directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1378851 - in /directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl: CursorBuilder.java EvaluatorBuilder.java
Date Thu, 30 Aug 2012 08:31:56 GMT
Author: elecharny
Date: Thu Aug 30 08:31:56 2012
New Revision: 1378851

URL: http://svn.apache.org/viewvc?rev=1378851&view=rev
Log:
o Removed the cursor and evaluators when the count is 0, as we won't have any candidate from
those cursors.
o Removed the Or and And cursors when they only have one single child
This results in a 15% speed improvement in complex filter searches.

Modified:
    directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/CursorBuilder.java
    directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/EvaluatorBuilder.java

Modified: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/CursorBuilder.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/CursorBuilder.java?rev=1378851&r1=1378850&r2=1378851&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/CursorBuilder.java
(original)
+++ directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/CursorBuilder.java
Thu Aug 30 08:31:56 2012
@@ -22,9 +22,9 @@ package org.apache.directory.server.xdbm
 
 import java.util.ArrayList;
 import java.util.List;
-import java.util.UUID;
 
 import org.apache.directory.server.i18n.I18n;
+import org.apache.directory.server.xdbm.EmptyIndexCursor;
 import org.apache.directory.server.xdbm.IndexEntry;
 import org.apache.directory.server.xdbm.Store;
 import org.apache.directory.server.xdbm.search.Evaluator;
@@ -79,6 +79,13 @@ public class CursorBuilder
 
     public <T> Cursor<IndexEntry<?, String>> build( ExprNode node ) throws
Exception
     {
+        Object count = node.get( "count" );
+
+        if ( ( count != null ) && ( ( Long ) count ) == 0L )
+        {
+            return ( Cursor ) new EmptyIndexCursor<T>();
+        }
+
         switch ( node.getAssertionType() )
         {
         /* ---------- LEAF NODE HANDLING ---------- */
@@ -160,7 +167,7 @@ public class CursorBuilder
      * @return Cursor over candidates satisfying disjunction expression
      * @throws Exception on db access failures
      */
-    private Cursor<IndexEntry<?, String>> buildOrCursor( OrNode node ) throws
Exception
+    private <T> Cursor<IndexEntry<?, String>> buildOrCursor( OrNode node
) throws Exception
     {
         List<ExprNode> children = node.getChildren();
         List<Cursor<IndexEntry<?, String>>> childCursors = new ArrayList<Cursor<IndexEntry<?,
String>>>(
@@ -171,11 +178,41 @@ public class CursorBuilder
         // Recursively create Cursors and Evaluators for each child expression node
         for ( ExprNode child : children )
         {
-            childCursors.add( build( child ) );
+            Object count = child.get( "count" );
+
+            if ( ( count != null ) && ( ( Long ) count == 0L ) )
+            {
+                // We can skip the cursor, it will not return any candidate
+                continue;
+            }
+
+            Cursor<IndexEntry<?, String>> childCursor = build( child );
+
+            if ( childCursor instanceof EmptyIndexCursor )
+            {
+                // We can skip it
+                continue;
+            }
+
+            childCursors.add( childCursor );
             childEvaluators.add( evaluatorBuilder.build( child ) );
         }
 
-        return new OrCursor( childCursors, childEvaluators );
+        int size = childCursors.size();
+
+        switch ( size )
+        {
+            case 0:
+                // All the cursor return 0, return an empty cursor
+                return ( Cursor ) new EmptyIndexCursor<T>();
+
+            case 1:
+                // W can just return the remaining cursor
+                return childCursors.get( 0 );
+
+            default:
+                return new OrCursor( childCursors, childEvaluators );
+        }
     }
 
 
@@ -186,7 +223,7 @@ public class CursorBuilder
      * @return Cursor over the conjunction expression
      * @throws Exception on db access failures
      */
-    private Cursor<IndexEntry<?, String>> buildAndCursor( AndNode node ) throws
Exception
+    private <T> Cursor<IndexEntry<?, String>> buildAndCursor( AndNode node
) throws Exception
     {
         int minIndex = 0;
         long minValue = Long.MAX_VALUE;
@@ -210,10 +247,16 @@ public class CursorBuilder
             }
 
             value = ( Long ) count;
-            minValue = Math.min( minValue, value );
 
-            if ( minValue == value )
+            if ( value == 0L )
             {
+                // No need to go any further : we won't have matching candidates anyway
+                return ( Cursor ) new EmptyIndexCursor<T>();
+            }
+
+            if ( value < minValue )
+            {
+                minValue = value;
                 minIndex = i;
             }
         }
@@ -223,6 +266,15 @@ public class CursorBuilder
         List<Evaluator<? extends ExprNode>> childEvaluators = new ArrayList<Evaluator<?
extends ExprNode>>(
             children.size() - 1 );
 
+        // Do recursive call to build min child Cursor then create AndCursor
+        Cursor<IndexEntry<?, String>> childCursor = build( minChild );
+
+        if ( childCursor instanceof EmptyIndexCursor )
+        {
+            // We can return directly : the And will not select any candidate
+            return childCursor;
+        }
+
         for ( ExprNode child : children )
         {
             if ( child == minChild )
@@ -233,9 +285,6 @@ public class CursorBuilder
             childEvaluators.add( evaluatorBuilder.build( child ) );
         }
 
-        // Do recursive call to build min child Cursor then create AndCursor
-        Cursor<IndexEntry<?, String>> childCursor = build( minChild );
-
         return new AndCursor( childCursor, childEvaluators );
     }
 }

