Jointures latérales

(sujet mis à jour avec la version 10)

Les 8 champions...le top du top !

      L’affaire est d'importance. Le clan des Géants des Pierres des Monts du Vieil Arbre a reçu une convocation pour le grand concours des lanceurs de rocs organisé chaque décade par le clan des Ogres-Mages d’Astragor. Les Géants se relaient en permanence, passant leur journée à lancer des blocs spécialement taillés de 637kg à plusieurs centaines de mètres dans la Vallée des Ecrasés, les écrasés étant les voyageurs ne connaissant pas la tradition du clan. Le Scribe Margiono, un gobelin mineur ayant été l’apprenti du Sage Marifel, grave scrupuleusement les résultats relevés au centimètre près par son corbeau. Oumpfor le Chef ordonne donc à Margiono de lui trouver les 8 meilleurs parmi les membres du clan, à savoir les Géants ayant réalisé les meilleures performances en considérant les plus récentes en cas d’égalité. Oumfor précise qu’il veut des membres actifs car les Géants sont un peu turbulents, se battent entre eux et une partie non négligeable du clan est en permanence sur le flanc.
      Margiono s’exécute, tentant d’abord une approche classique, aidé par Vincent :

postgres=# select version(); version ------------------------------------------------------------- PostgreSQL 9.5.1, compiled by Visual C++ build 1800, 64-bit (1 ligne) create table geants(idg smallint, nmg character varying(128), actif boolean, idg_chef smallint); CREATE TABLE insert into geants(idg, nmg, actif, idg_chef) values (1, 'Oumpfor', true, null), (2, 'Galdor', false, 7), (3, 'Goldar', false, 7), (4, 'Goldur', true, 7), (5, 'Guldor', false, 7), (6, 'Geldor', false, 7), (7, 'Golder', false, 8), (8, 'Gildir', true, 1), (9, 'Ambact', true, 1), (10, 'Amdas', false, 1), (11, 'Baldor', false, 8), (12, 'Boldar', false, 8), (13, 'Boldur', false, 8), (14, 'Buldor', false, 8), (15, 'Daldor', false, 16), (16, 'Doldar', true, 18), (17, 'Doldur', false, 18), (18, 'Duldor', false, 1), (19, 'Faldor', false, 20), (20, 'Foldar', false, 21), (21, 'Foldur', false, 1), (22, 'Haldor', false, 23), (23, 'Holdar', true, 24), (24, 'Holdur', true, 25), (25, 'Huldor', false, 26), (26, 'Heldor', false, 8), (27, 'Caldor', false, 28), (28, 'Coldar', false, 31), (29, 'Coldur', false, 30), (30, 'Culdor', false, 31), (31, 'Celdor', false, 1), (32, 'Polder', false, 33), (33, 'Pildir', false, 1), (34, 'Faldor', false, 37), (35, 'Foldar', false, 37), (36, 'Foldur', false, 37), (37, 'Fuldor', false, 1), (38, 'Maldor', true, 100), (39, 'Moldar', false, 100), (40, 'Moldur', true, 100), (41, 'Muldor', false, 100), (42, 'Meldor', true, 100), (43, 'Molder', false, 100), (44, 'Mildir', true, 100), (45, 'Naldor', true, 100), (46, 'Noldar', false, 100), (47, 'Noldur', true, 100), (48, 'Nuldor', false, 100), (49, 'Neldor', true, 100), (50, 'Nolder', false, 100), (51, 'Mildir', true, 100), (52, 'Ambas', true, 1), (53, 'Amcas', false, 1), (100, 'Tork', true, 1); INSERT 0 54 create unique index geants_i1 on geants(idg, actif); CREATE INDEX create table lancers(dtl timestamp, idg smallint, perf integer); CREATE TABLE do $$ begin for i in reverse 576000..1 loop insert into lancers(dtl, idg, perf) values(current_timestamp - (i || ' minutes')::interval, trunc(random() * 100 + 1), case when random() <= 0.0001 then 50000 + trunc(random() * 50000 + 1) else trunc(random() * 50000 + 1)end); end loop; end$$; DO create index lancers_i1 on lancers(idg); CREATE INDEX create index lancers_i2 on lancers(perf, dtl); CREATE INDEX explain select l.idg, l.dtl, l.perf from lancers l join (select g.idg idg, max(l.perf) perf from geants g join lancers l on (g.idg = l.idg) where g.actif = 't' group by g.idg) perf_max on (l.idg = perf_max.idg and l.perf = perf_max.perf) order by 3 desc, 2 desc limit 8; QUERY PLAN ------------------------------------------------------------------------------------------------- Limit (cost=13362.90..13362.91 rows=2 width=14) -> Sort (cost=13362.90..13362.91 rows=2 width=14) Sort Key: l.perf DESC, l.dtl DESC -> Nested Loop (cost=12509.07..13362.89 rows=2 width=14) -> HashAggregate (cost=12504.55..12504.72 rows=17 width=6) Group Key: g.idg -> Hash Join (cost=1.75..12014.95 rows=97920 width=6) Hash Cond: (l_1.idg = g.idg) -> Seq Scan on lancers l_1 (cost=0.00..8874.00 rows=576000 width=6) -> Hash (cost=1.54..1.54 rows=17 width=2) -> Seq Scan on geants g (cost=0.00..1.54 rows=17 width=2) Filter: actif -> Bitmap Heap Scan on lancers l (cost=4.52..50.46 rows=1 width=14) Recheck Cond: (perf = (max(l_1.perf))) Filter: (g.idg = idg) -> Bitmap Index Scan on lancers_i2 (cost=0.00..4.51 rows=12 width=0) Index Cond: (perf = (max(l_1.perf))) (17 lignes) select l.idg, l.dtl, l.perf from lancers l join (select g.idg idg, max(l.perf) perf from geants g join lancers l on (g.idg = l.idg) where g.actif = 't' group by g.idg) perf_max on (l.idg = perf_max.idg and l.perf = perf_max.perf) order by 3 desc, 2 desc limit 8; idg | dtl | perf -----+----------------------------+------- 42 | 2016-03-10 14:47:14.526144 | 97234 1 | 2016-01-01 17:21:14.526144 | 94390 4 | 2016-02-07 04:33:14.526144 | 87232 47 | 2015-07-24 13:06:14.526144 | 76053 40 | 2015-12-19 16:26:14.526144 | 73702 100 | 2015-11-02 16:16:14.526144 | 59483 23 | 2015-07-17 15:54:14.526144 | 57900 8 | 2016-06-13 01:55:14.526144 | 50000 (8 lignes) Temps : 313,086 ms Temps : 319,336 ms Temps : 385,451 ms

      Pas mal mais cette requête semble lente. Margiono se demande si une indexation différente pourrait donner de meilleures performances. Il sait en effet qu’Oumpfor n’espt pas spécialement patient. Mais avant de réindexer, ce qui est toujours coûteux, il décide de tenter d’utiliser les possibilités offertes par SQL-1999 et les jointures LATÉRALES. PostgreSQL permet en effet de réaliser ce type de jointure depuis la version 9.3.

