pingcap / pingcap/tidb

Planner: Join Reorder — Blocking / Bounded Operator Cost (Enhancement)

Open
#65,906 0 comments 0 reactions 1 assignee Claimed by @King-Dylan View on GitHub
planner/join-order type/enhancement
Dominant language
Go
Stars
40.5k
Forks
6.2k
PR merge metrics
PR metrics pending

Description

## Enhancement
### Problem
In join reorder, the cumulative cost of a node in the join group is currently computed by **recursively summing subtree row counts**. When the plan contains **blocking operators** (Aggregation, Sort, Window) or **bounded operators** (Limit, TopN), this leads to two issues:

1. **Subtree inflation**
Treating every node as “sum of children cost” inflates the cost of large subtrees, so join reorder may choose a worse join order (e.g. in some SQL-1–style workloads).

2. **Blocking cost not reflected**
Agg/Sort/Window are “blocking” (they consume a lot of input before producing rows). The current cost model does not reflect this. For queries like TPCH-Q17 with correlated subqueries (e.g. `avg()`), the chosen join order can be wrong—e.g. it may be better to put the side with Agg on the probe, but the current cost does not distinguish.

Additionally, Limit/TopN only produce `offset+count` rows, but the current model still accumulates subtree row counts, which distorts the cost comparison for join order as well.

### Desired enhancement

- In join reorder cost calculation:
- **Default**: Model Join/Selection/Projection/DataSource etc. with a “leaf-like” cost (e.g. output row count only) to avoid subtree inflation.
- **Limit/TopN**: Tie cost to `offset+count` (bounded) instead of unbounded subtree accumulation.
- **Aggregation/Sort/Window**: Introduce a **tunable** “blocking penalty” in the cost so that their need to consume large input before output is reflected, leading to better join orders in Q17-like scenarios.

- The strength of this blocking penalty should be **configurable** (e.g. via a session variable or hint), so it can be turned off or reduced if regressions appear, while still allowing it to be enabled by default to improve Q17-like queries.

### Reference scenarios

- **TPCH-Q17**: Correlated subquery with `avg(quantity)`; join order is sensitive to whether Agg is on the probe side.
- **Joins with large subtrees** : Avoid incorrect preference for the large-subtree side due to recursive cost accumulation.

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.