Module index_layout

Expand description

One git object index, three Arrow IPC layouts, measured against each other.

§The question

A git .pack carries no index at all. Git derives several separate files from it — .idx (oid → offset), .rev (offset → length), .bitmap, .midx — and two of the four facts a server actually needs on the hot path are in none of them:

fact	where git keeps it
oid	`.idx`
byte extent (offset, len)	offset in `.idx`, length only via `.rev` or the next offset
type	nowhere — an entry-header parse per object
uncompressed size	nowhere — the same entry-header parse
delta base	nowhere — the same entry-header parse, plus a varint

§`delta_base` is an OFFSET, and the arms are named for what they were

PLAN §13 settles it: delta_base is a u64 archive offset, not a row ordinal into this table. An ordinal would be half the width and would index the very table it sits in — and it would break silently the first time the table is rebuilt in a different order, which §14 guarantees will happen because the whole index is a droppable cache. An offset is order-independent because the pack it addresses never moves; PackWalk::rebased shifts it with one addition and no table to keep in step. 0 is the sentinel for no base: archive offset 0 is a pack’s PACK magic, so no entry can start there.

It joined the schema after the three arms were named and measured, so the names now count sections and tables, which is the variable under test — not facts. FourTables is four IPC sections, OneTableFourColumns is one; both carry five payload columns today, and PackedPayload still carries one. Every ns figure quoted below was taken on the four-fact, 25-byte schema and is marked where that matters.

So cat-file --batch-check over a pack is a varint decode per object, and a have negotiation of 1000 oids is 1000 of them. Consolidating all four facts into one index is the point of this module. The open question is what shape that index should have, and this module answers it by building three shapes behind ObjectIndex and benchmarking them (examples/index_layout_bench.rs).

arm	payload columns	buffers a full-row fetch touches
`FourTables`	5, in four IPC sections	5
`OneTableFourColumns`	5, in one IPC section	5
`PackedPayload`	1, in one IPC section	1

The first two were the original experiment, and they tied at every size, batch size and hit rate. The reason is visible in the table: Arrow is columnar, so “one table with five columns” is not row-contiguous. Both arms keep offset, len, object_type, uncompressed_size and delta_base in five separate buffers whose bases are megabytes apart (measured: 1 737 664 bytes between the offset and size buffers at 100 000 rows), so a full-row fetch costs five unrelated strides either way. The number of tables was never the variable. The number of columns is — which is what the third arm changes, and it is the only one that moves the number.

§What is deliberately shared, so the measurement is of the layout

All three arms resolve oid → ordinal through the same crate::oid_index stree (LAW 5: reuse, do not twin — and a third oid index written by accident would have made the arms incomparable anyway). The two columnar arms share one ColumnarPayload holding every read path, so they cannot drift apart in the hot loop and the only thing between them is IPC framing.

§Zero-copy is asserted, not assumed

All three arms decode with StreamDecoder::with_require_alignment(true), which makes arrow error rather than silently allocate-and-copy when a buffer is misaligned. A layout that quietly copied its columns out of the IPC bytes on open would be a different (and much slower to build) thing than the one being claimed, so the reader refuses to be that thing. ObjectIndex::ipc_bytes plus each arm’s column_is_inside_ipc let a test prove each array’s data pointer actually lies inside the IPC buffer.

§Measured

oden, 32 cores, 2026-08-07, --release --no-default-features, sha1 oids, 100 000 lookups per cell, 5 runs per cell, 4 sizes × 3 hit rates × 7 access paths + 2 column scans. /proc/loadavg 0.96–2.98 (1-min) across the three sweeps — the first rotation started at 2.98, the other two at 1.53 and 1.35, and the reported figures are the geometric mean of all three, so no arm sat disproportionately in the busier one.

Position is cancelled by rotation: the sweep is run three times with the arm order rotated, so each arm occupies each position exactly once. This matters — in the earlier two-arm work the arm timed second was measurably 1.1% slower at N ≥ 1e6 whichever layout it was, which is enough to invent a result out of nothing.

