github-actions[bot]
commented
1 month ago We have marked this issue as stale because it has been inactive for 18 months. If this issue is still relevant, removing the stale label or adding a comment will keep it active. Otherwise, we'll close it in 10 days to keep the issue queue tidy. Thank you for your contribution to Pebble!
In a quiescent state, each level of the LSM has 10x more bytes than the previous level. As a result, higher levels tend to be sparser. When positioned over a key in L6, it's fairly likely that the next key is also within L6.
During a Next on the merging iterator, the heap root is nexted to the next key, and then the heap is fixed up. Consider the case where the next key is from the same level.
mergingIterHeap.fix(0)needs to determine whether or not it should swap the level at the heap root with either of its heap children. It first calls Less(left, right) to determine which child is lessor, and then calls Less again to compare the root with its children, resulting in two total key comparisons. If there's a string of keys all from the same level, the Less(left, right) comparison to determine which child is lessor is redundant.It seems like there should be some means of remembering the knowledge of which child is lessor, and reducing the key comparisons to 1 per Next during long strings of keys originating from the same level.
I'm not sure how best to make this optimization while keeping the code general and maintainable.
Jira issue: PEBBLE-161