From: Jorgen Loland
Date: March 28 2011 8:47am
Subject: Re: bzr commit into mysql-5.5 branch (jorgen.loland:3382) Bug#11882131
List-Archive: http://lists.mysql.com/commits/133984
Message-Id: <4D904B08.7090906@oracle.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit

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=didrik@stripped
>>
>

-- 
Jørgen Løland | Senior Software Engineer | +47 73842138
Oracle MySQL
Trondheim, Norway