bzr commit into mysql-5.0 branch (kgeorge:2648) Bug#730, Bug#37830

[Georgi Kodinov]

#At file:///home/kgeorge/mysql/bzr/B37830-5.0-bugteam/

 2648 Georgi Kodinov	2008-07-15
      Bug#37830: ORDER BY ASC/DESC - no difference
            
      Range scan in descending order for c <= <col> <= c type of
      ranges was ignoring the DESC flag.
      However some engines like InnoDB have the primary key parts 
      as a suffix for every secondary key.
      When such primary key suffix is used for ordering ignoring 
      the DESC is not valid.
      But we generally would like to do this because it's faster.
      Fixed by adding a special flag to QUICK_SELECT_DESC to respect
      reverse ordering and read the EQ_RANGE backwards.
modified:
  mysql-test/r/innodb_mysql.result
  mysql-test/t/innodb_mysql.test
  sql/opt_range.cc
  sql/opt_range.h
  sql/sql_select.cc

per-file messages:
  mysql-test/r/innodb_mysql.result
    Bug#37830: test case
  mysql-test/t/innodb_mysql.test
    Bug#37830: test case
  sql/opt_range.cc
    Bug#730: Implementation of a flag to force reverse read of equal ranges.
  sql/opt_range.h
    Bug#37830: Added a "force reverse read on equal ranges" to 
    range read in descending order
  sql/sql_select.cc
    Bug#37830: Force reverse range read in descending order
    when the primary key suffix of a secondary key is used for ordering.
=== modified file 'mysql-test/r/innodb_mysql.result'
--- a/mysql-test/r/innodb_mysql.result	2008-02-07 07:12:49 +0000
+++ b/mysql-test/r/innodb_mysql.result	2008-07-15 08:45:22 +0000
@@ -1246,4 +1246,19 @@ set global innodb_autoextend_increment=@
 set @my_innodb_commit_concurrency=@@global.innodb_commit_concurrency;
 set global innodb_commit_concurrency=0;
 set global innodb_commit_concurrency=@my_innodb_commit_concurrency;
+CREATE TABLE t1 (a int, b int, c int, PRIMARY KEY (a), KEY t1_b (b))
+ENGINE=InnoDB;
+INSERT INTO t1 (a,b,c) VALUES (1,1,1), (2,1,1), (3,1,1), (4,1,1);
+INSERT INTO t1 (a,b,c) SELECT a+4,b,c FROM t1;
+EXPLAIN SELECT a, b, c FROM t1 WHERE b = 1 ORDER BY a DESC LIMIT 5;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	t1_b	t1_b	5	NULL	4	Using where
+SELECT a, b, c FROM t1 WHERE b = 1 ORDER BY a DESC LIMIT 5;
+a	b	c
+8	1	1
+7	1	1
+6	1	1
+5	1	1
+4	1	1
+DROP TABLE t1;
 End of 5.0 tests

=== modified file 'mysql-test/t/innodb_mysql.test'
--- a/mysql-test/t/innodb_mysql.test	2008-02-07 07:12:49 +0000
+++ b/mysql-test/t/innodb_mysql.test	2008-07-15 08:45:22 +0000
@@ -996,4 +996,22 @@ set @my_innodb_commit_concurrency=@@glob
 set global innodb_commit_concurrency=0;
 set global innodb_commit_concurrency=@my_innodb_commit_concurrency;
 
+#
+# Bug #37830: ORDER BY ASC/DESC - no difference
+#
+
+CREATE TABLE t1 (a int, b int, c int, PRIMARY KEY (a), KEY t1_b (b))
+ ENGINE=InnoDB;
+
+INSERT INTO t1 (a,b,c) VALUES (1,1,1), (2,1,1), (3,1,1), (4,1,1);
+INSERT INTO t1 (a,b,c) SELECT a+4,b,c FROM t1;
+
+# should be range access
+EXPLAIN SELECT a, b, c FROM t1 WHERE b = 1 ORDER BY a DESC LIMIT 5;
+
+# should produce '8 7 6 5 4' for a
+SELECT a, b, c FROM t1 WHERE b = 1 ORDER BY a DESC LIMIT 5;
+
+DROP TABLE t1;
+
 --echo End of 5.0 tests

