#At file:///data0/martin/bzr/6.0o-wl3724/
2652 Martin Hansson 2008-06-27
WL#3724: Short-Cutting Join Execution: Speeding up star queries
added:
mysql-test/r/short-cut.result
mysql-test/t/short-cut.test
modified:
sql/item.h
sql/item_func.cc
sql/item_func.h
sql/mysqld.cc
sql/set_var.cc
sql/sql_class.h
sql/sql_select.cc
sql/sql_select.h
sql/structs.h
support-files/build-tags
per-file messages:
mysql-test/r/short-cut.result
WL#3724: Test result.
mysql-test/t/short-cut.test
WL#3724: Test case.
sql/item.h
WL#3724: Commenting only
sql/item_func.cc
WL#3724: Initialization of used_tables_cache.
sql/item_func.h
WL#3724: Initialization of used_tables_cache.
sql/mysqld.cc
To do: remove
sql/set_var.cc
To do: remove
sql/sql_class.h
To do: remove
sql/sql_select.cc
WL#3724: to do: remove reference to system variable.
- Added function initialize_shortcuts
- Added short-cut optimization to select_cond, by means
of helper functions/methods.
- Added helper function to append information about
optimization to EXPLAIN.
sql/sql_select.h
WL#3724:
- added fields to JOIN_TAB.
- join_shortcut
- has_partial_tuple
- added method do_read_first_record to JOIN_TAB.
- added field last_join_tab_accessed to JOIN
- added method get_join_tab_by_map to JOIN.
sql/structs.h
WL#3724: Commenting only.
=== added file 'mysql-test/r/short-cut.result'
--- a/mysql-test/r/short-cut.result 1970-01-01 00:00:00 +0000
+++ b/mysql-test/r/short-cut.result 2008-06-27 09:17:42 +0000
@@ -0,0 +1,336 @@
+SET explain_shortcuts = 1;
+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
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using index; Shortcut(t1)
+1 SIMPLE t3 ref b b 5 test.t1.b 2 Using index
+SELECT * FROM t1 JOIN t2 USING( a ) JOIN t3 USING( b );
+b a
+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
+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
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using index; Shortcut(t1)
+1 SIMPLE t3 ref b b 5 test.t1.b 2 Using index
+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
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using index; Shortcut(t1)
+1 SIMPLE t3 ref b b 5 test.t1.b 2 Using index
+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
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using index; Shortcut(t1)
+1 SIMPLE t3 ref b b 5 test.t1.b 2 Using index
+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
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using index; Shortcut(t1)
+1 SIMPLE t3 ref b b 5 test.t1.b 2 Using index
+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
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using index; Shortcut(t1)
+1 SIMPLE t3 ref b b 5 test.t1.b 2 Using index
+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
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using index; Shortcut(t1)
+1 SIMPLE t3 ref b b 5 test.t1.b 2 Using index
+DROP TABLE t1, t2, 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
+1 SIMPLE t2 ref a a 5 test.t1.a 2
+1 SIMPLE t3 ref b b 5 test.t2.a 2 Using where; Using index; Shortcut(t1)
+1 SIMPLE t4 ref b b 5 test.t1.b 4 Using index
+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_next 0
+Handler_read_prev 0
+Handler_read_rnd 0
+Handler_read_rnd_next 3
+DROP TABLE t1, t2, t3, t4;
+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 ON t1.a = t2.a JOIN t3 ON 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 5
+1 SIMPLE t2 ref a a 5 test.t1.a 2 Using index; Shortcut(t1)
+1 SIMPLE t3 ref a a 5 test.t1.a 2 Using index
+SELECT STRAIGHT_JOIN * FROM t1 JOIN t2 ON t1.a = t2.a JOIN t3 ON t1.a = t3.a;
+a a a
+1 1 1
+3 3 3
+5 5 5
+SHOW STATUS LIKE 'handler_read_%';
+Variable_name Value
+Handler_read_first 0
+Handler_read_key 10
+Handler_read_next 6
+Handler_read_prev 0
+Handler_read_rnd 0
+Handler_read_rnd_next 6
+DROP TABLE t1, t2, 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;
+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;
+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
+EXPLAIN
+SELECT *
+FROM t1 LEFT JOIN (t2 JOIN t3 ON t2.a = t3.b) USING(a), t4
+WHERE 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.t1.a 2 Using index
+1 SIMPLE t4 ref b b 5 test.t1.a 4 Using index
+DROP TABLE t1, t2, t3, t4, t5;
+CREATE TABLE t1(
+a INT,
+b INT,
+KEY ( b )
+);
+INSERT INTO t1 VALUES (2, 1), (2, 2);
+CREATE TABLE t2 (
+c INT,
+KEY ( c )
+);
+INSERT INTO t2 VALUES (1);
+CREATE TABLE t3(
+d INT,
+KEY ( d )
+);
+INSERT INTO t3 VALUES (1), (2), (3);
+EXPLAIN
+SELECT * FROM t1 LEFT JOIN t2 ON a = c JOIN t3 ON b = d;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL b NULL NULL NULL 2
+1 SIMPLE t2 ref c c 5 test.t1.a 2 Using index
+1 SIMPLE t3 index d d 5 NULL 3 Using where; Using index; Using join buffer
+SELECT * FROM t1 LEFT JOIN t2 ON a = c JOIN t3 ON b = d;
+a b c d
+2 1 NULL 1
+2 2 NULL 2
+DROP TABLE t1, t2, t3;
+CREATE TABLE t1 (
+a INT,
+KEY ( A )
+);
+INSERT INTO t1 VALUES (1), (2), (3), (13);
+CREATE TABLE t2 (
+a INT,
+KEY ( A )
+);
+INSERT INTO t2 VALUES (1), (2);
+CREATE TABLE t3 (
+a INT,
+KEY ( A )
+);
+INSERT INTO t3 VALUES (1), (2), (3);
+CREATE TABLE t4 (
+a INT,
+KEY ( A )
+);
+INSERT INTO t4 VALUES (1), (2), (3);
+EXPLAIN SELECT STRAIGHT_JOIN t1.a, t2.a, t3.a, t4.a
+FROM t1 LEFT JOIN (t2 JOIN t3 USING(a)) ON t1.a=t3.a, t4
+WHERE t4.a=t1.a;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 index a a 5 NULL 4 Using index
+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
+1 SIMPLE t4 index a a 5 NULL 3 Using where; Using index; Using join buffer
+DROP TABLE t1, t2, t3, t4;
+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 );
+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
+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
+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
+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
+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; Shortcut(t1)
+1 SIMPLE t3 ref PRIMARY PRIMARY 4 test.t1.b 1 Using index
+DROP TABLE t1, t2, t3;
+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;
+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
+1 SIMPLE t2 ref a a 5 test.t1.a 2
+1 SIMPLE t3 ref a a 5 test.t2.b 2 Using index; Shortcut(t2)
+1 SIMPLE t4 ref a a 5 test.t1.a 2 Using where
+DROP TABLE t1, t2, t3, t4;
+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
+1 SIMPLE t2 eq_ref PRIMARY PRIMARY 4 test.t1.a 1 Using index; Shortcut(t1)
+1 SIMPLE t3 ref a a 5 test.t2.a 2 Using where; Using index
+SELECT t2.* FROM t2, t1, t3 WHERE t2.a = t1.a AND t1.a = t3.a;
+a
+2
+2
+DROP TABLE t1, t2, t3;
+CREATE TABLE t1 ( a INT, b INT, c INT );
+INSERT INTO t1 VALUES (1, 1, 2), (-1, -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;
+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
+1 SIMPLE t2 ALL a,b NULL NULL NULL 5 Using where; Using join buffer
+1 SIMPLE t3 ref a a 5 test.t2.b 4 Using index; Shortcut(t1)
+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 b c a b a a
+SHOW STATUS LIKE 'handler_read_%';
+Variable_name Value
+Handler_read_first 0
+Handler_read_key 2
+Handler_read_next 0
+Handler_read_prev 0
+Handler_read_rnd 0
+Handler_read_rnd_next 4
+DROP TABLE t1, t2, t3, t4;
+SET explain_shortcuts = 0;
=== added file 'mysql-test/t/short-cut.test'
--- a/mysql-test/t/short-cut.test 1970-01-01 00:00:00 +0000
+++ b/mysql-test/t/short-cut.test 2008-06-27 09:17:42 +0000
@@ -0,0 +1,344 @@
+#
+# wl3724: Short-Cutting Join Execution: Speeding up star queries
+#
+
+# This flag will be removed
+SET explain_shortcuts = 1;
+
+#
+# Test 1
+# 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 );
+
+SELECT * FROM t1 JOIN t2 USING( a ) JOIN t3 USING( b );
+
+# Test that the shortcut 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 );
+
+# 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;
+
+
+# Test 2
+# That the optimization actually works, i.e. that unneccesary reads are
+# indeed shortcut.
+
+# 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;
+
+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;
+
+# Test 2b
+# Short-cuts followed by successful keys. This tests that we perform the
+# optimal number of reads after the shortcut 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 ON t1.a = t2.a JOIN t3 ON t1.a = t3.a;
+SELECT STRAIGHT_JOIN * FROM t1 JOIN t2 ON t1.a = t2.a JOIN t3 ON t1.a = t3.a;
+
+SHOW STATUS LIKE 'handler_read_%';
+
+DROP TABLE t1, t2, t3;
+
+# Test 3.
+# Test for outer joins. We may not take shortcuts across outer join
+# boundaries. An outer join boundary goes before the first inner table for an
+# outer join.
+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;
+
+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;
+
+
+# Test 3: That outer join boundaries are not crossed even with more than one
+# inner table in the outer join.
+EXPLAIN
+SELECT *
+FROM t1 LEFT JOIN (t2 JOIN t3 ON t2.a = t3.b) USING(a), t4
+WHERE t1.a = t4.b;
+
+DROP TABLE t1, t2, t3, t4, t5;
+
+# Test 3: Test for outer joins. We may not take shortcuts across outer join
+# boundaries. An outer join boundary goes before the first inner table for an
+# outer join.
+
+CREATE TABLE t1(
+ a INT,
+ b INT,
+ KEY ( b )
+);
+INSERT INTO t1 VALUES (2, 1), (2, 2);
+
+CREATE TABLE t2 (
+ c INT,
+ KEY ( c )
+);
+INSERT INTO t2 VALUES (1);
+
+CREATE TABLE t3(
+ d INT,
+ KEY ( d )
+);
+INSERT INTO t3 VALUES (1), (2), (3);
+
+# This tests the case where we have a left outer join, followed by a table
+# that is inner joined with the first table.
+#
+# In this query, the join predicate t1.b = t3.d is transferred to the WHERE
+# clause, since the join operation to which it is attached is not an
+# outer join.
+# Normally, we wouldn''t have a problem with outer joins since join conditions
+# are not transferred to the WHERE clause in this case.
+#
+# t2 is the first (and only) inner table of the outer join.
+EXPLAIN
+SELECT * FROM t1 LEFT JOIN t2 ON a = c JOIN t3 ON b = d;
+SELECT * FROM t1 LEFT JOIN t2 ON a = c JOIN t3 ON b = d;
+
+DROP TABLE t1, t2, t3;
+
+# Test with more than one inner table
+
+CREATE TABLE t1 (
+ a INT,
+ KEY ( A )
+);
+INSERT INTO t1 VALUES (1), (2), (3), (13);
+
+CREATE TABLE t2 (
+ a INT,
+ KEY ( A )
+);
+INSERT INTO t2 VALUES (1), (2);
+
+CREATE TABLE t3 (
+ a INT,
+ KEY ( A )
+);
+INSERT INTO t3 VALUES (1), (2), (3);
+
+CREATE TABLE t4 (
+ a INT,
+ KEY ( A )
+);
+INSERT INTO t4 VALUES (1), (2), (3);
+
+EXPLAIN SELECT STRAIGHT_JOIN t1.a, t2.a, t3.a, t4.a
+FROM t1 LEFT JOIN (t2 JOIN t3 USING(a)) ON t1.a=t3.a, t4
+WHERE t4.a=t1.a;
+
+DROP TABLE t1, t2, t3, t4;
+
+# Test 3. Tests that we do not miss any data due to shortcutting.
+
+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;
+SELECT * FROM t1, t2, t3 WHERE t1.a = t2.a AND t2.b = t3.a AND t1.b = t3.b;
+
+# 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;
+
+# 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;
+
+DROP TABLE t1, t2, t3;
+
+# Test 3b
+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 shortcut 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;
+
+DROP TABLE t1, t2, t3, t4;
+
+# Test 4. Test of execution step.
+# In this test we are testing that a shortcut is properly separated from
+# the case of a normal 'end of records' state on the last table in the plan.
+# This particular case gets hit only when
+# - The optimizer reorders the tables
+# - We have a SELECT <table>.*
+CREATE TABLE t1( a INT );
+CREATE TABLE t2( a INT PRIMARY KEY );
+CREATE TABLE t3( a INT, INDEX( a ) );
+
+INSERT INTO t1( a ) VALUES ( 2 );
+INSERT INTO t1( a ) VALUES ( 2 );
+
+INSERT INTO t2( a ) VALUES ( 1 );
+INSERT INTO t2( a ) VALUES ( 2 );
+
+INSERT INTO t3( a ) VALUES ( 6 );
+INSERT INTO t3( a ) VALUES ( 5 );
+INSERT INTO t3( a ) VALUES ( 2 );
+
+EXPLAIN
+SELECT t2.* FROM t2, t1, t3 WHERE t2.a = t1.a AND t1.a = t3.a;
+SELECT t2.* FROM t2, t1, t3 WHERE t2.a = t1.a AND t1.a = t3.a;
+
+DROP TABLE t1, t2, t3;
+
+# Test 5.
+# Test that a short-cut may still cross a plan node using join buffering.
+CREATE TABLE t1 ( a INT, b INT, c INT );
+INSERT INTO t1 VALUES (1, 1, 2), (-1, -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;
+
+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;
+
+SET explain_shortcuts = 0;
=== modified file 'sql/item.h'
--- a/sql/item.h 2008-05-22 18:40:15 +0000
+++ b/sql/item.h 2008-06-27 09:17:42 +0000
@@ -741,7 +741,18 @@ public:
{ return val_decimal(val); }
virtual bool val_bool_result() { return val_bool(); }
- /* bit map of tables used by item */
+ /**
+ @brief Bitmap of tables used by item.
+
+ Conceptually, this is the set of tables directly referenced by an Item.
+
+ For an Item_field, the set contains simply the table to which the field
+ belongs.
+
+ 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/item_func.cc'
--- a/sql/item_func.cc 2008-04-28 23:00:37 +0000
+++ b/sql/item_func.cc 2008-06-27 09:17:42 +0000
@@ -85,7 +85,7 @@ void Item_func::set_arguments(List<Item>
}
Item_func::Item_func(List<Item> &list)
- :allowed_arg_cols(1)
+ :allowed_arg_cols(1), used_tables_cache(0)
{
set_arguments(list);
}
=== modified file 'sql/item_func.h'
--- a/sql/item_func.h 2008-03-27 19:02:15 +0000
+++ b/sql/item_func.h 2008-06-27 09:17:42 +0000
@@ -61,26 +61,26 @@ public:
enum Type type() const { return FUNC_ITEM; }
virtual enum Functype functype() const { return UNKNOWN_FUNC; }
Item_func(void):
- allowed_arg_cols(1), arg_count(0)
+ allowed_arg_cols(1), arg_count(0), used_tables_cache(0)
{
with_sum_func= 0;
}
Item_func(Item *a):
- allowed_arg_cols(1), arg_count(1)
+ allowed_arg_cols(1), arg_count(1), used_tables_cache(0)
{
args= tmp_arg;
args[0]= a;
with_sum_func= a->with_sum_func;
}
Item_func(Item *a,Item *b):
- allowed_arg_cols(1), arg_count(2)
+ allowed_arg_cols(1), arg_count(2), used_tables_cache(0)
{
args= tmp_arg;
args[0]= a; args[1]= b;
with_sum_func= a->with_sum_func || b->with_sum_func;
}
Item_func(Item *a,Item *b,Item *c):
- allowed_arg_cols(1)
+ allowed_arg_cols(1), used_tables_cache(0)
{
arg_count= 0;
if ((args= (Item**) sql_alloc(sizeof(Item*)*3)))
@@ -91,7 +91,7 @@ public:
}
}
Item_func(Item *a,Item *b,Item *c,Item *d):
- allowed_arg_cols(1)
+ allowed_arg_cols(1), used_tables_cache(0)
{
arg_count= 0;
if ((args= (Item**) sql_alloc(sizeof(Item*)*4)))
@@ -103,7 +103,7 @@ public:
}
}
Item_func(Item *a,Item *b,Item *c,Item *d,Item* e):
- allowed_arg_cols(1)
+ allowed_arg_cols(1), used_tables_cache(0)
{
arg_count= 5;
if ((args= (Item**) sql_alloc(sizeof(Item*)*5)))
=== modified file 'sql/mysqld.cc'
--- a/sql/mysqld.cc 2008-06-11 23:16:53 +0000
+++ b/sql/mysqld.cc 2008-06-27 09:17:42 +0000
@@ -7701,6 +7701,7 @@ static void mysql_init_variables(void)
max_system_variables.ndb_index_stat_cache_entries=~0L;
global_system_variables.ndb_index_stat_update_freq=20;
max_system_variables.ndb_index_stat_update_freq=~0L;
+ max_system_variables.explain_shortcuts=1;
#ifdef HAVE_OPENSSL
have_ssl=SHOW_OPTION_YES;
#else
=== modified file 'sql/set_var.cc'
--- a/sql/set_var.cc 2008-05-21 10:17:29 +0000
+++ b/sql/set_var.cc 2008-06-27 09:17:42 +0000
@@ -247,6 +247,7 @@ static sys_var_event_scheduler sys_event
static sys_var_long_ptr sys_expire_logs_days(&vars, "expire_logs_days",
&expire_logs_days);
+static sys_var_thd_ulong sys_explain_shortcuts(&vars, "explain_shortcuts", &SV::explain_shortcuts);
static sys_var_bool_ptr sys_flush(&vars, "flush", &myisam_flush);
static sys_var_long_ptr sys_flush_time(&vars, "flush_time", &flush_time);
static sys_var_str sys_ft_boolean_syntax(&vars, "ft_boolean_syntax",
=== modified file 'sql/sql_class.h'
--- a/sql/sql_class.h 2008-05-22 18:40:15 +0000
+++ b/sql/sql_class.h 2008-06-27 09:17:42 +0000
@@ -441,7 +441,7 @@ struct system_variables
DATE_TIME_FORMAT *datetime_format;
DATE_TIME_FORMAT *time_format;
my_bool sysdate_is_now;
-
+ ulong explain_shortcuts;
};
@@ -515,7 +515,7 @@ typedef struct system_status_var
sense to add to the /global/ status variable counter.
*/
double last_query_cost;
-
+ ulong explain_shortcuts;
} STATUS_VAR;
=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc 2008-05-31 07:14:57 +0000
+++ b/sql/sql_select.cc 2008-06-27 09:17:42 +0000
@@ -234,6 +234,7 @@ static bool test_if_ref(Item_field *left
static bool replace_where_subcondition(JOIN *join, TABLE_LIST *emb_nest,
Item *old_cond, Item *new_cond,
bool do_fix_fields);
+static void initialize_shortcuts(JOIN *join);
/*
This is used to mark equalities that were made from i-th IN-equality.
@@ -2985,6 +2986,7 @@ mysql_select(THD *thd, Item ***rref_poin
if (thd->is_error())
goto err;
+ initialize_shortcuts(join);
join->exec();
if (thd->cursor && thd->cursor->is_open())
@@ -6855,6 +6857,16 @@ cache_record_length(JOIN *join,uint idx)
return length;
}
+/**
+ @brief Reads the first record from the table belonging to this JOIN_TAB.
+ */
+int JOIN_TAB::do_read_first_record() {
+ join->last_join_tab_accessed= this;
+ int error= (*read_first_record)(this);
+ has_partial_tuple= !error;
+ return error;
+}
+
/*
Get the number of different row combinations for subset of partial join
@@ -10913,6 +10925,85 @@ optimize_cond(JOIN *join, COND *conds, L
DBUG_RETURN(conds);
}
+/**
+ @brief Pre-computes short-cuts for the join short-cut optimization.
+
+ @details This function initialized the field JOIN_TAB::join_shortcut
+ whenever short-cut optimization is applicable. The algorithm is implemented
+ as a nested loop, where the outer loop walks the JOIN_TAB's in the plan,
+ and the inner loop iterates through all tables that this table depends
+ upon. Valid short-cuts have the following property.
+
+ - The short-cut is of 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.
+
+ - If there are several applicable shortcuts by the above requirements, the
+ shortest one is chosen.
+
+ @see JOIN_TAB::join_shortcut.
+ */
+static void initialize_shortcuts(JOIN *join) {
+
+ if(!join->join_tab)
+ return;
+ /*
+ We start searching for short-cuts on the third table, since the minimum
+ length of a short-cut must be 2 steps.
+ */
+ for (uint i= 0; i < join->tables && i < 2; i++)
+ join->join_tab[i].join_shortcut= NULL;
+
+ for (uint i= 2; i < join->tables; i++)
+ {
+ JOIN_TAB *join_tab= &join->join_tab[i];
+ join_tab->join_shortcut= NULL;
+
+ const table_map select_cond_tables= join_tab->select_cond ?
+ join_tab->select_cond->used_tables() : (table_map)0L;
+
+ const table_map all_depenencies=
+ (join_tab->ref.depend_map | select_cond_tables) & ~join_tab->table->map;
+
+ if (all_depenencies == 0)
+ continue;
+
+ /* We iterate through the set by sliding a mask over the bitmap */
+ uint i;
+ table_map mask;
+ for (mask= 1, i= 0; mask <= all_depenencies; mask <<=1, ++i)
+ {
+ if (!(mask & all_depenencies))
+ continue;
+
+ JOIN_TAB *dependency= join->map2table[i];
+
+ if (join_tab > dependency) {
+ bool crosses_outer_join= FALSE;
+ for (JOIN_TAB *jt= dependency; jt < join_tab; ++jt)
+ if (jt->last_inner)
+ {
+ crosses_outer_join= TRUE;
+ break;
+ }
+
+ if (!crosses_outer_join &&
+ (!join_tab->join_shortcut ||
+ join_tab->join_shortcut < dependency) &&
+ join_tab - dependency > 1)
+ join_tab->join_shortcut= dependency;
+ }
+
+ if (dependency == join_tab - 1)
+ join_tab->join_shortcut= NULL;
+
+ }
+ }
+}
+
/**
Remove const and eq items.
@@ -13442,6 +13533,25 @@ sub_select_cache(JOIN *join,JOIN_TAB *jo
*/
int do_sj_reset(SJ_TMP_TABLE *sj_tbl);
+/**
+ @brief Helper function for join the short-cut optimization.
+
+ @details The Nested-loops join implementation is implemented as a number of
+ functions, recursing together. Hence in order to pass control backwards in
+ the plan, the @c return statement is used. But at each recursion level the
+ algorithm has to know whether it is in the middle of short-cut or not.
+
+ @see sub_select, sub_select_cache, flush_cached_records
+ */
+static bool execution_is_within_shortcut(JOIN *join, JOIN_TAB *join_tab)
+{
+ return
+ (uint)(join_tab - join->join_tab) < join->tables - 1 &&
+ join->last_join_tab_accessed->join_shortcut &&
+ !join->last_join_tab_accessed->has_partial_tuple &&
+ join->last_join_tab_accessed->join_shortcut != join_tab;
+}
+
enum_nested_loop_state
sub_select(JOIN *join,JOIN_TAB *join_tab,bool end_of_records)
{
@@ -13486,8 +13596,12 @@ sub_select(JOIN *join,JOIN_TAB *join_tab
}
join->thd->row_count= 0;
- error= (*join_tab->read_first_record)(join_tab);
+ join->last_join_tab_accessed= join_tab;
+ error= join_tab->do_read_first_record();
rc= evaluate_join_record(join, join_tab, error);
+
+ if (execution_is_within_shortcut(join, join_tab))
+ return NESTED_LOOP_OK;
}
/*
@@ -13514,6 +13628,10 @@ sub_select(JOIN *join,JOIN_TAB *join_tab
}
rc= evaluate_join_record(join, join_tab, error);
+
+ if (execution_is_within_shortcut(join, join_tab))
+ return NESTED_LOOP_OK;
+
}
if (rc == NESTED_LOOP_NO_MORE_ROWS &&
@@ -13886,6 +14004,8 @@ flush_cached_records(JOIN *join,JOIN_TAB
!(res= do_sj_dups_weedout(join->thd, join_tab->check_weed_out_table)))
{
rc= (join_tab->next_select)(join,join_tab+1,0);
+ if (execution_is_within_shortcut(join, join_tab))
+ return NESTED_LOOP_OK;
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
{
reset_cache_write(&join_tab->cache);
@@ -18545,6 +18665,31 @@ void JOIN::clear()
}
/**
+ @brief Append information about the short-cut optimization to EXPLAIN
+ output, if it is used for the current plan node.
+
+ @param join The execution plan.
+ @param join_tab The plan node to be annotated.
+ @param extra The current content of the 'extra' column in EXPLAIN.
+*/
+static void append_shortcut_to_explain(JOIN* join, JOIN_TAB *join_tab,
+ String *extra)
+{
+ JOIN_TAB *next_tab= join_tab + 1;
+ if (next_tab >= (join->join_tab + join->tables))
+ // i.e. there is no next join_tab
+ return;
+
+ if (next_tab->join_shortcut && join->thd->variables.explain_shortcuts)
+ {
+ extra->append(STRING_WITH_LEN("; Shortcut("));
+ extra->append(next_tab->join_shortcut->table->alias);
+ extra->append(STRING_WITH_LEN(")"));
+ }
+}
+
+
+/**
EXPLAIN handling.
Send a description about what how the select will be done to stdout.
@@ -18885,6 +19030,7 @@ void select_describe(JOIN *join, bool ne
extra.append(STRING_WITH_LEN("; Using where"));
if (tab->packed_info & TAB_INFO_FULL_SCAN_ON_NULL)
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
+ append_shortcut_to_explain(join, tab, &extra);
/* Skip initial "; "*/
const char *str= extra.ptr();
uint32 len= extra.length();
@@ -19029,6 +19175,7 @@ void select_describe(JOIN *join, bool ne
if (i > 0 && tab[-1].next_select == sub_select_cache)
extra.append(STRING_WITH_LEN("; Using join buffer"));
+ append_shortcut_to_explain(join, tab, &extra);
/* Skip initial "; "*/
const char *str= extra.ptr();
=== modified file 'sql/sql_select.h'
--- a/sql/sql_select.h 2008-05-31 07:14:57 +0000
+++ b/sql/sql_select.h 2008-06-27 09:17:42 +0000
@@ -184,6 +184,17 @@ typedef struct st_join_table {
TABLE *table;
KEYUSE *keyuse; /**< pointer to first used key */
SQL_SELECT *select;
+ /**
+ @brief This field corresponds somewhat to a pushdown condition. It may
+ contain more than just those conditions pushed to the actual table,
+ however.
+
+ @note For the first table in the plan there is usually a select_cond
+ attached but it is not initialized.
+
+ @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.
+ */
COND *select_cond;
QUICK_SELECT_I *quick;
/*
@@ -202,7 +213,31 @@ typedef struct st_join_table {
st_join_table *last_inner; /**< last table table for embedding outer join */
st_join_table *first_upper; /**< first inner table for embedding outer join */
st_join_table *first_unmatched; /**< used for optimization purposes only */
-
+
+ /**
+ @brief Used for join short-cut optimization.
+
+ @details This field is updated in initialize_shortcuts(), right before
+ execution. The requirement for a join short-cut from a table @i t is that:
+
+ - There is no predicate expression (in either @c WHERE clause or join
+ conditions) connecting the table with the table immediately preceding
+ it in the query execution plan.
+
+ - The goal of the short-cut is the last table in the plan to which
+ @i t is connected.
+ */
+ st_join_table *join_shortcut;
+
+ /**
+ @brief True if the last read operation succeeded for this JOIN_TAB.
+
+ @details This field is updated during nested-loops join execution as soon
+ as a read operation is performed. It is set to @c true if the operation
+ succeeded.
+ */
+ bool has_partial_tuple;
+
/* Special content for EXPLAIN 'Extra' column or NULL if none */
const char *info;
/*
@@ -314,6 +349,9 @@ typedef struct st_join_table {
(select->quick->get_type() ==
QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX));
}
+
+ int do_read_first_record();
+
} JOIN_TAB;
enum_nested_loop_state sub_select_cache(JOIN *join, JOIN_TAB *join_tab, bool
@@ -427,6 +465,15 @@ public:
JOIN_TAB *join_tab,**best_ref;
JOIN_TAB **map2table; ///< mapping between table indexes and JOIN_TABs
JOIN_TAB *join_tab_save; ///< saved join_tab for subquery reexecution
+ /**
+ @brief During execution this field contains the JOIN_TAB of the table
+ that was last read from.
+
+ @details This field is kept updated during nested-loops join execution
+ and is set right before reading from the table occurs. Hence it is
+ updated even if the reading caused an error.
+ */
+ JOIN_TAB *last_join_tab_accessed;
TABLE **table,**all_tables;
/**
The table which has an index that allows to produce the requried ordering.
@@ -692,6 +739,7 @@ public:
return (unit == &thd->lex->unit && (unit->fake_select_lex == 0 ||
select_lex == unit->fake_select_lex));
}
+
};
=== modified file 'sql/structs.h'
--- a/sql/structs.h 2008-05-31 07:14:57 +0000
+++ b/sql/structs.h 2008-06-27 09:17:42 +0000
@@ -121,6 +121,38 @@ class THD;
class handler;
struct st_join_table;
+/**
+ @brief Structure responsible for retrieving data during query execution.
+
+ The READ_RECORD could be called a "Record Reader", and acts as
+
+ - An abstraction layer beneath the query execution engine. 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 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 not complete. 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.
+
+*/
typedef struct st_read_record { /* Parameter to read_record */
struct st_table *table; /* Head-form */
handler *file;
=== modified file 'support-files/build-tags'
--- a/support-files/build-tags 2007-02-08 11:56:43 +0000
+++ b/support-files/build-tags 2008-06-27 09:17:42 +0000
@@ -2,7 +2,7 @@
rm -f TAGS
filter='\.cc$\|\.c$\|\.h$\|\.yy\|\.[ch]pp$'
-files=`bk -r sfiles -gU | grep $filter `
+files=`find . | grep $filter `
for f in $files ;
do
etags -o TAGS --append $f
| Thread |
|---|
| • bzr commit into mysql-6.0 branch (mhansson:2652) WL#3724 | Martin Hansson | 27 Jun |
