一元化されたシステムでのクエリの最適化

リレーショナル代数式を計算するための代替アクセスパスが導出されると、最適なアクセスパスが決定されます。この章では、集中型システムでのクエリの最適化について説明し、次の章では、分散システムでのクエリの最適化について学習します。

一元化されたシステムでは、クエリ処理は次の目的で実行されます。

クエリの応答時間の最小化（ユーザーのクエリに対して結果を生成するのにかかる時間）。
システムスループット（特定の時間内に処理される要求の数）を最大化します。
処理に必要なメモリとストレージの量を減らします。
並列処理を増やします。

クエリの解析と翻訳

最初に、SQLクエリがスキャンされます。次に、構文エラーとデータ型の正確さを探すために解析されます。クエリがこのステップに合格すると、クエリはより小さなクエリブロックに分解されます。次に、各ブロックは同等のリレーショナル代数式に変換されます。

クエリ最適化の手順

クエリの最適化には、クエリツリーの生成、プランの生成、クエリプランのコードの生成という3つのステップが含まれます。

Step 1 − Query Tree Generation

クエリツリーは、リレーショナル代数式を表すツリーデータ構造です。クエリのテーブルはリーフノードとして表されます。関係代数演算は、内部ノードとして表されます。ルートはクエリ全体を表します。

実行中、内部ノードは、そのオペランドテーブルが使用可能な場合は常に実行されます。その後、ノードは結果テーブルに置き換えられます。このプロセスは、ルートノードが実行されて結果テーブルに置き換えられるまで、すべての内部ノードに対して続行されます。

たとえば、次のスキーマについて考えてみましょう。

従業員

EmpID	EName	給料	部門番号	入社の日

部門

Dいいえ	DName	ロケーション

例1

クエリを次のように考えてみましょう。

$$ \ pi_ {EmpID}（\ sigma_ {EName = \ small "ArunKumar"} {（EMPLOYEE）}）$$

対応するクエリツリーは次のようになります-

例2

結合を含む別のクエリについて考えてみましょう。

$ \ pi_ {EName、Salary}（\ sigma_ {DName = \ small "Marketing"} {（DEPARTMENT）}）\ bowtie_ {DNo = DeptNo} {（EMPLOYEE）} $

以下は、上記のクエリのクエリツリーです。

Step 2 − Query Plan Generation

クエリツリーが生成された後、クエリプランが作成されます。クエリプランは、クエリツリー内のすべての操作のアクセスパスを含む拡張クエリツリーです。アクセスパスは、ツリー内の関係演算の実行方法を指定します。たとえば、選択操作には、選択のためのB +ツリーインデックスの使用に関する詳細を提供するアクセスパスを含めることができます。

さらに、クエリプランには、中間テーブルをあるオペレーターから次のオペレーターに渡す方法、一時テーブルを使用する方法、操作をパイプライン化/結合する方法も記載されています。

Step 3− Code Generation

コード生成は、クエリ最適化の最終ステップです。これはクエリの実行可能形式であり、その形式は基盤となるオペレーティングシステムの種類によって異なります。クエリコードが生成されると、Execution Managerはそれを実行し、結果を生成します。

クエリ最適化へのアプローチ

クエリ最適化のアプローチの中で、徹底的な検索とヒューリスティックベースのアルゴリズムが主に使用されます。

徹底的な検索の最適化

これらの手法では、クエリに対して、考えられるすべてのクエリプランが最初に生成され、次に最適なプランが選択されます。これらの手法は最良のソリューションを提供しますが、ソリューションスペースが大きいため、時間とスペースが指数関数的に複雑になります。たとえば、動的計画法。

ヒューリスティックベースの最適化

ヒューリスティックベースの最適化では、クエリの最適化にルールベースの最適化アプローチを使用します。これらのアルゴリズムは、多項式の時間と空間の複雑さを持っています。これは、徹底的な検索ベースのアルゴリズムの指数関数的な複雑さよりも低くなっています。ただし、これらのアルゴリズムは必ずしも最良のクエリプランを生成するとは限りません。

一般的なヒューリスティックルールのいくつかは次のとおりです。

結合操作の前に、選択操作とプロジェクト操作を実行します。これは、選択操作とプロジェクト操作をクエリツリーの下に移動することによって行われます。これにより、結合に使用できるタプルの数が減ります。
他の操作の前に、最初に最も制限の厳しい選択/プロジェクト操作を実行します。
非常に大きなサイズの中間テーブルになるため、製品間の操作は避けてください。