From: Date: July 15 2008 10:50am Subject: bzr commit into mysql-5.0 branch (kgeorge:2648) Bug#37830 List-Archive: http://lists.mysql.com/commits/49739 X-Bug: 37830 Message-Id: <200807150850.m6F8oeVd023598@magare.gmz> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit #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 <= <= 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#37830: 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:50:08 +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:50:08 +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:50:08 +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:50:08 +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:50:08 +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, ¬_used)) + test_if_order_by_key(order, table, nr, ¬_used, ¬_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, ¬_used))) + if ((flag= test_if_order_by_key(order, table, nr, ¬_used, + ¬_used_bool))) { if (!no_changes) {