Graph DBMSs need new join algorithms: Story of worst-case optimal joins
kuzudb.com
kuzudb.com
If you're curious about how come database researchers/developers still work on joins after 50 years, it's because what is possible and what is not is actually not that well understood. After many decades wcoj algorithms was probably the biggest algorithmic leap in the field. Many people are looking into information theory and computational geometry to improve our understanding. There is even more advanced but currently unpractical algorithms called "beyond worst-case optimal" join algorithms, which I briefly leave pointers to at the end of the post.
Enjoy reading!
Granted, it needs a good datastructure; I'm waiting for a friend to find time to discuss options there.
I'm firmly of the belief that beyond-wcoj is a question of implementation, not of theoretical suitability in practical scenarios.
So here's the problem. The core algorithmic step of "beyond wcojs" are "geometric resolutions". The core idea is to work with gaps in the space. So for example suppose we are joining two relations R(A), S(A) which is an intersection and suppose A is an integer domain. Suppose further than R's maximum A value is 100, and S's minimum value is 101. Then there is a gap of (100, \infty) in R's space and another graph (-\infty, 101) in S's space. If you "resolve/join" these gaps, you get a gap of (-\infty, \infty), which tells you in one operation that the join's output is empty.
On this simple query, this seems to work fine but if you have general relations (let alone non-integer data types) doing such geometric "resolutions" and finding efficient indices to index those "gaps" becomes quite challenging. But any good idea here will push the field!
An especially interesting area to us is how to redo these to be accelerated with GPUs. Ex: See https://www.adms-conf.org/2014/adms14_wu.pdf
We've been taking a worse-is-better approach to use these kinds of ideas that seems worth writing up at some point. Super fun time for rethinking these :)
For the latter part of your question: Yes, there is at least on RDBMS, Umbra, that implements wcoj's. I have a pointer to it in the blog post. Although, I'm convinced eventually many GDBMSs will integrate these algorithms, whether RDBMSs will broadly integrate these is less clear to me. The reason is not whether it's doable or not. Every DBMS, graph or relational, is relational at its core, in the sense that they compile high-level query languages to joins, groups by, filters, scans etc. In fact wcoj algorithms were invented assuming a relational system joining multiple relations. The reason is whether they care enough because wcojs are primarily for "cyclic joins" and they don't appear too often in traditional olap workloads, which are aggregation-heavy. Cyclic joins are more frequent on workloads on GDBMSs (e.g., finding a clique of users to develop a recommendation engine). So these algorithms are more critical for GDBMSs.