Skip to content

KMV build is charged 0.61–0.85 of its measured time; the library's O(k) duplicate scan dominates it #1373

Closed

Description

@zzylol

Example

The viewer's distinct-count rollup workload (tools/dag-viewer/memo-examples/sql/rollupheavy-t11-service-endpoint-5m.json):

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

every 60 s, 5% relative error per value, over 10,000 series sampled every 5 ms (2,000,000 rows per second, 600,000,000 rows per evaluation) and 1,000,000 users.

With the per-value δ split of the open PR on fix/delta-split-over-dependent-readouts, the planner answers both queries from one KMV at k = 4,323 built by (service, endpoint): 60,000 rows per state. The build is charged 553 operations per row. On the executor it measures 712–757 ns per row at that shape (400 states over 24,000,000 rows: 712; 1,000 states over 60,000,000 rows: 757). On main the same plan sizes the KMV at k = 26,656 and picks exact, so this under-charge only starts deciding plans once KMV is sized at k = 4,323.

Measured on the executor in two whole-plan runs over the same data (1,000 states, 1,000,000 users), scaled to one evaluation:

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

The plan should follow those measurements. It should read a KMV at 60,000 rows per state and count exactly at 12,000. The planner's choice is only right if each plan is charged its measured cost.

What happens today at 12,000 rows per state. On the δ-split branch, the planned 12,000-rows-per-state shape (10,000 series sampled every 25 ms, 120,000,000 rows per evaluation) already picks exact. An earlier probe that reported KMV there changed only arrival.rows_per_second. The planner prices a scan from series_count and sample_interval, so that probe still planned 600,000,000 rows. The wrong charge is the KMV build itself, at every shape measured (below).

Current behavior

update_operations_per_row (crates/cost/src/node/operations_per_unit.rs) charges a KMV row KMV_UPDATE_OPERATIONS_PER_ROW (65) plus KMV_OPERATIONS_PER_COMPARED_HASH (0.5) × kmv_compared_hashes_per_row(k, rows_per_state, distinct_values). Those constants were fitted on 28 builds of 300,000 rows. Measured over a wider grid (132 builds: 10 to 10,000 states, 1,200 to 60,000 rows per state, 10,000 to 1,000,000 distinct values, k = 1,081 to 106,263), every build is under-charged: measured ÷ charged is 1.17–1.63.

states × rows per state, distinct values, k charged ns/row measured
400 × 60,000, 1,000,000, 4,323 553 712
2,000 × 12,000, 1,000,000, 4,323 1,249 1,647
1,000 × 1,200, 1,000,000, 4,323 369 513
10 × 60,000, 1,000,000, 106,263 14,483 16,951

Cause: the library's linear duplicate scan

Most of the cost is asap_sketchlib's Kmv::update_with_hash. Before it inserts a hash below the state's largest, it walks every retained hash to check for a duplicate, so an update is O(k) while the state fills and for every hash that enters it. Kmv::merge updates the target with each of the other state's hashes, which makes a merge of two k-hash states O(k²). This is a library defect, not a property of KMV. Two changes fix it:

  • O(1) or O(log k) membership (a hash set beside the heap, or a sorted structure);
  • an O(k) sorted merge.

That library fix lands as a separate asap_sketchlib PR, which this repository then pins. The KMV build and merge constants must be measured again after it.

Expected behavior and invariant

The KMV build is charged its measured time per row across rows per state, k, groups and distinct values, and the KMV merge its measured time per inserted hash. The plan the planner picks is then the one that measures faster.

Proposal

  1. Refit the build's constants on the executor as it is today (the linear scan included), by leave-one-setting-out error as in the exact distinct refit. Charge a constant per row plus a constant per compared hash (kmv_compared_hashes_per_row, which already counts the walk over the retained hashes, k·ln(n/k) of them once the state is full). Add terms for heap inserts or cache misses only if the measurements support them.
  2. Give the KMV merge its own constants, so the build's refit does not move a merge cost that has not been measured again.
  3. After the library fix, measure both again.

Regression test

  • asap-cost: a KMV build is charged within 0.8–1.25 of its measured time at several measured shapes. It fails today: at 600,000 rows by job (10 states) at k = 1,081, the charge is 109 ns per row against 176 measured.
  • rollup_controlled: the rollup reads a KMV at 60,000 rows per state, and counts exactly at 12,000 rows per state (a sample every 25 ms).

Related

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