1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
/* Copyright (c) 2000, 2025, Oracle and/or its affiliates.
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License, version 2.0,
as published by the Free Software Foundation.
This program is designed to work with certain software (including
but not limited to OpenSSL) that is licensed under separate terms,
as designated in a particular file or component or in included license
documentation. The authors of MySQL hereby grant you an additional
permission to link the program and your derivative works with the
separately licensed software that they have either included with
the program or referenced in the documentation.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License, version 2.0, for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
#ifndef SQL_RANGE_OPTIMIZER_ROWID_ORDERED_RETRIEVAL_H_
#define SQL_RANGE_OPTIMIZER_ROWID_ORDERED_RETRIEVAL_H_
#include <assert.h>
#include <sys/types.h>
#include <vector>
#include "my_alloc.h"
#include "my_inttypes.h"
#include "priority_queue.h"
#include "sql/handler.h"
#include "sql/malloc_allocator.h"
#include "sql/range_optimizer/index_range_scan.h"
#include "sql/range_optimizer/range_optimizer.h"
#include "sql/sql_list.h"
#include "sql/table.h"
class String;
class THD;
struct MY_BITMAP;
/*
Rowid-Ordered Retrieval (ROR) index intersection quick select.
This quick select produces intersection of row sequences returned
by several IndexRangeScanIterators it "merges".
All merged IndexRangeScanIterators must return rowids in rowid order.
RowIDIntersectionIterator will return rows in rowid order, too.
All merged quick selects retrieve {rowid, covered_fields} tuples (not full
table records).
RowIDIntersectionIterator retrieves full records if it is not being used
by RowIDUnionIterator and all merged quick selects together don't
cover needed all fields.
If one of the merged quick selects is a Clustered PK range scan, it is
used only to filter rowid sequence produced by other merged quick selects.
*/
class RowIDIntersectionIterator : public RowIDCapableRowIterator {
public:
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);
~RowIDIntersectionIterator() override;
bool Init() override;
int Read() override;
uchar *last_rowid() const override {
assert(need_rows_in_rowid_order);
return m_last_rowid;
}
private:
/*
Range quick selects this intersection consists of, not including
cpk_quick.
*/
Mem_root_array<unique_ptr_destroy_only<RowIterator>> m_children;
/*
Merged quick select that uses Clustered PK, if there is one. This quick
select is not used for row retrieval, it is used for row retrieval.
*/
unique_ptr_destroy_only<RowIterator> m_cpk_child;
/*
If true, do retrieve full table rows.
The way this works is somewhat convoluted; this is my (sgunders')
understanding as of September 2021:
For covering indexes (for some complicated value of “covering” if there are
multiple indexes involved), we always use index-only scans; otherwise,
the index range scan uses a normal scan (table->file->set_keyread(false)),
which does first a lookup into the index, and then the secondary lookup to
get the actual row.
However, for intersection scans, we don't actually need all sub-scans to
fetch the actual row; that's just a waste, especially since in most cases,
we won't need the row. So in this case, the _intention_ is that we'd always
turn on index-only scans, although it seems the code for this was never
written. The idea is that the intersection iterator then is responsible for
doing a kind of “fetch after the fact” once the intersection has yielded a
row (unless we're covering). This is done by
table->file->ha_rnd_pos(table->record[0], rowid);
although index merge uses position() instead of ha_rnd_pos().
Both seem to have the (undocumented?) side effect of actually fetching the
row even on an index-only scan. This is the reason why we need the
intersection iterator to reuse the handler reuse for MyISAM; otherwise, we'd
never actually get the row, since it's stored privately in MI_INFO and not
in the row ID.
But if there's something above the intersection scan again (which can only
be a union), it's the same game; when we find a row, it might be a duplicate
of the same row ID from another sub-iterator of the union (whether a range
scan or an intersection of range scans), and then it's not worth it to fetch
the entire row. So that's why the intersection scan needs to be told “no,
don't do ha_rnd_pos; your parent will be doing that if it's interested”. And
that is what this variable is for.
*/
bool retrieve_full_rows;
/* in top-level quick select, true if merged scans where initialized */
bool scans_inited;
const bool need_rows_in_rowid_order;
uchar *m_last_rowid;
bool inited = false;
bool init_ror_merged_scan();
};
/*
Comparison function to be used RowIDUnionIterator::queue priority
queue.
*/
struct Quick_ror_union_less {
explicit Quick_ror_union_less(const handler *file) : m_file(file) {}
bool operator()(RowIterator *a, RowIterator *b) {
RowIDCapableRowIterator *real_a =
down_cast<RowIDCapableRowIterator *>(a->real_iterator());
RowIDCapableRowIterator *real_b =
down_cast<RowIDCapableRowIterator *>(b->real_iterator());
return m_file->cmp_ref(real_a->last_rowid(), real_b->last_rowid()) > 0;
}
const handler *m_file;
};
/*
Rowid-Ordered Retrieval index union select.
This quick select produces union of row sequences returned by several
quick select it "merges".
All merged quick selects must return rowids in rowid order.
RowIDUnionIterator will return rows in rowid order, too.
All merged quick selects are set not to retrieve full table records.
ROR-union quick select always retrieves full records.
*/
class RowIDUnionIterator : public TableRowIterator {
public:
RowIDUnionIterator(
THD *thd, MEM_ROOT *return_mem_root, TABLE *table,
Mem_root_array<unique_ptr_destroy_only<RowIterator>> children);
~RowIDUnionIterator() override;
bool Init() override;
int Read() override;
private:
Mem_root_array<unique_ptr_destroy_only<RowIterator>> m_children;
Priority_queue<RowIterator *,
std::vector<RowIterator *, Malloc_allocator<RowIterator *>>,
Quick_ror_union_less>
queue; /* Priority queue for merge operation */
MEM_ROOT *mem_root; /* Memory pool for this and merged quick selects data. */
uchar *cur_rowid; /* buffer used in Read() */
uchar *prev_rowid; /* rowid of last row returned by Read() */
bool have_prev_rowid; /* true if prev_rowid has valid data */
uint rowid_length; /* table rowid length */
bool scans_inited;
bool inited = false;
};
#endif // SQL_RANGE_OPTIMIZER_ROWID_ORDERED_RETRIEVAL_H_
|
