Skip to content

db: optimize for reads without range keys #1605

@jbowens

Description

@jbowens

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.LevelIter needs to change to return these empty spans.
  • The internal/keyspan.MergingIter currently 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

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions