承前

人生で一度くらいは DBMS を開発してみたいという気持ちになってきたので、どこかに良いエントリーポイントがないか探してみたところ、以下の Build Your Own SQLite というサイトを発見しました。名前が長いので以降 BYOS と略します。

https://cstack.github.io/db_tutorial/

BYOS では実装に C 言語を使用していますが、今回はこれを Haskell でやってみようと思います。

実装に Haskell を使うのは筆者の趣味によるもので、特に採用を正当化できる合理的な理由はありません。強いて言えば、Haskell を使うことで低レベル言語を利用した場合に比べて保守性とパフォーマンスにどれくらいの影響が出るのかを感覚的に知ることができるかもしれません。

以下、各章ごとに実施した内容をメモします。

Part 1 - Introduction and Setting up the REPL

DBMS は入力された SQL を実行計画に翻訳するフロントエンドと、実行計画を実際に実行するバックエンドの２つの部分に分けられます。BYOS ではフロントエンドから実装をスタートしています。

最初に実装するのは REPL です。入力をおうむ返しするだけの簡単な REPL を実装します。

module Main (main) where

import System.IO

main :: IO ()
main = repl

repl :: IO ()
repl = do
    input <- prompt "repl> "
    case input of
        "" ->
            repl
        ".exit" ->
            return ()
        query -> do
            putStrLn query
            repl

prompt :: String -> IO String
prompt text = do
    putStr text
    hFlush stdout
    getLine

SQLite では . で始まるコマンドはメタコマンドという SQL のクエリとは別種のコマンドとして扱われます。コード中で終了コマンドとして扱っている .exit もその一種です。

BYOS では C 言語で長々と書いているのですが、Haskell だと非常に楽ですね。

Part 2 - World's Simplest SQL Compiler and Virtual Machine

SQL パーサを実装します。最初のステップなので、ここでは極めて単純な命令のみを受け入れるパーサを実装します。認識するコマンドは SELECT と INSERT のみ、しかもコマンドに続けて記述されたパラメータは無視してよいことにします。

パーサの実装は非常に楽しい作業なので、パーサコンビネータから全て自前で実装しても良いのですが、あまり凝りすぎると本線から外れてしまうという負の予感があるので、今回は既存のパーサライブラリを利用してできるだけ簡単に済ませます。

今回は Earley というパッケージを利用します。Earley はその名が示す通り、Earley's parsing algorithm を採用した比較的新参のパーサライブラリで、単に面白そうというだけの理由で採用しています。Earley 自体は「ほとんどの他のパーサライブラリに比べて遅い」と開発者自身が Hackage に書いているくらいなので、パフォーマンスを追求するなら Megaparsec などの他のライブラリを選択した方が良さそうです。

Earley を依存関係に追加します。

dependencies:
- base >= 4.7 && < 5
- Earley

Earley の基本的な利用方法は、Grammar 型の文法規則を宣言し、宣言した文法規則を parser に渡してパーサを生成、最後に fullParses で実行するという流れです。GitHub にある サンプル を見ると捗ります。

module Parser
    ( Expr(..)
    , parse
    ) where

import Control.Applicative
import Data.Char
import Text.Earley

data Expr
    = ESelect
    | EInsert
    deriving (Show)

parse :: String -> ([Expr], Report String [String])
parse = fullParses (parser expr) . words

expr :: Grammar r (Prod r String String Expr)
expr = do
    select <- rule $ ESelect <$ keyword "select" <* many (satisfy (const True))
    insert <- rule $ EInsert <$ keyword "insert" <* many (satisfy (const True))
    rule $ select <|> insert

-- SQL's keywords are case-insensitive
keyword :: String -> Prod r e String String
keyword s =
    let toLowers = map toLower
    in  satisfy $ \t -> toLowers s == toLowers t

本来は fullParses の前に行う字句解析処理をちゃんと書くべきですが、横着して words で入力を適当にスペース区切りにしています。これは空白を含む文字列リテラルを与えられると破綻するので、いつか修正が必要になりそうです。と思いつつも、面倒なので今は直しません。

REPL にも反映しておきます。

+import Parser

 -- 中略

 repl :: IO ()
 repl = do
     input <- prompt "repl> "
     case input of
         "" ->
             repl
         ":q" ->
             putStrLn "Bye!"
         query -> do
-            putStrLn query
+            print . fst $ parse query
             repl

タプルの２つ目の要素の Report は不要なので捨てています。基本的に解析用の情報が出力されるだけなので、必要になった際に戻すくらいでよいでしょう。

コンソールで動作確認すると以下のような感じです。

repl> SELECT
[ESelect]
repl> insert
[EInsert]
repl> SeLeCt something from somewhere
[ESelect]
repl> Inserta
[]

Part 3 - An In-Memory, Append-Only, Single-Table Database

掲題の通り、SELECT と INSERT のみをサポートし、データの永続化を行わず、かつ以下のハードコードされた単一のテーブルしかサポートしないデータベースを実装します。

この章でやることは大きく２つです。

1. SQL パーサを修正して INSERT のパラメータを受け取れるようにする
2. SELECT と INSERT を実行するバックエンドを実装する

本丸は 2 の作業で、バックエンド実装の一環として、データの永続化を見据えたシリアライズ処理を実装します。この作業には Haskell でバイナリ列を効率的に操作する方法が必要になるため、ST や IO などの状態を扱うモナドから適切なものを選定する必要があります。

以下、各作業ごとにその内容を記載します。