Good morning, everyone.
I will be doing my best to speak loudly.
Is it OK in the back?
OK, it comes up.
Hi, everyone.
I'm Gabor.
I'm here to talk about graph databases, specifically where they come from, where they are, and where they are headed.
So my background for this is that, for the last 13 years, I did a lot of work on graph databases.
I did my masters, my PhD and postdoc in graph databases.
Two years ago, I pivoted to the relational databases at DuckDB for my day job.
But I still have a special place in my heart for graph databases.
And I'm happy to come here and tell you my experiences and lessons I learned about them.
So what is this talk about?
I would try to bring you up to speed in 50 minutes on what graph databases are.
And then you can decide whether they are something that you want to use.
There is a chance that you don't really have a graph workload, but I encourage you to stick around,
because I will show you some new research results that are applicable for graphs and also outside of graphs.
And then finally, I believe performance is really important for data analytics,
so I will give you a bunch of pointers for benchmarks and how to compare graph database systems.
So let's get started.
For this talk, I will use a running example that's rather complicated graph.
It has four types.
Countries, cities, people, and messages.
And it encapsulates this weird social network in the low countries,
where everyone and every city has a name with only three or four letters in the sake of fitting on the slide.
We have four cities, a bunch of people, and you have the sort of edges between them that you would imagine.
People know each other, people write messages, people are located in a city and so on.
So what are graph databases in the first place?
The definitions vary a lot, and it's really difficult to agree on what constitutes a graph database.
But if you go to a graph database, meet up, or if you open the website of any of the vendors,
there seems to be one thing that almost everyone agrees on.
And that common theme is that joins our bad.
If you go to a graph database, meet up, you get handed merch like this.
Graph constructions own no joins behind this point, or they say no expensive runtime joins,
or you should leave join those who left joins behind and leave joins behind.
So what are they on about? It's kind of a bit murky, they don't really give any specific examples.
I argue that sometimes they try to imply that relational databases cannot join, which is obviously an overstatement.
Relational databases can join actually rather well.
But then what's the problem? Well, let's take the middle part of our social network, where we have four cities and seven people,
and we want to ask a question, where do the friends of the person then live?
We can take this graph and then we can represent it as two tables.
We have a no stable with person one and person two pairs, and we have a location table that says where a specific person lives.
Now it's easy to see from the graph that then has two friends, car and deer, and they live in mall and os.
And you can also see that these are represented in the tables.
But if you try to write a secret creatively, you may end up writing something like this.
You want to select the city from the no stable joint on the location table on the corresponding attributes, and you filter for Dan.
But you will get only one city, you will get only os. What did we miss?
We miss the fact that the no's edge is bi-directional, and this is not captured in the data.
So what do we do? Well, one thing we can do is we can rewrite the query to make up for this.
Another thing we can do is we can insert those edges into the no stable flipped, so that we will introduce some redundancy,
but then the query will work.
Or we can just do a view that captures the undirected no's edge by flipping the edges in union or all.
All of these work, but already at this very simple complexity level, it starts to become a bit clunky.
So this is one thing graphed at a basis, got really right.
Most graphed at a basis have a syntax that is more elegant for capturing joints on something like this.
They provide really concise and elegant syntax, and they also provide an elegant syntax for handling the bi-directionality.
For example, the cipher query language, which is shown here on the right, has this construct where you can do brackets,
and just dash is saying this is an undirected edge.
And the rest is also simple, you say match for pattern matching p1 for person1, the name of the person location as a bracketed edge, and then return what you need.
So most graphed databases have some sort of syntax sugar for expressing joints concisely.
And there are actually quite a few graphed databases, and in the next couple minutes I will go through them.
You can think about them as some systems along the transactional to analytical spectrum.
So the more transactional system is, the more right oriented it is, and the more focused it is on high throughput,
and the more analytical is, the more focused it is on running queries that are long running and read a lot of data.
And I will argue that other than providing syntax sugar for joints, they also address other joint problems.
Namely, the first category addresses something that is called the repeated joint problem.
What does this mean?
Well, let's take another slice of the social network with just the bagency of more.
And imagine we have a client application that needs to render this in the user interface in some form.
What happens here is that you can do maybe five joints and then return the table.
It's actually not just five joints, you have to do left joints, you have to do some filtering,
and ultimately you will end up with this kind of universal schema of all your data.
But it has a bunch of problems. A big problem is redundancy.
You have to spell out the city name, the postcode and the population for every person who lives there.
Then you have to spell out all the person data for every message that they created.
You have a bunch of nows, and this is just difficult. It's also quite difficult to reconstruct the graph on the client side from all this data.
This is known as the overfetching problem.
You run complex queries, you overfetch, and then the client has to do extra work.
So in practice, almost no one does this. What they do instead is that they do iterative ramp trapping.
They first get the cities, they then get the people in the city, and then they get their messages.
But this is known as underfetching, because you don't get enough data to actually answer your problem.
You end up doing n plus one iterations, just always have to get more data and more data.
This is expensive, you run trip on the network.
So this is kind of seems like a tough problem, and as most tough problems in computer science, it has a name.
This is the impadence mismatch problem from object relational mapping.
The impadence mismatch problem states that if you have a graph like object oriented model and relational model for your relational database,
those are really difficult to map, and they don't really play nicely with each other.
So one potential solution to this was invented by the API folks. This is GraphQL, which allows you to have a query on the left,
where you can specify in this nest structure that you want the social network, then the city, it's people, and it's message and their messages.
And then you can return an SD data structure, which usually is represented as JSON, and is a rather nice encapsulation of what you had.
We don't over-pfetch, we don't under-fetch, there is no redundancy, and it's easy to reconstruct the graph from what you received.
So this was actually picked up by a bunch of graph databases.
Another solution that graph databases do, like Ori and DB, is they extend SQL by having some sort of a dot operator for introducing newer edges and navigating along the edges of the graph.
In the stock, because we are at first them, I will also focus on the licensing aspects of projects, and Ori and DB is an interesting one to start with.
So it was originally a patchy project, then it was bought by SAP, the company was bought, they spun out and enterprise version of it, and they saw licenses for it, then they abandoned it.
Ori and DB lives on in three different versions, one is a conceptual fork represented by the light bulb, that's called Arcade DB.
One is a fork called Utrecht DB, which actually powers the JetBrains Utrecht system for issue tracking, and there is still the original system.
So it kind of forked off into three different projects.
Another system is Microsoft Cosmos DB, this is an interesting system because it runs in the Microsoft Cloud, so it's obviously a proprietary piece of software.
And it has this really famous use case of powering GenGPT, so that's kind of something a graph database can do.
And Microsoft offers another SQL-like rule language, which is similar to Ori and DBs.
It offers the Grammly language, and very interestingly, it offers a MongoDB compatible API.
So this already illustrates that some graph databases don't really do complex pathways or pattern matching.
They just do some document database style operations, because that's what people want.
They want to think about their data as a graph, but they want to create in terms of nested JSON-like data structures.
And one very nice evidence for this is that Microsoft actually spun out an open source fork of Cosmos DB, which is called Document DB.
So this is really for document processing, it's licensed MIT, and it is running on top of Postgres.
A bunch of other graph database systems are here, what you can note here is that graphQL and various graphQL forks are quite popular, as well as data log and the Grammly language.
If you ever look for something like a graph serving system that does this sort of nested data returning queries,
you should look for something that's backed by a key value store, a document store, or it's called a real-time graph database,
if you go to the DB engines ranking and you open the list of graph databases, these will be called multi-modal systems, which are also document stores as kind of a second data model.
So if I want to put a label on this, I would call this the Mongo DBs of the graph database space.
The second category is interesting too. I would call them classic graph databases as a temporary name, and they basically solve the problem of recursive joins.
Well, if you want to do something like shortest path finding, no way, just try to find the shortest path between two people, then you would do something like this,
between Dan and Finn, obviously everyone can see that the shortest path is through Ada and Carr.
But if you want to get the same answer from a SQL system, you will end up writing something known as a recursive query with the recursive closing SQL,
and you end up with a monstrosity like this. I have spent a lot of time refining this query, but you do have to use lists to keep track of where you've been, you have to use window functions to look around the table,
and it's not efficient to write, it's not nice to read, and it's also not efficient to run, so this is obviously a big limitation of SQL 99.
Luckily, graph databases have another trick up their sleeves, inside for you can just say, you want the nose asterisk for cleaning star,
and then you want a shortest path and then you return this. This is basically as simple as it gets, obviously to start different compared to the SQL query.
And this language sci-fi was introduced by the Neo4j database system, Neo4j is kind of the first modern graph database,
and they did great work in introducing sci-fi, turning it into open source with a specification called open sci-fi,
and then pushing it through the ISO standardization process to EADGQL.
Neo4j also did amazing advocacy works, they ran more than 10 fourth-dumb dev rooms, published books when meetups and so on.
Neo4j is a transactional system in nature, but it leans into analytics, it has an analytical suite for graph algorithms,
and if you get the enterprise version, it also has a parallel runtime for more complex queries.
Another system that you may have come across in the last 10 years is called Titan, or it's called Genus Graph, or it's called Huge Graph.
This has also been forked multiple times, and most of those forks are no longer maintained.
The current version that's maintained is maintained mostly by by-do, and it's an Apache project,
and it focuses on highly transactional setups where you store the graph distributably, mostly create with the Gramlin language,
and focus on short reads and high throughput transactions.
Other systems in this category include AWS, Neptune, Galaxy-based graph scope, mamm graph, Nebula graph,
notably Google Spender Cloud, which is a new player, just being a few years, a few days ago, and Altypa.
And you can see that there are three languages here, Gramlin systems, Cypher systems, and GQS systems.
So it's kind of not unified yet in terms of three languages, but these are the key players.
This is the category, which is really popular in terms of mapping it back to relational database system.
Most of the legacy vendors, IBM, Oracle, Microsoft, they have versions of their systems of different maturity levels that do graph queries.
There are also postgres extensions and working progress implementations in postgres.
So I think it's fair to say that this is the postgres of graph database systems.
They do transactional workloads, bunch of joins, and they also do recursive joins.
And the final category is graph BI or graph overlap.
If you will, this focus is on many too many joins, complex recursive joins, and other graph patterns.
So what are complex recursive joins?
Well, instead of doing shortest path, we can do weighted shortest paths, also known as cheapest path.
For example, if you take our random social graph, we can do some crazy queries like, let's pick two cities.
Let's get the residents of those people, then let's do a Cartesian product between them,
and then try to find all the cheapest path between them.
This is, of course, a very heavy-hitting operation, and it needs very special algorithms to deliver it.
Namely, because you need something like a multi-source, multi-destination bi-directional cheapest path algorithm,
which is something that isn't even there in terms of research as far as I'm aware.
So this is something where real innovation can happen if someone wants to run these queries quickly.
Maybe a more mundane example is cyclic queries, so a typical use case for databases in the graph space are the recommendation problems.
So you can do something like, try to find people who have a lot of shared interest.
So I added a bunch of topics that people are interested in, mostly based on music genres,
and we can do a query like this.
Let's take the nosages, join interest one, interest two, and make sure those two are the same.
So visually, you can see that Ada and Bob have two shared interests, rock and ska,
and Ada and Carl have one shared interest, rap music.
So this is a triangle, and the triangle queries have this interesting problem that if you start to calculate them,
they will have huge intermediates, even if the end result is actually not that big.
The intermediates can blow up, but they only blow up if you do it with the so-called binary joins,
when you join two operands together.
So if you do interest one, nose and interest two, with binary joins, no matter how you order them,
it can blow up, and it can blow up quadratically, where m is the number of edges.
Obviously, this is not going to finish, but interestingly enough, if you do multi-way joins,
then you can get it down to n on the power of 1.5, which is still worse than n log n,
but it's something that we'll finish eventually.
And the third category is acyclic queries.
This is also kind of new research, which is, if you run a query saying, which persons have more topics of interest than friends,
kind of an evil query, then we can do this actually quite simple secret query that says, take the nose edge,
join it on the interest, and then just do group by on the person in the middle,
and try to find the number of topics that they are interested in, and the number of friends that they have,
and if there are more topics than friends, then that's a match for this query.
So we can see that both, for example, are two friends, but five interest, so he will qualify for the results of this query.
The problem is, is that if we do this join, we will get a huge blow up again,
because you can see that we have a topic, person one and person two, and every time Bob would get a new friend,
have to repeat all of his hobbies in the table, and every time he would get a new hobby,
we would have to list all those friends that he already has next to the new hobby.
So this is kind of another quadratic style blow up, and this is caused by a multi-value dependency,
which means that the person one in the middle is conditional independent on the two sides, both the topics,
and the friends that they have are independent.
And this is a common pattern that's introduced by many to many joins,
and it's not only common, it's very predictable, so it's easy to compress away,
and this compression is captured by something known as factorization.
factorization is a lost-less compression method for relational tables,
and you can take a big flat table on the left, and turn it into something known as a factorized table.
And the factorized table is basically this union of little Cartesian product,
so we have put in the topics for ADA, topics for Bob, and all the people,
and this is such an elegant and concise representation that you can answer the secret query
by just looking at the table.
You can say, well ADA has an equal amount of topics and friends,
Bob has more topics, so that's a return, and then Cartesian has fewer topics.
So you can just eyeball it and answer the query, which would be a lot more difficult,
and memory intensive if you use the actual table.
So it's kind of obvious at this point in research that the workloads that have a lot of these
many to many join operations, or N to M edge join operations.
They could benefit from factorization, but there are a lot of open questions around there,
and there are also a lot of open questions on how to implement this efficiently,
so both theoretical and implementation side, this is still up for grabs.
And another thing that is quite interesting is that advanced ways of this factorization,
called D representations, could also work for returning combat grabs.
So if you remember for the first category of systems, where we tried to return a graph,
but it was kind of difficult, factorization can also help with that.
So this is, I think, a really promising direction that may be overarching across different graph database systems.
The interesting thing about factorization and virtual optimal joins is that they are
results that follow this really traditional and kind of idea path of first being published in theory papers,
then being picked up by the database researchers, then being designed systems by systems architects,
and that ultimately they will end up in production systems.
But what's interesting is that this is really long journey,
so even though the ideas themselves are quite simple, it takes 10 years to get the first good process access
and maybe another 10 years to get the first good mature industry systems.
Speaking of, there is one that's called Kuzu, this is from the University of Waterloo,
and this implements both virtual optimal joins and factorization.
It supports the Cypher Career Language, and it also has strong focus on path queries.
It also has two academic precursors, graph flow, which was their system written in Java,
and then they had grain DB, which was a dark DB fork.
They abandoned both of those systems, but they reused all the knowledge that they accumulated
and built Kuzu, which is this dark DB style single node in process system for graph processing.
Another system, just to show you the variety, is called Tiger Graph.
This has a completely different QR language called GSQL, and it focuses on traverses.
So this is less on the join heavy, and more on the recursive cheapest path queries and other queries,
where you do some sort of a fixed point computation.
So if I want to put a final label on this, I would say this is the teradata of graph database systems.
So once you have this categorization, it will help you select the system, would you something like MongoDB,
or Postgres, or teradata for your problems?
What about schema and distribution? There is no easy answer to this.
Distribution can happen for all of these systems.
The only rule of thumb that I could say is that if you have really heavy analytical queries,
which are illustrated here by purple, then you need a schema.
There is really not really a huge chance of being very fast if you don't have the schema of your data.
But other than that, there are single node and distributed systems in all categories.
So I promised that I will talk about benchmarks.
I have been a longstanding member of the IDBC, the link data benchmark console,
which is a non-profit with the mission to accelerate progress in graph data management.
IDBC has a membership about 100 individuals, mostly researchers and practitioners,
and also 25 organizations. Who are those?
Well, we have a bunch of different categories here.
We have traditional vendors like Oracle, we have AWS, graph database vendors,
like Neo4j, Tiger Graph, the end group, Alibaba, and the bunch of other companies from hardware,
from cloud and databases and also academic institutes.
And the idea of IDBC is that it will take all of these members,
the database companies, the hardware vendors and the cloud vendors,
and it will force them to collaborate on standards, like benchmarks standards,
and create language standards, and it will force them to compete on performance,
purely because if they don't compete, they are left out from a leaderboard.
So to this hand, IDBC defines a bunch of benchmarks and create languages.
The first benchmark, one of the most popular workloads of ours,
is called the social network benchmark interactive workload.
And it has this sort of short read queries that fall into the classic graph data base,
or post-grast of granted databases category.
So for example here, we do a person and then we do one hope to hope and fetch the messages
that were created before a given day.
And obviously this is a graph database benchmark,
so if you formulate the queries in SQL, you can formulate them,
but sometimes they will be a bit unwieldy.
For example, this is already a rather long query.
But this allows me to demonstrate two new query languages.
One is called SQL property graph queries.
This will be mentioned in the next store by Daniel with more details.
But this is an extension of SQL 1023,
where you can say, from graph table and then you can do things like match a cyclic.
And then you have something very similar to the Cypher language.
You have the visual graphs syntax.
You can say, one comma two instead of spelling out the joins,
and you can return your results as a table.
Another language which was standardized just last year is called GQL.
This basically shares the pattern matching core with Cypher PGQ,
but it's more oriented towards processing just graphs.
The interactive workload has been out for a couple of years now,
and we have received a lot of official results from vendors.
And I think this is really impressive diagram because it shows that we have mostly
like a doubling of performance every year,
and even better if you take the performance and the price of the systems into account.
But what's really interesting in this diagram is that all those systems that competed here
and achieve better results are based in China.
So apparently China has a really strong venture capitalic system,
and they also do a lot of open source, two of these systems are open source.
So I think this is something to think about two weeks after DeepSeek R1 came out.
This is obviously something that hit like the mainstream media,
but in graph databases there's also a huge advantage in Chinese vendors
when it comes to performance.
I cannot really speak about the usability of these systems,
but performance wise they're good.
And one system that's really impressive is the little red dot,
which is not the fastest, but it's the fastest that uses the declarative language.
This is who by a GES, it's the graph engine service,
and it uses the cipher language, and it uses factorization internally
to make the queries go fast.
Another workload that I've worked a few years on is called the Business Intelligence workload.
This is graphful app, complex patterns like finding triangles,
complex pathways like finding cheapest paths,
and doing like a long run of power test,
with individual query run times, and throughput test with overlapping query run times.
We also ordered a bunch of systems for this,
but the vendors were very careful not to overlap in the scale factors.
So I cannot do any systems system comparison here.
We will do more all this this year, and hopefully we can compare their results.
And the final benchmark that I would like to mention is the financial benchmark.
This is a very interesting one because it was driven by the end group,
and create link and another company called Altipo.
They do very low latency queries,
with relaxed consistency requirements.
So think about the nosey,
well, eventual consistency,
and they have very interesting queries like they have path queries,
where you have to have not only regular expressions type path,
but also path where you keep some memory.
You keep some state during the traversal,
and you check that the amount of money that's strictly in across the path
is only decreasing by small amounts.
How do you use these TPC benchmarks?
Well, we have a complicated benchmark kit.
I have spent some time in this talk,
making fun of the vendors who kept relicens in their software.
We also did this because we picked GPL,
and then our members out there, so we also relicens.
And we do detailed specifications, papers,
generators, data sets, and all sorts of frameworks
to make our benchmarks be easy to implement.
The benchmarks are easy to implement,
but they're not easy to get audited.
We have TPC grade benchmark audits,
which means that we have certified auditors.
And if you're a vendor, you have to talk to an auditor.
It's usually something like 30 to 50,000 euros.
It's a multi-week process.
The auditor, we'll talk to the vendor,
they will compile the specifications sheets,
and then they will, of course,
rerun the benchmark and write a full disclosure report out of it.
This is kind of a painful process,
but vendors go through it,
because this is kind of the gold standard
in the graph database space,
and we have been doing audits for five years,
published 50 results,
and never had to retract any of the results.
The most issues I could find was a few typos
in old food disclosure reports.
And as you can see, we have grown quite well
in the last five years,
so we have more and more members,
lots of user community meetings,
benchmarks, results, and so on.
So what are the challenges in the graph database space?
What is a big decline?
I don't think that needs to be denied.
The hype cycle has moved over to AI technologies,
and I think there's a huge amount of confusion.
I'm trying to have the confusion here a bit
by setting these categories,
but when vendors go out saying,
we are a graph database,
you don't need joins,
and we will replace all relational systems.
I don't think that does anything any, any one any good.
I don't think anyone is seriously saying any more
that graph database is very replace relational systems.
There are many niche use cases,
and there are vendors who are basically tied to one or two of their customers.
They over optimized for that,
and that ends up in this very fragmented space
with dozens of clear languages.
You can see the effect of that,
so between 2013 and 2022,
there was a 13-fold increase in the DB engines
ranking for graph databases,
but since the summer of 2022,
it has been a decline,
so we are now back to basically two thirds of the peak,
and the decline doesn't look very good.
If you have heard about graph frag,
the vendors have heard about this,
this is the life that they are trying to cling onto.
This is something that the vendors think is going to help them,
and indeed it produces a lot of attention,
and it's a nice graph use case.
Okay, to sum up,
graph databases have syntax sugar
and optimizations for joins.
If you have ten joins in your query,
and for some reason,
it doesn't work with a relational system,
you should try a graph database,
but then based on the problem you may want,
the MongoDB,
the Postgres,
or the Teradata of your database.
And licensing is difficult,
check the licenses before using the software,
and check the performance results.
Thanks a lot.