MySQL 8.1.0
Source Code Documentation
index.h
Go to the documentation of this file.
1/* Copyright (c) 2016, 2023, Oracle and/or its affiliates.
2
3This program is free software; you can redistribute it and/or modify it under
4the terms of the GNU General Public License, version 2.0, as published by the
5Free Software Foundation.
6
7This program is also distributed with certain software (including but not
8limited to OpenSSL) that is licensed under separate terms, as designated in a
9particular file or component or in included license documentation. The authors
10of MySQL hereby grant you an additional permission to link the program and
11your derivative works with the separately licensed software that they have
12included with MySQL.
13
14This program is distributed in the hope that it will be useful, but WITHOUT
15ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
16FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
17for more details.
18
19You should have received a copy of the GNU General Public License along with
20this program; if not, write to the Free Software Foundation, Inc.,
2151 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
22
23/** @file storage/temptable/include/temptable/index.h
24TempTable Index declarations. */
25
26#ifndef TEMPTABLE_INDEX_H
27#define TEMPTABLE_INDEX_H
28
29#include <assert.h>
30
31#include "sql/key.h"
38
39namespace temptable {
40
41class Table;
42
43/** Index interface. */
44class Index {
45 public:
46 /** Index lookup (search) result. */
47 enum class Lookup {
48 /** The searched for indexed cells were found and the cursor is
49 * positioned
50 * on them. */
51 FOUND,
52
53 /** The searched for indexed cells were not found and the cursor is
54 * positioned on the next indexed cells in index order. */
56
57 /** The searched for indexed cells were not found and the cursor
58 * position is undefined. */
60 };
61
62 /** Constructor. */
63 Index(
64 /** [in] Table where this index belongs, used only for fetching metadata
65 * of its columns. */
66 const Table &table,
67 /** [in] MySQL index, for querying metadata. */
68 const KEY &mysql_index);
69
70 /** Destructor. */
71 virtual ~Index();
72
73 /** Insert a new entry into the index.
74 * @return Result::OK or another Result::* error code */
75 virtual Result insert(
76 /** [in] Indexed cells to insert. */
77 const Indexed_cells &indexed_cells,
78 /** [out] If insert succeeds (Result::OK) this will be set to the position
79 * inside the index where the new indexed cells where inserted. */
80 Cursor *insert_position) = 0;
81
82 /** Lookup (search) an indexed cells.
83 * @retval Lookup::FOUND the provided `search_cells` were found and `first`
84 * was positioned on them (the first entry, if there are duplicates).
85 * @retval Lookup::NOT_FOUND_CURSOR_POSITIONED_ON_NEXT the provided
86 * `search_cells` were not found and `first` was positioned on the next
87 * indexed cells in index order.
88 * @retval Lookup::NOT_FOUND_CURSOR_UNDEFINED the provided `search_cells` were
89 * not found and `first` is undefined. */
90 virtual Lookup lookup(
91 /** [in] Indexed cells to search for. */
92 const Indexed_cells &search_cells,
93 /** [out] First indexed cells that were found, see above. */
94 Cursor *first) const = 0;
95
96 /** Lookup (search) an indexed cells.
97 * @retval Lookup::FOUND the provided `search_cells` were found, `first`
98 * was positioned on them (the first entry, if there are duplicates) and
99 * `after_last` was positioned after the last matching entry.
100 * @retval Lookup::NOT_FOUND_CURSOR_POSITIONED_ON_NEXT the provided
101 * `search_cells` were not found and `first` and `after_last` were
102 * positioned on the next indexed cells in index order.
103 * @retval Lookup::NOT_FOUND_CURSOR_UNDEFINED the provided `search_cells` were
104 * not found and `first` and `after_last` are undefined. */
105 virtual Lookup lookup(const Indexed_cells &search_cells, Cursor *first,
106 Cursor *after_last) const = 0;
107
108 /** Erase the indexed cells pointer to by a cursor. */
109 virtual void erase(
110 /** [in] Position to erase. */
111 const Cursor &target) = 0;
112
113 /** Truncate the index, deleting all of its entries. */
114 virtual void truncate() = 0;
115
116 /** Get a cursor to the first entry.
117 * @return cursor to the first indexed cells in index order */
118 virtual Cursor begin() const = 0;
119
120 /** Get a cursor after the last entry.
121 * @return a cursor after the last indexed cells in index order */
122 virtual Cursor end() const = 0;
123
124 /** Get the number of indexed columns by this index.
125 * @return number of indexed columns */
126 size_t number_of_indexed_columns() const;
127
128 /** Get the Nth indexed column.
129 * @return the Nth indexed column */
131 /** [in] Index of the column to fetch,
132 * must be < `number_of_indexed_columns()`. */
133 size_t i) const;
134
135 /** Get the table of the index.
136 * @return table */
137 const Table &table() const;
138
139 /** Get the MySQL index structure which corresponds to this index.
140 * @return mysql index */
141 const KEY &mysql_index() const;
142
143 private:
144 /** Number of indexed columns. */
146
147 /** Table of the index. */
149
150 /** Indexed columns metadata, from [0, m_number_of_indexed_columns). */
151 std::array<Indexed_column, MAX_REF_PARTS> m_indexed_columns;
152
153 /** MySQL index. */
155};
156
157class Tree : public Index {
158 public:
160
161 Tree(const Table &table, const KEY &mysql_index,
162 const Allocator<Indexed_cells> &allocator);
163
164 Result insert(const Indexed_cells &indexed_cells,
165 Cursor *insert_position) override;
166
167 Lookup lookup(const Indexed_cells &search_cells,
168 Cursor *first) const override;
169
170 Lookup lookup(const Indexed_cells &search_cells, Cursor *first,
171 Cursor *after_last) const override;
172
173 void erase(const Cursor &target) override;
174
175 void truncate() override;
176
177 Cursor begin() const override;
178
179 Cursor end() const override;
180
183};
184
185class Hash_duplicates : public Index {
186 public:
188
190 const Allocator<Indexed_cells> &allocator);
191
192 Result insert(const Indexed_cells &indexed_cells,
193 Cursor *insert_position) override;
194
195 Lookup lookup(const Indexed_cells &search_cells,
196 Cursor *first) const override;
197
198 Lookup lookup(const Indexed_cells &search_cells, Cursor *first,
199 Cursor *after_last) const override;
200
201 void erase(const Cursor &target) override;
202
203 void truncate() override;
204
205 Cursor begin() const override;
206
207 Cursor end() const override;
208
210};
211
212class Hash_unique : public Index {
213 public:
215
216 Hash_unique(const Table &table, const KEY &mysql_index,
217 const Allocator<Indexed_cells> &allocator);
218
219 Result insert(const Indexed_cells &indexed_cells,
220 Cursor *insert_position) override;
221
222 Lookup lookup(const Indexed_cells &search_cells,
223 Cursor *first) const override;
224
225 Lookup lookup(const Indexed_cells &search_cells, Cursor *first,
226 Cursor *after_last) const override;
227
228 void erase(const Cursor &target) override;
229
230 void truncate() override;
231
232 Cursor begin() const override;
233
234 Cursor end() const override;
235
237};
238
239/* Implementation of inlined methods. */
240
241inline size_t Index::number_of_indexed_columns() const {
243}
244
245inline const Indexed_column &Index::indexed_column(size_t i) const {
246 assert(i < m_number_of_indexed_columns);
247 return m_indexed_columns[i];
248}
249
250inline const Table &Index::table() const { return m_table; }
251
252inline const KEY &Index::mysql_index() const { return *m_mysql_index; }
253
254} /* namespace temptable */
255
256#endif /* TEMPTABLE_INDEX_H */
Definition: key.h:112
Custom memory allocator.
Definition: allocator.h:353
A cursor for iterating over an Index.
Definition: cursor.h:40
Definition: index.h:185
Cursor end() const override
Get a cursor after the last entry.
Definition: index.cc:212
Lookup lookup(const Indexed_cells &search_cells, Cursor *first) const override
Lookup (search) an indexed cells.
Definition: index.cc:183
void truncate() override
Truncate the index, deleting all of its entries.
Definition: index.cc:208
Result insert(const Indexed_cells &indexed_cells, Cursor *insert_position) override
Insert a new entry into the index.
Definition: index.cc:168
Hash_duplicates(const Table &table, const KEY &mysql_index, const Allocator< Indexed_cells > &allocator)
Definition: index.cc:162
Hash_duplicates_container Container
Definition: index.h:187
Container m_hash_table
Definition: index.h:209
void erase(const Cursor &target) override
Erase the indexed cells pointer to by a cursor.
Definition: index.cc:204
Cursor begin() const override
Get a cursor to the first entry.
Definition: index.cc:210
Definition: index.h:212
void truncate() override
Truncate the index, deleting all of its entries.
Definition: index.cc:267
Hash_unique_container Container
Definition: index.h:214
Hash_unique(const Table &table, const KEY &mysql_index, const Allocator< Indexed_cells > &allocator)
Definition: index.cc:214
void erase(const Cursor &target) override
Erase the indexed cells pointer to by a cursor.
Definition: index.cc:263
Container m_hash_table
Definition: index.h:236
Cursor end() const override
Get a cursor after the last entry.
Definition: index.cc:271
Cursor begin() const override
Get a cursor to the first entry.
Definition: index.cc:269
Lookup lookup(const Indexed_cells &search_cells, Cursor *first) const override
Lookup (search) an indexed cells.
Definition: index.cc:242
Result insert(const Indexed_cells &indexed_cells, Cursor *insert_position) override
Insert a new entry into the index.
Definition: index.cc:220
Index interface.
Definition: index.h:44
virtual Lookup lookup(const Indexed_cells &search_cells, Cursor *first) const =0
Lookup (search) an indexed cells.
size_t m_number_of_indexed_columns
Number of indexed columns.
Definition: index.h:145
const KEY * m_mysql_index
MySQL index.
Definition: index.h:154
Index(const Table &table, const KEY &mysql_index)
Constructor.
Definition: index.cc:40
virtual Result insert(const Indexed_cells &indexed_cells, Cursor *insert_position)=0
Insert a new entry into the index.
Lookup
Index lookup (search) result.
Definition: index.h:47
@ NOT_FOUND_CURSOR_UNDEFINED
The searched for indexed cells were not found and the cursor position is undefined.
@ FOUND
The searched for indexed cells were found and the cursor is positioned on them.
@ NOT_FOUND_CURSOR_POSITIONED_ON_NEXT
The searched for indexed cells were not found and the cursor is positioned on the next indexed cells ...
virtual ~Index()
Destructor.
Definition: index.cc:55
virtual void erase(const Cursor &target)=0
Erase the indexed cells pointer to by a cursor.
const Table & m_table
Table of the index.
Definition: index.h:148
const Indexed_column & indexed_column(size_t i) const
Get the Nth indexed column.
Definition: index.h:245
const KEY & mysql_index() const
Get the MySQL index structure which corresponds to this index.
Definition: index.h:252
virtual void truncate()=0
Truncate the index, deleting all of its entries.
virtual Lookup lookup(const Indexed_cells &search_cells, Cursor *first, Cursor *after_last) const =0
Lookup (search) an indexed cells.
std::array< Indexed_column, MAX_REF_PARTS > m_indexed_columns
Indexed columns metadata, from [0, m_number_of_indexed_columns).
Definition: index.h:151
virtual Cursor begin() const =0
Get a cursor to the first entry.
size_t number_of_indexed_columns() const
Get the number of indexed columns by this index.
Definition: index.h:241
virtual Cursor end() const =0
Get a cursor after the last entry.
const Table & table() const
Get the table of the index.
Definition: index.h:250
Indexed cells represent one or more cells that are covered by an index.
Definition: indexed_cells.h:45
Definition: indexed_column.h:38
Definition: table.h:46
Definition: index.h:157
void erase(const Cursor &target) override
Erase the indexed cells pointer to by a cursor.
Definition: index.cc:154
Cursor begin() const override
Get a cursor to the first entry.
Definition: index.cc:158
void truncate() override
Truncate the index, deleting all of its entries.
Definition: index.cc:156
Tree_container Container
Definition: index.h:159
Tree(const Table &table, const KEY &mysql_index, const Allocator< Indexed_cells > &allocator)
Definition: index.cc:62
Result insert(const Indexed_cells &indexed_cells, Cursor *insert_position) override
Insert a new entry into the index.
Definition: index.cc:68
Lookup lookup(const Indexed_cells &search_cells, Cursor *first) const override
Lookup (search) an indexed cells.
Definition: index.cc:113
Container m_tree
Definition: index.h:181
bool m_allow_duplicates
Definition: index.h:182
Cursor end() const override
Get a cursor after the last entry.
Definition: index.cc:160
TempTable index containers declarations.
TempTable index cursor.
TempTable Indexed Cells declaration.
TempTable Indexed Column.
Definition: allocator.h:44
Result
Definition: result.h:33
std::multiset< Indexed_cells, Indexed_cells_less, Allocator< Indexed_cells > > Tree_container
The container used by tree unique and non-unique indexes.
Definition: containers.h:41
std::unordered_set< Indexed_cells, Indexed_cells_hash, Indexed_cells_equal_to, Allocator< Indexed_cells > > Hash_unique_container
The container used by hash unique indexes.
Definition: containers.h:52
std::unordered_multiset< Indexed_cells, Indexed_cells_hash, Indexed_cells_equal_to, Allocator< Indexed_cells > > Hash_duplicates_container
The container used by hash non-unique indexes.
Definition: containers.h:47
TempTable custom allocator.
TempTable auxiliary Result enum.