Return-Path: X-Original-To: apmail-directory-commits-archive@www.apache.org Delivered-To: apmail-directory-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 5EED9D25D for ; Fri, 7 Sep 2012 09:25:52 +0000 (UTC) Received: (qmail 25935 invoked by uid 500); 7 Sep 2012 09:25:52 -0000 Delivered-To: apmail-directory-commits-archive@directory.apache.org Received: (qmail 25902 invoked by uid 500); 7 Sep 2012 09:25:52 -0000 Mailing-List: contact commits-help@directory.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@directory.apache.org Delivered-To: mailing list commits@directory.apache.org Received: (qmail 25892 invoked by uid 99); 7 Sep 2012 09:25:52 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 07 Sep 2012 09:25:52 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 07 Sep 2012 09:25:48 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id 24E0323889C5 for ; Fri, 7 Sep 2012 09:25:06 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1381944 - in /directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server: core/partition/impl/btree/ xdbm/ xdbm/search/ xdbm/search/impl/ Date: Fri, 07 Sep 2012 09:25:05 -0000 To: commits@directory.apache.org From: elecharny@apache.org X-Mailer: svnmailer-1.0.8-patched Message-Id: <20120907092506.24E0323889C5@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org Author: elecharny Date: Fri Sep 7 09:25:05 2012 New Revision: 1381944 URL: http://svn.apache.org/viewvc?rev=1381944&view=rev Log: Decoupled the backend search result from the front end processing : we now return a set of UUID candidates which is fully computed in the SearchEngine, and the frontEnd is looping on the UUID, fetching the entries from the MasterTable. This allow the locks to be released fast. Added: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/PartitionSearchResult.java Modified: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/EntryCursorAdaptor.java directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexCursorAdaptor.java directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ForwardIndexEntry.java 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/DefaultSearchEngine.java Modified: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java?rev=1381944&r1=1381943&r2=1381944&view=diff ============================================================================== --- directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java (original) +++ directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java Fri Sep 7 09:25:05 2012 @@ -57,11 +57,12 @@ import org.apache.directory.server.xdbm. import org.apache.directory.server.xdbm.ParentIdAndRdn; import org.apache.directory.server.xdbm.Store; import org.apache.directory.server.xdbm.search.Optimizer; +import org.apache.directory.server.xdbm.search.PartitionSearchResult; import org.apache.directory.server.xdbm.search.SearchEngine; import org.apache.directory.server.xdbm.search.cursor.ChildrenCursor; +import org.apache.directory.server.xdbm.search.evaluator.PassThroughEvaluator; import org.apache.directory.shared.ldap.model.constants.SchemaConstants; import org.apache.directory.shared.ldap.model.cursor.Cursor; -import org.apache.directory.shared.ldap.model.cursor.SetCursor; import org.apache.directory.shared.ldap.model.entry.Attribute; import org.apache.directory.shared.ldap.model.entry.Entry; import org.apache.directory.shared.ldap.model.entry.Modification; @@ -917,16 +918,43 @@ public abstract class AbstractBTreeParti */ public EntryFilteringCursor list( ListOperationContext listContext ) throws LdapException { - return new BaseEntryFilteringCursor( - new EntryCursorAdaptor( this, - list( getEntryId( listContext.getDn() ) ) ), listContext ); + return list( getEntryId( listContext.getDn() ), listContext ); } /** * {@inheritDoc} */ - public final Cursor> list( String id ) throws LdapException + public Cursor> list( String id ) throws LdapException + { + try + { + Cursor> cursor = rdnIdx.forwardCursor(); + + IndexEntry startingPos = new ForwardIndexEntry(); + startingPos.setKey( new ParentIdAndRdn( id, ( Rdn[] ) null ) ); + cursor.before( startingPos ); + + dumpRdnIdx(); + + PartitionSearchResult searchResult = new PartitionSearchResult(); + Set> resultSet = new HashSet>(); + + Cursor> childrenCursor = new ChildrenCursor( this, id, cursor ); + + return childrenCursor; + } + catch ( Exception e ) + { + throw new LdapOperationErrorException( e.getMessage(), e ); + } + } + + + /** + * {@inheritDoc} + */ + public final EntryFilteringCursor list( String id, ListOperationContext listContext ) throws LdapException { try { @@ -940,7 +968,22 @@ public abstract class AbstractBTreeParti dumpRdnIdx(); - return new ChildrenCursor( this, id, cursor ); + PartitionSearchResult searchResult = new PartitionSearchResult(); + Set> resultSet = new HashSet>(); + + Cursor> childrenCursor = new ChildrenCursor( this, id, cursor ); + + while ( childrenCursor.next() ) + { + IndexEntry element = childrenCursor.get(); + resultSet.add( element ); + } + + searchResult.setResultSet( resultSet ); + searchResult.setEvaluator( new PassThroughEvaluator( this ) ); + + return new BaseEntryFilteringCursor( new EntryCursorAdaptor( this, searchResult ), + listContext ); } catch ( Exception e ) { @@ -964,11 +1007,10 @@ public abstract class AbstractBTreeParti AliasDerefMode derefMode = searchContext.getAliasDerefMode(); ExprNode filter = searchContext.getFilter(); - Set> result = searchEngine.buildResultSet( dn, derefMode, filter, scope ); - - Cursor underlying = new SetCursor>( result ); + PartitionSearchResult searchResult = searchEngine.computeResult( dn, derefMode, filter, scope ); - return new BaseEntryFilteringCursor( new EntryCursorAdaptor( this, underlying ), searchContext ); + return new BaseEntryFilteringCursor( new EntryCursorAdaptor( this, searchResult ), + searchContext ); } catch ( LdapException le ) { Modified: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/EntryCursorAdaptor.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/EntryCursorAdaptor.java?rev=1381944&r1=1381943&r2=1381944&view=diff ============================================================================== --- directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/EntryCursorAdaptor.java (original) +++ directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/EntryCursorAdaptor.java Fri Sep 7 09:25:05 2012 @@ -21,10 +21,13 @@ package org.apache.directory.server.core import org.apache.directory.server.xdbm.IndexEntry; +import org.apache.directory.server.xdbm.search.Evaluator; +import org.apache.directory.server.xdbm.search.PartitionSearchResult; import org.apache.directory.shared.ldap.model.cursor.AbstractCursor; import org.apache.directory.shared.ldap.model.cursor.ClosureMonitor; import org.apache.directory.shared.ldap.model.cursor.Cursor; import org.apache.directory.shared.ldap.model.entry.Entry; +import org.apache.directory.shared.ldap.model.filter.ExprNode; import org.slf4j.Logger; import org.slf4j.LoggerFactory; @@ -41,13 +44,15 @@ public class EntryCursorAdaptor extends private final AbstractBTreePartition db; private final Cursor> indexCursor; + private final Evaluator evaluator; - public EntryCursorAdaptor( AbstractBTreePartition db, Cursor> indexCursor ) + public EntryCursorAdaptor( AbstractBTreePartition db, PartitionSearchResult searchResult ) { LOG_CURSOR.debug( "Creating EntryCursorAdaptor {}", this ); this.db = db; - this.indexCursor = indexCursor; + indexCursor = searchResult.getResultSet(); + evaluator = searchResult.getEvaluator(); } @@ -138,13 +143,12 @@ public class EntryCursorAdaptor extends { IndexEntry indexEntry = indexCursor.get(); - if ( indexEntry.getEntry() == null ) + if ( evaluator.evaluate( indexEntry ) ) { - Entry entry = db.lookup( indexEntry.getId() ); - indexEntry.setEntry( entry ); + return indexEntry.getEntry(); } - return indexEntry.getEntry(); + return null; } Modified: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexCursorAdaptor.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexCursorAdaptor.java?rev=1381944&r1=1381943&r2=1381944&view=diff ============================================================================== --- directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexCursorAdaptor.java (original) +++ directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexCursorAdaptor.java Fri Sep 7 09:25:05 2012 @@ -63,7 +63,6 @@ public class IndexCursorAdaptor exten @SuppressWarnings("unchecked") public IndexCursorAdaptor( Cursor wrappedCursor, boolean forwardIndex ) { - LOG_CURSOR.debug( "Creating IndexCursorAdaptor {}", this ); this.wrappedCursor = wrappedCursor; if ( forwardIndex ) @@ -76,6 +75,8 @@ public class IndexCursorAdaptor exten forwardEntry = null; reverseEntry = new ReverseIndexEntry(); } + + LOG_CURSOR.debug( "Creating IndexCursorAdaptor {}", this ); } Modified: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ForwardIndexEntry.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ForwardIndexEntry.java?rev=1381944&r1=1381943&r2=1381944&view=diff ============================================================================== --- directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ForwardIndexEntry.java (original) +++ directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ForwardIndexEntry.java Fri Sep 7 09:25:05 2012 @@ -130,6 +130,45 @@ public class ForwardIndexEntry ex } + public int hashCode() + { + if ( getId() == null ) + { + return 0; + } + + return getId().hashCode(); + } + + + public boolean equals( IndexEntry that ) + { + if ( that == this ) + { + return true; + } + + if ( !( that instanceof ForwardIndexEntry ) ) + { + return false; + } + + ForwardIndexEntry thatIndexEntry = ( ForwardIndexEntry ) that; + + if ( thatIndexEntry.getId() == null ) + { + return getId() == null; + } + + if ( thatIndexEntry.getId().equals( getId() ) ) + { + return true; + } + + return false; + } + + /** * {@inheritDoc} */ Added: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/PartitionSearchResult.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/PartitionSearchResult.java?rev=1381944&view=auto ============================================================================== --- directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/PartitionSearchResult.java (added) +++ directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/PartitionSearchResult.java Fri Sep 7 09:25:05 2012 @@ -0,0 +1,138 @@ +/* + * 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.directory.server.xdbm.search; + + +import java.util.Set; + +import org.apache.directory.server.xdbm.IndexEntry; +import org.apache.directory.shared.ldap.model.cursor.SetCursor; +import org.apache.directory.shared.ldap.model.filter.ExprNode; + + +/** + * A class containing the result of a search : + *
    + *
  • A set of cadidate UUIDs
    • + *
  • A hierarchy of evaualtors to use to validate the candidates
    • + *
