A select that starts near its answer

Cuts that follow the gathering found the cheapest way to cut an r-index’s run-start values into chunks. The values are positions in a collection of 32 copies of 2,048 characters, few overall and crowded where the copies differ, and sparse on average, dense where it gathers had held them as chunks, each chunk a bitmap, its own Elias–Fano or a run, whichever is cheapest. Choosing the cuts as a shortest path through the sorted values, each chunk charged its cheapest form plus its share of the upper level, gave the cheapest partition exactly. On exact copies it is two chunks: 2 values spread over 63,481 positions, and 664 values gathered in a bitmap over 2,055. That costs 3.27 bits a value, 27% under chunks of 32.

It also costs 1,065 bits read for every select. A select asks for the $j$-th value; the upper level points it to the chunk, and a bitmap chunk is scanned from its first bit to the target one, which in a bitmap of 2,055 bits is half of it on average. One Elias–Fano, a position split in two, reads 33 bits a select. A cap on the values a chunk may hold bought the reads back at a steady rate: capped at 64 values, 3.68 bits a value for 116 bits read; at 32, 4.08 for 93.

Its closing section noticed that the cap is a blunt instrument. The scan is long because it starts at the chunk’s beginning, and it could start nearer the target instead. A long chunk could carry its own small directory, so that a select jumps into the chunk and scans only the stretch after the entry it lands on. That is a second level of the same structure inside the long chunks only, and its bits can be charged in the shortest path like everything else, so the optimum can choose to pay for it. The prediction was that on exact copies the uncapped optimum with directories reads under 150 bits a select for under 3.5 bits a value, which no capped partition achieves, and that on the middle divergences it changes nothing, because their chunks are already short.

The first part holds, and the second turns out to be the more interesting failure.

A sample every t values #

The directory is a select sample. A chunk of $k$ values over $u$ positions gets the offset, within the chunk, of every $t$-th value’s bit: in its bitmap for a bitmap chunk, in its high bit vector for an Elias–Fano chunk. Each sample takes $\lceil \log_2(u + 1) \rceil$ bits, the width a position needs when it is stored outright, and a chunk has $\lfloor (k - 1)/t \rfloor$ of them, since its first value is found at the chunk’s start. A select for the $j$-th value of a chunk reads the sample before it, one entry, and scans from that sample’s bit to its own. Runs are read without any scan, as before.

The shortest path now charges each chunk its cheapest form, its samples and the upper level’s share, so the optimum chooses its chunks with the samples’ price in view. With no samples, $t = \infty$, the path and its partitions are the earlier essay’s exactly, and the reads are counted by the same model: the upper level’s block to find the chunk, then the bits scanned inside it. It is a model of the bits read, not a timing. Samples are measured every 256, 64 and 16 values, beside the cheapest partition capped at 32, 64, 128 and 256 values and uncapped.

Under 150 bits on exact copies #

On exact copies, a select sample every 64 values inside the cheapest uncapped partition costs 3.45 bits a value for 111 bits read a select, against 3.68 bits for 116 read when the chunks are capped at 64 values. The prediction’s under-150-bits for under-3.5 is met, and the comparison it named is decisive: at about the same reads, the samples are 6% smaller than the cap. Every 16 values they cost 3.93 bits a value for 43 bits read, within ten bits of one Elias–Fano’s reads at 43% of its size; no cap on the plate reads fewer than 93.

The samples keep what the cap gave away. With a sample every 64 values the path still chooses two chunks, the same two, and the bitmap of 664 values over 2,055 positions, a bitmap because at one value in three a sparse representation loses, is kept whole, with ten samples inside it at twelve bits each: 120 bits, 0.18 bits a value, which is the whole of the difference between 3.45 and the uncapped 3.27. The cap at 64 instead cuts the set into twelve chunks, each with its own entry, tag and pointer in the upper level, and pays 0.41 bits a value over the uncapped partition, more than twice what the samples pay, to buy about the same reads. A sample is a cheaper way to find a place inside a chunk than a cut is, because it does not have to say what form the next stretch takes or where its payload lives.

