Update row and key fetch cost models to take into account data copy costsbb-10.7-selectivity

Before this patch, when calculating the cost of fetching and using a
row/key from the engine, we took into account the cost of finding a
row or key from the engine, but did not consistently take into account
index only accessed, clustered key or covered keys for all access
paths.

The cost of the WHERE clause (TIME_FOR_COMPARE) was not consistently
considered in best_access_path().  TIME_FOR_COMPARE was used in
calculation in other places, like greedy_search(), but was in some
cases (like scans) done an a different number of rows than was
accessed.

The cost calculation of row and index scans didn't take into account
the number of rows that where accessed, only the number of accepted
rows.

When using a filter, the cost of index_only_reads and cost of
accessing and disregarding 'filtered rows' where not taken into
account, which made filters cost less than there actually where.

To remedy the above, the following key & row fetch related costs
has been added:

- The cost of fetching and using a row is now split into different costs:
  - key + Row fetch cost (as before) but multiplied with the variable
  'optimizer_cache_cost' (default to 0.5). This allows the user to
  tell the optimizer the likehood of finding the key and row in the
  engine cache.
- RECORD_COPY_COST, The cost copying a row from the engine to the
  sql layer or creating a row from the join_cache to the record
  buffer. Mostly affects table scan costs.
- INDEX_COPY_COST the cost of finding the next key and copying it from
  the engine to the SQL layer. This is used when we calculate the cost
  index only reads. It makes index scans more expensive than before if
  they cover a lot of rows. (main.index_merge_myisam)
- INDEX_LOOKUP_COST, the cost of finding the first key in a range.
  This replaces the old define IDX_LOOKUP_COST, but with a higher cost.
- INDEX_NEXT_FIND_COST, the cost of finding the next key (and rowid).
  when doing a index scan and comparing the rowid to the filter.
  Before this cost was assumed to be 0.
- ROW_LOOKUP_COST, the cost of fetching a row by rowid.

All of the above constants/variables are now tuned to be somewhat in
proportion of executing complexity to each other.  There is tuning
need for these in the future, but that can wait until the above are
made user variables as that will make tuning much easier.

To make the usage of the above easy, there are new (not virtual)
cost calclation functions in handler:
- ha_read_time(), like read_time(), but take optimizer_cache_cost into
  account.
- ha_read_and_copy_time(), like ha_read_time() but take into account
  RECORD_COPY_TIME
- ha_read_and_compare_time(), like ha_read_and_copy_time() but take
  TIME_FOR_COMPARE into account.
- ha_read_with_rowid(). Read row with row id, taking RECORD_COPY_COST
  into account.  This is used with filesort where we don't need
  to execute the WHERE clause again.
- ha_keyread_time(), like keyread_time() but take
  optimizer_cache_cost into account.
- ha_keyread_and_copy_time(), like ha_keyread_time(), but add
  INDEX_COPY_COST.
- ha_key_scan_time(), like key_scan_time() but take
  optimizer_cache_cost nto account.
- ha_key_scan_and_compare_time(), like ha_key_scan_time(), but add
  INDEX_COPY_COST & TIME_FOR_COMPARE.

I also added some setup costs for doing different types of scans and
creating temporary tables (on disk and in memory). This encourages
the optimizer to not use these for simple 'a few row' lookups if
there are adequate key lookup strategies.
- TABLE_SCAN_SETUP_COST, cost of starting a table scan.
- INDEX_SCAN_SETUP_COST, cost of starting an index scan.
- HEAP_TEMPTABLE_CREATE_COST, cost of creating in memory
  temporary table.
- DISK_TEMPTABLE_CREATE_COST, cost of creating an on disk temporary
  table.

When calculating cost of fetching ranges, we had a cost of
IDX_LOOKUP_COST (0.125) for doing a key div for a new range. This is
now replaced with 'io_cost * INDEX_LOOKUP_COST (1.0) *
optimizer_cache_cost', which matches the cost we use for 'ref' and
other key lookups. The effect is that the cost is now a bit higher
when we have many ranges for a key.

Allmost all calculation with TIME_FOR_COMPARE is now done in
best_access_path(). 'JOIN::read_time' now includes the full
cost for finding the rows in the table.

In the result files, many of the changes are now again close to what
they where before the "Update cost for hash and cached joins" commit,
as that commit didn't fix the filter cost (too complex to do
everything in one commit).

The above changes showed a lot of a lot of inconsistencies in
optimizer cost calculation. The main objective with the other changes
was to calculation as similar (and accurate) as possible to make
different plans more comparable.

Detailed list of changes:

- Calculate index_only_cost consistently and correctly for all scan
  and ref accesses. The row fetch_cost and index_only_cost now
  takes into account clustered keys, covered keys and index only accesses.
- cost_for_index_read now returns both full cost and index_only_cost
- Fixed cost calculation of get_sweep_read_cost() to match other
  similar costs. This is bases on the assumption that data is more
  often stored on SSD than a hard disk.
- Replaced constant 2.0 with new define TABLE_SCAN_SETUP_COST.
- Some scan cost estimates did not take into account
  TIME_FOR_COMPARE. Now all scan costs takes this into
  account. (main.show_explain)
- Added session variable optimizer_cache_hit_ratio (default 50%). By
  adjusting this on can reduce or increase the cost of index or direct
  record lookups. The effect of the default is that key lookups is now
  a bit cheaper than before. See usage of 'optimizer_cache_cost' in
  handler.h.
- JOIN_TAB::scan_time() did not take into account index only scans,
  which produced a wrong cost when index scan was used. Changed
  JOIN_TAB:::scan_time() to take into consideration clustered and
  covered keys. The values are now cached and we only have to call
  this function once. Other calls are changed to use the cached
  values.  Function renamed to JOIN_TAB::estimate_scan_time().
- Fixed that most index cost calculations are done the same way and
  more close to 'range' calculations. The cost is now lower than
  before for small data sets and higher for large data sets as we take
  into account how many keys are read (main.opt_trace_selectivity,
  main.limit_rows_examined).
- Ensured that index_scan_cost() ==
  range(scan_of_all_rows_in_table_using_one_range) +
  MULTI_RANGE_READ_INFO_CONST. One effect of this is that if there
  is choice of doing a full index scan and a range-index scan over
  almost the whole table then index scan will be preferred (no
  range-read setup cost).  (innodb.innodb, main.show_explain,
  main.range)
  - Fixed the EQ_REF and REF takes into account clustered and covered
    keys.  This changes some plans to use covered or clustered indexes
    as these are much cheaper.  (main.subselect_mat_cost,
    main.state_tables_innodb, main.limit_rows_examined)
  - Rowid filter setup cost and filter compare cost now takes into
    account fetching and checking the rowid (INDEX_NEXT_FIND_COST).
    (main.partition_pruning heap.heap_btree main.log_state)
  - Added INDEX_NEXT_FIND_COST to
    Range_rowid_filter_cost_info::lookup_cost to account of the time
    to find and check the next key value against the container
  - Introduced ha_keyread_time(rows) that takes into account finding
    the next row and copying the key value to 'record'
    (INDEX_COPY_COST).
  - Introduced ha_key_scan_time() for calculating an index scan over
    all rows.
  - Added IDX_LOOKUP_COST to keyread_time() as a startup cost.
  - Added index_only_fetch_cost() as a convenience function to
    OPT_RANGE.
  - keyread_time() cost is slightly reduced to prefer shorter keys.
    (main.index_merge_myisam)
  - All of the above caused some index_merge combinations to be
    rejected because of cost (main.index_intersect). In some cases
    'ref' where replaced with index_merge because of the low
    cost calculation of get_sweep_read_cost().
  - Some index usage moved from PRIMARY to a covering index.
    (main.subselect_innodb)
- Changed cost calculation of filter to take INDEX_LOOKUP_COST and
  TIME_FOR_COMPARE into account.  See sql_select.cc::apply_filter().
  filter parameters and costs are now written to optimizer_trace.
- Don't use matchings_records_in_range() to try to estimate the number
  of filtered rows for ranges. The reason is that we want to ensure
  that 'range' is calculated similar to 'ref'. There is also more work
  needed to calculate the selectivity when using ranges and ranges and
  filtering.  This causes filtering column in EXPLAIN EXTENDED to be
  100.00 for some cases where range cannot use filtering.
  (main.rowid_filter)
- Introduced ha_scan_time() that takes into account the CPU cost of
  finding the next row and copying the row from the engine to
  'record'. This causes costs of table scan to slightly increase and
  some test to changed their plan from ALL to RANGE or ALL to ref.
  (innodb.innodb_mysql, main.select_pkeycache)
  In a few cases where scan time of very small tables have lower cost
  than a ref or range, things changed from ref/range to ALL.
  (main.myisam, main.func_group, main.limit_rows_examined,
  main.subselect2)
- Introduced ha_scan_and_compare_time() which is like ha_scan_time()
  but also adds the cost of the where clause (TIME_FOR_COMPARE).
- Added small cost for creating temporary table for
  materialization. This causes some very small tables to use scan
  instead of materialization.
- Added checking of the WHERE clause (TIME_FOR_COMPARE) of the
  accepted rows to ROR costs in get_best_ror_intersect()
- Removed '- 0.001' from 'join->best_read' and optimize_straight_join()
  to ensure that the 'Last_query_cost' status variable contains the same
  value as the one that was calculated by the optimizer.
- Take avg_io_cost() into account in handler::keyread_time() and
  handler::read_time(). This should have no effect as it's 1.0 by
  default, except for heap that overrides these functions.
- Some 'ref_or_null' accesses changed to 'range' because of cost
  adjustments (main.order_by)
- Added scan type "scan_with_join_cache" for optimizer_trace. This is
  just to show in the trace what kind of scan was used.
- When using 'scan_with_join_cache' take into account number of
  preceding tables (as have to restore all fields for all previous
  table combination when checking the where clause)
  The new cost added is:
  (row_combinations * RECORD_COPY_COST * number_of_cached_tables).
  This increases the cost of join buffering in proportion of the
  number of tables in the join buffer. One effect is that full scans
  are now done earlier as the cost is then smaller.
  (main.join_outer_innodb, main.greedy_optimizer)
