4th Jul 2022 9 minutes de lecture

Apprenez à connaître la puissance des requêtes récursives SQL

Le plus souvent, les requêtes SQL que nous exécutons sur une base de données sont assez simples. Cela dépend de votre rôle, bien sûr. Les analystes des entrepôts de données récupèrent des informations d'un tout autre ordre en utilisant (très souvent) des requêtes beaucoup plus complexes que les ingénieurs logiciels qui créent des applications CRUD.

Cependant, il est parfois plus simple ou plus élégant d'exécuter une requête un peu plus sophistiquée sans avoir besoin d'un traitement supplémentaire des données dans le code. L'une des façons d'y parvenir est d'utiliser une fonction SQL appelée " requête récursive".

Prenons un exemple concret. Supposons que nous ayons une base de données contenant une liste de nœuds et une liste de liens entre eux (que l'on peut comparer à des villes et des routes). Notre tâche consiste à trouver le chemin le plus court du nœud 1 au nœud 6.

En fait, il ne s'agit de rien d'autre que de traverser un graphe. La toute première idée d'un ingénieur logiciel moyen serait de récupérer toutes les lignes des deux tables et d'implémenter un algorithme DFS (Depth-First Search) ou BFS (Breadth-First Search) dans son langage de programmation préféré. Ce n'est pas une mauvaise idée (si vous aimez coder 😉 ) mais vous pouvez le faire avec une seule requête SQL !

Clause WITH - Les expressions de table communes à la rescousse !

Remarque : tous les exemples sont écrits pour PostgreSQL 9.3 ; cependant, il ne devrait pas être difficile de les rendre utilisables avec un SGBDR différent.

Si votre SGBDR est PostgreSQL, IBM DB2, MS SQL Server, Oracle (uniquement à partir de la version 11g 2) ou MySQL (uniquement à partir de la version 8.0.1), vous pouvez utiliser des requêtes WITH, connues sous le nom de Common Table Expressions (CTE). D'une manière générale, elles vous permettent de diviser des requêtes complexes en un ensemble de requêtes plus simples, ce qui facilite la lecture de la requête. La structure d'une clause WITH est la suivante :

WITH [cte_name] AS (
	[cte_term])
SELECT ... FROM [cte_name];

Par exemple, nous pourrions vouloir obtenir au maximum 3 noeuds, dont la longueur totale des liens sortants est d'au moins 100 et dont au moins un seul lien sortant a une longueur supérieure à 50. Vous n'avez pas besoin de comprendre complètement l'exemple suivant, il suffit de regarder la structure de la requête. Au lieu d'écrire une requête comme celle-ci :

SELECT * FROM node 
WHERE id IN (
    SELECT distinct node_from_id 
    FROM link
    WHERE length > 50 
      AND node_from_id IN (
        SELECT node_from_id
        FROM link 
        GROUP BY node_from_id 
        HAVING SUM(length) >= 100 
        ORDER BY SUM(length) DESC
        LIMIT 3));

nous pouvons l'écrire comme ceci :

WITH
longest_outgoing_links AS (
    SELECT node_from_id
    FROM link 
    GROUP BY node_from_id 
    HAVING SUM(length) >= 100 
    ORDER BY SUM(length) DESC
    LIMIT 3),
nodes_from_longest_outgoing_links AS (
    SELECT distinct node_from_id 
    FROM link
    WHERE length > 50 
      AND node_from_id IN 
         (SELECT * FROM longest_outgoing_links)
)
SELECT * FROM node 
WHERE id IN (SELECT * FROM nodes_from_longest_outgoing_links);

Les requêtes sont définies séparément, ce qui facilite grandement la compréhension lors de la mise en œuvre d'exemples beaucoup plus complexes.

Un point important : Les CTE peuvent aussi avoir une structure récursive:

WITH RECURSIVE [cte_name] (column, ...) AS (
    [non-recursive_term]
    UNION ALL
    [recursive_term])
SELECT ... FROM [cte_name];

Comment cela fonctionne-t-il ?

C'est très simple. Dans la première étape, un terme non récursif est évalué. Ensuite, pour chaque ligne de résultat de l'évaluation précédente, un terme récursif est évalué et ses résultats sont ajoutés aux précédents. Le terme récursif a accès aux résultats du terme évalué précédemment.

Un exemple simple #1

Prenons un exemple simple : la multiplication par 2 :

WITH RECURSIVE x2 (result) AS ( 
    SELECT 1 
    UNION ALL 
    SELECT result*2 FROM x2) 
SELECT * FROM x2 LIMIT 10;

Dans la première étape, la seule ligne de résultat est "1". Ensuite, il y a UNION ALL avec un terme récursif. 1 est multiplié par 2, ce qui donne une ligne de résultat - "2". Pour l'instant, il y a deux lignes de résultat : 1, 2. Cependant, la dernière évaluation du terme n'a produit qu'une seule ligne - "2" - et elle sera transmise à l'étape récursive suivante. 2 est multiplié par 2, ce qui donne "4", et ainsi de suite... Dans cet exemple, la récursivité serait infinie si nous n'avions pas spécifié la clause LIMIT.

Un exemple facile n°2

Prenons un autre exemple rapide (typiquement académique) : la suite de Fibonacci. Elle est définie comme suit :

F(n) =	0	, n = 0
	1	, n = 1
	F(n-1) + F(n-2)	, n > 1

Une telle fonction peut être définie en SQL à l'aide de la clause WITH:

WITH RECURSIVE fib(f1, f2) AS ( 
    SELECT 0, 1 
    UNION ALL 
    SELECT f2, (f1+f2) FROM fib ) 
SELECT f1 FROM fib LIMIT 10 ;

J'espère que le concept est maintenant clair.

Traversée de graphe

Reprenons notre exemple avec une traversée de graphe. Ce que nous voulons faire est de trouver le chemin le plus court entre deux nœuds. Voici à quoi ressemble la structure de la DB :

Juste pour rendre notre SQL plus lisible, définissons une vue simple node_links_view joignant node avec link et avec node à nouveau:

CREATE VIEW node_links_view AS 
SELECT 
    n1.id AS node_id, 
    n1.name AS node_name, 
    n2.id AS destination_node_id, 
    n2.name AS destination_node_name, 
    l.length AS link_length 
FROM 
    noeud n1 
    JOIN link l ON (n1.id = l.node_from_id) 
    JOIN node n2 ON (l.node_to_id = n2.id) ;

Maintenant, la structure de notre modèle se présente comme suit :

Qu'avons-nous besoin comme résultat de la requête ? Nous voulons un chemin exact entre les nœuds et sa longueur totale. Afin d'exclure tout cycle dans le graphe, nous avons également besoin d'un drapeau pour identifier si le dernier nœud a déjà été visité. Ainsi, la première partie de la définition du CTE ressemblera à ceci:

WITH RECURSIVE search_path (path_ids, length, is_visited) AS

Dans la première étape, nous devons obtenir tous les liens du nœud de départ :

   
SELECT 
    ARRAY[node_id, destination_node_id], -- path_ids
    link_length, -- longueur
    node_id = destination_node_id -- is_visited
FROM 
    node_links_view ;

C'est notre terme non récursif.

Maintenant, nous allons aller récursivement en partant du dernier nœud visité, qui est le dernier élément d'un tableau:

    SELECT 
        path_ids || d.destination_node_id, -- path_ids
        f.length + d.link_length, -- length
        d.destination_node_id = ANY(f.path_ids) -- is_visited
    FROM 
        node_links_view d, 
        chemin de recherche f 
    WHERE 
        f.path_ids[array_length(path_ids, 1)] = d.node_id 
        AND NOT f.is_visited ;

Comment cela fonctionne-t-il ? Regardez les clauses FROM et WHERE. La requête obtient les lignes suivantes de node_link_view qui commencent au dernier nœud de l'évaluation précédente qui ne s'est pas terminée par un cycle. Elle renvoie un tableau étendu avec un nœud de destination du lien, une somme de longueurs et un drapeau déterminant si ce nœud a été précédemment visité. Cette partie récursive de la requête sera exécutée tant qu'il existe des liens vers des nœuds non visités.

Donc, voici une requête SQL complète récupérant tous les chemins du nœud avec id=1 au nœud avec id=6:

WITH RECURSIVE search_path (path_ids, length, is_visited) AS 
( 
    SELECT 
        ARRAY [node_id, destination_node_id], 
        longueur_lien, 
        node_id = destination_node_id 
    FROM 
        vue_liens_noeud 

    UNION ALL 
    SELECT 
        path_ids || d.destination_node_id, 
        f.length + d.link_length, 
        d.destination_node_id = ANY(f.path_ids) 
    FROM 
        node_links_view d, 
        chemin de recherche f 
    WHERE 
    f.path_ids[array_length(path_ids, 1)] = d.node_id 
    AND NOT f.is_visited 
) 
SELECT * FROM search_path 
WHERE path_ids[1] = 1 
AND path_ids[array_length(path_ids, 1)] = 6 
ORDER BY length ;

En conséquence, nous obtenons tous les chemins du nœud 1 au nœud 6 ordonnés par la longueur totale du chemin :

 path_ids | length | is_visited 
---------------+--------+------------ 
 {1,3,2,5,6}   | 140 | f 
 {1,2,5,6}     | 150 | f 
 {1,3,4,5,6}   | 150 | f 
 {1,3,4,6}     | 190 | f 
 {1,2,3,4,5,6} | 200 | f 
 {1,2,3,4,6}   | 240 | f 
(6 rangs)

Le chemin le plus court est le premier, nous pourrions donc ajouter une clause LIMIT pour n'obtenir qu'un seul résultat.

Souvenez-vous que nous avons créé la vue externe - node_links_view - pour rendre le SQL plus facile à lire ? Nous pouvons faire la même chose avec un CTE:

WITH RECURSIVE search_path (path_ids, length, is_visited) AS 
( 
    SELECT 
        ARRAY [node_id, destination_node_id], 
        longueur_lien, 
        node_id = destination_node_id 
    FROM node_links_select

    UNION ALL 
    SELECT 
        path_ids || d.destination_node_id, 
        f.length + d.link_length, 
        d.destination_node_id = ANY(f.path_ids) 
    FROM node_links_select d, 
        search_path f 
    WHERE 
        f.path_ids[array_length(path_ids, 1)] = d.node_id 
        AND NOT f.is_visited 
), 

node_links_select AS ( 
    SELECT 
        n1.id AS node_id, 
        n1.name AS node_name, 
        n2.id AS destination_node_id, 
        n2.name AS destination_node_name, 
        l.length AS link_length 
    FROM 
        noeud n1 
        JOIN link l ON (n1.id = l.node_from_id) 
        JOIN node n2 ON (l.node_to_id = n2.id) 
)

SELECT * FROM search_path 
WHERE path_ids[1] = 1 
AND path_ids[array_length(path_ids, 1)] = 6 
ORDER BY length ;

Note: cet exemple n'est en aucun cas optimisé ! Son but est juste de vous montrer comment utiliser les CTE récursifs.

Oracle (avant la version 11g 2) - Requêtes hiérarchiques

Jusqu'à Oracle 11g version 2, les bases de données Oracle ne prenaient pas en charge les requêtes WITH récursives. Dans Oracle SQL, ces types de requêtes sont appelées requêtes hiérarchiques et elles ont une syntaxe complètement différente, mais l'idée est tout à fait la même. Vous pouvez en savoir plus sur les requêtes hiérarchiques dans la documentation Oracle.

MySQL - 33 mois de silence...

Mauvaise nouvelle pour les utilisateurs de MySQL. Il ne supporte pas la clause WITH bien qu'il y ait eu de nombreuses demandes de fonctionnalités la réclamant. La première était probablement celle-ci qui a été ignorée pendant 33 mois et n'a pas été résolue depuis janvier 2006...

Mise à jour : Les requêtes WITH récursives sont disponibles dans MySQL depuis la version 8.0.1, publiée en avril 2017.

J'espère que l'idée des requêtes récursives est maintenant claire pour vous. Profitez récursivement des requêtes récursives!

Tags: