- developers - lists.mariadb.org

[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (monty:2825)
by Michael Widenius 26 Mar '10

26 Mar '10

#At lp:maria based on revid:sergii@pisem.net-20100308170509-gsqfnt3a9rdaxj32 2825 Michael Widenius 2010-03-09 Added count of my_sync calls (to SHOW STATUS) tmp_table_size can now be set to 0 (to disable in memory internal temp tables) Improved speed for internal Maria temp tables: - Don't use packed keys, except with long text fields. - Don't copy key all accessed pages during key search. Some new benchmark tests to sql-bench (for group by) modified: BUILD/compile-pentium64-gcov BUILD/compile-pentium64-gprof include/my_sys.h mysql-test/r/variables.result mysys/my_sync.c sql-bench/test-select.sh sql/mysqld.cc sql/sql_select.cc storage/maria/ma_key_recover.h storage/maria/ma_page.c storage/maria/ma_rkey.c storage/maria/ma_search.c storage/maria/ma_write.c storage/maria/maria_def.h per-file messages: BUILD/compile-pentium64-gcov Update script to use same pentium_config flags as other tests BUILD/compile-pentium64-gprof Update script to use same pentium_config flags as other tests include/my_sys.h Added count of my_sync calls mysql-test/r/variables.result tmp_table_size can now be set to 0 sql-bench/test-select.sh Added some new test for GROUP BY on a not key field and group by with different order by sql/mysqld.cc Added count of my_sync calls tmp_table_size can now be set to 0 (to disable in memory internal temp tables) sql/sql_select.cc If tmp_table_size is 0, don't use in memory temp tables (good for benchmarking MyISAM/Maria temp tables) Don't pack keys for Maria tables; The 8K page size makes packed keys too slow for temp tables. storage/maria/ma_key_recover.h Moved definition to maria_def.h storage/maria/ma_page.c Moved code used to simplify comparing of identical Maria tables to own function (page_cleanup()) Fixed that one can read a page with a read lock. storage/maria/ma_rkey.c For not exact key reads, cache the page where we found key (to speed up future read-next/read-prev calls) storage/maria/ma_search.c Moved code to cache last key page to separate function. Instead of copying pages, only get a link to the page. This notable speeds up key searches on bigger tables. storage/maria/ma_write.c Added comment storage/maria/maria_def.h Moved page_cleanup() to separate function. === modified file 'BUILD/compile-pentium64-gcov' --- a/BUILD/compile-pentium64-gcov 2007-08-16 00:10:16 +0000 +++ b/BUILD/compile-pentium64-gcov 2010-03-09 19:22:24 +0000 @@ -9,9 +9,9 @@ export CCACHE_DISABLE export LDFLAGS="$gcov_link_flags" -extra_flags="$pentium64_cflags $debug_cflags $max_cflags $gcov_compile_flags" +extra_flags="$pentium64_cflags $max_cflags $gcov_compile_flags" c_warnings="$c_warnings $debug_extra_warnings" cxx_warnings="$cxx_warnings $debug_extra_warnings" -extra_configs="$pentium64_configs $debug_configs $gcov_configs $max_configs" +extra_configs="$pentium_configs $debug_configs $gcov_configs $max_configs --with-zlib-dir=bundled" . "$path/FINISH.sh" === modified file 'BUILD/compile-pentium64-gprof' --- a/BUILD/compile-pentium64-gprof 2007-08-16 00:10:16 +0000 +++ b/BUILD/compile-pentium64-gprof 2010-03-09 19:22:24 +0000 @@ -4,6 +4,6 @@ path=`dirname $0` . "$path/SETUP.sh" extra_flags="$pentium64_cflags $gprof_compile_flags" -extra_configs="$pentium64_configs $debug_configs $gprof_link_flags" +extra_configs="$pentium_configs $max_configs $gprof_link_flags --with-zlib-dir=bundled" . "$path/FINISH.sh" === modified file 'include/my_sys.h' --- a/include/my_sys.h 2009-12-03 11:19:05 +0000 +++ b/include/my_sys.h 2010-03-09 19:22:24 +0000 @@ -247,6 +247,7 @@ extern CHARSET_INFO compiled_charsets[]; /* statistics */ extern ulong my_file_opened,my_stream_opened, my_tmp_file_created; extern ulong my_file_total_opened; +extern ulong my_sync_count; extern uint mysys_usage_id; extern my_bool my_init_done; === modified file 'mysql-test/r/variables.result' --- a/mysql-test/r/variables.result 2010-02-10 19:06:24 +0000 +++ b/mysql-test/r/variables.result 2010-03-09 19:22:24 +0000 @@ -575,8 +575,6 @@ set storage_engine=myisam; set global thread_cache_size=100; set timestamp=1, timestamp=default; set tmp_table_size=100; -Warnings: -Warning 1292 Truncated incorrect tmp_table_size value: '100' set tx_isolation="READ-COMMITTED"; set wait_timeout=100; set log_warnings=1; === modified file 'mysys/my_sync.c' --- a/mysys/my_sync.c 2010-01-15 15:27:55 +0000 +++ b/mysys/my_sync.c 2010-03-09 19:22:24 +0000 @@ -17,6 +17,8 @@ #include "mysys_err.h" #include <errno.h> +ulong my_sync_count; /* Count number of sync calls */ + /* Sync data in file to disk @@ -46,6 +48,7 @@ int my_sync(File fd, myf my_flags) DBUG_ENTER("my_sync"); DBUG_PRINT("my",("fd: %d my_flags: %d", fd, my_flags)); + statistic_increment(my_sync_count,&THR_LOCK_open); do { #if defined(F_FULLFSYNC) === modified file 'sql-bench/test-select.sh' --- a/sql-bench/test-select.sh 2010-02-17 20:10:02 +0000 +++ b/sql-bench/test-select.sh 2010-03-09 19:22:24 +0000 @@ -68,7 +68,8 @@ do_many($dbh,$server->create("bench1", ["region char(1) NOT NULL", "idn integer(6) NOT NULL", "rev_idn integer(6) NOT NULL", - "grp integer(6) NOT NULL"], + "grp integer(6) NOT NULL", + "grp_no_key integer(6) NOT NULL"], ["primary key (region,idn)", "unique (region,rev_idn)", "unique (region,grp,idn)"])); @@ -105,10 +106,10 @@ for ($id=0,$rev_id=$opt_loop_count-1 ; $ { $grp=$id*3 % $opt_groups; $region=chr(65+$id%$opt_regions); - do_query($dbh,"$query'$region',$id,$rev_id,$grp)"); + do_query($dbh,"$query'$region',$id,$rev_id,$grp,$grp)"); if ($id == $half_done) { # Test with different insert - $query="insert into bench1 (region,idn,rev_idn,grp) values ("; + $query="insert into bench1 (region,idn,rev_idn,grp,grp_no_key) values ("; } } @@ -323,6 +324,26 @@ if ($limits->{'group_functions'}) $end_time=new Benchmark; print "Time for count_group_on_key_parts ($i:$rows): " . timestr(timediff($end_time, $loop_time),"all") . "\n"; + + $loop_time=new Benchmark; + $rows=0; + for ($i=0 ; $i < $opt_medium_loop_count ; $i++) + { + $rows+=fetch_all_rows($dbh,"select grp_no_key,count(*) from bench1 group by grp_no_key"); + } + $end_time=new Benchmark; + print "Time for count_group ($i:$rows): " . + timestr(timediff($end_time, $loop_time),"all") . "\n"; + + $loop_time=new Benchmark; + $rows=0; + for ($i=0 ; $i < $opt_medium_loop_count ; $i++) + { + $rows+=fetch_all_rows($dbh,"select grp_no_key,count(*) as cnt from bench1 group by grp_no_key order by cnt"); + } + $end_time=new Benchmark; + print "Time for count_group_with_order ($i:$rows): " . + timestr(timediff($end_time, $loop_time),"all") . "\n"; } if ($limits->{'group_distinct_functions'}) === modified file 'sql/mysqld.cc' --- a/sql/mysqld.cc 2010-02-11 19:15:24 +0000 +++ b/sql/mysqld.cc 2010-03-09 19:22:24 +0000 @@ -7273,10 +7273,10 @@ The minimum value for this variable is 4 0, GET_STR, REQUIRED_ARG, 0, 0, 0, 0, 0, 0}, {"tmp_table_size", OPT_TMP_TABLE_SIZE, "If an internal in-memory temporary table exceeds this size, MySQL will" - " automatically convert it to an on-disk MyISAM table.", + " automatically convert it to an on-disk MyISAM/Maria table.", (uchar**) &global_system_variables.tmp_table_size, (uchar**) &max_system_variables.tmp_table_size, 0, GET_ULL, - REQUIRED_ARG, 16*1024*1024L, 1024, MAX_MEM_TABLE_SIZE, 0, 1, 0}, + REQUIRED_ARG, 16*1024*1024L, 0, MAX_MEM_TABLE_SIZE, 0, 1, 0}, {"transaction_alloc_block_size", OPT_TRANS_ALLOC_BLOCK_SIZE, "Allocation block size for transactions to be stored in binary log", (uchar**) &global_system_variables.trans_alloc_block_size, @@ -7778,6 +7778,7 @@ SHOW_VAR status_vars[]= { {"Ssl_verify_mode", (char*) &show_ssl_get_verify_mode, SHOW_FUNC}, {"Ssl_version", (char*) &show_ssl_get_version, SHOW_FUNC}, #endif /* HAVE_OPENSSL */ + {"Syncs", (char*) &my_sync_count, SHOW_LONG_NOFLUSH}, {"Table_locks_immediate", (char*) &locks_immediate, SHOW_LONG}, {"Table_locks_waited", (char*) &locks_waited, SHOW_LONG}, #ifdef HAVE_MMAP === modified file 'sql/sql_select.cc' --- a/sql/sql_select.cc 2010-03-08 13:57:32 +0000 +++ b/sql/sql_select.cc 2010-03-09 19:22:24 +0000 @@ -10168,7 +10168,8 @@ create_tmp_table(THD *thd,TMP_TABLE_PARA /* future: storage engine selection can be made dynamic? */ if (blob_count || using_unique_constraint || (select_options & (OPTION_BIG_TABLES | SELECT_SMALL_RESULT)) == - OPTION_BIG_TABLES || (select_options & TMP_TABLE_FORCE_MYISAM)) + OPTION_BIG_TABLES || (select_options & TMP_TABLE_FORCE_MYISAM) || + !thd->variables.tmp_table_size) { share->db_plugin= ha_lock_engine(0, TMP_ENGINE_HTON); table->file= get_new_handler(share, &table->mem_root, @@ -10707,7 +10708,7 @@ static bool create_internal_tmp_table(TA { /* Create an unique key */ bzero((char*) &keydef,sizeof(keydef)); - keydef.flag=HA_NOSAME | HA_BINARY_PACK_KEY | HA_PACK_KEY; + keydef.flag=HA_NOSAME; keydef.keysegs= keyinfo->key_parts; keydef.seg= seg; } @@ -10732,7 +10733,7 @@ static bool create_internal_tmp_table(TA seg->type= keyinfo->key_part[i].type; /* Tell handler if it can do suffic space compression */ if (field->real_type() == MYSQL_TYPE_STRING && - keyinfo->key_part[i].length > 4) + keyinfo->key_part[i].length > 32) seg->flag|= HA_SPACE_PACK; } if (!(field->flags & NOT_NULL_FLAG)) === modified file 'storage/maria/ma_key_recover.h' --- a/storage/maria/ma_key_recover.h 2008-09-01 17:31:40 +0000 +++ b/storage/maria/ma_key_recover.h 2010-03-09 19:22:24 +0000 @@ -63,7 +63,6 @@ extern my_bool write_hook_for_undo_key_i extern my_bool write_hook_for_undo_key_delete(enum translog_record_type type, TRN *trn, MARIA_HA *tbl_info, LSN *lsn, void *hook_arg); -void _ma_unpin_all_pages(MARIA_HA *info, LSN undo_lsn); my_bool _ma_log_prefix(MARIA_PAGE *page, uint changed_length, int move_length); my_bool _ma_log_suffix(MARIA_PAGE *page, uint org_length, === modified file 'storage/maria/ma_page.c' --- a/storage/maria/ma_page.c 2009-05-06 12:03:24 +0000 +++ b/storage/maria/ma_page.c 2010-03-09 19:22:24 +0000 @@ -64,6 +64,15 @@ void _ma_page_setup(MARIA_PAGE *page, MA share->base.key_reflength : 0); } +#ifdef IDENTICAL_PAGES_AFTER_RECOVERY +void page_cleanup(MARIA_SHARE *share, MARIA_PAGE *page) +{ + uint length= page->size; + DBUG_ASSERT(length <= block_size - KEYPAGE_CHECKSUM_SIZE); + bzero(page->buff + length, share->block_size - length); +} +#endif + /** Fetch a key-page in memory @@ -102,8 +111,10 @@ my_bool _ma_fetch_keypage(MARIA_PAGE *pa if (lock != PAGECACHE_LOCK_LEFT_UNLOCKED) { - DBUG_ASSERT(lock == PAGECACHE_LOCK_WRITE); - page_link.unlock= PAGECACHE_LOCK_WRITE_UNLOCK; + DBUG_ASSERT(lock == PAGECACHE_LOCK_WRITE || PAGECACHE_LOCK_READ); + page_link.unlock= (lock == PAGECACHE_LOCK_WRITE ? + PAGECACHE_LOCK_WRITE_UNLOCK : + PAGECACHE_LOCK_READ_UNLOCK); page_link.changed= 0; push_dynamic(&info->pinned_pages, (void*) &page_link); page->link_offset= info->pinned_pages.elements-1; @@ -209,14 +220,7 @@ my_bool _ma_write_keypage(MARIA_PAGE *pa } #endif -#ifdef IDENTICAL_PAGES_AFTER_RECOVERY - { - uint length= page->size; - DBUG_ASSERT(length <= block_size - KEYPAGE_CHECKSUM_SIZE); - bzero(buff + length, block_size - length); - } -#endif - + page_cleanup(share, page); res= pagecache_write(share->pagecache, &share->kfile, (pgcache_page_no_t) (page->pos / block_size), === modified file 'storage/maria/ma_rkey.c' --- a/storage/maria/ma_rkey.c 2008-06-26 05:18:28 +0000 +++ b/storage/maria/ma_rkey.c 2010-03-09 19:22:24 +0000 @@ -82,6 +82,9 @@ int maria_rkey(MARIA_HA *info, uchar *bu rw_rdlock(&keyinfo->root_lock); nextflag= maria_read_vec[search_flag] | key.flag; + if (search_flag != HA_READ_KEY_EXACT || + ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME)) + nextflag|= SEARCH_SAVE_BUFF; switch (keyinfo->key_alg) { #ifdef HAVE_RTREE_KEYS === modified file 'storage/maria/ma_search.c' --- a/storage/maria/ma_search.c 2009-05-06 12:03:24 +0000 +++ b/storage/maria/ma_search.c 2010-03-09 19:22:24 +0000 @@ -18,6 +18,10 @@ #include "ma_fulltext.h" #include "m_ctype.h" +static int _ma_search_no_save(register MARIA_HA *info, MARIA_KEY *key, + uint32 nextflag, register my_off_t pos, + MARIA_PINNED_PAGE **res_page_link, + uchar **res_page_buff); static my_bool _ma_get_prev_key(MARIA_KEY *key, MARIA_PAGE *ma_page, uchar *keypos); @@ -57,7 +61,51 @@ int _ma_check_index(MARIA_HA *info, int */ int _ma_search(register MARIA_HA *info, MARIA_KEY *key, uint32 nextflag, - register my_off_t pos) + my_off_t pos) +{ + int error; + MARIA_PINNED_PAGE *page_link; + uchar *page_buff; + + info->page_changed= 1; /* If page not saved */ + if (!(error= _ma_search_no_save(info, key, nextflag, pos, &page_link, + &page_buff))) + { + if (nextflag & SEARCH_SAVE_BUFF) + { + bmove512(info->keyread_buff, page_buff, info->s->block_size); + + /* Save position for a possible read next / previous */ + info->int_keypos= info->keyread_buff + (ulonglong) info->int_keypos; + info->int_maxpos= info->keyread_buff + (ulonglong) info->int_maxpos; + info->int_keytree_version= key->keyinfo->version; + info->last_search_keypage= info->last_keypage; + info->page_changed= 0; + info->keyread_buff_used= 0; + } + } + _ma_unpin_all_pages(info, LSN_IMPOSSIBLE); + return (error); +} + +/** + @breif Search after row by a key + + ret_page_link Will contain pointer to page where we found key + + @note + Position to row is stored in info->lastpos + + @return + @retval 0 ok (key found) + @retval -1 Not found + @retval 1 If one should continue search on higher level +*/ + +static int _ma_search_no_save(register MARIA_HA *info, MARIA_KEY *key, + uint32 nextflag, register my_off_t pos, + MARIA_PINNED_PAGE **res_page_link, + uchar **res_page_buff) { my_bool last_key_not_used; int error,flag; @@ -66,6 +114,7 @@ int _ma_search(register MARIA_HA *info, uchar lastkey[MARIA_MAX_KEY_BUFF]; MARIA_KEYDEF *keyinfo= key->keyinfo; MARIA_PAGE page; + MARIA_PINNED_PAGE *page_link; DBUG_ENTER("_ma_search"); DBUG_PRINT("enter",("pos: %lu nextflag: %u lastpos: %lu", (ulong) pos, nextflag, (ulong) info->cur_row.lastpos)); @@ -81,10 +130,11 @@ int _ma_search(register MARIA_HA *info, } if (_ma_fetch_keypage(&page, info, keyinfo, pos, - PAGECACHE_LOCK_LEFT_UNLOCKED, - DFLT_INIT_HITS, info->keyread_buff, - test(!(nextflag & SEARCH_SAVE_BUFF)))) + PAGECACHE_LOCK_READ, DFLT_INIT_HITS, 0, 0)) goto err; + page_link= dynamic_element(&info->pinned_pages, + info->pinned_pages.elements-1, + MARIA_PINNED_PAGE*); DBUG_DUMP("page", page.buff, page.size); flag= (*keyinfo->bin_search)(key, &page, nextflag, &keypos, lastkey, @@ -98,8 +148,9 @@ int _ma_search(register MARIA_HA *info, if (flag) { - if ((error= _ma_search(info, key, nextflag, - _ma_kpos(nod_flag,keypos))) <= 0) + if ((error= _ma_search_no_save(info, key, nextflag, + _ma_kpos(nod_flag,keypos), + res_page_link, res_page_buff)) <= 0) DBUG_RETURN(error); if (flag >0) @@ -118,26 +169,15 @@ int _ma_search(register MARIA_HA *info, ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME || (key->flag & SEARCH_PART_KEY) || info->s->base.born_transactional)) { - if ((error= _ma_search(info, key, (nextflag | SEARCH_FIND) & - ~(SEARCH_BIGGER | SEARCH_SMALLER | SEARCH_LAST), - _ma_kpos(nod_flag,keypos))) >= 0 || + if ((error= _ma_search_no_save(info, key, (nextflag | SEARCH_FIND) & + ~(SEARCH_BIGGER | SEARCH_SMALLER | + SEARCH_LAST), + _ma_kpos(nod_flag,keypos), + res_page_link, res_page_buff)) >= 0 || my_errno != HA_ERR_KEY_NOT_FOUND) DBUG_RETURN(error); - info->last_keypage= HA_OFFSET_ERROR; /* Buffer not in mem */ } } - if (pos != info->last_keypage) - { - uchar *old_buff= page.buff; - if (_ma_fetch_keypage(&page, info, keyinfo, pos, - PAGECACHE_LOCK_LEFT_UNLOCKED,DFLT_INIT_HITS, - info->keyread_buff, - test(!(nextflag & SEARCH_SAVE_BUFF)))) - goto err; - /* Restore position if page buffer moved */ - keypos= page.buff + (keypos - old_buff); - maxpos= page.buff + (maxpos - old_buff); - } info->last_key.keyinfo= keyinfo; if ((nextflag & (SEARCH_SMALLER | SEARCH_LAST)) && flag != 0) @@ -172,16 +212,15 @@ int _ma_search(register MARIA_HA *info, } info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key); info->cur_row.trid= _ma_trid_from_key(&info->last_key); - /* Save position for a possible read next / previous */ - info->int_keypos= info->keyread_buff + (keypos - page.buff); - info->int_maxpos= info->keyread_buff + (maxpos - page.buff); - info->int_nod_flag=nod_flag; - info->int_keytree_version=keyinfo->version; - info->last_search_keypage=info->last_keypage; - info->page_changed=0; - /* Set marker that buffer was used (Marker for mi_search_next()) */ - info->keyread_buff_used= (info->keyread_buff != page.buff); + /* Store offset to key */ + info->int_keypos= (uchar*) (keypos - page.buff); + info->int_maxpos= (uchar*) (maxpos - page.buff); + info->int_nod_flag= nod_flag; + info->last_keypage= pos; + *res_page_link= page_link; + *res_page_buff= page.buff; + DBUG_PRINT("exit",("found key at %lu",(ulong) info->cur_row.lastpos)); DBUG_RETURN(0); @@ -190,7 +229,7 @@ err: info->cur_row.lastpos= HA_OFFSET_ERROR; info->page_changed=1; DBUG_RETURN (-1); -} /* _ma_search */ +} /* === modified file 'storage/maria/ma_write.c' --- a/storage/maria/ma_write.c 2009-02-19 09:01:25 +0000 +++ b/storage/maria/ma_write.c 2010-03-09 19:22:24 +0000 @@ -587,6 +587,12 @@ my_bool _ma_enlarge_root(MARIA_HA *info, /* Search after a position for a key and store it there + TODO: + Change this to use pagecache directly instead of creating a copy + of the page. To do this, we must however change write-key-on-page + algorithm to not overwrite the buffer but instead store any overflow + key in a separate buffer. + @return @retval -1 error @retval 0 ok === modified file 'storage/maria/maria_def.h' --- a/storage/maria/maria_def.h 2010-02-10 19:06:24 +0000 +++ b/storage/maria/maria_def.h 2010-03-09 19:22:24 +0000 @@ -979,6 +979,11 @@ extern ulonglong transid_get_packed(MARI #define page_store_info(share, page) \ _ma_store_keypage_flag((share), (page)->buff, (page)->flag); \ _ma_store_page_used((share), (page)->buff, (page)->size); +#ifdef IDENTICAL_PAGES_AFTER_RECOVERY +void page_cleanup(MARIA_SHARE *share, MARIA_PAGE *page) +#else +#define page_cleanup(A,B) while (0) +#endif extern MARIA_KEY *_ma_make_key(MARIA_HA *info, MARIA_KEY *int_key, uint keynr, uchar *key, const uchar *record, @@ -1197,7 +1202,7 @@ void _ma_tmp_disable_logging_for_table(M my_bool log_incomplete); my_bool _ma_reenable_logging_for_table(MARIA_HA *info, my_bool flush_pages); my_bool write_log_record_for_bulk_insert(MARIA_HA *info); - +void _ma_unpin_all_pages(MARIA_HA *info, LSN undo_lsn); #define MARIA_NO_CRC_NORMAL_PAGE 0xffffffff #define MARIA_NO_CRC_BITMAP_PAGE 0xfffffffe

2 2

Re: [Maria-developers] [Bug 544173] [NEW] Server crash for multi-engine transaction with binlog disabled
by Arjen Lentz 25 Mar '10

25 Mar '10

Hi Kristian On 22/03/2010, at 11:44 PM, Kristian Nielsen wrote: > Public bug reported: > If using both PBXT and XtraDB in the same transaction, and log_bin is > disabled, the server crashes: > [...] > Note, the crash only happens when log_bin is disabled. As a sideline of this, we need a test that verifies that the two-phase commit process actually works. This could be done by starting a transaction, doing some write in both XtraDB and PBXT, but set things up in such a way that a commit will fail on one - perhaps Paul can provide a good idea for this - then the testcase can simply check the values in the XtraDB and PBXT tables afterwards to assess what happened. This test is as important as the above crash, because multi-engine transactions are something people will be using and thus relying on correctly working, however the code inside MySQL core that handles it is wholly untested. The test is of course also important to guard against regressions when other bugs around this code get found & fixed over time. Thanks Regards, Arjen. -- Arjen Lentz, Exec.Director @ Open Query (http://openquery.com) Exceptional Services for MySQL at a fixed budget. Follow our blog at http://openquery.com/blog/ OurDelta: packages for MySQL and MariaDB @ http://ourdelta.org

4 3

Re: [Maria-developers] [Bug 544173] [NEW] Server crash for multi-engine transaction with binlog disabled
by Kristian Nielsen 25 Mar '10

25 Mar '10

Paul McCullagh <paul.mccullagh(a)primebase.com> writes: > On Mar 25, 2010, at 8:39 AM, Kristian Nielsen wrote: >> Yes. This is simple enough to do with DBUG. Just insert code that >> makes each >> engine fail in their prepare() when the appropriate DBUG flag is set. >> >> Another test we need is to have similar code to crash the server at >> the same >> points. Then on server restart check that the other engine does >> rollback. > > It would be great to have these tests. As Arjen says, this code is not > well traveled. An example for how to do this (from a random dive into the source tree) is in mysql-test/suite/maria/t/maria-recovery.test, which uses mysql-test/include/maria_verify_recovery.inc to crash the server at specific point and verify that crash recovery works. It shouldn't be hard to do something similar for this case (also with just commit fail instead of crash). Hopefully this could be useful if someone wants to implement such test. >> (For example current code has no protection against another >> thransaction >> seeing a transient state with one engine committed and another not, >> even using >> START TRANSACTION WITH CONSISTENT SNAPSHOT. And there are >> fundamentally >> unsolvable problems with transactions that span both MVCC- and lock- >> based >> engines). > > I would be interested in an actual example of something does not work. > Right now I have a problem imagining why something would not work. I just happened to run the following test two days ago: Consider the following tables create table t1 (a int primary key) engine=innodb create table t2 (b int primary key) engine=pbxt insert into t1 values (1) insert into t2 values (1) I run the following statement repeatedly in one thread: UPDATE t1,t2 SET a=a+1,b=b+1 It would be natural to assume that other threads will never be able to see different values for a and b in a single transaction, but that assumption would be wrong. I run the following statement repeatedly in a different thread: SELECT a,b FROM t1,t2 After just a few iterations, this will return a row with a=b+1. (The reason I did this test was that I was looking at the XA multi-engine code, and not seeing any code to enforce cross-engine consistency. I guess this test shows there just is no such code ...) I didn't report it as a bug, as I was not sure if it is a bug or not ... maybe it is? I'd want a better fix than just taking a global lock over every commit (which could hurt performance a lot), and such fix may be non-trivial... Here are the Perl long-liners I used to see this, just run them in parallel to see the failure: perl -MDBI -le 'use strict; my $dbh=DBI->connect("dbi:mysql:database=test", "<user>", "<password>", {RaiseError => 1}); $dbh->do("SET binlog_format=row"); $dbh->do($_) for ("drop table if exists t1,t2", "create table t1 (a int primary key) engine=innodb", "create table t2 (b int primary key) engine=pbxt", "begin", "insert into t1 values (1)", "insert into t2 values (1)", "commit"); for (;;) { $dbh->do("UPDATE t1,t2 SET a=a+1,b=b+1");}' perl -MDBI -le 'use strict; my $dbh=DBI->connect("dbi:mysql:database=test", "<user>", "<password>", {RaiseError => 1}); $dbh->do("SET SESSION TRANSACTION ISOLATION LEVEL REPEATABLE READ"); for(;;) {my $a=$dbh->selectrow_arrayref("SELECT a,b FROM t1,t2"); print join(" ", @$a); die if $a->[0] != $a->[1];}' (CONSISTENT SNAPSHOT does not make a difference, as is seen by replacing the second command with this: perl -MDBI -le 'use strict; my $dbh=DBI->connect("dbi:mysql:database=test", "<user>", "<password>", {RaiseError => 1}); $dbh->do("SET SESSION TRANSACTION ISOLATION LEVEL REPEATABLE READ"); for(;;) {$dbh->do("START TRANSACTION WITH CONSISTENT SNAPSHOT");my $a=$dbh->selectrow_arrayref("SELECT a,b FROM t1,t2"); print join(" ", @$a); die if $a->[0] != $a->[1];$dbh->do("COMMIT");}' ) With respect to the fundamental problems with combining MVCC and locking engines; I know I reported a documentation bug for this long ago, though google failed to find it for me. And I'm not sure how to repeat it now, as I don't have any non-mvcc engines easily available (MariaDB has no NDB, and BDB is gone also). But it goes something like this: In a locking engine, a transaction sees the (consistent) state of the database as it is at the *end* of the transactions. So the transaction can see all other transactions that committed before it did. In an mvcc engine, a transaction sees the (consistent) state of the database as it is at the *start* of the transaction. So it sees no transactions that started after it did. So to get an inconsistency, something like this should work: TRN1: SET TRANSACTION ISOLATION LEVEL REPEATABLE READ; TRN1: BEGIN; TRN1: SELECT * FROM mvcc_table; TRN2: BEGIN; TRN2: UPDATE mvcc_table SET amount - amount - 100; TRN2: UPDATE locking_table SET amount = amount + 100; TRN2: COMMIT; TRN1: SELECT * from locking_table; TRN1: COMMIT; In such a case, TRN1 will see the update of the locking_table, but not the update of the mvcc_table, which gives an inconsistent view of the database. I don't really see any way to solve this. (Of course one could add LOCK IN SHARE MODE to every select, in effect turning the mvcc engine into a locking engine). - Kristian.

2 1

Re: [Maria-developers] MariaDB Release Numbering
by Kristian Nielsen 25 Mar '10

25 Mar '10

Colin Charles <colin(a)askmonty.org> writes: > On 25 Mar 2010, at 02:09, Daniel Bartholomew wrote: > >> If so, my thinking is that the first 5.2 release will be called >> "5.2.1" >> and then go up from there. > > > This is the only logical way forward > > We can then say "5.2.1 branched from MySQL 5.x" (for example) > > We've got to be clear where we've pulled things from, because some > things might be fixed in later versions of MySQL. Also in case there > are changes (i.e. that may affect folk upgrading), its really > important to know where things are branched from > > Its also good that we "deviate" from their numbering. Putting on a > marketing hat, it does sound like we're doing well with a greater > version number (ok, I don't necessarily believe this, but I was semi- > convinced when I heard the explanation given to me by the marketing > folk at MySQL - it helps CIOs think, maybe) I don't want a marketing hat :) But from a technical point of view I just want to make it clear that there is no difference in this respect between MariaDB 5.1 and MariaDB 5.2. The only meaningful difference between 5.1 and 5.2 is that at some point we stopped adding features to 5.1 to make a stable release, and thus all additions that are not bugfixes are now called 5.2. But in terms of numbering from 1,2,3 or from corresponding MySQL versions, there is no difference. Any argument for one or the other numbering applies equally to both 5.1 and 5.2. The merging from MySQL is identical. So the consistent way would be to release 5.2.44, 5.2.45, ... (On the other hand there may be other reasons to prefer 5.2.1, 5.2.2, fine with me. We can't go back to MariaDB 5.1.1, but for MariaDB 5.2 we can choose). - Kristian.

