The two parts the law was not given

Every cut the law moves found out why a partition recut by the square-root law cannot recut cheaply. A file of four million keys is kept in seven parts, cut so that each part’s share of the keys times its share of the selection queries is the same, and nine queries in ten fall in a band 2% of the ranks wide that moves. When the band moves, the law moves 98% of its cuts, because the parts on either side of the band share out the key space the band leaves, and a cut on the far side of the file has to move for a band moving on the near side. Charging a recut only for the parts it changed saved 2%. Recutting only the three parts around the band cost up to three times as much a query, because the law’s other cuts were then in the wrong places.

That essay’s closing section proposed the opposite of the law’s habit: a background that never moves. Cut the file once into seven parts balanced by keys. Inside whichever part holds the band, keep the band in a small part of its own, cut by the law over that part alone, and leave every other part untouched. A recut would rewrite one background part, a seventh of the file, and only when the band moved within it or out of it. The prediction was that this partition would recut several times as often as the law, for a seventh of the cost each time, and come within 10% of the law’s cost a query on slow drift. It could fail where the band straddles two background parts, since half its queries would then fall in a part that is a seventh of the file and not cut for them.

Seven by keys, and the band cut inside #

The setting is the earlier essays’ throughout, a model of the exact selection what a second pass buys began with, priced in blocks. The file holds ranks of 2²² keys in 4,096 pieces of 1,024, the resolution cuts are drawn at. A selection query costs one read of the part it falls in, or two reads for a part larger than half the 8,192 words of memory, the charge what a pass costs when it is a file measured for exact selection. Each stream is 20,000 queries, four streams a setting. Every hundred queries a design prices its current partition against the one it would cut from a density of recent queries decayed with a half-life of 250 queries, and recuts when the saving a query over that half-life pays for the parts the recut rewrites.

The proposed design keeps the background’s cuts fixed at every seventh of the file. Its candidate partition takes the background part carrying the most decayed density, cuts that part into three by the law over its own stretch, and leaves the others whole. If the band has moved into a different part, the recut merges the old part back and splits the new one, and pays for both.

The proposed design writes nine parts, and the law writes seven. That is in the proposal’s own words, seven background parts and a part of its own for the band, and it went unremarked because the eye is on the rewriting. A part costs a reader nothing to have, and in this cost model more parts means smaller parts and cheaper queries. The law was held to seven because seven parts is what one pass can write with eight blocks of memory, one buffer a part and one for input, as parts cut where the questions are set it up. The fixed background never writes nine in one pass. It writes seven when it is first laid down and three when it splits a part. So it lives within memory, and still ends up with two more parts than the law could ever hold. A file written once for the queries after met the same ceiling from the other side: a pass that distributes keys into parts needs a block of memory for each part it is filling, and the number of parts is the memory in blocks less one. A design that writes its parts a few at a time escapes that ceiling, and the escape is worth exactly what the extra parts are worth.

That difference is the first thing to measure, because it could be the whole result. Four more designs make the comparison fair: the law given nine parts; six background parts with the band’s part cut in four, also nine; five background parts with the band’s part in three, the law’s own seven; and four background parts with the band’s part in four, also seven.

The win is the two extra parts #

The fixed background beats the law’s seven parts at every drift speed, by 2% at the slowest and 18% at the fastest — and the law given the same nine parts beats the fixed background at every speed, by 20% at the slowest and 3% at the fastest. The proposal predicted the background would come within 10% of the law on slow drift. It came in under it, and the reason is not its stillness.

Held to the law’s seven parts, the fixed background loses everywhere. Five parts by keys with the band in three costs 414 transfers a query at the slowest drift against the law’s 339, and 704 at the fastest against 680. Four by keys with the band cut in four does better: 305 at the slowest drift, under the law, and within 3% of it at every other speed but one. At a drift of 0.05 it costs 407 against 366, because on those streams the band spends a fifth of the time across one of its cuts. That is the failure the proposal named, and the next sections measure it.

The fair pair at nine parts is the law against six parts by keys with the band in four, and they are tied. At the five drift speeds the background costs 264, 278, 329, 386 and 522 transfers a query, and the law 265, 280, 322, 393 and 537. Neither is ahead by more than 3%. So the proposal’s central claim survives in a corrected form. A partition can hold its background still and recut only around the band, at no cost a query on drift, if it cuts the band’s part as finely as the law cuts the band. Three pieces were not enough. The band’s own part was 116 transfers where the law’s was 68, and nine queries in ten pay it.

Where each design’s transfers go #

Every recut of seven parts by keys rewrites 14% of the file, against the law’s 98%, and it spends 5.6 transfers a query on rewriting against the law’s 25.9. The proposal’s arithmetic of a seventh a recut was right to the per cent: the share sits between 13% and 15% at every drift speed. The recuts were predicted to be several times as frequent. They are not: 87.5 against the law’s 63.5 at this speed, and at the slowest drift fewer, 19.5 against 35.3. A background recut happens when the band leaves the stretch its split was cut for, which on a slow drift is rarely, and a law recut whenever the decayed density has moved enough to pay for the whole file.

The nine-part pair shows the trade the stillness makes. The law spends 21.3 transfers a query rewriting and 300.5 answering; the background spends 8.9 rewriting and 320.0 answering. What the background saves by not moving its far cuts, it gives back on queries, because the far cuts are not where the law would put them. Its background parts are a sixth of the file each, 1,366 transfers a stray query, wherever the band is. The law’s are cut around the band’s position, a different size on each side of it. At this speed the two exchanges come out 2% in the law’s favour. At the fastest drift, rewriting is a larger share of the law’s cost and the background is 3% ahead; at the two slowest the designs are within a per cent of each other.

