maria-developers team mailing list archive
-
maria-developers team
-
Mailing list archive
-
Message #00875
[Branch ~maria-captains/maria/5.1] Rev 2725: MWL#17: Table elimination
Merge authors:
Sergey Petrunia (sergefp)
Sergey Petrunia (sergefp)
------------------------------------------------------------
revno: 2725 [merge]
committer: Sergey Petrunya <psergey@xxxxxxxxxxxx>
branch nick: maria-5.1
timestamp: Wed 2009-09-02 12:42:28 +0400
message:
MWL#17: Table elimination
Pre-push merge to main. This should give the complete WL entry diff.
added:
mysql-test/lib/process-purecov-annotations.pl
mysql-test/r/table_elim.result
mysql-test/t/table_elim.test
sql-bench/test-table-elimination.sh
sql/opt_table_elimination.cc
modified:
.bzrignore
include/my_global.h
libmysqld/Makefile.am
mysql-test/lib/mtr_gcov.pl
mysql-test/mysql-test-run.pl
mysql-test/r/mysql-bug41486.result
mysql-test/r/ps_11bugs.result
mysql-test/r/select.result
mysql-test/r/subselect.result
mysql-test/r/union.result
mysql-test/t/index_merge_myisam.test
mysql-test/t/mysql-bug41486.test
mysql-test/valgrind.supp
sql/CMakeLists.txt
sql/Makefile.am
sql/item.cc
sql/item.h
sql/item_cmpfunc.cc
sql/item_cmpfunc.h
sql/item_subselect.cc
sql/item_subselect.h
sql/item_sum.cc
sql/item_sum.h
sql/mysql_priv.h
sql/mysqld.cc
sql/sql_bitmap.h
sql/sql_lex.cc
sql/sql_lex.h
sql/sql_list.h
sql/sql_select.cc
sql/sql_select.h
sql/table.h
--
lp:maria
https://code.launchpad.net/~maria-captains/maria/5.1
Your team Maria developers is subscribed to branch lp:maria.
To unsubscribe from this branch go to https://code.launchpad.net/~maria-captains/maria/5.1/+edit-subscription.
=== modified file '.bzrignore'
--- .bzrignore 2009-06-11 17:49:51 +0000
+++ .bzrignore 2009-08-13 21:12:12 +0000
@@ -1920,3 +1920,4 @@
sql/share/ukrainian
libmysqld/examples/mysqltest.cc
extra/libevent/event-config.h
+libmysqld/opt_table_elimination.cc
=== modified file 'include/my_global.h'
--- include/my_global.h 2009-05-19 09:28:05 +0000
+++ include/my_global.h 2009-08-31 20:02:09 +0000
@@ -950,8 +950,7 @@
#define MY_ALIGN(A,L) (((A) + (L) - 1) & ~((L) - 1))
#define ALIGN_SIZE(A) MY_ALIGN((A),sizeof(double))
/* Size to make adressable obj. */
-#define ALIGN_PTR(A, t) ((t*) MY_ALIGN((A),sizeof(t)))
- /* Offset of field f in structure t */
+#define ALIGN_PTR(A, t) ((t*) MY_ALIGN((A), sizeof(double)))
#define OFFSET(t, f) ((size_t)(char *)&((t *)0)->f)
#define ADD_TO_PTR(ptr,size,type) (type) ((uchar*) (ptr)+size)
#define PTR_BYTE_DIFF(A,B) (my_ptrdiff_t) ((uchar*) (A) - (uchar*) (B))
=== modified file 'libmysqld/Makefile.am'
--- libmysqld/Makefile.am 2009-03-12 22:27:35 +0000
+++ libmysqld/Makefile.am 2009-06-25 10:05:53 +0000
@@ -76,7 +76,7 @@
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/lib/mtr_gcov.pl'
--- mysql-test/lib/mtr_gcov.pl 2009-04-25 09:04:38 +0000
+++ mysql-test/lib/mtr_gcov.pl 2009-08-25 15:02:55 +0000
@@ -20,6 +20,8 @@
use strict;
+our $basedir;
+
sub gcov_prepare ($) {
my ($dir)= @_;
print "Purging gcov information from '$dir'...\n";
@@ -42,7 +44,7 @@
# Get current directory to return to later.
my $start_dir= cwd();
- print "Collecting source coverage info using '$gcov'...\n";
+ print "Collecting source coverage info using '$gcov'...$basedir\n";
-f "$start_dir/$gcov_msg" and unlink("$start_dir/$gcov_msg");
-f "$start_dir/$gcov_err" and unlink("$start_dir/$gcov_err");
@@ -62,6 +64,7 @@
$dir_reported= 1;
}
system("$gcov $f 2>>$start_dir/$gcov_err >>$start_dir/$gcov_msg");
+ system("perl $basedir/mysql-test/lib/process-purecov-annotations.pl $f.gcov");
}
chdir($start_dir);
}
=== added file 'mysql-test/lib/process-purecov-annotations.pl'
--- mysql-test/lib/process-purecov-annotations.pl 1970-01-01 00:00:00 +0000
+++ mysql-test/lib/process-purecov-annotations.pl 2009-08-25 15:02:55 +0000
@@ -0,0 +1,64 @@
+#!/usr/bin/perl
+# -*- cperl -*-
+
+# This script processes a .gcov coverage report to honor purecov
+# annotations: lines marked as inspected or as deadcode are changed
+# from looking like lines with code that was never executed to look
+# like lines that have no executable code.
+
+use strict;
+use warnings;
+
+foreach my $in_file_name ( @ARGV )
+{
+ my $out_file_name=$in_file_name . ".tmp";
+ my $skipping=0;
+
+ open(IN, "<", $in_file_name) || next;
+ open(OUT, ">", $out_file_name);
+ while(<IN>)
+ {
+ my $line= $_;
+ my $check= $line;
+
+ # process purecov: start/end multi-blocks
+ my $started=0;
+ my $ended= 0;
+ while (($started=($check =~ s/purecov: *begin *(deadcode|inspected)//)) ||
+ ($ended=($check =~ s/purecov: *end//)))
+ {
+ $skipping= $skipping + $started - $ended;
+ }
+ if ($skipping < 0)
+ {
+ print OUT "WARNING: #####: incorrect order of purecov begin/end annotations\n";
+ $skipping= 0;
+ }
+
+ # Besides purecov annotations, also remove uncovered code mark from cases
+ # like the following:
+ #
+ # -: 211:*/
+ # -: 212:class Field_value : public Value_dep
+ # #####: 213:{
+ # -: 214:public:
+ #
+ # I have no idea why would gcov think there is uncovered code there
+ #
+ my @arr= split(/:/, $line);
+ if ($skipping || $line =~ /purecov: *(inspected|deadcode)/ ||
+ $arr[2] =~ m/^{ */)
+ {
+ # Change '####' to '-'.
+ $arr[0] =~ s/#####/ -/g;
+ $line= join(":", @arr);
+ }
+ print OUT $line;
+ }
+ close(IN);
+ close(OUT);
+ system("cat $out_file_name > $in_file_name");
+ system("rm $out_file_name");
+}
+
+
=== modified file 'mysql-test/mysql-test-run.pl'
--- mysql-test/mysql-test-run.pl 2009-06-22 08:06:35 +0000
+++ mysql-test/mysql-test-run.pl 2009-08-25 15:02:55 +0000
@@ -169,6 +169,7 @@
our $opt_mem= $ENV{'MTR_MEM'};
our $opt_gcov;
+our $opt_gcov_src_dir;
our $opt_gcov_exe= "gcov";
our $opt_gcov_err= "mysql-test-gcov.msg";
our $opt_gcov_msg= "mysql-test-gcov.err";
@@ -270,7 +271,7 @@
command_line_setup();
if ( $opt_gcov ) {
- gcov_prepare($basedir);
+ gcov_prepare($basedir . "/" . $opt_gcov_src_dir);
}
if (!$opt_suites) {
@@ -416,7 +417,7 @@
mtr_print_line();
if ( $opt_gcov ) {
- gcov_collect($basedir, $opt_gcov_exe,
+ gcov_collect($basedir . "/" . $opt_gcov_src_dir, $opt_gcov_exe,
$opt_gcov_msg, $opt_gcov_err);
}
@@ -882,6 +883,7 @@
# Coverage, profiling etc
'gcov' => \$opt_gcov,
+ 'gcov-src-dir=s' => \$opt_gcov_src_dir,
'valgrind|valgrind-all' => \$opt_valgrind,
'valgrind-mysqltest' => \$opt_valgrind_mysqltest,
'valgrind-mysqld' => \$opt_valgrind_mysqld,
@@ -5397,6 +5399,9 @@
actions. Disable facility with NUM=0.
gcov Collect coverage information after the test.
The result is a gcov file per source and header file.
+ gcov-src-dir=subdir Colllect coverage only within the given subdirectory.
+ For example, if you're only developing the SQL layer,
+ it makes sense to use --gcov-src-dir=sql
HERE
exit(1);
=== modified file 'mysql-test/r/mysql-bug41486.result'
--- mysql-test/r/mysql-bug41486.result 2009-03-25 07:32:01 +0000
+++ mysql-test/r/mysql-bug41486.result 2009-06-24 22:44:14 +0000
@@ -3,6 +3,9 @@
SET @@global.max_allowed_packet = 2 * 1024 * 1024 + 1024;
CREATE TABLE t1(data LONGBLOB);
INSERT INTO t1 SELECT REPEAT('1', 2*1024*1024);
+SELECT COUNT(*) FROM t1;
+COUNT(*)
+1
SET @old_general_log = @@global.general_log;
SET @@global.general_log = 0;
SET @@global.general_log = @old_general_log;
=== modified file 'mysql-test/r/ps_11bugs.result'
--- mysql-test/r/ps_11bugs.result 2008-10-08 11:23:53 +0000
+++ mysql-test/r/ps_11bugs.result 2009-06-09 21:11:33 +0000
@@ -121,8 +121,8 @@
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 <union2,3> 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'
--- mysql-test/r/select.result 2009-03-16 05:02:10 +0000
+++ mysql-test/r/select.result 2009-06-17 05:27:39 +0000
@@ -3585,7 +3585,6 @@
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'
--- mysql-test/r/subselect.result 2009-04-25 09:04:38 +0000
+++ mysql-test/r/subselect.result 2009-06-09 21:11:33 +0000
@@ -4353,13 +4353,13 @@
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 <in_optimizer>(1,<exists>(select 1 AS `1` from `test`.`t1` group by `test`.`t1`.`a` having (<cache>(1) = <ref_null_helper>(1))))
+Note 1003 select 1 AS `1` from `test`.`t1` where <in_optimizer>(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 <in_optimizer>(1,<exists>(select 1 AS `1` from `test`.`t1` where (`test`.`t1`.`a` > 3) group by `test`.`t1`.`a` having (<cache>(1) = <ref_null_helper>(1))))
+Note 1003 select 1 AS `1` from `test`.`t1` where <in_optimizer>(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'
--- mysql-test/r/table_elim.result 1970-01-01 00:00:00 +0000
+++ mysql-test/r/table_elim.result 2009-08-26 21:01:40 +0000
@@ -0,0 +1,420 @@
+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;
+create table t1 (pk int primary key, col int);
+insert into t1 values (1,1),(2,2);
+create table t2 like t1;
+insert into t2 select * from t1;
+create table t3 like t1;
+insert into t3 select * from t1;
+explain
+select t1.* from t1 left join ( t2 left join t3 on t3.pk=t2.col) on t2.col=t1.col;
+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 NULL NULL NULL NULL 2
+explain
+select t1.*, t2.* from t1 left join (t2 left join t3 on t3.pk=t2.col) on t2.pk=t1.col;
+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.col 1
+explain select t1.*
+from
+t1 left join ( t2 left join t3 on t3.pk=t2.col or t3.pk=t2.col)
+on t2.col=t1.col or t2.col=t1.col;
+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 NULL NULL NULL NULL 2
+explain select t1.*, t2.*
+from
+t1 left join
+(t2 left join t3 on t3.pk=t2.col or t3.pk=t2.col)
+on t2.pk=t1.col or t2.pk=t1.col;
+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.col 1
+drop table t1, t2, t3;
+#
+# Check things that look like functional dependencies but really are not
+#
+create table t1 (a char(10) character set latin1 collate latin1_general_ci primary key);
+insert into t1 values ('foo');
+insert into t1 values ('bar');
+create table t2 (a char(10) character set latin1 collate latin1_general_cs primary key);
+insert into t2 values ('foo');
+insert into t2 values ('FOO');
+this must not use table elimination:
+explain select t1.* from t1 left join t2 on t2.a='foo' collate latin1_general_ci;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 index NULL PRIMARY 10 NULL 2 Using index
+1 SIMPLE t2 index PRIMARY PRIMARY 10 NULL 2 Using index
+this must not use table elimination:
+explain select t1.* from t1 left join t2 on t2.a=t1.a collate latin1_general_ci;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 index NULL PRIMARY 10 NULL 2 Using index
+1 SIMPLE t2 index PRIMARY PRIMARY 10 NULL 2 Using index
+drop table t1,t2;
+create table t1 (a int primary key);
+insert into t1 values (1),(2);
+create table t2 (a char(10) primary key);
+insert into t2 values ('1'),('1.0');
+this must not use table elimination:
+explain select t1.* from t1 left join t2 on t2.a=1;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 index NULL PRIMARY 4 NULL 2 Using index
+1 SIMPLE t2 index PRIMARY PRIMARY 10 NULL 2 Using index
+this must not use table elimination:
+explain select t1.* 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 index NULL PRIMARY 4 NULL 2 Using index
+1 SIMPLE t2 index PRIMARY PRIMARY 10 NULL 2 Using index
+drop table t1, t2;
+create table t1 (a char(10) primary key);
+insert into t1 values ('foo'),('bar');
+create table t2 (a char(10), unique key(a(2)));
+insert into t2 values ('foo'),('bar');
+explain select t1.* 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 index NULL PRIMARY 10 NULL 2 Using index
+1 SIMPLE t2 ref a a 3 test.t1.a 2
+drop table t1, t2;
+#
+# check UPDATE/DELETE that look like they could be eliminated
+#
+create table t1 (a int primary key, b int);
+insert into t1 values (1,1),(2,2),(3,3);
+create table t2 like t1;
+insert into t2 select * from t1;
+update t1 left join t2 using (a) set t2.a=t2.a+100;
+select * from t1;
+a b
+1 1
+2 2
+3 3
+select * from t2;
+a b
+101 1
+102 2
+103 3
+delete from t2;
+insert into t2 select * from t1;
+delete t2 from t1 left join t2 using (a);
+select * from t1;
+a b
+1 1
+2 2
+3 3
+select * from t2;
+a b
+drop table t1, t2;
+#
+# Tests with various edge-case ON expressions
+#
+create table t1 (a int, b int, c int, d int);
+insert into t1 values (0,0,0,0),(1,1,1,1),(2,2,2,2),(3,3,3,3);
+create table t2 (pk int primary key, b int)
+as select a as pk, a as b from t1 where a in (1,2);
+create table t3 (pk1 int, pk2 int, b int, unique(pk1,pk2));
+insert into t3 select a as pk1, a as pk2, a as b from t1 where a in (1,3);
+explain select t1.a from t1 left join t2 on t2.pk=t1.a and t2.b<t1.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 4
+explain select t1.a from t1 left join t2 on t2.pk=t1.a or t2.b<t1.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 ALL PRIMARY NULL NULL NULL 2
+explain select t1.a from t1 left join t2 on t2.b<t1.b or t2.pk=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 ALL PRIMARY NULL NULL NULL 2
+explain select t1.a from t1 left join t2 on t2.pk between 10 and 20;
+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 index PRIMARY PRIMARY 4 NULL 2 Using index
+explain select t1.a from t1 left join t2 on t2.pk between 0.5 and 1.5;
+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 index PRIMARY PRIMARY 4 NULL 2 Using index
+explain select t1.a from t1 left join t2 on t2.pk between 10 and 10;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 4
+explain select t1.a from t1 left join t2 on t2.pk in (10);
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 4
+explain select t1.a from t1 left join t2 on t2.pk in (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 t1.a from t1 left join t2 on TRUE;
+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 index NULL PRIMARY 4 NULL 2 Using index
+explain select t1.a from t1 left join t3 on t3.pk1=t1.a and t3.pk2 IS NULL;
+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,t3;
+#
+# Multi-equality tests
+#
+create table t1 (a int, b int, c int, d int);
+insert into t1 values (0,0,0,0),(1,1,1,1),(2,2,2,2),(3,3,3,3);
+create table t2 (pk int primary key, b int, c int);
+insert into t2 select a,a,a from t1 where a in (1,2);
+explain
+select t1.*
+from t1 left join t2 on t2.pk=t2.c and t2.b=t1.a and t1.a=t1.b and t2.c=t2.b
+where t1.d=1;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 4 Using where
+explain
+select t1.*
+from
+t1
+left join
+t2
+on (t2.pk=t2.c and t2.b=t1.a and t1.a=t1.b and t2.c=t2.b) or
+(t2.pk=t2.c and t2.b=t1.a and t1.a=t1.b and t2.c=t2.b)
+where t1.d=1;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 4 Using where
+#This can't be eliminated:
+explain
+select t1.*
+from
+t1
+left join
+t2
+on (t2.pk=t2.c and t2.b=t1.a and t2.c=t1.b) or
+(t2.pk=t2.c and t1.a=t1.b and t2.c=t1.b)
+where t1.d=1;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 4 Using where
+1 SIMPLE t2 eq_ref PRIMARY PRIMARY 4 test.t1.b 1
+explain
+select t1.*
+from
+t1
+left join
+t2
+on (t2.pk=t2.c and t2.b=t1.a and t2.c=t1.b) or
+(t2.pk=t2.c and t2.c=t1.b)
+;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 4
+explain
+select t1.*
+from t1 left join t2 on t2.pk=3 or t2.pk= 4;
+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 index PRIMARY PRIMARY 4 NULL 2 Using index
+explain
+select t1.*
+from t1 left join t2 on t2.pk=3 or t2.pk= 3;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 4
+explain
+select t1.*
+from t1 left join t2 on (t2.pk=3 and t2.b=3) or (t2.pk= 4 and t2.b=3);
+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 range PRIMARY PRIMARY 4 NULL 2 Using where
+drop table t1, t2;
=== modified file 'mysql-test/r/union.result'
--- mysql-test/r/union.result 2009-03-19 10:18:52 +0000
+++ mysql-test/r/union.result 2009-06-14 20:59:24 +0000
@@ -522,7 +522,7 @@
2 UNION t2 const PRIMARY PRIMARY 4 const 1 100.00
NULL UNION RESULT <union1,2> 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
=== modified file 'mysql-test/t/index_merge_myisam.test'
--- mysql-test/t/index_merge_myisam.test 2009-03-14 18:58:23 +0000
+++ mysql-test/t/index_merge_myisam.test 2009-08-24 19:10:48 +0000
@@ -25,15 +25,19 @@
--echo # we get another @@optimizer_switch user)
--echo #
+--replace_regex /,table_elimination=on//
select @@optimizer_switch;
set optimizer_switch='index_merge=off,index_merge_union=off';
+--replace_regex /,table_elimination=on//
select @@optimizer_switch;
set optimizer_switch='index_merge_union=on';
+--replace_regex /,table_elimination=on//
select @@optimizer_switch;
set optimizer_switch='default,index_merge_sort_union=off';
+--replace_regex /,table_elimination=on//
select @@optimizer_switch;
--error ER_WRONG_VALUE_FOR_VAR
@@ -71,17 +75,21 @@
set optimizer_switch=default;
set optimizer_switch='index_merge=off,index_merge_union=off,default';
+--replace_regex /,table_elimination=on//
select @@optimizer_switch;
set optimizer_switch=default;
# Check setting defaults for global vars
+--replace_regex /,table_elimination=on//
select @@global.optimizer_switch;
set @@global.optimizer_switch=default;
+--replace_regex /,table_elimination=on//
select @@global.optimizer_switch;
--echo #
--echo # Check index_merge's @@optimizer_switch flags
--echo #
+--replace_regex /,table_elimination.on//
select @@optimizer_switch;
create table t0 (a int);
@@ -182,6 +190,7 @@
explain select * from t1 where a=10 and b=10 or c=10;
set optimizer_switch=default;
+--replace_regex /,table_elimination.on//
show variables like 'optimizer_switch';
drop table t0, t1;
=== modified file 'mysql-test/t/mysql-bug41486.test'
--- mysql-test/t/mysql-bug41486.test 2009-03-25 08:47:41 +0000
+++ mysql-test/t/mysql-bug41486.test 2009-06-24 22:44:14 +0000
@@ -27,7 +27,8 @@
CREATE TABLE t1(data LONGBLOB);
INSERT INTO t1 SELECT REPEAT('1', 2*1024*1024);
-
+# The following is to remove the race between end of insert and start of MYSQL_DUMP:
+SELECT COUNT(*) FROM t1;
let $outfile= $MYSQLTEST_VARDIR/tmp/bug41486.sql;
--error 0,1
remove_file $outfile;
=== added file 'mysql-test/t/table_elim.test'
--- mysql-test/t/table_elim.test 1970-01-01 00:00:00 +0000
+++ mysql-test/t/table_elim.test 2009-08-26 21:01:40 +0000
@@ -0,0 +1,338 @@
+#
+# 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;
+#
+# Check that equality propagation is taken into account
+#
+create table t1 (pk int primary key, col int);
+insert into t1 values (1,1),(2,2);
+
+create table t2 like t1;
+insert into t2 select * from t1;
+
+create table t3 like t1;
+insert into t3 select * from t1;
+
+explain
+select t1.* from t1 left join ( t2 left join t3 on t3.pk=t2.col) on t2.col=t1.col;
+
+explain
+select t1.*, t2.* from t1 left join (t2 left join t3 on t3.pk=t2.col) on t2.pk=t1.col;
+
+explain select t1.*
+from
+ t1 left join ( t2 left join t3 on t3.pk=t2.col or t3.pk=t2.col)
+ on t2.col=t1.col or t2.col=t1.col;
+
+explain select t1.*, t2.*
+from
+ t1 left join
+ (t2 left join t3 on t3.pk=t2.col or t3.pk=t2.col)
+ on t2.pk=t1.col or t2.pk=t1.col;
+
+drop table t1, t2, t3;
+
+--echo #
+--echo # Check things that look like functional dependencies but really are not
+--echo #
+
+create table t1 (a char(10) character set latin1 collate latin1_general_ci primary key);
+insert into t1 values ('foo');
+insert into t1 values ('bar');
+
+create table t2 (a char(10) character set latin1 collate latin1_general_cs primary key);
+insert into t2 values ('foo');
+insert into t2 values ('FOO');
+
+-- echo this must not use table elimination:
+explain select t1.* from t1 left join t2 on t2.a='foo' collate latin1_general_ci;
+
+-- echo this must not use table elimination:
+explain select t1.* from t1 left join t2 on t2.a=t1.a collate latin1_general_ci;
+drop table t1,t2;
+
+create table t1 (a int primary key);
+insert into t1 values (1),(2);
+create table t2 (a char(10) primary key);
+insert into t2 values ('1'),('1.0');
+-- echo this must not use table elimination:
+explain select t1.* from t1 left join t2 on t2.a=1;
+-- echo this must not use table elimination:
+explain select t1.* from t1 left join t2 on t2.a=t1.a;
+
+drop table t1, t2;
+# partial unique keys do not work at the moment, although they are able to
+# provide one-match guarantees:
+create table t1 (a char(10) primary key);
+insert into t1 values ('foo'),('bar');
+
+create table t2 (a char(10), unique key(a(2)));
+insert into t2 values ('foo'),('bar');
+
+explain select t1.* from t1 left join t2 on t2.a=t1.a;
+
+drop table t1, t2;
+
+--echo #
+--echo # check UPDATE/DELETE that look like they could be eliminated
+--echo #
+create table t1 (a int primary key, b int);
+insert into t1 values (1,1),(2,2),(3,3);
+
+create table t2 like t1;
+insert into t2 select * from t1;
+update t1 left join t2 using (a) set t2.a=t2.a+100;
+select * from t1;
+select * from t2;
+
+delete from t2;
+insert into t2 select * from t1;
+
+delete t2 from t1 left join t2 using (a);
+select * from t1;
+select * from t2;
+drop table t1, t2;
+
+--echo #
+--echo # Tests with various edge-case ON expressions
+--echo #
+create table t1 (a int, b int, c int, d int);
+insert into t1 values (0,0,0,0),(1,1,1,1),(2,2,2,2),(3,3,3,3);
+
+create table t2 (pk int primary key, b int)
+ as select a as pk, a as b from t1 where a in (1,2);
+
+create table t3 (pk1 int, pk2 int, b int, unique(pk1,pk2));
+insert into t3 select a as pk1, a as pk2, a as b from t1 where a in (1,3);
+
+explain select t1.a from t1 left join t2 on t2.pk=t1.a and t2.b<t1.b;
+explain select t1.a from t1 left join t2 on t2.pk=t1.a or t2.b<t1.b;
+explain select t1.a from t1 left join t2 on t2.b<t1.b or t2.pk=t1.a;
+
+explain select t1.a from t1 left join t2 on t2.pk between 10 and 20;
+explain select t1.a from t1 left join t2 on t2.pk between 0.5 and 1.5;
+explain select t1.a from t1 left join t2 on t2.pk between 10 and 10;
+
+explain select t1.a from t1 left join t2 on t2.pk in (10);
+explain select t1.a from t1 left join t2 on t2.pk in (t1.a);
+
+explain select t1.a from t1 left join t2 on TRUE;
+
+explain select t1.a from t1 left join t3 on t3.pk1=t1.a and t3.pk2 IS NULL;
+
+drop table t1,t2,t3;
+
+--echo #
+--echo # Multi-equality tests
+--echo #
+create table t1 (a int, b int, c int, d int);
+insert into t1 values (0,0,0,0),(1,1,1,1),(2,2,2,2),(3,3,3,3);
+
+create table t2 (pk int primary key, b int, c int);
+insert into t2 select a,a,a from t1 where a in (1,2);
+
+explain
+select t1.*
+from t1 left join t2 on t2.pk=t2.c and t2.b=t1.a and t1.a=t1.b and t2.c=t2.b
+where t1.d=1;
+
+explain
+select t1.*
+from
+ t1
+ left join
+ t2
+ on (t2.pk=t2.c and t2.b=t1.a and t1.a=t1.b and t2.c=t2.b) or
+ (t2.pk=t2.c and t2.b=t1.a and t1.a=t1.b and t2.c=t2.b)
+where t1.d=1;
+
+--echo #This can't be eliminated:
+explain
+select t1.*
+from
+ t1
+ left join
+ t2
+ on (t2.pk=t2.c and t2.b=t1.a and t2.c=t1.b) or
+ (t2.pk=t2.c and t1.a=t1.b and t2.c=t1.b)
+where t1.d=1;
+
+explain
+select t1.*
+from
+ t1
+ left join
+ t2
+ on (t2.pk=t2.c and t2.b=t1.a and t2.c=t1.b) or
+ (t2.pk=t2.c and t2.c=t1.b)
+;
+
+explain
+select t1.*
+from t1 left join t2 on t2.pk=3 or t2.pk= 4;
+
+explain
+select t1.*
+from t1 left join t2 on t2.pk=3 or t2.pk= 3;
+
+explain
+select t1.*
+from t1 left join t2 on (t2.pk=3 and t2.b=3) or (t2.pk= 4 and t2.b=3);
+
+drop table t1, t2;
=== modified file 'mysql-test/valgrind.supp'
--- mysql-test/valgrind.supp 2009-08-05 07:21:37 +0000
+++ mysql-test/valgrind.supp 2009-08-13 21:12:12 +0000
@@ -703,3 +703,73 @@
fun:malloc
fun:inet_ntoa
}
+
+
+#
+# Some problem inside glibc on Ubuntu 9.04, x86 (but not amd64):
+#
+# ==5985== 19 bytes in 1 blocks are still reachable in loss record 1 of 6
+# ==5985== at 0x7AF3FDE: malloc (vg_replace_malloc.c:207)
+# ... 11,12, or 13 functions w/o symbols ...
+# ==5985== by 0x8717185: nptl_pthread_exit_hack_handler (my_thr_init.c:55)
+#
+# Since valgrind 3.3.0 doesn't support '...' multi-function pattern, using
+# multiple suppressions:
+#
+{
+ Mem loss inside nptl_pthread_exit_hack_handler
+ Memcheck:Leak
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:nptl_pthread_exit_hack_handler
+}
+
+{
+ Mem loss inside nptl_pthread_exit_hack_handler
+ Memcheck:Leak
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:nptl_pthread_exit_hack_handler
+}
+
+{
+ Mem loss inside nptl_pthread_exit_hack_handler
+ Memcheck:Leak
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:*
+ fun:nptl_pthread_exit_hack_handler
+}
+
=== added file 'sql-bench/test-table-elimination.sh'
--- sql-bench/test-table-elimination.sh 1970-01-01 00:00:00 +0000
+++ sql-bench/test-table-elimination.sh 2009-09-01 21:41:16 +0000
@@ -0,0 +1,316 @@
+#!@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";
+
+
+;
+
+####
+#### 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'
--- sql/CMakeLists.txt 2009-09-01 11:59:54 +0000
+++ sql/CMakeLists.txt 2009-09-01 22:20:00 +0000
@@ -74,7 +74,7 @@
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'
--- sql/Makefile.am 2009-03-12 22:27:35 +0000
+++ sql/Makefile.am 2009-06-25 10:05:53 +0000
@@ -121,7 +121,8 @@
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'
--- sql/item.cc 2009-04-25 10:05:32 +0000
+++ sql/item.cc 2009-08-31 20:02:09 +0000
@@ -1915,6 +1915,15 @@
name= (char*) f->field_name;
}
+
+bool Item_field::enumerate_field_refs_processor(uchar *arg)
+{
+ Field_enumerator *fe= (Field_enumerator*)arg;
+ fe->visit_field(field);
+ return FALSE;
+}
+
+
const char *Item_ident::full_name() const
{
char *tmp;
@@ -3380,7 +3389,7 @@
/* 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'
--- sql/item.h 2009-04-25 10:05:32 +0000
+++ sql/item.h 2009-08-31 20:02:09 +0000
@@ -731,7 +731,11 @@
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
+ class Field_enumerator)
+ */
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 @@
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 enumerate_field_refs_processor(uchar *arg) { return 0; }
+ virtual bool mark_as_eliminated_processor(uchar *arg) { return 0; }
/*
Check if a partition function is allowed
SYNOPSIS
@@ -1012,6 +1018,29 @@
};
+/*
+ Class to be used to enumerate all field references in an item tree.
+ Suggested usage:
+
+ class My_enumerator : public Field_enumerator
+ {
+ virtual void visit_field() { ... your actions ...}
+ }
+
+ My_enumerator enumerator;
+ item->walk(Item::enumerate_field_refs_processor, ...,(uchar*)&enumerator);
+
+ This is similar to Visitor pattern.
+*/
+
+class Field_enumerator
+{
+public:
+ virtual void visit_field(Field *field)= 0;
+ virtual ~Field_enumerator() {}; /* purecov: inspected */
+};
+
+
class sp_head;
@@ -1477,6 +1506,7 @@
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 enumerate_field_refs_processor(uchar *arg);
void cleanup();
bool result_as_longlong()
{
@@ -2203,6 +2233,10 @@
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_cmpfunc.cc'
--- sql/item_cmpfunc.cc 2009-04-25 09:04:38 +0000
+++ sql/item_cmpfunc.cc 2009-08-31 20:02:09 +0000
@@ -5168,33 +5168,7 @@
void Item_equal::sort(Item_field_cmpfunc cmp, void *arg)
{
- bool swap;
- List_iterator<Item_field> it(fields);
- do
- {
- Item_field *item1= it++;
- Item_field **ref1= it.ref();
- Item_field *item2;
-
- swap= FALSE;
- while ((item2= it++))
- {
- Item_field **ref2= it.ref();
- if (cmp(item1, item2, arg) < 0)
- {
- Item_field *item= *ref1;
- *ref1= *ref2;
- *ref2= item;
- swap= TRUE;
- }
- else
- {
- item1= item2;
- ref1= ref2;
- }
- }
- it.rewind();
- } while (swap);
+ exchange_sort<Item_field>(&fields, cmp, arg);
}
=== modified file 'sql/item_cmpfunc.h'
--- sql/item_cmpfunc.h 2008-12-12 11:13:11 +0000
+++ sql/item_cmpfunc.h 2009-08-20 15:51:02 +0000
@@ -1578,6 +1578,7 @@
uint members();
bool contains(Field *field);
Item_field* get_first() { return fields.head(); }
+ uint n_fields() { return fields.elements; }
void merge(Item_equal *item);
void update_const();
enum Functype functype() const { return MULT_EQUAL_FUNC; }
=== modified file 'sql/item_subselect.cc'
--- sql/item_subselect.cc 2009-01-31 21:22:44 +0000
+++ sql/item_subselect.cc 2009-08-31 20:02:09 +0000
@@ -39,7 +39,7 @@
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 @@
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 @@
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 @@
fixed= 1;
err:
+ in_fix_fields--;
thd->where= save_where;
return res;
}
+bool Item_subselect::enumerate_field_refs_processor(uchar *arg)
+{
+ List_iterator<Item> it(refers_to);
+ Item *item;
+ while ((item= it++))
+ {
+ if (item->walk(&Item::enumerate_field_refs_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 @@
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'
--- sql/item_subselect.h 2008-02-22 10:30:33 +0000
+++ sql/item_subselect.h 2009-08-31 20:02:09 +0000
@@ -52,8 +52,16 @@
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 @@
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 enumerate_field_refs_processor(uchar *arg);
/**
Get the SELECT_LEX structure associated with this Item.
=== modified file 'sql/item_sum.cc'
--- sql/item_sum.cc 2009-04-25 09:04:38 +0000
+++ sql/item_sum.cc 2009-06-22 11:46:31 +0000
@@ -350,7 +350,7 @@
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 @@
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'
--- sql/item_sum.h 2008-12-09 19:43:10 +0000
+++ sql/item_sum.h 2009-06-25 10:05:53 +0000
@@ -255,6 +255,12 @@
*/
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 @@
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()
=== modified file 'sql/mysql_priv.h'
--- sql/mysql_priv.h 2009-04-25 10:05:32 +0000
+++ sql/mysql_priv.h 2009-08-24 19:10:48 +0000
@@ -528,14 +528,27 @@
#define OPTIMIZER_SWITCH_INDEX_MERGE_UNION 2
#define OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION 4
#define OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT 8
-#define OPTIMIZER_SWITCH_LAST 16
-
+
+#ifdef DBUG_OFF
+# define OPTIMIZER_SWITCH_LAST 16
+#else
+# define OPTIMIZER_SWITCH_TABLE_ELIMINATION 16
+# define OPTIMIZER_SWITCH_LAST 32
+#endif
+
+#ifdef DBUG_OFF
/* The following must be kept in sync with optimizer_switch_str in mysqld.cc */
-#define OPTIMIZER_SWITCH_DEFAULT (OPTIMIZER_SWITCH_INDEX_MERGE | \
- OPTIMIZER_SWITCH_INDEX_MERGE_UNION | \
- OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION | \
- OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT)
-
+# define OPTIMIZER_SWITCH_DEFAULT (OPTIMIZER_SWITCH_INDEX_MERGE | \
+ OPTIMIZER_SWITCH_INDEX_MERGE_UNION | \
+ OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION | \
+ OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT)
+#else
+# define OPTIMIZER_SWITCH_DEFAULT (OPTIMIZER_SWITCH_INDEX_MERGE | \
+ OPTIMIZER_SWITCH_INDEX_MERGE_UNION | \
+ OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION | \
+ OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT | \
+ OPTIMIZER_SWITCH_TABLE_ELIMINATION)
+#endif
/*
Replication uses 8 bytes to store SQL_MODE in the binary log. The day you
=== modified file 'sql/mysqld.cc'
--- sql/mysqld.cc 2009-05-19 09:28:05 +0000
+++ sql/mysqld.cc 2009-08-25 09:27:50 +0000
@@ -297,9 +297,14 @@
static const char *optimizer_switch_names[]=
{
- "index_merge","index_merge_union","index_merge_sort_union",
- "index_merge_intersection", "default", NullS
+ "index_merge","index_merge_union","index_merge_sort_union",
+ "index_merge_intersection",
+#ifndef DBUG_OFF
+ "table_elimination",
+#endif
+ "default", NullS
};
+
/* Corresponding defines are named OPTIMIZER_SWITCH_XXX */
static const unsigned int optimizer_switch_names_len[]=
{
@@ -307,6 +312,9 @@
sizeof("index_merge_union") - 1,
sizeof("index_merge_sort_union") - 1,
sizeof("index_merge_intersection") - 1,
+#ifndef DBUG_OFF
+ sizeof("table_elimination") - 1,
+#endif
sizeof("default") - 1
};
TYPELIB optimizer_switch_typelib= { array_elements(optimizer_switch_names)-1,"",
@@ -382,7 +390,12 @@
/* Text representation for OPTIMIZER_SWITCH_DEFAULT */
static const char *optimizer_switch_str="index_merge=on,index_merge_union=on,"
"index_merge_sort_union=on,"
- "index_merge_intersection=on";
+ "index_merge_intersection=on"
+#ifndef DBUG_OFF
+ ",table_elimination=on";
+#else
+ ;
+#endif
static char *mysqld_user, *mysqld_chroot, *log_error_file_ptr;
static char *opt_init_slave, *language_ptr, *opt_init_connect;
static char *default_character_set_name;
@@ -6929,8 +6942,11 @@
0, GET_ULONG, OPT_ARG, MAX_TABLES+1, 0, MAX_TABLES+2, 0, 1, 0},
{"optimizer_switch", OPT_OPTIMIZER_SWITCH,
"optimizer_switch=option=val[,option=val...], where option={index_merge, "
- "index_merge_union, index_merge_sort_union, index_merge_intersection} and "
- "val={on, off, default}.",
+ "index_merge_union, index_merge_sort_union, index_merge_intersection"
+#ifndef DBUG_OFF
+ ", table_elimination"
+#endif
+ "} and val={on, off, default}.",
(uchar**) &optimizer_switch_str, (uchar**) &optimizer_switch_str, 0, GET_STR, REQUIRED_ARG,
/*OPTIMIZER_SWITCH_DEFAULT*/0,
0, 0, 0, 0, 0},
=== added file 'sql/opt_table_elimination.cc'
--- sql/opt_table_elimination.cc 1970-01-01 00:00:00 +0000
+++ sql/opt_table_elimination.cc 2009-09-01 21:41:16 +0000
@@ -0,0 +1,1853 @@
+/**
+ @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 "my_bit.h"
+#include "sql_select.h"
+
+/*
+ OVERVIEW
+ ========
+
+ This file contains table elimination module. The idea behind table
+ elimination is as follows: suppose we have a left join
+
+ SELECT * FROM t1 LEFT JOIN
+ (t2 JOIN t3) ON t2.primary_key=t1.col AND
+ t2.primary_key=t2.col
+ WHERE ...
+
+ such that
+ * 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),
+ * inner side of the outer join is guaranteed to produce at most one matching
+ record combination for each record combination of outer tables.
+
+ then the inner side of the outer join can be removed from the query, as it
+ will always produce only one record combination (either real or
+ null-complemented one) and we don't care about what that record combination
+ is.
+
+
+ MODULE INTERFACE
+ ================
+
+ The module has one entry point - the eliminate_tables() function, which one
+ needs to call (once) at some point before join optimization.
+ eliminate_tables() operates over the JOIN structures. Logically, it
+ removes the inner tables of an outer join operation together with the
+ operation itself. 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.
+
+ * 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 whether it was eliminated 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.
+
+
+ TABLE ELIMINATION ALGORITHM FOR ONE OUTER JOIN
+ ==============================================
+
+ As described above, we can remove inner side of an outer join if it is
+
+ 1. not referred to from any other parts of the query
+ 2. always produces one matching record combination.
+
+ We check #1 by doing a recursive descent down the join->join_list while
+ maintaining a union of used_tables() attribute of all Item expressions in
+ other parts of the query. When we encounter an outer join, we check if the
+ bitmap of tables on its inner side has intersection with tables that are used
+ elsewhere. No intersection means that inner side of the outer join could
+ potentially be eliminated.
+
+ In order to check #2, one needs to prove that inner side of an outer join
+ is functionally dependent on the outside. The proof is constructed from
+ functional dependencies of intermediate objects:
+
+ - Inner side of outer join is functionally dependent when each of its tables
+ are functionally dependent. (We assume a table is functionally dependent
+ when its dependencies allow to uniquely identify one table record, or no
+ records).
+
+ - Table is functionally dependent when it has got a unique key whose columns
+ are functionally dependent.
+
+ - A column is functionally dependent when we could locate an AND-part of a
+ certain ON clause in form
+
+ tblX.columnY= expr
+
+ where expr is functionally depdendent. expr is functionally dependent when
+ all columns that it refers to are functionally dependent.
+
+ These relationships are modeled as a bipartite directed graph that has
+ dependencies as edges and two kinds of nodes:
+
+ Value nodes:
+ - Table column values (each is a value of tblX.columnY)
+ - Table values (each node represents a table inside the join nest we're
+ trying to eliminate).
+ A value has one attribute, it is either bound (i.e. functionally dependent)
+ or not.
+
+ Module nodes:
+ - Modules representing tblX.colY=expr equalities. Equality module has
+ = incoming edges from columns used in expr
+ = outgoing edge to tblX.colY column.
+ - Nodes representing unique keys. Unique key has
+ = incoming edges from key component value modules
+ = outgoing edge to key's table module
+ - Inner side of outer join module. Outer join module has
+ = incoming edges from table value modules
+ = No outgoing edges. Once we reach it, we know we can eliminate the
+ outer join.
+ A module may depend on multiple values, and hence its primary attribute is
+ the number of its arguments that are not bound.
+
+ The algorithm starts with equality nodes that don't have any incoming edges
+ (their expressions are either constant or depend only on tables that are
+ outside of the outer join in question) and performns a breadth-first
+ traversal. If we reach the outer join nest node, it means outer join is
+ functionally dependent and can be eliminated. Otherwise it cannot be
+ eliminated.
+
+ HANDLING MULTIPLE NESTED OUTER JOINS
+ ====================================
+
+ Outer joins that are not nested one within another are eliminated
+ independently. For nested outer joins we have the following considerations:
+
+ 1. ON expressions from children outer joins must be taken into account
+
+ Consider this example:
+
+ SELECT t0.*
+ FROM
+ t0
+ LEFT JOIN
+ (t1 LEFT JOIN t2 ON t2.primary_key=t1.col1)
+ ON
+ t1.primary_key=t0.col AND t2.col1=t1.col2
+
+ Here we cannot eliminate the "... LEFT JOIN t2 ON ..." part alone because the
+ ON clause of top level outer join has references to table t2.
+ We can eliminate the entire "... LEFT JOIN (t1 LEFT JOIN t2) ON .." part,
+ but in order to do that, we must look at both ON expressions.
+
+ 2. ON expressions of parent outer joins are useless.
+ Consider an example:
+
+ SELECT t0.*
+ FROM
+ t0
+ LEFT JOIN
+ (t1 LEFT JOIN t2 ON some_expr)
+ ON
+ t2.primary_key=t1.col -- (*)
+
+ Here the uppermost ON expression has a clause that gives us functional
+ dependency of table t2 on t1 and hence could be used to eliminate the
+ "... LEFT JOIN t2 ON..." part.
+ However, we would not actually encounter this situation, because before the
+ table elimination we run simplify_joins(), which, among other things, upon
+ seeing a functional dependency condition like (*) will convert the outer join
+ of
+
+ "... LEFT JOIN t2 ON ..."
+
+ into inner join and thus make table elimination not to consider eliminating
+ table t2.
+*/
+
+class Dep_value;
+ class Dep_value_field;
+ class Dep_value_table;
+
+
+class Dep_module;
+ class Dep_module_expr;
+ class Dep_module_goal;
+ class Dep_module_key;
+
+class Dep_analysis_context;
+
+
+/*
+ A value, something that can be bound or not bound. One can also iterate over
+ unbound modules that depend on this value
+*/
+
+class Dep_value : public Sql_alloc
+{
+public:
+ Dep_value(): bound(FALSE) {}
+ virtual ~Dep_value(){} /* purecov: inspected */ /* stop compiler warnings */
+
+ bool is_bound() { return bound; }
+ void make_bound() { bound= TRUE; }
+
+ /* Iteration over unbound modules that depend on this value */
+ typedef char *Iterator;
+ virtual Iterator init_unbound_modules_iter(char *buf)=0;
+ virtual Dep_module* get_next_unbound_module(Dep_analysis_context *dac,
+ Iterator iter) = 0;
+ static const size_t iterator_size;
+protected:
+ bool bound;
+};
+
+
+/*
+ A table field value. There is exactly only one such object for any tblX.fieldY
+ - the field depends on its table and equalities
+ - expressions that use the field are its dependencies
+*/
+
+class Dep_value_field : public Dep_value
+{
+public:
+ Dep_value_field(Dep_value_table *table_arg, Field *field_arg) :
+ table(table_arg), field(field_arg)
+ {}
+
+ Dep_value_table *table; /* Table this field is from */
+ Field *field; /* Field this object is representing */
+
+ /* Iteration over unbound modules that are our dependencies */
+ Iterator init_unbound_modules_iter(char *buf);
+ Dep_module* get_next_unbound_module(Dep_analysis_context *dac,
+ Iterator iter);
+
+ void make_unbound_modules_iter_skip_keys(Iterator iter);
+
+ static const size_t iterator_size;
+private:
+ /*
+ Field_deps that belong to one table form a linked list, ordered by
+ field_index
+ */
+ Dep_value_field *next_table_field;
+
+ /*
+ Offset to bits in Dep_analysis_context::expr_deps (see comment to that
+ member for semantics of the bits).
+ */
+ uint bitmap_offset;
+
+ class Module_iter
+ {
+ public:
+ /* if not null, return this and advance */
+ Dep_module_key *key_dep;
+ /* Otherwise, this and advance */
+ uint equality_no;
+ };
+ friend class Dep_analysis_context;
+ friend class Field_dependency_recorder;
+ friend class Dep_value_table;
+};
+
+const size_t Dep_value_field::iterator_size=
+ ALIGN_SIZE(sizeof(Dep_value_field::Module_iter));
+
+
+/*
+ A table value. There is one Dep_value_table object for every table that can
+ potentially be eliminated.
+
+ Table becomes bound as soon as some of its unique keys becomes bound
+ Once the table is bound:
+ - all of its fields are bound
+ - its embedding outer join has one less unknown argument
+*/
+
+class Dep_value_table : public Dep_value
+{
+public:
+ Dep_value_table(TABLE *table_arg) :
+ table(table_arg), fields(NULL), keys(NULL)
+ {}
+ TABLE *table; /* Table this object is representing */
+ /* Ordered list of fields that belong to this table */
+ Dep_value_field *fields;
+ Dep_module_key *keys; /* Ordered list of Unique keys in this table */
+
+ /* Iteration over unbound modules that are our dependencies */
+ Iterator init_unbound_modules_iter(char *buf);
+ Dep_module* get_next_unbound_module(Dep_analysis_context *dac,
+ Iterator iter);
+ static const size_t iterator_size;
+private:
+ class Module_iter
+ {
+ public:
+ /* Space for field iterator */
+ char buf[Dep_value_field::iterator_size];
+ /* !NULL <=> iterating over depdenent modules of this field */
+ Dep_value_field *field_dep;
+ bool returned_goal;
+ };
+};
+
+
+const size_t Dep_value_table::iterator_size=
+ ALIGN_SIZE(sizeof(Dep_value_table::Module_iter));
+
+const size_t Dep_value::iterator_size=
+ max(Dep_value_table::iterator_size, Dep_value_field::iterator_size);
+
+
+/*
+ A 'module'. Module has unsatisfied dependencies, number of whose is stored in
+ unbound_args. Modules also can be linked together in a list.
+*/
+
+class Dep_module : public Sql_alloc
+{
+public:
+ virtual ~Dep_module(){} /* purecov: inspected */ /* stop compiler warnings */
+
+ /* Mark as bound. Currently is non-virtual and does nothing */
+ void make_bound() {};
+
+ /*
+ The final module will return TRUE here. When we see that TRUE was returned,
+ that will mean that functional dependency check succeeded.
+ */
+ virtual bool is_final () { return FALSE; }
+
+ /*
+ Increment number of bound arguments. this is expected to change
+ is_applicable() from false to true after sufficient set of arguments is
+ bound.
+ */
+ void touch() { unbound_args--; }
+ bool is_applicable() { return !test(unbound_args); }
+
+ /* Iteration over values that */
+ typedef char *Iterator;
+ virtual Iterator init_unbound_values_iter(char *buf)=0;
+ virtual Dep_value* get_next_unbound_value(Dep_analysis_context *dac,
+ Iterator iter)=0;
+ static const size_t iterator_size;
+protected:
+ uint unbound_args;
+
+ Dep_module() : unbound_args(0) {}
+ /* to bump unbound_args when constructing depedendencies */
+ friend class Field_dependency_recorder;
+ friend class Dep_analysis_context;
+};
+
+
+/*
+ This represents either
+ - "tbl.column= expr" equality dependency, i.e. tbl.column depends on fields
+ used in the expression, or
+ - tbl1.col1=tbl2.col2=... multi-equality.
+*/
+
+class Dep_module_expr : public Dep_module
+{
+public:
+ Dep_value_field *field;
+ Item *expr;
+
+ List<Dep_value_field> *mult_equal_fields;
+ /* Used during condition analysis only, similar to KEYUSE::level */
+ uint level;
+
+ Iterator init_unbound_values_iter(char *buf);
+ Dep_value* get_next_unbound_value(Dep_analysis_context *dac, Iterator iter);
+ static const size_t iterator_size;
+private:
+ class Value_iter
+ {
+ public:
+ Dep_value_field *field;
+ List_iterator<Dep_value_field> it;
+ };
+};
+
+const size_t Dep_module_expr::iterator_size=
+ ALIGN_SIZE(sizeof(Dep_module_expr::Value_iter));
+
+
+/*
+ A Unique key module
+ - Unique key has all of its components as arguments
+ - Once unique key is bound, its table value is known
+*/
+
+class Dep_module_key: public Dep_module
+{
+public:
+ Dep_module_key(Dep_value_table *table_arg, uint keyno_arg, uint n_parts_arg) :
+ table(table_arg), keyno(keyno_arg), next_table_key(NULL)
+ {
+ unbound_args= n_parts_arg;
+ }
+ Dep_value_table *table; /* Table this key is from */
+ uint keyno; /* The index we're representing */
+ /* Unique keys form a linked list, ordered by keyno */
+ Dep_module_key *next_table_key;
+
+ Iterator init_unbound_values_iter(char *buf);
+ Dep_value* get_next_unbound_value(Dep_analysis_context *dac, Iterator iter);
+ static const size_t iterator_size;
+private:
+ class Value_iter
+ {
+ public:
+ Dep_value_table *table;
+ };
+};
+
+const size_t Dep_module_key::iterator_size=
+ ALIGN_SIZE(sizeof(Dep_module_key::Value_iter));
+
+const size_t Dep_module::iterator_size=
+ max(Dep_module_expr::iterator_size, Dep_module_key::iterator_size);
+
+
+/*
+ A module that represents outer join that we're trying to eliminate. If we
+ manage to declare this module to be bound, then outer join can be eliminated.
+*/
+
+class Dep_module_goal: public Dep_module
+{
+public:
+ Dep_module_goal(uint n_children)
+ {
+ unbound_args= n_children;
+ }
+ bool is_final() { return TRUE; }
+ /*
+ This is the goal module, so the running wave algorithm should terminate
+ once it sees that this module is applicable and should never try to apply
+ it, hence no use for unbound value iterator implementation.
+ */
+ Iterator init_unbound_values_iter(char *buf)
+ {
+ DBUG_ASSERT(0);
+ return NULL;
+ }
+ Dep_value* get_next_unbound_value(Dep_analysis_context *dac, Iterator iter)
+ {
+ DBUG_ASSERT(0);
+ return NULL;
+ }
+};
+
+
+/*
+ Functional dependency analyzer context
+*/
+class Dep_analysis_context
+{
+public:
+ bool setup_equality_modules_deps(List<Dep_module> *bound_modules);
+ bool run_wave(List<Dep_module> *new_bound_modules);
+
+ /* Tables that we're looking at eliminating */
+ table_map usable_tables;
+
+ /* Array of equality dependencies */
+ Dep_module_expr *equality_mods;
+ uint n_equality_mods; /* Number of elements in the array */
+ uint n_equality_mods_alloced;
+
+ /* tablenr -> Dep_value_table* mapping. */
+ Dep_value_table *table_deps[MAX_KEY];
+
+ /* Element for the outer join we're attempting to eliminate */
+ Dep_module_goal *outer_join_dep;
+
+ /*
+ Bitmap of how expressions depend on bits. Given a Dep_value_field object,
+ one can check bitmap_is_set(expr_deps, field_val->bitmap_offset + expr_no)
+ to see if expression equality_mods[expr_no] depends on the given field.
+ */
+ MY_BITMAP expr_deps;
+
+ Dep_value_table *create_table_value(TABLE *table);
+ Dep_value_field *get_field_value(Field *field);
+
+#ifndef DBUG_OFF
+ void dbug_print_deps();
+#endif
+};
+
+
+void eliminate_tables(JOIN *join);
+
+static bool
+eliminate_tables_for_list(JOIN *join,
+ List<TABLE_LIST> *join_list,
+ table_map tables_in_list,
+ Item *on_expr,
+ table_map tables_used_elsewhere);
+static
+bool check_func_dependency(JOIN *join,
+ table_map dep_tables,
+ List_iterator<TABLE_LIST> *it,
+ TABLE_LIST *oj_tbl,
+ Item* cond);
+static
+void build_eq_mods_for_cond(Dep_analysis_context *dac,
+ Dep_module_expr **eq_mod, uint *and_level,
+ Item *cond);
+static
+void check_equality(Dep_analysis_context *dac, Dep_module_expr **eq_mod,
+ uint and_level, Item_func *cond, Item *left, Item *right);
+static
+Dep_module_expr *merge_eq_mods(Dep_module_expr *start,
+ Dep_module_expr *new_fields,
+ Dep_module_expr *end, uint and_level);
+static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl);
+static
+void add_module_expr(Dep_analysis_context *dac, Dep_module_expr **eq_mod,
+ uint and_level, Dep_value_field *field_val, Item *right,
+ List<Dep_value_field>* mult_equal_fields);
+
+
+/*****************************************************************************/
+
+/*
+ Perform table elimination
+
+ SYNOPSIS
+ eliminate_tables()
+ join Join to work on
+
+ DESCRIPTION
+ This is the entry point for table elimination. Grep for MODULE INTERFACE
+ section in this file for calling convention.
+
+ The idea behind table elimination is that if we have an outer join:
+
+ SELECT * FROM t1 LEFT JOIN
+ (t2 JOIN t3) ON t2.primary_key=t1.col AND
+ t3.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.
+
+ After this, if #1 is met, the function calls eliminate_tables_for_list()
+ that checks #2.
+
+ SIDE EFFECTS
+ See the OVERVIEW section at the top of this file.
+
+*/
+
+void eliminate_tables(JOIN *join)
+{
+ THD* thd= join->thd;
+ 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;
+
+#ifndef DBUG_OFF
+ if (!optimizer_flag(thd, OPTIMIZER_SWITCH_TABLE_ELIMINATION))
+ DBUG_VOID_RETURN; /* purecov: inspected */
+#endif
+
+ /* 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();
+ }
+
+ if (join->select_lex == &thd->lex->select_lex)
+ {
+
+ /* Multi-table UPDATE: don't eliminate tables referred from SET statement */
+ if (thd->lex->sql_command == SQLCOM_UPDATE_MULTI)
+ {
+ /* Multi-table UPDATE and DELETE: don't eliminate the tables we modify: */
+ used_tables |= thd->table_map_for_update;
+ List_iterator<Item> it2(thd->lex->value_list);
+ while ((item= it2++))
+ used_tables |= item->used_tables();
+ }
+
+ if (thd->lex->sql_command == SQLCOM_DELETE_MULTI)
+ {
+ TABLE_LIST *tbl;
+ for (tbl= (TABLE_LIST*)thd->lex->auxiliary_table_list.first;
+ tbl; tbl= tbl->next_local)
+ {
+ used_tables |= tbl->table->map;
+ }
+ }
+ }
+
+ table_map all_tables= join->all_tables_map();
+ if (all_tables & ~used_tables)
+ {
+ /* There are some tables that we probably could eliminate. Try it. */
+ eliminate_tables_for_list(join, join->join_list, all_tables, NULL,
+ used_tables);
+ }
+ DBUG_VOID_RETURN;
+}
+
+
+/*
+ Perform table elimination in a given join list
+
+ SYNOPSIS
+ eliminate_tables_for_list()
+ join The join we're working on
+ join_list Join list to eliminate tables from (and if
+ on_expr !=NULL, then try eliminating join_list
+ itself)
+ list_tables Bitmap of tables embedded in the join_list.
+ on_expr ON expression, if the join list is the inner side
+ of an outer join.
+ NULL means it's not an outer join but rather a
+ top-level join list.
+ tables_used_elsewhere Bitmap of tables that are referred to from
+ somewhere outside of the join list (e.g.
+ select list, HAVING, other ON expressions, etc).
+
+ DESCRIPTION
+ Perform table elimination in a given join list:
+ - First, walk through join list members and try doing table elimination for
+ them.
+ - Then, if the join list itself is an inner side of outer join
+ (on_expr!=NULL), then try to eliminate the entire join list.
+
+ See "HANDLING MULTIPLE NESTED OUTER JOINS" section at the top of this file
+ for more detailed description and justification.
+
+ RETURN
+ TRUE The entire join list eliminated
+ FALSE Join list wasn't eliminated (but some of its child outer joins
+ possibly were)
+*/
+
+static bool
+eliminate_tables_for_list(JOIN *join, List<TABLE_LIST> *join_list,
+ table_map list_tables, Item *on_expr,
+ table_map tables_used_elsewhere)
+{
+ TABLE_LIST *tbl;
+ List_iterator<TABLE_LIST> it(*join_list);
+ table_map tables_used_on_left= 0;
+ bool all_eliminated= TRUE;
+
+ while ((tbl= it++))
+ {
+ if (tbl->on_expr)
+ {
+ table_map outside_used_tables= tables_used_elsewhere |
+ tables_used_on_left;
+ if (tbl->nested_join)
+ {
+ /* This is "... LEFT JOIN (join_nest) ON cond" */
+ if (eliminate_tables_for_list(join,
+ &tbl->nested_join->join_list,
+ tbl->nested_join->used_tables,
+ tbl->on_expr,
+ outside_used_tables))
+ {
+ mark_as_eliminated(join, tbl);
+ }
+ else
+ all_eliminated= FALSE;
+ }
+ else
+ {
+ /* This is "... LEFT JOIN tbl ON cond" */
+ if (!(tbl->table->map & outside_used_tables) &&
+ check_func_dependency(join, tbl->table->map, NULL, tbl,
+ tbl->on_expr))
+ {
+ mark_as_eliminated(join, tbl);
+ }
+ else
+ all_eliminated= FALSE;
+ }
+ tables_used_on_left |= tbl->on_expr->used_tables();
+ }
+ else
+ {
+ DBUG_ASSERT(!tbl->nested_join);
+ }
+ }
+
+ /* Try eliminating the nest we're called for */
+ if (all_eliminated && on_expr && !(list_tables & tables_used_elsewhere))
+ {
+ it.rewind();
+ return check_func_dependency(join, list_tables & ~join->eliminated_tables,
+ &it, NULL, on_expr);
+ }
+ return FALSE; /* not eliminated */
+}
+
+
+/*
+ Check if given condition makes given set of tables functionally dependent
+
+ SYNOPSIS
+ check_func_dependency()
+ join Join we're procesing
+ dep_tables Tables that we check to be functionally dependent (on
+ everything else)
+ it Iterator that enumerates these tables, or NULL if we're
+ checking one single table and it is specified in oj_tbl
+ parameter.
+ oj_tbl NULL, or one single table that we're checking
+ cond Condition to use to prove functional dependency
+
+ DESCRIPTION
+ Check if we can use given condition to infer that the set of given tables
+ is functionally dependent on everything else.
+
+ RETURN
+ TRUE - Yes, functionally dependent
+ FALSE - No, or error
+*/
+
+static
+bool check_func_dependency(JOIN *join,
+ table_map dep_tables,
+ List_iterator<TABLE_LIST> *it,
+ TABLE_LIST *oj_tbl,
+ Item* cond)
+{
+ Dep_analysis_context dac;
+
+ /*
+ Pre-alloc some Dep_module_expr structures. We don't need this to be
+ guaranteed upper bound.
+ */
+ dac.n_equality_mods_alloced=
+ join->thd->lex->current_select->max_equal_elems +
+ (join->thd->lex->current_select->cond_count+1)*2 +
+ join->thd->lex->current_select->between_count;
+
+ bzero(dac.table_deps, sizeof(dac.table_deps));
+ if (!(dac.equality_mods= new Dep_module_expr[dac.n_equality_mods_alloced]))
+ return FALSE; /* purecov: inspected */
+
+ Dep_module_expr* last_eq_mod= dac.equality_mods;
+
+ /* Create Dep_value_table objects for all tables we're trying to eliminate */
+ if (oj_tbl)
+ {
+ if (!dac.create_table_value(oj_tbl->table))
+ return FALSE; /* purecov: inspected */
+ }
+ else
+ {
+ TABLE_LIST *tbl;
+ while ((tbl= (*it)++))
+ {
+ if (tbl->table && (tbl->table->map & dep_tables))
+ {
+ if (!dac.create_table_value(tbl->table))
+ return FALSE; /* purecov: inspected */
+ }
+ }
+ }
+ dac.usable_tables= dep_tables;
+
+ /*
+ Analyze the the ON expression and create Dep_module_expr objects and
+ Dep_value_field objects for the used fields.
+ */
+ uint and_level=0;
+ build_eq_mods_for_cond(&dac, &last_eq_mod, &and_level, cond);
+ if (!(dac.n_equality_mods= last_eq_mod - dac.equality_mods))
+ return FALSE; /* No useful conditions */
+
+ List<Dep_module> bound_modules;
+
+ if (!(dac.outer_join_dep= new Dep_module_goal(my_count_bits(dep_tables))) ||
+ dac.setup_equality_modules_deps(&bound_modules))
+ {
+ return FALSE; /* OOM, default to non-dependent */ /* purecov: inspected */
+ }
+
+ DBUG_EXECUTE("test", dac.dbug_print_deps(); );
+
+ return dac.run_wave(&bound_modules);
+}
+
+
+/*
+ Running wave functional dependency check algorithm
+
+ SYNOPSIS
+ Dep_analysis_context::run_wave()
+ new_bound_modules List of bound modules to start the running wave from.
+ The list is destroyed during execution
+
+ DESCRIPTION
+ This function uses running wave algorithm to check if the join nest is
+ functionally-dependent.
+ We start from provided list of bound modules, and then run the wave across
+ dependency edges, trying the reach the Dep_module_goal module. If we manage
+ to reach it, then the join nest is functionally-dependent, otherwise it is
+ not.
+
+ RETURN
+ TRUE Yes, functionally dependent
+ FALSE No.
+*/
+
+bool Dep_analysis_context::run_wave(List<Dep_module> *new_bound_modules)
+{
+ List<Dep_value> new_bound_values;
+
+ Dep_value *value;
+ Dep_module *module;
+
+ while (!new_bound_modules->is_empty())
+ {
+ /*
+ The "wave" is in new_bound_modules list. Iterate over values that can be
+ reached from these modules but are not yet bound, and collect the next
+ wave generation in new_bound_values list.
+ */
+ List_iterator<Dep_module> modules_it(*new_bound_modules);
+ while ((module= modules_it++))
+ {
+ char iter_buf[Dep_module::iterator_size];
+ Dep_module::Iterator iter;
+ iter= module->init_unbound_values_iter(iter_buf);
+ while ((value= module->get_next_unbound_value(this, iter)))
+ {
+ value->make_bound();
+ new_bound_values.push_back(value);
+ }
+ }
+ new_bound_modules->empty();
+
+ /*
+ Now walk over list of values we've just found to be bound and check which
+ unbound modules can be reached from them. If there are some modules that
+ became bound, collect them in new_bound_modules list.
+ */
+ List_iterator<Dep_value> value_it(new_bound_values);
+ while ((value= value_it++))
+ {
+ char iter_buf[Dep_value::iterator_size];
+ Dep_value::Iterator iter;
+ iter= value->init_unbound_modules_iter(iter_buf);
+ while ((module= value->get_next_unbound_module(this, iter)))
+ {
+ module->touch();
+ if (!module->is_applicable())
+ continue;
+ if (module->is_final())
+ return TRUE; /* Functionally dependent */
+ module->make_bound();
+ new_bound_modules->push_back(module);
+ }
+ }
+ new_bound_values.empty();
+ }
+ return FALSE;
+}
+
+
+/*
+ This is used to analyze expressions in "tbl.col=expr" dependencies so
+ that we can figure out which fields the expression depends on.
+*/
+
+class Field_dependency_recorder : public Field_enumerator
+{
+public:
+ Field_dependency_recorder(Dep_analysis_context *ctx_arg): ctx(ctx_arg)
+ {}
+
+ void visit_field(Field *field)
+ {
+ Dep_value_table *tbl_dep;
+ if ((tbl_dep= ctx->table_deps[field->table->tablenr]))
+ {
+ for (Dep_value_field *field_dep= tbl_dep->fields; field_dep;
+ field_dep= field_dep->next_table_field)
+ {
+ if (field->field_index == field_dep->field->field_index)
+ {
+ uint offs= field_dep->bitmap_offset + expr_offset;
+ if (!bitmap_is_set(&ctx->expr_deps, offs))
+ ctx->equality_mods[expr_offset].unbound_args++;
+ bitmap_set_bit(&ctx->expr_deps, offs);
+ return;
+ }
+ }
+ /*
+ We got here if didn't find this field. It's not a part of
+ a unique key, and/or there is no field=expr element for it.
+ Bump the dependency anyway, this will signal that this dependency
+ cannot be satisfied.
+ */
+ ctx->equality_mods[expr_offset].unbound_args++;
+ }
+ else
+ visited_other_tables= TRUE;
+ }
+
+ Dep_analysis_context *ctx;
+ /* Offset of the expression we're processing in the dependency bitmap */
+ uint expr_offset;
+
+ bool visited_other_tables;
+};
+
+
+
+
+/*
+ Setup inbound dependency relationships for tbl.col=expr equalities
+
+ SYNOPSIS
+ setup_equality_modules_deps()
+ bound_deps_list Put here modules that were found not to depend on
+ any non-bound columns.
+
+ DESCRIPTION
+ Setup inbound dependency relationships for tbl.col=expr equalities:
+ - allocate a bitmap where we store such dependencies
+ - for each "tbl.col=expr" equality, analyze the expr part and find out
+ which fields it refers to and set appropriate dependencies.
+
+ RETURN
+ FALSE OK
+ TRUE Out of memory
+*/
+
+bool Dep_analysis_context::setup_equality_modules_deps(List<Dep_module>
+ *bound_modules)
+{
+ DBUG_ENTER("setup_equality_modules_deps");
+
+ /*
+ Count Dep_value_field objects and assign each of them a unique
+ bitmap_offset value.
+ */
+ uint offset= 0;
+ for (Dep_value_table **tbl_dep= table_deps;
+ tbl_dep < table_deps + MAX_TABLES;
+ tbl_dep++)
+ {
+ if (*tbl_dep)
+ {
+ for (Dep_value_field *field_dep= (*tbl_dep)->fields;
+ field_dep;
+ field_dep= field_dep->next_table_field)
+ {
+ field_dep->bitmap_offset= offset;
+ offset += n_equality_mods;
+ }
+ }
+ }
+
+ void *buf;
+ if (!(buf= current_thd->alloc(bitmap_buffer_size(offset))) ||
+ bitmap_init(&expr_deps, (my_bitmap_map*)buf, offset, FALSE))
+ {
+ DBUG_RETURN(TRUE); /* purecov: inspected */
+ }
+ bitmap_clear_all(&expr_deps);
+
+ /*
+ Analyze all "field=expr" dependencies, and have expr_deps encode
+ dependencies of expressions from fields.
+
+ Also collect a linked list of equalities that are bound.
+ */
+ Field_dependency_recorder deps_recorder(this);
+ for (Dep_module_expr *eq_mod= equality_mods;
+ eq_mod < equality_mods + n_equality_mods;
+ eq_mod++)
+ {
+ deps_recorder.expr_offset= eq_mod - equality_mods;
+ deps_recorder.visited_other_tables= FALSE;
+ eq_mod->unbound_args= 0;
+
+ if (eq_mod->field)
+ {
+ /* Regular tbl.col=expr(tblX1.col1, tblY1.col2, ...) */
+ eq_mod->expr->walk(&Item::enumerate_field_refs_processor, FALSE,
+ (uchar*)&deps_recorder);
+ }
+ else
+ {
+ /* It's a multi-equality */
+ eq_mod->unbound_args= !test(eq_mod->expr);
+ List_iterator<Dep_value_field> it(*eq_mod->mult_equal_fields);
+ Dep_value_field* field_val;
+ while ((field_val= it++))
+ {
+ uint offs= field_val->bitmap_offset + eq_mod - equality_mods;
+ bitmap_set_bit(&expr_deps, offs);
+ }
+ }
+
+ if (!eq_mod->unbound_args)
+ bound_modules->push_back(eq_mod);
+ }
+
+ DBUG_RETURN(FALSE);
+}
+
+
+/*
+ Ordering that we're using whenever we need to maintain a no-duplicates list
+ of field value objects.
+*/
+
+static
+int compare_field_values(Dep_value_field *a, Dep_value_field *b, void *unused)
+{
+ uint a_ratio= a->field->table->tablenr*MAX_FIELDS +
+ a->field->field_index;
+
+ uint b_ratio= b->field->table->tablenr*MAX_FIELDS +
+ b->field->field_index;
+ return (a_ratio < b_ratio)? -1 : ((a_ratio == b_ratio)? 0 : 1);
+}
+
+
+/*
+ Produce Dep_module_expr elements for given condition.
+
+ SYNOPSIS
+ build_eq_mods_for_cond()
+ ctx Table elimination context
+ eq_mod INOUT Put produced equality conditions here
+ and_level INOUT AND-level (like in add_key_fields)
+ cond Condition to process
+
+ DESCRIPTION
+ Analyze the given condition and produce an array of Dep_module_expr
+ dependencies from it. The idea of analysis is as follows:
+ There are useful equalities that have form
+
+ eliminable_tbl.field = expr (denote as useful_equality)
+
+ The condition is composed of useful equalities and other conditions that
+ are combined together with AND and OR operators. We process the condition
+ in recursive fashion according to these basic rules:
+
+ useful_equality1 AND useful_equality2 -> make array of two
+ Dep_module_expr objects
+
+ useful_equality AND other_cond -> discard other_cond
+
+ useful_equality OR other_cond -> discard everything
+
+ useful_equality1 OR useful_equality2 -> check if both sides of OR are the
+ same equality. If yes, that's the
+ result, otherwise discard
+ everything.
+
+ The rules are used to map the condition into an array Dep_module_expr
+ elements. The array will specify functional dependencies that logically
+ follow from the condition.
+
+ SEE ALSO
+ This function is modeled after add_key_fields()
+*/
+
+static
+void build_eq_mods_for_cond(Dep_analysis_context *ctx,
+ Dep_module_expr **eq_mod,
+ uint *and_level, Item *cond)
+{
+ if (cond->type() == Item_func::COND_ITEM)
+ {
+ List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
+ uint orig_offset= *eq_mod - ctx->equality_mods;
+
+ /* AND/OR */
+ if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
+ {
+ Item *item;
+ while ((item=li++))
+ build_eq_mods_for_cond(ctx, eq_mod, and_level, item);
+
+ for (Dep_module_expr *mod_exp= ctx->equality_mods + orig_offset;
+ mod_exp != *eq_mod ; mod_exp++)
+ {
+ mod_exp->level= *and_level;
+ }
+ }
+ else
+ {
+ Item *item;
+ (*and_level)++;
+ build_eq_mods_for_cond(ctx, eq_mod, and_level, li++);
+ while ((item=li++))
+ {
+ Dep_module_expr *start_key_fields= *eq_mod;
+ (*and_level)++;
+ build_eq_mods_for_cond(ctx, eq_mod, and_level, item);
+ *eq_mod= merge_eq_mods(ctx->equality_mods + orig_offset,
+ start_key_fields, *eq_mod,
+ ++(*and_level));
+ }
+ }
+ return;
+ }
+
+ if (cond->type() != Item::FUNC_ITEM)
+ return;
+
+ Item_func *cond_func= (Item_func*) cond;
+ Item **args= cond_func->arguments();
+
+ switch (cond_func->functype()) {
+ case Item_func::BETWEEN:
+ {
+ Item *fld;
+ if (!((Item_func_between*)cond)->negated &&
+ (fld= args[0]->real_item())->type() == Item::FIELD_ITEM &&
+ args[1]->eq(args[2], ((Item_field*)fld)->field->binary()))
+ {
+ check_equality(ctx, eq_mod, *and_level, cond_func, args[0], args[1]);
+ check_equality(ctx, eq_mod, *and_level, cond_func, args[1], args[0]);
+ }
+ break;
+ }
+ case Item_func::EQ_FUNC:
+ case Item_func::EQUAL_FUNC:
+ {
+ check_equality(ctx, eq_mod, *and_level, cond_func, args[0], args[1]);
+ check_equality(ctx, eq_mod, *and_level, cond_func, args[1], args[0]);
+ break;
+ }
+ case Item_func::ISNULL_FUNC:
+ {
+ Item *tmp=new Item_null;
+ if (tmp)
+ check_equality(ctx, eq_mod, *and_level, cond_func, args[0], tmp);
+ break;
+ }
+ case Item_func::MULT_EQUAL_FUNC:
+ {
+ /*
+ The condition is a
+
+ tbl1.field1 = tbl2.field2 = tbl3.field3 [= const_expr]
+
+ multiple-equality. Do two things:
+ - Collect List<Dep_value_field> of tblX.colY where tblX is one of the
+ tables we're trying to eliminate.
+ - rembember if there was a bound value, either const_expr or tblY.colZ
+ swher tblY is not a table that we're trying to eliminate.
+ Store all collected information in a Dep_module_expr object.
+ */
+ Item_equal *item_equal= (Item_equal*)cond;
+ List<Dep_value_field> *fvl;
+ if (!(fvl= new List<Dep_value_field>))
+ break; /* purecov: inspected */
+
+ Item_equal_iterator it(*item_equal);
+ Item_field *item;
+ Item *bound_item= item_equal->get_const();
+ while ((item= it++))
+ {
+ if ((item->used_tables() & ctx->usable_tables))
+ {
+ Dep_value_field *field_val;
+ if ((field_val= ctx->get_field_value(item->field)))
+ fvl->push_back(field_val);
+ }
+ else
+ {
+ if (!bound_item)
+ bound_item= item;
+ }
+ }
+ exchange_sort<Dep_value_field>(fvl, compare_field_values, NULL);
+ add_module_expr(ctx, eq_mod, *and_level, NULL, bound_item, fvl);
+ break;
+ }
+ default:
+ break;
+ }
+}
+
+
+/*
+ Perform an OR operation on two (adjacent) Dep_module_expr arrays.
+
+ SYNOPSIS
+ merge_eq_mods()
+ start Start of left OR-part
+ new_fields Start of right OR-part
+ end End of right OR-part
+ and_level AND-level (like in add_key_fields)
+
+ DESCRIPTION
+ This function is invoked for two adjacent arrays of Dep_module_expr elements:
+
+ $LEFT_PART $RIGHT_PART
+ +-----------------------+-----------------------+
+ start new_fields end
+
+ The goal is to produce an array which would correspond to the combined
+
+ $LEFT_PART OR $RIGHT_PART
+
+ condition. This is achieved as follows: First, we apply distrubutive law:
+
+ (fdep_A_1 AND fdep_A_2 AND ...) OR (fdep_B_1 AND fdep_B_2 AND ...) =
+
+ = AND_ij (fdep_A_[i] OR fdep_B_[j])
+
+ Then we walk over the obtained "fdep_A_[i] OR fdep_B_[j]" pairs, and
+ - Discard those that that have left and right part referring to different
+ columns. We can't infer anything useful from "col1=expr1 OR col2=expr2".
+ - When left and right parts refer to the same column, we check if they are
+ essentially the same.
+ = If they are the same, we keep one copy
+ "t.col=expr OR t.col=expr" -> "t.col=expr
+ = if they are different , then we discard both
+ "t.col=expr1 OR t.col=expr2" -> (nothing useful)
+
+ (no per-table or for-index FUNC_DEPS exist yet at this phase).
+
+ See also merge_key_fields().
+
+ RETURN
+ End of the result array
+*/
+
+static
+Dep_module_expr *merge_eq_mods(Dep_module_expr *start,
+ Dep_module_expr *new_fields,
+ Dep_module_expr *end, uint and_level)
+{
+ if (start == new_fields)
+ return start; /* (nothing) OR (...) -> (nothing) */
+ if (new_fields == end)
+ return start; /* (...) OR (nothing) -> (nothing) */
+
+ Dep_module_expr *first_free= new_fields;
+
+ for (; new_fields != end ; new_fields++)
+ {
+ for (Dep_module_expr *old=start ; old != first_free ; old++)
+ {
+ if (old->field == new_fields->field)
+ {
+ if (!old->field)
+ {
+ /*
+ OR-ing two multiple equalities. We must compute an intersection of
+ used fields, and check the constants according to these rules:
+
+ a=b=c=d OR a=c=e=f -> a=c (compute intersection)
+ a=const1 OR a=b -> (nothing)
+ a=const1 OR a=const1 -> a=const1
+ a=const1 OR a=const2 -> (nothing)
+
+ If we're performing an OR operation over multiple equalities, e.g.
+
+ (a=b=c AND p=q) OR (a=b AND v=z)
+
+ then we'll need to try combining each equality with each. ANDed
+ equalities are guaranteed to be disjoint, so we'll only get one
+ hit.
+ */
+ Field *eq_field= old->mult_equal_fields->head()->field;
+ if (old->expr && new_fields->expr &&
+ old->expr->eq_by_collation(new_fields->expr, eq_field->binary(),
+ eq_field->charset()))
+ {
+ /* Ok, keep */
+ }
+ else
+ {
+ /* no single constant/bound item. */
+ old->expr= NULL;
+ }
+
+ List <Dep_value_field> *fv;
+ if (!(fv= new List<Dep_value_field>))
+ break; /* purecov: inspected */
+
+ List_iterator<Dep_value_field> it1(*old->mult_equal_fields);
+ List_iterator<Dep_value_field> it2(*new_fields->mult_equal_fields);
+ Dep_value_field *lfield= it1++;
+ Dep_value_field *rfield= it2++;
+ /* Intersect two ordered lists */
+ while (lfield && rfield)
+ {
+ if (lfield == rfield)
+ {
+ fv->push_back(lfield);
+ lfield=it1++;
+ rfield=it2++;
+ }
+ else
+ {
+ if (compare_field_values(lfield, rfield, NULL) < 0)
+ lfield= it1++;
+ else
+ rfield= it2++;
+ }
+ }
+
+ if (fv->elements + test(old->expr) > 1)
+ {
+ old->mult_equal_fields= fv;
+ old->level= and_level;
+ }
+ }
+ else if (!new_fields->expr->const_item())
+ {
+ /*
+ If the value matches, we can use the key reference.
+ If not, we keep it until we have examined all new values
+ */
+ if (old->expr->eq(new_fields->expr,
+ old->field->field->binary()))
+ {
+ old->level= and_level;
+ }
+ }
+ else if (old->expr->eq_by_collation(new_fields->expr,
+ old->field->field->binary(),
+ old->field->field->charset()))
+ {
+ old->level= and_level;
+ }
+ else
+ {
+ /* The expressions are different. */
+ if (old == --first_free) // If last item
+ break;
+ *old= *first_free; // Remove old value
+ old--; // Retry this value
+ }
+ }
+ }
+ }
+
+ /*
+ Ok, the results are within the [start, first_free) range, and the useful
+ elements have level==and_level. Now, remove all unusable elements:
+ */
+ for (Dep_module_expr *old=start ; old != first_free ;)
+ {
+ if (old->level != and_level)
+ { // Not used in all levels
+ if (old == --first_free)
+ break;
+ *old= *first_free; // Remove old value
+ continue;
+ }
+ old++;
+ }
+ return first_free;
+}
+
+
+/*
+ Add an Dep_module_expr element for left=right condition
+
+ SYNOPSIS
+ check_equality()
+ fda Table elimination context
+ eq_mod INOUT Store created Dep_module_expr here and increment ptr if
+ you do so
+ and_level AND-level (like in add_key_fields)
+ cond Condition we've inferred the left=right equality from.
+ left Left expression
+ right Right expression
+ usable_tables Create Dep_module_expr only if Left_expression's table
+ belongs to this set.
+
+ DESCRIPTION
+ Check if the passed left=right equality is such that
+ - 'left' is an Item_field referring to a field in a table we're checking
+ to be functionally depdendent,
+ - the equality allows to conclude that 'left' expression is functionally
+ dependent on the 'right',
+ and if so, create an Dep_module_expr object.
+*/
+
+static
+void check_equality(Dep_analysis_context *ctx, Dep_module_expr **eq_mod,
+ uint and_level, Item_func *cond, Item *left, Item *right)
+{
+ if ((left->used_tables() & ctx->usable_tables) &&
+ !(right->used_tables() & RAND_TABLE_BIT) &&
+ left->real_item()->type() == Item::FIELD_ITEM)
+ {
+ Field *field= ((Item_field*)left->real_item())->field;
+ if (field->result_type() == STRING_RESULT)
+ {
+ if (right->result_type() != STRING_RESULT)
+ {
+ if (field->cmp_type() != right->result_type())
+ return;
+ }
+ else
+ {
+ /*
+ We can't assume there's a functional dependency if the effective
+ collation of the operation differ from the field collation.
+ */
+ if (field->cmp_type() == STRING_RESULT &&
+ ((Field_str*)field)->charset() != cond->compare_collation())
+ return;
+ }
+ }
+ Dep_value_field *field_val;
+ if ((field_val= ctx->get_field_value(field)))
+ add_module_expr(ctx, eq_mod, and_level, field_val, right, NULL);
+ }
+}
+
+
+/*
+ Add a Dep_module_expr object with the specified parameters.
+
+ DESCRIPTION
+ Add a Dep_module_expr object with the specified parameters. Re-allocate
+ the ctx->equality_mods array if it has no space left.
+*/
+
+static
+void add_module_expr(Dep_analysis_context *ctx, Dep_module_expr **eq_mod,
+ uint and_level, Dep_value_field *field_val,
+ Item *right, List<Dep_value_field>* mult_equal_fields)
+{
+ if (*eq_mod == ctx->equality_mods + ctx->n_equality_mods_alloced)
+ {
+ /*
+ We've filled the entire equality_mods array. Replace it with a bigger
+ one. We do it somewhat inefficiently but it doesn't matter.
+ */
+ /* purecov: begin inspected */
+ Dep_module_expr *new_arr;
+ if (!(new_arr= new Dep_module_expr[ctx->n_equality_mods_alloced *2]))
+ return;
+ ctx->n_equality_mods_alloced *= 2;
+ for (int i= 0; i < *eq_mod - ctx->equality_mods; i++)
+ new_arr[i]= ctx->equality_mods[i];
+
+ ctx->equality_mods= new_arr;
+ *eq_mod= new_arr + (*eq_mod - ctx->equality_mods);
+ /* purecov: end */
+ }
+
+ (*eq_mod)->field= field_val;
+ (*eq_mod)->expr= right;
+ (*eq_mod)->level= and_level;
+ (*eq_mod)->mult_equal_fields= mult_equal_fields;
+ (*eq_mod)++;
+}
+
+
+/*
+ Create a Dep_value_table object for the given table
+
+ SYNOPSIS
+ Dep_analysis_context::create_table_value()
+ table Table to create object for
+
+ DESCRIPTION
+ Create a Dep_value_table object for the given table. Also create
+ Dep_module_key objects for all unique keys in the table.
+
+ RETURN
+ Created table value object
+ NULL if out of memory
+*/
+
+Dep_value_table *Dep_analysis_context::create_table_value(TABLE *table)
+{
+ Dep_value_table *tbl_dep;
+ if (!(tbl_dep= new Dep_value_table(table)))
+ return NULL; /* purecov: inspected */
+
+ Dep_module_key **key_list= &(tbl_dep->keys);
+ /* Add dependencies for unique keys */
+ for (uint i=0; i < table->s->keys; i++)
+ {
+ KEY *key= table->key_info + i;
+ if ((key->flags & (HA_NOSAME | HA_END_SPACE_KEY)) == HA_NOSAME)
+ {
+ Dep_module_key *key_dep;
+ if (!(key_dep= new Dep_module_key(tbl_dep, i, key->key_parts)))
+ return NULL;
+ *key_list= key_dep;
+ key_list= &(key_dep->next_table_key);
+ }
+ }
+ return table_deps[table->tablenr]= tbl_dep;
+}
+
+
+/*
+ Get a Dep_value_field object for the given field, creating it if necessary
+
+ SYNOPSIS
+ Dep_analysis_context::get_field_value()
+ field Field to create object for
+
+ DESCRIPTION
+ Get a Dep_value_field object for the given field. First, we search for it
+ in the list of Dep_value_field objects we have already created. If we don't
+ find it, we create a new Dep_value_field and put it into the list of field
+ objects we have for the table.
+
+ RETURN
+ Created field value object
+ NULL if out of memory
+*/
+
+Dep_value_field *Dep_analysis_context::get_field_value(Field *field)
+{
+ TABLE *table= field->table;
+ Dep_value_table *tbl_dep= table_deps[table->tablenr];
+
+ /* Try finding the field in field list */
+ Dep_value_field **pfield= &(tbl_dep->fields);
+ while (*pfield && (*pfield)->field->field_index < field->field_index)
+ {
+ pfield= &((*pfield)->next_table_field);
+ }
+ if (*pfield && (*pfield)->field->field_index == field->field_index)
+ return *pfield;
+
+ /* Create the field and insert it in the list */
+ Dep_value_field *new_field= new Dep_value_field(tbl_dep, field);
+ new_field->next_table_field= *pfield;
+ *pfield= new_field;
+
+ return new_field;
+}
+
+
+/*
+ Iteration over unbound modules that are our dependencies.
+ for those we have:
+ - dependendencies of our fields
+ - outer join we're in
+*/
+char *Dep_value_table::init_unbound_modules_iter(char *buf)
+{
+ Module_iter *iter= ALIGN_PTR(my_ptrdiff_t(buf), Module_iter);
+ iter->field_dep= fields;
+ if (fields)
+ {
+ fields->init_unbound_modules_iter(iter->buf);
+ fields->make_unbound_modules_iter_skip_keys(iter->buf);
+ }
+ iter->returned_goal= FALSE;
+ return (char*)iter;
+}
+
+
+Dep_module*
+Dep_value_table::get_next_unbound_module(Dep_analysis_context *dac,
+ char *iter)
+{
+ Module_iter *di= (Module_iter*)iter;
+ while (di->field_dep)
+ {
+ Dep_module *res;
+ if ((res= di->field_dep->get_next_unbound_module(dac, di->buf)))
+ return res;
+ if ((di->field_dep= di->field_dep->next_table_field))
+ {
+ char *field_iter= ((Module_iter*)iter)->buf;
+ di->field_dep->init_unbound_modules_iter(field_iter);
+ di->field_dep->make_unbound_modules_iter_skip_keys(field_iter);
+ }
+ }
+
+ if (!di->returned_goal)
+ {
+ di->returned_goal= TRUE;
+ return dac->outer_join_dep;
+ }
+ return NULL;
+}
+
+
+char *Dep_module_expr::init_unbound_values_iter(char *buf)
+{
+ Value_iter *iter= ALIGN_PTR(my_ptrdiff_t(buf), Value_iter);
+ iter->field= field;
+ if (!field)
+ {
+ new (&iter->it) List_iterator<Dep_value_field>(*mult_equal_fields);
+ }
+ return (char*)iter;
+}
+
+
+Dep_value* Dep_module_expr::get_next_unbound_value(Dep_analysis_context *dac,
+ char *buf)
+{
+ Dep_value *res;
+ if (field)
+ {
+ res= ((Value_iter*)buf)->field;
+ ((Value_iter*)buf)->field= NULL;
+ return (!res || res->is_bound())? NULL : res;
+ }
+ else
+ {
+ while ((res= ((Value_iter*)buf)->it++))
+ {
+ if (!res->is_bound())
+ return res;
+ }
+ return NULL;
+ }
+}
+
+
+char *Dep_module_key::init_unbound_values_iter(char *buf)
+{
+ Value_iter *iter= ALIGN_PTR(my_ptrdiff_t(buf), Value_iter);
+ iter->table= table;
+ return (char*)iter;
+}
+
+
+Dep_value* Dep_module_key::get_next_unbound_value(Dep_analysis_context *dac,
+ Dep_module::Iterator iter)
+{
+ Dep_value* res= ((Value_iter*)iter)->table;
+ ((Value_iter*)iter)->table= NULL;
+ return res;
+}
+
+
+Dep_value::Iterator Dep_value_field::init_unbound_modules_iter(char *buf)
+{
+ Module_iter *iter= ALIGN_PTR(my_ptrdiff_t(buf), Module_iter);
+ iter->key_dep= table->keys;
+ iter->equality_no= 0;
+ return (char*)iter;
+}
+
+
+void
+Dep_value_field::make_unbound_modules_iter_skip_keys(Dep_value::Iterator iter)
+{
+ ((Module_iter*)iter)->key_dep= NULL;
+}
+
+
+Dep_module* Dep_value_field::get_next_unbound_module(Dep_analysis_context *dac,
+ Dep_value::Iterator iter)
+{
+ Module_iter *di= (Module_iter*)iter;
+ Dep_module_key *key_dep= di->key_dep;
+
+ /*
+ First, enumerate all unique keys that are
+ - not yet applicable
+ - have this field as a part of them
+ */
+ while (key_dep && (key_dep->is_applicable() ||
+ !field->part_of_key.is_set(key_dep->keyno)))
+ {
+ key_dep= key_dep->next_table_key;
+ }
+
+ if (key_dep)
+ {
+ di->key_dep= key_dep->next_table_key;
+ return key_dep;
+ }
+ else
+ di->key_dep= NULL;
+
+ /*
+ Then walk through [multi]equalities and find those that
+ - depend on this field
+ - and are not bound yet.
+ */
+ uint eq_no= di->equality_no;
+ while (eq_no < dac->n_equality_mods &&
+ (!bitmap_is_set(&dac->expr_deps, bitmap_offset + eq_no) ||
+ dac->equality_mods[eq_no].is_applicable()))
+ {
+ eq_no++;
+ }
+
+ if (eq_no < dac->n_equality_mods)
+ {
+ di->equality_no= eq_no+1;
+ return &dac->equality_mods[eq_no];
+ }
+ return NULL;
+}
+
+
+/*
+ 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<TABLE_LIST> 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);
+}
+
+
+#ifndef DBUG_OFF
+/* purecov: begin inspected */
+void Dep_analysis_context::dbug_print_deps()
+{
+ DBUG_ENTER("dbug_print_deps");
+ DBUG_LOCK_FILE;
+
+ fprintf(DBUG_FILE,"deps {\n");
+
+ /* Start with printing equalities */
+ for (Dep_module_expr *eq_mod= equality_mods;
+ eq_mod != equality_mods + n_equality_mods; eq_mod++)
+ {
+ char buf[128];
+ String str(buf, sizeof(buf), &my_charset_bin);
+ str.length(0);
+ eq_mod->expr->print(&str, QT_ORDINARY);
+ if (eq_mod->field)
+ {
+ fprintf(DBUG_FILE, " equality%d: %s -> %s.%s\n",
+ eq_mod - equality_mods,
+ str.c_ptr(),
+ eq_mod->field->table->table->alias,
+ eq_mod->field->field->field_name);
+ }
+ else
+ {
+ fprintf(DBUG_FILE, " equality%d: multi-equality",
+ eq_mod - equality_mods);
+ }
+ }
+ fprintf(DBUG_FILE,"\n");
+
+ /* Then tables and their fields */
+ for (uint i=0; i < MAX_TABLES; i++)
+ {
+ Dep_value_table *table_dep;
+ if ((table_dep= table_deps[i]))
+ {
+ /* Print table */
+ fprintf(DBUG_FILE, " table %s\n", table_dep->table->alias);
+ /* Print fields */
+ for (Dep_value_field *field_dep= table_dep->fields; field_dep;
+ field_dep= field_dep->next_table_field)
+ {
+ fprintf(DBUG_FILE, " field %s.%s ->", table_dep->table->alias,
+ field_dep->field->field_name);
+ uint ofs= field_dep->bitmap_offset;
+ for (uint bit= ofs; bit < ofs + n_equality_mods; bit++)
+ {
+ if (bitmap_is_set(&expr_deps, bit))
+ fprintf(DBUG_FILE, " equality%d ", bit - ofs);
+ }
+ fprintf(DBUG_FILE, "\n");
+ }
+ }
+ }
+ fprintf(DBUG_FILE,"\n}\n");
+ DBUG_UNLOCK_FILE;
+ DBUG_VOID_RETURN;
+}
+/* purecov: end */
+
+#endif
+/**
+ @} (end of group Table_Elimination)
+*/
+
=== modified file 'sql/sql_bitmap.h'
--- sql/sql_bitmap.h 2008-01-29 11:14:34 +0000
+++ sql/sql_bitmap.h 2009-08-12 22:34:21 +0000
@@ -93,6 +93,34 @@
}
};
+/* An iterator to quickly walk over bits in unlonglong bitmap. */
+class Table_map_iterator
+{
+ ulonglong bmp;
+ uint no;
+public:
+ Table_map_iterator(ulonglong t) : bmp(t), no(0) {}
+ int next_bit()
+ {
+ static const char last_bit[16]= {32, 0, 1, 0,
+ 2, 0, 1, 0,
+ 3, 0, 1, 0,
+ 2, 0, 1, 0};
+ uint bit;
+ while ((bit= last_bit[bmp & 0xF]) == 32)
+ {
+ no += 4;
+ bmp= bmp >> 4;
+ if (!bmp)
+ return BITMAP_END;
+ }
+ bmp &= ~(1LL << bit);
+ return no + bit;
+ }
+ int operator++(int) { return next_bit(); }
+ enum { BITMAP_END= 64 };
+};
+
template <> class Bitmap<64>
{
ulonglong map;
@@ -136,5 +164,10 @@
my_bool operator==(const Bitmap<64>& map2) const { return map == map2.map; }
char *print(char *buf) const { longlong2str(map,buf,16); return buf; }
ulonglong to_ulonglong() const { return map; }
+ class Iterator : public Table_map_iterator
+ {
+ public:
+ Iterator(Bitmap<64> &bmp) : Table_map_iterator(bmp.map) {}
+ };
};
=== modified file 'sql/sql_lex.cc'
--- sql/sql_lex.cc 2009-04-25 10:05:32 +0000
+++ sql/sql_lex.cc 2009-07-08 17:10:38 +0000
@@ -1778,8 +1778,9 @@
'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)
{
+ SELECT_LEX *next_to_last;
/*
Mark all selects from resolved to 1 before select where was
found table as depended (of select where was found table)
@@ -1787,6 +1788,7 @@
for (SELECT_LEX *s= this;
s && s != last;
s= s->outer_select())
+ {
if (!(s->uncacheable & UNCACHEABLE_DEPENDENT))
{
// Select is dependent of outer select
@@ -1802,8 +1804,12 @@
sl->uncacheable|= UNCACHEABLE_UNITED;
}
}
+ next_to_last= s;
+ }
is_correlated= TRUE;
this->master_unit()->item->is_correlated= TRUE;
+ if (dependency)
+ next_to_last->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'
--- sql/sql_lex.h 2009-03-17 20:29:24 +0000
+++ sql/sql_lex.h 2009-06-22 11:46:31 +0000
@@ -743,7 +743,7 @@
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_list.h'
--- sql/sql_list.h 2009-05-06 12:03:24 +0000
+++ sql/sql_list.h 2009-08-31 20:02:09 +0000
@@ -443,6 +443,43 @@
/*
+ Exchange sort algorithm for List<T>.
+*/
+template <class T>
+inline void exchange_sort(List<T> *list_to_sort,
+ int (*sort_func)(T *a, T *b, void *arg), void *arg)
+{
+ bool swap;
+ List_iterator<T> it(*list_to_sort);
+ do
+ {
+ T *item1= it++;
+ T **ref1= it.ref();
+ T *item2;
+
+ swap= FALSE;
+ while ((item2= it++))
+ {
+ T **ref2= it.ref();
+ if (sort_func(item1, item2, arg) < 0)
+ {
+ T *item= *ref1;
+ *ref1= *ref2;
+ *ref2= item;
+ swap= TRUE;
+ }
+ else
+ {
+ item1= item2;
+ ref1= ref2;
+ }
+ }
+ it.rewind();
+ } while (swap);
+}
+
+
+/*
A simple intrusive list which automaticly removes element from list
on delete (for THD element)
*/
=== modified file 'sql/sql_select.cc'
--- sql/sql_select.cc 2009-06-29 21:03:30 +0000
+++ sql/sql_select.cc 2009-08-31 20:02:09 +0000
@@ -60,7 +60,6 @@
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);
@@ -115,7 +114,7 @@
COND *conds, bool top);
static bool check_interleaving_with_nj(JOIN_TAB *next);
static void restore_prev_nj_state(JOIN_TAB *last);
-static void reset_nj_counters(List<TABLE_LIST> *join_list);
+static uint reset_nj_counters(JOIN *join, List<TABLE_LIST> *join_list);
static uint build_bitmap_for_nested_joins(List<TABLE_LIST> *join_list,
uint first_unused);
@@ -1012,7 +1011,7 @@
DBUG_RETURN(1);
}
- reset_nj_counters(join_list);
+ reset_nj_counters(this, join_list);
make_outerjoin_info(this);
/*
@@ -2381,6 +2380,13 @@
}
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");
@@ -2646,24 +2652,31 @@
~outer_join, join->select_lex, &sargables))
goto error;
+ 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) */
- join->const_table_map= 0;
-
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 +2701,8 @@
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
@@ -2965,14 +2979,45 @@
This is called for OR between different levels.
- 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:.
+ 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=expr1 OR t.keycol=expr2 -> (since expr1 and expr2 are different
+ we can't produce a single equality,
+ so produce nothing)
+
+ t.keycol=expr1 OR t.keycol=expr1 -> t.keycol=expr1
+
+ t.keycol=expr1 OR t.keycol IS NULL -> t.keycol=expr1, and also set
+ KEY_OPTIMIZE_REF_OR_NULL flag
+
+ The last one is for ref_or_null access. We have handling for this special
+ because it's needed for evaluating IN subqueries that are internally
+ transformed into
@code
- SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL
+ EXISTS(SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL)
@endcode
+ See add_key_fields() for discussion of what is and_level.
+
KEY_FIELD::null_rejecting is processed as follows: @n
result has null_rejecting=true if it is set for both ORed references.
for example:
@@ -3312,6 +3357,26 @@
}
}
+
+/*
+ In this and other functions, and_level is a number that is ever-growing
+ and is different for the contents of every AND or OR clause. For example,
+ when processing clause
+
+ (a AND b AND c) OR (x AND y)
+
+ we'll have
+ * KEY_FIELD elements for (a AND b AND c) are assigned and_level=1
+ * KEY_FIELD elements for (x AND y) are assigned and_level=2
+ * OR operation is performed, and whatever elements are left after it are
+ assigned and_level=3.
+
+ The primary reason for having and_level attribute is the OR operation which
+ uses and_level to mark KEY_FIELDs that should get into the result of the OR
+ operation
+
+*/
+
static void
add_key_fields(JOIN *join, KEY_FIELD **key_fields, uint *and_level,
COND *cond, table_map usable_tables,
@@ -3990,8 +4055,7 @@
/** 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;
@@ -4592,7 +4656,7 @@
DBUG_ENTER("choose_plan");
join->cur_embedding_map= 0;
- reset_nj_counters(join->join_list);
+ reset_nj_counters(join, join->join_list);
/*
if (SELECT_STRAIGHT_JOIN option is set)
reorder tables so dependent tables come after tables they depend
@@ -5757,6 +5821,7 @@
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 +6086,7 @@
}
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 +8640,8 @@
conds= simplify_joins(join, &nested_join->join_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 +8800,7 @@
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,
@@ -8755,21 +8822,26 @@
tables which will be ignored.
*/
-static void reset_nj_counters(List<TABLE_LIST> *join_list)
+static uint reset_nj_counters(JOIN *join, List<TABLE_LIST> *join_list)
{
List_iterator<TABLE_LIST> li(*join_list);
TABLE_LIST *table;
DBUG_ENTER("reset_nj_counters");
+ uint n=0;
while ((table= li++))
{
NESTED_JOIN *nested_join;
if ((nested_join= table->nested_join))
{
nested_join->counter= 0;
- reset_nj_counters(&nested_join->join_list);
+ //nested_join->n_tables= my_count_bits(nested_join->used_tables &
+ // ~join->eliminated_tables);
+ nested_join->n_tables= reset_nj_counters(join, &nested_join->join_list);
}
+ if (table->table && (table->table->map & ~join->eliminated_tables))
+ n++;
}
- DBUG_VOID_RETURN;
+ DBUG_RETURN(n);
}
@@ -8894,7 +8966,7 @@
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;
@@ -8928,7 +9000,7 @@
{
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
@@ -16238,6 +16310,14 @@
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)
@@ -16560,8 +16640,11 @@
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;
}
@@ -16602,7 +16685,6 @@
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
{
@@ -16635,6 +16717,7 @@
*/
static void print_join(THD *thd,
+ table_map eliminated_tables,
String *str,
List<TABLE_LIST> *tables,
enum_query_type query_type)
@@ -16650,12 +16733,33 @@
*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 */
@@ -16665,7 +16769,7 @@
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("));
@@ -16719,12 +16823,13 @@
@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
@@ -16866,7 +16971,7 @@
{
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'
--- sql/sql_select.h 2009-04-25 10:05:32 +0000
+++ sql/sql_select.h 2009-08-12 23:43:02 +0000
@@ -285,7 +285,15 @@
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 +433,7 @@
table= 0;
tables= 0;
const_tables= 0;
+ eliminated_tables= 0;
join_list= 0;
sort_and_group= 0;
first_record= 0;
@@ -530,6 +539,10 @@
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 +743,12 @@
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'
--- sql/table.h 2009-02-19 09:01:25 +0000
+++ sql/table.h 2009-06-30 13:11:00 +0000
@@ -1366,7 +1366,8 @@
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 @@
typedef struct st_nested_join
{
List<TABLE_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 @@
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;
