-
Notifications
You must be signed in to change notification settings - Fork 555
db: optimize for reads without range keys #1605
Copy link
Copy link
Closed
Description
Range keys are intended to be rare, and in the CockroachDB use case of MVCC Delete Range especially rare. We should ensure that a read in a part of the key space NOT covered by range keys loads zero range key blocks. There is at least one TODO documenting this optimization, but I'll sketch out something larger here.
The new keyspan.Span type supports modeling spans without range keys as a valid Span with an empty Keys slice. These empty spans will be introduced by the range key level iterator (introduced in #1576). Imagine a SeekGE(k) that finds a file with bounds m-p. The span [k,m) contains no range keys within the level. The level iterator can return a Span{Start: k, End: m, Keys: nil}.
- The
internal/keyspan.LevelIterneeds to change to return these empty spans. - The
internal/keyspan.MergingItercurrently elides empty spans. That logic should be removed, allowing empty spans to be propagated up the iterator stack. - The DefragmentingIter defragments abutting, logically equivalent spans. Two empty spans are logically equivalent, so defragmentation will defragment empty spans. This is a problem, because defragmenting requires Next/Prev-ing adjacent spans until a nonequivalent span is encountered. The defragmenting iterator would trigger a block load at both the beginning and the end of the defragmented empty span. The defragmenting iterator should be adapted to avoid defragmenting empty spans.
Related to #1444
Reactions are currently unavailable
Metadata
Metadata
Assignees
Labels
No labels