Hacker News Reader

Comment by mdavidn | Hacker News Reader

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.

View on HN

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.

Yes, it is difficult to maintain. That might be a good moment to consider a proper graph database!

I’ve considered using a column to store indicate 2nd, 3rd, etc degree relations instead of n-th order tables.

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

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.

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.

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/

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

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

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

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.

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.

It depends a lot on how connected the graph is and whether you can fit it in memory.

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

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.

Reply on news.ycombinator.com