Zenn
⛳

データベースについてまとめる。

2020/10/13に公開
DB
RDBMS
tech

あまり使う機会がなかったRDBMSについてまとめていきます。モチベーションを保つためにみなさんのリアクションが欲しいので最初から公開状態で、書いていきます。なので読みにくいとは思いますがリアクションお願いします。

SQL文はどのように実行されるか。

RDBMSでのSQL文の処理

データベースにに対して処理の命令を行う文であるSQL文を受け取ったデータベースはどのような処理を行うかをみていきます。

  1. SQL文の解析
    • SQL文が文法的に正しいかどうか
    • 選択・射影・結合といった処理がそれぞれどのように実行されるかといった文の構造把握
    • SQL文内で指定されたテーブル、フィールドが存在するかどうか
    • ユーザのアクセス権限があるかどうか
      といったことを解析します。
  2. SQL文の書き換え
    ユーザが与えたSQL文をより高速に実行できるように書き換える処理をします。書き換えられたSQL文は，最終的にRDBMS内部の処理命令の集まりに変換されます。
  3. 実行計画の作成
    RDBMS内部の処理命令の集まりを実行する方法いくつかあります[1]。RDBMSは処理命令を実行する手続きを何通りか作成したうえで、その中から効率の良いものを作成します[2]。
    このようにRDBMSの内部の形式で表された一連の手続きのことを「実行計画」といいます。

こうして作成された実行計画は，内部処理命令ごとに実行され，ハードディスクからテーブルのデータなどがキャッシュ・バッファに読み込まれて操作されることになります。実際にデータを操作するまでにいくつもの処理が入っていることがわかります。

①の処理はパーサーという機能が担当します。
②③の処理を最適化といいオプティマイザという機能が担当します。

SQLの書き換えの具体例

SQL文の処理の２つ目で書き換えを行っていますが、その具体例を一つみてみましょう。

-- code:db-1
SELECT * FROM table1, table2
WHERE table1.id = 10
AND table2.id = table1.id

db-1はtable1, table2から、table1のidフィールドの値が10であり，かつtable1とtable2のidフィールドの値が一致するレコードを検索するSQL文です。

このSQL文をRDBMSでは例えば以下のように変更します。

SELECT * FROM table1, table2
WHERE table1.id = 10
AND table2.id = table1.id
AND table2.id = 10

これにより、table2に対してインデックス検索をすることができるようになり高速な処理が出来ます。

実行計画の具体例

データベースの各テーブルはよくExcelのような２次元の表で表現されます。コンピュータは人間のように表をザーッと眺めるようなことは出来ず一つずつ確認していくことしか出来ません。なのでどのように見ていくかの実行計画は効率に大きく影響します。

例えば２つのテーブルから以下のSQL文でデータを取り出すとしましょう。

SELECT column1, column2, column3, column4
FROM table1, table2
WHERE table1.table2no = table2.table2no

table2はtable２noという主キーを持ちインデックスpk_table2noが定義されています。一方table1はtable2noという外部キーを持ちますがこれに対してインデックスは作成されていません。

このSQL文に対して実行計画を作成した場合以下のようなものが考えられます。

  • 方法1

    1. table1から一つレコードを取り出す。
    2. table2から１つレコードを取り出し先ほどのtable1のレコードと組み合わせる。
    3. 以上を全てのレコードに対して行い、全ての組み合わせを作る。
    4. 全ての組み合わせからWHEREの条件に合致するものを取り出す。

  • 方法2

    1. table1から一つレコードを取り出す。
    2. そのレコードのtable2noをキーとしてインデックスpk_table2noを検索する。
    3. 検索して得られたROWID[3]を使ってtable2から対応するレコードを取り出す。
    4. 以上をtable1の各レコードについて繰り返す。

  • 方法3

    1. table2から一つレコードを取り出す。
    2. そのレコードのtable2noを使ってtable1のtable2noを全表走査で探す。
    3. 見つけたレコードを取り出す。
    4. 以上をtable2の各レコードについて繰り返す。

