Reuse a finer aggregate through a compensating filter and a rollup of values or states (view matching) #950

Problem, by example

The workload of #902: p90 of value over the last 5 minutes on metrics, every 10 s. Each query below could be answered from a finer query of the same workload that is already computed, but the planner offers no such candidate. The reasons in the last column come from reading the rule code, not from a planner run.

Expected: in each case the coarse query gets a candidate that reads the finer query through a compensating filter and, when needed, a rollup. Plan selection compares it with the query's own candidates.

Why it happens

Reuse of a finer aggregate is split across two rules, and each covers one fixed shape:

• memo/rules/filtered_group.rs (from A filtered query (city = 'NYC') doesn't read its group from a grouped summary another query builds #902) covers exactly one shape:

  • the coarse query is a global aggregate with a single Quantile measure;
  • the finer query groups by exactly one key;
  • the coarse scan has exactly one extra key = literal conjunct.

  It reads the finer result and wraps it in MIN, so that an absent group yields SQL's one NULL row.

• memo/rules/rollup.rs, with rollup_candidates_of in asap_aware_cse.rs (from [Bug] An exact coarser grouping does not roll up the finer exact result #923), covers a coarser grouping over the same rows. Exact accumulators regroup their finalized values (rollup_kind), and sketches regroup their states (SummaryMerge { group_by }). There is no compensating predicate.

Both rules answer the same question, which is standard view matching for aggregation queries.

Prior work

• Optimizing Queries Using Materialized Views: A Practical, Scalable Solution (SIGMOD 2001), §3.3. An aggregation query is computable from a view when:

  1. the view's SPJ part produces every row the query needs;
  2. the columns of the compensating predicates are in the view output;
  3. the query's group-by is a subset of the view's (the empty set included);
  4. the columns of the compensating group-by are in the view output.

  The compensating predicates come out of the equality, range and residual subsumption tests (§3.1). Equal group-bys need no further aggregation; a strict subset adds a compensating group-by. Rollup is defined for count(*) (a SUM of counts) and SUM. §4 indexes the views by a filter tree (source tables, output columns, residual and range constraints, grouping columns), so not every pair is matched.

• Apache Calcite (docs).

  • SqlAggFunction.getRollup(): each aggregate function declares its own rollup, or null. COUNT → SUM0; SUM, MIN, MAX, ANY_VALUE → themselves. The rules call only this method; there is no table of measure classes.
  • SubstitutionVisitor.unifyAggregates has two branches:
    • Same level: the group sets are equal, or every group column the query drops is pinned by a constant condition (constantCondInputRefs.containsAll(compenGroupSet)). The substitute is a Calc (compensating filter and project) over the view, with no aggregate. Holistic measures work here because they need no rollup.
    • Coarser: an Aggregate by the query's group set, with one getRollup() call per measure, over the compensating Calc. MaterializedViewAggregateRule rolls up the same way.

• The Cascades Framework for Query Optimization (IEEE Data Eng. Bull. 1995) lists "schema-specific rules for materialized views" but gives no matching rule. DataFusion has no built-in rule of this kind; only its documentation was searched.

This design follows Calcite's structure and adds two things Calcite lacks:

• SQL's empty-input row for a global query. In Calcite's same-level branch, the Calc yields no row when the pinned group is absent. I saw no special case for this in that code path, but did not run Calcite. A filtered query (city = 'NYC') doesn't read its group from a grouped summary another query builds #902 requires the row.
• Summary states. A finer measure column can be a state; its rollup is a state merge, which also exists for families whose values do not roll up (KLL quantiles).

Proposal

Terms

Compensating is the view-matching term used by the paper and Calcite. A finer result holds at least the rows a query needs, usually more and in finer groups. A compensating operation is what is added on top of it to close that gap, so that the output equals the query's result:

• compensating filter: the query's conjuncts that the finer aggregate lacks. It removes the extra rows.
• rollup (the paper's compensating group-by): merges finer groups into the query's groups.

Example B:

finer: SELECT city, host, sum(value) … GROUP BY city, host
query: SELECT sum(value) … WHERE city = 'NYC'

finer ▸ Filter(city = 'NYC') ▸ Aggregate(SUM)
        └ compensating filter ┘ └─ rollup ─┘

If the finer result lacks rows the query needs (for example, the finer query itself has city = 'SF'), no compensation exists and match_finer returns None.

Worked examples

The finer result below is already computed:

SELECT city, host, sum(value) AS s FROM metrics GROUP BY city, host

5. State rollup (example C). The finer query is p90 … GROUP BY city, answered by one KLL per city: (NYC, KLL₁), (SF, KLL₂), (LA, KLL₃). The query is p90 … WHERE city IN ('NYC','SF'). Two p90 values cannot be combined, but two KLL states can: Filter(city IN ('NYC','SF')) ▸ SummaryMerge(KLL₁ + KLL₂) ▸ estimate p90. The Filter must stay State so that SummaryMerge accepts it (§4).

6. No match (None).

1. Match two logical aggregates

/// A logical aggregate in normalized form: the scan's predicates and the
/// Filters above it form one conjunct set.
struct AggregateShape {
    source: SourceId,
    window: TimeWindow,
    predicates: Vec<Predicate>,
    group_by: KeySet,
    measures: Vec<AggIntent>,
}

/// How a query aggregate is computed from a finer one.
struct FinerAggregateMatch {
    /// The query's conjuncts that the finer aggregate lacks, over the finer
    /// group-by columns.
    compensating_filter: Option<Predicate>,
    /// The query's group-by, when a rollup is needed. `None` at the same
    /// level: equal group-bys, or every dropped finer key pinned by an
    /// equality in `compensating_filter`.
    rollup_by: Option<KeySet>,
}

fn match_finer(query: &AggregateShape, finer: &AggregateShape) -> Option<FinerAggregateMatch>;

match_finer succeeds when:

• the source, the window and the measures are equal;
• the finer conjuncts are a subset of the query's;
• every remaining conjunct compares one finer group-by column with a literal (=, IN, <, <=, >, >=), joined by AND;
• query.group_by ⊆ finer.group_by.

It reads no implementation and no family.

2. One rollup function per measure (Calcite's getRollup)

/// How the finer column of `measure`, realized by `family`, merges into
/// coarser groups; `None` when it cannot.
fn rollup(measure: &AggIntent, family: &FieldDataType) -> Option<Rollup>;

enum Rollup {
    /// A value column: sum and count → Sum; min; max (`rollup_kind`).
    Value(ExactKind),
    /// A state column: merge states (`FamilyCapability::merge_inputs`).
    States,
}

Whether the substitute reads values or states is not a separate case. It follows from how the finer implementation candidate represents the column. Both variants are derived from the existing FamilyCapability, so there is no new table.

3. Two substitute shapes

The finer side is a reference to its memo group, a leaf of the substitute (Cascades' group binding).

rollup_by = None:  finer ▸ Filter(compensating_filter) ▸ Project
                   For a global query, a single-row aggregate on top keeps
                   SQL's one NULL row (0 for count) on an empty selection.

rollup_by = Some:  finer ▸ Filter(compensating_filter) ▸ merge, where merge is
                     Value:  Aggregate(by rollup_by, one rollup per measure)
                     States: SummaryMerge { group_by: rollup_by } ▸ the query's estimate/finalize
                   Any measure whose rollup() is None → no candidate.

The substitute becomes one more candidate of the query group through append_reader, which checks the output contract.

4. IR change: Filter over a state stays a state (decided 2026-10-27)

A Filter whose predicate reads only the child's plain (key) columns over a State child yields State. It selects state rows and does not change them. This mirrors the existing Project case in non_asap.rs output_kind, which keeps State when it keeps a state column. The alternative, a filter field on SummaryMerge, was rejected because it touches the executor and every SummaryMerge consumer. Only the States path (example C) needs this change.

5. Pair groups through an index

Bucket the memo groups by (source, window, measures), the top levels of the filter tree, and run match_finer only within a bucket. This replaces the O(G²) loops of both current rules.

Guarantees

These are unchanged and use the existing recomposition:

• At the same level, each row keeps the finer group's guarantee; filtered_group_preserves_sql_empty_and_null_semantics tests this.
• A filter selecting several groups does not get a single-group rank bound.
• States uses the merged-state guarantee, with the shared build sized for all readers.

Code layout

• memo/rules/finer_aggregate.rs holds AggregateShape, match_finer, rollup, the two substitute builders and the bucketed pairing. It replaces filtered_group.rs and add_rollup_candidates in rollup.rs.
• The rollup part of asap_aware_cse.rs (rollup_candidates_of, regrouped, rolled_up) calls match_finer and rollup, or is deleted once the memo rule covers it.
• add_window_rollup_candidates (newest panes of a longer chain) stays. In these terms it is a compensating time range.

Scope and acceptance

In scope:

• examples A, B and C;
• every case the current rules cover. The A filtered query (city = 'NYC') doesn't read its group from a grouped summary another query builds #902, [Bug] An exact coarser grouping does not roll up the finer exact result #923 and SQL top-k by COUNT(*): sketch candidates are misplaced (per-host CMS/UnivMon, heap over exact counts); no CMS+heap over raw rows #886 regressions in sharing_issue_regressions.rs and identical_exact_queries keep passing.

Out of scope for the first version:

• AVG (the paper's SUM / count);
• grouping by functional dependency;
• OR and expressions in the compensating filter;
• conjuncts on non-key columns;
• HAVING and per-measure filters;
• the window dimension.

Acceptance:

• Failing-first tests in which A, B and C each get a reuse candidate, selected when it is cheaper.
• Negative tests:
  • a conjunct on a non-key column;
  • an unpinned dropped key under a quantile;
  • a range filter, which must not keep a single-group rank bound.
• An IR test: a Filter on key columns over a state is State; a Filter reading a state column is rejected or stays a Relation.
• An executor check of empty and NULL input for the same-level global case.

Open questions

1. Should the window rollup join this rule as a compensating time range now, or later? Recommended: later.
2. Should AVG be supported through SUM / count in the first version? Recommended: no.

Related

#902, #923, #924, #886, #680; #943 added filtered_group.rs.