List:Commits« Previous MessageNext Message »
From:igor Date:July 30 2007 6:01am
Subject:bk commit into 5.1 tree (igor:1.2565) BUG#28404
View as plain text  
Below is the list of changes that have just been committed into a local
5.1 repository of igor. When igor does a push these changes will
be propagated to the main repository and, within 24 hours after the
push, to the public repository.
For information on how to access the public repository
see http://dev.mysql.com/doc/mysql/en/installing-source-tree.html

ChangeSet@stripped, 2007-07-29 23:00:56-07:00, igor@stripped +12 -0
  Preliminary patch for bug #28404.

  mysql-test/r/distinct.result@stripped, 2007-07-29 23:00:45-07:00, igor@stripped +4 -4
    Adjusted results for test cases affected fy the fix for bug #28404.

  mysql-test/r/group_by.result@stripped, 2007-07-29 23:00:45-07:00, igor@stripped +1 -1
    Adjusted results for test cases affected fy the fix for bug #28404.

  mysql-test/r/group_min_max.result@stripped, 2007-07-29 23:00:46-07:00, igor@stripped +1 -1
    Adjusted results for test cases affected fy the fix for bug #28404.

  mysql-test/r/innodb.result@stripped, 2007-07-29 23:00:46-07:00, igor@stripped +1 -1
    Adjusted results for test cases affected fy the fix for bug #28404.

  mysql-test/r/merge.result@stripped, 2007-07-29 23:00:46-07:00, igor@stripped +1 -1
    Adjusted results for test cases affected fy the fix for bug #28404.

  mysql-test/r/order_by.result@stripped, 2007-07-29 23:00:46-07:00, igor@stripped +33 -0
    Added a test case for bug #28404.

  mysql-test/r/select_found.result@stripped, 2007-07-29 23:00:46-07:00, igor@stripped +1 -1
    Adjusted results for test cases affected fy the fix for bug #28404.

  mysql-test/r/subselect.result@stripped, 2007-07-29 23:00:46-07:00, igor@stripped +1 -1
    Adjusted results for test cases affected fy the fix for bug #28404.

  mysql-test/t/distinct.test@stripped, 2007-07-29 23:00:46-07:00, igor@stripped +1 -1
    Changed a test case after adding the fix for bug #28404.

  mysql-test/t/order_by.test@stripped, 2007-07-29 23:00:46-07:00, igor@stripped +35 -0
    Added a test case for bug #28404.

  sql/sql_select.cc@stripped, 2007-07-29 23:00:46-07:00, igor@stripped +84 -21
    Preliminary patch for bug #28404.

  sql/sql_select.h@stripped, 2007-07-29 23:00:46-07:00, igor@stripped +1 -0
    Preliminary patch for bug #28404.

diff -Nrup a/mysql-test/r/distinct.result b/mysql-test/r/distinct.result
--- a/mysql-test/r/distinct.result	2007-05-29 05:57:14 -07:00
+++ b/mysql-test/r/distinct.result	2007-07-29 23:00:45 -07:00
@@ -209,16 +209,16 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	t1	index	NULL	PRIMARY	4	NULL	4	Using index
 explain SELECT distinct t1.a from t1 order by a desc limit 1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index	NULL	PRIMARY	4	NULL	4	Using index
+1	SIMPLE	t1	index	NULL	PRIMARY	4	NULL	1	Using index
 explain SELECT distinct a from t3 order by a desc limit 2;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t3	index	NULL	a	5	NULL	204	Using index
+1	SIMPLE	t3	index	NULL	a	5	NULL	2	Using index
 explain SELECT distinct a,b from t3 order by a+1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	204	Using temporary; Using filesort
-explain SELECT distinct a,b from t3 order by a limit 10;
+explain SELECT distinct a,b from t3 order by a limit 2;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t3	index	NULL	a	5	NULL	204	Using temporary
+1	SIMPLE	t3	index	NULL	a	5	NULL	2	Using temporary
 explain SELECT a,b from t3 group by a,b order by a+1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	204	Using temporary; Using filesort
