5 ms·
One thing that isn't really covered in this article is relevance calculations. A surprising (to me) thing about PostgreSQL FTS is that it doesn't do TF/IDF or
by simonw 4y ago
One thing that isn't really covered in this article is relevance calculations.
A surprising (to me) thing about PostgreSQL FTS is that it doesn't do TF/IDF or BM25 relevance calculations.
These calculations take statistics about the entire corpus into account - they do things like ranking a document higher if it contains terms from the search which are statistically rare in the overall corpus.
PostgreSQL FTS uses how often the search terms appear in the document as part of the ranking score, but doesn't look at how common/rare individual terms are. https://www.postgresql.org/docs/current/textsearch-controls.html#TEXTSEARCH-RANKING https://www.postgresql.org/docs/current/textsearch-controls....
OpenSearch/Elasticsearch uses BM25: https://opensearch.org/docs/latest/opensearch/rest-api/explain/ https://opensearch.org/docs/latest/opensearch/rest-api/expla...
SQLite stores these kinds of statistics and can support BM25 or TF/IDF or custom ranking functions. I wrote more about that here: https://simonwillison.net/2019/Jan/7/exploring-search-relevance-algorithms-sqlite/ https://simonwillison.net/2019/Jan/7/exploring-search-releva...
Meilisearch does something a bit different (on reading this I don't think it considers full corpus statistics, but I may be misinterpreting that): https://docs.meilisearch.com/learn/core_concepts/relevancy.html#ranking-rules https://docs.meilisearch.com/learn/core_concepts/relevancy.h...
It looks like Typesense only considers the documents, not the overall corpus: https://typesense.org/docs/guide/ranking-and-relevance.html https://typesense.org/docs/guide/ranking-and-relevance.html
- hardwaresofton 4y agoThis is within reach due to the flexibility of features like setweight[0], but I don't know enough about TF/IDF or BM25. Seems like an excellent weekend project. [0]: https://www.postgresql.org/docs/current/textsearch-features.html https://www.postgresql.org/docs/current/textsearch-features....
- jrochkind1 4y agoI don't see how the setweight function could be used to give you something like a traditional TF/IDF algorithm, but perhaps I'm missing it. I would be interested in reading more about that if I am.
- hardwaresofton 4y agoWhat I'm thinking is a little far out but it came up recently on a project where I'm using Postgres FTS (it's slow but I guess I might as well link it for now[0] -- please do not HN hug it). Basically, I read on the internet (and was surprised by) the fact that setweight can be used and combined with individual terms on tsvectors, and then those tsvectors can be combined and they keep their weightings. Some code from that project to illustrate: UPDATE podcasts SET fts_doc = setweight(to_tsvector(COALESCE(title, ' ')), 'A') || setweight(to_tsvector(COALESCE(homepage_url, ' ')), 'A') || setweight(to_tsvector(COALESCE(podcast_idx_itunes_author, ' ')), 'A') || setweight(to_tsvector(COALESCE(podcast_idx_itunes_ownername, ' ')), 'A') || setweight(to_tsvector(COALESCE(podcast_idx_host, ' ')), 'A') || setweight(to_tsvector(array_to_string(categories, ' ')), 'B') || setweight(to_tsvector(COALESCE(description_html, ' ')), 'D') Basically I'm making tsvectors out of chunks of the document, weighting them differently then recombining with other vectors without losing the weightings -- I'm thinking this could be applied to words identified by the corpus-level algos. So my simplistic thinking here is that if you've done the corpus level processing, you could build an intermediate data structure and re-evaluate each search document with the appropriate weighting. It would likely be quite the lengthy stored procedure, but seems like setweight could support the usecase? Maybe I'm being a bit optimistic. [0]: https://podcastsaver.com https://podcastsaver.com
- pbronez 4y agoIf you could figure that out, it would be an awesome plugin. PS podcastsaver looks neat! some quick feedback: 1) your "switch back to light mode" icon looks a LOT like a gear for a settings menu. I turned on dark mode, did a search, saw the "back to light mode" icon and thought "huh, the dark mode toggle is settings now? Weird choice, let's see what's there..." 2) the show notes seem truncated. It would be helpful for me to be able to search the show notes for a defined set of podcasts. Sometimes I remember that a podcast mentioned a product or service that I wanted to check out, but I can't remember the name of the product or the overall episode, and it's painful to find the right one by scrolling back through everything in my pod catcher. 3) are you tracking Podcasts 2.0? Some interesting additional stuff to index there. https://origin.fm/blog/podcasting-2point0/ https://origin.fm/blog/podcasting-2point0/
- billythemaniam 4y agoYep. PG FTS works fine for a recall-based problem. If your data has a high cardinality then recall search works great. But with low cardinality data, you start needing BM25, ML, etc. The larger the dataset, the lower the cardinality in general. So PG FTS tends to work okay for small/medium datasets where most records are unique and you don't need advanced features like misspellings, synonyms, etc. Some of that advanced stuff is possible, but it's not out of the box and can be hard to set up.
- antman 4y agoWhat does you expression "recall search" mean? The corpus is so diverse that wrong results are impropable?
- billythemaniam 4y agoRecall referring to precision and recall [1]. Recall search meaning the use case primarily cares about finding all the results and less about ranking them correctly (precision). So find all the records containing an email address regardless of order is a recall problem 1. https://en.m.wikipedia.org/wiki/Precision_and_recall https://en.m.wikipedia.org/wiki/Precision_and_recall
- ianbutler 4y agoPostgres Extensions should allow you to make a TF/IDF and BM25 plugin pretty easily as well as dealing with the other relevance problems.
- jerrysievert 4y agoYou can also do rapid prototyping using one of the scripting languages, then build a module after validating approaches. Python or JavaScript come to mind.
- vosper 4y agoIt's curious they omitted MySQL, which is the usual point of comparison for Postgres. > InnoDB full-text search is modeled on the Sphinx full-text search engine, and the algorithms used are based on BM25 and TF-IDF ranking algorithms. For these reasons, relevancy rankings for InnoDB boolean full-text search may differ from MyISAM relevancy rankings. > InnoDB uses a variation of the “term frequency-inverse document frequency” (TF-IDF) weighting system to rank a document's relevance for a given full-text search query. The TF-IDF weighting is based on how frequently a word appears in a document, offset by how frequently the word appears in all documents in the collection. In other words, the more frequently a word appears in a document, and the less frequently the word appears in the document collection, the higher the document is ranked. MySQL's FTS is fine. We're using it at work for fairly basic boolean searches on millions of documents, also retrieving the relevancy score, and it's plenty fast. We'll outgrow it one day, but for now it's pretty easy and does well enough. https://dev.mysql.com/doc/refman/8.0/en/fulltext-boolean.html https://dev.mysql.com/doc/refman/8.0/en/fulltext-boolean.htm...
- sandinmyjoints 4y agoAgreed that MySQL FTS is "fine". Have you run into issues with the default value of innodb_ft_result_cache_limit (2 GB)? That's bit us (OOM restarts) a couple times.
- sroussey 4y agoBTW: when you outgrow it, it will be sudden. It’s performance fails in a very non-linear way. Edit: keep the index in memory
- mark_l_watson 4y agoI thought the universal practice for getting good performance for relational databases, RDF, other graph, etc. data stores is to be able to hold indices in memory.
- sroussey 4y agoYes, but paged b-trees are more graceful when they can’t fit in memory—which was the default when I cut my teeth on databases. It’s also a reason why MyIsam separated data and index files. InnoDb is a clustered index, so all the data is packed next to the primary key.
- throwaway81523 4y ago> doesn't do TF/IDF or BM25 relevance calculations In practice these are nearly worthless. Useful relevance ranking is difficult. Google sort of gamed it with PageRank (using inbound links). "Information Retrieval" by Buettcher et al is a good book on search implementation with a decent amount of info about relevance ranking, though maybe it no longer up to date: https://mitpress.mit.edu/9780262528870/information-retrieval/ https://mitpress.mit.edu/9780262528870/information-retrieval...
- billythemaniam 4y agoIn practice, it depends on the dataset size and use case. For web search? Mostly worthless, but can be a valuable signal to train ML. For small corpus of documents? BM25 alone does a pretty good job in general.
- jrochkind1 4y agoUseful relevance ranking is definitely difficult, but a lot of people are getting something that they believe to be useful from, say, ElasticSearch or Solr, both of which use broadly TF/IDF-baesd algorithms. Are you suggesting that you can do just as well without TF/IDF, or with postgres fts specifically? In some/all circumstances? I'd be interested in hearing more about that, if it comes from experience. Looking at the table of contents for the Büttcher et al book, it looks to me like it covers TF/IDF-based algorithms pretty extensively. BM25 is in the table of contents specifically. Büttcher's own pedagogical search engine, _Wumpus_, includes a BM25 implementation. http://stefan.buettcher.org/cs/wumpus/docs/relevance.html http://stefan.buettcher.org/cs/wumpus/docs/relevance.html
- throwaway81523 4y agoThe only way I found to get any useful ranking in Solr was to implement application-level scoring of the documents based on semantic considerations of their contents, and also of relationships between the documents. And even that was pretty bad. I concocted some dubious schemes to condition those scores on external info as well, but the project ended before I got to try any of that. Yes that book described tf/idf and bm25 but a bunch of other stuff too that was somewhat more promising. Really though, IMHO there is no getting away from understanding the actual documents, and possibly their connection with the outer world (pagerank being an example of the latter). For web search it's now probably worse than before, since instead of merely being overwhelmed by noise, the data is now actually adverserial in the sense of having SEO trying to game your ranking. Even without that though, go on any retail site and try a search. The relevance ranking will be so awful that sorting by price or age or alphabetically will work a lot better. Same thing with the Algolia search here on HN. Chronological is almost always more useful than the search engine's idea of relevance. For automating relevance the scoring system needs much more semantic understanding of the data. Maybe that is more feasible with recent advances in NLP. I don't know whether that is good or bad.
- 1vuio0pswjnm7 4y agoHow about Xapian, an option that the author totally ignores. https://xapian.org/docs/bm25.html https://xapian.org/docs/bm25.html https://getting-started-with-xapian.readthedocs.io/en/latest/howtos/weighting_scheme.html https://getting-started-with-xapian.readthedocs.io/en/latest...
- throwaway81523 4y agoI think that isn't really built for large datasets. I had a buddy who used it a lot on smaller web sites though. I'm way out of date and this stuff might be horribly old fashioned. Vector search is the new hotness but on the other hand, search systems everywhere are getting worse, so who knows.
- rurban 4y agoNo, gmane was big enough. And it's far advanced over PostgresQL FTS or Elasticseatch
- 1vuio0pswjnm7 4y agohttps://xapian.org/users.html https://xapian.org/users.html Also, it is used by the the public-inbox Perl scripts. See https://public-inbox.org https://public-inbox.org That includes the Linux kernel mailing list, Git mailing list and other lists available via lore.kernel.org: https://lore.kernel.org https://lore.kernel.org For example, to search the BPF mailing list for "bpf" and sort results by relevance: https://lore.kernel.org/bpf/?q=bpf&r https://lore.kernel.org/bpf/?q=bpf&r To view the Xapian query parser operators: https://lore.kernel.org/bpf/_/text/help https://lore.kernel.org/bpf/_/text/help
- Justsignedup 4y agoI agree with all this. As a heavy user of pg_search I can also say that it is also not nearly as good when you need to combine multiple full text indexes in very complex queries. A dedicated indexing tool seems to have so many advantages, with the only 2 disadvantages being complexity increase and a slight indexing delay. Overall, pg_search is an amazing tool for low-complexity systems. Once you need really complex searching going on, a dedicated tool wins by a lot.