Skip to content

KMV: pin the O(log k) sketchlib fix and recharge KMV builds, merges and memory at its measured cost #1394

Open

Description

@zzylol

Problem, by example

The DAG viewer's distinct-count rollup (tools/dag-viewer/memo-examples/sql/rollupheavy-t11-service-endpoint-5m.json) runs these two queries every 60 s, over 10,000 series sampled every 5 ms (600,000,000 rows per evaluation) with 1,000,000 users:

SELECT service, COUNT(DISTINCT user_id) AS value FROM http WHERE ts >= now() - INTERVAL '5 minutes' GROUP BY service
SELECT service, endpoint, COUNT(DISTINCT user_id) AS value FROM http WHERE ts >= now() - INTERVAL '5 minutes' GROUP BY service, endpoint

Each answer must be within 5% relative error.

A KMV answers both queries with less work than an exact count: it keeps only the k smallest hashes per group. On the executor today, though, KMV is barely faster than exact, and sometimes slower. Whole-plan measurements over the same data, at k = 4,323 and 1,000 states:

rows per state exact KMV (k = 4,323) faster
60,000 609.6 s 483.6 s KMV, 1.26×
12,000 127.9 s 178.4 s exact, 1.39×

A forced-KMV plan at k = 106,263 (a 5% target over 1,000,000 users) is worse still. It builds at 2.7 µs per row at 1.2M rows and 6.6 µs per row at 3M rows, and the cost per row keeps growing with the rows per group. The library's own update at the same k costs about 45 ns per key once it is fixed (below).

So KMV's measured benefit over exact is mostly hidden by an implementation defect, and the cost model is calibrated against that defect.

Why it happens

asap_sketchlib's KMV (Kmv::update_with_hash) checks for a duplicate by walking every retained hash (retained_hashes.iter().any(..)). It does this for every update while the sketch fills, and for every hash below the largest retained one after that. An update is O(k). Kmv::merge re-inserts the other sketch's k hashes one by one, so a merge of two full sketches is O(k²).

The profile of main at 79d99326e shows KMV update at 99.4% of the plan's CPU for the SQL distinct query. For the rollup, KMV update is 51% and KMV merge 46%.

The cost model follows the slow implementation:

The library fix (ready)

ProjectASAP/asap_sketchlib#264 (head e6ddbd7, closes asap_sketchlib#263):

  • Update: keeps the retained hashes in an open-addressing index beside the heap. Membership becomes expected O(1), and an update becomes O(log k): one probe and one heap sift.
  • Merge: selects the k smallest of the union with select_nth_unstable and heapifies them in O(k).
  • Unchanged: the retained set, the estimates and the ASAPv1 bytes stay bit-for-bit identical.

Measured in sketch-bench on 1,000,000 Zipf(1.1) u64 keys:

k insert ns/item, before → after one merge, before → after memory_bytes, before → after
4,323 210.0 → 10.6 8.80 ms → 0.193 ms 65,576 → 196,680
106,263 25,952 → 44.7 5,180 ms → 5.21 ms 1,048,616 → 3,145,800

It needs three decisions before it merges:

  1. Memory: accept 3× memory per state (the index holds twice the heap's slots). Recommended: yes. A sorted structure would save memory, but makes each update cost more.
  2. retained_hashes: make it private with a read-only accessor, so the heap and the index cannot drift apart. Recommended: yes.
  3. asap_sketchlib#228: close it. Its other changes already landed through asap_sketchlib#249, and it does not touch the scan or the merge. Recommended: yes.

Proposal

  1. Pin asap_sketchlib#264's commit in this repository (Cargo.toml). Do not wait for the sketchlib merge.
  2. Re-measure KMV on the executor over the same grid as fix(cost): charge KMV builds and merges their measured time (build 110 + 0.62, merge 2.6 + 0.43 per compared hash) #1375:
    • build: 132 settings, from 10 to 10,000 states, 1,200 to 60,000 rows per state, 10,000 to 1,000,000 distinct values, and k from 1,081 to 106,263;
    • merge: 45 settings, plus held-out rollups.
  3. Refit the cost model in crates/cost/src/node/operations_per_unit.rs:
  4. Handle fix(cost): charge KMV builds and merges their measured time (build 110 + 0.62, merge 2.6 + 0.43 per compared hash) #1375. Its build and merge constants describe the slow library, so this issue's refit replaces them. Its StateInputRows::distinct_values field is still needed: fix(cost): charge a counter-matrix sketch's state allocation, heap re-estimates, readout and merge, measured on the executor #1382 builds on it, and the new merge charge uses it. Either merge fix(cost): charge KMV builds and merges their measured time (build 110 + 0.62, merge 2.6 + 0.43 per compared hash) #1375 first and refit on top, or split out the field and close fix(cost): charge KMV builds and merges their measured time (build 110 + 0.62, merge 2.6 + 0.43 per compared hash) #1375 in favour of this refit. Recommended: split out the field.
  5. Rerun:

Acceptance

  • The KMV build and merge are each charged within 0.8–1.25 of their measured time, on the grid and on held-out shapes, with the pinned library.
  • The rollup's selected plan is the one that measures fastest end to end at both 60,000 and 12,000 rows per state. Report the measured sketch-versus-exact numbers for both.
  • The PR lists every plan the refit changes in the sweep.
  • The constants are refit from measurements, never tuned to make a test pass.

Related

Activity

  1. added
    bugSomething isn't working
    cost-modelCost formulas, statistics, ranking, and selection
    on Nov 17, 2026
  2. zzylol commented on Nov 17, 2026

    @zzylol
    ContributorAuthor

    The KMV cost refit is merged (#1375, squash commit 5ebca6c). It fits the build at 110 operations per row plus 0.62 per compared hash, and the merge at 2.6 per hash plus 0.43 per compared hash. Those numbers describe the pinned asap_sketchlib KMV, which walks every retained hash on each update. They are CostConstant::{KmvUpdateOperationsPerRow, KmvUpdateOperationsPerComparedHash, KmvMergeOperationsPerHash, KmvMergeOperationsPerComparedHash} in crates/cost/src/node/operations_per_unit.rs.

    Once the O(log k) fix is pinned, this issue's refit should replace those four constants. It should also revisit kmv_compared_hashes_per_row, whose O(k) walk model then no longer applies. The measurement grid and fit method are in #1375's body.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

bugSomething isn't workingcost-modelCost formulas, statistics, ranking, and selection

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions