[MDEV-312] CHEAP SQ: A query with LEFT JOIN in outer SELECT and INNER JOIN and aggregate in subquery takes much longer than on the main tree Created: 2012-06-05  Updated: 2012-06-07  Resolved: 2012-06-07

Status: Closed
Project: MariaDB Server
Component/s: None
Affects Version/s: None
Fix Version/s: 5.5.27

Type: Bug Priority: Major
Reporter: Elena Stepanova Assignee: Timour Katchaounov (Inactive)
Resolution: Won't Fix Votes: 0
Labels: None

Issue Links:
Relates
relates to MDEV-193 LP:944706 - Query with impossible or ... Closed

 Description   

The following query 

SELECT * FROM t1 LEFT JOIN t2 ON ( c = e )
 
WHERE d IN ( SELECT SUM(a) FROM t1, t2 WHERE f = b );

with ~550 rows in t1 and ~270 rows in t2 with the default optimizer_switch takes about 0.15 sec on the main 5.5 tree, and 6 sec on MDEV-193 tree.

5.5-timour:

date: 2012-06-01 14:10:15 +0300
 
revno: 3407

maria/5.5:

revision-id: wlad@montyprogram.com-20120530182054-g7sll9u4gsitvgqe
 
date: 2012-05-30 20:20:54 +0200
 
revno: 3425

optimizer_switch:

index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_merge_sort_intersection=off,engine_condition_pushdown=off,index_condition_pushdown=on,derived_merge=on,derived_with_keys=on,firstmatch=on,loosescan=on,materialization=on,in_to_exists=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr=off,mrr_cost_based=off,mrr_sort_keys=off,outer_join_with_cache=on,semijoin_with_cache=on,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on,optimize_join_buffer_size=off,table_elimination=on,extended_keys=off

Also reproducible with all OFF values (except for in_to_exists which is required). With the minimal optimizer_switch execution time on the main tree is about the same, while on MDEV-193 it grows up to 20+ seconds.

Reproducible with MyISAM, Aria, InnoDB.

EXPLAIN on MDEV-193 tree:

 
 
id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 
1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	274	100.00	Using where
 
1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	655	100.00	Using where; Using join buffer (flat, BNL join)
 
2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	274	100.00	
2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	655	100.00	Using where; Using join buffer (flat, BNL join)
 
Warnings:
 
Note	1003	select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t1`.`c` AS `c`,`test`.`t2`.`d` AS `d`,`test`.`t2`.`e` AS `e`,`test`.`t2`.`f` AS `f` from `test`.`t1` join `test`.`t2` where ((`test`.`t1`.`c` = `test`.`t2`.`e`) and <expr_cache><`test`.`t2`.`d`>(<in_optimizer>(`test`.`t2`.`d`,<exists>(select sum(`test`.`t1`.`a`) from `test`.`t1` join `test`.`t2` where (`test`.`t1`.`b` = `test`.`t2`.`f`) having (<cache>(`test`.`t2`.`d`) = <ref_null_helper>(sum(`test`.`t1`.`a`)))))))
 
SELECT * FROM t1 LEFT JOIN t2 ON ( c = e )
 
WHERE d IN ( SELECT SUM(a) FROM t1, t2 WHERE f = b );

EXPLAIN on maria/5.5:

 
 
id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 
1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	655	100.00	
1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	274	100.00	Using where; Using join buffer (flat, BNL join)
 
2	DEPENDENT SUBQUERY	t2	ALL	NULL	NULL	NULL	NULL	274	100.00	
2	DEPENDENT SUBQUERY	t1	ALL	NULL	NULL	NULL	NULL	655	100.00	Using where; Using join buffer (flat, BNL join)
 
Warnings:
 
Note	1003	select `test`.`t1`.`a` AS `a`,`test`.`t1`.`b` AS `b`,`test`.`t1`.`c` AS `c`,`test`.`t2`.`d` AS `d`,`test`.`t2`.`e` AS `e`,`test`.`t2`.`f` AS `f` from `test`.`t1` left join `test`.`t2` on((`test`.`t2`.`e` = `test`.`t1`.`c`)) where <expr_cache><`test`.`t2`.`d`>(<in_optimizer>(`test`.`t2`.`d`,<exists>(select sum(`test`.`t1`.`a`) from `test`.`t1` join `test`.`t2` where (`test`.`t1`.`b` = `test`.`t2`.`f`) having (<cache>(`test`.`t2`.`d`) = <ref_null_helper>(sum(`test`.`t1`.`a`))))))

Test case:

 
 
SET optimizer_switch = 'in_to_exists=on';
 
 
 
CREATE TABLE t1 (a INT, b VARCHAR(3), c VARCHAR(3));
 
INSERT INTO t1 VALUES 
(12,'N/A','Abi'),(22,'USA','Akr'),(9,'USA','Alb'),(45,'USA','Alb'),
 
(13,'USA','Ale'),(11,'N/A','All'),(17,'CAN','Ama'),(33,'USA','Ana'),
 
(26,'FRA','Anc'),(11,'USA','Ann'),(9,'USA','Ard'),(33,'USA','Arl'),
 
(17,'USA','Arl'),(10,'CAN','Arv'),(10,'USA','Ath'),(42,'USA','Atl'),
 
(20,'USA','Aug'),(28,'USA','Aur'),(14,'N/A','Aur'),(66,'USA','Aus'),
 
(25,'USA','Bak'),(65,'USA','Bal'),(23,'USA','Bat'),(11,'USA','Bea'),
 
(11,'CAN','Bel'),(10,'FRA','Ber'),(9,'USA','Bil'),(24,'USA','Bir'),
 
(19,'USA','Boi'),(59,'N/A','Bos'),(9,'USA','Bou'),(14,'USA','Bri'),
 
(9,'USA','Bro'),(14,'USA','Bro'),(29,'USA','Buf'),(10,'USA','Bur'),
 
(10,'USA','Cam'),(10,'USA','Cap'),(11,'USA','Car'),(9,'USA','Car'),
 
(9,'USA','Car'),(12,'USA','Ced'),(18,'USA','Cha'),(9,'USA','Cha'),
 
(54,'USA','Cha'),(16,'USA','Cha'),(20,'USA','Che'),(290,'USA','Chi'),
 
(17,'USA','Chu'),(33,'USA','Cin'),(10,'USA','Cit'),(11,'FRA','Cla'),
 
(10,'CAN','Cle'),(48,'USA','Cle'),(36,'USA','Col'),(12,'USA','Col'),
 
(71,'USA','Col'),(19,'N/A','Col'),(9,'USA','Com'),(12,'USA','Con'),
 
(12,'USA','Cor'),(12,'USA','Cor'),(28,'USA','Cor'),(11,'USA','Cos'),
 
(119,'USA','Dal'),(10,'USA','Dal'),(10,'CAN','Dav'),(17,'USA','Day'),
 
(55,'USA','Den'),(20,'USA','Des'),(95,'USA','Det'),(11,'USA','Dow'),
 
(19,'USA','Dur'),(13,'USA','Eas'),(9,'USA','El '),(12,'USA','El '),
 
(56,'N/A','El '),(9,'USA','Elg'),(12,'USA','Eli'),(10,'CAN','Eri'),
 
(13,'USA','Esc'),(14,'USA','Eug'),(12,'USA','Eva'),(9,'USA','Fai'),
 
(9,'USA','Fal'),(12,'USA','Fay'),(12,'USA','Fli'),(13,'FRA','Fon'),
 
(12,'USA','For'),(15,'USA','For'),(21,'USA','For'),(53,'USA','For'),
 
(20,'USA','Fre'),(43,'USA','Fre'),(13,'USA','Ful'),(9,'USA','Gai'),
 
(17,'USA','Gar'),(22,'N/A','Gar'),(10,'USA','Gar'),(11,'USA','Gil'),
 
(22,'USA','Gle'),(19,'USA','Gle'),(13,'CAN','Gra'),(20,'USA','Gra'),
 
(10,'USA','Gre'),(22,'USA','Gre'),(15,'USA','Ham'),(12,'USA','Har'),
 
(14,'USA','Hay'),(18,'USA','Hen'),(23,'USA','Hia'),(14,'USA','Hol'),
 
(37,'USA','Hon'),(195,'USA','Hou'),(19,'USA','Hun'),(16,'USA','Hun'),
 
(11,'USA','Ind'),(79,'FRA','Ind'),(11,'USA','Ing'),(14,'N/A','Irv'),
 
(19,'CAN','Irv'),(18,'USA','Jac'),(74,'USA','Jac'),(24,'USA','Jer'),
 
(11,'USA','Jol'),(44,'USA','Kan'),(15,'USA','Kan'),(9,'USA','Ken'),
 
(17,'USA','Kno'),(11,'USA','Laf'),(14,'USA','Lak'),(12,'USA','Lan'),
 
(12,'USA','Lan'),(18,'USA','Lar'),(48,'FRA','Las'),(26,'USA','Lex'),
 
(23,'N/A','Lin'),(18,'USA','Lit'),(10,'USA','Liv'),(46,'USA','Lon'),
 
(369,'USA','Los'),(26,'USA','Lou'),(11,'USA','Low'),(20,'USA','Lub'),
 
(11,'USA','Mac'),(21,'USA','Mad'),(11,'USA','Man'),(11,'USA','McA'),
 
(65,'USA','Mem'),(40,'USA','Mes'),(12,'USA','Mes'),(15,'N/A','Met'),
 
(36,'USA','Mia'),(10,'FRA','Mia'),(10,'USA','Mid'),(60,'USA','Mil'),
 
(38,'CAN','Min'),(10,'USA','Mis'),(20,'USA','Mob'),(19,'USA','Mod'),
 
(20,'USA','Mon'),(14,'N/A','Mor'),(13,'USA','Nap'),(57,'USA','Nas'),
 
(9,'USA','New'),(12,'USA','New'),(48,'USA','New'),(801,'USA','New'),
 
(27,'N/A','New'),(18,'USA','New'),(23,'USA','Nor'),(9,'CAN','Nor'),
 
(12,'USA','Nor'),(10,'FRA','Nor'),(40,'USA','Oak'),(16,'USA','Oce'),
 
(9,'USA','Ode'),(51,'USA','Okl'),(39,'USA','Oma'),(16,'USA','Ont'),
 
(13,'USA','Ora'),(19,'USA','Orl'),(15,'FRA','Ove'),(17,'N/A','Oxn'),
 
(12,'USA','Pal'),(12,'USA','Par'),(14,'USA','Pas'),(13,'USA','Pas'),
 
(15,'CAN','Pat'),(14,'USA','Pem'),(11,'USA','Peo'),(11,'USA','Peo'),
 
(152,'N/A','Phi'),(132,'USA','Pho'),(33,'USA','Pit'),(22,'USA','Pla'),
 
(15,'USA','Pom'),(53,'USA','Por'),(10,'USA','Por'),(17,'USA','Pro'),
 
(11,'USA','Pro'),(10,'USA','Pue'),(28,'FRA','Ral'),(13,'CAN','Ran'),
 
(18,'USA','Ren'),(20,'USA','Ric'),(9,'USA','Ric'),(26,'USA','Riv'),
 
(9,'USA','Roa'),(22,'N/A','Roc'),(15,'USA','Roc'),(41,'USA','Sac'),
 
(35,'USA','Sai'),(29,'USA','Sai'),(25,'USA','Sai'),(14,'USA','Sal'),
 
(15,'USA','Sal'),(18,'USA','Sal'),(114,'FRA','San'),(19,'USA','San'),
 
(10,'USA','San'),(122,'USA','San'),(78,'CAN','San'),(89,'USA','San'),
 
(9,'USA','San'),(10,'USA','San'),(34,'USA','San'),(10,'USA','San'),
 
(15,'N/A','San'),(9,'USA','San'),(15,'USA','San'),(13,'USA','Sav'),
 
(20,'USA','Sco'),(56,'FRA','Sea'),(20,'CAN','Shr'),(11,'USA','Sim'),
 
(12,'USA','Sio'),(11,'USA','Sou'),(20,'USA','Spo'),(15,'USA','Spr'),
 
(15,'USA','Spr'),(11,'USA','Spr'),(12,'USA','Sta'),(12,'USA','Ste'),
 
(24,'USA','Sto'),(13,'USA','Sun'),(10,'FRA','Sun'),(15,'USA','Syr'),
 
(19,'N/A','Tac'),(15,'USA','Tal'),(30,'USA','Tam'),(16,'USA','Tem'),
 
(12,'CAN','Tho'),(31,'USA','Tol'),(12,'USA','Top'),(14,'USA','Tor'),
 
(49,'USA','Tuc'),(39,'FRA','Tul'),(12,'USA','Val'),(14,'USA','Van'),
 
(43,'USA','Vir'),(9,'USA','Vis'),(11,'USA','Wac'),(14,'USA','War'),
 
(57,'USA','Was'),(11,'USA','Wat'),(11,'FRA','Wes'),(11,'USA','Wes'),
 
(10,'USA','Wes'),(34,'USA','Wic'),(10,'USA','Wic'),(19,'USA','Win'),
 
(17,'FRA','Wor'),(20,'USA','Yon');
 
 
 
CREATE TABLE t2 (d INT, e VARCHAR(3), f VARCHAR(3));
 
INSERT INTO t2 SELECT * FROM t1;
 
 
 
INSERT INTO t1 SELECT * FROM t1;
 
 
 
SELECT * FROM t1 LEFT JOIN t2 ON ( c = e )
 
WHERE d IN ( SELECT SUM(a) FROM t1, t2 WHERE f = b );
 
 



 Comments   
Comment by Timour Katchaounov (Inactive) [ 2012-06-06 ]

In my latest tree for mdev-193 I get the following:

MariaDB [md312]> explain extended SELECT * FROM t1 LEFT JOIN t2 ON ( c = e )
-> WHERE d IN ( SELECT SUM(a) FROM t1, t2 WHERE f = b );
------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

------------------------------------------------------------------------------------------------------------------------

1 PRIMARY t1 ALL NULL NULL NULL NULL 451 100.00  
1 PRIMARY t2 ALL NULL NULL NULL NULL 274 100.00 Using where; Using join buffer (flat, BNL join)
2 DEPENDENT SUBQUERY t2 ALL NULL NULL NULL NULL 274 100.00  
2 DEPENDENT SUBQUERY t1 ALL NULL NULL NULL NULL 451 100.00 Using where; Using join buffer (flat, BNL join)

------------------------------------------------------------------------------------------------------------------------

– After two subsequent restarts, I get this explain (and statistics):
------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

------------------------------------------------------------------------------------------------------------------------

1 PRIMARY t1 ALL NULL NULL NULL NULL 691 100.00  
1 PRIMARY t2 ALL NULL NULL NULL NULL 274 100.00 Using where; Using join buffer (flat, BNL join)
2 DEPENDENT SUBQUERY t2 ALL NULL NULL NULL NULL 274 100.00  
2 DEPENDENT SUBQUERY t1 ALL NULL NULL NULL NULL 691 100.00 Using where; Using join buffer (flat, BNL join)

------------------------------------------------------------------------------------------------------------------------

The plan is still the same.

– In 5.5 I get the same plan and almost the same stats:

MariaDB [md312]> explain extended SELECT * FROM t1 LEFT JOIN t2 ON ( c = e )
-> WHERE d IN ( SELECT SUM(a) FROM t1, t2 WHERE f = b );
------------------------------------------------------------------------------------------------------------------------

id select_type table type possible_keys key key_len ref rows filtered Extra

------------------------------------------------------------------------------------------------------------------------

1 PRIMARY t1 ALL NULL NULL NULL NULL 655 100.00  
1 PRIMARY t2 ALL NULL NULL NULL NULL 274 100.00 Using where; Using join buffer (flat, BNL join)
2 DEPENDENT SUBQUERY t2 ALL NULL NULL NULL NULL 274 100.00  
2 DEPENDENT SUBQUERY t1 ALL NULL NULL NULL NULL 655 100.00 Using where; Using join buffer (flat, BNL join)

------------------------------------------------------------------------------------------------------------------------

Comment by Timour Katchaounov (Inactive) [ 2012-06-07 ]

The changed query plans, and the difference in performance is a result of unstable InnoDB statistics.
The changes in mdev-193 have to effect on the the query in this test case because the IN subquery predicate is not constant.

If the 'd' field on the left side of IN is replaced by a constant (e.g. '11'), then constant subquery optimization kicks in, but this is not the case here.

Generated at Thu Feb 08 06:27:48 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.