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

[Kurt@OpenLDAP.org]

This is an example of a search were each of the indexed components
of the search criteria are ineffective at reducing the number of
candidate entries.  Note that the indexed components include both
the filter and the scope.

There are a number of ways to address such issues:
        a) place admin limits on number of candidates,
        b) utilize "better" search criteria,
        c) utilize a "better" DIT organization,
        d) use multiple databases to localize searches/indices,
        e) tune slapd(8) (including changing various hardcoded constants)

This is not viewed as a bug in the software, but an inherent aspect
of the database backend design.

Kurt

At 09:32 AM 12/29/2003, h.b.furuseth@usit.uio.no wrote:
>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.)