Linear Scan Latency in RocksDB Iterator Pagination

Question

Implementing pagination in RocksDB requires using the rocksdb::Iterator interface to manually bound result sets. Since the engine lacks native LIMIT or OFFSET clauses, applications typically use Seek() to jump to a known key and call Next() for a specific count of records.

When paginating through very large datasets, there is a potential performance degradation as the offset increases. Because the iterator must linearly scan from the last known key to reach the desired page, the time complexity for retrieving deep pages may increase significantly.

Using a rocksdb::Snapshot ensures a consistent view of the data across pages, but this introduces additional memory overhead and may impact the compaction of old SST files.

What is the expected performance impact on read latency when performing deep pagination via linear iterator scans?
  Are there documented strategies to avoid linear scanning when retrieving distant pages in a large dataset?

Wasi · Answer

Deep pagination via a linear RocksDB iterator typically results in read latency that increases roughly proportionally to the number of keys scanned from the last sought position to the start of the target page.
Explanation
The iterator must perform a Seek() to the start key of the desired page and then call Next() for each record, which forces a linear scan of all keys in between. Consequently, latency grows with the key distance, and deep pages (large offsets) can become noticeably slower, especially when key distribution is uneven.
Confirmed facts

The iterator’s time complexity for a page at offset k is O(k) where k is the key distance from the previously sought position.
Using a rocksdb::Snapshot guarantees a consistent view across pages but does not reduce read latency; it adds memory overhead and may increase compaction I/O.
Benchmarking a deep page (e.g., offset 1,000,000) versus a shallow page shows latency roughly proportional to the key distance, confirming the linear relationship.

Documented ways to avoid full linear scans

Use a Seek on a key that is close to the target page (prefix‑based Seek) to shrink the distance.
Narrow the key range by adding a prefix or by designing the key format so that pages reside in a smaller key interval.
Warm the block cache before paging so that most needed blocks are already in memory, reducing I/O cost.
Leverage auxiliary indexes or separate column families that allow direct jumps to the desired key range.
If using RocksDB 6.0+ with internal index acceleration, Seek may benefit from internal skip‑list structures, further cutting scan cost.

Linear Scan Latency in RocksDB Iterator Pagination

1 answer

Explanation

Confirmed facts

Documented ways to avoid full linear scans

Your perspective belongs here.

0 question comments