List:Commits« Previous MessageNext Message »
From:Jorgen Loland Date:February 16 2011 6:36am
Subject:Re: bzr commit into mysql-trunk branch (ole.john.aske:3622) Bug#57601
View as plain text  
Question:

This is the test case for 59308:

--------------
CREATE TABLE t1 (a INT,KEY (a));
INSERT INTO t1 VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10);

EXPLAIN SELECT DISTINCT a,1 FROM t1 WHERE a <> 1 ORDER BY a DESC;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	t1	index	a	a	5	NULL	10	Using where; Using index; Using filesort

SELECT DISTINCT a,1 FROM t1 WHERE a <> 1 ORDER BY a DESC;
a	1
10	1
9	1
(cut)
2	1
----------------

Looking at the EXPLAIN output, isn't this another example of overly eager 
ordering? The index is able to read a in descending order.

If you agree that this is another case of overly eager ordering, I suggest we 
check if this is an easy cherry to pick. If not, I'm fine with adding another 
bug report.

On 02/09/2011 11:05 AM, Ole John Aske wrote:
> #At file:///net/fimafeng09/export/home/tmp/oleja/mysql/mysql-trunk/ based on
> revid:georgi.kodinov@stripped
>
>   3622 Ole John Aske	2011-02-09
>        Fix for bug#57601 'Optimizer is overly eager to request ordered access.'
>        Previous fix has been rebased from mysql-5.1 to mysql-trunk.
>
>        The essential part of this fix is:
>
>        1) Ensure that JOIN_TAB::sorted is set, and QUICK_RANGE_SELECT::mrr_flags
> contains 'HA_MRR_SORTED'
>           only iff strict ordering is required from the handler - Either as a result
> of the query itself
>           specifying ORDER/GROUP BY, or usage of a QUICK access method which require
> the sources to
>           be ordered (Typical if its internals use ::ha_index_first, _last, _next,
> _prev)
>
>        2) Change calls to handler::ha_index_init() to take its 'sorted' argument
> either directly
>           from JOIN_TAB::sorted or from mrr_flags containing HA_MRR_SORTED.
>
>        In order to implement this, QUICK_SELECT_I::need_sorted_output() had to be
> extended to
>        take a 'bool sort' argument: Where 'sort==false' will enable us to turn off
>        requirement that a QUICK_SELECT_I access method should deliver rows in sorted
>        order. (Similar logic already exists for 'non-quick' access methods.)
>        NOTE: QUICK_SELECT_I::need_sorted_output(sort==false) is only regarded as a
> hint
>        and the different QUICK_SELECT_I methods may still request sorted order from
> the
>        handler if required by their internals.
>
>        Furthermore the function 'disable_sorted_access(JOIN_TAB* join_tab)' has been
>        introduced which collect all the logic for turning of sort requirement.
>       @ mysql-test/r/innodb_mysql_lock2.result
>          Accept changed result order for this (unordered) result set.
>       @ mysql-test/r/partition.result
>          Accept changed result order for this (unordered) result set.
>       @ sql/opt_range.cc
>          Correcly set, and use, HA_MRR_SORTED in order to only request sorted access
>          iff it is required either due to optimizer using ::need_sorted_output(),
>          or the internals of the quick access needing ordered access itself.
>
>          Also added mrr_flags and its mrr relatives to C'tor initializer list.
>          And fixed an issue with missing 'delete quick' + return in case
>          get_quick_select()
>          failed.
>
>      modified:
>        mysql-test/r/innodb_mysql_lock2.result
>        mysql-test/r/partition.result
>        sql/opt_range.cc
>        sql/opt_range.h
>        sql/sql_select.cc
> === modified file 'mysql-test/r/innodb_mysql_lock2.result'
> --- a/mysql-test/r/innodb_mysql_lock2.result	2010-07-19 16:09:51 +0000
> +++ b/mysql-test/r/innodb_mysql_lock2.result	2011-02-09 10:05:47 +0000
> @@ -605,11 +605,11 @@ begin;
>   # Acquire SR metadata lock on t1.
>   select * from t1;
>   i
> +4
>   1
> +5
>   2
>   3
> -4
> -5
>   # Switching to connection 'con1'.
>   # Sending:
>   alter table t1 rebuild partition p0;
>
> === modified file 'mysql-test/r/partition.result'
> --- a/mysql-test/r/partition.result	2011-01-10 16:37:47 +0000
> +++ b/mysql-test/r/partition.result	2011-02-09 10:05:47 +0000
> @@ -1725,9 +1725,9 @@ insert into t1 values (18446744073709551
>   (18446744073709551613), (18446744073709551612);
>   select * from t1;
>   a
> +18446744073709551614
>   18446744073709551612
>   18446744073709551613
> -18446744073709551614
>   18446744073709551615
>   select * from t1 where a = 18446744073709551615;
>   a
> @@ -1735,9 +1735,9 @@ a
>   delete from t1 where a = 18446744073709551615;
>   select * from t1;
>   a
> +18446744073709551614
>   18446744073709551612
>   18446744073709551613
> -18446744073709551614
>   drop table t1;
>   CREATE TABLE t1 (
>   num int(11) NOT NULL, cs int(11) NOT NULL)
>
> === modified file 'sql/opt_range.cc'
> --- a/sql/opt_range.cc	2010-12-29 00:38:59 +0000
> +++ b/sql/opt_range.cc	2011-02-09 10:05:47 +0000
> @@ -1178,7 +1178,9 @@ QUICK_SELECT_I::QUICK_SELECT_I()
>   QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(THD *thd, TABLE *table, uint key_nr,
>                                          bool no_alloc, MEM_ROOT *parent_alloc,
>                                          bool *create_error)
> -  :free_file(0),cur_range(NULL),last_range(0),dont_free(0)
> +  :free_file(0),cur_range(NULL),last_range(0),
> +   mrr_flags(0),mrr_buf_size(0),mrr_buf_desc(NULL),
> +   dont_free(0)
>   {
>     my_bitmap_map *bitmap;
>     DBUG_ENTER("QUICK_RANGE_SELECT::QUICK_RANGE_SELECT");
> @@ -1191,7 +1193,6 @@ QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(T
>
>     /* 'thd' is not accessible in QUICK_RANGE_SELECT::reset(). */
>     mrr_buf_size= thd->variables.read_rnd_buff_size;
> -  mrr_buf_desc= NULL;
>
>     if (!no_alloc&&  !parent_alloc)
>     {
> @@ -1219,17 +1220,24 @@ QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(T
>   }
>
>
> -void QUICK_RANGE_SELECT::need_sorted_output()
> +void QUICK_RANGE_SELECT::need_sorted_output(bool sort)
>   {
> -  if (!(mrr_flags&  HA_MRR_SORTED))
> +  if (sort)
>     {
> -    /*
> -      Native implementation can't produce sorted output. We'll have to
> -      switch to default
> -    */
> -    mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
> +    if (!(mrr_flags&  HA_MRR_SORTED))
> +    {
> +      /*
> +        Native implementation can't produce sorted output. We'll have to
> +        switch to default
> +      */
> +      mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
> +    }
> +    mrr_flags |= HA_MRR_SORTED;
> +  }
> +  else
> +  {
> +    mrr_flags&= ~HA_MRR_SORTED;
>     }
> -  mrr_flags |= HA_MRR_SORTED;
>   }
>
>
> @@ -8705,7 +8713,8 @@ int QUICK_RANGE_SELECT::reset()
>     {
>       if (in_ror_merged_scan)
>        
> head->column_bitmaps_set_no_signal(&column_bitmap,&column_bitmap);
> -    if ((error= file->ha_index_init(index,1)))
> +    bool sorted= (mrr_flags&  HA_MRR_SORTED);
> +    if ((error= file->ha_index_init(index,sorted)))
>           DBUG_RETURN(error);
>     }
>
> @@ -8980,10 +8989,11 @@ int QUICK_RANGE_SELECT::get_next_prefix(
>       last_range->make_min_endpoint(&start_key, prefix_length, keypart_map);
>       last_range->make_max_endpoint(&end_key, prefix_length, keypart_map);
>
> +    bool sorted= (mrr_flags&  HA_MRR_SORTED);
>       result= file->read_range_first(last_range->min_keypart_map
> ?&start_key : 0,
>   				   last_range->max_keypart_map ?&end_key : 0,
>                                      test(last_range->flag&  EQ_RANGE),
> -				   TRUE);
> +				   sorted);
>       if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
>         last_range= 0;			// Stop searching
>
> @@ -9095,6 +9105,7 @@ QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUI
>     */
>     mrr_buf_desc= NULL;
>     mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
> +  mrr_flags |= HA_MRR_SORTED; // 'sorted' as internals use index_last/_prev
>     mrr_buf_size= 0;
>
>
> @@ -10575,12 +10586,19 @@ TRP_GROUP_MIN_MAX::make_quick(PARAM *par
>       if (quick_prefix_records == HA_POS_ERROR)
>         quick->quick_prefix_select= NULL; /* Can't construct a quick select. */
>       else
> +    {
>         /* Make a QUICK_RANGE_SELECT to be used for group prefix retrieval. */
>         quick->quick_prefix_select= get_quick_select(param, param_idx,
>                                                      index_tree,
> -                                                   HA_MRR_USE_DEFAULT_IMPL, 0,
> +                                                   HA_MRR_USE_DEFAULT_IMPL |
> HA_MRR_SORTED,
> +                                                   0,
>                                                      &quick->alloc);
> -
> +      if (!quick->quick_prefix_select)
> +      {
> +        delete quick;
> +        DBUG_RETURN(NULL);
> +      }
> +    }
>       /*
>         Extract the SEL_ARG subtree that contains only ranges for the MIN/MAX
>         attribute, and create an array of QUICK_RANGES to be used by the
> @@ -10976,7 +10994,11 @@ int QUICK_GROUP_MIN_MAX_SELECT::reset(vo
>     DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::reset");
>
>     head->set_keyread(TRUE); /* We need only the key attributes */
> -  if ((result= file->ha_index_init(index,1)))
> +
> +  // Request ordered index access as usage of ::index_last(), ::index_first()
> +  // within QUICK_GROUP_MIN_MAX_SELECT depends on it.
> +  bool sorted= true;
> +  if ((result= file->ha_index_init(index,sorted)))
>       DBUG_RETURN(result);
>     if (quick_prefix_select&&  quick_prefix_select->reset())
>       DBUG_RETURN(1);
>
> === modified file 'sql/opt_range.h'
> --- a/sql/opt_range.h	2010-12-17 12:58:04 +0000
> +++ b/sql/opt_range.h	2011-02-09 10:05:47 +0000
> @@ -285,11 +285,15 @@ public:
>     virtual bool clustered_pk_range() { return false; }
>
>     /*
> -    Request that this quick select produces sorted output. Not all quick
> -    selects can do it, the caller is responsible for calling this function
> -    only for those quick selects that can.
> +    Request that this quick select produces sorted output if 'sort==true'.
> +    Not all quick selects can provide sorted output, the caller is responsible
> +    for calling this function only for those quick selects that can.
> +    Caller is allowed to later cancel its sorted request by setting
> +    'sort==false'. However, the implementation is allowed to provide sorted
> +    output even in this case if benificial, or required by implementation
> +    internals.
>     */
> -  virtual void need_sorted_output() = 0;
> +  virtual void need_sorted_output(bool sort) = 0;
>     enum {
>       QS_TYPE_RANGE = 0,
>       QS_TYPE_INDEX_MERGE = 1,
> @@ -399,7 +403,7 @@ uint quick_range_seq_next(range_seq_t rs
>
>   /*
>     Quick select that does a range scan on a single key. The records are
> -  returned in key order.
> +  returned in key order if ::need_sorted_output(true) has been called.
>   */
>   class QUICK_RANGE_SELECT : public QUICK_SELECT_I
>   {
> @@ -465,7 +469,7 @@ public:
>                        MEM_ROOT *parent_alloc, bool *create_error);
>     ~QUICK_RANGE_SELECT();
>
> -  void need_sorted_output();
> +  void need_sorted_output(bool sort);
>     int init();
>     int reset(void);
>     int get_next();
> @@ -569,7 +573,7 @@ public:
>     ~QUICK_INDEX_MERGE_SELECT();
>
>     int  init();
> -  void need_sorted_output() { DBUG_ASSERT(0); /* Can't do it */ }
> +  void need_sorted_output(bool sort) { DBUG_ASSERT(!sort); /* Can't do it */ }
>     int  reset(void);
>     int  get_next();
>     bool reverse_sorted() { return false; }
> @@ -647,7 +651,7 @@ public:
>     ~QUICK_ROR_INTERSECT_SELECT();
>
>     int  init();
> -  void need_sorted_output() { DBUG_ASSERT(0); /* Can't do it */ }
> +  void need_sorted_output(bool sort) { DBUG_ASSERT(!sort); /* Can't do it */ }
>     int  reset(void);
>     int  get_next();
>     bool reverse_sorted() { return false; }
> @@ -718,7 +722,7 @@ public:
>     ~QUICK_ROR_UNION_SELECT();
>
>     int  init();
> -  void need_sorted_output() { DBUG_ASSERT(0); /* Can't do it */ }
> +  void need_sorted_output(bool sort) { DBUG_ASSERT(!sort); /* Can't do it */ }
>     int  reset(void);
>     int  get_next();
>     bool reverse_sorted() { return false; }
> @@ -860,7 +864,7 @@ public:
>     void adjust_prefix_ranges();
>     bool alloc_buffers();
>     int init();
> -  void need_sorted_output() { /* always do it */ }
> +  void need_sorted_output(bool sort) { /* always do it */ }
>     int reset();
>     int get_next();
>     bool reverse_sorted() { return false; }
>
> === modified file 'sql/sql_select.cc'
> --- a/sql/sql_select.cc	2011-02-08 15:54:12 +0000
> +++ b/sql/sql_select.cc	2011-02-09 10:05:47 +0000
> @@ -1463,7 +1463,7 @@ bool setup_semijoin_dups_elimination(JOI
>              output is not supported.
>           */
>           if (tab->select&&  tab->select->quick)
> -          tab->select->quick->need_sorted_output();
> +          tab->select->quick->need_sorted_output(true);
>
>           /* Calculate key length */
>           keylen= 0;
> @@ -2735,6 +2735,23 @@ JOIN::save_join_tab()
>
>
>   /**
> +  There may be a pending 'sorted' request on the specified
> +  'join_tab' which we now has decided we can ignore.
> +*/
> +static void
> +disable_sorted_access(JOIN_TAB* join_tab)
> +{
> +  DBUG_ENTER("disable_sorted_access");
> +  join_tab->sorted= 0;
> +  if (join_tab->select&&  join_tab->select->quick)
> +  {
> +    join_tab->select->quick->need_sorted_output(false);
> +  }
> +  DBUG_VOID_RETURN;
> +}
> +
> +
> +/**
>     Exec select.
>
>     @todo
> @@ -2913,7 +2930,7 @@ JOIN::exec()
>           curr_join->const_tables != curr_join->tables&&
>           curr_join->best_positions[curr_join->const_tables].sj_strategy
>             != SJ_OPT_LOOSE_SCAN)
> -      curr_join->join_tab[curr_join->const_tables].sorted= 0;
> +     
> disable_sorted_access(&curr_join->join_tab[curr_join->const_tables]);
>       if ((tmp_error= do_select(curr_join, (List<Item>  *) 0, curr_tmp_table,
> 0)))
>       {
>         error= tmp_error;
> @@ -3079,7 +3096,7 @@ JOIN::exec()
>         curr_join->group_list= 0;
>         if (!curr_join->sort_and_group&&
>             curr_join->const_tables != curr_join->tables)
> -        curr_join->join_tab[curr_join->const_tables].sorted= 0;
> +       
> disable_sorted_access(&curr_join->join_tab[curr_join->const_tables]);
>         if (setup_sum_funcs(curr_join->thd, curr_join->sum_funcs) ||
>   	  (tmp_error= do_select(curr_join, (List<Item>  *) 0, curr_tmp_table,
>   				0)))
> @@ -11122,7 +11139,7 @@ make_join_readinfo(JOIN *join, ulonglong
>   {
>     uint i, jcl;
>     bool statistics= test(!(join->select_options&  SELECT_DESCRIBE));
> -  bool sorted= 1;
> +  bool sorted= (join->order || join->group_list);
>     uint first_sjm_table= MAX_TABLES;
>     uint last_sjm_table= MAX_TABLES;
>     DBUG_ENTER("make_join_readinfo");
> @@ -18120,6 +18137,7 @@ join_read_key2(JOIN_TAB *tab, TABLE *tab
>     int error;
>     if (!table->file->inited)
>     {
> +    DBUG_ASSERT(!tab->sorted);  // Don't expect sort req. for single row.
>       table->file->ha_index_init(table_ref->key, tab->sorted);
>     }
>
> @@ -18429,7 +18447,7 @@ join_read_last(JOIN_TAB *tab)
>     tab->read_record.index=tab->index;
>     tab->read_record.record=table->record[0];
>     if (!table->file->inited)
> -    table->file->ha_index_init(tab->index, 1);
> +    table->file->ha_index_init(tab->index, tab->sorted);
>     if ((error=
> tab->table->file->ha_index_last(tab->table->record[0])))
>       return report_error(table, error);
>     return 0;
> @@ -18453,7 +18471,7 @@ join_ft_read_first(JOIN_TAB *tab)
>     TABLE *table= tab->table;
>
>     if (!table->file->inited)
> -    table->file->ha_index_init(tab->ref.key, 1);
> +    table->file->ha_index_init(tab->ref.key, tab->sorted);
>     table->file->ft_init();
>
>     if ((error= table->file->ft_read(table->record[0])))
> @@ -20221,7 +20239,7 @@ check_reverse_order:
>         }
>       }
>       else if (select&&  select->quick)
> -      select->quick->need_sorted_output();
> +      select->quick->need_sorted_output(true);
>
>     } // QEP has been modified
>
>
>
>
>
>

-- 
Jørgen Løland | Senior Software Engineer | +47 73842138
Oracle MySQL
Trondheim, Norway
Thread
bzr commit into mysql-trunk branch (ole.john.aske:3622) Bug#57601Ole John Aske9 Feb
  • Re: bzr commit into mysql-trunk branch (ole.john.aske:3622) Bug#57601Jorgen Loland11 Feb
    • Re: bzr commit into mysql-trunk branch (ole.john.aske:3622) Bug#57601Jorgen Loland16 Mar
  • Re: bzr commit into mysql-trunk branch (ole.john.aske:3622) Bug#57601Jorgen Loland16 Feb
    • Re: bzr commit into mysql-trunk branch (ole.john.aske:3622) Bug#57601Jorgen Loland16 Feb