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...
