MySQL 8.2.0
Source Code Documentation
hash_join_iterator.h
Go to the documentation of this file.
1#ifndef SQL_ITERATORS_HASH_JOIN_ITERATOR_H_
2#define SQL_ITERATORS_HASH_JOIN_ITERATOR_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#include <stdio.h>
27#include <cstdint>
28#include <memory>
29#include <vector>
30
31#include "my_alloc.h"
32#include "my_base.h"
33#include "my_table_map.h"
34#include "prealloced_array.h"
36#include "sql/item_cmpfunc.h"
40#include "sql/join_type.h"
41#include "sql/mem_root_array.h"
42#include "sql/pack_rows.h"
43#include "sql_string.h"
44
45class Item;
46class JOIN;
47class THD;
48
49struct ChunkPair {
52};
53
54/// @file
55///
56/// An iterator for joining two inputs by using hashing to match rows from
57/// the inputs.
58///
59/// The iterator starts out by doing everything in-memory. If everything fits
60/// into memory, the joining algorithm for inner joins works like this:
61///
62/// 1) Designate one input as the "build" input and one input as the "probe"
63/// input. Ideally, the smallest input measured in total size (not number of
64/// rows) should be designated as the build input.
65///
66/// 2) Read all the rows from the build input into an in-memory hash table.
67/// The hash key used in the hash table is calculated from the join attributes,
68/// e.g., if we have the following query where "orders" is designated as the
69/// build input:
70///
71/// SELECT * FROM lineitem
72/// INNER JOIN orders ON orders.o_orderkey = lineitem.l_orderkey;
73///
74/// the hash value will be calculated from the values in the column
75/// orders.o_orderkey. Note that the optimizer recognizes implicit join
76/// conditions, so this also works for SQL statements like:
77///
78/// SELECT * FROM orders, lineitem
79/// WHERE orders.o_orderkey = lineitem.l_orderkey;
80///
81/// 3) Then, we read the rows from the probe input, one by one. For each row,
82/// a hash key is calculated for the other side of the join (the probe input)
83/// using the join attribute (lineitem.l_orderkey in the above example) and the
84/// same hash function as in step 2. This hash key is used to do a lookup in the
85/// hash table, and for each match, an output row is produced. Note that the row
86/// from the probe input is already located in the table record buffers, and the
87/// matching row stored in the hash table is restored back to the record buffers
88/// where it originally came from. For details around how rows are stored and
89/// restored, see comments on pack_rows::StoreFromTableBuffers.
90///
91/// The size of the in-memory hash table is controlled by the system variable
92/// join_buffer_size. If we run out of memory during step 2, we degrade into a
93/// hybrid hash join. The data already in memory is processed using regular hash
94/// join, and the remainder is processed using on-disk hash join. It works like
95/// this:
96///
97/// 1) The rest of the rows in the build input that did not fit into the hash
98/// table are partitioned out into a given amount of files, represented by
99/// HashJoinChunks. We create an equal number of chunk files for both the probe
100/// and build input. We determine which file to put a row in by calculating a
101/// hash from the join attribute like in step 2 above, but using a different
102/// hash function.
103///
104/// 2) Then, we read the rows from the probe input, one by one. We look for a
105/// match in the hash table as described above, but the row is also written out
106/// to the chunk file on disk, since it might match a row from the build input
107/// that we've written to disk.
108///
109/// 3) When the entire probe input is read, we run the "classic" hash join on
110/// each of the corresponding chunk file probe/build pairs. Since the rows are
111/// partitioned using the same hash function for probe and build inputs, we know
112/// that matching rows must be located in the same pair of chunk files.
113///
114/// The algorithm for semijoin is quite similar to inner joins:
115///
116/// 1) Designate the inner table (i.e. the IN-side of a semijoin) as the build
117/// input. As semijoins only needs the first matching row from the inner table,
118/// we do not store duplicate keys in the hash table.
119///
120/// 2) Output all rows from the probe input where there is at least one matching
121/// row in the hash table. In case we have degraded into on-disk hash join, we
122/// write the probe row out to chunk file only if we did not find a matching row
123/// in the hash table.
124///
125/// The optimizer may set up semijoins with conditions that are not pure join
126/// conditions, but that must be attached to the hash join iterator anyways.
127/// Consider the following query and (slightly modified) execution plan:
128///
129/// SELECT c FROM t WHERE 1 IN (SELECT t.c = col1 FROM t1);
130///
131/// -> Hash semijoin (no condition), extra conditions: (1 = (t.c = t1.col1))
132/// -> Table scan on t
133/// -> Hash
134/// -> Table scan on t1
135///
136/// In this query, the optimizer has set up the condition (1 = (t.c = t1.col1))
137/// as the semijoin condition. We cannot use this as a join condition, since
138/// hash join only supports equi-join conditions. However, we cannot attach this
139/// as a filter after the join, as that would cause wrong results. We attach
140/// these conditions as "extra" conditions to the hash join iterator, and causes
141/// these notable behaviors:
142///
143/// a. If we have any extra conditions, we cannot reject duplicate keys in the
144/// hash table: the first row matching the join condition could fail the
145/// extra condition(s).
146///
147/// b. We can only output rows if all extra conditions pass. If any of the extra
148/// conditions fail, we must go to the next matching row in the hash table.
149///
150/// c. In case of on-disk hash join, we must write the probe row to disk _after_
151/// we have checked that there are no rows in the hash table that match any
152/// of the extra conditions.
153///
154/// If we are able to execute the hash join in memory (classic hash join),
155/// the output will be sorted the same as the left (probe) input. If we start
156/// spilling to disk, we lose any reasonable ordering properties.
157///
158/// Note that we still might end up in a case where a single chunk file from
159/// disk won't fit into memory. This is resolved by reading as much as possible
160/// into the hash table, and then reading the entire probe chunk file for each
161/// time the hash table is reloaded. This might happen if we have a very skewed
162/// data set, for instance.
163///
164/// When we start spilling to disk, we allocate a maximum of "kMaxChunks"
165/// chunk files on disk for each of the two inputs. The reason for having an
166/// upper limit is to avoid running out of file descriptors.
167///
168/// There is also a flag we can set to avoid hash join spilling to disk
169/// regardless of the input size. If the flag is set, the join algorithm works
170/// like this:
171///
172/// 1) Read as many rows as possible from the build input into an in-memory hash
173/// table.
174/// 2) When the hash table is full (we have reached the limit set by the system
175/// variable join_buffer_size), start reading from the beginning of the probe
176/// input, probing for matches in the hash table. Output a row for each match
177/// found.
178/// 3) When the probe input is empty, see if there are any remaining rows in the
179/// build input. If so, clear the in-memory hash table and go to step 1,
180/// continuing from the build input where we stopped the last time. If not, the
181/// join is done.
182///
183/// Doing everything in memory can be beneficial in a few cases. Currently, it
184/// is used when we have a LIMIT without sorting or grouping in the query. The
185/// gain is that we start producing output rows a lot earlier than if we were to
186/// spill both inputs out to disk. It could also be beneficial if the build
187/// input _almost_ fits in memory; it would likely be better to read the probe
188/// input twice instead of writing both inputs out to disk. However, we do not
189/// currently do any such cost based optimization.
190///
191/// There is a concept called "probe row saving" in the iterator. This is a
192/// technique that is enabled in two different scenarios: when a hash join build
193/// chunk does not fit entirely in memory and when hash join is not allowed to
194/// spill to disk. Common for these two scenarios is that a probe row will be
195/// read multiple times. For certain join types (semijoin), we must take care so
196/// that the same probe row is not sent to the client multiple times. Probe row
197/// saving takes care of this by doing the following:
198///
199/// - If we realize that we are going to read the same probe row multiple times,
200/// we enable probe row saving.
201/// - When a probe row is read, we write the row out to a probe row saving write
202/// file, given that it matches certain conditions (for semijoin we only save
203/// unmatched probe rows).
204/// - After the probe input is consumed, we will swap the probe row saving
205/// _write_ file and the probe row saving _read_ file, making the write file
206/// available for writing again.
207/// - When we are to read the probe input again, we read the probe rows from the
208/// probe row saving read file. This ensures that we i.e. do not output the
209/// same probe row twice for semijoin. Note that if the rows we read from the
210/// probe row saving read file will be read again (e.g., we have a big hash
211/// join build chunk that is many times bigger than the available hash table
212/// memory, causing us to process the chunk file in chunks), we will again
213/// write the rows to a new probe row saving write file. This reading from the
214/// read file and writing to a new write file continues until we know that we
215/// are seeing the probe rows for the last time.
216///
217/// We use the same methods as on-disk hash join (HashJoinChunk) for reading and
218/// writing rows to files. Note that probe row saving is never enabled for inner
219/// joins, since we do want to output the same probe row multiple times if it
220/// matches muliple rows from the build input. There are some differences
221/// regarding when probe row saving is enabled, depending on the hash join type
222/// (see enum HashJoinType):
223///
224/// - IN_MEMORY: Probe row saving is never activated, since the probe input is
225/// read only once.
226/// - SPILL_TO_DISK: If a build chunk file does not fit in memory (may happen
227/// with skewed data set), we will have to read the corresponding probe chunk
228/// multiple times. In this case, probe row saving is enabled as soon as we
229/// see that the build chunk does not fit in memory, and remains active until
230/// the entire build chunk is consumed. After the probe chunk is read once,
231/// we swap the probe row saving write file and probe row saving read file so
232/// that probe rows will be read from the probe row saving read file. Probe
233/// row saving is deactivated once we move to the next pair of chunk files.
234/// - IN_MEMORY_WITH_HASH_TABLE_REFILL: Probe row saving is activated when we
235/// see that the build input is too large to fit in memory. Once the probe
236/// iterator has been consumed once, we swap the probe row saving write file
237/// and probe row saving read file so that probe rows will be read from the
238/// probe row saving read file. As long as the build input is not fully
239/// consumed, we write probe rows from the read file out to a new write file,
240/// swapping these files for every hash table refill. Probe row saving is
241/// never deactivated in this hash join type.
242///
243/// Note that we always write the entire row when writing to probe row saving
244/// file. It would be possible to only write the match flag, but this is tricky
245/// as long as we have the hash join type IN_MEMORY_WITH_HASH_TABLE_REFILL. If
246/// we were to write only match flags in this hash join type, we would have to
247/// read the probe iterator multiple times. But there is no guarantee that rows
248/// will come in the same order when reading an iterator multiple times (e.g.
249/// NDB does not guarantee this), so it would require us to store match flags in
250/// a lookup structure using a row ID as the key. Due to this, we will
251/// reconsider this if the hash join type IN_MEMORY_WITH_HASH_TABLE_REFILL goes
252/// away.
253
254/// The two inputs that we read from when executing a hash join.
255enum class HashJoinInput {
256 /// We build the hash table from this input.
257 kBuild,
258 /// For each row from this input, we try to find a match in the hash table.
259 kProbe
260};
261
262class HashJoinIterator final : public RowIterator {
263 public:
264 /// Construct a HashJoinIterator.
265 ///
266 /// @param thd
267 /// the thread handle
268 /// @param build_input
269 /// the iterator for the build input
270 /// @param build_input_tables
271 /// a list of all the tables in the build input. The tables are needed for
272 /// two things:
273 /// 1) Accessing the columns when creating the join key during creation of
274 /// the hash table,
275 /// 2) and accessing the column data when creating the row to be stored in
276 /// the hash table and/or the chunk file on disk.
277 /// @param estimated_build_rows
278 /// How many rows we assume there will be when reading the build input.
279 /// This is used to choose how many chunks we break it into on disk.
280 /// @param probe_input
281 /// the iterator for the probe input
282 /// @param probe_input_tables
283 /// the probe input tables. Needed for the same reasons as
284 /// build_input_tables.
285 /// @param store_rowids whether we need to make sure row ids are available
286 /// for all tables below us, after Read() has been called. used only if
287 /// we are below a weedout operation.
288 /// @param tables_to_get_rowid_for a map of which tables we need to call
289 /// position() for ourselves. tables that are in build_input_tables
290 /// but not in this map, are expected to be handled by some other iterator.
291 /// tables that are in this map but not in build_input_tables will be
292 /// ignored.
293 /// @param max_memory_available
294 /// the amount of memory available, in bytes, for this hash join iterator.
295 /// This can be user-controlled by setting the system variable
296 /// join_buffer_size.
297 /// @param join_conditions
298 /// a list of all the join conditions between the two inputs
299 /// @param allow_spill_to_disk
300 /// whether the hash join can spill to disk. This is set to false in some
301 /// cases where we have a LIMIT in the query
302 /// @param join_type
303 /// The join type.
304 /// @param extra_conditions
305 /// A list of extra conditions that the iterator will evaluate after a
306 /// lookup in the hash table is done, but before the row is returned. The
307 /// conditions are AND-ed together into a single Item.
308 /// @param first_input
309 /// The first input (build or probe) to read from. (If this is empty, we
310 /// will not have to read from the other.)
311 /// @param probe_input_batch_mode
312 /// Whether we need to enable batch mode on the probe input table.
313 /// Only make sense if it is a single table, and we are not on the
314 /// outer side of any nested loop join.
315 /// @param hash_table_generation
316 /// If this is non-nullptr, it is a counter of how many times the query
317 /// block the iterator is a part of has been asked to clear hash tables,
318 /// since outer references may have changed value. It is used to know when
319 /// we need to drop our hash table; when the value changes, we need to drop
320 /// it. If it is nullptr, we _always_ drop it on Init().
322 const Prealloced_array<TABLE *, 4> &build_input_tables,
323 double estimated_build_rows,
325 const Prealloced_array<TABLE *, 4> &probe_input_tables,
326 bool store_rowids, table_map tables_to_get_rowid_for,
327 size_t max_memory_available,
328 const std::vector<HashJoinCondition> &join_conditions,
329 bool allow_spill_to_disk, JoinType join_type,
330 const Mem_root_array<Item *> &extra_conditions,
331 HashJoinInput first_input, bool probe_input_batch_mode,
332 uint64_t *hash_table_generation);
333
334 bool Init() override;
335
336 int Read() override;
337
338 void SetNullRowFlag(bool is_null_row) override {
339 m_build_input->SetNullRowFlag(is_null_row);
340 m_probe_input->SetNullRowFlag(is_null_row);
341 }
342
343 void EndPSIBatchModeIfStarted() override {
344 m_build_input->EndPSIBatchModeIfStarted();
345 m_probe_input->EndPSIBatchModeIfStarted();
346 }
347
348 void UnlockRow() override {
349 // Since both inputs may have been materialized to disk, we cannot unlock
350 // them.
351 }
352
353 int ChunkCount() { return m_chunk_files_on_disk.size(); }
354
355 private:
356 /// Read all rows from the build input and store the rows into the in-memory
357 /// hash table. If the hash table goes full, the rest of the rows are written
358 /// out to chunk files on disk. See the class comment for more details.
359 ///
360 /// @retval true in case of error
361 bool BuildHashTable();
362
363 /// Read all rows from the next chunk file into the in-memory hash table.
364 /// See the class comment for details.
365 ///
366 /// @retval true in case of error
368
369 /// Read a single row from the probe iterator input into the tables' record
370 /// buffers. If we have started spilling to disk, the row is written out to a
371 /// chunk file on disk as well.
372 ///
373 /// The end condition is that either:
374 /// a) a row is ready in the tables' record buffers, and the state will be set
375 /// to READING_FIRST_ROW_FROM_HASH_TABLE.
376 /// b) There are no more rows to process from the probe input, so the iterator
377 /// state will be LOADING_NEXT_CHUNK_PAIR.
378 ///
379 /// @retval true in case of error
381
382 /// Read a single row from the current probe chunk file into the tables'
383 /// record buffers. The end conditions are the same as for
384 /// ReadRowFromProbeIterator().
385 ///
386 /// @retval true in case of error
388
389 /// Read a single row from the probe row saving file into the tables' record
390 /// buffers.
391 ///
392 /// @retval true in case of error
394
395 // Do a lookup in the hash table for matching rows from the build input.
396 // The lookup is done by computing the join key from the probe input, and
397 // using that join key for doing a lookup in the hash table. If the join key
398 // contains one or more SQL NULLs, the row cannot match anything and will be
399 // skipped, and the iterator state will be READING_ROW_FROM_PROBE_INPUT. If
400 // not, the iterator state will be READING_FIRST_ROW_FROM_HASH_TABLE.
401 //
402 // After this function is called, ReadJoinedRow() will return false until
403 // there are no more matching rows for the computed join key.
405
406 /// Take the next matching row from the hash table, and put the row into the
407 /// build tables' record buffers. The function expects that
408 /// LookupProbeRowInHashTable() has been called up-front. The user must
409 /// call ReadJoinedRow() as long as it returns false, as there may be
410 /// multiple matching rows from the hash table. It is up to the caller to set
411 /// a new state in case of EOF.
412 ///
413 /// @retval 0 if a match was found and the row is put in the build tables'
414 /// record buffers
415 /// @retval -1 if there are no more matching rows in the hash table
416 int ReadJoinedRow();
417
418 // Have we degraded into on-disk hash join?
419 bool on_disk_hash_join() const { return !m_chunk_files_on_disk.empty(); }
420
421 /// Write the last row read from the probe input out to chunk files on disk,
422 /// if applicable.
423 ///
424 /// For inner joins, we must write all probe rows to chunk files, since we
425 /// need to match the row against rows from the build input that are written
426 /// out to chunk files. For semijoin, we can only write probe rows that do not
427 /// match any of the rows in the hash table. Writing a probe row with a
428 /// matching row in the hash table could cause the row to be returned multiple
429 /// times.
430 ///
431 /// @retval true in case of errors.
433
434 /// @retval true if the last joined row passes all of the extra conditions.
436
437 /// If true, reject duplicate keys in the hash table.
438 ///
439 /// Semijoins/antijoins are only interested in the first matching row from the
440 /// hash table, so we can avoid storing duplicate keys in order to save some
441 /// memory. However, this cannot be applied if we have any "extra" conditions:
442 /// the first matching row in the hash table may fail the extra condition(s).
443 ///
444 /// @retval true if we can reject duplicate keys in the hash table.
445 bool RejectDuplicateKeys() const {
446 return m_extra_condition == nullptr &&
448 }
449
450 /// Clear the row buffer and reset all iterators pointing to it. This may be
451 /// called multiple times to re-init the row buffer.
452 ///
453 /// @retval true in case of error. my_error has been called
454 bool InitRowBuffer();
455
456 /// Prepare to read the probe iterator from the beginning, and enable batch
457 /// mode if applicable. The iterator state will remain unchanged.
458 ///
459 /// @retval true in case of error. my_error has been called.
460 bool InitProbeIterator();
461
462 /// Mark that probe row saving is enabled, and prepare the probe row saving
463 /// file for writing.
464 /// @see m_write_to_probe_row_saving
465 ///
466 /// @retval true in case of error. my_error has been called.
468
469 /// Mark that we should read from the probe row saving file. The probe row
470 /// saving file is rewinded to the beginning.
471 /// @see m_read_from_probe_row_saving
472 ///
473 /// @retval true in case of error. my_error has been called.
475
476 /// Set the iterator state to the correct READING_ROW_FROM_PROBE_*-state.
477 /// Which state we end up in depends on which hash join type we are executing
478 /// (in-memory, on-disk or in-memory with hash table refill).
480
481 /// Read a joined row from the hash table, and see if it passes any extra
482 /// conditions. The last probe row read will also be written do disk if needed
483 /// (see WriteProbeRowToDiskIfApplicable).
484 ///
485 /// @retval -1 There are no more matching rows in the hash table.
486 /// @retval 0 A joined row is ready.
487 /// @retval 1 An error occurred.
489
490 enum class State {
491 // We are reading a row from the probe input, where the row comes from
492 // the iterator.
494 // We are reading a row from the probe input, where the row comes from a
495 // chunk file.
497 // We are reading a row from the probe input, where the row comes from a
498 // probe row saving file.
500 // The iterator is moving to the next pair of chunk files, where the chunk
501 // file from the build input will be loaded into the hash table.
503 // We are reading the first row returned from the hash table lookup that
504 // also passes extra conditions.
506 // We are reading the remaining rows returned from the hash table lookup.
508 // No more rows, both inputs are empty.
510 };
511
515
518
519 // The last row that was read from the hash table, or nullptr if none.
520 // All rows under the same key are linked together (see the documentation
521 // for LinkedImmutableString), so this allows iterating through the rows
522 // until the end.
524
525 // These structures holds the tables and columns that are needed for the hash
526 // join. Rows/columns that are not needed are filtered out in the constructor.
527 // We need to know which tables that belong to each iterator, so that we can
528 // compute the join key when needed.
532
533 // An in-memory hash table that holds rows from the build input (directly from
534 // the build input iterator, or from a chunk file). See the class comment for
535 // details on how and when this is used.
537
538 // A list of the join conditions (all of them are equi-join conditions).
540
541 // Array to hold the list of chunk files on disk in case we degrade into
542 // on-disk hash join.
544
545 // Which HashJoinChunk, if any, we are currently reading from, in both
546 // LOADING_NEXT_CHUNK_PAIR and READING_ROW_FROM_PROBE_CHUNK_FILE.
547 // It is incremented during the state LOADING_NEXT_CHUNK_PAIR.
549
550 // Which row we currently are reading from each of the hash join chunk file.
553
554 // How many rows we assume there will be when reading the build input.
555 // This is used to choose how many chunks we break it into on disk.
557
558 public:
559 // The seed that is by xxHash64 when calculating the hash from a join
560 // key. We use xxHash64 when calculating the hash that is used for
561 // determining which chunk file a row should be placed in (in case of
562 // on-disk hash join); if we used the same hash function (and seed) for
563 // both operation, we would get a really bad hash table when loading
564 // a chunk file to the hash table. The number is chosen randomly and have
565 // no special meaning.
566 static constexpr uint32_t kChunkPartitioningHashSeed{899339};
567
568 // The maximum number of HashJoinChunks that is allocated for each of the
569 // inputs in case we spill to disk. We might very well end up with an amount
570 // less than this number, but we keep an upper limit so we don't risk running
571 // out of file descriptors. We always use a power of two number of files,
572 // which allows us to do some optimizations when calculating which chunk a row
573 // should be placed in.
574 static constexpr size_t kMaxChunks = 128;
575
576 private:
577 // A buffer that is used during two phases:
578 // 1) when constructing a join key from join conditions.
579 // 2) when moving a row between tables' record buffers and the hash table.
580 //
581 // There are two functions that needs this buffer; ConstructJoinKey() and
582 // StoreFromTableBuffers(). After calling one of these functions, the user
583 // must take responsibility of the data if it is needed for a longer lifetime.
584 //
585 // If there are no BLOB/TEXT column in the join, we calculate an upper bound
586 // of the row size that is used to preallocate this buffer. In the case of
587 // BLOB/TEXT columns, we cannot calculate a reasonable upper bound, and the
588 // row size is calculated per row. The allocated memory is kept for the
589 // duration of the iterator, so that we (most likely) avoid reallocations.
591
592 /// The first input (build or probe) to read from. (If this is empty, we will
593 /// not have to read from the other.)
595
596 // Whether we should turn on batch mode for the probe input. Batch mode is
597 // enabled if the probe input consists of exactly one table, and said table
598 // can return more than one row and has no associated subquery condition.
599 // (See ShouldEnableBatchMode().)
601
602 // Whether we are allowed to spill to disk.
604
605 // Whether the build iterator has more rows. This is used to stop the hash
606 // join iterator asking for more rows when we know for sure that the entire
607 // build input is consumed. The variable is only used if m_allow_spill_to_disk
608 // is false, as we have to see if there are more rows in the build input after
609 // the probe input is consumed.
611
612 // What kind of join the iterator should execute.
614
615 // If not nullptr, an extra condition that the iterator will evaluate after a
616 // lookup in the hash table is done, but before the row is returned. This is
617 // needed in case we have a semijoin condition that is not an equi-join
618 // condition (i.e. 't1.col1 < t2.col1').
620
621 // Whether we should write rows from the probe input to the probe row saving
622 // write file. See the class comment on HashJoinIterator for details around
623 // probe row saving.
625
626 // Whether we should read rows from the probe row saving read file. See the
627 // class comment on HashJoinIterator for details around probe row saving.
629
630 // The probe row saving files where unmatched probe rows are written to and
631 // read from.
634
635 // Which row we currently are reading from in the probe row saving read file.
636 // Used to know whether we have reached the end of the file. How many files
637 // the probe row saving read file contains is contained in the HashJoinChunk
638 // (see m_probe_row_saving_read_file).
640
641 // The "type" of hash join we are executing. We currently have three different
642 // types of hash join:
643 // - In memory: We do everything in memory without any refills of the hash
644 // table. Each input is read only once, and nothing is written to disk.
645 // - Spill to disk: If the build input does not fit in memory, we write both
646 // inputs out to a set of chunk files. Both inputs are partitioned using a
647 // hash function over the join attribute, ensuring that matching rows can be
648 // found in the same set of chunk files. Each pair of chunk file is then
649 // processed as an in-memory hash join.
650 // - In memory with hash table refill: This is enabled if we are not allowed
651 // to spill to disk, and the build input does not fit in memory. We read as
652 // much as possible from the build input into the hash table. We then read
653 // the entire probe input, probing for matching rows in the hash table.
654 // When the probe input returns EOF, the hash table is refilled with the
655 // rows that did not fit the first time. The entire probe input is read
656 // again, and this is repeated until the entire build input is consumed.
657 enum class HashJoinType {
658 IN_MEMORY,
661 };
663
664 // The match flag for the last probe row read from chunk file.
665 //
666 // This is needed if a outer join spills to disk; a probe row can match a row
667 // from the build input we haven't seen yet (it's been written out to disk
668 // because the hash table was full). So when reading a probe row from a chunk
669 // file, this variable holds the match flag. This flag must be a class member,
670 // since one probe row may match multiple rows from the hash table; the
671 // execution will go out of HashJoinIterator::Read() between each matching
672 // row, causing any local match flag to lose the match flag info from the last
673 // probe row read.
675
676 /// If true, a row was already read from the probe input, in order to check if
677 /// that input was empty. If so, we should process that row before reading
678 /// another.
679 bool m_probe_row_read{false};
680};
681
682#endif // SQL_ITERATORS_HASH_JOIN_ITERATOR_H_
Definition: hash_join_chunk.h:66
Definition: hash_join_iterator.h:262
HashJoinInput m_first_input
The first input (build or probe) to read from.
Definition: hash_join_iterator.h:594
bool BuildHashTable()
Read all rows from the build input and store the rows into the in-memory hash table.
Definition: hash_join_iterator.cc:460
void EndPSIBatchModeIfStarted() override
Ends performance schema batch mode, if started.
Definition: hash_join_iterator.h:343
const unique_ptr_destroy_only< RowIterator > m_build_input
Definition: hash_join_iterator.h:516
bool ReadRowFromProbeRowSavingFile()
Read a single row from the probe row saving file into the tables' record buffers.
Definition: hash_join_iterator.cc:839
bool JoinedRowPassesExtraConditions() const
Definition: hash_join_iterator.cc:989
int ReadNextJoinedRowFromHashTable()
Read a joined row from the hash table, and see if it passes any extra conditions.
Definition: hash_join_iterator.cc:997
State
Definition: hash_join_iterator.h:490
HashJoinIterator(THD *thd, unique_ptr_destroy_only< RowIterator > build_input, const Prealloced_array< TABLE *, 4 > &build_input_tables, double estimated_build_rows, unique_ptr_destroy_only< RowIterator > probe_input, const Prealloced_array< TABLE *, 4 > &probe_input_tables, bool store_rowids, table_map tables_to_get_rowid_for, size_t max_memory_available, const std::vector< HashJoinCondition > &join_conditions, bool allow_spill_to_disk, JoinType join_type, const Mem_root_array< Item * > &extra_conditions, HashJoinInput first_input, bool probe_input_batch_mode, uint64_t *hash_table_generation)
Construct a HashJoinIterator.
Definition: hash_join_iterator.cc:61
void UnlockRow() override
Definition: hash_join_iterator.h:348
bool m_probe_row_read
If true, a row was already read from the probe input, in order to check if that input was empty.
Definition: hash_join_iterator.h:679
Prealloced_array< HashJoinCondition, 4 > m_join_conditions
Definition: hash_join_iterator.h:539
bool m_build_iterator_has_more_rows
Definition: hash_join_iterator.h:610
HashJoinChunk m_probe_row_saving_write_file
Definition: hash_join_iterator.h:632
bool WriteProbeRowToDiskIfApplicable()
Write the last row read from the probe input out to chunk files on disk, if applicable.
Definition: hash_join_iterator.cc:952
Mem_root_array< ChunkPair > m_chunk_files_on_disk
Definition: hash_join_iterator.h:543
pack_rows::TableCollection m_probe_input_tables
Definition: hash_join_iterator.h:529
bool InitRowBuffer()
Clear the row buffer and reset all iterators pointing to it.
Definition: hash_join_iterator.cc:119
int Read() override
Read a single row.
Definition: hash_join_iterator.cc:1099
String m_temporary_row_and_join_key_buffer
Definition: hash_join_iterator.h:590
void SetNullRowFlag(bool is_null_row) override
Mark the current row buffer as containing a NULL row or not, so that if you read from it and the flag...
Definition: hash_join_iterator.h:338
State m_state
Definition: hash_join_iterator.h:512
void LookupProbeRowInHashTable()
Definition: hash_join_iterator.cc:894
LinkedImmutableString m_current_row
Definition: hash_join_iterator.h:523
static constexpr size_t kMaxChunks
Definition: hash_join_iterator.h:574
int ReadJoinedRow()
Take the next matching row from the hash table, and put the row into the build tables' record buffers...
Definition: hash_join_iterator.cc:939
bool m_read_from_probe_row_saving
Definition: hash_join_iterator.h:628
uint64_t m_last_hash_table_generation
Definition: hash_join_iterator.h:514
ha_rows m_build_chunk_current_row
Definition: hash_join_iterator.h:551
HashJoinType
Definition: hash_join_iterator.h:657
bool ReadNextHashJoinChunk()
Read all rows from the next chunk file into the in-memory hash table.
Definition: hash_join_iterator.cc:615
bool m_probe_input_batch_mode
Definition: hash_join_iterator.h:600
HashJoinType m_hash_join_type
Definition: hash_join_iterator.h:662
static constexpr uint32_t kChunkPartitioningHashSeed
Definition: hash_join_iterator.h:566
bool RejectDuplicateKeys() const
If true, reject duplicate keys in the hash table.
Definition: hash_join_iterator.h:445
bool ReadRowFromProbeChunkFile()
Read a single row from the current probe chunk file into the tables' record buffers.
Definition: hash_join_iterator.cc:796
bool m_probe_row_match_flag
Definition: hash_join_iterator.h:674
pack_rows::TableCollection m_build_input_tables
Definition: hash_join_iterator.h:530
const unique_ptr_destroy_only< RowIterator > m_probe_input
Definition: hash_join_iterator.h:517
int ChunkCount()
Definition: hash_join_iterator.h:353
ha_rows m_probe_chunk_current_row
Definition: hash_join_iterator.h:552
HashJoinChunk m_probe_row_saving_read_file
Definition: hash_join_iterator.h:633
uint64_t * m_hash_table_generation
Definition: hash_join_iterator.h:513
ha_rows m_probe_row_saving_read_file_current_row
Definition: hash_join_iterator.h:639
const double m_estimated_build_rows
Definition: hash_join_iterator.h:556
int m_current_chunk
Definition: hash_join_iterator.h:548
bool Init() override
Initialize or reinitialize the iterator.
Definition: hash_join_iterator.cc:156
const JoinType m_join_type
Definition: hash_join_iterator.h:613
bool m_allow_spill_to_disk
Definition: hash_join_iterator.h:603
bool on_disk_hash_join() const
Definition: hash_join_iterator.h:419
bool InitProbeIterator()
Prepare to read the probe iterator from the beginning, and enable batch mode if applicable.
Definition: hash_join_iterator.cc:143
const table_map m_tables_to_get_rowid_for
Definition: hash_join_iterator.h:531
void SetReadingProbeRowState()
Set the iterator state to the correct READING_ROW_FROM_PROBE_*-state.
Definition: hash_join_iterator.cc:1168
Item * m_extra_condition
Definition: hash_join_iterator.h:619
hash_join_buffer::HashJoinRowBuffer m_row_buffer
Definition: hash_join_iterator.h:536
bool InitWritingToProbeRowSavingFile()
Mark that probe row saving is enabled, and prepare the probe row saving file for writing.
Definition: hash_join_iterator.cc:1155
bool InitReadingFromProbeRowSavingFile()
Mark that we should read from the probe row saving file.
Definition: hash_join_iterator.cc:1161
bool m_write_to_probe_row_saving
Definition: hash_join_iterator.h:624
bool ReadRowFromProbeIterator()
Read a single row from the probe iterator input into the tables' record buffers.
Definition: hash_join_iterator.cc:718
Base class that is used to represent any kind of expression in a relational query.
Definition: item.h:932
Definition: sql_optimizer.h:132
LinkedImmutableString is designed for storing rows (values) in hash join.
Definition: immutable_string.h:172
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:425
A typesafe replacement for DYNAMIC_ARRAY.
Definition: prealloced_array.h:70
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
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:161
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
This file contains the HashJoinRowBuffer class and related functions/classes.
HashJoinInput
The two inputs that we read from when executing a hash join.
Definition: hash_join_iterator.h:255
@ kProbe
For each row from this input, we try to find a match in the hash table.
@ kBuild
We build the hash table from this input.
ImmutableString defines a storage format for strings that is designed to be as compact as possible,...
JoinType
Definition: join_type.h:27
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:488
This file includes constants used by all storage engines.
my_off_t ha_rows
Definition: my_base.h:1139
uint64_t table_map
Definition: my_table_map.h:29
Generic routines for packing rows (possibly from multiple tables at the same time) into strings,...
join_type
Definition: sql_opt_exec_shared.h:185
Our own string classes, used pervasively throughout the executor.
Definition: hash_join_iterator.h:49
HashJoinChunk probe_chunk
Definition: hash_join_iterator.h:50
HashJoinChunk build_chunk
Definition: hash_join_iterator.h:51