Rust से इंटरैक्टिव Datalog इंजन बनाना

 (github.com/frankmcsherry)
1 पॉइंट द्वारा GN⁺ 2025-06-16 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • लॉजिक प्रोग्रामिंग वर्कशॉप में Datalog टूल्स की usability और performance सीमाएँ सामने आने के बाद, Rust-आधारित इंटरैक्टिव Datalog shell datatoad का प्रयोग शुरू हुआ
  • datatoad का लक्ष्य ऐसी संरचना है जिसमें runtime पर rules जोड़े जा सकें और नए facts लगातार derive किए जा सकें; यह columnar storage और LSM layers से fact sets में duplicate handling की लागत घटाता है
  • rule evaluation Datalog body को join problem में बदलकर करता है, और stable स्थिति के आधार पर full evaluation और incremental evaluation को अलग करता है ताकि पहले से calculate किए गए stable-stable joins से बचा जा सके
  • Graspan dataset experiments में, सिर्फ manual rule rewriting और intermediate relations जोड़ने से aliasing analysis 736.34 सेकंड·50.13GB से घटकर 119.34 सेकंड·5.32GB तक आ गया
  • आगे का काम e-graph-आधारित join plan optimization, layered trie, fixed-width byte representation, disk spill, distributed evaluation, streaming join और demand transform तक बढ़ा

datatoad जिस समस्या को हल करना चाहता है

  • Memorial Day weekend की लॉजिक प्रोग्रामिंग वर्कशॉप में program analysis के लिए Datalog tools की असुविधा साफ दिखी, और इसी से सरल, उपयोगी और तेज़ Datalog implementation बनाने की कोशिश शुरू हुई
  • implementation का लक्ष्य static example runner नहीं, बल्कि interactive Datalog shell है
    • facts को bulk में load किया जा सकता है
    • runtime पर नए rules जोड़े जा सकते हैं
    • जोड़े गए rules के results को existing state में लगातार reflect किया जाता है
  • code को datatoad repository में follow किया जा सकता है
  • मौजूदा datafrog Datalog engine के core algorithms देता है, लेकिन यह ऐसे रूप में है जहाँ user को खुद wiring करनी पड़ती है; datatoad उन्हीं ideas को ज़्यादा easy-to-use रूप में फिर से organize करता है
  • httpd dataflow graph के nullability example में datatoad को Vec<String> data और uncompiled query के साथ 8.3 सेकंड लगे, जो (u32, u32) data इस्तेमाल करने वाले datafrog example के लगभग 2 सेकंड से करीब 4 गुना धीमा है
  • reachability problem में इसने datafrog implementation जितनी ही output tuples दीं, लेकिन सामान्य correctness verification अभी पूरी नहीं हुई है

Datalog model और shell structure

  • Datalog एक language है जिसमें simple logical rules लिखने पर उन rules से reachable सभी facts derive किए जाते हैं
  • rule head और body से बना होता है
    • उदाहरण: tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c).
    • tri, edge relations हैं और a, b, c variables हैं
    • head में आने वाले variables body में भी होने चाहिए
  • facts को empty body वाले rules के रूप में handle किया जाता है
    • उदाहरण: edge(1, 2) :- .
    • कई heads का इस्तेमाल करके एक साथ कई facts लिखे जा सकते हैं
  • Datalog की monotonicity के कारण rules या facts जोड़ने पर true facts का set घटता नहीं है, और same input rule set rule order से independent होकर same result तक पहुँचता है
  • Rust representation में Rule, Atom, Term तीन structures मुख्य हैं
    • Rule { head: Vec<Atom>, body: Vec<Atom> }
    • Atom { name: String, terms: Vec<Term> }
    • Term::Var(String) या Term::Lit(String)
  • literals को store करने के लिए String की जगह Vec<u8> का इस्तेमाल होता है
    • जरूरी properties literal equality और arbitrary sort order हैं
    • bytes का String, (u32, u32) या कोई और अर्थ होना user पर खुला है
  • interpreter state rules और facts को साथ रखती है
    • rules: Vec<Rule>
    • facts: facts::Facts
  • shell input line को Datalog में parse करने के बाद State::extend और State::update को call करता है, और .list command से हर relation name और fact count print करता है

Parsing और facts storage

  • parser parse.rs में है और Soufflé syntax से ली गई form इस्तेमाल करता है
  • variables ? से शुरू होते हैं
  • tokens ., ,, (, ), :-, ? तक सीमित हैं, और बाकी text को atom या term name के रूप में handle किया जाता है
  • tokenizer whitespace हटाता है और :- को ← में बदलकर single symbol की तरह scan करता है
  • rule parsing turnstile से पहले तक head atoms और period से पहले तक body atoms पढ़ने के तरीके से होती है
    • atom name, left parenthesis, term list और right parenthesis से बना होता है
    • term में ? हो तो variable, नहीं हो तो literal होता है
  • invalid rule None return करता है, और फिलहाल यह detail में नहीं बताता कि कौन-सा हिस्सा गलत है
  • negation rules जोड़ने के लिए Exclamation token चाहिए, लेकिन अभी इसे handle नहीं किया गया है

