Рейтинг лидеров в MySQL со зрителем в середине набора результатов

У меня есть таблица лидеров, которая выглядит так:

|--------------------------------------|
| userId | allTimePoints | allTimeRank |
|--------------------------------------|
|   ..   |      ...      |      ...    |
|   xx   |    5555555    |       ?     |
|   ..   |      ...      |      ...    |
----------------------------------------

Предположим, что в таблице миллион записей и что allTimePoints постоянно обновляется. Когда пользователь просит показать таблицу лидеров, я хотел бы иметь возможность показать ему его рейтинг, счет, а также ближайших конкурентов. Я хотел бы добиться следующего:

  • выяснить ранг каждого пользователя (сортировать таблицу по allTimePoints DESC)
  • выяснить смещение страницы, чтобы средство просмотра таблицы лидеров находилось в середине сокращенного набора результатов
  • сделать это в течение приемлемого времени выполнения (например, создать ощущение мгновенного отклика, даже если сотни тысяч других пользователей одновременно попадают на экран таблицы лидеров)

Я начал так, и на моей машине это занимает около 0,4 секунды, когда в таблице 1 миллион строк.

SET @rowIndex := 0;
SET @rank := 0;
SET @prev := NULL;
SET @userIdPosition := 0;
SELECT
    @rowIndex := @rowIndex+1 AS rowIndex,
    userId,
    @rank := IF(@prev=allTimePoints, @rank, @rank+1) AS rank,
    @prev := allTimePoints AS allTimePoints,
    @userIdPosition := IF(userId=1860, @rowIndex, @userIdPosition) AS requestedOffset
FROM Leaderboard
ORDER BY allTimePoints DESC;

Кстати, преимущество этого метода во время выполнения по сравнению с использованием самосоединения описано здесь (это намного быстрее): http://code.openark.org/blog/mysql/sql-ranking-without-self.-join

Я сохраняю rowIndex и rank как отдельные переменные, чтобы можно было более точно рассчитать смещение страницы запрашивающего пользователя, если есть связи в рейтинге (т. е. n пользователей имеют одинаковую оценку).

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

Что еще хуже, если я расширим этот запрос, чтобы он правильно работал с пейджингом, как описано выше, время выполнения увеличится до 1,5 с.

SET @rowIndex := 0;
SET @rank := 0;
SET @prev := NULL;
SET @userIdPosition := 0;
SELECT sortedL.userId, sortedL.rank, sortedL.allTimePoints
FROM 
    (SELECT
        @rowIndex := @rowIndex+1 AS rowIndex,
        userId,
        @rank := IF(@prev=allTimePoints, @rank, @rank+1) AS rank,
        @prev := allTimePoints AS allTimePoints,
        @userIdPosition := IF(userId=1860, @rowIndex, @userIdPosition) AS requestedOffset
    FROM Leaderboard
    ORDER BY allTimePoints DESC) AS sortedL
-- simulate paging, as LIMIT doesn't seem to accept variables
WHERE sortedL.rowIndex > sortedL.requestedOffset -15 AND sortedL.rowIndex < sortedL.requestedOffset + 15;

Это возвращает 29 пользователей, а запрашивающий пользователь находится посередине, как и хотелось.

Если я запускаю это с EXPLAIN, я вижу, что подзапрос использует FILESORT, но результаты не индексируются, и, следовательно, внешний SELECT вынужден выполнить еще одно полное сканирование набора результатов, используя WHERE (медленнее, чем FILESORT).

Вопросы (1): как это оптимизировать?

Другая идея состояла в том, чтобы хранить рейтинг в индексированном столбце: allTimeRank. Я подумал, что поэкспериментирую с сортировкой таблицы в процедуре по расписанию (скажем, каждые 10 минут), а затем предложу очень быстрый доступ с помощью более простого SELECT, который будет использовать индекс. Мне не удалось заставить это работать должным образом, похоже, оно не использует условие в моем предложении WHERE (ранжирование, хранящееся в allTimeRank, неверно, и MySQL жалуется, поэтому мне нужно отключить безопасные обновления, чтобы получить его хоть беги)

