As with any PostgreSQL question, the first place you should look for answer is the PostgreSQL docs. I was recently reviewing the EXPLAIN docs as freshen up on some query tuning fu and I came across this little gem:

EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 100;

                                  QUERY PLAN
------------------------------------------------------------------------------
 Bitmap Heap Scan on tenk1  (cost=2.37..232.35 rows=106 width=244)
   Recheck Cond: (unique1 < 100)
   ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..2.37 rows=106 width=0)
         Index Cond: (unique1 < 100)

What the above says (per the docs) is :

Here the planner has decided to use a two-step plan: the bottom plan node visits an index to find the locations of rows matching the index condition, and then the upper plan node actually fetches those rows from the table itself. Fetching the rows separately is much more expensive than sequentially reading them, but because not all the pages of the table have to be visited, this is still cheaper than a sequential scan. (The reason for using two levels of plan is that the upper plan node sorts the row locations identified by the index into physical order before reading them, so as to minimize the costs of the separate fetches. The "bitmap" mentioned in the node names is the mechanism that does the sorting.)

In short we go to the index and find out what tuples match the Index condition (unique1 < 100). What I didn't understand and what the docs didn't tell me was since the index already tells me which tuples meet the condition I had to recheck the condition in the upper node (Recheck Cond: (unique1 < 100). After a little investigation and help from Neil Conway I found the reason. A Bitmap scan is lossy and as the number of tuples returned from the scan increases PostgreSQL will switch from a "Match all tuples" to "Match all pages" mode. Since a page can contain multiple tuples, we have to recheck the condition in the upper node (Bitmap Heap scan).