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)

3 files changed, 4 insertions, 7 deletions

diff --git a/storage/spider/mysql-test/spider/bugfix/r/mdev_21884.result b/storage/spider/mysql-test/spider/bugfix/r/mdev_21884.result
index 789478457d9..7a9c58e6f36 100644
--- a/storage/spider/mysql-test/spider/bugfix/r/mdev_21884.result
+++ b/storage/spider/mysql-test/spider/bugfix/r/mdev_21884.result
@@ -72,11 +72,8 @@ connection child2_1;
 SET NAMES utf8;
 SELECT argument FROM mysql.general_log WHERE command_type != 'Execute' AND argument LIKE '%select %';
 argument
-select `a`,`b` from `auto_test_remote`.`ta_r3` where `a` = 11 order by `b`
-select `a`,`b` from `auto_test_remote`.`ta_r3` where `a` = 12 order by `b`
-select `a`,`b` from `auto_test_remote`.`ta_r3` where `a` = 13 order by `b`
-select `a`,`b` from `auto_test_remote`.`ta_r3` where `a` = 14 order by `b`
-select `a`,`b` from `auto_test_remote`.`ta_r3` where `a` = 15 order by `b`
+select `a`,`b` from `auto_test_remote`.`ta_r2` order by `a`,`b`
+select `a`,`b` from `auto_test_remote`.`ta_r3` order by `a`,`b`
 SELECT argument FROM mysql.general_log WHERE command_type != 'Execute' AND argument LIKE '%select %'
 SELECT a, b, c FROM ta_r2 ORDER BY a ;
 SELECT a, b, c FROM ta_r3 ORDER BY a;
diff --git a/storage/spider/mysql-test/spider/r/direct_left_right_join_nullable.result b/storage/spider/mysql-test/spider/r/direct_left_right_join_nullable.result
index b2c4a209016..ff4f211faf5 100644
--- a/storage/spider/mysql-test/spider/r/direct_left_right_join_nullable.result
+++ b/storage/spider/mysql-test/spider/r/direct_left_right_join_nullable.result
@@ -87,7 +87,7 @@ NULL	NULL	NULL	3
 connection child2_1;
 SELECT argument FROM mysql.general_log WHERE command_type != 'Execute' AND argument LIKE '%select %';
 argument
-select t0.`a` `a`,t2.`b` `b`,t2.`c` `c`,t3.`a` `a` from `auto_test_remote`.`ta_r_no_idx` t3 left join (`auto_test_remote`.`ta_r_auto_inc` t2 join `auto_test_remote`.`ta_r_3` t1 join `auto_test_remote`.`ta_r` t0) on ((t2.`b` = t3.`b`) and (t2.`c` = t1.`c`) and (t0.`a` = t1.`a`) and (t1.`a` is not null) and (t3.`b` is not null)) where 1 order by t3.`a` desc
+select t0.`a` `a`,t2.`b` `b`,t2.`c` `c`,t3.`a` `a` from `auto_test_remote`.`ta_r_no_idx` t3 left join (`auto_test_remote`.`ta_r_auto_inc` t2 join `auto_test_remote`.`ta_r_3` t1 join `auto_test_remote`.`ta_r` t0) on ((t2.`b` = t3.`b`) and (t1.`c` = t2.`c`) and (t0.`a` = t1.`a`) and (t3.`b` is not null) and (t1.`a` is not null)) where 1 order by t3.`a` desc
 SELECT argument FROM mysql.general_log WHERE command_type != 'Execute' AND argument LIKE '%select %'
 SELECT a, b, date_format(c, '%Y-%m-%d %H:%i:%s') FROM ta_r ORDER BY a;
 a	b	date_format(c, '%Y-%m-%d %H:%i:%s')
diff --git a/storage/spider/mysql-test/spider/r/direct_right_left_right_join_nullable.result b/storage/spider/mysql-test/spider/r/direct_right_left_right_join_nullable.result
index 9a2f1882b94..840328508fa 100644
--- a/storage/spider/mysql-test/spider/r/direct_right_left_right_join_nullable.result
+++ b/storage/spider/mysql-test/spider/r/direct_right_left_right_join_nullable.result
@@ -87,7 +87,7 @@ NULL	c	2000-01-03 00:00:00	3
 connection child2_1;
 SELECT argument FROM mysql.general_log WHERE command_type != 'Execute' AND argument LIKE '%select %';
 argument
-select t0.`a` `a`,t2.`b` `b`,t2.`c` `c`,t3.`a` `a` from `auto_test_remote`.`ta_r_no_idx` t3 left join (`auto_test_remote`.`ta_r_auto_inc` t2 join `auto_test_remote`.`ta_r_3` t1 left join `auto_test_remote`.`ta_r` t0 on ((t0.`a` = t1.`a`) and (t1.`a` is not null))) on ((t2.`b` = t3.`b`) and (t2.`c` = t1.`c`) and (t3.`b` is not null)) where 1 order by t3.`a` desc
+select t0.`a` `a`,t2.`b` `b`,t2.`c` `c`,t3.`a` `a` from `auto_test_remote`.`ta_r_no_idx` t3 left join (`auto_test_remote`.`ta_r_auto_inc` t2 join `auto_test_remote`.`ta_r_3` t1 left join `auto_test_remote`.`ta_r` t0 on ((t0.`a` = t1.`a`) and (t1.`a` is not null))) on ((t2.`b` = t3.`b`) and (t1.`c` = t2.`c`) and (t3.`b` is not null)) where 1 order by t3.`a` desc
 SELECT argument FROM mysql.general_log WHERE command_type != 'Execute' AND argument LIKE '%select %'
 SELECT a, b, date_format(c, '%Y-%m-%d %H:%i:%s') FROM ta_r ORDER BY a;
 a	b	date_format(c, '%Y-%m-%d %H:%i:%s')