A file written once for the queries after

What a pass costs when it is a file charged an exact selection for what a pass really costs on a file: a read of every block, through a buffer of at least one block. A file of 4,194,304 keys in blocks of 1,024 words is 4,096 blocks. The median took three passes at two blocks of memory and two at four, and nothing changed between four blocks and half the file. The selector is the narrowing kind what a second pass buys built for the streaming model, where the pass that was never a parameter first made the number of passes a dial. Its first pass cuts the key space into as many pieces as the memory holds counters for — 1,534 pieces at four blocks of memory — counts how many keys fall in each, and keeps the one piece holding the rank it wants. The next pass looks only inside that piece.

The page’s closing section noticed what that throws away. The counts from the first pass are a histogram of the whole file at the finest resolution the memory allows, and a second query for a different rank would compute exactly the same histogram in its own first pass. It proposed keeping the counts between queries. It went further and proposed writing the file out once, partitioned by piece, so that a later query reads only its own part. It asked how many queries it takes before writing the partition pays, and whether that number is set by the memory or by the workload. The prediction was that the partition pays by the second query on uniform keys and much later on a heavy tail, where equal-width pieces make one enormous part and many empty ones.

The measurement answers a sequence of queries four ways. The kept counts pay at once. The partition pays by the second or third query. Memory sets how much it saves, for a reason the proposal did not mention. And on the heavy tail it pays sooner and saves more, as long as the parts are not cut at equal widths.

Twenty-three queries, four ways #

The file is the earlier page’s: 2^22 uniform 32-bit keys, and a second file of the same size drawn from a Pareto distribution and rounded to integers. The workload is the median, then the 90th and 10th percentiles, then twenty ranks drawn at random: twenty-three exact selections. Every answer is checked against a sort of the whole file, and every block read or written is charged one transfer.

The four ways of answering:

• From nothing. Each query is a fresh selection, rereading the file every pass, as on the earlier page.
• The counts kept. The first query’s counts are kept, together with the finer counts its later passes made inside the piece it narrowed into. A later query finds the smallest counted interval holding its rank and starts there, as if the passes that made those counts had already run for it. Its remaining passes still read the whole file, since nothing about the file has changed.
• Parts of equal width. The first query’s first pass also writes the file out, split at equal widths of key space fixed before any key is read. A later query reads only the part holding its rank.
• Parts the counts balance. After the first query, one extra pass reads the file and writes it out in parts, cut at the counted boundaries that give each part as nearly as possible an equal share of the keys.

With the counts kept, every query after the first costs half of what it costs from nothing, and the saving starts at the second query. On uniform keys at 8,192 words a selection takes two passes: one to count and narrow, one to collect. Kept counts supply the first. Nothing has to be written, so there is nothing to recover: the policy is ahead from its second query and stays ahead.

Writing the file into parts costs the first query double: it reads the file once more, or writes it once while reading, and a write costs what a read costs. After that each later query reads only its part — a seventh of the file for the balanced parts, a sixth for the parts of equal width — and collects its answer in two passes over that part. The balanced parts overtake answering from nothing at the third query and finish at 10.3 reads of the file for twenty-three queries, against 46.0. They overtake the kept counts at the fourth.

That half confirms the prediction, and it is the less interesting half. The number of queries it takes to pay was never much in doubt. Writing the file once costs about two reads, and each later query then saves more than one read, so the partition is ahead by the third query whatever the details. What the prediction did not anticipate is what limits the saving.

A pass counts far finer than it writes #

The earlier page’s selector at 8,192 words counts the file into 3,582 pieces on its first pass. The proposal was to write the file out “partitioned by piece”. That would be 3,582 parts, and a later query would then read a 3,582nd of the file: one or two blocks.

A counting pass needs two words a piece; a writing pass needs a block of buffer for each part it writes. Keys arrive in no order, so a key for any part can come next, and each part being written must have a block in memory to collect its keys until a full block can go out. At 8,192 words and blocks of 1,024 that is seven parts beside the read buffer, against 3,582 pieces counted. Parts are 512 times coarser than pieces. The ratio is half the block size, and it holds at every memory.

