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 Loland21 Mar
  • Re: bzr commit into mysql-trunk branch (jorgen.loland:3281)Guilhem Bichot21 Mar
    • Re: bzr commit into mysql-trunk branch (jorgen.loland:3281)Jorgen Loland24 Mar