3 ms·

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 t

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

by ellisv 4y ago

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.