Hur skriver jag en anslutning med dessa ovanliga matchningskriterier?

Indeks

Skapa index på x.id och y.id - vilket du förmodligen redan har om det är dina primärnycklar.
Ett index med flera kolumner kan också hjälpa, särskilt med endast indexsökningar på sidan 9.2+:

CREATE INDEX y_mult_idx ON y (id DESC, val)

Men i mina tester användes inte detta index först. Var tvungen att lägga till (annars meningslöst) val till ORDER BY för att övertyga frågeplaneraren om att sorteringsordningen matchar. Se fråga 3 .

Indexet gör liten skillnad i denna syntetiska uppsättning. Men för tabeller med fler kolumner, hämta val från bordet blir allt dyrare, vilket gör det "täckande" indexet mer attraktivt.

Frågor

1) Enkel

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-fiol.

Mer förklaring till tekniken med DISTINCT i detta relaterade svar:

Välj först rad i varje GROUP BY-grupp?

Jag körde några tester eftersom jag hade mina misstankar om att den första frågan inte skulle skalas bra. Det är snabbt med ett litet bord, men inte bra med större bord. Postgres optimerar inte planen och börjar med en (begränsad) korskoppling, med en kostnad på O(N²) .

2) Snabbt

Den här frågan är fortfarande ganska enkel och skalas utmärkt:

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;

Fönsterfunktionen lead() är instrumentell. Jag använder alternativet för att tillhandahålla en standard för att täcka hörnet på den sista raden:2147483647 är det största möjliga heltal . Anpassa till din datatyp.

3) Mycket enkelt och nästan lika snabbt

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

Normalt korrelerade underfrågor tenderar att vara långsam. Men den här kan bara välja ett värde från (täckande) indexet och är annars så enkel att den kan konkurrera.

Den ytterligare ORDER BY objekt val (fet betoning) verkar meningslöst. Men att lägga till det övertygar frågeplaneraren att det är ok att använda flerkolumnsindexet y_mult_idx från ovan, eftersom sorteringsordningen matchar. Observera

i EXPLAIN utdata.

Testfall

Efter en livlig debatt och flera uppdateringar samlade jag alla frågor som postats hittills och gjorde ett testfall för en snabb överblick. Jag använder bara 1000 rader så SQLfiddle tar inte timeout med de långsammare frågorna. Men topp 4 (Erwin 2, Clodoaldo, a_horse, Erwin 3) skalas linjärt i alla mina lokala tester. Uppdaterad igen för att inkludera mitt senaste tillägg, förbättra format och ordning efter prestanda nu:

Big SQL Fiddle jämföra prestanda.