diff options
Diffstat (limited to 'sql')
| -rw-r--r-- | sql/filesort.cc | 13 | ||||
| -rw-r--r-- | sql/ha_partition.cc | 9 | ||||
| -rw-r--r-- | sql/handler.cc | 33 | ||||
| -rw-r--r-- | sql/handler.h | 221 | ||||
| -rw-r--r-- | sql/multi_range_read.cc | 60 | ||||
| -rw-r--r-- | sql/my_json_writer.h | 2 | ||||
| -rw-r--r-- | sql/mysqld.cc | 5 | ||||
| -rw-r--r-- | sql/opt_range.cc | 230 | ||||
| -rw-r--r-- | sql/opt_split.cc | 22 | ||||
| -rw-r--r-- | sql/opt_subselect.cc | 300 | ||||
| -rw-r--r-- | sql/opt_subselect.h | 4 | ||||
| -rw-r--r-- | sql/opt_trace.cc | 5 | ||||
| -rw-r--r-- | sql/rowid_filter.cc | 76 | ||||
| -rw-r--r-- | sql/rowid_filter.h | 30 | ||||
| -rw-r--r-- | sql/set_var.cc | 1 | ||||
| -rw-r--r-- | sql/set_var.h | 1 | ||||
| -rw-r--r-- | sql/sql_base.cc | 1 | ||||
| -rw-r--r-- | sql/sql_class.h | 9 | ||||
| -rw-r--r-- | sql/sql_const.h | 88 | ||||
| -rw-r--r-- | sql/sql_select.cc | 771 | ||||
| -rw-r--r-- | sql/sql_select.h | 31 | ||||
| -rw-r--r-- | sql/sys_vars.cc | 45 | ||||
| -rw-r--r-- | sql/table.cc | 6 | ||||
| -rw-r--r-- | sql/table.h | 44 |
24 files changed, 1351 insertions, 656 deletions
diff --git a/sql/filesort.cc b/sql/filesort.cc index 07194cb2e4f..988df356348 100644 --- a/sql/filesort.cc +++ b/sql/filesort.cc @@ -1584,6 +1584,10 @@ static bool check_if_pq_applicable(Sort_param *param, // Can we fit all the keys in memory? if (param->max_keys_per_buffer < num_available_keys) { + /* + Get cost of merge sort. Note that this does not include + scanning the table and comparing the rows with the where clause! + */ const double sort_merge_cost= get_merge_many_buffs_cost_fast(num_rows, num_available_keys, @@ -1591,17 +1595,12 @@ static bool check_if_pq_applicable(Sort_param *param, /* PQ has cost: (insert + qsort) * log(queue size) / TIME_FOR_COMPARE_ROWID + - cost of file lookup afterwards. - The lookup cost is a bit pessimistic: we take scan_time and assume - that on average we find the row after scanning half of the file. - A better estimate would be lookup cost, but note that we are doing - random lookups here, rather than sequential scan. + cost of rowid lookup of the original row to find the addon fields. */ const double pq_cpu_cost= (PQ_slowness * num_rows + param->max_keys_per_buffer) * log((double) param->max_keys_per_buffer) / TIME_FOR_COMPARE_ROWID; - const double pq_io_cost= - param->max_rows * table->file->scan_time() / 2.0; + const double pq_io_cost= table->file->ha_read_with_rowid(param->max_rows); const double pq_cost= pq_cpu_cost + pq_io_cost; if (sort_merge_cost < pq_cost) diff --git a/sql/ha_partition.cc b/sql/ha_partition.cc index f17abed82ff..46793c2b119 100644 --- a/sql/ha_partition.cc +++ b/sql/ha_partition.cc @@ -9636,6 +9636,15 @@ double ha_partition::scan_time() i < m_tot_parts; i= bitmap_get_next_set(&m_part_info->read_partitions, i)) scan_time+= m_file[i]->scan_time(); + if (m_tot_parts) + { + /* + Add TABLE_SCAN_SETUP_COST for partitions to make cost similar to + in ha_scan_time() + */ + scan_time+= (TABLE_SCAN_SETUP_COST * avg_io_cost() * (m_tot_parts - 1) / + optimizer_cache_cost); + } DBUG_RETURN(scan_time); } diff --git a/sql/handler.cc b/sql/handler.cc index 4d53c3e8424..02753f24812 100644 --- a/sql/handler.cc +++ b/sql/handler.cc @@ -3208,20 +3208,45 @@ LEX_CSTRING *handler::engine_name() by index 'keyno' of one range containing 'rows' key entries. If ranges == 0 then the function returns only the cost of copying those key entries into the engine buffers. + + This function doesn't take in account into copying the key to record + (INDEX_COPY_COST) or comparing the key to the where clause (TIME_FOR_COMPARE) */ double handler::keyread_time(uint index, uint ranges, ha_rows rows) { + size_t len; + double cost; DBUG_ASSERT(ranges == 0 || ranges == 1); - size_t len= table->key_info[index].key_length + ref_length; + len= table->key_info[index].key_length + ref_length; if (table->file->is_clustering_key(index)) len= table->s->stored_rec_length; - double cost= (double)rows*len/(stats.block_size+1)*IDX_BLOCK_COPY_COST; + + cost= ((double)rows*len/(stats.block_size+1)*INDEX_BLOCK_COPY_COST); + /* + We divide the cost with optimizer_cache_cost as ha_keyread_time() + and ha_key_scan_time() will multiply the result value with + optimizer_cache_cost and we want to keep the above 'memory operation' + cost unaffected by this multiplication. + */ + cost/= optimizer_cache_cost; if (ranges) { uint keys_per_block= (uint) (stats.block_size*3/4/len+1); - ulonglong blocks= (rows+ keys_per_block- 1)/keys_per_block; - cost+= blocks; + /* + We let the cost grow slowly in proportion to number of rows to + promote indexes with less rows. + We do not calculate exact number of block reads as then index + only reads will be more costly than normal reads, especially + compared to InnoDB clustered keys. + + INDEX_LOOKUP_COST is the cost of finding the first key in the + range. Finding the next key is usually a fast operation so we + don't count it here, it is taken into account in + ha_keyread_and_copy_time() + */ + cost+= (((double) (rows / keys_per_block) + INDEX_LOOKUP_COST) * + avg_io_cost()); } return cost; } diff --git a/sql/handler.h b/sql/handler.h index d41b14d82c0..c9707185b45 100644 --- a/sql/handler.h +++ b/sql/handler.h @@ -2850,10 +2850,11 @@ public: double avg_io_cost; /* cost of an average I/O oper. to fetch records */ double idx_io_count; /* number of I/O to read keys */ double idx_avg_io_cost; /* cost of an average I/O oper. to fetch records */ - double cpu_cost; /* total cost of operations in CPU */ - double idx_cpu_cost; /* cost of operations in CPU for index */ + double cpu_cost; /* Cost of reading the rows based on a key */ + double idx_cpu_cost; /* Cost of reading the key from the index tree */ double import_cost; /* cost of remote operations */ double comp_cost; /* Cost of comparing found rows with WHERE clause */ + double copy_cost; /* Copying the data to 'record' */ double mem_cost; /* cost of used memory */ static constexpr double IO_COEFF= 1; @@ -2866,16 +2867,24 @@ public: reset(); } + /* + Total cost for the range + Note that find_cost() + compare_cost() + data_copy_cost() == total_cost() + */ + double total_cost() const { return IO_COEFF*io_count*avg_io_cost + IO_COEFF*idx_io_count*idx_avg_io_cost + - CPU_COEFF*(cpu_cost + idx_cpu_cost + comp_cost) + + CPU_COEFF*(cpu_cost + idx_cpu_cost + comp_cost + copy_cost) + MEM_COEFF*mem_cost + IMPORT_COEFF*import_cost; } - /* Cost of fetching a row */ - double fetch_cost() const + /* + Cost of fetching a key and use the key to find a row (if not clustered or + covering key). Does not include row copy or compare with WHERE clause. + */ + double find_cost() const { return IO_COEFF*io_count*avg_io_cost + IO_COEFF*idx_io_count*idx_avg_io_cost + @@ -2885,37 +2894,33 @@ public: /* Cost of comparing the row with the WHERE clause - Note that fetch_cost() + compare_cost() == total_cost() */ - double compare_cost() const + inline double compare_cost() const { return CPU_COEFF*comp_cost; } + /* + Cost of copying the row or key to 'record' + */ + inline double data_copy_cost() const + { + return CPU_COEFF*copy_cost; + } + /* Cost of finding an index entry, without copying or comparing it */ double index_only_cost() { return IO_COEFF*idx_io_count*idx_avg_io_cost + CPU_COEFF*idx_cpu_cost; } - /** - Whether or not all costs in the object are zero - - @return true if all costs are zero, false otherwise - */ - bool is_zero() const - { - return io_count == 0.0 && idx_io_count == 0.0 && cpu_cost == 0.0 && - import_cost == 0.0 && mem_cost == 0.0 && comp_cost; - } - - void reset() + inline void reset() { avg_io_cost= 1.0; idx_avg_io_cost= 1.0; io_count= idx_io_count= cpu_cost= idx_cpu_cost= mem_cost= import_cost= - comp_cost= 0.0; + comp_cost= copy_cost= 0.0; } void multiply(double m) @@ -3287,6 +3292,11 @@ public: ulonglong rows_changed; /* One bigger than needed to avoid to test if key == MAX_KEY */ ulonglong index_rows_read[MAX_KEY+1]; + /* + Cost of using key/record cache: (100-cache_hit_ratio)/100 + Updated from THD in open_tables() + */ + double optimizer_cache_cost; ha_copy_info copy_info; private: @@ -3419,6 +3429,7 @@ public: ref_length(sizeof(my_off_t)), ft_handler(0), inited(NONE), pre_inited(NONE), pushed_cond(0), next_insert_id(0), insert_id_for_cur_row(0), + optimizer_cache_cost((100-CACHE_HIT_RATIO)/100.0), tracker(NULL), pushed_idx_cond(NULL), pushed_idx_cond_keyno(MAX_KEY), @@ -3538,14 +3549,15 @@ public: int ha_delete_row(const uchar * buf); void ha_release_auto_increment(); - bool keyread_enabled() { return keyread < MAX_KEY; } - int ha_start_keyread(uint idx) + inline bool keyread_enabled() { return keyread < MAX_KEY; } + inline int ha_start_keyread(uint idx) { - int res= keyread_enabled() ? 0 : extra_opt(HA_EXTRA_KEYREAD, idx); + if (keyread_enabled()) + return 0; keyread= idx; - return res; + return extra_opt(HA_EXTRA_KEYREAD, idx); } - int ha_end_keyread() + inline int ha_end_keyread() { if (!keyread_enabled()) return 0; @@ -3643,17 +3655,48 @@ public: } /* - Time for a full table scan of data file + Time for a full table data scan. To be overrided by engines, should not + be used by the sql level. */ +protected: virtual double scan_time() { - return ((ulonglong2double(stats.data_file_length) / stats.block_size + 2) * + return (((ulonglong2double(stats.data_file_length) / stats.block_size)) * avg_io_cost()); } +public: - virtual double key_scan_time(uint index) + inline double ha_scan_time() { - return keyread_time(index, 1, records()); + return (scan_time() * optimizer_cache_cost + + TABLE_SCAN_SETUP_COST * avg_io_cost()); + } + + /* + Time for a full table scan + fetching the rows from the table + + @param records Number of records from the engine or records from + status tables stored by ANALYZE TABLE. + + The TABLE_SCAN_SETUP_COST is there to prefer range scans to full + table scans. This is mainly to make the test suite happy as + many tests has very few rows. In real life tables has more than + a few rows and the extra cost has no practical effect. + */ + + inline double ha_scan_and_copy_time(ha_rows records) + { + return (ha_scan_time() + (double) records * RECORD_COPY_COST); + } + + /* + Time for a full table scan, fetching the rows from the table and comparing + the row with the where clause + */ + inline double ha_scan_and_compare_time(ha_rows records) + { + return (ha_scan_time() + + (double) records * (RECORD_COPY_COST + 1/TIME_FOR_COMPARE)); } virtual double avg_io_cost() @@ -3661,6 +3704,11 @@ public: return 1.0; } + virtual void set_optimizer_cache_cost(double cost) + { + optimizer_cache_cost= cost; + } + /** The cost of reading a set of ranges from the table using an index to access it. @@ -3672,18 +3720,114 @@ public: This method can be used to calculate the total cost of scanning a table using an index by calling it using read_time(index, 1, table_size). + + This function is to be reimplemented by engines (if needed). The sql_level + should call ha_read_time(), ha_read_and_copy_time() or + ha_read_and_compare_time(). */ +protected: virtual double read_time(uint index, uint ranges, ha_rows rows) - { return rows2double(ranges+rows); } + { + return ((rows2double(rows) * ROW_LOOKUP_COST + + rows2double(ranges) * INDEX_LOOKUP_COST) * avg_io_cost()); + } +public: + + /* Same as above, but take into account CACHE_COST */ + inline double ha_read_time(uint index, uint ranges, ha_rows rows) + { + return read_time(index, ranges, rows) * optimizer_cache_cost; + } + + /* Same as above, but take into account also copying of the row to 'record' */ + inline double ha_read_and_copy_time(uint index, uint ranges, ha_rows rows) + { + return (ha_read_time(index, ranges, rows) + + rows2double(rows) * RECORD_COPY_COST); + } + + /* Same as above, but take into account also copying and comparing the row */ + inline double ha_read_and_compare_time(uint index, uint ranges, ha_rows rows) + { + return (ha_read_time(index, ranges, rows) + + rows2double(rows) * (RECORD_COPY_COST + 1/TIME_FOR_COMPARE)); + } + + /* Cost of reading a row with rowid */ +protected: + virtual double read_with_rowid(ha_rows rows) + { + return rows2double(rows) * ROW_LOOKUP_COST * avg_io_cost(); + } +public: + /* + Same as above, but take into account cache_cost and copying of the row + to 'record'. + Note that this should normally be same as ha_read_time(some_key, 0, rows) + */ + inline double ha_read_with_rowid(ha_rows rows) + { + return (read_with_rowid(rows) * optimizer_cache_cost + + rows2double(rows) * RECORD_COPY_COST); + } /** - Calculate cost of 'keyread' scan for given index and number of records. + Calculate cost of 'index_only' scan for given index and number of records. + + @param index Index to read + @param flag If flag == 1 then the function returns the cost of + index only scan by index 'index' of one range containing + 'rows' key entries. + If flag == 0 then function returns only the cost of copying + those key entries into the engine buffers. + @param rows #of records to read + */ +protected: + virtual double keyread_time(uint index, uint flag, ha_rows rows); +public: + + /* + Calculate cost of 'keyread' scan for given index and number of records + including fetching the key to the 'record' buffer. + */ + + inline double ha_keyread_time(uint index, uint flag, ha_rows rows) + { + return (keyread_time(index, flag, rows) * optimizer_cache_cost); + } + + /* Same as above, but take into account copying the key the the SQL layer */ + inline double ha_keyread_and_copy_time(uint index, uint flag, ha_rows rows) + { + return ha_keyread_time(index, flag, rows) + (double) rows * INDEX_COPY_COST; + } - @param index index to read - @param ranges #of ranges to read - @param rows #of records to read + /* + Time for a full table index scan (without copy or compare cost). + To be overrided by engines, sql level should use ha_key_scan_time(). */ - virtual double keyread_time(uint index, uint ranges, ha_rows rows); +protected: + virtual double key_scan_time(uint index) + { + return keyread_time(index, 1, records()); + } +public: + + /* Cost of doing a full index scan */ + inline double ha_key_scan_time(uint index) + { + return (key_scan_time(index) * optimizer_cache_cost); + } + + /* + Cost of doing a full index scan with record copy and compare + @param rows Rows from stat tables + */ + inline double ha_key_scan_and_compare_time(uint index, ha_rows rows) + { + return (ha_key_scan_time(index) + + (double) rows * (INDEX_COPY_COST + 1/TIME_FOR_COMPARE)); + } virtual const key_map *keys_to_use_for_scanning() { return &key_map_empty; } @@ -4832,7 +4976,6 @@ private: } } -private: void mark_trx_read_write_internal(); bool check_table_binlog_row_based_internal(); @@ -5192,6 +5335,12 @@ protected: void set_ha_share_ptr(Handler_share *arg_ha_share); void lock_shared_ha_data(); void unlock_shared_ha_data(); + + /* + Mroonga needs to call read_time() directly for it's internal handler + methods + */ + friend class ha_mroonga; }; #include "multi_range_read.h" diff --git a/sql/multi_range_read.cc b/sql/multi_range_read.cc index 3f8f2aea742..6c8a8bba7c1 100644 --- a/sql/multi_range_read.cc +++ b/sql/multi_range_read.cc @@ -300,20 +300,33 @@ handler::multi_range_read_info_const(uint keyno, RANGE_SEQ_IF *seq, if (total_rows != HA_POS_ERROR) { + double io_cost= avg_io_cost(); + double range_lookup_cost= (io_cost * INDEX_LOOKUP_COST * + optimizer_cache_cost); set_if_smaller(total_rows, max_rows); /* The following calculation is the same as in multi_range_read_info(): */ *flags |= HA_MRR_USE_DEFAULT_IMPL; cost->reset(); - cost->avg_io_cost= cost->idx_avg_io_cost= avg_io_cost(); + cost->avg_io_cost= cost->idx_avg_io_cost= io_cost; if (!is_clustering_key(keyno)) { cost->idx_io_count= (double) io_blocks; - cost->idx_cpu_cost= (keyread_time(keyno, 0, total_rows) + - n_ranges * IDX_LOOKUP_COST); if (!(*flags & HA_MRR_INDEX_ONLY)) - cost->cpu_cost= read_time(keyno, 0, total_rows); + { + cost->idx_cpu_cost= (ha_keyread_time(keyno, 1, total_rows) + + (n_ranges-1) * range_lookup_cost); + cost->cpu_cost= ha_read_time(keyno, 0, total_rows); + cost->copy_cost= rows2double(total_rows) * RECORD_COPY_COST; + } + else + { + /* Index only read */ + cost->idx_cpu_cost= (ha_keyread_time(keyno, 1, total_rows) + + (n_ranges-1) * range_lookup_cost); + cost->copy_cost= rows2double(total_rows) * INDEX_COPY_COST; + } } else { @@ -323,9 +336,10 @@ handler::multi_range_read_info_const(uint keyno, RANGE_SEQ_IF *seq, ranges used by read_time to the number of dives. */ io_blocks+= unassigned_single_point_ranges; - cost->idx_cpu_cost= n_ranges * IDX_LOOKUP_COST; uint limited_ranges= (uint) MY_MIN((ulonglong) n_ranges, io_blocks); - cost->cpu_cost= read_time(keyno, limited_ranges, total_rows); + cost->idx_cpu_cost= limited_ranges * range_lookup_cost; + cost->cpu_cost= ha_read_time(keyno, 0, total_rows); + cost->copy_cost= rows2double(total_rows) * RECORD_COPY_COST; } cost->comp_cost= (rows2double(total_rows) / TIME_FOR_COMPARE + MULTI_RANGE_READ_SETUP_COST); @@ -394,21 +408,35 @@ ha_rows handler::multi_range_read_info(uint keyno, uint n_ranges, uint n_rows, /* Produce the same cost as non-MRR code does */ if (!is_clustering_key(keyno)) { + double range_lookup_cost= (avg_io_cost() * INDEX_LOOKUP_COST * + optimizer_cache_cost); /* idx_io_count could potentially be increased with the number of index leaf blocks we have to read for finding n_rows. */ cost->idx_io_count= n_ranges; - cost->idx_cpu_cost= (keyread_time(keyno, 0, n_rows) + - n_ranges * IDX_LOOKUP_COST); if (!(*flags & HA_MRR_INDEX_ONLY)) { + cost->idx_cpu_cost= (keyread_time(keyno, 1, n_rows) + + (n_ranges-1) * range_lookup_cost); cost->cpu_cost= read_time(keyno, 0, n_rows); + cost->copy_cost= rows2double(n_rows) * RECORD_COPY_COST; + } + else + { + /* + Same as above, but take into account copying the key to the upper level. + */ + cost->idx_cpu_cost= (keyread_time(keyno, 1, n_rows) + + (n_ranges-1) * range_lookup_cost); + cost->copy_cost= rows2double(n_rows) * INDEX_COPY_COST; } } else { - cost->cpu_cost= read_time(keyno, n_ranges, (uint)n_rows); + /* Clustering key */ + cost->cpu_cost= read_time(keyno, n_ranges, n_rows); + cost->copy_cost= rows2double(n_rows) * RECORD_COPY_COST; } cost->comp_cost= rows2double(n_rows) / TIME_FOR_COMPARE; return 0; @@ -2012,7 +2040,7 @@ bool DsMrr_impl::get_disk_sweep_mrr_cost(uint keynr, ha_rows rows, uint flags, cost->mem_cost= (double)rows_in_last_step * elem_size; /* Total cost of all index accesses */ - index_read_cost= primary_file->keyread_time(keynr, 1, rows); + index_read_cost= primary_file->ha_keyread_and_copy_time(keynr, 1, rows); cost->add_io(index_read_cost, 1 /* Random seeks */); return FALSE; } @@ -2099,10 +2127,14 @@ void get_sweep_read_cost(TABLE *table, ha_rows nrows, bool interrupted, DBUG_ENTER("get_sweep_read_cost"); cost->reset(); +#ifndef OLD_SWEEP_COST + cost->cpu_cost= table->file->ha_read_with_rowid(nrows); + cost->avg_io_cost= table->file->avg_io_cost(); +#else if (table->file->pk_is_clustering_key(table->s->primary_key)) { - cost->cpu_cost= table->file->read_time(table->s->primary_key, - (uint) nrows, nrows); + cost->cpu_cost= table->file->ha_read_and_copy_time(table->s->primary_key, + (uint) nrows, nrows); } else if ((cost->avg_io_cost= table->file->avg_io_cost()) >= 0.999) { @@ -2124,7 +2156,9 @@ void get_sweep_read_cost(TABLE *table, ha_rows nrows, bool interrupted, DISK_SEEK_PROP_COST*n_blocks/busy_blocks); } } - DBUG_PRINT("info",("returning cost=%g", cost->total_cost())); + cost->cpu_cost+= rows2double(n_rows) * RECORD_COPY_COST; +#endif + DBUG_PRINT("info",("returning cost: %g", cost->total_cost())); DBUG_VOID_RETURN; } diff --git a/sql/my_json_writer.h b/sql/my_json_writer.h index d82313f996f..f651edc196c 100644 --- a/sql/my_json_writer.h +++ b/sql/my_json_writer.h @@ -341,7 +341,7 @@ public: #endif } - bool trace_started() const + inline bool trace_started() const { return my_writer != 0; } diff --git a/sql/mysqld.cc b/sql/mysqld.cc index 93a548b476e..178bb7fdb25 100644 --- a/sql/mysqld.cc +++ b/sql/mysqld.cc @@ -753,8 +753,6 @@ char *opt_relay_logname = 0, *opt_relaylog_index_name=0; char *opt_logname, *opt_slow_logname, *opt_bin_logname; char *opt_binlog_index_name=0; - - /* Static variables */ my_bool opt_stack_trace; @@ -4322,7 +4320,6 @@ static int init_common_variables() return 1; } - #ifdef WITH_WSREP /* We need to initialize auxiliary variables, that will be @@ -8984,7 +8981,7 @@ void refresh_status(THD *thd) /* Add thread's status variabes to global status */ add_to_status(&global_status_var, &thd->status_var); - /* Reset thread's status variables */ + /* Reset thread's status vajoinriables */ thd->set_status_var_init(); thd->status_var.global_memory_used= 0; bzero((uchar*) &thd->org_status_var, sizeof(thd->org_status_var)); diff --git a/sql/opt_range.cc b/sql/opt_range.cc index e9560debe3e..dbb8a743ef7 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -412,7 +412,6 @@ static bool eq_tree(SEL_ARG* a,SEL_ARG *b); SEL_ARG null_element(SEL_ARG::IMPOSSIBLE); static bool null_part_in_key(KEY_PART *key_part, const uchar *key, uint length); -static bool is_key_scan_ror(PARAM *param, uint keynr, uint8 nparts); static SEL_ARG *enforce_sel_arg_weight_limit(RANGE_OPT_PARAM *param, uint keyno, @@ -2320,6 +2319,7 @@ public: struct st_ror_scan_info *cpk_scan; /* Clustered PK scan, if there is one */ bool is_covering; /* TRUE if no row retrieval phase is necessary */ double index_scan_costs; /* SUM(cost(index_scan)) */ + double cmp_cost; // Cost of out rows with WHERE clause void trace_basic_info(PARAM *param, Json_writer_object *trace_object) const; }; @@ -2679,7 +2679,6 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use, bool only_single_index_range_scan) { uint idx; - double scan_time; Item *notnull_cond= NULL; TABLE_READ_PLAN *best_trp= NULL; SEL_ARG **backup_keys= 0; @@ -2707,20 +2706,23 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use, only_single_index_range_scan= 1; if (head->force_index || force_quick_range) - scan_time= read_time= DBL_MAX; + read_time= DBL_MAX; else { - scan_time= rows2double(records) / TIME_FOR_COMPARE; + read_time= head->file->ha_scan_and_compare_time(records); + /* - The 2 is there to prefer range scans to full table scans. - This is mainly to make the test suite happy as many tests has - very few rows. In real life tables has more than a few rows and the - +2 has no practical effect. + Force the detection of range access if LIMIT is used. + The idea is that we want to store all possible range + accesses to see if we can use them to resolve an ORDER BY. + Ranges with too high costs will be pruned in best_access_path(). + + The test for read_time is there only to not modify read_time if + ha_scan_and_copy_time() returned a really big value */ - read_time= (double) head->file->scan_time() + scan_time + 2; - if (limit < records && read_time < (double) records + scan_time + 1 ) + if (limit < records && read_time < (double) records * 2) { - read_time= (double) records + scan_time + 1; // Force to use index + read_time= (double) records * 2; // Force to use index notnull_cond= NULL; } } @@ -2863,8 +2865,9 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use, if (!force_quick_range && !head->covering_keys.is_clear_all()) { int key_for_use= find_shortest_key(head, &head->covering_keys); - double key_read_time= (head->file->key_scan_time(key_for_use) + - rows2double(records) / TIME_FOR_COMPARE); + double key_read_time; + key_read_time= head->file->ha_key_scan_and_compare_time(key_for_use, + records); DBUG_PRINT("info", ("'all'+'using index' scan will be using key %d, " "read time %g", key_for_use, key_read_time)); @@ -2972,8 +2975,8 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use, if ((rori_trp= get_best_ror_intersect(¶m, tree, best_read_time, &can_build_covering))) { - best_trp= rori_trp; - best_read_time= best_trp->read_cost; + best_trp= rori_trp; + best_read_time= rori_trp->read_cost; /* Try constructing covering ROR-intersect only if it looks possible and worth doing. @@ -2997,10 +3000,9 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use, if ((intersect_trp= get_best_index_intersect(¶m, tree, best_read_time))) { - best_trp= intersect_trp; - best_read_time= best_trp->read_cost; - set_if_smaller(param.table->opt_range_condition_rows, - intersect_trp->records); + best_trp= intersect_trp; + best_read_time= intersect_trp->read_cost; + param.table->set_opt_range_condition_rows(intersect_trp->records); } } @@ -3019,8 +3021,7 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use, { new_conj_trp= get_best_disjunct_quick(¶m, imerge, best_read_time); if (new_conj_trp) - set_if_smaller(param.table->opt_range_condition_rows, - new_conj_trp->records); + param.table->set_opt_range_condition_rows(new_conj_trp->records); if (new_conj_trp && (!best_conj_trp || new_conj_trp->read_cost < best_conj_trp->read_cost)) @@ -3048,7 +3049,7 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use, { /* mark that we are changing opt_range_condition_rows */ group_by_optimization_used= 1; - set_if_smaller(param.table->opt_range_condition_rows, group_trp->records); + param.table->set_opt_range_condition_rows(group_trp->records); DBUG_PRINT("info", ("table_rows: %llu opt_range_condition_rows: %llu " "group_trp->records: %ull", table_records, param.table->opt_range_condition_rows, @@ -3400,7 +3401,11 @@ bool calculate_cond_selectivity_for_table(THD *thd, TABLE *table, Item **cond) } if (!*cond || table->pos_in_table_list->schema_table) + { + table->set_cond_selectivity(table->opt_range_condition_rows / + table_records); DBUG_RETURN(FALSE); + } /* This should be pre-alloced so that we could use the same bitmap for all @@ -3548,12 +3553,6 @@ end_of_range_loop: table_records); if (original_selectivity < table->cond_selectivity) { - DBUG_ASSERT(quick && - (quick->group_by_optimization_used || - quick->get_type() == QUICK_SELECT_I::QS_TYPE_INDEX_INTERSECT || - quick->get_type() == QUICK_SELECT_I::QS_TYPE_ROR_UNION || - quick->get_type() == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE || - quick->get_type() == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT)); table->cond_selectivity= original_selectivity; if (unlikely(thd->trace_started())) { @@ -5058,17 +5057,24 @@ static void dbug_print_singlepoint_range(SEL_ARG **start, uint num) Get cost of 'sweep' full records retrieval. SYNOPSIS get_sweep_read_cost() - param Parameter from test_quick_select - records # of records to be retrieved + param Parameter from test_quick_select + records # of records to be retrieved + add_time_for_compare If set, add cost of WHERE clause (TIME_FOR_COMPARE) RETURN cost of sweep */ -double get_sweep_read_cost(const PARAM *param, ha_rows records) +static double get_sweep_read_cost(const PARAM *param, ha_rows records, + bool add_time_for_compare) { + DBUG_ENTER("get_sweep_read_cost"); +#ifndef OLD_SWEEP_COST + DBUG_RETURN(param->table->file->ha_read_with_rowid(records) + + (add_time_for_compare ? records / TIME_FOR_COMPARE : 0)); +#else double result; uint pk= param->table->s->primary_key; - DBUG_ENTER("get_sweep_read_cost"); + if (param->table->file->pk_is_clustering_key(pk) || param->table->file->stats.block_size == 0 /* HEAP */) { @@ -5076,12 +5082,12 @@ double get_sweep_read_cost(const PARAM *param, ha_rows records) We are using the primary key to find the rows. Calculate the cost for this. */ - result= param->table->file->read_time(pk, (uint)records, records); + result= table->file->ha_read_with_rowid(records); } else { /* - Rows will be retreived with rnd_pos(). Caluclate the expected + Rows will be retreived with rnd_pos(). Calculate the expected cost for this. */ double n_blocks= @@ -5114,9 +5120,11 @@ double get_sweep_read_cost(const PARAM *param, ha_rows records) */ result= busy_blocks; } + result+= rows2double(n_rows) * RECORD_COPY_COST; } DBUG_PRINT("return",("cost: %g", result)); DBUG_RETURN(result); +#endif /* OLD_SWEEP_COST */ } @@ -5269,7 +5277,7 @@ TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge, imerge_cost += (*cur_child)->read_cost; all_scans_ror_able &= ((*ptree)->n_ror_scans > 0); all_scans_rors &= (*cur_child)->is_ror; - if (param->table->file->is_clustering_key(param->real_keynr[(*cur_child)->key_idx])) + if (param->table->file->is_clustering_key(keynr_in_table)) { cpk_scan= cur_child; cpk_scan_records= (*cur_child)->records; @@ -5333,7 +5341,8 @@ TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge, /* Calculate cost(rowid_to_row_scan) */ { - double sweep_cost= get_sweep_read_cost(param, non_cpk_scan_records); + /* imerge_cost already includes TIME_FOR_COMPARE */ + double sweep_cost= get_sweep_read_cost(param, non_cpk_scan_records, 0); imerge_cost+= sweep_cost; trace_best_disjunct. add("records", non_cpk_scan_records). @@ -5442,29 +5451,27 @@ skip_to_ror_scan: { /* Ok, we have index_only cost, now get full rows scan cost */ cost= param->table->file-> - read_time(param->real_keynr[(*cur_child)->key_idx], 1, - (*cur_child)->records) + - rows2double((*cur_child)->records) / TIME_FOR_COMPARE; + ha_read_and_compare_time(param->real_keynr[(*cur_child)->key_idx], 1, + (*cur_child)->records); } else cost= read_time; TABLE_READ_PLAN *prev_plan= *cur_child; - if (!(*cur_roru_plan= get_best_ror_intersect(param, *ptree, cost, - &dummy))) + TRP_ROR_INTERSECT *ror_trp; + if (!(*cur_roru_plan= ror_trp= get_best_ror_intersect(param, *ptree, cost, + &dummy))) { - if (prev_plan->is_ror) - *cur_roru_plan= prev_plan; - else + if (!prev_plan->is_ror) DBUG_RETURN(imerge_trp); + *cur_roru_plan= prev_plan; roru_index_costs += (*cur_roru_plan)->read_cost; } else - roru_index_costs += - ((TRP_ROR_INTERSECT*)(*cur_roru_plan))->index_scan_costs; + roru_index_costs += ror_trp->index_scan_costs; roru_total_records += (*cur_roru_plan)->records; - roru_intersect_part *= (*cur_roru_plan)->records / - param->table->stat_records(); + roru_intersect_part *= ((*cur_roru_plan)->records / + param->table->stat_records()); } trace_analyze_ror.end(); /* @@ -5485,10 +5492,10 @@ skip_to_ror_scan: */ double roru_total_cost; - roru_total_cost= roru_index_costs + - rows2double(roru_total_records)*log((double)n_child_scans) / - (TIME_FOR_COMPARE_ROWID * M_LN2) + - get_sweep_read_cost(param, roru_total_records); + roru_total_cost= (roru_index_costs + + rows2double(roru_total_records)*log((double)n_child_scans) / + (TIME_FOR_COMPARE_ROWID * M_LN2) + + get_sweep_read_cost(param, roru_total_records, 0)); DBUG_PRINT("info", ("ROR-union: cost %g, %zu members", roru_total_cost, n_child_scans)); @@ -5521,7 +5528,7 @@ skip_to_ror_scan: SYNOPSIS merge_same_index_scans() param Context info for the operation - imerge IN/OUT SEL_IMERGE from which imerge_trp has been extracted + imerge IN/OUT SEL_IMERGE from which imerge_trp has been extracted imerge_trp The index merge plan where index scans for the same indexes are to be merges read_time The upper bound for the cost of the plan to be evaluated @@ -5914,11 +5921,11 @@ bool prepare_search_best_index_intersect(PARAM *param, continue; } - cost= table->opt_range[(*index_scan)->keynr].index_only_cost; + cost= table->opt_range[(*index_scan)->keynr].index_only_fetch_cost(); idx_scan.add("cost", cost); - if (cost >= cutoff_cost) + if (cost + COST_EPS >= cutoff_cost) { if (unlikely(idx_scan.trace_started())) idx_scan.add("chosen", false).add("cause", "cost"); @@ -5976,7 +5983,7 @@ bool prepare_search_best_index_intersect(PARAM *param, return TRUE; common->best_uses_cpk= FALSE; - common->best_cost= cutoff_cost + COST_EPS; + common->best_cost= cutoff_cost; common->best_length= 0; if (!(common->best_intersect= @@ -6398,7 +6405,7 @@ bool check_index_intersect_extension(PARTIAL_INDEX_INTERSECT_INFO *curr, if (cost >= cutoff_cost) return FALSE; - cost+= get_sweep_read_cost(common_info->param, records); + cost+= get_sweep_read_cost(common_info->param, records, 1); next->cost= cost; next->length= curr->length+1; @@ -6499,7 +6506,6 @@ TRP_INDEX_INTERSECT *get_best_index_intersect(PARAM *param, SEL_TREE *tree, TRP_INDEX_INTERSECT *intersect_trp= NULL; TABLE *table= param->table; THD *thd= param->thd; - DBUG_ENTER("get_best_index_intersect"); Json_writer_object trace_idx_interect(thd, "analyzing_sort_intersect"); @@ -6567,7 +6573,7 @@ TRP_INDEX_INTERSECT *get_best_index_intersect(PARAM *param, SEL_TREE *tree, { intersect_trp->read_cost= common.best_cost; - intersect_trp->records= common.best_records; + intersect_trp->records= common.best_records; intersect_trp->range_scans= range_scans; intersect_trp->range_scans_end= cur_range; intersect_trp->filtered_scans= common.filtered_scans; @@ -6676,7 +6682,8 @@ ROR_SCAN_INFO *make_ror_scan(const PARAM *param, int idx, SEL_ARG *sel_arg) ror queue. */ ror_scan->index_read_cost= - param->table->file->keyread_time(ror_scan->keynr, 1, ror_scan->records); + param->table->file->ha_keyread_and_copy_time(ror_scan->keynr, 1, + ror_scan->records); DBUG_RETURN(ror_scan); } @@ -7037,8 +7044,8 @@ static bool ror_intersect_add(ROR_INTERSECT_INFO *info, each record of every scan. Assuming 1/TIME_FOR_COMPARE_ROWID per check this gives us: */ - const double idx_cost= rows2double(info->index_records) / - TIME_FOR_COMPARE_ROWID; + const double idx_cost= (rows2double(info->index_records) / + TIME_FOR_COMPARE_ROWID); info->index_scan_costs+= idx_cost; trace_costs->add("index_scan_cost", idx_cost); } @@ -7062,13 +7069,15 @@ static bool ror_intersect_add(ROR_INTERSECT_INFO *info, if (!info->is_covering) { double sweep_cost= get_sweep_read_cost(info->param, - double2rows(info->out_rows)); + double2rows(info->out_rows), 1); info->total_cost+= sweep_cost; trace_costs->add("disk_sweep_cost", sweep_cost); DBUG_PRINT("info", ("info->total_cost= %g", info->total_cost)); } else + { trace_costs->add("disk_sweep_cost", static_cast<longlong>(0)); + } DBUG_PRINT("info", ("New out_rows: %g", info->out_rows)); DBUG_PRINT("info", ("New cost: %g, %scovering", info->total_cost, @@ -7147,7 +7156,7 @@ TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree, bool *are_all_covering) { uint idx; - double min_cost= DBL_MAX; + double min_cost= DBL_MAX, cmp_cost; THD *thd= param->thd; DBUG_ENTER("get_best_ror_intersect"); DBUG_PRINT("enter", ("opt_range_condition_rows: %llu cond_selectivity: %g", @@ -7263,12 +7272,18 @@ TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree, *(intersect_scans_end++)= *(cur_ror_scan++); + /* + Check if intersect gives a lower cost. + The first ror scan is always accepted. + The next ror scan is only accepted if the total cost went down + (Enough rows where reject to offset the intersect cost) + */ if (intersect->total_cost < min_cost) { /* Local minimum found, save it */ + min_cost= intersect->total_cost; ror_intersect_cpy(intersect_best, intersect); intersect_scans_best= intersect_scans_end; - min_cost = intersect->total_cost; trace_idx.add("chosen", true); } else @@ -7309,10 +7324,11 @@ TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree, if (ror_intersect_add(intersect, cpk_scan, &trace_cpk, TRUE) && (intersect->total_cost < min_cost)) { + min_cost= intersect->total_cost; if (trace_cpk.trace_started()) - trace_cpk. - add("clustered_pk_scan_added_to_intersect", true). - add("cumulated_cost", intersect->total_cost); + trace_cpk. + add("clustered_pk_scan_added_to_intersect", true). + add("cumulated_cost", intersect->total_cost); intersect_best= intersect; //just set pointer here } else @@ -7334,12 +7350,20 @@ TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree, } trace_cpk.end(); + /* + Adjust row count and add the cost of comparing the final rows to the + WHERE clause + */ + cmp_cost= intersect_best->out_rows/TIME_FOR_COMPARE; + /* Ok, return ROR-intersect plan if we have found one */ TRP_ROR_INTERSECT *trp= NULL; - if (min_cost < read_time && (cpk_scan || best_num > 1)) + if (min_cost + cmp_cost < read_time && (cpk_scan || best_num > 1)) { + double best_rows= double2rows(intersect_best->out_rows); + set_if_bigger(best_rows, 1); if (!(trp= new (param->mem_root) TRP_ROR_INTERSECT)) - DBUG_RETURN(trp); + DBUG_RETURN(NULL); if (!(trp->first_scan= (ROR_SCAN_INFO**)alloc_root(param->mem_root, sizeof(ROR_SCAN_INFO*)*best_num))) @@ -7347,12 +7371,8 @@ TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree, memcpy(trp->first_scan, intersect_scans, best_num*sizeof(ROR_SCAN_INFO*)); trp->last_scan= trp->first_scan + best_num; trp->is_covering= intersect_best->is_covering; - trp->read_cost= intersect_best->total_cost; - /* Prevent divisons by zero */ - ha_rows best_rows = double2rows(intersect_best->out_rows); - if (!best_rows) - best_rows= 1; - set_if_smaller(param->table->opt_range_condition_rows, best_rows); + trp->read_cost= min_cost + cmp_cost; + param->table->set_opt_range_condition_rows(best_rows); trp->records= best_rows; trp->index_scan_costs= intersect_best->index_scan_costs; trp->cpk_scan= cpk_scan; @@ -7370,12 +7390,11 @@ TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree, { trace_ror. add("chosen", false). - add("cause", (read_time >= min_cost) - ? "too few indexes to merge" - : "cost"); + add("cause", (min_cost + cmp_cost >= read_time) ? + "cost" : "too few indexes to merge"); } - DBUG_PRINT("enter", ("opt_range_condition_rows: %llu", - (ulonglong) param->table->opt_range_condition_rows)); + DBUG_PRINT("exit", ("opt_range_condition_rows: %llu", + (ulonglong) param->table->opt_range_condition_rows)); DBUG_RETURN(trp); } @@ -7447,7 +7466,7 @@ TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param, DBUG_RETURN(0); bitmap_clear_all(covered_fields); - double total_cost= 0.0f; + double total_cost= 0.0; ha_rows records=0; bool all_covered; @@ -7509,6 +7528,8 @@ TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param, (TIME_FOR_COMPARE_ROWID * M_LN2); DBUG_PRINT("info", ("Covering ROR-intersect full cost: %g", total_cost)); + /* TODO: Add TIME_FOR_COMPARE cost to total_cost */ + if (total_cost > read_time) DBUG_RETURN(NULL); @@ -7526,9 +7547,9 @@ TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param, trp->read_cost= total_cost; trp->records= records; trp->cpk_scan= NULL; - set_if_smaller(param->table->opt_range_condition_rows, records); + param->table->set_opt_range_condition_rows(records); - DBUG_PRINT("info", + DBUG_PRINT("exit", ("Returning covering ROR-intersect plan: cost %g, records %lu", trp->read_cost, (ulong) trp->records)); DBUG_RETURN(trp); @@ -7611,19 +7632,19 @@ static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree, for_range_access, &mrr_flags, &buf_size, &cost, &is_ror_scan); - if (!for_range_access && !is_ror_scan && - !optimizer_flag(param->thd,OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION)) + if (found_records == HA_POS_ERROR || + (!for_range_access && !is_ror_scan && + !optimizer_flag(param->thd,OPTIMIZER_SWITCH_INDEX_MERGE_SORT_UNION))) { /* The scan is not a ROR-scan, just skip it */ continue; } - - if (found_records != HA_POS_ERROR && tree->index_scans && + found_read_time= cost.total_cost(); + if (tree->index_scans && (index_scan= (INDEX_SCAN_INFO *)alloc_root(param->mem_root, sizeof(INDEX_SCAN_INFO)))) { Json_writer_array trace_range(thd, "ranges"); - const KEY &cur_key= param->table->key_info[keynr]; const KEY_PART_INFO *key_part= cur_key.key_part; @@ -7646,15 +7667,14 @@ static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree, add("using_mrr", !(mrr_flags & HA_MRR_USE_DEFAULT_IMPL)). add("index_only", read_index_only). add("rows", found_records). - add("cost", cost.total_cost()); + add("cost", found_read_time); } - if ((found_records != HA_POS_ERROR) && is_ror_scan) + if (is_ror_scan) { tree->n_ror_scans++; tree->ror_scans_map.set_bit(idx); } - if (found_records != HA_POS_ERROR && - read_time > (found_read_time= cost.total_cost())) + if (read_time > found_read_time) { read_time= found_read_time; best_records= found_records; @@ -11755,16 +11775,28 @@ ha_rows check_quick_select(PARAM *param, uint idx, bool index_only, param->table->opt_range_keys.set_bit(keynr); range->key_parts= param->max_key_parts; range->ranges= param->range_count; - param->table->opt_range_condition_rows= - MY_MIN(param->table->opt_range_condition_rows, rows); + param->table->set_opt_range_condition_rows(rows); + range->selectivity= (rows ? + (param->table->opt_range_condition_rows / + rows) : + 1.0); // ok as rows is 0 range->rows= rows; - range->fetch_cost= cost->fetch_cost(); - /* Same as total cost */ - range->cost= range->fetch_cost + cost->compare_cost(); + /* cost of finding a row without copy or checking the where */ + range->find_cost= cost->find_cost(); + /* cost of finding a row copying it to the row buffer */ + range->fetch_cost= range->find_cost + cost->data_copy_cost(); + /* Add comparing it to the where. Same as cost.total_cost() */ + range->cost= (range->fetch_cost + cost->compare_cost()); + /* Calculate the cost of just finding the key. Used by filtering */ if (param->table->file->is_clustering_key(keynr)) - range->index_only_cost= 0; + range->index_only_cost= range->find_cost; else + { range->index_only_cost= cost->index_only_cost(); + DBUG_ASSERT(!(*mrr_flags & HA_MRR_INDEX_ONLY) || + range->index_only_cost == + range->find_cost); + } range->first_key_part_has_only_one_value= check_if_first_key_part_has_only_one_value(tree); } diff --git a/sql/opt_split.cc b/sql/opt_split.cc index c01f8f3cccf..48eeda0d40a 100644 --- a/sql/opt_split.cc +++ b/sql/opt_split.cc @@ -668,12 +668,13 @@ static double spl_postjoin_oper_cost(THD *thd, double join_record_count, uint rec_len) { double cost; - cost= get_tmp_table_write_cost(thd, join_record_count,rec_len) * - join_record_count; // cost to fill tmp table - cost+= get_tmp_table_lookup_cost(thd, join_record_count,rec_len) * - join_record_count; // cost to perform post join operation used here - cost+= get_tmp_table_lookup_cost(thd, join_record_count, rec_len) + - (join_record_count == 0 ? 0 : + TMPTABLE_COSTS tmp_cost= get_tmp_table_costs(thd, join_record_count, + rec_len, 0); + // cost to fill tmp table + cost= tmp_cost.create + tmp_cost.write * join_record_count; + // cost to perform post join operation used here + cost+= tmp_cost.lookup * join_record_count; + cost+= (join_record_count == 0 ? 0 : join_record_count * log2 (join_record_count)) * SORT_INDEX_CMP_COST; // cost to perform sorting return cost; @@ -1038,12 +1039,11 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count, } /* Set the cost of the preferred materialization for this partial join */ - records= (ha_rows)spl_opt_info->unsplit_card; spl_plan= spl_opt_info->last_plan; if (spl_plan) { startup_cost= record_count * spl_plan->cost; - records= (ha_rows) (records * spl_plan->split_sel); + records= (ha_rows) (spl_opt_info->unsplit_card * spl_plan->split_sel); if (unlikely(thd->trace_started())) { @@ -1055,7 +1055,11 @@ SplM_plan_info * JOIN_TAB::choose_best_splitting(double record_count, } } else - startup_cost= spl_opt_info->unsplit_cost; + { + /* Restore original values */ + startup_cost= spl_opt_info->unsplit_cost; + records= (ha_rows) spl_opt_info->unsplit_card; + } return spl_plan; } diff --git a/sql/opt_subselect.cc b/sql/opt_subselect.cc index 9e0d78851e6..9f98404fd07 100644 --- a/sql/opt_subselect.cc +++ b/sql/opt_subselect.cc @@ -448,7 +448,8 @@ static bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred); static bool convert_subq_to_jtbm(JOIN *parent_join, Item_in_subselect *subq_pred, bool *remove); static TABLE_LIST *alloc_join_nest(THD *thd); -static uint get_tmp_table_rec_length(Ref_ptr_array p_list, uint elements); +static uint get_tmp_table_rec_length(Ref_ptr_array p_list, uint elements, + bool *blobs_used); bool find_eq_ref_candidate(TABLE *table, table_map sj_inner_tables); static SJ_MATERIALIZATION_INFO * at_sjmat_pos(const JOIN *join, table_map remaining_tables, const JOIN_TAB *tab, @@ -1442,9 +1443,9 @@ void get_delayed_table_estimates(TABLE *table, /* Calculate cost of scanning the temptable */ double data_size= COST_MULT(item->jtbm_record_count, hash_sj_engine->tmp_table->s->reclength); - /* Do like in handler::scan_time() */ + /* Do like in handler::ha_scan_and_copy_time() */ *scan_time= ((data_size/table->file->stats.block_size+2) * - table->file->avg_io_cost()); + table->file->avg_io_cost()) + *out_rows * RECORD_COPY_COST; } @@ -2528,27 +2529,28 @@ bool optimize_semijoin_nests(JOIN *join, table_map all_table_map) /* Calculate temporary table parameters and usage costs */ + bool blobs_used; uint rowlen= get_tmp_table_rec_length(subq_select->ref_pointer_array, - subq_select->item_list.elements); - double lookup_cost= get_tmp_table_lookup_cost(join->thd, - subjoin_out_rows, rowlen); - double write_cost= get_tmp_table_write_cost(join->thd, - subjoin_out_rows, rowlen); - + subq_select->item_list.elements, + &blobs_used); + TMPTABLE_COSTS cost= get_tmp_table_costs(join->thd, + subjoin_out_rows, rowlen, + blobs_used); /* Let materialization cost include the cost to write the data into the temporary table: */ - sjm->materialization_cost.add_io(subjoin_out_rows, write_cost); - + sjm->materialization_cost.add_io(subjoin_out_rows, cost.write); + sjm->materialization_cost.copy_cost+= cost.create; + /* Set the cost to do a full scan of the temptable (will need this to consider doing sjm-scan): */ sjm->scan_cost.reset(); - sjm->scan_cost.add_io(sjm->rows, lookup_cost); + sjm->scan_cost.add_io(sjm->rows, cost.lookup); - sjm->lookup_cost.convert_from_cost(lookup_cost); + sjm->lookup_cost.convert_from_cost(cost.lookup); sj_nest->sj_mat_info= sjm; DBUG_EXECUTE("opt", print_sjm(sjm);); } @@ -2576,11 +2578,13 @@ bool optimize_semijoin_nests(JOIN *join, table_map all_table_map) Length of the temptable record, in bytes */ -static uint get_tmp_table_rec_length(Ref_ptr_array p_items, uint elements) +static uint get_tmp_table_rec_length(Ref_ptr_array p_items, uint elements, + bool *blobs_used) { uint len= 0; Item *item; - //List_iterator<Item> it(items); + + *blobs_used= 0; for (uint i= 0; i < elements ; i++) { item = p_items[i]; @@ -2603,6 +2607,8 @@ static uint get_tmp_table_rec_length(Ref_ptr_array p_items, uint elements) len += 8; else len += item->max_length; + if (item->max_length > MAX_FIELD_VARCHARLENGTH) + *blobs_used= 1; break; case DECIMAL_RESULT: len += 10; @@ -2618,46 +2624,48 @@ static uint get_tmp_table_rec_length(Ref_ptr_array p_items, uint elements) /** - The cost of a lookup into a unique hash/btree index on a temporary table - with 'row_count' rows each of size 'row_size'. + The cost of a create, write and read into a unique hash/btree index on + a temporary table with 'row_count' rows each of size 'row_size'. @param thd current query context @param row_count number of rows in the temp table @param row_size average size in bytes of the rows - @return the cost of one lookup + @return The cost of using the temporary table + + TODO: + This is an optimistic estimate. We are not taking into account: + - That we first write into a memory and then overflow to disk. + - If binary trees would be used for heap tables. + - The addition cost of writing a row to memory/disk and possible + index reorganization. */ -double -get_tmp_table_lookup_cost(THD *thd, double row_count, uint row_size) +TMPTABLE_COSTS +get_tmp_table_costs(THD *thd, double row_count, uint row_size, bool blobs_used) { - if (row_count > thd->variables.max_heap_table_size / (double) row_size) - return (double) DISK_TEMPTABLE_LOOKUP_COST; - else - return (double) HEAP_TEMPTABLE_LOOKUP_COST; -} + TMPTABLE_COSTS cost; -/** - The cost of writing a row into a temporary table with 'row_count' unique - rows each of size 'row_size'. + /* From heap_prepare_hp_create_info(), assuming one hash key used */ + row_size+= sizeof(char*)*2; + row_size= MY_ALIGN(MY_MAX(row_size, sizeof(char*)) + 1, sizeof(char*)); - @param thd current query context - @param row_count number of rows in the temp table - @param row_size average size in bytes of the rows - - @return the cost of writing one row -*/ - -double -get_tmp_table_write_cost(THD *thd, double row_count, uint row_size) -{ - double lookup_cost= get_tmp_table_lookup_cost(thd, row_count, row_size); - /* - TODO: - This is an optimistic estimate. Add additional costs resulting from - actually writing the row to memory/disk and possible index reorganization. - */ - return lookup_cost; + if (row_count > thd->variables.max_heap_table_size / (double) row_size || + blobs_used) + { + /* Disk based table */ + cost.lookup= (DISK_TEMPTABLE_LOOKUP_COST * + thd->variables.optimizer_cache_hit_ratio); + cost.write= cost.lookup; + cost.create= DISK_TEMPTABLE_CREATE_COST; + } + else + { + cost.lookup= HEAP_TEMPTABLE_LOOKUP_COST; + cost.write= cost.lookup; + cost.create= HEAP_TEMPTABLE_CREATE_COST; + } + return cost; } @@ -2902,9 +2910,16 @@ void advance_sj_state(JOIN *join, table_map remaining_tables, uint idx, 2. using strategy Z is cheaper, but it only removes fanout from semijoin X. 3. We have no clue what to do about fanount of semi-join Y. + + For the first iteration read_time will always be bigger than + *current_read_time (as the 'strategy' is an addition to the + chosen plan) . If a strategy was picked + (dusp_producing_tables & handled_fanout is true), then + *current_read_time is updated and the cost for the next + strategy can be smaller than *current_read_time. */ if ((dups_producing_tables & handled_fanout) || - (read_time < *current_read_time && + (read_time + COST_EPS < *current_read_time && !(handled_fanout & pos->inner_tables_handled_with_other_sjs))) { DBUG_ASSERT(pos->sj_strategy != sj_strategy); @@ -3158,8 +3173,6 @@ bool Sj_materialization_picker::check_qep(JOIN *join, disable_jbuf, prefix_rec_count, &curpos, &dummy); prefix_rec_count= COST_MULT(prefix_rec_count, curpos.records_read); prefix_cost= COST_ADD(prefix_cost, curpos.read_time); - prefix_cost= COST_ADD(prefix_cost, - prefix_rec_count / TIME_FOR_COMPARE); //TODO: take into account join condition selectivity here } @@ -3184,8 +3197,9 @@ bool Sj_materialization_picker::check_qep(JOIN *join, *handled_fanout= mat_nest->sj_inner_tables; if (unlikely(trace.trace_started())) { - trace.add("records", *record_count); - trace.add("read_time", *read_time); + trace. + add("records", *record_count). + add("cost", *read_time); } return TRUE; } @@ -3286,7 +3300,7 @@ bool LooseScan_picker::check_qep(JOIN *join, { trace. add("records", *record_count). - add("read_time", *read_time); + add("cost", *read_time); } return TRUE; } @@ -3403,8 +3417,9 @@ bool Firstmatch_picker::check_qep(JOIN *join, *strategy= SJ_OPT_FIRST_MATCH; if (unlikely(trace.trace_started())) { - trace.add("records", *record_count); - trace.add("read_time", *read_time); + trace. + add("records", *record_count). + add("cost", *read_time); } return TRUE; } @@ -3416,6 +3431,56 @@ bool Firstmatch_picker::check_qep(JOIN *join, } +/* + Duplicate_weedout strategy is described at + https://mariadb.com/kb/en/duplicateweedout-strategy/ + + The idea is that if one has a subquery of type: + + select * + from Country + where + Country.code IN (select City.Country + from City + where + ...) + + Before semi join optimization it was executed this way: + - Scan rows in Country + - For each accepted row, execute the sub query with + 'Country.code = City.Country' added to the WHERE clause and with + LIMIT 1 + + With semi join optimization it can be converted to the following semi join. + + select * from Country semi-join City + where Country.code = City.Country and ... + + This is executed as: + + - Scan rows in Country + - Scan rows in City with 'Country.code = City.Country' added to the + subquery WHERE clause. Stop scanning after the first match. + + or + + - Create temporary table to store City.Country (with a unique key) + - Scan rows in City (according to plan for City) and put them into the + temporary table + - Scan the temporary table + - Do index lookup in Country table with City.Country + +With Duplicate_weedout we would try to instead do: + + - Create temporary table to hold unique rowid's for the Country + - Scan rows in City (according to plan for City) + - Scan rows in Country (according to plan for Country) + - Write Country.id rowid to temporary table. If there was no + conflicting row in the temporary table, accept the row combination. + - Delete temporary table +*/ + + void Duplicate_weedout_picker::set_from_prev(POSITION *prev) { if (prev->dups_weedout_picker.is_used) @@ -3484,8 +3549,6 @@ bool Duplicate_weedout_picker::check_qep(JOIN *join, double sj_inner_fanout= 1.0; double sj_outer_fanout= 1.0; uint temptable_rec_size; - Json_writer_object trace(join->thd); - trace.add("strategy", "DuplicateWeedout"); if (first_tab == join->const_tables) { @@ -3501,14 +3564,11 @@ bool Duplicate_weedout_picker::check_qep(JOIN *join, } table_map dups_removed_fanout= 0; - double current_fanout= prefix_rec_count; for (uint j= first_dupsweedout_table; j <= idx; j++) { POSITION *p= join->positions + j; - current_fanout= COST_MULT(current_fanout, p->records_read); - dups_cost= COST_ADD(dups_cost, - COST_ADD(p->read_time, - current_fanout / TIME_FOR_COMPARE)); + dups_cost= COST_ADD(dups_cost, p->read_time); + if (p->table->emb_sj_nest) { sj_inner_fanout= COST_MULT(sj_inner_fanout, p->records_read); @@ -3527,29 +3587,33 @@ bool Duplicate_weedout_picker::check_qep(JOIN *join, - sj_outer_fanout table writes - sj_inner_fanout*sj_outer_fanout lookups. */ - double one_lookup_cost= get_tmp_table_lookup_cost(join->thd, - sj_outer_fanout, - temptable_rec_size); - double one_write_cost= get_tmp_table_write_cost(join->thd, - sj_outer_fanout, - temptable_rec_size); - - double write_cost= COST_MULT(join->positions[first_tab].prefix_record_count, - sj_outer_fanout * one_write_cost); + TMPTABLE_COSTS one_cost= get_tmp_table_costs(join->thd, + sj_outer_fanout, + temptable_rec_size, + 0); + double write_cost= + COST_ADD(one_cost.create, + COST_MULT(join->positions[first_tab].prefix_record_count, + sj_outer_fanout * one_cost.write)); double full_lookup_cost= - COST_MULT(join->positions[first_tab].prefix_record_count, - COST_MULT(sj_outer_fanout, - sj_inner_fanout * one_lookup_cost)); - dups_cost= COST_ADD(dups_cost, COST_ADD(write_cost, full_lookup_cost)); + COST_MULT(join->positions[first_tab].prefix_record_count, + COST_MULT(sj_outer_fanout, + sj_inner_fanout * one_cost.lookup)); + *read_time= COST_ADD(dups_cost, COST_ADD(write_cost, full_lookup_cost)); - *read_time= dups_cost; *record_count= prefix_rec_count * sj_outer_fanout; *handled_fanout= dups_removed_fanout; *strategy= SJ_OPT_DUPS_WEEDOUT; - if (unlikely(trace.trace_started())) + if (unlikely(join->thd->trace_started())) { - trace.add("records", *record_count); - trace.add("read_time", *read_time); + Json_writer_object trace(join->thd); + trace. + add("strategy", "DuplicateWeedout"). + add("records", *record_count). + add("dups_cost", dups_cost). + add("write_cost", write_cost). + add("full_lookup_cost", full_lookup_cost). + add("total_cost", *read_time); } return TRUE; } @@ -3686,6 +3750,8 @@ at_sjmat_pos(const JOIN *join, table_map remaining_tables, const JOIN_TAB *tab, static void recalculate_prefix_record_count(JOIN *join, uint start, uint end) { + DBUG_ASSERT(start >= join->const_tables); + for (uint j= start; j < end ;j++) { double prefix_count; @@ -3857,7 +3923,7 @@ void fix_semijoin_strategies_for_picked_join_order(JOIN *join) join->best_positions[first].n_sj_tables= tablenr - first + 1; POSITION dummy; // For loose scan paths double record_count= (first== join->const_tables)? 1.0: - join->best_positions[tablenr - 1].prefix_record_count; + join->best_positions[first - 1].prefix_record_count; table_map rem_tables= remaining_tables; uint idx; @@ -3898,7 +3964,7 @@ void fix_semijoin_strategies_for_picked_join_order(JOIN *join) POSITION *first_pos= join->best_positions + first; POSITION loose_scan_pos; // For loose scan paths double record_count= (first== join->const_tables)? 1.0: - join->best_positions[tablenr - 1].prefix_record_count; + join->best_positions[first - 1].prefix_record_count; table_map rem_tables= remaining_tables; uint idx; @@ -6422,18 +6488,14 @@ bool JOIN::choose_subquery_plan(table_map join_tables) IN/ALL/ANY optimizations are not applicable for so called fake select (this select exists only to filter results of union if it is needed). */ - if (select_lex == select_lex->master_unit()->fake_select_lex) - return 0; - - if (is_in_subquery()) - { - in_subs= unit->item->get_IN_subquery(); - if (in_subs->create_in_to_exists_cond(this)) - return true; - } - else + if (select_lex == select_lex->master_unit()->fake_select_lex || + likely(!is_in_subquery())) return false; + in_subs= unit->item->get_IN_subquery(); + if (in_subs->create_in_to_exists_cond(this)) + return true; + /* A strategy must be chosen earlier. */ DBUG_ASSERT(in_subs->has_strategy()); DBUG_ASSERT(in_to_exists_where || in_to_exists_having); @@ -6464,6 +6526,7 @@ bool JOIN::choose_subquery_plan(table_map join_tables) /* The cost of the IN->EXISTS strategy. */ double in_exists_strategy_cost; double dummy; + const char *strategy; /* A. Estimate the number of rows of the outer table that will be filtered @@ -6536,39 +6599,56 @@ bool JOIN::choose_subquery_plan(table_map join_tables) C. Compute execution costs. */ /* C.1 Compute the cost of the materialization strategy. */ - //uint rowlen= get_tmp_table_rec_length(unit->first_select()->item_list); - uint rowlen= get_tmp_table_rec_length(ref_ptrs, - select_lex->item_list.elements); - /* The cost of writing one row into the temporary table. */ - double write_cost= get_tmp_table_write_cost(thd, inner_record_count_1, - rowlen); - /* The cost of a lookup into the unique index of the materialized table. */ - double lookup_cost= get_tmp_table_lookup_cost(thd, inner_record_count_1, - rowlen); + bool blobs_used; + uint rowlen= get_tmp_table_rec_length(ref_ptrs, + select_lex->item_list.elements, + &blobs_used); + /* The cost of using the temp table */ + TMPTABLE_COSTS cost= get_tmp_table_costs(thd, inner_record_count_1, + rowlen, blobs_used); /* The cost of executing the subquery and storing its result in an indexed temporary table. */ - double materialization_cost= COST_ADD(inner_read_time_1, - COST_MULT(write_cost, - inner_record_count_1)); + double materialization_cost= + COST_ADD(cost.create, + COST_ADD(inner_read_time_1, + COST_MULT(cost.write, inner_record_count_1))); - materialize_strategy_cost= COST_ADD(materialization_cost, - COST_MULT(outer_lookup_keys, - lookup_cost)); + materialize_strategy_cost= + COST_ADD(materialization_cost, + COST_MULT(outer_lookup_keys, cost.lookup)); /* C.2 Compute the cost of the IN=>EXISTS strategy. */ - in_exists_strategy_cost= COST_MULT(outer_lookup_keys, inner_read_time_2); + in_exists_strategy_cost= + COST_MULT(outer_lookup_keys, inner_read_time_2); /* C.3 Compare the costs and choose the cheaper strategy. */ if (materialize_strategy_cost >= in_exists_strategy_cost) + { in_subs->set_strategy(SUBS_IN_TO_EXISTS); + strategy= "in_to_exists"; + } else + { in_subs->set_strategy(SUBS_MATERIALIZATION); + strategy= "materialization"; + } + if (unlikely(thd->trace_started())) + { + Json_writer_object trace_subquery(thd, "subquery_plan"); + trace_subquery. + add("records", inner_record_count_1). + add("materialization_cost", materialize_strategy_cost). + add("in_exist_cost", in_exists_strategy_cost). + add("choosen", strategy); + } DBUG_PRINT("info", - ("mat_strategy_cost: %.2f, mat_cost: %.2f, write_cost: %.2f, lookup_cost: %.2f", - materialize_strategy_cost, materialization_cost, write_cost, lookup_cost)); + ("mat_strategy_cost: %.2f mat_cost: %.2f write_cost: %.2f " + "lookup_cost: %.2f", + materialize_strategy_cost, materialization_cost, cost.write, + cost.lookup)); DBUG_PRINT("info", ("inx_strategy_cost: %.2f, inner_read_time_2: %.2f", in_exists_strategy_cost, inner_read_time_2)); @@ -6594,6 +6674,12 @@ bool JOIN::choose_subquery_plan(table_map join_tables) implementation, fall back to IN-TO-EXISTS. */ in_subs->set_strategy(SUBS_IN_TO_EXISTS); + + if (unlikely(thd->trace_started())) + { + Json_writer_object trace_subquery(thd, "subquery_plan_revert"); + trace_subquery.add("choosen", "in_to_exists"); + } } if (in_subs->test_strategy(SUBS_MATERIALIZATION)) diff --git a/sql/opt_subselect.h b/sql/opt_subselect.h index abd37f1e98e..45ea3eea6c2 100644 --- a/sql/opt_subselect.h +++ b/sql/opt_subselect.h @@ -233,8 +233,8 @@ public: double records= rows2double(s->table->file->stats.records); /* The cost is entire index scan cost (divided by 2) */ - double read_time= s->table->file->keyread_time(key, 1, - (ha_rows) records); + double read_time= s->table->file->ha_keyread_and_copy_time(key, 1, + (ha_rows) records); /* Now find out how many different keys we will get (for now we diff --git a/sql/opt_trace.cc b/sql/opt_trace.cc index afa4ae5951d..3d89d2c6298 100644 --- a/sql/opt_trace.cc +++ b/sql/opt_trace.cc @@ -618,7 +618,8 @@ void add_table_scan_values_to_trace(THD *thd, JOIN_TAB *tab) Json_writer_object table_rec(thd, "table_scan"); table_rec. add("rows", tab->found_records). - add("cost", tab->read_time); + add("read_cost", tab->read_time). + add("read_and_compare_cost", tab->cached_scan_and_compare_time); } @@ -678,7 +679,7 @@ void print_final_join_order(JOIN *join) /* Write information about the resulting join */ Json_writer_object obj(join->thd, "best_access_method"); - obj.add("cost", join->best_read); + obj.add("rows", join->join_record_count).add("cost", join->best_read); } diff --git a/sql/rowid_filter.cc b/sql/rowid_filter.cc index 3ed9a989345..b992c90f5d7 100644 --- a/sql/rowid_filter.cc +++ b/sql/rowid_filter.cc @@ -22,14 +22,17 @@ #include "sql_select.h" #include "opt_trace.h" +/* + INDEX_NEXT_FIND_COST below is the cost of finding the next possible key + and calling handler_rowid_filter_check() to check it against the filter +*/ double Range_rowid_filter_cost_info:: lookup_cost(Rowid_filter_container_type cont_type) { switch (cont_type) { case SORTED_ARRAY_CONTAINER: - /* The addition is here to take care of arrays with 1 element */ - return log(est_elements)*0.01+0.001; + return log(est_elements)*0.01+INDEX_NEXT_FIND_COST; default: DBUG_ASSERT(0); return 0; @@ -45,9 +48,10 @@ lookup_cost(Rowid_filter_container_type cont_type) inline double Range_rowid_filter_cost_info:: -avg_access_and_eval_gain_per_row(Rowid_filter_container_type cont_type) +avg_access_and_eval_gain_per_row(Rowid_filter_container_type cont_type, + double cost_of_row_fetch) { - return (1+1.0/TIME_FOR_COMPARE) * (1 - selectivity) - + return (cost_of_row_fetch+1.0/TIME_FOR_COMPARE) * (1 - selectivity) - lookup_cost(cont_type); } @@ -122,7 +126,8 @@ void Range_rowid_filter_cost_info::init(Rowid_filter_container_type cont_type, est_elements= (ulonglong) table->opt_range[key_no].rows; cost_of_building_range_filter= build_cost(container_type); selectivity= est_elements/((double) table->stat_records()); - gain= avg_access_and_eval_gain_per_row(container_type); + gain= avg_access_and_eval_gain_per_row(container_type, + tab->file->optimizer_cache_cost); if (gain > 0) cross_x= cost_of_building_range_filter/gain; else @@ -139,10 +144,10 @@ void Range_rowid_filter_cost_info::init(Rowid_filter_container_type cont_type, double Range_rowid_filter_cost_info::build_cost(Rowid_filter_container_type cont_type) { - double cost= 0; + double cost; DBUG_ASSERT(table->opt_range_keys.is_set(key_no)); - cost+= table->opt_range[key_no].index_only_cost; + cost= table->opt_range[key_no].index_only_fetch_cost(); switch (cont_type) { @@ -461,14 +466,6 @@ void Range_rowid_filter_cost_info::trace_info(THD *thd) The function looks through the array of cost info for range filters and chooses the element for the range filter that promise the greatest gain with the the ref or range access of the table by access_key_no. - As the array is sorted by cross_x in ascending order the function stops - the look through as soon as it reaches the first element with - cross_x_adj > records because the range filter for this element and the - range filters for all remaining elements do not promise positive gains. - - @note - It is easy to see that if cross_x[i] > cross_x[j] then - cross_x_adj[i] > cross_x_adj[j] @retval Pointer to the cost info for the range filter that promises the greatest gain, NULL if there is no such range filter @@ -477,20 +474,13 @@ void Range_rowid_filter_cost_info::trace_info(THD *thd) Range_rowid_filter_cost_info * TABLE::best_range_rowid_filter_for_partial_join(uint access_key_no, double records, - double access_cost_factor) + double fetch_cost, + double index_only_cost, + double prev_records) { if (range_rowid_filter_cost_info_elems == 0 || covering_keys.is_set(access_key_no)) return 0; - - // Disallow use of range filter if the key contains partially-covered - // columns. - for (uint i= 0; i < key_info[access_key_no].usable_key_parts; i++) - { - if (key_info[access_key_no].key_part[i].field->type() == MYSQL_TYPE_BLOB) - return 0; - } - /* Currently we do not support usage of range filters if the table is accessed by the clustered primary key. It does not make sense @@ -501,36 +491,44 @@ TABLE::best_range_rowid_filter_for_partial_join(uint access_key_no, if (file->is_clustering_key(access_key_no)) return 0; + // Disallow use of range filter if the key contains partially-covered + // columns. + for (uint i= 0; i < key_info[access_key_no].usable_key_parts; i++) + { + if (key_info[access_key_no].key_part[i].field->type() == MYSQL_TYPE_BLOB) + return 0; + } + Range_rowid_filter_cost_info *best_filter= 0; - double best_filter_gain= 0; + double best_filter_gain= DBL_MAX; key_map no_filter_usage= key_info[access_key_no].overlapped; no_filter_usage.merge(key_info[access_key_no].constraint_correlated); + no_filter_usage.set_bit(access_key_no); for (uint i= 0; i < range_rowid_filter_cost_info_elems ; i++) { - double curr_gain = 0; + double new_cost, new_total_cost, new_records; + double cost_of_accepted_rows, cost_of_rejected_rows; Range_rowid_filter_cost_info *filter= range_rowid_filter_cost_info_ptr[i]; /* Do not use a range filter that uses an in index correlated with the index by which the table is accessed */ - if ((filter->key_no == access_key_no) || - no_filter_usage.is_set(filter->key_no)) + if (no_filter_usage.is_set(filter->key_no)) continue; - filter->set_adjusted_gain_param(access_cost_factor); - - if (records < filter->cross_x_adj) - { - /* Does not make sense to look through the remaining filters */ - break; - } + new_records= records * filter->selectivity; + cost_of_accepted_rows= fetch_cost * filter->selectivity; + cost_of_rejected_rows= index_only_cost * (1 - filter->selectivity); + new_cost= (cost_of_accepted_rows + cost_of_rejected_rows + + records * filter->lookup_cost()); + new_total_cost= ((new_cost + new_records/TIME_FOR_COMPARE) * prev_records + + filter->get_setup_cost()); - curr_gain= filter->get_adjusted_gain(records); - if (best_filter_gain < curr_gain) + if (best_filter_gain > new_total_cost) { - best_filter_gain= curr_gain; + best_filter_gain= new_total_cost; best_filter= filter; } } diff --git a/sql/rowid_filter.h b/sql/rowid_filter.h index 660f8ce3a09..ff252a4a196 100644 --- a/sql/rowid_filter.h +++ b/sql/rowid_filter.h @@ -143,12 +143,19 @@ class SQL_SELECT; class Rowid_filter_container; class Range_rowid_filter_cost_info; -/* Cost to write rowid into array */ -#define ARRAY_WRITE_COST 0.005 -/* Factor used to calculate cost of sorting rowids in array */ -#define ARRAY_SORT_C 0.01 -/* Cost to evaluate condition */ -#define COST_COND_EVAL 0.2 +/* + Cost to write rowid into array. Assume inserting 1000 row id's into the + array has same cost as a 'disk io' or key fetch +*/ +#define ARRAY_WRITE_COST 0.001 +/* + Factor used to calculate cost of sorting rowids in array + This is multiplied by 'elements * log(elements)', so this factor + has a very high cost weight! + A value of 0.001 will have 200 rows have a cost of 1.05 and + 1000 rows a cost of 6.90. +*/ +#define ARRAY_SORT_C 0.001 typedef enum { @@ -423,7 +430,8 @@ public: inline double lookup_cost() { return lookup_cost(container_type); } inline double - avg_access_and_eval_gain_per_row(Rowid_filter_container_type cont_type); + avg_access_and_eval_gain_per_row(Rowid_filter_container_type cont_type, + double cost_of_row_fetch); inline double avg_adjusted_gain_per_row(double access_cost_factor); @@ -469,7 +477,13 @@ public: Range_rowid_filter_cost_info * TABLE::best_range_rowid_filter_for_partial_join(uint access_key_no, double records, - double access_cost_factor); + double fetch_cost, + double index_only_cost, + double prev_records); + 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 record_count); }; #endif /* ROWID_FILTER_INCLUDED */ diff --git a/sql/set_var.cc b/sql/set_var.cc index 4b3e23b06c0..103b7ca02ec 100644 --- a/sql/set_var.cc +++ b/sql/set_var.cc @@ -1548,4 +1548,3 @@ ulonglong get_system_variable_hash_version(void) { return system_variable_hash_version; } - diff --git a/sql/set_var.h b/sql/set_var.h index 2d538624825..f1f186b9bef 100644 --- a/sql/set_var.h +++ b/sql/set_var.h @@ -484,5 +484,4 @@ void free_engine_list(plugin_ref *list); plugin_ref *copy_engine_list(plugin_ref *list); plugin_ref *temp_copy_engine_list(THD *thd, plugin_ref *list); char *pretty_print_engine_list(THD *thd, plugin_ref *list); - #endif diff --git a/sql/sql_base.cc b/sql/sql_base.cc index d983fe9a332..f510e4aeec8 100644 --- a/sql/sql_base.cc +++ b/sql/sql_base.cc @@ -4449,6 +4449,7 @@ restart: tbl->reginfo.lock_type= tables->lock_type; tbl->reginfo.skip_locked= tables->skip_locked; } + #ifdef WITH_WSREP /* At this point we have SE associated with table so we can check wsrep_mode diff --git a/sql/sql_class.h b/sql/sql_class.h index cd11c4d465f..491471d33f4 100644 --- a/sql/sql_class.h +++ b/sql/sql_class.h @@ -653,7 +653,7 @@ typedef struct system_variables char* dynamic_variables_ptr; uint dynamic_variables_head; /* largest valid variable offset */ uint dynamic_variables_size; /* how many bytes are in use */ - + ulonglong max_heap_table_size; ulonglong tmp_memory_table_size; ulonglong tmp_disk_table_size; @@ -699,7 +699,6 @@ typedef struct system_variables ulong saved_lock_wait_timeout; ulonglong wsrep_gtid_seq_no; #endif /* WITH_WSREP */ - uint eq_range_index_dive_limit; ulong column_compression_zlib_strategy; ulong lock_wait_timeout; ulong join_cache_level; @@ -752,7 +751,6 @@ typedef struct system_variables ulong tx_isolation; ulong updatable_views_with_limit; ulong alter_algorithm; - int max_user_connections; ulong server_id; /** In slave thread we need to know in behalf of which @@ -763,10 +761,13 @@ typedef struct system_variables When replicating an event group with GTID, keep these values around so slave binlog can receive the same GTID as the original. */ - uint32 gtid_domain_id; uint64 gtid_seq_no; + uint32 gtid_domain_id; uint group_concat_max_len; + uint eq_range_index_dive_limit; + uint optimizer_cache_hit_ratio; + int max_user_connections; /** Default transaction access mode. READ ONLY (true) or READ WRITE (false). diff --git a/sql/sql_const.h b/sql/sql_const.h index bcc556e61f9..f73dce2ce5c 100644 --- a/sql/sql_const.h +++ b/sql/sql_const.h @@ -200,16 +200,82 @@ #define MIN_ROWS_TO_USE_BULK_INSERT 100 /** - The following is used to decide if MySQL should use table scanning + The following is used to decide if MariaDB should use table scanning instead of reading with keys. The number says how many evaluation of the WHERE clause is comparable to reading one extra row from a table. */ #define TIME_FOR_COMPARE 5.0 // 5 WHERE compares == one read #define TIME_FOR_COMPARE_IDX 20.0 -#define IDX_BLOCK_COPY_COST ((double) 1 / TIME_FOR_COMPARE) -#define IDX_LOOKUP_COST ((double) 1 / 8) -#define MULTI_RANGE_READ_SETUP_COST (IDX_BLOCK_COPY_COST/10) +/* + The table/index cache hit ratio in %. 0 means that a searched for key or row + will never be in the cache while 100 means it always in the cache. + + According to folklore, one need at least 80 % hit rate in the cache for + MariaDB to run very well. We set CACHE_HIT_RATIO to a bit smaller + as there is still a cost involved in finding the row in the B tree, hash + or other seek structure. + + Increasing CACHE_HIT_RATIO will make MariaDB prefer key lookups over + table scans as the impact of RECORD_COPY_COST and INDEX_COPY cost will + have a larger impact when more rows are exmined.. + + Note that avg_io_cost() is multipled with this constant! +*/ +#define CACHE_HIT_RATIO 50 + +/* + Cost of finding and copying keys of a total length of 'blocksize' + used in handler::keyread_time() + */ +#define INDEX_BLOCK_COPY_COST ((double) 1 / 5.0) +/* Cost for finding the first key in a key scan */ +#define INDEX_LOOKUP_COST ((double) 1.0) +/* Cost of finding a key from a row_ID (not used for clustered keys) */ +#define ROW_LOOKUP_COST ((double) 1.0) +/* + Cost of finding the next row during table scan and copying it to + 'table->record'. + If this is too small, then table scans will be prefered over 'ref' + as with table scans there are no key read (INDEX_LOOKUP_COST), fewer + disk reads but more record copying and row comparisions. If it's + too big then MariaDB will used key lookup even when table scan is + better. +*/ +#define RECORD_COPY_COST ((double) 1.0 / 20.0) +/* + Cost of finding the next key during index scan and copying it to + 'table->record' + + If this is too small, then index scans will be prefered over 'ref' + as with table scans there are no key read (INDEX_LOOKUP_COST) and + fewer disk reads. +*/ +#define INDEX_COPY_COST ((double) 1.0 / 40.0) +/* + Cost of finding the next index entry and checking it against filter + This cost is very low as it's done inside the storage engine. + Should be smaller than INDEX_COPY_COST. + */ +#define INDEX_NEXT_FIND_COST ((double) 1.0 / 80.0) + +/* Extra cost for doing a range scan. Used to prefer 'ref' over range */ +#define MULTI_RANGE_READ_SETUP_COST (double) (1.0 / 50.0) + +/* + These costs are mainly to handle small tables, like the one we have in the + mtr test suite +*/ +/* Extra cost for full table scan. Used to prefer range over table scans */ +#define TABLE_SCAN_SETUP_COST 1.0 +/* Extra cost for full index scan. Used to prefer range over index scans */ +#define INDEX_SCAN_SETUP_COST 1.0 + +/* + The lower bound of accepted rows when using filter. + This is used to ensure that filters are not too agressive. +*/ +#define MIN_ROWS_AFTER_FILTERING 1.0 /** Number of comparisons of table rowids equivalent to reading one row from a @@ -217,8 +283,14 @@ */ #define TIME_FOR_COMPARE_ROWID (TIME_FOR_COMPARE*100) -/* cost1 is better that cost2 only if cost1 + COST_EPS < cost2 */ -#define COST_EPS 0.001 +/* + cost1 is better that cost2 only if cost1 + COST_EPS < cost2 + The main purpose of this is to ensure we use the first index or plan + when there are identical plans. Without COST_EPS some plans in the + test suite would vary depending on floating point calculations done + in different paths. + */ +#define COST_EPS 0.0001 /* For sequential disk seeks the cost formula is: @@ -244,11 +316,13 @@ /* Subquery materialization-related constants */ +/* This should match ha_heap::read_time() */ #define HEAP_TEMPTABLE_LOOKUP_COST 0.05 +#define HEAP_TEMPTABLE_CREATE_COST 1.0 #define DISK_TEMPTABLE_LOOKUP_COST 1.0 +#define DISK_TEMPTABLE_CREATE_COST 4.0 /* Creating and deleting 2 temp tables */ #define SORT_INDEX_CMP_COST 0.02 - #define COST_MAX (DBL_MAX * (1.0 - DBL_EPSILON)) #define COST_ADD(c,d) (COST_MAX - (d) > (c) ? (c) + (d) : COST_MAX) 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, ¤t_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)) { diff --git a/sql/sql_select.h b/sql/sql_select.h index d4e06f42249..3d75aac8ff9 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -309,11 +309,6 @@ typedef struct st_join_table { Table_access_tracker *tracker; Table_access_tracker *jbuf_tracker; - /* - Bitmap of TAB_INFO_* bits that encodes special line for EXPLAIN 'Extra' - column, or 0 if there is no info. - */ - uint packed_info; // READ_RECORD::Setup_func materialize_table; READ_RECORD::Setup_func read_first_record; @@ -357,8 +352,17 @@ typedef struct st_join_table { double partial_join_cardinality; + /* set by estimate_scan_time() */ + double cached_scan_time; + double cached_scan_and_compare_time; + table_map dependent,key_dependent; /* + Bitmap of TAB_INFO_* bits that encodes special line for EXPLAIN 'Extra' + column, or 0 if there is no info. + */ + uint packed_info; + /* 1 - use quick select 2 - use "Range checked for each record" */ @@ -370,6 +374,7 @@ typedef struct st_join_table { uint index; uint status; ///< Save status for cache uint used_fields; + uint cached_covering_key; /* Set by estimate_scan_time() */ ulong used_fieldlength; ulong max_used_fieldlength; uint used_blobs; @@ -637,7 +642,7 @@ typedef struct st_join_table { { return (is_hash_join_key_no(key) ? hj_key : table->key_info+key); } - double scan_time(); + void estimate_scan_time(); ha_rows get_examined_rows(); bool preread_init(); @@ -937,7 +942,7 @@ public: /* Cost accessing the table in course of the entire complete join execution, i.e. cost of one access method use (e.g. 'range' or 'ref' scan ) times - number the access method will be invoked. + number the access method will be invoked and checking the WHERE clause. */ double read_time; @@ -2393,12 +2398,20 @@ bool instantiate_tmp_table(TABLE *table, KEY *keyinfo, bool open_tmp_table(TABLE *table); double prev_record_reads(const POSITION *positions, uint idx, table_map found_ref); void fix_list_after_tbl_changes(SELECT_LEX *new_parent, List<TABLE_LIST> *tlist); -double get_tmp_table_lookup_cost(THD *thd, double row_count, uint row_size); -double get_tmp_table_write_cost(THD *thd, double row_count, uint row_size); void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array); bool sort_and_filter_keyuse(THD *thd, DYNAMIC_ARRAY *keyuse, bool skip_unprefixed_keyparts); +struct TMPTABLE_COSTS +{ + double create; + double lookup; + double write; +}; + +TMPTABLE_COSTS get_tmp_table_costs(THD *thd, double row_count, uint row_size, + bool blobs_used); + struct st_cond_statistic { Item *cond; diff --git a/sql/sys_vars.cc b/sql/sys_vars.cc index e18ca6392d8..1b7cba81223 100644 --- a/sql/sys_vars.cc +++ b/sql/sys_vars.cc @@ -6764,20 +6764,6 @@ static Sys_var_mybool Sys_session_track_user_variables( #endif //EMBEDDED_LIBRARY -static Sys_var_uint Sys_in_subquery_conversion_threshold( - "in_predicate_conversion_threshold", - "The minimum number of scalar elements in the value list of " - "IN predicate that triggers its conversion to IN subquery. Set to " - "0 to disable the conversion.", - SESSION_VAR(in_subquery_conversion_threshold), CMD_LINE(REQUIRED_ARG), - VALID_RANGE(0, UINT_MAX), DEFAULT(IN_SUBQUERY_CONVERSION_THRESHOLD), BLOCK_SIZE(1)); - -static Sys_var_ulong Sys_optimizer_max_sel_arg_weight( - "optimizer_max_sel_arg_weight", - "The maximum weight of the SEL_ARG graph. Set to 0 for no limit", - SESSION_VAR(optimizer_max_sel_arg_weight), CMD_LINE(REQUIRED_ARG), - VALID_RANGE(0, ULONG_MAX), DEFAULT(SEL_ARG::MAX_WEIGHT), BLOCK_SIZE(1)); - static Sys_var_enum Sys_secure_timestamp( "secure_timestamp", "Restricts direct setting of a session " "timestamp. Possible levels are: YES - timestamp cannot deviate from " @@ -6794,3 +6780,34 @@ static Sys_var_ulonglong Sys_max_rowid_filter_size( SESSION_VAR(max_rowid_filter_size), CMD_LINE(REQUIRED_ARG), VALID_RANGE(1024, (ulonglong)~(intptr)0), DEFAULT(128*1024), BLOCK_SIZE(1)); + + +/* Optimizer variables */ + +static Sys_var_uint Sys_in_subquery_conversion_threshold( + "in_predicate_conversion_threshold", + "The minimum number of scalar elements in the value list of " + "IN predicate that triggers its conversion to IN subquery. Set to " + "0 to disable the conversion.", + SESSION_VAR(in_subquery_conversion_threshold), CMD_LINE(REQUIRED_ARG), + VALID_RANGE(0, UINT_MAX), DEFAULT(IN_SUBQUERY_CONVERSION_THRESHOLD), BLOCK_SIZE(1)); + +static Sys_var_ulong Sys_optimizer_max_sel_arg_weight( + "optimizer_max_sel_arg_weight", + "The maximum weight of the SEL_ARG graph. Set to 0 for no limit", + SESSION_VAR(optimizer_max_sel_arg_weight), CMD_LINE(REQUIRED_ARG), + VALID_RANGE(0, ULONG_MAX), DEFAULT(SEL_ARG::MAX_WEIGHT), BLOCK_SIZE(1)); + +/* + We don't allow 100 for optimizer_cache_cost as there is always a small + cost of finding the key, on cached pages, that we have to take into account. +*/ + +static Sys_var_uint Sys_optimizer_cache_cost( + "optimizer_cache_hit_ratio", + "Expected hit rate of the row and index cache in storage engines. " + "The value should be an integer between 0 and 99, where 0 means cache is " + "empty and 99 means that value is almost always in the cache", + SESSION_VAR(optimizer_cache_hit_ratio), CMD_LINE(REQUIRED_ARG), + VALID_RANGE(0, 99), DEFAULT(CACHE_HIT_RATIO), 1, NO_MUTEX_GUARD, + NOT_IN_BINLOG); diff --git a/sql/table.cc b/sql/table.cc index b1a7b6bfe2b..b0e8b11a543 100644 --- a/sql/table.cc +++ b/sql/table.cc @@ -5554,6 +5554,12 @@ void TABLE::init(THD *thd, TABLE_LIST *tl) opt_range_condition_rows=0; no_cache= false; initialize_opt_range_structures(); + /* + Update optimizer_cache_cost to ensure that a SET STATEMENT of + the variable it will work. + */ + file->set_optimizer_cache_cost((100 - thd->variables. + optimizer_cache_hit_ratio)/100.0); #ifdef HAVE_REPLICATION /* used in RBR Triggers */ master_had_triggers= 0; diff --git a/sql/table.h b/sql/table.h index 0caea757eb6..284c4b3073f 100644 --- a/sql/table.h +++ b/sql/table.h @@ -1356,16 +1356,38 @@ public: uint key_parts; uint ranges; ha_rows rows; - /* Cost of fetching and comparing the row aginst the WHERE clause */ + /* + The full cost of a using 'range'. Includes fetching the rows + trough keys, copying them and comparing the rows aginst the + WHERE clause. + */ double cost; - /* Cost of comparing row with WHERE clause. Included in 'cost' */ + /* + Cost of finding finding the key and fetching the row with row id. + In case of clustered keys or covered keys the fetch of the row is + not counted for. + */ + double find_cost; + /* find_cost + cost of copying the rows to record */ double fetch_cost; /* - If there is a range access by i-th index then the cost of - index only access for it is stored in index_only_costs[i] + Cost of fetching the keys, not including copying the keys to + record or comparing them with the WHERE clause. Used only when + working with filters. */ double index_only_cost; + /* Selectivity, in case of filters */ + double selectivity; bool first_key_part_has_only_one_value; + + /* + Cost of fetching a keys with index only read and returning them to the + sql level. + */ + double index_only_fetch_cost() + { + return index_only_cost + (double) rows * INDEX_COPY_COST; + } } *opt_range; /* Bitmaps of key parts that =const for the duration of join execution. If @@ -1712,8 +1734,9 @@ public: Range_rowid_filter_cost_info * best_range_rowid_filter_for_partial_join(uint access_key_no, double records, - double access_cost_factor); - + double fetch_cost, + double index_only_cost, + double prev_records); /** System Versioning support */ @@ -1766,18 +1789,23 @@ public: DBUG_ASSERT(s->period.name); return field[s->period.end_fieldno]; } - void set_cond_selectivity(double selectivity) + inline void set_cond_selectivity(double selectivity) { DBUG_ASSERT(selectivity >= 0.0 and selectivity <= 1.0); cond_selectivity= selectivity; DBUG_PRINT("info", ("cond_selectivity: %g", cond_selectivity)); } - void multiply_cond_selectivity(double selectivity) + inline void multiply_cond_selectivity(double selectivity) { DBUG_ASSERT(selectivity >= 0.0 and selectivity <= 1.0); cond_selectivity*= selectivity; DBUG_PRINT("info", ("cond_selectivity: %g", cond_selectivity)); } + inline void set_opt_range_condition_rows(ha_rows rows) + { + if (opt_range_condition_rows > rows) + opt_range_condition_rows= rows; + } ulonglong vers_start_id() const; ulonglong vers_end_id() const; |