0

Recently I started discovering a topic around "How to design db schema for storing structures similar to Instagram/Facebook/Reddit comments?".

After extensive research, I was able to find a bunch of different answers on SO, SE, medium articles and etc. Meanwhile, all of these articles were pretty basic and always point out a Closure table pattern, which I used once back in the day.

I did implement a comments/replies system only once a few years ago using PostgreSQL and since then the product is already not in production, so I don't know how my solution would scale in a data-intensive environment.

Therefore, I decided to ask a specific question with specific requirements and constraints, so I could probably get a hint from someone who had this experience in production!

Here we go with two different tasks:

Task 1

Requirements:

  • When I open a post I see only the first level of comments. In particular, 50 most liked comments are ordered ascending by the number of likes.
  • For every top-level comment: if a comment has only one reply - display this reply too.
  • For every top-level comment: if a comment has multiple replies, display only the one which is the most liked.
  • When the user clicks on "more replies": Display replies in descending order by their created_datetime.
  • The max depth is 2: Only the top-level comment and replies to it can exist. Replies to lower-level comments(depth == 0) should always be displayed near their parents. The only thing that distinguishes them is just a mention of a user you reply to, like @ on instagram.

Questions(only related to the design of relational database with Closure table):

  • What are the problems you faced in production with it and how you had to fix them? What would you recommend to people who just start with this, what should they spend their time on at the beginning to prevent a cascade of mess in the future?
  • Is there a better pattern with RDBS nowadays for this purpose?

Let's imagine the system grows. We don't talk about thousands of requests, but we talk about hundreds of thousands of comments and replies to them. E.g. some celebrity posted a message and then all the fans started replying, having conversations and etc. It results in a lot of rows in our records in both the comment and closure tables. Our queries to group by amount of likes start getting much slower on some posts, causing long-running transactions which cause a ton of mess and even probably downtimes. Again, that's what it looks to me that could happen if we just use a closure table. But what really happens? Curious to hear stories of people who had problems with it in really data-intensive applications. E.g. We can shard the table somehow, right? Or for really big posts we could cache a lot of stuff, right?

Task 2

  • The main difference to the first one: When I open a post I see 50 most liked comments but with all their children. Meaning I fetch the whole tree for these 50 first comments. Depth is not limited.

