Làm cách nào để viết một liên kết với tiêu chí kết hợp bất thường này?

Chỉ số

Tạo chỉ mục trên x.id và y.id - mà bạn có thể đã có nếu đó là khóa chính của bạn.
Chỉ mục nhiều cột cũng có thể hữu ích, đặc biệt là với chỉ quét chỉ mục trong trang 9.2+:

CREATE INDEX y_mult_idx ON y (id DESC, val)

Tuy nhiên, trong các thử nghiệm của tôi, chỉ số này lúc đầu không được sử dụng. Phải thêm (nếu không thì vô nghĩa) val đến ORDER BY để thuyết phục người lập kế hoạch truy vấn rằng thứ tự sắp xếp phù hợp. Xem truy vấn 3 .

Chỉ số tạo ra sự khác biệt nhỏ trong thiết lập tổng hợp này. Nhưng đối với các bảng có nhiều cột hơn, hãy truy xuất val khỏi bảng ngày càng trở nên đắt đỏ, khiến chỉ số "phủ sóng" trở nên hấp dẫn hơn.

Truy vấn

1) Đơn giản

SELECT DISTINCT ON (x.id)
       x.id, y.val
FROM   x
JOIN   y ON y.id <= x.id
ORDER  BY x.id, y.id DESC;

SQL Fiddle.

Giải thích thêm về kỹ thuật với DISTINCT trong câu trả lời có liên quan này:

Chọn trước hàng trong mỗi GROUP BY nhóm?

Tôi đã chạy một số bài kiểm tra vì tôi nghi ngờ rằng truy vấn đầu tiên sẽ không mở rộng quy mô tốt. Nó nhanh với một chiếc bàn nhỏ, nhưng không tốt với những chiếc bàn lớn hơn. Postgres không tối ưu hóa kế hoạch và bắt đầu với tham gia chéo (có giới hạn), với chi phí O(N²) .

2) Nhanh chóng

Truy vấn này vẫn khá đơn giản và quy mô xuất sắc:

SELECT x.id, y.val
FROM   x
JOIN  (SELECT *, lead(id, 1, 2147483647) OVER (ORDER BY id) AS next_id FROM y) y
       ON  x.id >= y.id
       AND x.id <  y.next_id
ORDER  BY 1;

Hàm window lead() là công cụ. Tôi sử dụng tùy chọn để cung cấp giá trị mặc định để che chữ hoa ở góc của hàng cuối cùng:2147483647 là số nguyên lớn nhất có thể . Điều chỉnh cho phù hợp với loại dữ liệu của bạn.

3) Rất đơn giản và gần như nhanh chóng

SELECT x.id
     ,(SELECT val FROM y WHERE id <= x.id ORDER BY id DESC, val LIMIT 1) AS val
FROM   x;

Thông thường, truy vấn phụ có tương quan có xu hướng chậm. Nhưng cái này chỉ có thể chọn một giá trị từ chỉ mục (bao hàm) và nếu không thì rất đơn giản để nó có thể cạnh tranh.

ORDER BY bổ sung item val (nhấn mạnh) dường như vô nghĩa. Nhưng việc thêm nó sẽ thuyết phục người lập kế hoạch truy vấn rằng bạn có thể sử dụng chỉ mục nhiều cột y_mult_idx từ phía trên, vì thứ tự sắp xếp phù hợp. Lưu ý

trong EXPLAIN đầu ra.

Trường hợp thử nghiệm

Sau một cuộc tranh luận sôi nổi và nhiều bản cập nhật, tôi đã thu thập tất cả các truy vấn được đăng cho đến nay và tạo một trường hợp thử nghiệm để có cái nhìn tổng quan nhanh chóng. Tôi chỉ sử dụng 1000 hàng để SQLfiddle không hết thời gian với các truy vấn chậm hơn. Nhưng top 4 (Erwin 2, Clodoaldo, a_horse, Erwin 3) chia tỷ lệ tuyến tính trong tất cả các bài kiểm tra cục bộ của tôi.

Big SQL Fiddle so sánh hiệu suất.