クエリ最適化のための関係代数

クエリが配置されると、最初にスキャン、解析、および検証されます。次に、クエリツリーやクエリグラフなど、クエリの内部表現が作成されます。次に、データベーステーブルから結果を取得するための代替実行戦略が考案されます。クエリ処理に最も適切な実行戦略を選択するプロセスは、クエリ最適化と呼ばれます。

DDBMSのクエリ最適化の問題

DDBMSでは、クエリの最適化は重要なタスクです。次の要因により、代替戦略の数が指数関数的に増加する可能性があるため、複雑さが高くなります。

多数のフラグメントの存在。
さまざまなサイト間でのフラグメントまたはテーブルの配布。
通信リンクの速度。
ローカル処理機能の不一致。

したがって、分散システムでは、多くの場合、ターゲットは、最適な実行戦略ではなく、クエリ処理の適切な実行戦略を見つけることです。クエリを実行する時間は、次の合計です。

クエリをデータベースに伝達する時間です。
ローカルクエリフラグメントを実行する時間。
さまざまなサイトからデータを収集する時間です。
結果をアプリケーションに表示する時間です。

クエリ処理

クエリ処理は、クエリの配置からクエリの結果の表示までのすべてのアクティビティのセットです。手順は次の図に示すとおりです-

関係代数

関係代数は、リレーショナルデータベースモデルの基本的な操作セットを定義します。一連の関係代数演算は、関係代数式を形成します。この式の結果は、データベースクエリの結果を表します。

基本的な操作は次のとおりです。

Projection
Selection
Union
Intersection
Minus
Join

投影

射影操作は、テーブルのフィールドのサブセットを表示します。これにより、テーブルの垂直パーティションが作成されます。

Syntax in Relational Algebra

$$ \ pi _ {<{AttributeList}>} {（<{テーブル名}>）} $$

たとえば、次の学生データベースについて考えてみましょう。

STUDENT
Roll_No	Name	Course	Semester	Gender
2	アミット・プラサド	BCA	1	男性
4	ヴァルシャ・ティワリ	BCA	1	女性
5	Asif Ali	MCA	2	男性
6	ジョーウォーレス	MCA	1	男性
8	シヴァニアイアンガー	BCA	1	女性

すべての学生の名前とコースを表示する場合は、次の関係代数式を使用します。

$$ \ pi_ {Name、Course} {（STUDENT）} $$

選択

選択操作は、特定の条件を満たすテーブルのタプルのサブセットを表示します。これにより、テーブルの水平パーティションが作成されます。

Syntax in Relational Algebra

$$ \ sigma _ {<{Conditions}>} {（<{Table Name}>）} $$

たとえば、Studentテーブルで、MCAコースを選択したすべての学生の詳細を表示する場合は、次の関係代数式を使用します。

$$ \ sigma_ {コース} = {\ small "BCA"} ^ {（STUDENT）} $$

射影演算と選択演算の組み合わせ

ほとんどのクエリでは、射影操作と選択操作の組み合わせが必要です。これらの式を書くには2つの方法があります-

一連の投影および選択操作を使用します。
名前変更操作を使用して中間結果を生成します。

たとえば、BCAコースのすべての女子学生の名前を表示するには-

一連の射影および選択演算を使用した関係代数式

$$ \ pi_ {Name}（\ sigma_ {Gender = \ small "Female" AND \：Course = \ small "BCA"} {（STUDENT）}）$$

名前変更操作を使用して中間結果を生成する関係代数式

$$ FemaleBCAStudent \ leftarrow \ sigma_ {Gender = \ small "Female" AND \：Course = \ small "BCA"} {（STUDENT）} $$

$$結果\ leftarrow \ pi_ {Name} {（FemaleBCAStudent）} $$

連合

Pが操作の結果であり、Qが別の操作の結果である場合、PとQの和集合（$ p \ cup Q $）は、PまたはQのいずれか、あるいは両方に重複のないすべてのタプルのセットです。。

たとえば、セメスター1またはBCAコースのいずれかにあるすべての学生を表示するには-

$$ Sem1Student \ leftarrow \ sigma_ {Semester = 1} {（STUDENT）} $$

$$ BCAStudent \ leftarrow \ sigma_ {コース= \ small "BCA"} {（STUDENT）} $$

