When it does not fit

A level priced on its own sample

A levelled store chose between two divisions of its filter memory by pricing both on a sample of queries, and still divided by the size rule's shape. The proposal was to descend from the floored division instead: price each level alone on the sample at the settings either side of what it has, and move a grid step of bits from the level that saves least to the one that saves most, until no move helps. At three quarters of a bit and one bit a key the descent reaches the fitted division on all three stores in at most two moves, within a third of a point. At half a bit it does not move at all on most of the fill, as the risk named: no single step pays, because the fitted division's trade is the largest level's half bit given up for many steps on the smallest, and a grid step is not a unit of bits. Moves priced in bits instead of grid places close half a bit on two stores of three — but they price up to 60% of the filters a full search builds, and the prediction was under a quarter.

A levelled store keeps its keys in levels of growing size, each with a range filter, and a range query that a level’s filter rules out costs that level nothing to read. The filters share a budget of bits a key, which one bit a key, divided first split between levels. A division chosen before the queries arrive found the best split by searching every assignment of bits to levels against the store’s own sample of queries, and every essay since has tried to reach that fitted division with something cheaper. The size rule of the sizes a store passes through gives each level a base number of bits plus a slope times how many factors of four smaller it is than the largest, every setting snapped to a grid of nought, a half, one, two, three, four, six, eight, twelve and sixteen bits a key; a floor under every level gave every level at least half a bit, and brought the rule within five points of the fitted division from one bit a key up.

Half a bit stayed hard: a span the queries do not see and a level scaled by the queries it meets found the shuffled and clustered stores wanting different divisions there. A choice the fences cannot make found that a switch between the floored division and a gentler unfloored one, read off the levels’ fences, failed on a store filled two clusters at a time, while pricing both divisions on the sample of queries and taking the cheaper was within 3.6 points of the fitted division on every store at both budgets measured. The sample did what the fences could not. But it was used only to choose between two shapes of the same rule.

That essay’s closing section proposed letting the sample do more at almost no cost. Start from the floored division; price each level alone on the sample at the grid settings either side of what it has; move a step of bits from the level whose filter saves least to the level whose filter saves most; repeat until no move helps. A descent from the rule the store already has, not a search from nothing. The prediction: from half a bit, three quarters and one bit a key on all three stores, the descent ends within two points of the fitted division everywhere, in at most four moves, building fewer than a quarter of the filters the full search builds. The risk: at half a bit, where the floored division and the fitted one differ on every level at once, a descent of single steps can stall at an assignment where no one move helps and two together would.

Moves the sample can price

A move takes one level down a grid step and another up a step, or takes one level up a step if the budget has room; the descent tries every such move, prices each on the sample — the store’s own choosing seed of queries, the one the fitted division is searched on — and takes the one that lowers the sample’s cost most, stopping when none lowers it. Pricing a level at a setting means building its filter at that many bits a key and running the sample against it, so the descent’s cost is the number of distinct level-and-setting pairs it prices. The full search prices every level at every setting: thirty filters for a store of three levels, forty for four.

Everything else is the earlier essays’. Three stores — filled in shuffled order, two clusters at a time and one cluster at a time — each measured at six points of its fill, from an eighth to the whole; every division charged on a second seed of queries, never the one it was chosen on; capture measured as the share of avoidable reads avoided, between no filters and a perfect one. The fitted division is the exhaustive search’s best on the choosing seed.

The hero plate is the whole result in one table, the worst gap over the fill on every store at every budget. At three quarters of a bit and one bit a key the descent by single steps reaches the fitted division, within 0.3 points everywhere, in at most two moves. At half a bit it stalls: 33.9, 15.9 and 9.1 points behind on the shuffled, paired and clustered stores, almost exactly where the floored division started. A descent whose moves are priced in bits rather than grid places closes half a bit on the shuffled and clustered stores and leaves 12.4 points at one checkpoint of the paired one.

A store that never moves

