You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by ma...@apache.org on 2007/08/18 20:24:22 UTC
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/
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
>>
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 Alex Karasulu <ak...@apache.org>.
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 )
> );
> }
>
>
>
>
>