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)
- Fixed that we don't calculate TIME_FOR_COMPARE twice for some plans,
like in optimize_straight_join() and greedy_search()
- 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 calculation are done the same way and
more close to 'range' calculations. The effects of this change are:
- Cost of index scan is now lower than before, which causes some
tests result to change. (innodb.innodb, main.show_explain)
- Fixed the EQ_REF takes into account clustered and covered keys.
- 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).
- 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_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() to is like ha_scan_time() but also
adds the cost of checking the where clause (TIME_FOR_COMPARE).
- Cost of index scan was too low before compared to anything else.
- 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.
- All of the above caused some index_merge combinations to be
rejected because of cost (main.index_intersect)
- Added checking of the WHERE clause of the accepted rows to ROR costs in
get_best_ror_intersect()
- 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.
- 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.
- 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)
- 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().
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)
Calculate index_only_cost correctly for all ref accesses
fetch_cost and index_only_cost now takes into account clustered keys and
index only accesses.
Before the index_only_cost was not correctly taken into account
when considering a filter. When using filter, not matching rows will
only do a index only access.
In the result files, many of the changes are going back to 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).
Other things:
- cost_for_index_read now returns both full cost and index_only_cost
- Ensure that access_cost_factor, used by
best_range_rowid_filter_for_partial_join() is between 0 and 1
(as documented).
This patch causes no changes in costs or result files.
Changes:
- Store row compare cost separately in Cost_estimate::comp_cost
- Store cost of fetching rows separately in OPT_RANGE
- Use range->fetch_cost instead of adjust_quick_cost(total_cost)
This was done to simplify cost calculation in sql_select.cc:
- We can use range->fetch_cost directly without having to call
adjust_quick_cost(). adjust_quick_cost() is now removed.
Other things:
- Removed some not used functions in Cost_estimate
startup_cost is the cost of a creating a temporary table (if needed)
Best_cost now includes the cost of comparing all WHERE clauses and also
cost of joining with previous row combinations.
Other things:
- Optimizer trace is now printing the total costs, including testing the
WHERE clause (TIME_FOR_COMPARE) and comparing with all previous rows.
- In optimizer trace, include also total cost of query together with the
final join order. This makes it easier to find out where the cost was
calculated.
- Old code used filter even if the cost for it was higher than not using a
filter. This is not corrected.
Adjust costs for doing index scan in cost_group_min_max()
The idea is that when doing a tree dive (once per group), we need to
compare key values, which is fast. For each new group, we have to
compare the full where clause for the row.
Compared to original code, the cost of group_min_max() has slightly
increased which affects some test with only a few rows.
main.group_min_max and main.distinct have been modified to show the
effect of the change.
The patch also adjust the number of groups in case of quick selects:
- For simple WHERE clauses, ensure that we have at least as many groups
as we have conditions on the used group-by key parts.
The assumption is that each condition will create at least one group.
- Ensure that there are no more groups than rows found by quick_select
Test changes:
- For some small tables there has been a change of
Using index for group-by -> Using index for group-by (scanning)
Range -> Index and Using index for group-by -> Using index
Return >= 1 from matching_candidates_in_table if records > 0.0
Having rows >= 1.0 helps ensure that when we calculate total rows of joins
the number of resulting rows will not be less after the join.
Changes in test cases:
- Join order change for some tables with few records
- 'Filtered' is much higher for tables with few rows, as 1 row is a high
procent of a table with few rows.
Update matching_candidates_in_table() to treat all conditions similar
Fixed also that the 'with_found_constraint parameter' to
matching_candidates_in_table() is as documented: It is now true only
if there is a reference to a previous table in the WHERE condition for
the current examined table (as it was originally documented)
Changes in test results:
- Filtered was 25% smaller for some queries (expected).
- Some join order changed (probably because the tables had very few rows).
- Some more table scans, probably because there would be fewer returned
rows.
- Some tests exposes a bug that if there is more filtered rows, then the
cost for table scan will be higher. This will be fixed in a later commit.
calculate_cond_selectivity_for_table() is largely rewritten:
- Process keys in the order of rows found, smaller ranges first. If two ranges
has equal number of rows, use the one with more key parts. This helps
us to mark more used fields to not be used for further selectivity
calculations. See cmp_quick_ranges().
- Ignore keys with fields that where used by previous keys
- Don't use rec_per_key[] to calculate selectivity for smaller
secondary key parts. This does not work as rec_per_key[] value
is calculated in the context of the previous key parts, not for the
key part itself. The one exception is if the previous key parts
is a constant.
Other things:
- Ensure that select->cond_selectivity is always between 0 and 1.
- Ensure that select->opt_range_condition_rows is never updated to
a higher value. It is initially set to the number of rows in table.
- We know store in table->opt_range_condition_rows the lowest number of
rows that any row-read-method has found so far. Before it was only done
for UICK_SELECT_I::QS_TYPE_ROR_UNION and QUICK_SELECT_I::QS_TYPE_INDEX_MERGE.
Now it is done for a lot more methods. See
calculate_cond_selectivity_for_table() for details.
- Calculate and use selectivity for the first key part of a multiple key part
if the first key part is a constant.
WHERE key1_part1=5 and key2_part1=5. IF key1 is used, then we can still
use selectivity for key2
Changes in test results:
- 'filtered' is slighly changed, usually to something slightly smaller
- A few cases where for group by queries the table order changed. This was
because the number of resulting rows from a group by query with MIN/MAX
is now set to be smaller.
- A few index was changed as we know prefer index with more key parts if
the number of resulting rows is the same.
