WIP【備忘録】DBの論文を読む : 従来のRDBMSシステム

データベース

そろそろデータベースに関するちゃんとした基礎知識をつけたいという思いがあるので、Readings in Database Systems, 5th Edition を読んでいこうと思う。
URL: http://www.redbook.io/index.html

この本は、DB に関する古典的な論文から、近年の特に重要な論文まで、章ごとに短い解説とともに紹介されている。

今回は Ch2 従来のRDBMSシステム を読む。

紹介された論文

  1. System R: Relational Approach to Database Management. [System R: DB 管理へのリレーショナルアプローチ] (1976).

    • RDBMS の基礎を構築した論文

  2. The design of POSTGRES. [Postgres のデザイン] (1986)

    • ADT の実装に関する論文
  3. The Gamma Database Machine Project. [Gamma DB プロジェクト] (1990)
    • シェアードナッシングの普及・分散システム

解説を読んだ

この章では古典的な論文の中で特に重要な論文を時系列で３つ紹介している。
夫々の功績は色々あるが、例えば以下のようなものが挙げられている。

Postgres は今でも使っているが、この章と前章のデータモデルの論文を読むまで、ADT に関する貢献は知らなかった。何となく使いやすいからとかそんな理由だと思っていた...。

Gamma については名前すら聞いたことがなかった。シェアードナッシングの普及に貢献した論文ならしい。
分散システムの論文を読み慣れていない自分にはいい勉強になったと思う。

ただ、自分の知識不足がいけないんだけど、結局「今はこの実装/考え方はどうなの？」という疑問を終始脇に置きながら読んでしまった感がある。。。

論文 1 について

いつか書く。

論文 2 について

この論文では Postgres の予備設計について解説されている。

Postgres は以下の 6 つの目標を達成することを目指して設計された。

目標 1. 複雑なオブジェクトを使いやすくする
目標 2. ユーザー定義のデータ型や演算子・アクセス方法の提供
目標 3. アクティブなデータベース（アラートやトリガー等のルール処理）と、前向きおよび後向き連鎖を含む推論のための機能を提供
目標 4. クラッシュリカバリのための DBMS コードを簡素化
目標 5. 光ディスクや複数の密結合プロセッサで構成されるワークステーション、およびカスタム設計された VLSI チップを利用できる設計
目標 6. リレーショナルモデルにできるだけ変更を加えないように 1~5 を達成

VLSI って何？と思ったんだけど、weblio によればでっかい IC ぐらいの意味らしい。

1 チップ当たりの半導体素子の集積度が 10 万個を超える集積回路。LSI の集積度をさらに高めたもの。超大規模集積回路。
[補説] 1970 年代以降 1990 年代に至るまで、集積化技術の向上にともない、集積度が 1000〜10 万個程度の LSI、10 万〜1000 万個程度の VLSI、1000 万個を越えた ULSI が登場し、それぞれを区別したが、2000 年代になってからはこのような区別をせず、集積回路全般を LSI または IC と呼称することが多い。
https://www.weblio.jp/content/VLSI

設計目標の議論
目標１、２に関しては Ch1 のデータモデルの論文で詳しく説明されているのを見たほうがまとまっている気がする。
一言で言うなら、「ドメインに合ったデータ型を利用できるようにしたかった」という意図があった。
詳しくは補足を見てほしい。

目標３については、多くのアプリケーションはアラートとトリガーを使用してプログラミングを行うことが多いかららしい。

トリガー利用例

例えば、会社の部門テーブルと従業員テーブルがあったとする。部門テーブルのある部門のタプルを削除した時、更新がトリガーされて従業員テーブルからその部門の全ての従業員を削除するようにしたい。

目標４については、当時の殆どの DBMS は複雑なクラッシュリカバリコードを含んでいたが、目標２のユーザー定義のアクセス方法を実現するにはクラッシュリカバリのモデルも可能な限り単純で簡単に拡張できる必要がある。

目標５は、単純に可能な限り新しいテクノロジーに対応したかったからというもの。

目標６は、関係モデルが多くの人に利用されるため、できるだけ変更したくないというもの。

目標１，２に関する補足

この補足は、Ch1 で紹介されたWhat Goes Around Comes AroundのThe Object-Relational Eraに関する内容を元にしている。

INGRES の初期に、研究チームは次のような単純な GIS(地理情報システム)の問題に悩まされていた。

例えば、交差点の集まりの位置を保存したいとする。

こんな感じ。

Intersections (I-id, long, lat, other-data)

もしバウンディングボックス(bbox)の中にある全ての交差点を取り出そうとしたら SQL で書くとこうなる。

Select I-id  
    From Intersections  
    Where X0 < long < X1 and Y0 < lat < Y1

これは INGRES の B 木は１次元のアクセス方法だったので、このシステムではこの２次元の検索を効率よく行えなかった。

範囲内の Parcel(区画)を求めるクエリは更に次元が増える。

Parcel (P-id, Xmin, Xmax, Ymin, Ymax)  

