ldbc_snb_bi VS benchgraph

Rigorous database benchmarking is indeed very difficult and time-consuming. I spent the last ~7 years working on benchmarks for graph processing systems in the Linked Data Benchmark Council (LDBC) [1], originally established in 2012 as an EU research project.

LDBC creates TPC-style application-level database benchmarks which can be used for system-to-system comparison. We provide detailed specifications, data generators, benchmark frameworks, and multiple reference implementations. The benchmarks are implemented by vendors for their database products, and the implementations submitted to be run by independent third-party auditors to ensure their correctness and reproducibility.

We have found that there is a market for audits for graph processing systems, albeit it is quite small: over the last 4 years, we have published 34 audited results, see e.g. [2] and [3].

A major problem we face is that process of implementing the benchmark for a system and getting an audited result is long (and therefore expensive). Vendors spend months implementing the and tuning the benchmarks. It is also typical for the auditor to spend 50+ hours on the auditing process, which includes a lengthy code review step, setting up the system, running the experiments, testing ACID properties, writing a report, etc. The length of the process is exacerbated by the lack of standard graph query languages. This potentially necessitates the auditor to learn a new query language or programming language.

We have tried to mitigate this problem by improving our documentation, creating more reference implementation, distributing pre-generated data sets. There are new standard graph query languages (SQL/PGQ, GQL) but their adoption is still very limited. Overall, the auditing process is quite long, which is mainly caused by the essential complexity of the problem: implementing an application-level benchmark and getting reliable results is very difficult.

[1] https://ldbcouncil.org/introduction/

[2] https://ldbcouncil.org/benchmarks/snb-interactive

[3] https://ldbcouncil.org/benchmarks/snb-bi/

At first, the plan was to use only the LDBC dataset and write different queries for the dataset, but LDBC has a set of well-designed queries that were specifically prepared to stress the database. Each query targets a special scenario, also called “chock point.” Not to be mistaken, they do not have deep graph traversal doing around 100 hops, but they are definitely more complex than the ones written for the Pokec dataset. There are two sets of queries for the LDBC SNB: interactive and business intelligence. LDBC provides a reference Cypher implementation for both of these queries for Neo4j. We took those queries, tweaked the data types, and made the queries work on Memgraph. Again, to be perfectly clear, this is NOT an official implementation of an LDBC Benchmark; this goes for both interactive and business intelligence queries. The queries were used as the basis for running the benchmark.

I designed and maintain several graph benchmarks in the Linked Data Benchmark Council, including workloads aimed for databases [1]. We make no restrictions on implementations, they can any query language like Cypher, SQL, etc.

In our last benchmark aimed at analytical systems [2], we found that SQL queries using WITH RECURSIVE can work for expressing reachability and even weighted shortest path queries. However, formulating an efficient algorithm yields very complex SQL queries [3] and their execution requires a system with a sophisticated optimizer such as Umbra developed at TU Munich [4]. Industry SQL systems are not yet at this level but they may attain that sometime in the future.

Another direction to include graph queries in SQL is the upcoming SQL/PGQ (Property Graph Queries) extension. I'm involved in a project at CWI Amsterdam to incorporate this language into DuckDB [5].

[1] https://ldbcouncil.org/benchmarks/snb/

[2] https://www.vldb.org/pvldb/vol16/p877-szarnyas.pdf

[3] https://github.com/ldbc/ldbc_snb_bi/blob/main/umbra/queries/...

[4] https://umbra-db.com/

[5] https://www.cidrdb.org/cidr2023/slides/p66-wolde-slides.pdf

During the run of a typical benchmark, you can run specific queries for a fixed period of time or take a chunk of queries, execute them, and measure elapsed time. Either way, you need a decent amount of queries (same query with different arguments), and for that, you need a bigger dataset. On top of that, testing performance on the more extensive scaled datasets is necessary. To put things into perspective for query requirements, on some of the queries that are being run, the database executes up to 300k queries or less, depending on the query complexity. For a detailed look into statistics, take a look at the benchmark.json file that holds all the results from the benchmarks. There you can see how many specific queries were executed per particular test.