PostgreSQL as a graph database, part 1: SQL/PGQ in PostgreSQL

This is the second post in a series exploring graph databases and PostgreSQL. The first post covered what graphs are, what can be modeled as a graph, and the landscape of graph database systems. This post moves from the general to the specific: how we query graphs, why SQL can be an awkward fit, and what SQL/PGQ changes. It ends with the PostgreSQL implementation, why it was reverted, and a few notes on the main features still to come.

Query languages for graphs

In the previous post, we ended on the observation that graph databases come in many forms, and that they differ in how they store graphs and what data models they support. They also differ in how you question them.

Unlike the relational world, which converged on SQL early and kept it as the dominant standard for decades, the graph ecosystem produced a proliferation of query languages:

• Cypher^[1], created at Neo4j, represents patterns as ASCII art:
  (a:Person)-[:KNOWS]->(b:Person);
• Gremlin^[2], from Apache TinkerPop, is imperative and step-based:
  g.V().hasLabel('Person').out('KNOWS');
• PGQL^[3], from Oracle, embedded graph patterns inside a SQL-like shell;
• And in 2024, GQL^[4] was ratified as ISO/IEC 39075, the first new database query language to reach ISO standardization since SQL itself.

For this series, the relevant one is SQL/PGQ^[5], standardized as part of SQL:2023. It is an extension of SQL that lets you define property graphs over existing tables and query them with GQL- and PGQL-like pattern syntax inside a standard SELECT.

How good is SQL for graphs ?

Consider a social network stored in two tables: person and knows.
A Cypher query asking for friends of friends looks like this:

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

The equivalent in plain SQL is a two-way self-join:

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';

That is not bad. It is verbose, but it is expressible, the JOIN is explicit, and whether it is two hops or ten hops, each is a matter of writing more JOINs.

Let’s try something a bit more graph-centric now. Suppose we want all people reachable from Alice within five KNOWS hops. In SQL/PGQ (very similar to Cypher) that is a single pattern:

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;

In SQL, things become a bit uglier:

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;

The author now encodes the depth limit, carries the path in an array to avoid cycles, and removes the seed row at the end. PostgreSQL 14 added SEARCH and CYCLE clauses^[6] that hide some of this bookkeeping, but the query is still a recursive fixpoint computation that happens to produce the right answer.

Though this is a basic graph pattern, things get even trickier. For shortest paths, we would need to track distance and prune. Asking for a trail (no repeated edges), and we would have to track edges, not just nodes.

Defining and querying a graph in SQL/PGQ

From here on, we use a richer example, set in the Star Wars galaxy. Jedi fought on planets, and Sith fought at stations. The vertex tables are jedi, sith, planet, and station, each with an id and a name, plus a title for the fighters and a region for the places. Two edge tables, fought_on_planet and fought_on_station, each hold a source id, a destination id, and the name of the battle.

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)
);

The graph is declared over them:

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)
    );

Labels group tables: force_user covers two vertex tables, place covers two, and fought_at covers both edge tables. The graph holds no data.
In PostgreSQL it is a new kind of relation (RELKIND_PROPGRAPH) that lives in pg_class with no heap and no columns of its own, so it behaves like a view. Five new catalogs (pg_propgraph_element, pg_propgraph_label and three more) record its elements, labels, and properties.

Querying it:

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)
);

How the rewrite works ?

PostgreSQL has no new executor node. The parser turns GRAPH_TABLE into a new range table entry kind, RTE_GRAPH_TABLE. The rewriter, the same stage that expands views, then replaces it with an ordinary subquery.
It does this in four steps:

1. The pattern is read left to right into a list of element patterns: vertices, edges in either direction, and nested sub-patterns.
2. Each unique variable name becomes one path factor. A variable that appears twice, as in a cycle that returns to a, shares one factor, and its predicates are ANDed.
3. Each label expression is resolved to the tables it covers, giving one path element per table.
4. Every combination of elements along the path is enumerated by a recursive DFS (Depth-First Search). A combination is valid only if each edge table’s source and destination keys really connect the two neighboring vertex tables. Each valid combination becomes a JOIN between edge and vertex tables on those keys, and all of them are combined with UNION ALL.

In our query, force_user has two tables, fought_at has two, and place has two, so there are 2 × 2 × 2 = 8 combinations. Only two are valid: a Jedi on a planet, and a Sith at a station. The query becomes equivalent to this:

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;

From this point, the planner and executor see joins and a union, nothing graph-specific. This is somewhat valuable because we benefit from indexes, statistics, parallel query, and everything else PostgreSQL has, which recalls the argument we made in the previous blog in the series about graph capabilities on top of mature systems.

There is a subtlety here that matters for how you read any benchmark comparing the two formalisms.

