Skip to content

compute: borrow each correction chunk once per merge, not once per update - #38896

Merged
antiguru merged 1 commit into
moritz/correction-metrics-o1from
moritz/correction-borrow-hoist
Sep 30, 2026
Merged

antiguru merged 1 commit into
moritz/correction-metrics-o1from
moritz/correction-borrow-hoist

Conversation

@antiguru

@antiguru antiguru commented Sep 16, 2026 •

Copy link
Copy Markdown
Member

Every element access in CorrectionV2 re-decoded its chunk. Chunk::index was self.column().borrow().get(i), and Column::borrow on a serialized column rebuilds the struct-of-arrays view from the serialized header, so a k-way merge paid O(log k) header decodes per output update: 42.7% of an insert profile, ahead of the merge itself at 12.2%.

Borrowing is now hoisted to one view per chunk, or per chunk pair in the two-way merge, whose inner loop runs until either cursor crosses a chunk boundary. The k-way merge that reads over three or more chains works in rounds the same way: each round borrows the current chunk of every input and heaps their updates, and ends when an input crosses a chunk boundary. merge_many_consolidates_across_chunks covers it. Cursor gained chunk_handle, reads_from, and get_with for callers that hold a view across cursor steps; get and index remain the documented single-access forms. Chain iteration, chunk splitting, and the time search index a hoisted view likewise.

Holding a view inside the iterator that updates_before hands across the persist writer's await needs the view to be Send, which is a new bound on the container. The container bounds move into a DataContainer helper trait so Data stays readable.

Insert improves 1.6x on a 4.19M-update append workload, and 2.0x under a memory cap, where each redundant decode also faulted the header page back in. The new column_borrow bench in mz-timely-util measures that decode: per-element borrows of a serialized column against one hoisted borrow and a typed column.

Supersedes the fork PR #38649.

🤖 Generated with Claude Code

@antiguru
antiguru added this pull request to stack #38898 September 16, 2026 17:59
@antiguru
antiguru marked this pull request as ready for review September 16, 2026 18:00
@antiguru
antiguru requested a review from a team as a code owner September 16, 2026 18:00
@antiguru antiguru changed the title moritz/correction borrow hoist compute: borrow each correction chunk once per merge, not once per update Sep 16, 2026
@antiguru
antiguru requested a review from DAlperin September 16, 2026 21:08
@antiguru
antiguru requested a review from a team as a code owner September 17, 2026 13:54
@antiguru
antiguru force-pushed the moritz/correction-borrow-hoist branch from f688154 to 72afe41 Compare September 17, 2026 13:54
@antiguru
antiguru force-pushed the moritz/correction-borrow-hoist branch from 72afe41 to cde2ae6 Compare September 23, 2026 13:23

@antiguru antiguru left a comment

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Self-review.

  • Placement: the column_borrow bench measures the per-element decode that this PR removes, but it lands in #38897. It belongs here.

🤖 Posted by Claude Code

@antiguru
antiguru force-pushed the moritz/correction-borrow-hoist branch from cde2ae6 to 0266dbb Compare September 30, 2026 13:12
@antiguru

Copy link
Copy Markdown
Member Author

Addressed. The column_borrow bench moved here from #38897.

🤖 Posted by Claude Code

@DAlperin

Copy link
Copy Markdown
Member

The description says this fixes the k-way merge, but merge_many isn't touched. The heap comparisons still call Cursor::get() on every compare, so the per-update header decode is still there. The insert numbers come from merge_2, which is all chain compaction uses. Reads with three or more chains still go through merge_many.

Either hoist there too (keep a view per MergeCursor and refresh it when the cursor changes chunks), or scope the description to the two-way merge. The new Cursor::get doc also says loops must hoist, and merge_many doesn't.

@antiguru
antiguru force-pushed the moritz/correction-borrow-hoist branch from 0266dbb to ca33cdf Compare September 30, 2026 15:44
@antiguru

Copy link
Copy Markdown
Member Author

Good catch, thanks. I hoisted the borrow in the k-way merge rather than narrowing the description. merge_many now works in rounds, like merge_2. Each round borrows the current chunk of every live cursor once and keys a heap on (time, data, index) straight from those views. A round ends when some cursor crosses into its next chunk, and the next round borrows again. All cursors at the same update are folded into it before a round can end, so no update is split across rounds.

The heap orders updates directly, so MergeHeap and MergeCursor are gone, and merge_many no longer calls Cursor::get. merge_many_consolidates_across_chunks runs a three-way merge over chains of several chunks each, with overlaps and cancellations. The test fails if equal updates are not gathered within a round.

