title: Understanding correlation in PostgreSQL
body: <p>When a database has to perform a join to another table, it may broadly choose from one of the three following strategies:</p>
  
  <ul>
  <li>sequential scan (when we want most of the records)</li>
  <li>bitmap index scan (when we want some of the records)</li>
  <li>index scan (when we want relatively few records, with a correlated index)</li>
  </ul>
  
  <p>The reasoning here is that if most records need to be retained, it is more efficient to completely ignore the index, avoid I/O penalties, and just read the entire table sequentially.  At the other extreme, clearly if we just need to read a few leaf nodes from an index, this would be faster than reading the entire table.</p>
  
  <p>What is <em>not</em> clear to me is what role correlation plays here, and how we should be thinking about it.</p>
  
  <p>Focusing on Postgres, the <a href="http://www.postgresql.org/docs/current/static/view-pg-stats.html" rel="nofollow noreferrer">documentation</a> describes correlation here:</p>
  
  <blockquote>
    <p>Statistical correlation between physical row ordering and logical ordering of the column values. This ranges from -1 to +1. When the value is near -1 or +1, an index scan on the column will be estimated to be cheaper than when it is near zero, due to reduction of random access to the disk. (This column is null if the column data type does not have a &lt; operator.)</p>
  </blockquote>
  
  <p>Here is a way by which we can obtain a correlation value for each column in a given table:</p>
  
  <pre><code>SELECT attname, correlation
  FROM pg_stats
  WHERE tablename = 'your_table';
  </code></pre>
  
  <p>From what I understand, using a secondary index <em>always</em> requires doing an I/O seek to the clustered index, to find the data.  As far as I can tell, the only thing which would make I/O better or worse would be if the secondary index were very near to the clustered index on disk.  But it is not clear to me how correlation would be significant for determining how costly an I/O seek is, since a seek is always required.</p>
  
  <p>Can someone give an explanation about what correlation physically means here?  Perhaps my confusion is arising from not understanding how a database performs an index scan.</p>