リレーショナルデータベースの仕組み (1/3) | POSTD

リレーショナルデータベースの仕組み (1/3)

リレーショナルデータベースが話題に挙がるとき、私は何かが足りないと思わずにはいられません。データベースはあらゆるところで使われており、その種類も、小規模で便利なSQLiteからパワフルなTeradataまで様々です。しかし、それがどういう仕組みで機能しているかを説明したものとなると、その数はごくわずかではないでしょうか。例えば「リレーショナルデータベース仕組み」などで検索してみてください。ヒット数の少なさを実感できると思います。さらにそれらの記事は短いものがほとんどです。逆に、近年流行している技術（ビッグデータ、NoSQL、JavaScriptなど）を検索した場合、それらの機能を詳しく説明した記事はたくさん見つかると思います。

リレーショナルデータベースは、もはや大学の授業や研究論文、専門書などでしか扱われないような古くて退屈な技術なのでしょうか？

logos of main databases

私は開発者として、理解していないものを使うのは好きではありません。データベースが40年もの間使われ続けてきたのには、それ相応の理由があるはずで、毎日使っているこの不可思議なブラックボックスを本当に理解するために、私は長年にわたって多くの時間を費やしてきました。リレーショナルデータベースは、便利で再利用可能な構想に基づいており、非常に興味深いものです。これをお読みの皆さんが、データベースを理解したいと思いつつも時間がなかったり、どこから手を付けていいか分からずに手をこまねいていたりするような場合には、きっとこの記事に興味を持っていただけると思います。

記事のタイトルをご覧いただければ分かるように、この記事の目的はデータベースの使い方を理解することではありません。そのため、記事の内容を理解するには、単純なJoinクエリや基本的なCRUDクエリを書けるくらいの知識は必要です。ただし、それさえ知っていれば、あとは私の方で説明します。

最初に触れるのは、時間計算量といったコンピュータ科学に関するものです。こういった概念はちょっと…という人がいるのは分かっていますが、これをやっておかないと、データベースの明晰さは理解できません。なお、テーマが大きいので、不可欠と思われるもの、つまり、データベースによるSQLクエリの処理方法に焦点を絞って進めます。データベースの背後にある基本の概念を紹介するので、記事を最後までお読みいただければ、実際に内部で何が起こっているのか、おおよその見当が付くようになるでしょう。

この記事はとても長く、多くのアルゴリズムやデータ構造に関する技術的な内容が含まれているので、最後まで読むにはある程度の時間が必要です。一部の概念については理解するのが難しいかもしれません。その場合、そこはスキップしてください。それでも大枠は理解していただけると思います。

内容についてもう少し具体的に説明しますね。大まかに分けて記事には3つのパートがあります。

低レベルと高レベルのデータベースコンポーネントの概要
クエリ最適化プロセスの概要
トランザクションおよびバッファプール管理の概要

1基本から
- 1.1O(1)) vs O(n2)
  - 1.1.1時間計算量の概念
  - 1.1.2時間計算量の例
  - 1.1.3踏み込んだ考察
- 1.2マージソート
  - 1.2.1マージ
  - 1.2.2分割段階
  - 1.2.3ソート段階
  - 1.2.4マージソートの威力
- 1.3配列、ツリー、ハッシュテーブル
  - 1.3.1配列
  - 1.3.2ツリーとデータベースインデックス
  - 1.3.3ハッシュテーブル
2全体の概要
3クライアントマネージャ
4クエリマネージャ
5データマネージャ
- 5.1キャッシュマネージャ
- 5.2トランザクションマネージャ
6終わりに

基本から

ずっと（遙か彼方の）以前には、開発者はコード内の処理数をしっかりと把握する必要がありました。CPUやメモリの無駄遣いでコンピュータの動作を遅くしないよう、アルゴリズムやデータ構造を頭に入れていたのです。

