Introduction des expressions de table communes récursives : Rendre Databricks SQL Turing complet

Les expressions de table communes récursives (CTE) sont désormais prises en charge dans Databricks. Cela apporte une manière native d'exprimer des boucles et des traversées en SQL, utile pour travailler avec des données hiérarchiques et structurées en graphe. Ces capacités sont alignées sur la norme SQL et suivent des modèles familiers utilisés dans les entrepôts de données hérités comme Teradata et Snowflake, ce qui facilite grandement les migrations à partir de tels entrepôts. Databricks a également contribué à la prise en charge des CTE récursives dans Apache Spark™, ce qui en fait un logiciel entièrement open source.

Databricks utilise la syntaxe SQL ANSI standard pour les CTE récursives, y compris le mot-clé RECURSIVE.

Cette fonctionnalité, apparemment mineure, améliore considérablement les capacités expressives de SQL, la rendant théoriquement Turing complète, c'est-à-dire capable d'effectuer n'importe quel calcul qu'un ordinateur peut réaliser. Les CTE récursives permettent des solutions composables qui nécessitaient auparavant du code procédural, tel que Python ou des outils externes.

CTE récursives sont maintenant disponibles en avant-première publique DBSQL 2025.20 et Databricks Runtime 17.0 (bientôt disponibles dans Lakeflow Declarative Pipelines). Dans ce billet de blog, nous explorerons comment fonctionnent les CTE récursives et comment elles peuvent vous aider à résoudre des problèmes du monde réel en utilisant du SQL pur.

Caractéristiques clés de la prise en charge des CTE récursives

La prise en charge des CTE récursives par Databricks inclut :

• Parcours de structures arborescentes et graphiques, telles que les organigrammes, les dossiers et les réseaux de routage
• Entièrement open source et intégré à Apache Spark™
• Garde-fous intégrés pour la récursion infinie (100 étapes, 1 million de lignes)
• Garde-fous personnalisables à l'aide de MAX RECURSION LEVEL
• Prise en charge de la récursion infinie contrôlée à l'aide de LIMIT

Les CTE récursives fonctionnent bien avec les systèmes traditionnels qui stockent des données hiérarchiques dans des tables normalisées, ainsi qu'avec les données provenant d'applications modernes qui génèrent des hiérarchies JSON/XML flexibles. Voir les exemples ci-dessous pour chaque cas, y compris les CTE récursives exploitant le type de données Variant pour les hiérarchies JSON.

De plus, la prise en charge des CTE récursives simplifie les migrations à partir des systèmes de bases de données hérités. Teradata et Postgres sont deux exemples de systèmes dont la syntaxe est identique, tandis que les systèmes comme Oracle, qui utilisent la syntaxe CONNECT BY, sont facilement convertis.

Comment fonctionnent les CTE récursives

Les CTE récursives sont des expressions de table communes définies avec le mot-clé RECURSIVE. Elles se composent de deux parties combinées à l'aide de UNION ALL :

1. Une sous-requête de cas de base — elle s'exécute une fois et amorce la récursion
2. Une sous-requête d'étape récursive — elle fait référence à la CTE elle-même et est appliquée de manière répétée pour construire de nouvelles lignes.

L'exécution commence par la requête de base. Ensuite, à chaque itération, l'étape récursive est exécutée en utilisant la sortie de l'étape précédente. Cela continue jusqu'à ce qu'aucune nouvelle ligne ne soit produite.

Pour éviter que la récursion infinie ne consomme des ressources excessives, Databricks applique deux limites de sécurité : une profondeur de récursion maximale de 100 étapes et une limite de lignes de 1 million. Si l'un ou l'autre seuil est dépassé, la requête échoue avec une erreur.

Si vous êtes convaincu que votre récursion nécessite plus de 100 étapes pour produire tous les résultats, vous pouvez outrepasser le niveau maximum en utilisant l'indice MAX RECURSION LEVEL :

 Pour plus de détails, consultez la documentation sur les CTE.

« Chez bp Supply Trading and Shipping – Market Risk, comprendre le reporting de la hiérarchie du portefeuille entre les unités commerciales est essentiel pour que notre entreprise fonctionne efficacement. En remplaçant notre code hérité par des CTE récursives dans Databricks SQL, nous avons réduit une étape de préparation de données hiérarchiques d'environ 6 minutes à environ 30 secondes, soit une amélioration de 12 fois. » — Dharmik Prajapati, bp Staff Software Engineer

Exemples de résolution de tâches itératives à l'aide de CTE récursives

Navigation dans les données arborescentes et hiérarchiques : Recherche des matériaux requis à l'aide d'une nomenclature

Dans l'industrie manufacturière, chaque pièce fabriquée nécessite un ensemble de composants pour être assemblée. Chaque composant peut être décomposé en un ensemble plus petit de pièces individuelles. L'ensemble complet de toutes les pièces est appelé nomenclature (BOM). 

Une nomenclature forme souvent une structure arborescente, ou plus généralement, un graphe acyclique dirigé (DAG). Dans cet exemple, nous examinons les pièces d'un vélo, que nous simplifierons en supposant une structure arborescente, où chaque composant est utilisé dans un seul parent.

Supposons que nous voulions calculer la quantité de matières premières nécessaires pour fabriquer un vélo. Considérons la nomenclature suivante :

Chaque ligne décrit un composant, la pièce plus grande à laquelle il appartient, et combien de composants sont nécessaires pour assembler une unité du parent.

La CTE récursive commence par un objectif : construire un vélo. C'est le cas de base. À chaque étape récursive, nous décomposons les composants en sous-composants. Par exemple, un vélo comprend un cadre, une transmission et deux roues. Chaque roue, à son tour, se compose d'un pneu et de 32 rayons. La structure récursive devient claire à mesure que nous décomposons les pièces en éléments plus petits.

Une fois que nous avons entièrement développé la hiérarchie, nous filtrons les composants intermédiaires (parents) pour ne conserver que les matières premières nécessaires à l'assemblage.

Cette requête calcule la quantité totale de chaque matériau de base nécessaire pour construire un vélo :

Recherche de chemin basée sur le parcours de graphe : Trouver tous les itinéraires de vol à partir d'une ville

Examinons un problème à l'aide d'une structure de données de graphe. Un graphe se compose d'un ensemble de nœuds connectés par des arêtes. Il est utilisé pour représenter des relations ou des connexions entre des paires d'éléments. La résolution d'un problème de graphe nécessitait auparavant Python, une logique de script compliquée ou une bibliothèque externe. Désormais, les requêtes récursives simplifient la tâche.

Un problème typique de structure de graphe est le voyage en avion : quels aéroports puis-je atteindre en utilisant une série de vols ? Supposons que nous ayons l'ensemble de vols suivant qui existent un jour donné :

Chaque vol est identifié par les codes IATA de sa source et de sa destination, ainsi que par les heures de départ et d'arrivée.

Supposons qu'une personne arrive à l'aéroport BEG à 8h du matin et souhaite trouver tous les itinéraires de voyage possibles qu'elle peut effectuer ce jour-là.

C'est un problème naturellement posé comme itératif. Chaque fois que nous découvrons une nouvelle ville que nous pouvons atteindre, nous trouvons tous les vols qui partent de là après notre heure d'arrivée. Pour cette raison, dans la CTE récursive, nous suivons l'heure d'arrivée à chaque aéroport. 

Cela produit l'ensemble de tous les aéroports accessibles, ainsi que le nombre et l'ensemble requis de vols.

Cette requête peut aider les utilisateurs à explorer toutes les destinations accessibles compte tenu des contraintes d'horaire, prenant en charge des applications telles que la planification de voyages, le routage de colis ou la logistique de transport.

Dans l'exemple précédent, nous avons défini les noms de colonnes dans la clause WITH RECURSIVE ... AS (...) . Ici, nous les définissons dans la requête d'ancrage à la place. Les deux approches sont valides dans les CTE récursives sur Databricks.

Parcourir des données semi-structurées et non structurées : Trouver tous les employés stockés dans un fichier JSON

Les systèmes traditionnels stockent souvent des données hiérarchiques dans des tables rigides et normalisées. Pendant ce temps, les applications modernes génèrent fréquemment des hiérarchies JSON/XML flexibles. La combinaison de CTE récursives de Databricks avec le type VARIANT vous permet de migrer ces modèles de données de manière transparente, vous permettant d'interroger à la fois les données normalisées traditionnelles et les structures JSON/XML flexibles dans un seul système.

Dans cet exemple, on nous donne une hiérarchie d'entreprise (relativement petite). Mais au lieu d'une table entièrement structurée, on nous la donne sous forme de JSON :

Supposons que nous voulions une liste de tous les employés et de leurs titres dans un tableau. Les champs des personnes de l'entreprise ne suivent pas le même schéma : certains ont des subordonnés directs, d'autres non ; certains ont leur emplacement, d'autres non ! Avec l'utilisation du type VARIANT dans Databricks, toutes leurs“commonalités” nécessaires peuvent être utilisées dans une CTE récursive pour explorer entièrement la structure imbriquée du JSON, tandis que leurs différences peuvent être ignorées.

Le cas de base de la récursion est la donnée JSON complète de l'employé racine, qui inclut une liste de ses subordonnés. À chaque étape récursive, la requête traite les données de chaque subordonné et répète le processus jusqu'à ce qu'elle atteigne un employé sans subordonnés.

Voici la requête récursive pour cet exemple :

Même si toutes les CTE ici sont sous un bloc WITH RECURSIVE, seule celle avec une récursion réelle est traitée comme récursive. Databricks est suffisamment intelligent pour détecter celles qui nécessitent une récursion, même si vous les marquez toutes !

Le résultat de la requête :

Pour commencer

Commencez avec les CTE récursives en lisant la documentation Databricks. 

Le meilleur entrepôt de données est un lakehouse. Pour en savoir plus sur Databricks SQL, visitez notre site web ou lisez la documentation. Vous pouvez également consulter la visite guidée du produit pour Databricks SQL. Si vous souhaitez migrer votre entrepôt existant vers un entrepôt de données serverless haute performance avec une excellente expérience utilisateur et un coût total réduit, alors Databricks SQL est la solution — essayez-le gratuitement.

(Cet article de blog a été traduit à l'aide d'outils basés sur l'intelligence artificielle) Article original