PolarDBデータベース並列クエリ技術の詳細な分析

[[399309]]

1. 背景

データの規模が拡大し続けるにつれて、ユーザー SQL の実行時間はますます長くなり、データベースの最適化機能に対する要件が高まるだけでなく、データベースの実行モードにも新たな課題が生じます。クラウド上のデータベースの活発な開発に伴い、クラウド上の弾力的な拡張のメリットを享受するために、従来のユーザーがますますクラウドに移行しています。しかし、事業の急速な拡大に伴い、多くのリソースを動的に追加しても、SQL の実行時間はどんどん遅くなり、リソースの投資に見合った期待した効果が得られていないことがわかりました。明らかに、多くの新しいリソースが追加されましたが、これらのリソースは十分に活用されていません。 Oracle や SQL Server などの従来の商用データベースの多くは、システム リソースを最大限に活用し、SQL 実行を高速化するために並列クエリ エンジンをサポートしています。

この記事では、主にコストベースの並列最適化と並列実行に基づくクラウド データベースの並列クエリ エンジンの主要な問題とコア テクノロジーを紹介します。

2. クエリを並列化する方法

OLAP のようなクエリの場合、通常は大量のデータに対するクエリであることは明らかです。大量のデータとは、データがデータベースのメモリ容量よりもはるかに大きいことを意味します。データのほとんどはデータベース バッファーにキャッシュされない可能性があり、クエリの実行時にバッファーに動的にロードする必要があります。これにより、多数の IO 操作が発生し、IO 操作が最も時間がかかります。したがって、最初に考慮すべきことは、IO 操作を高速化する方法です。

ハードウェアの制限により、各 IO の持続時間は基本的に固定されています。シーケンシャル IO とランダム IO には違いがありますが、SSD の普及に伴い、両者の差は徐々に縮まってきています。では、IO を高速化する他の方法はあるのでしょうか?明らかに、並列 IO はシンプルで簡単な方法です。複数のスレッドが同時に IO を開始できる場合、各スレッドはデータの一部のみを読み取るため、データはデータベース バッファーにすばやく読み込まれます。

上の図は、データを並列に読み取る方法を示しています。各ワーカーはスレッドを表します。データがすでにパーティション化されている場合、各スレッドは 1 つのパーティションを読み取ることができます。あるいは、すべてのデータをデータ ページ サイズなどの固定サイズに分割し、各スレッドがラウンドロビン モードでシャードを読み取ることもできます。

ここで注意すべき点は、既存のパーティションを異なるワーカーに割り当てると、各ワーカーがデータを不均一に処理する可能性があることです。ただし、ポーリングがラウンドロビン モードで実行され、シャードが比較的小さく設定されている場合、各ワーカーがデータを均等に処理するようにすることは比較的簡単です。

データがすぐに処理されるのではなく、単にバッファに読み込まれると、バッファがいっぱいになるためにデータがスワップアウトされ、IO を高速化する目的が達成されません。したがって、データを並列に読み取ると同時に、データも並列に処理する必要があり、これが並列クエリの高速化の基礎となります。

従来のオプティマイザーでは、シリアル実行プランしか生成できません。並列データ読み取りと並列データ処理を実現するには、まず既存のオプティマイザーを変換して、必要な並列プランを生成できるようにする必要があります。たとえば、どのテーブルを並列に読み取ることができるか、また並列読み取りによって十分な利点が得られるテーブルはどれかを選択します。または、どの操作を並行して実行でき、どの操作が十分な利益をもたらすかを判断します。

これは必ずしも並行変革が利益をもたらすことを意味するものではありません。たとえば、データ量が非常に少ない (おそらく数行のみ) テーブルの場合、そのデータも並列で読み取られると、並列実行に必要な複数のスレッドの構築とスレッド間のデータ同期にかかるコストが、得られるメリットよりもはるかに大きくなる可能性があります。一般に、並列実行にはより多くのリソースと時間が必要となり、コストに見合いません。したがって、クエリ プランの並列化はコストベースで行う必要があります。そうしないと、より深刻なパフォーマンス低下の問題が発生する可能性があります。

3. 並列スキャンのテーブルを選択する方法

並列スキャンの対象となるテーブルを選択することは、並列プランを生成するための重要な基礎となります。並列スキャンのコストを計算して比較し、並列スキャンできるテーブルを候補として選択することが、並列実行プランの反復の最初のステップです。新しい並列コストに基づいて、特に JOIN に関係するテーブルの数が多く、より多くの追加の反復スペースが必要な場合、より適切な JOIN 順序を選択できる可能性があります。最適化プロセスに時間がかかりすぎないようにするには、当初計画した JOIN 順序を維持するのがよいでしょう。さらに、JOIN に関係するテーブルごとに、フル テーブル スキャン、Ref インデックス スキャン、範囲インデックス スキャンなどのテーブル アクセス方法が異なるため、最終的な並列スキャン コストに影響します。

