Indices
Créer des index sur x.id et y.id - que vous avez probablement déjà si ce sont vos clés primaires.
Un index multi-colonnes peut également être utile, en particulier avec analyses d'index uniquement
à la page 9.2+ :
CREATE INDEX y_mult_idx ON y (id DESC, val)
Cependant, dans mes tests, cet indice n'a pas été utilisé au départ. Il a fallu ajouter (sinon inutile) val à ORDER BY pour convaincre le planificateur de requêtes que l'ordre de tri correspond. Voir la requête 3 .
L'indice fait peu de différence dans cette configuration synthétique. Mais pour les tables avec plus de colonnes, récupérer val de la table devient de plus en plus cher, rendant l'indice "couvrant" plus attractif.
Requêtes
1) Simplicité
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;
Plus d'explications pour la technique avec DISTINCT dans cette réponse connexe :
J'ai effectué quelques tests parce que je soupçonnais que la première requête n'évoluerait pas bien. C'est rapide avec une petite table, mais pas bon avec de plus grandes tables. Postgres n'optimise pas le plan et commence par une jointure croisée (limitée), avec un coût de O(N²) .
2) Rapide
Cette requête est encore assez simple et s'adapte parfaitement :
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;
La fonction de fenêtre lead()
est instrumental. J'utilise l'option pour fournir une valeur par défaut pour couvrir le cas d'angle de la dernière ligne :2147483647 est le le plus grand entier possible
. Adaptez-vous à votre type de données.
3) Très simple et presque aussi rapide
SELECT x.id
,(SELECT val FROM y WHERE id <= x.id ORDER BY id DESC, val LIMIT 1) AS val
FROM x;Normalement, les sous-requêtes corrélées ont tendance à être lents. Mais celui-ci peut simplement choisir une valeur à partir de l'index (couvrant) et est par ailleurs si simple qu'il peut rivaliser.
Le ORDER BY supplémentaire article val (en gras) semble inutile. Mais l'ajouter convainc le planificateur de requêtes qu'il est correct d'utiliser l'index multi-colonnes y_mult_idx d'en haut, car l'ordre de tri correspond. Notez le
dans le EXPLAIN sortie.
Cas de test
Après un débat animé et de multiples mises à jour, j'ai rassemblé toutes les requêtes publiées jusqu'à présent et j'ai créé un cas de test pour un aperçu rapide. Je n'utilise que 1000 lignes pour que SQLfiddle n'expire pas avec les requêtes plus lentes. Mais le top 4 (Erwin 2, Clodoaldo, a_horse, Erwin 3) évolue de manière linéaire dans tous mes tests locaux. Mis à jour une fois de plus pour inclure mon dernier ajout, améliorer le format et trier par performance maintenant :
Grand violon SQL comparer les performances.
