Applied Monty corrections to the FULL SCAN

optimiser bug patch.


mysql-test/r/distinct.result:
  test results reverted
mysql-test/r/order_by.result:
  test results reverted
sql/sql_select.cc:
  found_constrain renamed to found_constraint
  We don't perform full cartesian product in 
  case when JOIN BUFFER is used: it was taken
  into account.
  s->read_time may contain range index read time,
  so to get full table scan time is necessary to
  call s->table->file->scan_time().

3 files changed, 43 insertions, 32 deletions

diff --git a/mysql-test/r/distinct.result b/mysql-test/r/distinct.result
index 9fcb001de2c..a0343f13394 100644
--- a/mysql-test/r/distinct.result
+++ b/mysql-test/r/distinct.result
@@ -173,9 +173,9 @@ INSERT INTO t2 values (1),(2),(3);
 INSERT INTO t3 VALUES (1,'1'),(2,'2'),(1,'1'),(2,'2');
 explain SELECT distinct t3.a FROM t3,t2,t1 WHERE t3.a=t1.b AND t1.a=t2.a;
 table	type	possible_keys	key	key_len	ref	rows	Extra
-t2	index	a	a	4	NULL	5	Using index; Using temporary
-t1	eq_ref	PRIMARY	PRIMARY	4	t2.a	1	
-t3	index	a	a	5	NULL	5	Using where; Using index
+t3	index	a	a	5	NULL	6	Using index; Using temporary
+t2	index	a	a	4	NULL	5	Using index; Distinct
+t1	eq_ref	PRIMARY	PRIMARY	4	t2.a	1	Using where; Distinct
 SELECT distinct t3.a FROM t3,t2,t1 WHERE t3.a=t1.b AND t1.a=t2.a;
 a
 1
diff --git a/mysql-test/r/order_by.result b/mysql-test/r/order_by.result
index 64fac8af872..58f4972d08f 100644
--- a/mysql-test/r/order_by.result
+++ b/mysql-test/r/order_by.result
@@ -307,17 +307,17 @@ table	type	possible_keys	key	key_len	ref	rows	Extra
 t1	range	a	a	9	NULL	8	Using where; Using index
 explain select * from t1 where a = 2 and b >0 order by a desc,b desc;
 table	type	possible_keys	key	key_len	ref	rows	Extra
-t1	range	a	a	9	NULL	4	Using where; Using index
+t1	range	a	a	9	NULL	5	Using where; Using index
 explain select * from t1 where a = 2 and b is null order by a desc,b desc;
 table	type	possible_keys	key	key_len	ref	rows	Extra
 t1	ref	a	a	9	const,const	1	Using where; Using index; Using filesort
 explain select * from t1 where a = 2 and (b is null or b > 0) order by a
 desc,b desc;
 table	type	possible_keys	key	key_len	ref	rows	Extra
-t1	range	a	a	9	NULL	5	Using where; Using index
+t1	range	a	a	9	NULL	6	Using where; Using index
 explain select * from t1 where a = 2 and b > 0 order by a desc,b desc;
 table	type	possible_keys	key	key_len	ref	rows	Extra
-t1	range	a	a	9	NULL	4	Using where; Using index
+t1	range	a	a	9	NULL	5	Using where; Using index
 explain select * from t1 where a = 2 and b < 2 order by a desc,b desc;
 table	type	possible_keys	key	key_len	ref	rows	Extra
 t1	range	a	a	9	NULL	2	Using where; Using index
@@ -466,8 +466,8 @@ t2	eq_ref	PRIMARY,uid	PRIMARY	4	t1.gid	1
 t3	eq_ref	PRIMARY	PRIMARY	2	t2.uid	1	Using where; Using index
 EXPLAIN SELECT t1.gid, t3.uid from t1, t3 where t1.gid = t3.uid order by t1.gid,t3.skr;
 table	type	possible_keys	key	key_len	ref	rows	Extra
-t1	index	PRIMARY	PRIMARY	4	NULL	6	Using index
-t3	eq_ref	PRIMARY	PRIMARY	2	t1.gid	1	Using where
+t3	ALL	PRIMARY	NULL	NULL	NULL	6	Using temporary; Using filesort
+t1	eq_ref	PRIMARY	PRIMARY	4	t3.uid	1	Using where; Using index
 EXPLAIN SELECT t1.gid, t2.sid, t3.uid from t2, t1, t3 where t2.gid = t1.gid and t2.uid = t3.uid order by t3.uid, t1.gid;
 table	type	possible_keys	key	key_len	ref	rows	Extra
 t1	index	PRIMARY	PRIMARY	4	NULL	6	Using index; Using temporary; Using filesort
@@ -475,8 +475,8 @@ t2	eq_ref	PRIMARY,uid	PRIMARY	4	t1.gid	1
 t3	eq_ref	PRIMARY	PRIMARY	2	t2.uid	1	Using where; Using index
 EXPLAIN SELECT t1.gid, t3.uid from t1, t3 where t1.gid = t3.uid order by t3.skr,t1.gid;
 table	type	possible_keys	key	key_len	ref	rows	Extra
-t1	index	PRIMARY	PRIMARY	4	NULL	6	Using index; Using temporary; Using filesort
-t3	eq_ref	PRIMARY	PRIMARY	2	t1.gid	1	Using where
+t3	ALL	PRIMARY	NULL	NULL	NULL	6	Using temporary; Using filesort
+t1	eq_ref	PRIMARY	PRIMARY	4	t3.uid	1	Using where; Using index
 EXPLAIN SELECT t1.gid, t3.uid from t1, t3 where t1.skr = t3.uid order by t1.gid,t3.skr;
 table	type	possible_keys	key	key_len	ref	rows	Extra
 t1	ALL	NULL	NULL	NULL	NULL	6	Using temporary; Using filesort
diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index d537dccc5a6..53c41482a36 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -1898,7 +1898,7 @@ find_best(JOIN *join,table_map rest_tables,uint idx,double record_count,
       best=best_time=records=DBL_MAX;
       KEYUSE *best_key=0;
       uint best_max_key_part=0;
-      my_bool found_constrain= 0;
+      my_bool found_constraint= 0;
 
       if (s->keyuse)
       {						/* Use key if possible */
@@ -1979,7 +1979,7 @@ find_best(JOIN *join,table_map rest_tables,uint idx,double record_count,
           }
           else
           {
-	  found_constrain= 1;
+	  found_constraint= 1;
 	  /*
 	    Check if we found full key
 	  */
@@ -2133,12 +2133,28 @@ find_best(JOIN *join,table_map rest_tables,uint idx,double record_count,
 	    s->table->used_keys && best_key) &&
 	  !(s->table->force_index && best_key))
       {						// Check full join
+        ha_rows rnd_records= s->found_records;
         /* Estimate cost of reading table. */
-        tmp= (double) s->read_time;
+        tmp= s->table->file->scan_time();
+        /*
+          If there is a restriction on the table, assume that 25% of the
+          rows can be skipped on next part.
+          This is to force tables that this table depends on before this
+          table
+        */
+        if (found_constraint)
+          rnd_records-= rnd_records/4;
+
         if (s->on_expr)                         // Can't use join cache
         {
-          /* We have to read the whole table for each record */
-          tmp*= record_count;
+          tmp= record_count *
+               /* We have to read the whole table for each record */
+               (tmp +     
+               /*
+                 And we have to skip rows which does not satisfy join
+                 condition for each record.
+               */
+               (s->records - rnd_records)/(double) TIME_FOR_COMPARE);
         }
         else
         {
@@ -2146,30 +2162,25 @@ find_best(JOIN *join,table_map rest_tables,uint idx,double record_count,
           tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
                              record_count /
                              (double) thd->variables.join_buff_size));
+          /* 
+            We don't make full cartesian product between rows in the scanned
+            table and existing records because we skip all rows from the
+            scanned table, which does not satisfy join condition when 
+            we read the table (see flush_cached_records for details). Here we
+            take into account cost to read and skip these records.
+          */
+          tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
         }
 
         /*
-          We estimate the cost of making full cortesian product between
-          rows in the scanned table and generated records as
-          record_count*s->records/TIME_FOR_COMPARE. Taking into account
-          cost of evaluating WHERE clause for s->found_records is not
-          necessary because it costs much less than the cost mentioned
-          above.
+          We estimate the cost of evaluating WHERE clause for found records
+          as record_count * rnd_records + TIME_FOR_COMPARE. This cost plus
+          tmp give us total cost of using TABLE SCAN
         */
 	if (best == DBL_MAX ||
-	    (tmp  + record_count/(double) TIME_FOR_COMPARE*s->records <
+	    (tmp  + record_count/(double) TIME_FOR_COMPARE*rnd_records <
 	     best + record_count/(double) TIME_FOR_COMPARE*records))
 	{
-          /*
-            If there is a restriction on the table, assume that 25% of the
-            rows can be skipped on next part.
-            This is to force tables that this table depends on before this
-            table
-          */
-          ha_rows rnd_records= s->found_records;
-          if (found_constrain)
-            rnd_records-= rnd_records/4;
-          
 	  /*
 	    If the table has a range (s->quick is set) make_join_select()
 	    will ensure that this will be used