Membangun Mesin Datalog Interaktif dengan Rust

 (github.com/frankmcsherry)
1 poin oleh GN⁺ 2025-06-16 | 1 komentar | Bagikan ke WhatsApp
  • Berangkat dari keterbatasan kegunaan dan performa alat Datalog yang terlihat dalam lokakarya pemrograman logika, eksperimen datatoad, sebuah shell Datalog interaktif berbasis Rust, dimulai
  • datatoad menargetkan struktur yang dapat menambahkan aturan saat berjalan dan terus menurunkan fakta baru, serta mengurangi biaya penanganan duplikasi himpunan fakta dengan penyimpanan columnar dan lapisan LSM
  • Evaluasi aturan memproses body Datalog dengan mengubahnya menjadi masalah join, lalu memisahkan evaluasi penuh dan evaluasi inkremental berdasarkan status stable untuk menghindari join stable-stable yang sudah dihitung
  • Dalam eksperimen dataset Graspan, hanya dengan penulisan ulang aturan secara manual dan pengenalan relasi perantara, analisis aliasing berkurang dari 736,34 detik dan 50,13 GB menjadi 119,34 detik dan 5,32 GB
  • Pekerjaan berikutnya berlanjut ke optimisasi rencana join berbasis e-graph, layered trie, representasi byte berlebar tetap, spill ke disk, evaluasi terdistribusi, streaming join, dan demand transform

Masalah yang ingin dipecahkan datatoad

  • Pada lokakarya pemrograman logika akhir pekan Memorial Day, ketidaknyamanan alat Datalog untuk analisis program tampak menonjol, dan hal ini memicu upaya membuat implementasi Datalog yang sederhana, layak dipakai, dan cepat
  • Target implementasinya bukan eksekutor contoh statis, melainkan shell Datalog interaktif
    • Dapat memuat fakta dalam jumlah besar
    • Dapat menambahkan aturan baru saat berjalan
    • Terus mencerminkan hasil aturan yang ditambahkan ke dalam status yang sudah ada
  • Kodenya dapat diikuti di repository datatoad
  • datafrog yang sudah ada menyediakan algoritme inti mesin Datalog, tetapi karena bentuknya mengharuskan pengguna merangkainya sendiri, datatoad menyusun ulang ide yang sama menjadi bentuk yang lebih mudah digunakan
  • Dalam contoh nullability pada grafik dataflow httpd, datatoad membutuhkan 8,3 detik dengan data Vec<String> dan query yang tidak dikompilasi, sekitar 4 kali lebih lambat daripada contoh datafrog yang menggunakan data (u32, u32) dan berjalan sekitar 2 detik
  • Pada masalah reachability, datatoad menghasilkan jumlah tuple keluaran yang sama dengan implementasi datafrog, tetapi verifikasi kebenaran umum belum selesai

Model Datalog dan struktur shell

  • Datalog adalah bahasa yang, ketika aturan logika sederhana ditulis, menurunkan semua fakta yang dapat dicapai dari aturan tersebut
  • Aturan terdiri dari head dan body
    • Contoh: tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c).
    • tri dan edge adalah relasi, sedangkan a, b, c adalah variabel
    • Variabel yang muncul di head juga harus ada di body
  • Fakta diperlakukan sebagai aturan dengan body kosong
    • Contoh: edge(1, 2) :- .
    • Beberapa head dapat digunakan untuk menulis beberapa fakta sekaligus
  • Karena monotonisitas Datalog, menambahkan aturan atau fakta tidak akan mengurangi himpunan fakta yang benar, dan himpunan aturan input yang sama akan mencapai hasil yang sama terlepas dari urutan aturan
  • Representasi Rust berpusat pada tiga struktur: Rule, Atom, dan Term
    • Rule { head: Vec<Atom>, body: Vec<Atom> }
    • Atom { name: String, terms: Vec<Term> }
    • Term::Var(String) atau Term::Lit(String)
  • Untuk penyimpanan literal, digunakan Vec<u8> alih-alih String
    • Sifat yang diperlukan adalah kesetaraan literal dan urutan pengurutan arbitrer
    • Apakah byte tersebut bermakna sebagai String, (u32, u32), atau hal lain diserahkan kepada pengguna
  • Status interpreter menyimpan aturan dan fakta bersama-sama
    • rules: Vec<Rule>
    • facts: facts::Facts
  • Shell, setelah mem-parsing baris input sebagai Datalog, memanggil State::extend dan State::update, lalu dengan perintah .list menampilkan nama setiap relasi dan jumlah faktanya

Parsing dan penyimpanan fakta

  • Parser berada di parse.rs dan menggunakan bentuk yang diambil dari sintaks Soufflé
  • Variabel diawali dengan ?
  • Token dibatasi pada ., ,, (, ), :-, ?, sedangkan teks lainnya diperlakukan sebagai nama atom atau term
  • Tokenizer menghapus spasi putih dan mengganti :- dengan ← agar dapat dipindai seperti satu simbol
  • Parsing aturan dilakukan dengan membaca atom head hingga turnstile, lalu atom body hingga period
    • Atom terdiri dari nama, kurung kiri, daftar term, dan kurung kanan
    • Term menjadi variabel jika ada ?, dan menjadi literal jika tidak ada
  • Aturan yang tidak valid mengembalikan None, dan saat ini belum memberi tahu secara rinci bagian mana yang salah
  • Untuk menambahkan aturan negasi diperlukan token Exclamation, tetapi itu belum ditangani

