Rustで対話型Datalogエンジンを作る

• Datalog論理プログラミングとRustの効率性を組み合わせ、シンプルで使いやすく、性能まで考慮した対話型Datalogエンジンの開発過程を詳しく共有
• 直感的なCLI環境でルール(rule)とfactをリアルタイムに追加・拡張可能で、大量データのロード、動的なルール入力、高速なクエリ性能まで体験できる
• パース(Parsing)、データ表現(Representation)、ルール評価(Planning/Evaluation) を段階的にRustコードとともに説明し、実際の実装方法を学べる
• 最適化されていない単純な実装から始めて、段階的に性能と構造を改善していく過程を通じて、データ並列処理やjoin最適化などの高度なロジックも学べる
• 大規模データセットベースのプログラム解析(Nullability、Aliasingなど) の事例を実際に実行しながら、性能やメモリの課題、クエリ最適化、join-plan改善のノウハウを共有

---

導入: RustでDatalog論理プログラミングを試す

• Memorial Dayの期間中、Minnowbrookカンファレンスでさまざまな論理プログラミング(Datalogなど)の実習と議論を実施
• 既存のDatalogツール(Soufflé、ctdalなど)には実際の利用・拡張性・性能の面で限界が見つかり、実用的なツールの必要性が浮き彫りに
• 筆者はRustで、シンプルさ・使いやすさ・性能をすべて満たすDatalogインタプリタ(datatoad)を自ら実装することを決定
• プロジェクトの目標: CLIで大容量データを高速にロードし、動的にルールを追加・修正しながら、リアルタイムで結果を確認でき、クエリ性能も確保すること

Datalogの基本概念

• Datalog は、ルール(Head :- Body)形式の論理文を基盤に、与えられたfactとruleから導出可能なすべての事実を自動的に導く
• ルール(例: tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c))は、変数とリテラルで構成される
• fact は、条件なしで真となる値(例: edge(1, 2) :- .)
• Datalogの強み: ルールを追加すると推論可能な情報の集合が増え(単調性)、ルールや事実の順序に関係なく同じ結果に収束する(収束性)
• Rustでは、ルールとfactをAtom/Rule/Term構造体で表現し、relationごとにfact集合を管理する

中核構造の設計

データ表現

• Fact は Vec<String> として、fact集合は BTreeMap<String, Vec<Fact>> などで初期設計
• 大容量データの最適化のため、columnar(カラム指向)データ構造を導入し、alloc overheadを最小化
• FactContainer: ソートおよび重複除去されたfact集合で、append only構造
• FactLSM: FactContainerを複数階層で管理するLSM(Log-structured merge-tree)方式で、挿入およびソート・マージを効率化
• FactSet: factのlifecycle(新規追加、最近導出、安定化したfact)を管理し、重複計算や不要なメモリ浪費を防止

ルール適用と推論

• 各ルールはJoinPlan(joinプラン)を生成し、適切なカラム順序・キーの組み合わせを基にmerge join方式で推論
• merge join: body atomごとにキーカラムをソートし、joinキーが一致する場合にのみ新しいfactを導出して性能を最大化
• FactSetのstable/recent/to_add構造を活用し、既に導出済みのfactと新規factを分離して不要な再計算を防ぐ(差分評価)
• .update() ループ: 新しいfactの導出が止まるまで全ルールを反復適用し、fixpointに到達するまで推論を繰り返す

パーサ実装

• Souffléスタイルの文法(?var, :-, ., , など)をサポートし、Rustで独自にトークナイザ/パーサを実装
• エラー発生時は安全にNoneを返す、実験環境に適したシンプルなパーサ設計

性能最適化と実際の解析例

Nullability解析(Reachability)

• 大規模データセット(例: httpd_df)で、値のコピー・移動経路を追跡するためのDatalogルールを定義し、性能を測定
• ルールの書き方の違いによって性能差が非常に大きく、変数バインディング・カラム順序・joinプランに応じたtemp relation発生などが影響
• データの初期形状やjoin戦略により、実行時間とメモリ使用量に数十倍の差が生じ、クエリ最適化の重要性を実感
• 最適化を適用すると、既存のC++ベースツール(Graspanなど)と比べて10〜80倍以上の性能向上を確認

Aliasing解析(Points-to)

