diff options
Diffstat (limited to 'sql/opt_range.cc')
| -rw-r--r-- | sql/opt_range.cc | 98 |
1 files changed, 65 insertions, 33 deletions
diff --git a/sql/opt_range.cc b/sql/opt_range.cc index 731e9872aa5..ac5b1f575de 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -457,10 +457,10 @@ public: range_key, *range_key_flag); *range_key_flag|= key_tree->min_flag; if (key_tree->next_key_part && + key_tree->next_key_part->type == SEL_ARG::KEY_RANGE && key_tree->part != last_part && key_tree->next_key_part->part == key_tree->part+1 && - !(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) && - key_tree->next_key_part->type == SEL_ARG::KEY_RANGE) + !(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN))) res+= key_tree->next_key_part->store_min_key(key, range_key, range_key_flag, @@ -479,10 +479,10 @@ public: range_key, *range_key_flag); (*range_key_flag)|= key_tree->max_flag; if (key_tree->next_key_part && + key_tree->next_key_part->type == SEL_ARG::KEY_RANGE && key_tree->part != last_part && - key_tree->next_key_part->part == key_tree->part+1 && - !(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) && - key_tree->next_key_part->type == SEL_ARG::KEY_RANGE) + key_tree->next_key_part->part == key_tree->part+1 && + !(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX))) res+= key_tree->next_key_part->store_max_key(key, range_key, range_key_flag, @@ -1727,6 +1727,7 @@ SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, tmp->prev= *next_arg; // Link into next/prev chain (*next_arg)->next=tmp; (*next_arg)= tmp; + tmp->part= this->part; } else { @@ -6848,6 +6849,7 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2) else if ((cmp=tmp->cmp_max_to_min(key2)) < 0) { // Found tmp.max < key2.min 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 @@ -6876,6 +6878,7 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2) int tmp_cmp; if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max { + /* 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); @@ -6910,25 +6913,52 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2) } } - // tmp.max >= key2.min && tmp.min <= key.max (overlapping ranges) + /* + tmp.min >= key2.min && tmp.min <= key.max (overlapping ranges) + key2.min <= tmp.min <= key2.max + */ if (eq_tree(tmp->next_key_part,key2->next_key_part)) { if (tmp->is_same(key2)) { + /* + 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 } 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. + */ 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. + */ SEL_ARG *save=last; last=last->next; key1=key1->tree_delete(save); } - last->copy_min(tmp); + /* + 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. + */ + tmp= last; + last->copy_min(first); bool full_range= last->copy_min(key2); if (!full_range) { @@ -7438,27 +7468,25 @@ int test_rb_tree(SEL_ARG *element,SEL_ARG *parent) } -/* - Count how many times SEL_ARG graph "root" refers to its part "key" +/** + Count how many times SEL_ARG graph "root" refers to its part "key" via + transitive closure. - SYNOPSIS - count_key_part_usage() - root An RB-Root node in a SEL_ARG graph. - key Another RB-Root node in that SEL_ARG graph. - - DESCRIPTION - The passed "root" node may refer to "key" node via root->next_key_part, - root->next->n - - This function counts how many times the node "key" is referred (via - SEL_ARG::next_key_part) by - - intervals of RB-tree pointed by "root", - - intervals of RB-trees that are pointed by SEL_ARG::next_key_part from - intervals of RB-tree pointed by "root", - - and so on. + @param root An RB-Root node in a SEL_ARG graph. + @param key Another RB-Root node in that SEL_ARG graph. + + The passed "root" node may refer to "key" node via root->next_key_part, + root->next->n + + This function counts how many times the node "key" is referred (via + SEL_ARG::next_key_part) by + - intervals of RB-tree pointed by "root", + - intervals of RB-trees that are pointed by SEL_ARG::next_key_part from + intervals of RB-tree pointed by "root", + - and so on. - Here is an example (horizontal links represent next_key_part pointers, - vertical links - next/prev prev pointers): + Here is an example (horizontal links represent next_key_part pointers, + vertical links - next/prev prev pointers): +----+ $ |root|-----------------+ @@ -7478,8 +7506,8 @@ int test_rb_tree(SEL_ARG *element,SEL_ARG *parent) ... +---+ $ | | |------------+ +---+ $ - RETURN - Number of links to "key" from nodes reachable from "root". + @return + Number of links to "key" from nodes reachable from "root". */ static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key) @@ -7734,8 +7762,8 @@ check_quick_keys(PARAM *param, uint idx, SEL_ARG *key_tree, param->first_null_comp= key_tree->part+1; if (key_tree->next_key_part && - key_tree->next_key_part->part == key_tree->part+1 && - key_tree->next_key_part->type == SEL_ARG::KEY_RANGE) + key_tree->next_key_part->type == SEL_ARG::KEY_RANGE && + key_tree->next_key_part->part == key_tree->part+1) { // const key as prefix if (min_key_length == max_key_length && !memcmp(min_key, max_key, (uint) (tmp_max_key - max_key)) && @@ -8020,8 +8048,8 @@ get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key, &tmp_max_key,max_key_flag); if (key_tree->next_key_part && - key_tree->next_key_part->part == key_tree->part+1 && - key_tree->next_key_part->type == SEL_ARG::KEY_RANGE) + key_tree->next_key_part->type == SEL_ARG::KEY_RANGE && + key_tree->next_key_part->part == key_tree->part+1) { // const key as prefix if ((tmp_min_key - min_key) == (tmp_max_key - max_key) && memcmp(min_key, max_key, (uint)(tmp_max_key - max_key))==0 && @@ -10032,7 +10060,11 @@ check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item, } else if (cur_arg->const_item()) { - DBUG_RETURN(TRUE); + /* + For predicates of the form "const OP expr" we also have to check 'expr' + to make a decision. + */ + continue; } else DBUG_RETURN(FALSE); |