Siklus hidup himpunan fakta

  • Penyimpanan sederhana Vec<Vec<String>> memiliki alokasi bertingkat sehingga tidak menguntungkan untuk manajemen memori
  • datatoad menggunakan columnar untuk mengubah tipe Rust menjadi sejumlah kecil alokasi linear dengan layout datar
    • Byte string, batas string, dan batas fakta disimpan dalam array terpisah
  • FactContainer membungkus daftar fakta yang sudah diurutkan dan dihapus duplikatnya, serta melalui wrapper type mengisyaratkan invariant pengurutan dan penghapusan duplikat
  • Karena container kolumnar pada dasarnya append-only sehingga tidak cocok untuk perubahan di tengah, penambahan fakta baru menggunakan bentuk log-structured merge-tree (LSM)
    • FactLSM { layers: Vec<FactContainer> }
    • Dikelola agar ukuran lapisan tumbuh secara geometris
    • Lapisan-lapisan yang ukurannya dalam rentang 2 kali digabung untuk mempertahankan keadaan terurut dan tanpa duplikat
  • FactBuilder memiliki area active yang belum diurutkan dan dapat berisi duplikat, bersama layers yang sudah diurutkan dan dihapus duplikatnya
  • Fakta pada setiap relasi berpindah melalui tiga tahap
    • to_add: fakta yang baru tiba tetapi belum diperiksa apakah novel
    • recent: fakta yang distinct dan masih perlu diproses
    • stable: fakta distinct yang sudah diproses sepenuhnya
  • FactSet::advance memindahkan recent ke stable, lalu menghapus dari to_add fakta yang sudah ada di stable untuk membuat recent baru

Evaluasi aturan adalah masalah join

  • Body aturan Datalog dapat dilihat sebagai equi-join dalam basis data relasional
  • Contoh aturan segitiga adalah sebagai berikut
    • tri(?a, ?b, ?c) :- edge(?a, ?b), edge(?b, ?c), edge(?a, ?c).
  • Jika semua assignment variabel didaftarkan secara langsung, jumlahnya akan terlalu besar meskipun berhingga, sehingga relasi diurutkan berdasarkan kolom kunci dari variabel bersama lalu digabung
  • Implementasi mereduksi body dari kanan ke kiri
    • Dua relasi terakhir dijoin untuk membuat relasi perantara, lalu dijoin lagi dengan relasi kiri
    • Jika hanya ada satu body atom, ia hanya diubah ke bentuk head
  • JoinPlan memuat informasi berikut
    • bodys yang menata ulang dan memfilter body atom agar sesuai untuk join
    • joins yang memuat key arity dan projection keluaran setiap join perantara
    • heads yang menunjukkan koordinat atau literal untuk dimasukkan ke head atom
    • arity dari join pembentukan head terakhir
  • Rencana saat ini adalah right-linear join plan sederhana
  • Saat membuat JoinPlan, posisi kemunculan leftmost dan rightmost tiap variabel digunakan untuk menentukan sampai kapan nilai variabel harus dipertahankan, lalu kolom body atom dibagi menjadi kolom dead, key, dan value
  • Fungsi intinya adalah implement_plan(rule, plan, pos, stable, facts)
    • Ketika aturan baru ditambahkan, ia dimulai dengan stable = true terhadap seluruh fakta
    • Dalam penerapan berulang aturan yang sudah ada, ia menghitung hanya turunan baru dengan stable = false

Join inkremental dan merge join

  • Join bersifat bilinear sehingga dapat diuraikan seperti berikut
    • (A + a) ⋈ (B + b) = A ⋈ B + A ⋈ b + a ⋈ B + a ⋈ b
  • A ⋈ B yang sudah dibuat antarbagian stable tidak perlu dihitung ulang
  • Jika hanya derivasi baru yang diperlukan, cukup lakukan tiga join
    • A ⋈ b
    • a ⋈ B
    • a ⋈ b
  • join_with menyertakan atau mengecualikan join stable-stable sesuai flag stable
  • join sebenarnya adalah merge join yang menelusuri dua input terurut secara berurutan
    • Jika kuncinya sama, action dipanggil untuk semua kombinasi pada kunci tersebut
    • Jika kuncinya berbeda, gallop dipakai untuk melompat cepat ke titik kemungkinan kecocokan berikutnya
  • gallop adalah ide yang diambil dari EmptyHeaded: ia maju secara eksponensial selama kondisi monoton bernilai benar, lalu mempersempitnya dengan cara seperti pencarian biner

Eksperimen analisis nullability

  • Data eksperimen berasal dari proyek Graspan, dan masih tersedia juga di Google Drive
  • Input analisis dataflow memiliki dua relasi, e dan n
    • n(?a, ?b): nilai ?a dapat digunakan di lokasi ?b
    • e(?a, ?b): nilai dari suatu lokasi ?a dapat berpindah ke lokasi lain ?b
  • Aturan reachability adalah sebagai berikut
    • n(?a, ?c) :- n(?a, ?b), e(?b, ?c) .
  • Pada input httpd, .list awal menunjukkan hal berikut
    • e: 9.905.624
    • n: 138.331
  • Menjalankan aturan secara langsung memakan waktu sekitar 15 detik, dan n menjadi 9.393.283 entri
  • Salah satu alasan lambatnya adalah relasi sementara .temp-0-0-in, yang menyusun ulang n agar sesuai dengan kunci join, membesar hingga 9.393.283 entri
  • Performa membaik jika pengguna menulis ulang aturannya
    • m(?loc, ?val) :- n(?val, ?loc) .
    • m(?loc, ?val) :- m(?mid, ?val), e(?mid, ?loc) .
  • Pada input httpd yang sama, setelah ditulis ulang, aturan kedua berjalan sekitar 8,43 detik
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
datatoad 8.43s 24.33s 55.01s
datafrog 1.30s 4.06s 8.03s
  • Angka Graspan untuk lnx_kernel diberi tanda *; makalahnya melaporkan total waktu sekaligus, dan karena benturan identifier input, sulit menganggapnya sebagai eksekusi yang persis sama
  • Untuk perbandingan dengan alat yang dipakai praktisi, Soufflé mungkin menjadi target yang lebih tepat

Analisis aliasing dan optimasi manual

  • Analisis kedua adalah analisis aliasing Zheng and Rugina yang diadopsi oleh Graspan
  • Ada dua relasi input
    • A(?val, ?loc): ?loc <- ?val
    • D(?val, ?loc): ?loc digunakan dalam bentuk *?val
  • Tujuannya adalah memperoleh memory alias dan value alias
    • memory alias: dua ekspresi lvalue dapat menunjuk ke lokasi memori yang sama
    • value alias: dua ekspresi dapat dievaluasi menjadi nilai pointer yang sama
  • Notasi di makalah memunculkan ^T, ^?, ^*
    • ^T: transpose relasi
    • ^?: term opsional
    • ^*: pengulangan nol kali atau lebih
  • Dalam Datalog, ^? diekspresikan dengan memecahnya menjadi dua aturan, sedangkan ^* ditangani dengan memasukkan relasi identity secara eksplisit
  • Eksekusi aturan awal memakan waktu lama
    • Setelah dua aturan inisialisasi identity terakhir dimasukkan, masing-masing memakan waktu 686,57 detik dan 736,34 detik
    • Proses menggunakan 50,13 GB
    • V: 361.947.256
    • M: 92.806.768
    • F: 2.669.647
  • Dengan memakai relasi transpose -V, -M, -a, -d secara eksplisit, relasi sementara -in dihilangkan
    • Total 815,92 detik, sekitar 13,6 menit
    • Memori 31,96 GB
  • Pendekatan Zheng and Rugina bersifat demand-driven dan dalam praktiknya hanya M yang diperlukan, sehingga V di-inline ke M
    • Tidak membuat 361.947.256 entri -V
    • Memori turun menjadi 18,96 GB
  • Potongan join yang berulang diberi nama Fd untuk digunakan kembali, lalu setelah itu Fd dihitung langsung alih-alih F, sehingga masalah identity juga berkurang
  • Bentuk final yang memperkenalkan relasi antara MFd memberikan hasil berikut
    • Waktu eksekusi: 119,34 detik
    • Memori: 5,32 GB
    • -M: 92.806.768
    • Fd: 1.858.986
    • MFd: 73.474.947
  • Hanya dengan penulisan ulang manual, memori dan waktu eksekusi membaik hampir 10 kali dibanding upaya awal
  • Jika membuat hasil antara yang diberi nama, kita bisa menyusun sendiri join plan bushy-tree yang diinginkan sampai batas tertentu; tetapi jika memberi nama pada relasi yang sebenarnya tidak diperlukan seperti V, relasi itu akan dibuat dengan biaya besar

Kueri demand-driven dan magic sets

  • Kueri demand-driven adalah cara menelusuri hanya bagian yang diperlukan untuk fakta target tertentu
  • Sebagai solusi aproksimatif, magic sets dapat digunakan
    • Ini adalah transformasi yang menanamkan literal target ke dalam kueri
    • Kita bisa membayangkan ekspresi yang dimulai hanya dari d yang diminati, bukan semua d, tetapi jika diterapkan secara sederhana hasilnya bisa salah
  • Magic sets bukan jawaban optimal, dan penulis berencana membaca lebih banyak makalah terkait untuk mencari pendekatan yang mungkin lebih efisien
  • Tautan terkait adalah sebagai berikut

Optimasi rencana join dan IR paralel data

  • Daya tarik Datalog bukan pada Horn clause itu sendiri, melainkan pada kemampuannya menyingkap secara murni masalah inti komputasi paralel data, yaitu data rendezvous
  • Aturan h(x, y, z) :- b1(x, y), b2(y, z) . dapat dipandang sebagai masalah mengumpulkan x dan z yang terkait untuk setiap y di satu tempat
  • Operasi dasar komputasi paralel data adalah mengumpulkan record berdasarkan kunci dan menyerahkannya ke logika pengguna, sedangkan join mengekspresikan routing selektif di antaranya
  • IR sederhana menggunakan opcode berikut
    • Var(String): koleksi bernama
    • Map(Action): filter, permutasi, projection
    • Key(usize): menandai beberapa kolom terdepan sebagai kunci
    • Mul(usize): menggabungkan beberapa koleksi dengan panjang kunci yang sama
  • Setelah itu, Map dan Key digabungkan menjadi Action.key_arity
  • Action memuat filter literal, filter kesetaraan variabel, projection, dan key arity
  • Titik awal paling sederhana adalah melakukan cross join pada semua atom body lalu menambahkan filter dan projection untuk setiap head; ini memang menghasilkan jawaban benar, tetapi performanya sangat buruk

