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