pingcap / pingcap/tidb

planner: improve row count estimation for semi joins

Open
#68,912 0 comments 0 reactions 0 assignees View on GitHub
planner/performance sig/planner type/enhancement
Dominant language
Go
Stars
40.5k
Forks
6.2k
PR merge metrics
PR metrics pending

Description

## Enhancement

Semi-join row-count and NDV estimation is currently too coarse for some selective `EXISTS` / `IN` subqueries. This can make the native semi-join plan look much more expensive than the equivalent `SEMI_JOIN_REWRITE()` plan, even though both forms should have broadly similar output cardinality.

Current logic in `LogicalJoin.DeriveStats` handles `SemiJoin` and `AntiSemiJoin` with a fixed selection factor:

```go
if p.JoinType == base.SemiJoin || p.JoinType == base.AntiSemiJoin {
p.SetStats(&property.StatsInfo{
RowCount: leftProfile.RowCount * cost.SelectionFactor,
ColNDVs: make(map[int64]float64, len(leftProfile.ColNDVs)),
})
for id, c := range leftProfile.ColNDVs {
p.StatsInfo().ColNDVs[id] = c * cost.SelectionFactor
}
return p.StatsInfo(), true, nil
}
```

`cost.SelectionFactor` is a generic constant (`0.8`). It does not use join-key NDV, inner-side selectivity, equality conditions, or the already-computed `EqualCondOutCnt`.

A simplified and anonymized plan-replayer case:

```sql
SELECT o.sequential_id, o.label
FROM obj AS o
WHERE o.workspace_id = X
AND o.obj_type_id IN (...)
AND EXISTS (
SELECT 1
FROM rel AS r
JOIN obj AS seed
ON seed.id = r.referenced_object_id
AND seed.workspace_id = X
AND seed.obj_type_id = Y
AND seed.text_value = 'very-selective-value'
WHERE r.object_id = o.id
AND r.object_type_attribute_id IN (...)
)
ORDER BY o.label
LIMIT 1000;
```

Relevant indexes:

```sql
-- seed table access
KEY ix_obj_text_value_ot(workspace_id, obj_type_id, text_value)

-- relationship table access
KEY ix_rel_referenced_object_id(referenced_object_id)
```

Without `SEMI_JOIN_REWRITE()`, the native semi-join plan contains a hash semi join with a large estimated row count inherited from the left side. In the replayer, the plan shape was roughly:

```text
TopN estRows: 1000.00
└─TableReader / MPP or root join path
└─HashJoin(semi join) estRows: 1605245.92
├─subquery-side joins estRows: 155.53 / 12.49 / 1.00
└─outer table access estRows: 2006557.40
```

After adding `SEMI_JOIN_REWRITE()`, the equivalent inner-join + dedup shape has a much smaller and more reasonable cardinality:

```text
TopN estRows: 12.49
└─IndexHashJoin(inner join back to obj) estRows: 12.49
├─HashAgg(group by rel.object_id) estRows: 12.49
│ └─IndexHashJoin
│ ├─IndexLookUp(seed) estRows: 1.00
│ └─IndexLookUp(rel) estRows: 12.49
└─TableReader(obj) estRows: 6.01
```

The rewritten plan starts from a highly selective `seed` lookup, probes `rel`, deduplicates `object_id`, and joins back to `obj`. Since this is semantically equivalent to the semi join, the native semi-join cardinality should not be estimated as a simple `leftRows * 0.8` in this kind of case.

Expected improvement:

- Improve `SemiJoin` / `AntiSemiJoin` row-count estimation by considering join keys, inner-side cardinality/selectivity, and NDV where available.
- Make semi-join output cardinality closer to the equivalent inner-join + dedup rewrite when the rewrite is semantically safe.
- Avoid overestimating semi joins that have a highly selective inner side, so physical plan costing does not unfairly penalize the native semi-join shape.

This is related to, but separate from, supporting `SEMI_JOIN_REWRITE()` as an alternative logical plan. Even when both logical shapes are explored, the native semi-join shape should have a more accurate cardinality estimate.

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.