A recut the law decides

Parts cut where the questions are wrote a file of four million keys out as seven parts, so that each later selection query read only the part holding its rank. When nine queries in ten asked about the top 2% of ranks, parts balanced by keys cost 1,170 block transfers a query. Parts cut so that each part’s share of the keys times its share of the queries was equal cost 290. That is the square-root law: the cost of a query is the size of its part, and the sizes that minimise the expected cost fall as the square root of the query density. The saving lasted exactly as long as the queries stayed where they had been counted. Moved a percentile and a half, the fitted parts cost more than plain ones.

Its closing section proposed a partition that recuts itself. Keep a running, decayed count of where recent queries fall. Price the current partition under that density, and price the partition the law would cut from it. When the difference, over some stretch of future queries, exceeds the cost of rewriting the file, recut. The prediction was that this law-triggered recut stays within 20% of the best fixed recut interval at every drift speed, while a fixed interval must be tuned to the speed to do as well. It was expected to fail on traffic that jumps rather than drifts, where the recut would fit a place the queries had already left.

The file, the model of a query’s cost, and the streams #

The earlier page answered sixty queries a setting, each by exact selection within its part. A drift study needs tens of thousands, and exact selection at that scale is too slow. It turns out not to be needed. With 8,192 words of memory and blocks of 1,024, the exact selection of what a pass costs when it is a file costs exactly one read of a part holding at most 4,096 keys and exactly two reads of any larger part, at every part size from a thousand keys to the whole file. That rule is used here as the cost of a query, and it is checked against the exact selection at several sizes. A rewrite reads the file and writes its parts, 8,192 transfers.

The file’s ranks are divided into 4,096 pieces of 1,024 keys, and every partition cuts at piece boundaries into seven parts. The law’s cuts are computed from a density: each piece’s share of recent queries, plus one query’s worth spread evenly, so that no piece is certain never to be asked about. Every policy fits the first fifty queries and writes its first partition, and that write is charged to all of them.

The queries follow the earlier page’s shape: 90% of them uniformly within a band 2% of the ranks wide, the rest anywhere. The band’s centre either drifts, at 0.02 to 0.5 percentiles every hundred queries, reflecting off the ends of the file, or jumps to a random place at random times, on average every 1,000 to 10,000 queries. Each setting is four streams of 20,000 queries.

The fixed-interval policies recut every 125 to 4,000 queries, from the queries of the last interval. The law checks every hundred queries. Its density decays with a stated half-life, and it recuts when the saving a query it computes, times the half-life, exceeds the rewrite. A band that never moves, fitted once, costs 356 transfers a query. That is the floor the policies are chasing.

Every fixed interval is right for one speed #

At a drift of 0.02 percentiles every hundred queries the best fixed interval is 500 queries; at 0.2 and 0.5 it is 125, and the interval right for the slowest drift costs 919 transfers a query on the fastest, against 558 at its own best. Each curve is a trade between two costs. Recutting often keeps the parts where the queries are and pays 8,192 transfers each time. Recutting rarely saves the rewrites and answers queries from parts cut for a band that has since moved. Where the band moves slowly the rewrites dominate, and the interval should be long. Where it moves fast the stale parts dominate, and the interval should be short.

Never recutting costs 1,230 to 2,336 transfers a query, more than the keys’ partition would. The fitted parts are narrow where the band was and wide everywhere else, and once the band has left, every query falls in a wide part. The parts are worse than balanced ones as soon as the band has moved a few percentiles. The earlier page’s warning holds at every speed.

This is what the proposal set out to escape. A fixed interval must be chosen for the speed, and the speed is exactly what a system cannot see in advance.

The law, at two half-lives #

With its recent density decayed at a half-life of 250 queries, the law costs 339 transfers a query at the slowest drift and 681 at the fastest. That is within 7% of the best fixed interval up to 0.1 percentiles every hundred queries, 15% at 0.2 and 22% at 0.5. It needs no knowledge of the speed. At the three slower speeds the prediction holds. At the two fastest it misses the 20% by a little. What matters more is that a single fixed interval, chosen once, does much worse across the same range. Recutting every 1,000 queries is 8% off the best at the slowest drift and 117% off at the fastest.

