From: Jorgen Loland
Date: March 24 2011 1:38pm
Subject: Re: bzr commit into mysql-trunk branch (jorgen.loland:3281)
List-Archive: http://lists.mysql.com/commits/133781
Message-Id: <4D8B493E.50704@oracle.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit

This uncovered a misunderstanding (no my part) and a bug. I have committed a 
follow-up patch:

http://lists.mysql.com/commits/133748

On 03/21/2011 10:08 PM, Guilhem Bichot wrote:
> 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...
>

-- 
Jørgen Løland | Senior Software Engineer | +47 73842138
Oracle MySQL
Trondheim, Norway