สร้างเอนจิน Datalog แบบโต้ตอบได้ด้วย Rust

 (github.com/frankmcsherry)
1 คะแนน โดย GN⁺ 2025-06-16 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • การทดลอง datatoad ซึ่งเป็น เชลล์ Datalog แบบโต้ตอบได้ ที่พัฒนาด้วย Rust เริ่มต้นขึ้นจากข้อจำกัดด้านการใช้งานและประสิทธิภาพของเครื่องมือ Datalog ที่ปรากฏในเวิร์กช็อปด้าน logic programming
  • datatoad ตั้งเป้าสถาปัตยกรรมที่สามารถเพิ่มกฎได้ระหว่างรันและอนุมานข้อเท็จจริงใหม่ต่อเนื่อง โดยใช้การจัดเก็บแบบ columnar และ ชั้น LSM เพื่อลดต้นทุนการจัดการข้อมูลซ้ำในชุดข้อเท็จจริง
  • การประเมินกฎแปลงส่วน body ของ Datalog ให้เป็นปัญหา join แล้วประมวลผล และแยกการประเมินทั้งชุดกับ การประเมินแบบเพิ่มพูน ตามสถานะ stable เพื่อหลีกเลี่ยงการ join แบบ stable-stable ที่คำนวณไปแล้ว
  • ในการทดลองกับชุดข้อมูล Graspan การวิเคราะห์ aliasing ลดลงจาก 736.34 วินาที·50.13GB เหลือ 119.34 วินาที·5.32GB ได้เพียงด้วยการเขียนกฎใหม่ด้วยมือและเพิ่มความสัมพันธ์กลาง
  • งานต่อจากนี้ครอบคลุมการปรับเหมาะแผน join ด้วย e-graph, layered trie, การแทนข้อมูลแบบไบต์ความกว้างคงที่, disk spill, การประเมินแบบกระจาย, streaming join และ demand transform

ปัญหาที่ datatoad ต้องการแก้

  • ในเวิร์กช็อป logic programming ช่วงสุดสัปดาห์ Memorial Day ความไม่สะดวกของเครื่องมือ Datalog สำหรับการวิเคราะห์โปรแกรมปรากฏชัด จึงเป็นจุดเริ่มต้นของความพยายามสร้าง Datalog implementation ที่ เรียบง่าย ใช้งานได้จริง และเร็ว
  • สิ่งที่จะสร้างไม่ใช่ตัวรันตัวอย่างแบบคงที่ แต่เป็นเชลล์ Datalog แบบโต้ตอบได้
    • สามารถโหลดข้อเท็จจริงจำนวนมากได้
    • สามารถเพิ่มกฎใหม่ได้ระหว่างรัน
    • นำผลของกฎที่เพิ่มเข้ามาไปสะท้อนกับสถานะเดิมต่อเนื่อง
  • สามารถติดตามโค้ดได้ใน datatoad repository
  • datafrog เดิมมีอัลกอริทึมแกนหลักของ Datalog engine อยู่แล้ว แต่ผู้ใช้ต้องเดินสายประกอบเอง จึงนำแนวคิดเดียวกันมาจัดใหม่ใน datatoad ให้อยู่ในรูปแบบที่ใช้งานง่ายกว่า
  • ในตัวอย่าง nullability ของกราฟ dataflow httpd นั้น datatoad ใช้เวลา 8.3 วินาทีกับข้อมูล Vec<String> และคิวรีที่ยังไม่คอมไพล์ ซึ่งช้ากว่าตัวอย่าง datafrog ที่ใช้ข้อมูล (u32, u32) และใช้เวลาราว 2 วินาทีประมาณ 4 เท่า
  • สำหรับปัญหา reachability นั้นให้จำนวนเอาต์พุตทูเพิลเท่ากับ implementation ของ datafrog แต่ยังไม่ถือว่าผ่านการตรวจสอบความถูกต้องทั่วไปอย่างสมบูรณ์

โมเดล Datalog และโครงสร้างเชลล์

  • Datalog เป็นภาษาที่เมื่อเขียนกฎตรรกะแบบง่าย ๆ แล้ว จะอนุมานข้อเท็จจริงทั้งหมดที่เข้าถึงได้จากกฎเหล่านั้น
  • กฎประกอบด้วย head และ body
    • ตัวอย่าง: tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c).
    • tri, edge คือความสัมพันธ์ และ a, b, c คือตัวแปร
    • ตัวแปรที่ปรากฏใน head ต้องมีอยู่ใน body ด้วย
  • ข้อเท็จจริงถูกจัดการเป็นกฎที่มี body ว่าง
    • ตัวอย่าง: edge(1, 2) :- .
    • สามารถใช้หลาย head เพื่อเขียนหลายข้อเท็จจริงพร้อมกันได้
  • ด้วยคุณสมบัติ monotonicity ของ Datalog ต่อให้เพิ่มกฎหรือข้อเท็จจริง ชุดข้อเท็จจริงที่เป็นจริงก็จะไม่ลดลง และเมื่อใช้ชุดกฎอินพุตเดียวกันก็จะได้ผลลัพธ์เดียวกันโดยไม่ขึ้นกับลำดับของกฎ
  • การแทนใน Rust มี 3 โครงสร้างหลักคือ Rule, Atom, Term
    • Rule { head: Vec<Atom>, body: Vec<Atom> }
    • Atom { name: String, terms: Vec<Term> }
    • Term::Var(String) หรือ Term::Lit(String)
  • การเก็บ literal ใช้ Vec<u8> แทน String
    • คุณสมบัติที่ต้องการคือความเท่ากันของ literal และลำดับการเรียงใด ๆ ก็ได้
    • ว่าไบต์เหล่านั้นจะมีความหมายเป็น String, (u32, u32) หรืออย่างอื่น เปิดให้ผู้ใช้กำหนดเอง
  • สถานะของ interpreter เก็บทั้งกฎและข้อเท็จจริงไว้ด้วยกัน
    • rules: Vec<Rule>
    • facts: facts::Facts
  • เมื่อเชลล์พาร์สแต่ละบรรทัดอินพุตเป็น Datalog แล้ว จะเรียก State::extend และ State::update และใช้คำสั่ง .list เพื่อพิมพ์ชื่อแต่ละความสัมพันธ์กับจำนวนข้อเท็จจริง

การพาร์สและการเก็บข้อเท็จจริง

  • parser อยู่ใน parse.rs และใช้รูปแบบที่นำมาจากไวยากรณ์ของ Soufflé
  • ตัวแปรขึ้นต้นด้วย ?
  • โทเคนจำกัดอยู่ที่ ., ,, (, ), :-, ? ส่วนข้อความที่เหลือจะถูกจัดเป็นชื่อ atom หรือ term
  • tokenizer จะลบช่องว่างและแทน :- ด้วย ← เพื่อสแกนเหมือนเป็นสัญลักษณ์เดี่ยว
  • การพาร์สกฎใช้วิธีอ่าน head atom ไปจนถึง turnstile และอ่าน body atom ไปจนถึง period
    • atom ประกอบด้วยชื่อ วงเล็บซ้าย รายการ term และวงเล็บขวา
    • term ที่มี ? จะเป็นตัวแปร ถ้าไม่มีจะเป็น literal
  • กฎที่ไม่ถูกต้องจะคืนค่า None และตอนนี้ยังไม่บอกอย่างละเอียดว่าส่วนใดผิด
  • หากจะเพิ่มกฎปฏิเสธ ต้องมีโทเคน Exclamation แต่ยังไม่รองรับ

วงจรชีวิตของชุดข้อเท็จจริง

  • การเก็บแบบ Vec<Vec<String>> อย่างง่ายมีการจัดสรรหน่วยความจำซ้อนกัน จึง ไม่เป็นมิตรต่อการจัดการหน่วยความจำ
  • datatoad ใช้ columnar เพื่อแปลงชนิดข้อมูล Rust ให้เป็นเลย์เอาต์แบบแบนด้วยการจัดสรรเชิงเส้นจำนวนน้อย
    • เก็บไบต์ของสตริง ขอบเขตของสตริง และขอบเขตของข้อเท็จจริงไว้ในอาร์เรย์แยกกัน
  • FactContainer ห่อรายการข้อเท็จจริงที่ถูกจัดเรียงและลบข้อมูลซ้ำแล้ว โดยใช้ wrapper type เพื่อสื่อ invariant ว่าถูกจัดเรียงและไม่ซ้ำ
  • เนื่องจากคอนเทนเนอร์แบบ columnar แทบจะเป็น append-only จึงไม่เหมาะกับการแก้ไขระหว่างทาง และการเพิ่มข้อเท็จจริงใหม่จึงใช้รูปแบบ log-structured merge-tree (LSM)
    • FactLSM { layers: Vec<FactContainer> }
    • จัดการให้ขนาดของแต่ละชั้นโตแบบเรขาคณิต
    • รวมชั้นที่มีขนาดต่างกันไม่เกิน 2 เท่าเพื่อคงสถานะเรียงลำดับและลบซ้ำ
  • FactBuilder มีทั้งพื้นที่ active ที่ยังไม่เรียงและอาจซ้ำ และ layers ที่เรียงและลบซ้ำแล้ว
  • ข้อเท็จจริงของแต่ละความสัมพันธ์จะเคลื่อนผ่าน 3 ระยะ
    • to_add: ข้อเท็จจริงที่เพิ่งเข้ามาใหม่แต่ยังไม่ยืนยันว่า novel หรือไม่
    • recent: ข้อเท็จจริงที่ distinct แล้วแต่ยังต้องประมวลผล
    • stable: ข้อเท็จจริงที่ distinct และประมวลผลครบแล้ว
  • FactSet::advance จะย้าย recent ไปยัง stable และลบข้อเท็จจริงใน to_add ที่มีอยู่ใน stable แล้ว เพื่อสร้าง recent ชุดใหม่

การประเมินกฎคือปัญหา join

  • ส่วน body ของกฎ Datalog สามารถมองเป็น equi-join ในฐานข้อมูลเชิงสัมพันธ์ได้
  • ตัวอย่างกฎสามเหลี่ยมมีดังนี้
    • tri(?a, ?b, ?c) :- edge(?a, ?b), edge(?b, ?c), edge(?a, ?c).
  • หากไล่ enumerates การกำหนดค่าตัวแปรทั้งหมดโดยตรง แม้จะเป็นจำนวนจำกัดก็ยังมากเกินไป จึงใช้การเรียงตามคอลัมน์คีย์ของตัวแปรร่วมแล้วทำการ merge
  • implementation ลดรูป body จากขวาไปซ้าย
    • join ความสัมพันธ์สองตัวสุดท้ายเพื่อสร้างความสัมพันธ์กลาง แล้วจึง join กับความสัมพันธ์ทางซ้ายอีกครั้ง
    • ถ้า body atom มีเพียงตัวเดียว ก็แค่แปลงรูปไปเป็นรูปของ head
  • JoinPlan เก็บข้อมูลดังนี้
    • bodys สำหรับจัดเรียงใหม่และกรอง body atom ให้เหมาะกับการ join
    • joins ที่เก็บ key arity และ output projection ของแต่ละ join กลาง
    • heads ที่ระบุตำแหน่งพิกัดหรือลิเทอรัลที่จะใส่ใน head atom
    • arity ของ join สุดท้ายที่ใช้สร้าง head
  • ตอนนี้แผนที่ใช้เป็นเพียง right-linear join plan แบบง่าย
  • ตอนสร้าง JoinPlan จะใช้ตำแหน่งปรากฏซ้ายสุดและขวาสุดของตัวแปรแต่ละตัวเพื่อตัดสินว่าต้องเก็บค่าตัวแปรใดไว้ถึงเมื่อไร และแบ่งคอลัมน์ของ body atom ออกเป็นคอลัมน์ dead, key และ value
  • ฟังก์ชันแกนหลักคือ implement_plan(rule, plan, pos, stable, facts)
    • เมื่อมีการเพิ่มกฎใหม่ จะเริ่มจากข้อเท็จจริงทั้งหมดด้วย stable = true
    • เมื่อวนใช้กฎเดิมซ้ำ จะคำนวณเฉพาะสิ่งที่อนุมานใหม่ด้วย stable = false

incremental join และ merge join

  • join เป็นการดำเนินการแบบ bilinear จึงแยกได้ดังนี้
    • (A + a) ⋈ (B + b) = A ⋈ B + A ⋈ b + a ⋈ B + a ⋈ b
  • A ⋈ B ที่สร้างจาก stable ทั้งคู่แล้ว ไม่จำเป็นต้องคำนวณซ้ำ
  • ถ้าต้องการเฉพาะอนุพันธ์ใหม่ ก็ทำเพียงสาม join นี้
    • A ⋈ b
    • a ⋈ B
    • a ⋈ b
  • join_with จะรวมหรือตัด stable-stable join ออกตามแฟลก stable
  • join จริงเป็น merge join ที่ไล่อ่านอินพุตที่เรียงลำดับแล้วสองชุดตามลำดับ
    • ถ้าคีย์เท่ากัน จะเรียก action กับทุกคู่ผสมของคีย์นั้น
    • ถ้าคีย์ไม่เท่ากัน จะใช้ gallop กระโดดข้ามไปยังจุดที่มีโอกาสแมตช์ถัดไปอย่างรวดเร็ว
  • gallop เป็นแนวคิดที่นำมาจากฝั่ง EmptyHeaded โดยจะเดินหน้าแบบยกกำลังตราบใดที่เงื่อนไขเชิงโมโนโทนิกยังเป็นจริง แล้วค่อยบีบช่วงด้วยวิธีแบบไบนารี

