Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Cybernetics and programming
Reference:

Using a binary search to optimize the query to retrieve data

Milushkov Vitalii Igorevich



197101, Russia, g. Saint Petersburg, Kronverkskii prosp., 49

milushkoff@yandex.ru
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
Other publications by this author
 

 

Received:

20-11-2014


Published:

04-12-2014


Abstract: With the increasing popularity of DBMS its use inevitably begins to demand more and more resources. The first time is possible (and, of course, necessary) to lower the load through optimization of algorithms and / or architecture of the application. However, what if anything that can be optimized is already optimized, and the application still cannot cope with the load? In this article the methods and ways to use binary search to optimize the query to retrieve data are reviewed. Authors giv an overview of php + MySQL and solved the problem of the transfering the queue from fields without indexes to tables with primary keys, which significantly speeds up the query and the database itself. Proposed solution greatly accelerates the search for the desired item by reducing the search range but at the same time sacrificing some accuracy computations. For statistical reasons it is not critical if a few elements of millions will not be taken into account. Otherwise, it is necessary to make and complete epsilon zero search only after reaching the last level of the tree.


Keywords:

data structure, binary search, query optimization, search range, scaling, bisection method, index, primary key, database, DBMS


Введение

С ростом популярности СУБД его поддержка неизбежно начинает требовать всё больших и больших ресурсов[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! времени. Наконец, для поиска экстремума, скажем для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.
Выводы

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

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

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

References
1. «Intrusion Detection with Artificial Neural Networks (Anomaly based Intrusion Detection using Backpropagation Neural Networks)», Moazzam Hossain, ISBN 978-3-6392-1038-5, 2010 g.
2. «Snort Cookbook», Angela Orebaugh, ISBN 0596007914, 2005 g.
3. «A New Host-Based Hybrid IDS Architecture-A Mind Of Its Own (The Know-how Of Host-Based Hybrid Intrusion Detection System Architecture Using Machine Learning Algorithms With Feature Selection)», Murat Topallar, ISBN 978-3-6391-7288-1, 2010 g.
4. «Intrusion Detection System», Frederic P. Miller, ISBN 978-6-1328-6369-0, 2010 g.