A select sample spaced by its chunk

The run starts of an r-index’s Burrows–Wheeler transform are a sorted set of a few hundred to a few thousand values, and cuts that follow the gathering stored them as a partition into chunks — plain bitmaps, Elias–Fano lists or runs — cut where a shortest path over every possible cut says the bits are least. A select, the request for the $j$-th value, finds its chunk through an upper level and then has to find the value inside it, and every essay since has been about the second half. A select that starts near its answer put a select sample every $t$ values inside each chunk. A sample that has to be found put a rank sample every $s$ bits instead, which bounds the scan but has to be searched for.

A second level that pays in one band used both. A select sample every $t$ values holds not a bit position but the number of the rank block that contains its value. A select reads that number, steps forward through the rank samples from there until one counts past its target, and scans at most $s$ bits inside the block it has reached. The prediction was one or two steps, and the measurement was more: on exact copies with $t$ and $s$ both 64, a select stepped through 2.21 rank samples, and with a sample every 256 values, 6.25. The directory reached 62 bits read a select for 3.76 bits a value, a point neither single kind reached, but under 3.6 bits a value it read 84, and across the eight sets the second level saved more than a twentieth of a bit a value only between about 65 and 100 bits read.

The steps had a cause that the counts made plain. Select samples are spaced in values and rank blocks in bits, so how many blocks lie between a sample and the value after it depends on how many bits a value takes in that chunk. A dense bitmap, two or three bits a value, puts 64 values inside about two blocks of 64 bits; a sparse Elias–Fano chunk of six or seven bits a value puts them across six or seven. One spacing for every chunk is right for at most one density.

A spacing for each chunk #

The repair proposed was to space each chunk’s select samples by its own density. A chunk whose scanned vector is $L$ bits long for $k$ values carries $d = L/k$ bits a value, and $t \approx s/d$ values span about one rank block. Here each chunk takes the power of two nearest $s/d$, clamped between 8 and 512, so that $t$ values span between about 0.7 and 1.4 blocks; the spacing is a function of the chunk’s size, span and form, which the path already knows, and so it costs nothing to record beyond the samples it implies. Everything else is unchanged: the same sets, the same three widths of rank block, the same shortest path choosing the chunks with both levels’ bits charged, and the same model of reads — the upper level and chunk entry, the select sample, every rank sample stepped, and the bits scanned in the block.

The prediction had three parts. The steps would fall to about one a select on every set. On exact copies the directory would read under 70 bits a select for under 3.65 bits a value. And the band where two levels pay would widen from about 100 bits read to about 120. The risk named was the samples’ own bits: a chunk dense enough to need a sample every eight values carries a great many of them, each several bits wide, and that might cost more than the steps it saved.

The steps, on every set #

With rank samples every 64 bits, a select steps through between 0.94 and 1.33 rank samples on the eight sets once each chunk spaces its select samples to span about one block, against 1.15 to 2.21 with a sample every 64 values and up to 6.25 with one every 256. The first part of the prediction holds, and it holds everywhere: on the scattered marks, on exact copies, and at every divergence between. The variation that a fixed spacing produced across sets — a factor of nearly two at $t = 64$ and of five at $t = 256$ — is gone, because the variation was the sets’ densities and each chunk’s spacing now absorbs its own.

One is not quite the floor it sounds like. A select reads at least the rank sample of the block it lands in, and it reads a second when its target lies past the block its sample named. With $t$ values spanning about one block, the sample’s value sits somewhere inside its block and the values after it cross into the next block a good part of the time; that is the third of a step above one that exact copies show. The sets that come in just under one owe it to the last block of each chunk, which has no rank sample after it to read.

What the chunks chose #

On exact copies with rank samples every 64 bits, 54% of values take a select sample every 16 and 46% one every 32; no chunk on any of the three sets needed the densest spacing of 8, and the spacing doubles as $s$ doubles. The scattered marks are twelve Elias–Fano chunks, and an Elias–Fano chunk’s scanned part is its high bits, which take about two bits a value however wide the gaps; every chunk chose the same spacing, 32 values at $s = 64$, which is what $64/2$ gives. Exact copies split between two, though not by kind. Apart from a two-value lead-in, every chunk the path chose there is a plain bitmap, at 2.8 to 3.5 bits a value; the two at 2.8 round to 32 and the three above 3.1 round to 16. A rounding boundary, not a difference in kind, runs through the middle of the set. At divergence 0.01 almost every value is in chunks of about two bits a value, with a few in sparser bitmaps.

