List: | Commits | « Previous MessageNext Message » | |

From: | Guilhem Bichot | Date: | March 21 2011 9:08pm |

Subject: | Re: bzr commit into mysql-trunk branch (jorgen.loland:3281) | ||

View as plain text |

Hello Jorgen, Jorgen Loland a écrit, Le 21.03.2011 10:01: > #At file:///export/home/jl208045/mysql/wl4800/mysql-next-mr-opt-backporting-wl4800/ > based on revid:guilhem.bichot@stripped> > 3281 Jorgen Loland 2011-03-21 > Fixed two related optimizer tracing bugs. It was assumed that > TABLE_READ_PLAN pointers to SEL_ARGs pointed to the first range > interval when it in fact points to the root node of the SEL_ARG > red-black tree. > === modified file 'sql/opt_range.cc' > --- a/sql/opt_range.cc 2011-03-17 15:49:17 +0000 > +++ b/sql/opt_range.cc 2011-03-21 09:01:05 +0000 > @@ -177,16 +177,45 @@ class RANGE_OPT_PARAM; > > The entire graph is partitioned into "interval lists". > > - An interval list is a sequence of ordered disjoint intervals over the same > - key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally, > - all intervals in the list form an RB-tree, linked via left/right/parent > - pointers. The RB-tree root SEL_ARG object will be further called "root of the > - interval list". > - > + An interval list is a sequence of ordered disjoint intervals over > + the same key part. SEL_ARG are linked via "next" and "prev" pointers > + with NULL as sentinel. > + > In the example pic, there are 4 interval lists: > "kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13". > The vertical lines represent SEL_ARG::next/prev pointers. > > + Additionally, all intervals in the list form a red-black (RB) tree, > + linked via left/right/parent pointers with null_element as sentinel. The > + red-black tree root SEL_ARG object will be further called "root of the > + interval list". > + > + A red-black tree with 7 SEL_ARGs will look similar to what is shown > + below. Left/right/parent pointers are shown while next pointers go from a > + node with number X to the node with number X+1 (and prev in the > + opposite direction): > + > + Root > + +---+ > + | 4 | > + +---+ > + left/ \ right > + __/ \__ > + / \ > + +---+ +---+ > + | 2 | | 6 | > + +---+ +---+ > + left / \ right left / \ right > + | | | | > + +---+ +---+ +---+ +---+ > + | 1 | | 3 | | 5 | | 7 | > + +---+ +---+ +---+ +---+ > + > + In this tree, > + * node0->prev == node7->next == NULL > + * node1->left == node1->right == > + node3->left == ... node7->right == &null_element > + > In an interval list, each member X may have SEL_ARG::next_key_part pointer > pointing to the root of another interval list Y. The pointed interval list > must cover a key part with greater number (i.e. Y->part > X->part). > @@ -204,6 +233,17 @@ class RANGE_OPT_PARAM; > (kp1=2 AND (kp3=11 OR kp3=14)) OR > (kp1=3 AND (kp3=11 OR kp3=14)) thanks for the nice comments! > > + In red-black tree form: > + > + +------------------------------+ > + | kp1=2 AND (kp3=11 OR kp3=14) | > + +------------------------------+ > + / \ > + / \ > + +------------------------+ +--------------------+ > + | kp1 < 1 AND kp2=5 AND | | kp1=3 AND | > + | (kp3=10 OR kp3=12) | | (kp3=11 OR kp3=14) | > + +------------------------+ +--------------------+ This comment "An interval list is a sequence of ordered disjoint intervals over the same key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally, all intervals in the list form an RB-tree" makes me think that each interval list is a red-black tree. And an interval list is only about "the same key part". But your pic says the red-black tree has only 3 nodes, so I get confused... I suspect your pic is right and the old comment is confusing...

Thread | ||
---|---|---|

• bzr commit into mysql-trunk branch (jorgen.loland:3281) | Jorgen Loland | 21 Mar |

• Re: bzr commit into mysql-trunk branch (jorgen.loland:3281) | Guilhem Bichot | 21 Mar |

• Re: bzr commit into mysql-trunk branch (jorgen.loland:3281) | Jorgen Loland | 24 Mar |