SET SQL_SAFE_UPDATES=0;
SET @rowIndex := 0;
SET @rank := 0;
SET @prev := NULL;
SET @userIdPosition := 0;
UPDATE Leaderboard L, 
    (SELECT
        @rowIndex := @rowIndex+1 AS rowIndex,
        userId,
        @rank := IF(@prev=allTimePoints, @rank, @rank+1) AS rank,
        @prev := allTimePoints AS allTimePoints,
        @userIdPosition := IF(userId=1860, @rowIndex, @userIdPosition) AS requestedOffset
    FROM Leaderboard
    ORDER BY allTimePoints DESC) AS sortedL
SET L.allTimeRank = sortedL.rank
WHERE sortedL.userId = L.userId;
SET SQL_SAFE_UPDATES=1;

Вопрос (2): как заставить работать условие WHERE.

Это заняло от 2 минут до 12 секунд. Не знаю, почему несоответствие. В любом случае это заблокирует ОБНОВЛЕНИЯ от пользователей, которые набирают очки, создавая ощущение, что приложение зависло. Вопрос (3): есть ли обходной путь?


mysql sql jpql leaderboard
person DTs    schedule 10.12.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Во-первых, вы неправильно вычисляете ранг. Если есть три игрока: Бритни (100 баллов), Рэйчел (100 баллов) и Сьюзан (75 баллов), то Бритни и Рэйчел имеют ранг 1, а Сьюзен должен иметь ранг 3. Ваша программа даст Сьюзен ранг 2.

Во-вторых, когда игроки имеют одинаковые очки (и ранг), они должны отображаться в последовательном порядке. Порядок в одинаковых баллах/рангах должен соответствовать порядку, в котором она набрала этот балл.

Я бы добавил в таблицу два столбца: allTimeRank и allTimeRankOrder. И обновлять в режиме реального времени каждый раз, когда точки меняются. Поймите, что если моя оценка упадет со 100 до 125, переоценивать нужно будет только тех пользователей, у которых были оценки от 100 до 124, то есть тех, кого я перепрыгнул.

Вот процедура, чтобы сделать это. Он предполагает, что очки всегда идут вверх, а не вниз. У меня нет таблицы с миллионом строк для тестирования, но если у вас настроены правильные индексы, я надеюсь, что она будет работать довольно быстро.

CREATE PROCEDURE `updateUserPoints`(IN `puserid` VARCHAR(10), IN `pnewPoints` INT)
BEGIN
SET @currPoints = 0;
SET @currRank = 0;
SET @currRankOrder = 0;

SELECT allTimePoints, allTimeRank, allTimeRankOrder INTO @currPoints, @currRank, @currRankOrder from Leaderboard where userid = puserid;

SET @newRank = 0;
SET @newRankOrder = 0;
SELECT max(allTimeRank), max(allTimeRankOrder)+1 INTO @newRank, @newRankOrder FROM Leaderboard WHERE allTimePoints = pnewPoints;

IF (@newRank IS NULL) THEN 
   SET @newRank = (SELECT min(allTimeRank) from Leaderboard WHERE allTimePoints < pnewPoints);
   SET @newRankOrder = 0;
END IF;

UPDATE Leaderboard
   SET allTimePoints = pnewPoints,
       allTimeRank = @newRank,
       allTimeRankOrder = @newRankOrder
 WHERE userid = puserid;

/* all the people that I was tied with, but ahead in order,
   slide up one in the order */
 UPDATE Leaderboard
    SET allTimeRankOrder = allTimeRankOrder - 1
  WHERE allTimeRank = @currRank
    AND allTimeRankOrder > @currRankOrder;

/* did I jump anyone? Their rank goes down. */
UPDATE Leaderboard
   SET allTimeRank = allTimeRank + 1
 WHERE userid <> puserid
  AND allTimePoints >= @currPoints
  AND allTimePoints < pnewPoints;

 END
person Alan    schedule 10.12.2016