In a fixed-length pattern, SQL/PGQ is obliged to touch the vertex tables. The pattern binds vertices, so the join to the vertex table is part of the semantics even when no vertex property is requested, because there are no foreign keys (FKs). If you model the same graph yourself in plain SQL and only need the edge traversal, provided that you define FKs, joining the edge tables alone is enough.

Note: There’s a recent non-committed effort from PostgreSQL hackers to remove inner joins based on foreign keys, which is beneficial for SQL/PGQ + FKs on base graph element tables rewrite^[7].

What’s Supported and What’s Not

The standard tracks 100 features. The committed implementation had 26 of them. It supports graph patterns with WHERE, vertex patterns, edge patterns in full and abbreviated form, label disjunction (label1|label2), property references, GRAPH_TABLE, the DDL including ALTER and DROP, several labels per element table, and views as element tables.

The most interesting ones out of the other 74 it lacks fall (mostly) into five mechanisms that the standard defines on top of a basic pattern:

PostgreSQL is not alone here. Oracle’s SQL/PGQ is similarly narrow, DuckPGQ adds only ANY SHORTEST, and Oracle’s older PGQL supports most of these features.

The revert

SQL/PGQ was committed on March 16, 2026, for PostgreSQL 19. In early September, a pgsql-hackers thread on some issues in its catalog representation/definition and object dependencies ended with a decision to take it out.
Reviewers argued it should be reverted from 19 so the problems could be fixed properly and easily for 20, without backwards-compatibility pressure.

The feature is expected back in an upcoming version. The rewrite itself is not the part being redesigned, so it should survive the rework unchanged, which means further work, VLE (variable length edge), multi-path patterns, etc. can be built on top of the same foundation.

It is worth noting that none of this had to happen in the core at all. PostgreSQL has no parser hook, so an extension cannot add grammar, and parser hooks have been proposed and discussed repeatedly without landing. The latest mention was about how to release SQL/PGQ as an experimental feature^[8].
That leaves SQL/PGQ with only two options: work inside core, or do what Apache AGE does and parse a string at runtime; of course, the latter is something for an extension, not a core feature.
Had extensions been able to extend the parser, this could have been built and proven outside the tree, and only then considered for a contrib module or for core. That is not an argument that parser hooks should exist. It is an observation about where the cost of not having them ends up.

The feature everyone asks for

Of the missing pieces, one dominates every conversation about graph queries: variable-length edges (VLE).
It is the feature graph practitioners ask for first, and it is often the reason someone reaches for a graph query language instead of writing joins. The difficulty is proportional to the scale. A bounded pattern over two or three hops can be done with a similar rewrite to joins. A pattern that can reach hundreds of hops, or run unbounded until it exhausts the graph, is a different problem with its own memory, termination, and cycle-handling requirements.

The standard makes this harder than it looks, because it defines several mechanisms and features that interact with it. How far the pattern goes, which paths count as admissible, and which of those are returned are decided independently, and each combination implies a different execution strategy. All paths over a bounded depth, a single shortest path, and distinct reachable endpoints are different patterns we should think of in design. Of course, one can NOT support everything, but it’s important to keep such semantics in mind.

Implementations vary. One approach is another rewrite, this time to recursive CTEs, leaning on SEARCH and CYCLE clauses and doing a lot of the bookkeeping in the query itself for the different semantics. At the end of the day, it is set-based BFS (breadth-first search) expressed as joins; this is mostly okay but it won’t be any performant or flexible to work with in combination with any other features like path variables.

Another approach expands each possible length into its own UNION ALL arm, which cannot handle the unbounded case. This is a very bad idea; Oracle does this. Then there are executor-level strategies: DFS with path state held for backtracking, or BFS run directly in the executor (all with new executor nodes). Each is suited to a different goal, whether that is reachability, shortest path, or enumerating all possible paths. The future implementation will consider all of these, otherwise we can’t consider Postgres as a competitor, at all.

Key Takeaways

SQL/PGQ rewrites graph patterns to joins — no new executor nodes, no graph engine. The planner handles the rest with indexes, statistics, and parallel query.

The committed implementation covered 26 of 100 standard features, enough to prove the approach but stopping before the hard problems. Quantifiers, path modes, and variable-length edges were intentionally deferred.

The revert was about timing. Catalogs and dependency tracking need a cleaner foundation for PostgreSQL 20. The rewrite engine itself is not being redesigned.

Variable-length edges management is the required feature. The standard defines multiple mechanisms on top of VLE that imply different execution strategies — set-based BFS via recursive CTEs, per-length UNION ALL arms, or executor-level DFS/BFS with new nodes. Each serves a different goal.

Without parser hooks, SQL/PGQ must live in core or use runtime string parsing.

What’s Next?

The next post looks at the other graph options in PostgreSQL: Apache AGE, pgRouting, and the practical case for or against each.
After that, a benchmark comparing SQL/PGQ against Apache AGE.
And finally, what the long-term picture looks like for graph queries in PostgreSQL, and why the trajectory points toward relational systems absorbing graph workloads.