cockroachdb / cockroachdb/pebble
db: push down visibility filtering
- Dominant language
- Go
- Stars
- 6k
- Forks
- 584
- Avg merge
- 16h 35m
- Merged PRs (30d)
- 5
Description
Today, sequence number visibility filtering is applied in the merging iterator, after merging across levels.
Invisible keys are expected to be rare. Iterators created from snapshots may observe them in any level. Iterators created from the current version may only encounter invisible keys in two places:
1. If reading through an indexed batch, mutations applied to the batch since the last call to SetOptions are invisible.
2. Keys written to the mutable memtable after the iterator is opened are invisible.
In Cockroach, small, high-write regions of the keyspace like the lock table may accumulate a swath of invisible keys over the lifetime of an iterator. When there _is_ an accumulation of invisible keys, each individual key must be returned up to the merging iterator, which must perform key comparisons per invisible key to restore heap order. These comparisons are unfortunate, because they could be elided by a cheaper sequence number comparison.
We could consider pushing down the sequence number comparison to allow for cheaper skipping of new, invisible keys. This would also have the fortuitous side effect of simplifying visibility checking since only the batch iterator needs to consider the batch sequence number, and only the non-batch iterators need to consider the non-batch sequence numbers.
Additionally, there’s some room for optimizing the pathological cases in both memtable and batch skiplists by annotating skiplist nodes with the highest sequence number of a key reachable through a node link.
Motivated by analyzing cpu profiles from the BenchmarkIntentRangeResolution benchmark.
Jira issue: PEBBLE-199
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.