search

meilisearch / milli

Search engine library for Meilisearch ⚡️
MIT License
464 stars 82 forks source link

Optimise the `ExactWords` sub-criterion within `Exactness` #709

Closed loiclec closed 1 year ago

loiclec commented 1 year ago

Pull Request

Related issue

Fixes (partially) https://github.com/meilisearch/meilisearch/issues/3116

What does this PR do?

  1. Reduces the algorithmic complexity of finding the documents containing N exact words from something that is exponential to something that is polynomial.
  2. Cache intermediary results between different calls to the exactness criterion.

Performance Results

On the smol_songs.csv dataset, a request containing 10 common words now takes about 60ms instead of 5 seconds to execute. For example, this is the case with this (admittedly nonsensical) request: Rock You Hip Hop Folk World Country Electronic Love The.

loiclec commented 1 year ago

Thank you! bors merge

bors[bot] commented 1 year ago

Build succeeded!

And happy new year! 🎉