title: How can I find close-together points in a PostgreSQL database?
body: <p>I've got a PostgreSQL table of geographic <code>nodes</code>, each of which has a <code>latitude</code> and <code>longitude</code>. If any two nodes are less than 1 km apart, there's a good chance that one of them was created erroneously.</p>
  
  <p><strong>How can I detect this?</strong></p>
  
  <h2>An Extremely Slow Solution</h2>
  
  <p>The "brute force" way is basically, "for each node, examine each other node and see how far it is from the first one. If it's less than 1 km, add the pair to a list."</p>
  
  <p>An SQL implementation would be:</p>
  
  <pre><code>SELECT
    n1.id AS n1_id, n1.latitude AS n1_lat, n1.longitude AS n1_long,
    n2.id AS n2_id, n2.latitude AS n2_lat, n2.longitude AS n2_long
  FROM
    nodes n1
  INNER JOIN nodes n2 ON (
    n1.id != n2.id
    AND earth_distance(
      ll_to_earth(n1.latitude, n1.longitude),
      ll_to_earth(n2.latitude, n2.longitude)
    ) &lt; 1000
  )
  </code></pre>
  
  <p>This is horribly slow; for N nodes, there are roughly N<sup>2</sup> pairs to examine. On my database, it's infeasible to do this.</p>