Search code examples
mysqlgraphlarge-data

MySQL Reciprocal Search

I have a table which stores the edges of a directed graph like so:

Table EDGES
  FROM_NODE | TO_NODE | STRENGTH
  1         | 1       | 8
  1         | 2       | 5
  2         | 1       | 4
  1         | 3       | 2
  3         | 4       | 1

And I'm trying to search for edges which are supported in both directions with strength > 3. In the example above, 1 -> 2 and 2 -> 1 both exist, however, 1 <-> 3 does not exist in both directions. 1 -> 1 doesn't count, for obvious reasons.

The major complication is that there are over 1,000,000 edges to search, and all the queries I have tried so far fail before I can check if they've worked.

Any suggestions would be greatly appreciated!

Solution

  • To me the most straightforward solution is something like: 

    select one.from_node, one.to_node 
from edges one 
join edges other on (one.to_node = other.from_node AND one.from_node = other.to_node)
where one.strength > 3 AND other.strength > 3
    AND one.from_node <> one.to_node

    If you have a lot of data, than it's might be a good idea to reconsider indexes on the table and raise the execution limit.

    Here is an sql fiddle to check the query.