Fact set का lifecycle

  • simple Vec<Vec<String>> storage में allocations nested होती हैं, इसलिए यह memory management के लिए नुकसानदेह है
  • datatoad Rust types को flat layout की कुछ linear allocations में बदलने के लिए columnar का इस्तेमाल करता है
    • string bytes, string boundaries और fact boundaries को अलग arrays में store करता है
  • FactContainer sorted और deduplicated fact list को wrap करता है, और wrapper type के रूप में sorting और deduplication invariants का संकेत देता है
  • columnar container practically append-only है, इसलिए middle changes के लिए ठीक नहीं; नए facts जोड़ने के लिए log-structured merge-tree(LSM) form इस्तेमाल होता है
    • FactLSM { layers: Vec<FactContainer> }
    • layers के sizes geometric रूप से बढ़ें, ऐसा manage किया जाता है
    • size में 2x के भीतर वाली layers को merge करके sorted और deduplicated state maintain की जाती है
  • FactBuilder के पास unsorted और duplicate हो सकने वाला active area और sorted·deduplicated layers दोनों होते हैं
  • हर relation के facts तीन stages में move करते हैं
    • to_add: नए आए facts जिनकी novelty अभी check नहीं हुई है
    • recent: distinct facts जिन्हें अभी process करना है
    • stable: distinct facts जो पहले ही पूरी तरह process हो चुके हैं
  • FactSet::advance recent को stable में move करता है, और to_add से उन facts को हटाकर नया recent बनाता है जो पहले से stable में हैं

Rule evaluation एक join problem है

  • Datalog rule body को relational database के equi-join के रूप में देखा जा सकता है
  • triangle rule example इस तरह है
    • tri(?a, ?b, ?c) :- edge(?a, ?b), edge(?b, ?c), edge(?a, ?c).
  • सभी variable assignments को सीधे list करें तो finite होने पर भी संख्या बहुत बड़ी हो जाती है, इसलिए common variables के key columns के आधार पर sort करके merge किया जाता है
  • implementation body को right से left की ओर reduce करता है
    • आखिरी दो relations को join करके intermediate relation बनाता है, फिर उसे left relation से join करता है
    • अगर सिर्फ एक body atom हो, तो उसे केवल head form में transform करता है
  • JoinPlan में ये जानकारी होती है
    • body atoms को join के हिसाब से rearrange/filter करने वाले bodys
    • हर intermediate join की key arity और output projection रखने वाले joins
    • head atoms में insert किए जाने वाले coordinates या literals दिखाने वाले heads
    • final head generation join की arity
  • मौजूदा plan simple right-linear join plan है
  • JoinPlan बनाते समय हर variable की leftmost·rightmost occurrence positions का इस्तेमाल करके तय किया जाता है कि किस variable value को कब तक preserve करना है, और body atom columns को dead, key, value columns में बाँटा जाता है
  • core function implement_plan(rule, plan, pos, stable, facts) है
    • नया rule जोड़े जाने पर stable = true के साथ पूरे facts पर शुरू करता है
    • existing rules को बार-बार apply करते समय stable = false के साथ सिर्फ new derivations calculate करता है

Incremental join और merge join

  • join bilinear होता है, इसलिए इसे इस तरह तोड़ा जा सकता है
    • (A + a) ⋈ (B + b) = A ⋈ B + A ⋈ b + a ⋈ B + a ⋈ b
  • पहले से stable के बीच बना A ⋈ B दोबारा calculate करने की ज़रूरत नहीं है
  • अगर सिर्फ़ नई derivations चाहिए हों, तो केवल तीन joins किए जाते हैं
    • A ⋈ b
    • a ⋈ B
    • a ⋈ b
  • join_with, stable flag के आधार पर stable-stable join को include या exclude करता है
  • असली join sorted दो inputs को क्रम से scan करने वाला merge join है
    • keys समान हों तो उस key के लिए सभी combinations पर action call करता है
    • keys अलग हों तो gallop के ज़रिए अगले संभावित matching point तक तेज़ी से skip करता है
  • gallop EmptyHeaded से लिया गया idea है, जिसमें monotonic condition true रहने तक exponentially आगे बढ़ा जाता है और फिर binary तरीके से range को संकरा किया जाता है

Nullability analysis experiment

  • experiment data Graspan project का data है, और Google Drive पर भी अब तक मौजूद है
  • dataflow analysis input में e और n दो relations हैं
    • n(?a, ?b): value ?a, location ?b पर use हो सकती है
    • e(?a, ?b): एक location ?a की value दूसरी location ?b में move हो सकती है
  • reachability rule इस प्रकार है
    • n(?a, ?c) :- n(?a, ?b), e(?b, ?c) .
  • httpd input में initial .list यह दिखाता है
    • e: 9,905,624
    • n: 138,331
  • rule को सीधे चलाने पर लगभग 15 सेकंड लगते हैं, और n 9,393,283 हो जाता है
  • slow होने की एक वजह यह है कि n को join key के हिसाब से rearrange करने वाली temporary relation .temp-0-0-in 9,393,283 तक बढ़ गई
  • user rule को rewrite करे तो performance बेहतर हो जाती है
    • m(?loc, ?val) :- n(?val, ?loc) .
    • m(?loc, ?val) :- m(?mid, ?val), e(?mid, ?loc) .
  • उसी httpd input पर rewrite के बाद दूसरा rule लगभग 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 number पर * लगा है, और paper ने कुल समय को साथ में report किया था; input identifier collision की वजह से इसे ठीक वैसा ही run मानना मुश्किल है
  • practitioners द्वारा इस्तेमाल किए जाने वाले tool से compare करना हो तो Soufflé शायद अधिक उपयुक्त target हो सकता है

