PolarDB：Gunakan Hash Match untuk Melakukan Operasi yang Diaktifkan IMCI

Rencana Eksekusi

Implementasi operator Hash Match terdiri dari dua fase: fase pembuatan dan fase pencarian. Pada fase pembuatan, predikat join digunakan sebagai kunci untuk membangun setiap baris tabel kiri ke dalam tabel hash. Pada fase pencarian, tabel kanan dilintasi dan entri data dicocokkan berdasarkan predikat join tabel kanan dan tabel hash. Kemudian, set hasil dikeluarkan berdasarkan hasil pencocokan dari berbagai jenis join.

Dalam fase pembuatan, satu tabel hash dapat digunakan untuk mencakup semua data dalam tabel kiri. Namun, tabel hash yang berisi semua data terlalu besar, menyebabkan konflik serius atau memerlukan penskalaan keluar atau naik selama proses pembuatan. Oleh karena itu, data dalam tabel kiri dipartisi berdasarkan aturan tertentu, dan tabel hash independen dibangun untuk setiap partisi. Dalam fase pencarian, sistem mencari tabel hash di partisi tempat baris tabel kanan berada.

Fase Pembuatan

Dalam operasi yang diaktifkan IMCI, fitur pembuatan operator Hash Match diimplementasikan dalam doOpen, yang terdiri dari dua fase: doBuild dan doMerge. Setiap fase menggunakan grup utas untuk melakukan pemrosesan bersamaan.

DoBuild

Dalam fase doBuild, thread pekerja dalam grup utas membangun tabel hash independen untuk setiap partisi menggunakan data dalam tabel kiri.

Tabel hash dibangun untuk setiap partisi menggunakan thread pekerja. Selain itu, sekelompok chunk dihasilkan untuk menyimpan hasil materialisasi. Nilai tipe UInt64 dari tabel hash hanya menunjukkan posisi chunk yang sesuai dengan kunci saat ini. Nilai UInt64 dapat dibagi menjadi tiga bagian berikut berdasarkan bit: UInt16, UInt16, dan UInt32. Nilai UInt16 pertama menunjukkan thread pekerja tempat chunk tersebut milik. Nilai UInt16 kedua menunjukkan offset chunk. Nilai UInt32 menunjukkan pengindeksan array chunk. Thread pekerja mengambil tuple dari tabel kiri secara paralel dan menyisipkan tuple ke dalam tabel hash yang sesuai dengan thread pekerja dan partisi tanpa mengunci berdasarkan aturan partisi. Proses ini diulang hingga semua data tabel kiri diambil.

DoMerge

Setelah fase doBuild selesai, tabel hash dibangun untuk setiap partisi menggunakan thread pekerja. Tabel hash yang dibangun dalam fase pembuatan digunakan dalam fase pencarian untuk menentukan apakah pencarian cocok. Oleh karena itu, jika data dipartisi dalam fase pembuatan, data harus dicari dalam tabel hash yang sesuai berdasarkan aturan partisi dalam fase pencarian. Dalam fase doBuild, tabel hash dibangun untuk setiap partisi. Mereka dapat dicari satu per satu dalam fase pencarian. Namun, proses ini tidak nyaman dan mengurangi kinerja kueri. Oleh karena itu, operator Hash Match menggabungkan semua tabel hash dalam partisi menjadi satu dalam fase doMerge.

Fase doMerge dilakukan oleh grup utas. Agar mencegah sinkronisasi kunci yang tidak bermakna, tabel hash dalam partisi digabungkan oleh thread pekerja secara independen. Jumlah partisi lebih besar dari jumlah thread pekerja. Oleh karena itu, dalam fase doMerge, beban kerja setiap thread pekerja pada dasarnya sama.

Pengalihan Data dalam Fase Pembuatan

Beban kerja setiap thread pekerja pada dasarnya sama. Oleh karena itu, kita dapat mengasumsikan bahwa jumlah data yang diproses oleh setiap thread pekerja sama dan nilai rata-rata total memori dapat diambil sebagai kuota memori untuk setiap thread pekerja.

Ukuran memori terbatas dan operator Hash Match tidak dapat menyimpan tabel hash dan chunk semua partisi di memori. Tabel hash dan chunk semuanya dibagi berdasarkan partisi. Oleh karena itu, data berlebih dialihkan ke disk berdasarkan partisi jika memori tidak mencukupi.

Dengan cara ini, operasi dalam fase pembuatan dan fase pencarian dapat dilakukan secara normal dalam partisi di memori. Saat ini, operator Hash Match mulai dari partisi tertinggi untuk mengalihkan data seluruh partisi hingga partisi di memori dapat diproses secara normal. Jika tidak ada partisi yang dapat diproses, pengecualian OutOfMemoryError dilemparkan.

Dalam fase doBuild, jika pasangan nilai-kunci tidak dapat ditambahkan ke tabel hash atau data chunk tidak dapat disimpan dalam thread pekerja karena memori tidak mencukupi, data dalam partisi tertinggi thread pekerja harus dialihkan ke disk. Chunk ditulis ke file sementara, memori untuk chunk dilepaskan, dan tabel hash dihapus. Ketika partisi perlu diproses, chunk dalam file sementara dibaca, dan tabel hash partisi dibangun menggunakan chunk. Nomor partisi tertinggi untuk thread pekerja terlihat oleh thread pekerja lainnya. Jika nomor partisi tertinggi untuk thread pekerja lebih tinggi daripada thread pekerja lainnya, pekerja memperbarui nomor partisi tertinggi dan melepaskan memori. Dalam fase doBuild, thread pekerja tidak membangun tabel hash dalam partisi yang nomor partisinya lebih besar dari nomor tertinggi yang ada. Data disimpan dalam chunk dan dialihkan ke disk setelah chunk penuh.

Fase Pencarian

Dalam fase pembuatan, tabel kiri dibaca dan digunakan untuk membangun tabel hash. Dalam fase pencarian, data tabel kanan dibaca dan dikeluarkan berdasarkan hasil pencocokan tabel hash yang dibangun dalam fase pembuatan. Data dipartisi dalam fase pembuatan. Oleh karena itu, operasi dalam fase pencarian harus dilakukan berdasarkan aturan partisi yang sama.

DoFetch

Dalam fase pencarian, grup utas digunakan untuk memproses data dan didorong oleh operasi pengambilan memori pada node induk. Dalam fase doFetch, thread pekerja operator Hash Match mengambil data tabel kanan dan mencari tupel yang diambil dalam tabel hash partisi tertentu. Tupel yang dicari diproses berdasarkan hasil pencocokan. Proses ini diulang hingga semua thread pekerja mengambil data dari tabel kanan.

Pengalihan Data dalam Fase Pencarian

Jika memori tidak cukup untuk menyimpan semua partisi dalam fase pembuatan, memori dan disk dalam fase pencarian harus dipartisi secara terpisah.

Dalam fase doFetch, setelah thread pekerja mengambil data dari tabel kanan, jika partisi yang sesuai dengan tupel berada di memori, thread pekerja langsung mencari tabel hash untuk pencocokan. Jika partisi berada di disk, tupel perlu disimpan dalam chunk partisi tempat thread pekerja milik. Jika chunk penuh, data harus dialihkan ke disk dan memori chunk harus dilepaskan. Setelah semua thread pekerja mengambil data dari tabel kanan dan fase pencarian selesai, data partisi di memori diproses dan dapat dilepaskan.

Setelah semua partisi di memori diproses, partisi di disk diproses. Data partisi di disk disimpan dalam file sementara yang berbeda berdasarkan partisi. Oleh karena itu, untuk mencegah sinkronisasi kunci, dalam fase pencarian, setiap partisi disk diproses secara independen oleh thread pekerja. Jumlah partisi lebih besar dari jumlah thread pekerja. Oleh karena itu, beban kerja setiap thread pekerja pada dasarnya sama.

Pemrosesan partisi di disk menggunakan pekerja juga terdiri dari dua fase: fase pembuatan dan fase pencarian.

1. Dalam fase pembuatan, thread pekerja membaca data dari file sementara partisi tabel kiri dan membuat serial chunk. Kemudian, thread pekerja membangun tabel hash berdasarkan data chunk. Proses ini diulang hingga semua thread pekerja membaca data dari tabel kiri.

2. Dalam fase pencarian, thread pekerja membaca data dari file sementara partisi tabel kanan dan membuat serial chunk. Kemudian, thread pekerja mencari dan memproses tupel berdasarkan hasil pencocokan. Proses ini diulang hingga semua thread pekerja membaca data dari tabel kiri.

Setelah partisi diproses, operator hash match selesai. Pemrosesan partisi memori dan partisi disk dijelaskan secara berbeda dalam referensi ini. Namun, implementasinya disatukan dalam satu set kode.

Proses Terkait Pencarian

Proses terkait pencarian terdiri dari langkah-langkah berikut: ProbeMem, ProbeLeft, dan ProbeDisk. Semua langkah dilakukan dengan menggunakan fungsi probe.

1. Dalam tahap ProbeMen, data dibaca dari tabel kanan dan diproses di memori atau disk berdasarkan partisi data. Jika Anda tidak memanggil fungsi probe di memori, simpan data dalam file sementara. Dengan cara ini, dalam langkah ProbeDisk, data dalam partisi disk tertentu dapat dimuat dan diproses menggunakan fungsi probe.

2. Dalam tahap ProbeLeft, operasi LEFT JOIN seperti LEFT OUTER JOIN, LEFT SEMI JOIN, dan LEFT ANTI SEMI JOIN dilakukan. Semua pasangan nilai-kunci dalam tabel hash dilintasi dan tupel yang cocok atau tidak cocok disaring.

3. Dalam tahap ProbeDisk, operasi pencarian dilakukan pada partisi disk berdasarkan partisi. Ketika partisi disk diproses, chunk dalam file sementara dimuat dan diproses oleh fungsi probe. Jika operasi LEFT JOIN dilakukan, operasi JOIN harus dipanggil untuk memproses partisi.

Logika Join

Operator Hash Match mendukung INNER JOIN, LEFT OUTER JOIN, RIGHT OUTER JOIN, LEFT SEMI JOIN, LEFT ANTI SEMI JOIN, RIGHT SEMI JOIN, RIGHT ANTI SEMI JOIN, dan fitur PostFilter. Semua operasi JOIN terdiri dari fase pembuatan dan fase pencarian. Fase pembuatan pada dasarnya sama kecuali untuk pemrosesan nilai NULL. Fase pencarian berbeda. Bagian berikut adalah gambaran umum logika pemrosesan berbagai jenis operasi JOIN.

Inner

Jika sebuah tupel dalam tabel kanan bukan NULL dan cocok dengan tabel hash yang dibuat berdasarkan tabel kiri, tupel dalam tabel kiri dan kanan dikeluarkan.

LeftOuter

Jika sebuah tupel dalam tabel kanan bukan NULL dan cocok dengan tabel hash yang dibuat berdasarkan tabel kiri, tupel dalam tabel kiri dan kanan dikeluarkan. Semua tupel dalam tabel kiri yang tidak cocok dikeluarkan, dan posisi yang sesuai dalam tabel kanan diatur ke NULL. Jika PostFilter ada dalam LEFT OUTER JOIN, tabel hash yang cocok yang dibuat berdasarkan tabel kiri harus diverifikasi menggunakan fitur PostFilter.

RightOuter

Jika sebuah tupel dalam tabel kanan bukan NULL dan cocok dengan tabel hash yang dibuat berdasarkan tabel kiri, tupel dalam tabel kiri dan kanan dikeluarkan. Sebaliknya, tupel dikeluarkan dan posisi yang sesuai dalam tabel kiri diatur ke NULL. Jika PostFilter ada dalam RIGHT OUTER JOIN, tabel hash yang cocok yang dibuat berdasarkan tabel kiri harus diverifikasi menggunakan fitur PostFilter.

LeftSemi

LEFT SEMI JOIN mirip dengan LEFT OUTER JOIN. Tupel dalam tabel kiri dan kanan tidak dikeluarkan. Tupel dalam tabel kiri dan nilai NULL, TRUE, atau FALSE dikeluarkan berdasarkan tabel kebenaran berikut, atau hanya tupel dalam tabel kiri yang dikeluarkan, atau tidak ada nilai yang dikeluarkan. Jika PostFilter ada dalam LEFT SEMI JOIN, tabel hash yang cocok yang dibuat berdasarkan tabel kiri harus diverifikasi menggunakan fitur PostFilter.

  //+------------------------------+--------------+----------------+
  //|           mathched           | semi_probe_  | ! semi_probe_  |
  //+------------------------------+--------------+----------------+
  //| normal true                  | (left, TRUE) |   (left, ONLY) |
  //+------------------------------+--------------+----------------+
  //+------------------------------+--------------+----------------+
  //|        ! mathched            | semi_probe_  | ! semi_probe_  |
  //+------------------------------+--------------+----------------+
  //|NULL v.s. (empty set)         |              |                |
  //|e.g., NULL IN (empty set)     | (left, FALSE)|  NO_OUTPUT     |
  //+------------------------------+--------------+----------------+
  //|NULL v.s. (set)               |              |                |
  //|e.g., NULL IN (1, 2, 3)       | (left, NULL) |  NO_OUTPUT     |
  //+------------------------------+--------------+----------------+
  //|left_row v.s. (set with NULL) |              |                |
  //|e.g., 10 IN (1, NULL, 3)      | (left, NULL) |  NO_OUTPUT     |
  //+------------------------------+--------------+----------------+
  //|normal false                  |              |                |
  //|e.g., 10 IN (1, 2, 3)         | (left, FALSE)|  NO_OUTPUT     |
  //+------------------------------+--------------+----------------+

LeftAntiSemi

LEFT ANTI SEMI JOIN mirip dengan LEFT OUTER JOIN. Tupel dalam tabel kiri dan kanan tidak dikeluarkan. Hanya tupel dalam tabel kiri yang dikeluarkan berdasarkan tabel kebenaran berikut, atau tidak ada nilai yang dikeluarkan. Jika PostFilter ada dalam LEFT ANTI SEMI JOIN, tabel hash yang cocok yang dibuat berdasarkan tabel kiri harus diverifikasi menggunakan fitur PostFilter.

  //+------------------------------+----------------+
  //|        ! mathched            | ! semi_probe_  |
  //+------------------------------+----------------+
  //|NULL v.s. (empty set)         |                |
  //|e.g., NULL NOT IN (empty set) |   (left, ONLY) |
  //+------------------------------+----------------+
  //|NULL v.s. (set)               |                |
  //|e.g., NULL NOT IN (1, 2, 3)   |   (left, ONLY) |
  //+------------------------------+----------------+
  //|left_row v.s. (set with NULL) |                |
  //|e.g., 10 NOT IN (1, NULL, 3)  |   (left, ONLY) |
  //+------------------------------+----------------+
  //|normal false                  |                |
  //|e.g., 10 NOT IN (1, 2, 3)     |   (left, ONLY) |
  //+------------------------------+----------------+

RightSemi

RIGHT SEMI JOIN mirip dengan RIGHT OUTER JOIN. Tupel dalam tabel kiri dan kanan tidak dikeluarkan. Tupel dalam tabel kanan dan nilai NULL, TRUE, atau FALSE dikeluarkan berdasarkan tabel kebenaran berikut, atau hanya tupel dalam tabel kanan yang dikeluarkan, atau tidak ada nilai yang dikeluarkan. Jika PostFilter ada dalam RIGHT SEMI JOIN, tabel hash yang cocok yang dibuat berdasarkan tabel kiri harus diverifikasi menggunakan fitur PostFilter.

  //+------------------------------+--------------+----------------+
  //|           mathched           | semi_probe_  | ! semi_probe_  |
  //+------------------------------+--------------+----------------+
  //| normal true                  | (right, TRUE)|  (right, ONLY) |
  //+------------------------------+--------------+----------------+
  //+------------------------------+--------------+----------------+
  //|        ! mathched            | semi_probe_  | ! semi_probe_  |
  //+------------------------------+--------------+----------------+
  //|NULL v.s. (empty set)         |              |                |
  //|e.g., NULL IN (empty set)     |(right, FALSE)|  NO_OUTPUT     |
  //+------------------------------+--------------+----------------+
  //|NULL v.s. (set)               |              |                |
  //|e.g., NULL IN (1, 2, 3)       |(right, NULL) |  NO_OUTPUT     |
  //+------------------------------+--------------+----------------+
  //|left_row v.s. (set with NULL) |              |                |
  //|e.g., 10 IN (1, NULL, 3)      |(right, NULL) |  NO_OUTPUT     |
  //+------------------------------+--------------+----------------+
  //|normal false                  |              |                |
  //|e.g., 10 IN (1, 2, 3)         |(right, FALSE)|  NO_OUTPUT     |
  //+------------------------------+--------------+----------------+

RightAntiSemi

RIGHT SEMI JOIN mirip dengan RIGHT OUTER JOIN. Tupel dalam tabel kiri dan kanan tidak dikeluarkan. Tupel dalam tabel kanan dikeluarkan berdasarkan tabel kebenaran berikut, atau hanya tupel dalam tabel kanan yang dikeluarkan, atau tidak ada nilai yang dikeluarkan. Jika PostFilter ada dalam RIGHT ANTI SMEI JOIN, tabel hash yang cocok yang dibuat berdasarkan tabel kiri harus diverifikasi menggunakan fitur PostFilter.

  //+------------------------------+----------------+
  //|        ! mathched            | ! semi_probe_  |
  //+------------------------------+----------------+
  //|NULL v.s. (empty set)         |                |
  //|e.g., NULL NOT IN (empty set) |  (right, ONLY) |
  //+------------------------------+----------------+
  //|NULL v.s. (set)               |                |
  //|e.g., NULL NOT IN (1, 2, 3)   |  (right, ONLY) |
  //+------------------------------+----------------+
  //|left_row v.s. (set with NULL) |                |
  //|e.g., 10 NOT IN (1, NULL, 3)  |  (right, ONLY) |
  //+------------------------------+----------------+
  //|normal false                  |                |
  //|e.g., 10 NOT IN (1, 2, 3)     |  (right, ONLY) |
  //+------------------------------+----------------+

Implementasi Operator Hash Match

Operator Hash Match mendefinisikan proses yang mencakup pemrosesan memori dan disk, beberapa operasi JOIN, dan fitur PostFilter.

HashMap

Operasi tulis dan operasi query disediakan untuk mengimplementasikan operator Hash Match.

size_t PutValue(uint64_t hash_code, const char *key_buf, uint64_t key_len, const uint64_t tuple);
ValueIterator FindValue(uint64_t hash_code, const char *key_data, const uint64_t key_len, const bool need_mark = false);

Dua iterator disediakan untuk melintasi seluruh tabel hash:

  enum IteratorType { Normal = 0, NoneMark = 1, Mark = 2, END };

  class TableIterator {
   public:
    void Next();
    bool IsValid() const { return valid_; }
    ValueIterator GetIterator(IteratorType type);
	
   private:
	IteratorType type_ = IteratorType::END;
  };

  class ValueIterator {
    struct Listener {
      virtual void BlockEvent() {}
    };
    void SetListener(Listener *listener) { listener_ = listener; }
	
	void Next();
    bool IsValid() const { return valid_; }

   private:
    IteratorType type_ = IteratorType::Normal;
    Listener *listener_ = nullptr;
  };

Iterator TableIterator melintasi semua pasangan nilai-kunci dalam tabel hash, dan iterator ValueIterator melintasi semua blok data pasangan nilai-kunci. Kedua iterator mendukung tiga model iteratif berikut yang berlaku untuk operasi JOIN yang berbeda: Normal, NoneMark, dan Mark.

Iterator TableIterator melintasi semua tabel hash dan terutama diterapkan pada LEFT_OUTER, LEFT_ANTI_SEMI, dan LEFT_SEMI.

Info

HMInfo menyimpan data global yang dibagikan oleh semua pekerja, seperti nomor partisi memori dan objek partisi. Partisi menyimpan tabel hash gabungan partisi saat ini, set chunk tabel kiri dan kanan, dan file sementara tabel kiri dan kanan. Operator Hash Match menghasilkan file sementara untuk setiap partisi. Pekerja dapat melakukan operasi baca dan tulis atomik menggunakan fungsi pread, fungsi pwrite, dan variabel atomik offset.

Info Lokal

HMLocalInfo menyimpan data pribadi pekerja saat ini, seperti nomor partisi memori pekerja saat ini dan HMLocalPartitions kiri dan kanan. Setiap HMLocalPartition menyimpan tabel hash partisi saat ini pekerja, set chunk, dan objek chunk yang sedang ditulis.

Fetcher

Operator Hash Match mendukung beberapa metode pengambilan, termasuk mengambil data dari tabel kiri, mengambil data dari tabel kanan, membaca objek chunk dari set chunk Info atau LocalInfor memori, dan membaca serta membuat serial objek chunk dari file sementara. Metode-metode ini semuanya dapat digunakan untuk mengambil data dari chunk dalam fase pembuatan dan pencarian.

class HashMatchFetcher final {
  bool Fetch(Context &context, TupleChunk *&mat_chunk);
  // fetch from left or right child
  bool FetchMem(Context &context);
  // fetch from info chunks (include load from temp files)
  bool FetchDisk(Context &context, TupleChunk *&mat_chunk);

  size_t part_index_ = 0;
  TupleChunk chunk_;
};

Builder

Builder memproses partisi memori dan partisi disk secara terpusat dalam fase doBuild.

1. MemBuilder: Data dalam tabel kiri diambil dan disimpan dalam set chunk. Jika sebuah tupel milik partisi memori, tabel hash ditulis. Jika sebuah tupel milik partisi disk, data chunk dialihkan ke disk.

2. DiskBuilder: Set chunk dibaca dari tabel sementara dan digunakan untuk membangun tabel hash partisi ini.

class HashMatchBuilder {
  void Build();
  virtual void ChunkResult(const size_t offset, const bool is_null,
                           const size_t part_index, const uint64_t hash_val,
                           const char *key_data, const size_t key_len) = 0;
  virtual void ChunkDone() = 0;

  HashMatchFetcher fetcher_;
};

class HashMatchMemBuilder final : public HashMatchBuilder {
  void ChunkResult(const size_t offset, const bool is_null,
                   const size_t part_index, const uint64_t hash_val,
                   const char *key_data, const size_t key_len) override;
  void ChunkDone() override;
  
  TupleChunk origin_chunk_;
};

class HashMatchDiskBuilder final : public HashMatchBuilder {
  void ChunkResult(const size_t offset, const bool is_null,
                   const size_t part_index, const uint64_t hash_val,
                   const char *key_data, const size_t key_len) override;
  void ChunkDone() override;

  const size_t part_index_ = 0;
};

Prober

Operasi ProbeMen, ProbeLeft, dan ProbeDisk dalam fase pencarian semuanya dilakukan menggunakan fitur probe dari Prober.

class HashMatchProber final {
 public:
  void ProbeResult(TupleChunk *tpchunk, size_t &chunk_off, const size_t chunk_size);
  bool ProbeIter(Context &context, TupleChunk *tpchunk, size_t &chunk_off, const size_t chunk_size);
  bool Probe(Context &context, TupleChunk *tpchunk, size_t &chunk_off, const size_t chunk_size, const bool disk);

 private:
  const HashMatch &join_;
  HMInfo *info_ = nullptr;
  HMLocalInfo *local_info_ = nullptr;
  size_t part_index_ = 0;

  PostFilter filter_;

  LeftIterator lit_;
  RightIterator rit_;
  TraverseIterator tit_;  // used for probe left
};

HashMatchProber::PostFilter memproses probe dari operasi JOIN dengan fitur PostFilter. Set hasil yang diambil setelah fase pencarian harus diverifikasi oleh PostFilter.

  struct PostFilter final {
    bool Evaluate();
    bool Probe(TupleChunk *tpchunk, size_t &chunk_off, const size_t chunk_size);

    const HashMatchProber &prober_;
    const RTExprTreePtr &post_expr_;
    const HashMatchExpr &left_expr_;
    const HashMatchExpr &right_expr_;
    std::shared_ptr<Expressions::ExprEnv> post_env_ = nullptr;
  };