- Removed the usage of 'worst_seeks' in cost_for_index_read as it
  caused wrong plans to be created; It prefered JT_EQ_REF even if it
  would be much more expensive than a full table scan. A related issue
  was that worst_seeks only applied to full lookup, not to clustered
  or index only lookups, which is not consistent. This caused some
  plans to use index scan instead of eq_ref (main.union)
- Changed federated block size from 4096 to 1500, which is the typical
  size of an IO packet.
- Added costs for reading rows to Federated. Needed as there is no
  caching of rows in the federated engine.
- Added ha_innobase::read_with_rowid() cost function.
- A lot of extra things added to optimizer trace
  - More costs, especially for materialization and index_merge.
  - Make lables more uniform
  - Fixed a lot of minor bugs
  - Added 'trace_started()' around a lot of trace blocks.
- When calculating ORDER BY with LIMIT cost for using an index
  the cost did not take into account the number of row retrivals
  that has to be done or the cost of comparing the rows with the
  WHERE clause. The cost calculated would be just a fraction of
  the real cost. Now we calculate the cost as we do for ranges
  and 'ref'.
- 'Using index for group-by' is used a bit as we now take into account
   the WHERE clause cost when comparing with 'ref' and prefer the
   method with fewer row combinations.  (main.group_min_max).

Bugs fixed:
- Fixed that we don't calculate TIME_FOR_COMPARE twice for some plans,
  like in optimize_straight_join() and greedy_search()
- Fixed bug in save_explain_data where we could test for the wrong
  index when displaying 'Using index'. This caused some old plans to
  show 'Using index'.  (main.subselect_innodb, main.subselect2)
- Fixed bug in get_best_ror_intersect() where 'min_cost' was not
  updated, and the cost we compared with was not the one that was
  used.
- Fixed very wrong cost calculation for priority queues in
  check_if_pq_applicable(). (main.order_by now correctly uses priority
  queue)
- When calculating cost of EQ_REF or REF, we added the cost of
  comparing the WHERE clause with the found rows, not all row
  combinations. This made ref and eq_ref to be regarded way to cheap
  compared to other access methods.
- FORCE INDEX cost calculation didn't take into account clustered or
  covered indexes.
- JT_EQ_REF cost was estimated as avg_io_cost(), which is half the
  cost of a JT_REF key. This may be true for InnoDB primary key, but
  not for other unique keys or other engines. Now we use handler
  function to calculate the cost, which allows us to handle
  consistently clustered, covered keys and not covered keys.
- ha_start_keyread() didn't call extra_opt() if keyread was already
  enabled but still changed the 'keyread' variable (which is wrong).
  Fixed by not doing anything if keyread is already enabled.
- multi_range_read_info_cost() didn't take into account io_cost when
  calculating the cost of ranges.
- fix_semijoin_strategies_for_picked_join_order() used the wrong
  record_count when calling best_access_path() for SJ_OPT_FIRST_MATCH
  and SJ_OPT_LOOSE_SCAN.
- Hash joins didn't provide correct best_cost to the upper level, which
  means that the cost for hash_joins more expensive than calculated
  in best_access_path (a difference of 10x * TIME_OF_COMPARE).
  This is fixed in the new code thanks to that we now include
  TIME_OF_COMPARE cost in 'read_time'.

Other things:
- Added some 'if (thd->trace_started())' to speed up code
- Removed not used function Cost_estimate::is_zero()
- Simplified testing of HA_POS_ERROR in get_best_ror_intersect().
  (No cost changes)
- Moved ha_start_keyread() from join_read_const_table() to join_read_const()
  to enable keyread for all types of JT_CONST tables.
- Made a few very short functions inline in handler.h

Notes:
- In main.rowid_filter the join order of order and lineitem is swapped.
  This is because the cost of doing a range fetch of lineitem(98 rows) is
  almost as big as the whole join of order,lineitem. The filtering will
  also ensure that we only have to do very small key fetches of the rows
  in lineitem.
- main.index_merge_myisam had a few changes where we are now using
  less keys for index_merge. This is because index scans are now more
  expensive than before.
- handler->optimizer_cache_cost is updated in ha_external_lock().
  This ensures that it is up to date per statements.
  Not an optimal solution (for locked tables), but should be ok for now.
- 'DELETE FROM t1 WHERE t1.a > 0 ORDER BY t1.a' does not take cost of
  filesort into consideration when table scan is chosen.
  (main.myisam_explain_non_select_all)
- perfschema.table_aggregate_global_* has changed because an update
  on a table with 1 row will now use table scan instead of key lookup.

TODO in upcomming commits:
- Fix selectivity calculation for ranges with and without filtering and
  when there is a ref access but scan is chosen.
  For this we have to store the lowest known value for
  'accepted_records' in the OPT_RANGE structure.
- Change that records_read does not include filtered rows.
- test_if_cheaper_ordering() needs to be updated to properly calculate costs.
  This will fix tests like main.order_by_innodb, main.single_delete_update
- Extend get_range_limit_read_cost() to take into considering
  cost_for_index_read() if there where no quick keys. This will reduce
  the computed cost for ORDER BY with LIMIT in some cases.
  (main.innodb_ext_key)
- Change all optimizer cost constants to user variables. This will make it
  possible for the users to tune the cost model if needed instead of having
  to ask for a new server build.
- Fix that we take into account selectivity when counting the number of rows
  we have to read when considering using a index table scan to resolve
  ORDER BY.
- Add new calculation for reaed_with_rowid() where we take into account the
  benefit of reading multiple rows from the same page.

fixup to be combined with previous commit

Another fixup, to be combined with the previous commits

Fixed a lot of inconsistencies in optimizer cost calculation. The main
objective was get cost calculation as similar (and accurate) as
possible to make different plans more comparable.

- Replaced constant 2.0 with new define TABLE_SCAN_SETUP_COST.
- Added RECORD_COPY_COST, the cost of finding the next row and copying
  it to record for table scans.
- Added INDEX_COPY_COST, the cost of finding the next key and copying it
  to record for index scans.
- Added INDEX_NEXT_FIND_COST, the cost of finding the next index entry and
  checking it against filter.
- Some scan cost estimates did not take into account
  TIME_FOR_COMPARE. Now all scan costs takes this into
  account. (main.show_explain)
- Added session variable optimizer_cache_hit_ratio (default 50%). By
  adjusting this on can reduce or increase the cost of index or direct
  record lookups. The effect of the default is that key lookups is now
  a bit cheaper than before. See usage of 'optimizer_cache_cost' in
  handler.h.
- JOIN_TAB::scan_time() did not take into account index only scans,
  which produced a wrong cost when index scan was used. Fixed by
  adding support for covering keys. Cached also the calculated values
  to avoid future calls during optimization phase.
- Fixed that most index cost calculations are done the same way and
  more close to 'range' calculations. The cost is now lower than before for
  small data sets and higher for large data sets as we take into account
  how many keys are read.
  - Ensured that index_scan_cost() ==
    range(scan_of_all_rows_in_table_using_one_range) +
    MULTI_RANGE_READ_INFO_CONST. One effect of this is that if there is
    choice of doing a full index scan and a range-index scan over almost
    the whole table then index scan will be preferred (no range-read
    setup cost).
    (innodb.innodb, main.show_explain, main.range)
  - Fixed the EQ_REF and REF takes into account clustered and covered keys.
    This changes some plans to use covered or clustered indexes as these are
    much cheaper.
    (main.subselect_mat_cost main.state_tables_innodb)
  - Rowid filter setup cost and filter compare cost now takes into account
    fetching and checking the rowid (INDEX_NEXT_FIND_COST).
   (main.partition_pruning heap.heap_btree main.log_state)
  - Introduced ha_keyread_time(rows) that takes into account finding the
    next row and copying the key value to 'record' (INDEX_COPY_COST).
  - Introduced ha_key_scan_time() for calculating an index scan over all
    rows.
  - Added IDX_LOOKUP_COST to keyread_time() as a startup cost.
  - Added index_only_fetch_cost() as a convenience function to
    OPT_RANGE.
  - keyread_time() cost is slightly reduced to prefer shorter keys.
    (main.index_merge_myisam)
  - All of the above caused some index_merge combinations to be
    rejected because of cost (main.index_intersect). In some cases
    'ref' where replaced with index_merge because of the low
    cost calculation of get_sweep_read_cost().
  - Some index usage moved from PRIMARY to a covering index.
    (main.subselect_innodb)
- Don't use matching_records_in_range() to try to estimate the number of
  filtered rows for ranges. The reason is that we want to ensure that 'range'
  is calculated similar to 'ref'. There is also more work needed to
  calculate the selectivity when using ranges and ranges and filtering.
  This causes filtering column in EXPLAIN EXTENDED to be 100.00 for
  some cases where range cannot use filtering.
  (main.rowid_filter)
- Introduced ha_scan_time() that takes into account the CPU cost of
  finding the next row and copying the row from the engine to
  'record'. This causes costs of table scan to slightly increase and
  some test to changed their plan from ALL to RANGE or ALL to ref.
  (innodb.innodb_mysql, main.select_pkeycache)
- Introduced ha_scan_and_compare_time() which is like ha_scan_time()
  but also adds the cost of checking the where clause
  (TIME_FOR_COMPARE).
- Introduced ha_read_with_rowid() that takes into account
  RECORD_COPY_COST.
- Added checking of the WHERE clause of the accepted rows to ROR costs
  in get_best_ror_intersect()
- Removed '- 0.001' from 'join->best_read' and optimize_straight_join()
  to ensure that the 'Last_query_cost' status variable contains the same
  value as the one that was calculated by the optimizer.
- Added INDEX_NEXT_FIND_COST to Range_rowid_filter_cost_info::lookup_cost
  to account of the time to find and check the next key value against the
  container
