From f17cea00874130e4d212d23049b2969403a48d13 Mon Sep 17 00:00:00 2001 From: unknown Date: Sun, 5 Sep 2010 18:43:47 +0300 Subject: MWL#89: Cost-based choice between Materialization and IN->EXISTS transformation Fixes for multiple problems/bugs/test failures that resulted from moving subquery optimization from the execution phase to the optimization phase. --- sql/sql_select.h | 14 +++++++++++++- 1 file changed, 13 insertions(+), 1 deletion(-) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index 2b7fc8fd47c..c87147f6106 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -1573,8 +1573,15 @@ public: bool union_part; ///< this subselect is part of union bool optimized; ///< flag to avoid double optimization in EXPLAIN + bool initialized; ///< flag to avoid double init_execution calls Array sj_subselects; + /* + Additional WHERE and HAVING predicates to be considered for IN=>EXISTS + subquery transformation of a JOIN object. + */ + Item *in_to_exists_where; + Item *in_to_exists_having; /* Temporary tables used to weed-out semi-join duplicates */ List sj_tmp_tables; @@ -1649,6 +1656,7 @@ public: ref_pointer_array_size= 0; zero_result_cause= 0; optimized= 0; + initialized= 0; cond_equal= 0; group_optimized_away= 0; @@ -1662,6 +1670,8 @@ public: no_const_tables= FALSE; first_select= sub_select; + in_to_exists_where= NULL; + in_to_exists_having= NULL; } int prepare(Item ***rref_pointer_array, TABLE_LIST *tables, uint wind_num, @@ -1670,12 +1680,13 @@ public: SELECT_LEX_UNIT *unit); int optimize(); int reinit(); + int init_execution(); void exec(); int destroy(); void restore_tmp(); bool alloc_func_list(); bool flatten_subqueries(); - bool setup_subquery_materialization(); + bool optimize_unflattened_subqueries(); bool make_sum_func_list(List &all_fields, List &send_fields, bool before_group_by, bool recompute= FALSE); @@ -1735,6 +1746,7 @@ public: NULL : join_tab+const_tables; } bool setup_subquery_caches(); + bool choose_subquery_plan(); private: /** TRUE if the query contains an aggregate function but has no GROUP -- cgit v1.2.1 From 0e75dee2c29bbf8483e446dbabe6e6f27a7f77f3 Mon Sep 17 00:00:00 2001 From: unknown Date: Thu, 30 Sep 2010 18:32:44 +0300 Subject: MWL#89: Cost-based choice between Materialization and IN->EXISTS transformation Phase 3: Implementation of re-optimization of subqueries with injected predicates and cost comparison between Materialization and IN->EXISTS strategies. The commit contains the following known problems: - The implementation of EXPLAIN has not been re-engineered to reflect the changes in subquery optimization. EXPLAIN for subqueries is called during the execute phase, which results in different code paths during JOIN::optimize and thus in differing EXPLAIN messages for constant/system tables. - There are some valgrind warnings that need investigation - Several EXPLAINs with minor differences need to be reconsidered after fixing the EXPLAIN problem above. This patch also adds one extra optimizer_switch: 'in_to_exists' for complete manual control of the subquery execution strategies. --- sql/sql_select.h | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index c87147f6106..5f1abcce87f 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -1369,8 +1369,21 @@ inline bool sj_is_materialize_strategy(uint strategy) class JOIN :public Sql_alloc { +private: JOIN(const JOIN &rhs); /**< not implemented */ JOIN& operator=(const JOIN &rhs); /**< not implemented */ + +protected: + /* Support for plan reoptimization with rewritten conditions. */ + int reoptimize(Item *added_where, table_map join_tables, + POSITION *save_best_positions); + int save_query_plan(DYNAMIC_ARRAY *save_keyuse, POSITION *save_positions, + KEYUSE **save_join_tab_keyuse, + key_map *save_join_tab_checked_keys); + void restore_query_plan(DYNAMIC_ARRAY *save_keyuse, POSITION *save_positions, + KEYUSE **save_join_tab_keyuse, + key_map *save_join_tab_checked_keys); + public: JOIN_TAB *join_tab,**best_ref; JOIN_TAB **map2table; ///< mapping between table indexes and JOIN_TABs @@ -1746,7 +1759,7 @@ public: NULL : join_tab+const_tables; } bool setup_subquery_caches(); - bool choose_subquery_plan(); + bool choose_subquery_plan(table_map join_tables); private: /** TRUE if the query contains an aggregate function but has no GROUP -- cgit v1.2.1 From ffc9698d4c62e45dc845d2ffb68dc777cc5bbacc Mon Sep 17 00:00:00 2001 From: unknown Date: Sat, 23 Oct 2010 21:28:58 +0300 Subject: MWL#89: Cost-based choice between Materialization and IN->EXISTS transformation Added missing logic to handle the case when subquery tables are optimized away early during optimization. --- sql/sql_select.h | 2 ++ 1 file changed, 2 insertions(+) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index 5f1abcce87f..0bb8c9e9285 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -1383,6 +1383,8 @@ protected: void restore_query_plan(DYNAMIC_ARRAY *save_keyuse, POSITION *save_positions, KEYUSE **save_join_tab_keyuse, key_map *save_join_tab_checked_keys); + /* Choose a subquery plan for a table-less subquery. */ + bool choose_tableless_subquery_plan(); public: JOIN_TAB *join_tab,**best_ref; -- cgit v1.2.1 From e6f68ff6bba1b5d3c10a0032d8293e9c8863a4eb Mon Sep 17 00:00:00 2001 From: unknown Date: Tue, 2 Nov 2010 15:27:01 +0200 Subject: Fixed LP BUG#652727 and LP BUG#643424. The fixes for #643424 was part of the fix for #652727, that's why both fixes are pushed together. - The cause for #643424 was the improper use of get_partial_join_cost(), which assumed that the 'n_tables' parameter was the upper bound for query plan node indexes. Fixed by generalizing get_partial_join_cost() as a method that computes the cost of any partial join. - The cause of #652727 was that JOIN::choose_subquery_plan() incorrectly deleted the contents of the old keyuse array in the cases when an injected plan would not provide more key accesses, and reoptimization was not actually performed. --- sql/sql_select.h | 16 ++++++++++++---- 1 file changed, 12 insertions(+), 4 deletions(-) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index 0bb8c9e9285..14af63f5dd1 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -1374,9 +1374,16 @@ private: JOIN& operator=(const JOIN &rhs); /**< not implemented */ protected: + /* Results of reoptimizing a JOIN via JOIN::reoptimize(). */ + enum enum_reopt_result { + REOPT_NEW_PLAN, /* there is a new reoptimized plan */ + REOPT_OLD_PLAN, /* no new improved plan can be found, use the old one */ + REOPT_ERROR, /* an irrecovarable error occured during reoptimization */ + REOPT_NONE /* not yet reoptimized */ + }; + /* Support for plan reoptimization with rewritten conditions. */ - int reoptimize(Item *added_where, table_map join_tables, - POSITION *save_best_positions); + enum_reopt_result reoptimize(Item *added_where, table_map join_tables); int save_query_plan(DYNAMIC_ARRAY *save_keyuse, POSITION *save_positions, KEYUSE **save_join_tab_keyuse, key_map *save_join_tab_checked_keys); @@ -1762,6 +1769,9 @@ public: } bool setup_subquery_caches(); bool choose_subquery_plan(table_map join_tables); + void get_partial_join_cost(uint n_tables, + double *read_time_arg, double *record_count_arg); + private: /** TRUE if the query contains an aggregate function but has no GROUP @@ -1993,8 +2003,6 @@ 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); -void get_partial_join_cost(JOIN *join, uint n_tables, double *read_time_arg, - double *record_count_arg); 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, -- cgit v1.2.1 From f5443c1467395785c9508609df7d7aa492e15e7a Mon Sep 17 00:00:00 2001 From: unknown Date: Fri, 19 Nov 2010 12:54:15 +0200 Subject: Fixed LP BUG#641203: Query returns rows where no result is expected (impossible WHERE) The cause for the bug was two-fold: 1. Incorrect detection of whether a table is the first one in a query plan - "used_table & 1" actually checks if used_table is table with number "1". 2. Missing logic to delay the evaluation of (expensive) constant conditions during the execution phase. The fix adds/changes: The patch: - removes incorrect treatment of expensive predicates from make_cond_for_table, and lets the caller decide when to evaluate expensive predicates. - saves expensive constant conditions in JOIN::exec_const_cond, which is evaluated once in the beginning of JOIN::exec. --- sql/sql_select.h | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index 574e614594a..7cb5aaaac46 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -1593,6 +1593,12 @@ public: List *join_list; ///< list of joined tables in reverse order COND_EQUAL *cond_equal; COND_EQUAL *having_equal; + /* + Constant codition computed during optimization, but evaluated during + join execution. Typically expensive conditions that should not be + evaluated at optimization time. + */ + Item *exec_const_cond; SQL_SELECT *select; /// Date: Fri, 19 Nov 2010 17:01:48 +0200 Subject: Fix for LP BUG#676411 and MySQL BUG#52317 This is a backport of the fix for MySQL BUG#52317: Assertion failing in Field_varstring::store () at field.cc:6833 The orginal comment by Oystein is: In order for EXPLAIN to print const-refs, a Store_key_const_item object is created. This is different for normal execution of subqueries where a temporary store_key_item object is used instead. The problem is that EXPLAIN will execute subqueries. This leads to a scenario where a store_key_const_item object it told to write to its underlying field. This results in a failing assert since the write set of the underlying table does not reflect this. The resolution is to do the same trick as for store_key_item::copy_inner(). That is, temporarily change the write set to allow writes to all columns. This is only necessary in debug version since non-debug version does not contain asserts on write_set. sql/sql_select.h: Temporarily change write_set in store_key_const_item::copy_inner() to allow initialization of underlying field. This is necessary since subqueries are executed for EXPLAIN. (For normal execution, store_key_item::copy_inner is used.) --- sql/sql_select.h | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index 7cb5aaaac46..7fcf18a5985 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -1990,6 +1990,9 @@ protected: if (!inited) { inited=1; + TABLE *table= to_field->table; + my_bitmap_map *old_map= dbug_tmp_use_all_columns(table, + table->write_set); if ((res= item->save_in_field(to_field, 1))) { if (!err) @@ -2001,6 +2004,7 @@ protected: */ if (!err && to_field->table->in_use->is_error()) err= 1; /* STORE_KEY_FATAL */ + dbug_tmp_restore_column_map(table->write_set, old_map); } null_key= to_field->is_null() || item->null_value; return (err > 2 ? STORE_KEY_FATAL : (store_key_result) err); -- cgit v1.2.1 From c8413dba047cac6df3d9f0eb6b950fa95b2199d0 Mon Sep 17 00:00:00 2001 From: unknown Date: Thu, 2 Dec 2010 21:54:40 +0200 Subject: Fix LP BUG#682683 Analysis: The fix for LP BUG#680846 avoids evaluation of constant expressions with subqueries in the GROUP/ORDER clauses in the procedure remove_const(). The purpose of remove_const is to remove constant expressions in the GROUP/ORDER clauses. In order delay until execution the evaluation of such subqueries, they were not removed in the GROUP/ORDER clause. As a result temp table creation during execution attempted to create a column in the temp table for each constant GROUP/ORDER expression. However, the logic in create_tmp_table is to not create temp table columns for constant items. The crash was due to a group Item without a corresponding column in the temp table for GROUP BY. Solution: The patch adds back removal of constant expressions with subqueries. In order for such expressions to be evaluated, so that the server can ensure that such subquries return 1 row, the evaluation of these expressions is delayed until execution. --- sql/sql_select.h | 10 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index 7fcf18a5985..008530a4d94 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -1599,6 +1599,13 @@ public: evaluated at optimization time. */ Item *exec_const_cond; + /* + Constant ORDER and/or GROUP expressions that contain subqueries. Such + expressions need to evaluated to verify that the subquery indeed + returns a single row. The evaluation of such expressions is delayed + until query execution. + */ + List exec_const_order_group_cond; SQL_SELECT *select; /// Date: Wed, 15 Dec 2010 12:54:25 +0200 Subject: MWL#89 Post-review fixes. Intermediate commit to address review points 1.1, 1.2, 1.3, 1.4, 1.5, and 3.1, 3.2, 3.3. --- sql/sql_select.h | 36 +++++++++++++++++++++++++++++------- 1 file changed, 29 insertions(+), 7 deletions(-) (limited to 'sql/sql_select.h') diff --git a/sql/sql_select.h b/sql/sql_select.h index 9be3b7c3ffe..6541dd58383 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -1374,6 +1374,31 @@ private: JOIN& operator=(const JOIN &rhs); /**< not implemented */ protected: + + /** + ??? + */ + class Query_plan_state { + public: + DYNAMIC_ARRAY keyuse; /* Copy of the JOIN::keyuse array. */ + POSITION best_positions[MAX_TABLES+1]; /* Copy of JOIN::best_positions */ + /* Copies of the JOIN_TAB::keyuse pointers for each JOIN_TAB. */ + KEYUSE *join_tab_keyuse[MAX_TABLES]; + /* Copies of JOIN_TAB::checked_keys for each JOIN_TAB. */ + key_map join_tab_checked_keys[MAX_TABLES]; + public: + Query_plan_state() + { + keyuse.elements= 0; + keyuse.buffer= NULL; + } + Query_plan_state(JOIN *join); + ~Query_plan_state() + { + delete_dynamic(&keyuse); + } + }; + /* Results of reoptimizing a JOIN via JOIN::reoptimize(). */ enum enum_reopt_result { REOPT_NEW_PLAN, /* there is a new reoptimized plan */ @@ -1383,13 +1408,10 @@ protected: }; /* Support for plan reoptimization with rewritten conditions. */ - enum_reopt_result reoptimize(Item *added_where, table_map join_tables); - int save_query_plan(DYNAMIC_ARRAY *save_keyuse, POSITION *save_positions, - KEYUSE **save_join_tab_keyuse, - key_map *save_join_tab_checked_keys); - void restore_query_plan(DYNAMIC_ARRAY *save_keyuse, POSITION *save_positions, - KEYUSE **save_join_tab_keyuse, - key_map *save_join_tab_checked_keys); + enum_reopt_result reoptimize(Item *added_where, table_map join_tables, + Query_plan_state *save_to); + void save_query_plan(Query_plan_state *save_to); + void restore_query_plan(Query_plan_state *restore_from); /* Choose a subquery plan for a table-less subquery. */ bool choose_tableless_subquery_plan(); -- cgit v1.2.1 From 87d27bbf9b4f5b03ee3322b83ed1749c2f61943d Mon Sep 17 00:00:00 2001 From: unknown Date: Thu, 23 Dec 2010 17:33:00 +0200 Subject: MWL#89 - Post-review fixes. Intermediate commit to address review point 1.6. - Fixed valgrind warnings --- sql/sql_select.h | 13 +++++++++++-- 1 file changed, 11 insertions(+), 2 deletions(-) (limited to 'sql/sql_select.h') 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 *fields; List 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 */ -- cgit v1.2.1