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}