この投稿はPostgreSQL Advent Calendar 2013の8日目の記事です。

前回の記事では、PostgreSQLのご先祖様であるリレーショナルデータベースシステムINGRESについて、文献からわかる史実を元に(多少の脚色を加えて)その歴史的な側面をご紹介しました。

今回の記事では、1976年に発表された論文 "The design and implementation of INGRES" をもとに、INGRESの技術的な側面に注目してみたいと思います。

クエリ言語QUEL

リレーショナルデータベースでは、それ以前のナビゲーショナルデータベースとは異なり、どんなデータが欲しいかwhatを記述するだけで、具体的にどのようなデータ構造やアルゴリズムが実装されているかを一切知る必要なくデータを取得することができる、というのが大きなウリの一つです。そのwhatを記述するための言語がクエリ言語です。皆さんのよく知っているSQLもクエリ言語の一つです。

INGRESプロジェクトでは、クエリ言語としてQUELが開発されます。リレーショナルモデルに併せて Codd はDSL/APLHAというクエリ言語を1971年に発表しているのですが、DSL/ALPHAは数学的な表記(DSL/ALPHAは関係演算(relational calculus)をベースとして、量化子 ∃, ∀ や、論理演算の記号 ¬, ∧, ∨ などがほぼそのまま用いられていました)に基づいておりやや一般的にわかりやすいものではありませんでした。QUELはDSL/ALPHAをベースとして、数学的な表記のない やさしい クエリ言語として設計されました。

QUELがどんな言語なのか、簡単なサンプルコードをみてみましょう。

RANGE OF C IS CITY
RETRIEVE INTO W(C.CNAME,
                      DENSITY = C.POPULATION / C.AREA)
         WHERE C.STATE = 'California'
           AND C.POPULATION > 50000

このサンプルコードでは、カリフォルニア州にある人口5万人以上の市について、市の名前と人口密度の一覧を取得するという処理を行っています。一行目のRANGE文では、処理の対象としてCITYリレーションを選択して、CITYリレーションのタプルを表す変数名Cを宣言しています。二行目のRETRIEVE文は、SQLでいうところのSELECT文に相当します。処理の結果は、一時テーブルとして作成されるWに保存されます。細かい表記の違いを別にすると、現在使われているSQLとそれほど大きな違いがないことがわかると思います。

クエリ実行方式

1975年に発表された時点で、INGRESは複数のリレーションの結合を含むクエリをサポートしています。

データベースシステムをある程度使い込んだことがある人ならば、「ネステッドループ結合(ジョイン)」や「ハッシュ結合(ジョイン)」という言葉を聞いたことがあると思います。データベースの性能チューニングをやったことがある人は、クエリの実行プランを眺めてハッシュジョインが走るようにパラメタを調整して…なんていう記憶もあるのではないでしょうか。

当時のINGRESにおいては、今で言うネステッドループ結合が実装されていました。INGRESにおけるネステッドループ結合は、実は現在のデータベースシステムにおけるネステッドループ結合とアルゴリズムとしてはほとんど同じです。

では、INGRESの具体的なクエリ処理エンジンの構造を概観してみましょう。INGRESのクエリ処理エンジンは One Variable Query Processor (OVQP) と呼ばれています。日本語にすると「1変数クエリ処理エンジン」ということになります。前節のクエリの例で RANGE 文でリレーションに対して変数を宣言していましたが、「1変数クエリ処理エンジン」の「変数」とはこのリレーションを表す変数のことを指します。つまり、「1変数クエリ処理エンジン」とは同時にひとつのリレーションのみを処理することができるクエリ処理エンジンということです。

それじゃあ複数のリレーションの結合ができないじゃないか、と思われるかもしれません。複数のリレーションの結合とは、つまり複数の変数が組み合わさったクエリになるからです。このようなクエリを処理するために、INGRESでは事前に1つの複雑なクエリを、複数の1変数クエリに分解して、OVQPに放り込んで処理してゆきます。例を追いながらその処理を追いかけてみましょう。

RANGE OF E, M IS EMPLOYEE
RANGE OF D IS DEPT
RETRIEVE (E.NAME)
   WHERE E.SALARY > M.SALARY AND
            E.MANAGER = M.NAME AND
            E.DEPT  = D.DEPT AND
            D.FLOOR# = 1 AND
            E.AGE > 40

このクエリでは、EMPLOYEE(従業員)リレーションとDEPT(部門)リレーションが定義されているデータベースから、1階で働いていて、年齢が40歳より上で、マネージャーより給料が高い従業員のデータを抜き出す、という問い合わせを行っています。

Step 1.

クエリが1変数かどうかを判定→3変数なので分解する

Step 2.

次の2つのクエリを実行

(1)
RANGE OF D IS DEPT
RETRIEVE INTO T1(D.DEPT)
   WHERE D.FLOOR# = 1

(2)
RANGE OF E IS EMPLOYEE
RETRIEVE INTO T2(E.NAME, E.SALARY, E.MANAGER, E.DEPT)
   WHERE E.AGE > 40

