Bug #109155 Invalid scan on left join tables of which columns not in distinct output fields
Submitted: 22 Nov 2022 5:43 Modified: 22 Nov 2022 6:36
Reporter: Chen Wang Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S5 (Performance)
Version:8.0.18, 8.0.31 OS:Any
Assigned to: CPU Architecture:Any
Tags: distinct, left join, performace

[22 Nov 2022 5:43] Chen Wang
Description:
After the support of Volcano iterator in 8.0.18, there is a performance regress when using distinct with a multiple tables left joins of which columns not in the final distinct output fields.

Example which is simplified from one customer's scenario in "How to repeat":

In customer's case, there are nearly 60,000 in the driven table t1. SO the performance in 8.0.18/../31 is 15x lower than 8.0.13 version.

I compared the code flow between 13 and 18. You can see the different.
8.0.18
SQL: t1 -- left join ref scan -- t2 -- left join ref scan -- t3 -- left join ref scan -- t4

---> ha_innobase::rnd_next/index_first t1 1 row (Handler_read_rnd_next=1, Handler_read_first=1,  Handler_read_key=1)
-----> NL join t2
-------> read_key 1 row (Handler_read_key=2)
---------> NL join t3
-----------> read_key 1 row (Handler_read_key=3)
-------------> NL join t4
---------------> read_key 1 row (Handler_read_key=4)
---------------> ha_heap::write_row (Handler_write=1)
---------------> read_same_key 1 row (Handler_read_next=1) ---> EOF
-----------> read_same_key 1 row (Handler_read_next=2) ---> EOF
-------> read_same_key 1 row (Handler_read_next=3) ---> EOF

---> ha_innobase::rnd_next/index_next t1  1 row (Handler_read_rnd_next=2)
-----> NL join t2
-------> read_key 1 row  (Handler_read_key=5)
---------> NL join t3
-----------> read_key 1 row  (Handler_read_key=6)
-------------> NL join t4
---------------> read_key 1 row  (Handler_read_key=7)
---------------> ha_heap::write_row (Handler_write=2)
---------------> read_same_key 1 row (Handler_read_next=4) ---> EOF
-----------> read_same_key 1 row (Handler_read_next=5) ---> EOF
-------> read_same_key 1 row (Handler_read_next=6) ---> EOF

---> ha_innobase::rnd_next/index_next t1 1 row (Handler_read_rnd_next=3)
-----> NL join t2
-------> read_key 1 row  (Handler_read_key=8)
---------> NL join t3
-----------> read_key 1 row  (Handler_read_key=9)
-------------> NL join t4
---------------> read_key 1 row  (Handler_read_key=10)
---------------> ha_heap::write_row (Handler_write=3)
---------------> read_same_key 1 row  (Handler_read_next=7) ---> EOF
-----------> read_same_key 1 row (Handler_read_next=8) ---> EOF
-------> read_same_key 1 row  (Handler_read_next=9) ---> EOF

---> read_key next 1 row  (Handler_read_rnd_next=4)---> EOF

---> ha_heap::rnd_next (Handler_read_rnd_next=5)
---> ha_heap::rnd_next (Handler_read_rnd_next=6)
---> ha_heap::rnd_next (Handler_read_rnd_next=7)
---> ha_heap::rnd_next (Handler_read_rnd_next=8)---> EOF

8.0.13

---> ha_innobase::rnd_next/index_first t1 1 row (Handler_read_rnd_next=1, Handler_read_first=1,  Handler_read_key=1)
-----> NL join t2
-------> read_key 1 row (Handler_read_key=2)
---------> NL join t3
-----------> read_key 1 row (Handler_read_key=3)
-------------> NL join t4
---------------> read_key 1 row (Handler_read_key=4)
---------------> ha_heap::write_row (Handler_write=1)
-------> read_same_key 1 row (Handler_read_next=1) ---> EOF

---> ha_innobase::rnd_next/index_next t1  1 row (Handler_read_rnd_next=2)
-----> NL join t2
-------> read_key 1 row  (Handler_read_key=5)
---------> NL join t3
-----------> read_key 1 row  (Handler_read_key=6)
-------------> NL join t4
---------------> read_key 1 row  (Handler_read_key=7)
---------------> ha_heap::write_row (Handler_write=2)
-------> read_same_key 1 row (Handler_read_next=2) ---> EOF

---> ha_innobase::rnd_next/index_next t1 1 row (Handler_read_rnd_next=3)
-----> NL join t2
-------> read_key 1 row  (Handler_read_key=8)
---------> NL join t3
-----------> read_key 1 row  (Handler_read_key=9)
-------------> NL join t4
---------------> read_key 1 row  (Handler_read_key=10)
---------------> ha_heap::write_row (Handler_write=3)
-------> read_same_key 1 row  (Handler_read_next=3) ---> EOF

---> read_key next 1 row  (Handler_read_rnd_next=4)---> EOF

---> ha_heap::rnd_next (Handler_read_rnd_next=5)
---> ha_heap::rnd_next (Handler_read_rnd_next=6)
---> ha_heap::rnd_next (Handler_read_rnd_next=7)
---> ha_heap::rnd_next (Handler_read_rnd_next=8)---> EOF

Steinar H. Gunderson has ever improved some cases, however, there are still some other situations need to be considered.

commit a56102e778ac63d50f53c5529922294019b8c254
Author: Steinar H. Gunderson <steinar.gunderson@oracle.com>
Date:   Wed May 30 13:59:07 2018 +0200

Thanks.

How to repeat:
drop table t1, t2, t3, t4;

CREATE TABLE `t1` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `type` varchar(32), 
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

insert into t1 values(11,  'test');
insert into t1 values(12,  'test');
insert into t1 values(13,  'test');

CREATE TABLE `t2` ( 
  `id` bigint(20) NOT NULL,
   `t1_id` bigint(20) DEFAULT NULL, 
  PRIMARY KEY (`id`),
  KEY `idx_t1_id` (`t1_id`)
) ENGINE=InnoDB;

insert into t2 values (21 , 11);
insert into t2 values (22 , 12);
insert into t2 values (23 , 13);

CREATE TABLE `t3` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT, 
  `t1_id` bigint(20) DEFAULT NULL, 
  PRIMARY KEY (`id`),
  KEY `idx_t1_id` (`t1_id`)
) ENGINE=InnoDB;

insert into t3 values(31, 11);
insert into t3 values(32, 12);
insert into t3 values(33, 13);

CREATE TABLE `t4` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `t1_id` bigint(20) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_t1_id` (`t1_id`)
) ENGINE=InnoDB;

insert into t4 values( 41, 11);
insert into t4 values( 42, 12);
insert into t4 values( 43, 13);

SELECT distinct t2.t1_id , t1.id AS hp_id FROM t1 LEFT JOIN t2  ON t1.id = t2.t1_id LEFT JOIN t3 ON t1.id = t3.t1_id LEFT JOIN t4 ON t4.t1_id = t1.id WHERE t1.type = 'test';

Suggested fix:
May be also need to consider distinct optimization(qep_tab->not_used_in_distinct) and add Limit 1 Iterator to the table of which columns are not in the final output fields.
[22 Nov 2022 5:46] Chen Wang
show status from 8.0.13

Attachment: 8.0.13.jpg (image/jpeg, text), 140.57 KiB.

[22 Nov 2022 5:46] Chen Wang
show status in 8.0.18+

Attachment: 8.0.18.jpg (image/jpeg, text), 125.26 KiB.

[22 Nov 2022 6:36] MySQL Verification Team
Hello Chen Wang,

Thank you for the report and test case.
Verified as described.

regards,
Umesh