このパートでは、アルゴリズムやデータ構造の概念のいくつかについて話していきたいと思います。データベースを理解する上で不可欠な要素ですからね。また、データベースインデックスの考えについても触れるつもりです。

O(1)) vs O(n2)

今日、多くの開発者は時間計算量なんてものを気にしませんし、それはそれで間違ってはいません。しかし、大量のデータ（数千という話ではありません）を扱う場合やミリ秒を争うような場合、この概念を理解することは非常に重要です。そして、データベースというのは、上記の両方の状況を扱わなくてはなりません。話が長くなると退屈してしまうと思われるので、手短にその要旨をお伝えしますね。これは、後ほど出てくるコストベース最適化の概念を理解するのに役立ちます。

時間計算量の概念

時間計算量は、所定のデータに対してどの程度の時間をアルゴリズムが要するかを見るために使われています。この計算量を説明するためにコンピュータ科学者たちが使うのが、数学のO記法です。この表記は、所定の入力データに対してアルゴリズムに必要な処理数を説明する関数と共に使われます。

例えば、「このアルゴリズムはO(some_function())」と言う場合、それは所定のデータに対してアルゴリズムが完了するのに、some_function(所定データ量)の回数だけ処理が必要だということを意味します。

重要なのはデータの量ではなく、データが増えた時の処理数の増加の仕方です。時間計算量は確実な処理数を出すものではありませんが、大体の見当は与えてくれます。

time complexity analysis

この図は、異なる時間計算量の漸次的変化を示しています。グラフ表示には対数目盛りを使っているので、データの数は1から10億まで急速に増加しています。ここで分かるのは以下のことです。

O(1)または一定の計算量の場合は、一定のまま（そうでないなら、一定の計算量ではない）。
O(log(n))は、10億のデータ数でも低いまま。
最悪の計算量はO(n²)で、処理数は爆発的に上昇。
その他、2つの計算量も急激に上昇。

時間計算量の例

データ量が少ない場合、O(1)とO(n²)の違いはほんのわずかです。では、仮に2000要素の処理が必要なアルゴリズムがあるとしましょう。

O(1)アルゴリズムは1回の処理が必要
O(log(n))アルゴリズムは7回の処理が必要
O(n)アルゴリズムは2000回の処理が必要
O(n*log(n))アルゴリズムは14000回の処理が必要
O(n²)アルゴリズムは4000000回の処理が必要

O(1)とO(n²)の差は大きい(4000000倍)ですが、最大でも2ミリ秒ほど余分にかかるだけで、瞬き程度の時間差と言えなくはありません。実際のところ、現在のプロセッサは1秒で数百万の命令を処理できます。パフォーマンスや最適化が多くのITプロジェクトでそれほど問題にならないのは、これが理由です。

それでもやはり、前述の通り膨大な量のデータがある場合、この概念を知ることは重要です。例えば先のアルゴリズムが、今回は1000000の要素（データベースとしてはさほどの大きさではありません）を処理するとしましょう。

O(1)アルゴリズムは1回の処理が必要
O(log(n))アルゴリズムは14回の処理が必要
O(n)アルゴリズムは1000000回の処理が必要
O(n*log(n))アルゴリズムは14000000回の処理が必要
O(n²)アルゴリズムは1000000000000回の処理が必要

私は数学専攻ではありませんが、O(n²)アルゴリズムなら、1杯（ひょっとしたら2杯）のコーヒーブレイクは取れるでしょう。仮にデータ量があと1桁増えたら、長めの昼寝だって可能かもしれません。

踏み込んだ考察

参考までに。

優れたハッシュテーブル内の検索はO(1)で要素を取り出せる
バランスのとれたツリー内の検索は、O(log(n))で結果が取り出せる
配列内の検索は、O(n)で結果が取り出せる
最良のソートアルゴリズムはO(n*log(n))の計算量を有する
悪いソートアルゴリズムはO(n²)の計算量を有する

注：次のパートでは、これらのアルゴリズムやデータ構造を見ていきます。

