title: Estimating number of results from a MySQL "SELECT WHERE EXISTS" query?
body: <p>I have a simple database of "things" that can have zero or more "categories" or "tags" .  I've written a stored procedure that will get the first N objects in a given category, and performance is very good.  It looks something like</p>
  
  <pre><code>SELECT * FROM things
  WHERE things.datestamp &gt; @start AND things.datestamp &lt; @end
    AND EXISTS (
      SELECT 1 from thing_tags
      WHERE things.id = thing_tags.thing_id
        AND thing_tags.tag = @searchTag
    )
  LIMIT ?
  </code></pre>
  
  <p>With a few hundred thousand "things", each having about 0-5 tags, performance is fine -- I can get the first couple hundred matches in tens of milliseconds at most.</p>
  
  <p>However, if I want to know how many total matches there are, it takes ages -- many seconds, at least.  Is there a smarter way than just <code>SELECT COUNT(id) FROM .... (rest of query above)</code>?  The <code>id</code> field is indexed, per <a href="http://www.cloudspace.com/blog/2009/08/06/fast-mysql-innodb-count-really-fast/" rel="nofollow">this suggestion</a>, but the index doesn't help much since it has to inspect the <code>tags</code> table for each row in <code>things</code>.</p>
  
  <p>I'm looking at implementing pagination, and I know <code>LIMIT ?,?</code> (or <code>LIMIT ? OFFSET ?</code>) would make it easy, but it would be nice to show the user an approximation at least of how many total "matches" to expect.</p>