diff -Nrup a/mysql-test/r/group_by.result b/mysql-test/r/group_by.result
--- a/mysql-test/r/group_by.result	2007-06-12 05:10:27 -07:00
+++ b/mysql-test/r/group_by.result	2007-07-29 23:00:45 -07:00
@@ -1144,7 +1144,7 @@ CREATE TABLE t2 (a INT, b INT, KEY(a));
 INSERT INTO t2 VALUES (1, 1), (2, 2), (3,3), (4,4);
 EXPLAIN SELECT a, SUM(b) FROM t2 GROUP BY a LIMIT 2;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t2	index	NULL	a	5	NULL	4	
+1	SIMPLE	t2	index	NULL	a	5	NULL	2	
 EXPLAIN SELECT a, SUM(b) FROM t2 IGNORE INDEX (a) GROUP BY a LIMIT 2;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t2	ALL	NULL	NULL	NULL	NULL	4	Using temporary; Using filesort
diff -Nrup a/mysql-test/r/group_min_max.result b/mysql-test/r/group_min_max.result
--- a/mysql-test/r/group_min_max.result	2007-06-24 19:06:04 -07:00
+++ b/mysql-test/r/group_min_max.result	2007-07-29 23:00:46 -07:00
@@ -2256,7 +2256,7 @@ EXPLAIN SELECT 1 FROM t1 AS t1_outer WHE
 a IN (SELECT max(b) FROM t1 GROUP BY a HAVING a < 2);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1_outer	index	NULL	a	10	NULL	15	Using where; Using index
-2	DEPENDENT SUBQUERY	t1	index	NULL	a	10	NULL	15	Using index
+2	DEPENDENT SUBQUERY	t1	index	NULL	a	10	NULL	1	Using index
 EXPLAIN SELECT 1 FROM t1 AS t1_outer GROUP BY a HAVING 
 a > (SELECT max(b) FROM t1 GROUP BY a HAVING a < 2);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
diff -Nrup a/mysql-test/r/innodb.result b/mysql-test/r/innodb.result
--- a/mysql-test/r/innodb.result	2007-07-21 06:54:08 -07:00
+++ b/mysql-test/r/innodb.result	2007-07-29 23:00:46 -07:00
@@ -947,7 +947,7 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	t1	index	NULL	PRIMARY	4	NULL	#	
 explain select * from t1 order by b;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index	NULL	b	4	NULL	#	
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	#	Using filesort
 explain select * from t1 order by c;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	#	Using filesort
diff -Nrup a/mysql-test/r/merge.result b/mysql-test/r/merge.result
--- a/mysql-test/r/merge.result	2007-06-14 04:19:44 -07:00
+++ b/mysql-test/r/merge.result	2007-07-29 23:00:46 -07:00
@@ -86,7 +86,7 @@ a	b
 19	Testing
 explain select a from t3 order by a desc limit 10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t3	index	NULL	a	4	NULL	1131	Using index
+1	SIMPLE	t3	index	NULL	a	4	NULL	10	Using index
 select a from t3 order by a desc limit 10;
 a
 699
diff -Nrup a/mysql-test/r/order_by.result b/mysql-test/r/order_by.result
--- a/mysql-test/r/order_by.result	2007-04-06 00:45:03 -07:00
+++ b/mysql-test/r/order_by.result	2007-07-29 23:00:46 -07:00
@@ -1073,3 +1073,36 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	t1	const	PRIMARY,b	b	5	const	1	
 1	SIMPLE	t2	ref	a	a	5	const	2	Using where; Using index
 DROP TABLE t1,t2;
