Fastest Table Sort in the West – Redesigning DuckDB's Sort

DuckDB Labs · 2021 · 2. Tăng trưởng · Độ khó: Khó — bài gốc

Bài nhà cung cấp; benchmark do họ tự chạy. Phần sau: DuckDB Labs 2025 (thiết kế lại sau bốn năm).

Bối cảnh

Sort trong DB không phải sort một mảng số: sắp cả hàng (gồm các cột "payload" không nằm trong ORDER BY), theo nhiều cột, có chiều tăng/giảm và vị trí NULL. Bộ so sánh kiểu if/else cho mỗi hàng, cộng với lưu trữ cột, gây truy cập bộ nhớ ngẫu nhiên.
Mục tiêu: sort song song và sort được nhiều hơn RAM, hiệu năng tốt trong bộ nhớ và giảm dần mượt khi vượt bộ nhớ.

Chuẩn hoá khoá thành chuỗi nhị phân so được bằng memcmp (đảo bit theo chiều sắp, mã hoá NULL), nên dùng được radix sort trên byte.
Sort hai pha song song: mỗi luồng sort phần dữ liệu nó gom bằng radix sort; rồi cascade merge (mỗi lần gộp hai khối, hiệu quả trong bộ nhớ) thay vì k-way merge (ít I/O hơn, kiểu truyền thống cho sort ngoài). Khi số khối ít hơn số luồng, dùng Merge Path (tìm điểm cắt bằng tìm nhị phân) để nhiều luồng cùng gộp một cặp khối.
Chuyển cột sang hàng khi sort vì sắp lại cột payload từng cột một là truy cập ngẫu nhiên; việc chép đằng nào cũng phải làm. Dùng chung layout hàng với join và aggregation.
Ra đĩa nhờ buffer manager: chuỗi độ dài thay đổi nằm ở heap riêng nhưng xếp theo hàng; khi block bị đẩy ra đĩa, con trỏ trong hàng được đổi thành offset (pointer swizzling) để đọc lại được.
Predication: bỏ nhánh if/else trong vòng gộp để CPU không đoán sai nhánh.

Hiệu năng giảm mượt khi dữ liệu vượt RAM, tận dụng SSD; theo họ các hệ khác hoặc hết bộ nhớ mà chết, hoặc chuyển sang chiến lược sort ngoài chậm hơn nhiều.

Biến phép so sánh phức tạp thành memcmp trên khoá chuẩn hoá mở đường cho thuật toán nhanh hơn (radix).
Một máy được tận dụng triệt để (song song + tràn ra SSD có kiểm soát) đẩy xa thời điểm cần hệ phân tán.