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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.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! времени. Наконец, для поиска экстремума, скажем для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.

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

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

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

Библиография

бинарный управление запрос выборка

1. «Intrusion Detection with Artificial Neural Networks (Anomaly based Intrusion Detection using Backpropagation Neural Networks)», Moazzam Hossain, ISBN 978-3-6392-1038-5, 2010 г.

2. «Snort Cookbook», Angela Orebaugh, ISBN 0596007914, 2005 г.

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 г.

4. «Intrusion Detection System», Frederic P. Miller, ISBN 978-6-1328-6369-0, 2010 г.

Размещено на Allbest.ru