Основная проблема, возникающая в связи с этим, заключается в том, что модель стоимости, которая использовалась при оптимизации, со временем становится неточной, как из-за изменения размеров фрагментов, так и из-за реорганизаций базы данных, проводимых для балансировки нагрузки. Таким образом, задача состоит в том, чтобы определить оптимальные интервалы рекомпиляции/реоптимизации запросов с учетом соотношения затрат на их оптимизацию и выполнение. Критически важной проблемой с точки зрения стратегии поиска является проблема упорядочения соединений, которая является NP-полной от числа отношений [3]. Типичный подход к решению этой задачи — применение динамического программирования [4], которое является детерминированной стратегией. Эта почти исчерпывающая стратегия, гарантирующая нахождение наилучшего плана из всех возможных. Затраты (по времени и памяти) на ее реализацию приемлемы для небольшого числа отношений.
Однако уже для 5−7 отношений такой подход становится слишком дорогостоящим. В связи с этим в последнее время возрос интерес к стратегиям случайного перебора (randomizedstrategy), которые снижают сложность оптимизации, но не гарантируют нахождение наилучшего плана. Стратегии случайного перебора исследуют пространство решений контролируемым образом, в том смысле что оптимизация завершается по исчерпанию заданного для нее бюджета времени. Еще один способ снизить сложность оптимизации — применение эвристических подходов. В отличие от детерминированных стратегий, стратегии случайного перебора позволяют управлять соотношением затрат на оптимизацию и выполнение запросов [5,6].
Одним из способов оптимизации запросов является фрагментация данных. Ее целью является сужение пространства поиска при исполнении запроса. Фрагментация данных допускает разбиение отношения на два илиболее сегмента или фрагмента. Каждый фрагмент может храниться на любом узле базы данных. Принято выделять две базовых стратегии фрагментации данных: горизонтальная фрагментация (ГФ) и вертикальная фрагментация (ВФ). Вертикальная фрагментация — эторазделение атрибутов на группы, горизонтальная фрагментация — разделение отношения на подмножества таким образом, что каждое подмножество содержит полный набор атрибутов. Существует много подходов к фрагментации данных. Одним из них является алгоритм бустрофедона. Алгоритм бустрофедона предназначен для симметричногогоризонтального распределения данных. Данные располагаются вфайлах или таблицах реляционных баз данных.
Над ними выполняетсяоперация слияния нестрого упорядоченных файлов, которой вреляционных базах данных соответствует операция JOIN. Цельраспределения данных — построение параллельных алгоритмов названыхопераций [1,4]. Алгоритм бустрофедона состоит из следующих шагов. На базе исходных файлов (таблиц) формируются индексные файлы (таблицы).Из индексных файлов формируется файл параметров распределения, как их пересечение, и упорядочивается по возрастанию (убыванию) произведений числа записей в классах эквивалентности с одинаковым значением составного ключа. Первые p пар классов эквивалентности последовательно распределяются между p вычислителями (ядрами). Последние p пар классов эквивалентности в обратном порядке последовательно распределяются между p вычислителями. Номер первой записи файла параметров распределения увеличивается, а номер последней записи уменьшается на p. Пункты 3−5 повторяются до тех пор, пока весь файл параметров распределения не будет исчерпан.
Литература
.
Макаров Д.И., Мунерман В. И. Параллельная реализация операции соединения для массовой обработки данных // Системы высокой доступности. — 2012.- Т.8, № 3. — С. 26−28Зыкин С. В. Базы данных. Учебное пособие.
Омск: Изд-во Ом. гос. ун-та, 2008. -;
21 сЛевин Н. А., Мунерман В. И. Алгебраический подход к оптимизации обработки информации. -.
Системы и средства информатики. Спецвыпуск. Математические модели и методы информатики, стохастические технологии и системы. Москва: ИПИ РАН 2005. — c.
279−294.Новосельский.
В.Б. Применение генетических алгоритмов при проектировании распределенных баз данных // Научно-технический вестник информационных технологий, механики и оптики, № 46, 2008. С. 7−13T. I.
baraki and T. K ameda. O n the Optimal Nesting Order for Computing N-Relation Joins. — ACM T.
rans. D atabaseSyst., September 1984, 9(3), pp. 482−502.P.G. Selinger, M.M. Astrahan, D.D. Chamberlin, R.A. Lorie, and T.G. Price. A.
ccess Path Selection in a Relational Database Management System. — P roc. ACM SIGMOD I nt. C.
onf. on Management of Data, Boston, Mass., May 1979, pp. 23−34.Y. Ioannidis and Y.C. Kang. R andomized Algorithms for Optimizing Large Join Queries. — P.
roc. of the ACM SIGMOD Int. C onf. on Management of Data, 1990, pp. 312−321.
