July 2009 - developers - lists.mariadb.org

[Maria-developers] bzr commit into Mariadb 5.2, with Maria 2.0:maria/5.2 branch (sanja:2725)
by sanja＠askmonty.org 27 Nov '09

27 Nov '09

#At lp:maria/5.2 2725 sanja(a)askmonty.org 2009-07-07 Group commit and small optimisation of flush log (in case of page without CRC and sector protection) added. (for review) modified: mysql-test/suite/maria/r/maria3.result storage/maria/ha_maria.cc storage/maria/ma_init.c storage/maria/ma_loghandler.c storage/maria/ma_loghandler.h per-file messages: mysql-test/suite/maria/r/maria3.result New variables added storage/maria/ha_maria.cc New variables for group commit and routines to control them added. storage/maria/ma_init.c Service thread stop (if it is present) storage/maria/ma_loghandler.c 2 types of group commit added. If page is not protetcted by CRC or sector protection (i.e. we do not change header when add data to the page) we do not copy beginning of the page during forcing the buffer where the page is last to close. storage/maria/ma_loghandler.h Routines to control group commit added. === modified file 'mysql-test/suite/maria/r/maria3.result' --- a/mysql-test/suite/maria/r/maria3.result 2009-02-19 09:01:25 +0000 +++ b/mysql-test/suite/maria/r/maria3.result 2009-07-07 00:37:23 +0000 @@ -264,6 +264,8 @@ Variable_name Value maria_block_size 8192 maria_checkpoint_interval 30 maria_force_start_after_recovery_failures 0 +maria_group_commit none +maria_group_commit_rate 800 maria_log_file_size 4294959104 maria_log_purge_type immediate maria_max_sort_file_size 9223372036853727232 @@ -285,6 +287,7 @@ Maria_pagecache_read_requests # Maria_pagecache_reads # Maria_pagecache_write_requests # Maria_pagecache_writes # +Maria_transaction_log_syncs # create table t1 (b char(0)); insert into t1 values(NULL),(""); select length(b) from t1; === modified file 'storage/maria/ha_maria.cc' --- a/storage/maria/ha_maria.cc 2009-05-19 09:28:05 +0000 +++ b/storage/maria/ha_maria.cc 2009-07-07 00:37:23 +0000 @@ -101,22 +101,40 @@ TYPELIB maria_translog_purge_type_typeli array_elements(maria_translog_purge_type_names) - 1, "", maria_translog_purge_type_names, NULL }; + +/* transactional log directory sync */ const char *maria_sync_log_dir_names[]= { "NEVER", "NEWFILE", "ALWAYS", NullS }; - TYPELIB maria_sync_log_dir_typelib= { array_elements(maria_sync_log_dir_names) - 1, "", maria_sync_log_dir_names, NULL }; +/* transactional log group commit */ +const char *maria_group_commit_names[]= +{ + "none", "hard", "soft", NullS +}; +TYPELIB maria_group_commit_typelib= +{ + array_elements(maria_group_commit_names) - 1, "", + maria_group_commit_names, NULL +}; + /** Interval between background checkpoints in seconds */ static ulong checkpoint_interval; static void update_checkpoint_interval(MYSQL_THD thd, struct st_mysql_sys_var *var, void *var_ptr, const void *save); +static void update_maria_group_commit(MYSQL_THD thd, + struct st_mysql_sys_var *var, + void *var_ptr, const void *save); +static void update_maria_group_commit_rate(MYSQL_THD thd, + struct st_mysql_sys_var *var, + void *var_ptr, const void *save); /** After that many consecutive recovery failures, remove logs */ static ulong force_start_after_recovery_failures; static void update_log_file_size(MYSQL_THD thd, @@ -163,6 +181,24 @@ static MYSQL_SYSVAR_ULONG(log_file_size, NULL, update_log_file_size, TRANSLOG_FILE_SIZE, TRANSLOG_MIN_FILE_SIZE, 0xffffffffL, TRANSLOG_PAGE_SIZE); +static MYSQL_SYSVAR_ENUM(group_commit, maria_group_commit, + PLUGIN_VAR_RQCMDARG, + "Specifies maria group commit mode. " + "Possible values are \"none\" (no group commit), " + "\"hard\" (with waiting to actual commit), " + "\"soft\" (no wait for commit (DANGEROUS!!!))", + NULL, update_maria_group_commit, + TRANSLOG_GCOMMIT_NONE, &maria_group_commit_typelib); + +static MYSQL_SYSVAR_ULONG(group_commit_rate, maria_group_commit_rate, + PLUGIN_VAR_RQCMDARG, + "Number of commits per 100 seconds. (in other words one commit for" + "every 100/maria_group_commit_rate second). 0 stands for no waiting" + "for other threads to come and do a commit in \"hard\" mode and no" + " sync()/commit at all in \"soft\" mode. Option has only an effect" + "if maria_group_commit is used", + NULL, update_maria_group_commit_rate, 800, 0, UINT_MAX, 1); + static MYSQL_SYSVAR_ENUM(log_purge_type, log_purge_type, PLUGIN_VAR_RQCMDARG, "Specifies how maria transactional log will be purged. " @@ -3254,6 +3290,8 @@ static struct st_mysql_sys_var* system_v MYSQL_SYSVAR(block_size), MYSQL_SYSVAR(checkpoint_interval), MYSQL_SYSVAR(force_start_after_recovery_failures), + MYSQL_SYSVAR(group_commit), + MYSQL_SYSVAR(group_commit_rate), MYSQL_SYSVAR(page_checksum), MYSQL_SYSVAR(log_dir_path), MYSQL_SYSVAR(log_file_size), @@ -3284,6 +3322,97 @@ static void update_checkpoint_interval(M } /** + @brief Updates group commit mode +*/ + +static void update_maria_group_commit(MYSQL_THD thd, + struct st_mysql_sys_var *var, + void *var_ptr, const void *save) +{ + ulong value= (ulong)*((long *)var_ptr); + DBUG_ENTER("update_maria_group_commit"); + DBUG_PRINT("enter", ("old value: %lu new value %lu rate %lu", + value, (ulong)(*(long *)save), + maria_group_commit_rate)); + /* old value */ + switch (value) { + case TRANSLOG_GCOMMIT_NONE: + break; + case TRANSLOG_GCOMMIT_HARD: + translog_hard_group_commit(FALSE); + break; + case TRANSLOG_GCOMMIT_SOFT: + translog_soft_sync(FALSE); + if (maria_group_commit_rate) + translog_soft_sync_end(); + break; + default: + DBUG_ASSERT(0); /* impossible */ + } + value= *(ulong *)var_ptr= (ulong)(*(long *)save); + translog_sync(); + /* new value */ + switch (value) { + case TRANSLOG_GCOMMIT_NONE: + break; + case TRANSLOG_GCOMMIT_HARD: + translog_hard_group_commit(TRUE); + break; + case TRANSLOG_GCOMMIT_SOFT: + translog_soft_sync(TRUE); + /* variable change made under global lock so we can just read it */ + if (maria_group_commit_rate) + translog_soft_sync_start(); + break; + default: + DBUG_ASSERT(0); /* impossible */ + } + DBUG_VOID_RETURN; +} + +/** + @brief Updates group commit rate +*/ + +static void update_maria_group_commit_rate(MYSQL_THD thd, + struct st_mysql_sys_var *var, + void *var_ptr, const void *save) +{ + ulong new_value= (ulong)*((long *)save); + ulong *value_ptr= (ulong*) var_ptr; + DBUG_ENTER("update_maria_group_commit_rate"); + DBUG_PRINT("enter", ("old value: %lu new value %lu group commit %lu", + *value_ptr, new_value, maria_group_commit)); + if (new_value && + ((TRANSLOG_RATE_BASE * 1000000000ULL / new_value + + TRANSLOG_RATE_BASE / 2) / + TRANSLOG_RATE_BASE) == 0) + new_value= 0; /* protection against too small value */ + + /* variable change made under global lock so we can just read it */ + switch (maria_group_commit) { + case TRANSLOG_GCOMMIT_NONE: + *value_ptr= new_value; + translog_set_group_commit_rate(new_value); + break; + case TRANSLOG_GCOMMIT_HARD: + *value_ptr= new_value; + translog_set_group_commit_rate(new_value); + break; + case TRANSLOG_GCOMMIT_SOFT: + if (*value_ptr) + translog_soft_sync_end(); + translog_set_group_commit_rate(new_value); + if ((*value_ptr= new_value)) + translog_soft_sync_start(); + break; + default: + DBUG_ASSERT(0); /* impossible */ + } + DBUG_VOID_RETURN; +} + +/** @brief Updates the transaction log file limit. */ @@ -3305,6 +3434,7 @@ static SHOW_VAR status_variables[]= { {"Maria_pagecache_reads", (char*) &maria_pagecache_var.global_cache_read, SHOW_LONGLONG}, {"Maria_pagecache_write_requests", (char*) &maria_pagecache_var.global_cache_w_requests, SHOW_LONGLONG}, {"Maria_pagecache_writes", (char*) &maria_pagecache_var.global_cache_write, SHOW_LONGLONG}, + {"Maria_transaction_log_syncs", (char*) &translog_syncs, SHOW_LONGLONG}, {NullS, NullS, SHOW_LONG} }; === modified file 'storage/maria/ma_init.c' --- a/storage/maria/ma_init.c 2008-10-09 20:03:54 +0000 +++ b/storage/maria/ma_init.c 2009-07-07 00:37:23 +0000 @@ -82,6 +82,11 @@ void maria_end(void) maria_inited= maria_multi_threaded= FALSE; ft_free_stopwords(); ma_checkpoint_end(); + if (translog_status == TRANSLOG_OK) + { + translog_soft_sync_end(); + translog_sync(); + } if ((trid= trnman_get_max_trid()) > max_trid_in_control_file) { /* === modified file 'storage/maria/ma_loghandler.c' --- a/storage/maria/ma_loghandler.c 2009-05-19 09:28:05 +0000 +++ b/storage/maria/ma_loghandler.c 2009-07-07 00:37:23 +0000 @@ -18,6 +18,7 @@ #include "ma_blockrec.h" /* for some constants and in-write hooks */ #include "ma_key_recover.h" /* For some in-write hooks */ #include "ma_checkpoint.h" +#include "ma_servicethread.h" /* On Windows, neither my_open() nor my_sync() work for directories. @@ -47,6 +48,15 @@ #include <m_ctype.h> #endif +/** @brief protects checkpoint_in_progress */ +static pthread_mutex_t LOCK_soft_sync; +/** @brief for killing the background checkpoint thread */ +static pthread_cond_t COND_soft_sync; +/** @brief control structure for checkpoint background thread */ +static MA_SERVICE_THREAD_CONTROL soft_sync_control= + {THREAD_DEAD, FALSE, &LOCK_soft_sync, &COND_soft_sync}; + + /* transaction log file descriptor */ typedef struct st_translog_file { @@ -124,10 +134,20 @@ struct st_translog_buffer /* Previous buffer offset to detect it flush finish */ TRANSLOG_ADDRESS prev_buffer_offset; /* + If the buffer was forced to close it save value of its horizon + otherwise LSN_IMPOSSIBLE + */ + TRANSLOG_ADDRESS pre_force_close_horizon; + /* How much is written (or will be written when copy_to_buffer_in_progress become 0) to this buffer */ translog_size_t size; + /* + How much data was skipped during moving page from previous buffer + to this one (it is optimisation of forcing buffer to finish + */ + uint skipped_data; /* File handler for this buffer */ TRANSLOG_FILE *file; /* Threads which are waiting for buffer filling/freeing */ @@ -304,6 +324,7 @@ struct st_translog_descriptor */ pthread_mutex_t log_flush_lock; pthread_cond_t log_flush_cond; + pthread_cond_t new_goal_cond; /* Protects changing of headers of finished files (max_lsn) */ pthread_mutex_t file_header_lock; @@ -344,13 +365,39 @@ static struct st_translog_descriptor log ulong log_purge_type= TRANSLOG_PURGE_IMMIDIATE; ulong log_file_size= TRANSLOG_FILE_SIZE; +/* sync() of log files directory mode */ ulong sync_log_dir= TRANSLOG_SYNC_DIR_NEWFILE; +ulong maria_group_commit= TRANSLOG_GCOMMIT_NONE; +ulong maria_group_commit_rate= 0; /* Marker for end of log */ static uchar end_of_log= 0; #define END_OF_LOG &end_of_log +/** + Switch for "soft" sync (no real sync() but periodical sync by service + thread) +*/ +static volatile my_bool soft_sync= FALSE; +/** + Switch for "hard" group commit mode +*/ +static volatile my_bool hard_group_commit= FALSE; +/** + File numbers interval which have to be sync() +*/ +static uint32 soft_sync_min= 0; +static uint32 soft_sync_max= 0; +/** + stores interval in nanoseconds/TRANSLOG_RATE_BASE (to + fit into uint32) +*/ +static uint32 group_commit_wait= 0; enum enum_translog_status translog_status= TRANSLOG_UNINITED; +ulonglong translog_syncs= 0; /* Number of sync()s */ + +/* time of last flush */ +static ulonglong flush_start= 0; /* chunk types */ #define TRANSLOG_CHUNK_LSN 0x00 /* 0 chunk refer as LSN (head or tail */ @@ -980,12 +1027,17 @@ static TRANSLOG_FILE *get_logfile_by_num static TRANSLOG_FILE *get_current_logfile() { TRANSLOG_FILE *file; + DBUG_ENTER("get_current_logfile"); rw_rdlock(&log_descriptor.open_files_lock); + DBUG_PRINT("info", ("max_file: %lu min_file: %lu open_files: %lu", + (ulong) log_descriptor.max_file, + (ulong) log_descriptor.min_file, + (ulong) log_descriptor.open_files.elements)); DBUG_ASSERT(log_descriptor.max_file - log_descriptor.min_file + 1 == log_descriptor.open_files.elements); file= *dynamic_element(&log_descriptor.open_files, 0, TRANSLOG_FILE **); rw_unlock(&log_descriptor.open_files_lock); - return (file); + DBUG_RETURN(file); } uchar NEAR maria_trans_file_magic[]= @@ -1069,6 +1121,7 @@ static my_bool translog_write_file_heade static my_bool translog_max_lsn_to_header(File file, LSN lsn) { uchar lsn_buff[LSN_STORE_SIZE]; + my_bool rc; DBUG_ENTER("translog_max_lsn_to_header"); DBUG_PRINT("enter", ("File descriptor: %ld " "lsn: (%lu,0x%lx)", @@ -1077,11 +1130,13 @@ static my_bool translog_max_lsn_to_heade lsn_store(lsn_buff, lsn); - DBUG_RETURN(my_pwrite(file, lsn_buff, - LSN_STORE_SIZE, - (LOG_HEADER_DATA_SIZE - LSN_STORE_SIZE), - log_write_flags) != 0 || - my_sync(file, MYF(MY_WME)) != 0); + if (!(rc= (my_pwrite(file, lsn_buff, + LSN_STORE_SIZE, + (LOG_HEADER_DATA_SIZE - LSN_STORE_SIZE), + log_write_flags) != 0 || + my_sync(file, MYF(MY_WME)) != 0))) + translog_syncs++; + DBUG_RETURN(rc); } @@ -1423,7 +1478,9 @@ LSN translog_get_file_max_lsn_stored(uin static my_bool translog_buffer_init(struct st_translog_buffer *buffer, int num) { DBUG_ENTER("translog_buffer_init"); - buffer->prev_last_lsn= buffer->last_lsn= LSN_IMPOSSIBLE; + buffer->pre_force_close_horizon= + buffer->prev_last_lsn= buffer->last_lsn= + LSN_IMPOSSIBLE; DBUG_PRINT("info", ("last_lsn and prev_last_lsn set to 0 buffer: 0x%lx", (ulong) buffer)); @@ -1435,6 +1492,7 @@ static my_bool translog_buffer_init(stru memset(buffer->buffer, TRANSLOG_FILLER, TRANSLOG_WRITE_BUFFER); /* Buffer size */ buffer->size= 0; + buffer->skipped_data= 0; /* cond of thread which is waiting for buffer filling */ if (pthread_cond_init(&buffer->waiting_filling_buffer, 0)) DBUG_RETURN(1); @@ -1489,7 +1547,10 @@ static my_bool translog_close_log_file(T TODO: sync only we have changed the log */ if (!file->is_sync) + { rc= my_sync(file->handler.file, MYF(MY_WME)); + translog_syncs++; + } rc|= my_close(file->handler.file, MYF(MY_WME)); my_free(file, MYF(0)); return test(rc); @@ -2044,7 +2105,8 @@ static void translog_start_buffer(struct (ulong) LSN_OFFSET(log_descriptor.horizon), (ulong) LSN_OFFSET(log_descriptor.horizon))); DBUG_ASSERT(buffer_no == buffer->buffer_no); - buffer->prev_last_lsn= buffer->last_lsn= LSN_IMPOSSIBLE; + buffer->pre_force_close_horizon= + buffer->prev_last_lsn= buffer->last_lsn= LSN_IMPOSSIBLE; DBUG_PRINT("info", ("last_lsn and prev_last_lsn set to 0 buffer: 0x%lx", (ulong) buffer)); buffer->offset= log_descriptor.horizon; @@ -2052,6 +2114,7 @@ static void translog_start_buffer(struct buffer->file= get_current_logfile(); buffer->overlay= 0; buffer->size= 0; + buffer->skipped_data= 0; translog_cursor_init(cursor, buffer, buffer_no); DBUG_PRINT("info", ("file: #%ld (%d) init cursor #%u: 0x%lx " "chaser: %d Size: %lu (%lu)", @@ -2523,6 +2586,7 @@ static my_bool translog_buffer_flush(str TRANSLOG_ADDRESS offset= buffer->offset; TRANSLOG_FILE *file= buffer->file; uint8 ver= buffer->ver; + uint skipped_data; DBUG_ENTER("translog_buffer_flush"); DBUG_PRINT("enter", ("Buffer: #%u 0x%lx file: %d offset: (%lu,0x%lx) size: %lu", @@ -2557,6 +2621,8 @@ static my_bool translog_buffer_flush(str disk */ file= buffer->file; + skipped_data= buffer->skipped_data; + DBUG_ASSERT(skipped_data < TRANSLOG_PAGE_SIZE); for (i= 0, pg= LSN_OFFSET(buffer->offset) / TRANSLOG_PAGE_SIZE; i < buffer->size; i+= TRANSLOG_PAGE_SIZE, pg++) @@ -2573,13 +2639,16 @@ static my_bool translog_buffer_flush(str DBUG_ASSERT(i + TRANSLOG_PAGE_SIZE <= buffer->size); if (translog_status != TRANSLOG_OK && translog_status != TRANSLOG_SHUTDOWN) DBUG_RETURN(1); - if (pagecache_inject(log_descriptor.pagecache, + if (pagecache_write_part(log_descriptor.pagecache, &file->handler, pg, 3, buffer->buffer + i, PAGECACHE_PLAIN_PAGE, PAGECACHE_LOCK_LEFT_UNLOCKED, - PAGECACHE_PIN_LEFT_UNPINNED, 0, - LSN_IMPOSSIBLE)) + PAGECACHE_PIN_LEFT_UNPINNED, + PAGECACHE_WRITE_DONE, 0, + LSN_IMPOSSIBLE, + skipped_data, + TRANSLOG_PAGE_SIZE - skipped_data)) { DBUG_PRINT("error", ("Can't write page (%lu,0x%lx) to pagecache, error: %d", @@ -2589,10 +2658,12 @@ static my_bool translog_buffer_flush(str translog_stop_writing(); DBUG_RETURN(1); } + skipped_data= 0; } file->is_sync= 0; - if (my_pwrite(file->handler.file, buffer->buffer, - buffer->size, LSN_OFFSET(buffer->offset), + if (my_pwrite(file->handler.file, buffer->buffer + buffer->skipped_data, + buffer->size - buffer->skipped_data, + LSN_OFFSET(buffer->offset) + buffer->skipped_data, log_write_flags)) { DBUG_PRINT("error", ("Can't write buffer (%lu,0x%lx) size %lu " @@ -2985,6 +3056,7 @@ restart: uchar *from, *table= NULL; int is_last_unfinished_page; uint last_protected_sector= 0; + uint skipped_data= curr_buffer->skipped_data; TRANSLOG_FILE file_copy; uint8 ver= curr_buffer->ver; translog_wait_for_writers(curr_buffer); @@ -2997,7 +3069,25 @@ restart: } DBUG_ASSERT(LSN_FILE_NO(addr) == LSN_FILE_NO(curr_buffer->offset)); from= curr_buffer->buffer + (addr - curr_buffer->offset); - memcpy(buffer, from, TRANSLOG_PAGE_SIZE); + if (skipped_data > (addr - curr_buffer->offset)) + { + /* + We read page part of which is not present in buffer, + so we should read absent part from file (page cache actually) + */ + file= get_logfile_by_number(file_no); + DBUG_ASSERT(file != NULL); + buffer= pagecache_read(log_descriptor.pagecache, &file->handler, + LSN_OFFSET(addr) / TRANSLOG_PAGE_SIZE, + 3, buffer, + PAGECACHE_PLAIN_PAGE, + PAGECACHE_LOCK_LEFT_UNLOCKED, + NULL); + } + else + skipped_data= 0; /* Read after skipped in buffer data */ + memcpy(buffer + skipped_data, from + skipped_data, + TRANSLOG_PAGE_SIZE - skipped_data); /* We can use copy then in translog_page_validator() because it do not put it permanently somewhere. @@ -3291,6 +3381,7 @@ static my_bool translog_truncate_log(TRA uint32 next_page_offset, page_rest; uint32 i; File fd; + int rc; TRANSLOG_VALIDATOR_DATA data; char path[FN_REFLEN]; uchar page_buff[TRANSLOG_PAGE_SIZE]; @@ -3316,14 +3407,19 @@ static my_bool translog_truncate_log(TRA TRANSLOG_PAGE_SIZE); page_rest= next_page_offset - LSN_OFFSET(addr); memset(page_buff, TRANSLOG_FILLER, page_rest); - if ((fd= open_logfile_by_number_no_cache(LSN_FILE_NO(addr))) < 0 || - ((my_chsize(fd, next_page_offset, TRANSLOG_FILLER, MYF(MY_WME)) || - (page_rest && my_pwrite(fd, page_buff, page_rest, LSN_OFFSET(addr), - log_write_flags)) || - my_sync(fd, MYF(MY_WME))) | - my_close(fd, MYF(MY_WME))) || - (sync_log_dir >= TRANSLOG_SYNC_DIR_ALWAYS && - sync_dir(log_descriptor.directory_fd, MYF(MY_WME | MY_IGNORE_BADFD)))) + rc= ((fd= open_logfile_by_number_no_cache(LSN_FILE_NO(addr))) < 0 || + ((my_chsize(fd, next_page_offset, TRANSLOG_FILLER, MYF(MY_WME)) || + (page_rest && my_pwrite(fd, page_buff, page_rest, LSN_OFFSET(addr), + log_write_flags)) || + my_sync(fd, MYF(MY_WME))))); + translog_syncs++; + rc|= (fd > 0 && my_close(fd, MYF(MY_WME))); + if (sync_log_dir >= TRANSLOG_SYNC_DIR_ALWAYS) + { + rc|= sync_dir(log_descriptor.directory_fd, MYF(MY_WME | MY_IGNORE_BADFD)); + translog_syncs++; + } + if (rc) DBUG_RETURN(1); /* fix the horizon */ @@ -3511,6 +3607,7 @@ my_bool translog_init_with_table(const c pthread_mutex_init(&log_descriptor.dirty_buffer_mask_lock, MY_MUTEX_INIT_FAST) || pthread_cond_init(&log_descriptor.log_flush_cond, 0) || + pthread_cond_init(&log_descriptor.new_goal_cond, 0) || my_rwlock_init(&log_descriptor.open_files_lock, NULL) || my_init_dynamic_array(&log_descriptor.open_files, @@ -3912,7 +4009,6 @@ my_bool translog_init_with_table(const c log_descriptor.flushed= log_descriptor.horizon; log_descriptor.in_buffers_only= log_descriptor.bc.buffer->offset; log_descriptor.max_lsn= LSN_IMPOSSIBLE; /* set to 0 */ - log_descriptor.previous_flush_horizon= log_descriptor.horizon; /* Now 'flushed' is set to 'horizon' value, but 'horizon' is (potentially) address of the next LSN and we want indicate that all LSNs that are @@ -3995,6 +4091,10 @@ my_bool translog_init_with_table(const c It is beginning of the log => there is no LSNs in the log => There is no harm in leaving it "as-is". */ + log_descriptor.previous_flush_horizon= log_descriptor.horizon; + DBUG_PRINT("info", ("previous_flush_horizon: (%lu,0x%lx)", + LSN_IN_PARTS(log_descriptor. + previous_flush_horizon))); DBUG_RETURN(0); } file_no--; @@ -4070,6 +4170,9 @@ my_bool translog_init_with_table(const c translog_free_record_header(&rec); } } + log_descriptor.previous_flush_horizon= log_descriptor.horizon; + DBUG_PRINT("info", ("previous_flush_horizon: (%lu,0x%lx)", + LSN_IN_PARTS(log_descriptor.previous_flush_horizon))); DBUG_RETURN(0); err: ma_message_no_user(0, "log initialization failed"); @@ -4157,6 +4260,7 @@ void translog_destroy() pthread_mutex_destroy(&log_descriptor.log_flush_lock); pthread_mutex_destroy(&log_descriptor.dirty_buffer_mask_lock); pthread_cond_destroy(&log_descriptor.log_flush_cond); + pthread_cond_destroy(&log_descriptor.new_goal_cond); rwlock_destroy(&log_descriptor.open_files_lock); delete_dynamic(&log_descriptor.open_files); delete_dynamic(&log_descriptor.unfinished_files); @@ -6885,11 +6989,11 @@ int translog_read_record_header_from_buf { translog_size_t res; DBUG_ENTER("translog_read_record_header_from_buffer"); + DBUG_PRINT("info", ("page byte: 0x%x offset: %u", + (uint) page[page_offset], (uint) page_offset)); DBUG_ASSERT(translog_is_LSN_chunk(page[page_offset])); DBUG_ASSERT(translog_status == TRANSLOG_OK || translog_status == TRANSLOG_READONLY); - DBUG_PRINT("info", ("page byte: 0x%x offset: %u", - (uint) page[page_offset], (uint) page_offset)); buff->type= (page[page_offset] & TRANSLOG_REC_TYPE); buff->short_trid= uint2korr(page + page_offset + 1); DBUG_PRINT("info", ("Type %u, Short TrID %u, LSN (%lu,0x%lx)", @@ -7356,27 +7460,27 @@ static void translog_force_current_buffe "Buffer addr: (%lu,0x%lx) " "Page addr: (%lu,0x%lx) " "size: %lu (%lu) Pg: %u left: %u in progress %u", - (uint) log_descriptor.bc.buffer_no, - (ulong) log_descriptor.bc.buffer, - LSN_IN_PARTS(log_descriptor.bc.buffer->offset), + (uint) old_buffer_no, + (ulong) old_buffer, + LSN_IN_PARTS(old_buffer->offset), (ulong) LSN_FILE_NO(log_descriptor.horizon), (ulong) (LSN_OFFSET(log_descriptor.horizon) - log_descriptor.bc.current_page_fill), - (ulong) log_descriptor.bc.buffer->size, + (ulong) old_buffer->size, (ulong) (log_descriptor.bc.ptr -log_descriptor.bc. buffer->buffer), (uint) log_descriptor.bc.current_page_fill, (uint) left, - (uint) log_descriptor.bc.buffer-> + (uint) old_buffer-> copy_to_buffer_in_progress)); translog_lock_assert_owner(); LINT_INIT(current_page_fill); - new_buff_beginning= log_descriptor.bc.buffer->offset; - new_buff_beginning+= log_descriptor.bc.buffer->size; /* increase offset */ + new_buff_beginning= old_buffer->offset; + new_buff_beginning+= old_buffer->size; /* increase offset */ DBUG_ASSERT(log_descriptor.bc.ptr !=NULL); DBUG_ASSERT(LSN_FILE_NO(log_descriptor.horizon) == - LSN_FILE_NO(log_descriptor.bc.buffer->offset)); + LSN_FILE_NO(old_buffer->offset)); translog_check_cursor(&log_descriptor.bc); DBUG_ASSERT(left < TRANSLOG_PAGE_SIZE); if (left) @@ -7387,18 +7491,20 @@ static void translog_force_current_buffe */ DBUG_PRINT("info", ("left: %u", (uint) left)); + old_buffer->pre_force_close_horizon= + old_buffer->offset + old_buffer->size; /* decrease offset */ new_buff_beginning-= log_descriptor.bc.current_page_fill; current_page_fill= log_descriptor.bc.current_page_fill; memset(log_descriptor.bc.ptr, TRANSLOG_FILLER, left); - log_descriptor.bc.buffer->size+= left; + old_buffer->size+= left; DBUG_PRINT("info", ("Finish Page buffer #%u: 0x%lx " "Size: %lu", - (uint) log_descriptor.bc.buffer->buffer_no, - (ulong) log_descriptor.bc.buffer, - (ulong) log_descriptor.bc.buffer->size)); - DBUG_ASSERT(log_descriptor.bc.buffer->buffer_no == + (uint) old_buffer->buffer_no, + (ulong) old_buffer, + (ulong) old_buffer->size)); + DBUG_ASSERT(old_buffer->buffer_no == log_descriptor.bc.buffer_no); } else @@ -7509,11 +7615,21 @@ static void translog_force_current_buffe if (left) { - /* - TODO: do not copy beginning of the page if we have no CRC or sector - checks on - */ - memcpy(new_buffer->buffer, data, current_page_fill); + if (log_descriptor.flags & + (TRANSLOG_PAGE_CRC | TRANSLOG_SECTOR_PROTECTION)) + memcpy(new_buffer->buffer, data, current_page_fill); + else + { + /* + This page header does not change if we add more data to the page so + we can not copy it and will not overwrite later + */ + new_buffer->skipped_data= current_page_fill; +#ifndef DBUG_OFF + memset(new_buffer->buffer, 0xa5, current_page_fill); +#endif + DBUG_ASSERT(new_buffer->skipped_data < TRANSLOG_PAGE_SIZE); + } } old_buffer->next_buffer_offset= new_buffer->offset; translog_buffer_lock(new_buffer); @@ -7561,6 +7677,7 @@ void translog_flush_set_new_goal_and_wai { log_descriptor.next_pass_max_lsn= lsn; log_descriptor.max_lsn_requester= pthread_self(); + pthread_cond_broadcast(&log_descriptor.new_goal_cond); } while (flush_no == log_descriptor.flush_no) { @@ -7572,67 +7689,79 @@ void translog_flush_set_new_goal_and_wai /** - @brief Flush the log up to given LSN (included) + @brief sync() range of files (inclusive) and directory (by request) - @param lsn log record serial number up to which (inclusive) - the log has to be flushed + @param min min internal file number to flush + @param max max internal file number to flush + @param sync_dir need sync directory - @return Operation status + return Operation status @retval 0 OK @retval 1 Error - */ -my_bool translog_flush(TRANSLOG_ADDRESS lsn) +static my_bool translog_sync_files(uint32 min, uint32 max, + my_bool sync_dir) { - LSN sent_to_disk= LSN_IMPOSSIBLE; - TRANSLOG_ADDRESS flush_horizon; - uint fn, i; - dirty_buffer_mask_t dirty_buffer_mask; - uint8 last_buffer_no, start_buffer_no; + uint fn; my_bool rc= 0; - DBUG_ENTER("translog_flush"); - DBUG_PRINT("enter", ("Flush up to LSN: (%lu,0x%lx)", LSN_IN_PARTS(lsn))); - DBUG_ASSERT(translog_status == TRANSLOG_OK || - translog_status == TRANSLOG_READONLY); - LINT_INIT(sent_to_disk); - - pthread_mutex_lock(&log_descriptor.log_flush_lock); - DBUG_PRINT("info", ("Everything is flushed up to (%lu,0x%lx)", - LSN_IN_PARTS(log_descriptor.flushed))); - if (cmp_translog_addr(log_descriptor.flushed, lsn) >= 0) + ulonglong flush_interval; + DBUG_ENTER("translog_sync_files"); + DBUG_PRINT("info", ("min: %lu max: %lu sync dir: %d", + (ulong) min, (ulong) max, (int) sync_dir)); + DBUG_ASSERT(min <= max); + + flush_interval= group_commit_wait; + if (flush_interval) + flush_start= my_micro_time(); + for (fn= min; fn <= max; fn++) { - pthread_mutex_unlock(&log_descriptor.log_flush_lock); - DBUG_RETURN(0); - } - if (log_descriptor.flush_in_progress) - { - translog_flush_set_new_goal_and_wait(lsn); - if (!pthread_equal(log_descriptor.max_lsn_requester, pthread_self())) + TRANSLOG_FILE *file= get_logfile_by_number(fn); + DBUG_ASSERT(file != NULL); + if (!file->is_sync) { - /* fix lsn if it was horizon */ - if (cmp_translog_addr(lsn, log_descriptor.bc.buffer->last_lsn) > 0) - lsn= BUFFER_MAX_LSN(log_descriptor.bc.buffer); - translog_flush_wait_for_end(lsn); - pthread_mutex_unlock(&log_descriptor.log_flush_lock); - DBUG_RETURN(0); + if (my_sync(file->handler.file, MYF(MY_WME))) + { + rc= 1; + translog_stop_writing(); + DBUG_RETURN(rc); + } + translog_syncs++; + file->is_sync= 1; } - log_descriptor.next_pass_max_lsn= LSN_IMPOSSIBLE; } - log_descriptor.flush_in_progress= 1; - flush_horizon= log_descriptor.previous_flush_horizon; - DBUG_PRINT("info", ("flush_in_progress is set")); - pthread_mutex_unlock(&log_descriptor.log_flush_lock); - translog_lock(); - if (log_descriptor.is_everything_flushed) + if (sync_dir) { - DBUG_PRINT("info", ("everything is flushed")); - rc= (translog_status == TRANSLOG_READONLY); - translog_unlock(); - goto out; + if (!(rc= sync_dir(log_descriptor.directory_fd, + MYF(MY_WME | MY_IGNORE_BADFD)))) + translog_syncs++; } + DBUG_RETURN(rc); +} + + +/* + @brief Flushes buffers with LSNs in them less or equal address <lsn> + + @param lsn address up to which all LSNs should be flushed, + can be reset to real last LSN address + @parem sent_to_disk returns 'sent to disk' position + @param flush_horizon returns horizon of the flush + + @note About terminology see comment to translog_flush(). +*/ + +void translog_flush_buffers(TRANSLOG_ADDRESS *lsn, + TRANSLOG_ADDRESS *sent_to_disk, + TRANSLOG_ADDRESS *flush_horizon) +{ + dirty_buffer_mask_t dirty_buffer_mask; + uint i; + uint8 last_buffer_no, start_buffer_no; + DBUG_ENTER("translog_flush_buffers"); + /* We will recheck information when will lock buffers one by one so we can use unprotected read here (this is just for @@ -7656,15 +7785,15 @@ my_bool translog_flush(TRANSLOG_ADDRESS /* if LSN up to which we have to flush bigger then maximum LSN of previous buffer and at least one LSN was saved in the current buffer (last_lsn != - LSN_IMPOSSIBLE) then we better finish the current buffer. + LSN_IMPOSSIBLE) then we have to close the current buffer. */ - if (cmp_translog_addr(lsn, log_descriptor.bc.buffer->prev_last_lsn) > 0 && + if (cmp_translog_addr(*lsn, log_descriptor.bc.buffer->prev_last_lsn) > 0 && log_descriptor.bc.buffer->last_lsn != LSN_IMPOSSIBLE) { struct st_translog_buffer *buffer= log_descriptor.bc.buffer; - lsn= log_descriptor.bc.buffer->last_lsn; /* fix lsn if it was horizon */ + *lsn= log_descriptor.bc.buffer->last_lsn; /* fix lsn if it was horizon */ DBUG_PRINT("info", ("LSN to flush fixed to last lsn: (%lu,0x%lx)", - LSN_IN_PARTS(log_descriptor.bc.buffer->last_lsn))); + LSN_IN_PARTS(log_descriptor.bc.buffer->last_lsn))); last_buffer_no= log_descriptor.bc.buffer_no; log_descriptor.is_everything_flushed= 1; translog_force_current_buffer_to_finish(); @@ -7676,8 +7805,10 @@ my_bool translog_flush(TRANSLOG_ADDRESS TRANSLOG_BUFFERS_NO); translog_unlock(); } - sent_to_disk= translog_get_sent_to_disk(); - if (cmp_translog_addr(lsn, sent_to_disk) > 0) + + /* flush buffers */ + *sent_to_disk= translog_get_sent_to_disk(); + if (cmp_translog_addr(*lsn, *sent_to_disk) > 0) { DBUG_PRINT("info", ("Start buffer #: %u last buffer #: %u", @@ -7697,53 +7828,237 @@ my_bool translog_flush(TRANSLOG_ADDRESS LSN_IN_PARTS(buffer->last_lsn), (buffer->file ? "dirty" : "closed"))); - if (buffer->prev_last_lsn <= lsn && + if (buffer->prev_last_lsn <= *lsn && buffer->file != NULL) { - DBUG_ASSERT(flush_horizon <= buffer->offset + buffer->size); - flush_horizon= buffer->offset + buffer->size; + DBUG_ASSERT(*flush_horizon <= buffer->offset + buffer->size); + *flush_horizon= (buffer->pre_force_close_horizon != LSN_IMPOSSIBLE ? + buffer->pre_force_close_horizon : + buffer->offset + buffer->size); + /* pre_force_close_horizon is reset during new buffer start */ + DBUG_PRINT("info", ("flush_horizon: (%lu,0x%lx)", + LSN_IN_PARTS(*flush_horizon))); + DBUG_ASSERT(*flush_horizon <= log_descriptor.horizon); + translog_buffer_flush(buffer); } translog_buffer_unlock(buffer); i= (i + 1) % TRANSLOG_BUFFERS_NO; } while (i != last_buffer_no); - sent_to_disk= translog_get_sent_to_disk(); + *sent_to_disk= translog_get_sent_to_disk(); + } + + DBUG_VOID_RETURN; +} + +/** + @brief Flush the log up to given LSN (included) + + @param lsn log record serial number up to which (inclusive) + the log has to be flushed + + @return Operation status + @retval 0 OK + @retval 1 Error + + @note + + - Non group commit logic: Commits made in passes. Thread which started + flush first is performing actual flush, other threads sets new goal (LSN) + of the next pass (if it is maximum) and waits for the pass end or just + wait for the pass end. + + - If hard group commit enabled and rate set to zero: + The first thread sends all changed buffers to disk. This is repeated + as long as there are new LSNs added. The process can not loop + forever because we have limited number of threads and they will wait + for the data to be synced. + Pseudo code: + + do + send changed buffers to disk + while new_goal + sync + + - If hard group commit switched ON and less than rate microseconds has + passed from last sync, then after buffers have been sent to disk + wait until rate microseconds has passed since last sync, do sync and return. + This ensures that if we call sync infrequently we don't do any waits. + + - If soft group commit enabled everything works as with 'non group commit' + but the thread doesn't do any real sync(). If rate is not zero the + sync() will be performed by a service thread with the given rate + when needed (new LSN appears). + + @note Terminology: + 'sent to disk' means written to disk but not sync()ed, + 'flushed' mean sent to disk and synced(). +*/ + +my_bool translog_flush(TRANSLOG_ADDRESS lsn) +{ + struct timespec abstime; + ulonglong flush_interval; + ulonglong time_spent; + LSN sent_to_disk= LSN_IMPOSSIBLE; + TRANSLOG_ADDRESS flush_horizon; + my_bool rc= 0; + my_bool hgroup_commit_at_start; + DBUG_ENTER("translog_flush"); + DBUG_PRINT("enter", ("Flush up to LSN: (%lu,0x%lx)", LSN_IN_PARTS(lsn))); + DBUG_ASSERT(translog_status == TRANSLOG_OK || + translog_status == TRANSLOG_READONLY); + LINT_INIT(sent_to_disk); + + pthread_mutex_lock(&log_descriptor.log_flush_lock); + DBUG_PRINT("info", ("Everything is flushed up to (%lu,0x%lx)", + LSN_IN_PARTS(log_descriptor.flushed))); + if (cmp_translog_addr(log_descriptor.flushed, lsn) >= 0) + + + { + pthread_mutex_unlock(&log_descriptor.log_flush_lock); + DBUG_RETURN(0); } + if (log_descriptor.flush_in_progress) + { + translog_lock(); + /* fix lsn if it was horizon */ + if (cmp_translog_addr(lsn, log_descriptor.bc.buffer->last_lsn) > 0) + lsn= BUFFER_MAX_LSN(log_descriptor.bc.buffer); + translog_unlock(); + translog_flush_set_new_goal_and_wait(lsn); + if (!pthread_equal(log_descriptor.max_lsn_requester, pthread_self())) + { + /* + translog_flush_wait_for_end() release log_flush_lock while is + waiting then acquire it again + */ + translog_flush_wait_for_end(lsn); + pthread_mutex_unlock(&log_descriptor.log_flush_lock); + DBUG_RETURN(0); + } + log_descriptor.next_pass_max_lsn= LSN_IMPOSSIBLE; + } + log_descriptor.flush_in_progress= 1; + flush_horizon= log_descriptor.previous_flush_horizon; + DBUG_PRINT("info", ("flush_in_progress is set, flush_horizon: (%lu,0x%lx)", + LSN_IN_PARTS(flush_horizon))); + pthread_mutex_unlock(&log_descriptor.log_flush_lock); + + hgroup_commit_at_start= hard_group_commit; + if (hgroup_commit_at_start) + flush_interval= group_commit_wait * TRANSLOG_RATE_BASE; - /* sync files from previous flush till current one */ - for (fn= LSN_FILE_NO(log_descriptor.flushed); fn <= LSN_FILE_NO(lsn); fn++) + translog_lock(); + if (log_descriptor.is_everything_flushed) { - TRANSLOG_FILE *file= get_logfile_by_number(fn); - DBUG_ASSERT(file != NULL); - if (!file->is_sync) + DBUG_PRINT("info", ("everything is flushed")); + translog_unlock(); + pthread_mutex_lock(&log_descriptor.log_flush_lock); + goto out; + } + + for (;;) + { + /* Following function flushes buffers and makes translog_unlock() */ + translog_flush_buffers(&lsn, &sent_to_disk, &flush_horizon); + + if (!hgroup_commit_at_start) + break; /* flush pass is ended */ + +retest: + if (flush_interval != 0 && + (my_micro_time() - flush_start) >= flush_interval) + break; /* flush pass is ended */ + + pthread_mutex_lock(&log_descriptor.log_flush_lock); + if (log_descriptor.next_pass_max_lsn != LSN_IMPOSSIBLE) + { + /* take next goal */ + lsn= log_descriptor.next_pass_max_lsn; + log_descriptor.next_pass_max_lsn= LSN_IMPOSSIBLE; + /* prevent other thread from continue */ + log_descriptor.max_lsn_requester= pthread_self(); + DBUG_PRINT("info", ("flush took next goal: (%lu,0x%lx)", + LSN_IN_PARTS(lsn))); + } + else { - if (my_sync(file->handler.file, MYF(MY_WME))) + if (flush_interval == 0 || + (time_spent= (my_micro_time() - flush_start)) >= flush_interval) { - rc= 1; - translog_stop_writing(); - sent_to_disk= LSN_IMPOSSIBLE; - goto out; + pthread_mutex_unlock(&log_descriptor.log_flush_lock); + break; } - file->is_sync= 1; + DBUG_PRINT("info", ("flush waits: %llu interval: %llu spent: %llu", + flush_interval - time_spent, + flush_interval, time_spent)); + /* wait time or next goal */ + set_timespec_nsec(abstime, flush_interval - time_spent); + pthread_cond_timedwait(&log_descriptor.new_goal_cond, + &log_descriptor.log_flush_lock, + &abstime); + pthread_mutex_unlock(&log_descriptor.log_flush_lock); + DBUG_PRINT("info", ("retest conditions")); + goto retest; } + pthread_mutex_unlock(&log_descriptor.log_flush_lock); + + /* next flush pass */ + DBUG_PRINT("info", ("next flush pass")); + translog_lock(); } - if (sync_log_dir >= TRANSLOG_SYNC_DIR_ALWAYS && - (LSN_FILE_NO(log_descriptor.previous_flush_horizon) != - LSN_FILE_NO(flush_horizon) || - ((LSN_OFFSET(log_descriptor.previous_flush_horizon) - 1) / - TRANSLOG_PAGE_SIZE) != - ((LSN_OFFSET(flush_horizon) - 1) / TRANSLOG_PAGE_SIZE))) - rc|= sync_dir(log_descriptor.directory_fd, MYF(MY_WME | MY_IGNORE_BADFD)); + /* + sync() files from previous flush till current one + */ + if (!soft_sync || hgroup_commit_at_start) + { + if ((rc= + translog_sync_files(LSN_FILE_NO(log_descriptor.flushed), + LSN_FILE_NO(lsn), + sync_log_dir >= TRANSLOG_SYNC_DIR_ALWAYS && + (LSN_FILE_NO(log_descriptor. + previous_flush_horizon) != + LSN_FILE_NO(flush_horizon) || + (LSN_OFFSET(log_descriptor. + previous_flush_horizon) / + TRANSLOG_PAGE_SIZE) != + (LSN_OFFSET(flush_horizon) / + TRANSLOG_PAGE_SIZE))))) + { + sent_to_disk= LSN_IMPOSSIBLE; + pthread_mutex_lock(&log_descriptor.log_flush_lock); + goto out; + } + /* keep values for soft sync() and forced sync() actual */ + { + uint32 fileno= LSN_FILE_NO(lsn); + my_atomic_rwlock_wrlock(&soft_sync_rwl); + my_atomic_store32(&soft_sync_min, fileno); + my_atomic_store32(&soft_sync_max, fileno); + my_atomic_rwlock_wrunlock(&soft_sync_rwl); + } + } + else + { + my_atomic_rwlock_wrlock(&soft_sync_rwl); + my_atomic_store32(&soft_sync_max, LSN_FILE_NO(lsn)); + my_atomic_rwlock_wrunlock(&soft_sync_rwl); + } + + DBUG_ASSERT(flush_horizon <= log_descriptor.horizon); + + pthread_mutex_lock(&log_descriptor.log_flush_lock); log_descriptor.previous_flush_horizon= flush_horizon; out: - pthread_mutex_lock(&log_descriptor.log_flush_lock); if (sent_to_disk != LSN_IMPOSSIBLE) log_descriptor.flushed= sent_to_disk; log_descriptor.flush_in_progress= 0; log_descriptor.flush_no++; DBUG_PRINT("info", ("flush_in_progress is dropped")); - pthread_mutex_unlock(&log_descriptor.log_flush_lock);\ + pthread_mutex_unlock(&log_descriptor.log_flush_lock); pthread_cond_broadcast(&log_descriptor.log_flush_cond); DBUG_RETURN(rc); } @@ -8113,6 +8428,8 @@ LSN translog_first_theoretical_lsn() my_bool translog_purge(TRANSLOG_ADDRESS low) { uint32 last_need_file= LSN_FILE_NO(low); + uint32 min_unsync; + int soft; TRANSLOG_ADDRESS horizon= translog_get_horizon(); int rc= 0; DBUG_ENTER("translog_purge"); @@ -8120,12 +8437,23 @@ my_bool translog_purge(TRANSLOG_ADDRESS DBUG_ASSERT(translog_status == TRANSLOG_OK || translog_status == TRANSLOG_READONLY); + soft= soft_sync; + DBUG_PRINT("info", ("min_unsync: %lu", (ulong) min_unsync)); + if (soft && min_unsync < last_need_file) + { + last_need_file= min_unsync; + DBUG_PRINT("info", ("last_need_file set to %lu", (ulong)last_need_file)); + } + pthread_mutex_lock(&log_descriptor.purger_lock); + DBUG_PRINT("info", ("last_lsn_checked file: %lu:", + (ulong) log_descriptor.last_lsn_checked)); if (LSN_FILE_NO(log_descriptor.last_lsn_checked) < last_need_file) { uint32 i; uint32 min_file= translog_first_file(horizon, 1); DBUG_ASSERT(min_file != 0); /* log is already started */ + DBUG_PRINT("info", ("min_file: %lu:",(ulong) min_file)); for(i= min_file; i < last_need_file && rc == 0; i++) { LSN lsn= translog_get_file_max_lsn_stored(i); @@ -8356,6 +8684,153 @@ my_bool translog_log_debug_info(TRN *trn } + +/** + Sets soft sync mode + + @param mode TRUE if we need switch soft sync on else off +*/ + +void translog_soft_sync(my_bool mode) +{ + soft_sync= mode; +} + + +/** + Sets hard group commit + + @param mode TRUE if we need switch hard group commit on else off +*/ + +void translog_hard_group_commit(my_bool mode) +{ + hard_group_commit= mode; +} + + +/** + @brief forced log sync (used when we are switching modes) +*/ + +void translog_sync() +{ + uint32 max= get_current_logfile()->number; + uint32 min; + DBUG_ENTER("ma_translog_sync"); + + my_atomic_rwlock_rdlock(&soft_sync_rwl); + min= my_atomic_load32(&soft_sync_min); + my_atomic_rwlock_rdunlock(&soft_sync_rwl); + if (!min) + min= max; + + translog_sync_files(min, max, sync_log_dir >= TRANSLOG_SYNC_DIR_ALWAYS); + + DBUG_VOID_RETURN; +} + + +/** + @brief set rate for group commit + + @param rate rate to set. + + @note internally it stores interval in nanoseconds/TRANSLOG_RATE_BASE (to + fit into uint32) +*/ + +void translog_set_group_commit_rate(uint32 rate) +{ + DBUG_ENTER("translog_set_group_commit_rate"); + ulonglong wait_time; + if (rate) + { + wait_time= ((TRANSLOG_RATE_BASE * 1000000000ULL / rate + + TRANSLOG_RATE_BASE / 2) / + TRANSLOG_RATE_BASE); + if (wait_time == 0) + wait_time= 1; /* protection from getting special value */ + } + else + wait_time= 0; + group_commit_wait= wait_time; + DBUG_PRINT("info", ("rate: %lu wait: %llu", + (ulong)rate, (ulonglong)wait_time)); + DBUG_VOID_RETURN; +} + + +/** + @brief syncing service thread +*/ + +static pthread_handler_t +ma_soft_sync_background( void *arg __attribute__((unused))) +{ + + my_thread_init(); + { + DBUG_ENTER("ma_soft_sync_background"); + for(;;) + { + ulonglong prev_loop= my_micro_time(); + ulonglong time, sleep; + uint32 min, max; + my_atomic_rwlock_rdlock(&soft_sync_rwl); + min= my_atomic_load32(&soft_sync_min); + max= my_atomic_load32(&soft_sync_max); + my_atomic_store32(&soft_sync_min, max); + my_atomic_rwlock_rdunlock(&soft_sync_rwl); + + sleep= group_commit_wait * TRANSLOG_RATE_BASE; + translog_sync_files(min, max, FALSE); + time= my_micro_time() - prev_loop; + if (time > sleep) + sleep= 0; + else + sleep-= time; + if (my_service_thread_sleep(&soft_sync_control, sleep)) + break; + } + my_service_thread_signal_end(&soft_sync_control); + my_thread_end(); + DBUG_RETURN(0); + } +} + + +/** + @brief Starts syncing thread +*/ + +int translog_soft_sync_start(void) +{ + pthread_t th; + int res= 0; + DBUG_ENTER("translog_soft_sync_start"); + if (!(res= ma_service_thread_control_init(&soft_sync_control))) + if (!(res= pthread_create(&th, NULL, ma_soft_sync_background, NULL))) + soft_sync_control.status= THREAD_RUNNING; + DBUG_RETURN(res); +} + + +/** + @brief Stops syncing thread +*/ + +void translog_soft_sync_end(void) +{ + DBUG_ENTER("translog_soft_sync_end"); + if (soft_sync_control.inited) + { + ma_service_thread_control_end(&soft_sync_control); + } + DBUG_VOID_RETURN; +} + + #ifdef MARIA_DUMP_LOG #include <my_getopt.h> extern void translog_example_table_init(); === modified file 'storage/maria/ma_loghandler.h' --- a/storage/maria/ma_loghandler.h 2009-01-15 22:25:53 +0000 +++ b/storage/maria/ma_loghandler.h 2009-07-07 00:37:23 +0000 @@ -342,6 +342,14 @@ enum enum_translog_status TRANSLOG_SHUTDOWN /* going to shutdown the loghandler */ }; extern enum enum_translog_status translog_status; +extern ulonglong translog_syncs; /* Number of sync()s */ + +void translog_soft_sync(my_bool mode); +void translog_hard_group_commit(my_bool mode); +int translog_soft_sync_start(void); +void translog_soft_sync_end(void); +void translog_sync(); +void translog_set_group_commit_rate(uint32 rate); /* all the rest added because of recovery; should we make @@ -441,6 +449,18 @@ extern LOG_DESC log_record_type_descript typedef enum { + TRANSLOG_GCOMMIT_NONE, + TRANSLOG_GCOMMIT_HARD, + TRANSLOG_GCOMMIT_SOFT +} enum_maria_group_commit; +extern ulong maria_group_commit; +extern ulong maria_group_commit_rate; +/** + group commit interval is TRANSLOG_RATE_BASE/<rate> seconds +*/ +#define TRANSLOG_RATE_BASE 100 +typedef enum +{ TRANSLOG_PURGE_IMMIDIATE, TRANSLOG_PURGE_EXTERNAL, TRANSLOG_PURGE_ONDEMAND

