Дизайн Leaderboard с использованием SQL Server

Я создаю таблицу лидеров для некоторых своих онлайн-игр. Вот что мне нужно сделать с данными:

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

Я определил следующее определение таблицы и индекса, и у меня есть несколько вопросов.

Учитывая мои сценарии, у меня есть хороший первичный ключ? Причина, по которой у меня есть кластерный ключ в gameId, playerName и оценка, просто потому, что я хочу убедиться, что все данные для данного игра находится в той же области, и этот счет уже отсортирован. В большинстве случаев я покажу данные по убыванию счета (+ updatedDateTime для связей) для данного gameId. Это правильная стратегия? Другими словами, я хочу убедиться, что я могу запускать свои запросы, чтобы как можно быстрее получить ранг моих игроков.

CREATE TABLE score (
    [gameId]            [smallint] NOT NULL,
    [playerName]        [nvarchar](50) NOT NULL,
    [score]             [int] NOT NULL,
    [createdDateTime]   [datetime2](3) NOT NULL,
    [updatedDateTime]   [datetime2](3) NOT NULL,
PRIMARY KEY CLUSTERED ([gameId] ASC, [playerName] ASC, [score] DESC, [updatedDateTime] ASC)

CREATE NONCLUSTERED INDEX [Score_Idx] ON score ([gameId] ASC, [score] DESC, [updatedDateTime] ASC) INCLUDE ([playerName])

Ниже приведена первая итерация запроса, который я буду использовать, чтобы получить ранг моих игроков. Однако я немного разочарован планом исполнения (см. Ниже). Почему SQL должен сортироваться?. Дополнительная сортировка, похоже, поступает из функции RANK. Но разве мои данные уже отсортированы в порядке убывания (на основе кластеризованного ключа таблицы баллов)? Мне также интересно, нужно ли мне нормализовать немного больше моей таблицы и вывести столбец PlayerName в таблицу Player. Первоначально я решил сохранить все в одной таблице, чтобы свести к минимуму количество объединений.

DECLARE @GameId AS INT = 0
DECLARE @From AS DATETIME2(3) = '2013-10-01'

SELECT DENSE_RANK() OVER (ORDER BY Score DESC), s.PlayerName, s.Score, s.CountryCode, s.updatedDateTime
FROM [mrgleaderboard].[score] s
WHERE s.GameId = @GameId 
  AND (s.UpdatedDateTime >= @From OR @From IS NULL)

Спасибо за помощь!

Ответ 1

[Обновлено]

Основной ключ не является хорошим

У вас есть уникальная сущность, которая является [GameID] + [PlayerName]. И составной кластерный индекs > 120 байт с nvarchar. Найдите ответ @marc_s в соответствующем разделе SQL Server - Кластерный дизайн индекса для словаря

Схема вашей таблицы не соответствует вашим требованиям к периодам времени

Пример: я заработал 300 очков в среду, и этот счет был сохранен в таблице лидеров. На следующий день я заработал 250 баллов, но он не будет записываться в таблицу лидеров, и вы не получите результатов, если я запустил запрос во вторник в таблице лидеров.

Для получения полной информации вы можете получить из исторических игровых столов, но это может быть очень дорого

CREATE TABLE GameLog (
  [id]                int NOT NULL IDENTITY
                      CONSTRAINT [PK_GameLog] PRIMARY KEY CLUSTERED,
  [gameId]            smallint NOT NULL,
  [playerId]          int NOT NULL,
  [score]             int NOT NULL,
  [createdDateTime]   datetime2(3) NOT NULL)

Вот решения, чтобы ускорить процесс, связанный с агрегацией:

Индексированное представление по исторической таблице (см. сообщение @Twinkles).

Вам нужно 3 индексированных представления для трех периодов времени. Потенциально огромный размер исторических таблиц и 3 индексированных представления. Не удалось удалить "старые" периоды таблицы. Проблемы с производительностью для сохранения оценки.

Асинхронная таблица лидеров

Счета, сохраненные в исторической таблице. Задание SQL/ "Работник" (или несколько) в соответствии с расписанием (1 в минуту?) Сортирует историческую таблицу и заполняет таблицу лидеров (3 таблицы за 3 периода времени или одну таблицу с ключом периода времени) с предварительно рассчитанным рангом пользователя. Эта таблица также может быть денормализованной (иметь счет, дату и время, имя игрока и...). Плюсы: быстрое чтение (без сортировки), быстрое сохранение баллов, любые периоды времени, гибкая логика и гибкие графики. Минусы: пользователь закончил игру, но не сразу нашел себя в таблице лидеров.

Преагрегированная таблица лидеров

Во время записи результаты сеанса игры проходят предварительную обработку. В вашем случае что-то вроде UPDATE [Leaderboard] SET score = @CurrentScore WHERE @CurrentScore > MAX (score) AND ... для идентификатора игрока/игры, но вы сделали это только для таблицы "Все время". Схема может выглядеть так:

CREATE TABLE [Leaderboard] (
    [id]                int NOT NULL IDENTITY
                             CONSTRAINT [PK_Leaderboard] PRIMARY KEY CLUSTERED,
    [gameId]            smallint NOT NULL,
    [playerId]          int NOT NULL,
    [timePeriod]        tinyint NOT NULL,   -- 0 -all time, 1-monthly, 2 -weekly, 3 -daily
    [timePeriodFrom]    date NOT NULL,  -- '1900-01-01' for all time, '2013-11-01' for monthly, etc.
    [score]             int NOT NULL,
    [createdDateTime]   datetime2(3) NOT NULL
    )

playerId    timePeriod  timePeriodFrom  Score
----------------------------------------------
1           0           1900-01-01      300  
...
1           1           2013-10-01      150
1           1           2013-11-01      300
...
1           2           2013-10-07      150
1           2           2013-11-18      300
...
1           3           2013-11-19      300
1           3           2013-11-20      250
...

Итак, вам нужно обновить все 3 балла за весь период времени. Также, как вы можете видеть, таблица лидеров будет содержать "старые" периоды, такие как ежемесячный октябрь. Возможно, вам нужно удалить его, если вам не нужна эта статистика. Плюсы: не нужна историческая таблица. Минусы: сложная процедура для хранения результата. Требуется обслуживание лидеров. Запрос требует сортировки и JOIN

CREATE TABLE [Player] (
    [id]    int NOT NULL IDENTITY CONSTRAINT [PK_Player] PRIMARY KEY CLUSTERED,
    [playerName]        nvarchar(50) NOT NULL CONSTRAINT [UQ_Player_playerName] UNIQUE NONCLUSTERED)

CREATE TABLE [Leaderboard] (
    [id]                int NOT NULL IDENTITY CONSTRAINT [PK_Leaderboard] PRIMARY KEY CLUSTERED,
    [gameId]            smallint NOT NULL,
    [playerId]          int NOT NULL,
    [timePeriod]        tinyint NOT NULL,   -- 0 -all time, 1-monthly, 2 -weekly, 3 -daily
    [timePeriodFrom]    date NOT NULL,  -- '1900-01-01' for all time, '2013-11-01' for monthly, etc.
    [score]             int NOT NULL,
    [createdDateTime]   datetime2(3) 
)

CREATE UNIQUE NONCLUSTERED INDEX [UQ_Leaderboard_gameId_playerId_timePeriod_timePeriodFrom] ON [Leaderboard] ([gameId] ASC, [playerId] ASC, [timePeriod]  ASC,  [timePeriodFrom] ASC)
CREATE NONCLUSTERED INDEX [IX_Leaderboard_gameId_timePeriod_timePeriodFrom_Score] ON [Leaderboard] ([gameId] ASC, [timePeriod]  ASC,  [timePeriodFrom] ASC, [score] ASC)
GO

-- Generate test data
-- Generate 500K unique players
;WITH digits (d) AS (SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION
   SELECT 4 UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9 UNION SELECT 0)

INSERT INTO Player (playerName)
SELECT TOP (500000) LEFT(CAST(NEWID() as nvarchar(50)), 20 + (ABS(CHECKSUM(NEWID())) & 15)) as Name
FROM   digits CROSS JOIN digits ii CROSS  JOIN digits iii CROSS  JOIN digits iv CROSS  JOIN digits v CROSS  JOIN digits vi

-- Random score 500K players * 4 games = 2M rows
INSERT INTO [Leaderboard] (
    [gameId],[playerId],[timePeriod],[timePeriodFrom],[score],[createdDateTime])
SELECT  GameID, Player.id,ABS(CHECKSUM(NEWID())) & 3 as [timePeriod], DATEADD(MILLISECOND, CHECKSUM(NEWID()),GETDATE()) as Updated, ABS(CHECKSUM(NEWID())) & 65535 as score
    , DATEADD(MILLISECOND, CHECKSUM(NEWID()),GETDATE()) as Created
FROM (  SELECT 1 as GameID  UNION ALL SELECT 2  UNION ALL SELECT 3  UNION ALL SELECT 4) as Game
    CROSS JOIN Player
ORDER BY NEWID()
UPDATE [Leaderboard] SET [timePeriodFrom]='19000101' WHERE [timePeriod] = 0
GO

DECLARE @From date = '19000101'--'20131108'
    ,@GameID int = 3
    ,@timePeriod tinyint = 0

-- Get paginated ranking 
;With Lb as (
SELECT 
    DENSE_RANK() OVER (ORDER BY Score DESC) as Rnk
    ,Score, createdDateTime, playerId
FROM [Leaderboard]
WHERE GameId = @GameId
  AND [timePeriod] = @timePeriod
  AND [timePeriodFrom] = @From)

SELECT lb.rnk,lb.Score, lb.createdDateTime, lb.playerId, Player.playerName
FROM Lb INNER JOIN Player ON lb.playerId = Player.id
ORDER BY rnk OFFSET 75 ROWS FETCH NEXT 25 ROWS ONLY;

-- Get rank of a player for a given game 
SELECT (SELECT COUNT(DISTINCT rnk.score) 
        FROM [Leaderboard] as rnk 
        WHERE rnk.GameId = @GameId 
            AND rnk.[timePeriod] = @timePeriod
            AND rnk.[timePeriodFrom] = @From
            AND rnk.score >= [Leaderboard].score) as rnk
    ,[Leaderboard].Score, [Leaderboard].createdDateTime, [Leaderboard].playerId, Player.playerName
FROM [Leaderboard]  INNER JOIN Player ON [Leaderboard].playerId = Player.id
where [Leaderboard].GameId = @GameId
    AND [Leaderboard].[timePeriod] = @timePeriod
    AND [Leaderboard].[timePeriodFrom] = @From
    and Player.playerName = N'785DDBBB-3000-4730-B'
GO

Это только пример представления идей. Его можно оптимизировать. Например, объединение столбцов GameID, TimePeriod, TimePeriodDate в один столбец через таблицу словаря. Эффективность индекса будет выше.

P.S. Извините за мой английский. Не стесняйтесь исправить грамматические или орфографические ошибки.

Ответ 2

Вы можете посмотреть индексированные представления, чтобы создавать табло для общих диапазонов времени (сегодня, на этой неделе/месяц/год, все время).

Ответ 3

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

CREATE NONCLUSTERED INDEX [Score_Idx] 
ON score ([gameId] ASC, [updatedDateTime] ASC, [score] DESC) 
INCLUDE ([playerName])

для ранжирования с разбивкой по страницам:

для 24-го балла, я думаю, вам понадобятся все лучшие оценки одного пользователя во всех играх за последние 24 часа. для этого вы будете запрашивать [playername], [updateddatetime] с помощью [gameid].

для игроков между рангами 25-50, я предполагаю, что вы говорите об одной игре и имеете длинный рейтинг, который вы можете пропустить. тогда запрос будет основан на [gameid], [score] и немного на [updateddatetime] для связей.

однопользовательские ряды, вероятно, для каждой игры, немного сложнее. вам нужно будет запросить таблицы лидеров для всех игр, чтобы получить ранг игрока в них, а затем отфильтровать на проигрывателе. вам понадобится [gameid], [score], [updateddatetime], а затем фильтр от игрока.

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

PRIMARY KEY CLUSTERED ([gameId] ASC, [score] DESC, [updatedDateTime] ASC)

для оценки 24-го уровня я думаю, что это может помочь:

CREATE NONCLUSTERED INDEX [player_Idx] 
ON score ([playerName] ASC) 
INCLUDE ([gameId], [score])

запрос dense_rank сортируется, потому что он выбирает [gameId], [updatedDateTime], [score]. см. мой комментарий к некластеризованному индексу выше.

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

также вы можете подумать о разделении таблиц на [gameid].

Ответ 4

Как немного боковины:

Спросите себя, насколько точны и насколько актуальны последние оценки в таблице лидеров?

В качестве игрока мне все равно, если я номер 142134 в мире или номер 142133. Мне все равно, если я побью точный счет моих друзей (но тогда мне нужен только мой счет по сравнению с несколькими другими баллами), и я хочу знать, что мой новый рекорд отправляет меня откуда-то около 142000, где-то около 90000. (Yay!)

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

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

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

Ответ 5

Ваш кластеризованный индекс является составным, поэтому означает, что порядок определяется более чем одним столбцом. Вы запрашиваете ORDER BY Score, который является вторым столбцом в кластерном индексе. По этой причине записи в индексе необязательно находятся в порядке Score, например. Записи

1, 2, some date
2, 1, some other date

Если вы выберите только Score, порядок будет

2
1

который необходимо отсортировать.

Ответ 6

я бы не поместил столбец "score" в кластеризованный индекс, потому что он, вероятно, будет меняться все время... и обновления в столбце, что часть кластерного индекса будет дорогой.