Xây dựng một engine Datalog tương tác bằng Rust

 (github.com/frankmcsherry)
1 điểm bởi GN⁺ 2025-06-16 | 1 bình luận | Chia sẻ qua WhatsApp
  • Từ những giới hạn về khả năng sử dụng và hiệu năng của các công cụ Datalog được bộc lộ tại workshop về lập trình logic, thử nghiệm datatoad — một shell Datalog tương tác dựa trên Rust — đã bắt đầu
  • datatoad hướng tới cấu trúc cho phép thêm quy tắc trong lúc chạy và liên tục suy dẫn các fact mới; nó giảm chi phí xử lý trùng lặp trong tập fact bằng lưu trữ columnar và tầng LSM
  • Việc đánh giá quy tắc chuyển phần thân Datalog thành bài toán join để xử lý, và tùy theo trạng thái stable mà tách thành đánh giá toàn bộ và đánh giá tăng dần, tránh các join stable-stable đã tính trước đó
  • Trong thử nghiệm với bộ dữ liệu Graspan, chỉ bằng cách viết lại quy tắc thủ công và đưa thêm các quan hệ trung gian, phân tích aliasing đã giảm từ 736,34 giây·50,13GB xuống 119,34 giây·5,32GB
  • Các công việc tiếp theo mở rộng sang tối ưu hóa kế hoạch join dựa trên e-graph, layered trie, biểu diễn byte độ rộng cố định, spill ra đĩa, đánh giá phân tán, streaming join và demand transform

Vấn đề datatoad muốn giải quyết

  • Vào cuối tuần Memorial Day, tại workshop về lập trình logic, sự bất tiện của các công cụ Datalog dùng cho phân tích chương trình trở nên nổi bật; từ đó nảy sinh thử nghiệm xây dựng một triển khai Datalog đơn giản, dùng được và nhanh
  • Đối tượng triển khai không phải là trình chạy ví dụ tĩnh, mà là một shell Datalog tương tác
    • Có thể nạp hàng loạt fact
    • Có thể thêm quy tắc mới trong lúc chạy
    • Liên tục phản ánh kết quả của các quy tắc được thêm vào trạng thái hiện có
  • Có thể theo dõi mã tại datatoad repository
  • datafrog hiện có cung cấp thuật toán cốt lõi của một engine Datalog, nhưng ở dạng người dùng phải tự nối dây; datatoad tổ chức lại cùng ý tưởng đó theo cách dễ dùng hơn
  • Trong ví dụ nullability của đồ thị dataflow httpd, datatoad mất 8,3 giây với dữ liệu Vec<String> và truy vấn chưa được biên dịch, chậm hơn khoảng 4 lần so với khoảng 2 giây của ví dụ datafrog dùng dữ liệu (u32, u32)
  • Với bài toán reachability, nó tạo ra cùng số tuple đầu ra như triển khai datafrog, nhưng chưa phải là trạng thái đã hoàn tất kiểm chứng tính đúng đắn tổng quát

Mô hình Datalog và cấu trúc shell

  • Datalog là ngôn ngữ trong đó khi viết các quy tắc logic đơn giản, nó sẽ suy dẫn mọi fact có thể đạt tới từ các quy tắc đó
  • Quy tắc gồm head và body
    • Ví dụ: tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c).
    • tri, edge là các quan hệ, còn a, b, c là biến
    • Biến xuất hiện trong head cũng phải có trong body
  • Fact được xử lý như quy tắc có body rỗng
    • Ví dụ: edge(1, 2) :- .
    • Có thể dùng nhiều head để viết nhiều fact cùng lúc
  • Nhờ tính đơn điệu của Datalog, ngay cả khi thêm quy tắc hoặc fact, tập fact đúng không bị thu hẹp; cùng một tập quy tắc đầu vào sẽ đạt tới cùng một kết quả bất kể thứ tự quy tắc
  • Biểu diễn trong Rust xoay quanh ba cấu trúc Rule, Atom, Term
    • Rule { head: Vec<Atom>, body: Vec<Atom> }
    • Atom { name: String, terms: Vec<Term> }
    • Term::Var(String) hoặc Term::Lit(String)
  • Việc lưu literal dùng Vec<u8> thay vì String
    • Các tính chất cần thiết là tính bằng nhau của literal và một thứ tự sắp xếp tùy ý
    • Việc các byte mang ý nghĩa String, (u32, u32) hay ý nghĩa khác được để mở cho người dùng
  • Trạng thái interpreter lưu cả quy tắc và fact
    • rules: Vec<Rule>
    • facts: facts::Facts
  • Khi shell parse dòng nhập thành Datalog, nó gọi State::extend và State::update; lệnh .list xuất ra tên từng quan hệ và số fact

Parse và lưu fact

  • Parser nằm trong parse.rs, dùng một dạng lấy từ cú pháp Soufflé
  • Biến bắt đầu bằng ?
  • Token được giới hạn ở ., ,, (, ), :-, ?; phần văn bản còn lại được xử lý như tên atom hoặc term
  • Tokenizer loại bỏ khoảng trắng và thay :- bằng ← để quét như một ký hiệu đơn
  • Việc parse quy tắc đọc các atom head cho tới turnstile, rồi đọc các atom body cho tới dấu chấm
    • Atom gồm tên, ngoặc trái, danh sách term và ngoặc phải
    • Term là biến nếu có ?, nếu không thì là literal
  • Quy tắc sai trả về None, và hiện chưa cho biết chi tiết phần nào bị sai
  • Để thêm quy tắc phủ định cần token Exclamation, nhưng hiện chưa xử lý

Vòng đời của tập fact

  • Cách lưu Vec<Vec<String>> đơn giản có các cấp cấp phát lồng nhau nên bất lợi cho quản lý bộ nhớ
  • datatoad dùng columnar để chuyển kiểu Rust thành một số ít cấp phát tuyến tính với layout phẳng
    • Lưu byte của chuỗi, ranh giới chuỗi và ranh giới fact trong các mảng riêng
  • FactContainer bọc danh sách fact đã được sắp xếp và loại trùng, đồng thời dùng wrapper type để hàm ý bất biến sắp xếp/loại trùng
  • Vì container dạng cột trên thực tế là append-only và không phù hợp để thay đổi ở giữa, việc thêm fact mới dùng dạng log-structured merge-tree (LSM)
    • FactLSM { layers: Vec<FactContainer> }
    • Quản lý sao cho kích thước các tầng tăng theo cấp số nhân
    • Duy trì trạng thái đã sắp xếp và loại trùng bằng cách hợp nhất các tầng có kích thước trong phạm vi gấp đôi nhau
  • FactBuilder có cả vùng active chưa sắp xếp và có thể trùng lặp, cùng các layers đã sắp xếp và loại trùng
  • Fact của mỗi quan hệ di chuyển qua ba giai đoạn
    • to_add: fact mới đến nhưng chưa được kiểm tra có novel hay không
    • recent: distinct và vẫn cần xử lý
    • stable: distinct fact đã được xử lý hoàn toàn
  • FactSet::advance chuyển recent sang stable, rồi loại khỏi to_add các fact đã có trong stable để tạo recent mới

Đánh giá quy tắc là bài toán join

  • Phần thân của quy tắc Datalog có thể xem là equi-join trong cơ sở dữ liệu quan hệ
  • Ví dụ quy tắc tam giác như sau
    • tri(?a, ?b, ?c) :- edge(?a, ?b), edge(?b, ?c), edge(?a, ?c).
  • Nếu liệt kê trực tiếp mọi phép gán biến thì dù là hữu hạn cũng sẽ quá nhiều, nên cần sắp xếp theo các cột khóa của biến chung rồi merge
  • Triển khai rút gọn body từ phải sang trái
    • Join hai quan hệ cuối để tạo quan hệ trung gian, rồi join tiếp với quan hệ bên trái
    • Nếu chỉ có một body atom thì chỉ chuyển đổi sang dạng head
  • JoinPlan chứa các thông tin sau
    • bodys để sắp xếp lại và lọc các body atom cho phù hợp với join
    • joins chứa key arity và projection đầu ra của từng join trung gian
    • heads biểu thị tọa độ hoặc literal sẽ chèn vào head atom
    • arity của join tạo head cuối cùng
  • Kế hoạch hiện tại là right-linear join plan đơn giản
  • Khi tạo JoinPlan, dùng vị trí xuất hiện leftmost và rightmost của từng biến để xác định cần giữ giá trị biến đến lúc nào, rồi chia các cột body atom thành cột dead, key và value
  • Hàm cốt lõi là implement_plan(rule, plan, pos, stable, facts)
    • Khi thêm quy tắc mới, bắt đầu với stable = true trên toàn bộ fact
    • Trong quá trình áp dụng lặp lại các quy tắc hiện có, dùng stable = false để chỉ tính các suy dẫn mới

Join tăng dần và merge join

  • Join là song tuyến tính nên được phân rã như sau
    • (A + a) ⋈ (B + b) = A ⋈ B + A ⋈ b + a ⋈ B + a ⋈ b
  • A ⋈ B đã được tạo giữa các phần ổn định thì không cần tính lại
  • Nếu chỉ cần các suy diễn mới, chỉ thực hiện ba phép join
    • A ⋈ b
    • a ⋈ B
    • a ⋈ b
  • join_with bao gồm hoặc loại trừ join stable-stable tùy theo cờ stable
  • join thực tế là merge join, quét tuần tự hai đầu vào đã được sắp xếp
    • Nếu khóa giống nhau, gọi action cho mọi tổ hợp ứng với khóa đó
    • Nếu khóa khác nhau, dùng gallop để nhanh chóng nhảy tới điểm có khả năng khớp tiếp theo
  • gallop là ý tưởng lấy từ EmptyHeaded: tiến theo cấp số nhân trong khi điều kiện đơn điệu còn đúng, rồi thu hẹp lại theo kiểu tìm kiếm nhị phân