Questions(only related to the design of relational database with Closure table):

  • Should we simplify the logic and become less ambitious, so we would go with business requirements similar to the ones in task 1? (when we don't have infinite depth and comments trees can grow only in width) I assume otherwise this is almost impossible to scale such a business logic when there are millions or billions of comments.
  • If the answer to the first question is no, how the magic happens then? ( I don't believe that such product requirements could be scalable while infrastructure would still stay profitable; costs would grow exponentially imo)

General questions to be answered first:

  • Is a relational database still a case for such a problem nowadays? I don't know much about graph databases, but wouldn't it be optimal to store such hierarchical data there? Probably I just need to discover graph databases deeper, so please feel free to link the related articles. Doesn't seem I found them in a week, so I would definitely need help with finding the right materials :)

To sum up: I understand that my questions may seem pretty vague, but they are also quite complex and require the knowledge of someone who had this experience. Meanwhile, I am also quite opinionated on some topics (like growth of costs/sharding/caching) and that's why it is even more difficult for me to compile the opinion - I wanna have more thoughts gathered, not only mine.

In case you think an extensive answer would take too much of your time - please give me just short answers like yes or no and just link all the resources you think could really help me to build my opinion on this topic. Sharing your real production experience of working with such systems would be really helpful and appreciated!

Thanks!

1
  • Is a relational database still a case for such a problem nowadays? - in a word, yes. If you want to try graph databases (I've no experience with these and am not saying they're unsuitable nor even that they're not as good as (or even not better than) a classic RDBMS), you could look at AgensGraph which is a PostgreSQL fork and/or the Apache AGE (A Graphics Extension) which is a PostgreSQL extension (better than a fork IMHO - many have tried, few have been chosen) using OpenCypher.
    – Vérace
    Sep 11, 2022 at 10:50

2 Answers 2

4

This question is likely to generate a lot of opinions. In comes the "NoSQL" crowd touting in vague terms why relational is bad and this and that.

The issue is complicated because the relational database method is intended to be a declarative approach where you specify your solution and the relational database management system (RDBMS) would then optimize your declarative expressions.

And that's where the problems arise. A specific RDBMS might not have the method that might be best for optimizing the specific thing. Or it might not recognize your expression of benefitting from whatever method of optimization in does have. And there are so many twists and tweaks where something can go totally off the rails for unknown reasons (I have found Oracle to be prone to such weird problems, even total crash bugs, which they are slow to fix, if ever.)

To get this question out of hand-waving opinion mongering, you should probably show some work of how you express your requirements and then speculate about how RDBMS might realize your query, and then only can one start discussing trade-offs of different solutions. You also have to be aware of the framing of the question. NoSQL always wins because they can just hard-code to one partial problem but the full context of the full system (especially ACID requirements) don't go away. It's not like graph databases did not exist before the relational model was invented by Edgar Codd.

CREATE TABLE User_ (
  id UUID PRIMARY KEY,
  name text
);

CREATE TABLE Post (
  id UUID PRIMARY KEY,
  respondingToPostId UUID REFERENCES Post(id),
  time timestamp NOT NULL DEFAULT current_timestamp,
  authorId UUID REFERENCES User_(id),
  text text
);

CREATE TABLE Reaction (
  postId UUID REFERENCES Post(id),
  time timestamp NOT NULL DEFAULT current_timestamp,
  reactionType char NOT NULL DEFAULT 'L'
);

Can this be made any simpler? I don't think you want anonymous reactions just counted, so you won't be able to do without the Reaction table. No premature optimization here!

Now the transactions, every Post is an INSERT INTO Posts, every click of "like" or "haha" or whatever becomes an INSERT INTO Reaction. Simple.

I merged Post and Comment into Post (kind'a like Twitter style). I don't think for optimization it helps much to have separate Post vs. Comment tables, but if you want you can of course do it

CREATE TABLE Post (
  id UUID PRIMARY KEY,
  time timestamp NOT NULL DEFAULT current_timestamp,
  authorId UUID REFERENCES User_(id),
  text text
);

CREATE TABLE Comment (
  id UUID PRIMARY KEY,
  postId UUID REFERENCES Post(id),
  respondingToCommentId Comment(id),
  time timestamp NOT NULL DEFAULT current_timestamp,
  authorId UUID REFERENCES User_(id),
  text text
);

This just pushed the issue one down. So I stick with the simpler model I gave above. But for topological sorting, we still need some response ordinal which is a zero padded number of the post.

CREATE TABLE Post (
  id UUID PRIMARY KEY,
  respondingToPostId UUID REFERENCES Post(id),
  responseOrdinal CHAR(4) DEFAULT (
     SELECT to_char(to_number(max(reponseOrdinal) + 1), '0999') 
       FROM Post r
      WHERE r.respondingToPostId = this.respondingToPost),
  time timestamp NOT NULL DEFAULT current_timestamp,
  authorId UUID REFERENCES User_(id),
  text text,
);

On this DEFAULT of the Post.responseOrdinal I am taking some liberty, probably no RDBMS would allow such as a default, but it could be done as a trigger. I pushed this in here for my transitive closure table that comes further below.

Reactions Ranking

First we have to deal with the Reactions (likes). We want some ranking order by likes. This is totally dynamic and likes will accumulate quickly. Likewise you might want to rank by how many comments a post got.

So just like I put the responseOrdinal in above, which I might have just written as

SELECT *, 
       TO_CHAR(
         RANK() OVER(
           PARTITION BY respondingToPostId 
           ORDER BY time, authorId),
         '0999') AS responseOrdinal
  FROM Post

the number of likes or replies I would put in here too. But I wonder if that is a good idea because it changes all the time! Making frequent UPDATEs will possibly roll over a lot of space in your Post table. This could be good or bad. How would we write those?

CREATE TABLE PostReaction AS
SELECT post.id AS postId, 
       reactionType,
       count(1) AS reactionCount
  FROM Post
  INNER JOIN Reaction r ON(r.postId = post.id)
 GROUP BY(post.id)

This here reminds us that you might want likes and dislikes (ratioing) or you might want to deal with different reaction types "like" vs. "haha" vs. "angry", etc. Let's say you just care about how many reactions overall you have:

CREATE TABLE PostReactionCount AS
SELECT post.id AS postId, 
       reactionType,
       count(1) AS reactionCount
  FROM Post
  INNER JOIN Reaction r ON(r.postId = post.id)
 GROUP BY(post.id)

and then every time you log a new reaction you'd have to update the reaction count. Say with an AFTER INSERT TRIGGER on Reaction. This being a trigger on INSERT into Reaction, then NEW is the Reaction being inserted.

UPDATE PostReactionCount prc
   SET reactionCount = reactionCount + 1
 WHERE prc.postId = NEW.postId;

or, if you put this reactionCount right into post, you can say

UPDATE Post
   SET reactionCount = reactionCount + 1
 WHERE post.id = NEW.postId;

Probably would decrement for retracted reactions.

Similar thing can be done for insert into Post to count replies if that is the ranking metric. Or some aggregate of replies, reactions, ratio-ing, whatever.

Now to display post in rank order of reactions:

SELECT * 
  FROM Post
 ORDER BY reactionCount DESC
 LIMIT 50

or

WITH RankedPostId AS (
  SELECT postId,
    FROM PostReactionCount 
   ORDER BY reactionCount DESC
   LIMIT 50
)
SELECT * 
  FROM RankedPostId INNER JOIN Post ON(post.id = postId)

or something with RANK() and a where clause on the ranking column.

The trade-off is where you want the massive UPDATE activity to reside, with the Post or with a separate table? Heck, if you use a column-oriented database it doesn't matter. This is the point, optimization done prematurely boxes you in. SQL is if anything a language for concise specification of the logic of the data, and in E.F. Codd's original idea manifoldly yet never perfectly implemented.

Transitive Closure of Reply Tree

Now as for transitive closures, these are easy to whip up when you analyze data offline, but in the middle of massive transaction load, you would have to somehow track those with something like a trigger. And of course, inserting a row into an index is also a "trigger" action of sorts, only built-in to the RDBMs.

Let's say we want the transitive closure of comments.

CREATE TABLE INTO PostPlus AS
SELECT respondingToPostId AS ancestorId,
       1 AS distance,
       responseOrdinal::text AS path,
       postId AS descendantId,
  FROM Post;

The ::text betrays that I use PostgreSQL and I am fed up with the stupid VARCHAR(4000) limit of Oracle, let alone the stupid "2" in "VARCHAR2".

but I pushed it up already. Next to populate the PostPlus table once I always do this:

INSERT INTO PostPlus AS
SELECT a.ancestorId,
       a.distance + d.distance,
       a.path ||'.'|| d.path,
       d.descendantId
  FROM PostPlus a
  INNER JOIN PostPlus d
    ON(a.descendantId = d.ancestorId)
 WHERE (a.ancestorId, d.descendantId) NOT IN (
   SELECT ancestorId,   descendantId FROM PostPlus);

You run this INSERT until nothing new is inserted and you are done (this converges very quickly because we are extending the paths on both ends). I don't use "CONNECT BY" or WITH "recursive". Because this is actually usually faster on any system I know (haven't played with IBM's for a long time). But I am all for recursive WITH if the RDBMS knew how to really optimize it in all situations, especially transaction oriented use.

Problem with transitive closure tables is, you need to keep them up to date. To keep this PostPlus up to date you would need to follow every INSERT into Post with several INSERTs into PostPlus, like do some TRIGGER where usually NEW is the new row just inserted, so I might do:

 INSERT INTO PostPlus AS
 SELECT NEW.respondingToPostId AS ancestorId,
        1                      AS distance,
        NEW.responseOrdinal    AS path,
        new.postId             AS descendantId
 UNION ALL
 SELECT p.ancestorId,
        p.distance + 1,
        p.path ||'.'||NEW.responseOrdinal
        new.postId
   FROM PostPlus p
  WHERE p.descendantId = new.respondingToPostId;

So far so good. Now whether you actually need all this is a question only answered by the SELECT queries we have to write (declaratively, think of it as specification of the system we want to build, optimization may come later.)

Taking it to Task

So for Task 2 it's

WITH RankedDirectReply AS (
  SELECT reactionCount,
         postId   AS replyId,
         distance AS replyDistance,
         path     AS replyPath,
    FROM PostPlus as reply
    INNER JOIN PostReactionCount
      ON(postId = descendantId)
   WHERE ancestorId = :givenPostId
     AND distance = 1
   ORDER BY reactionCount DESC
   LIMIT 50
), ReplyTree AS (
  SELECT reactionCount, 
         replyId, distance, path FROM ReplyTree
  UNION ALL
  SELECT reactionCount,
         descendantId, 
         directReply.distance + replyTree.distance,
         directReply.path ||'.'|| replyTree.path
    FROM RankedDirectReply directReply,
    INNER JOIN PostPlus replyTree
      ON(replyTree.ancestorId = replyId)
  ORDER BY reactionCount, path
)
SELECT * 
  FROM ReplyTree
  INNER JOIN Post reply
    ON(reply.id = replyId)
 ORDER BY reactionCount, path

Can this be optimized? Probably. But at least now we know what we're talking about.

Your Task 2 is just a little more annoying because it includes only one reply of a reply, also ranked. I won't write it out.

The question poses itself if the PostPlus table should be updated to have replies? Or if the first, second, third, whatever level of post id should also be kept in the PostPlus table so that you can quickly join them with the latest PostReactionCount to re-order the tree by what's most liked.

This is all not too hard. Just annoying to go over another special case with 3 levels now.

Now I know you asked for "practical experience" and all I did was essentially fill in your work you should have done, i.e., specifying the what in SQL so that the how can even be discussed with more than just slinging opinions and hand-waving.

Any "No-SQL solution" must give account how they deal with the inserts and updates. I suppose sacrificing a little bit on ACID properties can be entertained, especially for the response counts. But you could do that around an SQL database too. And what exactly would you speed up? You could allow the counts to lapse behind a bit. But if you want immediate update on the user's screen?

1
  • If anything, you at least deserve an upvote for the length of this answer. 🙂 But know that I did read through it in it's entirety and agree with a lot of it, nice. "But you could do that around an SQL database too. And what exactly would you speed up?" - That's my favorite line when the whole "NoSQL is faster" mantra comes into a conversation.
    – J.D.
    Sep 12, 2022 at 12:45
0

One "shortcut" way might be to have some type of "origreplyid" stored with all the replies. This allows for comment nesting, but also makes it trivial to simply grab the entire reply tree for a top level post. You can put a LIMIT to prevent overloading the DB too much, and have clients request more if they want it - Facebook and Twitter do this, probably others/most

Now there is a separate problem is the votes/reactions, and counting the number of replies. One way might be to store this info with the posts. This does somewhat violate the the "C" principle in ACID (consistency), because this value might not match up with whatever the votes/reactions says it is.

I think what the "big players" (Twitter/Facebook/et. all) do is have some type of very customized, specialized DB for all of this. I also think they pre-generate as much as possible. So when 100 people all request the same data, you're not hitting the DB with 100 different queries, but just grabbing the latest data off some KV lookup (probably)

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.