matrixorigin / matrixorigin/matrixone

[Enhancement]: Eliminate bounded aggregates grouped by a complete primary key

Open
#27,730 1 comment 0 reactions 1 assignee Claimed by @Ariznawlll View on GitHub
area/performance kind/enhancement needs-triage
Dominant language
Go
Stars
1.9k
Forks
311
Avg merge
1d 3h
Merged PRs (30d)
768

Description

## Summary

For a direct table scan grouped by every component of its declared primary key, each group contains at most one visible row. A grouped aggregate is therefore redundant: supported single-row aggregates can be expressed as row expressions. When the query has bounded demand, deleting the aggregate also exposes the existing scan `LIMIT` pushdown and can change work from O(N) scan/hash/state to approximately O(K + OFFSET).

This issue tracks that proof-gated planner optimization. It does **not** track a generic Aggregate-to-Top runtime callback.

## Example and exact transformation

```sql
create table t (
id bigint primary key,
v bigint
);

select id, count(*), sum(v)
from t
group by id
limit 10;
```

Established plan shape:

```text
Limit/Project
-> Aggregate(group by id, count(*), sum(v))
-> TableScan(t)
```

Proven rewrite:

```text
Project(id, 1, cast(v as aggregate-result-type))
-> TableScan(t, limit 10)
```

The saving occurs before execution: the hash aggregate is removed, and for an unordered bounded query the storage reader can stop after satisfying the source demand instead of scanning and grouping the complete relation.

With `ORDER BY`, aggregate elimination may still remove hash work, but Sort remains a semantic barrier and the scan must remain complete.

## Why the original runtime-fusion direction was rejected

Two prototypes were evaluated before selecting the planner proof:

1. A generic Group-to-Top callback still scanned, hashed and aggregated every row and retained all group states until EOF. It reduced neither scan nor hash work and regressed a 10M integer COUNT case by 14.6%.
2. A narrower GROUP_CONCAT chunk finalizer reduced clean-process peak RSS by only about 2% and wall time by about 1% in its activating case. That did not justify a new cross-operator ownership protocol.

The accepted design therefore introduces no Group/Top callback, finalization interface, protobuf/RPC change, or colexec hot-path change.

## First-principles proof and eligibility

All conditions must hold; otherwise the established plan is retained:

1. bounded `LIMIT` demand reaches the aggregate only through unary Project, Filter, or Sort nodes;
2. demand does not cross Join, Union, shared CTE, grouping-family, or another multi-input boundary;
3. the aggregate has one direct `TABLE_SCAN` child;
4. the scan exposes a real declared primary key, not a synthetic/fake key;
5. every primary-key component appears as a direct grouping column from that scan;
6. grouping-set keys are all active;
7. every aggregate is a supported non-DISTINCT, unconfigured single-row aggregate;
8. every replacement expression is semantically equivalent and total over the complete source-value domain. If its result conversion can overflow or otherwise change error behavior, the rewrite must fail closed.

Initial supported laws are:

- `COUNT(*) = 1`;
- `COUNT(expr) = IF(expr IS NULL, 0, 1)`;
- `SUM`, `AVG`, `MIN`, `MAX`, and `ANY_VALUE` equal the single argument converted according to the aggregate result contract.

The conversion requirement is a proof obligation, not an assumption. High-precision DECIMAL boundaries, NULL behavior, unsigned maxima, ENUM/SET display semantics, CHAR padding, temporal and binary types must be covered or rejected.

## Semantic boundaries

- WHERE remains before grouping; a filtered subset of a primary key remains unique.
- HAVING must be evaluated before result demand is consumed. If it is represented on the scan, scan filtering must precede scan LIMIT/OFFSET.
- ORDER BY may permit aggregate elimination but must block unordered scan-limit pushdown.
- `SQL_CALC_FOUND_ROWS` must preserve the complete input stream needed by `FOUND_ROWS()`.
- DISTINCT/configured/unsupported aggregates and incomplete composite keys retain Aggregate.
- An aggregate-bearing query without LIMIT deliberately retains the established plan to bound rollout risk.

## Non-goals

- This optimization does **not** optimize ClickBench Q35 from #27685 because `hits.URL` is not proven unique. #27685 remains open and requires a separate exact design.
- It does not perform early eviction of arbitrary groups, approximate heavy hitters, ordered-prefix grouping, metadata aggregation, or distributed local TopK.
- It does not change spill, cancellation, lifecycle, ownership, or wire protocols.

## Acceptance criteria

1. Eligible plans remove Aggregate; unordered plans push correct `LIMIT/OFFSET` to TableScan, while ORDER BY and `SQL_CALC_FOUND_ROWS` retain a complete scan.
2. Results and errors match the established plan for NULLs, signed/unsigned numerics, DECIMAL precision boundaries, strings/collations/padding, ENUM/SET, temporal/binary values, HAVING, OFFSET, prepared LIMIT, and volatile expressions.
3. Full and partial composite-key cases prove respectively eligible and fail-closed behavior.
4. Join, Union/shared CTE boundaries, grouping sets, DISTINCT/configured/unsupported aggregates, no-PK tables, and unbounded queries retain the established plan.
5. At least one realistic high-cardinality bounded case shows a large wall-time and scan/hash-work reduction; non-eligible/unbounded controls remain within 3% outside ordinary measurement noise.
6. Planner UT, full `pkg/sql/plan`, public SQL BVT, complete `mo-service` build, SCA and CI pass.
7. The versioned design and PR Test Plan record exact base/candidate commits, same-data A/B procedure, plan assertions, correctness oracle, performance counters and cleanup.

## Related

- Implementation: #27850
- Original ClickBench Q35 problem, not solved by this optimization: #27685
- Pre-existing high-precision DECIMAL AVG wrong-result bug found during review: #27855
- Design: `docs/design/grouped_aggregate_topk_finalization.md`

## Follow-up roadmap

- #27856: scan-local non-PK uniqueness, including UNIQUE indexes and predicate-reduced composite keys.
- #27857: exact physical order from Cluster By or ordered indexes for streaming grouping.
- #27858: remove constant ORDER BY/HAVING exposed by single-row aggregate rewriting.
- #27859: propagate uniqueness and maximum multiplicity through joins/functional dependencies.
- #27860: extend explicit single-row laws to DISTINCT and additional aggregate families.

Unbounded rollout and metadata/zone-map aggregate pruning remain future gates; they should be split only after the bounded primary-key correctness boundary is closed and a concrete benefit/contract is demonstrated.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.