Every 16 values the price of the samples starts to shape the partition: the path cuts five chunks rather than two, the largest of 240 values, because a sample every sixteen values in a sparse stretch costs more than the stretch’s Elias–Fano bits would save by joining it. The optimum then pays half a bit a value for its samples, and still reads a twenty-fifth of what the uncapped partition read.

Where the chunks were short #

At a divergence of 0.0005, samples every 64 values cut the uncapped optimum’s reads from 175 bits a select to 99 for one twentieth of a bit a value more, 5.35 bits against 5.29. The prediction said the middle divergences would not change, because their chunks are already short, and the cheapest partition’s median chunk there does hold 18 values. But its largest holds 212, a bitmap laid over the place where the copies gather most, and the largest chunks are where the long scans are: a select into a chunk of 212 values reads on average half of it, and the chunk’s three samples cut every select’s scan to the stretch after the sample before it.

The capped partitions sit next to the sampled ones here, not far above them: capped at 64 values, 5.45 bits a value for 94 read. Where most chunks are short, a cap and a sample act on the same few long chunks, and a cut at 64 values in a gathering of 212 costs only a few upper-level entries. The samples’ advantage, a tenth of a bit a value at the same reads, is a third of what it is on exact copies, because there is one long chunk rather than one enormous one.

At a divergence of 0.01 the uncapped optimum reads 931 bits a select, nearly as many as on exact copies, and samples every 64 values bring it to 107 for 6.05 bits a value, against 6.13 for 96 when the chunks are capped at 64. Here the long chunks are not bitmaps over a gathering but Elias–Fano chunks over the near-even spread that the copies drift into, and the cheapest partition makes them as long as 1,202 values because a long Elias–Fano chunk pays its upper-level entry once. A select scans its high part from the start. The samples shorten that scan as well, at a cost of nine hundredths of a bit a value.

At this end of the range the cap and the samples are nearly equal. Every 256 values the samples read 286 bits for 5.94, where the cap at 256 reads 247 for the same 5.94: the cap is slightly better, because the path, given samples, re-cuts the long chunks less than the reads would want. Samples help most where one chunk is very long and dense, and least where many chunks are long and sparse.

When the path answers with cuts #

The samples are charged in the path, so the optimum can respond to them, and where it does the response is to cut. On exact copies and at 0.0005, a sample every 64 values leaves the partition exactly as it was, two chunks and thirty, and the samples simply sit inside the long chunks. At 0.005 the same samples take the partition from 25 chunks to 48, and at 0.01 from 15 to 57: the longest chunk at 0.01 falls from 1,202 values to 317.

The reason is the width of a sample. A sample is an offset within its chunk, as wide as the logarithm of the positions the chunk spans, and a long Elias–Fano chunk over a sparse stretch spans many thousands of positions, so its samples cost thirteen or fourteen bits each against twelve in the dense bitmap. Past some length, cutting the chunk and paying an upper-level entry costs the path less than sampling it, and the path cuts. That is why the cap and the samples come out nearly level on the most drifted sets: there the cheapest partition with samples is itself partly a capped partition, chosen by price rather than by rule.

Every set, one setting #

A sample every 64 values brings every set’s reads to between 77 and 111 bits a select, from as many as 1,371 without them; the cap at 64 values brings them to between 77 and 117. On every set the two settings read within fourteen bits of each other, and the samples are the smaller on every one, by 0.002 bits a value at 0.002 up to 0.23 on exact copies; they read more than the cap on three sets, 0.0005, 0.005 and 0.01, by five to fourteen bits. The scattered marks, a set with no gathering at all, show the same thing from the other side: the uncapped partition there makes a few chunks of hundreds of values and reads 1,371 bits a select, and samples every 64 values take that to 94 at 7.23 bits a value, against 103 at 7.41 for the cap. The plate is the closing section’s comparison drawn for every set at once: a cap and a sample are two ways to bound a scan, and which is cheaper depends on how the set’s long chunks are made.

