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
