Historique de la question.
Les modèles de données hiérarchiques utilisent traditionnellement des listes d'adjacence ou des ensembles imbriqués pour représenter des structures arborescentes. Alors que les listes d'adjacence minimisent le stockage et simplifient les insertions, les rapports analytiques nécessitent souvent des "chemins matérialisés" (par exemple, "Racine/Catégorie/Sous-catégorie") pour permettre un filtrage efficace utilisant des motifs de préfixe. Avant SQL:1999, aplatir ces hiérarchies nécessitait des curseurs procéduraux ou de la récursion côté application. L'introduction des expressions de table communes récursives (CTE) dans la norme SQL ANSI a permis un parcours déclaratif, mais construire des chemins déterministes et ordonnés avec des limites de profondeur introduit des complexités concernant la terminaison de la récursion et la stabilité du tri.
Le problème.
Vous devez transformer une liste d'adjacence récursive en un format dénormalisé où chaque ligne contient la lignée ancestrale complète sous forme de chaîne délimitée (par exemple, "/A/B/C"). La solution doit imposer trois contraintes : (1) les frères et sœurs à chaque niveau doivent apparaître dans l'ordre lexicographique au sein du chemin, (2) le parcours ne doit pas dépasser une profondeur maximale spécifiée pour éviter les requêtes aberrantes sur des données malformées, et (3) l'implémentation doit utiliser une syntaxe SQL ANSI stricte sans extensions propriétaires pour la hiérarchie.
La solution.
La solution emploie une approche CTE en deux étapes. Tout d'abord, un CTE non récursif calcule la position ordinale de chaque nœud parmi ses frères et sœurs à l'aide d'une fonction de fenêtre. Ce pré-calcul est nécessaire car SQL ANSI interdit les fonctions de fenêtre dans le membre récursif d'un CTE pour garantir une terminaison monotone. Ensuite, un CTE récursif parcourt l'arbre, concaténant les noms des nœuds et les clés de tri pré-calculées, tout en appliquant la limite de profondeur et la détection optionnelle de cycles dans la clause WHERE.
WITH RECURSIVE OrderedNodes AS ( -- Étape 1 : Attribuer un ordre déterministe aux frères et sœurs SELECT node_id, parent_id, node_name, ROW_NUMBER() OVER (PARTITION BY parent_id ORDER BY node_name, node_id) AS sibling_order FROM taxonomy ), PathBuilder AS ( -- Membre d'ancrage : Initialiser les nœuds racines SELECT node_id, node_name, 1 AS depth, CAST(node_name AS VARCHAR(1000)) AS materialized_path, CAST(sibling_order AS VARCHAR(100)) AS sort_key FROM OrderedNodes WHERE parent_id IS NULL UNION ALL -- Membre récursif : Ajouter des enfants SELECT c.node_id, c.node_name, p.depth + 1, p.materialized_path || '/' || c.node_name, p.sort_key || '.' || CAST(c.sibling_order AS VARCHAR(100)) FROM OrderedNodes c INNER JOIN PathBuilder p ON c.parent_id = p.node_id WHERE p.depth < 5 -- Contrainte stricte de profondeur AND p.materialized_path NOT LIKE '%/' || c.node_name || '%' -- Gardien de cycle ) SELECT node_id, materialized_path, depth FROM PathBuilder ORDER BY sort_key;
Description du problème.
Une plateforme de commerce électronique mondiale maintient une taxonomie de produits avec plus de 100 000 catégories dans une base de données PostgreSQL (mode conforme à SQL ANSI). L'équipe marketing nécessite une exportation quotidienne en CSV pour une plateforme publicitaire externe qui s'attend à des chemins de catégories entièrement qualifiés (par exemple, "Électronique/Ordinateurs/Ordinateurs portables") avec un ordre strictement alphabétique à chaque niveau pour assurer un ciblage cohérent du public. La solution existante utilisait un script Python qui exécutait N+1 requêtes, entraînant un temps d'exécution de 20 minutes et de fréquents dépassements de délais.
Différentes solutions envisagées.
Solution A : Mise en cache côté application avec reconstruction programmée. L'équipe a envisagé de matérialiser les chemins dans un cache Redis via un travail en arrière-plan toutes les 6 heures. Les avantages incluaient une implémentation Python simple et une charge réduite sur la base de données pendant les heures de pointe. Cependant, les inconvénients étaient une obsolescence significative des données (jusqu'à 6 heures), la complexité de l'invalidation du cache lorsque les catégories étaient réaffectées, et une consommation excessive de mémoire pour l'arbre complet.
Solution B : Vue de base de données utilisant un CTE récursif. Cette approche crée une vue qui calcule les chemins à la demande en utilisant le modèle CTE récursif SQL ANSI. Les avantages incluent la garantie de fraîcheur des données (résultats en temps réel), une source unique de vérité, et l'exploitation de l'optimiseur de requêtes de la base de données pour les jointures. Les inconvénients incluent l'intensité CPU sur le serveur de base de données et le risque de récursion infinie si les données contiennent des références cycliques (par exemple, une catégorie accidentellement liée à son propre descendant).
Solution C : Colonne matérialisée maintenue par un déclencheur. Cela ajouterait une colonne materialized_path à la table et la mettrait à jour via des déclencheurs lors d'insertion, mise à jour ou suppression. Les avantages incluent des performances de lecture extrêmement rapides (scan d'index simple). Les inconvénients incluent une surcharge d'écriture significative, une logique de déclencheur complexe pour gérer les déplacements ou les renommages de sous-arbres, et la difficulté de maintenir la contrainte d'ordre lexicographique lorsque les noms des frères et sœurs changent.
Solution choisie et résultat.
L'équipe a sélectionné Solution B (Vue CTE récursive) car la charge de travail lourde en lecture (ratio lecture-écriture de 100:1) bénéficiait d'un calcul à la demande sans le fardeau de maintenance des déclencheurs. Pour atténuer le risque de cycle, ils ont implémenté le contrôle de modèle LIKE dans la clause WHERE et ajouté une limite de profondeur de 5 niveaux basée sur des règles commerciales. Ils ont également créé un index composite sur (parent_id, node_name) pour optimiser le tri de la fonction de fenêtre dans le CTE d'ancrage. Le résultat a réduit le temps d'exportation de 20 minutes à 8 secondes, tout en détectant et isolant simultanément 3 références cycliques dans les données héritées lors de la phase de déploiement.
Pourquoi les fonctions agrégées ou de fenêtre ne peuvent-elles pas apparaître dans le membre récursif d'un CTE, et comment cela affecte-t-il le classement des frères et sœurs ?
Les normes SQL ANSI interdisent au membre récursif de contenir des fonctions agrégées (comme SUM) ou des fonctions de fenêtre (comme ROW_NUMBER) pour garantir que la requête récursive est monotone et a le potentiel d'atteindre un point fixe. Les fonctions de fenêtre nécessitent de matérialiser et de partitionner l'ensemble de travail, ce qui peut violer les sémantiques de flux requises pour la terminaison de la récursion et peut introduire de la non-déterminisme. Par conséquent, vous ne pouvez pas calculer le classement des frères et sœurs dynamiquement au sein de la récursion. L'approche correcte est de pré-calculer les positions ordinales dans un CTE non récursif séparé (comme démontré dans la solution), puis de référencer cette colonne calculée dans la jointure récursive. Les candidats tentent souvent de placer ROW_NUMBER() directement dans la liste SELECT récursive, entraînant des erreurs de syntaxe ou des plans d'exécution imprévisibles.
Comment gérez-vous les références cycliques dans la hiérarchie sans la syntaxe de détection de cycle propriétaire comme la clause CYCLE de PostgreSQL ?
Le SQL ANSI pur ne fournit pas de mécanisme de détection de CYCLE intégré (bien que SQL:2023 ait introduit les clauses CYCLE et SEARCH, elles ne sont pas encore largement mises en œuvre). Pour prévenir la récursion infinie, vous devez suivre manuellement les nœuds visités. La technique standard portable consiste à accumuler une chaîne délimitée d'identifiants de nœuds visités (ou un tableau si supporté) et à vérifier si le node_id actuel existe déjà dans cet accumulateur avant de procéder. Utiliser un prédicat comme WHERE p.materialized_path NOT LIKE '%/' || c.node_id || '%' efface efficacement les cycles, bien que cette méthode suppose des limites de profondeur raisonnables pour éviter le dépassement de longueur de chaîne. Alternativement, on pourrait utiliser une chaîne de bits ou un chemin haché pour des ensembles de données plus volumineux.
Qu'est-ce qui garantit un classement déterministe lorsque deux nœuds frères partagent des noms identiques, et pourquoi un ordre total est-il critique pour les chemins matérialisés ?
Le déterminisme repose sur l'établissement d'un ordre total parmi les frères et sœurs. Si la fonction de fenêtre utilise uniquement ORDER BY node_name et que deux frères et sœurs partagent le même nom, la base de données est libre de les renvoyer dans n'importe quel ordre (défini par l'implémentation), entraînant des chaînes de chemin non déterministes à travers différentes exécutions de requêtes ou versions de la base de données. Ce non-déterminisme casse la mise en cache des résultats de requête, complique les tests et peut causer des données en "flottement" dans des systèmes en aval. La solution consiste à ajouter un briseur d'égalité unique, typiquement la clé primaire node_id, à la clause ORDER BY : ORDER BY node_name, node_id. Cela garantit que chaque frère a une position ordinale unique, garantissant que le chemin matérialisé et la clé de tri auxiliaire sont reproductibles et stables.