通常、並列スキャンの利点が最大化されるように、最大​​のテーブルを並列テーブルとして選択します。もちろん、複数のテーブルを同時に並列スキャンすることもできます。より複雑な状況については後ほど説明します。

年間消費量上位 10 人のユーザーのクエリを例に挙げてみましょう。

SELECT c.c_name, sum(o.o_totalprice) as s FROM customer c, orders o WHERE c.c_custkey = o.o_custkey AND o_orderdate >= '1996-01-01' AND o_orderdate <= '1996-12-31' GROUP BY c.c_name ORDER BY s DESC LIMIT 10;

注文テーブルは大量のデータを持つ注文テーブルであり、このタイプのテーブルはファクト テーブルとも呼ばれます。顧客テーブルは比較的データが少ない顧客テーブルであり、このタイプのテーブルはディメンション テーブルとも呼ばれます。この SQL の並列実行プランは次のようになります。

このプランから、orders テーブルは 32 個のワーカー スレッドによって並列にスキャンされることがわかります。各ワーカーは、orders テーブルのデータ シャードの一部のみをスキャンし、o_custkey に基づいて customer テーブルとのインデックス検索 JOIN を実行します。 JOIN の結果はコレクター コンポーネントに送信され、その後、後続の GROUP BY、ORDER BY、および LIMIT 操作が引き続き実行されます。

4. 複数テーブルの並列結合を選択する

テーブルを並列にスキャンした後、なぜ 1 つのテーブルしか選択できないのか疑問に思うかもしれません。 SQL に 2 つ以上の FACT テーブルがある場合、すべての FACT テーブルを並列にスキャンすることは可能ですか?答えはもちろんイエスです。次の SQL を例に挙げます。

SELECT o.o_custkey, sum(l.l_extendedprice) as s FROM orders o, lineitem l WHERE o.o_custkey = l.l_orderkey GROUP BY o.o_custkey ORDER BY s LIMIT 10;

orders テーブルと lineitem テーブルはどちらも大量のデータを持つファクト テーブルです。この SQL の並列実行プランを次の図に示します。

このプランから、orders テーブルと lineitem テーブルの両方が並列にスキャンされ、両方とも 32 個のワーカー スレッドによって実行されることがわかります。では、複数のテーブルの並列処理はどのように実現されるのでしょうか? 2つのテーブルを例に挙げてみましょう。 2 つのテーブルを結合する場合、一般的な結合方法には、ネスト ループ JOIN と HASH JOIN があります。さまざまな結合方法の場合、結果の正確性を確保するために適切なテーブルスキャン方法を選択する必要があります。

HASH JOIN を例にとると、シリアルで実行される HASH JOIN の場合、最初にテーブルを選択して Build テーブルという HASH テーブルを作成し、次に別の Probe テーブルを読み取って HASH を計算し、Build テーブルで HASH マッチングを実行します。一致が成功した場合は結果を出力し、そうでない場合は読み取りを続行します。並列 HASH JOIN に変更すると、並列オプティマイザはシリアル実行された HASH JOIN を並列化して並列 HASH JOIN にします。並列化には 2 つのソリューションがあります。

解決策 1 は、両方のテーブルを HASH キーでパーティション分割することです。同じ HASH 値を持つデータは同じパーティションに配置され、同じスレッドで HASH JOIN が実行されます。解決策 2 は、HASH JOIN を実行するすべてのスレッドで共有される共有 Build テーブルを作成することです。次に、各スレッドは、自身のスレッドに属する別のテーブルのシャードを並列に読み取り、HASH JOIN を実行します。最終的なプランの選択はコスト見積もりを通じて決定されます。

図2 並列HASH JOINの概略図

ソリューション 1 では、テーブル内のすべてのデータを読み取り、選択した HASH キーに従ってデータを分割し、データを異なる処理スレッドに送信する必要があります。これには、パーティション分割ルールに従ってデータを異なる処理スレッドに送信する追加の Repartition 演算子が必要です。ソリューション 2 では、共有 HASH ビルド テーブルを並列に作成する必要があります。ビルド テーブルが正常に作成された後、各スレッドはプローブ テーブルのシャードを読み取り、HASH JOIN を個別に実行します。ここでのシャードは、HASH キーに従ってシャード化する必要はありません。各スレッドは、交差しないシャードを個別に読み取ることができます。

5. 解析統計のための複雑な演算子の並列処理

