June 2009 - developers - lists.mariadb.org

[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (monty:2710)
by Michael Widenius 05 Jun '09

05 Jun '09

#At lp:maria based on revid:monty@askmonty.org-20090605153614-xy15fk9dhi5uvk3t 2710 Michael Widenius 2009-06-05 Fixed valgrind warnings on 64 bit x86 SuSE 11.1 modified: mysql-test/valgrind.supp === modified file 'mysql-test/valgrind.supp' --- a/mysql-test/valgrind.supp 2009-06-05 15:35:22 +0000 +++ b/mysql-test/valgrind.supp 2009-06-05 20:46:23 +0000 @@ -422,12 +422,25 @@ obj:/lib*/ld-*.so obj:/lib*/ld-*.so obj:/lib*/libdl-*.so - fun:_dl_close + fun:dlclose fun:_ZL15free_plugin_memP12st_plugin_dl fun:_ZL13plugin_dl_delPK19st_mysql_lex_string } { + dlclose memory loss from plugin variant 5 + Memcheck:Leak + fun:malloc + obj:/lib*/ld-*.so + obj:/lib*/ld-*.so + obj:/lib*/ld-*.so + obj:/lib*/ld-*.so + obj:/lib*/libdl-*.so + fun:dlclose + fun:_ZL15free_plugin_memP12st_plugin_dl +} + +{ dlopen / ptread_cancel_init memory loss on Suse Linux 10.3 32/64 bit ver 1 Memcheck:Leak fun:*alloc

1 0

[Maria-developers] [Branch ~maria-captains/maria/5.1] Rev 2709: Add include files required for --staging-run
by noreply＠launchpad.net 05 Jun '09

05 Jun '09

------------------------------------------------------------ revno: 2709 committer: Michael Widenius <monty(a)askmonty.org> branch nick: mysql-maria timestamp: Fri 2009-06-05 18:36:14 +0300 message: Add include files required for --staging-run added: mysql-test/include/not_staging.inc mysql-test/r/not_staging.require === added file 'mysql-test/include/not_staging.inc' --- mysql-test/include/not_staging.inc 1970-01-01 00:00:00 +0000 +++ mysql-test/include/not_staging.inc 2009-06-05 15:36:14 +0000 @@ -0,0 +1,4 @@ +--require r/not_staging.require +disable_query_log; +eval select $STAGING_RUN as using_staging_run; +enable_query_log; === added file 'mysql-test/r/not_staging.require' --- mysql-test/r/not_staging.require 1970-01-01 00:00:00 +0000 +++ mysql-test/r/not_staging.require 2009-06-05 15:36:14 +0000 @@ -0,0 +1,2 @@ +using_staging_run +0 -- 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.

1 0

[Maria-developers] [Branch ~maria-captains/maria/5.1] Rev 2708: Added option --staging-run to mysql-test-run to mark slow, not important tests, to not be run in ...
by noreply＠launchpad.net 05 Jun '09

05 Jun '09

------------------------------------------------------------ revno: 2708 committer: Michael Widenius <monty(a)askmonty.org> branch nick: mysql-maria timestamp: Fri 2009-06-05 18:35:22 +0300 message: Added option --staging-run to mysql-test-run to mark slow, not important tests, to not be run in staging trees Use MY_MUTEX_INIT_FAST for pool mutex modified: mysql-test/mysql-test-run.pl mysql-test/suite/federated/federated_server.test mysql-test/suite/maria/t/maria-preload.test mysql-test/suite/rpl/t/rpl_optimize.test mysql-test/suite/rpl/t/rpl_relayrotate.test mysql-test/suite/rpl/t/rpl_row_001.test mysql-test/suite/rpl/t/rpl_row_mysqlbinlog.test mysql-test/suite/rpl/t/rpl_row_sp003.test mysql-test/suite/rpl/t/rpl_start_stop_slave.test mysql-test/t/compress.test mysql-test/t/count_distinct3.test mysql-test/t/index_merge_innodb.test mysql-test/t/information_schema_all_engines.test mysql-test/t/innodb_mysql.test mysql-test/t/pool_of_threads.test mysql-test/t/preload.test mysql-test/t/ssl.test mysql-test/t/ssl_compress.test mysql-test/valgrind.supp sql/scheduler.cc === modified file 'mysql-test/mysql-test-run.pl' --- mysql-test/mysql-test-run.pl 2009-05-12 06:44:01 +0000 +++ mysql-test/mysql-test-run.pl 2009-06-05 15:35:22 +0000 @@ -140,6 +140,7 @@ our $exe_libtool; our $opt_big_test= 0; +our $opt_staging_run= 0; our @opt_combinations; @@ -844,6 +845,7 @@ 'skip-combinations' => \&collect_option, 'experimental=s' => \$opt_experimental, 'skip-im' => \&ignore_option, + 'staging-run' => \$opt_staging_run, # Specify ports 'build-thread|mtr-build-thread=i' => \$opt_build_thread, @@ -1252,12 +1254,13 @@ } # -------------------------------------------------------------------------- - # Big test flags + # Big test and staging_run flags # -------------------------------------------------------------------------- if ( $opt_big_test ) { $ENV{'BIG_TEST'}= 1; } + $ENV{'STAGING_RUN'}= $opt_staging_run; # -------------------------------------------------------------------------- # Gcov flag @@ -5234,7 +5237,7 @@ skip-ssl Dont start server with support for ssl connections vs-config Visual Studio configuration used to create executables (default: MTR_VS_CONFIG environment variable) - + parallel=# How many parallell test should be run config|defaults-file=<config template> Use fixed config template for all tests defaults_extra_file=<config template> Extra config template to add to @@ -5276,6 +5279,8 @@ The default is: "$DEFAULT_SUITES" skip-rpl Skip the replication test cases. big-test Also run tests marked as "big" + staging-run Run a limited number of tests (no slow tests). Used + for running staging trees with valgrind. Options that specify ports === modified file 'mysql-test/suite/federated/federated_server.test' --- mysql-test/suite/federated/federated_server.test 2009-01-22 13:07:58 +0000 +++ mysql-test/suite/federated/federated_server.test 2009-06-05 15:35:22 +0000 @@ -1,5 +1,8 @@ # WL #3031 This test tests the new servers table as well as # if federated can utilise the servers table + +# Slow test, don't run during staging part +-- source include/not_staging.inc -- source federated.inc connection slave; === modified file 'mysql-test/suite/maria/t/maria-preload.test' --- mysql-test/suite/maria/t/maria-preload.test 2008-10-01 12:13:39 +0000 +++ mysql-test/suite/maria/t/maria-preload.test 2009-06-05 15:35:22 +0000 @@ -2,6 +2,8 @@ # Testing of PRELOAD # +# Slow test, don't run during staging part +-- source include/not_staging.inc -- source include/have_maria.inc --disable_warnings === modified file 'mysql-test/suite/rpl/t/rpl_optimize.test' --- mysql-test/suite/rpl/t/rpl_optimize.test 2008-03-25 13:28:12 +0000 +++ mysql-test/suite/rpl/t/rpl_optimize.test 2009-06-05 15:35:22 +0000 @@ -11,6 +11,8 @@ # Skipping this test if default engine = ndb ##################################### -- source include/not_ndb_default.inc +# Slow test, don't run during staging part +-- source include/not_staging.inc -- source include/master-slave.inc create table t1 (a int not null auto_increment primary key, b int, key(b)); === modified file 'mysql-test/suite/rpl/t/rpl_relayrotate.test' --- mysql-test/suite/rpl/t/rpl_relayrotate.test 2007-06-27 12:29:10 +0000 +++ mysql-test/suite/rpl/t/rpl_relayrotate.test 2009-06-05 15:35:22 +0000 @@ -6,6 +6,9 @@ ####################################################### -- source include/not_ndb_default.inc -- source include/have_innodb.inc +# Slow test, don't run during staging part +-- source include/not_staging.inc -- source include/master-slave.inc + let $engine_type=innodb; -- source extra/rpl_tests/rpl_relayrotate.test === modified file 'mysql-test/suite/rpl/t/rpl_row_001.test' --- mysql-test/suite/rpl/t/rpl_row_001.test 2007-06-27 12:29:10 +0000 +++ mysql-test/suite/rpl/t/rpl_row_001.test 2009-06-05 15:35:22 +0000 @@ -4,6 +4,9 @@ ######################################################## -- source include/not_ndb_default.inc -- source include/have_binlog_format_row.inc +# Slow test, don't run during staging part +-- source include/not_staging.inc -- source include/master-slave.inc + let $engine_type=MYISAM; -- source extra/rpl_tests/rpl_row_001.test === modified file 'mysql-test/suite/rpl/t/rpl_row_mysqlbinlog.test' --- mysql-test/suite/rpl/t/rpl_row_mysqlbinlog.test 2008-04-03 19:40:10 +0000 +++ mysql-test/suite/rpl/t/rpl_row_mysqlbinlog.test 2009-06-05 15:35:22 +0000 @@ -12,6 +12,8 @@ -- source include/master-slave.inc # This test requires the cp932 charset compiled in -- source include/have_cp932.inc +# Slow test, don't run during staging part +-- source include/not_staging.inc # Setup Section # we need this for getting fixed timestamps inside of this test === modified file 'mysql-test/suite/rpl/t/rpl_row_sp003.test' --- mysql-test/suite/rpl/t/rpl_row_sp003.test 2007-06-27 12:29:10 +0000 +++ mysql-test/suite/rpl/t/rpl_row_sp003.test 2009-06-05 15:35:22 +0000 @@ -8,6 +8,9 @@ -- source include/not_ndb_default.inc -- source include/have_innodb.inc -- source include/have_binlog_format_row.inc +# Slow test, don't run during staging part +-- source include/not_staging.inc -- source include/master-slave.inc + let $engine_type=INNODB; -- source extra/rpl_tests/rpl_row_sp003.test === modified file 'mysql-test/suite/rpl/t/rpl_start_stop_slave.test' --- mysql-test/suite/rpl/t/rpl_start_stop_slave.test 2008-12-12 11:25:36 +0000 +++ mysql-test/suite/rpl/t/rpl_start_stop_slave.test 2009-06-05 15:35:22 +0000 @@ -1,3 +1,5 @@ +# Slow test, don't run during staging part +-- source include/not_staging.inc source include/master-slave.inc; # === modified file 'mysql-test/t/compress.test' --- mysql-test/t/compress.test 2009-02-09 21:00:15 +0000 +++ mysql-test/t/compress.test 2009-06-05 15:35:22 +0000 @@ -3,8 +3,9 @@ # Can't test with embedded server -- source include/not_embedded.inc - -- source include/have_compress.inc +# Slow test, don't run during staging part +-- source include/not_staging.inc # Save the initial number of concurrent sessions --source include/count_sessions.inc === modified file 'mysql-test/t/count_distinct3.test' --- mysql-test/t/count_distinct3.test 2006-10-03 07:03:35 +0000 +++ mysql-test/t/count_distinct3.test 2009-06-05 15:35:22 +0000 @@ -3,6 +3,8 @@ # mysql-4.1 # +# Slow test +-- source include/big_test.inc --disable_warnings DROP TABLE IF EXISTS t1, t2; --enable_warnings === modified file 'mysql-test/t/index_merge_innodb.test' --- mysql-test/t/index_merge_innodb.test 2006-09-18 14:55:56 +0000 +++ mysql-test/t/index_merge_innodb.test 2009-06-05 15:35:22 +0000 @@ -10,7 +10,10 @@ # include/index_merge*.inc files # +# Slow test, don't run during staging part +--source include/not_staging.inc --source include/have_innodb.inc + let $engine_type= InnoDB; # InnoDB does not support Merge tables (affects include/index_merge1.inc) let $merge_table_support= 0; === modified file 'mysql-test/t/information_schema_all_engines.test' --- mysql-test/t/information_schema_all_engines.test 2009-04-08 16:55:26 +0000 +++ mysql-test/t/information_schema_all_engines.test 2009-06-05 15:35:22 +0000 @@ -4,6 +4,7 @@ --source include/not_embedded.inc --source include/have_pbxt.inc +-- source include/not_staging.inc use INFORMATION_SCHEMA; --replace_result Tables_in_INFORMATION_SCHEMA Tables_in_information_schema === modified file 'mysql-test/t/innodb_mysql.test' --- mysql-test/t/innodb_mysql.test 2009-02-20 09:50:50 +0000 +++ mysql-test/t/innodb_mysql.test 2009-06-05 15:35:22 +0000 @@ -5,6 +5,8 @@ # main testing code t/innodb_mysql.test -> include/mix1.inc # +# Slow test, don't run during staging part +-- source include/not_staging.inc -- source include/have_innodb.inc let $engine_type= InnoDB; let $other_engine_type= MEMORY; === modified file 'mysql-test/t/pool_of_threads.test' --- mysql-test/t/pool_of_threads.test 2009-03-18 15:46:32 +0000 +++ mysql-test/t/pool_of_threads.test 2009-06-05 15:35:22 +0000 @@ -2,7 +2,8 @@ # and run a number of tests -- source include/have_pool_of_threads.inc - +# Slow test, don't run during staging part +-- source include/not_staging.inc -- source include/common-tests.inc === modified file 'mysql-test/t/preload.test' --- mysql-test/t/preload.test 2005-07-28 00:22:47 +0000 +++ mysql-test/t/preload.test 2009-06-05 15:35:22 +0000 @@ -2,6 +2,9 @@ # Testing of PRELOAD # +# Slow test, don't run during staging part +-- source include/not_staging.inc + --disable_warnings drop table if exists t1, t2; --enable_warnings === modified file 'mysql-test/t/ssl.test' --- mysql-test/t/ssl.test 2009-03-03 20:34:18 +0000 +++ mysql-test/t/ssl.test 2009-06-05 15:35:22 +0000 @@ -2,6 +2,8 @@ # and run a number of tests -- source include/have_ssl.inc +# Slow test, don't run during staging part +-- source include/not_staging.inc # Save the initial number of concurrent sessions --source include/count_sessions.inc === modified file 'mysql-test/t/ssl_compress.test' --- mysql-test/t/ssl_compress.test 2009-03-03 20:34:18 +0000 +++ mysql-test/t/ssl_compress.test 2009-06-05 15:35:22 +0000 @@ -3,6 +3,7 @@ -- source include/have_ssl.inc -- source include/have_compress.inc +-- source include/not_staging.inc # Save the initial number of concurrent sessions --source include/count_sessions.inc === modified file 'mysql-test/valgrind.supp' --- mysql-test/valgrind.supp 2009-05-22 12:38:50 +0000 +++ mysql-test/valgrind.supp 2009-06-05 15:35:22 +0000 @@ -415,10 +415,40 @@ } { - dlopen / ptread_cancel_init memory loss on Suse Linux 10.3 32/64 bit - Memcheck:Leak - fun:*alloc - obj:/lib*/ld-*.so + dlclose memory loss from plugin variant 4 + Memcheck:Leak + fun:malloc + obj:/lib*/ld-*.so + obj:/lib*/ld-*.so + obj:/lib*/ld-*.so + obj:/lib*/libdl-*.so + fun:_dl_close + fun:_ZL15free_plugin_memP12st_plugin_dl + fun:_ZL13plugin_dl_delPK19st_mysql_lex_string +} + +{ + dlopen / ptread_cancel_init memory loss on Suse Linux 10.3 32/64 bit ver 1 + Memcheck:Leak + fun:*alloc + obj:/lib*/ld-*.so + obj:/lib*/ld-*.so + obj:/lib*/ld-*.so + obj:/lib*/ld-*.so + obj:/lib*/ld-*.so + obj:/lib*/ld-*.so + obj:/lib*/libc-*.so + obj:/lib*/ld-*.so + obj:/lib*/libc-*.so + fun:__libc_dlopen_mode + fun:pthread_cancel_init + fun:_Unwind_ForcedUnwind +} + +{ + dlopen / ptread_cancel_init memory loss on Suse Linux 10.3 32/64 bit ver 2 + Memcheck:Leak + fun:*alloc obj:/lib*/ld-*.so obj:/lib*/ld-*.so obj:/lib*/ld-*.so === modified file 'sql/scheduler.cc' --- sql/scheduler.cc 2009-03-12 22:27:35 +0000 +++ sql/scheduler.cc 2009-06-05 15:35:22 +0000 @@ -282,8 +282,8 @@ killed_threads= 0; kill_pool_threads= FALSE; - pthread_mutex_init(&LOCK_event_loop, NULL); - pthread_mutex_init(&LOCK_thd_add, NULL); + pthread_mutex_init(&LOCK_event_loop, MY_MUTEX_INIT_FAST); + pthread_mutex_init(&LOCK_thd_add, MY_MUTEX_INIT_FAST); /* set up sockets used to add new thds to the event pool */ if (init_socketpair(thd_add_pair)) -- 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.

1 0

[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (monty:2709)
by Michael Widenius 05 Jun '09

05 Jun '09

#At lp:maria based on revid:monty@askmonty.org-20090605153522-bk425no0j88goc9n 2709 Michael Widenius 2009-06-05 Add include files required for --staging-run added: mysql-test/include/not_staging.inc mysql-test/r/not_staging.require === added file 'mysql-test/include/not_staging.inc' --- a/mysql-test/include/not_staging.inc 1970-01-01 00:00:00 +0000 +++ b/mysql-test/include/not_staging.inc 2009-06-05 15:36:14 +0000 @@ -0,0 +1,4 @@ +--require r/not_staging.require +disable_query_log; +eval select $STAGING_RUN as using_staging_run; +enable_query_log; === added file 'mysql-test/r/not_staging.require' --- a/mysql-test/r/not_staging.require 1970-01-01 00:00:00 +0000 +++ b/mysql-test/r/not_staging.require 2009-06-05 15:36:14 +0000 @@ -0,0 +1,2 @@ +using_staging_run +0

1 0

[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (monty:2708)
by Michael Widenius 05 Jun '09

05 Jun '09

#At lp:maria based on revid:knielsen@knielsen-hq.org-20090602110359-n4q9gof38buucrny 2708 Michael Widenius 2009-06-05 Added option --staging-run to mysql-test-run to mark slow, not important tests, to not be run in staging trees Use MY_MUTEX_INIT_FAST for pool mutex modified: mysql-test/mysql-test-run.pl mysql-test/suite/federated/federated_server.test mysql-test/suite/maria/t/maria-preload.test mysql-test/suite/rpl/t/rpl_optimize.test mysql-test/suite/rpl/t/rpl_relayrotate.test mysql-test/suite/rpl/t/rpl_row_001.test mysql-test/suite/rpl/t/rpl_row_mysqlbinlog.test mysql-test/suite/rpl/t/rpl_row_sp003.test mysql-test/suite/rpl/t/rpl_start_stop_slave.test mysql-test/t/compress.test mysql-test/t/count_distinct3.test mysql-test/t/index_merge_innodb.test mysql-test/t/information_schema_all_engines.test mysql-test/t/innodb_mysql.test mysql-test/t/pool_of_threads.test mysql-test/t/preload.test mysql-test/t/ssl.test mysql-test/t/ssl_compress.test mysql-test/valgrind.supp sql/scheduler.cc per-file messages: mysql-test/mysql-test-run.pl Added option --staging-run Added information about --parallell=# to help message mysql-test/suite/federated/federated_server.test Slow test, don't run with --staging-run mysql-test/suite/maria/t/maria-preload.test Slow test, don't run with --staging-run mysql-test/suite/rpl/t/rpl_optimize.test Slow test, don't run with --staging-run mysql-test/suite/rpl/t/rpl_relayrotate.test Slow test, don't run with --staging-run mysql-test/suite/rpl/t/rpl_row_001.test Slow test, don't run with --staging-run mysql-test/suite/rpl/t/rpl_row_mysqlbinlog.test Slow test, don't run with --staging-run mysql-test/suite/rpl/t/rpl_row_sp003.test Slow test, don't run with --staging-run mysql-test/suite/rpl/t/rpl_start_stop_slave.test Slow test, don't run with --staging-run mysql-test/t/compress.test Slow test, don't run with --staging-run mysql-test/t/count_distinct3.test Slow test, don't run with --staging-run mysql-test/t/index_merge_innodb.test Slow test, don't run with --staging-run mysql-test/t/information_schema_all_engines.test Slow test, don't run with --staging-run mysql-test/t/innodb_mysql.test Slow test, don't run with --staging-run mysql-test/t/pool_of_threads.test Slow test, don't run with --staging-run mysql-test/t/preload.test Slow test, don't run with --staging-run mysql-test/t/ssl.test Slow test, don't run with --staging-run mysql-test/t/ssl_compress.test Slow test, don't run with --staging-run mysql-test/valgrind.supp Suppress warnings from SuSE 11.1 on x86 sql/scheduler.cc Use MY_MUTEX_INIT_FAST for pool mutex === modified file 'mysql-test/mysql-test-run.pl' --- a/mysql-test/mysql-test-run.pl 2009-05-12 06:44:01 +0000 +++ b/mysql-test/mysql-test-run.pl 2009-06-05 15:35:22 +0000 @@ -140,6 +140,7 @@ our $exe_mysqltest; our $exe_libtool; our $opt_big_test= 0; +our $opt_staging_run= 0; our @opt_combinations; @@ -844,6 +845,7 @@ sub command_line_setup { 'skip-combinations' => \&collect_option, 'experimental=s' => \$opt_experimental, 'skip-im' => \&ignore_option, + 'staging-run' => \$opt_staging_run, # Specify ports 'build-thread|mtr-build-thread=i' => \$opt_build_thread, @@ -1252,12 +1254,13 @@ sub command_line_setup { } # -------------------------------------------------------------------------- - # Big test flags + # Big test and staging_run flags # -------------------------------------------------------------------------- if ( $opt_big_test ) { $ENV{'BIG_TEST'}= 1; } + $ENV{'STAGING_RUN'}= $opt_staging_run; # -------------------------------------------------------------------------- # Gcov flag @@ -5234,7 +5237,7 @@ Options to control what engine/variation skip-ssl Dont start server with support for ssl connections vs-config Visual Studio configuration used to create executables (default: MTR_VS_CONFIG environment variable) - + parallel=# How many parallell test should be run config|defaults-file=<config template> Use fixed config template for all tests defaults_extra_file=<config template> Extra config template to add to @@ -5276,6 +5279,8 @@ Options to control what test suites or c The default is: "$DEFAULT_SUITES" skip-rpl Skip the replication test cases. big-test Also run tests marked as "big" + staging-run Run a limited number of tests (no slow tests). Used + for running staging trees with valgrind. Options that specify ports === modified file 'mysql-test/suite/federated/federated_server.test' --- a/mysql-test/suite/federated/federated_server.test 2009-01-22 13:07:58 +0000 +++ b/mysql-test/suite/federated/federated_server.test 2009-06-05 15:35:22 +0000 @@ -1,5 +1,8 @@ # WL #3031 This test tests the new servers table as well as # if federated can utilise the servers table + +# Slow test, don't run during staging part +-- source include/not_staging.inc -- source federated.inc connection slave; === modified file 'mysql-test/suite/maria/t/maria-preload.test' --- a/mysql-test/suite/maria/t/maria-preload.test 2008-10-01 12:13:39 +0000 +++ b/mysql-test/suite/maria/t/maria-preload.test 2009-06-05 15:35:22 +0000 @@ -2,6 +2,8 @@ # Testing of PRELOAD # +# Slow test, don't run during staging part +-- source include/not_staging.inc -- source include/have_maria.inc --disable_warnings === modified file 'mysql-test/suite/rpl/t/rpl_optimize.test' --- a/mysql-test/suite/rpl/t/rpl_optimize.test 2008-03-25 13:28:12 +0000 +++ b/mysql-test/suite/rpl/t/rpl_optimize.test 2009-06-05 15:35:22 +0000 @@ -11,6 +11,8 @@ # Skipping this test if default engine = ndb ##################################### -- source include/not_ndb_default.inc +# Slow test, don't run during staging part +-- source include/not_staging.inc -- source include/master-slave.inc create table t1 (a int not null auto_increment primary key, b int, key(b)); === modified file 'mysql-test/suite/rpl/t/rpl_relayrotate.test' --- a/mysql-test/suite/rpl/t/rpl_relayrotate.test 2007-06-27 12:29:10 +0000 +++ b/mysql-test/suite/rpl/t/rpl_relayrotate.test 2009-06-05 15:35:22 +0000 @@ -6,6 +6,9 @@ ####################################################### -- source include/not_ndb_default.inc -- source include/have_innodb.inc +# Slow test, don't run during staging part +-- source include/not_staging.inc -- source include/master-slave.inc + let $engine_type=innodb; -- source extra/rpl_tests/rpl_relayrotate.test === modified file 'mysql-test/suite/rpl/t/rpl_row_001.test' --- a/mysql-test/suite/rpl/t/rpl_row_001.test 2007-06-27 12:29:10 +0000 +++ b/mysql-test/suite/rpl/t/rpl_row_001.test 2009-06-05 15:35:22 +0000 @@ -4,6 +4,9 @@ ######################################################## -- source include/not_ndb_default.inc -- source include/have_binlog_format_row.inc +# Slow test, don't run during staging part +-- source include/not_staging.inc -- source include/master-slave.inc + let $engine_type=MYISAM; -- source extra/rpl_tests/rpl_row_001.test === modified file 'mysql-test/suite/rpl/t/rpl_row_mysqlbinlog.test' --- a/mysql-test/suite/rpl/t/rpl_row_mysqlbinlog.test 2008-04-03 19:40:10 +0000 +++ b/mysql-test/suite/rpl/t/rpl_row_mysqlbinlog.test 2009-06-05 15:35:22 +0000 @@ -12,6 +12,8 @@ -- source include/master-slave.inc # This test requires the cp932 charset compiled in -- source include/have_cp932.inc +# Slow test, don't run during staging part +-- source include/not_staging.inc # Setup Section # we need this for getting fixed timestamps inside of this test === modified file 'mysql-test/suite/rpl/t/rpl_row_sp003.test' --- a/mysql-test/suite/rpl/t/rpl_row_sp003.test 2007-06-27 12:29:10 +0000 +++ b/mysql-test/suite/rpl/t/rpl_row_sp003.test 2009-06-05 15:35:22 +0000 @@ -8,6 +8,9 @@ -- source include/not_ndb_default.inc -- source include/have_innodb.inc -- source include/have_binlog_format_row.inc +# Slow test, don't run during staging part +-- source include/not_staging.inc -- source include/master-slave.inc + let $engine_type=INNODB; -- source extra/rpl_tests/rpl_row_sp003.test === modified file 'mysql-test/suite/rpl/t/rpl_start_stop_slave.test' --- a/mysql-test/suite/rpl/t/rpl_start_stop_slave.test 2008-12-12 11:25:36 +0000 +++ b/mysql-test/suite/rpl/t/rpl_start_stop_slave.test 2009-06-05 15:35:22 +0000 @@ -1,3 +1,5 @@ +# Slow test, don't run during staging part +-- source include/not_staging.inc source include/master-slave.inc; # === modified file 'mysql-test/t/compress.test' --- a/mysql-test/t/compress.test 2009-02-09 21:00:15 +0000 +++ b/mysql-test/t/compress.test 2009-06-05 15:35:22 +0000 @@ -3,8 +3,9 @@ # Can't test with embedded server -- source include/not_embedded.inc - -- source include/have_compress.inc +# Slow test, don't run during staging part +-- source include/not_staging.inc # Save the initial number of concurrent sessions --source include/count_sessions.inc === modified file 'mysql-test/t/count_distinct3.test' --- a/mysql-test/t/count_distinct3.test 2006-10-03 07:03:35 +0000 +++ b/mysql-test/t/count_distinct3.test 2009-06-05 15:35:22 +0000 @@ -3,6 +3,8 @@ # mysql-4.1 # +# Slow test +-- source include/big_test.inc --disable_warnings DROP TABLE IF EXISTS t1, t2; --enable_warnings === modified file 'mysql-test/t/index_merge_innodb.test' --- a/mysql-test/t/index_merge_innodb.test 2006-09-18 14:55:56 +0000 +++ b/mysql-test/t/index_merge_innodb.test 2009-06-05 15:35:22 +0000 @@ -10,7 +10,10 @@ # include/index_merge*.inc files # +# Slow test, don't run during staging part +--source include/not_staging.inc --source include/have_innodb.inc + let $engine_type= InnoDB; # InnoDB does not support Merge tables (affects include/index_merge1.inc) let $merge_table_support= 0; === modified file 'mysql-test/t/information_schema_all_engines.test' --- a/mysql-test/t/information_schema_all_engines.test 2009-04-08 16:55:26 +0000 +++ b/mysql-test/t/information_schema_all_engines.test 2009-06-05 15:35:22 +0000 @@ -4,6 +4,7 @@ --source include/not_embedded.inc --source include/have_pbxt.inc +-- source include/not_staging.inc use INFORMATION_SCHEMA; --replace_result Tables_in_INFORMATION_SCHEMA Tables_in_information_schema === modified file 'mysql-test/t/innodb_mysql.test' --- a/mysql-test/t/innodb_mysql.test 2009-02-20 09:50:50 +0000 +++ b/mysql-test/t/innodb_mysql.test 2009-06-05 15:35:22 +0000 @@ -5,6 +5,8 @@ # main testing code t/innodb_mysql.test -> include/mix1.inc # +# Slow test, don't run during staging part +-- source include/not_staging.inc -- source include/have_innodb.inc let $engine_type= InnoDB; let $other_engine_type= MEMORY; === modified file 'mysql-test/t/pool_of_threads.test' --- a/mysql-test/t/pool_of_threads.test 2009-03-18 15:46:32 +0000 +++ b/mysql-test/t/pool_of_threads.test 2009-06-05 15:35:22 +0000 @@ -2,7 +2,8 @@ # and run a number of tests -- source include/have_pool_of_threads.inc - +# Slow test, don't run during staging part +-- source include/not_staging.inc -- source include/common-tests.inc === modified file 'mysql-test/t/preload.test' --- a/mysql-test/t/preload.test 2005-07-28 00:22:47 +0000 +++ b/mysql-test/t/preload.test 2009-06-05 15:35:22 +0000 @@ -2,6 +2,9 @@ # Testing of PRELOAD # +# Slow test, don't run during staging part +-- source include/not_staging.inc + --disable_warnings drop table if exists t1, t2; --enable_warnings === modified file 'mysql-test/t/ssl.test' --- a/mysql-test/t/ssl.test 2009-03-03 20:34:18 +0000 +++ b/mysql-test/t/ssl.test 2009-06-05 15:35:22 +0000 @@ -2,6 +2,8 @@ # and run a number of tests -- source include/have_ssl.inc +# Slow test, don't run during staging part +-- source include/not_staging.inc # Save the initial number of concurrent sessions --source include/count_sessions.inc === modified file 'mysql-test/t/ssl_compress.test' --- a/mysql-test/t/ssl_compress.test 2009-03-03 20:34:18 +0000 +++ b/mysql-test/t/ssl_compress.test 2009-06-05 15:35:22 +0000 @@ -3,6 +3,7 @@ -- source include/have_ssl.inc -- source include/have_compress.inc +-- source include/not_staging.inc # Save the initial number of concurrent sessions --source include/count_sessions.inc === modified file 'mysql-test/valgrind.supp' --- a/mysql-test/valgrind.supp 2009-05-22 12:38:50 +0000 +++ b/mysql-test/valgrind.supp 2009-06-05 15:35:22 +0000 @@ -415,7 +415,20 @@ } { - dlopen / ptread_cancel_init memory loss on Suse Linux 10.3 32/64 bit + dlclose memory loss from plugin variant 4 + Memcheck:Leak + fun:malloc + obj:/lib*/ld-*.so + obj:/lib*/ld-*.so + obj:/lib*/ld-*.so + obj:/lib*/libdl-*.so + fun:_dl_close + fun:_ZL15free_plugin_memP12st_plugin_dl + fun:_ZL13plugin_dl_delPK19st_mysql_lex_string +} + +{ + dlopen / ptread_cancel_init memory loss on Suse Linux 10.3 32/64 bit ver 1 Memcheck:Leak fun:*alloc obj:/lib*/ld-*.so @@ -433,6 +446,23 @@ } { + dlopen / ptread_cancel_init memory loss on Suse Linux 10.3 32/64 bit ver 2 + Memcheck:Leak + fun:*alloc + obj:/lib*/ld-*.so + obj:/lib*/ld-*.so + obj:/lib*/ld-*.so + obj:/lib*/ld-*.so + obj:/lib*/ld-*.so + obj:/lib*/libc-*.so + obj:/lib*/ld-*.so + obj:/lib*/libc-*.so + fun:__libc_dlopen_mode + fun:pthread_cancel_init + fun:_Unwind_ForcedUnwind +} + +{ dlopen / ptread_cancel_init memory loss on Suse Linux 10.3 32/64 bit Memcheck:Leak fun:*alloc === modified file 'sql/scheduler.cc' --- a/sql/scheduler.cc 2009-03-12 22:27:35 +0000 +++ b/sql/scheduler.cc 2009-06-05 15:35:22 +0000 @@ -282,8 +282,8 @@ static bool libevent_init(void) killed_threads= 0; kill_pool_threads= FALSE; - pthread_mutex_init(&LOCK_event_loop, NULL); - pthread_mutex_init(&LOCK_thd_add, NULL); + pthread_mutex_init(&LOCK_event_loop, MY_MUTEX_INIT_FAST); + pthread_mutex_init(&LOCK_thd_add, MY_MUTEX_INIT_FAST); /* set up sockets used to add new thds to the event pool */ if (init_socketpair(thd_add_pair))

1 0

[Maria-developers] Updated (by Guest): Table elimination (17)
by worklog-noreply＠askmonty.org 03 Jun '09

03 Jun '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination CREATION DATE..: Sun, 10 May 2009, 19:57 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 17 (http://askmonty.org/worklog/?tid=17) VERSION........: Server-5.1 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Wed, 03 Jun 2009, 22:01)=-=- Low Level Design modified. --- /tmp/wklog.17.old.21801 2009-06-03 22:01:34.000000000 +0300 +++ /tmp/wklog.17.new.21801 2009-06-03 22:01:34.000000000 +0300 @@ -1,3 +1,6 @@ +The code (currently in development) is at lp: +~maria-captains/maria/maria-5.1-table-elimination tree. + <contents> 1. Conditions for removal 1.1 Quick check if there are candidates -=-=(Guest - Wed, 03 Jun 2009, 15:04)=-=- Low Level Design modified. --- /tmp/wklog.17.old.20378 2009-06-03 15:04:54.000000000 +0300 +++ /tmp/wklog.17.new.20378 2009-06-03 15:04:54.000000000 +0300 @@ -135,3 +135,8 @@ Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? + +* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: + - affected tables must not be eliminated + - tables that are used on the right side of the SET x=y assignments must + not be eliminated either. -=-=(Psergey - Wed, 03 Jun 2009, 12:07)=-=- Dependency created: 29 now depends on 17 -=-=(Guest - Tue, 02 Jun 2009, 00:54)=-=- Low Level Design modified. --- /tmp/wklog.17.old.23548 2009-06-02 00:54:13.000000000 +0300 +++ /tmp/wklog.17.new.23548 2009-06-02 00:54:13.000000000 +0300 @@ -128,3 +128,10 @@ - this is what happens for constant tables, too. - I don't see how showing them could be of any use. They only make it harder to read the rewritten query. + +* Table elimination is performed after constant table detection (but before + the range analysis). Constant tables are technically different from + eliminated ones (e.g. the former are shown in EXPLAIN and the latter aren't). + Considering we've already done the join_read_const_table() call, is there any + real difference between constant table and eliminated one? If there is, should + we mark const tables also as eliminated? -=-=(Psergey - Mon, 01 Jun 2009, 20:46)=-=- Low Level Design modified. --- /tmp/wklog.17.old.17448 2009-06-01 20:46:40.000000000 +0300 +++ /tmp/wklog.17.new.17448 2009-06-01 20:46:40.000000000 +0300 @@ -122,3 +122,9 @@ always. If we want table elimination to work in presence of grouping, need to devise some other way of analyzing aggregate functions. + +* Should eliminated tables be shown in EXPLAIN EXTENDED? + - If we just ignore the question, they will be shown + - this is what happens for constant tables, too. + - I don't see how showing them could be of any use. They only make it + harder to read the rewritten query. -=-=(Guest - Mon, 01 Jun 2009, 12:49)=-=- Low Level Design modified. --- /tmp/wklog.17.old.32202 2009-06-01 12:49:15.000000000 +0300 +++ /tmp/wklog.17.new.32202 2009-06-01 12:49:15.000000000 +0300 @@ -8,7 +8,7 @@ 6. Todo, issues to resolve 6.1 To resolve 6.2 Resolved - +7. Additional issues </contents> It's not really about elimination of tables, it's about elimination of inner @@ -116,3 +116,9 @@ * We remove ON clauses within semi-join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? +* Aggregate functions report they depend on all tables, that is, + + item_agg_func->used_tables() == (1ULL << join->tables) - 1 + + always. If we want table elimination to work in presence of grouping, need + to devise some other way of analyzing aggregate functions. -=-=(Guest - Fri, 29 May 2009, 00:45)=-=- Low Level Design modified. --- /tmp/wklog.17.old.1348 2009-05-29 00:45:21.000000000 +0300 +++ /tmp/wklog.17.new.1348 2009-05-29 00:45:21.000000000 +0300 @@ -111,3 +111,8 @@ referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. +7. Additional issues +-------------------- +* We remove ON clauses within semi-join nests. If these clauses contain + subqueries, they probably should be gone from EXPLAIN output also? + -=-=(Guest - Tue, 26 May 2009, 21:52)=-=- Low Level Design modified. --- /tmp/wklog.17.old.14120 2009-05-26 21:52:06.000000000 +0300 +++ /tmp/wklog.17.new.14120 2009-05-26 21:52:06.000000000 +0300 @@ -1,11 +1,14 @@ <contents> 1. Conditions for removal +1.1 Quick check if there are candidates 2. Removal operation properties 3. Removal operation 4. User interface -5. Todo, issues to resolve -5.1 To resolve -5.2 Resolved +5. Tests and benchmarks +6. Todo, issues to resolve +6.1 To resolve +6.2 Resolved + </contents> It's not really about elimination of tables, it's about elimination of inner @@ -29,6 +32,18 @@ GROUP BY and HAVING do not refer to the inner tables of the outer join nest. +1.1 Quick check if there are candidates +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Before we start to enumerate join nests, here is a quick way to check if +there *can be* something to be removed: + + if ((tables used in select_list | + tables used in group/order by UNION | + tables used in where) != bitmap_of_all_tables) + { + attempt table elimination; + } + 2. Removal operation properties ------------------------------- * There is always one way to remove (no choice to remove either this or that) @@ -56,22 +71,24 @@ ----------------- * We'll add an @@optimizer switch flag for table elimination. Tentative name: 'table_elimination'. + (Note ^^ utility of the above questioned ^, as table elimination can never + be worse than no elimination. We're leaning towards not adding the flag) -* With EXPLAIN, there are two options: - - Show removed tables in a way similar to const tables, with some - indication that they are removed. - - Do not show them altogether. -(the second one seems to be better? We're targeting a situation with VIEWs, -where the user would not care about what tables were added into his query -and then discarded from it?) +* EXPLAIN will not show the removed tables at all. This will allow to check + if tables were removed, and also will behave nicely with anchor model and + VIEWs: stuff that user doesn't care about just won't be there. + +5. Tests and benchmarks +----------------------- +Should create a benchmark in sql-bench which checks if the dbms has table +elimination. +TODO elaborate -5. Todo, issues to resolve +6. Todo, issues to resolve -------------------------- -5.1 To resolve +6.1 To resolve ~~~~~~~~~~~~~~ -- See EXPLAIN question in section #4. - - Re-check how this works with equality propagation. - Relationship with prepared statements. @@ -87,7 +104,7 @@ that we'll meet outer joins which have N inner tables of which some are 1-row MyISAM tables that do not have primary key. -5.2 Resolved +6.2 Resolved ~~~~~~~~~~~~ - outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE -=-=(Guest - Fri, 22 May 2009, 17:23)=-=- High-Level Specification modified. --- /tmp/wklog.17.old.30851 2009-05-22 17:23:38.000000000 +0300 +++ /tmp/wklog.17.new.30851 2009-05-22 17:23:38.000000000 +0300 @@ -6,7 +6,7 @@ elimination but not to the same extent. Basically, what table elimination does, is to remove tables from the -execution plan when it is unneccessary to include them. This can, of +execution plan when it is unnecessary to include them. This can, of course, only happen if the right circumstances arise. Let us for example look at the following query: @@ -22,30 +22,26 @@ When using A as the left table we ensure that the query will return at least as many rows as there are in that table. For rows where the join condition (B.id = A.id) is not met the selected column (A.colA) will -contain a NULL value. +still contain it's original value. The not seen B.* row would contain all NULL:s. However, the result set could actually contain more rows than what is found in tableA if there are duplicates of the column B.id in tableB. If -A -contains a row [1, "val1"] and B the rows [1, "other1a"],[1, "other1b"] +A contains a row [1, "val1"] and B the rows [1, "other1a"],[1, "other1b"] then two rows will match in the join condition. The only way to know -what -the result will look like is to actually touch both tables during +what the result will look like is to actually touch both tables during execution. Instead, let's say that tableB contains rows that make it possible to place a unique constraint on the column B.id, for example and often the case a primary key. In this situation we know that we will get exactly -as -many rows as there are in tableA, since joining with tableB cannot +as many rows as there are in tableA, since joining with tableB cannot introduce any duplicates. If further, as in the example query, we do not select any columns from tableB, touching that table during execution is -unneccessary. We can remove the whole join operation from the execution +unnecessary. We can remove the whole join operation from the execution plan. Both SQL Server 2005/2008 and Oracle 11g will deploy table elimination -in -the case described above. Let us look at a more advanced query, where +in the case described above. Let us look at a more advanced query, where Oracle fails. select -=-=(Guest - Fri, 22 May 2009, 17:00)=-=- Version updated. --- /tmp/wklog.17.old.30176 2009-05-22 17:00:35.000000000 +0300 +++ /tmp/wklog.17.new.30176 2009-05-22 17:00:35.000000000 +0300 @@ -1 +1 @@ -Maria-2.0 +Server-5.1 ------------------------------------------------------------ -=-=(View All Progress Notes, 21 total)=-=- http://askmonty.org/worklog/index.pl?tid=17&nolimit=1 DESCRIPTION: Eliminate not needed tables from SELECT queries.. This will speed up some views and automatically generated queries. Example: CREATE TABLE B (id int primary key); select A.colA from tableA A left outer join tableB B on B.id = A.id; In this case we can remove table B and the join from the query. HIGH-LEVEL SPECIFICATION: Here is an extended explanation of table elimination. Table elimination is a feature found in some modern query optimizers, of which Microsoft SQL Server 2005/2008 seems to have the most advanced implementation. Oracle 11g has also been confirmed to use table elimination but not to the same extent. Basically, what table elimination does, is to remove tables from the execution plan when it is unnecessary to include them. This can, of course, only happen if the right circumstances arise. Let us for example look at the following query: select A.colA from tableA A left outer join tableB B on B.id = A.id; When using A as the left table we ensure that the query will return at least as many rows as there are in that table. For rows where the join condition (B.id = A.id) is not met the selected column (A.colA) will still contain it's original value. The not seen B.* row would contain all NULL:s. However, the result set could actually contain more rows than what is found in tableA if there are duplicates of the column B.id in tableB. If A contains a row [1, "val1"] and B the rows [1, "other1a"],[1, "other1b"] then two rows will match in the join condition. The only way to know what the result will look like is to actually touch both tables during execution. Instead, let's say that tableB contains rows that make it possible to place a unique constraint on the column B.id, for example and often the case a primary key. In this situation we know that we will get exactly as many rows as there are in tableA, since joining with tableB cannot introduce any duplicates. If further, as in the example query, we do not select any columns from tableB, touching that table during execution is unnecessary. We can remove the whole join operation from the execution plan. Both SQL Server 2005/2008 and Oracle 11g will deploy table elimination in the case described above. Let us look at a more advanced query, where Oracle fails. select A.colA from tableA A left outer join tableB B on B.id = A.id and B.fromDate = ( select max(sub.fromDate) from tableB sub where sub.id = A.id ); In this example we have added another join condition, which ensures that we only pick the matching row from tableB having the latest fromDate. In this case tableB will contain duplicates of the column B.id, so in order to ensure uniqueness the primary key has to contain the fromDate column as well. In other words the primary key of tableB is (B.id, B.fromDate). Furthermore, since the subselect ensures that we only pick the latest B.fromDate for a given B.id we know that at most one row will match the join condition. We will again have the situation where joining with tableB cannot affect the number of rows in the result set. Since we do not select any columns from tableB, the whole join operation can be eliminated from the execution plan. SQL Server 2005/2008 will deploy table elimination in this situation as well. We have not found a way to make Oracle 11g use it for this type of query. Queries like these arise in two situations. Either when you have denormalized model consisting of a fact table with several related dimension tables, or when you have a highly normalized model where each attribute is stored in its own table. The example with the subselect is common whenever you store historized/versioned data. LOW-LEVEL DESIGN: The code (currently in development) is at lp: ~maria-captains/maria/maria-5.1-table-elimination tree. <contents> 1. Conditions for removal 1.1 Quick check if there are candidates 2. Removal operation properties 3. Removal operation 4. User interface 5. Tests and benchmarks 6. Todo, issues to resolve 6.1 To resolve 6.2 Resolved 7. Additional issues </contents> It's not really about elimination of tables, it's about elimination of inner sides of outer joins. 1. Conditions for removal ------------------------- We can eliminate an inner side of outer join if: 1. For each record combination of outer tables, it will always produce exactly one record. 2. There are no references to columns of the inner tables anywhere else in the query. #1 means that every table inside the outer join nest is: - is a constant table: = because it can be accessed via eq_ref(const) access, or = it is a zero-rows or one-row MyISAM-like table [MARK1] - has an eq_ref access method candidate. #2 means that WHERE clause, ON clauses of embedding outer joins, ORDER BY, GROUP BY and HAVING do not refer to the inner tables of the outer join nest. 1.1 Quick check if there are candidates ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Before we start to enumerate join nests, here is a quick way to check if there *can be* something to be removed: if ((tables used in select_list | tables used in group/order by UNION | tables used in where) != bitmap_of_all_tables) { attempt table elimination; } 2. Removal operation properties ------------------------------- * There is always one way to remove (no choice to remove either this or that) * It is always better to remove as much tables as possible (at least within our cost model). Thus, no need for any cost calculations/etc. It's an unconditional rewrite. 3. Removal operation -------------------- * Remove the outer join nest's nested join structure (i.e. get the outer join's TABLE_LIST object $OJ and remove it from $OJ->embedding, $OJ->embedding->nested_join. Update table_map's of all ancestor nested joins). [MARK2] * Move the tables and their JOIN_TABs to front like it is done with const tables, with exception that if eliminated outer join nest was within another outer join nest, that shouldn't prevent us from moving away the eliminated tables. * Update join->table_count and all-join-tables bitmap. * That's it. Nothing else? 4. User interface ----------------- * We'll add an @@optimizer switch flag for table elimination. Tentative name: 'table_elimination'. (Note ^^ utility of the above questioned ^, as table elimination can never be worse than no elimination. We're leaning towards not adding the flag) * EXPLAIN will not show the removed tables at all. This will allow to check if tables were removed, and also will behave nicely with anchor model and VIEWs: stuff that user doesn't care about just won't be there. 5. Tests and benchmarks ----------------------- Should create a benchmark in sql-bench which checks if the dbms has table elimination. TODO elaborate 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ - Re-check how this works with equality propagation. - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have to limit the applicability by removing [MARK1] as that can change during lifetime of the statement. The other option is to do table elimination every time. This will require to rework operation [MARK2] to be undoable. I'm leaning towards doing the former. With anchor modeling, it is unlikely that we'll meet outer joins which have N inner tables of which some are 1-row MyISAM tables that do not have primary key. 6.2 Resolved ~~~~~~~~~~~~ - outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. 7. Additional issues -------------------- * We remove ON clauses within semi-join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? * Aggregate functions report they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 always. If we want table elimination to work in presence of grouping, need to devise some other way of analyzing aggregate functions. * Should eliminated tables be shown in EXPLAIN EXTENDED? - If we just ignore the question, they will be shown - this is what happens for constant tables, too. - I don't see how showing them could be of any use. They only make it harder to read the rewritten query. * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from eliminated ones (e.g. the former are shown in EXPLAIN and the latter aren't). Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? * For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - affected tables must not be eliminated - tables that are used on the right side of the SET x=y assignments must not be eliminated either. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Table elimination (17)
by worklog-noreply＠askmonty.org 03 Jun '09

03 Jun '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination CREATION DATE..: Sun, 10 May 2009, 19:57 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 17 (http://askmonty.org/worklog/?tid=17) VERSION........: Server-5.1 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Wed, 03 Jun 2009, 22:01)=-=- Low Level Design modified. --- /tmp/wklog.17.old.21801 2009-06-03 22:01:34.000000000 +0300 +++ /tmp/wklog.17.new.21801 2009-06-03 22:01:34.000000000 +0300 @@ -1,3 +1,6 @@ +The code (currently in development) is at lp: +~maria-captains/maria/maria-5.1-table-elimination tree. + <contents> 1. Conditions for removal 1.1 Quick check if there are candidates -=-=(Guest - Wed, 03 Jun 2009, 15:04)=-=- Low Level Design modified. --- /tmp/wklog.17.old.20378 2009-06-03 15:04:54.000000000 +0300 +++ /tmp/wklog.17.new.20378 2009-06-03 15:04:54.000000000 +0300 @@ -135,3 +135,8 @@ Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? + +* For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: + - affected tables must not be eliminated + - tables that are used on the right side of the SET x=y assignments must + not be eliminated either. -=-=(Psergey - Wed, 03 Jun 2009, 12:07)=-=- Dependency created: 29 now depends on 17 -=-=(Guest - Tue, 02 Jun 2009, 00:54)=-=- Low Level Design modified. --- /tmp/wklog.17.old.23548 2009-06-02 00:54:13.000000000 +0300 +++ /tmp/wklog.17.new.23548 2009-06-02 00:54:13.000000000 +0300 @@ -128,3 +128,10 @@ - this is what happens for constant tables, too. - I don't see how showing them could be of any use. They only make it harder to read the rewritten query. + +* Table elimination is performed after constant table detection (but before + the range analysis). Constant tables are technically different from + eliminated ones (e.g. the former are shown in EXPLAIN and the latter aren't). + Considering we've already done the join_read_const_table() call, is there any + real difference between constant table and eliminated one? If there is, should + we mark const tables also as eliminated? -=-=(Psergey - Mon, 01 Jun 2009, 20:46)=-=- Low Level Design modified. --- /tmp/wklog.17.old.17448 2009-06-01 20:46:40.000000000 +0300 +++ /tmp/wklog.17.new.17448 2009-06-01 20:46:40.000000000 +0300 @@ -122,3 +122,9 @@ always. If we want table elimination to work in presence of grouping, need to devise some other way of analyzing aggregate functions. + +* Should eliminated tables be shown in EXPLAIN EXTENDED? + - If we just ignore the question, they will be shown + - this is what happens for constant tables, too. + - I don't see how showing them could be of any use. They only make it + harder to read the rewritten query. -=-=(Guest - Mon, 01 Jun 2009, 12:49)=-=- Low Level Design modified. --- /tmp/wklog.17.old.32202 2009-06-01 12:49:15.000000000 +0300 +++ /tmp/wklog.17.new.32202 2009-06-01 12:49:15.000000000 +0300 @@ -8,7 +8,7 @@ 6. Todo, issues to resolve 6.1 To resolve 6.2 Resolved - +7. Additional issues </contents> It's not really about elimination of tables, it's about elimination of inner @@ -116,3 +116,9 @@ * We remove ON clauses within semi-join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? +* Aggregate functions report they depend on all tables, that is, + + item_agg_func->used_tables() == (1ULL << join->tables) - 1 + + always. If we want table elimination to work in presence of grouping, need + to devise some other way of analyzing aggregate functions. -=-=(Guest - Fri, 29 May 2009, 00:45)=-=- Low Level Design modified. --- /tmp/wklog.17.old.1348 2009-05-29 00:45:21.000000000 +0300 +++ /tmp/wklog.17.new.1348 2009-05-29 00:45:21.000000000 +0300 @@ -111,3 +111,8 @@ referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. +7. Additional issues +-------------------- +* We remove ON clauses within semi-join nests. If these clauses contain + subqueries, they probably should be gone from EXPLAIN output also? + -=-=(Guest - Tue, 26 May 2009, 21:52)=-=- Low Level Design modified. --- /tmp/wklog.17.old.14120 2009-05-26 21:52:06.000000000 +0300 +++ /tmp/wklog.17.new.14120 2009-05-26 21:52:06.000000000 +0300 @@ -1,11 +1,14 @@ <contents> 1. Conditions for removal +1.1 Quick check if there are candidates 2. Removal operation properties 3. Removal operation 4. User interface -5. Todo, issues to resolve -5.1 To resolve -5.2 Resolved +5. Tests and benchmarks +6. Todo, issues to resolve +6.1 To resolve +6.2 Resolved + </contents> It's not really about elimination of tables, it's about elimination of inner @@ -29,6 +32,18 @@ GROUP BY and HAVING do not refer to the inner tables of the outer join nest. +1.1 Quick check if there are candidates +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Before we start to enumerate join nests, here is a quick way to check if +there *can be* something to be removed: + + if ((tables used in select_list | + tables used in group/order by UNION | + tables used in where) != bitmap_of_all_tables) + { + attempt table elimination; + } + 2. Removal operation properties ------------------------------- * There is always one way to remove (no choice to remove either this or that) @@ -56,22 +71,24 @@ ----------------- * We'll add an @@optimizer switch flag for table elimination. Tentative name: 'table_elimination'. + (Note ^^ utility of the above questioned ^, as table elimination can never + be worse than no elimination. We're leaning towards not adding the flag) -* With EXPLAIN, there are two options: - - Show removed tables in a way similar to const tables, with some - indication that they are removed. - - Do not show them altogether. -(the second one seems to be better? We're targeting a situation with VIEWs, -where the user would not care about what tables were added into his query -and then discarded from it?) +* EXPLAIN will not show the removed tables at all. This will allow to check + if tables were removed, and also will behave nicely with anchor model and + VIEWs: stuff that user doesn't care about just won't be there. + +5. Tests and benchmarks +----------------------- +Should create a benchmark in sql-bench which checks if the dbms has table +elimination. +TODO elaborate -5. Todo, issues to resolve +6. Todo, issues to resolve -------------------------- -5.1 To resolve +6.1 To resolve ~~~~~~~~~~~~~~ -- See EXPLAIN question in section #4. - - Re-check how this works with equality propagation. - Relationship with prepared statements. @@ -87,7 +104,7 @@ that we'll meet outer joins which have N inner tables of which some are 1-row MyISAM tables that do not have primary key. -5.2 Resolved +6.2 Resolved ~~~~~~~~~~~~ - outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE -=-=(Guest - Fri, 22 May 2009, 17:23)=-=- High-Level Specification modified. --- /tmp/wklog.17.old.30851 2009-05-22 17:23:38.000000000 +0300 +++ /tmp/wklog.17.new.30851 2009-05-22 17:23:38.000000000 +0300 @@ -6,7 +6,7 @@ elimination but not to the same extent. Basically, what table elimination does, is to remove tables from the -execution plan when it is unneccessary to include them. This can, of +execution plan when it is unnecessary to include them. This can, of course, only happen if the right circumstances arise. Let us for example look at the following query: @@ -22,30 +22,26 @@ When using A as the left table we ensure that the query will return at least as many rows as there are in that table. For rows where the join condition (B.id = A.id) is not met the selected column (A.colA) will -contain a NULL value. +still contain it's original value. The not seen B.* row would contain all NULL:s. However, the result set could actually contain more rows than what is found in tableA if there are duplicates of the column B.id in tableB. If -A -contains a row [1, "val1"] and B the rows [1, "other1a"],[1, "other1b"] +A contains a row [1, "val1"] and B the rows [1, "other1a"],[1, "other1b"] then two rows will match in the join condition. The only way to know -what -the result will look like is to actually touch both tables during +what the result will look like is to actually touch both tables during execution. Instead, let's say that tableB contains rows that make it possible to place a unique constraint on the column B.id, for example and often the case a primary key. In this situation we know that we will get exactly -as -many rows as there are in tableA, since joining with tableB cannot +as many rows as there are in tableA, since joining with tableB cannot introduce any duplicates. If further, as in the example query, we do not select any columns from tableB, touching that table during execution is -unneccessary. We can remove the whole join operation from the execution +unnecessary. We can remove the whole join operation from the execution plan. Both SQL Server 2005/2008 and Oracle 11g will deploy table elimination -in -the case described above. Let us look at a more advanced query, where +in the case described above. Let us look at a more advanced query, where Oracle fails. select -=-=(Guest - Fri, 22 May 2009, 17:00)=-=- Version updated. --- /tmp/wklog.17.old.30176 2009-05-22 17:00:35.000000000 +0300 +++ /tmp/wklog.17.new.30176 2009-05-22 17:00:35.000000000 +0300 @@ -1 +1 @@ -Maria-2.0 +Server-5.1 ------------------------------------------------------------ -=-=(View All Progress Notes, 21 total)=-=- http://askmonty.org/worklog/index.pl?tid=17&nolimit=1 DESCRIPTION: Eliminate not needed tables from SELECT queries.. This will speed up some views and automatically generated queries. Example: CREATE TABLE B (id int primary key); select A.colA from tableA A left outer join tableB B on B.id = A.id; In this case we can remove table B and the join from the query. HIGH-LEVEL SPECIFICATION: Here is an extended explanation of table elimination. Table elimination is a feature found in some modern query optimizers, of which Microsoft SQL Server 2005/2008 seems to have the most advanced implementation. Oracle 11g has also been confirmed to use table elimination but not to the same extent. Basically, what table elimination does, is to remove tables from the execution plan when it is unnecessary to include them. This can, of course, only happen if the right circumstances arise. Let us for example look at the following query: select A.colA from tableA A left outer join tableB B on B.id = A.id; When using A as the left table we ensure that the query will return at least as many rows as there are in that table. For rows where the join condition (B.id = A.id) is not met the selected column (A.colA) will still contain it's original value. The not seen B.* row would contain all NULL:s. However, the result set could actually contain more rows than what is found in tableA if there are duplicates of the column B.id in tableB. If A contains a row [1, "val1"] and B the rows [1, "other1a"],[1, "other1b"] then two rows will match in the join condition. The only way to know what the result will look like is to actually touch both tables during execution. Instead, let's say that tableB contains rows that make it possible to place a unique constraint on the column B.id, for example and often the case a primary key. In this situation we know that we will get exactly as many rows as there are in tableA, since joining with tableB cannot introduce any duplicates. If further, as in the example query, we do not select any columns from tableB, touching that table during execution is unnecessary. We can remove the whole join operation from the execution plan. Both SQL Server 2005/2008 and Oracle 11g will deploy table elimination in the case described above. Let us look at a more advanced query, where Oracle fails. select A.colA from tableA A left outer join tableB B on B.id = A.id and B.fromDate = ( select max(sub.fromDate) from tableB sub where sub.id = A.id ); In this example we have added another join condition, which ensures that we only pick the matching row from tableB having the latest fromDate. In this case tableB will contain duplicates of the column B.id, so in order to ensure uniqueness the primary key has to contain the fromDate column as well. In other words the primary key of tableB is (B.id, B.fromDate). Furthermore, since the subselect ensures that we only pick the latest B.fromDate for a given B.id we know that at most one row will match the join condition. We will again have the situation where joining with tableB cannot affect the number of rows in the result set. Since we do not select any columns from tableB, the whole join operation can be eliminated from the execution plan. SQL Server 2005/2008 will deploy table elimination in this situation as well. We have not found a way to make Oracle 11g use it for this type of query. Queries like these arise in two situations. Either when you have denormalized model consisting of a fact table with several related dimension tables, or when you have a highly normalized model where each attribute is stored in its own table. The example with the subselect is common whenever you store historized/versioned data. LOW-LEVEL DESIGN: The code (currently in development) is at lp: ~maria-captains/maria/maria-5.1-table-elimination tree. <contents> 1. Conditions for removal 1.1 Quick check if there are candidates 2. Removal operation properties 3. Removal operation 4. User interface 5. Tests and benchmarks 6. Todo, issues to resolve 6.1 To resolve 6.2 Resolved 7. Additional issues </contents> It's not really about elimination of tables, it's about elimination of inner sides of outer joins. 1. Conditions for removal ------------------------- We can eliminate an inner side of outer join if: 1. For each record combination of outer tables, it will always produce exactly one record. 2. There are no references to columns of the inner tables anywhere else in the query. #1 means that every table inside the outer join nest is: - is a constant table: = because it can be accessed via eq_ref(const) access, or = it is a zero-rows or one-row MyISAM-like table [MARK1] - has an eq_ref access method candidate. #2 means that WHERE clause, ON clauses of embedding outer joins, ORDER BY, GROUP BY and HAVING do not refer to the inner tables of the outer join nest. 1.1 Quick check if there are candidates ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Before we start to enumerate join nests, here is a quick way to check if there *can be* something to be removed: if ((tables used in select_list | tables used in group/order by UNION | tables used in where) != bitmap_of_all_tables) { attempt table elimination; } 2. Removal operation properties ------------------------------- * There is always one way to remove (no choice to remove either this or that) * It is always better to remove as much tables as possible (at least within our cost model). Thus, no need for any cost calculations/etc. It's an unconditional rewrite. 3. Removal operation -------------------- * Remove the outer join nest's nested join structure (i.e. get the outer join's TABLE_LIST object $OJ and remove it from $OJ->embedding, $OJ->embedding->nested_join. Update table_map's of all ancestor nested joins). [MARK2] * Move the tables and their JOIN_TABs to front like it is done with const tables, with exception that if eliminated outer join nest was within another outer join nest, that shouldn't prevent us from moving away the eliminated tables. * Update join->table_count and all-join-tables bitmap. * That's it. Nothing else? 4. User interface ----------------- * We'll add an @@optimizer switch flag for table elimination. Tentative name: 'table_elimination'. (Note ^^ utility of the above questioned ^, as table elimination can never be worse than no elimination. We're leaning towards not adding the flag) * EXPLAIN will not show the removed tables at all. This will allow to check if tables were removed, and also will behave nicely with anchor model and VIEWs: stuff that user doesn't care about just won't be there. 5. Tests and benchmarks ----------------------- Should create a benchmark in sql-bench which checks if the dbms has table elimination. TODO elaborate 6. Todo, issues to resolve -------------------------- 6.1 To resolve ~~~~~~~~~~~~~~ - Re-check how this works with equality propagation. - Relationship with prepared statements. On one hand, it's natural to desire to make table elimination a once-per-statement operation, like outer->inner join conversion. We'll have to limit the applicability by removing [MARK1] as that can change during lifetime of the statement. The other option is to do table elimination every time. This will require to rework operation [MARK2] to be undoable. I'm leaning towards doing the former. With anchor modeling, it is unlikely that we'll meet outer joins which have N inner tables of which some are 1-row MyISAM tables that do not have primary key. 6.2 Resolved ~~~~~~~~~~~~ - outer->inner join conversion is not a problem for table elimination. We make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (requirement for OJ->IJ conversion) then table elimination would not be applicable anyway. 7. Additional issues -------------------- * We remove ON clauses within semi-join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? * Aggregate functions report they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 always. If we want table elimination to work in presence of grouping, need to devise some other way of analyzing aggregate functions. * Should eliminated tables be shown in EXPLAIN EXTENDED? - If we just ignore the question, they will be shown - this is what happens for constant tables, too. - I don't see how showing them could be of any use. They only make it harder to read the rewritten query. * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from eliminated ones (e.g. the former are shown in EXPLAIN and the latter aren't). Considering we've already done the join_read_const_table() call, is there any real difference between constant table and eliminated one? If there is, should we mark const tables also as eliminated? * For Multi-table UPDATEs/DELETEs, need to also analyze the SET clause: - affected tables must not be eliminated - tables that are used on the right side of the SET x=y assignments must not be eliminated either. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (psergey:2708)
by Sergey Petrunia 03 Jun '09

03 Jun '09

#At lp:maria based on revid:knielsen@knielsen-hq.org-20090602110359-n4q9gof38buucrny 2708 Sergey Petrunia 2009-06-03 [merge] Merge MWL#17 with maria/5.1 added: mysql-test/r/table_elim.result mysql-test/t/table_elim.test modified: sql/sql_select.cc sql/sql_select.h sql/table.h === added file 'mysql-test/r/table_elim.result' --- a/mysql-test/r/table_elim.result 1970-01-01 00:00:00 +0000 +++ b/mysql-test/r/table_elim.result 2009-06-03 13:10:45 +0000 @@ -0,0 +1,56 @@ +drop table if exists t0, t1, t2, t3; +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 +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 +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 Extra +1 SIMPLE t0 ALL NULL NULL NULL NULL 4 +1 SIMPLE t1 ALL NULL NULL NULL NULL 4 +drop table t0, t1, t2, t3; === added file 'mysql-test/t/table_elim.test' --- a/mysql-test/t/table_elim.test 1970-01-01 00:00:00 +0000 +++ b/mysql-test/t/table_elim.test 2009-06-03 13:10:45 +0000 @@ -0,0 +1,52 @@ +# +# Table elimination (MWL#17) tests +# +--disable_warnings +drop table if exists t0, t1, t2, t3; +--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; + +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; + +## TODO: Aggregate functions prevent table elimination ATM. + +--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 +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; + + +drop table t0, t1, t2, t3; + === modified file 'sql/sql_select.cc' --- a/sql/sql_select.cc 2009-05-19 09:28:05 +0000 +++ b/sql/sql_select.cc 2009-06-03 13:10:45 +0000 @@ -42,6 +42,11 @@ #define TMP_ENGINE_HTON myisam_hton #endif +#define FT_KEYPART (MAX_REF_PARTS+10) +/* Values in optimize */ +#define KEY_OPTIMIZE_EXISTS 1 +#define KEY_OPTIMIZE_REF_OR_NULL 2 + const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref", "MAYBE_REF","ALL","range","index","fulltext", "ref_or_null","unique_subquery","index_subquery", @@ -2468,6 +2473,304 @@ static ha_rows get_quick_record_count(TH DBUG_RETURN(HA_POS_ERROR); /* This shouldn't happend */ } + +bool has_eq_ref_access_candidate(TABLE *table, table_map can_refer_to_these) +{ + KEYUSE *keyuse= table->reginfo.join_tab->keyuse; + if (keyuse) + { + /* + walk through all of the KEYUSE elements and + - locate unique keys + - check if we have eq_ref access for them + TODO any other reqs? + loops are constructed like in best_access_path + */ + while (keyuse->table == table) + { + uint key= keyuse->key; + key_part_map bound_parts=0; + bool ft_key= test(keyuse->keypart == FT_KEYPART); + + do /* For each keypart and each way to read it */ + { + if (!(keyuse->used_tables & ~can_refer_to_these) && + !(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)) + { + bound_parts |= keyuse->keypart_map; + } + keyuse++; + } while (keyuse->table && keyuse->key == key); + + KEY *keyinfo= table->key_info + key; + if (!ft_key && + ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME) && + bound_parts == PREV_BITS(key_part_map, keyinfo->key_parts)) + { + return TRUE; + } + } + } + return FALSE; +} + + +static void mark_table_as_eliminated(JOIN *join, TABLE *table, uint *const_tbl_count, + table_map *const_tables) +{ + JOIN_TAB *tab= table->reginfo.join_tab; + if (!(*const_tables & tab->table->map)) + { + DBUG_PRINT("info", ("Eliminated table %s", table->alias)); + tab->type= JT_CONST; + tab->eliminated= TRUE; + *const_tables |= table->map; + join->const_table_map|= table->map; + set_position(join, (*const_tbl_count)++, tab, (KEYUSE*)0); + } +} + + +/* + Now on to traversal. There can be a situation like this: + + FROM t1 + LEFT JOIN t2 ON cond(t1,t2) + LEFT JOIN t3 ON cond(..., possibly-t2) // <--(*) + LEFT JOIN t4 ON cond(..., possibly-t2) + + Besides that, simplify_joins() may have created back references, so when + we're e.g. looking at outer join (*) we need to look both forward and + backward to check if there are any references in preceding/following + outer joins' + + TODO would it create only following-sibling references or + preceding-sibling as well? + And if not, should we rely on that? + +*/ + +int +eliminate_tables_for_join_list(JOIN *join, List<TABLE_LIST> *join_list, + table_map used_tables_elsewhere, + uint *const_tbl_count, table_map *const_tables) +{ + List_iterator<TABLE_LIST> it(*join_list); + table_map used_tables_on_right[MAX_TABLES]; // todo change to alloca + table_map used_tables_on_left; + TABLE_LIST *tbl; + int i, n_tables; + int eliminated=0; + + /* Collect the reverse-bitmap-array */ + for (i=0; (tbl= it++); i++) + { + used_tables_on_right[i]= 0; + if (tbl->on_expr) + used_tables_on_right[i]= tbl->on_expr->used_tables(); + if (tbl->nested_join) + used_tables_on_right[i]= tbl->nested_join->used_tables; + } + n_tables= i; + + for (i= n_tables - 2; i > 0; i--) + used_tables_on_right[i] |= used_tables_on_right[i+1]; + + it.rewind(); + + /* Walk through tables and join nests and see if we can eliminate them */ + used_tables_on_left= 0; + i= 1; + while ((tbl= it++)) + { + table_map tables_used_outside= used_tables_on_left | + used_tables_on_right[i] | + used_tables_elsewhere; + table_map cur_tables; + + if (tbl->nested_join) + { + DBUG_ASSERT(tbl->on_expr); + /* + There can be cases where table removal is applicable for tables + within the outer join but not for the outer join itself. Ask to + remove the children first. + + TODO: NoHopelessEliminationAttempts: the below call can return + information about whether it would make any sense to try removing + this entire outer join nest. + */ + int eliminated_in_children= + eliminate_tables_for_join_list(join, &tbl->nested_join->join_list, + tables_used_outside, + const_tbl_count, const_tables); + tbl->nested_join->n_tables -=eliminated_in_children; + cur_tables= tbl->nested_join->used_tables; + if (!(cur_tables & tables_used_outside)) + { + /* + Check if all embedded tables together can produce at most one + record combination. This is true when + - each of them has one_match(outer-tables) property + (this is a stronger condition than all of them together having + this property but that's irrelevant here) + - there are no outer joins among them + (except for the case of outer join which has all inner tables + to be constant and is guaranteed to produce only one record. + that record will be null-complemented) + */ + bool one_match= TRUE; + List_iterator<TABLE_LIST> it2(tbl->nested_join->join_list); + TABLE_LIST *inner; + while ((inner= it2++)) + { + /* + Bail out if we see an outer join (TODO: handle the above + null-complemntated-rows-only case) + */ + if (inner->on_expr) + { + one_match= FALSE; + break; + } + + if (inner->table && // <-- to be removed after NoHopelessEliminationAttempts + !has_eq_ref_access_candidate(inner->table, + ~tbl->nested_join->used_tables)) + { + one_match= FALSE; + break; + } + } + if (one_match) + { + it2.rewind(); + while ((inner= it2++)) + { + mark_table_as_eliminated(join, inner->table, const_tbl_count, + const_tables); + } + eliminated += tbl->nested_join->join_list.elements; + //psergey-todo: do we need to do anything about removing the join + //nest? + } + else + { + eliminated += eliminated_in_children; + } + } + } + else if (tbl->on_expr) + { + cur_tables= tbl->on_expr->used_tables(); + /* Check and remove */ + if (!(tbl->table->map & tables_used_outside) && + has_eq_ref_access_candidate(tbl->table, (table_map)-1)) + { + mark_table_as_eliminated(join, tbl->table, const_tbl_count, + const_tables); + eliminated += 1; + } + } + + /* Update bitmap of tables we've seen on the left */ + i++; + used_tables_on_left |= cur_tables; + } + return eliminated; +} + + +/* + Perform table elimination based on outer join + + SELECT * FROM t1 LEFT JOIN + (t2 JOIN t3) ON t3.primary_key=t1.col AND + t4.primary_key= t2.col + + CRITERIA FOR REMOVING ONE OJ NEST + we can't rely on sole presense of eq_refs. Because if we do, we'll miss + things like this: + + SELECT * FROM flights LEFT JOIN + (pax as S1 JOIN pax as S2 ON S2.id=S1.spouse AND s1.id=s2.spouse) + + (no-polygamy schema/query but there can be many couples on the flight) + .. + + REMOVAL PROCESS + We can remove an inner side of an outer join if it there is a warranty + that it will produce not more than one record: + + ... t1 LEFT JOIN t2 ON (t2.unique_key = expr) ... + + For nested outer joins: + - The process naturally occurs bottom-up (in order to remove an + outer-join we need to analyze its contents) + - If we failed to remove an outer join nest, it makes no sense to + try removing its ancestors, as the + ot LEFT JOIN it ON cond + pair may possibly produce two records (one record via match and + another one as access-method record). + + Q: If we haven't removed an OUTER JOIN, does it make sense to attempt + removing its ancestors? + A: No as the innermost outer join will produce two records => no ancestor + outer join nest will be able to provide the max_fanout==1 guarantee. + + psergey-todo: . +*/ + +static void eliminate_tables(JOIN *join, uint *const_tbl_count, table_map *const_tables) +{ + Item *item; + table_map used_tables; + DBUG_ENTER("eliminate_tables"); + if (!join->outer_join) + DBUG_VOID_RETURN; + + /* Find the tables that are referred to from WHERE/HAVING */ + used_tables= (join->conds? join->conds->used_tables() : 0) | + (join->having? join->having->used_tables() : 0); + + /* Add tables referred to from the select list */ + List_iterator<Item> it(join->fields_list); + while ((item= it++)) + used_tables |= item->used_tables(); + + /* Add tables referred to from ORDER BY and GROUP BY lists */ + ORDER *all_lists[]= { join->order, join->group_list}; + for (int i=0; i < 2; i++) + { + for (ORDER *cur_list= all_lists[i]; cur_list; cur_list= cur_list->next) + used_tables |= (*(cur_list->item))->used_tables(); + } + + THD* thd= join->thd; + if (join->select_lex == &thd->lex->select_lex) + { + /* Multi-table UPDATE and DELETE: don't eliminate the tables we modify: */ + used_tables |= thd->table_map_for_update; + + /* Multi-table UPDATE: don't eliminate tables referred from SET statement */ + if (thd->lex->sql_command == SQLCOM_UPDATE_MULTI) + { + List_iterator<Item> it2(thd->lex->value_list); + while ((item= it2++)) + used_tables |= item->used_tables(); + } + } + + if (((1 << join->tables) - 1) & ~used_tables) + { + /* There are some time tables that we probably could eliminate */ + eliminate_tables_for_join_list(join, join->join_list, used_tables, + const_tbl_count, const_tables); + } + DBUG_VOID_RETURN; +} + + /* This structure is used to collect info on potentially sargable predicates in order to check whether they become sargable after @@ -2823,6 +3126,10 @@ make_join_statistics(JOIN *join, TABLE_L } } + //psergey-todo: table elimination + eliminate_tables(join, &const_count, &found_const_table_map); + //:psergey-todo + /* Calc how many (possible) matched records in each table */ for (s=stat ; s < stat_end ; s++) @@ -2956,9 +3263,6 @@ typedef struct key_field_t { bool *cond_guard; /* See KEYUSE::cond_guard */ } KEY_FIELD; -/* Values in optimize */ -#define KEY_OPTIMIZE_EXISTS 1 -#define KEY_OPTIMIZE_REF_OR_NULL 2 /** Merge new key definitions to old ones, remove those not used in both. @@ -3563,7 +3867,6 @@ add_key_part(DYNAMIC_ARRAY *keyuse_array } -#define FT_KEYPART (MAX_REF_PARTS+10) static void add_ft_keys(DYNAMIC_ARRAY *keyuse_array, @@ -6021,7 +6324,7 @@ make_outerjoin_info(JOIN *join) } if (!tab->first_inner) tab->first_inner= nested_join->first_nested; - if (++nested_join->counter < nested_join->join_list.elements) + if (++nested_join->counter < nested_join->n_tables) break; /* Table tab is the last inner table for nested join. */ nested_join->first_nested->last_inner= tab; @@ -8575,6 +8878,8 @@ simplify_joins(JOIN *join, List<TABLE_LI 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 +9038,7 @@ static uint build_bitmap_for_nested_join with anything) 2. we could run out bits in nested_join_map otherwise. */ - if (nested_join->join_list.elements != 1) + if (nested_join->n_tables != 1) { nested_join->nj_map= (nested_join_map) 1 << first_unused++; first_unused= build_bitmap_for_nested_joins(&nested_join->join_list, @@ -8894,7 +9199,7 @@ static bool check_interleaving_with_nj(J join->cur_embedding_map |= next_emb->nested_join->nj_map; } - if (next_emb->nested_join->join_list.elements != + if (next_emb->nested_join->n_tables != next_emb->nested_join->counter) break; @@ -8928,7 +9233,7 @@ static void restore_prev_nj_state(JOIN_T { if (!(--last_emb->nested_join->counter)) join->cur_embedding_map&= ~last_emb->nested_join->nj_map; - else if (last_emb->nested_join->join_list.elements-1 == + else if (last_emb->nested_join->n_tables-1 == last_emb->nested_join->counter) join->cur_embedding_map|= last_emb->nested_join->nj_map; else @@ -16202,6 +16507,14 @@ static void select_describe(JOIN *join, tmp3.length(0); quick_type= -1; + + //psergey-todo: + if (tab->eliminated) + { + used_tables|=table->map; + continue; + } + item_list.empty(); /* id */ item_list.push_back(new Item_uint((uint32) === modified file 'sql/sql_select.h' --- a/sql/sql_select.h 2009-04-25 10:05:32 +0000 +++ b/sql/sql_select.h 2009-06-03 13:10:45 +0000 @@ -210,6 +210,9 @@ typedef struct st_join_table { JOIN *join; /** Bitmap of nested joins this table is part of */ nested_join_map embedding_map; + + //psergey-todo: more justified place + bool eliminated; void cleanup(); inline bool is_using_loose_index_scan() === modified file 'sql/table.h' --- a/sql/table.h 2009-02-19 09:01:25 +0000 +++ b/sql/table.h 2009-06-03 13:10:45 +0000 @@ -1626,6 +1626,8 @@ typedef struct st_nested_join Before each use the counters are zeroed by reset_nj_counters. */ uint counter; + /* Tables left after elimination */ + uint n_tables; nested_join_map nj_map; /* Bit used to identify this nested join*/ } NESTED_JOIN;

1 0

[Maria-developers] Please add into buildbot: lp:~maria-captains/maria-5.1-table-elimination
by Sergey Petrunya 03 Jun '09

03 Jun '09

Hi Kristian, I've got a branch with the code for MWL#17. Could you please add it to what BuildBot builds? Thanks, Sergey -- Sergey Petrunia, Software Developer Monty Program AB, http://askmonty.org Blog: http://s.petrunia.net/blog

2 1

[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (psergey:2706)
by Sergey Petrunia 03 Jun '09

03 Jun '09

#At lp:maria based on revid:knielsen@knielsen-hq.org-20090522175325-xpwm83ilnhqoqjz0 2706 Sergey Petrunia 2009-06-03 MWL#17: Table elimination - First code. Elimination works for simple cases, passes the testsuite. - Known issues: = No elimination is done for aggregate functions. = EXPLAIN EXTENDED shows eliminated tables (I think it better not) = No benchmark yet = The code needs some polishing. added: mysql-test/r/table_elim.result mysql-test/t/table_elim.test modified: sql/sql_select.cc sql/sql_select.h sql/table.h per-file messages: mysql-test/r/table_elim.result MWL#17: Table elimination - Testcases mysql-test/t/table_elim.test MWL#17: Table elimination - Testcases sql/sql_select.cc MWL#17: Table elimination sql/sql_select.h MWL#17: Table elimination - Added JOIN_TAB::eliminated (is JOIN_TAB the best place to store this flag?) sql/table.h MWL#17: Table elimination - ADded NESTED_JOIN::n_tables. We need to have the number of real tables remaining in an outer join nest. === added file 'mysql-test/r/table_elim.result' --- a/mysql-test/r/table_elim.result 1970-01-01 00:00:00 +0000 +++ b/mysql-test/r/table_elim.result 2009-06-03 13:10:45 +0000 @@ -0,0 +1,56 @@ +drop table if exists t0, t1, t2, t3; +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 +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 +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 Extra +1 SIMPLE t0 ALL NULL NULL NULL NULL 4 +1 SIMPLE t1 ALL NULL NULL NULL NULL 4 +drop table t0, t1, t2, t3; === added file 'mysql-test/t/table_elim.test' --- a/mysql-test/t/table_elim.test 1970-01-01 00:00:00 +0000 +++ b/mysql-test/t/table_elim.test 2009-06-03 13:10:45 +0000 @@ -0,0 +1,52 @@ +# +# Table elimination (MWL#17) tests +# +--disable_warnings +drop table if exists t0, t1, t2, t3; +--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; + +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; + +## TODO: Aggregate functions prevent table elimination ATM. + +--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 +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; + + +drop table t0, t1, t2, t3; + === modified file 'sql/sql_select.cc' --- a/sql/sql_select.cc 2009-05-19 09:28:05 +0000 +++ b/sql/sql_select.cc 2009-06-03 13:10:45 +0000 @@ -42,6 +42,11 @@ #define TMP_ENGINE_HTON myisam_hton #endif +#define FT_KEYPART (MAX_REF_PARTS+10) +/* Values in optimize */ +#define KEY_OPTIMIZE_EXISTS 1 +#define KEY_OPTIMIZE_REF_OR_NULL 2 + const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref", "MAYBE_REF","ALL","range","index","fulltext", "ref_or_null","unique_subquery","index_subquery", @@ -2468,6 +2473,304 @@ static ha_rows get_quick_record_count(TH DBUG_RETURN(HA_POS_ERROR); /* This shouldn't happend */ } + +bool has_eq_ref_access_candidate(TABLE *table, table_map can_refer_to_these) +{ + KEYUSE *keyuse= table->reginfo.join_tab->keyuse; + if (keyuse) + { + /* + walk through all of the KEYUSE elements and + - locate unique keys + - check if we have eq_ref access for them + TODO any other reqs? + loops are constructed like in best_access_path + */ + while (keyuse->table == table) + { + uint key= keyuse->key; + key_part_map bound_parts=0; + bool ft_key= test(keyuse->keypart == FT_KEYPART); + + do /* For each keypart and each way to read it */ + { + if (!(keyuse->used_tables & ~can_refer_to_these) && + !(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)) + { + bound_parts |= keyuse->keypart_map; + } + keyuse++; + } while (keyuse->table && keyuse->key == key); + + KEY *keyinfo= table->key_info + key; + if (!ft_key && + ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME) && + bound_parts == PREV_BITS(key_part_map, keyinfo->key_parts)) + { + return TRUE; + } + } + } + return FALSE; +} + + +static void mark_table_as_eliminated(JOIN *join, TABLE *table, uint *const_tbl_count, + table_map *const_tables) +{ + JOIN_TAB *tab= table->reginfo.join_tab; + if (!(*const_tables & tab->table->map)) + { + DBUG_PRINT("info", ("Eliminated table %s", table->alias)); + tab->type= JT_CONST; + tab->eliminated= TRUE; + *const_tables |= table->map; + join->const_table_map|= table->map; + set_position(join, (*const_tbl_count)++, tab, (KEYUSE*)0); + } +} + + +/* + Now on to traversal. There can be a situation like this: + + FROM t1 + LEFT JOIN t2 ON cond(t1,t2) + LEFT JOIN t3 ON cond(..., possibly-t2) // <--(*) + LEFT JOIN t4 ON cond(..., possibly-t2) + + Besides that, simplify_joins() may have created back references, so when + we're e.g. looking at outer join (*) we need to look both forward and + backward to check if there are any references in preceding/following + outer joins' + + TODO would it create only following-sibling references or + preceding-sibling as well? + And if not, should we rely on that? + +*/ + +int +eliminate_tables_for_join_list(JOIN *join, List<TABLE_LIST> *join_list, + table_map used_tables_elsewhere, + uint *const_tbl_count, table_map *const_tables) +{ + List_iterator<TABLE_LIST> it(*join_list); + table_map used_tables_on_right[MAX_TABLES]; // todo change to alloca + table_map used_tables_on_left; + TABLE_LIST *tbl; + int i, n_tables; + int eliminated=0; + + /* Collect the reverse-bitmap-array */ + for (i=0; (tbl= it++); i++) + { + used_tables_on_right[i]= 0; + if (tbl->on_expr) + used_tables_on_right[i]= tbl->on_expr->used_tables(); + if (tbl->nested_join) + used_tables_on_right[i]= tbl->nested_join->used_tables; + } + n_tables= i; + + for (i= n_tables - 2; i > 0; i--) + used_tables_on_right[i] |= used_tables_on_right[i+1]; + + it.rewind(); + + /* Walk through tables and join nests and see if we can eliminate them */ + used_tables_on_left= 0; + i= 1; + while ((tbl= it++)) + { + table_map tables_used_outside= used_tables_on_left | + used_tables_on_right[i] | + used_tables_elsewhere; + table_map cur_tables; + + if (tbl->nested_join) + { + DBUG_ASSERT(tbl->on_expr); + /* + There can be cases where table removal is applicable for tables + within the outer join but not for the outer join itself. Ask to + remove the children first. + + TODO: NoHopelessEliminationAttempts: the below call can return + information about whether it would make any sense to try removing + this entire outer join nest. + */ + int eliminated_in_children= + eliminate_tables_for_join_list(join, &tbl->nested_join->join_list, + tables_used_outside, + const_tbl_count, const_tables); + tbl->nested_join->n_tables -=eliminated_in_children; + cur_tables= tbl->nested_join->used_tables; + if (!(cur_tables & tables_used_outside)) + { + /* + Check if all embedded tables together can produce at most one + record combination. This is true when + - each of them has one_match(outer-tables) property + (this is a stronger condition than all of them together having + this property but that's irrelevant here) + - there are no outer joins among them + (except for the case of outer join which has all inner tables + to be constant and is guaranteed to produce only one record. + that record will be null-complemented) + */ + bool one_match= TRUE; + List_iterator<TABLE_LIST> it2(tbl->nested_join->join_list); + TABLE_LIST *inner; + while ((inner= it2++)) + { + /* + Bail out if we see an outer join (TODO: handle the above + null-complemntated-rows-only case) + */ + if (inner->on_expr) + { + one_match= FALSE; + break; + } + + if (inner->table && // <-- to be removed after NoHopelessEliminationAttempts + !has_eq_ref_access_candidate(inner->table, + ~tbl->nested_join->used_tables)) + { + one_match= FALSE; + break; + } + } + if (one_match) + { + it2.rewind(); + while ((inner= it2++)) + { + mark_table_as_eliminated(join, inner->table, const_tbl_count, + const_tables); + } + eliminated += tbl->nested_join->join_list.elements; + //psergey-todo: do we need to do anything about removing the join + //nest? + } + else + { + eliminated += eliminated_in_children; + } + } + } + else if (tbl->on_expr) + { + cur_tables= tbl->on_expr->used_tables(); + /* Check and remove */ + if (!(tbl->table->map & tables_used_outside) && + has_eq_ref_access_candidate(tbl->table, (table_map)-1)) + { + mark_table_as_eliminated(join, tbl->table, const_tbl_count, + const_tables); + eliminated += 1; + } + } + + /* Update bitmap of tables we've seen on the left */ + i++; + used_tables_on_left |= cur_tables; + } + return eliminated; +} + + +/* + Perform table elimination based on outer join + + SELECT * FROM t1 LEFT JOIN + (t2 JOIN t3) ON t3.primary_key=t1.col AND + t4.primary_key= t2.col + + CRITERIA FOR REMOVING ONE OJ NEST + we can't rely on sole presense of eq_refs. Because if we do, we'll miss + things like this: + + SELECT * FROM flights LEFT JOIN + (pax as S1 JOIN pax as S2 ON S2.id=S1.spouse AND s1.id=s2.spouse) + + (no-polygamy schema/query but there can be many couples on the flight) + .. + + REMOVAL PROCESS + We can remove an inner side of an outer join if it there is a warranty + that it will produce not more than one record: + + ... t1 LEFT JOIN t2 ON (t2.unique_key = expr) ... + + For nested outer joins: + - The process naturally occurs bottom-up (in order to remove an + outer-join we need to analyze its contents) + - If we failed to remove an outer join nest, it makes no sense to + try removing its ancestors, as the + ot LEFT JOIN it ON cond + pair may possibly produce two records (one record via match and + another one as access-method record). + + Q: If we haven't removed an OUTER JOIN, does it make sense to attempt + removing its ancestors? + A: No as the innermost outer join will produce two records => no ancestor + outer join nest will be able to provide the max_fanout==1 guarantee. + + psergey-todo: . +*/ + +static void eliminate_tables(JOIN *join, uint *const_tbl_count, table_map *const_tables) +{ + Item *item; + table_map used_tables; + DBUG_ENTER("eliminate_tables"); + if (!join->outer_join) + DBUG_VOID_RETURN; + + /* Find the tables that are referred to from WHERE/HAVING */ + used_tables= (join->conds? join->conds->used_tables() : 0) | + (join->having? join->having->used_tables() : 0); + + /* Add tables referred to from the select list */ + List_iterator<Item> it(join->fields_list); + while ((item= it++)) + used_tables |= item->used_tables(); + + /* Add tables referred to from ORDER BY and GROUP BY lists */ + ORDER *all_lists[]= { join->order, join->group_list}; + for (int i=0; i < 2; i++) + { + for (ORDER *cur_list= all_lists[i]; cur_list; cur_list= cur_list->next) + used_tables |= (*(cur_list->item))->used_tables(); + } + + THD* thd= join->thd; + if (join->select_lex == &thd->lex->select_lex) + { + /* Multi-table UPDATE and DELETE: don't eliminate the tables we modify: */ + used_tables |= thd->table_map_for_update; + + /* Multi-table UPDATE: don't eliminate tables referred from SET statement */ + if (thd->lex->sql_command == SQLCOM_UPDATE_MULTI) + { + List_iterator<Item> it2(thd->lex->value_list); + while ((item= it2++)) + used_tables |= item->used_tables(); + } + } + + if (((1 << join->tables) - 1) & ~used_tables) + { + /* There are some time tables that we probably could eliminate */ + eliminate_tables_for_join_list(join, join->join_list, used_tables, + const_tbl_count, const_tables); + } + DBUG_VOID_RETURN; +} + + /* This structure is used to collect info on potentially sargable predicates in order to check whether they become sargable after @@ -2823,6 +3126,10 @@ make_join_statistics(JOIN *join, TABLE_L } } + //psergey-todo: table elimination + eliminate_tables(join, &const_count, &found_const_table_map); + //:psergey-todo + /* Calc how many (possible) matched records in each table */ for (s=stat ; s < stat_end ; s++) @@ -2956,9 +3263,6 @@ typedef struct key_field_t { bool *cond_guard; /* See KEYUSE::cond_guard */ } KEY_FIELD; -/* Values in optimize */ -#define KEY_OPTIMIZE_EXISTS 1 -#define KEY_OPTIMIZE_REF_OR_NULL 2 /** Merge new key definitions to old ones, remove those not used in both. @@ -3563,7 +3867,6 @@ add_key_part(DYNAMIC_ARRAY *keyuse_array } -#define FT_KEYPART (MAX_REF_PARTS+10) static void add_ft_keys(DYNAMIC_ARRAY *keyuse_array, @@ -6021,7 +6324,7 @@ make_outerjoin_info(JOIN *join) } if (!tab->first_inner) tab->first_inner= nested_join->first_nested; - if (++nested_join->counter < nested_join->join_list.elements) + if (++nested_join->counter < nested_join->n_tables) break; /* Table tab is the last inner table for nested join. */ nested_join->first_nested->last_inner= tab; @@ -8575,6 +8878,8 @@ simplify_joins(JOIN *join, List<TABLE_LI 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 +9038,7 @@ static uint build_bitmap_for_nested_join with anything) 2. we could run out bits in nested_join_map otherwise. */ - if (nested_join->join_list.elements != 1) + if (nested_join->n_tables != 1) { nested_join->nj_map= (nested_join_map) 1 << first_unused++; first_unused= build_bitmap_for_nested_joins(&nested_join->join_list, @@ -8894,7 +9199,7 @@ static bool check_interleaving_with_nj(J join->cur_embedding_map |= next_emb->nested_join->nj_map; } - if (next_emb->nested_join->join_list.elements != + if (next_emb->nested_join->n_tables != next_emb->nested_join->counter) break; @@ -8928,7 +9233,7 @@ static void restore_prev_nj_state(JOIN_T { if (!(--last_emb->nested_join->counter)) join->cur_embedding_map&= ~last_emb->nested_join->nj_map; - else if (last_emb->nested_join->join_list.elements-1 == + else if (last_emb->nested_join->n_tables-1 == last_emb->nested_join->counter) join->cur_embedding_map|= last_emb->nested_join->nj_map; else @@ -16202,6 +16507,14 @@ static void select_describe(JOIN *join, tmp3.length(0); quick_type= -1; + + //psergey-todo: + if (tab->eliminated) + { + used_tables|=table->map; + continue; + } + item_list.empty(); /* id */ item_list.push_back(new Item_uint((uint32) === modified file 'sql/sql_select.h' --- a/sql/sql_select.h 2009-04-25 10:05:32 +0000 +++ b/sql/sql_select.h 2009-06-03 13:10:45 +0000 @@ -210,6 +210,9 @@ typedef struct st_join_table { JOIN *join; /** Bitmap of nested joins this table is part of */ nested_join_map embedding_map; + + //psergey-todo: more justified place + bool eliminated; void cleanup(); inline bool is_using_loose_index_scan() === modified file 'sql/table.h' --- a/sql/table.h 2009-02-19 09:01:25 +0000 +++ b/sql/table.h 2009-06-03 13:10:45 +0000 @@ -1626,6 +1626,8 @@ typedef struct st_nested_join Before each use the counters are zeroed by reset_nj_counters. */ uint counter; + /* Tables left after elimination */ + uint n_tables; nested_join_map nj_map; /* Bit used to identify this nested join*/ } NESTED_JOIN;

1 0