List:Commits« Previous MessageNext Message »
From:igor Date:August 1 2007 6:53pm
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-08-01 11:53:22-07:00, igor@stripped +14 -0
  Fixed bug#28404.
  This patch adds cost estimation for the queries with ORDER BY / GROUP BY
  and LIMIT. 
  If there was a ref/range access to the table whose rows were required
  to be ordered in the result set the optimizer always employed this access
  though a scan by a different index that was compatible with the required 
  order could be cheaper to produce the first L rows of the result set.
  Now for such queries the optimizer makes a choice between the cheapest
  ref/range accesses not compatible with the given order and index scans
  compatible with it.

  mysql-test/r/distinct.result@stripped, 2007-08-01 10:13:43-07:00, igor@stripped +4 -4
    Adjusted results for test cases affected fy the fix for bug #28404.

  mysql-test/r/endspace.result@stripped, 2007-08-01 10:13:44-07:00, igor@stripped +1 -1
    Adjusted results for test cases affected fy the fix for bug #28404.

  mysql-test/r/group_by.result@stripped, 2007-08-01 10:13:44-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-08-01 10:13:44-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-08-01 10:13:44-07:00, igor@stripped +1 -1
    Adjusted results for test cases affected fy the fix for bug #28404.

  mysql-test/r/innodb_mysql.result@stripped, 2007-08-01 10:13:44-07:00, igor@stripped +11 -11
    Adjusted results for test cases affected fy the fix for bug #28404.

  mysql-test/r/merge.result@stripped, 2007-08-01 10:13:44-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-08-01 10:13:44-07:00, igor@stripped +55 -0
    Added a test case for bug #28404.

  mysql-test/r/select_found.result@stripped, 2007-08-01 10:13:44-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-08-01 10:13:44-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-08-01 10:13:44-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-08-01 10:13:44-07:00, igor@stripped +37 -0
    Added a test case for bug #28404.

  sql/sql_select.cc@stripped, 2007-08-01 10:13:44-07:00, igor@stripped +131 -22
    Fixed bug#28404.
    This patch adds cost estimation for the queries with ORDER BY / GROUP BY
    and LIMIT. 
    Now for such queries the optimizer makes a choice between the cheapest
    ref/range accesses not compatible with the given order and index scans
    compatible with it.
    
    Modified the function test_if_skip_sort_order to make the above mentioned
    choice cost based. 

  sql/sql_select.h@stripped, 2007-08-01 10:13:45-07:00, igor@stripped +6 -0
    Fixed bug#28404.
    This patch adds cost estimation for the queries with ORDER BY / GROUP BY
    and LIMIT. 
    Added a new field fot the JOIN_TAB structure. 

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-08-01 10:13:43 -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/endspace.result b/mysql-test/r/endspace.result
--- a/mysql-test/r/endspace.result	2007-03-09 06:55:55 -08:00
+++ b/mysql-test/r/endspace.result	2007-08-01 10:13:44 -07:00
@@ -154,7 +154,7 @@ teststring	
 teststring
 explain select * from t1 order by text1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index	NULL	key1	34	NULL	3	
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	Using filesort
 alter table t1 modify text1 char(32) binary not null;
 select * from t1 order by text1;
 text1
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-08-01 10:13:44 -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-08-01 10:13:44 -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-08-01 10:13:44 -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/innodb_mysql.result b/mysql-test/r/innodb_mysql.result
--- a/mysql-test/r/innodb_mysql.result	2007-07-25 13:23:36 -07:00
+++ b/mysql-test/r/innodb_mysql.result	2007-08-01 10:13:44 -07:00
@@ -851,13 +851,13 @@ EXPLAIN SELECT * FROM t1 WHERE b BETWEEN
 id	1
 select_type	SIMPLE
 table	t1
-type	range
+type	index
 possible_keys	bkey
-key	bkey
-key_len	5
+key	PRIMARY
+key_len	4
 ref	NULL
-rows	16
-Extra	Using where; Using index; Using filesort
+rows	32
+Extra	Using where; Using index
 SELECT * FROM t1 WHERE b BETWEEN 1 AND 2 ORDER BY a;
 a	b
 1	2
@@ -946,13 +946,13 @@ EXPLAIN SELECT * FROM t2 WHERE b=1 ORDER
 id	1
 select_type	SIMPLE
 table	t2
-type	ref
+type	index
 possible_keys	bkey
-key	bkey
-key_len	5
-ref	const
-rows	8
-Extra	Using where; Using index; Using filesort
+key	PRIMARY
+key_len	4
+ref	NULL
+rows	16
+Extra	Using where; Using index
 SELECT * FROM t2 WHERE b=1 ORDER BY a;
 a	b	c
 1	1	1
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-08-01 10:13:44 -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-08-01 10:13:44 -07:00
@@ -1073,3 +1073,58 @@ 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),(31,39),
+(11,14),(15,18),(14,11),(12,15),(11,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	88	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	9300	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	316	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	12937	Using where; Using filesort
+SELECT id,c3 FROM t1 WHERE c2=11 ORDER BY c3 LIMIT 20;
+id	c3
+6	14
+16	14
+26	14
+36	14
+46	14
+56	14
+66	14
+76	14
+86	14
+96	14
+106	14
+116	14
+126	14
+136	14
+146	14
+156	14
+166	14
+176	14
+186	14
+196	14
+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-08-01 10:13:44 -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-08-01 10:13:44 -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-08-01 10:13:44 -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-08-01 10:13:44 -07:00
@@ -739,3 +739,40 @@ 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),(31,39),
+ (11,14),(15,18),(14,11),(12,15),(11,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;
+
+SELECT id,c3 FROM t1 WHERE c2=11 ORDER BY c3 LIMIT 20;
+
+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-08-01 10:13:44 -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,22 @@ 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;
+    bool group= join->group && order == join->group_list; 
 
     /* 
       filesort() and join cache are usually faster than reading in 
@@ -12786,35 +12797,133 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR
         This is to allow users to use index in ORDER BY.
       */
       if (table->force_index) 
-	keys.merge(table->keys_in_use_for_query);
+	keys.merge(group ? table->keys_in_use_for_group_by :
+                           table->keys_in_use_for_order_by);
       keys.intersect(usable_keys);
     }
     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;
+          /* 
+            Don't use an index scan with ORDER BY without limit.
+            For GROUP BY without limit always use index scan
+            if there is a suitable index. 
+            Why we hold to this asymmetry hardly can be explained
+            rationally. It's easy to demonstrate that using
+            temporary table + filesort could be cheaper for grouping
+            queries too.
+	  */ 
+          if (select_limit != HA_POS_ERROR || group && ref_key < 0)
+          {
+            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;
+            if (group)
+            {
+              rec_per_key= keyinfo->rec_per_key[used_key_parts-1];
+              set_if_bigger(rec_per_key, 1);
+              /*
+                With a grouping query each group containing on average
+                rec_per_key records produces only one row that will
+                be included into the result set.
+	      */  
+              if (select_limit > table_records/rec_per_key)
+                select_limit= table_records;
+              else
+                select_limit= (ha_rows) (select_limit*rec_per_key);
+            }
+            /* 
+              If tab=tk is not the last joined table tn then to get first
+              L records from the result set we can expect to retrieve
+              only L/fanout(tk,tn) where fanout(tk,tn) says how many
+              rows in the record set on average will match each row tk.
+              Usually our estimates for fanouts are too pessimistic.
+              So the estimate for L/fanout(tk,tn) will be too optimistic
+              and as result we'll choose an index scan when using ref/range
+              access + filesort will be cheaper.
+	    */
+            select_limit= (ha_rows) (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) (select_limit *
+                                       (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);
+            /*
+              Here we take into account the fact that rows are
+              accessed in sequences rec_per_key records in each.
+              Rows in such a sequence are supposed to be ordered
+              by rowid/primary key. When reading the data
+              in a sequence we'll touch not more pages than the
+              table file contains.
+              TODO. Use the formula for a disk sweep sequential access
+              to calculate the cost of accessing data rows for one 
+              index entry.
+	    */
+            index_scan_time= select_limit/rec_per_key *
+	                     min(rec_per_key, table->file->scan_time());
+            if (index_scan_time < read_time || group && ref_key < 0)
+              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 +15633,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-08-01 10:13:45 -07:00
@@ -194,6 +194,12 @@ typedef struct st_join_table {
   enum join_type type;
   bool		cached_eq_ref_table,eq_ref_table,not_used_in_distinct;
   bool		sorted;
+  /* 
+    If it's not 0 the number stored this field indicates that the index
+    scan has been chosen to access the table data and we expect to scan 
+    this number of rows for the table.
+  */ 
+  ha_rows       limit; 
   TABLE_REF	ref;
   JOIN_CACHE	cache;
   JOIN		*join;
Thread
bk commit into 5.1 tree (igor:1.2565) BUG#28404igor1 Aug