Select P-id  
    From Parcel  
    Where Xmax > X0 and Ymax > Y0 and Xmin < X1 and Ymax < Y1

この様に、単純な GIS のクエリですら SQL で表現するのは難しく、標準的な B 木で実行すると性能も悪かった。

初期の RDBMS では、整数や浮動小数点・文字列をサポートしていたが、それは元々 IMS のデータ型であったことが主な理由であるし、B 木の採用も、ビジネスデータ処理で一般的な検索を容易にするためだった。

そのため、GIS のような他のドメインでは此等は正しいデータ型ではないし、B 木 が最適でもない。

このように、あるドメインに対応するためには、そのドメインに適したデータ型とアクセス方法が必要だ。
しかし、ドメインにはそれぞれのニーズがあるので夫々で事前に用意するより、自分の特定のニーズに合わせて DBMS をカスタマイズできるようにすべきだと考えた。

そして、その考えを元に目標１，２が掲げられた。

論文ではこの後、以下の項目について詳しく書いてある。気分が向いたらまとめようと思う。

補足：
目標１，２のための機能については軽くまとめた。
またもやWhat Goes Around Comes Aroundを参考にしている。

目標１，２を達成するため、Postgres の SQL エンジンには以下の汎用拡張機能が追加された。

  • ユーザ定義のデータ型
  • ユーザ定義の演算子
  • ユーザ定義の関数
  • ユーザ定義のアクセスメソッド

これらの機能を GIS で利用するには、以下のように定義を追加すれば良い。

  • データ型... 地理的な点と地理的な箱
  • 演算子(関数)... 「点が矩形にある(!!)」「箱が箱と重なる(##)」
Intersections (I-id, point, other-data)  
Parcel (P-id, P-box)  

Select I-id  
    From Intersections  
    Where point !! “X0, X1, Y0, Y1”  

Select P-id  
    From Parcel  
    Where P-box ## “X0, X1, Y0, Y1”

以上のようにユーザ定義機能を適切に利用すれば、Quadtrees や R-trees の等の多次元 index と組み合わせると、高性能な GIS DBMS を構築できる。わーい。

また、当時は各ベンダーがストアドプロシージャを導入するためにはエラーメッセージ処理や制御フローを実行するための「独自の（小さな）プログラミング言語」を定義する必要があったが、Postgres UDT と UDF はこの概念を一般化する事で従来のプログラミング言語で書かれたコードを従来の SQL クエリの処理中に呼び出すことができるようにした。らしい。

論文 3 について

Gamma の特徴

Gamma はアーキテクチャを数百のプロセッサに拡張できるように、以下の特徴を持つ。

  1. シェアードナッシングを採用している。
  2. すべての関係(relations)ば複数のディスク間で水平に分割(シャーディング)される。これにより、関係を並行にスキャンできるようになる。
  3. Hybrid Hash-Join を使用し、結合関数や集計関数などの複雑な関係演算子を実装している。
  4. データフロー スケジューリング手法を使用して、マルチオペレータクエリを調整する。

ハードウェア構成のセクションは特に気になるところはなかった。

Gamma のソフトウェア・アーキテクチャ

ストレージ構成

Gamma は relations を水平分割している。
これにより、DB は全ての I/O 帯域幅を活用できる。

水平分割と垂直分割の違いは以下の記事がわかりやすい。

Gamma のクエリ言語は分割方法としてラウンドロビン、ハッシュ、範囲分割を提供している。

この３つの方法は今でも主流っぽい。

また、この論文には「ディスクを持つ全てのノードの全ての relations をデクラスタリングするのは間違っていた」とある。
より優れたアプローチは、負荷分散と全体的な負荷軽減のバランスを取るために、完全なデクラスタリングではなく、可変のデクラスタリングをサポートする仕組みをつくることらしい。
(heat of relations を利用するらしい。関係の疎性とかデータの局所性の話?)

ところでシェーディングとデクラスタリングって同じってことでいいのか？

Gamma プロセス構成
Gamma を形成するプロセスの全体構成は下図。
各ホストのカタログマネージャは各 DB の概念/内部スキーマの中央リポジトリとして機能する。
(その際、各ユーザーがキャッシュしたコピー間の一貫性を保証する必要がある)
また、マルチサイトのクエリはスケジューラプロセスで管理される。
クエリにスケジューラプロセスを割り当てるには、中央のディスパッチプロセスを使用する。
一方で、オプティマイザがシングルサイトのクエリであることを検出したクエリは、スケジューラプロセスを経由せずに、適切なノードに直接送られて実行される。

それ以外の機能については想像がつくと思う。

f:id:sereronnrot:20210530233112p:plain
引用：The Gamma Database Machine Project.　 　

クエリ実行
VAX 版 Gamma のクエリオプティマイザを設計する際、オプティマイザが考慮する可能性のある実行計画のセットは、left-deep-tree のみに制限されていたらしい。これは、right-deep-tree 等をサポートするのに十分なメモリがなかったため。

演算子とプロセスの構造
全ての relational 演算子のアルゴリズムは、単一のプロセッサで実行されるよう記述された。
演算子プロセスへの入力はタプルのストリームであり、出力は分割テーブル(値と出力先プロセスのマッピング)と呼ばれる構造で多重化されたタプルのストリームである。
処理の流れとしては以下のようになる。

  1. プロセスの実行を開始
  2. 入力ストリームから連続的にタプルを読み込み
  3. 各タプルに対して演算を実施
  4. 結果として非れたタプルを分割テーブルで指定されたプロセスに転送
  5. 出力ストリームを閉じると、各出力先プロセスにend of streamメッセージが送信される

f:id:sereronnrot:20210530233150p:plain
引用：The Gamma Database Machine Project.　

f:id:sereronnrot:20210530233212p:plain
引用：The Gamma Database Machine Project.　

詳しくは論文を参照してほしいが、簡単に例を乗せる。
Figure5 の実行計画をディスクを持つ２つのプロセッサ(P1, P2)とディスクを持たない２つのプロセッサ(P3, P4)で構成される GammaDB で実行する場合の例が Figure6 だ。

f:id:sereronnrot:20210530233224p:plain
引用：The Gamma Database Machine Project.　

f:id:sereronnrot:20210530233239p:plain
引用：The Gamma Database Machine Project.　

Gamma は、クエリの実行に必要な制御メッセージの数がクエリに含まれる演算子の数の 3 倍と各演算子の実行に使用するプロセッサの数にほぼ等しい。
実際、Figure6 の P1,P3 のプロセスに対するスケジューラからの制御メッセージの流れは下図のようになる。

f:id:sereronnrot:20210530233248p:plain

クエリ処理のアルゴリズム
結合演算子以外は一言レベルでの記載にする。

選択演算子
全ての relations は複数のディスク上でシェーディングされているので、選択演算を並列化するにはディスクを持つ関連ノードの上で選択演算子を実行すれば良い。

集約演算子
集約関数は 2 つのステップで計算される。

  1. 各プロセッサはパーティションごとに値を計算して結果の一部を算出する。
  2. 各プロセッサは「group by」属性のハッシュ化により、部分的な結果を再分配する。

更新演算子（replace、delete、append 等)
標準的な手法で実装される。