Modified: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/EvaluatorBuilder.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/EvaluatorBuilder.java?rev=1378851&r1=1378850&r2=1378851&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/EvaluatorBuilder.java
(original)
+++ directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/EvaluatorBuilder.java
Thu Aug 30 08:31:56 2012
@@ -82,6 +82,12 @@ public class EvaluatorBuilder
 
     public <T> Evaluator<? extends ExprNode> build( ExprNode node ) throws Exception
     {
+        Object count = node.get( "count" );
+        if ( ( count != null ) && ( ( Long ) count == 0L ) )
+        {
+            return null;
+        }
+
         switch ( node.getAssertionType() )
         {
         /* ---------- LEAF NODE HANDLING ---------- */
@@ -137,28 +143,63 @@ public class EvaluatorBuilder
     }
 
 
-    AndEvaluator buildAndEvaluator( AndNode node ) throws Exception
+    private <T> Evaluator<? extends ExprNode> buildAndEvaluator( AndNode node
) throws Exception
     {
         List<ExprNode> children = node.getChildren();
-        List<Evaluator<? extends ExprNode>> evaluators = new ArrayList<Evaluator<?
extends ExprNode>>(
-            children.size() );
-        for ( ExprNode child : children )
+        List<Evaluator<? extends ExprNode>> evaluators = buildList( children
);
+
+        int size = evaluators.size();
+
+        switch ( size )
         {
-            evaluators.add( build( child ) );
+            case 0:
+                return null;
+
+            case 1:
+                return evaluators.get( 0 );
+
+            default:
+                return new AndEvaluator( node, evaluators );
         }
-        return new AndEvaluator( node, evaluators );
     }
 
 
-    OrEvaluator buildOrEvaluator( OrNode node ) throws Exception
+    private <T> Evaluator<? extends ExprNode> buildOrEvaluator( OrNode node )
throws Exception
     {
         List<ExprNode> children = node.getChildren();
+        List<Evaluator<? extends ExprNode>> evaluators = buildList( children
);
+
+        int size = evaluators.size();
+
+        switch ( size )
+        {
+            case 0:
+                return null;
+
+            case 1:
+                return evaluators.get( 0 );
+
+            default:
+                return new OrEvaluator( node, evaluators );
+        }
+    }
+
+
+    private List<Evaluator<? extends ExprNode>> buildList( List<ExprNode>
children ) throws Exception
+    {
         List<Evaluator<? extends ExprNode>> evaluators = new ArrayList<Evaluator<?
extends ExprNode>>(
             children.size() );
+
         for ( ExprNode child : children )
         {
-            evaluators.add( build( child ) );
+            Evaluator<? extends ExprNode> evaluator = build( child );
+
+            if ( evaluator != null )
+            {
+                evaluators.add( build( child ) );
+            }
         }
-        return new OrEvaluator( node, evaluators );
+
+        return evaluators;
     }
 }



Mime
View raw message