Scaling Graph Algorithms to Billions of Edges with Only 10GB RAM: A Love Letter to DataFusion

By Sem Sinchenko | July 5, 2026 | $\approx 7$ min read

TL;DR: I successfully implemented a graph map-reduce framework using Apache DataFusion. By prioritizing bulk scans over random memory access and offloading data to disk, I can process billion-scale graphs on a consumer-grade memory budget.

---

The Core Philosophy

Traditionally, I believed that massive graph analytics required the heavy lifting of Apache Spark and GraphFrames. However, my perspective has shifted entirely. I've discovered that Apache DataFusion is an incredible tool for this task because it handles the "hard parts" of large-scale data processing:

• Spillover management
• Sort-Merge Joins (SMJ)
• Aggregations
• Query Planning & Execution

By leveraging these, my implementation remains lightweight. To ensure strict adherence to memory limits, I validated my results using systemd-run to enforce hard memory caps.

Current Hurdles

It hasn't been entirely seamless. I've encountered:

1. Occasional deadlocks within the FairSpillPool during extreme load.
2. The inability to force SMJ to recognize and use data that is already pre-sorted on disk.

---

Case Study 1: PageRank on graph500-26

PageRank is a staple for everything from SEO to fraud detection. I implemented this using a classical Pregel approach—a bulk-synchronous parallel (BSP) model—expressed through joins and aggregations.

Dataset Specifications

Implementation Details

The process involves offloading edges to disk and iteratively updating the state. To prevent the lineage from growing indefinitely, I offload the state to disk between iterations.

The Logic Flow:

• Performance: 15 full iterations took roughly 30 minutes.
• Accuracy: The results were a $100\%$ match against ground truth (within a tolerance of $\epsilon = 0.0001$).
• Join Strategy: While I used SMJ to prove scalability, a Hash Join (HJ) would also work here because the vertex set is relatively small (32M) and the state is minimal:
  • rank: f64
  • out_degree: i64
  • participation_flag: bool

---

Case Study 2: Weakly Connected Components (WCC)

WCC is essential for entity resolution and data deduplication via transitive IDs. For this, I used the "In-database connected component analysis" method (Bögeholz et al., arXiv 1802.09478).

Dataset Specifications

The Challenge of Scale

The twitter_mpi graph is massive; the edges alone occupy 30 GB in CSV format. Because WCC requires a symmetrized graph (treating directed edges as undirected), I had to perform a union of (src, dst) and (dst, src). At the peak, the system was processing nearly 4 billion edges with only an 8GB pool.

Once the initial iterations completed and the contraction process began, the edge count dropped sharply, and the algorithm finished in 10 minutes.

---

Execution & Logs

I ran the WCC algorithm using the following command to restrict resources:

sem@fedora:~/github/graphframes-rs$ systemd-run --user --scope \
  -p MemoryMax=10G -p MemorySwapMax=0 \
  -p AllowedCPUs=0-1 \
  --setenv=RUST_LOG=graphframes_rs=info,datafusion=warn \
  ./target/release/run-algorithm twitter_mpi-v.parquet twitter_mpi-e.parquet wcc 42 file:///var/home/sem/Downloads/gf_wcc_out 8G 2

Console Output:

Running as unit: run-p316509-i284528.scope ; invocation ID: 742f9296d31d426580b7ec8213422cf1
[ 2026-07-05T05:37:21Z INFO ... ] start WCC with run-id 017c0a23-2b20-4ffa-ac6b-6e2cb8d7203e
[ 2026-07-05T05:52:21Z INFO ... ] after preparation graph has 3228212374 edges
[ 2026-07-05T06:13:21Z INFO ... ] cc forward iteration 1, edges remaining: 840238268
[ 2026-07-05T06:17:39Z INFO ... ] cc forward iteration 2, edges remaining: 77322906
[ 2026-07-05T06:17:57Z INFO ... ] cc forward iteration 3, edges remaining: 5624128
[ 2026-07-05T06:17:59Z INFO ... ] cc forward iteration 4, edges remaining: 1075998
[ 2026-07-05T06:17:59Z INFO ... ] cc forward iteration 5, edges remaining: 230838
[ 2026-07-05T06:17:59Z INFO ... ] cc forward iteration 6, edges remaining: 97940
[ 2026-07-05T06:17:59Z INFO ... ] cc forward iteration 7, edges remaining: 42352

---

Future Roadmap

There is still plenty of room for optimization. I am looking into the following:

• Range Partitioning: Bucket edges by range so the SMJ doesn't have to re-sort the massive edge-side of the join every iteration.
• Operator Fusion: Attempt to fuse the Join and Aggregate stages.
  • Current flow: Edges $\rightarrow$ Join $\rightarrow$ Nodes $\rightarrow$ Group By $\rightarrow$ Agg.
  • Goal: Combine these into a single stage to drastically reduce overhead.

I am still learning the depths of DataFusion, but the potential for high-scale graph analytics on modest hardware is clearly there.