Rust ile etkileşimli bir Datalog motoru oluşturmak

 (github.com/frankmcsherry)
1 puan yazan GN⁺ 2025-06-16 | 1 yorum | WhatsApp'ta paylaş
  • Mantık programlama atölyesinde ortaya çıkan Datalog araçlarının kullanılabilirlik ve performans sınırları nedeniyle, Rust tabanlı etkileşimli Datalog kabuğu datatoad deneyi başlatıldı
  • datatoad, çalışma sırasında kurallar ekleyip yeni gerçekleri sürekli türeten bir yapıyı hedefliyor; columnar depolama ve LSM katmanları ile gerçek kümelerinde yinelenen veriyi işleme maliyetini azaltıyor
  • Kural değerlendirmesi, Datalog gövdesini bir join problemine dönüştürerek yürütülüyor; stable durumuna göre tam değerlendirme ile artımlı değerlendirme ayrılıyor ve daha önce hesaplanmış stable-stable join'lerden kaçınılıyor
  • Graspan veri kümesi deneylerinde, yalnızca elle kural yeniden yazımı ve ara ilişkilerin eklenmesiyle aliasing analizi 736.34 saniye·50.13GB'dan 119.34 saniye·5.32GB'a düştü
  • Sonraki çalışmalar e-graph tabanlı join planı optimizasyonu, layered trie, sabit genişlikli bayt gösterimi, disk spill, dağıtık değerlendirme, streaming join, demand transform yönünde ilerliyor

datatoad'un çözmeye çalıştığı sorun

  • Memorial Day hafta sonu düzenlenen mantık programlama atölyesinde, program analizi için kullanılan Datalog araçlarının kullanım zorlukları belirginleşti ve bunun üzerine basit, kullanışlı ve hızlı bir Datalog uygulaması denemesi başladı
  • Hedeflenen uygulama, statik bir örnek çalıştırıcı değil, etkileşimli bir Datalog kabuğu
    • Büyük miktarda gerçeği yükleyebiliyor
    • Çalışma sırasında yeni kurallar eklenebiliyor
    • Eklenen kuralların sonuçlarını mevcut duruma sürekli yansıtıyor
  • Kod, datatoad repository üzerinden takip edilebilir
  • Mevcut datafrog, Datalog motorunun temel algoritmalarını sağlıyor ancak kullanıcının bunları kendisinin bağlamasını gerektiriyor; datatoad ise aynı fikirleri kullanımı daha kolay bir biçimde yeniden düzenliyor
  • httpd veri akışı grafiğinin nullability örneğinde datatoad, Vec<String> verisi ve derlenmemiş sorgularla 8.3 saniye sürdü; bu, (u32, u32) verisi kullanan datafrog örneğindeki yaklaşık 2 saniyeye kıyasla yaklaşık 4 kat daha yavaş
  • Reachability probleminde, datafrog uygulamasıyla aynı sayıda çıktı tuple'ı üretti ancak genel doğruluk doğrulaması henüz tamamlanmış değil

Datalog modeli ve kabuk yapısı

  • Datalog, basit mantık kuralları yazıldığında bu kurallardan ulaşılabilen tüm gerçekleri türeten bir dil
  • Kurallar head ve body'den oluşur
    • Örnek: tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c).
    • tri, edge ilişkilerdir; a, b, c ise değişkenlerdir
    • Head'de görünen değişkenler body'de de bulunmalıdır
  • Gerçekler, body'si boş olan kurallar olarak ele alınır
    • Örnek: edge(1, 2) :- .
    • Birden fazla head kullanarak bir seferde birden çok gerçek yazılabilir
  • Datalog'un monotonluk özelliği nedeniyle, kural veya gerçek eklendiğinde doğru gerçekler kümesi küçülmez; aynı girdi kural kümesi, kuralların sırasından bağımsız olarak aynı sonuca ulaşır
  • Rust gösteriminde üç yapı merkezde yer alır: Rule, Atom, Term
    • Rule { head: Vec<Atom>, body: Vec<Atom> }
    • Atom { name: String, terms: Vec<Term> }
    • Term::Var(String) veya Term::Lit(String)
  • Literal depolamada String yerine Vec<u8> kullanılır
    • Gereken özellikler, literal eşitliği ve rastgele bir sıralama düzenidir
    • Baytların String, (u32, u32) ya da başka bir anlam taşıması kullanıcıya bırakılmıştır
  • Yorumlayıcı durumu kuralları ve gerçekleri birlikte tutar
    • rules: Vec<Rule>
    • facts: facts::Facts
  • Kabuk, giriş satırlarını Datalog olarak parse ettikten sonra State::extend ve State::update çağırır; .list komutu ise her ilişki adını ve gerçek sayısını yazdırır

Parse etme ve gerçek depolama

  • Parser parse.rs içinde yer alır ve Soufflé sözdiziminden alınmış bir biçim kullanır
  • Değişkenler ? ile başlar
  • Token'lar ., ,, (, ), :-, ? ile sınırlıdır; geri kalan metin atom veya term adı olarak işlenir
  • Tokenizer boşlukları kaldırır ve :- ifadesini tek bir sembol gibi taramak için ← ile değiştirir
  • Kural parse etme, turnstile'a kadar head atom'larını, period'a kadar body atom'larını okuma şeklinde ilerler
    • Atom; ad, sol parantez, term listesi ve sağ parantezden oluşur
    • Term, ? varsa değişken; yoksa literaldir
  • Hatalı kurallar None döndürür; şu anda hatanın hangi bölümde olduğunu ayrıntılı biçimde bildirmez
  • Negatif kuralları eklemek için Exclamation token'ı gerekir ancak bu henüz ele alınmıyor

