performance: a cold commit list reads every merged branch's history block, one at a time

Problem

The first commit list on a server that has just started reads every __history object of the graph, one after another, including the blocks of every merged review branch. The answer is only the branch's first-parent chain, and most of those objects hold none of its commits. On a graph written through short-lived review branches the cost grows with the number of branches ever merged, not with the length of the list. Each read is a bucket round trip, so a cold call runs for minutes.

The path at d883c49:

Omnigraph::list_commits (omnigraph.rs#L3902) → CommitGraph::load_commits (commit_graph.rs#L727) → lineage() (commit_graph.rs#L651) → .first_parent_chain().
The history cache counts as complete only when it is closed under every parent, merged parents included. On a cold handle lineage() therefore takes the full refresh (record_projection_full_refresh) through history::read_lineage_in.
The full refresh lists __history and reads each extent in turn: for key in list_extents(...) { found.push(selection.listed(&key, Narrow::All).await?) } (history.rs#L3061). Every extent waits for the previous one.
The result lives only in process memory, and it is stored only after the walk completes.
The server's scoped storage client sets client_max_retries=0 for every request, reads included (lance_access/scoped.rs#L72). One transient read error anywhere in the walk fails the whole request, and the next call starts the walk over. (bug: one storage write with an unknown outcome stops the server until a manual unlock #1067, step 3, covers re-enabling retries for idempotent requests.)

#1013 added paging (--limit/page_token) that walks first parents and reads only the extents a page's commits occupy. Without those parameters the answer and its cost are unchanged, and the unpaged form is still the default.

Evidence

A production cluster graph on 0.14.0-edge+d883c49, against an S3-compatible bucket in the same region as the server. Writers apply every change as load --from main on a review branch, merged into main.

__history holds 1,695 objects; the commit list returns main's first-parent chain:

	Count
Block extent objects	1,673 (221 MB)
Distinct blocks	1,596
Blocks with exactly one object, typically one commit (`<block>/143-143.lance`)	1,576
Commits returned	4,987
Blocks holding the returned commits	20
Merge commits among them, each naming a different merged branch's block	1,560

So about 93% of the objects the refresh reads hold no commit it returns.

Latency of GET /commits with no paging parameters:

Server state	Time
Just started	103 s
Immediately after	1.6 s
Just restarted	`500` after 56 s
Next call	227 s

227 s over 1,673 objects is about 136 ms per object, consistent with a few sequential requests per extent. That per-object figure is inferred from the timing; request counts were not measured. The server logs nothing during the walk (no Lance scan lines), so a slow call cannot be told apart from a hung one.

Directions

One first-parent walk for both forms. Build the unpaged list from the same first-parent walk the paged list uses, with no limit, and drop the requirement that the cache be closed under merged parents. The list never returns a merged branch's commits, so their blocks need not be read. Any caller that does need full closure under parents, such as ancestry or merge-base, keeps its own bounded reads.
Concurrent extent reads. Wherever a full refresh remains, read extents with bounded concurrency instead of one at a time. Memory is already bounded per extent.
Retries for reads. A GET is idempotent, and its retry cannot hide a mutation, so the single-attempt rule should apply to mutations only. (bug: one storage write with an unknown outcome stops the server until a manual unlock #1067, step 3.)
Fold small branch blocks. Let optimize combine the single-commit extents left by merged review branches into fewer objects, preserving commit ids and slots. That bounds the object count for every history reader, not only the commit list.
Observability. Log the history objects read and the time spent when a cold refresh runs, so a slow walk is visible.

Acceptance

On a cold handle, an unpaged commit list reads a number of __history objects bounded by the extents that hold the returned chain, flat in the number of merged branches.
One transient read error during the walk does not fail the request.
Gate this in a cost owner, for example integration/warm_read_cost.rs or a GQT --measure case: a graph with N merged single-commit review branches, where a cold commit list request count must stay flat as N grows.

How this was measured

Object counts: a LIST of the graph's __history/ prefix, keys and sizes only.
Commit and block counts: the returned commit ids (hb1.<block>.<slot>.…) and their merged_parent_commit_id values.
Wall times: the edge CLI over HTTPS from outside the region. The client-to-server round trip, about 0.2 s, is negligible next to these times.

Summary

A cold unpaged commit list still reads every __history extent. The paged list does not. I reproduced that growth on main b692610c4aa31066cb6a9fd34830f56977288943. No merged or open pull request changes this walk. This issue does not supersede another issue, and I am not closing it.

The user-visible problem is a cold GET /commits with no limit and no page_token. On a graph built from short review branches, the call reads objects that are not in the answer. The cost follows the number of merged branches. One failed read fails the whole call.

Status

The issue is open. It has no comments. No pull request implements the fix.

These issues cross-reference it: #1067, #641, #642, #644, #724, #837, #895, #970, #971. None of them is a reproduction or a fix.

What changed since `d883c49`

The unpaged path is the same path the report describes.

feat(commits): page a branch's commit list #1013 added paging. It is merged. Without limit or page_token, GET /commits still calls list_commits.
CommitGraph::lineage and the extent loop are unchanged. The history store now takes the Lance 13 session. That does not change which objects the loop reads.
lance_access/scoped.rs still sets client_max_retries to 0 and lance_aimd_max_retries to 0.
build(storage): upgrade lance to 13.0.0 #1072 pins Lance 13.0.0. It does not change this walk.

Reproduction

Reproduced for the read-count claim. Not reproduced for the S3 latency numbers. Confirmed from code for the single-error claim. I did not inject a fault.

Environment:

main b692610c4aa31066cb6a9fd34830f56977288943 (checked against origin/main on 2026-10-20)
rustc 1.97.1
Linux, local file:// directory, debug test profile
not S3, and not a server process

I added a temporary test next to the history counter in crates/omnigraph/tests/integration/warm_read_cost.rs, ran it, and removed it. It is not on a branch.

For N = 1, 3, and 6 the fixture did this:

Create review{i} from main.
Insert one row on that branch.
Insert one row on main, so the merge is not a fast-forward.
Merge the branch into main. Each merge outcome was Merged.

Then a new handle ran list_commits, a second call on that same handle, and a cold paged walk with limit 100. A control graph had 6 inserts on main and no review branch.

Command:

cargo test -p omnigraph-engine --test integration warm_read_cost::cold_unpaged_commit_list_reads_stay_flat -- --nocapture

The whole run finished in 0.95 s. Results from HistoryPlane::requests (the counter warm_read_cost.rs already uses; it sums the history wrapper and the opened store):

N	extent objects	commits returned	blocks in the answer	merged-parent blocks outside the answer	unpaged reads
1	1	5	2	1	4
3	3	9	2	3	8
6	6	15	2	6	14

Main-only control: 0 extent objects, 0 unpaged reads, 9 commits returned.

The test required unpaged reads to stay flat from N = 1 to N = 6. It failed. Reads went from 4 to 14. Objects on disk went from 1 to 6. Each object is one single-slot file, __history/blocks/<block>/<slot>-<slot>.lance. The paged walk stayed at 0. The second call on the same handle stayed at 0.

I did not split the counter by path. The object count is exact and equals N. The counter grew by 2 recorded reads per added branch (2*N+2).

Claim by claim

A cold unpaged list reads every merged-branch extent, and each extent waits for the previous one. Reproduced. list_commits calls load_commits, which calls lineage(), which calls read_lineage_in. With no commit ids, read_selected lists every extent and reads each one in a for loop (history.rs around the list_extents loop). Objects on disk equal N. The counter grows with N. The loop is sequential in source.
The answer is the first-parent chain, and most of those objects hold none of it. Reproduced, in a stronger local shape. The returned commits stay in the __manifest buffer under the default 256 KiB release budget. Their block count stays 2. Every extent is a merged parent outside that chain. The paged walk reads none of them. A main-only chain of 9 commits also reads none. So the reads follow merged branches, not the length of the answer.

The filed graph had also released main's own history: 4,987 commits in 20 blocks, and 1,673 extent objects. I did not rebuild that released shape. The same full refresh would read those main blocks and the merged-parent blocks. a_commit_list_page_reads_the_history_it_returns already shows that the whole listing reads more blocks when main releases more, and that one page reads less.
The result lives only in process memory, and only after the walk completes. Confirmed in code, and the warm call matches. HistoryCache::replace runs after read_lineage_in returns. The second call recorded 0 reads. A new handle is cold. I did not restart a server.
The server scope sets client_max_retries=0 for reads, so one transient read error fails the walk. Confirmed from code. Not injected. The local test uses an embedded file store, not the server scope. scoped.rs still forces both retry knobs to 0. A served graph uses that scope, and history reads use that session's store registry. The extent loop uses ?. The cache is not stored on error. The next call starts the walk again. Lance's default client_max_retries is 3. The scope overwrites it. download_retry_count (default 3) covers a short response body, not a GET that fails before a body.
feat(commits): page a branch's commit list #1013 does not change the unpaged default. Confirmed. server_commit_list calls list_commits when limit and page_token are both absent. The CLI does the same.
Cold calls of 103 s and 227 s, and a warm call of 1.6 s, on S3. Not reproduced. Local disk finished the N = 6 case inside a 0.95 s test. I cannot repeat the bucket round trips here. The warm half (0 reads on the same handle) matches the report's "the second call is cheap" claim. It does not match the 1.6 s figure.

Difference from the filed steps: I did not run load --from main. A branch merged with no later commit on main fast-forwards and does not write this merged-parent extent. The fixture writes on main after the fork so each merge is Merged. That is the shape behind the report's 1,560 merge commits.

Root cause

The list never returns a merged parent. lineage() still requires the cache to be closed under every parent, merged parents included (HeldCommits::outside_parents, then the complete check in lineage()). On a cold handle that check fails, and the code calls read_lineage_in. That function reads every extent. first_parent_page already walks only first parents and reads an extent only when the page does not already hold that commit. The unpaged list does not use it.

A missing or unreadable merged-parent extent also fails the list today, through unlisted_absent, even though the list does not return that commit.

Code on this SHA:

crates/omnigraph/src/db/omnigraph.rs list_commits (about line 4168) and list_commits_page (about line 4197)
crates/omnigraph-server/src/handlers.rs server_commit_list (the paged flag about line 3492, the unpaged call about line 3565)
crates/omnigraph-catalog/src/commit_graph.rs lineage (about line 652) and load_commits (about line 728) and first_parent_page (about line 744)
crates/omnigraph-catalog/src/history.rs read_selected (the loop about line 3061) and read_lineage_in (about line 3452)
crates/omnigraph-core/src/lance_access/scoped.rs (about lines 71–73)

Recommended design

Make the unpaged list the same first-parent walk as the paged list, with no page cap. Do not call lineage() from list_commits.

Keep the response the same when limit and page_token are absent. #1013 keeps that response byte-for-byte with the old list. Build the unpaged answer from the first-parent walk so the two forms cannot drift. load_commits still sorts by lineage_key and list_commits reverses that. A page walks first parents by generation. The type comment says lineage_key does not define feed order. A merge chain is the case to check, because a merged parent can have a generation off the first-parent line.

This is the small correct change. A faster full refresh would still read the irrelevant objects.

Callers of lineage() and what they actually need:

The commit list needs first parents only. Use the page walk.
build_change_feed_cut needs first parents only. It finds genesis and builds the child index. A cold change feed pays the full refresh today. changes: continue change feeds across additive schema changes and outside the request's type filter #1048 and changes: wait for a branch to move instead of polling #1056 sit on that cut. They do not need every merged parent.
Collector lineage_holds needs first parents below the captured head. It can stop at the commit it seeks.
Collector retained_merge_bases needs both parents. CommitGraph::merge_base already fetches by id, with a visit cap and a byte cap, and it does not fill the parent-closed cache. Use that walk. Do not load every extent first.
Unpublished and unattached lifetime checks need one commit id on the first-parent chain. A bounded walk or read_commit is enough.
get_commit and diff endpoints already read one commit by id. They do not use this full refresh.
changes: read the version history of one entity #1049, the history of one entity, should read the commits that touched that entity. It should not scan every merged-branch block. performance: a read pinned to a commit costs 0.5–0.9 s more than the same read at its branch #1052 is a different cost: a read pinned to a commit. It is not this walk.

After those callers move, read_lineage_in has no production caller. That is the shape invariant 11 and invariant 12 already ask for. Hot-path work follows the working set. A request does not rebuild a warm projection from full history.

Bounded concurrency. Do not use it to fix the list. It still reads the irrelevant objects. Use it only for a reader that must see every extent, such as an explicit integrity check. A lineage read fetches a suffix of at most TAIL_BYTES (512 KiB). A full record object can be 64 MiB (MAX_OBJECT_BYTES). Cap the number of reads in flight. Do not start one task per object.

Retries. Put them in the storage-outcome work, not in a special case in history.rs. #1067 step 3 and #1093 classify requests. A GET of an immutable extent can be retried. A conditional publication stays one attempt. Open PR #1096 splits those two clients and routes GET to the retrying client. It is not merged. It does not change which extents the list reads. On main, one GET error still fails this walk. Do not retry the whole walk as one mutation. Client retries do not fix the object count. An error that survives the retry budget still fails the call until the list stops reading every extent.

Folding small blocks. Do not put that in this change. optimize does not rewrite __history. A full list reads every object list_extents returns, and overlapping copies are compared. A fold that leaves the old objects in place makes that read worse. Replacing them is a retention decision (#645). #1082 says optimize on a served cluster requires a stop. #1094 and #1095 are about table versions, not these extents. Folding can help every history reader later. The list must be correct without it.

Persistence. Do not store a second copy of the chain. The cache is process memory, and it is stored only after a successful walk. A restart repeats a cold walk. A durable chain beside __history can drift. The block-registry RFC already keeps derived block shape in __manifest for merge-base, and __history stays the authority. ExtentCache can keep objects this process has already read. That is enough once a cold list reads only the chain.

Observability. Log a refresh that still runs: object count, bytes, and duration. record_projection_full_refresh only increments a test counter. It does nothing in production. Lance object-store metrics need the metrics feature and a recorder, and they do not name __history. Open PR #1001 adds OTLP traces. The history log line does not need to wait for that pull request.

What this choice gives up is a cache that survives a process restart. That is the right cut. A shadow chain is a second source of truth. After the fix, a cold list scales with the returned chain, so a restart does not need that copy.

The list also stops failing when a merged-parent extent is missing or unreadable. The list does not return that commit. A caller that needs the merged parent still fails its own read.

Test plan

Extend integration/warm_read_cost.rs. Do not add a .gqt case. The defect is a request count, and docs/dev/testing.md allows a deterministic operation count as a CI contract. The owner test a_commit_list_page_reads_the_history_it_returns already covers pages against releases on one branch. Extend that plane. Do not add a second harness.

The fixture above, at the default release budget. Assert that cold unpaged reads stay within a fixed bound of the main-only control as N grows. Assert that the paged walk stays in that bound. Assert that the second call reads 0. Assert that both forms return the same commits, including merge commits.
The same fixture with a low history_release_bytes, so main's chain is in __history. Assert that unpaged reads equal the paged walk of the whole chain. Assert that both stay flat in N against a main-only chain with the same number of releases.
One injected GET error on an extent the walk does read, through the scoped client. The list succeeds once read retries from fix(server): scope an unknown storage outcome to its key and branch #1096 exist. Until that client is merged, do not add a retry only in history.rs.
crates/omnigraph-dst/cost_table.txt has no commit-list row. Update it only if a covered operation's storage calls change.

Lance

Lance does not cause this, and a Lance upgrade will not fix it.

OmniGraph lists its own __history objects and GETs them in its own loop. The pinned version is Lance 13.0.0. That is also the latest stable release, published 2026-10-07. Current pre-release is v14.0.0-beta.21, published 2026-10-19. No open pull request in this repo upgrades Lance. #1072, the move to 13.0.0, is already merged.

I checked the Lance object-store guide and the Lance 13.0.0 client_max_retries getter. The default is 3. The server scope sets it to 0, so a change to Lance's default would not apply on the server until OmniGraph stops forcing 0. Open Lance work on retries (#8363 for OpenDAL, #6544 for rename_if_not_exists) does not remove this loop. Lance can emit lance_object_store_requests_total when metrics are enabled. That does not tell an operator that a commit list is walking every history object.

Related work

feat(commits): page a branch's commit list #1013, merged. Paging only. The unpaged default is unchanged.
bug: one storage write with an unknown outcome stops the server until a manual unlock #1067 step 3, rfc: storage outcomes per operation and restartable ownership #1093, and open fix(server): scope an unknown storage outcome to its key and branch #1096. Retries by request class. Not this object count. fix(server): scope an unknown storage outcome to its key and branch #1096 is open and is not a commit-list fix.
Optimizing a served cluster requires stopping the server, and each direct run keeps its lock #1082, Cleanup leaves a table version's manifest readable after deleting its files #1094, performance: cleanup opens every table version before deleting any, so a run cut short reclaims nothing #1095, storage: define logical commit-history retention and explicit expired-history outcomes #645. Optimize on a live cluster, cleanup, and history retention. Separate from this walk.
changes: continue change feeds across additive schema changes and outside the request's type filter #1048, changes: read the version history of one entity #1049, changes: wait for a branch to move instead of polling #1056. Change feeds and one-entity history. A cold feed cut uses lineage() today.
performance: a read pinned to a commit costs 0.5–0.9 s more than the same read at its branch #1052. Cost of a commit-pinned read. Different path.
Read cost and OOM on fragment/history-heavy branches #566. Fragment read cost and OOM. Different path.
docs/rfcs/2026-10-10-merge-base-block-registry.md. Derived block shape for merge-base. __history stays the authority.
performance: a commit lookup that misses the current branch checks out every live branch's __manifest #972. A commit lookup that misses the branch opens every live __manifest. Different path.

Nothing here supersedes #1068. The commit-list walk is still the open defect.

Limitations

No S3, and no server process. The 103 s and 227 s figures are not repeated here.
The fixture forces Merged by writing on main after the fork. A fast-forward does not write this extent.
I did not measure a graph whose main chain is already released. The full refresh is the path that would read those blocks too.
I did not inject a read error.
The temporary test was removed. No code was pushed.

Navigation Menu

Repository navigation

performance: a cold commit list reads every merged branch's history block, one at a time #1068

Problem

Evidence

Directions

Acceptance

How this was measured

Summary

Status

What changed since `d883c49`

Reproduction

Claim by claim

Root cause

Recommended design

Test plan

Lance

Related work

Limitations

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

performance: a cold commit list reads every merged branch's history block, one at a time #1068

Description

Problem

Evidence

Directions

Acceptance

How this was measured

Activity

ragnorc commented on Oct 20, 2026

Summary

Status

What changed since d883c49

Reproduction

Claim by claim

Root cause

Recommended design

Test plan

Lance

Related work

Limitations

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

What changed since `d883c49`