A background that holds two bands

The two parts the law was not given built a partition that does not move. A file of four million keys answers selection queries that fall, nine times in ten, in a band 2% of the ranks wide, and the band drifts or jumps. The file is kept in parts because a file written once for the queries after found that a selection reading only its own part, rather than the whole file, is what makes later queries cheap, and what a pass costs when it is a file is why the unit of every cost here is a block transfer. The square-root law, which parts cut where the questions are found by cutting where the questions fall rather than where the keys do, keeps the file in parts sized so that each part’s share of the keys times its share of the queries is the same, and moves almost every cut whenever the band moves. The fixed background instead cuts the file once into six parts by keys and cuts only the part holding the band, in four, by the law over that part alone. Nine parts on disk either way. On drifting traffic the background tied the nine-part law for a quarter of the rewriting. On jumping traffic it lost by 10% to 16% at every rate.

That page found the loss in one place. After a jump the background went on paying for the band at the cost of a whole background part, over a thousand transfers a query, for about three hundred queries — roughly one half-life of the decayed density it reads — before it moved its split to the band’s new part. The law followed in about a hundred and fifty. Its closing section named the cause as the question the background asks: which part holds the most decayed density. A majority is slow to change hands, and the old part keeps it until the old queries have decayed below the new ones. The proposal asked a different question of every part — whether its recent density would pay for splitting it — and allowed the background to hold two split parts at once, the old band’s and the new one’s, at the same nine parts, by cutting each into fewer pieces while two are split. It predicted that the cost after a jump falls to the law’s within a hundred and fifty queries, that on jumps the background comes within 5% of the law, and that on drift nothing changes, since a drifting band rarely needs two splits.

Two ideas, measured apart #

The proposal holds two ideas, and the measurement separates them. Both new designs keep the earlier page’s six parts by keys and its rule for when to recut: a recut is made when the saving it promises, over the half-life of 250 queries, exceeds the price of rewriting the parts it changes. The difference is in which recut they propose when the rule is asked.

The earlier page’s design proposes cutting in four whichever background part holds the most decayed query density. The paying part design asks every part instead: for each of the six, what would the partition cost with that part cut in four, and how much would the rewrite cost, and it proposes the one whose saving most exceeds its price. That is the first idea, and it alone answers the question the earlier page blamed. The two-split design asks the same question of a larger menu. Besides the six single splits it considers every ordered pair of parts, the first cut in three and the second in two, still nine parts in all, and proposes whichever of the thirty-six configurations pays most. That is both ideas together.

The law in nine parts is the yardstick, as before. Every design here is a choice about memory between queries, which is where this account of passes began: the pass that was never a parameter turned the streaming model’s one pass into a dial, and a partition kept between queries is that dial taken to its end, a pass paid once and kept. Streams, charges, seeds and the check every hundred queries are the earlier page’s.

On jumps the second idea does the work #

Allowed to split two parts at once, the background follows a jumping band to within 2% to 4% of the nine-part law — 333 transfers a query against 326 at a jump every 2,500 queries — where splitting one part left it 10% to 16% behind. The prediction of within 5% holds at every rate. The first idea, alone, does nothing: choosing the single part by what its split pays costs 363 at a jump every 2,500 against the majority rule’s 365, and the same to the transfer at the other three rates.

That the paying part ties the majority is the measurement’s first surprise, and it relocates the earlier page’s diagnosis. The two rules make nearly the same recuts — 34 and 33 a stream at a jump every thousand queries, 23 and 24 at every 2,500 — and pay the same for them, so after a jump they move the split at nearly the same moment. The wait was never in the choice of question. It was in the answer the rule could give. A single-split design that moves its split to the new band’s part must give up the split on the old band’s, and for a while after the jump the old part still carries most of the decayed queries. A split moved early would pay for the new band and charge the old band’s queries a whole background part. The saving does not exceed the rewrite until the old queries have decayed, about a half-life later, whichever question is asked.

A design that may hold two splits does not face that trade. It can split the new band’s part while the old one is still split, and the saving from the first stretch of new queries is large enough, alone, to pay for rewriting one part.

