Show HN: LearnDB - 純粋なPythonでゼロから実装したRDBMS（SQLiteクローン）

 (github.com/spandanb)
3 ポイント 投稿者 GN⁺ 2023-08-14 | 1件のコメント | WhatsAppで共有
  • LearnDBは、データベース内部構造をより深く理解するためにゼロから実装した**リレーショナルデータベース管理システム（RDBMS）**およびSQLiteクローン
  • 純粋なPythonで書かれており、ビルド手順がなく、基本的にゼロ設定で、設定をオーバーライドできる構造
  • select、from、where、group by、having、limit、order byをサポートするlearndb-sqlと、larkベースのカスタムレキサー・パーサーを提供
  • SQL文を受け取り、データベースのテーブルとデータを操作するエンジン、ディスクベースのbtreeバックアップデータ構造で構成
  • 利用方法はREPL、Pythonモジュールとしてのimport、コマンドファイルをエンジンに渡す方式をサポート
  • コードベースはtinkeringに適しているが、実際のストレージソリューションとして使ってはいけない重要な制限がある
    • 浮動小数点演算はIEEE754と比べて非常に単純化された実装
    • select * ...のようなワイルドカードカラム展開など、一般的なユーティリティ機能は未サポート
  • 開発時の実行要件はLinux/macOSシステムとPython 3.9以上で、データベースファイルへの排他的な読み取りアクセスのためにfcntlを使用
  • 参考資料として、cstackのデータベースチュートリアル、SQLite Database System: Design and Implementation、SQLiteファイルフォーマット文書、PostgreSQL文書を使用

関連記事