With a half-life of 1,000 queries the law falls 13% to 74% behind. At a drift of 0.2 percentiles every hundred queries the band moves two percentiles in a thousand queries, the width of the band itself. A density that remembers the last thousand queries is spread across twice the band’s width, and the parts the law cuts from it are too wide where the queries are now. The law then recuts often and cuts wrongly each time, 157 rewrites a stream, because each recut fits a smeared density and is immediately stale.

So the law does not remove a setting. It replaces the interval with a half-life, the time scale over which the recent queries are allowed to describe the next ones.

One half-life for every stream #

At a half-life of 250 queries, the law costs between 0.87 and 1.22 times the best fixed interval on all nine streams. The best fixed interval moves fourfold across them, from 500 queries to 125. The half-life that suits the fastest drift is also good at the slowest, because at slow drift the law simply recuts less often, when its saving is small, with no change of setting. A fixed interval has no such freedom. It recuts on schedule whether anything has moved or not.

Longer half-lives do worse everywhere, and worst at fast drift. A half-life of 2,000 queries costs nearly twice the best fixed interval at 0.2 and 0.5 percentiles and on the fastest jumps. The pattern suggests the half-life should be about as short as the density can be estimated from. At 250 queries, 225 of them in the band, the band’s position is known to a fraction of its width. A half-life of 100 or 50 would track faster and estimate worse. Those were not measured.

This is the same kind of result a horizon the stream can supply found for a landmark search’s refits. A rule that prices a change before making it needs to know how long the change will last, and the choice of that time scale is the setting that remains. Here it is set once and serves every stream. There, on memoryless jumps, no time scale estimated from the past could win the fastest case.

What the law is pricing #

The law’s decision at each check is a small calculation, and it is worth seeing what goes into it. It holds two partitions: the one in use, and the one the square-root law would cut from the decayed density now. It prices both under that density, as the expected cost of the next query: for each piece of the file, the density there times one or two reads of the part the piece falls in. The difference is the saving a query of recutting now, if the density is right. The law multiplies that by the half-life, on the reasoning that the density describes roughly the next half-life’s worth of queries, and recuts if the product exceeds 8,192 transfers.

Nothing in that calculation knows the drift speed, the band’s width or whether the traffic jumps. They enter only through the density. On a slow drift the saving grows slowly after each recut, crosses the threshold, and the law recuts. On a fast drift it crosses sooner. After a jump it crosses at once, by a wide margin. Between jumps it stays near zero. The speed a fixed interval must be told is read here off the data, through how fast the priced saving grows.

The one number the calculation cannot read off the data is how many future queries a saving should be multiplied by. Setting it to the half-life ties the horizon to the memory: a law that remembers 250 queries bets on the next 250. A refit priced before it is made priced a landmark search’s refits the same way, a saving on recent queries scaled to the next stretch against the refit’s price, and found the scaling was where it went wrong. The law pays for its information in lateness, and the half-life is the price it sets.

Jumps, the case that was to defeat it #

On traffic whose band jumps every 5,000 queries on average, the law costs 342 transfers a query against 383 for the best fixed interval. It rewrites 12.8 times a stream where that interval rewrites 80. The prediction had this backwards. A jump is the easiest change for the law to see. Within a few hundred queries of a jump, the decayed density has most of its weight at the new band, the current parts are wrong by a wide margin, the saving is large, and the law recuts once. Between jumps nothing moves, the saving is near zero, and it does not recut at all. A fixed interval recuts every 250 queries through the long quiet stretches because it cannot tell them from the moments after a jump.

The worry was that the law would fit a place the queries had left. That happens only if the band jumps again before the recut has paid, which at a jump every 1,000 queries it sometimes does. There the law loses, 518 transfers a query against 488. A recut costs 8,192 transfers, and it pays only if the band stays for enough queries to save that much, several hundred at the savings these parts give.