Gerçek kümelerinin yaşam döngüsü

  • Basit Vec<Vec<String>> depolama, iç içe tahsisler nedeniyle bellek yönetimi açısından elverişsizdir
  • datatoad, Rust türlerini düz bir yerleşime sahip az sayıdaki doğrusal tahsise dönüştürmek için columnar kullanır
    • String baytları, string sınırları ve gerçek sınırları ayrı dizilerde tutulur
  • FactContainer, sıralanmış ve yinelemeleri kaldırılmış gerçek listesini sarar; wrapper türü, sıralama ve yineleme kaldırma değişmezlerini ima eder
  • Sütun tabanlı kapsayıcı pratikte yalnızca append-only olduğundan, ara değişiklikler için uygun değildir; bu yüzden yeni gerçek ekleme için log-structured merge-tree(LSM) benzeri bir yapı kullanılır
    • FactLSM { layers: Vec<FactContainer> }
    • Katman boyutları geometrik olarak büyüyecek şekilde yönetilir
    • Boyutları 2 kat içinde kalan katmanlar birleştirilerek sıralı ve yinelemesiz durum korunur
  • FactBuilder, sıralanmamış ve yinelemeli olabilen active alanı ile sıralanmış ve yinelemeleri kaldırılmış layers alanlarını birlikte tutar
  • Her ilişkinin gerçekleri üç aşamadan geçer
    • to_add: Yeni gelmiş ancak gerçekten yeni olup olmadığı henüz doğrulanmamış gerçekler
    • recent: Ayrık ve henüz işlenmesi gereken gerçekler
    • stable: Zaten tamamen işlenmiş ayrık gerçekler
  • FactSet::advance, recent verisini stable alanına taşır ve to_add içinden zaten stable içinde olan gerçekleri çıkararak yeni recent oluşturur

Kural değerlendirmesi bir join problemidir

  • Datalog kural gövdesi, ilişkisel veritabanlarındaki bir equi-join olarak görülebilir
  • Üçgen kuralı örneği şöyledir
    • tri(?a, ?b, ?c) :- edge(?a, ?b), edge(?b, ?c), edge(?a, ?c).
  • Tüm değişken atamalarını doğrudan listelemek, sonlu olsalar bile çok fazla olduğundan, ortak değişkenlerin anahtar sütunlarına göre sıralanıp ardından birleştirilirler
  • Uygulama, gövdeyi sağdan sola doğru indirger
    • Son iki ilişki join edilerek ara ilişki oluşturulur, ardından bu ilişki soldaki ilişkiyle yeniden join edilir
    • Body atom'u yalnızca bir taneyse, sadece head biçimine dönüştürülür
  • JoinPlan şu bilgileri içerir
    • Body atom'larını join'e uygun biçimde yeniden düzenleyip filtreleyen bodys
    • Her ara join'in key arity'si ile çıktı projection'ını tutan joins
    • Head atom'una eklenecek koordinatları veya literalleri gösteren heads
    • Son head üretim join'inin arity'si
  • Mevcut plan, basit bir right-linear join plan
  • JoinPlan oluşturulurken, her değişkenin leftmost ve rightmost görünüm konumu kullanılarak hangi değişken değerlerinin ne zamana kadar korunacağı belirlenir; body atom sütunları dead, key ve value sütunlarına ayrılır
  • Temel fonksiyon implement_plan(rule, plan, pos, stable, facts) şeklindedir
    • Yeni bir kural eklendiğinde, tüm gerçekler üzerinde başlamak için stable = true kullanılır
    • Mevcut kuralların tekrarlı uygulanmasında ise yalnızca yeni türetimleri hesaplamak için stable = false kullanılır

Artımlı join ve merge join

  • Join işlemi çift doğrusal olduğundan şu şekilde ayrıştırılabilir
    • (A + a) ⋈ (B + b) = A ⋈ B + A ⋈ b + a ⋈ B + a ⋈ b
  • Stable kümeler arasında zaten oluşturulmuş A ⋈ B yeniden hesaplanmak zorunda değildir
  • Yalnızca yeni türetimler gerekiyorsa sadece üç join çalıştırılır
    • A ⋈ b
    • a ⋈ B
    • a ⋈ b
  • join_with, stable bayrağına göre stable-stable join'i dahil eder ya da hariç tutar
  • Gerçek join, sıralı iki girdiyi ardışık olarak tarayan bir merge join'dir
    • Anahtarlar eşitse, o anahtar için tüm kombinasyonlarda action çağrılır
    • Anahtarlar farklıysa, gallop ile bir sonraki olası eşleşme noktasına hızla atlanır
  • gallop, EmptyHeaded tarafındaki bir fikirden alınmıştır; tekdüze koşul doğru kaldığı sürece üstel olarak ilerler, ardından ikili aramayla aralığı daraltır

