I also know that the size of the cluster is a fraction of 40 instances (especially if you don't include the subcluster of web crawlers).
By comparison, it doesn't seem super impressive. Tineye's metadata is stored in a sharded PostgreSQL database, the image index itself is a separate proprietary engine (also sharded).
Then again, we probably dealt with a smaller set of query types so we could optimize those scenarios much more heavily. Nonetheless, from my experience it feels like they could do better with any of the options they've tried. It's important to be aware where the bottleneck is. In our case, the IO of the EC2 storage disks was a bottleneck (which we mitigated by sharding). Once we moved the cluster off of AWS and shoved some nice SSD drives into the machines, the performance increase was dramatic (half the shards for twice the speed, pretty much).
As to the sibling comment, that's another good point. You say it's because it knows about the queries ahead of time, but you don't get excellent real-world performance without what an academic might consider cheating. Special-case your data structures to expected queries, where those queries are either empirically discovered and adjusted for manually, or learned automatically over time. A closed-minded approach that simply shuts down creative thinking by parroting out "linear time, no can do better, sorry" is poor form.
The topic is about how search was faster than aggregation, and I'm saying that searching is faster than aggregation generally. You can parallelize all you want, it's still going to be faster to search than to aggregate.
http://perfcap.blogspot.com/2011/03/understanding-and-using-...
Somewhere there's an HN discussion for it too.
1. "Our 40-instance (m2.2xlarge) cluster can scan, filter, and aggregate 1 billion rows in 950 milliseconds."