Optimisasi berbasis e-graph

  • Optimisasi menggunakan e-graph dan equality saturation
  • Referensi yang digunakan meliputi egg webpage, tulisan sebelumnya, dan egg
  • Term graph direpresentasikan sebagai map berisi ENode<T> yang diberi Id, dan node yang sama dibagikan agar program dapat dinyatakan lebih ringkas
  • Ada tiga aturan e-graph yang diterapkan
    • MulPermute: membuat permutasi input Mul(k) menjadi ekuivalen
    • MulPartition: membagi Mul(k) dengan berbagai cara dan menjadikannya ekuivalen
    • MapPushdown: mendorong Map ke bawah Mul(2) untuk membentuk join yang memiliki key
  • Contoh aturannya sebagai berikut
    • head(?a, ?b) :- a(?x, ?a), b(?y, ?x), b(?y, ?z), a(?z, ?b) .
  • Setelah equality saturation, biaya diberikan pada tahap extraction
    • Biaya Map adalah jumlah kolom output
    • Biaya Mul adalah jumlah kolom key ditambah jumlah kolom non-key dari input
    • Biaya Var adalah 0
    • Jika seri, jumlah Map diminimalkan, lalu jumlah Mul
  • Pada contoh, rencana yang dipilih ditemukan di wave two dengan maksimal dua kolom tak berkorelasi
    • Map untuk input a dan b
    • Satu kali join
    • Projection perantara
    • Join dengan dirinya sendiri
    • Projection akhir
  • Pencarian rencana ini memakan sekitar 40 ms bahkan pada release build, dan sebagian besar waktunya digunakan untuk equivalence saturation

Pembaruan eksekusi rencana optimisasi

  • Pada pembaruan 2025-06-29, eksekusi rencana yang telah dioptimalkan diimplementasikan
  • Rencana keluar sebagai Vec<ENode<Op>>, tetapi eksekusi sebenarnya tidak menjalankan tiap node secara independen
  • Cara eksekusi yang dimaksud adalah sebagai berikut
    • Untuk tiap Var, beberapa Map yang bergantung padanya diterapkan dalam satu pemindaian koleksi eksternal
    • Untuk tiap Mul, beberapa Map yang bergantung padanya diterapkan dalam satu pemindaian join
  • Op::Map(action) lebih merupakan pekerjaan yang diantrekan ke operasi dependensi daripada operasi yang dijalankan langsung
  • Untuk itu, TempAction diperkenalkan
    • Filter literal
    • Filter kesetaraan variabel
    • Projection yang dapat memuat referensi kolom atau literal string
  • Tahap persiapan rencana eksekusi memisahkan body dan head, lalu mengumpulkan aksi Map berdasarkan node input
  • Dalam eksekusi Var, penanganan nama terbagi menjadi tiga kasus
    • Pembuatan head dipakai untuk nama relasi head
    • Transformasi identity memakai ulang nama input yang ada
    • Transformasi non-trivial disimpan dengan nama sementara .temp-*
  • Eksekusi Mul(2) memeriksa key arity dan nama dari dua input, lalu memanggil join_with untuk menumpuk hasil ke beberapa builder
  • Pada contoh aliasing yang kompleks, eksekusi rencana yang dioptimalkan berjalan 114,28 detik, sekitar 5 detik lebih cepat dari sebelumnya yang berada di kisaran 119 detik, tetapi alasannya tidak jelas
  • Optimisasi multi-rule belum diimplementasikan, dan pendekatan rencana itu sendiri mungkin perlu dipikirkan ulang

Optimisasi representasi fact

  • Setelah 50 GB dikurangi menjadi 5 GB, memori yang dipakai masih dipandang sekitar 10 kali lebih besar dari yang diperlukan
  • Largest layer pada relasi besar -M berisi 57.289.225 fact dan menggunakan sekitar 2.098.253.766 byte
    • Batas fact: 458.313.800 byte
    • Batas term: 916.627.600 byte
    • Data byte aktual: 723.312.366 byte
  • Optimisasi pertama memanfaatkan arity yang konstan
    • Jika semua fact memiliki 2 kolom, batas fact dapat direpresentasikan hanya dengan stride dan length
    • Data batas sekitar 458 MB praktis dihilangkan
  • Optimisasi kedua adalah menyamakan panjang term
    • Jika angka dibuat menjadi string fixed-width 7 digit, batas term juga dapat direpresentasikan dengan stride dan length
    • Sebagai gantinya, jumlah byte aktual bisa bertambah
  • Optimisasi ketiga adalah merepresentasikan angka sebagai binary, bukan teks
    • Angka 7 digit muat dalam u32 4 byte
    • Karena juga muat dalam 3 byte, ukurannya menjadi 57,289,225 × 2 × 3 = 343,735,350 byte
    • Turun dari sekitar 2 GB menjadi sekitar 350 MB, berkurang sekitar 6,10 kali
  • Jika pengulangan term pertama dikompresi, ukurannya turun lebih jauh
    • Ada 57.289.225 fact, tetapi distinct first term hanya 1.147.612
    • Jika disimpan dalam bentuk (Term, [Term]) alih-alih (Term, Term), largest layer turun ke sekitar 184.491.407 byte
    • Berkurang sekitar 11,37 kali dibanding 2 GB awal
  • Pada pembaruan 2025-07-02, optimisasi tahap pertama diterapkan
    • Largest batch menjadi 343.735.382 byte, yaitu nilai teoretis 343.735.350 byte ditambah 32 byte
    • Waktu eksekusi turun dari sekitar 115 detik menjadi sekitar 95 detik, membaik sekitar 20%

Representasi layered trie

  • Pada pembaruan 2025-07-20, layered trie dapat berfungsi
  • Representasi row-oriented dibandingkan dengan representasi layered trie column-oriented
    • 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 adalah cara menekan pengulangan kolom depan dalam representasi row yang terurut
  • Tiap kolom adalah list dari list nilai
    • Tiap list adalah daftar distinct value yang terurut dan sesuai dengan prefix kolom sebelumnya
    • Jumlah list dalam satu kolom sama dengan total item pada kolom sebelumnya
  • Dapat dilihat seperti trie, tetapi implementasi sebenarnya tetap dipertahankan sebagai kolom
  • Keuntungannya adalah pencarian, join, difference, dan merge dapat dilakukan per prefix
  • Jika hampir tidak ada distinct value dan lebih baik melihat seluruh baris sekaligus, pendekatan row-oriented bisa lebih menguntungkan
  • Sebagai abstraksi umum, trait FactContainer diperkenalkan
    • form
    • len
    • apply
    • join
    • except
    • merge
  • apply melacak range tiap layer dengan stack eksplisit, bukan rekursi, lalu membentuk baris dan meneruskannya ke action
  • align adalah helper umum untuk mencocokkan prefix dari dua layered trie
    • Ordering::Less: range yang hanya ada di self
    • Ordering::Greater: range yang hanya ada di other
    • Ordering::Equal: prefix sepanjang arity yang sama-sama ada di kedua sisi
  • join, except, dan merge semuanya diimplementasikan di atas align
    • join mengembangkan extension yang tersisa pada prefix bersama lalu melakukan cross join
    • except melakukan graft range yang hanya ada di self ke TrieBuilder
    • merge melakukan graft pada range self-only, other-only, dan equal masing-masing sekali secara sesuai

Optimisasi fixed-width dan performa

  • Jika dapat di-upgrade ke fixed-width [u8; 4], performa perbandingan membaik secara signifikan
  • Layered trie dapat menerapkan optimisasi fixed-width per kolom, sehingga dalam jangka panjang berpotensi lebih menguntungkan daripada row
  • upgrade dan downgrade mudah diterapkan pada except dan merge, tetapi penerapannya pada join lebih sulit karena masalah tipe 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
  • Saat ini sekitar 2/3 waktu dihabiskan di bawah join
  • Diperkirakan masih ada ruang setidaknya sekitar 2x lagi untuk optimasi join
  • Percobaan sederhana dengan menyusun ulang inner loop tidak menghasilkan peningkatan yang terukur

Spesialisasi hingga level kode terkompilasi

  • Jika mendeteksi term dengan panjang yang sama dan fact dengan arity yang sama, Vec<u8> dapat dipandang seperti Vec<[[u8; B]; T]>
  • Bentuk ini membuat Rust lebih memahami bentuk data, sehingga mengurangi biaya pemeriksaan bounds dan length, serta membuat perbandingan menjadi sangat murah
  • Perbandingan digunakan di berbagai titik dalam datatoad
    • Mengurutkan dan menghapus duplikat batch fact
    • Menggabungkan batch
    • Menggabungkan kunci join
    • Memfilter fact baru dengan membandingkannya terhadap fact yang sudah ada
  • Performa baseline adalah sebagai berikut
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
  • Optimasi pengurutan diuji dengan melakukan unsafe transmute dari Vec<u8> menjadi Vec<[u8; 8]>, lalu menjalankan sort dan 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
  • Optimasi penggabungan diimplementasikan dengan cara sederhana: menggabungkan dua input, lalu menjalankan sort dan 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
  • Masih belum mencapai performa terkompilasi milik datafrog
  • Biaya perbandingan yang tersisa juga ada pada join dan antijoin; rencananya peluang optimasi yang sama akan ditinjau lagi saat berpindah ke struktur berbasis trie
  • Sedang mencari cara untuk menghapus unsafe, dan menambahkan kesimpulan bahwa kode unsafe sebaiknya dihindari

