MySQL  8.0.27
Source Code Documentation
hash_join_iterator.h
Go to the documentation of this file.
1 #ifndef SQL_HASH_JOIN_ITERATOR_H_
2 #define SQL_HASH_JOIN_ITERATOR_H_
3 
4 /* Copyright (c) 2019, 2021, 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"
35 #include "sql/hash_join_buffer.h"
36 #include "sql/hash_join_chunk.h"
37 #include "sql/immutable_string.h"
38 #include "sql/item_cmpfunc.h"
39 #include "sql/join_type.h"
40 #include "sql/mem_root_array.h"
41 #include "sql/pack_rows.h"
42 #include "sql/row_iterator.h"
43 #include "sql_string.h"
44 
45 class Item;
46 class JOIN;
47 class THD;
48 
49 struct 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 class 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);
321 
322  bool Init() override;
323 
324  int Read() override;
325 
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  }
330 
331  void EndPSIBatchModeIfStarted() override {
332  m_build_input->EndPSIBatchModeIfStarted();
333  m_probe_input->EndPSIBatchModeIfStarted();
334  }
335 
336  void UnlockRow() override {
337  // Since both inputs may have been materialized to disk, we cannot unlock
338  // them.
339  }
340 
341  private:
342  /// Read all rows from the build input and store the rows into the in-memory
343  /// hash table. If the hash table goes full, the rest of the rows are written
344  /// out to chunk files on disk. See the class comment for more details.
345  ///
346  /// @retval true in case of error
347  bool BuildHashTable();
348 
349  /// Read all rows from the next chunk file into the in-memory hash table.
350  /// See the class comment for details.
351  ///
352  /// @retval true in case of error
353  bool ReadNextHashJoinChunk();
354 
355  /// Read a single row from the probe iterator input into the tables' record
356  /// buffers. If we have started spilling to disk, the row is written out to a
357  /// chunk file on disk as well.
358  ///
359  /// The end condition is that either:
360  /// a) a row is ready in the tables' record buffers, and the state will be set
361  /// to READING_FIRST_ROW_FROM_HASH_TABLE.
362  /// b) There are no more rows to process from the probe input, so the iterator
363  /// state will be LOADING_NEXT_CHUNK_PAIR.
364  ///
365  /// @retval true in case of error
367 
368  /// Read a single row from the current probe chunk file into the tables'
369  /// record buffers. The end conditions are the same as for
370  /// ReadRowFromProbeIterator().
371  ///
372  /// @retval true in case of error
374 
375  /// Read a single row from the probe row saving file into the tables' record
376  /// buffers.
377  ///
378  /// @retval true in case of error
380 
381  // Do a lookup in the hash table for matching rows from the build input.
382  // The lookup is done by computing the join key from the probe input, and
383  // using that join key for doing a lookup in the hash table. If the join key
384  // contains one or more SQL NULLs, the row cannot match anything and will be
385  // skipped, and the iterator state will be READING_ROW_FROM_PROBE_INPUT. If
386  // not, the iterator state will be READING_FIRST_ROW_FROM_HASH_TABLE.
387  //
388  // After this function is called, ReadJoinedRow() will return false until
389  // there are no more matching rows for the computed join key.
391 
392  /// Take the next matching row from the hash table, and put the row into the
393  /// build tables' record buffers. The function expects that
394  /// LookupProbeRowInHashTable() has been called up-front. The user must
395  /// call ReadJoinedRow() as long as it returns false, as there may be
396  /// multiple matching rows from the hash table. It is up to the caller to set
397  /// a new state in case of EOF.
398  ///
399  /// @retval 0 if a match was found and the row is put in the build tables'
400  /// record buffers
401  /// @retval -1 if there are no more matching rows in the hash table
402  int ReadJoinedRow();
403 
404  // Have we degraded into on-disk hash join?
405  bool on_disk_hash_join() const { return !m_chunk_files_on_disk.empty(); }
406 
407  /// Write the last row read from the probe input out to chunk files on disk,
408  /// if applicable.
409  ///
410  /// For inner joins, we must write all probe rows to chunk files, since we
411  /// need to match the row against rows from the build input that are written
412  /// out to chunk files. For semijoin, we can only write probe rows that do not
413  /// match any of the rows in the hash table. Writing a probe row with a
414  /// matching row in the hash table could cause the row to be returned multiple
415  /// times.
416  ///
417  /// @retval true in case of errors.
419 
420  /// @retval true if the last joined row passes all of the extra conditions.
421  bool JoinedRowPassesExtraConditions() const;
422 
423  /// If true, reject duplicate keys in the hash table.
424  ///
425  /// Semijoins/antijoins are only interested in the first matching row from the
426  /// hash table, so we can avoid storing duplicate keys in order to save some
427  /// memory. However, this cannot be applied if we have any "extra" conditions:
428  /// the first matching row in the hash table may fail the extra condition(s).
429  ///
430  /// @retval true if we can reject duplicate keys in the hash table.
431  bool RejectDuplicateKeys() const {
432  return m_extra_condition == nullptr &&
434  }
435 
436  /// Clear the row buffer and reset all iterators pointing to it. This may be
437  /// called multiple times to re-init the row buffer.
438  ///
439  /// @retval true in case of error. my_error has been called
440  bool InitRowBuffer();
441 
442  /// Prepare to read the probe iterator from the beginning, and enable batch
443  /// mode if applicable. The iterator state will remain unchanged.
444  ///
445  /// @retval true in case of error. my_error has been called.
446  bool InitProbeIterator();
447 
448  /// Mark that probe row saving is enabled, and prepare the probe row saving
449  /// file for writing.
450  /// @see m_write_to_probe_row_saving
451  ///
452  /// @retval true in case of error. my_error has been called.
454 
455  /// Mark that we should read from the probe row saving file. The probe row
456  /// saving file is rewinded to the beginning.
457  /// @see m_read_from_probe_row_saving
458  ///
459  /// @retval true in case of error. my_error has been called.
461 
462  /// Set the iterator state to the correct READING_ROW_FROM_PROBE_*-state.
463  /// Which state we end up in depends on which hash join type we are executing
464  /// (in-memory, on-disk or in-memory with hash table refill).
466 
467  /// Read a joined row from the hash table, and see if it passes any extra
468  /// conditions. The last probe row read will also be written do disk if needed
469  /// (see WriteProbeRowToDiskIfApplicable).
470  ///
471  /// @retval -1 There are no more matching rows in the hash table.
472  /// @retval 0 A joined row is ready.
473  /// @retval 1 An error occured.
475 
476  enum class State {
477  // We are reading a row from the probe input, where the row comes from
478  // the iterator.
480  // We are reading a row from the probe input, where the row comes from a
481  // chunk file.
483  // We are reading a row from the probe input, where the row comes from a
484  // probe row saving file.
486  // The iterator is moving to the next pair of chunk files, where the chunk
487  // file from the build input will be loaded into the hash table.
489  // We are reading the first row returned from the hash table lookup that
490  // also passes extra conditions.
492  // We are reading the remaining rows returned from the hash table lookup.
494  // No more rows, both inputs are empty.
496  };
497 
501 
504 
505  // The last row that was read from the hash table, or nullptr if none.
506  // All rows under the same key are linked together (see the documentation
507  // for LinkedImmutableString), so this allows iterating through the rows
508  // until the end.
510 
511  // These structures holds the tables and columns that are needed for the hash
512  // join. Rows/columns that are not needed are filtered out in the constructor.
513  // We need to know which tables that belong to each iterator, so that we can
514  // compute the join key when needed.
518 
519  // An in-memory hash table that holds rows from the build input (directly from
520  // the build input iterator, or from a chunk file). See the class comment for
521  // details on how and when this is used.
523 
524  // A list of the join conditions (all of them are equi-join conditions).
526 
527  // Array to hold the list of chunk files on disk in case we degrade into
528  // on-disk hash join.
530 
531  // Which HashJoinChunk, if any, we are currently reading from, in both
532  // LOADING_NEXT_CHUNK_PAIR and READING_ROW_FROM_PROBE_CHUNK_FILE.
533  // It is incremented during the state LOADING_NEXT_CHUNK_PAIR.
535 
536  // The seed that is by xxHash64 when calculating the hash from a join
537  // key. We use xxHash64 when calculating the hash that is used for
538  // determining which chunk file a row should be placed in (in case of
539  // on-disk hash join); if we used the same hash function (and seed) for
540  // both operation, we would get a really bad hash table when loading
541  // a chunk file to the hash table. The number is chosen randomly and have
542  // no special meaning.
543  static constexpr uint32_t kChunkPartitioningHashSeed{899339};
544 
545  // Which row we currently are reading from each of the hash join chunk file.
548 
549  // How many rows we assume there will be when reading the build input.
550  // This is used to choose how many chunks we break it into on disk.
552 
553  // The maximum number of HashJoinChunks that is allocated for each of the
554  // inputs in case we spill to disk. We might very well end up with an amount
555  // less than this number, but we keep an upper limit so we don't risk running
556  // out of file descriptors. We always use a power of two number of files,
557  // which allows us to do some optimizations when calculating which chunk a row
558  // should be placed in.
559  static constexpr size_t kMaxChunks = 128;
560 
561  // A buffer that is used during two phases:
562  // 1) when constructing a join key from join conditions.
563  // 2) when moving a row between tables' record buffers and the hash table.
564  //
565  // There are two functions that needs this buffer; ConstructJoinKey() and
566  // StoreFromTableBuffers(). After calling one of these functions, the user
567  // must take responsiblity of the data if it is needed for a longer lifetime.
568  //
569  // If there are no BLOB/TEXT column in the join, we calculate an upper bound
570  // of the row size that is used to preallocate this buffer. In the case of
571  // BLOB/TEXT columns, we cannot calculate a reasonable upper bound, and the
572  // row size is calculated per row. The allocated memory is kept for the
573  // duration of the iterator, so that we (most likely) avoid reallocations.
575 
576  // Whether we should turn on batch mode for the probe input. Batch mode is
577  // enabled if the probe input consists of exactly one table, and said table
578  // can return more than one row and has no associated subquery condition.
579  // (See ShouldEnableBatchMode().)
581 
582  // Whether we are allowed to spill to disk.
584 
585  // Whether the build iterator has more rows. This is used to stop the hash
586  // join iterator asking for more rows when we know for sure that the entire
587  // build input is consumed. The variable is only used if m_allow_spill_to_disk
588  // is false, as we have to see if there are more rows in the build input after
589  // the probe input is consumed.
591 
592  // What kind of join the iterator should execute.
594 
595  // If not nullptr, an extra condition that the iterator will evaluate after a
596  // lookup in the hash table is done, but before the row is returned. This is
597  // needed in case we have a semijoin condition that is not an equi-join
598  // condition (i.e. 't1.col1 < t2.col1').
600 
601  // Whether we should write rows from the probe input to the probe row saving
602  // write file. See the class comment on HashJoinIterator for details around
603  // probe row saving.
605 
606  // Whether we should read rows from the probe row saving read file. See the
607  // class comment on HashJoinIterator for details around probe row saving.
609 
610  // The probe row saving files where unmatched probe rows are written to and
611  // read from.
614 
615  // Which row we currently are reading from in the probe row saving read file.
616  // Used to know whether we have reached the end of the file. How many files
617  // the probe row saving read file contains is contained in the HashJoinChunk
618  // (see m_probe_row_saving_read_file).
620 
621  // The "type" of hash join we are executing. We currently have three different
622  // types of hash join:
623  // - In memory: We do everything in memory without any refills of the hash
624  // table. Each input is read only once, and nothing is written to disk.
625  // - Spill to disk: If the build input does not fit in memory, we write both
626  // inputs out to a set of chunk files. Both inputs are partitioned using a
627  // hash function over the join attribute, ensuring that matching rows can be
628  // found in the same set of chunk files. Each pair of chunk file is then
629  // processed as an in-memory hash join.
630  // - In memory with hash table refill: This is enabled if we are not allowed
631  // to spill to disk, and the build input does not fit in memory. We read as
632  // much as possible from the build input into the hash table. We then read
633  // the entire probe input, probing for matching rows in the hash table.
634  // When the probe input returns EOF, the hash table is refilled with the
635  // rows that did not fit the first time. The entire probe input is read
636  // again, and this is repeated until the entire build input is consumed.
637  enum class HashJoinType {
638  IN_MEMORY,
641  };
643 
644  // The match flag for the last probe row read from chunk file.
645  //
646  // This is needed if a outer join spills to disk; a probe row can match a row
647  // from the build input we haven't seen yet (it's been written out to disk
648  // because the hash table was full). So when reading a probe row from a chunk
649  // file, this variable holds the match flag. This flag must be a class member,
650  // since one probe row may match multiple rows from the hash table; the
651  // execution will go out of HashJoinIterator::Read() between each matching
652  // row, causing any local match flag to lose the match flag info from the last
653  // probe row read.
655 };
656 
657 #endif // SQL_HASH_JOIN_ITERATOR_H_
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.
Definition: hash_join_iterator.cc:410
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:502
bool ReadRowFromProbeRowSavingFile()
Read a single row from the probe row saving file into the tables' record buffers.
Definition: hash_join_iterator.cc:796
bool JoinedRowPassesExtraConditions() const
Definition: hash_join_iterator.cc:946
int ReadNextJoinedRowFromHashTable()
Read a joined row from the hash table, and see if it passes any extra conditions.
Definition: hash_join_iterator.cc:954
State
Definition: hash_join_iterator.h:476
void UnlockRow() override
Definition: hash_join_iterator.h:336
Prealloced_array< HashJoinCondition, 4 > m_join_conditions
Definition: hash_join_iterator.h:525
bool m_build_iterator_has_more_rows
Definition: hash_join_iterator.h:590
HashJoinChunk m_probe_row_saving_write_file
Definition: hash_join_iterator.h:612
bool WriteProbeRowToDiskIfApplicable()
Write the last row read from the probe input out to chunk files on disk, if applicable.
Definition: hash_join_iterator.cc:909
Mem_root_array< ChunkPair > m_chunk_files_on_disk
Definition: hash_join_iterator.h:529
pack_rows::TableCollection m_probe_input_tables
Definition: hash_join_iterator.h:515
bool InitRowBuffer()
Clear the row buffer and reset all iterators pointing to it.
Definition: hash_join_iterator.cc:111
int Read() override
Read a single row.
Definition: hash_join_iterator.cc:1056
String m_temporary_row_and_join_key_buffer
Definition: hash_join_iterator.h:574
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:498
void LookupProbeRowInHashTable()
Definition: hash_join_iterator.cc:851
LinkedImmutableString m_current_row
Definition: hash_join_iterator.h:509
static constexpr size_t kMaxChunks
Definition: hash_join_iterator.h:559
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:896
bool m_read_from_probe_row_saving
Definition: hash_join_iterator.h:608
uint64_t m_last_hash_table_generation
Definition: hash_join_iterator.h:500
ha_rows m_build_chunk_current_row
Definition: hash_join_iterator.h:546
HashJoinType
Definition: hash_join_iterator.h:637
bool ReadNextHashJoinChunk()
Read all rows from the next chunk file into the in-memory hash table.
Definition: hash_join_iterator.cc:567
bool m_probe_input_batch_mode
Definition: hash_join_iterator.h:580
HashJoinType m_hash_join_type
Definition: hash_join_iterator.h:642
static constexpr uint32_t kChunkPartitioningHashSeed
Definition: hash_join_iterator.h:543
bool RejectDuplicateKeys() const
If true, reject duplicate keys in the hash table.
Definition: hash_join_iterator.h:431
bool ReadRowFromProbeChunkFile()
Read a single row from the current probe chunk file into the tables' record buffers.
Definition: hash_join_iterator.cc:753
bool m_probe_row_match_flag
Definition: hash_join_iterator.h:654
pack_rows::TableCollection m_build_input_tables
Definition: hash_join_iterator.h:516
const unique_ptr_destroy_only< RowIterator > m_probe_input
Definition: hash_join_iterator.h:503
ha_rows m_probe_chunk_current_row
Definition: hash_join_iterator.h:547
HashJoinChunk m_probe_row_saving_read_file
Definition: hash_join_iterator.h:613
uint64_t * m_hash_table_generation
Definition: hash_join_iterator.h:499
ha_rows m_probe_row_saving_read_file_current_row
Definition: hash_join_iterator.h:619
const double m_estimated_build_rows
Definition: hash_join_iterator.h:551
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.
Definition: hash_join_iterator.cc:63
int m_current_chunk
Definition: hash_join_iterator.h:534
bool Init() override
Initialize or reinitialize the iterator.
Definition: hash_join_iterator.cc:148
const JoinType m_join_type
Definition: hash_join_iterator.h:593
bool m_allow_spill_to_disk
Definition: hash_join_iterator.h:583
bool on_disk_hash_join() const
Definition: hash_join_iterator.h:405
bool InitProbeIterator()
Prepare to read the probe iterator from the beginning, and enable batch mode if applicable.
Definition: hash_join_iterator.cc:135
const table_map m_tables_to_get_rowid_for
Definition: hash_join_iterator.h:517
void SetReadingProbeRowState()
Set the iterator state to the correct READING_ROW_FROM_PROBE_*-state.
Definition: hash_join_iterator.cc:1125
Item * m_extra_condition
Definition: hash_join_iterator.h:599
hash_join_buffer::HashJoinRowBuffer m_row_buffer
Definition: hash_join_iterator.h:522
bool InitWritingToProbeRowSavingFile()
Mark that probe row saving is enabled, and prepare the probe row saving file for writing.
Definition: hash_join_iterator.cc:1112
bool InitReadingFromProbeRowSavingFile()
Mark that we should read from the probe row saving file.
Definition: hash_join_iterator.cc:1118
bool m_write_to_probe_row_saving
Definition: hash_join_iterator.h:604
bool ReadRowFromProbeIterator()
Read a single row from the probe iterator input into the tables' record buffers.
Definition: hash_join_iterator.cc:676
Base class that is used to represent any kind of expression in a relational query.
Definition: item.h:802
Definition: sql_optimizer.h:125
LinkedImmutableString is designed for storing rows (values) in hash join.
Definition: immutable_string.h:172
bool empty() const
Definition: mem_root_array.h:398
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:60
THD * thd() const
Definition: row_iterator.h:190
Using this class is fraught with peril, and you need to be very careful when doing so.
Definition: sql_string.h:165
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_class.h:821
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,...
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:464
This file includes constants used by all storage engines.
my_off_t ha_rows
Definition: my_base.h:1138
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:178
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