Something akin +Infinity and -Infinity for ordered binary?

[vladar]

We are using arrays of JS primitives as keys for composite indexes and it works nice (ordered-binary is pretty cool!).

But now what we need is to run range queries. Does ordered binary has some special values that are "guaranteed to be before any other value" or "guaranteed to be after any other value"?

We can workaround this for "before" case using Symbols but is there a better alternative? Basically, some value that is never stored in lmdb-store keys but could be used in range queries to indicate the min/max possible binary value?

Example:

[1, `a`],
[2, `a`],
[2, `z`],
[3, `a`],

Then run something like this:

getRange({ start: [2], end: [2, Symbol.for(`+BinaryInfinity`)] })

to get all items starting with [2]?

[vladar]

Also, is it possible to expose ordered-binary methods from lmdb-store? I'd like to use it with dupSort (as encoded values).

I tried using the npm package (pure JS one) but it doesn't actually encode arrays?

[kriszyp]

I generally do something like this:

const HIGHEST_BYTE = Buffer.from([255]);
getRange({ start: [2], end: [2, HIGHEST_BYTE ]})

The highest bytes in ordered-binary are UTF-8, which can't have a first byte higher than 239. You could probably also safely use '\uffff'.

As far as exposing ordered-binary functionality, lmdb-store should actually export bufferToKeyValue and keyValueToBuffer (I exported them for testing purposes). I do have intentions of getting the pure JS package working and aligned again, since there are actually some situations where the conversion can be done faster in JS than in C++.

[vladar]

Heh, that's what I came up with as well for range boundary. Thanks for the hint!

As for bufferToKeyValue and keyValueToBuffer - node is just silently crashing for me when trying to use those functions:

const { bufferToKeyValue, keyValueToBuffer } = require("lmdb-store")
console.log(`1`)
const buffer = keyValueToBuffer(`foo`)
console.log(`2`)
const key = bufferToKeyValue(buffer)
console.log(key)

This outputs:

1

No exception or error output.

[vladar]

Also maybe just expose ordered-binary as another possible encoding for values (e.g. suitable for dupSort collections)?

[kriszyp]

Ok, I fixed the keyValueToBuffer error in v1.5.3. Adding ordered-binary as an encoding sounds like a good idea.

[vladar]

I can confirm that those methods seem to be working now however they still randomly crash node when values are a couple of kilobytes.

const { bufferToKeyValue, keyValueToBuffer } = require("lmdb-store")

console.log(`1`)
const buffer = keyValueToBuffer(`x`.repeat(1000))
console.log(`2`)
const key = bufferToKeyValue(buffer)
console.log(`3`, key)

Works 70% of the time and silently crashes 30% of the time

P.S. I realize LMDB keys are restricted by length, just trying to figure out if I need to ensure length or lmdb-store can throw in this case.

[kriszyp]

Yes, lmdb-store should enforce that. I had recently increased the maximum key size (from the LMDB default of 511 to the real maximum of 1978), but hadn't done it everywhere, so it the check wasn't properly being enforced. That should be fixed with the latest commit.

[vladar]

Another question related to ordered-binary - is there a way to inverse bits of one element of the key array?

The use-case is rather simple - imagine a secondary index similar to compound MongoDB index: { foo: 1, bar: -1 } (which is sort by "foo" ascending and "bar" - descending). When indexing actual value { foo: 1, bar: 2 } and storing a tuple in LMDB key (e.g. [1,2]) traversal is possible only in the same direction (either ascending or descending).

We don't have a way to apply custom key comparators but I guess we can at least invert binary values when inserting? But that requires messing with ordered-binary encoding so curious what do you think about it.

[kriszyp]

users may have both variants in the same index db basically.

I am not sure what this means. You can't change the key encoding on the fly, the keys are in the database itself. Of course if you want to simply iterate through a query backwards, you can use the reverse flag, but if you want to negate part of a key so that you can change the fundamental order of the database (where one key in an array is negated in relation to the other), well, you would need a new database (or rebuild) for that key encoding.

FWIW, in a typical SQL database, if you have an index on one field and then sort on that field in a combination with another, it will end up just doing the tie-breaking part of the sort in memory (for each sequence of entries that are tied by the first field).

[vladar]

I actually don't know how they do it internally in MongoDB but my assumption was that they do some sort of bitwise NOT operation on part of they key before saving it to db. E.g. the normal binary numbers representation is:

1: 0001
2: 0010
3: 0011
4: 0100

and negated is:

1: 1110
2: 1101
3: 1100
4: 1011

Now you want to store some keys in the database:

[1,1]
[3,2]
[3,3]
[3,4]

but keep the second element of the key negated. So you essentially do something like:

db.put([3, negate(2)], ``)

Then those keys are stored as:

[0001,1110] ([1,1])
[0011,1011] ([3,4])
[0011,1100] ([3,3])
[0011,1101] ([3,2])

Now if you want to run range queries against this, you do:

items.getRange({ start: [3, negate(2)], end: [3, negate(3)] })

And iteration will be in "mixed" order (virtually). But you will need to negate the second element of the key anytime you access it - if you need to (or just store a normal representation in a value).

Not sure if it makes any sense.

[vladar]

Oh, you also need to swap those pieces in range filters to make it work, so it is quite a wonderland 😅 Probably doesn't worth the effort, was just curious if it is possible in theory.

[kriszyp]

Yes, that is how I was intending to implement (using negation). And I initially thought using a function/operator to indicate negation would be good, but because you need to make sure that it is consistently applied, I think it makes more sense as an up-front "configuration" for database key. Also, you need to be able to deserialize these for returning keys in range iterators; if this was an ad-hoc application, we would need some way to store information that the second part of the key was negated, and that it has to be negated again to be deserialized. With a key configuration, that information would already be known to the key decoder. For the configuration, it might be nice to have a fully composable key configuration for encoding:

open({
  keyEncoding: [orderedBinary, negated(orderedBinary), negated(uint32), binary] // define really complex keys for a db
...

[vladar]

Yes, that makes perfect sense now. And I think it is possible to modify keys in a way that will work for more dynamic use-cases like ours.

E.g. we can create one db: { keyEncoding: [normal, negated, normal] } and then adjust a key like that:

[normal1, normal2, negated3, normal4, normal5] to
[[normal1, normal2], [negated3], [normal4, normal5]]

to make it fit.