- Changed 'JOIN_TAB:::scan_time() to take into consideration clustered and
  covered keys. The values are now cached and we only have to call this
  function once. Other calls are changed to use the cached values.
  Function renamed to JOIN_TAB::estimate_scan_time().
- Take avg_io_cost() into account in handler::keyread_time() and
  handler::read_time(). This should have no effect as it's 1.0 by
  default, except for heap that overrides these functions.
- Some 'ref_or_null' accesses changed to 'range' because of cost
  adjustments (main.order_by)
- Added scan type "scan_with_join_cache" for optimizer_trace. This is just
  to show what kind of scan was used.
-I had to remove the usage of 'worst_seeks' in cost_for_index_read as it
 cases wrong plans to be created;  It prefered JT_EQ_REF even if it would
 be much more expensive than a full table scan. A related issue was that
 worst_seeks only applied to full lookup, not to clustered or index only
 lookups, which is not consistent. This caused some plans to use index
 scan instead of eq_ref (main.union)

Bugs fixed:
- Fixed that we don't calculate TIME_FOR_COMPARE twice for some plans,
  like in optimize_straight_join() and greedy_search()
- Fixed bug in save_explain_data where we could test for the wrong
  index when displaying 'Using index'. This caused some old plans to
  show 'Using index'.  (main.subselect_innodb, main.subselect2)
- Fixed bug in get_best_ror_intersect() where 'min_cost' was not updated,
  and the cost we compared with was not the one that was used.
- Fixed very wrong cost calculation for priority queues in
  check_if_pq_applicable().
- When calculating cost of EQ_REF or REF, we added the cost of comparing
  the WHERE clause with the found rows, not all row combinations. This
  made ref and eq_ref to be regarded way to cheap compared to other
  access methods.
- FORCE INDEX cost calculation didn't take into account clustered or
  covered indexes.
- JT_EQ_REF cost was estimated as avg_io_cost(), which is half the
  cost of a JT_REF key. This may be true for InnoDB primary key, but
  not for other unique keys or other engines. Now we use handler
  function to calculate the cost, which allows us to handle
  consistently clustered, covered keys and not covered keys.
- ha_start_keyread() didn't call extra_opt() if keyread was already
  enabled but still changed the 'keyread' variable (which is wrong).
  Fixed by not doing anything if keyread is already enabled.
- multi_range_read_info_cost() didn't take into account io_cost when
  calculating the cost of ranges.

Other things:
- Added some 'if (thd->trace_started())' to speed up code
- Removed not used function Cost_estimate::is_zero()
- Simplified testing of HA_POS_ERROR in get_best_ror_intersect().
  (No cost changes)
- Moved ha_start_keyread() from join_read_const_table() to join_read_const()
  to enable keyread for all types of JT_CONST tables.
- Made a few very short functions inline in handler.h

TODO in upcomming commit:
- Fix selectivity calculation for ranges with and without filtering and
  when there is a ref access but scan is chosen.
  For this we have to store the lowest known value for
  'accepted_records' in the OPT_RANGE structure.
- test_if_cheaper_ordering() needs to be updated to properly calculate costs.
  This will fix tests like main.order_by_innodb.
- Extend get_range_limit_read_cost() to take into considering
  cost_for_index_read() if there where no quick keys. This will reduce
  the computed cost for ORDER BY with LIMIT in some cases.
  (main.innodb_ext_key)

COMMENTS:
- In main.rowid_filter the join order of order and lineitem is swapped.
  This is because the cost of doing a range fetch of lineitem(98 rows) is
  almost as big as the whole join of order,lineitem. The filtering will
  also ensure that we only have to do very small key fetches of the rows
  in lineitem.
- handler->optimizer_cache_cost is updated in ha_external_lock().
  This ensures that it is up to date per statements.
  Not an optimal solution (for locked tables), but should be ok for now.

Another temporary commit to be combined with previous ones

1 files changed, 490 insertions, 281 deletions

diff --git a/sql/sql_select.cc b/sql/sql_select.cc
index 172fbff6b72..b3bf0557941 100644
--- a/sql/sql_select.cc
+++ b/sql/sql_select.cc
@@ -88,6 +88,13 @@
 */
 #define HASH_FANOUT 0.1
 
+/* Cost for reading a row trough an index */
+struct INDEX_READ_COST
+{
+  double read_cost;
+  double index_only_cost;
+};
+
 const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref",
 			      "MAYBE_REF","ALL","range","index","fulltext",
 			      "ref_or_null","unique_subquery","index_subquery",
@@ -5504,7 +5511,8 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list,
 	  s->type=JT_SYSTEM;
 	  join->const_table_map|=table->map;
 	  set_position(join,const_count++,s,(KEYUSE*) 0);
-	  if ((tmp= join_read_const_table(join->thd, s, join->positions+const_count-1)))
+	  if ((tmp= join_read_const_table(join->thd, s,
+                                          join->positions+const_count-1)))
 	  {
 	    if (tmp > 0)
 	      goto error;			// Fatal error
@@ -5710,17 +5718,11 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list,
                                         "system");
         continue;
       }
-      /* Approximate found rows and time to read them */
-      if (s->table->is_filled_at_execution())
-      {
-        get_delayed_table_estimates(s->table, &s->records, &s->read_time,
-                                    &s->startup_cost);
-        s->found_records= s->records;
-        s->table->opt_range_condition_rows= s->records;
-        s->table->used_stat_records= s->records;
-      }
-      else
-        s->scan_time();
+      /*
+        Approximate found rows and time to read them
+        Update found_records, records, read_time and other scan related variables
+      */
+      s->estimate_scan_time();
 
       if (s->table->is_splittable())
         s->add_keyuses_for_splitting();
@@ -5730,10 +5732,15 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list,
         This is can't be to high as otherwise we are likely to use
         table scan.
       */
+#ifdef OLD_CODE_LIMITED_SEEKS
       s->worst_seeks= MY_MIN((double) s->found_records / 10,
-        (double) s->read_time*3);
+                             (double) s->read_time*3);
+      s->worst_seeks= s->found_records;        // Disable worst seeks
       if (s->worst_seeks < 2.0)			// Fix for small tables
         s->worst_seeks=2.0;
+#else
+      s->worst_seeks= DBL_MAX;
+#endif
 
       /*
         Add to stat->const_keys those indexes for which all group fields or
@@ -7610,7 +7617,7 @@ static double matching_candidates_in_table(JOIN_TAB *s,
     0.0 is returned only if it is guaranteed there are no matching rows
     (for example if the table is empty).
   */
-  return dbl_records ? MY_MAX(dbl_records, 1.0) : 0.0;
+  return dbl_records ? MY_MAX(dbl_records, MIN_ROWS_AFTER_FILTERING) : 0.0;
 }
 
 
