Change cost for REF to take into account cost for 1 extra key read_next

The main difference in code path between EQ_REF and REF is that for
REF we have to do an extra read_next on the index to check that there
is no more matching rows.

Before this patch we added a preference of EQ_REF by ensuring that REF
would always estimate to find at least 2 rows.

This patch adds the cost of the extra key read_next to REF access and
removes the code that limited REF to at least 2 rows. For some queries
this can have a big effect as the total estimated rows will be halved
for each REF table with 1 rows.

multi_range cost calculations are also changed to take into account
the difference between EQ_REF and REF.

The effect of the patch to the test suite:
- About 80 test case changed
- Almost all changes where for EXPLAIN where estimated rows for REF
  where changed from 2 to 1.
- A few test cases using explain extended had a change of 'filtered'.
  This is because of the estimated rows are now closer to the
  calculated selectivity.
- A very few test had a change of table order.
  This is because the change of estimated rows from 2 to 1 or the small
  cost change for REF
  (main.subselect_sj_jcl6, main.group_by, main.dervied_cond_pushdown,
  main.distinct, main.join_nested, main.order_by, main.join_cache)
- No key statistics and the estimated rows are now smaller which cased
  estimated filtering to be lower.
  (main.subselect_sj_mat)
- The number of total rows are halved.
  (main.derived_cond_pushdown)
- Plans with 1 row changed to use RANGE instead of REF.
  (main.group_min_max)
- ALL changed to REF
  (main.key_diff)
- Key changed from ref + index_only to PRIMARY key for InnoDB, as
  OPTIMIZER_ROW_LOOKUP_COST + OPTIMIZER_ROW_NEXT_FIND_COST is smaller than
  OPTIMIZER_KEY_LOOKUP_COST + OPTIMIZER_KEY_NEXT_FIND_COST.
  (main.join_outer_innodb)
- Cost changes printouts
  (main.opt_trace*)
- Result order change
  (innodb_gis.rtree)

1 files changed, 5 insertions, 5 deletions

diff --git a/mysql-test/main/table_elim.result b/mysql-test/main/table_elim.result
index a9602d90249..580b1cf5a0d 100644
--- a/mysql-test/main/table_elim.result
+++ b/mysql-test/main/table_elim.result
@@ -563,9 +563,9 @@ JOIN t5 ON t4.f3 ON t3.f1 = t5.f5 ON t2.f4 = t3.f4
 WHERE t3.f2 ;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	SIMPLE	t3	ALL	NULL	NULL	NULL	NULL	2	Using where
-1	SIMPLE	t5	ref	f5	f5	5	test.t3.f1	2	Using where; Using index
+1	SIMPLE	t5	ref	f5	f5	5	test.t3.f1	1	Using where; Using index
 1	SIMPLE	t4	ALL	NULL	NULL	NULL	NULL	3	Using where
-1	SIMPLE	t2	ref	f4	f4	1003	test.t3.f4	2	Using where
+1	SIMPLE	t2	ref	f4	f4	1003	test.t3.f4	1	Using where
 # ^^ The above must not produce a QEP of t3,t5,t2,t4
 #    as that violates the "no interleaving of outer join nests" rule.
 DROP TABLE t1,t2,t3,t4,t5;
@@ -970,7 +970,7 @@ group by yyy;
 explain select t1.* from t1 left join v2e on v2e.yyy=t1.a;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	10	
-1	PRIMARY	<derived2>	ref	key0	key0	5	test.t1.a	2	Using where
+1	PRIMARY	<derived2>	ref	key0	key0	5	test.t1.a	1	Using where
 2	DERIVED	NULL	NULL	NULL	NULL	NULL	NULL	NULL	no matching row in const table
 create table t2 (a int, b int, c int);
 insert into t2 select A.seq, B.seq, 123 from seq_1_to_3 A, seq_1_to_3 B;
@@ -980,14 +980,14 @@ explain select t1.* from t1 left join
 (select a, count(*) as cnt from t2 group by a, b) D on D.a=t1.a;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	10	
-1	PRIMARY	<derived2>	ref	key0	key0	5	test.t1.a	2	Using where
+1	PRIMARY	<derived2>	ref	key0	key0	5	test.t1.a	1	Using where
 2	DERIVED	t2	ALL	NULL	NULL	NULL	NULL	9	Using temporary; Using filesort
 # Still no elimination 'cause field D.b is just an alias for t2.a
 explain select t1.* from t1 left join 
 (select a, a as b, count(*) as cnt from t2 group by a, b) D on D.a=t1.a and D.b=t1.b;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	10	
-1	PRIMARY	<derived2>	ref	key0	key0	10	test.t1.a,test.t1.b	2	Using where
+1	PRIMARY	<derived2>	ref	key0	key0	10	test.t1.a,test.t1.b	1	Using where
 2	DERIVED	t2	ALL	NULL	NULL	NULL	NULL	9	Using temporary; Using filesort
 Warnings:
 Warning	1052	Column 'b' in group statement is ambiguous