Aliasing analysis और manual optimization

  • दूसरी analysis Zheng and Rugina की aliasing analysis है, जिसे Graspan ने अपनाया था
  • input relations दो प्रकार की हैं
    • A(?val, ?loc): ?loc <- ?val
    • D(?val, ?loc): ?loc, *?val रूप में use होता है
  • goal memory alias और value alias निकालना है
    • memory alias: दो lvalue expressions एक ही memory location को point कर सकते हैं
    • value alias: दो expressions एक ही pointer value evaluate कर सकते हैं
  • paper notation में ^T, ^?, ^* आते हैं
    • ^T: relation transpose
    • ^?: optional term
    • ^*: 0 या अधिक बार repetition
  • Datalog में ^? को दो rules में बांटकर express किया जाता है, और ^* को identity relation explicitly डालने के तरीके से handle किया जाता है
  • initial rule execution में काफ़ी समय लगता है
    • आख़िरी दो identity initialization rules input करने के बाद 686.57 सेकंड और 736.34 सेकंड लगे
    • process ने 50.13GB इस्तेमाल किया
    • V: 361,947,256
    • M: 92,806,768
    • F: 2,669,647
  • transposed relations -V, -M, -a, -d को explicitly इस्तेमाल करके -in temporary relation हटाई गई
    • कुल 815.92 सेकंड, यानी लगभग 13.6 मिनट
    • memory 31.96GB
  • Zheng and Rugina का approach demand-driven है और असल में केवल M चाहिए, इसलिए V को M में inline किया गया
    • -V के 361,947,256 entries नहीं बनाए गए
    • memory घटकर 18.96GB हो गई
  • repeated join fragment को Fd नाम देकर reuse किया गया, और बाद में F की जगह Fd को directly calculate करके identity problem भी कम की गई
  • MFd intermediate relation introduce करने वाले final form से ये results मिले
    • execution time: 119.34 सेकंड
    • memory: 5.32GB
    • -M: 92,806,768
    • Fd: 1,858,986
    • MFd: 73,474,947
  • सिर्फ़ manual rewrite से initial attempt की तुलना में memory और execution time में लगभग 10x सुधार हुआ
  • named intermediate results बनाने से desired bushy-tree join plan को कुछ हद तक सीधे construct किया जा सकता है, लेकिन V जैसी असल में ज़रूरी नहीं relation को नाम दे दें तो उसे बड़े cost पर generate करना पड़ता है

Demand-driven queries और magic sets

  • demand-driven query वह तरीका है जिसमें किसी specific target fact के लिए ज़रूरी हिस्से ही explore किए जाते हैं
  • approximate solution के रूप में magic sets इस्तेमाल किए जा सकते हैं
    • यह target literal को query में embed करने वाला transformation है
    • सभी d के बजाय केवल जिन d में interest है, उनसे शुरू करने वाली expression सोची जा सकती है, लेकिन सरलता से apply करने पर यह गलत हो सकती है
  • magic sets optimal answer नहीं हैं, और अधिक efficient हो सकने वाले approach खोजने के लिए related papers और पढ़ने की योजना है
  • related links ये हैं

Join plan optimization और data-parallel IR

  • Datalog की appeal Horn clause खुद से ज़्यादा इस बात में है कि यह data-parallel computation की मुख्य problem, यानी data rendezvous, को साफ़ तौर पर सामने लाता है
  • rule h(x, y, z) :- b1(x, y), b2(y, z) . को हर y के लिए related x और z को एक जगह collect करने की problem के रूप में देखा जा सकता है
  • data-parallel computation की basic operation key के हिसाब से records collect करके user logic को सौंपना है, और join उन्हीं में selective routing express करता है
  • simple IR ये opcodes इस्तेमाल करता है
    • Var(String): named collection
    • Map(Action): filter, permutation, projection
    • Key(usize): आगे के कुछ columns को key के रूप में mark करना
    • Mul(usize): समान key length वाली कई collections को combine करना
  • बाद में Map और Key को Action.key_arity में merge कर दिया गया
  • Action में literal filter, variable equality filter, projection, key arity होते हैं
  • सबसे सरल starting point यह है कि body atoms को सभी cross join करके हर head पर filter और projection लगा दिए जाएं; इससे सही answer तो बनता है, लेकिन performance बहुत खराब होती है

e-graph आधारित optimization

  • optimization में e-graph और equality saturation का इस्तेमाल किया गया
  • संदर्भ सामग्री के रूप में egg webpage, पिछला लेख, और egg इस्तेमाल हुए
  • term graph को Id लगे ENode<T> के map के रूप में दर्शाया गया है, और समान nodes साझा करके program को ज़्यादा संक्षिप्त रूप में दिखाता है
  • लागू किए गए e-graph नियम तीन हैं
    • MulPermute: Mul(k) input permutations को equivalent बनाता है
    • MulPartition: Mul(k) को कई तरीकों से विभाजित कर equivalent बनाता है
    • MapPushdown: Map को Mul(2) के नीचे push कर keyed join का रूप बनाता है
  • example rule यह है
    • head(?a, ?b) :- a(?x, ?a), b(?y, ?x), b(?y, ?z), a(?z, ?b) .
  • equality saturation के बाद extraction चरण में cost दी जाती है
    • Map की cost output columns की संख्या है
    • Mul की cost key columns की संख्या और inputs के non-key columns की संख्या का योग है
    • Var की cost 0 है
    • बराबरी होने पर Map की संख्या, फिर Mul की संख्या minimize की जाती है
  • example में चुना गया plan wave two में मिला, जिसमें अधिकतम दो non-correlated columns थे
    • inputs a, b के लिए map
    • एक join
    • intermediate projection
    • खुद के साथ join
    • final projection
  • यह plan search release build में भी लगभग 40ms लेती है, और अधिकांश समय equivalence saturation में लगता है

optimized plan execution update

  • 2025-06-29 update में optimized plan execution implement किया गया
  • plan Vec<ENode<Op>> के रूप में आता है, लेकिन actual execution में हर node को स्वतंत्र रूप से execute नहीं किया जाता
  • intended execution तरीका यह है
    • हर Var के लिए उस पर निर्भर कई Map को एक ही external collection scan में apply करना
    • हर Mul के लिए उस पर निर्भर कई Map को एक ही join scan में apply करना
  • Op::Map(action) सीधे perform होने वाला operation कम, dependency operation में queue किया जाने वाला task ज़्यादा है
  • इसके लिए TempAction introduce किया गया
    • literal filter
    • variable equality filter
    • column reference या string literal रख सकने वाला projection
  • execution plan preparation चरण body और head को अलग करके Map actions को input node के हिसाब से इकट्ठा करता है
  • Var execution में name handling तीन cases में बंटता है
    • head generation में head relation name में लिखा जाता है
    • identity transformation existing input name को reuse करता है
    • non-trivial transformation .temp-* temporary name में store करता है
  • Mul(2) execution दो inputs की key arity और names की जांच करता है और join_with को call करके कई builders में results जमा करता है
  • complex aliasing example में optimized plan execution 114.28 seconds रहा, जो पहले के 119 seconds range से करीब 5 seconds तेज था, लेकिन कारण स्पष्ट नहीं है
  • multi-rule optimization अभी implement नहीं हुआ है, और plan approach पर ही फिर से विचार करना पड़ सकता है

fact representation optimization

  • 50GB को 5GB तक घटाया गया, लेकिन माना गया कि अभी भी ज़रूरत से लगभग 10 गुना अधिक memory इस्तेमाल हो रही है
  • बड़े relation -M की largest layer में 57,289,225 facts हैं और यह लगभग 2,098,253,766 bytes इस्तेमाल करती है
    • fact boundaries: 458,313,800 bytes
    • term boundaries: 916,627,600 bytes
    • actual byte data: 723,312,366 bytes
  • पहला optimization arity के स्थिर होने का फायदा उठाता है
    • अगर सभी facts 2 columns वाले हों, तो fact boundaries को सिर्फ stride और length से represent किया जा सकता है
    • 458MB स्तर का boundary data व्यावहारिक रूप से हट जाता है
  • दूसरा optimization term length को समान बनाना है
    • numbers को 7-digit fixed-width strings बनाने पर term boundaries भी stride और length से represent हो सकती हैं
    • इसके बदले actual byte count बढ़ सकता है
  • तीसरा optimization numbers को text नहीं, binary के रूप में represent करना है
    • 7-digit number u32 के 4 bytes में आ जाता है
    • यह 3 bytes में भी आ जाता है, इसलिए 57,289,225 × 2 × 3 = 343,735,350 bytes होगा
    • लगभग 2GB से लगभग 350MB तक घटकर करीब 6.10 गुना कमी आती है
  • पहले term repetitions को compress करने पर और कमी आती है
    • 57,289,225 facts हैं, लेकिन distinct first terms सिर्फ 1,147,612 हैं
    • (Term, Term) के बजाय (Term, [Term]) रूप में store करने पर largest layer लगभग 184,491,407 bytes तक घट जाती है
    • initial 2GB की तुलना में लगभग 11.37 गुना कमी आती है
  • 2025-07-02 update में first optimization apply किया गया
    • largest batch theoretical value 343,735,350 bytes से 32 bytes अधिक, यानी 343,735,382 bytes हो गया
    • execution time लगभग 115 seconds से लगभग 95 seconds तक घटा, यानी करीब 20% improvement हुआ

Layered trie representation

  • 2025-07-20 update में layered trie workable हो गया
  • row-oriented representation और column-oriented layered trie representation की तुलना की गई
    • 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 sorted row representation में आगे के columns की repetitions को suppress करने का तरीका है
  • हर column value lists की list है
    • हर list पिछले column prefix से match करने वाली sorted distinct values की सूची है
    • किसी column की lists की संख्या पिछले column के कुल items की संख्या के बराबर होती है
  • इसे tree की तरह देखा जा सकता है, लेकिन actual implementation columns के रूप में रखी जाती है
  • फायदा यह है कि prefix unit पर search, join, difference और merge perform किए जा सकते हैं
  • जिन cases में distinct values बहुत कम हों और पूरी row को एक साथ देखना बेहतर हो, वहां row-oriented approach ज़्यादा लाभदायक हो सकती है
  • common abstraction के रूप में FactContainer trait introduce किया गया
    • form
    • len
    • apply
    • join
    • except
    • merge
  • apply recursion के बजाय explicit stack से हर layer की range track करता है, rows बनाता है और action को pass करता है
  • align दो layered tries के prefixes को match करके देखने वाला common helper है
    • Ordering::Less: range जो केवल self में है
    • Ordering::Greater: range जो केवल other में है
    • Ordering::Equal: arity length prefix दोनों तरफ common है
  • join, except, merge सभी align के ऊपर implement किए गए हैं
    • join common prefix से remaining extension को expand कर cross join करता है
    • except self-only range को TrieBuilder में graft करता है
    • merge self-only, other-only, equal ranges को appropriately एक-एक बार graft करता है

fixed-width optimization और performance

  • fixed-width [u8; 4] में upgrade कर सकने पर comparison performance काफी बेहतर हो जाती है
  • layered trie columns के हिसाब से fixed-width optimization apply कर सकता है, इसलिए long term में row से ज़्यादा फायदेमंद होने की संभावना है
  • except और merge में upgrade·downgrade आसानी से apply किए गए, लेकिन join में apply करना Rust type problems की वजह से ज़्यादा मुश्किल था
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 optimization में कम से कम करीब 2x और सुधार की गुंजाइश है
  • सिर्फ inner loop को re-order करने की कोशिश से मापने लायक सुधार नहीं हुआ

compiled code के स्तर तक specialize करना

  • समान लंबाई वाले term और समान arity वाले facts का पता चलने पर Vec<u8> को Vec<[[u8; B]; T]> की तरह देखा जा सकता है
  • इस रूप में Rust डेटा के आकार को बेहतर समझता है, जिससे bounds और length check की लागत घटती है, और comparison खास तौर पर सस्ता हो जाता है
  • comparison datatoad में कई जगह इस्तेमाल होता है
    • facts batch को sort करना और duplicate हटाना
    • batch merge
    • join key merge
    • नए facts को मौजूदा facts से compare करके filter करना
  • baseline performance इस तरह है
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
  • sort optimization का प्रयोग 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
  • merge optimization को दोनों inputs को concatenate करने के बाद sort और dedup करने वाली सरल विधि से implement किया गया
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 की compiled performance तक नहीं पहुंचा है
  • बची हुई comparison cost join और antijoin में भी है, और trie-based structure पर जाते समय ऐसे ही optimization मौकों को फिर से देखने की योजना है
  • unsafe हटाने का तरीका खोजा जा रहा है, और यह निष्कर्ष भी जोड़ा गया है कि unsafe code से बचना चाहिए

अभी बाकी काम

  • disk spill

    • columnar storage कम संख्या में बड़े allocations से बना है
    • बनाते समय memory के बजाय file में लिखा जा सकता है और memory map के जरिए फिर इस्तेमाल किया जा सकता है

  • distributed evaluation

    • join, duplicate removal, और distinctness check key equality पर आधारित हैं
    • key और उससे जुड़ा data कई workers में distribute किया जा सकता है
    • timely_communication के जरिए इसे कई processes तक scale किया जा सकता है

  • streaming rule evaluation

    • मौजूदा join binary join और materialized output का इस्तेमाल करता है
    • अगर जरूरी indexes हों, तो ऐसा plan बनाया जा सकता है जो internal state को materialize न करे
    • worst-case optimal join को भी यहीं handle किया जाएगा

  • custom representation specialization

    • transitive closure का पता लगाकर strongly connected component decomposition के लिए specialize करने का idea है
    • equivalence relation union-find data structure का इस्तेमाल कर सकता है
    • bddbddb और factorized databases को भी संबंधित विषयों के रूप में लिया गया है

  • संबंधित facts की खोज

    • demand transform को समझकर लागू करना होगा
    • interactive Datalog exploration के लिए इसे जरूरी transformation माना गया है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-06-16