2 3

[Maria-developers] bzr commit into Mariadb 5.2, with Maria 2.0:maria/5.2 branch (monty:2751)
by Michael Widenius 25 Mar '10

25 Mar '10

#At lp:maria/5.2 based on revid:sergii@pisem.net-20100323092233-t2gwaclx94hd6exa 2751 Michael Widenius 2010-03-25 simple speed & space optimization: - Avoid full inline of mark_trx_read_write() for many functions - Avoid somewhat expensive tests for every write/update/delete row modified: sql/handler.cc sql/handler.h sql/sql_base.cc per-file messages: sql/handler.h Adde ha_start_of_new_statement() to reset internal variables as part of the code in "open_table" that resets TABLE object for the new statement Faster mark_trx_read_write_part() sql/sql_base.cc Don't manipulate table->file internal structs directly === modified file 'sql/handler.cc' --- a/sql/handler.cc 2010-03-15 11:51:23 +0000 +++ b/sql/handler.cc 2010-03-25 13:33:39 +0000 @@ -3110,11 +3110,14 @@ int handler::ha_check(THD *thd, HA_CHECK if it is started. */ -inline void -handler::mark_trx_read_write() +handler::mark_trx_read_write_part2() { Ha_trx_info *ha_info= &ha_thd()->ha_data[ht->slot].ha_info[0]; + + /* Don't call this function again for this statement */ + mark_trx_done= TRUE; + /* When a storage engine method is called, the transaction must have been started, unless it's a DDL call, for which the === modified file 'sql/handler.h' --- a/sql/handler.h 2010-02-01 06:14:12 +0000 +++ b/sql/handler.h 2010-03-25 13:33:39 +0000 @@ -1134,6 +1134,7 @@ public: enum {NONE=0, INDEX, RND} inited; bool locked; bool implicit_emptied; /* Can be !=0 only if HEAP */ + bool mark_trx_done; const COND *pushed_cond; /** next_insert_id is the next value which should be inserted into the @@ -1177,7 +1178,7 @@ public: ref(0), key_used_on_scan(MAX_KEY), active_index(MAX_KEY), ref_length(sizeof(my_off_t)), ft_handler(0), inited(NONE), - locked(FALSE), implicit_emptied(0), + locked(FALSE), implicit_emptied(FALSE), mark_trx_done(FALSE), pushed_cond(0), next_insert_id(0), insert_id_for_cur_row(0), auto_inc_intervals_count(0) { @@ -1232,6 +1233,13 @@ public: DBUG_RETURN(rnd_end()); } int ha_reset(); + /* Tell handler (not storage engine) this is start of a new statement */ + void ha_start_of_new_statement() + { + ft_handler= 0; + mark_trx_done= FALSE; + } + /* this is necessary in many places, e.g. in HANDLER command */ int ha_index_or_rnd_end() { @@ -1943,8 +1951,13 @@ protected: private: /* Private helpers */ - inline void mark_trx_read_write(); -private: + void mark_trx_read_write_part2(); + inline void mark_trx_read_write() + { + if (!mark_trx_done) + mark_trx_read_write_part2(); + } + /* Low-level primitives for storage engines. These should be overridden by the storage engine class. To call these methods, use === modified file 'sql/sql_base.cc' --- a/sql/sql_base.cc 2010-03-15 11:51:23 +0000 +++ b/sql/sql_base.cc 2010-03-25 13:33:39 +0000 @@ -2996,7 +2996,7 @@ TABLE *open_table(THD *thd, TABLE_LIST * table->status=STATUS_NO_RECORD; table->insert_values= 0; table->fulltext_searched= 0; - table->file->ft_handler= 0; + table->file->ha_start_of_new_statement(); table->reginfo.impossible_range= 0; /* Catch wrong handling of the auto_increment_field_not_null. */ DBUG_ASSERT(!table->auto_increment_field_not_null);