=== modified file 'sql/opt_range.cc'
--- a/sql/opt_range.cc	2008-03-28 18:02:27 +0000
+++ b/sql/opt_range.cc	2008-07-15 08:45:22 +0000
@@ -7093,8 +7093,11 @@ bool QUICK_RANGE_SELECT::row_in_ranges()
  */
 
 QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q,
-                                     uint used_key_parts_arg)
- : QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
+                                     uint used_key_parts_arg, 
+                                     bool force_reverse_read_arg)
+ : QUICK_RANGE_SELECT(*q), force_reverse_read(force_reverse_read_arg),
+   rev_it(rev_ranges)
+  
 {
   QUICK_RANGE *r;
 
@@ -7124,7 +7127,8 @@ int QUICK_SELECT_DESC::get_next()
    *   - if there is NO_MAX_RANGE, start at the end and move backwards
    *   - if it is an EQ_RANGE, which means that max key covers the entire
    *     key, go directly to the key and read through it (sorting backwards is
-   *     same as sorting forwards)
+   *     same as sorting forwards).
+   *     Note : we can do this only if we're not required to read in order.
    *   - if it is NEAR_MAX, go to the key or next, step back once, and
    *     move backwards
    *   - otherwise (not NEAR_MAX == include the key), go after the key,
