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