Nullability analizi deneyi

  • Deney verisi Graspan projesinin verisidir ve Google Drive'da da durmaktadır
  • Veri akışı analizi girdisinde e ve n olmak üzere iki ilişki vardır
    • n(?a, ?b): ?a değeri ?b konumuna yazılabilir
    • e(?a, ?b): Bir ?a konumundaki değer başka bir ?b konumuna taşınabilir
  • Erişilebilirlik kuralı şöyledir
    • n(?a, ?c) :- n(?a, ?b), e(?b, ?c) .
  • httpd girdisinde başlangıç .list şu değerleri gösterir
    • e: 9,905,624
    • n: 138,331
  • Kural doğrudan çalıştırıldığında yaklaşık 15 saniye sürer ve n 9,393,283 kayda ulaşır
  • Yavaşlığın nedenlerinden biri, n'in join anahtarına uyacak şekilde yeniden düzenlenmiş geçici ilişki .temp-0-0-in'in 9,393,283 kayda kadar büyümesidir
  • Kullanıcı kuralı yeniden yazarsa performans iyileşir
    • m(?loc, ?val) :- n(?val, ?loc) .
    • m(?loc, ?val) :- m(?mid, ?val), e(?mid, ?loc) .
  • Aynı httpd girdisinde yeniden yazımdan sonra ikinci kural yaklaşık 8.43 saniyede çalışır
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 için Graspan değerinin yanında * vardır; makale toplam süreyi birlikte raporlamış ve girdi tanımlayıcı çakışmaları nedeniyle bunun birebir aynı çalıştırma olduğunu söylemek zordur
  • Uygulayıcıların kullandığı araçlarla karşılaştırmak için Soufflé daha uygun bir hedef olabilir

Aliasing analizi ve elle optimizasyon

  • İkinci analiz, Zheng ve Rugina'nın aliasing analizinin Graspan tarafından alınmış sürümüdür
  • Girdi ilişkileri iki adettir
    • A(?val, ?loc): ?loc <- ?val
    • D(?val, ?loc): ?loc, *?val biçiminde kullanılır
  • Amaç, memory alias ve value alias sonuçlarını çıkarmaktır
    • memory alias: iki lvalue ifadesi aynı bellek konumunu gösterebilir
    • value alias: iki ifade aynı pointer değerini değerlendirebilir
  • Makaledeki gösterimde ^T, ^?, ^* yer alır
    • ^T: ilişki transpozu
    • ^?: isteğe bağlı terim
    • ^*: 0 veya daha fazla tekrar
  • Datalog'da ^? iki kurala bölünerek ifade edilir; ^* ise identity ilişkisinin açıkça eklenmesiyle ele alınır
  • Başlangıçtaki kural yürütmesi uzun sürer
    • Son iki identity başlatma kuralı girildikten sonra 686.57 sn ve 736.34 sn sürer
    • Süreç 50.13GB kullanır
    • V: 361,947,256
    • M: 92,806,768
    • F: 2,669,647
  • -V, -M, -a, -d transpoz ilişkileri açıkça kullanılarak -in geçici ilişkileri kaldırılır
    • Toplam 815.92 sn, yani yaklaşık 13.6 dakika
    • Bellek 31.96GB
  • Zheng ve Rugina'nın yaklaşımı demand-driven'dır ve pratikte yalnızca M gerektiğinden V, M içine inline edilir
    • -V için 361,947,256 kayıt üretilmez
    • Bellek 18.96GB'a düşer
  • Tekrarlanan join parçaları Fd adıyla etiketlenip yeniden kullanılır; ardından F yerine doğrudan Fd hesaplanarak identity sorunu da azaltılır
  • MFd ara ilişkisini kullanan son biçim şu sonuçları verir
    • Çalışma süresi: 119.34 sn
    • Bellek: 5.32GB
    • -M: 92,806,768
    • Fd: 1,858,986
    • MFd: 73,474,947
  • Yalnızca elle yeniden yazımla, ilk denemeye kıyasla bellek kullanımı ve çalışma süresinde neredeyse 10 kat iyileşme elde edilir
  • Adlandırılmış ara sonuçlar oluşturmak, istenen bushy-tree join planını bir ölçüde doğrudan kurmayı sağlar; ancak V gibi gerçekte gerekmeyen ilişkilere ad vermek, bunların yüksek maliyetle üretilmesine yol açar

Demand-driven sorgular ve magic sets

  • Demand-driven sorgular, belirli bir hedef olgu için gerekli olan bölümleri keşfetme yaklaşımıdır
  • Yaklaşık bir çözüm olarak magic sets kullanılabilir
    • Hedef literal'i sorguya gömen bir dönüşümdür
    • Tüm d'lerden değil, yalnızca ilgilenilen d'lerden başlayan bir ifade düşünülebilir; ancak bu basit haliyle uygulanırsa yanlış olabilir
  • Magic sets en iyi çözüm değildir; daha verimli olabilecek yaklaşımları bulmak için ilgili makaleleri daha fazla okumayı planlıyor
  • İlgili bağlantılar şunlardır

Join planı optimizasyonu ve veri paralel IR

  • Datalog'un çekiciliği, Horn clause'un kendisinden çok, veri paralel hesaplamanın temel problemi olan data rendezvous kavramını saf biçimde ortaya koymasındadır
  • h(x, y, z) :- b1(x, y), b2(y, z) . kuralı, her y için ilgili x ve z değerlerini tek bir yerde toplama problemi olarak görülebilir
  • Veri paralel hesaplamanın temel davranışı, kayıtları anahtara göre toplayıp kullanıcı mantığına teslim etmektir; join ise bunun içindeki seçici yönlendirmeyi ifade eder
  • Basit bir IR şu opcode'ları kullanır
    • Var(String): adlı koleksiyon
    • Map(Action): filtre, permütasyon, projection
    • Key(usize): öndeki belirli sayıda sütunu anahtar olarak işaretleme
    • Mul(usize): aynı anahtar uzunluğuna sahip birden çok koleksiyonu birleştirme
  • Sonrasında Map ve Key, Action.key_arity içinde birleştirilir
  • Action; literal filtrelerini, değişken eşitliği filtrelerini, projection'ı ve key arity'yi içerir
  • En basit başlangıç noktası, body atomlarının hepsini cross join ile birleştirip her head için filtre ve projection eklemektir; ancak bu yaklaşım doğru sonucu üretse de performansı çok kötüdür

