RE: equality indexing

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

> -----Original Message-----
> From: Kurt D. Zeilenga [mailto:Kurt@OpenLDAP.org]

> At 11:39 PM 1/20/2004, Howard Chu wrote:
> >If we used a Btree for the attribute indexes, and used the
> actual attribute
> >value (instead of the hash that we use now) for the key, we
> could use BDB's
> >Range feature to do >= indexing as well as equality. (I'm
> not sure we get <=
> >indexing out of this, haven't thought it all the way through yet.)
> >
> >As a compromise, we can use a "prefix" with the hash appended.
>
> This comprise is problematic as it means that many non-equal
> values would share the same index key.  While not too problematic
> for ordering matching, it likely is for server-side sorting
> purposes.

I'm not sure I see this index helping in a server-side-sort. We still return
candidate lists in ascending entryID order and a lot of code depends on this
fact.

> We may be better off looking into order-preserving key
> compression algorithms.

Yes, that would be ideal. Unfortunately most of those are dictionary-based.

Since we would need to override the index database's comapre function and set
it to a function that implements the attribute's ordering rule, I guess we
would also need to go back to subdatabases again because we wouldn't want to
interfere with substring indexing.

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