0

I often read that graph dbms are well suited for social networks. So for example, followers on instagram or linkedin. I read that the SQL dbms performance can degrade if the query involves multiple joins, especially if the tables being joined are large.

What is the exact reason that SQL databases might perform poorly under joins? Assume that the followers table is indexed on both foreign keys.

The query:

SELECT DISTINCT f2.followed_id
FROM followers f1
         JOIN followers f2 ON f1.followed_id = f2.follower_id
WHERE f1.follower_id = 4;

Execution plan for the query:

HashAggregate  (cost=253.84..257.23 rows=339 width=8)
  Group Key: f2.followed_id
  ->  Nested Loop  (cost=0.84..253.00 rows=339 width=8)
        ->  Index Only Scan using followers_pkey on followers f1  (cost=0.42..16.22 rows=19 width=8)
              Index Cond: (follower_id = 4)
        ->  Index Only Scan using followers_pkey on followers f2  (cost=0.42..12.27 rows=19 width=16)
              Index Cond: (follower_id = f1.followed_id)

So I think that the execution plan does not show that tere are no complex operations being done. One thing I read is that when joining tables, the database engine needs to search for matching rows in both tables and combine them into a single result set. Is that the reason for poor performance?

Or maybe I'm missing some other valid point?

1
  • 1
    Aristotelian syllogism: graph DBMSs by design excel at modeling graphs; social networks are graphs; ergo, graph DBMSs excel at modeling social networks.
    – RonJohn
    May 8, 2023 at 15:10

2 Answers 2

3

You are mostly right that the query you posted above (a simple join, filter and aggregation) can easily be dealt with in any decent RDBMS with the right hardware and indexing. Joins and filters per-se are not a problem for modern RDBMSs, that is an old myth, mostly propogated by those who do not know how to index properly.

However, this is not the type of query that a graph database excels at. Graph databases would primarily be doing the types of queries that would require recursive CTEs, complex functions or cursors to achieve in SQL, all of which are much slower than regular joins in almost all RDBMSs.

For example, a typical query might be: all followers of id: 4, and recursively all their followers, where each one has at least two links to every other one. Such a query is fiendishly difficult and slow to do using SQL.

5
  • Recursive CTEs are generally not horribly slow in modern RDBMS, but obviously it depends on the complexity of the logic implemented in the recursion.
    – J.D.
    May 7, 2023 at 15:24
  • Horribly slow compared to a straight join. They are generally implemented using some kind of temporary table, which introduces its own read/write overhead. May 7, 2023 at 16:48
  • Eh, yea but that's a bit context specific though. Whereas cursors are almost always objectively worse, significantly, and I'd be careful bucketing the two together in regards to performance, for those who read your answer and don't have enough experience working with both. Sort operations have overhead as well, but that doesn't mean they're always horrible or not performant even though a straight join without needing to sort is always better.
    – J.D.
    May 7, 2023 at 23:37
  • But would you say that for this query, the relational dbms performance would not degrade significantly as the size of the tables grow? In comparison to a graph database such as Neo4j?
    – Damiano
    May 8, 2023 at 8:39
  • 2
    Not if it's well indexed. B+ trees are highly efficient when used correctly, they have O(log(n)) complexity and normally require only a handful of lookups even for billion row tables. May 8, 2023 at 11:12
1

The plan you post might not be complex, but it certainly can be slow. If your visibility map isn't all set, or if the query were slightly different than what you show selecting one more column, it might need to make 339 serial reads to random pages of the table and index. With a 5400 rpm hard disk and nothing usably cached, that would be almost 4 seconds.

So the problem certainly can be real. It can be addressed by ensuring index-only scans, caching, SSD, perhaps effective_io_concurrency or parallel query. Maybe it could also be addressed by using some unnamed "graph dbms", how could we possibly know what anonymous products are capable of?

1
  • I meant graph dbms - in general, but the engine I'm investigating for this role is Neo4j.
    – Damiano
    May 6, 2023 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.