Module integer 

The single column integer encodings and the cascade over them.

spec/06-compression.md section 6.2 lists the encoding set and section 6.3 says the ratios are in the cascade rather than in any one encoding. This module is both: the six candidate shapes for an integer column, each of which encodes its own output by calling back into the chooser, so that RLE over a dictionary over a bit packed code array is a thing that happens by construction rather than a case somebody wrote out.

Everything here works on i64. A narrower column is widened on the way in and nothing is lost by it, because every encoding’s size comes from the range of the values rather than from the declared width of the type: a SMALLINT column of values 100 to 130 packs to 5 bits whether it arrived as i16 or as i64. The one place the widening would cost something is a raw copy, and there is no raw copy, because a bit packed unit at width 64 is exactly that and the chooser reaches it on its own when nothing else fits.

The unit

Bit packing is per 1024 values, per crate::bitpack. Everything else is per chunk, where a chunk is however many values the caller passes in and is meant to be a row group. The two granularities are the point rather than an accident. A frame of reference base that is chosen per 1024 values tracks a column that drifts, which is what a timestamp column and an autoincrementing key both do, and one base per row group would pay the whole range of the row group on every value. A dictionary, on the other hand, is worth more the larger the unit it covers, which is the argument section 6.5 takes all the way to a dictionary per table.

The serialized form

A chunk is a tag byte, a value count, and a body whose shape depends on the tag. Bodies that contain another array of integers contain a whole chunk, tag and all, which is what makes the decoder a fold and what makes the cascade free: nothing in Rle knows what its run lengths are encoded as. The header is fixed width little endian rather than a varint, because 5 bytes per chunk against a chunk that holds a row group is not worth the branch on the decode path.

What the chooser does, and what it will have to do instead

It encodes every candidate and keeps the smallest. That is the honest baseline for M1, which is a measurement of what the format can do rather than of how fast a writer can decide, and it is not what a write path can afford. Section 6.3 describes the real thing: evaluate the candidates on a systematic sample, not the first N rows, because column data is frequently clustered and the first 1024 rows of a sorted column look constant. Building that first would mean the numbers this milestone produces are the sampler’s numbers rather than the format’s, and there would be no way to tell how much the sampler is leaving behind.

Enums

Kind

What a chunk is encoded as. The discriminant is the tag byte in the serialized form and is part of the format, so the numbers are written down rather than left to the compiler.

Functions

candidate_sizes

The size in bytes of every candidate, for a report that wants to say what the cascade was chosen over rather than only what it chose. A candidate that does not apply is absent.

decode

Decodes a chunk written by encode.

decode_prefix

Decodes a chunk that sits at the front of a longer buffer, and says how many bytes it took.

describe

The cascade a chunk was encoded as, as a line of text like DICT(PACKED, PACKED).

describe_prefix

describe over a chunk at the front of a longer buffer, and how many bytes it took.

encode

Encodes a chunk of integers, choosing the cascade that comes out smallest.