Relationships in a Relational Database: MySQL vs NebulaGraph from 1 Million to 500 Million Rows

About three years ago I started to build what was really a graph inside a relational database. My thinking at the time was quite simple: every connection between two nodes is a kind of many-to-many relationship, so if I have a table for the nodes and a table for the relationships between them, it should work. When we got to around 500 million rows, nodes and relationships together, the system completely collapsed. We were running it on the largest virtual machine we could get on AWS, which cost about 15 to 20 thousand dollars per month, and a simple query to find one relationship between two nodes was taking about 15 minutes.

After that we moved to graph databases, first ArangoDB, then Neo4j, and now we are using NebulaGraph (I wrote about the move from ArangoDB to NebulaGraph in an earlier article). The same kind of query now takes a few seconds, and at most 7 to 10 seconds, depending on how well the query is optimised.

A story from production is not something you can check, so for this article I built a benchmark that anyone can run on their own machine: the same graph loaded into MySQL and into NebulaGraph, the same questions asked to both, and every answer compared before any timing is trusted. All of the code and the raw results are on GitHub: MehdiMohseni82/graph-vs-relational-benchmark.

The benchmark confirms part of that story, but it also separates two things that the story mixes together, and I think that difference is the most useful thing in this article.

The model most of us start with

When a SQL developer models a graph, the first design is almost always the same, and it's the design I used three years ago. There is one table for the things, and one table for the relationships, where each row says that one node is connected to another node.

CREATE TABLE nodes (
  id   BIGINT      NOT NULL PRIMARY KEY,
  name VARCHAR(32) NOT NULL
) ENGINE=InnoDB;
 
CREATE TABLE edges (
  src BIGINT NOT NULL,
  dst BIGINT NOT NULL,
  PRIMARY KEY (src, dst)
) ENGINE=InnoDB;
 
ALTER TABLE edges ADD INDEX ix_edges_dst_src (dst, src);

This is not a bad design, and I want to be fair to it. In InnoDB the primary key is the clustered index, so all the relationships of one node are stored next to each other, and the reverse index (dst, src) does the same for the other direction. Finding the direct neighbours of a node is one index lookup, and it is very fast. The problem doesn't start with one hop, it starts when the question needs many hops.

The questions

The benchmark asks questions that are very common in real systems, for example in fraud detection, recommendations, access control or any knowledge graph. A relationship always counts in both directions.

1. The relationship question: are node A and node B related, and if yes, how many hops apart are they, up to 6 hops? This is the "simple relationship" query from my own story.
2. The neighbourhood question: how many different nodes can be reached from this node in 1, 2, 3 or 4 hops?
3. The neighbourhood without hubs: the same question, but the search may never enter a hub, a node with more than 1,000 relationships. I added this one after looking at a real identity graph, where a few placeholder values are connected to almost everything, and every useful search has to walk around them.

In MySQL 8 the natural way to ask a multi-hop question is a recursive CTE. This is the query for the neighbourhood question:

WITH RECURSIVE reach (id, depth) AS (
    SELECT @start, 0
    UNION
    SELECT e.dst, r.depth + 1 FROM reach r JOIN edges e ON e.src = r.id WHERE r.depth < @hops
    UNION
    SELECT e.src, r.depth + 1 FROM reach r JOIN edges e ON e.dst = r.id WHERE r.depth < @hops
)
SELECT COUNT(DISTINCT id) FROM reach WHERE depth > 0;

And this is the query for the relationship question, which is almost the same:

WITH RECURSIVE reach (id, depth) AS (
    SELECT @a, 0
    UNION
    SELECT e.dst, r.depth + 1 FROM reach r JOIN edges e ON e.src = r.id WHERE r.depth < @maxHops
    UNION
    SELECT e.src, r.depth + 1 FROM reach r JOIN edges e ON e.dst = r.id WHERE r.depth < @maxHops
)
SELECT MIN(depth) FROM reach WHERE id = @b;

In NebulaGraph the first two questions are written in nGQL, and they are much shorter, because traversal is the main job of the language:

GO 1 TO 4 STEPS FROM 42 OVER related BIDIRECT YIELD DISTINCT id($$) AS v | YIELD COUNT(*) AS n;
 
FIND SINGLE SHORTEST PATH FROM 42 TO 1337 OVER related BIDIRECT UPTO 6 STEPS YIELD path AS p | YIELD length($-.p) AS len;

Why the recursive CTE gets so expensive

It's important to understand what the CTE actually does, because the reason is not that MySQL is slow. Every recursive step joins the whole result of the previous step with the edges table again, twice, once for each direction. UNION removes duplicate rows, but a row here is the pair (id, depth), not the node alone. That means a node that was reached at depth 2 is reached again at depth 4, because you can walk to a neighbour and come straight back, and every time it is expanded again. The CTE has no memory of "I have already visited this node", it only knows "I have not produced this exact row yet".

The relationship question has a second problem, which is even bigger. A recursive CTE cannot stop when it finds B. It first builds every node within 6 hops of A, at every depth, and only after that the outer SELECT looks for B in the result. So the cost of the question "are these two nodes related?" does not depend on how close they are, it depends on how big the neighbourhood of A is.

The third method: a breadth-first search in C#

I also added a third method, because I think it is the most honest comparison. It is the solution that a good SQL developer would build after the CTE becomes too slow: keep the same MySQL tables, but do the breadth-first search in C#, one level at a time, with a HashSet of visited nodes and a bidirectional search for the shortest path.

public async Task<long?> ShortestPathAsync(long a, long b, int maxHops, TimeSpan timeout)
{
    if (a == b) return 0;
    var deadline = DateTime.UtcNow + timeout;
    var seenFromA = new HashSet<long> { a };
    var seenFromB = new HashSet<long> { b };
    var frontierA = new List<long> { a };
    var frontierB = new List<long> { b };
 
    for (int length = 1; length <= maxHops; length++)
    {
        bool expandA = frontierA.Count <= frontierB.Count;
        var (frontier, seen, other) = expandA
            ? (frontierA, seenFromA, seenFromB)
            : (frontierB, seenFromB, seenFromA);
        if (frontier.Count == 0) return null;
 
        var next = new List<long>();
        foreach (var neighbour in await NeighboursAsync(frontier, deadline, Queries.MySqlNeighboursOf))
        {
            if (other.Contains(neighbour)) return length;
            if (seen.Add(neighbour)) next.Add(neighbour);
        }
        if (expandA) frontierA = next; else frontierB = next;
    }
    return null;
}

NeighboursAsync sends the frontier to MySQL in batches of 2,000 ids and reads the neighbours in both directions with one query per batch:

SELECT dst FROM edges WHERE src IN ({0})
UNION ALL
SELECT src FROM edges WHERE dst IN ({0});

For the third question the BFS uses the same query with one extra condition per direction, NOT EXISTS (SELECT 1 FROM hubs h WHERE h.id = e.dst), so MySQL never returns a hub. The CTE gets the same condition inside its recursion. The exact queries are in the repository.

The setup

Everything runs in Docker on one machine, and the repository has a runbook and a script that runs one size from empty databases to the final table.

• Hardware: Mac Studio, Apple M3 Ultra, 96 GB RAM. Docker had 80 GB of memory and 24 CPUs, and nothing else was running.
• The same memory for both engines: MySQL 8.4 in a 30 GB container with a 24 GB InnoDB buffer pool. NebulaGraph 3.8 with 30 GB in total: the storage service in a 24 GB container with a 16 GB RocksDB block cache, and the graph service in a 6 GB container. One storage node and 36 partitions.
• Loading: MySQL with LOAD DATA INFILE and the reverse index built after the load. NebulaGraph with nebula-importer from exactly the same CSV files, followed by a compaction.
• The data: a deterministic generator in C#. Every node gets on average 9 relationships, and half of the targets come from a skewed distribution, so some nodes become hubs. The sizes are 1M, 10M, 100M and 500M rows, nodes and relationships together, which is the way I counted the rows in my own system.
• The measurement: 10 cases per question, one warm-up run and 3 measured runs, and the tables show the median. Half of the pairs for the relationship question are close to each other, the other half are two random nodes. The timeout is 15 minutes per query.
• Validity: after every size the run checks that no container was killed or restarted, that the kernel killed nothing for lack of memory, that no query returned an engine error, and that all methods returned the same answers. Every size passed.

Results: the relationship question

This is the result from my story. At 500 million rows the recursive CTE didn't answer a single one of the ten pairs within 15 minutes, while the other two methods answered in milliseconds. The pairs were between 2 and 6 hops apart, so this is not a question of a long path, it's the CTE building the whole 6-hop neighbourhood before it looks for B.

But look at the other two columns. The bidirectional search in C#, on the same MySQL tables, was faster than NebulaGraph at every size. So for this question, the problem was not the relational database. It was the recursive CTE.

Results: the neighbourhood question

These are 4 hops. At 1, 2 and 3 hops all three methods answer in at most about 130 ms at every size, and at 1 and 2 hops in a few milliseconds or less.

Two things are worth explaining here. First, NebulaGraph is the fastest at every size, but the BFS in C# is never far behind, between 1.1 and 2.4 times slower, and the CTE is between 2.5 and 9.4 times slower than NebulaGraph.

Second, 500M is faster than 100M for every method, which looks wrong. It isn't: the time of this query depends on how many nodes it reaches, not on the size of the table. With 10 million nodes, the median start node reached 3.9 million nodes in 4 hops, but with 50 million nodes the median start node reached 2.3 million, because the same number of relationships is spread over five times more nodes. Less work, less time, for all three engines in the same way.

Results: a graph with hubs

The graph above is friendly. Real graphs often have hubs, and in an identity graph a single placeholder value, like a default phone number, can be connected to hundreds of thousands of records. So I generated a second graph: 1 million nodes with on average 50 relationships, plus 20 hubs connected to about 630,000 nodes each. 904 nodes have more than 1,000 relationships. It's 63.5 million rows, and the timeout here is 5 minutes.

The first thing this graph shows is why hubs matter: from a median start node, 2 hops reach 999,991 of the 1,000,000 nodes. Every search goes through a hub, and after that it has the whole graph.

Here the difference between the BFS in C# and NebulaGraph becomes real: when a query touches the whole graph, NebulaGraph is 1.8 to 3.5 times faster. The BFS has to pull every level of the search over the network into the application, batch by batch, and NebulaGraph does the same work next to the data.

But nobody wants the whole graph. The useful question on this graph is the third one, the neighbourhood that walks around the hubs:

Avoiding the hubs, the median start node reaches about 12,000 nodes in 2 hops and 730,000 in 3 hops, so this is still a big search, but it is one the user actually asked for.

This question shows the most about NebulaGraph, because I couldn't write it as one nGQL statement that is both correct and usable:

• GO 1 TO 3 STEPS ... WHERE NOT "hub" IN tags($$) runs, but it returned more nodes than the SQL version. In our check on a small graph it found 5,821 nodes at 2 hops where the correct answer was 463, because the filter doesn't stop the walk from going through a hub.
• MATCH with a condition that no node on the path is a hub returns the correct answer, but it enumerates paths, and on a 20,000-node test graph the 4-hop version used up the 1 GB the graph service had in that test.

What an application does in this case is to walk one GO step per level from C# and remove the hubs between the levels. That is the same small graph engine in the application as the BFS on MySQL, just on top of a different database. I measured a version of it, but my implementation filtered the hubs with WHERE NOT "hub" IN tags($$) in every step, which makes NebulaGraph read the tags of every destination node, and a version that filtered in C# was about twice as fast in a small test. Because I don't have a fair measurement of that approach at full size, I leave NebulaGraph out of this table rather than show a number that makes it look worse than it is.

What the numbers say

I think the honest summary has three parts.

The recursive CTE is what breaks. In every table it is the slowest method, from about 1.2 times slower on the smallest searches to several thousand times slower on the relationship question, and at 500M rows it didn't answer a single relationship question within 15 minutes. It can't remember visited nodes, can't search from both sides and can't stop early. The query in my story was this kind of relationship question, and the benchmark suggests that the way such a query is written matters at least as much as where the data lives.

A breadth-first search on MySQL is a real alternative, and for paths it was the fastest. With the same tables and the same indexes, the BFS in C# answered the relationship question in under 3 milliseconds at every size, faster than NebulaGraph's FIND SHORTEST PATH, and on the 4-hop neighbourhood it stayed within 2.4 times of NebulaGraph on the normal graph. On the hub-avoiding question it was more than five times faster than the CTE at 3 hops. But it's important to be clear what it is: you are writing a small graph engine inside your application, with the visited set, the frontier, the batching, the bidirectional search and the timeouts, and every new kind of question means more code.

A graph database pays off when the traversal itself is big. On the hub graph, when a query really had to walk a large part of the graph, NebulaGraph was 1.8 to 3.5 times faster than the BFS, because it does the work next to the data instead of pulling every level into the application. It also gives you a language where the first two questions are one line each. What it didn't give me, in this test, is a single statement for a traversal that has to avoid certain nodes, and that is exactly the kind of question real graphs need.

Limits of this benchmark

• It runs on one machine with local disks and one NebulaGraph storage node. NebulaGraph is designed to spread partitions over many machines, and this test doesn't measure that at all. If your graph doesn't fit on one machine, that is a different question, and a benchmark on one machine can't answer it.
• The data is generated. It has the right shape (skewed degrees, hubs), but it is not production data with production query patterns and other traffic.
• The MySQL schema and queries are the common approach, not the only one. If you can make the relational side faster, a pull request with the numbers is very welcome.

When a relational database is still the right choice

If your queries are one or two hops, for example "the orders of this customer" or "the members of this group", a relational database with the right indexes is very fast, much simpler to operate, and you already have it. In every table above, 1 and 2 hops on the normal graph stayed in the range of a few milliseconds for all three methods.

In my view, the signal to look at a graph database is the shape of the questions, not the number of rows. When you start to write recursive CTEs, first replace them with a search in your application: in this benchmark that alone turned minutes into milliseconds. When the traversals become large, when the business keeps asking new kinds of graph questions, or when the graph grows beyond one machine, that's the point where a graph database earns its place.

Run it yourself

The repository has everything needed to reproduce these numbers: the Docker Compose file for MySQL and NebulaGraph, the C# generator, the C# benchmark with all methods, the runbook with the validity checks, and the raw CSV of every single run.

github.com/MehdiMohseni82/graph-vs-relational-benchmark