1 0

[Maria-developers] Rev 28: Added note about noop IO scheduler for Linux. Refactor variable name. in file:///Users/hakan/work/monty_program/mariadb-tools/
by Hakan Kuecuekyilmaz 25 Mar '10

25 Mar '10

At file:///Users/hakan/work/monty_program/mariadb-tools/ ------------------------------------------------------------ revno: 28 revision-id: hakan(a)askmonty.org-20100325014205-kwsruwixwlymz1ti parent: hakan(a)askmonty.org-20100310010046-hwv56n4wfn4t4odp committer: Hakan Kuecuekyilmaz <hakan(a)askmonty.org> branch nick: mariadb-tools timestamp: Thu 2010-03-25 02:42:05 +0100 message: Added note about noop IO scheduler for Linux. Refactor variable name. For MyISAM related tests added key_cache statistics dump out. === modified file 'sysbench/run-sysbench-myisam.sh' --- a/sysbench/run-sysbench-myisam.sh 2010-03-10 01:00:46 +0000 +++ b/sysbench/run-sysbench-myisam.sh 2010-03-25 01:42:05 +0000 @@ -6,16 +6,20 @@ # * Do not run this script with root privileges. We use # killall -9, which can cause severe side effects! # * By bzr pull we mean bzr merge --pull +# * For reasonable performance set your IO scheduler to noop or deadline, for +# reference please check +# http://www.mysqlperformanceblog.com/2009/01/30/linux-schedulers-in-tpcc-lik… # # Index sizes for 20 mio rows (--table-size=20000000). -# * delete.lua: 313M sbtest.MYI -# * insert.lua: 4.0K sbtest.MYI -# * oltp_complex_ro.lua: 313M sbtest.MYI -# * oltp_complex_rw.lua: 313M sbtest.MYI -# * oltp_simple.lua: 325M sbtest.MYI -# * select.lua: 313M sbtest.MYI -# * update_index.lua: 313M sbtest.MYI -# * update_non_index.lua: 313M sbtest.MYI +# * delete.lua 313M sbtest.MYI +# * insert.lua 4.0K sbtest.MYI +# * oltp_complex_ro.lua 313M sbtest.MYI +# * oltp_complex_rw.lua 313M sbtest.MYI +# * oltp_simple.lua 325M sbtest.MYI +# * select.lua 313M sbtest.MYI +# * select_random_ranges.lua 313M sbtest.MYI +# * update_index.lua 313M sbtest.MYI +# * update_non_index.lua 313M sbtest.MYI # # Hakan Kuecuekyilmaz <hakan at askmonty dot org> 2010-02-19. # @@ -60,13 +64,14 @@ # change these, except you exactly know what you are doing. # MYSQLADMIN='client/mysqladmin' +MYSQL='client/mysql' # # Variables. # MY_SOCKET="/tmp/mysql.sock" MYSQLADMIN_OPTIONS="--no-defaults -uroot --socket=$MY_SOCKET" -MYSQL_OPTIONS="--no-defaults \ +MYSQLD_OPTIONS="--no-defaults \ --datadir=$DATA_DIR \ --language=./sql/share/english \ --key_buffer_size=32M \ @@ -104,6 +109,7 @@ oltp_complex_rw.lua \ oltp_simple.lua \ select.lua \ + select_random_ranges.lua \ update_index.lua \ update_non_index.lua" @@ -240,7 +246,7 @@ } function start_mysqld { - sql/mysqld $MYSQL_OPTIONS & + sql/mysqld $MYSQLD_OPTIONS & j=0 STARTED=-1 @@ -269,7 +275,7 @@ # # Write out configurations used for future refernce. # -echo $MYSQL_OPTIONS > ${RESULT_DIR}/${TODAY}/${PRODUCT}/mysqld_options.txt +echo $MYSQLD_OPTIONS > ${RESULT_DIR}/${TODAY}/${PRODUCT}/mysqld_options.txt echo $SYSBENCH_OPTIONS > ${RESULT_DIR}/${TODAY}/${PRODUCT}/sysbench_options.txt echo '' >> ${RESULT_DIR}/${TODAY}/${PRODUCT}/sysbench_options.txt echo "Warm up time is: $WARM_UP_TIME" >> ${RESULT_DIR}/${TODAY}/${PRODUCT}/sysbench_options.txt @@ -331,6 +337,7 @@ echo "[$(date "+%Y-%m-%d %H:%M:%S")] Starting warm up of $WARM_UP_TIME seconds." $SYSBENCH $SYSBENCH_OPTIONS_WARM_UP run sync + echo 'FLUSH STATUS' | $MYSQL -uroot echo "[$(date "+%Y-%m-%d %H:%M:%S")] Finnished warm up." echo "[$(date "+%Y-%m-%d %H:%M:%S")] Starting actual sysbench run." @@ -338,6 +345,8 @@ grep "write requests:" ${THIS_RESULT_DIR}/result${k}.txt | awk '{ print $4 }' | sed -e 's/(//' >> ${THIS_RESULT_DIR}/results.txt + echo 'SELECT * FROM INFORMATION_SCHEMA.KEY_CACHES' | $MYSQL -uroot > ${THIS_RESULT_DIR}/key_cache_stats{k}.txt + k=$(($k + 1)) done === modified file 'sysbench/run-sysbench.sh' --- a/sysbench/run-sysbench.sh 2010-03-10 00:02:01 +0000 +++ b/sysbench/run-sysbench.sh 2010-03-25 01:42:05 +0000 @@ -6,6 +6,9 @@ # * Do not run this script with root privileges. We use # killall -9, which can cause severe side effects! # * By bzr pull we mean bzr merge --pull +# * For reasonable performance set your IO scheduler to noop or deadline, for +# reference please check +# http://www.mysqlperformanceblog.com/2009/01/30/linux-schedulers-in-tpcc-lik… # # Hakan Kuecuekyilmaz <hakan at askmonty dot org> 2010-02-19. # @@ -56,7 +59,7 @@ # MY_SOCKET="/tmp/mysql.sock" MYSQLADMIN_OPTIONS="--no-defaults -uroot --socket=$MY_SOCKET" -MYSQL_OPTIONS="--no-defaults \ +MYSQLD_OPTIONS="--no-defaults \ --datadir=$DATA_DIR \ --language=./sql/share/english \ --max_connections=256 \ @@ -236,7 +239,7 @@ } function start_mysqld { - sql/mysqld $MYSQL_OPTIONS & + sql/mysqld $MYSQLD_OPTIONS & j=0 STARTED=-1 @@ -265,7 +268,7 @@ # # Write out configurations used for future refernce. # -echo $MYSQL_OPTIONS > ${RESULT_DIR}/${TODAY}/${PRODUCT}/mysqld_options.txt +echo $MYSQLD_OPTIONS > ${RESULT_DIR}/${TODAY}/${PRODUCT}/mysqld_options.txt echo $SYSBENCH_OPTIONS > ${RESULT_DIR}/${TODAY}/${PRODUCT}/sysbench_options.txt echo '' >> ${RESULT_DIR}/${TODAY}/${PRODUCT}/sysbench_options.txt echo "Warm up time is: $WARM_UP_TIME" >> ${RESULT_DIR}/${TODAY}/${PRODUCT}/sysbench_options.txt