こうすると、一時リレーションT1、T2を使って最初のクエリは次のようになります。

RANGE OF D IS T1
RANGE OF E IS T2
RANGE OF M IS EMPLOYEE
RETRIEVE (E.NAME)
   WHERE E.SALARY > M.SALARY AND
            E.MANAGER = M.NAME AND
            E.DEPT  = D.DEPT

Step 3.

データ数の少ない一時テーブル、ここではT1を変数置換用のリレーションとして選択

Step 4.

T1の各タプルについて、元のクエリ中の変数Dをタプルの値で置き換える

RANGE OF E IS T2
RANGE OF M IS EMPLOYEE
RETRIEVE (E.NAME)
   WHERE E.SALARY > M.SALARY AND
            E.MANAGER = M.NAME AND
            E.DEPT  = [value].DEPT

これで元は3変数だったクエリが2変数になりました。

変数を値で置き換えたクエリが1変数でない場合には、Step 1. にもどって同じ手順を繰り返すことで、クエリ処理を複数の1変数クエリへと分解してゆくことができます。

アクセスメソッド

アクセスメソッドとは、その名の通りデータベースに保存されているデータにアクセスするための方法です。 PostgreSQLでいうところの、Seq Scan や Index Scan、Bitmap Index Scan などがそれに相当します。

アクセスメソッドには様々な実装方法があり、それぞれが得意とするデータアクセス、苦手とするデータアクセスのパターンがあります。データベースシステムのように総合的なデータの管理を行うためのシステムでは、複数のアクセスメソッドを利用できる必要があります。

INGRESでは、アクセスメソッドの共通インターフェースが定められています。INGRESで標準的に提供されるアクセスメソッドはすべてこのインターフェースを介して提供されており、またこのインターフェースに従って実装することで独自のアクセスメソッドを追加することができるように設計されています。

PostgreSQL本体のソースコードを追ったことがある人であればわかると思いますが、PostgreSQLではストレージアクセス、テーブルアクセス、メモリ管理コンテクストなど、様々なモジュールに関して共通インターフェースが規定されており、PostgreSQLの標準実装もそのインターフェースの一実装として提供される、という形をとっています。このような汎用性・拡張性に富んだPostgreSQLのソフトウェアアーキテクチャは、実はご先祖であるINGRESの頃から採用されていたことをうかがい知ることができます。

ちなみに、INGRESで定められているアクセスメソッドインターフェースは次の通りです:

OPENR(descriptor, mode, relation_name)
GET(descriptor, tid, limit_tid, tuple, next_flag)
FIND(descriptor, key, tid, key_type)
PARAMD(descriptor, access_characteristics_structure)
PARAMI(index_descriptor, access_characteristics_structure)
INSERT(descriptor, tuple)
REPLACE(descriptor, tid, new_tuple)
DELETE(descriptor, tid)
CLOSER(descriptor)

OPENR と CLOSER はプログラマにとってはファイル操作等でお馴染みのインターフェースでしょう。OPENR で指定したリレーションを開き、リレーションのディスクリプタを取得します。以降、このリレーションに対するアクセスはこのディスクリプタを以って行われます。一連のアクセスが完了した後は、CLOSER によってリレーションを閉じます。

GET は、タプルID(tid)をキーとしてタプルのデータを取得するための関数です。tidでタプルIDの下限を、limit_tidでタプルIDの上限を指定することができ、GETが呼び出されるとこの条件にマッチする最初のタプルを見つけてきて、そのデータを tuple に書き込みます。また、next_flagにTRUEを指定してGETを呼び出した場合には、次にマッチするタプルのIDをtidに書きこむため、連続してタプルを読みだしてゆくことができます。

FINDは、keyで指定した検索キーにマッチするタプルIDを取得するための関数です。key_typeで完全一致検索、範囲検索などの検索モードを指定することができます。

PARAMD、PARAMIはFINDにおいて利用可能な検索キーの種類や、検索モードを調べるための関数です。それぞれ、データのリレーションと、索引のリレーションに利用されます。

INSERTはタプルを挿入するための関数、REPLACEは既に存在するタプルを更新するための関数、DELETEはタプルを削除するための関数です。

まとめ

今回の記事では、INGRESの技術的な側面に焦点を当てて、クエリ言語、クエリ実行方式、そしてアクセスメソッドについて紹介しました。今からおよそ40年ほど前に開発されたINGRESですが、実はその特徴の多くが現在のPostgreSQLに受け継がれていることが（PostgreSQLのコードを読んだことがある人には）分かったと思います。今でも次々と新しい機能が追加されて進化しながらも、これだけの歴史が今動くコードから感じられるソフトウェアというのは、世の中にもそう多くは存在していないのではないでしょうか。これを機にPostgreSQLのソースコードリーディングに挑戦してみてはいかがでしょう。

Everyday Deadlock

PostgreSQL誕生以前 -INGRESの技術-