Использование бинарного поиска для оптимизации запроса на выборку данных

Милушков Виталий Игоревич аспирант, , Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики 197101, Россия, г. Санкт-Петербург, Кронверкский просп., 49 Milushkov Vitalii Igorevich 197101, Russia, g. Saint Petersburg, Kronverkskii prosp., 49 milushkoff@yandex.ru

Гатчин Юрий Арменакович доктор технических наук доцент, кафедра Проектирования и безопасности компьютерных систем, Санкт-Петербургский национальный исследовательский универси-тет информационных технологий, механики и оптики 197101, Россия, г. Санкт-Петербург, Кронверкский просп., 49 Gatchin Yurii Armenakovich Doctor of Technical Science associate professor of the Department of Computing Systems Design and Safety at Saint Petersburg National Research University of Information Technologies, Mechanics and Optics 197101, Russia, Saint Petersburg, Kronverkskii prosp., 49 gatchin@mail.ifmo.ru Другие публикации этого автора

С ростом популярности СУБД его поддержка неизбежно начинает требовать всё больших и больших ресурсов^[1]. Первое время с нагрузкой можно (и, несомненно, нужно) бороться путём оптимизации алгоритмов и/или архитектуры самого приложения. Однако, что делать, если всё, что можно было оптимизировать, уже оптимизировано, а приложение всё равно не справляется с нагрузкой?

И так, допустим, что оптимизация уже проведена, но приложение всё равно не справляется с нагрузкой. В таком случае решением проблемы, очевидно, может послужить разнесение его по нескольким хостам, с целью увеличения общей производительности приложения за счёт увеличения доступных ресурсов. Такой подход имеет официальное название – «масштабирование» (scale) приложения. Точнее говоря, под «масштабируемостью» (scalability) называется возможность системы увеличивать свою производительность при увеличении количества выделяемых ей ресурсов. Различают два способа масштабирования: вертикальное и горизонтальное. Вертикальное масштабирование подразумевает увеличение производительности приложения при добавлении ресурсов (процессора, памяти, диска) в рамках одного узла (хоста). Горизонтальное масштабирование характерно для распределённых приложений и подразумевает рост производительности приложения при добавлении ещё одного узла (хоста)^[2].

Предположим, что каждая таблица СУБД, в среднем содержала 40 миллионов записей. При этом мы бы использовали 3 INNER JOIN. Получается, что временная таблица состояла бы из 4*4*4*10^21 = 64*10^21 записей. Это колоссальная цифра. И загружать СУБД таким запросом для сбора статистики — непозволительная роскошь.

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

Пусть у нас имеется отсортированный массив из 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 — значение нижнего и верхнего краёв диапазона, удовлетворяющего условию.

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

Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании. Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке.

Пример кода на языке программирования Cи для поиска элемента x в массиве a[n], отсортированного в возрастающем порядке^[2]:

size_t first = 0; /* Первый элемент в массиве */
size_t last = n; /* Элемент в массиве, СЛЕДУЮЩИЙ ЗА последним */
/* Если просматриваемый участок непустой, first<last */
size_t mid;
if (n == 0)
{
/* массив пуст */
}
else if (a^[0] > x)
{
/* не найдено; если вам надо вставить его со сдвигом - то в позицию 0 */
}
else if (a[n - 1] < x)
{
/* не найдено; если вам надо вставить его со сдвигом - то в позицию n */
}
while (first < last)
{
/* ВНИМАНИЕ! В отличие от более простого (first+last)/2, этот код стоек к переполнениям.
Если first и last знаковые, возможен код (unsigned)(first+last) >> 1. */
mid = first + (last - first) / 2;
if (x <= a[mid])
{
last = mid;
}
else
{
first = mid + 1;
}
}

/* Если проверка n==0 в начале опущена - значит, тут раскомментировать! */
if (/*n!=0 &&*/ a[last] == x)
{
/* Искомый элемент найден. last - искомый индекс */
} else
{
/* Искомый элемент не найден. Но если вам вдруг надо его вставить со сдвигом, то его место - last. */
}

Практические приложения метода двоичного поиска разнообразны^[3]:

• Широкое распространение в информатике применительно к поиску в структурах данных. Например, поиск в массивах данных осуществляется по ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом).
• Также его применяют в качестве численного метода для нахождения приближённого решения уравнений.
• Метод бисекции используется для поиска численных решений уравнений^[4].
• Метод используется для нахождения экстремума целевой функции и в этом случае является методом условной одномерной оптимизации. Когда функция имеет вещественный аргумент, найти решение с точностью до ε можно за время log 21 / ε. Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт 1 + log_2N! времени. Наконец, для поиска экстремума, скажем для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.

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

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

Во-вторых, данной способ подходит не для всех решений, т. к. строки в таблице должны быть отсортированы в некотором порядке.