How quickly it follows #

After a jump the two-split design is out of the worst within a hundred queries — 854 transfers a query against the one-split background’s 1,190 — and level with the law by about four hundred, not by the hundred and fifty predicted. At 150 queries it pays 549 against the law’s 429. The prediction counted the time to move a split. It did not count how good a split made early can be.

Its first split of the new band’s part is made on the first hundred or so queries since the jump, and the decayed density at that moment still describes mostly the old band. The new part is cut in two, by the law over its own stretch of a density that has only a few dozen new queries in it, so the cut lands roughly near the band rather than tightly around it. The design recuts again as the new density builds, and again, which is why its curve descends in steps where the law’s falls smoothly. The law has the same problem with a thin density and solves it by moving every cut every time, which the earlier pages priced at nine tenths of the file a recut.

From 650 queries after the jump on, the two-split design pays 271 a query where the one-split background pays 230. That is the other side of the same habit. It keeps the old band’s split in three pieces and the new band’s in two until a recut back to one split in four pays for its rewrite. With a half-life of 250 that takes several half-lives once the old band’s queries are nearly gone, because by then the saving from cutting the new band in four instead of two is small. It is the only stretch on any plate where the two-split design is worse than the design it replaces, and over a stream it is outweighed by the first three hundred queries.

One recut, drawn #

A hundred and nine queries after the band jumps from the 20th percentile to the 35th, the two-split design cuts the new band’s part in two and keeps the old band’s part split, now in three pieces rather than four. The rewrite costs 2,730 transfers: the old part’s three new pieces and the new part’s two, a third of the file. The four other background parts are not touched.

The new cut at 35.8% puts nearly all of the band, which runs from about 33.9% to 35.9%, into a piece of 2.5% of the file, the first sixth of the new background part. The old band’s part keeps a piece around the 20th percentile of 1.3% of the file where it had a piece of 0.9%. Both bands are held in small parts, the new one about as well as the old one had been, and it is that second small part, the one the single-split design would have had to give up to make the first, which the old band’s last queries are using.

On drift, where nothing was expected #

On a drifting band the two-split design beats the nine-part law once the band moves a tenth of a percentile every hundred queries or faster: 302 transfers a query against 322 at 0.1, 361 against 393 at 0.2, 486 against 537 at 0.5. The prediction said drift would change nothing, and at the two slowest speeds it changes nothing: the two-split design is the one-split background to the transfer. At the three fastest it is 6% to 10% cheaper than the law and 6% to 8% cheaper than the background it extends.

The earlier page found the fixed background’s one weakness on drift, and it is where this gain comes from. A drifting band crosses the fixed background’s cuts, and while it lies across one, half its queries fall in a part that is not split for them. On one stream that page drew, four blocks of the band straddling a cut at twice the law’s cost nearly erased the background’s lead. A design that can split two parts splits both sides of the cut.

Where the band lies across a background cut, the one-split background pays 541 transfers a query at a drift of 0.1 and the two-split design 248 — less than the law’s 291 in the same stretches; where the band lies inside one part, all three pay within six transfers of each other at that speed, and within twelve at the faster ones. The band straddles in a tenth of the blocks at every speed, and that tenth carries the whole difference. Inside a part the three designs are doing the same thing: a small piece around the band and large pieces elsewhere. Across a cut the one-split background holds half the band in a whole sixth of the file. The two-split design holds each half in a small piece of its own part.

That the two-split design beats the law across a cut, and not only the one-split background, is a property of the law’s own geometry. The law must place all its cuts by one rule over the whole file, and the band’s piece is one of nine. The two-split design spends two of its pieces on the two halves of a band that a fixed cut divides, and its pieces there can be smaller than the law’s single one. It is a small advantage over a tenth of the stream, and at the fastest drift it is the difference between the two designs.

How often two are split, and what they cost to write #