2 1

Re: [Maria-developers] Sphinx Storage engine for MariaDB
by Andrew Aksyonoff 16 Aug '09

16 Aug '09

Hello Michael, Looks like I've overlooked this email back then. :( Peter pinged me about Sphinx vs Maria status recently and I just found it. Well, hopefully better late than never! Sunday, June 7, 2009, 1:18:30 PM, you wrote: MW> Andrew, what are the possible drawbacks you can see with having MW> Sphinx to be a part of MairaDB for a user that is not using Sphinx? Can't think of any. SphinxSE is a mere client and as such does not allocate any big RAM buffers or other resources. MW> I assume that if Sphinx is not enabled, it will not take any MW> resources. MW> If Sphinx is enabled but not used, what are the resorces it would use? Pretty much none, AFAIK. --- On an unrelated note, we're working on so called RT backend here, and it will allow all the normal CRUD operations in run time (as opposed to only having reads against a static fulltext index that we have now). When it's done it'll be also technically possible to integrate it too - and do so tighter by embedding the library instead of just talking to Sphinx searchd over network. Sphinx searchd can now talk MySQL protocol and supports basic SQL syntax. So for "just" full text tasks end users don't really need the integrated version. However it still might possibly be useful in certain use cases. To keep FT index in (better) sync with DB data, avoid overheads of double network roundtrips for additional processing, avoid hassles of keeping two connections and manually managing two open transactions, etc. So I wonder what'd be your opinion about the integration - whether it seems useful at all, and if yes, whether network client or embedded library route seems better. -- Best regards, Andrew mailto:shodan@shodan.ru

