How does Elasticsearch perform fuzzy "relevancy score" queries very fast?

Question

As I understand it, in order for Elasticsearch to execute "fuzzy" queries that involve a "relevancy score", it must iterate through and calculate relevancy for all possible matches (possibly including thousands or millions of rows), even if the "limit" on the query is only "10".

How is Elasticsearch able to accomplish this while at the same time providing reasonable response times?

Answer 1

In Lucene 4, fuzzy searches prune the search space rather than brute-forcing it as before:

Lucene's FuzzyQuery is 100 times faster in 4.0

Hopefully, ElasticSearch will be updated to Lucene 4 soon.

Answer 2

One possibility is that the search process can terminate after getting enough results even if they don't highest scores. Therefore, not all the results need to be computed.