PostgreSQL comme base de données graphique, partie 1: SQL/PGQ dans PostgreSQL

Cet article est le deuxième d’une série consacrée aux bases de données graphiques et à PostgreSQL. Le premier a posé les bases: qu’est-ce qu’un graphe, ce qu’on peut modéliser comme graphe, et le paysage des systèmes graphiques. Celui-ci passe du général au spécifique: comment on interroge les graphes, pourquoi SQL peut être maladroit pour cela, et ce que SQL/PGQ change. Il s’achève sur l’implémentation PostgreSQL, les raisons de son annulation, et quelques notes sur les fonctionnalités principales encore à venir.

Les langages d’interrogation des graphes

Dans l’article précédent, nous avons terminé par l’observation que les bases de données graphiques existent sous de nombreuses formes, qu’elles diffèrent dans leur façon de stocker les graphes et les modèles de données supportés. Elles diffèrent aussi sur la manière de les interroger.

Contrairement au monde relationnel, qui s’est convergé précocement vers SQL et l’a conservé comme standard dominant pendant des décennies, l’écosystème des graphes a engendré une prolifération de langages:

Cypher^[1], créé chez Neo4j, représente les motifs en ASCII art:
(a:Person)-[:KNOWS]->(b:Person) ;
Gremlin^[2], issu d’Apache TinkerPop, est impératif et basé sur des étapes:
g.V().hasLabel('Person').out('KNOWS') ;
PGQL^[3], d’Oracle, intègre les motifs de graphe dans une enveloppe de type SQL ;
Et en 2024, GQL^[4] a été ratifié comme norme ISO/IEC 39075, le premier nouveau langage de requête de base de données à atteindre une standardisation ISO depuis SQL lui-même.

Pour cette série, le plus pertinent est SQL/PGQ^[5], standardisé dans SQL:2023. C’est une extension de SQL qui permet de définir des graphes à propriétés sur des tables existantes et de les interroger avec une syntaxe de motifs de type GQL/PGQL intégrée dans un SELECT standard.

À quel point SQL est-il bon pour les graphes ?

Prenons un réseau social stocké dans deux tables: person et knows.
Une requête Cypher qui cherche les amis d’amis ressemble à:

 MATCH (a:Person)-[:KNOWS]->(b)-[:KNOWS]->(c)
 WHERE a.name = 'Alice'
RETURN c.name

L’équivalent en SQL pur est une double jointure croisée:

SELECT DISTINCT c.name
  FROM person a
  JOIN knows k1 ON k1.src = a.id
  JOIN person b ON k1.dst = b.id
  JOIN knows k2 ON k2.src = b.id
  JOIN person c ON k2.dst = c.id
 WHERE a.name = 'Alice';

Ce n’est pas mal. C’est verbeux, mais c’est expressible, le JOIN est explicite, et que ce soient deux sauts ou dix, chaque saut est conciste à écrire d’avantage de JOINs.

Essayons quelque chose de plus centré sur les graphes maintenant. Supposons que nous voulons toutes les personnes atteignables depuis Alice en cinq sauts KNOWS. En SQL/PGQ (très similaire à Cypher), c’est un seul motif:

SELECT c.name
  FROM GRAPH_TABLE(
          social_graph
    MATCH (a IS Person WHERE a.name = 'Alice')-[IS KNOWS]->{1,5}(c IS Person)
  COLUMNS (c.name)
) AS g;

En SQL, cela devient un peu lourd:

WITH RECURSIVE reachable(id, depth, path) AS (
    SELECT p.id
         , 0
         , ARRAY[p.id]
      FROM person p
     WHERE p.name = 'Alice'
    UNION ALL
    SELECT k.dst
         , r.depth + 1
         , r.path || k.dst
      FROM reachable r
      JOIN knows k ON k.src = r.id
     WHERE r.depth < 5
       AND k.dst <> ALL(r.path)
)
SELECT DISTINCT p.name
  FROM reachable r
  JOIN person p ON p.id = r.id
 WHERE r.depth > 0;

L’auteur encode désormais la limite de profondeur, transporte le chemin dans un tableau pour éviter les cycles, et retire la ligne racine à la fin. PostgreSQL 14 a ajouté les clauses SEARCH et CYCLE^[6] qui masquent une partie de cette gestion administrative, mais la requête reste un calcul de point fixe récursif qui arrive à produire le bon résultat.

Bien que ce soit un parcours de graphe basique, les choses deviennent encore plus complexes. Pour les plus courts chemins, il faudrait suivre la distance et faire du “pruning”. Si on demande un tracé (pas de répétition d’arêtes), il faudrait suivre les arêtes, pas seulement les sommets.