+CREATE TABLE t1(
+id int auto_increment PRIMARY KEY, c2 int, c3 int, INDEX k2(c2), INDEX k3(c3));
+INSERT INTO t1 (c2,c3) VALUES
+(31,34),(35,38),(34,31),(32,35),(36,39),
+(11,14),(15,18),(14,11),(12,15),(16,19);
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+SELECT COUNT(*) FROM t1;
+COUNT(*)
+40960
+EXPLAIN SELECT id,c3 FROM t1 WHERE c2=11 ORDER BY c3 LIMIT 20;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index	k2	k3	5	NULL	160	Using where
+EXPLAIN SELECT id,c3 FROM t1 WHERE c2=11 ORDER BY c3 LIMIT 100;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	ref	k2	k2	5	const	5109	Using where; Using filesort
+EXPLAIN SELECT id,c3 FROM t1 WHERE c2 BETWEEN 10 AND 12 ORDER BY c3 LIMIT 100;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	index	k2	k3	5	NULL	400	Using where
+EXPLAIN SELECT id,c3 FROM t1 WHERE c2 BETWEEN 10 AND 12 ORDER BY c3 LIMIT 2000;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	t1	range	k2	k2	5	NULL	9258	Using where; Using filesort
+DROP TABLE t1;
diff -Nrup a/mysql-test/r/select_found.result b/mysql-test/r/select_found.result
--- a/mysql-test/r/select_found.result	2005-03-01 04:47:08 -08:00
+++ b/mysql-test/r/select_found.result	2007-07-29 23:00:46 -07:00
@@ -84,7 +84,7 @@ UNIQUE KEY e_n (email,name)
 EXPLAIN SELECT SQL_CALC_FOUND_ROWS DISTINCT email FROM t2 LEFT JOIN t1  ON kid = t2.id WHERE t1.id IS NULL LIMIT 10;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t1	system	PRIMARY,kid	NULL	NULL	NULL	0	const row not found
-1	SIMPLE	t2	index	NULL	e_n	104	NULL	200	
+1	SIMPLE	t2	index	NULL	e_n	104	NULL	10	
 SELECT SQL_CALC_FOUND_ROWS DISTINCT email FROM t2 LEFT JOIN t1  ON kid = t2.id WHERE t1.id IS NULL LIMIT 10;
 email
 email1
diff -Nrup a/mysql-test/r/subselect.result b/mysql-test/r/subselect.result
--- a/mysql-test/r/subselect.result	2007-06-30 22:50:03 -07:00
+++ b/mysql-test/r/subselect.result	2007-07-29 23:00:46 -07:00
@@ -3419,7 +3419,7 @@ EXPLAIN
 SELECT * FROM t1 WHERE (a,b) = ANY (SELECT a, max(b) FROM t1 GROUP BY a);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	9	Using where
-2	DEPENDENT SUBQUERY	t1	index	NULL	a	8	NULL	9	Using filesort
+2	DEPENDENT SUBQUERY	t1	index	NULL	a	8	NULL	1	Using filesort
 DROP TABLE t1;
 create table t1( f1 int,f2 int);
 insert into t1 values (1,1),(2,2);
diff -Nrup a/mysql-test/t/distinct.test b/mysql-test/t/distinct.test
--- a/mysql-test/t/distinct.test	2007-04-10 06:55:47 -07:00
+++ b/mysql-test/t/distinct.test	2007-07-29 23:00:46 -07:00
@@ -97,7 +97,7 @@ explain SELECT t1.a from t1 group by a o
 explain SELECT distinct t1.a from t1 order by a desc limit 1;
 explain SELECT distinct a from t3 order by a desc limit 2;
 explain SELECT distinct a,b from t3 order by a+1;
-explain SELECT distinct a,b from t3 order by a limit 10;
+explain SELECT distinct a,b from t3 order by a limit 2;
 explain SELECT a,b from t3 group by a,b order by a+1;
 
 drop table t1,t2,t3,t4;
