MySQL 8.0.29
Source Code Documentation
walk_access_paths.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_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 Func, class JoinPtr>
63 WalkAccessPathPolicy cross_query_blocks, Func &&func,
64 bool post_order_traversal = false) {
65 static_assert(
66 std::is_convertible<JoinPtr, const JOIN *>::value,
67 "The “join” argument must be JOIN * or const JOIN * (or nullptr).");
68
69 if (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_QUERY_BLOCK) {
70 assert(join != nullptr);
71 }
72 if (!post_order_traversal) {
73 if (func(path, join)) {
74 // Stop recursing in this branch.
75 return;
76 }
77 }
78 switch (path->type) {
81 case AccessPath::REF:
87 case AccessPath::MRR:
99 // No children.
100 break;
102 WalkAccessPaths(path->nested_loop_join().outer, join, cross_query_blocks,
103 std::forward<Func &&>(func), post_order_traversal);
104 WalkAccessPaths(path->nested_loop_join().inner, join, cross_query_blocks,
105 std::forward<Func &&>(func), post_order_traversal);
106 break;
108 WalkAccessPaths(path->nested_loop_semijoin_with_duplicate_removal().outer,
109 join, cross_query_blocks, std::forward<Func &&>(func),
110 post_order_traversal);
111 WalkAccessPaths(path->nested_loop_semijoin_with_duplicate_removal().inner,
112 join, cross_query_blocks, std::forward<Func &&>(func),
113 post_order_traversal);
114 break;
116 WalkAccessPaths(path->bka_join().outer, join, cross_query_blocks,
117 std::forward<Func &&>(func), post_order_traversal);
118 WalkAccessPaths(path->bka_join().inner, join, cross_query_blocks,
119 std::forward<Func &&>(func), post_order_traversal);
120 break;
122 WalkAccessPaths(path->hash_join().outer, join, cross_query_blocks,
123 std::forward<Func &&>(func), post_order_traversal);
124 WalkAccessPaths(path->hash_join().inner, join, cross_query_blocks,
125 std::forward<Func &&>(func), post_order_traversal);
126 break;
128 WalkAccessPaths(path->filter().child, join, cross_query_blocks,
129 std::forward<Func &&>(func), post_order_traversal);
130 break;
131 case AccessPath::SORT:
132 WalkAccessPaths(path->sort().child, join, cross_query_blocks,
133 std::forward<Func &&>(func), post_order_traversal);
134 break;
136 WalkAccessPaths(path->aggregate().child, join, cross_query_blocks,
137 std::forward<Func &&>(func), post_order_traversal);
138 break;
140 WalkAccessPaths(path->temptable_aggregate().subquery_path, join,
141 cross_query_blocks, std::forward<Func &&>(func),
142 post_order_traversal);
143 WalkAccessPaths(path->temptable_aggregate().table_path, join,
144 cross_query_blocks, std::forward<Func &&>(func),
145 post_order_traversal);
146 break;
148 WalkAccessPaths(path->limit_offset().child, join, cross_query_blocks,
149 std::forward<Func &&>(func), post_order_traversal);
150 break;
152 if (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_TREE ||
153 (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_QUERY_BLOCK &&
154 path->stream().join == join)) {
155 WalkAccessPaths(path->stream().child, path->stream().join,
156 cross_query_blocks, std::forward<Func &&>(func),
157 post_order_traversal);
158 }
159 break;
161 WalkAccessPaths(path->materialize().table_path, join, cross_query_blocks,
162 std::forward<Func &&>(func), post_order_traversal);
163 for (const MaterializePathParameters::QueryBlock &query_block :
164 path->materialize().param->query_blocks) {
165 if (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_TREE ||
166 (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_QUERY_BLOCK &&
167 query_block.join == join)) {
168 WalkAccessPaths(query_block.subquery_path, query_block.join,
169 cross_query_blocks, std::forward<Func &&>(func),
170 post_order_traversal);
171 }
172 }
173 break;
175 WalkAccessPaths(path->materialize_information_schema_table().table_path,
176 join, cross_query_blocks, std::forward<Func &&>(func),
177 post_order_traversal);
178 break;
180 if (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_TREE) {
181 for (const AppendPathParameters &child : *path->append().children) {
182 WalkAccessPaths(child.path, child.join, cross_query_blocks,
183 std::forward<Func &&>(func), post_order_traversal);
184 }
185 }
186 break;
188 WalkAccessPaths(path->window().child, join, cross_query_blocks,
189 std::forward<Func &&>(func), post_order_traversal);
190 break;
192 WalkAccessPaths(path->weedout().child, join, cross_query_blocks,
193 std::forward<Func &&>(func), post_order_traversal);
194 break;
196 WalkAccessPaths(path->remove_duplicates().child, join, cross_query_blocks,
197 std::forward<Func &&>(func), post_order_traversal);
198 break;
200 WalkAccessPaths(path->remove_duplicates_on_index().child, join,
201 cross_query_blocks, std::forward<Func &&>(func),
202 post_order_traversal);
203 break;
205 WalkAccessPaths(path->alternative().child, join, cross_query_blocks,
206 std::forward<Func &&>(func), post_order_traversal);
207 break;
209 WalkAccessPaths(path->cache_invalidator().child, join, cross_query_blocks,
210 std::forward<Func &&>(func), post_order_traversal);
211 break;
213 for (AccessPath *child : *path->index_merge().children) {
214 WalkAccessPaths(child, join, cross_query_blocks,
215 std::forward<Func &&>(func), post_order_traversal);
216 }
217 break;
219 for (AccessPath *child : *path->rowid_intersection().children) {
220 WalkAccessPaths(child, join, cross_query_blocks,
221 std::forward<Func &&>(func), post_order_traversal);
222 }
223 break;
225 for (AccessPath *child : *path->rowid_union().children) {
226 WalkAccessPaths(child, join, cross_query_blocks,
227 std::forward<Func &&>(func), post_order_traversal);
228 }
229 break;
231 WalkAccessPaths(path->delete_rows().child, join, cross_query_blocks,
232 std::forward<Func &&>(func), post_order_traversal);
233 break;
234 }
235 if (post_order_traversal) {
236 if (func(path, join)) {
237 // Stop recursing in this branch. In practice a no-op, since we are
238 // already done with this branch.
239 return;
240 }
241 }
242}
243
244/**
245 A wrapper around WalkAccessPaths() that collects all tables under
246 “root_path” and calls the given functor, stopping at materializations.
247 This is typically used to know which tables to sort or the like.
248
249 func() must have signature func(TABLE *), and return true upon error.
250 */
251template <class Func>
252void WalkTablesUnderAccessPath(AccessPath *root_path, Func &&func,
253 bool include_pruned_tables) {
255 root_path, /*join=*/nullptr,
257 [&](AccessPath *path, const JOIN *) {
258 switch (path->type) {
259 case AccessPath::TABLE_SCAN:
260 return func(path->table_scan().table);
261 case AccessPath::INDEX_SCAN:
262 return func(path->index_scan().table);
263 case AccessPath::REF:
264 return func(path->ref().table);
265 case AccessPath::REF_OR_NULL:
266 return func(path->ref_or_null().table);
267 case AccessPath::EQ_REF:
268 return func(path->eq_ref().table);
269 case AccessPath::PUSHED_JOIN_REF:
270 return func(path->pushed_join_ref().table);
271 case AccessPath::FULL_TEXT_SEARCH:
272 return func(path->full_text_search().table);
273 case AccessPath::CONST_TABLE:
274 return func(path->const_table().table);
275 case AccessPath::MRR:
276 return func(path->mrr().table);
277 case AccessPath::FOLLOW_TAIL:
278 return func(path->follow_tail().table);
279 case AccessPath::INDEX_RANGE_SCAN:
280 return func(path->index_range_scan().used_key_part[0].field->table);
281 case AccessPath::INDEX_SKIP_SCAN:
282 return func(path->index_skip_scan().table);
283 case AccessPath::GROUP_INDEX_SKIP_SCAN:
284 return func(path->group_index_skip_scan().table);
285 case AccessPath::DYNAMIC_INDEX_RANGE_SCAN:
286 return func(path->dynamic_index_range_scan().table);
287 case AccessPath::STREAM:
288 return func(path->stream().table);
289 case AccessPath::MATERIALIZE:
290 return func(path->materialize().param->table);
291 case AccessPath::MATERIALIZED_TABLE_FUNCTION:
292 return func(path->materialized_table_function().table);
293 case AccessPath::ALTERNATIVE:
294 return func(
295 path->alternative().table_scan_path->table_scan().table);
296 case AccessPath::UNQUALIFIED_COUNT:
297 // Should never be below anything that needs
298 // WalkTablesUnderAccessPath().
299 assert(false);
300 return true;
301 case AccessPath::ZERO_ROWS:
302 if (include_pruned_tables && path->zero_rows().child != nullptr) {
303 WalkTablesUnderAccessPath(path->zero_rows().child, func,
304 include_pruned_tables);
305 }
306 return false;
308 return func(path->window().temp_table);
322 case AccessPath::SORT:
331 return false;
332 }
333 assert(false);
334 return true;
335 });
336}
337
338#endif // SQL_JOIN_OPTIMIZER_WALK_ACCESS_PATHS_H
Definition: sql_optimizer.h:125
static char * path
Definition: mysqldump.cc:130
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:188
@ FOLLOW_TAIL
Definition: access_path.h:214
@ FILTER
Definition: access_path.h:238
@ PUSHED_JOIN_REF
Definition: access_path.h:210
@ ZERO_ROWS_AGGREGATED
Definition: access_path.h:227
@ AGGREGATE
Definition: access_path.h:240
@ BKA_JOIN
Definition: access_path.h:234
@ ZERO_ROWS
Definition: access_path.h:226
@ CONST_TABLE
Definition: access_path.h:212
@ GROUP_INDEX_SKIP_SCAN
Definition: access_path.h:220
@ INDEX_RANGE_SCAN
Definition: access_path.h:215
@ UNQUALIFIED_COUNT
Definition: access_path.h:229
@ EQ_REF
Definition: access_path.h:209
@ FAKE_SINGLE_ROW
Definition: access_path.h:225
@ MATERIALIZE_INFORMATION_SCHEMA_TABLE
Definition: access_path.h:245
@ WINDOW
Definition: access_path.h:247
@ REF_OR_NULL
Definition: access_path.h:208
@ MATERIALIZE
Definition: access_path.h:244
@ NESTED_LOOP_SEMIJOIN_WITH_DUPLICATE_REMOVAL
Definition: access_path.h:233
@ ROWID_UNION
Definition: access_path.h:218
@ INDEX_SKIP_SCAN
Definition: access_path.h:219
@ MRR
Definition: access_path.h:213
@ CACHE_INVALIDATOR
Definition: access_path.h:252
@ INDEX_SCAN
Definition: access_path.h:206
@ TABLE_VALUE_CONSTRUCTOR
Definition: access_path.h:224
@ WEEDOUT
Definition: access_path.h:248
@ MATERIALIZED_TABLE_FUNCTION
Definition: access_path.h:228
@ REMOVE_DUPLICATES_ON_INDEX
Definition: access_path.h:250
@ TABLE_SCAN
Definition: access_path.h:205
@ REF
Definition: access_path.h:207
@ TEMPTABLE_AGGREGATE
Definition: access_path.h:241
@ LIMIT_OFFSET
Definition: access_path.h:242
@ APPEND
Definition: access_path.h:246
@ NESTED_LOOP_JOIN
Definition: access_path.h:232
@ INDEX_MERGE
Definition: access_path.h:216
@ FULL_TEXT_SEARCH
Definition: access_path.h:211
@ ALTERNATIVE
Definition: access_path.h:251
@ STREAM
Definition: access_path.h:243
@ REMOVE_DUPLICATES
Definition: access_path.h:249
@ ROWID_INTERSECTION
Definition: access_path.h:217
@ DYNAMIC_INDEX_RANGE_SCAN
Definition: access_path.h:221
@ DELETE_ROWS
Definition: access_path.h:255
@ SORT
Definition: access_path.h:239
@ HASH_JOIN
Definition: access_path.h:235
Definition: access_path.h:161
Definition: materialize_path_parameters.h:41
void WalkAccessPaths(AccessPath *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:252