MySQL 8.2.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 SEMIJOIN = static_cast<int>(JoinType::SEMI),
149 ANTIJOIN = static_cast<int>(JoinType::ANTI),
150
151 // STRAIGHT_JOIN is an inner join that the user has specified
152 // is noncommutative (as a hint, but one we are not allowed to
153 // disregard).
155
156 // Generally supported by the conflict detector only, not the parser
157 // or any iterators. We include this because we will be needing it
158 // when we actually implement full outer join, and because it helps
159 // verifying semijoin correctness in the unit tests (see the CountPlans*
160 // tests).
162
163 // An inner join between two _or more_ tables, with no join conditions.
164 // This is a special form used only during pushdown, for increased
165 // flexibility in reordering. MULTI_INNER_JOIN nodes do not use
166 // left and right, but rather store all its children in multi_children
167 // (which is empty for all other types).
169
170 TABLE = 100
172
174 : multi_children(thd->mem_root),
179
181
182 // Exactly the same as tables_in_subtree, just with node indexes instead of
183 // table indexes. This is stored alongside tables_in_subtree to save the cost
184 // and convenience of doing repeated translation between the two.
186
187 // If type == TABLE.
190
191 // The CompanionSet that this object is part of.
193
194 // If type != TABLE. Note that equijoin_conditions will be split off
195 // from join_conditions fairly late (at CreateHashJoinConditions()),
196 // so often, you will see equijoin conditions in join_condition..
199 multi_children; // See MULTI_INNER_JOIN.
202
203 // For each element in join_conditions and equijoin_conditions (respectively),
204 // contains some cached properties that the join optimizer would like to have
205 // available for frequent reuse.
206 //
207 // It is a bit awkward to have these separate instead of in the same arrays,
208 // but the latter would complicate MakeJoinHypergraph() a fair amount,
209 // as this information is private to the join optimizer (ie., it is not
210 // generated along with the hypergraph; it is added after MakeJoinHypergraph()
211 // is completed).
215
216 // If true, at least one condition under “join_conditions” is a false (0)
217 // constant. (Such conditions can never be under “equijoin_conditions”.)
220 // If the join conditions were also added as predicates due to cycles
221 // in the graph (see comment in AddCycleEdges()), contains a range of
222 // which indexes they got in the predicate list. This is so that we know that
223 // they are redundant and don't have to apply them if we actually apply this
224 // join (as opposed to getting the edge implicitly by means of joining the
225 // tables along some other way in the cycle).
227
228 // Conflict rules that must be checked before making a subgraph
229 // out of this join; this is in addition to the regular connectivity
230 // check. See FindHyperedgeAndJoinConflicts() for more details.
232};
233
234// Check conflict rules; usually, they will be empty, but the hyperedges are
235// not able to encode every single combination of disallowed joins.
236inline bool PassesConflictRules(hypergraph::NodeMap joined_tables,
237 const RelationalExpression *expr) {
238 for (const ConflictRule &rule : expr->conflict_rules) {
239 if (Overlaps(joined_tables, rule.needed_to_activate_rule) &&
240 !IsSubset(rule.required_nodes, joined_tables)) {
241 return false;
242 }
243 }
244 return true;
245}
246
247// Whether (a <expr> b) === (b <expr> a). See also OperatorsAreAssociative() and
248// OperatorsAre{Left,Right}Asscom() in make_join_hypergraph.cc.
250 return expr.type == RelationalExpression::INNER_JOIN ||
252}
253
254// Call the given functor on each non-table operator in the tree below expr,
255// including expr itself, in post-traversal order.
256template <class Func>
258 if (expr->type == RelationalExpression::TABLE) {
259 return;
260 }
261 ForEachJoinOperator(expr->left, std::forward<Func &&>(func));
262 ForEachJoinOperator(expr->right, std::forward<Func &&>(func));
263 func(expr);
264}
265
266template <class Func>
267void ForEachOperator(RelationalExpression *expr, Func &&func) {
268 if (expr->type != RelationalExpression::TABLE) {
269 ForEachOperator(expr->left, std::forward<Func &&>(func));
270 ForEachOperator(expr->right, std::forward<Func &&>(func));
271 }
272 func(expr);
273}
274
275/// The collection of CompanionSet objects for a given JoinHypergraph.
277 public:
279 Compute(thd, root, nullptr);
280 }
281
282 /// No copying.
285
286 CompanionSet *Find(table_map tables) { return FindInternal(tables); }
287
288 const CompanionSet *Find(table_map tables) const {
289 return FindInternal(tables);
290 }
291
292 /// For trace and debugging.
293 std::string ToString() const;
294
295 private:
296 /// A mapping from table number to CompanionSet.
297 std::array<CompanionSet *, MAX_TABLES> m_table_num_to_companion_set{nullptr};
298
299 /**
300 Compute the CompanionSet of 'expr' and all of its descendants.
301 @param thd The current thread.
302 @param expr Compute CompanionSet of this and all of its descendants.
303 @param current_set The CompanionSet to which 'expr' will belong, or
304 nullptr if 'expr' is the root of a new set.
305 */
306 void Compute(THD *thd, RelationalExpression *expr, CompanionSet *current_set);
307
308 /**
309 For a given set of tables, find the CompanionSet they are part of
310 Returns nullptr if the tables are in different (i.e., incompatible)
311 CompanionSet instances. If so, a condition using this set of
312 tables can _not_ induce a new (cycle) edge in the hypergraph, as
313 there are non-inner joins in the way.
314 */
315 CompanionSet *FindInternal(table_map tables) const;
316};
317
318#endif // SQL_JOIN_OPTIMIZER_RELATIONAL_EXPRESSION_H
bool IsSubset(uint64_t x, uint64_t y)
Definition: bit_utils.h:228
bool Overlaps(uint64_t x, uint64_t y)
Definition: bit_utils.h:236
The collection of CompanionSet objects for a given JoinHypergraph.
Definition: relational_expression.h:276
CompanionSet * Find(table_map tables)
Definition: relational_expression.h:286
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:297
CompanionSetCollection & operator=(const CompanionSetCollection &)=delete
CompanionSetCollection(THD *thd, struct RelationalExpression *root)
Definition: relational_expression.h:278
std::string ToString() const
For trace and debugging.
Definition: relational_expression.cc:180
const CompanionSet * Find(table_map tables) const
Definition: relational_expression.h:288
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:576
Base class for the equality comparison operators = and <=>.
Definition: item_cmpfunc.h:980
Implements the comparison operator equals (=)
Definition: item_cmpfunc.h:1045
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:425
Definition: overflow_bitset.h:76
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:2846
static MEM_ROOT mem_root
Definition: client_plugin.cc:113
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:267
void ForEachJoinOperator(RelationalExpression *expr, Func &&func)
Definition: relational_expression.h:257
bool PassesConflictRules(hypergraph::NodeMap joined_tables, const RelationalExpression *expr)
Definition: relational_expression.h:236
bool OperatorIsCommutative(const RelationalExpression &expr)
Definition: relational_expression.h:249
Access paths are a query planning structure that correspond 1:1 to iterators, in that an access path ...
Definition: access_path.h:193
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:226
Mem_root_array< CachedPropertiesForPredicate > properties_for_equijoin_conditions
Definition: relational_expression.h:214
Mem_root_array< Item_eq_base * > equijoin_conditions
Definition: relational_expression.h:201
int join_predicate_first
Definition: relational_expression.h:226
Mem_root_array< ConflictRule > conflict_rules
Definition: relational_expression.h:231
enum RelationalExpression::Type type
CompanionSet * companion_set
Definition: relational_expression.h:192
RelationalExpression(THD *thd)
Definition: relational_expression.h:173
table_map tables_in_subtree
Definition: relational_expression.h:180
const Table_ref * table
Definition: relational_expression.h:188
hypergraph::NodeMap nodes_in_subtree
Definition: relational_expression.h:185
Mem_root_array< RelationalExpression * > multi_children
Definition: relational_expression.h:199
Mem_root_array< Item * > join_conditions_pushable_to_this
Definition: relational_expression.h:189
table_map conditions_used_tables
Definition: relational_expression.h:219
Mem_root_array< Item * > join_conditions
Definition: relational_expression.h:200
Type
Definition: relational_expression.h:145
@ SEMIJOIN
Definition: relational_expression.h:148
@ MULTI_INNER_JOIN
Definition: relational_expression.h:168
@ STRAIGHT_INNER_JOIN
Definition: relational_expression.h:154
@ ANTIJOIN
Definition: relational_expression.h:149
@ INNER_JOIN
Definition: relational_expression.h:146
@ FULL_OUTER_JOIN
Definition: relational_expression.h:161
@ TABLE
Definition: relational_expression.h:170
@ LEFT_JOIN
Definition: relational_expression.h:147
bool join_conditions_reject_all_rows
Definition: relational_expression.h:218
Mem_root_array< CachedPropertiesForPredicate > properties_for_join_conditions
Definition: relational_expression.h:212
RelationalExpression * left
Definition: relational_expression.h:197
RelationalExpression * right
Definition: relational_expression.h:197
Definition: table.h:1396