MySQL 8.3.0
Source Code Documentation
relational_expression.h
Go to the documentation of this file.
1/* Copyright (c) 2020, 2023, 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_RELATIONAL_EXPRESSION_H
24#define SQL_JOIN_OPTIMIZER_RELATIONAL_EXPRESSION_H
25
26#include <stdint.h>
27
28#include "sql/item.h"
33#include "sql/join_type.h"
34#include "sql/mem_root_array.h"
35#include "sql/sql_class.h"
36
37struct AccessPath;
38class Item_eq_base;
39class Item_func_eq;
40
41// Some information about each predicate that the join optimizer would like to
42// have available in order to avoid computing it anew for each use of that
43// predicate.
47
48 // For equijoins only: A bitmap of which sargable predicates
49 // are part of the same multi-equality as this one (except the
50 // condition itself, which is excluded), and thus are redundant
51 // against it. This is used in AlreadyAppliedThroughSargable()
52 // to quickly find out if we already have applied any of them
53 // as a join condition.
55};
56
57// Describes a rule disallowing specific joins; if any tables from
58// needed_to_activate_rule is part of the join, then _all_ tables from
59// required_nodes must also be present.
60//
61// See FindHyperedgeAndJoinConflicts() for details.
65};
66
67/**
68 RelationalExpression objects in the same companion set are those
69 that are inner-joined against each other; we use this to see in
70 what parts of the graph we allow cycles. (Within companion sets, we
71 are also allowed to add Cartesian products if we deem that an
72 advantage, but we don't do it currently.) Tables may be alone in
73 their companion sets. Companion sets are also used when calculating
74 selectivity for equijoin predicates using multi-field indexes,
75 @see EstimateEqualPredicateSelectivity()).
76*/
77class CompanionSet final {
78 public:
79 CompanionSet() = default;
80
81 explicit CompanionSet(THD *thd) : m_equal_terms(thd->mem_root) {}
82
83 /// No copying.
84 CompanionSet(const CompanionSet &) = delete;
86
87 /// Add the set of equal fields specified by 'func_eq'.
88 void AddEquijoinCondition(THD *thd, const Item_func_eq &eq);
89
90 /**
91 If 'field' is part of an equijoin predicate in this CompanionSet, return a
92 table_map of the tables involved in that predicate. Otherwise, return 0.
93 */
94 table_map GetEqualityMap(const Field &field) const;
95
96 /// For tracing and debugging.
97 /// @returns A string representation like "{{t1.f1, t2.f2}, {t2.f3, t3.f4}}".
98 std::string ToString() const;
99
100 private:
102
103 /**
104 This represents equality between a set of fields, i.e.
105 "t1.f1=t2.f2...=tN.fN".
106 */
107 struct EqualTerm {
108 /// The fields that are equal to each other.
110
111 /// A map of all tables in 'fields'.
113 };
114
115 /**
116 The set of sets of fields in equijoin predicates in this companion set.
117 (@see EstimateEqualPredicateSelectivity() to see how this is utilized.)
118 For example, if we have:
119
120 SELECT ... FROM t1, t2, t3 WHERE t1.x=t2.x AND t2.x=t3.x AND t2.y=t3.y
121
122 m_equal_terms will contain:
123
124 {{t1.x, t2.x, t3.x}, {t2.y, t3.y}}
125 */
127};
128
129/**
130 Represents an expression tree in the relational algebra of joins.
131 Expressions are either tables, or joins of two expressions.
132 (Joins can have join conditions, but more general filters are
133 not represented in this structure.)
134
135 These are used as an abstract precursor to the join hypergraph;
136 they represent the joins in the query block more or less directly,
137 without any reordering. (The parser should largely have output a
138 structure like this instead of Table_ref, but we are not there yet.)
139 The only real manipulation we do on them is pushing down conditions,
140 identifying equijoin conditions from other join conditions,
141 and identifying join conditions that touch given tables (also a form
142 of pushdown).
143 */
145 enum Type {
146 INNER_JOIN = static_cast<int>(JoinType::INNER),
147 LEFT_JOIN = static_cast<int>(JoinType::OUTER),
148
149 /// Left semijoin.
150 SEMIJOIN = static_cast<int>(JoinType::SEMI),
151
152 /// Left antijoin.
153 ANTIJOIN = static_cast<int>(JoinType::ANTI),
154
155 // STRAIGHT_JOIN is an inner join that the user has specified
156 // is noncommutative (as a hint, but one we are not allowed to
157 // disregard).
159
160 // Generally supported by the conflict detector only, not the parser
161 // or any iterators. We include this because we will be needing it
162 // when we actually implement full outer join, and because it helps
163 // verifying semijoin correctness in the unit tests (see the CountPlans*
164 // tests).
166
167 // An inner join between two _or more_ tables, with no join conditions.
168 // This is a special form used only during pushdown, for increased
169 // flexibility in reordering. MULTI_INNER_JOIN nodes do not use
170 // left and right, but rather store all its children in multi_children
171 // (which is empty for all other types).
173
174 TABLE = 100
176
178 : multi_children(thd->mem_root),
183
185
186 // Exactly the same as tables_in_subtree, just with node indexes instead of
187 // table indexes. This is stored alongside tables_in_subtree to save the cost
188 // and convenience of doing repeated translation between the two.
190
191 // If type == TABLE.
194
195 // The CompanionSet that this object is part of.
197
198 // If type != TABLE. Note that equijoin_conditions will be split off
199 // from join_conditions fairly late (at CreateHashJoinConditions()),
200 // so often, you will see equijoin conditions in join_condition..
203 multi_children; // See MULTI_INNER_JOIN.
206
207 // For each element in join_conditions and equijoin_conditions (respectively),
208 // contains some cached properties that the join optimizer would like to have
209 // available for frequent reuse.
210 //
211 // It is a bit awkward to have these separate instead of in the same arrays,
212 // but the latter would complicate MakeJoinHypergraph() a fair amount,
213 // as this information is private to the join optimizer (ie., it is not
214 // generated along with the hypergraph; it is added after MakeJoinHypergraph()
215 // is completed).
219
220 // If true, at least one condition under “join_conditions” is a false (0)
221 // constant. (Such conditions can never be under “equijoin_conditions”.)
224 // If the join conditions were also added as predicates due to cycles
225 // in the graph (see comment in AddCycleEdges()), contains a range of
226 // which indexes they got in the predicate list. This is so that we know that
227 // they are redundant and don't have to apply them if we actually apply this
228 // join (as opposed to getting the edge implicitly by means of joining the
229 // tables along some other way in the cycle).
231
232 // Conflict rules that must be checked before making a subgraph
233 // out of this join; this is in addition to the regular connectivity
234 // check. See FindHyperedgeAndJoinConflicts() for more details.
236};
237
238// Check conflict rules; usually, they will be empty, but the hyperedges are
239// not able to encode every single combination of disallowed joins.
240inline bool PassesConflictRules(hypergraph::NodeMap joined_tables,
241 const RelationalExpression *expr) {
242 for (const ConflictRule &rule : expr->conflict_rules) {
243 if (Overlaps(joined_tables, rule.needed_to_activate_rule) &&
244 !IsSubset(rule.required_nodes, joined_tables)) {
245 return false;
246 }
247 }
248 return true;
249}
250
251// Whether (a <expr> b) === (b <expr> a). See also OperatorsAreAssociative() and
252// OperatorsAre{Left,Right}Asscom() in make_join_hypergraph.cc.
254 return expr.type == RelationalExpression::INNER_JOIN ||
256}
257
258// Call the given functor on each non-table operator in the tree below expr,
259// including expr itself, in post-traversal order.
260template <class Func>
262 if (expr->type == RelationalExpression::TABLE) {
263 return;
264 }
265 ForEachJoinOperator(expr->left, std::forward<Func &&>(func));
266 ForEachJoinOperator(expr->right, std::forward<Func &&>(func));
267 func(expr);
268}
269
270template <class Func>
271void ForEachOperator(RelationalExpression *expr, Func &&func) {
272 if (expr->type != RelationalExpression::TABLE) {
273 ForEachOperator(expr->left, std::forward<Func &&>(func));
274 ForEachOperator(expr->right, std::forward<Func &&>(func));
275 }
276 func(expr);
277}
278
279/// The collection of CompanionSet objects for a given JoinHypergraph.
281 public:
283 Compute(thd, root, nullptr);
284 }
285
286 /// No copying.
289
290 CompanionSet *Find(table_map tables) { return FindInternal(tables); }
291
292 const CompanionSet *Find(table_map tables) const {
293 return FindInternal(tables);
294 }
295
296 /// For trace and debugging.
297 std::string ToString() const;
298
299 private:
300 /// A mapping from table number to CompanionSet.
301 std::array<CompanionSet *, MAX_TABLES> m_table_num_to_companion_set{nullptr};
302
303 /**
304 Compute the CompanionSet of 'expr' and all of its descendants.
305 @param thd The current thread.
306 @param expr Compute CompanionSet of this and all of its descendants.
307 @param current_set The CompanionSet to which 'expr' will belong, or
308 nullptr if 'expr' is the root of a new set.
309 */
310 void Compute(THD *thd, RelationalExpression *expr, CompanionSet *current_set);
311
312 /**
313 For a given set of tables, find the CompanionSet they are part of
314 Returns nullptr if the tables are in different (i.e., incompatible)
315 CompanionSet instances. If so, a condition using this set of
316 tables can _not_ induce a new (cycle) edge in the hypergraph, as
317 there are non-inner joins in the way.
318 */
319 CompanionSet *FindInternal(table_map tables) const;
320};
321
322#endif // SQL_JOIN_OPTIMIZER_RELATIONAL_EXPRESSION_H
bool IsSubset(uint64_t x, uint64_t y)
Definition: bit_utils.h:220
bool Overlaps(uint64_t x, uint64_t y)
Definition: bit_utils.h:228
The collection of CompanionSet objects for a given JoinHypergraph.
Definition: relational_expression.h:280
CompanionSet * Find(table_map tables)
Definition: relational_expression.h:290
CompanionSet * FindInternal(table_map tables) const
For a given set of tables, find the CompanionSet they are part of Returns nullptr if the tables are i...
Definition: relational_expression.cc:198
CompanionSetCollection(const CompanionSetCollection &)=delete
No copying.
void Compute(THD *thd, RelationalExpression *expr, CompanionSet *current_set)
Compute the CompanionSet of 'expr' and all of its descendants.
Definition: relational_expression.cc:148
std::array< CompanionSet *, MAX_TABLES > m_table_num_to_companion_set
A mapping from table number to CompanionSet.
Definition: relational_expression.h:301
CompanionSetCollection & operator=(const CompanionSetCollection &)=delete
CompanionSetCollection(THD *thd, struct RelationalExpression *root)
Definition: relational_expression.h:282
std::string ToString() const
For trace and debugging.
Definition: relational_expression.cc:180
const CompanionSet * Find(table_map tables) const
Definition: relational_expression.h:292
RelationalExpression objects in the same companion set are those that are inner-joined against each o...
Definition: relational_expression.h:77
CompanionSet & operator=(const CompanionSet &)=delete
CompanionSet()=default
Mem_root_array< EqualTerm > m_equal_terms
The set of sets of fields in equijoin predicates in this companion set.
Definition: relational_expression.h:126
table_map GetEqualityMap(const Field &field) const
If 'field' is part of an equijoin predicate in this CompanionSet, return a table_map of the tables in...
Definition: relational_expression.cc:120
CompanionSet(const CompanionSet &)=delete
No copying.
CompanionSet(THD *thd)
Definition: relational_expression.h:81
std::string ToString() const
For tracing and debugging.
Definition: relational_expression.cc:131
void AddEquijoinCondition(THD *thd, const Item_func_eq &eq)
Add the set of equal fields specified by 'func_eq'.
Definition: relational_expression.cc:65
Definition: field.h:574
Base class for the equality comparison operators = and <=>.
Definition: item_cmpfunc.h:990
Implements the comparison operator equals (=)
Definition: item_cmpfunc.h:1055
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:425
Definition: overflow_bitset.h:77
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_lexer_thd.h:35
Definition: table.h:2853
static MEM_ROOT mem_root
Definition: client_plugin.cc:113
@ OUTER
Left outer join.
@ ANTI
Left antijoin, i.e.
@ SEMI
Left semijoin, i.e.
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
OverflowBitset is a fixed-size (once allocated) bitmap that is optimized for the common case of few e...
void ForEachOperator(RelationalExpression *expr, Func &&func)
Definition: relational_expression.h:271
void ForEachJoinOperator(RelationalExpression *expr, Func &&func)
Definition: relational_expression.h:261
bool PassesConflictRules(hypergraph::NodeMap joined_tables, const RelationalExpression *expr)
Definition: relational_expression.h:240
bool OperatorIsCommutative(const RelationalExpression &expr)
Definition: relational_expression.h:253
Access paths are a query planning structure that correspond 1:1 to iterators, in that an access path ...
Definition: access_path.h:212
Definition: relational_expression.h:44
double selectivity
Definition: relational_expression.h:46
Mem_root_array< ContainedSubquery > contained_subqueries
Definition: relational_expression.h:45
OverflowBitset redundant_against_sargable_predicates
Definition: relational_expression.h:54
This represents equality between a set of fields, i.e.
Definition: relational_expression.h:107
FieldArray * fields
The fields that are equal to each other.
Definition: relational_expression.h:109
table_map tables
A map of all tables in 'fields'.
Definition: relational_expression.h:112
Definition: relational_expression.h:62
hypergraph::NodeMap required_nodes
Definition: relational_expression.h:64
hypergraph::NodeMap needed_to_activate_rule
Definition: relational_expression.h:63
Represents an expression tree in the relational algebra of joins.
Definition: relational_expression.h:144
int join_predicate_last
Definition: relational_expression.h:230
Mem_root_array< CachedPropertiesForPredicate > properties_for_equijoin_conditions
Definition: relational_expression.h:218
Mem_root_array< Item_eq_base * > equijoin_conditions
Definition: relational_expression.h:205
int join_predicate_first
Definition: relational_expression.h:230
Mem_root_array< ConflictRule > conflict_rules
Definition: relational_expression.h:235
enum RelationalExpression::Type type
CompanionSet * companion_set
Definition: relational_expression.h:196
RelationalExpression(THD *thd)
Definition: relational_expression.h:177
table_map tables_in_subtree
Definition: relational_expression.h:184
const Table_ref * table
Definition: relational_expression.h:192
hypergraph::NodeMap nodes_in_subtree
Definition: relational_expression.h:189
Mem_root_array< RelationalExpression * > multi_children
Definition: relational_expression.h:203
Mem_root_array< Item * > join_conditions_pushable_to_this
Definition: relational_expression.h:193
table_map conditions_used_tables
Definition: relational_expression.h:223
Mem_root_array< Item * > join_conditions
Definition: relational_expression.h:204
Type
Definition: relational_expression.h:145
@ SEMIJOIN
Left semijoin.
Definition: relational_expression.h:150
@ MULTI_INNER_JOIN
Definition: relational_expression.h:172
@ STRAIGHT_INNER_JOIN
Definition: relational_expression.h:158
@ ANTIJOIN
Left antijoin.
Definition: relational_expression.h:153
@ INNER_JOIN
Definition: relational_expression.h:146
@ FULL_OUTER_JOIN
Definition: relational_expression.h:165
@ TABLE
Definition: relational_expression.h:174
@ LEFT_JOIN
Definition: relational_expression.h:147
bool join_conditions_reject_all_rows
Definition: relational_expression.h:222
Mem_root_array< CachedPropertiesForPredicate > properties_for_join_conditions
Definition: relational_expression.h:216
RelationalExpression * left
Definition: relational_expression.h:201
RelationalExpression * right
Definition: relational_expression.h:201
Definition: table.h:1403