On the shuffled store at half a bit, single steps leave the floored division where it is or nearly — 3, 0, 0, 1, 3, 0 moves at the six points of the fill — and trail the fitted division by up to 33.9 points; steps priced in bits follow it at every point, in 2, 1, 4, 5, 5, 3 movesThe shuffled store at half a bit a key, the share of avoidable reads avoided through the fill, charged on the second seed: ⅛: fitted 40.5 (3/1/0), floored 21.7 (0.5/0.5/0.5), single steps 35.7 (3/0/0.5, 3 moves), priced in bits 40.5 (3/1/0, 2 moves); ¼: fitted 54.7 (8/0), floored 38.4 (0.5/0.5), single steps 38.4 (0.5/0.5, 0 moves), priced in bits 54.7 (8/0, 1 moves); ⅜: fitted 65.2 (16/2/0), floored 33.0 (0.5/0.5/0.5), single steps 33.0 (0.5/0.5/0.5, 0 moves), priced in bits 65.2 (16/2/0, 4 moves); ½: fitted 61.1 (8/4/0.5/0), floored 34.7 (0.5/0.5/0.5/0.5), single steps 35.2 (1/0/0.5/0.5, 1 moves), priced in bits 61.1 (8/4/0.5/0, 5 moves); ¾: fitted 68.0 (8/4/2/0), floored 33.2 (0.5/0.5/0.5/0.5), single steps 47.6 (3/0/0.5/0.5, 3 moves), priced in bits 68.0 (8/4/2/0, 5 moves); full: fitted 71.5 (16/6/0), floored 37.6 (0.5/0.5/0.5), single steps 37.6 (0.5/0.5/0.5, 0 moves), priced in bits 71.5 (16/6/0, 3 moves).0.2000.4000.6000.800share of the fillshare of avoidable reads avoided⅛¼⅜½¾fullfitted divisionsteps priced in bitsfloored startsingle stepsshuffled, half a bit3 points where no single step helped
Fig. 1 The shuffled store at half a bit a key through the fill: the fitted division, the floored start, the descent by single steps and the descent by steps priced in bits. Single steps take 3, 0, 0, 1, 3 and 0 moves at the six points and trail by up to 33.9 points; steps priced in bits follow the fitted division at every point.

On the shuffled store at half a bit, single steps leave the floored division where it is or nearly — 3, 0, 0, 1, 3 and 0 moves at the six points of the fill — and trail the fitted division by up to 33.9 points; steps priced in bits follow it at every point, in two to five moves. This is the store the floored division always served worst at half a bit: its levels all meet about the same queries, so a floor that gives the largest level the same half bit as the smallest spends most of the budget where it saves least. The fitted division leaves the largest level bare and gives the smallest ones many bits. A descent was meant to walk from the one to the other.

At three of the six points it cannot take a single step. At the others it takes one to three moves and stops at an assignment no better than the floored one by more than a few points. Its stalls are the named risk exactly: every move the sample can price is worse than staying, and the assignment the store needs is several moves away.

The moves priced in bits reach it, from two moves at an eighth of the fill to five at three quarters. Each such move takes a level down by up to three grid steps and spends everything that frees, with whatever the budget has spare, raising one other level as far as it will go. It is a move about bits, and the trade the store needs is a trade of bits.

What a step cannot buy

What the descent cannot reach at half a bit: on the full shuffled store the floored division gives every level 0.5 bits a key, the fitted division gives 16, 6, 0 from the smallest level to the largest, single steps end at 0.5, 0.5, 0.5, and steps priced in bits end at 16, 6, 0Bits a key given to each level, smallest first, on the shuffled store at full of the fill and half a bit a key: floored start 0.5, 0.5, 0.5; single steps 0.5, 0.5, 0.5; priced in bits 16, 6, 0; fitted division 16, 6, 0. Grid of settings: 0, ½, 1, 2, 3, 4, 6, 8, 12, 16.floored startsingle stepspriced in bitsfitted divisionlevel 10.50.51616level 20.50.566level 30.50.500shuffled, full, half a bitbits a key, smallest level first
Fig. 2 Bits a key given to each level of the full shuffled store at half a bit, smallest level first: the floored start gives 0.5, 0.5 and 0.5; the fitted division 16, 6 and 0; single steps end at 0.5, 0.5 and 0.5; steps priced in bits end at 16, 6 and 0.

