Over time I've come to take this a step further. I feel people reach for a graph database way too early. Most use cases that most people have will work fine in a standard relational setup. And that brings with it the benefits of using technologies like Postgres that have stood the test of time. So I treat it as I do any performance consideration: first demonstrate that you actually need to go down the path less traveled, don't just assume you need to do so.
I do love PostgreSQL, and I often reach for this approach when working with hierarchical data, but a word of warning: Recursive queries will not scale to handle _very_ large edge tables. The recursive query will always consider _all_ edges, even when the outer query seeks only a single node's relationships. The solution is to build and index denormalized n-th order relationship tables.
Others have already pointed out the issues of cycles.
It's not even that it always considers all edges, but that you can't exit the search early when a condition is met. In other words, you have to first find all the paths and then, outside the CTE, filter to the shortest. We push the node filter into the CTE by wrapping it in a function.
> The solution is to build and index denormalized n-th order relationship tables.
This sounds much more performant but also more difficult to maintain.
"you can't exit the search early when a condition is met" - I have a DAG traversal written in a recursive CTE, and I can bail early out just fine when my traversal predicates no longer match. Not sure why I'd have to do that outside the (recursive part of the) CTE?
Obviously maintaining a flattened version is going to perform better in queries, but you're trading maintenance (write) time for query time. Or materialization time if you decide to do it lazily.
Postgres will walk both paths from A to D in the recursive CTE and then you can filter them afterwards to keep only the shortest.
You can use aggregate functions within the recursive CTE, so you can’t GROUP BY your starting node and stop once you find the first path. There isn’t a way to compare across multiple paths or iterations of the for-loop.
Ok but that's a little different than saying you can't cut the traversal short.
If I'm traversing ancestors (let's say) until I find one that doesn't satisfy a condition, it'll bail out then. I get that this doesn't serve all uses cases, but it isn't a small thing either.
> Recursive queries will not scale to handle _very_ large edge tables
What do you consider large ? We have a 12-year old telco application with a few million objects in Neo4J, doing fault impact calculations... Would PostgreSQL handle that easily nowadays ?
My hunch is that a few million objects is pretty tiny these days - you could probably write a script to import all of them into PostgreSQL in a few minutes and try it out yourself to see how it behaves.
Not very realistic example, you need to be requesting some actual fields across nodes and doing some filtering on at least strings and dates, maybe geo areas as well.
I'm sorry could you spell it out? What exactly does "recursive query will always consider _all_ edges" mean? A table scan? I'd be very grateful if you could give some pesudocode or point to a doc page.
I think GP means that it has to completely expand the recursive part for every branch before any where condition on the edge nodes can be applied. Graph databases presumably can optimize this.
I've found recursive queries to be difficult to scale in real-world queries past a few million edge nodes. We've denormalized several tree relationships so that the edge is connected both to its parent and to the root of its tree in several cases.
Thanks! Sounds like you're saying that brute-force recursive algorithms without backtracking or early termination aren't a good match for path finding. That's not a surprise.
I'm using recursive algorithm on Postgres to find trees in a graph, but only where I'm specificaly interested in all of the nodes.
Cycles are not a problem: just use `UNION`, not `UNION ALL`.
I myself build transitive closure tables that I update incrementally as needed (sometimes in a deferred way), so that many of the recursive queries I do can be very fast, but I only build transitive closures for the smallest portion I can (basically group nesting).
Of course relational db can act like a graph db. It's just not as efficient due to how things are stored and queried. Would be great to have a graph db plugin (and I found one https://github.com/apache/age)
Having first class pagerank and shortest path functions in tinkerpop gremlin vs having to roll it yourself with recursive CTEs feels like a graph DB win.
In my experience Postgres works really with a Recursive CTE inside a Materialized View for Graphs. Latest version can detect cycles. I used to add a distance column as well, to show number of hops apart, any 2 nodes are.
Hoping Postgres adds Automatic Incremental Mat View Maintenance soon, it will be perfect then as a Graph Database.
I've done this on many occasions, but I actually only go with a single nodes table.
Schema is like this
id
type: string (or enum)
data: jsonb
indexed: jsonb (but this one gets a GIN index)
toId: nullable foreign key to this same table
fromId: nullable foreign key to this same table
createdAt: date
updatedAt: date
So if I had a post with a comment on it, the data would look something like this
Yes, but the downside of your schema is that the distinction between nodes and edges is somewhat muddled.
Presumably, all nodes would have nulls in both fromId and toId, but the schema doesn't enforce that. The schema also allows linking edges to other edges.
Don't you think this is a bit too much flexibility if the intention is to model a graph?
It's a good tool as long as your queries are simple, and your graph isn't too large (which is probably the case 99% of the time). And if that allows you to have one less tool to deal with, go for it!
But I've tried to push it to its limits (using PostGIS, my nodes being land plots that were connected to each others — the biggest query used joins, lateral, recCTE, windows… you name it) and ran into many issues: can't branch out early, hard to optimize, no support for complex queries (writing anything beyond BFS and DFS is a pita). Yet, in the end I accepted the struggle (and the long queries) because it was so nice to work with my data directly where it was kept :)
Using the built-in PostGIS topology tools? Or something more custom? I'm curious as I just started digging into and using PostGIS for a land parcel use case. I've wondered about the graph structure of parcels adjacent to others, rather than just a big unordered table of geom objects.
Just using the geography stuff and doing joins on ST_Intersects. I couldn't guarantee that my data formed a partition of the plane, which is necessary for topology iirc.
Fun was had and headaches too. The biggest speedup I got was computing the graph online (creating a node/vertices tables from geometries) and then doing the recursive CTE on that table.
We used the "WITH RECURSIVE" basically the moment it shipped in Postgres for the original CoreOS Clair[0] data model which was a graph of software versions and vulnerabilities.
It scaled well compared to a naive graph abstraction implemented outside the database, but when performance wasn't great, it REALLY wasn't great. After running that version in production for a couple years, we ended up throwing it out and remodeling the domain to be less graph-y to achieve more consistent performance.
I've since worked on SpiceDB[1] which scales much better by taking the traditional design approach for graph databases and only treating Postgres as triple-store. IME, there's no short-cut: if you need a graph, you probably want to use a database optimized for graph access patterns. Most general-purpose graph databases are full of optimizations for common traversals that are uncommon operations in relation databases.
As a C# guy, I’ve figured out how to build in-memory graphs with generics and dsl/fluid queries. I’m working on a blog entry about it because it’s such a powerful skill to learn and leverage. No data store required. I can deserialize/serialize the data structure to/from binary or json.
Johan wrote the original Neo4j implementation as a graph layer on top of Postgres, random trivia. Then Java released NIO, he got excited and tried replacing the PG engine with one built for graphs from scratch.
Only remotely relevant, but I have recently come across Gremlin, a sort of “SQL for graphs”. Does anyone have some experience with it they can share? I only used it on an in-memory graph database, and I found it quite great so far.
Tinkerpop/Gremlin is not really SQL-like at all. My experience with it has not been fun: it's difficult to reason about, has obscenely bad documentation, poor tooling, idiosyncratic library support, and simple data access patterns are hard.
I mirror the sibling comment's experience: it was a tire fire; also, if one comes from an n-tier application mental model, it's further bad news because the actual query's compute runs _client side_ -- there is no such thing as "connect to Gremlin 'database,' submit query text, have it run queries" it's rather "boot up Gremlin in your appserver, run queries so long as your appserver can connect to every one of the data stores it references, credentials included"
"However, recursive SQL queries can be expected to perform comparably for 'find immediate descendants' queries, and much faster for other depth search queries, and so are the faster option for databases which provide them, such as PostgreSQL,..."
any suggestions for getting nice graph db-style functionality out of an postgres schema, where you've got the nodes and edges of a labelled property graph spread across a bunch of different tables? (AGE seems to want to create a separate graph object that lives alongside your other tables, and toy examples like this article just dump everything into special tables)
in my particular case i don't actually have a lot of data so i'm not looking for performance, just want to save developer time.
We accomplish similar with SchemafreeSQL. Currently MySQL 8 back-end but working on other SQL back-ends. This demo uses PlanetScale as the DB back-end, Fly.io handles the SFSQL endpoint, Netlify function handles the query, and cytoscape.js graph network library for the UI
Thanks !! We had hoped to use PS for our serverless backend and also offer a dedicated PS option. But we ran into some issues with Vitess. I was just thinking today I wanted to get back into it and see if we can resolve these issues. We had to go with Aurora.
The issues were on deletes. This demo is read only so it works well with a PS backend. My experience with your CS has been amazing despite these issues!!
Small nitpick but I wish the author just made `data` a JSONB field rather than VARCHAR. That really shows the power of Postgres, being able to operate as a "NoSQL graph DB" with little to no hacking.
Hey, author here! Thanks for the feedback! I went back and forth with having `data` being a JSONB field or VARCHAR, but ended up with VARCHAR to show that `nodes` don't have to be anything crazy. Really `nodes` is just a standard table you'd see in any old SQL database, and what makes it a "graph" is the `edges`/relationship table.
Few suggestions based on my prior experience on the same task in production system:-
1. Both the tables (Nodes and Edges) MUST HAVE one more column as "label" and then you must create partitions based on distinct values of "label" column. This greatly helps queries to run faster as search plan is narrowed when you include it in where clause and PG knows partitions to hit.
2. Instead of one big fat primary key column in each table use, consider having different uniques indexes on each partition.
3. The EDGES table can afford to have "data" column of data type TEXT or perhaps JSONB. PG saves it in different data disk layout and compression works great here. We used it to cache the result for previous/next nodes data or compute the result for many extra hops which are required on frequent basis.
4. Use PG procedures to hide the complexity of reusable DFS/BFS queries.
147 comments
[ 2.5 ms ] story [ 209 ms ] threadhttps://www.postgresql.org/docs/current/queries-with.html#QU... the docs themselves do have information about it.
[1] https://engineering.fb.com/2013/06/25/core-data/tao-the-powe...
Others have already pointed out the issues of cycles.
> The solution is to build and index denormalized n-th order relationship tables.
This sounds much more performant but also more difficult to maintain.
Obviously maintaining a flattened version is going to perform better in queries, but you're trading maintenance (write) time for query time. Or materialization time if you decide to do it lazily.
A->B
A->D
B->C
C->D
Postgres will walk both paths from A to D in the recursive CTE and then you can filter them afterwards to keep only the shortest.
You can use aggregate functions within the recursive CTE, so you can’t GROUP BY your starting node and stop once you find the first path. There isn’t a way to compare across multiple paths or iterations of the for-loop.
If I'm traversing ancestors (let's say) until I find one that doesn't satisfy a condition, it'll bail out then. I get that this doesn't serve all uses cases, but it isn't a small thing either.
What do you consider large ? We have a 12-year old telco application with a few million objects in Neo4J, doing fault impact calculations... Would PostgreSQL handle that easily nowadays ?
https://gist.github.com/simonw/c16ce01244760e186a3a0aa3fee04...
Then I ran that query again and it seems to return results in about 80ms:
https://lite.datasette.io/?sql=https://gist.github.com/simon...
I've found recursive queries to be difficult to scale in real-world queries past a few million edge nodes. We've denormalized several tree relationships so that the edge is connected both to its parent and to the root of its tree in several cases.
I'm using recursive algorithm on Postgres to find trees in a graph, but only where I'm specificaly interested in all of the nodes.
[1] https://age.apache.org/
I myself build transitive closure tables that I update incrementally as needed (sometimes in a deferred way), so that many of the recursive queries I do can be very fast, but I only build transitive closures for the smallest portion I can (basically group nesting).
Can you elaborate on this?
Does an n-th order relationship table contain all the nodes reachable from some node going through n edges?
And you'd have one such table for each integer in the range 2..n?
https://en.wikipedia.org/wiki/Hierarchical_and_recursive_que...
If Postgres added it, almost all of my interest in Materialize (the database, not the technique) would vanish immediately.
Schema is like this
So if I had a post with a comment on it, the data would look something like this And now for the edges: So then, for example, if I have a post, and I want to find the comments on it, I search for toId = <my post id>, type = '(posts < comments)'.Presumably, all nodes would have nulls in both fromId and toId, but the schema doesn't enforce that. The schema also allows linking edges to other edges.
Don't you think this is a bit too much flexibility if the intention is to model a graph?
The recursive query is cool, but how is the performance for graph queries compared to a DB optimized for this use case ?
But I think Postgres is likely to get these improvements in a few years too.
I ported the example in this tutorial to SQLite here - now you can play with it in Datasette Lite: https://lite.datasette.io/?sql=https%3A%2F%2Fgist.githubuser...
Amusingly I ported the sample PostgreSQL code using the new ChatGPT "Browsing" alpha, with the following prompt:
> Read this tutorial and then output equivalent create table and insert statements for SQLite https://www.dylanpaulus.com/posts/postgres-is-a-graph-databa...
With the static database trick, combined with recursive graphs
Anyone know of good docs for this sort of pattern with SQL that addresses those two common tasks?
as well as chapter 27 of SQL for Smarties, 5th
isn't ISO working on an graph extension to regular SQL? Can't seem to google it correctly
But I've tried to push it to its limits (using PostGIS, my nodes being land plots that were connected to each others — the biggest query used joins, lateral, recCTE, windows… you name it) and ran into many issues: can't branch out early, hard to optimize, no support for complex queries (writing anything beyond BFS and DFS is a pita). Yet, in the end I accepted the struggle (and the long queries) because it was so nice to work with my data directly where it was kept :)
Fun was had and headaches too. The biggest speedup I got was computing the graph online (creating a node/vertices tables from geometries) and then doing the recursive CTE on that table.
I've since worked on SpiceDB[1] which scales much better by taking the traditional design approach for graph databases and only treating Postgres as triple-store. IME, there's no short-cut: if you need a graph, you probably want to use a database optimized for graph access patterns. Most general-purpose graph databases are full of optimizations for common traversals that are uncommon operations in relation databases.
[0]: https://github.com/quay/clair
[1]: https://github.com/authzed/spicedb
https://dimagi.github.io/django-cte/#recursive-common-table-...
1-star, hate, will quit before using it again
"However, recursive SQL queries can be expected to perform comparably for 'find immediate descendants' queries, and much faster for other depth search queries, and so are the faster option for databases which provide them, such as PostgreSQL,..."
in my particular case i don't actually have a lot of data so i'm not looking for performance, just want to save developer time.
https://harmonious-mermaid-c4d794.netlify.app/got (sorry not mobile friendly but functional)
The issues were on deletes. This demo is read only so it works well with a PS backend. My experience with your CS has been amazing despite these issues!!
So, is this basically running transitive closure on the database during query? it would be expensive.
1. Both the tables (Nodes and Edges) MUST HAVE one more column as "label" and then you must create partitions based on distinct values of "label" column. This greatly helps queries to run faster as search plan is narrowed when you include it in where clause and PG knows partitions to hit.
2. Instead of one big fat primary key column in each table use, consider having different uniques indexes on each partition.
3. The EDGES table can afford to have "data" column of data type TEXT or perhaps JSONB. PG saves it in different data disk layout and compression works great here. We used it to cache the result for previous/next nodes data or compute the result for many extra hops which are required on frequent basis.
4. Use PG procedures to hide the complexity of reusable DFS/BFS queries.