Repository navigation
Description
Example
A top-10 of request counts by url (topk(10, sum by (url) (...)); the sketch-heavy survey's heavy-hitters workloads, e.g. cmsheap-topk10__u1000-i1-1hz-5m-every60s), planned two ways. The exact plan is a hash aggregate sum by (url), a top-10 sort and its output rows. The sketch plan is a query-time Count-Min or Count Sketch with heap and its top-10 read. Both arms were run on the executor (release build, thread CPU, median of 7 runs, pinned core) and compared with what the cost model charges at the head of #1382:
| Workload (top-k step) | Sketch measured | Sketch charged | Exact measured | Exact charged (estimated) | Exact faster by |
|---|---|---|---|---|---|
| Count Sketch + heap 7,500 × 81, 100 rows | 3.89 ms | 4.46 ms | 0.124 ms | ~0.28 ms | 31× |
| Count Sketch + heap 300 × 81, 100 rows | 3.43 ms | — | 0.125 ms | — | 27× |
| Count-Min + heap 272 × 10, 1,000 rows | 4.38 ms | 5.33 ms | 0.72 ms | ~2.76 ms | 6.1× |
| Count-Min + heap 272 × 12, 5,000 rows of 2,500 URLs | 23.8 ms | 30.2 ms | 1.91 ms | ~6.95 ms | 12× |
- Today: the sketch charges are 0.79–0.87 of their measurements, but the exact arm is charged about 2.2–3.8× its measured time. Plans still pick exact here, because the sketch is 6–31× slower.
- Expected: the exact arm is charged within the same error as the sketch arm, so the cheaper plan wins on its measured time.
The exact charges are estimates: they were derived from the CPU differences between the sketch-heavy survey's base and exact-only runs, not read from one node's charge. The sketch arm is the keyed build plus the top-10 read; the exact arm is sum by (url), the top-10 sort and the projection.
Current behavior
Exact top-k is charged from constants that were never measured against the executor's own exact top-k path:
- the hash aggregate's per-row work (
hash_aggregate_operations_per_rowincrates/cost/src/node/operations_per_unit.rs), where a top-k measure addsHASH_AGGREGATE_OPERATIONS_PER_FURTHER_KEY, documented as not measured; - the top-k sort over the aggregated groups (the
Sortnode's charge incrates/cost/src/node/usage/mod.rs, atSORT_OPERATIONS_PER_ROW_PER_LEVELper row and level); - one output row per group at
OUTPUT_ROW_OPERATIONS_PER_GROUP.
Which of these terms carries the over-charge has not been split yet.
Expected behavior and invariant
For a top-k query the exact arm and the sketch arm are both charged within the fit's error of their executor measurements, so the comparison between them is not biased toward either.
Why this blocks the executor heap fix
The executor's weighted-frequency kernel (crates/executor/src/summary_kernels/weighted_frequency.rs, update_key) calls rescore_heap() after every update. That re-estimates every heap resident per row, so a row costs (heap size + 1) estimates. #1382 charges that cost as measured. A planned executor fix offers only the touched key to the heap, which is the textbook heavy-hitter algorithm and keeps every certified guarantee. The review of #1382 measured what it would save:
- kernel time per row drops from 3,608 to 596 ns for Count-Min at depth 10 (6.1×), and from 4,495 to 685 ns at depth 12;
- it drops from 29.0 to 6.6–9.1 µs for Count Sketch at depth 81 (3.2–4.3×);
- the sketch arm would then measure about 1.37 ms, 4.7 ms and 1.9 ms on the rows above, and exact would still win by 1.9×, 2.5× and 15×.
But once the heap constants are re-measured for that fix, the model would charge the Count-Min sketch 0.53 ms against exact's 2.76 ms on the 272 × 10 row. It would pick the sketch, which runs about 1.9× slower.
So the executor heap fix must ship together with an exact top-k recalibration, in the same PR or before it. Otherwise the planner would pick a slower sketch.
Minimal reproduction
The review's harness times both arms on the executor's own operators: the keyed sketch build and top-10 read against a hash aggregate sum by (url), a top-10 sort and the projection, over 100 to 5,000 rows. The same shapes are then charged through node_resource_usage_and_cost.
Impact
Plan choice for every top-k and heavy-hitter query. Today the bias is hidden: the sketch's own per-row heap cost is larger still. It shows as soon as the heap cost falls.
Regression test
In crates/cost, a test like counter_matrix_sketches_are_charged_their_measured_time for the exact arm: for the four shapes above, each exact top-k plan's charged node costs (hash aggregate, sort, output rows) fall within the fit's measured ÷ charged range of their executor measurements. It fails today, where measured ÷ charged is about 0.26–0.45.
End-to-end verification
Re-run the sketch-heavy plan survey (its 25 top-k workloads) with three arms: today's constants, the recalibrated exact top-k plus the re-measured heap constants, and exact only. Report each plan's absolute cost per evaluation, and measure 3 changed plans on the executor (measured against charged).
Related
- [Bug] The cost model does not charge for a sketch's width: a query-time Count Sketch costs the same at 24,300 or 607,500 counters #1381 and fix(cost): charge a counter-matrix sketch's state allocation, heap re-estimates, readout and merge, measured on the executor #1382: query-time sketch size and heap work are charged.
- The executor heap fix:
weighted_frequency.rsupdate_keystops callingrescore_heap()per row. After it, the four*_HEAP_OPERATIONS_PER_ESTIMATE*constants incrates/cost/src/node/operations_per_unit.rsmust be measured again.
Activity
[-][Bug] Exact top-k is charged 2.2–3.8× its measured time, so a faster heap sketch would be picked over a faster exact plan[/-][+][Bug] Exact top-k is charged 2.2–3.8× its measured time; with the executor heap fix the planner would pick a slower sketch[/+]