MySQL Bugs: #59415: Range analysis should not be done many times for the same index

Bug #59415	Range analysis should not be done many times for the same index
Submitted:	11 Jan 2011 12:50	Modified:	3 May 2011 0:28
Reporter:	Jørgen Løland	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S4 (Feature request)
Version:	5.1, 5.5, trunk	OS:	Any
Assigned to:	Jørgen Løland	CPU Architecture:	Any

Description:
The optimizer often choses to access a table through an index that does not provide the correct ordering for free. To remedy this, the function test_if_skip_sort_order() is called to see if another index is as good as the chosen index and at the same time is able to provide ordering.

This implies that test_if_skip_sort_ordering() goes through a full range analysis (if range access is applicable) to check whether or not another range access plan should be used instead of the currently chosen ref/range access method.

The problem is that if range analysis is performed and it is decided that it is not better than whatever we had, the range analysis will most likely be performed again and again with the same outcome because test_if_skip_sort_order() is called from multiple locations. 

How to repeat:
Code inspection

Suggested fix:
Make sure that if test_if_skip_sort_order() already did range analysis for a certain index, it can skip doing so over again.

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/129048

3527 Jorgen Loland	2011-01-18
      BUG#59415: Range analysis should not be done many times for the
                 same index
      
      The optimizer often choses to access a table through an index 
      that does not provide the correct ordering for free. To remedy 
      this, the function test_if_skip_sort_order() is called to see 
      if another index is as good as the chosen index and at the 
      same time is able to provide ordering.
      
      This implies that test_if_skip_sort_ordering() goes through a 
      full range analysis (if range access is applicable) to check 
      whether or not another range access plan should be used 
      instead of the currently chosen ref/range access method.
      
      The problem is that if range analysis is performed and it is 
      decided that it is not better than whatever we had, the range 
      analysis will most likely be performed again and again with 
      the same outcome because test_if_skip_sort_order() is called 
      from multiple locations.
      
      This patch avoids the unnecessarily repeated range analysis
      described above by introducing key_map 
      JOIN_TAB::quick_order_tested which is checked to see
      if range analysis has already been performed for a given key.
     @ sql/sql_select.h
        Introduce JOIN_TAB::quick_order_tested used to avoid repeated range analysis for the same key in test_if_skip_sort_order()

Noted in 5.6.3 changelog.

For some queries, the optimizer performed range analysis too many
times for the same index.  

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