KÙZU Graph Database Management System

Guodong Jin, Xiyang Feng, Ziyi Chen, Chang Liu, Semih SalihogluCidr 2023

Abstract

Kùzu is a novel embeddable, disk-based graph database management system (GDBMS) designed to bridge the gap between relational and graph database architectures. By introducing the Accumulate-Semijoin-Probe (ASP-Join) operator, Kùzu combines the memory efficiency of factorized query processing with the high-performance sequential disk scans characteristic of relational systems. This architecture allows Kùzu to drastically outperform existing systems on complex, highly-connected workloads such as those found in the LDBC Social Network Benchmark.

Introduction

Graph database workloads are characterized by frequent many-to-many (m-n) joins, cyclic patterns, and recursive path queries. Traditional database engines face a fundamental tradeoff when executing these queries. Relational Database Management Systems (RDBMS) typically use hash joins, which ensure fast sequential disk scans but force the engine to "flatten" intermediate results, leading to massive memory consumption in m-n joins. Conversely, native GDBMSs often use Index Nested Loop Joins (INLJ) to maintain compressed, factorized intermediate states, but this approach suffers from slow, random disk I/O when fetching neighbor properties.

Kùzu addresses this conflict by redesigning the query processor to maintain memory-efficient factorized data structures while guaranteeing fast, sequential disk scans.

The ASP-Join Operator

The core innovation of Kùzu is the ASP-Join (Accumulate-Semijoin-Probe) operator. Unlike a standard two-stage hash join, ASP-Join utilizes a three-stage pipeline to optimize both memory and I/O:

  1. Accumulate: The operator gathers factorized tuples on the probe side into a temporary table and generates a "semijoin filter"—a list of node IDs guaranteed to participate in the join.
  2. Build: This filter is passed "sideways" to the build side. The engine then sequentially scans only the disk blocks containing properties or edges that match the filter to build a hash table.
  3. Probe: Finally, the engine re-scans the accumulated factorized tuples and probes the hash table to produce the output.
The ASP-Join (S-Join) mechanism utilizing sideways information passing and semijoin filters to optimize disk scans.

This "Sideways Information Passing" (SIP) is a critical advantage for graph queries, as it avoids reading massive amounts of irrelevant data from disk when only a small subset of nodes is required.

Factorized Query Processing

Kùzu leverages factorization to avoid the exponential growth of intermediate results. Instead of flattening joins into redundant tables, Kùzu represents intermediate results as Cartesian products of smaller sets. This approach, combined with the ASP-Join, ensures that the system remains robust even as query complexity increases.

Factorized representation of join results, showing how data is stored as Cartesian products to avoid redundancy.

For cyclic queries, such as finding cliques, Kùzu extends this logic into a Multiway WCO ASP-Join. This operator performs Worst-Case Optimal (WCO) multiway joins by intersecting multiple adjacency lists simultaneously using nested hash tables, all while preserving sequential scans.

Performance Evaluation

Kùzu was evaluated against DuckDB, Umbra (a state-of-the-art RDBMS), and a baseline INLJ-based graph configuration using the LDBC Social Network Benchmark (SNB) and large-scale web graphs (web-BerkStan, LiveJournal).

  • Acyclic Queries: Kùzu consistently outperformed DuckDB and Umbra by over 10x at low selectivities due to its superior filtering. At high selectivities, it remained competitive, avoiding the performance degradation seen in traditional INLJ systems.
  • End-to-End Speed: On LDBC SNB Interactive Short queries (e.g., IS02), Kùzu achieved latencies of ~16.7ms, significantly faster than Umbra (~189ms) and DuckDB (~5,264ms).
  • Cyclic Queries: The multiway ASP-Join successfully handled triangle and clique queries that caused the INLJ baseline to time out due to random I/O bottlenecks.

Conclusion and Future Work

Kùzu provides a high-performance, embeddable foundation for graph analytics, particularly for data scientists building Graph Neural Networks (GNNs). Future development focuses on optimizing outer joins, implementing Multi-Version Concurrency Control (MVCC) for multi-writer support, and deepening integration with Python libraries like PyTorch Geometric and NetworkX.

Summary updated

BibTeX
@inproceedings{jin2023kuzu,
  author = {Guodong Jin and Xiyang Feng and Ziyi Chen and Chang Liu and Semih Salihoglu},
  title = {{KÙZU Graph Database Management System}},
  booktitle = {Cidr},
  year = {2023},
}
Figure