cockroachdb / cockroachdb/pebble

perf: optimize {Lower,Upper}Bound handling in the memtable

Open
#98 7 comments 0 reactions 0 assignees View on GitHub
C-performance
Dominant language
Go
Stars
6k
Forks
584
Avg merge
16h 35m
Merged PRs (30d)
5

Description

The memtable currently checks the lower/upper bound on every iteration step. An alternative is to find the nodes which bound the lower and upper bound (using `SeekGE(lower)` and `SeekLT(upper)`) and then do pointer comparisons for the boundary checks. This will make the boundary checks a lot faster, but it does mean that we'll do an extra `Seek*` (we can do this lazily, but there will still be at least 1 extra seek). Note that the memtable can be inserted into concurrently with iteration, but those concurrent insertions are always for newer values and cannot affect the keys seen during an iteration.

@ajkr I was thinking about this after your comment on https://github.com/petermattis/pebble/pull/81#pullrequestreview-231332657. Thoughts?

Jira issue: PEBBLE-184

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.