SQL Server rank query optimization

Question

I'm trying to optimize a query to get the rank of a user in specific country from the DB. Currently is seems very inefficient.

I'm trying to determine what can be done to improve it.

This is the current SQL:

SELECT COUNT(*) + 1
FROM leaderboard lb, users u
WHERE u.country = 'United States' 
  AND lb.id = u.id 
  AND lb.score + 1 > (SELECT lb2.score 
                      FROM leaderboard lb2
                      WHERE lb2.id = some_user_id);

Details:

Users table:

• id is the primary key
• country column is indexed

Leadeboard table:

• id is the primary key
• score column is indexed

The execution plan shows 2 warnings:

Columns With No Statistics: [dbo].[leaderboard].id (cost 23%)

Columns With No Statistics: [dbo].[users].id (cost 28%)

Answer 1

I think you are looking for something like:

SELECT u.id AS user_id, u.country, lu.score, RANK() OVER (ORDER BY lu.score DESC) AS rnk
FROM users u
INNER JOIN leaderboard lu ON u.id = lu.id
WHERE u.country = 'United States'

You can see a demo here: http://rextester.com/KHM76159

Answer 2

Try storing the score in a variable then use it within the JOIN clause.

declare @score int = ( select top 1 score 
                       FROM leaderboard
                       WHERE id = some_user_id 
                     );

SELECT COUNT(*) + 1 as 'rank'
FROM leaderboard lb
JOIN users u
  ON lb.id = u.id 
 AND lb.score > @score
 AND u.country = 'United States';

Answer 3

Update 1: Just remove computation from where clause and use Joins

Based on your comments, if my first suggestion didn't improve the performance then i think the only thing you can do is: first of all, make sure that you created all needed indexes and statistics and remove computation from the WHERE clause, because it is not necessary, and use JOINs instead of linking table in the where clause (Using Joins doesn't improve performance but it's syntax is clearer and less ambiguous)

SELECT COUNT(*) + 1
FROM leaderboard lb INNER JOIN users u
ON lb.id = u.id 
WHERE u.country = 'United States' 
AND lb.score  > (SELECT lb2.score 
                  FROM leaderboard lb2
                  WHERE lb2.id = some_user_id)

Note that lb.score + 1> (SELECT lb2.score FROM leaderboard lb2 WHERE lb2.id = some_user_id) is equivalent to lb.score >= (SELECT lb2.score FROM leaderboard lb2 WHERE lb2.id = some_user_id) if score is integer, and you don't need it.

---

Initial answer: Use one of the Ranking functions with a subquery or CTE

I think it is better to use a ranking function like RANK()

Subquery

SELECT * FROM (

    SELECT u.id AS user_id, u.country, lb.score, RANK() OVER (ORDER BY lb.score DESC) AS rnk
    FROM users u
    INNER JOIN leaderboard lb ON u.id = lb.id
    WHERE u.country = 'United States' 

) T1 WHERE T1.user_id = some_user_id

Common table expression

 WITH CTE_1 AS (

    SELECT u.id AS user_id, u.country, lb.score, RANK() OVER (ORDER BY lb.score DESC) AS rnk
    FROM users u
    INNER JOIN leaderboard lb ON u.id = lb.id
    WHERE u.country = 'United States' 

) SELECT * FROM CTE_1 WHERE CTE_1.user_id = some_user_id

References

• Ranking Functions (Transact-SQL)
• WITH common_table_expression (Transact-SQL)
• Subquery Fundamentals

Answer 4

Make it more readable/testable and force execution steps using CTE's

WITH scoreToRank AS (
  SELECT score
  FROM leaderboard
  WHERE id = {some_user_id}
)

, usersInCountry AS (
  SELECT id
  FROM users
  WHERE country = 'United States'
)

, countOfUsersWithGreaterScore AS (
  SELECT COUNT(*) AS count
  FROM leaderboard l
  INNER JOIN usersInCountry u ON u.id = l.id
  WHERE l.score > (SELECT score FROM scoreToRank)
)

SELECT count + 1 AS usersRank FROM countOfUsersWithGreaterScore

Depending on SQL version and data density, using as IN clause for countOfUsersWithGreaterScore / usersInCountry may be more efficient

Answer 5

Can you please try this? It looks a little odd but I think it might work:

SELECT COUNT(*) + 1
FROM leaderboard lb, users u, leaderboard lb2
WHERE u.country = 'United States' 
  AND lb.id = u.id 
  AND lb.score + 1 > lb2.score AND lb2.id = some_user_id

Answer 6

I prefer joins over subqueries, the query below should give you the same result from your question.

SELECT COUNT(*) + 1
FROM leaderboard lb2
    LEFT OUTER JOIN users u ON u.Id <> lb2.Id AND u.country = 'United States'
    LEFT OUTER JOIN leaderboard lb ON lb.Id = u.Id
WHERE lb2.Id = some_user_id AND lb.score >= lb2.score 

If some users don't have scores than you should check for null values or you could change the joining order, which might even be better in some cases:

SELECT COUNT(*) + 1
FROM leaderboard lb2
    LEFT OUTER JOIN leaderboard lb ON lb.Id <> lb2.Id AND lb.score >= lb2.score 
    LEFT OUTER JOIN users u ON u.Id = lb.Id
WHERE lb2.Id = some_user_id AND u.country = 'United States'

Answer 7

This doesn't address your query, but rather the overall problem in case that's useful.

I confronted the same for an international contest where the teams table could get quite big. I never was able to get an SQL ranking query to perform well enough for a good user experience (goal was 80ms, and the query was somewhat more complex than yours), so finally decided to use a redis server just for returning ranks.

It provides a ranking function exactly suited to this problem. It's fast: a few millis for a table of 10 million contestants.

I still regarded scores stored in the SQL DB as the source of truth. Redis isn't ACID. It saves to disk only snapshots of its data image in RAM. If the server goes down, it reverts to the last snapshot. So redis and the source of truth could diverge a bit.

This wasn't any problem in my case because instantly returned ranks were acknowledged to be unofficial pending final review by judges. Missing data due to reboots from snapshot were "self healing". That is, if I queried for the rank of a team and it wasn't in the redis store, I added it then re-queried. I also ran a daily sync job to restore perfect agreement. I could run this sync at any time to initialize a new redis from scratch.

This scheme proved extremely fast and robust for 7 years. The implementation it replaced used a custom BerkeleyDB-based service. That one worked well for the preceding 7 years.

One other point is that a redis service can be very handy for other purposes like caches.

Answer 8

Maybe try denormalizing? For each row in the leaderboard table, include the user's country.

Also, use a CountryID instead of the country name, since ints are faster to query than varchar. (You can look up the name for the country separately.)

Then you could get the count you're seeking without needing a join or subselect - it would just be a select on a single table (and a faster one, since you would be using an int).

Answer 9

try something like :

SELECT score FROM leaderboard WHERE id in
    SELECT id FROM users WHERE country='United States' and id=some_user_id