title: Indexing & alternatives for low-selectivity columns
body: <p>What are the range of tactics available for selecting records on low selectivity columns?</p>
  
  <p>An example might be an orders table where, over many years, you build up a large number of completed orders but often need to select active orders. An order might go through a lifecycle such as placed, stock-allocated, picked from warehouse, despatched to customer, invoiced and paid. An order might additionally be cancelled, held, etc. The majority of records will eventually be in the final state (e.g. paid) but you might often need to select, say, allocated orders. In this case a sequential read would be slow.</p>
  
  <p>Similar questions on indexing<br>
  <a href="https://stackoverflow.com/questions/2386852/mysql-low-cardinality-selectivity-columns-how-to-index">MySQL: low cardinality/selectivity columns = how to index?</a><br>
  <a href="https://stackoverflow.com/questions/682161/do-indexes-suck-in-sql">Do indexes suck in SQL?</a><br>
  <a href="https://stackoverflow.com/questions/105400/what-are-indexes-and-how-can-i-use-them-to-optimize-queries-in-my-database">What are indexes and how can I use them to optimize queries in my database?</a><br>
  <a href="https://stackoverflow.com/questions/1954406/defining-indexes-which-columns-and-performance-impact">Defining indexes: Which Columns, and Performance Impact?</a><br>
  and numerous others decreasingly related.</p>
  
  <p>The approaches I have read about (in stackoverflow and elsewhere) include</p>
  
  <ul>
  <li>Use a bitmap index</li>
  <li>Use a partial index (<code>create index x on t(c2) where c1='a'</code>)</li>
  <li>Use a clustered index?</li>
  <li>Don't index low selectivity columns, use sequential read</li>
  <li>Partition the data (e.g. into several tables with identical schema)</li>
  <li>Use a supplementary table (e.g. <code>active_customers(customer_id)</code></li>
  </ul>
  
  <p>My current DBMS doesn't support the first three options listed above and the remainder seem problematic - are there any other commonly used approaches?</p>
  
  <p>Update: I've seen
    - index your low-selectivity column, but only ever select for high-selectivity values.</p>