MySQL 8.0.31
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
61/**
62 A struct containing a join hypergraph of a single query block, encapsulating
63 the constraints given by the relational expressions (e.g. inner joins are
64 more freely reorderable than outer joins).
65
66 Since the Hypergraph class does not carry any payloads for nodes and edges,
67 and we need to associate e.g. TABLE pointers with each node, we store our
68 extra data in “nodes” and “edges”, indexed the same way the hypergraph is
69 indexed.
70 */
73 : nodes(mem_root),
78
80
81 /// Flags set when AccessPaths are proposed to secondary engines for costing.
82 /// The intention of these flags is to avoid traversing the AccessPath tree to
83 /// check for certain criteria.
84 /// TODO (tikoldit) Move to JOIN or Secondary_engine_execution_context, so
85 /// that JoinHypergraph can be immutable during planning
87
88 // Maps table->tableno() to an index in “nodes”, also suitable for
89 // a bit index in a NodeMap. This is normally the identity mapping,
90 // except for when scalar-to-derived conversion is active.
91 std::array<int, MAX_TABLES> table_num_to_node_num;
92
93 struct Node {
95
96 // Join conditions that are potentially pushable to this node
97 // as sargable predicates (if they are sargable, they will be
98 // added to sargable_predicates below, together with sargable
99 // non-join conditions). This is a verbatim copy of
100 // the join_conditions_pushable_to_this member in RelationalExpression,
101 // which is computed as a side effect during join pushdown.
102 // (We could in principle have gone and collected all join conditions
103 // ourselves when determining sargable conditions, but there would be
104 // a fair amount of duplicated code in determining pushability,
105 // which is why regular join pushdown does the computation.)
107
108 // List of all sargable predicates (see SargablePredicate) where
109 // the field is part of this table. When we see the node for
110 // the first time, we will evaluate all of these and consider
111 // creating access paths that exploit these predicates.
113 };
115
116 // Note that graph.edges contain each edge twice (see Hypergraph
117 // for more information), so edges[i] corresponds to graph.edges[i*2].
119
120 // The first <num_where_predicates> are WHERE predicates;
121 // the rest are sargable join predicates. The latter are in the array
122 // solely so they can be part of the regular “applied_filters” bitmap
123 // if they are pushed down into an index, so that we know that we
124 // don't need to apply them as join conditions later.
126
128
129 // A bitmap over predicates that are, or contain, at least one
130 // materializable subquery.
132
133 // For each sargable join condition, maps into its index in “predicates”.
134 // We need the predicate index when applying the join to figure out whether
135 // we have already applied the predicate or not; see
136 // {applied,subsumed}_sargable_join_predicates in AccessPath.
138
139 /// Returns a pointer to the query block that is being planned.
140 const Query_block *query_block() const { return m_query_block; }
141
142 /// Returns a pointer to the JOIN object of the query block being planned.
143 const JOIN *join() const;
144
145 /// Whether, at any point, we could rewrite (t1 LEFT JOIN t2) LEFT JOIN t3
146 /// to t1 LEFT JOIN (t2 LEFT JOIN t3) or vice versa. We record this purely to
147 /// note that we have a known bug/inconsistency in row count estimation
148 /// in this case. Bug #33550360 has a test case, but to sum up:
149 /// Assume t1 and t3 has 25 rows, but t2 has zero rows, and selectivities
150 /// are 0.1. As long as we clamp the row count in FindOutputRowsForJoin(),
151 /// and do not modify these selectivities somehow, the former would give
152 /// 62.5 rows, and the second would give 25 rows. This should be fixed
153 /// eventually, but for now, at least we register it, so that we do not
154 /// assert-fail on inconsistent row counts if this (known) issue could be
155 /// the root cause.
157
158 /// The set of tables that are on the inner side of some outer join or
159 /// antijoin. If a table is not part of this set, and it is found to be empty,
160 /// we can assume that the result of the top-level join will also be empty.
162
163 private:
164 /// A pointer to the query block being planned.
166};
167
168/**
169 Make a join hypergraph from the query block given by “graph->query_block”,
170 converting from MySQL's join list structures to the ones expected
171 by the hypergraph join optimizer. This includes pushdown of WHERE
172 predicates, and detection of conditions suitable for hash join.
173 However, it does not include simplification of outer to inner joins;
174 that is presumed to have happened earlier.
175
176 The result is suitable for running DPhyp (subgraph_enumeration.h)
177 to find optimal join planning.
178 */
179bool MakeJoinHypergraph(THD *thd, std::string *trace, JoinHypergraph *graph,
180 bool *where_is_always_false);
181
182// Exposed for testing only.
184 std::string *trace,
185 JoinHypergraph *graph);
186
189 const std::array<int, MAX_TABLES> &table_num_to_node_num);
190
191std::string PrintDottyHypergraph(const JoinHypergraph &graph);
192
193/// Estimates the size of the hash join keys generated from the equi-join
194/// predicates in "expr".
196
198
199#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:802
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:1159
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_class.h:922
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:2393
void MakeJoinGraphFromRelationalExpression(THD *thd, RelationalExpression *expr, std::string *trace, JoinHypergraph *graph)
table_map GetVisibleTables(const RelationalExpression *expr)
Definition: make_join_hypergraph.cc:3548
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:2492
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:93
TABLE * table
Definition: make_join_hypergraph.h:94
Mem_root_array< SargablePredicate > sargable_predicates
Definition: make_join_hypergraph.h:112
Mem_root_array< Item * > join_conditions_pushable_to_this
Definition: make_join_hypergraph.h:106
A struct containing a join hypergraph of a single query block, encapsulating the constraints given by...
Definition: make_join_hypergraph.h:71
unsigned num_where_predicates
Definition: make_join_hypergraph.h:127
Mem_root_array< Node > nodes
Definition: make_join_hypergraph.h:114
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:161
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:156
hypergraph::Hypergraph graph
Definition: make_join_hypergraph.h:79
mem_root_unordered_map< Item *, int > sargable_join_predicates
Definition: make_join_hypergraph.h:137
const Query_block * query_block() const
Returns a pointer to the query block that is being planned.
Definition: make_join_hypergraph.h:140
JoinHypergraph(MEM_ROOT *mem_root, const Query_block *query_block)
Definition: make_join_hypergraph.h:72
const JOIN * join() const
Returns a pointer to the JOIN object of the query block being planned.
Definition: make_join_hypergraph.cc:3279
const Query_block * m_query_block
A pointer to the query block being planned.
Definition: make_join_hypergraph.h:165
Mem_root_array< Predicate > predicates
Definition: make_join_hypergraph.h:125
OverflowBitset materializable_predicates
Definition: make_join_hypergraph.h:131
SecondaryEngineCostingFlags secondary_engine_costing_flags
Flags set when AccessPaths are proposed to secondary engines for costing.
Definition: make_join_hypergraph.h:86
std::array< int, MAX_TABLES > table_num_to_node_num
Definition: make_join_hypergraph.h:91
Mem_root_array< JoinPredicate > edges
Definition: make_join_hypergraph.h:118
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:85
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
Field * field
Definition: make_join_hypergraph.h:57
Item * other_side
Definition: make_join_hypergraph.h:58
Definition: table.h:1396
Definition: hypergraph.h:85