A History and Evaluation of System R

July 3, 2021

System Rは、1970年に発表されたリレーショナルモデルを実装した初めてのリレーショナルデータベースである。 1981年に発表された表題の論文は、System Rの開発プロジェクトを3つのフェーズに分け各フェーズごとにえられた知見をまとめている。 Phase 0は、74年から75年にかけて、シングルユーザ向けにSQLサブセットと対話的なインターフェースを開発した期間にあたる。 Phase 1は、76年から77年の、Phase 0のコードを破棄し、マルチユーザに対応しSystem Rの機能を完全に実装するまでの期間である。 Phase 2は、78年から79年にSan Jose Research Laboratoryなどでの実用にもとづく評価期間にあたる。

Phase 0で開発されたインターフェースは、スタンドアローン環境のシングルユーザ向け対話型ターミナルである。実行できるSQLは限定的で、例えばJOINはサポートされていない。リレーショナルデータへのアクセス方法には、レコードをドメインごとに分けた領域に保存するXRMを採用した。 XRMの構造を以下に図示する。 XRMは、リレーションを32ビットのID(TID)をもつタプルで保存する。 TIDはページ番号を含み、タプルにはドメインへのポインタを保存する。 xrm

Phase 1では、アクセス方法がXRMからRSS(Research Storage System)に変わった。 XRMの問題は、処理性能や最適化の複雑さであった。例えば、TIDのリスト操作が高コストであり、取得するタプル数よりもI/O数の方がコスト予測材料に適し、IOだけでなくCPUネックのタスクもあることからCPUとI/Oの加重合計によるコスト予測が望ましいことがわかった。

アクセス方法を変えた一方で、アクセス方法(XRM, RSS)とSQLのオプティマイザ(RDS, Relational Data System)を別のモジュールにし、2つの機能を疎にしてリレーショナルデーターベースを実装することは変わらない。 RSSとRDSの内部に新しく追加した機能もまた、モジュールとして別モジュールと密結合しないように実装された。マルチユーザに対応したことで実装されたロックとリカバリのためのロギングはどちらもRSS内で分離されている。同じく認証機能とアクセス経路を選択するモジュールもRDS内で独立したモジュールからなる。

XRMではレコードをドメインで分解して保存したのに対し、RSSはレコードのままデータベースに保存する。レコードごとの物理的な位置が局所化し、リレーションの取得に必要なI/O回数を削減できた。レコードへのアクセス手段は3つあり、B-treeをもちいたindex scan, indexを使わず物理的なテーブルの配置に沿った走査、レコードに保存されたポインタで別のレコードを参照する方法がある。

オプティマイザはI/O回数とRSSの呼び出しを最小化する。最適化のために、XRMがTIDのリストの操作を最適化するのに対して、RSSはインデックスでアクセスパスを最適化する。 RSSは存在するならインデックスを一つ選び、インデックスによるテーブル検索の高速化をはかる。 Phase2から実装されたJOINの手段は2通りある。一つは、一方のテーブルの行を特定した後で他方のテーブルの行を特定する。他方は、JOINのフィールドで両テーブルをソートし順にレコードを比較してマージする。オプティマイザは、この2つの方法から最適な方選ぶ。インデックスがあるときは前者を、ないときは後者を選びやすい。

ロック機構は、Phase 1の当初、レコードの値を条件にロックするレコードを指定する仕組みだった。しかし、条件の充足判定の難しさと処理時間の長さから、粒度の異なるロックを使う手法に変わった。新しいロック機構は、レコードに対する複数のロックをテーブルのロックと交換することができ、粒度の大きいロックへの交換をブロックすることで、トランザクションを別のトランザクションから保護する。

論文をこちらからダウンロードできます。画像を論文から引用しました。