Unexpected Result by MERGE_JOIN

[bajinsheng]

Bug Report

Please answer these questions before submitting your issue. Thanks!

1. Minimal reproduce step (Required)

CREATE TABLE t0(c0 INT, c1 INT, c2 INT, PRIMARY KEY(c1));
CREATE TABLE t1 LIKE t0;
INSERT INTO t0 VALUES (1, 2, 3);
CREATE VIEW v0(c0, c1, c2) AS SELECT 4, 5, 6 FROM t1;
INSERT INTO t1 VALUES (7, 8, 9);

SELECT t0.c1 FROM t1, t0 NATURAL RIGHT JOIN v0 WHERE t0.c2 = t1.c2 NOT REGEXP 1; -- {NULL}
SELECT /*+ MERGE_JOIN(t0, t1, v0)*/t0.c1 FROM t1, t0 NATURAL RIGHT JOIN v0 WHERE t0.c2 = t1.c2 NOT REGEXP 1; -- empty set

2. What did you expect to see? (Required)

Both queries should return the same result, but not.

3. What did you see instead (Required)

4. What is your TiDB version? (Required)

| Release Version: v7.4.0-alpha
Edition: Community
Git Commit Hash: 32540a4a77984744dc0309d9287b05c8e9593252
Git Branch: heads/refs/tags/v7.4.0-alpha
UTC Build Time: 2023-09-27 14:33:24
GoVersion: go1.21.1
Race Enabled: false
Check Table Before Drop: false
Store: tikv |

[bajinsheng]

/label fuzz/sqlancer

[ti-chi-bot[bot]]

@bajinsheng: The label(s) /fuzz/sqlancer cannot be applied. These labels are supported: fuzz/sqlancer, challenge-program, compatibility-breaker, first-time-contributor, contribution, require-LGT3, good first issue, correctness, duplicate, proposal, security, ok-to-test, needs-ok-to-test, needs-more-info, needs-cherry-pick-release-5.3, needs-cherry-pick-release-5.4, needs-cherry-pick-release-6.1, needs-cherry-pick-release-6.5, needs-cherry-pick-release-7.1, needs-cherry-pick-release-7.4, affects-5.3, affects-5.4, affects-6.1, affects-6.5, affects-7.1, affects-7.4, may-affects-5.3, may-affects-5.4, may-affects-6.1, may-affects-6.5, may-affects-7.1, may-affects-7.4.

In response to [this](https://github.com/pingcap/tidb/issues/47345#issuecomment-1738290365): >/label /fuzz/sqlancer Instructions for interacting with me using PR comments are available [here](https://prow.tidb.net/command-help). If you have questions or suggestions related to my behavior, please file an issue against the [ti-community-infra/tichi](https://github.com/ti-community-infra/tichi/issues/new?title=Prow%20issue:) repository.

[elsa0520]

/assign @elsa0520

[elsa0520]

The correct result should be empty. So the first sql result is error.

The error plan is following:

mysql> explain SELECT t0.c1 FROM t1, t0 NATURAL RIGHT JOIN v0 WHERE t0.c2 = t1.c2 NOT REGEXP 1;
+----------------------------------+---------+-----------+---------------+---------------------------------------------------------------------------------------------------------+
| id                               | estRows | task      | access object | operator info                                                                                           |
+----------------------------------+---------+-----------+---------------+---------------------------------------------------------------------------------------------------------+
| HashJoin_18                      | 1.00    | root      |               | right outer join, equal:[eq(test.t0.c0, Column#10) eq(test.t0.c1, Column#11) eq(test.t0.c2, Column#12)] |
| ├─HashJoin_19(Build)             | 1.00    | root      |               | inner join, equal:[eq(test.t0.c2, Column#16)]                                                           |
| │ ├─Projection_24(Build)         | 1.00    | root      |               | not(regexp(cast(test.t1.c2, var_string(20)), 1))->Column#16                                             |
| │ │ └─TableReader_26             | 1.00    | root      |               | data:TableFullScan_25                                                                                   |
| │ │   └─TableFullScan_25         | 1.00    | cop[tikv] | table:t1      | keep order:false, stats:pseudo                                                                          |
| │ └─TableReader_23(Probe)        | 1.00    | root      |               | data:Selection_22                                                                                       |
| │   └─Selection_22               | 1.00    | cop[tikv] |               | not(isnull(test.t0.c0)), not(isnull(test.t0.c2))                                                        |
| │     └─TableFullScan_21         | 1.00    | cop[tikv] | table:t0      | keep order:false, stats:pseudo                                                                          |
| └─Projection_27(Probe)           | 1.00    | root      |               | 4->Column#10, 5->Column#11, 6->Column#12                                                                |
|   └─TableReader_29               | 1.00    | root      |               | data:TableFullScan_28                                                                                   |
|     └─TableFullScan_28           | 1.00    | cop[tikv] | table:t1      | keep order:false, stats:pseudo                                                                          |
+----------------------------------+---------+-----------+---------------+---------------------------------------------------------------------------------------------------------+

The predicate t0.c2 = t1.c2 NOT REGEXP 1 has been push down to Join(t0, t1) but the right join hasn't changed to inner join. When we push down the null rejection predicate, we need to change the right join to inner join together. Otherwise, the result will be wrong.

I close the join order rule, the plan is correct. So I suspect the join order rule incorrect allocate the predicate.

mysql> INSERT INTO mysql.opt_rule_blacklist VALUES("join_reorder");
Query OK, 1 row affected (0.01 sec)

mysql> admin reload opt_rule_blacklist;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT t0.c1 FROM t1, t0 NATURAL RIGHT JOIN v0 WHERE t0.c2 = t1.c2 NOT REGEXP 1;
Empty set (0.00 sec)

[elsa0520]

PTAL @winoros

[elsa0520]

/assign @winoros

[winoros]

We need some time to resolve it. Move down its severity to major. We can use /*+ SET_VAR(tidb_enable_outer_join_reorder=off) */ as the workaround.