On the full shuffled store at half a bit the floored division gives every level half a bit a key, the fitted division gives 16, 6 and 0 bits from the smallest level to the largest, single steps end where they began, and steps priced in bits end at the fitted division exactly. The plate shows why one step is the wrong unit. The fitted division’s trade is to remove the largest level’s filter — its half bit a key, over most of the store’s keys — and spend those bits on the two smaller levels, which hold 61,440 and 4,096 keys beside its 983,040 — a sixteenth of its size and a 240th. Half a bit a key over the largest level is eight bits a key over a level a sixteenth of the size.

A grid step moves a level to the next setting on the grid, and the grid’s steps are unequal: half a bit from nought to a half, then a half, then whole bits, then two, then four. Lowering the largest level by its one step frees half a bit a key on the largest level; raising the smallest by one step costs half a bit a key on the smallest. The move fits, and it leaves almost all of the freed bits unspent. Spending them takes the smallest level up eight grid steps and the middle one up five, thirteen moves, every one of which the sample prices alone.

That is why the descent by single steps reaches the fitted division at three quarters of a bit and one bit and not at half. At the larger budgets the floored division is close to the fitted one already — the earlier essays found it within five points from one bit — and the moves that remain are one step each. At half a bit the gap is a reallocation across the whole store.

Every move from the floor

Why single steps stall at half a bit: from the floored division on the full shuffled store, 3 single moves fit the budget and every one makes the sample's cost higher, by 1% to 5%; the other 6 do not fit, since a level can be raised a step only by lowering one at least as large — and the fitted division's trade, the largest level's half bit spent on many steps of the smaller levels, is many moves at once, not oneEvery move of one grid step up on one level, alone or paired with one step down on another, from the floored division (0.5/0.5/0.5) on the shuffled store at full of the fill and half a bit a key, level sizes 4096, 61440, 983040: level 1 up: over budget; level 2 down, level 1 up: 0.6% on the sample; level 3 down, level 1 up: 4.9% on the sample; level 2 up: over budget; level 1 down, level 2 up: over budget; level 3 down, level 2 up: 5.0% on the sample; level 3 up: over budget; level 1 down, level 3 up: over budget; level 2 down, level 3 up: over budget.change in the sample's cost, per centlevel 1 upover budgetlevel 2 down, level 1 up0.6%level 3 down, level 1 up4.9%level 2 upover budgetlevel 1 down, level 2 upover budgetlevel 3 down, level 2 up5.0%level 3 upover budgetlevel 1 down, level 3 upover budgetlevel 2 down, level 3 upover budgetshuffled, full, half a bitsingle moves
Fig. 3 Every single move from the floored division on the full shuffled store at half a bit — one level up a grid step, alone or paired with another down a step — and the change it makes to the sample’s cost. Three fit the budget and all three raise the cost; six do not fit.

From the floored division on the full shuffled store, three single moves fit the budget and every one makes the sample’s cost higher, by 1% to 5%; the other six do not fit, since a level can be raised a step only by lowering one at least as large — and the fitted division’s trade, the largest level’s half bit spent on many steps of the smaller levels, is many moves at once, not one. The plate is the stall, seen from the inside. The three moves that fit each take half a bit from a larger level and give it to a smaller one, and each raises the cost because the smaller level, given one more grid step, saves less than the larger level loses by going bare. Only after several such steps on the smaller level does the trade pay, and the descent never takes the first.

The proposal’s own diagnosis named this — “no one move helps and two together would” — and a descent that tries pairs of moves fails here too. Two single steps free half a bit on the largest level and spend it on two steps of the smaller ones; the sample still says no, because the trade needs thirteen. The useful move is not two steps but one move whose size is set by the bits it frees, which is what the second descent does.

The descent priced in bits is not a search. It still moves from where it is, still prices each move on the sample, and still stops when no move helps; it prices more filters because each of its moves prices a level at a distant setting. At half a bit on the paired store it stalls at the middle of the fill, where the fitted division is three, three, one and nought bits on four levels and the floored start is within a single move’s reach of nothing better.

The store filled two clusters at a time