イメージとしては与えられた２つの配列から一致するものを探すプログラムのロジックを考える感じです。もちろん今は低レイヤーの処理を考えているのでfind関数など便利なものはなく基本的な制御構文があるだけだと思ってください。

方法１ではfor文などの繰り返しの制御構文を二重にループさせて見つけるロジックです。
方法２では片方の配列がどこに何があるかのラベルがついている連想配列になっていて、もう一方の配列をループさせもう片方は連想配列のキーを指定して直接見つけるロジックです。
方法３でも片方が連想配列になっていてそれをループさせもう片方もキーが与えられていないのでループで見つけるロジックです。

イメージがついたところでどれが効率がいいか考えて見ましょう。方法１は無駄がとても多いことはすぐにわかると思います。方法３もせっかくインデックスが作ってあるのにそれを活かせていませんね。ここでは方法２が一番効率のいい実行計画と言えます。
オプティマイザはこのような候補の中から効率が良いものを選び出して実行計画を作成します。

実行計画の選択基準

上の項であげた例ではある意味人間的な感覚で効率の良い方法を選びましたが、実際にオプティマイザがどのような基準で選んでいるかをみてみましょう。大きく分けて二つのやり方があります。

ルールベースアプローチ

ルールベースアプローチはその名の通りルールを設け、そのルールにしたがって実行計画を選定します。一つのテーブルからデータを取り出す方法のことをアクセスパスといいます。アクセスパスには前述の全表走査などいくつも種類があります。それらのアクセスパスに対して効率に合わせてランクを付けます。ルールベースアプローチでは実行計画でより効率の良いランクのアクセスパスを持つものが選ばれます。

コストベースアプローチ

コストベースアプローチもその名の通りコストを元に実行計画を選定します。ここでいうコストとは、ディスクへのアクセス回数はCPU、メモリ使用量などを指します。このようなコストはテーブルのレコード数や，フィールドの値の最大値/最小値などの統計情報を元に算出されます。このようにして算出されたコストのうち最も低い実行計画が選ばれます。

どちらがいいのか？

ルールベースは場合によっては効率の悪い方法を選択してしまうので現在ではコストベースアプローチが主流のようです。

コストベースアプローチについてもう少し

コストベースアプローチは現在のテーブル数・レコード数などの統計情報から実行計画を作成します。例えば100件のレコードを持つデータベースの統計情報があります。この程度の数なら全表走査で十分なのでわざわざインデックスを設ける必要はありません。しかし、これが100万件のレコードを持つデータベースならインデックスを作った方が良いでしょう。この時統計情報を100件の時からアップデートしていなければ、100万件のレコードに対して100件のレコードの基準で全表走査をするでしょう。このように、コストベースでも現在のデータベースの状態を反映した統計情報がないと、効率の悪い方法を選択してしまいます。よって統計情報は頻繁にアップデートすることが求められます。
また、コストはフィールドの値が均等に分布していることを前提に計算されます。

フィールド名 型 制約
ID 数値 PRIMARY KEY/NOT NULL
NAME 文字
STATUS 文字 INDEX
その他
データ件数:1000件
内訳
STATUS:'success' 980件
STATUS:'failed' 10件
STATUS:'running' 10件

このようなテーブルから状態が'success'以外のものを取り出したいとしましょう。この場合は探したいレコードは20件ですのでインデックスを使って検索する方が早いと言えます。

例えば以下のようなSQL文が考えられます。
SELECT * FROM todos WHERE status != 'success'
この場合オプティマイザは全表走査を実行します。!=を使用した時オプティマイザはインデックスを利用するアクセスパスを選択しないからです。

次の例はどうでしょう。
SELECT * FROM todos WHERE status IN ('failed', 'running')
このSQL文は

  1. status = 'failed'のレコードをインデックスを使って取得
  2. status = 'running'のレコードをインデックスを使って取得
  3. ①，②の結果を連結する

