Every cut the law moves

A recut the law decides kept a file of four million keys as seven parts, cut so that each part’s share of the keys times its share of the selection queries was the same, the square-root law parts cut where the questions are had found. Nine queries in ten fell in a band 2% of the ranks wide, and the band moved. Every hundred queries the file priced its current cuts against the cuts the law would draw from a decayed count of recent queries, and recut when the saving a query, over the count’s half-life, paid for the rewrite. With a half-life of 250 queries it stayed within 7% of the best fixed recut interval on slow drift and beat every fixed interval on traffic that jumps.

Every recut was charged the whole file, a read and a write of all 4,096 blocks, 8,192 transfers. The essay’s closing section objected that on a slow drift most recuts move one cut: the band crosses a boundary, the law moves that boundary, and the five parts that did not change are rewritten anyway. It proposed charging a recut only for the parts whose boundaries change. It predicted that on slow drift such a recut would cost a tenth of a full one, that the law would then recut several times as often, and that the file would come within 5% of the 356 transfers a query a still band costs. It named the condition under which this would fail: if moving one cut changes the law’s best position for the others.

That condition is not an edge case. It is what the law does every time.

Charging only what changed #

The setting is the earlier essay’s, unchanged: ranks of 2²² keys in 4,096 pieces of 1,024, the resolution the cuts are drawn at; a selection query charged one read of its part, or two for a part larger than half the memory; 20,000 queries a stream; four streams a setting. The law prices its cuts every hundred queries against a density decayed with a half-life of 250 queries. The one change is the price of a recut. Charged for the changed parts, a recut costs two transfers for every block of a new part whose two boundaries are not exactly the boundaries of an old part. A recut that moves one cut changes the two parts on either side of it, and costs only their blocks. The law’s decision uses this price, so cheaper recuts are made more readily.

Two variants try to make recuts cheaper on purpose. Small moves held back draws the law’s cuts and then keeps any old cut that lies within a stated slack of a new one, 4, 16 or 64 pieces, so that the parts between kept cuts are left alone. Three parts around the band keeps every cut but those of the part the density loads most and one neighbour each side, and recuts those three parts by the law over their own stretch of the density.

The law moves everything #

At each recut the law moves 98% of its six cuts, a median of nineteen pieces, nineteen thousand ranks. The plate shows why. Three cuts stay close to the band, fencing it into two small parts, and they follow it as it drifts. The other three divide the rest of the file, and they drift too: the parts below the band grow as it moves up, and the parts above it shrink.

Two things move the background cuts, and either alone would move all of them. The first is the law itself. A part’s cost to a query is its size, and the law makes each part’s key share times its query share the same. Away from the band, the queries are the tenth spread evenly over the ranks, so a background part’s query share is proportional to its key share, and a law that knew the background exactly would make the background parts equal. When the band moves up by a percentile, the background below it gains a percentile and the background above it loses one, and equal parts on both sides means every one of them resizes. No cut away from the band is ever where it should be after the band has moved, because the band’s position decides how the background is shared.

The second is what the law reads. A density decayed with a half-life of 250 queries holds the weight of about 360, and a tenth of those are background, three dozen queries spread over four thousand pieces. A background cut falls wherever the cumulative count of those few dozen crosses its share, and the next pricing draws it again. On a band that does not move at all, the law’s cuts between one pricing and the next move a median of nineteen pieces, 95% of them, the same numbers as on a drift. The law rarely recuts a still band, three times in 20,000 queries, because the noise saves nothing worth a rewrite. When a drifting band does trigger a recut, the new background cuts are a fresh draw from the noise as well as a response to the band.

Smoothing the background removes the second cause and leaves the first. Giving the density a uniform floor worth 300 queries makes the background nearly flat in the law’s eyes, and at every drift speed 96% to 97% of the cuts still move at each recut. A floor worth thirty queries helps the law a little, 406.8 transfers a query at drift 0.1 against 416.8 and 328.7 at drift 0.02 against 339.1, and moves the cuts just as much.

The prediction pictured a band crossing one boundary at a time. The law has no fixed boundaries for the band to cross. Every boundary is a share of the space the band leaves.

Two per cent, not nine tenths #

Charged only for the parts it changes, the law costs 416.8 transfers a query at drift 0.1, against 416.0 charged for the whole file; at every drift speed the two are within 1%. A recut that moves 98% of the cuts changes nearly every part, and rewrites 98% of the file. The partial charge makes recuts 2% cheaper, the law makes one or two more of them a stream, and the total does not move.

The two variants that try to change fewer parts do change fewer, and pay for it in queries. Keeping cuts that move by sixteen pieces or less costs 438.7 transfers a query at drift 0.1, 5% more. Recutting only the three parts around the band costs 739.0, 78% more, and at drift 0.2 it costs 1,647, three times the law. The best fixed interval, recutting every 125 to 500 queries whatever happens, beats or ties all of them on drift.

What a recut rewrites #

Recutting only the three parts around the band still rewrites 61% of the file at each recut, because the band’s neighbours are the two largest parts. The law makes the band’s own parts tiny and gives the background the rest. A part next to the band is a background part, a fifth or a quarter of the file, and recutting it rewrites it whole. Moving 29% of the cuts rewrites 61% of the keys.

The local recut’s larger cost a query has the same cause as the law’s moving cuts. It recuts the band’s neighbourhood correctly, but every part it leaves alone was sized for where the band used to be. When the band drifts into a part the local recut has not touched, that part is large and hot, and the queries in it pay for its size until the band is far enough in for the local recut to reach it. The law’s partition is a single object whose pieces are sized against each other, and recutting a piece of it leaves the rest sized for a band that has gone.

