Redesigning DuckDB's Sort, Again

DuckDB Labs · 2025 · 4. Điều chỉnh · Độ khó: Khó — bài gốc

Bài nhà cung cấp; benchmark trên một laptop M1 Max (10 luồng, 64 GB) do chính tác giả chạy.

Bối cảnh

Thiết kế 2021 (DuckDB Labs 2021) chạy tốt, nhưng từ đó hash join và hash aggregation cũng được làm cho chạy vượt RAM bằng một layout trang tràn đĩa (spillable) mới tốt hơn. Sort còn dùng cách cũ, nên bốn năm sau họ viết lại sort trên nền chung đó.
Lựa chọn 2021 là cascade merge 2 chiều (nhanh trong RAM) chứ không phải k-way merge (ít I/O nhất khi vượt RAM, vốn là cách kinh điển).

Sort cục bộ mỗi luồng: vẫn chuẩn hoá khoá; so sánh số nguyên tĩnh; iterator đi qua các trang không liền nhau (trang 256 KiB) để tạo run dài mà vẫn tràn đĩa từng trang chứ không "tất cả hoặc không". Kết hợp ba thuật toán: Vergesort phát hiện và gộp đoạn gần như đã sắp (dữ liệu chuỗi thời gian thường đã có thứ tự), không thấy mẫu thì Ska sort (radix MSD thích ứng trên 64 bit đầu của khoá), phân vùng quá nhỏ hoặc chưa đủ thì pdqsort.
Đổi sang k-way merge để giảm I/O khi vượt RAM. Không còn vật chất hoá toàn bộ kết quả gộp: xuất từng chunk đã sắp ngay cho pipeline sau, và LIMIT có thể dừng gộp bất cứ lúc nào.
K-way Merge Path: các thuật toán gộp song song chống lệch (Merge Path, bitonic) đều cho gộp 2 chiều; họ tổng quát một luận văn cử nhân năm 2014 cho k run: tính điểm cắt sao cho mỗi chunk đầu ra có kích thước chọn trước, rồi các luồng gộp độc lập và xuất song song nhờ cơ chế giữ thứ tự sẵn có.

Số nguyên 1 tỉ dòng: đã sắp tăng 15,3 → 1,5 giây (khoảng 10 lần), ngẫu nhiên 17,6 → 6,5 giây (khoảng 2,7 lần).
Bảng rộng (lineitem TPC-H, 15 cột): SF100 với giới hạn 30 GB (không vừa RAM) 274 → 81 giây (hơn 3 lần); SF1 và SF10 khoảng 2 lần.

Một thiết kế tốt có thể phải làm lại khi phần còn lại của hệ thống tiến lên (layout tràn đĩa chung); dùng chung nền tảng giữa các toán tử đáng hơn tối ưu riêng lẻ.
Đánh đổi của 2021 (nhanh trong RAM, nhiều I/O khi tràn) đảo chiều khi vượt RAM trở thành trường hợp thường gặp.
Thuật toán thích ứng với dữ liệu đã có thứ tự cho lợi ích lớn trên dữ liệu thật.