matrixorigin / matrixorigin/matrixone

[Enhancement]: Extend bounded aggregate elimination to proven non-PK unique keys

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

Description

## Summary

Follow up #27730 and PR #27850 by extending proof-gated bounded aggregate elimination beyond declared primary keys to other uniqueness properties that can prove at most one visible input row per group.

This must be a separate change from #27850. The current PR should first close its primary-key correctness boundary and DECIMAL AVG regression without expanding the proof surface.

## Motivation

The relational law used by #27850 is not specific to primary-key syntax:

```text
direct scan + GROUP BY contains a proven unique key
=> at most one input row per group
=> supported aggregate(single row) is a row expression
=> Aggregate can be eliminated
=> unordered bounded demand may reach TableScan
```

Declared primary keys are the simplest proof because their columns are non-null and globally unique. Unique indexes and derived uniqueness require additional semantic checks before the same law is valid.

## Required proof sources

Initial candidates, in increasing order of risk:

1. a declared/enforced UNIQUE key whose complete key is grouped and whose components are all declared `NOT NULL`;
2. a nullable UNIQUE key only when predicates prove every key component non-null for every surviving scan row;
3. uniqueness properties already produced by the optimizer, but only if their scope, null semantics and relation tag are explicit and stable.

Each proof must refer to the exact direct scan relation and survive projection/filter remapping without changing collation, expression or NULL semantics.

## Fail-closed cases

Retain Aggregate when any of the following applies:

- only a prefix/subset of a composite unique key is grouped;
- any nullable unique-key component can still be NULL;
- the index is non-unique, prefix-based, functional/expression-based without exact expression identity, disabled, unbuilt or not enforced;
- uniqueness is local to a partition rather than global for the scanned relation;
- collation/coercion can merge values that the unique constraint distinguishes;
- a Join, Union/shared CTE, grouping family or another relational boundary invalidates direct-scan uniqueness;
- snapshot/temporary/external/cluster-table metadata does not provide the same enforced uniqueness contract;
- replacement aggregate conversion is not total over the source domain;
- the optimizer property is estimated rather than logically proven.

A generic NDV/cardinality estimate is never a uniqueness proof.

## Correctness matrix

| Dimension | Required cases |
| --- | --- |
| Key kind | single/composite primary key control; single/composite UNIQUE |
| Nullability | all NOT NULL; one nullable component; all nullable; NULL duplicates |
| Predicate proof | no predicate; `IS NOT NULL` for all components; partial proof; OR/unknown proof |
| Grouping | complete key; partial key; key plus extra columns; reordered/duplicated key columns |
| Index form | regular unique; unique secondary; functional/prefix/disabled/unbuilt controls |
| Storage scope | non-partitioned; partitioned global/local uniqueness; temporary table |
| Boundaries | WHERE, HAVING, ORDER BY, OFFSET, prepared LIMIT, Join, Union/shared CTE, grouping sets |
| Types | numeric, VARCHAR/collation, CHAR padding, binary, temporal, ENUM/SET, DECIMAL boundaries |
| Aggregate | COUNT, nullable COUNT, SUM/AVG/MIN/MAX/ANY_VALUE; DISTINCT/configured/unsupported fallback |
| Session semantics | `SQL_CALC_FOUND_ROWS`, snapshot reads and repeated prepared execution |

Tests must compare result values, metadata and error status against the established Aggregate plan. Plan-only assertions are insufficient.

## Performance validation

On the same NVMe data and with only the binary changed:

1. demonstrate a high-cardinality NOT-NULL UNIQUE-key case where unordered LIMIT materially reduces scan/hash work and wall time;
2. include OFFSET, selective WHERE/HAVING and ORDER BY shapes;
3. prove nullable/partial/unsupported controls retain Aggregate and stay within 3% outside documented noise;
4. report scan rows/bytes, group memory/spill, CPU, allocations/peak RSS and wall-time medians;
5. verify result counts during timing rather than discarding correctness.

## Acceptance criteria

1. A reusable optimizer uniqueness-proof API identifies the exact key columns, relation scope, enforcement state and NULL contract; the rewrite does not independently guess from raw index metadata.
2. Only a complete, globally enforced, NULL-safe unique key activates elimination.
3. Nullable UNIQUE behavior is covered with real duplicate-NULL rows; predicate-based activation requires proof for every component.
4. All fail-closed cases preserve the established Aggregate plan.
5. Single-row aggregate type/conversion proofs, including high-precision DECIMAL AVG, are shared with or stricter than #27850.
6. Focused planner UT, full plan suite, public SQL BVT, complete service build, SCA and same-data performance A/B pass.
7. The design and PR body include a QA-executable test plan and explicitly state which uniqueness sources remain unsupported.

## Non-goals

- Do not infer uniqueness from NDV/statistics.
- Do not optimize arbitrary high-cardinality grouping such as ClickBench Q35 without a logical unique-key proof.
- Do not combine this with generic early group eviction, approximate TopK or a Group-to-Top runtime callback.

## Related

- Primary-key implementation: #27850
- Primary-key tracking/design decision: #27730
- DECIMAL AVG boundary bug discovered during review: #27855
- ClickBench Q35, which still requires a separate design: #27685

## Scan-local uniqueness derivations

The proof should operate on a key closure, not only a literal `GROUP BY` list:

- For a unique key `U`, elimination is valid when every component of `U` is either a direct grouping column or is fixed by a proven scan predicate to one non-NULL value. For example, `UNIQUE(a,b) WHERE a = ? GROUP BY b` is eligible only when the bound parameter is non-NULL and the equality is preserved at execution.
- A unique secondary index may provide the same proof only when it represents an enabled, built and enforced SQL uniqueness constraint. An internal index table or estimated access-path cardinality is not sufficient.
- Equality closure must reject lossy casts, collation changes, volatile expressions, OR predicates and partial NULL proofs.
- Partition-local unique indexes require a fixed partition or inclusion of the partition identity/key; they must never be presented as table-global uniqueness.
- The proof should be attached as a reusable optimizer property before an index access path is lowered into index-table joins, so later rewrites cannot lose its relation scope.
- A covering index reduces I/O but does not independently prove uniqueness; a non-unique ordered index belongs to the order-property work in #27857.

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.