Noise band: median 8.9% run-to-run spread, p90 32.3% over 270 cells (excluding the 1e3 scans, whose ns-per-row is below timer resolution). The p90 is carried almost entirely by the 100 000-object rows, where the index fits in L3; at 1e3 and 4e6 the bands are 2–20%. Nothing below is claimed unless it clears its own cell’s band.

§First: the harness really does read all four facts

This has to be established before any of the rest means anything. A harness that resolved the oid and threw the row away would measure the stree and nothing else, and would produce a tie no matter what the layouts did.

ObjectIndex::ordinals_batch exists for exactly this: it resolves oid → ordinal and stops, touching no payload byte, and it is the same code in all three arms. Subtracting it from the full-row path isolates the payload gather — the only part any of these layouts can change:

objects	mix	stree floor	A payload	B payload	C payload	C/B
1e3	100% hit	50.3	6.3	6.1	1.5	0.24
1e3	10% hit	39.1	5.3	5.1	1.8	0.34
1e5	50% hit	58.6	15.0	14.0	10.6	0.76
1e6	100% hit	195.8	45.0	46.2	27.7	0.60
1e6	10% hit	113.4	11.4	11.1	7.2	0.65
4e6	100% hit	247.2	39.2	43.1	29.8	0.69
4e6	50% hit	199.6	30.9	27.9	20.9	0.75
4e6	10% hit	141.3	25.1	21.7	17.7	0.81

ns per lookup, batch 1000, position-cancelled. The payload column is nowhere near zero and it differs between arms, so the facts are being read. It is 9–28% of a full-row lookup; the shared stree is the other 72–91%.

§Rickard was right: one column IS faster to fetch than four

On the part of the work the layout controls, PackedPayload cuts the payload gather by 19–76%, and by 25–40% at every size from 1e6 up. One 25-byte stride against four strides megabytes apart, exactly as predicted. The single cell that does not show it (1e5, 100% hit, C/B 1.06) sits in the noisiest regime in the sweep, band 44%.

Those cells are the four-fact schema. delta_base makes the packed record 33 bytes and gives the columnar arms a fifth stride, so the mechanism points the same way and the magnitudes are stale until re-measured. See “What the fifth column costs” below for the measurement that was actually taken after the column landed.

But the win is capped by Amdahl, and this is the honest headline: the payload gather is only 9–28% of a lookup, so a 31% cut in it is a 4–8% cut end to end. At 4e6 objects, 100% hit, position-cancelled C/B:

path	A ns	B ns	C ns	C/B	band
ordinals only (the floor)	247.2	245.1	244.6	0.998	4.9%	tie, as it must be
full row, serial `lookup`	464.8	471.8	435.2	0.922	7.7%	C faster
full row, batch 1	824.2	811.9	757.4	0.933	11.4%	inside band
full row, batch 100	298.6	299.0	283.4	0.948	5.2%	C faster
full row, batch 1000	286.4	288.3	274.4	0.952	2.8%	C faster
full row, batch 10000	284.4	283.3	271.5	0.959	4.8%	inside band
extents only, batch 1000	261.5	263.0	264.2	1.005	4.0%	tie

Three of the four full-row cells clear their band; the direction is the same in all seven and at every size. At 1e3 the win is larger and cleaner (C/B 0.898–0.931 at batch ≥ 100, bands 1.8–2.8%) because there the stree floor is small enough not to swamp it.

extents is a tie, and that is the mechanism confirming itself. A partial-row fetch of two facts lets the columnar arms read two columns instead of four, while the packed arm reads the same 25 bytes it always reads. The advantage is exactly proportional to how much of the row you want, and at half a row it is gone.

§What the fifth column costs