Définir et interroger un graphe en SQL/PGQ

À partir d’ici, nous utilisons un exemple plus riche, situé dans la galaxie Star Wars. Les Jedi combattaient sur des planètes, et les Sith sur des stations. Les tables de sommets sont jedi, sith, planet et station, chacune avec un id et un name, plus un title pour les combattants et une region pour les lieux. Deux tables d’arêtes, fought_on_planet et fought_on_station, contiennent chacune un identifiant source, un identifiant destination, et le nom de la bataille.

CREATE TABLE jedi (
    id     BIGINT PRIMARY KEY,
    name   TEXT,
    title  TEXT
);

CREATE TABLE sith (
    id     BIGINT PRIMARY KEY,
    name   TEXT,
    title  TEXT
);

CREATE TABLE planet (
    id      BIGINT PRIMARY KEY,
    name    TEXT,
    region  TEXT
);

CREATE TABLE station (
    id      BIGINT PRIMARY KEY,
    name    TEXT,
    region  TEXT
);

CREATE TABLE fought_on_planet (
    a       BIGINT REFERENCES jedi (id),
    b       BIGINT REFERENCES planet (id),
    battle  TEXT,
    PRIMARY KEY (a, b)
);

CREATE TABLE fought_on_station (
    a       BIGINT REFERENCES sith (id),
    b       BIGINT REFERENCES station (id),
    battle  TEXT,
    PRIMARY KEY (a, b)
);

Le graphe est déclaré sur celles-ci:

CREATE PROPERTY GRAPH galaxy
    VERTEX TABLES (
        jedi    KEY (id) LABEL force_user PROPERTIES (id, name, title),
        sith    KEY (id) LABEL force_user PROPERTIES (id, name, title),
        planet  KEY (id) LABEL place      PROPERTIES (id, name, region),
        station KEY (id) LABEL place      PROPERTIES (id, name, region)
    )
    EDGE TABLES (
        fought_on_planet
            SOURCE KEY (a)      REFERENCES jedi (id)
            DESTINATION KEY (b) REFERENCES planet (id)
            LABEL fought_at     PROPERTIES (battle),
        fought_on_station
            SOURCE KEY (a)      REFERENCES sith (id)
            DESTINATION KEY (b) REFERENCES station (id)
            LABEL fought_at     PROPERTIES (battle)
    );

Les labels regroupent des tables: force_user couvre deux tables de sommets, place en couvre deux, et fought_at couvre les deux tables d’arêtes. Le graphe ne contient aucune donnée.
Dans PostgreSQL, c’est un nouveau type de relation (RELKIND_PROPGRAPH) qui vit dans pg_class sans “heap” (table) et sans colonne propre, ce qui fait qu’il se comporte comme une vue. Cinq nouveaux catalogues (pg_propgraph_element, pg_propgraph_label et trois autres) enregistrent ses éléments, labels et propriétés.

L’interroger:

SELECT *
FROM GRAPH_TABLE (
            galaxy
      MATCH (a IS force_user)-[IS fought_at]->(b IS place)
    COLUMNS (a.name AS fighter, b.name AS battlefield, b.region)
);

Comment fonctionne la réécriture ?

PostgreSQL n’a pas de nouveau nœud “exécuteur”. L’analyseur transforme GRAPH_TABLE en un nouveau type de “range-table”, RTE_GRAPH_TABLE. La réécriture, le même stade qui étend les vues, la remplace ensuite par une sous-requête ordinaire.
Il procède en quatre étapes:

Le motif est lu de gauche à droite dans une liste de motifs d’éléments: sommets, arêtes dans les deux sens, et sous-motifs imbriqués.
Chaque nom de variable unique devient un facteur de chemin. Une variable qui apparaît deux fois, dans un cycle qui retourne à a, partage un même facteur, et ses prédicats sont conjoints par AND.
Chaque expression de label est résolue vers les tables qu’elle couvre, donnant un élément de chemin par table.
Chaque combinaison d’éléments le long du chemin est énumérée par un DFS (recherche en profondeur d’abord) récursif. Une combinaison n’est valide que si les clés source et destination de chaque table d’arêtes relient vraiment les deux tables de sommets voisines. Chaque combinaison valide devient un JOIN entre les tables d’arêtes et de sommets sur ces clés, et toutes sont combinées par UNION ALL.

Dans notre requête, force_user a deux tables, fought_at en a deux, et place en a deux, il y a donc 2 × 2 × 2 = 8 combinaisons. Seulement deux sont valides: un Jedi sur une planète, et un Sith dans une station. La requête devient équivalente à:

SELECT jedi.name, planet.name, planet.region
  FROM jedi, fought_on_planet, planet
 WHERE jedi.id = fought_on_planet.a
   AND planet.id = fought_on_planet.b
UNION ALL
SELECT sith.name, station.name, station.region
  FROM sith, fought_on_station, station
 WHERE sith.id = fought_on_station.a
   AND station.id = fought_on_station.b;

À partir de ce point, le planificateur et l’exécuteur voient des jointures et une union, rien de spécifique aux graphes. Ceci a une certaine valeur car nous bénéficions des index, des statistiques, de l’interrogation parallèle et de tout ce que PostgreSQL possède — ce qui rappelle l’argument que nous faisons dans le précédent article de la série sur les bases de données graphes construites sur des systèmes matures.

Il y a ici une subtilité qui compte pour la lecture de tout benchmark comparant les deux formalismes.

Dans un motif de longueur fixe, SQL/PGQ est obligé de toucher les tables de sommets. Le motif lie les sommets, donc la jointure vers la table de sommets fait partie de la sémantique même lorsqu’aucune propriété de sommet n’est demandée, car il n’y a pas de clés étrangères (FK). Si vous modélisiez le même graphe vous-même en SQL pur et aviez seulement besoin de la traversée des arêtes, à condition d’avoir défini des FK, joindre les tables d’arêtes seules suffit.

Note: il y a un effort récent, non validé, de la part de hackers PostgreSQL pour éliminer les inner joins basés sur les clés étrangères, ce qui serait bénéfique pour la réécriture SQL/PGQ + FK sur les tables élémentaires du graphe^[7].

Ce qui est supporté et ce qui ne l’est pas

La norme recense 100 fonctionnalités. L’implémentation validée en couvrait 26. Elle supporte les motifs graphiques avec WHERE, les motifs de sommets, les motifs d’arêtes sous forme complète et abrégée, la disjonction de labels (label1|label2), les références de propriétés, GRAPH_TABLE, le DDL incluant ALTER et DROP, plusieurs labels par table élémentaire, et les vues comme tables élémentaires.

Les plus intéressantes des 74 manquantes relèvent (pour la plupart) de cinq mécanismes que la norme définit au-dessus d’un motif de base:

Mécanisme	Ce qu’il décide	PostgreSQL
Quantificateurs: `{n,m}`, `{n}`, `+`, `*`	Le nombre de sauts couverts par un motif	Non supporté

Modes de chemin: `WALK`, `TRAIL`, `SIMPLE`, `ACYCLIC`	Quels chemins sont admissibles (quoi qui peut se répéter)	Comporte comme `WALK`, mots-clés rejetés

Préfixes de recherche de chemin: `ALL`, `ANY`, `ALL SHORTEST`, `SHORTEST n`	Quels chemins admissibles sont retournés	Seulement `ALL`, le défaut

Modes de correspondance: `REPEATABLE ELEMENTS`, `DIFFERENT EDGES`	Si les arêtes peuvent se lier deux fois	Seulement `REPEATABLE ELEMENTS`

Plusieurs motifs de chemin séparés par des virgules dans un `MATCH`	Jointure de motifs sur des variables partagées	Patch existant, retardé après les quantificateurs

PostgreSQL n’est pas seul ici. Le SQL/PGQ d’Oracle est tout aussi réduit, DuckPGQ n’ajoute que ANY SHORTEST, et l’ancien PGQL d’Oracle supporte la plupart de ces fonctionnalités.

L’annulation (“git revert”)

SQL/PGQ a été validé le 16 mars 2026 pour PostgreSQL 19. Début septembre, une discussion sur pgsql-hackers concernant certains problèmes dans sa représentation/catalogue et ses dépendances d’objets s’est achevé par une décision de le retirer.
Les reviewers ont estimé qu’il devait être retiré de cette version afin que les problèmes puissent être corrigés proprement pour 20, sans la pression de la compatibilité ascendante.

La fonctionnalité devrait revenir dans une version future. La réécriture elle-même n’est pas la partie en cours de refonte, elle devrait donc survivre, inchangée, ce qui signifie que le travail supplémentaire — VLE (variable length edge), motifs multi-chemins, etc. — pourra s’appuyer sur le même socle.

Il est d’ailleurs à noter que tout cela n’a pas à être nécessairement dans le noyau. PostgreSQL n’a pas de parser hook, donc une extension ne peut pas ajouter de grammaire, et les parser hooks ont été proposés et discutés à maintes reprises sans aboutir. La dernière mention concernait la manière de publier SQL/PGQ comme fonctionnalité expérimentale^[8].
Il ne reste à SQL/PGQ que deux options: travailler dans le noyau, ou faire ce que fait Apache AGE et parser une chaîne à l’exécution ; bien sûr, la deuxième est un élément pour une extension, pas pour une fonctionnalité du noyau.
Si les extensions avaient pu étendre le parseur, cela aurait pu être construit et prouvé hors de l’arbre, puis ensuite considéré pour un module contrib ou pour le noyau. Ce n’est pas un argument en faveur des parser hooks. C’est une observation sur là où le coût de ne pas les avoir finit par peser.

