jackrabbit-oak-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From thom...@apache.org
Subject svn commit: r1564753 - in /jackrabbit/oak/trunk/oak-core/src: main/java/org/apache/jackrabbit/oak/query/ main/java/org/apache/jackrabbit/oak/query/ast/ test/resources/org/apache/jackrabbit/oak/query/
Date Wed, 05 Feb 2014 12:57:38 GMT
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 */
 



Mime
View raw message