MySQL 8.4.0
Source Code Documentation
Go to the documentation of this file.
1/* Copyright (c) 2020, 2024, Oracle and/or its affiliates.
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.
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.
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 GNU General Public License, version 2.0, for more details.
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 */
27#include <assert.h>
29#include <algorithm>
30#include <array>
31#include <cstddef>
32#include <string>
33#include <unordered_map>
34#include <utility>
36#include "map_helpers.h"
37#include "my_table_map.h"
38#include "sql/item.h"
44#include "sql/mem_root_array.h"
45#include "sql/sql_const.h"
47class CompanionSet;
48class Field;
49class JOIN;
50class Query_block;
51class THD;
52struct MEM_ROOT;
54struct TABLE;
57 A sargable (from “Search ARGument”) predicate is one that we can attempt
58 to push down into an index (what we'd call “ref access” or “index range
59 scan”/“quick”). This structure denotes one such instance, precomputed from
60 all the predicates in the given hypergraph.
61 */
63 // Index into the “predicates” array in the graph.
66 // The predicate is assumed to be <field> = <other_side>.
67 // Later, we could push down other kinds of relations, such as
68 // greater-than.
72 /// True if it is safe to evaluate "other_side" during optimization. It must
73 /// be constant during execution. Also, it should not contain subqueries or
74 /// stored procedures, which we do not want to execute during optimization.
79 A struct containing a join hypergraph of a single query block, encapsulating
80 the constraints given by the relational expressions (e.g. inner joins are
81 more freely reorderable than outer joins).
83 Since the Hypergraph class does not carry any payloads for nodes and edges,
84 and we need to associate e.g. TABLE pointers with each node, we store our
85 extra data in “nodes” and “edges”, indexed the same way the hypergraph is
86 indexed.
87 */
90 : graph(mem_root),
99 /// Flags set when AccessPaths are proposed to secondary engines for costing.
100 /// The intention of these flags is to avoid traversing the AccessPath tree to
101 /// check for certain criteria.
102 /// TODO (tikoldit) Move to JOIN or Secondary_engine_execution_context, so
103 /// that JoinHypergraph can be immutable during planning
106 // Maps table->tableno() to an index in “nodes”, also suitable for
107 // a bit index in a NodeMap. This is normally the identity mapping,
108 // except for when scalar-to-derived conversion is active.
109 std::array<int, MAX_TABLES> table_num_to_node_num;
111 class Node final {
112 public:
114 : m_table{table},
118 assert(mem_root != nullptr);
119 assert(table != nullptr);
120 }
122 TABLE *table() const { return m_table; }
123 const CompanionSet *companion_set() const { return m_companion_set; }
125 void AddSargable(const SargablePredicate &predicate) {
126 assert(predicate.predicate_index >= 0);
127 assert(predicate.field != nullptr);
128 assert(predicate.other_side != nullptr);
129 m_sargable_predicates.push_back(predicate);
130 }
134 }
136 void AddPushable(Item *cond) {
137 // Don't add duplicate conditions, as this causes their selectivity to
138 // be applied multiple times, giving poor row estimates (cf.
139 // bug#36135001).
140 if (std::none_of(m_pushable_conditions.cbegin(),
141 m_pushable_conditions.cend(), [&](const Item *other) {
142 return ItemsAreEqual(cond, other, true);
143 })) {
144 m_pushable_conditions.push_back(cond);
145 }
146 }
150 }
154 }
157 m_lateral_dependencies = dependencies;
158 }
160 private:
163 // List of all sargable predicates (see SargablePredicate) where
164 // the field is part of this table. When we see the node for
165 // the first time, we will evaluate all of these and consider
166 // creating access paths that exploit these predicates.
169 // Join conditions that are potentially pushable to this node
170 // as sargable predicates (if they are sargable, they will be
171 // added to sargable_predicates below, together with sargable
172 // non-join conditions). This is a verbatim copy of
173 // the m_pushable_conditions member in RelationalExpression,
174 // which is computed as a side effect during join pushdown.
175 // (We could in principle have gone and collected all join conditions
176 // ourselves when determining sargable conditions, but there would be
177 // a fair amount of duplicated code in determining pushability,
178 // which is why regular join pushdown does the computation.)
181 // The lateral dependencies of this table. That is, the set of tables that
182 // must be available on the outer side of a nested loop join in which this
183 // table is on the inner side. This map may be set for LATERAL derived
184 // tables and derived tables with outer references, and for table functions.
186 };
189 // Note that graph.edges contain each edge twice (see Hypergraph
190 // for more information), so edges[i] corresponds to graph.edges[i*2].
193 // The first <num_where_predicates> are WHERE predicates;
194 // the rest are sargable join predicates. The latter are in the array
195 // solely so they can be part of the regular “applied_filters” bitmap
196 // if they are pushed down into an index, so that we know that we
197 // don't need to apply them as join conditions later.
202 // A bitmap over predicates that are, or contain, at least one
203 // materializable subquery.
206 /// Returns a pointer to the query block that is being planned.
207 const Query_block *query_block() const { return m_query_block; }
209 /// Returns a pointer to the JOIN object of the query block being planned.
210 const JOIN *join() const;
212 /// Whether, at any point, we could rewrite (t1 LEFT JOIN t2) LEFT JOIN t3
213 /// to t1 LEFT JOIN (t2 LEFT JOIN t3) or vice versa. We record this purely to
214 /// note that we have a known bug/inconsistency in row count estimation
215 /// in this case. Bug #33550360 has a test case, but to sum up:
216 /// Assume t1 and t3 has 25 rows, but t2 has zero rows, and selectivities
217 /// are 0.1. As long as we clamp the row count in FindOutputRowsForJoin(),
218 /// and do not modify these selectivities somehow, the former would give
219 /// 62.5 rows, and the second would give 25 rows. This should be fixed
220 /// eventually, but for now, at least we register it, so that we do not
221 /// assert-fail on inconsistent row counts if this (known) issue could be
222 /// the root cause.
225 /// The set of tables that are on the inner side of some outer join or
226 /// antijoin. If a table is not part of this set, and it is found to be empty,
227 /// we can assume that the result of the top-level join will also be empty.
230 int FindSargableJoinPredicate(const Item *predicate) const {
231 const auto iter = m_sargable_join_predicates.find(predicate);
232 return iter == m_sargable_join_predicates.cend() ? -1 : iter->second;
233 }
235 void AddSargableJoinPredicate(const Item *predicate, int position) {
236 m_sargable_join_predicates.emplace(predicate, position);
237 }
239 private:
240 // For each sargable join condition, maps into its index in “predicates”.
241 // We need the predicate index when applying the join to figure out whether
242 // we have already applied the predicate or not; see
243 // {applied,subsumed}_sargable_join_predicates in AccessPath.
246 /// A pointer to the query block being planned.
251 Make a join hypergraph from the query block given by “graph->query_block”,
252 converting from MySQL's join list structures to the ones expected
253 by the hypergraph join optimizer. This includes pushdown of WHERE
254 predicates, and detection of conditions suitable for hash join.
255 However, it does not include simplification of outer to inner joins;
256 that is presumed to have happened earlier.
258 The result is suitable for running DPhyp (subgraph_enumeration.h)
259 to find optimal join planning.
260 */
261bool MakeJoinHypergraph(THD *thd, JoinHypergraph *graph,
262 bool *where_is_always_false);
264// Exposed for testing only.
266 JoinHypergraph *graph);
270 const std::array<int, MAX_TABLES> &table_num_to_node_num);
272std::string PrintDottyHypergraph(const JoinHypergraph &graph);
274/// Estimates the size of the hash join keys generated from the equi-join
275/// predicates in "expr".
RelationalExpression objects in the same companion set are those that are inner-joined against each o...
Definition: relational_expression.h:78
Definition: field.h:575
Base class that is used to represent any kind of expression in a relational query.
Definition: item.h:934
Definition: sql_optimizer.h:133
Definition: make_join_hypergraph.h:111
void AddSargable(const SargablePredicate &predicate)
Definition: make_join_hypergraph.h:125
const Mem_root_array< SargablePredicate > & sargable_predicates() const
Definition: make_join_hypergraph.h:132
TABLE * m_table
Definition: make_join_hypergraph.h:161
Mem_root_array< SargablePredicate > m_sargable_predicates
Definition: make_join_hypergraph.h:167
Mem_root_array< Item * > m_pushable_conditions
Definition: make_join_hypergraph.h:179
hypergraph::NodeMap lateral_dependencies() const
Definition: make_join_hypergraph.h:152
const Mem_root_array< Item * > & pushable_conditions() const
Definition: make_join_hypergraph.h:148
hypergraph::NodeMap m_lateral_dependencies
Definition: make_join_hypergraph.h:185
Node(MEM_ROOT *mem_root, TABLE *table, const CompanionSet *companion_set)
Definition: make_join_hypergraph.h:113
const CompanionSet * m_companion_set
Definition: make_join_hypergraph.h:162
const CompanionSet * companion_set() const
Definition: make_join_hypergraph.h:123
void AddPushable(Item *cond)
Definition: make_join_hypergraph.h:136
TABLE * table() const
Definition: make_join_hypergraph.h:122
void set_lateral_dependencies(hypergraph::NodeMap dependencies)
Definition: make_join_hypergraph.h:156
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:426
Definition: overflow_bitset.h:78
This class represents a query block, aka a query specification, which is a query consisting of a SELE...
Definition: sql_lex.h:1163
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_lexer_thd.h:36
std::unordered_map, but allocated on a MEM_ROOT.
Definition: map_helpers.h:291
static MEM_ROOT mem_root
Definition of an undirected (join) hypergraph.
bool MakeJoinHypergraph(THD *thd, JoinHypergraph *graph, bool *where_is_always_false)
Make a join hypergraph from the query block given by “graph->query_block”, converting from MySQL's jo...
hypergraph::NodeMap GetNodeMapFromTableMap(table_map table_map, const std::array< int, MAX_TABLES > &table_num_to_node_num)
std::string PrintDottyHypergraph(const JoinHypergraph &graph)
For the given hypergraph, make a textual representation in the form of a dotty graph.
void MakeJoinGraphFromRelationalExpression(THD *thd, RelationalExpression *expr, JoinHypergraph *graph)
Convert a join rooted at “expr” into a join hypergraph that encapsulates the constraints given by the...
table_map GetVisibleTables(const RelationalExpression *expr)
size_t EstimateHashJoinKeyWidth(const RelationalExpression *expr)
Estimates the size of the hash join keys generated from the equi-join predicates in "expr".
uint64_t table_map
Definition: my_table_map.h:30
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
OverflowBitset is a fixed-size (once allocated) bitmap that is optimized for the common case of few e...
For updating an AccessPath's costs by a secondary engine, i.e.
uint64_t SecondaryEngineCostingFlags
Definition: secondary_engine_costing_flags.h:39
File containing constants that can be used throughout the server.
A struct containing a join hypergraph of a single query block, encapsulating the constraints given by...
Definition: make_join_hypergraph.h:88
unsigned num_where_predicates
Definition: make_join_hypergraph.h:200
Mem_root_array< Node > nodes
Definition: make_join_hypergraph.h:187
table_map tables_inner_to_outer_or_anti
The set of tables that are on the inner side of some outer join or antijoin.
Definition: make_join_hypergraph.h:228
bool has_reordered_left_joins
Whether, at any point, we could rewrite (t1 LEFT JOIN t2) LEFT JOIN t3 to t1 LEFT JOIN (t2 LEFT JOIN ...
Definition: make_join_hypergraph.h:223
void AddSargableJoinPredicate(const Item *predicate, int position)
Definition: make_join_hypergraph.h:235
hypergraph::Hypergraph graph
Definition: make_join_hypergraph.h:97
const Query_block * query_block() const
Returns a pointer to the query block that is being planned.
Definition: make_join_hypergraph.h:207
JoinHypergraph(MEM_ROOT *mem_root, const Query_block *query_block)
Definition: make_join_hypergraph.h:89
const JOIN * join() const
Returns a pointer to the JOIN object of the query block being planned.
const Query_block * m_query_block
A pointer to the query block being planned.
Definition: make_join_hypergraph.h:247
Mem_root_array< Predicate > predicates
Definition: make_join_hypergraph.h:198
int FindSargableJoinPredicate(const Item *predicate) const
Definition: make_join_hypergraph.h:230
OverflowBitset materializable_predicates
Definition: make_join_hypergraph.h:204
SecondaryEngineCostingFlags secondary_engine_costing_flags
Flags set when AccessPaths are proposed to secondary engines for costing.
Definition: make_join_hypergraph.h:104
mem_root_unordered_map< const Item *, int > m_sargable_join_predicates
Definition: make_join_hypergraph.h:244
std::array< int, MAX_TABLES > table_num_to_node_num
Definition: make_join_hypergraph.h:109
Mem_root_array< JoinPredicate > edges
Definition: make_join_hypergraph.h:191
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:83
Represents an expression tree in the relational algebra of joins.
Definition: relational_expression.h:145
A sargable (from “Search ARGument”) predicate is one that we can attempt to push down into an index (...
Definition: make_join_hypergraph.h:62
int predicate_index
Definition: make_join_hypergraph.h:64
Field * field
Definition: make_join_hypergraph.h:69
Item * other_side
Definition: make_join_hypergraph.h:70
bool can_evaluate
True if it is safe to evaluate "other_side" during optimization.
Definition: make_join_hypergraph.h:75
Definition: table.h:1405
Definition: hypergraph.h:90