1 0

[Maria-developers] [Branch ~maria-captains/maria/5.1] Rev 2833: two crashes in the TC_LOG_MMAP:
by noreply＠launchpad.net 24 Mar '10

24 Mar '10

------------------------------------------------------------ revno: 2833 fixes bug(s): https://launchpad.net/bugs/544173 committer: Sergei Golubchik <sergii(a)pisem.net> branch nick: maria-5.1 timestamp: Wed 2010-03-24 23:12:39 +0100 message: two crashes in the TC_LOG_MMAP: 1. don't forget to initialize page->ptr 2. don't signal active->cond, if active is NULL added: mysql-test/suite/pbxt/r/pbxt_xa.result mysql-test/suite/pbxt/t/pbxt_xa.test modified: sql/log.cc -- 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] Updated (by Psergey): Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE (90)
by worklog-noreply＠askmonty.org 24 Mar '10

24 Mar '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE CREATION DATE..: Sun, 28 Feb 2010, 13:45 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-RawIdeaBin TASK ID........: 90 (http://askmonty.org/worklog/?tid=90) VERSION........: Server-5.3 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: -1 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Wed, 24 Mar 2010, 14:42)=-=- Low Level Design modified. --- /tmp/wklog.90.old.19182 2010-03-24 14:42:54.000000000 +0000 +++ /tmp/wklog.90.new.19182 2010-03-24 14:42:54.000000000 +0000 @@ -1 +1,140 @@ +<contents> +1. Applicability check +2. Representation +2.1 Option #1: Convert to TABLE_LIST +2.2 On subquery predicate removal +2.3 Option #2: No TABLE_LIST, convert to JOIN_TAB right away +2.3 What is expected of the result of conversion +3. Pre-optimization steps +3.1 Constant detection +3.3 update_ref_and_keys +3.4 JOIN_TAB sorting criteria +4. Optimization +5. Execution +User interface. +</contents> + +We'll call the new execution strategy "jtbm-materialization", for the lack of +better name. + +1. Applicability check +====================== +The criteria for checking whether a subquery can be processed with +jtbm-materialization can be checked at JOIN::prepare stage (like it +happens with semi-join check) + +2. Representation +================= + +2.1 Option #1: Convert to TABLE_LIST +------------------------------------ +Make it work like semi-join nests: each jtbm-predicate is converted into a +TABLE_LIST object. This will make it + + - uniform with semi-joins (we've stepped on all rakes there) + - allow to process JTBM-subqueries in ON expressions + +simplify_joins() will handle jtbm TABLE_LISTs as some kinds of opaque base +tables. + +for EXPLAIN EXTENDED, it would be natural to print something semi-join like, +i.e. for + + SELECT ... FROM ot WHERE oe IN (SELECT ie FROM materialized-non-sj-select) + +we'll print + + SELECT ... FROM ot SJ (SELECT ie FROM materialized-non-sj-select) ON oe=XX + +the XX part is not clear. we don't want to print 'ie' the second time here? + +2.2 On subquery predicate removal +--------------------------------- +Q: if we remove the subquery predicate permanently, who will run +fix_fields() for it? For semi-joins we don't have the problem as we +inject into ON expression (right? or not? we have sj_on_expr, too... +(Investigation: we the the same Item* pointer both in WHERE and +as sj_on_expr. fix_fields() is called for the WHERE part and that's +how sj_on_expr gets fixed. This works as long as +Item_func_eq::fix_fields() does not try to substitute itself with +another item). +A: ? + +2.3 Option #2: No TABLE_LIST, convert to JOIN_TAB right away +------------------------------------------------------------ +JOIN_TABs only live for the duration of one PS re-execution, so we'll have to +- make conversion fully undoable +- perform it sufficiently late in the optimization process, at the point + where JOIN_TABs are already allocated. + +Note that if we don't position JTBM predicates in join's TABLE_LIST tree, then +it will be impossible to handle JTBM queries inside/outside of outer joins. + +2.3 What is expected of the result of conversion +------------------------------------------------ +Join [pre]optimization relies on each optimized entity to have a bit in +table_map. + +TODO: where do we check if there will be enough bits for everyone? (at the + point where we assign them?) + +The bit stored in join_tab->table->map, and the apparent problem is that JTBM +join_tabs do not naturally have TABLE* object. + +We could use the the one that will be used for Materialization, but that will +stop working when we will have to include IN->EXISTS in the choice. + +Current approach: don't create a table. create a table_map element in JOIN_TAB +instead. Evgen has probably done something like that already. + +3. Pre-optimization steps +========================= +JOIN_TABs are allocated in make_join_statistics(). This where the changes will +be needed: for JOIN_TABs that correspond to JTBM-tables: + +- don't set tab->table, set tab->jtbm_select (or whatever) +- run subquery's optimizer to get its output cardinality + +3.1 Constant detection +---------------------- +What about subqueries that "are constant"? + const_item IN (SELECT uncorrelated) -> is constant, but not something + we would want to evaluate. + something IN (SELECT from_constant_join) -> is constant + +Do we need to mark their JOIN_TABs as constant? + +3.3 update_ref_and_keys +----------------------- +* Walk through JTBM elements and inject KEYUSE elements for their + IN-equalities. + +TODO: KEYUSE elements imply presense of KEYs! Which we don't have! + +3.4 JOIN_TAB sorting criteria +----------------------------- +Q: Where do we put JTBM's join_tab when pre-sorting records? +A: it should sort as regular table. + +TODO: where do we remove the predicates from the WHERE? + - remove them like SJ-converter does + - remove them with optimizer (like remove_eq_conds does) + +4. Optimization +=============== +Add a branch in best_access_path to account for +- JTBM-Materialization +- JTBM-Materialization-Scan. + +5. Execution +============ +* We should be able to reuse item_subselect.cc code for lookups +* But will have to use our own temptable scan code + +TODO: is it possible to have any unification with SJ-Materialization? + +User interface +-------------- +Any @@optimizer_switch flags for all this? + -=-=(Igor - Wed, 10 Mar 2010, 22:02)=-=- High Level Description modified. --- /tmp/wklog.90.old.2007 2010-03-10 22:02:23.000000000 +0000 +++ /tmp/wklog.90.new.2007 2010-03-10 22:02:23.000000000 +0000 @@ -13,8 +13,8 @@ for each record R2 in big_table such that oe=R1 pass R2 to output -Semi-join materialization supports such strategy with SJM-Scan strategy. This WL -entry is about adding support for such strategies for non-semijoin subqueries. +Semi-join materialization supports the inside-out strategy. This WL entry is +about adding support for such strategies for non-semijoin subqueries. Once WL#89 is done, there will be a cost-based choice between -=-=(Igor - Wed, 10 Mar 2010, 21:52)=-=- Status updated. --- /tmp/wklog.90.old.882 2010-03-10 21:52:02.000000000 +0000 +++ /tmp/wklog.90.new.882 2010-03-10 21:52:02.000000000 +0000 @@ -1 +1 @@ -Un-Assigned +Assigned -=-=(Psergey - Sun, 28 Feb 2010, 15:37)=-=- High Level Description modified. --- /tmp/wklog.90.old.23524 2010-02-28 15:37:47.000000000 +0000 +++ /tmp/wklog.90.new.23524 2010-02-28 15:37:47.000000000 +0000 @@ -15,3 +15,7 @@ Semi-join materialization supports such strategy with SJM-Scan strategy. This WL entry is about adding support for such strategies for non-semijoin subqueries. + + +Once WL#89 is done, there will be a cost-based choice between +Materialization+lookup, Materialization+scan, and IN->EXISTS+lookup strategies. -=-=(Psergey - Sun, 28 Feb 2010, 15:22)=-=- High-Level Specification modified. --- /tmp/wklog.90.old.23033 2010-02-28 15:22:09.000000000 +0000 +++ /tmp/wklog.90.new.23033 2010-02-28 15:22:09.000000000 +0000 @@ -1 +1,33 @@ +Basic idea on how this could be achieved: + +Pre-optimization phase +---------------------- + +The rewrite +~~~~~~~~~~~ +If we find a subquery predicate that is +- not processed by current semi-join optimizations +- is an AND-part of the WHERE/ON clause +- can be executed with Materialization + +then +- Remove the predicate from WHERE/ON clause +- Add a special JOIN_TAB object instead. + +Plan options +~~~~~~~~~~~~ +- Use the IN-equality to create KEYUSE elements. + +Optimization +------------ +- Pre-optimize the subquery so we know materialization cost +- Whenever best_access_path() encounters the "special JOIN_TAB" it should + consider two strategies: + A. Materialization and making lookups in the materialized table (if applicable) + B. Materialization and then scanning the materialized table. + + +EXPLAIN +------- +TODO how this will look in EXPLAIN output? -=-=(Psergey - Sun, 28 Feb 2010, 14:56)=-=- Dependency created: 91 now depends on 90 -=-=(Psergey - Sun, 28 Feb 2010, 14:54)=-=- Dependency deleted: 94 no longer depends on 90 -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- Title modified. --- /tmp/wklog.90.old.21903 2010-02-28 14:47:54.000000000 +0000 +++ /tmp/wklog.90.new.21903 2010-02-28 14:47:54.000000000 +0000 @@ -1 +1 @@ - Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE +Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- High Level Description modified. --- /tmp/wklog.90.old.21880 2010-02-28 14:47:28.000000000 +0000 +++ /tmp/wklog.90.new.21880 2010-02-28 14:47:28.000000000 +0000 @@ -1,10 +1,17 @@ -For uncorrelated IN subqueries that can't be converted to semi-joins it is -necessary to make a cost-based choice between IN->EXISTS and Materialization -strategies. +Consider the following case: -Both strategies handle two cases: -1. A simple case w/o NULLs handling -2. Handling NULLs. +SELECT * FROM big_table +WHERE oe IN (SELECT ie FROM table_with_few_groups + WHERE ... + GROUP BY group_col) AND ... -This WL is about making cost-based decision for #1. +Here the best way to execute the query is: + Materialize the subquery; + # now run the join: + for each record R1 in materialized table + for each record R2 in big_table such that oe=R1 + pass R2 to output + +Semi-join materialization supports such strategy with SJM-Scan strategy. This WL +entry is about adding support for such strategies for non-semijoin subqueries. -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- Title modified. --- /tmp/wklog.90.old.21859 2010-02-28 14:47:02.000000000 +0000 +++ /tmp/wklog.90.new.21859 2010-02-28 14:47:02.000000000 +0000 @@ -1 +1 @@ -Subqueries: cost-based choice between Materialization and IN->EXISTS transformation + Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE ------------------------------------------------------------ -=-=(View All Progress Notes, 11 total)=-=- http://askmonty.org/worklog/index.pl?tid=90&nolimit=1 DESCRIPTION: Consider the following case: SELECT * FROM big_table WHERE oe IN (SELECT ie FROM table_with_few_groups WHERE ... GROUP BY group_col) AND ... Here the best way to execute the query is: Materialize the subquery; # now run the join: for each record R1 in materialized table for each record R2 in big_table such that oe=R1 pass R2 to output Semi-join materialization supports the inside-out strategy. This WL entry is about adding support for such strategies for non-semijoin subqueries. Once WL#89 is done, there will be a cost-based choice between Materialization+lookup, Materialization+scan, and IN->EXISTS+lookup strategies. HIGH-LEVEL SPECIFICATION: Basic idea on how this could be achieved: Pre-optimization phase ---------------------- The rewrite ~~~~~~~~~~~ If we find a subquery predicate that is - not processed by current semi-join optimizations - is an AND-part of the WHERE/ON clause - can be executed with Materialization then - Remove the predicate from WHERE/ON clause - Add a special JOIN_TAB object instead. Plan options ~~~~~~~~~~~~ - Use the IN-equality to create KEYUSE elements. Optimization ------------ - Pre-optimize the subquery so we know materialization cost - Whenever best_access_path() encounters the "special JOIN_TAB" it should consider two strategies: A. Materialization and making lookups in the materialized table (if applicable) B. Materialization and then scanning the materialized table. EXPLAIN ------- TODO how this will look in EXPLAIN output? LOW-LEVEL DESIGN: <contents> 1. Applicability check 2. Representation 2.1 Option #1: Convert to TABLE_LIST 2.2 On subquery predicate removal 2.3 Option #2: No TABLE_LIST, convert to JOIN_TAB right away 2.3 What is expected of the result of conversion 3. Pre-optimization steps 3.1 Constant detection 3.3 update_ref_and_keys 3.4 JOIN_TAB sorting criteria 4. Optimization 5. Execution User interface. </contents> We'll call the new execution strategy "jtbm-materialization", for the lack of better name. 1. Applicability check ====================== The criteria for checking whether a subquery can be processed with jtbm-materialization can be checked at JOIN::prepare stage (like it happens with semi-join check) 2. Representation ================= 2.1 Option #1: Convert to TABLE_LIST ------------------------------------ Make it work like semi-join nests: each jtbm-predicate is converted into a TABLE_LIST object. This will make it - uniform with semi-joins (we've stepped on all rakes there) - allow to process JTBM-subqueries in ON expressions simplify_joins() will handle jtbm TABLE_LISTs as some kinds of opaque base tables. for EXPLAIN EXTENDED, it would be natural to print something semi-join like, i.e. for SELECT ... FROM ot WHERE oe IN (SELECT ie FROM materialized-non-sj-select) we'll print SELECT ... FROM ot SJ (SELECT ie FROM materialized-non-sj-select) ON oe=XX the XX part is not clear. we don't want to print 'ie' the second time here? 2.2 On subquery predicate removal --------------------------------- Q: if we remove the subquery predicate permanently, who will run fix_fields() for it? For semi-joins we don't have the problem as we inject into ON expression (right? or not? we have sj_on_expr, too... (Investigation: we the the same Item* pointer both in WHERE and as sj_on_expr. fix_fields() is called for the WHERE part and that's how sj_on_expr gets fixed. This works as long as Item_func_eq::fix_fields() does not try to substitute itself with another item). A: ? 2.3 Option #2: No TABLE_LIST, convert to JOIN_TAB right away ------------------------------------------------------------ JOIN_TABs only live for the duration of one PS re-execution, so we'll have to - make conversion fully undoable - perform it sufficiently late in the optimization process, at the point where JOIN_TABs are already allocated. Note that if we don't position JTBM predicates in join's TABLE_LIST tree, then it will be impossible to handle JTBM queries inside/outside of outer joins. 2.3 What is expected of the result of conversion ------------------------------------------------ Join [pre]optimization relies on each optimized entity to have a bit in table_map. TODO: where do we check if there will be enough bits for everyone? (at the point where we assign them?) The bit stored in join_tab->table->map, and the apparent problem is that JTBM join_tabs do not naturally have TABLE* object. We could use the the one that will be used for Materialization, but that will stop working when we will have to include IN->EXISTS in the choice. Current approach: don't create a table. create a table_map element in JOIN_TAB instead. Evgen has probably done something like that already. 3. Pre-optimization steps ========================= JOIN_TABs are allocated in make_join_statistics(). This where the changes will be needed: for JOIN_TABs that correspond to JTBM-tables: - don't set tab->table, set tab->jtbm_select (or whatever) - run subquery's optimizer to get its output cardinality 3.1 Constant detection ---------------------- What about subqueries that "are constant"? const_item IN (SELECT uncorrelated) -> is constant, but not something we would want to evaluate. something IN (SELECT from_constant_join) -> is constant Do we need to mark their JOIN_TABs as constant? 3.3 update_ref_and_keys ----------------------- * Walk through JTBM elements and inject KEYUSE elements for their IN-equalities. TODO: KEYUSE elements imply presense of KEYs! Which we don't have! 3.4 JOIN_TAB sorting criteria ----------------------------- Q: Where do we put JTBM's join_tab when pre-sorting records? A: it should sort as regular table. TODO: where do we remove the predicates from the WHERE? - remove them like SJ-converter does - remove them with optimizer (like remove_eq_conds does) 4. Optimization =============== Add a branch in best_access_path to account for - JTBM-Materialization - JTBM-Materialization-Scan. 5. Execution ============ * We should be able to reuse item_subselect.cc code for lookups * But will have to use our own temptable scan code TODO: is it possible to have any unification with SJ-Materialization? User interface -------------- Any @@optimizer_switch flags for all this? ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Psergey): Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE (90)
by worklog-noreply＠askmonty.org 24 Mar '10

