MySQL 8.2.0
Source Code Documentation
Go to the documentation of this file.
1/* Copyright (c) 2020, 2023, Oracle and/or its affiliates.
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.
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.
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 GNU General Public License, version 2.0, for more details.
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 */
26#include <stdint.h>
28#include "sql/item.h"
33#include "sql/join_type.h"
34#include "sql/mem_root_array.h"
35#include "sql/sql_class.h"
37struct AccessPath;
38class Item_eq_base;
39class Item_func_eq;
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.
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.
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.
61// See FindHyperedgeAndJoinConflicts() for details.
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()).
77class CompanionSet final {
78 public:
79 CompanionSet() = default;
81 explicit CompanionSet(THD *thd) : m_equal_terms(thd->mem_root) {}
83 /// No copying.
84 CompanionSet(const CompanionSet &) = delete;
87 /// Add the set of equal fields specified by 'func_eq'.
88 void AddEquijoinCondition(THD *thd, const Item_func_eq &eq);
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;
96 /// For tracing and debugging.
97 /// @returns A string representation like "{{t1.f1, t2.f2}, {t2.f3, t3.f4}}".
98 std::string ToString() const;
100 private:
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.
111 /// A map of all tables in 'fields'.
113 };
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:
120 SELECT ... FROM t1, t2, t3 WHERE t1.x=t2.x AND t2.x=t3.x AND t2.y=t3.y
122 m_equal_terms will contain:
124 {{t1.x, t2.x, t3.x}, {t2.y, t3.y}}
125 */
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.)
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),
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).
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).
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).
170 TABLE = 100
174 : multi_children(thd->mem_root),
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.
187 // If type == TABLE.
191 // The CompanionSet that this object is part of.
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.
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).
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).
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.
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;
247// Whether (a <expr> b) === (b <expr> a). See also OperatorsAreAssociative() and
248// OperatorsAre{Left,Right}Asscom() in
250 return expr.type == RelationalExpression::INNER_JOIN ||
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);
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);
275/// The collection of CompanionSet objects for a given JoinHypergraph.
277 public:
279 Compute(thd, root, nullptr);
280 }
282 /// No copying.
286 CompanionSet *Find(table_map tables) { return FindInternal(tables); }
288 const CompanionSet *Find(table_map tables) const {
289 return FindInternal(tables);
290 }
292 /// For trace and debugging.
293 std::string ToString() const;
295 private:
296 /// A mapping from table number to CompanionSet.
297 std::array<CompanionSet *, MAX_TABLES> m_table_num_to_companion_set{nullptr};
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);
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;
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...
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.
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.
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
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...
CompanionSet(const CompanionSet &)=delete
No copying.
CompanionSet(THD *thd)
Definition: relational_expression.h:81
std::string ToString() const
For tracing and debugging.
void AddEquijoinCondition(THD *thd, const Item_func_eq &eq)
Add the set of equal fields specified by 'func_eq'.
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
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
Definition: relational_expression.h:145
Definition: relational_expression.h:148
Definition: relational_expression.h:168
Definition: relational_expression.h:154
Definition: relational_expression.h:149
Definition: relational_expression.h:146
Definition: relational_expression.h:161
Definition: relational_expression.h:170
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