cockroachdb / cockroachdb/pebble

arenaskl: consider alternative TrySeekingUsingNext optimizations

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

Description

The arenaskl Iterator implementation implements the TrySeekUsingNext optimization through performing simple Nexts:

https://github.com/cockroachdb/pebble/blob/6c6fd7553fc59a1223ff0289f3c02164c23d442e/internal/arenaskl/iterator.go#L94-L115

If it doesn't find the sought key within 5 nexts, it abandons the work it's already done and starts anew. We could instead take advantage of the skiplist node structure and try advancing at levels above the base level but below the list height.

I'm imagining something like:
```
Initialize level = 0
for range 5 {
next := n.tower[level]
if key <= next.key {
return searchDescending(next, level, key)
}
n = next
if n.height > level+1 {
level++
}
}
```

Jira issue: PEBBLE-1197

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.