การทดลองวิเคราะห์ Nullability

  • ข้อมูลทดลองมาจากโครงการ Graspan และยังมีสำเนาอยู่ใน Google Drive
  • อินพุตของการวิเคราะห์ dataflow มีสอง relation คือ e และ n
    • n(?a, ?b): ค่า ?a อาจถูกเขียนลงที่ตำแหน่ง ?b
    • e(?a, ?b): ค่าที่ตำแหน่งหนึ่ง ?a อาจเคลื่อนไปยังอีกตำแหน่ง ?b
  • กฎ reachability มีดังนี้
    • n(?a, ?c) :- n(?a, ?b), e(?b, ?c) .
  • ในอินพุต httpd ค่าเริ่มต้น .list แสดงดังนี้
    • e: 9,905,624
    • n: 138,331
  • ถ้ารันกฎนี้ตรงๆ จะใช้เวลาประมาณ 15 วินาที และ n จะเพิ่มเป็น 9,393,283 รายการ
  • สาเหตุหนึ่งที่ช้าคือ relation ชั่วคราว .temp-0-0-in ซึ่งจัดเรียง n ใหม่ให้ตรงกับ join key โตขึ้นถึง 9,393,283 รายการ
  • หากผู้ใช้เขียนกฎใหม่ ประสิทธิภาพจะดีขึ้น
    • m(?loc, ?val) :- n(?val, ?loc) .
    • m(?loc, ?val) :- m(?mid, ?val), e(?mid, ?loc) .
  • กับอินพุต httpd ชุดเดิม หลังเขียนใหม่ กฎข้อที่สองรันได้ราว 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
  • ตัวเลขของ Graspan สำหรับ lnx_kernel มีเครื่องหมาย * กำกับอยู่ โดยในงานวิจัยรายงานเวลารวมทั้งหมด และเพราะมีการชนกันของตัวระบุอินพุต จึงดูเป็นการรันแบบเดียวกันตรงๆ ได้ยาก
  • หากจะเทียบกับเครื่องมือที่ใช้ในงานจริง Soufflé อาจเป็นเป้าหมายที่เหมาะสมกว่า

การวิเคราะห์ Aliasing และการปรับให้เหมาะด้วยมือ

  • การวิเคราะห์ชุดที่สองคือการวิเคราะห์ aliasing ของ Zheng และ Rugina ที่ Graspan นำมาใช้
  • relation อินพุตมีสองชนิด
    • A(?val, ?loc): ?loc <- ?val
    • D(?val, ?loc): ?loc ถูกใช้งานในรูป *?val
  • เป้าหมายคือหาทั้ง memory alias และ value alias
    • memory alias: นิพจน์ lvalue สองตัวอาจชี้ไปยังตำแหน่งหน่วยความจำเดียวกัน
    • value alias: นิพจน์สองตัวอาจประเมินได้เป็นค่าพอยน์เตอร์เดียวกัน
  • ในสัญลักษณ์ของงานวิจัยจะมี ^T, ^?, ^*
    • ^T: transpose ของ relation
    • ^?: เทอมแบบเลือกได้
    • ^*: ทำซ้ำ 0 ครั้งขึ้นไป
  • ใน Datalog นั้น ^? แทนได้ด้วยการแยกเป็นสองกฎ และ ^* จัดการโดยใส่ relation identity อย่างชัดเจน
  • การรันกฎเริ่มต้นใช้เวลานาน
    • หลังป้อนกฎเริ่มต้น identity สองข้อสุดท้าย ใช้เวลา 686.57 วินาที และ 736.34 วินาที
    • โปรเซสใช้หน่วยความจำ 50.13GB
    • V: 361,947,256
    • M: 92,806,768
    • F: 2,669,647
  • มีการใช้ relation transpose -V, -M, -a, -d อย่างชัดเจนเพื่อตัด relation ชั่วคราว -in ออก
    • รวม 815.92 วินาที หรือราว 13.6 นาที
    • หน่วยความจำ 31.96GB
  • แนวทางของ Zheng และ Rugina เป็นแบบ demand-driven และในทางปฏิบัติต้องใช้เพียง M จึง inline V เข้าไปใน M
    • ไม่ต้องสร้าง -V จำนวน 361,947,256 รายการ
    • หน่วยความจำลดลงเหลือ 18.96GB
  • ตั้งชื่อชิ้น join ที่เกิดซ้ำว่า Fd เพื่อใช้ซ้ำ และหลังจากนั้นคำนวณ Fd โดยตรงแทน F เพื่อลดปัญหา identity ด้วย
  • รูปแบบสุดท้ายที่เพิ่ม relation กลาง MFd ให้ผลลัพธ์ดังนี้
    • เวลาในการรัน: 119.34 วินาที
    • หน่วยความจำ: 5.32GB
    • -M: 92,806,768
    • Fd: 1,858,986
    • MFd: 73,474,947
  • เพียงแค่เขียนใหม่ด้วยมือ ก็ปรับปรุงทั้งหน่วยความจำและเวลาในการรันได้เกือบ 10 เท่าเมื่อเทียบกับความพยายามครั้งแรก
  • การสร้างผลลัพธ์กลางที่มีชื่อ ทำให้สามารถประกอบ bushy-tree join plan ที่ต้องการได้โดยตรงในระดับหนึ่ง แต่ถ้าตั้งชื่อ relation ที่จริงแล้วไม่จำเป็นอย่าง V ก็จะต้องเสียต้นทุนมากเพื่อสร้างมันขึ้นมา

คิวรีแบบ Demand-driven และ magic sets

  • คิวรีแบบ demand-driven คือวิธีที่สำรวจเฉพาะส่วนที่จำเป็นต่อ fact เป้าหมายที่กำหนด
  • magic sets อาจใช้เป็นคำตอบแบบประมาณได้
    • เป็นการแปลงที่ฝัง target literal ลงไปในคิวรี
    • อาจนึกถึงการเริ่มจาก d ที่สนใจแทนทุก d แต่ถ้าใช้แบบตรงๆ อย่างง่ายอาจผิดได้
  • magic sets ไม่ใช่คำตอบที่เหมาะที่สุดเสมอไป และมีแผนจะอ่านงานที่เกี่ยวข้องเพิ่มเพื่อหาแนวทางที่อาจมีประสิทธิภาพกว่านี้
  • ลิงก์ที่เกี่ยวข้องมีดังนี้

การปรับ join plan ให้เหมาะ และ IR สำหรับ data parallel

  • เสน่ห์ของ Datalog ไม่ได้อยู่ที่ Horn clause เองเท่านั้น แต่อยู่ที่มันเปิดเผยปัญหาแกนหลักของการคำนวณแบบ data parallel อย่าง data rendezvous ได้อย่างบริสุทธิ์
  • กฎ h(x, y, z) :- b1(x, y), b2(y, z) . มองได้ว่าเป็นปัญหาการรวบรวม x และ z ที่เกี่ยวข้องมาไว้ที่เดียวกันสำหรับแต่ละ y
  • การทำงานพื้นฐานของการคำนวณแบบ data parallel คือการรวบรวมเรกคอร์ดตามคีย์แล้วส่งต่อให้ตรรกะของผู้ใช้ โดย join เป็นการแสดงการกำหนดเส้นทางแบบเลือกเฉพาะกรณีชนิดหนึ่งในนั้น
  • IR แบบง่ายใช้ opcode ต่อไปนี้
    • Var(String): คอลเลกชันที่มีชื่อ
    • Map(Action): filter, permutation, projection
    • Key(usize): ทำเครื่องหมายว่ากี่คอลัมน์ด้านหน้าเป็นคีย์
    • Mul(usize): รวมหลายคอลเลกชันที่มีความยาวคีย์เท่ากัน
  • ต่อมา Map และ Key ถูกรวมกันเป็น Action.key_arity
  • Action เก็บ literal filter, variable equality filter, projection และ key arity
  • จุดเริ่มต้นที่ง่ายที่สุดคือ cross join body atom ทั้งหมดก่อน แล้วค่อยวาง filter และ projection ตามแต่ละ head ซึ่งแม้จะได้คำตอบที่ถูกต้อง แต่ประสิทธิภาพจะแย่มาก

