Exactness ranking rule takes an excessive amount of time

[loiclec]

For context, the exactness ranking rule sorts documents as follows:

1. a document's attribute is exactly equal to the search query
2. a document's attribute starts exactly by the search query
3. a document contains many of the search query's exact words (i.e. as opposed to derived terms such as ngrams or split words)

It is also, by default, the last ranking rule. It is therefore very performance sensitive since it can be called many times for the same search query.

For example, I noticed that with the songs dataset, a search query consisting of ten common words would take 5 seconds to be executed. This is because of the implementation of the 3rd sorting rule, which tries to find the documents containing any combinations of 10/9/8/7/etc. of the ten words in the query. That is a total of 1022 combinations

Each of those combination is computed by doing an intersection of 5 bitmaps on average. Additionally, this very expensive operation is repeated on each call to the ranking rule, which happens a lot since exactness is the last rule, by default.

It's possible to greatly speed up the current implementation. Nevertheless, I think we might need to rethink the design of the third sorting rule.

1. One potential solution is to simply remove the 3rd sorting rule from the implementation of exactness. This would somewhat impact the relevancy of the search results because ngrams and split words will not be disadvantaged anymore.

2. Another potential solution is to sort documents by the number of ngrams and split words that they contain. This will be a lot easier to implement and more efficient after we redesign the query tree.

---

TODO

• Implement changes in Milli
• Release a Milli version containing these changes
• Bump this new Milli version in Meilisearch and merge it into main

[curquiza]

Close by #3269, which integrates milli v0.38.0, which integrates the changes for this issue.