So a partition written in one pass saves a later query about (M/B − 1) of its reading, and the memory, not the workload, sets it. Each doubling of memory doubles the parts. The number of queries the workload asks decides only whether the partition’s two reads are ever recovered, and on any workload of more than two or three queries they are.

This is the constraint every external sort is organised around. A distribution pass can split a file only as many ways as it has output buffers, which is why a sort of a large file takes several passes even when a single pass could count its keys at fine resolution. Sorting what will not fit measured the merging version of the same limit, where a merge pass can combine only as many runs as it has input buffers, and found the pass count set by the logarithm to the base M/B. The kept counts here know where 3,582 boundaries lie, and a single writing pass can use only six of them.

The mismatch also says why the kept counts and the parts are not rivals. The counts are fine and cheap and cannot move keys; the parts move keys and are coarse. A later query uses both: the parts to read a seventh of the file, and, inside that seventh, the pieces the counts already resolved, so that its first pass over the part can start narrower than the part’s own boundaries. That combination was not measured: a later query here starts from its part’s own boundaries and counts the part afresh. On uniform keys it would change nothing, since a part of 600,000 keys needs one counting pass either way. On the Pareto file a later query already reads its part only about 1.2 times on average, because its narrow band of values often narrows to a single value and stops.

What one later query costs as memory grows #

Once the file is in balanced parts, a later query costs 0.667 of a read of the file at four blocks of memory, 0.286 at eight, 0.134 at sixteen and 0.032 at sixty-four. Each part is a (M/B − 1)th of the file. The query reads it twice, once to count and once to collect, until the part fits in memory beside the buffer, when it reads it once. At 65,536 words a part is 66,000 keys, and a query collects its answer from it in two passes of 65 blocks each.

The kept counts save exactly one pass at every memory and never more. The first pass they replace is the pass whose resolution grows with memory. The passes that remain read the whole file however fine the first pass’s pieces were, because the file has not been rearranged. Counts say where the answer is and do not bring the keys any closer to it.

Parts of equal width save almost as much as balanced ones on uniform keys, because equal widths are nearly balanced when keys are uniform. They are cheaper to make. They are written during the first query’s first pass, which then counts with the memory the output buffers leave, so no extra read is needed. At 65,536 words that makes them the cheapest policy measured over twenty-three queries, 3.7 reads of the file against 4.7 for the balanced parts. At 4,096 words they fail for a different reason: two output buffers and a read buffer leave one block for counting, so the first pass writes only two parts, each needing two passes to search.

On a heavy tail the parts must follow the counts #

The earlier page’s Pareto file is the case the proposal expected to be slow. Its values are rounded Pareto draws, so almost every key lies in a narrow band near the bottom of the key space, with a long thin tail above.

Parts of equal width put the entire Pareto file into one part. A sixth of the key space is 179 million values wide, and every one of the file’s keys lies in the first sixth. A later query reads that one part, which is the whole file, and pays everything answering from nothing pays, plus the first query’s writing. Over the workload the equal-width partition costs 70.0 reads of the file against 69.0 for answering from nothing. It never pays.

The balanced parts are cut from the counts, and here the choice of counts matters. The first pass’s pieces are equal-width too, 3,582 of them, and on this file nearly every key lands in the first. Cut points chosen from the first pass alone could not divide anything. But the first query’s second pass counted inside that crowded first piece, and its 3,582 finer pieces say where the keys are. Merged, the two passes’ counts are a histogram fine where the keys are dense and coarse where they are not. Cut from that histogram, the seven parts hold between 12.2% and 17.3% of the file each. A seventh would be 14.3%, and the unevenness is the histogram’s resolution: a cut can fall only on a counted boundary.

On the Pareto file a fresh selection takes three passes rather than two, because its first pass learns almost nothing. So a later query saves more there, from any policy that avoids the first two passes. The balanced parts overtake answering from nothing at the second query, not the third, and twenty-three queries cost 9.2 reads of the file against 69.0. The kept counts cost 25.0: each later query starts from an interval the first query’s two passes already narrowed, and needs one pass to finish.