時間計算量には複数のタイプがあります。

平均の場合のシナリオ
最良の場合のシナリオ
最悪の場合のシナリオ

時間計算量は往々にして、最悪の場合のシナリオであることが多いですね。

時間計算量についてのみ話していますが、計算量は以下の場合でも有効です。

アルゴリズムのメモリ使用量
アルゴリズムのディスクI/O使用量

もちろん、例えば次のようにn²よりもひどい計算量もあります。

n⁴：これはひどいです。以降で話すアルゴリズムの一部はこの計算量を有しています。
3ⁿ：さらいひどいです。記事の中頃に出てくるアルゴリズムの1つは、この計算量を有しています（そして、これは本当に多くのデータベースで使われています）。
nの階乗：データ量がどんなに少なくても、結果を得ることはできないでしょう。
nⁿ：この計算量に行き着いた場合、ご自身がITに向いているかどうか考えてみるべきかもしれません…

注：ここで提供したのはO記法の実際の定義ではなく、大枠のアイデアのみです。実際の定義についてはWikipediaに詳しいので、そちらをご覧ください。

マージソート

集合をソートする必要がある場合、あなたなら何をしますか。sort()関数を呼び出す？　確かに、それもいいですね。でも、データベースの場合、そのsort()関数がどのように作用するかを理解していなければなりません。

優れたソートアルゴリズムはいくつかありますが、中でも特に重要なものを1つ取り上げてみます。それがマージソートです。今の時点ではなぜデータのソートが役に立つのか分からないかもしれませんが、クエリ最適化に関するパートを読めば理解できるようになるはずです。また、マージソートについて理解することは、後ほど出てくるマージ結合と呼ばれるデータベースの一般的な結合処理を理解する上でも助けになるでしょう。

マージ

多くの便利なアルゴリズムと同様、マージソートもちょっとした仕掛けに基づいています。N/2のサイズのソート済み配列2つをN要素のソート済み配列にマージしても、N回の処理しか行われないのです。これがマージと呼ばれます。

どういうことか、簡単な例で確認してみましょう。

merge operation during merge sort algorithm

上の図を見ると、最終的に8要素がソートされた配列を構築するには、4要素の2つの配列を1回反復すればいいことが分かります。4要素の2つの配列が既にソートされているからです。

1）2つの配列の現状の要素を比較します（最初は1番目から）
2）次に、最小の要素を取り、8要素の配列に置きます
3）最小の要素を取った配列の、次の要素に移ります
一方の配列の最後の要素に到達するまで1、2、3を繰り返します。
もう一方の配列にある残りの要素を取り、8要素の配列に置きます。

これでうまくいくのは、4要素の2つの配列がソートされているため、これらの配列を「戻る」必要がないからです。

この仕掛けが分かったところで、マージソートの疑似コードを以下に示します。

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if
 
   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);
 
   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

マージソートは問題を小さな問題に分解してからその結果を求めることで、最初の問題の結果を得ます（注：このようなアルゴリズムは分割統治法と呼ばれます）。このアルゴリズムが理解できなくても心配いりません。私も最初は理解できませんでしたから。少しでも理解の助けになるように、このアルゴリズムを2段階のアルゴリズムと考えてみましょう。

配列を小さい配列に分割する分割段階
小さい配列を（マージを使って）より大きな配列にまとめるソート段階

分割段階

division phaseduring merge sort algorithm

分割段階では、配列が3段階で単一要素の配列に分割されます。何段階になるかはlog(N)で求められます（上の図の場合N=8、log(N)=3）。

どうしてそんなことが分かるのでしょうか。

私が天才だからです…というのは冗談で、数学のおかげです。各段階で、最初の配列のサイズが2で分割されていきます。つまり、配列を2で割れる回数が段階の数になります。これは対数の定義と完全に一致します（基数は2）。

ソート段階

sort phaseduring merge sort algorithm

