Facebook uses Cassandra, and, with properly designed schema, those queries are actually cheap, and, better yet, distributed across a cluster of machines. You can read about Cassandra here: http://cassandra.apache.org/