vendredi 27 août 2010

Postgresql et window functions

Les window functions de Postgresql permettent d'écrire des requêtes bien plus avancées, et ainsi de résoudre de nombreux problèmes complexes en pur SQL. Par exemple, prenons la table et les données suivantes:


create table historical(
id integer not null,
valid_from timestamp not null,
valid_to timestamp not null);

insert into historical values(1, '17-04-2010', '19-04-2010');
insert into historical values(1, '19-04-2010', '20-04-2010');
insert into historical values(1, '20-04-2010', '03-05-2010');
insert into historical values(1, '07-05-2010', '08-05-2010');
insert into historical values(1, '08-05-2010', '14-05-2010');
insert into historical values(2, '17-04-2010', '18-04-2010');
insert into historical values(2, '20-04-2010', '21-04-2010');
insert into historical values(2, '21-04-2010', '24-04-2010');
insert into historical values(2, '25-04-2010', '27-04-2010');
insert into historical values(2, '30-04-2010', '02-05-2010');
insert into historical values(2, '02-05-2010', '05-05-2010');


Pour une raison ou pour une autre, les données historiques ont été ajoutées sans essayer de les combiner avec l'existant, et l'on se retrouve donc avec bien plus de lignes que nécessaire dans la base. Ansi, les entrées du 17 au 19, du 19 au 20 et du 20 au 3 pourraient être représentées par une seule ligne, valide du 17 au 3. La question est: est-il possible d'écrire une requête SQL qui renvoie les données compactées?

Avec les window functions, oui!

L'idée est d'abord d'utiliser la fonction "lag", qui renvoie la valeur dans la table un certain nombre de lignes avant ou après, afin de comparer chaque ligne à la précédente. Si elle est différente, retournons 1, sinon, retournons 0:

select
id,
valid_from,
valid_to,
case when id = lag(id, 1)
over (order by id, valid_from, valid_to)
and valid_from = lag(valid_to, 1)
over (order by id, valid_from, valid_to)
then 0 else 1 end as agg
from historical
order by id, valid_from, valid_to

Cette requête nous renvoie une colonne supplémentaire, "agg", qui est à 0 lorsque la ligne pourrait être combinée avec la précédente.

1 2010-04-17 00:00:00 2010-04-19 00:00:00 1
1 2010-04-19 00:00:00 2010-04-20 00:00:00 0
1 2010-04-20 00:00:00 2010-05-03 00:00:00 0
1 2010-05-07 00:00:00 2010-05-08 00:00:00 1
1 2010-05-08 00:00:00 2010-05-14 00:00:00 0
2 2010-04-17 00:00:00 2010-04-18 00:00:00 1
2 2010-04-20 00:00:00 2010-04-21 00:00:00 1
2 2010-04-21 00:00:00 2010-04-24 00:00:00 0
2 2010-04-25 00:00:00 2010-04-27 00:00:00 1
2 2010-04-30 00:00:00 2010-05-02 00:00:00 1
2 2010-05-02 00:00:00 2010-05-05 00:00:00 0

Ceci fait, appelons maintenant la fonction "sum", pour renvoyer la somme courante des "agg", ce qui fournit un rang:

select id, valid_from, valid_to,
sum(agg) over (order by id, valid_from, valid_to) as ranked
from
(select
id,
valid_from,
valid_to,
case when id = lag(id, 1)
over (order by id, valid_from, valid_to)
and valid_from = lag(valid_to, 1)
over (order by id, valid_from, valid_to)
then 0 else 1 end as agg
from historical
order by id, valid_from, valid_to) as agg_aggregated
order by id, valid_from, valid_to

Cette requête retourne maintenant un rang identique pour chaque ligne pouvant être combinée.

1 2010-04-17 00:00:00 2010-04-19 00:00:00 1
1 2010-04-19 00:00:00 2010-04-20 00:00:00 1
1 2010-04-20 00:00:00 2010-05-03 00:00:00 1
1 2010-05-07 00:00:00 2010-05-08 00:00:00 2
1 2010-05-08 00:00:00 2010-05-14 00:00:00 2
2 2010-04-17 00:00:00 2010-04-18 00:00:00 3
2 2010-04-20 00:00:00 2010-04-21 00:00:00 4
2 2010-04-21 00:00:00 2010-04-24 00:00:00 4
2 2010-04-25 00:00:00 2010-04-27 00:00:00 5
2 2010-04-30 00:00:00 2010-05-02 00:00:00 6
2 2010-05-02 00:00:00 2010-05-05 00:00:00 6

Il est maintenant trivial d'agréger les lignes ayant le même rang, et de retourner le plus petit "from" et le plus grand "to".

select
min(id) as id,
min(valid_from) as valid_from,
max(valid_to) as valid_to
from
(select id, valid_from, valid_to,
sum(agg) over (order by id, valid_from, valid_to) as ranked
from
(select
id,
valid_from,
valid_to,
case when id = lag(id, 1)
over (order by id, valid_from, valid_to)
and valid_from = lag(valid_to, 1)
over (order by id, valid_from, valid_to)
then 0 else 1 end as agg
from historical
order by id, valid_from, valid_to) as agg_aggregated
order by id, valid_from, valid_to) as agg_ranked
group by ranked
order by id, valid_from

Le résultat est celui attendu:

1 2010-04-17 00:00:00 2010-05-03 00:00:00
1 2010-05-07 00:00:00 2010-05-14 00:00:00
2 2010-04-17 00:00:00 2010-04-18 00:00:00
2 2010-04-20 00:00:00 2010-04-24 00:00:00
2 2010-04-25 00:00:00 2010-04-27 00:00:00
2 2010-04-30 00:00:00 2010-05-05 00:00:00


Postgres peut ainsi combiner un million de lignes à la minute sur un PC de bureau, alors que les solutions alternatives allant du chargement et de la combinaison dans un programme séparé, à la solution itérative (mal) implémentée via une extension dans une BDD moins costaude, peuvent être de 5 à 1000 fois plus lents. Yay!

Aucun commentaire: