- developers - lists.mariadb.org

[Maria-developers] Updated (by Guest): Using the Valgrind API in mysqld (23)
by worklog-noreply＠askmonty.org 20 Jun '09

20 Jun '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Using the Valgrind API in mysqld CREATION DATE..: Fri, 22 May 2009, 11:43 SUPERVISOR.....: Psergey IMPLEMENTOR....: Knielsen COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 23 (http://askmonty.org/worklog/?tid=23) VERSION........: Server-9.x STATUS.........: Complete PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 40 (hours remain) ORIG. ESTIMATE.: 40 PROGRESS NOTES: -=-=(Guest - Sat, 20 Jun 2009, 21:35)=-=- Version updated. --- /tmp/wklog.23.old.7421 2009-06-20 21:35:40.000000000 +0300 +++ /tmp/wklog.23.new.7421 2009-06-20 21:35:40.000000000 +0300 @@ -1 +1 @@ -Connector/J-3.2 +Server-9.x -=-=(Guest - Fri, 19 Jun 2009, 20:48)=-=- Version updated. --- /tmp/wklog.23.old.1520 2009-06-19 20:48:56.000000000 +0300 +++ /tmp/wklog.23.new.1520 2009-06-19 20:48:56.000000000 +0300 @@ -1 +1 @@ -GUI-Tools-3.0 +Connector/J-3.2 -=-=(Guest - Fri, 19 Jun 2009, 20:45)=-=- Version updated. --- /tmp/wklog.23.old.1480 2009-06-19 20:45:53.000000000 +0300 +++ /tmp/wklog.23.new.1480 2009-06-19 20:45:53.000000000 +0300 @@ -1 +1 @@ -Connector/.NET-2.0 +GUI-Tools-3.0 -=-=(Guest - Fri, 19 Jun 2009, 20:42)=-=- Version updated. --- /tmp/wklog.23.old.1373 2009-06-19 20:42:48.000000000 +0300 +++ /tmp/wklog.23.new.1373 2009-06-19 20:42:48.000000000 +0300 @@ -1 +1 @@ -WorkLog-3.4 +Connector/.NET-2.0 -=-=(Guest - Fri, 19 Jun 2009, 20:39)=-=- Version updated. --- /tmp/wklog.23.old.1347 2009-06-19 20:39:44.000000000 +0300 +++ /tmp/wklog.23.new.1347 2009-06-19 20:39:44.000000000 +0300 @@ -1 +1 @@ -Server-6.0 +WorkLog-3.4 -=-=(Guest - Fri, 19 Jun 2009, 20:36)=-=- Version updated. --- /tmp/wklog.23.old.1240 2009-06-19 20:36:40.000000000 +0300 +++ /tmp/wklog.23.new.1240 2009-06-19 20:36:40.000000000 +0300 @@ -1 +1 @@ -Connector/J-5.2 +Server-6.0 -=-=(Guest - Fri, 19 Jun 2009, 20:33)=-=- Version updated. --- /tmp/wklog.23.old.1136 2009-06-19 20:33:36.000000000 +0300 +++ /tmp/wklog.23.new.1136 2009-06-19 20:33:36.000000000 +0300 @@ -1 +1 @@ -Server-5.1 +Connector/J-5.2 -=-=(Guest - Fri, 19 Jun 2009, 20:30)=-=- Version updated. --- /tmp/wklog.23.old.1109 2009-06-19 20:30:32.000000000 +0300 +++ /tmp/wklog.23.new.1109 2009-06-19 20:30:32.000000000 +0300 @@ -1 +1 @@ -Maria-1.0 +Server-5.1 -=-=(Guest - Fri, 19 Jun 2009, 20:27)=-=- Version updated. --- /tmp/wklog.23.old.1004 2009-06-19 20:27:28.000000000 +0300 +++ /tmp/wklog.23.new.1004 2009-06-19 20:27:28.000000000 +0300 @@ -1 +1 @@ -Connector/J-3.1 +Maria-1.0 -=-=(Guest - Fri, 19 Jun 2009, 20:24)=-=- Version updated. --- /tmp/wklog.23.old.907 2009-06-19 20:24:24.000000000 +0300 +++ /tmp/wklog.23.new.907 2009-06-19 20:24:24.000000000 +0300 @@ -1 +1 @@ -Maria-1.1 +Connector/J-3.1 ------------------------------------------------------------ -=-=(View All Progress Notes, 173 total)=-=- http://askmonty.org/worklog/index.pl?tid=23&nolimit=1 DESCRIPTION: Valgrind (the memcheck tool) has some very useful APIs that can be used in mysqld when testing with Valgrind to improve testing and/or debugging: file:///usr/share/doc/valgrind/html/mc-manual.html#mc-manual.clientreqs file:///usr/share/doc/valgrind/html/mc-manual.html#mc-manual.mempools This worklog is about adding configure checks and headers to allow to use these in a way that continues to work on machines where the Valgrind headers or functionality is missing. It also includes adding some basic Valgrind enhancements: - Adding Valgrind annotations to custom memory allocators so that Valgrind can detect leaks, use-before-init, and use-after-free problems also for these allocators. - Adding checks for definedness in appropriate places (eg. when calling libz). HIGH-LEVEL SPECIFICATION: With custom memory allocators, using the Valgrind APIs we can tell Valgrind when a memory block is allocated (so that data read from memory is marked as undefined instead of being defined or not at random depending on prior use); and when a memory block is freed (so that use after freeing can be reported as an error). In some cases cheking for leaks may also be appropriate. Another possibility is to add an explicit check for whether memory is defined. One place this would be useful is when calling libz. Due to the design of that library, Valgrind produces lots of false alarms about using undefined values (I think the issue is that it runs a few bytes off of initialized memory to reduce boundary checks in each loop iteration, then after the loop has checks to avoid using the undefined part of the result). This means we have lots of libz Valgrind suppressions and continue to add more as new warnings surface. So we might easily miss a real problem in this area. This could be improved by adding explicit checks at the call to libz functions that the passed memory is properly defined. Another use is to improve debugging. It is often the case when debugging a warning about using un-initialised memory that the detection happens long after the real problem, the un-initialized value being passed along through the code for a long time before being detected. This makes debugging the problem slow. By adding in strategic places code that asserts that a specific value must be initialised, it is possible to detect problems earlier, speeding up debugging. Such code can be added in more places over time as development and debugging goes on. See also a patch here: http://bugs.mysql.com/bug.php?id=44582 LOW-LEVEL DESIGN: Two places where we call into libz, and where checking for defined parameters would be good: - mysys/my_compress.c - sql/item_strfunc.cc (Item_func_compress). ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Better choice between range and index_merge/intersection options (26)
by worklog-noreply＠askmonty.org 20 Jun '09

20 Jun '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Better choice between range and index_merge/intersection options CREATION DATE..: Wed, 27 May 2009, 15:20 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 26 (http://askmonty.org/worklog/?tid=26) VERSION........: Server-9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Sat, 20 Jun 2009, 09:39)=-=- High-Level Specification modified. --- /tmp/wklog.26.old.21828 2009-06-20 09:39:25.000000000 +0300 +++ /tmp/wklog.26.new.21828 2009-06-20 09:39:25.000000000 +0300 @@ -1 +1,9 @@ +* Not a spec but rather preliminary notes* +User cases +---------- + +* BUG#32254: Index merge used unnecessarily +* BUG#34869: Almost 300% regression in index merge intersect performance +* BUG#40051: needed way to prevent optimizer from using index_merge on useless +keys (no testcase) -=-=(Guest - Sat, 13 Jun 2009, 06:51)=-=- Category updated. --- /tmp/wklog.26.old.26624 2009-06-13 06:51:56.000000000 +0300 +++ /tmp/wklog.26.new.26624 2009-06-13 06:51:56.000000000 +0300 @@ -1 +1 @@ -Server-BackLog +Server-Sprint -=-=(Guest - Sat, 13 Jun 2009, 06:06)=-=- Category updated. --- /tmp/wklog.26.old.24784 2009-06-13 06:06:28.000000000 +0300 +++ /tmp/wklog.26.new.24784 2009-06-13 06:06:28.000000000 +0300 @@ -1 +1 @@ -Server-RawIdeaBin +Server-BackLog -=-=(Psergey - Wed, 03 Jun 2009, 12:09)=-=- Dependency created: 30 now depends on 26 DESCRIPTION: The optimizer does a cost-based choice between possible range and index_merge/intersection scans. There are some issues with it: - index_merge/intersection gets chosen even when there is a single multi-part index that covers all keys. Measurements show that this is a poor choice. - The picked index_merge/intersection can use a redundant set of indexes: it will be intersect(idx1, ..., idxN) where all columns in idxN are covered by other used indexes. This WL is to fix these limitations. HIGH-LEVEL SPECIFICATION: * Not a spec but rather preliminary notes* User cases ---------- * BUG#32254: Index merge used unnecessarily * BUG#34869: Almost 300% regression in index merge intersect performance * BUG#40051: needed way to prevent optimizer from using index_merge on useless keys (no testcase) ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Better choice between range and index_merge/intersection options (26)
by worklog-noreply＠askmonty.org 20 Jun '09

20 Jun '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Better choice between range and index_merge/intersection options CREATION DATE..: Wed, 27 May 2009, 15:20 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 26 (http://askmonty.org/worklog/?tid=26) VERSION........: Server-9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Sat, 20 Jun 2009, 09:39)=-=- High-Level Specification modified. --- /tmp/wklog.26.old.21828 2009-06-20 09:39:25.000000000 +0300 +++ /tmp/wklog.26.new.21828 2009-06-20 09:39:25.000000000 +0300 @@ -1 +1,9 @@ +* Not a spec but rather preliminary notes* +User cases +---------- + +* BUG#32254: Index merge used unnecessarily +* BUG#34869: Almost 300% regression in index merge intersect performance +* BUG#40051: needed way to prevent optimizer from using index_merge on useless +keys (no testcase) -=-=(Guest - Sat, 13 Jun 2009, 06:51)=-=- Category updated. --- /tmp/wklog.26.old.26624 2009-06-13 06:51:56.000000000 +0300 +++ /tmp/wklog.26.new.26624 2009-06-13 06:51:56.000000000 +0300 @@ -1 +1 @@ -Server-BackLog +Server-Sprint -=-=(Guest - Sat, 13 Jun 2009, 06:06)=-=- Category updated. --- /tmp/wklog.26.old.24784 2009-06-13 06:06:28.000000000 +0300 +++ /tmp/wklog.26.new.24784 2009-06-13 06:06:28.000000000 +0300 @@ -1 +1 @@ -Server-RawIdeaBin +Server-BackLog -=-=(Psergey - Wed, 03 Jun 2009, 12:09)=-=- Dependency created: 30 now depends on 26 DESCRIPTION: The optimizer does a cost-based choice between possible range and index_merge/intersection scans. There are some issues with it: - index_merge/intersection gets chosen even when there is a single multi-part index that covers all keys. Measurements show that this is a poor choice. - The picked index_merge/intersection can use a redundant set of indexes: it will be intersect(idx1, ..., idxN) where all columns in idxN are covered by other used indexes. This WL is to fix these limitations. HIGH-LEVEL SPECIFICATION: * Not a spec but rather preliminary notes* User cases ---------- * BUG#32254: Index merge used unnecessarily * BUG#34869: Almost 300% regression in index merge intersect performance * BUG#40051: needed way to prevent optimizer from using index_merge on useless keys (no testcase) ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): index_merge: fair choice between index_merge union and range access (24)
by worklog-noreply＠askmonty.org 20 Jun '09

20 Jun '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: index_merge: fair choice between index_merge union and range access CREATION DATE..: Tue, 26 May 2009, 12:10 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: Psergey CATEGORY.......: Server-Sprint TASK ID........: 24 (http://askmonty.org/worklog/?tid=24) VERSION........: 9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Sat, 20 Jun 2009, 09:34)=-=- Low Level Design modified. --- /tmp/wklog.24.old.21663 2009-06-20 09:34:48.000000000 +0300 +++ /tmp/wklog.24.new.21663 2009-06-20 09:34:48.000000000 +0300 @@ -4,6 +4,7 @@ 2. New implementation 2.1 New tree_and() 2.2 New tree_or() +3. Testing and required coverage </contents> 1. Current implementation overview @@ -240,3 +241,14 @@ In order to limit the impact of this combinatorial explosion, we will introduce a rule that we won't generate more than #defined MAX_IMERGE_OPTS options. + +3. Testing and required coverage +================================ +So far could find the following user cases: + +* BUG#17259: Query optimizer chooses wrong index +* BUG#17673: Optimizer does not use Index Merge optimization in some cases +* BUG#23322: Optimizer sometimes erroniously prefers other index over index merge +* BUG#30151: optimizer is very reluctant to chose index_merge algorithm + + -=-=(Guest - Thu, 18 Jun 2009, 16:55)=-=- Low Level Design modified. --- /tmp/wklog.24.old.19152 2009-06-18 16:55:00.000000000 +0300 +++ /tmp/wklog.24.new.19152 2009-06-18 16:55:00.000000000 +0300 @@ -141,13 +141,15 @@ Operations on SEL_ARG trees will be modified to produce/process the trees of this kind: + 2.1 New tree_and() ------------------ In order not to lose plans, we'll make these changes: -1. Don't remove index_merge part of the tree. +A1. Don't remove index_merge part of the tree (this will take care of + DISCARD-IMERGE-1 problem) -2. Push range conditions down into index_merge trees that may support them. +A2. Push range conditions down into index_merge trees that may support them. if one tree has range(key1) and the other tree has imerge(key1 OR key2) then perform an equvalent of this operation: @@ -155,8 +157,86 @@ (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) -3. Just as before: if both sel_tree A and sel_tree B have index_merge options, +A3. Just as before: if both sel_tree A and sel_tree B have index_merge options, concatenate them together. -2.2 New tree_or() +2.2 New tree_or() +----------------- +O1. Dont remove non-range plans: + Current tree_or() code will refuse to produce index_merge plans for + conditions like + + "t.key1part2=const OR t.key2part1=const" + + (this is marked as DISCARD-IMERGE-3). This was justifed as the left part of + the AND condition is not usable for range access, and the operation of + tree_and() guaranteed that there was no way it could changed to make a + usable range plan. With new tree_and() and rule A2, this is no longer the + case. For example for this query: + + (t.key1part2=const OR t.key2part1=const) AND t.key1part1=const + + it will construct a + + imerge(t.key1part2=const OR t.key2part1=const), range(t.key1part1=const) + + then tree_and() will apply rule A2 to push the range down into index merge + and after that we'll have: + + range(t.key1part1=const) + imerge( + t.key1part2=const AND t.key1part1=const, + t.key2part1=const + ) + note that imerge(...) describes a usable index_merge plan and it's possible + that it will be the best access path. + +O2. "Create index_merge accesses when possible" + Current tree_or() will not create index_merge access when it could create + non-index merge access (see DISCARD-IMERGE-3 and its example in the "Problems + in the current implementation" section). This will be changed to work as + follows: we will create index_merge made for index scans that didn't have + their match in the other sel_tree. + Ilustrating it with an example: + + | sel_tree_A | sel_tree_B | A or B | include in index_merge? + ------+------------+------------+--------+------------------------ + key1 | cond1 | cond2 | condM | no + key2 | cond3 | cond4 | NULL | no + key3 | cond5 | | | yes, A-side + key4 | cond6 | | | yes, A-side + key5 | | cond7 | | yes, B-side + key6 | | cond8 | | yes, B-side + + here we assume that + - (cond1 OR cond2) did produce a combined range. Not including them in + index_merge. + - (cond3 OR cond4) didn't produce a usable range (e.g. they were + t.key1part1=c1 AND t.key1part2=c1, respectively, and combining them + didn't yield any range list) + - All other scand didn't have their counterparts, so we'll end up with a + SEL_TREE of: + + range(condM) AND index_merge((cond5 AND cond6),(cond7 AND cond8)) + . + +O4. There is no O4. DISCARD-INDEX-MERGE-4 will remain there. The idea is +that although DISCARD-INDEX-MERGE-4 does discard plans, so far we haven +seen any complaints that could be attributed to it. +If we face the need to lift DISCARD-INDEX-MERGE-4, our answer will be to +lift it ,and produce a cross-product: + + ((key1p OR key2p) AND (key3p OR key4p)) + OR + ((key5p OR key6p) AND (key7p OR key8p)) + + = (key1p OR key2p OR key5p OR key6p) AND // this part is currently + (key3p OR key4p OR key5p OR key6p) AND // produced + + (key1p OR key2p OR key5p OR key6p) AND // this part will be added + (key3p OR key4p OR key5p OR key6p) //. + +In order to limit the impact of this combinatorial explosion, we will +introduce a rule that we won't generate more than #defined +MAX_IMERGE_OPTS options. -=-=(Guest - Thu, 18 Jun 2009, 14:56)=-=- Low Level Design modified. --- /tmp/wklog.24.old.15612 2009-06-18 14:56:09.000000000 +0300 +++ /tmp/wklog.24.new.15612 2009-06-18 14:56:09.000000000 +0300 @@ -1 +1,162 @@ +<contents> +1. Current implementation overview +1.1. Problems in the current implementation +2. New implementation +2.1 New tree_and() +2.2 New tree_or() +</contents> + +1. Current implementation overview +================================== +At the moment, range analyzer works as follows: + +SEL_TREE structure represents + + # There are sel_trees, a sel_tree is either range or merge tree + sel_tree = range_tree | imerge_tree + + # a range tree has range access options, possibly for several keys + range_tree = range(key1) AND range(key2) AND ... AND range(keyN); + + # merge tree represents several way to index_merge + imerge_tree = imerge1 AND imerge2 AND ... + + # a way to do index merge == a set to use of different indexes. + imergeX = range_tree1 OR range_tree2 OR .. + where no pair of range_treeX have ranges over the same index. + + + tree_and(A, B) + { + if (both A and B are range trees) + return a range_tree with computed intersection for each range; + if (only one of A and B is a range tree) + return that tree; // DISCARD-IMERGE-1 + // at this point both trees are index_merge trees + return concat_lists( A.imerge1 ... A.imergeN, B.imerge1 ... B.imergeN); + } + + + tree_or(A, B) + { + if (A and B are range trees) + { + R = new range_tree; + for each index i + R.add(range_union(A.range(i), B.range(i))); + + if (R has at least one range access) + return R; + else + { + /* could not build any range accesses. construct index_merge */ + remove non-ranges from A; // DISCARD-IMERGE-2 + remove non-ranges from B; + return new index_merge(A, B); + } + } + else if (A is range tree and B is index_merge tree (or vice versa)) + { + Perform this transformation: + + range_treeA // this is A + OR + (range_treeB_11 OR range_treeB_12 OR ... OR range_treeB_1N) AND + (range_treeB_21 OR range_treeB_22 OR ... OR range_treeB_2N) AND + ... + (range_treeB_K1 OR range_treeB_K2 OR ... OR range_treeB_kN) AND + = + (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND + (range_treeA OR range_treeB_21 OR ... OR range_treeB_2N) AND + ... + (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND + + Now each line represents an index_merge.. + } + else if (both A and B are index_merge trees) + { + Perform this transformation: + + imergeA1 AND imergeA2 AND ... AND imergeAN + OR + imergeB1 AND imergeB2 AND ... AND imergeBN + + -> (discard all imergeA{i=2,3,...} -> // DISCARD-IMERGE-3 + + imergeA1 + OR + imergeB1 AND imergeB2 AND ... AND imergeBN = + + = (combine imergeA1 with each of the imergeB{i} ) = + + combine(imergeA1 OR imergeB1) AND + combine(imergeA1 OR imergeB2) AND + ... AND + combine(imergeA1 OR imergeBN) + } + } + +1.1. Problems in the current implementation +------------------------------------------- +As marked in the code above: + +DISCARD-IMERGE-1 step will cause index_merge option to be discarded when +the WHERE clause has this form: + + (t.key1=c1 OR t.key2=c2) AND t.badkey < c3 + +DISCARD-IMERGE-2 step will cause index_merge option to be discarded when +the WHERE clause has this form (conditions t.badkey may have abritrary form): + + (t.badkey<c1 AND t.key1=c1) OR (t.key1=c2 AND t.badkey < c2) + +DISCARD-IMERGE-3 manifests itself as the following effect: suppose there are +two indexes: + + INDEX i1(col1, col2), + INDEX i2(col1, col3) + +and this WHERE clause: + + col1=c1 AND (col2=c2 OR col3=c3) + +The optimizer will generate the plans that only use the "col1=c1" part. The +right side of the AND will be ignored even if it has good selectivity. + + +2. New implementation +===================== + +<general idea> +* Don't start fighting combinatorial explosion until we've actually got one. +</> + +SEL_TREE structure will be now able to hold both index_merge and range scan +candidates at the same time. That is, + + sel_tree2 = range_tree AND imerge_tree + +where both parts are optional (i.e. can be empty) + +Operations on SEL_ARG trees will be modified to produce/process the trees of +this kind: + +2.1 New tree_and() +------------------ +In order not to lose plans, we'll make these changes: + +1. Don't remove index_merge part of the tree. + +2. Push range conditions down into index_merge trees that may support them. + if one tree has range(key1) and the other tree has imerge(key1 OR key2) + then perform an equvalent of this operation: + + rangeA(key1) AND ( rangeB(key1) OR rangeB(key2)) = + + (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) + +3. Just as before: if both sel_tree A and sel_tree B have index_merge options, + concatenate them together. + +2.2 New tree_or() -=-=(Guest - Sat, 13 Jun 2009, 06:29)=-=- Category updated. --- /tmp/wklog.24.old.25753 2009-06-13 06:29:10.000000000 +0300 +++ /tmp/wklog.24.new.25753 2009-06-13 06:29:10.000000000 +0300 @@ -1 +1 @@ -Server-BackLog +Server-Sprint -=-=(Guest - Sat, 13 Jun 2009, 06:14)=-=- Category updated. --- /tmp/wklog.24.old.24991 2009-06-13 06:14:03.000000000 +0300 +++ /tmp/wklog.24.new.24991 2009-06-13 06:14:03.000000000 +0300 @@ -1 +1 @@ -Server-RawIdeaBin +Server-BackLog -=-=(Psergey - Wed, 03 Jun 2009, 12:09)=-=- Dependency created: 30 now depends on 24 -=-=(Guest - Mon, 01 Jun 2009, 23:30)=-=- High-Level Specification modified. --- /tmp/wklog.24.old.21580 2009-06-01 23:30:06.000000000 +0300 +++ /tmp/wklog.24.new.21580 2009-06-01 23:30:06.000000000 +0300 @@ -64,6 +64,9 @@ * How strict is the limitation on the form of the WHERE? +* Which version should this be based on? 5.1? Which patches are should be in + (google's/percona's/maria/etc?) + * TODO: The optimizer didn't compare costs of index_merge and range before (ok it did but that was done for accesses to different tables). Will there be any possible gotchas here? -=-=(Guest - Wed, 27 May 2009, 14:41)=-=- Category updated. --- /tmp/wklog.24.old.8414 2009-05-27 14:41:43.000000000 +0300 +++ /tmp/wklog.24.new.8414 2009-05-27 14:41:43.000000000 +0300 @@ -1 +1 @@ -Client-BackLog +Server-RawIdeaBin -=-=(Guest - Wed, 27 May 2009, 14:41)=-=- Version updated. --- /tmp/wklog.24.old.8414 2009-05-27 14:41:43.000000000 +0300 +++ /tmp/wklog.24.new.8414 2009-05-27 14:41:43.000000000 +0300 @@ -1 +1 @@ -Server-9.x +9.x -=-=(Guest - Wed, 27 May 2009, 13:59)=-=- Title modified. --- /tmp/wklog.24.old.9498 2009-05-27 13:59:23.000000000 +0300 +++ /tmp/wklog.24.new.9498 2009-05-27 13:59:23.000000000 +0300 @@ -1 +1 @@ -index_merge optimizer: dont discard index_merge union strategies when range is available +index_merge: fair choice between index_merge union and range access ------------------------------------------------------------ -=-=(View All Progress Notes, 12 total)=-=- http://askmonty.org/worklog/index.pl?tid=24&nolimit=1 DESCRIPTION: Current range optimizer will discard possible index_merge/[sort]union strategies when there is a possible range plan. This action is a part of measures we take to avoid combinatorial explosion of possible range/ index_merge strategies. A bad side effect of this is that for WHERE clauses in form t.key1= 'very-frequent-value' AND (t.key2='rare-value1' OR t.key3='rare-value2') the optimizer will - discard union(key2,key3) in favor of range(key1) - consider costs of using range(key1) and discard that plan also and the overall effect is that possible poor range access will cause possible good index_merge access not to be considered. This WL is to about lifting this limitation at least for some subset of WHERE clauses. HIGH-LEVEL SPECIFICATION: (Not a ready HLS but draft) <contents> Solution overview Limitations TODO </contents> Solution overview ================= The idea is to delay discarding potential index_merge plans until the point where it is really necessary. This way, we won't have to do much changes in the range analyzer, but will be able to keep potential index_merge plan just enough so that it's possible to take it into consideration together with range access plans. Since there are no changes in the optimizer, the ability to consider both range and index_merge options will be limited to WHERE clauses of this form: WHERE := range_cond(key1_1) AND range_cond(key2_1) AND other_cond AND index_merge_OR_cond1(key3_1, key3_2, ...) index_merge_OR_cond2(key4_1, key4_2, ...) where index_merge_OR_cond{N} := (range_cond(keyN_1) OR range_cond(keyN_2) OR ...) range_cond(keyX) := condition that allows to construct range access of keyX and doesn't allow to construct range/index_merge accesses for any keys of the table in question. For such WHERE clauses, the range analyzer will produce SEL_TREE of this form: SEL_TREE( range(key1_1), ... range(key2_1), SEL_IMERGE( (1) SEL_TREE(key3_1}) SEL_TREE(key3_2}) ... ) ... ) which can be used to make a cost-based choice between range and index_merge. Limitations ----------- This will not be a full solution in a sense that the range analyzer will not be able to produce sel_tree (1) if the WHERE clause is specified in other form (e.g. brackets were opened). TODO ---- * is it a problem if there are keys that are referred to both from index_merge and from range access? * How strict is the limitation on the form of the WHERE? * Which version should this be based on? 5.1? Which patches are should be in (google's/percona's/maria/etc?) * TODO: The optimizer didn't compare costs of index_merge and range before (ok it did but that was done for accesses to different tables). Will there be any possible gotchas here? LOW-LEVEL DESIGN: <contents> 1. Current implementation overview 1.1. Problems in the current implementation 2. New implementation 2.1 New tree_and() 2.2 New tree_or() 3. Testing and required coverage </contents> 1. Current implementation overview ================================== At the moment, range analyzer works as follows: SEL_TREE structure represents # There are sel_trees, a sel_tree is either range or merge tree sel_tree = range_tree | imerge_tree # a range tree has range access options, possibly for several keys range_tree = range(key1) AND range(key2) AND ... AND range(keyN); # merge tree represents several way to index_merge imerge_tree = imerge1 AND imerge2 AND ... # a way to do index merge == a set to use of different indexes. imergeX = range_tree1 OR range_tree2 OR .. where no pair of range_treeX have ranges over the same index. tree_and(A, B) { if (both A and B are range trees) return a range_tree with computed intersection for each range; if (only one of A and B is a range tree) return that tree; // DISCARD-IMERGE-1 // at this point both trees are index_merge trees return concat_lists( A.imerge1 ... A.imergeN, B.imerge1 ... B.imergeN); } tree_or(A, B) { if (A and B are range trees) { R = new range_tree; for each index i R.add(range_union(A.range(i), B.range(i))); if (R has at least one range access) return R; else { /* could not build any range accesses. construct index_merge */ remove non-ranges from A; // DISCARD-IMERGE-2 remove non-ranges from B; return new index_merge(A, B); } } else if (A is range tree and B is index_merge tree (or vice versa)) { Perform this transformation: range_treeA // this is A OR (range_treeB_11 OR range_treeB_12 OR ... OR range_treeB_1N) AND (range_treeB_21 OR range_treeB_22 OR ... OR range_treeB_2N) AND ... (range_treeB_K1 OR range_treeB_K2 OR ... OR range_treeB_kN) AND = (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND (range_treeA OR range_treeB_21 OR ... OR range_treeB_2N) AND ... (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND Now each line represents an index_merge.. } else if (both A and B are index_merge trees) { Perform this transformation: imergeA1 AND imergeA2 AND ... AND imergeAN OR imergeB1 AND imergeB2 AND ... AND imergeBN -> (discard all imergeA{i=2,3,...} -> // DISCARD-IMERGE-3 imergeA1 OR imergeB1 AND imergeB2 AND ... AND imergeBN = = (combine imergeA1 with each of the imergeB{i} ) = combine(imergeA1 OR imergeB1) AND combine(imergeA1 OR imergeB2) AND ... AND combine(imergeA1 OR imergeBN) } } 1.1. Problems in the current implementation ------------------------------------------- As marked in the code above: DISCARD-IMERGE-1 step will cause index_merge option to be discarded when the WHERE clause has this form: (t.key1=c1 OR t.key2=c2) AND t.badkey < c3 DISCARD-IMERGE-2 step will cause index_merge option to be discarded when the WHERE clause has this form (conditions t.badkey may have abritrary form): (t.badkey<c1 AND t.key1=c1) OR (t.key1=c2 AND t.badkey < c2) DISCARD-IMERGE-3 manifests itself as the following effect: suppose there are two indexes: INDEX i1(col1, col2), INDEX i2(col1, col3) and this WHERE clause: col1=c1 AND (col2=c2 OR col3=c3) The optimizer will generate the plans that only use the "col1=c1" part. The right side of the AND will be ignored even if it has good selectivity. 2. New implementation ===================== <general idea> * Don't start fighting combinatorial explosion until we've actually got one. </> SEL_TREE structure will be now able to hold both index_merge and range scan candidates at the same time. That is, sel_tree2 = range_tree AND imerge_tree where both parts are optional (i.e. can be empty) Operations on SEL_ARG trees will be modified to produce/process the trees of this kind: 2.1 New tree_and() ------------------ In order not to lose plans, we'll make these changes: A1. Don't remove index_merge part of the tree (this will take care of DISCARD-IMERGE-1 problem) A2. Push range conditions down into index_merge trees that may support them. if one tree has range(key1) and the other tree has imerge(key1 OR key2) then perform an equvalent of this operation: rangeA(key1) AND ( rangeB(key1) OR rangeB(key2)) = (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) A3. Just as before: if both sel_tree A and sel_tree B have index_merge options, concatenate them together. 2.2 New tree_or() ----------------- O1. Dont remove non-range plans: Current tree_or() code will refuse to produce index_merge plans for conditions like "t.key1part2=const OR t.key2part1=const" (this is marked as DISCARD-IMERGE-3). This was justifed as the left part of the AND condition is not usable for range access, and the operation of tree_and() guaranteed that there was no way it could changed to make a usable range plan. With new tree_and() and rule A2, this is no longer the case. For example for this query: (t.key1part2=const OR t.key2part1=const) AND t.key1part1=const it will construct a imerge(t.key1part2=const OR t.key2part1=const), range(t.key1part1=const) then tree_and() will apply rule A2 to push the range down into index merge and after that we'll have: range(t.key1part1=const) imerge( t.key1part2=const AND t.key1part1=const, t.key2part1=const ) note that imerge(...) describes a usable index_merge plan and it's possible that it will be the best access path. O2. "Create index_merge accesses when possible" Current tree_or() will not create index_merge access when it could create non-index merge access (see DISCARD-IMERGE-3 and its example in the "Problems in the current implementation" section). This will be changed to work as follows: we will create index_merge made for index scans that didn't have their match in the other sel_tree. Ilustrating it with an example: | sel_tree_A | sel_tree_B | A or B | include in index_merge? ------+------------+------------+--------+------------------------ key1 | cond1 | cond2 | condM | no key2 | cond3 | cond4 | NULL | no key3 | cond5 | | | yes, A-side key4 | cond6 | | | yes, A-side key5 | | cond7 | | yes, B-side key6 | | cond8 | | yes, B-side here we assume that - (cond1 OR cond2) did produce a combined range. Not including them in index_merge. - (cond3 OR cond4) didn't produce a usable range (e.g. they were t.key1part1=c1 AND t.key1part2=c1, respectively, and combining them didn't yield any range list) - All other scand didn't have their counterparts, so we'll end up with a SEL_TREE of: range(condM) AND index_merge((cond5 AND cond6),(cond7 AND cond8)) . O4. There is no O4. DISCARD-INDEX-MERGE-4 will remain there. The idea is that although DISCARD-INDEX-MERGE-4 does discard plans, so far we haven seen any complaints that could be attributed to it. If we face the need to lift DISCARD-INDEX-MERGE-4, our answer will be to lift it ,and produce a cross-product: ((key1p OR key2p) AND (key3p OR key4p)) OR ((key5p OR key6p) AND (key7p OR key8p)) = (key1p OR key2p OR key5p OR key6p) AND // this part is currently (key3p OR key4p OR key5p OR key6p) AND // produced (key1p OR key2p OR key5p OR key6p) AND // this part will be added (key3p OR key4p OR key5p OR key6p) //. In order to limit the impact of this combinatorial explosion, we will introduce a rule that we won't generate more than #defined MAX_IMERGE_OPTS options. 3. Testing and required coverage ================================ So far could find the following user cases: * BUG#17259: Query optimizer chooses wrong index * BUG#17673: Optimizer does not use Index Merge optimization in some cases * BUG#23322: Optimizer sometimes erroniously prefers other index over index merge * BUG#30151: optimizer is very reluctant to chose index_merge algorithm ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): index_merge: fair choice between index_merge union and range access (24)
by worklog-noreply＠askmonty.org 20 Jun '09

20 Jun '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: index_merge: fair choice between index_merge union and range access CREATION DATE..: Tue, 26 May 2009, 12:10 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: Psergey CATEGORY.......: Server-Sprint TASK ID........: 24 (http://askmonty.org/worklog/?tid=24) VERSION........: 9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Sat, 20 Jun 2009, 09:34)=-=- Low Level Design modified. --- /tmp/wklog.24.old.21663 2009-06-20 09:34:48.000000000 +0300 +++ /tmp/wklog.24.new.21663 2009-06-20 09:34:48.000000000 +0300 @@ -4,6 +4,7 @@ 2. New implementation 2.1 New tree_and() 2.2 New tree_or() +3. Testing and required coverage </contents> 1. Current implementation overview @@ -240,3 +241,14 @@ In order to limit the impact of this combinatorial explosion, we will introduce a rule that we won't generate more than #defined MAX_IMERGE_OPTS options. + +3. Testing and required coverage +================================ +So far could find the following user cases: + +* BUG#17259: Query optimizer chooses wrong index +* BUG#17673: Optimizer does not use Index Merge optimization in some cases +* BUG#23322: Optimizer sometimes erroniously prefers other index over index merge +* BUG#30151: optimizer is very reluctant to chose index_merge algorithm + + -=-=(Guest - Thu, 18 Jun 2009, 16:55)=-=- Low Level Design modified. --- /tmp/wklog.24.old.19152 2009-06-18 16:55:00.000000000 +0300 +++ /tmp/wklog.24.new.19152 2009-06-18 16:55:00.000000000 +0300 @@ -141,13 +141,15 @@ Operations on SEL_ARG trees will be modified to produce/process the trees of this kind: + 2.1 New tree_and() ------------------ In order not to lose plans, we'll make these changes: -1. Don't remove index_merge part of the tree. +A1. Don't remove index_merge part of the tree (this will take care of + DISCARD-IMERGE-1 problem) -2. Push range conditions down into index_merge trees that may support them. +A2. Push range conditions down into index_merge trees that may support them. if one tree has range(key1) and the other tree has imerge(key1 OR key2) then perform an equvalent of this operation: @@ -155,8 +157,86 @@ (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) -3. Just as before: if both sel_tree A and sel_tree B have index_merge options, +A3. Just as before: if both sel_tree A and sel_tree B have index_merge options, concatenate them together. -2.2 New tree_or() +2.2 New tree_or() +----------------- +O1. Dont remove non-range plans: + Current tree_or() code will refuse to produce index_merge plans for + conditions like + + "t.key1part2=const OR t.key2part1=const" + + (this is marked as DISCARD-IMERGE-3). This was justifed as the left part of + the AND condition is not usable for range access, and the operation of + tree_and() guaranteed that there was no way it could changed to make a + usable range plan. With new tree_and() and rule A2, this is no longer the + case. For example for this query: + + (t.key1part2=const OR t.key2part1=const) AND t.key1part1=const + + it will construct a + + imerge(t.key1part2=const OR t.key2part1=const), range(t.key1part1=const) + + then tree_and() will apply rule A2 to push the range down into index merge + and after that we'll have: + + range(t.key1part1=const) + imerge( + t.key1part2=const AND t.key1part1=const, + t.key2part1=const + ) + note that imerge(...) describes a usable index_merge plan and it's possible + that it will be the best access path. + +O2. "Create index_merge accesses when possible" + Current tree_or() will not create index_merge access when it could create + non-index merge access (see DISCARD-IMERGE-3 and its example in the "Problems + in the current implementation" section). This will be changed to work as + follows: we will create index_merge made for index scans that didn't have + their match in the other sel_tree. + Ilustrating it with an example: + + | sel_tree_A | sel_tree_B | A or B | include in index_merge? + ------+------------+------------+--------+------------------------ + key1 | cond1 | cond2 | condM | no + key2 | cond3 | cond4 | NULL | no + key3 | cond5 | | | yes, A-side + key4 | cond6 | | | yes, A-side + key5 | | cond7 | | yes, B-side + key6 | | cond8 | | yes, B-side + + here we assume that + - (cond1 OR cond2) did produce a combined range. Not including them in + index_merge. + - (cond3 OR cond4) didn't produce a usable range (e.g. they were + t.key1part1=c1 AND t.key1part2=c1, respectively, and combining them + didn't yield any range list) + - All other scand didn't have their counterparts, so we'll end up with a + SEL_TREE of: + + range(condM) AND index_merge((cond5 AND cond6),(cond7 AND cond8)) + . + +O4. There is no O4. DISCARD-INDEX-MERGE-4 will remain there. The idea is +that although DISCARD-INDEX-MERGE-4 does discard plans, so far we haven +seen any complaints that could be attributed to it. +If we face the need to lift DISCARD-INDEX-MERGE-4, our answer will be to +lift it ,and produce a cross-product: + + ((key1p OR key2p) AND (key3p OR key4p)) + OR + ((key5p OR key6p) AND (key7p OR key8p)) + + = (key1p OR key2p OR key5p OR key6p) AND // this part is currently + (key3p OR key4p OR key5p OR key6p) AND // produced + + (key1p OR key2p OR key5p OR key6p) AND // this part will be added + (key3p OR key4p OR key5p OR key6p) //. + +In order to limit the impact of this combinatorial explosion, we will +introduce a rule that we won't generate more than #defined +MAX_IMERGE_OPTS options. -=-=(Guest - Thu, 18 Jun 2009, 14:56)=-=- Low Level Design modified. --- /tmp/wklog.24.old.15612 2009-06-18 14:56:09.000000000 +0300 +++ /tmp/wklog.24.new.15612 2009-06-18 14:56:09.000000000 +0300 @@ -1 +1,162 @@ +<contents> +1. Current implementation overview +1.1. Problems in the current implementation +2. New implementation +2.1 New tree_and() +2.2 New tree_or() +</contents> + +1. Current implementation overview +================================== +At the moment, range analyzer works as follows: + +SEL_TREE structure represents + + # There are sel_trees, a sel_tree is either range or merge tree + sel_tree = range_tree | imerge_tree + + # a range tree has range access options, possibly for several keys + range_tree = range(key1) AND range(key2) AND ... AND range(keyN); + + # merge tree represents several way to index_merge + imerge_tree = imerge1 AND imerge2 AND ... + + # a way to do index merge == a set to use of different indexes. + imergeX = range_tree1 OR range_tree2 OR .. + where no pair of range_treeX have ranges over the same index. + + + tree_and(A, B) + { + if (both A and B are range trees) + return a range_tree with computed intersection for each range; + if (only one of A and B is a range tree) + return that tree; // DISCARD-IMERGE-1 + // at this point both trees are index_merge trees + return concat_lists( A.imerge1 ... A.imergeN, B.imerge1 ... B.imergeN); + } + + + tree_or(A, B) + { + if (A and B are range trees) + { + R = new range_tree; + for each index i + R.add(range_union(A.range(i), B.range(i))); + + if (R has at least one range access) + return R; + else + { + /* could not build any range accesses. construct index_merge */ + remove non-ranges from A; // DISCARD-IMERGE-2 + remove non-ranges from B; + return new index_merge(A, B); + } + } + else if (A is range tree and B is index_merge tree (or vice versa)) + { + Perform this transformation: + + range_treeA // this is A + OR + (range_treeB_11 OR range_treeB_12 OR ... OR range_treeB_1N) AND + (range_treeB_21 OR range_treeB_22 OR ... OR range_treeB_2N) AND + ... + (range_treeB_K1 OR range_treeB_K2 OR ... OR range_treeB_kN) AND + = + (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND + (range_treeA OR range_treeB_21 OR ... OR range_treeB_2N) AND + ... + (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND + + Now each line represents an index_merge.. + } + else if (both A and B are index_merge trees) + { + Perform this transformation: + + imergeA1 AND imergeA2 AND ... AND imergeAN + OR + imergeB1 AND imergeB2 AND ... AND imergeBN + + -> (discard all imergeA{i=2,3,...} -> // DISCARD-IMERGE-3 + + imergeA1 + OR + imergeB1 AND imergeB2 AND ... AND imergeBN = + + = (combine imergeA1 with each of the imergeB{i} ) = + + combine(imergeA1 OR imergeB1) AND + combine(imergeA1 OR imergeB2) AND + ... AND + combine(imergeA1 OR imergeBN) + } + } + +1.1. Problems in the current implementation +------------------------------------------- +As marked in the code above: + +DISCARD-IMERGE-1 step will cause index_merge option to be discarded when +the WHERE clause has this form: + + (t.key1=c1 OR t.key2=c2) AND t.badkey < c3 + +DISCARD-IMERGE-2 step will cause index_merge option to be discarded when +the WHERE clause has this form (conditions t.badkey may have abritrary form): + + (t.badkey<c1 AND t.key1=c1) OR (t.key1=c2 AND t.badkey < c2) + +DISCARD-IMERGE-3 manifests itself as the following effect: suppose there are +two indexes: + + INDEX i1(col1, col2), + INDEX i2(col1, col3) + +and this WHERE clause: + + col1=c1 AND (col2=c2 OR col3=c3) + +The optimizer will generate the plans that only use the "col1=c1" part. The +right side of the AND will be ignored even if it has good selectivity. + + +2. New implementation +===================== + +<general idea> +* Don't start fighting combinatorial explosion until we've actually got one. +</> + +SEL_TREE structure will be now able to hold both index_merge and range scan +candidates at the same time. That is, + + sel_tree2 = range_tree AND imerge_tree + +where both parts are optional (i.e. can be empty) + +Operations on SEL_ARG trees will be modified to produce/process the trees of +this kind: + +2.1 New tree_and() +------------------ +In order not to lose plans, we'll make these changes: + +1. Don't remove index_merge part of the tree. + +2. Push range conditions down into index_merge trees that may support them. + if one tree has range(key1) and the other tree has imerge(key1 OR key2) + then perform an equvalent of this operation: + + rangeA(key1) AND ( rangeB(key1) OR rangeB(key2)) = + + (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) + +3. Just as before: if both sel_tree A and sel_tree B have index_merge options, + concatenate them together. + +2.2 New tree_or() -=-=(Guest - Sat, 13 Jun 2009, 06:29)=-=- Category updated. --- /tmp/wklog.24.old.25753 2009-06-13 06:29:10.000000000 +0300 +++ /tmp/wklog.24.new.25753 2009-06-13 06:29:10.000000000 +0300 @@ -1 +1 @@ -Server-BackLog +Server-Sprint -=-=(Guest - Sat, 13 Jun 2009, 06:14)=-=- Category updated. --- /tmp/wklog.24.old.24991 2009-06-13 06:14:03.000000000 +0300 +++ /tmp/wklog.24.new.24991 2009-06-13 06:14:03.000000000 +0300 @@ -1 +1 @@ -Server-RawIdeaBin +Server-BackLog -=-=(Psergey - Wed, 03 Jun 2009, 12:09)=-=- Dependency created: 30 now depends on 24 -=-=(Guest - Mon, 01 Jun 2009, 23:30)=-=- High-Level Specification modified. --- /tmp/wklog.24.old.21580 2009-06-01 23:30:06.000000000 +0300 +++ /tmp/wklog.24.new.21580 2009-06-01 23:30:06.000000000 +0300 @@ -64,6 +64,9 @@ * How strict is the limitation on the form of the WHERE? +* Which version should this be based on? 5.1? Which patches are should be in + (google's/percona's/maria/etc?) + * TODO: The optimizer didn't compare costs of index_merge and range before (ok it did but that was done for accesses to different tables). Will there be any possible gotchas here? -=-=(Guest - Wed, 27 May 2009, 14:41)=-=- Category updated. --- /tmp/wklog.24.old.8414 2009-05-27 14:41:43.000000000 +0300 +++ /tmp/wklog.24.new.8414 2009-05-27 14:41:43.000000000 +0300 @@ -1 +1 @@ -Client-BackLog +Server-RawIdeaBin -=-=(Guest - Wed, 27 May 2009, 14:41)=-=- Version updated. --- /tmp/wklog.24.old.8414 2009-05-27 14:41:43.000000000 +0300 +++ /tmp/wklog.24.new.8414 2009-05-27 14:41:43.000000000 +0300 @@ -1 +1 @@ -Server-9.x +9.x -=-=(Guest - Wed, 27 May 2009, 13:59)=-=- Title modified. --- /tmp/wklog.24.old.9498 2009-05-27 13:59:23.000000000 +0300 +++ /tmp/wklog.24.new.9498 2009-05-27 13:59:23.000000000 +0300 @@ -1 +1 @@ -index_merge optimizer: dont discard index_merge union strategies when range is available +index_merge: fair choice between index_merge union and range access ------------------------------------------------------------ -=-=(View All Progress Notes, 12 total)=-=- http://askmonty.org/worklog/index.pl?tid=24&nolimit=1 DESCRIPTION: Current range optimizer will discard possible index_merge/[sort]union strategies when there is a possible range plan. This action is a part of measures we take to avoid combinatorial explosion of possible range/ index_merge strategies. A bad side effect of this is that for WHERE clauses in form t.key1= 'very-frequent-value' AND (t.key2='rare-value1' OR t.key3='rare-value2') the optimizer will - discard union(key2,key3) in favor of range(key1) - consider costs of using range(key1) and discard that plan also and the overall effect is that possible poor range access will cause possible good index_merge access not to be considered. This WL is to about lifting this limitation at least for some subset of WHERE clauses. HIGH-LEVEL SPECIFICATION: (Not a ready HLS but draft) <contents> Solution overview Limitations TODO </contents> Solution overview ================= The idea is to delay discarding potential index_merge plans until the point where it is really necessary. This way, we won't have to do much changes in the range analyzer, but will be able to keep potential index_merge plan just enough so that it's possible to take it into consideration together with range access plans. Since there are no changes in the optimizer, the ability to consider both range and index_merge options will be limited to WHERE clauses of this form: WHERE := range_cond(key1_1) AND range_cond(key2_1) AND other_cond AND index_merge_OR_cond1(key3_1, key3_2, ...) index_merge_OR_cond2(key4_1, key4_2, ...) where index_merge_OR_cond{N} := (range_cond(keyN_1) OR range_cond(keyN_2) OR ...) range_cond(keyX) := condition that allows to construct range access of keyX and doesn't allow to construct range/index_merge accesses for any keys of the table in question. For such WHERE clauses, the range analyzer will produce SEL_TREE of this form: SEL_TREE( range(key1_1), ... range(key2_1), SEL_IMERGE( (1) SEL_TREE(key3_1}) SEL_TREE(key3_2}) ... ) ... ) which can be used to make a cost-based choice between range and index_merge. Limitations ----------- This will not be a full solution in a sense that the range analyzer will not be able to produce sel_tree (1) if the WHERE clause is specified in other form (e.g. brackets were opened). TODO ---- * is it a problem if there are keys that are referred to both from index_merge and from range access? * How strict is the limitation on the form of the WHERE? * Which version should this be based on? 5.1? Which patches are should be in (google's/percona's/maria/etc?) * TODO: The optimizer didn't compare costs of index_merge and range before (ok it did but that was done for accesses to different tables). Will there be any possible gotchas here? LOW-LEVEL DESIGN: <contents> 1. Current implementation overview 1.1. Problems in the current implementation 2. New implementation 2.1 New tree_and() 2.2 New tree_or() 3. Testing and required coverage </contents> 1. Current implementation overview ================================== At the moment, range analyzer works as follows: SEL_TREE structure represents # There are sel_trees, a sel_tree is either range or merge tree sel_tree = range_tree | imerge_tree # a range tree has range access options, possibly for several keys range_tree = range(key1) AND range(key2) AND ... AND range(keyN); # merge tree represents several way to index_merge imerge_tree = imerge1 AND imerge2 AND ... # a way to do index merge == a set to use of different indexes. imergeX = range_tree1 OR range_tree2 OR .. where no pair of range_treeX have ranges over the same index. tree_and(A, B) { if (both A and B are range trees) return a range_tree with computed intersection for each range; if (only one of A and B is a range tree) return that tree; // DISCARD-IMERGE-1 // at this point both trees are index_merge trees return concat_lists( A.imerge1 ... A.imergeN, B.imerge1 ... B.imergeN); } tree_or(A, B) { if (A and B are range trees) { R = new range_tree; for each index i R.add(range_union(A.range(i), B.range(i))); if (R has at least one range access) return R; else { /* could not build any range accesses. construct index_merge */ remove non-ranges from A; // DISCARD-IMERGE-2 remove non-ranges from B; return new index_merge(A, B); } } else if (A is range tree and B is index_merge tree (or vice versa)) { Perform this transformation: range_treeA // this is A OR (range_treeB_11 OR range_treeB_12 OR ... OR range_treeB_1N) AND (range_treeB_21 OR range_treeB_22 OR ... OR range_treeB_2N) AND ... (range_treeB_K1 OR range_treeB_K2 OR ... OR range_treeB_kN) AND = (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND (range_treeA OR range_treeB_21 OR ... OR range_treeB_2N) AND ... (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND Now each line represents an index_merge.. } else if (both A and B are index_merge trees) { Perform this transformation: imergeA1 AND imergeA2 AND ... AND imergeAN OR imergeB1 AND imergeB2 AND ... AND imergeBN -> (discard all imergeA{i=2,3,...} -> // DISCARD-IMERGE-3 imergeA1 OR imergeB1 AND imergeB2 AND ... AND imergeBN = = (combine imergeA1 with each of the imergeB{i} ) = combine(imergeA1 OR imergeB1) AND combine(imergeA1 OR imergeB2) AND ... AND combine(imergeA1 OR imergeBN) } } 1.1. Problems in the current implementation ------------------------------------------- As marked in the code above: DISCARD-IMERGE-1 step will cause index_merge option to be discarded when the WHERE clause has this form: (t.key1=c1 OR t.key2=c2) AND t.badkey < c3 DISCARD-IMERGE-2 step will cause index_merge option to be discarded when the WHERE clause has this form (conditions t.badkey may have abritrary form): (t.badkey<c1 AND t.key1=c1) OR (t.key1=c2 AND t.badkey < c2) DISCARD-IMERGE-3 manifests itself as the following effect: suppose there are two indexes: INDEX i1(col1, col2), INDEX i2(col1, col3) and this WHERE clause: col1=c1 AND (col2=c2 OR col3=c3) The optimizer will generate the plans that only use the "col1=c1" part. The right side of the AND will be ignored even if it has good selectivity. 2. New implementation ===================== <general idea> * Don't start fighting combinatorial explosion until we've actually got one. </> SEL_TREE structure will be now able to hold both index_merge and range scan candidates at the same time. That is, sel_tree2 = range_tree AND imerge_tree where both parts are optional (i.e. can be empty) Operations on SEL_ARG trees will be modified to produce/process the trees of this kind: 2.1 New tree_and() ------------------ In order not to lose plans, we'll make these changes: A1. Don't remove index_merge part of the tree (this will take care of DISCARD-IMERGE-1 problem) A2. Push range conditions down into index_merge trees that may support them. if one tree has range(key1) and the other tree has imerge(key1 OR key2) then perform an equvalent of this operation: rangeA(key1) AND ( rangeB(key1) OR rangeB(key2)) = (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) A3. Just as before: if both sel_tree A and sel_tree B have index_merge options, concatenate them together. 2.2 New tree_or() ----------------- O1. Dont remove non-range plans: Current tree_or() code will refuse to produce index_merge plans for conditions like "t.key1part2=const OR t.key2part1=const" (this is marked as DISCARD-IMERGE-3). This was justifed as the left part of the AND condition is not usable for range access, and the operation of tree_and() guaranteed that there was no way it could changed to make a usable range plan. With new tree_and() and rule A2, this is no longer the case. For example for this query: (t.key1part2=const OR t.key2part1=const) AND t.key1part1=const it will construct a imerge(t.key1part2=const OR t.key2part1=const), range(t.key1part1=const) then tree_and() will apply rule A2 to push the range down into index merge and after that we'll have: range(t.key1part1=const) imerge( t.key1part2=const AND t.key1part1=const, t.key2part1=const ) note that imerge(...) describes a usable index_merge plan and it's possible that it will be the best access path. O2. "Create index_merge accesses when possible" Current tree_or() will not create index_merge access when it could create non-index merge access (see DISCARD-IMERGE-3 and its example in the "Problems in the current implementation" section). This will be changed to work as follows: we will create index_merge made for index scans that didn't have their match in the other sel_tree. Ilustrating it with an example: | sel_tree_A | sel_tree_B | A or B | include in index_merge? ------+------------+------------+--------+------------------------ key1 | cond1 | cond2 | condM | no key2 | cond3 | cond4 | NULL | no key3 | cond5 | | | yes, A-side key4 | cond6 | | | yes, A-side key5 | | cond7 | | yes, B-side key6 | | cond8 | | yes, B-side here we assume that - (cond1 OR cond2) did produce a combined range. Not including them in index_merge. - (cond3 OR cond4) didn't produce a usable range (e.g. they were t.key1part1=c1 AND t.key1part2=c1, respectively, and combining them didn't yield any range list) - All other scand didn't have their counterparts, so we'll end up with a SEL_TREE of: range(condM) AND index_merge((cond5 AND cond6),(cond7 AND cond8)) . O4. There is no O4. DISCARD-INDEX-MERGE-4 will remain there. The idea is that although DISCARD-INDEX-MERGE-4 does discard plans, so far we haven seen any complaints that could be attributed to it. If we face the need to lift DISCARD-INDEX-MERGE-4, our answer will be to lift it ,and produce a cross-product: ((key1p OR key2p) AND (key3p OR key4p)) OR ((key5p OR key6p) AND (key7p OR key8p)) = (key1p OR key2p OR key5p OR key6p) AND // this part is currently (key3p OR key4p OR key5p OR key6p) AND // produced (key1p OR key2p OR key5p OR key6p) AND // this part will be added (key3p OR key4p OR key5p OR key6p) //. In order to limit the impact of this combinatorial explosion, we will introduce a rule that we won't generate more than #defined MAX_IMERGE_OPTS options. 3. Testing and required coverage ================================ So far could find the following user cases: * BUG#17259: Query optimizer chooses wrong index * BUG#17673: Optimizer does not use Index Merge optimization in some cases * BUG#23322: Optimizer sometimes erroniously prefers other index over index merge * BUG#30151: optimizer is very reluctant to chose index_merge algorithm ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (knielsen:2702)
by knielsen＠knielsen-hq.org 19 Jun '09

19 Jun '09

#At lp:maria 2702 knielsen(a)knielsen-hq.org 2009-06-09 XtraDB after-merge fixes. Fixes to get the test suite to run without failures. removed: storage/xtradb/setup.sh modified: mysql-test/r/information_schema.result mysql-test/r/information_schema_all_engines.result mysql-test/r/innodb-autoinc.result mysql-test/r/innodb-index.result mysql-test/r/innodb-zip.result mysql-test/r/innodb.result mysql-test/r/innodb_bug36169.result mysql-test/r/innodb_xtradb_bug317074.result mysql-test/r/row-checksum-old.result mysql-test/r/row-checksum.result mysql-test/t/information_schema.test mysql-test/t/innodb-analyze.test mysql-test/t/innodb-autoinc.test mysql-test/t/innodb-index.test mysql-test/t/innodb-zip.test mysql-test/t/innodb.test mysql-test/t/innodb_bug34300.test mysql-test/t/innodb_bug36169.test mysql-test/t/innodb_bug36172.test mysql-test/t/innodb_xtradb_bug317074.test mysql-test/t/partition_innodb.test mysys/thr_mutex.c storage/xtradb/ibuf/ibuf0ibuf.c storage/xtradb/include/sync0rw.h storage/xtradb/include/sync0rw.ic storage/xtradb/include/univ.i storage/xtradb/srv/srv0start.c per-file messages: mysql-test/r/information_schema.result Additional variables available now. Sort output to avoid depending on engine order. mysql-test/r/information_schema_all_engines.result More variables now. mysql-test/r/innodb-autoinc.result Avoid picking up pbxt variables in result mysql-test/r/innodb-index.result Save state to not corrupt following testcases. Suppress an expected warning. mysql-test/r/innodb-zip.result Work around a problem with dependency on zlib version mysql-test/r/innodb.result Checksums have changed in Maria. Save and restore server state to not corrupt following testcases. mysql-test/r/innodb_bug36169.result Save and restore server state to not corrupt following testcases. mysql-test/r/innodb_xtradb_bug317074.result Save and restore server state to not corrupt following testcases. mysql-test/r/row-checksum-old.result Update result file mysql-test/r/row-checksum.result Update result file mysql-test/t/information_schema.test Sort output to avoid depending on engine order. mysql-test/t/innodb-analyze.test Save and restore server state to not corrupt following testcases. mysql-test/t/innodb-autoinc.test Save and restore server state to not corrupt following testcases. mysql-test/t/innodb-index.test Save state to not corrupt following testcases. Suppress an expected warning. mysql-test/t/innodb-zip.test Work around a problem with dependency on zlib version mysql-test/t/innodb.test Save and restore server state to not corrupt following testcases. Update --replace statements for new mysql-test-run mysql-test/t/innodb_bug34300.test Save and restore server state to not corrupt following testcases. mysql-test/t/innodb_bug36169.test Save and restore server state to not corrupt following testcases. mysql-test/t/innodb_bug36172.test Save and restore server state to not corrupt following testcases. mysql-test/t/innodb_xtradb_bug317074.test Save and restore server state to not corrupt following testcases. mysql-test/t/partition_innodb.test Fix regexps to work with new SHOW INNODB STATUS output. mysys/thr_mutex.c Initialize mutex deadlock detection lazily. This allows to test XtraDB, which initializes huge amounts of mutexes without using any but a few of them. storage/xtradb/ibuf/ibuf0ibuf.c Fix problem where value of INNODB_IBUF_MAX_SIZE would depend on the alignment of memory allocated by the buffer pool. storage/xtradb/include/sync0rw.h Fix XtraDB to compile without GCC atomic operation intrinsics (performance may suffer when they are not available though). storage/xtradb/include/sync0rw.ic Fix XtraDB to compile without GCC atomic operation intrinsics (performance may suffer when they are not available though). storage/xtradb/include/univ.i Fix for MariaDB storage/xtradb/setup.sh Remove no longer needed file from XtraDB. storage/xtradb/srv/srv0start.c Fix for MariaDB === modified file 'mysql-test/r/information_schema.result' --- a/mysql-test/r/information_schema.result 2009-04-08 16:55:26 +0000 +++ b/mysql-test/r/information_schema.result 2009-06-09 15:08:46 +0000 @@ -42,7 +42,7 @@ WHERE table_schema IN ('mysql', 'INFORMA table_name<>'ndb_binlog_index' AND table_name<>'ndb_apply_status' AND NOT (table_schema = 'INFORMATION_SCHEMA' AND table_name LIKE 'PBXT_%'); -select * from v1; +select * from v1 ORDER BY c COLLATE utf8_bin; c CHARACTER_SETS COLLATIONS @@ -54,6 +54,17 @@ EVENTS FILES GLOBAL_STATUS GLOBAL_VARIABLES +INNODB_BUFFER_POOL_PAGES +INNODB_BUFFER_POOL_PAGES_BLOB +INNODB_BUFFER_POOL_PAGES_INDEX +INNODB_CMP +INNODB_CMPMEM +INNODB_CMPMEM_RESET +INNODB_CMP_RESET +INNODB_LOCKS +INNODB_LOCK_WAITS +INNODB_RSEG +INNODB_TRX KEY_COLUMN_USAGE PARTITIONS PLUGINS @@ -72,6 +83,7 @@ TABLE_PRIVILEGES TRIGGERS USER_PRIVILEGES VIEWS +XTRADB_ENHANCEMENTS columns_priv db event @@ -87,6 +99,11 @@ proc procs_priv servers slow_log +t1 +t2 +t3 +t4 +t5 tables_priv time_zone time_zone_leap_second @@ -94,11 +111,6 @@ time_zone_name time_zone_transition time_zone_transition_type user -t1 -t4 -t2 -t3 -t5 v1 select c,table_name from v1 inner join information_schema.TABLES v2 on (v1.c=v2.table_name) @@ -800,6 +812,8 @@ TABLES CREATE_TIME datetime TABLES UPDATE_TIME datetime TABLES CHECK_TIME datetime TRIGGERS CREATED datetime +INNODB_TRX trx_started datetime +INNODB_TRX trx_wait_started datetime event execute_at datetime event last_executed datetime event starts datetime @@ -848,6 +862,7 @@ TABLES TABLE_NAME select TABLE_CONSTRAINTS TABLE_NAME select TABLE_PRIVILEGES TABLE_NAME select VIEWS TABLE_NAME select +INNODB_BUFFER_POOL_PAGES_INDEX table_name select delete from mysql.user where user='mysqltest_4'; delete from mysql.db where user='mysqltest_4'; flush privileges; @@ -1223,12 +1238,12 @@ DROP PROCEDURE p1; DROP USER mysql_bug20230@localhost; SELECT MAX(table_name) FROM information_schema.tables WHERE table_schema IN ('mysql', 'INFORMATION_SCHEMA', 'test'); MAX(table_name) -VIEWS +XTRADB_ENHANCEMENTS SELECT table_name from information_schema.tables WHERE table_name=(SELECT MAX(table_name) FROM information_schema.tables WHERE table_schema IN ('mysql', 'INFORMATION_SCHEMA', 'test')); table_name -VIEWS +XTRADB_ENHANCEMENTS DROP TABLE IF EXISTS bug23037; DROP FUNCTION IF EXISTS get_value; SELECT COLUMN_NAME, MD5(COLUMN_DEFAULT), LENGTH(COLUMN_DEFAULT) FROM INFORMATION_SCHEMA.COLUMNS WHERE TABLE_NAME='bug23037'; === modified file 'mysql-test/r/information_schema_all_engines.result' --- a/mysql-test/r/information_schema_all_engines.result 2009-04-08 16:55:26 +0000 +++ b/mysql-test/r/information_schema_all_engines.result 2009-06-09 15:08:46 +0000 @@ -29,6 +29,18 @@ TABLE_PRIVILEGES TRIGGERS USER_PRIVILEGES VIEWS +INNODB_BUFFER_POOL_PAGES_INDEX +INNODB_RSEG +INNODB_LOCKS +INNODB_BUFFER_POOL_PAGES +XTRADB_ENHANCEMENTS +INNODB_TRX +INNODB_BUFFER_POOL_PAGES_BLOB +INNODB_LOCK_WAITS +INNODB_CMP_RESET +INNODB_CMP +INNODB_CMPMEM_RESET +INNODB_CMPMEM PBXT_STATISTICS SELECT t.table_name, c1.column_name FROM information_schema.tables t @@ -73,6 +85,18 @@ TABLE_PRIVILEGES TABLE_SCHEMA TRIGGERS TRIGGER_SCHEMA USER_PRIVILEGES GRANTEE VIEWS TABLE_SCHEMA +INNODB_BUFFER_POOL_PAGES_INDEX schema_name +INNODB_RSEG rseg_id +INNODB_LOCKS lock_id +INNODB_BUFFER_POOL_PAGES page_type +XTRADB_ENHANCEMENTS name +INNODB_TRX trx_id +INNODB_BUFFER_POOL_PAGES_BLOB space_id +INNODB_LOCK_WAITS requesting_trx_id +INNODB_CMP_RESET page_size +INNODB_CMP page_size +INNODB_CMPMEM_RESET page_size +INNODB_CMPMEM page_size PBXT_STATISTICS ID SELECT t.table_name, c1.column_name FROM information_schema.tables t @@ -117,6 +141,18 @@ TABLE_PRIVILEGES TABLE_SCHEMA TRIGGERS TRIGGER_SCHEMA USER_PRIVILEGES GRANTEE VIEWS TABLE_SCHEMA +INNODB_BUFFER_POOL_PAGES_INDEX schema_name +INNODB_RSEG rseg_id +INNODB_LOCKS lock_id +INNODB_BUFFER_POOL_PAGES page_type +XTRADB_ENHANCEMENTS name +INNODB_TRX trx_id +INNODB_BUFFER_POOL_PAGES_BLOB space_id +INNODB_LOCK_WAITS requesting_trx_id +INNODB_CMP_RESET page_size +INNODB_CMP page_size +INNODB_CMPMEM_RESET page_size +INNODB_CMPMEM page_size PBXT_STATISTICS ID select 1 as f1 from information_schema.tables where "CHARACTER_SETS"= (select cast(table_name as char) from information_schema.tables @@ -149,6 +185,17 @@ EVENTS information_schema.EVENTS 1 FILES information_schema.FILES 1 GLOBAL_STATUS information_schema.GLOBAL_STATUS 1 GLOBAL_VARIABLES information_schema.GLOBAL_VARIABLES 1 +INNODB_BUFFER_POOL_PAGES information_schema.INNODB_BUFFER_POOL_PAGES 1 +INNODB_BUFFER_POOL_PAGES_BLOB information_schema.INNODB_BUFFER_POOL_PAGES_BLOB 1 +INNODB_BUFFER_POOL_PAGES_INDEX information_schema.INNODB_BUFFER_POOL_PAGES_INDEX 1 +INNODB_CMP information_schema.INNODB_CMP 1 +INNODB_CMPMEM information_schema.INNODB_CMPMEM 1 +INNODB_CMPMEM_RESET information_schema.INNODB_CMPMEM_RESET 1 +INNODB_CMP_RESET information_schema.INNODB_CMP_RESET 1 +INNODB_LOCKS information_schema.INNODB_LOCKS 1 +INNODB_LOCK_WAITS information_schema.INNODB_LOCK_WAITS 1 +INNODB_RSEG information_schema.INNODB_RSEG 1 +INNODB_TRX information_schema.INNODB_TRX 1 KEY_COLUMN_USAGE information_schema.KEY_COLUMN_USAGE 1 PARTITIONS information_schema.PARTITIONS 1 PBXT_STATISTICS information_schema.PBXT_STATISTICS 1 @@ -168,6 +215,7 @@ TABLE_PRIVILEGES information_schema.TABL TRIGGERS information_schema.TRIGGERS 1 USER_PRIVILEGES information_schema.USER_PRIVILEGES 1 VIEWS information_schema.VIEWS 1 +XTRADB_ENHANCEMENTS information_schema.XTRADB_ENHANCEMENTS 1 Database: information_schema +---------------------------------------+ | Tables | @@ -200,6 +248,18 @@ Database: information_schema | TRIGGERS | | USER_PRIVILEGES | | VIEWS | +| INNODB_BUFFER_POOL_PAGES_INDEX | +| INNODB_RSEG | +| INNODB_LOCKS | +| INNODB_BUFFER_POOL_PAGES | +| XTRADB_ENHANCEMENTS | +| INNODB_TRX | +| INNODB_BUFFER_POOL_PAGES_BLOB | +| INNODB_LOCK_WAITS | +| INNODB_CMP_RESET | +| INNODB_CMP | +| INNODB_CMPMEM_RESET | +| INNODB_CMPMEM | | PBXT_STATISTICS | +---------------------------------------+ Database: INFORMATION_SCHEMA @@ -234,6 +294,18 @@ Database: INFORMATION_SCHEMA | TRIGGERS | | USER_PRIVILEGES | | VIEWS | +| INNODB_BUFFER_POOL_PAGES_INDEX | +| INNODB_RSEG | +| INNODB_LOCKS | +| INNODB_BUFFER_POOL_PAGES | +| XTRADB_ENHANCEMENTS | +| INNODB_TRX | +| INNODB_BUFFER_POOL_PAGES_BLOB | +| INNODB_LOCK_WAITS | +| INNODB_CMP_RESET | +| INNODB_CMP | +| INNODB_CMPMEM_RESET | +| INNODB_CMPMEM | | PBXT_STATISTICS | +---------------------------------------+ Wildcard: inf_rmation_schema @@ -244,5 +316,5 @@ Wildcard: inf_rmation_schema +--------------------+ SELECT table_schema, count(*) FROM information_schema.TABLES WHERE table_schema IN ('mysql', 'INFORMATION_SCHEMA', 'test', 'mysqltest') AND table_name<>'ndb_binlog_index' AND table_name<>'ndb_apply_status' GROUP BY TABLE_SCHEMA; table_schema count(*) -information_schema 29 +information_schema 41 mysql 22 === modified file 'mysql-test/r/innodb-autoinc.result' --- a/mysql-test/r/innodb-autoinc.result 2009-06-09 13:19:13 +0000 +++ b/mysql-test/r/innodb-autoinc.result 2009-06-09 15:08:46 +0000 @@ -197,7 +197,7 @@ c1 c2 5 9 DROP TABLE t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=100, @@SESSION.AUTO_INCREMENT_OFFSET=10; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 100 auto_increment_offset 10 @@ -230,7 +230,7 @@ c1 DROP TABLE t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 1 auto_increment_offset 1 @@ -269,7 +269,7 @@ c1 DROP TABLE t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 1 auto_increment_offset 1 @@ -282,7 +282,7 @@ SELECT * FROM t1; c1 -1 SET @@SESSION.AUTO_INCREMENT_INCREMENT=100, @@SESSION.AUTO_INCREMENT_OFFSET=10; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 100 auto_increment_offset 10 @@ -315,7 +315,7 @@ c1 DROP TABLE t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 1 auto_increment_offset 1 @@ -330,7 +330,7 @@ SELECT * FROM t1; c1 1 SET @@SESSION.AUTO_INCREMENT_INCREMENT=100, @@SESSION.AUTO_INCREMENT_OFFSET=10; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 100 auto_increment_offset 10 @@ -370,7 +370,7 @@ c1 DROP TABLE t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 1 auto_increment_offset 1 @@ -385,7 +385,7 @@ SELECT * FROM t1; c1 1 SET @@SESSION.AUTO_INCREMENT_INCREMENT=100, @@SESSION.AUTO_INCREMENT_OFFSET=10; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 100 auto_increment_offset 10 @@ -419,7 +419,7 @@ c1 DROP TABLE t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 1 auto_increment_offset 1 @@ -434,7 +434,7 @@ c1 1 9223372036854775794 SET @@SESSION.AUTO_INCREMENT_INCREMENT=2, @@SESSION.AUTO_INCREMENT_OFFSET=10; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 2 auto_increment_offset 10 @@ -452,7 +452,7 @@ c1 DROP TABLE t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 1 auto_increment_offset 1 @@ -467,7 +467,7 @@ c1 1 18446744073709551603 SET @@SESSION.AUTO_INCREMENT_INCREMENT=2, @@SESSION.AUTO_INCREMENT_OFFSET=10; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 2 auto_increment_offset 10 @@ -485,7 +485,7 @@ c1 DROP TABLE t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 1 auto_increment_offset 1 @@ -500,7 +500,7 @@ c1 1 18446744073709551603 SET @@SESSION.AUTO_INCREMENT_INCREMENT=5, @@SESSION.AUTO_INCREMENT_OFFSET=7; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 5 auto_increment_offset 7 @@ -514,7 +514,7 @@ c1 DROP TABLE t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 1 auto_increment_offset 1 @@ -533,7 +533,7 @@ c1 -9223372036854775806 1 SET @@SESSION.AUTO_INCREMENT_INCREMENT=3, @@SESSION.AUTO_INCREMENT_OFFSET=3; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 3 auto_increment_offset 3 @@ -550,7 +550,7 @@ c1 DROP TABLE t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 1 auto_increment_offset 1 @@ -568,7 +568,7 @@ SET @@SESSION.AUTO_INCREMENT_INCREMENT=1 Warnings: Warning 1292 Truncated incorrect auto_increment_increment value: '1152921504606846976' Warning 1292 Truncated incorrect auto_increment_offset value: '1152921504606846976' -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 65535 auto_increment_offset 65535 @@ -581,7 +581,7 @@ c1 DROP TABLE t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; Variable_name Value auto_increment_increment 1 auto_increment_offset 1 === modified file 'mysql-test/r/innodb-index.result' --- a/mysql-test/r/innodb-index.result 2009-06-09 13:19:13 +0000 +++ b/mysql-test/r/innodb-index.result 2009-06-09 15:08:46 +0000 @@ -1,3 +1,4 @@ +SET @save_innodb_file_format_check=@@global.innodb_file_format_check; create table t1(a int not null, b int, c char(10) not null, d varchar(20)) engine = innodb; insert into t1 values (5,5,'oo','oo'),(4,4,'tr','tr'),(3,4,'ad','ad'),(2,3,'ak','ak'); commit; @@ -47,6 +48,7 @@ t1 CREATE TABLE `t1` ( KEY `b` (`b`) ) ENGINE=InnoDB DEFAULT CHARSET=latin1 CREATE TABLE `t1#1`(a INT PRIMARY KEY) ENGINE=InnoDB; +call mtr.add_suppression(" table `test`\\.`t1#[12]` already exists in InnoDB internal"); alter table t1 add unique index (c), add index (d); ERROR HY000: Table 'test.t1#1' already exists rename table `t1#1` to `t1#2`; @@ -1132,3 +1134,4 @@ t2 CREATE TABLE `t2` ( ) ENGINE=InnoDB DEFAULT CHARSET=latin1 DROP TABLE t2; DROP TABLE t1; +SET GLOBAL innodb_file_format_check=@save_innodb_file_format_check; === modified file 'mysql-test/r/innodb-zip.result' --- a/mysql-test/r/innodb-zip.result 2009-06-09 13:19:13 +0000 +++ b/mysql-test/r/innodb-zip.result 2009-06-09 15:08:46 +0000 @@ -141,7 +141,7 @@ drop table t1; CREATE TABLE t1(c TEXT, PRIMARY KEY (c(440))) ENGINE=InnoDB ROW_FORMAT=COMPRESSED KEY_BLOCK_SIZE=1 CHARSET=ASCII; ERROR 42000: Row size too large. The maximum row size for the used table type, not counting BLOBs, is 8126. You have to change some columns to TEXT or BLOBs -CREATE TABLE t1(c TEXT, PRIMARY KEY (c(439))) +CREATE TABLE t1(c TEXT, PRIMARY KEY (c(438))) ENGINE=InnoDB ROW_FORMAT=COMPRESSED KEY_BLOCK_SIZE=1 CHARSET=ASCII; INSERT INTO t1 VALUES(REPEAT('A',512)),(REPEAT('B',512)); DROP TABLE t1; === modified file 'mysql-test/r/innodb.result' --- a/mysql-test/r/innodb.result 2009-06-09 13:19:13 +0000 +++ b/mysql-test/r/innodb.result 2009-06-09 15:08:46 +0000 @@ -1433,7 +1433,7 @@ insert t2 select * from t1; insert t3 select * from t1; checksum table t1, t2, t3, t4 quick; Table Checksum -test.t1 2948697075 +test.t1 3442722830 test.t2 NULL test.t3 NULL test.t4 NULL @@ -1441,17 +1441,17 @@ Warnings: Error 1146 Table 'test.t4' doesn't exist checksum table t1, t2, t3, t4; Table Checksum -test.t1 2948697075 -test.t2 2948697075 -test.t3 2948697075 +test.t1 3442722830 +test.t2 3442722830 +test.t3 3442722830 test.t4 NULL Warnings: Error 1146 Table 'test.t4' doesn't exist checksum table t1, t2, t3, t4 extended; Table Checksum -test.t1 2948697075 -test.t2 2948697075 -test.t3 2948697075 +test.t1 3442722830 +test.t2 3442722830 +test.t3 3442722830 test.t4 NULL Warnings: Error 1146 Table 'test.t4' doesn't exist @@ -1781,6 +1781,7 @@ set global innodb_sync_spin_loops=20; show variables like "innodb_sync_spin_loops"; Variable_name Value innodb_sync_spin_loops 20 +SET @old_innodb_thread_concurrency= @@global.innodb_thread_concurrency; show variables like "innodb_thread_concurrency"; Variable_name Value innodb_thread_concurrency 0 @@ -1798,6 +1799,7 @@ set global innodb_thread_concurrency=16; show variables like "innodb_thread_concurrency"; Variable_name Value innodb_thread_concurrency 16 +SET @@global.innodb_thread_concurrency= @old_innodb_thread_concurrency; show variables like "innodb_concurrency_tickets"; Variable_name Value innodb_concurrency_tickets 500 === modified file 'mysql-test/r/innodb_bug36169.result' --- a/mysql-test/r/innodb_bug36169.result 2009-06-09 13:19:13 +0000 +++ b/mysql-test/r/innodb_bug36169.result 2009-06-09 15:08:46 +0000 @@ -1,2 +1,5 @@ +SET @save_innodb_file_format=@@global.innodb_file_format; +SET @save_innodb_file_format_check=@@global.innodb_file_format_check; +SET @save_innodb_file_per_table=@@global.innodb_file_per_table; SET GLOBAL innodb_file_format='Barracuda'; SET GLOBAL innodb_file_per_table=ON; === modified file 'mysql-test/r/innodb_xtradb_bug317074.result' --- a/mysql-test/r/innodb_xtradb_bug317074.result 2009-06-09 13:19:13 +0000 +++ b/mysql-test/r/innodb_xtradb_bug317074.result 2009-06-09 15:08:46 +0000 @@ -1,2 +1,5 @@ +SET @save_innodb_file_format=@@global.innodb_file_format; +SET @save_innodb_file_format_check=@@global.innodb_file_format_check; +SET @save_innodb_file_per_table=@@global.innodb_file_per_table; SET GLOBAL innodb_file_format='Barracuda'; SET GLOBAL innodb_file_per_table=ON; === modified file 'mysql-test/r/row-checksum-old.result' --- a/mysql-test/r/row-checksum-old.result 2008-06-28 12:45:15 +0000 +++ b/mysql-test/r/row-checksum-old.result 2009-06-09 15:08:46 +0000 @@ -72,6 +72,8 @@ Table Checksum test.t1 4108368782 drop table if exists t1; create table t1 (a int null, v varchar(100)) engine=innodb checksum=0 row_format=fixed; +Warnings: +Warning 1478 InnoDB: assuming ROW_FORMAT=COMPACT. insert into t1 values(null, null), (1, "hello"); checksum table t1; Table Checksum === modified file 'mysql-test/r/row-checksum.result' --- a/mysql-test/r/row-checksum.result 2008-06-28 12:45:15 +0000 +++ b/mysql-test/r/row-checksum.result 2009-06-09 15:08:46 +0000 @@ -72,6 +72,8 @@ Table Checksum test.t1 3885665021 drop table if exists t1; create table t1 (a int null, v varchar(100)) engine=innodb checksum=0 row_format=fixed; +Warnings: +Warning 1478 InnoDB: assuming ROW_FORMAT=COMPACT. insert into t1 values(null, null), (1, "hello"); checksum table t1; Table Checksum === modified file 'mysql-test/t/information_schema.test' --- a/mysql-test/t/information_schema.test 2009-04-08 16:55:26 +0000 +++ b/mysql-test/t/information_schema.test 2009-06-09 15:08:46 +0000 @@ -43,7 +43,7 @@ create view v1 (c) as table_name<>'ndb_binlog_index' AND table_name<>'ndb_apply_status' AND NOT (table_schema = 'INFORMATION_SCHEMA' AND table_name LIKE 'PBXT_%'); -select * from v1; +select * from v1 ORDER BY c COLLATE utf8_bin; select c,table_name from v1 inner join information_schema.TABLES v2 on (v1.c=v2.table_name) === modified file 'mysql-test/t/innodb-analyze.test' --- a/mysql-test/t/innodb-analyze.test 2009-06-09 13:19:13 +0000 +++ b/mysql-test/t/innodb-analyze.test 2009-06-09 15:08:46 +0000 @@ -11,6 +11,7 @@ -- disable_result_log -- enable_warnings +SET @save_innodb_stats_sample_pages=@@innodb_stats_sample_pages; SET GLOBAL innodb_stats_sample_pages=0; # check that the value has been adjusted to 1 @@ -60,4 +61,5 @@ ANALYZE TABLE innodb_analyze; SET GLOBAL innodb_stats_sample_pages=16; ANALYZE TABLE innodb_analyze; +SET GLOBAL innodb_stats_sample_pages=@save_innodb_stats_sample_pages; DROP TABLE innodb_analyze; === modified file 'mysql-test/t/innodb-autoinc.test' --- a/mysql-test/t/innodb-autoinc.test 2009-06-09 13:19:13 +0000 +++ b/mysql-test/t/innodb-autoinc.test 2009-06-09 15:08:46 +0000 @@ -156,7 +156,7 @@ DROP TABLE t1; # # Test changes to AUTOINC next value calculation SET @@SESSION.AUTO_INCREMENT_INCREMENT=100, @@SESSION.AUTO_INCREMENT_OFFSET=10; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; DROP TABLE IF EXISTS t1; CREATE TABLE t1 (c1 INT AUTO_INCREMENT, PRIMARY KEY(c1)) ENGINE=InnoDB; INSERT INTO t1 VALUES (NULL),(5),(NULL); @@ -173,7 +173,7 @@ DROP TABLE t1; # Reset the AUTOINC session variables SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; DROP TABLE IF EXISTS t1; CREATE TABLE t1 (c1 INT AUTO_INCREMENT, PRIMARY KEY(c1)) ENGINE=InnoDB; INSERT INTO t1 VALUES(0); @@ -193,13 +193,13 @@ DROP TABLE t1; # Reset the AUTOINC session variables SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; DROP TABLE IF EXISTS t1; CREATE TABLE t1 (c1 INT AUTO_INCREMENT, PRIMARY KEY(c1)) ENGINE=InnoDB; INSERT INTO t1 VALUES(-1); SELECT * FROM t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=100, @@SESSION.AUTO_INCREMENT_OFFSET=10; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; INSERT INTO t1 VALUES (-2), (NULL),(2),(NULL); INSERT INTO t1 VALUES (250),(NULL); SELECT * FROM t1; @@ -214,13 +214,13 @@ DROP TABLE t1; # Reset the AUTOINC session variables SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; DROP TABLE IF EXISTS t1; CREATE TABLE t1 (c1 INT UNSIGNED AUTO_INCREMENT, PRIMARY KEY(c1)) ENGINE=InnoDB; INSERT INTO t1 VALUES(-1); SELECT * FROM t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=100, @@SESSION.AUTO_INCREMENT_OFFSET=10; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; INSERT INTO t1 VALUES (-2); INSERT INTO t1 VALUES (NULL); INSERT INTO t1 VALUES (2); @@ -240,13 +240,13 @@ DROP TABLE t1; # Reset the AUTOINC session variables SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; DROP TABLE IF EXISTS t1; CREATE TABLE t1 (c1 INT UNSIGNED AUTO_INCREMENT, PRIMARY KEY(c1)) ENGINE=InnoDB; INSERT INTO t1 VALUES(-1); SELECT * FROM t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=100, @@SESSION.AUTO_INCREMENT_OFFSET=10; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; INSERT INTO t1 VALUES (-2),(NULL),(2),(NULL); INSERT INTO t1 VALUES (250),(NULL); SELECT * FROM t1; @@ -262,7 +262,7 @@ DROP TABLE t1; # Check for overflow handling when increment is > 1 SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; DROP TABLE IF EXISTS t1; CREATE TABLE t1 (c1 BIGINT AUTO_INCREMENT, PRIMARY KEY(c1)) ENGINE=InnoDB; # TODO: Fix the autoinc init code @@ -271,7 +271,7 @@ INSERT INTO t1 VALUES(NULL); INSERT INTO t1 VALUES (9223372036854775794); #-- 2^63 - 14 SELECT * FROM t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=2, @@SESSION.AUTO_INCREMENT_OFFSET=10; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; # This should just fit INSERT INTO t1 VALUES (NULL),(NULL),(NULL),(NULL),(NULL),(NULL); SELECT * FROM t1; @@ -281,7 +281,7 @@ DROP TABLE t1; # Check for overflow handling when increment and offser are > 1 SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; DROP TABLE IF EXISTS t1; CREATE TABLE t1 (c1 BIGINT UNSIGNED AUTO_INCREMENT, PRIMARY KEY(c1)) ENGINE=InnoDB; # TODO: Fix the autoinc init code @@ -290,7 +290,7 @@ INSERT INTO t1 VALUES(NULL); INSERT INTO t1 VALUES (18446744073709551603); #-- 2^64 - 13 SELECT * FROM t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=2, @@SESSION.AUTO_INCREMENT_OFFSET=10; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; # This should fail because of overflow but it doesn't, it seems to be # a MySQL server bug. It wraps around to 0 for the last value. # See MySQL Bug# 39828 @@ -313,7 +313,7 @@ DROP TABLE t1; # Check for overflow handling when increment and offset are odd numbers SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; DROP TABLE IF EXISTS t1; CREATE TABLE t1 (c1 BIGINT UNSIGNED AUTO_INCREMENT, PRIMARY KEY(c1)) ENGINE=InnoDB; # TODO: Fix the autoinc init code @@ -322,7 +322,7 @@ INSERT INTO t1 VALUES(NULL); INSERT INTO t1 VALUES (18446744073709551603); #-- 2^64 - 13 SELECT * FROM t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=5, @@SESSION.AUTO_INCREMENT_OFFSET=7; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; # This should fail because of overflow but it doesn't. It fails with # a duplicate entry message because of a MySQL server bug, it wraps # around. See MySQL Bug# 39828, once MySQL fix the bug we can replace @@ -344,7 +344,7 @@ DROP TABLE t1; # and check for large -ve numbers SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; DROP TABLE IF EXISTS t1; CREATE TABLE t1 (c1 BIGINT AUTO_INCREMENT, PRIMARY KEY(c1)) ENGINE=InnoDB; # TODO: Fix the autoinc init code @@ -355,7 +355,7 @@ INSERT INTO t1 VALUES(-92233720368547758 INSERT INTO t1 VALUES(-9223372036854775808); #-- -2^63 SELECT * FROM t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=3, @@SESSION.AUTO_INCREMENT_OFFSET=3; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; INSERT INTO t1 VALUES (NULL),(NULL), (NULL); SELECT * FROM t1; DROP TABLE t1; @@ -364,7 +364,7 @@ DROP TABLE t1; # large numbers 2^60 SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; DROP TABLE IF EXISTS t1; CREATE TABLE t1 (c1 BIGINT UNSIGNED AUTO_INCREMENT, PRIMARY KEY(c1)) ENGINE=InnoDB; # TODO: Fix the autoinc init code @@ -373,7 +373,7 @@ INSERT INTO t1 VALUES(NULL); INSERT INTO t1 VALUES (18446744073709551610); #-- 2^64 - 2 SELECT * FROM t1; SET @@SESSION.AUTO_INCREMENT_INCREMENT=1152921504606846976, @@SESSION.AUTO_INCREMENT_OFFSET=1152921504606846976; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; # This should fail because of overflow but it doesn't. It wraps around # and the autoinc values look bogus too. # See MySQL Bug# 39828, once MySQL fix the bug we can enable the error @@ -396,7 +396,7 @@ DROP TABLE t1; # SET @@SESSION.AUTO_INCREMENT_INCREMENT=1, @@SESSION.AUTO_INCREMENT_OFFSET=1; SET @@INSERT_ID=1; -SHOW VARIABLES LIKE "%auto_inc%"; +SHOW VARIABLES LIKE "auto_inc%"; CREATE TABLE t1 (c1 DOUBLE NOT NULL AUTO_INCREMENT, c2 INT, PRIMARY KEY (c1)) ENGINE=InnoDB; INSERT INTO t1 VALUES(NULL, 1); INSERT INTO t1 VALUES(NULL, 2); === modified file 'mysql-test/t/innodb-index.test' --- a/mysql-test/t/innodb-index.test 2009-06-09 13:19:13 +0000 +++ b/mysql-test/t/innodb-index.test 2009-06-09 15:08:46 +0000 @@ -1,5 +1,7 @@ -- source include/have_innodb.inc +SET @save_innodb_file_format_check=@@global.innodb_file_format_check; + create table t1(a int not null, b int, c char(10) not null, d varchar(20)) engine = innodb; insert into t1 values (5,5,'oo','oo'),(4,4,'tr','tr'),(3,4,'ad','ad'),(2,3,'ak','ak'); commit; @@ -20,6 +22,8 @@ show create table t1; # Check how existing tables interfere with temporary tables. CREATE TABLE `t1#1`(a INT PRIMARY KEY) ENGINE=InnoDB; +call mtr.add_suppression(" table `test`\\.`t1#[12]` already exists in InnoDB internal"); + --error 156 alter table t1 add unique index (c), add index (d); rename table `t1#1` to `t1#2`; @@ -509,3 +513,4 @@ SHOW CREATE TABLE t2; DROP TABLE t2; DROP TABLE t1; +SET GLOBAL innodb_file_format_check=@save_innodb_file_format_check; === modified file 'mysql-test/t/innodb-zip.test' --- a/mysql-test/t/innodb-zip.test 2009-06-09 13:19:13 +0000 +++ b/mysql-test/t/innodb-zip.test 2009-06-09 15:08:46 +0000 @@ -105,7 +105,11 @@ drop table t1; --error ER_TOO_BIG_ROWSIZE CREATE TABLE t1(c TEXT, PRIMARY KEY (c(440))) ENGINE=InnoDB ROW_FORMAT=COMPRESSED KEY_BLOCK_SIZE=1 CHARSET=ASCII; -CREATE TABLE t1(c TEXT, PRIMARY KEY (c(439))) +# The maximum key size for a compressed row actually depends on the +# version of libz used, as account must be taken for the maximum +# compressed size of a key, and this differs between libz +# versions. Some libz versions allow a size of 439, some only 438. +CREATE TABLE t1(c TEXT, PRIMARY KEY (c(438))) ENGINE=InnoDB ROW_FORMAT=COMPRESSED KEY_BLOCK_SIZE=1 CHARSET=ASCII; INSERT INTO t1 VALUES(REPEAT('A',512)),(REPEAT('B',512)); DROP TABLE t1; === modified file 'mysql-test/t/innodb.test' --- a/mysql-test/t/innodb.test 2009-06-09 13:19:13 +0000 +++ b/mysql-test/t/innodb.test 2009-06-09 15:08:46 +0000 @@ -1163,7 +1163,7 @@ drop table t2; # Test error handling # Embedded server doesn't chdir to data directory ---replace_result $MYSQLTEST_VARDIR . master-data/ '' +--replace_result $MYSQLTEST_VARDIR . mysqld.1/data/ '' --error ER_WRONG_FK_DEF create table t2 (id int(11) not null, id2 int(11) not null, constraint t1_id_fk foreign key (id2,id) references t1 (id)) engine = innodb; @@ -1318,6 +1318,7 @@ set global innodb_sync_spin_loops=20; show variables like "innodb_sync_spin_loops"; # Test for innodb_thread_concurrency variable +SET @old_innodb_thread_concurrency= @@global.innodb_thread_concurrency; show variables like "innodb_thread_concurrency"; set global innodb_thread_concurrency=1001; show variables like "innodb_thread_concurrency"; @@ -1325,6 +1326,7 @@ set global innodb_thread_concurrency=0; show variables like "innodb_thread_concurrency"; set global innodb_thread_concurrency=16; show variables like "innodb_thread_concurrency"; +SET @@global.innodb_thread_concurrency= @old_innodb_thread_concurrency; # Test for innodb_concurrency_tickets variable show variables like "innodb_concurrency_tickets"; @@ -1357,7 +1359,7 @@ source include/varchar.inc; # # Embedded server doesn't chdir to data directory ---replace_result $MYSQLTEST_VARDIR . master-data/ '' +--replace_result $MYSQLTEST_VARDIR . mysqld.1/data/ '' create table t1 (v varchar(65530), key(v)); drop table t1; create table t1 (v varchar(65536)); @@ -1632,7 +1634,7 @@ disconnect b; set foreign_key_checks=0; create table t2 (a int primary key, b int, foreign key (b) references t1(a)) engine = innodb; # Embedded server doesn't chdir to data directory ---replace_result $MYSQLTEST_VARDIR . master-data/ '' +--replace_result $MYSQLTEST_VARDIR . mysqld.1/data/ '' -- error 1005 create table t1(a char(10) primary key, b varchar(20)) engine = innodb; set foreign_key_checks=1; @@ -1644,7 +1646,7 @@ drop table t2; set foreign_key_checks=0; create table t1(a varchar(10) primary key) engine = innodb DEFAULT CHARSET=latin1; # Embedded server doesn't chdir to data directory ---replace_result $MYSQLTEST_VARDIR . master-data/ '' +--replace_result $MYSQLTEST_VARDIR . mysqld.1/data/ '' -- error 1005 create table t2 (a varchar(10), foreign key (a) references t1(a)) engine = innodb DEFAULT CHARSET=utf8; set foreign_key_checks=1; @@ -1675,7 +1677,7 @@ set foreign_key_checks=0; create table t2 (a varchar(10), foreign key (a) references t1(a)) engine = innodb DEFAULT CHARSET=latin1; create table t3(a varchar(10) primary key) engine = innodb DEFAULT CHARSET=utf8; # Embedded server doesn't chdir to data directory ---replace_result $MYSQLTEST_VARDIR . master-data/ '' +--replace_result $MYSQLTEST_VARDIR . mysqld.1/data/ '' -- error 1025 rename table t3 to t1; set foreign_key_checks=1; @@ -2315,7 +2317,7 @@ ALTER TABLE t2 ADD FOREIGN KEY (a) REFER # mysqltest first does replace_regex, then replace_result --replace_regex /'[^']*test\/#sql-[0-9a-f_]*'/'#sql-temporary'/ # Embedded server doesn't chdir to data directory ---replace_result $MYSQLTEST_VARDIR . master-data/ '' +--replace_result $MYSQLTEST_VARDIR . mysqld.1/data/ '' --error 1025 ALTER TABLE t2 MODIFY a INT NOT NULL; DELETE FROM t1; === modified file 'mysql-test/t/innodb_bug34300.test' --- a/mysql-test/t/innodb_bug34300.test 2009-06-09 13:19:13 +0000 +++ b/mysql-test/t/innodb_bug34300.test 2009-06-09 15:08:46 +0000 @@ -9,6 +9,7 @@ -- disable_result_log # set packet size and reconnect +SET @save_max_allowed_packet=@@global.max_allowed_packet; SET @@global.max_allowed_packet=16777216; --connect (newconn, localhost, root,,) @@ -30,3 +31,6 @@ ALTER TABLE bug34300 ADD COLUMN (f10 INT SELECT f4, f8 FROM bug34300; DROP TABLE bug34300; +disconnect newconn; +connection default; +SET @@global.max_allowed_packet=@save_max_allowed_packet; === modified file 'mysql-test/t/innodb_bug36169.test' --- a/mysql-test/t/innodb_bug36169.test 2009-06-09 13:19:13 +0000 +++ b/mysql-test/t/innodb_bug36169.test 2009-06-09 15:08:46 +0000 @@ -5,6 +5,9 @@ -- source include/have_innodb.inc +SET @save_innodb_file_format=@@global.innodb_file_format; +SET @save_innodb_file_format_check=@@global.innodb_file_format_check; +SET @save_innodb_file_per_table=@@global.innodb_file_per_table; SET GLOBAL innodb_file_format='Barracuda'; SET GLOBAL innodb_file_per_table=ON; @@ -1145,6 +1148,10 @@ KEY `idx44` (`col176`(100),`col42`,`col7 KEY `idx45` (`col2`(27),`col27`(116)) )engine=innodb ROW_FORMAT=COMPRESSED KEY_BLOCK_SIZE=1; +SET GLOBAL innodb_file_format=@save_innodb_file_format; +SET GLOBAL innodb_file_format_check=@save_innodb_file_format_check; +SET GLOBAL innodb_file_per_table=@save_innodb_file_per_table; + DROP TABLE IF EXISTS table0; DROP TABLE IF EXISTS table1; DROP TABLE IF EXISTS table2; === modified file 'mysql-test/t/innodb_bug36172.test' --- a/mysql-test/t/innodb_bug36172.test 2009-06-09 13:19:13 +0000 +++ b/mysql-test/t/innodb_bug36172.test 2009-06-09 15:08:46 +0000 @@ -14,6 +14,9 @@ SET storage_engine=InnoDB; -- disable_query_log -- disable_result_log +SET @save_innodb_file_format=@@global.innodb_file_format; +SET @save_innodb_file_format_check=@@global.innodb_file_format_check; +SET @save_innodb_file_per_table=@@global.innodb_file_per_table; SET GLOBAL innodb_file_format='Barracuda'; SET GLOBAL innodb_file_per_table=on; @@ -23,4 +26,8 @@ insert ignore into `table0` set `col23` CHECK TABLE table0 EXTENDED; INSERT IGNORE INTO `table0` SET `col19` = '19940127002709', `col20` = 2383927.9055146948, `col21` = 4293243420.5621204000, `col22` = '20511211123705', `col23` = 4289899778.6573381000, `col24` = 4293449279.0540481000, `col25` = 'emphysemic', `col26` = 'dentally', `col27` = '2347406', `col28` = 'eruct', `col30` = 1222, `col31` = 4294372994.9941406000, `col32` = 4291385574.1173744000, `col33` = 'borrowing\'s', `col34` = 'septics', `col35` = 'ratter\'s', `col36` = 'Kaye', `col37` = 'Florentia', `col38` = 'allium', `col39` = 'barkeep', `col40` = '19510407003441', `col41` = 4293559200.4215522000, `col42` = 22482, `col43` = 'decussate', `col44` = 'Brom\'s', `col45` = 'violated', `col46` = 4925506.4635456400, `col47` = 930549, `col48` = '51296066', `col49` = 'voluminously', `col50` = '29306676', `col51` = -88, `col52` = -2153690, `col53` = 4290250202.1464887000, `col54` = 'expropriation', `col55` = 'Aberdeen\'s', `col56` = 20343, `col58` = '19640415171532', `col59` = 'extern', `col60` = 'Ubana', `col61` = 4290487961.8539081000, `col62` = '2147', `col63` = -24271, `col64` = '20750801194548', `col65` = 'Cunaxa\'s', `col66` = 'pasticcio', `col67` = 2795817, `col68` = 'Indore\'s', `col70` = 6864127, `col71` = '1817832', `col72` = '20540506114211', `col73` = '20040101012300', `col74` = 'rationalized', `col75` = '45522', `col76` = 'indene', `col77` = -6964559, `col78` = 4247535.5266884370, `col79` = '20720416124357', `col80` = '2143', `col81` = 4292060102.4466386000, `col82` = 'striving', `col83` = 'boneblack\'s', `col84` = 'redolent', `col85` = 6489697.9009369183, `col86` = 4287473465.9731131000, `col87` = 7726015, `col88` = 'perplexed', `col89` = '17153791', `col90` = 5478587.1108127078, `col91` = 4287091404.7004304000, `col92` = 'Boulez\'s', `col93` = '2931278'; CHECK TABLE table0 EXTENDED; + +SET GLOBAL innodb_file_format=@save_innodb_file_format; +SET GLOBAL innodb_file_format_check=@save_innodb_file_format_check; +SET GLOBAL innodb_file_per_table=@save_innodb_file_per_table; DROP TABLE table0; === modified file 'mysql-test/t/innodb_xtradb_bug317074.test' --- a/mysql-test/t/innodb_xtradb_bug317074.test 2009-06-09 13:19:13 +0000 +++ b/mysql-test/t/innodb_xtradb_bug317074.test 2009-06-09 15:08:46 +0000 @@ -1,5 +1,8 @@ -- source include/have_innodb.inc +SET @save_innodb_file_format=@@global.innodb_file_format; +SET @save_innodb_file_format_check=@@global.innodb_file_format_check; +SET @save_innodb_file_per_table=@@global.innodb_file_per_table; SET GLOBAL innodb_file_format='Barracuda'; SET GLOBAL innodb_file_per_table=ON; @@ -35,4 +38,8 @@ DROP PROCEDURE insert_many; # The bug is hangup at the following statement ALTER TABLE test1 ENGINE=MyISAM; +SET GLOBAL innodb_file_format=@save_innodb_file_format; +SET GLOBAL innodb_file_format_check=@save_innodb_file_format_check; +SET GLOBAL innodb_file_per_table=@save_innodb_file_per_table; + DROP TABLE test1; === modified file 'mysql-test/t/partition_innodb.test' --- a/mysql-test/t/partition_innodb.test 2009-06-09 13:19:13 +0000 +++ b/mysql-test/t/partition_innodb.test 2009-06-09 15:08:46 +0000 @@ -27,14 +27,14 @@ UPDATE t1 SET DATA = data*2 WHERE id = 3 # grouping/referencing in replace_regex is very slow on long strings, # removing all before/after the interesting row before grouping/referencing ---replace_regex /.*---TRANSACTION [0-9A-F]+, .*, OS thread id [0-9]+// /MySQL thread id [0-9]+, query id [0-9]+ .*// /.*([0-9]+ lock struct$s$), heap size [0-9]+, ([0-9]+ row lock$s$).*/\1 \2/ +--replace_regex /.*LIST OF TRANSACTIONS FOR EACH SESSION:// /MySQL thread id [0-9]+, query id [0-9]+ .*// /.*([0-9]+ lock struct$s$), heap size [0-9]+, ([0-9]+ row lock$s$).*/\1 \2/ SHOW ENGINE InnoDB STATUS; UPDATE t1 SET data = data*2 WHERE data = 2; # grouping/referencing in replace_regex is very slow on long strings, # removing all before/after the interesting row before grouping/referencing ---replace_regex /.*---TRANSACTION [0-9A-F]+, .*, OS thread id [0-9]+// /MySQL thread id [0-9]+, query id [0-9]+ .*// /.*([0-9]+ lock struct$s$), heap size [0-9]+, ([0-9]+ row lock$s$).*/\1 \2/ +--replace_regex /.*LIST OF TRANSACTIONS FOR EACH SESSION:// /MySQL thread id [0-9]+, query id [0-9]+ .*// /.*([0-9]+ lock struct$s$), heap size [0-9]+, ([0-9]+ row lock$s$).*/\1 \2/ SHOW ENGINE InnoDB STATUS; SET @@session.tx_isolation = @old_tx_isolation; === modified file 'mysys/thr_mutex.c' --- a/mysys/thr_mutex.c 2009-02-19 09:01:25 +0000 +++ b/mysys/thr_mutex.c 2009-06-09 15:08:46 +0000 @@ -149,6 +149,35 @@ static inline void remove_from_active_li mp->prev= mp->next= 0; } +/* + We initialise the hashes for deadlock detection lazily. + This greatly helps with performance when lots of mutexes are initiased but + only a few of them are actually used (eg. XtraDB). +*/ +static int safe_mutex_lazy_init_deadlock_detection(safe_mutex_t *mp) +{ + if (!my_multi_malloc(MY_FAE | MY_WME, + &mp->locked_mutex, sizeof(*mp->locked_mutex), + &mp->used_mutex, sizeof(*mp->used_mutex), NullS)) + { + return 1; /* Error */ + } + + pthread_mutex_lock(&THR_LOCK_mutex); + mp->id= ++safe_mutex_id; + pthread_mutex_unlock(&THR_LOCK_mutex); + hash_init(mp->locked_mutex, &my_charset_bin, + 1000, + offsetof(safe_mutex_deadlock_t, id), + sizeof(mp->id), + 0, 0, HASH_UNIQUE); + hash_init(mp->used_mutex, &my_charset_bin, + 1000, + offsetof(safe_mutex_t, id), + sizeof(mp->id), + 0, 0, HASH_UNIQUE); + return 0; +} int safe_mutex_init(safe_mutex_t *mp, const pthread_mutexattr_t *attr __attribute__((unused)), @@ -167,35 +196,8 @@ int safe_mutex_init(safe_mutex_t *mp, mp->line= line; /* Skip the very common '&' prefix from the autogenerated name */ mp->name= name[0] == '&' ? name + 1 : name; + /* Deadlock detection is initialised only lazily, on first use. */ - if (safe_mutex_deadlock_detector && !( my_flags & MYF_NO_DEADLOCK_DETECTION)) - { - if (!my_multi_malloc(MY_FAE | MY_WME, - &mp->locked_mutex, sizeof(*mp->locked_mutex), - &mp->used_mutex, sizeof(*mp->used_mutex), NullS)) - { - /* Disable deadlock handling for this mutex */ - my_flags|= MYF_NO_DEADLOCK_DETECTION; - } - else - { - pthread_mutex_lock(&THR_LOCK_mutex); - mp->id= ++safe_mutex_id; - pthread_mutex_unlock(&THR_LOCK_mutex); - hash_init(mp->locked_mutex, &my_charset_bin, - 1000, - offsetof(safe_mutex_deadlock_t, id), - sizeof(mp->id), - 0, 0, HASH_UNIQUE); - hash_init(mp->used_mutex, &my_charset_bin, - 1000, - offsetof(safe_mutex_t, id), - sizeof(mp->id), - 0, 0, HASH_UNIQUE); - } - } - else - my_flags|= MYF_NO_DEADLOCK_DETECTION; mp->create_flags= my_flags; #ifdef SAFE_MUTEX_DETECT_DESTROY @@ -310,7 +312,8 @@ int safe_mutex_lock(safe_mutex_t *mp, my /* Deadlock detection */ mp->prev= mp->next= 0; - if (!(mp->active_flags & (MYF_TRY_LOCK | MYF_NO_DEADLOCK_DETECTION))) + if (!(mp->active_flags & (MYF_TRY_LOCK | MYF_NO_DEADLOCK_DETECTION)) && + (mp->used_mutex != NULL || !safe_mutex_lazy_init_deadlock_detection(mp))) { safe_mutex_t **mutex_in_use= my_thread_var_mutex_in_use(); @@ -643,7 +646,7 @@ int safe_mutex_destroy(safe_mutex_t *mp, void safe_mutex_free_deadlock_data(safe_mutex_t *mp) { /* Free all entries that points to this one */ - if (!(mp->create_flags & MYF_NO_DEADLOCK_DETECTION)) + if (!(mp->create_flags & MYF_NO_DEADLOCK_DETECTION) && mp->used_mutex != NULL) { pthread_mutex_lock(&THR_LOCK_mutex); my_hash_iterate(mp->used_mutex, === modified file 'storage/xtradb/ibuf/ibuf0ibuf.c' --- a/storage/xtradb/ibuf/ibuf0ibuf.c 2009-03-26 06:11:11 +0000 +++ b/storage/xtradb/ibuf/ibuf0ibuf.c 2009-06-09 15:08:46 +0000 @@ -422,7 +422,12 @@ ibuf_init_at_db_start(void) grow in size, as the references on the upper levels of the tree can change */ - ibuf->max_size = ut_min( buf_pool_get_curr_size() / UNIV_PAGE_SIZE + /* The default for ibuf_max_size is calculated from the requested + buffer pool size srv_buf_pool_size, not the actual size as returned + by buf_pool_get_curr_size(). The latter can differ from the former + by one page due to alignment requirements, and we do not want a + user-visible variable like INNODB_IBUF_MAX_SIZE to vary at random. */ + ibuf->max_size = ut_min( srv_buf_pool_size / UNIV_PAGE_SIZE / IBUF_POOL_SIZE_PER_MAX_SIZE, (ulint) srv_ibuf_max_size / UNIV_PAGE_SIZE); srv_ibuf_max_size = (long long) ibuf->max_size * UNIV_PAGE_SIZE; === modified file 'storage/xtradb/include/sync0rw.h' --- a/storage/xtradb/include/sync0rw.h 2009-03-26 06:11:11 +0000 +++ b/storage/xtradb/include/sync0rw.h 2009-06-09 15:08:46 +0000 @@ -357,6 +357,8 @@ rw_lock_get_x_lock_count( rw_lock_t* lock); /* in: rw-lock */ /************************************************************************ Accessor functions for rw lock. */ + +#ifdef INNODB_RW_LOCKS_USE_ATOMICS UNIV_INLINE ulint rw_lock_get_s_waiters( @@ -372,6 +374,14 @@ ulint rw_lock_get_wx_waiters( /*================*/ rw_lock_t* lock); +#else /* !INNODB_RW_LOCKS_USE_ATOMICS */ +UNIV_INLINE +ulint +rw_lock_get_waiters( +/*==================*/ + rw_lock_t* lock); +#endif /* INNODB_RW_LOCKS_USE_ATOMICS */ + UNIV_INLINE ulint rw_lock_get_writer( @@ -488,6 +498,7 @@ rw_lock_debug_print( rw_lock_debug_t* info); /* in: debug struct */ #endif /* UNIV_SYNC_DEBUG */ +/* #ifndef INNODB_RW_LOCKS_USE_ATOMICS #error INNODB_RW_LOCKS_USE_ATOMICS is not defined. Do you use enough new GCC or compatibles? #error Or do you use exact options for CFLAGS? @@ -495,6 +506,7 @@ rw_lock_debug_print( #error e.g. (for Sparc_64): "-m64 -mcpu=v9" #error Otherwise, this build may be slower than normal version. #endif +*/ /* NOTE! The structure appears here only for the compiler to know its size. Do not use its fields directly! The structure used in the spin lock === modified file 'storage/xtradb/include/sync0rw.ic' --- a/storage/xtradb/include/sync0rw.ic 2009-03-26 06:11:11 +0000 +++ b/storage/xtradb/include/sync0rw.ic 2009-06-09 15:08:46 +0000 @@ -68,6 +68,8 @@ rw_lock_remove_debug_info( /************************************************************************ Accessor functions for rw lock. */ + +#ifdef INNODB_RW_LOCKS_USE_ATOMICS UNIV_INLINE ulint rw_lock_get_s_waiters( @@ -93,23 +95,32 @@ rw_lock_get_wx_waiters( { return(lock->wait_ex_waiters); } +#else /* !INNODB_RW_LOCKS_USE_ATOMICS */ +UNIV_INLINE +ulint +rw_lock_get_waiters( +/*================*/ + /* out: 1 if waiters, 0 otherwise */ + rw_lock_t* lock) /* in: rw-lock */ +{ + return(lock->waiters); +} +#endif /* INNODB_RW_LOCKS_USE_ATOMICS */ + /************************************************************************ Sets lock->waiters to 1. It is not an error if lock->waiters is already 1. On platforms where ATOMIC builtins are used this function enforces a memory barrier. */ +#ifdef INNODB_RW_LOCKS_USE_ATOMICS UNIV_INLINE void rw_lock_set_s_waiter_flag( /*====================*/ rw_lock_t* lock) /* in: rw-lock */ { -#ifdef INNODB_RW_LOCKS_USE_ATOMICS // os_compare_and_swap(&lock->s_waiters, 0, 1); __sync_lock_test_and_set(&lock->s_waiters, 1); -#else /* INNODB_RW_LOCKS_USE_ATOMICS */ - lock->s_waiters = 1; -#endif /* INNODB_RW_LOCKS_USE_ATOMICS */ } UNIV_INLINE void @@ -117,12 +128,8 @@ rw_lock_set_x_waiter_flag( /*====================*/ rw_lock_t* lock) /* in: rw-lock */ { -#ifdef INNODB_RW_LOCKS_USE_ATOMICS // os_compare_and_swap(&lock->x_waiters, 0, 1); __sync_lock_test_and_set(&lock->x_waiters, 1); -#else /* INNODB_RW_LOCKS_USE_ATOMICS */ - lock->x_waiters = 1; -#endif /* INNODB_RW_LOCKS_USE_ATOMICS */ } UNIV_INLINE void @@ -130,30 +137,34 @@ rw_lock_set_wx_waiter_flag( /*====================*/ rw_lock_t* lock) /* in: rw-lock */ { -#ifdef INNODB_RW_LOCKS_USE_ATOMICS // os_compare_and_swap(&lock->wait_ex_waiters, 0, 1); __sync_lock_test_and_set(&lock->wait_ex_waiters, 1); -#else /* INNODB_RW_LOCKS_USE_ATOMICS */ - lock->wait_ex_waiters = 1; -#endif /* INNODB_RW_LOCKS_USE_ATOMICS */ } +#else /* !INNODB_RW_LOCKS_USE_ATOMICS */ +UNIV_INLINE +void +rw_lock_set_waiter_flag( +/*====================*/ + rw_lock_t* lock) /* in: rw-lock */ +{ + lock->waiters = 1; +} +#endif /* INNODB_RW_LOCKS_USE_ATOMICS */ /************************************************************************ Resets lock->waiters to 0. It is not an error if lock->waiters is already 0. On platforms where ATOMIC builtins are used this function enforces a memory barrier. */ +#ifdef INNODB_RW_LOCKS_USE_ATOMICS + UNIV_INLINE void rw_lock_reset_s_waiter_flag( /*======================*/ rw_lock_t* lock) /* in: rw-lock */ { -#ifdef INNODB_RW_LOCKS_USE_ATOMICS // os_compare_and_swap(&lock->s_waiters, 1, 0); __sync_lock_test_and_set(&lock->s_waiters, 0); -#else /* INNODB_RW_LOCKS_USE_ATOMICS */ - lock->s_waiters = 0; -#endif /* INNODB_RW_LOCKS_USE_ATOMICS */ } UNIV_INLINE void @@ -161,12 +172,8 @@ rw_lock_reset_x_waiter_flag( /*======================*/ rw_lock_t* lock) /* in: rw-lock */ { -#ifdef INNODB_RW_LOCKS_USE_ATOMICS // os_compare_and_swap(&lock->x_waiters, 1, 0); __sync_lock_test_and_set(&lock->x_waiters, 0); -#else /* INNODB_RW_LOCKS_USE_ATOMICS */ - lock->x_waiters = 0; -#endif /* INNODB_RW_LOCKS_USE_ATOMICS */ } UNIV_INLINE void @@ -174,13 +181,19 @@ rw_lock_reset_wx_waiter_flag( /*======================*/ rw_lock_t* lock) /* in: rw-lock */ { -#ifdef INNODB_RW_LOCKS_USE_ATOMICS // os_compare_and_swap(&lock->wait_ex_waiters, 1, 0); __sync_lock_test_and_set(&lock->wait_ex_waiters, 0); -#else /* INNODB_RW_LOCKS_USE_ATOMICS */ - lock->wait_ex_waiters = 0; -#endif /* INNODB_RW_LOCKS_USE_ATOMICS */ } +#else /* !INNODB_RW_LOCKS_USE_ATOMICS */ +UNIV_INLINE +void +rw_lock_reset_waiter_flag( +/*======================*/ + rw_lock_t* lock) /* in: rw-lock */ +{ + lock->waiters = 0; +} +#endif /* INNODB_RW_LOCKS_USE_ATOMICS */ /********************************************************************** Returns the write-status of the lock - this function made more sense === modified file 'storage/xtradb/include/univ.i' --- a/storage/xtradb/include/univ.i 2009-03-26 06:11:11 +0000 +++ b/storage/xtradb/include/univ.i 2009-06-09 15:08:46 +0000 @@ -210,7 +210,7 @@ operations (very slow); also UNIV_DEBUG #define UNIV_BTR_DEBUG /* check B-tree links */ #define UNIV_LIGHT_MEM_DEBUG /* light memory debugging */ -#ifdef HAVE_purify +#ifdef HAVE_valgrind /* The following sets all new allocated memory to zero before use: this can be used to eliminate unnecessary Purify warnings, but note that it also masks many bugs Purify could detect. For detailed Purify analysis it === removed file 'storage/xtradb/setup.sh' --- a/storage/xtradb/setup.sh 2009-06-09 11:16:11 +0000 +++ b/storage/xtradb/setup.sh 1970-01-01 00:00:00 +0000 @@ -1,47 +0,0 @@ -#!/bin/sh -# -# Copyright (c) 1995, 2009, Innobase Oy. All Rights Reserved. -# -# 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 the Free Software -# Foundation; version 2 of the License. -# -# This program is distributed in the hope that it will be useful, but WITHOUT -# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS -# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. -# -# You should have received a copy of the GNU General Public License along with -# this program; if not, write to the Free Software Foundation, Inc., 59 Temple -# Place, Suite 330, Boston, MA 02111-1307 USA -# -# Prepare the MySQL source code tree for building -# with checked-out InnoDB Subversion directory. - -# This script assumes that the current directory is storage/innobase. - -set -eu - -TARGETDIR=../storage/innobase - -# link the build scripts -BUILDSCRIPTS="compile-innodb compile-innodb-debug" -for script in $BUILDSCRIPTS ; do - ln -sf $TARGETDIR/$script ../../BUILD/ -done - -cd ../../mysql-test/t -ln -sf ../$TARGETDIR/mysql-test/*.test ../$TARGETDIR/mysql-test/*.opt . -cd ../r -ln -sf ../$TARGETDIR/mysql-test/*.result . -cd ../include -ln -sf ../$TARGETDIR/mysql-test/*.inc . - -# Apply any patches that are needed to make the mysql-test suite successful. -# These patches are usually needed because of deviations of behavior between -# the stock InnoDB and the InnoDB Plugin. -cd ../.. -for patch in storage/innobase/mysql-test/patches/*.diff ; do - if [ "${patch}" != "storage/innobase/mysql-test/patches/*.diff" ] ; then - patch -p0 < ${patch} - fi -done === modified file 'storage/xtradb/srv/srv0start.c' --- a/storage/xtradb/srv/srv0start.c 2009-03-26 06:11:11 +0000 +++ b/storage/xtradb/srv/srv0start.c 2009-06-09 15:08:46 +0000 @@ -124,7 +124,7 @@ static char* srv_monitor_file_name; /* Avoid warnings when using purify */ -#ifdef HAVE_purify +#ifdef HAVE_valgrind static int inno_bcmp(register const char *s1, register const char *s2, register uint len) {

