Как эффективно получить ряд ранжированных пользователей (для лидеров), используя Postgresql

Я прочитал много сообщений по этой теме, таких как mysql-get-rank-from-leaderboards.

Однако ни одно из решений не эффективно в масштабе для получения диапазона рангов из базы данных.

Проблема проста. Предположим, что у нас есть таблица Postgres с столбцом "id" и другим столбцом INTEGER, значения которого не уникальны, но у нас есть индекс для этого столбца.

например. таблица может быть:

CREATE TABLE my_game_users (id serial PRIMARY KEY, rating INTEGER NOT NULL);

Цель

Определите ранг для пользователей, заказывающих пользователей в столбце "рейтинг" по убыванию.
Уметь запрашивать список из ~ 50 пользователей, заказанных этим новым "рангом", с центром в любом конкретном пользователе.
Например, мы можем возвращать пользователей с рангом {15, 16,..., 64, 65}, где центральный пользователь имеет ранг № 40
Производительность должна масштабироваться, например. не менее 80 мс для 100 000 пользователей.

Попытка # 1: функция окна row_number()

WITH my_ranks AS 
  (SELECT my_game_users.*, row_number() OVER (ORDER BY rating DESC) AS rank
   FROM my_game_users)
SELECT *
FROM my_ranks
WHERE rank >= 4000 AND rank <= 4050
ORDER BY rank ASC;

Это "работает", но запросы усредняют 550 мс с 100 000 пользователей на быстром ноутбуке без какой-либо другой реальной работы.

Я попробовал добавить индексы и перефразировал этот запрос, чтобы не использовать синтаксис "WITH", и ничего не помогло ускорить его.

Попытка # 2 - подсчет количества строк с большим значением оценки Я попробовал такой запрос:

SELECT  t1.*,
  (SELECT  COUNT(*)
   FROM my_game_users t2
   WHERE (t1.rating, -t1.id) <= (t2.rating, -t2.id)
  ) AS rank
FROM my_game_users t1
WHERE id = 2000;

Это прилично, этот запрос занимает около 120 мс, при этом 100 000 пользователей имеют случайные рейтинги. Однако это возвращает только ранг для пользователя с определенным идентификатором (2000).

Я не вижу эффективного способа расширить этот запрос, чтобы получить ряд рангов. Любая попытка расширить это делает очень медленный запрос.

Я знаю только идентификатор пользователя "center", так как пользователи должны быть упорядочены по рангу, прежде чем мы узнаем, какие из них находятся в диапазоне!

Попытка # 3: упорядоченное в памяти дерево

В итоге я использовал Java TreeSet для хранения рангов. Я могу обновить TreeSet всякий раз, когда новый пользователь вставлен в базу данных или изменяется рейтинг пользователя.

Это супер быстрый, около 25 мс с 100 000 пользователей.

Однако у него есть серьезный недостаток, который он обновил только на Webapp node, обслуживающем запрос. Я использую Heroku и развожу несколько узлов для своего приложения. Таким образом, мне нужно было добавить запланированную задачу для сервера, чтобы каждый раз создавать таблицу ранжирования, чтобы убедиться, что узлы не слишком из-за синхронизации!

Если кто-нибудь знает об эффективном способе сделать это в Postgres с полным решением, то я все уши!

Ответ 1

Вы можете получить те же результаты, используя order by rating desc и offset и limit, чтобы получить пользователей от определенного ранга.

WITH my_ranks AS 
    (SELECT my_game_users.*, row_number() OVER (ORDER BY rating DESC) AS rank FROM my_game_users)
SELECT * FROM my_ranks WHERE rank >= 4000 AND rank <= 4050 ORDER BY rank ASC;

Вышеуказанный запрос совпадает с

select * , rank() over (order by rating desc) rank 
from my_game_users 
order by rating desc
limit 50 offset 4000

Если вы хотите выбрать пользователей вокруг ранга № 40, вы можете выбрать ранжирование # 15- # 65

select *, rank() over (order by rating desc) rank 
from my_game_users 
order by rating desc
limit 50 offset 15

Ответ 2

Спасибо, @FuzzyTree! Ваше решение не дает мне все, что мне нужно, но оно подтолкнуло меня в правильном направлении. Здесь полное решение, на котором я собираюсь сейчас.

Единственное ограничение с вашим решением заключается в том, что нет способа получить уникальный ранг для определенного пользователя. Все пользователи с одинаковым рейтингом будут иметь одинаковый ранг (или, по крайней мере, это undefined по стандарту SQL). Если бы я знал OFFSET раньше времени, то ваш рейтинг был бы достаточно хорош, но я должен сначала получить ранг определенного пользователя.

Мое решение состоит в том, чтобы выполнить следующий запрос, чтобы получить ряд рангов:

SELECT * FROM my_game_users ORDER BY rating DESC, id ASC LIMIT ? OFFSET ?

Это в основном уникальное определение рангов по рейтингу, а затем кто присоединился к игре сначала (нижний id). Чтобы сделать это эффективным, я создаю индекс (рейтинг DESC, id)

Затем я получаю определенный пользовательский ранг для подключения к этому запросу с помощью:

SELECT COUNT(*) FROM my_game_users WHERE rating > ? OR (rating = ? AND id < ?)

Я действительно сделал это более эффективным:

SELECT (SELECT COUNT(*) FROM my_game_users WHERE rating > ?) + (SELECT COUNT(*) FROM my_game_users WHERE rating = ? AND id < ?) + 1

Теперь даже с этими запросами требуется около 78 мс среднего и среднего времени, чтобы получить ряды вокруг пользователя. Если у кого-то есть хорошая идея, как ускорить их, я все уши!

Например, получение диапазона рангов занимает около 60 мс, и объяснение этого дает:

EXPLAIN SELECT * FROM word_users ORDER BY rating DESC, id ASC LIMIT 50 OFFSET 50000;

"Limit (cost=6350.28..6356.63 rows=50 width=665)" " -> Index Scan using idx_rating_desc_and_id on word_users (cost=0.29..12704.83 rows=100036 width=665)"

Таким образом, он использует рейтинг и индекс id, но он все еще имеет эту переменную стоимость от 0.29... 12704.83. Любые идеи о том, как улучшить?

Ответ 3

Если вы закажете его в порядке убывания, у вас есть его в правильном порядке. Используйте функцию rownumber(). Выберите номер строки в postgres

Также вы должны использовать кеш в памяти для хранения данных в памяти. Что-то вроде redis. Это отдельное приложение, которое может обслуживать несколько экземпляров даже удаленно.