Footprint: exactly 8 bytes per object, in every arm. This is arithmetic, not an estimate, and the byte-exact guards below hold it there: the packed record goes 25 → 33 B, and each columnar arm gains one u64 buffer of 8n bytes. 800 kB per 100 000 objects; 32 MB at 4e6. The only relative change between arms is that PackedPayload now saves four per-column IPC buffers instead of three — MEASURED 50 560 B at 100 000 rows against the 38 016 B it saved before (the_packed_arm_holds_the_same_payload_but_a_smaller_section, which asserts the scaling law rather than the constant).

Latency: NOT re-measured, and no claim is made. Two reasons, and the second is the one that will still be true tomorrow.

Load was the first: the harness refuses above 1-minute load 4.0 and oden was carrying another agent’s build at 9–26 for most of this change. That one cleared on its own (it fell to 2.1), so it is not the reason this is still unmeasured.

A before/after of a znippy change cannot be built in this tree, and that is structural. A before/after needs the old and the new source resolved at the same time, which needs two znippy checkouts, and there is nowhere to put the second one — MEASURED by trying all three placements:

where the second checkout goes	what happens
anywhere under `/home/rickard/git`	`package collision in the lockfile: znippy-common v0.9.13 (…/znippy-pre-deltabase) and znippy-common v0.9.13 (…/znippy) are different`
anywhere outside it	`failed to read …/znippy-zoomies/lbzip2/Cargo.toml`

The cycle is the cause, not the placement: znippy’s xtask and tests depend on ../../nornir, and nornir depends back on ../znippy/znippy-common — an absolute reference to the canonical checkout. So a second checkout drags the canonical one into its own resolve and two different copies of one version land in one lockfile. Move it out of /home/rickard/git to escape that and it loses the ../../znippy-zoomies/… path dependencies instead. Symlinking the siblings back does not help: cargo canonicalises, so nornir resolves to the real one and points at the real znippy again.

Anyone wanting this number should therefore plan on one checkout, timed twice — build the bench, git checkout the other revision of these files in place, build again — and should not spend the hour discovering the above. That mutates a shared checkout for as long as it takes to compile, which is why it was not done here while another agent was working in this crate.

What can be said without measuring, and is deliberately weaker than a number: the payload gather is 9–28% of a lookup, a columnar full-row fetch goes from four strides to five, and the packed record goes from ~1.4 cache lines to ~1.5. Both arms get slightly worse and the packed arm’s relative advantage on full-row fetches should narrow a little. An 8-byte-per-row effect is in any case inside the 8.9% median / 32.3% p90 band this sweep already reports, so the honest expectation is a null result rather than a regression. Re-run examples/index_layout_bench.rs on a quiet box before quoting any of the ns tables above as current.

§…and it loses the scans, by a lot

ns per row, full column scan, position-cancelled:

objects	scan	A	B	C	C/B
4e6	`sum_uncompressed` (uses 8 B of every row)	0.36	0.36	1.19	3.3×
4e6	`count_type` (uses 1 B of every row)	0.09	0.09	1.32	14.4×
1e6	`count_type`	0.09	0.09	1.27	14.0×
1e5	`count_type`	0.09	0.09	0.51	5.5×

The 4e6 rows clear their bands (4.5% and 34.7%) with room to spare, and the direction is identical at every size. This is the trade stated in PackedPayload’s docs, landing exactly where predicted: count_type drags 25 bytes through cache to use one, so it pays ~14× for the privilege of the 5% it won on full-row fetches. A quota gate or a type histogram over a 4-million-object repository is 5 ms on the columnar arms and 5 ms × 3–14 on this one.

§The other figures

	FourTables	OneTableFourColumns	PackedPayload
resident (IPC + stree), 4e6	326.635 MiB	326.634 MiB	325.203 MiB
build, 4e6 objects	3.956 s	4.052 s	3.975 s

