4 ms·
The BM25 thing is actually a really big deal. BM25 is similar to TF/IDF. In both cases, the key idea is to consider statistics of the overall corpus as part of
by simonw 2y ago
The BM25 thing is actually a really big deal.
BM25 is similar to TF/IDF. In both cases, the key idea is to consider statistics of the overall corpus as part of relevance calculations. If the user searches for "charities in new orleans" in a corpus where "new orleans" is only represented in a few documents, those should clearly rank highly. If the corpus has "new orleans" in almost every document then the term "charity" is more important.
PostgreSQL FTS cannot do this, because it doesn't maintain statistics for word frequencies across the entire corpus. This severely limits what it can implement in terms of relevance scoring - each result is scored based purely on if the search terms are present or not.
For comparison, SQLite FTS (which a lot of people are unaware of) actually does implement full index statistics, and SQLite FTS5 implements BM25 out of the box.
- beardedetim 2y agoBM25 is definitely a big deal when you're doing FTS. It's one of the reasons I've switched to Arango as my DB for the project I'm working on that needs FTS. The fact it also comes with graphs means I don't need to bang my head against CTEs either. Not saying Arango can replace Postgres but for my needs, it's a much better fit AND it offers the FTS that I need out of the box.
- philippemnoel 2y agoArango is sweet! We've actually talked to many people who switched from Postgres to Arango because of its better FTS. This was one of the reasons for creating ParadeDB in the first place. Many of the users who made this switch wished they could have stayed in Postgres without compromising on FTS.
- packetlost 2y agoI wish SQLite FTS had a nicer to use API. Last time I looked (a few months ago) it was very confusing and not very user friendly.
- simonw 2y agoI've built a bunch of Python (and CLI) code to try and help make that work better: https://sqlite-utils.datasette.io/en/stable/python-api.html#full-text-search https://sqlite-utils.datasette.io/en/stable/python-api.html#... import sqlite_utils db = sqlite_utils.Database("news.db") db["articles"].enable_fts(["headline", "body"]) results = list(db["articles"].search("softball")) Or with the CLI tool: https://sqlite-utils.datasette.io/en/stable/cli.html#configuring-full-text-search https://sqlite-utils.datasette.io/en/stable/cli.html#configu... sqlite-utils enable-fts news.db articles headline body sqlite-utils search news.db articles softball
- packetlost 2y agoThat's cool, maybe I can use it as a reference. Thank you!
- sroussey 2y agoThe problem with BM25 in a database, is that is can have unexpected outcomes for some common use cases. Take multi-tenancy. What if user 1 has many more documents than user 2, and uses "new orleans" a lot. But user 2 does not. User 2 does the search. The db will first use FTS, and then filter. So user 1 will bias the results of user 2. Perhaps enough for user 2 to discover what words are in user 1 corpus.
- simonw 2y agoDoesn't that affect BM25 with a solution like Elasticsearch as well? Or is that smart enough to apply filters to the corpus statistics before calculating relevance? You could solve that in SQLite by giving each user their own separate FTS table - not impossibly complex, but would grow increasingly messy if you have 10s of thousands of users.
- vosper 2y agoOne way to address this in Elasticsearch would be to put each customers documents in their own index. Other than that, as far as I can tell it's not smart enough to apply filters first. Also, shards can affect BM25 scoring: https://www.elastic.co/blog/practical-bm25-part-1-how-shards-affect-relevance-scoring-in-elasticsearch https://www.elastic.co/blog/practical-bm25-part-1-how-shards...
- nemo44x 2y agoIt’s why you need “enough” data. Generally the distribution of teens is a power-law distribution. There’s a set of common terms and a very long tail of other terms. This will be the case across every shard if you do in fact have enough data per shard. This becomes a factor in certain distributed aggregations as well. YMMV of course. In general you trade accuracy for speed. You tend to get a lot of speed for just a small amount of accuracy sacrifice.
- sroussey 2y agoOh sure, but it is a side channel attack to be aware of.
- formerly_proven 2y agoI've learned information retrieval in university before ever using any full text search engine and I was honestly kinda surprised that most engines are literal textbook implementations. IR was one of those courses where I definitely expected the SotA to be further out than the third slide deck.
- jhanschoo 2y agoIt kind of is now if you count deep-learning based solutions to an information need haha
- formerly_proven 2y agoThat is true
- chatmasta 2y agoThat’s probably because SotA in IR is proprietary implementations like Google Search, the most bread-and-butter trade secrets of their business. So they’re not publishing that (at least in any holistic manner, and even if they did, it’s not like one product could implement all its functionality including the complexities around the periphery). And what you’re left with is some pretty decent parity between industry and academic SotA, same as a lot of other areas of CS (databases, decentralized systems, etc). If anything, in most cases, implementation lags behind academic theory.
- SigmundA 2y agoThere was some work toward this, not sure about its current status: https://github.com/postgrespro/rum https://github.com/postgrespro/rum Badly needed.
- philippemnoel 2y agoRUM indices are a nice improvements, but they're not in Postgres core and likely won't ever be :( If you're looking for Elastic-level FTS in Postgres, your best bet is likely to overengineer pgvector+tsvector or simply to use ParadeDB pg_search
- jonahx 2y agoIt's been a while since I used tools in this space. Some questions: Where does AI/semantic search/vector DBs fit into the state of the art today? Is it generally a total replacement for traditional text search tools like elastic, or does it sit side by side? Most, but not all, use-cases I can think of would prefer semantic search, but what are the considerations here?
- evv555 2y agobm25 is often used along side vector search with a reciprocal rerank algorithm.
- marcyb5st 2y agoAs others mentioned you want to do combine both semantic and td-idf like searches. The thing is that searches that carry no semantic weight (e.g. a part number) or that have special meaning compared to the corpus used to train your embedding model (e.g. average Joe thinks about the building when seeing the word "bank", but if you work in a city planning firm you might only consider the bank of a river) fail spectacularly when using only semantic search. Alternatively you can finetune your embedding model so that it was exposed to these words/meanings. However, the best (from personal experience) is doing both and use some sort of query rewriting on the full-text search to keep only the "keywords".
- eskibars 2y agoAs others in this thread have mentioned, semantic/vector-based solutions tend to be much better when any of the following is true: 1. There are natural language questions being asked 2. There's ambiguity in any of the query terms but which there's more clarity if you understand the term in context of nearby terms (e.g. "I studied IT", "I saw the movie It", "What is it?") 3. There are multiple languages in either the query or the documents (many embedding models can embed to a very similar vector across languages) 4. Where you don't want to maintain giant synonym lists (e.g. user might search for or document might contain "movie" or "film" or "motion picture") Whether you need any of those depends on your use case. If you are just doing e.g. part number search, you probably don't need any of this, and certainly not semantic/vector stuff. But semantic/vector systems don't work well with terms that weren't trained in. e.g. "what color is part NY739DCP?" Fine tuning is bad at handling this (fine tuning is generally good for changing the format of the response, and generally not all that good for introducing or curtailing knowledge). Whether you need a keyword search system depends on whether your information are more of the "general knowledge" type or something more specific to your business. Most companies have some need for both because they're building a search on "their" data/business, and you want to combine the results to make sure you're not duplicating. But I'll say I've seen a lot of companies get this sort of combination business wrong. Keeping 2 datastores completely in sync is wrought with failure, the models all have different limitations than the keyword system limitations which is good in some ways but can cause unexpected results in others, and the actual blending logic (be it RRF or whatever) can be difficult to implement "right." I usually recommend folks look to use a single system for combining together these results as opposed to trying to invent yourself. Full disclosure: I work for Vectara (vectara.com) which has a complete pipeline that does combine both a neural/vector system and traditional keyword search, but I would recommend that folks look to combine these into a single system even if they didn't use our solution because it just takes so much operational complexity off the table.
- anacrolix 2y agoI didn't realise it was such a big deal. I wrote a custom BM25 and (faceted? boosted?) search implementation using roaring bitmaps, memory mapped files and pebble to replace sqlite FTS when it couldn't cope anymore with my requirements (100+ GB search index).