MySQL 8.0.32
Source Code Documentation
make_join_hypergraph.h
Go to the documentation of this file.
1/* Copyright (c) 2020, 2022, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is also distributed with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have included with MySQL.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License, version 2.0, for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
22
23#ifndef SQL_JOIN_OPTIMIZER_MAKE_JOIN_HYPERGRAPH
24#define SQL_JOIN_OPTIMIZER_MAKE_JOIN_HYPERGRAPH 1
25
26#include <array>
27#include <string>
28
29#include "map_helpers.h"
33#include "sql/mem_root_array.h"
34#include "sql/sql_const.h"
35
36class Field;
37class Item;
38class JOIN;
39class Query_block;
40class THD;
41struct MEM_ROOT;
42struct TABLE;
43
44/**
45 A sargable (from “Search ARGument”) predicate is one that we can attempt
46 to push down into an index (what we'd call “ref access” or “index range
47 scan”/“quick”). This structure denotes one such instance, precomputed from
48 all the predicates in the given hypergraph.
49 */
51 // Index into the “predicates” array in the graph.
53
54 // The predicate is assumed to be <field> = <other_side>.
55 // Later, we could push down other kinds of relations, such as
56 // greater-than.
59
60 /// True if "other_side" is constant during execution. (And true const; no
61 /// execution of queries or stored procedures during optimization.)
63};
64
65/**
66 A struct containing a join hypergraph of a single query block, encapsulating
67 the constraints given by the relational expressions (e.g. inner joins are
68 more freely reorderable than outer joins).
69
70 Since the Hypergraph class does not carry any payloads for nodes and edges,
71 and we need to associate e.g. TABLE pointers with each node, we store our
72 extra data in “nodes” and “edges”, indexed the same way the hypergraph is
73 indexed.
74 */
77 : graph(mem_root),
83
85
86 /// Flags set when AccessPaths are proposed to secondary engines for costing.
87 /// The intention of these flags is to avoid traversing the AccessPath tree to
88 /// check for certain criteria.
89 /// TODO (tikoldit) Move to JOIN or Secondary_engine_execution_context, so
90 /// that JoinHypergraph can be immutable during planning
92
93 // Maps table->tableno() to an index in “nodes”, also suitable for
94 // a bit index in a NodeMap. This is normally the identity mapping,
95 // except for when scalar-to-derived conversion is active.
96 std::array<int, MAX_TABLES> table_num_to_node_num;
97
98 struct Node {
100
101 // Join conditions that are potentially pushable to this node
102 // as sargable predicates (if they are sargable, they will be
103 // added to sargable_predicates below, together with sargable
104 // non-join conditions). This is a verbatim copy of
105 // the join_conditions_pushable_to_this member in RelationalExpression,
106 // which is computed as a side effect during join pushdown.
107 // (We could in principle have gone and collected all join conditions
108 // ourselves when determining sargable conditions, but there would be
109 // a fair amount of duplicated code in determining pushability,
110 // which is why regular join pushdown does the computation.)
112
113 // List of all sargable predicates (see SargablePredicate) where
114 // the field is part of this table. When we see the node for
115 // the first time, we will evaluate all of these and consider
116 // creating access paths that exploit these predicates.
118 };
120
121 // Note that graph.edges contain each edge twice (see Hypergraph
122 // for more information), so edges[i] corresponds to graph.edges[i*2].
124
125 // The first <num_where_predicates> are WHERE predicates;
126 // the rest are sargable join predicates. The latter are in the array
127 // solely so they can be part of the regular “applied_filters” bitmap
128 // if they are pushed down into an index, so that we know that we
129 // don't need to apply them as join conditions later.
131
133
134 // A bitmap over predicates that are, or contain, at least one
135 // materializable subquery.
137
138 // For each sargable join condition, maps into its index in “predicates”.
139 // We need the predicate index when applying the join to figure out whether
140 // we have already applied the predicate or not; see
141 // {applied,subsumed}_sargable_join_predicates in AccessPath.
143
144 /// Returns a pointer to the query block that is being planned.
145 const Query_block *query_block() const { return m_query_block; }
146
147 /// Returns a pointer to the JOIN object of the query block being planned.
148 const JOIN *join() const;
149
150 /// Whether, at any point, we could rewrite (t1 LEFT JOIN t2) LEFT JOIN t3
151 /// to t1 LEFT JOIN (t2 LEFT JOIN t3) or vice versa. We record this purely to
152 /// note that we have a known bug/inconsistency in row count estimation
153 /// in this case. Bug #33550360 has a test case, but to sum up:
154 /// Assume t1 and t3 has 25 rows, but t2 has zero rows, and selectivities
155 /// are 0.1. As long as we clamp the row count in FindOutputRowsForJoin(),
156 /// and do not modify these selectivities somehow, the former would give
157 /// 62.5 rows, and the second would give 25 rows. This should be fixed
158 /// eventually, but for now, at least we register it, so that we do not
159 /// assert-fail on inconsistent row counts if this (known) issue could be
160 /// the root cause.
162
163 /// The set of tables that are on the inner side of some outer join or
164 /// antijoin. If a table is not part of this set, and it is found to be empty,
165 /// we can assume that the result of the top-level join will also be empty.
167
168 private:
169 /// A pointer to the query block being planned.
171};
172
173/**
174 Make a join hypergraph from the query block given by “graph->query_block”,
175 converting from MySQL's join list structures to the ones expected
176 by the hypergraph join optimizer. This includes pushdown of WHERE
177 predicates, and detection of conditions suitable for hash join.
178 However, it does not include simplification of outer to inner joins;
179 that is presumed to have happened earlier.
180
181 The result is suitable for running DPhyp (subgraph_enumeration.h)
182 to find optimal join planning.
183 */
184bool MakeJoinHypergraph(THD *thd, std::string *trace, JoinHypergraph *graph,
185 bool *where_is_always_false);
186
187// Exposed for testing only.
189 std::string *trace,
190 JoinHypergraph *graph);
191
194 const std::array<int, MAX_TABLES> &table_num_to_node_num);
195
196std::string PrintDottyHypergraph(const JoinHypergraph &graph);
197
198/// Estimates the size of the hash join keys generated from the equi-join
199/// predicates in "expr".
201
203
204#endif // SQL_JOIN_OPTIMIZER_MAKE_JOIN_HYPERGRAPH
Definition: field.h:574
Base class that is used to represent any kind of expression in a relational query.
Definition: item.h:850
Definition: sql_optimizer.h:125
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:1153
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: client_plugin.cc:109
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.
Definition: make_join_hypergraph.cc:2415
void MakeJoinGraphFromRelationalExpression(THD *thd, RelationalExpression *expr, std::string *trace, JoinHypergraph *graph)
table_map GetVisibleTables(const RelationalExpression *expr)
Definition: make_join_hypergraph.cc:3663
size_t EstimateHashJoinKeyWidth(const RelationalExpression *expr)
Estimates the size of the hash join keys generated from the equi-join predicates in "expr".
Definition: make_join_hypergraph.cc:2514
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:98
TABLE * table
Definition: make_join_hypergraph.h:99
Mem_root_array< SargablePredicate > sargable_predicates
Definition: make_join_hypergraph.h:117
Mem_root_array< Item * > join_conditions_pushable_to_this
Definition: make_join_hypergraph.h:111
A struct containing a join hypergraph of a single query block, encapsulating the constraints given by...
Definition: make_join_hypergraph.h:75
unsigned num_where_predicates
Definition: make_join_hypergraph.h:132
Mem_root_array< Node > nodes
Definition: make_join_hypergraph.h:119
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:166
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:161
hypergraph::Hypergraph graph
Definition: make_join_hypergraph.h:84
mem_root_unordered_map< Item *, int > sargable_join_predicates
Definition: make_join_hypergraph.h:142
const Query_block * query_block() const
Returns a pointer to the query block that is being planned.
Definition: make_join_hypergraph.h:145
JoinHypergraph(MEM_ROOT *mem_root, const Query_block *query_block)
Definition: make_join_hypergraph.h:76
const JOIN * join() const
Returns a pointer to the JOIN object of the query block being planned.
Definition: make_join_hypergraph.cc:3415
const Query_block * m_query_block
A pointer to the query block being planned.
Definition: make_join_hypergraph.h:170
Mem_root_array< Predicate > predicates
Definition: make_join_hypergraph.h:130
OverflowBitset materializable_predicates
Definition: make_join_hypergraph.h:136
SecondaryEngineCostingFlags secondary_engine_costing_flags
Flags set when AccessPaths are proposed to secondary engines for costing.
Definition: make_join_hypergraph.h:91
std::array< int, MAX_TABLES > table_num_to_node_num
Definition: make_join_hypergraph.h:96
Mem_root_array< JoinPredicate > edges
Definition: make_join_hypergraph.h:123
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:80
A sargable (from “Search ARGument”) predicate is one that we can attempt to push down into an index (...
Definition: make_join_hypergraph.h:50
int predicate_index
Definition: make_join_hypergraph.h:52
bool is_constant
True if "other_side" is constant during execution.
Definition: make_join_hypergraph.h:62
Field * field
Definition: make_join_hypergraph.h:57
Item * other_side
Definition: make_join_hypergraph.h:58
Definition: table.h:1395
Definition: hypergraph.h:88