Bagaimana cara menulis gabungan dengan kriteria pencocokan yang tidak biasa ini?

Indeks

Buat indeks di x.id dan y.id - yang mungkin sudah Anda miliki jika itu adalah kunci utama Anda.
Indeks multi-kolom juga dapat membantu, terutama dengan pemindaian indeks saja di hal 9.2+:

CREATE INDEX y_mult_idx ON y (id DESC, val)

Namun, dalam pengujian saya, indeks ini tidak digunakan pada awalnya. Harus menambahkan (jika tidak, tidak ada gunanya) val untuk ORDER BY untuk meyakinkan perencana kueri bahwa urutan pengurutan cocok. Lihat kueri 3 .

Indeks membuat sedikit perbedaan dalam pengaturan sintetis ini. Tetapi untuk tabel dengan lebih banyak kolom, ambil val dari tabel menjadi semakin mahal, membuat indeks "penutup" lebih menarik.

Permintaan

1) Sederhana

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.

Penjelasan lebih lanjut untuk teknik ini dengan DISTINCT dalam jawaban terkait ini:

• Pilih dulu baris di setiap grup GROUP BY?

Saya menjalankan beberapa tes karena saya curiga bahwa kueri pertama tidak dapat diskalakan dengan baik. Cepat dengan meja kecil, tapi tidak bagus dengan meja yang lebih besar. Postgres tidak mengoptimalkan paket dan dimulai dengan gabungan silang (terbatas), dengan biaya O(N²) .

2) Cepat

Kueri ini masih agak sederhana dan skalanya sangat baik:

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;

Fungsi jendela lead() bersifat instrumental. Saya menggunakan opsi untuk memberikan default untuk menutupi kasus sudut dari baris terakhir:2147483647 adalah bilangan bulat terbesar . Sesuaikan dengan tipe data Anda.

3) Sangat sederhana dan hampir secepat

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

Biasanya, subkueri berkorelasi cenderung lambat. Tapi yang ini hanya bisa memilih nilai dari indeks (penutup) dan sebaliknya sangat sederhana sehingga bisa bersaing.

Tambahan ORDER BY item val (penekanan tebal) tampaknya tidak ada gunanya. Tetapi menambahkannya meyakinkan perencana kueri bahwa boleh saja menggunakan indeks multi-kolom y_mult_idx dari atas, karena urutannya cocok. Perhatikan

di EXPLAIN keluaran.

Kasus uji

Setelah debat yang hidup dan beberapa pembaruan, saya mengumpulkan semua pertanyaan yang diposting sejauh ini dan membuat kasus uji untuk tinjauan singkat. Saya hanya menggunakan 1000 baris sehingga SQLfiddle tidak kehabisan waktu dengan kueri yang lebih lambat. Tetapi 4 teratas (Erwin 2, Clodoaldo, a_horse, Erwin 3) skala secara linier di semua pengujian lokal saya. Diperbarui sekali lagi untuk memasukkan tambahan terbaru saya, tingkatkan format dan urutan berdasarkan kinerja sekarang:

Big SQL Fiddle membandingkan kinerja.