La fonctionnalité que tout le monde réclame

Des morceaux manquants, l’un domine chaque conversation sur les requêtes de graphe: les arêtes de longueur variable (VLE).
C’est la fonctionnalité que les utilisatrices et utilisateurs de graphes réclament en premier, et c’est souvent la raison pour laquelle on se tourne vers un langage de requête de graphe plutôt que d’écrire des jointures. La difficulté est proportionnelle à l’échelle. Un motif borné sur deux ou trois sauts peut être fait avec une réécriture similaire vers des jointures. Un motif pouvant atteindre des centaines de sauts, ou s’exécuter de manière non bornée jusqu’à épuisement du graphe, est un problème différent avec ses propres exigences de mémoire, de terminaison et de gestion des cycles.

La norme rend cela plus difficile qu’il n’y paraît, car elle définit plusieurs mécanismes et fonctionnalités qui interagissent avec elle. Comment le motif s’étend, quels chemins comptent comme admissibles, et lesquels de ceux-ci sont retournés sont décidés indépendamment, et chaque combinaison implique une stratégie d’exécution différente. Tous les chemins sur une profondeur bornée, un seul chemin le plus court, et les extrémités atteignables distinctes sont des motifs différents dont il faut tenir compte dans la conception. Bien sûr, on NE peut PAS tout supporter, mais il est important de garder ces sémantiques en tête.

Les implémentations varient. Une approche est une nouvelle réécriture, cette fois vers des CTE récursifs, s’appuyant sur les clauses SEARCH et CYCLE et faisant beaucoup de gestion administrative directement dans la requête pour les différentes sémantiques. En bout de ligne, c’est un BFS (recherche en largeur) basé sur des ensembles exprimé sous forme de jointures ; c’est acceptable mais ce ne sera ni performant ni flexible à combiner avec d’autres fonctionnalités comme les variables de chemin.

Une autre approche étend chaque longueur possible dans son propre UNION ALL, ce qui ne peut pas gérer le cas non borné. C’est une très mauvaise idée ; Oracle fait ça. Puis il y a les stratégies au niveau de l’exécuteur: DFS avec état de chemin pour le backtracking, ou BFS exécuté directement dans l’exécuteur (tous avec de nouveaux nœuds exécuteur). Chacune est adaptée à un objectif différent, qu’il s’agisse d’accessibilité, de plus court chemin, ou d’énumération de tous les chemins possibles. L’implémentation future prendra en compte toutes celles-ci, autrement on ne peut pas considérer Postgres dans la course, en aucune manière.

Points clés

SQL/PGQ réécrit les motifs de graphe en jointures — pas de nouveaux nœuds exécuteur, pas de moteur de graphe. Le planificateur gère le reste avec les index, les statistiques et l’interrogation parallèle.

L’implémentation validée couvrait 26 des 100 fonctionnalités de la norme, de quoi prouver l’approche mais en s’arrêtant avant les problèmes difficiles. Les quantificateurs, les modes de chemin et les arêtes de longueur variable étaient intentionnellement différés.

L’annulation est lié au “timing”. Les catalogues et le suivi des dépendances nécessitent une base plus propre pour PostgreSQL 20. Le moteur de réécriture lui-même n’est pas en cours de refonte.

La gestion des arêtes de longueur variable est la fonctionnalité requise. La norme définit plusieurs mécanismes au-dessus du VLE qui impliquent différentes stratégies d’exécution — BFS basé sur des ensembles via des CTE récursives, bras UNION ALL par longueur, ou DFS/BFS au niveau de l’exécuteur avec de nouveaux nœuds. Chacune sert un objectif différent.

Sans parser hooks, SQL/PGQ doit vivre dans le noyau ou utiliser un analyseur de chaîne à l’exécution.

Et maintenant ?

Le prochain article examine les autres options de graphes dans PostgreSQL: Apache AGE, pgRouting, et le cas pratique pour ou contre chacune.
Ensuite, un benchmark comparant SQL/PGQ à Apache AGE.
Et enfin, à quoi ressemble la vision à long terme pour les requêtes de graphe dans PostgreSQL, et pourquoi la trajectoire pointe vers l’absorption des charges de travail des graphes dans les systèmes relationnels.