6 ms·

Algorithms on billion-scale graph using 10GB RAM: I love DataFusion

137 points by speckx 3mo ago

slopblast 3mo ago
Really cool visualization, amazing how it resembles a neural network.
- convolvatron 3mo ago
  I'm pretty sure that's some stock output from CAIDA, looks like a traceroute graph from the inset
chrisweekly 3mo ago
> "I can compute PageRank on a directed graph with one billion edges (graph500-26 from the Graphalytics dataset) using 5 GB of memory. Alternatively, I can identify all the weakly connected components in a graph with two billion edges (twitter_mpi from the same dataset collection) using 10 GB of memory. Neither NetworkX nor Igraph can do this; most existing graph algorithms require the graph to fit into memory. Previously, I thought you needed Apache Spark and GraphFrames for billion-scale graph analytics. Now, however, I think all you need is a laptop. I have completely changed my old opinion about using Apache DataFusion for graph analytics." Impressive!
- anon7725 3mo ago
  > most existing graph algorithms require the graph to fit into memory. You can get pretty far with sparse graphs, which are just arrays, in combination with memory mapping.
  - ssinchenko 3mo ago
    Agreed, but I didn't see anything like this in popular projects such as Networkit or IGraph. If you have an example of an implementation, I would appreciate it!
- danbruc 3mo ago
  33M vertices and 1B edges easily fits into memory, if you use 32 bit integers, it will require about 4 GiB of memory. Out of curiosity I just implemented generating a random graph of that size and calculating one page rank iteration on it in the most naive way (20 lines of C#) and it consumed 8.4 GiB of memory and got one iteration done in 4:20 minutes single threaded.
  - eeks 3mo ago
    It reminds me of that Frank MacSherry paper[1]... [1] "Scalability! But at what COST?"
esafak 3mo ago
Does it support out-of-core or multi-processor processing?
- ssinchenko 3mo ago
  Yes, it is both out-of-core and multi-processor. I created this toy project to process graphs that cannot fit into memory (in CSR format) using all available cores. The multi-processing relies on DataFusion's Tokyo workers. The out-of-core aspect is achieved through a combination of DataFusion FairSpillPool, Sort-Merge-Join, and manually offloading everything to temporary Parquet files on disk.
Natalia724 3mo ago
[dead]
theLiminator 3mo ago
DataFusion is really cool, it's kind of like the LLVM of the OLAP world.
ratmice 3mo ago
It would be nice if OP noted what caused the change in their opinion? did datafusion gain some feature that they noted was missing in the previous article, or did something in their understanding click so they could overcome the previous issues?
- lmeyerov 3mo ago
  We shared with the author how databricks multi-node and single-node graphframes were wildly inefficient for this kind of thing: we were measuring doing billion-edge graph traversals & scans in single node in-memory in seconds with regular dataframe (cudf) libraries, so the core of pagerank, which is magnitudes more efficient than their original spark approach So then the question became pandas/polars/datafusion/duckdb/etc, must of which are rust/native. I'm curious myself why datafusion vs others, it's an interesting project :)
- adsharma 3mo ago
  There is a bit of healthy competition going on between graphframes and icebug. See: https://github.com/Ladybug-Memory/icebug-graphframes-comparison/ https://github.com/Ladybug-Memory/icebug-graphframes-compari... I thought of datafusion work and the rust implementation as a way to address the delta seen vs the Spark/JVM GraphFrames implementation (author is a major contributor). Looking forward to more such innovations, which will benefit the ecosystem as a whole. Why would anyone want to use a pure python graph algorithm package unless they're dealing with toy graphs?
- ssinchenko 3mo ago
  The previous issues were in my mind, not in DataFusion. I tried using DataFusion as an in-memory tool, which was a mistake. If the graph fits in memory, Networkit, IGraph, etc. will almost always be faster. These tools cannot process anything bigger than the available memory. So, I changed my approach. I wrote my own naive "disk checkpointer," offloading everything to disk and avoiding materialization. Although I was afraid that writing to and reading from the disk would be slow, it is surprisingly fast with DataFusion. The results are impressive: fast and out-of-core. Sorry, this post is short and not very detailed. I did not expect it to be at the top of HN and receive so much attention.
