It is pretty straightforward. You could denormalize as much as you want upfront, or you could parallelize. Facebook does some of both.
Indexing is an exercise in denormalization. At the time I post X, the data is also stored in an index keyed by eg every phrase I wrote and maybe even stemmed by synonyms. This makes search fast. It is a memory-time tradeoff which basically precomputes the answer for every query, limited to my feed.
As for searching 500 indexes in parallel - this is hardly unreasonable. The alternative -- updating N indexes for every post where N is the number of friends -- is more unreasonable, since it does the maximum amount of work, when the vast majority of it is wasted. No friend is going to search for every single word. On the contrary, some friends will eventually search for a large number of words in YOUR index.
Indexing is an exercise in denormalization. At the time I post X, the data is also stored in an index keyed by eg every phrase I wrote and maybe even stemmed by synonyms. This makes search fast. It is a memory-time tradeoff which basically precomputes the answer for every query, limited to my feed.
As for searching 500 indexes in parallel - this is hardly unreasonable. The alternative -- updating N indexes for every post where N is the number of friends -- is more unreasonable, since it does the maximum amount of work, when the vast majority of it is wasted. No friend is going to search for every single word. On the contrary, some friends will eventually search for a large number of words in YOUR index.
Facebook can easily do parallel queries and combine them. Even with a simple MySQL partitioned / sharded setup a site can do it. We do it at Qbix. Let alone Facebook which has improved on mapreduce in their architecture to be more dynamic (http://thenextweb.com/facebook/2012/11/08/facebook-engineeri...) and then there's this: http://www.semantikoz.com/blog/hadoop-2-0-beyond-mapreduce-w...
So yeah. That's how they probably do it.