Parts cut where the questions are

A file written once for the queries after answered a sequence of selection queries against a file of 4,194,304 keys, charging every block of 1,024 words read or written. The first query’s counting pass sorts every key into one of thousands of pieces. Keeping those counts saved each later query a read of the whole file. Writing the file out as parts, so that a later query reads only its own part, saved much more. A pass that can count thousands of pieces, though, can write only as many parts as it has block buffers: seven, at 8,192 words of memory. Seven parts balanced by the keys paid for themselves by the second query.

Its closing section noticed what the balance ignored. The queries were placed without regard to where the keys were, so dividing the keys evenly was the right target for that workload. A real sequence of selections is rarely like that. A monitoring system asks for the 99th and 99.9th percentiles of a latency file over and over, and almost never for the 30th. A partition that gave the top percent of the keys parts of their own would make every high-percentile query read a few hundredths of the file rather than a seventh. The section proposed three partitions, each written after a stated number of queries. One is balanced by keys. One is balanced by the queries seen so far, each part serving an equal share of them. The third is a mixture, cut so that each part’s size times its share of queries is equal. It predicted the mixture would win by a factor near the ratio of query concentration to key concentration, and that a partition fitted to old queries could lose to the keys’ if the workload moved.

A workload with a hot band #

The file is the earlier page’s uniform file, and a heavy-tailed (Pareto) file of the same size. What a second pass buys found that a selection’s state falls as a power of the passes it may make, and here every selection makes one or two passes over a part, so its cost is set by the part’s size. A query asks for a rank. With probability 0.9 the rank is drawn uniformly from the top 2% of ranks, and otherwise uniformly from all of them. The first query is the median, as before, and its counting passes give the histogram the cuts are chosen from. A rule sees the next fifty queries, writes its seven parts, and is then charged for sixty more, each answered by the earlier page’s exact selection within its own part. A part no larger than the memory is read once, and a larger one needs two passes over it. Every rule cuts at the boundaries of the first query’s histogram. A piece’s share of queries is its count of past queries, plus one pseudo-query spread over the file in proportion to the keys, so no piece is ever taken as certain never to be asked about.

The three rules cut the same file very differently. Balanced by keys, each part holds 600,000 keys and the hot band sits inside the top part. Balanced by past queries, six of the seven parts are spent inside the hot band, 5,000 to 25,000 keys each, because that is where 90% of the queries fell. The seventh holds the other 98% of the file, 4.1 million keys. The mixture puts two parts over the band, 45,000 and 37,000 keys, and divides the rest of the file into five parts of about a million.

Why equal shares of queries buy nothing #

Parts balanced by past queries cost a later query about what parts balanced by keys cost: 1,095 transfers against 1,170 after fifty queries, and between 788 and 1,630 as the history grows from five queries to eighty. The proposal’s second rule looks like the obvious one, and there is a short reason it cannot work on average. A query costs about the size of the part it lands in. If every part holds an equal share $1/k$ of the queries, the expected cost is the sum over parts of $1/k$ times that part’s size, which is the file’s size over $k$ — exactly what parts of equal size cost. Equal query shares move the parts but not the average. On this workload they make it worse in practice: the one query in ten that is not hot lands in the 4.1-million-key part and pays about 8,000 transfers. Which history the rule happened to see decides how many do.

The right rule falls out of the same arithmetic. Let $q(r)$ be the density of queries over the ranks, and let a part at rank $r$ have length $\ell(r)$. A query at $r$ costs $\ell(r)$, and $k$ parts means the part lengths must cover the file, $\int dr/\ell(r) = k$. Minimising $\int q\,\ell\,dr$ under that constraint gives $q\,\ell^2$ constant, so $\ell \propto 1/\sqrt{q}$. A part’s size times its share of queries is $\ell \cdot q\ell = q\ell^2$, so the proposal’s third rule, equal products, is the optimum. Its cost relative to parts of equal size is $(\int \sqrt{q}\,dr)^2$ for ranks scaled to $[0, 1]$, which Cauchy–Schwarz keeps at most one.

The square-root law, measured #

With 90% of queries in the top 2% of ranks, the mixture costs 0.25 of what parts balanced by keys cost, against 0.20 predicted by the square-root law. Across concentrations from half the queries hot to 99%, the measured ratio follows the prediction from above, never more than 31% over it. It is from above for three reasons. The law assumes as many parts as it likes, placed anywhere, and the file gets seven, cut at the first query’s piece boundaries. The cost of a part is not quite its size: a part larger than the memory needs two passes. And the rule sees fifty queries, not the density.

The prediction the section made was a factor near the ratio of query concentration to key concentration. With 90% of the queries on 2% of the keys that ratio is 45, and the measured factor is 4. The square root is the reason. The hot band’s query density is 451 times the cold region’s, and the law gives it parts $\sqrt{451}$, about 21 times, shorter — the measured cut has about 40,000 keys a hot part against 800,000 a cold one. Making the hot parts shorter lengthens the cold ones, and the cold queries pay for that length; the optimum balances the two at the square root, and the cost follows the parts’ sizes rather than the density’s ratio.

Nine cheap queries paid for by a tenth #

Every fitted rule is a trade, and the plate shows it query by query: the mixture’s hot queries cost 149 transfers and its cold ones 1,554, against 1,170 and 1,171 for parts balanced by keys. Nine queries in ten save about a thousand transfers each. The tenth pays about four hundred more. The optimum is where one more key moved from a cold part into a hot one would cost the cold queries exactly what it saves the hot ones, and that is the condition $q\ell^2$ constant says in words. The query-balanced rule goes much further along the same trade. Its hot queries are cheap, 324 on average, and would be cheaper still but for the ones that fall just below its first cut. Its cold queries cost 8,034, seven times the key partition’s, and at one query in ten they carry most of its bill.