Thử nghiệm phân tích Nullability

  • Dữ liệu thử nghiệm là dữ liệu của dự án Graspan, và vẫn còn trên Google Drive
  • Đầu vào phân tích dataflow có hai quan hệ e và n
    • n(?a, ?b): giá trị ?a có thể được dùng tại vị trí ?b
    • e(?a, ?b): giá trị ở một vị trí ?a có thể di chuyển sang vị trí khác ?b
  • Quy tắc reachability như sau
    • n(?a, ?c) :- n(?a, ?b), e(?b, ?c) .
  • Với đầu vào httpd, .list ban đầu cho thấy
    • e: 9,905,624
    • n: 138,331
  • Chạy trực tiếp quy tắc mất khoảng 15 giây, và n trở thành 9,393,283 mục
  • Một lý do khiến chậm là quan hệ tạm .temp-0-0-in, nơi n được sắp xếp lại theo khóa join, đã phình lên tới 9,393,283 mục
  • Khi người dùng viết lại quy tắc, hiệu năng được cải thiện
    • m(?loc, ?val) :- n(?val, ?loc) .
    • m(?loc, ?val) :- m(?mid, ?val), e(?mid, ?loc) .
  • Trên cùng đầu vào httpd, sau khi viết lại, quy tắc thứ hai chạy ở mức 8,43 giây
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
datatoad 8.43s 24.33s 55.01s
datafrog 1.30s 4.06s 8.03s
  • Số liệu Graspan của lnx_kernel có dấu *; bài báo báo cáo cả tổng thời gian và do xung đột định danh đầu vào nên khó xem là đúng cùng một lần chạy
  • Nếu muốn so sánh với công cụ mà người thực hành sử dụng, Soufflé có thể là đối tượng phù hợp hơn

Phân tích aliasing và tối ưu thủ công

  • Phân tích thứ hai là phân tích aliasing của Zheng và Rugina được Graspan đưa vào
  • Có hai quan hệ đầu vào
    • A(?val, ?loc): ?loc <- ?val
    • D(?val, ?loc): ?loc được dùng dưới dạng *?val
  • Mục tiêu là tìm memory alias và value alias
    • memory alias: hai biểu thức lvalue có thể trỏ tới cùng một vị trí bộ nhớ
    • value alias: hai biểu thức có thể đánh giá ra cùng một giá trị con trỏ
  • Ký hiệu trong bài báo có ^T, ^?, ^*
    • ^T: chuyển vị quan hệ
    • ^?: hạng mục tùy chọn
    • ^*: lặp 0 lần trở lên
  • Trong Datalog, ^? được biểu diễn bằng cách tách thành hai quy tắc, còn ^* được xử lý bằng cách thêm tường minh quan hệ identity
  • Lần chạy quy tắc ban đầu mất nhiều thời gian
    • Sau khi nhập hai quy tắc khởi tạo identity cuối cùng, lần lượt mất 686,57 giây và 736,34 giây
    • Tiến trình dùng 50,13GB
    • V: 361,947,256
    • M: 92,806,768
    • F: 2,669,647
  • Dùng tường minh các quan hệ chuyển vị -V, -M, -a, -d để loại bỏ quan hệ tạm -in
    • Tổng 815,92 giây, khoảng 13,6 phút
    • Bộ nhớ 31,96GB
  • Cách tiếp cận của Zheng và Rugina là demand-driven và thực tế chỉ cần M, nên inline V vào M
    • Không tạo 361,947,256 mục -V
    • Bộ nhớ giảm xuống 18,96GB
  • Đặt tên và tái sử dụng đoạn join lặp lại là Fd, sau đó tính trực tiếp Fd thay cho F để giảm cả vấn đề identity
  • Dạng cuối cùng đưa vào quan hệ trung gian MFd cho kết quả sau
    • Thời gian chạy: 119,34 giây
    • Bộ nhớ: 5,32GB
    • -M: 92,806,768
    • Fd: 1,858,986
    • MFd: 73,474,947
  • Chỉ bằng viết lại thủ công, bộ nhớ và thời gian chạy được cải thiện gần 10 lần so với thử nghiệm ban đầu
  • Tạo các kết quả trung gian được đặt tên cho phép phần nào trực tiếp cấu thành join plan kiểu bushy-tree mong muốn, nhưng nếu đặt tên cho một quan hệ thực ra không cần thiết như V, hệ thống sẽ tạo nó với chi phí lớn

Truy vấn demand-driven và magic sets

  • Truy vấn demand-driven là cách chỉ khám phá phần cần thiết cho một fact mục tiêu cụ thể
  • Magic sets có thể được dùng như một lời giải xấp xỉ
    • Đây là phép biến đổi nhúng target literal vào truy vấn
    • Có thể nghĩ tới biểu thức bắt đầu không phải từ mọi d mà chỉ từ d quan tâm, nhưng nếu áp dụng đơn giản thì có thể sai
  • Magic sets không phải đáp án tối ưu; tác giả dự định đọc thêm các bài báo liên quan để tìm cách tiếp cận có thể hiệu quả hơn
  • Các liên kết liên quan như sau

Tối ưu join plan và IR song song dữ liệu

  • Sức hấp dẫn của Datalog nằm ở chỗ nó bộc lộ một cách thuần túy vấn đề cốt lõi của tính toán song song dữ liệu là data rendezvous, hơn là bản thân Horn clause
  • Quy tắc h(x, y, z) :- b1(x, y), b2(y, z) . có thể được xem là bài toán gom các x và z liên quan về một chỗ cho từng y
  • Thao tác cơ bản của tính toán song song dữ liệu là gom record theo khóa và chuyển cho logic người dùng; join biểu diễn phần định tuyến chọn lọc trong đó
  • IR đơn giản dùng các opcode sau
    • Var(String): collection có tên
    • Map(Action): filter, hoán vị, projection
    • Key(usize): đánh dấu vài cột phía trước là khóa
    • Mul(usize): kết hợp nhiều collection có cùng độ dài khóa
  • Sau đó Map và Key được gộp vào Action.key_arity
  • Action chứa literal filter, bộ lọc bằng nhau của biến, projection và key arity
  • Điểm khởi đầu đơn giản nhất là cross join tất cả body atom rồi đặt filter và projection cho từng head; cách này tạo ra kết quả đúng nhưng hiệu năng rất tệ

