RE: Index Limitations with DBs?

["Howard Chu" <hyc@highlandsun.com>]

> -----Original Message-----
> From: owner-openldap-software@OpenLDAP.org
> [mailto:owner-openldap-software@OpenLDAP.org]On Behalf Of Lon Tierney

> At the Developer Day - SF, it was mentioned in Howard's talk about
> Hierarchical DB backend that BDB can not use indexes if there
> are over 64K
> entries in the DB. I don't recall what that had to do with
> the topic, but
> I am wondering how that applies to the choice of DB implementation?

That's not exactly what I said...

What I said is that in back-bdb, when any particular index slot gets to 64K
entries, it collapses from an explicit list of entry IDs into a range of IDs.
e.g., instead of it being a list 1,2,3,4,5,6,7,8 it becomes the range [1-8].

Now, in addition to attribute indices, there are also scope indices - subtree
and onelevel indices for every entry in the database, enumerating all of each
entry's children. There used to be a subtree index for the suffix/root of the
database too, and *that* index slot was fairly meaningless; and certainly
when you had more than 64K entries in your database, it would be turned into
a range. I removed that slot a long time ago. So when you do a subtree search
starting at the root of the database, no subtree index lookup is performed at
all. This is why this type of search is so much faster now than it used to
be, and it also contributed a 2x speedup to Adds since that slot no longer
needed updating.

> Is there a DB implementaiton that will give better indexing
> capabilities
> with LARGE numbers of entries? Here I am assuming LDBM backend.

LDBM indexing actually blows up at about 8K entries per slot. back-bdb is
better.
>
> Thanks!
> -lon


  -- Howard Chu
  Chief Architect, Symas Corp.       Director, Highland Sun
  http://www.symas.com               http://highlandsun.com/hyc
  Symas: Premier OpenSource Development and Support