Re: ordered indexing for integers

[Hallvard B Furuseth <h.b.furuseth@usit.uio.no>]

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.


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:

for values small enough to keep the exact value in the index:
  <0x80 + sign*(#bytes needed)> <those bytes of 2's complement value>
for larger absoulte values:
  same, but for the sake of speed read the value as hex, so we only
  need read the first digits (skipping initial zeros).
for huge values, something like:
  (value < 0 ? 0 : 255),
  <0x8000... + sign*#length octets>
  <sign*length...>
  <initial part of two's complement value-as-hex>

Too complicated?

> So far, 2.4 and 2.3 have totally identical database formats. Is it
> worthwhile to break this compatibility to gain this feature, or better
> to preserve compatibility and ignore this feature for now? Any
> thoughts on going ahead with it here in RE24?

I think it's worth it.  But it would be possible to support both too (at
least until 2.5).  Could make the max size of a key configurable, and
only use this format if that option is set.

-- 
Regards,
Hallvard