.nornir/random-access.md

Random-access file lookup

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:

[ 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:

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:

trie (fst::Map) → first lookup row — O(key length).
binary search of the sorted lookup's relative_path column — O(log n) (used when the trie section is absent).
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:

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:

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:

// 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/")?;

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.