SELECTのAPI(1) 概要

Koherent_DB

SQLと言えばまずはSELECT文です。ということで、最初にSELECT文相当の検索用APIを考えたいと思います。

例で使うテーブル

以下、次のようなテーブルがあるものとして話を進めます。

members: メンバーを格納したテーブル。
member_id family_name first_name age sex group_id
1011 中田 祐輔 22 0 1
1234 山下 沙希 17 1 2
1999 宮川 崇 18 0 2
2112 石田 菜々 21 1 1
2345 山崎 千佳 19 1 1

どのようにしてSELECTを行うか

SQLのSELECTは柔軟性に富んでおり、多様な操作を受け付けます。特に、結合やサブクエリをどのように扱うかということはよく考えなければなりません。PerlShellKoherent::DBのAPIでは、テーブルもクエリの結果もすべてKoherent::PerlShell::Tableクラスのインスタンスとして扱うことでこれを解決しようと思います。

RDBでは、SELECTにおけるインプットとアウトプットの両方を表として表すことが出来ます。例えば、

-- 成人のメンバーを取得 - クエリA 
SELECT * FROM members WHERE age >= 20;

というクエリのインプットは上記のmembersテーブルであり、アウトプットは下記のような表となります。

member_id family_name first_name age sex group_id
1011 中田 祐輔 22 0 1
2112 石田 菜々 21 1 1

これは複雑な結合やサブクエリに関しても言えることです。次のようなサブクエリを用いたSELECT文の場合でも、テーブルをインプット／アウトプットとする2段階の問い合わせと考えられます（例なので冗長なサブクエリになっていますが、目を瞑って下さい）。

-- 男性のメンバーを取得 - クエリB
SELECT * FROM (
    SELECT member_id, family_name, first_name,
           CASE WHEN sex = 0 THEN '男' ELSE '女' END AS sex_text
    FROM members
) WHERE sex_text = '男';

この場合、1段階目のインプットはmembersテーブルでそのアウトプットは次のようになります。

member_id family_name first_name sex_text
1011 中田 祐輔 男
1234 山下 沙希 女
1999 宮川 崇 男
2112 石田 菜々 女
2345 山崎 千佳 女

これがそのまま2段階目のインプットとなり、最終的なアウトプットは次のようになります。

member_id family_name first_name sex_text
1011 中田 祐輔 男
1999 宮川 崇 男

このように表をインプット／アウトプットと考えれば、サブクエリを特別なものとして扱わなくても単純なSELECTの繰り返しと考えられます。

コードの例

PerlShellKoherent::DBで上記のようなSELECT文をどのように書くかを考えて見ます。

上記クエリAは、例えば次のようなコードで書けるでしょう。

# 成人のメンバーを取得 - クエリA相当
my $adults = $members->where(sub{
    my $row = shift;
    $row->{'age'} < 20;
});

このとき、$members、$adultsともにTableオブジェクトとなります。同様にクエリBは次のようなコードになります。

# 男性のメンバーを取得 - クエリB相当

# 1段階目
my $mid_result = $members->select(
    'member_id', 'family_name', 'first_name',
    ['sex_text', sub{
        my $row = shift;
        $row->{'sex'} == 0 ? '男' : '女';
    }]
);

# 2段階目
my $men = $mid_result->where(sub{
    my $row = shift;
    $row->{'sex_text'} == '男';
});

上記のコードを一つにまとめて、次のように書くこともできます。

# 男性のメンバーを取得（一つにまとめた場合） - クエリB相当
my $men = $members->select(
    'member_id', 'family_name', 'first_name',
    ['sex_text', sub{
        my $row = shift;
        $row->{'sex'} == 0 ? '男' : '女';
    }]
)->where(sub{
    my $row = shift;
    $row->{'sex_text'} == '男';
});

このようにSELECTの結果をTableオブジェクトとして扱うことで、サブクエリのような複雑な問い合わせに対しても独自にメソッドを用意せずに対応できそうです。