Why a long memory lags #

On one fast-drifting stream, the law with a half-life of 1,000 answers its queries at 629 transfers each and rewrites 146 times; at 250 it answers at 456 and rewrites 90 times. The long memory costs twice over. Its parts are cut from a smeared density and fit the band poorly, so every query pays more. And because they fit poorly, the saving it computes at each check is large, so it recuts again and again for parts that fit no better. The short memory cuts parts that fit, and recuts only when the band has moved enough.

The fixed interval of 125 queries, the best on this stream, answers cheapest of all, at 363. It recuts 159 times, every time from exactly the last 125 queries, a window short enough to be sharp. The law with a half-life of 250 trades some of that sharpness for recutting less. The counter with no window in it found that a count fading by half every H queries settles, on a steady stream, at the count of a window 1.44H long. A half-life of 250 is a window of about 360 queries, between the best fixed intervals for slow and fast drift, and a half-life of 1,000 is a window of 1,440, longer than every interval that did well. A short memory is noisy and a long one is late, and a moving target punishes lateness.

Where the cost goes #

At every drift speed the law rewrites less than the best fixed interval and answers its queries dearer. At 0.05 percentiles every hundred queries it spends 16 transfers a query on rewrites against 33, and 350 answering against 333. The two nearly cancel, which is why the costs are within 1%. At 0.5 percentiles every hundred queries it rewrites nearly as often as the best interval, 60 against 66, and answers much dearer, 621 against 493. There the band moves a whole band-width every four hundred queries. The law’s density, averaged over 250 queries, is always a little behind, and a fixed interval of 125 queries, recutting from exactly the queries since the last cut, is ahead of it.

A file written once for the queries after found that writing the file out as parts paid from the second query. The rewrite is the same act, repeated. Its price, 8,192 transfers, is fourteen queries at the keys’ partition and twenty-three at the band’s floor. Every policy here is a way of deciding how often that price is worth paying.

The limits of the measurement #

A modelled cost. Each query is charged one or two reads of its part by a rule calibrated on the earlier pages’ exact selection, not by running the selection. Every figure is in block transfers, counted rather than timed for the reasons counting instead of timing gives. The rule matches the exact selection at every size tried, but a query that lands on a part boundary, or a memory other than 8,192 words, could break it.

Four streams, one band width. Each setting is four streams of 20,000 queries, and the band is always 2% wide with 90% of the queries. A narrower band would make stale parts more expensive and favour shorter intervals and half-lives. A wider one would do the opposite.

One shape of decay. The density fades exponentially. What a heavier tail actually buys compared four decays on a burst and found the heavier tails remembering it far longer. Here that would keep old band positions in the density, which on a moving band is exactly the lateness that cost the long half-life, so no heavier decay was tried.

The law’s horizon is its half-life. The saving is scaled by the half-life, on the reasoning that the density describes about that many future queries. A horizon set separately from the half-life was not tried.

Rewrites are whole. Every recut rewrites the whole file. A recut that rewrote only the parts whose cuts moved would cost less on slow drift, where one cut moves at a time, and might change which policy wins there. It was not built.

Still open: a recut that rewrites only what moved #

Every recut here reads and writes the whole file, 8,192 transfers, even when only one of its six cuts has moved. On a slow drift that is most recuts. The band moves across one cut, the law moves that cut, and the five parts that did not change are rewritten anyway. A recut that rewrote only the two parts on either side of a moved cut would cost a fraction of the whole, in proportion to their size. And the parts near the band are the small ones.

The measurement that follows charges a recut the read and write of only the parts whose boundaries change, lets the law price that smaller cost, and runs it on every stream. The prediction is that on slow drift the partial recut costs a tenth of a full one, the law recuts several times as often, and it comes within 5% of the still band’s floor of 356 transfers a query. On jumps it should change nothing, since a jump moves every cut. It could fail if moving one cut changes the law’s best position for the others. Then a partial recut, cheap in itself, would leave the rest of the partition fitted to a band that has gone, and the savings of recutting often would go to paying for parts that fit worse.