MySQL 8.2.0
Source Code Documentation
walk_access_paths.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_WALK_ACCESS_PATHS_H
24#define SQL_JOIN_OPTIMIZER_WALK_ACCESS_PATHS_H
25
26#include <type_traits>
27
30
32 // Stop on _any_ MATERIALIZE or STREAM path, even if they do not cross query
33 // blocks.
34 // Also stops on APPEND paths, which always cross query blocks.
36
37 // Stop on MATERIALIZE, STREAM or APPEND paths that cross query blocks.
39
40 // Do not stop at any kind of access path, unless func() returns true.
42};
43
44/**
45 Traverse every access path below `path` (possibly limited to the current query
46 block with the `cross_query_blocks` parameter), calling func() for each one
47 with pre- or post-order traversal. If func() returns true, the traversal does
48 not descend into the children of the current path. For post-order traversal,
49 the children have already been traversed when func() is called, so it is too
50 late to skip them, and the return value of func() is effectively ignored.
51
52 The `join` parameter signifies what query block `path` is part of, since that
53 is not implicit from the path itself. The function will track this as it
54 changes throughout the tree (in MATERIALIZE or STREAM access paths), and
55 will give the correct value to the func() callback. It is only used by
56 WalkAccessPaths() itself if the policy is ENTIRE_QUERY_BLOCK; if not, it is
57 only used for the func() callback, and you can set it to nullptr if you wish.
58 func() must have signature func(AccessPath *, const JOIN *), or it could be
59 JOIN * if a non-const JOIN is given in.
60 */
61template <class AccessPathPtr, class Func, class JoinPtr>
62void WalkAccessPaths(AccessPathPtr path, JoinPtr join,
63 WalkAccessPathPolicy cross_query_blocks, Func &&func,
64 bool post_order_traversal = false) {
65 static_assert(
66 std::is_convertible<AccessPathPtr, const AccessPath *>::value,
67 "The “path” argument must be AccessPath * or const AccessPath *.");
68 static_assert(
69 std::is_convertible<JoinPtr, const JOIN *>::value,
70 "The “join” argument must be JOIN * or const JOIN * (or nullptr).");
71
72 if (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_QUERY_BLOCK) {
73 assert(join != nullptr);
74 }
75 if (!post_order_traversal) {
76 if (func(path, join)) {
77 // Stop recursing in this branch.
78 return;
79 }
80 }
81 switch (path->type) {
84 case AccessPath::REF:
90 case AccessPath::MRR:
102 // No children.
103 break;
105 WalkAccessPaths(path->nested_loop_join().outer, join, cross_query_blocks,
106 std::forward<Func &&>(func), post_order_traversal);
107 WalkAccessPaths(path->nested_loop_join().inner, join, cross_query_blocks,
108 std::forward<Func &&>(func), post_order_traversal);
109 break;
111 WalkAccessPaths(path->nested_loop_semijoin_with_duplicate_removal().outer,
112 join, cross_query_blocks, std::forward<Func &&>(func),
113 post_order_traversal);
114 WalkAccessPaths(path->nested_loop_semijoin_with_duplicate_removal().inner,
115 join, cross_query_blocks, std::forward<Func &&>(func),
116 post_order_traversal);
117 break;
119 WalkAccessPaths(path->bka_join().outer, join, cross_query_blocks,
120 std::forward<Func &&>(func), post_order_traversal);
121 WalkAccessPaths(path->bka_join().inner, join, cross_query_blocks,
122 std::forward<Func &&>(func), post_order_traversal);
123 break;
125 WalkAccessPaths(path->hash_join().outer, join, cross_query_blocks,
126 std::forward<Func &&>(func), post_order_traversal);
127 WalkAccessPaths(path->hash_join().inner, join, cross_query_blocks,
128 std::forward<Func &&>(func), post_order_traversal);
129 break;
131 WalkAccessPaths(path->filter().child, join, cross_query_blocks,
132 std::forward<Func &&>(func), post_order_traversal);
133 break;
134 case AccessPath::SORT:
135 WalkAccessPaths(path->sort().child, join, cross_query_blocks,
136 std::forward<Func &&>(func), post_order_traversal);
137 break;
139 WalkAccessPaths(path->aggregate().child, join, cross_query_blocks,
140 std::forward<Func &&>(func), post_order_traversal);
141 break;
143 WalkAccessPaths(path->temptable_aggregate().subquery_path, join,
144 cross_query_blocks, std::forward<Func &&>(func),
145 post_order_traversal);
146 WalkAccessPaths(path->temptable_aggregate().table_path, join,
147 cross_query_blocks, std::forward<Func &&>(func),
148 post_order_traversal);
149 break;
151 WalkAccessPaths(path->limit_offset().child, join, cross_query_blocks,
152 std::forward<Func &&>(func), post_order_traversal);
153 break;
155 if (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_TREE ||
156 (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_QUERY_BLOCK &&
157 path->stream().join == join)) {
158 WalkAccessPaths(path->stream().child, path->stream().join,
159 cross_query_blocks, std::forward<Func &&>(func),
160 post_order_traversal);
161 }
162 break;
164 WalkAccessPaths(path->materialize().table_path, join, cross_query_blocks,
165 std::forward<Func &&>(func), post_order_traversal);
166 for (const MaterializePathParameters::Operand &operand :
167 path->materialize().param->m_operands) {
168 if (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_TREE ||
169 (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_QUERY_BLOCK &&
170 operand.join == join)) {
171 WalkAccessPaths(operand.subquery_path, operand.join,
172 cross_query_blocks, std::forward<Func &&>(func),
173 post_order_traversal);
174 }
175 }
176 break;
178 WalkAccessPaths(path->materialize_information_schema_table().table_path,
179 join, cross_query_blocks, std::forward<Func &&>(func),
180 post_order_traversal);
181 break;
183 if (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_TREE) {
184 for (const AppendPathParameters &child : *path->append().children) {
185 WalkAccessPaths(child.path, child.join, cross_query_blocks,
186 std::forward<Func &&>(func), post_order_traversal);
187 }
188 }
189 break;
191 WalkAccessPaths(path->window().child, join, cross_query_blocks,
192 std::forward<Func &&>(func), post_order_traversal);
193 break;
195 WalkAccessPaths(path->weedout().child, join, cross_query_blocks,
196 std::forward<Func &&>(func), post_order_traversal);
197 break;
199 WalkAccessPaths(path->remove_duplicates().child, join, cross_query_blocks,
200 std::forward<Func &&>(func), post_order_traversal);
201 break;
203 WalkAccessPaths(path->remove_duplicates_on_index().child, join,
204 cross_query_blocks, std::forward<Func &&>(func),
205 post_order_traversal);
206 break;
208 WalkAccessPaths(path->alternative().child, join, cross_query_blocks,
209 std::forward<Func &&>(func), post_order_traversal);
210 break;
212 WalkAccessPaths(path->cache_invalidator().child, join, cross_query_blocks,
213 std::forward<Func &&>(func), post_order_traversal);
214 break;
216 for (AccessPath *child : *path->index_merge().children) {
217 WalkAccessPaths(child, join, cross_query_blocks,
218 std::forward<Func &&>(func), post_order_traversal);
219 }
220 break;
222 for (AccessPath *child : *path->rowid_intersection().children) {
223 WalkAccessPaths(child, join, cross_query_blocks,
224 std::forward<Func &&>(func), post_order_traversal);
225 }
226 break;
228 for (AccessPath *child : *path->rowid_union().children) {
229 WalkAccessPaths(child, join, cross_query_blocks,
230 std::forward<Func &&>(func), post_order_traversal);
231 }
232 break;
234 WalkAccessPaths(path->delete_rows().child, join, cross_query_blocks,
235 std::forward<Func &&>(func), post_order_traversal);
236 break;
238 WalkAccessPaths(path->update_rows().child, join, cross_query_blocks,
239 std::forward<Func &&>(func), post_order_traversal);
240 break;
241 }
242 if (post_order_traversal) {
243 if (func(path, join)) {
244 // Stop recursing in this branch. In practice a no-op, since we are
245 // already done with this branch.
246 return;
247 }
248 }
249}
250
251/**
252 A wrapper around WalkAccessPaths() that collects all tables under
253 “root_path” and calls the given functor, stopping at materializations.
254 This is typically used to know which tables to sort or the like.
255
256 func() must have signature func(TABLE *), and return true upon error.
257 */
258template <class Func>
259void WalkTablesUnderAccessPath(AccessPath *root_path, Func &&func,
260 bool include_pruned_tables) {
262 root_path, /*join=*/nullptr,
264 [&](AccessPath *path, const JOIN *) {
265 switch (path->type) {
266 case AccessPath::TABLE_SCAN:
267 return func(path->table_scan().table);
268 case AccessPath::INDEX_SCAN:
269 return func(path->index_scan().table);
270 case AccessPath::REF:
271 return func(path->ref().table);
272 case AccessPath::REF_OR_NULL:
273 return func(path->ref_or_null().table);
274 case AccessPath::EQ_REF:
275 return func(path->eq_ref().table);
276 case AccessPath::PUSHED_JOIN_REF:
277 return func(path->pushed_join_ref().table);
278 case AccessPath::FULL_TEXT_SEARCH:
279 return func(path->full_text_search().table);
280 case AccessPath::CONST_TABLE:
281 return func(path->const_table().table);
282 case AccessPath::MRR:
283 return func(path->mrr().table);
284 case AccessPath::FOLLOW_TAIL:
285 return func(path->follow_tail().table);
286 case AccessPath::INDEX_RANGE_SCAN:
287 return func(path->index_range_scan().used_key_part[0].field->table);
288 case AccessPath::INDEX_SKIP_SCAN:
289 return func(path->index_skip_scan().table);
290 case AccessPath::GROUP_INDEX_SKIP_SCAN:
291 return func(path->group_index_skip_scan().table);
292 case AccessPath::DYNAMIC_INDEX_RANGE_SCAN:
293 return func(path->dynamic_index_range_scan().table);
294 case AccessPath::STREAM:
295 return func(path->stream().table);
296 case AccessPath::MATERIALIZE:
297 return func(path->materialize().param->table);
298 case AccessPath::MATERIALIZED_TABLE_FUNCTION:
299 return func(path->materialized_table_function().table);
300 case AccessPath::ALTERNATIVE:
301 return func(
302 path->alternative().table_scan_path->table_scan().table);
303 case AccessPath::UNQUALIFIED_COUNT:
304 // Should never be below anything that needs
305 // WalkTablesUnderAccessPath().
306 assert(false);
307 return true;
308 case AccessPath::ZERO_ROWS:
309 if (include_pruned_tables && path->zero_rows().child != nullptr) {
310 WalkTablesUnderAccessPath(path->zero_rows().child, func,
311 include_pruned_tables);
312 }
313 return false;
315 return func(path->window().temp_table);
329 case AccessPath::SORT:
339 return false;
340 }
341 assert(false);
342 return true;
343 });
344}
345
346#endif // SQL_JOIN_OPTIMIZER_WALK_ACCESS_PATHS_H
Definition: sql_optimizer.h:132
static char * path
Definition: mysqldump.cc:148
std::string join(Container cont, const std::string &delim)
join elements of an container into a string separated by a delimiter.
Definition: string.h:150
Access paths are a query planning structure that correspond 1:1 to iterators, in that an access path ...
Definition: access_path.h:193
@ FOLLOW_TAIL
Definition: access_path.h:221
@ FILTER
Definition: access_path.h:245
@ PUSHED_JOIN_REF
Definition: access_path.h:217
@ ZERO_ROWS_AGGREGATED
Definition: access_path.h:234
@ UPDATE_ROWS
Definition: access_path.h:263
@ AGGREGATE
Definition: access_path.h:247
@ BKA_JOIN
Definition: access_path.h:241
@ ZERO_ROWS
Definition: access_path.h:233
@ CONST_TABLE
Definition: access_path.h:219
@ GROUP_INDEX_SKIP_SCAN
Definition: access_path.h:227
@ INDEX_RANGE_SCAN
Definition: access_path.h:222
@ UNQUALIFIED_COUNT
Definition: access_path.h:236
@ EQ_REF
Definition: access_path.h:216
@ FAKE_SINGLE_ROW
Definition: access_path.h:232
@ MATERIALIZE_INFORMATION_SCHEMA_TABLE
Definition: access_path.h:252
@ WINDOW
Definition: access_path.h:254
@ REF_OR_NULL
Definition: access_path.h:215
@ MATERIALIZE
Definition: access_path.h:251
@ NESTED_LOOP_SEMIJOIN_WITH_DUPLICATE_REMOVAL
Definition: access_path.h:240
@ ROWID_UNION
Definition: access_path.h:225
@ INDEX_SKIP_SCAN
Definition: access_path.h:226
@ MRR
Definition: access_path.h:220
@ CACHE_INVALIDATOR
Definition: access_path.h:259
@ INDEX_SCAN
Definition: access_path.h:213
@ TABLE_VALUE_CONSTRUCTOR
Definition: access_path.h:231
@ WEEDOUT
Definition: access_path.h:255
@ MATERIALIZED_TABLE_FUNCTION
Definition: access_path.h:235
@ REMOVE_DUPLICATES_ON_INDEX
Definition: access_path.h:257
@ TABLE_SCAN
Definition: access_path.h:212
@ REF
Definition: access_path.h:214
@ TEMPTABLE_AGGREGATE
Definition: access_path.h:248
@ LIMIT_OFFSET
Definition: access_path.h:249
@ APPEND
Definition: access_path.h:253
@ NESTED_LOOP_JOIN
Definition: access_path.h:239
@ INDEX_MERGE
Definition: access_path.h:223
@ FULL_TEXT_SEARCH
Definition: access_path.h:218
@ ALTERNATIVE
Definition: access_path.h:258
@ STREAM
Definition: access_path.h:250
@ REMOVE_DUPLICATES
Definition: access_path.h:256
@ ROWID_INTERSECTION
Definition: access_path.h:224
@ DYNAMIC_INDEX_RANGE_SCAN
Definition: access_path.h:228
@ DELETE_ROWS
Definition: access_path.h:262
@ SORT
Definition: access_path.h:246
@ HASH_JOIN
Definition: access_path.h:242
Definition: access_path.h:163
Definition: materialize_path_parameters.h:41
void WalkAccessPaths(AccessPathPtr path, JoinPtr join, WalkAccessPathPolicy cross_query_blocks, Func &&func, bool post_order_traversal=false)
Traverse every access path below path (possibly limited to the current query block with the cross_que...
Definition: walk_access_paths.h:62
WalkAccessPathPolicy
Definition: walk_access_paths.h:31
void WalkTablesUnderAccessPath(AccessPath *root_path, Func &&func, bool include_pruned_tables)
A wrapper around WalkAccessPaths() that collects all tables under “root_path” and calls the given fun...
Definition: walk_access_paths.h:259