Hvordan skriver jeg en joinforbindelse med disse usædvanlige matchkriterier?

Indeks

Opret indekser på x.id og y.id - som du sandsynligvis allerede har, hvis det er dine primære nøgler.
Et indeks med flere kolonner kan også hjælpe, især med kun indeksscanninger på side 9.2+:

CREATE INDEX y_mult_idx ON y (id DESC, val)

I mine test blev dette indeks dog ikke brugt i starten. Var nødt til at tilføje (ellers meningsløst) val til ORDER BY at overbevise forespørgselsplanlæggeren om, at sorteringsrækkefølgen matcher. Se forespørgsel 3 .

Indekset gør ringe forskel i denne syntetiske opsætning. Men for tabeller med flere kolonner, henter val fra bordet bliver stadig dyrere, hvilket gør det "dækkende" indeks mere attraktivt.

Forespørgsler

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

Mere forklaring på teknikken med DISTINCT i dette relaterede svar:

• Vælg først række i hver GRUPPE FOR gruppe?

Jeg kørte nogle test, fordi jeg havde min mistanke om, at den første forespørgsel ikke ville skalere godt. Det er hurtigt med et lille bord, men ikke godt med større borde. Postgres optimerer ikke planen og starter med en (begrænset) krydsforbindelse med en pris på O(N²) .

2) Hurtigt

Denne forespørgsel er stadig ret enkel og skalerer fremragende:

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;

Vinduesfunktionen lead() er instrumentel. Jeg gør brug af muligheden for at give en standard til at dække hjørnekassen i den sidste række:2147483647 er det størst mulige heltal . Tilpas til din datatype.

3) Meget enkel og næsten lige så hurtig

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

Normalt korrelerede underforespørgsler tendens til at være langsom. Men denne kan bare vælge en værdi fra det (dækkende) indeks og er ellers så simpel, at den kan konkurrere.

Den ekstra ORDER BY element val (fed fremhævelse) virker meningsløst. Men tilføjelsen overbeviser forespørgselsplanlæggeren om, at det er ok at bruge flerkolonneindekset y_mult_idx ovenfra, fordi sorteringsrækkefølgen stemmer overens. Bemærk

i EXPLAIN output.

Testcase

Efter en livlig debat og flere opdateringer samlede jeg alle forespørgsler, der er postet indtil videre, og lavede en testcase for et hurtigt overblik. Jeg bruger kun 1000 rækker, så SQLfiddle stopper ikke med de langsommere forespørgsler. Men top 4 (Erwin 2, Clodoaldo, a_horse, Erwin 3) skaleres lineært i alle mine lokale test. Opdateret endnu en gang for at inkludere min seneste tilføjelse, forbedre format og rækkefølge efter ydeevne nu:

Big SQL Fiddle sammenligne ydeevne.