News for hackers. Stuff that matters.

A comment on Postgres: The Graph Database You Didn't Know You Had.

Re:Postgres: The Graph Database You Didn't Know You Had by mdavidn on Friday March 31, 2023 @10:46AM (#35387919)
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.

[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by ellisv on Friday March 31, 2023 @11:19AM (#35388404)
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.

[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by mdavidn on Friday March 31, 2023 @11:25AM (#35388524)
Yes, it is difficult to maintain. That might be a good moment to consider a proper graph database!
[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by ellisv on Friday March 31, 2023 @12:17PM (#35389339)
I’ve considered using a column to store indicate 2nd, 3rd, etc degree relations instead of n-th order tables.
[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by switchbak on Friday March 31, 2023 @12:11PM (#35389263)
"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.

[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by ellisv on Friday March 31, 2023 @01:21PM (#35390135)
If you have an edge list like:

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.

[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by FleaFlicker99 on Friday March 31, 2023 @01:41PM (#35390450)
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.

[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by liotier on Friday March 31, 2023 @12:05PM (#35389158)
> 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 ?

[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by simonw on Friday March 31, 2023 @12:28PM (#35389474)
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.
[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by simonw on Friday March 31, 2023 @12:34PM (#35389545)
I tried it against SQLite. I got ChatGPT to write me a script that would insert 1m edges and 1m nodes:

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...

[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by eurasiantiger on Friday March 31, 2023 @04:50PM (#35393457)
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.
[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by simonw on Friday March 31, 2023 @04:57PM (#35393549)
Go ahead and try it! I've documented all of the tools you need to run some detailed experiments against SQLite entirely in your browser here.
[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by ellisv on Friday March 31, 2023 @01:29PM (#35390263)
It depends a lot on how connected the graph is and whether you can fit it in memory.
[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by afandian on Friday March 31, 2023 @01:14PM (#35390066)
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.
[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by jeremyjh on Friday March 31, 2023 @01:36PM (#35390360)
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.

[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by afandian on Friday March 31, 2023 @06:49PM (#35394813)
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.

[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by Nezteb on Friday March 31, 2023 @01:43PM (#35390473)
I learned from one of the comments on the post about AGE[1], "a PostgreSQL extension that provides graph database functionality."

[1] https://age.apache.org/

[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by cryptonector on Friday March 31, 2023 @04:16PM (#35392952)
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).

[ Parent | on HN ]
Re:Postgres: The Graph Database You Didn't Know You Had by runeks on Saturday April 01, 2023 @12:41PM (#35401674)
> The solution is to build and index denormalized n-th order relationship tables.

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?

[ Parent | on HN ]