search

simerplaha / SwayDB

Persistent and in-memory key-value storage engine for JVM that scales on a single machine.
https://swaydb.simer.au
Apache License 2.0
293 stars 16 forks source link

Improve reverse iteration performance #287

Closed simerplaha closed 4 years ago

simerplaha commented 4 years ago

Reverse iterations are slower than forward iteration because reverse iterations are dependant on binary-search whereas forward iterations simply read the next key-value from sorted-index.

Storing previous key-value's offset within next key-value would result in much better reverse iteration performance and it would also remove the dependancy on binary-search. This should be configurable (optimiseForReverseIteration) and optionally enabled since there is a storage cost. Applications that do not need reverse iteration can disable this to save storage.

The following chart shows the difference in performance on a Persistent-Segment.

image

simerplaha commented 4 years ago

Configuration optimiseForReverseIteration implemented.

The following show performance benchmark with optimiseForReverseIteration set to true

image

New reverse iteration performance is nearly the same as forward iteration.