Merge Join executed incorrect resultset which returned empty resultset

[xiutangzju]

Bug Report

1. Minimal reproduce step (Required)

CREATE TABLE t1 (
id bigint(64) NOT NULL AUTO_INCREMENT,
col1 int(16) DEFAULT NULL,
PRIMARY KEY (id)
);

INSERT INTO t1 VALUES (1,65535),(2,65535),(3,-1),(4,NULL),(5,-1),(6,NULL),(7,-1),(8,NULL),(9,0),(10,NULL),(11,1),(12,NULL),(13,NULL),(14,65535),(15,-1),(16,NULL),(17,0);

CREATE TABLE t2 (
id bigint(64) NOT NULL AUTO_INCREMENT,
col1 int(16) DEFAULT NULL,
PRIMARY KEY (id)
);

INSERT INTO t2 VALUES (1,NULL),(2,65535),(3,0),(4,0),(5,0),(6,NULL),(7,NULL),(8,NULL),(9,65535),(10,NULL),(11,NULL),(12,-1),(13,1),(14,0),(15,65535);

CREATE TABLE t3 (
id bigint(64) NOT NULL AUTO_INCREMENT,
col1 int(16) NOT NULL,
PRIMARY KEY (id,col1)
);

INSERT INTO t3 VALUES (1,0),(3,-1),(5,-1),(8,0),(10,-1),(11,-1),(12,0),(9,1),(2,65535),(4,65535),(6,65535),(7,65535);

CREATE TABLE t4 (
id bigint(64) NOT NULL AUTO_INCREMENT,
PRIMARY KEY (id)
);

INSERT INTO t4 VALUES (19),(20),(21),(22),(23),(24),(25),(26),(27),(28),(29),(30);

2. What did you expect to see?

Correct Merge Join when transforming hash join to merge join.

3. What did you see instead

mysql> SELECT /+ merge_join(t3, t4, t1, t2)/ t1.id FROM ((t1 LEFT JOIN t2 ON t1.col1=t2.id) LEFT JOIN t3 ON t2.id=t3.id) LEFT JOIN t4 ON t3.col1=t4.id WHERE !(t3.col1<=>t2.col1);
Empty set (0.02 sec)

mysql> SELECT /+ hash_join(t3, t4, t1, t2)/ t1.id FROM ((t1 LEFT JOIN t2 ON t1.col1=t2..id) LEFT JOIN t3 ON t2.id=t3.id) LEFT JOIN t4 ON t3.col1=t4.id WHERE !(t3.col1<=>t2.col1);
+----+
| id |
+----+
| 11 |
+----+
1 row in set (0.01 sec)

4. What is your TiDB version? (Required)

mysql> SELECT tidb_version();
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| tidb_version() |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Release Version: v5.4.0
Edition: Community
Git Commit Hash: 55f3b24
Git Branch: heads/refs/tags/v5.4.0
UTC Build Time: 2022-01-25 08:39:26
GoVersion: go1.16.4
Race Enabled: false
TiKV Min Version: v3.0.0-60965b006877ca7234adaced7890d7b029ed1306
Check Table Before Drop: false |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

[ChenPeng2013]

I can't reproduce the issue

mysql> SELECT /*+ merge_join(t3, t4, t1, t2)*/ t1.id FROM ((t1 LEFT JOIN t2 ON t1.col1=t2.id) LEFT JOIN t3 ON t2.id=t3.id) LEFT JOIN t4 ON t3.col1=t4.id WHERE !(t3.col1<=>t2.col1);
+----+
| id |
+----+
| 42 |
| 46 |
| 37 |
| 35 |
+----+
4 rows in set (0.01 sec)

mysql>
mysql>
mysql> SELECT /*+ hash_join(t3, t4, t1, t2) */ t1.id FROM ((t1 LEFT JOIN t2 ON t1.col1=t2.id) LEFT JOIN t3 ON t2.id=t3.id) LEFT JOIN t4 ON t3.col1=t4.id WHERE !(t3.col1<=>t2.col1);
+----+
| id |
+----+
| 35 |
| 37 |
| 42 |
| 46 |
+----+
4 rows in set (0.01 sec)

mysql> select tidb_version();
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| tidb_version()                                                                                                                                                                                                                                                                                                       |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Release Version: v5.4.0
Edition: Community
Git Commit Hash: 55f3b24c1c9f506bd652ef1d162283541e428872
Git Branch: heads/refs/tags/v5.4.0
UTC Build Time: 2022-01-25 08:39:26
GoVersion: go1.16.4
Race Enabled: false
TiKV Min Version: v3.0.0-60965b006877ca7234adaced7890d7b029ed1306
Check Table Before Drop: false |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

@xiutangseeker can you provide more detail info

[xiutangzju]

I can't reproduce the issue
@xiutangseeker can you provide more detail info

@ChenPeng2013 Sorry, I updated the reproduce step.

[XuHuaiyu]

reproduce with

SELECT /*+ merge_join(t3) merge_join(t1, t2)*/ t1.id,t1.col1,t2.id,t2.col1,t3.id,t3.col1 FROM ((t1 LEFT JOIN t2 ON t1.col1=t2.id) LEFT JOIN t3 ON t2.id=t3.id) order by t1.id;

[XuHuaiyu]

/*+ merge_join(t3) hash_join(t1,t2)*/ works fine, but /*+ merge_join(t3) merge_join(t1,t2)*/ will got a wrong result.

Because merge_join(t1,t2) can not promise the output result is ordered by t2.id when it's a left outer join.
We need to add a Sort[t2.id] upon merge_join(t1,t2) for this case.