Bit vectors and rank/select

How do rank and select restore addressing in compact data, and why is every null skip a rank?

This is the mathematical core of the article, and the reason everything else in it works.

The two primitives

• rank(i) = the number of 1 bits before position i.
• select(k) = the position of the k-th 1 bit.

They look like puzzle operations. They are in fact the address-translation layer for compact data.

Here is why. In a fixed-width array, the location of element i is i × width. That is arithmetic: free, no metadata. The moment the layout stops being fixed-width, the arithmetic breaks and you need a directory. The classical directory is an array of offsets, 32 or 64 bits per element, which for short values costs more than the data. Rank/select is the cheap alternative: mark the structure in a bit vector, and recover addressing with o(n) extra bits.

Small example. Bit vector 1 0 1 1 0 0 1 (positions 0 to 6). rank(4) = the number of 1s before position 4 = 3 (at positions 0, 2 and 3). select(3) = the position of the 3rd 1 = 3. Now suppose bit i says "element i is present" and the present elements are stored packed, one after another, with no gaps. Then the packed index of the next present element at or after position 4 is rank(4) = 3, because three present elements come before it. This is exactly how null values are skipped in a column.

Constant-time rank in o(n) extra space, derived

• Store a cumulative count every log²n bits. There are n/log²n such superblocks, each count log n bits, so n/log n bits in total.
• Inside each superblock, store a superblock-relative count every log n bits. There are n/log n blocks, each count log log n bits.
• Within a block, count the remaining bits directly.

Total overhead o(n); a query is three lookups. In practice, engineered layouts use 256-bit or 512-bit blocks with 64-bit cumulative counters. They land between 3% and 25% overhead depending on how carefully the directory is packed, at a cost of roughly one extra cache line per rank.

The enabling mechanism is a hardware instruction, and the dates matter. Jacobson established succinct rank/select in 1989. It became practical when the POPCNT instruction shipped in 2008: counting the set bits in a word went from a loop or a lookup table to one instruction. This is a clean case for classifying claims: the theory was a permanent result from 1989, and the practice was economically contingent on a 2008 CPU feature. Select is the harder of the two. It had no single-instruction form until PDEP/PEXT in 2013, and those were microcoded and very slow on AMD until Zen 3. So portable libraries still implement select as a binary search over rank. Design structures that need rank. Treat needing select as a cost.

Where you already use this without knowing

• Arrow and Parquet validity bitmaps. When nulls are not stored in the values buffer, the physical offset of logical element i is rank(i) over the validity bitmap. This is almost certainly the most executed rank operation in the industry. It deserves a name and not just an implication.
• Variable-length string columns. Instead of a 32-bit offset per string, mark string starts in a bit vector and use select. For short strings this is a large saving.

The structural law this generalizes. The Immutability law (a layout that cannot update in place grows an indirection layer plus a collector) turns out to be a special case of something broader:

This strengthens the law instead of adding another one. It now covers four mechanisms instead of one, and it predicts something the original did not: a compact-but-not-relocating structure should have a directory and no garbage collection, which is exactly what rank/select is.