@@ -7623,33 +7630,165 @@ static double matching_candidates_in_table(JOIN_TAB *s,
 
   One main difference between the functions is that
   multi_range_read_info_const() adds a very small cost per range
-  (IDX_LOOKUP_COST) and also MULTI_RANGE_READ_SETUP_COST, to ensure that
-  'ref' is preferred slightly over ranges.
+  MULTI_RANGE_READ_SETUP_COST, to ensure that 'ref' is preferred
+  over ranges.
+
+  Note that this function assumes that index_only_cost is only to be
+  used with filtering (as cost.read_cost takes into account both
+  clustering and covered keys). index_only_cost does not include
+  INDEX_COPY_COST as for filtering there is no copying of not accepted
+  keys.
+
+  TIME_FOR_COMPARE cost is not added to any result.
 */
 
-double cost_for_index_read(const THD *thd, const TABLE *table, uint key,
-                           ha_rows records, ha_rows worst_seeks)
+INDEX_READ_COST cost_for_index_read(const THD *thd, const TABLE *table,
+                                    uint key,
+                                    ha_rows records, ha_rows worst_seeks)
 {
-  DBUG_ENTER("cost_for_index_read");
-  double cost;
+  INDEX_READ_COST cost;
   handler *file= table->file;
+  double rows_adjusted;
+  DBUG_ENTER("cost_for_index_read");
 
-  set_if_smaller(records, (ha_rows) thd->variables.max_seeks_for_key);
+  rows_adjusted= MY_MIN(records, (ha_rows) thd->variables.max_seeks_for_key);
+#ifdef OLD_CODE_LIMITED_SEEKS
+  set_if_smaller(rows_adjusted, worst_seeks);
+#endif
   if (file->is_clustering_key(key))
-    cost= file->read_time(key, 1, records);
-  else
-    if (table->covering_keys.is_set(key))
-    cost= file->keyread_time(key, 1, records);
+  {
+    cost.index_only_cost= file->ha_read_time(key, 1, rows_adjusted);
+    /*
+      Same computation as in ha_read_and_copy_time()
+      We do it explicitely here as we want to use the original value of
+      records to compute the record copy cost.
+    */
+    cost.read_cost= (cost.index_only_cost +
+                     rows2double(records) * RECORD_COPY_COST);
+  }
+  else if (table->covering_keys.is_set(key) && !table->no_keyread)
+  {
+    cost.index_only_cost= file->ha_keyread_time(key, 1, rows_adjusted);
+    /* Same computation as in ha_keyread_and_copy_time() */
+    cost.read_cost= (cost.index_only_cost +
+                     rows2double(records) * INDEX_COPY_COST);
+  }
   else
-    cost= ((file->keyread_time(key, 0, records) +
-            file->read_time(key, 1, MY_MIN(records, worst_seeks))));
-
-  DBUG_PRINT("statistics", ("cost: %.3f", cost));
+  {
+    cost.index_only_cost= file->ha_keyread_time(key, 1, records);
+    /*
+      Note that ha_read_time() + ..RECORD_COPY_COST should be same
+      as ha_read_with_rowid().
+    */
+    cost.read_cost= (cost.index_only_cost +
+                     file->ha_read_time(key, 0, rows_adjusted) +
+                     rows2double(records) * RECORD_COPY_COST);
+  }
+  DBUG_PRINT("statistics", ("index_cost: %.3f  full_cost: %.3f",
+                            cost.index_only_cost, cost.read_cost));
   DBUG_RETURN(cost);
 }
 
 
 /**
+   Apply filter if the filter is better than the current cost
+
+   @param thd             Thread handler
+   @param table           Table
+   @param cost            Pointer to cost for *records_arg rows, not including
+                          TIME_FOR_COMPARE cost.
+                          Will be updated to new cost if filter is used.
+   @param records_arg     Pointer to number of records for the current key.
+                          Will be updated to records after filter, if filter is
+                          used.
+   @param startup_cost    Startup cost. Will be updated if filter is used.
+   @param fetch_cost      Cost of finding the row, without copy or compare cost
+   @param index_only_cost Cost if fetching '*records_arg' key values
+   @param prev_records    Number of record combinations in previous tables
+
+   @return 'this'         Filter is used (and variables are updated)
+   @return 0              Filter is worse than old plan
+*/
+
+Range_rowid_filter_cost_info* Range_rowid_filter_cost_info::
+apply_filter(THD *thd, TABLE *table, double *cost, double *records_arg,
+             double *startup_cost, double fetch_cost, double index_only_cost,
+             uint ranges, double prev_records)
+{
+  bool use_filter;
+  double new_cost, new_total_cost, records= *records_arg, new_records;
+  double cost_of_accepted_rows, cost_of_rejected_rows;
+  double filter_startup_cost= get_setup_cost();
+  double io_cost= table->file->avg_io_cost();
+  double filter_lookup_cost= records * lookup_cost();
+
+  /*
+    Calculate number of resulting rows after filtering
+    Here we trust selectivity and do not adjust rows up even if
+    the end result is low. This means that new_records is allowed to be
+    be < 1.0
+  */
+  new_records= records * selectivity;
+
+  /*
+    Calculate the cost of the filter based on that we had originally
+    'records' rows and after the filter only 'new_records' accepted
+    rows.
+    Note that the rejected rows, we have only done a key read. We only
+    fetch the row and compare the where if the filter accepts the
+    row id.
+    In case of index only read, fetch_cost == index_only_cost. Even in this
+    the filter can give a better plan as we have to do less comparisons
+    with the WHERE clause.
+
+    The io_cost is used to take into account that we have to do 1 key
+    lookup to find the first matching key in each range.
+  */
+  cost_of_accepted_rows= fetch_cost * selectivity;
+  cost_of_rejected_rows= index_only_cost * (1-selectivity);
+  /*
+    The MAX() is used below to ensure that we take into account the index
+    read even if selectivity (and thus new_records) would be very low.
+  */
+  new_cost= (MY_MAX(cost_of_accepted_rows,
+                    ranges * INDEX_LOOKUP_COST * io_cost *
+                    table->file->optimizer_cache_cost) +
+             cost_of_rejected_rows + filter_lookup_cost);
+  new_total_cost= ((new_cost + new_records/TIME_FOR_COMPARE) * prev_records +
+                   filter_startup_cost);
+
+  DBUG_ASSERT(new_cost >= 0 && new_records >= 0);
+  use_filter= ((*cost + records/TIME_FOR_COMPARE) * prev_records >
+               new_total_cost);
+
+  if (unlikely(thd->trace_started()))
+  {
+    Json_writer_object trace_filter(thd, "filter");
+    trace_filter.add("rowid_filter_key",
+                     table->key_info[get_key_no()].name).
+      add("index_only_cost", index_only_cost).
+      add("filter_startup_cost", filter_startup_cost).
+      add("find_key_and_filter_lookup_cost", filter_lookup_cost).
+      add("filter_selectivity", selectivity).
+      add("orginal_rows", records).
+      add("new_rows", new_records).
+      add("original_found_rows_cost", fetch_cost).
+      add("new_found_rows_cost", new_cost).
+      add("cost", new_total_cost).
+      add("filter_used", use_filter);
+  }
+  if (use_filter)
+  {
+    *cost= new_cost;
+    *records_arg= new_records;
+    (*startup_cost)+= filter_startup_cost;
+    return this;
+  }
+  return 0;
+}
+
+
+/**
   Find the best access path for an extension of a partial execution
   plan and add this path to the plan.
 
@@ -7696,7 +7835,6 @@ best_access_path(JOIN      *join,
   my_bool found_constraint= 0;
   double best_cost=         DBL_MAX;
   double records=           DBL_MAX;
-  double best_filter_cmp_gain;
   table_map best_ref_depends_map= 0;
   Range_rowid_filter_cost_info *best_filter= 0;
   double tmp;
@@ -7706,28 +7844,32 @@ best_access_path(JOIN      *join,
   KEYUSE *hj_start_key= 0;
   SplM_plan_info *spl_plan= 0;
   enum join_type best_type= JT_UNKNOWN, type= JT_UNKNOWN;
-
-  disable_jbuf= disable_jbuf || idx == join->const_tables;  
-
   Loose_scan_opt loose_scan_opt;
+  TABLE *table= s->table;
+  Json_writer_object trace_wrapper(thd, "best_access_path");
   DBUG_ENTER("best_access_path");
 
-  Json_writer_object trace_wrapper(thd, "best_access_path");
+  disable_jbuf= disable_jbuf || idx == join->const_tables;
 
   bitmap_clear_all(eq_join_set);
 
   loose_scan_opt.init(join, s, remaining_tables);
 
-  if (s->table->is_splittable())
+  if (table->is_splittable())
     spl_plan= s->choose_best_splitting(record_count, remaining_tables);
+
+  if (unlikely(thd->trace_started()))
+  {
+    Json_writer_object info(thd, "plan_details");
+    info.add("record_count", record_count);
+  }
   Json_writer_array trace_paths(thd, "considered_access_paths");
 
   if (s->keyuse)
   {                                            /* Use key if possible */
     KEYUSE *keyuse;
     KEYUSE *start_key=0;
-    TABLE *table= s->table;
-    double best_records= DBL_MAX;
+    double best_records= DBL_MAX, index_only_cost= DBL_MAX;
     uint max_key_part=0;
 
     /* Test how we can use keys */
@@ -7853,7 +7995,10 @@ best_access_path(JOIN      *join,
           Calculate an adjusted cost based on how many records are read
           This will be later multipled by record_count.
         */
-        tmp= prev_record_reads(join_positions, idx, found_ref)/record_count;
+        tmp= (prev_record_reads(join_positions, idx, found_ref) /
+              record_count);
+        set_if_smaller(tmp, 1.0);
+        index_only_cost= tmp;
         /*
           Really, there should be records=0.0 (yes!)
           but 1.0 would be probably safer
@@ -7880,28 +8025,39 @@ best_access_path(JOIN      *join,
             - equalities we are using reject NULLs (3)
             then the estimate is rows=1.
           */
-          if ((key_flags & (HA_NOSAME | HA_EXT_NOSAME)) &&   // (1)
+          if ((key_flags & (HA_NOSAME | HA_EXT_NOSAME)) &&   //  (1)
               (!(key_flags & HA_NULL_PART_KEY) ||            //  (2)
                all_key_parts == notnull_part))               //  (3)
           {
-
-            /* TODO: Adjust cost for covering and clustering key */
+            double adjusted_cost;
             type= JT_EQ_REF;
             if (unlikely(trace_access_idx.trace_started()))
               trace_access_idx.
                 add("access_type", join_type_str[type]).
                 add("index", keyinfo->name);
             if (!found_ref && table->opt_range_keys.is_set(key))
+            {
+              /* Ensure that the cost is identical to the range cost */
               tmp= table->opt_range[key].fetch_cost;
+              index_only_cost= table->opt_range[key].index_only_cost;
+            }
             else
-              tmp= table->file->avg_io_cost();
+            {
+              INDEX_READ_COST cost= cost_for_index_read(thd, table, key,
+                                                        1,1);
+              tmp= cost.read_cost;
+              index_only_cost= cost.index_only_cost;
+            }
             /*
               Calculate an adjusted cost based on how many records are read
               This will be later multipled by record_count.
             */
-            tmp*= (prev_record_reads(join_positions, idx, found_ref) /
-                   record_count);
-            records=1.0;
+            adjusted_cost= (prev_record_reads(join_positions, idx, found_ref) /
+                            record_count);
+            set_if_smaller(adjusted_cost, 1.0);
+            tmp*= adjusted_cost;
+            index_only_cost*= adjusted_cost;
+            records= 1.0;
           }
           else
           {
@@ -7931,9 +8087,11 @@ best_access_path(JOIN      *join,
               */
               if (table->opt_range_keys.is_set(key))
               {
+                /* Ensure that the cost is identical to the range cost */
                 records= (double) table->opt_range[key].rows;
                 trace_access_idx.add("used_range_estimates", true);
                 tmp= table->opt_range[key].fetch_cost;
+                index_only_cost= table->opt_range[key].index_only_cost;
                 goto got_cost2;
               }
               /* quick_range couldn't use key! */
@@ -7992,9 +8150,12 @@ best_access_path(JOIN      *join,
                 }
               }
             }
-            /* Limit the number of matched rows */
-            tmp= cost_for_index_read(thd, table, key, (ha_rows) records,
-                                     (ha_rows) s->worst_seeks);
+            /* Calculate the cost of the index access */
+            INDEX_READ_COST cost= cost_for_index_read(thd, table, key,
+                                                      (ha_rows) records,
+                                                      (ha_rows) s->worst_seeks);
+            tmp= cost.read_cost;
+            index_only_cost= cost.index_only_cost;
           }
         }
         else
@@ -8060,6 +8221,11 @@ best_access_path(JOIN      *join,
             {
               records= (double) table->opt_range[key].rows;
               tmp= table->opt_range[key].fetch_cost;
+              index_only_cost= table->opt_range[key].index_only_cost;
+              /*
+                TODO: Disable opt_range testing below for this range as we can
+                always use this ref instead.
+              */
               trace_access_idx.add("used_range_estimates", true);
               goto got_cost2;
             }
@@ -8134,7 +8300,7 @@ best_access_path(JOIN      *join,
                          (keyinfo->user_defined_key_parts-1);
                   else
                     records= a;
-                  set_if_bigger(records, 1.0);
+                  set_if_bigger(records, MIN_ROWS_AFTER_FILTERING);
                 }
               }
 
@@ -8173,8 +8339,11 @@ best_access_path(JOIN      *join,
             /* Limit the number of matched rows */
             tmp= records;
             set_if_smaller(tmp, (double) thd->variables.max_seeks_for_key);
-            tmp= cost_for_index_read(thd, table, key, (ha_rows) tmp,
-                                     (ha_rows) s->worst_seeks);
+            INDEX_READ_COST cost= cost_for_index_read(thd, table, key,
+                                                      (ha_rows) tmp,
+                                                      (ha_rows) s->worst_seeks);
+            tmp= cost.read_cost;
+            index_only_cost= cost.index_only_cost;
           }
           else
           {
@@ -8196,75 +8365,56 @@ best_access_path(JOIN      *join,
       if (records == DBL_MAX)                   // Key not usable
         continue;
 
-      startup_cost= s->startup_cost;
       records_after_filter= records;
 
-      /* Check that start_key->key can be used for index access */
-      if (found_part & 1)
+      /*
+        Check that start_key->key can be used for index access
+        Records can be 0 in case of empty tables.
+      */
+      if ((found_part & 1) && records)
       {
-        double rows= record_count * records;
-        double access_cost_factor= MY_MIN(tmp / records, 1.0);
+        /*
+          Cost difference between fetch row with key and index only read.
+          The following formula can be > 1.0 in when range optimizer is used
+          as the range optimizer assumes that the needed key pages are
+          already in memory (because of records_in_range() calls) and
+          sets the io_cost for future index lookup calls is 0.
+        */
         filter=
-          table->best_range_rowid_filter_for_partial_join(start_key->key, rows,
-                                                          access_cost_factor);
+          table->best_range_rowid_filter_for_partial_join(start_key->key,
+                                                          records,
+                                                          tmp,
+                                                          index_only_cost,
+                                                          record_count);
         if (filter)
-	{
-          double new_cost, new_records;
-          bool use_filter;
-          double filter_startup_cost= filter->get_setup_cost();
-          double filter_lookup_cost= records * filter->lookup_cost();
-
-          /* Add cost of checking found rows against filter */
-          new_cost= COST_ADD(tmp, filter_lookup_cost);
-          /* Calculate number of resulting rows after filtering */
-          new_records= records * filter->selectivity;
-          DBUG_ASSERT(new_cost >= 0 && new_records >= 0);
-          use_filter= ((tmp + records/TIME_FOR_COMPARE) * record_count >=
-                       (new_cost + new_records/TIME_FOR_COMPARE)*record_count +
-                       filter_startup_cost);
-
-          if (thd->trace_started())
-          {
-            Json_writer_object trace_filter(thd, "filter");
-            trace_filter.add("rowid_filter_key",
-                             table->key_info[filter->get_key_no()].name).
-              add("original_found_rows_cost", tmp).
-              add("new_found_rows_cost", new_cost).
-              add("orginal_rows", records).
-              add("new_rows", new_records).
-              add("filter_startup_cost", filter_startup_cost).
-              add("filter_lookup_cost", filter_lookup_cost).
-              add("filter_selectivity", filter->selectivity).
-              add("filter_used", use_filter);
-          }
-          if (use_filter)
-          {
-            tmp= new_cost;
-            records_after_filter= new_records;
-            startup_cost+= filter_startup_cost;
-          }
-          else
-            filter= 0;
-        }
+          filter= filter->apply_filter(thd, table, &tmp, &records_after_filter,
+                                       &startup_cost,
+                                       tmp, index_only_cost,
+                                       1, record_count);
       }
       tmp= COST_ADD(tmp, records_after_filter/TIME_FOR_COMPARE);
-      if (unlikely(trace_access_idx.trace_started()))
-          trace_access_idx.
-          add("rows", records).
-          add("found_matching_rows_cost",tmp).
-          add("startup_cost", startup_cost);
-
       tmp= COST_MULT(tmp, record_count);
       tmp= COST_ADD(tmp, startup_cost);
-
       if (unlikely(trace_access_idx.trace_started()))
-        trace_access_idx.add("rows", records_after_filter).add("cost", tmp);
+      {
+        trace_access_idx.
+          add("rows", records_after_filter).
+          add("cost", tmp);
+      }
 
-      if (tmp + 0.0001 < best_cost)
+      /*
+        The COST_EPS is here to ensure we use the first key if there are
+        two 'identical keys' that could be used.
+      */
+      if (tmp + COST_EPS < best_cost)
       {
         trace_access_idx.add("chosen", true);
         best_cost= tmp;
-        best_records= records;
+        /*
+          We use 'records' instead of 'records_after_filter' here as we want
+          to have EXPLAIN print the number of rows found by the key access.
+        */
+        best_records= records;                  // Records before filter!
         best_key= start_key;
         best_max_key_part= max_key_part;
         best_ref_depends_map= found_ref;
@@ -8296,7 +8446,7 @@ best_access_path(JOIN      *join,
      !bitmap_is_clear_all(eq_join_set) &&  !disable_jbuf &&
       (!s->emb_sj_nest ||                     
        join->allowed_semijoin_with_cache) &&    // (1)
-      (!(s->table->map & join->outer_join) ||
+      (!(table->map & join->outer_join) ||
        join->allowed_outer_join_with_cache))    // (2)
   {
     Json_writer_object trace_access_hash(thd);
@@ -8317,14 +8467,7 @@ best_access_path(JOIN      *join,
       tmp= s->quick->read_time;
     }
     else
-    {
-      tmp= s->scan_time();
-      /*
-        Cost of comparing the found row with the attached WHERE
-        This is not part of scan_time()!
-      */
-      tmp= COST_ADD(tmp, s->records / TIME_FOR_COMPARE);
-    }
+      tmp= s->cached_scan_and_compare_time;
 
     /* We read the table as many times as join buffer becomes full. */
     refills= (1.0 + floor((double) cache_record_length(join,idx) *
@@ -8399,16 +8542,16 @@ best_access_path(JOIN      *join,
       !(s->quick &&
         s->quick->get_type() != QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX && // (2)
         best_key && s->quick->index == best_key->key &&      // (2)
-        best_max_key_part >= s->table->opt_range[best_key->key].key_parts) &&// (2)
-      !((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) &&   // (3)
-        ! s->table->covering_keys.is_clear_all() && best_key && !s->quick) &&// (3)
-      !(s->table->force_index && best_key && !s->quick) &&               // (4)
-      !(best_key && s->table->pos_in_table_list->jtbm_subselect))        // (5)
+        best_max_key_part >= table->opt_range[best_key->key].key_parts) &&// (2)
+      !((table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) &&   // (3)
+        ! table->covering_keys.is_clear_all() && best_key && !s->quick) &&// (3)
+      !(table->force_index && best_key && !s->quick) &&               // (4)
+      !(best_key && table->pos_in_table_list->jtbm_subselect))        // (5)
   {                                             // Check full join
-    double rnd_records= matching_candidates_in_table(s, found_constraint,
-                                                      use_cond_selectivity);
+    double rnd_records, records_after_filter, org_records;
     Range_rowid_filter_cost_info *filter= 0;
-    DBUG_ASSERT(rnd_records <= s->records);
+    double startup_cost= s->startup_cost;
+    const char *scan_type= "";
 
     /*
       Range optimizer never proposes a RANGE if it isn't better
@@ -8433,79 +8576,123 @@ best_access_path(JOIN      *join,
       */
       tmp= COST_MULT(s->quick->read_time, record_count);
 
-      if ( s->quick->get_type() == QUICK_SELECT_I::QS_TYPE_RANGE)
+      /*
+        Use record count from range optimizer.
+        This is done to make records found comparable to what we get with
+        'ref' access.
+      */
+      org_records= records_after_filter= rnd_records= s->found_records;
+
+      if (s->quick->get_type() == QUICK_SELECT_I::QS_TYPE_RANGE)
       {
-        double rows= record_count * s->found_records;
-        double access_cost_factor= MY_MIN(tmp / rows, 1.0);
         uint key_no= s->quick->index;
+        TABLE::OPT_RANGE *range= &table->opt_range[key_no];
+
+        /*
+          Ensure that 'range' and 's' are comming from the same source
+          The complex 'double' comparison is there because floating point
+          registers complications when costs are calculated.
+        */
+        DBUG_ASSERT(range->rows == s->found_records);
+        DBUG_ASSERT((range->cost == 0.0 && s->quick->read_time == 0.0) ||
+                     (range->cost / s->quick->read_time <= 1.0000001 &&
+                      range->cost / s->quick->read_time >= 0.9999999));
+
         filter=
-        s->table->best_range_rowid_filter_for_partial_join(key_no, rows,
-                                                           access_cost_factor);
+        table->best_range_rowid_filter_for_partial_join(key_no, range->rows,
+                                                        range->find_cost,
+                                                        range->index_only_cost,
+                                                        record_count);
         if (filter)
         {
-          tmp-= filter->get_adjusted_gain(rows);
-          DBUG_ASSERT(tmp >= 0);
+          double filter_cost= range->fetch_cost;
+          filter= filter->apply_filter(thd, table, &filter_cost,
+                                       &records_after_filter,
+                                       &startup_cost,
+                                       range->fetch_cost,
+                                       range->index_only_cost,
+                                       range->ranges,
+                                       record_count);
+          if (filter)
+          {
+            tmp= filter_cost;
+            /* Filter returns cost without TIME_FOR_COMPARE */
+            tmp= COST_ADD(tmp, records_after_filter / TIME_FOR_COMPARE);
+            tmp= COST_MULT(tmp, record_count);
+            tmp= COST_ADD(tmp, startup_cost);
+            startup_cost= 0;                    // Avoid adding it later
+            table->opt_range[key_no].selectivity= filter->selectivity;
+          }
         }
         type= JT_RANGE;
       }
       else
       {
         type= JT_INDEX_MERGE;
-        best_filter= 0;
       }
       loose_scan_opt.check_range_access(join, idx, s->quick);
     }
     else
     {
+      /* We will now calculate cost of scan, with or without join buffer */
+      rnd_records= matching_candidates_in_table(s, found_constraint,
+                                                use_cond_selectivity);
+      records_after_filter= rnd_records;
+      org_records= s->records;
+      DBUG_ASSERT(rnd_records <= s->records);
+
       /* Estimate cost of reading table. */
-      if (s->table->force_index && !best_key) // index scan
+      if (table->force_index && !best_key)
       {
+        INDEX_READ_COST cost= cost_for_index_read(thd, table, s->ref.key,
+                                                  s->records,
+                                                  s->worst_seeks);
+        /*
+          The query is using 'force_index' and we did not find a usable key.
+          Caclulcate cost of a table scan with the forced index.
+        */
         type= JT_NEXT;
-        tmp= s->table->file->read_time(s->ref.key, 1, s->records);
+        tmp= cost.read_cost;
       }
       else // table scan
       {
-        tmp= s->scan_time();
+        tmp= s->cached_scan_time;
         type= JT_ALL;
       }
 
-      if ((s->table->map & join->outer_join) || disable_jbuf)
+      if ((table->map & join->outer_join) || disable_jbuf)
       {
-        double cmp_time;
         /*
           Simple scan
 
           For each record we have to:
-          - Read the whole table record
-          - Compare with the current where clause with only fields for the
-            table
-          - Compare with the full where and skip rows which does not satisfy
-            the join condition
+          - Read the table record
+          - Compare with the current WHERE clause
+          We estmate that 'rnd_records' will survive this check.
         */
         /* Calculate cost of checking the attached WHERE */
-        cmp_time= s->records/TIME_FOR_COMPARE;
-        tmp= COST_ADD(tmp, cmp_time);
+        tmp= s->cached_scan_and_compare_time;
+        scan_type= "scan";
+
         /*
           If this is not the first table we have to compare the rows against
           all previous row combinations
         */
         if (idx != join->const_tables)
-        {
-          /* Calculate cost of checking matched rows against the join cache */
-          cmp_time= rnd_records/TIME_FOR_COMPARE;
-          tmp= COST_ADD(tmp, cmp_time);
-          /* We do the above for every row in the cache */
           tmp= COST_MULT(tmp, record_count);
-        }
       }
       else
       {
         /* Scan trough join cache */
         double cmp_time, refills;
 
-        /* Calculate cost of checking the attached WHERE */
-        cmp_time= s->records / TIME_FOR_COMPARE;
-        tmp= COST_ADD(tmp, cmp_time);
+        /*
+          Calculate cost of checking the the WHERE for this table.
+          This is done before we check the TABLE rows aginst the rows
+          in the join cache.
+        */
+        tmp= s->cached_scan_and_compare_time;
+        scan_type= "scan_with_join_cache";
 
         /* Calculate cost of refills */
         refills= (1.0 + floor((double) cache_record_length(join,idx) *
@@ -8513,34 +8700,41 @@ best_access_path(JOIN      *join,
                                (double) thd->variables.join_buff_size)));
         tmp= COST_MULT(tmp, refills);
 
-        /* Cost of compare matching rows against the rows in the join cache */
-        cmp_time= (rnd_records * record_count / TIME_FOR_COMPARE);
+        /* We come here only if there are already rows in the join cache */
+        DBUG_ASSERT(idx != join->const_tables);
+        /*
+          Cost of moving each row from each previous table from the join cache
+          to it's table record and comparing it with the found and accepted row.
+        */
+        cmp_time= (rnd_records * record_count *
+                   (RECORD_COPY_COST * (idx - join->const_tables) +
+                    1 / TIME_FOR_COMPARE));
         tmp= COST_ADD(tmp, cmp_time);
       }
     }
 
-    trace_access_scan.add("access_type", type == JT_ALL ?
-                                         "scan" :
-                                         join_type_str[type]);
     /* Splitting technique cannot be used with join cache */
-    if (s->table->is_splittable())
-      tmp+= s->table->get_materialization_cost();
-    else
-      tmp+= s->startup_cost;
+    if (table->is_splittable())
+      startup_cost= table->get_materialization_cost();
+    tmp+= startup_cost;
 
-    best_filter_cmp_gain= (best_filter ?
-                           best_filter->get_cmp_gain(record_count * records) :
-                           0);
     if (unlikely(trace_access_scan.trace_started()))
+    {
       trace_access_scan.
-        add("resulting_rows", rnd_records).
+        add("access_type",
+            type == JT_ALL ? scan_type : join_type_str[type]).
+        add("rows",              org_records).
+        add("rows_after_scan",   rnd_records).
+        add("rows_after_filter", records_after_filter).
         add("cost", tmp);
+      if (type == JT_ALL)
+      {
+        trace_access_scan.add("index_only",
+                              (s->cached_covering_key != MAX_KEY));
+      }
+    }
 
-    /* TODO: Document the following if */
-    if (best_cost == DBL_MAX ||
-        tmp <
-        (best_key->is_for_hash_join() ? best_cost :
-         COST_ADD(best_cost,-best_filter_cmp_gain)))
+    if (tmp + COST_EPS < best_cost)
     {
       /*
         If the table has a range (s->quick is set) make_join_select()
@@ -8556,12 +8750,14 @@ best_access_path(JOIN      *join,
       best_filter= filter;
       /* range/index_merge/ALL/index access method are "independent", so: */
       best_ref_depends_map= 0;
-      best_uses_jbuf= MY_TEST(!disable_jbuf && !((s->table->map &
+      best_uses_jbuf= MY_TEST(!disable_jbuf && !((table->map &
                                                   join->outer_join)));
       spl_plan= 0;
       best_type= type;
+      trace_access_scan.add("chosen", true);
     }
-    trace_access_scan.add("chosen", best_key == NULL);
+    else
+      trace_access_scan.add("chosen", false);
   }
   else
   {
@@ -8587,7 +8783,7 @@ best_access_path(JOIN      *join,
 
   if (!best_key &&
       idx == join->const_tables &&
-      s->table == join->sort_by_table &&
+      table == join->sort_by_table &&
       join->unit->lim.get_select_limit() >= records)
   {
     trace_access_scan.add("use_tmp_table", true);
@@ -9091,12 +9287,7 @@ optimize_straight_join(JOIN *join, table_map join_tables)
 
     /* compute the cost of the new plan extended with 's' */
     record_count= COST_MULT(record_count, position->records_read);
-    const double filter_cmp_gain= position->range_rowid_filter_info
-      ? position->range_rowid_filter_info->get_cmp_gain(record_count)
-      : 0;
-    read_time+= COST_ADD(read_time - filter_cmp_gain,
-                         COST_ADD(position->read_time,
-                                  record_count / TIME_FOR_COMPARE));
+    read_time+= COST_ADD(read_time, position->read_time);
     advance_sj_state(join, join_tables, idx, &record_count, &read_time,
                      &loose_scan_pos);
 
@@ -9115,7 +9306,7 @@ optimize_straight_join(JOIN *join, table_map join_tables)
   memcpy((uchar*) join->best_positions, (uchar*) join->positions,
          sizeof(POSITION)*idx);
   join->join_record_count= record_count;
-  join->best_read= read_time - 0.001;
+  join->best_read= read_time;
 }
 
 
@@ -9287,9 +9478,7 @@ greedy_search(JOIN      *join,
 
     /* compute the cost of the new plan extended with 'best_table' */
     record_count= COST_MULT(record_count, join->positions[idx].records_read);
-    read_time= COST_ADD(read_time,
-                         COST_ADD(join->positions[idx].read_time,
-                                  record_count / TIME_FOR_COMPARE));
+    read_time= COST_ADD(read_time, join->positions[idx].read_time);
 
     remaining_tables&= ~(best_table->table->map);
     --size_remain;
@@ -9397,9 +9586,7 @@ void JOIN::get_partial_cost_and_fanout(int end_tab_idx,
     if (tab->records_read && (cur_table_map & filter_map))
     {
       record_count= COST_MULT(record_count, tab->records_read);
-      read_time= COST_ADD(read_time,
-                          COST_ADD(tab->read_time,
-                                   record_count / TIME_FOR_COMPARE));
+      read_time= COST_ADD(read_time, tab->read_time);
       if (tab->emb_sj_nest)
         sj_inner_fanout= COST_MULT(sj_inner_fanout, tab->records_read);
 				     }
@@ -9414,7 +9601,7 @@ void JOIN::get_partial_cost_and_fanout(int end_tab_idx,
     if (tab == end_tab)
       break;
   }
-  *read_time_arg= read_time;// + record_count / TIME_FOR_COMPARE;
+  *read_time_arg= read_time;
   *record_count_arg= record_count;
 }
 
@@ -9443,9 +9630,8 @@ void JOIN::get_prefix_cost_and_fanout(uint n_tables,
       record_count= COST_MULT(record_count, best_positions[i].records_read);
       read_time= COST_ADD(read_time, best_positions[i].read_time);
     }
-    /* TODO: Take into account condition selectivities here */
   }
-  *read_time_arg= read_time;// + record_count / TIME_FOR_COMPARE;
+  *read_time_arg= read_time;
   *record_count_arg= record_count;
 }
 
@@ -9640,7 +9826,7 @@ double table_cond_selectivity(JOIN *join, uint idx, JOIN_TAB *s,
   Field *field;
   TABLE *table= s->table;
   MY_BITMAP *read_set= table->read_set;
-  double sel= s->table->cond_selectivity;
+  double sel= table->cond_selectivity;
   POSITION *pos= &join->positions[idx];
   uint keyparts= 0;
   uint found_part_ref_or_null= 0;
@@ -10044,7 +10230,6 @@ best_extension_by_limited_search(JOIN      *join,
     {
       double current_record_count, current_read_time;
       double partial_join_cardinality;
-      double filter_cmp_gain;
       double pushdown_cond_selectivity;
       POSITION loose_scan_pos, *position= join->positions + idx;
 
@@ -10061,14 +10246,7 @@ best_extension_by_limited_search(JOIN      *join,
 
       /* Compute the cost of extending the plan with 's' */
       current_record_count= COST_MULT(record_count, position->records_read);
-      filter_cmp_gain= position->range_rowid_filter_info ?
-        position->range_rowid_filter_info->get_cmp_gain(current_record_count) :
-        0;
-      current_read_time=COST_ADD(read_time,
-                                 COST_ADD(position->read_time -
-                                          filter_cmp_gain,
-                                          current_record_count /
-                                          TIME_FOR_COMPARE));
+      current_read_time= COST_ADD(read_time, position->read_time);
 
       if (unlikely(trace_one_table.trace_started()))
       {
@@ -10080,7 +10258,7 @@ best_extension_by_limited_search(JOIN      *join,
                        &current_read_time, &loose_scan_pos);
 
       /* Expand only partial plans with lower cost than the best QEP so far */
-      if (current_read_time >= join->best_read)
+      if (current_read_time + COST_EPS >= join->best_read)
       {
         DBUG_EXECUTE("opt", print_plan(join, idx+1,
                                        current_record_count,
@@ -10187,7 +10365,7 @@ best_extension_by_limited_search(JOIN      *join,
           memcpy((uchar*) join->best_positions, (uchar*) join->positions,
                  sizeof(POSITION) * (idx + 1));
           join->join_record_count= partial_join_cardinality;
-          join->best_read= current_read_time - 0.001;
+          join->best_read= current_read_time;
         }
         DBUG_EXECUTE("opt", print_plan(join, idx+1,
                                        current_record_count,
@@ -12177,7 +12355,9 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
 	  }
 	  tab->quick=0;
 	}
-	uint ref_key= sel->head? (uint) sel->head->reginfo.join_tab->ref.key+1 : 0;
+	uint ref_key= (sel->head ?
+                       (uint) sel->head->reginfo.join_tab->ref.key+1 :
+                       0);
 	if (i == join->const_tables && ref_key)
 	{
 	  if (!tab->const_keys.is_clear_all() &&
@@ -12286,9 +12466,9 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
 			     (sel->quick_keys.is_clear_all() ||
                               (sel->quick && 
                                sel->quick->read_time > 
-                               tab->table->file->scan_time() + 
-                               tab->table->file->stats.records/TIME_FOR_COMPARE
-                               ))) ?
+                               tab->table->file->
+                               ha_scan_and_compare_time(tab->table->file->
+                                                        stats.records)))) ?
 	      2 : 1;
 	    sel->read_tables= used_tables & ~current_map;
             sel->quick_keys.clear_all();
@@ -13773,7 +13953,10 @@ make_join_readinfo(JOIN *join, ulonglong options, uint no_jbuf_after)
                 tab->index= table->s->primary_key;
               else
 #endif
+              {
                 tab->index=find_shortest_key(table, & table->covering_keys);
+                DBUG_ASSERT(tab->index == tab->cached_covering_key);
+              }
             }
 	    tab->read_first_record= join_read_first;
             /* Read with index_first / index_next */
@@ -13999,7 +14182,7 @@ void JOIN_TAB::cleanup()
         end_read_record(&read_record);
         tmp->jtbm_subselect->cleanup();
         /* 
-          The above call freed the materializedd temptable. Set it to NULL so
+          The above call freed the materialized temptable. Set it to NULL so
           that we don't attempt to touch it if JOIN_TAB::cleanup() is invoked
           multiple times (it may be)
         */
@@ -14023,47 +14206,60 @@ void JOIN_TAB::cleanup()
 /**
   Estimate the time to get rows of the joined table
 
-  Note that this doesn't take into account of checking the WHERE clause
-  for all found rows (TIME_FOR_COMPARE)
+  Updates found_records, records, cached_scan_time, cached_covering_key,
+  read_time and cache_scan_and_compare_time
 */
 
-double JOIN_TAB::scan_time()
+void JOIN_TAB::estimate_scan_time()
 {
-  double res;
+  double copy_cost= RECORD_COPY_COST;
+
+  cached_covering_key= MAX_KEY;
   if (table->is_created())
   {
     if (table->is_filled_at_execution())
     {
       get_delayed_table_estimates(table, &records, &read_time,
                                   &startup_cost);
-      found_records= records;
       table->opt_range_condition_rows= records;
+      table->used_stat_records= records;
     }
     else
     {
-      found_records= records= table->stat_records();
-      read_time= table->file->scan_time();
+      records= table->stat_records();
       /*
         table->opt_range_condition_rows has already been set to
         table->file->stats.records
       */
+      DBUG_ASSERT(table->opt_range_condition_rows == records);
+
+      if (!table->covering_keys.is_clear_all() && ! table->no_keyread)
+      {
+        cached_covering_key= find_shortest_key(table, &table->covering_keys);
+        read_time= table->file->ha_key_scan_time(cached_covering_key);
+        copy_cost= INDEX_COPY_COST;
+      }
+      else
+        read_time= table->file->ha_scan_and_copy_time(records);
     }
-    res= read_time;
   }
   else
   {
-    found_records= records=table->stat_records();
-    read_time= found_records ? (double)found_records: 10.0;// TODO:fix this stub
-    res= read_time;
+    records= table->stat_records();
+    DBUG_ASSERT(table->opt_range_condition_rows == records);
+    read_time= records ? (double) records: 10.0;// TODO:fix this stub
   }
-  return res;
+  found_records= records;
+  cached_scan_time= read_time;
+  cached_scan_and_compare_time= (read_time + records *
+                                 (copy_cost + 1/TIME_FOR_COMPARE));
 }
 
 
 /**
-  Estimate the number of rows that a an access method will read from a table.
+  Estimate the number of rows that an access method will read from a table.
 
-  @todo: why not use JOIN_TAB::found_records
+  @todo: why not use JOIN_TAB::found_records or JOIN_TAB::records_read
 */
 
 ha_rows JOIN_TAB::get_examined_rows()
@@ -15966,7 +16162,7 @@ static COND *build_equal_items(JOIN *join, COND *cond,
         table->on_expr= build_equal_items(join, table->on_expr, inherited,
                                           nested_join_list, ignore_on_conds,
                                           &table->cond_equal);
-        if (unlikely(join->thd->trace_started()))
+        if (unlikely(thd->trace_started()))
         {
           const char *table_name;
           if (table->nested_join)
@@ -17558,7 +17754,6 @@ void optimize_wo_join_buffering(JOIN *join, uint first_tab, uint last_tab,
     reopt_remaining_tables &= ~rs->table->map;
     rec_count= COST_MULT(rec_count, pos.records_read);
     cost= COST_ADD(cost, pos.read_time);
-    cost= COST_ADD(cost, rec_count / TIME_FOR_COMPARE);
     //TODO: take into account join condition selectivity here
     double pushdown_cond_selectivity= 1.0;
     table_map real_table_bit= rs->table->map;
@@ -21704,15 +21899,7 @@ join_read_const_table(THD *thd, JOIN_TAB *tab, POSITION *pos)
   }
   else
   {
-    if (/*!table->file->key_read && */
-        table->covering_keys.is_set(tab->ref.key) && !table->no_keyread &&
-        (int) table->reginfo.lock_type <= (int) TL_READ_HIGH_PRIORITY)
-    {
-      table->file->ha_start_keyread(tab->ref.key);
-      tab->index= tab->ref.key;
-    }
     error=join_read_const(tab);
-    table->file->ha_end_keyread();
     if (unlikely(error))
     {
       tab->info= ET_UNIQUE_ROW_NOT_FOUND;
@@ -21833,10 +22020,20 @@ join_read_const(JOIN_TAB *tab)
       error=HA_ERR_KEY_NOT_FOUND;
     else
     {
-      error= table->file->ha_index_read_idx_map(table->record[0],tab->ref.key,
-                                                (uchar*) tab->ref.key_buff,
-                                                make_prev_keypart_map(tab->ref.key_parts),
-                                                HA_READ_KEY_EXACT);
+      handler *file= table->file;
+      if (table->covering_keys.is_set(tab->ref.key) && !table->no_keyread &&
+          (int) table->reginfo.lock_type <= (int) TL_READ_HIGH_PRIORITY)
+      {
+        file->ha_start_keyread(tab->ref.key);
+        /* This is probably needed for analyze table */
+        tab->index= tab->ref.key;
+      }
+      error= file->
+        ha_index_read_idx_map(table->record[0],tab->ref.key,
+                              (uchar*) tab->ref.key_buff,
+                              make_prev_keypart_map(tab->ref.key_parts),
+                              HA_READ_KEY_EXACT);
+      file->ha_end_keyread();
     }
     if (unlikely(error))
     {
@@ -23684,7 +23881,7 @@ uint find_shortest_key(TABLE *table, const key_map *usable_keys)
     {
       if (usable_keys->is_set(nr))
       {
-        double cost= table->file->keyread_time(nr, 1, table->file->records());
+        double cost= table->file->ha_key_scan_time(nr);
         if (cost < min_cost)
         {
           min_cost= cost;
@@ -27164,7 +27361,7 @@ bool JOIN_TAB::save_explain_data(Explain_table_access *eta,
   my_bool key_read;
   char table_name_buffer[SAFE_NAME_LEN];
   KEY *key_info= 0;
-  uint key_len= 0;
+  uint key_len= 0, used_index= MAX_KEY;
 
 #ifdef NOT_YET
   /*
@@ -27316,11 +27513,13 @@ bool JOIN_TAB::save_explain_data(Explain_table_access *eta,
 
   if (tab_type == JT_NEXT)
   {
+    used_index= index;
     key_info= table->key_info+index;
     key_len= key_info->key_length;
   }
   else if (ref.key_parts)
   {
+    used_index= ref.key;
     key_info= get_keyinfo_by_key_no(ref.key);
     key_len= ref.key_length;
   }
@@ -27370,6 +27569,7 @@ bool JOIN_TAB::save_explain_data(Explain_table_access *eta,
 
   if (tab_type == JT_HASH_NEXT) /* full index scan + hash join */
   {
+    used_index= index;
     eta->hash_next_key.set(thd->mem_root, 
                            & table->key_info[index], 
                            table->key_info[index].key_length);
@@ -27430,10 +27630,12 @@ bool JOIN_TAB::save_explain_data(Explain_table_access *eta,
     if (examined_rows)
     {
       double pushdown_cond_selectivity= cond_selectivity;
-      if (pushdown_cond_selectivity == 1.0)
-        f= (float) (100.0 * records_read / examined_rows);
-      else
+      if (pushdown_cond_selectivity != 1.0)
         f= (float) (100.0 * pushdown_cond_selectivity);
+      else if (range_rowid_filter_info)
+        f= (float) (100.0 * range_rowid_filter_info->selectivity);
+      else
+        f= (float) (100.0 * records_read / examined_rows);
     }
     set_if_smaller(f, 100.0);
     eta->filtered_set= true;
@@ -27442,8 +27644,8 @@ bool JOIN_TAB::save_explain_data(Explain_table_access *eta,
 
   /* Build "Extra" field and save it */
   key_read= table->file->keyread_enabled();
-  if ((tab_type == JT_NEXT || tab_type == JT_CONST) &&
-      table->covering_keys.is_set(index))
+  if ((tab_type == JT_NEXT || tab_type == JT_CONST) && used_index != MAX_KEY &&
+      table->covering_keys.is_set(used_index))
     key_read=1;
   if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT &&
       !((QUICK_ROR_INTERSECT_SELECT*)cur_quick)->need_to_fetch_row)
@@ -28875,22 +29077,23 @@ void JOIN::cache_const_exprs()
   @param  read_time OUT    Cost of reading using quick or ref(const) access.
 
 
-  @return 
+  @return
     true   There was a possible quick or ref access, its cost is in the OUT
            parameters.
-    false  No quick or ref(const) possible (and so, the caller will attempt 
+    false  No quick or ref(const) possible (and so, the caller will attempt
            to use a full index scan on this index).
 */
 
-static bool get_range_limit_read_cost(const JOIN_TAB *tab, 
-                                      const TABLE *table, 
+static bool get_range_limit_read_cost(const JOIN_TAB *tab,
+                                      const TABLE *table,
                                       ha_rows table_records,
                                       uint keynr,
                                       ha_rows rows_limit,
-                                      double *read_time)
+                                      double *read_time,
+                                      double *read_rows)
 {
   bool res= false;
-  /* 
+  /*
     We need to adjust the estimates if we had a quick select (or ref(const)) on
     index keynr.
   */
@@ -28901,10 +29104,10 @@ static bool get_range_limit_read_cost(const JOIN_TAB *tab,
       full index scan/cost.
     */
     double best_rows= (double) table->opt_range[keynr].rows;
-    double best_cost= (double) table->opt_range[keynr].cost;
-    
+    double best_cost= (double) table->opt_range[keynr].fetch_cost;
+
     /*
-      Check if ref(const) access was possible on this index. 
+      Check if ref(const) access was possible on this index.
     */
     if (tab)
     {
@@ -28916,13 +29119,13 @@ static bool get_range_limit_read_cost(const JOIN_TAB *tab,
         if (!(table->const_key_parts[keynr] & map))
           break;
       }
-      
+
       if (kp > 0)
       {
         ha_rows ref_rows;
         /*
           Two possible cases:
-          1. ref(const) uses the same #key parts as range access. 
+          1. ref(const) uses the same #key parts as range access.
           2. ref(const) uses fewer key parts, becasue there is a
             range_cond(key_part+1).
         */
@@ -28933,12 +29136,13 @@ static bool get_range_limit_read_cost(const JOIN_TAB *tab,
 
         if (ref_rows > 0)
         {
-          double tmp= cost_for_index_read(tab->join->thd, table, keynr,
-                                          ref_rows,
-                                          (ha_rows) tab->worst_seeks);
-          if (tmp < best_cost)
+          INDEX_READ_COST cost= cost_for_index_read(tab->join->thd, table,
+                                                    keynr,
+                                                    ref_rows,
+                                                    (ha_rows) tab->worst_seeks);
+          if (cost.read_cost < best_cost)
           {
-            best_cost= tmp;
+            best_cost= cost.read_cost;
             best_rows= (double)ref_rows;
           }
         }
@@ -28974,13 +29178,15 @@ static bool get_range_limit_read_cost(const JOIN_TAB *tab,
       /*
         LIMIT clause specifies that we will need to read fewer records than
         quick select will return. Assume that quick select's cost is
-        proportional to the number of records we need to return (e.g. if we 
+        proportional to the number of records we need to return (e.g. if we
         only need 1/3rd of records, it will cost us 1/3rd of quick select's
         read time)
       */
       best_cost *= rows_limit_for_quick / best_rows;
+      best_rows = rows_limit_for_quick;
     }
-    *read_time= best_cost;
+    *read_time= best_cost + best_rows/TIME_FOR_COMPARE;
+    *read_rows= best_rows;
     res= true;
   }
   return res;
@@ -28988,7 +29194,7 @@ static bool get_range_limit_read_cost(const JOIN_TAB *tab,
 
 
 /**
-  Find a cheaper access key than a given @a key
+  Find a cheaper access key than a given key
 
   @param          tab                 NULL or JOIN_TAB of the accessed table
   @param          order               Linked list of ORDER BY arguments
@@ -29092,13 +29298,12 @@ test_if_cheaper_ordering(const JOIN_TAB *tab, ORDER *order, TABLE *table,
     }
   }
   else
-    read_time= table->file->scan_time();        // TODO: Add TIME_FOR_COMPARE
-  
+    read_time= table->file->ha_scan_and_compare_time(table_records);
+
   trace_cheaper_ordering.add("fanout", fanout);
   /*
     TODO: add cost of sorting here.
   */
-  read_time += COST_EPS;
   trace_cheaper_ordering.add("read_time", read_time);
   /*
     Calculate the selectivity of the ref_key for REF_ACCESS. For
@@ -29284,6 +29489,17 @@ test_if_cheaper_ordering(const JOIN_TAB *tab, ORDER *order, TABLE *table,
         possible_key.add("updated_limit", select_limit);
         rec_per_key= keyinfo->actual_rec_per_key(keyinfo->user_defined_key_parts-1);
         set_if_bigger(rec_per_key, 1);
+#ifndef OLD_CODE
+        {
+          INDEX_READ_COST cost= cost_for_index_read(table->in_use, table, nr,
+                                                    select_limit,
+                                                    tab ?
+                                                    (ha_rows) tab->worst_seeks :
+                                                    HA_ROWS_MAX);
+          index_scan_time= (cost.read_cost +
+                            select_limit / TIME_FOR_COMPARE);
+        }
+#else
         /*
           Here we take into account the fact that rows are
           accessed in sequences rec_per_key records in each.
@@ -29291,28 +29507,21 @@ test_if_cheaper_ordering(const JOIN_TAB *tab, ORDER *order, TABLE *table,
           by rowid/primary key. When reading the data
           in a sequence we'll touch not more pages than the
           table file contains.
-          TODO. Use the formula for a disk sweep sequential access
-          to calculate the cost of accessing data rows for one 
-          index entry.
         */
-#ifdef NEED_TESTING
-        index_scan_time= (cost_for_index_read(table->in_use, table, nr,
-                                              select_limit,
-                                              (ha_rows) tab->worst_seeks) +
-                          select_limit / TIME_FOR_COMPARE);
-#else
         index_scan_time= (select_limit/rec_per_key *
-                          MY_MIN(rec_per_key, table->file->scan_time()));
+                          MY_MIN(rec_per_key, table->file->ha_scan_time()));
 #endif
-        double range_scan_time;
+        possible_key.add("index_scan_cost", index_scan_time);
+        double range_scan_time, range_rows;
         if (get_range_limit_read_cost(tab, table, table_records, nr,
-                                      select_limit, &range_scan_time))
+                                      select_limit,
+                                      &range_scan_time,
+                                      &range_rows))
         {
-          possible_key.add("range_scan_time", range_scan_time);
+          possible_key.add("range_scan_cost", range_scan_time);
           if (range_scan_time < index_scan_time)
             index_scan_time= range_scan_time;
         }
-        possible_key.add("index_scan_time", index_scan_time);
 
         if ((ref_key < 0 && (group || table->force_index || is_covering)) ||
             index_scan_time < read_time)
@@ -29342,7 +29551,7 @@ test_if_cheaper_ordering(const JOIN_TAB *tab, ORDER *order, TABLE *table,
           }
           if (table->opt_range_keys.is_set(nr))
             quick_records= table->opt_range[nr].rows;
-          possible_key.add("records", quick_records);
+          possible_key.add("rows", quick_records);
           if (best_key < 0 ||
               (select_limit <= MY_MIN(quick_records,best_records) ?
                keyinfo->user_defined_key_parts < best_key_parts :
@@ -29375,21 +29584,21 @@ test_if_cheaper_ordering(const JOIN_TAB *tab, ORDER *order, TABLE *table,
             possible_key.add("cause", cause);
           }
         }
-        else
+        else if (unlikely(possible_key.trace_started()))
         {
           possible_key.
             add("usable", false).
             add("cause", "cost");
         }
       }
-      else
+      else if (unlikely(possible_key.trace_started()))
       {
         possible_key.add("usable", false);
         if (!group && select_limit == HA_POS_ERROR)
           possible_key.add("cause", "order by without limit");
       }
     }
-    else
+    else if (unlikely(possible_key.trace_started()))
     {
       if (keys.is_set(nr))
       {