e-graph tabanlı optimizasyon

  • Optimizasyonda e-graph ve equality saturation kullanılıyor
  • Başvuru kaynakları olarak egg webpage, önceki yazı ve egg kullanılmış
  • term graph, Id eklenmiş ENode<T>'lerin bir eşlemesi olarak ifade ediliyor ve aynı düğümler paylaştırılarak program daha kompakt biçimde gösteriliyor
  • Uygulanan e-graph kuralları üç tane
    • MulPermute: Mul(k) girdi permütasyonlarını eşdeğer kılar
    • MulPartition: Mul(k) işlemini çeşitli şekillerde bölüp eşdeğer kılar
    • MapPushdown: Map'i Mul(2) altına iterek anahtarlı bir join biçimi oluşturur
  • Örnek kural şu şekilde
    • head(?a, ?b) :- a(?x, ?a), b(?y, ?x), b(?y, ?z), a(?z, ?b) .
  • equality saturation sonrasında extraction aşamasında maliyet atanıyor
    • Map maliyeti, çıktı sütunu sayısı
    • Mul maliyeti, anahtar sütun sayısı ile girdilerin anahtar olmayan sütun sayılarının toplamı
    • Var maliyeti 0
    • Eşitlik durumunda önce Map sayısı, sonra Mul sayısı en aza indiriliyor
  • Örnekte seçilen plan, en fazla iki ilişkisiz sütuna sahip wave two içinde bulunuyor
    • a, b girdileri için map
    • tek bir join
    • ara projection
    • kendisiyle join
    • son projection
  • Bu plan araması release build'de bile yaklaşık 40ms sürüyor ve zamanın büyük kısmı equivalence saturation için harcanıyor

Optimize edilmiş plan çalıştırma güncellemesi

  • 2025-06-29 güncellemesinde optimize edilmiş planın çalıştırılması hayata geçirildi
  • Plan Vec<ENode<Op>> olarak çıkıyor ama gerçek çalıştırmada her düğüm bağımsız biçimde yürütülmüyor
  • Hedeflenen çalıştırma biçimi şöyle
    • Her Var için, ona bağlı birden çok Map, tek bir dış koleksiyon taramasında uygulanıyor
    • Her Mul için, ona bağlı birden çok Map, tek bir join taramasında uygulanıyor
  • Op::Map(action), doğrudan yürütülen bir işlemden çok, bağımlı işleme kuyruğa alınan bir iş
  • Bunun için TempAction eklendi
    • literal filtre
    • değişken eşitliği filtresi
    • sütun referansı veya string literal taşıyabilen projection
  • Çalıştırma planı hazırlama aşaması, body ile head'i ayırıp Map eylemlerini giriş düğümüne göre topluyor
  • Var çalıştırmasında ad işleme üç duruma ayrılıyor
    • head üretimi, head ilişki adına yazıyor
    • identity dönüşümü, mevcut girdi adını yeniden kullanıyor
    • trivial olmayan dönüşüm, .temp-* geçici adına kaydediliyor
  • Mul(2) çalıştırması iki girdinin key arity ve adlarını denetliyor, ardından sonucu birden çok builder'a yığmak için join_with çağrılıyor
  • Karmaşık bir aliasing örneğinde optimize edilmiş planın çalıştırılması 114.28 saniye sürdü; bu, önceki 119 saniye düzeyine göre yaklaşık 5 saniye daha hızlı, ancak nedeni net değil
  • multi-rule optimizasyonu henüz uygulanmadı ve plan yaklaşımının kendisini yeniden düşünmek gerekebilir

Fact gösterimi optimizasyonu

  • 50GB, 5GB'a düşürüldü ama hâlâ gerekenden yaklaşık 10 kat fazla bellek kullanıldığı düşünülüyor
  • Büyük -M ilişkisi için en büyük layer 57,289,225 fact içeriyor ve yaklaşık 2,098,253,766 bayt kullanıyor
    • fact sınırları: 458,313,800 bayt
    • term sınırları: 916,627,600 bayt
    • gerçek bayt verisi: 723,312,366 bayt
  • İlk optimizasyon, arity'nin sabit olmasından yararlanıyor
    • Tüm fact'ler 2 sütunluysa, fact sınırları yalnızca stride ve length ile ifade edilebiliyor
    • Böylece 458MB düzeyindeki sınır verisi fiilen ortadan kalkıyor
  • İkinci optimizasyon, term uzunluklarını eşitlemek
    • Sayılar 7 basamaklı sabit genişlikli string'lere çevrilirse term sınırları da stride ve length ile ifade edilebiliyor
    • Bunun karşılığında gerçek bayt sayısı artabiliyor
  • Üçüncü optimizasyon, sayıları metin yerine binary olarak göstermek
    • 7 basamaklı bir sayı, u32 içinde 4 bayta sığıyor
    • 3 bayta da sığdığı için 57,289,225 × 2 × 3 = 343,735,350 bayt oluyor
    • Yaklaşık 2GB'dan yaklaşık 350MB'a iniyor; yani yaklaşık 6.10 kat azalma
  • İlk term tekrarını sıkıştırmak daha da fazla azaltıyor
    • 57,289,225 fact var ama distinct first term sayısı yalnızca 1,147,612
    • (Term, Term) yerine (Term, [Term]) biçiminde saklanırsa en büyük layer yaklaşık 184,491,407 bayta düşüyor
    • Bu da başlangıçtaki 2GB'a kıyasla yaklaşık 11.37 kat azalma demek
  • 2025-07-02 güncellemesinde ilk optimizasyon uygulandı
    • En büyük batch, kuramsal 343,735,350 bayta ek 32 bayt ile 343,735,382 bayt oldu
    • Çalışma süresi yaklaşık 115 saniyeden yaklaşık 95 saniyeye indi; yani yaklaşık %20 iyileşme