การเพิ่มประสิทธิภาพบนพื้นฐาน e-graph

  • การเพิ่มประสิทธิภาพใช้ e-graph และ equality saturation
  • ใช้ egg webpage, บทความก่อนหน้า และ egg เป็นแหล่งอ้างอิง
  • term graph แทนด้วยแมปของ ENode<T> ที่มี Id กำกับ และใช้โหนดเดียวกันร่วมกันเพื่อแทนโปรแกรมให้กระชับขึ้น
  • กฎ e-graph ที่นำมาใช้มีสามแบบ
    • MulPermute: ทำให้การเรียงลำดับอินพุตของ Mul(k) เป็นสมมูลกัน
    • MulPartition: แบ่ง Mul(k) ได้หลายแบบและทำให้เป็นสมมูลกัน
    • MapPushdown: ดัน Map ลงไปใต้ Mul(2) เพื่อสร้างรูปแบบ join ที่มีคีย์
  • กฎตัวอย่างมีดังนี้
    • head(?a, ?b) :- a(?x, ?a), b(?y, ?x), b(?y, ?z), a(?z, ?b) .
  • หลัง equality saturation จะกำหนดต้นทุนในขั้น extraction
    • ต้นทุนของ Map คือจำนวนคอลัมน์เอาต์พุต
    • ต้นทุนของ Mul คือจำนวนคอลัมน์คีย์บวกกับผลรวมของจำนวนคอลัมน์ที่ไม่ใช่คีย์ของอินพุต
    • ต้นทุนของ Var คือ 0
    • ถ้าเสมอกัน จะลดจำนวน Map ก่อน แล้วจึงลดจำนวน Mul
  • ในตัวอย่าง แผนที่ถูกเลือกถูกพบใน wave two ซึ่งมีคอลัมน์ที่ไม่สัมพันธ์กันได้มากสุดสองคอลัมน์
    • map สำหรับอินพุต a, b
    • join หนึ่งครั้ง
    • projection ขั้นกลาง
    • join กับตัวเอง
    • projection สุดท้าย
  • การสำรวจแผนนี้ใช้เวลาราว 40ms แม้ใน release build และเวลาส่วนใหญ่ถูกใช้ไปกับ equivalence saturation

อัปเดตการรันแผนเพิ่มประสิทธิภาพ

  • ในอัปเดต 2025-06-29 ได้มีการทำให้การรันแผนที่เพิ่มประสิทธิภาพแล้วใช้งานได้จริง
  • แผนออกมาเป็น Vec<ENode<Op>> แต่ในการรันจริงจะไม่ได้รันแต่ละโหนดอย่างอิสระ
  • วิธีรันที่ตั้งใจไว้เป็นดังนี้
    • สำหรับแต่ละ Var จะใช้ Map หลายตัวที่พึ่งพามันภายในการสแกนคอลเลกชันภายนอกเพียงครั้งเดียว
    • สำหรับแต่ละ Mul จะใช้ Map หลายตัวที่พึ่งพามันภายในการสแกน join เพียงครั้งเดียว
  • Op::Map(action) ไม่ใช่โอเปอเรชันที่ถูกทำโดยตรง แต่เป็นงานที่ถูกคิวไว้ให้โอเปอเรชันที่มันพึ่งพา
  • เพื่อรองรับสิ่งนี้จึงเพิ่ม TempAction
    • literal filter
    • ตัวกรองความเท่ากันของตัวแปร
    • projection ที่เก็บได้ทั้งการอ้างอิงคอลัมน์หรือสตริงลิเทอรัล
  • ขั้นเตรียม execution plan แยก body และ head แล้วรวบรวม Map action ตามโหนดอินพุต
  • การจัดการชื่อในระหว่างรัน Var แบ่งเป็นสามกรณี
    • การสร้าง head จะเขียนลงในชื่อ relation ของ head
    • การแปลงแบบ identity จะใช้ชื่ออินพุตเดิมซ้ำ
    • การแปลงที่ไม่ trivial จะเก็บลงชื่อชั่วคราวแบบ .temp-*
  • การรัน Mul(2) จะตรวจสอบ key arity และชื่อของอินพุตทั้งสอง แล้วเรียก join_with เพื่อสะสมผลลัพธ์ลงใน builder หลายตัว
  • ในตัวอย่าง aliasing ที่ซับซ้อน การรันแผนที่เพิ่มประสิทธิภาพแล้วใช้เวลา 114.28 วินาที เร็วกว่าก่อนหน้าที่อยู่ระดับ 119 วินาทีราว 5 วินาที แต่ยังไม่ชัดเจนว่าเพราะเหตุใด
  • การเพิ่มประสิทธิภาพแบบ multi-rule ยังไม่ได้ทำ และอาจต้องกลับไปคิดใหม่แม้แต่แนวทางของแผนเอง

การเพิ่มประสิทธิภาพการแทน facts

  • แม้จะลดจาก 50GB เหลือ 5GB ได้แล้ว แต่ก็ดูเหมือนว่ายังใช้หน่วยความจำมากกว่าที่จำเป็นราว 10 เท่า
  • largest layer ของ relation ขนาดใหญ่ -M เก็บ facts 57,289,225 รายการ และใช้ 2,098,253,766 ไบต์โดยประมาณ
    • fact boundaries: 458,313,800 ไบต์
    • term boundaries: 916,627,600 ไบต์
    • ข้อมูลไบต์จริง: 723,312,366 ไบต์
  • การเพิ่มประสิทธิภาพอย่างแรกอาศัยข้อเท็จจริงที่ว่า arity คงที่
    • หากทุก fact มี 2 คอลัมน์ fact boundaries สามารถแทนได้ด้วยแค่ stride และ length
    • จึงแทบจะตัดข้อมูลขอบเขตขนาด 458MB นี้ทิ้งได้
  • การเพิ่มประสิทธิภาพอย่างที่สองคือทำให้ความยาวของ term เท่ากัน
    • หากแปลงตัวเลขเป็นสตริงความกว้างคงที่ 7 หลัก term boundaries ก็สามารถแทนด้วย stride และ length ได้
    • แต่จำนวนไบต์จริงอาจเพิ่มขึ้นแทน
  • การเพิ่มประสิทธิภาพอย่างที่สามคือแทนตัวเลขด้วย binary แทนข้อความ
    • ตัวเลข 7 หลักเก็บใน u32 ขนาด 4 ไบต์ได้
    • และยังเก็บใน 3 ไบต์ได้ด้วย จึงเหลือ 57,289,225 × 2 × 3 = 343,735,350 ไบต์
    • ลดจากราว 2GB เหลือราว 350MB หรือประมาณ 6.10 เท่า
  • หากบีบอัดการซ้ำของ term ตัวแรก ก็ลดลงได้อีก
    • แม้มี facts 57,289,225 รายการ แต่ first term ที่ไม่ซ้ำมีเพียง 1,147,612 รายการ
    • หากเก็บเป็นรูป (Term, [Term]) แทน (Term, Term) largest layer จะลดเหลือราว 184,491,407 ไบต์
    • เทียบกับ 2GB แรกเริ่มแล้วลดลงราว 11.37 เท่า
  • ในอัปเดต 2025-07-02 ได้ใช้การเพิ่มประสิทธิภาพชุดแรกแล้ว
    • largest batch มีขนาดเป็น 343,735,382 ไบต์ ซึ่งคือค่าเชิงทฤษฎี 343,735,350 ไบต์บวกเพิ่ม 32 ไบต์
    • เวลารันลดจากราว 115 วินาทีเหลือราว 95 วินาที หรือดีขึ้นประมาณ 20%

การแทนแบบ layered trie

  • ในอัปเดต 2025-07-20 layered trie ใช้งานได้แล้ว
  • มีการเปรียบเทียบระหว่างการแทนแบบ row-oriented กับแบบ column-oriented layered trie
    • toad-row
    • toad-col
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
toad-row 3.88s 11.30s 25.67s
toad-col 3.47s 11.94s 23.09s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
graspan 8.4h 6.0h* 1.7h*
toad-row 28.21s 28.25s 7.62s
toad-col 19.39s 21.96s 9.48s
datafrog UNK UNK UNK
  • layered trie เป็นวิธีลดการซ้ำของคอลัมน์ต้น ๆ ในการแทนแบบ row ที่เรียงลำดับแล้ว
  • แต่ละคอลัมน์คือรายการของรายการค่า
    • แต่ละรายการคือชุดค่าที่ไม่ซ้ำและเรียงลำดับแล้ว ซึ่งสอดคล้องกับ prefix ของคอลัมน์ก่อนหน้า
    • จำนวนรายการของคอลัมน์หนึ่งจะเท่ากับจำนวนไอเท็มรวมทั้งหมดของคอลัมน์ก่อนหน้า
  • แม้จะมองเป็นต้นไม้ได้ แต่การติดตั้งใช้งานจริงยังคงเก็บเป็นคอลัมน์
  • ข้อดีคือสามารถทำการค้นหา, join, ผลต่างเซต, และ merge ได้ในระดับ prefix
  • ในกรณีที่แทบไม่มีค่าที่ไม่ซ้ำ และการมองทั้งแถวพร้อมกันเหมาะกว่า วิธีแบบ row-oriented อาจได้เปรียบกว่า
  • ได้เพิ่ม FactContainer trait เป็นนามธรรมร่วม
    • form
    • len
    • apply
    • join
    • except
    • merge
  • apply ติดตาม range ของแต่ละ layer ด้วย stack แบบชัดเจนแทนการเรียกซ้ำ แล้วสร้างแถวเพื่อส่งให้ action
  • align เป็นเฮลเปอร์ร่วมสำหรับจัด prefix ของ layered trie สองตัวให้ตรงกัน
    • Ordering::Less: ช่วงที่มีเฉพาะใน self
    • Ordering::Greater: ช่วงที่มีเฉพาะใน other
    • Ordering::Equal: prefix ความยาว arity ที่มีร่วมกันทั้งสองฝั่ง
  • join, except, merge ถูกสร้างบน align ทั้งหมด
    • join จะคลี่ extension ที่เหลือบน prefix ร่วมแล้วทำ cross join
    • except จะ graft ช่วงที่มีเฉพาะใน self ด้วย TrieBuilder
    • merge จะ graft ช่วงแบบ self-only, other-only และ equal อย่างเหมาะสมอย่างละหนึ่งครั้ง

การเพิ่มประสิทธิภาพแบบความกว้างคงที่และประสิทธิภาพ

  • เมื่ออัปเกรดเป็น [u8; 4] แบบความกว้างคงที่ได้ ประสิทธิภาพการเปรียบเทียบจะดีขึ้นมาก
  • layered trie สามารถใช้การเพิ่มประสิทธิภาพแบบความกว้างคงที่แยกตามคอลัมน์ได้ จึงมีโอกาสได้เปรียบกว่า row ในระยะยาว
  • กับ except และ merge สามารถใช้ upgrade·downgrade ได้ง่าย แต่การนำไปใช้กับ join ยากกว่าเพราะปัญหาเรื่องชนิดข้อมูลของ Rust
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
toad-row 3.88s 11.30s 25.67s
^-- +opt 3.11s 9.49s 19.83s
toad-col 3.47s 11.94s 23.09s
^-- +opt 2.55s 9.13s 15.95s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
graspan 8.4h 6.0h* 1.7h*
toad-row 28.21s 28.25s 7.62s
^-- +opt 23.31s 23.08s 6.73s
toad-col 19.39s 21.96s 9.48s
^-- +opt 14.26s 16.45s 8.33s
datafrog UNK UNK UNK
  • ขณะนี้เวลาราว 2/3 ถูกใช้ไปใต้ join
  • มองว่ายังมีช่องให้ปรับแต่ง join ได้เพิ่มอีกราว 2 เท่าเป็นอย่างน้อย
  • การลองเพียงสลับลำดับ inner loop ไม่ได้ให้การปรับปรุงที่วัดผลได้

ปรับให้เฉพาะทางถึงระดับโค้ดที่คอมไพล์แล้ว

  • หากตรวจจับได้ว่า term มีความยาวเท่ากันและ fact มี arity เท่ากัน ก็สามารถมอง Vec<u8> เป็น Vec<[[u8; B]; T]> ได้
  • รูปแบบนี้ทำให้ Rust เข้าใจรูปร่างข้อมูลได้ดีขึ้น ลดต้นทุนการตรวจ bounds·length และทำให้การเปรียบเทียบถูกลงมากเป็นพิเศษ
  • การเปรียบเทียบถูกใช้ในหลายจุดของ datatoad
    • การ sort·dedup ของ fact batch
    • การ merge batch
    • การ merge คีย์ของ join
    • การกรองโดยเปรียบเทียบ fact ใหม่กับ fact เดิมที่มีอยู่
  • ประสิทธิภาพอ้างอิงเป็นดังนี้
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
datatoad 7.44s 17.26s 42.25s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
graspan 8.4h 6.0h* 1.7h*
datatoad 101.24s 96.36s 20.20s
datafrog UNK UNK UNK
  • การปรับแต่ง sort ถูกทดลองด้วยวิธี unsafe transmute Vec<u8> เป็น Vec<[u8; 8]> แล้วทำ 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 ถูกทำแบบเรียบง่าย โดยนำอินพุตทั้งสองมาต่อกันแล้ว sort·dedup
dataflow httpd psql lnx_kernel
dt-orig 7.44s 17.26s 42.25s
dt-sort 4.99s 13.55s 32.15s
dt-both 3.71s 11.23s 23.58s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
dt-orig 101.24s 96.36s 20.20s
dt-sort 52.99s 53.19s 11.20s
dt-both 31.32s 30.08s 8.56s
datafrog UNK UNK UNK
  • ยังไปไม่ถึงประสิทธิภาพแบบคอมไพล์แล้วของ datafrog
  • ต้นทุนการเปรียบเทียบที่เหลือยังอยู่ใน join และ antijoin ด้วย และมีแผนจะกลับมาดูโอกาสปรับแต่งแบบเดียวกันอีกครั้งระหว่างย้ายไปใช้โครงสร้างแบบ trie
  • กำลังหาวิธีตัด unsafe ออก และสรุปเพิ่มเติมว่าควรหลีกเลี่ยงโค้ด unsafe