Holding cuts still #

Letting a cut stay where it was when the law would move it by up to sixteen pieces lowers the share of the file a recut rewrites from 98% to 88% at drift 0.1, and raises the cost a query from 416.8 to 438.7. At sixty-four pieces the recut rewrites 75% of the file and the cost a query is 575.3. The cuts held back are the background cuts, which move a few dozen pieces each time the band moves a percentile. Held, they leave the background parts unequal, and the law’s saving comes from their being equal.

The slack also makes the law recut less often, 44 recuts a stream at sixteen pieces against 64, and the band’s own small parts follow it less closely. Every saving in the rewrite is paid for in queries, and at every slack measured the queries cost more than the rewrite saved. What a pass costs when it is a file charged a pass over a file by the blocks it moves, and here the unit is the same: a recut is cheap only if it moves few blocks, and the law’s best partition is one that moves most of them.

Jumps, the same #

On jumping traffic the partial charge changes the law’s cost by under half a per cent: 340.7 transfers a query against 342.3 with a jump every 5,000 queries, both below the best fixed interval’s 383.5. A jump moves the band anywhere, and every cut has to move. The prediction expected nothing here, and nothing is what the measurement finds. The local recut is worst on jumps of all, 549.7 at the same rate, since a band that jumps lands in a part the local recut has never touched and stays there until the next pricing finds it.

A refit priced against a cost that was not its own #

The law decides to recut by pricing: the saving a query the new cuts would bring, under the decayed density, times the half-life, against the cost of the rewrite. Charged for the changed parts, the price falls by 2%, and the decision barely moves, one or two more recuts in a stream. The same pricing has been met before. A refit priced before it is made priced a landmark placement against four candidates and refitted when the saving paid, and a horizon the stream can supply found the price wrong in a different way, a saving assumed to last longer than the traffic let it. Here the saving is priced well and the cost is not what the proposal expected. Both are the same lesson about a pricing rule: it is only as good as the two quantities it compares, and each has to be measured on the structure that will pay it.

What the measurement shows is that the cost of a recut is set by the partition rule, not by the band’s movement. A rule whose background parts depend on the band’s position rewrites the whole file whenever it moves anything, and a cheaper way of charging the rewrite cannot change that. Choosing a growth factor found the same kind of trade for a dynamic array: how much of the structure each resize copies is decided by the rule that sets the new size, and the rule that copies least wastes most. A partition that rewrote only a part of itself at each recut would have to be a different partition, one with fixed pieces that the band’s parts live inside.

The local recut was a first attempt at that, and it failed for a specific reason. It kept the law’s background parts, which were sized for one band position, and recut around the band’s new one. The background then fitted neither the old position nor the new. A design that wants cheap recuts has to give up the law’s background entirely, not keep it and stop maintaining it.

All of these quantities are counted, not timed, for the reason counting instead of timing gives: a transfer is a block read or written, the same on every machine, and the comparisons between designs do not depend on what a block costs.

What the law’s partition is #

The earlier essay found the law worth having because it moved the tuning from a recut interval, which had to match the drift speed, to a half-life, which served every speed. This one finds the cost of that. The law’s partition is a global object. Its cuts are not positions in the file that the band crosses, but shares of the file that the band’s position sets, and when the band moves every share is recomputed.

A recut that rewrote only what moved would need a partition whose cuts did not depend on where the band was, except near it. That is not the square-root law. It is something closer to a file written once for the queries after: a fixed background partition, chosen once and never rewritten, with the band’s region cut finer inside whichever background part holds it. The law’s equal background parts would then be replaced by fixed ones, which are equal on average and never move. A recut would change only the background part holding the band, and its cost would be that part alone. That partition gives up the law’s optimality for the background in exchange for not paying to keep it, and nothing here measures the exchange.

The decayed count the law reads is the other place the cost goes. The counter with no window in it found a decayed count matching a window’s count only on a steady stream, and the law reads a drifting one through a few dozen background queries. That noise alone moves the background cuts as far as the band does, nineteen pieces at a pricing. A smoother count steadies them only when nothing else moves them, and the band always does.

Where the measurement stops #

One cost model. A query is charged one or two reads of its part, and a rewrite two transfers a block, as in the earlier essay. A device on which rewriting part of a file is much cheaper than rewriting all of it, because writes are sequential within a part, would change the partial charge’s arithmetic, though not how many parts change.

Seven parts. With more parts, each background part is smaller, and a recut that moves every cut rewrites the same share of a file. Whether more parts make the band’s own cuts a larger share of the movement was not measured.

Four streams a setting. Every number is a mean over four streams of 20,000 queries; the differences between the law charged both ways are smaller than the differences between streams, which is why they are reported as no difference.

Still open: a fixed background with the band cut inside it #

The law moves every cut because its background parts share out the space the band leaves. A partition with a fixed background would not. Cut the file once into seven background parts balanced by keys. Then, 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 measurement that follows builds that partition, prices its recuts at the blocks of the one part they rewrite, and runs it on every drift speed and jump rate. The prediction is that it recuts several times as often as the law for a seventh of the cost each, and comes within 10% of the law’s cost a query on slow drift, since the band’s own small part does most of the law’s work. It could fail where the band straddles two background parts. Half of the band’s queries would then fall in a part that is a seventh of the file and not cut for them, and on a band that drifts across a boundary, half the time is spent straddling one.