A graph with two billion edges sounds like cluster territory. The usual mental model includes a distributed graph engine, several machines, a large memory budget, and enough operational machinery to keep all of it moving.
That model is useful, but it is not the only one.
Sem Sinchenko recently demonstrated two large graph workloads on a single machine with strict memory limits: PageRank over roughly one billion edges with a 5 GB process limit, and weakly connected components over almost two billion edges with a 10 GB limit. The implementation uses Apache DataFusion, an embeddable Rust query engine built on Apache Arrow, rather than a specialized graph database or distributed compute framework.
The important part is not the headline number by itself. The real lesson is architectural: a graph algorithm does not always need the whole graph as a pointer-rich object in memory. If each iteration can be expressed as scans, joins, aggregations, and state updates, a columnar query engine can stream the work and spill intermediate data to disk.
This changes the limiting resource. RAM stops being a hard ceiling and becomes a cache. Storage bandwidth and repeated sorting become the price of admission.
The Workloads
The experiment uses datasets from the LDBC Graphalytics benchmark, which provides graph datasets, algorithm definitions, and reference results.
The first workload is PageRank on graph500-26:
| Property | Value |
|---|---|
| Vertices | 32,804,978 |
| Edges | 1,051,922,853 |
| Process memory limit | 5 GB |
| DataFusion memory pool | 4 GB |
The second workload is weakly connected components, or WCC, on twitter_mpi:
| Property | Value |
|---|---|
| Vertices | 52,579,682 |
| Edges | 1,963,263,821 |
| Process memory limit | 10 GB |
| DataFusion memory pool | 8 GB |
These are different kinds of stress test. PageRank repeatedly propagates values across edges and aggregates contributions at destination vertices. WCC has to discover groups of vertices connected by a path after edge direction is ignored. For the Twitter graph, that means effectively symmetrizing the edge relation, so the engine may process close to four billion directed edge rows during preparation.
The memory limits were not estimates from a dashboard. The process ran under systemd-run with MemoryMax set and swap disabled. That distinction matters. A configurable query-engine pool does not account for every allocation in a process. A cgroup limit tests whether the complete program survives within the stated envelope.
Stop Thinking in Pointers
Many general-purpose graph libraries represent a graph for fast random access. A vertex leads to an adjacency list; an edge leads to neighboring vertices; algorithm state lives beside those structures. This is excellent when the representation fits in RAM. It becomes awkward when every pointer, object header, index, and duplicate direction competes for a constrained memory budget.
The DataFusion approach starts from a different representation:
- a vertex table keyed by vertex ID
- an edge table with source and destination columns
- a compact state table for the current algorithm values
- intermediate tables materialized between iterations when necessary
That is less like walking an in-memory object graph and more like repeatedly transforming relations. A PageRank step can be described at a high level as:
- Join edges to the current source-vertex state.
- Compute each edge’s contribution.
- Group contributions by destination vertex.
- Join the aggregate back to the vertex table.
- Write the next state and repeat.
This is the Pregel bulk-synchronous idea expressed through a query engine. Every round reads a stable state, produces messages, combines them, updates vertex state, and reaches a barrier before the next round. The implementation does not require DataFusion to know what PageRank means. DataFusion only needs to execute the relational operators efficiently.
That separation is powerful. Graph-specific code defines the iteration and message semantics. The engine supplies planning, partitioned execution, Arrow batches, Parquet scans, joins, aggregation, memory accounting, and spill files.
Why Columnar Execution Helps
Graph datasets are sparse, but sparse does not automatically mean small. At billion-edge scale, even two integer columns occupy substantial space before intermediate state is considered.
Columnar execution helps in several ways.
First, the engine reads only the columns an operator needs. PageRank’s edge pass usually needs source and destination identifiers, not a large object containing every edge property.
Second, Arrow arrays place values of one type in contiguous buffers. That layout is friendly to vectorized processing and avoids much of the per-object overhead of a conventional object graph.
Third, DataFusion processes data in record batches. Operators can consume a stream of batches instead of waiting for an entire relation to materialize in memory.
Finally, the query planner can select and compose operators that already understand partitioning, ordering, and memory pressure. A compact graph layer can reuse years of query-engine work rather than building an external sort, hash table, aggregation engine, file reader, and memory manager from scratch.
Columnar layout is not magic compression, and it does not remove the need for indexes or graph-aware formats in every workload. Its advantage here is that the computation is dominated by bulk passes over a few simple columns.
Spilling Turns Memory into a Budget
DataFusion can enforce a memory pool for execution and spill supported operators to disk when they cannot reserve more memory. Its current feature set includes disk spilling for sorts, grouping, hash joins, and sort-merge joins. The memory-limited query guidance also explains an easy-to-miss tradeoff: more execution partitions can make tight-memory workloads worse because the fair pool divides memory among more concurrent reservations.
The experiment therefore used a deliberately small amount of parallelism. The WCC command limited execution to two CPU cores and gave DataFusion an 8 GB pool inside the 10 GB process cap. This leaves headroom for allocations not charged to the pool while avoiding dozens of partitions fighting over tiny shares.
The key join choice is also shaped by memory.
A hash join is usually attractive when one side is small enough to build an in-memory hash table. In PageRank, the vertex-state table can be compact enough for that approach, and Sinchenko reports it as faster. But the experiment also uses sort-merge joins to prove an out-of-core path. A sort-merge join can order both sides, spill sorted runs, and merge them without retaining a full hash table.
The tradeoff is extra I/O. If the edge table is sorted again on every iteration, the same billion rows repeatedly travel through storage and CPU-intensive comparison work. Pre-bucketing edges by vertex range or preserving useful order in the stored data could reduce that cost. DataFusion’s newer ordering optimizations can eliminate known redundant sorts in some plans, but the experiment notes that its current graph path does not yet reuse pre-sorted on-disk edges as effectively as desired.
This is the central bargain:
- in-memory graph engines pay for capacity and gain fast random access
- out-of-core relational execution pays for scans, sorts, and storage traffic to stay within a small RAM envelope
Neither is universally better. They optimize different constraints.
PageRank as Repeated Relational Work
PageRank maintains a score for every vertex. In each iteration, a vertex distributes its score across outgoing edges, destinations sum their incoming contributions, and the score is adjusted with the damping formula.
The state per vertex is small: a rank, an out-degree, and a participation flag in this implementation. The large, stable side is the edge table. That makes the workload a good match for a relational loop:
edges
JOIN current_vertex_state ON edges.source = state.vertex
PROJECT destination, contribution
GROUP BY destination SUM(contribution)
JOIN vertices ON destination = vertices.id
PROJECT next_rank
The edge relation can remain on disk while state is written out between rounds. Materializing the new state breaks an ever-growing lazy-plan lineage and gives the next iteration a concrete input.
Fifteen full iterations took about 30 minutes in the constrained test. That is not an attempt to beat a tuned in-memory system. It is evidence that the calculation completes predictably without a cluster or a machine sized to retain every working structure.
The results were compared with Graphalytics ground truth and matched within a tolerance of 0.0001. That validation is essential. Large-scale systems can produce impressive throughput numbers while quietly dropping records, overflowing identifiers, or stopping before convergence.
Why Connected Components Is Harder
Weakly connected components asks which vertices belong to the same connected region when edge direction is ignored. It is useful in identity resolution: if customer record A shares an identifier with B, and B shares another identifier with C, all three may describe the same entity even when A and C have no direct link.
The Twitter input is directed, so the algorithm needs both orientations of each relevant edge. After symmetrization and deduplication, the preparation stage reported more than 3.2 billion edges. That peak is precisely where an out-of-core execution plan earns its keep.
The implementation follows an in-database connected-components strategy based on graph contraction. Early rounds do the heavy work, but each round reduces the remaining relation dramatically:
| Stage | Edges remaining |
|---|---|
| After preparation | 3,228,212,374 |
| Forward iteration 1 | 840,238,268 |
| Forward iteration 2 | 77,322,906 |
| Forward iteration 3 | 5,624,128 |
| Forward iteration 5 | 230,838 |
| Forward iteration 22 | 0 |
Once the first few passes survive, the workload collapses into something much smaller. The algorithm then back-propagates component labels and writes the result. In the published run, the full WCC job took roughly 41 minutes from start to final output; the contraction phase after preparation became fast because almost all edges had disappeared.
The final component-size counts matched the benchmark result, including a giant component containing 52,515,193 vertices.
This pattern is worth looking for beyond graphs. A workload may have an intimidating peak input size but shrink aggressively after a few external-memory transformations. Designing for the peak with disk-backed operators can be more economical than keeping the entire pipeline in memory.
What the Demonstration Does Not Prove
It would be easy to turn this into the claim that every billion-edge graph fits comfortably on any laptop. That would be wrong.
The experiment covers two algorithms and two datasets. Other graph workloads depend on neighborhood expansion, frequent random access, large per-vertex state, dynamic mutation, or traversal latency. Those may fit a specialized graph engine better.
The implementation is also young. Sinchenko reports FairSpillPool deadlocks under extreme pressure and unresolved work around exploiting data already ordered on disk. The public graphframes-rs repository is an experimental codebase, not a drop-in replacement for Spark GraphFrames.
Storage matters. Spilling a billion-row sort to a fast local NVMe drive is very different from spilling it to a slow disk, a shared network volume, or a device without enough free space. Low RAM can shift the bill to storage capacity, write amplification, and SSD wear.
The benchmark also emphasizes feasibility over a complete cost comparison. To choose a production architecture, measure wall-clock time, peak memory, scratch-space usage, bytes read and written, CPU utilization, recovery behavior, and engineering complexity against the alternatives.
A Practical Design Checklist
If you want to test this pattern on a large iterative dataset, start with the shape of the computation rather than the headline size.
1. Make state explicit
Separate stable facts from changing algorithm state. Keep edges immutable where possible and store only the values needed for the next round.
2. Prefer bulk operators
Look for a formulation based on scans, joins, groupings, filters, and projections. The approach loses its advantage when every step needs unpredictable single-record lookups.
3. Choose identifiers carefully
Identifier width affects every edge row, sort key, join key, and intermediate batch. Use the narrowest safe type, but do not force 32-bit IDs when the domain may exceed them.
4. Preserve useful ordering
Repeated external sorts are expensive. Partition or bucket stable relations by common join keys, record their ordering accurately, and inspect the physical plan to confirm the engine can use it.
5. Set two memory limits
Configure the query engine’s execution pool, then test under a process or container limit with headroom for untracked allocations. Disable swap when you need to prove a real RAM bound rather than hide memory pressure.
6. Reduce parallelism under pressure
More partitions do not always mean more speed. If each partition receives too little memory, it may create additional spill runs and spend more time merging them.
7. Materialize iteration boundaries
Write compact state between rounds when doing so shortens lineage, frees old buffers, or lets the next plan start from a predictable physical layout.
8. Validate against known answers
Use a smaller in-memory implementation, benchmark ground truth, invariants, and component-size or rank checks. Resource efficiency is irrelevant if the result is subtly wrong.
9. Record spill metrics
Use EXPLAIN ANALYZE and DataFusion’s runtime metrics to find the operators producing the most rows, bytes, and compute time. Also monitor scratch-directory growth at the operating-system level.
The Larger Lesson
DataFusion is often described as a SQL or DataFrame engine, but its more interesting role is as a library of data-system building blocks. It gives an application a logical plan, physical optimizer, vectorized executor, file readers, memory pools, and spill-capable operators without forcing the application to become a general-purpose database.
The graph experiment uses that toolkit as an execution substrate. PageRank becomes a loop of joins and aggregates. Connected components becomes a contraction pipeline over tables. The graph API remains small because the engine already knows how to move and reshape large columnar relations.
That is the durable idea: when a dataset exceeds RAM, do not immediately jump from an in-memory library to a distributed cluster. First ask whether the workload can be expressed as ordered bulk transformations on a single machine.
Sometimes the answer will still be a cluster. Sometimes it will be a specialized graph engine. But when the algorithm has compact state, sequential passes, and spill-friendly operators, an ordinary laptop with a good SSD may be enough.
Sources
- Algorithms on billion-scale graph using 10GB RAM: I love DataFusion
- Apache DataFusion documentation
- DataFusion runtime configuration and tuning
- DataFusion feature support
- graphframes-rs source code
- LDBC Graphalytics benchmark specification
- Pregel: A System for Large-Scale Graph Processing
- Public discussion
Top comments (0)