From: Roy Lyseng Date: March 15 2011 1:14pm Subject: bzr commit into mysql-trunk branch (roy.lyseng:3348) Bug#11822517 List-Archive: http://lists.mysql.com/commits/133023 X-Bug: 11822517 Message-Id: <20110315131423.81AD31F3@tyr67.norway.sun.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============2470732202464350484==" --===============2470732202464350484== MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Content-Disposition: inline #At file:///home/rl136806/mysql/repo/mysql-work5/ based on revid:roy.lyseng@stripped 3348 Roy Lyseng 2011-03-15 Bug#11822517: Refactor call interface of choose_plan() The main purposes of this patch is 1. Make the interface of choose_plan() and greedy_search() simpler. 2. Prepare for a simpler test for dependencies when doing semi join materialization together with outer join (WL#5561). The fix involves replacing the join_tables argument to choose_plan() with a join nest pointer, which is NULL when the entire query will be optimized. Thus, the set of relevant tables is instead calculated inside this function. We also clarify that we need to pass as remaining_tables to best_access_path() not only the tables remaining to be optimized, but also all tables outside of the current semi join nest. sql/sql_select.cc optimize_semijoin_nests() is now taking the map of all query tables from the passed JOIN object instead of an argument. best_access_path() - meaning of argument remaining_tables is changed so that it actually is interpreted as all tables not added to the current partial plan. choose_plan() - argument join_tables is replaced with sjm_nest - pointer to semi join nest to generate a plan for. The tables to include in the plan is calculated inside the function instead. greedy_search() - now calling best_access_path() with all tables not included in the current partial plan. Not calling advance_sj_state() when calculating plan for a materialized semi join nest. sql/sql_select.h Added all_table_map (map of tables in query) to JOIN object. Commented const_table_map, found_const_table_map and outer_join modified: sql/sql_select.cc sql/sql_select.h === modified file 'sql/sql_select.cc' --- a/sql/sql_select.cc 2011-03-03 09:43:14 +0000 +++ b/sql/sql_select.cc 2011-03-15 13:13:54 +0000 @@ -66,7 +66,7 @@ struct st_sargable_param; static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array); static bool make_join_statistics(JOIN *join, TABLE_LIST *leaves, Item *conds, DYNAMIC_ARRAY *keyuse); -static bool optimize_semijoin_nests(JOIN *join, table_map all_table_map); +static bool optimize_semijoin_nests(JOIN *join); static bool update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse, JOIN_TAB *join_tab, uint tables, Item *conds, @@ -77,7 +77,7 @@ static int sort_keyuse(Key_use *a, Key_u static void set_position(JOIN *join, uint index, JOIN_TAB *table, Key_use *key); static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, Key_use *org_keyuse, table_map used_tables); -static bool choose_plan(JOIN *join, table_map join_tables); +static bool choose_plan(JOIN *join, TABLE_LIST *sjm_nest); static void best_access_path(JOIN *join, JOIN_TAB *s, table_map remaining_tables, uint idx, bool disable_jbuf, double record_count, @@ -4609,7 +4609,7 @@ make_join_statistics(JOIN *join, TABLE_L TABLE *table; TABLE_LIST *tables= tables_arg; uint i,table_count,const_count,key; - table_map found_const_table_map, all_table_map, found_ref, refs; + table_map found_const_table_map, found_ref, refs; TABLE **table_vector; JOIN_TAB *stat,*stat_end,*s,**stat_ref; Key_use *keyuse, *start_keyuse; @@ -4636,7 +4636,8 @@ make_join_statistics(JOIN *join, TABLE_L join->best_ref=stat_vector; stat_end=stat+table_count; - found_const_table_map= all_table_map=0; + found_const_table_map=0; + join->all_table_map= 0; const_count=0; for (s= stat, i= 0; @@ -4656,7 +4657,7 @@ make_join_statistics(JOIN *join, TABLE_L table->reginfo.join_tab=s; table->reginfo.not_exists_optimize=0; bzero((char*) table->const_key_parts, sizeof(key_part_map)*table->s->keys); - all_table_map|= table->map; + join->all_table_map|= table->map; s->join=join; s->dependent= tables->dep_tables; @@ -5082,13 +5083,13 @@ make_join_statistics(JOIN *join, TABLE_L if (join->const_tables != join->tables) optimize_keyuse(join, keyuse_array); - if (optimize_semijoin_nests(join, all_table_map)) + if (optimize_semijoin_nests(join)) DBUG_RETURN(TRUE); /* purecov: inspected */ /* Find an optimal join order of the non-constant tables. */ if (join->const_tables != join->tables) { - if (choose_plan(join, all_table_map & ~join->const_table_map)) + if (choose_plan(join, NULL)) goto error; } else @@ -5120,7 +5121,6 @@ error: SYNOPSIS optimize_semijoin_nests() join The join to optimize semi-join nests for - all_table_map Bitmap of all tables in the join DESCRIPTION Optimize each of the semi-join nests that can be run with @@ -5139,7 +5139,7 @@ error: TRUE Out of memory error */ -static bool optimize_semijoin_nests(JOIN *join, table_map all_table_map) +static bool optimize_semijoin_nests(JOIN *join) { DBUG_ENTER("optimize_semijoin_nests"); List_iterator sj_list_it(join->select_lex->sj_nests); @@ -5168,8 +5168,7 @@ static bool optimize_semijoin_nests(JOIN */ if (semijoin_types_allow_materialization(sj_nest)) { - join->emb_sjm_nest= sj_nest; - if (choose_plan(join, all_table_map & ~join->const_table_map)) + if (choose_plan(join, sj_nest)) DBUG_RETURN(TRUE); /* purecov: inspected */ /* The best plan to run the subquery is now in join->best_positions, @@ -5258,7 +5257,6 @@ static bool optimize_semijoin_nests(JOIN } } } - join->emb_sjm_nest= NULL; DBUG_RETURN(FALSE); } @@ -6927,11 +6925,18 @@ public: 'join->positions' of length 'idx'. The chosen access method for 's' and its cost are stored in 'join->positions[idx]'. + Notice also that when calculating a plan for a materialized semi join nest, + this function must not consider key references between tables inside the + semi join nest and those outside of it. The way to control this is to add + the set of outside tables to the @c remaining_tables argument. + @param join pointer to the structure providing all context info for the query @param s the table to be joined by the function @param thd thread for the connection that submitted the query - @param remaining_tables set of tables not included into the partial plan yet + @param remaining_tables set of tables not included into the partial plan yet. + also tables outside of the join nest when calculating + a materialized semi join nest. @param idx the length of the partial plan @param disable_jbuf TRUE<=> Don't use join buffering @param record_count estimate for the number of records returned by the @@ -7526,10 +7531,15 @@ best_access_path(JOIN *join, it. Each specific optimization procedure stores the final optimal plan in the array 'join->best_positions', and the cost of the plan in 'join->best_read'. - - @param join pointer to the structure providing all context info for - the query - @param join_tables set of the tables in the query + The function can be invoked to produce a plan for all tables in the query + (in this case, the const tables are usually filtered out), or it can be + invoked to produce a plan for a materialization of a semi join nest. + Call with non-NULL sjm_nest pointer when producing a plan for a semi join + nest to be materialized and a NULL pointer when producing a full query plan. + + @param join pointer to structure providing all context info for query + @param sjm_nest semi join nest that we are producing plan for, or NULL + which means produce plan for full query. @retval FALSE ok @@ -7537,24 +7547,31 @@ best_access_path(JOIN *join, TRUE Fatal error */ -static bool -choose_plan(JOIN *join, table_map join_tables) +static bool choose_plan(JOIN *join, TABLE_LIST *sjm_nest) { uint search_depth= join->thd->variables.optimizer_search_depth; uint prune_level= join->thd->variables.optimizer_prune_level; bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN); + table_map join_tables; DBUG_ENTER("choose_plan"); + join->emb_sjm_nest= sjm_nest; join->cur_embedding_map= 0; reset_nj_counters(join->join_list); qsort2_cmp jtab_sort_func; - if (join->emb_sjm_nest) + if (sjm_nest) { /* We're optimizing semi-join materialization nest, so put the tables from this semi-join as first */ jtab_sort_func= join_tab_cmp_embedded_first; + join_tables= sjm_nest->sj_inner_tables; + /* + Inner tables of semi join nest are not allowed to be identified as + const tables. + */ + DBUG_ASSERT(join_tables == (join_tables & ~join->const_table_map)); } else { @@ -7567,6 +7584,7 @@ choose_plan(JOIN *join, table_map join_t records accessed. */ jtab_sort_func= straight_join ? join_tab_cmp_straight : join_tab_cmp; + join_tables= join->all_table_map & ~join->const_table_map; } my_qsort2(join->best_ref + join->const_tables, join->tables - join->const_tables, sizeof(JOIN_TAB*), @@ -7594,6 +7612,9 @@ choose_plan(JOIN *join, table_map join_t */ if (join->thd->lex->is_single_level_stmt()) join->thd->status_var.last_query_cost= join->best_read; + + join->emb_sjm_nest= NULL; + DBUG_RETURN(FALSE); } @@ -7986,16 +8007,14 @@ greedy_search(JOIN *join, DBUG_ENTER("greedy_search"); /* number of tables that remain to be optimized */ - n_tables= size_remain= my_count_bits(remaining_tables & - (join->emb_sjm_nest? - join->emb_sjm_nest->sj_inner_tables : - ~(table_map)0)); + n_tables= size_remain= my_count_bits(remaining_tables); do { /* Find the extension of the current QEP with the lowest cost */ join->best_read= DBL_MAX; - if (best_extension_by_limited_search(join, remaining_tables, idx, record_count, - read_time, search_depth, prune_level)) + if (best_extension_by_limited_search(join, remaining_tables, idx, + record_count, read_time, + search_depth, prune_level)) DBUG_RETURN(TRUE); /* 'best_read < DBL_MAX' means that optimizer managed to find @@ -8242,18 +8261,25 @@ best_extension_by_limited_search(JOIN DBUG_EXECUTE("opt", print_plan(join, idx, record_count, read_time, read_time, "part_plan");); + /* + When calculating a plan for a materialized semi join nest, + best_access_plan() needs to know not only the remaining tables within the + join nest, but also all tables outside of this nest, because there may + be key references between the semi join nest and the outside tables + that should not be considered when materializing the semi join nest. + */ + const table_map excluded_tables= + join->emb_sjm_nest ? + join->all_table_map & ~join->emb_sjm_nest->sj_inner_tables : + 0; - table_map allowed_tables= ~(table_map)0; - if (join->emb_sjm_nest) - allowed_tables= join->emb_sjm_nest->sj_inner_tables; - - bool has_sj= !join->select_lex->sj_nests.is_empty(); + const bool has_sj= + !(join->select_lex->sj_nests.is_empty() || join->emb_sjm_nest); for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++) { table_map real_table_bit= s->table->map; if ((remaining_tables & real_table_bit) && - (allowed_tables & real_table_bit) && !(remaining_tables & s->dependent) && (!idx || !check_interleaving_with_nj(s))) { @@ -8262,7 +8288,8 @@ best_extension_by_limited_search(JOIN /* Find the best access method from 's' to the current partial plan */ POSITION loose_scan_pos; - best_access_path(join, s, remaining_tables, idx, FALSE, record_count, + best_access_path(join, s, excluded_tables | remaining_tables, + idx, FALSE, record_count, join->positions + idx, &loose_scan_pos); /* Compute the cost of extending the plan with 's' */ @@ -8277,6 +8304,8 @@ best_extension_by_limited_search(JOIN cost (takes 9% of time in a 20-table plan search), hence the if() above, which is also more efficient than the same if() inside advance_sj_state() would be. + Besides, never call advance_sj_state() when calculating the plan + for a materialized semi join nest. */ advance_sj_state(join, remaining_tables, s, idx, ¤t_record_count, ¤t_read_time, @@ -8333,7 +8362,7 @@ best_extension_by_limited_search(JOIN } } - if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) & allowed_tables ) + if (search_depth > 1 && (remaining_tables & ~real_table_bit)) { /* Recursively expand the current partial plan */ swap_variables(JOIN_TAB*, join->best_ref[idx], *pos); if (best_extension_by_limited_search(join, @@ -13932,6 +13961,15 @@ void advance_sj_state(JOIN *join, table_ TABLE_LIST *emb_sj_nest= new_join_tab->emb_sj_nest; POSITION *pos= join->positions + idx; + /* + Semi join nests cannot be nested, hence we never need to advance the + semi join state of a materialized semi join query. + In fact, doing this may cause undesirable effects because all tables + within a semi join nest have emb_sj_nest |= NULL, which triggers several + of the actions inside this function. + */ + DBUG_ASSERT(join->emb_sjm_nest == NULL); + /* Add this table to the join prefix */ remaining_tables &= ~new_join_tab->table->map; === modified file 'sql/sql_select.h' --- a/sql/sql_select.h 2011-03-01 14:57:53 +0000 +++ b/sql/sql_select.h 2011-03-15 13:13:54 +0000 @@ -1640,11 +1640,10 @@ public: bool first_record,full_join, no_field_update; bool group; /**< If query contains GROUP BY clause */ bool do_send_rows; - table_map const_table_map,found_const_table_map; - /* - Bitmap of all inner tables from outer joins - */ - table_map outer_join; + table_map all_table_map; /**< Set of tables contained in query */ + table_map const_table_map; /**< Set of tables found to be const */ + table_map found_const_table_map; /**< Tables that are const and non-empty */ + table_map outer_join; /**< Bitmap of all inner tables from outer joins */ /* Number of records produced after join + group operation */ ha_rows send_records; ha_rows found_records,examined_rows,row_limit; --===============2470732202464350484== MIME-Version: 1.0 Content-Type: text/bzr-bundle; charset="us-ascii"; name="bzr/roy.lyseng@stripped" Content-Transfer-Encoding: 7bit Content-Disposition: inline # Bazaar merge directive format 2 (Bazaar 0.90) # revision_id: roy.lyseng@stripped # target_branch: file:///home/rl136806/mysql/repo/mysql-work5/ # testament_sha1: 875b934b8a70ea6fa126c9c273744831f2561518 # timestamp: 2011-03-15 14:14:23 +0100 # base_revision_id: roy.lyseng@stripped\ # 13ilk7l18hcompvx # # Begin bundle IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWW+ApPYABZv/gFUQiQB7d/// /7fegL////VgDd9J6u6HQbAHuzWUnLvDZfQ+r77mmtaAip6DSUjT4SiEamBEn6JtFP01PVPKep6m wSaPUeUaaANPKBpmoDU9BBpNTBNRlQNHkg9QAAAAAAAEpGgk0ynpPUyNHqB6gaAAAANAABoCTUhB RlPaqNG9U9J+lNNAeoHqHqNqGgAAAaAbVBFP0KDaT1AZAeiAMIDJiAAAACRIIBNNAjQNE0jDIpm0 hqNpqGhpo0AxLQA7dz0gh8enr78eNitBytUpDZKkSZdSX4/n+J8sMbzMsczMRx5vBj+SxLHwd+zP Hma/T2Md+PXPBcYWmGCamDsw3XnRr5R2+ApWwsBtFxt0p7Vqc4v74fM+jkltKq3nXp8kNd6/TWIo z3NAbmBsmS563WTzmVi3u91ha6Q5urspFsVpbRkB1Agz4wCQTBHOxamIkShBA4MYCiKJBSHFIVOj 9x1z/SYt6mV/gTPI5Xv+IfgS51RajyO44jGxDaEa8/yBczDrws24cvP6MOlrcnHTWA6dMjNbg1W7 Iuimi3MdOuNXnVKklS1rWq6kE3qgmUIqamGRKJWbLJyDRJED3ta+K/lWfxrkuBuVPFjyV5O38yvw pEQ6ZCAVyORZLduSQ782kQvlsi66kz8DMPOulBHoRKgq3ezkB6eFEGKhEnYIUPJtUHJR3CZDPV6y GYp/ZVh2nLKE2C0zk4N9K0o8sr4WRoqjIpIE3NCP4eK1GSKnS9w0ofGMWoXDihRKJMUZyxbD1ac1 /zgUmOXCCMa+R7SpI0Zi0jp1foyd260ltZdm4aIjLjpPHD0l9ulRUYWMpMexLcOFTNelsL6gpGot 5LSgUIcrJUGOoYchXl2JZ7SPbrsFvlwtDxmQEREzHQ19iwsLbCo2RMJYKiFhAPJ6eVGy9aINZJpX SFTPcC6zdkFg7dvWMdnNhG2FwLkDG+7aDmWsyBWSxpLifWfMDnk+UZQEy2RlLBMhm+yzFSkWazsg znAjLcpLDmCwaWYRL0SJCKpEQwvKJyOd88L7Uqxw6g2aMno2VUWGakpZUjVRHHn4GbRtV49rg4j5 5kygoiY/o+2kNUZ8uYq+cZL2MC9hTKvU+98Z0uwoe9LHqaPrBinT07eUyV6hUyKQduO+v8+q5YW2 68g8g5GB1oW8vBXvI0j6BkrLgO+hx2mgYWl04ikLSI020kmc/upO3u1SDQSYYYCXOlvOPwhGqlpw NDXUDHyl5cqIE2E2T8Y94cfUWlu4LQ5kKsXUik4QwYKCRWU7y4ZAGATWmPo6DVjW2oJ2jiGl04yl jZORHiw98rkSBgZ7Dp9dBL5S8qb7sTeW7Xw586AbgLTyBkBeH3qhs3+nPQtAxvWbz14Gtz+rKvfi FJZ6BocLVBqpoL1RbJIF1QuEuEFLW1TVNcrcZVcxYWYRtIJTB9grKYK9hsxSFzChGTIZJxEg3To4 geMAQAuTk3tnvYVYHutrUDWFAM5vntgevZaA989RsOF+u/VeTFabmQXSNuwqG8dqdsFxXUUC8CMJ JS13ucOgLJIDplgqvcQYD1fBZZWzpPhkxdKwIGAwHSBfmGjz1a+ZypQV4DCKTkbCTOpHDIwAmtzU y8RFhDKCZRzC5M+OAKtPgW8UD0Ras6Uh9lu+bmlavQZWVZYsRajR0R1M4MILECw33A6DSgUQQGGV rjVi3SWE8ggpD1dRxpvLsJNCwGEpHUeAfuvzrJiOYbnuAum47QCN7ViDSvLso1KAIMaXnOcpahEH BUMMXuO5VM4ly0vrYIBMvXQlLmzAUeka6mVIK8KhcwlGTCu+d0zAeRoSMCnWB9QGumvbmzC2Suzd LIVaSBxmKKK1Flr9fjXqfzTl54k013O5NAdScnF+eFd0jolGNWooIDEg0tRnN0jM4mtUQYeoRFTY b+I2iRVRVX7HA2/OH0qm3uiUrHd5/BGkPs+IVJh+bD6TQuA11P9iZwaX/BPYPS/WWlpnUcYBqBOd 4FpYfZMZyFxldYm7yGk97CBpnKNEWLYQ9OGEWTIKzC4KGrWuZftAwGoZdthJoYDEFFdfV3UUKasq 1qjtJ/CE6z6uAeIT4jt908f4Oe/aQJ1sk9eH0ndOzIktsvGbhoWVt52UO+c6Q8lW+6a8JKkHmFk8 n6lCWK+8Z0Oi6S/ZOwhJH6KsxdGVXTNAubeposhppNF0KFJIpFRGNsSpEcIOBigqF0ikXnZegYpP 1GSUXx2QPKojCsz6DCRJa7iF5gX6BqHA7VUzTy0DwLYIBRHkyef2pAWh+clv5Af033JLcNn4Bkj5 zCCLKTGtUwqYiwPYmyBQnwIKKJqB5QpUGXSlGHNv9EoiIGtZC/YRgxGCIIeXelYpntdWFXDQ6SlJ iY20HeSjo8ZH4HnO7uOF4eouCJIYcR4K8+x6VEasTXMbLaabSLWT5KLTMCwxn5krVBI5zHlByOUc 3xn4VN9Q6PGIHJk22NjikOLrC8DiKAMZgkyDkFSPwdAXd6DweJADv9O/2ePJxtvU9JQ9ncZHDPoU ZrNHVCEaAWo2Fq3bngVR6t2h5omPdGUgNL4jZOGGejqYnIa7dT1E52pUlhOWffeVTVhWmYdMbmFi 9ZwI1sqt1Lt0sMCBGCSOEaAdSk3dXhgaK6HHq5aSTv44KqiOW/aXhZE6bZFo2nKYYuKdclQq6ypy ISMWZavUgwEdo0KrDBoyaL2lHvlVGmpLFgl3ilCV5wH7duuwyLCsCDUukYnLiJbgmdBDZgyiM56x jh2ssLZPBnymo06YO4KmtPuI/yeJgHXadR1Ew+9iMWBgyGjsMKgjzsSKnOKK140LOw0Km9G88uS8 yacRDbbKK8Azwkc8EewKIeMQWETu9fYgZYKiIsAdsizoEl50goGxrNI2kI9alw8fQjERqaaHN766 emibcd1ravQkFwouhbJRMQUselaiUF8Jb7EQd0iCUL4SSRNpElyRLplO3ex37H0znDul7rKIOYhr yL1IwQ3dXo9y85obIwVqbLEYqebeiDrfNwS905UObz8xiqBCTGQBUYldsaF2NB/fa2xqOxz/UnEp MlXAIJKg+k5Yhx4mZU8TBFJaYkrS0bYyFCCH2/Whh9IbUTkEwKyFgIWrwS8xRKOGI6CUEMaEXILC ASIzvH8B4F6Rahhe20uxoIZNonGCM4O46xLMsoxwmhMf7RLdmkZCO2XGQfBpcSYhsqlngSMNaOPm qWJIcmLoMz5y+xUMC0qHtMStlhGZQyfstAs3vaiA0VBRRasQokKlCpQgkMlLXRFtN0LEagwslXmP MDHALgsEiCJGIwTAWYAkiBZ4uBFg7mSkVFa0ep4mRZWyAgv95AlJYAXhh3jFMOAKopjVB4CxPKne sxGC0gQNW7TIxSYB3MKaznSEuA+1HzGaLoZ1iXyaNaLhgeGJYSokHej1gXFVyZsHuA0ZDDEgcKRb ryd5LOknVBdbEnNfGiBKCyMYsYnIW06kBx6BQlbounzSGDF5g9IFqpskaEioKqBqo/Brdq7aETFg y0wFQkwy2EymaF8T4gYlyCqCrBhbEANja8Bh2SSCJrsiESGQzOkWex/pU9BumDZ3MGyZuVqX6zM9 /tkrCqGkXR3aw4H3F6m0+4skYI/I+SZH1cMmnknlhdJSQUeRRjjU4JVqnLSi9JUYzFFRjFgxFJQb mQ/BhVDNrMXL5jbIVmCKXxOzJk4A2rm42SA+nLtaS9kw+SS5r6BB4OhLMW8WuRoEnLBd3DVUUI+L ZsWE0DzdS/sw5HJXuG3oF73KqjvcCLqxYpxSoySIDzbzULy/lwxRKymBtfBXM3TKklNyG5uB9/RS ylyKkpDJwQxaFQz0oLpnVDEM0thA+gC0zYZKX1CwHPvBUiQYgokVQEYgoqRICqKQoupErqXlEboN siwQ7mwl2WooETOLElg6DQfOV19igIi/PYYCqjRMapfeCIctESUmRJom7sxUCdDIuJFCzXzpXaI9 KD7Jgn1SyJgmoqQaTTZMDbqlMm0pAWOqFOUQY4YVY/AkjcUUHlmFVoBkEaECP1fwGLqfbgdGhl7m MOw6CSW7oWrOW+bdB1kTlVhUSfgB7QOjoyOYpteM4iRsk7yYYIFG8VFJ7zFTEP8XckU4UJBvgKT2 --===============2470732202464350484==--