About half the two-split design’s recuts on jumping traffic leave two parts split, and on drift the share rises with speed, from none at 0.05 to a quarter at 0.5. On jumping traffic most of those are the moments the drawn recut shows, the new band split while the old one fades. On drift they are straddles. Why their share rises with speed is not settled by these streams: the share of blocks in which the band straddles a cut stays at a tenth at every speed, and what changes is how many recuts the design makes — 84 at 0.05 and 179 at 0.5 — and how many of those land while the band is across a cut.

At a jump every 2,500 queries the two-split design pays about twice the one-split background’s rewriting, four transfers a query against two, for 34 fewer in its queries. It recuts 34 times in a stream where the background recuts 24, because following a jump now takes several recuts — the early split, the improved one, the eventual return to one split — and each rewrites a third of the file or less. The law rewrites ten transfers a query, because each of its recuts moves cuts everywhere. The two-split design’s writes are still under half the law’s. It recovers the law’s following without the law’s habit of moving the background, which was the point of the background, and every cut the law moves measured what that habit costs.

What the proposal got right, and why #

The proposal had the right remedy and the wrong reason for it. The earlier page diagnosed a rule that asked a slow question, and the paying-part design shows the question was not slow, or rather that any question a one-split design can ask has the same answer at the same time. What made the background slow was a constraint: one split. A partition with a fixed background and one split part is forced to choose between the band that is leaving and the band that has arrived, and while the leaving band still carries most of the recent queries, it chooses wrongly for a reason that is right on the evidence it has. Allowing two splits removes the choice.

The same diagnosis explains the drift gain. A band across a background cut is the drifting version of a band that has jumped — two parts each holding half the hot queries — and a one-split design makes the same forced choice there, every time the band crosses one of five fixed lines. The two-split design was proposed for jumps and finds its largest advantage over the law on drift, because drift makes the forced choice more often.

A recut the law decides found the law’s rule — recut when the saving over a half-life exceeds the price — the right rule for when. These measurements say something about which: a design that can only make expensive recuts must wait to make them, and a design given cheap partial ones, a part’s worth rather than a file’s, can make them early and correct them later. The two-split design recuts more often than the background it extends, writes twice as much, and is cheaper on every stream except the slowest, where it is the same.

What these streams leave out #

One shape of band. Every stream has one band, 2% wide, carrying nine tenths of the queries. A workload with two bands at once, steadily, is what the two-split design is built for and was not run; the jumping streams give it two bands only briefly.

Nine parts, divided one way. The count of nine is the law’s seven plus the two that the two parts the law was not given found a fixed background needed before the comparison stopped being bought with parts. The two-split design divides its three extra parts as three and two between the two bands. A division of two and two with the remaining part kept for the background, or one weighted by the bands’ densities, would place the cuts differently. Only one division was run.

One half-life. The decayed density’s half-life is 250 queries throughout, as on the earlier pages. A shorter half-life would make every design follow sooner and each first split cruder; the late cost of keeping two splits is set by it too.

Still open: a background that lets go of the old band sooner #

The two-split design’s one weakness on these plates is late: from 650 queries after a jump it pays about forty transfers a query more than the one-split background, because it keeps the old band’s part split in three until merging it back pays for the rewrite, and by then the saving from cutting the new band in four rather than two is small. The rule for when to recut is the law’s, and it prices only the saving over the next half-life.

A design could drop the old band’s split as soon as the old part’s decayed density falls below a share of the new part’s — releasing its pieces to the new band without waiting for the saving to exceed the rewrite. The measurement that follows gives the two-split design that rule, with the share swept from a quarter to a twentieth, and measures cost after a jump, on every jump rate and on drift. The prediction is that at a share of a tenth the late cost falls to the one-split background’s, about 230 a query, without giving back the early gain, and the jump costs come within 1% of the law. It could fail on drift: there the two splits are a straddle, not an old band and a new one, and the half of a straddling band in the emptier part may fall below a tenth of the other half for a moment and lose its split exactly while it is still being queried. The question is whether one rule can tell a band that is leaving from half a band that is still there, or whether the price-over-a-half-life rule is slow on jumps because it is right on drift.