List:Commits« Previous MessageNext Message »
From:Olav Sandstaa Date:April 1 2011 9:38am
Subject:Re: bzr commit into mysql-5.5 branch (jorgen.loland:3404) Bug#11882131
View as plain text  
Hi Jørgen,

Thanks for making an alternative fix for this problem. I think the 
solution in this patch is better than the first patch.

I agree with the comments you already have gotten from Tor and I have 
only minor comments (see inline).

OK to push when you have considered Tor's and my comments.

Olav


On 03/28/2011 10:45 AM, Jorgen Loland wrote:
> #At file:///export/home/jl208045/mysql/mysql-5.5-11882131/ based on
> revid:alfranio.correia@stripped
>
>   3404 Jorgen Loland	2011-03-28
>        BUG#11882131: OPTIMIZER CHOOSES FILESORT WHEN REVERSE
>                      INDEX SCAN COULD BE USED
>
>        Consider the following case:
>
>        CREATE TABLE t1 (a INT,KEY (a));
>        INSERT INTO t1 VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10);
>        SELECT DISTINCT a,1 FROM t1 WHERE a<>  1 ORDER BY a DESC;
>
>        This query could have been resolved by GROUP range access
>        if it hadn't been for the descending ordering [1].
>
>        To access this table, covering index scan is first chosen.
>        Later an attempt to avoid sorting is made by calling
>        test_if_skip_sort_order(). Range analysis now decides that
>        GROUP range access is the most efficient access method, but
>        since this access method cannot produce records in
>        descending order, it is scrapped by
>        test_if_skip_sort_order() before concluding that filesort
>        is required after all.
>
>        In this case, test_if_skip_sort_order() fails to check if
>        the descending ordering can be resolved by scanning the
>        covering index in reverse order instead. Because of this,
>        the resulting execution plan is to 1) scan the index and 2)
>        sort the result instead of simply do 1) scan the index in
>        reverse order.
>
>        This patch adds an interesting_order parameter to
>        test_quick_select(). This parameter is ensure that only range

is ensure => ensures

>        access plans that can produce rows in requested order are
>        considered.
>
>        The gains from this change include:
>         1) Optimizer will not spend time to calculate whether or not
>            an unusable range access plan is cheap.
>         2) Before, if two range access plans P1 and P2 were considered,
>            and P1 could produce the requested ordering but P2 could not,
>            P2 would still be returned from test_quick_select() if it was
>            cheaper than P1. test_if_skip_sort_order() would then discard
>            the range access plan as not usable. With this patch, P2 will
>            not be considered, so test_quick_select() will instead return
>            the best *usable* plan P1.
>         3) Due to #2, the aforementioned deficiency in
>            test_if_skip_sort_order() is no longer an issue: If
>            test_quick_select() returns a range access plan, that plan
>            will be able to resolve the requested ordering.
>       @ mysql-test/r/order_by.result
>          BUG#11882131: Changed test output
>       @ sql/item_sum.cc
>          Struct ORDER variable "bool asc" replaced with "enum_order order"
>       @ sql/opt_range.cc
>          Add parameter "interesting_order" to test_quick_select() and make the method
> only consider
>          range access plans that are able to produce rows in requested order. Also
> add variable
>          PARAM::order, defining whether the range access plan needs to produce
> ASC/DESC ordering
>          (or no order)
>       @ sql/opt_range.h
>          Add method QUICK_SELECT_I::reverse_sort_possible().
>       @ sql/sql_lex.cc
>          Struct ORDER variable "bool asc" replaced with "enum_order order"
>       @ sql/sql_parse.cc
>          Struct ORDER variable "bool asc" replaced with "enum_order order"
>       @ sql/sql_select.cc
>          When calling test_quick_select(): define whether ascending/descending
> ordering will be
>          required.
>       @ sql/sql_update.cc
>          Struct ORDER variable "bool asc" replaced with "enum_order order"
>       @ sql/table.h
>          Struct ORDER variable "bool asc" replaced with "enum_order order"
>
>      modified:
>        mysql-test/r/order_by.result
>        sql/item_sum.cc
>        sql/opt_range.cc
>        sql/opt_range.h
>        sql/sql_lex.cc
>        sql/sql_parse.cc
>        sql/sql_select.cc
>        sql/sql_update.cc
>        sql/table.h
>
> === modified file 'sql/opt_range.cc'
> --- a/sql/opt_range.cc	2010-12-29 00:26:31 +0000
> +++ b/sql/opt_range.cc	2011-03-28 08:45:06 +0000
> @@ -695,6 +695,8 @@ public:
>     /* Number of ranges in the last checked tree->key */
>     uint n_ranges;
>     uint8 first_null_comp; /* first null component if any, 0 - otherwise */
> +
> +  ORDER::enum_order order;

