As you deal with more and more rows, it becomes imperative that all of your where clauses hit indexes/indices, but even beyond that, with large enough row sizes, it's not enough to provide fast responses.
I suspect they deal with this in the form of some sort of caching outside of MySQL, but I haven't read into it.
I'd be curious about how you respond to such challenges at the billions or trillions of rows orders of magnitude. Millions can be difficult enough, but beyond that you may have queries that effectively never return if you do not plan.
Related reading:
[1]: https://dba.stackexchange.com/questions/20335/can-mysql-reas...