[adsharma]

Are you talking about Andy Pavlo bet here?

https://news.ycombinator.com/item?id=29737326

Kuzu folks took some of these discussions and implemented them. SIP, ASP joins, factorized joins and WCOJ.

Internally it's structured very similar to DuckDB, except for the differences noted above.

DuckDB 1.5 implemented sideways information passing (SIP). And LadybugDB is bringing in support for DuckDB node tables.

So the idea that graph databases have shaky internals stems primarily from pre 2021 incumbents.

4 more years to go to 2030!

[jandrewrogers]

I wasn't referring to the Pavlo bet but I would make the same one! Poor algorithm and architecture scalability is a serious bottleneck. I was part of a research program working on the fundamental computer science of high-scale graph databases ~15 years ago. Even back then we could show that the architectures you mention couldn't scale even in theory. Just about everyone has been re-hashing the same basic design for decades.

As I like to point out, for two decades DARPA has offered to pay many millions of dollars to anyone who can demonstrate a graph database that can handle a sparse trillion-edge graph. That data model easily fits on a single machine. No one has been able to claim the money.

Inexplicably, major advances in this area 15-20 years ago under the auspices of government programs never bled into the academic literature even though it materially improved the situation. (This case is the best example I've seen of obviously valuable advanced research that became lost for mundane reasons, which is pretty wild if you think about it.)

[zozbot234]

What do you need one trillion edges for? Wikidata is a huge, general purpose knowledge graph and it gets away with ~1B triples, give or take.

[jandrewrogers]

Almost all analytic graphs of general scope surpass 1T edges, see below. DARPA also has an unfilled objective for 1B edge real-time continuously updated operational graphs. These are smaller and the write throughput requirements are in line with non-graph analytical databases but graph databases struggle to meet that standard.

There are countless smaller graphs for narrow domains that may be <1B edges but many people have the ambition to stitch together these narrow graphs into a larger graph. When stitching graphs together, the number of edges is usually super-linear. A billion edges is kind of considered “Hello World” for system testing.

The Semantic Web companies in the 2000s had graphs that were 100B+ edges. They wanted to go much larger but hit hard scaling walls around that point. That scaling wall killed them.

Classic mapping data models are typically 10-100B edges. These could be much, much larger if they could process all the data available to them.

Of course, intelligence agencies had all kinds of graphs far beyond trillions of edges 20 years ago. People, places, things, events.

Any type of spatiotemporal entity graphs with large geographic scope are quadrillions of edges. It isn’t just a lot of inferred relationships between entities, the relationships evolve over time which also must be captured. These are probably the most commercially valuable type of graph. You could build hundreds of different graphs of this type with 1T+ edges in most regions, never mind doing it at scale. These are so large that we usually don’t store them. Subgraphs are generated on demand, which is computationally expensive.

These spatiotemporal entity graphs also have the largest write loads. Single sources generate tens of PB/day of new edges. There is a ton of industrial data that looks like this; it isn’t just people slinging structured data.

Graphs are everywhere but we furiously avoid them because the scalability of operations over anything but severely constrained graphs is so poor. Selection bias.

NSA in particular heavily funded foundational theoretical and applied computer science research into scaling graph computing for decades. They had all kinds of boring graphs where trillions of edges was their Tuesday. The US military also uses large graph databases in fairly boring applications that probably didn’t require a graph database.

[adsharma]

> many millions of dollars to anyone who can demonstrate a graph database that can handle a sparse trillion-edge graph.

I wonder why no one has claimed it. It's possible to compress large graphs to 1 byte per edge via Graph reordering techniques. So a trillion scale graph becomes 1TB, which can fit into high end machines.

Obviously it won't handle high write rates and mutations well. But with Apache Arrow based compression, it's certainly possible to handle read-only and read-mostly graphs.

Also the single machine constraint feels artificial. For any columnar database written in the last 5 years, implementing object store support is tablestakes.

[jandrewrogers]

Achieving adequate performance at 1T edges in one aspect requires severe tradeoffs in other aspects, making every implementation impractical at that scale. You touched on a couple of the key issues when I was working in this domain.

There is no single machine constraint, just the observation that we routinely run non-graph databases at similar scale on single machines without issue. It doesn't scale on in-memory supercomputers either, so the hardware details are unrelated to the problem:

- Graph database with good query performance typically has terrible write performance. It doesn't matter how fast queries are if it takes too long to get data into the system. At this scale there can be no secondary indexing structures into the graph; you need a graph cutting algorithm efficient for both scalable writes and join recursion. This was solved.

- Graph workloads break cache replacement algorithms for well-understood theory reasons. Avoiding disk just removes one layer of broken caching among many but doesn't address the abstract purpose for which a cache exists. This is why in-memory systems still scale poorly. We've known how to solve this in theory since at least the 1980s. The caveat is it is surprisingly difficult to fully reduce to practice in software, especially at scale, so no one really has. This is a work in progress.

- Most implementations use global synchronization barriers when parallelizing algorithms such as BFS, which greatly increases resource consumption while throttling hardware scalability and performance. My contribution to research was actually in this area: I discovered a way to efficiently use error correction algorithms to elide the barriers. I think there is room to make this even better but I don't think anyone has worked on it since.

The pathological cache replacement behavior is the real killer here. It is what is left even if you don't care about write performance or parallelization.

I haven't worked in this area for many years but I do keep tabs on new graph databases to see if someone is exploiting that prior R&D, even if developed independently.

[mleonhard]

> Inexplicably, major advances in this area 15-20 years ago under the auspices of government programs never bled into the academic literature even though it materially improved the situation.

Would you please share some more info about this? Were the advances implemented in software and never written up and published? What are the names of the government programs?

[rossjudson]

I guess it all depends on the meaning of the word "handle", and what the use cases are.

[darkteflon]

KuzuDB, now in [maintenance mode](https://github.com/kuzudb/kuzu). Quite annoyed about that one, was using it extensively.

[gdotv]

LadybugDB (https://github.com/LadybugDB/ladybug) at this point seems to be the only sustainable fork. When deciding what to do about the Kuzu archival on https://gdotv.com, we've gone with maintaining support for the last available version of Kuzu (it's still heavily used from what I'm seeing) whilst introducing support for LadybugDB. I've looked into a few other forks and at this point in time none seem to be actively maintained for more than a few weeks before getting dropped.

[darkteflon]

Thanks, that’s interesting - I didn’t know that Ladybug was a KuzuDB fork.

[adsharma]

Source: https://www.theregister.com/2023/03/08/great_graph_debate_we...

> There are some additional optimizations that are specific to graphs that a relational DBMS needs to incorporate: [...]

This is essentially what Kuzu implemented and DuckDB tried to implement (DuckPGQ), without touching relational storage.

The jury is out on which one is a better approach.