A level priced on its own sample
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 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
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
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 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 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 filter rebuilt with every write bloom filter · design parameter · lsm tree · per level · workload
- One length for the gaps and the clusters bloom filter · design parameter · lsm tree · per level
- The filter each run carries bloom filter · lsm tree · per level · space accounting
- The read a filter has no key for bloom filter · design parameter · lsm tree · workload
- The resolution a range filter can afford bloom filter · design parameter · lsm tree · per level
- The runs a range query can skip bloom filter · design parameter · lsm tree · workload
The objects this essay names
Each one links to every other essay that touches it.
Bloom filterDesign parameterLsm treePer levelPredictionSpace accountingWorkload