Tối ưu hóa dựa trên e-graph

  • Quá trình tối ưu hóa sử dụng e-graph và equality saturation
  • Tài liệu tham khảo gồm trang web egg, bài viết trước đó và egg
  • term graph được biểu diễn dưới dạng map các ENode<T> có gắn Id, chia sẻ các node giống nhau để biểu diễn chương trình gọn hơn
  • Có ba quy tắc e-graph đã áp dụng
    • MulPermute: biến các hoán vị đầu vào của Mul(k) thành tương đương
    • MulPartition: chia Mul(k) theo nhiều cách để tạo các dạng tương đương
    • MapPushdown: đẩy Map xuống dưới Mul(2) để tạo dạng join có khóa
  • Quy tắc ví dụ như sau
    • head(?a, ?b) :- a(?x, ?a), b(?y, ?x), b(?y, ?z), a(?z, ?b) .
  • Sau equality saturation, chi phí được gán ở bước extraction
    • Chi phí Map là số cột đầu ra
    • Chi phí Mul là tổng số cột khóa và số cột không phải khóa của các đầu vào
    • Chi phí Var là 0
    • Nếu hòa, tối thiểu hóa số lượng Map, rồi đến số lượng Mul
  • Trong ví dụ, kế hoạch được chọn được tìm thấy ở wave two với tối đa hai cột không tương quan
    • map cho đầu vào a, b
    • một lần join
    • projection trung gian
    • join với chính nó
    • projection cuối cùng
  • Việc tìm kiếm kế hoạch này mất khoảng 40ms ngay cả trong release build, và phần lớn thời gian được dùng cho equivalence saturation

Cập nhật thực thi kế hoạch tối ưu hóa

  • Trong bản cập nhật 2025-06-29, phần thực thi kế hoạch đã tối ưu hóa được triển khai
  • Kế hoạch được xuất ra dưới dạng Vec<ENode<Op>>, nhưng khi thực thi thực tế không chạy từng node một cách độc lập
  • Cách thực thi dự định như sau
    • Với mỗi Var, áp dụng nhiều Map phụ thuộc vào nó trong một lần quét collection bên ngoài
    • Với mỗi Mul, áp dụng nhiều Map phụ thuộc vào nó trong một lần quét join
  • Op::Map(action) không hẳn là một phép toán được thực hiện trực tiếp, mà là tác vụ được đưa vào hàng đợi cho phép toán phụ thuộc
  • Để làm việc này, TempAction được đưa vào
    • bộ lọc literal
    • bộ lọc đẳng thức biến
    • projection có thể chứa tham chiếu cột hoặc string literal
  • Bước chuẩn bị kế hoạch thực thi tách body và head, rồi gom các action Map theo từng node đầu vào
  • Khi thực thi Var, việc xử lý tên được chia thành ba trường hợp
    • tạo head thì dùng tên quan hệ head
    • biến đổi identity thì tái sử dụng tên đầu vào hiện có
    • biến đổi không trivial thì lưu vào tên tạm .temp-*
  • Thực thi Mul(2) kiểm tra key arity và tên của hai đầu vào, rồi gọi join_with để tích lũy kết quả vào nhiều builder
  • Trong ví dụ aliasing phức tạp, thực thi kế hoạch đã tối ưu hóa mất 114,28 giây, nhanh hơn khoảng 5 giây so với mức 119 giây trước đó, nhưng lý do chưa rõ ràng
  • Tối ưu hóa multi-rule chưa được triển khai, và có thể cần suy nghĩ lại chính cách tiếp cận bằng kế hoạch

Tối ưu hóa biểu diễn fact

  • Đã giảm 50GB xuống 5GB, nhưng vẫn được xem là dùng nhiều bộ nhớ hơn cần thiết khoảng 10 lần
  • largest layer của quan hệ lớn -M chứa 57.289.225 fact và dùng khoảng 2.098.253.766 byte
    • ranh giới fact: 458.313.800 byte
    • ranh giới term: 916.627.600 byte
    • dữ liệu byte thực tế: 723.312.366 byte
  • Tối ưu hóa đầu tiên tận dụng việc arity là cố định
    • Nếu mọi fact đều có 2 cột, ranh giới fact có thể được biểu diễn chỉ bằng stride và length
    • Về thực chất loại bỏ dữ liệu ranh giới ở mức 458MB
  • Tối ưu hóa thứ hai là làm cho độ dài term bằng nhau
    • Nếu biến số thành chuỗi fixed-width 7 chữ số, ranh giới term cũng có thể được biểu diễn bằng stride và length
    • Đổi lại, số byte thực tế có thể tăng
  • Tối ưu hóa thứ ba là biểu diễn số bằng binary thay vì text
    • Số 7 chữ số nằm gọn trong u32 4 byte
    • Vì cũng nằm gọn trong 3 byte, kết quả là 57,289,225 × 2 × 3 = 343,735,350 byte
    • Giảm từ khoảng 2GB xuống khoảng 350MB, tức giảm khoảng 6,10 lần
  • Nếu nén sự lặp lại của term đầu tiên thì còn giảm thêm
    • Có 57.289.225 fact, nhưng distinct first term chỉ có 1.147.612
    • Nếu lưu dưới dạng (Term, [Term]) thay vì (Term, Term), largest layer giảm xuống mức 184.491.407 byte
    • Giảm khoảng 11,37 lần so với 2GB ban đầu
  • Trong bản cập nhật 2025-07-02, tối ưu hóa bước 1 đã được áp dụng
    • largest batch trở thành 343.735.382 byte, nhiều hơn giá trị lý thuyết 343.735.350 byte đúng 32 byte
    • Thời gian thực thi giảm từ khoảng 115 giây xuống khoảng 95 giây, cải thiện khoảng 20%

