このトピックでは、クエリの最適化と結合順序変更の仕組みについて説明します。

クエリ最適化の概要

クエリ文が処理されると、オプティマイザは入力したクエリ文を受け取り、一連の同等の変換を実行し、カーディナリティ推定モデルとコストモデルを使用して同等の実行計画から最適な実行計画を選択します。データベースのパフォーマンスは選択した実行プランに大きく依存するため、すべてのデータベースシステムにクエリオプティマイザがあります。次の図は、一般的なクエリオプティマイザを示しています。

一般的なクエリオプティマイザには、次のコンポーネントが含まれます。

プランスペース列挙: 一連の同等の変換ルールに基づいて、複数の同等の実行プランを生成します。
カーディナリティ推定: テーブルの分布に基づいて、クエリ実行中のデータ量とデータ分布を推定します。
コストモデル: 実行計画とデータベース内の状態に基づいて、各実行計画を実行するためのコストを計算します。

結合順序の問題は、クエリオプティマイザのクエリプランで広く研究されています。誤った結合順序を選択すると、クエリのパフォーマンスが大幅に低下します。結合順序の問題は、前述のコンポーネントにも依存します。

HTAPのオプティマイザの新しい要件

MySQLは広く使用されているOLTPデータベースです。データストレージ、アクセス、およびシンプルまたは固定パターンのクエリに優れています。これを達成するために、MySQLオプティマイザは、その実行モデルに関連する多くの最適化を行う。たとえば、サブクエリはクエリ最適化フェーズで実行および削除され、ORDER BY句はインデックスに基づいて削除されます。このような最適化は、MySQLクエリで良好な結果をもたらす。これは、MySQLオプティマイザが実行モデルとストレージとの関連性が高いことも意味します。 HTAPでは、ほとんどのソリューションが行ストレージとIMCI (レプリカ) を使用し、実行層で複雑なクエリを高速化します。このような条件下では、MySQLオプティマイザのほとんどの仮定は覆されます。 MySQLオプティマイザは実行モデルとストレージとの関連性が高いため、簡単な変更でHTAPのクエリ最適化機能に適応することは困難です。データベースが異なるストレージモード、異なる実行モデル、および異なるデータモデルを処理する場合、オプティマイザは次の機能を提供する必要があります。

将来の機能の進化を容易にするために、ストレージ層または実行層との相関が少ない。
多次元フィルタリング、結合、集計などの複雑なクエリを処理できます。
HTAPでリアルタイム分析を実装するための効率的なクエリ最適化。

IMCIクエリの最適化

行ベースのプランの最適化とその限界

MySQLオプティマイザには、次の最適化プロセスがあります。

ルールベースの最適化を適切なプランに適用します (コスト計算は含まれません) 。
いくつかの外部結合を内部結合に変換する。
同等の変換を実装します。例えば、c1 = 5およびc1 = c2は、c1 = 5およびc2 = 5に変換することができる。
パーティションプルーニングを実行します。一部のパーティションのみがクエリされる場合、他のパーティションはアクセスされません。これにより、スキャンデータの量を大幅に削減できます。
サブクエリを削除します。計画を単純化するために、1行のみを返す一部のサブクエリは事前に実行され、結果に置き換えられます。
コストベースの結合再注文を使用します。
その後の最適化対策を実現します。テーブルにアクセスするメソッドが決定され、使用されるインデックスに基づいてORDER BYおよびDISTINCT句が削除されます。

この最適化プロセスは非常に明確で、MySQL実行モードで優れています。ただし、レプリカノードを追加すると、この最適化プロセスには次の問題もあります。

MySQL実行モードの制限により、結合再注文は左ディープ実行プランのみを生成できます。複雑なHTAPクエリでは、最適な実行計画が失われる可能性があります。サブクエリと結合順序ヒントを使用したSQLの書き換えは、ビジネスに大きな変化をもたらします。
MySQLが実行計画を列挙すると、入力行の数と各結合の選択性が計算されます。 MySQLは主に結合操作でインデックス結合を実行します。 MySQLは、テーブル上の既存のセカンダリインデックスを使用して選択性を推定します。二次インデックスが作成されない場合、コスト見積もりに重大なエラーが発生する可能性があります。これは、元のMySQLシナリオと一致します。結合操作はインデックスを使用し、インデックスを使用して低速クエリの問題を解決できます。ただし、この方法は、多数のセカンダリインデックスが必要になるため、IMCIで多次元フィルター、結合、および集計操作を実行する場合には適していません。インデックスを作成すると、読み取りロードは書き込み操作に均等に割り当てられます。多数の二次インデックスは、高い記憶空間を占有し、書き込み効率を低下させる。ヒストグラムはMySQL 8.0に導入されていますが、単一のテーブルで条件をフィルタリングし、選択性を推定するだけです。ヒストグラムは複雑なクエリステートメントでは役に立ちません。
結合再順序の問題を分離することは、検索効率を改善するが、局所的に最適な計画の問題を引き起こし得る。

IMCIプラン最適化プロセス

