#At lp:maria based on revid:knielsen@knielsen-hq.org-20090602110359-n4q9gof38buucrny 2708 Sergey Petrunia 2009-06-30 MWL#17: Table elimination - RC0 code added: mysql-test/r/table_elim.result mysql-test/t/table_elim.test sql-bench/test-table-elimination.sh sql/opt_table_elimination.cc modified: libmysqld/Makefile.am mysql-test/r/ps_11bugs.result mysql-test/r/select.result mysql-test/r/subselect.result mysql-test/r/union.result sql/CMakeLists.txt sql/Makefile.am sql/item.cc sql/item.h sql/item_subselect.cc sql/item_subselect.h sql/item_sum.cc sql/item_sum.h sql/sql_lex.cc sql/sql_lex.h sql/sql_select.cc sql/sql_select.h sql/table.h per-file messages: libmysqld/Makefile.am MWL#17: Table elimination - add opt_table_elimination.cc mysql-test/r/ps_11bugs.result MWL#17: Table elimination - Update test results (the difference is because we now recoginze Item_ref(const_item) as const mysql-test/r/select.result MWL#17: Table elimination - Update test results mysql-test/r/subselect.result MWL#17: Table elimination - Update test results (the difference is because we now recoginze Item_ref(const_item) as const mysql-test/r/table_elim.result MWL#17: Table elimination - Testcases mysql-test/r/union.result MWL#17: Table elimination - Update test results (the difference is because we now recoginze Item_ref(const_item) as const mysql-test/t/table_elim.test MWL#17: Table elimination - Testcases sql-bench/test-table-elimination.sh MWL#17: Table elimination - Benchmark which compares table elimination queries with no-table-elimination queries sql/CMakeLists.txt MWL#17: Table elimination - add opt_table_elimination.cc sql/Makefile.am MWL#17: Table elimination - add opt_table_elimination.cc sql/item.cc MWL#17: Table elimination - Add Item_field::check_column_usage_processor sql/item.h MWL#17: Table elimination - Add check_column_usage_processor() sql/item_subselect.cc MWL#17: Table elimination - Make Item_subselect to = be able to tell which particular items are referred from inside the select = to tell whether it was eliminated sql/item_subselect.h MWL#17: Table elimination - Make Item_subselect to = be able to tell which particular items are referred from inside the select = to tell whether it was eliminated sql/item_sum.cc MWL#17: Table elimination - Fix Item_sum_sum::used_tables() to report tables whose columns it really needs sql/item_sum.h MWL#17: Table elimination - Fix Item_sum_sum::used_tables() to report tables whose columns it really needs sql/opt_table_elimination.cc MWL#17: Table elimination - Table elimination Module sql/sql_lex.cc MWL#17: Table elimination - Collect Item_subselect::refers_to attribute sql/sql_lex.h MWL#17: Table elimination - Collect Item_subselect::refers_to attribute sql/sql_select.cc MWL#17: Table elimination - Make KEYUSE array code to also collect/process "binding" equalities in form t.keyXpartY= func(t.keyXpartZ,...) - Call table elimination function - Make EXPLAIN not to show eliminated tables/selects - Added more comments - Move definitions of FT_KEYPART, KEY_OPTIMIZE_* into sql_select.h as they are now used in opt_table_elimination.cc sql/sql_select.h MWL#17: Table elimination - Make KEYUSE array code to also collect/process "binding" equalities in form t.keyXpartY= func(t.keyXpartZ,...) - Call table elimination function - Make EXPLAIN not to show eliminated tables/selects - Added more comments - Move definitions of FT_KEYPART, KEY_OPTIMIZE_* into sql_select.h as they are now used in opt_table_elimination.cc sql/table.h MWL#17: Table elimination - More comments - Add NESTED_JOIN::n_tables === modified file 'libmysqld/Makefile.am' --- a/libmysqld/Makefile.am 2009-03-12 22:27:35 +0000 +++ b/libmysqld/Makefile.am 2009-06-30 15:09:36 +0000 @@ -76,7 +76,7 @@ sqlsources = derror.cc field.cc field_co rpl_filter.cc sql_partition.cc sql_builtin.cc sql_plugin.cc \ sql_tablespace.cc \ rpl_injector.cc my_user.c partition_info.cc \ - sql_servers.cc event_parse_data.cc + sql_servers.cc event_parse_data.cc opt_table_elimination.cc libmysqld_int_a_SOURCES= $(libmysqld_sources) nodist_libmysqld_int_a_SOURCES= $(libmysqlsources) $(sqlsources) === modified file 'mysql-test/r/ps_11bugs.result' --- a/mysql-test/r/ps_11bugs.result 2008-10-08 11:23:53 +0000 +++ b/mysql-test/r/ps_11bugs.result 2009-06-30 15:09:36 +0000 @@ -121,8 +121,8 @@ insert into t1 values (1); explain select * from t1 where 3 in (select (1+1) union select 1); id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables -2 DEPENDENT SUBQUERY NULL NULL NULL NULL NULL NULL NULL No tables used -3 DEPENDENT UNION NULL NULL NULL NULL NULL NULL NULL No tables used +2 DEPENDENT SUBQUERY NULL NULL NULL NULL NULL NULL NULL Impossible HAVING +3 DEPENDENT UNION NULL NULL NULL NULL NULL NULL NULL Impossible HAVING NULL UNION RESULT ALL NULL NULL NULL NULL NULL select * from t1 where 3 in (select (1+1) union select 1); a === modified file 'mysql-test/r/select.result' --- a/mysql-test/r/select.result 2009-03-16 05:02:10 +0000 +++ b/mysql-test/r/select.result 2009-06-30 15:09:36 +0000 @@ -3585,7 +3585,6 @@ INSERT INTO t2 VALUES (1,'a'),(2,'b'),(3 EXPLAIN SELECT t1.a FROM t1 LEFT JOIN t2 ON t2.b=t1.b WHERE t1.a=3; id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t1 const PRIMARY PRIMARY 4 const 1 -1 SIMPLE t2 const b b 22 const 1 Using index DROP TABLE t1,t2; CREATE TABLE t1(id int PRIMARY KEY, b int, e int); CREATE TABLE t2(i int, a int, INDEX si(i), INDEX ai(a)); === modified file 'mysql-test/r/subselect.result' --- a/mysql-test/r/subselect.result 2009-04-25 09:04:38 +0000 +++ b/mysql-test/r/subselect.result 2009-06-30 15:09:36 +0000 @@ -4353,13 +4353,13 @@ id select_type table type possible_keys 1 PRIMARY t1 ALL NULL NULL NULL NULL 2 100.00 2 DEPENDENT SUBQUERY t1 ALL NULL NULL NULL NULL 2 100.00 Using temporary; Using filesort Warnings: -Note 1003 select 1 AS `1` from `test`.`t1` where (1,<exists>(select 1 AS `1` from `test`.`t1` group by `test`.`t1`.`a` having (<cache>(1) = (1)))) +Note 1003 select 1 AS `1` from `test`.`t1` where (1,<exists>(select 1 AS `1` from `test`.`t1` group by `test`.`t1`.`a` having 1)) EXPLAIN EXTENDED SELECT 1 FROM t1 WHERE 1 IN (SELECT 1 FROM t1 WHERE a > 3 GROUP BY a); id select_type table type possible_keys key key_len ref rows filtered Extra 1 PRIMARY NULL NULL NULL NULL NULL NULL NULL NULL Impossible WHERE noticed after reading const tables 2 DEPENDENT SUBQUERY t1 ALL NULL NULL NULL NULL 2 100.00 Using where; Using temporary; Using filesort Warnings: -Note 1003 select 1 AS `1` from `test`.`t1` where (1,<exists>(select 1 AS `1` from `test`.`t1` where (`test`.`t1`.`a` > 3) group by `test`.`t1`.`a` having (<cache>(1) = (1)))) +Note 1003 select 1 AS `1` from `test`.`t1` where (1,<exists>(select 1 AS `1` from `test`.`t1` where (`test`.`t1`.`a` > 3) group by `test`.`t1`.`a` having 1)) DROP TABLE t1; End of 5.0 tests. CREATE TABLE t1 (a INT, b INT); === added file 'mysql-test/r/table_elim.result' --- a/mysql-test/r/table_elim.result 1970-01-01 00:00:00 +0000 +++ b/mysql-test/r/table_elim.result 2009-06-30 15:09:36 +0000 @@ -0,0 +1,204 @@ +drop table if exists t0, t1, t2, t3; +drop view if exists v1, v2; +create table t1 (a int); +insert into t1 values (0),(1),(2),(3); +create table t0 as select * from t1; +create table t2 (a int primary key, b int) +as select a, a as b from t1 where a in (1,2); +create table t3 (a int primary key, b int) +as select a, a as b from t1 where a in (1,3); +# This will be eliminated: +explain select t1.a from t1 left join t2 on t2.a=t1.a; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 4 +explain extended select t1.a from t1 left join t2 on t2.a=t1.a; +id select_type table type possible_keys key key_len ref rows filtered Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 4 100.00 +Warnings: +Note 1003 select `test`.`t1`.`a` AS `a` from `test`.`t1` where 1 +select t1.a from t1 left join t2 on t2.a=t1.a; +a +0 +1 +2 +3 +# This will not be eliminated as t2.b is in in select list: +explain select * from t1 left join t2 on t2.a=t1.a; +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 eq_ref PRIMARY PRIMARY 4 test.t1.a 1 +# This will not be eliminated as t2.b is in in order list: +explain select t1.a from t1 left join t2 on t2.a=t1.a order by t2.b; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 4 Using temporary; Using filesort +1 SIMPLE t2 eq_ref PRIMARY PRIMARY 4 test.t1.a 1 +# This will not be eliminated as t2.b is in group list: +explain select t1.a from t1 left join t2 on t2.a=t1.a group by t2.b; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 4 Using temporary; Using filesort +1 SIMPLE t2 eq_ref PRIMARY PRIMARY 4 test.t1.a 1 +# This will not be eliminated as t2.b is in the WHERE +explain select t1.a from t1 left join t2 on t2.a=t1.a where t2.b < 3 or t2.b is null; +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 eq_ref PRIMARY PRIMARY 4 test.t1.a 1 Using where +# Elimination of multiple tables: +explain select t1.a from t1 left join (t2 join t3) on t2.a=t1.a and t3.a=t1.a; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 4 +# Elimination of multiple tables (2): +explain select t1.a from t1 left join (t2 join t3 on t2.b=t3.b) on t2.a=t1.a and t3.a=t1.a; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 4 +# Elimination when done within an outer join nest: +explain extended +select t0.* +from +t0 left join (t1 left join (t2 join t3 on t2.b=t3.b) on t2.a=t1.a and +t3.a=t1.a) on t0.a=t1.a; +id select_type table type possible_keys key key_len ref rows filtered Extra +1 SIMPLE t0 ALL NULL NULL NULL NULL 4 100.00 +1 SIMPLE t1 ALL NULL NULL NULL NULL 4 100.00 +Warnings: +Note 1003 select `test`.`t0`.`a` AS `a` from `test`.`t0` left join (`test`.`t1`) on((`test`.`t0`.`a` = `test`.`t1`.`a`)) where 1 +# Elimination with aggregate functions +explain select count(*) from t1 left join t2 on t2.a=t1.a; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 4 +explain select count(1) from t1 left join t2 on t2.a=t1.a; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 4 +explain select count(1) from t1 left join t2 on t2.a=t1.a group by t1.a; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 4 Using temporary; Using filesort +This must not use elimination: +explain select count(1) from t1 left join t2 on t2.a=t1.a group by t2.a; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 4 Using temporary; Using filesort +1 SIMPLE t2 eq_ref PRIMARY PRIMARY 4 test.t1.a 1 Using index +drop table t0, t1, t2, t3; +create table t0 ( id integer, primary key (id)); +create table t1 ( +id integer, +attr1 integer, +primary key (id), +key (attr1) +); +create table t2 ( +id integer, +attr2 integer, +fromdate date, +primary key (id, fromdate), +key (attr2,fromdate) +); +insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); +insert into t0 select A.id + 10*B.id from t0 A, t0 B where B.id > 0; +insert into t1 select id, id from t0; +insert into t2 select id, id, date_add('2009-06-22', interval id day) from t0; +insert into t2 select id, id+1, date_add('2008-06-22', interval id day) from t0; +create view v1 as +select +F.id, A1.attr1, A2.attr2 +from +t0 F +left join t1 A1 on A1.id=F.id +left join t2 A2 on A2.id=F.id and +A2.fromdate=(select MAX(fromdate) from +t2 where id=A2.id); +create view v2 as +select +F.id, A1.attr1, A2.attr2 +from +t0 F +left join t1 A1 on A1.id=F.id +left join t2 A2 on A2.id=F.id and +A2.fromdate=(select MAX(fromdate) from +t2 where id=F.id); +This should use one table: +explain select id from v1 where id=2; +id select_type table type possible_keys key key_len ref rows Extra +1 PRIMARY F const PRIMARY PRIMARY 4 const 1 Using index +This should use one table: +explain extended select id from v1 where id in (1,2,3,4); +id select_type table type possible_keys key key_len ref rows filtered Extra +1 PRIMARY F range PRIMARY PRIMARY 4 NULL 4 100.00 Using where; Using index +Warnings: +Note 1276 Field or reference 'test.A2.id' of SELECT #3 was resolved in SELECT #1 +Note 1003 select `F`.`id` AS `id` from `test`.`t0` `F` where (`F`.`id` in (1,2,3,4)) +This should use facts and A1 tables: +explain extended select id from v1 where attr1 between 12 and 14; +id select_type table type possible_keys key key_len ref rows filtered Extra +1 PRIMARY A1 range PRIMARY,attr1 attr1 5 NULL 2 100.00 Using where +1 PRIMARY F eq_ref PRIMARY PRIMARY 4 test.A1.id 1 100.00 Using index +Warnings: +Note 1276 Field or reference 'test.A2.id' of SELECT #3 was resolved in SELECT #1 +Note 1003 select `F`.`id` AS `id` from `test`.`t0` `F` join `test`.`t1` `A1` where ((`F`.`id` = `A1`.`id`) and (`A1`.`attr1` between 12 and 14)) +This should use facts, A2 and its subquery: +explain extended select id from v1 where attr2 between 12 and 14; +id select_type table type possible_keys key key_len ref rows filtered Extra +1 PRIMARY A2 range PRIMARY,attr2 attr2 5 NULL 5 100.00 Using where +1 PRIMARY F eq_ref PRIMARY PRIMARY 4 test.A2.id 1 100.00 Using index +3 DEPENDENT SUBQUERY t2 ref PRIMARY PRIMARY 4 test.A2.id 2 100.00 Using index +Warnings: +Note 1276 Field or reference 'test.A2.id' of SELECT #3 was resolved in SELECT #1 +Note 1003 select `F`.`id` AS `id` from `test`.`t0` `F` join `test`.`t2` `A2` where ((`F`.`id` = `A2`.`id`) and (`A2`.`attr2` between 12 and 14) and (`A2`.`fromdate` = (select max(`test`.`t2`.`fromdate`) AS `MAX(fromdate)` from `test`.`t2` where (`test`.`t2`.`id` = `A2`.`id`)))) +This should use one table: +explain select id from v2 where id=2; +id select_type table type possible_keys key key_len ref rows Extra +1 PRIMARY F const PRIMARY PRIMARY 4 const 1 Using index +This should use one table: +explain extended select id from v2 where id in (1,2,3,4); +id select_type table type possible_keys key key_len ref rows filtered Extra +1 PRIMARY F range PRIMARY PRIMARY 4 NULL 4 100.00 Using where; Using index +Warnings: +Note 1276 Field or reference 'test.F.id' of SELECT #3 was resolved in SELECT #1 +Note 1003 select `F`.`id` AS `id` from `test`.`t0` `F` where (`F`.`id` in (1,2,3,4)) +This should use facts and A1 tables: +explain extended select id from v2 where attr1 between 12 and 14; +id select_type table type possible_keys key key_len ref rows filtered Extra +1 PRIMARY A1 range PRIMARY,attr1 attr1 5 NULL 2 100.00 Using where +1 PRIMARY F eq_ref PRIMARY PRIMARY 4 test.A1.id 1 100.00 Using index +Warnings: +Note 1276 Field or reference 'test.F.id' of SELECT #3 was resolved in SELECT #1 +Note 1003 select `F`.`id` AS `id` from `test`.`t0` `F` join `test`.`t1` `A1` where ((`F`.`id` = `A1`.`id`) and (`A1`.`attr1` between 12 and 14)) +This should use facts, A2 and its subquery: +explain extended select id from v2 where attr2 between 12 and 14; +id select_type table type possible_keys key key_len ref rows filtered Extra +1 PRIMARY A2 range PRIMARY,attr2 attr2 5 NULL 5 100.00 Using where +1 PRIMARY F eq_ref PRIMARY PRIMARY 4 test.A2.id 1 100.00 Using where; Using index +3 DEPENDENT SUBQUERY t2 ref PRIMARY PRIMARY 4 test.F.id 2 100.00 Using index +Warnings: +Note 1276 Field or reference 'test.F.id' of SELECT #3 was resolved in SELECT #1 +Note 1003 select `F`.`id` AS `id` from `test`.`t0` `F` join `test`.`t2` `A2` where ((`F`.`id` = `A2`.`id`) and (`A2`.`attr2` between 12 and 14) and (`A2`.`fromdate` = (select max(`test`.`t2`.`fromdate`) AS `MAX(fromdate)` from `test`.`t2` where (`test`.`t2`.`id` = `F`.`id`)))) +drop view v1, v2; +drop table t0, t1, t2; +create table t1 (a int); +insert into t1 values (0),(1),(2),(3); +create table t2 (pk1 int, pk2 int, pk3 int, col int, primary key(pk1, pk2, pk3)); +insert into t2 select a,a,a,a from t1; +This must use only t1: +explain select t1.* from t1 left join t2 on t2.pk1=t1.a and +t2.pk2=t2.pk1+1 and +t2.pk3=t2.pk2+1; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 4 +This must use only t1: +explain select t1.* from t1 left join t2 on t2.pk1=t1.a and +t2.pk3=t2.pk1+1 and +t2.pk2=t2.pk3+1; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 4 +This must use both: +explain select t1.* from t1 left join t2 on t2.pk1=t1.a and +t2.pk3=t2.pk1+1 and +t2.pk2=t2.pk3+t2.col; +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 PRIMARY PRIMARY 4 test.t1.a 1 +This must use only t1: +explain select t1.* from t1 left join t2 on t2.pk2=t1.a and +t2.pk1=t2.pk2+1 and +t2.pk3=t2.pk1; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 ALL NULL NULL NULL NULL 4 +drop table t1, t2; === modified file 'mysql-test/r/union.result' --- a/mysql-test/r/union.result 2009-03-19 10:18:52 +0000 +++ b/mysql-test/r/union.result 2009-06-30 15:09:36 +0000 @@ -522,7 +522,7 @@ id select_type table type possible_keys 2 UNION t2 const PRIMARY PRIMARY 4 const 1 100.00 NULL UNION RESULT ALL NULL NULL NULL NULL NULL NULL Warnings: -Note 1003 (select '1' AS `a`,'1' AS `b` from `test`.`t1` where ('1' = 1)) union (select '1' AS `a`,'10' AS `b` from `test`.`t2` where ('1' = 1)) +Note 1003 (select '1' AS `a`,'1' AS `b` from `test`.`t1` where 1) union (select '1' AS `a`,'10' AS `b` from `test`.`t2` where 1) (select * from t1 where a=5) union (select * from t2 where a=1); a b 1 10 === added file 'mysql-test/t/table_elim.test' --- a/mysql-test/t/table_elim.test 1970-01-01 00:00:00 +0000 +++ b/mysql-test/t/table_elim.test 2009-06-30 15:09:36 +0000 @@ -0,0 +1,160 @@ +# +# Table elimination (MWL#17) tests +# +--disable_warnings +drop table if exists t0, t1, t2, t3; +drop view if exists v1, v2; +--enable_warnings + +create table t1 (a int); +insert into t1 values (0),(1),(2),(3); +create table t0 as select * from t1; + +create table t2 (a int primary key, b int) + as select a, a as b from t1 where a in (1,2); + +create table t3 (a int primary key, b int) + as select a, a as b from t1 where a in (1,3); + +--echo # This will be eliminated: +explain select t1.a from t1 left join t2 on t2.a=t1.a; +explain extended select t1.a from t1 left join t2 on t2.a=t1.a; + +select t1.a from t1 left join t2 on t2.a=t1.a; + +--echo # This will not be eliminated as t2.b is in in select list: +explain select * from t1 left join t2 on t2.a=t1.a; + +--echo # This will not be eliminated as t2.b is in in order list: +explain select t1.a from t1 left join t2 on t2.a=t1.a order by t2.b; + +--echo # This will not be eliminated as t2.b is in group list: +explain select t1.a from t1 left join t2 on t2.a=t1.a group by t2.b; + +--echo # This will not be eliminated as t2.b is in the WHERE +explain select t1.a from t1 left join t2 on t2.a=t1.a where t2.b < 3 or t2.b is null; + +--echo # Elimination of multiple tables: +explain select t1.a from t1 left join (t2 join t3) on t2.a=t1.a and t3.a=t1.a; + +--echo # Elimination of multiple tables (2): +explain select t1.a from t1 left join (t2 join t3 on t2.b=t3.b) on t2.a=t1.a and t3.a=t1.a; + +--echo # Elimination when done within an outer join nest: +explain extended +select t0.* +from + t0 left join (t1 left join (t2 join t3 on t2.b=t3.b) on t2.a=t1.a and + t3.a=t1.a) on t0.a=t1.a; + +--echo # Elimination with aggregate functions +explain select count(*) from t1 left join t2 on t2.a=t1.a; +explain select count(1) from t1 left join t2 on t2.a=t1.a; +explain select count(1) from t1 left join t2 on t2.a=t1.a group by t1.a; + +--echo This must not use elimination: +explain select count(1) from t1 left join t2 on t2.a=t1.a group by t2.a; + +drop table t0, t1, t2, t3; + +# This will stand for elim_facts +create table t0 ( id integer, primary key (id)); + +# Attribute1, non-versioned +create table t1 ( + id integer, + attr1 integer, + primary key (id), + key (attr1) +); + +# Attribute2, time-versioned +create table t2 ( + id integer, + attr2 integer, + fromdate date, + primary key (id, fromdate), + key (attr2,fromdate) +); + +insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); +insert into t0 select A.id + 10*B.id from t0 A, t0 B where B.id > 0; + +insert into t1 select id, id from t0; +insert into t2 select id, id, date_add('2009-06-22', interval id day) from t0; +insert into t2 select id, id+1, date_add('2008-06-22', interval id day) from t0; + +create view v1 as +select + F.id, A1.attr1, A2.attr2 +from + t0 F + left join t1 A1 on A1.id=F.id + left join t2 A2 on A2.id=F.id and + A2.fromdate=(select MAX(fromdate) from + t2 where id=A2.id); +create view v2 as +select + F.id, A1.attr1, A2.attr2 +from + t0 F + left join t1 A1 on A1.id=F.id + left join t2 A2 on A2.id=F.id and + A2.fromdate=(select MAX(fromdate) from + t2 where id=F.id); + +--echo This should use one table: +explain select id from v1 where id=2; +--echo This should use one table: +explain extended select id from v1 where id in (1,2,3,4); +--echo This should use facts and A1 tables: +explain extended select id from v1 where attr1 between 12 and 14; +--echo This should use facts, A2 and its subquery: +explain extended select id from v1 where attr2 between 12 and 14; + +# Repeat for v2: + +--echo This should use one table: +explain select id from v2 where id=2; +--echo This should use one table: +explain extended select id from v2 where id in (1,2,3,4); +--echo This should use facts and A1 tables: +explain extended select id from v2 where attr1 between 12 and 14; +--echo This should use facts, A2 and its subquery: +explain extended select id from v2 where attr2 between 12 and 14; + +drop view v1, v2; +drop table t0, t1, t2; + +# +# Tests for the code that uses t.keypartX=func(t.keypartY) equalities to +# make table elimination inferences +# +create table t1 (a int); +insert into t1 values (0),(1),(2),(3); + +create table t2 (pk1 int, pk2 int, pk3 int, col int, primary key(pk1, pk2, pk3)); +insert into t2 select a,a,a,a from t1; + +--echo This must use only t1: +explain select t1.* from t1 left join t2 on t2.pk1=t1.a and + t2.pk2=t2.pk1+1 and + t2.pk3=t2.pk2+1; + +--echo This must use only t1: +explain select t1.* from t1 left join t2 on t2.pk1=t1.a and + t2.pk3=t2.pk1+1 and + t2.pk2=t2.pk3+1; + +--echo This must use both: +explain select t1.* from t1 left join t2 on t2.pk1=t1.a and + t2.pk3=t2.pk1+1 and + t2.pk2=t2.pk3+t2.col; + +--echo This must use only t1: +explain select t1.* from t1 left join t2 on t2.pk2=t1.a and + t2.pk1=t2.pk2+1 and + t2.pk3=t2.pk1; + +drop table t1, t2; + === added file 'sql-bench/test-table-elimination.sh' --- a/sql-bench/test-table-elimination.sh 1970-01-01 00:00:00 +0000 +++ b/sql-bench/test-table-elimination.sh 2009-06-30 15:09:36 +0000 @@ -0,0 +1,320 @@ +#!@PERL@ +# Test of table elimination feature + +use Cwd; +use DBI; +use Getopt::Long; +use Benchmark; + +$opt_loop_count=100000; +$opt_medium_loop_count=10000; +$opt_small_loop_count=100; + +$pwd = cwd(); $pwd = "." if ($pwd eq ''); +require "$pwd/bench-init.pl" || die "Can't read Configuration file: $!\n"; + +if ($opt_small_test) +{ + $opt_loop_count/=10; + $opt_medium_loop_count/=10; + $opt_small_loop_count/=10; +} + +print "Testing table elimination feature\n"; +print "The test table has $opt_loop_count rows.\n\n"; + +# A query to get the recent versions of all attributes: +$select_current_full_facts=" + select + F.id, A1.attr1, A2.attr2 + from + elim_facts F + left join elim_attr1 A1 on A1.id=F.id + left join elim_attr2 A2 on A2.id=F.id and + A2.fromdate=(select MAX(fromdate) from + elim_attr2 where id=A2.id); +"; +$select_current_full_facts=" + select + F.id, A1.attr1, A2.attr2 + from + elim_facts F + left join elim_attr1 A1 on A1.id=F.id + left join elim_attr2 A2 on A2.id=F.id and + A2.fromdate=(select MAX(fromdate) from + elim_attr2 where id=F.id); +"; +# TODO: same as above but for some given date also? +# TODO: + + +#### +#### Connect and start timeing +#### + +$dbh = $server->connect(); +$start_time=new Benchmark; + +#### +#### Create needed tables +#### + +goto select_test if ($opt_skip_create); + +print "Creating tables\n"; +$dbh->do("drop table elim_facts" . $server->{'drop_attr'}); +$dbh->do("drop table elim_attr1" . $server->{'drop_attr'}); +$dbh->do("drop table elim_attr2" . $server->{'drop_attr'}); + +# The facts table +do_many($dbh,$server->create("elim_facts", + ["id integer"], + ["primary key (id)"])); + +# Attribute1, non-versioned +do_many($dbh,$server->create("elim_attr1", + ["id integer", + "attr1 integer"], + ["primary key (id)", + "key (attr1)"])); + +# Attribute2, time-versioned +do_many($dbh,$server->create("elim_attr2", + ["id integer", + "attr2 integer", + "fromdate date"], + ["primary key (id, fromdate)", + "key (attr2,fromdate)"])); + +#NOTE: ignoring: if ($limits->{'views'}) +$dbh->do("drop view elim_current_facts"); +$dbh->do("create view elim_current_facts as $select_current_full_facts"); + +if ($opt_lock_tables) +{ + do_query($dbh,"LOCK TABLES elim_facts, elim_attr1, elim_attr2 WRITE"); +} + +if ($opt_fast && defined($server->{vacuum})) +{ + $server->vacuum(1,\$dbh); +} + +#### +#### Fill the facts table +#### +$n_facts= $opt_loop_count; + +if ($opt_fast && $server->{transactions}) +{ + $dbh->{AutoCommit} = 0; +} + +print "Inserting $n_facts rows into facts table\n"; +$loop_time=new Benchmark; + +$query="insert into elim_facts values ("; +for ($id=0; $id < $n_facts ; $id++) +{ + do_query($dbh,"$query $id)"); +} + +if ($opt_fast && $server->{transactions}) +{ + $dbh->commit; + $dbh->{AutoCommit} = 1; +} + +$end_time=new Benchmark; +print "Time to insert ($n_facts): " . + timestr(timediff($end_time, $loop_time),"all") . "\n\n"; + +#### +#### Fill attr1 table +#### +if ($opt_fast && $server->{transactions}) +{ + $dbh->{AutoCommit} = 0; +} + +print "Inserting $n_facts rows into attr1 table\n"; +$loop_time=new Benchmark; + +$query="insert into elim_attr1 values ("; +for ($id=0; $id < $n_facts ; $id++) +{ + $attr1= ceil(rand($n_facts)); + do_query($dbh,"$query $id, $attr1)"); +} + +if ($opt_fast && $server->{transactions}) +{ + $dbh->commit; + $dbh->{AutoCommit} = 1; +} + +$end_time=new Benchmark; +print "Time to insert ($n_facts): " . + timestr(timediff($end_time, $loop_time),"all") . "\n\n"; + +#### +#### Fill attr2 table +#### +if ($opt_fast && $server->{transactions}) +{ + $dbh->{AutoCommit} = 0; +} + +print "Inserting $n_facts rows into attr2 table\n"; +$loop_time=new Benchmark; + +for ($id=0; $id < $n_facts ; $id++) +{ + # Two values for each $id - current one and obsolete one. + $attr1= ceil(rand($n_facts)); + $query="insert into elim_attr2 values ($id, $attr1, now())"; + do_query($dbh,$query); + $query="insert into elim_attr2 values ($id, $attr1, '2009-01-01')"; + do_query($dbh,$query); +} + +if ($opt_fast && $server->{transactions}) +{ + $dbh->commit; + $dbh->{AutoCommit} = 1; +} + +$end_time=new Benchmark; +print "Time to insert ($n_facts): " . + timestr(timediff($end_time, $loop_time),"all") . "\n\n"; + +#### +#### Finalize the database population +#### + +if ($opt_lock_tables) +{ + do_query($dbh,"UNLOCK TABLES"); +} + +if ($opt_fast && defined($server->{vacuum})) +{ + $server->vacuum(0,\$dbh,["elim_facts", "elim_attr1", "elim_attr2"]); +} + +if ($opt_lock_tables) +{ + do_query($dbh,"LOCK TABLES elim_facts, elim_attr1, elim_attr2 WRITE"); +} + +#### +#### Do some selects on the table +#### + +select_test: + +# +# The selects will be: +# - N pk-lookups with all attributes +# - pk-attribute-based lookup +# - latest-attribute value based lookup. + + +### +### Bare facts select: +### +print "testing bare facts facts table\n"; +$loop_time=new Benchmark; +$rows=0; +for ($i=0 ; $i < $opt_medium_loop_count ; $i++) +{ + $val= ceil(rand($n_facts)); + $rows+=fetch_all_rows($dbh,"select * from elim_facts where id=$val"); +} +$count=$i; + +$end_time=new Benchmark; +print "time for select_bare_facts ($count:$rows): " . + timestr(timediff($end_time, $loop_time),"all") . "\n"; + + +### +### Full facts select, no elimination: +### +print "testing full facts facts table\n"; +$loop_time=new Benchmark; +$rows=0; +for ($i=0 ; $i < $opt_medium_loop_count ; $i++) +{ + $val= rand($n_facts); + $rows+=fetch_all_rows($dbh,"select * from elim_current_facts where id=$val"); +} +$count=$i; + +$end_time=new Benchmark; +print "time for select_two_attributes ($count:$rows): " . + timestr(timediff($end_time, $loop_time),"all") . "\n"; + +### +### Now with elimination: select only only one fact +### +print "testing selection of one attribute\n"; +$loop_time=new Benchmark; +$rows=0; +for ($i=0 ; $i < $opt_medium_loop_count ; $i++) +{ + $val= rand($n_facts); + $rows+=fetch_all_rows($dbh,"select id, attr1 from elim_current_facts where id=$val"); +} +$count=$i; + +$end_time=new Benchmark; +print "time for select_one_attribute ($count:$rows): " . + timestr(timediff($end_time, $loop_time),"all") . "\n"; + +### +### Now with elimination: select only only one fact +### +print "testing selection of one attribute\n"; +$loop_time=new Benchmark; +$rows=0; +for ($i=0 ; $i < $opt_medium_loop_count ; $i++) +{ + $val= rand($n_facts); + $rows+=fetch_all_rows($dbh,"select id, attr2 from elim_current_facts where id=$val"); +} +$count=$i; + +$end_time=new Benchmark; +print "time for select_one_attribute ($count:$rows): " . + timestr(timediff($end_time, $loop_time),"all") . "\n"; + + +### +### TODO... +### + +; + +#### +#### End of benchmark +#### + +if ($opt_lock_tables) +{ + do_query($dbh,"UNLOCK TABLES"); +} +if (!$opt_skip_delete) +{ + do_query($dbh,"drop table elim_facts, elim_attr1, elim_attr2" . $server->{'drop_attr'}); +} + +if ($opt_fast && defined($server->{vacuum})) +{ + $server->vacuum(0,\$dbh); +} + +$dbh->disconnect; # close connection + +end_benchmark($start_time); + === modified file 'sql/CMakeLists.txt' --- a/sql/CMakeLists.txt 2008-11-21 14:21:50 +0000 +++ b/sql/CMakeLists.txt 2009-06-30 15:09:36 +0000 @@ -73,7 +73,7 @@ ADD_EXECUTABLE(mysqld partition_info.cc rpl_utility.cc rpl_injector.cc sql_locale.cc rpl_rli.cc rpl_mi.cc sql_servers.cc sql_connect.cc scheduler.cc - sql_profile.cc event_parse_data.cc + sql_profile.cc event_parse_data.cc opt_table_elimination.cc ${PROJECT_SOURCE_DIR}/sql/sql_yacc.cc ${PROJECT_SOURCE_DIR}/sql/sql_yacc.h ${PROJECT_SOURCE_DIR}/include/mysqld_error.h === modified file 'sql/Makefile.am' --- a/sql/Makefile.am 2009-03-12 22:27:35 +0000 +++ b/sql/Makefile.am 2009-06-30 15:09:36 +0000 @@ -121,7 +121,8 @@ mysqld_SOURCES = sql_lex.cc sql_handler. event_queue.cc event_db_repository.cc events.cc \ sql_plugin.cc sql_binlog.cc \ sql_builtin.cc sql_tablespace.cc partition_info.cc \ - sql_servers.cc event_parse_data.cc + sql_servers.cc event_parse_data.cc \ + opt_table_elimination.cc nodist_mysqld_SOURCES = mini_client_errors.c pack.c client.c my_time.c my_user.c === modified file 'sql/item.cc' --- a/sql/item.cc 2009-04-25 10:05:32 +0000 +++ b/sql/item.cc 2009-06-30 15:09:36 +0000 @@ -1915,6 +1915,37 @@ void Item_field::reset_field(Field *f) name= (char*) f->field_name; } + +bool Item_field::check_column_usage_processor(uchar *arg) +{ + Field_processor_info* info=(Field_processor_info*)arg; + + if (field->table == info->table) + { + /* It is not ok to use columns that are not part of the key of interest: */ + if (!(field->part_of_key.is_set(info->keyno))) + return TRUE; + + /* Find which key part we're using and mark it in needed_key_parts */ + KEY *key= &field->table->key_info[info->keyno]; + for (uint part= 0; part < key->key_parts; part++) + { + if (field->field_index == key->key_part[part].field->field_index) + { + if (part == info->forbidden_part) + return TRUE; + info->needed_key_parts |= key_part_map(1) << part; + break; + } + } + return FALSE; + } + else + info->used_tables |= this->used_tables(); + return FALSE; +} + + const char *Item_ident::full_name() const { char *tmp; @@ -3380,7 +3411,7 @@ static void mark_as_dependent(THD *thd, /* store pointer on SELECT_LEX from which item is dependent */ if (mark_item) mark_item->depended_from= last; - current->mark_as_dependent(last); + current->mark_as_dependent(last, resolved_item); if (thd->lex->describe & DESCRIBE_EXTENDED) { char warn_buff[MYSQL_ERRMSG_SIZE]; === modified file 'sql/item.h' --- a/sql/item.h 2009-04-25 10:05:32 +0000 +++ b/sql/item.h 2009-06-30 15:09:36 +0000 @@ -731,7 +731,11 @@ public: virtual bool val_bool_result() { return val_bool(); } virtual bool is_null_result() { return is_null(); } - /* bit map of tables used by item */ + /* + Bitmap of tables used by item + (note: if you need to check dependencies on individual columns, check out + check_column_usage_processor) + */ virtual table_map used_tables() const { return (table_map) 0L; } /* Return table map of tables that can't be NULL tables (tables that are @@ -888,6 +892,8 @@ public: virtual bool reset_query_id_processor(uchar *query_id_arg) { return 0; } virtual bool is_expensive_processor(uchar *arg) { return 0; } virtual bool register_field_in_read_map(uchar *arg) { return 0; } + virtual bool check_column_usage_processor(uchar *arg) { return 0; } + virtual bool mark_as_eliminated_processor(uchar *arg) { return 0; } /* Check if a partition function is allowed SYNOPSIS @@ -1011,6 +1017,18 @@ public: bool eq_by_collation(Item *item, bool binary_cmp, CHARSET_INFO *cs); }; +/* Data for Item::check_column_usage_processor */ +typedef struct +{ + TABLE *table; /* Table of interest */ + uint keyno; /* Index of interest */ + uint forbidden_part; /* key part which one is not allowed to refer to */ + /* [Set by processor] used tables, besides the table of interest */ + table_map used_tables; + /* [Set by processor] Parts of index of interest that expression refers to */ + uint needed_key_parts; +} Field_processor_info; + class sp_head; @@ -1477,6 +1495,7 @@ public: bool find_item_in_field_list_processor(uchar *arg); bool register_field_in_read_map(uchar *arg); bool check_partition_func_processor(uchar *int_arg) {return FALSE;} + bool check_column_usage_processor(uchar *arg); void cleanup(); bool result_as_longlong() { @@ -2203,6 +2222,10 @@ public: if (!depended_from) (*ref)->update_used_tables(); } + bool const_item() const + { + return (*ref)->const_item(); + } table_map not_null_tables() const { return (*ref)->not_null_tables(); } void set_result_field(Field *field) { result_field= field; } bool is_result_field() { return 1; } === modified file 'sql/item_subselect.cc' --- a/sql/item_subselect.cc 2009-01-31 21:22:44 +0000 +++ b/sql/item_subselect.cc 2009-06-30 15:09:36 +0000 @@ -39,7 +39,7 @@ inline Item * and_items(Item* cond, Item Item_subselect::Item_subselect(): Item_result_field(), value_assigned(0), thd(0), substitution(0), engine(0), old_engine(0), used_tables_cache(0), have_to_be_excluded(0), - const_item_cache(1), engine_changed(0), changed(0), is_correlated(FALSE) + const_item_cache(1), in_fix_fields(0), engine_changed(0), changed(0), is_correlated(FALSE) { with_subselect= 1; reset(); @@ -151,10 +151,14 @@ bool Item_subselect::fix_fields(THD *thd DBUG_ASSERT(fixed == 0); engine->set_thd((thd= thd_param)); + if (!in_fix_fields) + refers_to.empty(); + eliminated= FALSE; if (check_stack_overrun(thd, STACK_MIN_SIZE, (uchar*)&res)) return TRUE; - + + in_fix_fields++; res= engine->prepare(); // all transformation is done (used by prepared statements) @@ -181,12 +185,14 @@ bool Item_subselect::fix_fields(THD *thd if (!(*ref)->fixed) ret= (*ref)->fix_fields(thd, ref); thd->where= save_where; + in_fix_fields--; return ret; } // Is it one field subselect? if (engine->cols() > max_columns) { my_error(ER_OPERAND_COLUMNS, MYF(0), 1); + in_fix_fields--; return TRUE; } fix_length_and_dec(); @@ -203,11 +209,30 @@ bool Item_subselect::fix_fields(THD *thd fixed= 1; err: + in_fix_fields--; thd->where= save_where; return res; } +bool Item_subselect::check_column_usage_processor(uchar *arg) +{ + List_iterator<Item> it(refers_to); + Item *item; + while ((item= it++)) + { + if (item->walk(&Item::check_column_usage_processor,FALSE, arg)) + return TRUE; + } + return FALSE; +} + +bool Item_subselect::mark_as_eliminated_processor(uchar *arg) +{ + eliminated= TRUE; + return FALSE; +} + bool Item_subselect::walk(Item_processor processor, bool walk_subquery, uchar *argument) { @@ -225,6 +250,7 @@ bool Item_subselect::walk(Item_processor if (lex->having && (lex->having)->walk(processor, walk_subquery, argument)) return 1; + /* TODO: why does this walk WHERE/HAVING but not ON expressions of outer joins? */ while ((item=li++)) { === modified file 'sql/item_subselect.h' --- a/sql/item_subselect.h 2008-02-22 10:30:33 +0000 +++ b/sql/item_subselect.h 2009-06-30 15:09:36 +0000 @@ -52,8 +52,16 @@ protected: bool have_to_be_excluded; /* cache of constant state */ bool const_item_cache; - + public: + /* + References from inside the subquery to the select that this predicate is + in. References to parent selects not included. + */ + List<Item> refers_to; + int in_fix_fields; + bool eliminated; + /* changed engine indicator */ bool engine_changed; /* subquery is transformed */ @@ -126,6 +134,8 @@ public: virtual void reset_value_registration() {} enum_parsing_place place() { return parsing_place; } bool walk(Item_processor processor, bool walk_subquery, uchar *arg); + bool mark_as_eliminated_processor(uchar *arg); + bool check_column_usage_processor(uchar *arg); /** Get the SELECT_LEX structure associated with this Item. === modified file 'sql/item_sum.cc' --- a/sql/item_sum.cc 2009-04-25 09:04:38 +0000 +++ b/sql/item_sum.cc 2009-06-30 15:09:36 +0000 @@ -350,7 +350,7 @@ bool Item_sum::register_sum_func(THD *th sl= sl->master_unit()->outer_select() ) sl->master_unit()->item->with_sum_func= 1; } - thd->lex->current_select->mark_as_dependent(aggr_sel); + thd->lex->current_select->mark_as_dependent(aggr_sel, NULL); return FALSE; } @@ -542,11 +542,6 @@ void Item_sum::update_used_tables () args[i]->update_used_tables(); used_tables_cache|= args[i]->used_tables(); } - - used_tables_cache&= PSEUDO_TABLE_BITS; - - /* the aggregate function is aggregated into its local context */ - used_tables_cache |= (1 << aggr_sel->join->tables) - 1; } } === modified file 'sql/item_sum.h' --- a/sql/item_sum.h 2008-12-09 19:43:10 +0000 +++ b/sql/item_sum.h 2009-06-30 15:09:36 +0000 @@ -255,6 +255,12 @@ protected: */ Item **orig_args, *tmp_orig_args[2]; table_map used_tables_cache; + + /* + TRUE <=> We've managed to calculate the value of this Item in + opt_sum_query(), hence it can be considered constant at all subsequent + steps. + */ bool forced_const; public: @@ -341,6 +347,15 @@ public: virtual const char *func_name() const= 0; virtual Item *result_item(Field *field) { return new Item_field(field); } + /* + Return bitmap of tables that are needed to evaluate the item. + + The implementation takes into account the used strategy: items resolved + at optimization phase will report 0. + Items that depend on the number of join output records, but not columns + of any particular table (like COUNT(*)) will report 0 from used_tables(), + but will still return false from const_item(). + */ table_map used_tables() const { return used_tables_cache; } void update_used_tables (); void cleanup() === added file 'sql/opt_table_elimination.cc' --- a/sql/opt_table_elimination.cc 1970-01-01 00:00:00 +0000 +++ b/sql/opt_table_elimination.cc 2009-06-30 15:09:36 +0000 @@ -0,0 +1,494 @@ +/** + @file + + @brief + Table Elimination Module + + @defgroup Table_Elimination Table Elimination Module + @{ +*/ + +#ifdef USE_PRAGMA_IMPLEMENTATION +#pragma implementation // gcc: Class implementation +#endif + +#include "mysql_priv.h" +#include "sql_select.h" + +/* + OVERVIEW + + The module has one entry point - eliminate_tables() function, which one + needs to call (once) sometime after update_ref_and_keys() but before the + join optimization. + eliminate_tables() operates over the JOIN structures. Logically, it + removes the right sides of outer join nests. Physically, it changes the + following members: + + * Eliminated tables are marked as constant and moved to the front of the + join order. + * In addition to this, they are recorded in JOIN::eliminated_tables bitmap. + + * All join nests have their NESTED_JOIN::n_tables updated to discount + the eliminated tables + + * Items that became disused because they were in the ON expression of an + eliminated outer join are notified by means of the Item tree walk which + calls Item::mark_as_eliminated_processor for every item + - At the moment the only Item that cares is Item_subselect with its + Item_subselect::eliminated flag which is used by EXPLAIN code to + check if the subquery should be shown in EXPLAIN. + + Table elimination is redone on every PS re-execution. +*/ + +static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl); +static bool table_has_one_match(TABLE *table, table_map bound_tables, + bool *multiple_matches); +static uint +eliminate_tables_for_list(JOIN *join, TABLE **leaves_arr, + List *join_list, + bool its_outer_join, + table_map tables_in_list, + table_map tables_used_elsewhere, + bool *multiple_matches); +static bool +extra_keyuses_bind_all_keyparts(table_map bound_tables, TABLE *table, + KEYUSE *key_start, KEYUSE *key_end, + uint n_keyuses, table_map bound_parts); + +/* + Perform table elimination + + SYNOPSIS + eliminate_tables() + join Join to work on + const_tbl_count INOUT Number of constant tables (this includes + eliminated tables) + const_tables INOUT Bitmap of constant tables + + DESCRIPTION + This function is the entry point for table elimination. + The idea behind table elimination is that if we have an outer join: + + SELECT * FROM t1 LEFT JOIN + (t2 JOIN t3) ON t3.primary_key=t1.col AND + t4.primary_key=t2.col + such that + + 1. columns of the inner tables are not used anywhere ouside the outer + join (not in WHERE, not in GROUP/ORDER BY clause, not in select list + etc etc), and + 2. inner side of the outer join is guaranteed to produce at most one + record combination for each record combination of outer tables. + + then the inner side of the outer join can be removed from the query. + This is because it will always produce one matching record (either a + real match or a NULL-complemented record combination), and since there + are no references to columns of the inner tables anywhere, it doesn't + matter which record combination it was. + + This function primary handles checking #1. It collects a bitmap of + tables that are not used in select list/GROUP BY/ORDER BY/HAVING/etc and + thus can possibly be eliminated. + + SIDE EFFECTS + See the OVERVIEW section at the top of this file. + +*/ + +void eliminate_tables(JOIN *join) +{ + Item *item; + table_map used_tables; + DBUG_ENTER("eliminate_tables"); + + DBUG_ASSERT(join->eliminated_tables == 0); + + /* If there are no outer joins, we have nothing to eliminate: */ + if (!join->outer_join) + DBUG_VOID_RETURN; + + /* Find the tables that are referred to from WHERE/HAVING */ + used_tables= (join->conds? join->conds->used_tables() : 0) | + (join->having? join->having->used_tables() : 0); + + /* Add tables referred to from the select list */ + List_iterator<Item> it(join->fields_list); + while ((item= it++)) + used_tables |= item->used_tables(); + + /* Add tables referred to from ORDER BY and GROUP BY lists */ + ORDER *all_lists[]= { join->order, join->group_list}; + for (int i=0; i < 2; i++) + { + for (ORDER *cur_list= all_lists[i]; cur_list; cur_list= cur_list->next) + used_tables |= (*(cur_list->item))->used_tables(); + } + + THD* thd= join->thd; + if (join->select_lex == &thd->lex->select_lex) + { + /* Multi-table UPDATE and DELETE: don't eliminate the tables we modify: */ + used_tables |= thd->table_map_for_update; + + /* Multi-table UPDATE: don't eliminate tables referred from SET statement */ + if (thd->lex->sql_command == SQLCOM_UPDATE_MULTI) + { + List_iterator<Item> it2(thd->lex->value_list); + while ((item= it2++)) + used_tables |= item->used_tables(); + } + } + + table_map all_tables= join->all_tables_map(); + if (all_tables & ~used_tables) + { + /* There are some tables that we probably could eliminate. Try it. */ + TABLE *leaves_array[MAX_TABLES]; + bool multiple_matches= FALSE; + eliminate_tables_for_list(join, leaves_array, join->join_list, FALSE, + all_tables, used_tables, &multiple_matches); + } + DBUG_VOID_RETURN; +} + +/* + Perform table elimination in a given join list + + SYNOPSIS + eliminate_tables_for_list() + join The join + leaves_arr OUT Store here an array of leaf (base) tables that + are descendants of the join_list, and increment + the pointer to point right above the array. + join_list Join list to work on + its_outer_join TRUE <=> join_list is an inner side of an outer + join + FALSE <=> otherwise (this is top-level join list) + tables_in_list Bitmap of tables embedded in the join_list. + tables_used_elsewhere Bitmap of tables that are referred to from + somewhere outside of the join list (e.g. + select list, HAVING, etc). + + DESCRIPTION + Perform table elimination for a join list. + Try eliminating children nests first. + The "all tables in join nest can produce only one matching record + combination" property checking is modeled after constant table detection, + plus we reuse info attempts to eliminate child join nests. + + RETURN + Number of children left after elimination. 0 means everything was + eliminated. +*/ +static uint +eliminate_tables_for_list(JOIN *join, TABLE **leaves_arr, + List *join_list, + bool its_outer_join, + table_map tables_in_list, + table_map tables_used_elsewhere, + bool *multiple_matches) +{ + TABLE_LIST *tbl; + List_iterator it(*join_list); + table_map tables_used_on_left= 0; + TABLE **cur_table= leaves_arr; + bool children_have_multiple_matches= FALSE; + uint remaining_children= 0; + + while ((tbl= it++)) + { + if (tbl->on_expr) + { + table_map outside_used_tables= tables_used_elsewhere | + tables_used_on_left; + bool multiple_matches= FALSE; + if (tbl->nested_join) + { + /* This is "... LEFT JOIN (join_nest) ON cond" */ + uint n; + if (!(n= eliminate_tables_for_list(join, cur_table, + &tbl->nested_join->join_list, TRUE, + tbl->nested_join->used_tables, + outside_used_tables, + &multiple_matches))) + { + mark_as_eliminated(join, tbl); + } + else + remaining_children++; + tbl->nested_join->n_tables= n; + } + else + { + /* This is "... LEFT JOIN tbl ON cond" */ + if (!(tbl->table->map & outside_used_tables) && + table_has_one_match(tbl->table, join->all_tables_map(), + &multiple_matches)) + { + mark_as_eliminated(join, tbl); + } + else + remaining_children++; + } + tables_used_on_left |= tbl->on_expr->used_tables(); + children_have_multiple_matches= children_have_multiple_matches || + multiple_matches; + } + else + { + DBUG_ASSERT(!tbl->nested_join); + remaining_children++; + } + + if (tbl->table) + *(cur_table++)= tbl->table; + } + + *multiple_matches |= children_have_multiple_matches; + + /* Try eliminating the nest we're called for */ + if (its_outer_join && !children_have_multiple_matches && + !(tables_in_list & tables_used_elsewhere)) + { + table_map bound_tables= join->const_table_map | (join->all_tables_map() & + ~tables_in_list); + table_map old_bound_tables; + TABLE **leaves_end= cur_table; + /* + Do the same as const table search table: try to expand the set of bound + tables until it covers all tables in the join_list + */ + do + { + old_bound_tables= bound_tables; + for (cur_table= leaves_arr; cur_table != leaves_end; cur_table++) + { + if (!((*cur_table)->map & join->eliminated_tables) && + table_has_one_match(*cur_table, bound_tables, multiple_matches)) + { + bound_tables |= (*cur_table)->map; + } + } + } while (old_bound_tables != bound_tables); + + if (!(tables_in_list & ~bound_tables)) + { + /* + This join_list can be eliminated. Signal about this to the caller by + returning number of tables. + */ + remaining_children= 0; + } + } + return remaining_children; +} + + +/* + Check if the table will produce at most one matching record + + SYNOPSIS + table_has_one_match() + table The [base] table being checked + bound_tables Tables that should be considered bound. + multiple_matches OUT Set to TRUE when there is no way we could + find find a limitation that would give us one-match + property. + + DESCRIPTION + Check if table will produce at most one matching record for each record + combination of tables in bound_tables bitmap. + + The check is based on ref analysis data, KEYUSE structures. We're + handling two cases: + + 1. Table has a UNIQUE KEY(uk_col_1, ... uk_col_N), and for each uk_col_i + there is a KEYUSE that represents a limitation in form + + table.uk_col_i = func(bound_tables) (X) + + 2. Same as above but we also handle limitations in form + + table.uk_col_i = func(bound_tables, uk_col_j1, ... uk_col_j2) (XX) + + where values of uk_col_jN are known to be bound because for them we + have an equality of form (X) or (XX). + + RETURN + TRUE Yes, at most one match + FALSE No +*/ + +static bool table_has_one_match(TABLE *table, table_map bound_tables, + bool *multiple_matches) +{ + KEYUSE *keyuse= table->reginfo.join_tab->keyuse; + if (keyuse) + { + while (keyuse->table == table) + { + uint key= keyuse->key; + key_part_map bound_parts=0; + uint n_unusable=0; + bool ft_key= test(keyuse->keypart == FT_KEYPART); + KEY *keyinfo= table->key_info + key; + KEYUSE *key_start = keyuse; + + do /* For each keypart and each way to read it */ + { + if (keyuse->type == KEYUSE_USABLE) + { + if(!(keyuse->used_tables & ~bound_tables) && + !(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)) + { + bound_parts |= keyuse->keypart_map; + } + } + else + n_unusable++; + keyuse++; + } while (keyuse->table == table && keyuse->key == key); + + if (ft_key || ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) + != HA_NOSAME)) + { + continue; + } + + if (bound_parts == PREV_BITS(key_part_map, keyinfo->key_parts) || + extra_keyuses_bind_all_keyparts(bound_tables, table, key_start, + keyuse, n_unusable, bound_parts)) + { + return TRUE; + } + } + } + return FALSE; +} + + +/* + Check if KEYUSE elemements with unusable==TRUE bind all parts of the key + + SYNOPSIS + + extra_keyuses_bind_all_keyparts() + bound_tables Tables which can be considered constants + table Table we're examining + key_start Start of KEYUSE array with elements describing the key + of interest + key_end End of the array + 1 + n_keyuses Number of elements in the array that have unusable==TRUE + bound_parts Key parts whose values are known to be bound. + + DESCRIPTION + Check if unusable KEYUSE elements cause all parts of key to be bound. An + unusable keyuse element makes a keypart bound when it + represents the following: + + keyXpartY=func(bound_columns, preceding_tables) + + RETURN + TRUE Yes, at most one match + FALSE No +*/ + +static bool +extra_keyuses_bind_all_keyparts(table_map bound_tables, TABLE *table, + KEYUSE *key_start, KEYUSE *key_end, + uint n_keyuses, table_map bound_parts) +{ + /* + We need + - some 'unusable' KEYUSE elements to work on + - some keyparts to be already bound to start inferences: + */ + if (n_keyuses && bound_parts) + { + KEY *keyinfo= table->key_info + key_start->key; + bool bound_more_parts; + do + { + bound_more_parts= FALSE; + for (KEYUSE *k= key_start; k!=key_end; k++) + { + if (k->type == KEYUSE_UNKNOWN) + { + Field_processor_info fp= {table, k->key, k->keypart, 0, 0}; + if (k->val->walk(&Item::check_column_usage_processor, FALSE, + (uchar*)&fp)) + k->type= KEYUSE_NO_BIND; + else + { + k->used_tables= fp.used_tables; + k->keypart_map= fp.needed_key_parts; + k->type= KEYUSE_BIND; + } + } + + if (k->type == KEYUSE_BIND) + { + /* + If this is a binding keyuse, such that + - all tables it refers to are bound, + - all parts it refers to are bound + - but the key part it binds is not itself bound + */ + if (!(k->used_tables & ~bound_tables) && + !(k->keypart_map & ~bound_parts) && + !(bound_parts & key_part_map(1) << k->keypart)) + { + bound_parts|= key_part_map(1) << k->keypart; + if (bound_parts == PREV_BITS(key_part_map, keyinfo->key_parts)) + return TRUE; + bound_more_parts= TRUE; + } + } + } + } while (bound_more_parts); + } + return FALSE; +} + + +/* + Mark one table or the whole join nest as eliminated. +*/ +static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl) +{ + TABLE *table; + /* + NOTE: there are TABLE_LIST object that have + tbl->table!= NULL && tbl->nested_join!=NULL and + tbl->table == tbl->nested_join->join_list->element(..)->table + */ + if (tbl->nested_join) + { + TABLE_LIST *child; + List_iterator it(tbl->nested_join->join_list); + while ((child= it++)) + mark_as_eliminated(join, child); + } + else if ((table= tbl->table)) + { + JOIN_TAB *tab= tbl->table->reginfo.join_tab; + if (!(join->const_table_map & tab->table->map)) + { + DBUG_PRINT("info", ("Eliminated table %s", table->alias)); + tab->type= JT_CONST; + join->eliminated_tables |= table->map; + join->const_table_map|= table->map; + set_position(join, join->const_tables++, tab, (KEYUSE*)0); + } + } + + if (tbl->on_expr) + tbl->on_expr->walk(&Item::mark_as_eliminated_processor, FALSE, NULL); +} + +/** + @} (end of group Table_Elimination) +*/ + === modified file 'sql/sql_lex.cc' --- a/sql/sql_lex.cc 2009-04-25 10:05:32 +0000 +++ b/sql/sql_lex.cc 2009-06-30 15:09:36 +0000 @@ -1778,7 +1778,7 @@ void st_select_lex_unit::exclude_tree() 'last' should be reachable from this st_select_lex_node */ -void st_select_lex::mark_as_dependent(st_select_lex *last) +void st_select_lex::mark_as_dependent(st_select_lex *last, Item *dependency) { /* Mark all selects from resolved to 1 before select where was @@ -1804,6 +1804,8 @@ void st_select_lex::mark_as_dependent(st } is_correlated= TRUE; this->master_unit()->item->is_correlated= TRUE; + if (dependency) + this->master_unit()->item->refers_to.push_back(dependency); } bool st_select_lex_node::set_braces(bool value) { return 1; } === modified file 'sql/sql_lex.h' --- a/sql/sql_lex.h 2009-03-17 20:29:24 +0000 +++ b/sql/sql_lex.h 2009-06-30 15:09:36 +0000 @@ -743,7 +743,7 @@ public: return master_unit()->return_after_parsing(); } - void mark_as_dependent(st_select_lex *last); + void mark_as_dependent(st_select_lex *last, Item *dependency); bool set_braces(bool value); bool inc_in_sum_expr(); === modified file 'sql/sql_select.cc' --- a/sql/sql_select.cc 2009-05-19 09:28:05 +0000 +++ b/sql/sql_select.cc 2009-06-30 15:09:36 +0000 @@ -60,7 +60,6 @@ static bool update_ref_and_keys(THD *thd table_map table_map, SELECT_LEX *select_lex, st_sargable_param **sargables); static int sort_keyuse(KEYUSE *a,KEYUSE *b); -static void set_position(JOIN *join,uint index,JOIN_TAB *table,KEYUSE *key); static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse, table_map used_tables); static bool choose_plan(JOIN *join,table_map join_tables); @@ -2381,6 +2380,13 @@ mysql_select(THD *thd, Item ***rref_poin } else { + /* + When in EXPLAIN, delay deleting the joins so that they are still + available when we're producing EXPLAIN EXTENDED warning text. + */ + if (select_options & SELECT_DESCRIBE) + free_join= 0; + if (!(join= new JOIN(thd, fields, select_options, result))) DBUG_RETURN(TRUE); thd_proc_info(thd, "init"); @@ -2468,6 +2474,7 @@ static ha_rows get_quick_record_count(TH DBUG_RETURN(HA_POS_ERROR); /* This shouldn't happend */ } + /* This structure is used to collect info on potentially sargable predicates in order to check whether they become sargable after @@ -2646,24 +2653,31 @@ make_join_statistics(JOIN *join, TABLE_L ~outer_join, join->select_lex, &sargables)) goto error; - /* Read tables with 0 or 1 rows (system tables) */ join->const_table_map= 0; + join->const_tables= const_count; + eliminate_tables(join); + const_count= join->const_tables; + found_const_table_map= join->const_table_map; + /* Read tables with 0 or 1 rows (system tables) */ for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count; p_pos < p_end ; p_pos++) { - int tmp; s= p_pos->table; - s->type=JT_SYSTEM; - join->const_table_map|=s->table->map; - if ((tmp=join_read_const_table(s, p_pos))) + if (! (s->table->map & join->eliminated_tables)) { - if (tmp > 0) - goto error; // Fatal error + int tmp; + s->type=JT_SYSTEM; + join->const_table_map|=s->table->map; + if ((tmp=join_read_const_table(s, p_pos))) + { + if (tmp > 0) + goto error; // Fatal error + } + else + found_const_table_map|= s->table->map; } - else - found_const_table_map|= s->table->map; } /* loop until no more const tables are found */ @@ -2688,7 +2702,8 @@ make_join_statistics(JOIN *join, TABLE_L substitution of a const table the key value happens to be null then we can state that there are no matches for this equi-join. */ - if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map) + if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map && + !(table->map & join->eliminated_tables)) { /* When performing an outer join operation if there are no matching rows @@ -2747,14 +2762,16 @@ make_join_statistics(JOIN *join, TABLE_L { start_keyuse=keyuse; key=keyuse->key; - s->keys.set_bit(key); // QQ: remove this ? + if (keyuse->type == KEYUSE_USABLE) + s->keys.set_bit(key); // QQ: remove this ? refs=0; const_ref.clear_all(); eq_part.clear_all(); do { - if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize) + if (keyuse->type == KEYUSE_USABLE && + keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize) { if (!((~found_const_table_map) & keyuse->used_tables)) const_ref.set_bit(keyuse->keypart); @@ -2954,17 +2971,35 @@ typedef struct key_field_t { */ bool null_rejecting; bool *cond_guard; /* See KEYUSE::cond_guard */ + enum keyuse_type type; /* See KEYUSE::type */ } KEY_FIELD; -/* Values in optimize */ -#define KEY_OPTIMIZE_EXISTS 1 -#define KEY_OPTIMIZE_REF_OR_NULL 2 /** Merge new key definitions to old ones, remove those not used in both. This is called for OR between different levels. + That is, the function operates on an array of KEY_FIELD elements which has + two parts: + + $LEFT_PART $RIGHT_PART + +-----------------------+-----------------------+ + start new_fields end + + $LEFT_PART and $RIGHT_PART are arrays that have KEY_FIELD elements for two + parts of the OR condition. Our task is to produce an array of KEY_FIELD + elements that would correspond to "$LEFT_PART OR $RIGHT_PART". + + The rules for combining elements are as follows: + (keyfieldA1 AND keyfieldA2 AND ...) OR (keyfieldB1 AND keyfieldB2 AND ...)= + AND_ij (keyfieldA_i OR keyfieldB_j) + + We discard all (keyfieldA_i OR keyfieldB_j) that refer to different + fields. For those referring to the same field, the logic is as follows: + + t.keycol= + To be able to do 'ref_or_null' we merge a comparison of a column and 'column IS NULL' to one test. This is useful for sub select queries that are internally transformed to something like:. @@ -3029,13 +3064,18 @@ merge_key_fields(KEY_FIELD *start,KEY_FI KEY_OPTIMIZE_REF_OR_NULL)); old->null_rejecting= (old->null_rejecting && new_fields->null_rejecting); + /* + The conditions are the same, hence their usabilities should + be, too (TODO: shouldn't that apply to the above + null_rejecting and optimize attributes?) + */ + DBUG_ASSERT(old->type == new_fields->type); } } else if (old->eq_func && new_fields->eq_func && old->val->eq_by_collation(new_fields->val, old->field->binary(), old->field->charset())) - { old->level= and_level; old->optimize= ((old->optimize & new_fields->optimize & @@ -3044,10 +3084,15 @@ merge_key_fields(KEY_FIELD *start,KEY_FI KEY_OPTIMIZE_REF_OR_NULL)); old->null_rejecting= (old->null_rejecting && new_fields->null_rejecting); + // "t.key_col=const" predicates are always usable + DBUG_ASSERT(old->type == KEYUSE_USABLE && + new_fields->type == KEYUSE_USABLE); } else if (old->eq_func && new_fields->eq_func && - ((old->val->const_item() && old->val->is_null()) || - new_fields->val->is_null())) + ((new_fields->type == KEYUSE_USABLE && + old->val->const_item() && old->val->is_null()) || + ((old->type == KEYUSE_USABLE && new_fields->val->is_null())))) + /* TODO ^ why is the above asymmetric, why const_item()? */ { /* field = expression OR field IS NULL */ old->level= and_level; @@ -3118,6 +3163,7 @@ add_key_field(KEY_FIELD **key_fields,uin table_map usable_tables, SARGABLE_PARAM **sargables) { uint exists_optimize= 0; + bool optimizable=0; if (!(field->flags & PART_KEY_FLAG)) { // Don't remove column IS NULL on a LEFT JOIN table @@ -3130,15 +3176,12 @@ add_key_field(KEY_FIELD **key_fields,uin else { table_map used_tables=0; - bool optimizable=0; for (uint i=0; iused_tables(); if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT))) optimizable=1; } - if (!optimizable) - return; if (!(usable_tables & field->table->map)) { if (!eq_func || (*value)->type() != Item::NULL_ITEM || @@ -3151,7 +3194,8 @@ add_key_field(KEY_FIELD **key_fields,uin JOIN_TAB *stat=field->table->reginfo.join_tab; key_map possible_keys=field->key_start; possible_keys.intersect(field->table->keys_in_use_for_query); - stat[0].keys.merge(possible_keys); // Add possible keys + if (optimizable) + stat[0].keys.merge(possible_keys); // Add possible keys /* Save the following cases: @@ -3244,6 +3288,7 @@ add_key_field(KEY_FIELD **key_fields,uin (*key_fields)->val= *value; (*key_fields)->level= and_level; (*key_fields)->optimize= exists_optimize; + (*key_fields)->type= optimizable? KEYUSE_USABLE : KEYUSE_UNKNOWN; /* If the condition has form "tbl.keypart = othertbl.field" and othertbl.field can be NULL, there will be no matches if othertbl.field @@ -3555,6 +3600,7 @@ add_key_part(DYNAMIC_ARRAY *keyuse_array keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL; keyuse.null_rejecting= key_field->null_rejecting; keyuse.cond_guard= key_field->cond_guard; + keyuse.type= key_field->type; VOID(insert_dynamic(keyuse_array,(uchar*) &keyuse)); } } @@ -3563,7 +3609,6 @@ add_key_part(DYNAMIC_ARRAY *keyuse_array } -#define FT_KEYPART (MAX_REF_PARTS+10) static void add_ft_keys(DYNAMIC_ARRAY *keyuse_array, @@ -3622,6 +3667,7 @@ add_ft_keys(DYNAMIC_ARRAY *keyuse_array, keyuse.used_tables=cond_func->key_item()->used_tables(); keyuse.optimize= 0; keyuse.keypart_map= 0; + keyuse.type= KEYUSE_USABLE; VOID(insert_dynamic(keyuse_array,(uchar*) &keyuse)); } @@ -3636,6 +3682,13 @@ sort_keyuse(KEYUSE *a,KEYUSE *b) return (int) (a->key - b->key); if (a->keypart != b->keypart) return (int) (a->keypart - b->keypart); + + // Usable ones go before the unusable + int a_ok= test(a->type == KEYUSE_USABLE); + int b_ok= test(b->type == KEYUSE_USABLE); + if (a_ok != b_ok) + return a_ok? -1 : 1; + // Place const values before other ones if ((res= test((a->used_tables & ~OUTER_REF_TABLE_BIT)) - test((b->used_tables & ~OUTER_REF_TABLE_BIT)))) @@ -3846,7 +3899,8 @@ update_ref_and_keys(THD *thd, DYNAMIC_AR found_eq_constant=0; for (i=0 ; i < keyuse->elements-1 ; i++,use++) { - if (!use->used_tables && use->optimize != KEY_OPTIMIZE_REF_OR_NULL) + if (use->type == KEYUSE_USABLE && !use->used_tables && + use->optimize != KEY_OPTIMIZE_REF_OR_NULL) use->table->const_key_parts[use->key]|= use->keypart_map; if (use->keypart != FT_KEYPART) { @@ -3870,7 +3924,8 @@ update_ref_and_keys(THD *thd, DYNAMIC_AR /* Save ptr to first use */ if (!use->table->reginfo.join_tab->keyuse) use->table->reginfo.join_tab->keyuse=save_pos; - use->table->reginfo.join_tab->checked_keys.set_bit(use->key); + if (use->type == KEYUSE_USABLE) + use->table->reginfo.join_tab->checked_keys.set_bit(use->key); save_pos++; } i=(uint) (save_pos-(KEYUSE*) keyuse->buffer); @@ -3900,7 +3955,7 @@ static void optimize_keyuse(JOIN *join, To avoid bad matches, we don't make ref_table_rows less than 100. */ keyuse->ref_table_rows= ~(ha_rows) 0; // If no ref - if (keyuse->used_tables & + if (keyuse->type == KEYUSE_USABLE && keyuse->used_tables & (map= (keyuse->used_tables & ~join->const_table_map & ~OUTER_REF_TABLE_BIT))) { @@ -3990,8 +4045,7 @@ add_group_and_distinct_keys(JOIN *join, /** Save const tables first as used tables. */ -static void -set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key) +void set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key) { join->positions[idx].table= table; join->positions[idx].key=key; @@ -4093,7 +4147,8 @@ best_access_path(JOIN *join, if 1. expression doesn't refer to forward tables 2. we won't get two ref-or-null's */ - if (!(remaining_tables & keyuse->used_tables) && + if (keyuse->type == KEYUSE_USABLE && + !(remaining_tables & keyuse->used_tables) && !(ref_or_null_part && (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL))) { @@ -5547,7 +5602,8 @@ static bool create_ref_for_key(JOIN *joi */ do { - if (!(~used_tables & keyuse->used_tables)) + if (!(~used_tables & keyuse->used_tables) && + keyuse->type == KEYUSE_USABLE) { if (keyparts == keyuse->keypart && !(found_part_ref_or_null & keyuse->optimize)) @@ -5597,9 +5653,11 @@ static bool create_ref_for_key(JOIN *joi uint i; for (i=0 ; i < keyparts ; keyuse++,i++) { - while (keyuse->keypart != i || - ((~used_tables) & keyuse->used_tables)) + while (keyuse->keypart != i || ((~used_tables) & keyuse->used_tables) || + !(keyuse->type == KEYUSE_USABLE)) + { keyuse++; /* Skip other parts */ + } uint maybe_null= test(keyinfo->key_part[i].null_bit); j->ref.items[i]=keyuse->val; // Save for cond removal @@ -5757,6 +5815,7 @@ JOIN::make_simple_join(JOIN *parent, TAB tables= 1; const_tables= 0; const_table_map= 0; + eliminated_tables= 0; tmp_table_param.field_count= tmp_table_param.sum_func_count= tmp_table_param.func_count= 0; tmp_table_param.copy_field= tmp_table_param.copy_field_end=0; @@ -6021,7 +6080,7 @@ make_outerjoin_info(JOIN *join) } if (!tab->first_inner) tab->first_inner= nested_join->first_nested; - if (++nested_join->counter < nested_join->join_list.elements) + if (++nested_join->counter < nested_join->n_tables) break; /* Table tab is the last inner table for nested join. */ nested_join->first_nested->last_inner= tab; @@ -8575,6 +8634,8 @@ simplify_joins(JOIN *join, Listjoin_list, conds, top); used_tables= nested_join->used_tables; not_null_tables= nested_join->not_null_tables; + /* The following two might become unequal after table elimination: */ + nested_join->n_tables= nested_join->join_list.elements; } else { @@ -8733,7 +8794,7 @@ static uint build_bitmap_for_nested_join with anything) 2. we could run out bits in nested_join_map otherwise. */ - if (nested_join->join_list.elements != 1) + if (nested_join->n_tables != 1) { nested_join->nj_map= (nested_join_map) 1 << first_unused++; first_unused= build_bitmap_for_nested_joins(&nested_join->join_list, @@ -8894,7 +8955,7 @@ static bool check_interleaving_with_nj(J join->cur_embedding_map |= next_emb->nested_join->nj_map; } - if (next_emb->nested_join->join_list.elements != + if (next_emb->nested_join->n_tables != next_emb->nested_join->counter) break; @@ -8926,9 +8987,23 @@ static void restore_prev_nj_state(JOIN_T JOIN *join= last->join; while (last_emb) { + /* + psergey-elim: (nevermind) + new_prefix= cur_prefix & ~last; + if (!(new_prefix & cur_table_map)) // removed last inner table + { + join->cur_embedding_map&= ~last_emb->nested_join->nj_map; + } + else (current) + { + // Won't hurt doing it all the time: + join->cur_embedding_map |= ...; + } + else + */ if (!(--last_emb->nested_join->counter)) join->cur_embedding_map&= ~last_emb->nested_join->nj_map; - else if (last_emb->nested_join->join_list.elements-1 == + else if (last_emb->nested_join->n_tables-1 == last_emb->nested_join->counter) join->cur_embedding_map|= last_emb->nested_join->nj_map; else @@ -16202,6 +16277,14 @@ static void select_describe(JOIN *join, tmp3.length(0); quick_type= -1; + + /* Don't show eliminated tables */ + if (table->map & join->eliminated_tables) + { + used_tables|=table->map; + continue; + } + item_list.empty(); /* id */ item_list.push_back(new Item_uint((uint32) @@ -16524,8 +16607,11 @@ static void select_describe(JOIN *join, unit; unit= unit->next_unit()) { - if (mysql_explain_union(thd, unit, result)) - DBUG_VOID_RETURN; + if (!(unit->item && unit->item->eliminated)) + { + if (mysql_explain_union(thd, unit, result)) + DBUG_VOID_RETURN; + } } DBUG_VOID_RETURN; } @@ -16566,7 +16652,6 @@ bool mysql_explain_union(THD *thd, SELEC unit->fake_select_lex->options|= SELECT_DESCRIBE; if (!(res= unit->prepare(thd, result, SELECT_NO_UNLOCK | SELECT_DESCRIBE))) res= unit->exec(); - res|= unit->cleanup(); } else { @@ -16599,6 +16684,7 @@ bool mysql_explain_union(THD *thd, SELEC */ static void print_join(THD *thd, + table_map eliminated_tables, String *str, List *tables, enum_query_type query_type) @@ -16614,12 +16700,33 @@ static void print_join(THD *thd, *t= ti++; DBUG_ASSERT(tables->elements >= 1); - (*table)->print(thd, str, query_type); + /* + Assert that the first table in the list isn't eliminated. This comes from + the fact that the first table can't be inner table of an outer join. + */ + DBUG_ASSERT(!eliminated_tables || + !(((*table)->table && ((*table)->table->map & eliminated_tables)) || + ((*table)->nested_join && !((*table)->nested_join->used_tables & + ~eliminated_tables)))); + (*table)->print(thd, eliminated_tables, str, query_type); TABLE_LIST **end= table + tables->elements; for (TABLE_LIST **tbl= table + 1; tbl < end; tbl++) { TABLE_LIST *curr= *tbl; + /* + The "eliminated_tables &&" check guards againist the case of + printing the query for CREATE VIEW. We do that without having run + JOIN::optimize() and so will have nested_join->used_tables==0. + */ + if (eliminated_tables && + ((curr->table && (curr->table->map & eliminated_tables)) || + (curr->nested_join && !(curr->nested_join->used_tables & + ~eliminated_tables)))) + { + continue; + } + if (curr->outer_join) { /* MySQL converts right to left joins */ @@ -16629,7 +16736,7 @@ static void print_join(THD *thd, str->append(STRING_WITH_LEN(" straight_join ")); else str->append(STRING_WITH_LEN(" join ")); - curr->print(thd, str, query_type); + curr->print(thd, eliminated_tables, str, query_type); if (curr->on_expr) { str->append(STRING_WITH_LEN(" on(")); @@ -16683,12 +16790,13 @@ Index_hint::print(THD *thd, String *str) @param str string where table should be printed */ -void TABLE_LIST::print(THD *thd, String *str, enum_query_type query_type) +void TABLE_LIST::print(THD *thd, table_map eliminated_tables, String *str, + enum_query_type query_type) { if (nested_join) { str->append('('); - print_join(thd, str, &nested_join->join_list, query_type); + print_join(thd, eliminated_tables, str, &nested_join->join_list, query_type); str->append(')'); } else @@ -16830,7 +16938,7 @@ void st_select_lex::print(THD *thd, Stri { str->append(STRING_WITH_LEN(" from ")); /* go through join tree */ - print_join(thd, str, &top_join_list, query_type); + print_join(thd, join? join->eliminated_tables: 0, str, &top_join_list, query_type); } else if (where) { === modified file 'sql/sql_select.h' --- a/sql/sql_select.h 2009-04-25 10:05:32 +0000 +++ b/sql/sql_select.h 2009-06-30 15:09:36 +0000 @@ -28,6 +28,45 @@ #include "procedure.h" #include +#define FT_KEYPART (MAX_REF_PARTS+10) +/* Values in optimize */ +#define KEY_OPTIMIZE_EXISTS 1 +#define KEY_OPTIMIZE_REF_OR_NULL 2 + +/* KEYUSE element types */ +enum keyuse_type +{ + /* + val refers to the same table, this is either KEYUSE_BIND or KEYUSE_NO_BIND + type, we didn't determine which one yet. + */ + KEYUSE_UNKNOWN= 0, + /* + 'regular' keyuse, i.e. it represents one of the following + * t.keyXpartY = func(constants, other-tables) + * t.keyXpartY IS NULL + * t.keyXpartY = func(constants, other-tables) OR t.keyXpartY IS NULL + and can be used to construct ref acces + */ + KEYUSE_USABLE, + /* + The keyuse represents a condition in form: + + t.uniq_keyXpartY = func(other parts of uniq_keyX) + + This can't be used to construct uniq_keyX but we could use it to determine + that the table will produce at most one match. + */ + KEYUSE_BIND, + /* + Keyuse that's not usable for ref access and doesn't meet the criteria of + KEYUSE_BIND. Examples: + t.keyXpartY = func(t.keyXpartY) + t.keyXpartY = func(column of t that's not covered by keyX) + */ + KEYUSE_NO_BIND +}; + typedef struct keyuse_t { TABLE *table; Item *val; /**< or value if no field */ @@ -51,6 +90,15 @@ typedef struct keyuse_t { NULL - Otherwise (the source equality can't be turned off) */ bool *cond_guard; + /* + 1 <=> This keyuse can be used to construct key access. + 0 <=> Otherwise. Currently unusable KEYUSEs represent equalities + where one table column refers to another one, like this: + t.keyXpartA=func(t.keyXpartB) + This equality cannot be used for index access but is useful + for table elimination. + */ + enum keyuse_type type; } KEYUSE; class store_key; @@ -210,7 +258,7 @@ typedef struct st_join_table { JOIN *join; /** Bitmap of nested joins this table is part of */ nested_join_map embedding_map; - + void cleanup(); inline bool is_using_loose_index_scan() { @@ -285,7 +333,15 @@ public: fetching data from a cursor */ bool resume_nested_loop; - table_map const_table_map,found_const_table_map; + table_map const_table_map; + /* + Constant tables for which we have found a row (as opposed to those for + which we didn't). + */ + table_map found_const_table_map; + + /* Tables removed by table elimination. Set to 0 before the elimination. */ + table_map eliminated_tables; /* Bitmap of all inner tables from outer joins */ @@ -425,6 +481,7 @@ public: table= 0; tables= 0; const_tables= 0; + eliminated_tables= 0; join_list= 0; sort_and_group= 0; first_record= 0; @@ -530,6 +587,10 @@ public: return (unit == &thd->lex->unit && (unit->fake_select_lex == 0 || select_lex == unit->fake_select_lex)); } + inline table_map all_tables_map() + { + return (table_map(1) << tables) - 1; + } private: bool make_simple_join(JOIN *join, TABLE *tmp_table); }; @@ -730,9 +791,12 @@ bool error_if_full_join(JOIN *join); int report_error(TABLE *table, int error); int safe_index_read(JOIN_TAB *tab); COND *remove_eq_conds(THD *thd, COND *cond, Item::cond_result *cond_value); +void set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key); inline bool optimizer_flag(THD *thd, uint flag) { return (thd->variables.optimizer_switch & flag); } +void eliminate_tables(JOIN *join); + === modified file 'sql/table.h' --- a/sql/table.h 2009-02-19 09:01:25 +0000 +++ b/sql/table.h 2009-06-30 15:09:36 +0000 @@ -1366,7 +1366,8 @@ struct TABLE_LIST return (derived || view || schema_table || (create && !table->db_stat) || !table); } - void print(THD *thd, String *str, enum_query_type query_type); + void print(THD *thd, table_map eliminated_tables, String *str, + enum_query_type query_type); bool check_single_table(TABLE_LIST **table, table_map map, TABLE_LIST *view); bool set_insert_values(MEM_ROOT *mem_root); @@ -1615,7 +1616,11 @@ public: typedef struct st_nested_join { List join_list; /* list of elements in the nested join */ - table_map used_tables; /* bitmap of tables in the nested join */ + /* + Bitmap of tables within this nested join (including those embedded within + its children), including tables removed by table elimination. + */ + table_map used_tables; table_map not_null_tables; /* tables that rejects nulls */ struct st_join_table *first_nested;/* the first nested table in the plan */ /* @@ -1626,6 +1631,11 @@ typedef struct st_nested_join Before each use the counters are zeroed by reset_nj_counters. */ uint counter; + /* + Number of elements in join_list that were not (or contain table(s) that + weren't) removed by table elimination. + */ + uint n_tables; nested_join_map nj_map; /* Bit used to identify this nested join*/ } NESTED_JOIN;