Biểu diễn layered trie

  • Trong bản cập nhật 2025-07-20, layered trie đã có thể hoạt động
  • So sánh biểu diễn row-oriented và biểu diễn layered trie column-oriented
    • toad-row
    • toad-col
dataflow httpd psql lnx_kernel
graspan 684s 8640s 42840s*
toad-row 3.88s 11.30s 25.67s
toad-col 3.47s 11.94s 23.09s
datafrog 1.30s 4.06s 8.03s
aliasing httpd psql lnx_kernel
graspan 8.4h 6.0h* 1.7h*
toad-row 28.21s 28.25s 7.62s
toad-col 19.39s 21.96s 9.48s
datafrog UNK UNK UNK
  • layered trie là phương thức hạn chế sự lặp lại của các cột phía trước trong biểu diễn row đã sắp xếp
  • Mỗi cột là một danh sách các danh sách giá trị
    • Mỗi danh sách là danh sách các giá trị distinct đã sắp xếp, tương ứng với prefix của cột trước đó
    • Số danh sách trong một cột bằng tổng số item của cột trước đó
  • Có thể xem như một cây, nhưng triển khai thực tế vẫn giữ theo dạng cột
  • Ưu điểm là có thể thực hiện tìm kiếm, join, difference và merge theo từng đơn vị prefix
  • Khi hầu như không có giá trị distinct và xem toàn bộ hàng một lần sẽ tốt hơn, cách tiếp cận row-oriented có thể có lợi hơn
  • Đưa vào trait FactContainer làm abstraction chung
    • form
    • len
    • apply
    • join
    • except
    • merge
  • apply dùng stack tường minh thay vì đệ quy để theo dõi range của từng layer, tạo hàng và chuyển cho action
  • align là helper chung để khớp prefix của hai layered trie
    • Ordering::Less: range chỉ có trong self
    • Ordering::Greater: range chỉ có trong other
    • Ordering::Equal: prefix có độ dài arity chung ở cả hai phía
  • join, except, merge đều được triển khai trên align
    • join bung phần extension còn lại tại prefix chung để cross join
    • except graft range chỉ có trong self vào TrieBuilder
    • merge graft các range self-only, other-only và equal đúng một lần tùy trường hợp

Tối ưu hóa fixed-width và hiệu năng

  • Khi có thể nâng cấp lên fixed-width [u8; 4], hiệu năng so sánh được cải thiện đáng kể
  • layered trie có thể áp dụng tối ưu hóa fixed-width theo từng cột, nên về dài hạn có khả năng lợi thế hơn row
  • upgrade·downgrade đã được áp dụng dễ dàng cho except và merge, nhưng áp dụng cho join khó hơn do vấn đề kiểu của 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
  • Hiện khoảng 2/3 thời gian được tiêu tốn dưới join
  • Cho rằng vẫn còn dư địa tối ưu hóa join thêm ít nhất khoảng 2 lần nữa
  • Thử nghiệm chỉ đơn giản sắp xếp lại inner loop không tạo ra cải thiện đo được

Chuyên biệt hóa xuống mức mã đã biên dịch

  • Khi phát hiện các term có cùng độ dài và các fact có cùng arity, có thể xem Vec<u8> như Vec<[[u8; B]; T]>
  • Dạng này giúp Rust hiểu rõ hơn hình dạng dữ liệu, giảm chi phí kiểm tra bounds·length, và khiến phép so sánh đặc biệt rẻ
  • Phép so sánh được dùng ở nhiều điểm trong datatoad
    • Sắp xếp và loại trùng batch fact
    • Hợp nhất batch
    • Hợp nhất khóa join
    • So sánh fact mới với fact hiện có để lọc
  • Hiệu năng chuẩn như sau
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
  • Tối ưu hóa sắp xếp được thử nghiệm bằng cách unsafe transmute Vec<u8> thành Vec<[u8; 8]> rồi 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
  • Tối ưu hóa hợp nhất được triển khai theo cách đơn giản: nối hai input rồi 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
  • Vẫn chưa đạt tới hiệu năng đã biên dịch của datafrog
  • Chi phí so sánh còn lại cũng nằm trong join và antijoin; dự định sẽ xem xét lại các cơ hội tối ưu hóa tương tự khi chuyển sang cấu trúc dựa trên trie
  • Đang tìm cách loại bỏ unsafe, đồng thời bổ sung kết luận rằng nên tránh mã unsafe