งานที่ยังเหลือ

  • spill ลงดิสก์

    • สตอเรจแบบ columnar ประกอบด้วยการจัดสรรขนาดใหญ่จำนวนน้อย
    • ตอนสร้างสามารถเขียนลงไฟล์แทนหน่วยความจำ แล้วนำกลับมาใช้ผ่าน memory map ได้

  • การประเมินผลแบบกระจาย

    • join, การกำจัดข้อมูลซ้ำ, และ distinctness check อาศัยความเท่ากันของคีย์
    • สามารถกระจายคีย์และข้อมูลที่เกี่ยวข้องไปยัง worker หลายตัวได้
    • สามารถขยายไปถึงหลายโปรเซสด้วย timely_communication

  • การประเมินกฎแบบสตรีมมิง

    • ปัจจุบัน join ใช้ binary join และ materialized output
    • หากมีอินเด็กซ์ที่ต้องการ ก็สามารถสร้างแผนที่ไม่ materialize สถานะภายในได้
    • worst-case optimal join ก็จะพูดถึงในส่วนนี้ด้วย

  • ปรับให้เฉพาะทางสำหรับ custom representation

    • มีแนวคิดในการตรวจจับ transitive closure แล้วปรับให้เฉพาะกับ strongly connected component decomposition
    • สำหรับ equivalence relation สามารถใช้โครงสร้างข้อมูล union-find ได้
    • bddbddb และ factorized databases ก็กล่าวถึงหัวข้อที่เกี่ยวข้องเช่นกัน

  • การค้นหา fact ที่เกี่ยวข้อง

    • ต้องทำความเข้าใจและนำ demand transform มาปรับใช้
    • มองว่าเป็นการแปลงที่จำเป็นสำหรับการสำรวจ Datalog แบบโต้ตอบ

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-06-16
ความคิดเห็นบน Hacker News

  • เห็นบทความนี้ขึ้นอันดับ 1 แล้วน่าสนใจดี
    ตอนนี้กำลังสร้างเกมวางแผนแบบเรียลไทม์ด้วย Differential Datalog และ Rust โดยให้ DDL จัดการตรรกะของเกม
    ส่วนใหญ่ก็เป็นข้ออ้างในการลองไอเดียใหม่ ๆ แล้วได้โกนขนจามรีกันไม่รู้จบมากกว่า
    https://github.com/vmware-archive/differential-datalog

    • ดูเหมือนเป็นเดโมเจ๋ง ๆ ที่ทำด้วย ddlog
      อนึ่ง ทีม ddlog ตอนนี้ไปก่อตั้ง Feldera แล้ว และก็น่าพิจารณาการใช้ DBSP โดยตรงจาก Rust ด้วย
      https://github.com/feldera/feldera
    • สงสัยว่าถ้าผสม repository ต้นฉบับกับ salsa ซึ่งเป็น crate ที่ขับเคลื่อน Rust analyzer จะสร้าง differential datalog แบบแฟรงเกนสไตน์ได้ไหม
      https://github.com/salsa-rs/salsa
    • อยากรู้ว่าสถานะการ implement เป็นอย่างไร และจะไปได้ไกลแค่ไหน
      ยิ่งน่าสนใจเพราะ DDLog ไม่ได้ถูกดูแลอย่างแข็งขันแล้ว

  • “ฉัน ผู้ร้ายฉาวโฉ่ ได้รับคำเชิญ โดยครึ่งหนึ่งเชื่อว่ากำลังจะไปรับการลงทัณฑ์ที่ควรได้รับมานานแล้ว” — เป็น ประโยคเปิดที่ดีที่สุด ของบล็อกเทคนิคที่อ่านมาในปีนี้
    คำแทรกของผู้เล่าเรื่องก็ยอดเยี่ยม และบทความที่ลึกทางเทคนิคแต่ยังอ่านสนุกแบบนี้หาได้ยาก
    การเดินทางเพื่อ optimize query เรื่อง alias ให้ความรู้สึกเหมือนนิยายสืบสวน และผู้อ่านก็ได้คร่ำครวญไปด้วยกันกับ การใช้หน่วยความจำ 50GB ก่อนจะโห่ร้องยินดีเมื่อลดลงเหลือ 5GB
    ทั้งโค้ดและงานเขียนยอดเยี่ยมมาก

  • เคยทำงาน port mangle datalog ไปเป็น Rust ไปบ้างเล็กน้อย
    อยู่ที่ https://github.com/google/mangle/tree/main/rust และอยู่ใน repository เดียวกับ implementation ภาษา Go
    ความคืบหน้าช้า เพราะไม่ใช่ priority สูง แถมยังมีอาการ second-system syndrome ด้วย
    Mangle Rust มุ่งไปทางการจัดการข้อมูลขนาดใดก็ได้ โดยอ่านและเขียน fact จากดิสก์ด้วย memory mapping ส่วน implementation ภาษา Go เป็นแบบ in-memory
    บทความนี้ดีตรงที่พูดถึงการ parse Datalog และยังแตะ LSM tree ด้วย แถมตามได้ง่ายกว่าเนื้อหาเกี่ยวกับ datafrog มาก
    ใน Rust มี implementation ของ Datalog จำนวนมากที่ใช้ procedural macro เช่น ascent, crepe แต่มีข้อเสียคือรับ query ตอน runtime ได้ยาก
    ถ้าใช้สำหรับ static analysis ที่ query และ program ถูกกำหนดตายตัว วิธีแบบ procedural macro อาจเหมาะกว่า

  • แม้กระแส การฟื้นคืนของ Datalog ในตอนนี้ดูเหมือนจะแผ่วลง แต่ก็ดีใจที่เห็นแฟนตัวยงแกนหลักยังคงยืนหยัดอยู่
    งานประชุม Datalog 2.0 ล่าสุดเล็กลงกว่าก่อนพอสมควร และงาน HYTRADBOI ครั้งที่สองก็มีสัดส่วน Datalog ต่ำลง
    ใน HYTRADBOI ครั้งแรก หนึ่งในสี่ของงานที่ส่งเข้ามาเกี่ยวข้องกับ Datalog
    การที่คนอื่นแชร์โปรเจกต์ Datalog ล่าสุดก็เป็นเรื่องน่าชื่นใจ
    ตอนนี้กำลังเตรียม migration ซอฟต์แวร์ขนาดใหญ่ และสร้าง data quality pipeline สำหรับฐานข้อมูล SQL legacy
    ถ้า structuring query ดี ๆ จะอ่านง่ายมาก จึงคิดว่า Datalog มีประโยชน์กว่า SQL มากในการระบุและค้นหาปัญหาคุณภาพข้อมูล

    • ถึงจะเห็นด้วยกับทิศทางใหญ่ ๆ แต่คงยากที่จะยกจำนวนผู้เข้าร่วม Datalog 2.0 ที่น้อยเป็นกรณีตัวแทนของขาลงของ Datalog
      Datalog 2.0 เป็น workshop satellite ของ LPNMR ซึ่งเป็นการประชุมวิชาการในยุโรปที่ค่อนข้างไม่เป็นที่รู้จักมากนัก และบังเอิญว่าการประชุมนั้นจัดที่ Dallas
      ตอนที่ไปเข้าร่วมเองก็รู้สึกว่างานค่อนข้างเงียบ และถึงจะส่ง paper เข้า workshop ไปด้วย ก็ไม่ค่อยเห็นคนในสาขานั้นมากนัก
      ข้อยกเว้นที่เด่นชัดคือกลุ่มจากยุโรปที่มาแนะนำตัวแก้ปัญหา Nemo
      ผมคิดว่าการที่ปีนี้ผู้เข้าร่วมน้อย สะท้อนมากกว่าว่านี่เป็น workshop satellite ของการประชุมที่ชื่อเสียงไม่ได้ใหญ่อยู่แล้ว และงานหลักก็เป็น ICLP มากกว่าจะสะท้อนว่าความสนใจต่อ implementation ของ Datalog ลดลง
      แน่นอนว่าไม่ได้พยายามโต้แย้งข้ออ้างใหญ่ที่ว่าแทบไม่เหลือความใหม่ใน implementation ของ engine Datalog แบบบริสุทธิ์แล้ว
      พื้นที่วิจัยก้าวไปไกลกว่านั้นมากแล้ว ไปสู่ปัญหาที่แปลกใหม่กว่า เช่น streaming (HydroFlow), choice (Dusa), และสิ่งที่ใกล้กับ general chase (chase engine ของ Egglog)
      โดยทั่วไปแทบไม่มีใครขัดแย้งว่า vanilla Datalog น่าเบื่อ แต่ monotone forward saturation และ Horn clause เป็น baseline ที่มั่งคั่งซึ่งเข้าใจภูมิทัศน์ด้าน performance engineering ดีแล้ว จึงเหมาะสำหรับต่อยอดทฤษฎีที่น่าสนใจกว่าอย่าง semiring หรือ Z-set

  • ถ้าสนใจส่วน state machine และ parsing ขอแนะนำ presentation เก่าของ Rob Pike เรื่อง Lexical Scanning in Go ด้วย
    https://www.youtube.com/watch?v=HxaD_trXwRE
    แม้จะเป็น Go แต่ส่วนใหญ่ก็เอาไปประยุกต์กับภาษาอื่นได้ง่าย
    ดีที่ภาษา modern อย่าง Rust, Zig, Go รองรับ Unicode/rune/grapheme แบบ native
    เมื่อเทียบกับ Java, .NET, C++ หรือภาษา scripting แล้ว ปัญหาหลายอย่างหายไปเฉย ๆ

  • โดยรวมชอบงาน Datalog ของผู้เขียน แต่ไม่อยากให้สื่อสอนสำหรับผู้เริ่มต้นสอน binary join
    พอออกนอกกรณีอุดมคติ ภายในจะรกขึ้นอย่างรวดเร็ว และ method แบบ general join ทำให้ generalize ในหัวได้ง่ายกว่ามาก
    https://en.wikipedia.org/wiki/Worst-case_optimal_join_algorithm

    • ที่เกี่ยวข้องกัน บล็อกโพสต์ก่อนหน้าของ McSherry แสดงให้เห็นว่า ภายใต้สมมติฐานว่ามีการปรับแผน query อย่างเหมาะสม binary join ก็สามารถทำเวลา execution แบบ worst-case optimal ได้
      https://github.com/frankmcsherry/blog/blob/master/posts/2025-05-29.md

  • สมัยเรียนเมื่อนานมาแล้วเคยแตะ Prolog นิดหน่อย และพอรู้คร่าว ๆ ว่าใช้ทำอะไร มีประโยชน์ตรงไหน แต่ไม่ได้เข้าใจลึกซึ้ง
    หลังจากนั้นก็ได้ยินเรื่อยมาว่า Datalog ยอดเยี่ยมมาก แต่ก็ยังจับประเด็นไม่ได้ว่า Datalog ปรับปรุงอะไรจาก Prolog กันแน่
    เมื่อกี้ลองกวาดดูหน้า Datalog ใน Wikipedia แล้ว ดูเหมือนว่า Prolog มีประสิทธิภาพค่อนข้างแย่ ส่วน Datalog ลดพลังในการแสดงออกและฟีเจอร์ลง แลกกับการปรับปรุงประสิทธิภาพอย่างมาก ทำให้รองรับชุดข้อมูลที่ใหญ่ขึ้นและการประมวลผลแบบขนานได้มากขึ้น
    ดูเหมือนจะรวมถึงการสูญเสียความเป็น Turing-complete ด้วย เลยสงสัยว่านี่คือประเด็นหลัก หรือผมเข้าใจผิดไปไกลกันแน่

    • เท่าที่รู้ Prolog ดูเหมือนเป็นแบบ declarative ที่แค่ encode ความสัมพันธ์ก็จะหาคำตอบให้ แต่ในทางปฏิบัติกลับพึ่งพา ลำดับของกฎ ค่อนข้างมาก และยังต้องมีคำสั่งกำกับเพิ่มเติมอย่าง “cut” ด้วย
      cut ไม่ได้แค่ป้องกันการคำนวณที่สูญเปล่า แต่ยังอาจมีผลต่อผลลัพธ์ด้วย
      ส่วน Datalog โดยทั่วไปมี syntax ใกล้เคียงฐานข้อมูลเชิงสัมพันธ์อีกแบบหนึ่งมากกว่า
    • Datalog เรียบง่ายกว่า ไม่ใช่ Turing-complete และเท่าที่จำได้ใช้ forward reasoning ซึ่งส่งผลต่อเนื่องไปถึงลักษณะด้านประสิทธิภาพและหน่วยความจำ
      พื้นที่ค้นหาขนาดมหึมาที่ดูเล็กน้อยใน Prolog อาจกินหน่วยความจำมากเกินไปใน Datalog จนไม่สามารถแสดงออกได้เลย
      Datalog เหมือนรถ commuter ที่ใช้เกียร์ CVT ส่วน Prolog ใกล้เคียงรถ F1
      มันไม่เชิงเป็นการปรับปรุง แต่ใกล้เคียงกับการตัดทอน Prolog บางส่วนเพื่อไม่ให้ผู้ใช้ยิงเท้าตัวเองทิ้ง และยังนำไป implement/ฝังในแอปพลิเคชันอื่นได้ง่ายกว่ามาก
      ถ้าคุ้นกับ Prolog แล้ว Datalog โดยมากจะรู้สึกอึดอัด
      ไม่มี call/3 ไม่มี term/goal expansion และโดยพื้นฐานแล้ว Datalog เหมือนถูกออกแบบโดยดึงชุดความสามารถร่วมขั้นต่ำของ Prolog มาใช้กับการค้นหาฐานข้อมูลแบบโต้ตอบ
      โค้ด Datalog ที่เร็วเขียนได้ง่าย แต่เพดานก็ต่ำกว่ามากเช่นกัน
      Prolog ก็สามารถเขียนในแบบที่เปิดให้ทำงานพร้อมกันได้ แต่เป็นงานระดับกลางที่ต้องเข้าใจ implementation
      Guarded Horn Clauses และภาษาที่ต่อยอดมาจากมันถูกพัฒนาขึ้นเพื่อทำให้ส่วนนี้เป็นรูปแบบเชิงทางการ แต่พัฒนาการฝั่งญี่ปุ่นหลังยุค Prolog นั้นเข้าใจยากมาก
      ประสิทธิภาพของ Prolog ขึ้นอยู่กับโปรแกรมเมอร์ implementation ที่ใช้ และตำแหน่งที่นำไปใช้เป็นอย่างมาก
      เช่นเดียวกับ Lisp, Prolog ก็สามารถใช้สร้าง native machine code จาก DSL ณ เวลา compile ได้
      ถ้าเข้าใจว่า implementation พื้นฐานทำงานอย่างไร และเขียนโค้ดให้เข้าทางกับมัน ก็เร็วพอได้
      แต่การจะทำแบบนั้นต้องเขียนโค้ด Prolog กับ implementation เดียวกันเป็นเวลาหลายปี
      งานวิจัยด้านการ optimize compiler ของ Prolog ก็มีมาก และมีกรณี implementation เชิง proprietary ด้วย
      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 และมี syntax สำหรับ query แบบ Datalog ให้ด้วย

    • Cozodb ดูดี แต่เหมือนแทบจะไม่ active แล้ว
      ช่วงประมาณพฤศจิกายน 2024 เคยลองดู และพบจุดที่ปรับปรุงได้ง่าย ๆ อยู่หลายอย่างใน storage backend ของ SQLite
      https://github.com/cozodb/cozo/issues/285
    • Cozodb โดยรวมทำงานได้ดีตามเอกสาร และทำงานด้วยแล้วสนุก
      เคยใช้กับการวิเคราะห์สถิตของโปรแกรมด้วย และภายในใช้ sorted tree กับเทคนิคด้าน type
      เอกสารเพียงพอที่จะเทียบกับคำอธิบายแบบทีละขั้นในบล็อกช่วงแรก ๆ ได้ และงานด้าน query optimization น่าสนใจเป็นพิเศษ
      แต่ถ้าไม่ได้ทำงานในหน่วยความจำจาก Rust ค่าใช้จ่ายในการ serialize ข้อมูลจะสูง และตัวโปรเจกต์เอง ต่อให้มองในแง่ดี ก็อยู่ในสภาพค่อนข้างเงียบ

  • ก่อนหน้านี้แฟน ๆ Clojure เคยบอกว่า Datalog ดีกว่า SQL และน่าเสียดายที่ฐานข้อมูลเชิงสัมพันธ์ทั้งหมดใช้ SQL
    ผมยังไม่ได้เจาะลึกพอว่าทำไมพวกเขาถึงคิดแบบนั้น

    • โดยพื้นฐานแล้ว Datalog กระชับกว่า SQL มาก ค่าใช้จ่ายในการแยก view ต่ำกว่ามาก และรองรับ transitive closure ได้เหนือชั้นมาก
      http://canonical.org/~kragen/binary-relations เริ่มจากคิวรีแบบไม่ recursive ที่เรียบง่าย แต่การแปลเป็น SQL ก็เข้าขั้นอาชญากรรมแล้ว ส่วนวิธีแก้ด้วย SQL ที่แยกส่วนอย่างเหมาะสมนั้นถึงขั้นสมควรถูกประหาร
      ช่วงหลัง ANSI SQL เพิ่มความสามารถแบบ recursive เข้ามาแล้ว จึงไม่ใช่ว่าเป็นไปไม่ได้โดยสิ้นเชิงอีกต่อไป แต่มีข้อเสียใหญ่สามอย่าง
      อย่างแรก เผลอทำให้ SQL เป็น Turing-complete ไปเสียแล้ว ในทางกลับกันคิวรี Datalog รับประกันว่าจะสิ้นสุด
      อย่างที่สอง ยังใช้งานได้เทอะทะมาก
      อย่างที่สาม เพราะเหตุผลข้อแรก จึงมักไม่ได้ถูก implement อย่างสมบูรณ์ ทำให้ไว้ใจใช้งานได้ยาก
    • dialect แบบ Clojure/Datomic เข้าใจยาก แต่ผมเห็นด้วยกับทิศทางใหญ่
      ถ้าอยากลองจับ Datalog ในสภาพแวดล้อม notebook ที่เป็นมิตรบนออนไลน์ แนะนำ Percival
      https://percival.ink/
      ในบรรดา implementation ของ Datalog ไม่มีมาตรฐานเทียบเท่า “ANSI SQL” แต่ถ้าเข้าใจแนวคิดหลักแล้ว Datalog แบบอื่น ๆ ก็ไม่ยากนัก
      ยังมี fork ของ Percival ที่คอมไพล์ Datalog เป็น SQLite ด้วย ดังนั้นถ้าอยากดูว่าทั้งสองอย่างแสดงสิ่งเดียวกันอย่างไร ก็ลองดูได้
      https://percival.jake.tl/
      aggregation และ join ขั้นสูงกว่านี้ยังไม่เสร็จ แต่รูปแบบพื้นฐานทำงานได้ดี
      Logica เป็นคอมไพเลอร์ Datalog→SQL ที่จริงจังและสมบูรณ์กว่ามาก สร้างโดยนักวิจัยของ Google โดยคอมไพล์ไปเป็น BigTable, DuckDB และ SQL dialect บางแบบ
      https://logica.dev/
      จุดที่ Datalog ง่ายขึ้นมากกว่าหนึ่งลำดับขั้นคือเวลาจัดการ คิวรี/กฎแบบ recursive
      ใน SQL ก็ทำได้ แต่ความรู้สึกใกล้เคียงกับการดูด Play-Doh ผ่านหลอด
      Materialize.com ของ Frank มีรูปแบบ SQL “WITH MUTUALLY RECURSIVE” ที่ดีกว่าวิธี recursive แบบ ANSI SQL เดิมมาก และ Notion กำลังประเมินเพื่อใช้กับคิวรีโหลดหน้าและการซิงก์ข้อมูล
      https://materialize.com/blog/recursion-in-materialize/
      Feldera ก็มีรูปแบบคล้ายกันสำหรับ recursive view
      https://www.feldera.com/blog/recursive-sql-queries-in-feldera
      ผมชอบที่ Feldera สามารถทำให้แต่ละ “rule” หรือ sub-view เป็น statement แยกกันได้ โดยไม่ต้องยัดทุกอย่างไว้ใน statement ยักษ์เพียงอันเดียว
      ข้อเสียหลักที่เห็นระหว่างทดสอบคือ SQL dialect ของ Feldera มีข้อจำกัดที่สืบทอดมาจาก Apache Calcite อยู่พอสมควร ส่วน SQL dialect ของ Materialize พยายามอย่างหนักมากที่จะให้เข้ากันได้กับ PostgreSQL

  • เป็นบทความใหม่ของ McSharry ยอดเยี่ยมเลย
    ครั้งสุดท้ายที่ตรวจดู ดูเหมือนว่า VMWare จะถอยห่างจาก differential datalog ไปแล้ว

    • ทีม Differential Datalog ไปก่อตั้ง Feldera
      https://www.feldera.com/
      ดูเหมือนพวกเขาเปลี่ยนจาก differential Datalog ไปเป็น differential SQL ซึ่งผมคิดว่าอาจเป็นเพราะตระหนักแล้วว่า Datalog ขายยากจริง ๆ