$$結果\ leftarrow Sem1Student \ cup BCAStudent $$

交差点

Pが操作の結果であり、Qが別の操作の結果である場合、PとQの共通部分（$ p \ cap Q $）は、PとQの両方にあるすべてのタプルのセットです。

たとえば、次の2つのスキーマがあるとします-

EMPLOYEE

EmpID	名前	市	部門	給料

PROJECT

PId	市	部門	状態

プロジェクトがあり、従業員が住んでいるすべての都市の名前を表示するには-

$$ CityEmp \ leftarrow \ pi_ {City} {（EMPLOYEE）} $$

$$ CityProject \ leftarrow \ pi_ {City} {（PROJECT）} $$

$$結果\ leftarrow CityEmp \ cap CityProject $$

マイナス

Pが操作の結果であり、Qが別の操作の結果である場合、P-Qは、QではなくPにあるすべてのタプルのセットです。

たとえば、進行中のプロジェクトがないすべての部門を一覧表示するには（ステータス=進行中のプロジェクト）-

$$ AllDept \ leftarrow \ pi_ {Department} {（EMPLOYEE）} $$

$$ ProjectDept \ leftarrow \ pi_ {Department}（\ sigma_ {Status = \ small "ongoing"} {（PROJECT）}）$$

$$結果\ leftarrow AllDept-ProjectDept $$

参加する

結合操作は、2つの異なるテーブル（クエリの結果）の関連するタプルを1つのテーブルに結合します。

たとえば、銀行データベースのCustomerとBranchの2つのスキーマを次のように考えます。

CUSTOMER

CustID	AccNo	TypeOfAc	BranchID	DateOfOpening

BRANCH

BranchID	支店名	IFSCコード	住所

支店の詳細とともに従業員の詳細を一覧表示するには-

$$結果\ leftarrow CUSTOMER \ bowtie_ {Customer.BranchID = Branch.BranchID} {BRANCH} $$

SQLクエリの関係代数への変換

SQLクエリは、最適化の前に同等のリレーショナル代数式に変換されます。クエリは、最初は小さなクエリブロックに分解されます。これらのブロックは、同等のリレーショナル代数式に変換されます。最適化には、各ブロックの最適化と、クエリ全体の最適化が含まれます。

例

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

社員

EmpID	名前	市	部門	給料

事業

PId	市	部門	状態

WORKS

EmpID	PID	時間

例1

平均給与よりも少ない給与を稼いでいるすべての従業員の詳細を表示するために、SQLクエリを記述します-

SELECT * FROM EMPLOYEE 
WHERE SALARY < ( SELECT AVERAGE(SALARY) FROM EMPLOYEE ) ;

このクエリには、ネストされたサブクエリが1つ含まれています。したがって、これは2つのブロックに分割できます。

内側のブロックは-

SELECT AVERAGE(SALARY)FROM EMPLOYEE ;

このクエリの結果がAvgSalの場合、外側のブロックは-です。

SELECT * FROM EMPLOYEE WHERE SALARY < AvgSal;

内部ブロックの関係代数式-

$$ AvgSal \ leftarrow \ Im_ {AVERAGE（Salary）} {EMPLOYEE} $$

外側のブロックの関係代数式-

$$ \ sigma_ {Salary <{AvgSal}>} {EMPLOYEE} $$

例2

従業員「ArunKumar」のすべてのプロジェクトのプロジェクトIDとステータスを表示するには、SQLクエリを記述します-

SELECT PID, STATUS FROM PROJECT 
WHERE PID = ( SELECT FROM WORKS  WHERE EMPID = ( SELECT EMPID FROM EMPLOYEE 
            WHERE NAME = 'ARUN KUMAR'));

このクエリには、ネストされた2つのサブクエリが含まれています。したがって、次のように3つのブロックに分割できます。

SELECT EMPID FROM EMPLOYEE WHERE NAME = 'ARUN KUMAR'; 
SELECT PID FROM WORKS WHERE EMPID = ArunEmpID; 
SELECT PID, STATUS FROM PROJECT WHERE PID = ArunPID;

（ここで、ArunEmpIDとArunPIDは内部クエリの結果です）

3つのブロックの関係代数式は次のとおりです。

$$ ArunEmpID \ leftarrow \ pi_ {EmpID}（\ sigma_ {Name = \ small "Arun Kumar"} {（EMPLOYEE）}）$$

