Skip to content

Exact distinct-count cache sizes are fixed constants: calibrate them per machine #1369

Open

Description

@zzylol

Problem, by example

An exact COUNT(DISTINCT user_id) over 12,000,000 rows of 1,000,000 distinct users, ungrouped:

SELECT COUNT(DISTINCT user_id) FROM http WHERE ts >= now() - INTERVAL '20 minutes'

The cost (exact_distinct_value_operations_per_row in crates/cost/src/node/operations_per_unit.rs) charges a cache-miss term for its value table:

207 × cache_miss_fraction(1,000,000 values, EXACT_DISTINCT_VALUES_IN_CACHE = 200,000)
  = 207 × (1 − 200,000 / 1,000,000) = 207 × 0.8 = 166 operations per row

The 200,000 (values whose table still fits in the cache) and EXACT_DISTINCT_PAIRS_IN_CACHE = 500,000 ((group, value) pairs) were fitted on one machine type: 35 MB of L3 cache per socket. They are constants, so every machine gets the same knee:

machine value table fits up to charge for the example
the fitted machine (35 MB L3 per socket) 200,000 values 166 per row for misses
a machine with half the cache about 100,000 values (expected) still 166 per row; should be about 186 (0.9 miss)
a machine with 4× the cache about 800,000 values (expected) still 166 per row; should be about 41 (0.2 miss)

The rows for other machines are what the miss form predicts, not measurements; no other machine has been measured.

The measured time also moves with how busy the shared cache is. The same shape measured 393.5 ns per row on an idle core and 553.6 ns per row while other builds shared the cache (1.4×). By service (100 groups) it measured 510 against 653.

