Repository navigation
[Performance] Stage 3's compile check is quadratic in panes since #988 (scan_window, time_range_window) #993
Description
Example
workload_file_with_a_range_evaluation_is_planned (crates/devtools/tests/stage_pipeline.rs:1164) fails on main. It runs --exhaustive with a 30 s budget.
| Commit | Plans evaluated in 30 s | Selected | Cost/s |
|---|---|---|---|
f4eac007 (before #988) |
13 | joint-plan-6 | 460.04 |
f06a5556 (#988), 249ebd23 |
2, then time_limit |
joint-plan-1 | 719,154.73 |
Prices did not change: joint-plan-1 is 719,154.73 at both commits. With --milp-time-limit-s 900, main still reaches 460.04, after 105 evaluations. The search is slower, so it stops before it reaches the cheap plan.
Main's CI did not catch this. CI stopped at the stale planner_fuzz #902 test first, which #992 fixes.
Current baseline
The executor compile check runs once per candidate.
| Candidate | Panes | Before #988 | After #988 | Where the time goes after #988 |
|---|---|---|---|---|
| joint-plan-1 | 9,375 | 2.68 s | 10.9 s | 4.1 s in 2 calls to PhysicalASAPDAG::scan_window, 3.8 s in 18,750 calls to time_range_window |
| joint-plan-2 | 25,000 | 7.3 s | > 35 s (hits the deadline) | 29.4 s in scan_window |
Cause:
scan_windowandtime_range_window(crates/types/src/ir/physical_export.rs:372,:428) find each node with a linearnodes.iter().find.scan_windowalso rescans every edge for each TimeShift reader.- The executor calls both once per Scan and per TimeRange on the pane-expanded DAG (
crates/executor/src/physical_planner/mod.rs:228,:733,:813).
So the compile check is quadratic in the number of panes.
Metric and target
The compile check stays linear in DAG size, and the test selects the 460.04 plan within its 30 s budget again.
Correctness constraints
Both functions return the same windows. Prices do not change.
Measurement method and acceptable variance
The test above, plus per-candidate compile-check time for joint-plan-1 and joint-plan-2.
Possible fix: index nodes by id and edges by producer once per DAG, or reuse the compile's nodes / dependencies maps. #988 already lists "Look nodes up by id once in scan_window / time_range_window" as a follow-up. #949 (remove the compile check from plan selection) would also avoid this cost.
Activity