diff -Nrup a/mysql-test/t/order_by.test b/mysql-test/t/order_by.test
--- a/mysql-test/t/order_by.test	2007-06-01 06:49:38 -07:00
+++ b/mysql-test/t/order_by.test	2007-07-29 23:00:46 -07:00
@@ -739,3 +739,38 @@ INSERT INTO t2 VALUES (1,1),(1,2),(2,1),
 EXPLAIN SELECT 1 FROM t1,t2 WHERE t1.b=2 AND t1.a=t2.a ORDER BY t2.b;
 
 DROP TABLE t1,t2;
+
+# End of 5.0
+
+#
+# Bug #28404: query with ORDER BY and ref access
+#
+
+CREATE TABLE t1(
+  id int auto_increment PRIMARY KEY, c2 int, c3 int, INDEX k2(c2), INDEX k3(c3));
+
+INSERT INTO t1 (c2,c3) VALUES
+ (31,34),(35,38),(34,31),(32,35),(36,39),
+ (11,14),(15,18),(14,11),(12,15),(16,19);
+
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+INSERT INTO t1 (c2,c3) SELECT c2,c3 FROM t1;
+
+SELECT COUNT(*) FROM t1;
+
+EXPLAIN SELECT id,c3 FROM t1 WHERE c2=11 ORDER BY c3 LIMIT 20;
+EXPLAIN SELECT id,c3 FROM t1 WHERE c2=11 ORDER BY c3 LIMIT 100;
+EXPLAIN SELECT id,c3 FROM t1 WHERE c2 BETWEEN 10 AND 12 ORDER BY c3 LIMIT 100;
+EXPLAIN SELECT id,c3 FROM t1 WHERE c2 BETWEEN 10 AND 12 ORDER BY c3 LIMIT 2000;
+
+DROP TABLE t1;
diff -Nrup a/sql/sql_select.cc b/sql/sql_select.cc
--- a/sql/sql_select.cc	2007-07-27 01:38:07 -07:00
+++ b/sql/sql_select.cc	2007-07-29 23:00:46 -07:00
@@ -6450,6 +6450,7 @@ void JOIN_TAB::cleanup()
   quick= 0;
   x_free(cache.buff);
   cache.buff= 0;
+  limit= 0;
   if (table)
   {
     if (table->key_read)
@@ -12757,12 +12758,21 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
       DBUG_RETURN(1);			/* No need to sort */
     }
   }
