Database Showdown: Which Storage Engine Best Predicts Your Next Social Connection?

TL;DR

Choosing the right database for a social network isn't just about how you store the data—it's about how you query it. This study pits MySQL, Redis, and Neo4J against each other in the task of Link Prediction. The verdict? MySQL wins on simple neighborhood "joins," but Redis's raw in-memory speed crushes complex path-finding and PageRank tasks.

Context: The Link Prediction Challenge

Link prediction—predicting which two nodes in a network are likely to form an edge—is the "Engine Room" of friend recommendations. While researchers have developed dozens of metrics (like Common Neighbors or Rooted PageRank), the database community has largely ignored the performance implications of where these algorithms run.

The authors argue that the computational complexity of these metrics varies so wildly that a "one-size-fits-all" database approach is bound to fail.

Methodology: The Seven Metrics

The study implements seven metrics that test different database access patterns:

1. Local Neighborhood: Common Neighbors, Jaccard Coefficient, Adamic-Adar. (Tests Join efficiency).
2. Popularity-Based: Preferential Attachment. (Tests Indexing efficiency).
3. Path/Global-Based: Graph Distance, Katz Measure, Rooted PageRank. (Tests Recursion and Iteration).

Implementation Approaches

• MySQL: Relational tables with heavy use of stored procedures and helper tables for neighbor counts.
• Redis: Leveraging in-memory key-value pairs where values are adjacency sets, optimized with Lua scripting.
• Neo4J: Using the declarative Cypher language for pattern matching.

Figure 1: Performance comparison across different metrics (a) Common Neighbors, (b) Jaccard, (c) Adamic-Adar, (d) Graph Distance.

Key Insights from the Experiments

1. The Relational Powerhouse

Surprisingly, for neighborhood-based metrics like Common Neighbors, MySQL was the champion. Relational databases have spent decades optimizing "Joins," which is exactly what looking for mutual friends requires.

• Insight: If your queries are mostly 1-step or 2-step lookups, don't ditch SQL yet.

2. The In-Memory Speed of Redis

As soon as the queries moved beyond the immediate neighborhood to Graph Distance or Katz, MySQL's performance plummeted. Redis took the lead here. Because Redis is an in-memory key-value store, it lacks the overhead of a query optimizer and transaction management for complex traversals.

• Insight: For recursive or iterative algorithms (like PageRank), memory-resident data structures are unbeatable.

3. The Neo4J Paradox

Neo4J, despite being a "Graph Database," often had the worst performance. The authors noted two primary reasons:

• Language Maturity: The Cypher language at the time lacked basic mathematical functions (like log or exp), making metrics like Adamic-Adar impossible to implement natively.
• Overhead: The abstraction layer of a graph database can introduce significant latency compared to raw in-memory lookups.

Figure 2: Runtime for finding the top-100 most popular nodes. MySQL's B-Tree indexing on neighbor counts provides a significant advantage.

SOTA Comparison: Quantitative Summary

Critical Analysis & Conclusion

The study highlights a critical gap in the "Graph Database" hype of the early 2010s: Matching a data model (Graph) to a storage model (Graph) does not automatically guarantee speed.

Limitations

• Scale: The study was limited to a single machine (datasets up to 350k nodes). It does not address how these results change in a distributed environment (e.g., Sharding in MySQL vs. Cluster mode in Redis).
• Language Support: The poor performance of Neo4J was partly due to the immaturity of the Cypher language at the time of publication.

The Future: Hybrid is Key

The ultimate takeaway is the proposal for a Hybrid System. By presenting a Graph API to the developer while dynamically shifting data between a Relational engine (for neighborhood counting) and a Key-Value engine (for random walks), we can achieve the best of both worlds.

Takeaway for Architects

If you are building a recommendation engine today, don't pick a database based on the "shape" of your data. Pick it based on the depth of your traversals. Shorter paths? Stick to SQL. Deep recursive paths? Look at in-memory key-value stores or modern, highly-optimized graph engines.