So the prediction’s second half is backwards. The heavy tail is where the partition pays soonest and saves most, because it is where the first pass of a fresh selection is most wasted. What fails on the heavy tail is only the equal-width partition, and the proposal’s worry — “one enormous piece and many empty ones” — is exactly right about that. Cutting the parts from the counts removes it, and the counts that do so are the ones the first query already paid for.

Where the pass that runs the other way comes in #

The pass that runs the other way measured a pass whose value depends on what comes after it, and the earlier page’s closing section guessed the partition would be another. It is, in a sharper form than guessed. A partition is worth nothing to the query that pays for it: the first query costs twice what it would alone. Its whole value is in the later queries, and how much it is worth is decided the moment it is written, by the memory available then. A query sequence that turns out to be one query long has wasted a read and a write of the file, and that is the only way the partition loses.

That makes the decision to write a partition like the decision the day a filter cannot grow priced for a rebuild. An investment of two reads of the file is repaid only if enough later work arrives. The difference is how small the threshold is: two or three queries, against a filter’s thousands of lookups. A selection on a file is expensive enough that almost any repeated use pays for rearranging the file.

The kept counts are the free version of the same idea. They cost no transfers at all, only the memory to hold them between queries: 7,164 words at 8,192 words of memory on uniform keys, the pass’s whole counter array, and twice that on the Pareto file, where a second pass counted too. They save one pass on every later query and never lose. A system that answers selections against a file and throws the first pass’s counts away is discarding a pass per query to free memory it will need again at the next query.

The arrangement is familiar from the other side. The index not worth reading priced an index against a scan and found the index pays only while the rows asked for are few. A partition is an index at the coarsest grain there is — M/B − 1 entries — and it pays for the opposite reason: a selection asks for one key, but finding it without an index takes whole passes over the file. Permuting is sorting here showed that on a file rearranging keys is as expensive as sorting them. The partition is the cheapest rearrangement that still helps, one pass, and it already earns its cost back by the third query.

What was measured and what was not #

One sequence of queries. Twenty-three ranks, three of them fixed and twenty random. A workload concentrated in one part of the key space — every query for a high percentile, say — would make the balanced parts less valuable than an uneven partition that splits the busy region finer. That is a partition fitted to the queries rather than to the keys, and it was not measured.

One writing pass. The partition is written once, as far as one pass can split the file. A second writing pass would split each part up to M/B − 1 ways again, which is how an external distribution sort proceeds, until each part fits in memory and a later query costs one read of one part. That takes about as many passes as the file has factors of M/B in it, and it is the limit this page’s policies approach.

Rounded Pareto keys and the one-value shortcut. The Pareto file’s values are rounded to integers, so many keys share a value, and a selection whose interval narrows to a single value stops without a collecting pass. At 65,536 words of memory the merged counts resolve so finely that every later query is answered from the counts alone, at no cost at all. That is real for this file and flatters every policy on it. Keys without repeated values would need a collecting pass in every case.

Transfers, not time. A write costs what a read costs here, as on the earlier page. On devices where writes cost more, or where a sequential read of a large part is cheaper per block than the scattered reads a selection makes, the thresholds move, and the order of the policies does not.

Still open: parts fitted to the queries rather than the keys #

Every partition here divides the keys evenly or at equal widths. The queries were placed without regard to either, so evenly divided keys were the right target. 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 1% of the keys three parts of their own, and the bottom 99% the other four, would make every high-percentile query read a few hundredths of the file rather than a seventh.

The counts can say where the keys are, and only the queries can say where the questions are. The measurement that follows answers a workload concentrated on a few high ranks. It compares three partitions written after a stated number of queries: balanced by keys, balanced by the queries seen so far (cut so each part serves an equal share of past queries), and a mixture, cut so each part’s size times its share of queries is equal. The prediction is that the mixture wins by a factor near the ratio of query concentration to key concentration. It should fail in one way: if the workload moves after the partition is written, a partition fitted to the old queries can be worse than one fitted to the keys, and the number to watch is how far the queries can drift before the fitted partition falls behind.