MySQL  8.0.27
Source Code Documentation
access_path.h
Go to the documentation of this file.
1 /* Copyright (c) 2020, 2021, 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 also distributed 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 included with MySQL.
13 
14  This program is distributed in the hope that it will be useful,
15  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  GNU General Public License, version 2.0, for more details.
18 
19  You should have received a copy of the GNU General Public License
20  along with this program; if not, write to the Free Software
21  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
22 
23 #ifndef SQL_JOIN_OPTIMIZER_ACCESS_PATH_H
24 #define SQL_JOIN_OPTIMIZER_ACCESS_PATH_H
25 
26 #include <assert.h>
27 #include <stdint.h>
28 
29 #include <string>
30 #include <type_traits>
31 #include <vector>
32 
37 #include "sql/join_type.h"
38 #include "sql/mem_root_array.h"
39 #include "sql/sql_class.h"
40 
41 class Common_table_expr;
42 class Filesort;
43 class Item;
44 class Item_func_match;
45 class JOIN;
46 class KEY;
47 class RowIterator;
48 class QEP_TAB;
49 class QUICK_SELECT_I;
50 class SJ_TMP_TABLE;
51 class Table_function;
52 class Temp_table_param;
53 class Window;
54 struct AccessPath;
55 struct ORDER;
56 struct POSITION;
58 struct TABLE;
59 struct TABLE_REF;
60 
61 /**
62  A specification that two specific relational expressions
63  (e.g., two tables, or a table and a join between two other tables)
64  should be joined together. The actual join conditions, if any,
65  live inside the “expr” object, as does the join type etc.
66  */
67 struct JoinPredicate {
69  double selectivity;
70 
71  // If this join is made using a hash join, estimates the width
72  // of each row as stored in the hash table, in bytes.
74 
75  // The set of (additional) functional dependencies that are active
76  // after this join predicate has been applied. E.g. if we're joining
77  // on t1.x = t2.x, there will be a bit for that functional dependency.
78  // We don't currently support more complex join conditions, but there's
79  // no conceptual reason why we couldn't, e.g. a join on a = b + c
80  // could give rise to the FD {b, c} → a and possibly even {a, b} → c
81  // or {a, c} → b.
82  //
83  // Used in the processing of interesting orders.
85 
86  // A less compact form of functional_dependencies, used during building
87  // (FunctionalDependencySet bitmaps are only available after all functional
88  // indexes have been collected and Build() has been called).
90 
91  // If this is a suitable semijoin: Contains the grouping given by the
92  // join key. If the rows are in this grouping, then the join optimizer will
93  // consider deduplicating on it and inverting the join. -1 otherwise.
95 
96  // Same as ordering_idx_needed_for_semijoin_rewrite, but given to the
97  // RemoveDuplicatesIterator for doing the actual grouping. Allocated
98  // on the MEM_ROOT. Can be empty, in which case a LIMIT 1 would do.
99  Item **semijoin_group = nullptr;
101 };
102 
103 /**
104  A filter of some sort that is not a join condition (those are stored
105  in JoinPredicate objects). AND conditions are typically split up into
106  multiple Predicates.
107  */
108 struct Predicate {
110 
111  // condition->used_tables(), converted to a NodeMap.
113 
114  // tables referred to by the condition, plus any tables whose values
115  // can null any of those tables. (Even when reordering outer joins,
116  // at least one of those tables will still be present on the
117  // left-hand side of the outer join, so this is sufficient.)
118  //
119  // As a special case, we allow setting RAND_TABLE_BIT, even though it
120  // is normally part of a table_map, not a NodeMap.
122 
123  double selectivity;
124 
125  // Whether this predicate is a join condition after all; it was promoted
126  // to a WHERE predicate since it was part of a cycle (see the comment in
127  // AddCycleEdges()). If it is, it is usually ignored so that we don't
128  // double-apply join conditions -- but if the join in question was not
129  // applied (because the cycle was broken at this point), the predicate
130  // would come into play. This is normally registered on the join itself
131  // (see RelationalExpression::join_predicate_bitmap), but having the bit
132  // on the predicate itself is used to avoid trying to push it down as a
133  // sargable predicate.
134  bool was_join_condition = false;
135 
136  // If this is a join condition that came from a multiple equality,
137  // and we have decided to create a mesh from that multiple equality,
138  // returns the index of it into the “multiple_equalities” array
139  // in MakeJoinHypergraph(). (You don't actually need the array to
140  // use this; it's just an opaque index to deduplicate between different
141  // predicates.) Otherwise, -1.
143 
144  // See the equivalent fields in JoinPredicate.
147 };
148 
152 };
153 
154 /**
155  Access paths are a query planning structure that correspond 1:1 to iterators,
156  in that an access path contains pretty much exactly the information
157  needed to instantiate given iterator, plus some information that is only
158  needed during planning, such as costs. (The new join optimizer will extend
159  this somewhat in the future. Some iterators also need the query block,
160  ie., JOIN object, they are part of, but that is implicitly available when
161  constructing the tree.)
162 
163  AccessPath objects build on a variant, ie., they can hold an access path of
164  any type (table scan, filter, hash join, sort, etc.), although only one at the
165  same time. Currently, they contain 32 bytes of base information that is common
166  to any access path (type identifier, costs, etc.), and then up to 40 bytes
167  that is type-specific (e.g. for a table scan, the TABLE object). It would be
168  nice if we could squeeze it down to 64 and fit a cache line exactly, but it
169  does not seem to be easy without fairly large contortions.
170 
171  We could have solved this by inheritance, but the fixed-size design makes it
172  possible to replace an access path when a better one is found, without
173  introducing a new allocation, which will be important when using them as a
174  planning structure.
175  */
176 struct AccessPath {
177  enum Type : uint8_t {
178  // Basic access paths (those with no children, at least nominally).
191 
192  // Basic access paths that don't correspond to a specific table.
199 
200  // Joins.
205 
206  // Composite access paths.
222  } type;
223 
224  /// Whether this access path counts as one that scans a base table,
225  /// and thus should be counted towards examined_rows. It can sometimes
226  /// seem a bit arbitrary which iterators count towards examined_rows
227  /// and which ones do not, so the only canonical reference is the tests.
228  bool count_examined_rows = false;
229 
230  /// A general enum to describe the safety of a given operation.
231  /// Currently we only use this to describe row IDs, but it can easily
232  /// be reused for safety of updating a table we're reading from
233  /// (the Halloween problem), or just generally unreproducible results
234  /// (e.g. a TABLESAMPLE changing due to external factors).
235  ///
236  /// Less safe values have higher numerical values.
237  enum Safety : uint8_t {
238  /// The given operation is always safe on this access path.
239  SAFE = 0,
240 
241  /// The given operation is safe if this access path is scanned once,
242  /// but not if it's scanned multiple times (e.g. used on the inner side
243  /// of a nested-loop join). A typical example of this is a derived table
244  /// or CTE that is rematerialized on each scan, so that references to
245  /// the old values (such as row IDs) are no longer valid.
247 
248  /// The given operation is unsafe on this access path, no matter how many
249  /// or few times it's scanned. Often, it may help to materialize it
250  /// (assuming the materialization itself doesn't use the operation
251  /// in question).
252  UNSAFE = 2
253  };
254 
255  /// Whether it is safe to get row IDs (for sorting) from this access path.
257 
258  /// Which ordering the rows produced by this path follow, if any
259  /// (see interesting_orders.h). This is really a LogicalOrderings::StateIndex,
260  /// but we don't want to add a dependency on interesting_orders.h from
261  /// this file, so we use the base type instead of the typedef here.
262  int ordering_state = 0;
263 
264  /// If an iterator has been instantiated for this access path, points to the
265  /// iterator. Used for constructing iterators that need to talk to each other
266  /// (e.g. for recursive CTEs, or BKA join), and also for locating timing
267  /// information in EXPLAIN ANALYZE queries.
268  RowIterator *iterator = nullptr;
269 
270  /// Expected number of output rows, -1.0 for unknown.
271  double num_output_rows{-1.0};
272 
273  /// Expected cost to read all of this access path once; -1.0 for unknown.
274  double cost{-1.0};
275 
276  /// Expected cost to initialize this access path; ie., cost to read
277  /// k out of N rows would be init_cost + (k/N) * (cost - init_cost).
278  /// Note that EXPLAIN prints out cost of reading the _first_ row
279  /// because it is easier for the user and also easier to measure in
280  /// EXPLAIN ANALYZE, but it is easier to do calculations with a pure
281  /// initialization cost, so that is what we use in this member.
282  /// -1.0 for unknown.
283  double init_cost{-1.0};
284 
285  /// Of init_cost, how much of the initialization needs only to be done
286  /// once per query block. (This is a cost, not a proportion.)
287  /// Ie., if the access path can reuse some its initialization work
288  /// if Init() is called multiple times, this member will be nonzero.
289  /// A typical example is a materialized table with rematerialize=false;
290  /// the second time Init() is called, it's a no-op. Most paths will have
291  /// init_once_cost = 0.0, ie., repeated scans will cost the same.
292  /// We do not intend to use this field to model cache effects.
293  ///
294  /// This is currently not printed in EXPLAIN, only optimizer trace.
295  double init_once_cost{0.0};
296 
297  /// If no filter, identical to num_output_rows, cost, respectively.
298  /// init_cost is always the same (filters have zero initialization cost).
300 
301  /// Bitmap of WHERE predicates that we are including on this access path,
302  /// referring to the “predicates” array internal to the join optimizer.
303  /// Since bit masks are much cheaper to deal with than creating Item
304  /// objects, and we don't invent new conditions during join optimization
305  /// (all of them are known when we begin optimization), we stick to
306  /// manipulating bit masks during optimization, saying which filters will be
307  /// applied at this node (a 1-bit means the filter will be applied here; if
308  /// there are multiple ones, they are ANDed together).
309  ///
310  /// This is used during join optimization only; before iterators are
311  /// created, we will add FILTER access paths to represent these instead,
312  /// removing the dependency on the array. Said FILTER paths are by
313  /// convention created with materialize_subqueries = false, since the by far
314  /// most common case is that there are no subqueries in the predicate. In
315  /// other words, if you wish to represent a filter with
316  /// materialize_subqueries = true, you will nede to make an explicit FILTER
317  /// node.
319 
320  /// Bitmap of sargable join predicates that have already been applied
321  /// in this access path by means of an index lookup (ref access),
322  /// again referring to “predicates”, and thus should not be counted again
323  /// for selectivity. Note that the filter may need to be applied
324  /// nevertheless (especially in case of type conversions); see
325  /// subsumed_sargable_join_predicates.
326  ///
327  /// Since these refer to the same array as filter_predicates, they will
328  /// never overlap with filter_predicates, and so we can reuse the same
329  /// memory using an alias (a union would not be allowed, since OverflowBitset
330  /// is a class with non-trivial default constructor), even though the meaning
331  /// is entirely separate. If N = num_where_predictes in the hypergraph, then
332  /// bits 0..(N-1) belong to filter_predicates, and the rest to
333  /// applied_sargable_join_predicates.
335  return filter_predicates;
336  }
338  return filter_predicates;
339  }
340 
341  /// Bitmap of WHERE predicates that touch tables we have joined in,
342  /// but that we could not apply yet (for instance because they reference
343  /// other tables, or because because we could not push them down into
344  /// the nullable side of outer joins). Used during planning only
345  /// (see filter_predicates).
347 
348  /// Similar to applied_sargable_join_predicates, bitmap of sargable
349  /// join predicates that have been applied and will subsume the join
350  /// predicate entirely, ie., not only should the selectivity not be
351  /// double-counted, but the predicate itself is redundant and need not
352  /// be applied as a filter. (It is an error to have a bit set here but not
353  /// in applied_sargable_join_predicates.)
355  return delayed_predicates;
356  }
358  return delayed_predicates;
359  }
360 
361  /// If nonzero, a bitmap of other tables whose joined-in rows must already be
362  /// loaded when rows from this access path are evaluated; that is, this
363  /// access path must be put on the inner side of a nested-loop join (or
364  /// multiple such joins) where the outer side includes all of the given
365  /// tables.
366  ///
367  /// The most obvious case for this is dependent tables in LATERAL, but a more
368  /// common case is when we have pushed join conditions referring to those
369  /// tables; e.g., if this access path represents t1 and we have a condition
370  /// t1.x=t2.x that is pushed down into an index lookup (ref access), t2 will
371  /// be set in this bitmap. We can still join in other tables, deferring t2,
372  /// but the bit(s) will then propagate, and we cannot be on the right side of
373  /// a hash join until parameter_tables is zero again.
374  ///
375  /// As a special case, we allow setting RAND_TABLE_BIT, even though it
376  /// is normally part of a table_map, not a NodeMap. In this case, it specifies
377  /// that the access path is entirely noncachable, because it depends on
378  /// something nondeterministic or an outer reference, and thus can never be on
379  /// the right side of a hash join, ever.
381 
382  /// Auxiliary data used by a secondary storage engine while processing the
383  /// access path during optimization and execution. The secondary storage
384  /// engine is free to store any useful information in this member, for example
385  /// extra statistics or cost estimates. The data pointed to is fully owned by
386  /// the secondary storage engine, and it is the responsibility of the
387  /// secondary engine to manage the memory and make sure it is properly
388  /// destroyed.
389  void *secondary_engine_data{nullptr};
390 
391  // Accessors for the union below.
392  auto &table_scan() {
393  assert(type == TABLE_SCAN);
394  return u.table_scan;
395  }
396  const auto &table_scan() const {
397  assert(type == TABLE_SCAN);
398  return u.table_scan;
399  }
400  auto &index_scan() {
401  assert(type == INDEX_SCAN);
402  return u.index_scan;
403  }
404  const auto &index_scan() const {
405  assert(type == INDEX_SCAN);
406  return u.index_scan;
407  }
408  auto &ref() {
409  assert(type == REF);
410  return u.ref;
411  }
412  const auto &ref() const {
413  assert(type == REF);
414  return u.ref;
415  }
416  auto &ref_or_null() {
417  assert(type == REF_OR_NULL);
418  return u.ref_or_null;
419  }
420  const auto &ref_or_null() const {
421  assert(type == REF_OR_NULL);
422  return u.ref_or_null;
423  }
424  auto &eq_ref() {
425  assert(type == EQ_REF);
426  return u.eq_ref;
427  }
428  const auto &eq_ref() const {
429  assert(type == EQ_REF);
430  return u.eq_ref;
431  }
432  auto &pushed_join_ref() {
433  assert(type == PUSHED_JOIN_REF);
434  return u.pushed_join_ref;
435  }
436  const auto &pushed_join_ref() const {
437  assert(type == PUSHED_JOIN_REF);
438  return u.pushed_join_ref;
439  }
441  assert(type == FULL_TEXT_SEARCH);
442  return u.full_text_search;
443  }
444  const auto &full_text_search() const {
445  assert(type == FULL_TEXT_SEARCH);
446  return u.full_text_search;
447  }
448  auto &const_table() {
449  assert(type == CONST_TABLE);
450  return u.const_table;
451  }
452  const auto &const_table() const {
453  assert(type == CONST_TABLE);
454  return u.const_table;
455  }
456  auto &mrr() {
457  assert(type == MRR);
458  return u.mrr;
459  }
460  const auto &mrr() const {
461  assert(type == MRR);
462  return u.mrr;
463  }
464  auto &follow_tail() {
465  assert(type == FOLLOW_TAIL);
466  return u.follow_tail;
467  }
468  const auto &follow_tail() const {
469  assert(type == FOLLOW_TAIL);
470  return u.follow_tail;
471  }
473  assert(type == INDEX_RANGE_SCAN);
474  return u.index_range_scan;
475  }
476  const auto &index_range_scan() const {
477  assert(type == INDEX_RANGE_SCAN);
478  return u.index_range_scan;
479  }
481  assert(type == DYNAMIC_INDEX_RANGE_SCAN);
482  return u.dynamic_index_range_scan;
483  }
484  const auto &dynamic_index_range_scan() const {
485  assert(type == DYNAMIC_INDEX_RANGE_SCAN);
486  return u.dynamic_index_range_scan;
487  }
490  return u.materialized_table_function;
491  }
492  const auto &materialized_table_function() const {
494  return u.materialized_table_function;
495  }
497  assert(type == UNQUALIFIED_COUNT);
498  return u.unqualified_count;
499  }
500  const auto &unqualified_count() const {
501  assert(type == UNQUALIFIED_COUNT);
502  return u.unqualified_count;
503  }
505  assert(type == TABLE_VALUE_CONSTRUCTOR);
506  return u.table_value_constructor;
507  }
508  const auto &table_value_constructor() const {
509  assert(type == TABLE_VALUE_CONSTRUCTOR);
510  return u.table_value_constructor;
511  }
512  auto &fake_single_row() {
513  assert(type == FAKE_SINGLE_ROW);
514  return u.fake_single_row;
515  }
516  const auto &fake_single_row() const {
517  assert(type == FAKE_SINGLE_ROW);
518  return u.fake_single_row;
519  }
520  auto &zero_rows() {
521  assert(type == ZERO_ROWS);
522  return u.zero_rows;
523  }
524  const auto &zero_rows() const {
525  assert(type == ZERO_ROWS);
526  return u.zero_rows;
527  }
529  assert(type == ZERO_ROWS_AGGREGATED);
530  return u.zero_rows_aggregated;
531  }
532  const auto &zero_rows_aggregated() const {
533  assert(type == ZERO_ROWS_AGGREGATED);
534  return u.zero_rows_aggregated;
535  }
536  auto &hash_join() {
537  assert(type == HASH_JOIN);
538  return u.hash_join;
539  }
540  const auto &hash_join() const {
541  assert(type == HASH_JOIN);
542  return u.hash_join;
543  }
544  auto &bka_join() {
545  assert(type == BKA_JOIN);
546  return u.bka_join;
547  }
548  const auto &bka_join() const {
549  assert(type == BKA_JOIN);
550  return u.bka_join;
551  }
553  assert(type == NESTED_LOOP_JOIN);
554  return u.nested_loop_join;
555  }
556  const auto &nested_loop_join() const {
557  assert(type == NESTED_LOOP_JOIN);
558  return u.nested_loop_join;
559  }
562  return u.nested_loop_semijoin_with_duplicate_removal;
563  }
566  return u.nested_loop_semijoin_with_duplicate_removal;
567  }
568  auto &filter() {
569  assert(type == FILTER);
570  return u.filter;
571  }
572  const auto &filter() const {
573  assert(type == FILTER);
574  return u.filter;
575  }
576  auto &sort() {
577  assert(type == SORT);
578  return u.sort;
579  }
580  const auto &sort() const {
581  assert(type == SORT);
582  return u.sort;
583  }
584  auto &aggregate() {
585  assert(type == AGGREGATE);
586  return u.aggregate;
587  }
588  const auto &aggregate() const {
589  assert(type == AGGREGATE);
590  return u.aggregate;
591  }
593  assert(type == TEMPTABLE_AGGREGATE);
594  return u.temptable_aggregate;
595  }
596  const auto &temptable_aggregate() const {
597  assert(type == TEMPTABLE_AGGREGATE);
598  return u.temptable_aggregate;
599  }
600  auto &limit_offset() {
601  assert(type == LIMIT_OFFSET);
602  return u.limit_offset;
603  }
604  const auto &limit_offset() const {
605  assert(type == LIMIT_OFFSET);
606  return u.limit_offset;
607  }
608  auto &stream() {
609  assert(type == STREAM);
610  return u.stream;
611  }
612  const auto &stream() const {
613  assert(type == STREAM);
614  return u.stream;
615  }
616  auto &materialize() {
617  assert(type == MATERIALIZE);
618  return u.materialize;
619  }
620  const auto &materialize() const {
621  assert(type == MATERIALIZE);
622  return u.materialize;
623  }
626  return u.materialize_information_schema_table;
627  }
630  return u.materialize_information_schema_table;
631  }
632  auto &append() {
633  assert(type == APPEND);
634  return u.append;
635  }
636  const auto &append() const {
637  assert(type == APPEND);
638  return u.append;
639  }
640  auto &window() {
641  assert(type == WINDOW);
642  return u.window;
643  }
644  const auto &window() const {
645  assert(type == WINDOW);
646  return u.window;
647  }
648  auto &weedout() {
649  assert(type == WEEDOUT);
650  return u.weedout;
651  }
652  const auto &weedout() const {
653  assert(type == WEEDOUT);
654  return u.weedout;
655  }
657  assert(type == REMOVE_DUPLICATES);
658  return u.remove_duplicates;
659  }
660  const auto &remove_duplicates() const {
661  assert(type == REMOVE_DUPLICATES);
662  return u.remove_duplicates;
663  }
665  assert(type == REMOVE_DUPLICATES_ON_INDEX);
666  return u.remove_duplicates_on_index;
667  }
668  const auto &remove_duplicates_on_index() const {
669  assert(type == REMOVE_DUPLICATES_ON_INDEX);
670  return u.remove_duplicates_on_index;
671  }
672  auto &alternative() {
673  assert(type == ALTERNATIVE);
674  return u.alternative;
675  }
676  const auto &alternative() const {
677  assert(type == ALTERNATIVE);
678  return u.alternative;
679  }
681  assert(type == CACHE_INVALIDATOR);
682  return u.cache_invalidator;
683  }
684  const auto &cache_invalidator() const {
685  assert(type == CACHE_INVALIDATOR);
686  return u.cache_invalidator;
687  }
688 
689  private:
690  // We'd prefer if this could be an std::variant, but we don't have C++17 yet.
691  // It is private to force all access to be through the type-checking
692  // accessors.
693  //
694  // For information about the meaning of each value, see the corresponding
695  // row iterator constructors.
696  union {
697  struct {
700  struct {
701  TABLE *table;
702  int idx;
703  bool use_order;
704  bool reverse;
706  struct {
707  TABLE *table;
709  bool use_order;
710  bool reverse;
711  } ref;
712  struct {
713  TABLE *table;
714  TABLE_REF *ref;
715  bool use_order;
717  struct {
718  TABLE *table;
719  TABLE_REF *ref;
720  bool use_order;
722  struct {
723  TABLE *table;
724  TABLE_REF *ref;
725  bool use_order;
726  bool is_unique;
728  struct {
729  TABLE *table;
730  TABLE_REF *ref;
731  bool use_order;
732  bool use_limit;
735  struct {
736  TABLE *table;
737  TABLE_REF *ref;
739  struct {
740  TABLE *table;
741  TABLE_REF *ref;
745  } mrr;
746  struct {
747  TABLE *table;
749  struct {
750  TABLE *table;
753  struct {
754  TABLE *table;
755  QEP_TAB *qep_tab; // Used only for buffering.
757  struct {
758  TABLE *table;
762  struct {
764 
765  struct {
766  // No members (implicit from the JOIN).
768  struct {
769  // No members.
771  struct {
772  // See ZeroRowsIterator for an explanation as of why there is
773  // a child path here.
775  // Used for EXPLAIN only.
776  // TODO(sgunders): make an enum.
777  const char *cause;
779  struct {
780  // Used for EXPLAIN only.
781  // TODO(sgunders): make an enum.
782  const char *cause;
784 
785  struct {
789  bool store_rowids; // Whether we are below a weedout or not.
793  struct {
797  float rec_per_key;
798  bool store_rowids; // Whether we are below a weedout or not.
801  struct {
806  struct {
808  const TABLE *table;
810  size_t key_len;
812 
813  struct {
814  AccessPath *child;
816 
817  // This parameter, unlike nearly all others, is not passed to the the
818  // actual iterator. Instead, if true, it signifies that when creating
819  // the iterator, all materializable subqueries in “condition” should be
820  // materialized (with any in2exists condition removed first). In the
821  // very rare case that there are two or more such subqueries, this is
822  // an all-or-nothing decision, for simplicity.
823  //
824  // See FinalizeMaterializedSubqueries().
827  struct {
828  AccessPath *child;
831 
832  // If filesort is nullptr: A new filesort will be created at the
833  // end of optimization, using this order and flags. Otherwise: Ignored.
837  bool use_limit;
838  } sort;
839  struct {
840  AccessPath *child;
841  bool rollup;
843  struct {
846  TABLE *table;
850  struct {
851  AccessPath *child;
856  // Only used when the LIMIT is on a UNION with SQL_CALC_FOUND_ROWS.
857  // See Query_expression::send_records.
860  struct {
861  AccessPath *child;
864  TABLE *table;
866  int ref_slice;
868  struct {
869  // NOTE: The only legal access paths within table_path are
870  // TABLE_SCAN, REF, REF_OR_NULL, EQ_REF, ALTERNATIVE and
871  // CONST_TABLE (the latter is somewhat nonsensical).
873 
874  // Large, and has nontrivial destructors, so split out
875  // into its own allocation.
878  struct {
881  Item *condition;
883  struct {
886  struct {
887  AccessPath *child;
891  int ref_slice;
894  struct {
895  AccessPath *child;
899  struct {
900  AccessPath *child;
904  struct {
905  AccessPath *child;
906  TABLE *table;
907  KEY *key;
910  struct {
912 
913  // For the ref.
914  AccessPath *child;
917  struct {
918  AccessPath *child;
919  const char *name;
921  } u;
922 };
924  "AccessPath must be trivially destructible, as it is allocated "
925  "on the MEM_ROOT and not wrapped in unique_ptr_destroy_only"
926  "(because multiple candidates during planning could point to "
927  "the same access paths, and refcounting would be expensive)");
928 static_assert(sizeof(AccessPath) <= 136,
929  "We are creating a lot of access paths in the join "
930  "optimizer, so be sure not to bloat it without noticing. "
931  "(96 bytes for the base, 40 bytes for the variant.)");
932 
933 inline void CopyBasicProperties(const AccessPath &from, AccessPath *to) {
934  to->num_output_rows = from.num_output_rows;
935  to->cost = from.cost;
936  to->init_cost = from.init_cost;
937  to->init_once_cost = from.init_once_cost;
939  to->safe_for_rowid = from.safe_for_rowid;
940  to->ordering_state = from.ordering_state;
941 }
942 
943 // Trivial factory functions for all of the types of access paths above.
944 
946  bool count_examined_rows) {
947  AccessPath *path = new (thd->mem_root) AccessPath;
949  path->count_examined_rows = count_examined_rows;
950  path->table_scan().table = table;
951  return path;
952 }
953 
954 inline AccessPath *NewIndexScanAccessPath(THD *thd, TABLE *table, int idx,
955  bool use_order, bool reverse,
956  bool count_examined_rows) {
957  AccessPath *path = new (thd->mem_root) AccessPath;
959  path->count_examined_rows = count_examined_rows;
960  path->index_scan().table = table;
961  path->index_scan().idx = idx;
962  path->index_scan().use_order = use_order;
963  path->index_scan().reverse = reverse;
964  return path;
965 }
966 
968  bool use_order, bool reverse,
969  bool count_examined_rows) {
970  AccessPath *path = new (thd->mem_root) AccessPath;
971  path->type = AccessPath::REF;
972  path->count_examined_rows = count_examined_rows;
973  path->ref().table = table;
974  path->ref().ref = ref;
975  path->ref().use_order = use_order;
976  path->ref().reverse = reverse;
977  return path;
978 }
979 
981  TABLE_REF *ref, bool use_order,
982  bool count_examined_rows) {
983  AccessPath *path = new (thd->mem_root) AccessPath;
985  path->count_examined_rows = count_examined_rows;
986  path->ref_or_null().table = table;
987  path->ref_or_null().ref = ref;
988  path->ref_or_null().use_order = use_order;
989  return path;
990 }
991 
993  bool use_order,
994  bool count_examined_rows) {
995  AccessPath *path = new (thd->mem_root) AccessPath;
996  path->type = AccessPath::EQ_REF;
997  path->count_examined_rows = count_examined_rows;
998  path->eq_ref().table = table;
999  path->eq_ref().ref = ref;
1000  path->eq_ref().use_order = use_order;
1001  return path;
1002 }
1003 
1005  TABLE_REF *ref, bool use_order,
1006  bool is_unique,
1007  bool count_examined_rows) {
1008  AccessPath *path = new (thd->mem_root) AccessPath;
1010  path->count_examined_rows = count_examined_rows;
1011  path->pushed_join_ref().table = table;
1012  path->pushed_join_ref().ref = ref;
1013  path->pushed_join_ref().use_order = use_order;
1014  path->pushed_join_ref().is_unique = is_unique;
1015  return path;
1016 }
1017 
1019  TABLE_REF *ref,
1020  Item_func_match *ft_func,
1021  bool use_order, bool use_limit,
1022  bool count_examined_rows) {
1023  AccessPath *path = new (thd->mem_root) AccessPath;
1025  path->count_examined_rows = count_examined_rows;
1026  path->full_text_search().table = table;
1027  path->full_text_search().ref = ref;
1028  path->full_text_search().use_order = use_order;
1029  path->full_text_search().use_limit = use_limit;
1030  path->full_text_search().ft_func = ft_func;
1031  return path;
1032 }
1033 
1035  TABLE_REF *ref,
1036  bool count_examined_rows) {
1037  AccessPath *path = new (thd->mem_root) AccessPath;
1038  path->type = AccessPath::CONST_TABLE;
1039  path->count_examined_rows = count_examined_rows;
1040  path->num_output_rows = 1.0;
1041  path->cost = 0.0;
1042  path->init_cost = 0.0;
1043  path->init_once_cost = 0.0;
1044  path->const_table().table = table;
1045  path->const_table().ref = ref;
1046  return path;
1047 }
1048 
1050  int mrr_flags) {
1051  AccessPath *path = new (thd->mem_root) AccessPath;
1052  path->type = AccessPath::MRR;
1053  path->mrr().table = table;
1054  path->mrr().ref = ref;
1055  path->mrr().mrr_flags = mrr_flags;
1056 
1057  // This will be filled in when the BKA iterator is created.
1058  path->mrr().bka_path = nullptr;
1059 
1060  return path;
1061 }
1062 
1064  bool count_examined_rows) {
1065  AccessPath *path = new (thd->mem_root) AccessPath;
1066  path->type = AccessPath::FOLLOW_TAIL;
1067  path->count_examined_rows = count_examined_rows;
1068  path->follow_tail().table = table;
1069  return path;
1070 }
1071 
1074  bool count_examined_rows) {
1075  AccessPath *path = new (thd->mem_root) AccessPath;
1077  path->count_examined_rows = count_examined_rows;
1078  path->index_range_scan().table = table;
1079  path->index_range_scan().quick = quick;
1080  return path;
1081 }
1082 
1084  THD *thd, TABLE *table, QEP_TAB *qep_tab, bool count_examined_rows) {
1085  AccessPath *path = new (thd->mem_root) AccessPath;
1087  path->count_examined_rows = count_examined_rows;
1088  path->dynamic_index_range_scan().table = table;
1089  path->dynamic_index_range_scan().qep_tab = qep_tab;
1090  return path;
1091 }
1092 
1094  THD *thd, TABLE *table, Table_function *table_function,
1095  AccessPath *table_path) {
1096  AccessPath *path = new (thd->mem_root) AccessPath;
1098  path->materialized_table_function().table = table;
1099  path->materialized_table_function().table_function = table_function;
1100  path->materialized_table_function().table_path = table_path;
1101  return path;
1102 }
1103 
1105  AccessPath *path = new (thd->mem_root) AccessPath;
1107  return path;
1108 }
1109 
1111  AccessPath *path = new (thd->mem_root) AccessPath;
1113  // The iterator keeps track of which row it is at in examined_rows,
1114  // so we always need to give it the pointer.
1115  path->count_examined_rows = true;
1116  return path;
1117 }
1118 
1120  THD *thd, AccessPath *outer, AccessPath *inner, const TABLE *table,
1121  KEY *key, size_t key_len) {
1122  AccessPath *path = new (thd->mem_root) AccessPath;
1124  path->nested_loop_semijoin_with_duplicate_removal().outer = outer;
1125  path->nested_loop_semijoin_with_duplicate_removal().inner = inner;
1126  path->nested_loop_semijoin_with_duplicate_removal().table = table;
1127  path->nested_loop_semijoin_with_duplicate_removal().key = key;
1128  path->nested_loop_semijoin_with_duplicate_removal().key_len = key_len;
1129  return path;
1130 }
1131 
1133  Item *condition) {
1134  AccessPath *path = new (thd->mem_root) AccessPath;
1135  path->type = AccessPath::FILTER;
1136  path->filter().child = child;
1137  path->filter().condition = condition;
1138  path->filter().materialize_subqueries = false;
1139  return path;
1140 }
1141 
1142 // Not inline, because it needs access to filesort internals
1143 // (which are forward-declared in this file).
1145  bool count_examined_rows);
1146 
1148  bool rollup) {
1149  AccessPath *path = new (thd->mem_root) AccessPath;
1150  path->type = AccessPath::AGGREGATE;
1151  path->aggregate().child = child;
1152  path->aggregate().rollup = rollup;
1153  return path;
1154 }
1155 
1157  THD *thd, AccessPath *subquery_path, Temp_table_param *temp_table_param,
1158  TABLE *table, AccessPath *table_path, int ref_slice) {
1159  AccessPath *path = new (thd->mem_root) AccessPath;
1161  path->temptable_aggregate().subquery_path = subquery_path;
1162  path->temptable_aggregate().temp_table_param = temp_table_param;
1163  path->temptable_aggregate().table = table;
1164  path->temptable_aggregate().table_path = table_path;
1165  path->temptable_aggregate().ref_slice = ref_slice;
1166  return path;
1167 }
1168 
1170  ha_rows limit, ha_rows offset,
1171  bool count_all_rows,
1172  bool reject_multiple_rows,
1173  ha_rows *send_records_override) {
1174  AccessPath *path = new (thd->mem_root) AccessPath;
1176  path->limit_offset().child = child;
1177  path->limit_offset().limit = limit;
1178  path->limit_offset().offset = offset;
1179  path->limit_offset().count_all_rows = count_all_rows;
1180  path->limit_offset().reject_multiple_rows = reject_multiple_rows;
1181  path->limit_offset().send_records_override = send_records_override;
1182 
1183  if (child->num_output_rows >= 0.0) {
1184  path->num_output_rows =
1185  offset >= child->num_output_rows
1186  ? 0.0
1187  : (std::min<double>(child->num_output_rows, limit) - offset);
1188  }
1189 
1190  if (child->init_cost < 0.0) {
1191  // We have nothing better, since we don't know how much is startup cost.
1192  path->cost = child->cost;
1193  } else if (child->num_output_rows < 1e-6) {
1194  path->cost = path->init_cost = child->init_cost;
1195  } else {
1196  const double fraction_start_read =
1197  std::min(1.0, double(offset) / child->num_output_rows);
1198  const double fraction_full_read =
1199  std::min(1.0, double(limit) / child->num_output_rows);
1200  path->cost = child->init_cost +
1201  fraction_full_read * (child->cost - child->init_cost);
1202  path->init_cost = child->init_cost +
1203  fraction_start_read * (child->cost - child->init_cost);
1204  }
1205  path->init_once_cost = child->init_once_cost;
1206  path->ordering_state = child->ordering_state;
1207 
1208  return path;
1209 }
1210 
1212  bool count_examined_rows) {
1213  AccessPath *path = new (thd->mem_root) AccessPath;
1215  path->count_examined_rows = count_examined_rows;
1216  path->num_output_rows = 1.0;
1217  path->cost = 0.0;
1218  path->init_cost = 0.0;
1219  path->init_once_cost = 0.0;
1220  return path;
1221 }
1222 
1224  const char *cause) {
1225  AccessPath *path = new (thd->mem_root) AccessPath;
1226  path->type = AccessPath::ZERO_ROWS;
1227  path->zero_rows().child = child;
1228  path->zero_rows().cause = cause;
1229  path->num_output_rows = 0.0;
1230  path->cost = 0.0;
1231  path->init_cost = 0.0;
1232  path->init_once_cost = 0.0;
1233  return path;
1234 }
1235 
1236 inline AccessPath *NewZeroRowsAccessPath(THD *thd, const char *cause) {
1237  return NewZeroRowsAccessPath(thd, /*child=*/nullptr, cause);
1238 }
1239 
1241  const char *cause) {
1242  AccessPath *path = new (thd->mem_root) AccessPath;
1244  path->zero_rows_aggregated().cause = cause;
1245  path->num_output_rows = 1.0;
1246  path->cost = 0.0;
1247  path->init_cost = 0.0;
1248  return path;
1249 }
1250 
1252  JOIN *join,
1253  Temp_table_param *temp_table_param,
1254  TABLE *table, int ref_slice) {
1255  AccessPath *path = new (thd->mem_root) AccessPath;
1256  path->type = AccessPath::STREAM;
1257  path->stream().child = child;
1258  path->stream().join = join;
1259  path->stream().temp_table_param = temp_table_param;
1260  path->stream().table = table;
1261  path->stream().ref_slice = ref_slice;
1262  // Will be set later if we get a weedout access path as parent.
1263  path->stream().provide_rowid = false;
1264  return path;
1265 }
1266 
1269  JOIN *join, bool copy_items,
1270  Temp_table_param *temp_table_param) {
1271  assert(path != nullptr);
1273  MaterializePathParameters::QueryBlock &query_block = array[0];
1274  query_block.subquery_path = path;
1275  query_block.select_number = select_number;
1276  query_block.join = join;
1277  query_block.disable_deduplication_by_hash_field = false;
1278  query_block.copy_items = copy_items;
1279  query_block.temp_table_param = temp_table_param;
1280  return array;
1281 }
1282 
1284  THD *thd,
1286  Mem_root_array<const AccessPath *> *invalidators, TABLE *table,
1287  AccessPath *table_path, Common_table_expr *cte, Query_expression *unit,
1288  int ref_slice, bool rematerialize, ha_rows limit_rows,
1289  bool reject_multiple_rows) {
1290  MaterializePathParameters *param =
1292  param->query_blocks = std::move(query_blocks);
1293  if (rematerialize) {
1294  // There's no point in adding invalidators if we're rematerializing
1295  // every time anyway.
1296  param->invalidators = nullptr;
1297  } else {
1298  param->invalidators = invalidators;
1299  }
1300  param->table = table;
1301  param->cte = cte;
1302  param->unit = unit;
1303  param->ref_slice = ref_slice;
1304  param->rematerialize = rematerialize;
1305  param->limit_rows = limit_rows;
1306  param->reject_multiple_rows = reject_multiple_rows;
1307 
1308 #ifndef NDEBUG
1309  for (MaterializePathParameters::QueryBlock &query_block :
1310  param->query_blocks) {
1311  assert(query_block.subquery_path != nullptr);
1312  }
1313 #endif
1314 
1315  AccessPath *path = new (thd->mem_root) AccessPath;
1316  path->type = AccessPath::MATERIALIZE;
1317  path->materialize().table_path = table_path;
1318  path->materialize().param = param;
1319  if (rematerialize) {
1320  path->safe_for_rowid = AccessPath::SAFE_IF_SCANNED_ONCE;
1321  } else {
1322  // The default; this is just to be explicit in the code.
1323  path->safe_for_rowid = AccessPath::SAFE;
1324  }
1325  return path;
1326 }
1327 
1329  THD *thd, AccessPath *table_path, TABLE_LIST *table_list, Item *condition) {
1330  AccessPath *path = new (thd->mem_root) AccessPath;
1332  path->materialize_information_schema_table().table_path = table_path;
1333  path->materialize_information_schema_table().table_list = table_list;
1334  path->materialize_information_schema_table().condition = condition;
1335  return path;
1336 }
1337 
1338 // The Mem_root_array must be allocated on a MEM_ROOT that lives at least for as
1339 // long as the access path.
1341  THD *thd, Mem_root_array<AppendPathParameters> *children) {
1342  AccessPath *path = new (thd->mem_root) AccessPath;
1343  path->type = AccessPath::APPEND;
1344  path->append().children = children;
1345  path->cost = 0.0;
1346  path->init_cost = 0.0;
1347  path->init_once_cost = 0.0;
1348  for (const AppendPathParameters &child : *children) {
1349  path->cost += child.path->cost;
1350  path->init_cost += child.path->init_cost;
1351  path->init_once_cost += child.path->init_once_cost;
1352  }
1353  return path;
1354 }
1355 
1357  Temp_table_param *temp_table_param,
1358  int ref_slice, bool needs_buffering) {
1359  AccessPath *path = new (thd->mem_root) AccessPath;
1360  path->type = AccessPath::WINDOW;
1361  path->window().child = child;
1362  path->window().temp_table_param = temp_table_param;
1363  path->window().ref_slice = ref_slice;
1364  path->window().needs_buffering = needs_buffering;
1365  return path;
1366 }
1367 
1369  SJ_TMP_TABLE *weedout_table) {
1370  AccessPath *path = new (thd->mem_root) AccessPath;
1371  path->type = AccessPath::WEEDOUT;
1372  path->weedout().child = child;
1373  path->weedout().weedout_table = weedout_table;
1374  path->weedout().tables_to_get_rowid_for =
1375  0; // Must be handled by the caller.
1376  return path;
1377 }
1378 
1380  Item **group_items,
1381  int group_items_size) {
1382  AccessPath *path = new (thd->mem_root) AccessPath;
1384  path->remove_duplicates().child = child;
1385  path->remove_duplicates().group_items = group_items;
1386  path->remove_duplicates().group_items_size = group_items_size;
1387  return path;
1388 }
1389 
1391  THD *thd, AccessPath *child, TABLE *table, KEY *key,
1392  unsigned loosescan_key_len) {
1393  AccessPath *path = new (thd->mem_root) AccessPath;
1395  path->remove_duplicates_on_index().child = child;
1396  path->remove_duplicates_on_index().table = table;
1397  path->remove_duplicates_on_index().key = key;
1398  path->remove_duplicates_on_index().loosescan_key_len = loosescan_key_len;
1399  return path;
1400 }
1401 
1403  AccessPath *table_scan_path,
1404  TABLE_REF *used_ref) {
1405  AccessPath *path = new (thd->mem_root) AccessPath;
1406  path->type = AccessPath::ALTERNATIVE;
1407  path->alternative().table_scan_path = table_scan_path;
1408  path->alternative().child = child;
1409  path->alternative().used_ref = used_ref;
1410  return path;
1411 }
1412 
1414  const char *name) {
1415  AccessPath *path = new (thd->mem_root) AccessPath;
1417  path->cache_invalidator().child = child;
1418  path->cache_invalidator().name = name;
1419  return path;
1420 }
1421 
1423 
1424 /**
1425  If the path is a FILTER path marked that subqueries are to be materialized,
1426  do so. If not, do nothing.
1427 
1428  It is important that this is not called until the entire plan is ready;
1429  not just when planning a single query block. The reason is that a query
1430  block A with materializable subqueries may itself be part of a materializable
1431  subquery B, so if one calls this when planning A, the subqueries in A will
1432  irrevocably be materialized, even if that is not the optimal plan given B.
1433  Thus, this is done when creating iterators.
1434  */
1436 
1438  THD *thd, AccessPath *path, JOIN *join, bool eligible_for_batch_mode);
1439 
1440 void SetCostOnTableAccessPath(const Cost_model_server &cost_model,
1441  const POSITION *pos, bool is_after_filter,
1442  AccessPath *path);
1443 
1444 /**
1445  Returns a map of all tables read when `path` or any of its children are
1446  exectued. Only iterators that are part of the same query block as `path`
1447  are considered.
1448 
1449  If a table is read that doesn't have a map, specifically the temporary
1450  tables made as part of materialization within the same query block,
1451  RAND_TABLE_BIT will be set as a convention and none of that access path's
1452  children will be included in the map. In this case, the caller will need to
1453  manually go in and find said access path, to ask it for its TABLE object.
1454 
1455  If include_pruned_tables = true, tables that are hidden under a ZERO_ROWS
1456  access path (ie., pruned away due to impossible join conditions) will be
1457  included in the map. This is normally what you want, as those tables need to
1458  be included whenever you store NULL flags and the likes, but if you don't
1459  want them (perhaps to specifically check for conditions referring to pruned
1460  tables), you can set it to false.
1461  */
1462 table_map GetUsedTableMap(const AccessPath *path, bool include_pruned_tables);
1463 
1464 /**
1465  Find the list of all tables used by this root, stopping at materializations.
1466  Used for knowing which tables to sort.
1467  */
1469 
1470 /**
1471  For each access path in the (sub)tree rooted at “path”, expand any use of
1472  “filter_predicates” into newly-inserted FILTER access paths, using the given
1473  predicate list. This is used after finding an optimal set of access paths,
1474  to normalize the tree so that the remaining consumers do not need to worry
1475  about filter_predicates and cost_before_filter.
1476 
1477  “join” is the join that “path” is part of.
1478  */
1479 void ExpandFilterAccessPaths(THD *thd, AccessPath *path, const JOIN *join,
1480  const Mem_root_array<Predicate> &predicates,
1481  unsigned num_where_predicates);
1482 
1483 /// Like ExpandFilterAccessPaths(), but expands only the single access path
1484 /// at “path”.
1486  const Mem_root_array<Predicate> &predicates,
1487  unsigned num_where_predicates);
1488 
1489 #endif // SQL_JOIN_OPTIMIZER_ACCESS_PATH_H
AccessPath * NewWindowAccessPath(THD *thd, AccessPath *child, Temp_table_param *temp_table_param, int ref_slice, bool needs_buffering)
Definition: access_path.h:1356
AccessPath * NewStreamingAccessPath(THD *thd, AccessPath *child, JOIN *join, Temp_table_param *temp_table_param, TABLE *table, int ref_slice)
Definition: access_path.h:1251
bool FinalizeMaterializedSubqueries(THD *thd, JOIN *join, AccessPath *path)
If the path is a FILTER path marked that subqueries are to be materialized, do so.
Definition: access_path.cc:180
AccessPath * NewFollowTailAccessPath(THD *thd, TABLE *table, bool count_examined_rows)
Definition: access_path.h:1063
void CopyBasicProperties(const AccessPath &from, AccessPath *to)
Definition: access_path.h:933
AccessPath * NewTableValueConstructorAccessPath(THD *thd)
Definition: access_path.h:1110
AccessPath * NewEQRefAccessPath(THD *thd, TABLE *table, TABLE_REF *ref, bool use_order, bool count_examined_rows)
Definition: access_path.h:992
AccessPath * NewFilterAccessPath(THD *thd, AccessPath *child, Item *condition)
Definition: access_path.h:1132
AccessPath * NewTableScanAccessPath(THD *thd, TABLE *table, bool count_examined_rows)
Definition: access_path.h:945
AccessPath * NewMaterializeAccessPath(THD *thd, Mem_root_array< MaterializePathParameters::QueryBlock > query_blocks, Mem_root_array< const AccessPath * > *invalidators, TABLE *table, AccessPath *table_path, Common_table_expr *cte, Query_expression *unit, int ref_slice, bool rematerialize, ha_rows limit_rows, bool reject_multiple_rows)
Definition: access_path.h:1283
AccessPath * NewIndexRangeScanAccessPath(THD *thd, TABLE *table, QUICK_SELECT_I *quick, bool count_examined_rows)
Definition: access_path.h:1072
AccessPath * NewInvalidatorAccessPath(THD *thd, AccessPath *child, const char *name)
Definition: access_path.h:1413
AccessPath * NewAppendAccessPath(THD *thd, Mem_root_array< AppendPathParameters > *children)
Definition: access_path.h:1340
Mem_root_array< TABLE * > CollectTables(THD *thd, AccessPath *root_path)
Find the list of all tables used by this root, stopping at materializations.
Definition: access_path.cc:140
AccessPath * NewZeroRowsAggregatedAccessPath(THD *thd, const char *cause)
Definition: access_path.h:1240
AccessPath * NewDynamicIndexRangeScanAccessPath(THD *thd, TABLE *table, QEP_TAB *qep_tab, bool count_examined_rows)
Definition: access_path.h:1083
table_map GetUsedTableMap(const AccessPath *path, bool include_pruned_tables)
Returns a map of all tables read when path or any of its children are exectued.
Definition: access_path.cc:109
AccessPath * NewSortAccessPath(THD *thd, AccessPath *child, Filesort *filesort, bool count_examined_rows)
Definition: access_path.cc:46
AccessPath * NewLimitOffsetAccessPath(THD *thd, AccessPath *child, ha_rows limit, ha_rows offset, bool count_all_rows, bool reject_multiple_rows, ha_rows *send_records_override)
Definition: access_path.h:1169
AccessPath * NewAggregateAccessPath(THD *thd, AccessPath *child, bool rollup)
Definition: access_path.h:1147
AccessPath * NewUnqualifiedCountAccessPath(THD *thd)
Definition: access_path.h:1104
Mem_root_array< MaterializePathParameters::QueryBlock > SingleMaterializeQueryBlock(THD *thd, AccessPath *path, int select_number, JOIN *join, bool copy_items, Temp_table_param *temp_table_param)
Definition: access_path.h:1268
AccessPath * NewConstTableAccessPath(THD *thd, TABLE *table, TABLE_REF *ref, bool count_examined_rows)
Definition: access_path.h:1034
unique_ptr_destroy_only< RowIterator > CreateIteratorFromAccessPath(THD *thd, AccessPath *path, JOIN *join, bool eligible_for_batch_mode)
Definition: access_path.cc:205
AccessPath * NewMRRAccessPath(THD *thd, TABLE *table, TABLE_REF *ref, int mrr_flags)
Definition: access_path.h:1049
AccessPath * NewMaterializeInformationSchemaTableAccessPath(THD *thd, AccessPath *table_path, TABLE_LIST *table_list, Item *condition)
Definition: access_path.h:1328
AccessPath * NewMaterializedTableFunctionAccessPath(THD *thd, TABLE *table, Table_function *table_function, AccessPath *table_path)
Definition: access_path.h:1093
AccessPath * NewIndexScanAccessPath(THD *thd, TABLE *table, int idx, bool use_order, bool reverse, bool count_examined_rows)
Definition: access_path.h:954
AccessPath * NewTemptableAggregateAccessPath(THD *thd, AccessPath *subquery_path, Temp_table_param *temp_table_param, TABLE *table, AccessPath *table_path, int ref_slice)
Definition: access_path.h:1156
AccessPath * NewNestedLoopSemiJoinWithDuplicateRemovalAccessPath(THD *thd, AccessPath *outer, AccessPath *inner, const TABLE *table, KEY *key, size_t key_len)
Definition: access_path.h:1119
AccessPath * NewWeedoutAccessPath(THD *thd, AccessPath *child, SJ_TMP_TABLE *weedout_table)
Definition: access_path.h:1368
AccessPath * NewFakeSingleRowAccessPath(THD *thd, bool count_examined_rows)
Definition: access_path.h:1211
void ExpandFilterAccessPaths(THD *thd, AccessPath *path, const JOIN *join, const Mem_root_array< Predicate > &predicates, unsigned num_where_predicates)
For each access path in the (sub)tree rooted at “path”, expand any use of “filter_predicates” into ne...
Definition: access_path.cc:897
AccessPath * NewAlternativeAccessPath(THD *thd, AccessPath *child, AccessPath *table_scan_path, TABLE_REF *used_ref)
Definition: access_path.h:1402
void FindTablesToGetRowidFor(AccessPath *path)
Definition: access_path.cc:772
void ExpandSingleFilterAccessPath(THD *thd, AccessPath *path, const Mem_root_array< Predicate > &predicates, unsigned num_where_predicates)
Like ExpandFilterAccessPaths(), but expands only the single access path at “path”.
Definition: access_path.cc:860
AccessPath * NewRefAccessPath(THD *thd, TABLE *table, TABLE_REF *ref, bool use_order, bool reverse, bool count_examined_rows)
Definition: access_path.h:967
AccessPath * NewFullTextSearchAccessPath(THD *thd, TABLE *table, TABLE_REF *ref, Item_func_match *ft_func, bool use_order, bool use_limit, bool count_examined_rows)
Definition: access_path.h:1018
AccessPath * NewPushedJoinRefAccessPath(THD *thd, TABLE *table, TABLE_REF *ref, bool use_order, bool is_unique, bool count_examined_rows)
Definition: access_path.h:1004
AccessPath * NewZeroRowsAccessPath(THD *thd, AccessPath *child, const char *cause)
Definition: access_path.h:1223
AccessPath * NewRefOrNullAccessPath(THD *thd, TABLE *table, TABLE_REF *ref, bool use_order, bool count_examined_rows)
Definition: access_path.h:980
AccessPath * NewRemoveDuplicatesOnIndexAccessPath(THD *thd, AccessPath *child, TABLE *table, KEY *key, unsigned loosescan_key_len)
Definition: access_path.h:1390
AccessPath * NewRemoveDuplicatesAccessPath(THD *thd, AccessPath *child, Item **group_items, int group_items_size)
Definition: access_path.h:1379
After parsing, a Common Table Expression is accessed through a TABLE_LIST.
Definition: table.h:4237
API for getting cost estimates for server operations that are not directly related to a table object.
Definition: opt_costmodel.h:41
Sorting related info.
Definition: filesort.h:51
Definition: item_func.h:3444
Base class that is used to represent any kind of expression in a relational query.
Definition: item.h:802
Definition: sql_optimizer.h:125
Definition: key.h:112
Definition: overflow_bitset.h:73
Definition: sql_executor.h:256
Definition: range_optimizer.h:221
MEM_ROOT * mem_root
Definition: sql_class.h:243
This class represents a query expression (one query block or several query blocks combined with UNION...
Definition: sql_lex.h:629
A context for reading through a single table using a chosen access method: index read,...
Definition: row_iterator.h:60
Definition: sql_executor.h:101
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_class.h:821
Class representing a table function.
Definition: table_function.h:52
Object containing parameters used when creating and using temporary tables.
Definition: temp_table_param.h:98
Represents the (explicit) window of a SQL 2003 section 7.11 <window clause>, or the implicit (inlined...
Definition: window.h:94
char * pos
Definition: do_ctype.cc:76
bool filesort(THD *thd, Filesort *filesort, RowIterator *source_iterator, table_map tables_to_get_rowid_for, ha_rows num_rows_estimate, Filesort_info *fs_info, Sort_result *sort_result, ha_rows *found_rows)
Sort a table.
Definition: filesort.cc:366
void SetCostOnTableAccessPath(const Cost_model_server &cost_model, const POSITION *pos, bool is_after_filter, AccessPath *path)
Definition: sql_executor.cc:1706
std::bitset< kMaxSupportedFDs > FunctionalDependencySet
Definition: interesting_orders_defs.h:62
JoinType
Definition: join_type.h:27
std::unique_ptr< T, Destroy_only< T > > unique_ptr_destroy_only
std::unique_ptr, but only destroying.
Definition: my_alloc.h:464
my_off_t ha_rows
Definition: my_base.h:1138
uint64_t table_map
Definition: my_table_map.h:29
static bool quick
Definition: mysql.cc:154
static char * path
Definition: mysqldump.cc:130
PT & ref(PT *tp)
Definition: tablespace_impl.cc:358
uint64_t NodeMap
Since our graphs can never have more than 61 tables, node sets and edge lists are implemented using 6...
Definition: node_map.h:39
RangeReverse< Range > reverse(Range &x)
Iterate over a range in reverse.
Definition: utilities.h:135
std::string join(Container cont, const std::string &delim)
join elements of an container into a string separated by a delimiter.
Definition: string.h:144
OverflowBitset is a fixed-size (once allocated) bitmap that is optimized for the common case of few e...
const string value("\"Value\"")
required string key
Definition: replication_asynchronous_connection_failover.proto:59
case opt name
Definition: sslopt-case.h:32
Access paths are a query planning structure that correspond 1:1 to iterators, in that an access path ...
Definition: access_path.h:176
const auto & cache_invalidator() const
Definition: access_path.h:684
bool count_all_rows
Definition: access_path.h:854
AccessPath * bka_path
Definition: access_path.h:742
const OverflowBitset & applied_sargable_join_predicates() const
Definition: access_path.h:337
double cost_before_filter
Definition: access_path.h:299
hypergraph::NodeMap parameter_tables
If nonzero, a bitmap of other tables whose joined-in rows must already be loaded when rows from this ...
Definition: access_path.h:380
struct AccessPath::@48::@68 bka_join
TABLE * temp_table
Definition: access_path.h:889
Item ** group_items
Definition: access_path.h:901
const auto & append() const
Definition: access_path.h:636
bool rollup
Definition: access_path.h:841
double num_output_rows
Expected number of output rows, -1.0 for unknown.
Definition: access_path.h:271
auto & mrr()
Definition: access_path.h:456
auto & eq_ref()
Definition: access_path.h:424
const auto & zero_rows_aggregated() const
Definition: access_path.h:532
struct AccessPath::@48::@49 table_scan
auto & dynamic_index_range_scan()
Definition: access_path.h:480
Item * condition
Definition: access_path.h:815
const auto & weedout() const
Definition: access_path.h:652
const auto & materialize_information_schema_table() const
Definition: access_path.h:628
enum AccessPath::Type type
AccessPath * outer
Definition: access_path.h:786
const auto & eq_ref() const
Definition: access_path.h:428
const auto & full_text_search() const
Definition: access_path.h:444
struct AccessPath::@48::@55 full_text_search
struct AccessPath::@48::@85 cache_invalidator
const auto & filter() const
Definition: access_path.h:572
bool rewrite_semi_to_inner
Definition: access_path.h:790
const auto & window() const
Definition: access_path.h:644
const auto & alternative() const
Definition: access_path.h:676
const auto & index_scan() const
Definition: access_path.h:404
int group_items_size
Definition: access_path.h:902
bool use_order
Definition: access_path.h:703
const auto & pushed_join_ref() const
Definition: access_path.h:436
bool pfs_batch_mode
Definition: access_path.h:804
struct AccessPath::@48::@58 follow_tail
struct AccessPath::@48::@67 hash_join
struct AccessPath::@48::@74 temptable_aggregate
auto & table_value_constructor()
Definition: access_path.h:504
bool materialize_subqueries
Definition: access_path.h:825
AccessPath * child
Definition: access_path.h:774
bool allow_spill_to_disk
Definition: access_path.h:788
struct AccessPath::@48::@63 table_value_constructor
auto & pushed_join_ref()
Definition: access_path.h:432
const auto & remove_duplicates_on_index() const
Definition: access_path.h:668
const auto & unqualified_count() const
Definition: access_path.h:500
auto & materialized_table_function()
Definition: access_path.h:488
bool reject_multiple_rows
Definition: access_path.h:855
struct AccessPath::@48::@81 weedout
auto & index_range_scan()
Definition: access_path.h:472
auto & filter()
Definition: access_path.h:568
const char * name
Definition: access_path.h:919
bool use_limit
Definition: access_path.h:732
Window * window
Definition: access_path.h:888
table_map tables_to_get_rowid_for
Definition: access_path.h:791
SJ_TMP_TABLE * weedout_table
Definition: access_path.h:896
struct AccessPath::@48::@72 sort
struct AccessPath::@48::@61 materialized_table_function
const auto & table_scan() const
Definition: access_path.h:396
const auto & bka_join() const
Definition: access_path.h:548
bool keep_current_rowid
Definition: access_path.h:744
const auto & sort() const
Definition: access_path.h:580
struct AccessPath::@48::@54 pushed_join_ref
auto & alternative()
Definition: access_path.h:672
const auto & const_table() const
Definition: access_path.h:452
union AccessPath::@48 u
auto & fake_single_row()
Definition: access_path.h:512
float rec_per_key
Definition: access_path.h:797
Safety safe_for_rowid
Whether it is safe to get row IDs (for sorting) from this access path.
Definition: access_path.h:256
const auto & dynamic_index_range_scan() const
Definition: access_path.h:484
JOIN * join
Definition: access_path.h:862
auto & bka_join()
Definition: access_path.h:544
auto & temptable_aggregate()
Definition: access_path.h:592
struct AccessPath::@48::@69 nested_loop_join
RowIterator * iterator
If an iterator has been instantiated for this access path, points to the iterator.
Definition: access_path.h:268
const auto & ref() const
Definition: access_path.h:412
struct AccessPath::@48::@50 index_scan
const auto & follow_tail() const
Definition: access_path.h:468
double init_cost
Expected cost to initialize this access path; ie., cost to read k out of N rows would be init_cost + ...
Definition: access_path.h:283
auto & materialize()
Definition: access_path.h:616
const auto & hash_join() const
Definition: access_path.h:540
auto & follow_tail()
Definition: access_path.h:464
struct AccessPath::@48::@62 unqualified_count
void * secondary_engine_data
Auxiliary data used by a secondary storage engine while processing the access path during optimizatio...
Definition: access_path.h:389
const auto & nested_loop_join() const
Definition: access_path.h:556
const auto & materialize() const
Definition: access_path.h:620
auto & hash_join()
Definition: access_path.h:536
bool remove_duplicates
Definition: access_path.h:835
KEY * key
Definition: access_path.h:809
auto & remove_duplicates()
Definition: access_path.h:656
auto & unqualified_count()
Definition: access_path.h:496
auto & cache_invalidator()
Definition: access_path.h:680
const auto & temptable_aggregate() const
Definition: access_path.h:596
struct AccessPath::@48::@64 fake_single_row
size_t key_len
Definition: access_path.h:810
auto & remove_duplicates_on_index()
Definition: access_path.h:664
ha_rows offset
Definition: access_path.h:853
auto & aggregate()
Definition: access_path.h:584
int idx
Definition: access_path.h:702
const auto & index_range_scan() const
Definition: access_path.h:476
QUICK_SELECT_I * quick
Definition: access_path.h:751
struct AccessPath::@48::@71 filter
ORDER * order
Definition: access_path.h:834
ha_rows limit
Definition: access_path.h:852
const auto & remove_duplicates() const
Definition: access_path.h:660
const auto & aggregate() const
Definition: access_path.h:588
const JoinPredicate * join_predicate
Definition: access_path.h:787
struct AccessPath::@48::@83 remove_duplicates_on_index
int ref_slice
Definition: access_path.h:848
TABLE_LIST * table_list
Definition: access_path.h:880
OverflowBitset filter_predicates
Bitmap of WHERE predicates that we are including on this access path, referring to the “predicates” a...
Definition: access_path.h:318
AccessPath * inner
Definition: access_path.h:786
bool provide_rowid
Definition: access_path.h:865
auto & full_text_search()
Definition: access_path.h:440
struct AccessPath::@48::@73 aggregate
Item_func_match * ft_func
Definition: access_path.h:733
struct AccessPath::@48::@60 dynamic_index_range_scan
ha_rows * send_records_override
Definition: access_path.h:858
QEP_TAB * qep_tab
Definition: access_path.h:755
auto & weedout()
Definition: access_path.h:648
Table_function * table_function
Definition: access_path.h:759
bool unwrap_rollup
Definition: access_path.h:836
double init_once_cost
Of init_cost, how much of the initialization needs only to be done once per query block.
Definition: access_path.h:295
auto & zero_rows()
Definition: access_path.h:520
struct AccessPath::@48::@76 stream
Type
Definition: access_path.h:177
@ FOLLOW_TAIL
Definition: access_path.h:188
@ FILTER
Definition: access_path.h:207
@ PUSHED_JOIN_REF
Definition: access_path.h:184
@ ZERO_ROWS_AGGREGATED
Definition: access_path.h:196
@ AGGREGATE
Definition: access_path.h:209
@ BKA_JOIN
Definition: access_path.h:203
@ ZERO_ROWS
Definition: access_path.h:195
@ CONST_TABLE
Definition: access_path.h:186
@ INDEX_RANGE_SCAN
Definition: access_path.h:189
@ UNQUALIFIED_COUNT
Definition: access_path.h:198
@ EQ_REF
Definition: access_path.h:183
@ FAKE_SINGLE_ROW
Definition: access_path.h:194
@ MATERIALIZE_INFORMATION_SCHEMA_TABLE
Definition: access_path.h:214
@ WINDOW
Definition: access_path.h:216
@ REF_OR_NULL
Definition: access_path.h:182
@ MATERIALIZE
Definition: access_path.h:213
@ NESTED_LOOP_SEMIJOIN_WITH_DUPLICATE_REMOVAL
Definition: access_path.h:202
@ MRR
Definition: access_path.h:187
@ CACHE_INVALIDATOR
Definition: access_path.h:221
@ INDEX_SCAN
Definition: access_path.h:180
@ TABLE_VALUE_CONSTRUCTOR
Definition: access_path.h:193
@ WEEDOUT
Definition: access_path.h:217
@ MATERIALIZED_TABLE_FUNCTION
Definition: access_path.h:197
@ REMOVE_DUPLICATES_ON_INDEX
Definition: access_path.h:219
@ TABLE_SCAN
Definition: access_path.h:179
@ REF
Definition: access_path.h:181
@ TEMPTABLE_AGGREGATE
Definition: access_path.h:210
@ LIMIT_OFFSET
Definition: access_path.h:211
@ APPEND
Definition: access_path.h:215
@ NESTED_LOOP_JOIN
Definition: access_path.h:201
@ FULL_TEXT_SEARCH
Definition: access_path.h:185
@ ALTERNATIVE
Definition: access_path.h:220
@ STREAM
Definition: access_path.h:212
@ REMOVE_DUPLICATES
Definition: access_path.h:218
@ DYNAMIC_INDEX_RANGE_SCAN
Definition: access_path.h:190
@ SORT
Definition: access_path.h:208
@ HASH_JOIN
Definition: access_path.h:204
const TABLE * table
Definition: access_path.h:808
struct AccessPath::@48::@53 eq_ref
const auto & fake_single_row() const
Definition: access_path.h:516
auto & ref()
Definition: access_path.h:408
auto & stream()
Definition: access_path.h:608
struct AccessPath::@48::@66 zero_rows_aggregated
int mrr_flags
Definition: access_path.h:743
int ordering_state
Which ordering the rows produced by this path follow, if any (see interesting_orders....
Definition: access_path.h:262
JoinType join_type
Definition: access_path.h:795
struct AccessPath::@48::@57 mrr
MaterializePathParameters * param
Definition: access_path.h:876
struct AccessPath::@48::@84 alternative
const char * cause
Definition: access_path.h:777
auto & zero_rows_aggregated()
Definition: access_path.h:528
struct AccessPath::@48::@70 nested_loop_semijoin_with_duplicate_removal
struct AccessPath::@48::@77 materialize
const auto & stream() const
Definition: access_path.h:612
const auto & ref_or_null() const
Definition: access_path.h:420
auto & index_scan()
Definition: access_path.h:400
auto & materialize_information_schema_table()
Definition: access_path.h:624
const auto & limit_offset() const
Definition: access_path.h:604
AccessPath * subquery_path
Definition: access_path.h:844
auto & window()
Definition: access_path.h:640
Mem_root_array< AppendPathParameters > * children
Definition: access_path.h:884
TABLE_REF * ref
Definition: access_path.h:708
double cost
Expected cost to read all of this access path once; -1.0 for unknown.
Definition: access_path.h:274
OverflowBitset & subsumed_sargable_join_predicates()
Similar to applied_sargable_join_predicates, bitmap of sargable join predicates that have been applie...
Definition: access_path.h:354
const auto & nested_loop_semijoin_with_duplicate_removal() const
Definition: access_path.h:564
auto & nested_loop_join()
Definition: access_path.h:552
struct AccessPath::@48::@78 materialize_information_schema_table
auto & table_scan()
Definition: access_path.h:392
Temp_table_param * temp_table_param
Definition: access_path.h:845
bool reverse
Definition: access_path.h:704
AccessPath * table_scan_path
Definition: access_path.h:911
const auto & zero_rows() const
Definition: access_path.h:524
auto & nested_loop_semijoin_with_duplicate_removal()
Definition: access_path.h:560
bool count_examined_rows
Whether this access path counts as one that scans a base table, and thus should be counted towards ex...
Definition: access_path.h:228
unsigned loosescan_key_len
Definition: access_path.h:908
OverflowBitset & applied_sargable_join_predicates()
Bitmap of sargable join predicates that have already been applied in this access path by means of an ...
Definition: access_path.h:334
auto & limit_offset()
Definition: access_path.h:600
struct AccessPath::@48::@79 append
auto & append()
Definition: access_path.h:632
struct AccessPath::@48::@59 index_range_scan
struct AccessPath::@48::@56 const_table
OverflowBitset delayed_predicates
Bitmap of WHERE predicates that touch tables we have joined in, but that we could not apply yet (for ...
Definition: access_path.h:346
struct AccessPath::@48::@75 limit_offset
auto & sort()
Definition: access_path.h:576
AccessPath * table_path
Definition: access_path.h:760
TABLE * table
Definition: access_path.h:698
const auto & mrr() const
Definition: access_path.h:460
TABLE_REF * used_ref
Definition: access_path.h:915
auto & ref_or_null()
Definition: access_path.h:416
bool needs_buffering
Definition: access_path.h:892
auto & const_table()
Definition: access_path.h:448
bool is_unique
Definition: access_path.h:726
Safety
A general enum to describe the safety of a given operation.
Definition: access_path.h:237
@ SAFE_IF_SCANNED_ONCE
The given operation is safe if this access path is scanned once, but not if it's scanned multiple tim...
Definition: access_path.h:246
@ UNSAFE
The given operation is unsafe on this access path, no matter how many or few times it's scanned.
Definition: access_path.h:252
@ SAFE
The given operation is always safe on this access path.
Definition: access_path.h:239
unsigned mrr_length_per_rec
Definition: access_path.h:796
const auto & materialized_table_function() const
Definition: access_path.h:492
double num_output_rows_before_filter
If no filter, identical to num_output_rows, cost, respectively.
Definition: access_path.h:299
struct AccessPath::@48::@52 ref_or_null
Filesort * filesort
Definition: access_path.h:829
struct AccessPath::@48::@65 zero_rows
const OverflowBitset & subsumed_sargable_join_predicates() const
Definition: access_path.h:357
bool store_rowids
Definition: access_path.h:789
const auto & table_value_constructor() const
Definition: access_path.h:508
Definition: access_path.h:149
JOIN * join
Definition: access_path.h:151
AccessPath * path
Definition: access_path.h:150
A specification that two specific relational expressions (e.g., two tables, or a table and a join bet...
Definition: access_path.h:67
int semijoin_group_size
Definition: access_path.h:100
FunctionalDependencySet functional_dependencies
Definition: access_path.h:84
Mem_root_array< int > functional_dependencies_idx
Definition: access_path.h:89
RelationalExpression * expr
Definition: access_path.h:68
double selectivity
Definition: access_path.h:69
int ordering_idx_needed_for_semijoin_rewrite
Definition: access_path.h:94
Item ** semijoin_group
Definition: access_path.h:99
size_t estimated_bytes_per_row
Definition: access_path.h:73
Definition: materialize_path_parameters.h:41
int select_number
Definition: materialize_path_parameters.h:43
bool copy_items
Definition: materialize_path_parameters.h:46
Temp_table_param * temp_table_param
Definition: materialize_path_parameters.h:47
AccessPath * subquery_path
Definition: materialize_path_parameters.h:42
bool disable_deduplication_by_hash_field
Definition: materialize_path_parameters.h:45
JOIN * join
Definition: materialize_path_parameters.h:44
Definition: materialize_path_parameters.h:39
bool rematerialize
Definition: materialize_path_parameters.h:56
Common_table_expr * cte
Definition: materialize_path_parameters.h:53
bool reject_multiple_rows
Definition: materialize_path_parameters.h:58
ha_rows limit_rows
Definition: materialize_path_parameters.h:57
Mem_root_array< QueryBlock > query_blocks
Definition: materialize_path_parameters.h:50
TABLE * table
Definition: materialize_path_parameters.h:52
int ref_slice
Definition: materialize_path_parameters.h:55
Query_expression * unit
Definition: materialize_path_parameters.h:54
Mem_root_array< const AccessPath * > * invalidators
Definition: materialize_path_parameters.h:51
Definition: table.h:279
A position of table within a join order.
Definition: sql_select.h:350
A filter of some sort that is not a join condition (those are stored in JoinPredicate objects).
Definition: access_path.h:108
hypergraph::NodeMap total_eligibility_set
Definition: access_path.h:121
bool was_join_condition
Definition: access_path.h:134
Mem_root_array< int > functional_dependencies_idx
Definition: access_path.h:146
FunctionalDependencySet functional_dependencies
Definition: access_path.h:145
int source_multiple_equality_idx
Definition: access_path.h:142
hypergraph::NodeMap used_nodes
Definition: access_path.h:112
Item * condition
Definition: access_path.h:109
double selectivity
Definition: access_path.h:123
Represents an expression tree in the relational algebra of joins.
Definition: relational_expression.h:62
Definition: table.h:2694
Definition: sql_opt_exec_shared.h:59
Definition: table.h:1394