Hacker News की राय

  • यह देखकर मज़ा आया कि यह लेख नंबर 1 पर पहुंच गया है
    अभी Differential Datalog और Rust से एक रियल-टाइम स्ट्रैटेजी गेम बना रहा हूं, और गेम लॉजिक DDL से मैनेज करवा रहा हूं
    ज़्यादातर यह नए आइडिया से परिचित होने और अंतहीन yak shaving करने का बहाना जैसा ही है
    https://github.com/vmware-archive/differential-datalog

    • ddlog से बना कोई शानदार डेमो लगता है
      वैसे, ddlog टीम ने अब Feldera शुरू कर दी है, और Rust में DBSP को सीधे इस्तेमाल करने पर भी विचार किया जा सकता है
      https://github.com/feldera/feldera
    • सोचता हूं कि मूल लेख की repository और Rust analyzer को चलाने वाले crate salsa को मिलाकर कोई Frankenstein-style differential datalog बनाया जा सकता है या नहीं
      https://github.com/salsa-rs/salsa
    • implementation की स्थिति कैसी है, और यह कितनी दूर जा सकता है, जानने की उत्सुकता है
      DDLog अब सक्रिय रूप से maintained नहीं है, इसलिए यह और भी दिलचस्प है

  • “मुझे, एक कुख्यात खलनायक को, इस आधे यकीन के साथ बुलाया गया था कि मैं वह सज़ा भुगतने जा रहा हूं जो मुझे बहुत पहले मिल जानी चाहिए थी।” — इस साल पढ़े गए tech blog posts में सबसे बेहतरीन पहला वाक्य
    narrator की बीच-बीच में की गई टिप्पणियां भी शानदार थीं, और इतना technically deep होते हुए भी इतना मज़ेदार पढ़ने वाला लेख दुर्लभ है
    alias queries को optimize करने की यात्रा detective novel जैसी लगी, और पाठक भी साथ में 50GB memory usage पर कराहता है और 5GB तक घटने पर खुशी मनाता है
    code और लेख, दोनों बेहतरीन हैं

  • mangle datalog को Rust में port करने पर थोड़ा काम किया है
    यह https://github.com/google/mangle/tree/main/rust पर है, और Go implementation वाली ही repository में है
    priority बहुत ऊंची नहीं है, ऊपर से second-system syndrome भी है, इसलिए प्रगति धीमी है
    Mangle Rust की दिशा यह है कि memory mapping के जरिए disk से facts पढ़ते-लिखते हुए arbitrary-size data संभाले जाएं, जबकि Go implementation in-memory तरीके का है
    यह लेख अच्छा है क्योंकि यह Datalog को parse करता है और LSM tree को भी संभालता है, और datafrog से जुड़ी सामग्री की तुलना में इसे follow करना कहीं आसान है
    Rust में ascent, crepe जैसे Datalog implementations काफी हैं जो procedural macros इस्तेमाल करते हैं, लेकिन downside यह है कि runtime पर queries लेना मुश्किल होता है
    अगर query और program fixed हों, जैसे static analysis के use case में, तो procedural macro approach बेहतर भी हो सकती है

  • मौजूदा Datalog revival कमजोर पड़ता दिख रहा है, फिर भी core enthusiasts को टिके रहना देखकर अच्छा लगता है
    हाल की Datalog 2.0 conference पहले से काफी छोटी थी, और दूसरी HYTRADBOI conference में भी Datalog का हिस्सा कम था
    पहली HYTRADBOI में submissions का एक-चौथाई Datalog से संबंधित था
    यह भी उत्साहजनक है कि दूसरे लोग हाल के Datalog projects share कर रहे हैं
    अभी मैं बड़े scale के software migration की तैयारी करते हुए legacy SQL database के लिए data quality pipeline बना रहा हूं
    queries को अच्छी तरह structure किया जाए तो वे बहुत readable होती हैं, इसलिए data quality issues identify और locate करने में Datalog मुझे SQL से कहीं ज़्यादा उपयोगी लगता है

    • बड़े रुझान से सहमत होने के बावजूद, Datalog 2.0 में कम attendance को Datalog के decline का प्रतिनिधि उदाहरण मानना मुश्किल है
      Datalog 2.0 यूरोप की अपेक्षाकृत कम जानी-पहचानी conference LPNMR का satellite workshop है, और वह conference संयोग से Dallas में हुई थी
      खुद attend करने पर भी event कुछ sparse लगा, और मैंने workshop में paper भी दिया था, लेकिन उस field के बहुत लोग दिखाई नहीं दिए
      exception के तौर पर Nemo solver पेश करने वाले यूरोपीय लोग जरूर दिखे
      मेरे हिसाब से इस साल कम attendees होना Datalog implementations में रुचि की कमी से ज़्यादा यह दिखाता है कि यह पहले से ही बहुत प्रसिद्ध न रही conference का satellite workshop था, और main event भी ICLP था
      बेशक, मैं इस बड़े दावे का विरोध नहीं कर रहा कि pure Datalog engine implementation में अब बहुत कम novelty बची है
      research space इससे काफी आगे निकलकर streaming (HydroFlow), choice (Dusa), और general chase के करीब चीज़ों (Egglog का chase engine) जैसे ज़्यादा exotic problems की ओर चला गया है
      vanilla Datalog boring है, इस पर आम तौर पर बहुत असहमति नहीं है, लेकिन monotone forward saturation और Horn clauses एक समृद्ध baseline हैं जिनका performance engineering landscape अच्छी तरह समझा गया है, इसलिए semiring या Z-set जैसी ज़्यादा दिलचस्प theories बनाने के लिए वे अच्छे हैं

  • अगर state machine और parsing वाला हिस्सा दिलचस्प लगा हो, तो Rob Pike की पुरानी talk Lexical Scanning in Go भी recommend करूंगा
    https://www.youtube.com/watch?v=HxaD_trXwRE
    Go में है, लेकिन इसका अधिकांश हिस्सा दूसरी languages पर भी आसानी से लागू किया जा सकता है
    Rust, Zig, Go जैसी modern languages में Unicode/rune/grapheme का native support होना अच्छा है
    Java, .NET, C++ या scripting languages से तुलना करें तो कई समस्याएं बस गायब हो जाती हैं

  • लेखक का Datalog work मुझे कुल मिलाकर पसंद है, लेकिन चाहता हूं कि introductory material में binary joins न सिखाए जाएं
    ideal cases से बाहर निकलते ही internals जल्दी messy हो गए, और general join style वाले methods दिमाग में generalize करना कहीं आसान लगा
    https://en.wikipedia.org/wiki/Worst-case_optimal_join_algorithm

    • इससे संबंधित McSherry की ठीक पिछली blog post यह दिखाती थी कि सही query plan adjustments मानकर, binary joins भी worst-case optimal execution time हासिल कर सकते हैं
      https://github.com/frankmcsherry/blog/blob/master/posts/2025-05-29.md

  • बहुत पहले पढ़ाई के दौरान Prolog से थोड़ा-सा पाला पड़ा था, और यह मोटे तौर पर पता है कि इसका इस्तेमाल कहाँ होता है और यह किस काम में उपयोगी है, लेकिन गहरी समझ नहीं है
    उसके बाद से Datalog के शानदार होने की बातें लगातार सुनता रहा हूँ, पर असल में Datalog, Prolog की तुलना में क्या सुधार करता है यह साफ़ नहीं बैठता
    अभी-अभी Wikipedia का Datalog पेज सरसरी तौर पर देखा, तो ऐसा लगता है कि Prolog का प्रदर्शन अपेक्षाकृत खराब है और Datalog अभिव्यक्ति-क्षमता और फीचर्स कम करके प्रदर्शन में बड़ा सुधार करता है, जिससे बड़े datasets और अधिक parallelized processing संभव होती है
    लगता है इसमें Turing completeness का हट जाना भी शामिल है, लेकिन उत्सुक हूँ कि यही मुख्य बात है या मैं पूरी तरह गलत दिशा में हूँ

    • जितना मुझे पता है, Prolog दिखने में declarative लगता है—बस relations encode कर दो और यह जवाब ढूँढ़ देता है—लेकिन असल में यह rules के order पर काफी निर्भर करता है और “cut” जैसे अतिरिक्त निर्देशों की भी जरूरत पड़ती है
      cut सिर्फ बेकार computation को रोकता ही नहीं, बल्कि परिणामों को भी प्रभावित कर सकता है
      इसके विपरीत Datalog आम तौर पर syntax में दूसरे relational databases के ज्यादा करीब है
    • Datalog ज्यादा सरल है, Turing-complete नहीं है, और याद पड़ता है कि यह forward reasoning का इस्तेमाल करता है, जिसका performance और memory characteristics पर cascading असर पड़ता है
      Prolog में कोई मामूली-सा विशाल search space भी Datalog में इतनी memory खा सकता है कि उसे व्यक्त करना ही संभव न हो
      Datalog, CVT वाली commuter car जैसा है, और Prolog, F1 car के ज्यादा करीब है
      यह सुधार से ज्यादा Prolog का एक आंशिक रूप से सीमित किया गया संस्करण है ताकि लोग अपने ही पैर पर कुल्हाड़ी न मार लें, और इसे दूसरे applications में implement और embed करना भी कहीं आसान है
      अगर आप Prolog से परिचित हैं, तो Datalog आम तौर पर काफी सीमित और खीझ पैदा करने वाला लगेगा
      call/3 भी नहीं है, term/goal expansion भी नहीं है, और Datalog मूलतः Prolog की न्यूनतम common functionality निकालकर interactive database search में इस्तेमाल करने के लिए designed है
      तेज Datalog code लिखना आसान है, लेकिन इसकी upper bound भी काफी कम है
      Prolog को भी concurrency की अनुमति देने वाले तरीके से लिखा जा सकता है, लेकिन इसके लिए implementation को समझना पड़ता है और यह एक intermediate-level task है
      Guarded Horn Clauses और उनसे निकली भाषाएँ ऐसी बातों को formalize करने के लिए विकसित की गई थीं, लेकिन Prolog के बाद जापान में हुआ विकास बहुत ही दुरूह है
      Prolog का performance programmer, इस्तेमाल किए गए implementation और इस्तेमाल की जगह पर बहुत निर्भर करता है
      Lisp की तरह Prolog का इस्तेमाल भी compile time पर DSL से native machine code generate करने में किया जा सकता है
      underlying implementation कैसे काम करता है, यह समझकर उसी के अनुरूप code लिखें तो यह पर्याप्त तेज होता है
      हालांकि इसके लिए एक ही implementation में कई साल तक Prolog code लिखना पड़ेगा
      Prolog compiler optimization पर भी काफी research है, और proprietary implementations के उदाहरण भी हैं
      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 query syntax भी देता है

    • Cozodb अच्छा दिखता है, लेकिन लगभग inactive सा लगता है
      नवंबर 2024 के आसपास इसे देखते समय SQLite storage backend में कुछ आसान improvements मिल गए थे
      https://github.com/cozodb/cozo/issues/285
    • Cozodb documentation के मुताबिक कुल मिलाकर अच्छी तरह काम करता था और इसके साथ काम करना सुखद था
      मैंने इसे program static analysis में भी इस्तेमाल किया, और यह internally sorted trees और type techniques का इस्तेमाल करता है
      documentation इतनी पर्याप्त है कि blog की step-by-step explanation से तुलना की जा सके, और खासकर query optimization का काम रोचक है
      लेकिन Rust में in-memory काम न करें तो data serialization की लागत बड़ी होती है, और project को अच्छी नज़र से देखें तब भी यह शांत ही है

  • पहले Clojure के प्रशंसक कहते थे कि Datalog, SQL से बेहतर है, और यह अफसोस की बात है कि relational databases सब SQL इस्तेमाल करते हैं
    उन्होंने ऐसा क्यों सोचा, इस पर मैं पर्याप्त गहराई से नहीं जा पाया था

    • मूल रूप से Datalog, SQL की तुलना में कहीं कम verbose है, views को अलग करने की लागत बहुत कम है, और transitive closure को जबरदस्त ढंग से support करता है
      http://canonical.org/~kragen/binary-relations एक साधारण non-recursive query से शुरू हुआ था, लेकिन SQL translation पहले ही अपराध जैसा है, और ठीक से अलग किया गया SQL solution तो फांसी लायक है
      हाल में ANSI SQL में recursion feature जोड़ा गया है, इसलिए यह अब पूरी तरह असंभव नहीं रहा, लेकिन इसके तीन बड़े नुकसान हैं
      पहला, गलती से SQL को Turing complete बना दिया गया, जबकि Datalog queries के terminate होने की guarantee होती है
      दूसरा, यह अब भी इस्तेमाल में बेहद भद्दा/भारी है
      तीसरा, पहले कारण की वजह से अक्सर इसे पूरी तरह implement नहीं किया जाता, इसलिए भरोसे से इस्तेमाल करना मुश्किल है
    • Clojure/Datomic dialect समझना मुश्किल है, लेकिन बड़ी दिशा से मैं सहमत हूं
      अगर online एक friendly notebook environment में Datalog आज़माना हो, तो मैं Percival recommend करता हूं
      https://percival.ink/
      Datalog implementations में “ANSI SQL” जैसा कोई standard नहीं है, लेकिन core ideas सीख लेने पर दूसरे Datalog भी बहुत मुश्किल नहीं लगते
      मैंने Datalog को SQLite में compile करने वाला Percival fork भी शुरू किया है, इसलिए अगर देखना हो कि दोनों वही चीज़ कैसे express करते हैं, तो इसे देख सकते हैं
      https://percival.jake.tl/
      aggregation और ज़्यादा advanced joins अभी अधूरे हैं, लेकिन basic form अच्छी तरह काम करता है
      Logica, Google के researcher द्वारा बनाया गया कहीं ज़्यादा serious और polished Datalog→SQL compiler है, जो BigTable, DuckDB और कुछ SQL dialects में compile करता है
      https://logica.dev/
      Datalog जिस क्षेत्र में कम-से-कम एक order of magnitude आसान हो जाता है, वह recursive queries/rules हैं
      SQL में भी यह संभव है, लेकिन यह straw से Play-Doh पीने जैसा लगता है
      Frank के Materialize.com में पुराने ANSI SQL recursion तरीके से काफी बेहतर “WITH MUTUALLY RECURSIVE” SQL form है, और Notion में इसे page load queries और data synchronization के लिए evaluate किया जा रहा है
      https://materialize.com/blog/recursion-in-materialize/
      Feldera में भी recursive views के लिए मिलता-जुलता form है
      https://www.feldera.com/blog/recursive-sql-queries-in-feldera
      Feldera मुझे इसलिए पसंद है कि हर “rule” या sub-view को एक ही विशाल statement में डालने के बजाय अलग statement बनाया जा सकता है
      testing के दौरान जो मुख्य कमी दिखी, वह यह थी कि Feldera के SQL dialect में Apache Calcite से विरासत में मिली काफी constraints हैं, और Materialize SQL dialect PostgreSQL compatibility से बहुत मेहनत से मेल बैठाने की कोशिश करता है

  • नया McSharry article है, बढ़िया
    आखिरी बार जब मैंने देखा था, VMWare differential datalog से दूर जाता लग रहा था

    • Differential Datalog team ने Feldera शुरू किया है
      https://www.feldera.com/
      लगता है उन्होंने differential Datalog से differential SQL की ओर shift किया है, शायद इसलिए कि उन्हें एहसास हुआ कि Datalog बेचना वाकई मुश्किल है