apache / apache/lucene

MinHashFilter generates invalid terms [LUCENE-8779]

Open
#9,823 0 comments 0 reactions 0 assignees View on GitHub
legacy-jira-priority:Minor type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

This problem was reported at https://github.com/elastic/elasticsearch/issues/41556: MinHashFilter computes a hash and then folds its bits into the chars of the term. However this might generate invalid terms that eg. end with a character that is a high surrogate.

This doesn't trigger exceptions at index time because we are lenient with unmatched surrogates when converting to a binary term.

```Java
} else {
// surrogate pair
// confirm valid high surrogate
if (code < 0xDC00 && (i < end-1)) {
int utf32 = (int) s.charAt(i+1);
// confirm valid low surrogate and write pair
if (utf32 >= 0xDC00 && utf32 <= 0xDFFF) {
utf32 = (code << 10) + utf32 + SURROGATE_OFFSET;
i++;
out[upto++] = (byte)(0xF0 | (utf32 >> 18));
out[upto++] = (byte)(0x80 | ((utf32 >> 12) & 0x3F));
out[upto++] = (byte)(0x80 | ((utf32 >> 6) & 0x3F));
out[upto++] = (byte)(0x80 | (utf32 & 0x3F));
continue;
}
}
// replace unpaired surrogate or out-of-order low surrogate
// with substitution character
out[upto++] = (byte) 0xEF;
out[upto++] = (byte) 0xBF;
out[upto++] = (byte) 0xBD;
}
```

---
Migrated from [LUCENE-8779](https://issues.apache.org/jira/browse/LUCENE-8779) by Adrien Grand (@jpountz)

Contributor guide

Open the contributing guide

Research direction

Start by locating MinHashFilter and the code that folds hash bits into term characters; reproduce or inspect the unmatched-high-surrogate case described in the issue. Determine how the filter should avoid invalid terms, then verify that generated terms are valid and that indexing no longer relies on lenient unmatched-surrogate handling.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.