IMCI機能は、HTAPのMySQLオプティマイザの欠点を克服するための新しい最適化プロセスを導入します。新しい最適化プロセスは、不足しているインデックス、新しい実行モデル、およびHTAPの複雑なクエリを処理します。 IMCIクエリでは、オプティマイザはルールベースの書き換えとコストベースの最適化を使用します。

ルールベースの計画の書き換え

この手順は、MySQLオプティマイザに似ています。 MySQLオプティマイザの既存のルールに新しいルールが追加されます。これらの新しい規則は、主に、IMCIエグゼキュータの効率をさらに最適化し、実行計画を実行モデルの要件に適合させるために使用される。例：

サブクエリのネスト解除: インデックスがない場合、ネストされたサブクエリはネストされたループ結合と同様に実行されます。このため、実行効率が悪くなる。 IMCI機能は、サブクエリアンネストを使用してネストされたサブクエリを結合に変換し、ハッシュ結合を使用してクエリを効率的に実行します。
サブクエリにDISTINCTを含む集計関数は削除されます。例：
```
SELECT COUNT(DISTINCT c1) FROM t;
-- に変換されます
SELECT COUNT(c1) FROM (SELECT c1 FROM t GROUP BY c1); 
```
このような変換により、IMCIエグゼキュータの設計が簡素化され、より多くの機能がサポートされます。
述語の再分類: たとえば、共通のテーブルスキャンでは、複数の述語が見つかります。t1.c2 LIKE '% cat %' AND t1.c1 = 5。 t1.c1 = 5の述語は、より低い実行コストをもたらし、より低い選択性を有する。これら2つの述語を再分類し、最初にt1.c1 = 5述語を実行すると、LIKE演算が大幅に削減され、クエリ効率が向上します。
実際、このステップには、コストベースのクエリ最適化も含まれます。これは、ほとんどの場合、クエリも最適化します。述語プッシュダウンなどの動作のための規則を適用することは、コストベースのクエリ最適化装置および実行装置の入力を標準化し、コストベースのクエリ最適化において消費されるストレージを低減し、クエリ最適化の効率を改善する。

コストベースの最適化

ルールベースのクエリの書き換え後、プランはコストベースのクエリオプティマイザを入力します。 IMCI機能は、カスケードオプティマイザーフレームワークを使用します。これにより、クエリ最適化でのローカル最適プランの問題を回避できます。このフレームワークに加えて、従来のオプティマイザの次の機能モジュールも使用されます。プラン列挙、カーディナリティ推定、コストモデル。これらのモジュールの作業プロセスは、結合順序の問題に基づいて説明されます。

プラン列挙

プラン列挙は、オプティマイザがプランを列挙するために使用するコンポーネントです。解析やバインドなどの一連の手順の後、初期クエリプランが生成され、オプティマイザに追加されます。オプティマイザは、ルールを使用してクエリ計画に対してさまざまな同等の変換を実行し、新しい同等のクエリ計画を生成します。 IMCIでは、プラン書き換えのルールは次のタイプに分類されます。

変換ルール: ルールの書き換えに似ています。ただし、これらのルールはオプションであり、クエリのパフォーマンスを最適化するために使用されます。それらは広く使用されていません。したがって、このようなルールがIMCIのコストベースのオプティマイザに追加され、同等のクエリプランが列挙されます。続いて、カーディナリティ推定およびコストモデルを使用することによって、最適なクエリプランが選択される。
ルールの実装: 論理計画と物理計画の間でアルゴリズムを選択するために使用されます。例えば、結合操作のために、ハッシュ結合、インデックス結合、およびソートマージ結合を選択することができる。異なるアルゴリズムは、異なるシナリオに適している。したがって、このようなルールは、IMCIのコストベースのオプティマイザにも追加されます。

このモジュールでは、実行計画は、これらの書き換え規則に基づいて多数の同等の計画に変換されます。最適なプランは、コストを比較して選択されます。 IMCIのカスケードオプティマイザは、Memo、Group、GroupExprなどのデータ構造を使用して、共有中間結果を保存します。これは、多くの冗長な中間結果を排除する。しかし、多数の結合を含むクエリステートメントは、依然として膨大な等価プランを生成する可能性がある。 n個のテーブルの結合に対して、少なくとも2 ^n個の可能な結合順序が存在する。次の図は、デカルト積を考慮しない結合計画の数と列挙時間の関係を示しています。

上の図は、12個のテーブルを含む結合再順序が、最悪の場合に10秒以上かかることを示しています。一般的なスタークエリでも、20個のテーブルの計画を最適化するのに10秒以上かかる場合があります。この最適化時間は、多くのテーブルを含むいくつかのクエリには受け入れられない。最適な結合順序を選択すると、3つの問題を解決できます。

最適なプランは、列挙された結合プランに含める必要があります。この目標を達成するためには、最適な結合計画を探索空間に含めることができるように、列挙は高効率でなければならない。
結合されるテーブルが多すぎる場合、許容可能な期間内に適切なクエリプランを検索するために、安定したヒューリスティックアルゴリズムが利用可能である。
列挙されたすべての結合プランから最適なプランを正しく選択できます。

カーディナリティ推定とコストモデル

最適なプランは、各プランのコストを見積もることによって選択されます。現在のオプティマイザでは、このプロセスには次のコンポーネントが含まれます。