The risk the proposal named, the chunk that needs a sample every eight values, does not occur, and the reason is in the forms. A spacing of 8 at $s = 64$ is what a chunk needs when its scanned vector takes about eight bits a value. A bitmap that sparse is never chosen, since an Elias–Fano list codes the same values in fewer bits, and an Elias–Fano chunk scans only its high part, about two bits a value. So the scanned densities the path can produce are squeezed into a narrow range, roughly two to four bits a value, and the spacings into two powers of two. The risk arrives in a smaller form, a spacing of 16 rather than 8, and the next plate is where it is paid.

The spacings themselves say something the fixed directories hid. At $t = 64$ every chunk on exact copies was spaced two to four times too widely for one-block steps. The directory that won at 62 bits read was a compromise between its densest and sparsest chunks, and the proposal’s diagnosis — that one spacing is right for at most one density — is visible in the split: no single power of two is chosen by more than about half of the values on exact copies.

Where the bits went #

On exact copies with rank samples every 64 bits, spacing the select samples by chunk cuts the rank samples a select reads from 17.12 bits to 9.70 and the total from 62.01 to 54.82; the price is in the directory, 3.875 bits a value against 3.763. The saving is exactly where the proposal put it. The select sample costs a select the same 2.5 bits either way, since it is one block number of the same width; the scan inside the block is the same 31 or 32 bits, half a block on average; and the rank samples stepped, which were the part that grew with the spacing, fall by more than seven bits. A select now reads 55 bits where the best fixed directory read 62.

The bill is 0.112 bits a value, and it has two parts. The select samples themselves are the larger: a chunk spaced at 16 carries four times as many as the same chunk spaced at 64, each one a block number of four or five bits, so the directory’s bits rise from 0.366 a value to 0.431. The rest is the partition. Charged for denser samples, the shortest path cuts the set into six chunks where it cut five, and the chunks it chooses code their values slightly less tightly.

The fixed directory’s partition kept a 40-value Elias–Fano chunk between two bitmaps; the per-chunk partition has none, and its five bitmaps are smaller. That second part is the reason the result is not just the first part scaled. The path sees the samples’ bits and nothing about reads, so when a spacing makes a chunk dearer in bits the path answers in bits, by rearranging the chunks, and the rearrangement is chosen without any regard for what the select then reads. The plate’s reads fell because the steps fell; the bits rose partly because the samples grew and partly because the path, minimising only bits, paid to avoid them.

The frontier on exact copies #

On exact copies the chunk-spaced directory reads 54.82 bits a select for 3.88 bits a value, a point no fixed spacing reaches and the single kinds cost 3.93 to reach; at $s$ = 128 and 256 its points sit on or just above the fixed spacings’. The second part of the prediction fails. Under 3.65 bits a value the cheapest read the chunk-spaced directory makes is 80.27 bits, at $s = 128$, and the fixed spacing beside it reads 84.14 for 3.560. Spacing by chunk has moved each point to the left — fewer bits read — and up, by more than the move to the left is worth at that end of the frontier.

The three points tell the same story at three widths. At $s = 256$ the chunk-spaced point is almost exactly the best fixed one, 139.93 bits read against 143.35 at a hundredth of a bit less; at that width a select already steps through about one rank sample with $t = 64$, so there is little left to save, and the spacings chosen, 64 and 128, are close to the fixed ones anyway. At $s = 128$ the move is four bits read for three hundredths of a bit a value. At $s = 64$ it is seven bits read for eleven hundredths, and it lands on a point nothing else reached.

The prediction expected the gain at the cheap end of the frontier in bits and found it at the cheap end in reads. The proposal’s reasoning was that the steps were waste — reads paid for nothing — so removing them would be free. They were not paid for nothing. A wide spacing is a decision to store fewer samples and read more rank samples instead, and on the dense chunks that decision was a reasonable price; reversing it everywhere buys reads at a fixed exchange rate, which is worth paying only where reads are what is short.

Where the second level pays now #

The chunk’s own spacing widens the band where two levels pay downward, not upward: within 60 or 70 bits read it gives three sets a two-level point no fixed spacing reached — the scattered marks at 60, exact copies at 60, divergence 0.0005 at 70 — and within 100 it changes nothing on any set. The third part of the prediction fails in the direction the frontier already suggested. The band was about 65 to 100 bits read a select, and its upper edge has not moved, because above 100 bits read the single kinds’ finest rank samples and the fixed two-level spacings were already as cheap as either can be. Its lower edge has moved from about 65 to under 60.