Layered trie gösterimi

  • 2025-07-20 güncellemesinde layered trie çalışır hâle geldi
  • row-oriented gösterim ile column-oriented layered trie gösterimi karşılaştırılıyor
    • 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, sıralı row gösteriminde öndeki sütunların tekrarını bastıran bir yöntem
  • Her sütun, değer listelerinin bir listesi
    • Her liste, önceki sütun prefix'ine karşılık gelen sıralı distinct değerler kümesini içeriyor
    • Bir sütundaki liste sayısı, bir önceki sütundaki toplam öğe sayısıyla aynı
  • Ağaç gibi görülebilir ama gerçek uygulama sütunlar üzerinden tutuluyor
  • Avantajı, prefix düzeyinde arama, join, fark alma ve birleştirme yapılabilmesi
  • distinct değerlerin neredeyse hiç olmadığı ve tüm satırları tek seferde görmenin daha iyi olduğu durumlarda row-oriented yaklaşım daha avantajlı olabilir
  • Ortak soyutlama olarak FactContainer trait'i eklendi
    • form
    • len
    • apply
    • join
    • except
    • merge
  • apply, özyineleme yerine açık bir stack ile her layer'ın range'ini izleyip satır oluşturarak action'a iletiyor
  • align, iki layered trie'nin prefix'lerini hizalı biçimde görmeye yarayan ortak bir yardımcı
    • Ordering::Less: yalnızca self'te bulunan aralık
    • Ordering::Greater: yalnızca other'da bulunan aralık
    • Ordering::Equal: arity uzunluğundaki prefix her iki tarafta da ortak
  • join, except, merge işlemlerinin tümü align üzerine kurulmuş
    • join, ortak prefix üzerinde kalan extension'ları açıp cross join yapıyor
    • except, yalnızca self'te bulunan aralıkları TrieBuilder ile graft ediyor
    • merge, self-only, other-only ve equal aralıkları uygun şekilde birer kez graft ediyor

Sabit genişlik optimizasyonu ve performans

  • Sabit genişlikli [u8; 4] tipine yükseltilebildiğinde karşılaştırma performansı ciddi biçimde iyileşiyor
  • layered trie, sütun bazında sabit genişlik optimizasyonu uygulayabildiği için uzun vadede row gösterimine göre avantajlı olabilir
  • except ve merge için upgrade ve downgrade kolayca uygulanabildi ama join için uygulama, Rust tür sorunları nedeniyle daha zordu
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
  • Şu anda sürenin yaklaşık 2/3'ü join altında harcanıyor
  • Join optimizasyonunda en az ek 2 kat kadar iyileştirme alanı olduğunu düşünüyorum
  • Sadece inner loop'u yeniden sıralamayı deneyen girişim, ölçülebilir bir iyileşme sağlayamadı

Derlenmiş kod düzeyinde özelleştirme

  • Aynı uzunluktaki term'leri ve aynı arity'ye sahip fact'leri algılarsak, Vec<u8>'i Vec<[[u8; B]; T]> gibi görebiliriz
  • Bu biçim, Rust'ın verinin şeklini daha iyi bilmesini sağlayarak bounds·length kontrol maliyetini azaltır ve özellikle karşılaştırmaları çok ucuz hale getirir
  • Karşılaştırmalar datatoad'ın birçok noktasında kullanılıyor
    • fact batch'lerini sıralama·yinelenenleri kaldırma
    • batch birleştirme
    • join anahtarlarını birleştirme
    • yeni fact'leri mevcut fact'lerle karşılaştırarak filtreleme
  • Referans performansı şöyle
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
  • Sıralama optimizasyonu, Vec<u8>'i Vec<[u8; 8]>'e unsafe transmute ederek sort·dedup uygulama yöntemiyle denendi
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
  • Birleştirme optimizasyonu, iki girdiyi birleştirip ardından sort·dedup yapan basit bir yöntemle uygulandı
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
  • Hâlâ datafrog'un derlenmiş performansına ulaşabilmiş değilim
  • Kalan karşılaştırma maliyeti join ve antijoin'de de var; trie tabanlı yapılara geçerken aynı optimizasyon fırsatlarına yeniden bakmayı planlıyorum
  • unsafe'i kaldırmanın bir yolunu arıyorum ve sonuç olarak unsafe koddan kaçınılması gerektiğini de ekliyorum

