Repository navigation
Plain Count-Min still uses the portable CountMinSketch: drops nonpositive weights, reuses row seeds past 20 rows #725
Description
Problem, by example
A plain Count-Min summary (SketchAlgorithm::Cms, no heap) is still built by the executor through asap_sketchlib's portable CountMinSketch. Every other frequency family (CountSketch, CMS-with-heap, CountSketch-with-heap) now uses the per-row-seeded Float64 weighted frequency kernel (#706, #721).
Example: a Count-Min point query over sum by (path) (rate(http_requests_total[5m])). The weights are per-path rates, so they are Float64, and with no declared counter type they may be ≤ 0. Say the Count-Min shape has depth 25.
Today (portable CountMinSketch) |
Expected | |
|---|---|---|
a weight of 0.0 or -1.5 |
silently dropped | rejected (Count-Min needs non-negative weights), as the weighted kernel does |
| rows 21–25 | hashed with the same seeds as rows 1–5 (SEEDLIST[r % 20]), so they are not independent |
every row independently seeded |
approx_memory_bytes |
a fixed 16 KiB | the actual matrix size (25 × width × 8 bytes) |
| reading the total count | copies the whole matrix | read in place |
The first two break the planner's certified bound: the failure probability assumes independent rows and that every update is counted. The third makes Stage 3's memory price wrong for this family.
Cause
The plain Count-Min family was not moved in #721. Moving it onto the weighted frequency kernel (capacity 0) changes the DAG's stored Count-Min state type.
Proposal
Build plain Count-Min through WeightedFrequencyUpdater with capacity 0, as plain CountSketch already is. Update validate_state and any stored-state fixtures for the new state type.
Scope / acceptance
- Regression tests that fail today: a depth-25 Count-Min has 25 distinct row seeds; a negative weight is rejected, not dropped; memory reports the real matrix size.
- Example outputs (selected plans and costs) are unchanged, or any change is explained.
Status / related
Deferred by decision on 2026-10-15; not scheduled. Related: #706, #721, upstream ProjectASAP/asap_sketchlib#230 (which notes the native >20-row seed reuse).
Activity