Введение
Сейчас очень популярна тем оптимизации работы с различными СУБД. На многочисленных форумах ведутся дискуссии о «самой лучшей СУБД в мире», но часто все это перетекает в необоснованные выкрики о том, что «я познал смысл жизни и понял, что самое лучшее хранилище данных — Х».
Да, несомненно, сейчас мы можем наблюдать активное развитие NoSQL решений, которые позволяют делать многое. Но данная статья не о них. Так вышло, что я сменил работу и в нагрузку мне достался один очень интересный проект на связке php+MySQL. В нем есть много хороших решений, но он писался без расчёта на большую аудиторию. За несколько лет существования количество активных пользователей начало приближаться к числам с 7 нулями. Так как проект представляет из себя подобие социальной сети с игровыми элементами, то таблица с пользователями оказалась не самой «тяжёлой» из всех. В наследство мне достались таблицы с десятками миллионов вещей пользователей, личных сообщений, биллинговыми записями и т. п. Проект начали рефакторить, разбивать на несколько серверов и достигли значительных результатов. Сейчас все стабильно.
Но недавно мне на почту прислали новую задачу. Суть заключалась в сборе статистики. Проанализировав требования я понял, что для выполнения достаточно написать один единственный запрос, выполняющий 3 INNER JOIN'а на таблицы, размеры которых впечатляли. Каждая таблица в среднем содержала 40 миллионов записей. Получается, что временная таблица состояла бы из 4*4*4*10^21 = 64*10^21 записей. Это колоссальная цифра. И загружать СУБД таким запросом для сбора статистики — непозволительная роскошь.
Далее, собственно, я и хочу представить решение данной абстрактной задачи, которое пришло мне в голову, когда я вспоминал занятия по информатике на первом курсе университета.
(в проекте используется СУБД MySQL, но алгоритм не имеет каких-либо специфических особенностей)
Что такое бинарный поиск
Думаю, что многие из вас писали лабораторные работы, посвящённые поиску элемента в массиве с использование бинарного алгоритма. Постараюсь кратко изложить его суть.
Пусть у нас имеется отсортированный массив из n элементов:
Первый элемент массива = 1
Последний элемент массива = n
Нам необходимо найти индекс элемента со значением f.
Каждый шаг заключается в том, что мы вычисляем середину массива:
Середина массива = round(Первый элемент + Последний элемент)/2
Затем вычисляем значение этого элемента и проверяем больше или меньше полученное значение в сравнении с искомым f. Диапазон поиска уменьшается в 2 раза:
Если <значение середины> > f, то
Последний элемент массива = значение середины
Иначе
Первый элемент массива = значение середины
Данные шаги повторяются пока не наступит одно из условий:
- Модуль разности значений середины и f меньше некоторого эпсилон(где эпсилон, некоторая погрешность)
- Количество итераций превысило значение log2(количество элементов в массиве)
Думаю, суть ясна. Таким образом мы значительно ускоряем поиск нужного элемента за счёт сокращения диапазонов поиска, но жертвуем некоторой точностью вычислений (для статистики это не критично, если пару элементов из миллионов не будут учтены. В противном случае необходимо сделать эпсилон нулевым и завершать поиск только после достижения последнего уровня дерева).
Переходим к практике
Итак, предположим, что нам необходимо сделать INNER JOIN на 3 таблицы, а затем задать условие «столбец х в диапазоне между 10 и 20». Причём столбец х не имеет индекса. Это будет очень долго выполнятся. Тут и приходит на помощь это простой способ.
Берем таблицу с этим самым столбцом и применяем на ней бинарный поиск, для поиска диапазона первичных ключей, удовлетворяющих условию 10<=x<=20. Учитывая, что для подобной выборки мы будем использовать только индексы, то очень скоро мы получим нужную пару значений.
Стоит сказать, что бинарный поиск используется для нахождения одного элемента, а не диапазона, но никто не мешает нам найти первый элемент со значением 10 и последний элемент со значением 20. Их первичные ключи и буду ограничениями диапазонов.
С этим диапазоном мы идём снова к нашему запросу, но теперь вместо условия WHERE x >= 10 AND x <= 20 мы пишем WHERE id_x BETWEEN min_id_x AND max_id_x, где min_id_x и max_id_x — значение нижнего и верхнего краёв диапазона, удовлетворяющего условию.
Что мы получаем: теперь мы делаем выборку не по некому столбцу х, а по первичному ключу. Время потраченное на обход одной таблицы сэкономлено. Аналогичную процедуру можно провести с другими условиями в запросе.
Приводить здесь код не вижу смысла, т. к. код бинарного поиска можно найти на википедии, а сам запрос — ничего сверхъестественного.
Выводы
Данный алгоритм позволяет перенести условия с полей без индексов на первичные ключи, что значительно ускоряет работу запроса. Но метод нельзя считать панацеей.
Во-первых, трудно подготовить универсальное решение для всех запросов. В любом случае будет необходимо учитывать детали реализации той или иной таблицы и, как следствие, каждый раз тратить время на оптимизацию.
Во-вторых, данной способ подходит не для всех решений, т. к. строки в таблице должны быть отсортированы в некотором порядке.
