Weird Results Matching (on big indexes 3M+) , why?

[thePanz]

For an "address searcher" application we indexed a bunch of indexes in Switzerland.
We would like to offer a search feature and used Meilisearch for indexing them, but the results are not as we expect them, in particular for the received scores.

How can those two results be explained, where the second one (score=0.49) should be the best candidate?

• Query "Abeggweg 1 8001 Zurich"
• First result: "Abendweg 1 8038 Zürich", score=0.87
• Second result: "Abeggweg 1 8057 Zürich", score=0.49

Notes:

• the first word of the 2nd result exactly matches the searched one
• both zip codes are not correct, thus the typo should match them (but why does only in the first result? 😕 )
• the results are ""almost"" correct when we use a small index (with both of the entries indexed), but when the index reaches 3M records, the ""wrong"" result is placed first. We can not understand the reason behind that behavior.

Given the query:

{
	"q": "Abeggweg 1 8001 Zurich",
	"offset": 0,
	"limit": 2,
	"attributesToRetrieve": ["id"],
	"attributesToSearchOn": ["fullAddress", "fullAddressAbbreviated"],
	"attributesToHighlight": ["fullAddress", "fullAddressAbbreviated"],
	"showMatchesPosition": false,
	"showRankingScore": true,
	"showRankingScoreDetails": true							 
}

and the results:

{
	"hits": [
		{
			"id": "018e5c23-5ca1-78d1-aec3-9847983e444c",
			"_formatted": {
				"fullAddress": "<em>Abendweg</em> <em>1</em> <em>8038</em> <em>Zürich</em>",
				"fullAddressAbbreviated": "<em>Abendweg</em> <em>1</em> <em>8038</em> <em>Zürich</em>",
				"id": "018e5c23-5ca1-78d1-aec3-9847983e444c"
			},
			"_rankingScore": 0.8725,
			"_rankingScoreDetails": {
				"words": {
					"order": 0,
					"matchingWords": 4,
					"maxMatchingWords": 4,
					"score": 1.0
				},
				"typo": {
					"order": 1,
					"typoCount": 4,
					"maxTypoCount": 7,
					"score": 0.5
				},
				"proximity": {
					"order": 2,
					"score": 1.0
				},
				"exactness": {
					"order": 3,
					"matchType": "noExactMatch",
					"matchingWords": 2,
					"maxMatchingWords": 4,
					"score": 0.2
				},
				"attribute": {
					"order": 4,
					"attributeRankingOrderScore": 1.0,
					"queryWordDistanceScore": 1.0,
					"score": 1.0
				}
			}
		},
		{
			"id": "018e5c1e-b36d-7bf2-923b-6212be7a756a",
			"_formatted": {
				"fullAddress": "<em>Abeggweg</em> <em>1</em> 8057 <em>Zürich</em>",
				"fullAddressAbbreviated": "<em>Abeggweg</em> <em>1</em> 8057 <em>Zürich</em>",
				"id": "018e5c1e-b36d-7bf2-923b-6212be7a756a"
			},
			"_rankingScore": 0.4947916666666667,
			"_rankingScoreDetails": {
				"words": {
					"order": 0,
					"matchingWords": 2,
					"maxMatchingWords": 4,
					"score": 0.5
				},
				"typo": {
					"order": 1,
					"typoCount": 0,
					"maxTypoCount": 3,
					"score": 1.0
				},
				"proximity": {
					"order": 2,
					"score": 1.0
				},
				"exactness": {
					"order": 3,
					"matchType": "matchesStart",
					"score": 0.6666666666666666
				},
				"attribute": {
					"order": 4,
					"attributeRankingOrderScore": 1.0,
					"queryWordDistanceScore": 1.0,
					"score": 1.0
				}
			}
		}
	],
	"query": "Abeggweg 1 8001 Zurich",
	"processingTimeMs": 10,
	"limit": 2,
	"offset": 0,
	"estimatedTotalHits": 340
}

The index is configured with typos as:

