title: Efficient implementation of faceted search in relational databases
body: <p>I am trying to implement a <a href="http://en.wikipedia.org/wiki/Faceted_search" rel="noreferrer">Faceted search</a> or tagging with multiple-tag filtering. In the faceted navigation, only not-empty categories are displayed and the number of items in the category that are also matching already applied criteria is presented in parenthesis. </p>
  
  <p><a href="http://forge.mysql.com/wiki/TagSchema#Items_Having_All_of_A_Set_of_Tags" rel="noreferrer">I can get all items having assigned categories using INNER JOINs</a> and <a href="https://stackoverflow.com/questions/1653280/getting-count-of-related-tags">get number of items in all category using COUNT and GROUP BY</a>, however I'm not sure how it will scale to millions of objects and thousands of tags. Especially the counting. </p>
  
  <p>I know that there are some not-relational solutions like <a href="http://lucene.apache.org/solr/" rel="noreferrer">Lucene + SOLR</a>, but I've found also some closed-source RDBMS-based implementations that are said to be entreprise-strength like <a href="http://facetmap.com" rel="noreferrer">FacetMap.com</a> or <a href="http://www.endeca.com/" rel="noreferrer">Endeca</a> software, so there must be an efficient way to perform faceted search in relational databases.</p>
  
  <p>Does anybody have experience in faceted search and could give some tips? </p>
  
  <p>Cache the counts for each category set? Maybe use some smart incremental technique that will update the counters? </p>
  
  <p>Edit:</p>
  
  <p>An example of faceted navigation can be found here: <a href="http://orange.sims.berkeley.edu/cgi-bin/flamenco.cgi/famuseum/Flamenco" rel="noreferrer">Flamenco</a>.</p>
  
  <p>Currently I have the standard 3-table scheme (items, tags and items_tags like described here: <a href="http://www.pui.ch/phred/archives/2005/04/tags-database-schemas.html#toxi" rel="noreferrer">http://www.pui.ch/phred/archives/2005/04/tags-database-schemas.html#toxi</a> ) plus a table for facets. Each tag has assigned a facet.</p>