4 ms·
The 14th way is “multi way joins” also called “worst case optimal joins” which is a terrible name. It means instead of joining tables two at a time and dealing
by maxdemarzi 3y ago
The 14th way is “multi way joins” also called “worst case optimal joins” which is a terrible name.
It means instead of joining tables two at a time and dealing with the temporary results along the way (eating memory), you join 3 or more tables together without the temporary results.
There is a blog post and short video of this on https://relational.ai/blog/dovetail-join https://relational.ai/blog/dovetail-join and the original paper is on https://dl.acm.org/doi/pdf/10.1145/3180143 https://dl.acm.org/doi/pdf/10.1145/3180143
I work for RelationalAI, we and about 4 other new database companies are bringing these new join algorithms to market after ten years in academia.
- namibj 3y agoNegating inputs (set complement) turns the join's `AND` into a `NOR`, as Tetris exploits. The worst case bounds don't tighten over (stateless/streaming) WCOJ's, but much real world data has far smaller box certificates. One thing I didn't see is whether Dovetail join allows recursive queries (i.e., arbitrary datalog with a designated output relation, and the user having no concern about what the engine does with all the intermediate relations mentioned in the bundle of horn clauses that make up this datalog query). Do you happen to know if it supports such queries?
- gavinray 3y agoJustin also has a post on WCOJ that's really solid: https://justinjaffray.com/a-gentle-ish-introduction-to-worst-case-optimal-joins https://justinjaffray.com/a-gentle-ish-introduction-to-worst...