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 five 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. FRONT, which is the length of the prefix each value shares with the one before it and the rest of the value.

DICT_FSST from the section 6.2 table is not a sixth 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.

Why front coding is here

The whole file measurement in M1 says the chooser produces 11.65 GB for hits against Parquet’s 13.76 GB, and that URL, Referer and OriginalURL are 6.11 GB of it, and that on those three the chooser loses to Parquet’s Snappy. The shape it picked on all three was DICT(FSST[255]), so the cascade was working and FSST was still losing.

The reason is structural. FSST compresses each value on its own against a 255 symbol table, and a block compressor has the previous few kilobytes of the page to point back into. Two URLs that share a host and half a path are most of a back reference to each other and are nothing at all to a symbol table, which can only spend eight bytes of a symbol on the part they share and has to spend it again on every value. On a sorted dictionary of URLs the value before is the closest thing in the column to the value in hand, and the bytes they share are the redundancy Snappy was finding. Front coding is what reaches those bytes, and it composes with everything else here: the suffixes it leaves behind are a string column and go back through the chooser, so DICT(FRONT(FSST)) is a shape the chooser can arrive at without anyone naming it.

The chain has no restarts, so reading entry n means walking from entry zero. That is the right trade while a dictionary is decoded whole, which is what decode does. When something wants one entry out of a dictionary without materialising the rest, the answer is a restart every so many entries, and it costs one full value per block.

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.