MySQL storing undirected graph edges efficiently

Question

I want to store undirected graph edges (for example, for friends). To store and retrieve all friends of node a, one can use:

Create two rows per edge, query on one column per node:

+--------------------------+
| id | from_node | to_node |
+--------------------------+
| 1  |  a        |  b      |
| 2  |  b        |  a      |
+--------------------------+
SELECT * FROM `x` WHERE from_node = a

Create one row per edge, use OR:

+--------------------------+
| id | node_a    | node_b  |
+--------------------------+
| 1  |  a        |  b      |
+--------------------------+
SELECT * FROM `y` WHERE node_a = a OR node_b = a

Which makes for more efficient lookups?

• Table x with 2n rows, indices on from_node and to_node, lookup on one column
• Table y with n rows, indices on node_a and node_b, lookup on both columns using OR

Answer 1

This is likely to be far too out of date to be useful, but I'll post incase it helps other people!

I store undirected graphs like your second example and have a constraint that node_a has to be less than node_b. You then trivially place a UNIQUE constraint on the pair and know that the data is consistent. Queries have to a bit more work by compare node_a to the smaller of {a,b} and node_b the other value. PostgreSQL (the DB I know best) provides GREATEST() and LEAST() functions that help here.