-  else
   {
-    /* check if we can use a key to resolve the group */
-    /* Tables using JT_NEXT are handled here */
+    /*
+      Check whether there is an index compatible with the given order
+      usage of which is cheaper than usage of the ref_key index (ref_key>=0)
+      or a table scan.
+      It may be the case if ORDER/GROUP BY is used with LIMIT.
+    */
     uint nr;
     key_map keys;
+    int flag;
+    double read_time;
+    double fanout= 1;
+    JOIN *join= tab->join;
+    uint tablenr= tab - join->join_tab;
+    ha_rows table_records= table->file->stats.records; 
 
     /* 
       filesort() and join cache are usually faster than reading in 
@@ -12792,29 +12802,82 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
     else
       keys= usable_keys;
 
+    read_time= join->best_positions[tablenr].read_time;
+    for (uint i= tablenr+1; i < join->tables; i++)
+      fanout*= join->best_positions[i].records_read; // fanout is always >= 1
+
     for (nr=0; nr < table->s->keys ; nr++)
     {
-      uint not_used;
+      uint used_key_parts;
       if (keys.is_set(nr))
       {
-	int flag;
-	if ((flag= test_if_order_by_key(order, table, nr, &not_used)))
-	{
-	  if (!no_changes)
-	  {
-	    tab->index=nr;
-	    tab->read_first_record=  (flag > 0 ? join_read_first:
-				      join_read_last);
-	    tab->type=JT_NEXT;	// Read with index_first(), index_next()
-	    if (table->covering_keys.is_set(nr))
-	    {
-	      table->key_read=1;
-	      table->file->extra(HA_EXTRA_KEYREAD);
-	    }
+        if ((flag= test_if_order_by_key(order, table, nr, &used_key_parts)))
+        {
+          if (table->covering_keys.is_set(nr) ||
+              nr == table->s->primary_key &&
+              table->file->primary_key_is_clustered() ||
+              ref_key < 0 && table->force_index &&
+              table->keys_in_use_for_query.is_set(nr))
+            break;
+          if (select_limit != HA_POS_ERROR || join->group)
+          {
+            double rec_per_key;
+            double index_scan_time;
+            KEY *keyinfo= tab->table->key_info+nr;
+            if (select_limit == HA_POS_ERROR)
+              select_limit= table_records; 
+            select_limit= (uint) (select_limit < fanout ?
+                                  1 : select_limit/fanout);
+            /*
+              We assume that each of the tested indexes is not correlated
+              with ref_key. Thus, to select first N records we have to scan
+              N/selectivity(ref_key) index entries. 
+              selectivity(ref_key) = #scanned_records/#table_records =
+              table->quick_condition_rows/table_records.
+              In any case we can't select more than #table_records.
+              N/(table->quick_condition_rows/table_records) > table_records 
+              <=> N > table->quick_condition_rows.
+            */ 
+            if (select_limit > table->quick_condition_rows)
+              select_limit= table_records;
+            else
+              select_limit*= (ha_rows) ((double) table_records/
+                                         table->quick_condition_rows);
+            rec_per_key= keyinfo->rec_per_key[keyinfo->key_parts-1];
+            set_if_bigger(rec_per_key, 1);
+            index_scan_time= select_limit/rec_per_key *
+	                     min(rec_per_key, table->file->scan_time());
+            index_scan_time= select_limit;
+            if (index_scan_time < read_time || join->group)
+              break;
 	  }
-	  DBUG_RETURN(1);
-	}
+	}      
+      }
+    }
+    if (nr < table->s->keys)
+    {
+      if (!no_changes)
+      {
+        tab->index= nr;
+        tab->read_first_record= flag > 0 ? join_read_first:join_read_last;
+        tab->type=JT_NEXT;          // Read with index_first(), index_next()
+        if (table->covering_keys.is_set(nr))
+        {
+          table->key_read=1;
+          table->file->extra(HA_EXTRA_KEYREAD);
+        }
+        table->file->ha_index_or_rnd_end();
+        if (join->select_options & SELECT_DESCRIBE)
+        {
+          tab->ref.key= -1;
+          tab->ref.key_parts= 0;
+          if (tab->select)
+            tab->select->quick= 0;
+          if (select_limit < table_records) 
+            tab->limit= select_limit;
+        }
       }
+      DBUG_RETURN(1);
     }
   }
   DBUG_RETURN(0);				// Can't use index.
@@ -15524,7 +15587,7 @@ static void select_describe(JOIN *join, 
       if (tab->select && tab->select->quick)
         examined_rows= tab->select->quick->records;
       else if (tab->type == JT_NEXT || tab->type == JT_ALL)
-        examined_rows= tab->table->file->records();
+        examined_rows= tab->limit ? tab->limit : tab->table->file->records();
       else
         examined_rows=(ha_rows)join->best_positions[i].records_read; 
  
diff -Nrup a/sql/sql_select.h b/sql/sql_select.h
--- a/sql/sql_select.h	2007-06-30 20:25:44 -07:00
+++ b/sql/sql_select.h	2007-07-29 23:00:46 -07:00
@@ -194,6 +194,7 @@ typedef struct st_join_table {
   enum join_type type;
   bool		cached_eq_ref_table,eq_ref_table,not_used_in_distinct;
   bool		sorted;
+  uint          limit; 
   TABLE_REF	ref;
   JOIN_CACHE	cache;
   JOIN		*join;
Thread
bk commit into 5.1 tree (igor:1.2565) BUG#28404igor30 Jul