Hâlâ yapılacak işler var

  • Diske spill

    • columnar depolama, az sayıda büyük tahsisten oluşuyor
    • Oluşturulurken bellek yerine dosyaya yazılabilir ve sonra memory map ile yeniden kullanılabilir

  • Dağıtık değerlendirme

    • Join, yinelemeleri kaldırma ve distinctness kontrolü anahtar eşitliğine dayanıyor
    • Anahtarlar ve bunlara karşılık gelen veriler birden fazla worker'a dağıtılabilir
    • timely_communication ile birden çok prosese kadar ölçeklenebilir

  • Akış tabanlı kural değerlendirmesi

    • Mevcut join, ikili join ve materialized output kullanıyor
    • Gerekli indeksler varsa, iç durumu materialize etmeyen bir plan oluşturulabilir
    • worst-case optimal join de burada ele alınacak

  • custom representation özelleştirmesi

    • Transitive closure'ı algılayıp strongly connected component decomposition için özelleştirme fikri var
    • Equivalence relation için union-find veri yapısı kullanılabilir
    • bddbddb ve factorized databases de ilgili konuları ele alıyor

  • İlgili fact arama

    • demand transform'u anlayıp uygulamak gerekiyor
    • Etkileşimli Datalog keşfi için bunun gerekli bir dönüşüm olduğunu düşünüyorum

İlgili okumalar

