Оптимизировать топ N запросов - PullRequest
Новая
       11

Оптимизировать топ N запросов

4 голосов
/ 11 августа 2011

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

SELECT RESULT_ID FROM RESULTS 
WHERE SOURCE = 1 AND GROUP=2 AND SCORE1 BETWEEN 20 AND 100 
ORDER BY SCORE2 LIMIT 450;

для таблицы innodb с 40 миллионами строк.В запросе может потребоваться отсортировать до 15 миллионов результатов, чтобы получить первые 450. До сих пор я пробовал:

  1. Определение индексов, но они не используются для сортировки, поскольку MySQL игнорирует любые столбцы виндекс после условия диапазона.Поскольку у нас есть несколько столбцов с оценками, мы можем получить условия диапазона по ряду из них, а затем отсортировать по конкретному результату и ограничить набор результатов до верхних 450.
  2. Использование таблиц памяти, но те непри сортировке таких больших результатов он не работает.
  3. Sphinx, но я не уверен, поможет ли он в таких запросах.

Кроме того, существует ли реализация куба OLAP, котораяможно оптимизировать такого рода запросы?

Ответы [ 3 ]

1 голос
/ 12 августа 2011

То, что вы ищете, ИМХО, это способ получить лучших K элементов в (теоретически) бесконечном потоке элементов.

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

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

Немного более формально: дан поток данных q1,.,,, qn, добавьте qj в кучу, если оценка (qj) больше, чем наименьшая оценка в куче.В этом случае наименьший оценочный балл должен быть удален из кучи.

Конкретное решение

У вас есть несколько столбцов баллов, и пользователь может запросить верхние 450 для любой комбинации столбцов, используядиапазон запросов.

Концептуально я хотел бы сделать следующее:

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

Надеюсь, это поможет.

1 голос
/ 12 августа 2011

Вы можете предварительно указать общие диапазоны оценок.Например, вы можете создать несколько типов диапазонов: 

                1          2           3           4
RANGE_50  = { 0..50,    51..100,   101..150,   151..200 }
RANGE_100 = { 0..100,   101..200                        }
RANGE_200 = { 0..200                                    }

Эти типы диапазонов могут быть созданы как столбцы в вашей таблице и должны быть обновлены в соответствии со значением оценка1 .

Тогда вы сможете использовать такие запросы: 

SELECT RESULT_ID FROM RESULTS 
WHERE SOURCE = 1 AND GROUP=2 AND RANGE_100 = 2 
ORDER BY SCORE2 LIMIT 450;
1 голос
/ 11 августа 2011

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

Таким образом, вашему запросу не нужно будет каждый раз просматривать все строки.

...