diff options
| -rw-r--r-- | sql/opt_subselect.cc | 76 | ||||
| -rw-r--r-- | sql/sql_select.cc | 31 | ||||
| -rw-r--r-- | sql/sql_select.h | 13 |
3 files changed, 72 insertions, 48 deletions
diff --git a/sql/opt_subselect.cc b/sql/opt_subselect.cc index 7b47bed1e09..bdf5175fc8b 100644 --- a/sql/opt_subselect.cc +++ b/sql/opt_subselect.cc @@ -3653,8 +3653,8 @@ bool JOIN::optimize_unflattened_subqueries() */ bool JOIN::choose_subquery_plan(table_map join_tables) -{ /* The original QEP of the subquery. */ - Query_plan_state save_qep; +{ + Query_plan_state save_qep; /* The original QEP of the subquery. */ enum_reopt_result reopt_result= REOPT_NONE; Item_in_subselect *in_subs; @@ -3681,32 +3681,50 @@ bool JOIN::choose_subquery_plan(table_map join_tables) if (in_subs->in_strategy & SUBS_MATERIALIZATION && in_subs->in_strategy & SUBS_IN_TO_EXISTS) { - JOIN *outer_join= unit->outer_select() ? unit->outer_select()->join : NULL; + JOIN *outer_join; JOIN *inner_join= this; - /* Cost of the outer JOIN. */ - double outer_read_time, outer_record_count; - /* Cost of the unmodified subquery. */ + /* Number of (partial) rows of the outer JOIN filtered by the IN predicate. */ + double outer_record_count; + /* Number of unique value combinations filtered by the IN predicate. */ + double outer_lookup_keys; + /* Cost and row count of the unmodified subquery. */ double inner_read_time_1, inner_record_count_1; - /* Cost of the subquery with injected IN-EXISTS predicates. */ - double inner_read_time_2, inner_record_count_2; + /* Cost and row count of the subquery with injected IN-EXISTS predicates. */ + double inner_read_time_2; /* The cost to compute IN via materialization. */ double materialize_strategy_cost; /* The cost of the IN->EXISTS strategy. */ double in_exists_strategy_cost; + double dummy; + /* + A. Estimate the number of rows of the outer table that will be filtered + by the IN predicate. + */ + outer_join= unit->outer_select() ? unit->outer_select()->join : NULL; if (outer_join) { + uint outer_partial_plan_len; /* Make_cond_for_table is called for predicates only in the WHERE/ON clauses. In all other cases, predicates are not pushed to any JOIN_TAB, and their joi_tab_idx remains MAX_TABLES. Such predicates - are evaluated for each complete row. + are evaluated for each complete row of the outer join. */ - uint partial_plan_len= (in_subs->get_join_tab_idx() == MAX_TABLES) ? - outer_join->tables : - in_subs->get_join_tab_idx() + 1; - outer_join->get_partial_join_cost(partial_plan_len, - &outer_read_time, &outer_record_count); + outer_partial_plan_len= (in_subs->get_join_tab_idx() == MAX_TABLES) ? + outer_join->tables : + in_subs->get_join_tab_idx() + 1; + outer_join->get_partial_join_cost(outer_partial_plan_len, &dummy, + &outer_record_count); + if (outer_join->tables > outer_join->const_tables) + outer_lookup_keys= prev_record_reads(outer_join->best_positions, + outer_partial_plan_len, + in_subs->used_tables()); + else + { + /* If all tables are constant, positions is undefined. */ + outer_lookup_keys= 1; + } } else { @@ -3714,15 +3732,17 @@ bool JOIN::choose_subquery_plan(table_map join_tables) TODO: outer_join can be NULL for DELETE statements. How to compute its cost? */ - outer_read_time= 1; /* TODO */ - outer_record_count= 1; /* TODO */ + outer_record_count= 1; + outer_lookup_keys=1; } + DBUG_ASSERT(outer_lookup_keys <= outer_record_count); - inner_join->get_partial_join_cost(inner_join->tables, - &inner_read_time_1, - &inner_record_count_1); - /* inner_read_time_1 above is a dummy, get the correct total join cost. */ + /* + B. Estimate the cost and number of records of the subquery both + unmodified, and with injected IN->EXISTS predicates. + */ inner_read_time_1= inner_join->best_read; + inner_record_count_1= inner_join->record_count; if (in_to_exists_where && const_tables != tables) { @@ -3734,9 +3754,6 @@ bool JOIN::choose_subquery_plan(table_map join_tables) if (reopt_result == REOPT_ERROR) return TRUE; - inner_join->get_partial_join_cost(inner_join->tables, - &inner_read_time_2, - &inner_record_count_2); /* inner_read_time_2 above is a dummy, get the correct total join cost. */ inner_read_time_2= inner_join->best_read; @@ -3745,13 +3762,12 @@ bool JOIN::choose_subquery_plan(table_map join_tables) { /* Reoptimization would not produce any better plan. */ inner_read_time_2= inner_read_time_1; - inner_record_count_2= inner_record_count_1; } - /* Compute execution costs. */ /* - 1. Compute the cost of the materialization strategy. + C. Compute execution costs. */ + /* C.1 Compute the cost of the materialization strategy. */ uint rowlen= get_tmp_table_rec_length(unit->first_select()->item_list); /* The cost of writing one row into the temporary table. */ double write_cost= get_tmp_table_write_cost(thd, inner_record_count_1, @@ -3769,12 +3785,10 @@ bool JOIN::choose_subquery_plan(table_map join_tables) materialize_strategy_cost= materialization_cost + outer_record_count * lookup_cost; - /* - 2. Compute the cost of the IN=>EXISTS strategy. - */ - in_exists_strategy_cost= outer_record_count * inner_read_time_2; + /* C.2 Compute the cost of the IN=>EXISTS strategy. */ + in_exists_strategy_cost= outer_lookup_keys * inner_read_time_2; - /* Compare the costs and choose the cheaper strategy. */ + /* C.3 Compare the costs and choose the cheaper strategy. */ if (materialize_strategy_cost >= in_exists_strategy_cost) in_subs->in_strategy&= ~SUBS_MATERIALIZATION; else diff --git a/sql/sql_select.cc b/sql/sql_select.cc index f23fda455c6..739e9b8a991 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -65,15 +65,13 @@ static bool sort_and_filter_keyuse(DYNAMIC_ARRAY *keyuse); static int sort_keyuse(KEYUSE *a,KEYUSE *b); static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse, table_map used_tables); -bool choose_plan(JOIN *join,table_map join_tables); - void best_access_path(JOIN *join, JOIN_TAB *s, table_map remaining_tables, uint idx, bool disable_jbuf, double record_count, POSITION *pos, POSITION *loose_scan_pos); 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 depth, uint prune_level); static bool best_extension_by_limited_search(JOIN *join, table_map remaining_tables, uint idx, double record_count, @@ -90,7 +88,6 @@ static int join_tab_cmp_embedded_first(const void *emb, const void* ptr1, const static bool find_best(JOIN *join,table_map rest_tables,uint index, double record_count,double read_time); static uint cache_record_length(JOIN *join,uint index); -static double prev_record_reads(JOIN *join, uint idx, table_map found_ref); static bool get_best_combination(JOIN *join); static store_key *get_store_key(THD *thd, KEYUSE *keyuse, table_map used_tables, @@ -3143,6 +3140,7 @@ make_join_statistics(JOIN *join, TABLE_LIST *tables_arg, COND *conds, { memcpy((uchar*) join->best_positions,(uchar*) join->positions, sizeof(POSITION)*join->const_tables); + join->record_count= 1.0; join->best_read=1.0; } if (join->choose_subquery_plan(all_table_map & ~join->const_table_map)) @@ -4505,8 +4503,8 @@ best_access_path(JOIN *join, if (!(keyuse->used_tables & ~join->const_table_map)) const_part|= keyuse->keypart_map; - double tmp2= prev_record_reads(join, idx, (found_ref | - keyuse->used_tables)); + double tmp2= prev_record_reads(join->positions, idx, + (found_ref | keyuse->used_tables)); if (tmp2 < best_prev_record_reads) { best_part_found_ref= keyuse->used_tables & ~join->const_table_map; @@ -4546,7 +4544,7 @@ best_access_path(JOIN *join, Really, there should be records=0.0 (yes!) but 1.0 would be probably safer */ - tmp= prev_record_reads(join, idx, found_ref); + tmp= prev_record_reads(join->positions, idx, found_ref); records= 1.0; } else @@ -4561,7 +4559,7 @@ best_access_path(JOIN *join, max_key_part= (uint) ~0; if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME) { - tmp = prev_record_reads(join, idx, found_ref); + tmp = prev_record_reads(join->positions, idx, found_ref); records=1.0; } else @@ -5275,6 +5273,7 @@ optimize_straight_join(JOIN *join, table_map join_tables) read_time+= record_count; // We have to make a temp table memcpy((uchar*) join->best_positions, (uchar*) join->positions, sizeof(POSITION)*idx); + join->record_count= record_count; join->best_read= read_time; } @@ -5487,7 +5486,7 @@ void JOIN::get_partial_join_cost(uint n_tables, double record_count= 1; double read_time= 0.0; - DBUG_ASSERT(n_tables <= tables && n_tables > 0); + DBUG_ASSERT(n_tables <= tables); for (uint i= const_tables; i < n_tables; i++) { @@ -5502,8 +5501,6 @@ void JOIN::get_partial_join_cost(uint n_tables, } - - /** Find a good, possibly optimal, query execution plan (QEP) by a possibly exhaustive search. @@ -5756,6 +5753,7 @@ best_extension_by_limited_search(JOIN *join, { memcpy((uchar*) join->best_positions, (uchar*) join->positions, sizeof(POSITION) * (idx + 1)); + join->record_count= current_record_count; join->best_read= current_read_time - 0.001; } DBUG_EXECUTE("opt", print_plan(join, idx+1, @@ -5981,12 +5979,12 @@ cache_record_length(JOIN *join,uint idx) Expected number of row combinations */ -static double -prev_record_reads(JOIN *join, uint idx, table_map found_ref) +double +prev_record_reads(POSITION *positions, uint idx, table_map found_ref) { double found=1.0; - POSITION *pos_end= join->positions - 1; - for (POSITION *pos= join->positions + idx - 1; pos != pos_end; pos--) + POSITION *pos_end= positions - 1; + for (POSITION *pos= positions + idx - 1; pos != pos_end; pos--) { if (pos->table->table->map & found_ref) { @@ -19478,7 +19476,10 @@ JOIN::reoptimize(Item *added_where, table_map join_tables, } if (!added_keyuse.elements) + { + delete_dynamic(&added_keyuse); return REOPT_OLD_PLAN; + } if (save_to) save_query_plan(save_to); diff --git a/sql/sql_select.h b/sql/sql_select.h index 6541dd58383..a1e0d95a88d 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -1376,7 +1376,8 @@ private: protected: /** - ??? + The subset of the state of a JOIN that represents an optimized query + execution plan. Allows saving/restoring different plans for the same query. */ class Query_plan_state { public: @@ -1512,6 +1513,13 @@ public: account the changes made by test_if_skip_sort_order()). */ double best_read; + /* + Estimated result rows (fanout) of the whole query. If this is a subquery + that is reexecuted multiple times, this value includes the estiamted # of + reexecutions. This value is equal to the multiplication of all + join->positions[i].records_read of a JOIN. + */ + double record_count; List<Item> *fields; List<Cached_item> group_fields, group_fields_cache; TABLE *tmp_table; @@ -2054,7 +2062,7 @@ inline Item * and_items(Item* cond, Item *item) { return (cond? (new Item_cond_and(cond, item)) : item); } -bool choose_plan(JOIN *join,table_map join_tables); +bool choose_plan(JOIN *join, table_map join_tables); void optimize_wo_join_buffering(JOIN *join, uint first_tab, uint last_tab, table_map last_remaining_tables, bool first_alt, uint no_jbuf_before, @@ -2099,5 +2107,6 @@ bool create_internal_tmp_table(TABLE *table, KEY *keyinfo, ulonglong options); bool open_tmp_table(TABLE *table); void setup_tmp_table_column_bitmaps(TABLE *table, uchar *bitmaps); +double prev_record_reads(POSITION *positions, uint idx, table_map found_ref); #endif /* SQL_SELECT_INCLUDED */ |