カーディナリティ推定コンポーネントは、各演算子の入力行および出力行の数と、各演算子の出力データの近似分布とを推定する。このコンポーネントは、2つのモジュールに依存しています。統計の収集と計算、および入力行と出力行の数を計算するロジックです。
コストモデルコンポーネントは、コストを計算し、各演算子の実行コストを加算して総コストを取得し、総コストが最も低い実行プランを選択します。

IMCIでの統計の収集と計算

十分なセカンダリインデックスがない場合にクエリを最適化するために、IMCI機能はオプティマイザで統計モジュールを使用します。 IMCI機能は、テーブルから次の情報を収集することにより、各演算子の出力行数と出力行数を推定します。

各列のカーディナリティ (列内の一意の値の数。COUNT(DISTINCT col) に相当します) 。
各列のNULL値の割合。
各列の最大値と最小値。
値のサイズに基づいて各列に作成されたヒストグラム。
テーブル内の一意のキー属性と外部キー属性。

IMCI機能のために構築された統計

これらの統計を収集するために、システムはテーブルのデータ量に基づいてサンプリングする行数を計算します。サンプリングされる行数は、次の式を使用して決定されます。

式において、nはテーブルのサイズであり、kはヒストグラムにおけるバケットの数であり、fは相対誤差 (または信頼度) の信頼区間である。オプティマイザが適切な定数に基づいてサンプリングされた行の数を計算した後、オプティマイザは入力行を使用してヒストグラムを作成し、NULL値の割合を計算します。オプティマイザは、サンプリングされたデータに基づいて列のカーディナリティを計算します。 IMCIでは、オプティマイザは最初に上記の式を使用してサンプリングされた行の数を計算し、次にサンプリングレートに基づいて異なるカーディナリティ推定式を選択してカーディナリティ推定のエラーを最小化します。このような式は通常、一様なランダムサンプリングを必要とする。しかしながら、IMCIでは、データは通常、ページに格納されない。 IMCIでは、通常、64K行が圧縮され、すべて一緒に格納されます。データの行が読み取られると、その行を含むデータブロック全体がディスクから読み取られ、解凍される。これは重大な読み取り増幅を引き起こす。この問題を解決するために、IMCIはデータブロックをサンプリングしてリード増幅を減らし、COLLAPSEアルゴリズムを使用して異なる値の計算式を変更します。複数の同一の値が同じブロックに現れる場合、前の式はに大きく依存するため、1つの値のみが計算されます。一様ランダムサンプリングに基づく推定誤差は、データ局所性の影響を低減することによって補正される。

オペレータが統計を使用してIMCIの行数を推定する方法

実際に推定する必要がある演算子は、フィルタリング、結合、およびグループバイです。ソートなどの他の演算子の場合、出力は通常、入力行の数にのみ関連します。ヒストグラムは、a > 10 AND a < 100のような述語の選択性を効果的に推定することができる。ヒストグラムのジョインは、等しいジョインおよびレンジジョインの選択性を計算することができる。列カーディナリティは、出力ごとにグループ内のグループの数を推定するために、ならびに、いくつかのヒストグラムが利用可能でない場合に等価述語および等価結合の選択性を推定することを支援するために使用することができる。例えば、Selectivity(a = 1) = 1/COUNT(DISTINCT a) では、一意のキーおよび外部キーを使用して、等しい結合の結果を訂正することができる。次のSQL文では、

SELECT COUNT(*)
t1, t2から
どこt1.a = t2.a;

t1.aはt1の固有キーであり、t1.aはt2.aの外部キーである。 t2の各行について、t1はそれに一致する行を含む必要がある。これにより、このジョインの出力行数とt2のサイズを正確に求めることができる。

複数の述語の相関

IMCI機能は、データ列が相関しているという仮定を使用します。指数バックオフアルゴリズムは、複数の述語間の選択性を計算するために使用される。このアルゴリズムは、まず各述語の選択性値をソートし、次に次の式を使用して選択性を計算します。

アルゴリズムは、実際のデータに基づいてほとんどのデータセットの推定誤差を効果的に減らすことができます。

テストの最適化結果

IMCIクエリ最適化が有効および無効の場合、TPCH 1テラバイトデータセットのパフォーマンスをテストします。最適化の結果を次の図に示します。

前の図では、Q8とQ9のマルチテーブル結合の場合、IMCIクエリの最適化が有効になった後、より良いクエリプランが選択されているため、実行効率が大幅に向上しています。

IMCIクエリ最適化が有効になっていない場合、結合は方法で実行されます。次の図では、テーブルdとテーブルe (オレンジ色) を結合するために大量のデータが処理されます。全体のクエリ時間の60% 以上は、大きなテーブルを結合するためのデータの処理に費やされます。次の図は、IMCIクエリ最適化が有効でない場合のクエリプロセスを示しています。

次の図は、IMCIクエリ最適化が有効な場合のクエリプロセスを示しています。

IMCIクエリ最適化を有効にすると、結合順序はになります。大きなテーブルdおよびeの結合は排除される。実行時間は50% 以上短縮されます。