Рейтинг в MySQL, как мне получить максимальную производительность при частых обновлениях и большом наборе данных?

Question

Я хочу сгруппировать рейтинг на очень большой таблице, я нашел пару решений для этой проблемы, например. в this post и других местах в Интернете. Однако я не могу понять сложность этих решений в худшем случае. Конкретная проблема состоит из таблицы, в которой каждая строка имеет несколько точек и ассоциированное имя. Я хочу иметь возможность запрашивать ранговые интервалы, такие как 1-4. Вот некоторые примеры данных:

name | points 
Ab  14 
Ac  14 
B  16 
C  16 
Da  15 
De  13 

С этими значениями следующего «рейтингом» создано:

Query id | Rank | Name 
1   1  B 
2   1  C 
3   3  Da 
4   4  Ab 
5   4  Ac 
6   6  De 

И это должно быть возможно создать следующий интервал на запрос-идентификаторы: 2-5 Давать ранг: 1,3,4 и 4.

В базе данных хранится около 3 миллионов записей, поэтому, если возможно, я хочу избежать решения со сложностью, большей, чем log (n). В базе данных постоянно обновляются и вставляются данные, поэтому эти действия предпочтительно должны выполняться с учетом сложности log (n). Я не уверен, что это возможно, хотя и я пробовал обернуть вокруг себя его в течение некоторого времени. Я пришел к выводу, что бинарный поиск должен быть возможен, но я не смог создать запрос, который делает это. Я использую сервер MySQL.

Я расскажу о том, как может работать псевдокод для фильтрации. Во-первых, необходим индекс (точки, имя). В качестве вклада вы получаете fromrank и tillrank. Общее количество записей в базе данных - n. Псевдокод должен выглядеть примерно так:

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

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

Answer 1

Вам необходима хранимая процедура, чтобы иметь возможность вызвать это с параметрами:

CREATE TABLE rank (name VARCHAR(20) NOT NULL, points INTEGER NOT NULL); 

CREATE INDEX ix_rank_points ON rank(points, name); 

CREATE PROCEDURE prc_ranks(fromrank INT, tillrank INT) 
BEGIN 
    SET @fromrank = fromrank; 
    SET @tillrank = tillrank; 
    PREPARE STMT FROM 
    ' 
    SELECT rn, rank, name, points 
    FROM (
    SELECT CASE WHEN @cp = points THEN @rank ELSE @rank := @rn + 1 END AS rank, 
      @rn := @rn + 1 AS rn, 
      @cp := points, 
      r.* 
    FROM (
     SELECT @cp := -1, @rn := 0, @rank = 1 
     ) var, 
     (
     SELECT * 
     FROM rank 
     FORCE INDEX (ix_rank_points) 
     ORDER BY 
      points DESC, name DESC 
     LIMIT ? 
     ) r 
    ) o 
    WHERE rn >= ? 
    '; 
    EXECUTE STMT USING @tillrank, @fromrank; 
END; 

CALL prc_ranks (2, 5); 

Если вы создаете индекс и силу MySQL использовать его (как в моем запросе), то сложность запроса будет не зависит от количества строк, это будет зависеть только от tillrank.

На самом деле это займет последние tillrank значений из индекса, выполнить некоторые простые вычисления на них и отфильтровать первые fromrank значений.

Время, которое вы можете видеть, зависит только от tillrank, оно не зависит от количества записей.

Я только что проверил в на 400,000 строк, он выбирает ряды от 5 до 100 в 0,004 секунд (то есть, мгновенно)

Важно: это работает только если вы сортировать по именам в DESCENDING порядке.MySQL не поддерживает DESC в индексах, это значит, что points и name необходимо сортировать в одном заказе для INDEX SORT для использования (либо ASCENDING, либо оба DESCENDING). Если вы хотите быстро ASC сортировать по name, вам нужно будет сохранить минус точек в базе данных, а также изменить знак в статье SELECT.

Вы также можете удалить name из индекса на всех, и выполнить окончательную ORDER «ИНГ без использования индекса:

CREATE INDEX ix_rank_points ON rank(points); 

CREATE PROCEDURE prc_ranks(fromrank INT, tillrank INT) 
BEGIN 
    SET @fromrank = fromrank; 
    SET @tillrank = tillrank; 
    PREPARE STMT FROM 
    ' 
    SELECT rn, rank, name, points 
    FROM (
    SELECT CASE WHEN @cp = points THEN @rank ELSE @rank := @rn + 1 END AS rank, 
      @rn := @rn + 1 AS rn, 
      @cp := points, 
      r.* 
    FROM (
     SELECT @cp := -1, @rn := 0, @rank = 1 
     ) var, 
     (
     SELECT * 
     FROM rank 
     FORCE INDEX (ix_rank_points) 
     ORDER BY 
      points DESC 
     LIMIT ? 
     ) r 
    ) o 
    WHERE rn >= ? 
    ORDER BY rank, name 
    '; 
    EXECUTE STMT USING @tillrank, @fromrank; 
END; 

Это будет влиять на производительность на больших диапазонах, но вы вряд ли заметите его на небольшом диапазоны.