ozgrakkurt 3mo ago
3.4 gb dataset on 10gb ram
yadgire7 3mo ago
Hello, I am new to hacker news and finding it really resourceful. I found this article interesting (having learnt KG and Map Reduce (spark) as part of my masters' course), appreciate the effort to post this. I am here to seek guidance from the community. I want to refresh my memory on knowledge graphs and algorithms for Big Data Mining and Processing. I believe KG can solve problems on Agent attacks (LLM agency) in real-time - so want to build knowledge around the topic. Interested to join any interest/ discussion groups if any. Thanks!
lmeyerov 3mo ago
Related, we recently release the polars version of GFQL, the only oss cypher property graph query engine for CPU+GPU, and even better, no database nor outside process needed. We started doing LDBC benchmarks vs neo4j, memgraph, kuzu, etc, and are already starting to outperform them both on latency for small OLTP graph searches and $, speed for big graph OLAP ones, especially in GPU mode. The cool in the original post was directly inspired by our work here, with our advocacy to the author of keeping their previous Spark work for initial data lake data extraction, and the actual graph work to be redone in our columnar in-memory optimized style for magnitudes of speedup , cost savings Pip install, benchmarks : https://pygraphistry.readthedocs.io/en/latest/gfql/benchmark_filter_pagerank.html https://pygraphistry.readthedocs.io/en/latest/gfql/benchmark...
cpdomina 3mo ago
cool! you might be interested in graphchi (2012), also designed to do large scale graph operations on a single machine https://github.com/GraphChi/graphchi-cpp#performance https://github.com/GraphChi/graphchi-cpp#performance
- adsharma 3mo ago
  It looks similar to networkit in that it represents graphs using row oriented memory layout. I forked networkit for exactly this reason. Columnar memory is much more efficient.
- BigTTYGothGF 3mo ago
  I got to use graphchi/graphlab back in the day (I think I still have the tshirt from the 2013 conference), wish it had caught on more.
- ssinchenko 3mo ago
  Yes, my toy tool is similar by the concept to graphchi. But I did not write the vertex-centric processing from scratch and I'm relying on DataFusion built-ins (select, join, group by, aggregate)
dekhn 3mo ago
It's hard to take the article seriously when it has quotes like this: "The hardest part. 2B edges twitter graph is already huge (its edges are 30 GB in CSV !!!)." Who cares how big the graph is in CSV? That's not the representation you operate over in big data. All of this would have easily fit in memory on any reasonable modern system.
- adsharma 3mo ago
  Here is a proposal built on parquet/arrow. What other alternatives exist that can be queried by a database without ingest? https://github.com/Ladybug-Memory/icebug-format https://github.com/Ladybug-Memory/icebug-format
- ssinchenko 3mo ago
  > All of this would have easily fit in memory on any reasonable modern system. Understand me correctly. This is my research project and I only have a laptop, not a server with 256 GB of RAM. I tested my project on a 2B graph with a hard cap of 8–10 GB of RAM. Of course it fits in memory on any modern system with 64–128 GB of RAM. The whole idea was to conduct a stress test and check how my tool works in out-of-core mode, not to prove to anyone that 2 billion edges (30 GB CSV) constitutes "big data".
adsharma 3mo ago
The idea of graph algorithms on Apache arrow at scale originated here. 100+ graph algorithms running on columnar memory. https://github.com/Ladybug-Memory/icebug https://github.com/Ladybug-Memory/icebug Out of core with datafusion is the main innovation here in graphframes-rs. But it has only 2 algorithms so far. Icebug and LadybugDB can be tightly integrated to efficiently move tables encoded as compressed sparse row (CSR) into arrow memory. Jupyter notebooks available.
- adsharma 3mo ago
  https://github.com/LadybugDB/ladybug-icebug-notebooks/blob/main/ladybug_icebug_comm_detection.ipynb https://github.com/LadybugDB/ladybug-icebug-notebooks/blob/m... Trade-off: datafusion allows you to do fine grained storage integration (spill to disk as a part of the algorithm). The icebug/ladybug way is coarse grained. But it allows you to run cypher instead of writing datafusion operators.
- lmeyerov 3mo ago
  Not really ;-) ~10 years ago, we helped create apache arrow, helped create GPU data frames, and been running for the last decade the open source pygraphistry and now gfql cpu+gpu property graph engine for this. Likewise, Nvidia has been doing great with cuGraph (OSS) for GPU algs around this. It is great you are finding success with this direction, but "shoulders of giants" merit credit - 100+ people.
  - adsharma 3mo ago
    Ofc. I'm not claiming credit for Apache Arrow. Lots of people contributed to it. I didn't write the graph algorithms in networkit. Somebody else did. But if you're looking for 100-200 graph algorithms running efficiently on columnar memory, I haven't found a working implementation that's permissively open source. Happy to work with cugraph or anyone else who builds on top of Parquet/Arrow ecosystem.
    - lmeyerov 3mo ago
      cudf/cugraph is open source and helped fund the arrow ecosystem , I think it's good to give teams credit when they do work they didn't have to do and not misrepresent them. And yes, it works great, graph500 leaderboard level.