@@ -7136,7 +7140,7 @@ int QUICK_SELECT_DESC::get_next()
     int result;
     if (last_range)
     {						// Already read through key
-      result = ((last_range->flag & EQ_RANGE)
+      result = ((last_range->flag & EQ_RANGE) && !force_reverse_read
 		? file->index_next_same(record, (byte*) last_range->min_key,
 					last_range->min_length) :
 		file->index_prev(record));
@@ -7163,7 +7167,7 @@ int QUICK_SELECT_DESC::get_next()
       continue;
     }
 
-    if (last_range->flag & EQ_RANGE)
+    if (last_range->flag & EQ_RANGE && !force_reverse_read)
     {
       result= file->index_read(record, (byte*) last_range->max_key,
                                last_range->max_length, HA_READ_KEY_EXACT);
@@ -7171,6 +7175,7 @@ int QUICK_SELECT_DESC::get_next()
     else
     {
       DBUG_ASSERT(last_range->flag & NEAR_MAX ||
+                  (last_range->flag & EQ_RANGE && force_reverse_read) ||
                   range_reads_after_key(last_range));
       result=file->index_read(record, (byte*) last_range->max_key,
 			      last_range->max_length,

=== modified file 'sql/opt_range.h'
--- a/sql/opt_range.h	2007-02-21 12:07:08 +0000
+++ b/sql/opt_range.h	2008-07-15 08:45:22 +0000
@@ -661,11 +661,18 @@ public:
 class QUICK_SELECT_DESC: public QUICK_RANGE_SELECT
 {
 public:
-  QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint used_key_parts);
+  QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint used_key_parts, 
+                    bool force_reverse_read_arg);
   int get_next();
   bool reverse_sorted() { return 1; }
   int get_type() { return QS_TYPE_RANGE_DESC; }
 private:
+  /*
+    Always read the range in reverse. There storage engine can be such 
+    that primary key parts are appended to the secondary key and we may
+    use this when sorting.
+  */
+  bool force_reverse_read;
   bool range_reads_after_key(QUICK_RANGE *range);
 #ifdef NOT_USED
   bool test_if_null_range(QUICK_RANGE *range, uint used_key_parts);

=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc	2008-05-16 14:05:55 +0000
+++ b/sql/sql_select.cc	2008-07-15 08:45:22 +0000
@@ -12097,6 +12097,7 @@ part_of_refkey(TABLE *table,Field *field
     table		Table to sort
     idx			Index to check
     used_key_parts	Return value for used key parts.
+    pk_used     	Return true if the primary key was also used.
 
 
   NOTES
@@ -12110,14 +12111,14 @@ part_of_refkey(TABLE *table,Field *field
 *****************************************************************************/
 
 static int test_if_order_by_key(ORDER *order, TABLE *table, uint idx,
-				uint *used_key_parts)
+				uint *used_key_parts, bool *pk_used)
 {
   KEY_PART_INFO *key_part,*key_part_end;
   key_part=table->key_info[idx].key_part;
   key_part_end=key_part+table->key_info[idx].key_parts;
   key_part_map const_key_parts=table->const_key_parts[idx];
   int reverse=0;
-  my_bool on_primary_key= FALSE;
+  bool on_primary_key= false;
   DBUG_ENTER("test_if_order_by_key");
 
   for (; order ; order=order->next, const_key_parts>>=1)
@@ -12143,7 +12144,7 @@ static int test_if_order_by_key(ORDER *o
           (table->file->table_flags() & HA_PRIMARY_KEY_IN_READ_INDEX)
&&
           table->s->primary_key != MAX_KEY)
       {
-        on_primary_key= TRUE;
+        on_primary_key= true;
         key_part= table->key_info[table->s->primary_key].key_part;
         key_part_end=key_part+table->key_info[table->s->primary_key].key_parts;
         const_key_parts=table->const_key_parts[table->s->primary_key];
@@ -12172,6 +12173,7 @@ static int test_if_order_by_key(ORDER *o
     reverse=flag;				// Remember if reverse
     key_part++;
   }
+  *pk_used= on_primary_key;
   *used_key_parts= on_primary_key ? table->key_info[idx].key_parts :
     (uint) (key_part - table->key_info[idx].key_part);
   if (reverse == -1 && !(table->file->index_flags(idx, *used_key_parts-1,
1) &
@@ -12250,6 +12252,7 @@ test_if_subkey(ORDER *order, TABLE *tabl
   uint min_length= (uint) ~0;
   uint best= MAX_KEY;
   uint not_used;
+  bool not_used_bool;
   KEY_PART_INFO *ref_key_part= table->key_info[ref].key_part;
   KEY_PART_INFO *ref_key_part_end= ref_key_part + ref_key_parts;
 
@@ -12260,7 +12263,7 @@ test_if_subkey(ORDER *order, TABLE *tabl
 	table->key_info[nr].key_parts >= ref_key_parts &&
 	is_subkey(table->key_info[nr].key_part, ref_key_part,
 		  ref_key_part_end) &&
-	test_if_order_by_key(order, table, nr, &not_used))
+	test_if_order_by_key(order, table, nr, &not_used, &not_used_bool))
     {
       min_length= table->key_info[nr].key_length;
       best= nr;
@@ -12481,6 +12484,7 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
     */
     int order_direction;
     uint used_key_parts;
+    bool pk_used;
     if (!usable_keys.is_set(ref_key))
     {
       /*
@@ -12542,7 +12546,8 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
     /* Check if we get the rows in requested sorted order by using the key */
     if (usable_keys.is_set(ref_key) &&
 	(order_direction = test_if_order_by_key(order,table,ref_key,
-						&used_key_parts)))
+						&used_key_parts,
+                                                &pk_used)))
     {
       if (order_direction == -1)		// If ORDER BY ... DESC
       {
@@ -12563,7 +12568,8 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
             
             /* ORDER BY range_key DESC */
 	    QUICK_SELECT_DESC *tmp=new
QUICK_SELECT_DESC((QUICK_RANGE_SELECT*)(select->quick),
-							 used_key_parts);
+							 used_key_parts,
+                                                         pk_used);
 	    if (!tmp || tmp->error)
 	    {
 	      delete tmp;
@@ -12623,10 +12629,12 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
     for (nr=0; nr < table->s->keys ; nr++)
     {
       uint not_used;
+      bool not_used_bool;
       if (keys.is_set(nr))
       {
 	int flag;
-	if ((flag= test_if_order_by_key(order, table, nr, &not_used)))
+	if ((flag= test_if_order_by_key(order, table, nr, &not_used, 
+                                        &not_used_bool)))
 	{
 	  if (!no_changes)
 	  {