「ITエンジニアのためのデータベース再入門」 第4章 DBMSの内部構造

(リレーショナル理論とかは飛ばして、まず内部構造の部分からノート。)

第4章 DBMSの内部構造

現代のRDBMSは与えられたSQLからアクセスするデータ量、データの分布、インデックスやパーティショニングの有無などから自動的にデータ取得アルゴリズムを決定する。(SQLは宣言的な言語。「こういうデータを取得」は含まれているが、「こうやってデータを取得」は含まれていない。)

DBMSは次のように処理をすすめる。

SQLを構文解析 → オプティマイザが実行計画を作成 → 実行エンジンが実行計画に基づいてデータを取得 → 表示

SQLの解析〜動作

まずはSQLの実行計画をみてみよう。SQLの前に EXPLAIN 句をつけると表示できる。主に注目したいのは

  • インデックススキャン/テーブルスキャンどちらをつかっているか
  • 結合に使う手法として何を使っているか(ネステッドループ、ソート/マージ、ハッシュ)

インデックス(本書には書いてないけど、調べたので補足)

インデックスはテーブルから高速にデータを取り出すための仕組み。インデックスが存在しない場合、毎回すべてのレコードを走査する必要がある。

インデックスは1つのカラムだけで作ることもできるが、複数のカラムを組み合わせた複合インデックスも定義可能。複合インデックスを使うときは、その複合インデックス定義に使った順番でカラムを検索に使う必要がある。順番さえ守っていれば、すべてのカラムを使わずに途中まででもインデックスは使われる。(飛ばすのはNG)

よく使われるインデックスには次のようなものがある。

  • B-Treeインデックス

B-Treeを使ったインデックス。構造上、カーディナリティの高い(=特定のキーが偏って現れたりせず、「バランス良く」現れている)場合に有効である。(Balancedだけに?)

  • ハッシュインデックス

ハッシュ関数を使い、キーの値とレコードを含むページを直接結びつける。範囲検索には使うことができない。ハッシュ関数を自前で定義することで、性能のチューニングが行いやすい。

  • ビットマップインデックス

キーのとりうる値が限られている(=カーディナリティが低い)場合、各値に対して「n番目のレコードがその値を取るのであれば1,そうでなければ0」というビット列を作る。操作時は、このビット列を読み、1が現れた位置のレコードを取得する。

どの場合も、インデックスの作成・更新にはコストがかかる。このため、使わないインデックスを定義するのは挿入更新を遅くするだけである。

結合

JOIN を実現するアルゴリズムは3種類。

  • ネステッドループ結合

T1とT2、2つのテーブルがあった場合、T1の各レコードに対してT2の全レコードとの比較を行う。そして結合項目の値が一致しているものを探す。コストはT1、T2それぞれのレコード数の積に比例する。

T1がインデックスのない件数の少ないテーブル、T2がインデックスの定義されている件数の多いテーブルである場合に有効。

  • ハッシュ結合

ネステッドループ結合のようにT1のレコード一件ごとにT2のレコードと比較を行う。このとき、結合する項目の値をキーとしてT2に対するハッシュテーブルを作成しておく。すると、全件を走査する必要がなくなり、高速になる。

ただし、元のテーブルのサイズが大きいとハッシュテーブルがメモリ上に収まらないため、事前にパーティショニングを行う必要がある。

つまり、ネステッドループ結合に比べたら時間計算量は減るが空間計算量が多い。

  • ソート/マージ結合

結合キーによってあらかじめT1,T2をソートしておく方法。両方のテーブルのレコードに対してポインタを上から下へ動かすだけ。つまりレコード操作はたった一回で済む。

あらかじめソートされていない場合は、ソートのコストも考える必要がある。

一般的に速度は ハッシュ結合 > ソート/マージ > ネステッドループ の順になるといわれる。しかし、レコード数やインデックス定義の有無など個別のケースによっても速度は変わる。

トランザクション

いくつかの操作をひとまとめにした手続きの単位がトランザクション。トランザクションが途中まで実行されて、中途半端にデータが更新されることはあってはならない。トランザクションはコミットされる(トランザクションに含まれる更新がすべて反映される)かロールバックされる(トランザクションに含まれる更新がすべて破棄される)のどちらか。

ACID特性

A: Atomicity トランザクションはすべて行われるかすべて破棄されるかのいずれかである C: Consistency トランザクションはデータの一貫性を維持する I: Isolation 同時に実行されるトランザクションはお互い影響を受けない D: Durability コミットされたトランザクションはシステム障害が起きても保証される

RDPのトランザクションはACID特性を備えている必要がある

CAP定理

C: Consistency 整合性 A: Availability 可用性 P: Partition 分断耐性

この3つをすべて兼ね備えることはできない。RDBはCA、NOSQL系DBはCPまたはAPをもつ。