Hoe schrijf ik een join met deze ongebruikelijke matching criteria?

Indices

Maak indices op x.id en y.id - die je waarschijnlijk al hebt als dat je primaire sleutels zijn.
Een index met meerdere kolommen kan ook helpen, vooral met alleen index scant op pagina 9.2+:

CREATE INDEX y_mult_idx ON y (id DESC, val)

In mijn tests werd deze index in eerste instantie echter niet gebruikt. Moest toevoegen (anders zinloos) val om ORDER BY om de queryplanner ervan te overtuigen dat de sorteervolgorde overeenkomt. Zie zoekopdracht 3 .

De index maakt weinig verschil in deze synthetische opstelling. Maar voor tabellen met meer kolommen, het ophalen van val van de tafel wordt steeds duurder, waardoor de "dekkingsindex" aantrekkelijker wordt.

Vragen

1) Eenvoudig

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.

Meer uitleg voor de techniek met DISTINCT in dit gerelateerde antwoord:

Selecteer eerst rij in elke GROUP BY-groep?

Ik heb wat tests uitgevoerd omdat ik mijn vermoedens had dat de eerste query niet goed zou schalen. Het is snel met een kleine tafel, maar niet goed met grotere tafels. Postgres optimaliseert het plan niet en begint met een (beperkte) cross join, met een kostprijs van O(N²) .

2) Snel

Deze query is nog steeds vrij eenvoudig en schaalt uitstekend:

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;

De vensterfunctie lead() instrumentaal is. Ik maak gebruik van de optie om een standaardwaarde op te geven om de hoek van de laatste rij te dekken:2147483647 is de grootst mogelijke integer . Aanpassen aan uw gegevenstype.

3) Heel eenvoudig en bijna net zo snel

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

Normaal gesproken gecorreleerde subquery's hebben de neiging traag te zijn. Maar deze kan gewoon een waarde kiezen uit de (dekkende) index en is verder zo eenvoudig dat hij kan concurreren.

De extra ORDER BY item val (vetgedrukte nadruk) lijkt zinloos. Maar het toevoegen ervan overtuigt de queryplanner dat het oké is om de index met meerdere kolommen y_mult_idx te gebruiken van boven, omdat de sorteervolgorde overeenkomt. Let op de

in de EXPLAIN uitvoer.

Testcase

Na een levendig debat en meerdere updates heb ik alle tot nu toe geposte vragen verzameld en een testcase gemaakt voor een snel overzicht. Ik gebruik slechts 1000 rijen, zodat SQLfiddle geen time-out heeft met de langzamere query's. Maar de top 4 (Erwin 2, Clodoaldo, a_horse, Erwin 3) schaalt lineair in al mijn lokale tests. Opnieuw bijgewerkt met mijn nieuwste toevoeging, nu het formaat en de volgorde op prestatie verbeterd:

Big SQL Fiddle prestaties vergelijken.