Lors d’une de mes formations pour Learning Tree la semaine dernière j’ai voulu expliquer à certains stagiaires qu’il était possible de parcourir une hiérarchie sans connaitre sa profondeur à l’avance grâce à une CTE (Common table expression) et grâce à la récursivité et cela n’était pas si simple. Voici donc une explication imagée de l’utilité des CTE récursives, de leur fonctionnement et de leur impact sur les performances.

• Une CTE Récursive Simple

Un exemple assez simple pour comprendre comment fonctionne la récursivité à travers une CTE c’est la réalisation d’un compteur de 1 à 5

--Définition de la CTE
WITH CompteurCTE
AS (
	SELECT 1 AS i
	
	UNION ALL
	
	SELECT i + 1
	FROM CompteurCTE
	WHERE i < 5
	)
-- Appel de la CTE
SELECT *
FROM CompteurCTE

Résultat :

Que vient-il de se passer exactement ?

En appelant notre CTE nous avons demandé à SQL Serveur d’effectuer les étapes suivantes :

1. Retourne moi le résultat de SELECT 1 dans une colonne nommée i
   Le résultat est le suivant :

   i
   -----------
   1

2. Effectue un Union ALL avec SELECT i + 1 FROM CompteurCTE
   Ceci aura pour effet de rappeler notre CTE et donc le SELECT 1 la différence avec le premier appel étant que l’on demande d’effectuer un +1 avec le résultat ce qui nous donne :

   i
   -----------
   1
   2

3. Mais en appelant à nouveau notre SELECT 1 nous avons à nouveau demandé à évaluer le SELECT i + 1 FROM CompteurCTE qui va à nouveau ajouter i au résultat précédent. Et cela sera le cas jusqu’à ce que la condition WHERE i < 5 termine cette répétition d’appel à CompteurCTE. Ce qui nous donnera après 4 itérations, le résultat suivant :

   i
   -----------
   1
   2
   3
   4
   5

• Une CTE Récursive pour parcourir une hiérarchie

Ce procédé qui permet de rappeler une fonction en boucle est un moyen confortable pour parcourir une hiérarchie dont on ne connait pas la profondeur comme la hiérarchie entre les employés dans une entreprise.

Prenons par exemple la table DimEmployee de la base d’exemple AdventureWorksDW2014, la requête suivante nous retourne le numéro des employés, celui de leur chef ainsi que leur nom et prénom.

SELECT [EmployeeKey]
      ,[ParentEmployeeKey]
      ,FirstName
      ,LastName
  FROM [AdventureWorksDW2014].[dbo].[DimEmployee]

Si je vous demande d’afficher le Chef direct (N+1) de chaque employé, vous pourriez écrire :

SELECT --Information de l'employé
        empl.[EmployeeKey]
      ,empl.[ParentEmployeeKey]
      ,empl.FirstName
      ,empl.LastName
      -- Information de son chef
      ,Chef.FirstName AS ChefPrénom
      ,Chef.LastName AS ChefNom
  FROM [AdventureWorksDW2014].[dbo].[DimEmployee] Empl
    LEFT JOIN [AdventureWorksDW2014].[dbo].[DimEmployee] Chef
        ON Empl.ParentEmployeeKey = Chef.EmployeeKey

Le résultat est :

Mais qu’en est-il si je veux connaître le niveau hiérarchique de tous mes salariés ? Je pourrais faire autant de jointures que de niveaux mais ne connaissant pas le nombre de niveaux, c’est pas gagné. Heureusement les CTE sont là pour nous aider.

WITH EmployeeCTE AS
(
-- On démarre avec le BigBoss
    SELECT [EmployeeKey]
    ,[ParentEmployeeKey]
    ,FirstName
    ,LastName
    ,0 AS Niveau
    FROM [AdventureWorksDW2014].[dbo].[DimEmployee]
    WHERE [ParentEmployeeKey] IS NULL

    UNION ALL

    SELECT Emp.[EmployeeKey]
    ,Emp.[ParentEmployeeKey]
    ,Emp.FirstName
    ,Emp.LastName
    ,Niveau+1
    FROM [AdventureWorksDW2014].[dbo].[DimEmployee] Emp
        INNER JOIN EmployeeCTE Chef
            ON Chef.EmployeeKey = Emp.ParentEmployeeKey

)

SELECT * FROM EmployeeCTE 
ORDER BY Niveau

Vous noterez au passage qu’il est possible de modifier la CTE pour sortir uniquement une partie de la hiérarchie, si je veux toutes les personnes qui sont sous Peter Krebs je pourrais modifier ma requête de cette façon. (J’ajoute aussi une nouvelle colonne RootName qui me permet de garder le nom du manager le plus haut dans ma hiérarchie)

WITH EmployeeCTE AS
(
-- On démarre avec le BigBoss
    SELECT [EmployeeKey]
    ,[ParentEmployeeKey]
    ,FirstName
    ,LastName
    ,FirstName AS [RootName]
    ,0 AS Niveau
    FROM [AdventureWorksDW2014].[dbo].[DimEmployee]
    --WHERE ParentEmployeeKey IS NULL
    WHERE LastName = 'Krebs'

    UNION ALL

    SELECT Emp.[EmployeeKey]
    ,Emp.[ParentEmployeeKey]
    ,Emp.FirstName
    ,Emp.LastName
    ,RootName
    ,Niveau+1
    FROM [AdventureWorksDW2014].[dbo].[DimEmployee] Emp
        INNER JOIN EmployeeCTE Chef
            ON Chef.EmployeeKey = Emp.ParentEmployeeKey

)

SELECT * FROM EmployeeCTE 

ORDER BY Niveau

Qu’en est-il des performances ?

1. Les CTE Récursives sont plutôt rapides surtout si vous avez des indexes sur vos prédicats de recherche (EmployeeKey et ParentEmployeeKey dans l’exemple ci-dessus). Toutefois si vous avez des filtres complexes, et des relations parent-child non uniques vous pouvez obtenir de fortes optimisations en suivant cet article de SQLCat.
2.  Une CTE n’est pas une table ni une vue, vous ne pourrez malheureusement pas l’indexer, et dans le cas ou votre CTE est par la suite intégrée dans de grosses jointures cela peut vous coûter cher. Dans ce cas, il peut être préférable d’utiliser la CTE pour persister votre jeu de données dans une table indexée. (Ou alors utiliser une boucle en SQL à la place …)

En conclusion, n’hésitez pas à utiliser les CTE récursives, celles-ci peuvent vous simplifier grandement la vie comme pour la génération d’une dimension temps par exemple.