MySQL 8.0.30
Source Code Documentation
relational_expression.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_RELATIONAL_EXPRESSION_H
24#define SQL_JOIN_OPTIMIZER_RELATIONAL_EXPRESSION_H
25
26#include <stdint.h>
27
31#include "sql/join_type.h"
32#include "sql/mem_root_array.h"
33#include "sql/sql_class.h"
34
35struct AccessPath;
36class Item_func_eq;
37
41 int row_width; // Of the subquery's rows.
42};
43
44// Some information about each predicate that the join optimizer would like to
45// have available in order to avoid computing it anew for each use of that
46// predicate.
50
51 // For equijoins only: A bitmap of which sargable predicates
52 // are part of the same multi-equality as this one (except the
53 // condition itself, which is excluded), and thus are redundant
54 // against it. This is used in AlreadyAppliedThroughSargable()
55 // to quickly find out if we already have applied any of them
56 // as a join condition.
58};
59
60// Describes a rule disallowing specific joins; if any tables from
61// needed_to_activate_rule is part of the join, then _all_ tables from
62// required_nodes must also be present.
63//
64// See FindHyperedgeAndJoinConflicts() for details.
68};
69
70/**
71 Represents an expression tree in the relational algebra of joins.
72 Expressions are either tables, or joins of two expressions.
73 (Joins can have join conditions, but more general filters are
74 not represented in this structure.)
75
76 These are used as an abstract precursor to the join hypergraph;
77 they represent the joins in the query block more or less directly,
78 without any reordering. (The parser should largely have output a
79 structure like this instead of TABLE_LIST, but we are not there yet.)
80 The only real manipulation we do on them is pushing down conditions,
81 identifying equijoin conditions from other join conditions,
82 and identifying join conditions that touch given tables (also a form
83 of pushdown).
84 */
92
93 enum Type {
94 INNER_JOIN = static_cast<int>(JoinType::INNER),
95 LEFT_JOIN = static_cast<int>(JoinType::OUTER),
96 SEMIJOIN = static_cast<int>(JoinType::SEMI),
97 ANTIJOIN = static_cast<int>(JoinType::ANTI),
98
99 // STRAIGHT_JOIN is an inner join that the user has specified
100 // is noncommutative (as a hint, but one we are not allowed to
101 // disregard).
103
104 // Generally supported by the conflict detector only, not the parser
105 // or any iterators. We include this because we will be needing it
106 // when we actually implement full outer join, and because it helps
107 // verifying semijoin correctness in the unit tests (see the CountPlans*
108 // tests).
110
111 // An inner join between two _or more_ tables, with no join conditions.
112 // This is a special form used only during pushdown, for increased
113 // flexibility in reordering. MULTI_INNER_JOIN nodes do not use
114 // left and right, but rather store all its children in multi_children
115 // (which is empty for all other types).
117
118 TABLE = 100
121
122 // Exactly the same as tables_in_subtree, just with node indexes instead of
123 // table indexes. This is stored alongside tables_in_subtree to save the cost
124 // and convenience of doing repeated translation between the two.
126
127 // If type == TABLE.
130 // Tables in the same companion set are those that are inner-joined
131 // against each other; we use this to see in what parts of the graph
132 // we allow cycles. (Within companion sets, we are also allowed to
133 // add Cartesian products if we deem that an advantage, but we don't
134 // do it currently.) -1 means that the table is not part of a companion
135 // set, e.g. because it only participates in outer joins. Tables may
136 // also be alone in their companion sets, which essentially means
137 // the same thing as -1. The companion sets are just opaque identifiers;
138 // the number itself doesn't mean much.
140
141 // If type != TABLE. Note that equijoin_conditions will be split off
142 // from join_conditions fairly late (at CreateHashJoinConditions()),
143 // so often, you will see equijoin conditions in join_condition..
146 multi_children; // See MULTI_INNER_JOIN.
149
150 // For each element in join_conditions and equijoin_conditions (respectively),
151 // contains some cached properties that the join optimizer would like to have
152 // available for frequent reuse.
153 //
154 // It is a bit awkward to have these separate instead of in the same arrays,
155 // but the latter would complicate MakeJoinHypergraph() a fair amount,
156 // as this information is private to the join optimizer (ie., it is not
157 // generated along with the hypergraph; it is added after MakeJoinHypergraph()
158 // is completed).
162
163 // If true, at least one condition under “join_conditions” is a false (0)
164 // constant. (Such conditions can never be under “equijoin_conditions”.)
167 // If the join conditions were also added as predicates due to cycles
168 // in the graph (see comment in AddCycleEdges()), contains a range of
169 // which indexes they got in the predicate list. This is so that we know that
170 // they are redundant and don't have to apply them if we actually apply this
171 // join (as opposed to getting the edge implicitly by means of joining the
172 // tables along some other way in the cycle).
174
175 // Conflict rules that must be checked before making a subgraph
176 // out of this join; this is in addition to the regular connectivity
177 // check. See FindHyperedgeAndJoinConflicts() for more details.
179};
180
181// Check conflict rules; usually, they will be empty, but the hyperedges are
182// not able to encode every single combination of disallowed joins.
183inline bool PassesConflictRules(hypergraph::NodeMap joined_tables,
184 const RelationalExpression *expr) {
185 for (const ConflictRule &rule : expr->conflict_rules) {
186 if (Overlaps(joined_tables, rule.needed_to_activate_rule) &&
187 !IsSubset(rule.required_nodes, joined_tables)) {
188 return false;
189 }
190 }
191 return true;
192}
193
194// Whether (a <expr> b) === (b <expr> a). See also OperatorIsAssociative(),
195// OperatorsAreAssociative() // and OperatorsAre{Left,Right}Asscom()
196// in make_join_hypergraph.cc.
198 return expr.type == RelationalExpression::INNER_JOIN ||
200}
201
202// Call the given functor on each non-table operator in the tree below expr,
203// including expr itself, in post-traversal order.
204template <class Func>
206 if (expr->type == RelationalExpression::TABLE) {
207 return;
208 }
209 ForEachJoinOperator(expr->left, std::forward<Func &&>(func));
210 ForEachJoinOperator(expr->right, std::forward<Func &&>(func));
211 func(expr);
212}
213
214template <class Func>
215void ForEachOperator(RelationalExpression *expr, Func &&func) {
216 if (expr->type != RelationalExpression::TABLE) {
217 ForEachOperator(expr->left, std::forward<Func &&>(func));
218 ForEachOperator(expr->right, std::forward<Func &&>(func));
219 }
220 func(expr);
221}
222
223#endif // SQL_JOIN_OPTIMIZER_RELATIONAL_EXPRESSION_H
bool IsSubset(uint64_t x, uint64_t y)
Definition: bit_utils.h:222
bool Overlaps(uint64_t x, uint64_t y)
Definition: bit_utils.h:230
Implements the comparison operator equals (=)
Definition: item_cmpfunc.h:976
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:421
Definition: overflow_bitset.h:76
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_class.h:922
static MEM_ROOT mem_root
Definition: client_plugin.cc:109
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:215
void ForEachJoinOperator(RelationalExpression *expr, Func &&func)
Definition: relational_expression.h:205
bool PassesConflictRules(hypergraph::NodeMap joined_tables, const RelationalExpression *expr)
Definition: relational_expression.h:183
bool OperatorIsCommutative(const RelationalExpression &expr)
Definition: relational_expression.h:197
Access paths are a query planning structure that correspond 1:1 to iterators, in that an access path ...
Definition: access_path.h:188
Definition: relational_expression.h:47
double selectivity
Definition: relational_expression.h:49
Mem_root_array< ContainedSubquery > contained_subqueries
Definition: relational_expression.h:48
OverflowBitset redundant_against_sargable_predicates
Definition: relational_expression.h:57
Definition: relational_expression.h:65
hypergraph::NodeMap required_nodes
Definition: relational_expression.h:67
hypergraph::NodeMap needed_to_activate_rule
Definition: relational_expression.h:66
Definition: relational_expression.h:38
AccessPath * path
Definition: relational_expression.h:39
int row_width
Definition: relational_expression.h:41
bool materializable
Definition: relational_expression.h:40
Represents an expression tree in the relational algebra of joins.
Definition: relational_expression.h:85
int join_predicate_last
Definition: relational_expression.h:173
Mem_root_array< CachedPropertiesForPredicate > properties_for_equijoin_conditions
Definition: relational_expression.h:161
int join_predicate_first
Definition: relational_expression.h:173
Mem_root_array< ConflictRule > conflict_rules
Definition: relational_expression.h:178
enum RelationalExpression::Type type
RelationalExpression(THD *thd)
Definition: relational_expression.h:86
table_map tables_in_subtree
Definition: relational_expression.h:120
hypergraph::NodeMap nodes_in_subtree
Definition: relational_expression.h:125
Mem_root_array< RelationalExpression * > multi_children
Definition: relational_expression.h:146
Mem_root_array< Item * > join_conditions_pushable_to_this
Definition: relational_expression.h:129
table_map conditions_used_tables
Definition: relational_expression.h:166
Mem_root_array< Item * > join_conditions
Definition: relational_expression.h:147
Type
Definition: relational_expression.h:93
@ SEMIJOIN
Definition: relational_expression.h:96
@ MULTI_INNER_JOIN
Definition: relational_expression.h:116
@ STRAIGHT_INNER_JOIN
Definition: relational_expression.h:102
@ ANTIJOIN
Definition: relational_expression.h:97
@ INNER_JOIN
Definition: relational_expression.h:94
@ FULL_OUTER_JOIN
Definition: relational_expression.h:109
@ TABLE
Definition: relational_expression.h:118
@ LEFT_JOIN
Definition: relational_expression.h:95
Mem_root_array< Item_func_eq * > equijoin_conditions
Definition: relational_expression.h:148
const TABLE_LIST * table
Definition: relational_expression.h:128
bool join_conditions_reject_all_rows
Definition: relational_expression.h:165
Mem_root_array< CachedPropertiesForPredicate > properties_for_join_conditions
Definition: relational_expression.h:159
RelationalExpression * left
Definition: relational_expression.h:144
RelationalExpression * right
Definition: relational_expression.h:144
int companion_set
Definition: relational_expression.h:139
Definition: table.h:2684
Definition: table.h:1394