Dremel keeps a prefetch cache that takes 95% of the hits, and it gives an approximate answer when one is requested.
A person's next query is not very different from the last one. It filters on the same data, with a little data added and a little removed. A least recently used cache holds that data, so the first query takes a lot of time and the subsequent queries are quick.
An approximate answer is an option for count and top K queries:
- The top 100 of restaurants ranked 0 to 110. The top 10 and the top 20 are exact, and the tail is sampled from ranks 75 to 110.
- The top 10 queries of yesterday. The first 8 are accurate, and the others are sampled from ranks 8 to 12.
The response is faster because it does not scan all table shards. A query that hits 100 shards has a high chance of a shard failing, and its latency spikes.
The election commission asks every person, which takes time. The news channels sample.