1件のコメント

 
GN⁺ 2023-08-14
Hacker News の意見

  • Python のような言語でこうしたシステムを書くのは、むしろ素晴らしい選択だと思う。データベースはたいてい C++ や C で書かれるが、自分にとっては Python のほうがずっと読みやすく、取り組みやすい
    本気で性能を狙うなら後で低レベル言語に移植すればいいし、今の形では学習用として有用
    自分もデータベースエンジンが分散環境でどう動作し得るのかを学ぶために、Python で SQL/グラフ Cypher/ドキュメント/DynamoDB スタイルを混ぜた分散型の擬似マルチモデルデータベースを作った: https://GitHub.com/samsquire/hash-db

    • だから純 Java のリレーショナルデータベースコミュニティがあるのだと思う。Hypersonic、H2、Derby のように、大型機級のスケールが不要なら、データベースを配布して使うのが簡単で、必要ならメモリに組み込むのも容易
    • 完全に同意。その意味で、Python で Git をゼロから作る ugit シリーズは本当に良かった: https://www.leshenko.net/p/ugit/
    • よく分からない。Python も C/C++ と同じくらい微妙で、データベースの作り方を学ぶには、触れるべき面白い部分の多くに Python ではなかなか手を出しにくいという欠点がある
      C も Python も、悪い言語設計や不整合、数々の落とし穴を無視して簡単な部分だけ見れば取り組みやすく見える。しかし C なら少なくとも正しくやる方法を学べる可能性はあるが、Python では現実世界がどうなっているのかすら分からないかもしれない
    • 素晴らしい仕事。自分も似たように感じたし、Python のおかげで高レベルの概念に集中できた。ただ途中で、静的型付けでコンパイル言語だったらよかったと思った瞬間もあった

  • かなり昔、誰かが SQLite を C から C# に書き直し/移植したことがある: https://code.google.com/archive/p/csharp-sqlite/wikis/Letter...
    Dr. Richard Hipp がその作業をどれほど歓迎していたかも見る価値がある
    GitHub ではおそらくここにあるようだ: https://github.com/CsharpDatabase/CsharpSQLite その後のクローンもさらにあるかもしれない

  • 素晴らしい。きっと楽しく、やりがいのある経験だったはず
    高速に作る意図ではなかったのは分かるが、面白半分にベンチマークもいくつか作ってみられないだろうか？

    • 少し本題から外れるが、有用なベンチマークの作り方を扱った良い資料や発表、ブログ記事を知っている？
    • learndb に TPC-C のようなものを実装して、どうなるか見てみるのも面白い練習になりそう

  • この記事のおかげで、Python 向けの Lark というかなり良さそうなパーサーライブラリを知った
    サイトの JSON チュートリアルが素晴らしい。JSON 用の基本パーサーの作り方を示したうえで、性能を改善する方法をかなり詳しく扱っている: https://lark-parser.readthedocs.io/en/latest/json_tutorial.h...
    RDBMS プロジェクトで使われた文法はここにある: https://github.com/spandanb/learndb-py/blob/master/learndb/l...

    • Python プロジェクトには Lark を強くおすすめする。使いやすい
      文法をデバッグするときに IDE が非常に便利だった: https://www.lark-parser.org/ide/
      EvaDB では、AI モデル利用に合わせた SQL 風言語に Lark を使っている: https://github.com/georgia-tech-db/evadb/blob/master/evadb/p... https://github.com/georgia-tech-db/evadb/
      Lark が気に入ったなら、スポンサーになることも検討してよい: https://github.com/sponsors/lark-parser
    • 文字列内の DSL とは、それは本当に良いやり方なのだろうか？ Python でこれを使ったり必要になったりしたことは思い浮かばないが、もっと良い方法があり得るのではないかと思う
      期待するキーを持つ dict と、ビット OR 演算子による構成だけでも、多くの文法形式とおおよそ対応していて、より良いのでは？ import は import のままにして、何らかの形で混ぜられそう
      ざっと見て最初に思ったことなので、何か見落としているかもしれない
    • 失礼に聞こえるつもりはなく、この作業が素晴らしく、新しいことを学ぶ方法だという点も認めている。ただ、パーサー生成が最終目標ではなく、AST をデータベースで実行するための手段なら、パーサー部分だけで何を学べるのかが気になる
      生成されたパーサーをより効率的にするために、継続的に最適化しなければならない部分があるのだろうか？
      論理的な次の段階は、AST から最適なクエリプランを生成することなのだろうか？

  • とても良い
    SQLite は読むのが非常に難しいが、この実装はかなり理解しやすい。特に仮想マシンの部分がそうだ: https://github.com/spandanb/learndb-py/blob/master/learndb/v...
    このファイルと比較できる: https://github.com/sqlite/sqlite/blob/master/src/vdbe.c
    ただ、この LearnDB がどれほど完全なのかは気になる。SQLite が読みにくいのは古いからだけではなく、SQL の多くの部分を扱い、SQL 仕様に従ううちに複雑になるからでもある
    SQLite には優れたテストスイートがあるので、この実装にそのテストを走らせてみるとよさそう

  • 本当に良くて、私のような人がデータ構造とアルゴリズムをよりよく学ぶのに良い方法に見える。B+木がどう動作するかは説明できるが、自分でコーディングしろと言われると戸惑いそう
    データベースと Python が好きなので、ざっと見ていく過程が本当に興味深かった

    • 確かにそうだった。B木の実装がこのプロジェクトを始めた最初の動機だった。特にノードの再平衡化と分割に関する細部が重要だった
      さらにディスクに保存される構造である点が、実装を考えるうえでもう一つの複雑な要素を加えていた

  • SQLite テストスイートのうち、どれくらい通せるのだろう？

  • ACID 保証やクエリプランニング/最適化はサポートしている？
    できるべきだという意味で聞いているのではなく、B木と SQL 以外にどこまで試したのか知りたい
    自分もいつかこういうものをやってみたい。素晴らしい仕事だ

    • ACID 保証については、複数の文をアトミックにまとめる概念、つまりトランザクションはない
      しかしそれ以外では単一ファイルのデータベースであり、データベースファイルを操作するプロセスも 1 つの learndb インスタンスだけが可能だ。なので単一接続データベースという点で一貫性と分離性が得られる
      永続性はファイルシステムが永続性を提供する分だけ得られる。だから ACID 特性のどこかには位置している
      クエリプランニング/最適化はまだ実装していないが、最適化モジュールをどこに入れられるかは考えてみた。パーサーが AST を出力し、この AST やそこから派生した中間表現を最適化できる
      つまり VM が AST を実行する前に、AST を書き換えたりノードを削除したりできる

  • 少し話はそれるが、Python にも mapDB のようなものはある？
    https://mapdb.org

  • 素晴らしいプロジェクトだ。コードも非常に読みやすく、コメントも素晴らしい