実際には、テーブルに対してはUPDATEやINSERT、DELETEなどを行うことができますが、SELECTの結果に対してはSELECTしか行うことができないため、これらを区別する必要があります。そのため、SELECTしか行えない表をKoherent::PerlShellDB::Viewクラス、テーブルはそれを継承したKoherent::PerlShellDB::Tableクラスとして扱おうと思います。

まとめ

SELECTのインプット／アウトプットは表と考えられるため、テーブルもSELECTの結果もKoherent::PerlShellDB::Viewクラスで扱います。更新が可能なテーブルには更新用のメソッドを用意する必要があるため、Viewクラスを継承したKoherent::PerlShellDB::Tableクラスとして扱います。

実装の方針

Koherent_DB

併せて、方針変更についてもご覧下さい。
(2009-10-16)

RDBMSの実装においては、次のような要素がキーになると思います。

これらについて実装の方針をまとめておきます。

インデックス

PerlShellKoherent::DBではB木*1によるインデックスを実装しようと思います。

B+木*2やB*木*3で実装した方がいいのでしょうが、実装が面倒そうですし、インデックスを抽象化して作っておけば後から差し替えられます。気が向けばハッシュインデックスも実装するかもしれません。

キャッシュ

キャッシュはDBのパフォーマンス上重要ですが、今回はまずは動くものを作ろうと思うので、キャッシュは動いた後で実装しようと思っています。LRU*4では同時アクセス数が増えたときにパフォーマンスが落ちてしまうようなので、CLOCK*5で実装する予定です。

トランザクションと同時実行制御

PerlShellKoherent::DBでは、まずはMySQLのMyISAMのような、トランザクションはサポートせずテーブルロックするような仕様で作ろうとおもいます。でももしかするとトランザクションのサポートをにらんでMVCCみたいな実装をするかもしれません。

テーブルやビューの結合

結合ができないとRDBになりません。結合方式はNested Loop Joinを考えています。Nested Loop Joinは外部表（駆動表）で件数を絞った後に結合を行う場合には高速な結合方式です。

しかし、外部表M件、内部表N件いの全件を結合しようとすると、Nested Loop Joinではインデックスが有効な場合でもO(M log N)になってしまうため、全件結合時にO(M + N)で結合可能なHash JoinやSort-Merge Joinの実装も検討中です。ただ、PerlShellKoherent::DBで大量データの全件結合を行うと吹っ飛んでしまいそうですし、数件の検索しかおこなわないのであればNested Loop Joinのみの実装でも良いように思います。

SQLやAPI

通常のRDBMSではDBにアクセスする手段としてSQLを用いるわけですが、PerlShellKoherent::DBでは今のところSQLをサポートしない予定です。

SQLをサポートするには構文解析が必要になりますが、これを本気で行うのは短期間では苦しいですし、DBの本質でもありません。代わりに、DBを操作するAPIを提供します。APIのイメージを作らずに他の実装を始めると、やりたいことが実現できていなかったり、不必要な実装を行ったりしてしまい、後々困ったことになりそうなので、まず初めにこのAPIから作り始めたいと思います。

実行計画とオプティマイザ

上記APIではインデックスの使用などを完全に指定する方式を採るため、実行計画を組み立てたり、オプティマイザを実装したりはしません。SQLをサポートするとなれば必要なので、そのときには実装することになるでしょう。

*1:http://ja.wikipedia.org/wiki/B%E6%9C%A8

*2:http://ja.wikipedia.org/wiki/B%2B%E6%9C%A8

*3:http://ja.wikipedia.org/wiki/B*%E6%9C%A8

*4:http://ja.wikipedia.org/wiki/Least_Recently_Used

*5:http://en.wikipedia.org/wiki/Page_replacement_algorithm#Clock

PerlShell

Koherent_DB

