001/*
002 * (C) Copyright 2014 Nuxeo SA (http://nuxeo.com/) and contributors.
003 *
004 * All rights reserved. This program and the accompanying materials
005 * are made available under the terms of the GNU Lesser General Public License
006 * (LGPL) version 2.1 which accompanies this distribution, and is available at
007 * http://www.gnu.org/licenses/lgpl-2.1.html
008 *
009 * This library is distributed in the hope that it will be useful,
010 * but WITHOUT ANY WARRANTY; without even the implied warranty of
011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012 * Lesser General Public License for more details.
013 *
014 * Contributors:
015 *     Florent Guillaume
016 */
017package org.nuxeo.ecm.core.storage;
018
019import java.util.Collections;
020import java.util.HashSet;
021import java.util.Iterator;
022import java.util.LinkedList;
023import java.util.Set;
024
025import org.nuxeo.ecm.core.api.impl.FacetFilter;
026import org.nuxeo.ecm.core.query.sql.NXQL;
027import org.nuxeo.ecm.core.query.sql.model.Expression;
028import org.nuxeo.ecm.core.query.sql.model.FromClause;
029import org.nuxeo.ecm.core.query.sql.model.FromList;
030import org.nuxeo.ecm.core.query.sql.model.Literal;
031import org.nuxeo.ecm.core.query.sql.model.LiteralList;
032import org.nuxeo.ecm.core.query.sql.model.MultiExpression;
033import org.nuxeo.ecm.core.query.sql.model.Operand;
034import org.nuxeo.ecm.core.query.sql.model.Operator;
035import org.nuxeo.ecm.core.query.sql.model.Reference;
036import org.nuxeo.ecm.core.query.sql.model.SQLQuery;
037import org.nuxeo.ecm.core.query.sql.model.SelectClause;
038import org.nuxeo.ecm.core.query.sql.model.SelectList;
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<String>(schemaManager.getNoPerDocumentQueryFacets());
069        toplevelOperands = new LinkedList<Operand>();
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<String>();
110        FromList elements = node.elements;
111        for (int i = 0; i < elements.size(); i++) {
112            String typeName = elements.get(i);
113            if (TYPE_DOCUMENT.equalsIgnoreCase(typeName)) {
114                typeName = TYPE_DOCUMENT;
115            }
116
117            Set<String> subTypes = schemaManager.getDocumentTypeNamesExtending(typeName);
118            if (subTypes == null) {
119                throw new RuntimeException("Unknown type: " + typeName);
120            }
121            fromTypes.addAll(subTypes);
122            boolean isRelation = false;
123            do {
124                if (TYPE_RELATION.equals(typeName)) {
125                    isRelation = true;
126                    break;
127                }
128                Type t = schemaManager.getDocumentType(typeName);
129                if (t != null) {
130                    t = t.getSuperType();
131                }
132                typeName = t == null ? null : t.getName();
133            } while (typeName != null);
134            onlyRelations = onlyRelations && isRelation;
135        }
136        fromTypes.remove(TYPE_ROOT);
137        LiteralList list = new LiteralList();
138        for (String type : fromTypes) {
139            list.add(new StringLiteral(type));
140        }
141        toplevelOperands.add(new Expression(new Reference(NXQL.ECM_PRIMARYTYPE), Operator.IN, list));
142    }
143
144    /**
145     * Expand toplevel ANDed operands into simple list.
146     */
147    protected void analyzeToplevelOperands(Operand node) {
148        if (node instanceof Expression) {
149            Expression expr = (Expression) node;
150            Operator op = expr.operator;
151            if (op == Operator.AND) {
152                analyzeToplevelOperands(expr.lvalue);
153                analyzeToplevelOperands(expr.rvalue);
154                return;
155            }
156        }
157        toplevelOperands.add(node);
158    }
159
160    /**
161     * Simplify ecm:primaryType positive references, and non-per-instance mixin types.
162     */
163    protected void simplifyToplevelOperands() {
164        Set<String> primaryTypes = null; // if defined, required
165        for (Iterator<Operand> it = toplevelOperands.iterator(); it.hasNext();) {
166            // whenever we don't know how to optimize the expression,
167            // we just continue the loop
168            Operand node = it.next();
169            if (!(node instanceof Expression)) {
170                continue;
171            }
172            Expression expr = (Expression) node;
173            if (!(expr.lvalue instanceof Reference)) {
174                continue;
175            }
176            String name = ((Reference) expr.lvalue).name;
177            Operator op = expr.operator;
178            Operand rvalue = expr.rvalue;
179            if (NXQL.ECM_PRIMARYTYPE.equals(name)) {
180                if (op != Operator.EQ && op != Operator.IN) {
181                    continue;
182                }
183                Set<String> set;
184                if (op == Operator.EQ) {
185                    if (!(rvalue instanceof StringLiteral)) {
186                        continue;
187                    }
188                    String primaryType = ((StringLiteral) rvalue).value;
189                    set = new HashSet<String>(Collections.singleton(primaryType));
190                } else { // Operator.IN
191                    if (!(rvalue instanceof LiteralList)) {
192                        continue;
193                    }
194                    set = getStringLiterals((LiteralList) rvalue);
195                }
196                if (primaryTypes == null) {
197                    primaryTypes = set;
198                } else {
199                    primaryTypes.retainAll(set);
200                }
201                it.remove(); // expression simplified into primaryTypes set
202            } else if (NXQL.ECM_MIXINTYPE.equals(name)) {
203                if (op != Operator.EQ && op != Operator.NOTEQ) {
204                    continue;
205                }
206                if (!(rvalue instanceof StringLiteral)) {
207                    continue;
208                }
209                String mixin = ((StringLiteral) rvalue).value;
210                if (!neverPerInstanceMixins.contains(mixin)) {
211                    // mixin per instance -> primary type checks not enough
212                    continue;
213                }
214                Set<String> set = schemaManager.getDocumentTypeNamesForFacet(mixin);
215                if (set == null) {
216                    // unknown mixin
217                    set = Collections.emptySet();
218                }
219                if (primaryTypes == null) {
220                    if (op == Operator.EQ) {
221                        primaryTypes = new HashSet<String>(set); // copy
222                    } else {
223                        continue; // unknown positive, no optimization
224                    }
225                } else {
226                    if (op == Operator.EQ) {
227                        primaryTypes.retainAll(set);
228                    } else {
229                        primaryTypes.removeAll(set);
230                    }
231                }
232                it.remove(); // expression simplified into primaryTypes set
233            }
234        }
235        // readd the simplified primary types constraints
236        if (primaryTypes != null) {
237            if (primaryTypes.isEmpty()) {
238                // TODO better removal
239                primaryTypes.add("__NOSUCHTYPE__");
240            }
241            Expression expr;
242            if (primaryTypes.size() == 1) {
243                String pt = primaryTypes.iterator().next();
244                expr = new Expression(new Reference(NXQL.ECM_PRIMARYTYPE), Operator.EQ, new StringLiteral(pt));
245            } else { // primaryTypes.size() > 1
246                LiteralList list = new LiteralList();
247                for (String pt : primaryTypes) {
248                    list.add(new StringLiteral(pt));
249                }
250                expr = new Expression(new Reference(NXQL.ECM_PRIMARYTYPE), Operator.IN, list);
251            }
252            toplevelOperands.addFirst(expr);
253        }
254    }
255
256    protected static Set<String> getStringLiterals(LiteralList list) {
257        Set<String> set = new HashSet<String>();
258        for (Literal literal : list) {
259            if (!(literal instanceof StringLiteral)) {
260                throw new RuntimeException("requires string literals");
261            }
262            set.add(((StringLiteral) literal).value);
263        }
264        return set;
265    }
266}