{
	"searchableAttributes": [
		"fullAddress",
		"fullAddressAbbreviated"
	],
	"rankingRules": [
		"words",
		"typo",
		"proximity",
		"exactness",
		"attribute",
		"sort"
	],
	"proximityPrecision": "byWord",
	"typoTolerance": {
		"enabled": true,
		"minWordSizeForTypos": {
			"oneTypo": 3,
			"twoTypos": 4
		}
	},

maybe related: #4093

[dureuill]

Hello @thePanz 👋

Thank you for the super-detailed report ❤️

I think I can explain the behavior you're observing and why it triggers only on big indexes.
There are two distinct issues at play here.

1. As you noticed, 8001 -> 8038 is detected as a typo, while 8001 -> 8057 isn't. This is a consequence of limits that Meilisearch has in place in the number of typos that are considered per word. The search runs afoul of this limit more easily as the index becomes bigger, because there are more candidates to try from 8001 to 8057 (candidates are tried lexicographically, so the last eligible one for two typos should be around 8052). Note that the limit is in effect due to the very high cost of considering too many typos in a single search request.
2. As a consequence of (1), 8057 is not considered as a "matching" word for 8001. The default matching word strategy of Meilisearch is last, where Meilisearch will produce the following buckets of documents:
   1. Documents that contain "Zurich", "8001", "1" and "Abeggweg", or one of their typos, with matching words 4/4. Your first hit is in this bucket.
   2. Documents that contain "8001", "1" and "Abeggweg", or one of their typos, with matching words 3/4
   3. Documents that contain "1" and "Abeggweg", or one of their typos, with matching words 2/4. This is the bucket of your second hit.
   4. Lastly, documents that only contain "Abeggweg" or one of its typos, with matching words 1/4.

So, as far as typo rules and matching word strategies are concerned, that behavior is expected, if a bit unintuitive.
I understand the behavior might be undesirable, but I'm not sure there is an easy way out here, neither using the current version of the engine or after possible fixes...

• A matching strategy that would try to match all combinations of words would degrade performance too much
• Same for removing the typo restriction, it would also increase memory cost.

I'll bring that to the team, maybe a relevancy expert could help you structure your index or massage your query to get better results

[thePanz]

Thank you @dureuill for answering.
I get the technical problem (being implementing search engines for a while now) and I see the threshold to limit the resource usage and keep the whole search experience fast.

Unfortunately I see this issue as an incorrect behavior of the scoring's computation, rather than a a bit unintuitive: from the documentation here: https://www.meilisearch.com/docs/learn/core_concepts/relevancy?ref=blog.meilisearch.com#ranking-score I read:

A document's ranking score does not change based on the scores of other documents in the same index.

But it does not mention that a document score might change by the size of the index and the cardinality of the field's posting file (as it is in this case I guess). This might be a quite relevant information to share, explaining the limitations of the matching used behind typo.

From my point of view this behavior/limitation is bringing 'incorrect' results with a higher score than the 'correct' ones. And the root cause lead by the lexicographical distance between from the searched term and the tolerance on typos.

Looking to get more details and hints from your relevancy expert 👍

As far as I get from the querying: there is no way to specify the typo-expansion threshold on a "per-field" basis at query time (I checked as we tried to move the ZIP data into its own field).

In the meantime this is quite a show stopper for us, as the search is providing incorrect results and will investigate other options.

[dureuill]

rather than a a bit unintuitive

Yes that was a bit of an understatement. This can rather be described as a relevancy bug, or a relevancy limitation of the engine. Rankings (and hence, scores) are not supposed to be dependent on the dataset.

In the meantime this is quite a show stopper for us

I'm really sorry to hear that 😞 As discussed, I brought the issue with the team, but even the other people most familiar with relevancy were not able to find a workaround for your use case.

I think that the crux of the issue is that we should maybe special case numbers, where it makes sense to consider more typo candidates than regular numbers. However, even if we do that, looking at many typo candidates will definitely have the engine explode, whether the typos are numbers of not.

As a quick workaround, you could try patching the two typos limit from 50 to 100, this might give you a more "natural" behavior. However that won't fix the core issue.