Article complet: Agrégation d'intervalles en SQL

Le problème est le suivant : partant d'une table contenant des intervalles (périodes de temps, plage d'entiers ou autres...), c'est à dire une information continue bornée par deux colonnes (DEBUT et FIN par exemple), comment faire en sorte d'agréger ces intervalles lorsque certains se recoupent ?

[Suite:]

Ce problème est assez générique. Par exemple il permet de savoir s'il y a une interruption dans la continuité d'un système résultant de multiples périodes.
Pour bien comprendre comment résoudre ce problème partons d'un exemple simple et d'un algorithme "force brute".

Voici la table qui nous servira de modèle :
CREATE TABLE TIMELINE (DEBUT INT, FIN INT)

Nous allons tout d'abord y insérer uniquement deux palges dont la particularité est qu'elle se recouvrent par la fait que la fin de l'une est le début de l'autre :
INSERT INTO TIMELINE VALUES (1, 5) 
INSERT INTO TIMELINE VALUES (5, 10)

Il semble à priori évident que la solution si elle existe, se trouve dans la combinaison de tous les débuts de toutes les plages par la fin de toutes ces mêmes plages.
D'où une première requête très simple faisant un produit cartésien :

SELECT DISTINCT PRE.DEBUT, DER.FIN 
FROM   TIMELINE PRE --> PRE pour premier 
       CROSS JOIN TIMELINE DER --> DER pour dernier

DEBUT       FIN 
----------- ----------- 
1           5 
1           10 
5           5 
5           10

Dès à présent il nous saute aux yeux que la 3e ligne n'apporte rien car sa "durée" (ou distance, longueur) est zéro.
Ce genre de cas peut être éliminé par une non équi jointure plutôt que par le produit cartésien, ce qui apporte l'avantage de traiter dès le départ moins de lignes :

SELECT DISTINCT PRE.DEBUT, DER.FIN 
FROM   TIMELINE PRE 
       INNER JOIN TIMELINE DER 
             ON PRE.DEBUT < DER.FIN

DEBUT       FIN 
----------- ----------- 
1           5 
1           10 
5           10  

Il s'agit maintenant d'éliminer les périodes pour lesquelles le début de l'une est supérieur au début de l'autre avec la même fin.
Ce qui peut être fait avec la condition supplémentaire suivante :

SELECT DISTINCT PRE.DEBUT, DER.FIN 
FROM   TIMELINE PRE 
       INNER JOIN TIMELINE DER 
             ON PRE.DEBUT < DER.FIN 
AND NOT EXISTS (SELECT *  
                FROM   TIMELINE SI1 --> SI1 pour Sous Intervalle 1 
                WHERE  SI1.DEBUT < PRE.DEBUT 
                  AND  PRE.DEBUT <= SI1.FIN)

DEBUT       FIN 
----------- ----------- 
1           5 
1           10   

Bien entendu cela doit aussi être fait pour la borne de fin, ce qui conduit à l'amélioration suivante :

SELECT DISTINCT PRE.DEBUT, DER.FIN 
FROM   TIMELINE PRE 
       INNER JOIN TIMELINE DER 
             ON PRE.DEBUT < DER.FIN 
AND NOT EXISTS (SELECT *  
                FROM   TIMELINE SI1 
                WHERE  (SI1.DEBUT < PRE.DEBUT  
                        AND PRE.DEBUT = SI1.FIN) 
                   OR  (SI1.DEBUT = DER.FIN  
                        AND DER.FIN < SI1.FIN))

DEBUT       FIN 
----------- ----------- 
1           10

A ce stade notre résultat semble être parfait, mais il n'en est rien, car notre jeu de données est insufisant à traduire toutes les problématiques.
Ajoutons y quelques lignes afin de savoir quand il fonctionne et quand il est en echec.

Insertion d'un intervalle inclus :

INSERT INTO TIMELINE VALUES (2, 4)

La requête précédente nous donne :

DEBUT       FIN 
----------- ----------- 
1           4 
1           10 
2           4 
2           10

Ce qui est un résultat faux, mais se corrige en considérant que la comparaisons entre les bornes peut se faire par inégalité comme ceci :

SELECT DISTINCT PRE.DEBUT, DER.FIN 
FROM   TIMELINE PRE 
       INNER JOIN TIMELINE DER 
             ON PRE.DEBUT < DER.FIN 
AND NOT EXISTS (SELECT *  
                FROM   TIMELINE SI1 
                WHERE  (SI1.DEBUT < PRE.DEBUT  
                        AND PRE.DEBUT <= SI1.FIN) 
                   OR  (SI1.DEBUT <= DER.FIN  
                        AND DER.FIN < SI1.FIN))

Insérons maintenant un intervalle englobant un autre intervalle :

INSERT INTO TIMELINE VALUES (0, 6)

La requête précédente, nous donne :

DEBUT       FIN 
----------- ----------- 
0           10

Ce qui est un résultat prévisible du fait des inégalités introduite par l'amélioration précédente.

Insérons maintenant un intervalle dissocié de tous les autres. Notre résultat devrait avoir deux lignes : le résultat précédent plus cette nouvelle ligne.

INSERT INTO TIMELINE VALUES (15, 20)

Or il n'en est rien :

DEBUT       FIN 
----------- ----------- 
0           10 
0           20 
15          20

Pour éliminer ce dernier effet de bord nous devons considérer qu'un intervalle doit être une continuité d'intervalle. Ou encore que pour tout intervalle il ne doit pas exister un non intervalle inclus. Cette double négation est-celle là même qui forme la division relationnelle selon la méthode du double NOT EXISTS... La requête finale s'écrit donc :

SELECT DISTINCT PRE.DEBUT, DER.FIN 
FROM   TIMELINE PRE 
       INNER JOIN TIMELINE DER 
             ON PRE.DEBUT < DER.FIN 
WHERE NOT EXISTS (SELECT *  
                  FROM   TIMELINE SI1 
                  WHERE  (SI1.DEBUT < PRE.DEBUT  
                          AND PRE.DEBUT <= SI1.FIN) 
                     OR  (SI1.DEBUT <= DER.FIN  
                          AND DER.FIN < SI1.FIN)) 
AND NOT EXISTS (SELECT *  
                FROM   TIMELINE SI2  --> SI2 pour Sous Intervalle 2 
                WHERE  PRE.DEBUT < SI2.DEBUT  
                  AND  SI2.DEBUT <= DER.FIN 
                  AND  NOT EXISTS (SELECT *  
                                   FROM   TIMELINE SI3  --> SI3 pour Sous Intervalle 3 
                                   WHERE  SI3.DEBUT < SI2.DEBUT 
                                     AND  SI2.DEBUT <= SI3.FIN))

Au fait, nous pouvons écrire cette requête sous forme de CTE :

WITH 
T_INTERVALLES AS 
(SELECT PRE.DEBUT AS D1, PRE.FIN AS F1,  
        DER.DEBUT AS D2, DER.FIN AS F2 
 FROM   TIMELINE PRE 
        INNER JOIN TIMELINE DER 
              ON PRE.DEBUT < DER.FIN) 
SELECT DISTINCT D1, F2 
FROM   T_INTERVALLES AS I 
WHERE  NOT EXISTS (SELECT *  
                  FROM   TIMELINE SI1 
                  WHERE  (SI1.DEBUT < D1  
                          AND D1 <= SI1.FIN) 
                     OR  (SI1.DEBUT <= F2  
                          AND F2 < SI1.FIN)) 
AND NOT EXISTS (SELECT *  
                FROM   TIMELINE SI2  --> SI2 pour Sous Intervalle 2 
                WHERE  D1 < SI2.DEBUT  
                  AND  SI2.DEBUT <= F2 
                  AND  NOT EXISTS (SELECT *  
                                   FROM   TIMELINE SI3  --> SI3 pour Sous Intervalle 3 
                                   WHERE  SI3.DEBUT < SI2.DEBUT 
                                     AND  SI2.DEBUT <= SI3.FIN))   

D'autres formulation de ce calcul existe sous forme de requête en table dérivée comme sous forme récursive.

Notons néanmoins que cette requête facile à expliquer possède l'inconvénient d'un coût assez élevé.
Tentons de comprendre l'évolution de son coût en fonction du volume des données.

-- ce code sert à insérer 400 lignes soit environ 8 Ko de données à chaque appel. (Syntaxe T-SQL/SQL Server) 
DECLARE @NB INT, @DEB INT, @FIN INT; 
SET @NB = 400; 
WHILE @NB > 0 
BEGIN 
   SET @DEB = 100000 * RAND(); 
   SET @FIN = @DEB + 1000 * RAND(); 
   INSERT INTO TIMELINE VALUES (@DEB, @FIN); 
   SET  @NB = @NB - 1; 
END 

Voici les résultats de consommation d'IO (MS SQL Server)

------------------------------------------------------------- 
Lignes|       400 |         800 |        1200 |        1600 | 
------------------------------------------------------------- 
IO    |   236 360 |     776 004 |   1 670 043 |   2 943 618 | 
------------------------------------------------------------- 
 
