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

 (github.com/frankmcsherry)
1 ポイント 投稿者 GN⁺ 2025-06-16 | 1件のコメント | WhatsAppで共有
  • ロジックプログラミングのワークショップで明らかになったDatalogツールの使い勝手・性能の限界をきっかけに、Rustベースの対話型Datalogシェルである datatoad の実験が始まった
  • datatoad は実行中に規則を追加し、新しい事実を継続的に導出する構造を目指しており、columnar ストレージと LSM 階層によって事実集合の重複処理コストを抑える
  • 規則評価は Datalog の本体を結合問題に変換して処理し、stable かどうかに応じて全体評価と 増分評価を分け、すでに計算した stable-stable 結合を避ける
  • Graspan データセット実験では、手動の規則書き換えと中間関係の導入だけで aliasing 解析が 736.34秒・50.13GB から 119.34秒・5.32GB まで削減された
  • 今後の作業は、e-graph ベースの結合計画最適化、layered trie、固定幅バイト表現、ディスク spill、分散評価、ストリーミング結合、demand transform へと続く

datatoad が解こうとしている問題

  • Memorial Day の週末に行われたロジックプログラミングのワークショップで、プログラム解析向け Datalog ツールの使いにくさが目立ち、これをきっかけにシンプルで実用的かつ高速な Datalog 実装を試みた
  • 実装対象は静的なサンプル実行器ではなく、対話型 Datalog シェルである
    • 事実を大量にロードできる
    • 実行中に新しい規則を追加できる
    • 追加した規則の結果を既存の状態に継続的に反映する
  • コードは datatoad repository で追うことができる
  • 既存の datafrog は Datalog エンジンの中核アルゴリズムを提供するが、利用者が自分で配線する必要がある形のため、datatoad は同じアイデアをより使いやすい形で再構成している
  • httpd データフローグラフの nullability 例では、datatoad は Vec<String> データと未コンパイルのクエリで 8.3秒かかり、(u32, u32) データを使う datafrog の例のおよそ 2秒より約4倍遅い
  • reachability 問題では datafrog 実装と同じ数の出力タプルを出したが、一般的な正確性検証が完了した状態ではない

Datalog モデルとシェル構造

  • Datalog は単純な論理規則を書くと、その規則から到達可能なすべての事実を導出する言語である
  • 規則は head と body で構成される
    • 例: tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c).
    • tri、edge は関係で、a、b、c は変数である
    • head に現れる変数は body にも存在しなければならない
  • 事実は body が空の規則として扱う
    • 例: edge(1, 2) :- .
    • 複数の head を使って複数の事実を一度に書ける
  • Datalog の単調性により、規則や事実を追加しても真である事実集合は減少せず、同じ入力規則集合なら規則の順序に関係なく同じ結果に到達する
  • Rust 表現では Rule、Atom、Term の3つの構造が中心となる
    • Rule { head: Vec<Atom>, body: Vec<Atom> }
    • Atom { name: String, terms: Vec<Term> }
    • Term::Var(String) または Term::Lit(String)
  • リテラル保存には String の代わりに Vec<u8> を使う
    • 必要な性質はリテラルの同値性と任意の整列順序である
    • バイト列が String、(u32, u32)、あるいは別の意味を持つかどうかは利用者に委ねられている
  • インタープリタの状態は規則と事実を一緒に保持する
    • rules: Vec<Rule>
    • facts: facts::Facts
  • シェルは入力行を Datalog としてパースすると State::extend と State::update を呼び出し、.list コマンドで各関係名と事実数を表示する

パースと事実保存

  • パーサは parse.rs にあり、Soufflé 文法から持ってきた形を使っている
  • 変数は ? で始まる
  • トークンは ., ,, (, ), :-, ? に限定され、それ以外のテキストは atom または term 名として処理する
  • tokenizer は空白を取り除き、:- を ← に置き換えて単一記号のように走査する
  • 規則パースは、turnstile まで head atom を、period まで body atom を読む方式である
    • atom は名前、左括弧、term の一覧、右括弧で構成される
    • term は ? があれば変数、なければリテラルである
  • 誤った規則は None を返し、現状ではどの部分が間違っているかを詳しく知らせない
  • 否定規則を追加するには Exclamation トークンが必要だが、まだ扱っていない

事実集合のライフサイクル

  • 単純な Vec<Vec<String>> 保存では割り当てが入れ子になり、メモリ管理に不利である
  • datatoad は columnar を使って、Rust 型をフラットなレイアウトの少数の線形割り当てへ変換する
    • 文字列バイト列、文字列境界、事実境界を別々の配列に保存する
  • FactContainer は整列済みかつ重複排除済みの事実一覧を包み、wrapper type によって整列・重複排除という不変条件を示す
  • カラム型コンテナは実質的に append-only のため途中変更には向かず、新しい事実の追加には log-structured merge-tree(LSM) 形式を使う
    • FactLSM { layers: Vec<FactContainer> }
    • 階層サイズが幾何級数的に大きくなるよう管理する
    • サイズが2倍以内の階層同士をマージして、整列・重複排除状態を維持する
  • FactBuilder は、未整列で重複を含みうる active 領域と、整列・重複排除済みの layers を併せ持つ
  • 各関係の事実は3段階を移動する
    • to_add: 新たに到着したが novel かどうか未確認の事実
    • recent: distinct で、まだ処理が必要な事実
    • stable: すでに完全に処理済みの distinct な事実
  • FactSet::advance は recent を stable へ移し、to_add からすでに stable にある事実を除去して新しい recent を作る

規則評価は結合問題

  • Datalog 規則の body は、関係データベースの equi-join とみなせる
  • 三角形規則の例は次のとおり
    • tri(?a, ?b, ?c) :- edge(?a, ?b), edge(?b, ?c), edge(?a, ?c).
  • すべての変数割り当てを直接列挙すると、有限であっても数が多すぎるため、共通変数のキー列を基準に整列してからマージする
  • 実装では body を右から左へ縮約していく
    • 最後の2つの関係を結合して中間関係を作り、再び左側の関係と結合する
    • body atom が1つしかなければ head 形式への変換だけを行う
  • JoinPlan は次の情報を持つ
    • body atom を結合向けに再配置・フィルタリングする bodys
    • 各中間結合の key arity と出力 projection を持つ joins
    • head atom に挿入する座標またはリテラルを表す heads
    • 最後の head 生成結合の arity
  • 現在の計画は単純な right-linear join plan である
  • JoinPlan 生成時には、各変数の leftmost・rightmost 出現位置を使ってどの変数値をいつまで保持するかを判断し、body atom の列を dead、key、value 列に分ける
  • 中核関数は implement_plan(rule, plan, pos, stable, facts) である
    • 新しい規則が追加されたときは stable = true として全事実に対して開始する
    • 既存規則の反復適用では stable = false として新しい導出分だけを計算する

増分結合と merge join

  • 結合は双線形なので、次のように分解できる
    • (A + a) ⋈ (B + b) = A ⋈ B + A ⋈ b + a ⋈ B + a ⋈ b
  • すでに stable 同士で作った A ⋈ B は再計算する必要がない
  • 新しい導出だけが必要なら、3つの結合だけを実行する
    • A ⋈ b
    • a ⋈ B
    • a ⋈ b
  • join_with は stable フラグに応じて stable-stable 結合を含めたり除外したりする
  • 実際の join は、ソート済みの2つの入力を順に走査する merge join である
    • キーが同じなら、そのキーに対するすべての組み合わせに action を呼び出す
    • キーが異なるなら、gallop で次に一致しうる位置まで高速に飛ばす
  • gallop は EmptyHeaded から取り入れたアイデアで、単調条件が真である間は指数的に前進し、その後二分探索的に絞り込む

Nullability 解析の実験

  • 実験データは Graspan プロジェクトのデータで、Google Drive にも残っている
  • データフロー解析の入力には e と n の2つの関係がある
    • n(?a, ?b): 値 ?a が位置 ?b に書き込まれる可能性がある
    • e(?a, ?b): ある位置 ?a の値が別の位置 ?b に移動する可能性がある
  • 到達可能性の規則は次のとおり
    • n(?a, ?c) :- n(?a, ?b), e(?b, ?c) .
  • httpd 入力では、初期 .list は次を示す
    • e: 9,905,624
    • n: 138,331
  • 規則をそのまま実行すると約15秒かかり、n は 9,393,283 件になる
  • 遅い理由の1つは、n を結合キーに合わせて並べ替えた一時関係 .temp-0-0-in が 9,393,283 件まで膨らんだことにある
  • ユーザーが規則を書き換えると性能が改善する
    • m(?loc, ?val) :- n(?val, ?loc) .
    • m(?loc, ?val) :- m(?mid, ?val), e(?mid, ?loc) .
  • 同じ httpd 入力で、書き換え後の2番目の規則は 8.43 秒程度で実行される
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
datatoad 8.43s 24.33s 55.01s
datafrog 1.30s 4.06s 8.03s
  • lnx_kernel の Graspan の数値には * が付いており、論文では総時間をまとめて報告していて、入力識別子の衝突のためそのまま同じ実行と見なすのは難しい
  • 実務で使われるツールと比較するなら、Soufflé のほうがより適切な比較対象かもしれない

