Union-find chỉ là đi lên gốc cây parent, đơn giản mà? Tôi đo thử: thiếu nén đường và union by rank, cây suy biến thành chuỗi và find thành O(n) — 28.368 ns/find. Thêm hai tối ưu, mỗi thao tác còn 3,8 ns, gần O(1) (α(n) — Ackermann ngược), nhanh hơn cả O(log n).
Cùng một đoạn code, cùng những con số, chỉ khác mảng được sắp trước hay chưa: bản chưa sắp chạy 660 ms, bản đã sắp 379 ms — chênh 1,7 lần. Không phải ít phép tính hơn, không phải cache. Thủ phạm là dự đoán nhánh của CPU, thứ big-O không hề thấy. Viết không nhánh xóa hẳn (183 ms). Tôi đo.
VACUUM dọn 20000 dead tuple về 0 nhưng bảng vẫn đúng 712kB — nó đánh dấu chỗ trống để tái dùng chứ không trả đĩa. Tôi tưởng VACUUM hỏng vì nhìn kích thước file, hóa ra phải nhìn n_dead_tup. VACUUM FULL mới nén còn 8kB nhưng khóa bảng — hai lệnh gần tên mà khác hẳn tác động.
Lần đọc đầu là shared read (nạp trang), lần sau thành shared hit (từ RAM). Nhưng một seq scan bảng lớn KHÔNG vào cache dù bảng nhỏ hơn shared_buffers — vì ring buffer cố ý bảo vệ cache khỏi bị một lần quét lớn xóa sạch. Tôi tưởng 'chạy lại luôn nhanh hơn', hóa ra đó không phải luật tự nhiên.
Truy vấn chọn lọc (1% hàng) dùng index nhanh 4,7 lần; nhưng trên cột boolean 50% hàng, planner bỏ index chọn seq scan. Tôi tưởng 'có index thì phải dùng index'. Index chỉ giúp khi truy vấn trả về ít hàng — và một index chết còn âm thầm làm chậm mọi lần ghi.
Trên hai cột trùng nhau, planner đoán 99 hàng còn thực tế 10000 — lệch 100 lần. 'rows' của EXPLAIN là ước lượng (không chạy), 'actual rows' của EXPLAIN ANALYZE mới là đo thật (có chạy). Chính khoảng cách giữa hai con số tố cáo planner đang đoán mù — và EXPLAIN ANALYZE chạy thật cả UPDATE/DELETE.