RobinL 3mo ago
Love this Sem. Will provide a great alternative to the SQL based connected components algorithm we ship in Splink. Looking forward to testing how much faster it is. Thanks for your work on it!
- ssinchenko 3mo ago
  Thank you!
nylonstrung 3mo ago
Datafusion is undoubtedly one of the best open source projects of all time, it's so incredibly powerful and well designed. The extensibility is insane, you can create your own query language that compiles to logical plans.
- ssinchenko 3mo ago
  I agree 100%! DataFusion is beautiful and easy to extend in any direction. For the second version of my "out-of-core" graph algorithms project, for example, I implemented my own "co-partitioning" to speed up joins and achieved a performance improvement of two times! It was also easy to modify the physical plan and declare partitioning.
  - stuhood 3mo ago
    Co-partitioning of range-partitioned data is now supported on `main` too: see https://github.com/apache/datafusion/issues/23183 https://github.com/apache/datafusion/issues/23183 and the epic https://github.com/apache/datafusion/issues/22395 https://github.com/apache/datafusion/issues/22395

137 points by speckx 3mo ago

slopblast 3mo ago

Really cool visualization, amazing how it resembles a neural network.

convolvatron 3mo ago
I'm pretty sure that's some stock output from CAIDA, looks like a traceroute graph from the inset

chrisweekly 3mo ago

> "I can compute PageRank on a directed graph with one billion edges (graph500-26 from the Graphalytics dataset) using 5 GB of memory. Alternatively, I can identify all the weakly connected components in a graph with two billion edges (twitter_mpi from the same dataset collection) using 10 GB of memory. Neither NetworkX nor Igraph can do this; most existing graph algorithms require the graph to fit into memory. Previously, I thought you needed Apache Spark and GraphFrames for billion-scale graph analytics. Now, however, I think all you need is a laptop. I have completely changed my old opinion about using Apache DataFusion for graph analytics." Impressive!

anon7725 3mo ago
> most existing graph algorithms require the graph to fit into memory. You can get pretty far with sparse graphs, which are just arrays, in combination with memory mapping.
- ssinchenko 3mo ago
  Agreed, but I didn't see anything like this in popular projects such as Networkit or IGraph. If you have an example of an implementation, I would appreciate it!