というインデックスを利用することを意図したものですが、実際は全表走査になります。なぜかというと、コストベースアプローチでは値が均等に分布していることが前提でした。なので'success', 'failed', 'running'は1/3ずつ均等に分布しているとオプティマイザは判断します。その場合全表走査の方がインデックスを使うより早く見つけることができるのでそのように判断されます。

ではどのようにすればいいのでしょうか？ヒント句と呼ばれるものを使用することでユーザがオプティマイザのアクセスパスの選択を制御することが出来ます。
ヒント句は以下のように書きます。
/*+ 内容 */
例えば今回の場合

SELECT /*+ USE_CONCAT INDEX(todos idx_status)*/ 
FROM todos 
WHERE status IN ('failed', 'running')

とすることでインデックスを使用したアクセスパスを選択させることが出来ます。詳しくはヒント句で検索してみてください。

アルゴリズムを使い分ける

ここまでみてきたようにオプティマイザによる最適化は万能ではありません。なのでパフォーマンスの低下を防ぐには、明示的にヒントをつけるなどプログラマがSQL文の書き方を工夫する必要があります。以下で特に速度に影響が出やすい結合処理をとりあげます。

結合処理には「ネストループ結合」「マージ結合」「ハッシュ結合」の三つのアルゴリズムがあります。これらについてみていきましょう。

ネストループ結合

ネスト・ループ結合は、単純に二重ループを回してテーブルを結合する方法です。例えば、AとBの二つのテーブルがあった場合、Aの各レコードごとにBの全レコードとの比較して、フィールドの値が一致するものを探します。
コストは２つのテーブルのレコード数の積に比例します。Bのレコードにインデックスが定義されている場合は、Bの検索にインデックスを利用することも出来ます。
インデックスの定義されていない小さなテーブルと、インデックスの定義された大きなテーブルを結合する場合に効果的です。

マージ結合

マージ結合は結合する２つのテーブルを予めソートしておきます。

テーブルA テーブルB
1 1
2 3
4 5
7 6
9 7
これにより検索する値を上から順番に見ていけば良いので、レコードの走査がA,Bそれぞれ1回ずつで済みます。
マージ結合の場合、テーブルのソートにかかるコストも考えなくてはなりません。しかし一般的にはネストループより低コストになります。

ハッシュ結合

ハッシュ結合は検索処理の部分にハッシュ法を使うことで高速化を図ります[4]。

まず，結合するフィールドの値をキーとして、テーブルBに対するハッシュ・テーブルを作ります。あとはテーブルAのレコードごとにフィールドの値が一致するものをハッシュ・テーブルから検索すれば、テーブルの結合が完成します。元のテーブルのサイズが大きいと作成したハッシュ・テーブルがメモリーに収まらないため、一般にはあらかじめテーブルをいくつかのパーティションに分割してから、パーティションごとにハッシュ結合を行います。

まとめ

これらの方法は一般的にネストループ→マージ→ハッシュの順で早いですが２つのテーブルの大きさが極端に異なるなど必ずしもこの順番になるとは限りません。
扱っているデータベースをよく見極めて選択する必要があります。

脚注

  1. 例えば一つのテーブルからデータを取り出すアクセスパスという方法では、先頭から順番に検索していく「全表走査」やインデックスを使う方法などがあります。 ↩︎

  2. 複雑なSQL文の場合は組み合わせが何千通りにもなることもあります。 ↩︎

  3. ROWIDは，テーブルの行を一意に識別するための識別子で，通常はファイル番号，ページ番号，およびそのページ内部でのエントリの番号からなります。なお，エントリの順番とページにレコードが格納される順番は必ずしも一致しません。 ↩︎

  4. ハッシュ法とは、データ探索アルゴリズムの一つで、対象となるデータから一定の手順で算出したハッシュ値を用いてデータ本体の代わりに比較に用いる方式。対象とするデータが長い場合に処理を高速化することができる。 ↩︎

Discussion