performance: every change page restarts its comparison (re-plan, re-resolve endpoints, re-sort keys) #970

Activity

1. github-actions

   added

   needs-triageAwaiting maintainer triageAwaiting maintainer triage

   on Oct 13, 2026
2. ragnorc commented on Oct 19, 2026

   

   ragnorc

   on Oct 19, 2026 – with Cursor

   ContributorAuthor

   More actions

   Summary

   Each continuation page of a change comparison starts the comparison again. The page re-plans every changed interval, resolves both endpoint commits again, and restarts the ordered walk with an id > last filter. Lance then sorts the remaining keys. A result of P pages repeats the catalog work P times, and it repeats most of the sort.

   This is on commit changes, on a change-feed page that stops inside one commit, and on a graph diff page. It is the same on local disk and on an object store, and for HTTP, CLI, MCP, and embedded callers.

   Reproduction

   Reproduced on main 9e2425d26a03b1b5628030a359ee51f096d3ca1c (still origin/main at the time of this comment). The functions the issue cites are still at those lines: plan_intervals in crates/omnigraph/src/changes/enumerate.rs and the resume filter in crates/omnigraph/src/changes/row_compare.rs.

   Environment: Linux 6.12, 4 CPUs, 15 GiB RAM, rustc 1.97.1, OmniGraph 0.14.0, Lance 11.0.0 from crates.io. DST used the in-memory object store and --model s3-like. Local times used the debug binary target/debug/omnigraph (version 0.14.0), not a release build.

   Request counts

   Command:

   omnigraph-gqt /tmp/repro970/iso/p1.gqt /tmp/repro970/iso/p3.gqt /tmp/repro970/iso/p6.gqt \
     --measure --model s3-like \
     --target omnigraph-engine-dst --storage in-memory-object-store --seed 0 \
     --artifacts /tmp/repro970/artifacts-iso
   

   Shape of each case: Person { name String @key, age I32, bio String }. The bio is 32 repeats of one character. The seed loads 20,000 rows in 5 commits of 4,000. The feature branch updates 5,999 of those rows in 2 commits of 4,000, then inserts one row. Main inserts one row after the fork. One branch diff feature into main follows. Each case is its own process, so the three diffs do not share a Lance session. The stock GQT runner reads one page. The measurement binary followed every continuation page inside that one branch-read step and recorded the page count. That edit is not on main.

   Recorded pages, each seed twice: 1 page and 6,000 changes, 3 pages and 6,000 changes, 6 pages and 6,000 changes. The table is the first run, step 5 only (the branch read).

   pages	limit	requests	repeat reads	manifest	table	table_data.get	sim ms	bytes read
   1	8192	113	33	22	91	85	652.8	1,483,261
   3	2000	229	119	66	163	149	1,546.9	3,066,382
   6	1000 (default)	421	259	132	289	263	2,914.9	5,723,430

   Manifest requests are exactly 22 on every page (22, 66, 132). The change_feed.pre_table_open phase is exactly 19 requests per page (19, 57, 114). phase.start stays at 7 requests. change_feed.post_head_witness is 87, then 165, then 300. From 1 page to 6 pages the same 6,000 changes issue 308 more requests (about 62 per extra page) and read 3.9 times as many bytes. Simulated s3-like time grows by about 450 ms per extra page. Repeat reads go 33, 119, 259, so most of the added requests read an object this step already read.

   Wall time

   Same debug CLI, local disk, two passes. Output bytes are identical across limits, so the byte budget does not split these pages.

   16,001 rows, 4,001 changes, 2,072,195 bytes:

   limit	pages	pass 1	pass 2
   8192	1	0.381 s	0.339 s
   1000	5	0.600 s	0.553 s
   500	9	0.813 s	0.718 s
   250	17	1.137 s	1.034 s

   About 0.04–0.05 s per extra page on the second pass.

   80,001 rows, 8,001 changes, 4,167,800 bytes:

   limit	pages	pass 1	pass 2
   8192	1	1.058 s	0.998 s
   1000	9	1.895 s	1.837 s
   500	17	2.268 s	2.277 s

   About 0.08–0.10 s per extra page. The slope is larger on the larger table.

   Command:

   omnigraph --store file:///tmp/repro970/graph branch diff feature --into main --limit <N> --json
   omnigraph --store file:///tmp/repro970/graph80 branch diff feature --into main --limit <N> --json
   

   With no --page-token, the CLI follows every page and returns one JSON object. These times are the full result. Both graphs are Person rows with a 32-byte bio, loaded in commits of 4,000. The feature branch updates 4,000 or 8,000 rows and inserts one. Main inserts one row after the fork. The branch diff omits that main insert, so the change counts are 4,001 and 8,001.

   What differs from the report as filed

   • The checkout is 9e2425d, not the citation SHA 2d8bab7a. The two cited functions are still at the cited lines.
   • A 32-byte bio at the default limit of 1,000 gives 1, 2, and 6 pages for 10, 2,000, and 6,000 changes. The filed counts of 1, 3, and 7 need a change large enough for the 4 MiB byte budget to split the page (on the order of 4,500 bytes). Here each change serializes to about 518 bytes, so the byte budget does not split. The 3-page row above uses limit 2000.
   • Absolute DST counts differ. This run is 113 / 229 / 421 requests for 1 / 3 / 6 pages of one 6,000-change diff. The issue reported 92 / 288 / 604 for 1 / 3 / 7 pages, and about 41 catalog requests plus 45–57 table requests per extra page. Here the catalog class is 22 requests on every page, including the first. table_data.get grows by about 32–38 per extra page. That is less than a full repeat of the one-page scan (85 GETs) and still far above the bytes of the changes themselves.
   • Wall time is a debug CLI on 4 CPUs at 16,001 and 80,001 rows. The filed timing is a release CLI on 18 cores, 1,000,000 rows, and 100,000 changes (19.5 s at 100 pages versus 7.3 s at 13 pages, about 0.14 s per extra page). The shape matches: the same changes cost more when they are split into more pages, and the extra cost grows with the table. The 1,000,000-row case was not run.
   • Current GQT spelling is branch diff under --- query. Merge-base and merge dry run do not page, so they are not in this slope.

   Root cause

   Every page calls enumerate_commit_changes, and that function calls plan_intervals before it emits a row.

   • plan_intervals opens both pinned datasets with open_at_entry_verified (lines 392–393), fingerprints the user schema, may classify a candidate plan, then re-proves both branch heads with reprove_named_branch_heads (lines 441–442 and 462–479).
   • enumerate_commit_changes calls that plan on line 498 for every page, including a resume.
   • The measured feature interval covers more than one Lance version (two update commits, then an insert). interval_candidate_plan returns None before any transaction read when the interval is wider than one version (lines 184–218). The walk is then the full ordered merge. That matches performance: graph diff and branch review read both full tables unless the endpoints are one transaction apart #969.
   • Resume is col(id).gt(lit(after_id)) at row_compare.rs line 361. OrderedRowCursor::open requests ColumnOrdering::asc_nulls_last(id). scan_stream_with sends an ordered scan to execute_bounded_ordered_scan.
   • Lance 11.0.0 appends SortExec whenever ordering is set (scanner.rs lines 3096–3124 in the pinned crate) and refuses limit/offset pushdown because it must sort all data first (lines 2865–2867). use_scalar_index defaults to true, so a BTREE can accelerate the id > last filter. The survivors are still sorted. There is no scanner resume API.
   • A fresh load has no __id BTREE. plan_index_work_node plans that index when index work or optimize runs.

   Callers, all on this SHA:

   • Commit changes: commit_changes_page resolves the parent and the child again and calls enumerate_commit_changes on every page. An omitted limit is 1,000 (line 2529).
   • Graph diff: run_diff_page always enumerates (line 2869). The first page resolves the endpoints in prepare_diff. A later page uses reopen_diff_continuation. The branch form calls capture_merge_base again (line 3074) and then opens both commits. The token stores commit ids. It is checksummed, not signed.
   • Change feed: feed.rs line 336 calls enumerate_commit_changes for each commit, including a MidBlock resume (line 355).
   • Merge-base and merge dry run are one-shot lineage and classification reads. They do not restart a paged comparison.

   Graph-branch pins have native_dataset_branch == None, so open_at_entry_verified uses the warm TableStore session (lines 1739–1741). Lance 11 already caches manifests in that session (Dataset::get_manifest around line 830 of the pinned dataset.rs, keyed by version and e_tag). The measured requests still grow by a fixed catalog cost per page. The session cache does not remove the re-plan, the head reprove, or the sort.

   Interim mitigation

   The CLI mitigation is in place for a follow-all read. Pagination::from_args uses COMMIT_CHANGES_MAX_CHANGES (8,192) when there is no token. An explicit --page-token leaves the limit unset, so the server default of 1,000 applies. HTTP passes params.limit through, and an omitted limit becomes 1,000. The MCP diff tool has an optional limit and no default (mcp.rs line 1712), so an omitted limit is also 1,000. This cuts the page count. The catalog cost per page stays.

   Recommended fix

   Keep one plan of the two immutable snapshots, and reuse that plan for every page of the comparison.

   The token already carries the resume key: the commit ids and the last id. That key remains the name of the comparison. A process-local cache may hold the version-pinned datasets and the interval plan, keyed by those commit ids. Invariant 12 allows a cache of immutable version-pinned state. Invariant 6 requires the answer to be the same when the cache misses, so a miss re-plans. Invariant 11 requires hot-path work to scale with the working set. Today page K also repeats the catalog work and the sort of the keys still ahead.

   Every page still authorizes the caller and still runs the branch-reach, head-reprove, and schema-boundary witnesses. Those witnesses exist so a branch delete and recreate cannot retarget a continuation (CHANGE_FEED_PRE_TABLE_OPEN, CHANGE_FEED_POST_HEAD_WITNESS, the e_tag check, reprove_named_branch_heads). A cache that skips them would return the wrong rows. Tokens are checksummed, not signed (#1009), so a client can claim coordinates. Do not treat Lance versions inside the token as authority. If a later token carries snapshot coordinates, one read still proves them.

   Ordered resume: when a covering __id BTREE exists, read the key range in index order from the last id and do not append SortExec. When it does not exist, sort once for the comparison and keep a bounded key cursor for later pages. A fresh table has no __id BTREE until index work runs, so the one-sort cursor is the path that covers a new load.

   This covers commit-changes pages, change-feed pages that stop inside a commit, and graph diff pages (branch form and two-point form), on local disk and on object stores, for HTTP, CLI, MCP, and embedded callers. Merge-base and merge dry run stay outside it. A later write does not change the rows of an already published commit, so the cache key is the commit id, not the branch tip. A branch move stays on the reach walk that already runs on each page. A schema boundary still refuses the whole pair on every page.

   Alternatives

   1. Raise the HTTP and MCP default toward 8,192. Fewer pages. The cost stays linear in P. The CLI already does this when it follows every page. The acceptance (catalog cost flat in pages already served) stays unmet.
   2. Cache the snapshots and the plan only. Catalog opens become flat. The sort of the remainder remains.
   3. Index resume only. The sort drops when a BTREE exists. The catalog restart remains. A table with no BTREE is unchanged.
   4. Carry snapshot coordinates in the token and validate them with one read. This works across processes. The token is unsigned, so the claim must be checked. The sort remains.

   Liability

   Removed: P times the catalog open, and P times the sort of the remaining keys.

   Added: a bounded cache of pinned state. The cache must fail closed when a witness does not match. It must not outlive the snapshot. It must not skip policy. A wrong cache is worse than a slow page. Open pull request #818 already holds a pin the process just wrote. That is the same invariant 12 idea for a different object. It is not a change-page cache, and it should not become a second source of truth.

   Lance upstream

   Pinned Lance is unmodified 11.0.0. Lance 11 already has checkout_version (dataset.rs line 493) and a session manifest cache (get_manifest, line 830). That cache is already on the warm open path used here. It does not flatten the measured growth.

   Lance 13.0.0 (released 2026-10-07) still refuses limit/offset pushdown on an ordered scan, with the same comment at scanner.rs line 3165, and still appends SortExec at line 3445. I found no Lance issue or pull request that adds a scanner resume cursor or that replaces SortExec with an ordered walk of a scalar BTREE.

   Open pull request #1072 upgrades this repository to Lance 13.0.0. It does not claim to change change enumeration. Lance 13 does make a future index-ordered resume cheaper:

   • lance#9310 coalesces btree page loads into one read_ranges request
   • lance#9461 caches index file metadata across opens
   • lance#9462 assembles btree search results once
   • lance#9463 streams btree pages for update, remap, and prewarm

   Session manifest reuse on open and checkout is already in Lance 11 (lance#7576, lance#7661). The Lance performance guide describes BTREE range queries and sorted access. The scanner order_by path does not use that order. An upgrade can lower the cost of each open and of each index lookup. It does not make the per-page catalog cost flat, and it does not remove the sort. Release notes: https://github.com/lance-format/lance/releases/tag/v13.0.0

   Related work

   • #971 is the same ordered walk and a different cost. Hydration re-reads data pages for every chunk inside one walk. performance: every change page restarts its comparison (re-plan, re-resolve endpoints, re-sort keys) #970 restarts the plan, the endpoints, and the sort on every continuation page. A fix for one leaves the other. Neither supersedes the other. performance: ordered-cursor hydration re-reads data pages and file metadata for every chunk #971 is open and has no comments.
   • #966 (merged) added graph diff, branch review, and merge dry run.
   • #968 (merged) is the CLI page size of 8,192 and the one-resolution of diff sides on the first page. It left this restart open.
   • #969 is the full-table compare when the endpoints are not one transaction apart. That is why these pages sort the whole remainder.
   • #972 is the commit-lookup miss that scans every live branch. perf(changes): resolve diff sides once, skip commit lookups for branch names, use full CLI pages #968 fixed that for branch-name sides.
   • #1009 continuation tokens are checksummed, not signed.
   • #1048 feed across additive schema changes. #1049 entity version history. #1053 footprint and filters before table opens. #1056 wait for a branch move. #1068 cold commit-list cost. #1052 pinned-read cost. #642 fork metadata versus sibling branch count. #837 reuse the process's last publication. #724 process-global admission.
   • #818 (open) holds a just-written version in the read-handle cache.

   Supersession

   No open issue covers this defect with a broader scope or a better reproduction. This issue stays open.

   Limitations

   • The 1,000,000-row release-CLI timing was not repeated. The local trend is at 16,001 and 80,001 rows on a debug build and 4 CPUs.
   • The filed DST page counts of 1 / 3 / 7 were not reproduced with a 32-byte bio. The measured series is 1 / 3 / 6 pages of the same 6,000 changes, and the 3-page case uses limit 2,000.
   • Stock GQT reads one page. The request counts above depend on a temporary follow-pages edit in the measurement binary. That edit is not on main.
   • Merge-base and merge dry run were not measured. They do not page.