Skip to content

Plain Count-Min cannot answer a per-item frequency lookup: COUNT(*) WHERE url = 'x' never gets a CMS point query #1378

Open

Description

@zzylol

Example

A per-item frequency lookup over the synthetic clicks table (100,000 rows/s, 1,000,000 distinct URLs declared), every 60 s:

SELECT COUNT(*) FROM clicks
WHERE url = 'url-00042' AND ts >= now() - INTERVAL '3600 seconds'
-- accuracy: absolute_stream_l1, max_error 0.001, failure_probability 0.05, whole_result

This is the textbook Count-Min point query, "how often did item x occur in the window". Today the memo has no sketch candidate for it at all:

  • The URL predicate is pushed into the Scan.
  • Pass 1 offers only ExactAggregate(Count) states over the filtered rows, either a query-time build or a tumbling-window chain.
  • The selected plan is exact, at 5.36 /s.

Measured on main 2f3664d1f with the sketch-heavy study's planning driver (default deployment and cost model). The workload is tools/dag-viewer/workloads/sketch-heavy/blocked-sql-point-count-one-url__100000rps-3600s-every60s-l1eps0.001-d0.05.json.

For this single, predictable URL the exact filtered counter is the right plan. The gap shows when the item is not one fixed value:

  • many such queries, each with a different URL;
  • ad hoc lookups of any URL;
  • raw data not retained (MVP), where an exact answer for an arbitrary URL needs a count per URL.

One Count-Min state over the unfiltered rows answers all of them in bounded memory. The planner cannot consider that plan, because it never forms the readout.

Why it happens

  • Only the bare total maps to Count. SketchStatistic::for_intent (types/src/summary_type/statistic/mod.rs:46) maps AggIntent::Count to PointCount { key: SampleValue, value: None }, the bare total. Nothing produces PointCount { key: url, value: Some("url-00042") }, the per-item lookup that StatisticKind::ItemFrequency (summary_type/capability.rs:57) already names.
  • A total-only CMS always loses. For a bare total, an exact counter is always cheaper than a Count-Min state. So plain CMS is never selected, in this or any other workload of the sketch-heavy set.
  • The filter is gone before Pass 1 runs. The equality predicate on the item column is pushed into the Scan. Pass 1 sees a count over already-filtered rows, not "a count of rows whose url equals a literal" over the full stream.
  • The executor answers only the total. The Count-Min kernel answers only the total (executor/src/summary_kernels/count_min_sketch.rs:61). query_key exists, and Hydra-CMS already answers PointCount { value: Some(_) } (summary_kernels/hydra_cms.rs:143).

Proposal

  1. Recognize the shape. Recognize COUNT(*) (or SUM(w)) with an equality predicate on one column, item = literal, as a candidate for PointCount { key: item, value: Some(literal) }. Read it from a Count-Min state over the unfiltered input, keyed by item.
    • Keep the exact filtered counter as the other candidate.
    • PromQL's count(m{item="x"}) / sum(...) over a label is the same shape.
  2. Guarantee. Give the readout Count-Min's point-query guarantee (absolute, stream-L1 scaled ε, failure probability per lookup), so the existing sizing applies.
  3. Sharing. Point queries for different items, or a point query next to a top-k over the same key, can then share one Count-Min (or CMS + heap) state.
  4. Executor. Extend the Count-Min kernel's estimate to PointCount { value: Some(_) } through query_key. Executor gaps do not limit the planner design, so this can land separately.

Scope and acceptance

  • In scope: the candidate, its guarantee, and a snapshot that pins it.
  • Out of scope: range or prefix predicates (url LIKE 'x%').
  • Acceptance:
    • The example's memo contains a Count-Min SummaryEstimate PointCount { key: url, value: Some("url-00042") } candidate that is not pruned.
    • A workload with many URL lookups, or the same lookup under MVP, selects it where it is cheaper.
    • The single-URL example above may stay exact.

Related

Activity

  1. added
    accuracyAccuracy requirements, guarantees, and propagation
    enhancementNew feature or request
    optimizerWorkload optimization and plan selection
    promqlPromQL front-end lowering (L1→L2)
    sqlSQL front-end lowering (DataFusion → L2)
    on Nov 16, 2026
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

    accuracyAccuracy requirements, guarantees, and propagationenhancementNew feature or requestoptimizerWorkload optimization and plan selectionpromqlPromQL front-end lowering (L1→L2)sqlSQL front-end lowering (DataFusion → L2)

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions