[HTML search] optimization: don't loop over all document terms and title terms during partial-matching.

[jayaddison]

Is your feature request related to a problem? Please describe.
There seems to be a potentially-large inefficiency in the Sphinx JavaScript search code: for any query word greater than length two (likely to be >90% of them, I'd guess!), we iterate through all document terms and all title terms in the client's search index to check for partial matches.

However, if an exact-match was already found on the query word, then we won't add any of those candidates, even when they do match. That means that we spend JavaScript compute resources iterating through items that are unused. Since Sphinx 7.3.0, this is no longer true thanks to #11958 -- if an exact-match on a stemmed term is found, we skip checks for partial matches for that query term.

The relevant code is found here:

sphinx/sphinx/themes/basic/static/searchtools.js

Lines 469 to 476 in cf7d275

	Object.keys(terms).forEach((term) => {
	if (term.match(escapedWord) && !terms[word])
	arr.push({ files: terms[term], score: Scorer.partialTerm });
	});
	Object.keys(titleTerms).forEach((term) => {
	if (term.match(escapedWord) && !titleTerms[word])
	arr.push({ files: titleTerms[word], score: Scorer.partialTitle });
	});

I don't have any stats on the performance impact of this, but it feels like it may be significant, especially for large documentation projects. Initial results appear to indicate a 9ms vs 48ms difference on a local test machine.

Describe the solution you'd like

• If we've already found exact-matches for a document term, then do not iterate over all document terms to check for partial matches.
• If we've already found exact-matches for a document title term, then do not iterate over all document title terms to check for partial matches.
• Find a non-brute-force algorithm for partial substring matching on terms and titles.

Describe alternatives you've considered
A clear and concise description of any alternative solutions or features you've considered.

Additional context

• Extracted from HTML Search: Partial matches can overwrite main matches in certain rare cases #11957.

[jayaddison]

Resolved by #11958.

[jayaddison]

Re-opening because I'm puzzling over this potential performance problem. Some thoughts:

• Perhaps it's not a relevant/useful problem to work on, because most searches involve a fresh page-load and often also include additional HTTP GET requests to load search snippets (search summaries) -- and the time overhead involved in those may make these loops miniscule.
• Perhaps enough user query terms do find at least one exact-match term, meaning that this problem is not encountered frequently.
• The Python docs, as an example large-ish docbase, do contain over 40k terms, from a quick check I ran, and that feels like a lot to me. Yes, most modern compute devices (mobile or desktop) are 'fast', but even so, removing that kind of iteration might improve perceived performance (and energy efficiency).
• ngrams -- and in particular in this case, trigrams or larger -- could support the existing functionality. My personal opinion is that they might be finnicky and annoying to work with in terms of code complexity, though. They could unlock search-as-you-type as a side-effect -- but might also make for larger sized search indexes (again as reference: Python docs' search index is currently ~3.7MB uncompressed. ngrams would introduce an increase on that I expect, even if we are able to drop the terms/title-terms indexes in the process).

Edit: and a second item questioning how often the problem occurs in practice.

[wlach]

Out of curiosity, I ran a search through Chrome's devtools profiler and here were the results:

The javascript portion of the search is around 16ms on my Dell i7. No doubt it would be a little slower on older machines, but I doubt by much.

A more significant optimization would likely be to fetch results for the search previews in parallel. That seems to be the main bottleneck to showing a full result.