• aliasing/ポインタ追跡解析のための複雑なDatalogパターンを実装し、論文(Graspan、Zheng-Ruginaなど)と同じクエリを実行
• Datalogルール内の反復(^*)、オプション(^?)、転置(^T)演算を明示的な再帰/unionへ展開
• 中間結果(relation alias、temp joinなど)の命名や再利用の設計次第で、クエリプラン全体の効率と資源消費が大きく変化
• クエリプラン最適化なしに大きな中間結果を生成すると、性能低下とメモリ爆発を招く(例: V relation)
• 必要な結果だけを算出する"demand-driven"方式(マジックセット変換)を議論し、実際のクエリプラン変形と性能改善の可能性を提示

Rustで直接試して得た教訓

• Datalogエンジン性能の核心は、データ表現(カラム指向/LSM)、差分推論、joinプラン最適化にある
• ルールを機械的に書くだけでは、不要な中間データ生成とリソース浪費につながるため、最適化が必要
• Rustで直接試すことで、実運用データセットにおける数百万〜数千万rowのfactを効率的に管理し、拡張性と推論速度を同時に達成できる
• CLI環境で大規模データのロード、リアルタイムのルール追加、結果確認まで容易に実験可能
• query optimizerの役割、bushy-tree join(中間結果活用)、不要な関係の生成を避ける習慣など、実際のDatalog記述と運用に大きな示唆がある

今後の拡張課題

• ディスクスピル、複数ワーカー/プロセスへの分散拡張、ストリーミングjoin、カスタムコンパイル最適化など、今後の研究課題が残っている
• 大規模プログラム解析、グラフ/関係推論、静的解析、データフロー追跡などの実践分野でRust Datalogの活用可能性は高い

[GN⁺]

Hacker Newsの意見

• いまこの記事が上位に出ているのが面白い状況で、Differential Datalog（このリポジトリ）とRustを使ってリアルタイム戦略ゲームを作る作業を進めているとの説明。DDLがゲームロジックを担う構成で、新しいアイデアを学び、いろいろ試行錯誤して経験を積むのが狙い
  • 進捗を楽しみにしており、結果が気になるとのこと
  • Differential Datalogの開発が停止している状況なので、その実装がどこまで可能なのか、現時点でどの程度完成しているのか気になっている
• mangle datalogをRustへ移植しようとして少し進展した経験を共有。Rust実装はこちらで確認でき、golang版も同じリポジトリ内にある。作業が遅い理由は優先度が低いこともあるが、"second system syndrome"（最初のものより2つ目で欲が出て作業が遅くなる現象）のためでもある。Rust版mangleはメモリマッピングにより必要なときにディスクからデータを読み書きできるため、大規模データを扱える。golang版は全データをメモリに載せて処理する構造。この記事の良い点は、datalogパーサの構成がうまく整理されていて、LSMツリーへの言及もあり理解しやすいこと、data frogよりずっと追いやすいこと。Rustにはproc-macrosを使ったascent、crepeなどさまざまなdatalog実装があるが、実行中にクエリを動的に処理するには制約がある。クエリとプログラムが固定された静的解析のケースなら、proc macroのアプローチも十分優れているという立場
• datalog愛好家の一部が継続的に集まって活動している様子が良いという話。最近はdatalogルネサンスがやや勢いを失った雰囲気で、Datalog 2.0カンファレンスも以前より小規模だったし、HYTRADBOIカンファレンス第2回ではdatalog関連の議論自体が大きく減っていた。第1回では論文の4分の1がdatalog関連だった記憶がある。他の参加者が最近のdatalogプロジェクト経験を共有してくれるのが大きな励みになっている。最近は古いSQLデータベースから大規模ソフトウェア移行を準備しながらデータ品質パイプラインを作っており、datalogクエリはうまく構造化すると可読性が高く、データ品質問題の探索にはSQLよりずっと効率的な道具だと思う
  • Datalog 2.0の参加者が少なかったのは、datalog自体の停滞というよりイベント構成の問題が大きいという意見。Datalog 2.0はLPNMRというあまり知られていないヨーロッパのカンファレンスのサテライトイベントで、今回は米国Dallasで唐突に開催された。自分もDatalog 2.0に論文を投稿したが、主要著者は別にいて、実際にdatalog分野の人もイベントにはあまり参加していなかった。Nemo solverを発表したヨーロッパ側の参加者が目立っていた。要するに、今年Datalog 2.0の参加者数が少なかったのはイベント固有の事情とサテライト開催であった点が大きく、datalogエンジン実装そのものに大きな革新が残っていないという見方にも同意する。実際の研究の流れは基本的なdatalogより、streamベース（HydroFlow）、choice（Dusa）、chase engine（Egglog）など、より興味深いテーマへ進んでいる。monotonic、chain-forward saturation（Horn clauses）はエンジニアリング的に十分確立された手法で、その上にsemirings、Z-setsなど新しい理論探究が進んでいる状況との説明
