In their new book, Neo4j In Action, Jonas Partner and Aleksa Vukotic perform a fascinating experiment. In theory, a graph database should be much faster than a relational databases in graph traversal. For example, in a social network, finding all the friends of a user’s friends. Even more so for friends of friends of friends. Aleksa and Jonas built this query in both MySQL and Neo4j with a database of 1,000,000 users and the results are striking. Execution Time is in seconds, for 1,000 users.
Depth Execution Time – MySQL Execution Time –Neo4j
2 0.016 0.010
3 30.267 0.168
4 1,543.505 1.359
5 Not Finished in 1 Hour 2.132
  For the simple friends of friends query, Neo4j is 60% faster than MySQL. For friends of friends of friends, Neo is 180 times faster. And for the depth four query, Neo4j is 1,135 times faster. And MySQL just chokes on the depth 5 query. The results are dramatic. Read about the whole experiment in the first chapter of Neo4j In Action.