ソート段階は、単一要素の配列から始まります。各段階でマージを複数回適用し、処理はN=8回になります。

ステップ1ではそれぞれ2回の処理を要するマージが4回発生します
ステップ2ではそれぞれ4回の処理を要するマージが2回発生します
ステップ3では8回の処理を要するマージが1回発生します

log(N)段階あるため、全体で必要な処理はN * log(N)回です。

マージソートの威力

このアルゴリズムはなぜそんなに威力があるのでしょうか。

理由：

新しい配列を作成するのではなく入力配列を直接修正する方法で、メモリの使用量を削減することができる。

注：このようなアルゴリズムはin-placeアルゴリズムと呼ばれます。

大きなディスクI/Oペナルティを発生させることなく、ディスク領域と少量のメモリを同時に使用するための修正ができる。この場合、現在処理されている部分のみがメモリにロードされます。これは、100MB程度のメモリバッファでギガバイト単位のテーブルをソートしなければならない場合に重要です。

注：このようなアルゴリズムは外部ソートと呼ばれます。

複数のプロセス/スレッド/サーバで実行するように修正できる。

例えば、分散マージソートはHadoop（ビッグデータの代表的なフレームワーク）の重要な構成要素です。

このアルゴリズムが「金の鉱脈」に変わる可能性がある（これは事実です）。

このソートアルゴリズムはほとんど全てのデータベースで使用されていますが、唯一のアルゴリズムではありません。より詳しく知りたい方は、データベースの一般的なソートアルゴリズムについて様々な考察が掲載されているこちらの研究論文をご覧ください。

配列、ツリー、ハッシュテーブル

時間計算量とソートの背景にある考え方について理解できたところで、3つのデータ構造について説明したいと思います。これらの構造は、モダンなデータベースの根幹となるので、理解しておきましょう。併せて、データベースインデックスの概念についても紹介していきます。

配列

2次元配列はシンプルなデータ構造で、テーブルは配列として見ることができます。例えば以下のようなテーブルです。

この2次元配列は行と列からなるテーブルです。

各行は、対象者を表している。
列はその対象者の特徴を表している。
各欄には、ある型のデータが保存される（整数や文字列、日付など）。

データを保存し、視覚化できたのは素晴らしいことですが、特定の値を探すには不便です。

例えば、UKで働く男性全員を探す場合、UKと記述されている行がないか、全ての行を確認しなければなりません。つまり、Ｎ回の処理（Nは行の数）が必要になるということです。これは悪いことではありませんが、他に速く処理できる方法はないのでしょうか？　そこでツリーの登場です。

補足：最近のほとんどのデータベースでは、ヒープ表や索引構成表のように、効率的にテーブルを保存するための高度な配列が提供されています。しかし、列のグループ内にある特定の条件を素早く探し出すという問題については、何も解決していません。

ツリーとデータベースインデックス

バイナリサーチツリーは、特殊なプロパティを持つバイナリツリーで、各ノードのキーは以下の条件でなければいけません。

左側のサブツリーに保存されているどのキーよりも大きい。
右側のサブツリーに保存されているどのキーよりも小さい。

視覚的に見ていきましょう。

例題

binary search tree

注釈：全てのノードには、結びついたテーブル内の行に向かってポインタがある。

このツリーには、N＝15個の要素があります。例えば、208を探し出したいとしましょう。

まず、キーが136である根ノードから始めます。136は208より小さいので、ノード136の右側のサブツリーを見ます。
398は208より大きいので、ノード398の左側のサブツリーを見ます。
250は208より大きいので、ノード250の左側のサブツリーを見ます。
200は208より小さいので、ノード200の右側のサブツリーを見ます。ですが、200の右側にはサブツリーがありません。つまり値が存在しないのです（値が存在するなら、200の右側にサブツリーがあるはずです）。

では次に、40を探してみましょう。