🤖 Posted by Claude Code

@DAlperin DAlperin left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM, thanks

…date

Every element access in `CorrectionV2` re-decoded its chunk. `Chunk::index` was
`self.column().borrow().get(i)`, and `Column::borrow` on a serialized column
rebuilds the struct-of-arrays view from the serialized header, so a k-way merge
paid O(log k) header decodes per output update: 42.7% of an insert profile,
ahead of the merge itself at 12.2%.

Borrowing is now hoisted to one view per chunk, or per chunk pair in the two-way
merge, whose inner loop runs until either cursor crosses a chunk boundary. The
k-way merge that reads over three or more chains works in rounds the same way:
each round borrows the current chunk of every input and heaps their updates, and
ends when an input crosses a chunk boundary. The heap orders updates directly,
so `MergeHeap` and `MergeCursor` are gone.
`Cursor` gained `chunk_handle`, `reads_from`, and `get_with` for callers that
hold a view across cursor steps. `get` and `index` remain the documented
single-access forms. Chain iteration, chunk splitting, and the time search
index a hoisted view likewise.

Holding a view inside the iterator that `updates_before` hands across the
persist writer's `await` needs the view to be `Send`, which is a new bound on
the container. The container bounds move into a `DataContainer` helper trait
so `Data` stays readable.

Insert improves 1.6x on a 4.19M-update append workload, and 2.0x under a memory
cap, where each redundant decode also faulted the header page back in. The new
`column_borrow` bench in `mz-timely-util` measures that decode: per-element
borrows of a serialized column against one hoisted borrow and a typed column.

`merge_many_consolidates_across_chunks` checks a three-way merge over chains of
several chunks each.

Co-Authored-By: Claude Fable 5.1 <[email protected]>
Co-Authored-By: Claude Opus 5.5 <[email protected]>
@antiguru
antiguru force-pushed the moritz/correction-borrow-hoist branch from ca33cdf to b736ed7 Compare September 30, 2026 18:07
@antiguru
antiguru merged commit f8f5184 into main Sep 30, 2026
83 checks passed
@antiguru
antiguru deleted the moritz/correction-borrow-hoist branch September 30, 2026 19:45
antiguru added a commit that referenced this pull request Sep 30, 2026
`compute_correction_v2_chunk_size` sizes `CorrectionV2`'s staging area,
not its chunks: chunk bodies are fixed at the columnar ship size. The
staging size sets how many updates accumulate before a chain is minted,
and every chain minted is a chain some later read has to merge. Raising
the default from 8 KiB to 2 MiB, one chunk body's worth, takes insert on
a 4.19M-update append workload from 3503 ms to 1897 ms, with drain and
peak RSS unchanged. These are medians of three `correction_mem` runs
with the rest of the stack applied and no pool installed. The curve is
monotone across the range (the new `bench_chunk_size` sweep in the
`correction` bench shows it), so the default is bounded only by the
per-sink, per-worker cost of the staging vector.

The stage counted its fill in tuples of `size_of::<(D, Timestamp,
Diff)>()`, which is 40 bytes for a `Row` however wide the row is, so a
byte-sized flag bounded neither the staging memory nor the reported size
once rows spill out of line. A new `DataBytes` trait on the buffer's
data types reports each datum's bytes with the heap included (`Row` via
`byte_len`, `DataflowErrorSer` via its serialized length), the stage
ships when the staged bytes reach the flag, and its size metrics carry
the same figure.

`stage_ships_by_bytes` checks that rows of two widths ship after the
number of updates their bytes predict.

That vector was allocated eagerly at the configured capacity and
re-allocated at that capacity on every flush. At 2 MiB per sink and
worker that is no longer free, so it now grows on demand and gives its
allocation back on flush.

The mzcompose and parallel-workload flag tables follow the new default,
since CI runs the value listed there rather than the compiled default.
The flag's description now says what it sizes.

First of four, split out of #38645: this, the O(1) metrics (#38895), the
per-chunk borrow hoist (#38896), and the pool substrate (#38897) land in
that order. Supersedes the fork PR #38647.

🤖 Generated with [Claude Code](https://claude.com/claude-code)

Co-authored-by: Claude Fable 5.1 <[email protected]>
@linear-code

linear-code Bot commented Oct 1, 2026

Copy link
Copy Markdown

CPU-279

This was referenced Oct 2, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants