Huấn luyện mô hình 4B tối ưu hóa truy vấn SQL: Nhanh hơn 81% so với Postgres mặc định

Các trình tối ưu hóa truy vấn (query optimizer) thực sự tốt đến mức nào?

Leis và cộng sự đã đặt ra chính xác câu hỏi này vào năm 2015. Sau đó, họ lại đặt ra nó một lần nữa 10 năm sau đó.

Bất chấp một khối lượng nghiên cứu khổng lồ kéo dài một thập kỷ kể từ khám phá ban đầu của họ, họ nhận thấy rằng các trình tối ưu hóa truy vấn vẫn còn nhiều điều đáng bàn.

Tôi đã rất ngạc nhiên khi lần đầu biết về điều này. Một cơ sở dữ liệu Postgres lẽ ra phải biết mọi thứ về những gì nằm trong các bảng của nó chứ, phải không? Việc đó có thể khó đến mức nào cơ chứ?

Hóa ra là: cực kỳ khó. Trên thực tế, một tác vụ cụ thể mà trình tối ưu hóa truy vấn cần thực hiện, đó là sắp xếp thứ tự join (join ordering), được biết đến là một bài toán NP-hard.

Vì vậy, các trình tối ưu hóa truy vấn rất khó. Điều không khó bằng là xác minh xem một kế hoạch truy vấn (query plan) mà trình tối ưu hóa chọn có tốt hay không. Nói một cách đơn giản, một trình tối ưu hóa truy vấn tốt sẽ tạo ra các kế hoạch chạy nhanh, và một trình tối ưu hóa tồi sẽ tạo ra các kế hoạch chạy chậm. Các mô hình ngôn ngữ đặc biệt giỏi trong việc học cách thực hiện các tác vụ với kết quả đầu ra dễ xác minh. Bởi vì chỉ có một trục duy nhất để tối ưu hóa—thời gian thực thi truy vấn—nên vấn đề được quy giản một cách tuyệt vời về việc củng cố các hành vi hướng dẫn mô hình tạo ra các kế hoạch truy vấn nhanh hơn.

Sau đây là phân tích về một thử nghiệm mà tôi đã thực hiện để khám phá câu hỏi: liệu một mô hình nhỏ, có trọng số mở (open-weights) có thể được hậu đào tạo (post-trained) thông qua tinh chỉnh có giám sát (SFT) và học tăng cường tác tử (agentic RL) để tạo ra các kế hoạch truy vấn Postgres vượt trội hơn các kế hoạch mặc định của Postgres hay không?

Câu trả lời cho câu hỏi của chúng tôi là một lời khẳng định chắc nịch. Các điểm nổi bật bao gồm:

Hãy bắt đầu từ đầu.

Bên trong một trình tối ưu hóa truy vấn

Hãy xem xét lát cắt sau của tập dữ liệu IMDb:

Giả sử tôi đang cố gắng trả lời câu hỏi: “Những công ty Nhật Bản nào đã phát hành nhiều tựa phim nhất trong những năm 2000?” Chúng ta có thể viết truy vấn sau:

Chạy truy vấn này sẽ xuất ra 10 công ty Nhật Bản cùng với số lượng tựa phim mà họ liên quan trong khoảng thời gian từ năm 2000 đến 2009, được sắp xếp từ cao xuống thấp.

Nhưng làm thế nào Postgres có được những kết quả này?

Con đường mà Postgres thực hiện để lấy dữ liệu này cho chúng ta không phải là một kết luận đã định trước, và nó liên quan mật thiết đến những gì chúng ta gọi là các vị ngữ chọn lọc (selective predicates) (tức là các điều kiện lọc trong mệnh đề WHERE).

Để minh họa điều này, hãy tưởng tượng cùng một truy vấn đó nhưng không có bộ lọc công ty Nhật Bản hoặc bộ lọc phạm vi ngày:

