I am Gabor Sarnas and I'm here with David Proha.
We work at CWI Amsterdam and we're here to present you the LDBC social network benchmark.
What is the LDBC?
The abbreviation stands for Linked Data Benchmark Council.
It is a non-profit company founded in 2012 and its mission is to accelerate the progress
in the field of graph data management.
And to this end, it designs and governs the use of graph benchmarks and everything we
do is open source under the Apache version 2 license.
From an organizational perspective, LDBC consists of more than 20 members who all have some
vested interest in graph data management.
We have financial service providers like the End Group, database vendors like Oracle,
Neo4j and Tigrograph, cloud vendors like AWS and hardware vendors like Intel.
Also we have individual contributors like David and me who contribute to the benchmarks.
So to put things into context, the last two decades has seen a rise in the use of modern
graph database management systems.
Typically, the data model used in these systems is called a property graph, which is a labelled
graph where both the nodes and the edges can have an arbitrary number of properties.
For example, this is a small social network consisting of five person nodes and a single
city node, which is the city of SPA.
And the properties can be on the nodes.
For example, here the nodes have names and the edges have attributes like the date when
the friendship was established.
We can see that Bob and Carl met in 2015.
And if you want to run a query on this system, we can use a graph query where we look for
matches of a given graph.
So here the query says we want to start from Bob.
We want to use an arbitrary number of edges to reach some person who lives in SPA and
we want to do an aggregation to return the number of those people.
If you want to evaluate this, we then start from the person Bob, push to all the people
transitively, which are known by Bob directly or via multiple edges.
This means all four people here.
We shrink it down to the people who actually live in SPA, then add up the results and get
the result too.
So graph databases use something called a visual graph syntax, also known as the sqr graph
syntax, which is similar to the popular cipher language of Neo4j.
And here this query is actually really similar to the graph pattern that I have shown.
So there are similarities in how the nodes are formulated, how the edges are captured
in this text, and also how the transitive closure of the little asterisk is captured
in the query language.
So this is a very intuitive and concise way of formulating the queries.
If we deconstruct this query, we can see three main components.
The one is relational operators.
Obviously, we still need relational operators.
We want to be able to identify people by filtering.
So we filter for Bob, we filter for SPA, and also we want to sometimes aggregate.
So the count aggregation is part of this query.
The pathfinding is really elegant in this formulation because we have nodes asterisk
which captures that we can use an arbitrary number of edges.
And the pattern matching which connects the person to SPA is also very concise and readable.
So what is interesting from a future work perspective on graph databases?
Obviously, relational operators are quite well known at this point, and there are endless
papers and techniques on how to implement these.
But we believe that pathfinding and pattern matching is really good in graph databases
compared to traditional relational systems because they provide a more concise syntax
and better algorithms and implementations.
Interestingly enough, even in the last 15 years, there have been lots of papers on better
BFS algorithms, better factorization representations for graph patterns, multi-wavers, case optimal
joins, and so on.
So we believe that these should be adopted by more and more systems.
And to this end, we designed benchmarks that try to push the state of the art and the four
systems to adopt better and better techniques.
David will talk about these benchmarks.
Yeah, hi.
So I will give an overview about the social network benchmark.
And so first, we'll go through three steps of this benchmark, so the data sets, two example
queries, and the update operations done in this benchmark.
So here we see a small example of the data sets where on the left side, we see persons
with friendships, forms, and network, and these persons post messages on the social network
and can reply to each other forming a tree-shaped data structure.
And now we will do one query on this very small data set example.
So with query nine, we want to retrieve messages posted by a given person, friend, and friends
of friends before a given date.
And the dates are here shortened for simplicity.
So if we would start with BOP, we will traverse to their friends and friends of friends, retrieve
the messages, and then filter out the ones that are actually before Saturday.
And then we touch upon 10 nodes in this data.
Suppose we would start from another person, so for example Finn, and we traverse again
to their friends and friends of friends.
Here we see that we touch upon five different nodes.
So half of the one of BOP.
And this difference can actually be troublesome since runtimes for the same queries are different
and therefore doesn't help in understanding what's happening.
So for this benchmark, we actually want to select parameters that have similar runtimes
and also to actually stress the technical difficulties in these systems.
So we select the parameters more carefully.
So here we see an example of when we do not select the parameters carefully, just a uniform
random.
And we can see here a trial model, distribution by model, and one with many outliers.
And we don't want that.
So in the data sets, there are also statistics provided in this example for each person,
the number of friends and friends of friends.
Then we want to select persons with similar number to get more predictable runtimes.
And so if we do that, then we can see here an example that we have unimodal distributions
with very tight runtimes.
And that improves also in understanding these, like the behavior of the queries.
So now we're going to the updates.
And for example, if Eve and Gia wants to be friends, we insert a nose edge.
And this is then formed into the network.
Suppose that the next operation is inserting a comment.
So Gia comments replies on a message posted by Eve.
And both messages are posted on the same date.
Then we have another problem.
Because when we are executing these operations concurrently, it can happen that the reply
is earlier than the message in such a network, posting an error.
And to mitigate this, we introduce dependency tracking.
So for each operation, and also includes the edges, but just for simplicity, the notes
are here with the dependent dates.
We include for each operation a creation date and dependent date.
The creation date is when it's scheduled to be executed, and the dependent date is the
one that's, like in this case, for M6, is the creation date of M3.
And here we can see, actually, that each operation is dependent on each other, forming
a whole chain in the social network.
Suppose now that Eve wants to leave the social network and removes her account.
And so we start with deleting the notes of Eve, and this will trigger a cascading effect
by, since we then need to remove the edges connected to Eve, the messages posted, and
also the replies to those messages.
We can actually see, like, this huge cascading effect, and that can actually have a large
impact on the data distribution, and also therefore the executability of these operations.
And furthermore, it also influences for selecting the parameters, which we have shown before.
And we want to include this delete because it prohibits append only data structures in
databases and also stress the garbage collector of these systems.
Now we are going to give another example to also stress the temporal aspect of this benchmark.
So suppose we want to find a path between two persons.
So we have a start person and a destination person, and, for example, Finn and Gia.
Then we can see here that we have a four-hole path between these persons.
But at one point in the benchmark, it can happen that a node's edge is removed, and
then there is no path anymore.
It can also happen that there's another edge inserted between Carl and Gia, and then we
have a path again.
And so for the same parameters, we can actually have three different outcomes.
And to mitigate this, we do temporal parameter selection.
So each parameter is assigned in a time bucket to actually ensure that we have similar results
and therefore also similar run times.
Now going through the benchmark workflow.
So we start by the data gen, and the data gen provides us with a temporal graph spanning
over social media activity for three years, and it is simulated closely to the, similar
to the Facebook social network.
It's a spark-based data generator that can generate data up to 30 terabytes, and it contains
the, you know, skewed data sets, for example, with the nodes and person data in this data.
And so the output is a data set suitable for loading into the system on a test, updates
which are then executed during the benchmark, and statistics where we can select the parameters.
And the selection of the parameters is done in the parameter generator.
This ensures the stable query run times and assigns parameters into a temporal bucket.
So a parameter can, it may include parameters that once are inserted into the data sets
or before they are removed from the network.
So and then we have a benchmark driver who schedules these operations and ensures that
they can be executed with using the dependency tracking.
And this is especially important when executing the operations concurrently.
And lastly, we have the system on the test where we have, for example, graph databases,
triple stores or relational databases.
And now Gabor will go further into the workloads.
Okay, so graph workloads are actually quite diverse in terms of what they are trying to
achieve, and our benchmark reflects that by having multiple workloads.
We have the social network benchmark interactive workload, which is transactional in nature,
so it has loads of concurrent operations.
The queries here are relatively simple, so they always start in one or two person nodes,
the same as David presented before.
And here the systems are striving to achieve a high throughput, so the competition is getting
as many operations per second as possible.
We are happy to report that we have official results from the last three years, where systems
started with slightly above 5,000 operations per second and have sped up exponentially,
now being close to 17,000 operations per second on a 100 gigabyte dataset.
The other workload of the social network benchmark is called business intelligence.
This is an analytical workload where the queries touch on large portions of the data.
For example, this query in this slide shows a case where we start from a given country
and then find all triangles of friendships in that country.
It's easy to see that this is a very heavy hitting operation.
It may touch on billions of edges in the graph, and it also has to do a complex computation
to find those people.
So here system can use either a bulk update or a concurrent update method, and they should
also strive to get both a high throughput and low query run times.
This benchmark is relatively new.
It was released at the end of last year, so we only have a single result, which was done
by a collaboration of Tiger Graph and AMD.
We're happy to report that there are more audits under way, so we are going to release
more results in 2023.
So probably you can see from this presentation that these benchmarks can get fairly complex
and implementing them is not trivial.
So we did our best to provide everything our users need.
For each of the workloads that we have presented, we have a specification, we have detailed
academic papers who motivate the design choices and the architecture of these benchmarks.
We released a data generator as well as pre-generated datasets, and we have benchmark drivers and
at least two reference implementations for each of the workloads.
Moreover, we have guidelines on how to execute these benchmarks correctly, how to validate
the results of a given system, and how to ensure that the system will lose your data
or mingle up the transactions.
So we have asset compliance tests and recovery tests.
This leads us to our auditing process.
Similarly to the TPC, the Transaction Processing Performance Council, we have a rigorous auditing
process where vendors can commission an independent third party who will rerun the benchmark in
an executable and reproducible manner, and they will write up it as a full disclosure
report so that the benchmark is understandable by whoever wants to see that result.
This is important because LDBC is trademarked worldwide, and we only allow official audited
results to use the term LDBC benchmark result.
This is not to say that we don't allow people to use this benchmark.
Researchers, practitioners, and developers are welcome to use the benchmark.
They can run it.
They can report the results if it is accompanied by the appropriate disclaimer that this is
not an official LDBC benchmark result.
I would like to talk a bit about standard GraphQL languages.
This is an important topic because this has been a pain point for GraphSystems for many
years.
There is a bit of a tower of Babel out there with many languages, both of them using some
sort of visual graph syntax, but always with slightly different semantics and a slightly
different syntax, which makes it difficult for users to adopt these techniques and may
put them in a position of being locked in by their vendors.
In the next couple of years, there are going to be new standard queer languages.
These focus on pathfinding and pattern matching.
The first one is called SQL PGQ.
This is an extension to the SQL language and PGQ stands for property graph queries.
This is going to be released next summer, and GQL, the standalone GraphQL language,
is going to come out in 2024.
We are happy to report that even though we have two new languages, the pattern matching
core of them, the visual graph syntax that we all know and love, is going to be the same,
so users can port at least those bits of their queries.
To give you a taste of how this will look like, here is query 9 that David presented
in the social network benchmark interactive workload.
This query can be formulated in SQL.
It's not too difficult, but the new variants, SQL PGQ and GQL, can represent it as terms
of a graph pattern, and this is a much more concise formulation.
The difference is even more pronounced for query 13 with the path queries.
Here we can see that in SQL PGQ, the pattern is really similar to the visual representation.
It just has a source, a target, and an arbitrary amount of nose edges denoted by nose asterisk
in between.
In SQL, this is a lot less readable, hard to maintain, and it's even less sufficient
because it just implements a unidirectional search algorithm instead of doing a bidirectional
search which has a better algorithmic complexity.
The way LDBC is involved in these new query languages is manifold.
First, it had the G-core design language released in 2018 which influenced these benchmarks.
Then LDBC has the formal semantics working group which formalized the pattern matching
core of these new languages, and LDBC is doing further research to advance the state
of the art on graph schemas.
We have an industry-driven and a theory-driven group, and what they do will end up in the
new versions of these languages.
The outlook is the LDBC Graphalytics benchmark.
This is a more wide benchmark because it can target analytical libraries like NetworkX,
distributed systems like Apache Giraffe, or the GraphBlast API.
This is everything that has to do with analyzing large graphs.
Here the graph is an untyped, unattributed graph, so there are no properties or no labels.
We do use the LDBC social network benchmark dataset, but it is stripped down to the person-nose-person
core graph.
Additionally, we have included a number of well-known datasets like Graph500, Twitter,
and so on.
The algorithms that we run are mostly well-known graph algorithms.
There is the BFS, which starts from a given node and assigns the number of steps that
need to be taken to all of the other nodes to reach them.
We have the famous PageRank centrality algorithm, which highlights the most important nodes in
the network, and we have the local clustering coefficient, community detection using label
propagation, weakly connected components, and shortest paths.
This benchmark is a bit simpler than the social network benchmark.
It does not have a rigorous auditing process.
We trust people that they can run this benchmark efficiently and correctly on their own infrastructure,
and they can report results.
If they do so, they will be able to participate in the Graphalytics competition, which has
a leaderboard for the best implementations.
Wrapping up, you should consider joining the IDBC because members can participate in the
benchmark design.
They have a say in where we are going in terms of including new features.
They can commission audits if they are vendors, and members can gain access to these ISO standard
drafts that I mentioned, SQL, PGQ, and GQR.
Otherwise, these are not available to general public.
Being wise, this is free for individuals, and there is a yearly fee for companies.
To sum up, we have presented three benchmarks, the social network benchmark's interactive
workload, its business intelligence workload, and the Graphalytics graph algorithms workload.
We have more benchmarks.
There is semantic publishing benchmark, which is targeting RDF systems set in the media
and publishing industry.
There is the financial benchmark, which is going to be released this year, which targets
distributed systems, and it uses the financial fraud detection domain as its area, and it
imposes strict latency bounds on queries.
This is quite a different workload from the previous ones.
Of course, graphs are ubiquitous, and they have loads of use cases, so there are many
future benchmark ideas, including graph neural network mining and streaming.
Thank you very much, and we're open to any questions.
Yes.
So, in this one overview that was the graph data set, and the updates were kind of separated.
Is there a possibility to create a graph data set where the updates are included in the
data set, so that the nodes and vertices get time stamps when they were deleted or when
they were added?
Yes.
So, is it possible to create something like a temporal graph with the time stamps of when
the specific node is created and deleted, and this is actually very easy, because this
is the first step that the data gen creates.
So, when David said that it creates a social network of three years, that has everything
that was ever created or deleted during those three years, and then we have attributes like
creation date and deletion date, and then we turn it into something that's loadable
to the database, we hide deletion dates, because the database, of course, shouldn't be aware
of this, but this is something that the data gen supports out of the box.
Okay, but then it's also too able to get this data set with the deletion date, because you
already said that it's hideable.
It's hideable, but we have one which is called the row temporal data set, and that is available,
and we even published that, so that's something that, yeah, it has a lot of chance to be influential
in the streaming community, I believe.
All right, more questions?
Yeah, Michael?
So the question is, can we extend to other domains?
And we usually emphasize that social networks is not really the domain that is the actual
primary use case for graphs, we just use this because this is really easy to understand,
we don't have to explain person-nose-person, and you can put in all sorts of interesting
technological challenges to a graph domain like this.
It would make sense, and sometimes we are approached by our members saying, we want
to do a new benchmark in the domain X, and we then send them the process that is required
to get one of these benchmarks completed, and that's usually the end of the conversation,
but we are definitely open to have more interesting benchmarks, and of course, a good data generator
is worth gold to all the researchers and the vendors in this community, so that's usually
the hard point, and I would be definitely interested in having a retail graph generator.
Carlo?
Hi.
The question is specifically, what do you see the impact of this will be on the industry
or it's more uneductive of evidence if it's, if the system would have improved, or if the
system would get more robust as in that you detect stuff that is doing things and stuff
get fixed, or what's the, yeah.
So the question?
Yeah, the question is about the potential impact.
What could all this achieve?
And we believe that it will help accelerate the field in the sense that systems will get
more mature, because if you want to get an audited result, you have to pass all the asset
tests, you have to be able to recover after a crash, and ideally you would have to be
fast, so that is hopefully one of the other things that systems will take away.
They will have better optimizers, improved storage, better query execution engines,
and we have seen this in the aftermath of the TPC benchmarks, so those resulted in quite
a big speedup.
So that's one area, and of course there is pricing, we would like that users can get
more transactions per dollar, and the third that we are personally quite interested in
is the new accelerators that come out.
So there are, especially in the field of machine learning, there are cards that do fast sparse
matrix multiplications, those could be harnessed specifically for the analytical benchmarks
that we have, and that would be interesting to see how big of a hassle it is to implement
and how big of a speedup they give, cool, all right, okay, thank you very much.