Abstract: Google BigTable's scale-out design for distributed key-value storage inspired a generation of NoSQL databases. Recently the NewSQL paradigm emerged in response to analytic workloads that demand distributed computation local to data storage. Many such analytics take the form of graph algorithms, a trend that motivated the GraphBLAS initiative to standardize a set of matrix math kernels for building graph algorithms. In this article we show how it is possible to implement the GraphBLAS kernels in a BigTable database by presenting the design of Graphulo, a library for executing graph algorithms inside the Apache Accumulo database. We detail the Graphulo implementation of two graph algorithms and conduct experiments comparing their performance to two main-memory matrix math systems. Our results shed insight into the conditions that determine when executing a graph algorithm is faster inside a database versus an external system—in short, that memory requirements and relative I/O are critical factors.
Introduction
For years, the "NoSQL" movement prioritized massive scale and flexible schemas over complex in-database computation. This led to a paradigm where databases like Google's BigTable or Apache Accumulo were treated as "dumb" storage buckets. To perform graph analytics—such as finding clusters or calculating vertex similarity—engineers typically had to export massive datasets to external systems like Spark or MATLAB.
This "export-then-analyze" workflow creates a massive I/O bottleneck. Graphulo addresses this by asking: Can we bring the math to the data? Specifically, Graphulo implements the emerging GraphBLAS standard, which treats graph operations as linear algebra, directly within a BigTable-style architecture to enable "NewSQL" style analytics.
The Graphulo Design: Fusing Kernels into the Iterator Stack
The core technical contribution of Graphulo lies in how it leverages Apache Accumulo’s iterator stack. In a standard NoSQL setup, data is filtered as it is read from disk. Graphulo extends this by "fusing" mathematical kernels into the server-side process.
Key components of this architecture include:
- Matrix-Graph Duality: Graphs are represented as adjacency matrices stored in Accumulo tables, where rows and columns correspond to vertex IDs.
- The TwoTableIterator: This is Graphulo’s primary innovation. It allows the database to stream two tables (or two parts of the same table) through a single server-side process to perform operations like Sparse Generalized Matrix Multiply (SpGEMM) without intermediate disk writes.
- Kernel Fusion: To avoid the "disk trip" penalty, Graphulo performs multiplication and filtering in a single pass within the iterator stack, rather than writing intermediate results back to the database.
Performance Evaluation
The researchers evaluated Graphulo using the Graph500 unpermuted power-law graph generator, varying the "SCALE" parameter from $2^{10}$ to $2^{17}$ nodes. They compared Graphulo against D4M (a MATLAB-based sparse matrix library) and Matrix Toolkits Java (MTJ) (a library for dense matrix math).
Jaccard Coefficients
For vertex similarity (Jaccard coefficients), Graphulo demonstrated significant utility. As shown in the scaling results, Graphulo consistently outperformed the sparse MATLAB (D4M) system and matched the speed of the dense Java (MTJ) system. Crucially, Graphulo could handle datasets that were too large for the main-memory systems to even load, proving its value for "Big Data" scales.
$k$-truss Decomposition
In contrast, the iterative $k$-truss algorithm—used to find highly connected subgraphs—revealed the limitations of in-database processing. While the authors used clever "parity tricks" (integer division and remainders) to optimize triangle discovery, main-memory systems remained an order of magnitude faster. Graphulo suffered a "write overhead" of 280x to 2200x because it was forced to commit intermediate results to disk between iterations, whereas RAM-based systems kept all data in flight.
Discussion and Key Insights
The study reinforces that the optimal system depends on the algorithm's nature:
- Data-Parallel vs. State-Parallel: Algorithms like Jaccard are "data-parallel" and thrive in-database because they require minimal global coordination. "State-parallel" algorithms like $k$-truss struggle because they require multiple iterations and global state management, which triggers expensive database writes.
- Locality is King: The primary advantage of Graphulo is the elimination of the "data tax" paid when moving billions of rows over a network to an external analyzer. When data exceeds RAM, the database's ability to manage disk I/O efficiently becomes the deciding factor.
Conclusion and Future Work
While this evaluation was limited to a single-node setup to establish a baseline for overhead, Graphulo's design is intended to scale to hundreds of nodes. Future work will focus on "cross-system optimization"—building a query planner that automatically decides whether to run a graph algorithm inside the database or "cast" the data to an external memory-resident system based on estimated I/O costs and memory availability.
Summary updated