The same shape appears wherever a cost is spent to favour the common case. The optimal code that is beaten measured Huffman’s code giving a symbol seen 99 times in a hundred a codeword of one bit and paying for it in the rare symbols’ lengths. The code-length rule there is the logarithm of the probability and here it is the square root of the density, because a codeword’s cost is its length while a part’s cost is its size, and a part’s size is shared by every query that lands in it. The partition cannot give each query its own part; it can only decide how many queries share each one.

An estimate is a reweighting found that a search guided by an estimate is the same search on a reweighted graph, and a partition fitted to queries is a reweighting of the same kind. The file is unchanged, and what changes is which keys are cheap to reach. The query-balanced rule reweights so hard that the unfavoured tenth of the queries becomes the whole cost. The product rule reweights exactly as far as the favoured nine can pay for.

How much history the rule needs #

Five past queries are enough for the mixture: it costs 292 transfers a query after five, 267 after twenty and 298 after eighty. The product rule is forgiving because it needs only the rough shape of the query density. Four or five hot queries out of five say where the band is, and the pseudo-query spread over the keys keeps the cold region from being written as one enormous part. On the heavy-tailed file the key-balanced parts are uneven, from 512,000 keys to 726,000, because every rule cuts at the boundaries of the first query’s histogram. On a heavy tail that histogram is equal-width pieces refined only around the median, so a part cannot end just anywhere. The key partition costs 1,615 transfers a query there, and the mixture 192 to 233. The saving is larger on the file where the keys are least even, because the hot band sits in the part of the file the histogram resolves finely and the cold parts absorb the unevenness. The pass that was never a parameter turned a restriction into a dial; the histogram’s resolution is a dial of the same kind, and a finer first pass would let every rule cut closer to where it wants.

The query-balanced rule does not settle as its history grows. Its cost moves between 740 and 1,630 depending on how many of the cold queries it saw. It divides the hot band into six parts either way, and the one part left for everything else is always most of the file. The pass that runs the other way found that the order a pass reads in decides what it costs. Here the choice that decides the cost is the one part the cold queries fall into, and the query-balanced rule leaves them almost nothing.

When the questions move #

Moved from the 99th percentile to the 98.5th, the band still costs the fitted parts 729 transfers a query, less than the keys’ 1,170. Moved to the 97.5th, it costs 1,475, and from the 95th down it costs 1,909. The fitted parts lose their lead after a move of a percentile and a half, less than the band’s own width of two points. That is the risk the section named, and its size follows from the same law. The mixture made its cold parts about a million keys each so that its hot parts could be small. A band that moves out of the hot parts lands in a cold part up to 1.7 times as large as a key-balanced one, and pays in proportion. The keys’ partition does not care where the band goes: every part is the same size, so every query costs the same, 1,170 transfers whether the band sits at the 99th percentile or the 50th. Its indifference is what it buys with the four-fold saving it gives up.

The parts balanced by past queries fare far worse. Their cold part is the rest of the file, and the moved band lands in it at 8,034 transfers a query, nearly seven times the keys’ partition. A partition’s exposure to a moving workload is the size of the part the moved questions land in, and a rule that fits the past more closely leaves less room for anything else.

So the saving has a shelf life, and it can be measured before it expires. How long a reweighting stays true found a preparation paid back in under three queries and asked how long the workload it was fitted to lasts; here the preparation is the same for every rule, and what varies is how far the workload can move before the rule’s choice of part sizes is wrong. A system that keeps its first query’s counts can also keep a count of where recent queries fall. Once more than a stated share of them land in cold parts — a share the square-root law can set, since it prices a query in each part — the partition should be cut again.

Where the measurements come from #

One file size, one memory. Every number is for 2^22 keys, blocks of 1,024 words and 8,192 words of memory, so seven parts. More memory means more parts. The square-root law’s continuous optimum is approached as the parts get finer, so it predicts the mixture gains most from that; the prediction was not measured.

One shape of workload. Queries are a hot band plus a uniform remainder. A workload with two separate hot spots — the 99th and the 50th percentile, say — would give the mixture short parts at both, and the square-root law still applies to its density. A workload of a single repeated rank has a density concentrated at a point, where the law says a part of length zero. What that really asks for is a cache of the answer, not a partition.

Sixty later queries a setting. Each cost is the mean over sixty later queries, answered exactly and charged exactly. The spread of that mean is largest for the query-balanced rule, whose cold queries each cost thousands of transfers, and that spread is part of the finding rather than noise in it.

The writing is the same for every rule. Every partition costs one read of the file and one write of it, 8,192 transfers, whichever rule cut it. What a pass costs when it is a file found that a write of the surviving interval could make a later pass nearly free. Here every rule pays the same write, and they differ only in what later queries cost.

Still open: a partition that recuts itself #

The fitted parts lost their advantage after a move of a percentile and a half, and the law that set them can say when that has happened. Each query’s cost is the size of its part, and the expected cost under the counted density is known. A running count of where recent queries fall gives a second density, and it costs almost nothing to keep: a counter for each piece of the first query’s histogram, which the system already holds to find each query’s part, decayed so that old queries fade. When the partition’s cost under the recent density exceeds what a recut would cost under it by more than the price of a rewrite, the partition should be recut.

The measurement that follows drives a drifting workload, its band moving a tenth of a percentile every hundred queries. It compares three policies: never recut, recut every $N$ queries, and recut when the square-root law says the saving pays for the rewrite. The prediction is that the law-triggered recut stays within 20% of the best fixed interval for every drift speed, and that the fixed interval must be tuned to the speed to do as well. It could fail on a workload that jumps rather than drifts. There a recut is triggered by a band that has already left, and a partition fitted to the recent density fits a place the queries are no longer asking about.