A vs B is still a tie, now confirmed with a harness that provably reads the payload: A/B ranges 0.96–1.06 and every cell is inside its band. Four sections cost exactly 1048 bytes more than one, constant at every size — the framing of three extra IPC streams, 0.0003% at 4e6.
PackedPayload is the smallest on disk, by three per-column IPC buffers: 38 016 B at 100 000 rows, 75 456 B at 200 000, i.e. 3 · n/8. Its payload is byte-identical (25 = 8 + 8 + 1 + 8).
Build is a tie across all three — within 2.5% at 4e6, inside the band. Build is the oid sort and the stree, not the framing or the packing.

§What this means for the shape of the index

Neither the packed arm nor the columnar ones is right everywhere, and the measurement says which is which rather than leaving it to taste:

The negotiation path (want/have, full row) is 5% faster packed, and the ceiling on that is the stree, not the payload — the next real win on that path is in the oid step, not here.
The wire path (extents) is indifferent.
Analytics (quota gates, type histograms) are 3–14× slower packed.
The packed arm gives up being four typed Arrow columns. A FixedSizeBinary(25) is opaque to DuckDB / Polars / DataFusion, which can query the other two arms straight off the IPC bytes with no consumer code. That is a real cost and it is not a performance one.

§The stree header was the next experiment, and it was a negative result

What this sweep can say, which the two-arm version could not, is that the oid step is where the remaining time is: the ordinals_batch floor is 72–91% of every full-row lookup, and it is identical in all three arms. The floor itself grows 39 ns → 247 ns from 1e3 to 4e6 objects, which is cache and TLB behaviour in the stree, not in any payload column.

That pointed at oid_index’s 24-byte header (24 mod 64 = 24, so the key array is off-line by construction). It has now been built and measured — crate::oid_index::OidLayout and examples/oid_align_bench.rs, three arms separating the header offset from the allocator. A 64-aligned keyspace takes 5.2% off cache-misses, reproducibly, and does not move the clock at all: 0 of 24 cells clear their band, and 0 of 6 clear it again at 4e6 with the band tightened to 5%. The header is not where the oid step’s time is, and the reason is instructive — stree’s internal nodes live in the tree’s own Vec, not in this section, so the header could only ever move the leaf touch, and the pipelined batch walk was already hiding it. The full numbers and the mechanism are in crate::oid_index.

Structs§

Columns: The six Arrow arrays that carry the five facts, in oid-lexicographic order. The byte extent is one fact in two columns because that is what it is — (offset, len) — and splitting it lets a scan of just the offsets stay contiguous.
FourTables: Four Arrow IPC sections — oid, byte extent, type, size — joined by row ordinal.
IndexEntry: One object, as the caller hands it to ObjectIndex::build. Order is irrelevant — every implementation sorts by oid and derives ordinals itself.
IndexRow: What a lookup resolves to: the ordinal plus all five facts.
OidResolver: The stree oid keyspace, shared verbatim by both arms.
OneTableFourColumns: One Arrow IPC section, one table, the facts one column each.
PackedPayload: One payload column: all five facts of one object packed adjacently into a single FixedSizeBinary(33) element.
Rng: splitmix64. Seeded, so a bench run is reproducible and a historized series is comparable at all.

Enums§

ObjType: Object type, in git’s own pack entry encoding.

Constants§

COL_DELTA_BASE
COL_LEN
COL_OFFSET
COL_OID: Column names, one place, so the two arms cannot drift apart on spelling.
COL_PACKED: Column name of the single packed payload column.
COL_SIZE
COL_TYPE
PACKED_LEN: The five facts of one object, packed little-endian into PACKED_LEN bytes.

Traits§

ObjectIndex: A git object index over Apache Arrow IPC.

Functions§

columns: Materialise the five arrays from entries in order.
oid_column: The oid column alone. Every arm stores it, and no arm packs it into the payload: the oid is the key the stree resolves against, not one of the facts a resolved lookup fetches, so putting it next to the payload would widen every payload read for a field nobody reads at lookup time.
packed_column: One FixedSizeBinary(PACKED_LEN) element per object, in order.
synthetic_entries: n distinct entries with uniformly random oids.