[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (igor:2747)
#At lp:maria based on revid:igor@askmonty.org-20091026173514-biry7lgxqiz2zz7a 2747 Igor Babaev 2009-10-29 Replaced a lame implementation of the function sel_trees_must_be_ored that blocked building index merge plans for the queries with where conditions of the form (key1|2_p1=c AND range(key1_p2)) OR (key1|2_p1=c AND range(key2_p2)). The problem was discovered by Sergey Petrunia when he reviewed the patch for WL#24. Added new test cases. One of them failed to produce an index merge plan before the patch was applied. modified: mysql-test/r/range_vs_index_merge.result mysql-test/r/range_vs_index_merge_innodb.result mysql-test/t/range_vs_index_merge.test sql/opt_range.cc === modified file 'mysql-test/r/range_vs_index_merge.result' --- a/mysql-test/r/range_vs_index_merge.result 2009-10-17 18:40:46 +0000 +++ b/mysql-test/r/range_vs_index_merge.result 2009-10-29 18:49:58 +0000 @@ -1076,6 +1076,68 @@ ID BETWEEN 3500 AND 3800) AND Country='U AND (Name LIKE 'Pho%' OR ID BETWEEN 4000 AND 4300); ID Name Country Population 3798 Phoenix USA 1321045 +DROP INDEX Population ON City; +DROP INDEX Name ON City; +EXPLAIN +SELECT * FROM City +WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR +Country='USA' AND Name LIKE 'Pa%'; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE City index_merge Country,CountryPopulation,CountryName CountryPopulation,CountryName 7,38 NULL 10 Using sort_union(CountryPopulation,CountryName); Using where +SELECT * FROM City USE INDEX() +WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR +Country='USA' AND Name LIKE 'Pa%'; +ID Name Country Population +3932 Paterson USA 149222 +3943 Pasadena USA 141674 +3953 Pasadena USA 133936 +3967 Paradise USA 124682 +3986 Palmdale USA 116670 +4030 Sandy USA 101853 +4031 Athens-Clarke County USA 101489 +4032 Cambridge USA 101355 +SELECT * FROM City +WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR +Country='USA' AND Name LIKE 'Pa%'; +ID Name Country Population +3932 Paterson USA 149222 +3943 Pasadena USA 141674 +3953 Pasadena USA 133936 +3967 Paradise USA 124682 +3986 Palmdale USA 116670 +4030 Sandy USA 101853 +4031 Athens-Clarke County USA 101489 +4032 Cambridge USA 101355 +EXPLAIN +SELECT * FROM City +WHERE Country='USA' AND +(Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%'); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE City index_merge Country,CountryPopulation,CountryName CountryPopulation,CountryName 7,38 NULL 10 Using sort_union(CountryPopulation,CountryName); Using where +SELECT * FROM City +WHERE Country='USA' AND +(Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%'); +ID Name Country Population +3932 Paterson USA 149222 +3943 Pasadena USA 141674 +3953 Pasadena USA 133936 +3967 Paradise USA 124682 +3986 Palmdale USA 116670 +4030 Sandy USA 101853 +4031 Athens-Clarke County USA 101489 +4032 Cambridge USA 101355 +SELECT * FROM City +WHERE Country='USA' AND +(Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%'); +ID Name Country Population +3932 Paterson USA 149222 +3943 Pasadena USA 141674 +3953 Pasadena USA 133936 +3967 Paradise USA 124682 +3986 Palmdale USA 116670 +4030 Sandy USA 101853 +4031 Athens-Clarke County USA 101489 +4032 Cambridge USA 101355 DROP DATABASE world; use test; CREATE TABLE t1 ( === modified file 'mysql-test/r/range_vs_index_merge_innodb.result' --- a/mysql-test/r/range_vs_index_merge_innodb.result 2009-10-17 18:40:46 +0000 +++ b/mysql-test/r/range_vs_index_merge_innodb.result 2009-10-29 18:49:58 +0000 @@ -1077,6 +1077,68 @@ ID BETWEEN 3500 AND 3800) AND Country='U AND (Name LIKE 'Pho%' OR ID BETWEEN 4000 AND 4300); ID Name Country Population 3798 Phoenix USA 1321045 +DROP INDEX Population ON City; +DROP INDEX Name ON City; +EXPLAIN +SELECT * FROM City +WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR +Country='USA' AND Name LIKE 'Pa%'; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE City index_merge Country,CountryPopulation,CountryName CountryPopulation,CountryName 7,38 NULL 8 Using sort_union(CountryPopulation,CountryName); Using where +SELECT * FROM City USE INDEX() +WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR +Country='USA' AND Name LIKE 'Pa%'; +ID Name Country Population +3932 Paterson USA 149222 +3943 Pasadena USA 141674 +3953 Pasadena USA 133936 +3967 Paradise USA 124682 +3986 Palmdale USA 116670 +4030 Sandy USA 101853 +4031 Athens-Clarke County USA 101489 +4032 Cambridge USA 101355 +SELECT * FROM City +WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR +Country='USA' AND Name LIKE 'Pa%'; +ID Name Country Population +3932 Paterson USA 149222 +3943 Pasadena USA 141674 +3953 Pasadena USA 133936 +3967 Paradise USA 124682 +3986 Palmdale USA 116670 +4030 Sandy USA 101853 +4031 Athens-Clarke County USA 101489 +4032 Cambridge USA 101355 +EXPLAIN +SELECT * FROM City +WHERE Country='USA' AND +(Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%'); +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE City index_merge Country,CountryPopulation,CountryName CountryPopulation,CountryName 7,38 NULL 8 Using sort_union(CountryPopulation,CountryName); Using where +SELECT * FROM City +WHERE Country='USA' AND +(Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%'); +ID Name Country Population +3932 Paterson USA 149222 +3943 Pasadena USA 141674 +3953 Pasadena USA 133936 +3967 Paradise USA 124682 +3986 Palmdale USA 116670 +4030 Sandy USA 101853 +4031 Athens-Clarke County USA 101489 +4032 Cambridge USA 101355 +SELECT * FROM City +WHERE Country='USA' AND +(Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%'); +ID Name Country Population +3932 Paterson USA 149222 +3943 Pasadena USA 141674 +3953 Pasadena USA 133936 +3967 Paradise USA 124682 +3986 Palmdale USA 116670 +4030 Sandy USA 101853 +4031 Athens-Clarke County USA 101489 +4032 Cambridge USA 101355 DROP DATABASE world; use test; CREATE TABLE t1 ( === modified file 'mysql-test/t/range_vs_index_merge.test' --- a/mysql-test/t/range_vs_index_merge.test 2009-10-17 18:40:46 +0000 +++ b/mysql-test/t/range_vs_index_merge.test 2009-10-29 18:49:58 +0000 @@ -570,6 +570,51 @@ SELECT * FROM City AND (Name LIKE 'Pho%' OR ID BETWEEN 4000 AND 4300); +DROP INDEX Population ON City; +DROP INDEX Name ON City; + +# The pattern of the WHERE condition used in the following query is +# (key1|2_p1=c AND range(key1_p2)) OR (key1|2_p1=c AND range(key2_p2)) +# We get an index merge retrieval over key1, key2 for it + +EXPLAIN +SELECT * FROM City + WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR + Country='USA' AND Name LIKE 'Pa%'; + +# The following 2 queries check that the plans +# for the previous plan is valid + +SELECT * FROM City USE INDEX() + WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR + Country='USA' AND Name LIKE 'Pa%'; + +SELECT * FROM City + WHERE Country='USA' AND Population BETWEEN 101000 AND 102000 OR + Country='USA' AND Name LIKE 'Pa%'; + + +# The pattern of the WHERE condition used in the following query is +# key1|2_p1=c AND (range(key1_p2) OR range(key2_p2)) +# We get an index merge retrieval over key1, key2 for it + +EXPLAIN +SELECT * FROM City + WHERE Country='USA' AND + (Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%'); + +# The following 2 queries check that the plans +# for the previous plan is valid + +SELECT * FROM City + WHERE Country='USA' AND + (Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%'); + +SELECT * FROM City + WHERE Country='USA' AND + (Population BETWEEN 101000 AND 102000 OR Name LIKE 'Pa%'); + + DROP DATABASE world; use test; === modified file 'sql/opt_range.cc' --- a/sql/opt_range.cc 2009-10-12 04:59:34 +0000 +++ b/sql/opt_range.cc 2009-10-29 18:49:58 +0000 @@ -262,6 +262,11 @@ public: uint8 part; // Which key part uint8 maybe_null; /* + The ordinal number the least significant component encountered the ranges + of the SEL_ARG tree (the first component has number 1) + */ + uint max_part_no; + /* Number of children of this element in the RB-tree, plus 1 for this element itself. */ @@ -737,12 +742,12 @@ public: uint real_keynr[MAX_KEY]; /* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */ uint alloced_sel_args; + 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; @@ -2172,6 +2177,7 @@ SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_allo 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; } @@ -2189,7 +2195,7 @@ SEL_ARG::SEL_ARG(Field *f,const uchar *m :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), max_part_no(1) { left=right= &null_element; } @@ -2202,6 +2208,7 @@ SEL_ARG::SEL_ARG(Field *field_,uint8 par 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; } @@ -2244,6 +2251,7 @@ SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM increment_use_count(1); tmp->color= color; tmp->elements= this->elements; + tmp->max_part_no= max_part_no; return tmp; } @@ -7000,14 +7008,14 @@ bool sel_trees_can_be_ored(RANGE_OPT_PAR ordable_keys bitmap of SEL_ARG trees that can be ored DESCRIPTION - For two trees tree1 and tree2 and the bitmap ordable_keys containing - bits for indexes that have SEL_ARG trees in range parts of both trees - and these SEL_ARG trees can be ored the function checks if there are - indexes for which SEL_ARG trees must be ored. Two SEL_ARG trees for the - same index must be ored if all indexes for which SEL_SRG trees from the - range parts of tree1 anf tree2 that can be ored have the same field as - their major index component. - + 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. @@ -7031,21 +7039,31 @@ bool sel_trees_must_be_ored(RANGE_OPT_PA if (!tmp.is_clear_all()) DBUG_RETURN(FALSE); - Field *field= 0; - uint part; - int key_no; - key_map::Iterator it(oredable_keys); - while ((key_no= it++) != key_map::Iterator::BITMAP_END) - { - SEL_ARG *key1= tree1->keys[key_no]; - if (!field) + int idx1, idx2; + key_map::Iterator it1(oredable_keys); + while ((idx1= it1++) != key_map::Iterator::BITMAP_END) + { + 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) { - field= key1->field; - part= key1->part; + 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); + } } - else if (!field->eq(key1->field)) - DBUG_RETURN(FALSE); } + DBUG_RETURN(TRUE); } @@ -7342,6 +7360,7 @@ and_all_keys(RANGE_OPT_PARAM *param, SEL if (!key1) return &null_element; // Impossible ranges key1->use_count++; + key1->max_part_no= max(key2->max_part_no, key2->part+1); return key1; } @@ -7441,6 +7460,7 @@ key_and(RANGE_OPT_PARAM *param, SEL_ARG 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) { @@ -7478,6 +7498,7 @@ key_and(RANGE_OPT_PARAM *param, SEL_ARG key2->free_tree(); if (!new_tree) return &null_element; // Impossible range + new_tree->max_part_no= max_part_no; return new_tree; } @@ -7557,6 +7578,8 @@ key_or(RANGE_OPT_PARAM *param, SEL_ARG * bool key2_shared=key2->use_count != 0; key1->maybe_flag|=key2->maybe_flag; + 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 @@ -7749,6 +7772,7 @@ end: key2=next; } key1->use_count++; + key1->max_part_no= max_part_no; return key1; }
participants (1)
-
Igor Babaev