Didrik,
I think your idea of taking "order direction" into account when considering
range access plans is good. I've committed a new completely different patch for
this bug:
http://lists.mysql.com/commits/133983
On 03/25/2011 02:29 PM, Tor Didriksen wrote:
> On Fri, Mar 18, 2011 at 11:48 AM, Jorgen
> Loland<jorgen.loland@stripped>wrote:
>
>> #At file:///export/home/jl208045/mysql/mysql-5.5-11882131/ based on
>> revid:gkodinov@stripped
>>
>> 3382 Jorgen Loland 2011-03-18
>> 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.
>>
>> With this patch, test_if_skip_sort_order() will try to
>> produce a result in descending order by doing reverse scan
>> on the index in the case that the suggested range access
>> plan cannot be used.
>>
>> Note that even without this patch, reverse index scan would
>> be chosen given that an unusable range access plan was not
>> suggested used.
>>
>> [1] GROUP, INDEX_MERGE, ROR_INTERSECT and ROR_UNION range
>> access methods cannot produce reverse ordering.
>> @ mysql-test/r/order_by.result
>> BUG#11882131: Changed test output
>>
>> modified:
>> mysql-test/r/order_by.result
>> sql/sql_select.cc
>> === 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-18 10:48:27 +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/sql_select.cc'
>> --- a/sql/sql_select.cc 2011-03-16 14:11:20 +0000
>> +++ b/sql/sql_select.cc 2011-03-18 10:48:27 +0000
>> @@ -13827,7 +13827,17 @@ check_reverse_order:
>> quick_type == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX)
>> {
>> tab->limit= 0;
>> - goto use_filesort; // Use filesort
>> + if (select&& select->quick != save_quick)
>> + {
>> + /*
>> + A new quick was created by this function, but it cannot
>>
>
> Actually: by test_quick_select() ??
>
>
>> + produce reverse ordering. Restore save_quick and
>> + continue to check of ordering can be resolved by reverse
>> + scan of best_key index instead.
>> + */
>> + delete select->quick;
>> + select->quick= save_quick;
>>
>
> select->set_quick(save_quick);
>
> But would it be hard to tell test_quick_select() about the ordering
> requirement,
> so that we don't create, and then delete, these quickies? (twice!)
>
>
>
>> + }
>> }
>> }
>> }
>> @@ -13929,7 +13939,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:
>>
>>
>>
>> --
>> MySQL Code Commits Mailing List
>> For list archives: http://lists.mysql.com/commits
>> To unsubscribe:
>> http://lists.mysql.com/commits?unsub=1
>>
>
--
Jørgen Løland | Senior Software Engineer | +47 73842138
Oracle MySQL
Trondheim, Norway
