#At file:///data0/martin/bzrroot/wl3724/n-mr-o-t-Roy/ based on revid:tor.didriksen@stripped
3225 Martin Hansson 2010-10-06
WL#3724: Short-Cutting Join Execution: Speeding up star queries
added:
mysql-test/r/shortcut.result
mysql-test/t/shortcut.test
sql/sql_set.h
sql/sql_shortcut.h
modified:
mysql-test/r/func_in_none.result
mysql-test/r/greedy_optimizer.result
mysql-test/r/join.result
mysql-test/r/join_cache_jcl1.result
mysql-test/r/join_nested.result
mysql-test/r/order_by_none.result
mysql-test/r/subselect_innodb.result
mysql-test/t/subselect_innodb.test
sql/item.cc
sql/item.h
sql/records.h
sql/sql_select.cc
sql/sql_select.h
sql/structs.h
=== modified file 'mysql-test/r/func_in_none.result'
--- a/mysql-test/r/func_in_none.result 2010-07-23 17:51:11 +0000
+++ b/mysql-test/r/func_in_none.result 2010-10-06 15:22:47 +0000
@@ -371,7 +371,7 @@ JOIN t4 WHERE t4.a IN (t1.b, t2.b);
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t3 index PRIMARY PRIMARY 4 NULL 4 Using index
1 SIMPLE t1 eq_ref PRIMARY PRIMARY 4 test.t3.a 1
-1 SIMPLE t2 eq_ref PRIMARY PRIMARY 4 test.t3.a 1
+1 SIMPLE t2 eq_ref PRIMARY PRIMARY 4 test.t3.a 1 StarJoin(t3)
1 SIMPLE t4 ALL PRIMARY NULL NULL NULL 7 Range checked for each record (index map: 0x1)
SELECT STRAIGHT_JOIN * FROM t3
JOIN t1 ON t3.a=t1.a
@@ -389,7 +389,7 @@ WHERE t3.a=t1.a AND t3.a=t2.a;
id select_type table type possible_keys key key_len ref rows Extra
1 PRIMARY t3 index PRIMARY PRIMARY 4 NULL 4 Using index
1 PRIMARY t1 eq_ref PRIMARY PRIMARY 4 test.t3.a 1
-1 PRIMARY t2 eq_ref PRIMARY PRIMARY 4 test.t3.a 1
+1 PRIMARY t2 eq_ref PRIMARY PRIMARY 4 test.t3.a 1 StarJoin(t3)
2 DEPENDENT SUBQUERY t4 index NULL PRIMARY 4 NULL 7 Using where; Using index
SELECT STRAIGHT_JOIN
(SELECT SUM(t4.a) FROM t4 WHERE t4.a IN (t1.b, t2.b))
=== modified file 'mysql-test/r/greedy_optimizer.result'
--- a/mysql-test/r/greedy_optimizer.result 2010-06-25 09:34:37 +0000
+++ b/mysql-test/r/greedy_optimizer.result 2010-10-06 15:22:47 +0000
@@ -153,8 +153,8 @@ id select_type table type possible_keys
1 SIMPLE t6 ALL NULL NULL NULL NULL 18 Using join buffer (BNL, regular buffers)
1 SIMPLE t1 eq_ref PRIMARY PRIMARY 4 test.t2.c21 1 Using where
1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using index
-1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using index
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using index
+1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using index; StarJoin(t1)
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using index; StarJoin(t1)
show status like 'Last_query_cost';
Variable_name Value
Last_query_cost 289.430791
@@ -165,8 +165,8 @@ id select_type table type possible_keys
1 SIMPLE t6 ALL NULL NULL NULL NULL 18 Using join buffer (BNL, regular buffers)
1 SIMPLE t1 eq_ref PRIMARY PRIMARY 4 test.t2.c21 1 Using where
1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using index
-1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using index
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using index
+1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using index; StarJoin(t1)
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using index; StarJoin(t1)
show status like 'Last_query_cost';
Variable_name Value
Last_query_cost 289.430791
@@ -178,7 +178,7 @@ id select_type table type possible_keys
1 SIMPLE t1 eq_ref PRIMARY PRIMARY 4 test.t2.c21 1 Using where
1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using where
1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using where
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where; StarJoin(t5)
show status like 'Last_query_cost';
Variable_name Value
Last_query_cost 289.469776
@@ -189,8 +189,8 @@ id select_type table type possible_keys
1 SIMPLE t6 ALL NULL NULL NULL NULL 18 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t1 eq_ref PRIMARY PRIMARY 4 test.t2.c21 1 Using where
1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using where
-1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using where
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where
+1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using where; StarJoin(t1)
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where; StarJoin(t1)
show status like 'Last_query_cost';
Variable_name Value
Last_query_cost 289.469776
@@ -226,8 +226,8 @@ explain select t1.c11 from t1, t2, t3, t
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 ALL PRIMARY NULL NULL NULL 3 Using where
1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using index
-1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using index
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using index
+1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using index; StarJoin(t1)
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using index; StarJoin(t1)
1 SIMPLE t2 ALL NULL NULL NULL NULL 6 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t4 ALL NULL NULL NULL NULL 12 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t6 ALL NULL NULL NULL NULL 18 Using where; Using join buffer (BNL, regular buffers)
@@ -238,8 +238,8 @@ explain select t1.c11 from t7, t6, t5, t
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 ALL PRIMARY NULL NULL NULL 3 Using where
1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using index
-1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using index
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using index
+1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using index; StarJoin(t1)
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using index; StarJoin(t1)
1 SIMPLE t2 ALL NULL NULL NULL NULL 6 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t4 ALL NULL NULL NULL NULL 12 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t6 ALL NULL NULL NULL NULL 18 Using where; Using join buffer (BNL, regular buffers)
@@ -251,7 +251,7 @@ id select_type table type possible_keys
1 SIMPLE t1 ALL PRIMARY NULL NULL NULL 3 Using where
1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1
1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using where
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where; StarJoin(t3)
1 SIMPLE t2 ALL NULL NULL NULL NULL 6 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t4 ALL NULL NULL NULL NULL 12 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t6 ALL NULL NULL NULL NULL 18 Using where; Using join buffer (BNL, regular buffers)
@@ -262,8 +262,8 @@ explain select t1.c11 from t7, t6, t5, t
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 ALL PRIMARY NULL NULL NULL 3 Using where
1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1
-1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using where
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where
+1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using where; StarJoin(t1)
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where; StarJoin(t1)
1 SIMPLE t2 ALL NULL NULL NULL NULL 6 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t4 ALL NULL NULL NULL NULL 12 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t6 ALL NULL NULL NULL NULL 18 Using where; Using join buffer (BNL, regular buffers)
@@ -305,8 +305,8 @@ id select_type table type possible_keys
1 SIMPLE t6 ALL NULL NULL NULL NULL 18 Using join buffer (BNL, regular buffers)
1 SIMPLE t1 eq_ref PRIMARY PRIMARY 4 test.t2.c21 1 Using where
1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using index
-1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using index
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using index
+1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using index; StarJoin(t1)
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using index; StarJoin(t1)
show status like 'Last_query_cost';
Variable_name Value
Last_query_cost 289.430791
@@ -317,8 +317,8 @@ id select_type table type possible_keys
1 SIMPLE t6 ALL NULL NULL NULL NULL 18 Using join buffer (BNL, regular buffers)
1 SIMPLE t1 eq_ref PRIMARY PRIMARY 4 test.t2.c21 1 Using where
1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using index
-1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using index
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using index
+1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using index; StarJoin(t1)
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using index; StarJoin(t1)
show status like 'Last_query_cost';
Variable_name Value
Last_query_cost 289.430791
@@ -330,7 +330,7 @@ id select_type table type possible_keys
1 SIMPLE t1 eq_ref PRIMARY PRIMARY 4 test.t2.c21 1 Using where
1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using where
1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using where
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where; StarJoin(t5)
show status like 'Last_query_cost';
Variable_name Value
Last_query_cost 289.469776
@@ -341,8 +341,8 @@ id select_type table type possible_keys
1 SIMPLE t6 ALL NULL NULL NULL NULL 18 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t1 eq_ref PRIMARY PRIMARY 4 test.t2.c21 1 Using where
1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using where
-1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using where
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where
+1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using where; StarJoin(t1)
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where; StarJoin(t1)
show status like 'Last_query_cost';
Variable_name Value
Last_query_cost 289.469776
@@ -410,7 +410,7 @@ id select_type table type possible_keys
1 SIMPLE t6 ALL NULL NULL NULL NULL 18 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using where
1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using where
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where; StarJoin(t5)
show status like 'Last_query_cost';
Variable_name Value
Last_query_cost 795.085394
@@ -458,8 +458,8 @@ explain select t1.c11 from t1, t2, t3, t
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 ALL PRIMARY NULL NULL NULL 3 Using where
1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using index
-1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using index
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using index
+1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using index; StarJoin(t1)
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using index; StarJoin(t1)
1 SIMPLE t2 ALL NULL NULL NULL NULL 6 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t4 ALL NULL NULL NULL NULL 12 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t6 ALL NULL NULL NULL NULL 18 Using where; Using join buffer (BNL, regular buffers)
@@ -470,8 +470,8 @@ explain select t1.c11 from t7, t6, t5, t
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 ALL PRIMARY NULL NULL NULL 3 Using where
1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using index
-1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using index
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using index
+1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using index; StarJoin(t1)
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using index; StarJoin(t1)
1 SIMPLE t2 ALL NULL NULL NULL NULL 6 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t4 ALL NULL NULL NULL NULL 12 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t6 ALL NULL NULL NULL NULL 18 Using where; Using join buffer (BNL, regular buffers)
@@ -483,7 +483,7 @@ id select_type table type possible_keys
1 SIMPLE t1 ALL PRIMARY NULL NULL NULL 3 Using where
1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1
1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using where
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where; StarJoin(t3)
1 SIMPLE t2 ALL NULL NULL NULL NULL 6 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t4 ALL NULL NULL NULL NULL 12 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t6 ALL NULL NULL NULL NULL 18 Using where; Using join buffer (BNL, regular buffers)
@@ -494,8 +494,8 @@ explain select t1.c11 from t7, t6, t5, t
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 ALL PRIMARY NULL NULL NULL 3 Using where
1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1
-1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using where
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where
+1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using where; StarJoin(t1)
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where; StarJoin(t1)
1 SIMPLE t2 ALL NULL NULL NULL NULL 6 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t4 ALL NULL NULL NULL NULL 12 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t6 ALL NULL NULL NULL NULL 18 Using where; Using join buffer (BNL, regular buffers)
@@ -562,7 +562,7 @@ id select_type table type possible_keys
1 SIMPLE t6 ALL NULL NULL NULL NULL 18 Using where; Using join buffer (BNL, regular buffers)
1 SIMPLE t5 eq_ref PRIMARY PRIMARY 4 test.t1.c14 1 Using where
1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.c12 1 Using where
-1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where
+1 SIMPLE t7 eq_ref PRIMARY PRIMARY 4 test.t1.c16 1 Using where; StarJoin(t5)
show status like 'Last_query_cost';
Variable_name Value
Last_query_cost 795.085394
=== modified file 'mysql-test/r/join.result'
--- a/mysql-test/r/join.result 2010-08-26 21:32:48 +0000
+++ b/mysql-test/r/join.result 2010-10-06 15:22:47 +0000
@@ -848,7 +848,7 @@ explain select * from t1, t2, t3 where t
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 ALL NULL NULL NULL NULL 4 Using where
1 SIMPLE t2 eq_ref PRIMARY PRIMARY 4 test.t1.b 1 Using index
-1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.a 1 Using index
+1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.a 1 Using index; StarJoin(t1)
We expect rnd_next=5, and read_key must be 0 because of short-cutting:
show status like 'Handler_read%';
Variable_name Value
=== modified file 'mysql-test/r/join_cache_jcl1.result'
--- a/mysql-test/r/join_cache_jcl1.result 2010-10-04 13:10:35 +0000
+++ b/mysql-test/r/join_cache_jcl1.result 2010-10-06 15:22:47 +0000
@@ -480,7 +480,7 @@ CountryLanguage.Percentage > 50;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE CountryLanguage ALL PRIMARY,Percentage NULL NULL NULL 984 Using where
1 SIMPLE Country eq_ref PRIMARY PRIMARY 3 world.CountryLanguage.Country 1 Using where
-1 SIMPLE City ref Country Country 3 world.Country.Code 18 Using where
+1 SIMPLE City ref Country Country 3 world.Country.Code 18 Using where; StarJoin(CountryLanguage)
SELECT City.Name, Country.Name, CountryLanguage.Language
FROM City,Country,CountryLanguage
WHERE City.Country=Country.Code AND
@@ -787,7 +787,7 @@ CountryLanguage.Percentage > 50;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE CountryLanguage ALL PRIMARY,Percentage NULL NULL NULL 984 Using where
1 SIMPLE Country eq_ref PRIMARY PRIMARY 3 world.CountryLanguage.Country 1 Using where
-1 SIMPLE City ref Country Country 3 world.Country.Code 18 Using where
+1 SIMPLE City ref Country Country 3 world.Country.Code 18 Using where; StarJoin(CountryLanguage)
SELECT City.Name, Country.Name, CountryLanguage.Language
FROM City,Country,CountryLanguage
WHERE City.Country=Country.Code AND
@@ -1308,10 +1308,10 @@ id select_type table type possible_keys
1 SIMPLE t1 ref t1_affiliateid,t1_metaid t1_affiliateid 4 const 1
1 SIMPLE t4 ref PRIMARY,t4_formatclassid,t4_formats_idx t4_formats_idx 1 const 1 Using where
1 SIMPLE t5 eq_ref PRIMARY,t5_formattypeid PRIMARY 4 test.t4.formatclassid 1 Using where
-1 SIMPLE t2 eq_ref PRIMARY PRIMARY 4 test.t1.metaid 1
-1 SIMPLE t7 ref PRIMARY PRIMARY 4 test.t1.metaid 1 Using index
-1 SIMPLE t3 ref t3_metaid,t3_formatid,t3_metaidformatid t3_metaid 4 test.t1.metaid 2 Using where
-1 SIMPLE t8 eq_ref PRIMARY PRIMARY 4 test.t7.artistid 1
+1 SIMPLE t2 eq_ref PRIMARY PRIMARY 4 test.t1.metaid 1 StarJoin(t1)
+1 SIMPLE t7 ref PRIMARY PRIMARY 4 test.t1.metaid 1 Using index; StarJoin(t1)
+1 SIMPLE t3 ref t3_metaid,t3_formatid,t3_metaidformatid t3_metaid 4 test.t1.metaid 2 Using where; StarJoin(t4)
+1 SIMPLE t8 eq_ref PRIMARY PRIMARY 4 test.t7.artistid 1 StarJoin(t7)
1 SIMPLE t9 index PRIMARY,t9_subgenreid,t9_metaid PRIMARY 8 NULL 2 Using where; Using index; Using join buffer (BNL, regular buffers)
1 SIMPLE t10 eq_ref PRIMARY,t10_genreid PRIMARY 4 test.t9.subgenreid 1
1 SIMPLE t11 eq_ref PRIMARY PRIMARY 4 test.t10.genreid 1
@@ -1613,7 +1613,7 @@ t1.b IS NULL AND t2.b IS NULL AND t3.b I
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 ALL PRIMARY NULL NULL NULL 16384 Using where
1 SIMPLE t2 eq_ref PRIMARY PRIMARY 4 test.t1.a 1 Using where
-1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.a 1 Using where
+1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.a 1 Using where; StarJoin(t1)
SELECT COUNT(*) FROM t1,t2,t3
WHERE t1.a=t2.a AND t2.a=t3.a AND
t1.b IS NULL AND t2.b IS NULL AND t3.b IS NULL;
@@ -1815,8 +1815,8 @@ where t2.b=t1.b and t3.d=t1.d and t4.c=t
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t1 ALL NULL NULL NULL NULL 7 Using where
1 SIMPLE t2 ref idx idx 5 test.t1.b 1
-1 SIMPLE t3 ref idx idx 5 test.t1.d 1
-1 SIMPLE t4 ref idx idx 5 test.t1.c 1
+1 SIMPLE t3 ref idx idx 5 test.t1.d 1 StarJoin(t1)
+1 SIMPLE t4 ref idx idx 5 test.t1.c 1 StarJoin(t1)
select t1.a, t1.b, t1.c, t1.d, t2.e, t3.f, t4.g from t1,t2,t3,t4
where t2.b=t1.b and t3.d=t1.d and t4.c=t1.c;
a b c d e f g
@@ -1865,8 +1865,8 @@ id select_type table type possible_keys
1 SIMPLE t1 ALL NULL NULL NULL NULL 349 Using where
1 SIMPLE t2 eq_ref PRIMARY PRIMARY 8 test.t1.id3 1 Using where
1 SIMPLE t3 eq_ref PRIMARY PRIMARY 8 test.t2.id4 1 Using where
-1 SIMPLE t4 eq_ref PRIMARY PRIMARY 8 test.t1.id2 1
-1 SIMPLE t5 eq_ref PRIMARY PRIMARY 16 test.t1.id1,test.t1.id2 1 Using where
+1 SIMPLE t4 eq_ref PRIMARY PRIMARY 8 test.t1.id2 1 StarJoin(t1)
+1 SIMPLE t5 eq_ref PRIMARY PRIMARY 16 test.t1.id1,test.t1.id2 1 Using where; StarJoin(t1)
SELECT STRAIGHT_JOIN t1.id1, t1.num3, t3.text1, t3.id4, t2.id3, t4.dummy
FROM t1 JOIN t2 JOIN t3 JOIN t4 JOIN t5
WHERE t1.id1=t5.id1 AND t1.id2=t5.id2 and t4.id2=t1.id2 AND
=== modified file 'mysql-test/r/join_nested.result'
--- a/mysql-test/r/join_nested.result 2010-10-04 13:10:35 +0000
+++ b/mysql-test/r/join_nested.result 2010-10-06 15:22:47 +0000
@@ -1447,7 +1447,7 @@ id select_type table type possible_keys
1 SIMPLE t2 ALL NULL NULL NULL NULL X
1 SIMPLE t3 ref a a 5 test.t2.b X
1 SIMPLE t5 ref a a 5 test.t3.b X
-1 SIMPLE t4 ref a a 5 test.t3.b X Using where
+1 SIMPLE t4 ref a a 5 test.t3.b X Using where; StarJoin(t2)
explain select * from (t4 join t6 on t6.a=t4.b) right join t3 on t4.a=t3.b
join t2 left join (t5 join t7 on t7.a=t5.b) on t5.a=t2.b where t3.a<=>t2.b;
id select_type table type possible_keys key key_len ref rows Extra
@@ -1465,7 +1465,7 @@ id select_type table type possible_keys
1 SIMPLE t3 ref a a 5 test.t2.b X
1 SIMPLE t4 ref a a 5 test.t3.b X
1 SIMPLE t6 ref a a 5 test.t4.b X
-1 SIMPLE t5 ref a a 5 test.t3.b X
+1 SIMPLE t5 ref a a 5 test.t3.b X StarJoin(t3)
drop table t0, t1, t2, t3, t4, t5, t6, t7;
create table t1 (a int);
insert into t1 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
@@ -1733,7 +1733,7 @@ id select_type table type possible_keys
1 SIMPLE t1 eq_ref PRIMARY PRIMARY 4 test.t2.package_id 1
1 SIMPLE t4 eq_ref PRIMARY,id PRIMARY 2 test.t1.carrier 1
1 SIMPLE t5 ref carrier_id carrier_id 5 test.t4.id 22 Using index
-1 SIMPLE t3 ref package_id package_id 5 test.t1.id 1 Using where; Using index
+1 SIMPLE t3 ref package_id package_id 5 test.t1.id 1 Using where; Using index; StarJoin(t1)
SELECT COUNT(*)
FROM ((t2 JOIN t1 ON t2.package_id = t1.id)
JOIN t3 ON t3.package_id = t1.id)
=== modified file 'mysql-test/r/order_by_none.result'
--- a/mysql-test/r/order_by_none.result 2010-09-27 13:20:24 +0000
+++ b/mysql-test/r/order_by_none.result 2010-10-06 15:22:47 +0000
@@ -497,7 +497,7 @@ EXPLAIN select t1.gid, t2.sid, t3.uid fr
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t2 ALL PRIMARY,uid NULL NULL NULL 6 Using temporary; Using filesort
1 SIMPLE t3 eq_ref PRIMARY PRIMARY 2 test.t2.uid 1 Using where; Using index
-1 SIMPLE t1 eq_ref PRIMARY PRIMARY 4 test.t2.gid 1 Using index
+1 SIMPLE t1 eq_ref PRIMARY PRIMARY 4 test.t2.gid 1 Using index; StarJoin(t2)
EXPLAIN SELECT t1.gid, t3.uid from t1, t3 where t1.gid = t3.uid order by t1.gid,t3.skr;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t3 ALL PRIMARY NULL NULL NULL 6 Using temporary; Using filesort
@@ -506,7 +506,7 @@ EXPLAIN SELECT t1.gid, t2.sid, t3.uid fr
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t2 ALL PRIMARY,uid NULL NULL NULL 6 Using temporary; Using filesort
1 SIMPLE t1 eq_ref PRIMARY PRIMARY 4 test.t2.gid 1 Using index
-1 SIMPLE t3 eq_ref PRIMARY PRIMARY 2 test.t2.uid 1 Using where; Using index
+1 SIMPLE t3 eq_ref PRIMARY PRIMARY 2 test.t2.uid 1 Using where; Using index; StarJoin(t2)
EXPLAIN SELECT t1.gid, t3.uid from t1, t3 where t1.gid = t3.uid order by t3.skr,t1.gid;
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE t3 ALL PRIMARY NULL NULL NULL 6 Using temporary; Using filesort
=== added file 'mysql-test/r/shortcut.result'
--- a/mysql-test/r/shortcut.result 1970-01-01 00:00:00 +0000
+++ b/mysql-test/r/shortcut.result 2010-10-06 15:22:47 +0000
@@ -0,0 +1,744 @@
+#
+# wl3724: Short-Cutting Join Execution: Speeding up star queries
+#
+#
+# Test 1. Basic tests.
+#
+# Test 1a. Tests of EXPLAIN.
+#
+CREATE TABLE t1 (
+a INT,
+b INT
+);
+INSERT INTO t1 VALUES (1, 2), (-1, -1);
+CREATE TABLE t2 (
+a INT,
+KEY( a )
+);
+INSERT INTO t2 VALUES (1), (1), (1), (1), (1);
+CREATE TABLE t3 (
+b INT,
+KEY( b )
+);
+INSERT INTO t3 VALUES (1), (1), (1), (1), (1), (1);
+EXPLAIN SELECT * FROM t1 JOIN t2 USING( a ) JOIN t3 USING( b );
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2 Using where
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using index
+1 SIMPLE t3 ref b b 5 test.t1.b 2 Using index; StarJoin(t1)
+SELECT * FROM t1 JOIN t2 USING( a ) JOIN t3 USING( b );
+b a
+# Test that the short-cut does not cross an outer join boundary
+EXPLAIN SELECT * FROM t1 LEFT JOIN ( t2, t3 ) USING( b );
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2
+1 SIMPLE t3 ref b b 5 test.t1.b 2 Using index
+1 SIMPLE t2 index NULL a 5 NULL 5 Using index
+EXPLAIN SELECT * FROM t1 LEFT JOIN ( t2 JOIN t3 ON a = b ) USING( b );
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2
+1 SIMPLE t3 ref b b 5 test.t1.b 2 Using index
+1 SIMPLE t2 ref a a 5 test.t3.b 2 Using index
+# Test that the optimization is robust wrt reordering of tables
+EXPLAIN SELECT * FROM t1, t2, t3 WHERE t1.a = t2.a AND t1.b = t3.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2 Using where
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using index
+1 SIMPLE t3 ref b b 5 test.t1.b 2 Using index; StarJoin(t1)
+EXPLAIN SELECT * FROM t1, t3, t2 WHERE t1.a = t2.a AND t1.b = t3.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2 Using where
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using index
+1 SIMPLE t3 ref b b 5 test.t1.b 2 Using index; StarJoin(t1)
+EXPLAIN SELECT * FROM t2, t1, t3 WHERE t1.a = t2.a AND t1.b = t3.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2 Using where
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using index
+1 SIMPLE t3 ref b b 5 test.t1.b 2 Using index; StarJoin(t1)
+EXPLAIN SELECT * FROM t2, t3, t1 WHERE t1.a = t2.a AND t1.b = t3.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2 Using where
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using index
+1 SIMPLE t3 ref b b 5 test.t1.b 2 Using index; StarJoin(t1)
+EXPLAIN SELECT * FROM t3, t1, t2 WHERE t1.a = t2.a AND t1.b = t3.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2 Using where
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using index
+1 SIMPLE t3 ref b b 5 test.t1.b 2 Using index; StarJoin(t1)
+EXPLAIN SELECT * FROM t3, t2, t1 WHERE t1.a = t2.a AND t1.b = t3.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2 Using where
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using index
+1 SIMPLE t3 ref b b 5 test.t1.b 2 Using index; StarJoin(t1)
+DROP TABLE t1, t2, t3;
+# Test that short-cuts show up in EXPLAIN properly with "Using index"
+CREATE TABLE t1 ( a INT );
+INSERT INTO t1 VALUES (1), (2), (3);
+CREATE TABLE t2 ( b INT KEY );
+INSERT INTO t2 VALUES (1), (2), (3);
+CREATE TABLE t3 ( c INT KEY );
+INSERT INTO t3 VALUES (1), (2), (3);
+EXPLAIN SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 3 Using where
+1 SIMPLE t2 eq_ref PRIMARY PRIMARY 4 test.t1.a 1 Using index
+1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.a 1 Using index; StarJoin(t1)
+# Test that we don't take a short-cut if we have successfully read a
+# record already.
+EXPLAIN
+SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c WHERE c > 1;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 3 Using where
+1 SIMPLE t2 index PRIMARY PRIMARY 4 NULL 3 Using where; Using index; Using join buffer (BNL, regular buffers)
+1 SIMPLE t3 eq_ref PRIMARY PRIMARY 4 test.t1.a 1 Using index
+SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c WHERE c > 1;
+a b c
+2 2 2
+3 3 3
+DROP TABLE t1, t2, t3;
+#
+# Test 1b.
+# Tests that short-cuts work properly with join buffers.
+#
+CREATE TABLE t1 ( a INT );
+INSERT INTO t1 VALUES (1), (2), (3);
+CREATE TABLE t2 ( b INT );
+INSERT INTO t2 VALUES (1), (2), (3);
+CREATE TABLE t2key ( b INT KEY );
+INSERT INTO t2key VALUES (1), (2), (3);
+CREATE TABLE t3 ( c INT, d INT );
+INSERT INTO t3 VALUES (1, -1), (2, 1), (3, 1);
+# Should not use short-cuts.
+EXPLAIN
+SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c WHERE d > 0;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 3
+1 SIMPLE t2 ALL NULL NULL NULL NULL 3 Using where; Using join buffer (BNL, regular buffers)
+1 SIMPLE t3 ALL NULL NULL NULL NULL 3 Using where; Using join buffer (BNL, regular buffers)
+SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c WHERE d > 0;
+a b c d
+2 2 2 1
+3 3 3 1
+# Should not use short-cuts.
+EXPLAIN
+SELECT * FROM t1 JOIN t2key ON a = b JOIN t3 ON a = c WHERE d > 0;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 3 Using where
+1 SIMPLE t2key eq_ref PRIMARY PRIMARY 4 test.t1.a 1 Using index
+1 SIMPLE t3 ALL NULL NULL NULL NULL 3 Using where; Using join buffer (BNL, regular buffers)
+SELECT * FROM t1 JOIN t2key ON a = b JOIN t3 ON a = c WHERE d > 0;
+a b c d
+2 2 2 1
+3 3 3 1
+DROP TABLE t1, t2, t2key, t3;
+# Test that we reject a short-cut properly. We have a cartesian product
+# of a table and the result of an outer join. The optimizer places the
+# table between the outer and inner table of the outer join and hence
+# there is a short-cut from the inner table to the outer table. This
+# short-cut should be rejected.
+CREATE TABLE t1 ( a INT PRIMARY KEY );
+INSERT INTO t1 VALUES (1),(2);
+CREATE TABLE t2 ( a INT );
+INSERT INTO t2 VALUES (1), (2), (3);
+CREATE TABLE t3 ( a INT );
+INSERT INTO t3 VALUES (1), (2), (3);
+# Should not use short-cuts.
+EXPLAIN
+SELECT * FROM t2, t1 LEFT OUTER JOIN t3 ON (t3.a = t1.a);
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 index NULL PRIMARY 4 NULL 2 Using index
+1 SIMPLE t2 ALL NULL NULL NULL NULL 3 Using join buffer (BNL, regular buffers)
+1 SIMPLE t3 ALL NULL NULL NULL NULL 3 Using where
+SELECT * FROM t2, t1 LEFT OUTER JOIN t3 ON (t3.a = t1.a);
+a a a
+1 1 1
+1 2 2
+2 1 1
+2 2 2
+3 1 1
+3 2 2
+DROP TABLE t1, t2, t3;
+# Test 2
+# That the optimization actually works, i.e. that unneccesary reads are
+# indeed short-cut.
+#
+# Test 2a: We have two tables between giving and receiving end of short-cut:
+# t2 and t3.
+#
+CREATE TABLE t1 ( a INT, b INT );
+INSERT INTO t1 VALUES (1, 2), (-1, -1);
+CREATE TABLE t2 ( a INT, b INT, KEY( a ) );
+INSERT INTO t2 VALUES (1, 2),(1, 2),(1, 2),(1, 2),(1, 2);
+INSERT INTO t2 SELECT * FROM t2;
+CREATE TABLE t3 ( b INT, KEY( b ) );
+INSERT INTO t3 VALUES (1), (1), (1), (1), (1);
+INSERT INTO t3 SELECT * FROM t3;
+CREATE TABLE t4 ( b INT, KEY( b ) );
+INSERT INTO t4 VALUES (1), (1), (1), (1), (1);
+INSERT INTO t4 SELECT * FROM t4;
+INSERT INTO t4 SELECT * FROM t4;
+INSERT INTO t4 SELECT * FROM t4;
+FLUSH STATUS;
+EXPLAIN
+SELECT * FROM t1 JOIN t2 USING(a) JOIN t3 ON t2.a = t3.b JOIN t4 ON t1.b = t4.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2 Using where
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using where
+1 SIMPLE t3 ref b b 5 test.t2.a 2 Using where; Using index
+1 SIMPLE t4 ref b b 5 test.t1.b 4 Using index; StarJoin(t1)
+SELECT * FROM t1 JOIN t2 USING(a) JOIN t3 ON t2.a = t3.b JOIN t4 ON t1.b = t4.b;
+a b b b b
+SHOW STATUS LIKE 'handler_read_%';
+Variable_name Value
+Handler_read_first 0
+Handler_read_key 4
+Handler_read_last 0
+Handler_read_next 0
+Handler_read_prev 0
+Handler_read_rnd 0
+Handler_read_rnd_next 3
+DROP TABLE t1, t2, t3, t4;
+# Test 2b
+# Short-cuts followed by successful keys. This tests that we perform the
+# optimal number of reads after the short-cut is taken without missing tuples.
+CREATE TABLE t1 ( a INT );
+INSERT INTO t1 VALUES (1), (2), (3), (4), (5);
+CREATE TABLE t2 ( a INT, KEY (a) );
+INSERT INTO t2 VALUES (1), (2), (2), (2), (2), (2), (3), (4), (4), (4), (5);
+CREATE TABLE t3 ( a INT, KEY (a) );
+INSERT INTO t3 VALUES (1), (3), (5), (-1), (-1), (-1), (-1), (-1), (-1);
+FLUSH STATUS;
+EXPLAIN
+SELECT STRAIGHT_JOIN * FROM t1 JOIN t2 USING(a) JOIN t3 USING(a);
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 5 Using where
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using index
+1 SIMPLE t3 ref a a 5 test.t1.a 2 Using index; StarJoin(t1)
+SELECT STRAIGHT_JOIN * FROM t1 JOIN t2 USING(a) JOIN t3 USING(a);
+a
+1
+3
+5
+SHOW STATUS LIKE 'handler_read_%';
+Variable_name Value
+Handler_read_first 0
+Handler_read_key 10
+Handler_read_last 0
+Handler_read_next 6
+Handler_read_prev 0
+Handler_read_rnd 0
+Handler_read_rnd_next 6
+DROP TABLE t1, t2, t3;
+#
+# Test 3.
+# Test for outer joins. We may not take short-cuts across outer join
+# boundaries. An outer join boundary goes before the first inner table for an
+# outer join.
+#
+# Test 3a.
+#
+CREATE TABLE t1 ( a INT, b INT );
+INSERT INTO t1 VALUES (1, 2), (-1, -1);
+CREATE TABLE t2 ( a INT, b INT, KEY( a ) );
+INSERT INTO t2 VALUES (1, 2),(1, 2),(1, 2),(1, 2),(1, 2);
+INSERT INTO t2 SELECT * FROM t2;
+CREATE TABLE t3 ( b INT, KEY( b ) );
+INSERT INTO t3 VALUES (1), (1), (1), (1), (1);
+INSERT INTO t3 SELECT * FROM t3;
+CREATE TABLE t4 ( b INT, KEY( b ) );
+INSERT INTO t4 VALUES (1), (1), (1), (1), (1);
+INSERT INTO t4 SELECT * FROM t4;
+INSERT INTO t4 SELECT * FROM t4;
+INSERT INTO t4 SELECT * FROM t4;
+CREATE TABLE t5 ( b INT, KEY( b ) );
+INSERT INTO t5 VALUES (1), (1), (1), (1), (1), (1), (1), (1);
+INSERT INTO t5 SELECT * FROM t5;
+# Test of two outer join boundaries in one join.
+EXPLAIN
+SELECT *
+FROM t1 LEFT JOIN (t2 JOIN t3 ON t2.a = t3.b) USING ( a )
+LEFT JOIN t4 ON t1.a = t4.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2
+1 SIMPLE t2 ref a a 5 test.t1.a 2
+1 SIMPLE t3 ref b b 5 test.t2.a 2 Using index
+1 SIMPLE t4 ref b b 5 test.t1.a 4 Using index
+EXPLAIN
+SELECT *
+FROM t1 LEFT JOIN (t2 JOIN t3 ON t2.a = t3.b) USING(a)
+LEFT JOIN (t4 JOIN t5 USING( b )) ON t1.a = t4.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2
+1 SIMPLE t2 ref a a 5 test.t1.a 2
+1 SIMPLE t3 ref b b 5 test.t2.a 2 Using index
+1 SIMPLE t4 ref b b 5 test.t1.a 4 Using index
+1 SIMPLE t5 ref b b 5 test.t4.b 2 Using index
+DROP TABLE t1, t2, t3, t4, t5;
+# Test 3b.
+# Tests that we do not miss any data due to short-cutting.
+CREATE TABLE t1 ( a INT, b INT );
+CREATE TABLE t2 ( a INT, b INT, PRIMARY KEY (a,b) );
+CREATE TABLE t3 ( a INT, b INT, PRIMARY KEY (a,b) );
+INSERT INTO t1 VALUES ( 1, 1 ), ( 2, 1 ), ( 1, 3 );
+INSERT INTO t2 VALUES ( 1, 1 ), ( 2, 2 ), ( 3, 3 );
+INSERT INTO t3 VALUES ( 1, 1 ), ( 2, 1 ), ( 1, 3 );
+# Test of the short-cut detection algorithm. When traversing the
+# push-down conditions the algorithm will first find that the
+# prospective short-cut t3->t1, but this must be invalidated due to the
+# later found dependency t3->t2.
+EXPLAIN
+SELECT * FROM t1, t2, t3 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.b = t3.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 3 Using where
+1 SIMPLE t2 ref PRIMARY PRIMARY 4 test.t1.a 1 Using index
+1 SIMPLE t3 eq_ref PRIMARY PRIMARY 8 test.t2.b,test.t1.b 1 Using index
+SELECT * FROM t1, t2, t3 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.b = t3.b;
+a b a b a b
+1 1 1 1 1 1
+2 1 2 2 2 1
+1 3 1 1 1 3
+# Test of internal representation of pushdown conditions.
+# The join conditions will be encoded in ref access, while the WHERE
+# expression remains in the pushdown condition.
+EXPLAIN
+SELECT *
+FROM t1 JOIN t2 ON t1.a = t2.a JOIN t3 ON t1.b = t3.a
+WHERE t3.b + 1 = t2.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 3 Using where
+1 SIMPLE t2 ref PRIMARY PRIMARY 4 test.t1.a 1 Using index
+1 SIMPLE t3 ref PRIMARY PRIMARY 4 test.t1.b 1 Using where; Using index
+# Short-cut is actually applicable in this case, thanks to equality
+# propagation. The WHERE condition t3.a + 1 = t2.a is rewritten into
+# t1.b + 1 = t1.a, and hence we have an optimizable star query.
+EXPLAIN
+SELECT *
+FROM t1 JOIN t2 ON t1.a = t2.a JOIN t3 ON t1.b = t3.a
+WHERE t3.a + 1 = t2.a;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 3 Using where
+1 SIMPLE t2 ref PRIMARY PRIMARY 4 test.t1.a 1 Using index
+1 SIMPLE t3 ref PRIMARY PRIMARY 4 test.t1.b 1 Using index; StarJoin(t1)
+DROP TABLE t1, t2, t3;
+# Test 3c
+CREATE TABLE t1 ( a INT );
+INSERT INTO t1 VALUES (1), (1), (1), (1);
+CREATE TABLE t2 ( a INT, KEY (a), b INT, c INT );
+INSERT INTO t2 VALUES (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1);
+INSERT INTO t2 SELECT * FROM t2;
+INSERT INTO t2 SELECT * FROM t2;
+CREATE TABLE t3 ( a INT, KEY (a) );
+INSERT INTO t3 VALUES (1), (1), (1), (1), (1), (1), (1), (1), (1), (1), (3);
+CREATE TABLE t4 ( a INT, KEY (a), b INT );
+INSERT INTO t4 VALUES (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1);
+INSERT INTO t4 SELECT * FROM t4;
+#
+# Test that the short-cut t4->t1 is rejected in favor of t4->t2.
+#
+EXPLAIN
+SELECT STRAIGHT_JOIN *
+FROM t1 JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t2.b = t3.a
+JOIN t4 ON t1.a = t4.a AND t2.c = t4.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 4 Using where
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using where
+1 SIMPLE t3 ref a a 5 test.t2.b 2 Using index
+1 SIMPLE t4 ref a a 5 test.t1.a 2 Using where; StarJoin(t2)
+DROP TABLE t1, t2, t3, t4;
+# Test 4. Test of execution step.
+# In this test we are testing that a short-cut is properly separated from
+# the case of a normal 'end of records' state on the last table in the plan.
+# This particular case gets hit only when
+# - The optimizer reorders the tables
+# - We have a SELECT <table>.*
+CREATE TABLE t1( a INT );
+CREATE TABLE t2( a INT PRIMARY KEY );
+CREATE TABLE t3( a INT, INDEX( a ) );
+INSERT INTO t1( a ) VALUES ( 2 );
+INSERT INTO t1( a ) VALUES ( 2 );
+INSERT INTO t2( a ) VALUES ( 1 );
+INSERT INTO t2( a ) VALUES ( 2 );
+INSERT INTO t3( a ) VALUES ( 6 );
+INSERT INTO t3( a ) VALUES ( 5 );
+INSERT INTO t3( a ) VALUES ( 2 );
+EXPLAIN
+SELECT t2.* FROM t2, t1, t3 WHERE t2.a = t1.a AND t1.a = t3.a;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2 Using where
+1 SIMPLE t2 eq_ref PRIMARY PRIMARY 4 test.t1.a 1 Using index
+1 SIMPLE t3 ref a a 5 test.t2.a 2 Using where; Using index; StarJoin(t1)
+SELECT t2.* FROM t2, t1, t3 WHERE t2.a = t1.a AND t1.a = t3.a;
+a
+2
+2
+DROP TABLE t1, t2, t3;
+#
+# Test 5.
+# Tests that a short-cut does not cross a plan node that is using join
+# buffering.
+#
+# Test 5a.
+#
+CREATE TABLE t1 ( a INT, c INT );
+INSERT INTO t1 VALUES (1, 2), (-1, -1);
+CREATE TABLE t2 ( a INT, b INT, KEY( a ), KEY( b ) );
+INSERT INTO t2 VALUES (1, 2),(1, 2),(1, 2),(1, 2),(1, 2);
+CREATE TABLE t3 ( a INT, KEY( a ) );
+INSERT INTO t3 VALUES (2), (2), (2), (2), (2);
+INSERT INTO t3 SELECT * FROM t3;
+INSERT INTO t3 SELECT * FROM t3;
+INSERT INTO t3 SELECT * FROM t3;
+CREATE TABLE t4 ( a INT, KEY( a ) );
+INSERT INTO t4 VALUES (1), (1), (1), (1), (1);
+INSERT INTO t4 SELECT * FROM t4;
+INSERT INTO t4 SELECT * FROM t4;
+INSERT INTO t4 SELECT * FROM t4;
+INSERT INTO t4 SELECT * FROM t4;
+FLUSH STATUS;
+# Should not use short-cuts.
+EXPLAIN
+SELECT * FROM t1, t2, t3, t4 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.c = t4.a;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2 Using where
+1 SIMPLE t2 ALL a,b NULL NULL NULL 5 Using where; Using join buffer (BNL, regular buffers)
+1 SIMPLE t3 ref a a 5 test.t2.b 4 Using index
+1 SIMPLE t4 ref a a 5 test.t1.c 9 Using index
+SELECT * FROM t1, t2, t3, t4 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.c = t4.a;
+a c a b a a
+# Should not use short-cuts.
+EXPLAIN
+SELECT * FROM t1, t2, t3, t4 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.c = t4.a;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2 Using where
+1 SIMPLE t2 ALL a,b NULL NULL NULL 5 Using where; Using join buffer (BNL, regular buffers)
+1 SIMPLE t3 ref a a 5 test.t2.b 4 Using index
+1 SIMPLE t4 ref a a 5 test.t1.c 9 Using index
+SELECT * FROM t1, t2, t3, t4 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.c = t4.a;
+a c a b a a
+SHOW STATUS LIKE 'handler_read_%';
+Variable_name Value
+Handler_read_first 0
+Handler_read_key 410
+Handler_read_last 0
+Handler_read_next 400
+Handler_read_prev 0
+Handler_read_rnd 0
+Handler_read_rnd_next 18
+DROP TABLE t1, t2, t3, t4;
+#
+# Test 5b.
+#
+CREATE TABLE t1 ( a INT, c INT );
+INSERT INTO t1 VALUES (1, 2), (-1, -1);
+CREATE TABLE t2 ( a INT, b INT, KEY( a, b ) );
+INSERT INTO t2 VALUES (1, 2),(1, 2),(1, 2),(1, 2),(1, 2);
+CREATE TABLE t3 ( a INT );
+INSERT INTO t3 VALUES (2), (2), (2), (2), (2);
+INSERT INTO t3 SELECT * FROM t3;
+CREATE TABLE t4 ( a INT );
+INSERT INTO t4 VALUES (1), (1), (1), (1), (1);
+INSERT INTO t4 SELECT * FROM t4;
+INSERT INTO t4 SELECT * FROM t4;
+FLUSH STATUS;
+# Should not use short-cuts.
+EXPLAIN
+SELECT * FROM t1, t2, t3, t4 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.c = t4.a;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 2 Using where
+1 SIMPLE t2 ref a a 5 test.t1.a 1 Using index
+1 SIMPLE t3 ALL NULL NULL NULL NULL 10 Using where; Using join buffer (BNL, regular buffers)
+1 SIMPLE t4 ALL NULL NULL NULL NULL 20 Using where; Using join buffer (BNL, regular buffers)
+SELECT * FROM t1, t2, t3, t4 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.c = t4.a;
+a c a b a a
+SHOW STATUS LIKE 'handler_read_%';
+Variable_name Value
+Handler_read_first 0
+Handler_read_key 2
+Handler_read_last 0
+Handler_read_next 5
+Handler_read_prev 0
+Handler_read_rnd 0
+Handler_read_rnd_next 35
+DROP TABLE t1, t2, t3, t4;
+#
+# Test 6. Test of short-cuts in conjunction with outer join.
+#
+# Test 6a. Test of outer join detection.
+# In this case the execution order is t1, t2, t3, t4.
+# t2, t3 and t4 will form an 'outer join nest' with which t1 is left
+# outer joined. But (t3, t2) is left joined with t4. Since t4 is just one
+# table, however, the 'outer join nest' of t4 is only implicitly
+# represented in the query plan. The only way to detect it is by looking
+# at t4's first_inner pointer, which would be null for the last inner table
+# in an outer join nest. But since it points to itseld, t4 is in its own
+# nest. But there is no NESTED_JOIN to represent it, since it follows the
+# 'normal' left-deep tree representation.
+#
+CREATE TABLE t1 (a INT, b INT, c INT);
+CREATE TABLE t2 (d INT, e INT, f INT);
+CREATE TABLE t3 (g INT, h INT, i INT);
+CREATE TABLE t4 (j INT, k INT, l INT);
+INSERT INTO t1 VALUES (3,1,0), (2,2,0), (3,3,0);
+INSERT INTO t2 VALUES (1,1,0), (2,2,0);
+INSERT INTO t3 VALUES (3,2,0), (6,2,0), (6,1,0);
+INSERT INTO t4 VALUES (0,2,0), (1,2,0);
+EXPLAIN
+SELECT a, b, c, d, e, f, g, h, i, j, k, l
+FROM t1 LEFT JOIN ( (t3, t2) LEFT JOIN t4 ON t2.e = t4.k AND t3.h < 10 ) ON t1.b = t2.e;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 3
+1 SIMPLE t2 ALL NULL NULL NULL NULL 2 Using where
+1 SIMPLE t3 ALL NULL NULL NULL NULL 3
+1 SIMPLE t4 ALL NULL NULL NULL NULL 2 Using where
+SELECT *
+FROM t1 LEFT JOIN ( (t3, t2) LEFT JOIN t4 ON t2.e = t4.k AND t3.h < 10 ) ON t1.b = t2.e;
+a b c g h i d e f j k l
+3 1 0 3 2 0 1 1 0 NULL NULL NULL
+3 1 0 6 2 0 1 1 0 NULL NULL NULL
+3 1 0 6 1 0 1 1 0 NULL NULL NULL
+2 2 0 3 2 0 2 2 0 0 2 0
+2 2 0 3 2 0 2 2 0 1 2 0
+2 2 0 6 2 0 2 2 0 0 2 0
+2 2 0 6 2 0 2 2 0 1 2 0
+2 2 0 6 1 0 2 2 0 0 2 0
+2 2 0 6 1 0 2 2 0 1 2 0
+3 3 0 NULL NULL NULL NULL NULL NULL NULL NULL NULL
+DROP TABLE t1, t2, t3, t4;
+#
+# Test 6b.
+# We may take short-cuts across or inside an outer join, as long as we
+# don't fail due to an outer join predicate. It goes as follows.
+#
+# - We may take a short-cut across a nested outer join.
+# - We may take short-cuts inside a nested inner join sequence.
+#
+CREATE TABLE t1 ( a INT );
+INSERT INTO t1 VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10);
+CREATE TABLE t2 ( b INT, KEY ( b ) );
+INSERT INTO t2 VALUES (1), (2), (4), (5), (6), (7), (8), (9), (10);
+CREATE TABLE t3 ( c INT, KEY( c ) );
+INSERT INTO t3 VALUES (1), (2), (3), (4), (6), (7), (8), (9), (10);
+CREATE TABLE t4 ( d INT, KEY( d ) );
+INSERT INTO t4 VALUES (1), (2), (3), (4), (5), (6), (7), (8), (10);
+INSERT INTO t4 VALUES (10), (10), (10), (10);
+CREATE TABLE t5 ( e INT, KEY( e ) );
+INSERT INTO t5 VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10);
+# Outer join followed by a table that is inner joined with the first.
+EXPLAIN
+SELECT * FROM t1 LEFT JOIN t2 ON a = b JOIN t3 ON a = c;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 10 Using where
+1 SIMPLE t2 ref b b 5 test.t1.a 2 Using index
+1 SIMPLE t3 ref c c 5 test.t1.a 2 Using index; StarJoin(t1)
+SELECT * FROM t1 LEFT JOIN t2 ON a = b JOIN t3 ON a = c;
+a b c
+1 1 1
+2 2 2
+3 NULL 3
+4 4 4
+6 6 6
+7 7 7
+8 8 8
+9 9 9
+10 10 10
+# Short-cut across a nested outer join
+EXPLAIN
+SELECT * FROM t1 JOIN (t2 LEFT JOIN t3 ON b = c) ON a = b JOIN t4 ON a = d;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 10 Using where
+1 SIMPLE t2 ref b b 5 test.t1.a 2 Using index
+1 SIMPLE t3 ref c c 5 test.t1.a 2 Using index
+1 SIMPLE t4 ref d d 5 test.t1.a 2 Using index; StarJoin(t1)
+SELECT * FROM t1 JOIN (t2 LEFT JOIN t3 ON b = c) ON a = b JOIN t4 ON a = d;
+a b c d
+1 1 1 1
+2 2 2 2
+4 4 4 4
+5 5 NULL 5
+6 6 6 6
+7 7 7 7
+8 8 8 8
+10 10 10 10
+10 10 10 10
+10 10 10 10
+10 10 10 10
+10 10 10 10
+# Short-cut across a nested outer join with a nested inner join
+EXPLAIN
+SELECT * FROM t1
+JOIN (t2 LEFT JOIN (t3 JOIN t4 ON c = d) ON b = d) ON a = b
+JOIN t5 ON a = e;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 10 Using where
+1 SIMPLE t2 ref b b 5 test.t1.a 2 Using where; Using index
+1 SIMPLE t3 ref c c 5 test.t2.b 2 Using where; Using index
+1 SIMPLE t4 ref d d 5 test.t3.c 2 Using where; Using index
+1 SIMPLE t5 ref e e 5 test.t2.b 2 Using where; Using index; StarJoin(t2)
+SELECT * FROM t1
+JOIN (t2 LEFT JOIN (t3 JOIN t4 ON c = d) ON b = d) ON a = b
+JOIN t5 ON a = e;
+a b c d e
+1 1 1 1 1
+2 2 2 2 2
+4 4 4 4 4
+5 5 NULL NULL 5
+6 6 6 6 6
+7 7 7 7 7
+8 8 8 8 8
+9 9 NULL NULL 9
+10 10 10 10 10
+10 10 10 10 10
+10 10 10 10 10
+10 10 10 10 10
+10 10 10 10 10
+# Short-cut from last inner table inside an inner join that is nested
+# within an outer join
+EXPLAIN
+SELECT * FROM t1 LEFT JOIN (t2 JOIN t3 ON b = c JOIN t4 ON b = d) on a = b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 10
+1 SIMPLE t2 ref b b 5 test.t1.a 2 Using index
+1 SIMPLE t3 ref c c 5 test.t2.b 2 Using index
+1 SIMPLE t4 ref d d 5 test.t2.b 2 Using index; StarJoin(t2)
+SELECT * FROM t1 LEFT JOIN (t2 JOIN t3 ON b = c JOIN t4 ON b = d) on a = b;
+a b c d
+1 1 1 1
+2 2 2 2
+3 NULL NULL NULL
+4 4 4 4
+5 NULL NULL NULL
+6 6 6 6
+7 7 7 7
+8 8 8 8
+9 NULL NULL NULL
+10 10 10 10
+10 10 10 10
+10 10 10 10
+10 10 10 10
+10 10 10 10
+# Short-cut from not last inner table inside an inner join that is nested
+# within an outer join
+EXPLAIN
+SELECT * FROM t1
+LEFT JOIN
+(t2 JOIN t3 ON b = c JOIN t4 ON b = d JOIN t5 ON d = e)
+ON a = b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 10
+1 SIMPLE t2 ref b b 5 test.t1.a 2 Using index
+1 SIMPLE t3 ref c c 5 test.t2.b 2 Using index
+1 SIMPLE t4 ref d d 5 test.t2.b 2 Using index; StarJoin(t2)
+1 SIMPLE t5 ref e e 5 test.t4.d 2 Using index
+SELECT * FROM t1
+LEFT JOIN
+(t2 JOIN t3 ON b = c JOIN t4 ON b = d JOIN t5 ON d = e)
+ON a = b;
+a b c d e
+1 1 1 1 1
+2 2 2 2 2
+3 NULL NULL NULL NULL
+4 4 4 4 4
+5 NULL NULL NULL NULL
+6 6 6 6 6
+7 7 7 7 7
+8 8 8 8 8
+9 NULL NULL NULL NULL
+10 10 10 10 10
+10 10 10 10 10
+10 10 10 10 10
+10 10 10 10 10
+10 10 10 10 10
+# Illegal scenario for short-cut. Should not be taken.
+EXPLAIN
+SELECT * FROM t1 JOIN t2 ON a = b LEFT JOIN t3 ON a = c;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 10 Using where
+1 SIMPLE t2 ref b b 5 test.t1.a 2 Using index
+1 SIMPLE t3 ref c c 5 test.t1.a 2 Using index
+SELECT * FROM t1 JOIN t2 ON a = b LEFT JOIN t3 ON a = c;
+a b c
+1 1 1
+2 2 2
+4 4 4
+5 5 NULL
+6 6 6
+7 7 7
+8 8 8
+9 9 9
+10 10 10
+EXPLAIN
+SELECT * FROM t1 JOIN t2 ON a = b LEFT JOIN (t3 JOIN t4 ON c = d) ON a = c;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 10 Using where
+1 SIMPLE t2 ref b b 5 test.t1.a 2 Using index
+1 SIMPLE t3 ref c c 5 test.t1.a 2 Using index
+1 SIMPLE t4 ref d d 5 test.t1.a 2 Using index
+SELECT * FROM t1 JOIN t2 ON a = b LEFT JOIN (t3 JOIN t4 ON c = d) ON a = c;
+a b c d
+1 1 1 1
+2 2 2 2
+4 4 4 4
+5 5 NULL NULL
+6 6 6 6
+7 7 7 7
+8 8 8 8
+9 9 NULL NULL
+10 10 10 10
+10 10 10 10
+10 10 10 10
+10 10 10 10
+10 10 10 10
+DROP TABLE t1, t2, t3, t4, t5;
+#
+# Test 6c.
+# Tests that short-cuts work even if a record was read and then rejected.
+# This happens for table scan without join buffering.
+#
+set optimizer_join_cache_level = 0;;
+CREATE TABLE t1 ( a INT );
+INSERT INTO t1 VALUES (1), (2), (3);
+CREATE TABLE t2 ( b INT );
+INSERT INTO t2 VALUES (1), (2), (2), (2), (2), (3);
+CREATE TABLE t3 ( c INT, d INT );
+INSERT INTO t3(c) VALUES (1), (3), (4), (4), (4), (4);
+FLUSH STATUS;
+EXPLAIN
+SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 3
+1 SIMPLE t2 ALL NULL NULL NULL NULL 6 Using where
+1 SIMPLE t3 ALL NULL NULL NULL NULL 6 Using where; StarJoin(t1)
+SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c;
+a b c d
+1 1 1 NULL
+3 3 3 NULL
+SHOW STATUS LIKE 'handler_read%';
+Variable_name Value
+Handler_read_first 0
+Handler_read_key 0
+Handler_read_last 0
+Handler_read_next 0
+Handler_read_prev 0
+Handler_read_rnd 0
+Handler_read_rnd_next 34
+FLUSH STATUS;
+EXPLAIN
+SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c WHERE d > 0;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 3
+1 SIMPLE t2 ALL NULL NULL NULL NULL 6 Using where
+1 SIMPLE t3 ALL NULL NULL NULL NULL 6 Using where; StarJoin(t1)
+SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c WHERE d > 0;
+a b c d
+SHOW STATUS LIKE 'handler_read%';
+Variable_name Value
+Handler_read_first 0
+Handler_read_key 0
+Handler_read_last 0
+Handler_read_next 0
+Handler_read_prev 0
+Handler_read_rnd 0
+Handler_read_rnd_next 34
+set @@optimizer_join_cache_level = DEFAULT;
+DROP TABLE t1, t2, t3;
=== modified file 'mysql-test/r/subselect_innodb.result'
--- a/mysql-test/r/subselect_innodb.result 2010-10-04 13:10:35 +0000
+++ b/mysql-test/r/subselect_innodb.result 2010-10-06 15:22:47 +0000
@@ -278,7 +278,7 @@ EXPLAIN EXTENDED SELECT t2.*, t4.DOCTYPE
id select_type table type possible_keys key key_len ref rows filtered Extra
1 PRIMARY t2 ALL DDOCTYPEID_IDX NULL NULL NULL 9 100.00 Using where
1 PRIMARY t1 eq_ref PRIMARY PRIMARY 34 test.t2.DOCID 1 100.00
-1 PRIMARY t4 eq_ref PRIMARY PRIMARY 34 test.t2.DOCTYPEID 1 100.00
+1 PRIMARY t4 eq_ref PRIMARY PRIMARY 34 test.t2.DOCTYPEID 1 100.00 StarJoin(t2)
2 DEPENDENT SUBQUERY t3 unique_subquery PRIMARY,FFOLDERID_IDX PRIMARY 34 func 1 100.00 Using where
3 DEPENDENT SUBQUERY t3 unique_subquery PRIMARY,FFOLDERID_IDX PRIMARY 34 func 1 100.00 Using where
4 DEPENDENT SUBQUERY t3 unique_subquery PRIMARY,FFOLDERID_IDX PRIMARY 34 func 1 100.00 Using where
@@ -286,6 +286,9 @@ id select_type table type possible_keys
6 DEPENDENT SUBQUERY t3 unique_subquery PRIMARY,FFOLDERID_IDX,CMFLDRPARNT_IDX PRIMARY 34 func 1 100.00 Using where
Warnings:
Note 1003 select `test`.`t2`.`DOCID` AS `DOCID`,`test`.`t2`.`DOCNAME` AS `DOCNAME`,`test`.`t2`.`DOCTYPEID` AS `DOCTYPEID`,`test`.`t2`.`FOLDERID` AS `FOLDERID`,`test`.`t2`.`AUTHOR` AS `AUTHOR`,`test`.`t2`.`CREATED` AS `CREATED`,`test`.`t2`.`TITLE` AS `TITLE`,`test`.`t2`.`SUBTITLE` AS `SUBTITLE`,`test`.`t2`.`DOCABSTRACT` AS `DOCABSTRACT`,`test`.`t2`.`PUBLISHDATE` AS `PUBLISHDATE`,`test`.`t2`.`EXPIRATIONDATE` AS `EXPIRATIONDATE`,`test`.`t2`.`LOCKEDBY` AS `LOCKEDBY`,`test`.`t2`.`STATUS` AS `STATUS`,`test`.`t2`.`PARENTDOCID` AS `PARENTDOCID`,`test`.`t2`.`REPID` AS `REPID`,`test`.`t2`.`MODIFIED` AS `MODIFIED`,`test`.`t2`.`MODIFIER` AS `MODIFIER`,`test`.`t2`.`PUBLISHSTATUS` AS `PUBLISHSTATUS`,`test`.`t2`.`ORIGINATOR` AS `ORIGINATOR`,`test`.`t4`.`DOCTYPENAME` AS `DOCTYPENAME`,`test`.`t1`.`CONTENTSIZE` AS `CONTENTSIZE`,`test`.`t1`.`MIMETYPE` AS `MIMETYPE` from `test`.`t2` join `test`.`t4` left join `test`.`t1` on((`test`.`t1`.`DOCID` = `test`.`t2`.`DOCID`)) where ((`test`.`t4`.`DOCTYPEID` = `test`.`t2`.`DOCTYPEID`) and (`test`.`t2`.`DOCNAME` = 'Last Discussion') and <in_optimizer>(`test`.`t2`.`FOLDERID`,<exists>(<primary_index_lookup>(<cache>(`test`.`t2`.`FOLDERID`) in t3 on PRIMARY where ((`test`.`t3`.`FOLDERNAME` = 'Movie Reviews') and <in_optimizer>(`test`.`t3`.`PARENTID`,<exists>(<primary_index_lookup>(<cache>(`test`.`t3`.`PARENTID`) in t3 on PRIMARY where ((`test`.`t3`.`FOLDERNAME` = 'CopiedFolder') and <in_optimizer>(`test`.`t3`.`PARENTID`,<exists>(<primary_index_lookup>(<cache>(`test`.`t3`.`PARENTID`) in t3 on PRIMARY where ((`test`.`t3`.`FOLDERNAME` = 'Level3') and <in_optimizer>(`test`.`t3`.`PARENTID`,<exists>(<primary_index_lookup>(<cache>(`test`.`t3`.`PARENTID`) in t3 on PRIMARY where ((`test`.`t3`.`FOLDERNAME` = 'Level2') and <in_optimizer>(`test`.`t3`.`PARENTID`,<exists>(<primary_index_lookup>(<cache>(`test`.`t3`.`PARENTID`) in t3 on PRIMARY where ((`test`.`t3`.`FOLDERNAME` = 'Level1') and (`test`.`t3`.`PARENTID` = '2f6161e879db43c1a5b82c21ddc49089') and (<cache>(`test`.`t3`.`PARENTID`) = `test`.`t3`.`FOLDERID`))))) and (<cache>(`test`.`t3`.`PARENTID`) = `test`.`t3`.`FOLDERID`))))) and (<cache>(`test`.`t3`.`PARENTID`) = `test`.`t3`.`FOLDERID`))))) and (<cache>(`test`.`t3`.`PARENTID`) = `test`.`t3`.`FOLDERID`))))) and (<cache>(`test`.`t2`.`FOLDERID`) = `test`.`t3`.`FOLDERID`))))))
+SELECT t2.*, t4.DOCTYPENAME, t1.CONTENTSIZE,t1.MIMETYPE FROM t2 INNER JOIN t4 ON t2.DOCTYPEID = t4.DOCTYPEID LEFT OUTER JOIN t1 ON t2.DOCID = t1.DOCID WHERE t2.FOLDERID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID='2f6161e879db43c1a5b82c21ddc49089' AND t3.FOLDERNAME = 'Level1') AND t3.FOLDERNAME = 'Level2') AND t3.FOLDERNAME = 'Level3') AND t3.FOLDERNAME = 'CopiedFolder') AND t3.FOLDERNAME = 'Movie Reviews') AND t2.DOCNAME = 'Last Discussion';
+DOCID DOCNAME DOCTYPEID FOLDERID AUTHOR CREATED TITLE SUBTITLE DOCABSTRACT PUBLISHDATE EXPIRATIONDATE LOCKEDBY STATUS PARENTDOCID REPID MODIFIED MODIFIER PUBLISHSTATUS ORIGINATOR DOCTYPENAME CONTENTSIZE MIMETYPE
+c373e9f5ad07993f3859444553544200 Last Discussion c373e9f5ad079174ff17444553544200 c373e9f5ad0796c0eca4444553544200 Goldilocks 2003-06-09 11:21:06 Title: Last Discussion NULL Setting new abstract and keeping doc checked out 2003-06-09 10:51:26 2003-06-09 10:51:26 NULL NULL NULL 03eea05112b845949f3fd03278b5fe43 2003-06-09 11:21:06 admin 0 NULL Discussion NULL NULL
drop table t1, t2, t3, t4;
CREATE TABLE t1 (
school_name varchar(45) NOT NULL,
=== added file 'mysql-test/t/shortcut.test'
--- a/mysql-test/t/shortcut.test 1970-01-01 00:00:00 +0000
+++ b/mysql-test/t/shortcut.test 2010-10-06 15:22:47 +0000
@@ -0,0 +1,500 @@
+--echo #
+--echo # wl3724: Short-Cutting Join Execution: Speeding up star queries
+--echo #
+
+--echo #
+--echo # Test 1. Basic tests.
+--echo #
+--echo # Test 1a. Tests of EXPLAIN.
+--echo #
+CREATE TABLE t1 (
+ a INT,
+ b INT
+);
+
+INSERT INTO t1 VALUES (1, 2), (-1, -1);
+
+CREATE TABLE t2 (
+ a INT,
+ KEY( a )
+);
+INSERT INTO t2 VALUES (1), (1), (1), (1), (1);
+
+CREATE TABLE t3 (
+ b INT,
+ KEY( b )
+);
+INSERT INTO t3 VALUES (1), (1), (1), (1), (1), (1);
+
+EXPLAIN SELECT * FROM t1 JOIN t2 USING( a ) JOIN t3 USING( b );
+
+SELECT * FROM t1 JOIN t2 USING( a ) JOIN t3 USING( b );
+
+--echo # Test that the short-cut does not cross an outer join boundary
+EXPLAIN SELECT * FROM t1 LEFT JOIN ( t2, t3 ) USING( b );
+EXPLAIN SELECT * FROM t1 LEFT JOIN ( t2 JOIN t3 ON a = b ) USING( b );
+
+--echo # Test that the optimization is robust wrt reordering of tables
+EXPLAIN SELECT * FROM t1, t2, t3 WHERE t1.a = t2.a AND t1.b = t3.b;
+EXPLAIN SELECT * FROM t1, t3, t2 WHERE t1.a = t2.a AND t1.b = t3.b;
+
+EXPLAIN SELECT * FROM t2, t1, t3 WHERE t1.a = t2.a AND t1.b = t3.b;
+EXPLAIN SELECT * FROM t2, t3, t1 WHERE t1.a = t2.a AND t1.b = t3.b;
+
+EXPLAIN SELECT * FROM t3, t1, t2 WHERE t1.a = t2.a AND t1.b = t3.b;
+EXPLAIN SELECT * FROM t3, t2, t1 WHERE t1.a = t2.a AND t1.b = t3.b;
+
+DROP TABLE t1, t2, t3;
+
+--echo # Test that short-cuts show up in EXPLAIN properly with "Using index"
+CREATE TABLE t1 ( a INT );
+INSERT INTO t1 VALUES (1), (2), (3);
+
+CREATE TABLE t2 ( b INT KEY );
+INSERT INTO t2 VALUES (1), (2), (3);
+
+CREATE TABLE t3 ( c INT KEY );
+INSERT INTO t3 VALUES (1), (2), (3);
+
+EXPLAIN SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c;
+
+--echo # Test that we don't take a short-cut if we have successfully read a
+--echo # record already.
+EXPLAIN
+SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c WHERE c > 1;
+SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c WHERE c > 1;
+
+DROP TABLE t1, t2, t3;
+--echo #
+--echo # Test 1b.
+--echo # Tests that short-cuts work properly with join buffers.
+--echo #
+CREATE TABLE t1 ( a INT );
+INSERT INTO t1 VALUES (1), (2), (3);
+
+CREATE TABLE t2 ( b INT );
+INSERT INTO t2 VALUES (1), (2), (3);
+
+CREATE TABLE t2key ( b INT KEY );
+INSERT INTO t2key VALUES (1), (2), (3);
+
+CREATE TABLE t3 ( c INT, d INT );
+INSERT INTO t3 VALUES (1, -1), (2, 1), (3, 1);
+
+--echo # Should not use short-cuts.
+EXPLAIN
+SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c WHERE d > 0;
+SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c WHERE d > 0;
+
+--echo # Should not use short-cuts.
+EXPLAIN
+SELECT * FROM t1 JOIN t2key ON a = b JOIN t3 ON a = c WHERE d > 0;
+SELECT * FROM t1 JOIN t2key ON a = b JOIN t3 ON a = c WHERE d > 0;
+
+DROP TABLE t1, t2, t2key, t3;
+--echo # Test that we reject a short-cut properly. We have a cartesian product
+--echo # of a table and the result of an outer join. The optimizer places the
+--echo # table between the outer and inner table of the outer join and hence
+--echo # there is a short-cut from the inner table to the outer table. This
+--echo # short-cut should be rejected.
+CREATE TABLE t1 ( a INT PRIMARY KEY );
+INSERT INTO t1 VALUES (1),(2);
+
+CREATE TABLE t2 ( a INT );
+INSERT INTO t2 VALUES (1), (2), (3);
+
+CREATE TABLE t3 ( a INT );
+INSERT INTO t3 VALUES (1), (2), (3);
+
+--echo # Should not use short-cuts.
+EXPLAIN
+SELECT * FROM t2, t1 LEFT OUTER JOIN t3 ON (t3.a = t1.a);
+SELECT * FROM t2, t1 LEFT OUTER JOIN t3 ON (t3.a = t1.a);
+DROP TABLE t1, t2, t3;
+--echo # Test 2
+--echo # That the optimization actually works, i.e. that unneccesary reads are
+--echo # indeed short-cut.
+--echo #
+--echo # Test 2a: We have two tables between giving and receiving end of short-cut:
+--echo # t2 and t3.
+--echo #
+CREATE TABLE t1 ( a INT, b INT );
+INSERT INTO t1 VALUES (1, 2), (-1, -1);
+
+CREATE TABLE t2 ( a INT, b INT, KEY( a ) );
+INSERT INTO t2 VALUES (1, 2),(1, 2),(1, 2),(1, 2),(1, 2);
+INSERT INTO t2 SELECT * FROM t2;
+
+CREATE TABLE t3 ( b INT, KEY( b ) );
+INSERT INTO t3 VALUES (1), (1), (1), (1), (1);
+INSERT INTO t3 SELECT * FROM t3;
+
+CREATE TABLE t4 ( b INT, KEY( b ) );
+INSERT INTO t4 VALUES (1), (1), (1), (1), (1);
+INSERT INTO t4 SELECT * FROM t4;
+INSERT INTO t4 SELECT * FROM t4;
+INSERT INTO t4 SELECT * FROM t4;
+
+FLUSH STATUS;
+
+EXPLAIN
+SELECT * FROM t1 JOIN t2 USING(a) JOIN t3 ON t2.a = t3.b JOIN t4 ON t1.b = t4.b;
+SELECT * FROM t1 JOIN t2 USING(a) JOIN t3 ON t2.a = t3.b JOIN t4 ON t1.b = t4.b;
+
+SHOW STATUS LIKE 'handler_read_%';
+DROP TABLE t1, t2, t3, t4;
+--echo # Test 2b
+--echo # Short-cuts followed by successful keys. This tests that we perform the
+--echo # optimal number of reads after the short-cut is taken without missing tuples.
+CREATE TABLE t1 ( a INT );
+INSERT INTO t1 VALUES (1), (2), (3), (4), (5);
+
+CREATE TABLE t2 ( a INT, KEY (a) );
+INSERT INTO t2 VALUES (1), (2), (2), (2), (2), (2), (3), (4), (4), (4), (5);
+
+CREATE TABLE t3 ( a INT, KEY (a) );
+INSERT INTO t3 VALUES (1), (3), (5), (-1), (-1), (-1), (-1), (-1), (-1);
+
+FLUSH STATUS;
+
+EXPLAIN
+SELECT STRAIGHT_JOIN * FROM t1 JOIN t2 USING(a) JOIN t3 USING(a);
+SELECT STRAIGHT_JOIN * FROM t1 JOIN t2 USING(a) JOIN t3 USING(a);
+
+SHOW STATUS LIKE 'handler_read_%';
+
+DROP TABLE t1, t2, t3;
+--echo #
+--echo # Test 3.
+--echo # Test for outer joins. We may not take short-cuts across outer join
+--echo # boundaries. An outer join boundary goes before the first inner table for an
+--echo # outer join.
+--echo #
+--echo # Test 3a.
+--echo #
+CREATE TABLE t1 ( a INT, b INT );
+INSERT INTO t1 VALUES (1, 2), (-1, -1);
+
+CREATE TABLE t2 ( a INT, b INT, KEY( a ) );
+INSERT INTO t2 VALUES (1, 2),(1, 2),(1, 2),(1, 2),(1, 2);
+INSERT INTO t2 SELECT * FROM t2;
+
+CREATE TABLE t3 ( b INT, KEY( b ) );
+INSERT INTO t3 VALUES (1), (1), (1), (1), (1);
+INSERT INTO t3 SELECT * FROM t3;
+
+CREATE TABLE t4 ( b INT, KEY( b ) );
+INSERT INTO t4 VALUES (1), (1), (1), (1), (1);
+INSERT INTO t4 SELECT * FROM t4;
+INSERT INTO t4 SELECT * FROM t4;
+INSERT INTO t4 SELECT * FROM t4;
+
+CREATE TABLE t5 ( b INT, KEY( b ) );
+INSERT INTO t5 VALUES (1), (1), (1), (1), (1), (1), (1), (1);
+INSERT INTO t5 SELECT * FROM t5;
+
+--echo # Test of two outer join boundaries in one join.
+EXPLAIN
+SELECT *
+FROM t1 LEFT JOIN (t2 JOIN t3 ON t2.a = t3.b) USING ( a )
+ LEFT JOIN t4 ON t1.a = t4.b;
+
+EXPLAIN
+SELECT *
+FROM t1 LEFT JOIN (t2 JOIN t3 ON t2.a = t3.b) USING(a)
+ LEFT JOIN (t4 JOIN t5 USING( b )) ON t1.a = t4.b;
+
+DROP TABLE t1, t2, t3, t4, t5;
+--echo # Test 3b.
+--echo # Tests that we do not miss any data due to short-cutting.
+
+CREATE TABLE t1 ( a INT, b INT );
+CREATE TABLE t2 ( a INT, b INT, PRIMARY KEY (a,b) );
+CREATE TABLE t3 ( a INT, b INT, PRIMARY KEY (a,b) );
+
+INSERT INTO t1 VALUES ( 1, 1 ), ( 2, 1 ), ( 1, 3 );
+INSERT INTO t2 VALUES ( 1, 1 ), ( 2, 2 ), ( 3, 3 );
+INSERT INTO t3 VALUES ( 1, 1 ), ( 2, 1 ), ( 1, 3 );
+
+--echo # Test of the short-cut detection algorithm. When traversing the
+--echo # push-down conditions the algorithm will first find that the
+--echo # prospective short-cut t3->t1, but this must be invalidated due to the
+--echo # later found dependency t3->t2.
+EXPLAIN
+SELECT * FROM t1, t2, t3 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.b = t3.b;
+SELECT * FROM t1, t2, t3 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.b = t3.b;
+
+--echo # Test of internal representation of pushdown conditions.
+--echo # The join conditions will be encoded in ref access, while the WHERE
+--echo # expression remains in the pushdown condition.
+EXPLAIN
+SELECT *
+FROM t1 JOIN t2 ON t1.a = t2.a JOIN t3 ON t1.b = t3.a
+WHERE t3.b + 1 = t2.b;
+
+--echo # Short-cut is actually applicable in this case, thanks to equality
+--echo # propagation. The WHERE condition t3.a + 1 = t2.a is rewritten into
+--echo # t1.b + 1 = t1.a, and hence we have an optimizable star query.
+EXPLAIN
+SELECT *
+FROM t1 JOIN t2 ON t1.a = t2.a JOIN t3 ON t1.b = t3.a
+WHERE t3.a + 1 = t2.a;
+
+DROP TABLE t1, t2, t3;
+--echo # Test 3c
+CREATE TABLE t1 ( a INT );
+INSERT INTO t1 VALUES (1), (1), (1), (1);
+
+CREATE TABLE t2 ( a INT, KEY (a), b INT, c INT );
+INSERT INTO t2 VALUES (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1);
+INSERT INTO t2 SELECT * FROM t2;
+INSERT INTO t2 SELECT * FROM t2;
+
+CREATE TABLE t3 ( a INT, KEY (a) );
+INSERT INTO t3 VALUES (1), (1), (1), (1), (1), (1), (1), (1), (1), (1), (3);
+
+CREATE TABLE t4 ( a INT, KEY (a), b INT );
+INSERT INTO t4 VALUES (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1);
+INSERT INTO t4 SELECT * FROM t4;
+
+--echo #
+--echo # Test that the short-cut t4->t1 is rejected in favor of t4->t2.
+--echo #
+EXPLAIN
+SELECT STRAIGHT_JOIN *
+FROM t1 JOIN t2 ON t1.a = t2.a
+ JOIN t3 ON t2.b = t3.a
+ JOIN t4 ON t1.a = t4.a AND t2.c = t4.b;
+
+DROP TABLE t1, t2, t3, t4;
+--echo # Test 4. Test of execution step.
+--echo # In this test we are testing that a short-cut is properly separated from
+--echo # the case of a normal 'end of records' state on the last table in the plan.
+--echo # This particular case gets hit only when
+--echo # - The optimizer reorders the tables
+--echo # - We have a SELECT <table>.*
+CREATE TABLE t1( a INT );
+CREATE TABLE t2( a INT PRIMARY KEY );
+CREATE TABLE t3( a INT, INDEX( a ) );
+
+INSERT INTO t1( a ) VALUES ( 2 );
+INSERT INTO t1( a ) VALUES ( 2 );
+
+INSERT INTO t2( a ) VALUES ( 1 );
+INSERT INTO t2( a ) VALUES ( 2 );
+
+INSERT INTO t3( a ) VALUES ( 6 );
+INSERT INTO t3( a ) VALUES ( 5 );
+INSERT INTO t3( a ) VALUES ( 2 );
+
+EXPLAIN
+SELECT t2.* FROM t2, t1, t3 WHERE t2.a = t1.a AND t1.a = t3.a;
+SELECT t2.* FROM t2, t1, t3 WHERE t2.a = t1.a AND t1.a = t3.a;
+
+DROP TABLE t1, t2, t3;
+--echo #
+--echo # Test 5.
+--echo # Tests that a short-cut does not cross a plan node that is using join
+--echo # buffering.
+--echo #
+--echo # Test 5a.
+--echo #
+CREATE TABLE t1 ( a INT, c INT );
+INSERT INTO t1 VALUES (1, 2), (-1, -1);
+
+CREATE TABLE t2 ( a INT, b INT, KEY( a ), KEY( b ) );
+INSERT INTO t2 VALUES (1, 2),(1, 2),(1, 2),(1, 2),(1, 2);
+
+CREATE TABLE t3 ( a INT, KEY( a ) );
+INSERT INTO t3 VALUES (2), (2), (2), (2), (2);
+INSERT INTO t3 SELECT * FROM t3;
+INSERT INTO t3 SELECT * FROM t3;
+INSERT INTO t3 SELECT * FROM t3;
+
+CREATE TABLE t4 ( a INT, KEY( a ) );
+INSERT INTO t4 VALUES (1), (1), (1), (1), (1);
+INSERT INTO t4 SELECT * FROM t4;
+INSERT INTO t4 SELECT * FROM t4;
+INSERT INTO t4 SELECT * FROM t4;
+INSERT INTO t4 SELECT * FROM t4;
+
+FLUSH STATUS;
+
+--echo # Should not use short-cuts.
+EXPLAIN
+SELECT * FROM t1, t2, t3, t4 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.c = t4.a;
+SELECT * FROM t1, t2, t3, t4 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.c = t4.a;
+
+--echo # Should not use short-cuts.
+EXPLAIN
+SELECT * FROM t1, t2, t3, t4 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.c = t4.a;
+SELECT * FROM t1, t2, t3, t4 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.c = t4.a;
+
+SHOW STATUS LIKE 'handler_read_%';
+
+DROP TABLE t1, t2, t3, t4;
+--echo #
+--echo # Test 5b.
+--echo #
+CREATE TABLE t1 ( a INT, c INT );
+INSERT INTO t1 VALUES (1, 2), (-1, -1);
+
+CREATE TABLE t2 ( a INT, b INT, KEY( a, b ) );
+INSERT INTO t2 VALUES (1, 2),(1, 2),(1, 2),(1, 2),(1, 2);
+
+CREATE TABLE t3 ( a INT );
+INSERT INTO t3 VALUES (2), (2), (2), (2), (2);
+INSERT INTO t3 SELECT * FROM t3;
+
+CREATE TABLE t4 ( a INT );
+INSERT INTO t4 VALUES (1), (1), (1), (1), (1);
+INSERT INTO t4 SELECT * FROM t4;
+INSERT INTO t4 SELECT * FROM t4;
+
+FLUSH STATUS;
+
+--echo # Should not use short-cuts.
+EXPLAIN
+SELECT * FROM t1, t2, t3, t4 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.c = t4.a;
+SELECT * FROM t1, t2, t3, t4 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.c = t4.a;
+
+SHOW STATUS LIKE 'handler_read_%';
+
+DROP TABLE t1, t2, t3, t4;
+--echo #
+--echo # Test 6. Test of short-cuts in conjunction with outer join.
+--echo #
+--echo # Test 6a. Test of outer join detection.
+--echo # In this case the execution order is t1, t2, t3, t4.
+--echo # t2, t3 and t4 will form an 'outer join nest' with which t1 is left
+--echo # outer joined. But (t3, t2) is left joined with t4. Since t4 is just one
+--echo # table, however, the 'outer join nest' of t4 is only implicitly
+--echo # represented in the query plan. The only way to detect it is by looking
+--echo # at t4's first_inner pointer, which would be null for the last inner table
+--echo # in an outer join nest. But since it points to itseld, t4 is in its own
+--echo # nest. But there is no NESTED_JOIN to represent it, since it follows the
+--echo # 'normal' left-deep tree representation.
+--echo #
+CREATE TABLE t1 (a INT, b INT, c INT);
+CREATE TABLE t2 (d INT, e INT, f INT);
+CREATE TABLE t3 (g INT, h INT, i INT);
+CREATE TABLE t4 (j INT, k INT, l INT);
+
+INSERT INTO t1 VALUES (3,1,0), (2,2,0), (3,3,0);
+INSERT INTO t2 VALUES (1,1,0), (2,2,0);
+INSERT INTO t3 VALUES (3,2,0), (6,2,0), (6,1,0);
+INSERT INTO t4 VALUES (0,2,0), (1,2,0);
+
+EXPLAIN
+SELECT a, b, c, d, e, f, g, h, i, j, k, l
+FROM t1 LEFT JOIN ( (t3, t2) LEFT JOIN t4 ON t2.e = t4.k AND t3.h < 10 ) ON t1.b = t2.e;
+SELECT *
+FROM t1 LEFT JOIN ( (t3, t2) LEFT JOIN t4 ON t2.e = t4.k AND t3.h < 10 ) ON t1.b = t2.e;
+
+DROP TABLE t1, t2, t3, t4;
+--echo #
+--echo # Test 6b.
+--echo # We may take short-cuts across or inside an outer join, as long as we
+--echo # don't fail due to an outer join predicate. It goes as follows.
+--echo #
+--echo # - We may take a short-cut across a nested outer join.
+--echo # - We may take short-cuts inside a nested inner join sequence.
+--echo #
+CREATE TABLE t1 ( a INT );
+INSERT INTO t1 VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10);
+
+CREATE TABLE t2 ( b INT, KEY ( b ) );
+INSERT INTO t2 VALUES (1), (2), (4), (5), (6), (7), (8), (9), (10);
+
+CREATE TABLE t3 ( c INT, KEY( c ) );
+INSERT INTO t3 VALUES (1), (2), (3), (4), (6), (7), (8), (9), (10);
+
+CREATE TABLE t4 ( d INT, KEY( d ) );
+INSERT INTO t4 VALUES (1), (2), (3), (4), (5), (6), (7), (8), (10);
+INSERT INTO t4 VALUES (10), (10), (10), (10);
+
+CREATE TABLE t5 ( e INT, KEY( e ) );
+INSERT INTO t5 VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10);
+
+--echo # Outer join followed by a table that is inner joined with the first.
+EXPLAIN
+SELECT * FROM t1 LEFT JOIN t2 ON a = b JOIN t3 ON a = c;
+SELECT * FROM t1 LEFT JOIN t2 ON a = b JOIN t3 ON a = c;
+
+--echo # Short-cut across a nested outer join
+EXPLAIN
+SELECT * FROM t1 JOIN (t2 LEFT JOIN t3 ON b = c) ON a = b JOIN t4 ON a = d;
+SELECT * FROM t1 JOIN (t2 LEFT JOIN t3 ON b = c) ON a = b JOIN t4 ON a = d;
+
+--echo # Short-cut across a nested outer join with a nested inner join
+EXPLAIN
+SELECT * FROM t1
+ JOIN (t2 LEFT JOIN (t3 JOIN t4 ON c = d) ON b = d) ON a = b
+ JOIN t5 ON a = e;
+SELECT * FROM t1
+ JOIN (t2 LEFT JOIN (t3 JOIN t4 ON c = d) ON b = d) ON a = b
+ JOIN t5 ON a = e;
+
+--echo # Short-cut from last inner table inside an inner join that is nested
+--echo # within an outer join
+EXPLAIN
+SELECT * FROM t1 LEFT JOIN (t2 JOIN t3 ON b = c JOIN t4 ON b = d) on a = b;
+SELECT * FROM t1 LEFT JOIN (t2 JOIN t3 ON b = c JOIN t4 ON b = d) on a = b;
+
+--echo # Short-cut from not last inner table inside an inner join that is nested
+--echo # within an outer join
+EXPLAIN
+SELECT * FROM t1
+ LEFT JOIN
+ (t2 JOIN t3 ON b = c JOIN t4 ON b = d JOIN t5 ON d = e)
+ ON a = b;
+SELECT * FROM t1
+ LEFT JOIN
+ (t2 JOIN t3 ON b = c JOIN t4 ON b = d JOIN t5 ON d = e)
+ ON a = b;
+
+--echo # Illegal scenario for short-cut. Should not be taken.
+EXPLAIN
+SELECT * FROM t1 JOIN t2 ON a = b LEFT JOIN t3 ON a = c;
+SELECT * FROM t1 JOIN t2 ON a = b LEFT JOIN t3 ON a = c;
+
+EXPLAIN
+SELECT * FROM t1 JOIN t2 ON a = b LEFT JOIN (t3 JOIN t4 ON c = d) ON a = c;
+SELECT * FROM t1 JOIN t2 ON a = b LEFT JOIN (t3 JOIN t4 ON c = d) ON a = c;
+
+DROP TABLE t1, t2, t3, t4, t5;
+--echo #
+--echo # Test 6c.
+--echo # Tests that short-cuts work even if a record was read and then rejected.
+--echo # This happens for table scan without join buffering.
+--echo #
+let $requires_join_cache_level = 0;
+--source include/have_join_cache_level.inc
+--eval set optimizer_join_cache_level = $requires_join_cache_level;
+CREATE TABLE t1 ( a INT );
+INSERT INTO t1 VALUES (1), (2), (3);
+
+CREATE TABLE t2 ( b INT );
+INSERT INTO t2 VALUES (1), (2), (2), (2), (2), (3);
+
+CREATE TABLE t3 ( c INT, d INT );
+INSERT INTO t3(c) VALUES (1), (3), (4), (4), (4), (4);
+
+FLUSH STATUS;
+
+EXPLAIN
+SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c;
+SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c;
+
+SHOW STATUS LIKE 'handler_read%';
+FLUSH STATUS;
+
+EXPLAIN
+SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c WHERE d > 0;
+SELECT * FROM t1 JOIN t2 ON a = b JOIN t3 ON a = c WHERE d > 0;
+
+SHOW STATUS LIKE 'handler_read%';
+
+set @@optimizer_join_cache_level = DEFAULT;
+
+DROP TABLE t1, t2, t3;
=== modified file 'mysql-test/t/subselect_innodb.test'
--- a/mysql-test/t/subselect_innodb.test 2010-08-14 07:28:31 +0000
+++ b/mysql-test/t/subselect_innodb.test 2010-10-06 15:22:47 +0000
@@ -302,7 +302,7 @@ ALTER TABLE t3 ADD FOREIGN KEY FK_FLDRS
SELECT t2.*, t4.DOCTYPENAME, t1.CONTENTSIZE,t1.MIMETYPE FROM t2 INNER JOIN t4 ON t2.DOCTYPEID = t4.DOCTYPEID LEFT OUTER JOIN t1 ON t2.DOCID = t1.DOCID WHERE t2.FOLDERID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID='2f6161e879db43c1a5b82c21ddc49089' AND t3.FOLDERNAME = 'Level1') AND t3.FOLDERNAME = 'Level2') AND t3.FOLDERNAME = 'Level3') AND t3.FOLDERNAME = 'CopiedFolder') AND t3.FOLDERNAME = 'Movie Reviews') AND t2.DOCNAME = 'Last Discussion';
EXPLAIN EXTENDED SELECT t2.*, t4.DOCTYPENAME, t1.CONTENTSIZE,t1.MIMETYPE FROM t2 INNER JOIN t4 ON t2.DOCTYPEID = t4.DOCTYPEID LEFT OUTER JOIN t1 ON t2.DOCID = t1.DOCID WHERE t2.FOLDERID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID='2f6161e879db43c1a5b82c21ddc49089' AND t3.FOLDERNAME = 'Level1') AND t3.FOLDERNAME = 'Level2') AND t3.FOLDERNAME = 'Level3') AND t3.FOLDERNAME = 'CopiedFolder') AND t3.FOLDERNAME = 'Movie Reviews') AND t2.DOCNAME = 'Last Discussion';
-
+SELECT t2.*, t4.DOCTYPENAME, t1.CONTENTSIZE,t1.MIMETYPE FROM t2 INNER JOIN t4 ON t2.DOCTYPEID = t4.DOCTYPEID LEFT OUTER JOIN t1 ON t2.DOCID = t1.DOCID WHERE t2.FOLDERID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID IN(SELECT t3.FOLDERID FROM t3 WHERE t3.PARENTID='2f6161e879db43c1a5b82c21ddc49089' AND t3.FOLDERNAME = 'Level1') AND t3.FOLDERNAME = 'Level2') AND t3.FOLDERNAME = 'Level3') AND t3.FOLDERNAME = 'CopiedFolder') AND t3.FOLDERNAME = 'Movie Reviews') AND t2.DOCNAME = 'Last Discussion';
drop table t1, t2, t3, t4;
# End of 4.1 tests
=== modified file 'sql/item.cc'
--- a/sql/item.cc 2010-09-28 15:17:29 +0000
+++ b/sql/item.cc 2010-10-06 15:22:47 +0000
@@ -2306,6 +2306,9 @@ bool Item_field::eq(const Item *item, bo
}
+/**
+ This set contains simply the table to which the field belongs.
+*/
table_map Item_field::used_tables() const
{
if (field->table->const_table)
=== modified file 'sql/item.h'
--- a/sql/item.h 2010-09-07 19:07:18 +0000
+++ b/sql/item.h 2010-10-06 15:22:47 +0000
@@ -860,7 +860,13 @@ public:
virtual bool val_bool_result() { return val_bool(); }
virtual bool is_null_result() { return is_null(); }
- /* bit map of tables used by item */
+ /**
+ This is the set of tables directly referenced by this Item.
+
+ For pushdown conditions, used_tables is the set tables referenced by the
+ pushdown condition recursively, *including* the table to which the
+ condition is pushed.
+ */
virtual table_map used_tables() const { return (table_map) 0L; }
/*
Return table map of tables that can't be NULL tables (tables that are
=== modified file 'sql/records.h'
--- a/sql/records.h 2010-07-13 17:29:44 +0000
+++ b/sql/records.h 2010-10-06 15:22:47 +0000
@@ -38,6 +38,34 @@ class SQL_SELECT;
...
}
end_read_record();
+
+ READ_RECORD is an interface that is used to retrieve records one by one.
+
+ - An abstraction layer between the query execution engine and the storage
+ engine API. The only read operation the execution engine has to know of
+ is reading the next record. Beneath the abstraction layer is the storage
+ engine API, which is invoked differently for table/index scans and key
+ lookups, and the join buffer.
+
+ - An executable sub-program, resulting from the optimizer. It is set up with a
+ reference to a handler and a function pointer to a read function during
+ query optimization.
+
+ The abstraction is incomplete, however. For instace, reading the first
+ record from a handler is done through a function pointer in the JOIN_TAB
+ rather than in its READ_RECORD.
+
+ Sometimes the READ_RECORD is initialized during query execution.
+
+ - It is reinitialized during buffered nested loops join, before the buffer
+ is flushed.
+
+ - For many table accesses, it is initialized right before the first record
+ is read.
+
+ The READ_RECORD design can be viewed as a strategy pattern, where the
+ abstract strategy is the READ_RECORD struct and the concrete strategy is
+ determined by the values of the function pointer READ_RECORD::read_record.
*/
class Copy_field;
=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc 2010-09-30 14:53:11 +0000
+++ b/sql/sql_select.cc 2010-10-06 15:22:47 +0000
@@ -28,6 +28,9 @@
#pragma implementation // gcc: Class implementation
#endif
+#include "sql_set.h"
+#include "sql_shortcut.h"
+
#include "sql_priv.h"
#include "unireg.h"
#include "sql_select.h"
@@ -2468,6 +2471,9 @@ JOIN::optimize()
}
tmp_having= having;
+
+ setup_shortcuts(this);
+
if (select_options & SELECT_DESCRIBE)
{
error= 0;
@@ -16982,6 +16988,7 @@ sub_select_cache(JOIN *join, JOIN_TAB *j
DBUG_ASSERT(cache != NULL);
cache->reset_join(join);
+ join->return_tab= join_tab;
DBUG_ENTER("sub_select_cache");
@@ -17156,6 +17163,7 @@ sub_select(JOIN *join,JOIN_TAB *join_tab
join_tab->table->null_row=0;
if (end_of_records)
{
+ join->return_tab= join_tab;
enum_nested_loop_state nls=
(*join_tab->next_select)(join,join_tab+1,end_of_records);
DBUG_RETURN(nls);
@@ -17184,12 +17192,16 @@ sub_select(JOIN *join,JOIN_TAB *join_tab
}
join->thd->warning_info->reset_current_row_for_warning();
+ join_tab->current_prefix_successful= FALSE;
error= (*join_tab->read_first_record)(join_tab);
if (join_tab->keep_current_rowid)
join_tab->table->file->position(join_tab->table->record[0]);
-
+
rc= evaluate_join_record(join, join_tab, error);
+
+ if (shortcut_applies(join_tab, rc))
+ join->return_tab= join_tab->shortcut;
/*
Note: psergey has added the 2nd part of the following condition; the
@@ -17201,8 +17213,12 @@ sub_select(JOIN *join,JOIN_TAB *join_tab
if (join_tab->keep_current_rowid)
join_tab->table->file->position(join_tab->table->record[0]);
-
+
rc= evaluate_join_record(join, join_tab, error);
+
+ if (shortcut_applies(join_tab, rc))
+ join->return_tab= join_tab->shortcut;
+
}
if (rc == NESTED_LOOP_NO_MORE_ROWS &&
@@ -17376,6 +17392,8 @@ evaluate_join_record(JOIN *join, JOIN_TA
if (join->thd->is_error())
DBUG_RETURN(NESTED_LOOP_ERROR);
}
+ join_tab->current_prefix_successful= found;
+
if (found)
{
/*
@@ -22797,6 +22815,13 @@ void select_describe(JOIN *join, bool ne
extra.append(STRING_WITH_LEN(", incremental buffers)"));
}
+ if (tab->shortcut != NULL)
+ {
+ extra.append(STRING_WITH_LEN("; StarJoin("));
+ extra.append(tab->shortcut->table->alias);
+ extra.append(STRING_WITH_LEN(")"));
+ }
+
/* Skip initial "; "*/
const char *str= extra.ptr();
uint32 len= extra.length();
=== modified file 'sql/sql_select.h'
--- a/sql/sql_select.h 2010-09-23 12:16:36 +0000
+++ b/sql/sql_select.h 2010-10-06 15:22:47 +0000
@@ -210,6 +210,17 @@ typedef struct st_join_table : public Sq
TABLE *table;
KEYUSE *keyuse; /**< pointer to first used key */
SQL_SELECT *select;
+ /**
+ This field corresponds to a pushdown condition. It may contain more than
+ just those conditions pushed to the actual table, however.
+
+ @note Not all pushdown conditions are found in this field. @c ref access
+ conditions are removed from here and are encoded in JOIN_TAB::ref.
+
+ @note The @c used_tables set for pushdown conditions is the set of tables
+ referenced by the pushdown condition recursively, including the table to
+ which the condition is pushed.
+ */
Item *select_cond;
QUICK_SELECT_I *quick;
Item **on_expr_ref; /**< pointer to the associated on expression */
@@ -351,6 +362,15 @@ typedef struct st_join_table : public Sq
/* NestedOuterJoins: Bitmap of nested joins this table is part of */
nested_join_map embedding_map;
+ /**
+ This flag is set true once a partial row has been produced for the
+ current table that corresponds to the partial row produced for all
+ previous tables in the current join.
+ */
+ bool current_prefix_successful;
+
+ st_join_table *shortcut;
+
void cleanup();
inline bool is_using_loose_index_scan()
{
@@ -479,7 +499,8 @@ st_join_table::st_join_table()
found_match(FALSE),
keep_current_rowid(0),
- embedding_map(0)
+ embedding_map(0),
+ shortcut(NULL)
{
/**
@todo Add constructor to READ_RECORD.
@@ -1779,12 +1800,13 @@ public:
TABLE_LIST *tables_list; ///<hold 'tables' parameter of mysql_select
List<TABLE_LIST> *join_list; ///< list of joined tables in reverse order
COND_EQUAL *cond_equal;
- /*
+ /**
+ Interface for taking short-cuts through join execution.
Join tab to return to. Points to an element of join->join_tab array, or to
join->join_tab[-1].
This is used at execution stage to shortcut join enumeration. Currently
shortcutting is done to handle outer joins or handle semi-joins with
- FirstMatch strategy.
+ FirstMatch strategy. It is also used to optimize execution of star joins.
*/
JOIN_TAB *return_tab;
Item **ref_pointer_array; ///<used pointer reference for this select
@@ -1952,6 +1974,37 @@ public:
((group || tmp_table_param.sum_func_count) && !group_list)) ?
NULL : join_tab+const_tables;
}
+
+
+ /**
+ Returns true if JOIN_TAB's a and b participate on the same nesting level
+ within a chain of inner joined tables.
+
+ @note The optimizer execution plan is considered, and outer joins may
+ have been rewritten into inner joins.
+ */
+ static bool are_inner_joined(JOIN_TAB *a, JOIN_TAB *b)
+ {
+ DBUG_ASSERT(a < b);
+ return
+ a->table->pos_in_table_list->embedding ==
+ b->table->pos_in_table_list->embedding &&
+ (b->on_expr_ref == NULL || *b->on_expr_ref == NULL);
+ }
+
+
+ /**
+ True if this query execution plan uses join buffering between plan nodes
+ a and b.
+ */
+ static bool contains_join_buffering(JOIN_TAB *a, JOIN_TAB *b)
+ {
+ for (JOIN_TAB *join_tab= a; join_tab <= b; join_tab++)
+ if (join_tab->use_join_cache)
+ return TRUE;
+ return FALSE;
+ }
+
private:
/**
TRUE if the query contains an aggregate function but has no GROUP
=== added file 'sql/sql_set.h'
--- a/sql/sql_set.h 1970-01-01 00:00:00 +0000
+++ b/sql/sql_set.h 2010-10-06 15:22:47 +0000
@@ -0,0 +1,111 @@
+#ifndef INCLUDES_MYSQL_SQL_SET_H
+#define INCLUDES_MYSQL_SQL_SET_H
+/* Copyright (c) 2000, 2010 Oracle and/or its affiliates. All rights reserved.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; version 2 of the License.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
+
+#include "my_global.h"
+
+template <class T> class Bitmap_set_iterator;
+template <class T> class Bitmap_set_reverse_iterator;
+
+/**
+ A set implemented as a bitmap. Due to this implementation, operations that
+ normally are quite expensive, typically having O(n log n) complexity, are
+ extremely cheap. A set consists of a bitmap and an array of pointers to
+ elements, the backing store. Each n:th bit in the bitmap represents the
+ member at position n in the array, where the first member has position 0. A
+ set consisting of this element is represented by the bitmap 1.
+
+ For obvious reasons, it cannot be allowed to perform a union operation on
+ two sets that have different backing stores, even if their type is the
+ same. Attempts at such operations will result in failed assertions.
+ */
+template <class T> class Bitmap_set {
+
+private:
+ ulonglong m_map;
+ T** m_backing_store;
+
+public:
+ Bitmap_set(ulonglong map, T** backing_store) :
+ m_map(map), m_backing_store(backing_store) {}
+
+ bool is_empty() { return m_map == 0; }
+
+ Bitmap_set<T> set_union(const Bitmap_set<T>& other) const
+ {
+ DBUG_ASSERT(m_backing_store == other.m_backing_store);
+ return Bitmap_set<T>(m_map | other.m_map, m_backing_store);
+ }
+
+ friend class Bitmap_set_iterator<T>;
+ friend class Bitmap_set_reverse_iterator<T>;
+};
+
+template <class T> class Bitmap_set_iterator {
+private:
+ const Bitmap_set<T>& m_set;
+ uint m_current_element;
+
+public:
+ Bitmap_set_iterator(const Bitmap_set<T>& set) :
+ m_set(set), m_current_element(0) {}
+
+ inline T* operator++(int) {
+ ulonglong mask= 1 << m_current_element;
+ while ((mask & m_set.m_map) == 0)
+ {
+ if (mask == 0 || mask > m_set.m_map)
+ return NULL;
+ mask<<= 1;
+ ++m_current_element;
+ }
+ T* element= m_set.m_backing_store[m_current_element++];
+ return element;
+ }
+
+};
+
+template <class T> class Bitmap_set_reverse_iterator {
+private:
+ const Bitmap_set<T>& m_set;
+ int m_current_element;
+
+public:
+ Bitmap_set_reverse_iterator(const Bitmap_set<T>& set) :
+ m_set(set), m_current_element(0)
+ {
+ ulonglong map= set.m_map;
+ while ((map>>= 1) != 0)
+ ++m_current_element;
+ }
+
+ inline T* operator++(int) {
+ if (m_current_element == -1)
+ return NULL;
+ ulonglong mask= 1 << m_current_element;
+ while ((mask & m_set.m_map) == 0)
+ {
+ if (mask == 0)
+ return NULL;
+ mask>>= 1;
+ --m_current_element;
+ }
+ T* element= m_set.m_backing_store[m_current_element--];
+ return element;
+ }
+
+};
+#endif // INCLUDES_MYSQL_SQL_SET_H
=== added file 'sql/sql_shortcut.h'
--- a/sql/sql_shortcut.h 1970-01-01 00:00:00 +0000
+++ b/sql/sql_shortcut.h 2010-10-06 15:22:47 +0000
@@ -0,0 +1,153 @@
+#ifndef INCLUDES_MYSQL_SQL_SHORTCUT_H
+#define INCLUDES_MYSQL_SQL_SHORTCUT_H
+
+/* Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; version 2 of the License.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
+
+#include "sql_select.h"
+#include "sql_set.h"
+
+
+/**
+ Updates a short-cut from from one plan node to another. The function
+ assumes that it is invoked on plan nodes in reverse order in which they
+ appear in the query execution plan.
+
+ @param join The execution plan.
+
+ @param join_tab The plan node from which a short-cut may potentially be
+ taken.
+
+ @param dependent A plan node that access to join_tab depends on.
+
+ @retval TRUE There may be other short-cuts possible early in the plan.
+ @retval FALSE There are no earlier short-cuts available. Either the only
+ possible one was found and completely initialized, or there are none.
+*/
+static bool update_star_dependency(JOIN *join, JOIN_TAB *join_tab,
+ JOIN_TAB *dependency)
+{
+ if (dependency == NULL)
+ return FALSE;
+
+ if (join_tab <= dependency)
+ return TRUE;
+
+ if (dependency == join_tab - 1)
+ {
+ DBUG_PRINT("info", ("Invalidated a join short-cut from %s to %s",
+ join_tab->table->alias,
+ dependency->table->alias));
+ return FALSE;
+ }
+ else if (join->are_inner_joined(dependency, join_tab) &&
+ !join->contains_join_buffering(dependency, join_tab))
+ {
+ DBUG_PRINT("info", ("Found a join short-cut from %s to %s",
+ join_tab->table->alias,
+ dependency->table->alias));
+
+ join_tab->shortcut= dependency;
+
+ return FALSE;
+ }
+ return TRUE;
+}
+
+
+/**
+ Sets the short-cut from from one plan node to another, if one is found.
+
+ @param join The execution plan.
+
+ @param join_tab The plan node from which a short-cut willpotentially be
+ taken.
+*/
+static void set_star_dependency(JOIN *join, JOIN_TAB *join_tab)
+{
+ table_map where_clause_tables_map;
+ if (join_tab->select_cond != NULL)
+ {
+ Item *where_condition= join_tab->select_cond;
+ where_condition->update_used_tables();
+ where_clause_tables_map=
+ where_condition->used_tables() & ~PSEUDO_TABLE_BITS;
+ }
+ else
+ where_clause_tables_map= (table_map)0L;
+
+ table_map ref_access_tables_map=
+ join_tab->ref.depend_map & ~PSEUDO_TABLE_BITS;
+
+ Bitmap_set<JOIN_TAB>
+ where_clause_tables(where_clause_tables_map, join->map2table);
+
+ Bitmap_set<JOIN_TAB>
+ ref_access_tables(ref_access_tables_map, join->map2table);
+
+ Bitmap_set<JOIN_TAB> tables_depended_upon=
+ where_clause_tables.set_union(ref_access_tables);
+
+ if (tables_depended_upon.is_empty())
+ return;
+
+ for(Bitmap_set_reverse_iterator<JOIN_TAB> it(tables_depended_upon);
+ update_star_dependency(join, join_tab, it++);) ;
+}
+
+
+/**
+ Pre-compute short-cuts for the join short-cut optimization.
+
+ This function adorns the query exeution plan with star join short-cuts
+ where applicable. Short-cuts are triggered by the executioner. The
+ algorithm is implemented as a nested loop, where the outer loop walks the
+ nodes (JOIN_TAB's) in the query execution plan, and the inner loop iterates
+ through all tables that this table depends upon. Valid short-cuts have the
+ following property.
+
+ - The short-cut has a minimum length of 2. If a table is dependent on the
+ table directly preceding it, the short-cut would be of length 1, and it
+ would indicate that there are no valid short-cuts from this table.
+
+ - The short-cut does not cross an outer join boundary. In this case the
+ optimization is not applicable, because a valid result would be missed.
+
+ - The short-cut does not cross a node using join buffers. Short-cuts are
+ not compatible with join buffering.
+
+ - If there are several applicable shortcuts by the above requirements, the
+ shortest one is chosen.
+
+ @param join The query execution plan. The plan is assumed to be complete
+ and ready for execution when this method is invoked.
+*/
+static void setup_shortcuts(JOIN *join)
+{
+ if(join->join_tab == NULL)
+ return;
+
+ for (uint i= 2; i < join->tables; i++)
+ set_star_dependency(join, &join->join_tab[i]);
+}
+
+bool shortcut_applies(const JOIN_TAB *join_tab, enum_nested_loop_state rc)
+{
+ return rc != NESTED_LOOP_OK &&
+ !join_tab->current_prefix_successful &&
+ join_tab->shortcut != NULL;
+}
+
+#endif // INCLUDES_MYSQL_SQL_SHORTCUT_H
=== modified file 'sql/structs.h'
--- a/sql/structs.h 2010-07-13 17:29:44 +0000
+++ b/sql/structs.h 2010-10-06 15:22:47 +0000
@@ -119,6 +119,27 @@ struct st_join_table;
typedef struct st_reginfo { /* Extra info about reg */
struct st_join_table *join_tab; /* Used by SELECT() */
enum thr_lock_type lock_type; /* How database is used */
+ /**
+ This is an outer join optimization. The idea is to avoid
+ NULL-complementing a row for the inner table(s). The bespoke case is when
+ we have a query such as
+
+ @code
+
+ SELECT ...
+ FROM t1 LEFT OUTER JOIN (t2, t3) ON <condition>
+ WHERE t2.non_nullable_column IS NULL
+
+ @endcode
+
+ In this case not_exists_optimize would be set for t2.
+
+ Once the query execution reaches the place where <condition> holds for
+ the current result tuple, we know that there cannot be a row where the
+ WHERE condition holds. There is no need produce a NULL-complemented row.
+
+ @see update_ref_and_keys
+ */
bool not_exists_optimize;
/*
TRUE <=> range optimizer found that there is no rows satisfying
Attachment: [text/bzr-bundle] bzr/martin.hansson@oracle.com-20101006152247-iv4ap5giawtj6fs2.bundle
| Thread |
|---|
| • bzr commit into mysql-next-mr-opt-team branch (martin.hansson:3225) WL#3724 | Martin Hansson | 6 Oct |
