MySQL 8.3.0
Source Code Documentation
rowid_ordered_retrieval.h
Go to the documentation of this file.
1/* Copyright (c) 2000, 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_RANGE_OPTIMIZER_ROWID_ORDERED_RETRIEVAL_H_
24#define SQL_RANGE_OPTIMIZER_ROWID_ORDERED_RETRIEVAL_H_
25
26#include <assert.h>
27#include <sys/types.h>
28#include <vector>
29
30#include "my_alloc.h"
31#include "my_inttypes.h"
32#include "priority_queue.h"
33#include "sql/handler.h"
37#include "sql/sql_list.h"
38#include "sql/table.h"
39
40class String;
41class THD;
42struct MY_BITMAP;
43
44/*
45 Rowid-Ordered Retrieval (ROR) index intersection quick select.
46 This quick select produces intersection of row sequences returned
47 by several IndexRangeScanIterators it "merges".
48
49 All merged IndexRangeScanIterators must return rowids in rowid order.
50 RowIDIntersectionIterator will return rows in rowid order, too.
51
52 All merged quick selects retrieve {rowid, covered_fields} tuples (not full
53 table records).
54 RowIDIntersectionIterator retrieves full records if it is not being used
55 by RowIDUnionIterator and all merged quick selects together don't
56 cover needed all fields.
57
58 If one of the merged quick selects is a Clustered PK range scan, it is
59 used only to filter rowid sequence produced by other merged quick selects.
60*/
61
63 public:
65 THD *thd, MEM_ROOT *return_mem_root, TABLE *table_arg,
70
71 bool Init() override;
72 int Read() override;
73 uchar *last_rowid() const override {
75 return m_last_rowid;
76 }
77
78 private:
79 /*
80 Range quick selects this intersection consists of, not including
81 cpk_quick.
82 */
84
85 /*
86 Merged quick select that uses Clustered PK, if there is one. This quick
87 select is not used for row retrieval, it is used for row retrieval.
88 */
90
91 /*
92 If true, do retrieve full table rows.
93
94 The way this works is somewhat convoluted; this is my (sgunders')
95 understanding as of September 2021:
96
97 For covering indexes (for some complicated value of “covering” if there are
98 multiple indexes involved), we always use index-only scans; otherwise,
99 the index range scan uses a normal scan (table->file->set_keyread(false)),
100 which does first a lookup into the index, and then the secondary lookup to
101 get the actual row.
102
103 However, for intersection scans, we don't actually need all sub-scans to
104 fetch the actual row; that's just a waste, especially since in most cases,
105 we won't need the row. So in this case, the _intention_ is that we'd always
106 turn on index-only scans, although it seems the code for this was never
107 written. The idea is that the intersection iterator then is responsible for
108 doing a kind of “fetch after the fact” once the intersection has yielded a
109 row (unless we're covering). This is done by
110
111 table->file->ha_rnd_pos(table->record[0], rowid);
112
113 although index merge uses position() instead of ha_rnd_pos().
114 Both seem to have the (undocumented?) side effect of actually fetching the
115 row even on an index-only scan. This is the reason why we need the
116 intersection iterator to reuse the handler reuse for MyISAM; otherwise, we'd
117 never actually get the row, since it's stored privately in MI_INFO and not
118 in the row ID.
119
120 But if there's something above the intersection scan again (which can only
121 be a union), it's the same game; when we find a row, it might be a duplicate
122 of the same row ID from another sub-iterator of the union (whether a range
123 scan or an intersection of range scans), and then it's not worth it to fetch
124 the entire row. So that's why the intersection scan needs to be told “no,
125 don't do ha_rnd_pos; your parent will be doing that if it's interested”. And
126 that is what this variable is for.
127 */
129
130 /* in top-level quick select, true if merged scans where initialized */
132
135 bool inited = false;
136
138};
139
140/*
141 Comparison function to be used RowIDUnionIterator::queue priority
142 queue.
143*/
148 down_cast<RowIDCapableRowIterator *>(a->real_iterator());
150 down_cast<RowIDCapableRowIterator *>(b->real_iterator());
151 return m_file->cmp_ref(real_a->last_rowid(), real_b->last_rowid()) > 0;
152 }
154};
155
156/*
157 Rowid-Ordered Retrieval index union select.
158 This quick select produces union of row sequences returned by several
159 quick select it "merges".
160
161 All merged quick selects must return rowids in rowid order.
162 RowIDUnionIterator will return rows in rowid order, too.
163
164 All merged quick selects are set not to retrieve full table records.
165 ROR-union quick select always retrieves full records.
166
167*/
168
170 public:
172 THD *thd, MEM_ROOT *return_mem_root, TABLE *table,
174 ~RowIDUnionIterator() override;
175
176 bool Init() override;
177 int Read() override;
178
179 private:
181
183 std::vector<RowIterator *, Malloc_allocator<RowIterator *>>,
185 queue; /* Priority queue for merge operation */
186
187 MEM_ROOT *mem_root; /* Memory pool for this and merged quick selects data. */
188 uchar *cur_rowid; /* buffer used in Read() */
189 uchar *prev_rowid; /* rowid of last row returned by Read() */
190 bool have_prev_rowid; /* true if prev_rowid has valid data */
191 uint rowid_length; /* table rowid length */
192
194 bool inited = false;
195};
196
197#endif // SQL_RANGE_OPTIMIZER_ROWID_ORDERED_RETRIEVAL_H_
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:425
Implements a priority queue using a vector-based max-heap.
Definition: priority_queue.h:103
An interface for RowIterators that have a given row ID, ie., they can be children in ROR (rowid-order...
Definition: rowid_capable_row_iterator.h:35
virtual uchar * last_rowid() const =0
Definition: rowid_ordered_retrieval.h:62
int Read() override
Read a single row.
Definition: rowid_ordered_retrieval.cc:322
bool init_ror_merged_scan()
Definition: rowid_ordered_retrieval.cc:169
const bool need_rows_in_rowid_order
Definition: rowid_ordered_retrieval.h:133
bool inited
Definition: rowid_ordered_retrieval.h:135
RowIDIntersectionIterator(THD *thd, MEM_ROOT *return_mem_root, TABLE *table_arg, bool retrieve_full_rows, bool need_rows_in_rowid_order, Mem_root_array< unique_ptr_destroy_only< RowIterator > > children, unique_ptr_destroy_only< RowIterator > cpk_child)
Definition: rowid_ordered_retrieval.cc:47
Mem_root_array< unique_ptr_destroy_only< RowIterator > > m_children
Definition: rowid_ordered_retrieval.h:83
uchar * m_last_rowid
Definition: rowid_ordered_retrieval.h:134
uchar * last_rowid() const override
Definition: rowid_ordered_retrieval.h:73
unique_ptr_destroy_only< RowIterator > m_cpk_child
Definition: rowid_ordered_retrieval.h:89
~RowIDIntersectionIterator() override
Definition: rowid_ordered_retrieval.cc:225
bool Init() override
Initialize or reinitialize the iterator.
Definition: rowid_ordered_retrieval.cc:198
bool retrieve_full_rows
Definition: rowid_ordered_retrieval.h:128
bool scans_inited
Definition: rowid_ordered_retrieval.h:131
Definition: rowid_ordered_retrieval.h:169
uchar * cur_rowid
Definition: rowid_ordered_retrieval.h:188
Priority_queue< RowIterator *, std::vector< RowIterator *, Malloc_allocator< RowIterator * > >, Quick_ror_union_less > queue
Definition: rowid_ordered_retrieval.h:185
uint rowid_length
Definition: rowid_ordered_retrieval.h:191
Mem_root_array< unique_ptr_destroy_only< RowIterator > > m_children
Definition: rowid_ordered_retrieval.h:180
RowIDUnionIterator(THD *thd, MEM_ROOT *return_mem_root, TABLE *table, Mem_root_array< unique_ptr_destroy_only< RowIterator > > children)
Definition: rowid_ordered_retrieval.cc:229
~RowIDUnionIterator() override
Definition: rowid_ordered_retrieval.cc:293
bool have_prev_rowid
Definition: rowid_ordered_retrieval.h:190
bool inited
Definition: rowid_ordered_retrieval.h:194
bool scans_inited
Definition: rowid_ordered_retrieval.h:193
uchar * prev_rowid
Definition: rowid_ordered_retrieval.h:189
int Read() override
Read a single row.
Definition: rowid_ordered_retrieval.cc:433
bool Init() override
Initialize or reinitialize the iterator.
Definition: rowid_ordered_retrieval.cc:241
MEM_ROOT * mem_root
Definition: rowid_ordered_retrieval.h:187
A context for reading through a single table using a chosen access method: index read,...
Definition: row_iterator.h:81
THD * thd() const
Definition: row_iterator.h:227
virtual RowIterator * real_iterator()
If this iterator is wrapping a different iterator (e.g.
Definition: row_iterator.h:223
Using this class is fraught with peril, and you need to be very careful when doing so.
Definition: sql_string.h:166
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_lexer_thd.h:35
Definition: row_iterator.h:233
TABLE * table() const
Definition: row_iterator.h:245
The handler class is the interface for dynamically loadable storage engines.
Definition: handler.h:4548
virtual int cmp_ref(const uchar *ref1, const uchar *ref2) const
Compare two positions.
Definition: handler.h:6084
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...
std::unique_ptr< T, Destroy_only< T > > unique_ptr_destroy_only
std::unique_ptr, but only destroying.
Definition: my_alloc.h:476
Some integer typedefs for easier portability.
unsigned char uchar
Definition: my_inttypes.h:51
Definition: os0file.h:88
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:82
Definition: my_bitmap.h:42
Definition: rowid_ordered_retrieval.h:144
const handler * m_file
Definition: rowid_ordered_retrieval.h:153
Quick_ror_union_less(const handler *file)
Definition: rowid_ordered_retrieval.h:145
bool operator()(RowIterator *a, RowIterator *b)
Definition: rowid_ordered_retrieval.h:146
Definition: table.h:1403