The samples cost 0.01 to 0.18 bits a value at one every 64 values, and 0.29 to 0.53 at one every 16. Their cost follows the long chunks: highest on exact copies and at the two ends of drift, lowest at 0.002, where the cheapest partition’s chunks are a median of 20 values and the largest only 100, so few of them reach a sample at all. Where a set has no long chunks, the samples cost almost nothing because they are almost never there, and save almost nothing for the same reason.

Bounding a scan #

A select has two ways to be cheap. It can land in a short chunk, which is what a cap does by making every chunk short; or it can land near its answer inside a long chunk, which is what a sample does. A cap pays for its bound with a cut, an upper-level entry, a tag and a pointer, about 45 bits on these sets, and it cuts the set where the cap falls rather than where the set changes density, which is the misplacement the shortest path was invented to avoid. A sample pays eleven bits for a bound and leaves the chunk whole. On exact copies, where one chunk holds all but two values, the difference is 6% of the index at the same reads.

The earlier essays found a sequence of savings on the same values: chunks beat one Elias–Fano by holding dense places as bitmaps, cuts beat fixed chunks by following the gatherings, and samples now beat caps by keeping the cuts where the gatherings put them. Twenty bits apart began with the observation that a sparse set’s values are best described by how far apart they are; each step since has let the description follow the values a little more closely, and the samples are the first step that is paid in reads rather than in bits.

What the prediction got right #

The closing section predicted that on exact copies the uncapped optimum with directories would read under 150 bits a select for under 3.5 bits a value, which no capped partition achieves. With a sample every 64 values it reads 111 for 3.45; the nearest capped partition reads 116 for 3.68. It predicted that the middle divergences would not change, since their chunks are short. Their median chunk is short, and their largest is not: at 0.0005 the samples take the reads from 175 bits a select to 99, two fifths of them, because the reads were all in the one long chunk the median does not see.

The question was whether a cap on chunk length is the right way to buy back reads, or whether a cheapest partition should be allowed to make its chunks as long as the set wants and carry its own way into each one. On the sets where the set wants one very long chunk, the second, by 6% of the index. Where it wants many long sparse chunks, neither, by a tenth of a bit either way.

What the samples leave out #

Samples by count. A sample falls every $t$ values, so in a sparse stretch of a chunk it may be hundreds of bits from the next. A sample every $s$ bits would bound the scan in bits directly; nothing here measures it.

One spacing at a time. The path is given one $t$ for every chunk. A path free to choose each chunk’s spacing, or none, would sit on or under every curve here, since each $t$ measured is one of its choices; it was not run.

One collection. As in the earlier essays, 32 copies of 2,048 characters, drifted at seven divergences, and one set of marks, the marks a locating apparatus keeps.

A model of reads. Bits scanned after the directory lookups, counted as the earlier essays counted them, with a sample’s entry charged its width; the count is not the time, and nothing here closes that gap. Nothing was timed.

Still open: a sample every s bits #

A sample every $t$ values bounds how many values a select passes, not how many bits it reads. In a bitmap chunk over a gathering, 64 values span about 200 bits; in an Elias–Fano chunk over a sparse stretch, 64 values span 64 ones and their gaps in the high part, more bits again; and inside a chunk whose density changes, one sample’s stretch can be ten times another’s. A sample every $s$ bits of the chunk’s bit vector instead bounds the scan at $s$ whatever the density, and costs a count of the ones before it rather than a position, which is often narrower.

The measurement that follows gives the chunks rank samples every $s$ bits, $s$ from 64 to 1,024, charged in the path as before, and draws the frontier against the samples by count. The prediction is that on exact copies, where the long chunk is one dense bitmap, the two kinds of sample draw the same frontier, and that at 0.005 and 0.01, where the long chunks are sparse Elias–Fano chunks, samples by bits read a third less at the same cost, since there 64 values span three or four times as many bits as in the bitmap. It could fail on the select itself. A rank sample tells a select how many ones precede it, so the select must find its target’s sample by a search over samples rather than jump to one, and that search reads entries a value-indexed sample never has to. The question is whether a select is better served by a directory indexed by what it asks, a rank, or by what it reads, a position.