From 3019d3972932931d9c4a14bec4183b232355cdcf Mon Sep 17 00:00:00 2001 From: Igor Babaev Date: Sun, 11 Oct 2009 21:59:34 -0700 Subject: The main patch for WL#24: "index_merge: fair choice between index_merge union and range access" mysql-test/include/world.inc: A new include file to upload the world database. mysql-test/include/world_schema.inc: A new include file to create tables of the world database. mysql-test/r/index_merge_myisam.result: The results for test cases testing the optimizations added in WL#24 for MyISAM. mysql-test/r/range_vs_index_merge.result: The results for test cases testing the optimizations added in WL#24 for InnoDB. mysql-test/t/range_vs_index_merge.test: Test cases to test the optimizations added in WL#24 for MyISAM. mysql-test/t/range_vs_index_merge_innodb.test: Test cases to test the optimizations added in WL#24 for InnoDB. sql/sql_list.h: Fixed a bug that did not allow adding a non-empty list to an empty list. --- sql/sql_list.h | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'sql/sql_list.h') diff --git a/sql/sql_list.h b/sql/sql_list.h index 93cdd20c299..cbe94b9f226 100644 --- a/sql/sql_list.h +++ b/sql/sql_list.h @@ -168,6 +168,14 @@ public: { if (!list->is_empty()) { +#if 0 +#else + if (is_empty()) + { + *this= *list; + return; + } +#endif *last= list->first; last= list->last; elements+= list->elements; -- cgit v1.2.1 From 709a0a131021135e9fb7a2095fcfcbc223dfb126 Mon Sep 17 00:00:00 2001 From: Igor Babaev Date: Wed, 26 May 2010 13:18:18 -0700 Subject: MWL#106: Backport optimizations for derived tables and views. The main consolidated patch. --- sql/sql_list.h | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-) (limited to 'sql/sql_list.h') diff --git a/sql/sql_list.h b/sql/sql_list.h index 93cdd20c299..f1b71b00cf6 100644 --- a/sql/sql_list.h +++ b/sql/sql_list.h @@ -168,6 +168,11 @@ public: { if (!list->is_empty()) { + if (is_empty()) + { + *this= *list; + return; + } *last= list->first; last= list->last; elements+= list->elements; @@ -188,11 +193,13 @@ public: list_node *node= first; list_node *list_first= list->first; elements=0; - while (node && node != list_first) + while (node != list_first) { prev= &node->next; node= node->next; elements++; + if (node == &end_of_list) + return; } *prev= *last; last= prev; -- cgit v1.2.1 From 3a61fbe972f96a8eed3ed9d51c2c3594860bbc53 Mon Sep 17 00:00:00 2001 From: Igor Babaev Date: Sat, 11 Sep 2010 12:18:58 -0700 Subject: WL#24: post review fixes. --- sql/sql_list.h | 3 --- 1 file changed, 3 deletions(-) (limited to 'sql/sql_list.h') diff --git a/sql/sql_list.h b/sql/sql_list.h index 6a568c2dfd7..69798079a0f 100644 --- a/sql/sql_list.h +++ b/sql/sql_list.h @@ -235,14 +235,11 @@ public: { if (!list->is_empty()) { -#if 0 -#else if (is_empty()) { *this= *list; return; } -#endif *last= list->first; last= list->last; elements+= list->elements; -- cgit v1.2.1 From 84a0c9b2a245a166b87296b0aa9218730be89c21 Mon Sep 17 00:00:00 2001 From: Igor Babaev Date: Sat, 15 Jan 2011 11:14:36 -0800 Subject: Fixed LP bug #698882. Made sure that the optimal fields are used by TABLE_REF objects when building index access keys to joined tables. Fixed a bug in the template function that sorts the elements of a list using the bubble sort algorithm. The bug caused poor performance of the function. Also added an optimization that skips comparison with the most heavy elements that has been already properly placed in the list. Made the comparison of the fields belonging to the same Item_equal more granular: fields belonging to the same table are also ordered according to some rules. --- sql/sql_list.h | 28 ++++++++++++++++------------ 1 file changed, 16 insertions(+), 12 deletions(-) (limited to 'sql/sql_list.h') diff --git a/sql/sql_list.h b/sql/sql_list.h index 76b3145f24d..2dade14f211 100644 --- a/sql/sql_list.h +++ b/sql/sql_list.h @@ -515,36 +515,40 @@ public: /* - Exchange sort algorithm for List. + Bubble sort algorithm for List. + This sort function is supposed to be used only for very short list. + Currently it is used for the lists of Item_equal objects and + for some lists in the table elimination algorithms. In both + cases the sorted lists are very short. */ + template -inline void exchange_sort(List *list_to_sort, - int (*sort_func)(T *a, T *b, void *arg), void *arg) +inline void bubble_sort(List *list_to_sort, + int (*sort_func)(T *a, T *b, void *arg), void *arg) { bool swap; + T **ref1= 0; + T **ref2= 0; List_iterator it(*list_to_sort); do { + T **last_ref= ref1; T *item1= it++; - T **ref1= it.ref(); + ref1= it.ref(); T *item2; swap= FALSE; - while ((item2= it++)) + while ((item2= it++) && (ref2= it.ref()) != last_ref) { - T **ref2= it.ref(); if (sort_func(item1, item2, arg) < 0) { - T *item= *ref1; - *ref1= *ref2; - *ref2= item; + *ref1= item2; + *ref2= item1; swap= TRUE; } else - { item1= item2; - ref1= ref2; - } + ref1= ref2; } it.rewind(); } while (swap); -- cgit v1.2.1 From 0f4236659c2af3720d57255e224b3a8bb4f1d697 Mon Sep 17 00:00:00 2001 From: unknown Date: Thu, 28 Apr 2011 17:15:05 +0300 Subject: Fix LP BUG#718593 Analysis: Build_equal_items_for_cond() rewrites the WHERE clause in such a way, that it may merge the list join->cond_equal->current_level with the list of child Items in an AND condition of the WHERE clause. The place where this is done is: static COND *build_equal_items_for_cond(THD *thd, COND *cond, COND_EQUAL *inherited) { ... if (and_level) { args->concat(&eq_list); args->concat((List *)&cond_equal.current_level); } ... } As a result, later transformations on the WHERE clause may change the structure of the list join->cond_equal->current_level without knowing this. Specifically in this bug, Item_in_subselect::inject_in_to_exists_cond creates a new AND of the old WHERE clause and the IN->EXISTS conditions. It then calls fix_fields() for the new AND. Among other things, fix_fields flattens all nested ANDs into one by merging the AND argument lists. When there is a cond_equal for the JOIN, its list of Item_equal objects is attached to the end of the original AND. When a lower-level AND is merged into the top-level one, the argument list of the lower-level AND is concatenated to the list of multiple equalities in the upper-level AND. As a result, when substitute_for_best_equal_field processes the multiple equalities, it turns out that the multiple equality list contains the Items from the lower-level AND which were concatenated to the end of the join->cond_equal->current_level list. This results in a crash because this list must not contain any other Items except for the previously found Item_equal ones. Solution: When performing IN->EXIST predicate injection, and the where clause is an AND, detach the list of Item_equal objects before calling fix_fields on the injected where clause. After fix_fields is done, reattach back the multiple equalities list to the end of the argument list of the new AND. --- sql/sql_list.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'sql/sql_list.h') diff --git a/sql/sql_list.h b/sql/sql_list.h index 2dade14f211..e90f16aeb99 100644 --- a/sql/sql_list.h +++ b/sql/sql_list.h @@ -260,7 +260,7 @@ public: list_node *node= first; list_node *list_first= list->first; elements=0; - while (node && node != list_first) + while (node->info && node != list_first) { prev= &node->next; node= node->next; -- cgit v1.2.1 From 742dfc92a2de5ae9bc8b4d115d2bbd6dbb401bcc Mon Sep 17 00:00:00 2001 From: unknown Date: Mon, 23 May 2011 10:56:05 +0300 Subject: MWL#89: Address review feedback (by Sergey Petrunia) mysql-test/r/subselect4.result: Moved test case for LP BUG#718593 into the correct test file subselect_mat_cost_bugs.test. mysql-test/t/subselect4.test: Moved test case for LP BUG#718593 into the correct test file subselect_mat_cost_bugs.test. --- sql/sql_list.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'sql/sql_list.h') diff --git a/sql/sql_list.h b/sql/sql_list.h index e90f16aeb99..7d9f3d26ec8 100644 --- a/sql/sql_list.h +++ b/sql/sql_list.h @@ -260,7 +260,7 @@ public: list_node *node= first; list_node *list_first= list->first; elements=0; - while (node->info && node != list_first) + while (node != &end_of_list && node != list_first) { prev= &node->next; node= node->next; -- cgit v1.2.1 From 99cce18955dfb43d7d69c7de704cb29f047f8da5 Mon Sep 17 00:00:00 2001 From: unknown Date: Tue, 19 Jul 2011 23:19:10 +0300 Subject: Fixed LP BUG#800696. The problem was that optimizer removes some outer references (it they are constant for example) and the list of outer items built during prepare phase is not actual during execution phase when we need it as the cache parameters. First solution was use pointer on pointer on outer reference Item and initialize temporary table on demand. This solved most problem except case when optimiser also reduce Item which contains outer references ('OR' in this bug test suite). The solution is to build the list of outer reference items on execution phase (after optimization) on demand (just before temporary table creation) by walking Item tree and finding outer references among Item_ident (Item_field/Item_ref) and Item_sum items. Removed depends_on list (because it is not neede any mnore for the cache, in the place where it was used it replaced with upper_refs). Added processor (collect_outer_ref_processor) and get_cache_parameters() methods to collect outer references (or other expression parameters in future). mysql-test/r/subselect_cache.result: A new test added. mysql-test/r/subselect_scache.result: Changes in creating the cache and its paremeters order or adding arguments of aggregate function (which is a parameter also, but this has no influence on the result). mysql-test/t/subselect_cache.test: Added a new test. sql/item.cc: depends_on removed. Added processor (collect_outer_ref_processor) and get_cache_parameters() methods to collect outer references. Item_cache_wrapper collect parameters befor initialization of its cache. sql/item.h: depends_on removed. Added processor (collect_outer_ref_processor) and get_cache_parameters() methods to collect outer references. sql/item_cmpfunc.cc: depends_on removed. Added processor (collect_outer_ref_processor) to collect outer references. sql/item_cmpfunc.h: Added processor (collect_outer_ref_processor) to collect outer references. sql/item_subselect.cc: depends_on removed. Added processor get_cache_parameters() method to collect outer references. sql/item_subselect.h: depends_on removed. Added processor get_cache_parameters() method to collect outer references. sql/item_sum.cc: Added processor (collect_outer_ref_processor) method to collect outer references. sql/item_sum.h: Added processor (collect_outer_ref_processor) and get_cache_parameters() methods to collect outer references. sql/opt_range.cc: depends_on removed. sql/sql_base.cc: depends_on removed. sql/sql_class.h: New iterator added. sql/sql_expression_cache.cc: Build of list of items resolved in outer query done just before creating expression cache on the first execution of the subquery which removes influence of optimizer removing items (all optimization already done). sql/sql_expression_cache.h: Build of list of items resolved in outer query done just before creating expression cache on the first execution of the subquery which removes influence of optimizer removing items (all optimization already done). sql/sql_lex.cc: depends_on removed. sql/sql_lex.h: depends_on removed. sql/sql_list.h: Added add_unique method to add only unique elements to the list. sql/sql_select.cc: Support of new Item list added. sql/sql_select.h: Support of new Item list added. --- sql/sql_list.h | 13 +++++++++++++ 1 file changed, 13 insertions(+) (limited to 'sql/sql_list.h') diff --git a/sql/sql_list.h b/sql/sql_list.h index 38235a10c18..50673921aeb 100644 --- a/sql/sql_list.h +++ b/sql/sql_list.h @@ -152,6 +152,7 @@ struct list_node :public Sql_alloc } }; +typedef bool List_eq(void *a, void *b); extern MYSQL_PLUGIN_IMPORT list_node end_of_list; @@ -295,6 +296,16 @@ public: inline void **head_ref() { return first != &end_of_list ? &first->info : 0; } inline bool is_empty() { return first == &end_of_list ; } inline list_node *last_ref() { return &end_of_list; } + inline bool add_unique(void *info, List_eq *eq) + { + list_node *node= first; + for (; + node != &end_of_list && (!(*eq)(node->info, info)); + node= node->next) ; + if (node == &end_of_list) + return push_back(info); + return 1; + } friend class base_list_iterator; friend class error_list; friend class error_list_iterator; @@ -465,6 +476,8 @@ public: inline void concat(List *list) { base_list::concat(list); } inline void disjoin(List *list) { base_list::disjoin(list); } inline void prepand(List *list) { base_list::prepand(list); } + inline bool add_unique(T *a, bool (*eq)(T *a, T *b)) + { return base_list::add_unique(a, (List_eq *)eq); } void delete_elements(void) { list_node *element,*next; -- cgit v1.2.1