1

I want to show a number of posts, ordered by their score, limited to some number. The score is the product of the number of likes they have (from another table) and the recipricol of their normalized (0 to 1) age.

I have an SQL query that works fine for my MVP, but it neccesitates a full scan of the posts table.

SELECT
    posts.id,
    posts.title,
    1 / (EXTRACT(EPOCH FROM (NOW() - posts.timestamp)) / EXTRACT(EPOCH FROM MIN(posts.timestamp))) * COUNT(likes) AS score,
    COUNT(likes) AS likes
FROM
    posts
LEFT JOIN
    likes ON likes.post_id = posts.id
GROUP BY
    posts.id
ORDER BY
    score DESC

(MIN(posts.timestamp) could be replaced by some arbitrary fixed epoch.)

The calculations have to be done in the database, since the sorting needs to be done before the limiting.

Thinking towards the longer term, as well as adding personalized feeds, how would one go about building something that can take streams of posts and likes, and continually aggregate those to keep an ordered list of posts relative up to date? I'm planning to use Apache Pulsar for some of my other needs, so that seems like a good starting place, but I'm not sure what would be a suitable tool for the aggregation, and what that might look like. Is this a problem something like Spark would be suited towards?

Edit: I thought perhaps I could create a materialized view based on this query and add an index on the sort column, which would go a long way towards what I need for now. However, I thought Postgres implemented them with triggers and so they would stay up to date, but apparently you have to refresh them, so I'm still open to better ideas.

7
  • How set are you on this specific algorithm and how exact do you need this do be?
    – Helena
    Jul 18 at 9:49
  • You write that you limit by some number, but your SQL query doesn't have a limit. Will that limit be fixed or within a specific range? Are you only ever interested in the top results or will you show things in the middle (e.g. by using pagination).
    – Helena
    Jul 18 at 9:53
  • @Helena I'm not particularly set on it. I just chose it because the 1/x graph approximated what I wanted. Yes, sorry, there's no LIMIT on that one, because I grabbed it from my console. The actual query is written using Quill. The limit will be different in different cases, and actually I'll need filtered versions (e.g. only ones in a given category) and a pagination window eventually too.
    – Isvara
    Jul 18 at 11:00
  • In general, for time decay an exponential function is more appropriate than a reciprocal. If you use such a function, likes would have a "half-life" after which they are only worth half as much as a fresh like. For example, if your half-life is one week, two likes one week ago would count as much as one like now or four likes two weeks ago. For relative ordering, it is possible to just accumulate likes with their time-exoonential weights, and do the sorting of posts without arithmetics in the sql query. Sorry, posting from mobile, so working out the exact algorithm in an answer isn't feasible. Jul 18 at 20:51
  • @Hans-MartinMosner That sounds great. So if I'm understanding correctly, I could add a score column to my posts table, and an INSERT trigger on the likes table that calculates the amount that that like contributes (based on time) and adds that to the relevant post's score (and subtracts it on DELETE).
    – Isvara
    Jul 18 at 23:13
1

To expand on my comment:

Likes are weighted by an exponential function of t_like - t_ref. To achieve a half-life of one week, you multiply this difference by weight_factor = LN(2)/d_week where d_week is the duration of a week measured in the unit used to compute time differences. The complete weighted score for a like would be EXP((t_like-t_ref)*weight_factor). If you have dislikes or percentage-likes, you can multiply this by -1 or the percentage factor.

The weighted likes can be accumulated in a column score in your posts table, for example using database triggers. Since this column then represents the sum of time-weighted likes, you can directly sort by it descending.

As noticed, this algorithm will lead to float exponent overflow after some time, specifically after 2^8 or 2^11 half-life intervals if you choose an optimal t_ref, earlier otherwise.

To circumvent this, you need to readjust t_ref regularly (often enough that overflow doesn't happen, so for example yearly for a 1 week half-life, or monthly if you choose a 1 day half-life.

When readjusting, you need to divide all post scores by EXP((t_ref_new-t_ref_old)*weight_factor). To avoid calculating wrong scores when likes are inserted during that operation, you need to either lock out processing of likes during this, or recalculate the weighted scores for posts which received likes during that time (or just recently, wouldn't matter). If your likes table includes a timestamp t_like that should be relatively easy.

1
  • Still some things to work out, but this is an excellent jumping off point.
    – Isvara
    Jul 19 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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