------------------------------------------------------------- 
Lignes|      2000 |        2400 |        2800 |        3200 | 
------------------------------------------------------------- 
IO    | 4 519 013 |   6 641 549 |   9 021 330 |  11 847 356 | 
-------------------------------------------------------------

Il existe bien entendu d'autres formulation de ce type de requête notamment de manière récursive. Il est aussi possible d'indexer les colonnes pour obtenir de meilleures performances. Mais l'influence de la distribution des données et du volume des lignes à traiter étant très forte il est difficile de donner des métriques précises.

Voici par exemple une solution donnée par Snodgrass :

WITH T 
AS (SELECT F.DEBUT, L.FIN 
    FROM   TIMELINE AS F 
           JOIN TIMELINE AS L 
                ON F.FIN <= L.FIN 
           CROSS JOIN TIMELINE AS E      
    GROUP  BY F.DEBUT, L.FIN 
    HAVING COUNT(CASE 
                    WHEN (E.DEBUT < F.DEBUT AND F.DEBUT <= E.FIN) 
                      OR (E.DEBUT <= L.FIN AND L.FIN < E.FIN)  
                    THEN 1  
                 END) = 0) 
SELECT DEBUT, MIN(FIN) AS FIN 
FROM   T  
GROUP  BY DEBUT 

Exercice :

Voici un jeu d'essai assez simple représentant tous les cas de figure :

DELETE FROM TIMELINE 
 
INSERT INTO TIMELINE VALUES (0, 5)  
 
INSERT INTO TIMELINE VALUES (6, 10) 
 
INSERT INTO TIMELINE VALUES (20, 25) 
INSERT INTO TIMELINE VALUES (25, 30) 
 
INSERT INTO TIMELINE VALUES (40, 55) 
INSERT INTO TIMELINE VALUES (54, 60) 
 
INSERT INTO TIMELINE VALUES (70, 80) 
INSERT INTO TIMELINE VALUES (74, 76) 
 
INSERT INTO TIMELINE VALUES (100, 120) 
INSERT INTO TIMELINE VALUES (110, 130) 
INSERT INTO TIMELINE VALUES (120, 140) 
 
INSERT INTO TIMELINE VALUES (200, 250) 
INSERT INTO TIMELINE VALUES (250, 280) 
INSERT INTO TIMELINE VALUES (280, 290) 
 
INSERT INTO TIMELINE VALUES (300, 390) 
INSERT INTO TIMELINE VALUES (310, 380) 
INSERT INTO TIMELINE VALUES (330, 360)

Qui doit conduire à la solution :

DEBUT       FIN 
----------- ----------- 
0           5 
6           10 
20          30 
40          60 
70          80 
100         140 
200         290 
300         390

Autre solution...

Voici une manière récursive de traiter le problème :

WITH  
T0 AS -- suprime les périodes incluses et calcule la durée  
(SELECT DISTINCT Tout.*  
 FROM   TIMELINE  AS Tout  
 WHERE  NOT EXISTS(SELECT *  
                   FROM   TIMELINE  AS Tin  
                   WHERE  Tout.DEBUT >= Tin.DEBUT AND Tout.FIN < Tin.FIN)),  
T1 AS -- ancres : périodes de tête...  
(SELECT Ta.*, 1 AS ITERATION  
 FROM   T0 AS Ta  
 WHERE  NOT EXISTS(SELECT *  
                   FROM   T0 AS Tb  
                   WHERE  Tb.FIN >= Ta.DEBUT   
                      AND Tb.FIN < Ta.FIN)  
 UNION  ALL -- itération sur période dont le debut est inclus dans les bornes de la période ancre  
 SELECT T1.DEBUT, T0.FIN, T1.ITERATION + 1  
 FROM   T1   
        INNER JOIN T0  
              ON T1.DEBUT < T0.DEBUT  
                 AND T1.FIN >= T0.DEBUT  
                 AND T1.FIN < T0.FIN),  
T2 AS  
(SELECT *, ROW_NUMBER() OVER(PARTITION BY DEBUT ORDER BY FIN - DEBUT DESC) AS N1, 
           ROW_NUMBER() OVER(PARTITION BY FIN   ORDER BY FIN - DEBUT DESC) AS N2 
 FROM   T1)  
SELECT DEBUT, FIN  
FROM   T2  
WHERE  N1 = 1 AND N2 = 1;

-------- 
Frédéric Brouard, SQLpro - ARCHITECTE DE DONNÉES, http://sqlpro.developpez.com/ 
Expert bases de données relationnelles et langage SQL. MVP Microsoft SQL Server 
www.sqlspot.com : modélisation, conseil, audit, optimisation, tuning, formation 
* * * * *  Enseignant CNAM PACA - ISEN Toulon - CESI Aix en Provence  * * * * *