Concept

Range query — where it appears

A request for every key between two bounds rather than for one key. A membership filter cannot answer it, because a range names no key to hash, so structures built for point lookups often make a range query pay their full cost.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Also named here as read amplification, sorted run — the same set of essays touches all of them, so they are one junction rather than several.

The read a filter has no key for

A Bloom filter on every run of a log-structured store turns a lookup for a missing key from a read of every level into a fraction of one — 0.72 transfers across eight levels at five bits a key, and 0.00027 at twenty. A range query over the same store reads nine transfers at five bits and nine at twenty, because a filter answers whether one named key is in a run and a range has no key to name.

applied · Transfer

The runs a range query can skip

A Bloom filter over key prefixes can tell a range query that a run holds nothing it wants, which a filter over keys cannot. On a four-level store of a million keys, a range expected to hold one key costs 4.76 transfers with no such filter and 2.41 with one built on 20-bit prefixes. The best length moves two bits for every tenfold longer range. By a hundred keys the most any range filter could save is a fifth of a transfer, because only the smallest level is ever empty. And the same memory spent on 20-bit prefixes makes a lookup for an absent key three times dearer.

applied · Transfer

Named alongside it

The objects these essays reach for when they reach for this one.

Block size Bloom filter Design parameter Lsm tree Read amplification Sorted run Space time trade Workload Block transfer Compaction False-positive Write amplification

All concepts