Diff performance: add per-table commit index to skip unchanged-table commit loads

[timsehn]

Problem

dolt_diff_<table> full-history queries walk every commit in the graph. For tables that change infrequently, most of that work is wasted.

What's already done

• Streaming results: dolt_diff_<table> uses prollyDiffIterOpen / prollyDiffIterStep — a lazy iterator over the prolly tree diff. Results flow through xNext one change at a time with no intermediate buffer.
• Skip unchanged commits: appendCurrentDiffPair (doltlite_diff_table.c:377-379) compares the table root + schema hash between each commit and its child. If both match, the commit is skipped and no prolly diff iterator is opened.

Remaining bottleneck

Even with the skip, the walker still loads every commit in the graph to check: doltliteLoadCommit + doltliteLoadCatalog + linear scan for the table name. For a table that changed in 100 out of 10K commits, that's 9900 unnecessary commit loads + catalog deserializations.

Proposed fix: per-table commit index

At commit time, for each table whose root hash changed from parent, write a (table_id, commit_hash) entry into a side index in the chunk store. Then dolt_diff_<table> walks only the indexed commits instead of every commit in the graph.

The index is small (one 20-byte hash per table per commit that touched it) and the write-time cost is one root-hash comparison per table per commit — which we already compute during the commit flow anyway.

This is the same optimization git log -- path uses: git can skip commits where the subtree hash for the directory didn't change because it has tree objects with hashes at each level.

[timsehn]

Partial progress update — the streaming ask is done.

dolt_diff_<table> now uses prollyDiffIterOpen / prollyDiffIterStep (a lazy iterator over the prolly tree diff). Results flow through the vtable's xNext one change at a time; there's no intermediate buffer of the entire result set. This was implemented as part of the prolly diff infrastructure that predates this issue being filed.

The other two asks — pre-computed/cached row-level deltas at commit time and commit graph indexing for efficient ancestor queries — are still open. The current per-table diff does an O(changes) prolly tree walk between two roots (not O(table size)), but it recomputes from scratch on every query with no caching across calls.

Updating the title to reflect remaining scope.

[timsehn]

Per-table commit index idea:

At commit time, for each table whose root hash changed from parent, write a (table_id, commit_hash) entry into a side index in the chunk store. Then dolt_diff_<table> walks only the indexed commits instead of every commit in the graph.

The current full-history walker (buildDiffPairs in doltlite_diff_table.c) already skips commits where the table root didn't change (line 377-379 compares root + schema hashes and returns early), but it still pays the per-commit overhead of doltliteLoadCommit + doltliteLoadCatalog + linear scan for the table name on every commit in the graph just to discover there's nothing to do. For a table that changed in 100 out of 10K commits, that's 9900 unnecessary commit loads + catalog deserializations.

A per-table change index turns that into 100 indexed lookups with zero wasted catalog loads. The index is small (one 20-byte hash per table per commit that touched it) and the write-time cost is one root-hash comparison per table per commit — which we already compute during the commit flow anyway.

This is the same optimization git log -- path uses: git can skip commits where the subtree hash for the directory didn't change because it has tree objects with hashes at each level. The doltlite analog stores (table_id, commit_hash) pairs explicitly so the diff walker can seek directly to relevant commits.

[timsehn]

Closing — the two actionable optimizations are already implemented:

1. Streaming: dolt_diff_ uses prollyDiffIterOpen/Step, no buffering.
2. Skip unchanged: buildDiffPairs compares table root + schema hashes per commit and skips the prolly diff entirely when they match.

The per-table commit index idea would save the per-commit catalog-load overhead for irrelevant commits, but Dolt itself uses the same walk-and-compare strategy at production scale without a table-level index. The constant factor per skipped commit (load commit metadata, look up table hash, compare) is small enough that this doesn't need a dedicated index structure.

If diff latency becomes a real problem at high commit counts, the index idea is documented in the comments above and can be revisited.