Aliasing 解析と手動最適化

  • 2つ目の解析は、Zheng and Rugina の aliasing 解析を Graspan が取り入れたものである
  • 入力関係は2種類ある
    • A(?val, ?loc): ?loc <- ?val
    • D(?val, ?loc): ?loc が *?val の形で使われる
  • 目的は memory alias と value alias を求めることだ
    • memory alias: 2つの lvalue 式が同じメモリ位置を指しうること
    • value alias: 2つの式が同じポインタ値に評価されうること
  • 論文の表記には ^T、^?、^* が登場する
    • ^T: 関係の転置
    • ^?: 任意項
    • ^*: 0回以上の繰り返し
  • Datalog では、^? は規則を2つに分けて表現し、^* は identity 関係を明示的に入れる形で扱う
  • 初期の規則実行には長い時間がかかる
    • 最後の2つの identity 初期化規則を入力した後、686.57 秒、736.34 秒かかった
    • プロセスは 50.13GB を使用した
    • V: 361,947,256
    • M: 92,806,768
    • F: 2,669,647
  • 転置関係 -V、-M、-a、-d を明示的に使って -in 一時関係を除去する
    • 合計 815.92 秒、約 13.6 分
    • メモリは 31.96GB
  • Zheng and Rugina のアプローチは demand-driven で、実際には M だけが必要なので、V を M にインライン展開する
    • -V の 361,947,256 件を作らずに済む
    • メモリは 18.96GB まで減る
  • 繰り返し現れる結合断片を Fd と名付けて再利用し、その後 F の代わりに Fd を直接計算して identity の問題も減らす
  • MFd 中間関係を導入した最終形は、次の結果を出す
    • 実行時間: 119.34 秒
    • メモリ: 5.32GB
    • -M: 92,806,768
    • Fd: 1,858,986
    • MFd: 73,474,947
  • 手動の書き換えだけで、初期の試行と比べてメモリ使用量と実行時間がほぼ10倍改善した
  • 名前付きの中間結果を作れば、望みの bushy-tree join plan をある程度自分で構成できるが、V のように実際には不要な関係に名前を付けると、大きなコストを払って生成することになる

Demand-driven クエリと magic sets

  • demand-driven クエリは、特定の目標事実に必要な部分だけを探索する方式である
  • 近似的な解法として magic sets が使える
    • target literal をクエリに埋め込む変換である
    • すべての d ではなく、関心のある d だけから始める形を考えられるが、単純に適用すると誤る可能性がある
  • magic sets は最適解ではなく、より効率的なアプローチを探すために関連論文をさらに読む予定だ
  • 関連リンクは次のとおり

結合計画最適化とデータ並列 IR

  • Datalog の魅力は、Horn clause そのものよりも、データ並列計算の中核問題である data rendezvous を純粋な形で露わにする点にある
  • 規則 h(x, y, z) :- b1(x, y), b2(y, z) . は、各 y について関連する x と z を1か所に集める問題として見られる
  • データ並列計算の基本動作は、キーごとにレコードを集めてユーザーロジックに渡すことであり、join はその中の選択的ルーティングを表現する
  • 単純な IR は次の opcode を使う
    • Var(String): 名前付きコレクション
    • Map(Action): フィルタ、順列、projection
    • Key(usize): 先頭の何列かをキーとして示す
    • Mul(usize): 同じキー長を持つ複数コレクションを結合する
  • その後 Map と Key は Action.key_arity に統合される
  • Action はリテラルフィルタ、変数等値フィルタ、projection、key arity を保持する
  • 最も単純な出発点は、body atom をすべて cross join し、各 head に filter と projection を載せる方式だが、正しい答えは作れても性能は非常に悪い

e-graph ベースの最適化

  • 最適化には e-graph と equality saturation を使用する
  • 参考資料として egg webpage、以前の記事、egg を使用している
  • term graph は Id が付いた ENode<T> のマップとして表現し、同一ノードを共有することでプログラムをより簡潔に表す
  • 適用した e-graph ルールは 3 つある
    • MulPermute: Mul(k) の入力順列を同値にする
    • MulPartition: Mul(k) を複数の方法で分割して同値にする
    • MapPushdown: Map を Mul(2) の下に押し下げて、キー付きの join 形式を作る
  • 例のルールは次のとおり
    • head(?a, ?b) :- a(?x, ?a), b(?y, ?x), b(?y, ?z), a(?z, ?b) .
  • equality saturation 後の extraction 段階でコストを与える
    • Map のコストは出力カラム数
    • Mul のコストはキーのカラム数と入力の非キーカラム数の合計
    • Var のコストは 0
    • 同点の場合は Map の数、次に Mul の数を最小化する
  • 例で選ばれたプランは、最大 2 つの非相関カラムを持つ wave two で見つかる
    • 入力 a、b に対する map
    • 1 回の join
    • 中間 projection
    • 自分自身との join
    • 最終 projection
  • このプラン探索には release build でも約 40ms かかり、時間の大半は equivalence saturation に使われる

最適化プラン実行の更新

  • 2025-06-29 の更新で最適化されたプラン実行を実装した
  • プランは Vec<ENode<Op>> として出力されるが、実際の実行では各ノードを独立して実行しない
  • 意図した実行方式は次のとおり
    • 各 Var について、依存する複数の Map を 1 回の外部コレクション走査で適用する
    • 各 Mul について、依存する複数の Map を 1 回の join 走査で適用する
  • Op::Map(action) は直接実行される演算というより、依存先の演算にキューイングされる作業である
  • そのために TempAction を導入した
    • リテラルフィルタ
    • 変数同値性フィルタ
    • カラム参照または文字列リテラルを持てる projection
  • 実行プランの準備段階では body と head を分離し、Map アクションを入力ノードごとに集める
  • Var 実行での名前処理は 3 つのケースに分かれる
    • head 生成は head 関係名に書き込む
    • identity 変換は既存の入力名を再利用する
    • 自明でない変換は .temp-* 一時名に保存する
  • Mul(2) の実行では 2 つの入力の key arity と名前を確認し、join_with を呼び出して複数の builder に結果を蓄積する
  • 複雑な aliasing の例では、最適化されたプラン実行は 114.28 秒で、以前の 119 秒台より約 5 秒速かったが、理由ははっきりしない
  • multi-rule 最適化はまだ実装されておらず、プランというアプローチ自体を見直す必要があるかもしれない

ファクト表現の最適化

  • 50GB を 5GB に減らしたものの、なお必要以上に約 10 倍のメモリを使っていると見ている
  • 大きな関係 -M の largest layer は 57,289,225 個のファクトを保持し、約 2,098,253,766 バイトを使用する
    • ファクト境界: 458,313,800 バイト
    • term 境界: 916,627,600 バイト
    • 実際のバイトデータ: 723,312,366 バイト
  • 1 つ目の最適化は arity が一定である点を利用すること
    • すべてのファクトが 2 カラムなら、ファクト境界は stride と length だけで表現できる
    • 458MB 規模の境界データを事実上取り除ける
  • 2 つ目の最適化は term の長さを揃えること
    • 数値を 7 桁固定幅文字列にすると、term 境界も stride と length で表現できる
    • その代わり実際のバイト数は増える可能性がある
  • 3 つ目の最適化は数値をテキストではなく binary で表現すること
    • 7 桁の数値は u32 の 4 バイトに収まる
    • 3 バイトにも収まるので、57,289,225 × 2 × 3 = 343,735,350 バイトになる
    • 約 2GB から約 350MB に減り、約 6.10 倍の削減になる
  • 先頭 term の繰り返しを圧縮するとさらに減る
    • 57,289,225 個のファクトがあるが、distinct な first term は 1,147,612 個しかない
    • (Term, Term) の代わりに (Term, [Term]) 形式で保存すると、largest layer は 184,491,407 バイト程度まで減る
    • 当初の 2GB と比べて約 11.37 倍の削減になる
  • 2025-07-02 の更新で 1 次最適化が適用された
    • largest batch は理論値 343,735,350 バイトに 32 バイトを加えた 343,735,382 バイトになった
    • 実行時間は約 115 秒から約 95 秒に下がり、約 20% 改善した