• 筆者はdatalog関連の仕事がうまいと思うが、導入部でbinary joinを教えるやり方は理想的な状況でなければすぐ複雑になるので惜しいという立場。generic join系の方法のほうが直感的に一般化しやすいと思う。worst-case optimal join algorithmについてはwikiの説明参照を推奨
  • 関連する話として、McSherryの以前のブログ記事では、binary joinでも適切なクエリプラン調整によってworst-case最適ランタイムを達成できることを証明する過程が確認できる。ブログ記事参照
• 該当ブログ記事の冒頭にある "I, a notorious villain, was invited for what I was half sure was my long-due comeuppance." という一文が最も印象的で、今年最高の技術ブログ記事の書き出しだと思った。全編を通して筆者の愉快な語り口が光っており、これほど深い技術テーマをここまで楽しく読める文章は珍しいという感想。aliasingクエリ最適化の旅を探偵小説のように面白く描いている。50GBのメモリ使用量に打ちのめされ、5GBへの最適化成功時には一緒に応援したくなる感覚。コードも文章力も素晴らしいと評価
• 以前、何人かのClojureファンがdatalogはSQLより優れていると信じていて、リレーショナルDBがどれもSQLしかサポートしていないのが惜しいと言っていたのを聞いたことがある。なぜそう考えるのかは自分では深く掘り下げていない
  • ClojureやDatomicのdatalog方言には自分はあまり馴染みがないが、datalog自体には共感している立場。オンラインnotebook環境でdatalogを試せるPercivalを勧める。percival.ink を利用し、datalogの核心概念さえつかめば実装間の移行も容易。PercivalをforkしてdatalogをSQLiteへコンパイルする版も作ったことがあり、fork版 はまだ集計関数や高度なjoinは未完成だが、基本クエリはよく動く。LogicaはGoogle研究者が作った、より本格的で完成度の高いdatalog->SQLコンパイラで、BigTable、DuckDBなど多様なSQL方言をサポートしている。Logica 参照。再帰クエリやルールを扱うとき、datalogは圧倒的に扱いやすいのが印象的。SQLでも不可能ではないが、まるで粘土をストローで吸うような感覚。Frank McSherryが作っているMaterialize.comは “WITH MUTUALLY RECURSIVE” というSQL形式を提供しており、Materializeブログ を参照中。Notionのページロードクエリやデータ同期への活用を検討している。Felderaにも再帰ビュー向けの類似形式がある。Felderaのブログ記事 参照。Felderaの利点は各「ルール」またはサブビューを独立したstatementとして分けて書けることで、1つの文にすべて詰め込む必要がない。欠点はSQL文法にApache Calcite由来の制約が多い点。Materialize SQLはPostgreSQL互換性に力を入れている印象
• 少し前までVMwareがdifferential datalogから距離を置いているという話を見た記憶があり、McSharryの新しい記事をうれしく思っている
  • Differential DatalogチームはFelderaという会社を設立しており、Felderaウェブサイトで確認できる。differential datalogからdifferential SQLへ移行した理由は、datalogが市場で実際に採用されにくいからだと推測
• datalogとRustを一緒に使いたいならcozodbを勧める。cozodbはRustで書かれていてdatalogクエリ構文をサポートしている
  • cozodbも興味深いプロジェクトだが、活動停止したプロジェクトに見える。2024年11月ごろにソースコードを見ていて、sqlite保存バックエンドに簡単に改善できる点（issue #285）を見つけた経験がある
• 1日前にHacker Newsへ投稿された関連スレッドへのリンクを共有 投稿はこちら