これは 自作DBMS Advent Calendar 2020 - Adventar 25日目の記事です。
LSM-Tree 実装するとか言ってたけど奥歯に穴が空くなどのインシデントがあり、できませんでした。
代わりと言ってはなんですが、簡単な Tuple-at-a-time 方式のクエリエクスキューターを書いてみたのでご紹介します。
実装した理由はもちろん自分の学習のためでもあるのですが、会社の同僚が MySQL のインデックスの貼り方で悩んでいるときにパッと説明用に取り出せる小さいコードが欲しかった、という背景があります。 そういうわけで今回は Rust ではなく Ruby で書いてみました。
クエリ実行にだけ焦点を当てたかったため、データはすべてナイーブなインメモリで書き込みなし、データ構造も B-Tree ですらなくて静的に構築されたただのソート済み配列です。
B-Tree もソート済み配列も検索の時間計算量は O(log(n)) であり、違うのは挿入と削除の時間計算量です。 DBMS の利用者的な観点で言えば、B-Tree は挿入と削除の時間計算量が O(n) ではなく O(log(n)) な魔法のソート済み配列とみなすことができます。
このような激しい割り切りにより、わずか200行程度で SeqScan, IndexScan, Limit, Sort の基本的なオペレーターと4種類の実行計画のサンプルコードを実装できています。この実装の小ささは Ruby の Enumerable の便利さも一役買っています。
これくらい短いコードであれば DBMS 初学者にもポンと渡して十分気軽に遊んでもらえるのではないかと思います。
サンプルコードのテストデータとして ISUCON9 予選問題のデータを利用しています。 参考実装からクエリを拾って、それを題材に適切なインデックスと実行計画を考える練習ができます（問題公開されてるのはマジで偉大）。
ISUCON の練習や MySQL の学習と称して布教をし、うっかりこちら側に足を滑らせてくれる人が増えないかなと目論んでいる次第です。
というわけで、Ruby 200行から始める DBMS 沼のご紹介でした。
Happy Holidays!
