1) grab index for each word in the query 2) grab first x results from each index 3) cross these to filter down to actual matches
I believe step 3 is as expensive as rendering the results AND nobody would like to wait for rendering 600k results before getting some of it. This they stick with some simple estimate, like max(size of found indices), or average or whatnot.
I did a search for "hackerspace" (no quotes) and it claims "About 588,000 results." Paging through the results, I eventually got "In order to show you the most relevant results, we have omitted some entries very similar to the 390 already displayed." Even with omitted entries included, there only seems to be 832 results.
Try http://www.google.com/custom?q=hackerspace&num=100&safe=off&... it will show you that they actually found those thousands of results, but only if you search with an older algorithm.
> Sorry, Google does not serve more than 1000 results for any query. (You asked for results starting from 9000.)