# Random-access file lookup
<!-- nornir:class: reasoning -->
How znippy answers "give me the bytes of *this* path" — the question Holger
asks when it wants one artifact out of an archive of millions. There are now
**three ways to get a row**, each a different trade between open cost, memory,
and who is asking (the znippy reader, or an outside SQL engine).
## What's on disk
Every archive ends with the v0.7 multi-index footer:
```text
[ blob_0 … blob_N ]
[ data sub-index_0 ] … [ data sub-index_M ] ← one Arrow IPC stream per (pkg_type, repo)
[ lookup sub-index ] ← NEW: base columns, sorted by (relative_path, chunk_seq)
[ trie blob ] ← NEW: fst::Map<relative_path → first lookup row>
[ manifest Arrow IPC ] ← one row per section: pkg_type, repo, module_name, offset, len, row_count
[ 8-byte MAGIC "ZNPYMIDX" ][ 8-byte LE u64 manifest_offset ]
```
The base index columns (the same in every archive) are:
```text
relative_path · chunk_seq · fdata_offset · compressed
uncompressed_size · blob_offset · blob_size · checksum(32-byte blake3)
```
A file larger than `file_split_block_size` (10 MB) spans several rows — one per
chunk — sharing a `relative_path` and ordered by `chunk_seq`. To return a file
you must gather *all* of its chunk rows, decompress each, and place it at its
`fdata_offset`.
### The lookup sub-index and trie are *reserved* manifest entries
Both new sections are registered in the ordinary manifest, but with a reserved
discriminant so no existing reader trips over them:
- `pkg_type = i8::MIN` (`RESERVED_PKG_TYPE`)
- `module_name = "__znippy_lookup__"` / `"__znippy_trie__"`
`read_znippy_manifest` filters these out and the index-merge loop skips them, so
`list`, `decompress`, the iceberg sink, and the manifest-count tests see exactly
the data sub-indexes they always did. The 16-byte footer is **unchanged** —
archives written before this layer simply lack the two entries and still open.
The **lookup sub-index** is not new data: it is the base columns of the main
index *re-sorted by `(relative_path, chunk_seq)`* and stripped of plugin columns.
Sorting buys two things at once — a file's chunks become contiguous, and paths
land in byte-lexicographic order (which is exactly what `fst` requires to build).
The main index keeps its original `chunk_seq` write order, so **Law 3
(deterministic checksums bound to `chunk_seq`) is untouched** — the lookup is a
second, sorted *copy* of the locating columns, never a reordering of the source.
The **trie** is an `fst::Map` from `relative_path` to the index of that file's
first row in the (sorted) lookup. Exact lookup is O(key length); because the keys
are stored sorted, prefix/range scans (`com/google/…`) fall out for free.
## The three ways to get a row
### 1. `ZnippyArchive::open` + `extract_file` — eager full-index map
`znippy-common/src/archive.rs`. `open()` reads the **whole** index and builds a
`HashMap<String, FileEntry>` up front. After that, every `extract_file` /
`contains` / `file_size` is O(1).
- **Cost:** O(n) parse + O(n) memory *per open*; O(1) per lookup thereafter.
- **Use when:** you hold one archive open and pull many files from it.
### 2. `get_file` / `znippy get` — lean, no full-index load
`znippy-common/src/decompress.rs::get_file` → `index.rs::locate_file`. This never
materializes the whole index. It resolves one path through a **three-tier
fallback**, fastest first:
1. **trie** (`fst::Map`) → first lookup row — **O(key length)**.
2. **binary search** of the sorted lookup's `relative_path` column — **O(log n)**
(used when the trie section is absent).
3. **linear scan** of the merged main index — **O(n)** (only for archives written
before the lookup layer existed — full backward compatibility).
Having found one matching row, it expands to the contiguous run sharing that path
(the sort guarantees they're adjacent), then for each chunk: `pread` the blob,
`decompress_into` (or take the raw bytes on the skip path), **blake3-verify
against the per-chunk checksum**, and copy into the output at `fdata_offset`.
- **Cost:** O(key)/O(log n) to locate + O(chunks) to reassemble; minimal memory.
- **Use when:** you want one (or a few) files — "Holger asks for a path." This is
the path behind the CLI:
```bash
znippy get -i archive.znippy -p com/google/guava/guava/33.2.0/guava-33.2.0.jar -o guava.jar
znippy get -i archive.znippy -p pom.xml # no -o ⇒ bytes to stdout
```
### 3. External SQL over the lookup sub-index — no znippy at all
The lookup sub-index is a valid Arrow IPC stream sorted by `relative_path`. Slice
it out by the manifest's `index_offset` / `index_len` and hand the bytes to
DuckDB / Polars / DataFusion:
```sql
SELECT blob_offset, blob_size, uncompressed_size, compressed, chunk_seq, checksum
FROM '<lookup-slice>.arrow'
WHERE relative_path = 'com/google/guava/guava/33.2.0/guava-33.2.0.jar'
ORDER BY chunk_seq;
```
- **Cost:** whatever the engine does over a sorted Arrow column (≈ O(log n) with a
predicate pushdown); **zero znippy code**.
- **Use when:** an analytics tool, not the znippy reader, is the consumer — the
reason the index was Arrow-native in the first place.
## Browsing metadata, not bytes — `get_all_files_meta`
The three ways above each return *bytes*. Holger (and other consumers) often want
the opposite: the **list of artifacts** and their sizes, without reading any file
data — to render a tree, total a subtree, or decide what to fetch next. Two
library calls cover that, both reading only the lookup sub-index:
```rust
// Every file, one slim row each, sorted by relative_path.
let all: Vec<ArtifactMeta> = znippy_common::get_all_files_meta(&archive)?;
// …or just a subtree — "maybe you don't want all files".
let sub = znippy_common::get_files_meta_with_prefix(&archive, "com/google/guava/")?;
```
```rust
pub struct ArtifactMeta {
pub relative_path: String,
pub uncompressed_size: u64, // summed across the file's chunks
pub chunk_count: u32,
pub compressed: bool, // false on the stored-raw skip path
}
```
The prefix form is where the **trie earns its keep a second time**: an `fst::Map`
is an ordered set, so `map.range().ge(prefix)` seeks straight to the first key
≥ the prefix in O(prefix length), and matching files — being sorted — form one
contiguous run that we walk until a key stops matching. No full scan, no bytes
read. The fallbacks mirror `get_file`: no trie ⇒ binary-search the sorted lookup
for the prefix's lower bound; no lookup layer ⇒ aggregate the legacy main index
into per-file rows. Each file's chunks are aggregated into one `ArtifactMeta`
(sizes summed, `compressed` OR-ed), so the result is a clean per-artifact listing
rather than per-chunk rows.
This is the cheap browse primitive behind "show me what's under this group/path"
— the same access shape as way **3** (external SQL `SELECT … WHERE relative_path
LIKE 'prefix%'`), but in-process and without an analytics engine.
## Why both a sorted table *and* a trie?
They serve different readers and that's the point of carrying both. The sorted
Arrow table is what an *outside* engine can query (DuckDB can't read an `fst`
blob); the trie is what the *native* reader uses to skip the binary search
entirely and to answer prefix queries. Same rows, two access shapes, built once
in `meta_sink.rs::write_lookup_and_trie` during finalize.