search

Level / abstract-level

Abstract class for a lexicographically sorted key-value database.
MIT License
128 stars 8 forks source link

range queries inclusive/exclusive #24

Closed ronag closed 2 years ago

ronag commented 2 years ago

Currently the range options have some overlap and I'm wondering if we could remove the requirement for backends to implement both? e.g. rocksdb (and probably others) have support for inclusive lower bound (gte) and exclusive upper bound (lt).

I think we could e.g. emulate lte as lt + '\u0000' and gt as gt + '\uFFFF'. I'm not 100% sure. Thougths?

vweevers commented 2 years ago

I'm wondering if we could remove the requirement for backends to implement both?

Why?

ronag commented 2 years ago

I'm wondering if we could remove the requirement for backends to implement both?

Because it simplifies things for the backends, e.g. rocksdb has built-in support for lt and gte. Not sure about leveldb. Also the priorities between the overlapping options is not entirely clear and can cause weird bugs for implementers.

ronag commented 2 years ago

Also not having to do both is faster.

vweevers commented 2 years ago

Because it simplifies things for the backends, e.g. rocksdb has built-in support for lt and gte.

Do you have a link to relevant docs?

I expect it will be harder to ensure consistent behavior between rocksdb and leveldb. E.g. what happens if you seek() to a key outside the given range?

Also the priorities between the overlapping options is not entirely clear

See:

The gte and lte range options take precedence over gt and lt respectively. — https://github.com/Level/abstract-level#iterator--dbiteratoroptions

ronag commented 2 years ago

https://github.com/facebook/rocksdb/blob/main/include/rocksdb/options.h#L1404-L1433

vweevers commented 2 years ago

Apart from rocksdb, I don't know of any that have builtin support.

If we're gonna do this, it should be implemented internally, in rocks-level. Because the ltgte options are well known and used all over the ecosystem (including abstract-level itself, e.g. to implement sublevels). Doing the translation in the C++ of rocks-level also means we won't have to do more copies, can instead allocate one extra byte when we convert a given JS range option to a slice. And rocks-level would still pass the abstract-level test suite (assuming there are no edge cases, like the seek() case).

ronag commented 2 years ago

So it's easy to emulate this. Just need to append \0 to lte and gt. So in theory we could remove the requirement for backends to implement these.

vweevers commented 2 years ago

They can do so internally, should not affect the public API of abstract-level.