MySQL 9.0.0
Source Code Documentation
walk_access_paths.h
Go to the documentation of this file.
1/* Copyright (c) 2020, 2024, 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 designed to work 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 either included with
13 the program or referenced in the documentation.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
23
24#ifndef SQL_JOIN_OPTIMIZER_WALK_ACCESS_PATHS_H
25#define SQL_JOIN_OPTIMIZER_WALK_ACCESS_PATHS_H
26
27#include <type_traits>
28
31
33 // Stop on _any_ MATERIALIZE, STREAM or TEMPTABLE_AGGREGATE paths, even if
34 // they do not cross query blocks.
35 // Also stops on APPEND paths, which always cross query blocks.
37
38 // Stop on MATERIALIZE, STREAM, TEMPTABLE_AGGREGATE or APPEND paths that
39 // cross query blocks.
41
42 // Do not stop at any kind of access path, unless func() returns true.
44};
45
46/**
47 Traverse every access path below `path` (possibly limited to the current query
48 block with the `cross_query_blocks` parameter), calling func() for each one
49 with pre- or post-order traversal. If func() returns true, the traversal does
50 not descend into the children of the current path. For post-order traversal,
51 the children have already been traversed when func() is called, so it is too
52 late to skip them, and the return value of func() is effectively ignored.
53
54 The `join` parameter signifies what query block `path` is part of, since that
55 is not implicit from the path itself. The function will track this as it
56 changes throughout the tree (in MATERIALIZE or STREAM access paths), and
57 will give the correct value to the func() callback. It is only used by
58 WalkAccessPaths() itself if the policy is ENTIRE_QUERY_BLOCK; if not, it is
59 only used for the func() callback, and you can set it to nullptr if you wish.
60 func() must have signature func(AccessPath *, const JOIN *), or it could be
61 JOIN * if a non-const JOIN is given in.
62 */
63template <class AccessPathPtr, class Func, class JoinPtr>
64void WalkAccessPaths(AccessPathPtr path, JoinPtr join,
65 WalkAccessPathPolicy cross_query_blocks, Func &&func,
66 bool post_order_traversal = false) {
67 static_assert(
68 std::is_convertible<AccessPathPtr, const AccessPath *>::value,
69 "The “path” argument must be AccessPath * or const AccessPath *.");
70 static_assert(
71 std::is_convertible<JoinPtr, const JOIN *>::value,
72 "The “join” argument must be JOIN * or const JOIN * (or nullptr).");
73
74 if (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_QUERY_BLOCK) {
75 assert(join != nullptr);
76 }
77 if (!post_order_traversal) {
78 if (func(path, join)) {
79 // Stop recursing in this branch.
80 return;
81 }
82 }
83 switch (path->type) {
88 case AccessPath::REF:
94 case AccessPath::MRR:
106 // No children.
107 break;
109 WalkAccessPaths(path->nested_loop_join().outer, join, cross_query_blocks,
110 std::forward<Func &&>(func), post_order_traversal);
111 WalkAccessPaths(path->nested_loop_join().inner, join, cross_query_blocks,
112 std::forward<Func &&>(func), post_order_traversal);
113 break;
115 WalkAccessPaths(path->nested_loop_semijoin_with_duplicate_removal().outer,
116 join, cross_query_blocks, std::forward<Func &&>(func),
117 post_order_traversal);
118 WalkAccessPaths(path->nested_loop_semijoin_with_duplicate_removal().inner,
119 join, cross_query_blocks, std::forward<Func &&>(func),
120 post_order_traversal);
121 break;
123 WalkAccessPaths(path->bka_join().outer, join, cross_query_blocks,
124 std::forward<Func &&>(func), post_order_traversal);
125 WalkAccessPaths(path->bka_join().inner, join, cross_query_blocks,
126 std::forward<Func &&>(func), post_order_traversal);
127 break;
129 WalkAccessPaths(path->hash_join().inner, join, cross_query_blocks,
130 std::forward<Func &&>(func), post_order_traversal);
131 WalkAccessPaths(path->hash_join().outer, join, cross_query_blocks,
132 std::forward<Func &&>(func), post_order_traversal);
133 break;
135 WalkAccessPaths(path->filter().child, join, cross_query_blocks,
136 std::forward<Func &&>(func), post_order_traversal);
137 break;
138 case AccessPath::SORT:
139 WalkAccessPaths(path->sort().child, join, cross_query_blocks,
140 std::forward<Func &&>(func), post_order_traversal);
141 break;
143 WalkAccessPaths(path->aggregate().child, join, cross_query_blocks,
144 std::forward<Func &&>(func), post_order_traversal);
145 break;
147 if (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_TREE ||
148 (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_QUERY_BLOCK &&
149 path->temptable_aggregate().join == join)) {
150 WalkAccessPaths(path->temptable_aggregate().subquery_path, join,
151 cross_query_blocks, std::forward<Func &&>(func),
152 post_order_traversal);
153 }
154 WalkAccessPaths(path->temptable_aggregate().table_path, join,
155 cross_query_blocks, std::forward<Func &&>(func),
156 post_order_traversal);
157 break;
159 WalkAccessPaths(path->limit_offset().child, join, cross_query_blocks,
160 std::forward<Func &&>(func), post_order_traversal);
161 break;
163 if (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_TREE ||
164 (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_QUERY_BLOCK &&
165 path->stream().join == join)) {
166 WalkAccessPaths(path->stream().child, path->stream().join,
167 cross_query_blocks, std::forward<Func &&>(func),
168 post_order_traversal);
169 }
170 break;
172 WalkAccessPaths(path->materialize().table_path, join, cross_query_blocks,
173 std::forward<Func &&>(func), post_order_traversal);
174 for (const MaterializePathParameters::Operand &operand :
175 path->materialize().param->m_operands) {
176 if (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_TREE ||
177 (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_QUERY_BLOCK &&
178 operand.join == join)) {
179 WalkAccessPaths(operand.subquery_path, operand.join,
180 cross_query_blocks, std::forward<Func &&>(func),
181 post_order_traversal);
182 }
183 }
184 break;
186 WalkAccessPaths(path->materialize_information_schema_table().table_path,
187 join, cross_query_blocks, std::forward<Func &&>(func),
188 post_order_traversal);
189 break;
191 if (cross_query_blocks == WalkAccessPathPolicy::ENTIRE_TREE) {
192 for (const AppendPathParameters &child : *path->append().children) {
193 WalkAccessPaths(child.path, child.join, cross_query_blocks,
194 std::forward<Func &&>(func), post_order_traversal);
195 }
196 }
197 break;
199 WalkAccessPaths(path->window().child, join, cross_query_blocks,
200 std::forward<Func &&>(func), post_order_traversal);
201 break;
203 WalkAccessPaths(path->weedout().child, join, cross_query_blocks,
204 std::forward<Func &&>(func), post_order_traversal);
205 break;
207 WalkAccessPaths(path->remove_duplicates().child, join, cross_query_blocks,
208 std::forward<Func &&>(func), post_order_traversal);
209 break;
211 WalkAccessPaths(path->remove_duplicates_on_index().child, join,
212 cross_query_blocks, std::forward<Func &&>(func),
213 post_order_traversal);
214 break;
216 WalkAccessPaths(path->alternative().child, join, cross_query_blocks,
217 std::forward<Func &&>(func), post_order_traversal);
218 break;
220 WalkAccessPaths(path->cache_invalidator().child, join, cross_query_blocks,
221 std::forward<Func &&>(func), post_order_traversal);
222 break;
224 for (AccessPath *child : *path->index_merge().children) {
225 WalkAccessPaths(child, join, cross_query_blocks,
226 std::forward<Func &&>(func), post_order_traversal);
227 }
228 break;
230 for (AccessPath *child : *path->rowid_intersection().children) {
231 WalkAccessPaths(child, join, cross_query_blocks,
232 std::forward<Func &&>(func), post_order_traversal);
233 }
234 break;
236 for (AccessPath *child : *path->rowid_union().children) {
237 WalkAccessPaths(child, join, cross_query_blocks,
238 std::forward<Func &&>(func), post_order_traversal);
239 }
240 break;
242 WalkAccessPaths(path->delete_rows().child, join, cross_query_blocks,
243 std::forward<Func &&>(func), post_order_traversal);
244 break;
246 WalkAccessPaths(path->update_rows().child, join, cross_query_blocks,
247 std::forward<Func &&>(func), post_order_traversal);
248 break;
249 }
250 if (post_order_traversal) {
251 if (func(path, join)) {
252 // Stop recursing in this branch. In practice a no-op, since we are
253 // already done with this branch.
254 return;
255 }
256 }
257}
258
259/**
260 A wrapper around WalkAccessPaths() that collects all tables under
261 “root_path” and calls the given functor, stopping at materializations.
262 This is typically used to know which tables to sort or the like.
263
264 func() must have signature func(TABLE *), and return true upon error.
265 */
266template <class Func>
267void WalkTablesUnderAccessPath(AccessPath *root_path, Func &&func,
268 bool include_pruned_tables) {
270 root_path, /*join=*/nullptr,
272 [&](AccessPath *path, const JOIN *) {
273 switch (path->type) {
274 case AccessPath::TABLE_SCAN:
275 return func(path->table_scan().table);
276 case AccessPath::SAMPLE_SCAN:
277 // SampleScan can be executed only in the secondary engine.
278 return false; /* LCOV_EXCL_LINE */
279 case AccessPath::INDEX_SCAN:
280 return func(path->index_scan().table);
281 case AccessPath::INDEX_DISTANCE_SCAN:
282 return func(path->index_distance_scan().table);
283 case AccessPath::REF:
284 return func(path->ref().table);
285 case AccessPath::REF_OR_NULL:
286 return func(path->ref_or_null().table);
287 case AccessPath::EQ_REF:
288 return func(path->eq_ref().table);
289 case AccessPath::PUSHED_JOIN_REF:
290 return func(path->pushed_join_ref().table);
291 case AccessPath::FULL_TEXT_SEARCH:
292 return func(path->full_text_search().table);
293 case AccessPath::CONST_TABLE:
294 return func(path->const_table().table);
295 case AccessPath::MRR:
296 return func(path->mrr().table);
297 case AccessPath::FOLLOW_TAIL:
298 return func(path->follow_tail().table);
299 case AccessPath::INDEX_RANGE_SCAN:
300 return func(path->index_range_scan().used_key_part[0].field->table);
301 case AccessPath::INDEX_SKIP_SCAN:
302 return func(path->index_skip_scan().table);
303 case AccessPath::GROUP_INDEX_SKIP_SCAN:
304 return func(path->group_index_skip_scan().table);
305 case AccessPath::DYNAMIC_INDEX_RANGE_SCAN:
306 return func(path->dynamic_index_range_scan().table);
307 case AccessPath::STREAM:
308 return func(path->stream().table);
309 case AccessPath::MATERIALIZED_TABLE_FUNCTION:
310 return func(path->materialized_table_function().table);
311 case AccessPath::ALTERNATIVE:
312 return func(
313 path->alternative().table_scan_path->table_scan().table);
314 case AccessPath::UNQUALIFIED_COUNT:
315 // Should never be below anything that needs
316 // WalkTablesUnderAccessPath().
317 assert(false);
318 return true;
319 case AccessPath::ZERO_ROWS:
320 if (include_pruned_tables && path->zero_rows().child != nullptr) {
321 WalkTablesUnderAccessPath(path->zero_rows().child, func,
322 include_pruned_tables);
323 }
324 return false;
326 return func(path->window().temp_table);
341 case AccessPath::SORT:
351 return false;
352 }
353 assert(false);
354 return true;
355 });
356}
357
358#endif // SQL_JOIN_OPTIMIZER_WALK_ACCESS_PATHS_H
Definition: sql_optimizer.h:133
static char * path
Definition: mysqldump.cc:149
std::string join(Container cont, const std::string &delim)
join elements of an container into a string separated by a delimiter.
Definition: string.h:151
Access paths are a query planning structure that correspond 1:1 to iterators, in that an access path ...
Definition: access_path.h:213
@ FOLLOW_TAIL
Definition: access_path.h:244
@ FILTER
Definition: access_path.h:268
@ PUSHED_JOIN_REF
Definition: access_path.h:240
@ ZERO_ROWS_AGGREGATED
Definition: access_path.h:257
@ UPDATE_ROWS
Definition: access_path.h:286
@ AGGREGATE
Definition: access_path.h:270
@ BKA_JOIN
Definition: access_path.h:264
@ ZERO_ROWS
Definition: access_path.h:256
@ CONST_TABLE
Definition: access_path.h:242
@ GROUP_INDEX_SKIP_SCAN
Definition: access_path.h:250
@ SAMPLE_SCAN
Definition: access_path.h:234
@ INDEX_RANGE_SCAN
Definition: access_path.h:245
@ UNQUALIFIED_COUNT
Definition: access_path.h:259
@ EQ_REF
Definition: access_path.h:239
@ FAKE_SINGLE_ROW
Definition: access_path.h:255
@ MATERIALIZE_INFORMATION_SCHEMA_TABLE
Definition: access_path.h:275
@ WINDOW
Definition: access_path.h:277
@ REF_OR_NULL
Definition: access_path.h:238
@ MATERIALIZE
Definition: access_path.h:274
@ NESTED_LOOP_SEMIJOIN_WITH_DUPLICATE_REMOVAL
Definition: access_path.h:263
@ ROWID_UNION
Definition: access_path.h:248
@ INDEX_SKIP_SCAN
Definition: access_path.h:249
@ MRR
Definition: access_path.h:243
@ CACHE_INVALIDATOR
Definition: access_path.h:282
@ INDEX_SCAN
Definition: access_path.h:235
@ TABLE_VALUE_CONSTRUCTOR
Definition: access_path.h:254
@ WEEDOUT
Definition: access_path.h:278
@ MATERIALIZED_TABLE_FUNCTION
Definition: access_path.h:258
@ REMOVE_DUPLICATES_ON_INDEX
Definition: access_path.h:280
@ TABLE_SCAN
Definition: access_path.h:233
@ REF
Definition: access_path.h:237
@ TEMPTABLE_AGGREGATE
Definition: access_path.h:271
@ LIMIT_OFFSET
Definition: access_path.h:272
@ APPEND
Definition: access_path.h:276
@ NESTED_LOOP_JOIN
Definition: access_path.h:262
@ INDEX_MERGE
Definition: access_path.h:246
@ FULL_TEXT_SEARCH
Definition: access_path.h:241
@ ALTERNATIVE
Definition: access_path.h:281
@ STREAM
Definition: access_path.h:273
@ REMOVE_DUPLICATES
Definition: access_path.h:279
@ ROWID_INTERSECTION
Definition: access_path.h:247
@ DYNAMIC_INDEX_RANGE_SCAN
Definition: access_path.h:251
@ DELETE_ROWS
Definition: access_path.h:285
@ SORT
Definition: access_path.h:269
@ INDEX_DISTANCE_SCAN
Definition: access_path.h:236
@ HASH_JOIN
Definition: access_path.h:265
Definition: access_path.h:178
Definition: materialize_path_parameters.h:42
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:64
WalkAccessPathPolicy
Definition: walk_access_paths.h:32
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:267