enable semi_join_rewrite in multi alternative implementation

Enhancement

DROP DATABASE IF EXISTS d1;
CREATE DATABASE d1;
USE d1;

CREATE TABLE `t1` (
  `id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
  `c1` BIGINT UNSIGNED NOT NULL,           -- filter key
  `c2` VARCHAR(64) NOT NULL,               -- join key
  `c3` DATETIME NOT NULL,                  -- order by key
  `c4` VARCHAR(64) NULL,                   -- projected column
  PRIMARY KEY (`id`),
  UNIQUE KEY `idx1` (`c2`),
  KEY `idx2` (`c1`, `c3`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

CREATE TABLE `t2` (
  `id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
  `c2` VARCHAR(64) NOT NULL,               -- join key
  `c5` VARCHAR(128) NULL,                  -- projected column
  PRIMARY KEY (`id`),
  UNIQUE KEY `idx3` (`c2`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

CREATE TABLE `t3` (
  `id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
  `c2` VARCHAR(64) NOT NULL,               -- join key
  `c6` VARCHAR(64) NULL,                   -- projected column
  `c7` VARCHAR(64) NULL,                   -- projected column
  PRIMARY KEY (`id`),
  UNIQUE KEY `idx4` (`c2`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

CREATE TABLE `t4` (
  `id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
  `c2` VARCHAR(64) NOT NULL,               -- join key
  `c8` VARCHAR(256) NULL,                  -- EXISTS + LIKE filter column
  PRIMARY KEY (`id`),
  KEY `idx5` (`c2`, `c8`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

EXPLAIN
SELECT
  a.c2,
  a.c4,
  b.c5,
  c.c6,
  c.c7
FROM t1 a
LEFT JOIN t2 b ON a.c2 = b.c2
LEFT JOIN t3 c ON a.c2 = c.c2
WHERE a.c1 = 100
  AND EXISTS (
    SELECT  1
    FROM t4 d
    WHERE d.c2 = a.c2
      AND d.c8 LIKE 'abc%'
  )
ORDER BY a.c3 DESC
LIMIT 100;

bad plan

In real customer env, the final result is zero(IndexJoin_181 output 0 rows), most of time is spent to compute the outer side of IndexJoin_181, because a left join b left c will keep all rows from a, and a is a very large table(almost 3,000,000 rows after the filter of a.c1 = 100.

+-----------------------------------------+---------+-----------+-----------------------------+-------------------------------------------------------------------------------------------------------------------+
| id                                      | estRows | task      | access object               | operator info                                                                                                     |
+-----------------------------------------+---------+-----------+-----------------------------+-------------------------------------------------------------------------------------------------------------------+
| Projection_27                           | 15.62   | root      |                             | d1.t1.c2, d1.t1.c4, d1.t2.c5, d1.t3.c6, d1.t3.c7                                                                  |
| └─Limit_34                              | 15.62   | root      |                             | offset:0, count:100                                                                                               |
|   └─IndexJoin_181                       | 15.62   | root      |                             | left outer join, inner:IndexLookUp_180, outer key:d1.t1.c2, inner key:d1.t3.c2, equal cond:eq(d1.t1.c2, d1.t3.c2) |
|     ├─IndexHashJoin_195(Build)          | 12.50   | root      |                             | left outer join, inner:IndexLookUp_192, outer key:d1.t1.c2, inner key:d1.t2.c2, equal cond:eq(d1.t1.c2, d1.t2.c2) |
|     │ ├─IndexJoin_207(Build)            | 10.00   | root      |                             | inner join, inner:HashAgg_205, outer key:d1.t1.c2, inner key:d1.t4.c2, equal cond:eq(d1.t1.c2, d1.t4.c2)          |
|     │ │ ├─Projection_219(Build)         | 10.00   | root      |                             | d1.t1.c1, d1.t1.c2, d1.t1.c3, d1.t1.c4                                                                            |
|     │ │ │ └─IndexLookUp_218             | 10.00   | root      |                             |                                                                                                                   |
|     │ │ │   ├─IndexRangeScan_216(Build) | 10.00   | cop[tikv] | table:a, index:idx2(c1, c3) | range:[100,100], keep order:true, desc, stats:pseudo                                                              |
|     │ │ │   └─TableRowIDScan_217(Probe) | 10.00   | cop[tikv] | table:a                     | keep order:false, stats:pseudo                                                                                    |
|     │ │ └─HashAgg_205(Probe)            | 10.00   | root      |                             | group by:d1.t4.c2, funcs:firstrow(d1.t4.c2)->d1.t4.c2                                                             |
|     │ │   └─IndexReader_206             | 10.00   | root      |                             | index:HashAgg_204                                                                                                 |
|     │ │     └─HashAgg_204               | 10.00   | cop[tikv] |                             | group by:d1.t4.c2,                                                                                                |
|     │ │       └─Selection_203           | 10.00   | cop[tikv] |                             | like(d1.t4.c8, "abc%", 92)                                                                                        |
|     │ │         └─IndexRangeScan_202    | 400.00  | cop[tikv] | table:d, index:idx5(c2, c8) | range: decided by [eq(d1.t4.c2, d1.t1.c2) like(d1.t4.c8, abc%, 92)], keep order:false, stats:pseudo               |
|     │ └─IndexLookUp_192(Probe)          | 10.00   | root      |                             |                                                                                                                   |
|     │   ├─IndexRangeScan_190(Build)     | 10.00   | cop[tikv] | table:b, index:idx3(c2)     | range: decided by [eq(d1.t2.c2, d1.t1.c2)], keep order:false, stats:pseudo                                        |
|     │   └─TableRowIDScan_191(Probe)     | 10.00   | cop[tikv] | table:b                     | keep order:false, stats:pseudo                                                                                    |
|     └─IndexLookUp_180(Probe)            | 12.50   | root      |                             |                                                                                                                   |
|       ├─IndexRangeScan_178(Build)       | 12.50   | cop[tikv] | table:c, index:idx4(c2)     | range: decided by [eq(d1.t3.c2, d1.t1.c2)], keep order:false, stats:pseudo                                        |
|       └─TableRowIDScan_179(Probe)       | 12.50   | cop[tikv] | table:c                     | keep order:false, stats:pseudo                                                                                    |
+-----------------------------------------+---------+-----------+-----------------------------+-------------------------------------------------------------------------------------------------------------------+

good plan

a better way is to let a and d join first, but for now tidb join reorder doesn't support reoreder for semi join, that's why we have above bad plan. And a wrokaround is to use semi_join_rewirte() hint, which can convert the semi join to a inner join with a HashAgg for dedup

Actually we can add this hint to the framework of multiple alternative, so the optimizer can generate this plan automatically.

+-----------------------------------------+---------+-----------+-----------------------------+-------------------------------------------------------------------------------------------------------------------+
| id                                      | estRows | task      | access object               | operator info                                                                                                     |
+-----------------------------------------+---------+-----------+-----------------------------+-------------------------------------------------------------------------------------------------------------------+
| Projection_19                           | 12.50   | root      |                             | d1.t1.c2, d1.t1.c4, d1.t2.c5, d1.t3.c6, d1.t3.c7                                                                  |
| └─Limit_26                              | 12.50   | root      |                             | offset:0, count:100                                                                                               |
|   └─IndexHashJoin_131                   | 12.50   | root      |                             | semi join, inner:IndexReader_128, outer key:d1.t1.c2, inner key:d1.t4.c2, equal cond:eq(d1.t1.c2, d1.t4.c2)       |
|     ├─IndexJoin_140(Build)              | 15.62   | root      |                             | left outer join, inner:IndexLookUp_139, outer key:d1.t1.c2, inner key:d1.t3.c2, equal cond:eq(d1.t1.c2, d1.t3.c2) |
|     │ ├─IndexJoin_152(Build)            | 12.50   | root      |                             | left outer join, inner:IndexLookUp_151, outer key:d1.t1.c2, inner key:d1.t2.c2, equal cond:eq(d1.t1.c2, d1.t2.c2) |
|     │ │ ├─Projection_163(Build)         | 10.00   | root      |                             | d1.t1.c1, d1.t1.c2, d1.t1.c3, d1.t1.c4                                                                            |
|     │ │ │ └─IndexLookUp_162             | 10.00   | root      |                             |                                                                                                                   |
|     │ │ │   ├─IndexRangeScan_160(Build) | 10.00   | cop[tikv] | table:a, index:idx2(c1, c3) | range:[100,100], keep order:true, desc, stats:pseudo                                                              |
|     │ │ │   └─TableRowIDScan_161(Probe) | 10.00   | cop[tikv] | table:a                     | keep order:false, stats:pseudo                                                                                    |
|     │ │ └─IndexLookUp_151(Probe)        | 10.00   | root      |                             |                                                                                                                   |
|     │ │   ├─IndexRangeScan_149(Build)   | 10.00   | cop[tikv] | table:b, index:idx3(c2)     | range: decided by [eq(d1.t2.c2, d1.t1.c2)], keep order:false, stats:pseudo                                        |
|     │ │   └─TableRowIDScan_150(Probe)   | 10.00   | cop[tikv] | table:b                     | keep order:false, stats:pseudo                                                                                    |
|     │ └─IndexLookUp_139(Probe)          | 12.50   | root      |                             |                                                                                                                   |
|     │   ├─IndexRangeScan_137(Build)     | 12.50   | cop[tikv] | table:c, index:idx4(c2)     | range: decided by [eq(d1.t3.c2, d1.t1.c2)], keep order:false, stats:pseudo                                        |
|     │   └─TableRowIDScan_138(Probe)     | 12.50   | cop[tikv] | table:c                     | keep order:false, stats:pseudo                                                                                    |
|     └─IndexReader_128(Probe)            | 19.53   | root      |                             | index:Selection_127                                                                                               |
|       └─Selection_127                   | 19.53   | cop[tikv] |                             | like(d1.t4.c8, "abc%", 92)                                                                                        |
|         └─IndexRangeScan_126            | 781.25  | cop[tikv] | table:d, index:idx5(c2, c8) | range: decided by [eq(d1.t4.c2, d1.t1.c2) like(d1.t4.c8, abc%, 92)], keep order:false, stats:pseudo               |
+-----------------------------------------+---------+-----------+-----------------------------+-------------------------------------------------------------------------------------------------------------------+

Additional evidence from a plan replayer case:

The same query shape can get a much better plan only after applying SEMI_JOIN_REWRITE(). Without the rewrite, the native semi-join/apply search space keeps the left side as the driving side, so the optimizer cannot explore the cheaper shape where the selective inner side is evaluated first and then joined back to the original left table.

In the replayer case, the rewritten plan first uses a highly selective index lookup on the subquery side, deduplicates the join key with HashAgg, and then probes the outer table with IndexHashJoin / TableReader. The resulting estimated cost is much lower than the original plan shape. This matches the request in this issue: semi-join rewrite should be generated as a costed logical alternative, not only when the query explicitly uses the hint or enables tidb_opt_enable_semi_join_rewrite globally.

So the expected behavior is:

keep the original semi-join/apply plan as one candidate;
generate the SEMI_JOIN_REWRITE equivalent as another alternative when it is semantically safe;
let the alternative logical plan framework choose by physical cost.

A simplified and anonymized version of the plan-replayer case is below. The table names, column names, and literal values are rewritten, but the join shape and access paths are the relevant parts.

Schema shape:

CREATE TABLE obj (
  id varbinary(16) NOT NULL,
  workspace_id varbinary(16) NOT NULL,
  obj_type_id varbinary(16) NOT NULL,
  label varchar(256),
  sequential_id bigint,
  text_value varchar(256),
  PRIMARY KEY (workspace_id, id),
  KEY ix_obj_text_value_ot(workspace_id, obj_type_id, text_value),
  KEY ix_obj_label_objtypeid(workspace_id, label, obj_type_id, sequential_id)
);

CREATE TABLE rel (
  object_id varbinary(16) NOT NULL,
  referenced_object_id varbinary(16) NOT NULL,
  object_type_attribute_id varbinary(16) NOT NULL,
  object_type_id varbinary(16) NOT NULL,
  KEY ix_rel_referenced_object_id(referenced_object_id)
);

Query shape:

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;

Without SEMI_JOIN_REWRITE(), the native semi-join/apply search space keeps obj AS o as the driving side. In the replayer, this led the optimizer toward a much more expensive shape, because it could not explore the plan that starts from the highly selective seed lookup.

With SEMI_JOIN_REWRITE(), the optimizer can produce this cheaper shape:

TopN
└─IndexHashJoin
  ├─HashAgg(group by r.object_id)
  │ └─IndexHashJoin
  │   ├─IndexLookUp on seed using ix_obj_text_value_ot
  │   │   range: (workspace_id = X, obj_type_id = Y, text_value = 'very-selective-value')
  │   │   estimated rows: about 1
  │   └─IndexLookUp on rel using ix_rel_referenced_object_id
  │       range: decided by seed.id = rel.referenced_object_id
  └─TableReader on obj AS o
      range: decided by o.id = r.object_id and o.workspace_id = X

The important point is that the rewritten inner-join + HashAgg form allows the optimizer to start from the selective subquery side, deduplicate object_id, and then probe the original outer table. The native semi-join/apply form cannot currently expose this alternative because both the apply direction and semi-join index-join construction keep the original left side as the outer/driving side.

This is why supporting semi-join rewrite inside the alternative logical plan framework is useful: it lets the optimizer cost both the native semi-join shape and the rewritten inner-join + dedup shape, then choose the cheaper one without requiring users to add SEMI_JOIN_REWRITE() manually.

planner: support semi join rewrite as an alternative logical plan (#6…

planner: avoid semi join rewrite round race (#69459)

Navigation Menu

Repository navigation

enable semi_join_rewrite in multi alternative implementation #67467

Enhancement

bad plan

good plan

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

enable semi_join_rewrite in multi alternative implementation #67467

Description

Enhancement

bad plan

good plan

Activity

AilinKid commented on Jun 3, 2026

AilinKid commented on Jun 3, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions