MDEV-20109: Optimizer ignores distinct key created for materialized...

(Backported to 10.3, addressed review input)

Sj_materialization_picker::check_qep(): fix error in cost/fanout
calculations:
- for each join prefix, add #prefix_rows / TIME_FOR_COMPARE to the cost,
  like best_extension_by_limited_search does
- Remove the fanout produced by the subquery tables.
- Also take into account join condition selectivity

optimize_wo_join_buffering() (used by LooseScan and FirstMatch)
- also add #prefix_rows / TIME_FOR_COMPARE to the cost of each prefix.
- Also take into account join condition selectivity

1 files changed, 42 insertions, 18 deletions

diff --git a/mysql-test/main/subselect_sj.result b/mysql-test/main/subselect_sj.result
index ad43a09c7ff..a7cca9d4831 100644
--- a/mysql-test/main/subselect_sj.result
+++ b/mysql-test/main/subselect_sj.result
@@ -729,8 +729,8 @@ SELECT int_key FROM ot1
 WHERE int_nokey IN (SELECT it2.int_key
 FROM it1 LEFT JOIN it2 ON it2.datetime_key);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	<subquery2>	ALL	distinct_key	NULL	NULL	NULL	11	
-1	PRIMARY	ot1	ALL	NULL	NULL	NULL	NULL	20	Using where; Using join buffer (flat, BNL join)
+1	PRIMARY	ot1	ALL	NULL	NULL	NULL	NULL	20	
+1	PRIMARY	<subquery2>	eq_ref	distinct_key	distinct_key	4	func	1	
 2	MATERIALIZED	it1	index	NULL	int_key	4	NULL	2	Using index
 2	MATERIALIZED	it2	ALL	int_key,datetime_key	NULL	NULL	NULL	20	Using where
 DROP TABLE ot1, it1, it2;
@@ -972,11 +972,11 @@ SELECT `varchar_key`  , `varchar_nokey`
 FROM t1  
 WHERE `varchar_nokey`  < 'n' XOR `pk`  )   ;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	PRIMARY	<subquery2>	ALL	distinct_key	NULL	NULL	NULL	15	100.00	
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	18	100.00	Using where; Using join buffer (flat, BNL join)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	18	100.00	
+1	PRIMARY	<subquery2>	eq_ref	distinct_key	distinct_key	8	func,func	1	100.00	
 2	MATERIALIZED	t1	ALL	varchar_key	NULL	NULL	NULL	15	100.00	Using where
 Warnings:
-Note	1003	select `test`.`t2`.`varchar_nokey` AS `varchar_nokey` from `test`.`t2` semi join (`test`.`t1`) where `test`.`t1`.`varchar_nokey` = `test`.`t1`.`varchar_key` and `test`.`t2`.`varchar_nokey` = `test`.`t1`.`varchar_key` and (`test`.`t1`.`varchar_key` < 'n' xor `test`.`t1`.`pk`)
+Note	1003	select `test`.`t2`.`varchar_nokey` AS `varchar_nokey` from `test`.`t2` semi join (`test`.`t1`) where `test`.`t1`.`varchar_nokey` = `test`.`t1`.`varchar_key` and (`test`.`t1`.`varchar_key` < 'n' xor `test`.`t1`.`pk`)
 SELECT varchar_nokey
 FROM t2  
 WHERE ( `varchar_nokey`  , `varchar_nokey`  )  IN (  
@@ -1246,8 +1246,8 @@ INSERT INTO t2 VALUES (1, 0), (1, 1), (2, 0), (2, 1);
 EXPLAIN
 SELECT * FROM t1 WHERE (i) IN (SELECT i FROM t2 where j > 0);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t2	index	k	k	10	NULL	4	Using where; Using index; LooseScan
-1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	5	Using where; Using join buffer (flat, BNL join)
+1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	5	
+1	PRIMARY	t2	index	k	k	10	NULL	4	Using where; Using index; Start temporary; End temporary
 SELECT * FROM t1 WHERE (i) IN (SELECT i FROM t2 where j > 0);
 i
 1
@@ -1757,8 +1757,8 @@ insert into t3 values('three'),( 'four');
 insert into t3 values('three'),( 'four');
 explain select * from t3 where t3.b in (select t2.b from t1 left join t2 on t1.a=t2.a);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	<subquery2>	ALL	distinct_key	NULL	NULL	NULL	2	
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	8	Using where; Using join buffer (flat, BNL join)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	8	
+1	PRIMARY	<subquery2>	eq_ref	distinct_key	distinct_key	10	func	1	
 2	MATERIALIZED	t1	ALL	NULL	NULL	NULL	NULL	2	
 2	MATERIALIZED	t2	ALL	NULL	NULL	NULL	NULL	2	Using where
 select * from t3 where t3.b in (select t2.b from t1 left join t2 on t1.a=t2.a);
@@ -1991,12 +1991,13 @@ CREATE VIEW v4 AS SELECT DISTINCT f2 FROM t4 ;
 explain extended
 SELECT * FROM t1 NATURAL LEFT JOIN (t2, t3) WHERE t2.f3 IN (SELECT * FROM t4);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
-1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where
-1	PRIMARY	t4	ref	f2	f2	5	test.t2.f3	2	100.00	Using index; FirstMatch(t2)
+1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	2	100.00	
+1	PRIMARY	<subquery2>	eq_ref	distinct_key	distinct_key	4	func	1	100.00	
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	3	100.00	Using where; Using join buffer (flat, BNL join)
 1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	5	100.00	Using where; Using join buffer (flat, BNL join)
+2	MATERIALIZED	t4	index	f2	f2	5	NULL	2	100.00	Using index
 Warnings:
-Note	1003	select `test`.`t1`.`f1` AS `f1`,`test`.`t1`.`f2` AS `f2`,`test`.`t2`.`f3` AS `f3`,`test`.`t3`.`f3` AS `f3` from `test`.`t1` semi join (`test`.`t4`) join `test`.`t2` join `test`.`t3` where `test`.`t4`.`f2` = `test`.`t2`.`f3` and `test`.`t3`.`f1` = `test`.`t1`.`f1` and `test`.`t1`.`f2` = `test`.`t2`.`f2`
+Note	1003	select `test`.`t1`.`f1` AS `f1`,`test`.`t1`.`f2` AS `f2`,`test`.`t2`.`f3` AS `f3`,`test`.`t3`.`f3` AS `f3` from `test`.`t1` semi join (`test`.`t4`) join `test`.`t2` join `test`.`t3` where `test`.`t3`.`f1` = `test`.`t1`.`f1` and `test`.`t1`.`f2` = `test`.`t2`.`f2`
 SELECT * FROM t1 NATURAL LEFT JOIN (t2, t3) WHERE t2.f3 IN (SELECT * FROM t4);
 f1	f2	f3	f3
 2	0	0	0
@@ -2495,8 +2496,8 @@ WHERE t1.a = t2.a AND t2.a IN (SELECT b FROM t3 STRAIGHT_JOIN t4);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t3	system	NULL	NULL	NULL	NULL	1	
 1	PRIMARY	<subquery2>	ALL	distinct_key	NULL	NULL	NULL	1	
-1	PRIMARY	t1	ref	a	a	5	const	1	Using index
-1	PRIMARY	t2	ref	a	a	5	func	1	Using index
+1	PRIMARY	t2	ref	a	a	5	const	1	Using index
+1	PRIMARY	t1	ref	a	a	5	func	1	Using index
 2	MATERIALIZED	t4	ALL	NULL	NULL	NULL	NULL	0	
 SELECT * FROM t1, t2
 WHERE t1.a = t2.a AND t2.a IN (SELECT b FROM t3 STRAIGHT_JOIN t4);
@@ -2701,8 +2702,8 @@ a
 19
 explain select * from t3 where a in (select kp1 from t1 where kp1<20);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	PRIMARY	t1	range	kp1	kp1	5	NULL	48	Using where; Using index; LooseScan
-1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	100	Using where; Using join buffer (flat, BNL join)
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	100	Using where
+1	PRIMARY	t1	ref	kp1	kp1	5	test.t3.a	1	Using index; FirstMatch(t3)
 drop table t0,t1,t3;
 set optimizer_switch= @tmp_923246;
 #
@@ -2918,8 +2919,8 @@ WHERE alias1.pk = 58 OR alias1.col_varchar_key = 'o'
 );
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	2	
-1	PRIMARY	alias1	index_merge	PRIMARY,col_int_key,col_varchar_key	PRIMARY,col_varchar_key	4,4	NULL	2	Using sort_union(PRIMARY,col_varchar_key); Using where
-1	PRIMARY	alias2	ALL	col_int_key	NULL	NULL	NULL	12	Range checked for each record (index map: 0x2); FirstMatch(t2)
+1	PRIMARY	alias1	index_merge	PRIMARY,col_int_key,col_varchar_key	PRIMARY,col_varchar_key	4,4	NULL	2	Using sort_union(PRIMARY,col_varchar_key); Using where; Start temporary
+1	PRIMARY	alias2	ALL	col_int_key	NULL	NULL	NULL	12	Range checked for each record (index map: 0x2); End temporary
 SELECT *
 FROM t2
 WHERE (field1) IN (SELECT alias1.col_varchar_nokey AS field1
@@ -3255,4 +3256,27 @@ create table t2 (a2 varchar(25)) ;
 insert into t1 select 'xxx' from dual where 'xxx' in (select a2 from t2);
 drop table t1,t2;
 # End of 5.5 test
+# 
+# MDEV-20109: Optimizer ignores distinct key created for materialized 
+#             semi-join subquery when searching for best execution plan
+# 
+create table t1(a int);
+insert into t1 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
+create table t2(a int);
+insert into t2 select A.a + B.a* 10 + C.a * 100 from t1 A, t1 B, t1 C;
+create table t3 (a int);
+create table t4 (a int);
+insert into t3 select A.a +1000*B.a from t2 A, t1 B;
+insert into t4 select floor(rand()*1000) from t2 limit 500;
+# The following must not use this query plan that does a cross join:
+# |    1 | PRIMARY      | <subquery2> | ALL  | distinct_key  | ... | 500   |                                                 |
+# |    1 | PRIMARY      | t3          | ALL  | NULL          | ... | 10000 | Using where; Using join buffer (flat, BNL join) |
+#
+# Instead, it should use eq_ref on the materialized table.
+explain select * from t3 where a in (select a from t4 group by a);
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	10000	
+1	PRIMARY	<subquery2>	eq_ref	distinct_key	distinct_key	4	func	1	
+2	MATERIALIZED	t4	ALL	NULL	NULL	NULL	NULL	500	
+drop table t1, t2, t3, t4;
 set optimizer_switch=@subselect_sj_tmp;