Q:

In Lucene, what is the accepted way to return an approximate result count without impacting performance?

I want my users' search results to include some idea of how many matches there were for a given search query.
However, after a bit of research and observation of my users' search logs, I've noticed a direct correlation between logged query speed and the number of total results and have determined that this is because I am accessing the totalHits property, which apparently has to iterate over the entire result set in order to return a value.
I would be happy to simply return an approximate value, maybe even just an order of magnitude indicating a rough idea of how many results are available, but I can't see if there's any good way to calculate this without noticeably affecting performance. I don't really want to just dump a seemingly-bottomless result set in front of the user without providing them any rough idea of how many results their search matched.
Any suggestions?

A:

With boolean queries you can try to approximate:

|A or B| / |D| = ((|A| / |D|) + (|B| / |D|)) / 2
|A and B| / |D| = (|A| / |D|) * (|B| / |D|) 

Where A and B are two terms, and |D| is the total number of documents. This is basically making an assumption of independence.
You can use the rewrite method to rewrite any query to a boolean query. 
There isn't really a better way of doing this, but I've found that this assumption isn't too bad in practice. If you have a very small number of docs it might give bad answers though.
EDIT: as jpountz points out, my calculation for OR is wrong. Should be:
P(A U B) = 1 - P(~(AUB)) 
         = 1 - P((~A) & (~B))
         = 1 - P(~A)P(~B)
         = 1 - (1 - P(A))(1 - P(B))
         = 1 - (1 - P(A) - P(B) + P(A)P(B))
         = P(A) + P(B) - P(A)P(B)