Layered trie 表現

  • 2025-07-20 の更新で layered trie が動作可能になった
  • row-oriented 表現と column-oriented layered trie 表現を比較している
    • toad-row
    • toad-col
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
toad-row 3.88s 11.30s 25.67s
toad-col 3.47s 11.94s 23.09s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
graspan 8.4h 6.0h* 1.7h*
toad-row 28.21s 28.25s 7.62s
toad-col 19.39s 21.96s 9.48s
datafrog UNK UNK UNK
  • layered trie は、ソート済みの row 表現で前方カラムの繰り返しを抑える方式である
  • 各カラムは値リストのリストである
    • 各リストは前のカラム prefix に対応する、ソート済みで distinct な値の一覧である
    • あるカラムのリスト数は、1 つ前のカラムの総アイテム数に等しい
  • ツリーのように見なせるが、実装上は実際にカラムとして保持している
  • 利点は prefix 単位で検索・join・差集合・マージを実行できる点にある
  • distinct 値がほとんどなく、行全体を一度に見るほうがよい場合には、row-oriented アプローチのほうが有利なことがある
  • 共通抽象化として FactContainer trait を導入した
    • form
    • len
    • apply
    • join
    • except
    • merge
  • apply は再帰の代わりに明示的な stack で各 layer の range を追跡し、行を作って action に渡す
  • align は 2 つの layered trie の prefix を揃えて見る共通ヘルパーである
    • Ordering::Less: self にのみある範囲
    • Ordering::Greater: other にのみある範囲
    • Ordering::Equal: arity 長の prefix が両側で共通
  • join、except、merge はすべて align の上に実装されている
    • join は共通 prefix で残りの extension を展開して cross join する
    • except は self のみにある範囲を TrieBuilder で graft する
    • merge は self-only、other-only、equal の各範囲を適切に 1 回ずつ graft する

固定幅最適化と性能

  • 固定幅 [u8; 4] に upgrade できる場合、比較性能が大きく向上する
  • layered trie はカラムごとに固定幅最適化を適用できるため、長期的には row より有利になる可能性がある
  • except と merge には upgrade・downgrade を容易に適用できたが、join への適用は Rust の型の問題でより難しかった
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
toad-row 3.88s 11.30s 25.67s
^-- +opt 3.11s 9.49s 19.83s
toad-col 3.47s 11.94s 23.09s
^-- +opt 2.55s 9.13s 15.95s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
graspan 8.4h 6.0h* 1.7h*
toad-row 28.21s 28.25s 7.62s
^-- +opt 23.31s 23.08s 6.73s
toad-col 19.39s 21.96s 9.48s
^-- +opt 14.26s 16.45s 8.33s
datafrog UNK UNK UNK
  • 現在の時間のおよそ2/3はjoinの下で消費されている
  • join最適化には少なくともさらに2倍程度の余地があると見ている
  • 単に inner loop を並べ替える試みでは、測定可能な改善は得られなかった

コンパイル済みコード水準へ特化する

  • 同じ長さの term と同じ arity の fact を検出できれば、Vec<u8>をVec<[[u8; B]; T]>のように見なせる
  • この形にすると Rust がデータの形をよりよく把握でき、bounds・length チェックのコストを減らし、とくに比較を安くできる
  • 比較は datatoad の複数の箇所で使われる
    • fact batch のソート・重複除去
    • batch のマージ
    • join key のマージ
    • 新しい fact を既存の fact と比較してフィルタリング
  • ベースライン性能は次のとおり
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
datatoad 7.44s 17.26s 42.25s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
graspan 8.4h 6.0h* 1.7h*
datatoad 101.24s 96.36s 20.20s
datafrog UNK UNK UNK
  • ソート最適化は、Vec<u8>をVec<[u8; 8]>へunsafeに transmute して sort・dedup する方式で実験した
dataflow httpd psql lnx_kernel
dt-orig 7.44s 17.26s 42.25s
dt-sort 4.99s 13.55s 32.15s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
dt-orig 101.24s 96.36s 20.20s
dt-sort 52.99s 53.19s 11.20s
datafrog UNK UNK UNK
  • マージ最適化は、2つの入力を連結したあと sort・dedup する単純な方式で実装した
dataflow httpd psql lnx_kernel
dt-orig 7.44s 17.26s 42.25s
dt-sort 4.99s 13.55s 32.15s
dt-both 3.71s 11.23s 23.58s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
dt-orig 101.24s 96.36s 20.20s
dt-sort 52.99s 53.19s 11.20s
dt-both 31.32s 30.08s 8.56s
datafrog UNK UNK UNK
  • まだ datafrog のコンパイル済み性能には到達していない
  • 残っている比較コストは join と antijoin にもあり、trie ベースの構造へ移行しながら同じ最適化の機会を再検討する予定だ
  • unsafeを取り除く方法を探しており、unsafe コードは避けるべきだという結論も付け加えている