1 yorum

 
GN⁺ 2025-06-16
Hacker News yorumları

  • Bu yazının 1 numaraya çıktığını görmek ilginç
    Şu anda Differential Datalog ve Rust ile gerçek zamanlı bir strateji oyunu yapıyorum; oyun mantığını DDL’in yönetmesini sağlıyorum
    Bunun çoğu, yeni bir fikirle tanışıp sonu gelmeyen yak tıraşına girişmek için bir bahaneye yakın
    https://github.com/vmware-archive/differential-datalog

    • ddlog ile yapılmış havalı bir demoya benziyor
      Bu arada ddlog ekibi artık Feldera’yı kurdu; Rust’ta DBSP’yi doğrudan kullanmayı düşünmek de mantıklı olabilir
      https://github.com/feldera/feldera
    • Asıl yazının deposunu, Rust analizörünü çalıştıran crate olan salsa ile karıştırınca Frankenstein tarzı bir differential datalog yapılabilir mi merak ediyorum
      https://github.com/salsa-rs/salsa
    • Uygulamanın durumunun nasıl olduğunu, ne kadar ileri gidebileceğini merak ediyorum
      DDLog artık aktif olarak bakımı yapılan bir durumda olmadığı için daha da ilginç

  • “Ben, kötü şöhretli bir kötü adam, çoktan hak ettiğim cezayı çekmeye gidiyor olduğuma yarı yarıya inanarak davet edildim.” — bu yıl okuduğum teknik blog yazıları içindeki en iyi ilk cümle
    Anlatıcının araya giren sözleri de harikaydı; bu kadar teknik olarak derin olup aynı zamanda bu kadar eğlenceli okunan yazılar nadir
    Alias sorgularını optimize etme yolculuğu bir polisiye roman gibi hissettirdi; okuyucu da 50 GB bellek kullanımı karşısında inleyip 5 GB’a düştüğünde sevinç çığlığı atıyor
    Hem kod hem yazı harika

  • mangle datalog’u Rust’a portlama işinde biraz ilerledim
    https://github.com/google/mangle/tree/main/rust adresinde, Go uygulamasıyla aynı depoda yer alıyor
    Önceliği yüksek değil, ayrıca ikinci sistem sendromu da var; bu yüzden ilerleme yavaş
    Mangle Rust, bellek eşleme ile olguları diskten okuyup yazarak keyfi boyutta verilerle çalışmayı hedefliyor; Go uygulaması ise bellek içi çalışıyor
    Bu yazı Datalog’u ayrıştırmayı ve LSM ağacını da ele aldığı için güzel; datafrog ile ilgili materyallerden çok daha kolay takip ediliyor
    Rust’ta ascent ve crepe gibi prosedürel makrolar kullanan çok sayıda Datalog uygulaması var, ama bunların çalışma zamanında sorgu almakta zorlanma gibi bir dezavantajı var
    Sorguların ve programın sabit olduğu statik analiz kullanımları için prosedürel makro yaklaşımı daha iyi olabilir

  • Mevcut Datalog canlanması zayıflıyor gibi görünse de çekirdek meraklıların dayanmaya devam ettiğini görmek sevindirici
    Son Datalog 2.0 konferansı eskisine göre epey küçüktü; ikinci HYTRADBOI konferansında da Datalog’un payı düşüktü
    İlk HYTRADBOI’de gönderilerin dörtte biri Datalog ile ilgiliydi
    Başkalarının yakın tarihli Datalog projelerini paylaşması da cesaret verici
    Şu anda büyük ölçekli bir yazılım migrasyonuna hazırlanırken eski bir SQL veritabanı için veri kalitesi pipeline’ı oluşturuyorum
    Sorguları iyi yapılandırırsanız çok okunabilir oluyor; veri kalitesi sorunlarını belirlemek ve bulmak için Datalog’un SQL’den çok daha kullanışlı olduğunu düşünüyorum

    • Büyük resme katılsam da Datalog 2.0’daki düşük katılımcı sayısını Datalog’un düşüşüne temsilî bir örnek olarak görmek zor
      Datalog 2.0, görece daha az bilinen Avrupa konferansı LPNMR’nin uydu çalıştayıydı ve o konferans tesadüfen Dallas’ta düzenleniyordu
      Bizzat katıldığımda da etkinlik biraz tenha hissettirdi; çalıştaya makale de gönderdim ama o alandaki insanlardan pek çoğunu göremedim
      İstisna olarak Nemo çözücüsünü tanıtan Avrupalı kişiler göze çarpıyordu
      Bu yıl katılımcının az olması, Datalog uygulamalarına ilgi eksikliğinden ziyade, zaten çok büyük itibarı olmayan bir konferansın uydu çalıştayı olması ve ana etkinliğin de ICLP olmasıyla daha iyi açıklanır bence
      Elbette saf Datalog motoru uygulamalarında pek yenilik kalmadığı yönündeki daha büyük iddiaya karşı çıkmaya çalışmıyorum
      Araştırma alanı çoktan bunun ötesine geçip akış işleme (HydroFlow), seçim (Dusa), genel chase’e yakın şeyler (Egglog’un chase motoru) gibi daha egzotik problemlere kaydı
      Vanilla Datalog’un sıkıcı olduğu konusunda genel olarak pek ihtilaf yok; ancak monoton ileri doygunluk ve Horn cümleleri, performans mühendisliği zemini iyi anlaşılmış zengin bir temel çizgi sunduğu için semiring veya Z-set gibi daha ilginç teorileri inşa etmeye elverişli

  • Durum makinesi ve ayrıştırma kısmı ilginizi çektiyse Rob Pike’ın eski sunumu Lexical Scanning in Go’yu da öneririm
    https://www.youtube.com/watch?v=HxaD_trXwRE
    Go ile yapılmış ama büyük kısmı diğer dillere de kolayca uygulanabilir
    Rust, Zig ve Go gibi modern dillerin Unicode/rune/grafem desteğini yerel olarak sunması güzel
    Java, .NET, C++ veya betik dilleriyle karşılaştırınca birçok sorun kendiliğinden ortadan kalkıyor

  • Yazarın Datalog çalışmalarını genel olarak seviyorum ama giriş materyallerinde ikili join öğretilmemesini isterdim
    İdeal durumların dışına çıkınca içi hızla karmakarışık hale geldi; genel join yöntemleri kafamda çok daha kolay genelleniyordu
    https://en.wikipedia.org/wiki/Worst-case_optimal_join_algorithm

  • Uzun zaman önce öğrenciyken Prolog’a biraz değinmiştim; nerelerde kullanıldığını ve neye yararlı olduğunu kabaca biliyorum ama derinlemesine anladığımı söyleyemem.
    O zamandan beri Datalog’un harika olduğuna dair şeyler duyup duruyorum; ama aslında Datalog’un Prolog’a göre neyi iyileştirdiğini tam oturtamıyorum.
    Az önce Wikipedia’daki Datalog sayfasına göz attım; Prolog’un performansı görece zayıf, Datalog’un ise ifade gücünü ve özellikleri azaltma pahasına performansı ciddi biçimde artırarak daha büyük veri kümelerini ve daha paralel işlemeyi mümkün kıldığı izlenimini verdi.
    Turing-tamlığın ortadan kalkması da buna dahil gibi görünüyor; bunun kilit nokta mı yoksa tamamen yanlış bir çıkarım mı olduğunu merak ediyorum.

    • Bildiğim kadarıyla Prolog, yalnızca ilişkileri kodlayınca yanıtı bulan deklaratif bir dil gibi görünür; ama pratikte kural sırasına epey bağımlıdır ve “cut” gibi ek yönergelere de ihtiyaç duyar.
      cut yalnızca boşa hesaplamayı önlemekle kalmaz, sonuçları da etkileyebilir.
      Datalog ise genel olarak sözdizimi farklı bir ilişkisel veritabanına daha yakındır.
    • Datalog daha basittir, Turing-tam değildir ve hatırladığım kadarıyla ileriye doğru çıkarım kullanır; bunun performans ve bellek özellikleri üzerinde zincirleme etkileri vardır.
      Prolog’da önemsiz sayılabilecek devasa bir arama uzayı, Datalog’da fazla bellek tükettiği için baştan ifade edilemez hale gelebilir.
      Datalog, CVT’li bir işe gidip gelme arabası; Prolog ise daha çok bir F1 arabası gibidir.
      Bir iyileştirmeden ziyade, insanların kendi ayaklarını uçurmaması için Prolog’un kısmen budanmış hali gibidir ve başka uygulamalara uygulaması ve gömmesi de çok daha kolaydır.
      Prolog’a alışkınsanız Datalog büyük ölçüde kısıtlayıcı gelecektir.
      call/3 yoktur, term/goal expansion yoktur; Datalog temelde Prolog’un en küçük ortak özellik kümesini alıp etkileşimli veritabanı araması için kullanmak üzere tasarlanmış sayılır.
      Hızlı Datalog kodu yazmak kolaydır, ama üst sınırı da çok daha düşüktür.
      Prolog da eşzamanlılığa izin verecek şekilde yazılabilir; ancak uygulamayı anlamayı gerektiren orta seviye bir iştir.
      Guarded Horn Clauses ve türev diller bu kısmı biçimselleştirmek için geliştirildi, fakat Prolog sonrasındaki Japonya kaynaklı gelişmeler oldukça anlaşılması güçtür.
      Prolog performansı; programcıya, kullanılan implementasyona ve nerede kullanıldığına büyük ölçüde bağlıdır.
      Lisp gibi Prolog da derleme zamanında bir DSL’den yerel makine kodu üretmek için kullanılabilir.
      Alttaki implementasyonun nasıl çalıştığını anlayıp kodu onun yapısına uygun yazarsanız yeterince hızlıdır.
      Ancak bunun için birkaç yıl boyunca tek bir implementasyonla Prolog kodu yazmanız gerekir.
      Prolog derleyici optimizasyonu üzerine de çok sayıda araştırma ve tescilli implementasyon örneği vardır.
      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 ve Rust kullanmak istiyorsanız, cozodb Rust ile yazılmıştır ve Datalog sorgu sözdizimi de sunar.

    • Cozodb harika görünüyor ama neredeyse pasif durumda gibi.
      2024 Kasım civarında incelerken SQLite depolama backend’inde kolayca yapılabilecek birkaç iyileştirme noktası bulmuştum.
      https://github.com/cozodb/cozo/issues/285
    • Cozodb belgelerde anlatıldığı gibi genel olarak iyi çalıştı ve onunla çalışmak keyifliydi.
      Program statik analizinde de kullandım; içeride sıralama ağaçları ve tip teknikleri kullanıyor.
      Belgeleri, blogdaki adım adım anlatımla ilk karşılaştırma yapmaya yetecek düzeyde; özellikle sorgu optimizasyonu çalışması ilginç.
      Ancak Rust’ta bellek içi çalışmıyorsanız veri serileştirme maliyeti yüksek ve proje en iyi ihtimalle sessiz durumda.

  • Eskiden Clojure hayranları Datalog’un SQL’den daha iyi olduğunu ve ilişkisel veritabanlarının hepsinin SQL kullanmasının üzücü olduğunu söylerdi
    Neden böyle düşündüklerini yeterince derinlemesine inceleyememiştim

    • Temelde Datalog, SQL’e göre çok daha az laf kalabalığı içerir, görünümleri ayırmanın maliyeti çok daha düşüktür ve geçişli kapanışı ezici derecede iyi destekler
      http://canonical.org/~kragen/binary-relations basit, özyinelemesiz bir sorguyla başlamıştı; SQL çevirisi şimdiden suç sayılacak kadar kötü, düzgün ayrıştırılmış SQL çözümü ise idamlık
      Son dönemde ANSI SQL’e özyineleme özelliği eklendiği için artık tamamen imkânsız değil, ama üç büyük dezavantajı var
      Birincisi, yanlışlıkla SQL’i Turing-complete hale getirdiler; buna karşılık Datalog sorgularının sonlanması garanti edilir
      İkincisi, kullanımı hâlâ son derece hantal
      Üçüncüsü, ilk nedenden dolayı çoğu zaman tam olarak uygulanmadığından güvenip kullanmak zor
    • Clojure/Datomic lehçesini anlamak zor, ama genel yöne katılıyorum
      Datalog’u çevrimiçi, kullanıcı dostu bir notebook ortamında kurcalamak istiyorsanız Percival’ı öneririm
      https://percival.ink/
      Datalog uygulamalarının genelinde “ANSI SQL”e karşılık gelen bir standart yok, ama temel fikri kavradığınızda diğer Datalog’lar da çok zor gelmez
      Datalog’u SQLite’a derleyen bir Percival fork’u da başlattım; ikisinin aynı şeyi nasıl ifade ettiğini görmek isterseniz bakabilirsiniz
      https://percival.jake.tl/
      Toplama işlemleri ve daha gelişmiş join’ler henüz tamamlanmadı, ama temel biçim iyi çalışıyor
      Logica, bir Google araştırmacısının yaptığı çok daha ciddi ve olgun bir Datalog→SQL derleyicisi; BigTable, DuckDB ve birkaç SQL lehçesine derliyor
      https://logica.dev/
      Datalog’un bir büyüklük mertebesinden fazla kolaylaştığı alan özyinelemeli sorgular/kurallar ile uğraşırken ortaya çıkıyor
      SQL’de de mümkün, ama pipetle oyun hamuru içmeye daha yakın bir his
      Frank’in Materialize.com’unda, eski ANSI SQL özyineleme yönteminden çok daha iyi olan “WITH MUTUALLY RECURSIVE” adlı bir SQL biçimi var ve Notion’da sayfa yükleme sorguları ile veri senkronizasyonu için değerlendiriliyor
      https://materialize.com/blog/recursion-in-materialize/
      Feldera’da da özyinelemeli görünümler için benzer bir biçim var
      https://www.feldera.com/blog/recursive-sql-queries-in-feldera
      Feldera’yı sevmemin nedeni, her “kuralı” veya alt görünümü tek bir dev ifadeye koymak yerine ayrı ifadeler olarak yazabilmeniz
      Test ederken gördüğüm başlıca dezavantaj, Feldera’nın SQL lehçesinin Apache Calcite’tan miras aldığı epey kısıta sahip olması; Materialize SQL lehçesi ise PostgreSQL uyumluluğunu çok sıkı biçimde yakalamaya çalışıyor

  • Yeni bir McSharry yazısı, harika
    Son kontrol ettiğimde VMWare differential datalog’dan uzaklaşmış gibiydi

    • Differential Datalog ekibi Feldera’yı kurdu
      https://www.feldera.com/
      differential Datalog’dan differential SQL’e geçmişler gibi görünüyor; muhtemelen Datalog’u satmanın gerçekten zor olduğunu fark ettikleri için