24 Mar '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE CREATION DATE..: Sun, 28 Feb 2010, 13:45 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-RawIdeaBin TASK ID........: 90 (http://askmonty.org/worklog/?tid=90) VERSION........: Server-5.3 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: -1 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Wed, 24 Mar 2010, 14:42)=-=- Low Level Design modified. --- /tmp/wklog.90.old.19182 2010-03-24 14:42:54.000000000 +0000 +++ /tmp/wklog.90.new.19182 2010-03-24 14:42:54.000000000 +0000 @@ -1 +1,140 @@ +<contents> +1. Applicability check +2. Representation +2.1 Option #1: Convert to TABLE_LIST +2.2 On subquery predicate removal +2.3 Option #2: No TABLE_LIST, convert to JOIN_TAB right away +2.3 What is expected of the result of conversion +3. Pre-optimization steps +3.1 Constant detection +3.3 update_ref_and_keys +3.4 JOIN_TAB sorting criteria +4. Optimization +5. Execution +User interface. +</contents> + +We'll call the new execution strategy "jtbm-materialization", for the lack of +better name. + +1. Applicability check +====================== +The criteria for checking whether a subquery can be processed with +jtbm-materialization can be checked at JOIN::prepare stage (like it +happens with semi-join check) + +2. Representation +================= + +2.1 Option #1: Convert to TABLE_LIST +------------------------------------ +Make it work like semi-join nests: each jtbm-predicate is converted into a +TABLE_LIST object. This will make it + + - uniform with semi-joins (we've stepped on all rakes there) + - allow to process JTBM-subqueries in ON expressions + +simplify_joins() will handle jtbm TABLE_LISTs as some kinds of opaque base +tables. + +for EXPLAIN EXTENDED, it would be natural to print something semi-join like, +i.e. for + + SELECT ... FROM ot WHERE oe IN (SELECT ie FROM materialized-non-sj-select) + +we'll print + + SELECT ... FROM ot SJ (SELECT ie FROM materialized-non-sj-select) ON oe=XX + +the XX part is not clear. we don't want to print 'ie' the second time here? + +2.2 On subquery predicate removal +--------------------------------- +Q: if we remove the subquery predicate permanently, who will run +fix_fields() for it? For semi-joins we don't have the problem as we +inject into ON expression (right? or not? we have sj_on_expr, too... +(Investigation: we the the same Item* pointer both in WHERE and +as sj_on_expr. fix_fields() is called for the WHERE part and that's +how sj_on_expr gets fixed. This works as long as +Item_func_eq::fix_fields() does not try to substitute itself with +another item). +A: ? + +2.3 Option #2: No TABLE_LIST, convert to JOIN_TAB right away +------------------------------------------------------------ +JOIN_TABs only live for the duration of one PS re-execution, so we'll have to +- make conversion fully undoable +- perform it sufficiently late in the optimization process, at the point + where JOIN_TABs are already allocated. + +Note that if we don't position JTBM predicates in join's TABLE_LIST tree, then +it will be impossible to handle JTBM queries inside/outside of outer joins. + +2.3 What is expected of the result of conversion +------------------------------------------------ +Join [pre]optimization relies on each optimized entity to have a bit in +table_map. + +TODO: where do we check if there will be enough bits for everyone? (at the + point where we assign them?) + +The bit stored in join_tab->table->map, and the apparent problem is that JTBM +join_tabs do not naturally have TABLE* object. + +We could use the the one that will be used for Materialization, but that will +stop working when we will have to include IN->EXISTS in the choice. + +Current approach: don't create a table. create a table_map element in JOIN_TAB +instead. Evgen has probably done something like that already. + +3. Pre-optimization steps +========================= +JOIN_TABs are allocated in make_join_statistics(). This where the changes will +be needed: for JOIN_TABs that correspond to JTBM-tables: + +- don't set tab->table, set tab->jtbm_select (or whatever) +- run subquery's optimizer to get its output cardinality + +3.1 Constant detection +---------------------- +What about subqueries that "are constant"? + const_item IN (SELECT uncorrelated) -> is constant, but not something + we would want to evaluate. + something IN (SELECT from_constant_join) -> is constant + +Do we need to mark their JOIN_TABs as constant? + +3.3 update_ref_and_keys +----------------------- +* Walk through JTBM elements and inject KEYUSE elements for their + IN-equalities. + +TODO: KEYUSE elements imply presense of KEYs! Which we don't have! + +3.4 JOIN_TAB sorting criteria +----------------------------- +Q: Where do we put JTBM's join_tab when pre-sorting records? +A: it should sort as regular table. + +TODO: where do we remove the predicates from the WHERE? + - remove them like SJ-converter does + - remove them with optimizer (like remove_eq_conds does) + +4. Optimization +=============== +Add a branch in best_access_path to account for +- JTBM-Materialization +- JTBM-Materialization-Scan. + +5. Execution +============ +* We should be able to reuse item_subselect.cc code for lookups +* But will have to use our own temptable scan code + +TODO: is it possible to have any unification with SJ-Materialization? + +User interface +-------------- +Any @@optimizer_switch flags for all this? + -=-=(Igor - Wed, 10 Mar 2010, 22:02)=-=- High Level Description modified. --- /tmp/wklog.90.old.2007 2010-03-10 22:02:23.000000000 +0000 +++ /tmp/wklog.90.new.2007 2010-03-10 22:02:23.000000000 +0000 @@ -13,8 +13,8 @@ for each record R2 in big_table such that oe=R1 pass R2 to output -Semi-join materialization supports such strategy with SJM-Scan strategy. This WL -entry is about adding support for such strategies for non-semijoin subqueries. +Semi-join materialization supports the inside-out strategy. This WL entry is +about adding support for such strategies for non-semijoin subqueries. Once WL#89 is done, there will be a cost-based choice between -=-=(Igor - Wed, 10 Mar 2010, 21:52)=-=- Status updated. --- /tmp/wklog.90.old.882 2010-03-10 21:52:02.000000000 +0000 +++ /tmp/wklog.90.new.882 2010-03-10 21:52:02.000000000 +0000 @@ -1 +1 @@ -Un-Assigned +Assigned -=-=(Psergey - Sun, 28 Feb 2010, 15:37)=-=- High Level Description modified. --- /tmp/wklog.90.old.23524 2010-02-28 15:37:47.000000000 +0000 +++ /tmp/wklog.90.new.23524 2010-02-28 15:37:47.000000000 +0000 @@ -15,3 +15,7 @@ Semi-join materialization supports such strategy with SJM-Scan strategy. This WL entry is about adding support for such strategies for non-semijoin subqueries. + + +Once WL#89 is done, there will be a cost-based choice between +Materialization+lookup, Materialization+scan, and IN->EXISTS+lookup strategies. -=-=(Psergey - Sun, 28 Feb 2010, 15:22)=-=- High-Level Specification modified. --- /tmp/wklog.90.old.23033 2010-02-28 15:22:09.000000000 +0000 +++ /tmp/wklog.90.new.23033 2010-02-28 15:22:09.000000000 +0000 @@ -1 +1,33 @@ +Basic idea on how this could be achieved: + +Pre-optimization phase +---------------------- + +The rewrite +~~~~~~~~~~~ +If we find a subquery predicate that is +- not processed by current semi-join optimizations +- is an AND-part of the WHERE/ON clause +- can be executed with Materialization + +then +- Remove the predicate from WHERE/ON clause +- Add a special JOIN_TAB object instead. + +Plan options +~~~~~~~~~~~~ +- Use the IN-equality to create KEYUSE elements. + +Optimization +------------ +- Pre-optimize the subquery so we know materialization cost +- Whenever best_access_path() encounters the "special JOIN_TAB" it should + consider two strategies: + A. Materialization and making lookups in the materialized table (if applicable) + B. Materialization and then scanning the materialized table. + + +EXPLAIN +------- +TODO how this will look in EXPLAIN output? -=-=(Psergey - Sun, 28 Feb 2010, 14:56)=-=- Dependency created: 91 now depends on 90 -=-=(Psergey - Sun, 28 Feb 2010, 14:54)=-=- Dependency deleted: 94 no longer depends on 90 -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- Title modified. --- /tmp/wklog.90.old.21903 2010-02-28 14:47:54.000000000 +0000 +++ /tmp/wklog.90.new.21903 2010-02-28 14:47:54.000000000 +0000 @@ -1 +1 @@ - Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE +Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- High Level Description modified. --- /tmp/wklog.90.old.21880 2010-02-28 14:47:28.000000000 +0000 +++ /tmp/wklog.90.new.21880 2010-02-28 14:47:28.000000000 +0000 @@ -1,10 +1,17 @@ -For uncorrelated IN subqueries that can't be converted to semi-joins it is -necessary to make a cost-based choice between IN->EXISTS and Materialization -strategies. +Consider the following case: -Both strategies handle two cases: -1. A simple case w/o NULLs handling -2. Handling NULLs. +SELECT * FROM big_table +WHERE oe IN (SELECT ie FROM table_with_few_groups + WHERE ... + GROUP BY group_col) AND ... -This WL is about making cost-based decision for #1. +Here the best way to execute the query is: + Materialize the subquery; + # now run the join: + for each record R1 in materialized table + for each record R2 in big_table such that oe=R1 + pass R2 to output + +Semi-join materialization supports such strategy with SJM-Scan strategy. This WL +entry is about adding support for such strategies for non-semijoin subqueries. -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- Title modified. --- /tmp/wklog.90.old.21859 2010-02-28 14:47:02.000000000 +0000 +++ /tmp/wklog.90.new.21859 2010-02-28 14:47:02.000000000 +0000 @@ -1 +1 @@ -Subqueries: cost-based choice between Materialization and IN->EXISTS transformation + Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE ------------------------------------------------------------ -=-=(View All Progress Notes, 11 total)=-=- http://askmonty.org/worklog/index.pl?tid=90&nolimit=1 DESCRIPTION: Consider the following case: SELECT * FROM big_table WHERE oe IN (SELECT ie FROM table_with_few_groups WHERE ... GROUP BY group_col) AND ... Here the best way to execute the query is: Materialize the subquery; # now run the join: for each record R1 in materialized table for each record R2 in big_table such that oe=R1 pass R2 to output Semi-join materialization supports the inside-out strategy. This WL entry is about adding support for such strategies for non-semijoin subqueries. Once WL#89 is done, there will be a cost-based choice between Materialization+lookup, Materialization+scan, and IN->EXISTS+lookup strategies. HIGH-LEVEL SPECIFICATION: Basic idea on how this could be achieved: Pre-optimization phase ---------------------- The rewrite ~~~~~~~~~~~ If we find a subquery predicate that is - not processed by current semi-join optimizations - is an AND-part of the WHERE/ON clause - can be executed with Materialization then - Remove the predicate from WHERE/ON clause - Add a special JOIN_TAB object instead. Plan options ~~~~~~~~~~~~ - Use the IN-equality to create KEYUSE elements. Optimization ------------ - Pre-optimize the subquery so we know materialization cost - Whenever best_access_path() encounters the "special JOIN_TAB" it should consider two strategies: A. Materialization and making lookups in the materialized table (if applicable) B. Materialization and then scanning the materialized table. EXPLAIN ------- TODO how this will look in EXPLAIN output? LOW-LEVEL DESIGN: <contents> 1. Applicability check 2. Representation 2.1 Option #1: Convert to TABLE_LIST 2.2 On subquery predicate removal 2.3 Option #2: No TABLE_LIST, convert to JOIN_TAB right away 2.3 What is expected of the result of conversion 3. Pre-optimization steps 3.1 Constant detection 3.3 update_ref_and_keys 3.4 JOIN_TAB sorting criteria 4. Optimization 5. Execution User interface. </contents> We'll call the new execution strategy "jtbm-materialization", for the lack of better name. 1. Applicability check ====================== The criteria for checking whether a subquery can be processed with jtbm-materialization can be checked at JOIN::prepare stage (like it happens with semi-join check) 2. Representation ================= 2.1 Option #1: Convert to TABLE_LIST ------------------------------------ Make it work like semi-join nests: each jtbm-predicate is converted into a TABLE_LIST object. This will make it - uniform with semi-joins (we've stepped on all rakes there) - allow to process JTBM-subqueries in ON expressions simplify_joins() will handle jtbm TABLE_LISTs as some kinds of opaque base tables. for EXPLAIN EXTENDED, it would be natural to print something semi-join like, i.e. for SELECT ... FROM ot WHERE oe IN (SELECT ie FROM materialized-non-sj-select) we'll print SELECT ... FROM ot SJ (SELECT ie FROM materialized-non-sj-select) ON oe=XX the XX part is not clear. we don't want to print 'ie' the second time here? 2.2 On subquery predicate removal --------------------------------- Q: if we remove the subquery predicate permanently, who will run fix_fields() for it? For semi-joins we don't have the problem as we inject into ON expression (right? or not? we have sj_on_expr, too... (Investigation: we the the same Item* pointer both in WHERE and as sj_on_expr. fix_fields() is called for the WHERE part and that's how sj_on_expr gets fixed. This works as long as Item_func_eq::fix_fields() does not try to substitute itself with another item). A: ? 2.3 Option #2: No TABLE_LIST, convert to JOIN_TAB right away ------------------------------------------------------------ JOIN_TABs only live for the duration of one PS re-execution, so we'll have to - make conversion fully undoable - perform it sufficiently late in the optimization process, at the point where JOIN_TABs are already allocated. Note that if we don't position JTBM predicates in join's TABLE_LIST tree, then it will be impossible to handle JTBM queries inside/outside of outer joins. 2.3 What is expected of the result of conversion ------------------------------------------------ Join [pre]optimization relies on each optimized entity to have a bit in table_map. TODO: where do we check if there will be enough bits for everyone? (at the point where we assign them?) The bit stored in join_tab->table->map, and the apparent problem is that JTBM join_tabs do not naturally have TABLE* object. We could use the the one that will be used for Materialization, but that will stop working when we will have to include IN->EXISTS in the choice. Current approach: don't create a table. create a table_map element in JOIN_TAB instead. Evgen has probably done something like that already. 3. Pre-optimization steps ========================= JOIN_TABs are allocated in make_join_statistics(). This where the changes will be needed: for JOIN_TABs that correspond to JTBM-tables: - don't set tab->table, set tab->jtbm_select (or whatever) - run subquery's optimizer to get its output cardinality 3.1 Constant detection ---------------------- What about subqueries that "are constant"? const_item IN (SELECT uncorrelated) -> is constant, but not something we would want to evaluate. something IN (SELECT from_constant_join) -> is constant Do we need to mark their JOIN_TABs as constant? 3.3 update_ref_and_keys ----------------------- * Walk through JTBM elements and inject KEYUSE elements for their IN-equalities. TODO: KEYUSE elements imply presense of KEYs! Which we don't have! 3.4 JOIN_TAB sorting criteria ----------------------------- Q: Where do we put JTBM's join_tab when pre-sorting records? A: it should sort as regular table. TODO: where do we remove the predicates from the WHERE? - remove them like SJ-converter does - remove them with optimizer (like remove_eq_conds does) 4. Optimization =============== Add a branch in best_access_path to account for - JTBM-Materialization - JTBM-Materialization-Scan. 5. Execution ============ * We should be able to reuse item_subselect.cc code for lookups * But will have to use our own temptable scan code TODO: is it possible to have any unification with SJ-Materialization? User interface -------------- Any @@optimizer_switch flags for all this? ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Psergey): Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE (90)
by worklog-noreply＠askmonty.org 24 Mar '10

