3

Context: I'm reading about RocksDB and LSM trees, from my understanding Bloom filter is used to avoid multiple I/Os for item retrieval in all the storage levels. And I'm ok with that.

Apparently, one of the challenges is that Bloom filter cannot be used in range queries. What is the reason? If I want to check if there is a key between 32 and 200, I can do a single-key lookup for each value in between (or stop at the first "true" response). Is it really inefficient?

Thomas Mueller
  • 48,905
  • 14
  • 116
  • 132
Murray
  • 97
  • 8

1 Answers1

2

You can do that but it is inefficient because single point lookup are slow (even with bloom filters) comparing to seeking the first value (32) and iterating towards 200. Leveldb/rocksdb are optimized for such iterations.

Furthermore in your case you just want any first key between 32 and 200 - you just do one seek and that's it while otherwise you'd have to do in worst case 200-32 = 168 lookups. Bloom filter can quickly answer whether the key is not present if there are no collisions, but it still requires a disk lookup if there is.

ren
  • 3,843
  • 9
  • 50
  • 95
  • for future reference, you may want to take a look at SuRF. It won the best paper at SIGMOD this year. http://www.pdl.cmu.edu/PDL-FTP/Storage/surf_sigmod18.pdf It is a filter that supports range queries, and was tested in RocksDB. – shinjin Dec 07 '18 at 07:44
  • I am still lost without modifying BF its not possible to do range queries, is there any trick that RocksDB implemented? – Laukik Dec 28 '22 at 14:45