semihsalihoglu

Indeed 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.

That's a topic quite separate from new join algorithms. I also don't know enough frankly but I don't yet see them being integrated in the systems that I'm aware of. I would be hesitant to put them inside KuzuDB since I don't see them resolving major performance bottlenecks. I think on the indices side, one interesting topic is to find more update-friendly disk-based CSR-based indices for graph DBMSs.

This is a good paper. It's likely to especially useful for people using GPUs in DBMSs. There is tons of research on this: https://www.nowpublishers.com/article/Details/DBS-076. It will be exciting to see when this could be the norm.

I 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.

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.

Please do :). We're a bit early but very actively developing the system!

If you have any good ideas about how to implement Tetris in a practical way, you can make a good impact here. This is the only work that I know that tried to implement these: https://arxiv.org/pdf/1503.04169.pdf (and excitingly published at GRADES workshop at SIGMOD, which I co-chaired twice and is very dear to my heart). But I talked to the authors and they all agree that despite the tone of the paper, they found them quite difficult to implement in a performant way.

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!

Can you clarify what you mean by byte-sized implementations? There are several systems now that implement these algorithms, KuzuDB, Umbra, LogicBlox (the earliest was this) are examples I know. I'm sure more will come.

You are welcome :)

Interesting. I think there are groups that does quite interesting work on linear algebra that intersects with wcoj algorithms: This keynote abstract should give some pointers on this group's work: https://www.vldb.org/pvldb/vol13/p3502-olteanu.pdf.

I wrote about a (relatively) new class of join algorithms for DBMSs that are called "worst-case optimal join algorithms". This is a topic that has kept me very busy for the last 5 6 years and the post aims to explain the simple ideas behind it and why it is the type of algorithms that graph DBMSs should integrate (and we have at KuzuDB: https://github.com/kuzudb/kuzu).

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!

echoing _frkl: yes, kuzu aims to fill exactly this space. an easy to use dbms that gives you the ability to model your records as a graph, do common querying and transformations, and extractions all in a high-level graph-specific query language. we are very new and have quite a lot to go but it still implements many cypher clauses, so many things can still be done.

I agree. As I say in the blog, there is no perfect data model. RDF is great fit for certain things, e.g., when storing dbpedia-like datasets, and doing "automatic" advanced OWL reasoning over it by implementing OWL rules. For example, if a record t X is of type Y and there is a rule that says Y is of type Z, then by OWL reasoning rules, X is of type Z. So if a user scans all Z's, a system that does automatic OWL reasoning should return record t. RDFox is an interesting system that attempts this and has a niche space. Overall the semantic web community has thought greatly about these types of problems and pioneered these types computations.

Property GDBMSs can do manual reasoning queries if you ask questions with Kleene star but they would have to implement OWL rules and "OWL rule" data type, and URI data type etc. There is no other way I'm aware of. I am convinced with the right architecture this should be possible and if we see interest in this, we might work on this in Kùzu. But currently we definitely plan to support URIs as first class citizen data types so at least common queries over URI-heavy datasets and manual reasoning can be done efficiently, and that should cover most use cases for applications that want to model their data as triples of URIs.

provide a lesson -> provide a proof.

I can't say something very insightful as I don't know it closely. My shallow understanding was that it is a modern json/xml-like dbms supporting a nested object (tree-like) model and path-expression-based query languages of such systems. If this is accurate, such models are graph-based as well, so the feature set on my blog would largely apply to them as well.

This is actually a very good point and unfortunately formal verification is not the current norm when developing DMBSs or complex systems software. If you asked how do you know DBMS X is correctly implementing snapshot isolation, no one will be able to provide a lesson for you. This is true for every system out there I'm aware of. This goes more deeply actually about questions like this: "how do you know you implement SQL or Cypher correctly". In fact, we can't even sometimes very formally answer "what is the meaning of this query X". Back in the day my PhD advisor Jennifer Widom, who had a background in programming languages, talked a lot about how we put DBMSs into everywhere, e.g., planes that are flying up in the air, yet we can't really precisely state what the outputs of queries should be. She had some excellent writing on this for implementation of triggers that were coming out of different groups. She was one of the pioneers of triggers before triggers existed in SQL. And as I assume you might know better than me, Leslie Lamport is known as a pioneer in the distributed systems space for formal verification of programs.

Your comment on shortened URLs is noted. This is my first HN post ever :), so I might need to pick up the customs.

I tried to talk about "what it should do" at a higher-level. As a comparison, if you want to read something that is similar in spirit but discusses "how GDBMSs should do" certain things, you can look at the link I have in footnote 4. This is what I call the CWI list of how GDBMSs can be architected to be competent. The CWI list's items are specific implementation and optimization "techniques", like columnar storage, vectorized processing etc.

I can happily say that this list comes from Peter Boncz, who was an early pioneer of analytical RDBMSs, and Peter and I have similar opinions on these core architectural decisions here. And Kùzu currently adopts (or we are implementing) 11 of 12 techniques there.