Why it happens

  • The exact distinct-count cost (refit in the exact COUNT(DISTINCT) refit PR, fix(cost): charge an exact distinct count per value and pair lookup that misses the cache; declare the production workloads' column-wide distinct users #1368) models a lookup into a hash table that has outgrown the cache as max(0, 1 − K / entries). K is a property of the machine (cache size, entry size), not of the algorithm.
  • K is stored as two consts in operations_per_unit.rs. Unlike other per-operation costs, nothing measures it per machine. Their docs say they are machine-specific defaults.
  • The fit only weakly pins the pair knee: the best value was about 3,000,000 pairs on one grid and 200,000–1,000,000 on the other, with errors within 0.01 of each other. Both grids ran on the same CPU model, so "across grids" was not a cross-machine check.

Proposal

  • The calibration harness (asap_run calibrate, [Design] asap_run: one binary to execute plans, calibrate measured unit costs per machine, and bench predicted vs measured #1317) measures the two cache sizes per machine key. It runs exact distinct counts over a small grid of distinct values (1e3 to 1e7) and group counts, and fits K for the value table and for the pair set. It writes both to <machine-key>/costs.json next to the other measured unit costs.
  • CostInputs carries them. exact_distinct_value_operations_per_row reads them from there, and the two constants stay only as the defaults used when no calibration exists (with the existing missing-calibration warning).
  • Alternative: derive K from the machine's cache size and the executor's entry size, without a measured fit. It is simpler, but it misses the effect of a busy shared cache and of the hash table's layout.

Second dependency: value skew

The fit also assumes values are uniform. The measurement grid draws user_id uniformly from U values (the expected distinct and pair counts are computed that way), so every value is equally likely to be a cache miss once the table outgrows the cache.

Example: SELECT service, COUNT(DISTINCT user_id) FROM requests GROUP BY service over 12M rows and 1M users.

  • Uniform users: the value table holds 1M entries, the miss fraction is 1 − 200,000 / 1,000,000 = 0.8, and the charge includes 207 × 0.8 = 166 operations per row for misses.
  • Zipf-skewed users (a few heavy users make most requests): the same 1M entries exist, but most lookups hit the hot entries already in cache. The real miss rate is well below 0.8. The charge stays at 166, so exact is over-charged and the planner leans toward a sketch.

This has not been measured.

Proposal (skew)

  • Add skew as a grid dimension: uniform, plus Zipf with exponent 0.8, 1.0 and 1.2, over the same distinct values, rows and group counts.
  • If predicted ÷ measured leaves 0.76–1.32 under skew, make the miss fraction depend on skew. Use the fraction of lookups that land on values outside the K hottest, instead of 1 − K/x. Under a Zipf law this fraction has a closed form in the exponent.
  • The planner then needs the skew as a data fact. Following the rule for undeclared facts, use a written default (uniform, the conservative choice for exact) and report it in SelectedPlanReport.assumed_data_facts when it is not declared.
  • Done (skew part) when the skewed grid is measured, and predicted ÷ measured stays within 0.76–1.32 on it, with or without the new fact.

Scope and acceptance

Related

Activity

  1. added
    cost-modelCost formulas, statistics, ranking, and selection
    enhancementNew feature or request
    on Nov 16, 2026
  2. zzylol commented on Nov 16, 2026

    @zzylol
    ContributorAuthor

    Skew measurement (no code change)

    Under Zipf skew the cost charged for an exact COUNT(DISTINCT) (main 79d9932) is too high by up to 5×. The skew fact is needed.

    Setup

    • 12M rows on one pinned idle core, median of 3 runs.
    • Each setting combines:
      • U ∈ {1e5, 1e6, 1e7} possible values;
      • grouping: none, 100 groups, or 10,000 groups;
      • Zipf exponent s ∈ {0, 0.8, 1.0, 1.2}.
    • The values are drawn by rank with probability ∝ k^−s, and the hot ranks are scattered over the value ids.

    Example (U = 1e7, no grouping), in ns/row:

    s distinct values seen measured charged measured ÷ charged
    0 6.99M 744 817 0.91
    0.8 4.32M 608 817 0.74
    1.0 2.22M 390 817 0.48
    1.2 641k 157 817 0.19

    Measured ÷ charged over the whole grid:

    charge computed from uniform rows (9) skewed rows (27) rows outside 0.76–1.32
    bound U 0.91–1.14 0.19–1.10 17
    distinct values actually seen 0.96–1.29 0.41–1.21 14

    What this shows:

    • Feeding the cost the distinct count actually seen is not enough.
    • Skew lowers the cost even when the value table fits in cache: at U = 1e5 the ratio falls to 0.54–0.69. So the effect is not only on cache misses. Lookups and inserts also change.

    Candidate formula (variant C). It keeps the merged form and takes everything from (U, s, rows, groups G):

    Formula part Under Zipf
    Distinct values D Σₖ (1 − e^(−rows·pₖ)), with pₖ = k^−s / H(U,s)
    Pairs P G · Σₖ (1 − e^(−(rows/G)·pₖ))
    Value miss fraction 1 − max(H(K_v,s)/H(U,s), K_v/D), where H(N,s) = Σ_{k≤N} k^−s
    Pair miss fraction 1 − max(H(K_p/G,s)/H(U,s), K_p/P)

    D and P match the counts actually seen to within 0.05%. At s = 0 every part reduces exactly to the current formula.

    Leave-one-setting-out over 155 points (this grid plus the two uniform grids):

    variant all points skewed rows
    A: miss fraction only 0.36–1.89 (RMS log 0.240) 0.36–1.39
    B: expected D and P only 0.56–1.62 (RMS log 0.227) 0.56–1.50
    C: A + B 0.70–1.43 (RMS log 0.150) 0.70–1.43 (RMS log 0.206)

    C does not yet meet the 0.76–1.32 acceptance. The residual follows s:

    • s = 0.8 is charged too little: measured ÷ charged is 1.22–1.43 at U ≥ 1e6.
    • s = 1.2 is charged too much: measured ÷ charged is 0.70–0.90.

    The hit mass of the hottest K values looks too optimistic at s = 0.8. A fitted factor on K under skew may close the gap; it is untested.

    Next

    1. Test the K factor.
    2. If it meets acceptance, add a test-first PR. The PR:
      • adds an optional per-column skew fact, with uniform as the default (it charges exact the most). When undeclared, the fact is reported in assumed_data_facts.
      • applies variant C to the exact distinct cost.
    3. Measure the same skew effect on the KMV/HLL build, because their insert rate also falls under skew. Otherwise exact and the sketches are charged inconsistently.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

cost-modelCost formulas, statistics, ranking, and selectionenhancementNew feature or request

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions