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

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

0 голосов
/ 16 февраля 2009

Я хочу сгруппировать ранжирование на очень большой таблице, я нашел пару решений этой проблемы, например. в этом посте и других местах в сети. Однако я не могу понять сложность этих решений в худшем случае. Конкретная проблема состоит из таблицы, в которой каждая строка имеет количество точек и имя, связанное с ними. Я хочу иметь возможность запрашивать интервалы ранга, такие как 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 и тилранк. Общее количество записей в базе данных составляет n. Псевдокод должен выглядеть примерно так:

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

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

1 Ответ

2 голосов
/ 16 февраля 2009

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

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;

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

...