Skip to content

db: consider requiring prefix filtering within InternalIterator #2182

@jbowens

Description

@jbowens

This came up during #2178.

Today, SeekPrefixGE is not required to return a key that matches the provided prefix. Levels that can't cheaply (eg, bloom-filter check) determine whether a level contains a prefix behave like a SeekGE. This avoids the need to compare prefixes in all of the leaf iterators.

However, every leaf iterator that returns a key increases the work required to build the merging heap. In the case where only zero or one levels contain a key with the provided prefix, checking the prefix at the leaf iterators would result in n prefix checks. This is in contrast to the current 1 top-level prefix check + n key comparisons to build the heap. If all of the keys with the prefix reside in a single level, iteration over the prefix also benefits from the reduced heap size removing k log n comparisons, where k is the number of times the iterator is stepped.

In the common case where one levels contains relevant keys, the seek would only move the single prefix check into the leaf iterator and remove the log n key comparisons.

Metadata

Metadata

Type

No type

Projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions