TiDB開発者ガイド: Planner

この記事は、TiDB Development Guide - 3.3 Planner の抄訳です。

パッケージ構造

Plannerの入力はSQL解析後のAST(Abstract Syntax Tree)であり、出力はプラン・ツリーです。
TiDBには2つのプランナーがあります。1つはデフォルトで使用されているSystem Rモデルのプランナー、もう1つはまだ開発中のCascadesモデルのプランナーです。この記事ではSystem Rプランナーについて焦点を当てています。

どちらのモジュールもエントリーポイントはOptimize()メソッドです。このメソッドは最初にSQL Plan Managementモジュールの介入の必要があるかをチェックし、もしあれば最適化を行う前にASTを変更します。

パッケージ	説明
tidb/pkg/planner/cascades	開発中の次世代Cascadesモデルプランナー(デフォルトで無効)
tidb/pkg/planner/core	現在使用中のSystem Rモデルプランナーの中核ロジック。Cascadesプランナーもこのパッケージのユーティリティ関数を呼び出します。
tidb/pkg/planner/implementation	Cascadesプランナーの演算子の物理的実装
tidb/pkg/planner/memo	Cascadesプランナーの探索プロシージャの中間結果
tidb/pkg/planner/property	演算子の出力に関するプロパティ(スキーマ、統計、順序付けプロパティ、パーティションプロパティなど)
tidb/pkg/planner/util	2つのプランナーで共有される一般的なユーティリティ関数/構造体

クエリ最適化プロシージャ

クエリの最適化は、下記の4ステップに従って行われます。

1. プランの構築
2. 論理最適化
3. 物理最適化
4. 事後最適化

プランの構築

プラン構築の開始

プラン作成のエントリーポイントはPlanBuilder.Build()です。これはASTを下から上に向かってたどっていき、決められたルールに基づいて実行計画へと変換していきます。
具体的には、クエリの部分節を確認し、それぞれに対応した演算子を組み立てていきます。この演算子はDAGとして連結されますが、これが論理プラン・ツリーと呼ばれるものです。

節の処理・式の変換

このフェーズの重要なステップは、節の式変換です。例えば、where a = 1に対してSelection演算子を作成し、同様にeq(a, 1)と変換されてSelection 演算子中に保存されます。
式の変換ロジックはexpressionRewriter構造体とそのメソッドにカプセル化されています。
expressionRewriterはASTを再帰的に走査し、変換を行います。中間結果は結果スタックに格納されます。

サブクエリの最適化

expressionRewriterは単純な式変換だけでなく、式内のサブクエリも最適化します。
非相関サブクエリのほとんどは直接実行され、結果を定数として置き換えられます。
相関サブクエリや一部の非相関サブクエリは、サブツリーを構築してメインのプラン・ツリーにLogicalJoinまたはLogicalApply演算子で接続されます。

LogicalApplyはNL(Nested Loop)でのみ実行できる特殊な演算子です。プラン・ツリー中のLogicalApplyにはより効率的なjoinアルゴリズムで処理されるLogicalJoinに変換できるものも含まれており、プランナーはこの変換を後の論理最適化フェーズで行います。

最適化フラグを設定する

プラン構築中、各演算子に対して最適化フラグが設定されます。例えば、Selection演算子に対しては、flagPredicatePushDownが設定されます。これらのフラグは後の論理的最適化段階で使用されます。

論理最適化

論理最適化のエントリーポイントは、logicalOptimize()です。この関数は、リレーショナル代数に従って、初期プラン・ツリーに対して論理的に等価な変換を実施します。結果のツリーは、理論上性能面に関してより良いものとなります。

最適化ルールの適用

具体的には、あらかじめ定義された最適化ルールのリストoptRuleListに従って、ルールを順に適用していきます。各ルールが適用可能かどうかは、プラン構築時に設定された最適化フラグを参照して判断されます。
フラグが設定されている場合、プラン・ツリーを上から順に移動し、そのルールの前提条件を満たすサブツリーに対して変換を適用します。

最適化ルールの例

• 列プルーニング: プラン・ツリー中の各演算子に対し、上位の演算子が必要とする列を収集し、不要な列を出力から除外します。
• 非相関化: 相関した列を参照する演算子を引き上げ、列の依存関係を解消することで、LogicalApplyをLogicalJoinに変換しようとします。

物理最適化

このフェーズはコストベース最適化としても知られています。このフェーズのエントリーポイントは、 physicalOptimize()です。物理最適化では、個々の論理演算子の実装について、コストに基づいた列挙が行われ、その中から最小のコストとなるような組み合わせを見つけ出し、それを最終的な物理実行計画とします。

演算子の実装の列挙

具体的には、各論理演算子は、exhaustPhysicalPlans()インターフェイス関数を実装しています。
この関数は、その論理演算子の全ての可能な物理的実装(アルゴリズム)を列挙します。例えば、論理的集約演算子(LogicalAggregation)には、ストリーム集約(PhysicalStreamAggregation)とハッシュ集約(PhysicalHashAggregation)の2つの実装があります。

子演算子への要求プロパティの伝搬

物理実装では、その子の出力に対して特定のプロパティ(PhysicalProperty)を要求する場合があります。例えば、ストリーム集約はGROUP BY列で並んだ順序付き出力を子に要求します。
これらの要求はPhysicalPropertyに記録されており、子の列挙プロシージャに渡されます。

コストの計算と最適プランの選択

プランナーがプラン・ツリーまたはプラン・ツリーの部分木の実装を把握すると、そのコストを計算できます。
コストは、CPU、メモリ、ネットワーク、I/Oなどのリソース消費の合計として計算されます。
各リソースの消費量は、単位係数(例えば、scanFactorはTiKVもしくはTiFlashの1バイトを読むコスト)と、その演算子で処理される予測行数/バイト数から算出されます。

単位係数は、異なるハードウェア設定に対応できるように、tidb_opt_xxx_factorのようなシステム変数で変更できるようになっています。

論理プラン・ツリーの全ての実装に対してコストが計算され、最も低コストの実装が選択されます。

ストレージエンジンへの演算子プッシュダウン

TiDBは選択(Selection)などの一部の演算子を、TiKVのコプロセッサへプッシュダウンしてクエリ実行を高速化できます。
このプッシュダウンの決定も、物理的最適化の探索フレームワークに組み込まれています。具体的には、PhysicalPropertyのTaskTypeフィールドを使用しています。
例えば、Limit演算子をTiKVにプッシュダウンする場合、PhysicalLimit実装を列挙しますが、その際に、CopXXXTaskTypeをTaskTypeとするPhysicalPropertyを持たせ、子にこれを要求します。
PhysicalLimitの子がTiKVの実装を生成した後、この二つの部分実行計画をattach2Task()インターフェースで連結します。これにより演算子のストレージエンジンへのプッシュダウンが行われます。

事後最適化

このフェーズのエントリーポイントは、postOptimize()です。
このフェーズでは大きな変更は行われず、クエリ最適化がほぼ完了した後の整理作業が行われます。
ここで行われる作業には、再度のプロジェクション除去(初回は論理最適化で行われた）、executorパッケージのコードを単純化するためのプロジェクション挿入などがあります。