5 ms·

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

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.

ellisv 4y ago
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.
- mdavidn 4y ago
  Yes, it is difficult to maintain. That might be a good moment to consider a proper graph database!
  - ellisv 4y ago
    I’ve considered using a column to store indicate 2nd, 3rd, etc degree relations instead of n-th order tables.
- switchbak 4y ago
  "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.
  - ellisv 4y ago
    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.
    - FleaFlicker99 4y ago
      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.
liotier 4y ago
> 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 ?
- simonw 4y ago
  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.
  - simonw 4y ago
    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/c16ce01244760e186a3a0aa3fee0405d 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/simonw/c16ce01244760e186a3a0aa3fee0405d#/data?sql=WITH+RECURSIVE+friend_of_friend+AS+%28%0A++SELECT+edges.next_node%0A++FROM+edges%0A++WHERE+edges.previous_node+%3D+14%0A++UNION%0A++SELECT+edges.next_node%0A++FROM+edges%0A++JOIN+friend_of_friend+ON+edges.previous_node+%3D+friend_of_friend.next_node%0A%29%0ASELECT+nodes.data%0AFROM+nodes%0AJOIN+friend_of_friend+ON+nodes.id+%3D+friend_of_friend.next_node%3B https://lite.datasette.io/?sql=https://gist.github.com/simon...
    - eurasiantiger 4y ago
      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.
      - simonw 4y ago
        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.
afandian 4y ago
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.
- jeremyjh 4y ago
  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.
  - afandian 4y ago
    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.
Nezteb 4y ago
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/ https://age.apache.org/
cryptonector 4y ago
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).
runeks 4y ago
> 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?

ellisv 4y ago

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.

mdavidn 4y ago
Yes, it is difficult to maintain. That might be a good moment to consider a proper graph database!
- ellisv 4y ago
  I’ve considered using a column to store indicate 2nd, 3rd, etc degree relations instead of n-th order tables.
switchbak 4y ago
"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.
- ellisv 4y ago
  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.
  - FleaFlicker99 4y ago
    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.

liotier 4y ago

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

simonw 4y ago
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.
- simonw 4y ago
  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/c16ce01244760e186a3a0aa3fee0405d 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/simonw/c16ce01244760e186a3a0aa3fee0405d#/data?sql=WITH+RECURSIVE+friend_of_friend+AS+%28%0A++SELECT+edges.next_node%0A++FROM+edges%0A++WHERE+edges.previous_node+%3D+14%0A++UNION%0A++SELECT+edges.next_node%0A++FROM+edges%0A++JOIN+friend_of_friend+ON+edges.previous_node+%3D+friend_of_friend.next_node%0A%29%0ASELECT+nodes.data%0AFROM+nodes%0AJOIN+friend_of_friend+ON+nodes.id+%3D+friend_of_friend.next_node%3B https://lite.datasette.io/?sql=https://gist.github.com/simon...
  - eurasiantiger 4y ago
    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.
    - simonw 4y ago
      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.

afandian 4y ago

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.

jeremyjh 4y ago
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.
- afandian 4y ago
  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.

Nezteb 4y ago

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/ https://age.apache.org/

cryptonector 4y ago

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

runeks 4y ago

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