3 2

[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (knielsen:2714)
by knielsen＠knielsen-hq.org 19 Jun '09

19 Jun '09

#At lp:maria 2714 knielsen(a)knielsen-hq.org 2009-06-18 Fix test cases after merge of XtraDB into MariaDB. Manually merge some InnoDB changes into XtraDB. Fix ALTER TABLE bug in XtraDB with wrong comparison of row type. modified: mysql-test/include/varchar.inc mysql-test/mysql-test-run.pl mysql-test/r/innodb.result mysql-test/t/innodb-use-sys-malloc.test sql/sql_table.cc storage/xtradb/handler/ha_innodb.cc storage/xtradb/include/pars0pars.h storage/xtradb/include/univ.i per-file messages: mysql-test/include/varchar.inc Fix in test case that which of several duplicate keys triggers an error is not deterministic. mysql-test/mysql-test-run.pl InnoDB does not bother to free resources individually during shutdown, but due to using its own memory tracking it nevertheless can free everything at exit. But XtraDB adds an option, on by default, to skip this extra tracking. This causes lots of Valgrind warnings, so needs to be disabled for Valgrind testing. mysql-test/r/innodb.result Fix in test case that which of several duplicate keys triggers an error is not deterministic. mysql-test/t/innodb-use-sys-malloc.test InnoDB does not bother to free resources individually during shutdown, but due to using its own memory tracking it nevertheless can free everything at exit. But XtraDB adds an option, on by default, to skip this extra tracking. This causes lots of Valgrind warnings, so needs to be disabled for Valgrind testing. sql/sql_table.cc Add some useful DBUG while debugging alter table. storage/xtradb/handler/ha_innodb.cc Fix that check_if_incompatible_data did not realise that ROW_TYPE_DEFAULT is identical to the default row format ROW_TYPE_COMPACT, causing excessive table copying in ALTER TABLE Add some useful DBUG while debugging alter table. Manually merge into XtraDB a few small changes for InnoDB from upstream MySQL. storage/xtradb/include/pars0pars.h Manually merge into XtraDB a few small changes for InnoDB from upstream MySQL. storage/xtradb/include/univ.i Manually merge a MariaDB fix in InnoDB into XtraDB. === modified file 'mysql-test/include/varchar.inc' --- a/mysql-test/include/varchar.inc 2008-05-14 06:50:16 +0000 +++ b/mysql-test/include/varchar.inc 2009-06-18 12:39:21 +0000 @@ -86,6 +86,8 @@ explain select count(*) from t1 where v --replace_column 9 # explain select count(*) from t1 where v between 'a' and 'a ' and v between 'a ' and 'b\n'; +# Which duplicate entry triggers error is not deterministic. +--replace_regex /Duplicate entry '[^']+' for key/Duplicate entry '{ ' for key/ --error ER_DUP_ENTRY alter table t1 add unique(v); alter table t1 add key(v); === modified file 'mysql-test/mysql-test-run.pl' --- a/mysql-test/mysql-test-run.pl 2009-06-05 15:35:22 +0000 +++ b/mysql-test/mysql-test-run.pl 2009-06-18 12:39:21 +0000 @@ -1356,6 +1356,18 @@ sub command_line_setup { join(" ", @valgrind_args), "\""); } + # InnoDB does not bother to do individual de-allocations at exit. Instead it + # relies on a custom allocator to track every allocation, and frees all at + # once during exit. + # In XtraDB, an option use-sys-malloc is introduced (and on by default) to + # disable this (for performance). But this exposes Valgrind to all the + # missing de-allocations, so we need to disable it to at least get + # meaningful leak checking for the rest of the server. + if ($opt_valgrind_mysqld) + { + push(@opt_extra_mysqld_opt, "--loose-skip-innodb-use-sys-malloc"); + } + mtr_report("Checking supported features..."); check_ndbcluster_support(\%mysqld_variables); === modified file 'mysql-test/r/innodb.result' --- a/mysql-test/r/innodb.result 2009-06-09 15:08:46 +0000 +++ b/mysql-test/r/innodb.result 2009-06-18 12:39:21 +0000 @@ -1970,7 +1970,7 @@ explain select count(*) from t1 where v id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t1 ref v v 13 const # Using where; Using index alter table t1 add unique(v); -ERROR 23000: Duplicate entry 'v' for key 'v_2' +ERROR 23000: Duplicate entry '{ ' for key 'v_2' alter table t1 add key(v); select concat('*',v,'*',c,'*',t,'*') as qq from t1 where v='a'; qq === modified file 'mysql-test/t/innodb-use-sys-malloc.test' --- a/mysql-test/t/innodb-use-sys-malloc.test 2009-06-09 13:19:13 +0000 +++ b/mysql-test/t/innodb-use-sys-malloc.test 2009-06-18 12:39:21 +0000 @@ -1,4 +1,7 @@ --source include/have_innodb.inc +# XtraDB has lots of memory leak warnings at shutdown when +# --innodb-use-sys-malloc +--source include/not_valgrind.inc #display current value of innodb_use_sys_malloc SELECT @@GLOBAL.innodb_use_sys_malloc; === modified file 'sql/sql_table.cc' --- a/sql/sql_table.cc 2009-06-02 09:58:27 +0000 +++ b/sql/sql_table.cc 2009-06-18 12:39:21 +0000 @@ -5333,6 +5333,7 @@ compare_tables(TABLE *table, !table->s->mysql_version || (table->s->frm_version < FRM_VER_TRUE_VARCHAR && varchar)) { + DBUG_PRINT("info", ("Basic checks -> ALTER_TABLE_DATA_CHANGED")); *need_copy_table= ALTER_TABLE_DATA_CHANGED; DBUG_RETURN(0); } @@ -5361,6 +5362,8 @@ compare_tables(TABLE *table, if ((tmp_new_field->flags & NOT_NULL_FLAG) != (uint) (field->flags & NOT_NULL_FLAG)) { + DBUG_PRINT("info", ("NULL behaviour difference in field '%s' -> " + "ALTER_TABLE_DATA_CHANGED", new_field->field_name)); *need_copy_table= ALTER_TABLE_DATA_CHANGED; DBUG_RETURN(0); } @@ -5382,6 +5385,8 @@ compare_tables(TABLE *table, /* Evaluate changes bitmap and send to check_if_incompatible_data() */ if (!(tmp= field->is_equal(tmp_new_field))) { + DBUG_PRINT("info", ("!field_is_equal('%s') -> ALTER_TABLE_DATA_CHANGED", + new_field->field_name)); *need_copy_table= ALTER_TABLE_DATA_CHANGED; DBUG_RETURN(0); } @@ -5515,16 +5520,22 @@ compare_tables(TABLE *table, /* Check if changes are compatible with current handler without a copy */ if (table->file->check_if_incompatible_data(create_info, changes)) { + DBUG_PRINT("info", ("check_if_incompatible_data() -> " + "ALTER_TABLE_DATA_CHANGED")); *need_copy_table= ALTER_TABLE_DATA_CHANGED; DBUG_RETURN(0); } if (*index_drop_count || *index_add_count) { + DBUG_PRINT("info", ("Index dropped=%u added=%u -> " + "ALTER_TABLE_INDEX_CHANGED", + *index_drop_count, *index_add_count)); *need_copy_table= ALTER_TABLE_INDEX_CHANGED; DBUG_RETURN(0); } + DBUG_PRINT("info", (" -> ALTER_TABLE_METADATA_ONLY")); *need_copy_table= ALTER_TABLE_METADATA_ONLY; // Tables are compatible DBUG_RETURN(0); } === modified file 'storage/xtradb/handler/ha_innodb.cc' --- a/storage/xtradb/handler/ha_innodb.cc 2009-06-11 12:53:26 +0000 +++ b/storage/xtradb/handler/ha_innodb.cc 2009-06-18 12:39:21 +0000 @@ -5018,7 +5018,6 @@ convert_search_mode_to_innobase( case HA_READ_MBR_WITHIN: case HA_READ_MBR_DISJOINT: case HA_READ_MBR_EQUAL: - my_error(ER_TABLE_CANT_HANDLE_SPKEYS, MYF(0)); return(PAGE_CUR_UNSUPP); /* do not use "default:" in order to produce a gcc warning: enumeration value '...' not handled in switch @@ -6720,6 +6719,7 @@ innobase_rename_table( int error; char* norm_to; char* norm_from; + DBUG_ENTER("innobase_rename_table"); if (lower_case_table_names) { srv_lower_case_table_names = TRUE; @@ -6747,6 +6747,7 @@ innobase_rename_table( if (error != DB_SUCCESS) { FILE* ef = dict_foreign_err_file; + DBUG_PRINT("info", ("rename failed: %d", error)); fputs("InnoDB: Renaming table ", ef); ut_print_name(ef, trx, TRUE, norm_from); fputs(" to ", ef); @@ -6767,7 +6768,7 @@ innobase_rename_table( my_free(norm_to, MYF(0)); my_free(norm_from, MYF(0)); - return error; + DBUG_RETURN(error); } /************************************************************************* Renames an InnoDB table. */ @@ -6900,7 +6901,7 @@ ha_innobase::records_in_range( mode2); } else { - n_rows = 0; + n_rows = HA_POS_ERROR; } mem_heap_free(heap); @@ -7614,7 +7615,7 @@ ha_innobase::get_foreign_key_list(THD *t f_key_info.referenced_key_name = thd_make_lex_string( thd, f_key_info.referenced_key_name, foreign->referenced_index->name, - strlen(foreign->referenced_index->name), 1); + (uint) strlen(foreign->referenced_index->name), 1); } else f_key_info.referenced_key_name= 0; @@ -8227,7 +8228,7 @@ innodb_show_status( bool result = FALSE; - if (stat_print(thd, innobase_hton_name, strlen(innobase_hton_name), + if (stat_print(thd, innobase_hton_name, (uint) strlen(innobase_hton_name), STRING_WITH_LEN(""), str, flen)) { result= TRUE; } @@ -8258,7 +8259,7 @@ innodb_mutex_show_status( ulint rw_lock_count_os_yield= 0; ulonglong rw_lock_wait_time= 0; #endif /* UNIV_DEBUG */ - uint hton_name_len= strlen(innobase_hton_name), buf1len, buf2len; + uint hton_name_len= (uint) strlen(innobase_hton_name), buf1len, buf2len; DBUG_ENTER("innodb_mutex_show_status"); DBUG_ASSERT(hton == innodb_hton_ptr); @@ -8302,9 +8303,9 @@ innodb_mutex_show_status( rw_lock_wait_time += mutex->lspent_time; } #else /* UNIV_DEBUG */ - buf1len= my_snprintf(buf1, sizeof(buf1), "%s:%lu", + buf1len= (uint) my_snprintf(buf1, sizeof(buf1), "%s:%lu", mutex->cfile_name, (ulong) mutex->cline); - buf2len= my_snprintf(buf2, sizeof(buf2), "os_waits=%lu", + buf2len= (uint) my_snprintf(buf2, sizeof(buf2), "os_waits=%lu", mutex->count_os_wait); if (stat_print(thd, innobase_hton_name, @@ -8860,7 +8861,7 @@ ha_innobase::get_error_message(int error { trx_t* trx = check_trx_exists(ha_thd()); - buf->copy(trx->detailed_error, strlen(trx->detailed_error), + buf->copy(trx->detailed_error, (uint) strlen(trx->detailed_error), system_charset_info); return(FALSE); @@ -9294,31 +9295,49 @@ ha_innobase::check_if_incompatible_data( HA_CREATE_INFO* info, uint table_changes) { + enum row_type row_type, info_row_type; + DBUG_ENTER("ha_innobase::check_if_incompatible_data"); + if (table_changes != IS_EQUAL_YES) { - return(COMPATIBLE_DATA_NO); + DBUG_PRINT("info", ("table_changes != IS_EQUAL_YES " + "-> COMPATIBLE_DATA_NO")); + DBUG_RETURN(COMPATIBLE_DATA_NO); } /* Check that auto_increment value was not changed */ if ((info->used_fields & HA_CREATE_USED_AUTO) && info->auto_increment_value != 0) { - return(COMPATIBLE_DATA_NO); + DBUG_PRINT("info", ("auto_increment_value changed -> " + "COMPATIBLE_DATA_NO")); + DBUG_RETURN(COMPATIBLE_DATA_NO); } /* Check that row format didn't change */ + row_type = get_row_type(); + info_row_type = info->row_type; + /* Default is compact. */ + if (info_row_type == ROW_TYPE_DEFAULT) + info_row_type = ROW_TYPE_COMPACT; if ((info->used_fields & HA_CREATE_USED_ROW_FORMAT) && - get_row_type() != info->row_type) { + row_type != info_row_type) { - return(COMPATIBLE_DATA_NO); + DBUG_PRINT("info", ("get_row_type()=%d != info->row_type=%d -> " + "COMPATIBLE_DATA_NO", + row_type, info->row_type)); + DBUG_RETURN(COMPATIBLE_DATA_NO); } /* Specifying KEY_BLOCK_SIZE requests a rebuild of the table. */ if (info->used_fields & HA_CREATE_USED_KEY_BLOCK_SIZE) { - return(COMPATIBLE_DATA_NO); + DBUG_PRINT("info", ("HA_CREATE_USED_KEY_BLOCK_SIZE -> " + "COMPATIBLE_DATA_NO")); + DBUG_RETURN(COMPATIBLE_DATA_NO); } - return(COMPATIBLE_DATA_YES); + DBUG_PRINT("info", (" -> COMPATIBLE_DATA_YES")); + DBUG_RETURN(COMPATIBLE_DATA_YES); } /**************************************************************** === modified file 'storage/xtradb/include/pars0pars.h' --- a/storage/xtradb/include/pars0pars.h 2009-03-26 06:11:11 +0000 +++ b/storage/xtradb/include/pars0pars.h 2009-06-18 12:39:21 +0000 @@ -700,7 +700,7 @@ struct for_node_struct{ definition */ que_node_t* loop_start_limit;/* initial value of loop variable */ que_node_t* loop_end_limit; /* end value of loop variable */ - int loop_end_value; /* evaluated value for the end value: + lint loop_end_value; /* evaluated value for the end value: it is calculated only when the loop is entered, and will not change within the loop */ === modified file 'storage/xtradb/include/univ.i' --- a/storage/xtradb/include/univ.i 2009-06-11 12:53:26 +0000 +++ b/storage/xtradb/include/univ.i 2009-06-18 12:39:21 +0000 @@ -133,10 +133,10 @@ from Makefile.in->ut0auxconf.h */ # endif /* HAVE_ATOMIC_PTHREAD_T */ #endif /* HAVE_GCC_ATOMIC_BUILTINS */ -/* We only try to do explicit inlining of functions with gcc and -Microsoft Visual C++ */ +/* Enable explicit inlining of functions only for compilers known to +support it. */ -# if !defined(__GNUC__) +# if !defined(__GNUC__) && !defined(__SUNPRO_C) # undef UNIV_MUST_NOT_INLINE /* Remove compiler warning */ # define UNIV_MUST_NOT_INLINE # endif

3 2

[Maria-developers] Updated (by Guest): index_merge: fair choice between index_merge union and range access (24)
by worklog-noreply＠askmonty.org 18 Jun '09

18 Jun '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: index_merge: fair choice between index_merge union and range access CREATION DATE..: Tue, 26 May 2009, 12:10 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: Psergey CATEGORY.......: Server-Sprint TASK ID........: 24 (http://askmonty.org/worklog/?tid=24) VERSION........: 9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Thu, 18 Jun 2009, 16:55)=-=- Low Level Design modified. --- /tmp/wklog.24.old.19152 2009-06-18 16:55:00.000000000 +0300 +++ /tmp/wklog.24.new.19152 2009-06-18 16:55:00.000000000 +0300 @@ -141,13 +141,15 @@ Operations on SEL_ARG trees will be modified to produce/process the trees of this kind: + 2.1 New tree_and() ------------------ In order not to lose plans, we'll make these changes: -1. Don't remove index_merge part of the tree. +A1. Don't remove index_merge part of the tree (this will take care of + DISCARD-IMERGE-1 problem) -2. Push range conditions down into index_merge trees that may support them. +A2. Push range conditions down into index_merge trees that may support them. if one tree has range(key1) and the other tree has imerge(key1 OR key2) then perform an equvalent of this operation: @@ -155,8 +157,86 @@ (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) -3. Just as before: if both sel_tree A and sel_tree B have index_merge options, +A3. Just as before: if both sel_tree A and sel_tree B have index_merge options, concatenate them together. -2.2 New tree_or() +2.2 New tree_or() +----------------- +O1. Dont remove non-range plans: + Current tree_or() code will refuse to produce index_merge plans for + conditions like + + "t.key1part2=const OR t.key2part1=const" + + (this is marked as DISCARD-IMERGE-3). This was justifed as the left part of + the AND condition is not usable for range access, and the operation of + tree_and() guaranteed that there was no way it could changed to make a + usable range plan. With new tree_and() and rule A2, this is no longer the + case. For example for this query: + + (t.key1part2=const OR t.key2part1=const) AND t.key1part1=const + + it will construct a + + imerge(t.key1part2=const OR t.key2part1=const), range(t.key1part1=const) + + then tree_and() will apply rule A2 to push the range down into index merge + and after that we'll have: + + range(t.key1part1=const) + imerge( + t.key1part2=const AND t.key1part1=const, + t.key2part1=const + ) + note that imerge(...) describes a usable index_merge plan and it's possible + that it will be the best access path. + +O2. "Create index_merge accesses when possible" + Current tree_or() will not create index_merge access when it could create + non-index merge access (see DISCARD-IMERGE-3 and its example in the "Problems + in the current implementation" section). This will be changed to work as + follows: we will create index_merge made for index scans that didn't have + their match in the other sel_tree. + Ilustrating it with an example: + + | sel_tree_A | sel_tree_B | A or B | include in index_merge? + ------+------------+------------+--------+------------------------ + key1 | cond1 | cond2 | condM | no + key2 | cond3 | cond4 | NULL | no + key3 | cond5 | | | yes, A-side + key4 | cond6 | | | yes, A-side + key5 | | cond7 | | yes, B-side + key6 | | cond8 | | yes, B-side + + here we assume that + - (cond1 OR cond2) did produce a combined range. Not including them in + index_merge. + - (cond3 OR cond4) didn't produce a usable range (e.g. they were + t.key1part1=c1 AND t.key1part2=c1, respectively, and combining them + didn't yield any range list) + - All other scand didn't have their counterparts, so we'll end up with a + SEL_TREE of: + + range(condM) AND index_merge((cond5 AND cond6),(cond7 AND cond8)) + . + +O4. There is no O4. DISCARD-INDEX-MERGE-4 will remain there. The idea is +that although DISCARD-INDEX-MERGE-4 does discard plans, so far we haven +seen any complaints that could be attributed to it. +If we face the need to lift DISCARD-INDEX-MERGE-4, our answer will be to +lift it ,and produce a cross-product: + + ((key1p OR key2p) AND (key3p OR key4p)) + OR + ((key5p OR key6p) AND (key7p OR key8p)) + + = (key1p OR key2p OR key5p OR key6p) AND // this part is currently + (key3p OR key4p OR key5p OR key6p) AND // produced + + (key1p OR key2p OR key5p OR key6p) AND // this part will be added + (key3p OR key4p OR key5p OR key6p) //. + +In order to limit the impact of this combinatorial explosion, we will +introduce a rule that we won't generate more than #defined +MAX_IMERGE_OPTS options. -=-=(Guest - Thu, 18 Jun 2009, 14:56)=-=- Low Level Design modified. --- /tmp/wklog.24.old.15612 2009-06-18 14:56:09.000000000 +0300 +++ /tmp/wklog.24.new.15612 2009-06-18 14:56:09.000000000 +0300 @@ -1 +1,162 @@ +<contents> +1. Current implementation overview +1.1. Problems in the current implementation +2. New implementation +2.1 New tree_and() +2.2 New tree_or() +</contents> + +1. Current implementation overview +================================== +At the moment, range analyzer works as follows: + +SEL_TREE structure represents + + # There are sel_trees, a sel_tree is either range or merge tree + sel_tree = range_tree | imerge_tree + + # a range tree has range access options, possibly for several keys + range_tree = range(key1) AND range(key2) AND ... AND range(keyN); + + # merge tree represents several way to index_merge + imerge_tree = imerge1 AND imerge2 AND ... + + # a way to do index merge == a set to use of different indexes. + imergeX = range_tree1 OR range_tree2 OR .. + where no pair of range_treeX have ranges over the same index. + + + tree_and(A, B) + { + if (both A and B are range trees) + return a range_tree with computed intersection for each range; + if (only one of A and B is a range tree) + return that tree; // DISCARD-IMERGE-1 + // at this point both trees are index_merge trees + return concat_lists( A.imerge1 ... A.imergeN, B.imerge1 ... B.imergeN); + } + + + tree_or(A, B) + { + if (A and B are range trees) + { + R = new range_tree; + for each index i + R.add(range_union(A.range(i), B.range(i))); + + if (R has at least one range access) + return R; + else + { + /* could not build any range accesses. construct index_merge */ + remove non-ranges from A; // DISCARD-IMERGE-2 + remove non-ranges from B; + return new index_merge(A, B); + } + } + else if (A is range tree and B is index_merge tree (or vice versa)) + { + Perform this transformation: + + range_treeA // this is A + OR + (range_treeB_11 OR range_treeB_12 OR ... OR range_treeB_1N) AND + (range_treeB_21 OR range_treeB_22 OR ... OR range_treeB_2N) AND + ... + (range_treeB_K1 OR range_treeB_K2 OR ... OR range_treeB_kN) AND + = + (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND + (range_treeA OR range_treeB_21 OR ... OR range_treeB_2N) AND + ... + (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND + + Now each line represents an index_merge.. + } + else if (both A and B are index_merge trees) + { + Perform this transformation: + + imergeA1 AND imergeA2 AND ... AND imergeAN + OR + imergeB1 AND imergeB2 AND ... AND imergeBN + + -> (discard all imergeA{i=2,3,...} -> // DISCARD-IMERGE-3 + + imergeA1 + OR + imergeB1 AND imergeB2 AND ... AND imergeBN = + + = (combine imergeA1 with each of the imergeB{i} ) = + + combine(imergeA1 OR imergeB1) AND + combine(imergeA1 OR imergeB2) AND + ... AND + combine(imergeA1 OR imergeBN) + } + } + +1.1. Problems in the current implementation +------------------------------------------- +As marked in the code above: + +DISCARD-IMERGE-1 step will cause index_merge option to be discarded when +the WHERE clause has this form: + + (t.key1=c1 OR t.key2=c2) AND t.badkey < c3 + +DISCARD-IMERGE-2 step will cause index_merge option to be discarded when +the WHERE clause has this form (conditions t.badkey may have abritrary form): + + (t.badkey<c1 AND t.key1=c1) OR (t.key1=c2 AND t.badkey < c2) + +DISCARD-IMERGE-3 manifests itself as the following effect: suppose there are +two indexes: + + INDEX i1(col1, col2), + INDEX i2(col1, col3) + +and this WHERE clause: + + col1=c1 AND (col2=c2 OR col3=c3) + +The optimizer will generate the plans that only use the "col1=c1" part. The +right side of the AND will be ignored even if it has good selectivity. + + +2. New implementation +===================== + +<general idea> +* Don't start fighting combinatorial explosion until we've actually got one. +</> + +SEL_TREE structure will be now able to hold both index_merge and range scan +candidates at the same time. That is, + + sel_tree2 = range_tree AND imerge_tree + +where both parts are optional (i.e. can be empty) + +Operations on SEL_ARG trees will be modified to produce/process the trees of +this kind: + +2.1 New tree_and() +------------------ +In order not to lose plans, we'll make these changes: + +1. Don't remove index_merge part of the tree. + +2. Push range conditions down into index_merge trees that may support them. + if one tree has range(key1) and the other tree has imerge(key1 OR key2) + then perform an equvalent of this operation: + + rangeA(key1) AND ( rangeB(key1) OR rangeB(key2)) = + + (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) + +3. Just as before: if both sel_tree A and sel_tree B have index_merge options, + concatenate them together. + +2.2 New tree_or() -=-=(Guest - Sat, 13 Jun 2009, 06:29)=-=- Category updated. --- /tmp/wklog.24.old.25753 2009-06-13 06:29:10.000000000 +0300 +++ /tmp/wklog.24.new.25753 2009-06-13 06:29:10.000000000 +0300 @@ -1 +1 @@ -Server-BackLog +Server-Sprint -=-=(Guest - Sat, 13 Jun 2009, 06:14)=-=- Category updated. --- /tmp/wklog.24.old.24991 2009-06-13 06:14:03.000000000 +0300 +++ /tmp/wklog.24.new.24991 2009-06-13 06:14:03.000000000 +0300 @@ -1 +1 @@ -Server-RawIdeaBin +Server-BackLog -=-=(Psergey - Wed, 03 Jun 2009, 12:09)=-=- Dependency created: 30 now depends on 24 -=-=(Guest - Mon, 01 Jun 2009, 23:30)=-=- High-Level Specification modified. --- /tmp/wklog.24.old.21580 2009-06-01 23:30:06.000000000 +0300 +++ /tmp/wklog.24.new.21580 2009-06-01 23:30:06.000000000 +0300 @@ -64,6 +64,9 @@ * How strict is the limitation on the form of the WHERE? +* Which version should this be based on? 5.1? Which patches are should be in + (google's/percona's/maria/etc?) + * TODO: The optimizer didn't compare costs of index_merge and range before (ok it did but that was done for accesses to different tables). Will there be any possible gotchas here? -=-=(Guest - Wed, 27 May 2009, 14:41)=-=- Category updated. --- /tmp/wklog.24.old.8414 2009-05-27 14:41:43.000000000 +0300 +++ /tmp/wklog.24.new.8414 2009-05-27 14:41:43.000000000 +0300 @@ -1 +1 @@ -Client-BackLog +Server-RawIdeaBin -=-=(Guest - Wed, 27 May 2009, 14:41)=-=- Version updated. --- /tmp/wklog.24.old.8414 2009-05-27 14:41:43.000000000 +0300 +++ /tmp/wklog.24.new.8414 2009-05-27 14:41:43.000000000 +0300 @@ -1 +1 @@ -Server-9.x +9.x -=-=(Guest - Wed, 27 May 2009, 13:59)=-=- Title modified. --- /tmp/wklog.24.old.9498 2009-05-27 13:59:23.000000000 +0300 +++ /tmp/wklog.24.new.9498 2009-05-27 13:59:23.000000000 +0300 @@ -1 +1 @@ -index_merge optimizer: dont discard index_merge union strategies when range is available +index_merge: fair choice between index_merge union and range access -=-=(Guest - Wed, 27 May 2009, 13:59)=-=- Version updated. --- /tmp/wklog.24.old.9498 2009-05-27 13:59:23.000000000 +0300 +++ /tmp/wklog.24.new.9498 2009-05-27 13:59:23.000000000 +0300 @@ -1 +1 @@ -Benchmarks-3.0 +Server-9.x ------------------------------------------------------------ -=-=(View All Progress Notes, 11 total)=-=- http://askmonty.org/worklog/index.pl?tid=24&nolimit=1 DESCRIPTION: Current range optimizer will discard possible index_merge/[sort]union strategies when there is a possible range plan. This action is a part of measures we take to avoid combinatorial explosion of possible range/ index_merge strategies. A bad side effect of this is that for WHERE clauses in form t.key1= 'very-frequent-value' AND (t.key2='rare-value1' OR t.key3='rare-value2') the optimizer will - discard union(key2,key3) in favor of range(key1) - consider costs of using range(key1) and discard that plan also and the overall effect is that possible poor range access will cause possible good index_merge access not to be considered. This WL is to about lifting this limitation at least for some subset of WHERE clauses. HIGH-LEVEL SPECIFICATION: (Not a ready HLS but draft) <contents> Solution overview Limitations TODO </contents> Solution overview ================= The idea is to delay discarding potential index_merge plans until the point where it is really necessary. This way, we won't have to do much changes in the range analyzer, but will be able to keep potential index_merge plan just enough so that it's possible to take it into consideration together with range access plans. Since there are no changes in the optimizer, the ability to consider both range and index_merge options will be limited to WHERE clauses of this form: WHERE := range_cond(key1_1) AND range_cond(key2_1) AND other_cond AND index_merge_OR_cond1(key3_1, key3_2, ...) index_merge_OR_cond2(key4_1, key4_2, ...) where index_merge_OR_cond{N} := (range_cond(keyN_1) OR range_cond(keyN_2) OR ...) range_cond(keyX) := condition that allows to construct range access of keyX and doesn't allow to construct range/index_merge accesses for any keys of the table in question. For such WHERE clauses, the range analyzer will produce SEL_TREE of this form: SEL_TREE( range(key1_1), ... range(key2_1), SEL_IMERGE( (1) SEL_TREE(key3_1}) SEL_TREE(key3_2}) ... ) ... ) which can be used to make a cost-based choice between range and index_merge. Limitations ----------- This will not be a full solution in a sense that the range analyzer will not be able to produce sel_tree (1) if the WHERE clause is specified in other form (e.g. brackets were opened). TODO ---- * is it a problem if there are keys that are referred to both from index_merge and from range access? * How strict is the limitation on the form of the WHERE? * Which version should this be based on? 5.1? Which patches are should be in (google's/percona's/maria/etc?) * TODO: The optimizer didn't compare costs of index_merge and range before (ok it did but that was done for accesses to different tables). Will there be any possible gotchas here? LOW-LEVEL DESIGN: <contents> 1. Current implementation overview 1.1. Problems in the current implementation 2. New implementation 2.1 New tree_and() 2.2 New tree_or() </contents> 1. Current implementation overview ================================== At the moment, range analyzer works as follows: SEL_TREE structure represents # There are sel_trees, a sel_tree is either range or merge tree sel_tree = range_tree | imerge_tree # a range tree has range access options, possibly for several keys range_tree = range(key1) AND range(key2) AND ... AND range(keyN); # merge tree represents several way to index_merge imerge_tree = imerge1 AND imerge2 AND ... # a way to do index merge == a set to use of different indexes. imergeX = range_tree1 OR range_tree2 OR .. where no pair of range_treeX have ranges over the same index. tree_and(A, B) { if (both A and B are range trees) return a range_tree with computed intersection for each range; if (only one of A and B is a range tree) return that tree; // DISCARD-IMERGE-1 // at this point both trees are index_merge trees return concat_lists( A.imerge1 ... A.imergeN, B.imerge1 ... B.imergeN); } tree_or(A, B) { if (A and B are range trees) { R = new range_tree; for each index i R.add(range_union(A.range(i), B.range(i))); if (R has at least one range access) return R; else { /* could not build any range accesses. construct index_merge */ remove non-ranges from A; // DISCARD-IMERGE-2 remove non-ranges from B; return new index_merge(A, B); } } else if (A is range tree and B is index_merge tree (or vice versa)) { Perform this transformation: range_treeA // this is A OR (range_treeB_11 OR range_treeB_12 OR ... OR range_treeB_1N) AND (range_treeB_21 OR range_treeB_22 OR ... OR range_treeB_2N) AND ... (range_treeB_K1 OR range_treeB_K2 OR ... OR range_treeB_kN) AND = (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND (range_treeA OR range_treeB_21 OR ... OR range_treeB_2N) AND ... (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND Now each line represents an index_merge.. } else if (both A and B are index_merge trees) { Perform this transformation: imergeA1 AND imergeA2 AND ... AND imergeAN OR imergeB1 AND imergeB2 AND ... AND imergeBN -> (discard all imergeA{i=2,3,...} -> // DISCARD-IMERGE-3 imergeA1 OR imergeB1 AND imergeB2 AND ... AND imergeBN = = (combine imergeA1 with each of the imergeB{i} ) = combine(imergeA1 OR imergeB1) AND combine(imergeA1 OR imergeB2) AND ... AND combine(imergeA1 OR imergeBN) } } 1.1. Problems in the current implementation ------------------------------------------- As marked in the code above: DISCARD-IMERGE-1 step will cause index_merge option to be discarded when the WHERE clause has this form: (t.key1=c1 OR t.key2=c2) AND t.badkey < c3 DISCARD-IMERGE-2 step will cause index_merge option to be discarded when the WHERE clause has this form (conditions t.badkey may have abritrary form): (t.badkey<c1 AND t.key1=c1) OR (t.key1=c2 AND t.badkey < c2) DISCARD-IMERGE-3 manifests itself as the following effect: suppose there are two indexes: INDEX i1(col1, col2), INDEX i2(col1, col3) and this WHERE clause: col1=c1 AND (col2=c2 OR col3=c3) The optimizer will generate the plans that only use the "col1=c1" part. The right side of the AND will be ignored even if it has good selectivity. 2. New implementation ===================== <general idea> * Don't start fighting combinatorial explosion until we've actually got one. </> SEL_TREE structure will be now able to hold both index_merge and range scan candidates at the same time. That is, sel_tree2 = range_tree AND imerge_tree where both parts are optional (i.e. can be empty) Operations on SEL_ARG trees will be modified to produce/process the trees of this kind: 2.1 New tree_and() ------------------ In order not to lose plans, we'll make these changes: A1. Don't remove index_merge part of the tree (this will take care of DISCARD-IMERGE-1 problem) A2. Push range conditions down into index_merge trees that may support them. if one tree has range(key1) and the other tree has imerge(key1 OR key2) then perform an equvalent of this operation: rangeA(key1) AND ( rangeB(key1) OR rangeB(key2)) = (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) A3. Just as before: if both sel_tree A and sel_tree B have index_merge options, concatenate them together. 2.2 New tree_or() ----------------- O1. Dont remove non-range plans: Current tree_or() code will refuse to produce index_merge plans for conditions like "t.key1part2=const OR t.key2part1=const" (this is marked as DISCARD-IMERGE-3). This was justifed as the left part of the AND condition is not usable for range access, and the operation of tree_and() guaranteed that there was no way it could changed to make a usable range plan. With new tree_and() and rule A2, this is no longer the case. For example for this query: (t.key1part2=const OR t.key2part1=const) AND t.key1part1=const it will construct a imerge(t.key1part2=const OR t.key2part1=const), range(t.key1part1=const) then tree_and() will apply rule A2 to push the range down into index merge and after that we'll have: range(t.key1part1=const) imerge( t.key1part2=const AND t.key1part1=const, t.key2part1=const ) note that imerge(...) describes a usable index_merge plan and it's possible that it will be the best access path. O2. "Create index_merge accesses when possible" Current tree_or() will not create index_merge access when it could create non-index merge access (see DISCARD-IMERGE-3 and its example in the "Problems in the current implementation" section). This will be changed to work as follows: we will create index_merge made for index scans that didn't have their match in the other sel_tree. Ilustrating it with an example: | sel_tree_A | sel_tree_B | A or B | include in index_merge? ------+------------+------------+--------+------------------------ key1 | cond1 | cond2 | condM | no key2 | cond3 | cond4 | NULL | no key3 | cond5 | | | yes, A-side key4 | cond6 | | | yes, A-side key5 | | cond7 | | yes, B-side key6 | | cond8 | | yes, B-side here we assume that - (cond1 OR cond2) did produce a combined range. Not including them in index_merge. - (cond3 OR cond4) didn't produce a usable range (e.g. they were t.key1part1=c1 AND t.key1part2=c1, respectively, and combining them didn't yield any range list) - All other scand didn't have their counterparts, so we'll end up with a SEL_TREE of: range(condM) AND index_merge((cond5 AND cond6),(cond7 AND cond8)) . O4. There is no O4. DISCARD-INDEX-MERGE-4 will remain there. The idea is that although DISCARD-INDEX-MERGE-4 does discard plans, so far we haven seen any complaints that could be attributed to it. If we face the need to lift DISCARD-INDEX-MERGE-4, our answer will be to lift it ,and produce a cross-product: ((key1p OR key2p) AND (key3p OR key4p)) OR ((key5p OR key6p) AND (key7p OR key8p)) = (key1p OR key2p OR key5p OR key6p) AND // this part is currently (key3p OR key4p OR key5p OR key6p) AND // produced (key1p OR key2p OR key5p OR key6p) AND // this part will be added (key3p OR key4p OR key5p OR key6p) //. In order to limit the impact of this combinatorial explosion, we will introduce a rule that we won't generate more than #defined MAX_IMERGE_OPTS options. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): index_merge: fair choice between index_merge union and range access (24)
by worklog-noreply＠askmonty.org 18 Jun '09

18 Jun '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: index_merge: fair choice between index_merge union and range access CREATION DATE..: Tue, 26 May 2009, 12:10 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: Psergey CATEGORY.......: Server-Sprint TASK ID........: 24 (http://askmonty.org/worklog/?tid=24) VERSION........: 9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Thu, 18 Jun 2009, 16:55)=-=- Low Level Design modified. --- /tmp/wklog.24.old.19152 2009-06-18 16:55:00.000000000 +0300 +++ /tmp/wklog.24.new.19152 2009-06-18 16:55:00.000000000 +0300 @@ -141,13 +141,15 @@ Operations on SEL_ARG trees will be modified to produce/process the trees of this kind: + 2.1 New tree_and() ------------------ In order not to lose plans, we'll make these changes: -1. Don't remove index_merge part of the tree. +A1. Don't remove index_merge part of the tree (this will take care of + DISCARD-IMERGE-1 problem) -2. Push range conditions down into index_merge trees that may support them. +A2. Push range conditions down into index_merge trees that may support them. if one tree has range(key1) and the other tree has imerge(key1 OR key2) then perform an equvalent of this operation: @@ -155,8 +157,86 @@ (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) -3. Just as before: if both sel_tree A and sel_tree B have index_merge options, +A3. Just as before: if both sel_tree A and sel_tree B have index_merge options, concatenate them together. -2.2 New tree_or() +2.2 New tree_or() +----------------- +O1. Dont remove non-range plans: + Current tree_or() code will refuse to produce index_merge plans for + conditions like + + "t.key1part2=const OR t.key2part1=const" + + (this is marked as DISCARD-IMERGE-3). This was justifed as the left part of + the AND condition is not usable for range access, and the operation of + tree_and() guaranteed that there was no way it could changed to make a + usable range plan. With new tree_and() and rule A2, this is no longer the + case. For example for this query: + + (t.key1part2=const OR t.key2part1=const) AND t.key1part1=const + + it will construct a + + imerge(t.key1part2=const OR t.key2part1=const), range(t.key1part1=const) + + then tree_and() will apply rule A2 to push the range down into index merge + and after that we'll have: + + range(t.key1part1=const) + imerge( + t.key1part2=const AND t.key1part1=const, + t.key2part1=const + ) + note that imerge(...) describes a usable index_merge plan and it's possible + that it will be the best access path. + +O2. "Create index_merge accesses when possible" + Current tree_or() will not create index_merge access when it could create + non-index merge access (see DISCARD-IMERGE-3 and its example in the "Problems + in the current implementation" section). This will be changed to work as + follows: we will create index_merge made for index scans that didn't have + their match in the other sel_tree. + Ilustrating it with an example: + + | sel_tree_A | sel_tree_B | A or B | include in index_merge? + ------+------------+------------+--------+------------------------ + key1 | cond1 | cond2 | condM | no + key2 | cond3 | cond4 | NULL | no + key3 | cond5 | | | yes, A-side + key4 | cond6 | | | yes, A-side + key5 | | cond7 | | yes, B-side + key6 | | cond8 | | yes, B-side + + here we assume that + - (cond1 OR cond2) did produce a combined range. Not including them in + index_merge. + - (cond3 OR cond4) didn't produce a usable range (e.g. they were + t.key1part1=c1 AND t.key1part2=c1, respectively, and combining them + didn't yield any range list) + - All other scand didn't have their counterparts, so we'll end up with a + SEL_TREE of: + + range(condM) AND index_merge((cond5 AND cond6),(cond7 AND cond8)) + . + +O4. There is no O4. DISCARD-INDEX-MERGE-4 will remain there. The idea is +that although DISCARD-INDEX-MERGE-4 does discard plans, so far we haven +seen any complaints that could be attributed to it. +If we face the need to lift DISCARD-INDEX-MERGE-4, our answer will be to +lift it ,and produce a cross-product: + + ((key1p OR key2p) AND (key3p OR key4p)) + OR + ((key5p OR key6p) AND (key7p OR key8p)) + + = (key1p OR key2p OR key5p OR key6p) AND // this part is currently + (key3p OR key4p OR key5p OR key6p) AND // produced + + (key1p OR key2p OR key5p OR key6p) AND // this part will be added + (key3p OR key4p OR key5p OR key6p) //. + +In order to limit the impact of this combinatorial explosion, we will +introduce a rule that we won't generate more than #defined +MAX_IMERGE_OPTS options. -=-=(Guest - Thu, 18 Jun 2009, 14:56)=-=- Low Level Design modified. --- /tmp/wklog.24.old.15612 2009-06-18 14:56:09.000000000 +0300 +++ /tmp/wklog.24.new.15612 2009-06-18 14:56:09.000000000 +0300 @@ -1 +1,162 @@ +<contents> +1. Current implementation overview +1.1. Problems in the current implementation +2. New implementation +2.1 New tree_and() +2.2 New tree_or() +</contents> + +1. Current implementation overview +================================== +At the moment, range analyzer works as follows: + +SEL_TREE structure represents + + # There are sel_trees, a sel_tree is either range or merge tree + sel_tree = range_tree | imerge_tree + + # a range tree has range access options, possibly for several keys + range_tree = range(key1) AND range(key2) AND ... AND range(keyN); + + # merge tree represents several way to index_merge + imerge_tree = imerge1 AND imerge2 AND ... + + # a way to do index merge == a set to use of different indexes. + imergeX = range_tree1 OR range_tree2 OR .. + where no pair of range_treeX have ranges over the same index. + + + tree_and(A, B) + { + if (both A and B are range trees) + return a range_tree with computed intersection for each range; + if (only one of A and B is a range tree) + return that tree; // DISCARD-IMERGE-1 + // at this point both trees are index_merge trees + return concat_lists( A.imerge1 ... A.imergeN, B.imerge1 ... B.imergeN); + } + + + tree_or(A, B) + { + if (A and B are range trees) + { + R = new range_tree; + for each index i + R.add(range_union(A.range(i), B.range(i))); + + if (R has at least one range access) + return R; + else + { + /* could not build any range accesses. construct index_merge */ + remove non-ranges from A; // DISCARD-IMERGE-2 + remove non-ranges from B; + return new index_merge(A, B); + } + } + else if (A is range tree and B is index_merge tree (or vice versa)) + { + Perform this transformation: + + range_treeA // this is A + OR + (range_treeB_11 OR range_treeB_12 OR ... OR range_treeB_1N) AND + (range_treeB_21 OR range_treeB_22 OR ... OR range_treeB_2N) AND + ... + (range_treeB_K1 OR range_treeB_K2 OR ... OR range_treeB_kN) AND + = + (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND + (range_treeA OR range_treeB_21 OR ... OR range_treeB_2N) AND + ... + (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND + + Now each line represents an index_merge.. + } + else if (both A and B are index_merge trees) + { + Perform this transformation: + + imergeA1 AND imergeA2 AND ... AND imergeAN + OR + imergeB1 AND imergeB2 AND ... AND imergeBN + + -> (discard all imergeA{i=2,3,...} -> // DISCARD-IMERGE-3 + + imergeA1 + OR + imergeB1 AND imergeB2 AND ... AND imergeBN = + + = (combine imergeA1 with each of the imergeB{i} ) = + + combine(imergeA1 OR imergeB1) AND + combine(imergeA1 OR imergeB2) AND + ... AND + combine(imergeA1 OR imergeBN) + } + } + +1.1. Problems in the current implementation +------------------------------------------- +As marked in the code above: + +DISCARD-IMERGE-1 step will cause index_merge option to be discarded when +the WHERE clause has this form: + + (t.key1=c1 OR t.key2=c2) AND t.badkey < c3 + +DISCARD-IMERGE-2 step will cause index_merge option to be discarded when +the WHERE clause has this form (conditions t.badkey may have abritrary form): + + (t.badkey<c1 AND t.key1=c1) OR (t.key1=c2 AND t.badkey < c2) + +DISCARD-IMERGE-3 manifests itself as the following effect: suppose there are +two indexes: + + INDEX i1(col1, col2), + INDEX i2(col1, col3) + +and this WHERE clause: + + col1=c1 AND (col2=c2 OR col3=c3) + +The optimizer will generate the plans that only use the "col1=c1" part. The +right side of the AND will be ignored even if it has good selectivity. + + +2. New implementation +===================== + +<general idea> +* Don't start fighting combinatorial explosion until we've actually got one. +</> + +SEL_TREE structure will be now able to hold both index_merge and range scan +candidates at the same time. That is, + + sel_tree2 = range_tree AND imerge_tree + +where both parts are optional (i.e. can be empty) + +Operations on SEL_ARG trees will be modified to produce/process the trees of +this kind: + +2.1 New tree_and() +------------------ +In order not to lose plans, we'll make these changes: + +1. Don't remove index_merge part of the tree. + +2. Push range conditions down into index_merge trees that may support them. + if one tree has range(key1) and the other tree has imerge(key1 OR key2) + then perform an equvalent of this operation: + + rangeA(key1) AND ( rangeB(key1) OR rangeB(key2)) = + + (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) + +3. Just as before: if both sel_tree A and sel_tree B have index_merge options, + concatenate them together. + +2.2 New tree_or() -=-=(Guest - Sat, 13 Jun 2009, 06:29)=-=- Category updated. --- /tmp/wklog.24.old.25753 2009-06-13 06:29:10.000000000 +0300 +++ /tmp/wklog.24.new.25753 2009-06-13 06:29:10.000000000 +0300 @@ -1 +1 @@ -Server-BackLog +Server-Sprint -=-=(Guest - Sat, 13 Jun 2009, 06:14)=-=- Category updated. --- /tmp/wklog.24.old.24991 2009-06-13 06:14:03.000000000 +0300 +++ /tmp/wklog.24.new.24991 2009-06-13 06:14:03.000000000 +0300 @@ -1 +1 @@ -Server-RawIdeaBin +Server-BackLog -=-=(Psergey - Wed, 03 Jun 2009, 12:09)=-=- Dependency created: 30 now depends on 24 -=-=(Guest - Mon, 01 Jun 2009, 23:30)=-=- High-Level Specification modified. --- /tmp/wklog.24.old.21580 2009-06-01 23:30:06.000000000 +0300 +++ /tmp/wklog.24.new.21580 2009-06-01 23:30:06.000000000 +0300 @@ -64,6 +64,9 @@ * How strict is the limitation on the form of the WHERE? +* Which version should this be based on? 5.1? Which patches are should be in + (google's/percona's/maria/etc?) + * TODO: The optimizer didn't compare costs of index_merge and range before (ok it did but that was done for accesses to different tables). Will there be any possible gotchas here? -=-=(Guest - Wed, 27 May 2009, 14:41)=-=- Category updated. --- /tmp/wklog.24.old.8414 2009-05-27 14:41:43.000000000 +0300 +++ /tmp/wklog.24.new.8414 2009-05-27 14:41:43.000000000 +0300 @@ -1 +1 @@ -Client-BackLog +Server-RawIdeaBin -=-=(Guest - Wed, 27 May 2009, 14:41)=-=- Version updated. --- /tmp/wklog.24.old.8414 2009-05-27 14:41:43.000000000 +0300 +++ /tmp/wklog.24.new.8414 2009-05-27 14:41:43.000000000 +0300 @@ -1 +1 @@ -Server-9.x +9.x -=-=(Guest - Wed, 27 May 2009, 13:59)=-=- Title modified. --- /tmp/wklog.24.old.9498 2009-05-27 13:59:23.000000000 +0300 +++ /tmp/wklog.24.new.9498 2009-05-27 13:59:23.000000000 +0300 @@ -1 +1 @@ -index_merge optimizer: dont discard index_merge union strategies when range is available +index_merge: fair choice between index_merge union and range access -=-=(Guest - Wed, 27 May 2009, 13:59)=-=- Version updated. --- /tmp/wklog.24.old.9498 2009-05-27 13:59:23.000000000 +0300 +++ /tmp/wklog.24.new.9498 2009-05-27 13:59:23.000000000 +0300 @@ -1 +1 @@ -Benchmarks-3.0 +Server-9.x ------------------------------------------------------------ -=-=(View All Progress Notes, 11 total)=-=- http://askmonty.org/worklog/index.pl?tid=24&nolimit=1 DESCRIPTION: Current range optimizer will discard possible index_merge/[sort]union strategies when there is a possible range plan. This action is a part of measures we take to avoid combinatorial explosion of possible range/ index_merge strategies. A bad side effect of this is that for WHERE clauses in form t.key1= 'very-frequent-value' AND (t.key2='rare-value1' OR t.key3='rare-value2') the optimizer will - discard union(key2,key3) in favor of range(key1) - consider costs of using range(key1) and discard that plan also and the overall effect is that possible poor range access will cause possible good index_merge access not to be considered. This WL is to about lifting this limitation at least for some subset of WHERE clauses. HIGH-LEVEL SPECIFICATION: (Not a ready HLS but draft) <contents> Solution overview Limitations TODO </contents> Solution overview ================= The idea is to delay discarding potential index_merge plans until the point where it is really necessary. This way, we won't have to do much changes in the range analyzer, but will be able to keep potential index_merge plan just enough so that it's possible to take it into consideration together with range access plans. Since there are no changes in the optimizer, the ability to consider both range and index_merge options will be limited to WHERE clauses of this form: WHERE := range_cond(key1_1) AND range_cond(key2_1) AND other_cond AND index_merge_OR_cond1(key3_1, key3_2, ...) index_merge_OR_cond2(key4_1, key4_2, ...) where index_merge_OR_cond{N} := (range_cond(keyN_1) OR range_cond(keyN_2) OR ...) range_cond(keyX) := condition that allows to construct range access of keyX and doesn't allow to construct range/index_merge accesses for any keys of the table in question. For such WHERE clauses, the range analyzer will produce SEL_TREE of this form: SEL_TREE( range(key1_1), ... range(key2_1), SEL_IMERGE( (1) SEL_TREE(key3_1}) SEL_TREE(key3_2}) ... ) ... ) which can be used to make a cost-based choice between range and index_merge. Limitations ----------- This will not be a full solution in a sense that the range analyzer will not be able to produce sel_tree (1) if the WHERE clause is specified in other form (e.g. brackets were opened). TODO ---- * is it a problem if there are keys that are referred to both from index_merge and from range access? * How strict is the limitation on the form of the WHERE? * Which version should this be based on? 5.1? Which patches are should be in (google's/percona's/maria/etc?) * TODO: The optimizer didn't compare costs of index_merge and range before (ok it did but that was done for accesses to different tables). Will there be any possible gotchas here? LOW-LEVEL DESIGN: <contents> 1. Current implementation overview 1.1. Problems in the current implementation 2. New implementation 2.1 New tree_and() 2.2 New tree_or() </contents> 1. Current implementation overview ================================== At the moment, range analyzer works as follows: SEL_TREE structure represents # There are sel_trees, a sel_tree is either range or merge tree sel_tree = range_tree | imerge_tree # a range tree has range access options, possibly for several keys range_tree = range(key1) AND range(key2) AND ... AND range(keyN); # merge tree represents several way to index_merge imerge_tree = imerge1 AND imerge2 AND ... # a way to do index merge == a set to use of different indexes. imergeX = range_tree1 OR range_tree2 OR .. where no pair of range_treeX have ranges over the same index. tree_and(A, B) { if (both A and B are range trees) return a range_tree with computed intersection for each range; if (only one of A and B is a range tree) return that tree; // DISCARD-IMERGE-1 // at this point both trees are index_merge trees return concat_lists( A.imerge1 ... A.imergeN, B.imerge1 ... B.imergeN); } tree_or(A, B) { if (A and B are range trees) { R = new range_tree; for each index i R.add(range_union(A.range(i), B.range(i))); if (R has at least one range access) return R; else { /* could not build any range accesses. construct index_merge */ remove non-ranges from A; // DISCARD-IMERGE-2 remove non-ranges from B; return new index_merge(A, B); } } else if (A is range tree and B is index_merge tree (or vice versa)) { Perform this transformation: range_treeA // this is A OR (range_treeB_11 OR range_treeB_12 OR ... OR range_treeB_1N) AND (range_treeB_21 OR range_treeB_22 OR ... OR range_treeB_2N) AND ... (range_treeB_K1 OR range_treeB_K2 OR ... OR range_treeB_kN) AND = (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND (range_treeA OR range_treeB_21 OR ... OR range_treeB_2N) AND ... (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND Now each line represents an index_merge.. } else if (both A and B are index_merge trees) { Perform this transformation: imergeA1 AND imergeA2 AND ... AND imergeAN OR imergeB1 AND imergeB2 AND ... AND imergeBN -> (discard all imergeA{i=2,3,...} -> // DISCARD-IMERGE-3 imergeA1 OR imergeB1 AND imergeB2 AND ... AND imergeBN = = (combine imergeA1 with each of the imergeB{i} ) = combine(imergeA1 OR imergeB1) AND combine(imergeA1 OR imergeB2) AND ... AND combine(imergeA1 OR imergeBN) } } 1.1. Problems in the current implementation ------------------------------------------- As marked in the code above: DISCARD-IMERGE-1 step will cause index_merge option to be discarded when the WHERE clause has this form: (t.key1=c1 OR t.key2=c2) AND t.badkey < c3 DISCARD-IMERGE-2 step will cause index_merge option to be discarded when the WHERE clause has this form (conditions t.badkey may have abritrary form): (t.badkey<c1 AND t.key1=c1) OR (t.key1=c2 AND t.badkey < c2) DISCARD-IMERGE-3 manifests itself as the following effect: suppose there are two indexes: INDEX i1(col1, col2), INDEX i2(col1, col3) and this WHERE clause: col1=c1 AND (col2=c2 OR col3=c3) The optimizer will generate the plans that only use the "col1=c1" part. The right side of the AND will be ignored even if it has good selectivity. 2. New implementation ===================== <general idea> * Don't start fighting combinatorial explosion until we've actually got one. </> SEL_TREE structure will be now able to hold both index_merge and range scan candidates at the same time. That is, sel_tree2 = range_tree AND imerge_tree where both parts are optional (i.e. can be empty) Operations on SEL_ARG trees will be modified to produce/process the trees of this kind: 2.1 New tree_and() ------------------ In order not to lose plans, we'll make these changes: A1. Don't remove index_merge part of the tree (this will take care of DISCARD-IMERGE-1 problem) A2. Push range conditions down into index_merge trees that may support them. if one tree has range(key1) and the other tree has imerge(key1 OR key2) then perform an equvalent of this operation: rangeA(key1) AND ( rangeB(key1) OR rangeB(key2)) = (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) A3. Just as before: if both sel_tree A and sel_tree B have index_merge options, concatenate them together. 2.2 New tree_or() ----------------- O1. Dont remove non-range plans: Current tree_or() code will refuse to produce index_merge plans for conditions like "t.key1part2=const OR t.key2part1=const" (this is marked as DISCARD-IMERGE-3). This was justifed as the left part of the AND condition is not usable for range access, and the operation of tree_and() guaranteed that there was no way it could changed to make a usable range plan. With new tree_and() and rule A2, this is no longer the case. For example for this query: (t.key1part2=const OR t.key2part1=const) AND t.key1part1=const it will construct a imerge(t.key1part2=const OR t.key2part1=const), range(t.key1part1=const) then tree_and() will apply rule A2 to push the range down into index merge and after that we'll have: range(t.key1part1=const) imerge( t.key1part2=const AND t.key1part1=const, t.key2part1=const ) note that imerge(...) describes a usable index_merge plan and it's possible that it will be the best access path. O2. "Create index_merge accesses when possible" Current tree_or() will not create index_merge access when it could create non-index merge access (see DISCARD-IMERGE-3 and its example in the "Problems in the current implementation" section). This will be changed to work as follows: we will create index_merge made for index scans that didn't have their match in the other sel_tree. Ilustrating it with an example: | sel_tree_A | sel_tree_B | A or B | include in index_merge? ------+------------+------------+--------+------------------------ key1 | cond1 | cond2 | condM | no key2 | cond3 | cond4 | NULL | no key3 | cond5 | | | yes, A-side key4 | cond6 | | | yes, A-side key5 | | cond7 | | yes, B-side key6 | | cond8 | | yes, B-side here we assume that - (cond1 OR cond2) did produce a combined range. Not including them in index_merge. - (cond3 OR cond4) didn't produce a usable range (e.g. they were t.key1part1=c1 AND t.key1part2=c1, respectively, and combining them didn't yield any range list) - All other scand didn't have their counterparts, so we'll end up with a SEL_TREE of: range(condM) AND index_merge((cond5 AND cond6),(cond7 AND cond8)) . O4. There is no O4. DISCARD-INDEX-MERGE-4 will remain there. The idea is that although DISCARD-INDEX-MERGE-4 does discard plans, so far we haven seen any complaints that could be attributed to it. If we face the need to lift DISCARD-INDEX-MERGE-4, our answer will be to lift it ,and produce a cross-product: ((key1p OR key2p) AND (key3p OR key4p)) OR ((key5p OR key6p) AND (key7p OR key8p)) = (key1p OR key2p OR key5p OR key6p) AND // this part is currently (key3p OR key4p OR key5p OR key6p) AND // produced (key1p OR key2p OR key5p OR key6p) AND // this part will be added (key3p OR key4p OR key5p OR key6p) //. In order to limit the impact of this combinatorial explosion, we will introduce a rule that we won't generate more than #defined MAX_IMERGE_OPTS options. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): index_merge: fair choice between index_merge union and range access (24)
by worklog-noreply＠askmonty.org 18 Jun '09

18 Jun '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: index_merge: fair choice between index_merge union and range access CREATION DATE..: Tue, 26 May 2009, 12:10 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: Psergey CATEGORY.......: Server-Sprint TASK ID........: 24 (http://askmonty.org/worklog/?tid=24) VERSION........: 9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Thu, 18 Jun 2009, 14:56)=-=- Low Level Design modified. --- /tmp/wklog.24.old.15612 2009-06-18 14:56:09.000000000 +0300 +++ /tmp/wklog.24.new.15612 2009-06-18 14:56:09.000000000 +0300 @@ -1 +1,162 @@ +<contents> +1. Current implementation overview +1.1. Problems in the current implementation +2. New implementation +2.1 New tree_and() +2.2 New tree_or() +</contents> + +1. Current implementation overview +================================== +At the moment, range analyzer works as follows: + +SEL_TREE structure represents + + # There are sel_trees, a sel_tree is either range or merge tree + sel_tree = range_tree | imerge_tree + + # a range tree has range access options, possibly for several keys + range_tree = range(key1) AND range(key2) AND ... AND range(keyN); + + # merge tree represents several way to index_merge + imerge_tree = imerge1 AND imerge2 AND ... + + # a way to do index merge == a set to use of different indexes. + imergeX = range_tree1 OR range_tree2 OR .. + where no pair of range_treeX have ranges over the same index. + + + tree_and(A, B) + { + if (both A and B are range trees) + return a range_tree with computed intersection for each range; + if (only one of A and B is a range tree) + return that tree; // DISCARD-IMERGE-1 + // at this point both trees are index_merge trees + return concat_lists( A.imerge1 ... A.imergeN, B.imerge1 ... B.imergeN); + } + + + tree_or(A, B) + { + if (A and B are range trees) + { + R = new range_tree; + for each index i + R.add(range_union(A.range(i), B.range(i))); + + if (R has at least one range access) + return R; + else + { + /* could not build any range accesses. construct index_merge */ + remove non-ranges from A; // DISCARD-IMERGE-2 + remove non-ranges from B; + return new index_merge(A, B); + } + } + else if (A is range tree and B is index_merge tree (or vice versa)) + { + Perform this transformation: + + range_treeA // this is A + OR + (range_treeB_11 OR range_treeB_12 OR ... OR range_treeB_1N) AND + (range_treeB_21 OR range_treeB_22 OR ... OR range_treeB_2N) AND + ... + (range_treeB_K1 OR range_treeB_K2 OR ... OR range_treeB_kN) AND + = + (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND + (range_treeA OR range_treeB_21 OR ... OR range_treeB_2N) AND + ... + (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND + + Now each line represents an index_merge.. + } + else if (both A and B are index_merge trees) + { + Perform this transformation: + + imergeA1 AND imergeA2 AND ... AND imergeAN + OR + imergeB1 AND imergeB2 AND ... AND imergeBN + + -> (discard all imergeA{i=2,3,...} -> // DISCARD-IMERGE-3 + + imergeA1 + OR + imergeB1 AND imergeB2 AND ... AND imergeBN = + + = (combine imergeA1 with each of the imergeB{i} ) = + + combine(imergeA1 OR imergeB1) AND + combine(imergeA1 OR imergeB2) AND + ... AND + combine(imergeA1 OR imergeBN) + } + } + +1.1. Problems in the current implementation +------------------------------------------- +As marked in the code above: + +DISCARD-IMERGE-1 step will cause index_merge option to be discarded when +the WHERE clause has this form: + + (t.key1=c1 OR t.key2=c2) AND t.badkey < c3 + +DISCARD-IMERGE-2 step will cause index_merge option to be discarded when +the WHERE clause has this form (conditions t.badkey may have abritrary form): + + (t.badkey<c1 AND t.key1=c1) OR (t.key1=c2 AND t.badkey < c2) + +DISCARD-IMERGE-3 manifests itself as the following effect: suppose there are +two indexes: + + INDEX i1(col1, col2), + INDEX i2(col1, col3) + +and this WHERE clause: + + col1=c1 AND (col2=c2 OR col3=c3) + +The optimizer will generate the plans that only use the "col1=c1" part. The +right side of the AND will be ignored even if it has good selectivity. + + +2. New implementation +===================== + +<general idea> +* Don't start fighting combinatorial explosion until we've actually got one. +</> + +SEL_TREE structure will be now able to hold both index_merge and range scan +candidates at the same time. That is, + + sel_tree2 = range_tree AND imerge_tree + +where both parts are optional (i.e. can be empty) + +Operations on SEL_ARG trees will be modified to produce/process the trees of +this kind: + +2.1 New tree_and() +------------------ +In order not to lose plans, we'll make these changes: + +1. Don't remove index_merge part of the tree. + +2. Push range conditions down into index_merge trees that may support them. + if one tree has range(key1) and the other tree has imerge(key1 OR key2) + then perform an equvalent of this operation: + + rangeA(key1) AND ( rangeB(key1) OR rangeB(key2)) = + + (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) + +3. Just as before: if both sel_tree A and sel_tree B have index_merge options, + concatenate them together. + +2.2 New tree_or() -=-=(Guest - Sat, 13 Jun 2009, 06:29)=-=- Category updated. --- /tmp/wklog.24.old.25753 2009-06-13 06:29:10.000000000 +0300 +++ /tmp/wklog.24.new.25753 2009-06-13 06:29:10.000000000 +0300 @@ -1 +1 @@ -Server-BackLog +Server-Sprint -=-=(Guest - Sat, 13 Jun 2009, 06:14)=-=- Category updated. --- /tmp/wklog.24.old.24991 2009-06-13 06:14:03.000000000 +0300 +++ /tmp/wklog.24.new.24991 2009-06-13 06:14:03.000000000 +0300 @@ -1 +1 @@ -Server-RawIdeaBin +Server-BackLog -=-=(Psergey - Wed, 03 Jun 2009, 12:09)=-=- Dependency created: 30 now depends on 24 -=-=(Guest - Mon, 01 Jun 2009, 23:30)=-=- High-Level Specification modified. --- /tmp/wklog.24.old.21580 2009-06-01 23:30:06.000000000 +0300 +++ /tmp/wklog.24.new.21580 2009-06-01 23:30:06.000000000 +0300 @@ -64,6 +64,9 @@ * How strict is the limitation on the form of the WHERE? +* Which version should this be based on? 5.1? Which patches are should be in + (google's/percona's/maria/etc?) + * TODO: The optimizer didn't compare costs of index_merge and range before (ok it did but that was done for accesses to different tables). Will there be any possible gotchas here? -=-=(Guest - Wed, 27 May 2009, 14:41)=-=- Category updated. --- /tmp/wklog.24.old.8414 2009-05-27 14:41:43.000000000 +0300 +++ /tmp/wklog.24.new.8414 2009-05-27 14:41:43.000000000 +0300 @@ -1 +1 @@ -Client-BackLog +Server-RawIdeaBin -=-=(Guest - Wed, 27 May 2009, 14:41)=-=- Version updated. --- /tmp/wklog.24.old.8414 2009-05-27 14:41:43.000000000 +0300 +++ /tmp/wklog.24.new.8414 2009-05-27 14:41:43.000000000 +0300 @@ -1 +1 @@ -Server-9.x +9.x -=-=(Guest - Wed, 27 May 2009, 13:59)=-=- Title modified. --- /tmp/wklog.24.old.9498 2009-05-27 13:59:23.000000000 +0300 +++ /tmp/wklog.24.new.9498 2009-05-27 13:59:23.000000000 +0300 @@ -1 +1 @@ -index_merge optimizer: dont discard index_merge union strategies when range is available +index_merge: fair choice between index_merge union and range access -=-=(Guest - Wed, 27 May 2009, 13:59)=-=- Version updated. --- /tmp/wklog.24.old.9498 2009-05-27 13:59:23.000000000 +0300 +++ /tmp/wklog.24.new.9498 2009-05-27 13:59:23.000000000 +0300 @@ -1 +1 @@ -Benchmarks-3.0 +Server-9.x -=-=(Guest - Tue, 26 May 2009, 13:27)=-=- High-Level Specification modified. --- /tmp/wklog.24.old.305 2009-05-26 13:27:32.000000000 +0300 +++ /tmp/wklog.24.new.305 2009-05-26 13:27:32.000000000 +0300 @@ -1 +1,70 @@ +(Not a ready HLS but draft) +<contents> +Solution overview +Limitations +TODO + +</contents> + +Solution overview +================= +The idea is to delay discarding potential index_merge plans until the point +where it is really necessary. + +This way, we won't have to do much changes in the range analyzer, but will be +able to keep potential index_merge plan just enough so that it's possible to +take it into consideration together with range access plans. + +Since there are no changes in the optimizer, the ability to consider both +range and index_merge options will be limited to WHERE clauses of this form: + + WHERE := range_cond(key1_1) AND + range_cond(key2_1) AND + other_cond AND + index_merge_OR_cond1(key3_1, key3_2, ...) + index_merge_OR_cond2(key4_1, key4_2, ...) + +where + + index_merge_OR_cond{N} := (range_cond(keyN_1) OR + range_cond(keyN_2) OR ...) + + + range_cond(keyX) := condition that allows to construct range access of keyX + and doesn't allow to construct range/index_merge accesses + for any keys of the table in question. + + +For such WHERE clauses, the range analyzer will produce SEL_TREE of this form: + + SEL_TREE( + range(key1_1), + ... + range(key2_1), + SEL_IMERGE( (1) + SEL_TREE(key3_1}) + SEL_TREE(key3_2}) + ... + ) + ... + ) + +which can be used to make a cost-based choice between range and index_merge. + +Limitations +----------- +This will not be a full solution in a sense that the range analyzer will not +be able to produce sel_tree (1) if the WHERE clause is specified in other form +(e.g. brackets were opened). + +TODO +---- +* is it a problem if there are keys that are referred to both from + index_merge and from range access? + +* How strict is the limitation on the form of the WHERE? + +* TODO: The optimizer didn't compare costs of index_merge and range before (ok + it did but that was done for accesses to different tables). Will there be any + possible gotchas here? DESCRIPTION: Current range optimizer will discard possible index_merge/[sort]union strategies when there is a possible range plan. This action is a part of measures we take to avoid combinatorial explosion of possible range/ index_merge strategies. A bad side effect of this is that for WHERE clauses in form t.key1= 'very-frequent-value' AND (t.key2='rare-value1' OR t.key3='rare-value2') the optimizer will - discard union(key2,key3) in favor of range(key1) - consider costs of using range(key1) and discard that plan also and the overall effect is that possible poor range access will cause possible good index_merge access not to be considered. This WL is to about lifting this limitation at least for some subset of WHERE clauses. HIGH-LEVEL SPECIFICATION: (Not a ready HLS but draft) <contents> Solution overview Limitations TODO </contents> Solution overview ================= The idea is to delay discarding potential index_merge plans until the point where it is really necessary. This way, we won't have to do much changes in the range analyzer, but will be able to keep potential index_merge plan just enough so that it's possible to take it into consideration together with range access plans. Since there are no changes in the optimizer, the ability to consider both range and index_merge options will be limited to WHERE clauses of this form: WHERE := range_cond(key1_1) AND range_cond(key2_1) AND other_cond AND index_merge_OR_cond1(key3_1, key3_2, ...) index_merge_OR_cond2(key4_1, key4_2, ...) where index_merge_OR_cond{N} := (range_cond(keyN_1) OR range_cond(keyN_2) OR ...) range_cond(keyX) := condition that allows to construct range access of keyX and doesn't allow to construct range/index_merge accesses for any keys of the table in question. For such WHERE clauses, the range analyzer will produce SEL_TREE of this form: SEL_TREE( range(key1_1), ... range(key2_1), SEL_IMERGE( (1) SEL_TREE(key3_1}) SEL_TREE(key3_2}) ... ) ... ) which can be used to make a cost-based choice between range and index_merge. Limitations ----------- This will not be a full solution in a sense that the range analyzer will not be able to produce sel_tree (1) if the WHERE clause is specified in other form (e.g. brackets were opened). TODO ---- * is it a problem if there are keys that are referred to both from index_merge and from range access? * How strict is the limitation on the form of the WHERE? * Which version should this be based on? 5.1? Which patches are should be in (google's/percona's/maria/etc?) * TODO: The optimizer didn't compare costs of index_merge and range before (ok it did but that was done for accesses to different tables). Will there be any possible gotchas here? LOW-LEVEL DESIGN: <contents> 1. Current implementation overview 1.1. Problems in the current implementation 2. New implementation 2.1 New tree_and() 2.2 New tree_or() </contents> 1. Current implementation overview ================================== At the moment, range analyzer works as follows: SEL_TREE structure represents # There are sel_trees, a sel_tree is either range or merge tree sel_tree = range_tree | imerge_tree # a range tree has range access options, possibly for several keys range_tree = range(key1) AND range(key2) AND ... AND range(keyN); # merge tree represents several way to index_merge imerge_tree = imerge1 AND imerge2 AND ... # a way to do index merge == a set to use of different indexes. imergeX = range_tree1 OR range_tree2 OR .. where no pair of range_treeX have ranges over the same index. tree_and(A, B) { if (both A and B are range trees) return a range_tree with computed intersection for each range; if (only one of A and B is a range tree) return that tree; // DISCARD-IMERGE-1 // at this point both trees are index_merge trees return concat_lists( A.imerge1 ... A.imergeN, B.imerge1 ... B.imergeN); } tree_or(A, B) { if (A and B are range trees) { R = new range_tree; for each index i R.add(range_union(A.range(i), B.range(i))); if (R has at least one range access) return R; else { /* could not build any range accesses. construct index_merge */ remove non-ranges from A; // DISCARD-IMERGE-2 remove non-ranges from B; return new index_merge(A, B); } } else if (A is range tree and B is index_merge tree (or vice versa)) { Perform this transformation: range_treeA // this is A OR (range_treeB_11 OR range_treeB_12 OR ... OR range_treeB_1N) AND (range_treeB_21 OR range_treeB_22 OR ... OR range_treeB_2N) AND ... (range_treeB_K1 OR range_treeB_K2 OR ... OR range_treeB_kN) AND = (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND (range_treeA OR range_treeB_21 OR ... OR range_treeB_2N) AND ... (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND Now each line represents an index_merge.. } else if (both A and B are index_merge trees) { Perform this transformation: imergeA1 AND imergeA2 AND ... AND imergeAN OR imergeB1 AND imergeB2 AND ... AND imergeBN -> (discard all imergeA{i=2,3,...} -> // DISCARD-IMERGE-3 imergeA1 OR imergeB1 AND imergeB2 AND ... AND imergeBN = = (combine imergeA1 with each of the imergeB{i} ) = combine(imergeA1 OR imergeB1) AND combine(imergeA1 OR imergeB2) AND ... AND combine(imergeA1 OR imergeBN) } } 1.1. Problems in the current implementation ------------------------------------------- As marked in the code above: DISCARD-IMERGE-1 step will cause index_merge option to be discarded when the WHERE clause has this form: (t.key1=c1 OR t.key2=c2) AND t.badkey < c3 DISCARD-IMERGE-2 step will cause index_merge option to be discarded when the WHERE clause has this form (conditions t.badkey may have abritrary form): (t.badkey<c1 AND t.key1=c1) OR (t.key1=c2 AND t.badkey < c2) DISCARD-IMERGE-3 manifests itself as the following effect: suppose there are two indexes: INDEX i1(col1, col2), INDEX i2(col1, col3) and this WHERE clause: col1=c1 AND (col2=c2 OR col3=c3) The optimizer will generate the plans that only use the "col1=c1" part. The right side of the AND will be ignored even if it has good selectivity. 2. New implementation ===================== <general idea> * Don't start fighting combinatorial explosion until we've actually got one. </> SEL_TREE structure will be now able to hold both index_merge and range scan candidates at the same time. That is, sel_tree2 = range_tree AND imerge_tree where both parts are optional (i.e. can be empty) Operations on SEL_ARG trees will be modified to produce/process the trees of this kind: 2.1 New tree_and() ------------------ In order not to lose plans, we'll make these changes: 1. Don't remove index_merge part of the tree. 2. Push range conditions down into index_merge trees that may support them. if one tree has range(key1) and the other tree has imerge(key1 OR key2) then perform an equvalent of this operation: rangeA(key1) AND ( rangeB(key1) OR rangeB(key2)) = (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) 3. Just as before: if both sel_tree A and sel_tree B have index_merge options, concatenate them together. 2.2 New tree_or() ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0