How does a query into a huge database return with negligible latency?
Well, I'm not sure if it is MapReduce that solves the problem, but it surely wouldn't be MapReduce alone to solve all these questions you raised. But here are important things to take into account, and that make it feasible to have such low latency on queries from all these TBs of data in different machines:


distributed computing: by being distributed does not mean that the indexes are simply distributed in different machines, they are actually replicated along different clusters, which allows for lots of users performing different queries with low retrieval time (yes, huge companies can afford for that much of machines);
caching: caches tremendously reduce execution time, be it for the crawling step, for the retrieval of pages, or for the ranking and exihibition of results;
lots of tweaking: all the above and very efficient algorithms/solutions can only be effective if the implementation is also efficient. There are tons of (hard coded) optimizations, such as locality of reference, compression, caching; all of them usually appliable to different parts of the processing.


Considering that, lets try to address your questions:


  but I imagine it infeasible for the results of every single possible query to be indexed


Yes, it would be, and actually is infeasible to have results for every single possible query. There is an infinite number of terms in the world (even if you assume that only terms properly spelled will be entered), and there is an exponential number of queries from these n -&gt; inf terms (2^n). So what is done? Caching. But if there are so many queries/results, which ones to cache? Caching policies. The most frequent/popular/relevant-for-the-user queries are the ones cached.


  wouldn't the hardware latency in Google's hardware be huge? Even if the data in Google were all stored in TB/s SSDs


Nowdays, with such highly developed processors, people tend to think that every possible task that must finish within a second (or less), and that deals with so much data, must be processed by extremely powerful processors with multiple cores and lots of memory. However, the one thing ruling market is money, and the investors are not interested in wasting it. So what is done?

The preference is actually for having lots of machines, each using simple/accessible (in terms of cost) processors, which lowers the price of building up the multitude of clusters there are. And yes, it does work. The main bottleneck always boils down to disk, if you consider simple measurements of performance. But once there are so many machines, one can afford to load things up to main memory, instead of working on hard disks.

Memory cards are expensive for us, mere human beings, but they are very cheap for enterprises that buy lots of such cards at once. Since it's not costly, having much memory as needed to load indexes and keep caches at hand is not a problem. And since there are so many machines, there is no need for super fast processors, as you can direct queries to different places, and have clusters of machines responsible for attending specific geographical regions, which allows for more specialized data caching, and even better response times.


  Does MapReduce help solve this problem?


Although I don't think that using or not MapReduce is restricted information inside Google, I'm not conversant about this point. However, Google's implementation of MapReduce (which is surely not Hadoop) must have lots of optimizations, many involving the aspects discussed above. So, the architecture of MapReduce probably helps guiding how the computations are physically distributed, but there are many other points to be considered to justify such speed in querying time.


  Okay, so I understand that popular searches can be cached in memory. But what about unpopular searches?


The graph below presents a curve of how the kinds of queries occur. You can see that there are three main kinds of searches, each of them holding approximately 1/3 of the volume of queries (area below curve). The plot shows power law, and reinforces the fact that smaller queries are the most popular. The second third of queries are still feasible to process, since they hold few words. But the set of so-called obscure queries, which usually consist of non-experienced users' queries, are not a negligible part of the queries.



And there lies space for novel solutions. Since it's not just one or two queries (but one third of them), they must have relevant results. If you type in something much too obscure in a Google search, it shan't take longer to return a list of results, but will most probably show you something it inferred you'd like to say. Or it may simply state that there was no document with such terms -- or even cut down your search to 32 words (which just happened to me in a random test here).

There are dozens of appliable heuristics, which may be either to ignore some words, or to try to break the query into smaller ones, and gather the most popular results. And all these solutions can be tailored and tweaked to respect feasible waiting times of, say, less then a second? :D