Skip to main content
Database Administrators

Timeline for How can I efficiently traverse graph data with this pattern?

Current License: CC BY-SA 4.0

15 events
when toggle format what by license comment
May 20, 2023 at 22:15 comment added J.D. @AndriyM It's arguably both ways. Yes, the name edges makes it appropriate, because yes there are 2 edges to node 2. But the way the recursive CTE operates and the way OP is trying to manipulate the data is really treating the edges tables as a nodes table. Each row is the equivalent of a node, from the perspective of a recursive CTE as it recurses each one. This results in row (0, 2) and (1, 2) being different nodes from each other in actuality, creating a tree-like structure.
May 20, 2023 at 17:31 comment added Andriy M I respectfully disagree with the statement in the opening sentence. Your argument is that node 2 is shown once in the image but listed twice in the #edges table. But the reason for the latter is because #edges is not a table of graphs but a table of, well, edges. You can't express the fact that a node is the head to two tails without listing it twice in a table of edges. And there are indeed two edges pointing to node 2 in the image, too. So as far as nodes 0, 1 & 2 are concerned, I believe the provided #edges sample represents the image accurately.
May 20, 2023 at 4:09 comment added alx9r ”…can you store it in a different manner if you wanted to?” - Yes. I have no restrictions on how the graph is represented in SQL Server.
May 20, 2023 at 4:04 history edited J.D. CC BY-SA 4.0
added 250 characters in body
May 20, 2023 at 4:02 comment added J.D. @alx9r Sorry I forgot to ask this in my last comment. Do you have control over the table structure / data that lives in the #edges table, in your actual use case?...can you store it in a different manner if you wanted to?
May 20, 2023 at 3:55 comment added alx9r "...so you want to be able to pick any node, and get the unique list of descendents?" - Yes. Achieving that in less than O(2^n) would be an improvement over what I've attained. " Is there a guarantee that your graph is always acyclic?" - I could live with guaranteed acyclic. I suspect though, that whatever efficient traversal exists could be repurposed to detect cycles.
May 20, 2023 at 3:50 comment added J.D. @alx9r That execution plan is great, thanks! Gotcha, so you want to be able to pick any node, and get the unique list of descendents? Is there a guarantee that your graph is always acyclic?
May 20, 2023 at 1:03 comment added alx9r "Also what is the end goal output you're looking for?" - I think at this point my goal is to efficiently generate a list of descendants of an arbitrary set of anchor nodes for graphs of 1000 nodes comprised of data of the shape in my example. The end goal is substantially more complicated to convey. This fiddle achieves that goal for 29 nodes. The fiddle also show the execution plan. Adding one more node results in a timeout. I have little experience with execution plans so I'm not sure if the execution plan from the fiddle is adequate.
May 19, 2023 at 23:28 comment added J.D. @alx9r The complexity of the SQL Engine makes it very difficult to speculate on the realism of a solution to a problem based on just data size alone (it's kind of a moot point TBH). Again, it's more important to understand what the process is doing under the hood, and where the bottleneck exists, which is usually evident in the execution plan. Could you please add the actual execution plan of your example? Also what is the end goal output you're looking for?... that'll help me conceptualize what you're actually trying to accomplish by only wanting to traverse each node once.
May 19, 2023 at 23:05 comment added alx9r "Just because it's traversing duplicate nodes doesn't necessarily mean the process to get there was inefficient." - I do agree with this in principle. However, increasing the node count causes total_nodes to increase with 2^n. If the CTE emits 2^100 records, it seems like no degree of query efficiency would work.
May 19, 2023 at 22:35 comment added J.D. @alx9r "Would you expect this technique to work with the graph data from my example?" - Unfortunately, shortly after I posted my answer, I was wondering if that solution would be irrelevant here because of how you noted, these aren't duplicates as a result of cyclic ancestor chains, rather it's just separate sibling branches with the same child node. Unfortunately I don't think that solution is applicable here. I'm typing all of this up on my phone at the moment, but when I get a chance to sit down at a computer, I'll be able to conceptualize the problem better.
May 19, 2023 at 22:29 comment added alx9r "So this actually implicitly ends up breaking your graph into a tree instead..." - I agree completely. Is there another way to represent a graph in regular SQL tables? The only methods I've come across ultimately express edges thereby duplicating mentions of nodes.
May 19, 2023 at 22:14 comment added alx9r "If you want to visit each node only once, then you can workaround the redundancy issue by keeping track of nodes that were already visited, on each iteration of the recursion." - Would you expect this technique to work with the graph data from my example? I tried technique you suggested and no reduction of total nodes resulted. This is what I would expect given that iterations comprising each path can only know about its ancestor paths, and not its peers. In the (somewhat contrive) data in the example the duplicates are in peer paths not ancestral paths.
May 19, 2023 at 22:00 comment added alx9r "Is the current implementation unacceptably inefficient?" - yes. Because of the duplication, there are some instances of real-world data I have where 100s of nodes results in millions of records nearly all of which are duplicates, and which takes more than 30 minutes to complete.
May 19, 2023 at 21:24 history answered J.D. CC BY-SA 4.0