Module string 

The string column, which is offsets, bytes, and the choice between compressing the bytes and not storing most of them at all.

ClickBench hits is a string dataset before it is anything else. URL, Referer, Title and the referer derived columns are most of the 20.46 GB DuckDB writes for it, so most of what spec/02-the-goal.md promises on the resource axis has to come out of this file.

The four shapes

CONSTANT when every value is the same. PLAIN, which is lengths and raw bytes and is the baseline the others have to beat. FSST, which is a symbol table and the same lengths over compressed bytes. DICT, which is the distinct values and an array of codes.

DICT_FSST from the section 6.2 table is not a fifth shape. A dictionary’s entries are a string column, and encoding them goes back through the same chooser, so a dictionary whose entries are FSST compressed is what the chooser produces on its own whenever that is smaller. The same recursion gives run length encoding of strings for free, because the codes are an integer chunk and crate::integer already knows what to do with a column of long runs.

Lengths, not offsets

The usual layout is n + 1 offsets and Arrow does it that way because a slice of an array has to be free. On disk the offsets are a monotonically increasing sequence whose differences are the lengths, and the differences are what compress: URL lengths in a real column are a few dozen distinct values in a narrow band, which the integer cascade turns into a handful of bits each, while the offsets themselves need enough bits to address the whole chunk. The integer cascade would find that by choosing DELTA, and storing lengths directly gets to the same place without spending a level of the cascade on it. Offsets are a prefix sum away and that is a decode time cost of one add per value.

What is not here

Nulls. A chunk here is N byte strings and an empty string is a value like any other. Validity is a bitmap that belongs to the column rather than to the encoding, per spec/05-storage.md, and ROARING in the section 6.2 table is what encodes it.

Shared symbol tables and shared dictionaries across columns, which are section 6.4 and are the measurement this milestone exists for. Everything here is one column on its own, which is the baseline they get compared against.

Enums

Kind

What a string chunk is encoded as. The discriminant is the tag byte and is part of the format.

Functions

candidate_sizes

The size of every candidate that applies, for a report that wants to say what was chosen over what.

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 shape a chunk was encoded as, as a line of text like DICT(FSST, RLE(...)).

describe_prefix

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

encode

Encodes a chunk of strings, choosing whatever comes out smallest.