oqgraph-dev team mailing list archive
Mailing list archive
Re: Adding new algorithm to oqgraph
Arjen Lentz <arjen@xxxxxxxxxxxxxxxx>
Mon, 25 Jan 2016 13:07:30 +1000
Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.5.1
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
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