You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@directory.apache.org by Alex Karasulu <ak...@apache.org> on 2007/08/18 21:18:30 UTC
Re: svn commit: r567310 - in /directory/apacheds/trunk: core/src/main/java/org/apache/directory/server/core/partition/impl/btree/ server-unit/src/test/java/org/apache/directory/server/
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 <ma...@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 )
> );
> }
>
>
>
>
>
Re: svn commit: r567310 - in /directory/apacheds/trunk: core/src/main/java/org/apache/directory/server/core/partition/impl/btree/
server-unit/src/test/java/org/apache/directory/server/
Posted by Martin Alderson <eq...@planetquake.com>.
Hi Alex,
We need both the entries that don't pass the specified filter for the
attribute, and those that don't have the attribute at all. We would
need a way to get all entries that are not contained in the index for
the attribute and a way to join that enumeration to the one we had in
the old code (which should be easy enough with a JoinedEnumeration class).
I think the current attribute indices need to be modified to store a
list of entries that do not have the attribute. Each index will then
take up a bit more space. All existing ApacheDS installations would
also need their attribute indices rebuilding too.
What do you think?
Martin
Alex Karasulu wrote:
> 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 <ma...@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
>>