関係演算アルゴリズムとコスト
この記事は大学の期末試験勉強のために作成したものです。間違い等は悪しからず。
関係データベース演算の種類
- 入力演算
- 選択（Selection）
- 射影（[Delta] Projection)
- 集約（Aggregation）
- 整列（Order-By)
- 重複除去（Duplication Elimination）
- グループ化（Group-By）
- 結合（Join）
- 準結合（Semi-Join）
- 集合積（Intersection）
- 集合差（Difference）
- 集合和（Union）
- 直積（Cartesian Product）
- 商（Division）
演算のコスト見積もり
比較回数（CPUコスト）とディスクI/Oによって見積もる。また以下の議論では、関係代数Rのサイズを以下で定義する。
- Rのタプル数：$\{R\}$
- Rのディスクページ数：$|R|$
各選択演算とコストの見積もり
選択演算（Selection）のコスト
SELECT * FROM ~ ;
データベースにIndexがない場合
- 比較回数：$\{R\}$（Rのタプル数に等しい）
- ディスクI/O回数：$|R|$（Rのディスクページ分だけI/O）
データベースにIndexがある場合
- B木ベースのIndexの場合
- 比較回数、I/O回数共に、$\log_F\{R\}+1$
- ハッシュIndexの場合
- 比較回数、I/O回数共に、定数回（$O(1)$）
射影演算（Projection）のコスト
SELECT [DISTINCT] query1, query2 FROM ~ ;
今、重複除去（Delta）を行わないとする。
Indexの効果は無いので、全スキャンを行う。すなわち
- タプルアクセス：$\{R\}$（Rのタプル数に等しい）
- ディスクI/O回数：$|R|$（Rのディスクページ分だけI/O）
集約演算（Aggregation）
SELECT COUNT( * ) FROM ~ ;
他にもSUM()やAVE()など。
Indexの効果は無いので、全スキャンを行う。すなわち
- 比較回数：$\{R\}$（Rのタプル数に等しい）
- ディスクI/O回数：$|R|$（Rのディスクページ分だけI/O）
整列演算（Order-By）
データがCPUメモリ上に乗る場合は、一般のソートアルゴリズムを用いる。
<参考>
https://postd.cc/how-does-a-rdb-work-1/#Merge_Sort
データがCPUメモリ上に乗らない場合は、外部ソートを用いる。このとき、ディスクアクセスを前提とするとクイックソートは適さない。なぜならば、最初に論理キーで分割するため、サイズが一定でないからである。そこでマージソート、特に2-wayマージソートを用いる。（2-wayマージした各段をディスクに格納）
重複除去（Duplication Elimination）のコスト
ソートを利用した場合
-
比較の回数：$\{R\}(\log \{R\} + 1)$
- ソート（マージソート）をする：$\{R\} \log \{R\}$
- （成立したデータに対し）比較：$\{R\}$
-
ディスクI/O：$|R|(2\log |R| + 1)$
- 各段での読み出し：$2|R| \log |R|$
- 結果の格納：$|R|$
ハッシュを利用した場合
同じハッシュバケット（ハッシュテーブルにおける各スロットのこと。衝突が起きやすいハッシュテーブルでは各スロットが単一レコードでなくレコードの集合に対応していることが多いためこう呼ばれる）の中で同じ値を除去すればよい。
- 比較回数：$\{R\}$
- ディスクI/O：$|R|$
グループ化演算（Group-by）のコスト
SELECT query1, Sum(query2)
FROM "foo"
GROUP BY "bar
入れ子ループ（ネステッド・ループ）を用いる場合
query1を固定してグループに対応する全てのものを探索するので、組み合わせ演算と等価。（ $ {}_R \mathrm{C} _2$ ）
-
比較回数：$ \frac{ \{R\} (\{R\} - 1)}{2} $
- （ $ {}_R \mathrm{C} _2$ ）
-
ディスクI/O：$\frac {|R|(|R|+1) }{2} $
- 最後にディスクに結果を書き込む。
ソートを用いる場合
重複除去のソートの場合と同じ。
-
比較の回数：$\{R\}(\log \{R\} + 1)$
- ソート（マージソート）をする：$\{R\} \log \{R\}$
- （成立したデータに対し）比較：$\{R\}$
-
ディスクI/O：$|R|(2\log |R| + 1)$
- 各段での読み出し：$2|R| \log |R|$
- 結果の格納：$|R|$
ハッシュを用いる場合
- 比較回数：$\{R\}$
- ディスクI/O：$|R|$
結合演算（Join）のコスト
SELECT *
FROM DB1, DB2
WHERE DB1.hoge = DB2.huga;
入れ子ループの場合
- 比較回数：$\{R\} \times \{S\}$
- ディスクI/O：$|R| \times |S|$
ソートマージ結合を用いる場合
2つのデータベースをそれぞれソートし、この2つをマージする。
- 比較回数：$\{R\}(\log \{R\} + 1) \times \{S\}(\log \{S\} + 1)$
- ディスクI/O：$|R|(2\log |R| + 1) + |S|(2\log |S| + 1)$
ハッシュ結合を用いる場合
等結合（=）のみ可能で、両方の関係のタプルに同じハッシュ関数を適用することで実現。
RとSの全タプルが計算メモリに乗る場合...
- レコード数の少ない表（図3ではDEPARTMENT表）の結合条件列（DEPARTMENT_ID列）をハッシュ関数にかけ、メモリ上にハッシュ・テーブルを作成する。 -> BUILD
- もう一方の表（図3ではEMPLOYEE表）の結合条件列（DEPARTMENT_ID列）をハッシュ関数にかけ、結合できるかをハッシュ・テーブルで確認する。 -> PROBE
- ハッシュ値が等しいレコードを結合して結果を返す。
ハッシュテーブルのバケット数を$n$として、
- ハッシュ関数の適用の回数：$\{R\} + \{S\}$
- 比較の回数：$\{R\}/n \times \{S\}/n \times n$
RとSの全タプルが計算メモリに乗らない場合...
- 単純ハッシュ結合
- GRACEハッシュ結合
- ハイブリッド結合
ハッシュテーブルに使えるメモリ量を$|M|$、タプルサイズについて$|R| > |S|$、また属性値は均等に分散していると仮定する。
単純ハッシュ結合とそのコスト
ハッシュテーブルに入りきらない部分をディスクに格納し、これをオーバーフロー分がなくなるまで繰り返す。この時の繰り返しの回数$L$は平均で$L = |R|/|M|$
比較回数
この時の計算コストは、ハッシュ適用回数と比較回数にて決まる。
ハッシュ適用１回目
- ハッシュ適用回数：$\{R\} + \{S\}$
- 比較回数：$\{S\}/L$
ハッシュ適用i回目
- ハッシュ適用回数：$\{R\} - (i-1)\times \{R\}/L + \{S\} - (i-1)\times \{S\}/L$
- 比較回数：$\{S\}/L$
全体として
上式の$i = 1, ... , L$の和を取ればよいので、
- ハッシュ適用回数：$(|R|+|M|) \times (\{R\} + \{S\}) / (2|M|) $
- 比較回数：$\{S\}$
ディスクI/O
1回目
- 読み出し：$(|R|+|S|)$回
- 書き込み：$(|R|-|M| + |S| - |S|/L)回
２回目以降i回目
- 読み出し：$((|R|+|S|) - (i-1) \times (|R|+|S|)/L$回
- 書き込み：$((|R|+|S|) - i \times (|R| + |S|)/L$回
全体として
上式の$i = 1, ... , L$の和を取ればよいので、$|R|(|R|+|S|)/|M|$
参考
https://postd.cc/how-does-a-rdb-work-1/#Merge_Sort
https://www.atmarkit.co.jp/ait/articles/0408/25/news101.html