Calculating averages of rows in a very large dataset

Question

We have a ratings system in our website that allows users to provide feedback to 3 different questions about a user.
We currently calculate the rating using averages using the following query on our RDBMS:

SELECT AVG(question_1), AVG(question_2), AVG(question_3)
FROM ratings
WHERE user_id = 1

This query does not scale even when the result is cached (and it is) since some of our users have millions of ratings.
Using a functional index is not an option because our RDBMS does not support them and using one would slow down writes significantly.

The solution I came up with is to create an append-only log of the averages in a given time frame and periodically merge them using a weighted average.
So we'd end up with the following data structure per user:

| question1_avg | question2_avg | question3_avg | ratings_count | timestamp  |

| 3.4           | 4.5           | 4.9           | 10000         | 1480429792 |

| 5             | 5             | 5             | 30            | 1480429848 |

So the merge process would look like:

(3.4 * 10000 + 5 * 30) / 10030

The previous records would be tombstoned and the new average will be appended to the log.
Is this design correct? Will it work at scale?
Where will you store that kind of data? A document store (such as MongoDB), a key-value store (such as Redis) or an RDBMS?

Since this concept is very similar to CRDT Counters I tried to find a Convergent Replicated Data Type that allows you to calculate averages but I could not find one. Is there a data structure I missed?
Is there another algorithm or data type I should look into?

Answer 1

What you can do to optimize this depends on how precisely the rating system works, and what kinds of analysis you want to do with the data. But if the ratings are discrete (like a 1–5 star rating), we can calculate them efficiently by storing the accumulated votes in a histogram. That is, we count how often each rating was chosen:

| Question | r1  | r2  | r3  | r4  | r5  | (avg) |
+----------+-----+-----+-----+-----+-----+-------+
|        1 |  12 |  89 | 127 | 698 |  74 |   3.7 |
|        2 |  39 |  72 | 487 | 278 | 124 |   3.4 |
|        3 |  90 |   9 | 776 |  25 | 100 |   3.0 |

where the average is calculated as (1*r1 + 2*r2 + 3*r3 + 4*r4 + 5*r5) / (r1 + r2 + r3 + r4 + r5), which looks tedious but is a constant-time operation.

This is similar to your weighted average approach, but will not accumulate errors over time.

You should probably still store the individual ratings as well, as that allows additional analysis (e.g. is there a correlation between question 1 and 3? Are there trends over time?). By aggregating the data into a histogram, we lose that information.

It is perfectly reasonable to store both the individual ratings and the histogram in the same relational database. In particular, this will allow us to keep the vote counts in sync by using triggers and/or stored procedures. Upon insert, the appropriate count is simply incremented. If we were to use a separate database for the aggregated ratings, the applications writing to the database would have to do additional work.

This strategy will not work if the possible ratings are not discrete, or when the rating calculation is more complicated than a simple average, e.g. if ratings decay over time.