Prober mendukung iterator berikut: LeftIterator, RightIterator, dan TraverseIterator.

  struct Iterator {
    virtual void InitExpr() {}
    virtual void FiniExpr() {}
    virtual void Init(const size_t part_index);
    virtual void Fini();
    virtual bool Valid(Context &context) { return false; }
    virtual void Next() = 0;

    HashMatchProber &prober_;
    PostFilter &filter_;
  };

HashMatchProber::LeftIterator menggunakan HashMap::ValueIterator untuk melintasi semua nilai kunci tertentu dalam tabel hash dan menemukan tupel chunk tertentu berdasarkan nilai-nilai tersebut. Dengan cara ini, semua tupel kunci yang ditentukan disediakan untuk menangani berbagai jenis operasi JOIN dan fitur PostFilter.

  // for Probe
  struct LeftIterator final : public Iterator, public ValueIterator::Listener {
    void BlockEvent() override;

    bool Valid(Context &context) override;
    void Next() override;
    bool Find(const size_t part_index, const uint64_t hash_val,
              const char *key_data, const uint64_t key_len);

    ValueIterator it_;
  };

HashMatchProber::RightIterator terus menggunakan HashMatchFetcher untuk mengambil set chunk dari tabel kanan atau file sementara dan menyediakan fitur untuk melintasi semua chunk dan semua tupel. Semua operasi JOIN menggunakan RightIterator dalam tahap ProbeMem atau ProbeDisk untuk mengambil chunk, dan kemudian mencari tabel hash dalam partisi. Jika tabel hash ada, objek LeftIterator dibangun untuk melintasi semua tupel kunci. Selain itu, LEFT JOIN juga perlu diproses menggunakan ProbeLeft.

  // for Probe
  struct RightIterator : public Iterator {
    bool Valid(Context &context) override;
    void Next() override;

    HashMatchFetcher fetcher_;
    TupleChunk origin_chunk_;
    size_t chunk_size_ = 0;
  };

HashMatchProber::TraverseIterator terutama digunakan untuk LEFT JOIN, seperti Left OUTER JOIN, LEFT SEMI JOIN, dan LEFT ANTI SEMI JOIN. Ini menggunakan HashMap::TableIterator untuk melintasi seluruh tabel hash dan menyaring kunci yang cocok atau tidak cocok, kemudian menggunakan LeftIterator untuk melintasi semua tupel dari kunci tersebut. LEFT JOIN menggunakan ProbeMem atau ProbeDisk untuk mencari tabel hash dan melakukan pencocokan. Jika tabel hash cocok, pasangan nilai-kunci dalam tabel hash ditandai. Kemudian, ProbeLeft menggunakan TraverseIterator untuk menyaring pasangan nilai-kunci yang cocok atau tidak cocok.

  // for ProbeLeft
  struct TraverseIterator final : public Iterator {
    bool Valid(Context &context) override;
    void Next() override;

    TableIterator tit_;
    LeftIterator lit_;
    IteratorType it_type_ = IteratorType::END;
  };

Uji

Sebuah uji dilakukan untuk membandingkan kinerja operator Hash Join dan operator Hash Match. Dalam uji ini, kedua operator digunakan untuk menjalankan Q14 dari TPC Benchmark-H (TPC-H). Data yang di-query berukuran 1 TB. Kedua operator menggunakan algoritma serupa. Perbedaannya adalah apakah hasil perantara dimaterialisasi.

select
	100.00 * sum(case
				when p_type like 'PROMO%'
				then l_extendedprice * (1 - l_discount)
				else 0
				end) / sum(l_extendedprice * (1 - l_discount)) as promo_revenue
from
	lineitem,
	part
where
	l_partkey = p_partkey
	and l_shipdate >= date '1995-09-01'
	and l_shipdate < date '1995-09-01' + interval '1' month;

• Kueri dilakukan dengan cache LRU dan memori eksekutor sebesar 100 GB.

  Kueri(TPCH1T)	HashJoin	HashMatch
  Q14	23,96 detik	12,56 detik

• Kueri dilakukan dengan cache Least Recently Used (LRU) dan memori eksekutor sebesar 32 GB.

  Kueri(TPCH1T)	HashJoin	HashMatch
  Q14	Lebih dari 10 menit	35,73 detik