MySQL 9.4.0
Source Code Documentation
access_path.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_ACCESS_PATH_H
25#define SQL_JOIN_OPTIMIZER_ACCESS_PATH_H
26
27#include <assert.h>
28#include <stdint.h>
29#include <cmath>
30#include <cstddef>
31#include <span>
32#include <type_traits>
33#include <utility>
34#include <vector>
35
36#include "my_alloc.h"
37#include "my_base.h"
38#include "my_table_map.h"
39#include "sql/item.h"
40// IWYU suggests removing row_iterator.h, but then the inlined short form of
41// CreateIteratorFromAccessPath() fails to compile. So use a pragma to keep it.
42#include "sql/iterators/row_iterator.h" // IWYU pragma: keep
47#include "sql/join_type.h"
48#include "sql/mem_root_array.h"
49#include "sql/olap.h"
50#include "sql/sql_class.h"
51#include "sql/table.h"
52
54class Filesort;
56class Item_func_match;
57class JOIN;
58class KEY;
60class QEP_TAB;
61class QUICK_RANGE;
62class SJ_TMP_TABLE;
63class Table_function;
65class Window;
66struct AccessPath;
69struct Index_lookup;
70struct KEY_PART;
71struct POSITION;
73
74/**
75 A specification that two specific relational expressions
76 (e.g., two tables, or a table and a join between two other tables)
77 should be joined together. The actual join conditions, if any,
78 live inside the “expr” object, as does the join type etc.
79 */
83
84 // If this join is made using a hash join, estimates the width
85 // of each row as stored in the hash table, in bytes.
87
88 // The set of (additional) functional dependencies that are active
89 // after this join predicate has been applied. E.g. if we're joining
90 // on t1.x = t2.x, there will be a bit for that functional dependency.
91 // We don't currently support more complex join conditions, but there's
92 // no conceptual reason why we couldn't, e.g. a join on a = b + c
93 // could give rise to the FD {b, c} → a and possibly even {a, b} → c
94 // or {a, c} → b.
95 //
96 // Used in the processing of interesting orders.
98
99 // A less compact form of functional_dependencies, used during building
100 // (FunctionalDependencySet bitmaps are only available after all functional
101 // indexes have been collected and Build() has been called).
103
104 // A semijoin on the following format:
105 //
106 // SELECT ... FROM t1 WHERE EXISTS
107 // (SELECT ... FROM t2 WHERE t1.f1=t2.f2 AND t1.f3=t2.f4 ... t1.fn=t2.fm)
108 //
109 // may be transformed into an equivalent inner join:
110 //
111 // SELECT ... FROM (SELECT DISTINCT f2, f4...fm FROM t2) d JOIN t1
112 // ON t1.f1=d.f2 AND t1.f3=d.f4 ... t1.fn=d.fm
113 //
114 // If this is a suitable semijoin: This field will identify the the
115 // grouping given by (f2, f4..fm). (@see
116 // LogicalOrderings::RemapOrderingIndex() for a description of how this
117 // value can be mapped to an actual ordering). The join
118 // optimizer will then consider deduplicating on it and applying the
119 // above transform. If no such grouping was found, this field will be -1.
121
122 // Same as ordering_idx_needed_for_semijoin_rewrite, but given to the
123 // RemoveDuplicatesIterator for doing the actual grouping. Allocated
124 // on the MEM_ROOT. Can be empty, in which case a LIMIT 1 would do.
125 std::span<Item *> semijoin_group{};
126};
127
128/**
129 A filter of some sort that is not a join condition (those are stored
130 in JoinPredicate objects). AND conditions are typically split up into
131 multiple Predicates.
132 */
133struct Predicate {
135
136 // condition->used_tables(), converted to a NodeMap.
138
139 // tables referred to by the condition, plus any tables whose values
140 // can null any of those tables. (Even when reordering outer joins,
141 // at least one of those tables will still be present on the
142 // left-hand side of the outer join, so this is sufficient.)
143 //
144 // As a special case, we allow setting RAND_TABLE_BIT, even though it
145 // is normally part of a table_map, not a NodeMap.
147
149
150 // Whether this predicate is a join condition after all; it was promoted
151 // to a WHERE predicate since it was part of a cycle (see the comment in
152 // AddCycleEdges()). If it is, it is usually ignored so that we don't
153 // double-apply join conditions -- but if the join in question was not
154 // applied (because the cycle was broken at this point), the predicate
155 // would come into play. This is normally registered on the join itself
156 // (see RelationalExpression::join_predicate_bitmap), but having the bit
157 // on the predicate itself is used to avoid trying to push it down as a
158 // sargable predicate.
159 bool was_join_condition = false;
160
161 // Whether this predicate references tables that could be NULL-complemented
162 // later by an outer join. This could for example be true for degenerate outer
163 // join conditions that are pushed down as a table filter on one of the inner
164 // tables, or for join conditions in inner joins that are on the inner side of
165 // an outer join.
166 //
167 // We keep track of this here in order to prevent collection of functional
168 // dependencies from such predicates if the functional dependencies are not
169 // valid after the outer join.
171
172 // If this is a join condition that came from a multiple equality,
173 // and we have decided to create a mesh from that multiple equality,
174 // returns the index of it into the “multiple_equalities” array
175 // in MakeJoinHypergraph(). (You don't actually need the array to
176 // use this; it's just an opaque index to deduplicate between different
177 // predicates.) Otherwise, -1.
179
180 // See the equivalent fields in JoinPredicate.
183
184 // The list of all subqueries referred to in this predicate, if any.
185 // The optimizer uses this to add their materialized/non-materialized
186 // costs when evaluating filters.
188};
189
193};
194
195/// To indicate that a row estimate is not yet made.
196inline constexpr double kUnknownRowCount = -1.0;
197
198/// To indicate that a cost estimate is not yet made. We use a large negative
199/// value to avoid getting a positive result if we by mistake add this to
200/// a real (positive) cost.
201inline constexpr double kUnknownCost = -1e12;
202
203/// Calculate the cost of reading the first row from an access path, given
204/// estimates for init cost, total cost and the number of rows returned.
205inline double FirstRowCost(double init_cost, double total_cost,
206 double output_rows) {
207 assert(init_cost >= 0.0);
208 assert(total_cost >= init_cost);
209 assert(output_rows >= 0.0);
210 if (output_rows <= 1.0) {
211 return total_cost;
212 }
213 return init_cost + (total_cost - init_cost) / output_rows;
214}
215
216/**
217 Access paths are a query planning structure that correspond 1:1 to iterators,
218 in that an access path contains pretty much exactly the information
219 needed to instantiate given iterator, plus some information that is only
220 needed during planning, such as costs. (The new join optimizer will extend
221 this somewhat in the future. Some iterators also need the query block,
222 ie., JOIN object, they are part of, but that is implicitly available when
223 constructing the tree.)
224
225 AccessPath objects build on a variant, ie., they can hold an access path of
226 any type (table scan, filter, hash join, sort, etc.), although only one at the
227 same time. Currently, they contain 32 bytes of base information that is common
228 to any access path (type identifier, costs, etc.), and then up to 40 bytes
229 that is type-specific (e.g. for a table scan, the TABLE object). It would be
230 nice if we could squeeze it down to 64 and fit a cache line exactly, but it
231 does not seem to be easy without fairly large contortions.
232
233 We could have solved this by inheritance, but the fixed-size design makes it
234 possible to replace an access path when a better one is found, without
235 introducing a new allocation, which will be important when using them as a
236 planning structure.
237 */
239 enum Type : uint8_t {
240 // Basic access paths (those with no children, at least nominally).
241 // NOTE: When adding more paths to this section, also update GetBasicTable()
242 // to handle them.
262
263 // Basic access paths that don't correspond to a specific table.
270
271 // Joins.
276
277 // Composite access paths.
293
294 // Access paths that modify tables.
298
299 /// A general enum to describe the safety of a given operation.
300 /// Currently we only use this to describe row IDs, but it can easily
301 /// be reused for safety of updating a table we're reading from
302 /// (the Halloween problem), or just generally unreproducible results
303 /// (e.g. a TABLESAMPLE changing due to external factors).
304 ///
305 /// Less safe values have higher numerical values.
306 enum Safety : uint8_t {
307 /// The given operation is always safe on this access path.
308 SAFE = 0,
309
310 /// The given operation is safe if this access path is scanned once,
311 /// but not if it's scanned multiple times (e.g. used on the inner side
312 /// of a nested-loop join). A typical example of this is a derived table
313 /// or CTE that is rematerialized on each scan, so that references to
314 /// the old values (such as row IDs) are no longer valid.
316
317 /// The given operation is unsafe on this access path, no matter how many
318 /// or few times it's scanned. Often, it may help to materialize it
319 /// (assuming the materialization itself doesn't use the operation
320 /// in question).
321 UNSAFE = 2
322 };
323
324 /// Whether it is safe to get row IDs (for sorting) from this access path.
326
327 /// Whether this access path counts as one that scans a base table,
328 /// and thus should be counted towards examined_rows. It can sometimes
329 /// seem a bit arbitrary which iterators count towards examined_rows
330 /// and which ones do not, so the only canonical reference is the tests.
331 bool count_examined_rows : 1 {false};
332
333 /// Whether this access path contains a GROUP_INDEX_SKIP_SCAN
334 bool has_group_skip_scan : 1 {false};
335
336#ifndef NDEBUG
337 /// Whether this access path is forced preferred over all others by means
338 /// of a SET DEBUG force_subplan_0x... statement.
339 bool forced_by_dbug : 1 {false};
340#endif
341
342 /// For UPDATE and DELETE statements: The node index of a table which can be
343 /// updated or deleted from immediately as the rows are read from the
344 /// iterator, if this path is only read from once. -1 if there is no such
345 /// table in this path.
346 ///
347 /// Note that this is an index into CostingReceiver's array of nodes, and is
348 /// not necessarily equal to the table number within the query block given by
349 /// Table_ref::tableno().
350 ///
351 /// The table, if any, is currently always the outermost table in the path.
352 ///
353 /// It is possible to have plans where it would be safe to operate
354 /// "immediately" on more than one table. For example, if we do a merge join,
355 /// it is safe to perform immediate deletes on tables on the inner side of the
356 /// join, since both sides are read only once. (However, we currently do not
357 /// support merge joins.)
358 ///
359 /// Another possibility is when the outer table of a nested loop join is
360 /// guaranteed to return at most one row (typically, a unique index lookup
361 /// aka. eq_ref). Then it's safe to delete immediately from both sides of the
362 /// nested loop join. But we don't to this yet.
363 ///
364 /// Hash joins read both sides exactly once, However, with hash joins, the
365 /// scans on the inner tables are not positioned on the correct row when the
366 /// result of the join is returned, so the immediate delete logic will need to
367 /// be changed to reposition the underlying scans before doing the immediate
368 /// deletes. While this can be done, it makes the benefit of immediate deletes
369 /// less obvious for these tables, and it can also be a loss in some cases,
370 /// because we lose the deduplication provided by the Unique object used for
371 /// buffered deletes (the immediate deletes could end up spending time
372 /// repositioning to already deleted rows). So we currently don't attempt to
373 /// do immediate deletes from inner tables of hash joins either.
374 ///
375 /// The outer table of a hash join can be deleted from immediately if the
376 /// inner table fits in memory. If the hash join spills to disk, though,
377 /// neither the rows of the outer table nor the rows of the inner table come
378 /// out in the order of the underlying scan, so it is not safe in general to
379 /// perform immediate deletes on the outer table of a hash join.
380 ///
381 /// If support for immediate operations on multiple tables is added,
382 /// this member could be changed from a node index to a NodeMap.
384
385 /// Which ordering the rows produced by this path follow, if any
386 /// (see interesting_orders.h). This is really a LogicalOrderings::StateIndex,
387 /// but we don't want to add a dependency on interesting_orders.h from
388 /// this file, so we use the base type instead of the typedef here.
390
391 /// If an iterator has been instantiated for this access path, points to the
392 /// iterator. Used for constructing iterators that need to talk to each other
393 /// (e.g. for recursive CTEs, or BKA join), and also for locating timing
394 /// information in EXPLAIN ANALYZE queries.
396
397 double cost() const { return m_cost; }
398
399 double init_cost() const { return m_init_cost; }
400
401 /// The cost of reading the first row.
402 double first_row_cost() const {
404 }
405
406 double init_once_cost() const { return m_init_once_cost; }
407
408 double cost_before_filter() const { return m_cost_before_filter; }
409
410 void set_cost(double val) {
411 assert(std::isfinite(val));
412 assert(val >= 0.0 || val == kUnknownCost);
413 m_cost = val;
414 }
415
416 void set_init_cost(double val) {
417 assert(std::isfinite(val));
418 assert(val >= 0.0 || val == kUnknownCost);
419 m_init_cost = val;
420 }
421
422 void set_init_once_cost(double val) {
423 assert(std::isfinite(val));
424 assert(val >= 0.0);
425 m_init_once_cost = val;
426 }
427
428 void set_cost_before_filter(double val) {
429 assert(std::isfinite(val));
430 assert(val >= 0.0 || val == kUnknownCost);
432 }
433
434 /// Return the cost of scanning the given path for the second time
435 /// (or later) in the given query block. This is really the interesting
436 /// metric, not init_once_cost in itself, but since nearly all paths
437 /// have zero init_once_cost, storing that instead allows us to skip
438 /// a lot of repeated path->init_once_cost = path->init_cost calls
439 /// in the code.
440 double rescan_cost() const { return cost() - init_once_cost(); }
441
442 /// If no filter, identical to num_output_rows.
444
445 /// Bitmap of WHERE predicates that we are including on this access path,
446 /// referring to the “predicates” array internal to the join optimizer.
447 /// Since bit masks are much cheaper to deal with than creating Item
448 /// objects, and we don't invent new conditions during join optimization
449 /// (all of them are known when we begin optimization), we stick to
450 /// manipulating bit masks during optimization, saying which filters will be
451 /// applied at this node (a 1-bit means the filter will be applied here; if
452 /// there are multiple ones, they are ANDed together).
453 ///
454 /// This is used during join optimization only; before iterators are
455 /// created, we will add FILTER access paths to represent these instead,
456 /// removing the dependency on the array. Said FILTER paths are by
457 /// convention created with materialize_subqueries = false, since the by far
458 /// most common case is that there are no subqueries in the predicate.
459 /// In other words, if you wish to represent a filter with
460 /// materialize_subqueries = true, you will need to make an explicit FILTER
461 /// node.
462 ///
463 /// See also nested_loop_join().equijoin_predicates, which is for filters
464 /// being applied _before_ nested-loop joins, but is otherwise the same idea.
466
467 /// Bitmap of sargable join predicates that have already been applied
468 /// in this access path by means of an index lookup (ref access),
469 /// again referring to “predicates”, and thus should not be counted again
470 /// for selectivity. Note that the filter may need to be applied
471 /// nevertheless (especially in case of type conversions); see
472 /// subsumed_sargable_join_predicates.
473 ///
474 /// Since these refer to the same array as filter_predicates, they will
475 /// never overlap with filter_predicates, and so we can reuse the same
476 /// memory using an alias (a union would not be allowed, since OverflowBitset
477 /// is a class with non-trivial default constructor), even though the meaning
478 /// is entirely separate. If N = num_where_predicates in the hypergraph, then
479 /// bits 0..(N-1) belong to filter_predicates, and the rest to
480 /// applied_sargable_join_predicates.
482 return filter_predicates;
483 }
485 return filter_predicates;
486 }
487
488 /// Bitmap of WHERE predicates that touch tables we have joined in,
489 /// but that we could not apply yet (for instance because they reference
490 /// other tables, or because because we could not push them down into
491 /// the nullable side of outer joins). Used during planning only
492 /// (see filter_predicates).
494
495 /// Similar to applied_sargable_join_predicates, bitmap of sargable
496 /// join predicates that have been applied and will subsume the join
497 /// predicate entirely, ie., not only should the selectivity not be
498 /// double-counted, but the predicate itself is redundant and need not
499 /// be applied as a filter. (It is an error to have a bit set here but not
500 /// in applied_sargable_join_predicates.)
502 return delayed_predicates;
503 }
505 return delayed_predicates;
506 }
507
508 /// If nonzero, a bitmap of other tables whose joined-in rows must already be
509 /// loaded when rows from this access path are evaluated; that is, this
510 /// access path must be put on the inner side of a nested-loop join (or
511 /// multiple such joins) where the outer side includes all of the given
512 /// tables.
513 ///
514 /// The most obvious case for this is dependent tables in LATERAL, but a more
515 /// common case is when we have pushed join conditions referring to those
516 /// tables; e.g., if this access path represents t1 and we have a condition
517 /// t1.x=t2.x that is pushed down into an index lookup (ref access), t2 will
518 /// be set in this bitmap. We can still join in other tables, deferring t2,
519 /// but the bit(s) will then propagate, and we cannot be on the right side of
520 /// a hash join until parameter_tables is zero again. (Also see
521 /// DisallowParameterizedJoinPath() for when we disallow such deferring,
522 /// as an optimization.)
523 ///
524 /// As a special case, we allow setting RAND_TABLE_BIT, even though it
525 /// is normally part of a table_map, not a NodeMap. In this case, it specifies
526 /// that the access path is entirely noncachable, because it depends on
527 /// something nondeterministic or an outer reference, and thus can never be on
528 /// the right side of a hash join, ever.
530
531 /// Auxiliary data used by a secondary storage engine while processing the
532 /// access path during optimization and execution. The secondary storage
533 /// engine is free to store any useful information in this member, for example
534 /// extra statistics or cost estimates. The data pointed to is fully owned by
535 /// the secondary storage engine, and it is the responsibility of the
536 /// secondary engine to manage the memory and make sure it is properly
537 /// destroyed.
538 void *secondary_engine_data{nullptr};
539
540 // Accessors for the union below.
541 auto &table_scan() {
542 assert(type == TABLE_SCAN);
543 return u.table_scan;
544 }
545 const auto &table_scan() const {
546 assert(type == TABLE_SCAN);
547 return u.table_scan;
548 }
549 auto &sample_scan() {
550 assert(type == SAMPLE_SCAN);
551 return u.sample_scan;
552 }
553 const auto &sample_scan() const {
554 assert(type == SAMPLE_SCAN);
555 return u.sample_scan;
556 }
557 auto &index_scan() {
558 assert(type == INDEX_SCAN);
559 return u.index_scan;
560 }
561 const auto &index_scan() const {
562 assert(type == INDEX_SCAN);
563 return u.index_scan;
564 }
566 assert(type == INDEX_DISTANCE_SCAN);
567 return u.index_distance_scan;
568 }
569 const auto &index_distance_scan() const {
570 assert(type == INDEX_DISTANCE_SCAN);
571 return u.index_distance_scan;
572 }
573 auto &ref() {
574 assert(type == REF);
575 return u.ref;
576 }
577 const auto &ref() const {
578 assert(type == REF);
579 return u.ref;
580 }
581 auto &ref_or_null() {
582 assert(type == REF_OR_NULL);
583 return u.ref_or_null;
584 }
585 const auto &ref_or_null() const {
586 assert(type == REF_OR_NULL);
587 return u.ref_or_null;
588 }
589 auto &eq_ref() {
590 assert(type == EQ_REF);
591 return u.eq_ref;
592 }
593 const auto &eq_ref() const {
594 assert(type == EQ_REF);
595 return u.eq_ref;
596 }
598 assert(type == PUSHED_JOIN_REF);
599 return u.pushed_join_ref;
600 }
601 const auto &pushed_join_ref() const {
602 assert(type == PUSHED_JOIN_REF);
603 return u.pushed_join_ref;
604 }
606 assert(type == FULL_TEXT_SEARCH);
607 return u.full_text_search;
608 }
609 const auto &full_text_search() const {
610 assert(type == FULL_TEXT_SEARCH);
611 return u.full_text_search;
612 }
613 auto &const_table() {
614 assert(type == CONST_TABLE);
615 return u.const_table;
616 }
617 const auto &const_table() const {
618 assert(type == CONST_TABLE);
619 return u.const_table;
620 }
621 auto &mrr() {
622 assert(type == MRR);
623 return u.mrr;
624 }
625 const auto &mrr() const {
626 assert(type == MRR);
627 return u.mrr;
628 }
629 auto &follow_tail() {
630 assert(type == FOLLOW_TAIL);
631 return u.follow_tail;
632 }
633 const auto &follow_tail() const {
634 assert(type == FOLLOW_TAIL);
635 return u.follow_tail;
636 }
638 assert(type == INDEX_RANGE_SCAN);
639 return u.index_range_scan;
640 }
641 const auto &index_range_scan() const {
642 assert(type == INDEX_RANGE_SCAN);
643 return u.index_range_scan;
644 }
645 auto &index_merge() {
646 assert(type == INDEX_MERGE);
647 return u.index_merge;
648 }
649 const auto &index_merge() const {
650 assert(type == INDEX_MERGE);
651 return u.index_merge;
652 }
654 assert(type == ROWID_INTERSECTION);
655 return u.rowid_intersection;
656 }
657 const auto &rowid_intersection() const {
658 assert(type == ROWID_INTERSECTION);
659 return u.rowid_intersection;
660 }
661 auto &rowid_union() {
662 assert(type == ROWID_UNION);
663 return u.rowid_union;
664 }
665 const auto &rowid_union() const {
666 assert(type == ROWID_UNION);
667 return u.rowid_union;
668 }
670 assert(type == INDEX_SKIP_SCAN);
671 return u.index_skip_scan;
672 }
673 const auto &index_skip_scan() const {
674 assert(type == INDEX_SKIP_SCAN);
675 return u.index_skip_scan;
676 }
678 assert(type == GROUP_INDEX_SKIP_SCAN);
679 return u.group_index_skip_scan;
680 }
681 const auto &group_index_skip_scan() const {
682 assert(type == GROUP_INDEX_SKIP_SCAN);
683 return u.group_index_skip_scan;
684 }
687 return u.dynamic_index_range_scan;
688 }
689 const auto &dynamic_index_range_scan() const {
691 return u.dynamic_index_range_scan;
692 }
695 return u.materialized_table_function;
696 }
697 const auto &materialized_table_function() const {
699 return u.materialized_table_function;
700 }
702 assert(type == UNQUALIFIED_COUNT);
703 return u.unqualified_count;
704 }
705 const auto &unqualified_count() const {
706 assert(type == UNQUALIFIED_COUNT);
707 return u.unqualified_count;
708 }
710 assert(type == TABLE_VALUE_CONSTRUCTOR);
711 return u.table_value_constructor;
712 }
713 const auto &table_value_constructor() const {
714 assert(type == TABLE_VALUE_CONSTRUCTOR);
715 return u.table_value_constructor;
716 }
718 assert(type == FAKE_SINGLE_ROW);
719 return u.fake_single_row;
720 }
721 const auto &fake_single_row() const {
722 assert(type == FAKE_SINGLE_ROW);
723 return u.fake_single_row;
724 }
725 auto &zero_rows() {
726 assert(type == ZERO_ROWS);
727 return u.zero_rows;
728 }
729 const auto &zero_rows() const {
730 assert(type == ZERO_ROWS);
731 return u.zero_rows;
732 }
734 assert(type == ZERO_ROWS_AGGREGATED);
735 return u.zero_rows_aggregated;
736 }
737 const auto &zero_rows_aggregated() const {
738 assert(type == ZERO_ROWS_AGGREGATED);
739 return u.zero_rows_aggregated;
740 }
741 auto &hash_join() {
742 assert(type == HASH_JOIN);
743 return u.hash_join;
744 }
745 const auto &hash_join() const {
746 assert(type == HASH_JOIN);
747 return u.hash_join;
748 }
749 auto &bka_join() {
750 assert(type == BKA_JOIN);
751 return u.bka_join;
752 }
753 const auto &bka_join() const {
754 assert(type == BKA_JOIN);
755 return u.bka_join;
756 }
758 assert(type == NESTED_LOOP_JOIN);
759 return u.nested_loop_join;
760 }
761 const auto &nested_loop_join() const {
762 assert(type == NESTED_LOOP_JOIN);
763 return u.nested_loop_join;
764 }
767 return u.nested_loop_semijoin_with_duplicate_removal;
768 }
771 return u.nested_loop_semijoin_with_duplicate_removal;
772 }
773 auto &filter() {
774 assert(type == FILTER);
775 return u.filter;
776 }
777 const auto &filter() const {
778 assert(type == FILTER);
779 return u.filter;
780 }
781 auto &sort() {
782 assert(type == SORT);
783 return u.sort;
784 }
785 const auto &sort() const {
786 assert(type == SORT);
787 return u.sort;
788 }
789 auto &aggregate() {
790 assert(type == AGGREGATE);
791 return u.aggregate;
792 }
793 const auto &aggregate() const {
794 assert(type == AGGREGATE);
795 return u.aggregate;
796 }
798 assert(type == TEMPTABLE_AGGREGATE);
799 return u.temptable_aggregate;
800 }
801 const auto &temptable_aggregate() const {
802 assert(type == TEMPTABLE_AGGREGATE);
803 return u.temptable_aggregate;
804 }
805 auto &limit_offset() {
806 assert(type == LIMIT_OFFSET);
807 return u.limit_offset;
808 }
809 const auto &limit_offset() const {
810 assert(type == LIMIT_OFFSET);
811 return u.limit_offset;
812 }
813 auto &stream() {
814 assert(type == STREAM);
815 return u.stream;
816 }
817 const auto &stream() const {
818 assert(type == STREAM);
819 return u.stream;
820 }
821 auto &materialize() {
822 assert(type == MATERIALIZE);
823 return u.materialize;
824 }
825 const auto &materialize() const {
826 assert(type == MATERIALIZE);
827 return u.materialize;
828 }
831 return u.materialize_information_schema_table;
832 }
835 return u.materialize_information_schema_table;
836 }
837 auto &append() {
838 assert(type == APPEND);
839 return u.append;
840 }
841 const auto &append() const {
842 assert(type == APPEND);
843 return u.append;
844 }
845 auto &window() {
846 assert(type == WINDOW);
847 return u.window;
848 }
849 const auto &window() const {
850 assert(type == WINDOW);
851 return u.window;
852 }
853 auto &weedout() {
854 assert(type == WEEDOUT);
855 return u.weedout;
856 }
857 const auto &weedout() const {
858 assert(type == WEEDOUT);
859 return u.weedout;
860 }
862 assert(type == REMOVE_DUPLICATES);
863 return u.remove_duplicates;
864 }
865 const auto &remove_duplicates() const {
866 assert(type == REMOVE_DUPLICATES);
867 return u.remove_duplicates;
868 }
871 return u.remove_duplicates_on_index;
872 }
873 const auto &remove_duplicates_on_index() const {
875 return u.remove_duplicates_on_index;
876 }
877 auto &alternative() {
878 assert(type == ALTERNATIVE);
879 return u.alternative;
880 }
881 const auto &alternative() const {
882 assert(type == ALTERNATIVE);
883 return u.alternative;
884 }
886 assert(type == CACHE_INVALIDATOR);
887 return u.cache_invalidator;
888 }
889 const auto &cache_invalidator() const {
890 assert(type == CACHE_INVALIDATOR);
891 return u.cache_invalidator;
892 }
893 auto &delete_rows() {
894 assert(type == DELETE_ROWS);
895 return u.delete_rows;
896 }
897 const auto &delete_rows() const {
898 assert(type == DELETE_ROWS);
899 return u.delete_rows;
900 }
901 auto &update_rows() {
902 assert(type == UPDATE_ROWS);
903 return u.update_rows;
904 }
905 const auto &update_rows() const {
906 assert(type == UPDATE_ROWS);
907 return u.update_rows;
908 }
909
910 double num_output_rows() const { return m_num_output_rows; }
911
912 void set_num_output_rows(double val) {
913 assert(std::isfinite(val));
914 assert(val == kUnknownRowCount || val >= 0.0);
915 m_num_output_rows = val;
916 }
917
918 private:
919 /// Expected number of output rows.
921
922 /// Expected cost to read all of this access path once.
924
925 /// Expected cost to initialize this access path; ie., cost to read
926 /// k out of N rows would be init_cost + (k/N) * (cost - init_cost).
927 /// Note that EXPLAIN prints out cost of reading the _first_ row
928 /// because it is easier for the user and also easier to measure in
929 /// EXPLAIN ANALYZE, but it is easier to do calculations with a pure
930 /// initialization cost, so that is what we use in this member.
931 /// kUnknownCost for unknown.
933
934 /// Of init_cost, how much of the initialization needs only to be done
935 /// once per query block. (This is a cost, not a proportion.)
936 /// Ie., if the access path can reuse some its initialization work
937 /// if Init() is called multiple times, this member will be nonzero.
938 /// A typical example is a materialized table with rematerialize=false;
939 /// the second time Init() is called, it's a no-op. Most paths will have
940 /// init_once_cost = 0.0, ie., repeated scans will cost the same.
941 /// We do not intend to use this field to model cache effects.
942 ///
943 /// This is currently not printed in EXPLAIN, only optimizer trace.
944 double m_init_once_cost{0.0};
945
946 /// If no filter, identical to cost. init_cost is always the same
947 /// (filters have zero initialization cost).
949
950 // We'd prefer if this could be an std::variant, but we don't have C++17 yet.
951 // It is private to force all access to be through the type-checking
952 // accessors.
953 //
954 // For information about the meaning of each value, see the corresponding
955 // row iterator constructors.
956 union {
957 struct {
960 struct {
961 TABLE *table;
965 struct {
966 TABLE *table;
967 int idx;
971 struct {
972 TABLE *table;
973 int idx;
975 bool reverse;
977 struct {
978 TABLE *table;
980 bool use_order;
981 bool reverse;
983 struct {
984 TABLE *table;
986 bool use_order;
988 struct {
989 TABLE *table;
992 struct {
993 TABLE *table;
995 bool use_order;
998 struct {
999 TABLE *table;
1001 bool use_order;
1005 struct {
1006 TABLE *table;
1009 struct {
1010 TABLE *table;
1016 struct {
1017 TABLE *table;
1019 struct {
1020 // The key part(s) we are scanning on. Note that this may be an array.
1021 // You can get the table we are working on by looking into
1022 // used_key_parts[0].field->table (it is not stored directly, to avoid
1023 // going over the AccessPath size limits).
1025
1026 // The actual ranges we are scanning over (originally derived from “key”).
1027 // Not a Bounds_checked_array, to save 4 bytes on the length.
1029 unsigned num_ranges;
1030
1031 unsigned mrr_flags;
1033
1034 // Which index (in the TABLE) we are scanning over, and how many of its
1035 // key parts we are using.
1036 unsigned index;
1038
1039 // If true, the scan can return rows in rowid order.
1041
1042 // If true, the scan _should_ return rows in rowid order.
1043 // Should only be set if can_be_used_for_ror == true.
1045
1046 // If true, this plan can be used for index merge scan.
1048
1049 // See row intersection for more details.
1051
1052 // Whether we are scanning over a geometry key part.
1053 bool geometry : 1;
1054
1055 // Whether we need a reverse scan. Only supported if geometry == false.
1056 bool reverse : 1;
1057
1058 // For a reverse scan, if we are using extended key parts. It is needed,
1059 // to set correct flags when retrieving records.
1062 struct {
1063 TABLE *table;
1068 struct {
1069 TABLE *table;
1071
1072 // Clustered primary key scan, if any.
1074
1075 bool forced_by_hint;
1078
1079 // If true, the first child scan should reuse table->file instead of
1080 // creating its own. This is true if the intersection is the topmost
1081 // range scan, but _not_ if it's below a union. (The reasons for this
1082 // are unknown.) It can also be negated by logic involving
1083 // retrieve_full_rows and is_covering, again for unknown reasons.
1084 //
1085 // This is not only for performance; multi-table delete has a hidden
1086 // dependency on this behavior when running against certain types of
1087 // tables (e.g. MyISAM), as it assumes table->file is correctly positioned
1088 // when deleting (and not all table types can transfer the position of one
1089 // handler to another by using position()).
1090 bool reuse_handler;
1091
1092 // true if no row retrieval phase is necessary.
1095 struct {
1096 TABLE *table;
1098 bool forced_by_hint;
1100 struct {
1101 TABLE *table;
1102 unsigned index;
1103 unsigned num_used_key_parts;
1104 bool forced_by_hint;
1105
1106 // Large, and has nontrivial destructors, so split out into
1107 // its own allocation.
1110 struct {
1111 TABLE *table;
1112 unsigned index;
1113 unsigned num_used_key_parts;
1114 bool forced_by_hint;
1115
1116 // Large, so split out into its own allocation.
1119 struct {
1120 TABLE *table;
1121 QEP_TAB *qep_tab; // Used only for buffering.
1123 struct {
1124 TABLE *table;
1128 struct {
1130
1131 struct {
1134 struct {
1135 // No members.
1137 struct {
1138 // The child is optional. It is only used for keeping track of which
1139 // tables are pruned away by this path, and it is only needed when this
1140 // path is on the inner side of an outer join. See ZeroRowsIterator for
1141 // details. The child of a ZERO_ROWS access path will not be visited by
1142 // WalkAccessPaths(). It will be visited by WalkTablesUnderAccessPath()
1143 // only if called with include_pruned_tables = true. No iterator is
1144 // created for the child, and the child is not shown by EXPLAIN.
1146 // Used for EXPLAIN only.
1147 // TODO(sgunders): make an enum.
1148 const char *cause;
1150 struct {
1151 // Used for EXPLAIN only.
1152 // TODO(sgunders): make an enum.
1153 const char *cause;
1155
1156 struct {
1160 bool store_rowids; // Whether we are below a weedout or not.
1164 struct {
1169 bool store_rowids; // Whether we are below a weedout or not.
1172 struct {
1174 JoinType join_type; // Somewhat redundant wrt. join_predicate.
1178
1179 // Equijoin filters to apply before the join, if any.
1180 // Indexes into join_predicate->expr->equijoin_conditions.
1181 // Non-equijoin conditions are always applied.
1182 // If already_expanded_predicates is true, do not re-expand.
1184
1185 // NOTE: Due to the nontrivial constructor on equijoin_predicates,
1186 // this struct needs an initializer, or the union would not be
1187 // default-constructible. If we need more than one union member
1188 // with such an initializer, we would probably need to change
1189 // equijoin_predicates into a uint64_t type-punned to an OverflowBitset.
1190 } nested_loop_join = {nullptr, nullptr, JoinType::INNER, false, false,
1191 nullptr, {}};
1192 struct {
1194 const TABLE *table;
1196 size_t key_len;
1198
1199 struct {
1202
1203 // This parameter, unlike nearly all others, is not passed to the the
1204 // actual iterator. Instead, if true, it signifies that when creating
1205 // the iterator, all materializable subqueries in “condition” should be
1206 // materialized (with any in2exists condition removed first). In the
1207 // very rare case that there are two or more such subqueries, this is
1208 // an all-or-nothing decision, for simplicity.
1209 //
1210 // See FinalizeMaterializedSubqueries().
1213 struct {
1217
1218 // If filesort is nullptr: A new filesort will be created at the
1219 // end of optimization, using this order and flags. Otherwise: Only
1220 // used by EXPLAIN.
1227 struct {
1231 struct {
1235 TABLE *table;
1239 struct {
1241 ha_rows limit;
1245 // Only used when the LIMIT is on a UNION with SQL_CALC_FOUND_ROWS.
1246 // See Query_expression::send_records.
1249 struct {
1251 JOIN *join;
1253 TABLE *table;
1255 int ref_slice;
1257 struct {
1258 // NOTE: The only legal access paths within table_path are
1259 // TABLE_SCAN, REF, REF_OR_NULL, EQ_REF, ALTERNATIVE,
1260 // CONST_TABLE (somewhat nonsensical), INDEX_SCAN and DYNAMIC_INDEX_SCAN
1262
1263 // Large, and has nontrivial destructors, so split out
1264 // into its own allocation.
1266 /** The total cost of executing the queries that we materialize.*/
1268 /// The number of materialized rows (as opposed to the number of rows
1269 /// fetched by table_path). Needed for 'explain'.
1272 struct {
1275 Item *condition;
1277 struct {
1280 struct {
1285 int ref_slice;
1288 struct {
1293 struct {
1294 using ItemSpan = std::span<Item *>;
1296
1297 /// @cond IGNORE
1298 // These functions somehow triggers a doxygen warning. (Presumably
1299 // a doxygen bug.)
1300 ItemSpan &group_items() {
1301 return reinterpret_cast<ItemSpan &>(m_group_items);
1302 }
1303
1304 const ItemSpan &group_items() const {
1305 return reinterpret_cast<const ItemSpan &>(m_group_items);
1306 }
1307 /// @endcond
1308
1309 private:
1310 // gcc 11 does not support a span as a union member. Replace this
1311 // with "std::span<Item *> group_items" when we move to newer gcc version.
1312 alignas(alignof(ItemSpan)) std::byte m_group_items[sizeof(ItemSpan)];
1314 struct {
1316 TABLE *table;
1317 KEY *key;
1320 struct {
1322
1323 // For the ref.
1327 struct {
1329 const char *name;
1331 struct {
1336 struct {
1341 } u;
1342};
1344 "AccessPath must be trivially destructible, as it is allocated "
1345 "on the MEM_ROOT and not wrapped in unique_ptr_destroy_only"
1346 "(because multiple candidates during planning could point to "
1347 "the same access paths, and refcounting would be expensive)");
1348static_assert(sizeof(AccessPath) <= 144,
1349 "We are creating a lot of access paths in the join "
1350 "optimizer, so be sure not to bloat it without noticing. "
1351 "(96 bytes for the base, 48 bytes for the variant.)");
1352
1353inline void CopyBasicProperties(const AccessPath &from, AccessPath *to) {
1355 to->set_cost(from.cost());
1356 to->set_init_cost(from.init_cost());
1359 to->safe_for_rowid = from.safe_for_rowid;
1360 to->ordering_state = from.ordering_state;
1362}
1363
1364// Trivial factory functions for all of the types of access paths above.
1365
1367 bool count_examined_rows) {
1368 AccessPath *path = new (thd->mem_root) AccessPath;
1370 path->count_examined_rows = count_examined_rows;
1371 path->table_scan().table = table;
1372 return path;
1373}
1374
1376 double sampling_percentage,
1377 bool count_examined_rows) {
1378 AccessPath *path = new (thd->mem_root) AccessPath;
1380 path->count_examined_rows = count_examined_rows;
1381 path->sample_scan().table = table;
1382 path->sample_scan().sampling_percentage = sampling_percentage;
1383 return path;
1384}
1385
1387 bool use_order, bool reverse,
1388 bool count_examined_rows) {
1389 AccessPath *path = new (thd->mem_root) AccessPath;
1391 path->count_examined_rows = count_examined_rows;
1392 path->index_scan().table = table;
1393 path->index_scan().idx = idx;
1394 path->index_scan().use_order = use_order;
1395 path->index_scan().reverse = reverse;
1396 return path;
1397}
1398
1400 bool use_order, bool reverse,
1401 bool count_examined_rows) {
1402 AccessPath *path = new (thd->mem_root) AccessPath;
1403 path->type = AccessPath::REF;
1404 path->count_examined_rows = count_examined_rows;
1405 path->ref().table = table;
1406 path->ref().ref = ref;
1407 path->ref().use_order = use_order;
1408 path->ref().reverse = reverse;
1409 return path;
1410}
1411
1413 Index_lookup *ref, bool use_order,
1414 bool count_examined_rows) {
1415 AccessPath *path = new (thd->mem_root) AccessPath;
1417 path->count_examined_rows = count_examined_rows;
1418 path->ref_or_null().table = table;
1419 path->ref_or_null().ref = ref;
1420 path->ref_or_null().use_order = use_order;
1421 return path;
1422}
1423
1425 bool count_examined_rows) {
1426 AccessPath *path = new (thd->mem_root) AccessPath;
1427 path->type = AccessPath::EQ_REF;
1428 path->count_examined_rows = count_examined_rows;
1429 path->eq_ref().table = table;
1430 path->eq_ref().ref = ref;
1431 return path;
1432}
1433
1435 Index_lookup *ref, bool use_order,
1436 bool is_unique,
1437 bool count_examined_rows) {
1438 AccessPath *path = new (thd->mem_root) AccessPath;
1440 path->count_examined_rows = count_examined_rows;
1441 path->pushed_join_ref().table = table;
1442 path->pushed_join_ref().ref = ref;
1443 path->pushed_join_ref().use_order = use_order;
1444 path->pushed_join_ref().is_unique = is_unique;
1445 return path;
1446}
1447
1450 Item_func_match *ft_func,
1451 bool use_order, bool use_limit,
1452 bool count_examined_rows) {
1453 AccessPath *path = new (thd->mem_root) AccessPath;
1455 path->count_examined_rows = count_examined_rows;
1456 path->full_text_search().table = table;
1457 path->full_text_search().ref = ref;
1458 path->full_text_search().use_order = use_order;
1459 path->full_text_search().use_limit = use_limit;
1460 path->full_text_search().ft_func = ft_func;
1461 return path;
1462}
1463
1466 bool count_examined_rows) {
1467 AccessPath *path = new (thd->mem_root) AccessPath;
1469 path->count_examined_rows = count_examined_rows;
1470 path->set_num_output_rows(1.0);
1471 path->set_cost(0.0);
1472 path->set_init_cost(0.0);
1473 path->set_init_once_cost(0.0);
1474 path->const_table().table = table;
1475 path->const_table().ref = ref;
1476 return path;
1477}
1478
1480 int mrr_flags) {
1481 AccessPath *path = new (thd->mem_root) AccessPath;
1482 path->type = AccessPath::MRR;
1483 path->mrr().table = table;
1484 path->mrr().ref = ref;
1485 path->mrr().mrr_flags = mrr_flags;
1486
1487 // This will be filled in when the BKA iterator is created.
1488 path->mrr().bka_path = nullptr;
1489
1490 return path;
1491}
1492
1494 bool count_examined_rows) {
1495 AccessPath *path = new (thd->mem_root) AccessPath;
1497 path->count_examined_rows = count_examined_rows;
1498 path->follow_tail().table = table;
1499 return path;
1500}
1501
1503 THD *thd, TABLE *table, QEP_TAB *qep_tab, bool count_examined_rows) {
1504 AccessPath *path = new (thd->mem_root) AccessPath;
1506 path->count_examined_rows = count_examined_rows;
1507 path->dynamic_index_range_scan().table = table;
1508 path->dynamic_index_range_scan().qep_tab = qep_tab;
1509 return path;
1510}
1511
1513 THD *thd, TABLE *table, Table_function *table_function,
1514 AccessPath *table_path) {
1515 AccessPath *path = new (thd->mem_root) AccessPath;
1517 path->materialized_table_function().table = table;
1518 path->materialized_table_function().table_function = table_function;
1519 path->materialized_table_function().table_path = table_path;
1520 return path;
1521}
1522
1524 AccessPath *path = new (thd->mem_root) AccessPath;
1526 return path;
1527}
1528
1530 const JOIN *join);
1531
1533 THD *thd, AccessPath *outer, AccessPath *inner, const TABLE *table,
1534 KEY *key, size_t key_len) {
1535 AccessPath *path = new (thd->mem_root) AccessPath;
1537 path->nested_loop_semijoin_with_duplicate_removal().outer = outer;
1538 path->nested_loop_semijoin_with_duplicate_removal().inner = inner;
1539 path->nested_loop_semijoin_with_duplicate_removal().table = table;
1540 path->nested_loop_semijoin_with_duplicate_removal().key = key;
1541 path->nested_loop_semijoin_with_duplicate_removal().key_len = key_len;
1542 path->has_group_skip_scan =
1544 return path;
1545}
1546
1548 Item *condition) {
1549 AccessPath *path = new (thd->mem_root) AccessPath;
1550 path->type = AccessPath::FILTER;
1551 path->filter().child = child;
1552 path->filter().condition = condition;
1553 path->filter().materialize_subqueries = false;
1554 path->has_group_skip_scan = child->has_group_skip_scan;
1555 return path;
1556}
1557
1558// Not inline, because it needs access to filesort internals
1559// (which are forward-declared in this file).
1561 ORDER *order, bool count_examined_rows);
1562
1564 olap_type olap) {
1565 AccessPath *path = new (thd->mem_root) AccessPath;
1567 path->aggregate().child = child;
1568 path->aggregate().olap = olap;
1569 path->has_group_skip_scan = child->has_group_skip_scan;
1570 return path;
1571}
1572
1574 THD *thd, AccessPath *subquery_path, JOIN *join,
1575 Temp_table_param *temp_table_param, TABLE *table, AccessPath *table_path,
1576 int ref_slice) {
1577 AccessPath *path = new (thd->mem_root) AccessPath;
1579 path->temptable_aggregate().subquery_path = subquery_path;
1580 path->temptable_aggregate().join = join;
1581 path->temptable_aggregate().temp_table_param = temp_table_param;
1582 path->temptable_aggregate().table = table;
1583 path->temptable_aggregate().table_path = table_path;
1584 path->temptable_aggregate().ref_slice = ref_slice;
1585 return path;
1586}
1587
1589 ha_rows limit, ha_rows offset,
1590 bool count_all_rows,
1591 bool reject_multiple_rows,
1592 ha_rows *send_records_override) {
1594 AccessPath *path = new (thd->mem_root) AccessPath;
1596 path->immediate_update_delete_table = child->immediate_update_delete_table;
1597 path->limit_offset().child = child;
1598 path->limit_offset().limit = limit;
1599 path->limit_offset().offset = offset;
1600 path->limit_offset().count_all_rows = count_all_rows;
1601 path->limit_offset().reject_multiple_rows = reject_multiple_rows;
1602 path->limit_offset().send_records_override = send_records_override;
1603 CopyBasicProperties(*child, path);
1605 return path;
1606}
1607
1609 bool count_examined_rows) {
1610 AccessPath *path = new (thd->mem_root) AccessPath;
1612 path->count_examined_rows = count_examined_rows;
1613 path->set_num_output_rows(1.0);
1614 path->set_cost(0.0);
1615 path->set_init_cost(0.0);
1616 path->set_init_once_cost(0.0);
1617 return path;
1618}
1619
1621 const char *cause) {
1622 AccessPath *path = new (thd->mem_root) AccessPath;
1624 path->zero_rows().child = child;
1625 path->zero_rows().cause = cause;
1626 path->set_num_output_rows(0.0);
1627 path->set_cost(0.0);
1628 path->set_init_cost(0.0);
1629 path->set_init_once_cost(0.0);
1630 path->num_output_rows_before_filter = 0.0;
1631 path->set_cost_before_filter(0.0);
1632 return path;
1633}
1634
1635inline AccessPath *NewZeroRowsAccessPath(THD *thd, const char *cause) {
1636 return NewZeroRowsAccessPath(thd, /*child=*/nullptr, cause);
1637}
1638
1640 const char *cause) {
1641 AccessPath *path = new (thd->mem_root) AccessPath;
1643 path->zero_rows_aggregated().cause = cause;
1644 path->set_num_output_rows(1.0);
1645 path->set_cost(0.0);
1646 path->set_init_cost(0.0);
1647 return path;
1648}
1649
1651 JOIN *join,
1652 Temp_table_param *temp_table_param,
1653 TABLE *table, int ref_slice) {
1654 AccessPath *path = new (thd->mem_root) AccessPath;
1655 path->type = AccessPath::STREAM;
1656 path->stream().child = child;
1657 path->stream().join = join;
1658 path->stream().temp_table_param = temp_table_param;
1659 path->stream().table = table;
1660 path->stream().ref_slice = ref_slice;
1661 // Will be set later if we get a weedout access path as parent.
1662 path->stream().provide_rowid = false;
1663 path->has_group_skip_scan = child->has_group_skip_scan;
1664 return path;
1665}
1666
1669 JOIN *join, bool copy_items,
1670 Temp_table_param *temp_table_param) {
1671 assert(path != nullptr);
1673 MaterializePathParameters::Operand &operand = array[0];
1674 operand.subquery_path = path;
1675 operand.select_number = select_number;
1676 operand.join = join;
1678 operand.copy_items = copy_items;
1679 operand.temp_table_param = temp_table_param;
1680 return array;
1681}
1682
1686 AccessPath *table_path, Common_table_expr *cte, Query_expression *unit,
1687 int ref_slice, bool rematerialize, ha_rows limit_rows,
1688 bool reject_multiple_rows,
1693 param->m_operands = std::move(operands);
1694 if (rematerialize) {
1695 // There's no point in adding invalidators if we're rematerializing
1696 // every time anyway.
1697 param->invalidators = nullptr;
1698 } else {
1699 param->invalidators = invalidators;
1700 }
1701 param->table = table;
1702 param->cte = cte;
1703 param->unit = unit;
1704 param->ref_slice = ref_slice;
1705 param->rematerialize = rematerialize;
1706 param->limit_rows = (table == nullptr || table->is_union_or_table()
1707 ? limit_rows
1708 :
1709 // INTERSECT, EXCEPT: Enforced by TableScanIterator,
1710 // see its constructor
1711 HA_POS_ERROR);
1712 param->reject_multiple_rows = reject_multiple_rows;
1713 param->deduplication_reason = dedup_reason;
1714
1715#ifndef NDEBUG
1716 for (MaterializePathParameters::Operand &operand : param->m_operands) {
1717 assert(operand.subquery_path != nullptr);
1718 }
1719#endif
1720
1721 AccessPath *path = new (thd->mem_root) AccessPath;
1723 path->materialize().table_path = table_path;
1724 path->materialize().param = param;
1725 path->materialize().subquery_cost = kUnknownCost;
1726 path->materialize().subquery_rows = kUnknownRowCount;
1727 if (rematerialize) {
1728 path->safe_for_rowid = AccessPath::SAFE_IF_SCANNED_ONCE;
1729 } else {
1730 // The default; this is just to be explicit in the code.
1731 path->safe_for_rowid = AccessPath::SAFE;
1732 }
1733 return path;
1734}
1735
1737 THD *thd, AccessPath *table_path, Table_ref *table_list, Item *condition) {
1738 AccessPath *path = new (thd->mem_root) AccessPath;
1740 path->materialize_information_schema_table().table_path = table_path;
1741 path->materialize_information_schema_table().table_list = table_list;
1742 path->materialize_information_schema_table().condition = condition;
1743 return path;
1744}
1745
1746/// Add path costs c1 and c2, but handle kUnknownCost correctly.
1747inline double AddCost(double c1, double c2) {
1748 // If one is undefined, use the other, as we have nothing else.
1749 if (c1 == kUnknownCost) {
1750 return c2;
1751 } else if (c2 == kUnknownCost) {
1752 return c1;
1753 } else {
1754 return c1 + c2;
1755 }
1756}
1757
1758/// Add row counts c1 and c2, but handle kUnknownRowCount correctly.
1759inline double AddRowCount(double c1, double c2) {
1760 // If one is undefined, use the other, as we have nothing else.
1761 if (c1 == kUnknownRowCount) {
1762 return c2;
1763 } else if (c2 == kUnknownRowCount) {
1764 return c1;
1765 } else {
1766 return c1 + c2;
1767 }
1768}
1769
1770// The Mem_root_array must be allocated on a MEM_ROOT that lives at least for as
1771// long as the access path.
1773 THD *thd, Mem_root_array<AppendPathParameters> *children) {
1774 AccessPath *path = new (thd->mem_root) AccessPath;
1775 path->type = AccessPath::APPEND;
1776 path->append().children = children;
1777 double num_output_rows = kUnknownRowCount;
1778 for (const AppendPathParameters &child : *children) {
1779 path->set_cost(AddCost(path->cost(), child.path->cost()));
1780 path->set_init_cost(AddCost(path->init_cost(), child.path->init_cost()));
1781 path->set_init_once_cost(path->init_once_cost() +
1782 child.path->init_once_cost());
1783 num_output_rows =
1784 AddRowCount(num_output_rows, child.path->num_output_rows());
1785 }
1786 path->set_num_output_rows(num_output_rows);
1787 return path;
1788}
1789
1791 Window *window,
1792 Temp_table_param *temp_table_param,
1793 int ref_slice, bool needs_buffering) {
1794 AccessPath *path = new (thd->mem_root) AccessPath;
1795 path->type = AccessPath::WINDOW;
1796 path->window().child = child;
1797 path->window().window = window;
1798 path->window().temp_table = nullptr;
1799 path->window().temp_table_param = temp_table_param;
1800 path->window().ref_slice = ref_slice;
1801 path->window().needs_buffering = needs_buffering;
1802 path->set_num_output_rows(child->num_output_rows());
1803 return path;
1804}
1805
1807 SJ_TMP_TABLE *weedout_table) {
1808 AccessPath *path = new (thd->mem_root) AccessPath;
1809 path->type = AccessPath::WEEDOUT;
1810 path->weedout().child = child;
1811 path->weedout().weedout_table = weedout_table;
1812 path->weedout().tables_to_get_rowid_for =
1813 0; // Must be handled by the caller.
1814 return path;
1815}
1816
1818 THD *thd, AccessPath *child, std::span<Item *> group_items) {
1819 AccessPath *path = new (thd->mem_root) AccessPath;
1821 path->remove_duplicates().child = child;
1822 path->remove_duplicates().group_items() = group_items;
1823 path->has_group_skip_scan = child->has_group_skip_scan;
1824 return path;
1825}
1826
1828 THD *thd, AccessPath *child, TABLE *table, KEY *key,
1829 unsigned loosescan_key_len) {
1830 AccessPath *path = new (thd->mem_root) AccessPath;
1832 path->remove_duplicates_on_index().child = child;
1833 path->remove_duplicates_on_index().table = table;
1834 path->remove_duplicates_on_index().key = key;
1835 path->remove_duplicates_on_index().loosescan_key_len = loosescan_key_len;
1836 path->has_group_skip_scan = child->has_group_skip_scan;
1837 return path;
1838}
1839
1841 AccessPath *table_scan_path,
1842 Index_lookup *used_ref) {
1843 AccessPath *path = new (thd->mem_root) AccessPath;
1845 path->alternative().table_scan_path = table_scan_path;
1846 path->alternative().child = child;
1847 path->alternative().used_ref = used_ref;
1848 return path;
1849}
1850
1852 const char *name) {
1853 AccessPath *path = new (thd->mem_root) AccessPath;
1855 path->cache_invalidator().child = child;
1856 path->cache_invalidator().name = name;
1857 return path;
1858}
1859
1862 table_map immediate_tables);
1863
1865 table_map update_tables,
1866 table_map immediate_tables);
1867
1868/**
1869 Modifies "path" and the paths below it so that they provide row IDs for
1870 all tables.
1871
1872 This also figures out how the row IDs should be retrieved for each table in
1873 the input to the path. If the handler of the table is positioned on the
1874 correct row while reading the input, handler::position() can be called to get
1875 the row ID from the handler. However, if the input iterator returns rows
1876 without keeping the position of the underlying handlers in sync, calling
1877 handler::position() will not be able to provide the row IDs. Specifically,
1878 hash join and BKA join do not keep the underlying handlers positioned on the
1879 right row. Therefore, this function will instruct every hash join or BKA join
1880 below "path" to maintain row IDs in the join buffer, and updating handler::ref
1881 in every input table for each row they return. Then "path" does not need to
1882 call handler::position() to get it (nor should it, since calling it would
1883 overwrite the correct row ID with a stale one).
1884
1885 The tables on which "path" should call handler::position() are stored in a
1886 `tables_to_get_rowid_for` bitset in "path". For all the other tables, it can
1887 assume that handler::ref already contains the correct row ID.
1888 */
1890
1893 bool eligible_for_batch_mode);
1894
1895// A short form of CreateIteratorFromAccessPath() that implicitly uses the THD's
1896// MEM_ROOT for storage, which is nearly always what you want. (The only caller
1897// that does anything else is DynamicRangeIterator.)
1899 THD *thd, AccessPath *path, JOIN *join, bool eligible_for_batch_mode) {
1901 eligible_for_batch_mode);
1902}
1903
1904void SetCostOnTableAccessPath(const Cost_model_server &cost_model,
1905 const POSITION *pos, bool is_after_filter,
1906 AccessPath *path);
1907
1908/**
1909 Return the TABLE* referred from 'path' if it is a basic access path,
1910 else a nullptr is returned. Temporary tables, such as those used by
1911 sorting, aggregate and subquery materialization are not returned.
1912*/
1914
1915/**
1916 Returns a map of all tables read when `path` or any of its children are
1917 executed. Only iterators that are part of the same query block as `path`
1918 are considered.
1919
1920 If a table is read that doesn't have a map, specifically the temporary
1921 tables made as part of materialization within the same query block,
1922 RAND_TABLE_BIT will be set as a convention and none of that access path's
1923 children will be included in the map. In this case, the caller will need to
1924 manually go in and find said access path, to ask it for its TABLE object.
1925
1926 If include_pruned_tables = true, tables that are hidden under a ZERO_ROWS
1927 access path (ie., pruned away due to impossible join conditions) will be
1928 included in the map. This is normally what you want, as those tables need to
1929 be included whenever you store NULL flags and the likes, but if you don't
1930 want them (perhaps to specifically check for conditions referring to pruned
1931 tables), you can set it to false.
1932 */
1933table_map GetUsedTableMap(const AccessPath *path, bool include_pruned_tables);
1934
1935/**
1936 Find the list of all tables used by this root, stopping at materializations.
1937 Used for knowing which tables to sort.
1938 */
1940
1941/**
1942 For each access path in the (sub)tree rooted at “path”, expand any use of
1943 “filter_predicates” into newly-inserted FILTER access paths, using the given
1944 predicate list. This is used after finding an optimal set of access paths,
1945 to normalize the tree so that the remaining consumers do not need to worry
1946 about filter_predicates and cost_before_filter.
1947
1948 “join” is the join that “path” is part of.
1949 */
1951 const Mem_root_array<Predicate> &predicates,
1952 unsigned num_where_predicates);
1953
1954/**
1955 Extracts the Item expression from the given “filter_predicates” corresponding
1956 to the given “mask”.
1957 */
1960 int num_where_predicates);
1961
1962/// Like ExpandFilterAccessPaths(), but expands only the single access path
1963/// at “path”.
1965 const Mem_root_array<Predicate> &predicates,
1966 unsigned num_where_predicates);
1967
1968/**
1969 Clear all the bits representing filter predicates in a bitset, and keep only
1970 the bits representing applied sargable join conditions.
1971
1972 See AccessPath::filter_predicates and
1973 AccessPath::applied_sargable_join_predicates() for details about how filter
1974 predicates and applied sargable join predicates are stored in different
1975 partitions of the same bitset.
1976
1977 @param predicates A bitset representing both filter predicates and applied
1978 sargable join predicates.
1979 @param num_where_predicates The number of filter predicates.
1980 @param mem_root The root on which to allocate memory, if needed.
1981
1982 @return A copy of "predicates" with only the bits for applied sargable join
1983 predicates set.
1984 */
1986 int num_where_predicates,
1988
1989/// Returns the tables that are part of a hash join.
1991
1992/**
1993 Get the conditions to put into the extra conditions of the HashJoinIterator.
1994 This includes the non-equijoin conditions, as well as any equijoin conditions
1995 on columns that are too big to include in the hash table. (The old optimizer
1996 handles equijoin conditions on long columns elsewhere, so the last part only
1997 applies to the hypergraph optimizer.)
1998
1999 @param mem_root The root on which to allocate memory, if needed.
2000 @param using_hypergraph_optimizer True if using the hypergraph optimizer.
2001 @param equijoin_conditions All the equijoin conditions of the join.
2002 @param other_conditions All the non-equijoin conditions of the join.
2003
2004 @return All the conditions to evaluate as "extra conditions" in
2005 HashJoinIterator, or nullptr on OOM.
2006 */
2008 MEM_ROOT *mem_root, bool using_hypergraph_optimizer,
2009 const std::vector<HashJoinCondition> &equijoin_conditions,
2010 const Mem_root_array<Item *> &other_conditions);
2011
2012/**
2013 Update status variables which count how many scans of various types are used
2014 in a query plan.
2015
2016 The following status variables are updated: Select_scan, Select_full_join,
2017 Select_range, Select_full_range_join, Select_range_check. They are also stored
2018 as performance schema statement events with the same names.
2019
2020 In addition, the performance schema statement events NO_INDEX_USED and
2021 NO_GOOD_INDEX_USED are updated, if appropriate.
2022 */
2023void CollectStatusVariables(THD *thd, const JOIN *top_join,
2024 const AccessPath &top_path);
2025
2026#endif // SQL_JOIN_OPTIMIZER_ACCESS_PATH_H
constexpr double kUnknownCost
To indicate that a cost estimate is not yet made.
Definition: access_path.h:201
AccessPath * NewStreamingAccessPath(THD *thd, AccessPath *child, JOIN *join, Temp_table_param *temp_table_param, TABLE *table, int ref_slice)
Definition: access_path.h:1650
AccessPath * NewInvalidatorAccessPath(THD *thd, AccessPath *child, const char *name)
Definition: access_path.h:1851
AccessPath * NewRemoveDuplicatesAccessPath(THD *thd, AccessPath *child, std::span< Item * > group_items)
Definition: access_path.h:1817
AccessPath * NewRefAccessPath(THD *thd, TABLE *table, Index_lookup *ref, bool use_order, bool reverse, bool count_examined_rows)
Definition: access_path.h:1399
AccessPath * NewDeleteRowsAccessPath(THD *thd, AccessPath *child, table_map delete_tables, table_map immediate_tables)
Definition: access_path.cc:122
void CopyBasicProperties(const AccessPath &from, AccessPath *to)
Definition: access_path.h:1353
void ExpandSingleFilterAccessPath(THD *thd, AccessPath *path, const JOIN *join, 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:1565
AccessPath * NewFullTextSearchAccessPath(THD *thd, TABLE *table, Index_lookup *ref, Item_func_match *ft_func, bool use_order, bool use_limit, bool count_examined_rows)
Definition: access_path.h:1448
double AddRowCount(double c1, double c2)
Add row counts c1 and c2, but handle kUnknownRowCount correctly.
Definition: access_path.h:1759
AccessPath * NewUpdateRowsAccessPath(THD *thd, AccessPath *child, table_map update_tables, table_map immediate_tables)
Definition: access_path.cc:134
table_map GetHashJoinTables(AccessPath *path)
Returns the tables that are part of a hash join.
Definition: access_path.cc:1698
AccessPath * NewDynamicIndexRangeScanAccessPath(THD *thd, TABLE *table, QEP_TAB *qep_tab, bool count_examined_rows)
Definition: access_path.h:1502
AccessPath * NewMaterializeAccessPath(THD *thd, Mem_root_array< MaterializePathParameters::Operand > operands, 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, MaterializePathParameters::DedupType dedup_reason=MaterializePathParameters::NO_DEDUP)
Definition: access_path.h:1683
AccessPath * NewZeroRowsAggregatedAccessPath(THD *thd, const char *cause)
Definition: access_path.h:1639
AccessPath * NewAlternativeAccessPath(THD *thd, AccessPath *child, AccessPath *table_scan_path, Index_lookup *used_ref)
Definition: access_path.h:1840
AccessPath * NewMRRAccessPath(THD *thd, TABLE *table, Index_lookup *ref, int mrr_flags)
Definition: access_path.h:1479
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 executed.
Definition: access_path.cc:272
AccessPath * NewAppendAccessPath(THD *thd, Mem_root_array< AppendPathParameters > *children)
Definition: access_path.h:1772
AccessPath * NewNestedLoopSemiJoinWithDuplicateRemovalAccessPath(THD *thd, AccessPath *outer, AccessPath *inner, const TABLE *table, KEY *key, size_t key_len)
Definition: access_path.h:1532
void CollectStatusVariables(THD *thd, const JOIN *top_join, const AccessPath &top_path)
Update status variables which count how many scans of various types are used in a query plan.
Definition: access_path.cc:1712
AccessPath * NewTemptableAggregateAccessPath(THD *thd, AccessPath *subquery_path, JOIN *join, Temp_table_param *temp_table_param, TABLE *table, AccessPath *table_path, int ref_slice)
Definition: access_path.h:1573
AccessPath * NewRemoveDuplicatesOnIndexAccessPath(THD *thd, AccessPath *child, TABLE *table, KEY *key, unsigned loosescan_key_len)
Definition: access_path.h:1827
AccessPath * NewFakeSingleRowAccessPath(THD *thd, bool count_examined_rows)
Definition: access_path.h:1608
AccessPath * NewTableValueConstructorAccessPath(const THD *thd, const JOIN *join)
Definition: access_path.cc:166
Item * ConditionFromFilterPredicates(const Mem_root_array< Predicate > &predicates, OverflowBitset mask, int num_where_predicates)
Extracts the Item expression from the given “filter_predicates” corresponding to the given “mask”.
Definition: access_path.cc:1554
AccessPath * NewFilterAccessPath(THD *thd, AccessPath *child, Item *condition)
Definition: access_path.h:1547
constexpr double kUnknownRowCount
To indicate that a row estimate is not yet made.
Definition: access_path.h:196
AccessPath * NewSortAccessPath(THD *thd, AccessPath *child, Filesort *filesort, ORDER *order, bool count_examined_rows)
Definition: access_path.cc:87
AccessPath * NewMaterializedTableFunctionAccessPath(THD *thd, TABLE *table, Table_function *table_function, AccessPath *table_path)
Definition: access_path.h:1512
const Mem_root_array< Item * > * GetExtraHashJoinConditions(MEM_ROOT *mem_root, bool using_hypergraph_optimizer, const std::vector< HashJoinCondition > &equijoin_conditions, const Mem_root_array< Item * > &other_conditions)
Get the conditions to put into the extra conditions of the HashJoinIterator.
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:303
AccessPath * NewTableScanAccessPath(THD *thd, TABLE *table, bool count_examined_rows)
Definition: access_path.h:1366
AccessPath * NewSampleScanAccessPath(THD *thd, TABLE *table, double sampling_percentage, bool count_examined_rows)
Definition: access_path.h:1375
AccessPath * NewAggregateAccessPath(THD *thd, AccessPath *child, olap_type olap)
Definition: access_path.h:1563
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:1677
double AddCost(double c1, double c2)
Add path costs c1 and c2, but handle kUnknownCost correctly.
Definition: access_path.h:1747
AccessPath * NewMaterializeInformationSchemaTableAccessPath(THD *thd, AccessPath *table_path, Table_ref *table_list, Item *condition)
Definition: access_path.h:1736
void FindTablesToGetRowidFor(AccessPath *path)
Modifies "path" and the paths below it so that they provide row IDs for all tables.
Definition: access_path.cc:1390
TABLE * GetBasicTable(const AccessPath *path)
Return the TABLE* referred from 'path' if it is a basic access path, else a nullptr is returned.
Definition: access_path.cc:215
AccessPath * NewRefOrNullAccessPath(THD *thd, TABLE *table, Index_lookup *ref, bool use_order, bool count_examined_rows)
Definition: access_path.h:1412
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:1588
AccessPath * NewEQRefAccessPath(THD *thd, TABLE *table, Index_lookup *ref, bool count_examined_rows)
Definition: access_path.h:1424
AccessPath * NewWindowAccessPath(THD *thd, AccessPath *child, Window *window, Temp_table_param *temp_table_param, int ref_slice, bool needs_buffering)
Definition: access_path.h:1790
double FirstRowCost(double init_cost, double total_cost, double output_rows)
Calculate the cost of reading the first row from an access path, given estimates for init cost,...
Definition: access_path.h:205
AccessPath * NewFollowTailAccessPath(THD *thd, TABLE *table, bool count_examined_rows)
Definition: access_path.h:1493
AccessPath * NewConstTableAccessPath(THD *thd, TABLE *table, Index_lookup *ref, bool count_examined_rows)
Definition: access_path.h:1464
MutableOverflowBitset ClearFilterPredicates(OverflowBitset predicates, int num_where_predicates, MEM_ROOT *mem_root)
Clear all the bits representing filter predicates in a bitset, and keep only the bits representing ap...
Definition: access_path.cc:1689
unique_ptr_destroy_only< RowIterator > CreateIteratorFromAccessPath(THD *thd, MEM_ROOT *mem_root, AccessPath *path, JOIN *join, bool eligible_for_batch_mode)
Definition: access_path.cc:539
AccessPath * NewWeedoutAccessPath(THD *thd, AccessPath *child, SJ_TMP_TABLE *weedout_table)
Definition: access_path.h:1806
AccessPath * NewPushedJoinRefAccessPath(THD *thd, TABLE *table, Index_lookup *ref, bool use_order, bool is_unique, bool count_examined_rows)
Definition: access_path.h:1434
AccessPath * NewZeroRowsAccessPath(THD *thd, AccessPath *child, const char *cause)
Definition: access_path.h:1620
AccessPath * NewUnqualifiedCountAccessPath(THD *thd)
Definition: access_path.h:1523
AccessPath * NewIndexScanAccessPath(THD *thd, TABLE *table, int idx, bool use_order, bool reverse, bool count_examined_rows)
Definition: access_path.h:1386
Mem_root_array< MaterializePathParameters::Operand > SingleMaterializeQueryBlock(THD *thd, AccessPath *path, int select_number, JOIN *join, bool copy_items, Temp_table_param *temp_table_param)
Definition: access_path.h:1668
After parsing, a Common Table Expression is accessed through a Table_ref.
Definition: table.h:4538
API for getting cost estimates for server operations that are not directly related to a table object.
Definition: opt_costmodel.h:54
Sorting related info.
Definition: filesort.h:52
A class that represents a join condition in a hash join.
Definition: item_cmpfunc.h:87
Definition: item_func.h:3536
Base class that is used to represent any kind of expression in a relational query.
Definition: item.h:927
Definition: sql_optimizer.h:133
Definition: key.h:113
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:432
Definition: overflow_bitset.h:179
Definition: overflow_bitset.h:81
Definition: sql_executor.h:256
Definition: range_optimizer.h:69
This class represents a query expression (one query block or several query blocks combined with UNION...
Definition: sql_lex.h:643
A context for reading through a single table using a chosen access method: index read,...
Definition: row_iterator.h:82
Definition: sql_executor.h:95
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_lexer_thd.h:36
MEM_ROOT * mem_root
Definition: sql_lexer_thd.h:40
Class representing a table function.
Definition: table_function.h:53
Definition: table.h:2931
Object containing parameters used when creating and using temporary tables.
Definition: temp_table_param.h:97
Represents the (explicit) window of a SQL 2003 section 7.11 <window clause>, or the implicit (inlined...
Definition: window.h:110
static MEM_ROOT mem_root
Definition: client_plugin.cc:114
void EstimateLimitOffsetCost(AccessPath *path)
Estimate the costs and row count for a WINDOW AccessPath.
Definition: cost_model.cc:1607
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:367
void SetCostOnTableAccessPath(const Cost_model_server &cost_model, const POSITION *pos, bool is_after_filter, AccessPath *path)
Definition: sql_executor.cc:2009
std::bitset< kMaxSupportedFDs > FunctionalDependencySet
Definition: interesting_orders_defs.h:63
JoinType
Definition: join_type.h:28
unsigned char byte
Blob class.
Definition: common.h:151
static mi_bit_type mask[]
Definition: mi_packrec.cc:141
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...
std::unique_ptr< T, Destroy_only< T > > unique_ptr_destroy_only
std::unique_ptr, but only destroying.
Definition: my_alloc.h:480
This file includes constants used by all storage engines.
my_off_t ha_rows
Definition: my_base.h:1217
#define HA_POS_ERROR
Definition: my_base.h:1219
uint64_t table_map
Definition: my_table_map.h:30
static char * path
Definition: mysqldump.cc:150
static PFS_engine_table_share_proxy table
Definition: pfs.cc:61
PT & ref(PT *tp)
Definition: tablespace_impl.cc:359
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:40
ValueType value(const std::optional< ValueType > &v)
Definition: gtid.h:83
RangeReverse< Range > reverse(Range &x)
Iterate over a range in reverse.
Definition: utilities.h:132
std::string join(const detail::range auto &rng, std::string_view delim)
join elements of a range into a string separated by a delimiter.
Definition: string.h:74
int delete_tables(PFS_engine_table_share_proxy **, unsigned int) noexcept
Definition: pfs_plugin_table_v1_all_empty.cc:39
olap_type
Definition: olap.h:31
OverflowBitset is a fixed-size (once allocated) bitmap that is optimized for the common case of few e...
required string key
Definition: replication_asynchronous_connection_failover.proto:60
case opt name
Definition: sslopt-case.h:29
Access paths are a query planning structure that correspond 1:1 to iterators, in that an access path ...
Definition: access_path.h:238
struct AccessPath::@68::@93 zero_rows_aggregated
auto & weedout()
Definition: access_path.h:853
auto & filter()
Definition: access_path.h:773
bool count_all_rows
Definition: access_path.h:1243
AccessPath * bka_path
Definition: access_path.h:1012
auto & ref_or_null()
Definition: access_path.h:581
auto & materialized_table_function()
Definition: access_path.h:693
AccessPath * cpk_child
Definition: access_path.h:1073
auto & rowid_union()
Definition: access_path.h:661
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:529
const auto & bka_join() const
Definition: access_path.h:753
TABLE * temp_table
Definition: access_path.h:1283
struct AccessPath::@68::@101 temptable_aggregate
OverflowBitset equijoin_predicates
Definition: access_path.h:1183
struct AccessPath::@68::@71 index_scan
double rescan_cost() const
Return the cost of scanning the given path for the second time (or later) in the given query block.
Definition: access_path.h:440
struct AccessPath::@68::@78 const_table
auto & materialize()
Definition: access_path.h:821
const auto & temptable_aggregate() const
Definition: access_path.h:801
OverflowBitset & subsumed_sargable_join_predicates()
Similar to applied_sargable_join_predicates, bitmap of sargable join predicates that have been applie...
Definition: access_path.h:501
auto & index_scan()
Definition: access_path.h:557
const auto & delete_rows() const
Definition: access_path.h:897
const auto & filter() const
Definition: access_path.h:777
const auto & index_distance_scan() const
Definition: access_path.h:569
auto & delete_rows()
Definition: access_path.h:893
bool reuse_handler
Definition: access_path.h:1050
KEY_PART * used_key_part
Definition: access_path.h:1024
double m_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:932
olap_type olap
Definition: access_path.h:1229
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:481
Item * condition
Definition: access_path.h:1201
const auto & index_merge() const
Definition: access_path.h:649
const auto & update_rows() const
Definition: access_path.h:905
double subquery_rows
The number of materialized rows (as opposed to the number of rows fetched by table_path).
Definition: access_path.h:1270
enum AccessPath::Type type
auto & alternative()
Definition: access_path.h:877
auto & pushed_join_ref()
Definition: access_path.h:597
void set_cost(double val)
Definition: access_path.h:410
AccessPath * outer
Definition: access_path.h:1157
struct AccessPath::@68::@80 follow_tail
struct AccessPath::@68::@79 mrr
std::span< Item * > ItemSpan
Definition: access_path.h:1294
auto & index_skip_scan()
Definition: access_path.h:669
bool rewrite_semi_to_inner
Definition: access_path.h:1161
const auto & zero_rows_aggregated() const
Definition: access_path.h:737
auto & group_index_skip_scan()
Definition: access_path.h:677
struct AccessPath::@68::@94 hash_join
const auto & eq_ref() const
Definition: access_path.h:593
bool use_order
Definition: access_path.h:968
struct AccessPath::@68::@103 stream
bool pfs_batch_mode
Definition: access_path.h:1175
auto & temptable_aggregate()
Definition: access_path.h:797
struct AccessPath::@68::@90 table_value_constructor
GroupIndexSkipScanParameters * param
Definition: access_path.h:1117
auto & rowid_intersection()
Definition: access_path.h:653
double init_cost() const
Definition: access_path.h:399
bool materialize_subqueries
Definition: access_path.h:1211
AccessPath * child
Definition: access_path.h:1145
bool allow_spill_to_disk
Definition: access_path.h:1159
Index_lookup * used_ref
Definition: access_path.h:1325
auto & mrr()
Definition: access_path.h:621
std::byte m_group_items[sizeof(ItemSpan)]
Definition: access_path.h:1312
auto & sample_scan()
Definition: access_path.h:549
const auto & index_scan() const
Definition: access_path.h:561
const auto & fake_single_row() const
Definition: access_path.h:721
bool reject_multiple_rows
Definition: access_path.h:1244
bool allow_clustered_primary_key_scan
Definition: access_path.h:1065
const char * name
Definition: access_path.h:1329
bool use_limit
Definition: access_path.h:1002
Window * window
Definition: access_path.h:1282
table_map tables_to_get_rowid_for
Definition: access_path.h:1162
auto & materialize_information_schema_table()
Definition: access_path.h:829
auto & bka_join()
Definition: access_path.h:749
const auto & follow_tail() const
Definition: access_path.h:633
SJ_TMP_TABLE * weedout_table
Definition: access_path.h:1290
bool has_group_skip_scan
Whether this access path contains a GROUP_INDEX_SKIP_SCAN.
Definition: access_path.h:334
Index_lookup * ref
Definition: access_path.h:979
const auto & window() const
Definition: access_path.h:849
void set_init_once_cost(double val)
Definition: access_path.h:422
const auto & materialized_table_function() const
Definition: access_path.h:697
auto & unqualified_count()
Definition: access_path.h:701
bool keep_current_rowid
Definition: access_path.h:1014
bool using_extended_key_parts
Definition: access_path.h:1060
auto & nested_loop_join()
Definition: access_path.h:757
const auto & full_text_search() const
Definition: access_path.h:609
struct AccessPath::@68::@98 filter
struct AccessPath::@68::@102 limit_offset
bool can_be_used_for_ror
Definition: access_path.h:1040
float rec_per_key
Definition: access_path.h:1168
Safety safe_for_rowid
Whether it is safe to get row IDs (for sorting) from this access path.
Definition: access_path.h:325
struct AccessPath::@68::@112 cache_invalidator
struct AccessPath::@68::@104 materialize
JOIN * join
Definition: access_path.h:1233
struct AccessPath::@68::@111 alternative
struct AccessPath::@68::@87 dynamic_index_range_scan
unsigned index
Definition: access_path.h:1036
unsigned mrr_buf_size
Definition: access_path.h:1032
auto & remove_duplicates()
Definition: access_path.h:861
RowIterator * iterator
If an iterator has been instantiated for this access path, points to the iterator.
Definition: access_path.h:395
struct AccessPath::@68::@95 bka_join
const auto & stream() const
Definition: access_path.h:817
const auto & remove_duplicates() const
Definition: access_path.h:865
struct AccessPath::@68::@83 rowid_intersection
auto & window()
Definition: access_path.h:845
bool need_rows_in_rowid_order
Definition: access_path.h:1044
Table_ref * table_list
Definition: access_path.h:1274
const auto & unqualified_count() const
Definition: access_path.h:705
void * secondary_engine_data
Auxiliary data used by a secondary storage engine while processing the access path during optimizatio...
Definition: access_path.h:538
struct AccessPath::@68::@108 weedout
void set_init_cost(double val)
Definition: access_path.h:416
void set_num_output_rows(double val)
Definition: access_path.h:912
bool is_covering
Definition: access_path.h:1093
const auto & mrr() const
Definition: access_path.h:625
struct AccessPath::@68::@82 index_merge
void set_cost_before_filter(double val)
Definition: access_path.h:428
bool remove_duplicates
Definition: access_path.h:1223
table_map tables_to_update
Definition: access_path.h:1338
const auto & table_value_constructor() const
Definition: access_path.h:713
KEY * key
Definition: access_path.h:1195
struct AccessPath::@68::@113 delete_rows
struct AccessPath::@68::@89 unqualified_count
auto & table_value_constructor()
Definition: access_path.h:709
auto & stream()
Definition: access_path.h:813
size_t key_len
Definition: access_path.h:1196
const OverflowBitset & subsumed_sargable_join_predicates() const
Definition: access_path.h:504
const auto & zero_rows() const
Definition: access_path.h:729
const auto & append() const
Definition: access_path.h:841
ha_rows offset
Definition: access_path.h:1242
int idx
Definition: access_path.h:967
auto & hash_join()
Definition: access_path.h:741
auto & cache_invalidator()
Definition: access_path.h:885
bool force_sort_rowids
Definition: access_path.h:1225
unsigned num_used_key_parts
Definition: access_path.h:1037
struct AccessPath::@68::@77 full_text_search
unsigned num_ranges
Definition: access_path.h:1029
ORDER * order
Definition: access_path.h:1221
auto & sort()
Definition: access_path.h:781
auto & fake_single_row()
Definition: access_path.h:717
ha_rows limit
Definition: access_path.h:1222
auto & follow_tail()
Definition: access_path.h:629
double m_num_output_rows
Expected number of output rows.
Definition: access_path.h:920
const auto & sample_scan() const
Definition: access_path.h:553
const JoinPredicate * join_predicate
Definition: access_path.h:1158
const auto & const_table() const
Definition: access_path.h:617
struct AccessPath::@68::@92 zero_rows
const auto & dynamic_index_range_scan() const
Definition: access_path.h:689
const auto & table_scan() const
Definition: access_path.h:545
struct AccessPath::@68::@76 pushed_join_ref
unsigned mrr_flags
Definition: access_path.h:1031
int ref_slice
Definition: access_path.h:1237
struct AccessPath::@68::@110 remove_duplicates_on_index
OverflowBitset filter_predicates
Bitmap of WHERE predicates that we are including on this access path, referring to the “predicates” a...
Definition: access_path.h:465
bool can_be_used_for_imerge
Definition: access_path.h:1047
bool forced_by_hint
Definition: access_path.h:1064
struct AccessPath::@68::@106 append
auto & limit_offset()
Definition: access_path.h:805
AccessPath * inner
Definition: access_path.h:1157
QUICK_RANGE * range
Definition: access_path.h:974
bool provide_rowid
Definition: access_path.h:1254
const auto & index_range_scan() const
Definition: access_path.h:641
const auto & ref() const
Definition: access_path.h:577
bool forced_by_dbug
Whether this access path is forced preferred over all others by means of a SET DEBUG force_subplan_0x...
Definition: access_path.h:339
Item_func_match * ft_func
Definition: access_path.h:1003
struct AccessPath::@68::@75 eq_ref
ha_rows * send_records_override
Definition: access_path.h:1247
auto & table_scan()
Definition: access_path.h:541
const auto & hash_join() const
Definition: access_path.h:745
QEP_TAB * qep_tab
Definition: access_path.h:1121
struct AccessPath::@68::@72 index_distance_scan
Table_function * table_function
Definition: access_path.h:1125
auto & zero_rows_aggregated()
Definition: access_path.h:733
const auto & sort() const
Definition: access_path.h:785
bool unwrap_rollup
Definition: access_path.h:1224
Type
Definition: access_path.h:239
@ FOLLOW_TAIL
Definition: access_path.h:254
@ FILTER
Definition: access_path.h:278
@ PUSHED_JOIN_REF
Definition: access_path.h:250
@ ZERO_ROWS_AGGREGATED
Definition: access_path.h:267
@ UPDATE_ROWS
Definition: access_path.h:296
@ AGGREGATE
Definition: access_path.h:280
@ BKA_JOIN
Definition: access_path.h:274
@ ZERO_ROWS
Definition: access_path.h:266
@ CONST_TABLE
Definition: access_path.h:252
@ GROUP_INDEX_SKIP_SCAN
Definition: access_path.h:260
@ SAMPLE_SCAN
Definition: access_path.h:244
@ INDEX_RANGE_SCAN
Definition: access_path.h:255
@ UNQUALIFIED_COUNT
Definition: access_path.h:269
@ EQ_REF
Definition: access_path.h:249
@ FAKE_SINGLE_ROW
Definition: access_path.h:265
@ MATERIALIZE_INFORMATION_SCHEMA_TABLE
Definition: access_path.h:285
@ WINDOW
Definition: access_path.h:287
@ REF_OR_NULL
Definition: access_path.h:248
@ MATERIALIZE
Definition: access_path.h:284
@ NESTED_LOOP_SEMIJOIN_WITH_DUPLICATE_REMOVAL
Definition: access_path.h:273
@ ROWID_UNION
Definition: access_path.h:258
@ INDEX_SKIP_SCAN
Definition: access_path.h:259
@ MRR
Definition: access_path.h:253
@ CACHE_INVALIDATOR
Definition: access_path.h:292
@ INDEX_SCAN
Definition: access_path.h:245
@ TABLE_VALUE_CONSTRUCTOR
Definition: access_path.h:264
@ WEEDOUT
Definition: access_path.h:288
@ MATERIALIZED_TABLE_FUNCTION
Definition: access_path.h:268
@ REMOVE_DUPLICATES_ON_INDEX
Definition: access_path.h:290
@ TABLE_SCAN
Definition: access_path.h:243
@ REF
Definition: access_path.h:247
@ TEMPTABLE_AGGREGATE
Definition: access_path.h:281
@ LIMIT_OFFSET
Definition: access_path.h:282
@ APPEND
Definition: access_path.h:286
@ NESTED_LOOP_JOIN
Definition: access_path.h:272
@ INDEX_MERGE
Definition: access_path.h:256
@ FULL_TEXT_SEARCH
Definition: access_path.h:251
@ ALTERNATIVE
Definition: access_path.h:291
@ STREAM
Definition: access_path.h:283
@ REMOVE_DUPLICATES
Definition: access_path.h:289
@ ROWID_INTERSECTION
Definition: access_path.h:257
@ DYNAMIC_INDEX_RANGE_SCAN
Definition: access_path.h:261
@ DELETE_ROWS
Definition: access_path.h:295
@ SORT
Definition: access_path.h:279
@ INDEX_DISTANCE_SCAN
Definition: access_path.h:246
@ HASH_JOIN
Definition: access_path.h:275
bool retrieve_full_rows
Definition: access_path.h:1076
double m_init_once_cost
Of init_cost, how much of the initialization needs only to be done once per query block.
Definition: access_path.h:944
const auto & rowid_union() const
Definition: access_path.h:665
const TABLE * table
Definition: access_path.h:1194
struct AccessPath::@68::@114 update_rows
const auto & index_skip_scan() const
Definition: access_path.h:673
auto & dynamic_index_range_scan()
Definition: access_path.h:685
const auto & pushed_join_ref() const
Definition: access_path.h:601
auto & remove_duplicates_on_index()
Definition: access_path.h:869
table_map immediate_tables
Definition: access_path.h:1334
struct AccessPath::@68::@100 aggregate
double m_cost_before_filter
If no filter, identical to cost.
Definition: access_path.h:948
double cost() const
Definition: access_path.h:397
int mrr_flags
Definition: access_path.h:1013
struct AccessPath::@68::@105 materialize_information_schema_table
struct AccessPath::@68::@74 ref_or_null
struct AccessPath::@68::@86 group_index_skip_scan
auto & full_text_search()
Definition: access_path.h:605
const auto & materialize() const
Definition: access_path.h:825
int ordering_state
Which ordering the rows produced by this path follow, if any (see interesting_orders....
Definition: access_path.h:389
auto & eq_ref()
Definition: access_path.h:589
struct AccessPath::@68::@81 index_range_scan
JoinType join_type
Definition: access_path.h:1166
const auto & limit_offset() const
Definition: access_path.h:809
MaterializePathParameters * param
Definition: access_path.h:1265
const char * cause
Definition: access_path.h:1148
struct AccessPath::@68::@84 rowid_union
struct AccessPath::@68::@85 index_skip_scan
auto & update_rows()
Definition: access_path.h:901
auto & index_merge()
Definition: access_path.h:645
auto & aggregate()
Definition: access_path.h:789
struct AccessPath::@68::@91 fake_single_row
double m_cost
Expected cost to read all of this access path once.
Definition: access_path.h:923
const auto & group_index_skip_scan() const
Definition: access_path.h:681
auto & zero_rows()
Definition: access_path.h:725
AccessPath * subquery_path
Definition: access_path.h:1232
Mem_root_array< AppendPathParameters > * children
Definition: access_path.h:1278
struct AccessPath::@68::@97 nested_loop_semijoin_with_duplicate_removal
const auto & nested_loop_join() const
Definition: access_path.h:761
bool already_expanded_predicates
Definition: access_path.h:1176
const auto & remove_duplicates_on_index() const
Definition: access_path.h:873
Temp_table_param * temp_table_param
Definition: access_path.h:1234
auto & nested_loop_semijoin_with_duplicate_removal()
Definition: access_path.h:765
bool reverse
Definition: access_path.h:969
AccessPath * table_scan_path
Definition: access_path.h:1321
enum tablesample_type sampling_type
Definition: access_path.h:963
const auto & materialize_information_schema_table() const
Definition: access_path.h:833
union AccessPath::@68 u
double subquery_cost
The total cost of executing the queries that we materialize.
Definition: access_path.h:1267
bool geometry
Definition: access_path.h:1053
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:331
unsigned loosescan_key_len
Definition: access_path.h:1318
auto & index_distance_scan()
Definition: access_path.h:565
auto & ref()
Definition: access_path.h:573
double first_row_cost() const
The cost of reading the first row.
Definition: access_path.h:402
table_map tables_to_delete_from
Definition: access_path.h:1333
double init_once_cost() const
Definition: access_path.h:406
IndexSkipScanParameters * param
Definition: access_path.h:1108
const OverflowBitset & applied_sargable_join_predicates() const
Definition: access_path.h:484
Mem_root_array< AccessPath * > * children
Definition: access_path.h:1066
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:493
AccessPath * table_path
Definition: access_path.h:1126
const auto & aggregate() const
Definition: access_path.h:793
TABLE * table
Definition: access_path.h:958
auto & append()
Definition: access_path.h:837
double cost_before_filter() const
Definition: access_path.h:408
const auto & weedout() const
Definition: access_path.h:857
const auto & cache_invalidator() const
Definition: access_path.h:889
double sampling_percentage
Definition: access_path.h:962
struct AccessPath::@68::@99 sort
bool needs_buffering
Definition: access_path.h:1286
int8_t immediate_update_delete_table
For UPDATE and DELETE statements: The node index of a table which can be updated or deleted from imme...
Definition: access_path.h:383
QUICK_RANGE ** ranges
Definition: access_path.h:1028
bool is_unique
Definition: access_path.h:996
const auto & alternative() const
Definition: access_path.h:881
Safety
A general enum to describe the safety of a given operation.
Definition: access_path.h:306
@ 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:315
@ UNSAFE
The given operation is unsafe on this access path, no matter how many or few times it's scanned.
Definition: access_path.h:321
@ SAFE
The given operation is always safe on this access path.
Definition: access_path.h:308
auto & const_table()
Definition: access_path.h:613
struct AccessPath::@68::@96 nested_loop_join
unsigned mrr_length_per_rec
Definition: access_path.h:1167
const auto & rowid_intersection() const
Definition: access_path.h:657
Mem_root_array< Item_values_column * > * output_refs
Definition: access_path.h:1132
auto & index_range_scan()
Definition: access_path.h:637
double num_output_rows() const
Definition: access_path.h:910
double num_output_rows_before_filter
If no filter, identical to num_output_rows.
Definition: access_path.h:443
struct AccessPath::@68::@70 sample_scan
const auto & ref_or_null() const
Definition: access_path.h:585
Filesort * filesort
Definition: access_path.h:1215
struct AccessPath::@68::@88 materialized_table_function
struct AccessPath::@68::@69 table_scan
bool store_rowids
Definition: access_path.h:1160
const auto & nested_loop_semijoin_with_duplicate_removal() const
Definition: access_path.h:769
Definition: access_path.h:190
JOIN * join
Definition: access_path.h:192
AccessPath * path
Definition: access_path.h:191
Definition: group_index_skip_scan_plan.h:45
Logically a part of AccessPath::index_skip_scan(), but is too large, so split out into its own struct...
Definition: index_skip_scan_plan.h:73
Structure used for index-based lookups.
Definition: sql_opt_exec_shared.h:67
A specification that two specific relational expressions (e.g., two tables, or a table and a join bet...
Definition: access_path.h:80
FunctionalDependencySet functional_dependencies
Definition: access_path.h:97
Mem_root_array< int > functional_dependencies_idx
Definition: access_path.h:102
RelationalExpression * expr
Definition: access_path.h:81
double selectivity
Definition: access_path.h:82
int ordering_idx_needed_for_semijoin_rewrite
Definition: access_path.h:120
std::span< Item * > semijoin_group
Definition: access_path.h:125
size_t estimated_bytes_per_row
Definition: access_path.h:86
Definition: range_optimizer.h:55
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:83
Definition: materialize_path_parameters.h:42
AccessPath * subquery_path
Definition: materialize_path_parameters.h:43
int select_number
Definition: materialize_path_parameters.h:44
JOIN * join
Definition: materialize_path_parameters.h:45
bool copy_items
Definition: materialize_path_parameters.h:47
Temp_table_param * temp_table_param
Definition: materialize_path_parameters.h:48
bool disable_deduplication_by_hash_field
Definition: materialize_path_parameters.h:46
Definition: materialize_path_parameters.h:40
bool rematerialize
True if rematerializing on every Init() call (e.g., because we have a dependency on a value from outs...
Definition: materialize_path_parameters.h:80
DedupType deduplication_reason
Definition: materialize_path_parameters.h:111
Mem_root_array< Operand > m_operands
Definition: materialize_path_parameters.h:58
Common_table_expr * cte
If materializing a CTE, points to it (see m_cte), otherwise nullptr.
Definition: materialize_path_parameters.h:65
DedupType
The context for which deduplication is being used.
Definition: materialize_path_parameters.h:106
@ NO_DEDUP
Definition: materialize_path_parameters.h:109
bool reject_multiple_rows
True if this is the top level iterator for a materialized derived table transformed from a scalar sub...
Definition: materialize_path_parameters.h:99
ha_rows limit_rows
Used for when pushing LIMIT down to MaterializeIterator; this is more efficient than having a LimitOf...
Definition: materialize_path_parameters.h:92
TABLE * table
Handle to table to materialize into.
Definition: materialize_path_parameters.h:62
int ref_slice
Definition: materialize_path_parameters.h:74
Query_expression * unit
The query expression we are materializing.
Definition: materialize_path_parameters.h:68
Mem_root_array< const AccessPath * > * invalidators
Definition: materialize_path_parameters.h:59
Definition: table.h:298
A position of table within a join order.
Definition: sql_select.h:355
A filter of some sort that is not a join condition (those are stored in JoinPredicate objects).
Definition: access_path.h:133
hypergraph::NodeMap total_eligibility_set
Definition: access_path.h:146
bool was_join_condition
Definition: access_path.h:159
Mem_root_array< int > functional_dependencies_idx
Definition: access_path.h:182
bool possibly_null_complemented_later
Definition: access_path.h:170
FunctionalDependencySet functional_dependencies
Definition: access_path.h:181
int source_multiple_equality_idx
Definition: access_path.h:178
hypergraph::NodeMap used_nodes
Definition: access_path.h:137
Item * condition
Definition: access_path.h:134
double selectivity
Definition: access_path.h:148
Mem_root_array< ContainedSubquery > contained_subqueries
Definition: access_path.h:187
Represents an expression tree in the relational algebra of joins.
Definition: relational_expression.h:147
Definition: table.h:1433
tablesample_type
Definition: tablesample.h:27