> Instead of joining the tables completely and sorting at the end, a Rank Join streams its inputs in descending score order (sorted access, or SA), building candidate result-sets as it goes.
Your algorithm feels like a variant of the WAND algorithm the Snowflake Top-K pruning paper [1] pulls from.
You can go distributed with this approach if you have a "gossip" protocol between workers to distribute the heap boundaries periodically.
Before the AI age, a "papers we love" group was a great thing within any company.
Now, Claude or Codex will know the SOTA literature around a topic like this and "uniformly distribute" the past into every single implementation of a similar idea. The future isn't uniformly distributed, but the past is getting the treatment & that's good.
Yes! Search engines like Tantivy have long employed WAND to score across terms. The difference though is that WAND is not joining terms in descending order by score: rather, by doc-id.
This algorithm is closer to Fagin's Threshold Algorithm (also mentioned in your link): the Threshold Algorithm was the first iteration of a rank join.
Searching what you stored is nice. But usually, you want to put some ETL (extract, transform, and load) in between your data base and search indices that enables you to enrich, transform, and improve data. If you are using vector search, this is also where you calculate your embeddings and run your data to elaborate tokenization pipelines. And you might do things like calculate categorizations and other classifications that you might use for filtering.
Search quality tuning inevitably involves iterating on how you index your data. The value of separation of where your database and search index live is that you can try out new indexing strategies and try different strategies.
I've been consulting on how to improve search quality for some time and sorting out ETL is usually the first thing I need to do for clients. A good question is "when did you last reindex your data". If the answer is never, that usually means the clien is probably not able to do this easily and that they probably made a lot of mistakes when they set up their system first. I've helped quite a few clients like that.
ETL doesn't have to mean bringing in a lot of complexity. A few simple python or whatever scripts can do the job. And many people don't actually have a lot of data which means these scripts can run quickly. I've had clients where it only took a few seconds to rebuild their search indices.
ParadeDB seems premised on the notion of just skipping all this. IMHO this is usually a mistake and if you were to do this properly, you'd still end up with a separate db from which you index into ParadeDB. Of course, if you do that, you could question if you could not pick something else instead.
This is neat, but I’m a bit confused by the query that motivates the whole article. If I search for ‘ocaml’, I want to match users’ about_me (the users.about_me ||| 'ocaml' part), but I do really want this to match on the basis of each (completely irrelevant) post and/or comment that gets picked up by the join? I think I would rather match the user, possibly with some user scoring by the overall user score independent of my search term.
I feel like I would probably execute three separate queries and merge the results myself. And the user query wouldn’t join against posts at all. Doing this would end up implicitly doing something like the optimization in the article.
ParadeDB is the best! I really like the Django integration (https://github.com/paradedb/django-paradedb). You get proper BM25 scoring, fuzzy matching, hybrid search, metadata filtering while still just using QuerySets. And you're keeping everything in Postgres, so there isn't any need to manage or sync a separate DB/search engine.
In my case I'm not so much interested by the BM25 aspect (I don't really have text to search), but I have collection of objects with many columns (having a small-ish number of values, et categories/tags) and I'd like to have an easy way to facet-filter them efficiently.
Right now with "vanilla Postgres" I have to guess which combination of facets is going to be common and try to define indexes for these. Would ParadeDB help there?
This looks exciting for some searches (top k), but the headline doesn't really fit. Yes - we still have to denormalize. Just not for some of the use cases paradedb targets. Impressive work.
Denormalization & Joins are mainly a thing from 80-90s when diskspace & compute was expensive; today its easy just do denormalize everything and not use joins, since diskspace & RAM today is abundant.
(sure, not true for that one verylarge enterpriseDB at megacorpX, but in 95% of uses cases these topics do not matter anymore)
That makes it rather annoying to keep data consistent though, and tons of people just won't take enough care to properly update everything. Having had to deal with that kind of half-out-of-date mess, I'd rather not, tbh.
Not really, as the article mentions: if you simply denormalize everything, each time you need to eg update a user name, you suddenly have to update its whole posts and comments everywhere, making it something quite expensive
a) thats the reason why lot of platforms do not allow to change username after signup
b) absolutely manageable with a solid tooling (and honestly, in 99% of cases this event is trivial as most systems just do not hold enough data to make it like a "eeek this change will run for 3 days for that 1 user")
But why do it? You yourself are saying that it increases resource usage (which is mentality that left us with electron BTW), and creates additional difficulty with keeping data consistent. What's the upside?
I've never worked on anything, and probably won't ever work, that wouldn't fit in modern machines even in heavily denormalized forms, and have zero desire to do it just for consistency sake. 3NF or up, with very rare exceptions.
Your assumption that increased resource usage is single concept with one outcome and no nuance is entirely false (where do the problems of engineering a desktop app even overlap with row level schema planning in a database?)
The claim that is somehow causes data consistency issues also seems kind of unsubstantiated.
The upside is that when you model it correctly your data conforms to your domain and business in a way that makes every aspect of its use easier.
I do not agree, I believe normalization leads to a lot of other benefits like making you think about connections between data much more carefully, and thinking about what you need for each request. Denormalized tables have led way too many times in my experience to hapless developers fetching enormous amounts of data just to use a tiny amount far too often.
And db performance absolutely is an issue. Agents mess it up all the time on our codebases...
Denormalization brings a complexity cost when updating to ensure integrity, though. And if storage and compute is cheap then you can easily get the benefits of denormalization without the downsides by keeping data normalized for consistency and instead build indexes to let you query it dernormalized when it makes sense.
The index is columnar, so the writes are less scattered on disk than in a row-style B tree even when the updated values are very scattered in logical order I think.
> Instead of joining the tables completely and sorting at the end, a Rank Join streams its inputs in descending score order (sorted access, or SA), building candidate result-sets as it goes.
Your algorithm feels like a variant of the WAND algorithm the Snowflake Top-K pruning paper [1] pulls from.
You can go distributed with this approach if you have a "gossip" protocol between workers to distribute the heap boundaries periodically.
Before the AI age, a "papers we love" group was a great thing within any company.
Now, Claude or Codex will know the SOTA literature around a topic like this and "uniformly distribute" the past into every single implementation of a similar idea. The future isn't uniformly distributed, but the past is getting the treatment & that's good.
[1] - https://arxiv.org/html/2504.11540v1#S5
Yes! Search engines like Tantivy have long employed WAND to score across terms. The difference though is that WAND is not joining terms in descending order by score: rather, by doc-id.
This algorithm is closer to Fagin's Threshold Algorithm (also mentioned in your link): the Threshold Algorithm was the first iteration of a rank join.
Searching what you stored is nice. But usually, you want to put some ETL (extract, transform, and load) in between your data base and search indices that enables you to enrich, transform, and improve data. If you are using vector search, this is also where you calculate your embeddings and run your data to elaborate tokenization pipelines. And you might do things like calculate categorizations and other classifications that you might use for filtering.
Search quality tuning inevitably involves iterating on how you index your data. The value of separation of where your database and search index live is that you can try out new indexing strategies and try different strategies.
I've been consulting on how to improve search quality for some time and sorting out ETL is usually the first thing I need to do for clients. A good question is "when did you last reindex your data". If the answer is never, that usually means the clien is probably not able to do this easily and that they probably made a lot of mistakes when they set up their system first. I've helped quite a few clients like that.
ETL doesn't have to mean bringing in a lot of complexity. A few simple python or whatever scripts can do the job. And many people don't actually have a lot of data which means these scripts can run quickly. I've had clients where it only took a few seconds to rebuild their search indices.
ParadeDB seems premised on the notion of just skipping all this. IMHO this is usually a mistake and if you were to do this properly, you'd still end up with a separate db from which you index into ParadeDB. Of course, if you do that, you could question if you could not pick something else instead.
This is neat, but I’m a bit confused by the query that motivates the whole article. If I search for ‘ocaml’, I want to match users’ about_me (the users.about_me ||| 'ocaml' part), but I do really want this to match on the basis of each (completely irrelevant) post and/or comment that gets picked up by the join? I think I would rather match the user, possibly with some user scoring by the overall user score independent of my search term.
I feel like I would probably execute three separate queries and merge the results myself. And the user query wouldn’t join against posts at all. Doing this would end up implicitly doing something like the optimization in the article.
Indeed. The query should maybe be a UNION ALL over individual search results instead.
ParadeDB is the best! I really like the Django integration (https://github.com/paradedb/django-paradedb). You get proper BM25 scoring, fuzzy matching, hybrid search, metadata filtering while still just using QuerySets. And you're keeping everything in Postgres, so there isn't any need to manage or sync a separate DB/search engine.
Any questions please go for it, ParadeDB team is watching.
I would like to try out ParadeDB and potentially retire Typesense but being unable to install it in CloudSQL makes it more than difficult.
In my case I'm not so much interested by the BM25 aspect (I don't really have text to search), but I have collection of objects with many columns (having a small-ish number of values, et categories/tags) and I'd like to have an easy way to facet-filter them efficiently.
Right now with "vanilla Postgres" I have to guess which combination of facets is going to be common and try to define indexes for these. Would ParadeDB help there?
This looks exciting for some searches (top k), but the headline doesn't really fit. Yes - we still have to denormalize. Just not for some of the use cases paradedb targets. Impressive work.
Denormalization & Joins are mainly a thing from 80-90s when diskspace & compute was expensive; today its easy just do denormalize everything and not use joins, since diskspace & RAM today is abundant.
(sure, not true for that one verylarge enterpriseDB at megacorpX, but in 95% of uses cases these topics do not matter anymore)
That makes it rather annoying to keep data consistent though, and tons of people just won't take enough care to properly update everything. Having had to deal with that kind of half-out-of-date mess, I'd rather not, tbh.
Not really, as the article mentions: if you simply denormalize everything, each time you need to eg update a user name, you suddenly have to update its whole posts and comments everywhere, making it something quite expensive
a) thats the reason why lot of platforms do not allow to change username after signup
b) absolutely manageable with a solid tooling (and honestly, in 99% of cases this event is trivial as most systems just do not hold enough data to make it like a "eeek this change will run for 3 days for that 1 user")
>a) thats the reason why lot of platforms do not allow to change username after signup
Nor any of the other user data that is indexed with every single post?
If I look at my youtube comment notification, Id say propably not? (Timestamp belongs to a post as well as likes etc.?)
This is true only if you have *very* specific data.
But why do it? You yourself are saying that it increases resource usage (which is mentality that left us with electron BTW), and creates additional difficulty with keeping data consistent. What's the upside?
I've never worked on anything, and probably won't ever work, that wouldn't fit in modern machines even in heavily denormalized forms, and have zero desire to do it just for consistency sake. 3NF or up, with very rare exceptions.
Your assumption that increased resource usage is single concept with one outcome and no nuance is entirely false (where do the problems of engineering a desktop app even overlap with row level schema planning in a database?)
The claim that is somehow causes data consistency issues also seems kind of unsubstantiated.
The upside is that when you model it correctly your data conforms to your domain and business in a way that makes every aspect of its use easier.
I do not agree, I believe normalization leads to a lot of other benefits like making you think about connections between data much more carefully, and thinking about what you need for each request. Denormalized tables have led way too many times in my experience to hapless developers fetching enormous amounts of data just to use a tiny amount far too often.
And db performance absolutely is an issue. Agents mess it up all the time on our codebases...
Denormalization brings a complexity cost when updating to ensure integrity, though. And if storage and compute is cheap then you can easily get the benefits of denormalization without the downsides by keeping data normalized for consistency and instead build indexes to let you query it dernormalized when it makes sense.
> today its easy just do denormalize everything and not use joins
You _can_ take this approach on a read-heavy db, but depending on your usecase you are going to struggle with updates and writes.
Or keep your data normalized, and maintain materialized views if and when they're needed.
The article mainly talks about searching.
What about the use case where data frequently gets updated as well? I assume you then get to update lots of duplicate data.
The index is columnar, so the writes are less scattered on disk than in a row-style B tree even when the updated values are very scattered in logical order I think.