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