Pekerjaan yang masih tersisa

  • Spill ke disk

    • Penyimpanan columnar terdiri dari sejumlah kecil alokasi besar
    • Saat dibuat, data dapat ditulis ke file alih-alih memori, lalu digunakan kembali dengan memory map

  • Evaluasi terdistribusi

    • Join, penghapusan duplikat, dan distinctness check berbasis pada kesetaraan kunci
    • Kunci dan data terkait dapat didistribusikan ke beberapa worker
    • Dengan timely_communication, ini dapat diperluas hingga beberapa proses

  • Evaluasi aturan streaming

    • Saat ini join menggunakan binary join dan output yang dimaterialisasi
    • Jika indeks yang diperlukan tersedia, dapat dibuat rencana yang tidak mematerialisasi state internal
    • Worst-case optimal join juga akan dibahas di sini

  • Spesialisasi custom representation

    • Ada ide untuk mendeteksi transitive closure dan mengkhususkan pada strongly connected component decomposition
    • Equivalence relation dapat menggunakan struktur data union-find
    • bddbddb dan factorized databases juga dibahas sebagai topik terkait

  • Pencarian fact terkait

    • Perlu memahami dan menerapkan demand transform
    • Ini dipandang sebagai transformasi yang diperlukan untuk eksplorasi Datalog interaktif

Bacaan terkait

