集中システムでのクエリ最適化

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

集中システムでは、クエリ処理は次の目的で行われます-

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

クエリの解析と翻訳

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

クエリ最適化の手順

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

ステップ1-クエリツリーの生成

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

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

たとえば、次のスキーマを考えてみましょう-

社員

EmpID

EName

Salary

DeptNo

DateOfJoining

部門

DNo

DName

Location

例1

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

\ pi _ \ {EmpID}（\ sigma _ \ {EName = \ small "ArunKumar"} \ {（EMPLOYEE）}）

対応するクエリツリーは-

対応するクエリツリー

例2

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

$ \ pi _ \ {EName、Salary}（\ sigma _ \ {DName = \ small "Marketing"} \ {（DEPARTMENT）}）\ bowtie _ \ {DNo = DeptNo} \ {（EMPLOYEE）} $

上記のクエリのクエリツリーを次に示します。

クエリツリー

ステップ2-クエリプランの生成

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

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

ステップ3-コード生成

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

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

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

徹底的な検索の最適化

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

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

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

一般的なヒューリスティックルールの一部は次のとおりです-

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

Distributed-dbms-query-optimization-centralized-systems

目次