もろもろの事情でKoherent::DBに改名することにしました。
(2009-11-24)

という名前にすることにしました。これから実装するRDBMSを。

やはり名前がないと不便ですし、名前は必要です。

名前の由来

名前の由来は「pearl shell（真珠貝）」です。

  1. Perlは元々pearl（真珠）から名付けられた*1
  2. 真珠が入っているのは真珠貝
  3. Perl（で作ったデータ）を入れておくものはPerlShell

というわけで、これからはPerlShellと呼ぶことにします。

*1:http://ja.wikipedia.org/wiki/Perl#.E5.90.8D.E7.A7.B0

Pure PerlのRDBMSを作る

Koherent_DB Perl

今日からブログを書くことにしましたkoherです。

突然ですが、Pure PerlのRDBMSを作りたいと思います。

自己紹介

某ITコンサルに勤めていましたが、より技術的なことに取り組みたいと思い、退職して大学院に戻ろうと考えています。8月でプロジェクトがひと段落したこともあり、会社にも退職の意思を伝えて現在休暇中です。

はてなでアルバイトがしたい

大学院に戻るといっても生活費は稼がなければなりません。せっかくならスキルアップにもつながる会社でアルバイトができればと思ってさがしている際に、はてながアルバイトの求人をしていることを知りました。はてなであれば技術的なこだわりもありそうですし、一度WEB系の会社を内側から見てみたいという思いもあったのではてなに応募してみることにしました。

なぜPerlでRDBMSを作るのか

はてなで最もよく使われているプログラミング言語はPerlのようです。これまで、Java、C、JavaScript、PHP、ActionScriptなどを触ってきましたが、Perlはおそろしいほど経験がありません。大昔に本を見ながら簡易掲示板のCGIを作っただけです。もはや、変数に$をつけることしか覚えていませんでした。

はてなの求人のページには

求められる知識/経験

http://www.hatena.ne.jp/company/staff/applicationengineer

とありますが、さすがにPerlは書けませんでは通用しないと思います。ですので、一からPerlを勉強することにしました。

しかし、ただ勉強するだけではおもしろくありません。それに、本やWEBを読んでいるだけでは身に付きません。練習がてらPerlを書くのであれば、せっかくなので前々から作ってみたいと思っていたRDBをPerlで書いてみることにしました。

はてなのWEBアプリケーションエンジニアに応募するならWEBアプリでも作った方が良いように思えるかもしれません。もちろん、PerlでWEBアプリも書いてみようと思います。GETやPOST、Cookie、セッションの扱い方、MemcachedやDBアクセスの方法（DBIx::MoCoなんかも）、テンプレートエンジンくらいはおさえておきたいところです。ただ、WEBアプリはあまり複雑な処理を行わないことが多いのでプログラムも定型的になってしまい、言語の勉強としてはベストでないように思います。

それに、勉強の過程をブログに記すのに、題材がWEBアプリではおもしろみがありません。公開しておもしろそうなもので、プログラミング的にある程度の難易度があり、自分が興味を持っているもの。そう考えるとRDBMSなんかいいんじゃないかと思ったわけです（キーバリューストアなんかも考えましたが、RDBMSの方が複雑そうだったので）。

何を作るのか

方針変更に伴い、一部修正しました。

ここまで作る、ということは明確には決めていませんが、大体下記のようなものを考えています。

  • 100%Perlで開発する。
  • 10月上〜中旬10月下旬くらいまでにある程度形にする。
  • まずはMyISAMのような、トランザクションなし、テーブルロックで動作するものを作る。追記型MVCCでトランザクションをサポートする。
  • 実用性は重視しないが、小型のシステムに気軽に組み込んで使えるようなものを想定する。
  • SQLのサポートは構文解析が大変な上に、アルゴリズム的な本質ではないので後回し。

どんなものができあがるかわかりませんが、あたたかく見守っていただければ幸いです。