When a background cut runs through the band #

On a band that stays put, six parts by keys with the band in four cost 275 transfers a query on average against the nine-part law’s 282 — and at the five places where a background cut runs through the band they cost up to 785, nearly three times the law. The straddle the proposal feared is real, and on a still band it is sharp. When the band is centred on a cut, half its queries fall in one background part and half in the next. The design splits only the part with more of the density, so the other half of the band is answered from a whole background part of 1,366 transfers.

Away from the cuts the fixed background is cheaper than the law at all but two of the 44 centres, by a median of about thirty transfers a query. That says something about the law, not about stillness. The square-root rule balances the product of key share and query share; it is not the minimum of a cost model that charges a part one read below half the memory and two above it. A background cut by keys, with the band’s part split finely, happens to sit closer to that minimum when nothing straddles. The figure is what the earlier pages assumed when they called the law’s partition the floor. It is a good partition, and not the best one.

One drifting stream #

On one stream drifting at 0.1, the fixed background runs ten transfers a query under the law for thirty-five blocks, and then spends four blocks across a background cut at twice the law’s cost. Those four blocks are a tenth of the stream and nearly erase the background’s lead: over the whole stream it costs 299 against the law’s 282, on this seed. Averaged over four seeds and five speeds the two designs tie, and the averaging is hiding this shape: a design that is a little better most of the time and much worse for short stretches that arrive whenever the band crosses one of five fixed lines.

A partition that moved its background a little near the band would avoid the straddle. That is a step back toward the law, whose every cut moves, and every cut the law moves measured where that ends: holding small moves back kept a quarter of the file still and cost more a query.

Jumps #

When the band jumps instead of drifting, the nine-part law beats the six-part background at every rate, by 10% to 16%. A recut the law decides found the law at its best on jumps, beating every fixed recut interval, and against a fixed background it keeps that advantage. The proposal’s seven parts by keys does worse still, losing even to the law in seven parts once jumps come every 2,500 queries or less often.

Straddling does not explain this. A jump lands at a uniformly chosen rank, and the band then straddles a background cut in only 1% to 9% of the blocks. Something else is costing the background on every jump.

Three hundred queries to believe the band has moved #

After a jump, the nine-part law has re-shaped its partition within a hundred and fifty queries; the fixed background goes on answering the band from a whole background part, over a thousand transfers a query, for about three hundred. Once it moves, it is cheaper than the law, 235 transfers a query against 266 over the rest of the thousand. But at a jump every 2,500 queries, three hundred queries at four times the settled cost is a large share of the total.

The delay is in how the background chooses the part to split. It splits the part carrying the most decayed density, and after a jump the old part keeps the majority until a half-life of new queries has outweighed it. The arithmetic is short. With a half-life of 250 queries, $t$ queries after a jump the old band’s queries carry a weight of $2^{-t/250}$ of the density’s total and the new band’s carry the rest, so the two are equal at exactly $t = 250$. The density is read every hundred queries, so the new part first leads at a reading between 250 and 350 queries after the jump, and that is where the plate’s background drops. Only then does the split move. The half-life was chosen by a recut the law decides to keep the law within 7% of the best fixed interval on drift, and nothing about that choice was meant to set how quickly a single split changes hands. The law does not choose a part. It cuts the whole file from the mixed density, giving parts to the old band and the new one at once, and the new band gets a part of its own as soon as its queries pay for a rewrite. A design that splits one part can follow one band, and it follows the one that has been there longer.

What the counts depend on #

A cost model, not a run of selection. Each query is charged by its part’s size alone, the charge the earlier pages checked against exact selection at every part size used; no selection was run here. The step in that charge at half the memory is why more parts matter so much and why the law is not this model’s minimum.

Two more parts are free here and may not be elsewhere. A reader of the file pays nothing for holding nine parts rather than seven. A system that keeps each part’s metadata, or opens a file a part, would charge for them, and then the comparison at seven parts is the one that counts.

One band, four seeds. Every stream has one band 2% wide carrying 90% of its queries. A workload with two bands would ask the fixed background to split two parts, which it does not do.

One way of choosing the band’s part. The background splits the part with the most decayed density. Choosing instead by the saving a split would make, the rule the law uses for its whole partition, would change how quickly it follows a jump; the section after this one proposes exactly that and it was not run here.

Still open: the split that follows a jump at once #

The fixed background ties the nine-part law on drift and loses to it on jumps for one reason that can be named: it waits about three hundred queries, roughly one half-life, before it believes the band has moved to another part. Its rule asks which background part holds the most decayed density, and a majority is slow to change hands. The question could instead be whether a part has gathered enough recent density to pay for splitting it, asked of every part, and answered yes for the new part while the old one is still split.

The measurement that follows lets the background hold two split parts at once, the old band’s and the new one’s, at the same total of nine parts, by cutting each split part into fewer pieces while two are split. It recuts when a whole part’s density would pay for a split under the same rule the law uses, and merges a split part back when its density no longer pays for keeping it split. It runs on every jump rate and every drift speed. The prediction is that the cost after a jump falls to the law’s within a hundred and fifty queries, so that on jumps the background comes within 5% of the nine-part law, and that on drift it changes nothing, since a drifting band rarely needs two split parts. It could fail on the pieces. Two split parts in nine leave each band fewer pieces, and the band’s own part was the first thing this essay found too coarse at three. The question is whether a background can follow a jump as quickly as the law without giving back what holding still saved, or whether following quickly is exactly the law’s habit of moving every cut, under a different name.