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, 4 insertions, 4 deletions

diff --git a/mysql-test/main/subselect4.result b/mysql-test/main/subselect4.result
index c4e945c2d10..382e4044081 100644
--- a/mysql-test/main/subselect4.result
+++ b/mysql-test/main/subselect4.result
@@ -265,7 +265,7 @@ EXPLAIN
 SELECT * FROM t1 WHERE NULL NOT IN (SELECT t2c.i FROM t2c WHERE t2c.pk = t1.pk);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	4	Using where
-2	DEPENDENT SUBQUERY	t2c	index_subquery	it2c	it2c	8	const,test.t1.pk	2	Using index; Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2c	index_subquery	it2c	it2c	8	const,test.t1.pk	1	Using index; Using where; Full scan on NULL key
 SELECT * FROM t1 WHERE NULL NOT IN (SELECT t2c.i FROM t2c WHERE t2c.pk = t1.pk);
 pk	i
 SELECT * FROM t1 WHERE NULL     IN (SELECT t2c.i FROM t2c WHERE t2c.pk = t1.pk) IS UNKNOWN;
@@ -335,7 +335,7 @@ EXPLAIN
 SELECT * FROM t1 WHERE (NULL, 1) NOT IN (SELECT t2c.i, t2c.pk FROM t2c WHERE t2c.pk = t1.pk);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	4	Using where
-2	DEPENDENT SUBQUERY	t2c	index_subquery	it2c	it2c	8	const,test.t1.pk	2	Using index; Using where; Full scan on NULL key
+2	DEPENDENT SUBQUERY	t2c	index_subquery	it2c	it2c	8	const,test.t1.pk	1	Using index; Using where; Full scan on NULL key
 SELECT * FROM t1 WHERE (NULL, 1) NOT IN (SELECT t2c.i, t2c.pk FROM t2c WHERE t2c.pk = t1.pk);
 pk	i
 0	10
@@ -1170,7 +1170,7 @@ WHERE (t2.pk = t1.pk) AND t2.pk IN (SELECT f2 FROM t1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t2	system	PRIMARY	NULL	NULL	NULL	1	
 1	PRIMARY	t1	const	PRIMARY	PRIMARY	4	const	1	
-2	DEPENDENT SUBQUERY	t1	index_subquery	f2	f2	4	func	2	Using index
+2	DEPENDENT SUBQUERY	t1	index_subquery	f2	f2	4	func	1	Using index
 SELECT t1.f3, MAX(t1.f2)
 FROM t1, t2
 WHERE (t2.pk = t1.pk) AND t2.pk IN (SELECT f2 FROM t1);
@@ -2797,7 +2797,7 @@ EXPLAIN
 SELECT * FROM t2 WHERE (t2.a,t2.b) IN (('abc',1), ('def', 2));
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t2	ALL	NULL	NULL	NULL	NULL	5	Using where
-1	PRIMARY	<derived3>	ref	key1	key1	4	test.t2.b	2	Using where; FirstMatch(t2)
+1	PRIMARY	<derived3>	ref	key1	key1	4	test.t2.b	1	Using where; FirstMatch(t2)
 3	DERIVED	NULL	NULL	NULL	NULL	NULL	NULL	NULL	No tables used
 set names default;
 set @@in_predicate_conversion_threshold= @save_in_predicate_conversion_threshold;