matrixorigin / matrixorigin/matrixone
[Enhancement]: Propagate join uniqueness for bounded aggregate elimination
- Dominant language
- Go
- Stars
- 1.9k
- Forks
- 311
- Avg merge
- 1d 3h
- Merged PRs (30d)
- 768
Description
## Summary
Extend the optimizer's logical uniqueness/functional-dependency properties through joins and row-preserving relational operators. A grouped aggregate above a join may be eliminated only when the join is proven to preserve at-most-one row for each grouped key.
This is separate from scan-local unique-key work in #27856 because join cardinality, null extension and distributed ownership add a new proof boundary.
## Examples
Eligible in principle:
```sql
-- dim.id is unique, so the inner join cannot duplicate each fact row.
select f.id, count(*)
from fact f join dim d on f.dim_id = d.id
group by f.id
limit 10;
```
For an INNER join, the result is a subset of fact rows; for a LEFT join against an at-most-one matching dimension row, every fact row remains exactly once. If `f.id` is unique, grouping by it still has at most one row per group.
Ineligible:
```sql
-- d.dim_id is not unique and may duplicate each fact row.
select f.id, count(*)
from fact f join detail d on f.id = d.fact_id
group by f.id
limit 10;
```
## Required logical property
Track uniqueness as scoped keys/functional dependencies with:
- originating relation/row identity and output expression mapping;
- NULL semantics and whether outer-join null extension preserves the key;
- maximum join multiplicity from each side based on enforced unique keys and equality predicates;
- effects of Filter, Project, CTE inlining, Union, aggregation, semi/anti joins and exchanges;
- partition/global scope and whether distributed execution can duplicate a logical row.
Only exact enforced constraints and equality closure may prove multiplicity. NDV, selectivity and cardinality estimates must never activate the rewrite.
## Fail-closed cases
- many-to-one direction is applied to the wrong preserved side;
- non-equality, lossy cast or collation-changing join predicates;
- nullable unique keys without a complete NULL proof;
- full/right/mark/single joins whose row/null semantics are not explicitly modeled;
- multiple joins where any edge can multiply the grouped identity;
- Union/shared CTE or exchange behavior that duplicates rows;
- uniqueness inferred from statistics or assumed foreign-key data without enforced guarantees;
- aggregate conversion or expression evaluation is not total/equivalent.
## Validation matrix
- INNER/LEFT/SEMI/ANTI joins with zero, one and multiple matches;
- unique/non-unique single and composite join keys, including nullable components;
- uniqueness from PK, UNIQUE and predicate-reduced keys;
- filters before/after join, projected/aliased keys and chained joins;
- one/multi-CN, broadcast/shuffle joins and partitioned tables;
- WHERE, HAVING, ORDER BY, LIMIT/OFFSET, prepared LIMIT and `SQL_CALC_FOUND_ROWS`;
- supported/mixed/unsupported aggregates and DECIMAL boundaries;
- plan assertions plus base/candidate result, metadata and error-status comparison.
## Acceptance criteria
1. A reusable uniqueness/multiplicity property is produced and consumed; no join-type/query-text special case.
2. Every eligible join is proven not to multiply the grouped identity.
3. Ineligible joins retain Aggregate and established execution.
4. Distributed placement cannot duplicate or split one logical finalization owner.
5. Deterministic UT/BVT cover zero/one/many matches, outer null extension and multi-join composition.
6. Same-data performance A/B demonstrates material benefit and neutral fallback controls.
## Related
- Direct primary-key implementation: #27850
- Scan-local non-PK uniqueness: #27856
- Storage/index order follow-up: #27857
- Umbrella decision: #27730
Contributor guide
Assessment
This issue has not been assessed yet.