planner: add phase-1 Yannakakis+ DISTINCT rewrite for acyclic joins
- Dominant language
- Go
- Stars
- 40.5k
- Forks
- 6.2k
- PR merge metrics
- PR metrics pending
Description
## Enhancement
Add a phase-1 Yannakakis+-style logical rewrite for `DISTINCT` on acyclic inner equi-joins in the TiDB planner.
### Motivation
TiDB currently evaluates `DISTINCT` over acyclic join components using the normal join pipeline. For a restricted but common subset of queries, we can reduce intermediate multiplicity earlier by pushing interface-level `DISTINCT` reductions into acyclic join subtrees before the final root aggregation.
This issue tracks a conservative first step instead of the full paper:
- only top-level `DISTINCT` shapes represented as `LogicalAggregation(first_row(...))`;
- only acyclic inner equi-joins;
- only cases where all final output columns are owned by the same leaf relation;
- no generic decomposable aggregation, FK-based pruning, or cycle handling yet.
### Scope
- add a dedicated logical optimizer rule before aggregation pushdown / join reorder;
- detect the safe phase-1 query shape;
- build an acyclic relation tree with GYO-style reduction;
- rewrite child subtrees to interface-level `DISTINCT` reductions;
- keep heuristic failure as no-op rather than a planning error;
- add focused planner regression coverage;
- document the recursive invariant and proof sketch in `docs/note/planner`.
### Expected Benefit
- reduce multiplicity earlier for a safe subset of `DISTINCT` queries over acyclic joins;
- establish planner scaffolding for later phases that can expand to relation-dominated outputs and decomposable aggregations;
- keep correctness risk bounded by a narrow matcher and explicit invariants.
### Non-goals for phase 1
- generic `GROUP BY` + aggregation pushdown;
- cost-based selection among multiple legal join trees;
- support for cyclic joins;
- semijoin reduction driven by foreign keys or Bloom filters.
Suggested labels: `type/enhancement`, `component/test` (the repository does not appear to have a planner-specific `component/*` label)
Contributor guide
Research direction
Start by locating TiDB's logical optimizer rule pipeline, the aggregation pushdown and join reorder stages, and the existing planner regression tests. Implement the narrowly defined phase-1 shape and document the recursive invariant and proof sketch in docs/note/planner; done means focused coverage for safe rewrites and no-op behavior when matching fails.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go, sql
- Domain
- backend, databases
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 35/100