Bug #57601 Optimizer is overly eager to request ordered access.
Submitted: 20 Oct 2010 13:19 Modified: 21 Apr 2011 1:04
Reporter: Ole John Aske Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S3 (Non-critical)
Version:5.1.52, 5.5, next-mr OS:Any
Assigned to: Ole John Aske
Triage: Triaged: D3 (Medium)

[20 Oct 2010 13:19] Ole John Aske
Description:
MySQL optimizer is overly eager to request ordered access from its storage engines in several situations where an ordered result set isn't really required. This seems to be done under the false assumption that an ordered result set is 'for free' when we anyway are accessing the table through an ordered index (or primary key)

This may be true for some storage engines, but the partitioned storage engine and NDB need to merge results from all partitions in order to provide an ordered result.

For the ongoing 'pushed join' project in MySQL Cluster requesting a sorted resultset will also limit the pushability for some queries. A fix for this problem is therefore critical for the success of this project.

How to repeat:
Based on code inspection and experience from the 'pushed join' project

Suggested fix:
Will commit a proposed patch based on 5.1 mainline.
The same code is present in the 5.5 branch, and I assume the patch can be applied for this branch also.
.. Has not checked against branches > 5.5, but would assume the same for these also.

1)  Ensure that JOIN_TAB::sorted and QUICK_SELECT_I::sorted is requested only when
    strict ordering is required from the handler - Either as a result of the query
    specifying ORDER/GROUP BY, or the handler being a source in a QUICK access
    method which require the sources to be ordered

2a Call handler::ha_index_init(int idx, bool sorted) with 'sorted==false' in any
   access methods requesting a single row (HA_READ_KEY_EXACT)
   (join_read_key(), .....

2b) Else: Always use above 'sorted' attributes as arguments to handler::ha_index_init()
    and other handler methods having a 'bool sorted' argument (::read_range_first())
[20 Oct 2010 13:23] Bugs System
A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/121326

3473 Ole John Aske	2010-10-20
      Proposed fix for bug#57601 'Optimizer is overly eager to request ordered access.'
      
      1)  Ensure that JOIN_TAB::sorted and QUICK_SELECT_I::sorted is requested only when
          strict ordering is required from the handler - Either as a result of the query
          specifying ORDER/GROUP BY, or the handler being a source in a QUICK access
          method which require the sources to be ordered
      
      2a Call handler::ha_index_init(int idx, bool sorted) with 'sorted==false' in any
         access methods requesting a single row (HA_READ_KEY_EXACT)
         (join_read_key(), .....
      
      2b) Else: Always use above 'sorted' attributes as arguments to handler::ha_index_init()
          and other handler methods having a 'bool sorted' argument (::read_range_first())
[20 Oct 2010 13:37] Ole John Aske
Has verified that the same problem is present in next-mr.
[20 Oct 2010 13:54] Bugs System
A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/121334

3227 Ole John Aske	2010-10-20
      Cherry picked proposed fix for bug#57601 into telco.7-0.spj bran
      ch:
      Make the optimizer less eager in requesting ordered access when it is actually not needed.
[2 Feb 2011 15:14] Ole John Aske
There will be a reworked, mysql-trunk based, fix for this bug.
[9 Feb 2011 10:01] Bugs System
A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/130816

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.
[9 Feb 2011 10:04] Ole John Aske
Please disregard previous commit - there will be a now one ASAP ... :-/
[9 Feb 2011 10:06] Bugs System
A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/130818

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.
[21 Apr 2011 1:04] Paul Dubois
Noted in 5.6.3 changelog.

The optimizer sometimes requested ordered access from a storage 
engine when ordered access was not required. 

CHANGESET - http://lists.mysql.com/commits/134106