diff options
| -rw-r--r-- | sql/sql_select.cc | 188 | ||||
| -rw-r--r-- | sql/sql_select.h | 4 | ||||
| -rw-r--r-- | sql/table.h | 1 |
3 files changed, 175 insertions, 18 deletions
diff --git a/sql/sql_select.cc b/sql/sql_select.cc index 697f8093cb2..ef1c44d46ed 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -111,12 +111,14 @@ static void optimize_straight_join(JOIN *join, table_map join_tables); static bool greedy_search(JOIN *join, table_map remaining_tables, uint depth, uint prune_level, uint use_cond_selectivity); + enum enum_best_search { SEARCH_ABORT= -2, SEARCH_ERROR= -1, SEARCH_OK= 0, SEARCH_FOUND_EDGE=1 }; + static enum_best_search best_extension_by_limited_search(JOIN *join, table_map remaining_tables, @@ -492,6 +494,7 @@ void JOIN::init(THD *thd_arg, List<Item> &fields_arg, original_join_tab= 0; explain= NULL; tmp_table_keep_current_rowid= 0; + allowed_top_level_tables= 0; all_fields= fields_arg; if (&fields_list != &fields_arg) /* Avoid valgrind-warning */ @@ -2163,6 +2166,9 @@ JOIN::optimize_inner() thd->restore_active_arena(arena, &backup); } + if (!allowed_top_level_tables) + calc_allowed_top_level_tables(select_lex); + if (optimize_constant_subqueries()) DBUG_RETURN(1); @@ -9192,6 +9198,7 @@ greedy_search(JOIN *join, uint idx= join->const_tables; // index into 'join->best_ref' uint best_idx; uint size_remain; // cardinality of remaining_tables + table_map usable_tables; POSITION best_pos; JOIN_TAB *best_table; // the next plan node to be added to the curr QEP // ==join->tables or # tables in the sj-mat nest we're optimizing @@ -9199,16 +9206,20 @@ 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 & - ~join->const_table_map) - : - ~(table_map)0)); + usable_tables= (join->emb_sjm_nest ? + (join->emb_sjm_nest->sj_inner_tables & + ~join->const_table_map & remaining_tables): + remaining_tables); + n_tables= size_remain= my_count_bits(usable_tables); join->next_sort_position= join->sort_positions; do { - /* Find the extension of the current QEP with the lowest cost */ + /* + Find the extension of the current QEP with the lowest cost + We are using remaining_table instead of usable tables here as + in case of an emb_sjm_nest, we want to be able to check if + an embedded table is depending on an outer table. + */ join->best_read= DBL_MAX; if ((int) best_extension_by_limited_search(join, remaining_tables, idx, record_count, @@ -10054,6 +10065,8 @@ best_extension_by_limited_search(JOIN *join, bool disable_jbuf= join->thd->variables.join_cache_level == 0; enum_best_search best_res; uint tables_left= join->table_count - idx, found_tables; + uint accepted_tables __attribute__((unused)); + table_map allowed_tables, allowed_current_tables; POSITION *sort_position= join->next_sort_position; SORT_POSITION *sort= (SORT_POSITION*) alloca(sizeof(SORT_POSITION)*tables_left); SORT_POSITION *sort_end; @@ -10073,13 +10086,28 @@ best_extension_by_limited_search(JOIN *join, "part_plan");); status_var_increment(thd->status_var.optimizer_join_prefixes_check_calls); - /* - If we are searching for the execution plan of a materialized semi-join nest - then allowed_tables contains bits only for the tables from this nest. - */ - table_map allowed_tables= ~(table_map)0; if (join->emb_sjm_nest) - allowed_tables= join->emb_sjm_nest->sj_inner_tables & ~join->const_table_map; + { + /* + If we are searching for the execution plan of a materialized semi-join nest + then allowed_tables contains bits only for the tables from this nest. + */ + allowed_tables= (join->emb_sjm_nest->sj_inner_tables & remaining_tables); + allowed_current_tables= join->get_allowed_nj_tables(idx) & remaining_tables; + } + else + { + /* + allowed_tables is used to check if there are tables left that can improve + a key search and to see if there are more tables to add in next iteration. + + allowed_current_tables tells us which tables we can add to the current + plan at this stage. + */ + allowed_tables= remaining_tables; + allowed_current_tables= join->get_allowed_nj_tables(idx) & remaining_tables; + } + DBUG_ASSERT(allowed_tables & remaining_tables); { Json_writer_object trace_one_table(thd); @@ -10093,11 +10121,13 @@ best_extension_by_limited_search(JOIN *join, for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++) { table_map real_table_bit= s->table->map; - DBUG_ASSERT(remaining_tables & real_table_bit); - - if ((allowed_tables & real_table_bit) && + if ((allowed_current_tables & real_table_bit) && !(remaining_tables & s->dependent)) { +#ifdef DBUG_ASSERT_EXISTS + DBUG_ASSERT(!check_interleaving_with_nj(s)); + restore_prev_nj_state(s); // Revert effect of check_... call +#endif sort_end->join_tab= pos; sort_end->position= sort_position; @@ -10111,8 +10141,17 @@ best_extension_by_limited_search(JOIN *join, sort_end++; sort_position+= 2; } + else + { + /* Verify that 'allowed_current_tables' was calculated correctly */ + DBUG_ASSERT((remaining_tables & s->dependent) || + !(remaining_tables & real_table_bit) || + !(allowed_tables & real_table_bit) || + check_interleaving_with_nj(s)); + } } found_tables= sort_end - sort; + DBUG_ASSERT(found_tables > 0); if (found_tables > 1) my_qsort(sort, found_tables, sizeof(SORT_POSITION), (qsort_cmp) sort_positions); @@ -10121,6 +10160,7 @@ best_extension_by_limited_search(JOIN *join, DBUG_ASSERT(join->next_sort_position <= join->sort_positions + join->sort_space); + accepted_tables= 0; for (SORT_POSITION *pos= sort ; pos < sort_end ; pos++) { s= *pos->join_tab; @@ -10138,6 +10178,7 @@ best_extension_by_limited_search(JOIN *join, trace_one_table.add_table_name(s); } + accepted_tables++; *position= *pos->position; // Get stored result loose_scan_pos= pos->position+1; @@ -10236,8 +10277,8 @@ best_extension_by_limited_search(JOIN *join, } } - if ((search_depth > 1) && (remaining_tables & ~real_table_bit) & - allowed_tables) + if ((search_depth > 1) && + ((remaining_tables & ~real_table_bit) & allowed_tables)) { /* Recursively expand the current partial plan */ Json_writer_array trace_rest(thd, "rest_of_plan"); @@ -10305,6 +10346,7 @@ best_extension_by_limited_search(JOIN *join, } } } + DBUG_ASSERT(accepted_tables > 0); best_res= SEARCH_OK; end: @@ -17589,6 +17631,116 @@ static void restore_prev_nj_state(JOIN_TAB *last) } +/* + Compute allowed_top_level_tables - a bitmap of tables one can put into the + join order if the last table in the join prefix is not inside any outer + join nest. + + NESTED_JOIN::direct_children_map - a bitmap of tables ... if the last + table in the join prefix is inside the join nest. + + Note: it looks like a sensible way to do this is a top-down descent on + JOIN::join_list, but apparently that list is missing I_S tables. + e.g. for SHOW TABLES WHERE col IN (SELECT ...) it will just have a + semi-join nest. +*/ + +void JOIN::calc_allowed_top_level_tables(SELECT_LEX *lex) +{ + TABLE_LIST *tl; + List_iterator<TABLE_LIST> ti(lex->leaf_tables); + DBUG_ENTER("JOIN::calc_allowed_top_level_tables"); + DBUG_ASSERT(allowed_top_level_tables == 0); // Should only be called once + + while ((tl= ti++)) + { + table_map map; + TABLE_LIST *embedding= tl->embedding; + + if (tl->table) + map= tl->table->map; + else + { + DBUG_ASSERT(tl->jtbm_subselect); + map= table_map(1) << tl->jtbm_table_no; + } + + if (!(embedding= tl->embedding)) + { + allowed_top_level_tables |= map; + continue; + } + + // Walk out of any semi-join nests + while (embedding && !embedding->on_expr) + { + // semi-join nest or an INSERT-INTO view... + embedding->nested_join->direct_children_map |= map; + embedding= embedding->embedding; + } + + // Ok we are in the parent nested outer join nest. + if (!embedding) + { + allowed_top_level_tables |= map; + continue; + } + embedding->nested_join->direct_children_map |= map; + + // Walk to grand-parent join nest. + embedding= embedding->embedding; + + // Walk out of any semi-join nests + while (embedding && !embedding->on_expr) + { + DBUG_ASSERT(embedding->sj_on_expr); + embedding->nested_join->direct_children_map |= map; + embedding= embedding->embedding; + } + + if (embedding) + { + DBUG_ASSERT(embedding->on_expr); // Impossible, see above + embedding->nested_join->direct_children_map |= map; + } + else + allowed_top_level_tables |= map; + } + DBUG_VOID_RETURN; +} + + +/* + Get the tables that one is allowed to have as the next table in the + current plan +*/ + +table_map JOIN::get_allowed_nj_tables(uint idx) +{ + TABLE_LIST *last_emb; + if (idx > const_tables && + (last_emb= positions[idx-1].table->table->pos_in_table_list->embedding)) + { + for (;last_emb && last_emb != emb_sjm_nest; + last_emb= last_emb->embedding) + { + if (!last_emb->sj_on_expr) + { + NESTED_JOIN *nest= last_emb->nested_join; + if (!nest->is_fully_covered()) + { + // Return tables that are direct members of this join nest + return nest->direct_children_map; + } + } + } + } + // Return bitmap of tables not in any join nest + if (emb_sjm_nest) + return emb_sjm_nest->nested_join->direct_children_map; + return allowed_top_level_tables; +} + /* Change access methods not to use join buffering and adjust costs accordingly diff --git a/sql/sql_select.h b/sql/sql_select.h index eec073179f3..54f65c347c2 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -1261,6 +1261,8 @@ public: table_map outer_join; /* Bitmap of tables used in the select list items */ table_map select_list_used_tables; + + table_map allowed_top_level_tables; ha_rows send_records,found_records,join_examined_rows, accepted_rows; /* @@ -1765,6 +1767,8 @@ public: bool transform_in_predicates_into_in_subq(THD *thd); bool optimize_upper_rownum_func(); + void calc_allowed_top_level_tables(SELECT_LEX *lex); + table_map get_allowed_nj_tables(uint idx); private: /** diff --git a/sql/table.h b/sql/table.h index d4394bcd566..8c48b016cb8 100644 --- a/sql/table.h +++ b/sql/table.h @@ -3116,6 +3116,7 @@ typedef struct st_nested_join table_map sj_depends_on; /* Outer non-trivially correlated tables */ table_map sj_corr_tables; + table_map direct_children_map; List<Item_ptr> sj_outer_expr_list; /** True if this join nest node is completely covered by the query execution |