nordisk/znippy

znippy index — reasoning

Class: reasoning. This file holds the why, the trade-offs, and every design we rejected. The descriptive shape we actually run is in index-design.md, which by rule mentions none of this. If you want to know "why not X?" — X is here.

f0 — why a seekable footer at all

The whole point of znippy is O(key) per-file seeks on a content-addressed store. The naive compressor gives you one thing: decompress the whole archive. We wanted "Holger asks for one path, and we read only that file's blobs" — plus "an analyst queries the layout without running znippy." Both demands land on the same answer: publish the file→location map inside the archive, in a format others can read, sorted so a single file is a point lookup. Everything below defends that footer while keeping determinism (Law 3) and back-compat intact.

Why BOTH a sorted Arrow table AND an fst trie

They serve different readers, and neither can do the other's job:

• DuckDB / Polars / DataFusion can't read an fst blob — but they can read an Arrow IPC stream. So we ship the lookup as a sorted Arrow table: the index becomes a SQL surface with zero znippy code.
• The native reader wants two things an Arrow table gives grudgingly: (a) skip the binary search entirely — the trie maps relative_path → first lookup row in O(key); (b) answer prefix queries — map.range().ge(prefix) seeks a subtree in O(prefix len). A sorted column alone gives O(log n) exact lookups and no cheap prefix seek.

Same rows, two access shapes. The trie is a fast index over the sorted table, not a replacement — when the trie is absent (older archive) the reader falls back to binary search of the same sorted column, then to a linear scan. We pay one extra fst blob to buy both a tool-free query surface and O(key) native seeks.

Why a second sorted COPY, not reordering the main index

The obvious space-saver is to sort the main index in place and drop the copy. Rejected — it breaks Law 3. Every chunk's blake3 checksum is bound to its chunk_seq in original write order; decompress verifies against that binding to stay deterministic and core-count-independent. Reorder the rows and chunk_seq no longer matches the write order the checksums were computed against — the deterministic-restore guarantee collapses. So the main index keeps its write order, and the lookup is a separate, derived, sorted copy with plugin columns stripped. We spend the disk for the second copy to keep restore provably deterministic.

Why reserved manifest discriminants, not a new footer version

The lookup and trie could announce themselves with a bumped footer version. Rejected for back-compat. Instead they register as ordinary manifest entries under reserved discriminants: pkg_type = i8::MIN (RESERVED_PKG_TYPE) with module_name = "__znippy_lookup__" / "__znippy_trie__", and read_znippy_manifest filters them out of the data view. The payoff: the 16-byte footer (MAGIC + manifest_offset) is unchanged, and an old reader that never heard of a lookup simply skips the reserved sections as unknown — archives written before this layer still open, and archives written after still open in old tools. A version bump would have forced a hard cutover; reserved discriminants make the new layer purely additive.

Rejected: a single index reordered in place

Covered above but worth stating as its own rejection: one index, sorted by (relative_path, chunk_seq), no second copy. Minimal disk, one structure to maintain. Rejected because it moves rows out of chunk_seq write order and breaks the deterministic checksums (Law 3). Determinism is non-negotiable — it's what makes decompress core-count-independent — so the copy stays.

Rejected: a bespoke on-disk B-tree instead of Arrow

We could have written our own B-tree (or a custom trie-only format) as the index and skipped Arrow entirely — tighter, purpose-built. Rejected: it loses the "query without the tool" property. An Arrow IPC lookup is readable by DuckDB, Polars, and DataFusion out of the box; a bespoke B-tree is readable only by code we write and maintain forever. The whole reason the lookup is Arrow is that the ecosystem already speaks it. So the on-disk query structure is Arrow, and the fst trie rides alongside it as the native fast path.

The cold-read cost we knowingly pay

The design isn't free: a cold locate_file re-decodes the whole lookup, so per-call latency grows ~linearly with N. For occasional single seeks that's fine; for a workload of many independent single-file reads on a huge archive it's the wrong shape (use ZnippyArchive::open, which parses once and amortizes). The clean fix — a cached reader that decodes the lookup once and holds the trie resident across calls — is deliberately future work: it's an optimization over the current design, not a change to the footer, so it can land without touching on-disk compatibility.