[Date Prev][Date Next] [Chronological] [Thread] [Top]

Re: equality indexing

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

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

>E.g., use the
>first 4 bytes of the actual attribute value, plus the current equality hash.
>That way our equality lookups are still reasonably compact, and still
>unambiguous, but we also have a means for doing loose ordering indexing.
>  -- Howard Chu
>  Chief Architect, Symas Corp.       Director, Highland Sun
>  http://www.symas.com               http://highlandsun.com/hyc
>  Symas: Premier OpenSource Development and Support