Is there no way to use indices with searches that use a negation operator in the filter?  I'm feeling
like perhaps we're nixing out the whole thing to solve the problem.  Then again what's the performance
impact of a full master scan verses a full index scan.

Alex

On 8/18/07, malderson@apache.org < malderson@apache.org> wrote:
Author: malderson
Date: Sat Aug 18 11:24:21 2007
New Revision: 567310

URL: http://svn.apache.org/viewvc?view=rev&rev=567310
Log:
Fix for DIRSERVER-951, where a search with a negated filter on an indexed attribute won't find entries without the attribute.

Modified:
    directory/apacheds/trunk/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/DefaultOptimizer.java
    directory/apacheds/trunk/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/ExpressionEnumerator.java
    directory/apacheds/trunk/server-unit/src/test/java/org/apache/directory/server/DIRSERVER951ITest.java

Modified: directory/apacheds/trunk/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/DefaultOptimizer.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/DefaultOptimizer.java?view=diff&rev=567310&r1=567309&r2=567310
==============================================================================
--- directory/apacheds/trunk/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/DefaultOptimizer.java (original)
+++ directory/apacheds/trunk/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/DefaultOptimizer.java Sat Aug 18 11:24:21 2007
@@ -201,14 +201,9 @@


     /**
-     * Negation counts are estimated in one of two ways depending on its
-     * composition.  If the sole child of the negation is a leaf and an index
-     * exists for the attribute of the leaf then the count on the index is taken
-     * as the scan count.  If the child is a branch node then the count of the
-     * negation node is set to the total count of entries in the master table.
-     * This last resort tactic is used to get a rough estimate because it would
-     * cost too much to get an exact estimate on the count of a negation on a
-     * branch node.
+     * A negation filter is always worst case since we will have to retrieve all
+     * entries from the master table then test each one against the negated
+     * child filter.  There is no way to use the indices.
      *
      * @param node the negation node
      * @return the scan count
@@ -216,25 +211,7 @@
      */
     private Long getNegationScan( BranchNode node ) throws NamingException
     {
-        ExprNode onlyChild = node.getChildren().get( 0 );
-
-        annotate( onlyChild );
-
-        if ( onlyChild.isLeaf() && !( onlyChild instanceof ScopeNode ) && !( onlyChild instanceof AssertionNode )
-            && !( onlyChild instanceof PresenceNode ) )
-        {
-            LeafNode leaf = ( LeafNode ) onlyChild;
-
-            if ( db.hasUserIndexOn( leaf.getAttribute() ) )
-            {
-                Index idx = db.getUserIndex( leaf.getAttribute() );
-                return Long.valueOf( idx.count() );
-            }
-
-            return Long.valueOf( db.count() );
-        }
-
-        return Long.valueOf( db.count() );
+        return MAX;
     }



Modified: directory/apacheds/trunk/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/ExpressionEnumerator.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/ExpressionEnumerator.java?view=diff&rev=567310&r1=567309&r2=567310
==============================================================================
--- directory/apacheds/trunk/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/ExpressionEnumerator.java (original)
+++ directory/apacheds/trunk/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/ExpressionEnumerator.java Sat Aug 18 11:24:21 2007
@@ -184,31 +184,10 @@
      */
     private NamingEnumeration enumNeg( final BranchNode node ) throws NamingException
     {
-        Index idx = null;
-        NamingEnumeration childEnumeration = null;
+        NamingEnumeration baseEnumeration = null;
         NamingEnumeration enumeration = null;
-
-        // Iterates over entire set of index values
-        if ( node.getChild().isLeaf() )
-        {
-            LeafNode child = ( LeafNode ) node.getChild();
-
-            if ( db.hasUserIndexOn( child.getAttribute() ) )
-            {
-                idx = db.getUserIndex( child.getAttribute() );
-                childEnumeration = idx.listIndices();
-            }
-            else
-            {
-                childEnumeration = db.getNdnIndex().listIndices();
-            }
-        }
-        // Iterates over the entire set of entries
-        else
-        {
-            idx = db.getNdnIndex();
-            childEnumeration = idx.listIndices();
-        }
+
+        baseEnumeration = db.getNdnIndex().listIndices();

         IndexAssertion assertion = new IndexAssertion()
         {
@@ -221,7 +200,7 @@
             }
         };

-        enumeration = new IndexAssertionEnumeration( childEnumeration, assertion, true );
+        enumeration = new IndexAssertionEnumeration( baseEnumeration, assertion, true );
         return enumeration;
     }


Modified: directory/apacheds/trunk/server-unit/src/test/java/org/apache/directory/server/DIRSERVER951ITest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/server-unit/src/test/java/org/apache/directory/server/DIRSERVER951ITest.java?view=diff&rev=567310&r1=567309&r2=567310
==============================================================================
--- directory/apacheds/trunk/server-unit/src/test/java/org/apache/directory/server/DIRSERVER951ITest.java (original)
+++ directory/apacheds/trunk/server-unit/src/test/java/org/apache/directory/server/DIRSERVER951ITest.java Sat Aug 18 11:24:21 2007
@@ -122,11 +122,10 @@
      */
     public void testSearchNotCN() throws Exception
     {
-        //NOTE: This test is disabled while waiting for a fix to DIRSERVER-951.  Uncomment to re-enable.
-//        Set<SearchResult> results = getResults( "(!(cn=test1))" );
-//        assertFalse( contains( "uid=test1,ou=test,ou=system", results ) );
-//        assertTrue( contains( "uid=test2,ou=test,ou=system", results ) );
-//        assertTrue( contains( "uid=testNoCN,ou=test,ou=system", results ) );
+        Set<SearchResult> results = getResults( "(!(cn=test1))" );
+        assertFalse( contains( "uid=test1,ou=test,ou=system", results ) );
+        assertTrue( contains( "uid=test2,ou=test,ou=system", results ) );
+        assertTrue( contains( "uid=testNoCN,ou=test,ou=system", results ) );
     }