List:Commits« Previous MessageNext Message »
From:Guilhem Bichot Date:April 5 2011 9:19am
Subject:Re: bzr commit into mysql-trunk branch (jorgen.loland:3285)
View as plain text  
Hello,

Jorgen Loland a écrit, Le 24.03.2011 11:22:
> #At file:///export/home/jl208045/mysql/wl4800/mysql-next-mr-opt-backporting-wl4800/
> based on revid:guilhem.bichot@stripped
> 
>  3285 Jorgen Loland	2011-03-24
>       Fix optimizer tracing in range access plan analysis:
>       
>       Fixed misunderstanding: SEL_ARG::next_key_part does not
>       point to a single SEL_ARG but to the root of a SEL_ARG tree
>        * Old optimizer tracing code that effectively 
>          printed all intervals of the first keypart and appended it
>          with only the root of consecutive keyparts is replaced with
>          recursive function that combines a range over the current
>          keypart with all ranges in consecutive keyparts
>        * Fixed documentation that describes how SEL_ARG red-black
>          trees are structured.
>        * Added test case that used to fail to print all ranges for
>          a range access plan.
>       
>       Bonus: With new understanding of how SEL_ARG R-B trees are 
>       structured, it was possible to:
>        * Remove tracing from sel_arg_range_seq_next() (and all
>          RANGE_SEQ_IF::next() implementations) and step_down_to().
>          This was replaced with tracing of SEL_ARG trees in the 
>          range optimizer.

So good!

>     modified:
>       mysql-test/include/optimizer_trace_range.inc
>       mysql-test/r/optimizer_trace_range_no_prot.result
>       mysql-test/r/optimizer_trace_range_ps_prot.result
>       sql/handler.cc
>       sql/handler.h
>       sql/opt_range.cc
>       sql/opt_range.h
>       sql/sql_join_cache.cc

> === modified file 'sql/opt_range.cc'
> --- a/sql/opt_range.cc	2011-03-21 20:50:40 +0000
> +++ b/sql/opt_range.cc	2011-03-24 10:21:59 +0000
> @@ -235,15 +235,28 @@ class RANGE_OPT_PARAM;
>  
>    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) |
> -         +------------------------+    +--------------------+
> +                     +-------+                 +--------+
> +                     | kp1=2 |.................| kp3=14 |
> +                     +-------+                 +--------+
> +                      /     \                     /
> +             +---------+    +-------+     +--------+
> +             | kp1 < 1 |    | kp1=3 |     | kp3=11 |
> +             +---------+    +-------+     +--------+
> +                 .               .
> +            ......               .......
> +            .                          .
> +        +-------+                  +--------+
> +        | kp2=5 |                  | kp3=14 |
> +        +-------+                  +--------+
> +            .                        /
> +            .                   +--------+
> +       (root of R-B tree        | kp3=11 |
> +        for "kp3={10|12}")      +--------+
> +
> +
> +  Where / and \ denote left and right pointers and ... denotes
> +  next_key_part pointers to the root of the R-B tree of intervals for
> +  consecutive key parts.
>  
>    3. SEL_ARG GRAPH USE
>  
> @@ -372,6 +385,7 @@ public:
>    SEL_ARG *left,*right;   /* R-B tree children */
>    SEL_ARG *next,*prev;    /* Links for bi-directional interval list */
>    SEL_ARG *parent;        /* R-B tree parent */
> +  /*  R-B tree root of intervals covering consecutive keyparts */

In the picture above, when I look at intervals in one RB-tree, each 
interval is about a single keypart, not about consecutive keyparts:
I see this RB-tree: kp3=14 - kp3=11,
this other RB-tree: kp1=2 - kp1 < 1 - kp1 = 3
this other RB-tree: kp3=4 - kp3=11,
this other RB-tree: kp3={10,12}...
each of them is about a single keypart.
So I think the one-line comment should be clarified: maybe it means that 
next_key_part is about a keypart consecutive of this SEL_ARG's keypart?

>    SEL_ARG *next_key_part; 
>    enum leaf_color { BLACK,RED } color;
>    enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;

> +/**
> +  Traverse an R-B tree of range conditions and append all ranges for this
> +  keypart and consecutive keyparts to the optimizer trace. See
> +  description of R-B trees/SEL_ARG for details on how ranges are
> +  linked.
> +
> +  @param[in,out] trace_range   Optimizer trace object ranges are appended to

s/object/array

> +  @param[in]     range_so_far  String containing ranges for keyparts prior
> +                               to this keypart.
> +  @param[in]     keypart_root  The root of the R-B tree containing intervals
> +                               for this keypart.
> +  @param[in]     key_part      Index components description, used when adding
> +                               information to the optimizer trace

looks like key_part describes several key_part-s? if so, I'd name it 
key_parts.

> +*/
> +static void trace_range_all_keyparts(Opt_trace_array &trace_range,
> +                                     const String &range_so_far,

Coding style says:
"    * Never pass parameters with the &variable_name construct in C++. 
Always use a pointer instead!

The reason is that the above makes it much harder for the one reading 
the caller function code to know what is happening and what kind of code 
the compiler is generating for the call. "

> +                                     SEL_ARG *keypart_root,

can this one be a const pointer?

> +                                     const KEY_PART_INFO *key_part)
> +{
> +  DBUG_ASSERT(keypart_root && keypart_root != &null_element);
> +
> +  // Navigate to first interval in red-black tree
> +  const KEY_PART_INFO *cur_key_part= key_part + keypart_root->part;
> +  SEL_ARG *keypart_range= keypart_root->first();
> +
> +  while (keypart_range)
> +  {
> +    String range_cur_keypart= String(range_so_far);
> +    // Append the current range to the range String
> +    append_range(&range_cur_keypart, cur_key_part,
> +                 keypart_range->min_value, keypart_range->max_value,
> +                 keypart_range->min_flag | keypart_range->max_flag);
> +
> +    if (keypart_range->next_key_part)
> +    {
> +      // Not done - there are ranges in consecutive keyparts as well
> +      trace_range_all_keyparts(trace_range, range_cur_keypart,
> +                               keypart_range->next_key_part, key_part);
> +    }
> +    else
> +    {
> +      /*
> +        This is the last keypart with a range. Print full range
> +        info to the optimizer trace
> +      */
> +      trace_range.add_utf8(range_cur_keypart.ptr(),
> +                           range_cur_keypart.length());
> +    }
> +    keypart_range= keypart_range->next;
> +  }
> +
> +}
> +
>  #endif //OPTIMIZER_TRACE

Ok to push.
Thread
bzr commit into mysql-trunk branch (jorgen.loland:3285) Jorgen Loland24 Mar
  • Re: bzr commit into mysql-trunk branch (jorgen.loland:3285)Guilhem Bichot5 Apr
    • Re: bzr commit into mysql-trunk branch (jorgen.loland:3285)Jorgen Loland6 Apr
      • Re: bzr commit into mysql-trunk branch (jorgen.loland:3285)Guilhem Bichot7 Apr
        • Re: bzr commit into mysql-trunk branch (jorgen.loland:3285)Jorgen Loland7 Apr