A query for a few rows in 75000 should take less than a second. An index would really help you out here. I've done queries on millions of records without noticeable performance.
It also depends how many records you need to match in the result. A query for 10 rows in a 100 million records (with a proper index) is going to be much faster than a query for 10,000 records out of a million. The less rows the query has to return, the less disk accesses it needs to make. In addition to the things already mentioned, this is something that works in Google's favor. They only need to return one page of results at a time. If you do a query and page through the results, you'll notice that the total number of rows gets more refined over time. The initial "page 1 of 20" is an estimate.