Re: ordered indexing for integers

[Howard Chu <hyc@symas.com>]

Hallvard B Furuseth wrote:
> Quanah Gibson-Mount writes:
> > I think every other release has had incompatible changes, and if we are
> > contemplating one for 2.4, we need to do it sooner rather than later.
>
> Yes.  And I'd like to see this.
>
> If incompatibility worries people even as early as this in 2.4's life,
> we could leave the old format as the default in 2.4, and provide a
> slapd.conf-option to enable ordered indexing.

OK, I guess we can add a config option to switch formats.

> Howard Chu writes:
> > Currently the Presence index uses a hardcoded 4 byte key of
> > 0x00000001. I want to change it to a 2 byte key of 0x0000 instead, to
> > prevent it from colliding with the Integer key space.
>
> What representation are you planning?  My thoughts about it tend towards
> DER-inspired formats, something like this:

I was thinking of a fixed word size. Anything with variable length will 
require a custom B-tree sort function, and we really don't want to go there.

8-byte keys representing 64 bit integers would do. (In fact we could leave the 
presence index unchanged in that case.) We'd have to use a negated 2's 
complement representation, since the B-tree sorts keys as unsigned characters.
--
  -- Howard Chu
  Chief Architect, Symas Corp.  http://www.symas.com
  Director, Highland Sun        http://highlandsun.com/hyc/
  Chief Architect, OpenLDAP     http://www.openldap.org/project/