oqgraph-dev team mailing list archive

[Arjen Lentz <arjen@xxxxxxxxxxxxxxxx>]

Hi Heinz

On 22/01/16 21:48, Heinz Wiesinger wrote:
> 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 :)

I'm all for implementing new algorithms.

But in this case, it shouldn't be necessary.
The current codebase already offers a query for finding all nodes below
origid.


Regards,
Arjenn.
-- 
Arjen Lentz, Exec.Director @ Open Query (http://openquery.com.au)
Australian peace of mind for your MySQL/MariaDB infrastructure.

Follow us http://openquery.com.au/blog/ & http://twitter.com/openquery