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

diff --git a/mysql-test/main/subselect_no_mat.result b/mysql-test/main/subselect_no_mat.result
index ad5ead75ccb..12c72545f73 100644
--- a/mysql-test/main/subselect_no_mat.result
+++ b/mysql-test/main/subselect_no_mat.result
@@ -352,7 +352,7 @@ patient_uq	clinic_uq
 explain extended select * from t6 where exists (select * from t7 where uq = clinic_uq);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
 1	PRIMARY	t7	index	PRIMARY	PRIMARY	4	NULL	2	100.00	Using index
-1	PRIMARY	t6	ref	i1	i1	5	test.t7.uq	2	100.00	
+1	PRIMARY	t6	ref	i1	i1	5	test.t7.uq	1	100.00	
 Warnings:
 Note	1276	Field or reference 'test.t6.clinic_uq' of SELECT #2 was resolved in SELECT #1
 Note	1003	select `test`.`t6`.`patient_uq` AS `patient_uq`,`test`.`t6`.`clinic_uq` AS `clinic_uq` from `test`.`t7` join `test`.`t6` where `test`.`t6`.`clinic_uq` = `test`.`t7`.`uq`
@@ -4411,7 +4411,7 @@ CREATE INDEX I2 ON t1 (b);
 EXPLAIN SELECT a,b FROM t1 WHERE b IN (SELECT a FROM t1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	index	I1	I1	2	NULL	2	Using where; Using index; LooseScan
-1	PRIMARY	t1	ref	I2	I2	13	test.t1.a	2	Using index condition
+1	PRIMARY	t1	ref	I2	I2	13	test.t1.a	1	Using index condition
 SELECT a,b FROM t1 WHERE b IN (SELECT a FROM t1);
 a	b
 CREATE TABLE t2 (a VARCHAR(1), b VARCHAR(10));
@@ -4421,14 +4421,14 @@ CREATE INDEX I2 ON t2 (b);
 EXPLAIN SELECT a,b FROM t2 WHERE b IN (SELECT a FROM t2);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t2	index	I1	I1	4	NULL	2	Using where; Using index; LooseScan
-1	PRIMARY	t2	ref	I2	I2	13	test.t2.a	2	Using index condition
+1	PRIMARY	t2	ref	I2	I2	13	test.t2.a	1	Using index condition
 SELECT a,b FROM t2 WHERE b IN (SELECT a FROM t2);
 a	b
 EXPLAIN
 SELECT a,b FROM t1 WHERE b IN (SELECT a FROM t1 WHERE LENGTH(a)<500);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	index	I1	I1	2	NULL	2	Using where; Using index; LooseScan
-1	PRIMARY	t1	ref	I2	I2	13	test.t1.a	2	Using index condition
+1	PRIMARY	t1	ref	I2	I2	13	test.t1.a	1	Using index condition
 SELECT a,b FROM t1 WHERE b IN (SELECT a FROM t1 WHERE LENGTH(a)<500);
 a	b
 DROP TABLE t1,t2;
@@ -6656,7 +6656,7 @@ SET @@optimizer_switch='semijoin=off,materialization=off,in_to_exists=on,subquer
 EXPLAIN SELECT * FROM t1 WHERE a IN (SELECT a AS field1 FROM t1 GROUP BY field1);
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	index	NULL	a	4	NULL	2	Using where; Using index
-2	DEPENDENT SUBQUERY	t1	index_subquery	a	a	4	func	2	Using index
+2	DEPENDENT SUBQUERY	t1	index_subquery	a	a	4	func	1	Using index
 SELECT * FROM t1 WHERE a IN (SELECT a AS field1 FROM t1 GROUP BY field1);
 a
 2009-01-01
@@ -6859,7 +6859,7 @@ FROM t1 AS alias1, t1 AS alias2, t1 AS alias3
 WHERE alias1.a = alias2.a OR ('Moscow') IN ( SELECT a FROM t1 );
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	alias1	index	a	a	19	NULL	11	Using where; Using index
-1	PRIMARY	alias2	ref	a	a	19	test.alias1.a	2	Using index
+1	PRIMARY	alias2	ref	a	a	19	test.alias1.a	1	Using index
 1	PRIMARY	alias3	index	NULL	a	19	NULL	11	Using index; Using join buffer (flat, BNL join)
 2	SUBQUERY	t1	index_subquery	a	a	19	const	1	Using index; Using where
 SELECT MAX( alias2.a )
@@ -7009,7 +7009,7 @@ WHERE SLEEP(0.1) OR c < 'p' OR b = ( SELECT MIN(b) FROM t2 );
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	t1	system	NULL	NULL	NULL	NULL	1	
 1	PRIMARY	t2	ALL	b	NULL	NULL	NULL	2	Using where
-1	PRIMARY	t3	ref	d	d	5	test.t2.b	2	Using index
+1	PRIMARY	t3	ref	d	d	5	test.t2.b	1	Using index
 3	SUBQUERY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Select tables optimized away
 set @tmp_mdev410=@@global.userstat;
 set global userstat=on;
@@ -7041,7 +7041,7 @@ EXPLAIN SELECT * FROM t1 WHERE EXISTS ( SELECT a FROM t1, t2 WHERE b = a GROUP B
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
 2	SUBQUERY	t1	range	a	a	5	NULL	2	Using where; Using index
-2	SUBQUERY	t2	ref	b	b	5	test.t1.a	2	Using index
+2	SUBQUERY	t2	ref	b	b	5	test.t1.a	1	Using index
 DROP TABLE t1,t2;
 #
 # MDEV-435: Expensive subqueries may be evaluated during optimization in merge_key_fields
@@ -7074,7 +7074,7 @@ EXPLAIN SELECT * FROM t1 WHERE EXISTS ( SELECT a FROM t1, t2 WHERE b = a GROUP B
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
 1	PRIMARY	NULL	NULL	NULL	NULL	NULL	NULL	NULL	Impossible WHERE
 2	SUBQUERY	t1	range	a	a	5	NULL	2	Using where; Using index
-2	SUBQUERY	t2	ref	b	b	5	test.t1.a	2	Using index
+2	SUBQUERY	t2	ref	b	b	5	test.t1.a	1	Using index
 DROP TABLE t1,t2;
 #
 # MDEV-5991: crash in Item_field::used_tables