同様に、キーが136である根ノードから始めます。136は40より大きいので、ノード136の左側のサブツリーを見ます。
80は40より大きいので、ノード80の左側のサブツリーを見ます。
40は、私が探している40と等しいので、ノードが存在していることになります。このノードにある行ID（図には記載していません）を取り出し、その行IDのテーブルを確認します。
行IDが分かれば、テーブル上のどこにデータがあるのか正しい位置を知ることができ、簡単にデータを取り出すことができます。

結局、この2つの探索では、ツリー内で数回のレベルを踏むことになりました。

マージソートのパートを注意深く読んでいただければ、ここにlog(N)レベルがあることに気づくはずです。つまり、探索のコストはlog(N)となります。悪くないですね！

本来の問題へ

上記の探索は抽象的すぎるので、本来の問題に戻って考えてみましょう。退屈な整数はやめにして、前のテーブルで国名を表していた文字列を思い浮かべてください。テーブルに”国名”という列が含まれているツリーだと仮定します。

UKで働く人は誰なのかを知りたいとします。
その場合、UKを表すノードを得るためにツリーを見ます。
そうすれば、”UKノード”の中にあるUK労働者の行の位置を探すことができます。

配列を直接使えば、この探索はN回の処理ではなく、log(N)回の処理で済むことになります。今、あなたが思い描いたことこそがデータベースインデックスです。

キー（例えば列のグループ）を比較する関数があれば、列がどんなグループ（1つの文字列、1つの整数、2つの文字列、整数と文字列、日付など）であろうと、ツリーのインデックスを構築することが可能です。つまり、キー間の順序を決めることができるのです（これは、データベースのどんな基本的な型にも該当します）。

B+ツリーのインデックス

特定の値を1つ得るには、バイナリサーチツリーでも問題ありませんが、2つの値の間にある複数の要素を得たい場合は、大きな問題が生じます。この場合、ツリーにある各ノードを見なくてはならず、さらに、それが2つの値の間（例えば、ツリーの間順走査）なのかを確認しなくてはならないので、コストはO(N)となります。その上、ツリー全体を読み込まなければならないので、この処理はディスクI/Oに優しくありません。ですから、レンジクエリを効率的に行う方法を見つける必要があります。この問題を解決してくれるのが、B+ツリーです。最近のデータベースは従来のツリーから、修正版であるB+ツリーを使っており、以下の特徴を持っています。

最下層のノード（葉ノード）にのみ情報（結びついたテーブル上の行の場所）が保存される。
その他のノードは、探索の間、正しいノードにルートするためだけにある。

B+Tree index in databases

注釈：ノードには、結びついたテーブル内の行に向かってポインタがある。

また、各ノードはB+ツリー上の次の要素へのリンクも持っている。

見てお分かりの通り、さらに多くのノード（2倍）があります。追加されたノードである”ディシジョンノード”は、正しいノード（結びついたテーブル内の行の位置情報を保存する）を見つけてくれます。しかし、探索の時間計算量は依然としてO(log(N))です（階層は1つだけ増えます）。大きな違いは、最下層のノードは、それぞれ次の要素にリンクしているということです。

40と100の間の値を探すのであれば、B+ツリーでは以下のようになります。

バイナリサーチツリーと同じように、40の値を探します（40が存在しない場合は、40以上の値で近いものを探します）。
100になるまで、次要素への直リンクを辿ることを繰り返して、要素を集めていきます。

例えば、M個の次要素が見つかり、ツリーにはN個のノードがあるとしましょう。バイナリサーチツリーと同じように、特定のノードを探索するコストは、log(N)です。ですが、このノードが得られれば、次要素の直リンクを使ってM回の処理を行い、M個の要素を得られます。この場合の探索のコストは、M + log(N)回の処理 対バイナリサーチでのN回の処理となります。また、ツリー全体を読み込む必要はありません（M + log(N)のノードだけでいいです）ので、ディスクの使用量が少なくて済みます。Mの値が小さくて（200行など）Nの値が大きい（100万行）場合、これは大きな違いになってきます。

