001/*
002 * (C) Copyright 2014-2016 Nuxeo SA (http://nuxeo.com/) and others.
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 *     http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 *
016 * Contributors:
017 *     Florent Guillaume
018 */
019package org.nuxeo.ecm.core.storage;
020
021import java.util.Collections;
022import java.util.HashSet;
023import java.util.Iterator;
024import java.util.LinkedList;
025import java.util.Set;
026
027import org.nuxeo.ecm.core.api.impl.FacetFilter;
028import org.nuxeo.ecm.core.query.sql.NXQL;
029import org.nuxeo.ecm.core.query.sql.model.Expression;
030import org.nuxeo.ecm.core.query.sql.model.FromClause;
031import org.nuxeo.ecm.core.query.sql.model.FromList;
032import org.nuxeo.ecm.core.query.sql.model.Literal;
033import org.nuxeo.ecm.core.query.sql.model.LiteralList;
034import org.nuxeo.ecm.core.query.sql.model.MultiExpression;
035import org.nuxeo.ecm.core.query.sql.model.Operand;
036import org.nuxeo.ecm.core.query.sql.model.Operator;
037import org.nuxeo.ecm.core.query.sql.model.Reference;
038import org.nuxeo.ecm.core.query.sql.model.SQLQuery;
039import org.nuxeo.ecm.core.query.sql.model.StringLiteral;
040import org.nuxeo.ecm.core.schema.SchemaManager;
041import org.nuxeo.ecm.core.schema.types.Type;
042import org.nuxeo.runtime.api.Framework;
043
044/**
045 * Generic optimizer for a NXQL query.
046 *
047 * @since 5.9.4
048 */
049public class QueryOptimizer {
050
051    public static final String TYPE_ROOT = "Root";
052
053    public static final String TYPE_DOCUMENT = "Document";
054
055    public static final String TYPE_RELATION = "Relation";
056
057    protected final SchemaManager schemaManager;
058
059    protected final Set<String> neverPerInstanceMixins;
060
061    protected final LinkedList<Operand> toplevelOperands;
062
063    /** Do we match only relations? */
064    protected boolean onlyRelations;
065
066    public QueryOptimizer() {
067        schemaManager = Framework.getLocalService(SchemaManager.class);
068        neverPerInstanceMixins = new HashSet<>(schemaManager.getNoPerDocumentQueryFacets());
069        toplevelOperands = new LinkedList<>();
070    }
071
072    public MultiExpression getOptimizedQuery(SQLQuery query, FacetFilter facetFilter) {
073        if (facetFilter != null) {
074            addFacetFilterClauses(facetFilter);
075        }
076        visitFromClause(query.from); // for primary types
077        if (query.where != null) {
078            analyzeToplevelOperands(query.where.predicate);
079        }
080        simplifyToplevelOperands();
081        return new MultiExpression(Operator.AND, toplevelOperands);
082    }
083
084    protected void addFacetFilterClauses(FacetFilter facetFilter) {
085        for (String mixin : facetFilter.required) {
086            // every facet is required, not just any of them,
087            // so do them one by one
088            Expression expr = new Expression(new Reference(NXQL.ECM_MIXINTYPE), Operator.EQ, new StringLiteral(mixin));
089            toplevelOperands.add(expr);
090        }
091        if (!facetFilter.excluded.isEmpty()) {
092            LiteralList list = new LiteralList();
093            for (String mixin : facetFilter.excluded) {
094                list.add(new StringLiteral(mixin));
095            }
096            Expression expr = new Expression(new Reference(NXQL.ECM_MIXINTYPE), Operator.NOTIN, list);
097            toplevelOperands.add(expr);
098        }
099    }
100
101    /**
102     * Finds all the types to take into account (all concrete types being a subtype of the passed types) based on the
103     * FROM list.
104     * <p>
105     * Adds them as a ecm:primaryType match in the toplevel operands.
106     */
107    protected void visitFromClause(FromClause node) {
108        onlyRelations = true;
109        Set<String> fromTypes = new HashSet<>();
110        FromList elements = node.elements;
111        for (String typeName : elements.values()) {
112            if (TYPE_DOCUMENT.equalsIgnoreCase(typeName)) {
113                typeName = TYPE_DOCUMENT;
114            }
115
116            Set<String> subTypes = schemaManager.getDocumentTypeNamesExtending(typeName);
117            if (subTypes == null) {
118                throw new RuntimeException("Unknown type: " + typeName);
119            }
120            fromTypes.addAll(subTypes);
121            boolean isRelation = false;
122            do {
123                if (TYPE_RELATION.equals(typeName)) {
124                    isRelation = true;
125                    break;
126                }
127                Type t = schemaManager.getDocumentType(typeName);
128                if (t != null) {
129                    t = t.getSuperType();
130                }
131                typeName = t == null ? null : t.getName();
132            } while (typeName != null);
133            onlyRelations = onlyRelations && isRelation;
134        }
135        fromTypes.remove(TYPE_ROOT);
136        LiteralList list = new LiteralList();
137        for (String type : fromTypes) {
138            list.add(new StringLiteral(type));
139        }
140        toplevelOperands.add(new Expression(new Reference(NXQL.ECM_PRIMARYTYPE), Operator.IN, list));
141    }
142
143    /**
144     * Expand toplevel ANDed operands into simple list.
145     */
146    protected void analyzeToplevelOperands(Operand node) {
147        if (node instanceof Expression) {
148            Expression expr = (Expression) node;
149            Operator op = expr.operator;
150            if (op == Operator.AND) {
151                analyzeToplevelOperands(expr.lvalue);
152                analyzeToplevelOperands(expr.rvalue);
153                return;
154            }
155        }
156        toplevelOperands.add(node);
157    }
158
159    /**
160     * Simplify ecm:primaryType positive references, and non-per-instance mixin types.
161     */
162    protected void simplifyToplevelOperands() {
163        Set<String> primaryTypes = null; // if defined, required
164        for (Iterator<Operand> it = toplevelOperands.iterator(); it.hasNext();) {
165            // whenever we don't know how to optimize the expression,
166            // we just continue the loop
167            Operand node = it.next();
168            if (!(node instanceof Expression)) {
169                continue;
170            }
171            Expression expr = (Expression) node;
172            if (!(expr.lvalue instanceof Reference)) {
173                continue;
174            }
175            String name = ((Reference) expr.lvalue).name;
176            Operator op = expr.operator;
177            Operand rvalue = expr.rvalue;
178            if (NXQL.ECM_PRIMARYTYPE.equals(name)) {
179                if (op != Operator.EQ && op != Operator.IN) {
180                    continue;
181                }
182                Set<String> set;
183                if (op == Operator.EQ) {
184                    if (!(rvalue instanceof StringLiteral)) {
185                        continue;
186                    }
187                    String primaryType = ((StringLiteral) rvalue).value;
188                    set = new HashSet<>(Collections.singleton(primaryType));
189                } else { // Operator.IN
190                    if (!(rvalue instanceof LiteralList)) {
191                        continue;
192                    }
193                    set = getStringLiterals((LiteralList) rvalue);
194                }
195                if (primaryTypes == null) {
196                    primaryTypes = set;
197                } else {
198                    primaryTypes.retainAll(set);
199                }
200                it.remove(); // expression simplified into primaryTypes set
201            } else if (NXQL.ECM_MIXINTYPE.equals(name)) {
202                if (op != Operator.EQ && op != Operator.NOTEQ) {
203                    continue;
204                }
205                if (!(rvalue instanceof StringLiteral)) {
206                    continue;
207                }
208                String mixin = ((StringLiteral) rvalue).value;
209                if (!neverPerInstanceMixins.contains(mixin)) {
210                    // mixin per instance -> primary type checks not enough
211                    continue;
212                }
213                Set<String> set = schemaManager.getDocumentTypeNamesForFacet(mixin);
214                if (set == null) {
215                    // unknown mixin
216                    set = Collections.emptySet();
217                }
218                if (primaryTypes == null) {
219                    if (op == Operator.EQ) {
220                        primaryTypes = new HashSet<>(set); // copy
221                    } else {
222                        continue; // unknown positive, no optimization
223                    }
224                } else {
225                    if (op == Operator.EQ) {
226                        primaryTypes.retainAll(set);
227                    } else {
228                        primaryTypes.removeAll(set);
229                    }
230                }
231                it.remove(); // expression simplified into primaryTypes set
232            }
233        }
234        // readd the simplified primary types constraints
235        if (primaryTypes != null) {
236            if (primaryTypes.isEmpty()) {
237                // TODO better removal
238                primaryTypes.add("__NOSUCHTYPE__");
239            }
240            Expression expr;
241            if (primaryTypes.size() == 1) {
242                String pt = primaryTypes.iterator().next();
243                expr = new Expression(new Reference(NXQL.ECM_PRIMARYTYPE), Operator.EQ, new StringLiteral(pt));
244            } else { // primaryTypes.size() > 1
245                LiteralList list = new LiteralList();
246                for (String pt : primaryTypes) {
247                    list.add(new StringLiteral(pt));
248                }
249                expr = new Expression(new Reference(NXQL.ECM_PRIMARYTYPE), Operator.IN, list);
250            }
251            toplevelOperands.addFirst(expr);
252        }
253    }
254
255    protected static Set<String> getStringLiterals(LiteralList list) {
256        Set<String> set = new HashSet<>();
257        for (Literal literal : list) {
258            if (!(literal instanceof StringLiteral)) {
259                throw new RuntimeException("requires string literals");
260            }
261            set.add(((StringLiteral) literal).value);
262        }
263        return set;
264    }
265}