MySQL 8.3.0
Source Code Documentation
hash_join_buffer.h
Go to the documentation of this file.
1#ifndef SQL_ITERATORS_HASH_JOIN_BUFFER_H_
2#define SQL_ITERATORS_HASH_JOIN_BUFFER_H_
3
4/* Copyright (c) 2019, 2023, Oracle and/or its affiliates.
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License, version 2.0,
8 as published by the Free Software Foundation.
9
10 This program is also distributed with certain software (including
11 but not limited to OpenSSL) that is licensed under separate terms,
12 as designated in a particular file or component or in included license
13 documentation. The authors of MySQL hereby grant you an additional
14 permission to link the program and your derivative works with the
15 separately licensed software that they have included with MySQL.
16
17 This program is distributed in the hope that it will be useful,
18 but WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 GNU General Public License, version 2.0, for more details.
21
22 You should have received a copy of the GNU General Public License
23 along with this program; if not, write to the Free Software
24 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
25
26/// @file
27///
28/// This file contains the HashJoinRowBuffer class and related
29/// functions/classes.
30///
31/// A HashJoinBuffer is a row buffer that can hold a certain amount of rows.
32/// The rows are stored in a hash table, which allows for constant-time lookup.
33/// The HashJoinBuffer maintains its own internal MEM_ROOT, where all of the
34/// data is allocated.
35///
36/// The HashJoinBuffer contains an operand with rows from one or more tables,
37/// keyed on the value we join on. Consider the following trivial example:
38///
39/// SELECT t1.data FROM t1 JOIN t2 ON (t1.key = t2.key);
40///
41/// Let us say that the table "t2" is stored in a HashJoinBuffer. In this case,
42/// the hash table key will be the value found in "t2.key", since that is the
43/// join condition that belongs to t2. If we have multiple equalities, they
44/// will be concatenated together in order to form the hash table key. The hash
45/// table key is a std::string_view.
46///
47/// In order to store a row, we use the function StoreFromTableBuffers. See the
48/// comments attached to the function for more details.
49///
50/// The amount of memory a HashJoinBuffer instance can use is limited by the
51/// system variable "join_buffer_size". However, note that we check whether we
52/// have exceeded the memory limit _after_ we have inserted data into the row
53/// buffer. As such, we will probably use a little bit more memory than
54/// specified by join_buffer_size.
55///
56/// The primary use case for these classes is, as the name implies,
57/// for implementing hash join.
58
59#include <stddef.h>
60#include <cassert>
61#include <memory>
62#include <string>
63#include <string_view>
64#include <vector>
65
66#include "extra/robin-hood-hashing/robin_hood.h"
67#include "my_alloc.h"
69#include "sql/item_cmpfunc.h"
70#include "sql/pack_rows.h"
71#include "sql_string.h"
72
73class THD;
74
75namespace hash_join_buffer {
76
77/// The key type for the hash structure in HashJoinRowBuffer.
78///
79/// A key consists of the value from one or more columns, taken from the join
80/// condition(s) in the query. E.g., if the join condition is
81/// (t1.col1 = t2.col1 AND t1.col2 = t2.col2), the key is (col1, col2), with the
82/// two key parts concatenated together.
83///
84/// What the data actually contains depends on the comparison context for the
85/// join condition. For instance, if the join condition is between a string
86/// column and an integer column, the comparison will be done in a string
87/// context, and thus the integers will be converted to strings before storing.
88/// So the data we store in the key are in some cases converted, so that we can
89/// hash and compare them byte-by-byte (i.e. decimals), while other types are
90/// already comparable byte-by-byte (i.e. integers), and thus stored as-is.
91///
92/// Note that the key data can come from items as well as fields if the join
93/// condition is an expression. E.g. if the join condition is
94/// UPPER(t1.col1) = UPPER(t2.col1), the join key data will come from an Item
95/// instead of a Field.
96///
97/// The Key class never takes ownership of the data. As such, the user must
98/// ensure that the data has the proper lifetime. When storing rows in the row
99/// buffer, the data must have the same lifetime as the row buffer itself.
100/// When using the Key class for lookups in the row buffer, the same lifetime is
101/// not needed; the key object is only needed when the lookup is done.
102using Key = std::string_view;
103
105 public:
106 // This is a marker from C++17 that signals to the container that
107 // operator() can be called with arguments of which one of the types
108 // differs from the container's key type (ImmutableStringWithLength),
109 // and thus enables map.find(Key). The type itself does not matter.
110 using is_transparent = void;
111
112 bool operator()(const Key &str1,
113 const ImmutableStringWithLength &other) const {
114 return str1 == other.Decode();
115 }
116
118 const ImmutableStringWithLength &str2) const {
119 return str1 == str2;
120 }
121};
122
123// A row in the hash join buffer is the same as the Key class.
125
127 public:
128 // This is a marker from C++17 that signals to the container that
129 // operator() can be called with an argument that differs from the
130 // container's key type (ImmutableStringWithLength), and thus enables
131 // map.find(Key). The type itself does not matter.
132 using is_transparent = void;
133
135 return robin_hood::hash_bytes(key.data(), key.size());
136 }
137
139 std::string_view decoded = key.Decode();
140 return robin_hood::hash_bytes(decoded.data(), decoded.size());
141 }
142};
143
144// A convenience form of LoadIntoTableBuffers() that also verifies the end
145// pointer for us.
147 BufferRow row);
148
149// A convenience form of the above that also decodes the LinkedImmutableString
150// for us.
153
155
157 public:
158 // Construct the buffer. Note that Init() must be called before the buffer can
159 // be used.
161 std::vector<HashJoinCondition> join_conditions,
162 size_t max_mem_available_bytes);
163
164 // Initialize the HashJoinRowBuffer so it is ready to store rows. This
165 // function can be called multiple times; subsequent calls will only clear the
166 // buffer for existing rows.
167 bool Init();
168
169 /// Store the row that is currently lying in the tables record buffers.
170 /// The hash map key is extracted from the join conditions that the row buffer
171 /// holds.
172 ///
173 /// @param thd the thread handler
174 /// @param reject_duplicate_keys If true, reject rows with duplicate keys.
175 /// If a row is rejected, the function will still return ROW_STORED.
176 ///
177 /// @retval ROW_STORED the row was stored.
178 /// @retval BUFFER_FULL the row was stored, and the buffer is full.
179 /// @retval FATAL_ERROR an unrecoverable error occurred (most likely,
180 /// malloc failed). It is the caller's responsibility to call
181 /// my_error().
182 StoreRowResult StoreRow(THD *thd, bool reject_duplicate_keys);
183
184 size_t size() const { return m_hash_map->size(); }
185
186 bool empty() const { return m_hash_map->empty(); }
187
188 bool inited() const { return m_hash_map != nullptr; }
189
190 using hash_map_type = robin_hood::unordered_flat_map<
192
193 using hash_map_iterator = hash_map_type::const_iterator;
194
195 hash_map_iterator find(const Key &key) const { return m_hash_map->find(key); }
196
197 hash_map_iterator begin() const { return m_hash_map->begin(); }
198
199 hash_map_iterator end() const { return m_hash_map->end(); }
200
202 assert(Initialized());
203 return m_last_row_stored;
204 }
205
206 bool Initialized() const { return m_hash_map.get() != nullptr; }
207
208 bool contains(const Key &key) const { return find(key) != end(); }
209
210 private:
211 const std::vector<HashJoinCondition> m_join_conditions;
212
213 // A row can consist of parts from different tables. This structure tells us
214 // which tables that are involved.
216
217 // The MEM_ROOT on which all of the hash table keys and values are allocated.
218 // The actual hash map is on the regular heap.
220
221 // A MEM_ROOT used only for storing the final row (possibly both key and
222 // value). The code assumes fairly deeply that inserting a row never fails, so
223 // when m_mem_root goes full (we set a capacity on it to ensure that the last
224 // allocated block does not get too big), we allocate the very last row on
225 // this MEM_ROOT and the signal fullness so that we can start spilling to
226 // disk.
228
229 // The hash table where the rows are stored.
230 std::unique_ptr<hash_map_type> m_hash_map;
231
232 // A buffer we can use when we are constructing a join key from a join
233 // condition. In order to avoid reallocating memory, the buffer never shrinks.
236
237 // The maximum size of the buffer, given in bytes.
239
240 // The last row that was stored in the hash table, or nullptr if the hash
241 // table is empty. We may have to put this row back into the tables' record
242 // buffers if we have a child iterator that expects the record buffers to
243 // contain the last row returned by the storage engine (the probe phase of
244 // hash join may put any row in the hash table in the tables' record buffer).
245 // See HashJoinIterator::BuildHashTable() for an example of this.
247
248 // Fetch the relevant fields from each table, and pack them into m_mem_root
249 // as a LinkedImmutableString where the “next” pointer points to “next_ptr”.
250 // If that does not work (capacity reached), pack into m_overflow_mem_root
251 // instead and set “full” to true. If _that_ does not work (fatally out
252 // of memory), returns nullptr. Otherwise, returns a pointer to the newly
253 // packed string.
255 LinkedImmutableString next_ptr, bool *full);
256};
257
258} // namespace hash_join_buffer
259
260/// External interface to the corresponding member in HashJoinRowBuffer
262 MEM_ROOT *mem_root, MEM_ROOT *overflow_mem_root,
264 size_t row_size_upper_bound, bool *full);
265
266#endif // SQL_ITERATORS_HASH_JOIN_BUFFER_H_
The variant with length (ImmutableStringWithLength) stores the length as a Varint128 (similar to prot...
Definition: immutable_string.h:62
std::string_view Decode() const
Definition: immutable_string.h:129
LinkedImmutableString is designed for storing rows (values) in hash join.
Definition: immutable_string.h:172
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: hash_join_buffer.h:156
String m_buffer
Definition: hash_join_buffer.h:234
bool contains(const Key &key) const
Definition: hash_join_buffer.h:208
size_t m_row_size_upper_bound
Definition: hash_join_buffer.h:235
hash_map_type::const_iterator hash_map_iterator
Definition: hash_join_buffer.h:193
hash_map_iterator end() const
Definition: hash_join_buffer.h:199
size_t size() const
Definition: hash_join_buffer.h:184
bool Init()
Definition: hash_join_buffer.cc:132
bool Initialized() const
Definition: hash_join_buffer.h:206
hash_map_iterator begin() const
Definition: hash_join_buffer.h:197
bool empty() const
Definition: hash_join_buffer.h:186
bool inited() const
Definition: hash_join_buffer.h:188
std::unique_ptr< hash_map_type > m_hash_map
Definition: hash_join_buffer.h:230
HashJoinRowBuffer(pack_rows::TableCollection tables, std::vector< HashJoinCondition > join_conditions, size_t max_mem_available_bytes)
Definition: hash_join_buffer.cc:118
LinkedImmutableString m_last_row_stored
Definition: hash_join_buffer.h:246
const std::vector< HashJoinCondition > m_join_conditions
Definition: hash_join_buffer.h:211
const size_t m_max_mem_available
Definition: hash_join_buffer.h:238
LinkedImmutableString StoreLinkedImmutableStringFromTableBuffers(LinkedImmutableString next_ptr, bool *full)
Definition: hash_join_buffer.cc:97
StoreRowResult StoreRow(THD *thd, bool reject_duplicate_keys)
Store the row that is currently lying in the tables record buffers.
Definition: hash_join_buffer.cc:161
const pack_rows::TableCollection m_tables
Definition: hash_join_buffer.h:215
robin_hood::unordered_flat_map< ImmutableStringWithLength, LinkedImmutableString, KeyHasher, KeyEquals > hash_map_type
Definition: hash_join_buffer.h:191
LinkedImmutableString LastRowStored() const
Definition: hash_join_buffer.h:201
hash_map_iterator find(const Key &key) const
Definition: hash_join_buffer.h:195
MEM_ROOT m_overflow_mem_root
Definition: hash_join_buffer.h:227
MEM_ROOT m_mem_root
Definition: hash_join_buffer.h:219
Definition: hash_join_buffer.h:104
void is_transparent
Definition: hash_join_buffer.h:110
bool operator()(const ImmutableStringWithLength &str1, const ImmutableStringWithLength &str2) const
Definition: hash_join_buffer.h:117
bool operator()(const Key &str1, const ImmutableStringWithLength &other) const
Definition: hash_join_buffer.h:112
Definition: hash_join_buffer.h:126
size_t operator()(hash_join_buffer::Key key) const
Definition: hash_join_buffer.h:134
void is_transparent
Definition: hash_join_buffer.h:132
size_t operator()(ImmutableStringWithLength key) const
Definition: hash_join_buffer.h:138
A structure that contains a list of input tables for a hash join operation, BKA join operation or a s...
Definition: pack_rows.h:92
static MEM_ROOT mem_root
Definition: client_plugin.cc:113
LinkedImmutableString StoreLinkedImmutableStringFromTableBuffers(MEM_ROOT *mem_root, MEM_ROOT *overflow_mem_root, pack_rows::TableCollection tables, LinkedImmutableString next_ptr, size_t row_size_upper_bound, bool *full)
External interface to the corresponding member in HashJoinRowBuffer.
Definition: hash_join_buffer.cc:44
ImmutableString defines a storage format for strings that is designed to be as compact as possible,...
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...
Definition: hash_join_buffer.cc:94
std::string_view Key
The key type for the hash structure in HashJoinRowBuffer.
Definition: hash_join_buffer.h:102
Key BufferRow
Definition: hash_join_buffer.h:124
void LoadImmutableStringIntoTableBuffers(const TableCollection &tables, LinkedImmutableString row)
Definition: hash_join_buffer.cc:113
void LoadBufferRowIntoTableBuffers(const TableCollection &tables, BufferRow row)
Definition: hash_join_buffer.cc:106
StoreRowResult
Definition: hash_join_buffer.h:154
Generic routines for packing rows (possibly from multiple tables at the same time) into strings,...
required string key
Definition: replication_asynchronous_connection_failover.proto:59
Our own string classes, used pervasively throughout the executor.
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:82