MySQL 8.1.0
Source Code Documentation
Go to the documentation of this file.
1/* Copyright (c) 2020, 2023, 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 also distributed with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have included with MySQL.
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 GNU General Public License, version 2.0, for more details.
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
26#include <array>
27#include <string>
29#include "map_helpers.h"
33#include "sql/mem_root_array.h"
34#include "sql/sql_const.h"
36class CompanionSet;
37class Field;
38class Item;
39class JOIN;
40class Query_block;
41class THD;
42struct MEM_ROOT;
43struct TABLE;
46 A sargable (from “Search ARGument”) predicate is one that we can attempt
47 to push down into an index (what we'd call “ref access” or “index range
48 scan”/“quick”). This structure denotes one such instance, precomputed from
49 all the predicates in the given hypergraph.
50 */
52 // Index into the “predicates” array in the graph.
55 // The predicate is assumed to be <field> = <other_side>.
56 // Later, we could push down other kinds of relations, such as
57 // greater-than.
61 /// True if it is safe to evaluate "other_side" during optimization. It must
62 /// be constant during execution. Also, it should not contain subqueries or
63 /// stored procedures, which we do not want to execute during optimization.
68 A struct containing a join hypergraph of a single query block, encapsulating
69 the constraints given by the relational expressions (e.g. inner joins are
70 more freely reorderable than outer joins).
72 Since the Hypergraph class does not carry any payloads for nodes and edges,
73 and we need to associate e.g. TABLE pointers with each node, we store our
74 extra data in “nodes” and “edges”, indexed the same way the hypergraph is
75 indexed.
76 */
79 : graph(mem_root),
88 /// Flags set when AccessPaths are proposed to secondary engines for costing.
89 /// The intention of these flags is to avoid traversing the AccessPath tree to
90 /// check for certain criteria.
91 /// TODO (tikoldit) Move to JOIN or Secondary_engine_execution_context, so
92 /// that JoinHypergraph can be immutable during planning
95 // Maps table->tableno() to an index in “nodes”, also suitable for
96 // a bit index in a NodeMap. This is normally the identity mapping,
97 // except for when scalar-to-derived conversion is active.
98 std::array<int, MAX_TABLES> table_num_to_node_num;
100 struct Node {
103 // Join conditions that are potentially pushable to this node
104 // as sargable predicates (if they are sargable, they will be
105 // added to sargable_predicates below, together with sargable
106 // non-join conditions). This is a verbatim copy of
107 // the join_conditions_pushable_to_this member in RelationalExpression,
108 // which is computed as a side effect during join pushdown.
109 // (We could in principle have gone and collected all join conditions
110 // ourselves when determining sargable conditions, but there would be
111 // a fair amount of duplicated code in determining pushability,
112 // which is why regular join pushdown does the computation.)
115 // List of all sargable predicates (see SargablePredicate) where
116 // the field is part of this table. When we see the node for
117 // the first time, we will evaluate all of these and consider
118 // creating access paths that exploit these predicates.
122 };
125 // Note that graph.edges contain each edge twice (see Hypergraph
126 // for more information), so edges[i] corresponds to graph.edges[i*2].
129 // The first <num_where_predicates> are WHERE predicates;
130 // the rest are sargable join predicates. The latter are in the array
131 // solely so they can be part of the regular “applied_filters” bitmap
132 // if they are pushed down into an index, so that we know that we
133 // don't need to apply them as join conditions later.
138 // A bitmap over predicates that are, or contain, at least one
139 // materializable subquery.
142 // For each sargable join condition, maps into its index in “predicates”.
143 // We need the predicate index when applying the join to figure out whether
144 // we have already applied the predicate or not; see
145 // {applied,subsumed}_sargable_join_predicates in AccessPath.
148 /// Returns a pointer to the query block that is being planned.
149 const Query_block *query_block() const { return m_query_block; }
151 /// Returns a pointer to the JOIN object of the query block being planned.
152 const JOIN *join() const;
154 /// Whether, at any point, we could rewrite (t1 LEFT JOIN t2) LEFT JOIN t3
155 /// to t1 LEFT JOIN (t2 LEFT JOIN t3) or vice versa. We record this purely to
156 /// note that we have a known bug/inconsistency in row count estimation
157 /// in this case. Bug #33550360 has a test case, but to sum up:
158 /// Assume t1 and t3 has 25 rows, but t2 has zero rows, and selectivities
159 /// are 0.1. As long as we clamp the row count in FindOutputRowsForJoin(),
160 /// and do not modify these selectivities somehow, the former would give
161 /// 62.5 rows, and the second would give 25 rows. This should be fixed
162 /// eventually, but for now, at least we register it, so that we do not
163 /// assert-fail on inconsistent row counts if this (known) issue could be
164 /// the root cause.
167 /// The set of tables that are on the inner side of some outer join or
168 /// antijoin. If a table is not part of this set, and it is found to be empty,
169 /// we can assume that the result of the top-level join will also be empty.
172 private:
173 /// A pointer to the query block being planned.
178 Make a join hypergraph from the query block given by “graph->query_block”,
179 converting from MySQL's join list structures to the ones expected
180 by the hypergraph join optimizer. This includes pushdown of WHERE
181 predicates, and detection of conditions suitable for hash join.
182 However, it does not include simplification of outer to inner joins;
183 that is presumed to have happened earlier.
185 The result is suitable for running DPhyp (subgraph_enumeration.h)
186 to find optimal join planning.
187 */
188bool MakeJoinHypergraph(THD *thd, std::string *trace, JoinHypergraph *graph,
189 bool *where_is_always_false);
191// Exposed for testing only.
193 std::string *trace,
194 JoinHypergraph *graph);
198 const std::array<int, MAX_TABLES> &table_num_to_node_num);
200std::string PrintDottyHypergraph(const JoinHypergraph &graph);
202/// Estimates the size of the hash join keys generated from the equi-join
203/// predicates in "expr".
RelationalExpression objects in the same companion set are those that are inner-joined against each o...
Definition: relational_expression.h:77
Definition: field.h:575
Base class that is used to represent any kind of expression in a relational query.
Definition: item.h:853
Definition: sql_optimizer.h:132
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:425
Definition: overflow_bitset.h:76
This class represents a query block, aka a query specification, which is a query consisting of a SELE...
Definition: sql_lex.h:1162
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_lexer_thd.h:33
std::unordered_map, but allocated on a MEM_ROOT.
Definition: map_helpers.h:281
static MEM_ROOT mem_root
Definition of an undirected (join) hypergraph.
bool MakeJoinHypergraph(THD *thd, std::string *trace, 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, std::string *trace, JoinHypergraph *graph)
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:29
uint64_t NodeMap
Since our graphs can never have more than 61 tables, node sets and edge lists are implemented using 6...
Definition: node_map.h:39
For updating an AccessPath's costs by a secondary engine, i.e.
uint64_t SecondaryEngineCostingFlags
Definition: secondary_engine_costing_flags.h:38
File containing constants that can be used throughout the server.
Definition: make_join_hypergraph.h:100
const CompanionSet * companion_set
Definition: make_join_hypergraph.h:121
TABLE * table
Definition: make_join_hypergraph.h:101
Mem_root_array< SargablePredicate > sargable_predicates
Definition: make_join_hypergraph.h:119
Mem_root_array< Item * > join_conditions_pushable_to_this
Definition: make_join_hypergraph.h:113
A struct containing a join hypergraph of a single query block, encapsulating the constraints given by...
Definition: make_join_hypergraph.h:77
unsigned num_where_predicates
Definition: make_join_hypergraph.h:136
Mem_root_array< Node > nodes
Definition: make_join_hypergraph.h:123
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:170
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:165
hypergraph::Hypergraph graph
Definition: make_join_hypergraph.h:86
mem_root_unordered_map< Item *, int > sargable_join_predicates
Definition: make_join_hypergraph.h:146
const Query_block * query_block() const
Returns a pointer to the query block that is being planned.
Definition: make_join_hypergraph.h:149
JoinHypergraph(MEM_ROOT *mem_root, const Query_block *query_block)
Definition: make_join_hypergraph.h:78
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:174
Mem_root_array< Predicate > predicates
Definition: make_join_hypergraph.h:134
OverflowBitset materializable_predicates
Definition: make_join_hypergraph.h:140
SecondaryEngineCostingFlags secondary_engine_costing_flags
Flags set when AccessPaths are proposed to secondary engines for costing.
Definition: make_join_hypergraph.h:93
std::array< int, MAX_TABLES > table_num_to_node_num
Definition: make_join_hypergraph.h:98
Mem_root_array< JoinPredicate > edges
Definition: make_join_hypergraph.h:127
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:82
Represents an expression tree in the relational algebra of joins.
Definition: relational_expression.h:144
A sargable (from “Search ARGument”) predicate is one that we can attempt to push down into an index (...
Definition: make_join_hypergraph.h:51
int predicate_index
Definition: make_join_hypergraph.h:53
Field * field
Definition: make_join_hypergraph.h:58
Item * other_side
Definition: make_join_hypergraph.h:59
bool can_evaluate
True if it is safe to evaluate "other_side" during optimization.
Definition: make_join_hypergraph.h:64
Definition: table.h:1394
Definition: hypergraph.h:88