cockroachdb / cockroachdb/pebble
perf: optimize {Lower,Upper}Bound handling in the memtable
- 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.