From: Martin Hansson Date: October 6 2010 3:22pm Subject: bzr commit into mysql-next-mr-opt-team branch (martin.hansson:3225) WL#3724 List-Archive: http://lists.mysql.com/commits/120146 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============0254781392==" --===============0254781392== MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Content-Disposition: inline #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 .* +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 (`test`.`t2`.`FOLDERID`,(((`test`.`t2`.`FOLDERID`) in t3 on PRIMARY where ((`test`.`t3`.`FOLDERNAME` = 'Movie Reviews') and (`test`.`t3`.`PARENTID`,(((`test`.`t3`.`PARENTID`) in t3 on PRIMARY where ((`test`.`t3`.`FOLDERNAME` = 'CopiedFolder') and (`test`.`t3`.`PARENTID`,(((`test`.`t3`.`PARENTID`) in t3 on PRIMARY where ((`test`.`t3`.`FOLDERNAME` = 'Level3') and (`test`.`t3`.`PARENTID`,(((`test`.`t3`.`PARENTID`) in t3 on PRIMARY where ((`test`.`t3`.`FOLDERNAME` = 'Level2') and (`test`.`t3`.`PARENTID`,(((`test`.`t3`.`PARENTID`) in t3 on PRIMARY where ((`test`.`t3`.`FOLDERNAME` = 'Level1') and (`test`.`t3`.`PARENTID` = '2f6161e879db43c1a5b82c21ddc49089') and ((`test`.`t3`.`PARENTID`) = `test`.`t3`.`FOLDERID`))))) and ((`test`.`t3`.`PARENTID`) = `test`.`t3`.`FOLDERID`))))) and ((`test`.`t3`.`PARENTID`) = `test`.`t3`.`FOLDERID`))))) and ((`test`.`t3`.`PARENTID`) = `test`.`t3`.`FOLDERID`))))) and ((`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
.* +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; /// *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; ///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 Bitmap_set_iterator; +template 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 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 set_union(const Bitmap_set& other) const + { + DBUG_ASSERT(m_backing_store == other.m_backing_store); + return Bitmap_set(m_map | other.m_map, m_backing_store); + } + + friend class Bitmap_set_iterator; + friend class Bitmap_set_reverse_iterator; +}; + +template class Bitmap_set_iterator { +private: + const Bitmap_set& m_set; + uint m_current_element; + +public: + Bitmap_set_iterator(const Bitmap_set& 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 Bitmap_set_reverse_iterator { +private: + const Bitmap_set& m_set; + int m_current_element; + +public: + Bitmap_set_reverse_iterator(const Bitmap_set& 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 + where_clause_tables(where_clause_tables_map, join->map2table); + + Bitmap_set + ref_access_tables(ref_access_tables_map, join->map2table); + + Bitmap_set tables_depended_upon= + where_clause_tables.set_union(ref_access_tables); + + if (tables_depended_upon.is_empty()) + return; + + for(Bitmap_set_reverse_iterator 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 + 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 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 --===============0254781392== MIME-Version: 1.0 Content-Type: text/bzr-bundle; charset="us-ascii"; name="bzr/martin.hansson@stripped" Content-Transfer-Encoding: 7bit Content-Disposition: inline # Bazaar merge directive format 2 (Bazaar 0.90) # revision_id: martin.hansson@stripped\ # iv4ap5giawtj6fs2 # target_branch: file:///data0/martin/bzrroot/wl3724/n-mr-o-t-Roy/ # testament_sha1: 85224496f975af6dfc25d554414fd5b30ddd6c3d # timestamp: 2010-10-06 17:22:52 +0200 # base_revision_id: tor.didriksen@stripped\ # 7qwh7ilpy1uh1ziq # # Begin bundle IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWbAVkKcAO75/gHewBAD///// f///+r////9gSb3quzuaTtq4Bqry9cvTd7b3nez5tvbe9747yn0p7Zm+73u+PXbV09AvY7svr4A6 gWODBt671rd3B7Z9dffTvh7vuox3u+T73vgZ1pC7t7w6+nqQT6yQbsaBW+B6+FaEBaxRKS1lWzZd Hz2EPb7u9l7GmbOpvcHruATnOTL2l9zHffePR6lbCbKtbTeyuK7773rXgXbGtahKApmUWF5Htw9e lm56w89mhrNqEdvdh7s8JTRECZNBoFT9DKbTRNNKe1TZk1TR6j1Nponqekeo9T1AGhoAShMgEBEA nqnoSeCp5ENPUDTIDQAAaAAAJI0gpMIp+ganpRoPUaaeiABpoAGgAAAAASaSQk0mCniGlPCo/TVH 5Uw0aTENBtRowgaDQAAAiUICBMQ1MaUzSYCaeqb0p6A0mUaaGxTwU020pkyaPSAqSIIATIaExDQm mQYgCAganqaaGyT1AeSBpp0yHuZIQPcHuPaIVnuYZGsRFFP7tZKj/Mf7EQ/qP3j7PK4uLmwKRXKF PXZtY+/Gs+4UD9HQBTNHaIm2a1sDstJtsc+W6QS9JmKsGKOu77PwOS8NRk6c6MoSg55SSUaCysiw M83CcEigzzUpFRMhKLiZqzZoiGlM5/2w6C5U0RUJAlB2o9mTYRGMGRb6gprgXLlhMO0MAopiOwyk lQqj/ahLValipNtUrat5lrHkFqEWp8CJ3C7CL6gtKXMzNmQBhnHCIcZ3Q444jR6vcjSfIeSlzvpC Br5sWmoTpQkWc30oLDdAJUOrvsJDxGEJshrffDNS6dPqTZJieWmydylpf9ZzNYoO1wgg4H2buSoK JftxqGv76N+3xDCKkneJFe24j8whCgaSp3IqDsyaeiGrwMvoOCGjntgsEFXY5HFH1DzGriA7wGtI dDCkjY01VKpcqShBZctGq1R4Y8Usn5YIZlSzp07erYVEsPEQlwp0pO+Pzf3+w1L3G/w9QQNgQP8e IyCA5RNDdkhU7JQvdlkTICzGSwo08AgPIIGQIcQB64ohStCsRTQCGOIkRYSESSJ5eOBkJb0phHYI HM7v/Z9NPqMHGl+/r+hyki/AatGJMqfSfDVE+uYNKExoChfj4tvYZcxO7LOKPbf+VxCEkWtekRD4 yICJp3Tpsz0QDooQxQCTKj7se134KMXT/vqin737asIwhDmn/mdjlWwwYdgTDO4/r8/o11Nb7HnW I30+LHBRXa78dttl2Lxw34Pt745LrFUnQm+vGRQK9BVQO2BkPBNS7+VaUmK56HSy7/8RLmlunpx3 rLR75QVXxQyVxog7UENsOcRBRWrdRS2kQwlhowDaQSkDiJBpz1GiRIRrQ6/Ugc10qatb5reW3PvW mPfQyMhGHuIXjmc5Sa0U1PDkWFtE5lRTFNWwZ8aGvyLtTQk3F60xDJJtPjxxr7Sb0Pv+3O9Pc8HT a22WUOXy1OW+3ZrecCCtR58Y8bYeBr1mpmf5lwVvnLdebM52OqT1GYLgvVLOhS+fOGGorOzu469c kSedJhy5VtssobSGdShpCBUowrHjCHgaxYUzMJYK3tt0YwwWSw6A8/I85LIAv4/SzcPLbWQ0JCoU SvoLSnDjrilFUWGlA5Sq1rQ6VQAxibGhSKDG4DzumQPPZIMziqRrGLXBm/k4JrEDwK1F7uwj97Sm P35PjJ1k5E5ffW22W3xzp51xaJ7ww/FZ00r4nAp6Hl5iqMZVwkCn2jwqqqoirFVVgqqqqsRFVVgk kkhCTJJGR7dTmXDC/LNq0yjPmJk2mrxWbghoUnStgeHC8iEoCYIYiEkijyG8iuarWtKxPFneTv9K pT1k6ybs7GQ8O6hOfOLIhISChIqkig8xl09Z6CxsC/V/ExBMW6zvzWaa6aJgla1xrXnrWVrW7Y1r XZsZcbM1uyuzLrHj0cjy9tDt6+t5krBMMdgr3pGYY4phjmwVgnuz6AklMfIm5d1FfCtpxWkKwLOh V3tWVmvOjErRS9VRYlKypZb3o4gxcb4JtM7AQYz17eQQGiKrqBrHOEIk40mBhB8/U3QPzu+unkNj Vg1aYKrWFm7ujcdfFy5+2PdqXwguMYoYuxhsSxf7VVQ+AFNAQUNUQEQ2IRUEgMSJtnxkAR3DFBbE YDJ9ywKRgjHvLUns+tZgkYiKIhEYkRFYokREk8vr+Hc/hO+HgQJM8voIPoPvs/h5uWMKwaR5AbaX HMbtPW7vyh9IGIEAgID7CwK5cOwMYwZJJIxMBwRISLpEwNB9goFKdAdB0xJDmCCJEQVUIgooSRJA REIIIQRAQilKQopESigj80fZreSTubH5NrHavDZCfEzWS/VWv5p8lSkoo9KyxT0pNow8sHsIYlBs EcIyqH0EEv0go2lrOgmhA1jsUMDSKUDXBo2NAbYtKC63xZ4GApRoLHQoiUUCe57U9v6R/edWDQN3 mzNwRyewjB6MgdVl6DtEOgXvDFQUFJBYsFFUiigoLILVZx5OOfwmFQp/UQz5+O1HnYeGb/EfwtkQ yGQwg83lrLO3wxcLvF00/EKKTLOhRKUQ1JUKJjuhuVmO5GanMVwTmDGgkZBaFWMst40xVmXcl80r MZJJnOXcR1hqRNFDcbgOBQQaD0+M3YXFcG66qHEm2UqLJaxKdHg34anG4UQyJsSJmVOddJVXKnuh pLOTC0baqtYSxSchzZa7bWd6NdSS0UmuhYxItVtVKrmVAqKaYxOkCYJyssOzqSa1OqVbDzU0V0Ux UZA0hvnWbzMxwWneebzAyNJEzFBRSFD0iix7ij9yhrUgpMESxKC6zElVV5Sraj48/s6BeLd+Gt3q uBrAprO6fSA/2EnjGAFwhgR8RE0HS0s3tUn2aTVHO96lU9TFPye1mXzcllp242Ptfc0JEd6iPMii Rr8+rfvnB4ULP5k6uZD93u3Lek+R7Q9RInrERlWiewRExLrHXZm8l8MaVUpSKKKSYsmpcwEowMGD 0uT97weAiOjr6/sWo4rS9PHIj0h+rSCUJWKiAFDxO4gaRYjKCxxPQXKGByHzjJczWOk9zq3nl28u cwJ+I0p43JVIcQ2nQWLFjoL+CB2A/PyjyGRmew8eEHhtaYbeAa0hsTyxkkYkMBAwgViixQ84fXCh KGAhMMEsvVVRgWOhSyKOmT6OjxfcsYHe3dPqS1qePus+kOAo3E3InQ63+ZP7Cbk2TvdwnukIQGGo KvT9Aq8tiYbk98V/mKwATmxfXpFDSQgQAhBJnGxCpGsPMT4G2TlpTp4BhRPYekPEvoFRTAKGu4gU M8AsMFuKMEFEAwLDExlVEJwqXXuvLy98lMFMmK6KRZcupp9jg9ZShp0qgd3dO7hSDcRxm6jKWGwQ 5lEOZTs6zuEDsRThJJJBEoI3EFDa8fRKF+BjPR3ZL0XJAwTJeYZ5DXEWUkl4Idl1jRfSeIdT/9XV a4UZhLgyjoobSJHzjR4NykzQlAOpUGRRdyRcp90voVqfImLpds9D2HmTgwlxSRqWLdx8YnWaVWST ZkWekuZpBQc0He+reYuncHgF1WpFlI7BNGCXKUWpYUihgkNP5yGkgZ4+7kYxyMUB1RiRzbWzMRN5 HDHHLdyr2G6aDlIl0ExjWTFCjeaTQGgxo0ibzlA+YyS6lJ0kllIaf/zT0cG1fZSovy6L/om+i1o3 xbZcjCoMqBSZHBeXdkvJEsPwchkE5C7iRZRqaVnhu92v107W5xX01nKdmKdi7DocShVTcNzYFFDN rUPM6o6ajlaH4Rth+lA8mSSDwh06iNppyGS6trIEDI2kCYUQXsSm4gspCaCzHePc9iqmtH0KtwpY uKoqh3inDzRYbqbjG5QwOEFB9s1AlYYhSsgw554mYg8iEgrjKJApkybxMnS6sJFnOLAmUQVQDC6S eTlakj2UgcVmxFjhEEQnIrkkGA74O++gExkcUMpWtRUchLMVTyeJDsvJZmT5D0mntXMHzORwslYJ DCwL4EjiWRSmuqPSEjzyx1UcZWORjwdjHfpgU7iZIQg6oyAyBfXpcUdyCSoJsSZAnU099oEmKefl k0sSWxCE6ioFyA4OS2HBShgY8jgsH6p5z6RB3mpqZOylxnKq8pq9wWSPWi7NYhIbQ8anJIpDFMVO v8wwcLDwLwzTfB0ZSxJL1tNMrUra8pQeYyOYuBO8qnibesze6TNjgNlJKTkVMA5LyHJcCzLHzFsO QpX1C8oSasMu0zgi6zFSZFPPb0NyCh1UvZ+riSPvmTDzF8vTz2coMTCRcZDgVByDZxOZljJ5TCyT vEG+vFsbdVLBHBB6GSRgQ1A4TLs5WlhQUF212mNeI6jiVm2ZMRc2PmvLyaMkMoUVJuNhfEbYoTZn WpI2lQYzkqM9CwfNT67XwgNQUgYUWpk6mw5PQvKQ7FNb16fUrdTMFg9NhBlcUYqUfXMyFRPVWUui hQchyWcL70cdQxGdI2KCNTvMCux4HnN9Bjo0UjA1IIBrC98UjsMjaSCZPlxa2kdBMvILhVZK/dhz UrH+g+kkqENx53+ZJY0rGK6mKFHQoS6XU7WbAko1lJdHYsLhRRMCTJ9TAhpFEok0GaxkumRSkpkp MV1kR2fBNDSpoalFhYhS4WUsWL5ilzU0LklLpJLkoUiWJgilkwUtLqUok2tzuakakaEak5LLEUoS 5omkqJQwSa0GtEYJOhza21gUus4tayiTVFlUKI1GoalKL4Kpvb+TocurFuUY0Ws4SFFmeVJJQ3mK eYsWpz6ZHFFFILFi6khRXpeghfDexncwWp2FS1NSxsWS/qw+KmChRzyvrJIFXF2+iir0tozNMkbn QKqULF80cnWGn1N6uORLEgYvAT0NWVJFG1CHJldE0dMKg8mLiskyo1hjSU8fS7lBqzKvJtRTWeBI XRYIHbVxtdssqKuGBs4GEY8hXEVSSpU9o0rG5kxBjiRM8VOpVGp43kCctbwmauNebffFmbbklOSp gRzgzIHgzqAFN6bqOAhjoS6m5pua2xk+C99rTm23Wm82PJzOTEs1GbVvVZlvIKxQx5UtQmv/R+OZ ShuoTHy99zHYae4rfwhLv9n1e3wUfkee/k6KY/XMst8PhKnq24uQYwkhJl7UySMTuyd3wqGDibzL nqldQ9GGio0V95v4Gs9AzNK1HMQMOIEqSAqIsH84RCKoiqpEijFRFRFRVRVVFVYgqqqqqoiqqqqq qoqqiqqqiKqqqqqIqIqIqqqIioqqqoqPvshT/ydqxCh7wT7IqTa+t3NylOt1t7vb3/eeFVQ1g/w9 KsC8iP2q/isP+BqbNlrWlrGC7IjBTBRDA+dRMkXIsoUpSk+7TVn6lTh8FWSOL67EkT4Aoj/JQFlC FqVUJVSqhHVqZ6Hm+3Jq2IwbMG5SUKKKNfS5lLbi6QV2ufATYxeCoEXLlzc7Qeq6m/OTJMBP0nzm AGAMBghEj2uzw2/H1eH1g+6wrkDhkydjXTsWp9m/LE83bUTbq2ct9GYPNzmnZ4DhRVOphPh9rMk8 2/Sa1wg21Ovw+jza8qdDGcxApSUpJi1dT7+L8UZmZRuOvsNRQ6mQyKCiiI5t7ebFQ1N+7j8d3XOS 5BTuMHeTBPJ1owRRAyT6iqKsXUoilKCmAqCUKUSCMBSCpTvJwRkWpSiZC58kd6NQ1Os7OTYDY34V qvt0I08sg6QrK7qzqipDRosu3uYM9xjy6r3ueUP21zrpnh4pQylbYMdRe8UO8FxktkbIqsTxTKQd qHDOQaKaEkOBhrQolDQkDQyaRZYlLLGgop/ps8/6ifrZE/xUSRYpIl9iqe3ElmLE2UVKhM49D8Oz ue5jNvN9rYnpaMU7qJdQiR83UTmUgp2rJLKQnYou5L9HDY1uxSwmtQWZWO/xya/Xnx32YtCalEpS zThoYDoUetTUvquze85tIBzwJmXG5VsMhIx1H7D7BzNQid9ZdwYPXpNkPJYk/iL6FQEgTIKoIMEY QO1irk1KTyUj1mt09Std7Vv09H/nNkzcUG1uKGxSyynveDBZgwXWeCcXF1ZeqffVVI0+NQXxzMNI f37/hpJSY+gSLIkU26bi8gRk1uSUYKO+CxYsIwfMM7Pp+pf6vqTcxuNLYhwcgTggN5gIRvKJNtoH UB9thwNWBJHFuZISUrWzmzJ7nAa73LiKTeV8ifYQz7tA30NCRzeoGRD9mNRS4GnWfj+X3v3Gksdr jlneh6bO/FYcCdu/eYscjXPR3Oje+HWYtmx2aenrFM0l5vu8SNZGucS11KRiDWmusUzSWrjl4OBx hQYY1NBxPwb3VfkX9+9An3kJcIc7saSFlpaVJeGc2CKaTxu/WmK6xD2DmskeBcNpNHVgbtB0nicj Bh3h6iFEhghGQlGQRKUQEEKSBQEhaREjCIBgkwlzLCsUW8++ct5um03slI4IiFEEAQhQKOCosUYk W3MSTBJJ49lKfNHDjVKCY6PP1DSfBUZ6zW1UdStllhhhghAQwENgLwgqwlvQcnpE2iOJijiXGcAV vY4+lH1HvHBYkBLYmfPQQ0BZA6j9MBgSCQPSMGkytWFQhhH2JQCEGsV2+bw3AeSxwysGsFylomMM YhIEMYepIcOJA3ejlehDENIdG16bQ+zPwmESDBYMibnRdDtp5nuerzWmxvgdRDDsMCaJoYQlYg7i S81SkhGEA3EGEHGGZ2NBQ7CnqXySC2xuXS5grJgoIWYNKmSZMSfErYJpoXEIPUsToSgcILsdMi3P 5x7fYFzcuYBBMLoew+7FS88KXFvk1S5lmZGKjNfa40xXvTGLWRoU4NDez3+jakxDMmwZm41mgRWZ Cg+pFhcUajOV5zNVPvPJZRsCe5RjFEiJAR98gDSSEECSnm2nPuDlZYNe5mXBIggFolImwTXDCODL zYhu4JUJbtV5cy5iSdWh07CIukCT1BbcVJDN6ADSHsAhKEiQCiSiNqCNagjSgiEpCkoQSCSSMMFX 3BqHPma5e3ggOOw5BJJIBEZIBKqBjUJjThVibOHfsQtnlaIHf5nM0KAmMYxtY5BnLcPXUQZTPaZT qnYmFchV6nCkglhwMNkX1J5OrDa7gXHL7kg1Aflf1Ix2wNr13xmlM8RZ7Tl1KKHmKJUDUydRmbBQ mdHmgqGhyJPrS8KutN9gQvYV+FEYGUNRT7O7c1M4qaAIV37moLApjY2LHAgeGmZqvJYGkc7GSnU3 6bYLmEPaKZBRE4yMJ2nKzjEi/TdPfp0KicCnAw5q43zmP03INKkh/IWN7m5yPJjyEbmbSqorFOaF LObW54Obx0tLobWk2uh3Icmh0M2LJyaXfm0pGlk4UNHw629pHsTuHpFewz4BIVQqMCBJIkSRTBYg VJJWzXo97uw5dkGemoWMOTDB1MOdtuedNoRFEG8b62o9lcnE6iAiVPDbXYQLL7SgIe8qikklAqlU lFFKWiD1EuWi9BJih0Z93C3CbtDYzKFqL2log43nA/NIa7cEChc5tkWvke0kewmesr1AQwKa+o+B fdPaQTF1tPUkRskywLgsAgxe6OaGNqHtArSbI56DjkxnpnIVTd151AubWJ0usDbWn7zJg+wLGdGo KaNiTQ0lgvI010pYwacHtk0CIdo2zpUvOLipm1Ol1NWasPmHsc3U7Hmn5uDYdxmKhMxYX1mg1gdJ 7TgjeN0MkmFUnECLFo0RogkOg7/ZXhYpfw6qlstVpmK2HXXhpythVtfawv5tRINeenDdzaPW0B6h G9ZEetdOgMDmOyoQI9g49fXKF0dZgnBD2hormZiPvASAk/kSPncYjoewyOGBxi8/oazWO4kmRaH3 vYWKFCDxT4bWHJl5u4joynKck9i6alxF38D+HBuiljF7wZJnwySQgc10Kq/gAEFIGLgYJpI5NjuL hM4bQVvA2NDkg1SW8htBiYOMA8xY3HEDvBoApbUPW8JJGQkXnFAVERUEQ1UOu1d62iaJvVnQcxPu q0UwInfFLjjgdUqbiea4gFbRqa6BCgC2kkNRAgKtJdKmDzUXOxs5yKXQQ3u19DsXIKCXGYodxQbV OdbHefFj19Klg4OdzcU0tQRymiRl5yLmTPuaHJz2MT72lxcfHR1TN4Ny+6EYLOzSwzbiZuZK8SkU glaYmCtOo6WwXS8xcogeQIEzUwdYimbNm1rqaWtd2OTcxzHBx+fZ6mTz7mxrf3urcwHzD97y4NH0 Pa62bc20+iGp7D1xRRPYiCgAeHDC6NDhv5xQOx0hdO3o2WegA0mD4CJYS5cxYZHVMM5L2Wx618C5 7Eg7HvQ+8ac6e4qAhUNBStx65klfqA4jCtaJJUuRYoPI1GPxQGdSxQkB8Cl8kEjJ0sblgKpM+s4P An2JzypQ7t6le/v1I27hDByRHJv4ibWFkepnOhzyeM8Bpcm9v2OzN6V2PpZNfLup6fUI9bePpets HzPqe1df53wPh752oVPP71lSopUluiwpOzP4nH4YlylHJr4w8OTaOhUyxFPkGawJldhUbzBow8Wb Uo1ULKEU9Cx6r+dUvr6GqYMPOY94UKGhgig9CbnjrFxzkuLsZKfGlFUPiQSh9bLUrIXJqbFWLbGh qdDQZMGidwsFUnkVPn4EaBtZqbl3S+dg3ZOKm27Y6G8ya1mx9Yjylnu6R87YeDwVKilSdsh0LSdP Hr3UtdqS6c1PFqKrxjsIY8gMAIKREpiHiFdAncr2HJLqMyOUK2H96p9S7i11RsC4HZPgBDLoeZIO 8dOwEtJC78FDQzSg416FZKdS2hDPyUPYYmLf3n1mkd303KmQxvVe5msTQfdpijOtzg3KmOewIdBy ZqXDUcYma7bGR6lzU6nQc1MR2GcbWcToGrPGaCo3NuSSQmY0HM5LKZYZpy+Y607b82k0N3jeXeG9 HgiIwNSW6CC47G4ySMwtRaHi0EEolGCYTHJRdcrUahWlzkrrYvRankenpG+ymKim/wDKb/Ube1jf dVmqmhpcd1tYqWIrPQx0D5AdTcsda+tCRubnjxJOSBi5qSJ6VAdJy7Q2shNbiwhsV2lh3Wdr0CWZ 4UKHqfSsZ6AQQI4p4KZ0LHQnTJ3nzvGtWQ1W/kKm4skoTOzSg2abS0UUocHjxUeFNhpHYUsOkthM GSGXt2q6pYQ1oYqTsdp1EJ0qdSWgvI4xtE8Ot8Dkigx2FY7yBgoY5FJlRJXTuTqLX1KpJPqNkaif opY5LZhiQqiiH63MdXmTYOFRkON1inBJEBu6jggveVaiIE0EK63a4HHX8Ld9vB++fdIlcv3GmUZ8 HK+mCADMhCB0mVqsoq9Fqc9WiLh9SilgkXGVQLxMlCfr82yw35ieF8Cg341/B+JivZLPn8XUODjL DCiiYWnJxm6OZRdWG6mabOHRmSrbXx8vq4JDyQRA2WM3fA8r0gw9E1sYsJOEUkDhiiIQMBSLFVFg T0G/f39R5TVa+U4HpJcnJ5bnE1TlynC8GuE3w0bBSVzg2ONbunc9Xv8PRryc+HmPuqIiiiyCCAjB YokBSfN8fwHX1e4/jODt8z2E/QJ9y09x3oCWT6JAZ+b3+ZyEcD/Rxeg69VfVg8s85Sq6MCJnSQVt sMsteRivryEA9Wu4qosWCogkH1pORAtVVRWMkj75ej0/SIdphYA8SUrWtIOBDcad/rE6oImIe0zS P9D1VQGwFqYFfv85KJpQBP6+3yDB8oKHxqD/2P/oCv1AGQgH5mBQMD81P+SGpUX+J1mpVHHPYI6j XpX2g9R8hGAsQiiCtk6RJIB/mfVAt6ocGqD9cRviH8NhF2DHV9piOsVGumqgpcn8HRMWb8mtcu2P RM401VEm02oFLOy+z8YX6DoVN43nIa923kCsZAkLywrk7huzThoZkfpVRE2nR/0DeDQvFR9zVeoY ArAWCsWABBYIXmJc3SQkuRF6YN6gpzY5x6Cyo6BxUFKFHBS5mFF3mx1pBpkjSiI2CSYxdMZhFm/i IcDcSTctGBCk4tqzImHJIuIulBRQoo9NAmUkSuuveqYe+0N6SapLJwLrJr8E4E9KvQkHVaUqJ/0S zgiNHYu6OzTbC0suTAWXWelzd6Zcye9aSJO6biRGIPEoiiRSRSIjaizfYYJJks3iIoSWUEGUGzff W4FjWaixm3hwi9HeoNIifkayivMPhaCC/0tQktoTYpSbDsJ/yyq/eBn7UkA7/aE9VlHKIyCHIqqH LB60IfJA4Aod8zZFnYpERzJB4yEjk2NgnTaxLWtI6WSxKcGuSInfBKkFKSTz5XS7ilhJPMT/Qn72 rR7xYcYJFNckSaAoUbvEQoCiaR+z4siyCmQRSQEgqyihKCUhQknJRK3eSlCy8mxAxs7XNulwcoUS EZM85SLiIqXepN6JJM6CvGk8qMWcFtQiK9knGA+M/RRF5uhU3ICmCA9ZxKAK6OZ0Xiu/z68y8d1n vkM1gPIbqhkK39QlT6AeVz/nEh1kiODRJImY6n+q67XQ95LNMIhmb1yOaxcMFAwHeqjoHFTO5G/e qLmQqJyoCm8V8JiWERMGhgEVSdOx8c2YknBYm+k0KHPUqOxBpoqoVVUKKFKClFCTVSyTzI8QiZm5 2mYOmrgDTcCiWFdTcPeHYbTpw1gTU9tJ2GtEyVhA+uyFSREIoAoyQgycNoqRRQ1HeARO8ANhiwMB KXUM2RYE6lo90OEGC5ILOpEzmHCCS8tNY5GK6MeG7EwERhnAyCxZsI0KGx1oZ0kk2jgihshIo86p Soa7aE62zoTS3lhJN5tZiQb2hzCOkwBgrwQuwampBkSQJJBPeIUYSKqqgIEBgSRJ6SbhMA7EBKpF ynS9dgycJJDhEicKWRKHBvXQUk8Ezdc/V8H7f6ef4j2tbWTyeCu9O/Jc8QdqB0Fj409D8q/Iepim 9bEbA/5NwWBo7HcT833OU0hsQGE/LODDBIqqqUeVZbmHImggLCCTgIFgU6KP96F4KwM2o5trwaYM b6OQWGAZCjT+CqUMaRewL7ffS9vSRKJSlILiBhJKQYiJ1oPrCxqATIM8JCSQsKFWnrFTxoD5oskF kc/dtZ2AhcVqSxEggQO6gqlBUYC2IIFSBUIHoi5kCplQQcqH20sMTEkL7hFAWEg+nVSl8T3F7fvL YOQzEFOwGPIIYPkQWFBWfBG7WewuL8YOUFgVCIoMRNZk/g/lTf/FzQ565xf8/NJJtcGlZca2xZB3 EQmBQGkU7KUSkTuGCuk9kfaYlA+UJQwL+koerNSvY7FOsEchInUUS5TlYoPAj4LUXzdB83zaC8Nm o1HtNf3FUT3zePKfylH3O0o+5EChdgMlD0nWdpdquNvh3J+KXn4R5jEzT+WZdqweN2EaE0bom5Op SHDjnGm1o5yKQ1sF1KRowkHoySfmiPwY3ZslY3hGDBvI8anoEVEl+qZLRqn0NkjRuXoI8Bp6mgpU ilc8JIdSfSdLUzZuLOP2aoR29AeceDuRToSpS088Och0n1HOBfmCbxHgEAxuihaDGKlMzVcm42TQ 95vXgN5G1NJXtZBj6IMOUGkKdhpDnYVEKfEDTIm/e6IM1X9DgI3xjUnUtof+HXnqdgntkj+iyw/A yQOXUfIyikk2D3SgSkkLd2AKMM0AgIZUd5BUEweaEIHTd83ZjvXTRp7vvta32u9M3FT7T3KeT7nn Gp1s2h8mTU+LSyfe+NPU6HAdD6HtYN+be0Ol2w2KlqqpRRE42Iw6SR5hbXYmd1pkLSwuMNWBjwgx jMUi6WSwNVFyLjd5SyeoxFSsRkFkVICEhHhIwn3+qyMPf9uSXj9rpZROaoOajWW9+bAMZ4TzO988 lKI9yp1vo0OMRFDJJRJtSgqbf5WVTT1vIafS0FLLOLEpkljOfdeUUnp15BmaZvPGdAjtEaTTjM5Q WnQOHQXrMG/fo8m9xZsbsGPsdk5oc513jvkVhOhSqiWmG563u7U2MWKzzrqh5De7WFOpk6uXQ0TL jQaQIw8sbNTPhA3m4CxsUNhqKFjGXU+CoGc5blITMQWlWshWKdnu3L/qneG4EaoDxc3CGnsGGbTX xFNDqYj6EDiZYh4TAewqfjTgkp9TTvS6UfQ6mS9rLVCTFSrSosncuwlR1M2vaTXemh3RzcIkUopC MmSQoFYAiSdZ851yTyEnh1EU+IsipIeOpeSmO0TpUdDBgrJZdVynyChLKlgadaNBhBtCnrZZhJQu mSrOiiIlCpBk3EPo9x8eA1uLzAKjWVm8YILFSqUzUSccTQCOpE2rN5X12mqb418xTrQqYOw58itv rIILnJYoYMbYPoYGDgEfc+hxIxeb3s2exwbWBh2VU3RDc6yMKS1rSopVEWkzWXhi+gylXO5OLbuY c3rb3UybppMY1iwtqXvOeqa1OPoWf0VB6PXPQ5LFfZd/ovHlM3k7LzhRwmUPl7GiSSPLscWnF4su xxHYu75DY2uHNo6Gi0q+S6mhE9Q6ygC4dJcLTuXqIw2gVDThzxhSNu3YOSP1bWJplN03vnfalTkI bSGDh9r32OCpZ2RDJB0CphzOohyLCBmbUMjwm3U7s9rDlTYC4Ep5gsYGGAYmDJE2Tk5CZA4X+wMD Nt+kHE0wqPQJimkF1GQ2KVFosCpOdpFlKKTgo1QWUyPtVDKwICoilTNMkDmf7Qwgo6PyMWCzAwZL lpKyd1clQqEzDBTAF+93Szii4LplpiJEMBYULiiJWuyQTH4HmliGSFEHFTgKqXBKVFIIaZqOhYUs m80hjcrBYteo7CoV0dtS4oWHGUnUtkplr3SvFO3riPEv3g44pZpCptLc2cCchtCDrD0FTwFEBqCw QZYZgv8vAyRl5+U8tIDnmOI5xmWHPbrsfRD1ck9cc8Z6E/f3VgQZDxmHzYFVVWotMwbjtHLDYHF2 9/r2ShJKCJ4BDviFxxDKIYwaXgWjsKCFDwJ4J02BC5EstFMW4Zu58iTeZrJNFQrzcGhh3c+fi8nG 3bZk7dEe5CTbZJ7mx0yEsljewPTJFzmqezPQseWGdtlcMHmXWWbxkKKIUmMJ4UZivp54XPyIEvbQ ial8KlBU0O81wPUJJ3pkpsjCooH7xOcLHwPdH1+9daHgmEbb1193XOCpi5ZpJCyo9i42Lxub1jJR oO1OCne3MYdR0Vbn1Fhrc3ZJ7ae3t6auej7blcDaSKD3eOKROWHg24EA2GZ23FecUkuSkT90zLAh yuszbmhUlSNHqdcYBfzFjOPpWm+d0k4v4rvSflRH3qfp/rTrZNzFuFdezbe0uJgLIJAMKiMfAc8J rDAh0IeBeXGCpX0pcJ+tVPWYmBZ4iZa4cfL71Ss1XQ2w+cQkSIRjFF2NzBPL62QmxROBSnzGHOnG +0s3d7KGjmSESb7d4IIw4UB9WWUGxc8QNkbXEWwFw9hYpYHIS7EQYEr6ca5iE3tBqipL0K7OaOcn YzKhceYalLyzBaLqTNdcmDVxXYjTULPQhMqJRxKUUgMbRFl0UYImnVIW8citpQZK+IlC28v9JCop ++Goe2g+fk0r9IzqT3wzwHMgppLzdlZhrVUyRPLfShC9HciH6NfMCnCIidxze6KL4YKHF1qyiJyM yIn59SgZGADlqM0fbJDY9h7zznn9JHHcfP6KxHc4CHPSWFpt4nAuKm1HcSLCZsOZKnBIzvCGRjJI 0Nz1OiHzoTNTQ0NthOmchezZcmgpIx9FN7rkNhKUR1NPuHoc3LjPvfsQ/WhdDepwetLSLFOA1ves ODW2zJHyqSNB22Up8unZdPkpmoj3eYCeczHga/dHae83EdcPk/OaR3GRqIeaqfsIJE21IbaQTNUm rrd7se31vpZo4tan3Oq54X7xcTlvaWvS5d7ylo8hH6d5pV56j73sZ9A3MzCNre7JLPNs1xwh7RR5 PDnMitittHyK1ZbVjEVEUE1IaORQnsNeJPW8OSz7ExySHWtra36CWa4RdLEn4KkLJ+JA+d+xzIbS bsILIKCKkUIjAWLIjIxBgkGMBQiirJOiQ9lMEvslK/W0FxeBas7iloiZX3vBgAyHzm5QFQUYkYoI 8HwKBzGHvMxBaXB8i3CwIkIowkIKNbUCpJdLMDRpchjHyds+VO52dr1OXQ7/rkQ3zYKinkNT0b2D H/X3JdKp0tsnAR7F2FEMTFLy6lh7+2fmPokZ5ZPbZ7qrX7Pbd73UQy36aUxvnOrOIYzgONZ8Bl1l nSzcn4u2cmECMNcL3Sn+PdClPypoIpET6D8NBUyHb3HiNZYDUb3qchCEBCkLxOzPsG43CuxdXX7O oJqM2vZk6oYUJEYxGcqRpYxIMhUkJ6coRaeqKDvlIKeGw9rnGl/bXS0xFnjKQnwpEepi6FnHdDy+ 15tbscp5qpo99M75CQ2QlNh9d4mGjaIxAgaLlirYQ18+CHNUSh2N9UUvD1q+5hFpVS0p+39Pfk6z snYIkh7UAogJSwqSKMEISK7jt752jt5TkelXxQ1YMEgwYHlsoMgiRiQQEG/HAMQREGQa9X+Eedui O6LOHRuK/HSn50a1SODqej6VUw8YHgUPqiXpB6Q06mRU/X1GsP2omhcnf9xynLqdAjKdTd3qfMs+ 9+rxNpMkNhaFUnv+ZwfB+Y6W4R+129/0dA/NvdeyIPhupaWfzr/5c+XyqhPh6zriWyNMOPy2c2I4 c6cstR/MZBOiuGEJmvOQymYkevZnY7AkbzoQ4/0nsA6/KRojzMmh90fdSZLMK1eoYpyTjvIY2RYh eIXep0vk0vve7XGiIwa9kjj5OPPc/QOt6quug0moDMbb7TQTKtGm88+ckwoEBXQCKRxrZMF6VKi9 WtZd74lszfQ8zW2Q/qFDP1AX9BHRIaADVf1ffDtipeprB4juAskKjDSXLoIgR5zenaKGpmUciJUQ ipCI1gNRBlRDkDtq1EIqmKg00JvXg0RW0h4Ytwk0SGSpH42mGUnFfn3ETcRNRkhctRhujQ6eJcZl kMBxIUn4l6tfkPOGmG+sIiWnz3tlho1Dv0fZZ0v7nnkNAskGCcoFyCLT07wLJa+jeQBySZRwTLOe ncdnPCQMDkDEyZyTPzywUWiXZFD5qgxrRgpMGFoSY3Une3smxmz+rpe+qWs/sUfx1ylui9K7KlF1 mk4Ea9HLJJFylY17Sg1tZF+r9j7pCkLfsxMvwpWqLE2RudKJVrqEbWy7pqk+r/G7ifR0BLHgBhDv LP+UCqHUntPZELpql0qNgvL6vBg1MtT8+v/CNCMdM1EPHf155ti7/b2zMykE1WbWCD8zYsZgPysK BsIE7eIFGIa3E3wnIxnHYwsTCaienjMSagNBGlpScCQu7IaLhtqU0aMLUlBBQUpRLBQvxCzKJrWo lmHV1aJtEYQDnaiJvQvKyFnenLZSzVSrcwxcphhMMG8TCEKxDjgol4yFoRVolpSVQLlFOaYoXH6j wnw4TUZt5ncP4VA01Aoy1wFVdI1utJJoaILCggbCBZlDIQus1sTUJRi7loLrglmSJkJLWVS8lVQf P/fh7WKN+VySqYJcTgUoleDKZKJSpJEqKiSKURifPdLNTux2Sjlkxl1h5i4qCFjNNIxS87Kahh9R Ool5BX3HE+T4HnHMYbHFuWqqqYKiypRcULS35MUIZJrUUEYIgEoMhYepCgxj3BaykjFscL2ex9rR mPxd7TNzeL7v2eY8kFhzEUkMyJTUU5yBIQiGu1DHHI6uw6zxjxW7XVuvw2p+16VhUqaWhOt1GlNU kT9xyNOC5Gt9gPtYgsVAiAPrQq/CeBD4j7eU4IcukEgi7IhxDbHbQKCMihJGJuCGuHUQbQGpBkRL kE9ZTfdii3lEMYWXnv+c51cS8DlLhNECwtz8wwdnKEOLSlkdzC8T10lSntdjUyf7XndkzUU7vxVS 63FaWomHatRtqJsQlSRrGM+3TXzmBu7HIKCdieMCqdSROOBzii9eLeUKkOBCkh/c/yxIbGEnBdTj 2Pg/kx1TgbFUqknX0J4QseYefzt2aVEfAqEz6P4tk21Waz0xYrN2EwIXP4fh7HwPk7LLTzr3vRLX WbuIiz1qEfob7RJoaPk4f2rvmTY3YoURUc91vsH5az+WMh6IQ1uPlT4S02yRT+3FNkpHrHqU03Z9 TJE1ptqKUaooqVcbMCmHxYHSQ0Rbzc0mjSN7GfAzRdZP3f3S5DjAeiO3NCKObe2DCA1scCGoYfL8 ckn1vWPU+153Bykken4LMmttZx6VXWfd4DwiT8lI6Hc+x5x8Glv+ngdsj+yotK+l6XsdibeXBBBY w2kGoVsQRIBUkFhSIhaFLClEUgjBFgwXwprCxjE6/CBQagQdpDyF5ZMVQLMCAruORUP2Fwg0SKll uxCJHb3dRYwC/fFaaO8NvhzAlJvAC0slKUiBaMVtT/OdMsAlihRCheu0JBQ8kBoviJti6oWgfF8c 4FTNwKG0NpxOV85oSMSEVZBiIML3X6Nf+Ba6tPRNIQE0a6a04O+AwQgWhDJJ/8eP4g4Oghscilho IP2HzfjQf0Fb2Up0H2tCYdEW5fHBI6InQlcTPmuwKwfJlPaPRjVKqTJ63XFTbLHUowYi0fBSLfEU 0BVJTcT4DHDY1TdUN5GdknMPrnnzjzkP1trgbJDa4NuMJg8EOTKIk4FhskILb2w/naczwwNzQG9L EalY4O0edoBBuBBfTnzYM2kqCIVJTUo7t1KC1h2CSDeSWUb5KoZNy0l2DHCCYFgTDRvuZmpWMRE3 DRYYIVw9NJsashom08xeDR0BsU4tApxZRO7ihsMKlNqGklyaQWHVrq0pditmz2Ff+zp1yNjp6Yqs 0kLJIChBcuOoKt0DWx8bxJNm0MtYbQaXUNaran1qqquMFAPZtLE2UFuZJByEdByUdDFoXGhuOp/W t5mLvdI2sI1xjy1ttNtOphRxxJaMF4vDZR6dFnB4yeT609BDb3DQjgerZdrt6mMKqayngsi1RFeu vbRkPs0NQ9lSNCF0c1HW0Ehxa6yPp+qlVX64X7CXkXabBQzOhCtk+VRTURCdJgVEKllG+IzdasGp Dxa410fv/B3h66HQe7tOshDl6fEgedVVVVVVX8ncdc2A+aMbKUqZVKq6MMyZE5KLi17QukLuqXU2 ojF0pSVbAhUXKwYMGCyg0Jg3ChMREDY0UJJGdVIbtk8AhIdbUEzqYVkMyp1ImA0jPAkC8Jq2GJaA y1S0JfUjAuEdp2OXgMznuB+IN0As5bva9bJs71mWZDqxVZGDAzVZOV2lbKlyDNTlZkWRHUYLkFyh HeIxokroxgCjDWCIBjxEjWkhUMjUaSS9Zok0DA4CAvCXIcYtIfTyKQJAZZhRSY9dDA4JMEmCzbTp KHcFYYFF7xRdgSLJVFoTIJn1pWhfMmZnrnZSJG9zZ4skpumy1rLWlllJUuJJU9sQ7IiHqUnqgllg P5PnEWSJUSkkqUSkh4+9mkMAZkUCUKSSqiRmUjKiikJUKQFCKoH2TakEAiSTYBJIAwZEiQA0JCgh CxIRQA5aFgFI2IIDIK2gkgCVUgJUIP6iqhfC3s79kcE3qlItZ28LzoYE50hgumRa5QtHmIUswIWZ ulI21VJNhDetQh0sD6RnfIh+c2KcMCqsF1hmE6eYG0wguO+SCiXjZ2iZd946JbcuVha61o6KMV00 F9Eo6GhdgSrljArHxaU0R7I6izJp1NK1kJ3rTLQizVvYXmbmpvmK51iO2oJVRJ4owRFeZ47Hx3Wn rqXqNMHFFH4oiJvtaiVQokBOn5wKpvtQaln5jPPY4szkxS867LfY071oS6I65ny0XYnq58yh6TLl EpaYpDI4ImXCzDKLi5LMiWVCoLyR0eIEM6xOegsBvNRyFxFZBTQWHWBEoIFnA83FULQzLWNF8rll ht1UUpwqTJRlMFvJS5aAX0rQgwqUBzabMC4E9X1VDXi5QyTMq2SoTl3JZN7CLtJsb1t3zO8h5END qMm8djwdvUo6/0puiyT3lKbzF0p9CheYJ/DS/rFQY78wVPQnr8uWc9tdo4w8GkTB3TGWZ6PwnJE/ HOWfS4XXmmHg1kap3qWEHgQ9npq3Whj4/EBj0uCpvRKnw3ZA50GgUzo9aPJCjim42PSaLH7ypQWp FCEhEqQIVKAsMIWRPpIi2XyRUf9GHUB+44nWLi8Y3nbN3jgIo6t28zzHAowrIVcTGiLzI+wxSXVG cqRizdjwcBramObBnpOrBI2t7FfYVOpa5qlCRwZOwQYJ4QI9bdBFRE/AqBO9LDA5xsIJ2HhpR8Pz 1HKBZh+04FBMopjSOdLpNclk+lSehoWbpTJIWU/S7XMRm2fJ4u52O5rlKiJzdDxH1jRyZSQ7jD5r yH8JT8Sm5Ub3qLITEhRyUa1KVENauVZNu5kyvVYuKkxXjOq4sxxwtGHwNzc6B8DN9k1uFGaLzOjY mobJSkORAjMrFx2KRcZLUGS4kHLkz8laHTAIGUmnpbnk7eDU9jazW0ubzOhEOLdJDfJNn7qfHxb1 Oy3ejQ6lkh2MLN/xTksoz5MnWPaeLiORB0r3O4DR/xASQ4qP+oklkpqD/xdyRThQkLAVkKc= --===============0254781392==--