まだ残っている作業

  • ディスクへの spill

    • columnarストレージは少数の大きな割り当てで構成される
    • 生成時にメモリではなくファイルへ書き出し、memory map で再利用できる

  • 分散評価

    • join、重複除去、distinctness check はキーの同値性に基づく
    • キーとそれに対応するデータを複数の worker に分散できる
    • timely_communicationで複数プロセスまで拡張できる

  • ストリーミング規則評価

    • 現在の join は二項 join と materialized output を使っている
    • 必要なインデックスがあれば、内部状態を materialize しないプランを作れる
    • worst-case optimal join もここで扱う予定だ

  • custom representation の特化

    • transitive closure を検出して strongly connected component decomposition に特化するアイデアがある
    • equivalence relation には union-find データ構造を使える
    • bddbddbと factorized databasesも関連トピックとして扱っている

  • 関連 fact の検索

    • demand transformを理解して適用する必要がある
    • 対話型 Datalog 探索には必要な変換だと見ている

関連記事

1件のコメント

 
GN⁺ 2025-06-16
Hacker News のコメント

  • この記事が1位に上がっているのを見ると面白い
    いま Differential Datalog と Rust でリアルタイムストラテジーゲームを作っていて、ゲームロジックは DDL に管理させている
    たいていは新しいアイデアに触れて、終わりのないヤクの毛刈りをしてみるための口実に近い
    https://github.com/vmware-archive/differential-datalog

    • ddlog で作るクールなデモのように見える
      ちなみに ddlog チームは今では Feldera を創業しており、Rust から DBSP を直接使うことも検討に値する
      https://github.com/feldera/feldera
    • 元記事のリポジトリと、Rust アナライザーを動かすクレートである salsa を組み合わせると、フランケンシュタイン式の differential datalog を作れるのか気になる
      https://github.com/salsa-rs/salsa
    • 実装状況がどうなのか、どこまで行けるのか気になる
      DDLog はもはや活発にメンテナンスされていない状態なので、なおさら興味深い

  • 「私、悪名高い悪党は、ずっと前に受けるべきだった報いを受けに行くのだと半ば確信しながら招待された。」——今年読んだ技術ブログ記事の中で 最高の書き出し だ
    語り手の差し込みも素晴らしく、これほど技術的に深く、それでいて楽しく読める記事は珍しい
    エイリアスクエリを最適化する旅が探偵小説のように感じられ、読者も一緒に 50GB のメモリ使用量 にうめき、5GB に減ったときには歓声を上げることになる
    コードも文章も素晴らしい

  • mangle datalog を Rust に移植する作業を少し進めていた
    https://github.com/google/mangle/tree/main/rust にあり、Go 実装と同じリポジトリに入っている
    優先度が高くないうえにセカンドシステム症候群もあり、進捗は遅い
    Mangle Rust はメモリマッピングでディスク上のファクトを読み書きしながら任意サイズのデータを扱う方向で、Go 実装はインメモリ方式だ
    この記事は Datalog のパースに加えて LSM ツリー も扱っていて良く、datafrog 関連の資料よりずっと追いやすい
    Rust には ascent や crepe のように手続き型マクロを使う Datalog 実装が多いが、実行時にクエリを受け取るのは難しいという欠点がある
    クエリとプログラムが固定された静的解析用途なら、手続き型マクロのアプローチのほうが良いかもしれない

  • 現在の Datalog 復興 が弱まりつつあるように見える中でも、コアな愛好者たちが踏みとどまり続けているのはうれしい
    最近の Datalog 2.0 カンファレンスは以前よりかなり小規模で、2回目の HYTRADBOI カンファレンスでも Datalog の比重は低かった
    1回目の HYTRADBOI では、投稿の4分の1が Datalog に関連していた
    他の人たちが最近の Datalog プロジェクトを共有しているのも励みになる
    今は大規模なソフトウェア移行に備えて、レガシー SQL データベース向けの データ品質パイプライン を作っている
    クエリをうまく構造化すれば非常に読みやすいので、データ品質問題を特定して見つけるには、Datalog のほうが SQL よりずっと有用だと思う

    • 大きな方向性には同意するとしても、Datalog 2.0 の少ない参加者数を Datalog 衰退の代表例と見るのは難しい
      Datalog 2.0 は比較的知名度の低い欧州の学会 LPNMR の併設ワークショップで、その学会がたまたま Dallas で開かれたという状況だった
      実際に参加したときもイベントはやや閑散としているように感じられ、ワークショップに論文も出したが、その分野の人たちはあまり見かけなかった
      例外的に、Nemo ソルバーを紹介していた欧州勢は目立っていた
      今年の参加者が少なかったことは、Datalog 実装への興味不足というより、もともと名声が大きくない学会の併設ワークショップであり、本会議も ICLP だったという点をよく示していると思う
      もちろん、純粋な Datalog エンジン実装には新規性がほとんど残っていないという大きな主張に反論したいわけではない
      研究領域はすでにはるか先へ進み、ストリーミング（HydroFlow）、選択（Dusa）、一般的な chase に近いもの（Egglog の chase エンジン）といった、よりエキゾチックな問題へ移っている
      バニラ Datalog が退屈だという点にはおおむね異論はないが、単調な前方飽和と Horn 節は、性能エンジニアリングの地形がよく理解された豊かな基準線なので、半環や Z-set のようなより興味深い理論を積み上げるのに適している

  • 状態機械とパース部分が面白かったなら、Rob Pike の昔の発表 Lexical Scanning in Go もおすすめ
    https://www.youtube.com/watch?v=HxaD_trXwRE
    Go で書かれているが、大部分は他の言語にも簡単に適用できる
    Rust、Zig、Go のような現代的な言語が Unicode/rune/書記素クラスタ をネイティブにサポートしているのは良い
    Java、.NET、C++ やスクリプト言語と比べると、多くの問題がそのまま消えてなくなる

  • 著者の Datalog への取り組みは全体として好きだが、入門資料で 二項結合 を教えないでほしい
    理想的なケースを外れると内部がすぐに汚くなり、一般的な結合方式のメソッドのほうが頭の中でずっと一般化しやすかった
    https://en.wikipedia.org/wiki/Worst-case_optimal_join_algorithm

  • かなり前に学生時代に Prolog に少し触れたことがあり、何に使われ、何に役立つのかは大まかに分かるものの、深く理解しているわけではない。
    その後 Datalog がすごいという話をずっと聞いているが、肝心の Datalog が Prolog より何を改善しているのかがいまひとつつかめない。
    先ほど Wikipedia の Datalog ページをざっと見たところ、Prolog は性能が比較的悪く、Datalog は表現力と機能を減らす代わりに性能を大きく改善し、より大きなデータセットと、より並列化された処理を可能にしているように見える。
    チューリング完全性がなくなることも含まれるようだが、これが核心なのか、完全に見当違いなのかが気になる。

    • 私の知る限り、Prolog は関係だけをエンコードすれば答えを見つけてくれる宣言型のように見えるが、実際には規則の順序に大きく依存し、“cut” のような追加指示も必要になる。
      cut は無駄な計算を防ぐだけでなく、結果にも影響し得る。
      一方 Datalog は、全体として構文の異なるリレーショナルデータベースに近い。
    • Datalog はより単純で、チューリング完全ではなく、記憶では前向き推論を使うため、性能とメモリ特性に連鎖的な影響を与える。
      Prolog では些細だが巨大な探索空間も、Datalog ではメモリを食いすぎて表現自体が不可能な場合がある。
      Datalog は CVT 付きの通勤用車で、Prolog は F1 カーに近い。
      改善というより、人々が自分の足を吹き飛ばさないように Prolog を部分的に切り詰めたものに近く、他のアプリケーションに実装・組み込みするのもはるかに簡単だ。
      Prolog に慣れているなら、Datalog はたいてい窮屈に感じるはずだ。
      call/3 もなく、term/goal expansion もなく、Datalog は基本的に Prolog の最小公倍数的な機能を取り出し、対話的なデータベース検索に使うよう設計されたものと言える。
      速い Datalog コードは書きやすいが、上限もずっと低い。
      Prolog も並行性を許す形で書けるが、実装を理解している必要がある中級者向けの課題だ。
      Guarded Horn Clauses とその派生言語は、そうした部分を形式化しようとして開発されたが、Prolog 以後の日本側の発展は非常に難解だ。
      Prolog の性能は、プログラマ、使う実装、使う場所に大きく左右される。
      Lisp と同じく、Prolog もコンパイル時に DSL からネイティブ機械語を生成するのに使える。
      基盤実装がどう動くのかを理解し、その性質に沿ってコードを書けば十分速い。
      ただしそのためには、1つの実装で数年間 Prolog コードを書く必要がある。
      Prolog コンパイラ最適化の研究も多く、独占的な実装例もある。
      http://logicprogramming.stanford.edu/readings/ullman.pdf
      https://www.ueda.info.waseda.ac.jp/AITEC_ICOT_ARCHIVES/ICOT/Museum/IFS/abst/078.html
      https://www.sciencedirect.com/science/article/pii/S0743106696889813
      https://link.springer.com/content/pdf/10.1007/3-540-18024-9_26.pdf
      https://sicstus.sics.se/

  • Datalog と Rust を使いたいなら、cozodb は Rust で書かれており、Datalog のクエリ構文も提供している。

    • Cozodb はよさそうに見えるが、ほぼ非アクティブな状態に見える。
      2024年11月ごろに調べていたとき、SQLite ストレージバックエンドで簡単に改善できる点をいくつか見つけた。
      https://github.com/cozodb/cozo/issues/285
    • Cozodb はドキュメントどおり、おおむねうまく動作し、扱っていて楽しかった。
      プログラムの静的解析にも使い、内部ではソート木と型の手法を使っている。
      ドキュメントは、ブログの段階的な説明と最初に比較してみるには十分で、特にクエリ最適化の取り組みが興味深い。
      ただし Rust でインメモリに作業しない場合はデータのシリアライズコストが大きく、プロジェクトは好意的に見ても静かな状態だ。

  • 以前、Clojure ファンたちが Datalog は SQL より優れていて、リレーショナルデータベースがどれも SQL を使っているのは残念だと言っていた
    なぜそう考えていたのかは、十分に掘り下げられなかった

    • 基本的に Datalog は SQL よりはるかに冗長でなく、ビューを分離するコストがずっと小さく、推移閉包を圧倒的にうまくサポートする
      http://canonical.org/~kragen/binary-relations は単純な非再帰クエリから始まったが、SQL への翻訳はすでに犯罪的で、きちんと分離した SQL 解法は死刑ものだった
      最近の ANSI SQL には再帰機能が追加され、もはや完全に不可能ではなくなったが、大きな欠点が3つある
      第一に、うっかり SQL をチューリング完全にしてしまった一方で、Datalog クエリは終了が保証される
      第二に、依然として使うにはひどく鈍重である
      第三に、第一の理由のため完全には実装されないことが多く、安心して使いにくい
    • Clojure/Datomic 方言は理解しにくいが、大きな方向性には同意する
      オンラインで親切なノートブック環境として Datalog を触ってみるなら Percival を勧める
      https://percival.ink/
      Datalog 実装全般における「ANSI SQL」に相当する標準はないが、核となる考え方を身につければ、他の Datalog もそれほど難しくない
      Datalog を SQLite にコンパイルする Percival のフォークも始めたので、両者が同じことをどう表現するのか見たいなら確認できる
      https://percival.jake.tl/
      集約とより高度な join はまだ未完成だが、基本形はうまく動作する
      Logica は Google の研究者が作った、はるかに本格的で完成度の高い Datalog→SQL コンパイラで、BigTable、DuckDB、いくつかの SQL 方言へコンパイルする
      https://logica.dev/
      Datalog が一桁以上簡単になる領域は、再帰クエリ/ルールを扱うときである
      SQL でも可能だが、ストローでプレイドーを吸うような感覚に近い
      Frank の Materialize.com には、従来の ANSI SQL の再帰方式よりはるかに優れた「WITH MUTUALLY RECURSIVE」という SQL 形式があり、Notion でページ読み込みクエリとデータ同期の用途として評価中である
      https://materialize.com/blog/recursion-in-materialize/
      Feldera にも再帰ビュー向けの似た形式がある
      https://www.feldera.com/blog/recursive-sql-queries-in-feldera
      Feldera は各「ルール」やサブビューを1つの巨大な文にすべて入れるのではなく、別々の文にできるので気に入っている
      テストしていて見た主な欠点は、Feldera の SQL 方言には Apache Calcite から受け継いだ制約がかなりある点で、Materialize の SQL 方言は PostgreSQL 互換性に非常に熱心に合わせようとしている

  • 新しい McSharry の記事とは素晴らしい
    最後に確認したとき、VMWare は differential datalog から離れたように見えた

    • Differential Datalog チームは Feldera を創業した
      https://www.feldera.com/
      differential Datalog から differential SQL に変えたようだが、おそらく Datalog は本当に売りにくいと気づいたからだと思う