Skip to content

KMV insert and merge are O(k) and O(k²) in asap_sketchlib; unusable at the k the planner sizes #709

Open

Description

@zzylol

Problem

asap_sketchlib's KMV insert_by_hash does a linear scan for duplicates on every insert, and merge is O(k²). At the k the planner sizes (kmv_k_99: 40,002 at ε = 0.05, about 1e6 at ε = 0.01), building or merging a KMV is impractically slow. Found while reviewing the KMV kernel (#704).

To do (upstream, not a local copy)

  • In asap_sketchlib, check against the heap root first (a hash ≥ the current k-th smallest can be dropped immediately), and use a hash set for duplicate detection. Merge then becomes O(k log k).
  • Move the pin once it's merged or on a pin branch.

Related: #697, #704, #694.

Activity

  1. added
    bugSomething isn't working
    bindingLogical-to-physical binding and implementation selection
    on Oct 15, 2026
  2. zzylol commented on Nov 16, 2026

    @zzylol
    ContributorAuthor

    The grouped KMV build: measured on the executor

    The linear duplicate scan this issue describes is what makes a grouped KMV build slow. Example: SELECT region, COUNT(DISTINCT user_id) FROM t GROUP BY region, 300,000 rows in 4 groups, user_id uniform over 100,000 values, release build, one core.

    Query Plan Per row
    COUNT(DISTINCT user_id), no GROUP BY query-time KMV, one state, k = 4,323 191 ns
    ... GROUP BY region (4 groups) query-time KMV, k = 26,656 7.4 µs
    ... GROUP BY job (10 groups) query-time KMV, k = 26,656 6.6 µs
    ... GROUP BY region, exact exact distinct count 293 ns

    So the grouped build is 25x the exact distinct count it should beat.

    Cause. The executor's per-row work around the sketch is constant: build_per_group_summary (crates/executor/src/operators/summary/mod.rs) looks up each row's group and calls KmvAccumulator::update_value, which calls asap_sketchlib's Kmv::update. In sketchlib, update_with_hash (src/sketches/kmv.rs) checks the heap root only once the sketch is full; otherwise it compares the hash with every retained hash, one at a time (retained_hashes.iter().any(..)). A per-group state sees fewer rows and fewer distinct values than one state over all rows, so it stays below k for most or all of its rows, and nearly every row walks the whole heap. A single state fills early and then turns most rows away with one comparison.

    The expected number of retained hashes compared per row fits the measurements across 22 builds (100 to 10,000,000 distinct values, 1 to 1,000 groups, k = 4,323 and 26,656): 65 ns per row plus 0.50 ns per compared hash. For the 4-group build above, that is 13,820 hashes per row.

    The merge pays the same scan. Kmv::merge calls update_with_hash once per hash of the other sketch. A rollup of COUNT(DISTINCT user_id) from 1,000 (region, service) states (k = 106,263, 12,000 rows each, 1,000,000 distinct users) into 100 service groups takes 352 s; the plan's build takes 40 s and the two exact counts it replaces 14.7 s together.

    Planner side. The cost model now charges a KMV update and a KMV merge by this count (kmv_compared_hashes_per_row in crates/cost/src/node/operations_per_unit.rs, on #1363): 348 s charged for that rollup, 36.5 s for the build. So the planner stops picking grouped KMV builds and rollups that measure slower than the exact counts. When this issue is fixed, KMV_UPDATE_OPERATIONS_PER_ROW and KMV_OPERATIONS_PER_COMPARED_HASH must be measured again.

    Proposed fix (unchanged from this issue).

    1. In asap_sketchlib, keep a hash set of the retained hashes beside the heap (the values are already 64-bit hashes, so a pass-through hasher is enough), so the duplicate check is one lookup. merge then needs O(k) lookups instead of O(k²) comparisons.
    2. Move the ASAPPlanner pin to that commit.
    3. Measure the grouped build again. Target: within 2x of the one-state build's time per row, and below the exact distinct count's.

    #1366 (draft, merging stored windows by row position in SummaryMerge) does not touch this path.

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    bindingLogical-to-physical binding and implementation selectionbugSomething isn't working

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions