oqgraph-dev team mailing list archive

[Heinz Wiesinger <HMWiesinger@xxxxxxxxxxx>]

Hi All,

We recently had a situation in our backend system where we ended up with a 
rather large graph (16000 edges for about 800 nodes). We found that a 
particular query we run on our graph didn't perform very well, with average 
runtimes of 10s, tending upwards.

Our graph looks pretty much like a simple tree, and can probably be best 
visualized similarly to a git commit graph. The query we run finds all 
reachable leaf nodes for a given origid. Currently we do this by querying all 
reachable nodes and then filtering the results with a "WHERE NOT IN (SELECT 
origid FROM graph_table)" condition, which works reasonably fast up until 
around 4000/5000 edges and then drastically slows down.

I was wondering if it might be an option to add an algorithm like that 
directly in oqgraph itself, without the need to specify the extra WHERE 
condition, in the hope that that would eliminate the slowdown on larger 
graphs. Something like

SELECT * FROM graph_table WHERE latch="leafs" AND origid=356

I had a quick look at the code to get a grasp of the complexity of that, and 
while I found the location where to put it, I also noticed I don't understand 
much of the code present there currently :)

We (as in the company I work for) might be interested to implement this 
feature, if feasible, but as a first step, I'd just like to hear some opinions 
on this :)

Grs,
Heinz

Attachment: signature.asc
Description: This is a digitally signed message part.