The largest of the new points is on the scattered marks. With rank samples every 64 bits and select samples every 32 values the marks read under 60 bits a select for 7.44 bits a value, where the better single kind needs 7.86 to read that little: four tenths of a bit a value, the largest saving any version of this directory has made on any set. The marks’ chunks are all Elias–Fano lists scanned at about two bits a value, so one spacing is right for all of them, and the reason no fixed directory found it is only that 32 was not among the fixed spacings measured. The spacing rule found it because it computes the spacing rather than choosing from a list.

That is worth saying plainly, because it limits what the plate shows. On a set of one density, the per-chunk rule is a fixed spacing that happens to be the right one, and its gain over a list of 64, 128 and 256 is partly a gain over a coarse list. On exact copies, where the chunks differ, the rule’s gain is the rule’s own; and there it is five hundredths of a bit at 60 bits read.

Why the steps were a price, not a waste #

The earlier essay read 2.21 steps as a defect, and it was one in the sense that the prediction of one or two was wrong. But the steps were the cheap half of a trade. A select sample costs a block number’s width once per $t$ values; a step costs a rank sample’s width once per select that takes it. On a bitmap chunk of three bits a value with $s = 64$, a block number is four or five bits and a rank sample about ten, so spacing at 16 instead of 64 adds about 0.2 bits a value to the chunk and saves about one rank sample — ten bits — a select. Whether that is a good trade depends entirely on how a bit stored compares with a bit read, and the path, which counts only bits stored, will never make it on its own.

The count is not the time made the general point for this collection’s earliest measurements: a model’s units decide what its optimum looks like. Here the units are stored bits for the path and read bits for the frontier, and every directory in these essays has been a choice of where to stand between them. Where the sparse representation loses found the same arithmetic one level up, choosing between a bitmap and an Elias–Fano list by density: the right representation was a function of the bits a value, and so, it now turns out, is the right spacing of a directory over either.

What the locating apparatus becomes is the reminder of what all of this is for. The run starts are one part of an r-index’s locating apparatus, and a select into them happens once per match located. A directory that saves seven bits read a select on exact copies saves them on every match, which on a collection of copies is most of the work; one that costs a tenth of a bit a value costs it once, on a set of a few hundred values. At these sizes the tenth of a bit is a few dozen bytes. Sparse on average, dense where it gathers measured how far that ratio moves as the indexed text grows: the set grows with the number of runs, the selects with the number of matches.

What the measurement does not settle #

One shape of chunk. Each chunk’s spacing is set from its mean density. A chunk whose values gather unevenly inside it — dense at one end, sparse at the other — would want two spacings, and a chunk-wide mean gives it one. The partition tends to cut such chunks apart, and that may be part of why the path took six chunks on exact copies where it took five.

Powers of two. The spacing is rounded to the nearest power of two, so $t$ values span between 0.7 and 1.4 blocks rather than one. Any spacing would do as well for storage; powers of two are only convenient for the arithmetic that finds a sample.

Reads, not time. Every number is bits read under a model that charges a scanned bit, a sample and a block number alike per bit. A position split in two is where a select was first priced that way, and a machine that reads words rather than bits would charge the scan, which is half of everything here, very differently from the samples.

Still open: a spacing priced by what it saves #

The plates say the spacing rule is right about the steps and wrong about the trade: it chooses each chunk’s spacing to make the steps one, whatever that costs in bits, while the path chooses the chunks to make the bits least, whatever that costs in reads. Neither sees both. A path could. If each chunk’s directory is charged its stored bits plus its expected read bits times an exchange rate — the selects into the chunk times the bits each reads, times $\lambda$ bits stored per bit read — then the path can choose for each chunk among spacings of $s/d$, $2s/d$ and $4s/d$ the one that is cheapest at that rate, and sweeping $\lambda$ traces a frontier the fixed and per-chunk spacings only sample.

The measurement that follows does that, with selects assumed uniform over the values, at $\lambda$ from a thousandth to a tenth, on all eight sets. The prediction is that on exact copies the priced path reaches under 60 bits read for under 3.80 bits a value, and under 70 for under 3.70, filling the gap between the per-chunk point and the fixed spacing at $t = 64$; and that on the scattered marks it changes nothing, since one density has one right spacing. It could fail on the assumption about selects: on an r-index the selects follow the matches, not the values, and a chunk that holds the run starts of a common pattern is asked far more often than its share. The question is whether a directory can be fitted to a rate of exchange between storage and reading, or whether the rate itself depends on which values are asked for — and the path, which sees only the set, cannot know.