cockroachdb / cockroachdb/pebble

db: SeekPrefixGE lazy positioning, or GetPrefix

Open
#2,002 7 comments 0 reactions 0 assignees View on GitHub
A-storage C-enhancement T-storage
Dominant language
Go
Stars
6k
Forks
584
Avg merge
16h 35m
Merged PRs (30d)
5

Description

I have not thought through the design space here in detail, but it seems possible to use MVCC metadata about sstables (eg, the computed block properties) to avoid reading files that contain older versions of a key during a SeekPrefixGE. The goal would be to reduce block reads during MVCCGets, making MVCCGets performance profile more similar to a pebble Get.

A design, just to serve as an illustrative example:
* the sstable iterator SeekPrefixGE returns a synthetic `@`key if the bloom filter indicates the file may contain the key
* the merging iterator is updated to skip past these synthetic keys (much like it does today for range tombstones)
* nexting a sstable iterator last positioned by SeekPrefixGE actually performs the seek

if we elevated MVCC timestamps into the `*fileMetadata`, it seems like we could even avoid some of the bloom filter reads and table loads.

Somewhat related to #2182.

Jira issue: PEBBLE-142

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by tracing SeekPrefixGE through the sstable iterator and merging iterator, then review how MVCCGets use them and how range tombstones are skipped. Examine fileMetadata and the related discussion in #2182; done requires an agreed design and evidence that unnecessary block reads or table loads are reduced without changing iterator behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
go
Domain
databases, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.