search

speedb-io / speedb

A RocksDB compliant high performance scalable embedded key-value store
https://www.speedb.io/
Apache License 2.0
852 stars 63 forks source link

PBS - Probabilistic search implementation in speedb #24

Open ayulas opened 2 years ago

ayulas commented 2 years ago

Why: Reduce CPU and improve performance of read and seek operation, especially when data resides in memory

What: Accelerate the index search by using a more sophisticated searching algorithm than binary search. By utilizing a probabilistic search algorithm (will be explained in a different scientific paper) save on search time and cpu cycles (do less searches then binary search) In order to select between binary search and probabilistic search another step in the sst creation needs to be done to not waste time on “trying” the right search algorithm.

ayulas commented 2 years ago

performance test: 1 - limit the seek to less steps (cpu) 2 - force index pin using cache_index_and_filter_blocks = false 3 - read hit miss