TiDBのハッシュジョインを改善： チューニング不要で最大5倍高速化

※このブログは2025年6月20日に公開された英語ブログ ｢Improving TiDB Hash Joins: Up to 5× Faster with No Tuning Required｣ の拙訳です。

ハッシュジョインは、SQL ワークロードにおいて一般的なパフォーマンスボトルネックであり、TiDB も例外ではありませんでした。TiDB 8.5 では、全体的なパフォーマンスを向上させる、全く新しいハッシュジョイン実行エンジンを導入しました。この新エンジンは、マルチスレッドによるビルド処理、ベクトル化されたプローブ処理、そしてより効率的なディスクへの書き出し戦略により、最新のハードウェアをフルにに活用します。
社内のベンチマークによると、一般的なジョイン処理の処理性能が2倍に向上し、レイテンシが低減され、メモリ制約の厳しい状況下でも、処理性能のばらつきが減り、安定して動作するようになります。

本ブログは2回に渡るブログシリーズの最初の第1部です。今回は、概要レベルでのアップデートと、ユーザーがこの性能向上の恩恵を受けるために知っておくべきポイントに焦点を当てます。

ジョインが依然として重要な理由

ジョインは、分析処理とトランザクション処理、両方の中核にある存在です。ジョインが速度低下を起こすと、単一のクエリだけでなく、アプリケーション全体がボトルネックになる可能性があります

ハッシュジョインはパフォーマンス向上のための定番手法ですが、偏ったデータや限られたメモリサイズなどの現実的な条件下では、信頼性が低下し、デバッグが困難になる場合があります。
TiDBの従来のハッシュジョイン実行エンジンにはいくつかの制限がありました。具体的には、ハッシュテーブルの構築が単一スレッドで行われていたこと、Goの汎用的なマップ構造に依存していたこと、メモリが不足した際のスピル処理 (ディスクへの書き出し) が限定的であったこと、などです。

これらの問題により、レイテンシが高くなり、パフォーマンスが安定しないという課題が生じていました。もしTiDBでジョイン処理が停止した経験があるなら、その原因はこれらの問題である可能性が高いです。

背景

TiDBでは、多様なSQLクエリを実行する際、特に大規模なデータセット間で等価条件が関与する場合に、ハッシュジョインを使用しています。典型的なハッシュジョインでは、実行エンジンが一方のテーブルを「ビルド側」として選び、その行からメモリ上にハッシュテーブルを構築します。そして、もう一方のテーブルを使って一致する行を探索 (プローブ) します。.

たとえば、以下のようなクエリは、すべてTiDBでハッシュジョインを選択します：

-- Classic inner join
SELECT * FROM lineitem l JOIN orders o ON l.orderkey = o.orderkey;

-- Semi join with filter
SELECT * FROM lineitem l WHERE EXISTS (
  SELECT 1 FROM orders o WHERE l.orderkey = o.orderkey AND o.orderstatus = 'F'
);

-- Join with additional filter
SELECT * FROM lineitem l JOIN orders o
  ON l.orderkey = o.orderkey AND l.partkey > o.custkey;

以前のバージョンのTiDBでは、ビルド側はGoの組み込みマップ構造を使用して単一のスレッドで処理されていました。この構造は大規模なジョイン処理には最適化されておらず、ポインターの間接参照、CPUキャッシュの局所性の低下、実行時マップの再調整といった要因が、データ量の増加とともにパフォーマンスのボトルネックとなりました。

プローブフェーズにも同様の問題がありました。ジョインは1行ずつ処理されており、ベクトル化による高速化ができない構造でした。セミジョインのようなジョインの種類では、最初にマッチする行を見つけても早期終了せず、重複チェックのために処理を継続していました。さらに、結合キーが文字列だった場合、候補ごとに照合順序の ロジックを毎回再評価しており、これが追加のコスト増につながっていました。

メモリ使用量が設定された制限を超えた場合、TiDBは中間データをディスクに書き出そうと試みても、書き出されるのは行データのみで、ハッシュテーブルはメモリ内に残ったままでした。このため、実際に解放されるメモリに制限があり、メモリに制約のある環境ではクエリが失敗したり、非効率なディスクアクセスによって著しくパフォーマンスが低下するケースが発生していました。

これらの制限を背景に、TiDB 8.5ではハッシュジョイン実行エンジンの全面的な再設計が行われ、再設計の焦点は、「並列性の向上」「メモリ効率の最適化」「パフォーマンスの予測可能性の確保」に置かれています。

従来のボトルネック

TiDBにおける従来のハッシュジョイン実行エンジンには、アーキテクチャ上のいくつかの制約があり、特に前のセクションで紹介したような大規模または複雑なクエリにおいてパフォーマンス上の課題を引き起こしていました。これらの問題は、実行の3つの主要なフェーズ: ビルド、プローブ、スピルのすべて影響を及ぼしていました。

ビルドフェーズ

ビルドフェーズは、単一スレッド設計によって制約されていました。たとえTiDBが16コアや32コアといったシステム上で動作していたとしても、ハッシュテーブルの構築には1つのコアしか使用されませんでした。この設計はスループットに明確な上限を設けることになり、特に lineitem–orders のようなジョイン処理においては深刻な制約となっていました。

SELECT * FROM lineitem l JOIN orders o ON l.orderkey = o.orderkey;

追加のボトルネックには以下のものが含まれていました：

• 単一スレッドでの実行：ビルド側 (例：orders) のハッシュテーブルは、1つのワーカーによって構築されていました。
• Goマップの非効率性：Goの組み込みマップを使用していたため、ポインタの追跡やキャッシュミスが発生し、CPU依存の処理が遅くなっていました。
• 動的なリサイズ：マップのサイズが拡大するにつれて、クエリ実行中に予測不能なタイミングでリサイズが発生し、突発的な遅延を引き起こしていました。

プローブフェーズ

ビルドが完了すると、プローブ側は行を1件ずつ処理していました。この処理は特に、ジョインのフィルターや非等価条件を含むクエリにおいてコストが高くなっていました。たとえば、以下のようなクエリです：

SELECT * FROM lineitem l JOIN orders o
  ON l.orderkey = o.orderkey AND l.partkey > o.custkey;

このフェーズにおける主な非効率性は以下の通りです：

• ベクトル化なし：入力行ごとに、キーの照合や述語の評価のために、毎回な関数の呼び出しが発生していました。
• 最適化されていない結合セマンティクス：セミジョインの場合、たとえ1件の一致で十分であっても、TiDBは一致するすべてのビルド行をスキャンしていました。
• 比較の繰り返し：照合順序を考慮する文字列キーでは、候補ごとの一致判定で毎回再評価が行われ、CPUへの大きな負荷となっていました。

スピルフェーズ 

クエリがメモリのクォータを超えた場合、TiDBはデータをディスクにスピル (書き出し) しようと試みていました。しかし、この仕組みは不完全であり、さらなる問題を引き起こしていました：

• 不完全なスピル処理：ディスクに書き出されるのは行データのみで、ハッシュテーブル自体はメモリに常駐したままでした。そのため、回収できるメモリ量には限界がありました。
• 非効率なI/O：ディスクに書き出されたデータに対するプローブ処理ではランダムディスクアクセスが発生し、パフォーマンスが予測不能かつしばしば劣化する原因となっていました。

これらのボトルネックにより、ジョインを多用するワークロードはスケールしづらく、特にメモリが制限されていたり、入力データが大きい、または偏りがある場合に深刻な影響を及ぼしていました。

デザイン原則：新たなスタートのための設計

従来の実行エンジンの制限を解消するために、TiDB 8.5では、ハッシュジョインの実行エンジンを根本から再設計しました。新しい設計は、パフォーマンス、予測可能性、スケーラビリティを向上させる5つの原則をを軸としています。

1. すべてのCPUコアを活用する
   1. ビルド側のデータは物理的にパーティション分割されます。
   2. 各パーティションは別々のスレッドで並列処理されます。
   3. これにより単一スレッドのボトルネックが解消され、ビルドフェーズが大幅に短縮されます。
2. ビルド側データは行フォーマットで格納
   1. ビルド入力は列ではなく行として格納されます。
   2. これにより結果構築時のキャッシュの局所性が向上します。
   3. また、特に幅の広い行のジョイン結果の実体化が簡素化されます。
3. 固定サイズのチェーンベースハッシュテーブルを使用
   1. ハッシュテーブル用のメモリは事前に確保されます。
   2. ハッシュの衝突はプロービングではなくチェイニングによって処理されます。
   3. これにより動的なリサイズを避け、安定したパフォーマンスを実現します。
4. ベクトル化されたチャンク単位のプローブ処理を実行
   1. プローブ処理は行単位ではなくバッチ単位で行われます。
   2. ジョインのキーやフィルターはベクトル化されたロジックでまとめて評価されます。
   3. これによりスループットが向上し、1行あたりのオーバーヘッドが減少します。
5. ハッシュバケットを含むスピルを可能にする
   1. メモリが不足した場合は、行データだけでなくハッシュテーブルのバケットごとパーティション単位でディスクにスピル (ディスクに書き出し) されます。
   2. スピルおよびリストア (ディスクからの読み戻し) はシーケンシャルかつパーティションを意識した処理となっています。
   3. これによりメモリ制約下でもスピル処理がスケールし、許容可能なパフォーマンスを維持できます。

これらの変更により、新しいエンジンはコア数の増加に伴ってスケールアップし、メモリに制約がある時にはスケールダウンしつつも、予測可能で高いパフォーマンスを保つことが可能となりました。

新しいエンジンの動作原理

新しいハッシュジョインの実行エンジンでは、各実行フェーズにおける課題を解決するために、並列処理、ベクトル化、そしてよりスマートなスピル処理が導入されています。以下の表は、どのような点が変更され、それがどのようにパフォーマンス向上につながっているのかをまとめたものです。

ステージ	変更点	高速化の理由
Pre-build (事前ビルド)	入力チャンクがハッシュパーティションされ、同時に列形式から行形式へ変換されるようになった	二度目のスキャンが不要になり、結果の構築時の行の局所性が向上
Build (ビルド)	各パーティションが、スレッドローカルな固定サイズのハッシュテーブルを用いて並列に構築される	CPUコアをフル活用可能。TPC-H 50のテストでは、ハッシュテーブル構築時間が73秒から7秒に短縮
Probe (プローブ)	プローブ処理はバッチ単位で実行され、タグ付きポインタで大多数の誤ったマッチを高速に除外。フィルターはベクトル化された式で評価される	不要な比較を減らし、キャッシュ効率を向上。TPC-H 50ではプローブ時間が208秒から77秒に短縮
Spill (スピル)	メモリ制限に達した場合、パーティション全体 (ハッシュバケットを含む) をディスクにシーケンシャルに書き出し、同じ形式で読み戻す	ランダムI/Oを最小化。メモリクォータが1GBでも安定したパフォーマンスを維持可能

この新しい実行モデルは、インメモリでのジョイン処理を高速化するだけでなく、メモリ不足時の挙動もはるかに予測可能で効率的なものにしています。

実運用での効果

新しいハッシュジョインの実行エンジンの評価のために、代表的なクエリとデータセットを用いて従来の実装と比較テストを行いました。
その結果、さまざまなジョインの種類とスケールにおいて、大幅な性能向上が確認されました。

ベンチマーク：単純な内部結合

単純な等価条件で、2つの大規模なテーブルをジョインします。

SELECT * FROM lineitem l JOIN orders o ON l.orderkey = o.orderkey;

• 従来版：65秒
• 新エンジン：29秒
• 高速化：2.2倍

ベンチマーク：非等価条件付きの結合

ジョイン後のフィルターを追加し、CPUおよびメモリへの負荷が増加させます。

SELECT * FROM lineitem l JOIN orders o
  ON l.orderkey = o.orderkey AND l.partkey > o.custkey;

• 従来版：143 秒
• 新エンジン：29 秒
• 速度向上：4.9倍

ベンチマーク：TPC-H 50GB 

スケールファクタを50に設定時のTPC-Hベンチマークスイートのエンドツーエンドの結果：

• ハッシュビルド時間：
  • 従来版：73秒
  • 新エンジン：7秒
• ハッシュプローブ時間：
  • 従来版：208秒
  • 新エンジン：77秒
• クエリ全体の実行時間：
  • 従来版：647秒
  • 新エンジン：561秒

この規模になると、ジョインのパフォーマンスはもはや主なボトルネックではありません。残りの処理時間の大半は、スキャンや集約オペレーターが占めています。リソースが制限されている状況でも、新しい実行エンジンは安定した動作を示します。

わずか1GBのメモリの割り当てでも、新エンジンはクエリを正常に完了させる一方で、従来の方式は失敗するか、6倍遅くなることがあります。

お客さまに与える影響

TiDBのハッシュジョイン実行エンジンの改良は、ワークロードの規模が大きくなったりメモリが制約されても、一貫したパフォーマンスを提供するよう設計されています。
複雑な分析クエリを実行する場合でも、高スループットなトランザクションがジョイン処理を行う場合でも、その効果は即座に実感でき、測定可能です。

期待できるポイントは以下の通りです：

• 負荷が高くても安定したレイテンシー：新エンジンは厳しいメモリクォータ下でも安定した性能を維持します。スピル処理は効率的に行われ、クエリの予測可能性が保たれます。
• リソースの有効活用：固定サイズのメモリ割り当てと並列実行により、CPUやメモリの無駄を削減しました。過大なインスタンスを必要とせずに高速に結合処理を完了します。
• ワークロードを問わないスケーラビリティ：数百万行の結合から数十億行のジョインまで、新エンジンは利用可能なハードウェアを活用し、効率的に動作し続けます。
• 将来を見据えたアーキテクチャ：将来を見据えたアーキテクチャ– ベクトル化とパーティション化された設計は、SIMDアクセラレーション、GPU統合、高度なジョインの最適化など、将来の改善の可能性を拓きます。

このアップデートはTiDB 8.5における最も影響力の大きいパフォーマンス改善の一つであり、今後のリリースに向けたSQL実行層のさらなる堅固な基盤を築きます。

次のステップ

新しいハッシュジョイン実行エンジンはTiDB 8.5から利用可能になりました。このバージョンではデフォルトで無効化されていますが、今後のバージョンではデフォルトの動作となる予定です。

8.5で試すには、セッションレベルで有効化できます。

SET SESSION tidb_enable_new_hash_join = ON;

有効化されると、オプティマイザは対象のクエリに対して新しい実行エンジンを自動的に選択します。スキーマの変更やアプリケーションの修正は不要です。

現在クエリのチューニングを行っている方や、大規模なジョイン処理でパフォーマンスに悩まされている方は、ぜひご自身の環境でこの機能を試してみてください。 フィードバックや結果の共有は、GitHub DiscussionsやTiDB Community Slackでお待ちしています。

このアップグレードは、SQL実行層のパフォーマンス向上に対する私たちの幅広い投資の一環です。皆さまのワークロードでの動作報告を楽しみにしています。

このブログシリーズの第2回目では、オープンソースコミュニティ向けにより詳しいエンジニアリングの内容を掘り下げます。次回の投稿をぜひご期待ください。