MySQL 8.0.32
Source Code Documentation
Go to the documentation of this file.
4/* Copyright (c) 2019, 2022, Oracle and/or its affiliates.
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.
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.
17 This program is distributed in the hope that it will be useful,
18 but WITHOUT ANY WARRANTY; without even the implied warranty of
20 GNU General Public License, version 2.0, for more details.
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 */
26#include <stdio.h>
27#include <cstdint>
28#include <memory>
29#include <vector>
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"
45class Item;
46class JOIN;
47class THD;
49struct ChunkPair {
54/// @file
56/// An iterator for joining two inputs by using hashing to match rows from
57/// the inputs.
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:
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.
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:
71/// SELECT * FROM lineitem
72/// INNER JOIN orders ON orders.o_orderkey = lineitem.l_orderkey;
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:
78/// SELECT * FROM orders, lineitem
79/// WHERE orders.o_orderkey = lineitem.l_orderkey;
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.
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:
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.
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.
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.
114/// The algorithm for semijoin is quite similar to inner joins:
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.
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.
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:
129/// SELECT c FROM t WHERE 1 IN (SELECT t.c = col1 FROM t1);
131/// -> Hash semijoin (no condition), extra conditions: (1 = (t.c = t1.col1))
132/// -> Table scan on t
133/// -> Hash
134/// -> Table scan on t1
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:
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).
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.
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.
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.
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.
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.
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:
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.
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.
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:
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.
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):
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.
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.
253class HashJoinIterator final : public RowIterator {
254 public:
255 /// Construct a HashJoinIterator.
256 ///
257 /// @param thd
258 /// the thread handle
259 /// @param build_input
260 /// the iterator for the build input
261 /// @param build_input_tables
262 /// a list of all the tables in the build input. The tables are needed for
263 /// two things:
264 /// 1) Accessing the columns when creating the join key during creation of
265 /// the hash table,
266 /// 2) and accessing the column data when creating the row to be stored in
267 /// the hash table and/or the chunk file on disk.
268 /// @param estimated_build_rows
269 /// How many rows we assume there will be when reading the build input.
270 /// This is used to choose how many chunks we break it into on disk.
271 /// @param probe_input
272 /// the iterator for the probe input
273 /// @param probe_input_tables
274 /// the probe input tables. Needed for the same reasons as
275 /// build_input_tables.
276 /// @param store_rowids whether we need to make sure row ids are available
277 /// for all tables below us, after Read() has been called. used only if
278 /// we are below a weedout operation.
279 /// @param tables_to_get_rowid_for a map of which tables we need to call
280 /// position() for ourselves. tables that are in build_input_tables
281 /// but not in this map, are expected to be handled by some other iterator.
282 /// tables that are in this map but not in build_input_tables will be
283 /// ignored.
284 /// @param max_memory_available
285 /// the amount of memory available, in bytes, for this hash join iterator.
286 /// This can be user-controlled by setting the system variable
287 /// join_buffer_size.
288 /// @param join_conditions
289 /// a list of all the join conditions between the two inputs
290 /// @param allow_spill_to_disk
291 /// whether the hash join can spill to disk. This is set to false in some
292 /// cases where we have a LIMIT in the query
293 /// @param join_type
294 /// The join type.
295 /// @param extra_conditions
296 /// A list of extra conditions that the iterator will evaluate after a
297 /// lookup in the hash table is done, but before the row is returned. The
298 /// conditions are AND-ed together into a single Item.
299 /// @param probe_input_batch_mode
300 /// Whether we need to enable batch mode on the probe input table.
301 /// Only make sense if it is a single table, and we are not on the
302 /// outer side of any nested loop join.
303 /// @param hash_table_generation
304 /// If this is non-nullptr, it is a counter of how many times the query
305 /// block the iterator is a part of has been asked to clear hash tables,
306 /// since outer references may have changed value. It is used to know when
307 /// we need to drop our hash table; when the value changes, we need to drop
308 /// it. If it is nullptr, we _always_ drop it on Init().
310 const Prealloced_array<TABLE *, 4> &build_input_tables,
311 double estimated_build_rows,
313 const Prealloced_array<TABLE *, 4> &probe_input_tables,
314 bool store_rowids, table_map tables_to_get_rowid_for,
315 size_t max_memory_available,
316 const std::vector<HashJoinCondition> &join_conditions,
317 bool allow_spill_to_disk, JoinType join_type,
318 const Mem_root_array<Item *> &extra_conditions,
319 bool probe_input_batch_mode,
320 uint64_t *hash_table_generation);
322 bool Init() override;
324 int Read() override;
326 void SetNullRowFlag(bool is_null_row) override {
327 m_build_input->SetNullRowFlag(is_null_row);
328 m_probe_input->SetNullRowFlag(is_null_row);
329 }
331 void EndPSIBatchModeIfStarted() override {
332 m_build_input->EndPSIBatchModeIfStarted();
333 m_probe_input->EndPSIBatchModeIfStarted();
334 }
336 void UnlockRow() override {
337 // Since both inputs may have been materialized to disk, we cannot unlock
338 // them.
339 }
341 int ChunkCount() { return m_chunk_files_on_disk.size(); }
343 private:
344 /// Read all rows from the build input and store the rows into the in-memory
345 /// hash table. If the hash table goes full, the rest of the rows are written
346 /// out to chunk files on disk. See the class comment for more details.
347 ///
348 /// @retval true in case of error
349 bool BuildHashTable();
351 /// Read all rows from the next chunk file into the in-memory hash table.
352 /// See the class comment for details.
353 ///
354 /// @retval true in case of error
357 /// Read a single row from the probe iterator input into the tables' record
358 /// buffers. If we have started spilling to disk, the row is written out to a
359 /// chunk file on disk as well.
360 ///
361 /// The end condition is that either:
362 /// a) a row is ready in the tables' record buffers, and the state will be set
364 /// b) There are no more rows to process from the probe input, so the iterator
365 /// state will be LOADING_NEXT_CHUNK_PAIR.
366 ///
367 /// @retval true in case of error
370 /// Read a single row from the current probe chunk file into the tables'
371 /// record buffers. The end conditions are the same as for
372 /// ReadRowFromProbeIterator().
373 ///
374 /// @retval true in case of error
377 /// Read a single row from the probe row saving file into the tables' record
378 /// buffers.
379 ///
380 /// @retval true in case of error
383 // Do a lookup in the hash table for matching rows from the build input.
384 // The lookup is done by computing the join key from the probe input, and
385 // using that join key for doing a lookup in the hash table. If the join key
386 // contains one or more SQL NULLs, the row cannot match anything and will be
387 // skipped, and the iterator state will be READING_ROW_FROM_PROBE_INPUT. If
388 // not, the iterator state will be READING_FIRST_ROW_FROM_HASH_TABLE.
389 //
390 // After this function is called, ReadJoinedRow() will return false until
391 // there are no more matching rows for the computed join key.
394 /// Take the next matching row from the hash table, and put the row into the
395 /// build tables' record buffers. The function expects that
396 /// LookupProbeRowInHashTable() has been called up-front. The user must
397 /// call ReadJoinedRow() as long as it returns false, as there may be
398 /// multiple matching rows from the hash table. It is up to the caller to set
399 /// a new state in case of EOF.
400 ///
401 /// @retval 0 if a match was found and the row is put in the build tables'
402 /// record buffers
403 /// @retval -1 if there are no more matching rows in the hash table
404 int ReadJoinedRow();
406 // Have we degraded into on-disk hash join?
407 bool on_disk_hash_join() const { return !m_chunk_files_on_disk.empty(); }
409 /// Write the last row read from the probe input out to chunk files on disk,
410 /// if applicable.
411 ///
412 /// For inner joins, we must write all probe rows to chunk files, since we
413 /// need to match the row against rows from the build input that are written
414 /// out to chunk files. For semijoin, we can only write probe rows that do not
415 /// match any of the rows in the hash table. Writing a probe row with a
416 /// matching row in the hash table could cause the row to be returned multiple
417 /// times.
418 ///
419 /// @retval true in case of errors.
422 /// @retval true if the last joined row passes all of the extra conditions.
425 /// If true, reject duplicate keys in the hash table.
426 ///
427 /// Semijoins/antijoins are only interested in the first matching row from the
428 /// hash table, so we can avoid storing duplicate keys in order to save some
429 /// memory. However, this cannot be applied if we have any "extra" conditions:
430 /// the first matching row in the hash table may fail the extra condition(s).
431 ///
432 /// @retval true if we can reject duplicate keys in the hash table.
433 bool RejectDuplicateKeys() const {
434 return m_extra_condition == nullptr &&
436 }
438 /// Clear the row buffer and reset all iterators pointing to it. This may be
439 /// called multiple times to re-init the row buffer.
440 ///
441 /// @retval true in case of error. my_error has been called
442 bool InitRowBuffer();
444 /// Prepare to read the probe iterator from the beginning, and enable batch
445 /// mode if applicable. The iterator state will remain unchanged.
446 ///
447 /// @retval true in case of error. my_error has been called.
448 bool InitProbeIterator();
450 /// Mark that probe row saving is enabled, and prepare the probe row saving
451 /// file for writing.
452 /// @see m_write_to_probe_row_saving
453 ///
454 /// @retval true in case of error. my_error has been called.
457 /// Mark that we should read from the probe row saving file. The probe row
458 /// saving file is rewinded to the beginning.
459 /// @see m_read_from_probe_row_saving
460 ///
461 /// @retval true in case of error. my_error has been called.
464 /// Set the iterator state to the correct READING_ROW_FROM_PROBE_*-state.
465 /// Which state we end up in depends on which hash join type we are executing
466 /// (in-memory, on-disk or in-memory with hash table refill).
469 /// Read a joined row from the hash table, and see if it passes any extra
470 /// conditions. The last probe row read will also be written do disk if needed
471 /// (see WriteProbeRowToDiskIfApplicable).
472 ///
473 /// @retval -1 There are no more matching rows in the hash table.
474 /// @retval 0 A joined row is ready.
475 /// @retval 1 An error occurred.
478 enum class State {
479 // We are reading a row from the probe input, where the row comes from
480 // the iterator.
482 // We are reading a row from the probe input, where the row comes from a
483 // chunk file.
485 // We are reading a row from the probe input, where the row comes from a
486 // probe row saving file.
488 // The iterator is moving to the next pair of chunk files, where the chunk
489 // file from the build input will be loaded into the hash table.
491 // We are reading the first row returned from the hash table lookup that
492 // also passes extra conditions.
494 // We are reading the remaining rows returned from the hash table lookup.
496 // No more rows, both inputs are empty.
498 };
507 // The last row that was read from the hash table, or nullptr if none.
508 // All rows under the same key are linked together (see the documentation
509 // for LinkedImmutableString), so this allows iterating through the rows
510 // until the end.
513 // These structures holds the tables and columns that are needed for the hash
514 // join. Rows/columns that are not needed are filtered out in the constructor.
515 // We need to know which tables that belong to each iterator, so that we can
516 // compute the join key when needed.
521 // An in-memory hash table that holds rows from the build input (directly from
522 // the build input iterator, or from a chunk file). See the class comment for
523 // details on how and when this is used.
526 // A list of the join conditions (all of them are equi-join conditions).
529 // Array to hold the list of chunk files on disk in case we degrade into
530 // on-disk hash join.
533 // Which HashJoinChunk, if any, we are currently reading from, in both
535 // It is incremented during the state LOADING_NEXT_CHUNK_PAIR.
538 // The seed that is by xxHash64 when calculating the hash from a join
539 // key. We use xxHash64 when calculating the hash that is used for
540 // determining which chunk file a row should be placed in (in case of
541 // on-disk hash join); if we used the same hash function (and seed) for
542 // both operation, we would get a really bad hash table when loading
543 // a chunk file to the hash table. The number is chosen randomly and have
544 // no special meaning.
545 static constexpr uint32_t kChunkPartitioningHashSeed{899339};
547 // Which row we currently are reading from each of the hash join chunk file.
551 // How many rows we assume there will be when reading the build input.
552 // This is used to choose how many chunks we break it into on disk.
555 // The maximum number of HashJoinChunks that is allocated for each of the
556 // inputs in case we spill to disk. We might very well end up with an amount
557 // less than this number, but we keep an upper limit so we don't risk running
558 // out of file descriptors. We always use a power of two number of files,
559 // which allows us to do some optimizations when calculating which chunk a row
560 // should be placed in.
561 static constexpr size_t kMaxChunks = 128;
563 // A buffer that is used during two phases:
564 // 1) when constructing a join key from join conditions.
565 // 2) when moving a row between tables' record buffers and the hash table.
566 //
567 // There are two functions that needs this buffer; ConstructJoinKey() and
568 // StoreFromTableBuffers(). After calling one of these functions, the user
569 // must take responsibility of the data if it is needed for a longer lifetime.
570 //
571 // If there are no BLOB/TEXT column in the join, we calculate an upper bound
572 // of the row size that is used to preallocate this buffer. In the case of
573 // BLOB/TEXT columns, we cannot calculate a reasonable upper bound, and the
574 // row size is calculated per row. The allocated memory is kept for the
575 // duration of the iterator, so that we (most likely) avoid reallocations.
578 // Whether we should turn on batch mode for the probe input. Batch mode is
579 // enabled if the probe input consists of exactly one table, and said table
580 // can return more than one row and has no associated subquery condition.
581 // (See ShouldEnableBatchMode().)
584 // Whether we are allowed to spill to disk.
587 // Whether the build iterator has more rows. This is used to stop the hash
588 // join iterator asking for more rows when we know for sure that the entire
589 // build input is consumed. The variable is only used if m_allow_spill_to_disk
590 // is false, as we have to see if there are more rows in the build input after
591 // the probe input is consumed.
594 // What kind of join the iterator should execute.
597 // If not nullptr, an extra condition that the iterator will evaluate after a
598 // lookup in the hash table is done, but before the row is returned. This is
599 // needed in case we have a semijoin condition that is not an equi-join
600 // condition (i.e. 't1.col1 < t2.col1').
603 // Whether we should write rows from the probe input to the probe row saving
604 // write file. See the class comment on HashJoinIterator for details around
605 // probe row saving.
608 // Whether we should read rows from the probe row saving read file. See the
609 // class comment on HashJoinIterator for details around probe row saving.
612 // The probe row saving files where unmatched probe rows are written to and
613 // read from.
617 // Which row we currently are reading from in the probe row saving read file.
618 // Used to know whether we have reached the end of the file. How many files
619 // the probe row saving read file contains is contained in the HashJoinChunk
620 // (see m_probe_row_saving_read_file).
623 // The "type" of hash join we are executing. We currently have three different
624 // types of hash join:
625 // - In memory: We do everything in memory without any refills of the hash
626 // table. Each input is read only once, and nothing is written to disk.
627 // - Spill to disk: If the build input does not fit in memory, we write both
628 // inputs out to a set of chunk files. Both inputs are partitioned using a
629 // hash function over the join attribute, ensuring that matching rows can be
630 // found in the same set of chunk files. Each pair of chunk file is then
631 // processed as an in-memory hash join.
632 // - In memory with hash table refill: This is enabled if we are not allowed
633 // to spill to disk, and the build input does not fit in memory. We read as
634 // much as possible from the build input into the hash table. We then read
635 // the entire probe input, probing for matching rows in the hash table.
636 // When the probe input returns EOF, the hash table is refilled with the
637 // rows that did not fit the first time. The entire probe input is read
638 // again, and this is repeated until the entire build input is consumed.
639 enum class HashJoinType {
643 };
646 // The match flag for the last probe row read from chunk file.
647 //
648 // This is needed if a outer join spills to disk; a probe row can match a row
649 // from the build input we haven't seen yet (it's been written out to disk
650 // because the hash table was full). So when reading a probe row from a chunk
651 // file, this variable holds the match flag. This flag must be a class member,
652 // since one probe row may match multiple rows from the hash table; the
653 // execution will go out of HashJoinIterator::Read() between each matching
654 // row, causing any local match flag to lose the match flag info from the last
655 // probe row read.
Definition: hash_join_chunk.h:66
Definition: hash_join_iterator.h:253
bool BuildHashTable()
Read all rows from the build input and store the rows into the in-memory hash table.
void EndPSIBatchModeIfStarted() override
Ends performance schema batch mode, if started.
Definition: hash_join_iterator.h:331
const unique_ptr_destroy_only< RowIterator > m_build_input
Definition: hash_join_iterator.h:504
bool ReadRowFromProbeRowSavingFile()
Read a single row from the probe row saving file into the tables' record buffers.
bool JoinedRowPassesExtraConditions() const
int ReadNextJoinedRowFromHashTable()
Read a joined row from the hash table, and see if it passes any extra conditions.
Definition: hash_join_iterator.h:478
void UnlockRow() override
Definition: hash_join_iterator.h:336
Prealloced_array< HashJoinCondition, 4 > m_join_conditions
Definition: hash_join_iterator.h:527
bool m_build_iterator_has_more_rows
Definition: hash_join_iterator.h:592
HashJoinChunk m_probe_row_saving_write_file
Definition: hash_join_iterator.h:614
bool WriteProbeRowToDiskIfApplicable()
Write the last row read from the probe input out to chunk files on disk, if applicable.
Mem_root_array< ChunkPair > m_chunk_files_on_disk
Definition: hash_join_iterator.h:531
pack_rows::TableCollection m_probe_input_tables
Definition: hash_join_iterator.h:517
bool InitRowBuffer()
Clear the row buffer and reset all iterators pointing to it.
int Read() override
Read a single row.
String m_temporary_row_and_join_key_buffer
Definition: hash_join_iterator.h:576
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:326
State m_state
Definition: hash_join_iterator.h:500
void LookupProbeRowInHashTable()
LinkedImmutableString m_current_row
Definition: hash_join_iterator.h:511
static constexpr size_t kMaxChunks
Definition: hash_join_iterator.h:561
int ReadJoinedRow()
Take the next matching row from the hash table, and put the row into the build tables' record buffers...
bool m_read_from_probe_row_saving
Definition: hash_join_iterator.h:610
uint64_t m_last_hash_table_generation
Definition: hash_join_iterator.h:502
ha_rows m_build_chunk_current_row
Definition: hash_join_iterator.h:548
Definition: hash_join_iterator.h:639
bool ReadNextHashJoinChunk()
Read all rows from the next chunk file into the in-memory hash table.
bool m_probe_input_batch_mode
Definition: hash_join_iterator.h:582
HashJoinType m_hash_join_type
Definition: hash_join_iterator.h:644
static constexpr uint32_t kChunkPartitioningHashSeed
Definition: hash_join_iterator.h:545
bool RejectDuplicateKeys() const
If true, reject duplicate keys in the hash table.
Definition: hash_join_iterator.h:433
bool ReadRowFromProbeChunkFile()
Read a single row from the current probe chunk file into the tables' record buffers.
bool m_probe_row_match_flag
Definition: hash_join_iterator.h:656
pack_rows::TableCollection m_build_input_tables
Definition: hash_join_iterator.h:518
const unique_ptr_destroy_only< RowIterator > m_probe_input
Definition: hash_join_iterator.h:505
int ChunkCount()
Definition: hash_join_iterator.h:341
ha_rows m_probe_chunk_current_row
Definition: hash_join_iterator.h:549
HashJoinChunk m_probe_row_saving_read_file
Definition: hash_join_iterator.h:615
uint64_t * m_hash_table_generation
Definition: hash_join_iterator.h:501
ha_rows m_probe_row_saving_read_file_current_row
Definition: hash_join_iterator.h:621
const double m_estimated_build_rows
Definition: hash_join_iterator.h:553
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, bool probe_input_batch_mode, uint64_t *hash_table_generation)
Construct a HashJoinIterator.
int m_current_chunk
Definition: hash_join_iterator.h:536
bool Init() override
Initialize or reinitialize the iterator.
const JoinType m_join_type
Definition: hash_join_iterator.h:595
bool m_allow_spill_to_disk
Definition: hash_join_iterator.h:585
bool on_disk_hash_join() const
Definition: hash_join_iterator.h:407
bool InitProbeIterator()
Prepare to read the probe iterator from the beginning, and enable batch mode if applicable.
const table_map m_tables_to_get_rowid_for
Definition: hash_join_iterator.h:519
void SetReadingProbeRowState()
Set the iterator state to the correct READING_ROW_FROM_PROBE_*-state.
Item * m_extra_condition
Definition: hash_join_iterator.h:601
hash_join_buffer::HashJoinRowBuffer m_row_buffer
Definition: hash_join_iterator.h:524
bool InitWritingToProbeRowSavingFile()
Mark that probe row saving is enabled, and prepare the probe row saving file for writing.
bool InitReadingFromProbeRowSavingFile()
Mark that we should read from the probe row saving file.
bool m_write_to_probe_row_saving
Definition: hash_join_iterator.h:606
bool ReadRowFromProbeIterator()
Read a single row from the probe iterator input into the tables' record buffers.
Base class that is used to represent any kind of expression in a relational query.
Definition: item.h:850
Definition: sql_optimizer.h:125
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:33
Definition: hash_join_buffer.h:161
A structure that contains a list of tables for the hash join operation, and some pre-computed propert...
Definition: pack_rows.h:83
This file contains the HashJoinRowBuffer class and related functions/classes.
ImmutableString defines a storage format for strings that is designed to be as compact as possible,...
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,...
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