Những việc còn lại

  • Spill ra đĩa

    • Kho lưu trữ columnar gồm một số ít vùng cấp phát lớn
    • Khi tạo, có thể ghi ra file thay vì bộ nhớ và dùng lại bằng memory map

  • Đánh giá phân tán

    • Join, loại trùng và kiểm tra distinctness dựa trên tính bằng nhau của khóa
    • Có thể phân tán khóa và dữ liệu tương ứng cho nhiều worker
    • Có thể mở rộng tới nhiều process bằng timely_communication

  • Đánh giá quy tắc dạng streaming

    • Join hiện tại dùng binary join và materialized output
    • Nếu có các index cần thiết, có thể tạo kế hoạch không materialize trạng thái nội bộ
    • Worst-case optimal join cũng sẽ được xử lý ở đây

  • Chuyên biệt hóa custom representation

    • Có ý tưởng phát hiện transitive closure và chuyên biệt hóa cho strongly connected component decomposition
    • Equivalence relation có thể dùng cấu trúc dữ liệu union-find
    • bddbddb và factorized databases cũng được đề cập như các chủ đề liên quan

  • Tìm kiếm các fact liên quan

    • Cần hiểu và áp dụng demand transform
    • Được xem là phép biến đổi cần thiết cho khám phá Datalog tương tác

Bài viết liên quan

1 bình luận

 
GN⁺ 2025-06-16
Ý kiến trên Hacker News

  • Thấy bài này leo lên vị trí số 1 cũng thú vị
    Hiện tôi đang làm một game chiến thuật thời gian thực bằng Differential Datalog và Rust, trong đó logic game do DDL quản lý
    Phần lớn chỉ là cái cớ để tiếp xúc với ý tưởng mới và thử một màn yak shaving bất tận
    https://github.com/vmware-archive/differential-datalog

    • Có vẻ là một demo hay ho làm bằng ddlog
      Nhân tiện, nhóm ddlog giờ đã lập startup Feldera, và việc dùng trực tiếp DBSP trong Rust cũng đáng cân nhắc
      https://github.com/feldera/feldera
    • Tôi tò mò liệu có thể trộn repository của bài gốc với salsa, crate chạy bộ phân tích Rust, để tạo ra một kiểu differential datalog Frankenstein không
      https://github.com/salsa-rs/salsa
    • Tôi tò mò tình trạng triển khai hiện ra sao và có thể đi xa đến đâu
      DDLog không còn được bảo trì tích cực nữa nên càng thú vị hơn

  • “Ta, một kẻ phản diện khét tiếng, được mời đến, nửa tin rằng mình sắp nhận sự trừng phạt lẽ ra đã phải đến từ lâu.” — đây là câu mở đầu hay nhất trong các bài blog kỹ thuật tôi đọc năm nay
    Những đoạn chen ngang của người kể chuyện cũng rất tuyệt, và hiếm có bài nào vừa sâu về kỹ thuật vừa đọc thú vị như vậy
    Hành trình tối ưu hóa truy vấn alias có cảm giác như tiểu thuyết trinh thám; độc giả cũng cùng rên rỉ trước mức dùng bộ nhớ 50GB, rồi reo lên khi nó giảm xuống 5GB
    Cả code lẫn bài viết đều xuất sắc

  • Tôi đã làm được một ít việc trong quá trình port mangle datalog sang Rust
    Nó nằm ở https://github.com/google/mangle/tree/main/rust, trong cùng repository với bản triển khai Go
    Vì mức ưu tiên không cao và còn có hội chứng hệ thống thứ hai, tiến độ khá chậm
    Mangle Rust đi theo hướng xử lý dữ liệu kích thước tùy ý bằng cách đọc/ghi các fact trên đĩa qua memory mapping, còn bản Go là kiểu in-memory
    Bài này hay vì vừa parse Datalog vừa đụng tới LSM tree, và dễ theo dõi hơn nhiều so với các tài liệu liên quan đến datafrog
    Trong Rust có nhiều triển khai Datalog dùng procedural macro như ascent, crepe, nhưng nhược điểm là khó nhận truy vấn lúc runtime
    Nếu dùng cho phân tích tĩnh với truy vấn và chương trình cố định, cách tiếp cận procedural macro có thể tốt hơn

  • Dù làn sóng phục hưng Datalog hiện tại có vẻ đang yếu đi, tôi vẫn vui khi thấy những người đam mê cốt lõi tiếp tục bám trụ
    Hội nghị Datalog 2.0 gần đây nhỏ hơn trước khá nhiều, và hội nghị HYTRADBOI lần thứ hai cũng có tỷ trọng Datalog thấp
    Ở HYTRADBOI đầu tiên, một phần tư bài gửi có liên quan đến Datalog
    Việc những người khác chia sẻ các dự án Datalog gần đây cũng rất đáng khích lệ
    Hiện tôi đang chuẩn bị cho một đợt migration phần mềm quy mô lớn và xây dựng pipeline chất lượng dữ liệu cho cơ sở dữ liệu SQL legacy
    Nếu cấu trúc truy vấn tốt thì rất dễ đọc, nên tôi cho rằng Datalog hữu ích hơn SQL nhiều trong việc xác định và tìm các vấn đề chất lượng dữ liệu

    • Dù đồng ý với hướng nhìn chung, khó xem số người tham dự ít của Datalog 2.0 là ví dụ tiêu biểu cho sự đi xuống của Datalog
      Datalog 2.0 là một workshop vệ tinh của LPNMR, một hội nghị châu Âu tương đối ít được biết đến, và năm đó hội nghị tình cờ được tổ chức ở Dallas
      Khi trực tiếp tham dự, tôi cũng thấy sự kiện hơi vắng; tôi có nộp bài cho workshop, nhưng không thấy nhiều người trong lĩnh vực đó
      Ngoại lệ là một số người phía châu Âu giới thiệu solver Nemo khá nổi bật
      Tôi nghĩ việc năm nay ít người tham dự phản ánh rõ hơn rằng đây là workshop vệ tinh của một hội nghị vốn không quá danh tiếng, và sự kiện chính lại là ICLP, hơn là phản ánh sự thiếu quan tâm đến triển khai Datalog
      Tất nhiên tôi không định phản bác luận điểm lớn rằng gần như không còn nhiều cái mới trong việc triển khai engine Datalog thuần túy
      Không gian nghiên cứu đã vượt xa mức đó và chuyển sang các vấn đề lạ hơn như streaming (HydroFlow), choice (Dusa), và những thứ gần với general chase (chase engine của Egglog)
      Nhìn chung không mấy ai phản đối rằng Datalog vanilla khá nhàm chán, nhưng forward saturation đơn điệu và mệnh đề Horn là một baseline phong phú với địa hình kỹ thuật hiệu năng đã được hiểu rõ, nên rất phù hợp để xây các lý thuyết thú vị hơn như semiring hay Z-set

  • Nếu bạn thấy phần state machine và parsing thú vị, tôi cũng khuyên xem bài thuyết trình cũ của Rob Pike, Lexical Scanning in Go
    https://www.youtube.com/watch?v=HxaD_trXwRE
    Tuy viết bằng Go, phần lớn nội dung có thể áp dụng dễ dàng cho các ngôn ngữ khác
    Thật tốt khi các ngôn ngữ hiện đại như Rust, Zig, Go hỗ trợ Unicode/rune/grapheme một cách native
    So với Java, .NET, C++ hay các ngôn ngữ script, nhiều vấn đề đơn giản là biến mất

  • Nhìn chung tôi thích các công trình Datalog của tác giả, nhưng mong các tài liệu nhập môn đừng dạy binary join
    Khi ra ngoài trường hợp lý tưởng, bên trong nhanh chóng trở nên lộn xộn, còn phương thức kiểu general join thì dễ tổng quát hóa trong đầu hơn nhiều
    https://en.wikipedia.org/wiki/Worst-case_optimal_join_algorithm

  • Từ lâu khi còn đi học tôi có tiếp xúc sơ qua với Prolog, và đại khái biết nó dùng vào đâu, hữu ích cho việc gì, nhưng không phải là hiểu sâu
    Sau đó tôi cứ nghe nói Datalog rất tuyệt, nhưng thật ra vẫn chưa nắm được Datalog cải thiện điều gì so với Prolog
    Vừa lướt qua trang Datalog trên Wikipedia thì có vẻ Prolog có hiệu năng tương đối kém, còn Datalog thì giảm bớt sức biểu đạt và tính năng để đổi lấy cải thiện hiệu năng lớn, cho phép xử lý các tập dữ liệu lớn hơn và song song hóa nhiều hơn
    Có vẻ điều này cũng bao gồm việc mất tính Turing-complete, nhưng tôi tò mò không biết đó có phải điểm cốt lõi hay tôi đang hiểu sai hoàn toàn

    • Theo tôi biết, Prolog trông giống một ngôn ngữ khai báo: chỉ cần mã hóa các quan hệ là nó sẽ tìm ra câu trả lời, nhưng trên thực tế lại phụ thuộc nhiều vào thứ tự quy tắc, và còn cần các chỉ thị bổ sung như “cut”
      cut không chỉ ngăn các tính toán lãng phí mà còn có thể ảnh hưởng đến kết quả
      Ngược lại, Datalog nhìn chung gần với một cơ sở dữ liệu quan hệ có cú pháp khác hơn
    • Datalog đơn giản hơn, không Turing-complete, và nếu tôi nhớ đúng thì dùng suy luận tiến, kéo theo các hệ quả dây chuyền đối với hiệu năng và đặc tính bộ nhớ
      Một không gian tìm kiếm khổng lồ nhưng tầm thường trong Prolog có thể ngốn quá nhiều bộ nhớ trong Datalog đến mức không thể biểu diễn được
      Datalog giống một chiếc xe đi làm gắn hộp số CVT, còn Prolog gần với xe F1 hơn
      Thay vì là một cải tiến, nó giống như cắt bớt một phần Prolog để người ta không tự bắn vào chân mình, và cũng dễ triển khai, nhúng vào các ứng dụng khác hơn nhiều
      Nếu đã quen với Prolog thì Datalog nhìn chung sẽ gây cảm giác tù túng
      Không có call/3, không có term/goal expansion, và về cơ bản Datalog được thiết kế bằng cách rút ra mẫu số chung tối thiểu của Prolog để dùng cho tìm kiếm cơ sở dữ liệu tương tác
      Mã Datalog nhanh thì dễ viết, nhưng trần khả năng cũng thấp hơn nhiều
      Prolog cũng có thể được viết theo cách cho phép đồng thời, nhưng đó là một bài toán trung cấp đòi hỏi phải hiểu cách triển khai
      Guarded Horn Clauses và các ngôn ngữ phái sinh được phát triển để hình thức hóa những phần như vậy, nhưng các phát triển ở Nhật sau Prolog thì rất khó hiểu
      Hiệu năng Prolog phụ thuộc rất nhiều vào lập trình viên, bản triển khai được dùng và nơi nó được dùng
      Giống Lisp, Prolog cũng có thể được dùng để sinh mã máy native từ DSL tại thời điểm biên dịch
      Nếu hiểu cách bản triển khai nền tảng hoạt động và viết mã thuận theo nó thì đủ nhanh
      Tuy nhiên để làm vậy cần viết mã Prolog với một bản triển khai trong vài năm
      Cũng có nhiều nghiên cứu về tối ưu hóa trình biên dịch Prolog, và có cả các bản triển khai độc quyền
      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/

  • Nếu muốn dùng Datalog và Rust, cozodb được viết bằng Rust và cũng cung cấp cú pháp truy vấn Datalog

    • Cozodb trông khá hay nhưng có vẻ gần như không còn hoạt động
      Khoảng tháng 11/2024 tôi xem thử và đã tìm thấy vài điểm có thể cải thiện dễ dàng trong backend lưu trữ SQLite
      https://github.com/cozodb/cozo/issues/285
    • Cozodb nhìn chung hoạt động tốt như tài liệu mô tả và làm việc với nó khá thú vị
      Tôi cũng đã dùng nó cho phân tích tĩnh chương trình, và nội bộ nó sử dụng cây sắp xếp cùng các kỹ thuật kiểu
      Tài liệu đủ tốt để đem so sánh với phần giải thích từng bước trên blog, và đặc biệt công việc tối ưu hóa truy vấn rất thú vị
      Tuy nhiên nếu không làm việc trong bộ nhớ từ Rust thì chi phí tuần tự hóa dữ liệu lớn, và dự án này, nói tích cực nhất, cũng đang khá im ắng

  • Trước đây, các fan Clojure từng nói rằng Datalog tốt hơn SQL, và thật đáng tiếc khi cơ sở dữ liệu quan hệ hầu hết đều dùng SQL.
    Tôi chưa đào sâu đủ để hiểu vì sao họ nghĩ như vậy.

    • Về cơ bản, Datalog ít rườm rà hơn SQL rất nhiều, chi phí tách view nhỏ hơn nhiều, và hỗ trợ bao đóng bắc cầu vượt trội.
      http://canonical.org/~kragen/binary-relations bắt đầu bằng một truy vấn phi đệ quy đơn giản, nhưng bản dịch sang SQL đã gần như “phạm tội”, còn lời giải SQL được tách bạch tử tế thì đáng bị xử tử.
      Gần đây ANSI SQL đã bổ sung tính năng đệ quy nên không còn hoàn toàn bất khả thi nữa, nhưng có ba nhược điểm lớn.
      Thứ nhất, nó vô tình biến SQL thành Turing-complete, trong khi truy vấn Datalog thì được đảm bảo kết thúc.
      Thứ hai, nó vẫn cực kỳ cồng kềnh khi dùng.
      Thứ ba, vì lý do thứ nhất, tính năng này thường không được triển khai đầy đủ, nên khó có thể tin cậy để dùng.
    • Phương ngữ Clojure/Datomic khá khó hiểu, nhưng tôi đồng ý với hướng đi lớn.
      Nếu muốn thử Datalog trong một môi trường notebook thân thiện trên web, tôi khuyên dùng Percival.
      https://percival.ink/
      Trong các triển khai Datalog nói chung không có một chuẩn tương đương “ANSI SQL”, nhưng một khi nắm được ý tưởng cốt lõi thì các Datalog khác cũng không quá khó.
      Cũng đã có một fork của Percival biên dịch Datalog sang SQLite, nên nếu muốn xem hai bên biểu diễn cùng một thứ như thế nào thì có thể xem thử.
      https://percival.jake.tl/
      Aggregate và các join nâng cao hơn vẫn chưa hoàn thiện, nhưng dạng cơ bản hoạt động tốt.
      Logica là một trình biên dịch Datalog→SQL nghiêm túc và hoàn thiện hơn nhiều do một nhà nghiên cứu của Google tạo ra; nó biên dịch sang BigTable, DuckDB và một số phương ngữ SQL.
      https://logica.dev/
      Lĩnh vực mà Datalog dễ hơn từ một bậc độ lớn trở lên là khi xử lý truy vấn/quy tắc đệ quy.
      SQL cũng làm được, nhưng cảm giác gần như hút Play-Doh qua ống hút.
      Materialize.com của Frank có một dạng SQL “WITH MUTUALLY RECURSIVE” tốt hơn nhiều so với cách đệ quy ANSI SQL cũ, và Notion đang đánh giá nó cho truy vấn tải trang và đồng bộ dữ liệu.
      https://materialize.com/blog/recursion-in-materialize/
      Feldera cũng có một dạng tương tự cho view đệ quy.
      https://www.feldera.com/blog/recursive-sql-queries-in-feldera
      Tôi thích Feldera ở chỗ có thể viết mỗi “quy tắc” hoặc subview thành một câu lệnh riêng, thay vì nhét tất cả vào một câu lệnh khổng lồ.
      Nhược điểm chính tôi thấy khi thử nghiệm là phương ngữ SQL của Feldera có khá nhiều ràng buộc kế thừa từ Apache Calcite, còn phương ngữ SQL của Materialize thì rất nỗ lực bám sát khả năng tương thích PostgreSQL.

  • Lại có bài mới của McSharry, tuyệt vời.
    Lần cuối tôi kiểm tra thì có vẻ VMWare đã rời xa differential datalog.

    • Nhóm Differential Datalog đã lập ra Feldera.
      https://www.feldera.com/
      Có vẻ họ đã chuyển từ differential Datalog sang differential SQL, có lẽ vì nhận ra Datalog thực sự rất khó bán.