RustでDatalogを実現！

この記事がトップに来ててウケるね！
ちょうどDifferential Datalog[1]とRustを使ってリアルタイム戦略ゲームを作ってるところなんだ。
DDLでゲームロジックを管理してるよ。
新しいアイデアに触れたい、yak shavingを楽しみたいってのが一番の理由かな。[1] https://github.com/vmware-archive/differential-datalog

ddlogを使ってクールなデモを作ってるんだね！
そういえば、俺たちddlogチームはFeldera(https://github.com/feldera/feldera)を立ち上げたんだ。
RustからDBSPを直接使うことも検討してみてね。

Differential Datalogとsalsa[1]（rust-analyzerのバックエンドに使われてるクレート）を組み合わせて、Frankensteinみたいなバージョンを作れないかな？って思うんだけど。[1] https://github.com/salsa-rs/salsa

おー、いいね！
これからの話を読むのが楽しみだよ！

超クールだね！
DDLogはもう積極的にメンテナンスされてないみたいだし、実装が今どうなってるのか、どこまで進むのかめっちゃ気になるよ。

「悪名高い悪党である私が、まさかお縄頂戴かと思っていた場に招かれた」– これは今年読んだ技術ブログの中で一番の掴みだったね！
語り手のセリフ回しも最高だったよ。
こんなに技術的に深いのに、読んでて楽しい記事は珍しいね。
エイリアスクエリの最適化の道のりは探偵小説みたいだった。
読者も一緒に、50GBのメモリ使用量にうめき、5GBまで減った時に歓声をあげたって感じ。
コードも文章も最高だったよ！

mangle datalogをRustに移植する作業、https://github.com/google/mangle/tree/main/rustでちょっと進めてるんだ。
Go版と同じリポジトリにあるよ。
遅々としてるけど、優先順位が低いのもあるし、second system syndromeにもかかってるんだよね。
Mangle Rustはmemory mappingでデータをディスクに読み書きするから、どんなサイズでも扱えるはず。
Go版はインメモリなんだ。
この記事はDatalogをパースしたりLSM treeに触れてて、data frogより分かりやすいからいいね。
Rustにはproc-macroを使ったDatalog実装（ascent, crepe）がすごく多いんだけど、実行時にクエリを扱えないのが欠点かな。
静的解析みたいにクエリが決まってる用途ならproc macroの方がいいかもね。

Datalog好きのコアグループが頑張ってるの見るのはいいね、最近のDatalogブームは下火っぽいけどね。Datalog 2.0カンファレンスは前より小さかったし、HYTRADBOIもDatalogの発表が少なかったんだ。みんなが最近のDatalogプロジェクトをシェアしてくれて励みになるよ。俺は今、古いSQLデータベースのデータ品質パイプラインを構築中で、移行の準備をしてるんだ。Datalogの方がSQLよりデータ品質の問題を見つけやすいし、ちゃんと構造化すればクエリがすごく読みやすいんだ。

悪く思わないで欲しいんだけど、Datalog 2.0の参加者が少なかったのをDatalogの衰退の例にするのはどうかな。あれはLPNMRっていうあまり知られてないヨーロッパのカンファレンスの付属ワークショップで、たまたまDallasで開かれたんだ。俺もDatalog 2.0に行ったけど確かに人は少なかった。論文も発表したよ。あの分野の人はあまり来てなかったかな、何人かのヨーロッパの人（Nemo solverを紹介してた人とか）を除いてね。だから、参加者の少なさは、メインイベント（ICLP）ですらない付属ワークショップっていう、権威の低いカンファレンスだったことの方が原因だと思うんだ。
俺が言いたいのは、バニラDatalogエンジンの実装に目新しさがないっていうハイレベルな点については反論するつもりはないってこと。もちろん同意だよ、研究はもうずっと前からHydroFlowみたいなストリーミングとか、Dusaの選択とか、Egglogのチェイスエンジンみたいにもっとエキゾチックな問題に移ってる。バニラDatalogが面白くないってことには誰も反対しないと思うんだ。ただ、monotonicで前方連鎖推論（Horn clauses!）っていうのは、semiringsとかZ-setsみたいなもっと面白い理論を構築するための、よく理解されたエンジニアリング領域（特にハイパフォーマンス分野で）を持つ豊かなベースラインなんだよ。

アメリカはヨーロッパ人にとって訪問しにくい環境なんだよ。西ヨーロッパや北ヨーロッパ全体で避けるのがテーマになってる。もしヨーロッパからの参加者を期待してたなら、それが過去と違う理由だろうね。科学分野でも、観光でも、ビジネス旅行でも同じなんだ。

君に全く同意だけど、あのイベントは2024年10月に開催されたから、トランプのひどい振る舞いは影響してないよ。外国人にとってTexasに行きたくない理由はトランプ以外にもあるだろうけど、この特定の場合は、LPMNRが伝統的にヨーロッパのカンファレンスなのにたまたまアメリカで開催されたことの方が関係してると思うな。

ステートマシン＋パージングの部分が気に入ったなら、Rob Pikeがやった古い「Lexical Scanning in Go」っていうトークもおすすめだよ。
https://www.youtube.com/watch?v=HxaD_trXwRE
Goだけど、他の言語でも簡単にほとんど応用できる。Rust, Zig, Goみたいなモダン言語がunicode／runes／graphemesをネイティブでサポートしてるの本当に嬉しい。Java, .net, C++, あるいはスクリプト言語に比べて、すごくたくさんの問題が消えるんだ。

著者のDatalogの仕事は全体的に好きなんだけど、入門資料でバイナリJOINを使うのを教えないで欲しかったな。あれって理想的なケースから外れると、内部がすごくごちゃごちゃになるのを見つけたんだ。汎用的なJOINスタイルメソッドの方が、頭の中で一般化するのがずっとずっとシンプルだと思ったよ（Worst-case optimal join algorithmとかを見てみて）。
https://en.wikipedia.org/wiki/Worst-case_optimal_join_algori…

関連する話だけど：McSherryの前のブログ記事は、クエリプランを適切に調整すれば、バイナリJOINでもworst-case optimal runtimeを達成できることを示すものだったよ。
https://github.com/frankmcsherry/blog/blob/master/posts/2025…

materializationが多いワークロード（プログラム解析など）の場合、最適化されたバイナリJOINプラン（プロファイル最適化、手動最適化など）が、worst-case optimal plansよりも勝ることがよくあるんだ。これはトライベースの表現を使う必要がない分、スケーラビリティ（ロックが少ない）が良いからだよ。worst-case optimal plansの領域内でもまだたくさんの選択肢があるけど、悪いworst-case optimal planは、悪い（ランダムに選ばれた）バイナリplanに勝てないこともよくある。そしてもちろん（この議論の全体的なポイントだけど）、全てのバイナリplanが爆発してしまうクエリもあって、そういう場合はWCOJが必要なんだ。もっと伝統的なバイナリJOINを堅牢にする研究（https://db.in.tum.de/people/sites/birler/papers/diamond.pdf ）など、他の面白い研究（https://arxiv.org/html/2502.15181v1 ）もあるよ。WCOJの並列化は、俺が知る限りまだ未解決の問題らしい（少なくとも、それに取り組んでる人たちがそう言ってるよ）。でも、それに取り組むいくつかの有望な方向性があって、何人かの人たちが研究してると思うよ。

昔、学生時代にPrologに軽く触れたことがあるんだ。どう使うかとか何に役立つかは大体わかるんだけど、全然深くはないんだ。それ以来、Datalogが何かすごいものだって聞き続けてるんだけど、それが何なのか理解できないんだ。つまり、シンプルな疑問「DatalogはPrologの何が改善されてるの？」の答えが掴めない。今ちょうどDatalogのWikipediaページをざっと読んでみたんだ。そこから得る漠然とした理論は、多分Prologのパフォーマンスが比較的悪いのに対して、Datalogはパフォーマンスを劇的に改善した（おそらくもっと大きなデータセットやもっと並列化された処理を可能にしてる）んだけど、その代わりに他の重要な点で表現力や機能を減らしたってことかな？（チューリング完全性じゃなくなったとか？） それがDatalogのことなの？ それとも完全に的外れ？

俺の知ってる限りだと、Prologって関係性を定義するだけで答えが出る宣言的なものに見えたけど、実際はルールの順番とか”cut”みたいな追加命令に依存してた。それらはムダな計算を防ぐだけでなく、結果にも影響しちゃったんだ。一方Datalogは、良くも悪くも構文が違うだけの関係データベースって感じ。

Datalogはもっとシンプルでチューリング完全じゃないんだ。フォワードチェイニングを使うからパフォーマンスとかメモリ特性に影響が出るよ。Prologだと簡単な巨大な探索空間も、Datalogだとメモリ食いすぎて表現できない。DatalogはCVT付きの通勤カー、PrologはF1カーって感じ。つまり、改善じゃなくて、Prologをみんながヤケドしないように去勢したようなもんだね。他のアプリに実装したり組み込んだりもしやすい（Prologも簡単に組み込める場合もあるけど）。
Prologに慣れてると、Datalogは窮屈に感じるだろうね。call/3がない？項展開とか目標展開がない？Datalogは basically PrologのLCD機能セットを引っ張り出して、インタラクティブなデータベース検索として使うように設計されてる。＞ Prologのパフォーマンスは比較的貧弱だけど、Datalogは劇的にパフォーマンスを向上させる
速いDatalogコードは書きやすいけど、上限もずっと低いよ。Prologは並行処理もできるように書けるけど、それは実装を理解する必要がある中級レベルのタスク。Guarded Horn Clausesとか派生言語[2]は、それを形式化するために開発されたけど、Prologに関する日本の進歩はすごく専門的だね。Prologのパフォーマンスはプログラマーと使ってる実装に really依存するんだ。PrologはLispみたいに、コンパイル時にDSLからネイティブマシンコードを生成できる。
使ってるPrologの実装がどう動くか理解して、それに沿ったコードをどう書くか分かれば、absolutely「十分速い」よ。残念ながら、それには一つの実装で何年もPrologコードを書く必要がある。Prologコンパイラの最適化に関する研究もいっぱいあるよ[3][4]、それにいくつかの商用例[5]もあるね。
[1] - http://logicprogramming.stanford.stanford.edu/readings/ullman.pdf
[2] - https://www.ueda.info.waseda.ac.jp/AITEC_ICOT_ARCHIVES/ICOT/…
[3] - https://www.sciencedirect.com/science/article/pii/S074310669…
[4] - https://link.springer.com/content/pdf/10.1007/3-540-18024-9_…
[5] - https://sicstus.sics.se/

もしDatalogとRustを使いたいなら、cozodbがRustで書かれててDatalogクエリ構文があるよ。

Cozodb良さそうだけど、あんまり活発じゃないね。2024年11月頃にちょっと触ってみたら、sqliteストレージバックエンドに簡単な課題を見つけたよ。https://github.com/cozodb/cozo/issues/285

コード量がそんなに多くないからいじりやすいよ。

うん、Cozodbは俺にとっては大体ドキュメント通り動いてくれたし、使うのが楽しかったよ（プログラムの静的解析とかにもね、あれも内部でsorted treesとかtype-fu使ってる）。ドキュメントにはブログのウォークスルーと比較するのに十分な内容があるし、特にクエリ最適化に関する作業は面白い。でもRustでインメモリじゃない場合、データのシリアライゼーションがコストかかるし、プロジェクトはせいぜい静かだね。

昔Clojureファンに、DatalogはSQLより優れてるし、リレーショナルDBがみんなSQLを使ってるのは残念だ、って言われたことがあるんだ。なんでそう思ったのか、十分深く掘り下げなかったけど。

基本的にDatalogはSQLよりずっと簡潔で、ビューの分離もはるかに簡単だし、推移閉包も圧倒的にやりやすい。俺が簡単な非再帰クエリで始めたのがhttp://canonical.org/~kragen/binary-relationsなんだけど、そのSQLへの翻訳（以下に示す）は既に犯罪的だし、適切にファクタリングされたSQLの解決策は死刑に値するよ。
最近のANSI SQLの追加で再帰の機能は入って、もう完全に不可能ではなくなったけど、3つ大きな欠点があるんだ。
1. 誤ってSQLをチューリング完全にしてしまったこと。一方、Datalogクエリは終了が保証されてる。
2. まだ使うのがすごく不器用なこと。
3. 1のせいで、完全に実装されてないことも多くて、頼りにならない。

そうそう、1番目（SQLがチューリング完全になったこと）はbasically設計を最初から間違ったってことだよね。評価する言語が、in fact Datalogじゃないんだから、Datalogの実際のメリットを享受することは不可能。再帰クエリは射影でarbitraryな計算を実行できる能力があるから、まずトップダウン評価戦略とかマジックセットみたいなハイブリッド評価は除外されちゃう。

興味あるんだけど、どうやったら有用かつ自然にSQLに再帰を追加できるんだろう？チューリング完全性にしないでさ。

俺もよく分かんないんだけどさ。Feldera では SQL に再帰機能を追加して、チューリング完全になったんだぜ。詳しいのはここ見てくれよな。
https://www.feldera.com/blog/recursive-sql-queries-in-felder…

Clojure/Datomic は分からんけど Datalog の core は掴めるね。お試しは Percival がお手軽だよ（https://percival.ink/）。俺が SQLite コンパイル版も作った（https://percival.jake.tl/）。Logica はすごい Datalog-＞SQL コンパイラだ（https://logica.dev/）。再帰クエリは Datalog が楽勝！SQL も Materialize (https://materialize.com/blog/recursion-in-materialize/) や Feldera (https://www.feldera.com/blog/recursive-sql-queries-in-felder…) でマシになったけどね。Feldera は Calcite 由来の SQL dialect に制限があるのが難点かな。

Feldera では SQL の機能、Calcite に貢献して増やしてるんだぜ。みんなにとって良くなるようにね。Feldera SQL コンパイラの作者 Mihai Budiu は Calcite の committer なんだ。

貢献ありがとう！Mihai が Calcite に UUID 実装したの見たよ（https://issues.apache.org/jira/browse/CALCITE-6738）。僕が困ったとこで、僕の Feldera 経験半年前で古いね、君ら速い！Feldera/Calcite は Postgres と SQL 構文が違うのが辛いんだ。::bigint とか JSON の -＞ とか。VARIANT とか [] は elegant だけど、慣れた Postgres から移す時 regex replace が手間かな。Feldera 好きだけど friction はあるね。