# 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`](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.