1 komentar

 
GN⁺ 2025-06-16
Komentar Hacker News

  • Melihat tulisan ini naik ke peringkat 1, sepertinya memang menarik
    Saat ini saya sedang membuat game strategi real-time dengan Differential Datalog dan Rust, dan logika game-nya dikelola oleh DDL
    Sebagian besarnya lebih seperti alasan untuk menemukan ide baru dan melakukan yak shaving tanpa akhir
    https://github.com/vmware-archive/differential-datalog

    • Sepertinya demo keren yang dibuat dengan ddlog
      Sebagai referensi, tim ddlog sekarang telah mendirikan Feldera, jadi mungkin layak juga mempertimbangkan memakai DBSP langsung dari Rust
      https://github.com/feldera/feldera
    • Saya penasaran apakah dengan mencampurkan repositori tulisan asli ini dan salsa, crate yang menjalankan Rust analyzer, kita bisa membuat differential datalog ala Frankenstein
      https://github.com/salsa-rs/salsa
    • Saya penasaran bagaimana status implementasinya dan sejauh mana ini bisa dibawa
      DDLog sudah tidak lagi dipelihara secara aktif, jadi justru lebih menarik

  • “Saya, si penjahat terkenal, diundang dengan keyakinan setengah pasti bahwa saya sedang pergi untuk menerima hukuman yang seharusnya sudah saya terima sejak lama.” — ini adalah kalimat pembuka terbaik dari tulisan blog teknis yang saya baca tahun ini
    Sisipan komentar naratornya juga luar biasa, dan jarang ada tulisan yang sedalam ini secara teknis tetapi tetap begitu menyenangkan dibaca
    Perjalanan mengoptimalkan kueri alias terasa seperti novel detektif, dan pembaca ikut merintih pada penggunaan memori 50GB lalu bersorak ketika turun menjadi 5GB
    Kode maupun tulisannya sama-sama hebat

  • Saya sempat mengerjakan sedikit port mangle datalog ke Rust
    Ada di https://github.com/google/mangle/tree/main/rust dan berada di repositori yang sama dengan implementasi Go
    Karena prioritasnya tidak tinggi, ditambah sindrom sistem kedua, progresnya lambat
    Mangle Rust diarahkan untuk menangani data berukuran sewenang-wenang sambil membaca dan menulis fakta dari disk lewat memory mapping, sedangkan implementasi Go berbasis in-memory
    Tulisan ini bagus karena juga membahas parsing Datalog dan LSM tree, dan jauh lebih mudah diikuti dibanding materi tentang datafrog
    Di Rust ada banyak implementasi Datalog yang memakai procedural macro seperti ascent dan crepe, tetapi kekurangannya adalah sulit menerima kueri saat runtime
    Jika dipakai untuk analisis statis dengan kueri dan program yang sudah tetap, pendekatan procedural macro mungkin lebih baik

  • Meski tampaknya kebangkitan Datalog saat ini mulai melemah, menyenangkan melihat para penggemar intinya tetap bertahan
    Konferensi Datalog 2.0 terbaru cukup jauh lebih kecil dibanding dulu, dan konferensi HYTRADBOI kedua juga porsi Datalog-nya kecil
    Pada HYTRADBOI pertama, seperempat dari karya yang diajukan berkaitan dengan Datalog
    Juga menggembirakan melihat orang lain membagikan proyek Datalog terbaru mereka
    Saat ini saya sedang menyiapkan migrasi perangkat lunak berskala besar sambil membuat pipeline kualitas data untuk basis data SQL lama
    Jika kuerinya disusun dengan baik, hasilnya sangat mudah dibaca, jadi menurut saya Datalog jauh lebih berguna daripada SQL untuk mengidentifikasi dan menelusuri masalah kualitas data

    • Meski saya setuju dengan arah besarnya, saya rasa jumlah peserta Datalog 2.0 yang sedikit sulit dijadikan contoh utama menurunnya Datalog
      Datalog 2.0 adalah workshop satelit dari konferensi Eropa LPNMR yang relatif kurang dikenal, dan kebetulan konferensi itu diadakan di Dallas
      Saat saya hadir langsung pun acaranya terasa agak sepi, dan walau saya juga mengirim makalah ke workshop itu, saya tidak terlalu melihat banyak orang dari bidang tersebut
      Sebagai pengecualian, orang-orang dari Eropa yang memperkenalkan solver Nemo cukup menonjol
      Menurut saya, sedikitnya peserta tahun ini lebih menunjukkan bahwa ini adalah workshop satelit dari konferensi yang memang tidak terlalu terkenal, dengan acara utamanya ICLP, daripada kurangnya minat pada implementasi Datalog
      Tentu saja saya tidak bermaksud membantah klaim yang lebih besar bahwa hampir tidak ada lagi hal baru yang tersisa dalam implementasi engine Datalog murni
      Ruang risetnya sudah bergerak jauh ke isu-isu yang lebih eksotis seperti streaming (HydroFlow), choice (Dusa), dan hal-hal yang lebih mendekati general chase (engine chase milik Egglog)
      Hampir semua orang tampaknya setuju bahwa Datalog vanilla itu membosankan, tetapi saturasi maju monotonic dan Horn clause adalah baseline kaya dengan lanskap rekayasa performa yang sudah dipahami dengan baik, sehingga bagus untuk membangun teori yang lebih menarik seperti semiring atau Z-set

  • Jika bagian state machine dan parsing terasa menarik, saya juga merekomendasikan presentasi lama Rob Pike Lexical Scanning in Go
    https://www.youtube.com/watch?v=HxaD_trXwRE
    Memang dalam Go, tetapi sebagian besarnya mudah diterapkan ke bahasa lain
    Menyenangkan bahwa bahasa modern seperti Rust, Zig, dan Go mendukung Unicode/rune/grapheme secara native
    Dibandingkan Java, .NET, C++, atau bahasa skrip, banyak masalah jadi langsung hilang

  • Saya secara umum menyukai pekerjaan Datalog penulis ini, tetapi saya berharap materi pengantarnya tidak mengajarkan binary join
    Begitu keluar dari kasus ideal, bagian dalamnya cepat menjadi berantakan, dan metode dengan gaya join umum jauh lebih mudah digeneralisasi di kepala saya
    https://en.wikipedia.org/wiki/Worst-case_optimal_join_algorithm

  • Dulu saat kuliah saya sempat sedikit bersentuhan dengan Prolog, dan kurang lebih tahu dipakai untuk apa serta apa kegunaannya, tetapi tidak pernah benar-benar memahaminya secara mendalam.
    Sejak itu saya terus mendengar bahwa Datalog itu hebat, tetapi justru sulit menangkap apa yang diperbaiki Datalog dibanding Prolog.
    Barusan saya membaca sekilas halaman Wikipedia tentang Datalog, dan kesannya Prolog punya performa yang relatif buruk, sedangkan Datalog secara drastis meningkatkan performa dengan mengurangi daya ekspresi dan fitur, sehingga bisa menangani dataset yang lebih besar dan pemrosesan yang lebih terparalelkan.
    Sepertinya ini juga mencakup hilangnya kelengkapan Turing, tetapi saya penasaran apakah itu memang inti persoalannya atau saya sepenuhnya meleset.

    • Setahu saya, Prolog terlihat deklaratif seolah-olah cukup mengenkode relasi lalu ia akan menemukan jawabannya, tetapi dalam praktiknya sangat bergantung pada urutan aturan dan juga memerlukan arahan tambahan seperti “cut”.
      cut bukan hanya mencegah komputasi yang terbuang, tetapi juga bisa memengaruhi hasil.
      Sebaliknya, Datalog pada umumnya lebih mirip basis data relasional dengan sintaks yang berbeda.
    • Datalog lebih sederhana, tidak Turing-complete, dan kalau saya tidak salah memakai forward chaining, yang kemudian berdampak berantai pada karakteristik performa dan memori.
      Ruang pencarian besar yang sepele di Prolog bisa saja menghabiskan terlalu banyak memori di Datalog hingga tak bisa direpresentasikan sama sekali.
      Datalog adalah mobil komuter dengan CVT, sementara Prolog lebih seperti mobil F1.
      Jadi ini bukan benar-benar peningkatan, melainkan lebih seperti Prolog yang dipreteli sebagian agar orang tidak menembak kaki sendiri, dan jauh lebih mudah juga untuk diimplementasikan serta disematkan ke aplikasi lain.
      Jika Anda terbiasa dengan Prolog, Datalog kemungkinan besar akan terasa membatasi.
      Tidak ada call/3, tidak ada term/goal expansion, dan pada dasarnya Datalog adalah himpunan fitur minimum bersama dari Prolog yang dirancang untuk pencarian basis data interaktif.
      Mudah menulis kode Datalog yang cepat, tetapi batas atasnya juga jauh lebih rendah.
      Prolog juga bisa ditulis dengan cara yang memungkinkan konkurensi, tetapi itu pekerjaan tingkat menengah yang menuntut pemahaman terhadap implementasinya.
      Guarded Horn Clauses dan bahasa-bahasa turunannya dikembangkan untuk memformalkan sisi tersebut, tetapi perkembangan pasca-Prolog dari Jepang sangat sulit dipahami.
      Performa Prolog sangat bergantung pada programmer, implementasi yang dipakai, dan di mana ia digunakan.
      Seperti Lisp, Prolog juga bisa dipakai pada waktu kompilasi untuk menghasilkan kode mesin native dari DSL.
      Jika Anda memahami cara kerja implementasi dasarnya dan menulis kode yang sejalan dengannya, performanya bisa cukup cepat.
      Hanya saja untuk sampai ke situ biasanya perlu menulis kode Prolog selama bertahun-tahun dengan satu implementasi.
      Ada banyak penelitian tentang optimisasi kompilator Prolog, dan juga contoh implementasi proprietari.
      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/

  • Jika ingin memakai Datalog dan Rust, cozodb ditulis dalam Rust dan juga menyediakan sintaks kueri Datalog.

    • Cozodb terlihat keren, tetapi tampaknya nyaris tidak aktif.
      Sekitar November 2024 saya sempat melihatnya dan menemukan beberapa perbaikan mudah pada backend penyimpanan SQLite.
      https://github.com/cozodb/cozo/issues/285
    • Cozodb pada umumnya bekerja baik sesuai dokumentasinya dan menyenangkan untuk dipakai.
      Saya juga memakainya untuk analisis statis program, dan secara internal ia menggunakan pohon terurut serta teknik pengetikan.
      Dokumentasinya cukup baik sampai layak dibandingkan dengan penjelasan blog langkah demi langkah di awal, dan khususnya pekerjaan optimisasi kuerinya menarik.
      Hanya saja, jika tidak bekerja in-memory di Rust, biaya serialisasi datanya besar, dan proyeknya, kalau dinilai baik-baik pun, sedang sepi.

  • Dulu para penggemar Clojure mengatakan bahwa Datalog lebih baik daripada SQL, dan sayang sekali semua basis data relasional memakai SQL
    Saya belum benar-benar mendalami alasan mereka berpikir begitu

    • Pada dasarnya, Datalog jauh lebih ringkas dibanding SQL, biaya untuk memisahkan view jauh lebih kecil, dan dukungannya untuk penutupan transitif jauh lebih unggul
      http://canonical.org/~kragen/binary-relations dimulai dari kueri non-rekursif yang sederhana, tetapi terjemahan SQL-nya sudah terasa kriminal, dan solusi SQL yang dipisahkan dengan benar layak dihukum mati
      ANSI SQL belakangan menambahkan fitur rekursi sehingga ini tidak lagi sepenuhnya mustahil, tetapi masih ada tiga kelemahan besar
      Pertama, SQL tanpa sengaja jadi Turing-complete, sedangkan kueri Datalog dijamin berhenti
      Kedua, tetap saja sangat canggung digunakan
      Ketiga, karena alasan pertama, implementasinya sering tidak sepenuhnya lengkap sehingga sulit dipercaya untuk dipakai
    • Dialek Clojure/Datomic memang sulit dipahami, tetapi saya setuju dengan arah besarnya
      Jika ingin mencoba Datalog secara online lewat lingkungan notebook yang ramah, saya merekomendasikan Percival
      https://percival.ink/
      Secara umum belum ada standar untuk implementasi Datalog yang setara dengan “ANSI SQL”, tetapi begitu memahami ide intinya, Datalog lain pun tidak akan terlalu sulit
      Saya juga sudah mulai membuat fork Percival yang mengompilasi Datalog ke SQLite, jadi kalau ingin melihat bagaimana keduanya mengekspresikan hal yang sama, bisa dicek
      https://percival.jake.tl/
      Agregasi dan join yang lebih canggih masih belum selesai, tetapi bentuk dasarnya sudah bekerja dengan baik
      Logica adalah kompiler Datalog→SQL yang jauh lebih serius dan matang, dibuat oleh peneliti Google, dan dapat mengompilasi ke BigTable, DuckDB, dan beberapa dialek SQL lainnya
      https://logica.dev/
      Area tempat Datalog menjadi jauh lebih mudah adalah saat menangani kueri/aturan rekursif
      Di SQL ini juga mungkin, tetapi rasanya seperti minum Play-Doh dengan sedotan
      Di Materialize.com milik Frank ada format SQL “WITH MUTUALLY RECURSIVE” yang jauh lebih baik daripada pendekatan rekursif ANSI SQL lama, dan sedang dievaluasi di Notion untuk kueri pemuatan halaman serta sinkronisasi data
      https://materialize.com/blog/recursion-in-materialize/
      Feldera juga punya format serupa untuk view rekursif
      https://www.feldera.com/blog/recursive-sql-queries-in-feldera
      Saya menyukai Feldera karena setiap “aturan” atau sub-view bisa dibuat sebagai pernyataan terpisah alih-alih harus memasukkannya semua ke dalam satu pernyataan raksasa
      Kekurangan utama yang saya lihat saat mengujinya adalah bahwa dialek SQL Feldera membawa cukup banyak batasan dari Apache Calcite, sedangkan dialek SQL Materialize sangat berusaha menjaga kompatibilitas PostgreSQL

  • Tulisan baru dari McSharry, bagus sekali
    Terakhir kali saya cek, VMWare tampaknya sudah menjauh dari differential datalog

    • Tim Differential Datalog mendirikan Feldera
      https://www.feldera.com/
      Sepertinya mereka beralih dari differential Datalog ke differential SQL, kemungkinan karena mereka sadar Datalog memang sangat sulit dijual