0

On my website, Replies to Post are sorted based on an algorithm that depends on multiple factors: Reactions, Reply Quality, User Reputation, Reports, Replies to Reply, etc... (these are just a few examples)

In most posts, sorting Replies is quick, but there are some posts that have, say 200K replies, and still growing, and sorting all these replies takes over 1 second.

I am aware of VIRTUAL GENERATED columns. However:

  1. Only if the algorithm depended on columns of the same table, I could create an indexed VIRTUAL GENERATED column.

  2. But, the algorithm depends on factors from other tables, such as User Reputation.

  3. And unfortunately, if a table has a VIRTUAL GENERATED column, it's no longer possible to do ALTER ONLINE TABLE. As this table is growing every day, this is a huge inconvenience.

What are my alternatives for optimizing such complex algorithm so that sorting Replies on Posts that have grown a lot, is quick/instance?

How does Reddit sort thousands and thousands of Replies, by "Top/Best", very quickly?

These are mainly posts that are years old, but still actively getting replies.

I was thinking on maintaining some kind of "materialized view", that would be updated on every new reply, or when something happens on a reply (like a Reaction, etc). And then sort the Replies based on the key of this view (joining with the rest). However, this would greatly increase storage required and UPDATES/INSERTS on the database. Is this a reasonable solution?

(I use InnoDB, file per table, no partitions. MariaDB 10.8.)

1 Answer 1

1

As you insert a row (Reply, etc), gather all the info needed for the sorting into a single, separate table. As you suggested a "materialized" view; but you have to do all the work.

Suggest storing a Reply should involve calling a Stored Procedure which will insert the info in the current tables, plus add/replace the row in the view-like table.

That table would have only the columns needed for the sorting; if possible, it would have an indexed metric, making it trivial to sort.

If you need RANK() or DENSE_RANK() or PERCENTILE(), that will be reasonably easy to compute -- assuming you have MySQL 8.0 or MariaDB 10.2.

See pt-online-schema-change for a way to ALTER TABLE with virtually no downtime.

One way to improve performance is to change the PRIMARY KEY to achieve clustering. It sounds like something like (user_id, thread_id, post_id) would help. (I assume that "post_id" includes both posts and replies).

Usually people have PRIMARY KEY(id) and that leads to things like "replies" being scattered throughout the table. This leads to a lot of I/O. Clustering clumps them together, thereby cutting back drastically on I/O.

4
  • Thanks very much once more, Rick! Looks like this might be the solution, so! Yeah, the PRIMARY KEY for this table would be something like that (maybe without user_id, as I don't think it's relevant), and then an index on (thread_id, post_score). The post_score being calculated either in the stored procedure, based on all the factors (and that way I don't store any of them in this table), or as a VIRTUAL GENERATED, if I store all the factors in the table. (it would be just duplicated/historical data, though!)
    – Nuno
    Jan 1, 2023 at 4:38
  • If post_score is repeatedly changing, it would be inefficient to have it as part ot any INDEX (including the PRIMARY KEY).
    – Rick James
    Jan 1, 2023 at 17:12
  • Thanks @RickJames - but if it's not like that (already calculated and indexed), then that means the database would have to be constantly calculating and sorting ("Filesort"), and therefore I'm back to the same problem I have right now, isn't that correct? Cheers, good day.
    – Nuno
    Jan 2, 2023 at 7:59
  • @Nuno - There is no efficient way to recompute "rank" when the metric keeps changing. By the way, "filesort" may actually be a reasonably fast in-RAM quicksort or heap sort. (Or it may involve a temp table on disk.)
    – Rick James
    Jan 2, 2023 at 16:48

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.