From: Jorgen Loland
Date: February 16 2011 7:06am
Subject: Re: bzr commit into mysql-trunk branch (ole.john.aske:3622) Bug#57601
List-Archive: http://lists.mysql.com/commits/131369
Message-Id: <4D5B775D.8040408@oracle.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit

A quick hack suggests that it can easily be done:

         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
+         // Do like use_filesort
+         // Todo: handle orig_select_cond as well
+         if (select && select->quick != save_quick)
+         {
+           delete select->quick;
+           select->quick= save_quick;
+           goto check_reverse_order;
+         }
+         // Probably have to handle orig_select_cond as well
         }

This changes the query to not do filesort.

So... New bug or fix here?



On 02/16/2011 07:36 AM, Jorgen Loland wrote:
> 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