$$ ArunPID \ leftarrow \ pi_ {PID}（\ sigma_ {EmpID = \ small "ArunEmpID"} {（WORKS）}）$$

$$ Result \ leftarrow \ pi_ {PID、Status}（\ sigma_ {PID = \ small "ArunPID"} {（PROJECT）}）$$

関係代数演算子の計算

関係代数演算子の計算はさまざまな方法で実行でき、それぞれの選択肢は access path。

代替計算は、3つの主な要因に依存します-

演算子タイプ
使用可能なメモリ
ディスク構造

関係代数演算の実行を実行する時間は、-の合計です。

タプルを処理する時間です。
テーブルのタプルをディスクからメモリにフェッチする時間。

タプルを処理する時間は、ストレージからタプルをフェッチする時間よりも非常に短いため、特に分散システムでは、ディスクアクセスは、リレーショナル式のコストを計算するためのメトリックと見なされることがよくあります。

選択の計算

選択操作の計算は、選択条件の複雑さとテーブルの属性のインデックスの可用性に依存します。

以下は、インデックスに応じた計算の選択肢です。

No Index−テーブルがソートされておらず、インデックスがない場合、選択プロセスには、テーブルのすべてのディスクブロックのスキャンが含まれます。各ブロックがメモリに取り込まれ、ブロック内の各タプルが選択条件を満たすかどうかが調べられます。条件が満たされると、出力として表示されます。これは、各タプルがメモリに取り込まれ、各タプルが処理されるため、最もコストのかかるアプローチです。
B+ Tree Index−ほとんどのデータベースシステムは、B +ツリーインデックスに基づいて構築されています。選択条件がこのB +ツリーインデックスのキーであるフィールドに基づいている場合、このインデックスは結果の取得に使用されます。ただし、複雑な条件で選択ステートメントを処理すると、ディスクブロックへのアクセス数が多くなり、場合によってはテーブルの完全なスキャンが必要になることがあります。
Hash Index−ハッシュインデックスが使用され、そのキーフィールドが選択条件で使用される場合、ハッシュインデックスを使用してタプルを取得することは簡単なプロセスになります。ハッシュインデックスは、ハッシュ関数を使用して、ハッシュ値に対応するキー値が格納されているバケットのアドレスを検索します。インデックス内のキー値を見つけるために、ハッシュ関数が実行され、バケットアドレスが見つかります。バケット内のキー値が検索されます。一致するものが見つかった場合、実際のタプルがディスクブロックからメモリにフェッチされます。

結合の計算

PとQなどの2つのテーブルを結合する場合、結合条件が満たされているかどうかをテストするために、Pの各タプルをQの各タプルと比較する必要があります。条件が満たされると、対応するタプルが連結され、重複するフィールドが削除され、結果の関係に追加されます。したがって、これは最もコストのかかる操作です。

結合を計算するための一般的なアプローチは次のとおりです。

ネストループアプローチ

これは、従来の結合アプローチです。これは、次の擬似コードで説明できます（表PおよびQ、タプルtuple_pおよびtuple_q、結合属性a）-

For each tuple_p in P 
For each tuple_q in Q
If tuple_p.a = tuple_q.a Then 
   Concatenate tuple_p and tuple_q and append to Result 
End If 
Next tuple_q 
Next tuple-p

ソートマージアプローチ

このアプローチでは、2つのテーブルが結合属性に基づいて個別にソートされ、ソートされたテーブルがマージされます。レコード数が非常に多く、メモリに収容できないため、外部ソーティング手法が採用されています。個々のテーブルがソートされると、ソートされた各テーブルの1ページがメモリに取り込まれ、結合属性に基づいてマージされ、結合されたタプルが書き出されます。

ハッシュ結合アプローチ

このアプローチは、パーティショニングフェーズとプロービングフェーズの2つのフェーズで構成されます。パーティショニングフェーズでは、テーブルPとQが2セットの互いに素なパーティションに分割されます。共通のハッシュ関数が決定されます。このハッシュ関数は、タプルをパーティションに割り当てるために使用されます。プロービングフェーズでは、Pのパーティション内のタプルがQの対応するパーティションのタプルと比較されます。それらが一致する場合、それらは書き出されます。