CODEWITHSUNDEEP
ruby-on-railsrubypostgresql
StefanDorresteijn
StefanDorresteijn

Reputation: 419

Optimized method for retrieving top high scores, one per user (has_many through)

I have an app that saves high scores for its users. We want to show a leaderboard but we only want every user to show up once with their highest score. We have a HighScore model, which saves scores and has a few other fields (game type, game settings, etc). HighScore has a has_many_through relationship to User (through high_score_user) because a HighScore can have multiple users (in case of a game that's played with multiple players). Now I need a function that shows that leaderboard but I have yet to find a good way to write this code.

Currently I simply grab the top 500 scores, include the high_score_users, then iterate through them to filter out duplicate users. Once I have 10 scores, I return those scores. Obviously this is extremely suboptimal and it's very, very slow. Here's the code I have so far:

def self.unique_leaderboard(map_name, score_type, game_mode, game_type)
    used_scores = Rails.cache.fetch("leaderboards_unique/#{map_name}/#{score_type}/#{game_type}/#{game_mode}",
                                    expires_in: 10.minutes) do
      top500 = HighScore
      top500 = top500.for_map(map_name) if map_name
      top500 = top500.for_type(score_type) if score_type
      top500 = top500.for_gametype(game_type) if game_type
      top500 = top500.for_gamemode(game_mode) if game_mode
      top500 = top500.current_season
      top500 = top500.ranked(game_type)
      top500 = top500.includes(:high_score_users)
      top500 = top500.limit(500)

      used_scores = []
      top500.each do |score|
        break if used_scores.count >= 10

        next unless (used_scores.map do |used_score|
                       used_score.high_score_users.map(&:user_id)
                     end.flatten.uniq & score.high_score_users.map(&:user_id)).empty?

        used_scores << score
      end
      used_scores
    end
    HighScore.where(id: used_scores.map(&:id)).includes(:users).ranked(game_type)
  end

I'm using Ruby on Rails with Postgres. How do I improve this code so it's not incredibly slow? I couldn't find a way to do it in SQL, nor could I find a way to do it properly with ActiveRecord.

Upvotes: 0

Views: 99

Answers (1)

Konstantin Strukov
Konstantin Strukov

Reputation: 3019

I would bet that the major time killer is this code:

next unless (used_scores.map do |used_score|
                       used_score.high_score_users.map(&:user_id)
                     end.flatten.uniq & score.high_score_users.map(&:user_id)).empty?

It is being executed up to 500 times in a worst case, and each iteration is relatively heavy-weight due to several unnecessary maps on each iteration. And all this computational complexity just to track unique user_ids from the high scores (to short-circuit the iteration as soon as 10 unique top scorers are selected...

So if you just replace

...
used_scores = []
top500.each do |score|
  ...
end
used_scores
...

with smth. like

top_scorers = Hash.new { |h,k| h[k] = [] }
top500.each do |score|
  score.high_score_users.each do |user|
    top_scorers[user.id] << score
    break if top_scorers.size >= 10
  end
end
top_scorers.values.flatten.uniq

it should become significantly faster already.

But honestly fetching 500 high scores just to pick 10 top scorers seems weird anyway. This task can be solved perfectly fine by the database itself. If <high scores SQL query> is your high scores query (without the limit part) then something like this would do the job (pseudocode! just to illustrate the idea)

user_ids = select distinct(user_id) from <high scores SQL query> limit 10;
select * from <high scores SQL query> where user_id in <user_ids>

(this pseudocode could be "translated" into AR query(ies) in different ways, it's up to you)

Upvotes: 1

Related Questions