MySQL 9.4.0
Source Code Documentation
cost_model.h
Go to the documentation of this file.
1/* Copyright (c) 2020, 2025, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is designed to work with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have either included with
13 the program or referenced in the documentation.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
23
24#ifndef SQL_JOIN_OPTIMIZER_COST_MODEL_H_
25#define SQL_JOIN_OPTIMIZER_COST_MODEL_H_
26
27#include <algorithm> // std::clamp
28#include <span>
29
30#include "my_base.h"
31#include "my_bitmap.h" // bitmap_bits_set
32
36#include "sql/mem_root_array.h"
37#include "sql/table.h"
38
39struct AccessPath;
41class Item;
42class Query_block;
43class THD;
44
45/**
46 When we make cost estimates, we use this as the maximal length the
47 values we get from evaluating an Item (in bytes). Actual values of
48 e.g. blobs may be much longer, but even so we use this as an upper
49 limit when doing cost calculations. (For context, @see Item#max_length .)
50*/
51constexpr size_t kMaxItemLengthEstimate = 4096;
52
53/// A fallback cardinality estimate that is used in case the storage engine
54/// cannot provide one (like for table functions). It's a fairly arbitrary
55/// non-zero value.
57
58/**
59 We model the IO cost for InnoDB tables with the DYNAMIC row format. For
60 other storage engines the IO cost is currently set to zero. For other
61 InnoDB row formats, the model may not be a good fit.
62
63 We only count the cost of accessing the leaf pages of indexes (clustered
64 or unclustered)that are not already in the buffer pool. For tables/indexes
65 that are (estimated to be) fully cached we get an IO cost of zero.
66 Tables that are small relative to the buffer pool are assumed to be fully
67 cached (all pages are in the buffer pool).
68 The only operations for which we count IO cost are random and sequential
69 page reads.
70
71 The cost of a disk IO operation is modeled as an affine function:
72
73 io_cost = kIOStartCost + no_of_bytes * kIOByteCost
74
75 Note that the granularity of no_of_bytes is the storage engine page size.
76 The values used here are derived from measurements in a cloud setting.
77 This means that they may be wrong in another context, such as when
78 running against a local SSD. Cloud measurements may also give inconsistent
79 results due to heterogeneous cloud hardware, and the impact of activity
80 in other cloud VMs.
81 Ideally we should be able to configure these parameters, or even set them
82 dynamically based on observed behavior.
83*/
84constexpr double kIOStartCost{937.0};
85
86/// The additional cost of reading an extra byte from disk.
87constexpr double kIOByteCost{0.0549};
88
89/// This is the estimated fraction of an (innodb) block that is in use
90/// (i.e. not free for future inserts).
91constexpr double kBlockFillFactor{0.75};
92
93/// See EstimateFilterCost.
94struct FilterCost {
95 /// Cost of evaluating the filter for all rows if subqueries are not
96 /// materialized. (Note that this includes the contribution from
97 /// init_cost_if_not_materialized.)
99
100 /// Initial cost before the filter can be applied for the first time.
101 /// Typically the cost of executing 'independent subquery' in queries like:
102 /// "SELECT * FROM tab WHERE field = <independent subquery>".
103 /// (That corresponds to the Item_singlerow_subselect class.)
105
106 /// Cost of evaluating the filter for all rows if all subqueries in
107 /// it have been materialized beforehand. If there are no subqueries
108 /// in the condition, equals cost_if_not_materialized.
110
111 /// Cost of materializing all subqueries present in the filter.
112 /// If there are no subqueries in the condition, equals zero.
114};
115
116/// Used internally by EstimateFilterCost() only.
117void AddCost(THD *thd, const ContainedSubquery &subquery, double num_rows,
118 FilterCost *cost);
119
120/**
121 Estimate the cost of evaluating “condition”, “num_rows” times.
122 This is a fairly rudimentary estimation, _but_ it includes the cost
123 of any subqueries that may be present and that need evaluation.
124 */
125FilterCost EstimateFilterCost(THD *thd, double num_rows, Item *condition,
126 const Query_block *outer_query_block);
127
128/**
129 A cheaper overload of EstimateFilterCost() that assumes that all
130 contained subqueries have already been extracted (ie., it skips the
131 walking, which can be fairly expensive). This data is typically
132 computed by FindContainedSubqueries().
133 */
135 THD *thd, double num_rows,
136 const Mem_root_array<ContainedSubquery> &contained_subqueries) {
137 FilterCost cost;
140
141 for (const ContainedSubquery &subquery : contained_subqueries) {
142 AddCost(thd, subquery, num_rows, &cost);
143 }
144 return cost;
145}
146
147/**
148 Estimate costs and output rows for a SORT AccessPath.
149 @param thd Current thread.
150 @param path the AccessPath.
151 @param distinct_rows An estimate of the number of distinct rows, if
152 remove_duplicates==true and we have an estimate already.
153*/
155 double distinct_rows = kUnknownRowCount);
156
158
159/// Array of aggregation terms.
160using TermArray = std::span<const Item *const>;
161
162/**
163 Estimate the number of rows with a distinct combination of values for
164 'terms'. @see EstimateDistinctRowsFromStatistics for additional details.
165 @param thd The current thread.
166 @param child_rows The number of input rows.
167 @param terms The terms for which we estimate the number of unique
168 combinations.
169 @returns The estimated number of output rows.
170*/
171double EstimateDistinctRows(THD *thd, double child_rows, TermArray terms);
172/**
173 Estimate costs and result row count for an aggregate operation.
174 @param[in,out] thd The current thread.
175 @param[in,out] path The AGGREGATE path.
176 @param[in] query_block The Query_block to which 'path' belongs.
177 */
179 const Query_block *query_block);
182
183/// Estimate the costs and row count for a STREAM AccessPath.
185
186/**
187 Estimate the costs and row count for a WINDOW AccessPath. As described in
188 @see AccessPath::m_init_cost, the cost to read k out of N rows would be
189 init_cost + (k/N) * (cost - init_cost).
190*/
192
193/// Estimate the costs and row count for a Temp table Aggregate AccessPath.
195 const Query_block *query_block);
196
197/// Estimate the costs and row count for a WINDOW AccessPath.
199
200/**
201 Estimate the fan out for a left semijoin or a left antijoin. The fan out
202 is defined as the number of result rows, divided by the number of input
203 rows from the left hand relation. For a semijoin, J1:
204
205 SELECT ... FROM t1 WHERE EXISTS (SELECT ... FROM t2 WHERE predicate)
206
207 we know that the fan out of the corresponding inner join J2:
208
209 SELECT ... FROM t1, t2 WHERE predicate
210
211 is: F(J2) = CARD(t2) * SELECTIVITY(predicate) , where CARD(t2)=right_rows,
212 and SELECTIVITY(predicate)=edge.selectivity. If 'predicate' is a
213 deterministic function of t1 and t2 rows, then J1 is equivalent to an inner
214 join J3:
215
216 SELECT ... FROM t1 JOIN (SELECT DISTINCT f1,..fn FROM t2) d ON predicate
217
218 where f1,..fn are those fields from t2 that appear in the predicate.
219
220 Then F(J1) = F(J3) = F(J2) * CARD(d) / CARD(t2)
221 = CARD(d) * SELECTIVITY(predicate).
222
223 This function therefore collects f1..fn and estimates CARD(d). As a special
224 case, 'predicate' may be independent of t2. The query is then equivalent to:
225
226 SELECT ... FROM t1 WHERE predicate AND (SELECT COUNT(*) FROM t2) > 0
227
228 The fan out is then the selectivity of 'predicate' multiplied by the
229 probability of t2 having at least one row.
230
231 @param thd The current thread.
232 @param right_rows The number of input rows from the right hand relation.
233 @param edge Join edge.
234 @returns fan out.
235 */
236double EstimateSemijoinFanOut(THD *thd, double right_rows,
237 const JoinPredicate &edge);
238
239/**
240 Estimate the number of output rows from joining two relations.
241 @param thd The current thread.
242 @param left_rows Number of rows in the left hand relation.
243 @param right_rows Number of rows in the right hand relation.
244 @param edge The join between the two relations.
245*/
246inline double FindOutputRowsForJoin(THD *thd, double left_rows,
247 double right_rows,
248 const JoinPredicate *edge) {
249 switch (edge->expr->type) {
251 // For outer joins, every outer row produces at least one row (if none
252 // are matching, we get a NULL-complemented row).
253 // Note that this can cause inconsistent row counts; see bug #33550360
254 // and/or JoinHypergraph::has_reordered_left_joins.
255 return left_rows * std::max(right_rows * edge->selectivity, 1.0);
256
258 return left_rows * EstimateSemijoinFanOut(thd, right_rows, *edge);
259
261 // Antijoin are estimated as simply the opposite of semijoin (see above),
262 // but wrongly estimating 0 rows (or, of course, a negative amount) could
263 // be really bad, so we assume at least 10% coming out as a fudge factor.
264 // It's better to estimate too high than too low here.
265 return left_rows *
266 std::max(1.0 - EstimateSemijoinFanOut(thd, right_rows, *edge),
267 0.1);
268
271 return left_rows * right_rows * edge->selectivity;
272
273 case RelationalExpression::FULL_OUTER_JOIN: // Not implemented.
274 case RelationalExpression::MULTI_INNER_JOIN: // Should not appear here.
275 case RelationalExpression::TABLE: // Should not appear here.
276 assert(false);
277 return 0;
278
279 default:
280 assert(false);
281 return 0;
282 }
283}
284
285/**
286 Determines whether a given key on a table is both clustered and primary.
287
288 @param table The table to which the index belongs.
289 @param key_idx The position of the key in table->key_info[].
290
291 @return True if the key is clustered and primary, false otherwise.
292*/
293inline bool IsClusteredPrimaryKey(const TABLE *table, unsigned key_idx) {
294 if (table->s->is_missing_primary_key()) return false;
295 return key_idx == table->s->primary_key &&
296 table->file->primary_key_is_clustered();
297}
298
299/// The minimum number of bytes to return for row length estimates. This is
300/// mostly to guard against returning estimates of zero, which may or may not
301/// actually be able to happen in practice.
302constexpr unsigned kMinEstimatedBytesPerRow = 8;
303
304/// The maximum number of bytes to return for row length estimates. The current
305/// value of this constant is set to cover a wide range of row sizes and should
306/// capture the most common row lengths in bytes. We place an upper limit on the
307/// estimates since we have performed our calibration within this range, and we
308/// would like to prevent cost estimates from running away in case the
309/// underlying statistics are off in some instances. In such cases we prefer
310/// capping the resulting estimate. As a reasonable upper limit we use half the
311/// default InnoDB page size of 2^14 = 16384 bytes.
312constexpr unsigned kMaxEstimatedBytesPerRow = 8 * 1024;
313
314/**
315 This struct represents the number of bytes we expect to read for a table row.
316 Note that the split between b-tree and overflow pages is specific to InnoDB
317 and may not be a good fit for other storage engines. Ideally we should
318 calculate row size and IO-cost in the handler, in a way that is specific to
319 each particular storage engine.
320 When using the DYNAMIC row format, an InnoDB B-tree record cannot be bigger
321 than about half a page. (The default page size is 16KB). Above that, the
322 longest fields are stored in separate overflow pages.
323*/
325 /**
326 The number of bytes read from the B-tree record. This also includes those
327 fields that were not in the projection.
328 */
330
331 /**
332 The number of bytes read from overflow pages. This is the combined size
333 of those long variable-sized fields that are in the projection but stored
334 in overflow pages.
335 */
337
338 /*
339 The probability of reading from an overflow page (i.e. an estimate
340 of the probability that at least one of the columns in the
341 projection overflows).
342 */
344};
345
346/**
347 Estimate the average number of bytes that we need to read from the
348 storage engine when reading a row from 'table'. This is the size of
349 the (b-tree) record and the overflow pages of any field that is
350 part of the projection. This is similar to what EstimateBytesPerRowTable()
351 does, but this function is intended to do a more accurate but also more
352 expensive calculation for tables with potentially large rows (i.e. tables
353 with BLOBs or large VARCHAR fields).
354
355 Note that this function tailored for InnoDB (and also for the
356 DYNAMIC row format of InnoDB). At some point we may want to move
357 this logic to the handler, so that we can customize it for other
358 engines as well.
359
360 @param table The target table
361 @param max_row_size The row size if all variable-sized fields are full.
362 @returns The estimated row size.
363*/
365 int64_t max_row_size);
366
367/// We clamp the block size to lie in the interval between the max and min
368/// allowed block size for InnoDB (2^12 to 2^16). Ideally we would have a
369/// guarantee that stats.block_size has a reasonable value (across all storage
370/// engines, types of tables, state of statistics), but in the absence of such
371/// a guarantee we clamp to the values for the InnoDB storage engine since the
372/// cost model has been calibrated for these values.
373inline unsigned ClampedBlockSize(const TABLE *table) {
374 constexpr unsigned kMinEstimatedBlockSize = 4096;
375 constexpr unsigned kMaxEstimatedBlockSize = 65536;
376 return std::clamp(table->file->stats.block_size, kMinEstimatedBlockSize,
377 kMaxEstimatedBlockSize);
378}
379
380/**
381 Estimates the number of bytes that MySQL must process when reading a row from
382 a table, independently of the size of the read set.
383
384 @param table The table to produce an estimate for.
385
386 @returns The estimated row size.
387
388 @note There are two different relevant concepts of bytes per row:
389
390 1. The bytes per row on the storage engine side.
391 2. The bytes per row on the server side.
392
393 One the storage engine side, for InnoDB at least, we compute
394 stats.mean_rec_length as the size of the data file divided by the number of
395 rows in the table.
396
397 On the server side we are interested in the size of the MySQL representation
398 in bytes. This could be a more accurate statistic when determining the CPU
399 cost of processing a row (i.e., it does not matter very much if InnoDB pages
400 are only half-full). As an approximation to the size of a row in bytes on the
401 server side we use the length of the record buffer for rows that should
402 not exceed the maximal size of an InnoDB B-tree record. (Otherwise, we call
403 EstimateBytesPerRowWideTable() to make the estimate).
404
405 Note that when the table fits in a single page stats.mean_rec_length
406 will tend to overestimate the record length since it is computed as
407 stats.data_file_length / stats.records and the data file length is
408 at least a full page which defaults to 16384 bytes (for InnoDB at
409 least). We may then get a better estimate from table->s->rec_buff_length.
410*/
412 int64_t max_bytes{0};
413
414 for (uint i = 0; i < table->s->fields; i++) {
415 // field_length is the maximal size (in bytes) of this field.
416 max_bytes += table->field[i]->field_length;
417 }
418
419 if (max_bytes < ClampedBlockSize(table) / 2) {
420 // The row should fit in a b-tree record.
421 return {.record_bytes =
422 std::clamp(table->s->rec_buff_length, kMinEstimatedBytesPerRow,
424 .overflow_bytes = 0,
425 .overflow_probability = 0.0};
426 }
427
428 // Make a more sophisticated estimate for tables that may have very
429 // large rows.
430 return EstimateBytesPerRowWideTable(table, max_bytes);
431}
432
433/**
434 Estimates the number of bytes that MySQL must process when reading a row from
435 a secondary index, independently of the size of the read set.
436
437 @param table The table to which the index belongs.
438 @param key_idx The position of the key in table->key_info[].
439
440 @return The estimated number of bytes per row in the index.
441*/
442inline unsigned EstimateBytesPerRowIndex(const TABLE *table, unsigned key_idx) {
443 // key_length should correspond to the length of the field(s) of the key in
444 // bytes and ref_length is the length of the field(s) of the primary key in
445 // bytes. Secondary indexes (in InnoDB) contain a copy of the value of the
446 // primary key associated with a given row, in order to make it possible to
447 // retrieve the corresponding row from the primary index in case we use a
448 // non-covering index operation.
449 unsigned estimate =
450 table->key_info[key_idx].key_length + table->file->ref_length;
451 return std::clamp(estimate, kMinEstimatedBytesPerRow,
453}
454
455/**
456 Estimates the height of a B-tree index.
457
458 We estimate the height of the index to be the smallest positive integer h such
459 that table_records <= (1 + records_per_page)^h.
460
461 This function supports both clustered primary indexes and secondary indexes.
462 Secondary indexes will tend to have more records per page compared to primary
463 clustered indexes and as a consequence they will tend to be shorter.
464
465 @param table The table to which the index belongs.
466 @param key_idx The position of the key in table->key_info[].
467
468 @return The estimated height of the index.
469*/
470inline int IndexHeight(const TABLE *table, unsigned key_idx) {
471 unsigned block_size = ClampedBlockSize(table);
472 unsigned bytes_per_row = IsClusteredPrimaryKey(table, key_idx)
473 ? table->bytes_per_row()->record_bytes
475
476 // Ideally we should always have that block_size >= bytes_per_row, but since
477 // the storage engine and MySQL row formats differ, this is not always the
478 // case. Therefore we manually ensure that records_per_page >= 1.0.
479 double records_per_page =
480 std::max(1.0, static_cast<double>(block_size) / bytes_per_row);
481
482 // Computing the height using a while loop instead of using std::log turns out
483 // to be about 5 times faster in microbenchmarks when the measurement is made
484 // using a somewhat realistic and representative set of values for the number
485 // of records per page and the number of records in the table. In the worst
486 // case, if the B-tree contains only a single record per page, the table would
487 // have to contain 2^30 pages (corresponding to more than 16 terabytes of
488 // data) for this loop to run 30 times. A B-tree with 1 billion records and
489 // 100 records per page only uses 4 iterations of the loop (the height is 5).
490 int height = 1;
491 double r = 1.0 + records_per_page;
492 while (r < table->file->stats.records) {
493 r = r * (1.0 + records_per_page);
494 height += 1;
495 }
496 return height;
497}
498
499/// Calculate the IO-cost of reading 'num_rows' rows from 'table'.
500double TableAccessIOCost(const TABLE *table, double num_rows,
501 BytesPerTableRow row_size);
502
503/// Calculate the IO-cost of doing a lookup on index 'key_idx' on 'table'
504/// and then read 'num_rows' rows.
505double CoveringIndexAccessIOCost(const TABLE *table, unsigned key_idx,
506 double num_rows);
507
508/**
509 Computes the expected cost of reading a number of rows. The cost model takes
510 into account the number of fields that is being read from the row and the
511 width of the row in bytes. Both RowReadCostTable() and RowReadCostIndex() call
512 this function and thus use the same cost model.
513
514 @param num_rows The (expected) number of rows to read.
515 @param fields_read_per_row The number of fields to read per row.
516 @param bytes_per_row The total length of the row to be processed (including
517 fields that are not read) in bytes.
518
519 @returns The expected cost of reading num_rows.
520
521 @note It is important that this function be robust to fractional row
522 estimates. For example, if we index nested loop join two primary key columns
523 and the inner table is smaller than the outer table, we should see that
524 num_rows for the inner index lookup is less than one. In this case it is
525 important that we return the expected cost of the operation. For example, if
526 we only expect to read 0.1 rows the cost should be 0.1 of the cost of reading
527 one row (we are working with a linear cost model, so we only have to take the
528 expected number of rows into account, and not the complete distribution).
529*/
530inline double RowReadCost(double num_rows, double fields_read_per_row,
531 double bytes_per_row) {
532 return (kReadOneRowCost + kReadOneFieldCost * fields_read_per_row +
533 kReadOneByteCost * bytes_per_row) *
534 num_rows;
535}
536
537/**
538 Computes the cost of reading a number of rows from a table.
539 @see ReadRowCost() for further details.
540
541 @param table The table to read from.
542 @param num_rows The (expected) number of rows to read.
543
544 @returns The cost of reading num_rows.
545*/
546inline double RowReadCostTable(const TABLE *table, double num_rows) {
547 double fields_read_per_row = bitmap_bits_set(table->read_set);
548 const BytesPerTableRow &bytes_per_row = *table->bytes_per_row();
549 return RowReadCost(
550 num_rows, fields_read_per_row,
551 bytes_per_row.record_bytes + bytes_per_row.overflow_bytes) +
552 TableAccessIOCost(table, num_rows, bytes_per_row);
553}
554
555/**
556 Computes the cost of reading a number of rows from an index.
557 @see ReadRowCost() for further details.
558
559 @param table The table to which the index belongs.
560 @param key_idx The position of the key in table->key_info[].
561 @param num_rows The (expected) number of rows to read.
562
563 @returns The cost of reading num_rows.
564*/
565inline double RowReadCostIndex(const TABLE *table, unsigned key_idx,
566 double num_rows) {
567 if (IsClusteredPrimaryKey(table, key_idx)) {
568 return RowReadCostTable(table, num_rows);
569 }
570 // Assume we read two fields from the index record if it is not covering. The
571 // exact assumption here is not very important as the cost should be dominated
572 // by the additional lookup into the primary index.
573 constexpr double kDefaultFieldsReadFromCoveringIndex = 2;
574 double fields_read_per_row = table->covering_keys.is_set(key_idx)
575 ? bitmap_bits_set(table->read_set)
576 : kDefaultFieldsReadFromCoveringIndex;
577
578 double bytes_per_row = EstimateBytesPerRowIndex(table, key_idx);
579 return RowReadCost(num_rows, fields_read_per_row, bytes_per_row) +
580 CoveringIndexAccessIOCost(table, key_idx, num_rows);
581}
582
583/**
584 Estimates the cost of a full table scan. Primarily used to assign a cost to
585 the TABLE_SCAN access path.
586
587 @param table The table to estimate cost for.
588
589 @returns The cost of scanning the table.
590*/
591inline double EstimateTableScanCost(const TABLE *table) {
592 return RowReadCostTable(table, table->file->stats.records);
593}
594
595/**
596 Estimates the cost of an index lookup.
597
598 @param table The table to which the index belongs.
599 @param key_idx The position of the key in table->key_info[].
600
601 @return The estimated cost of an index lookup.
602
603 @note The model "cost ~ index_height" works well when the Adaptive Hash Index
604 (AHI) is disabled. The AHI essentially works as a dynamic cache for the most
605 frequently accessed index pages that sits on top of the B-tree. With AHI
606 enabled the cost of random lookups does not appear to be predictable using
607 standard explanatory variables such as index height or the logarithm of the
608 number of rows in the index. The performance of AHI will also be dependent on
609 the access pattern, so it is fundamentally difficult to create an accurate
610 model. However, our calibration experiments reveal two things that hold true
611 both with and without AHI enabled:
612
613 1. Index lookups usually take 1-3 microseconds. The height of a B-tree grows
614 very slowly (proportional to log(N)/log(R) for tables with N rows and R
615 records per page), making it near-constant in the common case where tables
616 have many records per page, even without AHI.
617
618 2. Random lookups in large indexes tend to be slower. A random access pattern
619 will cause more cache misses, both for regular hardware caching and AHI. In
620 addition, for a larger B-tree only the top levels fit in cache and we will
621 invariably see a few cache misses with random accesses.
622
623 We model the cost of index lookups by interpolating between a model with
624 constant cost and a model that depends entirely on the height of the index.
625 The constants are based on calibration experiments with and without AHI.
626
627 Another factor that is important when calibrating the cost of index lookups is
628 whether we are interested in the average cost when performing many lookups
629 such as when performing an index nested loop join or scanning along a
630 secondary non-covering index and lookup into the primary index, or the cost of
631 a single lookup such as a point select that uses an index. From our
632 measurements we see that the average running time of an index lookup can
633 easily be a factor ~5x faster when performing thousands of successive lookups
634 compared to just one. This is likely due to hardware caching effects. Since
635 getting the cost right in the case when we perform many lookups is typically
636 more important, we have opted to calibrate costs based on operations that
637 perform many lookups.
638
639 For adding IO costs to this model (future work) we probably want to assume
640 that we only fetch a single page when performing an index lookup, as
641 everything but leaf pages will tend to be cached, at least when performing
642 many index lookups in a query plan, which is exactly the case where it is
643 important to get costs right.
644*/
645inline double IndexLookupCost(const TABLE *table, unsigned key_idx) {
646 assert(key_idx < table->s->keys);
647 double cost_with_ahi = kIndexLookupFixedCost;
648 double cost_without_ahi = kIndexLookupPageCost * IndexHeight(table, key_idx);
649 return 0.5 * (cost_with_ahi + cost_without_ahi);
650}
651
652/// Type of range scan operation.
653enum class RangeScanType : char {
654 /// Using the MRR optimization.
656
657 /// Plain range scan, without the MRR optimization.
659};
660
661/**
662 Estimates the cost of an index range scan.
663
664 The cost model for index range scans accounts for the index lookup cost as
665 well as the cost of reading rows. Both index scans and ref accesses can be
666 viewed as special cases of index range scans, so the cost functions for those
667 operations call this function under the hood.
668
669 @note In the future this function should be extended to account for IO cost.
670
671 @param table The table to which the index belongs.
672 @param key_idx The position of the key in table->key_info[].
673 @param scan_type Whether this an MRR or a regular index range scan.
674 @param num_ranges The number of ranges.
675 @param num_output_rows The estimated expected number of output rows.
676
677 @returns The estimated cost of the index range scan operation.
678*/
679double EstimateIndexRangeScanCost(const TABLE *table, unsigned key_idx,
680 RangeScanType scan_type, double num_ranges,
681 double num_output_rows);
682
683/**
684 Estimates the cost of an index scan. An index scan scans all rows in the
685 table along the supplied index.
686
687 @param table The table to which the index belongs.
688 @param key_idx The position of the key in table->key_info[].
689
690 @returns The estimated cost of the index scan.
691*/
692inline double EstimateIndexScanCost(const TABLE *table, unsigned key_idx) {
694 1.0, table->file->stats.records);
695}
696
697/**
698 Estimates the cost of an index lookup (ref access).
699
700 @param table The table to which the index belongs.
701 @param key_idx The position of the key in table->key_info[].
702 @param num_output_rows The estimated number of output rows.
703
704 @returns The estimated cost of the index scan.
705*/
706inline double EstimateRefAccessCost(const TABLE *table, unsigned key_idx,
707 double num_output_rows) {
708 // We want the optimizer to prefer ref acccesses to range scans when they both
709 // have the same cost. This is particularly important for the EQ_REF access
710 // path (index lookups with at most one matching row) since the EQ_REF
711 // iterator uses caching to improve performance.
712 constexpr double kRefAccessCostDiscount = 0.05;
713 return (1.0 - kRefAccessCostDiscount) *
715 1.0, num_output_rows);
716}
717
718#endif // SQL_JOIN_OPTIMIZER_COST_MODEL_H_
constexpr double kUnknownRowCount
To indicate that a row estimate is not yet made.
Definition: access_path.h:196
Base class that is used to represent any kind of expression in a relational query.
Definition: item.h:927
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:432
This class represents a query block, aka a query specification, which is a query consisting of a SELE...
Definition: sql_lex.h:1179
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_lexer_thd.h:36
Hypergraph optimizer cost constants.
constexpr double kReadOneFieldCost
Cost of per field in the read set.
Definition: cost_constants.h:85
constexpr double kApplyOneFilterCost
Cost of evaluating one filter on one row.
Definition: cost_constants.h:117
constexpr double kReadOneRowCost
Fixed cost of reading a row from the storage engine into the record buffer.
Definition: cost_constants.h:81
constexpr double kIndexLookupPageCost
The cost per page that is visited when performing an index lookup in an InnoDB B-tree.
Definition: cost_constants.h:129
constexpr double kIndexLookupFixedCost
Fixed cost of an index lookup when AHI is enabled (default).
Definition: cost_constants.h:132
constexpr double kReadOneByteCost
Overhead per byte when reading a row.
Definition: cost_constants.h:95
double RowReadCost(double num_rows, double fields_read_per_row, double bytes_per_row)
Computes the expected cost of reading a number of rows.
Definition: cost_model.h:530
constexpr ha_rows kRowEstimateFallback
A fallback cardinality estimate that is used in case the storage engine cannot provide one (like for ...
Definition: cost_model.h:56
double EstimateRefAccessCost(const TABLE *table, unsigned key_idx, double num_output_rows)
Estimates the cost of an index lookup (ref access).
Definition: cost_model.h:706
double TableAccessIOCost(const TABLE *table, double num_rows, BytesPerTableRow row_size)
Calculate the IO-cost of reading 'num_rows' rows from 'table'.
Definition: cost_model.cc:418
void EstimateSortCost(THD *thd, AccessPath *path, double distinct_rows=kUnknownRowCount)
Estimate costs and output rows for a SORT AccessPath.
Definition: cost_model.cc:605
void EstimateTemptableAggregateCost(THD *thd, AccessPath *path, const Query_block *query_block)
Estimate the costs and row count for a Temp table Aggregate AccessPath.
Definition: cost_model.cc:1640
RangeScanType
Type of range scan operation.
Definition: cost_model.h:653
@ kSingleRange
Plain range scan, without the MRR optimization.
@ kMultiRange
Using the MRR optimization.
BytesPerTableRow EstimateBytesPerRowTable(const TABLE *table)
Estimates the number of bytes that MySQL must process when reading a row from a table,...
Definition: cost_model.h:411
void EstimateWindowCost(AccessPath *path)
Estimate the costs and row count for a WINDOW AccessPath.
Definition: cost_model.cc:1684
bool IsClusteredPrimaryKey(const TABLE *table, unsigned key_idx)
Determines whether a given key on a table is both clustered and primary.
Definition: cost_model.h:293
double CoveringIndexAccessIOCost(const TABLE *table, unsigned key_idx, double num_rows)
Calculate the IO-cost of doing a lookup on index 'key_idx' on 'table' and then read 'num_rows' rows.
Definition: cost_model.cc:473
double EstimateTableScanCost(const TABLE *table)
Estimates the cost of a full table scan.
Definition: cost_model.h:591
constexpr size_t kMaxItemLengthEstimate
When we make cost estimates, we use this as the maximal length the values we get from evaluating an I...
Definition: cost_model.h:51
void AddCost(THD *thd, const ContainedSubquery &subquery, double num_rows, FilterCost *cost)
Used internally by EstimateFilterCost() only.
Definition: cost_model.cc:662
double EstimateIndexScanCost(const TABLE *table, unsigned key_idx)
Estimates the cost of an index scan.
Definition: cost_model.h:692
void EstimateLimitOffsetCost(AccessPath *path)
Estimate the costs and row count for a WINDOW AccessPath.
Definition: cost_model.cc:1607
double RowReadCostIndex(const TABLE *table, unsigned key_idx, double num_rows)
Computes the cost of reading a number of rows from an index.
Definition: cost_model.h:565
std::span< const Item *const > TermArray
Array of aggregation terms.
Definition: cost_model.h:160
void EstimateDeleteRowsCost(AccessPath *path)
Definition: cost_model.cc:1550
constexpr unsigned kMinEstimatedBytesPerRow
The minimum number of bytes to return for row length estimates.
Definition: cost_model.h:302
int IndexHeight(const TABLE *table, unsigned key_idx)
Estimates the height of a B-tree index.
Definition: cost_model.h:470
double EstimateIndexRangeScanCost(const TABLE *table, unsigned key_idx, RangeScanType scan_type, double num_ranges, double num_output_rows)
Estimates the cost of an index range scan.
Definition: cost_model.cc:518
double FindOutputRowsForJoin(THD *thd, double left_rows, double right_rows, const JoinPredicate *edge)
Estimate the number of output rows from joining two relations.
Definition: cost_model.h:246
void EstimateUpdateRowsCost(AccessPath *path)
Definition: cost_model.cc:1567
constexpr double kBlockFillFactor
This is the estimated fraction of an (innodb) block that is in use (i.e.
Definition: cost_model.h:91
unsigned ClampedBlockSize(const TABLE *table)
We clamp the block size to lie in the interval between the max and min allowed block size for InnoDB ...
Definition: cost_model.h:373
constexpr double kIOStartCost
We model the IO cost for InnoDB tables with the DYNAMIC row format.
Definition: cost_model.h:84
double EstimateDistinctRows(THD *thd, double child_rows, TermArray terms)
Estimate the number of rows with a distinct combination of values for 'terms'.
Definition: cost_model.cc:1499
BytesPerTableRow EstimateBytesPerRowWideTable(const TABLE *table, int64_t max_row_size)
Estimate the average number of bytes that we need to read from the storage engine when reading a row ...
Definition: cost_model.cc:317
void EstimateMaterializeCost(THD *thd, AccessPath *path)
Provide row estimates and costs for a MATERIALIZE AccessPath.
Definition: cost_model.cc:827
double IndexLookupCost(const TABLE *table, unsigned key_idx)
Estimates the cost of an index lookup.
Definition: cost_model.h:645
void EstimateStreamCost(THD *thd, AccessPath *path)
Estimate the costs and row count for a STREAM AccessPath.
Definition: cost_model.cc:1584
void EstimateAggregateCost(THD *thd, AccessPath *path, const Query_block *query_block)
Estimate costs and result row count for an aggregate operation.
Definition: cost_model.cc:1528
unsigned EstimateBytesPerRowIndex(const TABLE *table, unsigned key_idx)
Estimates the number of bytes that MySQL must process when reading a row from a secondary index,...
Definition: cost_model.h:442
FilterCost EstimateFilterCost(THD *thd, double num_rows, Item *condition, const Query_block *outer_query_block)
Estimate the cost of evaluating “condition”, “num_rows” times.
Definition: cost_model.cc:703
constexpr unsigned kMaxEstimatedBytesPerRow
The maximum number of bytes to return for row length estimates.
Definition: cost_model.h:312
double EstimateSemijoinFanOut(THD *thd, double right_rows, const JoinPredicate &edge)
Estimate the fan out for a left semijoin or a left antijoin.
Definition: cost_model.cc:1694
double RowReadCostTable(const TABLE *table, double num_rows)
Computes the cost of reading a number of rows from a table.
Definition: cost_model.h:546
constexpr double kIOByteCost
The additional cost of reading an extra byte from disk.
Definition: cost_model.h:87
This file includes constants used by all storage engines.
my_off_t ha_rows
Definition: my_base.h:1217
uint bitmap_bits_set(const MY_BITMAP *map)
Definition: my_bitmap.cc:416
static char * path
Definition: mysqldump.cc:150
static PFS_engine_table_share_proxy table
Definition: pfs.cc:61
Definition: os0file.h:89
ValueType max(X &&first)
Definition: gtid.h:103
T clamp(U x)
Definition: ut0ut.h:412
const mysql_service_registry_t * r
Definition: pfs_example_plugin_employee.cc:86
Access paths are a query planning structure that correspond 1:1 to iterators, in that an access path ...
Definition: access_path.h:238
This struct represents the number of bytes we expect to read for a table row.
Definition: cost_model.h:324
int64_t overflow_bytes
The number of bytes read from overflow pages.
Definition: cost_model.h:336
double overflow_probability
Definition: cost_model.h:343
int64_t record_bytes
The number of bytes read from the B-tree record.
Definition: cost_model.h:329
This class represents a subquery contained in some subclass of Item_subselect,.
Definition: item.h:859
See EstimateFilterCost.
Definition: cost_model.h:94
double init_cost_if_not_materialized
Initial cost before the filter can be applied for the first time.
Definition: cost_model.h:104
double cost_to_materialize
Cost of materializing all subqueries present in the filter.
Definition: cost_model.h:113
double cost_if_materialized
Cost of evaluating the filter for all rows if all subqueries in it have been materialized beforehand.
Definition: cost_model.h:109
double cost_if_not_materialized
Cost of evaluating the filter for all rows if subqueries are not materialized.
Definition: cost_model.h:98
A specification that two specific relational expressions (e.g., two tables, or a table and a join bet...
Definition: access_path.h:80
RelationalExpression * expr
Definition: access_path.h:81
double selectivity
Definition: access_path.h:82
enum RelationalExpression::Type type
@ SEMIJOIN
Left semijoin.
Definition: relational_expression.h:153
@ MULTI_INNER_JOIN
Definition: relational_expression.h:175
@ STRAIGHT_INNER_JOIN
Definition: relational_expression.h:161
@ ANTIJOIN
Left antijoin.
Definition: relational_expression.h:156
@ INNER_JOIN
Definition: relational_expression.h:149
@ FULL_OUTER_JOIN
Definition: relational_expression.h:168
@ TABLE
Definition: relational_expression.h:177
@ LEFT_JOIN
Definition: relational_expression.h:150
Definition: table.h:1433