🤖 Below is an AI-generated summary of my FOSDEM 2025 talk (based on the slide deck).
What are graph databases really about?
At their core, graph databases are about joins. Despite marketing claims from some vendors that relational databases “cannot join,” the reality is more nuanced. Relational systems handle joins perfectly well at the execution level. What graph databases actually bring to the table is syntax sugar and specialized optimizations for join-heavy workloads. If you find yourself writing queries with 10 or more joins that perform poorly, a graph database might be worth exploring.
The three categories
The presentation organizes graph databases into three categories based on the type of join problem they address:
Category I – Graph Serving (transactional). These systems solve the n+1 query problem, which arises from repeated joins when fetching interconnected data. When you need a nested object — say, a city with its residents and their messages — relational databases force you into either overfetching (one massive join that produces redundant rows) or underfetching (multiple round-trips). Graph serving systems, typically backed by key-value or document stores, handle this elegantly by returning nested data structures. Systems in this category include OrientDB (and its forks ArcadeDB, YouTrackDB), Microsoft Cosmos DB, Dgraph, and ArangoDB. A tell-tale sign of a graph serving system: it’s backed by a document store, calls itself “real-time,” or markets itself as “multi-model.”
Category II – Classic Graph Databases (transactional). These tackle recursive joins, particularly path queries like shortest path finding. Writing a shortest path query in standard SQL (using recursive CTEs) is verbose and fragile, while Cypher — the query language popularized by Neo4j — expresses the same operation in just a few lines of readable ASCII-art syntax. Neo4j (2007) is the most prominent system here, having spawned the Cypher language that eventually influenced the GQL and SQL/PGQ standards. Other systems include JanusGraph/HugeGraph (Gremlin-based, distributed), Memgraph, NebulaGraph, and FalkorDB (built on GraphBLAS with sparse matrix operations).
Category III – Graph BI (analytical). These address complex analytical workloads involving many-to-many joins, cyclic graph patterns, and long acyclic patterns. This is where the most interesting recent research lives. Key challenges include cheapest (weighted shortest) path queries, triangle/cyclic queries that produce enormous intermediate results, and acyclic queries that suffer from redundancy. Systems here include KùzuDB/LadybugDB, DuckPGQ (a DuckDB extension supporting SQL/PGQ), RelationalAI (running on Snowflake), and TigerGraph.
Key research concepts
Worst-case optimal joins. Traditional binary join plans can produce intermediate results that blow up quadratically on cyclic queries (like finding mutual interests between friends). Worst-case optimal join algorithms process all relations simultaneously, keeping intermediate sizes bounded at O(m^1.5) instead of O(m^2) for triangle-like patterns.
Factorization. A lossless compression technique for join results. When a many-to-many join introduces predictable redundancy — for instance, every combination of a person’s interests crossed with their friends — factorization compresses this into a compact representation. Instead of materializing all cross-product rows, results are stored as sets grouped by their shared key. Open questions remain around factorizing long chains, determining which queries benefit, and returning factorized structures to clients.
The standards landscape
Several query languages compete in this space: Cypher (Neo4j), Gremlin (Apache TinkerPop), SPARQL (RDF/semantic web), GSQL (TigerGraph), and various SQL dialects. Two standardization efforts are converging: GQL as a standalone graph query language and SQL/PGQ as an extension to SQL (part of SQL:2023). Major relational databases are adopting graph extensions — Oracle Database 23ai supports SQL/PGQ, PostgreSQL has it in progress, and DuckDB offers it through the DuckPGQ community extension.
Benchmarks and the LDBC
The Linked Data Benchmark Council (GDC/LDBC), with around 20 member organizations, develops “TPC-grade” benchmarks for graph systems. Their Interactive workload (transactional) has seen audited results showing a 25× speedup over four years at scale factor 100, with a 71× improvement in price-performance. Notably, all leading results come from Chinese vendors (AtlasGraph, CreateLink GalaxyBase, GraphScope, Huawei GES, TuGraph). Their Business Intelligence workload covers analytical queries, and a newer Financial Benchmark (developed by Ant Group and others) focuses on strict latency requirements with relaxed consistency.
Current challenges
The graph database space faces a decline in hype — the DB-Engines ranking for graph databases has dropped by a third in three years, as industry attention shifted toward AI. Persistent confusion around terminology doesn’t help: vague claims about not needing joins, predictions that graph databases will replace RDBMSs (very unlikely), and the ambiguity of what “graph database” even means across such different system categories all contribute to fragmentation. The presentation argues that graph databases will remain a relatively niche technology deployed in use cases that particularly benefit from graph operations — and that’s perfectly fine.
Practical takeaway
Graph databases offer meaningful advantages in concise query syntax for traversals and specialized optimizations for join-heavy workloads. But the landscape is fragmented, licenses vary widely (from open-source MIT/Apache to proprietary), and the right choice depends entirely on your category of workload. Check actual benchmark results and license terms before committing.