FYI, in my next posts, I will talk about "how a GDBMS should do" features 1 and 2 in my list, using specific query processing techniques we have implemented in Kùzu.

We are building one (https://github.com/kuzudb/kuzu)! :)

Interesting. I think the required computation is different for 2 different cases you have in your post.

Case 1: If you have = relationships (let's call the type of the relationship eq). Then what you need is to identify weak connectivity. If you want to do find the equivalence class of a single node, say with primary key "foo", you can do this with a Cypher query using Kleene star:

"MATCH (a)-[:eq*]->(b) WHERE a.pk = "foo" RETURN DISTINCT b"

This finds the "weakly connected component" of node "foo". If you want to find all equivalence classes, that's equivalent to finding all weakly connected components and you should probably call that algorithm from the algorithms library built over the GDBMS (e.g., https://tinyurl.com/mtx98c5s). You can do it in Cypher but it will be very slow.

Case 2: You have <= relationships, so relationships are not symmetric, so you want to find strong connectivity of nodes. I won't type it here but you could do this with a Cypher query for a single node but for all nodes again you can call the strongly connected components algorithm from the algorithms library of the GDBMS.

You can do some of these natively in Datalog, but if you implement it yourself in a native query language, but the computations is likely to be quite slow. So it might still be better to call a specialized algorithm that's implemented in a library above the DBMS you are using.

Hope this helps.

Yes, this will be interesting to see. This is the SQL/PGQ extension that's coming in 2023. On the one hand, as I articulate in my post, GDBMSs are based on relational principles, so building a system that can seamlessly query in relational and graph model is a good idea. On the other hand, there is this: (1) no SQL extension into a graph-based model has been successful historically (e.g., into RDF or XML or even json). That seems to confuse users, so sticking to a single model seems like a good idea. (2) RDBMSs that implement SQL/PGQ will not be very performant unless they change their cores with several techniques I and my research group has been advocating for (e.g., how to do predefined joins, worst-case optimal joins, factorization etc.).

One of the core developers of Kùzu, Guodong Jin, actually wrote his PhD thesis on a project called GRainDB, which showed how to integrate predefined joins into DuckDB, so an RDBMS can be made efficient on "graph workloads". He did this excellent work: https://www.vldb.org/pvldb/vol15/p1011-jin.pdf, https://www.cidrdb.org/cidr2022/papers/p57-jin.pdf, which articulates a good plan for how RDBMSs can be efficient in a mixed relational-graph model.

Well, it'll be very interesting to see where SQL/PGQ goes...

Agreed.

I realized, I forgot to complete my sentence here: "...because of this every semi-structured graph model historically has been extended with a schema." Examples include, XML and RDF. More relevant to this discussion: there is an ongoing effort to define a graph schema in GQL, which is an industry-academia effort including I think all major players: Neo, Tiger, Oracle etc. (https://www.gqlstandards.org/home).

You can search for this on the link: "GQL will incorporate this prior work, as part of an expanded set of features including regular path queries, graph compositional queries (enabling views) and schema support."

I don't quite follow the question here but to clarify one thing: Kùzu is currently integrating Arrow not as a core storage structure but as a file format from which we can ingest data. We are writing Kùzu's entire storage, so it's our own design. It has three components: Vanilla columns for node properties, columnar compressed sparse row (https://tinyurl.com/2r2s4wpe) join indices and relationship properties, and a hash index for primary keys of node records. We don't use Arrow to store db files.

For serializability: yes, we support serializable transactions. So when you insert, delete or update node, rel records, you get all or nothing behavior (e.g., if you rollback none of your updates will be visible).

That said, supporting ACID transactions is a compeletely separate design decision in DBMSs, so our (or other systems') mechanisms to support transactions (for example whether it's based on write ahead logging or not) and storage designs are generally mutually exclusive decisions.

I think it's a mistake for any DBMS to not support a schema. I bet this hurts Neo4j a lot and no question that this is a mistake. In fact some GDBMS, including Kùzu or TigerGraph supports a schema. I think MemGraph does too, though I might be wrong. Schema allows systems to do many core computations efficiently, most importantly scans of data, which is the backbone operation of DBMSs. In fact, because of this every semi-structured graph model historically has been extended with a schema.

In practice, if you want DBMSs to be performant, you need to structure your data. It's one thing to optionally support a semi-structured model, which is for example great when building initial proof of concepts when you want to develop something quickly. It's another thing to not support putting a structure on the data, which you'll want when you finally take your application to production and will care about performance.

When you insert the Transfer records in my example, you indicate that they are "edges/relationships" between "Account" node records. The system interprets the values in those records implicitly as foreign keys to the Account records. This is what I mean by "predefined joins" in my example. When you ingest your relationship records, you predefine a join to the system and the GDBMS uses those Transfer records to join node records.

Hope this helps.