Beagle SCM

LITE-028 DONE: index catch-up is O(history) — readState full-scans the lane per new commit

After one git commit in a linux-sized repo, the next lite verb (any link click) stalls ~10 seconds "doing index update" for a one-file change. The tree-diff pruning is INNOCENT — descend/diffMap (DOG-030) is O(changed) as designed. The cost is readState (index/index.js:365): whenever the tip is not marked, it makes ONE full cursor pass over the ENTIRE lane — every K_BLOB/K_CMMT/K_CPAR row ever written — to build next/byPB/top for ALL paths and done for ALL indexed commits, then indexes the single new commit. O(history) paid for O(1) of new work, every commit.

Input

Context

bringUp (index/index.js:621): O(1) mark check (markSet, tip marked = no-op), else readState full pass, collect walk (stops at done, fine), per-commit descend (pruned, fine), emit consuming st.next/byPB/top. The 2026-08-13 no-ceiling ruling made PRESENCE the walk boundary; the full arrival-state pass rode along and was invisible on be-sized repos — linux exposes it.

• The state actually needed per run: done probes for the walked commits' parents (O(new × parents)), and next/top/byPB for ONLY the paths the new commits touch.
• The lane is SEEKABLE by key (hlKey); markSet already does a keyed seek — the full pass is a convenience, not a necessity.
• KNOWN TRAP kept: range/prefix return zero rows at the 2^64 bound; keyed passes must ride the seek cursor (index/index.js:350).

Goals

Post-commit catch-up cost proportional to the NEW work, exact same rows written.

• done membership: a K_CPAR seek per probed commit inside collect, no materialized set.
• next/byPB/top: after descend names a commit's changed paths, keyed per-phl seeks fill the state for just those paths (memoized across the run's commits).
• Full-scan readState may remain as the fallback for a big backlog (first index, long absence) — pick by walked-set size or keep the seeks unconditional if they win there too; measure.
• Interrupted-run semantics unchanged: presence boundary, CPAR-last, top re-put guard must hold row-for-row.

Constraints

• ///lite worktree, index/index.js (+ tests) only; no VC ops.
• Repro first: a fixture (or a cloned big history) timed — one new commit must not re-read the lane; assert rows written identical to today's.
• Full-suite failure counts identical to the pristine baseline; the golden fault-injection legs (_faultMid) stay green.

WIP

Design decisions

• done is a keyed CPAR seek per PROBED commit, memoized both ways (hit and miss) for the run; the walk probes O(new × parents) commits.
• next/byPB/top are filled per PATH: a path's REV rows are the key span [phl<<24, (phl+1)<<24), so ONE seek off the top of the span fills the state for it. Other kinds hash into the span, so it is filtered by KIND, never cut short by one. Memoized per path_hl for the run.
• The full pass is DELETED, not kept behind a threshold. A seek-count threshold that buys the pass loses on both ends (numbers in Outcome): it costs a full-lane read for a backlog on a big lane — the very bug — and it is not needed for the from-scratch derive, which is not a threshold case at all but an EMPTY lane: one row read says so, and then the run seeks for nothing, because every row it will ever read is its own.

TODOs

• repro: big lane + 1 commit, time and row-count baseline
• done as keyed CPAR probes in collect
• lazy per-path next/byPB/top seeks in emit's path
• backlog fallback ruling: threshold or unconditional; measure both
• fault-injection legs re-verified (mid-commit seal, re-walk to NOTHING)

Blockers and bummers

• The installed jab has no git.getTreeDiff (pre-DOG-030), so the whole lite suite must run with LITEJAB=~/tmp/l25/qjb/bin/quickjab; under plain jab half of it fails for that reason alone.

Outcome

readState's full pass is gone: state() + hasDone() + loadPath() read the lane BY KEY, emit loads a path on first use, an empty lane is settled by one row read. ///lite wt work/LITE-028, staged, not committed.

Measured with the counting shim (test/index/lazy.js), runtime quickjab, rows READ off the lane / wall ms, synthetic fixtures in ~/tmp/lite028:

So the catch-up is 87× cheaper at 200k commits and gets cheaper the bigger the history is (the 1.3M-commit ~/src/linux extrapolates to 6.5M rows read, the reported 10 s). What the catch-up DOES read is the touched file's own rev chain, not the repo's history.

Backlog fallback, both costs (30,201-commit derive; 5000-commit backlog on a 125k-row lane): with a 4096-keyed-seek threshold that buys the full pass, 2813 ms and 1399 ms / 130,109 reads; unconditional seeks, 2687 ms and 1153 ms / 80,609 reads. The threshold loses on both and its cost is UNBOUNDED on a big lane (a 4096-commit pull on linux would read all 6.5M rows again), so it is not in the code. Overturn if wanted — it is ~15 lines.

Row identity, dumped key/val and cmp-ed against the pre-fix code over the same history: 176,007-row lane after a 5000-commit backlog and 1,000,007-row lane after a one-commit catch-up, both BYTE-IDENTICAL. Interrupted run at scale: _faultMid at commit 50 of 100 over a 176k-row lane, then resumed — 51 commits re-walked, 50 revs minted (the stranded commit re-derived to NOTHING through the lazy top guard) and the lane byte-identical to the unfaulted control.

Tests: lite/index 123 -> 129 checks, all green (leg 3 + lazy.js: the repro, the file-chain bound, dense rev chains, one rev per path per commit). The new leg is RED on the pristine tree (reads 2503/2507 and 5007/5009 = the whole lane) and GREEN here (41 and 82). Full suite failure counts identical to a pristine clone of #96b7909d: blob 12/13, cat 16/35, list 17/78, pager 1/33, tree 25/47 pre-existing, everything else PASS, resume leg 16/16 unamended.

Suggested commit: LITE-028: index catch-up reads by key, not the whole lane