MySQL 8.0.29
Source Code Documentation
make_join_hypergraph.h
Go to the documentation of this file.
1/* Copyright (c) 2020, 2021, 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"
32#include "sql/mem_root_array.h"
33#include "sql/sql_const.h"
34
35class Field;
36class Item;
37class JOIN;
38class Query_block;
39class THD;
40struct MEM_ROOT;
41struct TABLE;
42
43/**
44 A sargable (from “Search ARGument”) predicate is one that we can attempt
45 to push down into an index (what we'd call “ref access” or “index range
46 scan”/“quick”). This structure denotes one such instance, precomputed from
47 all the predicates in the given hypergraph.
48 */
50 // Index into the “predicates” array in the graph.
52
53 // The predicate is assumed to be <field> = <other_side>.
54 // Later, we could push down other kinds of relations, such as
55 // greater-than.
58};
59
60/**
61 A struct containing a join hypergraph of a single query block, encapsulating
62 the constraints given by the relational expressions (e.g. inner joins are
63 more freely reorderable than outer joins).
64
65 Since the Hypergraph class does not carry any payloads for nodes and edges,
66 and we need to associate e.g. TABLE pointers with each node, we store our
67 extra data in “nodes” and “edges”, indexed the same way the hypergraph is
68 indexed.
69 */
72 : nodes(mem_root),
77
79
80 // Maps table->tableno() to an index in “nodes”, also suitable for
81 // a bit index in a NodeMap. This is normally the identity mapping,
82 // except for when scalar-to-derived conversion is active.
83 std::array<int, MAX_TABLES> table_num_to_node_num;
84
85 struct Node {
87
88 // Join conditions that are potentially pushable to this node
89 // as sargable predicates (if they are sargable, they will be
90 // added to sargable_predicates below, together with sargable
91 // non-join conditions). This is a verbatim copy of
92 // the join_conditions_pushable_to_this member in RelationalExpression,
93 // which is computed as a side effect during join pushdown.
94 // (We could in principle have gone and collected all join conditions
95 // ourselves when determining sargable conditions, but there would be
96 // a fair amount of duplicated code in determining pushability,
97 // which is why regular join pushdown does the computation.)
99
100 // List of all sargable predicates (see SargablePredicate) where
101 // the field is part of this table. When we see the node for
102 // the first time, we will evaluate all of these and consider
103 // creating access paths that exploit these predicates.
105 };
107
108 // Note that graph.edges contain each edge twice (see Hypergraph
109 // for more information), so edges[i] corresponds to graph.edges[i*2].
111
112 // The first <num_where_predicates> are WHERE predicates;
113 // the rest are sargable join predicates. The latter are in the array
114 // solely so they can be part of the regular “applied_filters” bitmap
115 // if they are pushed down into an index, so that we know that we
116 // don't need to apply them as join conditions later.
118
120
121 // A bitmap over predicates that are, or contain, at least one
122 // materializable subquery.
124
125 // For each sargable join condition, maps into its index in “predicates”.
126 // We need the predicate index when applying the join to figure out whether
127 // we have already applied the predicate or not; see
128 // {applied,subsumed}_sargable_join_predicates in AccessPath.
130
131 /// Returns a pointer to the query block that is being planned.
132 const Query_block *query_block() const { return m_query_block; }
133
134 /// Returns a pointer to the JOIN object of the query block being planned.
135 const JOIN *join() const;
136
137 /// Whether, at any point, we could rewrite (t1 LEFT JOIN t2) LEFT JOIN t3
138 /// to t1 LEFT JOIN (t2 LEFT JOIN t3) or vice versa. We record this purely to
139 /// note that we have a known bug/inconsistency in row count estimation
140 /// in this case. Bug #33550360 has a test case, but to sum up:
141 /// Assume t1 and t3 has 25 rows, but t2 has zero rows, and selectivities
142 /// are 0.1. As long as we clamp the row count in FindOutputRowsForJoin(),
143 /// and do not modify these selectivities somehow, the former would give
144 /// 62.5 rows, and the second would give 25 rows. This should be fixed
145 /// eventually, but for now, at least we register it, so that we do not
146 /// assert-fail on inconsistent row counts if this (known) issue could be
147 /// the root cause.
149
150 private:
151 /// A pointer to the query block being planned.
153};
154
155/**
156 Make a join hypergraph from the query block given by “graph->query_block”,
157 converting from MySQL's join list structures to the ones expected
158 by the hypergraph join optimizer. This includes pushdown of WHERE
159 predicates, and detection of conditions suitable for hash join.
160 However, it does not include simplification of outer to inner joins;
161 that is presumed to have happened earlier.
162
163 The result is suitable for running DPhyp (subgraph_enumeration.h)
164 to find optimal join planning.
165 */
166bool MakeJoinHypergraph(THD *thd, std::string *trace, JoinHypergraph *graph);
167
168// Exposed for testing only.
170 std::string *trace,
171 JoinHypergraph *graph);
172
175 const std::array<int, MAX_TABLES> &table_num_to_node_num);
176
177std::string PrintDottyHypergraph(const JoinHypergraph &graph);
178
179#endif // SQL_JOIN_OPTIMIZER_MAKE_JOIN_HYPERGRAPH
Definition: field.h:573
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:421
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:1124
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_class.h:945
std::unordered_map, but allocated on a MEM_ROOT.
Definition: map_helpers.h:280
static MEM_ROOT mem_root
Definition: client_plugin.cc:109
Definition of an undirected (join) hypergraph.
hypergraph::NodeMap GetNodeMapFromTableMap(table_map table_map, const std::array< int, MAX_TABLES > &table_num_to_node_num)
bool MakeJoinHypergraph(THD *thd, std::string *trace, JoinHypergraph *graph)
Make a join hypergraph from the query block given by “graph->query_block”, converting from MySQL's jo...
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:2280
void MakeJoinGraphFromRelationalExpression(THD *thd, RelationalExpression *expr, std::string *trace, JoinHypergraph *graph)
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
File containing constants that can be used throughout the server.
Definition: make_join_hypergraph.h:85
TABLE * table
Definition: make_join_hypergraph.h:86
Mem_root_array< SargablePredicate > sargable_predicates
Definition: make_join_hypergraph.h:104
Mem_root_array< Item * > join_conditions_pushable_to_this
Definition: make_join_hypergraph.h:98
A struct containing a join hypergraph of a single query block, encapsulating the constraints given by...
Definition: make_join_hypergraph.h:70
unsigned num_where_predicates
Definition: make_join_hypergraph.h:119
Mem_root_array< Node > nodes
Definition: make_join_hypergraph.h:106
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:148
hypergraph::Hypergraph graph
Definition: make_join_hypergraph.h:78
mem_root_unordered_map< Item *, int > sargable_join_predicates
Definition: make_join_hypergraph.h:129
const Query_block * query_block() const
Returns a pointer to the query block that is being planned.
Definition: make_join_hypergraph.h:132
JoinHypergraph(MEM_ROOT *mem_root, const Query_block *query_block)
Definition: make_join_hypergraph.h:71
const JOIN * join() const
Returns a pointer to the JOIN object of the query block being planned.
Definition: make_join_hypergraph.cc:3118
const Query_block * m_query_block
A pointer to the query block being planned.
Definition: make_join_hypergraph.h:152
Mem_root_array< Predicate > predicates
Definition: make_join_hypergraph.h:117
OverflowBitset materializable_predicates
Definition: make_join_hypergraph.h:123
std::array< int, MAX_TABLES > table_num_to_node_num
Definition: make_join_hypergraph.h:83
Mem_root_array< JoinPredicate > edges
Definition: make_join_hypergraph.h:110
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:49
int predicate_index
Definition: make_join_hypergraph.h:51
Field * field
Definition: make_join_hypergraph.h:56
Item * other_side
Definition: make_join_hypergraph.h:57
Definition: table.h:1394
Definition: hypergraph.h:85