[Date Prev][Date Next]
[Chronological]
[Thread]
[Top]
RE: equality indexing
> -----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