mc chỉ có thể join với cn thông qua mc.company_id = cn.id, và t chỉ có thể join với mc thông qua t.id = mc.movie_id.

Những ràng buộc này tạo ra hai cây join hợp lệ. (Về mặt kỹ thuật có tám cây join nếu chúng ta tính đến tính giao hoán. Trong trường hợp này, chúng ta không tính vì nó không ảnh hưởng đến kích thước của các quan hệ thu được từ các phép join).

⋈ ⋈ t cn mc (cn ⋈ mc) ⋈ t ⋈ ⋈ cn t mc (t ⋈ mc) ⋈ cn

Cardinality (số lượng phần tử) của một bảng hoặc kết quả truy vấn là số lượng hàng mà nó chứa. Giả sử các bảng liên quan có cardinality như sau:

Có tính đến các phép join của chúng ta, chúng ta có các cardinality sau:

Bất kể thứ tự của ba bảng này được join như thế nào, cùng một lượng 2 triệu hàng luôn được chuyển vào phép join thứ hai.

Bây giờ hãy thêm lại các vị ngữ chọn lọc của chúng ta:

Thứ tự join đầu tiên lọc 2 triệu mục movie_companies xuống còn 5% lát cắt các công ty là của Nhật Bản. Giả sử phân phối đồng nhất (chúng ta sẽ thảo luận sau tại sao lại giả định điều này), phép join này dẫn đến khoảng 100 nghìn hàng. Việc join kết quả với bảng title đã lọc sẽ chỉ giữ lại 20% số hàng đó từ những năm 2000.

Thứ tự join thứ hai lọc 2 triệu mục movie_companies xuống còn 20% lát cắt các tựa phim được thực hiện trong những năm 2000. Giả định về tính đồng nhất tương tự được áp dụng, vì vậy phép join đầu tiên dẫn đến 400 nghìn hàng, nghĩa là chúng ta đang chuyển 400 nghìn hàng vào phép join thứ hai.

Chúng ta thực hiện khối lượng công việc gấp 4 lần nếu chọn thứ tự join thứ hai.

Thật không may, nó không dừng lại ở đó.

Sự bùng nổ tổ hợp

Mỗi phép join có thể sử dụng bất kỳ cách nào trong số:

Bây giờ tính đến tính giao hoán (mặc dù tính giao hoán không làm thay đổi số lượng hàng được tạo ra, nhưng nó phải được xem xét vì nó ảnh hưởng đến hiệu suất liên quan đến thuật toán join được sử dụng), có 4 hướng join ngoài/trong khác nhau, dẫn đến 8 tổ hợp có thể xảy ra:

(cn⋈mc)⋈t(cn \bowtie mc) \bowtie t t⋈(cn⋈mc)t \bowtie (cn \bowtie mc)

(mc⋈cn)⋈t(mc \bowtie cn) \bowtie t t⋈(mc⋈cn)t \bowtie (mc \bowtie cn)

(t⋈mc)⋈cn(t \bowtie mc) \bowtie cn cn⋈(t⋈mc)cn \bowtie (t \bowtie mc)

(mc⋈t)⋈cn(mc \bowtie t) \bowtie cn cn⋈(mc⋈t)cn \bowtie (mc \bowtie t)

Cuối cùng, mỗi bảng có thể được quét theo những cách khác nhau. Chỉ xét bốn loại quét:

Có 4.608 cách khác nhau để chạy truy vấn này (Đây thực sự là một con số thấp hơn thực tế. Các kế hoạch có thể chạy song song, các tập hợp có thể được băm hoặc sắp xếp, v.v.).

Cũng cần lưu ý rằng Postgres không đánh giá tất cả các kế hoạch này. Nó sử dụng quy hoạch động (và thuật toán di truyền cho các truy vấn liên quan đến 12+ phép join) để cắt tỉa không gian tìm kiếm.

Tệ hơn nữa, mỗi phép join làm bùng nổ không gian tìm kiếm theo kiểu tổ hợp:

Ước tính, không phải đếm