pingcap / pingcap/tidb

TiDB does not eliminate duplicate identical EXISTS predicates, causing repeated semi-join work

Open
#69,930 2 comments 0 reactions 0 assignees View on GitHub
contribution type/enhancement
Dominant language
Go
Stars
40.5k
Forks
6.2k
PR merge metrics
PR metrics pending

Description

## Bug Report

Please answer these questions before submitting your issue. Thanks!
In TiDB, two identical correlated `EXISTS` predicates connected by `AND` are not deduplicated by the optimizer. The original query contains one `EXISTS` predicate and produces one semi join. The mutated query adds the same `EXISTS` predicate again, which is logically redundant, but TiDB plans two semi joins and scans/builds the inner side twice.

Both queries return the same result, but the duplicated predicate is measurably slower.

Retested on TiDB v8.5.7:

```text
original median: 150.717 ms
mutated median: 281.718 ms
ratio: 1.87x slower
```
### 1. Minimal reproduce step (Required)

```sql
DROP DATABASE IF EXISTS tidb_mdev_40434_big;
CREATE DATABASE tidb_mdev_40434_big;
USE tidb_mdev_40434_big;

CREATE TABLE outer_t(id INT PRIMARY KEY);
CREATE TABLE inner_t(v INT, pad CHAR(20));
CREATE TABLE d(n INT);

INSERT INTO d VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);

INSERT INTO outer_t
SELECT a.n + 10*b.n + 100*c.n
FROM d AS a
JOIN d AS b
JOIN d AS c;

INSERT INTO inner_t
SELECT
(a.n + 10*b.n + 100*c.n + 1000*d1.n + 10000*e.n + 100000*f.n) % 1000,
REPEAT('x', 20)
FROM d AS a
JOIN d AS b
JOIN d AS c
JOIN d AS d1
JOIN d AS e
JOIN d AS f;

ANALYZE TABLE outer_t;
ANALYZE TABLE inner_t;

-- Original query
SELECT COUNT(*)
FROM outer_t AS o
WHERE EXISTS (
SELECT 1
FROM inner_t AS i
WHERE i.v = o.id
AND i.pad = 'xxxxxxxxxxxxxxxxxxxx'
);

-- Mutated query with duplicated identical EXISTS
SELECT COUNT(*)
FROM outer_t AS o
WHERE EXISTS (
SELECT 1
FROM inner_t AS i
WHERE i.v = o.id
AND i.pad = 'xxxxxxxxxxxxxxxxxxxx'
)
AND EXISTS (
SELECT 1
FROM inner_t AS i
WHERE i.v = o.id
AND i.pad = 'xxxxxxxxxxxxxxxxxxxx'
);
```

### 2. What did you expect to see? (Required)
TiDB should recognize:

```sql
EXISTS(subquery) AND EXISTS(same_subquery)
```

as equivalent to:

```sql
EXISTS(subquery)
```

or otherwise avoid repeating the same semi-join work.
### 3. What did you see instead (Required)

Original query:

```text
HashAgg
HashJoin semi join, equal:[eq(outer_t.id, inner_t.v)]
TableReader(Build)
Selection eq(inner_t.pad, "xxxxxxxxxxxxxxxxxxxx"), not(isnull(inner_t.v))
TableFullScan table:inner_t
TableReader(Probe)
TableFullScan table:outer_t
```

Mutated query:

```text
HashAgg
HashJoin semi join, equal:[eq(outer_t.id, inner_t.v)]
TableReader(Build)
Selection eq(inner_t.pad, "xxxxxxxxxxxxxxxxxxxx"), not(isnull(inner_t.v))
TableFullScan table:inner_t
HashJoin(Probe) semi join, equal:[eq(outer_t.id, inner_t.v)]
TableReader(Build)
Selection eq(inner_t.pad, "xxxxxxxxxxxxxxxxxxxx"), not(isnull(inner_t.v))
TableFullScan table:inner_t
TableReader(Probe)
TableFullScan table:outer_t
```

The mutated query scans/builds `inner_t` twice even though the two `EXISTS` predicates are identical.
Both queries return:

```text
1000
```

Measured execution time over repeated runs:

```text
original ms: 151.444, 150.345, 147.378, 152.573, 150.717, 149.059, 153.786
mutated ms: 249.531, 287.182, 280.359, 287.418, 287.858, 281.718, 281.297
```

Median:

```text
original median: 150.717 ms
mutated median: 281.718 ms
ratio: 1.87x slower
```

### 4. What is your TiDB version? (Required)

```text
Release Version: v8.5.7
Edition: Community
Git Commit Hash: 202b7f47286a1109b5c957401d34c9358d130ae0
Git Branch: HEAD
UTC Build Time: 2026-07-15 02:06:00
GoVersion: go1.25.10
Race Enabled: false
Check Table Before Drop: false
Store: unistore
```

Contributor guide

Open the contributing guide

Research direction

Start with the supplied SQL reproduction and compare the original and duplicated-EXISTS plans. Trace TiDB's optimizer handling of correlated EXISTS predicates and determine where identical predicates could be recognized; done means the duplicated query no longer performs the inner semi-join work twice while preserving the reported result.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.