Labelled Subgraph Query Benchmark (LSQB)

📄 LSQB: A Large-Scale Subgraph Query Benchmark, GRADES-NDA'21 paper (presentation)

Overview

A benchmark for subgraph matching but with type information (vertex and edge types). The primary goal of this benchmark is to test the query optimizer (join ordering, choosing between binary and n-ary joins) and the execution engine (join performance, support for worst-case optimal joins) of graph databases. Features found in more mature database systems and query languages such as date/string operations, query composition, complex aggregates/filters are out of scope for this benchmark.

The benchmark consists of the following 9 queries:

Inspirations and references:

• VLDB'19 keynote by Tamer Özsu
• CACM'21 technical perspective paper on graphs

Getting started

Install dependencies

1. Install Docker on your machine.

2. (Optional) Change the location of Docker's data directory (instructions).

3. Install the dependencies:

   scripts/install-dependencies.sh
   # optional convenience packages
   scripts/install-convenience-packages.sh

4. (Optional) Add the Umbra binaries as described in the umb/README.md file.

5. Test the system using scripts/benchmark.sh, e.g. run all systems through the smallest example data set. This tests whether all dependencies are installed and it also downloads the required Docker images.

Creating the input data

Data sets should be provided in two formats:

• data/social-network-sf${SF}-projected-fk: projected foreign keys, the preferred format for most graph database management systems.
• data/social-network-sf${SF}-merged-fk: merged foreign keys, the preferred format for most relational database management systems.

An example data set is provided with the substitution SF=example:

• data/social-network-sfexample-projected-fk
• data/social-network-sfexample-merged-fk

Pre-generated data sets are available in the SURF/CWI data repository.

To download the data sets, set the MAX_SF environment variable to the size of the maximum scale factor you want to use (at least 1) and run the download script.

For example:

export MAX_SF=3
scripts/download-projected-fk-data-sets.sh
scripts/download-merged-fk-data-sets.sh

For more information, see the download instructions and links.

Generating the data sets from scratch

See data generation.

Running the benchmark

The following implementations are provided. The 🐳 symbol denotes that the implementation uses Docker.

Stable implementations:

• ddb: DuckDB [SQL] (embedded)
• hyp: HyPer [SQL] 🐳
• kuz: Kùzu [Cypher] (embedded)
• mys: MySQL [SQL] 🐳
• neo: Neo4j Community Edition [Cypher] 🐳
• pos: PostgreSQL [SQL] 🐳
• umb: Umbra [SQL] 🐳

Running the benchmark

The benchmark run consists of two key steps: loading the data and running the queries on the database.

Some systems need to be online before loading, while others need to be offline. To handle these differences in a unified way, we use three scripts for loading:

• pre-load.sh: steps before loading the data (e.g. starting the DB for systems with online loaders)
• load.sh: loads the data
• post-load.sh: steps after loading the data (e.g. starting the DB for systems with offline loaders)

The init-and-load.sh script calls these three scripts (pre-load.sh, load.sh, and post-load.sh). Therefore, to run the benchmark and clean up after execution, use the following three scripts:

• init-and-load.sh: initialize the database and load the data
• run.sh: runs the benchmark
• stop.sh: stops the database

Example usage that loads scale factor 0.3 to Neo4j:

cd neo
export SF=0.3
./init-and-load.sh && ./run.sh && ./stop.sh

Example usage that runs multiple scale factors on DuckDB. Note that the SF environment variable needs to be exported.

cd ddb
export SF
for SF in 0.1 0.3 1; do
   ./init-and-load.sh && ./run.sh && ./stop.sh
done

Validation of results

Use the validate.sh script. For example:

scripts/validate.sh --system DuckDB-1.0.0 --variant "10 threads" --scale_factor example
scripts/validate.sh --system Neo4j-5.20.0 --scale_factor 0.1
scripts/validate.sh --system PostgreSQL --scale_factor example

Philosophy

• This benchmark has been inspired by the LDBC SNB and the JOB benchmarks.
• First and foremost, this benchmark is designed to be simple. In the spirit of this, we do not provide auditing guidelines – it's the user's responsibility to ensure that the benchmark setup is meaningful. We do not provide a common Java/Python driver component as the functionality required by the driver is very simple and can be implemented by users ideally in less than an hour.