Author: thomasm
Date: Wed Feb 5 12:57:38 2014
New Revision: 1564753
URL: http://svn.apache.org/r1564753
Log:
OAK-1372 XPath queries with both path and property restrictions are slow (WIP:
estimate the total cost of all selectors)
Added:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/SelectorExecutionPlan.java
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/Query.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/QueryImpl.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/UnionQueryImpl.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/FullTextSearchImpl.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/JoinImpl.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/SelectorImpl.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/SourceImpl.java
jackrabbit/oak/trunk/oak-core/src/test/resources/org/apache/jackrabbit/oak/query/xpath.txt
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/Query.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/Query.java?rev=1564753&r1=1564752&r2=1564753&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/Query.java
(original)
+++
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/Query.java
Wed Feb 5 12:57:38 2014
@@ -73,6 +73,8 @@ public interface Query {
* @return the query plan
*/
String getPlan();
+
+ double getEstimatedCost();
Tree getTree(String path);
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/QueryImpl.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/QueryImpl.java?rev=1564753&r1=1564752&r2=1564753&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/QueryImpl.java
(original)
+++
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/QueryImpl.java
Wed Feb 5 12:57:38 2014
@@ -54,6 +54,7 @@ import org.apache.jackrabbit.oak.query.a
import org.apache.jackrabbit.oak.query.ast.SelectorImpl;
import org.apache.jackrabbit.oak.query.ast.SourceImpl;
import org.apache.jackrabbit.oak.query.ast.UpperCaseImpl;
+import org.apache.jackrabbit.oak.query.index.FilterImpl;
import org.apache.jackrabbit.oak.query.index.TraversingIndex;
import org.apache.jackrabbit.oak.spi.query.Filter;
import org.apache.jackrabbit.oak.spi.query.PropertyValues;
@@ -111,6 +112,8 @@ public class QueryImpl implements Query
private ExecutionContext context;
private final NamePathMapper namePathMapper;
+
+ private double estimatedCost;
QueryImpl(String statement, SourceImpl source, ConstraintImpl constraint,
ColumnImpl[] columns, NamePathMapper mapper) {
@@ -421,7 +424,12 @@ public class QueryImpl implements Query
@Override
public String getPlan() {
- return source.getPlan(context.getBaseState());
+ return source.getPlan(context.getBaseState()); // + " cost: " +
estimatedCost;
+ }
+
+ @Override
+ public double getEstimatedCost() {
+ return estimatedCost;
}
@Override
@@ -430,7 +438,7 @@ public class QueryImpl implements Query
return;
}
prepared = true;
- source.prepare();
+ estimatedCost = source.prepare();
}
/**
@@ -593,12 +601,13 @@ public class QueryImpl implements Query
this.traversalFallback = traversal;
}
- public QueryIndex getBestIndex(Filter filter) {
- return getBestIndex(context.getBaseState(), filter,
+ public SelectorExecutionPlan getBestSelectorExecutionPlan(FilterImpl
filter) {
+ return getBestSelectorExecutionPlan(context.getBaseState(), filter,
context.getIndexProvider(), traversalFallback);
}
- private static QueryIndex getBestIndex(NodeState rootState, Filter filter,
+ private static SelectorExecutionPlan getBestSelectorExecutionPlan(
+ NodeState rootState, FilterImpl filter,
QueryIndexProvider indexProvider, boolean traversalFallback) {
QueryIndex best = null;
if (LOG.isDebugEnabled()) {
@@ -619,8 +628,14 @@ public class QueryImpl implements Query
if (bestCost == Double.POSITIVE_INFINITY && traversalFallback) {
best = new TraversingIndex();
+ bestCost = best.getCost(filter, rootState);
}
- return best;
+ SelectorExecutionPlan plan = new SelectorExecutionPlan();
+ plan.filter = filter;
+ plan.estimatedCost = bestCost;
+ plan.index = best;
+ plan.selector = filter.getSelector();
+ return plan;
}
@Override
Added:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/SelectorExecutionPlan.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/SelectorExecutionPlan.java?rev=1564753&view=auto
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/SelectorExecutionPlan.java
(added)
+++
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/SelectorExecutionPlan.java
Wed Feb 5 12:57:38 2014
@@ -0,0 +1,39 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.jackrabbit.oak.query;
+
+import org.apache.jackrabbit.oak.query.ast.SelectorImpl;
+import org.apache.jackrabbit.oak.spi.query.Filter;
+import org.apache.jackrabbit.oak.spi.query.QueryIndex;
+
+/**
+ * An execution plan for one selector in a query. The conditions of the given
+ * selectors are compiled into a filter, and the execution plan for the
selector
+ * is to use a certain query index, which will result in an estimated cost to
+ * use that index to retrieve nodes for this index.
+ */
+public class SelectorExecutionPlan {
+
+ public Filter filter;
+
+ public SelectorImpl selector;
+
+ public double estimatedCost;
+
+ public QueryIndex index;
+
+}
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/UnionQueryImpl.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/UnionQueryImpl.java?rev=1564753&r1=1564752&r2=1564753&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/UnionQueryImpl.java
(original)
+++
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/UnionQueryImpl.java
Wed Feb 5 12:57:38 2014
@@ -106,6 +106,11 @@ public class UnionQueryImpl implements Q
left.prepare();
right.prepare();
}
+
+ @Override
+ public double getEstimatedCost() {
+ return left.getEstimatedCost() + right.getEstimatedCost();
+ }
@Override
public List<String> getBindVariableNames() {
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/FullTextSearchImpl.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/FullTextSearchImpl.java?rev=1564753&r1=1564752&r2=1564753&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/FullTextSearchImpl.java
(original)
+++
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/FullTextSearchImpl.java
Wed Feb 5 12:57:38 2014
@@ -161,7 +161,7 @@ public class FullTextSearchImpl extends
// to avoid running out of memory if the node is large,
// and because we might not implement all features
// such as index aggregation
- if (selector.index instanceof FulltextQueryIndex) {
+ if (selector.getIndex() instanceof FulltextQueryIndex) {
// first verify if a property level condition exists and if that
// condition checks out, this takes out some extra rows from the
index
// aggregation bits
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/JoinImpl.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/JoinImpl.java?rev=1564753&r1=1564752&r2=1564753&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/JoinImpl.java
(original)
+++
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/JoinImpl.java
Wed Feb 5 12:57:38 2014
@@ -119,9 +119,14 @@ public class JoinImpl extends SourceImpl
}
@Override
- public void prepare() {
- left.prepare();
- right.prepare();
+ public double prepare() {
+ // the estimated cost is the cost of the left selector,
+ // plus twice the cost of the right selector (we expect
+ // two rows for the right selector for each node
+ // on the left selector)
+ double cost = left.prepare();
+ cost += 2 * right.prepare();
+ return cost;
}
@Override
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/SelectorImpl.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/SelectorImpl.java?rev=1564753&r1=1564752&r2=1564753&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/SelectorImpl.java
(original)
+++
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/SelectorImpl.java
Wed Feb 5 12:57:38 2014
@@ -43,11 +43,11 @@ import org.apache.jackrabbit.oak.api.Tre
import org.apache.jackrabbit.oak.api.Type;
import org.apache.jackrabbit.oak.commons.PathUtils;
import org.apache.jackrabbit.oak.query.QueryImpl;
+import org.apache.jackrabbit.oak.query.SelectorExecutionPlan;
import org.apache.jackrabbit.oak.query.fulltext.FullTextExpression;
import org.apache.jackrabbit.oak.query.index.FilterImpl;
import org.apache.jackrabbit.oak.spi.query.Cursor;
import org.apache.jackrabbit.oak.spi.query.Cursors;
-import org.apache.jackrabbit.oak.spi.query.Filter;
import org.apache.jackrabbit.oak.spi.query.IndexRow;
import org.apache.jackrabbit.oak.spi.query.PropertyValues;
import org.apache.jackrabbit.oak.spi.query.QueryIndex;
@@ -62,7 +62,7 @@ import com.google.common.collect.Iterabl
public class SelectorImpl extends SourceImpl {
// TODO possibly support using multiple indexes (using index intersection
/ index merge)
- protected QueryIndex index;
+ protected SelectorExecutionPlan plan;
/**
* the node type associated with the {@link #nodeTypeName}
@@ -185,11 +185,11 @@ public class SelectorImpl extends Source
}
public boolean isPrepared() {
- return index != null;
+ return plan != null;
}
@Override
- public void prepare() {
+ public double prepare() {
if (queryConstraint != null) {
queryConstraint.restrictPushDown(this);
}
@@ -198,13 +198,14 @@ public class SelectorImpl extends Source
c.restrictPushDown(this);
}
}
- index = query.getBestIndex(createFilter(true));
+ plan = query.getBestSelectorExecutionPlan(createFilter(true));
+ return plan.estimatedCost;
}
@Override
public void execute(NodeState rootState) {
- if (index != null) {
- cursor = index.query(createFilter(false), rootState);
+ if (plan.index != null) {
+ cursor = plan.index.query(createFilter(false), rootState);
} else {
cursor = Cursors.newPathCursor(new ArrayList<String>());
}
@@ -215,8 +216,8 @@ public class SelectorImpl extends Source
StringBuilder buff = new StringBuilder();
buff.append(toString());
buff.append(" /* ");
- if (index != null) {
- buff.append(index.getPlan(createFilter(true), rootState));
+ if (getIndex() != null) {
+ buff.append(getIndex().getPlan(createFilter(true), rootState));
} else {
buff.append("no-index");
}
@@ -234,7 +235,7 @@ public class SelectorImpl extends Source
* @return the filter
*/
@Override
- public Filter createFilter(boolean preparing) {
+ public FilterImpl createFilter(boolean preparing) {
FilterImpl f = new FilterImpl(this, query.getStatement());
f.setPreparing(preparing);
if (joinCondition != null) {
@@ -563,4 +564,8 @@ public class SelectorImpl extends Source
}
}
+ QueryIndex getIndex() {
+ return plan == null ? null : plan.index;
+ }
+
}
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/SourceImpl.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/SourceImpl.java?rev=1564753&r1=1564752&r2=1564753&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/SourceImpl.java
(original)
+++
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/query/ast/SourceImpl.java
Wed Feb 5 12:57:38 2014
@@ -151,9 +151,11 @@ public abstract class SourceImpl extends
/**
* Prepare executing the query (recursively). This method will decide which
* index to use.
+ *
+ * @return the estimated cost
*/
- public abstract void prepare();
-
+ public abstract double prepare();
+
/**
* Execute the query. The current node is set to before the first row.
*
Modified:
jackrabbit/oak/trunk/oak-core/src/test/resources/org/apache/jackrabbit/oak/query/xpath.txt
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/test/resources/org/apache/jackrabbit/oak/query/xpath.txt?rev=1564753&r1=1564752&r2=1564753&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/test/resources/org/apache/jackrabbit/oak/query/xpath.txt
(original)
+++
jackrabbit/oak/trunk/oak-core/src/test/resources/org/apache/jackrabbit/oak/query/xpath.txt
Wed Feb 5 12:57:38 2014
@@ -25,6 +25,9 @@
# property names with missing @
+xpath2sql /jcr:root/testroot//b/c/d/*[@jcr:uuid='1' or @jcr:uuid='2']
+select d.[jcr:path] as [jcr:path], d.[jcr:score] as [jcr:score], d.* from
[nt:base] as a inner join [nt:base] as b on ischildnode(b, a) inner join
[nt:base] as c on ischildnode(c, b) inner join [nt:base] as d on ischildnode(d,
c) where name(a) = 'b' and isdescendantnode(a, '/testroot') and name(b) = 'c'
and name(c) = 'd' and (d.[jcr:uuid] = '1' or d.[jcr:uuid] = '2') /* xpath:
/jcr:root/testroot//b/c/d/*[@jcr:uuid='1' or @jcr:uuid='2'] */
+
xpath2sql /jcr:root/test/*[@a='1' and b='2' and jcr:contains(c, '3') and
jcr:contains(., '4') and jcr:contains(@d, '5')] order by e
select [jcr:path], [jcr:score], * from [nt:base] as a where [a] = '1' and [b]
= '2' and contains([c/*], '3') and contains(*, '4') and contains([d], '5') and
ischildnode(a, '/test') order by [e] /* xpath: /jcr:root/test/*[@a='1' and
b='2' and jcr:contains(c, '3') and jcr:contains(., '4') and jcr:contains(@d,
'5')] order by e */