しかし、ここで新たな問題があります（またです！）。データベース（ひいては、B+ツリーのインデックスに紐づいたデータベース）の行を追加したり削除したりする場合、以下のことに注意しなくてはいけません。

B+ツリーにあるノード間の順序を保つ。そうしないと、ごちゃごちゃしたデータベースの中からノードを見つけることはできません。
B+ツリーで、極力少ない数のレベルを保つ。そうしないと、時間計算量O(log(N))がO(N)になってしまいます。

言い換えると、B+ツリーは、それ自身で順序を保ち、バランスを取らなくてはいけないということです。有り難いことに、これは高性能な削除、または挿入の処理で可能となります。しかし、これにはコストが伴います。B+ツリーの挿入と削除は、O(log(N))です。必要以上に多くのインデックスを使用することは賢明ではない、と聞いたことがある人もいるかもしれませんが、これがその理由です。データベースは、インデックス毎のO(log(N))回の処理と併せて、テーブルのインデックスを更新する必要があるため、テーブル上での行の挿入や更新、削除の速度が低下してしまうのです。それだけでなく、インデックスを追加するということは、トランザクションマネージャ（この記事の最後のパートで説明します）に対する負荷が増すことにもなります。

詳細については、Wikipediaの「B+木（ツリー）」を参照してください。データベースへのB+ツリーの実装例は、MySQLのメイン開発者が投稿しているこちらの記事とこちらの記事を読んでみるといいでしょう。どちらもinnoDB（MySQLのデータベースエンジン）がどのようにインデックスを扱うかについて言及しています。

補足：読者の方から教えていただいたのですが、低水準の最適化なので、B+ツリーは完全に平衡化されている必要があるそうです。

ハッシュテーブル

重要なデータ構造の最後は、ハッシュテーブルです。すぐに値を確認したいときなどにとても役立ちます。さらに、ハッシュテーブルを理解すれば、ハッシュ結合と呼ばれる一般的なデータベースの結合を理解するのが楽になります。このデータ構造は、また、内部のものを保存するデータベースとしても使われます（ロックテーブルやバッファプールなど。こちらの概念については、後でご紹介します）。

ハッシュテーブルとは、キーを利用して要素を素早く探すデータ構造の1つです。ハッシュテーブルを構築するためには、次に挙げる項目を定義する必要があります。

要素に対応するキー。
キーに対応するハッシュ関数。キーに対して算出されたハッシュが、要素の位置情報（いわゆるバケット）を示します。
キーを比較する関数。適切なバケットが決まり次第、この比較を利用して、バケット内で探索している要素を見つけ出す必要があります。

簡単な事例

次のような図で例を見てみましょう。

hash table

このハッシュテーブルにはバケットが10個あります。面倒なので図には5個しか表しませんでしたが、実際はもう5個加わっている図を思い描いてください。ここで使ったハッシュ関数は、各キーのmodulo10、となります。分かりやすく言うと、各要素が分類されるバケットを決めるために、要素の下1桁の数値だけをキーとして使うことにします。

下1桁が0の場合、その要素はバケット0に分類する。
下1桁が1の場合、その要素はバケット1に分類する。
下1桁が2の場合、その要素はバケット2に分類する。
以下同様。

この例では、単純に2つの整数間の等しさを比べる比較関数を使います。

では、78という要素を探すとしましょう。

ハッシュテーブルは、78に対するハッシュコードを8と算出。
比較関数がバケット8を探索。最初に見つかった要素は78。
78という要素を結果として返却。
探索にかかった処理数は2回のみ（ハッシュ値の算出に1回、バケット内で要素を探索するために1回）。

次は、59という要素を探してみましょう。

ハッシュテーブルは、59に対するハッシュコードを9と算出。
比較関数がバケット9を探索。最初に見つかった要素は99。この数値は探している要素59と異なるので、要素99は