Grouper, fenêtrer
Le grand chef Ompfor demande à Margiono quelques informations sur les lancers de cailloux effectués depuis 2019. Il veut obtenir pour chaque géant :
- la performance maximale
- la performance maximale réalisée par son clan
- le nombre de lancers effectués
- le nombre de lancers effectués par son clan
- le nombre de géants différents ayant lancé pour son clan
Le scribe utilise PostgreSQL pour stocker les données et sait tirer parti des fonctionnalités analytiques de ce SGBD. Le contexte, une table mère geants et une table fille lancers. Cadre commun de la démonstration avec PostgreSQL 11 :
select version();
version
----------------------------------------------------------------------------------------------------------------------------------
PostgreSQL 11.2 (Ubuntu 11.2-2.pgdg18.04+1) on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0, 64-bit
create table geants(idge integer generated by default as identity primary key, idcl smallint, dtn timestamp, taille smallint, devise varchar(128), dicton varchar(128), berserk boolean);
CREATE TABLE
with recursive serie(i) as
(select 1
UNION ALL
select i + 1 from serie where i < 1000)
insert into geants(idcl, dtn, taille, devise, dicton, berserk)
select
least(random()*10, random()*10),
current_date - 3650 - trunc(random() * 10000 + 1)::int,
200 + (trunc(random() * 200 + 1)),
upper(md5(random()::text)),upper(md5(random()::text)),
case when random() < 0.001 then true else false end
from serie;
INSERT 0 1000
create table lancers (idge integer references geants(idge), dtl timestamp, perf integer );
CREATE TABLE
insert into lancers(dtl, idge, perf) with recursive serie(i) as (select 1 UNION ALL select i + 1 from serie where i < 10000000)
select clock_timestamp() - ((i || ' minutes')::interval)::interval, trunc(random() * 1000 + 1), trunc(random() * 100000 + 1) from serie;
INSERT 0 10000000
create unique index on lancers(idge, dtl);
CREATE INDEX
create index on lancers using brin(dtl);
CREATE INDEX
\d+
Liste des relations
Schéma | Nom | Type | Propriétaire | Taille | Description
----------+-----------------+----------+--------------+------------+-------------
postgres | geants | table | postgres | 144 kB |
postgres | geants_idge_seq | séquence | postgres | 8192 bytes |
postgres | lancers | table | postgres | 498 MB |
\di+
Liste des relations
Schéma | Nom | Type | Propriétaire | Table | Taille | Description
----------+----------------------+-------+--------------+---------+--------+-------------
postgres | geants_pkey | index | postgres | geants | 40 kB |
postgres | lancers_dtl_idx | index | postgres | lancers | 56 kB |
postgres | lancers_idge_dtl_idx | index | postgres | lancers | 301 MB |
Dans un premier temps, Margiono choisit de tout traiter avec des fonctions analytiques appliquées sur des fenêtres ad-hoc :
explain
with travail as(
select
l.idge,
g.idcl,
max(perf) over par_geant pmag,
max(perf) over par_clan pmac,
count(1) over par_geant nblg,
count(1) over par_clan nblc,
dense_rank() over par_clan_ord_geant rgc
from
geants g join lancers l on (g.idge = l.idge)
where dtl >= date '2019-01-01'
window par_geant as (partition by l.idge), par_clan as (partition by g.idcl), par_clan_ord_geant as (par_clan order by l.idge)
)
select distinct
idge,
idcl,
pmag,
pmac,
nblg,
nblc,
max(rgc) over par_clan nbgc
from travail
window par_clan as (partition by idcl)
order by idge;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------
Sort (cost=147845.79..147888.97 rows=17270 width=38)
Sort Key: travail.idge
CTE travail
-> WindowAgg (cost=118482.54..121936.48 rows=172697 width=38)
-> Sort (cost=118482.54..118914.29 rows=172697 width=34)
Sort Key: g.idcl, l.idge
-> WindowAgg (cost=100005.79..103459.73 rows=172697 width=34)
-> Sort (cost=100005.79..100437.53 rows=172697 width=22)
Sort Key: g.idcl
-> WindowAgg (cost=81529.04..84982.98 rows=172697 width=22)
-> Sort (cost=81529.04..81960.78 rows=172697 width=10)
Sort Key: l.idge
-> Hash Join (cost=96.96..66506.23 rows=172697 width=10)
Hash Cond: (l.idge = g.idge)
-> Bitmap Heap Scan on lancers l (cost=59.46..66013.47 rows=172697 width=8)
Recheck Cond: (dtl >= '2019-01-01'::date)
-> Bitmap Index Scan on lancers_dtl_idx (cost=0.00..16.29 rows=180721 width=0)
Index Cond: (dtl >= '2019-01-01'::date)
-> Hash (cost=25.00..25.00 rows=1000 width=6)
-> Seq Scan on geants g (cost=0.00..25.00 rows=1000 width=6)
-> HashAggregate (cost=24521.15..24693.85 rows=17270 width=38)
Group Key: travail.idge, travail.idcl, travail.pmag, travail.pmac, travail.nblg, travail.nblc, max(travail.rgc) OVER (?)
-> WindowAgg (cost=18476.75..21498.95 rows=172697 width=38)
-> Sort (cost=18476.75..18908.49 rows=172697 width=38)
Sort Key: travail.idcl
-> CTE Scan on travail (cost=0.00..3453.94 rows=172697 width=38)
with travail as(
select
l.idge,
g.idcl,
max(perf) over par_geant pmag,
max(perf) over par_clan pmac,
count(1) over par_geant nblg,
count(1) over par_clan nblc,
dense_rank() over par_clan_ord_geant rgc
from
geants g join lancers l on (g.idge = l.idge)
where dtl >= date '2019-01-01'
window par_geant as (partition by l.idge), par_clan as (partition by g.idcl), par_clan_ord_geant as (par_clan order by l.idge)
)
select distinct
idge,
idcl,
pmag,
pmac,
nblg,
nblc,
max(rgc) over par_clan nbgc
from travail
window par_clan as (partition by idcl)
order by idge;
...
Temps : 461,906 ms
Temps : 438,800 ms
Temps : 466,975 ms
Pas trop mal, la requête de Margiono bénéficie du minuscule index BRIN. Le scribe sait qu'il faut filtrer le plus tôt possible et a remonté le critère de date au niveau de la CTE (with query) en attendant l'arrivée de PostgreSQL 12.
Seulement, 0s5 c'est malgré tout un peu trop long pour avoir une impression de fluidité parfaite et Oumpfor fronce les sourcils.
Margiono se dit qu'il pourrait effectuer l'élimination des doublons au niveau de la CTE plutôt que dans la requête principale en remontant le distinct. Mais il imagine soudain une solution plus radicale : grouper ce qui peut l'être au niveau de la CTE avec la "vieille" instruction GROUP BY. Il compte ainsi réaliser le fenêtrage et appliquer les fonctions analytiques sur un jeu de résultats beaucoup plus réduit :
explain
with travail as(
select
l.idge,
g.idcl,
max(perf) pmag,
count(1) nblg,
dense_rank() over par_clan_ord_geant rgc
from
geants g join lancers l on (g.idge = l.idge)
where dtl >= date '2019-01-01'
group by l.idge, g.idcl
window par_clan_ord_geant as (partition by g.idcl order by l.idge)
)
select
idge,
idcl,
pmag,
max(pmag) over par_clan pmac,
nblg,
sum(nblg) over par_clan nblc,
max(rgc) over par_clan nbgc
from travail
window par_clan as (partition by idcl)
order by idge;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
Sort (cost=71245.86..71273.36 rows=11000 width=62)
Sort Key: travail.idge
CTE travail
-> WindowAgg (cost=69081.59..69301.59 rows=11000 width=26)
-> Sort (cost=69081.59..69109.09 rows=11000 width=18)
Sort Key: g.idcl, l.idge
-> HashAggregate (cost=68233.20..68343.20 rows=11000 width=18)
Group Key: l.idge, g.idcl
-> Hash Join (cost=96.96..66506.23 rows=172697 width=10)
Hash Cond: (l.idge = g.idge)
-> Bitmap Heap Scan on lancers l (cost=59.46..66013.47 rows=172697 width=8)
Recheck Cond: (dtl >= '2019-01-01'::date)
-> Bitmap Index Scan on lancers_dtl_idx (cost=0.00..16.29 rows=180721 width=0)
Index Cond: (dtl >= '2019-01-01'::date)
-> Hash (cost=25.00..25.00 rows=1000 width=6)
-> Seq Scan on geants g (cost=0.00..25.00 rows=1000 width=6)
-> WindowAgg (cost=958.39..1205.89 rows=11000 width=62)
-> Sort (cost=958.39..985.89 rows=11000 width=26)
Sort Key: travail.idcl
-> CTE Scan on travail (cost=0.00..220.00 rows=11000 width=26)
with travail as(
select
l.idge,
g.idcl,
max(perf) pmag,
count(1) nblg,
dense_rank() over par_clan_ord_geant rgc
from
geants g join lancers l on (g.idge = l.idge)
where dtl >= date '2019-01-01'
group by l.idge, g.idcl
window par_clan_ord_geant as (partition by g.idcl order by l.idge)
)
select
idge,
idcl,
pmag,
max(pmag) over par_clan pmac,
nblg,
sum(nblg) over par_clan nblc,
max(rgc) over par_clan nbgc
from travail
window par_clan as (partition by idcl)
order by idge;
...
Temps : 87,446 ms
Temps : 90,875 ms
Temps : 86,985 ms
Excellente pioche pour Margiono : le gain est très conséquent avec un facteur 5 entre le temps d'exécution de la première requête et de la seconde.
Il n'est bien sûr pas toujours simple ni même possible d'effectuer une telle réécriture. Tout dépend de ce qui est demandé mais "grouper avant de fenêtrer" peut être une bonne piste d'optimisation. Les tests ont ici été réalisés avec PostgreSQL 11 ; des tests effectués avec Oracle Database 11.2.0.4 et 19c montrent également des gains avec la deuxième écriture de la requête.
Mise à jour : 06/05/2019