#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
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 'mysql-test/r/order_by.result'
--- a/mysql-test/r/order_by.result 2011-02-07 09:40:42 +0000
+++ b/mysql-test/r/order_by.result 2011-03-28 08:45:06 +0000
@@ -1651,7 +1651,7 @@ 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
+1 SIMPLE t1 index a a 5 NULL 10 Using where; Using index
SELECT DISTINCT a,1 FROM t1 WHERE a <> 1 ORDER BY a DESC;
a 1
10 1
=== modified file 'sql/item_sum.cc'
--- a/sql/item_sum.cc 2011-03-16 14:11:20 +0000
+++ b/sql/item_sum.cc 2011-03-28 08:45:06 +0000
@@ -2894,7 +2894,7 @@ int group_concat_key_cmp_with_order(void
uint offset= (field->offset(field->table->record[0]) -
table->s->null_bytes);
if ((res= field->cmp((uchar*)key1 + offset, (uchar*)key2 + offset)))
- return (*order_item)->asc ? res : -res;
+ return ((*order_item)->order == ORDER::ORDER_ASC) ? res : -res;
}
}
/*
@@ -3435,7 +3435,7 @@ void Item_func_group_concat::print(Strin
if (i)
str->append(',');
orig_args[i + arg_count_field]->print(str, query_type);
- if (order[i]->asc)
+ if (order[i]->order == ORDER::ORDER_ASC)
str->append(STRING_WITH_LEN(" ASC"));
else
str->append(STRING_WITH_LEN(" DESC"));
=== 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;
};
class TABLE_READ_PLAN;
@@ -2147,8 +2149,9 @@ static int fill_used_fields_bitmap(PARAM
*/
int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
- table_map prev_tables,
- ha_rows limit, bool force_quick_range)
+ table_map prev_tables,
+ ha_rows limit, bool force_quick_range,
+ const ORDER::enum_order &interesting_order)
{
uint idx;
double scan_time;
@@ -2204,6 +2207,7 @@ int SQL_SELECT::test_quick_select(THD *t
param.imerge_cost_buff_size= 0;
param.using_real_indexes= TRUE;
param.remove_jump_scans= TRUE;
+ param.order= interesting_order;
thd->no_errors=1; // Don't warn about NULL
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
@@ -2328,10 +2332,12 @@ int SQL_SELECT::test_quick_select(THD *t
/*
Simultaneous key scans and row deletes on several handler
objects are not allowed so don't use ROR-intersection for
- table deletes.
+ table deletes.Also, ROR-intersection cannot return rows in
+ descending order
*/
if ((thd->lex->sql_command != SQLCOM_DELETE) &&
- optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE))
+ optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE) &&
+ interesting_order != ORDER::ORDER_DESC)
{
/*
Get best non-covering ROR-intersection plan and prepare data for
@@ -2355,7 +2361,9 @@ int SQL_SELECT::test_quick_select(THD *t
}
else
{
- if (optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE))
+ // Cannot return rows in descending order.
+ if (optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE) &&
+ interesting_order != ORDER::ORDER_DESC)
{
/* Try creating index_merge/ROR-union scan. */
SEL_IMERGE *imerge;
@@ -4605,6 +4613,9 @@ TRP_ROR_INTERSECT *get_best_ror_intersec
!optimizer_flag(param->thd, OPTIMIZER_SWITCH_INDEX_MERGE_INTERSECT))
DBUG_RETURN(NULL);
+ if (param->order == ORDER::ORDER_DESC)
+ DBUG_RETURN(NULL);
+
/*
Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of
them. Also find and save clustered PK scan if there is one.
@@ -9434,6 +9445,8 @@ get_best_group_min_max(PARAM *param, SEL
DBUG_RETURN(NULL);
if (table->s->keys == 0) /* There are no indexes to use. */
DBUG_RETURN(NULL);
+ if (param->order == ORDER::ORDER_DESC) /* Cannot do reverse ordering */
+ DBUG_RETURN(NULL);
/* Check (SA1,SA4) and store the only MIN/MAX argument - the C attribute.*/
if (join->make_sum_func_list(join->all_fields, join->fields_list, 1))
=== 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;
virtual bool unique_key_range() { return false; }
virtual bool clustered_pk_range() { return false; }
@@ -439,7 +440,8 @@ public:
void range_end();
int get_next_prefix(uint prefix_length, uint group_key_parts,
uchar *cur_prefix);
- bool reverse_sorted() { return 0; }
+ bool reverse_sorted() { return false; }
+ bool reverse_sort_possible() { return true; }
bool unique_key_range();
int init_ror_merged_scan(bool reuse_handler);
void save_last_pos()
@@ -537,6 +539,7 @@ public:
int reset(void);
int get_next();
bool reverse_sorted() { return false; }
+ bool reverse_sort_possible() { return false; }
bool unique_key_range() { return false; }
int get_type() { return QS_TYPE_INDEX_MERGE; }
void add_keys_and_lengths(String *key_names, String *used_lengths);
@@ -614,6 +617,7 @@ public:
int reset(void);
int get_next();
bool reverse_sorted() { return false; }
+ bool reverse_sort_possible() { return false; }
bool unique_key_range() { return false; }
int get_type() { return QS_TYPE_ROR_INTERSECT; }
void add_keys_and_lengths(String *key_names, String *used_lengths);
@@ -684,6 +688,7 @@ public:
int reset(void);
int get_next();
bool reverse_sorted() { return false; }
+ bool reverse_sort_possible() { return false; }
bool unique_key_range() { return false; }
int get_type() { return QS_TYPE_ROR_UNION; }
void add_keys_and_lengths(String *key_names, String *used_lengths);
@@ -825,6 +830,7 @@ public:
int reset();
int get_next();
bool reverse_sorted() { return false; }
+ bool reverse_sort_possible() { return false; }
bool unique_key_range() { return false; }
int get_type() { return QS_TYPE_GROUP_MIN_MAX; }
void add_keys_and_lengths(String *key_names, String *used_lengths);
@@ -845,7 +851,8 @@ class QUICK_SELECT_DESC: public QUICK_RA
public:
QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint used_key_parts);
int get_next();
- bool reverse_sorted() { return 1; }
+ bool reverse_sorted() { return true; }
+ bool reverse_sort_possible() { return true; }
int get_type() { return QS_TYPE_RANGE_DESC; }
QUICK_SELECT_I *make_reverse(uint used_key_parts_arg)
{
@@ -881,7 +888,8 @@ class SQL_SELECT :public Sql_alloc {
{
key_map tmp;
tmp.set_all();
- return test_quick_select(thd, tmp, 0, limit, force_quick_range) < 0;
+ return test_quick_select(thd, tmp, 0, limit, force_quick_range,
+ ORDER::ORDER_NOT_RELEVANT) < 0;
}
inline bool skip_record(THD *thd, bool *skip_record)
{
@@ -889,7 +897,8 @@ class SQL_SELECT :public Sql_alloc {
return thd->is_error();
}
int test_quick_select(THD *thd, key_map keys, table_map prev_tables,
- ha_rows limit, bool force_quick_range);
+ ha_rows limit, bool force_quick_range,
+ const ORDER::enum_order &interesting_order);
};
=== modified file 'sql/sql_lex.cc'
--- a/sql/sql_lex.cc 2011-03-08 17:39:25 +0000
+++ b/sql/sql_lex.cc 2011-03-28 08:45:06 +0000
@@ -2178,7 +2178,7 @@ void st_select_lex::print_order(String *
}
else
(*order->item)->print(str, query_type);
- if (!order->asc)
+ if (order->order == ORDER::ORDER_DESC)
str->append(STRING_WITH_LEN(" desc"));
if (order->next)
str->append(',');
=== 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;
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());
}
}
@@ -13929,7 +13930,7 @@ check_reverse_order:
/*
Cleanup:
We may have both a 'select->quick' and 'save_quick' (original)
- at this point. Delete the one that we wan't use.
+ at this point. Delete the one that we won't use.
*/
skipped_filesort:
@@ -14425,7 +14426,7 @@ SORT_FIELD *make_unireg_sortorder(ORDER
}
else
pos->item= *order->item;
- pos->reverse=! order->asc;
+ pos->reverse= (order->order == ORDER::ORDER_DESC);
}
*length=count;
DBUG_RETURN(sort);
@@ -15162,7 +15163,7 @@ create_distinct_group(THD *thd, Item **r
*/
ord->item= ref_pointer_array;
}
- ord->asc=1;
+ ord->order= ORDER::ORDER_ASC;
*prev=ord;
prev= &ord->next;
}
@@ -15239,7 +15240,7 @@ test_if_subpart(ORDER *a,ORDER *b)
for (; a && b; a=a->next,b=b->next)
{
if ((*a->item)->eq(*b->item,1))
- a->asc=b->asc;
+ a->order= b->order;
else
return 0;
}
=== modified file 'sql/sql_update.cc'
--- a/sql/sql_update.cc 2011-02-21 15:49:03 +0000
+++ b/sql/sql_update.cc 2011-03-28 08:45:06 +0000
@@ -1731,7 +1731,7 @@ loop_end:
/* Make an unique key over the first field to avoid duplicated updates */
bzero((char*) &group, sizeof(group));
- group.asc= 1;
+ group.order= ORDER::ORDER_ASC;
group.item= (Item**) temp_fields.head_ref();
tmp_param->quick_group=1;
=== modified file 'sql/table.h'
--- a/sql/table.h 2011-03-25 09:06:07 +0000
+++ b/sql/table.h 2011-03-28 08:45:06 +0000
@@ -194,7 +194,13 @@ typedef struct st_order {
Item *item_ptr; /* Storage for initial item */
int counter; /* position in SELECT list, correct
only if counter_used is true*/
- bool asc; /* true if ascending */
+ enum enum_order {
+ ORDER_NOT_RELEVANT,
+ ORDER_ASC,
+ ORDER_DESC
+ };
+
+ enum_order order; /* Requested direction of ordering */
bool free_me; /* true if item isn't shared */
bool in_field_list; /* true if in select field list */
bool counter_used; /* parameter was counter of columns */
Attachment: [text/bzr-bundle] bzr/jorgen.loland@oracle.com-20110328084506-64iqa40zsmr5ea7m.bundle