danbruc 3mo ago
33M vertices and 1B edges easily fits into memory, if you use 32 bit integers, it will require about 4 GiB of memory. Out of curiosity I just implemented generating a random graph of that size and calculating one page rank iteration on it in the most naive way (20 lines of C#) and it consumed 8.4 GiB of memory and got one iteration done in 4:20 minutes single threaded.
- eeks 3mo ago
  It reminds me of that Frank MacSherry paper[1]... [1] "Scalability! But at what COST?"

esafak 3mo ago

Does it support out-of-core or multi-processor processing?

ssinchenko 3mo ago
Yes, it is both out-of-core and multi-processor. I created this toy project to process graphs that cannot fit into memory (in CSR format) using all available cores. The multi-processing relies on DataFusion's Tokyo workers. The out-of-core aspect is achieved through a combination of DataFusion FairSpillPool, Sort-Merge-Join, and manually offloading everything to temporary Parquet files on disk.

Natalia724 3mo ago

[dead]

theLiminator 3mo ago

DataFusion is really cool, it's kind of like the LLVM of the OLAP world.

ratmice 3mo ago

It would be nice if OP noted what caused the change in their opinion? did datafusion gain some feature that they noted was missing in the previous article, or did something in their understanding click so they could overcome the previous issues?

lmeyerov 3mo ago
We shared with the author how databricks multi-node and single-node graphframes were wildly inefficient for this kind of thing: we were measuring doing billion-edge graph traversals & scans in single node in-memory in seconds with regular dataframe (cudf) libraries, so the core of pagerank, which is magnitudes more efficient than their original spark approach So then the question became pandas/polars/datafusion/duckdb/etc, must of which are rust/native. I'm curious myself why datafusion vs others, it's an interesting project :)
adsharma 3mo ago
There is a bit of healthy competition going on between graphframes and icebug. See: https://github.com/Ladybug-Memory/icebug-graphframes-comparison/ https://github.com/Ladybug-Memory/icebug-graphframes-compari... I thought of datafusion work and the rust implementation as a way to address the delta seen vs the Spark/JVM GraphFrames implementation (author is a major contributor). Looking forward to more such innovations, which will benefit the ecosystem as a whole. Why would anyone want to use a pure python graph algorithm package unless they're dealing with toy graphs?
ssinchenko 3mo ago
The previous issues were in my mind, not in DataFusion. I tried using DataFusion as an in-memory tool, which was a mistake. If the graph fits in memory, Networkit, IGraph, etc. will almost always be faster. These tools cannot process anything bigger than the available memory. So, I changed my approach. I wrote my own naive "disk checkpointer," offloading everything to disk and avoiding materialization. Although I was afraid that writing to and reading from the disk would be slow, it is surprisingly fast with DataFusion. The results are impressive: fast and out-of-core. Sorry, this post is short and not very detailed. I did not expect it to be at the top of HN and receive so much attention.

ozgrakkurt 3mo ago

3.4 gb dataset on 10gb ram

yadgire7 3mo ago

Hello, I am new to hacker news and finding it really resourceful. I found this article interesting (having learnt KG and Map Reduce (spark) as part of my masters' course), appreciate the effort to post this. I am here to seek guidance from the community. I want to refresh my memory on knowledge graphs and algorithms for Big Data Mining and Processing. I believe KG can solve problems on Agent attacks (LLM agency) in real-time - so want to build knowledge around the topic. Interested to join any interest/ discussion groups if any. Thanks!

lmeyerov 3mo ago

Related, we recently release the polars version of GFQL, the only oss cypher property graph query engine for CPU+GPU, and even better, no database nor outside process needed. We started doing LDBC benchmarks vs neo4j, memgraph, kuzu, etc, and are already starting to outperform them both on latency for small OLTP graph searches and $, speed for big graph OLAP ones, especially in GPU mode. The cool in the original post was directly inspired by our work here, with our advocacy to the author of keeping their previous Spark work for initial data lake data extraction, and the actual graph work to be redone in our columnar in-memory optimized style for magnitudes of speedup , cost savings Pip install, benchmarks : https://pygraphistry.readthedocs.io/en/latest/gfql/benchmark_filter_pagerank.html https://pygraphistry.readthedocs.io/en/latest/gfql/benchmark...

cpdomina 3mo ago

cool! you might be interested in graphchi (2012), also designed to do large scale graph operations on a single machine https://github.com/GraphChi/graphchi-cpp#performance https://github.com/GraphChi/graphchi-cpp#performance

adsharma 3mo ago
It looks similar to networkit in that it represents graphs using row oriented memory layout. I forked networkit for exactly this reason. Columnar memory is much more efficient.
BigTTYGothGF 3mo ago
I got to use graphchi/graphlab back in the day (I think I still have the tshirt from the 2013 conference), wish it had caught on more.
ssinchenko 3mo ago
Yes, my toy tool is similar by the concept to graphchi. But I did not write the vertex-centric processing from scratch and I'm relying on DataFusion built-ins (select, join, group by, aggregate)

dekhn 3mo ago

It's hard to take the article seriously when it has quotes like this: "The hardest part. 2B edges twitter graph is already huge (its edges are 30 GB in CSV !!!)." Who cares how big the graph is in CSV? That's not the representation you operate over in big data. All of this would have easily fit in memory on any reasonable modern system.

adsharma 3mo ago
Here is a proposal built on parquet/arrow. What other alternatives exist that can be queried by a database without ingest? https://github.com/Ladybug-Memory/icebug-format https://github.com/Ladybug-Memory/icebug-format
ssinchenko 3mo ago
> All of this would have easily fit in memory on any reasonable modern system. Understand me correctly. This is my research project and I only have a laptop, not a server with 256 GB of RAM. I tested my project on a 2B graph with a hard cap of 8–10 GB of RAM. Of course it fits in memory on any modern system with 64–128 GB of RAM. The whole idea was to conduct a stress test and check how my tool works in out-of-core mode, not to prove to anyone that 2 billion edges (30 GB CSV) constitutes "big data".

adsharma 3mo ago

The idea of graph algorithms on Apache arrow at scale originated here. 100+ graph algorithms running on columnar memory. https://github.com/Ladybug-Memory/icebug https://github.com/Ladybug-Memory/icebug Out of core with datafusion is the main innovation here in graphframes-rs. But it has only 2 algorithms so far. Icebug and LadybugDB can be tightly integrated to efficiently move tables encoded as compressed sparse row (CSR) into arrow memory. Jupyter notebooks available.

adsharma 3mo ago
https://github.com/LadybugDB/ladybug-icebug-notebooks/blob/main/ladybug_icebug_comm_detection.ipynb https://github.com/LadybugDB/ladybug-icebug-notebooks/blob/m... Trade-off: datafusion allows you to do fine grained storage integration (spill to disk as a part of the algorithm). The icebug/ladybug way is coarse grained. But it allows you to run cypher instead of writing datafusion operators.
lmeyerov 3mo ago
Not really ;-) ~10 years ago, we helped create apache arrow, helped create GPU data frames, and been running for the last decade the open source pygraphistry and now gfql cpu+gpu property graph engine for this. Likewise, Nvidia has been doing great with cuGraph (OSS) for GPU algs around this. It is great you are finding success with this direction, but "shoulders of giants" merit credit - 100+ people.
- adsharma 3mo ago
  Ofc. I'm not claiming credit for Apache Arrow. Lots of people contributed to it. I didn't write the graph algorithms in networkit. Somebody else did. But if you're looking for 100-200 graph algorithms running efficiently on columnar memory, I haven't found a working implementation that's permissively open source. Happy to work with cugraph or anyone else who builds on top of Parquet/Arrow ecosystem.
  - lmeyerov 3mo ago
    cudf/cugraph is open source and helped fund the arrow ecosystem , I think it's good to give teams credit when they do work they didn't have to do and not misrepresent them. And yes, it works great, graph500 leaderboard level.

RobinL 3mo ago

Love this Sem. Will provide a great alternative to the SQL based connected components algorithm we ship in Splink. Looking forward to testing how much faster it is. Thanks for your work on it!

ssinchenko 3mo ago
Thank you!

nylonstrung 3mo ago

Datafusion is undoubtedly one of the best open source projects of all time, it's so incredibly powerful and well designed. The extensibility is insane, you can create your own query language that compiles to logical plans.

ssinchenko 3mo ago
I agree 100%! DataFusion is beautiful and easy to extend in any direction. For the second version of my "out-of-core" graph algorithms project, for example, I implemented my own "co-partitioning" to speed up joins and achieved a performance improvement of two times! It was also easy to modify the physical plan and declare partitioning.
- stuhood 3mo ago
  Co-partitioning of range-partitioned data is now supported on `main` too: see https://github.com/apache/datafusion/issues/23183 https://github.com/apache/datafusion/issues/23183 and the epic https://github.com/apache/datafusion/issues/22395 https://github.com/apache/datafusion/issues/22395