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}