24 Mar '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE CREATION DATE..: Sun, 28 Feb 2010, 13:45 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: Igor, Psergey, Timour CATEGORY.......: Server-RawIdeaBin TASK ID........: 90 (http://askmonty.org/worklog/?tid=90) VERSION........: Server-5.3 STATUS.........: Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: -1 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Wed, 24 Mar 2010, 14:42)=-=- Low Level Design modified. --- /tmp/wklog.90.old.19182 2010-03-24 14:42:54.000000000 +0000 +++ /tmp/wklog.90.new.19182 2010-03-24 14:42:54.000000000 +0000 @@ -1 +1,140 @@ +<contents> +1. Applicability check +2. Representation +2.1 Option #1: Convert to TABLE_LIST +2.2 On subquery predicate removal +2.3 Option #2: No TABLE_LIST, convert to JOIN_TAB right away +2.3 What is expected of the result of conversion +3. Pre-optimization steps +3.1 Constant detection +3.3 update_ref_and_keys +3.4 JOIN_TAB sorting criteria +4. Optimization +5. Execution +User interface. +</contents> + +We'll call the new execution strategy "jtbm-materialization", for the lack of +better name. + +1. Applicability check +====================== +The criteria for checking whether a subquery can be processed with +jtbm-materialization can be checked at JOIN::prepare stage (like it +happens with semi-join check) + +2. Representation +================= + +2.1 Option #1: Convert to TABLE_LIST +------------------------------------ +Make it work like semi-join nests: each jtbm-predicate is converted into a +TABLE_LIST object. This will make it + + - uniform with semi-joins (we've stepped on all rakes there) + - allow to process JTBM-subqueries in ON expressions + +simplify_joins() will handle jtbm TABLE_LISTs as some kinds of opaque base +tables. + +for EXPLAIN EXTENDED, it would be natural to print something semi-join like, +i.e. for + + SELECT ... FROM ot WHERE oe IN (SELECT ie FROM materialized-non-sj-select) + +we'll print + + SELECT ... FROM ot SJ (SELECT ie FROM materialized-non-sj-select) ON oe=XX + +the XX part is not clear. we don't want to print 'ie' the second time here? + +2.2 On subquery predicate removal +--------------------------------- +Q: if we remove the subquery predicate permanently, who will run +fix_fields() for it? For semi-joins we don't have the problem as we +inject into ON expression (right? or not? we have sj_on_expr, too... +(Investigation: we the the same Item* pointer both in WHERE and +as sj_on_expr. fix_fields() is called for the WHERE part and that's +how sj_on_expr gets fixed. This works as long as +Item_func_eq::fix_fields() does not try to substitute itself with +another item). +A: ? + +2.3 Option #2: No TABLE_LIST, convert to JOIN_TAB right away +------------------------------------------------------------ +JOIN_TABs only live for the duration of one PS re-execution, so we'll have to +- make conversion fully undoable +- perform it sufficiently late in the optimization process, at the point + where JOIN_TABs are already allocated. + +Note that if we don't position JTBM predicates in join's TABLE_LIST tree, then +it will be impossible to handle JTBM queries inside/outside of outer joins. + +2.3 What is expected of the result of conversion +------------------------------------------------ +Join [pre]optimization relies on each optimized entity to have a bit in +table_map. + +TODO: where do we check if there will be enough bits for everyone? (at the + point where we assign them?) + +The bit stored in join_tab->table->map, and the apparent problem is that JTBM +join_tabs do not naturally have TABLE* object. + +We could use the the one that will be used for Materialization, but that will +stop working when we will have to include IN->EXISTS in the choice. + +Current approach: don't create a table. create a table_map element in JOIN_TAB +instead. Evgen has probably done something like that already. + +3. Pre-optimization steps +========================= +JOIN_TABs are allocated in make_join_statistics(). This where the changes will +be needed: for JOIN_TABs that correspond to JTBM-tables: + +- don't set tab->table, set tab->jtbm_select (or whatever) +- run subquery's optimizer to get its output cardinality + +3.1 Constant detection +---------------------- +What about subqueries that "are constant"? + const_item IN (SELECT uncorrelated) -> is constant, but not something + we would want to evaluate. + something IN (SELECT from_constant_join) -> is constant + +Do we need to mark their JOIN_TABs as constant? + +3.3 update_ref_and_keys +----------------------- +* Walk through JTBM elements and inject KEYUSE elements for their + IN-equalities. + +TODO: KEYUSE elements imply presense of KEYs! Which we don't have! + +3.4 JOIN_TAB sorting criteria +----------------------------- +Q: Where do we put JTBM's join_tab when pre-sorting records? +A: it should sort as regular table. + +TODO: where do we remove the predicates from the WHERE? + - remove them like SJ-converter does + - remove them with optimizer (like remove_eq_conds does) + +4. Optimization +=============== +Add a branch in best_access_path to account for +- JTBM-Materialization +- JTBM-Materialization-Scan. + +5. Execution +============ +* We should be able to reuse item_subselect.cc code for lookups +* But will have to use our own temptable scan code + +TODO: is it possible to have any unification with SJ-Materialization? + +User interface +-------------- +Any @@optimizer_switch flags for all this? + -=-=(Igor - Wed, 10 Mar 2010, 22:02)=-=- High Level Description modified. --- /tmp/wklog.90.old.2007 2010-03-10 22:02:23.000000000 +0000 +++ /tmp/wklog.90.new.2007 2010-03-10 22:02:23.000000000 +0000 @@ -13,8 +13,8 @@ for each record R2 in big_table such that oe=R1 pass R2 to output -Semi-join materialization supports such strategy with SJM-Scan strategy. This WL -entry is about adding support for such strategies for non-semijoin subqueries. +Semi-join materialization supports the inside-out strategy. This WL entry is +about adding support for such strategies for non-semijoin subqueries. Once WL#89 is done, there will be a cost-based choice between -=-=(Igor - Wed, 10 Mar 2010, 21:52)=-=- Status updated. --- /tmp/wklog.90.old.882 2010-03-10 21:52:02.000000000 +0000 +++ /tmp/wklog.90.new.882 2010-03-10 21:52:02.000000000 +0000 @@ -1 +1 @@ -Un-Assigned +Assigned -=-=(Psergey - Sun, 28 Feb 2010, 15:37)=-=- High Level Description modified. --- /tmp/wklog.90.old.23524 2010-02-28 15:37:47.000000000 +0000 +++ /tmp/wklog.90.new.23524 2010-02-28 15:37:47.000000000 +0000 @@ -15,3 +15,7 @@ Semi-join materialization supports such strategy with SJM-Scan strategy. This WL entry is about adding support for such strategies for non-semijoin subqueries. + + +Once WL#89 is done, there will be a cost-based choice between +Materialization+lookup, Materialization+scan, and IN->EXISTS+lookup strategies. -=-=(Psergey - Sun, 28 Feb 2010, 15:22)=-=- High-Level Specification modified. --- /tmp/wklog.90.old.23033 2010-02-28 15:22:09.000000000 +0000 +++ /tmp/wklog.90.new.23033 2010-02-28 15:22:09.000000000 +0000 @@ -1 +1,33 @@ +Basic idea on how this could be achieved: + +Pre-optimization phase +---------------------- + +The rewrite +~~~~~~~~~~~ +If we find a subquery predicate that is +- not processed by current semi-join optimizations +- is an AND-part of the WHERE/ON clause +- can be executed with Materialization + +then +- Remove the predicate from WHERE/ON clause +- Add a special JOIN_TAB object instead. + +Plan options +~~~~~~~~~~~~ +- Use the IN-equality to create KEYUSE elements. + +Optimization +------------ +- Pre-optimize the subquery so we know materialization cost +- Whenever best_access_path() encounters the "special JOIN_TAB" it should + consider two strategies: + A. Materialization and making lookups in the materialized table (if applicable) + B. Materialization and then scanning the materialized table. + + +EXPLAIN +------- +TODO how this will look in EXPLAIN output? -=-=(Psergey - Sun, 28 Feb 2010, 14:56)=-=- Dependency created: 91 now depends on 90 -=-=(Psergey - Sun, 28 Feb 2010, 14:54)=-=- Dependency deleted: 94 no longer depends on 90 -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- Title modified. --- /tmp/wklog.90.old.21903 2010-02-28 14:47:54.000000000 +0000 +++ /tmp/wklog.90.new.21903 2010-02-28 14:47:54.000000000 +0000 @@ -1 +1 @@ - Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE +Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- High Level Description modified. --- /tmp/wklog.90.old.21880 2010-02-28 14:47:28.000000000 +0000 +++ /tmp/wklog.90.new.21880 2010-02-28 14:47:28.000000000 +0000 @@ -1,10 +1,17 @@ -For uncorrelated IN subqueries that can't be converted to semi-joins it is -necessary to make a cost-based choice between IN->EXISTS and Materialization -strategies. +Consider the following case: -Both strategies handle two cases: -1. A simple case w/o NULLs handling -2. Handling NULLs. +SELECT * FROM big_table +WHERE oe IN (SELECT ie FROM table_with_few_groups + WHERE ... + GROUP BY group_col) AND ... -This WL is about making cost-based decision for #1. +Here the best way to execute the query is: + Materialize the subquery; + # now run the join: + for each record R1 in materialized table + for each record R2 in big_table such that oe=R1 + pass R2 to output + +Semi-join materialization supports such strategy with SJM-Scan strategy. This WL +entry is about adding support for such strategies for non-semijoin subqueries. -=-=(Psergey - Sun, 28 Feb 2010, 14:47)=-=- Title modified. --- /tmp/wklog.90.old.21859 2010-02-28 14:47:02.000000000 +0000 +++ /tmp/wklog.90.new.21859 2010-02-28 14:47:02.000000000 +0000 @@ -1 +1 @@ -Subqueries: cost-based choice between Materialization and IN->EXISTS transformation + Subqueries: Inside-out execution for non-semijoin materialized subqueries that are AND-parts of the WHERE ------------------------------------------------------------ -=-=(View All Progress Notes, 11 total)=-=- http://askmonty.org/worklog/index.pl?tid=90&nolimit=1 DESCRIPTION: Consider the following case: SELECT * FROM big_table WHERE oe IN (SELECT ie FROM table_with_few_groups WHERE ... GROUP BY group_col) AND ... Here the best way to execute the query is: Materialize the subquery; # now run the join: for each record R1 in materialized table for each record R2 in big_table such that oe=R1 pass R2 to output Semi-join materialization supports the inside-out strategy. This WL entry is about adding support for such strategies for non-semijoin subqueries. Once WL#89 is done, there will be a cost-based choice between Materialization+lookup, Materialization+scan, and IN->EXISTS+lookup strategies. HIGH-LEVEL SPECIFICATION: Basic idea on how this could be achieved: Pre-optimization phase ---------------------- The rewrite ~~~~~~~~~~~ If we find a subquery predicate that is - not processed by current semi-join optimizations - is an AND-part of the WHERE/ON clause - can be executed with Materialization then - Remove the predicate from WHERE/ON clause - Add a special JOIN_TAB object instead. Plan options ~~~~~~~~~~~~ - Use the IN-equality to create KEYUSE elements. Optimization ------------ - Pre-optimize the subquery so we know materialization cost - Whenever best_access_path() encounters the "special JOIN_TAB" it should consider two strategies: A. Materialization and making lookups in the materialized table (if applicable) B. Materialization and then scanning the materialized table. EXPLAIN ------- TODO how this will look in EXPLAIN output? LOW-LEVEL DESIGN: <contents> 1. Applicability check 2. Representation 2.1 Option #1: Convert to TABLE_LIST 2.2 On subquery predicate removal 2.3 Option #2: No TABLE_LIST, convert to JOIN_TAB right away 2.3 What is expected of the result of conversion 3. Pre-optimization steps 3.1 Constant detection 3.3 update_ref_and_keys 3.4 JOIN_TAB sorting criteria 4. Optimization 5. Execution User interface. </contents> We'll call the new execution strategy "jtbm-materialization", for the lack of better name. 1. Applicability check ====================== The criteria for checking whether a subquery can be processed with jtbm-materialization can be checked at JOIN::prepare stage (like it happens with semi-join check) 2. Representation ================= 2.1 Option #1: Convert to TABLE_LIST ------------------------------------ Make it work like semi-join nests: each jtbm-predicate is converted into a TABLE_LIST object. This will make it - uniform with semi-joins (we've stepped on all rakes there) - allow to process JTBM-subqueries in ON expressions simplify_joins() will handle jtbm TABLE_LISTs as some kinds of opaque base tables. for EXPLAIN EXTENDED, it would be natural to print something semi-join like, i.e. for SELECT ... FROM ot WHERE oe IN (SELECT ie FROM materialized-non-sj-select) we'll print SELECT ... FROM ot SJ (SELECT ie FROM materialized-non-sj-select) ON oe=XX the XX part is not clear. we don't want to print 'ie' the second time here? 2.2 On subquery predicate removal --------------------------------- Q: if we remove the subquery predicate permanently, who will run fix_fields() for it? For semi-joins we don't have the problem as we inject into ON expression (right? or not? we have sj_on_expr, too... (Investigation: we the the same Item* pointer both in WHERE and as sj_on_expr. fix_fields() is called for the WHERE part and that's how sj_on_expr gets fixed. This works as long as Item_func_eq::fix_fields() does not try to substitute itself with another item). A: ? 2.3 Option #2: No TABLE_LIST, convert to JOIN_TAB right away ------------------------------------------------------------ JOIN_TABs only live for the duration of one PS re-execution, so we'll have to - make conversion fully undoable - perform it sufficiently late in the optimization process, at the point where JOIN_TABs are already allocated. Note that if we don't position JTBM predicates in join's TABLE_LIST tree, then it will be impossible to handle JTBM queries inside/outside of outer joins. 2.3 What is expected of the result of conversion ------------------------------------------------ Join [pre]optimization relies on each optimized entity to have a bit in table_map. TODO: where do we check if there will be enough bits for everyone? (at the point where we assign them?) The bit stored in join_tab->table->map, and the apparent problem is that JTBM join_tabs do not naturally have TABLE* object. We could use the the one that will be used for Materialization, but that will stop working when we will have to include IN->EXISTS in the choice. Current approach: don't create a table. create a table_map element in JOIN_TAB instead. Evgen has probably done something like that already. 3. Pre-optimization steps ========================= JOIN_TABs are allocated in make_join_statistics(). This where the changes will be needed: for JOIN_TABs that correspond to JTBM-tables: - don't set tab->table, set tab->jtbm_select (or whatever) - run subquery's optimizer to get its output cardinality 3.1 Constant detection ---------------------- What about subqueries that "are constant"? const_item IN (SELECT uncorrelated) -> is constant, but not something we would want to evaluate. something IN (SELECT from_constant_join) -> is constant Do we need to mark their JOIN_TABs as constant? 3.3 update_ref_and_keys ----------------------- * Walk through JTBM elements and inject KEYUSE elements for their IN-equalities. TODO: KEYUSE elements imply presense of KEYs! Which we don't have! 3.4 JOIN_TAB sorting criteria ----------------------------- Q: Where do we put JTBM's join_tab when pre-sorting records? A: it should sort as regular table. TODO: where do we remove the predicates from the WHERE? - remove them like SJ-converter does - remove them with optimizer (like remove_eq_conds does) 4. Optimization =============== Add a branch in best_access_path to account for - JTBM-Materialization - JTBM-Materialization-Scan. 5. Execution ============ * We should be able to reuse item_subselect.cc code for lookups * But will have to use our own temptable scan code TODO: is it possible to have any unification with SJ-Materialization? User interface -------------- Any @@optimizer_switch flags for all this? ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0