結合演算子
Gamma がデフォルトで提供する並列結合アルゴリズムであるHybrid Hash-Joinは、結合される 2 つの関係(テーブル)を各タプルの join 属性にハッシュ関数を適用することにより、バケットと呼ばれる分離したサブセットに分割するというコンセプトに基づいている。

Gamma で実装されるアルゴリズムを理解するために、先ずはそのベースとなる集中型ハイブリッドハッシュ結合アルゴリズムを解説する。

集中型ハイブリッドハッシュ結合アルゴリズム
このアルゴリズムは３つのステップで実行される。
大きな結合が一連のより小さな結合に分割されるのを確認してほしい。

  1. ハッシュ関数を使用し、内側の（小さい）関係 R を N 個のバケットに分割する
    • 最初のバケットのタプルはメモリ内のハッシュテーブルを構築するために使用され、残りの N-1 個のバケットは一時ファイルに保存される
    • 小さい方の関係のサイズがバケットの数を決定する
  2. ステップ 1 のハッシュ関数を使って関係 S を N 個のバケットに分割する
    • ここでも
    • 最初のパケットは手順１で作成したハッシュテーブルと直ちに probe し結合する
    • 残りの N-1 個は一時ファイルへ
  3. アルゴリズムは関係 R からの残りの N-1 バケットを関係 S からのそれぞれのバケットに結合する

Gamma で実装される並列アルゴリズムは、上記の手順について、

  • パーティション分割テーブルにより、各論理バケットを夫々ディスクサイトに分割
  • ジョイニング分割テーブルにより、タプルをそれぞれのジョイニング・プロセッサ（これらのプロセッサには、必ずしもディスクが接続されている必要はない）にルーティングし、結合フェーズを並列化

等の仕様追加が行われている。

Figure8 は、関係 R が k 個のディスクサイトで N 個のバケットに分割され、最初のバケットが m 個のプロセッサで結合される様子を示している。

f:id:sereronnrot:20210530233259p:plain
引用：The Gamma Database Machine Project.　

トランザクションと障害の管理
Gamma がトランザクションと障害管理のために使用している機構について説明されている。

同時実行制御
Gamma の同時性制御は、2 相ロックに基づいている。
詳しくは論文参照。
2 相ロックの説明自体は以下の記事がわかりやすい。

リカバリ機構とログマネージャ
オペレータプロセスがレコードを更新する時、DB の状態変化を記録するログレコードが生成される。
これらのログレコードには、ノード番号とローカルのシーケンス番号で構成されるログシーケンス番号（LSN）が関連付けられている。
ログレコードは、クエリプロセッサから 1 つ(或いは複数の)ログマネージャに送信され、ログマネージャは受信したログレコードを結合して 1 つのログストリームを形成する。

詳しくは論文参照。

MEMO: WAL

障害の管理
TODO:書く。