統計分析では、特に JOIN 結果が大量にある場合には、GROUP BY 操作は避けられない操作です。これは SQL 全体の中で最も時間のかかるプロセスです。したがって、GROUP BY の並列処理も、並列クエリ エンジンが最初に解決しなければならない問題です。

年間消費量上位 10 社の顧客の SQL を例にとると、GROUP BY の並列化後の並列実行プランは次の図のようになります。

以前の実行プランと比較すると、新しい実行プランにはコレクター コンポーネントが 1 つ追加され、合計 2 つのコレクター コンポーネントになります。まず、2 行目のコレクター コンポーネントを見てみましょう。追加情報に「Using temporary; Using filesort」が 2 つありますが、これはワーカーから受信したデータに対して GROUP BY を実行し、次に ORDER でソートすることを意味します。最初のコレクター コンポーネントのみがユーザーのセッションに存在するため、このコレクターもワーカー内で並列に実行されます。つまり、Group by、Order by、および Limit が並列に実行されます。次に、最初の行のコレクター コンポーネントを確認します。追加情報には「マージ ソート」が 1 つだけあります。これは、セッション スレッドがワーカーから受信したデータに対してマージ ソートを実行し、その結果をユーザーに返すことを意味します。ここで、セッション スレッドがマージ ソートを実行するだけで GROUP BY 操作を完了できるのはなぜかと疑問に思う人がいるかもしれません。限界はどこですか?

まず、2番目の質問に答えさせてください。説明プランに問題が表示されるため、LIMIT 操作は通常モードでは表示されませんが、ツリー モードでは表示されます。以下のように表示されます。

ツリー型プランツリーからは、 LIMIT 操作が 2 つあることが明確にわかります。 1 つはプランの最上部、つまりセッションにあり、制限が完了した後にデータがユーザーに返されます。もう 1 つはプラン ツリーの中央にあり、実際にはワーカー スレッドの実行プラン上にあります。各ワーカー スレッドでは、ソートが完了した後に制限も実行されます。これにより、ワーカーからセッション スレッドに返されるデータの量が大幅に削減され、全体的なパフォーマンスが向上します。

最初の質問に答えましょう。結果の正確性を確保するために、GROUP BY をワーカー スレッドで 1 回だけ実行する必要があるのはなぜでしょうか。一般的に、各ワーカーにはすべてのデータのシャードが 1 つだけあります。 1 つのデータ シャードのみで GROUP BY を実行すると、同じ GROUP グループ化のデータがこのワーカーのデータ シャード上だけでなく、他のワーカーのデータ シャード内に存在し、他のワーカーによって保持されている可能性があるため、間違った GROUP BY 結果が得られる大きなリスクがあります。ただし、同じ GROUP グループ内のデータが同じデータ シャードに配置され、このデータ シャードが 1 つの WORKER スレッドによってのみ保持されることを保証できる場合は、GROUP BY 結果の正確性は保証されます。ツリー型の実行プランから、並列 JOIN 後、JOIN 結果が GROUP グループの KEY 値: c.c_name に従って再分割され、同じグループ内のデータが同じ WORKER に分散されることがわかります。これにより、各 WORKER が所有するデータ シャードが互いに重複しないようにし、GROUP BY 結果の正確性を確保します。

各 WORKER の GROUP BY 操作がすでに最終結果となっているため、ORDER BY と LIMIT も WORKER にプッシュダウンして実行することができ、並列実行の効率がさらに向上します。

6. TPCHの並列クエリエンジンの線形加速

添付の図は、TPC-H における並列クエリ エンジンの高速化効果を示しています。 TPC-H の SQL の 100% を高速化でき、SQL の 70% は 8 倍以上高速化され、合計の高速化は 13 倍近くになり、Q6 と Q12 は 32 倍以上高速化されます。

七。結論

データベースはアプリケーション システムの中核であり、オプティマイザはデータベースの中核です。オプティマイザーの品質によって、データベース製品の成功または失敗がほぼ決まります。まったく新しいオプティマイザーを開発することは、どのチームにとっても大きな課題です。技術の複雑さは言うまでもなく、製品を十分に安定させること自体が克服するのが非常に難しい問題です。そのため、従来の商用データベースでも、既存のオプティマイザーに基づいて継続的に改善され、並列処理のサポートが徐々に増加し、最終的には成熟した並列オプティマイザーになります。 PolarDB についても同様です。並列クエリエンジンの設計と開発では、既存のオプティマイザの技術的蓄積と実装基盤を最大限に活用し、継続的に改善と磨きをかけ、最終的に継続的に反復的な技術ソリューションを形成して、新しいオプティマイザの安定した動作と技術革新を確保しました。