title: MySQL storing undirected graph edges efficiently
body: <p>I want to store undirected graph edges (for example, for friends). To store and retrieve all friends of node <code>a</code>, one can use:</p>
  
  <p>Create two rows per edge, query on one column per node:</p>
  
  <pre><code>+--------------------------+
  | id | from_node | to_node |
  +--------------------------+
  | 1  |  a        |  b      |
  | 2  |  b        |  a      |
  +--------------------------+
  SELECT * FROM `x` WHERE from_node = a
  </code></pre>
  
  <p>Create one row per edge, use <code>OR</code>:</p>
  
  <pre><code>+--------------------------+
  | id | node_a    | node_b  |
  +--------------------------+
  | 1  |  a        |  b      |
  +--------------------------+
  SELECT * FROM `y` WHERE node_a = a OR node_b = a
  </code></pre>
  
  <p>Which makes for more efficient lookups?</p>
  
  <ul>
  <li>Table <code>x</code> with <code>2n</code> rows, indices on <code>from_node</code> and <code>to_node</code>, lookup on one column</li>
  <li>Table <code>y</code> with <code>n</code> rows, indices on <code>node_a</code> and <code>node_b</code>, lookup on both columns using <code>OR</code></li>
  </ul>