slow search when out-of-scope entries match (ITS#2897)

[h.b.furuseth@usit.uio.no]

Full_Name: Hallvard B Furuseth
Version: 2.1.25
OS: Linux
URL: 
Submission from: (NULL) (129.240.186.42)
Submitted by: hallvard


With LDBM, a search for (objectclass=organization) in a big subtree
which contains no matching entries, takes a long time if there is
_another_ big subtree whose entries match.

A search for an objectclass which does not exist in the database
takes no time.

Objectclass has an 'eq' index.

When I try with a database with 50000 entires in scope without
'objectclass: organization' and 50000 entries out of scope with
'objectclass: organization', the 'slapd -d -1' output contains:

search_candidates: base="l=device,l=x" s=1 d=0
=> filter_candidates
	AND
=> list_candidates 0xa0
=> filter_candidates
	DN ONE
=> dn2idl( "%l=device,l=x" )
=> ldbm_cache_open( "dn2id.dbb", 73, 600 )
<= ldbm_cache_open (cache 0)
=> ldbm_cache_open( "nextid.dbb", 73, 600 )
ldbm_cache_open (blksize 8192) (maxids 2046) (maxindirect 5)
<= ldbm_cache_open (opened 2)
<= filter_candidates 100004
=> filter_candidates
	OR
=> list_candidates 0xa1
=> filter_candidates
	EQUALITY
=> equality_candidates
=> ldbm_cache_open( "objectClass.dbb", 73, 600 )
ldbm_cache_open (blksize 8192) (maxids 2046) (maxindirect 5)
<= ldbm_cache_open (opened 3)
=> key_read
<= index_read 0 candidates
<= equality_candidates NULL
<= equality_candidates 0
<= filter_candidates 0
=> filter_candidates
	EQUALITY
=> equality_candidates
=> ldbm_cache_open( "objectClass.dbb", 73, 600 )
<= ldbm_cache_open (cache 3)
=> key_read
<= index_read 100004 candidates
<= equality_candidates 100004
<= filter_candidates 100004
<= list_candidates 100004
<= filter_candidates 100004
<= list_candidates 100004
<= filter_candidates 100004
====> cache_return_entry_r( 2 ): created (0)

Then it does test_filter  100003 times, even though the
search scope only contains 50000 entries.


=== Configuration:
./configure --enable-aci --prefix=/ldap/test/usr --enable-ldbm

=== slapd.conf:
include		/ldap/test/usr/etc/openldap/schema/core.schema
database	ldbm
suffix		"l=x"
directory	/ldap/test/usr/var/openldap-ldbm
index objectClass eq

=== To generate the LDIF file:
#!/usr/bin/perl -l
%k = ("device", "cn", "organization", "o");
print "dn: l=x\nobjectClass: locality\nl: x\n";
foreach $c ("device", "organization") {
  print "dn: l=$c,l=x\nobjectClass: locality\nl: $c\n";
  for ($i = 0; $i < 50000; $i++) {
    print "dn: $k{$c}=$i,l=$c,l=x\nobjectClass: $c\n$k{$c}: $i\n";
  }
}

=== Search command (takes 70 seconds on my box):
/ldap/test/usr/bin/ldapsearch -h localhost:3890 -xLLL \
    -b l=device,l=x -s one "(objectclass=organization)"

(No entries returned.)