1 /* Copyright (c) 2000, 2020, Oracle and/or its affiliates. All rights reserved.
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 /**
24 @file
25 Implementations of basic iterators, ie. those that have no children
26 and don't take any refs (they typically read directly from a table
27 in some way). See row_iterator.h.
28 */
29
30 #include "sql/records.h"
31
32 #include <string.h>
33 #include <algorithm>
34 #include <atomic>
35 #include <new>
36
37 #include "my_base.h"
38 #include "my_dbug.h"
39 #include "my_inttypes.h"
40 #include "my_sys.h"
41 #include "sql/debug_sync.h"
42 #include "sql/handler.h"
43 #include "sql/item.h"
44 #include "sql/key.h"
45 #include "sql/opt_explain.h"
46 #include "sql/opt_range.h" // QUICK_SELECT_I
47 #include "sql/sql_class.h" // THD
48 #include "sql/sql_const.h"
49 #include "sql/sql_executor.h"
50 #include "sql/sql_optimizer.h"
51 #include "sql/sql_sort.h"
52 #include "sql/sql_tmp_table.h"
53 #include "sql/table.h"
54 #include "sql/timing_iterator.h"
55
56 using std::string;
57 using std::vector;
58
59 /**
60 Initialize a row iterator to perform full index scan in desired
61 direction using the RowIterator interface
62
63 This function has been added at late stage and is used only by
64 UPDATE/DELETE. Other statements perform index scans using IndexScanIterator.
65
66 @param thd Thread handle
67 @param table Table to be accessed
68 @param idx index to scan
69 @param reverse Scan in the reverse direction
70 @param qep_tab If not NULL, used for record buffer and pushed condition
71
72 @retval true error
73 @retval false success
74 */
75
create_table_iterator_idx(THD * thd,TABLE * table,uint idx,bool reverse,QEP_TAB * qep_tab)76 unique_ptr_destroy_only<RowIterator> create_table_iterator_idx(
77 THD *thd, TABLE *table, uint idx, bool reverse, QEP_TAB *qep_tab) {
78 empty_record(table);
79
80 ha_rows *examined_rows = nullptr;
81 if (qep_tab != nullptr && qep_tab->join() != nullptr) {
82 examined_rows = &qep_tab->join()->examined_rows;
83 }
84
85 if (reverse) {
86 return NewIterator<IndexScanIterator<true>>(thd, table, idx,
87 /*use_order=*/true, qep_tab,
88 examined_rows);
89 } else {
90 return NewIterator<IndexScanIterator<false>>(thd, table, idx,
91 /*use_order=*/true, qep_tab,
92 examined_rows);
93 }
94 }
95
96 template <bool Reverse>
IndexScanIterator(THD * thd,TABLE * table,int idx,bool use_order,QEP_TAB * qep_tab,ha_rows * examined_rows)97 IndexScanIterator<Reverse>::IndexScanIterator(THD *thd, TABLE *table, int idx,
98 bool use_order, QEP_TAB *qep_tab,
99 ha_rows *examined_rows)
100 : TableRowIterator(thd, table),
101 m_record(table->record[0]),
102 m_idx(idx),
103 m_use_order(use_order),
104 m_qep_tab(qep_tab),
105 m_examined_rows(examined_rows) {}
106
107 template <bool Reverse>
~IndexScanIterator()108 IndexScanIterator<Reverse>::~IndexScanIterator() {
109 if (table() && table()->key_read) {
110 table()->set_keyread(false);
111 }
112 }
113
114 template <bool Reverse>
Init()115 bool IndexScanIterator<Reverse>::Init() {
116 if (!table()->file->inited) {
117 if (table()->covering_keys.is_set(m_idx) && !table()->no_keyread) {
118 table()->set_keyread(true);
119 }
120
121 int error = table()->file->ha_index_init(m_idx, m_use_order);
122 if (error) {
123 PrintError(error);
124 return true;
125 }
126
127 if (set_record_buffer(m_qep_tab)) {
128 return true;
129 }
130 }
131 m_first = true;
132 return false;
133 }
134
135 // Doxygen gets confused by the explicit specializations.
136
137 //! @cond
138 template <>
Read()139 int IndexScanIterator<false>::Read() { // Forward read.
140 int error;
141 if (m_first) {
142 error = table()->file->ha_index_first(m_record);
143 m_first = false;
144 } else {
145 error = table()->file->ha_index_next(m_record);
146 }
147 if (error) return HandleError(error);
148 if (m_examined_rows != nullptr) {
149 ++*m_examined_rows;
150 }
151 return 0;
152 }
153
154 template <>
Read()155 int IndexScanIterator<true>::Read() { // Backward read.
156 int error;
157 if (m_first) {
158 error = table()->file->ha_index_last(m_record);
159 m_first = false;
160 } else {
161 error = table()->file->ha_index_prev(m_record);
162 }
163 if (error) return HandleError(error);
164 if (m_examined_rows != nullptr) {
165 ++*m_examined_rows;
166 }
167 return 0;
168 }
169 //! @endcond
170
171 template <bool Reverse>
DebugString() const172 vector<string> IndexScanIterator<Reverse>::DebugString() const {
173 DBUG_ASSERT(table()->file->pushed_idx_cond == nullptr);
174
175 const KEY *key = &table()->key_info[m_idx];
176 string str =
177 string("Index scan on ") + table()->alias + " using " + key->name;
178 if (Reverse) {
179 str += " (reverse)";
180 }
181 str += table()->file->explain_extra();
182 return {str};
183 }
184
185 template class IndexScanIterator<true>;
186 template class IndexScanIterator<false>;
187
188 /**
189 setup_read_record is used to scan by using a number of different methods.
190 Which method to use is set-up in this call so that you can fetch rows
191 through the resulting row iterator afterwards.
192
193 @param thd Thread handle
194 @param table Table the data [originally] comes from; if NULL,
195 'table' is inferred from 'qep_tab'; if non-NULL, 'qep_tab' must be NULL.
196 @param qep_tab QEP_TAB for 'table', if there is one; we may use
197 qep_tab->quick() as data source
198 @param disable_rr_cache
199 Don't use caching in SortBufferIndirectIterator (used by sort-union
200 index-merge which produces rowid sequences that are already ordered)
201 @param ignore_not_found_rows
202 Ignore any rows not found in reference tables, as they may already have
203 been deleted by foreign key handling. Only relevant for methods that need
204 to look up rows in tables (those marked “Indirect”).
205 @param examined_rows
206 If non-nullptr, the iterator will increase this variable by the number of
207 examined rows. If nullptr, will use qep_tab->join()->examined_rows
208 if possible.
209 @param using_table_scan
210 If non-nullptr, will be whether a TableScanIterator was chosen.
211 */
create_table_iterator(THD * thd,TABLE * table,QEP_TAB * qep_tab,bool disable_rr_cache,bool ignore_not_found_rows,ha_rows * examined_rows,bool * using_table_scan)212 unique_ptr_destroy_only<RowIterator> create_table_iterator(
213 THD *thd, TABLE *table, QEP_TAB *qep_tab, bool disable_rr_cache,
214 bool ignore_not_found_rows, ha_rows *examined_rows,
215 bool *using_table_scan) {
216 // If only 'table' is given, assume no quick, no condition.
217 DBUG_ASSERT(!(table && qep_tab));
218 if (!table) table = qep_tab->table();
219 empty_record(table);
220 if (using_table_scan != nullptr) {
221 *using_table_scan = false;
222 }
223
224 if (examined_rows == nullptr && qep_tab != nullptr &&
225 qep_tab->join() != nullptr) {
226 examined_rows = &qep_tab->join()->examined_rows;
227 }
228
229 QUICK_SELECT_I *quick = qep_tab ? qep_tab->quick() : nullptr;
230 if (table->unique_result.io_cache &&
231 my_b_inited(table->unique_result.io_cache)) {
232 DBUG_PRINT("info", ("using SortFileIndirectIterator"));
233 unique_ptr_destroy_only<RowIterator> iterator =
234 NewIterator<SortFileIndirectIterator>(
235 thd, table, table->unique_result.io_cache, !disable_rr_cache,
236 ignore_not_found_rows, examined_rows);
237 table->unique_result.io_cache =
238 nullptr; // Now owned by SortFileIndirectIterator.
239 return iterator;
240 } else if (quick) {
241 DBUG_PRINT("info", ("using IndexRangeScanIterator"));
242 return NewIterator<IndexRangeScanIterator>(thd, table, quick, qep_tab,
243 examined_rows);
244 } else if (table->unique_result.has_result_in_memory()) {
245 /*
246 The Unique class never puts its results into table->sort's
247 Filesort_buffer.
248 */
249 DBUG_ASSERT(!table->unique_result.sorted_result_in_fsbuf);
250 DBUG_PRINT("info", ("using SortBufferIndirectIterator (unique)"));
251 return NewIterator<SortBufferIndirectIterator>(
252 thd, table, &table->unique_result, ignore_not_found_rows,
253 examined_rows);
254 } else if (qep_tab != nullptr && qep_tab->table_ref != nullptr &&
255 qep_tab->table_ref->is_recursive_reference()) {
256 unique_ptr_destroy_only<RowIterator> iterator =
257 NewIterator<FollowTailIterator>(thd, table, qep_tab, examined_rows);
258 qep_tab->recursive_iterator =
259 down_cast<FollowTailIterator *>(iterator->real_iterator());
260 return iterator;
261 } else {
262 DBUG_PRINT("info", ("using TableScanIterator"));
263 if (using_table_scan != nullptr) {
264 *using_table_scan = true;
265 }
266 return NewIterator<TableScanIterator>(thd, table, qep_tab, examined_rows);
267 }
268 }
269
init_table_iterator(THD * thd,TABLE * table,QEP_TAB * qep_tab,bool disable_rr_cache,bool ignore_not_found_rows)270 unique_ptr_destroy_only<RowIterator> init_table_iterator(
271 THD *thd, TABLE *table, QEP_TAB *qep_tab, bool disable_rr_cache,
272 bool ignore_not_found_rows) {
273 unique_ptr_destroy_only<RowIterator> iterator = create_table_iterator(
274 thd, table, qep_tab, disable_rr_cache, ignore_not_found_rows,
275 /*examined_rows=*/nullptr, /*using_table_scan=*/nullptr);
276 if (iterator->Init()) {
277 return nullptr;
278 }
279 return iterator;
280 }
281
282 /**
283 The default implementation of unlock-row method of RowIterator,
284 used in all access methods except EQRefIterator.
285 */
UnlockRow()286 void TableRowIterator::UnlockRow() { m_table->file->unlock_row(); }
287
SetNullRowFlag(bool is_null_row)288 void TableRowIterator::SetNullRowFlag(bool is_null_row) {
289 if (is_null_row) {
290 m_table->set_null_row();
291 } else {
292 m_table->reset_null_row();
293 }
294 }
295
HandleError(int error)296 int TableRowIterator::HandleError(int error) {
297 if (thd()->killed) {
298 thd()->send_kill_message();
299 return 1;
300 }
301
302 if (error == HA_ERR_END_OF_FILE || error == HA_ERR_KEY_NOT_FOUND) {
303 m_table->set_no_row();
304 return -1;
305 } else {
306 PrintError(error);
307 return 1;
308 }
309 }
310
PrintError(int error)311 void TableRowIterator::PrintError(int error) {
312 m_table->file->print_error(error, MYF(0));
313 }
314
StartPSIBatchMode()315 void TableRowIterator::StartPSIBatchMode() {
316 m_table->file->start_psi_batch_mode();
317 }
318
EndPSIBatchModeIfStarted()319 void TableRowIterator::EndPSIBatchModeIfStarted() {
320 m_table->file->end_psi_batch_mode_if_started();
321 }
322
children() const323 std::vector<RowIterator::Child> TableRowIterator::children() const {
324 /*
325 A TableRowIterator is normally a leaf node in the set of Iterators.
326 The exception is if a subquery was included as part of an
327 'engine_condition_pushdown'. In such cases the subquery has
328 been evaluated prior to acessing this table, and the result(s)
329 from the subquery materialized into the pushed condition.
330 Report such subqueries as children of this table.
331 */
332 Item *pushed_cond = const_cast<Item *>(table()->file->pushed_cond);
333 vector<Child> ret;
334
335 if (pushed_cond != nullptr) {
336 ForEachSubselect(
337 pushed_cond, [&ret](int select_number, bool is_dependent,
338 bool is_cacheable, RowIterator *iterator) {
339 char description[256];
340 if (is_dependent) {
341 snprintf(description, sizeof(description),
342 "Select #%d (subquery in pushed condition; dependent)",
343 select_number);
344 } else if (!is_cacheable) {
345 snprintf(description, sizeof(description),
346 "Select #%d (subquery in pushed condition; uncacheable)",
347 select_number);
348 } else {
349 snprintf(description, sizeof(description),
350 "Select #%d (subquery in pushed condition; run only once)",
351 select_number);
352 }
353 ret.push_back(Child{iterator, description});
354 });
355 }
356 return ret;
357 }
358
IndexRangeScanIterator(THD * thd,TABLE * table,QUICK_SELECT_I * quick,QEP_TAB * qep_tab,ha_rows * examined_rows)359 IndexRangeScanIterator::IndexRangeScanIterator(THD *thd, TABLE *table,
360 QUICK_SELECT_I *quick,
361 QEP_TAB *qep_tab,
362 ha_rows *examined_rows)
363 : TableRowIterator(thd, table),
364 m_quick(quick),
365 m_qep_tab(qep_tab),
366 m_examined_rows(examined_rows) {}
367
Init()368 bool IndexRangeScanIterator::Init() {
369 /*
370 Only attempt to allocate a record buffer the first time the handler is
371 initialized.
372 */
373 const bool first_init = !table()->file->inited;
374
375 int error = m_quick->reset();
376 if (error) {
377 // Ensures error status is propagated back to client.
378 (void)report_handler_error(table(), error);
379 return true;
380 }
381
382 if (first_init && table()->file->inited && set_record_buffer(m_qep_tab))
383 return true; /* purecov: inspected */
384
385 m_seen_eof = false;
386 return false;
387 }
388
Read()389 int IndexRangeScanIterator::Read() {
390 if (m_seen_eof) {
391 return -1;
392 }
393
394 int tmp;
395 while ((tmp = m_quick->get_next())) {
396 if (thd()->killed || (tmp != HA_ERR_RECORD_DELETED)) {
397 int error_code = HandleError(tmp);
398 if (error_code == -1) {
399 m_seen_eof = true;
400 }
401 return error_code;
402 }
403 }
404
405 if (m_examined_rows != nullptr) {
406 ++*m_examined_rows;
407 }
408 return 0;
409 }
410
DebugString() const411 vector<string> IndexRangeScanIterator::DebugString() const {
412 // TODO: Convert QUICK_SELECT_I to RowIterator so that we can get
413 // better outputs here (similar to dbug_dump()).
414 String str;
415 m_quick->add_info_string(&str);
416 string ret = string("Index range scan on ") + table()->alias + " using " +
417 to_string(str);
418 if (table()->file->pushed_idx_cond != nullptr) {
419 ret += ", with index condition: " +
420 ItemToString(table()->file->pushed_idx_cond);
421 }
422 ret += table()->file->explain_extra();
423 return {ret};
424 }
425
TableScanIterator(THD * thd,TABLE * table,QEP_TAB * qep_tab,ha_rows * examined_rows)426 TableScanIterator::TableScanIterator(THD *thd, TABLE *table, QEP_TAB *qep_tab,
427 ha_rows *examined_rows)
428 : TableRowIterator(thd, table),
429 m_record(table->record[0]),
430 m_qep_tab(qep_tab),
431 m_examined_rows(examined_rows) {}
432
~TableScanIterator()433 TableScanIterator::~TableScanIterator() {
434 if (table()->file != nullptr) {
435 table()->file->ha_index_or_rnd_end();
436 }
437 }
438
Init()439 bool TableScanIterator::Init() {
440 /*
441 Only attempt to allocate a record buffer the first time the handler is
442 initialized.
443 */
444 const bool first_init = !table()->file->inited;
445
446 int error = table()->file->ha_rnd_init(true);
447 if (error) {
448 PrintError(error);
449 return true;
450 }
451
452 if (first_init && set_record_buffer(m_qep_tab))
453 return true; /* purecov: inspected */
454
455 return false;
456 }
457
Read()458 int TableScanIterator::Read() {
459 int tmp;
460 while ((tmp = table()->file->ha_rnd_next(m_record))) {
461 /*
462 ha_rnd_next can return RECORD_DELETED for MyISAM when one thread is
463 reading and another deleting without locks.
464 */
465 if (tmp == HA_ERR_RECORD_DELETED && !thd()->killed) continue;
466 return HandleError(tmp);
467 }
468 if (m_examined_rows != nullptr) {
469 ++*m_examined_rows;
470 }
471 return 0;
472 }
473
DebugString() const474 vector<string> TableScanIterator::DebugString() const {
475 DBUG_ASSERT(table()->file->pushed_idx_cond == nullptr);
476 return {string("Table scan on ") + table()->alias +
477 table()->file->explain_extra()};
478 }
479
FollowTailIterator(THD * thd,TABLE * table,QEP_TAB * qep_tab,ha_rows * examined_rows)480 FollowTailIterator::FollowTailIterator(THD *thd, TABLE *table, QEP_TAB *qep_tab,
481 ha_rows *examined_rows)
482 : TableRowIterator(thd, table),
483 m_record(table->record[0]),
484 m_qep_tab(qep_tab),
485 m_examined_rows(examined_rows) {}
486
~FollowTailIterator()487 FollowTailIterator::~FollowTailIterator() {
488 if (table()->file != nullptr) {
489 table()->file->ha_index_or_rnd_end();
490 }
491 }
492
Init()493 bool FollowTailIterator::Init() {
494 // BeginMaterialization() must be called before this.
495 DBUG_ASSERT(m_stored_rows != nullptr);
496
497 /*
498 Only attempt to allocate a record buffer the first time the handler is
499 initialized.
500 */
501 const bool first_init = !table()->file->inited;
502
503 if (first_init) {
504 // Before starting a new WITH RECURSIVE execution,
505 // MaterializeIterator::Init() does ha_index_or_rnd_end() on all read
506 // cursors of recursive members, which sets file->inited = false, so we can
507 // use that as a signal.
508 if (!table()->is_created()) {
509 // Recursive references always refer to a temporary table,
510 // which do not exist at resolution time; thus, we need to
511 // connect to it on first run here.
512 if (open_tmp_table(table())) {
513 return true;
514 }
515 }
516
517 int error = table()->file->ha_rnd_init(true);
518 if (error) {
519 PrintError(error);
520 return true;
521 }
522
523 if (first_init && set_record_buffer(m_qep_tab))
524 return true; /* purecov: inspected */
525
526 // The first seen record will start a new iteration.
527 m_read_rows = 0;
528 m_recursive_iteration_count = 0;
529 m_end_of_current_iteration = 0;
530 } else {
531 // Just continue where we left off last time.
532 }
533
534 return false;
535 }
536
Read()537 int FollowTailIterator::Read() {
538 if (m_read_rows == *m_stored_rows) {
539 /*
540 Return EOF without even checking if there are more rows
541 (there isn't), so that we can continue reading when there are.
542 There are two underlying reasons why we need to do this,
543 depending on the storage engine in use:
544
545 1. For both MEMORY and InnoDB, when they report EOF,
546 the scan stays blocked at EOF forever even if new rows
547 are inserted later. (InnoDB has a supremum record, and
548 MEMORY increments info->current_record unconditionally.)
549
550 2. Specific to MEMORY, inserting records that are deduplicated
551 away can corrupt cursors that hit EOF. Consider the following
552 scenario:
553
554 - write 'A'
555 - write 'A': allocates a record, hits a duplicate key error, leaves
556 the allocated place as "deleted record".
557 - init scan
558 - read: finds 'A' at #0
559 - read: finds deleted record at #1, properly skips over it, moves to
560 EOF
561 - even if we save the read position at this point, it's "after #1"
562 - close scan
563 - write 'B': takes the place of deleted record, i.e. writes at #1
564 - write 'C': writes at #2
565 - init scan, reposition at saved position
566 - read: still after #1, so misses 'B'.
567
568 In this scenario, the table is formed of real records followed by
569 deleted records and then EOF.
570
571 To avoid these problems, we keep track of the number of rows in the
572 table by holding the m_stored_rows pointer into the MaterializeIterator,
573 and simply avoid hitting EOF.
574 */
575 return -1;
576 }
577
578 if (m_read_rows == m_end_of_current_iteration) {
579 // We have started a new iteration. Check to see if we have passed the
580 // user-set limit.
581 if (++m_recursive_iteration_count >
582 thd()->variables.cte_max_recursion_depth) {
583 my_error(ER_CTE_MAX_RECURSION_DEPTH, MYF(0), m_recursive_iteration_count);
584 return 1;
585 }
586 m_end_of_current_iteration = *m_stored_rows;
587
588 #ifdef ENABLED_DEBUG_SYNC
589 if (m_recursive_iteration_count == 4) {
590 DEBUG_SYNC(thd(), "in_WITH_RECURSIVE");
591 }
592 #endif
593 }
594
595 // Read the actual row.
596 //
597 // We can never have MyISAM here, so we don't need the checks
598 // for HA_ERR_RECORD_DELETED that TableScanIterator has.
599 int err = table()->file->ha_rnd_next(m_record);
600 if (err) {
601 return HandleError(err);
602 }
603
604 ++m_read_rows;
605
606 if (m_examined_rows != nullptr) {
607 ++*m_examined_rows;
608 }
609 return 0;
610 }
611
DebugString() const612 vector<string> FollowTailIterator::DebugString() const {
613 DBUG_ASSERT(table()->file->pushed_idx_cond == nullptr);
614 return {string("Scan new records on ") + table()->alias};
615 }
616
RepositionCursorAfterSpillToDisk()617 bool FollowTailIterator::RepositionCursorAfterSpillToDisk() {
618 return reposition_innodb_cursor(table(), m_read_rows);
619 }
620