explain select g.idg, g.nmg, l.dtl, l.perf from (select idg, nmg from geants where actif = true) g join lateral (select perf, dtl from lancers where g.idg = idg order by perf desc, dtl desc fetch first 1 rows only) l on (true) order by perf desc, dtl desc fetch first 8 rows only; QUERY PLAN ------------------------------------------------------------------------------------------------------------------- Limit (cost=102.17..102.19 rows=8 width=20) -> Sort (cost=102.17..102.21 rows=17 width=20) Sort Key: lancers.perf DESC, lancers.dtl DESC -> Nested Loop (cost=0.42..101.83 rows=17 width=20) -> Seq Scan on geants (cost=0.00..1.54 rows=17 width=8) Filter: actif -> Limit (cost=0.42..5.88 rows=1 width=12) -> Index Scan Backward using lancers_i2 on lancers (cost=0.42..31416.42 rows=5760 width=12) Filter: (geants.idg = idg) (9 lignes) select g.idg, g.nmg, l.dtl, l.perf from (select idg, nmg from geants where actif = true) g join lateral (select perf, dtl from lancers where g.idg = idg order by perf desc, dtl desc fetch first 1 rows only) l on (true) order by perf desc, dtl desc fetch first 8 rows only; idg | nmg | dtl | perf -----+---------+----------------------------+------- 42 | Meldor | 2016-03-10 14:47:14.526144 | 97234 1 | Oumpfor | 2016-01-01 17:21:14.526144 | 94390 4 | Goldur | 2016-02-07 04:33:14.526144 | 87232 47 | Noldur | 2015-07-24 13:06:14.526144 | 76053 40 | Moldur | 2015-12-19 16:26:14.526144 | 73702 100 | Tork | 2015-11-02 16:16:14.526144 | 59483 23 | Holdar | 2015-07-17 15:54:14.526144 | 57900 8 | Gildir | 2016-06-13 01:55:14.526144 | 50000 (8 lignes) Temps : 3,904 ms Temps : 4,736 ms Temps : 3,594 ms

      Bonne pioche de la part de Margiono. PostgreSQL estimait que le coût du plan de la requête utilisant LATERAL serait largement inférieur à celui du plan de la requête "classique". Et, à l’exécution, les temps de réponse oternus se sont en effet révélés être largement meilleurs.
      Qu’apporte ce type de jointure par rapport à une jointure habituelle ? Le mot clé LATERAL autorise ici à faire référence à une colonne de geants dans la sous-requête effectuée sur la table lancers. Il s’agit donc de fait d’une boucle de type FOR EACH. Pour chaque géant actif, nous cherchons la meilleure performance et la date à laquelle elle a été réalisée via l’index lancers_i2 : c’est bien le fait de limiter le jeu de résultats de la sous-requête à la "top perf" de chaque géant qui rend ici la jointure latérale si efficace.

Mise à jour : 18/06/2016