On the two clusters at a time store at half a bit, single steps leave the floored division where it is or nearly — 0, 0, 0, 0, 0, 0 moves at the six points of the fill — and trail the fitted division by up to 15.9 points; steps priced in bits follow it except at ½, in 2, 1, 2, 0, 3, 2 movesThe two clusters at a time store at half a bit a key, the share of avoidable reads avoided through the fill, charged on the second seed: ⅛: fitted 55.3 (3/1/0), floored 56.1 (0.5/0.5/0.5), single steps 56.1 (0.5/0.5/0.5, 0 moves), priced in bits 55.3 (3/1/0, 2 moves); ¼: fitted 63.4 (8/0), floored 66.1 (0.5/0.5), single steps 66.1 (0.5/0.5, 0 moves), priced in bits 63.4 (8/0, 1 moves); ⅜: fitted 75.2 (12/2/0), floored 65.4 (0.5/0.5/0.5), single steps 65.4 (0.5/0.5/0.5, 0 moves), priced in bits 75.2 (12/2/0, 2 moves); ½: fitted 78.2 (3/3/1/0), floored 65.8 (0.5/0.5/0.5/0.5), single steps 65.8 (0.5/0.5/0.5/0.5, 0 moves), priced in bits 65.8 (0.5/0.5/0.5/0.5, 0 moves); ¾: fitted 83.4 (12/3/2/0), floored 67.6 (0.5/0.5/0.5/0.5), single steps 67.6 (0.5/0.5/0.5/0.5, 0 moves), priced in bits 83.4 (12/3/2/0, 3 moves); full: fitted 78.9 (12/4/0), floored 69.4 (0.5/0.5/0.5), single steps 69.4 (0.5/0.5/0.5, 0 moves), priced in bits 78.9 (12/6/0, 2 moves).0.5000.6000.7000.8000.900share of the fillshare of avoidable reads avoided⅛¼⅜½¾fullfitted divisionsteps priced in bitsfloored startsingle stepstwo clusters at a time, half a bit4 points where no single step helped
Fig. 4 The store filled two clusters at a time at half a bit through the fill: the fitted division, the floored start, single steps and steps priced in bits. Single steps take no move at any point; steps priced in bits follow the fitted division except at half the fill, 12.4 points behind.

On the store filled two clusters at a time at half a bit, single steps take no move at any of the six points and trail the fitted division by up to 15.9 points; steps priced in bits follow it except at half the fill, where they take no move either and are 12.4 points behind. This is the store the reach-ratio switch failed on, and the plate shows the descent meeting it from the other side. The floored division is the right shape at some points of this store’s fill and the wrong one at others; where it is wrong, the fitted division wants, as on the shuffled store, bits moved from the largest level to the smaller ones.

At the middle of the fill the store has four levels and the fitted division gives them 3, 3, 1 and 0 bits a key. That is a reallocation not from one level to one other but from the largest to three, and a move that spends what one level frees on one other level finds nothing that pays: each single destination, raised as far as the freed bits allow, is worse than leaving the bits where they were. The descent priced in bits stalls for the same reason single steps did, one level of structure up.

At two of the six points the floored division charged on the second seed beats the fitted division, by 0.8 and 2.8 points: the fitted division was searched on the choosing seed and overfits it there. A descent that stays at the floor loses nothing at those points, which is why the worst gap, not the mean, is the plate’s measure.

The filters a descent prices

The descent prices fewer filters than the search, but not a quarter of them: single steps price at most 25% to 33% of what the full search builds, because a store has only three or four levels and ten settings for each, and a descent prices each level at its own setting and its neighbours, three of the ten; steps priced in bits price up to 60%The largest share over the fill of the full search's filters — every level at every grid setting — that each descent priced on the sample: shuffled, 0.5: single steps 33%, priced in bits 60%; shuffled, 0.75: single steps 27%, priced in bits 48%; shuffled, 1: single steps 30%, priced in bits 55%; two clusters at a time, 0.5: single steps 25%, priced in bits 60%; two clusters at a time, 0.75: single steps 33%, priced in bits 53%; two clusters at a time, 1: single steps 30%, priced in bits 57%; one cluster at a time, 0.5: single steps 25%, priced in bits 57%; one cluster at a time, 0.75: single steps 33%, priced in bits 53%; one cluster at a time, 1: single steps 30%, priced in bits 55%.a quartersingle stepssteps priced in bitsshuffled, 0.533% · 60%shuffled, 0.7527% · 48%shuffled, 130% · 55%two clusters at a time, 0.525% · 60%two clusters at a time, 0.7533% · 53%two clusters at a time, 130% · 57%one cluster at a time, 0.525% · 57%one cluster at a time, 0.7533% · 53%one cluster at a time, 130% · 55%worst over the fillshare of filters priced
Fig. 5 The largest share over the fill of the full search’s filters — every level at every setting — that each descent priced, on every store and budget. Single steps: 25% to 33%. Steps priced in bits: up to 60%.