Consider adding a short comments for this new member variable.

> === modified file 'sql/opt_range.h'
> --- a/sql/opt_range.h	2010-12-17 12:52:39 +0000
> +++ b/sql/opt_range.h	2011-03-28 08:45:06 +0000
> @@ -278,6 +278,7 @@ public:
>     virtual void range_end() {}
>
>     virtual bool reverse_sorted() = 0;
> +  virtual bool reverse_sort_possible() = 0;

1. Consider making this member function const:

     virtual bool reverse_sort_possible() const = 0;

2. Consider to add doxygen documentation for this member function

>
>
> === modified file 'sql/sql_parse.cc'
> --- a/sql/sql_parse.cc	2011-03-08 17:39:25 +0000
> +++ b/sql/sql_parse.cc	2011-03-28 08:45:06 +0000
> @@ -5688,7 +5688,7 @@ bool add_to_list(THD *thd, SQL_I_List<OR
>       DBUG_RETURN(1);
>     order->item_ptr= item;
>     order->item=&order->item_ptr;
> -  order->asc = asc;
> +  order->order = asc ? ORDER::ORDER_ASC : ORDER::ORDER_DESC;

Minor suggestions:

a. Remve the " " in front of the "="
b. Add ( ) around the "asc ? ... " (I think it makes it easier to read.. 
- but feel free to ignore this)
c. Did you consider changing the last argument to add_to_list() from 
bool to ORDER::enum_order?

>     order->free_me=0;
>     order->used=0;
>     order->counter_used= 0;
>
> === modified file 'sql/sql_select.cc'
> --- a/sql/sql_select.cc	2011-03-16 14:11:20 +0000
> +++ b/sql/sql_select.cc	2011-03-28 08:45:06 +0000
> @@ -2607,8 +2607,9 @@ static ha_rows get_quick_record_count(TH
>     if (select)
>     {
>       select->head=table;
> -    if ((error= select->test_quick_select(thd, *(key_map *)keys,(table_map) 0,
> -                                          limit, 0)) == 1)
> +    error= select->test_quick_select(thd, *(key_map *)keys,(table_map) 0,
> +                                     limit, 0, ORDER::ORDER_NOT_RELEVANT);
> +    if (error == 1)
>         DBUG_RETURN(select->quick->records);
>       if (error == -1)
>       {
> @@ -6580,12 +6581,13 @@ make_join_select(JOIN *join,SQL_SELECT *
>   	    if (sel->cond&&  !sel->cond->fixed)
>   	      sel->cond->quick_fix_field();
>
> -	    if (sel->test_quick_select(thd, tab->keys,
> -				       used_tables&  ~ current_map,
> -				       (join->select_options&
> -					OPTION_FOUND_ROWS ?
> -					HA_POS_ERROR :
> -					join->unit->select_limit_cnt), 0)<  0)
> +            if (sel->test_quick_select(thd, tab->keys,
> +                                       used_tables&  ~ current_map,
> +                                       (join->select_options&
> +                                        OPTION_FOUND_ROWS ?
> +                                        HA_POS_ERROR :
> +                                        join->unit->select_limit_cnt),
> +                                       0, ORDER::ORDER_NOT_RELEVANT)<  0)
>               {
>   	      /*
>   		Before reporting "Impossible WHERE" for the whole query
> @@ -6598,7 +6600,9 @@ make_join_select(JOIN *join,SQL_SELECT *
>                                            (join->select_options&
>                                             OPTION_FOUND_ROWS ?
>                                             HA_POS_ERROR :
> -                                          join->unit->select_limit_cnt),0)<
>  0)
> +                                          join->unit->select_limit_cnt),
> +                                         0, ORDER::ORDER_NOT_RELEVANT)
> +<  0)
>   		DBUG_RETURN(1);			// Impossible WHERE
>               }
>               else
> @@ -12436,7 +12440,8 @@ test_if_quick_select(JOIN_TAB *tab)
>     delete tab->select->quick;
>     tab->select->quick=0;
>     return tab->select->test_quick_select(tab->join->thd, tab->keys,
> -					(table_map) 0, HA_POS_ERROR, 0);
> +                                        (table_map) 0, HA_POS_ERROR, 0,
> +                                        ORDER::ORDER_NOT_RELEVANT);
>   }
>
>
> @@ -13298,7 +13303,8 @@ static int test_if_order_by_key(ORDER *o
>         DBUG_RETURN(0);
>
>       /* set flag to 1 if we can use read-next on key, else to -1 */
> -    flag= ((order->asc == !(key_part->key_part_flag&  HA_REVERSE_SORT)) ?
> +    bool asc_order= (order->order == ORDER::ORDER_ASC);
> +    flag= ((asc_order == !(key_part->key_part_flag&  HA_REVERSE_SORT)) ?
>              1 : -1);
>       if (reverse&&  flag != reverse)
>         DBUG_RETURN(0);
> @@ -13739,8 +13745,8 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
>                                           (tab->join->select_options&
>                                            OPTION_FOUND_ROWS) ?
>                                           HA_POS_ERROR :
> -                                       
> tab->join->unit->select_limit_cnt,0)<=
> -              0)
> +                                        tab->join->unit->select_limit_cnt,
> 0,
> +                                        order->order)<= 0)
>               goto use_filesort;
>   	}
>           ref_key= new_ref_key;
> @@ -13789,7 +13795,7 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
>                                     join->select_options&  OPTION_FOUND_ROWS
> ?
>                                     HA_POS_ERROR :
>                                     join->unit->select_limit_cnt,
> -                                  0);
> +                                  0, order->order);
>         }
>         order_direction= best_key_direction;
>         /*
> @@ -13818,18 +13824,13 @@ check_reverse_order:
>         */
>         if (select->quick->reverse_sorted())
>           goto skipped_filesort;
> -      else
> -      {
> -        int quick_type= select->quick->get_type();
> -        if (quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE ||
> -            quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT ||
> -            quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION ||
> -            quick_type == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX)
> -        {
> -          tab->limit= 0;
> -          goto use_filesort;               // Use filesort
> -        }
> -      }
> +
> +      bool quick_created= (select->quick != save_quick);
> +      /*
> +        test_quick_select() should not create a quick that cannot do
> +        reverse ordering
> +      */
> +      DBUG_ASSERT(!quick_created || select->quick->reverse_sort_possible());

When compiling a non-debug build you will get a warning about 
quick_created not being used here.
Could you move the expression  inside the DBUG_ASSERT instead?

>
>


Thread
bzr commit into mysql-5.5 branch (jorgen.loland:3404) Bug#11882131Jorgen Loland28 Mar
  • Re: bzr commit into mysql-5.5 branch (jorgen.loland:3404) Bug#11882131Tor Didriksen28 Mar
    • Re: bzr commit into mysql-5.5 branch (jorgen.loland:3404) Bug#11882131Olav Sandstaa1 Apr
    • Re: bzr commit into mysql-5.5 branch (jorgen.loland:3404) Bug#11882131Jorgen Loland1 Apr
  • Re: bzr commit into mysql-5.5 branch (jorgen.loland:3404) Bug#11882131Olav Sandstaa1 Apr
    • Re: bzr commit into mysql-5.5 branch (jorgen.loland:3404) Bug#11882131Jorgen Loland1 Apr
      • Re: bzr commit into mysql-5.5 branch (jorgen.loland:3404) Bug#11882131Olav Sandstaa1 Apr