実装の方針
併せて、方針変更についてもご覧下さい。
(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から作り始めたいと思います。
