Repository navigation
PagedChunkVectorStorage pages with OFFSET: sec ask is 7.3× slower at 400k chunks than the unbounded read it replaced #365
Description
PagedChunkVectorStorage.similaritySearch pages kb_chunk with ORDER BY chunk_id ASC LIMIT 512 OFFSET n. SQLite walks and discards the first n rows of every page, so reading the table a page at a time is O(N²/page) — the memory bound was bought with a super-linear time cost, and sec ask scores every chunk on every question, so every question pays it.
Measured on a real SQLite kb_chunk (64-dimension vectors, 512-row pages), scanning the whole table the way one question does:
rows OFFSET paging keyset paging unbounded (the old behaviour)
50,000 566 ms 189 ms 214 ms
100,000 1,885 ms 791 ms 383 ms
200,000 6,040 ms 993 ms 651 ms
400,000 21,482 ms 3,083 ms 2,925 ms
Correction (2026-09-15): re-measured on a real SQLite file with the vector width recorded, the magnitude is 3.3× / +4.6 s at 400k, not 7.3× / +18.6 s. The superlinearity and the fix are unchanged; the magnitude is row-width and machine dependent.
Both forms issue the same 782 statements; only the work per statement differs. The ordering is already the primary key, which is exactly the column a keyset cursor needs, so the memory bound did not have to cost anything.
Fix: replace offset with a WHERE chunk_id > ? predicate.
Activity
sroussey commentedon Sep 15, 2026
Fixed on
claude/admiring-lovelace-59uare—ba0b58c2(keyset paging) ande58b2b1f(thetoVectornote below). No PR opened.What changed
src/kb/PagedChunkVectorStorage.ts:96-119— thefor (let offset = 0; ; offset += SCAN_PAGE)loop overgetAll({ limit, offset })is now a cursor loop over the inheritedgetPage:ITabularStoragehas grown the operator the issue was missing, and more:getPageon a SQL backend pushes the whole keyset predicate down (BaseSqlTabularStorage.runSqlPage/buildKeysetWhere), so noprepareagainst the raw handle was needed. It also handles the two traps for free —ChunkVectorPrimaryKeyis["chunk_id"], a single column, so the predicate is one inequality rather than a row-value comparison, and the cursor is refused outright if the ordering it was built under stops matching. The memory bound is unchanged: one page of rows plus thetopKlist.--dry-runis untouched — nothing on this path writes.The loop ends on an empty page as well as on an absent cursor. A table whose size is an exact multiple of 512 hands back a cursor for its last full page (nothing about that page says it was the last), and following the cursor alone never terminates.
Measured
Rerun from scratch rather than quoting the table above — same shape, smaller absolute numbers. Real SQLite file (WAL),
kb_chunkviaSqliteVectorStorage, 64-dimension vectors, 512-row pages,topK5, one whole-table scan per measurement, page cache warmed identically before each. Node 24.20.0 / Bun 1.4.2. The keyset column is the shippedPagedChunkVectorStorage.similaritySearch, not a hand-rolled loop; all three arms are asserted to return the identical ranking at every size.Two earlier runs of the same benchmark agreed within ~5% (400k: offset 7,042 / 7,019 ms, keyset 2,062 / 2,109 ms).
The superlinearity reproduces: 200k→400k costs OFFSET 3.1× where keyset costs 2.0×. The absolute regression I measured is 3.3× the unbounded read at 400k (+4.6 s per question) rather than the 7.3× / +18.6 s in the report — my vectors are 64-dimension where the original probe's width is not stated, and a narrower row makes the per-page re-walk cheaper relative to the scoring. Direction, exponent and fix are the same; the magnitude is machine- and row-width-dependent.
Plans, verbatim:
SCANvsSEARCHis the whole difference: the OFFSET form re-enters the index at the start each page and discards its way forward.Tests
src/kb/secKnowledgeBaseSearch.test.ts, four cases, withSCAN_PAGEnow exported so a corpus can be seeded at an exact page boundary rather than at a number that happens to cross one:seeks to the last key seen rather than counting rows past— pins the statement count at exactly 3 for a2·SCAN_PAGE + 5corpus, asserts no read carriesOFFSET, and asserts every read after the first carries`chunk_id` >. This is the regression test the issue asked for, and I confirmed it fails on the OFFSET implementation:AssertionError: expected 'SELECT * FROM \kb_chunk` ORDER BY `chunk_id` ASC LIMIT ? OFFSET ?' not to match /OFFSET/i`.terminates on a corpus that is an exact multiple of the page—2·SCAN_PAGErows, ranking correct, exactly 3 reads (two full pages plus the empty one that ends it).ranks an empty index without reading a page twice— one read, no second.SCAN_PAGE.The two smaller things
toVector— addressed as you suggested, with a comment rather than a behaviour change (e58b2b1f). It now says thatFloat32Arrayand thevector/metadataproperty names are restated because the base holds all three in private fields with no accessor, that they are right for the oneChunkVectorStorageSchemastoregetSecKnowledgeBasebuilds and silently wrong for any other, and that widening the class means reading them off the base rather than restating them. The protected accessor upstream is a@workglow/storagechange and is not in this branch.Verification
bun run format-checkbun run lintbun run typecheckbun run buildbunx vitest run src/kbbunx vitest run(full suite)No timeouts and no load-sensitive failures in the
verifytier on this run.Generated by Claude Code
sroussey commentedon Sep 21, 2026
Fixed by
31d72bdd("perf(kb): page kb_chunk by key rather than by offset (#373)"). Verified by execution atd544bc64, not by reading the diff.1. The shipped class no longer emits an
OFFSET. Driving the realPagedChunkVectorStorageagainst a realnode:sqlitefile (1,543 rows = 3 full pages + 7,SCAN_PAGE = 512), recording every statement it prepares and takingEXPLAIN QUERY PLANof each:SCAN … USING INDEX→SEARCH … USING INDEX (chunk_id>?)is exactly the plan change the commit claims, and the ranking is unchanged: the three best chunks are seeded LAST inchunk_idorder, so only a scan that reaches the end finds them.2. The super-linearity is gone, and the memory bound is now free. Three arms over a real SQLite file (64-dimension JSON vectors, 512-row pages, cosine per row, top-3 kept), all three asserted to return identical rankings, two independent runs:
200k → 400k costs OFFSET 3.4× and keyset 1.1×. At 400k chunks the fix removes ~6.2–8.2 s per question, and the paged read is now faster than the unbounded read it replaced (1.26 s vs 1.93 s) rather than 3.3× slower — so the heap ceiling is removed at no time cost at all, which is what this issue asked for.
3. The termination case is real and is pinned.
31d72bddbreaks onnextCursor === undefinedor an empty page, with a comment saying why: a table whose size is an exact multiple of the page hands back a cursor for its last full page, and following the cursor alone never ends.secKnowledgeBaseSearch.test.tsseedsSCAN_PAGE * 2and asserts exactly three chunk reads.SCAN_PAGEis now exported so the tests seed a real page boundary rather than a number that happens to cross one.Gates at
d544bc64:format-check0,lint0,typecheck0,build0.bunx vitest run src/kb src/task/kb src/cli/groups→ 9 files / 55 tests passed.One residual, split out rather than left here: in the fully-indexed steady state
sec askstill traverses all offiling_documenton every question, and the new(filing_date, accession_number)index is a wash-to-worse in exactly that regime. Filed separately.Closing as completed.
Generated by Claude Code