A sample that has to be found

A select that starts near its answer put a small directory inside the chunks of the cheapest partition of an r-index’s run-start values. The values are positions in 32 drifted copies of 2,048 characters, and cuts that follow the gathering had found the cheapest way to cut them into chunks, each held as a bitmap, its own Elias–Fano or a run, as a shortest path. Its chunks could be very long, and a select scanned a chunk from its start: 1,065 bits read a select on exact copies. A select sample every 64 values, the offset of every 64th value’s bit within its chunk, let a select jump to the sample before its value and scan from there. On exact copies the uncapped partition with those samples read 111 bits a select for 3.45 bits a value, where capping the chunks at 64 values cost 3.68 for about the same reads.

Its closing section noticed what a sample by count bounds. It bounds how many values a select passes, 63 at most, not how many bits it reads, and the bits depend on the chunk’s density. In a dense bitmap over a gathering, 64 values span about 200 bits; in an Elias–Fano chunk over a sparse stretch, 64 values span their own 64 ones and the zeros of their gaps in the high part; and inside one chunk whose density changes, one sample’s stretch can be ten times another’s. A sample every $s$ bits of the chunk’s vector would bound the scan at $s$ bits whatever the density, and it holds a count of the ones before it rather than a position, often a narrower number. The prediction was that on exact copies the two kinds of sample would draw the same frontier, and that at divergences of 0.005 and 0.01, where the long chunks are sparse, samples by bits would read a third less at the same cost. It named the risk: a sample by count is found by arithmetic, the $j$-th value’s sample is number $\lfloor j/t \rfloor$, while a sample by position says how many ones precede it and must be searched for.

The risk is where most of the difference went.

Samples a select has to search #

A chunk’s scanned vector is its bitmap, for a bitmap chunk, or the high part of its Elias–Fano, for an Elias–Fano chunk; runs are read without any scan, as before. A rank sample every $s$ bits holds the number of ones in the vector before that bit, in as many bits as the chunk’s value count needs. To select the $j$-th value of a chunk, a select must find the last sample whose count is at most $j$, which it does by binary search over the chunk’s samples, reading $\lceil \log_2(E + 1) \rceil$ of them for $E$ samples; then it scans from that sample’s bit to its own. The samples’ bits are charged in the shortest path, so the optimum chooses its chunks with their price in view, and with no samples the path is the earlier essay’s exactly.

The comparison is the earlier essay’s select samples, every 256, 64 or 16 values, jumped to directly, against rank samples every 1,024, 512, 256, 128 and 64 bits. Reads are counted in the same model: the upper level’s block that finds the chunk, the search, if any, and the scan. It is a model of the bits read, not a timing, and a count of what is read is not the time it takes.

The same frontier at the sparse end #

At a divergence of 0.01, rank samples every 128 bits cost 6.05 bits a value for 104 bits read a select, and select samples every 64 values cost 6.05 for 107: at the same cost, three bits fewer, not a third fewer. The two curves lie on one frontier from 250 bits read down to about 100. Below that the rank samples go further in small steps, 80 bits read for 6.18 at a sample every 64 bits, where the next select-sample setting, every 16 values, jumps to 55 bits read for 6.52.

The scan inside the block is bounded as the closing section said it would be. With a sample every 128 bits, a select at 0.01 scans 57 bits after its sample, about half a block, where a select sample every 64 values leaves it scanning a stretch that varies with the chunk’s density. What eats the advantage is the other column: the search.

A third of every select spent searching #

With a rank sample every 128 bits, the search for the right sample is a third of what a select reads on exact copies, 31 bits of 98, and between 1% and 33% across the sets. On exact copies the long chunk is a bitmap over the gathering, a bitmap because at that density a sparse representation loses, about two thousand bits long, and it holds a dozen or more rank samples of ten bits each; a binary search over them reads four or five, forty or fifty bits, for every select that lands in it. A select sample costs none of that, because the select knows which sample it wants before it reads anything.

Where the long chunks are few and short, the search costs almost nothing: at 0.002, where the cheapest partition’s largest chunk holds 100 values, a select reads one bit of search on average. The search is a cost of long chunks, which are exactly where samples are wanted, so it is largest where the samples are most useful.

Exact copies #

On exact copies, rank samples every 128 bits cost 3.51 bits a value for 98 bits read, against select samples every 64 values at 3.45 for 111. The prediction that the two would draw the same frontier here holds: neither point is beaten by the other on both counts, and rank samples every 256 bits, at 3.39 for 170, sit between the select samples’ 3.31 for 380 and 3.45 for 111. On a dense bitmap a sample by count and a sample by position are nearly the same thing, since 64 values in the gathering span about 200 bits of a vector where about one bit in three is a one; the select samples’ positions are twelve bits each and the rank samples’ counts ten, so the rank samples’ narrower entries buy almost nothing.

At 0.005 the rank samples read 97 bits a select for 6.74 bits a value, against 102 for the same cost by count; every 64 bits they read 69 for 6.85, where the select samples have nothing between 102 and 55. Here, as at 0.01, the rank samples’ gain at a given cost is five per cent of the reads, not a third. Their real advantage over the select samples on the sparse sets is granularity: their steps are smaller, so a budget of reads that falls between two select-sample settings is met more cheaply.

What the path does with them #

The samples are charged in the path, and the path answers rank samples as it answered select samples, by re-cutting where samples cost more than cuts. On exact copies a rank sample every 128 bits takes the partition from two chunks to three; at 0.01, from 15 chunks to 48, and at a sample every 64 bits to 58, with the largest chunk falling from 1,202 values to a few hundred. At 0.0002 and 0.0005 the partition does not move at any spacing measured, because the long chunks there are bitmaps over gatherings, where samples are cheap and a cut would separate values that one chunk holds most cheaply.