The descent prices fewer filters than the search, but not under a quarter of them: single steps price at most 25% to 33% of what the full search builds, because a store has only three or four levels and ten settings for each, and a descent prices each level at its own setting and its neighbours, three of the ten; steps priced in bits price up to 60%. The proposal’s third number fails for a reason that has nothing to do with the descent and everything to do with the store’s size. A full search on three levels builds thirty filters; a descent that prices every level and its two neighbours has built nine before it moves, and each move adds a few more.

On a store of many levels the arithmetic would be the other way: a full search prices every level at every setting and searches every combination, and the combinations grow as the settings to the power of the levels, while a descent’s prices grow as the levels times a few. Here the combinations are a thousand or ten thousand and the search over them is cheap; what costs is building and running the filters, and of those the full search builds only thirty or forty.

That changes what the descent is for. It does not save filters on a store of this size. What it saves is the assumption that the sample can be searched exhaustively, and what it offers in exchange is a division reachable from the rule the store already writes, in two or three moves, at the budgets where the rule is close. At half a bit it offers nothing a two-way choice did not.

Where the sample’s price runs out

The question the proposal closed on was whether the division a store needs is reachable from the rule it already has by moves its own sample can price, or whether at the smallest budgets only a search finds it. At three quarters of a bit and one bit it is reachable, in two moves of a grid step each, and the earlier essays’ rule plus a short descent is the fitted division to a third of a point. At half a bit it is not reachable by grid steps, because the reallocation the store needs is large in bits and small in grid places on the large level, large in grid places on the small one; a move sized in bits reaches it on two of three stores.

A choice the fences cannot make priced two whole divisions on the sample and took the cheaper, within 3.6 points of the fitted division everywhere. That is still the best rule at half a bit that does not search: a descent from the floor reaches the gentle division’s neighbourhood only when its moves can carry many grid steps at once. The two methods agree on what the sample can do and differ on what it is asked. Asked to compare two complete assignments, it answers well; asked to judge one small step at a time from the wrong starting point, it can only say that every step is uphill.

What the measurement leaves out

Three stores, three budgets, six points. A store of more levels would make the full search’s combinations, not its filters, the cost, and would change which method is cheaper.

Greedy moves only. The descent always takes the best move; a descent that sometimes took a worse one, or started from the gentle division instead of the floored, was not measured.

One sample. The descent and the fitted division are both chosen on the choosing seed and charged on the other; a sample that drifted between the two was not measured.

Still open: a descent from the better of two

The descent reaches the fitted division wherever it starts close, and the two-way choice already finds, from the sample, which of two divisions is closer: the floored or the gentle. Start the descent from whichever the sample prefers. On the shuffled store at half a bit the gentle division leaves the largest level bare and gives the smaller ones most of the budget, so the trade the floored start could not make is already made, and what remains should be a step or two.

The measurement that follows prices the floored and the gentle divisions on the sample, starts the single-step descent from the cheaper, and charges the result as here, on all three stores at half a bit and three quarters. The prediction is that it ends within two points of the fitted division everywhere, in at most three moves and under a third of the full search’s filters, since the two-way choice was already within 3.6 points and the descent closes small gaps. It could fail on the paired store, where the fitted division at half the fill spreads the largest level’s bits over three smaller levels and neither starting division is the right shape. The question is whether the right start and short steps make up for moves that are too small, or whether the smallest budgets always need a move as large as the reallocation.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

The objects this essay names

Each one links to every other essay that touches it.

Bloom filterDesign parameterLsm treePer levelPredictionSpace accountingWorkload