Label assignment sorts every chunk it does not need to: -26% wall at 10M variables

[FBumann]

Split out of #146, where the profiling lives. This is the actionable piece: one clause, measured, with the open questions that stop it being a trivial diff.

The statement

executor.py::_label_frame:

INSERT INTO {table}
SELECT {collist},
       {next_label} + ROW_NUMBER() OVER (ORDER BY {order_key}) - 1
FROM {from_clause}
WHERE t_{lead}.ord >= {lo} AND t_{lead}.ord < {hi} AND {where_clause}

The ORDER BY sorts every chunk. Isolated at 10M rows (16GB budget, best of three):

	time
OVER (ORDER BY t_snapshot.ord, t_generator.ord) — current	4.03 s
OVER ()	1.66 s
ord * card + ord (arithmetic, no window)	1.62 s
no label at all — the join floor	1.41 s

What it buys, end to end

A/B interleaved in one session, best of three, memory_limit=1GB:

case	build	total	vs linopy
dispatch 10M — before	5.50 s	9.38 s	2.44x
dispatch 10M — after	3.48 s	6.97 s	1.81x
transport 9.8M — before	7.20 s	11.86 s	2.59x
transport 9.8M — after	5.44 s	10.24 s	2.24x

Peak RSS also drops (0.88 -> 0.74 GB on dispatch), which is consistent with the sort being what materialises the chunk.

Why the order is not load-bearing for correctness

Labels only have to be a dense bijection, and denseness comes from the chunk filter plus the running offset, not from the sort. What the ORDER BY fixes is which coordinate gets which index — determinism, not validity. Evidence: with the clause removed the suite is 311 passed / 1 failed, and the one failure is test_walkthrough_matches_golden, whose committed output prints primal rows in label order. Every differential and parity test against the linopy oracle passes.

Operational finding 3 already says LP section order is free.

What has to be checked before it lands

1. solver_direct batching. A is streamed ORDER BY row, and within a row the column indices would no longer be ascending. HiGHS's addRows does not document a sorted-index requirement, but this needs a direct test rather than an assumption — it is the shipped path.
2. Reproducibility (LP output is not byte-reproducible: the file sinks emit unordered COPYs #109). LP output is already not byte-reproducible, but scrambled labels make runs differ from each other in a new way. If LP output is not byte-reproducible: the file sinks emit unordered COPYs #109 is ever fixed, a deterministic label order is likely part of the fix, so the two decisions are coupled. OVER () under multiple threads gives no ordering guarantee at all.
3. Locality of A. Ordered labels leave the COO roughly sorted, which may help the terminal GROUP BY row, col and the solver's CSR ingestion. The measurements above are net of any such loss on the lp_file path; solver_direct is unmeasured.
4. The arithmetic alternative. For an unmasked frame the label is ord_lead * card_rest + ord_rest — no window at all, deterministic, and the same 1.6 s. It only works when nothing is filtered out, so it would be a fast path beside the window rather than a replacement. Worth it if determinism turns out to matter, since it keeps both properties.

The walkthrough golden would need regenerating either way; that file is asserted line for line on purpose, so the diff is the visible part of the decision.

[FBumann]

Option 4 is not a consolation prize for option 1 — it dominates it

Investigated all four open questions. The short version: taking the arithmetic path instead of OVER () makes questions 1–3 stop existing, because it emits the same labels, not merely valid ones.

ROW_NUMBER() OVER (ORDER BY t_a.ord, t_b.ord, …) numbers the coordinate product in row-major order. With no mask every combination survives, so that rank is the mixed-radix value of the ord tuple. ord is dense 0..card-1 on every dim table (_create_dim_tables assigns it with its own ROW_NUMBER), and the chunk filter plus running offset already make the per-chunk base exact — so the closed form reproduces the window's output integer for integer.

Branch: claude/performance-issues-19xx4f.

The four questions, answered

1. solver_direct batching — not an issue, and not an assumption. Tested highspy directly: same LP, within-row column indices ascending vs reversed vs shuffled.

variant	status	objective	primal
ascending	kOptimal	150.093096286621	—
reversed	kOptimal	150.093096286621	identical
shuffled	kOptimal	150.093096286621	identical

Objective delta 0.0 in both cases. addRows does not care. Worth recording independently of this issue, since the code relies on it implicitly. (Note sinks/highs.py:64 does need a['row'] sorted — np.searchsorted — but that comes from ORDER BY row in the A query, which is untouched.)

2. Reproducibility (#109) — decoupled. Labels are unchanged, so this buys nothing new to be non-deterministic about. The two decisions are no longer coupled. OVER () would have coupled them.

3. Locality of A — no loss; if anything a gain. Interleaved runs show transport's emit phase, which this patch does not touch, going 5.39s → 4.62s. Physical row order of the label tables differs (the window emitted them sorted; the join does not, with preserve_insertion_order=false), and it came out ahead. Reporting it as an observation, not a claim — but there is certainly no locality penalty to trade against.

4. The arithmetic alternative — bigger than measured here, and the right default. At 10M rows, 1GB budget, best of three:

statement	time	labels
ORDER BY ord tuple (today)	4.37s	—
ORDER BY single BIGINT key	3.34s	identical
arithmetic, no window	0.56s	identical

7.8x, not the 2.5x in the issue body. And the walkthrough golden needs no regeneration — the diff you flagged as "the visible part of the decision" doesn't happen.

End to end

Interleaved baseline/patched in one session, best of three, memory_limit=1GB, size l. (4-core box, so absolute numbers are well above the ones in this issue — compare within the table.)

case	build before	build after
transport 9.8M	10.19s	6.52s	−36%
dispatch 10M	8.20s	8.02s	unchanged

The catch, and it is the interesting part

dispatch gets nothing — because bench/models/dispatch.yaml masks with where: "p_max > 0", and p_max is uniform(50, 150). The mask removes nothing and the model pays a full 10M-row sort for the generality.

That is the real remaining cost, and it is worth its own decision:

• Sorting on one computed BIGINT instead of the N-column tuple: 4.09s → 4.01s masked. Dud — the sort itself is the cost, not the key width. Ruled out by measurement, don't re-try it.
• Speculate and verify. Insert with the arithmetic label, then count(*); if it equals the full coordinate product the mask was vacuous and the labels are already right, otherwise throw the table away and redo with the window. count(*) on a materialised table is 2ms.

mask	window (today)	speculate + verify
vacuous (dispatch)	4.37s	0.63s	0.14x
biting (10% dropped)	3.71s	4.24s	1.14x

7x when the guard is vacuous, 14% when it bites. Guards that are almost always true (p_max > 0, cap > 0) are the common case, and 14% of label assignment is ~5% of build — but it is a real regression for genuinely sparse models, so it is your call rather than mine. Left out of the branch; happy to add it.

What landed

_row_major_label beside _label_frame, taken only when where is None. Plus two tests: one asserting unmasked labels are exactly the window's (three dims of distinct cardinality, both chunk regimes) and one that masked labels stay dense. Mutation-checked — un-reversing the strides, dropping the chunk offset, and widening the fast path to masked frames each fail the right test.

332 passed, 1 xfailed; ruff and pyrefly clean. Parity gate passes with bit-identical objectives against linopy on both cases.

---

Generated by Claude Code