That re-cutting is part of why the two kinds of sample come out level. Where samples of either kind are dear, in long sparse chunks with wide entries, the path declines them and cuts instead, and a cut costs the same whichever kind of sample it replaces. Where they are cheap, in dense bitmaps, both kinds are taken and both work. The cases where the kind of sample could matter most are the ones the path takes out of play.

Within a budget of reads #

Within a budget of 100 bits read a select, rank samples give the smaller index on five of the eight sets, by up to 0.42 bits a value on exact copies; select samples are smaller on the scattered marks, by 0.11, and at 0.0005, by 0.02, and at 0.002 the two are equal. The large wins are budgets that the select samples’ coarse steps miss: on exact copies the select samples’ only setting under 100 reads is a sample every 16 values at 3.93 bits a value, and the rank samples meet the budget at 3.51. At a budget of 80 bits the rank samples win on seven sets of eight for the same reason.

On the marks, the set with no gathering, the marks the locating apparatus keeps, the select samples win at 100 bits read because their sample every 64 values happens to land just under the budget, at 94 bits read, while the rank samples’ nearest setting reads 103. Neither kind of sample is better in itself on these sets. Each is a different grid of settings over one frontier, and which is cheaper at a given budget depends on where the grids’ points fall.

What a sample has to say #

The two kinds of sample answer different questions, and a select needs both answers. A select sample says where the $t$-th value is, so the select knows which sample it needs by arithmetic, but not how far it will scan. A rank sample says how many ones precede a position, so the scan after it is bounded, but the select must search for it. The earlier essay’s select samples paid for their ignorance of the scan length with long scans in sparse stretches; the rank samples pay for their ignorance of which sample is needed with a search, and the two costs come out nearly equal on every set.

Sparse on average, dense where it gathers found that the run-start values are dense in a few places and sparse everywhere else, and every directory since has had to serve both. There is a plain way to see why the two come out level. A select sample every $t$ values costs a select one entry and then a scan of, on average, half the bits that $t$ values span; a rank sample every $s$ bits costs a select $\log_2$ of the chunk’s samples in entries and then half of $s$. In a chunk of uniform density the two can be set to scan the same, and then the select sample’s single entry is cheaper than the rank sample’s search; in a chunk whose density varies, the rank sample’s scan is shorter where the values are sparse. These sets’ long chunks are mostly uniform, a gathering in one bitmap or a near-even spread in one Elias–Fano, so the search costs about what the bound saves.

A directory indexed by count is right where the values are sparse, since a count of values there is a long stretch of bits that a scan should not cross whole; a directory indexed by position is right where they are dense, since a fixed number of bits there holds many values a search can skip. Neither alone does better than the other here, because each partition puts its long chunks in different places, and the long chunks are where the directory is used.

What the prediction got right #

The closing section predicted that on exact copies the two kinds of sample would draw the same frontier, and they do, the rank samples a little cheaper in reads and dearer in bits at each neighbouring setting. It predicted that at 0.005 and 0.01 samples by bits would read a third less at the same cost; they read 3% and 5% less, because the bound they put on the scan is paid for by a search over the samples, 15 bits a select at 0.01 and up to 34 elsewhere. It named that search as the risk, and it is the whole of the difference between a third and a twentieth. Both halves of the prediction reasoned about the scan, and the scan behaves as they said; the search is the one cost they set aside.

A third was the size of the scan’s saving alone. With a sample every 128 bits the scan inside the block at 0.01 is 57 bits, never more than 128, where a select sample’s stretch has no bound but the chunk’s density, and that part of the prediction holds; it is the search, which a select sample never pays, that takes the saving back.

The question was whether a select is better served by a directory indexed by what it asks, a rank, or by what it reads, a position. On these sets, by neither: the two directories cost a select the same, one in scanning and the other in searching, and the choice between them comes down to which offers a setting near the reads a caller can afford.

What the samples leave out #

One kind at a time. Every chunk gets samples of one kind at one spacing. A chunk could carry both, a select sample to find the right block and rank samples within it to bound the scan, which is what the next measurement asks.

A binary search over every sample. The search reads samples one at a time from the full list, the cost a position array searched by binary search also paid. A search that started from an estimate, the sample a uniform density would predict, would read fewer of them on even stretches; it was not modelled.

Uniform queries. Every value is selected once and the reads are averaged over all of them. A workload that selected some regions far more often than others would weigh the long chunks’ cost by their traffic, and might favour whichever kind of sample suits the busy chunks.

One collection. As before, 32 copies of 2,048 characters at seven divergences, and one set of marks.

Still open: a select sample that points into a rank directory #

The select sample knows which block to start from and not how far to scan; the rank sample bounds the scan and must be searched for. A two-level directory gives a select both: a select sample every $t$ values, holding not a bit position but the number of the rank block that contains its value, and rank samples every $s$ bits. A select reads its select sample by arithmetic, which names a rank block close to its target, steps forward through the rank samples until the count passes its rank, usually one or two of them, and scans at most $s$ bits.

The measurement that follows gives the long chunks that directory, with $t$ from 64 to 256 values and $s$ from 64 to 256 bits, charges both levels in the path, and draws the frontier against either kind alone. The prediction is that it reads under 70 bits a select for under 3.6 bits a value on exact copies, a point neither kind reaches, because the select sample removes the search and the rank samples bound the scan, and that at 0.01 it reads under 70 bits for about 6.2. It could fail on the price of carrying two directories in chunks that are only moderately long, where the second level’s bits cost more than the reads it removes; the path would then cut those chunks instead, and the frontier would move little. The question is whether a select’s two kinds of ignorance can each be removed by the directory built for it, or whether the cheapest directory is always one of them, chosen by where the long chunks are.