4 ms·
Not sure what you mean by lazily but in general this sub-optimality can't be fixed by joining relations 2 at a time. You need a different algorithmic step that
by semihsalihoglu 4y ago
Not sure what you mean by lazily but in general this sub-optimality can't be fixed by joining relations 2 at a time. You need a different algorithmic step that takes > 2 relations and joins them "column by column". That's why you need new "multiway join operators". So you cannot just use existing join operators in a traditional system and fix things.
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.
- throwaway81523 4y agoWhat I mean is that the query planner can decide to do a multi-way join, just like a compiler can reorganize arithmetic expressions or vectorize loops. It is a high level transformation but databases are allowed to do that.
- semihsalihoglu 4y agoI see, that's for sure. That's what every system does in one way or another. Both of the papers I have listed there describe different ways to do it: the Graphflow paper (and Kuzu) currently does this inside their dynamic programming-based join order optimizer. Umbra does it after a good join order is picked.
- throwaway81523 4y agoRight so I don't see where graph db's come into this. Regular SQL can handle it.
- semihsalihoglu 4y agoIndeed pretty much everything is doable in every DBMS, graph or relational, simply because all DBMSs from enough distance are very similar in terms of their core features: a high-level query language that compiles to relational operators, support for transactions, a recovery mechanism etc. What differentiates them (aside from the data models and specific query language syntax they expose to users) are what type of applications they choose to provide optimizations for. Graph DBMSs immediately come into mind for wcoj algorithms because the applications they support frequently contain cyclic many-to-many join queries, which is the workloads wcojs can provide performance benefits. RDBMS, OLAP or OLTP don't assume their application workloads contain such queries. That is why every work done on wcojs so-far has used "graph patterns and workloads" in their evalution, not something like TPC-C or TPC-H.