[search] issues with the new HTML search algorithm

[picnixz]

I don't really have a good title for this issue, but the CPython issue speaks for itself. It appears we are still misranking titles in some cases (the 3.11 doc is generated by 7.2.6 but the 3.12 is generated by 7.3.7).

cc @wlach @jayaddison

From python/cpython#119423 (comment)

(I initially posted this in the pythondotorg repo - where I was directed here. Copying the description from there verbatim)

Describe the bug Searching for library modules on 3.12 returns first a list of "What's new in " pages instead of the searched for module.

To Reproduce Steps to reproduce the behavior:

1. Go to [docs.python.org/3.12/index.html](https://docs.python.org/3.12/index.html)

2. Click on search box in top right corner, enter e.g. "asyncio" and hit enter

3. [Scroll through results](https://docs.python.org/3.12/search.html?q=asyncio)

4. See that the first result is "History and License" followed by 10 (!) "What’s New In Python <version>" results. The 11th result is the actual asyncio module.

Expected behavior I would expect the asyncio module page to be the first result, or at the very least to appear very close to the top. This has been the case in previous versions of the website search.

Screenshots (the list goes on a few more entries below the screenshot)

Compare with search from 3.11:

Desktop (please complete the following information):

* OS: MacOS

* Browser Chrome

* Version 123

Additional context This happens for other topics too, not only modules.

[wlach]

Ironically I think fixing the search algorithm so it worked as originally intended made this worse. In previous versions, there were various bugs that made title matches rank lower than they should have.

In this case, asyncio is a title and it's a full match in the case of the release notes. In the case of the module, it's asyncio — Asynchronous I/O so is only a partial one (I'm not sure what's going on with the module match-- would need to investigate)

That's said, there's a few things we could investigate that might improve things:

• Figure out if we can boost module-level results
• Rank title matches lower if they're coming from a subheader
• Give extra points if the match is at the beginning even if it's only a partial match (@picnixz suggested something similar in Python 3.12 docs website search results prioritizes "what's new" instead of actual topic python/cpython#119423 (comment))

[Saba-Sabato]

If I may add my two cents here, I think a key part is actually the webpage name: https://docs.python.org/3.12/library/asyncio.html, https://docs.python.org/3.12/library/itertools.html
If you boosted the webpage's actual name, it would at the very least solve the issue for all modules. (which IMO is one of the most common use cases for search, but I don't really have data here)

[picnixz]

There are other possibilities, namely rank the match higher:

• if it's part of the document being documented (in general, you document a module in a file that has the same... name)
• if it's a standalone name + lowercased name (usually important in this case)

EDIT: We had the same idea with the name of the file !

[wlach]

Definitely lots of things we could experiment with! I think now that we have a foundation with better testing (esp. after #12102 merges) it will be easier to iterate on things and make sure that we maintain desired behaviour.

[picnixz]

I'll be out for the next days due to Eurocrypt, but I'll be back next week and could perhaps make that happen. In the meantime, @hugovk I suggest you generate the docs with a patched version of searchtools.js so that Python is not broken for too much time (or maybe people can live with that, though it's a bit annoying...).

[hugovk]

Thanks, I think we can wait, let's see. Enjoy Eurocrypt!

[wlach]

Spent a bit of time looking at this today. Some thoughts:

• I'm not an expert in information retrieval, but my sense from taking a couple of undergraduate courses in the distant past is that it's very hard to come up with heuristics that don't occasionally give bad results like what we're seeing here. It's probably better to just rely on things like tf-idf with a few lightweight things on top to weight the results a bit.
• In this vein, the existing js code seems to heavily boost results where there is a full title match (100 points, vs. like 5 for a term search). This might make sense when it's the title of the whole document but when it's a subtitle this probably isn't nearly as much of a hint that the information is relevant. I suspect this feature actually never worked exactly as originally intended, but various bugs in the JavaScript code obscured that.

I attempted a quick fix that adjusted some things here:

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

Line 327 in 48cbb43

const queryLower = query.toLowerCase().trim();

It seems to give somewhat better results (see PR) but to be honest I'm not super happy with it, it feels very much like a set of hacks (on top of the existing hacks) that might just lead to other problems.

Longer term, I think we might want to focus on improving the scoring algorithm for generic term search. I may be misunderstanding what's going on (wouldn't be the first time 😄), but based on my initial spelunking of the https://github.com/sphinx-doc/sphinx/blob/48cbb43e28efe82b198137042811e0ade3599ae7/sphinx/search/__init__.py it doesn't look like we're using tf-idf -- it seems like we just check whether the term is in the document or not. I suspect we could get much better results by using that by default, then implementing title search on top of that (to further boost scores), instead of making it its own thing.

[picnixz]

So, I'm back and here's what I suggest:

1. merge [tests] JavaScript: extract searchindex.js-format test fixtures. #12102 (the comments that I made are only cosmetic so we can merge it right away and revist the PR later
2. should we sit down to check how to improve the whole search algorithm? IMO we should probably revisit more or less everything from scratch (the premises might be wrong)

I had some lectures about learning theory, tensors and similarities but those were mostly theoretical and not really with implementations. So on that one I cannot really help although I can give ideas. Nonetheless, I can help with the maths behind if needed (and graph-based searches as well).

PS: If anyone has experience in search-based engine (e.g., someone that is well-versed in Google techniques :D), they are welcome to help us!

[wlach]

So, I'm back and here's what I suggest:

1. merge [[tests] JavaScript: extract searchindex.js-format test fixtures. #12102](https://github.com/sphinx-doc/sphinx/pull/12102) (the comments that I made are only cosmetic so we can merge it right away and revist the PR later

Do you have rights to edit the pull request? I believe maintainers usually do with the committers' consent. But yes, that makes sense to me.

2. should we sit down to check how to improve the whole search algorithm? IMO we should probably revisit more or less everything from scratch (the premises might be wrong)

Yes, I kind of think so though it feels like a large project -- at least 40 to 80 hours, maybe more (especially if you consider product research and testing). One thing to note is that any site hosted by readthedocs (which many sphinx projects use, though not cpython) uses a different server-side implementation of search which doesn't appear to suffer from these problems.

Part of me wonders if we should implement some variation of #12393 as an interim solution to at least fix these pathologically bad cases where a subtitle gets ranked higher than a title.

I had some lectures about learning theory, tensors and similarities but those were mostly theoretical and not really with implementations. So on that one I cannot really help although I can give ideas. Nonetheless, I can help with the maths behind if needed (and graph-based searches as well).

PS: If anyone has experience in search-based engine (e.g., someone that is well-versed in Google techniques :D), they are welcome to help us!

Well, there's definitely prior art out there to look at-- e.g. I think mkdocs and mkdocs-material have pretty good client side search. I believe they use a combination of lunr.js (using https://github.com/yeraydiazdiaz/lunr.py to generate the index) with some other magic.

[picnixz]

Do you have rights to edit the pull request? I believe maintainers usually do with the committers' consent. But yes, that makes sense to me.

I think Jay allowed it.

Yes, I kind of think so though it feels like a large project -- at least 40 to 80 hours, maybe more (especially if you consider product research and testing)

I'm defending my thesis in one month, so I cannot really afford to spend 40-80h on that task but at least, it's good that we agree that we need to do something. If you however know of anything that is opensource and that can be used as a plug-in replacement or from where we could inspire ourselves, then it'd be definitely a starting point. The lunar.py framework seems suitable to our needs since we do have something that could serve as primary/secondary keys.

For instance, with the 'asyncio' use case, we would have multiple matches but only one of them would be a "module"-like match and in this case, it is pretty easy to select which would be the expected one.

Now, before doing anything, perhaps we could decide the priority of the fields, like, when you search something, do you first want a module, a class, a property, or what? and in which order?