pingcap / pingcap/tidb

planner: add phase-1 Yannakakis+ DISTINCT rewrite for acyclic joins

Open
#66,789 0 comments 0 reactions 0 assignees View on GitHub
component/test type/enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.