MySQL Recursive CTE vs C# BFS vs NebulaGraph at 500 Million Rows

A team moving a relationship-heavy system from MySQL to graph databases reports that a recursive CTE collapsed at around 500 million rows. The author built a reproducible benchmark comparing the CTE, a C# breadth-first search on the same MySQL tables, and NebulaGraph. The results suggest the CTE's design, not the relational engine, caused most of the delay.

Key points

• The recursive CTE re-expands the same node at every depth and cannot stop when the target is found, so at 500M rows it answered none of ten relationship queries within 15 minutes.
• A bidirectional BFS in C# over the same MySQL tables answered the relationship question in 2.7 ms at 500M rows.
• Filtering hubs with WHERE NOT "hub" IN tags($$) in nGQL returned wrong counts in the author's test, so hub avoidance was done in application code.
• The benchmark code and raw results are published on GitHub and can be rerun on your own machine.
• For queries that touch the whole graph, NebulaGraph was 1.8 to 3.5 times faster than the C# BFS.

A developer who moved a relationship-heavy system from relational tables to graph databases reports that a recursive CTE in MySQL became unusable at about 500 million rows, with one relationship query taking roughly 15 minutes. The author then built a reproducible benchmark that loads the same data into MySQL 8.4 and NebulaGraph 3.8, checks that all methods return identical answers, and only then measures timing.

The central finding is that the CTE keeps re-expanding nodes at every depth and cannot stop early when the target is found. A bidirectional breadth-first search written in C# over the same MySQL tables answered shortest-path questions in milliseconds at every size, often beating NebulaGraph. When the graph contains hub nodes, NebulaGraph is faster for queries that traverse the whole graph, but the hub-avoiding search could not be expressed correctly in a single nGQL statement.

Real-world use

• A fraud detection service that must find the shortest path between two accounts or devices in milliseconds.
• An identity graph where placeholder values such as a default phone number connect to hundreds of thousands of records.
• A team that keeps MySQL as its store and wants to replace a recursive CTE with a BFS written in C#.

Why it matters

Before switching databases for multi-hop relationship queries, check the traversal algorithm, because the CTE was the bottleneck here. The benchmark also shows that hub handling must be designed explicitly.

Related stories

• Collection Return Types in C#: Interfaces, Views, and SnapshotsDLNick Cosentino (Dev Leader)2 d ago
• Idempotent NebulaGraph bulk ingestion from .NET using deterministic VIDsDVDEV Community: #csharp3 d ago
• Events and Delegates in C#: Contracts, Subscriptions and NotificationDLNick Cosentino (Dev Leader)3 d ago