For practical purposes, you usually don't index every column. The index is a value-add for performance gains, which as far as I've seen requires custom implementation in map-reduce databases. When it is implemented, you would have the same storage problem. As an example you can look at Common Crawl, which has a public index of web page data. They provide a hadoop database of page source, and a smaller data set of page text. The page text database serves a similar function to an index. Using the text dataset instead of full HTML would be like an "Index Scan" in database optimizer terms.

I don't think he said you can't do complex joins; he said people tend to denormalize the data before putting it into NoSQL databases.