+ * @author Apache Directory Project + */ +public class PartitionSearchResult +{ + /** The set of candidate UUIDs selected by the search */ + private SetCursor> resultSet; + + /** The evaluator to validate the candidates */ + private Evaluator evaluator; + + + /** + * Create a PartitionSearchResult instance + */ + public PartitionSearchResult() + { + } + + + /** + * @return the resultSet + */ + public SetCursor> getResultSet() + { + return resultSet; + } + + + /** + * @param resultSet the resultSet to set + */ + public void setResultSet( Set> set ) + { + resultSet = new SetCursor>( set ); + } + + + /** + * @return the evaluator + */ + public Evaluator getEvaluator() + { + return evaluator; + } + + + /** + * @param evaluator the evaluator to set + */ + public void setEvaluator( Evaluator evaluator ) + { + this.evaluator = evaluator; + } + + + /** + * @see Object#toString() + */ + public String toString() + { + StringBuilder sb = new StringBuilder(); + + sb.append( "Search result : \n" ); + sb.append( evaluator ); + + if ( resultSet == null ) + { + sb.append( "No UUID found" ); + } + else + { + sb.append( '{' ); + boolean isFirst = true; + + try + { + while ( resultSet.next() ) + { + if ( isFirst ) + { + isFirst = false; + } + else + { + sb.append( ", " ); + } + + sb.append( resultSet.get().getId() ); + } + + resultSet.beforeFirst(); + } + catch ( Exception e ) + { + // Nothing we can do... + } + + sb.append( '}' ); + } + + return sb.toString(); + } +} 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=1381944&r1=1381943&r2=1381944&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 Fri Sep 7 09:25:05 2012 @@ -20,41 +20,42 @@ package org.apache.directory.server.xdbm.search.impl; -import java.util.ArrayList; import java.util.List; +import java.util.Set; +import java.util.regex.Pattern; +import org.apache.directory.server.core.api.partition.Partition; import org.apache.directory.server.i18n.I18n; -import org.apache.directory.server.xdbm.EmptyIndexCursor; +import org.apache.directory.server.xdbm.ForwardIndexEntry; +import org.apache.directory.server.xdbm.Index; import org.apache.directory.server.xdbm.IndexEntry; +import org.apache.directory.server.xdbm.ParentIdAndRdn; +import org.apache.directory.server.xdbm.SingletonIndexCursor; import org.apache.directory.server.xdbm.Store; -import org.apache.directory.server.xdbm.search.Evaluator; -import org.apache.directory.server.xdbm.search.cursor.AndCursor; import org.apache.directory.server.xdbm.search.cursor.ApproximateCursor; -import org.apache.directory.server.xdbm.search.cursor.EqualityCursor; -import org.apache.directory.server.xdbm.search.cursor.GreaterEqCursor; -import org.apache.directory.server.xdbm.search.cursor.LessEqCursor; -import org.apache.directory.server.xdbm.search.cursor.NotCursor; -import org.apache.directory.server.xdbm.search.cursor.OneLevelScopeCursor; -import org.apache.directory.server.xdbm.search.cursor.OrCursor; -import org.apache.directory.server.xdbm.search.cursor.PresenceCursor; -import org.apache.directory.server.xdbm.search.cursor.SubstringCursor; -import org.apache.directory.server.xdbm.search.cursor.SubtreeScopeCursor; +import org.apache.directory.server.xdbm.search.cursor.ChildrenCursor; +import org.apache.directory.server.xdbm.search.cursor.DescendantCursor; import org.apache.directory.server.xdbm.search.evaluator.ApproximateEvaluator; -import org.apache.directory.server.xdbm.search.evaluator.EqualityEvaluator; -import org.apache.directory.server.xdbm.search.evaluator.GreaterEqEvaluator; -import org.apache.directory.server.xdbm.search.evaluator.LessEqEvaluator; -import org.apache.directory.server.xdbm.search.evaluator.OneLevelScopeEvaluator; -import org.apache.directory.server.xdbm.search.evaluator.PresenceEvaluator; -import org.apache.directory.server.xdbm.search.evaluator.SubstringEvaluator; -import org.apache.directory.server.xdbm.search.evaluator.SubtreeScopeEvaluator; import org.apache.directory.shared.ldap.model.cursor.Cursor; import org.apache.directory.shared.ldap.model.entry.Entry; +import org.apache.directory.shared.ldap.model.entry.Value; import org.apache.directory.shared.ldap.model.filter.AndNode; +import org.apache.directory.shared.ldap.model.filter.ApproximateNode; +import org.apache.directory.shared.ldap.model.filter.EqualityNode; import org.apache.directory.shared.ldap.model.filter.ExprNode; +import org.apache.directory.shared.ldap.model.filter.GreaterEqNode; +import org.apache.directory.shared.ldap.model.filter.LessEqNode; import org.apache.directory.shared.ldap.model.filter.NotNode; import org.apache.directory.shared.ldap.model.filter.OrNode; +import org.apache.directory.shared.ldap.model.filter.PresenceNode; import org.apache.directory.shared.ldap.model.filter.ScopeNode; +import org.apache.directory.shared.ldap.model.filter.SubstringNode; import org.apache.directory.shared.ldap.model.message.SearchScope; +import org.apache.directory.shared.ldap.model.name.Rdn; +import org.apache.directory.shared.ldap.model.schema.AttributeType; +import org.apache.directory.shared.ldap.model.schema.MatchingRule; +import org.apache.directory.shared.ldap.model.schema.Normalizer; +import org.apache.directory.shared.ldap.model.schema.normalizers.NoOpNormalizer; import org.apache.directory.shared.util.exception.NotImplementedException; @@ -85,13 +86,13 @@ public class CursorBuilder } - public Cursor> build( ExprNode node ) throws Exception + public long build( ExprNode node, Set uuidSet ) throws Exception { Object count = node.get( "count" ); if ( ( count != null ) && ( ( Long ) count ) == 0L ) { - return ( Cursor ) new EmptyIndexCursor(); + return 0; } switch ( node.getAssertionType() ) @@ -99,62 +100,44 @@ public class CursorBuilder /* ---------- LEAF NODE HANDLING ---------- */ case APPROXIMATE: - return ( Cursor ) new ApproximateCursor( db, - ( ApproximateEvaluator ) evaluatorBuilder - .build( node ) ); + return computeApproximate( ( ApproximateNode ) node, uuidSet ); case EQUALITY: - return ( Cursor ) new EqualityCursor( db, - ( EqualityEvaluator ) evaluatorBuilder - .build( node ) ); + return computeEquality( ( EqualityNode ) node, uuidSet ); case GREATEREQ: - return ( Cursor ) new GreaterEqCursor( db, - ( GreaterEqEvaluator ) evaluatorBuilder - .build( node ) ); + return computeGreaterEq( ( GreaterEqNode ) node, uuidSet ); case LESSEQ: - return ( Cursor ) new LessEqCursor( db, - ( LessEqEvaluator ) evaluatorBuilder - .build( node ) ); + return computeLessEq( ( LessEqNode ) node, uuidSet ); case PRESENCE: - return ( Cursor ) new PresenceCursor( db, - ( PresenceEvaluator ) evaluatorBuilder - .build( node ) ); + return computePresence( ( PresenceNode ) node, uuidSet ); case SCOPE: - if ( ( ( ScopeNode ) node ).getScope() == SearchScope.ONELEVEL ) + if ( ( ( ScopeNode ) node ).getScope() == SearchScope.ONELEVEL ) { - return ( Cursor ) new OneLevelScopeCursor( - db, - ( OneLevelScopeEvaluator ) evaluatorBuilder - .build( node ) ); + return computeOneLevelScope( ( ScopeNode ) node, uuidSet ); } else { - return ( Cursor ) new SubtreeScopeCursor( - db, - ( SubtreeScopeEvaluator ) evaluatorBuilder - .build( node ) ); + return computeSubLevelScope( ( ScopeNode ) node, uuidSet ); } case SUBSTRING: - return ( Cursor ) new SubstringCursor( db, - ( SubstringEvaluator ) evaluatorBuilder - .build( node ) ); + return computeSubstring( ( SubstringNode ) node, uuidSet ); /* ---------- LOGICAL OPERATORS ---------- */ case AND: - return buildAndCursor( ( AndNode ) node ); + return computeAnd( ( AndNode ) node, uuidSet ); case NOT: - return ( Cursor ) new NotCursor( db, evaluatorBuilder.build( ( ( NotNode ) node ) - .getFirstChild() ) ); + // Always return infinite, except if the resulting eva + return computeNot( ( NotNode ) node, uuidSet ); case OR: - return buildOrCursor( ( OrNode ) node ); + return computeOr( ( OrNode ) node, uuidSet ); /* ---------- NOT IMPLEMENTED ---------- */ @@ -169,19 +152,427 @@ public class CursorBuilder /** + * Computes the set of candidates for an Approximate filter. We will feed the set only if + * we have an index for the AT. + */ + + private long computeApproximate( ApproximateNode node, Set uuidSet ) + throws Exception + { + ApproximateCursor cursor = new ApproximateCursor( db, + ( ApproximateEvaluator ) evaluatorBuilder + .build( node ) ); + + int nbResults = 0; + + while ( cursor.next() ) + { + IndexEntry indexEntry = cursor.get(); + + String uuid = indexEntry.getId(); + + if ( !uuidSet.contains( uuid ) ) + { + uuidSet.add( uuid ); + nbResults++; + } + } + + cursor.close(); + + return nbResults; + } + + + /** + * Computes the set of candidates for an Equality filter. We will feed the set only if + * we have an index for the AT. + */ + private long computeEquality( EqualityNode node, Set uuidSet ) + throws Exception + { + AttributeType attributeType = node.getAttributeType(); + Value value = node.getValue(); + int nbResults = 0; + + // Fetch all the UUIDs if we have an index + if ( db.hasIndexOn( attributeType ) ) + { + // Get the cursor using the index + Index userIndex = ( Index ) db.getIndex( attributeType ); + Cursor> userIdxCursor = userIndex.forwardCursor( value.getValue() ); + + // And loop on it + while ( userIdxCursor.next() ) + { + IndexEntry indexEntry = userIdxCursor.get(); + + String uuid = indexEntry.getId(); + + if ( !uuidSet.contains( uuid ) ) + { + // The UUID is not present in the Set, we add it + uuidSet.add( uuid ); + nbResults++; + } + } + + userIdxCursor.close(); + } + else + { + // No index, we will have to do a full scan + return Long.MAX_VALUE; + } + + return nbResults; + } + + + /** + * Computes the set of candidates for an GreateEq filter. We will feed the set only if + * we have an index for the AT. + */ + private long computeGreaterEq( GreaterEqNode node, Set uuidSet ) + throws Exception + { + AttributeType attributeType = node.getAttributeType(); + Value value = node.getValue(); + int nbResults = 0; + + // Fetch all the UUIDs if we have an index + if ( db.hasIndexOn( attributeType ) ) + { + // Get the cursor using the index + Index userIndex = ( Index ) db.getIndex( attributeType ); + Cursor> userIdxCursor = userIndex.forwardCursor(); + + // Position the index on the element we should start from + IndexEntry indexEntry = new ForwardIndexEntry(); + indexEntry.setKey( value.getValue() ); + + userIdxCursor.before( indexEntry ); + + // And loop on it + while ( userIdxCursor.next() ) + { + indexEntry = userIdxCursor.get(); + + String uuid = indexEntry.getId(); + + if ( !uuidSet.contains( uuid ) ) + { + // The UUID is not present in the Set, we add it + uuidSet.add( uuid ); + nbResults++; + } + } + + userIdxCursor.close(); + } + else + { + // No index, we will have to do a full scan + return Long.MAX_VALUE; + } + + return nbResults; + } + + + /** + * Computes the set of candidates for an LessEq filter. We will feed the set only if + * we have an index for the AT. + */ + private long computeLessEq( LessEqNode node, Set uuidSet ) + throws Exception + { + AttributeType attributeType = node.getAttributeType(); + Value value = node.getValue(); + int nbResults = 0; + + // Fetch all the UUIDs if we have an index + if ( db.hasIndexOn( attributeType ) ) + { + // Get the cursor using the index + Index userIndex = ( Index ) db.getIndex( attributeType ); + Cursor> userIdxCursor = userIndex.forwardCursor(); + + // Position the index on the element we should start from + IndexEntry indexEntry = new ForwardIndexEntry(); + indexEntry.setKey( value.getValue() ); + + userIdxCursor.after( indexEntry ); + + // And loop on it + while ( userIdxCursor.previous() ) + { + indexEntry = userIdxCursor.get(); + + String uuid = indexEntry.getId(); + + if ( !uuidSet.contains( uuid ) ) + { + // The UUID is not present in the Set, we add it + uuidSet.add( uuid ); + nbResults++; + } + } + + userIdxCursor.close(); + } + else + { + // No index, we will have to do a full scan + return Long.MAX_VALUE; + } + + return nbResults; + } + + + /** + * Computes the set of candidates for a Presence filter. We will feed the set only if + * we have an index for the AT. + */ + private long computePresence( PresenceNode node, Set uuidSet ) + throws Exception + { + AttributeType attributeType = node.getAttributeType(); + int nbResults = 0; + + // Fetch all the UUIDs if we have an index + if ( db.hasIndexOn( attributeType ) ) + { + // Get the cursor using the index + Cursor> presenceCursor = db.getPresenceIndex().forwardCursor( + attributeType.getOid() ); + + // Position the index on the element we should start from + IndexEntry indexEntry = new ForwardIndexEntry(); + + // And loop on it + while ( presenceCursor.next() ) + { + indexEntry = presenceCursor.get(); + + String uuid = indexEntry.getId(); + + if ( !uuidSet.contains( uuid ) ) + { + // The UUID is not present in the Set, we add it + uuidSet.add( uuid ); + nbResults++; + } + } + + presenceCursor.close(); + } + else + { + // No index, we will have to do a full scan + return Long.MAX_VALUE; + } + + return nbResults; + } + + + /** + * Computes the set of candidates for a OneLevelScope filter. We will feed the set only if + * we have an index for the AT. + */ + private long computeOneLevelScope( ScopeNode node, Set uuidSet ) + throws Exception + { + int nbResults = 0; + + // We use the RdnIndex to get all the entries from a starting point + // and below up to the number of children + Cursor> rdnCursor = db.getRdnIndex().forwardCursor(); + + IndexEntry startingPos = new ForwardIndexEntry(); + startingPos.setKey( new ParentIdAndRdn( node.getBaseId(), ( Rdn[] ) null ) ); + rdnCursor.before( startingPos ); + + Cursor> scopeCursor = new ChildrenCursor( db, node.getBaseId(), rdnCursor ); + + // Fetch all the UUIDs if we have an index + // And loop on it + while ( scopeCursor.next() ) + { + IndexEntry indexEntry = scopeCursor.get(); + + String uuid = indexEntry.getId(); + + if ( !uuidSet.contains( uuid ) ) + { + // The UUID is not present in the Set, we add it + uuidSet.add( uuid ); + nbResults++; + } + } + + scopeCursor.close(); + + return nbResults; + } + + + /** + * Computes the set of candidates for a SubLevelScope filter. We will feed the set only if + * we have an index for the AT. + */ + private long computeSubLevelScope( ScopeNode node, Set uuidSet ) + throws Exception + { + // If we are searching from the partition DN, better get out. + String contextEntryId = db.getEntryId( ( ( Partition ) db ).getSuffixDn() ); + + if ( node.getBaseId() == contextEntryId ) + { + return Long.MAX_VALUE; + } + + int nbResults = 0; + + // We use the RdnIndex to get all the entries from a starting point + // and below up to the number of descendant + String baseId = node.getBaseId(); + ParentIdAndRdn parentIdAndRdn = db.getRdnIndex().reverseLookup( baseId ); + IndexEntry startingPos = new ForwardIndexEntry(); + + startingPos.setKey( parentIdAndRdn ); + startingPos.setId( baseId ); + + Cursor> rdnCursor = new SingletonIndexCursor( + startingPos ); + String parentId = parentIdAndRdn.getParentId(); + + Cursor> scopeCursor = new DescendantCursor( db, baseId, parentId, rdnCursor ); + + // Fetch all the UUIDs if we have an index + // And loop on it + while ( scopeCursor.next() ) + { + IndexEntry indexEntry = scopeCursor.get(); + + String uuid = indexEntry.getId(); + + if ( !uuidSet.contains( uuid ) ) + { + // The UUID is not present in the Set, we add it + uuidSet.add( uuid ); + nbResults++; + } + } + + scopeCursor.close(); + + return nbResults; + } + + + /** + * Computes the set of candidates for an Substring filter. We will feed the set only if + * we have an index for the AT. + */ + private long computeSubstring( SubstringNode node, Set uuidSet ) + throws Exception + { + AttributeType attributeType = node.getAttributeType(); + + // Fetch all the UUIDs if we have an index + if ( db.hasIndexOn( attributeType ) ) + { + Index userIndex = ( ( Index ) db.getIndex( attributeType ) ); + Cursor> cursor = userIndex.forwardCursor(); + + // Position the index on the element we should start from + IndexEntry indexEntry = new ForwardIndexEntry(); + indexEntry.setKey( node.getInitial() ); + + cursor.before( indexEntry ); + int nbResults = 0; + + MatchingRule rule = attributeType.getSubstring(); + + if ( rule == null ) + { + rule = attributeType.getEquality(); + } + + Normalizer normalizer; + Pattern regexp; + + if ( rule != null ) + { + normalizer = rule.getNormalizer(); + } + else + { + normalizer = new NoOpNormalizer( attributeType.getSyntaxOid() ); + } + + // compile the regular expression to search for a matching attribute + // if the attributeType is humanReadable + if ( attributeType.getSyntax().isHumanReadable() ) + { + regexp = node.getRegex( normalizer ); + } + else + { + regexp = null; + } + + // And loop on it + while ( cursor.next() ) + { + indexEntry = cursor.get(); + + String key = indexEntry.getKey(); + + if ( !regexp.matcher( key ).matches() ) + { + cursor.close(); + + return nbResults; + } + + String uuid = indexEntry.getId(); + + if ( !uuidSet.contains( uuid ) ) + { + // The UUID is not present in the Set, we add it + uuidSet.add( uuid ); + nbResults++; + } + } + + cursor.close(); + + return nbResults; + } + else + { + // No index, we will have to do a full scan + return Long.MAX_VALUE; + } + } + + + /** * Creates a OrCursor over a disjunction expression branch node. * * @param node the disjunction expression branch node * @return Cursor over candidates satisfying disjunction expression * @throws Exception on db access failures */ - private Cursor> buildOrCursor( OrNode node ) throws Exception + private long computeOr( OrNode node, Set uuidSet ) throws Exception { List children = node.getChildren(); - List>> childCursors = new ArrayList>>( - children.size() ); - List> childEvaluators = new ArrayList>( - children.size() ); + + long nbOrResults = 0; // Recursively create Cursors and Evaluators for each child expression node for ( ExprNode child : children ) @@ -190,37 +581,34 @@ public class CursorBuilder if ( ( count != null ) && ( ( Long ) count == 0L ) ) { - // We can skip the cursor, it will not return any candidate - continue; + long countLong = ( Long ) count; + + if ( countLong == 0 ) + { + // We can skip the cursor, it will not return any candidate + continue; + } + else if ( countLong == Long.MAX_VALUE ) + { + // We can stop here, we will anyway do a full scan + return countLong; + } } - Cursor> childCursor = build( child ); + long nbResults = build( child, uuidSet ); - if ( childCursor instanceof EmptyIndexCursor ) + if ( nbResults == Long.MAX_VALUE ) { - // We can skip it - continue; + // We can stop here, we will anyway do a full scan + return nbResults; + } + else + { + nbOrResults += nbResults; } - - childCursors.add( childCursor ); - childEvaluators.add( evaluatorBuilder.build( child ) ); } - int size = childCursors.size(); - - switch ( size ) - { - case 0: - // All the cursor return 0, return an empty cursor - return ( Cursor ) new EmptyIndexCursor(); - - case 1: - // W can just return the remaining cursor - return childCursors.get( 0 ); - - default: - return new OrCursor( childCursors, childEvaluators ); - } + return nbOrResults; } @@ -231,7 +619,7 @@ public class CursorBuilder * @return Cursor over the conjunction expression * @throws Exception on db access failures */ - private Cursor> buildAndCursor( AndNode node ) throws Exception + private long computeAnd( AndNode node, Set uuidSet ) throws Exception { int minIndex = 0; long minValue = Long.MAX_VALUE; @@ -240,7 +628,7 @@ public class CursorBuilder /* * We scan the child nodes of a branch node searching for the child * expression node with the smallest scan count. This is the child - * we will use for iteration by creating a Cursor over its expression. + * we will use for iteration */ final List children = node.getChildren(); @@ -259,7 +647,7 @@ public class CursorBuilder if ( value == 0L ) { // No need to go any further : we won't have matching candidates anyway - return ( Cursor ) new EmptyIndexCursor(); + return 0L; } if ( value < minValue ) @@ -269,30 +657,41 @@ public class CursorBuilder } } - // Once found we build the child Evaluators minus the one for the minChild + // Once found we return the number of candidates for this child ExprNode minChild = children.get( minIndex ); - List> childEvaluators = new ArrayList>( - children.size() - 1 ); + long nbResults = build( minChild, uuidSet ); + + return nbResults; + } + + + /** + * Creates an AndCursor over a conjunction expression branch node. + * + * @param node a conjunction expression branch node + * @return Cursor over the conjunction expression + * @throws Exception on db access failures + */ + private long computeNot( NotNode node, Set uuidSet ) throws Exception + { + final List children = node.getChildren(); - // Do recursive call to build min child Cursor then create AndCursor - Cursor> childCursor = build( minChild ); + ExprNode child = children.get( 0 ); + Object count = child.get( "count" ); - if ( childCursor instanceof EmptyIndexCursor ) + if ( count == null ) { - // We can return directly : the And will not select any candidate - return childCursor; + return Long.MAX_VALUE; } - for ( ExprNode child : children ) - { - if ( child == minChild ) - { - continue; - } + long value = ( Long ) count; - childEvaluators.add( evaluatorBuilder.build( child ) ); + if ( value == Long.MAX_VALUE ) + { + // No need to go any further : we won't have matching candidates anyway + return 0L; } - return new AndCursor( childCursor, childEvaluators ); + return Long.MAX_VALUE; } } Modified: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/DefaultSearchEngine.java URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/DefaultSearchEngine.java?rev=1381944&r1=1381943&r2=1381944&view=diff ============================================================================== --- directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/DefaultSearchEngine.java (original) +++ directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/DefaultSearchEngine.java Fri Sep 7 09:25:05 2012 @@ -24,12 +24,14 @@ import java.util.HashSet; import java.util.Set; import org.apache.directory.server.core.api.partition.Partition; +import org.apache.directory.server.core.partition.impl.btree.IndexCursorAdaptor; import org.apache.directory.server.i18n.I18n; import org.apache.directory.server.xdbm.ForwardIndexEntry; import org.apache.directory.server.xdbm.IndexEntry; import org.apache.directory.server.xdbm.Store; import org.apache.directory.server.xdbm.search.Evaluator; import org.apache.directory.server.xdbm.search.Optimizer; +import org.apache.directory.server.xdbm.search.PartitionSearchResult; import org.apache.directory.server.xdbm.search.SearchEngine; import org.apache.directory.shared.ldap.model.cursor.Cursor; import org.apache.directory.shared.ldap.model.entry.Entry; @@ -100,20 +102,21 @@ public class DefaultSearchEngine impleme /** * {@inheritDoc} */ - public Set> buildResultSet( Dn base, AliasDerefMode aliasDerefMode, ExprNode filter, + public PartitionSearchResult computeResult( Dn base, AliasDerefMode aliasDerefMode, ExprNode filter, SearchScope scope ) throws Exception { Dn effectiveBase; String baseId = db.getEntryId( base ); - Set> result = new HashSet>(); + PartitionSearchResult searchSet = new PartitionSearchResult(); + Set> resultSet = new HashSet>(); // Check that we have an entry, otherwise we can immediately get out if ( baseId == null ) { if ( ( ( Partition ) db ).getSuffixDn().equals( base ) ) { - // The context entry is not created yet, return an empty cursor - return result; + // The context entry is not created yet, return an empty result + return searchSet; } else { @@ -177,13 +180,12 @@ public class DefaultSearchEngine impleme } indexEntry.setEntry( entry ); + resultSet.add( indexEntry ); - if ( evaluator.evaluate( indexEntry ) ) - { - result.add( indexEntry ); - } + searchSet.setEvaluator( evaluator ); + searchSet.setResultSet( resultSet ); - return result; + return searchSet; } // Add the scope node using the effective base to the filter @@ -194,16 +196,44 @@ public class DefaultSearchEngine impleme // Annotate the node with the optimizer and return search enumeration. optimizer.annotate( root ); + Evaluator evaluator = evaluatorBuilder.build( root ); - Cursor> cursor = ( Cursor ) cursorBuilder.build( root ); + Set uuidSet = new HashSet(); - while ( cursor.next() ) + long nbResults = cursorBuilder.build( root, uuidSet ); + + if ( nbResults < Long.MAX_VALUE ) + { + for ( String uuid : uuidSet ) + { + ForwardIndexEntry indexEntry = new ForwardIndexEntry(); + indexEntry.setId( uuid ); + resultSet.add( indexEntry ); + } + } + else { - IndexEntry indexEntry = cursor.get(); - result.add( indexEntry ); + // Full scan : use the MasterTable + Cursor> cursor = new IndexCursorAdaptor( db.getMasterTable().cursor(), true ); + + while ( cursor.next() ) + { + IndexEntry indexEntry = cursor.get(); + + // Here, the indexEntry contains a tuple. Convert it to + ForwardIndexEntry forwardIndexEntry = new ForwardIndexEntry(); + forwardIndexEntry.setKey( indexEntry.getKey() ); + forwardIndexEntry.setId( indexEntry.getKey() ); + forwardIndexEntry.setEntry( ( Entry ) indexEntry.getTuple().getValue() ); + + resultSet.add( forwardIndexEntry ); + } } - return result; + searchSet.setEvaluator( evaluator ); + searchSet.setResultSet( resultSet ); + + return searchSet; }