5 14

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

29 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination CREATION DATE..: Sun, 10 May 2009, 19:57 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 17 (http://askmonty.org/worklog/?tid=17) VERSION........: Server-5.1 STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 1 ESTIMATE.......: 3 (hours remain) ORIG. ESTIMATE.: 3 PROGRESS NOTES: -=-=(Guest - Wed, 29 Jul 2009, 21:41)=-=- Low Level Design modified. --- /tmp/wklog.17.old.26011 2009-07-29 21:41:04.000000000 +0300 +++ /tmp/wklog.17.new.26011 2009-07-29 21:41:04.000000000 +0300 @@ -2,163 +2,146 @@ ~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 +1. Elimination criteria +2. No outside references check +2.1 Quick check if there are tables with no outside references +3. One-match check +3.1 Functional dependency source #1: Potential eq_ref access +3.2 Functional dependency source #2: col2=func(col1) +3.3 Functional dependency source #3: One or zero records in the table +3.4 Functional dependency check implementation +3.4.1 Equality collection: Option1 +3.4.2 Equality collection: Option2 +3.4.3 Functional dependency propagation - option 1 +3.4.4 Functional dependency propagation - option 2 +4. Removal operation properties +5. Removal operation +6. User interface +6.1 @@optimizer_switch flag +6.2 EXPLAIN [EXTENDED] +7. Miscellaneous adjustments +7.1 Fix used_tables() of aggregate functions +7.2 Make subquery predicates collect their outer references +8. Other concerns +8.1 Relationship with outer->inner joins converter +8.2 Relationship with prepared statements +8.3 Relationship with constant table detection +9. Tests and benchmarks </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 +1. Elimination criteria +======================= +We can eliminate inner side of an outer join nest if: + +1. There are no references to columns of the inner tables anywhere else in the query. +2. For each record combination of outer tables, it will always produce + exactly one matching record combination. + +Most of effort in this WL entry is checking these two conditions. -#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: +2. No outside references check +============================== +Criterion #1 means that the WHERE clause, ON clauses of embedding/subsequent +outer joins, ORDER BY, GROUP BY and HAVING must have no references to inner +tables of the outer join nest we're trying to remove. + +For multi-table UPDATE/DELETE we also must not remove tables that we're +updating/deleting from or tables that are used in UPDATE's SET clause. + +2.1 Quick check if there are tables with no outside references +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Before we start searching for outer join nests that could be eliminated, +we'll do a quick and cheap check if there possibly could be something that +could be eliminated: - if ((tables used in select_list | + if (there are outer joins && + (tables used in select_list | tables used in group/order by UNION | - tables used in where) != bitmap_of_all_tables) + tables used in where) != bitmap_of_all_join_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] +3. One-match check +================== +We can eliminate inner side of outer join if it will always generate exactly +one matching record combination. -* 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. +By definition of OUTER JOIN, a NULL-complemented record combination will be +generated when the inner side of outer join has not produced any matches. -* Update join->table_count and all-join-tables bitmap. +What remains to be checked is that there is no possiblity that inner side of +the outer join could produce more than one matching record combination. -* That's it. Nothing else? +We'll refer to one-match property as "functional dependency": -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. +- A outer join nest is functionally dependent [wrt outer tables] if it will + produce one matching record combination per each record combination of + outer tables -5. Tests and benchmarks ------------------------ -Create a benchmark in sql-bench which checks if the DBMS has table -elimination. -[According to Monty] Run - - queries that would use elimination - - queries that are very similar to one above (so that they would have same - QEP, execution cost, etc) but cannot use table elimination. -then compare run times and make a conclusion about whether dbms supports table -elimination. +- A table is functionally dependent wrt certain set of dependency tables, if + record combination of dependency tables uniquely identifies zero or one + matching record in the table -6. Todo, issues to resolve --------------------------- +- Definitions of functional dependency of keys (=column tuples) and columns are + apparent. -6.1 To resolve -~~~~~~~~~~~~~~ -- 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. - -* 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. +Our goal is to prove that the entire join nest is functionally-dependent. -* Aggregate functions used to report that they depend on all tables, that is, +Join nest is functionally dependent (on the otside tables) if each of its +elements (those can be either base tables or join nests) is functionally +dependent. - item_agg_func->used_tables() == (1ULL << join->tables) - 1 +Functional dependency is transitive: if table A is f-dependent on the outer +tables and table B is f.dependent on {A, outer_tables} then B is functionally +dependent on the outer tables. + +Subsequent sections list cases when we can declare a table to be +functionally-dependent. + +3.1 Functional dependency source #1: Potential eq_ref access +------------------------------------------------------------ +This is the most practically-important case. Taking the example from the HLD +of this WL entry: + + select + A.colA + from + tableA A + left outer join + tableB B + on + B.id = A.id; - always. Fixed it, now aggregate function reports it depends on - tables that its arguments depend on. In particular, COUNT(*) reports - that it depends on no tables (item_count_star->used_tables()==0). - One consequence of that is that "item->used_tables()==0" is not - equivalent to "item->const_item()==true" anymore (not sure if it's - "anymore" or this has been already happening). - -* EXPLAIN EXTENDED warning text was generated after the JOIN object has - been discarded. This didn't allow to use information about join plan - when printing the warning. Fixed this by keeping the JOIN objects until - we've printed the warning (have also an intent to remove the const - tables from the join output). - -7. Additional issues --------------------- -* We remove ON clauses within outer join nests. If these clauses contain - subqueries, they probably should be gone from EXPLAIN output also? - Yes. Current approach: when removing an outer join nest, walk the ON clause - and mark subselects as eliminated. Then let EXPLAIN code check if the - SELECT was eliminated before the printing (EXPLAIN is generated by doing - a recursive descent, so the check will also cause children of eliminated - selects not to be printed) - -* 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? - from user/EXPLAIN point of view: no. constant table is the one that we read - one record from. eliminated table is the one that we don't acccess at all. +and generalizing it: a table TBL is functionally-dependent if the ON +expression allows to construct a potential eq_ref access to table TBL that +uses only outer or functionally-dependent tables. + +In other words: table TBL will have one match if the ON expression can be +converted into this form + + TBL.unique_key=func(one_match_tables) AND .. remainder ... + +(with appropriate extension for multi-part keys), where + + one_match_tables= { + tables that are not on the inner side of the outer join in question, and + functionally dependent tables + } + +Note that this will cover constant tables, except those that are constant because +they have 0/1 record or are partitioned and have no used partitions. + + +3.2 Functional dependency source #2: col2=func(col1) +---------------------------------------------------- +This comes from the second example in the HLS: -* What is described above will not be able to eliminate this outer join create unique index idx on tableB (id, fromDate); ... left outer join @@ -169,32 +152,331 @@ B.fromDate = (select max(sub.fromDate) from tableB sub where sub.id = A.id); - This is because condition "B.fromDate= func(tableB)" cannot be used. - Reason#1: update_ref_and_keys() does not consider such conditions to - be of any use (and indeed they are not usable for ref access) - so they are not put into KEYUSE array. - Reason#2: even if they were put there, we would need to be able to tell - between predicates like - B.fromDate= func(B.id) // guarantees only one matching row as - // B.id is already bound by B.id=A.id - // hence B.fromDate becomes bound too. - and - "B.fromDate= func(B.*)" // Can potentially have many matching - // records. - We need to - - Have update_ref_and_keys() create KEYUSE elements for such equalities - - Have eliminate_tables() and friends make a more accurate check. - The right check is to check whether all parts of a unique key are bound. - If we have keypartX to be bound, then t.keypartY=func(keypartX) makes - keypartY to be bound. - The difficulty here is that correlated subquery predicate cannot tell what - columns it depends on (it only remembers tables). - Traversing the predicate is expensive and complicated. - We're leaning towards making each subquery predicate have a List<Item> with - items that - - are in the current select - - and it depends on. - This list will be useful in certain other subquery optimizations as well, - it is cheap to collect it in fix_fields() phase, so it will be collected - for every subquery predicate. +Here it is apparent that tableB can be eliminated. It is not possible to +construct eq_ref access to tableB, though, because for the second part of the +primary key (fromDate column) we only got a condition in this form: + + B.fromDate= func(tableB) + +(we write "func(tableB)" because ref optimizer can only determine which tables +the right part of the equality depends on). + +In general case, equality like this doesn't guarantee functional dependency. +For example, if func() == { return fromDate;}, i.e the ON expression is + + ... ON B.id = A.id and B.fromDate = B.fromDate + +then that would allow table B to have multiple matches per record of table A. + +In order to be able to distinguish between these two cases, we'll need to go +down to column level: + +- A table is functionally dependent if it has a unique key that's functionally + dependent + +- A unique key is functionally dependent when all of its columns are + functionally dependent + +- A table column is functionally dependent if the ON clause allows to extract + an AND-part in this form: + + tbl.column = f(functionally-dependent columns or columns of outer tables) + +3.3 Functional dependency source #3: One or zero records in the table +--------------------------------------------------------------------- +A table with one or zero records cannot generate more than one matching +record. This source is of lesser importance as one/zero-record tables are only +MyISAM tables. + +3.4 Functional dependency check implementation +---------------------------------------------- +As shown above, we need something similar to KEYUSE structures, but not +exactly that (we need things that current ref optimizer considers unusable and +don't need things that it considers usable). + +3.4.1 Equality collection: Option1 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +We could +- extend KEYUSE structures to store all kinds of equalities we need +- change update_ref_and_keys() and co. to collect equalities both for ref + access and for table elimination + = [possibly] Improve [eq_]ref access to be able to use equalities in + form keypart2=func(keypart1) +- process the KEYUSE array both by table elimination and by ref access + optimizer. + ++ This requires less effort. +- Code will have to be changed all over sql_select.cc +- update_ref_and_keys() and co. already do several unrelated things. Hooking + up table elimination will make it even worse. + +3.4.2 Equality collection: Option2 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Alternatively, we could process the WHERE clause totally on our own. ++ Table elimination is standalone and easy to detach module. +- Some code duplication with update_ref_and_keys() and co. + +Having got the equalities, we'll to propagate functional dependency property +to unique keys, tables and, ultimately, join nests. + +3.4.3 Functional dependency propagation - option 1 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Borrow the approach used in constant table detection code: + + do + { + converted= FALSE; + for each table T in join nest + { + if (check_if_functionally_dependent(T)) + converted= TRUE; + } + } while (converted == TRUE); + + check_if_functionally_dependent(T) + { + if (T has eq_ref access based on func_dep_tables) + return TRUE; + + Apply the same do-while loop-based approach to available equalities + T.column1=func(other columns) + to spread the set of functionally-dependent columns. The goal is to get + all columns of a certain unique key to be bound. + } + + +3.4.4 Functional dependency propagation - option 2 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Analyze the ON expression(s) and build a list of + + tbl.field = expr(...) + +equalities. tbl here is a table that belongs to a join nest that could +potentially be eliminated. + +besides those, add to the list + - An element for each unique key in the table that needs to be eliminated + - An element for each table that needs to be eliminated + - An element for each join nest that can be eliminated (i.e. has no + references from outside). + +Then, setup "reverse dependencies": each element should have pointers to +elements that are functionally dependent on it: + +- "tbl.field=expr(...)" equality is functionally dependent on all fields that + are used in "expr(...)" (here we take into account only fields that belong + to tables that can potentially be eliminated). +- a unique key is dependent on all of its components +- a table is dependent on all of its unique keys +- a join nest is dependent on all tables that it contains + +These pointers are stored in form of one bitmap, such that: + + "X depends on Y" == test( bitmap[(X's number)*n_objects + (Y's number)] ) + +Each object also stores a number of dependencies it needs to be satisfied +before it itself is satisfied: + +- "tbl.field=expr(...)" needs all its underlying fields (if a field is + referenced many times it is counted only once) + +- a unique key needs all of its key parts + +- a table needs only one of its unique keys + +- a join nest needs all of its tables + +(TODO: so what do we do when we've marked a table as constant? We'll need to +update the "field=expr(....)" elements that use fields of that table. And the +problem is that we won't know how much to decrement from the counters of those +elements. + +Solution#1: switch to table_map() based approach. +Solution#2: introduce separate elements for each involved field. + field will depend on its table, + "field=expr" will depend on fields. +) + +Besides the above, let each element have a pointer to another element, so that +we can have a linked list of elements. + +After the above structures have been created, we start the main algorithm. + +The first step is to create a list of functionally-dependent elements. We walk +across array of dependencies and mark those elements that are already bound +(i.e. their dependencies are satisfied). At the moment those immediately-bound +are only "field=expr" dependencies that don't refer to any columns that are +not bound. + +The second step is the loop + + while (bound_list is not empty) + { + Take the first bound element F off the list. + Use the bitmap to find out what other elements depended on it + for each such element E + { + if (E becomes bound after F is bound) + add E to the list; + } + } + +The last step is to walk through elements that represent the join nests. Those +that are bound can be eliminated. + +4. 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. + + +5. Removal operation +==================== +(This depends a lot on whether we make table elimination a one-off rewrite or +conditional) + +At the moment table elimination is re-done for each join re-execution, hence +the removal operation is designed not to modify any statement's permanent +members. + +* 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 the front of join order, 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. + ^ TODO: not true anymore ^ + +* That's it. Nothing else? + +6. User interface +================= + +6.1 @@optimizer_switch flag +--------------------------- +Argument againist adding the flag: +* It is always better to perform table elimination than not to do it. + +Arguments for the flag: +* It is always theoretically possible that the new code will cause unintended + slowdowns. +* Having the flag is useful for QA and comparative benchmarking. + +Decision so far: add the flag under #ifdef. Make the flag be present in debug +builds. + +6.2 EXPLAIN [EXTENDED] +---------------------- +There are two possible options: +1. Show eliminated tables, like we do with const tables. +2. Do not show eliminated tables. + +We chose option 2, because: +- the table is not accessed at all (besides locking it) +- it is more natural for anchor model user - when he's querying an anchor- + and attributes view, he doesn't care about the unused attributes. + +EXPLAIN EXTENDED+SHOW WARNINGS won't show the removed table either. + +NOTE: Before this WL, the warning text was generated after all JOIN objects +have been destroyed. This didn't allow to use information about join plan +when printing the warning. We've fixed this by keeping the JOIN objects until +the warning text has been generated. + +Table elimination removes inner sides of outer join, and logically the ON +clause is also removed. If this clause has any subqueries, they will be +also removed from EXPLAIN output. + +An exception to the above is that if we eliminate a derived table, it will +still be shown in EXPLAIN output. This comes from the fact that the FROM +subqueries are evaluated before table elimination is invoked. +TODO: Is the above ok or still remove parts of FROM subqueries? + +7. Miscellaneous adjustments +============================ + +7.1 Fix used_tables() of aggregate functions +-------------------------------------------- +Aggregate functions used to report that they depend on all tables, that is, + + item_agg_func->used_tables() == (1ULL << join->tables) - 1 + +always. Fixed it, now aggregate function reports that it depends on the +tables that its arguments depend on. In particular, COUNT(*) reports that it +depends on no tables (item_count_star->used_tables()==0). One consequence of +that is that "item->used_tables()==0" is not equivalent to +"item->const_item()==true" anymore (not sure if it's "anymore" or this has +been already so for some items). + +7.2 Make subquery predicates collect their outer references +----------------------------------------------------------- +Per-column functional dependency analysis requires us to take a + + tbl.field = func(...) + +equality and tell which columns of which tables are referred from func(...) +expression. For scalar expressions, this is accomplished by Item::walk()-based +traversal. It should be reasonably cheap (the only practical Item that can be +expensive to traverse seems to be a special case of "col IN (const1,const2, +...)". check if we traverse the long list for such items). + +For correlated subqueries, traversal can be expensive, it is cheaper to make +each subquery item have a list of its outer references. The list can be +collected at fix_fields() stage with very little extra cost, and then it could +be used for other optimizations. + + +8. Other concerns +================= + +8.1 Relationship with outer->inner joins converter +-------------------------------------------------- +One could suspect that outer->inner join conversion could get in the way +of table elimination by changing outer joins (which could be eliminated) +to inner (which we will not try to eliminate). +This concern is not valid: we make outer->inner conversions based on +predicates in WHERE. If the WHERE referred to an inner table (this is a +requirement for the conversion) then table elimination would not be +applicable anyway. + +8.2 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. + + +8.3 Relationship with constant table detection +---------------------------------------------- +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? +from user/EXPLAIN point of view: no. constant table is the one that we read +one record from. eliminated table is the one that we don't acccess at all. +TODO + +9. Tests and benchmarks +======================= +Create a benchmark in sql-bench which checks if the DBMS has table +elimination. +[According to Monty] Run + - query Q1 that would use elimination + - query Q2 that is very similar to Q1 (so that they would have same + QEP, execution cost, etc) but cannot use table elimination. +then compare run times and make a conclusion about whether the used dbms +supports table elimination. -=-=(Guest - Thu, 23 Jul 2009, 20:07)=-=- Dependency created: 29 now depends on 17 -=-=(Monty - Thu, 23 Jul 2009, 09:19)=-=- Version updated. --- /tmp/wklog.17.old.24090 2009-07-23 09:19:32.000000000 +0300 +++ /tmp/wklog.17.new.24090 2009-07-23 09:19:32.000000000 +0300 @@ -1 +1 @@ -Server-9.x +Server-5.1 -=-=(Guest - Mon, 20 Jul 2009, 14:28)=-=- deukje weg Worked 1 hour and estimate 3 hours remain (original estimate increased by 4 hours). -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24138 2009-07-17 02:44:49.000000000 +0300 +++ /tmp/wklog.17.new.24138 2009-07-17 02:44:49.000000000 +0300 @@ -1 +1 @@ -9.x +Server-9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-5.1 +9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Category updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-Sprint +Client-BackLog -=-=(Guest - Thu, 18 Jun 2009, 04:15)=-=- Low Level Design modified. --- /tmp/wklog.17.old.29969 2009-06-18 04:15:23.000000000 +0300 +++ /tmp/wklog.17.new.29969 2009-06-18 04:15:23.000000000 +0300 @@ -158,3 +158,43 @@ from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. +* What is described above will not be able to eliminate this outer join + create unique index idx on tableB (id, fromDate); + ... + 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); + + This is because condition "B.fromDate= func(tableB)" cannot be used. + Reason#1: update_ref_and_keys() does not consider such conditions to + be of any use (and indeed they are not usable for ref access) + so they are not put into KEYUSE array. + Reason#2: even if they were put there, we would need to be able to tell + between predicates like + B.fromDate= func(B.id) // guarantees only one matching row as + // B.id is already bound by B.id=A.id + // hence B.fromDate becomes bound too. + and + "B.fromDate= func(B.*)" // Can potentially have many matching + // records. + We need to + - Have update_ref_and_keys() create KEYUSE elements for such equalities + - Have eliminate_tables() and friends make a more accurate check. + The right check is to check whether all parts of a unique key are bound. + If we have keypartX to be bound, then t.keypartY=func(keypartX) makes + keypartY to be bound. + The difficulty here is that correlated subquery predicate cannot tell what + columns it depends on (it only remembers tables). + Traversing the predicate is expensive and complicated. + We're leaning towards making each subquery predicate have a List<Item> with + items that + - are in the current select + - and it depends on. + This list will be useful in certain other subquery optimizations as well, + it is cheap to collect it in fix_fields() phase, so it will be collected + for every subquery predicate. + -=-=(Guest - Thu, 18 Jun 2009, 02:48)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27792 2009-06-18 02:48:45.000000000 +0300 +++ /tmp/wklog.17.new.27792 2009-06-18 02:48:45.000000000 +0300 @@ -89,14 +89,14 @@ - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. +then compare run times and make a conclusion about whether dbms supports table +elimination. 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 @@ -141,8 +141,13 @@ 7. Additional issues -------------------- -* We remove ON clauses within semi-join nests. If these clauses contain +* We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? + Yes. Current approach: when removing an outer join nest, walk the ON clause + and mark subselects as eliminated. Then let EXPLAIN code check if the + SELECT was eliminated before the printing (EXPLAIN is generated by doing + a recursive descent, so the check will also cause children of eliminated + selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Thu, 18 Jun 2009, 02:24)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27162 2009-06-18 02:24:14.000000000 +0300 +++ /tmp/wklog.17.new.27162 2009-06-18 02:24:14.000000000 +0300 @@ -83,9 +83,12 @@ 5. Tests and benchmarks ----------------------- -Should create a benchmark in sql-bench which checks if the dbms has table +Create a benchmark in sql-bench which checks if the DBMS has table elimination. -TODO elaborate +[According to Monty] Run + - queries that would use elimination + - queries that are very similar to one above (so that they would have same + QEP, execution cost, etc) but cannot use table elimination. 6. Todo, issues to resolve -------------------------- @@ -109,33 +112,37 @@ 6.2 Resolved ~~~~~~~~~~~~ -- outer->inner join conversion is not a problem for table elimination. +* 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? +* 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. -* Aggregate functions report they depend on all tables, that is, +* Aggregate functions used to report that 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. + always. Fixed it, now aggregate function reports it depends on + tables that its arguments depend on. In particular, COUNT(*) reports + that it depends on no tables (item_count_star->used_tables()==0). + One consequence of that is that "item->used_tables()==0" is not + equivalent to "item->const_item()==true" anymore (not sure if it's + "anymore" or this has been already happening). + +* EXPLAIN EXTENDED warning text was generated after the JOIN object has + been discarded. This didn't allow to use information about join plan + when printing the warning. Fixed this by keeping the JOIN objects until + we've printed the warning (have also an intent to remove the const + tables from the join output). -* 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. - It turns out that - - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement - lifetime) changes. - - it is hard to have it show per-execution data. This is because the warning - text is generated after the execution structures have been destroyed. +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? * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from @@ -143,8 +150,6 @@ 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? + from user/EXPLAIN point of view: no. constant table is the one that we read + one record from. eliminated table is the one that we don't acccess at all. -* 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. ------------------------------------------------------------ -=-=(View All Progress Notes, 26 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. Elimination criteria 2. No outside references check 2.1 Quick check if there are tables with no outside references 3. One-match check 3.1 Functional dependency source #1: Potential eq_ref access 3.2 Functional dependency source #2: col2=func(col1) 3.3 Functional dependency source #3: One or zero records in the table 3.4 Functional dependency check implementation 3.4.1 Equality collection: Option1 3.4.2 Equality collection: Option2 3.4.3 Functional dependency propagation - option 1 3.4.4 Functional dependency propagation - option 2 4. Removal operation properties 5. Removal operation 6. User interface 6.1 @@optimizer_switch flag 6.2 EXPLAIN [EXTENDED] 7. Miscellaneous adjustments 7.1 Fix used_tables() of aggregate functions 7.2 Make subquery predicates collect their outer references 8. Other concerns 8.1 Relationship with outer->inner joins converter 8.2 Relationship with prepared statements 8.3 Relationship with constant table detection 9. Tests and benchmarks </contents> It's not really about elimination of tables, it's about elimination of inner sides of outer joins. 1. Elimination criteria ======================= We can eliminate inner side of an outer join nest if: 1. There are no references to columns of the inner tables anywhere else in the query. 2. For each record combination of outer tables, it will always produce exactly one matching record combination. Most of effort in this WL entry is checking these two conditions. 2. No outside references check ============================== Criterion #1 means that the WHERE clause, ON clauses of embedding/subsequent outer joins, ORDER BY, GROUP BY and HAVING must have no references to inner tables of the outer join nest we're trying to remove. For multi-table UPDATE/DELETE we also must not remove tables that we're updating/deleting from or tables that are used in UPDATE's SET clause. 2.1 Quick check if there are tables with no outside references ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Before we start searching for outer join nests that could be eliminated, we'll do a quick and cheap check if there possibly could be something that could be eliminated: if (there are outer joins && (tables used in select_list | tables used in group/order by UNION | tables used in where) != bitmap_of_all_join_tables) { attempt table elimination; } 3. One-match check ================== We can eliminate inner side of outer join if it will always generate exactly one matching record combination. By definition of OUTER JOIN, a NULL-complemented record combination will be generated when the inner side of outer join has not produced any matches. What remains to be checked is that there is no possiblity that inner side of the outer join could produce more than one matching record combination. We'll refer to one-match property as "functional dependency": - A outer join nest is functionally dependent [wrt outer tables] if it will produce one matching record combination per each record combination of outer tables - A table is functionally dependent wrt certain set of dependency tables, if record combination of dependency tables uniquely identifies zero or one matching record in the table - Definitions of functional dependency of keys (=column tuples) and columns are apparent. Our goal is to prove that the entire join nest is functionally-dependent. Join nest is functionally dependent (on the otside tables) if each of its elements (those can be either base tables or join nests) is functionally dependent. Functional dependency is transitive: if table A is f-dependent on the outer tables and table B is f.dependent on {A, outer_tables} then B is functionally dependent on the outer tables. Subsequent sections list cases when we can declare a table to be functionally-dependent. 3.1 Functional dependency source #1: Potential eq_ref access ------------------------------------------------------------ This is the most practically-important case. Taking the example from the HLD of this WL entry: select A.colA from tableA A left outer join tableB B on B.id = A.id; and generalizing it: a table TBL is functionally-dependent if the ON expression allows to construct a potential eq_ref access to table TBL that uses only outer or functionally-dependent tables. In other words: table TBL will have one match if the ON expression can be converted into this form TBL.unique_key=func(one_match_tables) AND .. remainder ... (with appropriate extension for multi-part keys), where one_match_tables= { tables that are not on the inner side of the outer join in question, and functionally dependent tables } Note that this will cover constant tables, except those that are constant because they have 0/1 record or are partitioned and have no used partitions. 3.2 Functional dependency source #2: col2=func(col1) ---------------------------------------------------- This comes from the second example in the HLS: create unique index idx on tableB (id, fromDate); ... 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); Here it is apparent that tableB can be eliminated. It is not possible to construct eq_ref access to tableB, though, because for the second part of the primary key (fromDate column) we only got a condition in this form: B.fromDate= func(tableB) (we write "func(tableB)" because ref optimizer can only determine which tables the right part of the equality depends on). In general case, equality like this doesn't guarantee functional dependency. For example, if func() == { return fromDate;}, i.e the ON expression is ... ON B.id = A.id and B.fromDate = B.fromDate then that would allow table B to have multiple matches per record of table A. In order to be able to distinguish between these two cases, we'll need to go down to column level: - A table is functionally dependent if it has a unique key that's functionally dependent - A unique key is functionally dependent when all of its columns are functionally dependent - A table column is functionally dependent if the ON clause allows to extract an AND-part in this form: tbl.column = f(functionally-dependent columns or columns of outer tables) 3.3 Functional dependency source #3: One or zero records in the table --------------------------------------------------------------------- A table with one or zero records cannot generate more than one matching record. This source is of lesser importance as one/zero-record tables are only MyISAM tables. 3.4 Functional dependency check implementation ---------------------------------------------- As shown above, we need something similar to KEYUSE structures, but not exactly that (we need things that current ref optimizer considers unusable and don't need things that it considers usable). 3.4.1 Equality collection: Option1 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ We could - extend KEYUSE structures to store all kinds of equalities we need - change update_ref_and_keys() and co. to collect equalities both for ref access and for table elimination = [possibly] Improve [eq_]ref access to be able to use equalities in form keypart2=func(keypart1) - process the KEYUSE array both by table elimination and by ref access optimizer. + This requires less effort. - Code will have to be changed all over sql_select.cc - update_ref_and_keys() and co. already do several unrelated things. Hooking up table elimination will make it even worse. 3.4.2 Equality collection: Option2 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Alternatively, we could process the WHERE clause totally on our own. + Table elimination is standalone and easy to detach module. - Some code duplication with update_ref_and_keys() and co. Having got the equalities, we'll to propagate functional dependency property to unique keys, tables and, ultimately, join nests. 3.4.3 Functional dependency propagation - option 1 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Borrow the approach used in constant table detection code: do { converted= FALSE; for each table T in join nest { if (check_if_functionally_dependent(T)) converted= TRUE; } } while (converted == TRUE); check_if_functionally_dependent(T) { if (T has eq_ref access based on func_dep_tables) return TRUE; Apply the same do-while loop-based approach to available equalities T.column1=func(other columns) to spread the set of functionally-dependent columns. The goal is to get all columns of a certain unique key to be bound. } 3.4.4 Functional dependency propagation - option 2 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Analyze the ON expression(s) and build a list of tbl.field = expr(...) equalities. tbl here is a table that belongs to a join nest that could potentially be eliminated. besides those, add to the list - An element for each unique key in the table that needs to be eliminated - An element for each table that needs to be eliminated - An element for each join nest that can be eliminated (i.e. has no references from outside). Then, setup "reverse dependencies": each element should have pointers to elements that are functionally dependent on it: - "tbl.field=expr(...)" equality is functionally dependent on all fields that are used in "expr(...)" (here we take into account only fields that belong to tables that can potentially be eliminated). - a unique key is dependent on all of its components - a table is dependent on all of its unique keys - a join nest is dependent on all tables that it contains These pointers are stored in form of one bitmap, such that: "X depends on Y" == test( bitmap[(X's number)*n_objects + (Y's number)] ) Each object also stores a number of dependencies it needs to be satisfied before it itself is satisfied: - "tbl.field=expr(...)" needs all its underlying fields (if a field is referenced many times it is counted only once) - a unique key needs all of its key parts - a table needs only one of its unique keys - a join nest needs all of its tables (TODO: so what do we do when we've marked a table as constant? We'll need to update the "field=expr(....)" elements that use fields of that table. And the problem is that we won't know how much to decrement from the counters of those elements. Solution#1: switch to table_map() based approach. Solution#2: introduce separate elements for each involved field. field will depend on its table, "field=expr" will depend on fields. ) Besides the above, let each element have a pointer to another element, so that we can have a linked list of elements. After the above structures have been created, we start the main algorithm. The first step is to create a list of functionally-dependent elements. We walk across array of dependencies and mark those elements that are already bound (i.e. their dependencies are satisfied). At the moment those immediately-bound are only "field=expr" dependencies that don't refer to any columns that are not bound. The second step is the loop while (bound_list is not empty) { Take the first bound element F off the list. Use the bitmap to find out what other elements depended on it for each such element E { if (E becomes bound after F is bound) add E to the list; } } The last step is to walk through elements that represent the join nests. Those that are bound can be eliminated. 4. 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. 5. Removal operation ==================== (This depends a lot on whether we make table elimination a one-off rewrite or conditional) At the moment table elimination is re-done for each join re-execution, hence the removal operation is designed not to modify any statement's permanent members. * 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 the front of join order, 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. ^ TODO: not true anymore ^ * That's it. Nothing else? 6. User interface ================= 6.1 @@optimizer_switch flag --------------------------- Argument againist adding the flag: * It is always better to perform table elimination than not to do it. Arguments for the flag: * It is always theoretically possible that the new code will cause unintended slowdowns. * Having the flag is useful for QA and comparative benchmarking. Decision so far: add the flag under #ifdef. Make the flag be present in debug builds. 6.2 EXPLAIN [EXTENDED] ---------------------- There are two possible options: 1. Show eliminated tables, like we do with const tables. 2. Do not show eliminated tables. We chose option 2, because: - the table is not accessed at all (besides locking it) - it is more natural for anchor model user - when he's querying an anchor- and attributes view, he doesn't care about the unused attributes. EXPLAIN EXTENDED+SHOW WARNINGS won't show the removed table either. NOTE: Before this WL, the warning text was generated after all JOIN objects have been destroyed. This didn't allow to use information about join plan when printing the warning. We've fixed this by keeping the JOIN objects until the warning text has been generated. Table elimination removes inner sides of outer join, and logically the ON clause is also removed. If this clause has any subqueries, they will be also removed from EXPLAIN output. An exception to the above is that if we eliminate a derived table, it will still be shown in EXPLAIN output. This comes from the fact that the FROM subqueries are evaluated before table elimination is invoked. TODO: Is the above ok or still remove parts of FROM subqueries? 7. Miscellaneous adjustments ============================ 7.1 Fix used_tables() of aggregate functions -------------------------------------------- Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 always. Fixed it, now aggregate function reports that it depends on the tables that its arguments depend on. In particular, COUNT(*) reports that it depends on no tables (item_count_star->used_tables()==0). One consequence of that is that "item->used_tables()==0" is not equivalent to "item->const_item()==true" anymore (not sure if it's "anymore" or this has been already so for some items). 7.2 Make subquery predicates collect their outer references ----------------------------------------------------------- Per-column functional dependency analysis requires us to take a tbl.field = func(...) equality and tell which columns of which tables are referred from func(...) expression. For scalar expressions, this is accomplished by Item::walk()-based traversal. It should be reasonably cheap (the only practical Item that can be expensive to traverse seems to be a special case of "col IN (const1,const2, ...)". check if we traverse the long list for such items). For correlated subqueries, traversal can be expensive, it is cheaper to make each subquery item have a list of its outer references. The list can be collected at fix_fields() stage with very little extra cost, and then it could be used for other optimizations. 8. Other concerns ================= 8.1 Relationship with outer->inner joins converter -------------------------------------------------- One could suspect that outer->inner join conversion could get in the way of table elimination by changing outer joins (which could be eliminated) to inner (which we will not try to eliminate). This concern is not valid: we make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (this is a requirement for the conversion) then table elimination would not be applicable anyway. 8.2 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. 8.3 Relationship with constant table detection ---------------------------------------------- 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? from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. TODO 9. Tests and benchmarks ======================= Create a benchmark in sql-bench which checks if the DBMS has table elimination. [According to Monty] Run - query Q1 that would use elimination - query Q2 that is very similar to Q1 (so that they would have same QEP, execution cost, etc) but cannot use table elimination. then compare run times and make a conclusion about whether the used dbms supports table elimination. 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 29 Jul '09

29 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination CREATION DATE..: Sun, 10 May 2009, 19:57 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 17 (http://askmonty.org/worklog/?tid=17) VERSION........: Server-5.1 STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 1 ESTIMATE.......: 3 (hours remain) ORIG. ESTIMATE.: 3 PROGRESS NOTES: -=-=(Guest - Wed, 29 Jul 2009, 21:41)=-=- Low Level Design modified. --- /tmp/wklog.17.old.26011 2009-07-29 21:41:04.000000000 +0300 +++ /tmp/wklog.17.new.26011 2009-07-29 21:41:04.000000000 +0300 @@ -2,163 +2,146 @@ ~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 +1. Elimination criteria +2. No outside references check +2.1 Quick check if there are tables with no outside references +3. One-match check +3.1 Functional dependency source #1: Potential eq_ref access +3.2 Functional dependency source #2: col2=func(col1) +3.3 Functional dependency source #3: One or zero records in the table +3.4 Functional dependency check implementation +3.4.1 Equality collection: Option1 +3.4.2 Equality collection: Option2 +3.4.3 Functional dependency propagation - option 1 +3.4.4 Functional dependency propagation - option 2 +4. Removal operation properties +5. Removal operation +6. User interface +6.1 @@optimizer_switch flag +6.2 EXPLAIN [EXTENDED] +7. Miscellaneous adjustments +7.1 Fix used_tables() of aggregate functions +7.2 Make subquery predicates collect their outer references +8. Other concerns +8.1 Relationship with outer->inner joins converter +8.2 Relationship with prepared statements +8.3 Relationship with constant table detection +9. Tests and benchmarks </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 +1. Elimination criteria +======================= +We can eliminate inner side of an outer join nest if: + +1. There are no references to columns of the inner tables anywhere else in the query. +2. For each record combination of outer tables, it will always produce + exactly one matching record combination. + +Most of effort in this WL entry is checking these two conditions. -#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: +2. No outside references check +============================== +Criterion #1 means that the WHERE clause, ON clauses of embedding/subsequent +outer joins, ORDER BY, GROUP BY and HAVING must have no references to inner +tables of the outer join nest we're trying to remove. + +For multi-table UPDATE/DELETE we also must not remove tables that we're +updating/deleting from or tables that are used in UPDATE's SET clause. + +2.1 Quick check if there are tables with no outside references +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Before we start searching for outer join nests that could be eliminated, +we'll do a quick and cheap check if there possibly could be something that +could be eliminated: - if ((tables used in select_list | + if (there are outer joins && + (tables used in select_list | tables used in group/order by UNION | - tables used in where) != bitmap_of_all_tables) + tables used in where) != bitmap_of_all_join_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] +3. One-match check +================== +We can eliminate inner side of outer join if it will always generate exactly +one matching record combination. -* 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. +By definition of OUTER JOIN, a NULL-complemented record combination will be +generated when the inner side of outer join has not produced any matches. -* Update join->table_count and all-join-tables bitmap. +What remains to be checked is that there is no possiblity that inner side of +the outer join could produce more than one matching record combination. -* That's it. Nothing else? +We'll refer to one-match property as "functional dependency": -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. +- A outer join nest is functionally dependent [wrt outer tables] if it will + produce one matching record combination per each record combination of + outer tables -5. Tests and benchmarks ------------------------ -Create a benchmark in sql-bench which checks if the DBMS has table -elimination. -[According to Monty] Run - - queries that would use elimination - - queries that are very similar to one above (so that they would have same - QEP, execution cost, etc) but cannot use table elimination. -then compare run times and make a conclusion about whether dbms supports table -elimination. +- A table is functionally dependent wrt certain set of dependency tables, if + record combination of dependency tables uniquely identifies zero or one + matching record in the table -6. Todo, issues to resolve --------------------------- +- Definitions of functional dependency of keys (=column tuples) and columns are + apparent. -6.1 To resolve -~~~~~~~~~~~~~~ -- 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. - -* 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. +Our goal is to prove that the entire join nest is functionally-dependent. -* Aggregate functions used to report that they depend on all tables, that is, +Join nest is functionally dependent (on the otside tables) if each of its +elements (those can be either base tables or join nests) is functionally +dependent. - item_agg_func->used_tables() == (1ULL << join->tables) - 1 +Functional dependency is transitive: if table A is f-dependent on the outer +tables and table B is f.dependent on {A, outer_tables} then B is functionally +dependent on the outer tables. + +Subsequent sections list cases when we can declare a table to be +functionally-dependent. + +3.1 Functional dependency source #1: Potential eq_ref access +------------------------------------------------------------ +This is the most practically-important case. Taking the example from the HLD +of this WL entry: + + select + A.colA + from + tableA A + left outer join + tableB B + on + B.id = A.id; - always. Fixed it, now aggregate function reports it depends on - tables that its arguments depend on. In particular, COUNT(*) reports - that it depends on no tables (item_count_star->used_tables()==0). - One consequence of that is that "item->used_tables()==0" is not - equivalent to "item->const_item()==true" anymore (not sure if it's - "anymore" or this has been already happening). - -* EXPLAIN EXTENDED warning text was generated after the JOIN object has - been discarded. This didn't allow to use information about join plan - when printing the warning. Fixed this by keeping the JOIN objects until - we've printed the warning (have also an intent to remove the const - tables from the join output). - -7. Additional issues --------------------- -* We remove ON clauses within outer join nests. If these clauses contain - subqueries, they probably should be gone from EXPLAIN output also? - Yes. Current approach: when removing an outer join nest, walk the ON clause - and mark subselects as eliminated. Then let EXPLAIN code check if the - SELECT was eliminated before the printing (EXPLAIN is generated by doing - a recursive descent, so the check will also cause children of eliminated - selects not to be printed) - -* 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? - from user/EXPLAIN point of view: no. constant table is the one that we read - one record from. eliminated table is the one that we don't acccess at all. +and generalizing it: a table TBL is functionally-dependent if the ON +expression allows to construct a potential eq_ref access to table TBL that +uses only outer or functionally-dependent tables. + +In other words: table TBL will have one match if the ON expression can be +converted into this form + + TBL.unique_key=func(one_match_tables) AND .. remainder ... + +(with appropriate extension for multi-part keys), where + + one_match_tables= { + tables that are not on the inner side of the outer join in question, and + functionally dependent tables + } + +Note that this will cover constant tables, except those that are constant because +they have 0/1 record or are partitioned and have no used partitions. + + +3.2 Functional dependency source #2: col2=func(col1) +---------------------------------------------------- +This comes from the second example in the HLS: -* What is described above will not be able to eliminate this outer join create unique index idx on tableB (id, fromDate); ... left outer join @@ -169,32 +152,331 @@ B.fromDate = (select max(sub.fromDate) from tableB sub where sub.id = A.id); - This is because condition "B.fromDate= func(tableB)" cannot be used. - Reason#1: update_ref_and_keys() does not consider such conditions to - be of any use (and indeed they are not usable for ref access) - so they are not put into KEYUSE array. - Reason#2: even if they were put there, we would need to be able to tell - between predicates like - B.fromDate= func(B.id) // guarantees only one matching row as - // B.id is already bound by B.id=A.id - // hence B.fromDate becomes bound too. - and - "B.fromDate= func(B.*)" // Can potentially have many matching - // records. - We need to - - Have update_ref_and_keys() create KEYUSE elements for such equalities - - Have eliminate_tables() and friends make a more accurate check. - The right check is to check whether all parts of a unique key are bound. - If we have keypartX to be bound, then t.keypartY=func(keypartX) makes - keypartY to be bound. - The difficulty here is that correlated subquery predicate cannot tell what - columns it depends on (it only remembers tables). - Traversing the predicate is expensive and complicated. - We're leaning towards making each subquery predicate have a List<Item> with - items that - - are in the current select - - and it depends on. - This list will be useful in certain other subquery optimizations as well, - it is cheap to collect it in fix_fields() phase, so it will be collected - for every subquery predicate. +Here it is apparent that tableB can be eliminated. It is not possible to +construct eq_ref access to tableB, though, because for the second part of the +primary key (fromDate column) we only got a condition in this form: + + B.fromDate= func(tableB) + +(we write "func(tableB)" because ref optimizer can only determine which tables +the right part of the equality depends on). + +In general case, equality like this doesn't guarantee functional dependency. +For example, if func() == { return fromDate;}, i.e the ON expression is + + ... ON B.id = A.id and B.fromDate = B.fromDate + +then that would allow table B to have multiple matches per record of table A. + +In order to be able to distinguish between these two cases, we'll need to go +down to column level: + +- A table is functionally dependent if it has a unique key that's functionally + dependent + +- A unique key is functionally dependent when all of its columns are + functionally dependent + +- A table column is functionally dependent if the ON clause allows to extract + an AND-part in this form: + + tbl.column = f(functionally-dependent columns or columns of outer tables) + +3.3 Functional dependency source #3: One or zero records in the table +--------------------------------------------------------------------- +A table with one or zero records cannot generate more than one matching +record. This source is of lesser importance as one/zero-record tables are only +MyISAM tables. + +3.4 Functional dependency check implementation +---------------------------------------------- +As shown above, we need something similar to KEYUSE structures, but not +exactly that (we need things that current ref optimizer considers unusable and +don't need things that it considers usable). + +3.4.1 Equality collection: Option1 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +We could +- extend KEYUSE structures to store all kinds of equalities we need +- change update_ref_and_keys() and co. to collect equalities both for ref + access and for table elimination + = [possibly] Improve [eq_]ref access to be able to use equalities in + form keypart2=func(keypart1) +- process the KEYUSE array both by table elimination and by ref access + optimizer. + ++ This requires less effort. +- Code will have to be changed all over sql_select.cc +- update_ref_and_keys() and co. already do several unrelated things. Hooking + up table elimination will make it even worse. + +3.4.2 Equality collection: Option2 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Alternatively, we could process the WHERE clause totally on our own. ++ Table elimination is standalone and easy to detach module. +- Some code duplication with update_ref_and_keys() and co. + +Having got the equalities, we'll to propagate functional dependency property +to unique keys, tables and, ultimately, join nests. + +3.4.3 Functional dependency propagation - option 1 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Borrow the approach used in constant table detection code: + + do + { + converted= FALSE; + for each table T in join nest + { + if (check_if_functionally_dependent(T)) + converted= TRUE; + } + } while (converted == TRUE); + + check_if_functionally_dependent(T) + { + if (T has eq_ref access based on func_dep_tables) + return TRUE; + + Apply the same do-while loop-based approach to available equalities + T.column1=func(other columns) + to spread the set of functionally-dependent columns. The goal is to get + all columns of a certain unique key to be bound. + } + + +3.4.4 Functional dependency propagation - option 2 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Analyze the ON expression(s) and build a list of + + tbl.field = expr(...) + +equalities. tbl here is a table that belongs to a join nest that could +potentially be eliminated. + +besides those, add to the list + - An element for each unique key in the table that needs to be eliminated + - An element for each table that needs to be eliminated + - An element for each join nest that can be eliminated (i.e. has no + references from outside). + +Then, setup "reverse dependencies": each element should have pointers to +elements that are functionally dependent on it: + +- "tbl.field=expr(...)" equality is functionally dependent on all fields that + are used in "expr(...)" (here we take into account only fields that belong + to tables that can potentially be eliminated). +- a unique key is dependent on all of its components +- a table is dependent on all of its unique keys +- a join nest is dependent on all tables that it contains + +These pointers are stored in form of one bitmap, such that: + + "X depends on Y" == test( bitmap[(X's number)*n_objects + (Y's number)] ) + +Each object also stores a number of dependencies it needs to be satisfied +before it itself is satisfied: + +- "tbl.field=expr(...)" needs all its underlying fields (if a field is + referenced many times it is counted only once) + +- a unique key needs all of its key parts + +- a table needs only one of its unique keys + +- a join nest needs all of its tables + +(TODO: so what do we do when we've marked a table as constant? We'll need to +update the "field=expr(....)" elements that use fields of that table. And the +problem is that we won't know how much to decrement from the counters of those +elements. + +Solution#1: switch to table_map() based approach. +Solution#2: introduce separate elements for each involved field. + field will depend on its table, + "field=expr" will depend on fields. +) + +Besides the above, let each element have a pointer to another element, so that +we can have a linked list of elements. + +After the above structures have been created, we start the main algorithm. + +The first step is to create a list of functionally-dependent elements. We walk +across array of dependencies and mark those elements that are already bound +(i.e. their dependencies are satisfied). At the moment those immediately-bound +are only "field=expr" dependencies that don't refer to any columns that are +not bound. + +The second step is the loop + + while (bound_list is not empty) + { + Take the first bound element F off the list. + Use the bitmap to find out what other elements depended on it + for each such element E + { + if (E becomes bound after F is bound) + add E to the list; + } + } + +The last step is to walk through elements that represent the join nests. Those +that are bound can be eliminated. + +4. 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. + + +5. Removal operation +==================== +(This depends a lot on whether we make table elimination a one-off rewrite or +conditional) + +At the moment table elimination is re-done for each join re-execution, hence +the removal operation is designed not to modify any statement's permanent +members. + +* 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 the front of join order, 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. + ^ TODO: not true anymore ^ + +* That's it. Nothing else? + +6. User interface +================= + +6.1 @@optimizer_switch flag +--------------------------- +Argument againist adding the flag: +* It is always better to perform table elimination than not to do it. + +Arguments for the flag: +* It is always theoretically possible that the new code will cause unintended + slowdowns. +* Having the flag is useful for QA and comparative benchmarking. + +Decision so far: add the flag under #ifdef. Make the flag be present in debug +builds. + +6.2 EXPLAIN [EXTENDED] +---------------------- +There are two possible options: +1. Show eliminated tables, like we do with const tables. +2. Do not show eliminated tables. + +We chose option 2, because: +- the table is not accessed at all (besides locking it) +- it is more natural for anchor model user - when he's querying an anchor- + and attributes view, he doesn't care about the unused attributes. + +EXPLAIN EXTENDED+SHOW WARNINGS won't show the removed table either. + +NOTE: Before this WL, the warning text was generated after all JOIN objects +have been destroyed. This didn't allow to use information about join plan +when printing the warning. We've fixed this by keeping the JOIN objects until +the warning text has been generated. + +Table elimination removes inner sides of outer join, and logically the ON +clause is also removed. If this clause has any subqueries, they will be +also removed from EXPLAIN output. + +An exception to the above is that if we eliminate a derived table, it will +still be shown in EXPLAIN output. This comes from the fact that the FROM +subqueries are evaluated before table elimination is invoked. +TODO: Is the above ok or still remove parts of FROM subqueries? + +7. Miscellaneous adjustments +============================ + +7.1 Fix used_tables() of aggregate functions +-------------------------------------------- +Aggregate functions used to report that they depend on all tables, that is, + + item_agg_func->used_tables() == (1ULL << join->tables) - 1 + +always. Fixed it, now aggregate function reports that it depends on the +tables that its arguments depend on. In particular, COUNT(*) reports that it +depends on no tables (item_count_star->used_tables()==0). One consequence of +that is that "item->used_tables()==0" is not equivalent to +"item->const_item()==true" anymore (not sure if it's "anymore" or this has +been already so for some items). + +7.2 Make subquery predicates collect their outer references +----------------------------------------------------------- +Per-column functional dependency analysis requires us to take a + + tbl.field = func(...) + +equality and tell which columns of which tables are referred from func(...) +expression. For scalar expressions, this is accomplished by Item::walk()-based +traversal. It should be reasonably cheap (the only practical Item that can be +expensive to traverse seems to be a special case of "col IN (const1,const2, +...)". check if we traverse the long list for such items). + +For correlated subqueries, traversal can be expensive, it is cheaper to make +each subquery item have a list of its outer references. The list can be +collected at fix_fields() stage with very little extra cost, and then it could +be used for other optimizations. + + +8. Other concerns +================= + +8.1 Relationship with outer->inner joins converter +-------------------------------------------------- +One could suspect that outer->inner join conversion could get in the way +of table elimination by changing outer joins (which could be eliminated) +to inner (which we will not try to eliminate). +This concern is not valid: we make outer->inner conversions based on +predicates in WHERE. If the WHERE referred to an inner table (this is a +requirement for the conversion) then table elimination would not be +applicable anyway. + +8.2 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. + + +8.3 Relationship with constant table detection +---------------------------------------------- +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? +from user/EXPLAIN point of view: no. constant table is the one that we read +one record from. eliminated table is the one that we don't acccess at all. +TODO + +9. Tests and benchmarks +======================= +Create a benchmark in sql-bench which checks if the DBMS has table +elimination. +[According to Monty] Run + - query Q1 that would use elimination + - query Q2 that is very similar to Q1 (so that they would have same + QEP, execution cost, etc) but cannot use table elimination. +then compare run times and make a conclusion about whether the used dbms +supports table elimination. -=-=(Guest - Thu, 23 Jul 2009, 20:07)=-=- Dependency created: 29 now depends on 17 -=-=(Monty - Thu, 23 Jul 2009, 09:19)=-=- Version updated. --- /tmp/wklog.17.old.24090 2009-07-23 09:19:32.000000000 +0300 +++ /tmp/wklog.17.new.24090 2009-07-23 09:19:32.000000000 +0300 @@ -1 +1 @@ -Server-9.x +Server-5.1 -=-=(Guest - Mon, 20 Jul 2009, 14:28)=-=- deukje weg Worked 1 hour and estimate 3 hours remain (original estimate increased by 4 hours). -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24138 2009-07-17 02:44:49.000000000 +0300 +++ /tmp/wklog.17.new.24138 2009-07-17 02:44:49.000000000 +0300 @@ -1 +1 @@ -9.x +Server-9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Version updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-5.1 +9.x -=-=(Guest - Fri, 17 Jul 2009, 02:44)=-=- Category updated. --- /tmp/wklog.17.old.24114 2009-07-17 02:44:36.000000000 +0300 +++ /tmp/wklog.17.new.24114 2009-07-17 02:44:36.000000000 +0300 @@ -1 +1 @@ -Server-Sprint +Client-BackLog -=-=(Guest - Thu, 18 Jun 2009, 04:15)=-=- Low Level Design modified. --- /tmp/wklog.17.old.29969 2009-06-18 04:15:23.000000000 +0300 +++ /tmp/wklog.17.new.29969 2009-06-18 04:15:23.000000000 +0300 @@ -158,3 +158,43 @@ from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. +* What is described above will not be able to eliminate this outer join + create unique index idx on tableB (id, fromDate); + ... + 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); + + This is because condition "B.fromDate= func(tableB)" cannot be used. + Reason#1: update_ref_and_keys() does not consider such conditions to + be of any use (and indeed they are not usable for ref access) + so they are not put into KEYUSE array. + Reason#2: even if they were put there, we would need to be able to tell + between predicates like + B.fromDate= func(B.id) // guarantees only one matching row as + // B.id is already bound by B.id=A.id + // hence B.fromDate becomes bound too. + and + "B.fromDate= func(B.*)" // Can potentially have many matching + // records. + We need to + - Have update_ref_and_keys() create KEYUSE elements for such equalities + - Have eliminate_tables() and friends make a more accurate check. + The right check is to check whether all parts of a unique key are bound. + If we have keypartX to be bound, then t.keypartY=func(keypartX) makes + keypartY to be bound. + The difficulty here is that correlated subquery predicate cannot tell what + columns it depends on (it only remembers tables). + Traversing the predicate is expensive and complicated. + We're leaning towards making each subquery predicate have a List<Item> with + items that + - are in the current select + - and it depends on. + This list will be useful in certain other subquery optimizations as well, + it is cheap to collect it in fix_fields() phase, so it will be collected + for every subquery predicate. + -=-=(Guest - Thu, 18 Jun 2009, 02:48)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27792 2009-06-18 02:48:45.000000000 +0300 +++ /tmp/wklog.17.new.27792 2009-06-18 02:48:45.000000000 +0300 @@ -89,14 +89,14 @@ - queries that would use elimination - queries that are very similar to one above (so that they would have same QEP, execution cost, etc) but cannot use table elimination. +then compare run times and make a conclusion about whether dbms supports table +elimination. 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 @@ -141,8 +141,13 @@ 7. Additional issues -------------------- -* We remove ON clauses within semi-join nests. If these clauses contain +* We remove ON clauses within outer join nests. If these clauses contain subqueries, they probably should be gone from EXPLAIN output also? + Yes. Current approach: when removing an outer join nest, walk the ON clause + and mark subselects as eliminated. Then let EXPLAIN code check if the + SELECT was eliminated before the printing (EXPLAIN is generated by doing + a recursive descent, so the check will also cause children of eliminated + selects not to be printed) * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from -=-=(Guest - Thu, 18 Jun 2009, 02:24)=-=- Low Level Design modified. --- /tmp/wklog.17.old.27162 2009-06-18 02:24:14.000000000 +0300 +++ /tmp/wklog.17.new.27162 2009-06-18 02:24:14.000000000 +0300 @@ -83,9 +83,12 @@ 5. Tests and benchmarks ----------------------- -Should create a benchmark in sql-bench which checks if the dbms has table +Create a benchmark in sql-bench which checks if the DBMS has table elimination. -TODO elaborate +[According to Monty] Run + - queries that would use elimination + - queries that are very similar to one above (so that they would have same + QEP, execution cost, etc) but cannot use table elimination. 6. Todo, issues to resolve -------------------------- @@ -109,33 +112,37 @@ 6.2 Resolved ~~~~~~~~~~~~ -- outer->inner join conversion is not a problem for table elimination. +* 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? +* 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. -* Aggregate functions report they depend on all tables, that is, +* Aggregate functions used to report that 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. + always. Fixed it, now aggregate function reports it depends on + tables that its arguments depend on. In particular, COUNT(*) reports + that it depends on no tables (item_count_star->used_tables()==0). + One consequence of that is that "item->used_tables()==0" is not + equivalent to "item->const_item()==true" anymore (not sure if it's + "anymore" or this has been already happening). + +* EXPLAIN EXTENDED warning text was generated after the JOIN object has + been discarded. This didn't allow to use information about join plan + when printing the warning. Fixed this by keeping the JOIN objects until + we've printed the warning (have also an intent to remove the const + tables from the join output). -* 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. - It turns out that - - it is easy to have EXPLAIN EXTENDED show permanent (once-per-statement - lifetime) changes. - - it is hard to have it show per-execution data. This is because the warning - text is generated after the execution structures have been destroyed. +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? * Table elimination is performed after constant table detection (but before the range analysis). Constant tables are technically different from @@ -143,8 +150,6 @@ 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? + from user/EXPLAIN point of view: no. constant table is the one that we read + one record from. eliminated table is the one that we don't acccess at all. -* 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. ------------------------------------------------------------ -=-=(View All Progress Notes, 26 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. Elimination criteria 2. No outside references check 2.1 Quick check if there are tables with no outside references 3. One-match check 3.1 Functional dependency source #1: Potential eq_ref access 3.2 Functional dependency source #2: col2=func(col1) 3.3 Functional dependency source #3: One or zero records in the table 3.4 Functional dependency check implementation 3.4.1 Equality collection: Option1 3.4.2 Equality collection: Option2 3.4.3 Functional dependency propagation - option 1 3.4.4 Functional dependency propagation - option 2 4. Removal operation properties 5. Removal operation 6. User interface 6.1 @@optimizer_switch flag 6.2 EXPLAIN [EXTENDED] 7. Miscellaneous adjustments 7.1 Fix used_tables() of aggregate functions 7.2 Make subquery predicates collect their outer references 8. Other concerns 8.1 Relationship with outer->inner joins converter 8.2 Relationship with prepared statements 8.3 Relationship with constant table detection 9. Tests and benchmarks </contents> It's not really about elimination of tables, it's about elimination of inner sides of outer joins. 1. Elimination criteria ======================= We can eliminate inner side of an outer join nest if: 1. There are no references to columns of the inner tables anywhere else in the query. 2. For each record combination of outer tables, it will always produce exactly one matching record combination. Most of effort in this WL entry is checking these two conditions. 2. No outside references check ============================== Criterion #1 means that the WHERE clause, ON clauses of embedding/subsequent outer joins, ORDER BY, GROUP BY and HAVING must have no references to inner tables of the outer join nest we're trying to remove. For multi-table UPDATE/DELETE we also must not remove tables that we're updating/deleting from or tables that are used in UPDATE's SET clause. 2.1 Quick check if there are tables with no outside references ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Before we start searching for outer join nests that could be eliminated, we'll do a quick and cheap check if there possibly could be something that could be eliminated: if (there are outer joins && (tables used in select_list | tables used in group/order by UNION | tables used in where) != bitmap_of_all_join_tables) { attempt table elimination; } 3. One-match check ================== We can eliminate inner side of outer join if it will always generate exactly one matching record combination. By definition of OUTER JOIN, a NULL-complemented record combination will be generated when the inner side of outer join has not produced any matches. What remains to be checked is that there is no possiblity that inner side of the outer join could produce more than one matching record combination. We'll refer to one-match property as "functional dependency": - A outer join nest is functionally dependent [wrt outer tables] if it will produce one matching record combination per each record combination of outer tables - A table is functionally dependent wrt certain set of dependency tables, if record combination of dependency tables uniquely identifies zero or one matching record in the table - Definitions of functional dependency of keys (=column tuples) and columns are apparent. Our goal is to prove that the entire join nest is functionally-dependent. Join nest is functionally dependent (on the otside tables) if each of its elements (those can be either base tables or join nests) is functionally dependent. Functional dependency is transitive: if table A is f-dependent on the outer tables and table B is f.dependent on {A, outer_tables} then B is functionally dependent on the outer tables. Subsequent sections list cases when we can declare a table to be functionally-dependent. 3.1 Functional dependency source #1: Potential eq_ref access ------------------------------------------------------------ This is the most practically-important case. Taking the example from the HLD of this WL entry: select A.colA from tableA A left outer join tableB B on B.id = A.id; and generalizing it: a table TBL is functionally-dependent if the ON expression allows to construct a potential eq_ref access to table TBL that uses only outer or functionally-dependent tables. In other words: table TBL will have one match if the ON expression can be converted into this form TBL.unique_key=func(one_match_tables) AND .. remainder ... (with appropriate extension for multi-part keys), where one_match_tables= { tables that are not on the inner side of the outer join in question, and functionally dependent tables } Note that this will cover constant tables, except those that are constant because they have 0/1 record or are partitioned and have no used partitions. 3.2 Functional dependency source #2: col2=func(col1) ---------------------------------------------------- This comes from the second example in the HLS: create unique index idx on tableB (id, fromDate); ... 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); Here it is apparent that tableB can be eliminated. It is not possible to construct eq_ref access to tableB, though, because for the second part of the primary key (fromDate column) we only got a condition in this form: B.fromDate= func(tableB) (we write "func(tableB)" because ref optimizer can only determine which tables the right part of the equality depends on). In general case, equality like this doesn't guarantee functional dependency. For example, if func() == { return fromDate;}, i.e the ON expression is ... ON B.id = A.id and B.fromDate = B.fromDate then that would allow table B to have multiple matches per record of table A. In order to be able to distinguish between these two cases, we'll need to go down to column level: - A table is functionally dependent if it has a unique key that's functionally dependent - A unique key is functionally dependent when all of its columns are functionally dependent - A table column is functionally dependent if the ON clause allows to extract an AND-part in this form: tbl.column = f(functionally-dependent columns or columns of outer tables) 3.3 Functional dependency source #3: One or zero records in the table --------------------------------------------------------------------- A table with one or zero records cannot generate more than one matching record. This source is of lesser importance as one/zero-record tables are only MyISAM tables. 3.4 Functional dependency check implementation ---------------------------------------------- As shown above, we need something similar to KEYUSE structures, but not exactly that (we need things that current ref optimizer considers unusable and don't need things that it considers usable). 3.4.1 Equality collection: Option1 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ We could - extend KEYUSE structures to store all kinds of equalities we need - change update_ref_and_keys() and co. to collect equalities both for ref access and for table elimination = [possibly] Improve [eq_]ref access to be able to use equalities in form keypart2=func(keypart1) - process the KEYUSE array both by table elimination and by ref access optimizer. + This requires less effort. - Code will have to be changed all over sql_select.cc - update_ref_and_keys() and co. already do several unrelated things. Hooking up table elimination will make it even worse. 3.4.2 Equality collection: Option2 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Alternatively, we could process the WHERE clause totally on our own. + Table elimination is standalone and easy to detach module. - Some code duplication with update_ref_and_keys() and co. Having got the equalities, we'll to propagate functional dependency property to unique keys, tables and, ultimately, join nests. 3.4.3 Functional dependency propagation - option 1 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Borrow the approach used in constant table detection code: do { converted= FALSE; for each table T in join nest { if (check_if_functionally_dependent(T)) converted= TRUE; } } while (converted == TRUE); check_if_functionally_dependent(T) { if (T has eq_ref access based on func_dep_tables) return TRUE; Apply the same do-while loop-based approach to available equalities T.column1=func(other columns) to spread the set of functionally-dependent columns. The goal is to get all columns of a certain unique key to be bound. } 3.4.4 Functional dependency propagation - option 2 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Analyze the ON expression(s) and build a list of tbl.field = expr(...) equalities. tbl here is a table that belongs to a join nest that could potentially be eliminated. besides those, add to the list - An element for each unique key in the table that needs to be eliminated - An element for each table that needs to be eliminated - An element for each join nest that can be eliminated (i.e. has no references from outside). Then, setup "reverse dependencies": each element should have pointers to elements that are functionally dependent on it: - "tbl.field=expr(...)" equality is functionally dependent on all fields that are used in "expr(...)" (here we take into account only fields that belong to tables that can potentially be eliminated). - a unique key is dependent on all of its components - a table is dependent on all of its unique keys - a join nest is dependent on all tables that it contains These pointers are stored in form of one bitmap, such that: "X depends on Y" == test( bitmap[(X's number)*n_objects + (Y's number)] ) Each object also stores a number of dependencies it needs to be satisfied before it itself is satisfied: - "tbl.field=expr(...)" needs all its underlying fields (if a field is referenced many times it is counted only once) - a unique key needs all of its key parts - a table needs only one of its unique keys - a join nest needs all of its tables (TODO: so what do we do when we've marked a table as constant? We'll need to update the "field=expr(....)" elements that use fields of that table. And the problem is that we won't know how much to decrement from the counters of those elements. Solution#1: switch to table_map() based approach. Solution#2: introduce separate elements for each involved field. field will depend on its table, "field=expr" will depend on fields. ) Besides the above, let each element have a pointer to another element, so that we can have a linked list of elements. After the above structures have been created, we start the main algorithm. The first step is to create a list of functionally-dependent elements. We walk across array of dependencies and mark those elements that are already bound (i.e. their dependencies are satisfied). At the moment those immediately-bound are only "field=expr" dependencies that don't refer to any columns that are not bound. The second step is the loop while (bound_list is not empty) { Take the first bound element F off the list. Use the bitmap to find out what other elements depended on it for each such element E { if (E becomes bound after F is bound) add E to the list; } } The last step is to walk through elements that represent the join nests. Those that are bound can be eliminated. 4. 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. 5. Removal operation ==================== (This depends a lot on whether we make table elimination a one-off rewrite or conditional) At the moment table elimination is re-done for each join re-execution, hence the removal operation is designed not to modify any statement's permanent members. * 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 the front of join order, 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. ^ TODO: not true anymore ^ * That's it. Nothing else? 6. User interface ================= 6.1 @@optimizer_switch flag --------------------------- Argument againist adding the flag: * It is always better to perform table elimination than not to do it. Arguments for the flag: * It is always theoretically possible that the new code will cause unintended slowdowns. * Having the flag is useful for QA and comparative benchmarking. Decision so far: add the flag under #ifdef. Make the flag be present in debug builds. 6.2 EXPLAIN [EXTENDED] ---------------------- There are two possible options: 1. Show eliminated tables, like we do with const tables. 2. Do not show eliminated tables. We chose option 2, because: - the table is not accessed at all (besides locking it) - it is more natural for anchor model user - when he's querying an anchor- and attributes view, he doesn't care about the unused attributes. EXPLAIN EXTENDED+SHOW WARNINGS won't show the removed table either. NOTE: Before this WL, the warning text was generated after all JOIN objects have been destroyed. This didn't allow to use information about join plan when printing the warning. We've fixed this by keeping the JOIN objects until the warning text has been generated. Table elimination removes inner sides of outer join, and logically the ON clause is also removed. If this clause has any subqueries, they will be also removed from EXPLAIN output. An exception to the above is that if we eliminate a derived table, it will still be shown in EXPLAIN output. This comes from the fact that the FROM subqueries are evaluated before table elimination is invoked. TODO: Is the above ok or still remove parts of FROM subqueries? 7. Miscellaneous adjustments ============================ 7.1 Fix used_tables() of aggregate functions -------------------------------------------- Aggregate functions used to report that they depend on all tables, that is, item_agg_func->used_tables() == (1ULL << join->tables) - 1 always. Fixed it, now aggregate function reports that it depends on the tables that its arguments depend on. In particular, COUNT(*) reports that it depends on no tables (item_count_star->used_tables()==0). One consequence of that is that "item->used_tables()==0" is not equivalent to "item->const_item()==true" anymore (not sure if it's "anymore" or this has been already so for some items). 7.2 Make subquery predicates collect their outer references ----------------------------------------------------------- Per-column functional dependency analysis requires us to take a tbl.field = func(...) equality and tell which columns of which tables are referred from func(...) expression. For scalar expressions, this is accomplished by Item::walk()-based traversal. It should be reasonably cheap (the only practical Item that can be expensive to traverse seems to be a special case of "col IN (const1,const2, ...)". check if we traverse the long list for such items). For correlated subqueries, traversal can be expensive, it is cheaper to make each subquery item have a list of its outer references. The list can be collected at fix_fields() stage with very little extra cost, and then it could be used for other optimizations. 8. Other concerns ================= 8.1 Relationship with outer->inner joins converter -------------------------------------------------- One could suspect that outer->inner join conversion could get in the way of table elimination by changing outer joins (which could be eliminated) to inner (which we will not try to eliminate). This concern is not valid: we make outer->inner conversions based on predicates in WHERE. If the WHERE referred to an inner table (this is a requirement for the conversion) then table elimination would not be applicable anyway. 8.2 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. 8.3 Relationship with constant table detection ---------------------------------------------- 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? from user/EXPLAIN point of view: no. constant table is the one that we read one record from. eliminated table is the one that we don't acccess at all. TODO 9. Tests and benchmarks ======================= Create a benchmark in sql-bench which checks if the DBMS has table elimination. [According to Monty] Run - query Q1 that would use elimination - query Q2 that is very similar to Q1 (so that they would have same QEP, execution cost, etc) but cannot use table elimination. then compare run times and make a conclusion about whether the used dbms supports table elimination. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Rev 2820: Apply Evgen's fix: in file:///home/psergey/dev/mysql-next-fix-subq-r2/
by Sergey Petrunya 29 Jul '09

29 Jul '09

At file:///home/psergey/dev/mysql-next-fix-subq-r2/ ------------------------------------------------------------ revno: 2820 revision-id: psergey(a)askmonty.org-20090729161849-ynumr03ety244ueu parent: psergey(a)askmonty.org-20090708174703-dz9uf5b0m6pcvtl6 committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: mysql-next-fix-subq-r2 timestamp: Wed 2009-07-29 20:18:49 +0400 message: Apply Evgen's fix: Bug#45174: Incorrectly applied equality propagation caused wrong result on a query with a materialized semi-join. Equality propagation is done after query execution plan is chosen. It substitutes fields from tables being retrieved later for fields from tables being retrieved earlier. Materialized semi-joins are exception to this rule. For field which belongs to a table within a materialized semi-join, we can only pick fields from the same semi-join. Example: suppose we have a join order: ot1 ot2 SJ-Mat(it1 it2 it3) ot3 and equality ot2.col = it1.col = it2.col If we're looking for best substitute for 'it2.col', we should pick it1.col and not ot2.col. For a field that is not in a materialized semi-join we must pick a field that's not embedded in a materialized semi-join. Example: suppose we have a join order: SJ-Mat(it1 it2) ot1 ot2 and equality ot2.col = ot1.col = it2.col If we're looking for best substitute for 'ot2.col', we should pick ot1.col and not it2.col, because when we run a join between ot1 and ot2 execution of SJ-Mat(...) has already finished and we can't rely on the value of it*.*. Now the Item_equal::get_first function accepts as a parameter a field being substituted and checks whether it belongs to a materialized semi-join. Depending on the check result a field to substitute for or NULL is returned. The is_sj_materialization_strategy method is added to the JOIN_TAB class to check whether JOIN_TAB belongs to a materialized semi-join. === modified file 'mysql-test/r/subselect3.result' --- a/mysql-test/r/subselect3.result 2009-04-30 19:37:21 +0000 +++ b/mysql-test/r/subselect3.result 2009-07-29 16:18:49 +0000 @@ -1081,8 +1081,8 @@ insert into t3 select A.a + 10*B.a, 'filler' from t0 A, t0 B; explain select * from t3 where a in (select a from t2) and (a > 5 or a < 10); id select_type table type possible_keys key key_len ref rows Extra -1 PRIMARY t2 ALL NULL NULL NULL NULL 2 Using where; Materialize; Scan -1 PRIMARY t3 ref a a 5 test.t2.a 1 +1 PRIMARY t2 ALL NULL NULL NULL NULL 2 Materialize; Scan +1 PRIMARY t3 ref a a 5 test.t2.a 1 Using index condition select * from t3 where a in (select a from t2); a filler 1 filler @@ -1129,8 +1129,8 @@ explain select * from t1, t3 where t3.a in (select a from t2) and (t3.a < 10 or t3.a >30) and t1.a =3; id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY t1 ALL NULL NULL NULL NULL 10 Using where -1 PRIMARY t2 ALL NULL NULL NULL NULL 10 Using where; Materialize; Scan -1 PRIMARY t3 ref a a 5 test.t2.a 10 +1 PRIMARY t2 ALL NULL NULL NULL NULL 10 Materialize; Scan +1 PRIMARY t3 ref a a 5 test.t2.a 10 Using index condition explain select straight_join * from t1 A, t1 B where A.a in (select a from t2); id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY A ALL NULL NULL NULL NULL 10 Using where @@ -1158,14 +1158,14 @@ explain select * from t0, t3 where t3.a in (select a from t2) and (t3.a < 10 or t3.a >30); id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY t0 system NULL NULL NULL NULL 1 -1 PRIMARY t2 ALL NULL NULL NULL NULL 10 Using where; Materialize; Scan -1 PRIMARY t3 ref a a 5 test.t2.a 10 +1 PRIMARY t2 ALL NULL NULL NULL NULL 10 Materialize; Scan +1 PRIMARY t3 ref a a 5 test.t2.a 10 Using index condition create table t4 as select a as x, a as y from t1; explain select * from t0, t3 where (t3.a, t3.b) in (select x,y from t4) and (t3.a < 10 or t3.a >30); id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY t0 system NULL NULL NULL NULL 1 -1 PRIMARY t4 ALL NULL NULL NULL NULL 10 Using where; Materialize; Scan -1 PRIMARY t3 ref a a 5 test.t4.x 10 Using where +1 PRIMARY t4 ALL NULL NULL NULL NULL 10 Materialize; Scan +1 PRIMARY t3 ref a a 5 test.t4.x 10 Using index condition; Using where drop table t0,t1,t2,t3,t4; create table t0 (a int); insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); === modified file 'mysql-test/r/subselect3_jcl6.result' --- a/mysql-test/r/subselect3_jcl6.result 2009-04-30 19:37:21 +0000 +++ b/mysql-test/r/subselect3_jcl6.result 2009-07-29 16:18:49 +0000 @@ -1086,8 +1086,8 @@ insert into t3 select A.a + 10*B.a, 'filler' from t0 A, t0 B; explain select * from t3 where a in (select a from t2) and (a > 5 or a < 10); id select_type table type possible_keys key key_len ref rows Extra -1 PRIMARY t2 ALL NULL NULL NULL NULL 2 Using where; Materialize; Scan -1 PRIMARY t3 ref a a 5 test.t2.a 1 Using join buffer +1 PRIMARY t2 ALL NULL NULL NULL NULL 2 Materialize; Scan +1 PRIMARY t3 ref a a 5 test.t2.a 1 Using index condition; Using join buffer select * from t3 where a in (select a from t2); a filler 1 filler @@ -1134,8 +1134,8 @@ explain select * from t1, t3 where t3.a in (select a from t2) and (t3.a < 10 or t3.a >30) and t1.a =3; id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY t1 ALL NULL NULL NULL NULL 10 Using where -1 PRIMARY t2 ALL NULL NULL NULL NULL 10 Using where; Materialize; Scan -1 PRIMARY t3 ref a a 5 test.t2.a 10 Using join buffer +1 PRIMARY t2 ALL NULL NULL NULL NULL 10 Materialize; Scan +1 PRIMARY t3 ref a a 5 test.t2.a 10 Using index condition; Using join buffer explain select straight_join * from t1 A, t1 B where A.a in (select a from t2); id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY A ALL NULL NULL NULL NULL 10 Using where @@ -1163,14 +1163,14 @@ explain select * from t0, t3 where t3.a in (select a from t2) and (t3.a < 10 or t3.a >30); id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY t0 system NULL NULL NULL NULL 1 -1 PRIMARY t2 ALL NULL NULL NULL NULL 10 Using where; Materialize; Scan -1 PRIMARY t3 ref a a 5 test.t2.a 10 Using join buffer +1 PRIMARY t2 ALL NULL NULL NULL NULL 10 Materialize; Scan +1 PRIMARY t3 ref a a 5 test.t2.a 10 Using index condition; Using join buffer create table t4 as select a as x, a as y from t1; explain select * from t0, t3 where (t3.a, t3.b) in (select x,y from t4) and (t3.a < 10 or t3.a >30); id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY t0 system NULL NULL NULL NULL 1 -1 PRIMARY t4 ALL NULL NULL NULL NULL 10 Using where; Materialize; Scan -1 PRIMARY t3 ref a a 5 test.t4.x 10 Using where; Using join buffer +1 PRIMARY t4 ALL NULL NULL NULL NULL 10 Materialize; Scan +1 PRIMARY t3 ref a a 5 test.t4.x 10 Using index condition; Using where; Using join buffer drop table t0,t1,t2,t3,t4; create table t0 (a int); insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); === modified file 'mysql-test/r/subselect_sj.result' --- a/mysql-test/r/subselect_sj.result 2009-07-06 07:57:39 +0000 +++ b/mysql-test/r/subselect_sj.result 2009-07-29 16:18:49 +0000 @@ -372,3 +372,39 @@ 3 2 drop table t1, t2, t3; +# +# Bug#45174: Incorrectly applied equality propagation caused wrong +# result on a query with a materialized semi-join. +# +CREATE TABLE `CC` ( +`pk` int(11) NOT NULL AUTO_INCREMENT, +`varchar_key` varchar(1) NOT NULL, +`varchar_nokey` varchar(1) NOT NULL, +PRIMARY KEY (`pk`), +KEY `varchar_key` (`varchar_key`) +); +INSERT INTO `CC` VALUES (11,'m','m'),(12,'j','j'),(13,'z','z'),(14,'a','a'),(15,'',''),(16,'e','e'),(17,'t','t'),(19,'b','b'),(20,'w','w'),(21,'m','m'),(23,'',''),(24,'w','w'),(26,'e','e'),(27,'e','e'),(28,'p','p'); +CREATE TABLE `C` ( +`varchar_nokey` varchar(1) NOT NULL +); +INSERT INTO `C` VALUES ('v'),('u'),('n'),('l'),('h'),('u'),('n'),('j'),('k'),('e'),('i'),('u'),('n'),('b'),('x'),(''),('q'),('u'); +EXPLAIN EXTENDED SELECT varchar_nokey +FROM C +WHERE ( `varchar_nokey` , `varchar_nokey` ) IN ( +SELECT `varchar_key` , `varchar_nokey` +FROM CC +WHERE `varchar_nokey` < 'n' XOR `pk` ) ; +id select_type table type possible_keys key key_len ref rows filtered Extra +1 PRIMARY C ALL NULL NULL NULL NULL 18 100.00 +1 PRIMARY CC ALL varchar_key NULL NULL NULL 15 100.00 Using where; Materialize +Warnings: +Note 1003 select `test`.`C`.`varchar_nokey` AS `varchar_nokey` from `test`.`C` semi join (`test`.`CC`) where ((`test`.`CC`.`varchar_key` = `test`.`C`.`varchar_nokey`) and (`test`.`CC`.`varchar_nokey` = `test`.`CC`.`varchar_key`) and ((`test`.`CC`.`varchar_nokey` < 'n') xor `test`.`CC`.`pk`)) +SELECT varchar_nokey +FROM C +WHERE ( `varchar_nokey` , `varchar_nokey` ) IN ( +SELECT `varchar_key` , `varchar_nokey` +FROM CC +WHERE `varchar_nokey` < 'n' XOR `pk` ) ; +varchar_nokey +DROP TABLE CC, C; +# End of the test for bug#45174. === modified file 'mysql-test/r/subselect_sj_jcl6.result' --- a/mysql-test/r/subselect_sj_jcl6.result 2009-07-06 07:57:39 +0000 +++ b/mysql-test/r/subselect_sj_jcl6.result 2009-07-29 16:18:49 +0000 @@ -376,6 +376,42 @@ 3 2 drop table t1, t2, t3; +# +# Bug#45174: Incorrectly applied equality propagation caused wrong +# result on a query with a materialized semi-join. +# +CREATE TABLE `CC` ( +`pk` int(11) NOT NULL AUTO_INCREMENT, +`varchar_key` varchar(1) NOT NULL, +`varchar_nokey` varchar(1) NOT NULL, +PRIMARY KEY (`pk`), +KEY `varchar_key` (`varchar_key`) +); +INSERT INTO `CC` VALUES (11,'m','m'),(12,'j','j'),(13,'z','z'),(14,'a','a'),(15,'',''),(16,'e','e'),(17,'t','t'),(19,'b','b'),(20,'w','w'),(21,'m','m'),(23,'',''),(24,'w','w'),(26,'e','e'),(27,'e','e'),(28,'p','p'); +CREATE TABLE `C` ( +`varchar_nokey` varchar(1) NOT NULL +); +INSERT INTO `C` VALUES ('v'),('u'),('n'),('l'),('h'),('u'),('n'),('j'),('k'),('e'),('i'),('u'),('n'),('b'),('x'),(''),('q'),('u'); +EXPLAIN EXTENDED SELECT varchar_nokey +FROM C +WHERE ( `varchar_nokey` , `varchar_nokey` ) IN ( +SELECT `varchar_key` , `varchar_nokey` +FROM CC +WHERE `varchar_nokey` < 'n' XOR `pk` ) ; +id select_type table type possible_keys key key_len ref rows filtered Extra +1 PRIMARY C ALL NULL NULL NULL NULL 18 100.00 +1 PRIMARY CC ALL varchar_key NULL NULL NULL 15 100.00 Using where; Materialize +Warnings: +Note 1003 select `test`.`C`.`varchar_nokey` AS `varchar_nokey` from `test`.`C` semi join (`test`.`CC`) where ((`test`.`CC`.`varchar_key` = `test`.`C`.`varchar_nokey`) and (`test`.`CC`.`varchar_nokey` = `test`.`CC`.`varchar_key`) and ((`test`.`CC`.`varchar_nokey` < 'n') xor `test`.`CC`.`pk`)) +SELECT varchar_nokey +FROM C +WHERE ( `varchar_nokey` , `varchar_nokey` ) IN ( +SELECT `varchar_key` , `varchar_nokey` +FROM CC +WHERE `varchar_nokey` < 'n' XOR `pk` ) ; +varchar_nokey +DROP TABLE CC, C; +# End of the test for bug#45174. set join_cache_level=default; show variables like 'join_cache_level'; Variable_name Value === modified file 'mysql-test/t/subselect_sj.test' --- a/mysql-test/t/subselect_sj.test 2009-07-06 07:57:39 +0000 +++ b/mysql-test/t/subselect_sj.test 2009-07-29 16:18:49 +0000 @@ -22,7 +22,6 @@ create table t12 like t10; insert into t12 select * from t10; - --echo Flattened because of dependency, t10=func(t1) explain select * from t1 where a in (select pk from t10); select * from t1 where a in (select pk from t10); @@ -252,3 +251,43 @@ where a in (select c from t2 where d >= some(select e from t3 where b=e)); drop table t1, t2, t3; + +--echo # +--echo # Bug#45174: Incorrectly applied equality propagation caused wrong +--echo # result on a query with a materialized semi-join. +--echo # + +CREATE TABLE `CC` ( + `pk` int(11) NOT NULL AUTO_INCREMENT, + `varchar_key` varchar(1) NOT NULL, + `varchar_nokey` varchar(1) NOT NULL, + PRIMARY KEY (`pk`), + KEY `varchar_key` (`varchar_key`) +); + +INSERT INTO `CC` VALUES (11,'m','m'),(12,'j','j'),(13,'z','z'),(14,'a','a'),(15,'',''),(16,'e','e'),(17,'t','t'),(19,'b','b'),(20,'w','w'),(21,'m','m'),(23,'',''),(24,'w','w'),(26,'e','e'),(27,'e','e'),(28,'p','p'); + +CREATE TABLE `C` ( + `varchar_nokey` varchar(1) NOT NULL +); + +INSERT INTO `C` VALUES ('v'),('u'),('n'),('l'),('h'),('u'),('n'),('j'),('k'),('e'),('i'),('u'),('n'),('b'),('x'),(''),('q'),('u'); + +EXPLAIN EXTENDED SELECT varchar_nokey +FROM C +WHERE ( `varchar_nokey` , `varchar_nokey` ) IN ( +SELECT `varchar_key` , `varchar_nokey` +FROM CC +WHERE `varchar_nokey` < 'n' XOR `pk` ) ; + +SELECT varchar_nokey +FROM C +WHERE ( `varchar_nokey` , `varchar_nokey` ) IN ( +SELECT `varchar_key` , `varchar_nokey` +FROM CC +WHERE `varchar_nokey` < 'n' XOR `pk` ) ; + +DROP TABLE CC, C; + +--echo # End of the test for bug#45174. + === modified file 'sql/item.cc' --- a/sql/item.cc 2009-07-06 07:57:39 +0000 +++ b/sql/item.cc 2009-07-29 16:18:49 +0000 @@ -4895,7 +4895,7 @@ return this; return const_item; } - Item_field *subst= item_equal->get_first(); + Item_field *subst= item_equal->get_first(this); if (subst && field->table != subst->field->table && !field->eq(subst->field)) return subst; } === modified file 'sql/item_cmpfunc.cc' --- a/sql/item_cmpfunc.cc 2009-07-06 07:57:39 +0000 +++ b/sql/item_cmpfunc.cc 2009-07-29 16:18:49 +0000 @@ -5377,7 +5377,7 @@ void Item_equal::fix_length_and_dec() { - Item *item= get_first(); + Item *item= get_first(NULL); eval_item= cmp_item::get_comparator(item->result_type(), item->collation.collation); } @@ -5440,3 +5440,107 @@ str->append(')'); } + +/* + @brief Get the first field of multiple equality. + @param[in] field the field to get equal field to + + @details Get the first field of multiple equality that is equal to the + given field. In order to make semi-join materialization strategy work + correctly we can't propagate equal fields from upper select to the semi-join. + Thus the fields is returned according to following rules: + + 1) If the given field belongs to a semi-join then the first field in + multiple equality which belong to the same semi-join is returned. + Otherwise NULL is returned. + 2) If no field is given or the field doesn't belong to a semi-join then + the first field in the multiple equality is returned. + + @retval Found first field in the multiple equality. + @retval 0 if no field found. +*/ + +Item_field* Item_equal::get_first(Item_field *field) +{ + List_iterator<Item_field> it(fields); + Item_field *item; + JOIN_TAB *field_tab; + + if (!field) + return fields.head(); + /* + Of all equal fields, return the first one we can use. Normally, this is the + field which belongs to the table that is the first in the join order. + + There is one exception to this: When semi-join materialization strategy is + used, and the given field belongs to a table within the semi-join nest, we + must pick the first field in the semi-join nest. + + Example: suppose we have a join order: + + ot1 ot2 SJ-Mat(it1 it2 it3) ot3 + + and equality ot2.col = it1.col = it2.col + If we're looking for best substitute for 'it2.col', we should pick it1.col + and not ot2.col. + */ + + field_tab= field->field->table->reginfo.join_tab; + if (field_tab->is_sj_materialization_strategy()) + { + /* + It's a field from an materialized semi-join. We can substitute it only + for a field from the same semi-join. + */ + JOIN_TAB *first; + JOIN *join= field_tab->join; + uint tab_idx= field_tab - field_tab->join->join_tab; + /* Find first table of this semi-join. */ + for (int i=tab_idx; i >= join->const_tables; i--) + { + if (join->best_positions[i].sj_strategy == SJ_OPT_MATERIALIZE || + join->best_positions[i].sj_strategy == SJ_OPT_MATERIALIZE_SCAN) + first= join->join_tab + i; + else + // Found first tab that doesn't belong to current SJ. + break; + } + /* Find an item to substitute for. */ + while ((item= it++)) + { + if (item->field->table->reginfo.join_tab >= first) + { + /* + If we found given field then return NULL to avoid unnecessary + substitution. + */ + return (item != field) ? item : NULL; + } + } + } + else + { + /* + The field is not in SJ-Materialization nest. We must return the first field + that's not embedded in a SJ-Materialization nest. + Example: suppose we have a join order: + + SJ-Mat(it1 it2) ot1 ot2 + + and equality ot2.col = ot1.col = it2.col + If we're looking for best substitute for 'ot2.col', we should pick ot1.col + and not it2.col, because when we run a join between ot1 and ot2 + execution of SJ-Mat(...) has already finished and we can't rely on the + value of it*.*. + */ + while ((item= it++)) + { + field_tab= item->field->table->reginfo.join_tab; + if (!field_tab->is_sj_materialization_strategy()) + return item; + } + } + // Shouldn't get here. + DBUG_ASSERT(0); + return NULL; +} === modified file 'sql/item_cmpfunc.h' --- a/sql/item_cmpfunc.h 2009-07-06 07:57:39 +0000 +++ b/sql/item_cmpfunc.h 2009-07-29 16:18:49 +0000 @@ -1593,7 +1593,7 @@ void add(Item_field *f); uint members(); bool contains(Field *field); - Item_field* get_first() { return fields.head(); } + Item_field* get_first(Item_field *field); void merge(Item_equal *item); void update_const(); enum Functype functype() const { return MULT_EQUAL_FUNC; } === modified file 'sql/sql_select.cc' --- a/sql/sql_select.cc 2009-07-06 14:33:29 +0000 +++ b/sql/sql_select.cc 2009-07-29 16:18:49 +0000 @@ -10379,6 +10379,21 @@ /** + Check whether the JOIN_TAB belongs to a materialized semi-join. +*/ + +bool JOIN_TAB::is_sj_materialization_strategy() +{ + uint tab_idx= this - join->join_tab; + + return (emb_sj_nest && + ((join->best_positions[tab_idx].sj_strategy == SJ_OPT_MATERIALIZE || + join->best_positions[tab_idx].sj_strategy == SJ_OPT_MATERIALIZE_SCAN))); + +} + + +/** Partially cleanup JOIN after it has executed: close index or rnd read (table cursors), free quick selects. @@ -11720,7 +11735,7 @@ head= item_const; else { - head= item_equal->get_first(); + head= item_equal->get_first(NULL); it++; } Item_field *item_field; === modified file 'sql/sql_select.h' --- a/sql/sql_select.h 2009-05-07 20:48:24 +0000 +++ b/sql/sql_select.h 2009-07-29 16:18:49 +0000 @@ -332,6 +332,7 @@ return first_inner; return first_sj_inner_tab; } + bool is_sj_materialization_strategy(); } JOIN_TAB; /*

1 0

[Maria-developers] new buildbot report at askmonty
by Bryan Alsdorf 28 Jul '09

28 Jul '09

Hi all, Last week I pushed a new report for buildbot live and after a few tweaks wanted to send out an email on it. The report is located here: http://askmonty.org/buildbot/reports/ At the moment we only have the "cross reference" report, more reports will be added in the future. The cross reference report lists all test failures matching your search (to view all data just click "search" with no parameters"). You can click on a row to display the full test failure text. Currently there are only a few test failures listed but all future failures will appear on this report. If you have any questions or comments feel free to email the list, me directly or hop on #maria Best Regards, -- Bryan Alsdorf, Lead Web Developer Monty Program, AB. http://askmonty.org

3 3

[Maria-developers] Rev 2717: WL#4800: Optimizer trace in file:///home/psergey/dev/maria-5.1-opt-trace/
by Sergey Petrunya 23 Jul '09

23 Jul '09

At file:///home/psergey/dev/maria-5.1-opt-trace/ ------------------------------------------------------------ revno: 2717 revision-id: psergey(a)askmonty.org-20090723174522-99j6if4ay9r341qg parent: knielsen(a)knielsen-hq.org-20090707111924-e44ycwmckomk13qz committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-opt-trace timestamp: Thu 2009-07-23 21:45:22 +0400 message: WL#4800: Optimizer trace - Port current state to MariaDB Diff too large for email (1909 lines, the limit is 1000).

1 0

[Maria-developers] Rev 2717: WL#4800: Optimizer trace in file:///home/psergey/dev/maria-5.1-opt-trace/
by Sergey Petrunya 23 Jul '09

23 Jul '09

At file:///home/psergey/dev/maria-5.1-opt-trace/ ------------------------------------------------------------ revno: 2717 revision-id: psergey(a)askmonty.org-20090723174047-982pmyty704c5bgu parent: knielsen(a)knielsen-hq.org-20090707111924-e44ycwmckomk13qz committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-opt-trace timestamp: Thu 2009-07-23 21:40:47 +0400 message: WL#4800: Optimizer trace - Port of current state to mariadb-5.1 Diff too large for email (1354 lines, the limit is 1000).

1 0

[Maria-developers] Updated (by Guest): Table elimination: all tasks (29)
by worklog-noreply＠askmonty.org 23 Jul '09

23 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination: all tasks CREATION DATE..: Wed, 03 Jun 2009, 12:07 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Psergey CATEGORY.......: Server-Sprint TASK ID........: 29 (http://askmonty.org/worklog/?tid=29) VERSION........: Server-5.1 STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Thu, 23 Jul 2009, 20:13)=-=- Version updated. --- /tmp/wklog.29.old.17550 2009-07-23 20:13:44.000000000 +0300 +++ /tmp/wklog.29.new.17550 2009-07-23 20:13:44.000000000 +0300 @@ -1 +1 @@ -Server-4.0 +Server-5.1 -=-=(Guest - Thu, 23 Jul 2009, 20:09)=-=- Version updated. --- /tmp/wklog.29.old.17326 2009-07-23 20:09:38.000000000 +0300 +++ /tmp/wklog.29.new.17326 2009-07-23 20:09:38.000000000 +0300 @@ -1 +1 @@ -Server-9.x +Server-4.0 -=-=(Guest - Thu, 23 Jul 2009, 20:07)=-=- Dependency created: 29 now depends on 17 -=-=(Guest - Tue, 16 Jun 2009, 17:03)=-=- Dependency deleted: 29 no longer depends on 20 -=-=(Guest - Tue, 16 Jun 2009, 17:01)=-=- Dependency deleted: 29 no longer depends on 17 -=-=(Psergey - Wed, 03 Jun 2009, 12:07)=-=- Dependency created: 29 now depends on 20 -=-=(Psergey - Wed, 03 Jun 2009, 12:07)=-=- Dependency created: 29 now depends on 17 DESCRIPTION: This WL entry groups all table elimination tasks. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Table elimination: all tasks (29)
by worklog-noreply＠askmonty.org 23 Jul '09

23 Jul '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Table elimination: all tasks CREATION DATE..: Wed, 03 Jun 2009, 12:07 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Psergey CATEGORY.......: Server-Sprint TASK ID........: 29 (http://askmonty.org/worklog/?tid=29) VERSION........: Server-5.1 STATUS.........: In-Progress PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Thu, 23 Jul 2009, 20:13)=-=- Version updated. --- /tmp/wklog.29.old.17550 2009-07-23 20:13:44.000000000 +0300 +++ /tmp/wklog.29.new.17550 2009-07-23 20:13:44.000000000 +0300 @@ -1 +1 @@ -Server-4.0 +Server-5.1 -=-=(Guest - Thu, 23 Jul 2009, 20:09)=-=- Version updated. --- /tmp/wklog.29.old.17326 2009-07-23 20:09:38.000000000 +0300 +++ /tmp/wklog.29.new.17326 2009-07-23 20:09:38.000000000 +0300 @@ -1 +1 @@ -Server-9.x +Server-4.0 -=-=(Guest - Thu, 23 Jul 2009, 20:07)=-=- Dependency created: 29 now depends on 17 -=-=(Guest - Tue, 16 Jun 2009, 17:03)=-=- Dependency deleted: 29 no longer depends on 20 -=-=(Guest - Tue, 16 Jun 2009, 17:01)=-=- Dependency deleted: 29 no longer depends on 17 -=-=(Psergey - Wed, 03 Jun 2009, 12:07)=-=- Dependency created: 29 now depends on 20 -=-=(Psergey - Wed, 03 Jun 2009, 12:07)=-=- Dependency created: 29 now depends on 17 DESCRIPTION: This WL entry groups all table elimination tasks. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0