diff options
Diffstat (limited to 'sql/opt_range.cc')
| -rw-r--r-- | sql/opt_range.cc | 3887 |
1 files changed, 3177 insertions, 710 deletions
diff --git a/sql/opt_range.cc b/sql/opt_range.cc index e0505e2d65c..e5f544747e5 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -1,4 +1,4 @@ -/* Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved. +/* Copyright (c) 2000, 2010, Oracle and/or its affiliates. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -310,6 +310,11 @@ public: uint8 part; // Which key part uint8 maybe_null; /* + The ordinal number the least significant component encountered in + the ranges of the SEL_ARG tree (the first component has number 1) + */ + uint16 max_part_no; + /* Number of children of this element in the RB-tree, plus 1 for this element itself. */ @@ -342,8 +347,9 @@ public: SEL_ARG(Field *field, uint8 part, uchar *min_value, uchar *max_value, uint8 min_flag, uint8 max_flag, uint8 maybe_flag); SEL_ARG(enum Type type_arg) - :min_flag(0),elements(1),use_count(1),left(0),right(0),next_key_part(0), - color(BLACK), type(type_arg) + :min_flag(0), max_part_no(0) /* first key part means 1. 0 mean 'no parts'*/, + elements(1),use_count(1),left(0),right(0), + next_key_part(0), color(BLACK), type(type_arg) {} inline bool is_same(SEL_ARG *arg) { @@ -566,6 +572,11 @@ public: pos->increment_use_count(count); } } + void incr_refs() + { + increment_use_count(1); + use_count++; + } void free_tree() { for (SEL_ARG *pos=first(); pos ; pos=pos->next) @@ -627,7 +638,100 @@ public: class SEL_IMERGE; +#define CLONE_KEY1_MAYBE 1 +#define CLONE_KEY2_MAYBE 2 +#define swap_clone_flag(A) ((A & 1) << 1) | ((A & 2) >> 1) + +/* + While objects of the class SEL_ARG represent ranges for indexes or + index infixes (including ranges for index prefixes and index suffixes), + objects of the class SEL_TREE represent AND/OR formulas of such ranges. + Currently an AND/OR formula represented by a SEL_TREE object can have + at most three levels: + + <SEL_TREE formula> ::= + [ <SEL_RANGE_TREE formula> AND ] + [ <SEL_IMERGE formula> [ AND <SEL_IMERGE formula> ...] ] + + <SEL_RANGE_TREE formula> ::= + <SEL_ARG formula> [ AND <SEL_ARG_formula> ... ] + + <SEL_IMERGE formula> ::= + <SEL_RANGE_TREE formula> [ OR <SEL_RANGE_TREE formula> ] + + As we can see from the above definitions: + - SEL_RANGE_TREE formula is a conjunction of SEL_ARG formulas + - SEL_IMERGE formula is a disjunction of SEL_RANGE_TREE formulas + - SEL_TREE formula is a conjunction of a SEL_RANGE_TREE formula + and SEL_IMERGE formulas. + It's required above that a SEL_TREE formula has at least one conjunct. + + Usually we will consider normalized SEL_RANGE_TREE formulas where we use + TRUE as conjunct members for those indexes whose SEL_ARG trees are empty. + + We will call an SEL_TREE object simply 'tree'. + The part of a tree that represents SEL_RANGE_TREE formula is called + 'range part' of the tree while the remaining part is called 'imerge part'. + If a tree contains only a range part then we call such a tree 'range tree'. + Components of a range tree that represent SEL_ARG formulas are called ranges. + If a tree does not contain any range part we call such a tree 'imerge tree'. + Components of the imerge part of a tree that represent SEL_IMERGE formula + are called imerges. + + Usually we'll designate: + SEL_TREE formulas by T_1,...,T_k + SEL_ARG formulas by R_1,...,R_k + SEL_RANGE_TREE formulas by RT_1,...,RT_k + SEL_IMERGE formulas by M_1,...,M_k + Accordingly we'll use: + t_1,...,t_k - to designate trees representing T_1,...,T_k + r_1,...,r_k - to designate ranges representing R_1,...,R_k + rt_1,...,r_tk - to designate range trees representing RT_1,...,RT_k + m_1,...,m_k - to designate imerges representing M_1,...,M_k + + SEL_TREE objects are usually built from WHERE conditions or + ON expressions. + A SEL_TREE object always represents an inference of the condition it is + built from. Therefore, if a row satisfies a SEL_TREE formula it also + satisfies the condition it is built from. + + The following transformations of tree t representing SEL_TREE formula T + yield a new tree t1 thar represents an inference of T: T=>T1. + (1) remove any of SEL_ARG tree from the range part of t + (2) remove any imerge from the tree t + (3) remove any of SEL_ARG tree from any range tree contained + in any imerge of tree + + Since the basic blocks of any SEL_TREE objects are ranges, SEL_TREE + objects in many cases can be effectively used to filter out a big part + of table rows that do not satisfy WHERE/IN conditions utilizing + only single or multiple range index scans. + + A single range index scan is constructed for a range tree that contains + only one SEL_ARG object for an index or an index prefix. + An index intersection scan can be constructed for a range tree + that contains several SEL_ARG objects. Currently index intersection + scans are constructed only for single-point ranges. + An index merge scan is constructed for a imerge tree that contains only + one imerge. If range trees of this imerge contain only single-point merges + than a union of index intersections can be built. + + Usually the tree built by the range optimizer for a query table contains + more than one range in the range part, and additionally may contain some + imerges in the imerge part. The range optimizer evaluates all of them one + by one and chooses the range or the imerge that provides the cheapest + single or multiple range index scan of the table. According to rules + (1)-(3) this scan always filter out only those rows that do not satisfy + the query conditions. + + For any condition the SEL_TREE object for it is built in a bottom up + manner starting from the range trees for the predicates. The tree_and + function builds a tree for any conjunction of formulas from the trees + for its conjuncts. The tree_or function builds a tree for any disjunction + of formulas from the trees for its disjuncts. +*/ + class SEL_TREE :public Sql_alloc { public: @@ -643,7 +747,7 @@ public: keys_map.clear_all(); bzero((char*) keys,sizeof(keys)); } - SEL_TREE(SEL_TREE *arg, RANGE_OPT_PARAM *param); + SEL_TREE(SEL_TREE *arg, bool without_merges, RANGE_OPT_PARAM *param); /* Note: there may exist SEL_TREE objects with sel_tree->type=KEY and keys[i]=0 for all i. (SergeyP: it is not clear whether there is any @@ -663,9 +767,15 @@ public: key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */ uint n_ror_scans; /* number of set bits in ror_scans_map */ + struct st_index_scan_info **index_scans; /* list of index scans */ + struct st_index_scan_info **index_scans_end; /* last index scan */ + struct st_ror_scan_info **ror_scans; /* list of ROR key scans */ struct st_ror_scan_info **ror_scans_end; /* last ROR scan */ /* Note that #records for each key scan is stored in table->quick_rows */ + + bool without_ranges() { return keys_map.is_clear_all(); } + bool without_imerges() { return merges.is_empty(); } }; class RANGE_OPT_PARAM @@ -719,12 +829,13 @@ public: /* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */ uint alloced_sel_args; bool force_default_mrr; + KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */ }; class PARAM : public RANGE_OPT_PARAM { public: - KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */ + ha_rows quick_rows[MAX_KEY]; longlong baseflag; uint max_key_part, range_count; @@ -751,9 +862,11 @@ class TABLE_READ_PLAN; class TRP_RANGE; class TRP_ROR_INTERSECT; class TRP_ROR_UNION; - class TRP_ROR_INDEX_MERGE; + class TRP_INDEX_INTERSECT; + class TRP_INDEX_MERGE; class TRP_GROUP_MIN_MAX; +struct st_index_scan_info; struct st_ror_scan_info; static SEL_TREE * get_mm_parts(RANGE_OPT_PARAM *param,COND *cond_func,Field *field, @@ -778,6 +891,9 @@ static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree, bool update_tbl_stats, double read_time); static +TRP_INDEX_INTERSECT *get_best_index_intersect(PARAM *param, SEL_TREE *tree, + double read_time); +static TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree, double read_time, bool *are_all_covering); @@ -789,6 +905,10 @@ static TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge, double read_time); static +TABLE_READ_PLAN *merge_same_index_scans(PARAM *param, SEL_IMERGE *imerge, + TRP_INDEX_MERGE *imerge_trp, + double read_time); +static TRP_GROUP_MIN_MAX *get_best_group_min_max(PARAM *param, SEL_TREE *tree, double read_time); @@ -801,11 +921,15 @@ static void print_ror_scans_arr(TABLE *table, const char *msg, static void print_quick(QUICK_SELECT_I *quick, const key_map *needed_reg); #endif -static SEL_TREE *tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2); -static SEL_TREE *tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2); +static SEL_TREE *tree_and(RANGE_OPT_PARAM *param, + SEL_TREE *tree1, SEL_TREE *tree2); +static SEL_TREE *tree_or(RANGE_OPT_PARAM *param, + SEL_TREE *tree1,SEL_TREE *tree2); static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2); -static SEL_ARG *key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2); -static SEL_ARG *key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, +static SEL_ARG *key_or(RANGE_OPT_PARAM *param, + SEL_ARG *key1, SEL_ARG *key2); +static SEL_ARG *key_and(RANGE_OPT_PARAM *param, + SEL_ARG *key1, SEL_ARG *key2, uint clone_flag); static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1); bool get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key, @@ -816,11 +940,27 @@ static bool eq_tree(SEL_ARG* a,SEL_ARG *b); static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE); static bool null_part_in_key(KEY_PART *key_part, const uchar *key, uint length); -bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, RANGE_OPT_PARAM* param); static bool is_key_scan_ror(PARAM *param, uint keynr, uint8 nparts); #include "opt_range_mrr.cc" +static bool sel_trees_have_common_keys(SEL_TREE *tree1, SEL_TREE *tree2, + key_map *common_keys); +static void eliminate_single_tree_imerges(RANGE_OPT_PARAM *param, + SEL_TREE *tree); + +static bool sel_trees_can_be_ored(RANGE_OPT_PARAM* param, + SEL_TREE *tree1, SEL_TREE *tree2, + key_map *common_keys); +static bool sel_trees_must_be_ored(RANGE_OPT_PARAM* param, + SEL_TREE *tree1, SEL_TREE *tree2, + key_map common_keys); +static int and_range_trees(RANGE_OPT_PARAM *param, + SEL_TREE *tree1, SEL_TREE *tree2, + SEL_TREE *result); +static bool remove_nonrange_trees(RANGE_OPT_PARAM *param, SEL_TREE *tree); + + /* SEL_IMERGE is a list of possible ways to do index merge, i.e. it is a condition in the following form: @@ -850,23 +990,39 @@ public: trees_next(trees), trees_end(trees + PREALLOCED_TREES) {} - SEL_IMERGE (SEL_IMERGE *arg, RANGE_OPT_PARAM *param); + SEL_IMERGE (SEL_IMERGE *arg, uint cnt, RANGE_OPT_PARAM *param); int or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree); - int or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree); - int or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge); + bool have_common_keys(RANGE_OPT_PARAM *param, SEL_TREE *tree); + int and_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree, + SEL_IMERGE *new_imerge); + int or_sel_tree_with_checks(RANGE_OPT_PARAM *param, + uint n_init_trees, + SEL_TREE *new_tree, + bool is_first_check_pass, + bool *is_last_check_pass); + int or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, + uint n_init_trees, + SEL_IMERGE* imerge, + bool is_first_check_pass, + bool *is_last_check_pass); }; /* - Add SEL_TREE to this index_merge without any checks, + Add a range tree to the range trees of this imerge - NOTES - This function implements the following: - (x_1||...||x_N) || t = (x_1||...||x_N||t), where x_i, t are SEL_TREEs + SYNOPSIS + or_sel_tree() + param Context info for the operation + tree SEL_TREE to add to this imerge + + DESCRIPTION + The function just adds the range tree 'tree' to the range trees + of this imerge. RETURN - 0 - OK - -1 - Out of memory. + 0 if the operation is success + -1 if the function runs out memory */ int SEL_IMERGE::or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree) @@ -891,96 +1047,303 @@ int SEL_IMERGE::or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree) /* - Perform OR operation on this SEL_IMERGE and supplied SEL_TREE new_tree, - combining new_tree with one of the trees in this SEL_IMERGE if they both - have SEL_ARGs for the same key. + Check if any of the range trees of this imerge intersects with a given tree SYNOPSIS - or_sel_tree_with_checks() - param PARAM from SQL_SELECT::test_quick_select - new_tree SEL_TREE with type KEY or KEY_SMALLER. + have_common_keys() + param Context info for the function + tree SEL_TREE intersection with the imerge range trees is checked for - NOTES - This does the following: - (t_1||...||t_k)||new_tree = - either - = (t_1||...||t_k||new_tree) - or - = (t_1||....||(t_j|| new_tree)||...||t_k), - - where t_i, y are SEL_TREEs. - new_tree is combined with the first t_j it has a SEL_ARG on common - key with. As a consequence of this, choice of keys to do index_merge - read may depend on the order of conditions in WHERE part of the query. + DESCRIPTION + The function checks whether there is any range tree rt_i in this imerge + such that there are some indexes for which ranges are defined in both + rt_i and the range part of the SEL_TREE tree. + To check this the function calls the function sel_trees_have_common_keys. + RETURN + TRUE if there are such range trees in this imerge + FALSE otherwise +*/ + +bool SEL_IMERGE::have_common_keys(RANGE_OPT_PARAM *param, SEL_TREE *tree) +{ + for (SEL_TREE** or_tree= trees, **bound= trees_next; + or_tree != bound; or_tree++) + { + key_map common_keys; + if (sel_trees_have_common_keys(*or_tree, tree, &common_keys)) + return TRUE; + } + return FALSE; +} + + +/* + Perform AND operation for this imerge and the range part of a tree + + SYNOPSIS + and_sel_tree() + param Context info for the operation + tree SEL_TREE for the second operand of the operation + new_imerge OUT imerge for the result of the operation + + DESCRIPTION + This function performs AND operation for this imerge m and the + range part of the SEL_TREE tree rt. In other words the function + pushes rt into this imerge. The resulting imerge is returned in + the parameter new_imerge. + If this imerge m represent the formula + RT_1 OR ... OR RT_k + then the resulting imerge of the function represents the formula + (RT_1 AND RT) OR ... OR (RT_k AND RT) + The function calls the function and_range_trees to construct the + range tree representing (RT_i AND RT). + + NOTE + The function may return an empty imerge without any range trees. + This happens when each call of and_range_trees returns an + impossible range tree (SEL_TREE::IMPOSSIBLE). + Example: (key1 < 2 AND key2 > 10) AND (key1 > 4 OR key2 < 6). + RETURN - 0 OK - 1 One of the trees was combined with new_tree to SEL_TREE::ALWAYS, - and (*this) should be discarded. - -1 An error occurred. + 0 if the operation is a success + -1 otherwise: there is not enough memory to perform the operation */ -int SEL_IMERGE::or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree) +int SEL_IMERGE::and_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree, + SEL_IMERGE *new_imerge) { - for (SEL_TREE** tree = trees; - tree != trees_next; - tree++) + for (SEL_TREE** or_tree= trees; or_tree != trees_next; or_tree++) { - if (sel_trees_can_be_ored(*tree, new_tree, param)) + SEL_TREE *res_or_tree= 0; + if (!(res_or_tree= new SEL_TREE())) + return (-1); + if (!and_range_trees(param, *or_tree, tree, res_or_tree)) { - *tree = tree_or(param, *tree, new_tree); - if (!*tree) - return 1; - if (((*tree)->type == SEL_TREE::MAYBE) || - ((*tree)->type == SEL_TREE::ALWAYS)) + if (new_imerge->or_sel_tree(param, res_or_tree)) + return (-1); + } + } + return 0; +} + + +/* + Perform OR operation on this imerge and the range part of a tree + + SYNOPSIS + or_sel_tree_with_checks() + param Context info for the operation + n_trees Number of trees in this imerge to check for oring + tree SEL_TREE whose range part is to be ored + is_first_check_pass <=> the first call of the function for this imerge + is_last_check_pass OUT <=> no more calls of the function for this imerge + + DESCRIPTION + The function performs OR operation on this imerge m and the range part + of the SEL_TREE tree rt. It always replaces this imerge with the result + of the operation. + + The operation can be performed in two different modes: with + is_first_check_pass==TRUE and is_first_check_pass==FALSE, transforming + this imerge differently. + + Given this imerge represents the formula + RT_1 OR ... OR RT_k: + + 1. In the first mode, when is_first_check_pass==TRUE : + 1.1. If rt must be ored(see the function sel_trees_must_be_ored) with + some rt_j (there may be only one such range tree in the imerge) + then the function produces an imerge representing the formula + RT_1 OR ... OR (RT_j OR RT) OR ... OR RT_k, + where the tree for (RT_j OR RT) is built by oring the pairs + of SEL_ARG trees for the corresponding indexes + 1.2. Otherwise the function produces the imerge representing the formula: + RT_1 OR ... OR RT_k OR RT. + + 2. In the second mode, when is_first_check_pass==FALSE : + 2.1. For each rt_j in the imerge that can be ored (see the function + sel_trees_can_be_ored), but not must be ored, with rt the function + replaces rt_j for a range tree such that for each index for which + ranges are defined in both in rt_j and rt the tree contains the + result of oring of these ranges. + 2.2. In other cases the function does not produce any imerge. + + When is_first_check==TRUE the function returns FALSE in the parameter + is_last_check_pass if there is no rt_j such that rt_j can be ored with rt, + but, at the same time, it's not true that rt_j must be ored with rt. + When is_first_check==FALSE the function always returns FALSE in the + parameter is_last_check_pass. + + RETURN + 1 The result of oring of rt_j and rt that must be ored returns the + the range tree with type==SEL_TREE::ALWAYS + (in this case the imerge m should be discarded) + -1 The function runs out of memory + 0 in all other cases +*/ + +int SEL_IMERGE::or_sel_tree_with_checks(RANGE_OPT_PARAM *param, + uint n_trees, + SEL_TREE *tree, + bool is_first_check_pass, + bool *is_last_check_pass) +{ + bool was_ored= FALSE; + *is_last_check_pass= TRUE; + SEL_TREE** or_tree = trees; + for (uint i= 0; i < n_trees; i++, or_tree++) + { + SEL_TREE *result= 0; + key_map result_keys; + key_map ored_keys; + if (sel_trees_can_be_ored(param, *or_tree, tree, &ored_keys)) + { + bool must_be_ored= sel_trees_must_be_ored(param, *or_tree, tree, + ored_keys); + if (must_be_ored || !is_first_check_pass) + { + result_keys.clear_all(); + result= *or_tree; + for (uint key_no= 0; key_no < param->keys; key_no++) + { + if (!ored_keys.is_set(key_no)) + { + result->keys[key_no]= 0; + continue; + } + SEL_ARG *key1= (*or_tree)->keys[key_no]; + SEL_ARG *key2= tree->keys[key_no]; + key2->incr_refs(); + if ((result->keys[key_no]= key_or(param, key1, key2))) + { + + result_keys.set_bit(key_no); +#ifdef EXTRA_DEBUG + if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS) + { + key1= result->keys[key_no]; + (key1)->test_use_count(key1); + } +#endif + } + } + } + else if(is_first_check_pass) + *is_last_check_pass= FALSE; + } + + if (result) + { + if (result_keys.is_clear_all()) + result->type= SEL_TREE::ALWAYS; + *is_last_check_pass= TRUE; + if ((result->type == SEL_TREE::MAYBE) || + (result->type == SEL_TREE::ALWAYS)) return 1; /* SEL_TREE::IMPOSSIBLE is impossible here */ - return 0; + result->keys_map= result_keys; + *or_tree= result; + if (is_first_check_pass) + return 0; + was_ored= TRUE; } } + if (was_ored) + return 0; - /* New tree cannot be combined with any of existing trees. */ - return or_sel_tree(param, new_tree); + if (!*is_last_check_pass && + !(tree= new SEL_TREE(tree, FALSE, param))) + return (-1); + return or_sel_tree(param, tree); } /* - Perform OR operation on this index_merge and supplied index_merge list. + Perform OR operation on this imerge and and another imerge + + SYNOPSIS + or_sel_imerge_with_checks() + param Context info for the operation + n_trees Number of trees in this imerge to check for oring + imerge The second operand of the operation + is_first_check_pass <=> the first call of the function for this imerge + is_last_check_pass OUT <=> no more calls of the function for this imerge + DESCRIPTION + For each range tree rt from 'imerge' the function calls the method + SEL_IMERGE::or_sel_tree_with_checks that performs OR operation on this + SEL_IMERGE object m and the tree rt. The mode of the operation is + specified by the parameter is_first_check_pass. Each call of + SEL_IMERGE::or_sel_tree_with_checks transforms this SEL_IMERGE object m. + The function returns FALSE in the prameter is_last_check_pass if + at least one of the calls of SEL_IMERGE::or_sel_tree_with_checks + returns FALSE as the value of its last parameter. + RETURN - 0 - OK - 1 - One of conditions in result is always TRUE and this SEL_IMERGE - should be discarded. - -1 - An error occurred + 1 One of the calls of SEL_IMERGE::or_sel_tree_with_checks returns 1. + (in this case the imerge m should be discarded) + -1 The function runs out of memory + 0 in all other cases */ -int SEL_IMERGE::or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge) -{ - for (SEL_TREE** tree= imerge->trees; - tree != imerge->trees_next; - tree++) - { - if (or_sel_tree_with_checks(param, *tree)) - return 1; +int SEL_IMERGE::or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, + uint n_trees, + SEL_IMERGE* imerge, + bool is_first_check_pass, + bool *is_last_check_pass) +{ + *is_last_check_pass= TRUE; + SEL_TREE** tree= imerge->trees; + SEL_TREE** tree_end= imerge->trees_next; + for ( ; tree < tree_end; tree++) + { + uint rc; + bool is_last= TRUE; + rc= or_sel_tree_with_checks(param, n_trees, *tree, + is_first_check_pass, &is_last); + if (!is_last) + *is_last_check_pass= FALSE; + if (rc) + return rc; } return 0; } -SEL_TREE::SEL_TREE(SEL_TREE *arg, RANGE_OPT_PARAM *param): Sql_alloc() +/* + Copy constructor for SEL_TREE objects + + SYNOPSIS + SEL_TREE + arg The source tree for the constructor + without_merges <=> only the range part of the tree arg is copied + param Context info for the operation + + DESCRIPTION + The constructor creates a full copy of the SEL_TREE arg if + the prameter without_merges==FALSE. Otherwise a tree is created + that contains the copy only of the range part of the tree arg. +*/ + +SEL_TREE::SEL_TREE(SEL_TREE *arg, bool without_merges, + RANGE_OPT_PARAM *param): Sql_alloc() { keys_map= arg->keys_map; type= arg->type; - for (int idx= 0; idx < MAX_KEY; idx++) + for (uint idx= 0; idx < param->keys; idx++) { if ((keys[idx]= arg->keys[idx])) - keys[idx]->increment_use_count(1); + keys[idx]->incr_refs(); } + if (without_merges) + return; + List_iterator<SEL_IMERGE> it(arg->merges); for (SEL_IMERGE *el= it++; el; el= it++) { - SEL_IMERGE *merge= new SEL_IMERGE(el, param); + SEL_IMERGE *merge= new SEL_IMERGE(el, 0, param); if (!merge || merge->trees == merge->trees_next) { merges.empty(); @@ -991,7 +1354,23 @@ SEL_TREE::SEL_TREE(SEL_TREE *arg, RANGE_OPT_PARAM *param): Sql_alloc() } -SEL_IMERGE::SEL_IMERGE (SEL_IMERGE *arg, RANGE_OPT_PARAM *param) : Sql_alloc() +/* + Copy constructor for SEL_IMERGE objects + + SYNOPSIS + SEL_IMERGE + arg The source imerge for the constructor + cnt How many trees from arg are to be copied + param Context info for the operation + + DESCRIPTION + The cnt==0 then the constructor creates a full copy of the + imerge arg. Otherwise only the first cnt trees of the imerge + are copied. +*/ + +SEL_IMERGE::SEL_IMERGE(SEL_IMERGE *arg, uint cnt, + RANGE_OPT_PARAM *param) : Sql_alloc() { uint elements= (arg->trees_end - arg->trees); if (elements > PREALLOCED_TREES) @@ -1003,13 +1382,13 @@ SEL_IMERGE::SEL_IMERGE (SEL_IMERGE *arg, RANGE_OPT_PARAM *param) : Sql_alloc() else trees= &trees_prealloced[0]; - trees_next= trees; + trees_next= trees + (cnt ? cnt : arg->trees_next-arg->trees); trees_end= trees + elements; - for (SEL_TREE **tree = trees, **arg_tree= arg->trees; tree < trees_end; + for (SEL_TREE **tree = trees, **arg_tree= arg->trees; tree < trees_next; tree++, arg_tree++) { - if (!(*tree= new SEL_TREE(*arg_tree, param))) + if (!(*tree= new SEL_TREE(*arg_tree, FALSE, param))) goto mem_err; } @@ -1023,7 +1402,19 @@ mem_err: /* - Perform AND operation on two index_merge lists and store result in *im1. + Perform AND operation on two imerge lists + + SYNOPSIS + imerge_list_and_list() + param Context info for the operation + im1 The first imerge list for the operation + im2 The second imerge list for the operation + + DESCRIPTION + The function just appends the imerge list im2 to the imerge list im1 + + RETURN VALUE + none */ inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2) @@ -1033,73 +1424,242 @@ inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2) /* - Perform OR operation on 2 index_merge lists, storing result in first list. - - NOTES - The following conversion is implemented: - (a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) => - => (a_1||b_1). - - i.e. all conjuncts except the first one are currently dropped. - This is done to avoid producing N*K ways to do index_merge. - - If (a_1||b_1) produce a condition that is always TRUE, NULL is returned - and index_merge is discarded (while it is actually possible to try - harder). - - As a consequence of this, choice of keys to do index_merge read may depend - on the order of conditions in WHERE part of the query. + Perform OR operation on two imerge lists + SYNOPSIS + imerge_list_or_list() + param Context info for the operation + im1 The first imerge list for the operation + im2 The second imerge list for the operation + + DESCRIPTION + Assuming that the first imerge list represents the formula + F1= M1_1 AND ... AND M1_k1 + while the second imerge list represents the formula + F2= M2_1 AND ... AND M2_k2, + where M1_i= RT1_i_1 OR ... OR RT1_i_l1i (i in [1..k1]) + and M2_i = RT2_i_1 OR ... OR RT2_i_l2i (i in [1..k2]), + the function builds a list of imerges for some formula that can be + inferred from the formula (F1 OR F2). + + More exactly the function builds imerges for the formula (M1_1 OR M2_1). + Note that + (F1 OR F2) = (M1_1 AND ... AND M1_k1) OR (M2_1 AND ... AND M2_k2) = + AND (M1_i OR M2_j) (i in [1..k1], j in [1..k2]) => + M1_1 OR M2_1. + So (M1_1 OR M2_1) is indeed an inference formula for (F1 OR F2). + + To build imerges for the formula (M1_1 OR M2_1) the function invokes, + possibly twice, the method SEL_IMERGE::or_sel_imerge_with_checks + for the imerge m1_1. + At its first invocation the method SEL_IMERGE::or_sel_imerge_with_checks + performs OR operation on the imerge m1_1 and the range tree rt2_1_1 by + calling SEL_IMERGE::or_sel_tree_with_checks with is_first_pass_check==TRUE. + The resulting imerge of the operation is ored with the next range tree of + the imerge m2_1. This oring continues until the last range tree from + m2_1 has been ored. + At its second invocation the method SEL_IMERGE::or_sel_imerge_with_checks + performs the same sequence of OR operations, but now calling + SEL_IMERGE::or_sel_tree_with_checks with is_first_pass_check==FALSE. + + The imerges that the operation produces replace those in the list im1 + RETURN - 0 OK, result is stored in *im1 - other Error, both passed lists are unusable + 0 if the operation is a success + -1 if the function has run out of memory */ int imerge_list_or_list(RANGE_OPT_PARAM *param, List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2) { + + uint rc; + bool is_last_check_pass= FALSE; + SEL_IMERGE *imerge= im1->head(); + uint elems= imerge->trees_next-imerge->trees; im1->empty(); im1->push_back(imerge); - return imerge->or_sel_imerge_with_checks(param, im2->head()); + rc= imerge->or_sel_imerge_with_checks(param, elems, im2->head(), + TRUE, &is_last_check_pass); + if (rc) + { + if (rc == 1) + { + im1->empty(); + rc= 0; + } + return rc; + } + + if (!is_last_check_pass) + { + SEL_IMERGE* new_imerge= new SEL_IMERGE(imerge, elems, param); + if (new_imerge) + { + is_last_check_pass= TRUE; + rc= new_imerge->or_sel_imerge_with_checks(param, elems, im2->head(), + FALSE, &is_last_check_pass); + if (!rc) + im1->push_back(new_imerge); + } + } + return rc; } /* - Perform OR operation on index_merge list and key tree. + Perform OR operation for each imerge from a list and the range part of a tree + SYNOPSIS + imerge_list_or_tree() + param Context info for the operation + merges The list of imerges to be ored with the range part of tree + tree SEL_TREE whose range part is to be ored with the imerges + + DESCRIPTION + For each imerge mi from the list 'merges' the function performes OR + operation with mi and the range part of 'tree' rt, producing one or + two imerges. + + Given the merge mi represent the formula RTi_1 OR ... OR RTi_k, + the function forms the merges by the following rules: + + 1. If rt cannot be ored with any of the trees rti the function just + produces an imerge that represents the formula + RTi_1 OR ... RTi_k OR RT. + 2. If there exist a tree rtj that must be ored with rt the function + produces an imerge the represents the formula + RTi_1 OR ... OR (RTi_j OR RT) OR ... OR RTi_k, + where the range tree for (RTi_j OR RT) is constructed by oring the + SEL_ARG trees that must be ored. + 3. For each rti_j that can be ored with rt the function produces + the new tree rti_j' and substitutes rti_j for this new range tree. + + In any case the function removes mi from the list and then adds all + produced imerges. + + To build imerges by rules 1-3 the function calls the method + SEL_IMERGE::or_sel_tree_with_checks, possibly twice. With the first + call it passes TRUE for the third parameter of the function. + At this first call imerges by rules 1-2 are built. If the call + returns FALSE as the return value of its fourth parameter then the + function are called for the second time. At this call the imerge + of rule 3 is produced. + + If a call of SEL_IMERGE::or_sel_tree_with_checks returns 1 then + then it means that the produced tree contains an always true + range tree and the whole imerge can be discarded. + RETURN - 0 OK, result is stored in *im1. - other Error + 1 if no imerges are produced + 0 otherwise */ +static int imerge_list_or_tree(RANGE_OPT_PARAM *param, - List<SEL_IMERGE> *im1, + List<SEL_IMERGE> *merges, SEL_TREE *tree) { + SEL_IMERGE *imerge; - List_iterator<SEL_IMERGE> it(*im1); - bool tree_used= FALSE; + List<SEL_IMERGE> additional_merges; + List_iterator<SEL_IMERGE> it(*merges); + while ((imerge= it++)) { - SEL_TREE *or_tree; - if (tree_used) + bool is_last_check_pass; + int rc= 0; + int rc1= 0; + SEL_TREE *or_tree= new SEL_TREE (tree, FALSE, param); + if (or_tree) { - or_tree= new SEL_TREE (tree, param); - if (!or_tree || - (or_tree->keys_map.is_clear_all() && or_tree->merges.is_empty())) - return FALSE; + uint elems= imerge->trees_next-imerge->trees; + rc= imerge->or_sel_tree_with_checks(param, elems, or_tree, + TRUE, &is_last_check_pass); + if (!is_last_check_pass) + { + SEL_IMERGE *new_imerge= new SEL_IMERGE(imerge, elems, param); + if (new_imerge) + { + rc1= new_imerge->or_sel_tree_with_checks(param, elems, or_tree, + FALSE, &is_last_check_pass); + if (!rc1) + additional_merges.push_back(new_imerge); + } + } } - else - or_tree= tree; - - if (imerge->or_sel_tree_with_checks(param, or_tree)) + if (rc || rc1 || !or_tree) it.remove(); - tree_used= TRUE; } - return im1->is_empty(); + + merges->concat(&additional_merges); + return merges->is_empty(); +} + + +/* + Perform pushdown operation of the range part of a tree into given imerges + + SYNOPSIS + imerge_list_and_tree() + param Context info for the operation + merges IN/OUT List of imerges to push the range part of 'tree' into + tree SEL_TREE whose range part is to be pushed into imerges + + DESCRIPTION + For each imerge from the list merges the function pushes the range part + rt of 'tree' into the imerge. + More exactly if the imerge mi from the list represents the formula + RTi_1 OR ... OR RTi_k + the function bulds a new imerge that represents the formula + (RTi_1 AND RT) OR ... OR (RTi_k AND RT) + and adds this imerge to the list merges. + To perform this pushdown operation the function calls the method + SEL_IMERGE::and_sel_tree. + For any imerge mi the new imerge is not created if for each pair of + trees rti_j and rt the intersection of the indexes with defined ranges + is empty. + If the result of the pushdown operation for the imerge mi returns an + imerge with no trees then then not only nothing is added to the list + merges but mi itself is removed from the list. + + RETURN + 1 if no imerges are left in the list merges + 0 otherwise +*/ + +static +int imerge_list_and_tree(RANGE_OPT_PARAM *param, + List<SEL_IMERGE> *merges, + SEL_TREE *tree) +{ + SEL_IMERGE *imerge; + SEL_IMERGE *new_imerge= NULL; + List<SEL_IMERGE> new_merges; + List_iterator<SEL_IMERGE> it(*merges); + + while ((imerge= it++)) + { + if (!new_imerge) + new_imerge= new SEL_IMERGE(); + if (imerge->have_common_keys(param, tree) && + new_imerge && !imerge->and_sel_tree(param, tree, new_imerge)) + { + if (new_imerge->trees == new_imerge->trees_next) + it.remove(); + else + { + new_merges.push_back(new_imerge); + new_imerge= NULL; + } + } + } + imerge_list_and_list(&new_merges, merges); + *merges= new_merges; + return merges->is_empty(); } @@ -1133,7 +1693,7 @@ SQL_SELECT *make_select(TABLE *head, table_map const_tables, select->read_tables=read_tables; select->const_tables=const_tables; select->head=head; - select->cond=conds; + select->cond= conds; if (head->sort.io_cache) { @@ -1147,7 +1707,7 @@ SQL_SELECT *make_select(TABLE *head, table_map const_tables, } -SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0) +SQL_SELECT::SQL_SELECT() :quick(0),cond(0),pre_idx_push_select_cond(NULL),free_cond(0) { quick_keys.clear_all(); needed_reg.clear_all(); my_b_clear(&file); @@ -1271,7 +1831,7 @@ QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT() DBUG_PRINT("info", ("Freeing separate handler 0x%lx (free: %d)", (long) file, free_file)); file->ha_external_lock(current_thd, F_UNLCK); - file->close(); + file->ha_close(); delete file; } } @@ -1284,12 +1844,18 @@ QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT() DBUG_VOID_RETURN; } +/* + QUICK_INDEX_SORT_SELECT works as follows: + - Do index scans, accumulate rowids in the Unique object + (Unique will also sort and de-duplicate rowids) + - Use rowids from unique to run a disk-ordered sweep +*/ -QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(THD *thd_param, - TABLE *table) +QUICK_INDEX_SORT_SELECT::QUICK_INDEX_SORT_SELECT(THD *thd_param, + TABLE *table) :unique(NULL), pk_quick_select(NULL), thd(thd_param) { - DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT"); + DBUG_ENTER("QUICK_INDEX_SORT_SELECT::QUICK_INDEX_SORT_SELECT"); index= MAX_KEY; head= table; bzero(&read_record, sizeof(read_record)); @@ -1297,38 +1863,48 @@ QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(THD *thd_param, DBUG_VOID_RETURN; } -int QUICK_INDEX_MERGE_SELECT::init() +int QUICK_INDEX_SORT_SELECT::init() { - DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::init"); + DBUG_ENTER("QUICK_INDEX_SORT_SELECT::init"); DBUG_RETURN(0); } -int QUICK_INDEX_MERGE_SELECT::reset() +int QUICK_INDEX_SORT_SELECT::reset() { - DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::reset"); + DBUG_ENTER("QUICK_INDEX_SORT_SELECT::reset"); DBUG_RETURN(read_keys_and_merge()); } bool -QUICK_INDEX_MERGE_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick_sel_range) +QUICK_INDEX_SORT_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick_sel_range) { - /* - Save quick_select that does scan on clustered primary key as it will be - processed separately. - */ + DBUG_ENTER("QUICK_INDEX_SORT_SELECT::push_quick_back"); if (head->file->primary_key_is_clustered() && quick_sel_range->index == head->s->primary_key) + { + /* + A quick_select over a clustered primary key is handled specifically + Here we assume: + - PK columns are included in any other merged index + - Scan on the PK is disk-ordered. + (not meeting #2 will only cause performance degradation) + + We could treat clustered PK as any other index, but that would + be inefficient. There is no point in doing scan on + CPK, remembering the rowid, then making rnd_pos() call with + that rowid. + */ pk_quick_select= quick_sel_range; - else - return quick_selects.push_back(quick_sel_range); - return 0; + DBUG_RETURN(0); + } + DBUG_RETURN(quick_selects.push_back(quick_sel_range)); } -QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT() +QUICK_INDEX_SORT_SELECT::~QUICK_INDEX_SORT_SELECT() { List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects); QUICK_RANGE_SELECT* quick; - DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT"); + DBUG_ENTER("QUICK_INDEX_SORT_SELECT::~QUICK_INDEX_SORT_SELECT"); delete unique; quick_it.rewind(); while ((quick= quick_it++)) @@ -1342,7 +1918,6 @@ QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT() DBUG_VOID_RETURN; } - QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(THD *thd_param, TABLE *table, bool retrieve_full_rows, @@ -1451,7 +2026,7 @@ int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler) if (init() || reset()) { file->ha_external_lock(thd, F_UNLCK); - file->close(); + file->ha_close(); goto failure; } free_file= TRUE; @@ -1501,15 +2076,17 @@ failure: */ int QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(bool reuse_handler) { - List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects); - QUICK_RANGE_SELECT* quick; + List_iterator_fast<QUICK_SELECT_WITH_RECORD> quick_it(quick_selects); + QUICK_SELECT_WITH_RECORD *cur; + QUICK_RANGE_SELECT *quick; DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan"); /* Initialize all merged "children" quick selects */ DBUG_ASSERT(!need_to_fetch_row || reuse_handler); if (!need_to_fetch_row && reuse_handler) { - quick= quick_it++; + cur= quick_it++; + quick= cur->quick; /* There is no use of this->file. Use it for the first of merged range selects. @@ -1518,8 +2095,9 @@ int QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(bool reuse_handler) DBUG_RETURN(1); quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS); } - while ((quick= quick_it++)) + while ((cur= quick_it++)) { + quick= cur->quick; if (quick->init_ror_merged_scan(FALSE)) DBUG_RETURN(1); quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS); @@ -1551,10 +2129,10 @@ int QUICK_ROR_INTERSECT_SELECT::reset() if (!scans_inited && init_ror_merged_scan(TRUE)) DBUG_RETURN(1); scans_inited= TRUE; - List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); - QUICK_RANGE_SELECT *quick; - while ((quick= it++)) - quick->reset(); + List_iterator_fast<QUICK_SELECT_WITH_RECORD> it(quick_selects); + QUICK_SELECT_WITH_RECORD *qr; + while ((qr= it++)) + qr->quick->reset(); DBUG_RETURN(0); } @@ -1564,6 +2142,7 @@ int QUICK_ROR_INTERSECT_SELECT::reset() SYNOPSIS QUICK_ROR_INTERSECT_SELECT::push_quick_back() + alloc Mem root to create auxiliary structures on quick Quick select to be added. The quick select must return rows in rowid order. NOTES @@ -1575,11 +2154,17 @@ int QUICK_ROR_INTERSECT_SELECT::reset() */ bool -QUICK_ROR_INTERSECT_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick) +QUICK_ROR_INTERSECT_SELECT::push_quick_back(MEM_ROOT *alloc, QUICK_RANGE_SELECT *quick) { - return quick_selects.push_back(quick); + QUICK_SELECT_WITH_RECORD *qr; + if (!(qr= new QUICK_SELECT_WITH_RECORD) || + !(qr->key_tuple= (uchar*)alloc_root(alloc, quick->max_used_key_length))) + return TRUE; + qr->quick= quick; + return quick_selects.push_back(qr); } + QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT() { DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT"); @@ -1748,6 +2333,7 @@ SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc() min_value=arg.min_value; max_value=arg.max_value; next_key_part=arg.next_key_part; + max_part_no= arg.max_part_no; use_count=1; elements=1; } @@ -1765,9 +2351,10 @@ SEL_ARG::SEL_ARG(Field *f,const uchar *min_value_arg, :min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()), elements(1), use_count(1), field(f), min_value((uchar*) min_value_arg), max_value((uchar*) max_value_arg), next(0),prev(0), - next_key_part(0),color(BLACK),type(KEY_RANGE) + next_key_part(0), color(BLACK), type(KEY_RANGE) { left=right= &null_element; + max_part_no= 1; } SEL_ARG::SEL_ARG(Field *field_,uint8 part_, @@ -1778,6 +2365,7 @@ SEL_ARG::SEL_ARG(Field *field_,uint8 part_, field(field_), min_value(min_value_), max_value(max_value_), next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE) { + max_part_no= part+1; left=right= &null_element; } @@ -1821,6 +2409,7 @@ SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, increment_use_count(1); tmp->color= color; tmp->elements= this->elements; + tmp->max_part_no= max_part_no; return tmp; } @@ -2036,6 +2625,26 @@ public: /* + Plan for QUICK_INDEX_INTERSECT_SELECT scan. + QUICK_INDEX_INTERSECT_SELECT always retrieves full rows, so retrieve_full_rows + is ignored by make_quick. +*/ + +class TRP_INDEX_INTERSECT : public TABLE_READ_PLAN +{ +public: + TRP_INDEX_INTERSECT() {} /* Remove gcc warning */ + virtual ~TRP_INDEX_INTERSECT() {} /* Remove gcc warning */ + QUICK_SELECT_I *make_quick(PARAM *param, bool retrieve_full_rows, + MEM_ROOT *parent_alloc); + TRP_RANGE **range_scans; /* array of ptrs to plans of intersected scans */ + TRP_RANGE **range_scans_end; /* end of the array */ + /* keys whose scans are to be filtered by cpk conditions */ + key_map filtered_scans; +}; + + +/* Plan for QUICK_INDEX_MERGE_SELECT scan. QUICK_ROR_INTERSECT_SELECT always retrieves full rows, so retrieve_full_rows is ignored by make_quick. @@ -2106,6 +2715,38 @@ public: }; +typedef struct st_index_scan_info +{ + uint idx; /* # of used key in param->keys */ + uint keynr; /* # of used key in table */ + uint range_count; + ha_rows records; /* estimate of # records this scan will return */ + + /* Set of intervals over key fields that will be used for row retrieval. */ + SEL_ARG *sel_arg; + + KEY *key_info; + uint used_key_parts; + + /* Estimate of # records filtered out by intersection with cpk */ + ha_rows filtered_out; + /* Bitmap of fields used in index intersection */ + MY_BITMAP used_fields; + + /* Fields used in the query and covered by ROR scan. */ + MY_BITMAP covered_fields; + uint used_fields_covered; /* # of set bits in covered_fields */ + int key_rec_length; /* length of key record (including rowid) */ + + /* + Cost of reading all index records with values in sel_arg intervals set + (assuming there is no need to access full table records) + */ + double index_read_cost; + uint first_uncovered_field; /* first unused bit in covered_fields */ + uint key_components; /* # of parts in the key */ +} INDEX_SCAN_INFO; + /* Fill param->needed_fields with bitmap of fields used in the query. SYNOPSIS @@ -2231,7 +2872,8 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use, quick=0; needed_reg.clear_all(); quick_keys.clear_all(); - if (keys_to_use.is_clear_all()) + DBUG_ASSERT(!head->is_filled_at_execution()); + if (keys_to_use.is_clear_all() || head->is_filled_at_execution()) DBUG_RETURN(0); records= head->file->stats.records; if (!records) @@ -2381,72 +3023,92 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use, It is possible to use a range-based quick select (but it might be slower than 'all' table scan). */ - if (tree->merges.is_empty()) - { - TRP_RANGE *range_trp; - TRP_ROR_INTERSECT *rori_trp; - bool can_build_covering= FALSE; + TRP_RANGE *range_trp; + TRP_ROR_INTERSECT *rori_trp; + TRP_INDEX_INTERSECT *intersect_trp; + bool can_build_covering= FALSE; + + remove_nonrange_trees(¶m, tree); - /* Get best 'range' plan and prepare data for making other plans */ - if ((range_trp= get_key_scans_params(¶m, tree, FALSE, TRUE, - best_read_time))) - { - best_trp= range_trp; - best_read_time= best_trp->read_cost; - } + /* Get best 'range' plan and prepare data for making other plans */ + if ((range_trp= get_key_scans_params(¶m, tree, FALSE, TRUE, + best_read_time))) + { + best_trp= range_trp; + best_read_time= best_trp->read_cost; + } + /* + Simultaneous key scans and row deletes on several handler + objects are not allowed so don't use ROR-intersection for + table deletes. + */ + if ((thd->lex->sql_command != SQLCOM_DELETE) && + optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE)) + { /* - Simultaneous key scans and row deletes on several handler - objects are not allowed so don't use ROR-intersection for - table deletes. + Get best non-covering ROR-intersection plan and prepare data for + building covering ROR-intersection. */ - if ((thd->lex->sql_command != SQLCOM_DELETE) && - optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE)) + if ((rori_trp= get_best_ror_intersect(¶m, tree, best_read_time, + &can_build_covering))) { + best_trp= rori_trp; + best_read_time= best_trp->read_cost; /* - Get best non-covering ROR-intersection plan and prepare data for - building covering ROR-intersection. + Try constructing covering ROR-intersect only if it looks possible + and worth doing. */ - if ((rori_trp= get_best_ror_intersect(¶m, tree, best_read_time, - &can_build_covering))) - { + if (!rori_trp->is_covering && can_build_covering && + (rori_trp= get_best_covering_ror_intersect(¶m, tree, + best_read_time))) best_trp= rori_trp; - best_read_time= best_trp->read_cost; - /* - Try constructing covering ROR-intersect only if it looks possible - and worth doing. - */ - if (!rori_trp->is_covering && can_build_covering && - (rori_trp= get_best_covering_ror_intersect(¶m, tree, - best_read_time))) - best_trp= rori_trp; - } } } - else + /* + Do not look for an index intersection plan if there is a covering + index. The scan by this covering index will be always cheaper than + any index intersection. + */ + if (param.table->covering_keys.is_clear_all() && + optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE) && + optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE_SORT_INTERSECT)) { - if (optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE)) + if ((intersect_trp= get_best_index_intersect(¶m, tree, + best_read_time))) { - /* Try creating index_merge/ROR-union scan. */ - SEL_IMERGE *imerge; - TABLE_READ_PLAN *best_conj_trp= NULL, *new_conj_trp; - LINT_INIT(new_conj_trp); /* no empty index_merge lists possible */ - DBUG_PRINT("info",("No range reads possible," - " trying to construct index_merge")); - List_iterator_fast<SEL_IMERGE> it(tree->merges); - while ((imerge= it++)) + best_trp= intersect_trp; + best_read_time= best_trp->read_cost; + set_if_smaller(param.table->quick_condition_rows, + intersect_trp->records); + } + } + + if (optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE)) + { + /* Try creating index_merge/ROR-union scan. */ + SEL_IMERGE *imerge; + TABLE_READ_PLAN *best_conj_trp= NULL, *new_conj_trp; + LINT_INIT(new_conj_trp); /* no empty index_merge lists possible */ + DBUG_PRINT("info",("No range reads possible," + " trying to construct index_merge")); + List_iterator_fast<SEL_IMERGE> it(tree->merges); + while ((imerge= it++)) + { + new_conj_trp= get_best_disjunct_quick(¶m, imerge, best_read_time); + if (new_conj_trp) + set_if_smaller(param.table->quick_condition_rows, + new_conj_trp->records); + if (new_conj_trp && + (!best_conj_trp || + new_conj_trp->read_cost < best_conj_trp->read_cost)) { - new_conj_trp= get_best_disjunct_quick(¶m, imerge, best_read_time); - if (new_conj_trp) - set_if_smaller(param.table->quick_condition_rows, - new_conj_trp->records); - if (!best_conj_trp || (new_conj_trp && new_conj_trp->read_cost < - best_conj_trp->read_cost)) - best_conj_trp= new_conj_trp; + best_conj_trp= new_conj_trp; + best_read_time= best_conj_trp->read_cost; } - if (best_conj_trp) - best_trp= best_conj_trp; } + if (best_conj_trp) + best_trp= best_conj_trp; } } @@ -3743,11 +4405,19 @@ double get_sweep_read_cost(const PARAM *param, ha_rows records) DBUG_ENTER("get_sweep_read_cost"); if (param->table->file->primary_key_is_clustered()) { + /* + We are using the primary key to find the rows. + Calculate the cost for this. + */ result= param->table->file->read_time(param->table->s->primary_key, (uint)records, records); } else { + /* + Rows will be retreived with rnd_pos(). Caluclate the expected + cost for this. + */ double n_blocks= ceil(ulonglong2double(param->table->file->stats.data_file_length) / IO_SIZE); @@ -3764,7 +4434,7 @@ double get_sweep_read_cost(const PARAM *param, ha_rows records) return 1; */ JOIN *join= param->thd->lex->select_lex.join; - if (!join || join->tables == 1) + if (!join || join->table_count == 1) { /* No join, assume reading is done in one 'sweep' */ result= busy_blocks*(DISK_SEEK_BASE_COST + @@ -3855,7 +4525,6 @@ TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge, { SEL_TREE **ptree; TRP_INDEX_MERGE *imerge_trp= NULL; - uint n_child_scans= imerge->trees_next - imerge->trees; TRP_RANGE **range_scans; TRP_RANGE **cur_child; TRP_RANGE **cpk_scan= NULL; @@ -3875,6 +4544,24 @@ TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge, DBUG_ENTER("get_best_disjunct_quick"); DBUG_PRINT("info", ("Full table scan cost: %g", read_time)); + /* + In every tree of imerge remove SEL_ARG trees that do not make ranges. + If after this removal some SEL_ARG tree becomes empty discard imerge. + */ + for (ptree= imerge->trees; ptree != imerge->trees_next; ptree++) + { + if (remove_nonrange_trees(param, *ptree)) + { + imerge->trees_next= imerge->trees; + break; + } + } + + uint n_child_scans= imerge->trees_next - imerge->trees; + + if (!n_child_scans) + DBUG_RETURN(NULL); + if (!(range_scans= (TRP_RANGE**)alloc_root(param->mem_root, sizeof(TRP_RANGE*)* n_child_scans))) @@ -3979,7 +4666,9 @@ TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge, imerge_cost += Unique::get_use_cost(param->imerge_cost_buff, (uint)non_cpk_scan_records, param->table->file->ref_length, - param->thd->variables.sortbuff_size); + param->thd->variables.sortbuff_size, + TIME_FOR_COMPARE_ROWID, + FALSE, NULL); DBUG_PRINT("info",("index_merge total cost: %g (wanted: less then %g)", imerge_cost, read_time)); if (imerge_cost < read_time) @@ -3994,6 +4683,13 @@ TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge, imerge_trp->range_scans_end= range_scans + n_child_scans; read_time= imerge_cost; } + if (imerge_trp) + { + TABLE_READ_PLAN *trp= merge_same_index_scans(param, imerge, imerge_trp, + read_time); + if (trp != imerge_trp) + DBUG_RETURN(trp); + } } build_ror_index_merge: @@ -4009,6 +4705,7 @@ build_ror_index_merge: sizeof(TABLE_READ_PLAN*)* n_child_scans))) DBUG_RETURN(imerge_trp); + skip_to_ror_scan: roru_index_costs= 0.0; roru_total_records= 0; @@ -4092,30 +4789,990 @@ skip_to_ror_scan: DBUG_RETURN(roru); } } - DBUG_RETURN(imerge_trp); + DBUG_RETURN(imerge_trp); } -typedef struct st_ror_scan_info + +/* + Merge index scans for the same indexes in an index merge plan + + SYNOPSIS + merge_same_index_scans() + param Context info for the operation + imerge IN/OUT SEL_IMERGE from which imerge_trp has been extracted + imerge_trp The index merge plan where index scans for the same + indexes are to be merges + read_time The upper bound for the cost of the plan to be evaluated + + DESRIPTION + For the given index merge plan imerge_trp extracted from the SEL_MERGE + imerge the function looks for range scans with the same indexes and merges + them into SEL_ARG trees. Then for each such SEL_ARG tree r_i the function + creates a range tree rt_i that contains only r_i. All rt_i are joined + into one index merge that replaces the original index merge imerge. + The function calls get_best_disjunct_quick for the new index merge to + get a new index merge plan that contains index scans only for different + indexes. + If there are no index scans for the same index in the original index + merge plan the function does not change the original imerge and returns + imerge_trp as its result. + + RETURN + The original or or improved index merge plan +*/ + +static +TABLE_READ_PLAN *merge_same_index_scans(PARAM *param, SEL_IMERGE *imerge, + TRP_INDEX_MERGE *imerge_trp, + double read_time) { - uint idx; /* # of used key in param->keys */ - uint keynr; /* # of used key in table */ - ha_rows records; /* estimate of # records this scan will return */ + uint16 first_scan_tree_idx[MAX_KEY]; + SEL_TREE **tree; + TRP_RANGE **cur_child; + uint removed_cnt= 0; - /* Set of intervals over key fields that will be used for row retrieval. */ - SEL_ARG *sel_arg; + DBUG_ENTER("merge_same_index_scans"); - /* Fields used in the query and covered by this ROR scan. */ - MY_BITMAP covered_fields; - uint used_fields_covered; /* # of set bits in covered_fields */ - int key_rec_length; /* length of key record (including rowid) */ + bzero(first_scan_tree_idx, sizeof(first_scan_tree_idx[0])*param->keys); - /* - Cost of reading all index records with values in sel_arg intervals set - (assuming there is no need to access full table records) - */ - double index_read_cost; - uint first_uncovered_field; /* first unused bit in covered_fields */ - uint key_components; /* # of parts in the key */ + for (tree= imerge->trees, cur_child= imerge_trp->range_scans; + tree != imerge->trees_next; + tree++, cur_child++) + { + DBUG_ASSERT(tree); + uint key_idx= (*cur_child)->key_idx; + uint16 *tree_idx_ptr= &first_scan_tree_idx[key_idx]; + if (!*tree_idx_ptr) + *tree_idx_ptr= (uint16) (tree-imerge->trees+1); + else + { + SEL_TREE **changed_tree= imerge->trees+(*tree_idx_ptr-1); + SEL_ARG *key= (*changed_tree)->keys[key_idx]; + bzero((*changed_tree)->keys, + sizeof((*changed_tree)->keys[0])*param->keys); + (*changed_tree)->keys_map.clear_all(); + if (((*changed_tree)->keys[key_idx]= + key_or(param, key, (*tree)->keys[key_idx]))) + (*changed_tree)->keys_map.set_bit(key_idx); + *tree= NULL; + removed_cnt++; + } + } + if (!removed_cnt) + DBUG_RETURN(imerge_trp); + + TABLE_READ_PLAN *trp= NULL; + SEL_TREE **new_trees_next= imerge->trees; + for (tree= new_trees_next; tree != imerge->trees_next; tree++) + { + if (!*tree) + continue; + if (tree > new_trees_next) + *new_trees_next= *tree; + new_trees_next++; + } + imerge->trees_next= new_trees_next; + + DBUG_ASSERT(imerge->trees_next>imerge->trees); + + if (imerge->trees_next-imerge->trees > 1) + trp= get_best_disjunct_quick(param, imerge, read_time); + else + { + /* + This alternative theoretically can be reached when the cost + of the index merge for such a formula as + (key1 BETWEEN c1_1 AND c1_2) AND key2 > c2 OR + (key1 BETWEEN c1_3 AND c1_4) AND key3 > c3 + is estimated as being cheaper than the cost of index scan for + the formula + (key1 BETWEEN c1_1 AND c1_2) OR (key1 BETWEEN c1_3 AND c1_4) + + In the current code this may happen for two reasons: + 1. for a single index range scan data records are accessed in + a random order + 2. the functions that estimate the cost of a range scan and an + index merge retrievals are not well calibrated + */ + trp= get_key_scans_params(param, *imerge->trees, FALSE, TRUE, + read_time); + } + + DBUG_RETURN(trp); +} + + +/* + This structure contains the info common for all steps of a partial + index intersection plan. Morever it contains also the info common + for index intersect plans. This info is filled in by the function + prepare_search_best just before searching for the best index + intersection plan. +*/ + +typedef struct st_common_index_intersect_info +{ + PARAM *param; /* context info for range optimizations */ + uint key_size; /* size of a ROWID element stored in Unique object */ + uint compare_factor; /* 1/compare - cost to compare two ROWIDs */ + ulonglong max_memory_size; /* maximum space allowed for Unique objects */ + ha_rows table_cardinality; /* estimate of the number of records in table */ + double cutoff_cost; /* discard index intersects with greater costs */ + INDEX_SCAN_INFO *cpk_scan; /* clustered primary key used in intersection */ + + bool in_memory; /* unique object for intersection is completely in memory */ + + INDEX_SCAN_INFO **search_scans; /* scans possibly included in intersect */ + uint n_search_scans; /* number of elements in search_scans */ + + bool best_uses_cpk; /* current best intersect uses clustered primary key */ + double best_cost; /* cost of the current best index intersection */ + /* estimate of the number of records in the current best intersection */ + ha_rows best_records; + uint best_length; /* number of indexes in the current best intersection */ + INDEX_SCAN_INFO **best_intersect; /* the current best index intersection */ + /* scans from the best intersect to be filtrered by cpk conditions */ + key_map filtered_scans; + + uint *buff_elems; /* buffer to calculate cost of index intersection */ + +} COMMON_INDEX_INTERSECT_INFO; + + +/* + This structure contains the info specific for one step of an index + intersection plan. The structure is filled in by the function + check_index_intersect_extension. +*/ + +typedef struct st_partial_index_intersect_info +{ + COMMON_INDEX_INTERSECT_INFO *common_info; /* shared by index intersects */ + uint length; /* number of index scans in the partial intersection */ + ha_rows records; /* estimate of the number of records in intersection */ + double cost; /* cost of the partial index intersection */ + + /* estimate of total number of records of all scans of the partial index + intersect sent to the Unique object used for the intersection */ + ha_rows records_sent_to_unique; + + /* total cost of the scans of indexes from the partial index intersection */ + double index_read_cost; + + bool use_cpk_filter; /* cpk filter is to be used for this scan */ + bool in_memory; /* uses unique object in memory */ + double in_memory_cost; /* cost of using unique object in memory */ + + key_map filtered_scans; /* scans to be filtered by cpk conditions */ + + MY_BITMAP *intersect_fields; /* bitmap of fields used in intersection */ +} PARTIAL_INDEX_INTERSECT_INFO; + + +/* Check whether two indexes have the same first n components */ + +static +bool same_index_prefix(KEY *key1, KEY *key2, uint used_parts) +{ + KEY_PART_INFO *part1= key1->key_part; + KEY_PART_INFO *part2= key2->key_part; + for(uint i= 0; i < used_parts; i++, part1++, part2++) + { + if (part1->fieldnr != part2->fieldnr) + return FALSE; + } + return TRUE; +} + + +/* Create a bitmap for all fields of a table */ + +static +bool create_fields_bitmap(PARAM *param, MY_BITMAP *fields_bitmap) +{ + my_bitmap_map *bitmap_buf; + + if (!(bitmap_buf= (my_bitmap_map *) alloc_root(param->mem_root, + param->fields_bitmap_size))) + return TRUE; + if (bitmap_init(fields_bitmap, bitmap_buf, param->table->s->fields, FALSE)) + return TRUE; + + return FALSE; +} + +/* Compare two indexes scans for sort before search for the best intersection */ + +static +int cmp_intersect_index_scan(INDEX_SCAN_INFO **a, INDEX_SCAN_INFO **b) +{ + return (*a)->records < (*b)->records ? + -1 : (*a)->records == (*b)->records ? 0 : 1; +} + + +static inline +void set_field_bitmap_for_index_prefix(MY_BITMAP *field_bitmap, + KEY_PART_INFO *key_part, + uint used_key_parts) +{ + bitmap_clear_all(field_bitmap); + for (KEY_PART_INFO *key_part_end= key_part+used_key_parts; + key_part < key_part_end; key_part++) + { + bitmap_set_bit(field_bitmap, key_part->fieldnr-1); + } +} + + +/* + Round up table cardinality read from statistics provided by engine. + This function should go away when mysql test will allow to handle + more or less easily in the test suites deviations of InnoDB + statistical data. +*/ + +static inline +ha_rows get_table_cardinality_for_index_intersect(TABLE *table) +{ + if (table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) + return table->file->stats.records; + else + { + ha_rows d; + double q; + for (q= (double)table->file->stats.records, d= 1 ; q >= 10; q/= 10, d*= 10 ) ; + return (ha_rows) (floor(q+0.5) * d); + } +} + + +static +ha_rows records_in_index_intersect_extension(PARTIAL_INDEX_INTERSECT_INFO *curr, + INDEX_SCAN_INFO *ext_index_scan); + +/* + Prepare to search for the best index intersection + + SYNOPSIS + prepare_search_best_index_intersect() + param common info about index ranges + tree tree of ranges for indexes than can be intersected + common OUT info needed for search to be filled by the function + init OUT info for an initial pseudo step of the intersection plans + cutoff_cost cut off cost of the interesting index intersection + + DESCRIPTION + The function initializes all fields of the structure 'common' to be used + when searching for the best intersection plan. It also allocates + memory to store the most cheap index intersection. + + NOTES + When selecting candidates for index intersection we always take only + one representative out of any set of indexes that share the same range + conditions. These indexes always have the same prefixes and the + components of this prefixes are exactly those used in these range + conditions. + Range conditions over clustered primary key (cpk) is always used only + as the condition that filters out some rowids retrieved by the scans + for secondary indexes. The cpk index will be handled in special way by + the function that search for the best index intersection. + + RETURN + FALSE in the case of success + TRUE otherwise +*/ + +static +bool prepare_search_best_index_intersect(PARAM *param, + SEL_TREE *tree, + COMMON_INDEX_INTERSECT_INFO *common, + PARTIAL_INDEX_INTERSECT_INFO *init, + double cutoff_cost) +{ + uint i; + uint n_search_scans; + double cost; + INDEX_SCAN_INFO **index_scan; + INDEX_SCAN_INFO **scan_ptr; + INDEX_SCAN_INFO *cpk_scan= NULL; + TABLE *table= param->table; + uint n_index_scans= tree->index_scans_end - tree->index_scans; + + if (!n_index_scans) + return 1; + + bzero(init, sizeof(*init)); + init->common_info= common; + init->cost= cutoff_cost; + + common->param= param; + common->key_size= table->file->ref_length; + common->compare_factor= TIME_FOR_COMPARE_ROWID; + common->max_memory_size= param->thd->variables.sortbuff_size; + common->cutoff_cost= cutoff_cost; + common->cpk_scan= NULL; + common->table_cardinality= + get_table_cardinality_for_index_intersect(table); + + if (n_index_scans <= 1) + return TRUE; + + if (table->file->primary_key_is_clustered()) + { + INDEX_SCAN_INFO **index_scan_end; + index_scan= tree->index_scans; + index_scan_end= index_scan+n_index_scans; + for ( ; index_scan < index_scan_end; index_scan++) + { + if ((*index_scan)->keynr == table->s->primary_key) + { + common->cpk_scan= cpk_scan= *index_scan; + break; + } + } + } + + i= n_index_scans - test(cpk_scan != NULL) + 1; + + if (!(common->search_scans = + (INDEX_SCAN_INFO **) alloc_root (param->mem_root, + sizeof(INDEX_SCAN_INFO *) * i))) + return TRUE; + bzero(common->search_scans, sizeof(INDEX_SCAN_INFO *) * i); + + INDEX_SCAN_INFO **selected_index_scans= common->search_scans; + + for (i=0, index_scan= tree->index_scans; i < n_index_scans; i++, index_scan++) + { + uint used_key_parts= (*index_scan)->used_key_parts; + KEY *key_info= (*index_scan)->key_info; + + if (*index_scan == cpk_scan) + continue; + if (cpk_scan && cpk_scan->used_key_parts >= used_key_parts && + same_index_prefix(cpk_scan->key_info, key_info, used_key_parts)) + continue; + + cost= table->file->keyread_time((*index_scan)->keynr, + (*index_scan)->range_count, + (*index_scan)->records); + if (cost >= cutoff_cost) + continue; + + for (scan_ptr= selected_index_scans; *scan_ptr ; scan_ptr++) + { + /* + When we have range conditions for two different indexes with the same + beginning it does not make sense to consider both of them for index + intersection if the range conditions are covered by common initial + components of the indexes. Actually in this case the indexes are + guaranteed to have the same range conditions. + */ + if ((*scan_ptr)->used_key_parts == used_key_parts && + same_index_prefix((*scan_ptr)->key_info, key_info, used_key_parts)) + break; + } + if (!*scan_ptr || cost < (*scan_ptr)->index_read_cost) + { + *scan_ptr= *index_scan; + (*scan_ptr)->index_read_cost= cost; + } + } + + ha_rows records_in_scans= 0; + + for (scan_ptr=selected_index_scans, i= 0; *scan_ptr; scan_ptr++, i++) + { + if (create_fields_bitmap(param, &(*scan_ptr)->used_fields)) + return TRUE; + records_in_scans+= (*scan_ptr)->records; + } + n_search_scans= i; + + if (cpk_scan && create_fields_bitmap(param, &cpk_scan->used_fields)) + return TRUE; + + if (!(common->n_search_scans= n_search_scans)) + return TRUE; + + common->best_uses_cpk= FALSE; + common->best_cost= cutoff_cost + COST_EPS; + common->best_length= 0; + + if (!(common->best_intersect= + (INDEX_SCAN_INFO **) alloc_root (param->mem_root, + sizeof(INDEX_SCAN_INFO *) * + (i + test(cpk_scan != NULL))))) + return TRUE; + + size_t calc_cost_buff_size= + Unique::get_cost_calc_buff_size((size_t)records_in_scans, + common->key_size, + common->max_memory_size); + if (!(common->buff_elems= (uint *) alloc_root(param->mem_root, + calc_cost_buff_size))) + return TRUE; + + my_qsort(selected_index_scans, n_search_scans, sizeof(INDEX_SCAN_INFO *), + (qsort_cmp) cmp_intersect_index_scan); + + if (cpk_scan) + { + PARTIAL_INDEX_INTERSECT_INFO curr; + set_field_bitmap_for_index_prefix(&cpk_scan->used_fields, + cpk_scan->key_info->key_part, + cpk_scan->used_key_parts); + curr.common_info= common; + curr.intersect_fields= &cpk_scan->used_fields; + curr.records= cpk_scan->records; + curr.length= 1; + for (scan_ptr=selected_index_scans; *scan_ptr; scan_ptr++) + { + ha_rows scan_records= (*scan_ptr)->records; + ha_rows records= records_in_index_intersect_extension(&curr, *scan_ptr); + (*scan_ptr)->filtered_out= records >= scan_records ? + 0 : scan_records-records; + } + } + else + { + for (scan_ptr=selected_index_scans; *scan_ptr; scan_ptr++) + (*scan_ptr)->filtered_out= 0; + } + + return FALSE; +} + + +/* + On Estimation of the Number of Records in an Index Intersection + =============================================================== + + Consider query Q over table t. Let C be the WHERE condition of this query, + and, idx1(a1_1,...,a1_k1) and idx2(a2_1,...,a2_k2) be some indexes defined + on table t. + Let rt1 and rt2 be the range trees extracted by the range optimizer from C + for idx1 and idx2 respectively. + Let #t be the estimate of the number of records in table t provided for the + optimizer. + Let #r1 and #r2 be the estimates of the number of records in the range trees + rt1 and rt2, respectively, obtained by the range optimizer. + + We need to get an estimate for the number of records in the index + intersection of rt1 and rt2. In other words, we need to estimate the + cardinality of the set of records that are in both trees. Let's designate + this number by #r. + + If we do not make any assumptions then we can only state that + #r<=min(#r1,#r2). + With this estimate we can't say that the index intersection scan will be + cheaper than the cheapest index scan. + + Let Rt1 and Rt2 be AND/OR conditions representing rt and rt2 respectively. + The probability that a record belongs to rt1 is sel(Rt1)=#r1/#t. + The probability that a record belongs to rt2 is sel(Rt2)=#r2/#t. + + If we assume that the values in columns of idx1 and idx2 are independent + then #r/#t=sel(Rt1&Rt2)=sel(Rt1)*sel(Rt2)=(#r1/#t)*(#r2/#t). + So in this case we have: #r=#r1*#r2/#t. + + The above assumption of independence of the columns in idx1 and idx2 means + that: + - all columns are different + - values from one column do not correlate with values from any other column. + + We can't help with the case when column correlate with each other. + Yet, if they are assumed to be uncorrelated the value of #r theoretically can + be evaluated . Unfortunately this evaluation, in general, is rather complex. + + Let's consider two indexes idx1:(dept, manager), idx2:(dept, building) + over table 'employee' and two range conditions over these indexes: + Rt1: dept=10 AND manager LIKE 'S%' + Rt2: dept=10 AND building LIKE 'L%'. + We can state that: + sel(Rt1&Rt2)=sel(dept=10)*sel(manager LIKE 'S%')*sel(building LIKE 'L%') + =sel(Rt1)*sel(Rt2)/sel(dept=10). + sel(Rt1/2_0:dept=10) can be estimated if we know the cardinality #r1_0 of + the range for sub-index idx1_0 (dept) of the index idx1 or the cardinality + #rt2_0 of the same range for sub-index idx2_0(dept) of the index idx2. + The current code does not make an estimate either for #rt1_0, or for #rt2_0, + but it can be adjusted to provide those numbers. + Alternatively, min(rec_per_key) for (dept) could be used to get an upper + bound for the value of sel(Rt1&Rt2). Yet this statistics is not provided + now. + + Let's consider two other indexes idx1:(dept, last_name), + idx2:(first_name, last_name) and two range conditions over these indexes: + Rt1: dept=5 AND last_name='Sm%' + Rt2: first_name='Robert' AND last_name='Sm%'. + + sel(Rt1&Rt2)=sel(dept=5)*sel(last_name='Sm5')*sel(first_name='Robert') + =sel(Rt2)*sel(dept=5) + Here max(rec_per_key) for (dept) could be used to get an upper bound for + the value of sel(Rt1&Rt2). + + When the intersected indexes have different major columns, but some + minor column are common the picture may be more complicated. + + Let's consider the following range conditions for the same indexes as in + the previous example: + Rt1: (Rt11: dept=5 AND last_name='So%') + OR + (Rt12: dept=7 AND last_name='Saw%') + Rt2: (Rt21: first_name='Robert' AND last_name='Saw%') + OR + (Rt22: first_name='Bob' AND last_name='So%') + Here we have: + sel(Rt1&Rt2)= sel(Rt11)*sel(Rt21)+sel(Rt22)*sel(dept=5) + + sel(Rt21)*sel(dept=7)+sel(Rt12)*sel(Rt22) + Now consider the range condition: + Rt1_0: (dept=5 OR dept=7) + For this condition we can state that: + sel(Rt1_0&Rt2)=(sel(dept=5)+sel(dept=7))*(sel(Rt21)+sel(Rt22))= + sel(dept=5)*sel(Rt21)+sel(dept=7)*sel(Rt21)+ + sel(dept=5)*sel(Rt22)+sel(dept=7)*sel(Rt22)= + sel(dept=5)*sel(Rt21)+sel(Rt21)*sel(dept=7)+ + sel(Rt22)*sel(dept=5)+sel(dept=7)*sel(Rt22) > + sel(Rt11)*sel(Rt21)+sel(Rt22)*sel(dept=5)+ + sel(Rt21)*sel(dept=7)+sel(Rt12)*sel(Rt22) > + sel(Rt1 & Rt2) + + We've just demonstrated for an example what is intuitively almost obvious + in general. We can remove the ending parts fromrange trees getting less + selective range conditions for sub-indexes. + So if not a most major component with the number k of an index idx is + encountered in the index with which we intersect we can use the sub-index + idx_k-1 that includes the components of idx up to the i-th component and + the range tree for idx_k-1 to make an upper bound estimate for the number + of records in the index intersection. + The range tree for idx_k-1 we use here is the subtree of the original range + tree for idx that contains only parts from the first k-1 components. + + As it was mentioned above the range optimizer currently does not provide + an estimate for the number of records in the ranges for sub-indexes. + However, some reasonable upper bound estimate can be obtained. + + Let's consider the following range tree: + Rt: (first_name='Robert' AND last_name='Saw%') + OR + (first_name='Bob' AND last_name='So%') + Let #r be the number of records in Rt. Let f_1 be the fan-out of column + last_name: + f_1 = rec_per_key[first_name]/rec_per_key[last_name]. + The the number of records in the range tree: + Rt_0: (first_name='Robert' OR first_name='Bob') + for the sub-index (first_name) is not greater than max(#r*f_1, #t). + Strictly speaking, we can state only that it's not greater than + max(#r*max_f_1, #t), where + max_f_1= max_rec_per_key[first_name]/min_rec_per_key[last_name]. + Yet, if #r/#t is big enough (and this is the case of an index intersection, + because using this index range with a single index scan is cheaper than + the cost of the intersection when #r/#t is small) then almost safely we + can use here f_1 instead of max_f_1. + + The above considerations can be used in future development. Now, they are + used partly in the function that provides a rough upper bound estimate for + the number of records in an index intersection that follow below. +*/ + +/* + Estimate the number of records selected by an extension a partial intersection + + SYNOPSIS + records_in_index_intersect_extension() + curr partial intersection plan to be extended + ext_index_scan the evaluated extension of this partial plan + + DESCRIPTION + The function provides an estimate for the number of records in the + intersection of the partial index intersection curr with the index + ext_index_scan. If all intersected indexes does not have common columns + then the function returns an exact estimate (assuming there are no + correlations between values in the columns). If the intersected indexes + have common columns the function returns an upper bound for the number + of records in the intersection provided that the intersection of curr + with ext_index_scan can is expected to have less records than the expected + number of records in the partial intersection curr. In this case the + function also assigns the bitmap of the columns in the extended + intersection to ext_index_scan->used_fields. + If the function cannot expect that the number of records in the extended + intersection is less that the expected number of records #r in curr then + the function returns a number bigger than #r. + + NOTES + See the comment before the desription of the function that explains the + reasoning used by this function. + + RETURN + The expected number of rows in the extended index intersection +*/ + +static +ha_rows records_in_index_intersect_extension(PARTIAL_INDEX_INTERSECT_INFO *curr, + INDEX_SCAN_INFO *ext_index_scan) +{ + KEY *key_info= ext_index_scan->key_info; + KEY_PART_INFO* key_part= key_info->key_part; + uint used_key_parts= ext_index_scan->used_key_parts; + MY_BITMAP *used_fields= &ext_index_scan->used_fields; + + if (!curr->length) + { + /* + If this the first index in the intersection just mark the + fields in the used_fields bitmap and return the expected + number of records in the range scan for the index provided + by the range optimizer. + */ + set_field_bitmap_for_index_prefix(used_fields, key_part, used_key_parts); + return ext_index_scan->records; + } + + uint i; + bool better_selectivity= FALSE; + ha_rows records= curr->records; + MY_BITMAP *curr_intersect_fields= curr->intersect_fields; + for (i= 0; i < used_key_parts; i++, key_part++) + { + if (bitmap_is_set(curr_intersect_fields, key_part->fieldnr-1)) + break; + } + if (i) + { + ha_rows table_cardinality= curr->common_info->table_cardinality; + ha_rows ext_records= ext_index_scan->records; + if (i < used_key_parts) + { + ulong *rec_per_key= key_info->rec_per_key+i-1; + ulong f1= rec_per_key[0] ? rec_per_key[0] : 1; + ulong f2= rec_per_key[1] ? rec_per_key[1] : 1; + ext_records= (ha_rows) ((double) ext_records / f2 * f1); + } + if (ext_records < table_cardinality) + { + better_selectivity= TRUE; + records= (ha_rows) ((double) records / table_cardinality * + ext_records); + bitmap_copy(used_fields, curr_intersect_fields); + key_part= key_info->key_part; + for (uint j= 0; j < used_key_parts; j++, key_part++) + bitmap_set_bit(used_fields, key_part->fieldnr-1); + } + } + return !better_selectivity ? records+1 : + !records ? 1 : records; +} + + +/* + Estimate the cost a binary search within disjoint cpk range intervals + + Number of comparisons to check whether a cpk value satisfies + the cpk range condition = log2(cpk_scan->range_count). +*/ + +static inline +double get_cpk_filter_cost(ha_rows filtered_records, + INDEX_SCAN_INFO *cpk_scan, + double compare_factor) +{ + return log((double) (cpk_scan->range_count+1)) / (compare_factor * M_LN2) * + filtered_records; +} + + +/* + Check whether a patial index intersection plan can be extended + + SYNOPSIS + check_index_intersect_extension() + curr partial intersection plan to be extended + ext_index_scan a possible extension of this plan to be checked + next OUT the structure to be filled for the extended plan + + DESCRIPTION + The function checks whether it makes sense to extend the index + intersection plan adding the index ext_index_scan, and, if this + the case, the function fills in the structure for the extended plan. + + RETURN + TRUE if it makes sense to extend the given plan + FALSE otherwise +*/ + +static +bool check_index_intersect_extension(PARTIAL_INDEX_INTERSECT_INFO *curr, + INDEX_SCAN_INFO *ext_index_scan, + PARTIAL_INDEX_INTERSECT_INFO *next) +{ + ha_rows records; + ha_rows records_sent_to_unique; + double cost; + ha_rows ext_index_scan_records= ext_index_scan->records; + ha_rows records_filtered_out_by_cpk= ext_index_scan->filtered_out; + COMMON_INDEX_INTERSECT_INFO *common_info= curr->common_info; + double cutoff_cost= common_info->cutoff_cost; + uint idx= curr->length; + next->index_read_cost= curr->index_read_cost+ext_index_scan->index_read_cost; + if (next->index_read_cost > cutoff_cost) + return FALSE; + + if ((next->in_memory= curr->in_memory)) + next->in_memory_cost= curr->in_memory_cost; + + next->intersect_fields= &ext_index_scan->used_fields; + next->filtered_scans= curr->filtered_scans; + + records_sent_to_unique= curr->records_sent_to_unique; + + next->use_cpk_filter= FALSE; + + /* Calculate the cost of using a Unique object for index intersection */ + if (idx && next->in_memory) + { + /* + All rowids received from the first scan are expected in one unique tree + */ + ha_rows elems_in_tree= common_info->search_scans[0]->records- + common_info->search_scans[0]->filtered_out ; + next->in_memory_cost+= Unique::get_search_cost(elems_in_tree, + common_info->compare_factor)* + ext_index_scan_records; + cost= next->in_memory_cost; + } + else + { + uint *buff_elems= common_info->buff_elems; + uint key_size= common_info->key_size; + uint compare_factor= common_info->compare_factor; + ulonglong max_memory_size= common_info->max_memory_size; + + records_sent_to_unique+= ext_index_scan_records; + cost= Unique::get_use_cost(buff_elems, (size_t) records_sent_to_unique, key_size, + max_memory_size, compare_factor, TRUE, + &next->in_memory); + if (records_filtered_out_by_cpk) + { + /* Check whether using cpk filter for this scan is beneficial */ + + double cost2; + bool in_memory2; + ha_rows records2= records_sent_to_unique-records_filtered_out_by_cpk; + cost2= Unique::get_use_cost(buff_elems, (size_t) records2, key_size, + max_memory_size, compare_factor, TRUE, + &in_memory2); + cost2+= get_cpk_filter_cost(ext_index_scan_records, common_info->cpk_scan, + compare_factor); + if (cost > cost2 + COST_EPS) + { + cost= cost2; + next->in_memory= in_memory2; + next->use_cpk_filter= TRUE; + records_sent_to_unique= records2; + } + + } + if (next->in_memory) + next->in_memory_cost= cost; + } + + if (next->use_cpk_filter) + { + next->filtered_scans.set_bit(ext_index_scan->keynr); + bitmap_union(&ext_index_scan->used_fields, + &common_info->cpk_scan->used_fields); + } + next->records_sent_to_unique= records_sent_to_unique; + + records= records_in_index_intersect_extension(curr, ext_index_scan); + if (idx && records > curr->records) + return FALSE; + if (next->use_cpk_filter && curr->filtered_scans.is_clear_all()) + records-= records_filtered_out_by_cpk; + next->records= records; + + cost+= next->index_read_cost; + if (cost >= cutoff_cost) + return FALSE; + + cost+= get_sweep_read_cost(common_info->param, records); + + next->cost= cost; + next->length= curr->length+1; + + return TRUE; +} + + +/* + Search for the cheapest extensions of range scans used to access a table + + SYNOPSIS + find_index_intersect_best_extension() + curr partial intersection to evaluate all possible extension for + + DESCRIPTION + The function tries to extend the partial plan curr in all possible ways + to look for a cheapest index intersection whose cost less than the + cut off value set in curr->common_info.cutoff_cost. +*/ + +static +void find_index_intersect_best_extension(PARTIAL_INDEX_INTERSECT_INFO *curr) +{ + PARTIAL_INDEX_INTERSECT_INFO next; + COMMON_INDEX_INTERSECT_INFO *common_info= curr->common_info; + INDEX_SCAN_INFO **index_scans= common_info->search_scans; + uint idx= curr->length; + INDEX_SCAN_INFO **rem_first_index_scan_ptr= &index_scans[idx]; + double cost= curr->cost; + + if (cost + COST_EPS < common_info->best_cost) + { + common_info->best_cost= cost; + common_info->best_length= curr->length; + common_info->best_records= curr->records; + common_info->filtered_scans= curr->filtered_scans; + /* common_info->best_uses_cpk <=> at least one scan uses a cpk filter */ + common_info->best_uses_cpk= !curr->filtered_scans.is_clear_all(); + uint sz= sizeof(INDEX_SCAN_INFO *) * curr->length; + memcpy(common_info->best_intersect, common_info->search_scans, sz); + common_info->cutoff_cost= cost; + } + + if (!(*rem_first_index_scan_ptr)) + return; + + next.common_info= common_info; + + INDEX_SCAN_INFO *rem_first_index_scan= *rem_first_index_scan_ptr; + for (INDEX_SCAN_INFO **index_scan_ptr= rem_first_index_scan_ptr; + *index_scan_ptr; index_scan_ptr++) + { + *rem_first_index_scan_ptr= *index_scan_ptr; + *index_scan_ptr= rem_first_index_scan; + if (check_index_intersect_extension(curr, *rem_first_index_scan_ptr, &next)) + find_index_intersect_best_extension(&next); + *index_scan_ptr= *rem_first_index_scan_ptr; + *rem_first_index_scan_ptr= rem_first_index_scan; + } +} + + +/* + Get the plan of the best intersection of range scans used to access a table + + SYNOPSIS + get_best_index_intersect() + param common info about index ranges + tree tree of ranges for indexes than can be intersected + read_time cut off value for the evaluated plans + + DESCRIPTION + The function looks for the cheapest index intersection of the range + scans to access a table. The info about the ranges for all indexes + is provided by the range optimizer and is passed through the + parameters param and tree. Any plan whose cost is greater than read_time + is rejected. + After the best index intersection is found the function constructs + the structure that manages the execution by the chosen plan. + + RETURN + Pointer to the generated execution structure if a success, + 0 - otherwise. +*/ + +static +TRP_INDEX_INTERSECT *get_best_index_intersect(PARAM *param, SEL_TREE *tree, + double read_time) +{ + uint i; + uint count; + TRP_RANGE **cur_range; + TRP_RANGE **range_scans; + INDEX_SCAN_INFO *index_scan; + COMMON_INDEX_INTERSECT_INFO common; + PARTIAL_INDEX_INTERSECT_INFO init; + TRP_INDEX_INTERSECT *intersect_trp= NULL; + TABLE *table= param->table; + + + DBUG_ENTER("get_best_index_intersect"); + + if (prepare_search_best_index_intersect(param, tree, &common, &init, + read_time)) + DBUG_RETURN(NULL); + + find_index_intersect_best_extension(&init); + + if (common.best_length <= 1 && !common.best_uses_cpk) + DBUG_RETURN(NULL); + + if (common.best_uses_cpk) + { + memmove((char *) (common.best_intersect+1), (char *) common.best_intersect, + sizeof(INDEX_SCAN_INFO *) * common.best_length); + common.best_intersect[0]= common.cpk_scan; + common.best_length++; + } + + count= common.best_length; + + if (!(range_scans= (TRP_RANGE**)alloc_root(param->mem_root, + sizeof(TRP_RANGE *)* + count))) + DBUG_RETURN(NULL); + + for (i= 0, cur_range= range_scans; i < count; i++) + { + index_scan= common.best_intersect[i]; + if ((*cur_range= new (param->mem_root) TRP_RANGE(index_scan->sel_arg, + index_scan->idx, 0))) + { + TRP_RANGE *trp= *cur_range; + trp->read_cost= index_scan->index_read_cost; + trp->records= index_scan->records; + trp->is_ror= FALSE; + trp->mrr_buf_size= 0; + table->intersect_keys.set_bit(index_scan->keynr); + cur_range++; + } + } + + count= tree->index_scans_end - tree->index_scans; + for (i= 0; i < count; i++) + { + index_scan= tree->index_scans[i]; + if (!table->intersect_keys.is_set(index_scan->keynr)) + { + for (uint j= 0; j < common.best_length; j++) + { + INDEX_SCAN_INFO *scan= common.best_intersect[j]; + if (same_index_prefix(index_scan->key_info, scan->key_info, + scan->used_key_parts)) + { + table->intersect_keys.set_bit(index_scan->keynr); + break; + } + } + } + } + + if ((intersect_trp= new (param->mem_root)TRP_INDEX_INTERSECT)) + { + intersect_trp->read_cost= common.best_cost; + intersect_trp->records= common.best_records; + intersect_trp->range_scans= range_scans; + intersect_trp->range_scans_end= cur_range; + intersect_trp->filtered_scans= common.filtered_scans; + } + DBUG_RETURN(intersect_trp); +} + + +typedef struct st_ror_scan_info : INDEX_SCAN_INFO +{ } ROR_SCAN_INFO; @@ -4151,7 +5808,7 @@ ROR_SCAN_INFO *make_ror_scan(const PARAM *param, int idx, SEL_ARG *sel_arg) ror_scan->key_rec_length= (param->table->key_info[keynr].key_length + param->table->file->ref_length); ror_scan->sel_arg= sel_arg; - ror_scan->records= param->table->quick_rows[keynr]; + ror_scan->records= param->quick_rows[keynr]; if (!(bitmap_buf= (my_bitmap_map*) alloc_root(param->mem_root, param->fields_bitmap_size))) @@ -4171,8 +5828,7 @@ ROR_SCAN_INFO *make_ror_scan(const PARAM *param, int idx, SEL_ARG *sel_arg) bitmap_set_bit(&ror_scan->covered_fields, key_part->fieldnr-1); } ror_scan->index_read_cost= - param->table->file->keyread_time(ror_scan->keynr, 1, - param->table->quick_rows[ror_scan->keynr]); + param->table->file->keyread_time(ror_scan->keynr, 1, ror_scan->records); DBUG_RETURN(ror_scan); } @@ -4457,7 +6113,7 @@ static double ror_scan_selectivity(const ROR_INTERSECT_INFO *info, } if (!prev_covered) { - double tmp= rows2double(info->param->table->quick_rows[scan->keynr]) / + double tmp= rows2double(info->param->quick_rows[scan->keynr]) / rows2double(prev_records); DBUG_PRINT("info", ("Selectivity multiplier: %g", tmp)); selectivity_mult *= tmp; @@ -4536,7 +6192,7 @@ static bool ror_intersect_add(ROR_INTERSECT_INFO *info, } else { - info->index_records += info->param->table->quick_rows[ror_scan->keynr]; + info->index_records += info->param->quick_rows[ror_scan->keynr]; info->index_scan_costs += ror_scan->index_read_cost; bitmap_union(&info->covered_fields, &ror_scan->covered_fields); if (!info->is_covering && bitmap_is_subset(&info->param->needed_fields, @@ -4646,7 +6302,6 @@ TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree, ROR_SCAN_INFO **cur_ror_scan; ROR_SCAN_INFO *cpk_scan= NULL; uint cpk_no; - bool cpk_scan_used= FALSE; if (!(tree->ror_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root, sizeof(ROR_SCAN_INFO*)* @@ -4658,11 +6313,20 @@ TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree, for (idx= 0, cur_ror_scan= tree->ror_scans; idx < param->keys; idx++) { ROR_SCAN_INFO *scan; + uint key_no; if (!tree->ror_scans_map.is_set(idx)) continue; + key_no= param->real_keynr[idx]; + if (key_no != cpk_no && + param->table->file->index_flags(key_no,0,0) & HA_CLUSTERED_INDEX) + { + /* Ignore clustering keys */ + tree->n_ror_scans--; + continue; + } if (!(scan= make_ror_scan(param, idx, tree->keys[idx]))) return NULL; - if (param->real_keynr[idx] == cpk_no) + if (key_no == cpk_no) { cpk_scan= scan; tree->n_ror_scans--; @@ -4748,15 +6412,14 @@ TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree, { if (ror_intersect_add(intersect, cpk_scan, TRUE) && (intersect->total_cost < min_cost)) - { - cpk_scan_used= TRUE; intersect_best= intersect; //just set pointer here - } } + else + cpk_scan= 0; // Don't use cpk_scan /* Ok, return ROR-intersect plan if we have found one */ TRP_ROR_INTERSECT *trp= NULL; - if (min_cost < read_time && (cpk_scan_used || best_num > 1)) + if (min_cost < read_time && (cpk_scan || best_num > 1)) { if (!(trp= new (param->mem_root) TRP_ROR_INTERSECT)) DBUG_RETURN(trp); @@ -4775,7 +6438,7 @@ TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree, set_if_smaller(param->table->quick_condition_rows, best_rows); trp->records= best_rows; trp->index_scan_costs= intersect_best->index_scan_costs; - trp->cpk_scan= cpk_scan_used? cpk_scan: NULL; + trp->cpk_scan= cpk_scan; DBUG_PRINT("info", ("Returning non-covering ROR-intersect plan:" "cost %g, records %lu", trp->read_cost, (ulong) trp->records)); @@ -4787,7 +6450,7 @@ TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree, /* Get best covering ROR-intersection. SYNOPSIS - get_best_covering_ror_intersect() + get_best_ntersectcovering_ror_intersect() param Parameter from test_quick_select function. tree SEL_TREE with sets of intervals for different keys. read_time Don't return table read plans with cost > read_time. @@ -4975,6 +6638,14 @@ static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree, "tree scans");); tree->ror_scans_map.clear_all(); tree->n_ror_scans= 0; + tree->index_scans= 0; + if (!tree->keys_map.is_clear_all()) + { + tree->index_scans= + (INDEX_SCAN_INFO **) alloc_root(param->mem_root, + sizeof(INDEX_SCAN_INFO *) * param->keys); + } + tree->index_scans_end= tree->index_scans; for (idx= 0,key=tree->keys, end=key+param->keys; key != end; key++,idx++) { if (*key) @@ -4983,18 +6654,32 @@ static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree, COST_VECT cost; double found_read_time; uint mrr_flags, buf_size; + INDEX_SCAN_INFO *index_scan; uint keynr= param->real_keynr[idx]; if ((*key)->type == SEL_ARG::MAYBE_KEY || (*key)->maybe_flag) param->needed_reg->set_bit(keynr); - bool read_index_only= index_read_must_be_used || - param->table->covering_keys.is_set(keynr); + bool read_index_only= index_read_must_be_used ? TRUE : + (bool) param->table->covering_keys.is_set(keynr); found_records= check_quick_select(param, idx, read_index_only, *key, update_tbl_stats, &mrr_flags, &buf_size, &cost); + if (found_records != HA_POS_ERROR && tree->index_scans && + (index_scan= (INDEX_SCAN_INFO *)alloc_root(param->mem_root, + sizeof(INDEX_SCAN_INFO)))) + { + index_scan->idx= idx; + index_scan->keynr= keynr; + index_scan->key_info= ¶m->table->key_info[keynr]; + index_scan->used_key_parts= param->max_key_part+1; + index_scan->range_count= param->range_count; + index_scan->records= found_records; + index_scan->sel_arg= *key; + *tree->index_scans_end++= index_scan; + } if ((found_records != HA_POS_ERROR) && param->is_ror_scan) { tree->n_ror_scans++; @@ -5064,6 +6749,36 @@ QUICK_SELECT_I *TRP_INDEX_MERGE::make_quick(PARAM *param, return quick_imerge; } + +QUICK_SELECT_I *TRP_INDEX_INTERSECT::make_quick(PARAM *param, + bool retrieve_full_rows, + MEM_ROOT *parent_alloc) +{ + QUICK_INDEX_INTERSECT_SELECT *quick_intersect; + QUICK_RANGE_SELECT *quick; + /* index_merge always retrieves full rows, ignore retrieve_full_rows */ + if (!(quick_intersect= new QUICK_INDEX_INTERSECT_SELECT(param->thd, param->table))) + return NULL; + + quick_intersect->records= records; + quick_intersect->read_time= read_cost; + quick_intersect->filtered_scans= filtered_scans; + for (TRP_RANGE **range_scan= range_scans; range_scan != range_scans_end; + range_scan++) + { + if (!(quick= (QUICK_RANGE_SELECT*) + ((*range_scan)->make_quick(param, FALSE, &quick_intersect->alloc)))|| + quick_intersect->push_quick_back(quick)) + { + delete quick; + delete quick_intersect; + return NULL; + } + } + return quick_intersect; +} + + QUICK_SELECT_I *TRP_ROR_INTERSECT::make_quick(PARAM *param, bool retrieve_full_rows, MEM_ROOT *parent_alloc) @@ -5089,7 +6804,7 @@ QUICK_SELECT_I *TRP_ROR_INTERSECT::make_quick(PARAM *param, (*first_scan)->sel_arg, HA_MRR_USE_DEFAULT_IMPL | HA_MRR_SORTED, 0, alloc)) || - quick_intrsect->push_quick_back(quick)) + quick_intrsect->push_quick_back(alloc, quick)) { delete quick_intrsect; DBUG_RETURN(NULL); @@ -5513,11 +7228,10 @@ static SEL_TREE *get_full_func_mm_tree(RANGE_OPT_PARAM *param, Item_equal *item_equal= field_item->item_equal; if (item_equal) { - Item_equal_iterator it(*item_equal); - Item_field *item; - while ((item= it++)) + Item_equal_fields_iterator it(*item_equal); + while (it++) { - Field *f= item->field; + Field *f= it.get_curr_field(); if (field->eq(f)) continue; if (!((ref_tables | f->table->map) & param_comp)) @@ -5666,13 +7380,13 @@ static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond) case Item_func::MULT_EQUAL_FUNC: { Item_equal *item_equal= (Item_equal *) cond; - if (!(value= item_equal->get_const())) + if (!(value= item_equal->get_const()) || value->is_expensive()) DBUG_RETURN(0); - Item_equal_iterator it(*item_equal); + Item_equal_fields_iterator it(*item_equal); ref_tables= value->used_tables(); - while ((field_item= it++)) + while (it++) { - Field *field= field_item->field; + Field *field= it.get_curr_field(); Item_result cmp_type= field->cmp_type(); if (!((ref_tables | field->table->map) & param_comp)) { @@ -5699,6 +7413,9 @@ static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond) } else DBUG_RETURN(0); + if (value && value->is_expensive()) + DBUG_RETURN(0); + ftree= get_full_func_mm_tree(param, cond_func, field_item, value, inv); } @@ -5747,6 +7464,7 @@ get_mm_parts(RANGE_OPT_PARAM *param, COND *cond_func, Field *field, DBUG_RETURN(0); // OOM } sel_arg->part=(uchar) key_part->part; + sel_arg->max_part_no= sel_arg->part+1; tree->keys[key_part->key]=sel_add(tree->keys[key_part->key],sel_arg); tree->keys_map.set_bit(key_part->key); } @@ -5767,7 +7485,6 @@ get_mm_leaf(RANGE_OPT_PARAM *param, COND *conf_func, Field *field, SEL_ARG *tree= 0; MEM_ROOT *alloc= param->mem_root; uchar *str; - ulonglong orig_sql_mode; int err; DBUG_ENTER("get_mm_leaf"); @@ -5937,16 +7654,8 @@ get_mm_leaf(RANGE_OPT_PARAM *param, COND *conf_func, Field *field, We can't always use indexes when comparing a string index to a number cmp_type() is checked to allow compare of dates to numbers */ - if (field->result_type() == STRING_RESULT && - value->result_type() != STRING_RESULT && - field->cmp_type() != value->result_type()) + if (field->cmp_type() == STRING_RESULT && value->cmp_type() != STRING_RESULT) goto end; - /* For comparison purposes allow invalid dates like 2000-01-32 */ - orig_sql_mode= field->table->in_use->variables.sql_mode; - if (value->real_item()->type() == Item::STRING_ITEM && - (field->type() == MYSQL_TYPE_DATE || - field->type() == MYSQL_TYPE_DATETIME)) - field->table->in_use->variables.sql_mode|= MODE_INVALID_DATES; err= value->save_in_field_no_warnings(field, 1); if (err > 0) { @@ -5958,7 +7667,6 @@ get_mm_leaf(RANGE_OPT_PARAM *param, COND *conf_func, Field *field, { tree= new (alloc) SEL_ARG(field, 0, 0); tree->type= SEL_ARG::IMPOSSIBLE; - field->table->in_use->variables.sql_mode= orig_sql_mode; goto end; } else @@ -5992,10 +7700,7 @@ get_mm_leaf(RANGE_OPT_PARAM *param, COND *conf_func, Field *field, */ } else - { - field->table->in_use->variables.sql_mode= orig_sql_mode; goto end; - } } } @@ -6018,12 +7723,10 @@ get_mm_leaf(RANGE_OPT_PARAM *param, COND *conf_func, Field *field, } else if (err < 0) { - field->table->in_use->variables.sql_mode= orig_sql_mode; /* This happens when we try to insert a NULL field in a not null column */ tree= &null_element; // cmp with NULL is never TRUE goto end; } - field->table->in_use->variables.sql_mode= orig_sql_mode; /* Any sargable predicate except "<=>" involving NULL as a constant is always @@ -6198,13 +7901,138 @@ sel_add(SEL_ARG *key1,SEL_ARG *key2) return root; } -#define CLONE_KEY1_MAYBE 1 -#define CLONE_KEY2_MAYBE 2 -#define swap_clone_flag(A) ((A & 1) << 1) | ((A & 2) >> 1) +/* + Build a range tree for the conjunction of the range parts of two trees + + SYNOPSIS + and_range_trees() + param Context info for the operation + tree1 SEL_TREE for the first conjunct + tree2 SEL_TREE for the second conjunct + result SEL_TREE for the result -static SEL_TREE * -tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2) + DESCRIPTION + This function takes range parts of two trees tree1 and tree2 and builds + a range tree for the conjunction of the formulas that these two range parts + represent. + More exactly: + if the range part of tree1 represents the normalized formula + R1_1 AND ... AND R1_k, + and the range part of tree2 represents the normalized formula + R2_1 AND ... AND R2_k, + then the range part of the result represents the formula: + RT = R_1 AND ... AND R_k, where R_i=(R1_i AND R2_i) for each i from [1..k] + + The function assumes that tree1 is never equal to tree2. At the same + time the tree result can be the same as tree1 (but never as tree2). + If result==tree1 then rt replaces the range part of tree1 leaving + imerges as they are. + if result!=tree1 than it is assumed that the SEL_ARG trees in tree1 and + tree2 should be preserved. Otherwise they can be destroyed. + + RETURN + 1 if the type the result tree is SEL_TREE::IMPOSSIBLE + 0 otherwise +*/ + +static +int and_range_trees(RANGE_OPT_PARAM *param, SEL_TREE *tree1, SEL_TREE *tree2, + SEL_TREE *result) +{ + DBUG_ENTER("and_ranges"); + key_map result_keys; + result_keys.clear_all(); + key_map anded_keys= tree1->keys_map; + anded_keys.merge(tree2->keys_map); + int key_no; + key_map::Iterator it(anded_keys); + while ((key_no= it++) != key_map::Iterator::BITMAP_END) + { + uint flag=0; + SEL_ARG *key1= tree1->keys[key_no]; + SEL_ARG *key2= tree2->keys[key_no]; + if (key1 && !key1->simple_key()) + flag|= CLONE_KEY1_MAYBE; + if (key2 && !key2->simple_key()) + flag|=CLONE_KEY2_MAYBE; + if (result != tree1) + { + if (key1) + key1->incr_refs(); + if (key2) + key2->incr_refs(); + } + SEL_ARG *key; + if ((result->keys[key_no]= key =key_and(param, key1, key2, flag))) + { + if (key && key->type == SEL_ARG::IMPOSSIBLE) + { + result->type= SEL_TREE::IMPOSSIBLE; + DBUG_RETURN(1); + } + result_keys.set_bit(key_no); +#ifdef EXTRA_DEBUG + if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS) + key->test_use_count(key); +#endif + } + } + result->keys_map= result_keys; + DBUG_RETURN(0); +} + + +/* + Build a SEL_TREE for a conjunction out of such trees for the conjuncts + + SYNOPSIS + tree_and() + param Context info for the operation + tree1 SEL_TREE for the first conjunct + tree2 SEL_TREE for the second conjunct + + DESCRIPTION + This function builds a tree for the formula (A AND B) out of the trees + tree1 and tree2 that has been built for the formulas A and B respectively. + + In a general case + tree1 represents the formula RT1 AND MT1, + where RT1 = R1_1 AND ... AND R1_k1, MT1=M1_1 AND ... AND M1_l1; + tree2 represents the formula RT2 AND MT2 + where RT2 = R2_1 AND ... AND R2_k2, MT2=M2_1 and ... and M2_l2. + + The result tree will represent the formula of the the following structure: + RT AND MT1 AND MT2 AND RT1MT2 AND RT2MT1, such that + rt is a tree obtained by range intersection of trees tree1 and tree2, + RT1MT2 = RT1M2_1 AND ... AND RT1M2_l2, + RT2MT1 = RT2M1_1 AND ... AND RT2M1_l1, + where rt1m2_i (i=1,...,l2) is the result of the pushdown operation + of range tree rt1 into imerge m2_i, while rt2m1_j (j=1,...,l1) is the + result of the pushdown operation of range tree rt2 into imerge m1_j. + + RT1MT2/RT2MT is empty if MT2/MT1 is empty. + + The range intersection of two range trees is produced by the function + and_range_trees. The pushdown of a range tree to a imerge is performed + by the function imerge_list_and_tree. This function may produce imerges + containing only one range tree. Such trees are intersected with rt and + the result of intersection is returned as the range part of the result + tree, while the corresponding imerges are removed altogether from its + imerge part. + + NOTE. + The pushdown operation of range trees into imerges is needed to be able + to construct valid imerges for the condition like this: + key1_p1=c1 AND (key1_p2 BETWEEN c21 AND c22 OR key2 < c2) + + RETURN + The result tree, if a success + 0 - otherwise. +*/ + +static +SEL_TREE *tree_and(RANGE_OPT_PARAM *param, SEL_TREE *tree1, SEL_TREE *tree2) { DBUG_ENTER("tree_and"); if (!tree1) @@ -6226,87 +8054,216 @@ tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2) tree1->type=SEL_TREE::KEY_SMALLER; DBUG_RETURN(tree1); } - key_map result_keys; - result_keys.clear_all(); - - /* Join the trees key per key */ - SEL_ARG **key1,**key2,**end; - for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ; - key1 != end ; key1++,key2++) + + if (!tree1->merges.is_empty()) + imerge_list_and_tree(param, &tree1->merges, tree2); + if (!tree2->merges.is_empty()) + imerge_list_and_tree(param, &tree2->merges, tree1); + if (and_range_trees(param, tree1, tree2, tree1)) + DBUG_RETURN(tree1); + imerge_list_and_list(&tree1->merges, &tree2->merges); + eliminate_single_tree_imerges(param, tree1); + DBUG_RETURN(tree1); +} + + +/* + Eliminate single tree imerges in a SEL_TREE objects + + SYNOPSIS + eliminate_single_tree_imerges() + param Context info for the function + tree SEL_TREE where single tree imerges are to be eliminated + + DESCRIPTION + For each imerge in 'tree' that contains only one disjunct tree, i.e. + for any imerge of the form m=rt, the function performs and operation + the range part of tree, replaces rt the with the result of anding and + removes imerge m from the the merge part of 'tree'. + + RETURN VALUE + none +*/ + +static +void eliminate_single_tree_imerges(RANGE_OPT_PARAM *param, SEL_TREE *tree) +{ + SEL_IMERGE *imerge; + List<SEL_IMERGE> merges= tree->merges; + List_iterator<SEL_IMERGE> it(merges); + tree->merges.empty(); + while ((imerge= it++)) { - uint flag=0; - if (*key1 || *key2) - { - if (*key1 && !(*key1)->simple_key()) - flag|=CLONE_KEY1_MAYBE; - if (*key2 && !(*key2)->simple_key()) - flag|=CLONE_KEY2_MAYBE; - *key1=key_and(param, *key1, *key2, flag); - if (*key1 && (*key1)->type == SEL_ARG::IMPOSSIBLE) - { - tree1->type= SEL_TREE::IMPOSSIBLE; - DBUG_RETURN(tree1); - } - result_keys.set_bit(key1 - tree1->keys); -#ifdef EXTRA_DEBUG - if (*key1 && param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS) - (*key1)->test_use_count(*key1); -#endif + if (imerge->trees+1 == imerge->trees_next) + { + tree= tree_and(param, tree, *imerge->trees); + it.remove(); } } - tree1->keys_map= result_keys; - /* dispose index_merge if there is a "range" option */ - if (!result_keys.is_clear_all()) - { - tree1->merges.empty(); - DBUG_RETURN(tree1); - } + tree->merges= merges; +} - /* ok, both trees are index_merge trees */ - imerge_list_and_list(&tree1->merges, &tree2->merges); - DBUG_RETURN(tree1); + +/* + For two trees check that there are indexes with ranges in both of them + + SYNOPSIS + sel_trees_have_common_keys() + tree1 SEL_TREE for the first tree + tree2 SEL_TREE for the second tree + common_keys OUT bitmap of all indexes with ranges in both trees + + DESCRIPTION + For two trees tree1 and tree1 the function checks if there are indexes + in their range parts such that SEL_ARG trees are defined for them in the + range parts of both trees. The function returns the bitmap of such + indexes in the parameter common_keys. + + RETURN + TRUE if there are such indexes (common_keys is nor empty) + FALSE otherwise +*/ + +static +bool sel_trees_have_common_keys(SEL_TREE *tree1, SEL_TREE *tree2, + key_map *common_keys) +{ + *common_keys= tree1->keys_map; + common_keys->intersect(tree2->keys_map); + return !common_keys->is_clear_all(); } /* - Check if two SEL_TREES can be combined into one (i.e. a single key range - read can be constructed for "cond_of_tree1 OR cond_of_tree2" ) without - using index_merge. + Check whether range parts of two trees can be ored for some indexes + + SYNOPSIS + sel_trees_can_be_ored() + param Context info for the function + tree1 SEL_TREE for the first tree + tree2 SEL_TREE for the second tree + common_keys IN/OUT IN: bitmap of all indexes with SEL_ARG in both trees + OUT: bitmap of all indexes that can be ored + + DESCRIPTION + For two trees tree1 and tree2 and the bitmap common_keys containing + bits for indexes that have SEL_ARG trees in range parts of both trees + the function checks if there are indexes for which SEL_ARG trees can + be ored. Two SEL_ARG trees for the same index can be ored if the most + major components of the index used in these trees coincide. If the + SEL_ARG trees for an index cannot be ored the function clears the bit + for this index in the bitmap common_keys. + + The function does not verify that indexes marked in common_keys really + have SEL_ARG trees in both tree1 and tree2. It assumes that this is true. + + NOTE + The function sel_trees_can_be_ored is usually used in pair with the + function sel_trees_have_common_keys. + + RETURN + TRUE if there are indexes for which SEL_ARG trees can be ored + FALSE otherwise */ -bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, - RANGE_OPT_PARAM* param) +static +bool sel_trees_can_be_ored(RANGE_OPT_PARAM* param, + SEL_TREE *tree1, SEL_TREE *tree2, + key_map *common_keys) { - key_map common_keys= tree1->keys_map; DBUG_ENTER("sel_trees_can_be_ored"); - common_keys.intersect(tree2->keys_map); + if (!sel_trees_have_common_keys(tree1, tree2, common_keys)) + DBUG_RETURN(FALSE); + int key_no; + key_map::Iterator it(*common_keys); + while ((key_no= it++) != key_map::Iterator::BITMAP_END) + { + DBUG_ASSERT(tree1->keys[key_no] && tree2->keys[key_no]); + /* Trees have a common key, check if they refer to the same key part */ + if (tree1->keys[key_no]->part != tree2->keys[key_no]->part) + common_keys->clear_bit(key_no); + } + DBUG_RETURN(!common_keys->is_clear_all()); +} + +/* + Check whether range parts of two trees must be ored for some indexes + + SYNOPSIS + sel_trees_must_be_ored() + param Context info for the function + tree1 SEL_TREE for the first tree + tree2 SEL_TREE for the second tree + ordable_keys bitmap of SEL_ARG trees that can be ored + + DESCRIPTION + For two trees tree1 and tree2 the function checks whether they must be + ored. The function assumes that the bitmap ordable_keys contains bits for + those corresponding pairs of SEL_ARG trees from tree1 and tree2 that can + be ored. + We believe that tree1 and tree2 must be ored if any pair of SEL_ARG trees + r1 and r2, such that r1 is from tree1 and r2 is from tree2 and both + of them are marked in ordable_keys, can be merged. + + NOTE + The function sel_trees_must_be_ored as a rule is used in pair with the + function sel_trees_can_be_ored. + + RETURN + TRUE if there are indexes for which SEL_ARG trees must be ored + FALSE otherwise +*/ + +static +bool sel_trees_must_be_ored(RANGE_OPT_PARAM* param, + SEL_TREE *tree1, SEL_TREE *tree2, + key_map oredable_keys) +{ + key_map tmp; + DBUG_ENTER("sel_trees_must_be_ored"); - if (common_keys.is_clear_all()) + tmp= tree1->keys_map; + tmp.merge(tree2->keys_map); + tmp.subtract(oredable_keys); + if (!tmp.is_clear_all()) DBUG_RETURN(FALSE); - /* trees have a common key, check if they refer to same key part */ - SEL_ARG **key1,**key2; - for (uint key_no=0; key_no < param->keys; key_no++) + int idx1, idx2; + key_map::Iterator it1(oredable_keys); + while ((idx1= it1++) != key_map::Iterator::BITMAP_END) { - if (common_keys.is_set(key_no)) + KEY_PART *key1_init= param->key[idx1]+tree1->keys[idx1]->part; + KEY_PART *key1_end= param->key[idx1]+tree1->keys[idx1]->max_part_no; + key_map::Iterator it2(oredable_keys); + while ((idx2= it2++) != key_map::Iterator::BITMAP_END) { - key1= tree1->keys + key_no; - key2= tree2->keys + key_no; - if ((*key1)->part == (*key2)->part) - { - DBUG_RETURN(TRUE); + if (idx2 <= idx1) + continue; + + KEY_PART *key2_init= param->key[idx2]+tree2->keys[idx2]->part; + KEY_PART *key2_end= param->key[idx2]+tree2->keys[idx2]->max_part_no; + KEY_PART *part1, *part2; + for (part1= key1_init, part2= key2_init; + part1 < key1_end && part2 < key2_end; + part1++, part2++) + { + if (!part1->field->eq(part2->field)) + DBUG_RETURN(FALSE); } } } - DBUG_RETURN(FALSE); -} + + DBUG_RETURN(TRUE); +} /* - Remove the trees that are not suitable for record retrieval. + Remove the trees that are not suitable for record retrieval + SYNOPSIS - param Range analysis parameter - tree Tree to be processed, tree->type is KEY or KEY_SMALLER + remove_nonrange_trees() + param Context info for the function + tree Tree to be processed, tree->type is KEY or KEY_SMALLER DESCRIPTION This function walks through tree->keys[] and removes the SEL_ARG* trees @@ -6317,41 +8274,36 @@ bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, A SEL_ARG* tree cannot be used to construct quick select if it has tree->part != 0. (e.g. it could represent "keypart2 < const"). - - WHY THIS FUNCTION IS NEEDED Normally we allow construction of SEL_TREE objects that have SEL_ARG - trees that do not allow quick range select construction. For example for - " keypart1=1 AND keypart2=2 " the execution will proceed as follows: + trees that do not allow quick range select construction. + For example: + for " keypart1=1 AND keypart2=2 " the execution will proceed as follows: tree1= SEL_TREE { SEL_ARG{keypart1=1} } tree2= SEL_TREE { SEL_ARG{keypart2=2} } -- can't make quick range select from this call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG tree. - - There is an exception though: when we construct index_merge SEL_TREE, - any SEL_ARG* tree that cannot be used to construct quick range select can - be removed, because current range analysis code doesn't provide any way - that tree could be later combined with another tree. - Consider an example: we should not construct - st1 = SEL_TREE { - merges = SEL_IMERGE { - SEL_TREE(t.key1part1 = 1), - SEL_TREE(t.key2part2 = 2) -- (*) - } - }; - because - - (*) cannot be used to construct quick range select, - - There is no execution path that would cause (*) to be converted to - a tree that could be used. - - The latter is easy to verify: first, notice that the only way to convert - (*) into a usable tree is to call tree_and(something, (*)). - - Second look at what tree_and/tree_or function would do when passed a - SEL_TREE that has the structure like st1 tree has, and conlcude that - tree_and(something, (*)) will not be called. + Another example: + tree3= SEL_TREE { SEL_ARG{key1part1 = 1} } + tree4= SEL_TREE { SEL_ARG{key2part2 = 2} } -- can't make quick range select + from this + call tree_or(tree3, tree4) -- creates a SEL_MERGE ot of which no index + merge can be constructed, but it is potentially useful, as anding it with + tree5= SEL_TREE { SEL_ARG{key2part1 = 3} } creates an index merge that + represents the formula + key1part1=1 AND key2part1=3 OR key2part1=3 AND key2part2=2 + for which an index merge can be built. + + Any final SEL_TREE may contain SEL_ARG trees for which no quick select + can be built. Such SEL_ARG trees should be removed from the range part + before different range scans are evaluated. Such SEL_ARG trees also should + be removed from all range trees of each index merge before different + possible index merge plans are evaluated. If after this removal one + of the range trees in the index merge becomes empty the whole index merge + must be discarded. + RETURN 0 Ok, some suitable trees left 1 No tree->keys[] left. @@ -6377,6 +8329,74 @@ static bool remove_nonrange_trees(RANGE_OPT_PARAM *param, SEL_TREE *tree) } +/* + Build a SEL_TREE for a disjunction out of such trees for the disjuncts + + SYNOPSIS + tree_or() + param Context info for the operation + tree1 SEL_TREE for the first disjunct + tree2 SEL_TREE for the second disjunct + + DESCRIPTION + This function builds a tree for the formula (A OR B) out of the trees + tree1 and tree2 that has been built for the formulas A and B respectively. + + In a general case + tree1 represents the formula RT1 AND MT1, + where RT1=R1_1 AND ... AND R1_k1, MT1=M1_1 AND ... AND M1_l1; + tree2 represents the formula RT2 AND MT2 + where RT2=R2_1 AND ... AND R2_k2, MT2=M2_1 and ... and M2_l2. + + The function constructs the result tree according the formula + (RT1 OR RT2) AND (MT1 OR RT1) AND (MT2 OR RT2) AND (MT1 OR MT2) + that is equivalent to the formula (RT1 AND MT1) OR (RT2 AND MT2). + + To limit the number of produced imerges the function considers + a weaker formula than the original one: + (RT1 AND M1_1) OR (RT2 AND M2_1) + that is equivalent to: + (RT1 OR RT2) (1) + AND + (M1_1 OR M2_1) (2) + AND + (M1_1 OR RT2) (3) + AND + (M2_1 OR RT1) (4) + + For the first conjunct (1) the function builds a tree with a range part + and, possibly, one imerge. For the other conjuncts (2-4)the function + produces sets of imerges. All constructed imerges are included into the + result tree. + + For the formula (1) the function produces the tree representing a formula + of the structure RT [AND M], such that: + - the range tree rt contains the result of oring SEL_ARG trees from rt1 + and rt2 + - the imerge m consists of two range trees rt1 and rt2. + The imerge m is added if it's not true that rt1 and rt2 must be ored + If rt1 and rt2 can't be ored rt is empty and only m is produced for (1). + + To produce imerges for the formula (2) the function calls the function + imerge_list_or_list passing it the merge parts of tree1 and tree2 as + parameters. + + To produce imerges for the formula (3) the function calls the function + imerge_list_or_tree passing it the imerge m1_1 and the range tree rt2 as + parameters. Similarly, to produce imerges for the formula (4) the function + calls the function imerge_list_or_tree passing it the imerge m2_1 and the + range tree rt1. + + If rt1 is empty then the trees for (1) and (4) are empty. + If rt2 is empty then the trees for (1) and (3) are empty. + If mt1 is empty then the trees for (2) and (3) are empty. + If mt2 is empty then the trees for (2) and (4) are empty. + + RETURN + The result tree for the operation if a success + 0 - otherwise +*/ + static SEL_TREE * tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2) { @@ -6392,74 +8412,100 @@ tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2) if (tree2->type == SEL_TREE::MAYBE) DBUG_RETURN(tree2); - SEL_TREE *result= 0; - key_map result_keys; - result_keys.clear_all(); - if (sel_trees_can_be_ored(tree1, tree2, param)) + SEL_TREE *result= NULL; + key_map result_keys; + key_map ored_keys; + SEL_TREE *rtree[2]= {NULL,NULL}; + SEL_IMERGE *imerge[2]= {NULL, NULL}; + bool no_ranges1= tree1->without_ranges(); + bool no_ranges2= tree2->without_ranges(); + bool no_merges1= tree1->without_imerges(); + bool no_merges2= tree2->without_imerges(); + if (!no_ranges1 && !no_merges2) { - /* Join the trees key per key */ - SEL_ARG **key1,**key2,**end; - for (key1= tree1->keys,key2= tree2->keys,end= key1+param->keys ; - key1 != end ; key1++,key2++) - { - *key1=key_or(param, *key1, *key2); - if (*key1) - { - result=tree1; // Added to tree1 - result_keys.set_bit(key1 - tree1->keys); -#ifdef EXTRA_DEBUG - if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS) - (*key1)->test_use_count(*key1); -#endif - } - } - if (result) - result->keys_map= result_keys; + rtree[0]= new SEL_TREE(tree1, TRUE, param); + imerge[1]= new SEL_IMERGE(tree2->merges.head(), 0, param); } - else + if (!no_ranges2 && !no_merges1) { - /* ok, two trees have KEY type but cannot be used without index merge */ - if (tree1->merges.is_empty() && tree2->merges.is_empty()) + rtree[1]= new SEL_TREE(tree2, TRUE, param); + imerge[0]= new SEL_IMERGE(tree1->merges.head(), 0, param); + } + bool no_imerge_from_ranges= FALSE; + if (!(result= new SEL_TREE())) + DBUG_RETURN(result); + + /* Build the range part of the tree for the formula (1) */ + if (sel_trees_can_be_ored(param, tree1, tree2, &ored_keys)) + { + bool must_be_ored= sel_trees_must_be_ored(param, tree1, tree2, ored_keys); + no_imerge_from_ranges= must_be_ored; + key_map::Iterator it(ored_keys); + int key_no; + while ((key_no= it++) != key_map::Iterator::BITMAP_END) { - if (param->remove_jump_scans) + SEL_ARG *key1= tree1->keys[key_no]; + SEL_ARG *key2= tree2->keys[key_no]; + if (!must_be_ored) { - bool no_trees= remove_nonrange_trees(param, tree1); - no_trees= no_trees || remove_nonrange_trees(param, tree2); - if (no_trees) - DBUG_RETURN(new SEL_TREE(SEL_TREE::ALWAYS)); + key1->incr_refs(); + key2->incr_refs(); } - SEL_IMERGE *merge; - /* both trees are "range" trees, produce new index merge structure */ - if (!(result= new SEL_TREE()) || !(merge= new SEL_IMERGE()) || - (result->merges.push_back(merge)) || - (merge->or_sel_tree(param, tree1)) || - (merge->or_sel_tree(param, tree2))) - result= NULL; - else - result->type= tree1->type; + if ((result->keys[key_no]= key_or(param, key1, key2))) + result->keys_map.set_bit(key_no); } - else if (!tree1->merges.is_empty() && !tree2->merges.is_empty()) - { - if (imerge_list_or_list(param, &tree1->merges, &tree2->merges)) - result= new SEL_TREE(SEL_TREE::ALWAYS); - else - result= tree1; - } - else - { - /* one tree is index merge tree and another is range tree */ - if (tree1->merges.is_empty()) - swap_variables(SEL_TREE*, tree1, tree2); + result->type= tree1->type; + } - if (param->remove_jump_scans && remove_nonrange_trees(param, tree2)) - DBUG_RETURN(new SEL_TREE(SEL_TREE::ALWAYS)); - /* add tree2 to tree1->merges, checking if it collapses to ALWAYS */ - if (imerge_list_or_tree(param, &tree1->merges, tree2)) - result= new SEL_TREE(SEL_TREE::ALWAYS); - else - result= tree1; - } + if (no_imerge_from_ranges && no_merges1 && no_merges2) + { + if (result->keys_map.is_clear_all()) + result->type= SEL_TREE::ALWAYS; + DBUG_RETURN(result); } + + SEL_IMERGE *imerge_from_ranges; + if (!(imerge_from_ranges= new SEL_IMERGE())) + result= NULL; + else if (!no_ranges1 && !no_ranges2 && !no_imerge_from_ranges) + { + /* Build the imerge part of the tree for the formula (1) */ + SEL_TREE *rt1= tree1; + SEL_TREE *rt2= tree2; + if (!no_merges1) + rt1= new SEL_TREE(tree1, TRUE, param); + if (!no_merges2) + rt2= new SEL_TREE(tree2, TRUE, param); + if (!rt1 || !rt2 || + result->merges.push_back(imerge_from_ranges) || + imerge_from_ranges->or_sel_tree(param, rt1) || + imerge_from_ranges->or_sel_tree(param, rt2)) + result= NULL; + } + if (!result) + DBUG_RETURN(result); + + result->type= tree1->type; + + if (!no_merges1 && !no_merges2 && + !imerge_list_or_list(param, &tree1->merges, &tree2->merges)) + { + /* Build the imerges for the formula (2) */ + imerge_list_and_list(&result->merges, &tree1->merges); + } + + /* Build the imerges for the formulas (3) and (4) */ + for (uint i=0; i < 2; i++) + { + List<SEL_IMERGE> merges; + SEL_TREE *rt= rtree[i]; + SEL_IMERGE *im= imerge[1-i]; + + if (rt && im && !merges.push_back(im) && + !imerge_list_or_tree(param, &merges, rt)) + imerge_list_and_list(&result->merges, &merges); + } + DBUG_RETURN(result); } @@ -6505,6 +8551,7 @@ and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, if (!key1) return &null_element; // Impossible ranges key1->use_count++; + key1->max_part_no= max(key2->max_part_no, key2->part+1); return key1; } @@ -6597,6 +8644,7 @@ key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, uint clone_flag) key1->use_count--; key2->use_count--; SEL_ARG *e1=key1->first(), *e2=key2->first(), *new_tree=0; + uint max_part_no= max(key1->max_part_no, key2->max_part_no); while (e1 && e2) { @@ -6634,6 +8682,7 @@ key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, uint clone_flag) key2->free_tree(); if (!new_tree) return &null_element; // Impossible range + new_tree->max_part_no= max_part_no; return new_tree; } @@ -6739,7 +8788,7 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2) { key1->free_tree(); key2->free_tree(); - return 0; // Can't optimize this + return 0; // Can't optimize this } // If one of the key is MAYBE_KEY then the found region may be bigger @@ -6762,247 +8811,548 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2) { swap_variables(SEL_ARG *,key1,key2); } - if (key1->use_count > 0 || !(key1=key1->clone_tree(param))) - return 0; // OOM + if (key1->use_count > 0 && !(key1=key1->clone_tree(param))) + return 0; // OOM } // Add tree at key2 to tree at key1 bool key2_shared=key2->use_count != 0; key1->maybe_flag|=key2->maybe_flag; + /* + Notation for illustrations used in the rest of this function: + + Range: [--------] + ^ ^ + start stop + + Two overlapping ranges: + [-----] [----] [--] + [---] or [---] or [-------] + + Ambiguity: *** + The range starts or stops somewhere in the "***" range. + Example: a starts before b and may end before/the same plase/after b + a: [----***] + b: [---] + + Adjacent ranges: + Ranges that meet but do not overlap. Example: a = "x < 3", b = "x >= 3" + a: ----] + b: [---- + */ + + uint max_part_no= max(key1->max_part_no, key2->max_part_no); + for (key2=key2->first(); key2; ) { - SEL_ARG *tmp=key1->find_range(key2); // Find key1.min <= key2.min - int cmp; + /* + key1 consists of one or more ranges. tmp is the range currently + being handled. + + initialize tmp to the latest range in key1 that starts the same + place or before the range in key2 starts + + key2: [------] + key1: [---] [-----] [----] + ^ + tmp + */ + SEL_ARG *tmp=key1->find_range(key2); + + /* + Used to describe how two key values are positioned compared to + each other. Consider key_value_a.<cmp_func>(key_value_b): + + -2: key_value_a is smaller than key_value_b, and they are adjacent + -1: key_value_a is smaller than key_value_b (not adjacent) + 0: the key values are equal + 1: key_value_a is bigger than key_value_b (not adjacent) + -2: key_value_a is bigger than key_value_b, and they are adjacent + + Example: "cmp= tmp->cmp_max_to_min(key2)" + + key2: [-------- (10 <= x ...) + tmp: -----] (... x < 10) => cmp==-2 + tmp: ----] (... x <= 9) => cmp==-1 + tmp: ------] (... x = 10) => cmp== 0 + tmp: --------] (... x <= 12) => cmp== 1 + (cmp == 2 does not make sense for cmp_max_to_min()) + */ + int cmp= 0; if (!tmp) { - tmp=key1->first(); // tmp.min > key2.min + /* + The range in key2 starts before the first range in key1. Use + the first range in key1 as tmp. + + key2: [--------] + key1: [****--] [----] [-------] + ^ + tmp + */ + tmp=key1->first(); cmp= -1; } - else if ((cmp=tmp->cmp_max_to_min(key2)) < 0) - { // Found tmp.max < key2.min + else if ((cmp= tmp->cmp_max_to_min(key2)) < 0) + { + /* + This is the case: + key2: [-------] + tmp: [----**] + */ SEL_ARG *next=tmp->next; - /* key1 on the left of key2 non-overlapping */ if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part)) { - // Join near ranges like tmp.max < 0 and key2.min >= 0 - SEL_ARG *key2_next=key2->next; - if (key2_shared) - { - if (!(key2=new SEL_ARG(*key2))) - return 0; // out of memory - key2->increment_use_count(key1->use_count+1); - key2->next=key2_next; // New copy of key2 - } - key2->copy_min(tmp); - if (!(key1=key1->tree_delete(tmp))) - { // Only one key in tree - key1=key2; - key1->make_root(); - key2=key2_next; - break; - } + /* + Adjacent (cmp==-2) and equal next_key_parts => ranges can be merged + + This is the case: + key2: [-------] + tmp: [----] + + Result: + key2: [-------------] => inserted into key1 below + tmp: => deleted + */ + SEL_ARG *key2_next=key2->next; + if (key2_shared) + { + if (!(key2=new SEL_ARG(*key2))) + return 0; // out of memory + key2->increment_use_count(key1->use_count+1); + key2->next=key2_next; // New copy of key2 + } + + key2->copy_min(tmp); + if (!(key1=key1->tree_delete(tmp))) + { // Only one key in tree + key1=key2; + key1->make_root(); + key2=key2_next; + break; + } } - if (!(tmp=next)) // tmp.min > key2.min - break; // Copy rest of key2 + if (!(tmp=next)) // Move to next range in key1. Now tmp.min > key2.min + break; // No more ranges in key1. Copy rest of key2 } + if (cmp < 0) - { // tmp.min > key2.min + { + /* + This is the case: + key2: [--***] + tmp: [----] + */ int tmp_cmp; - if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max + if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) { - /* tmp is on the right of key2 non-overlapping */ - if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part)) - { // ranges are connected - tmp->copy_min_to_min(key2); - key1->merge_flags(key2); - if (tmp->min_flag & NO_MIN_RANGE && - tmp->max_flag & NO_MAX_RANGE) - { - if (key1->maybe_flag) - return new SEL_ARG(SEL_ARG::MAYBE_KEY); - return 0; - } - key2->increment_use_count(-1); // Free not used tree - key2=key2->next; - continue; - } - else - { - SEL_ARG *next=key2->next; // Keys are not overlapping - if (key2_shared) - { - SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy - if (!cpy) - return 0; // OOM - key1=key1->insert(cpy); - key2->increment_use_count(key1->use_count+1); - } - else - key1=key1->insert(key2); // Will destroy key2_root - key2=next; - continue; - } + /* + This is the case: + key2: [------**] + tmp: [----] + */ + if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part)) + { + /* + Adjacent ranges with equal next_key_part. Merge like this: + + This is the case: + key2: [------] + tmp: [-----] + + Result: + key2: [------] + tmp: [-------------] + + Then move on to next key2 range. + */ + tmp->copy_min_to_min(key2); + key1->merge_flags(key2); + if (tmp->min_flag & NO_MIN_RANGE && + tmp->max_flag & NO_MAX_RANGE) + { + if (key1->maybe_flag) + return new SEL_ARG(SEL_ARG::MAYBE_KEY); + return 0; + } + key2->increment_use_count(-1); // Free not used tree + key2=key2->next; + continue; + } + else + { + /* + key2 not adjacent to tmp or has different next_key_part. + Insert into key1 and move to next range in key2 + + This is the case: + key2: [------**] + tmp: [----] + + Result: + key1_ [------**][----] + ^ ^ + insert tmp + */ + SEL_ARG *next=key2->next; + if (key2_shared) + { + SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy + if (!cpy) + return 0; // OOM + key1=key1->insert(cpy); + key2->increment_use_count(key1->use_count+1); + } + else + key1=key1->insert(key2); // Will destroy key2_root + key2=next; + continue; + } } } - /* - tmp.min >= key2.min && tmp.min <= key.max (overlapping ranges) - key2.min <= tmp.min <= key2.max - */ + /* + The ranges in tmp and key2 are overlapping: + + key2: [----------] + tmp: [*****-----*****] + + Corollary: tmp.min <= key2.max + */ if (eq_tree(tmp->next_key_part,key2->next_key_part)) { + // Merge overlapping ranges with equal next_key_part if (tmp->is_same(key2)) { - /* - Found exact match of key2 inside key1. + /* + Found exact match of key2 inside key1. Use the relevant range in key1. */ - tmp->merge_flags(key2); // Copy maybe flags - key2->increment_use_count(-1); // Free not used tree + tmp->merge_flags(key2); // Copy maybe flags + key2->increment_use_count(-1); // Free not used tree } else { - SEL_ARG *last=tmp; - SEL_ARG *first=tmp; - /* - Find the last range in tmp that overlaps key2 and has the same - condition on the rest of the keyparts. + SEL_ARG *last= tmp; + SEL_ARG *first= tmp; + + /* + Find the last range in key1 that overlaps key2 and + where all ranges first...last have the same next_key_part as + key2. + + key2: [****----------------------*******] + key1: [--] [----] [---] [-----] [xxxx] + ^ ^ ^ + first last different next_key_part + + Since key2 covers them, the ranges between first and last + are merged into one range by deleting first...last-1 from + the key1 tree. In the figure, this applies to first and the + two consecutive ranges. The range of last is then extended: + * last.min: Set to min(key2.min, first.min) + * last.max: If there is a last->next that overlaps key2 (i.e., + last->next has a different next_key_part): + Set adjacent to last->next.min + Otherwise: Set to max(key2.max, last.max) + + Result: + key2: [****----------------------*******] + [--] [----] [---] => deleted from key1 + key1: [**------------------------***][xxxx] + ^ ^ + tmp=last different next_key_part */ - while (last->next && last->next->cmp_min_to_max(key2) <= 0 && - eq_tree(last->next->next_key_part,key2->next_key_part)) - { + while (last->next && last->next->cmp_min_to_max(key2) <= 0 && + eq_tree(last->next->next_key_part,key2->next_key_part)) + { /* - We've found the last overlapping key1 range in last. - This means that the ranges between (and including) the - first overlapping range (tmp) and the last overlapping range - (last) are fully nested into the current range of key2 - and can safely be discarded. We just need the minimum endpoint - of the first overlapping range (tmp) so we can compare it with - the minimum endpoint of the enclosing key2 range. + last->next is covered by key2 and has same next_key_part. + last can be deleted */ - SEL_ARG *save=last; - last=last->next; - key1=key1->tree_delete(save); - } + SEL_ARG *save=last; + last=last->next; + key1=key1->tree_delete(save); + } + // Redirect tmp to last which will cover the entire range + tmp= last; + /* - The tmp range (the first overlapping range) could have been discarded - by the previous loop. We should re-direct tmp to the new united range - that's taking its place. + We need the minimum endpoint of first so we can compare it + with the minimum endpoint of the enclosing key2 range. */ - tmp= last; last->copy_min(first); bool full_range= last->copy_min(key2); if (!full_range) { if (last->next && key2->cmp_max_to_min(last->next) >= 0) { - last->max_value= last->next->min_value; - if (last->next->min_flag & NEAR_MIN) - last->max_flag&= ~NEAR_MAX; - else - last->max_flag|= NEAR_MAX; + /* + This is the case: + key2: [-------------] + key1: [***------] [xxxx] + ^ ^ + last different next_key_part + + Extend range of last up to last->next: + key2: [-------------] + key1: [***--------][xxxx] + */ + last->copy_min_to_max(last->next); } else + /* + This is the case: + key2: [--------*****] + key1: [***---------] [xxxx] + ^ ^ + last different next_key_part + + Extend range of last up to max(last.max, key2.max): + key2: [--------*****] + key1: [***----------**] [xxxx] + */ full_range= last->copy_max(key2); } - if (full_range) - { // Full range - key1->free_tree(); - for (; key2 ; key2=key2->next) - key2->increment_use_count(-1); // Free not used tree - if (key1->maybe_flag) - return new SEL_ARG(SEL_ARG::MAYBE_KEY); - return 0; - } + if (full_range) + { // Full range + key1->free_tree(); + for (; key2 ; key2=key2->next) + key2->increment_use_count(-1); // Free not used tree + if (key1->maybe_flag) + return new SEL_ARG(SEL_ARG::MAYBE_KEY); + return 0; + } } } if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0) - { // tmp.min <= x < key2.min + { + /* + This is the case ("cmp>=0" means that tmp.max >= key2.min): + key2: [----] + tmp: [------------*****] + */ + + if (!tmp->next_key_part) + { + /* + tmp->next_key_part is empty: cut the range that is covered + by tmp from key2. + Reason: (key2->next_key_part OR tmp->next_key_part) will be + empty and therefore equal to tmp->next_key_part. Thus, this + part of the key2 range is completely covered by tmp. + */ + if (tmp->cmp_max_to_max(key2) >= 0) + { + /* + tmp covers the entire range in key2. + key2: [----] + tmp: [-----------------] + + Move on to next range in key2 + */ + key2->increment_use_count(-1); // Free not used tree + key2=key2->next; + continue; + } + else + { + /* + This is the case: + key2: [-------] + tmp: [---------] + + Result: + key2: [---] + tmp: [---------] + */ + key2->copy_max_to_min(tmp); + continue; + } + } + + /* + The ranges are overlapping but have not been merged because + next_key_part of tmp and key2 differ. + key2: [----] + tmp: [------------*****] + + Split tmp in two where key2 starts: + key2: [----] + key1: [--------][--*****] + ^ ^ + insert tmp + */ SEL_ARG *new_arg=tmp->clone_first(key2); if (!new_arg) - return 0; // OOM - if ((new_arg->next_key_part= key1->next_key_part)) - new_arg->increment_use_count(key1->use_count+1); + return 0; // OOM + if ((new_arg->next_key_part= tmp->next_key_part)) + new_arg->increment_use_count(key1->use_count+1); tmp->copy_min_to_min(key2); key1=key1->insert(new_arg); - } + } // tmp.min >= key2.min due to this if() - // tmp.min >= key2.min && tmp.min <= key2.max - SEL_ARG key(*key2); // Get copy we can modify + /* + Now key2.min <= tmp.min <= key2.max: + key2: [---------] + tmp: [****---*****] + */ + SEL_ARG key2_cpy(*key2); // Get copy we can modify for (;;) { - if (tmp->cmp_min_to_min(&key) > 0) - { // key.min <= x < tmp.min - SEL_ARG *new_arg=key.clone_first(tmp); - if (!new_arg) - return 0; // OOM - if ((new_arg->next_key_part=key.next_key_part)) - new_arg->increment_use_count(key1->use_count+1); - key1=key1->insert(new_arg); - } - if ((cmp=tmp->cmp_max_to_max(&key)) <= 0) - { // tmp.min. <= x <= tmp.max - tmp->maybe_flag|= key.maybe_flag; - key.increment_use_count(key1->use_count+1); - tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part); - if (!cmp) // Key2 is ready - break; - key.copy_max_to_min(tmp); - if (!(tmp=tmp->next)) - { - SEL_ARG *tmp2= new SEL_ARG(key); - if (!tmp2) - return 0; // OOM - key1=key1->insert(tmp2); - key2=key2->next; - goto end; - } - if (tmp->cmp_min_to_max(&key) > 0) - { - SEL_ARG *tmp2= new SEL_ARG(key); - if (!tmp2) - return 0; // OOM - key1=key1->insert(tmp2); - break; - } + if (tmp->cmp_min_to_min(&key2_cpy) > 0) + { + /* + This is the case: + key2_cpy: [------------] + key1: [-*****] + ^ + tmp + + Result: + key2_cpy: [---] + key1: [-------][-*****] + ^ ^ + insert tmp + */ + SEL_ARG *new_arg=key2_cpy.clone_first(tmp); + if (!new_arg) + return 0; // OOM + if ((new_arg->next_key_part=key2_cpy.next_key_part)) + new_arg->increment_use_count(key1->use_count+1); + key1=key1->insert(new_arg); + key2_cpy.copy_min_to_min(tmp); + } + // Now key2_cpy.min == tmp.min + + if ((cmp= tmp->cmp_max_to_max(&key2_cpy)) <= 0) + { + /* + tmp.max <= key2_cpy.max: + key2_cpy: a) [-------] or b) [----] + tmp: [----] [----] + + Steps: + 1) Update next_key_part of tmp: OR it with key2_cpy->next_key_part. + 2) If case a: Insert range [tmp.max, key2_cpy.max] into key1 using + next_key_part of key2_cpy + + Result: + key1: a) [----][-] or b) [----] + */ + tmp->maybe_flag|= key2_cpy.maybe_flag; + key2_cpy.increment_use_count(key1->use_count+1); + tmp->next_key_part= key_or(param, tmp->next_key_part, + key2_cpy.next_key_part); + + if (!cmp) + break; // case b: done with this key2 range + + // Make key2_cpy the range [tmp.max, key2_cpy.max] + key2_cpy.copy_max_to_min(tmp); + if (!(tmp=tmp->next)) + { + /* + No more ranges in key1. Insert key2_cpy and go to "end" + label to insert remaining ranges in key2 if any. + */ + SEL_ARG *tmp2= new SEL_ARG(key2_cpy); + if (!tmp2) + return 0; // OOM + key1=key1->insert(tmp2); + key2=key2->next; + goto end; + } + if (tmp->cmp_min_to_max(&key2_cpy) > 0) + { + /* + The next range in key1 does not overlap with key2_cpy. + Insert this range into key1 and move on to the next range + in key2. + */ + SEL_ARG *tmp2= new SEL_ARG(key2_cpy); + if (!tmp2) + return 0; // OOM + key1=key1->insert(tmp2); + break; + } + /* + key2_cpy overlaps with the next range in key1 and the case + is now "key2.min <= tmp.min <= key2.max". Go back to for(;;) + to handle this situation. + */ + continue; } else { - SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max - if (!new_arg) - return 0; // OOM - tmp->copy_max_to_min(&key); - tmp->increment_use_count(key1->use_count+1); - /* Increment key count as it may be used for next loop */ - key.increment_use_count(1); - new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part); - key1=key1->insert(new_arg); - break; + /* + This is the case: + key2_cpy: [-------] + tmp: [------------] + + Result: + key1: [-------][---] + ^ ^ + new_arg tmp + Steps: + 0) If tmp->next_key_part is empty: do nothing. Reason: + (key2_cpy->next_key_part OR tmp->next_key_part) will be + empty and therefore equal to tmp->next_key_part. Thus, + the range in key2_cpy is completely covered by tmp + 1) Make new_arg with range [tmp.min, key2_cpy.max]. + new_arg->next_key_part is OR between next_key_part + of tmp and key2_cpy + 2) Make tmp the range [key2.max, tmp.max] + 3) Insert new_arg into key1 + */ + if (!tmp->next_key_part) // Step 0 + { + key2_cpy.increment_use_count(-1); // Free not used tree + break; + } + SEL_ARG *new_arg=tmp->clone_last(&key2_cpy); + if (!new_arg) + return 0; // OOM + tmp->copy_max_to_min(&key2_cpy); + tmp->increment_use_count(key1->use_count+1); + /* Increment key count as it may be used for next loop */ + key2_cpy.increment_use_count(1); + new_arg->next_key_part= key_or(param, tmp->next_key_part, + key2_cpy.next_key_part); + key1=key1->insert(new_arg); + break; } } - key2=key2->next; + // Move on to next range in key2 + key2=key2->next; } end: + /* + Add key2 ranges that are non-overlapping with and higher than the + highest range in key1. + */ while (key2) { SEL_ARG *next=key2->next; if (key2_shared) { - SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy + SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy if (!tmp) - return 0; + return 0; key2->increment_use_count(key1->use_count+1); key1=key1->insert(tmp); } else - key1=key1->insert(key2); // Will destroy key2_root + key1=key1->insert(key2); // Will destroy key2_root key2=next; } key1->use_count++; + + key1->max_part_no= max_part_no; return key1; } @@ -7478,11 +9828,7 @@ static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key) void SEL_ARG::test_use_count(SEL_ARG *root) { uint e_count=0; - if (this == root && use_count != 1) - { - sql_print_information("Use_count: Wrong count %lu for root",use_count); - return; - } + if (this->type != SEL_ARG::KEY_RANGE) return; for (SEL_ARG *pos=first(); pos ; pos=pos->next) @@ -7540,9 +9886,9 @@ ha_rows check_quick_select(PARAM *param, uint idx, bool index_only, uint *mrr_flags, uint *bufsize, COST_VECT *cost) { SEL_ARG_RANGE_SEQ seq; - RANGE_SEQ_IF seq_if = {sel_arg_range_seq_init, sel_arg_range_seq_next, 0, 0}; + RANGE_SEQ_IF seq_if = {NULL, sel_arg_range_seq_init, sel_arg_range_seq_next, 0, 0}; handler *file= param->table->file; - ha_rows rows; + ha_rows rows= HA_POS_ERROR; uint keynr= param->real_keynr[idx]; DBUG_ENTER("check_quick_select"); @@ -7575,25 +9921,31 @@ ha_rows check_quick_select(PARAM *param, uint idx, bool index_only, bool pk_is_clustered= file->primary_key_is_clustered(); if (index_only && (file->index_flags(keynr, param->max_key_part, 1) & HA_KEYREAD_ONLY) && - !(pk_is_clustered && keynr == param->table->s->primary_key)) + !(file->index_flags(keynr, param->max_key_part, 1) & HA_CLUSTERED_INDEX)) *mrr_flags |= HA_MRR_INDEX_ONLY; - if (current_thd->lex->sql_command != SQLCOM_SELECT) + if (param->thd->lex->sql_command != SQLCOM_SELECT) *mrr_flags |= HA_MRR_USE_DEFAULT_IMPL; *bufsize= param->thd->variables.mrr_buff_size; - rows= file->multi_range_read_info_const(keynr, &seq_if, (void*)&seq, 0, - bufsize, mrr_flags, cost); + /* + Skip materialized derived table/view result table from MRR check as + they aren't contain any data yet. + */ + if (param->table->pos_in_table_list->is_non_derived()) + rows= file->multi_range_read_info_const(keynr, &seq_if, (void*)&seq, 0, + bufsize, mrr_flags, cost); if (rows != HA_POS_ERROR) { - param->table->quick_rows[keynr]=rows; + param->quick_rows[keynr]= rows; if (update_tbl_stats) { param->table->quick_keys.set_bit(keynr); - param->table->quick_key_parts[keynr]=param->max_key_part+1; + param->table->quick_key_parts[keynr]= param->max_key_part+1; param->table->quick_n_ranges[keynr]= param->range_count; param->table->quick_condition_rows= min(param->table->quick_condition_rows, rows); + param->table->quick_rows[keynr]= rows; } } /* Figure out if the key scan is ROR (returns rows in ROWID order) or not */ @@ -7940,7 +10292,7 @@ bool QUICK_SELECT_I::is_keys_used(const MY_BITMAP *fields) return is_key_used(head, index, fields); } -bool QUICK_INDEX_MERGE_SELECT::is_keys_used(const MY_BITMAP *fields) +bool QUICK_INDEX_SORT_SELECT::is_keys_used(const MY_BITMAP *fields) { QUICK_RANGE_SELECT *quick; List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); @@ -7954,11 +10306,11 @@ bool QUICK_INDEX_MERGE_SELECT::is_keys_used(const MY_BITMAP *fields) bool QUICK_ROR_INTERSECT_SELECT::is_keys_used(const MY_BITMAP *fields) { - QUICK_RANGE_SELECT *quick; - List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); - while ((quick= it++)) + QUICK_SELECT_WITH_RECORD *qr; + List_iterator_fast<QUICK_SELECT_WITH_RECORD> it(quick_selects); + while ((qr= it++)) { - if (is_key_used(head, quick->index, fields)) + if (is_key_used(head, qr->quick->index, fields)) return 1; } return 0; @@ -8094,6 +10446,7 @@ QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table, quick->mrr_buf_size= thd->variables.mrr_buff_size; if (table->file->multi_range_read_info(quick->index, 1, (uint)records, + ~0, &quick->mrr_buf_size, &quick->mrr_flags, &cost)) goto err; @@ -8122,13 +10475,23 @@ err: other error */ -int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge() +int read_keys_and_merge_scans(THD *thd, + TABLE *head, + List<QUICK_RANGE_SELECT> quick_selects, + QUICK_RANGE_SELECT *pk_quick_select, + READ_RECORD *read_record, + bool intersection, + key_map *filtered_scans, + Unique **unique_ptr) { List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects); QUICK_RANGE_SELECT* cur_quick; int result; + Unique *unique= *unique_ptr; handler *file= head->file; - DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::read_keys_and_merge"); + bool with_cpk_filter= pk_quick_select != NULL; + + DBUG_ENTER("read_keys_and_merge"); /* We're going to just read rowids. */ if (!head->key_read) @@ -8139,6 +10502,7 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge() cur_quick_it.rewind(); cur_quick= cur_quick_it++; + bool first_quick= TRUE; DBUG_ASSERT(cur_quick != 0); /* @@ -8156,9 +10520,11 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge() unique= new Unique(refpos_order_cmp, (void *)file, file->ref_length, - thd->variables.sortbuff_size); + thd->variables.sortbuff_size, + intersection ? quick_selects.elements : 0); if (!unique) goto err; + *unique_ptr= unique; } else unique->reset(); @@ -8170,6 +10536,14 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge() { while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE) { + if (intersection) + with_cpk_filter= filtered_scans->is_set(cur_quick->index); + if (first_quick) + { + first_quick= FALSE; + if (intersection && unique->is_in_memory()) + unique->close_for_expansion(); + } cur_quick->range_end(); cur_quick= cur_quick_it++; if (!cur_quick) @@ -8194,8 +10568,8 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge() if (thd->killed) goto err; - /* skip row if it will be retrieved by clustered PK scan */ - if (pk_quick_select && pk_quick_select->row_in_ranges()) + if (with_cpk_filter && + pk_quick_select->row_in_ranges() != intersection ) continue; cur_quick->file->position(cur_quick->record); @@ -8209,14 +10583,13 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge() sequence. */ result= unique->get(head); - doing_pk_scan= FALSE; /* - index_merge currently doesn't support "using index" at all + index merge currently doesn't support "using index" at all */ head->disable_keyread(); - if (init_read_record(&read_record, thd, head, (SQL_SELECT*) 0, 1 , 1, TRUE)) + if (init_read_record(read_record, thd, head, (SQL_SELECT*) 0, 1 , 1, TRUE)) result= 1; - DBUG_RETURN(result); + DBUG_RETURN(result); err: head->disable_keyread(); @@ -8224,6 +10597,17 @@ err: } +int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge() + +{ + int result; + DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::read_keys_and_merge"); + result= read_keys_and_merge_scans(thd, head, quick_selects, pk_quick_select, + &read_record, FALSE, NULL, &unique); + doing_pk_scan= FALSE; + DBUG_RETURN(result); +} + /* Get next row for index_merge. NOTES @@ -8260,6 +10644,32 @@ int QUICK_INDEX_MERGE_SELECT::get_next() DBUG_RETURN(result); } +int QUICK_INDEX_INTERSECT_SELECT::read_keys_and_merge() + +{ + int result; + DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::read_keys_and_merge"); + result= read_keys_and_merge_scans(thd, head, quick_selects, pk_quick_select, + &read_record, TRUE, &filtered_scans, + &unique); + DBUG_RETURN(result); +} + +int QUICK_INDEX_INTERSECT_SELECT::get_next() +{ + int result; + DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::get_next"); + + if ((result= read_record.read_record(&read_record)) == -1) + { + result= HA_ERR_END_OF_FILE; + end_read_record(&read_record); + free_io_cache(head); + } + + DBUG_RETURN(result); +} + /* Retrieve next record. @@ -8283,7 +10693,8 @@ int QUICK_INDEX_MERGE_SELECT::get_next() int QUICK_ROR_INTERSECT_SELECT::get_next() { - List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects); + List_iterator_fast<QUICK_SELECT_WITH_RECORD> quick_it(quick_selects); + QUICK_SELECT_WITH_RECORD *qr; QUICK_RANGE_SELECT* quick; int error, cmp; uint last_rowid_count=0; @@ -8292,7 +10703,8 @@ int QUICK_ROR_INTERSECT_SELECT::get_next() do { /* Get a rowid for first quick and save it as a 'candidate' */ - quick= quick_it++; + qr= quick_it++; + quick= qr->quick; error= quick->get_next(); if (cpk_quick) { @@ -8302,17 +10714,22 @@ int QUICK_ROR_INTERSECT_SELECT::get_next() if (error) DBUG_RETURN(error); + /* Save the read key tuple */ + key_copy(qr->key_tuple, record, head->key_info + quick->index, + quick->max_used_key_length); + quick->file->position(quick->record); memcpy(last_rowid, quick->file->ref, head->file->ref_length); last_rowid_count= 1; while (last_rowid_count < quick_selects.elements) { - if (!(quick= quick_it++)) + if (!(qr= quick_it++)) { quick_it.rewind(); - quick= quick_it++; + qr= quick_it++; } + quick= qr->quick; do { @@ -8322,6 +10739,9 @@ int QUICK_ROR_INTERSECT_SELECT::get_next() cmp= head->file->cmp_ref(quick->file->ref, last_rowid); } while (cmp < 0); + key_copy(qr->key_tuple, record, head->key_info + quick->index, + quick->max_used_key_length); + /* Ok, current select 'caught up' and returned ref >= cur_ref */ if (cmp > 0) { @@ -8337,6 +10757,10 @@ int QUICK_ROR_INTERSECT_SELECT::get_next() } memcpy(last_rowid, quick->file->ref, head->file->ref_length); last_rowid_count= 1; + + //save the fields here + key_copy(qr->key_tuple, record, head->key_info + quick->index, + quick->max_used_key_length); } else { @@ -8349,6 +10773,21 @@ int QUICK_ROR_INTERSECT_SELECT::get_next() if (need_to_fetch_row) error= head->file->ha_rnd_pos(head->record[0], last_rowid); } while (error == HA_ERR_RECORD_DELETED); + + if (!need_to_fetch_row) + { + /* Restore the columns we've read/saved with other quick selects */ + quick_it.rewind(); + while ((qr= quick_it++)) + { + if (qr->quick != quick) + { + key_restore(record, qr->key_tuple, head->key_info + qr->quick->index, + qr->quick->max_used_key_length); + } + } + } + DBUG_RETURN(error); } @@ -8469,7 +10908,7 @@ int QUICK_RANGE_SELECT::reset() if (!mrr_buf_desc) empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL; - RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next, 0, 0}; + RANGE_SEQ_IF seq_funcs= {NULL, quick_range_seq_init, quick_range_seq_next, 0, 0}; error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements, mrr_flags, mrr_buf_desc? mrr_buf_desc: &empty_buf); @@ -8494,7 +10933,7 @@ int QUICK_RANGE_SELECT::reset() int QUICK_RANGE_SELECT::get_next() { - char *dummy; + range_id_t dummy; DBUG_ENTER("QUICK_RANGE_SELECT::get_next"); if (in_ror_merged_scan) { @@ -8893,30 +11332,53 @@ bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range_arg) } -void QUICK_RANGE_SELECT::add_info_string(String *str) +void QUICK_SELECT_I::add_key_name(String *str, bool *first) { KEY *key_info= head->key_info + index; + + if (*first) + *first= FALSE; + else + str->append(','); str->append(key_info->name); } + + +void QUICK_RANGE_SELECT::add_info_string(String *str) +{ + bool first= TRUE; + + add_key_name(str, &first); +} void QUICK_INDEX_MERGE_SELECT::add_info_string(String *str) { QUICK_RANGE_SELECT *quick; bool first= TRUE; List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); + str->append(STRING_WITH_LEN("sort_union(")); while ((quick= it++)) { - if (!first) - str->append(','); - else - first= FALSE; - quick->add_info_string(str); + quick->add_key_name(str, &first); } if (pk_quick_select) + pk_quick_select->add_key_name(str, &first); + str->append(')'); +} + +void QUICK_INDEX_INTERSECT_SELECT::add_info_string(String *str) +{ + QUICK_RANGE_SELECT *quick; + bool first= TRUE; + List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); + + str->append(STRING_WITH_LEN("sort_intersect(")); + if (pk_quick_select) + pk_quick_select->add_key_name(str, &first); + while ((quick= it++)) { - str->append(','); - pk_quick_select->add_info_string(str); + quick->add_key_name(str, &first); } str->append(')'); } @@ -8924,132 +11386,127 @@ void QUICK_INDEX_MERGE_SELECT::add_info_string(String *str) void QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str) { bool first= TRUE; - QUICK_RANGE_SELECT *quick; - List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); + QUICK_SELECT_WITH_RECORD *qr; + List_iterator_fast<QUICK_SELECT_WITH_RECORD> it(quick_selects); + str->append(STRING_WITH_LEN("intersect(")); - while ((quick= it++)) + while ((qr= it++)) { - KEY *key_info= head->key_info + quick->index; - if (!first) - str->append(','); - else - first= FALSE; - str->append(key_info->name); + qr->quick->add_key_name(str, &first); } if (cpk_quick) - { - KEY *key_info= head->key_info + cpk_quick->index; - str->append(','); - str->append(key_info->name); - } + cpk_quick->add_key_name(str, &first); str->append(')'); } + void QUICK_ROR_UNION_SELECT::add_info_string(String *str) { - bool first= TRUE; QUICK_SELECT_I *quick; + bool first= TRUE; List_iterator_fast<QUICK_SELECT_I> it(quick_selects); + str->append(STRING_WITH_LEN("union(")); while ((quick= it++)) { - if (!first) - str->append(','); - else + if (first) first= FALSE; + else + str->append(','); quick->add_info_string(str); } str->append(')'); } -void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names, - String *used_lengths) +void QUICK_SELECT_I::add_key_and_length(String *key_names, + String *used_lengths, + bool *first) { char buf[64]; uint length; KEY *key_info= head->key_info + index; + + if (*first) + *first= FALSE; + else + { + key_names->append(','); + used_lengths->append(','); + } key_names->append(key_info->name); length= longlong10_to_str(max_used_key_length, buf, 10) - buf; used_lengths->append(buf, length); } + +void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names, + String *used_lengths) +{ + bool first= TRUE; + + add_key_and_length(key_names, used_lengths, &first); +} + void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names, String *used_lengths) { - char buf[64]; - uint length; - bool first= TRUE; QUICK_RANGE_SELECT *quick; + bool first= TRUE; List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); + while ((quick= it++)) { - if (first) - first= FALSE; - else - { - key_names->append(','); - used_lengths->append(','); - } - - KEY *key_info= head->key_info + quick->index; - key_names->append(key_info->name); - length= longlong10_to_str(quick->max_used_key_length, buf, 10) - buf; - used_lengths->append(buf, length); + quick->add_key_and_length(key_names, used_lengths, &first); } + if (pk_quick_select) - { - KEY *key_info= head->key_info + pk_quick_select->index; - key_names->append(','); - key_names->append(key_info->name); - length= (longlong10_to_str(pk_quick_select->max_used_key_length, buf, 10) - - buf); - used_lengths->append(','); - used_lengths->append(buf, length); - } + pk_quick_select->add_key_and_length(key_names, used_lengths, &first); } -void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names, - String *used_lengths) + +void QUICK_INDEX_INTERSECT_SELECT::add_keys_and_lengths(String *key_names, + String *used_lengths) { - char buf[64]; - uint length; - bool first= TRUE; QUICK_RANGE_SELECT *quick; + bool first= TRUE; + List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); + + if (pk_quick_select) + pk_quick_select->add_key_and_length(key_names, used_lengths, &first); + while ((quick= it++)) { - KEY *key_info= head->key_info + quick->index; - if (first) - first= FALSE; - else - { - key_names->append(','); - used_lengths->append(','); - } - key_names->append(key_info->name); - length= longlong10_to_str(quick->max_used_key_length, buf, 10) - buf; - used_lengths->append(buf, length); + quick->add_key_and_length(key_names, used_lengths, &first); } +} - if (cpk_quick) +void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names, + String *used_lengths) +{ + QUICK_SELECT_WITH_RECORD *qr; + bool first= TRUE; + + List_iterator_fast<QUICK_SELECT_WITH_RECORD> it(quick_selects); + + while ((qr= it++)) { - KEY *key_info= head->key_info + cpk_quick->index; - key_names->append(','); - key_names->append(key_info->name); - length= longlong10_to_str(cpk_quick->max_used_key_length, buf, 10) - buf; - used_lengths->append(','); - used_lengths->append(buf, length); + qr->quick->add_key_and_length(key_names, used_lengths, &first); } + if (cpk_quick) + cpk_quick->add_key_and_length(key_names, used_lengths, &first); } void QUICK_ROR_UNION_SELECT::add_keys_and_lengths(String *key_names, String *used_lengths) { - bool first= TRUE; QUICK_SELECT_I *quick; + bool first= TRUE; + List_iterator_fast<QUICK_SELECT_I> it(quick_selects); + while ((quick= it++)) { if (first) @@ -9078,7 +11535,7 @@ static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree, uchar *key_infix, uint *key_infix_len, KEY_PART_INFO **first_non_infix_part); static bool -check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item, +check_group_min_max_predicates(Item *cond, Item_field *min_max_arg_item, Field::imagetype image_type); static void @@ -9241,7 +11698,7 @@ get_best_group_min_max(PARAM *param, SEL_TREE *tree, double read_time) /* Perform few 'cheap' tests whether this access method is applicable. */ if (!join) DBUG_RETURN(NULL); /* This is not a select statement. */ - if ((join->tables != 1) || /* The query must reference one table. */ + if ((join->table_count != 1) || /* The query must reference one table. */ (join->select_lex->olap == ROLLUP_TYPE)) /* Check (B3) for ROLLUP */ DBUG_RETURN(NULL); if (table->s->keys == 0) /* There are no indexes to use. */ @@ -9677,14 +12134,14 @@ get_best_group_min_max(PARAM *param, SEL_TREE *tree, double read_time) */ static bool -check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item, +check_group_min_max_predicates(Item *cond, Item_field *min_max_arg_item, Field::imagetype image_type) { DBUG_ENTER("check_group_min_max_predicates"); DBUG_ASSERT(cond && min_max_arg_item); cond= cond->real_item(); - Item::Type cond_type= cond->type(); + Item::Type cond_type= cond->real_type(); if (cond_type == Item::COND_ITEM) /* 'AND' or 'OR' */ { DBUG_PRINT("info", ("Analyzing: %s", ((Item_func*) cond)->func_name())); @@ -9700,18 +12157,27 @@ check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item, } /* - TODO: - This is a very crude fix to handle sub-selects in the WHERE clause - (Item_subselect objects). With the test below we rule out from the - optimization all queries with subselects in the WHERE clause. What has to - be done, is that here we should analyze whether the subselect references - the MIN/MAX argument field, and disallow the optimization only if this is - so. + Disallow loose index scan if the MIN/MAX argument field is referenced by + a subquery in the WHERE clause. */ - if (cond_type == Item::SUBSELECT_ITEM || - (cond->get_cached_item() && - cond->get_cached_item()->type() == Item::SUBSELECT_ITEM)) - DBUG_RETURN(FALSE); + + if (cond_type == Item::SUBSELECT_ITEM) + { + Item_subselect *subs_cond= (Item_subselect*) cond; + if (subs_cond->is_correlated) + { + DBUG_ASSERT(subs_cond->upper_refs.elements > 0); + List_iterator_fast<Item_subselect::Ref_to_outside> + li(subs_cond->upper_refs); + Item_subselect::Ref_to_outside *dep; + while ((dep= li++)) + { + if (dep->item->eq(min_max_arg_item, FALSE)) + DBUG_RETURN(FALSE); + } + } + DBUG_RETURN(TRUE); + } /* Condition of the form 'field' is equivalent to 'field <> 0' and thus @@ -9858,13 +12324,14 @@ get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree, Find the range tree for the current keypart. We assume that index_range_tree points to the leftmost keypart in the index. */ - for (cur_range= index_range_tree; cur_range; + for (cur_range= index_range_tree; + cur_range && cur_range->type == SEL_ARG::KEY_RANGE; cur_range= cur_range->next_key_part) { if (cur_range->field->eq(cur_part->field)) break; } - if (!cur_range) + if (!cur_range || cur_range->type != SEL_ARG::KEY_RANGE) { if (min_max_arg_part) return FALSE; /* The current keypart has no range predicates at all. */ @@ -11053,6 +13520,7 @@ int QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range() /* Compare the found key with max_key. */ int cmp_res= key_cmp(index_info->key_part, max_key, real_prefix_len + min_max_arg_len); + my_afree(max_key); /* The key is outside of the range if: the interval is open and the key is equal to the maximum boundry @@ -11178,6 +13646,7 @@ int QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range() /* Compare the found key with min_key. */ int cmp_res= key_cmp(index_info->key_part, min_key, real_prefix_len + min_max_arg_len); + my_afree(min_key); /* The key is outside of the range if: the interval is open and the key is equal to the minimum boundry @@ -11278,11 +13747,9 @@ void QUICK_GROUP_MIN_MAX_SELECT::update_max_result() void QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names, String *used_lengths) { - char buf[64]; - uint length; - key_names->append(index_info->name); - length= longlong10_to_str(max_used_key_length, buf, 10) - buf; - used_lengths->append(buf, length); + bool first= TRUE; + + add_key_and_length(key_names, used_lengths, &first); } @@ -11313,7 +13780,8 @@ static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map, if (!tmp.length()) tmp.append(STRING_WITH_LEN("(empty)")); - DBUG_PRINT("info", ("SEL_TREE: 0x%lx (%s) scans: %s", (long) tree, msg, tmp.ptr())); + DBUG_PRINT("info", ("SEL_TREE: 0x%lx (%s) scans: %s", (long) tree, msg, + tmp.c_ptr_safe())); DBUG_VOID_RETURN; } @@ -11336,7 +13804,7 @@ static void print_ror_scans_arr(TABLE *table, const char *msg, } if (!tmp.length()) tmp.append(STRING_WITH_LEN("(empty)")); - DBUG_PRINT("info", ("ROR key scans (%s): %s", msg, tmp.ptr())); + DBUG_PRINT("info", ("ROR key scans (%s): %s", msg, tmp.c_ptr())); DBUG_VOID_RETURN; } @@ -11353,7 +13821,6 @@ print_key(KEY_PART *key_part, const uchar *key, uint used_length) { char buff[1024]; const uchar *key_end= key+used_length; - String tmp(buff,sizeof(buff),&my_charset_bin); uint store_length; TABLE *table= key_part->field->table; my_bitmap_map *old_sets[2]; @@ -11362,6 +13829,7 @@ print_key(KEY_PART *key_part, const uchar *key, uint used_length) for (; key < key_end; key+=store_length, key_part++) { + String tmp(buff,sizeof(buff),&my_charset_bin); Field *field= key_part->field; store_length= key_part->store_length; @@ -11449,8 +13917,7 @@ void QUICK_RANGE_SELECT::dbug_dump(int indent, bool verbose) /* purecov: end */ } - -void QUICK_INDEX_MERGE_SELECT::dbug_dump(int indent, bool verbose) +void QUICK_INDEX_SORT_SELECT::dbug_dump(int indent, bool verbose) { List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); QUICK_RANGE_SELECT *quick; @@ -11468,13 +13935,13 @@ void QUICK_INDEX_MERGE_SELECT::dbug_dump(int indent, bool verbose) void QUICK_ROR_INTERSECT_SELECT::dbug_dump(int indent, bool verbose) { - List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); - QUICK_RANGE_SELECT *quick; + List_iterator_fast<QUICK_SELECT_WITH_RECORD> it(quick_selects); + QUICK_SELECT_WITH_RECORD *qr; fprintf(DBUG_FILE, "%*squick ROR-intersect select, %scovering\n", indent, "", need_to_fetch_row? "":"non-"); fprintf(DBUG_FILE, "%*smerged scans {\n", indent, ""); - while ((quick= it++)) - quick->dbug_dump(indent+2, verbose); + while ((qr= it++)) + qr->quick->dbug_dump(indent+2, verbose); if (cpk_quick) { fprintf(DBUG_FILE, "%*sclustered PK quick:\n", indent, ""); |