Содержание к диссертации
Введение
1. Анализ современных методов обработки SQL-запросов в СУБД 10
1.1 Архитектуры параллельных систем 10
1.2 Классификация архитектур параллельных систем баз данных 13
1.3 Масштабируемость параллельных систем обработки данных 16
1.4 Формы параллелизма. Параллельное исполнение операторов языка SQL 18
1.5 Методы поиска субоптимальных алгоритмов исполнения запроса 26
1.6 Основные понятия и обозначения реляционной алгебры 28
Выводы к главе 1 31
ГЛАВА 2. Принципы построения систем для параллельной обработки запросов с использованием избыточности данных 33
2.1 Архитектура системы для параллельного исполнения запросов с использованием избыточного представления информации 34
2.2. Декомпозиция запроса с отображением его в древовидную структуру41
2.3 Доказательства эквивалентности преобразования запросов к запросам, допускающим параллельное исполнение 45
2.4. Исследование возможности параллельного исполнения модифицированных запросов 51
2.5. Априорные оценки времени исполнения запросов 54
Выводы к главе 2 60
ГЛАВА 3. Алгоритмы преобразования запросов для параллельного исполнения 62
3.1 Алгоритм для преобразования запросов с использованием условий фильтрации в инструкции WHERE 63
3.2 Алгоритм для преобразования запроса с агрегирующими функциями и оператором группирования атрибутов 72
3.3 Алгоритм преобразования запроса с использованием инструкции соединения таблиц JOIN 79
3.4 Алгоритмы для преобразования запросов с использованием ограничений на количество кортежей в инструкции SELECT 85
3.5 Алгоритм для преобразования запроса с использованием подзапросов87
3.6 Применение инструкции ORDER BY при параллельном исполнении запроса 93
Выводы к главе 3 95
ГЛАВА 4. Экспериментальное исследование эффективности механизма распараллеливания запросов 96
4.1 Программная реализация распараллеливания SQL-запросов. Структура, особенности реализации, методика выбора алгоритма преобразования .97
4.2 Проектирование информационной структуры базы данных для проведения тестирования 101
4.3 Результаты экспериментального исследования распараллеливания запросов 111
Выводы к главе 4 124
Заключение 125
Литература 127
- Формы параллелизма. Параллельное исполнение операторов языка SQL
- Доказательства эквивалентности преобразования запросов к запросам, допускающим параллельное исполнение
- Алгоритм для преобразования запроса с агрегирующими функциями и оператором группирования атрибутов
- Проектирование информационной структуры базы данных для проведения тестирования
Введение к работе
Актуальность темы:
Проблема повышения производительности систем управления базами данных (СУБД) в настоящее время продолжает оставаться актуальной. Увеличение количества пользователей, работающих с базой данных и возрастание объемов обрабатываемой информации, требует соответствующего повышения быстродействия баз данных для обеспечения приемлемого времени реакции на пользовательский запрос [41].
Эффективной и экономически обоснованной альтернативой однопроцессорным СУБД являются параллельные СУБД, функционирующие одновременно на нескольких процессорах. Применение параллельных СУБД позволяет объединить несколько маломощных машин для получения того же самого уровня производительности, что и в случае одной, но более мощной машины, получая выигрыш в масштабируемости и надежности системы, по сравнению с однопроцессорными СУБД [15].
В настоящее время СУБД используются практически во всех сферах человеческой деятельности, связанных с хранением и переработкой информации. Прогресс, достигнутый в области технологий баз данных, в значительной мере базируется на реляционной модели, предложенной Э. Коддом [57] на рубеже 60-х - 70-х годов XX века. За свою тридцатилетнюю историю реляционные СУБД прошли путь от научно-исследовательских прототипов, наиболее значительными из которых являются System R [18, 43] и Ingres [91, 89], до коммерческих продуктов, способных хранить и обрабатывать терабайты информации. Однако научная и практическая деятельность человека выдвигает все новые масштабные задачи, требующие обработки сверхбольших баз данных.
Анализируя существующие методы работы с данными, можно прийти к выводу, что они не в полной мере отвечают всем предъявляемым к ним в настоящий момент требованиям. Об этом, в частности, свидетельствуют интен сивные научные исследования в области баз данных, проводимые в настоящее время в России и за рубежом [13, 73].
Возникновение сверхбольших баз данных связано с расширением видов и сфер применения СУБД. Примерами новых приложений баз данных являются электронная коммерция [72], электронные библиотеки [14, 63], геоинформационные системы [39], мультимедийные архивы [76], научные базы данных [48, 92].
Сегодня наблюдается повышение спроса к технологиям параллельных и распределенных СУБД со стороны как крупных, так и средних компаний связанное с тем, что этап локальной автоматизации филиалов ими, в основном, успешно пройден. Дальнейшим логическим шагом в направлении развития информационных систем данного класса является создание единой базы данных обеспечивающей возможность оперативного доступа и анализа данных, а также решение специфических для компании (в зависимости от сфер ее деятельности) вопросов [27].
Фактически, единственным известным на сегодняшний день эффективным решением проблемы хранения и обработки сверхбольших баз данных является использование параллельных систем баз данных [61, 47] с репликацией хранящейся информации, обеспечивающих параллельную обработку запросов на многопроцессорных вычислительных системах.
Интенсивные научные исследования в области параллельных СУБД были начаты в 80-х годах. В течение последних двух десятилетий параллельные системы баз данных проделали путь от научно-исследовательских прототипов к полнофункциональным коммерческим продуктам, поставляемым на рынок высокопроизводительных информационных систем. В качестве примеров успешных коммерческих проектов создания параллельных систем баз данных можно привести целый ряд продуктов - DB2 Parallel Edition [11], NonStop SQL [37] и NCR Teradata[21]. Однако стоимость такого специализированного программного обеспечения для данных систем сопоставима, а в некоторых случаях и выше стоимости аппаратной составляющей.
Подобные системы объединяют сотни процессоров и жестких дисков и способны обрабатывать базы данных в десятки терабайт. Тем не менее, в области параллельных систем баз данных до сих пор остается ряд направлений, требующих дополнительных научных исследований [97, 10]. Одно из них -дальнейшее развитие методов оптимизации запросов для исполнения в составе параллельных и распределенных систем баз данных. Кроме того, многими исследователями справедливо указывается на ограничения в масштабируемости большинства существующих параллельных баз данных из-за ограничений, присущих архитектуре систем, поддерживающих их работу [20]. При большом количестве процессоров в системах такого рода начинают возникать конфликты доступа к разделяемой памяти, что может привести к серьезной деградации общей производительности системы [95]. В соответствии с этим реальная масштабируемость так называемых SMP систем ограничивается 32 процессорами [98].
Как указывается в одном из отчетов, написанным ведущими специалистами в области систем управления базами данных, о направлениях исследований в области развития баз данных [46], в ближайшем будущем крупные организации будут располагать базами данных объемом, превышающим один петабайт.
В случае реализации возможности использования стандартного программного обеспечения для широко масштабируемых массово-параллельных архитектур существенно сокращается общая стоимость решения. В качестве таких систем можно рассматривать набор существующих серверов СУБД, входящих в состав высокоскоростной локально-вычислительной сети предприятия, изначально не использующих параллельной обработки данных. Использование их ресурсов для параллельной обработки отношений позволит отказаться от приобретения дорогостоящих программно-аппаратных конфигураций.
Все известные на сегодняшний день подходы к параллельной обработке запроса основываются на разделении нагрузки между узлами системы в средней и конечной стадии формирования плана исполнения запроса. Учет особенностей параллельной обработки запроса уже в начальной стадии компиляции позволяет достичь ряда преимуществ. В частности, упрощается процедура разработки программного обеспечения для параллельной обработки запроса, обеспечивается работа в составе гетерогенных СУБД, дальнейшая обработка запроса допускает использование уже известных методов параллельного вычисления. Таким образом, актуальность темы диссертации обуславливается отсутствием методов и программного обеспечения для обеспечения параллельной обработки запросов в начальной стадии компиляции.
Диссертационная работа выполнена в рамках научного направления Воронежского государственного технического университета - «Вычислительные системы и программно-аппаратные электротехнические комплексы».
Цель работы:
Целью работы является разработка методов параллельного исполнения SQL-запросов в гетерогенных архитектурах для повышения производительности распределенных СУБД.
Задачи исследования:
Исходя из указанных целей исследования, его основными задачами являются:
1. Выполнить анализ современных архитектур СУБД и методов, применяемых в них для параллельного исполнения SQL-запросов, обобщить анализ современного состояния исследований в области применения методов параллельной обработки запросов.
2. Разработать эффективные методы распараллеливания запросов в гетерогенных средах с доказательством их корректности.
3. Разработать алгоритмы и программные средства для параллельного исполнения SQL-запросов, обеспечить их совместимость с существующими СУБД.
4. На основе полученных результатов реализовать систему для распараллеливания запросов и провести вычислительный эксперимент, используя разработанные методы и алгоритмы. Методы исследования:
При выполнении работы использованы методы булевой алгебры, реляционной алгебры, имитационного моделирования, математической статистики, теории графов, элементы математического анализа, элементы системного анализа.
Научная новизна работы:
В результате проведенного исследования были получены результаты, характеризующиеся научной новизной:
• метод параллельного исполнения SQL-запросов, ориентированный на использование источников данных, не поддерживающих параллелизм в гетерогенных средах, отличительной особенностью которого является динамическое разделение отношений запроса на диапазоны обработки;
• алгоритм нахождения точек разделения отношений на отношения с равными кардинальными числами, отличающийся использованием статистических данных по атрибутам таблиц, и позволяющий ускорить вычисление точек разделения на основе информации предыдущих итераций;
• априорные оценки эффективности распараллеливания запросов, отличающиеся учетом особенностей исполнения запросов в гетерогенных системах с репликацией данных, и позволяющие быстро оценить целесообразность применения созданного метода распараллеливания SQL-запросов на этапе конфигурирования системы;
• структура программного обеспечения препроцессора СУБД, отличающегося возможностью распараллеливания SQL-запросов и обеспечивающего ускорение их обработки средствами СУБД, не ориентированных на параллельное исполнение.
Практическая значимость работы.
Практическая значимость работы заключается в создании специального программного обеспечения, обеспечивающего распараллеливание SQL-запросов до начала их исполнения в гетерогенных СУБД, а также алгоритмов рационального выбора атрибута разделения отношений.
Реализация и внедрение результатов работы. Теоретические и практические результаты работы реализованы в специальном программном комплексе исполнения аналитических запросов в рамках системы автоматизации предприятия. С его использованием разработана программа "Учет потребления электроэнергии абонентами юридическими лицами", которая внедрена в практическую деятельность ОГУП "Западные межрайонные электрические сети" (г. Елец) и зарегистрирована в Государственном фонде алгоритмов и программ [31].
Апробация работы:
Основные результаты работы докладывались и обсуждались на Международной научно-практической конференции «Единое информационное пространство» (Днепропетровск, 2003); ИХ - X Международных открытых научных конференциях «Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях» (Воронеж, 2003-2005); XI Всероссийской научно-методической конференции «Телема-тика 2004» (Санкт-Петербург, 2004); II Всероссийской научно-технической конференции «Вузовская наука - региону» (Вологда, 2004); VIII Международной научно-практической конференции «Актуальные проблемы информатики и информационных технологий» (Тамбов, 2004).
Публикации:
Основные результаты диссертации опубликованы в 11 научных работах. Список работ включен в список литературы.
Структура и объем работы:
Работа состоит из введения, четырех глав, заключения, списка литературы, включающего в себя 101 наименование и трех приложений. Основная часть работы изложена на 137 страницах, содержит 32 таблицы и 24 рисунка.
Формы параллелизма. Параллельное исполнение операторов языка SQL
Межтранзакционный параллелизм подразумевает параллельное выполнение множества независимых транзакций над одним и тем же набором данных. Данный вид параллелизма присутствует уже в однопроцессорных системах в виде так называемого многопользовательского режима и основан на перекрытии задержек ввода-вывода. Межтранзакционный параллелизм позволяет существенно увеличить суммарную производительность систем баз данных в режиме OLTP. Данный вид параллелизма также должен поддерживаться и в параллельной системе баз данных (наряду с внутритранзакцион-ным параллелизмом).
Внутритранзакционный параллелизм предполагает параллельное выполнение отдельной транзакции. Этот вид параллелизма может быть реализован либо в форме межзапросного параллелизма, либо в форме внутриза-просного параллелизма.
Межзапросный (межоператорный) параллелизм предполагает параллельное выполнение отдельных SQL-операторов, принадлежащих одной и той же транзакции. Степень межзапросного параллелизма, однако, ограничена как количеством SQL-операторов (запросов), составляющих данную транзакцию, так и ограничениями предшествования между отдельными SQL-операторами. Межзапросный параллелизм не поддерживается большинством современных СУБД, так как это потребовало бы от программиста явной спецификации межзапросных зависимостей с помощью некоторых специальных языковых конструкций. Однако далее в работе мы разовьем этот подход и покажем, как можно использовать данный вид параллелизма для распределенного исполнения запросов. Будет показано, каким образом можно выделять отдельные SQL-операторы и преобразовывать их к набору SQL-инструкций, которые можно исполнять параллельно.
Внутризапросный (внутриоператорный) параллелизм предполагает параллельное выполнение отдельного SQL-оператора (запроса). Данная форма параллелизма характерна для реляционных систем баз данных. Это обусловлено тем, что реляционные операции над наборами кортежей по своей природе хорошо приспособлены для эффективного распараллеливания. Внутри-запросный параллелизм реализуется оптимизатором запросов прозрачным для пользователя образом [51]. Для каждого запроса оптимизатор генерирует план выполнения запроса, который представляется в виде дерева (ациклического ориентированного графа), узлы которого соответствуют реляционным операциям, дуги - потокам данных между операциями, а в качестве листьев фигурируют отношения [40, 8]. Внутризапросный параллелизм может реали-зовываться либо в виде межоперационного параллелизма, либо в виде внут-риоперационного параллелизма.
Межоперационный параллелизм предполагает параллельное выполнение реляционных операций, принадлежащих одному и тому же плану запроса. Межоперационный параллелизм может реализовываться либо в виде горизонтального параллелизма, либо в виде вертикального параллелизма.
Горизонтальный (кустовой) параллелизм предполагает параллельное выполнение независимых поддеревьев дерева, представляющего план запроса. Основная проблема, связанная с кустовым параллелизмом, заключается в том, что очень трудно обеспечить, чтобы два подплана одного плана начали генерировать выходные данные в правильное время и в правильном темпе. При этом правильное время далеко не всегда означает одинаковое время, например для входных потоков операции хеш-соединения, а правильный темп далеко не всегда означает одинаковый темп, например для случая, когда входные потоки соединения слиянием имеют различные размеры [67]. В силу указанных причин кустовой параллелизм редко используется на практике. Следует заметить, что в случае, когда удается разбить план запроса на поддеревья, сосредоточив в них основные вычислительные затраты, такой подход является перспективным.
В научных публикациях кустовой параллелизм исследовался главным образом в контексте оптимизации запросов с мультисоединениями [55, 62].
Вертикальный (конвейерный) параллелизм предполагает организацию параллельного выполнения различных операций плана запроса на базе механизма конвейеризации. В соответствие с данным механизмом между смежными операциями в дереве запроса организуется поток данных в виде конвейера, по которому элементы данных (гранулы) передаются от поставщик к потребителю. Традиционный подход к организации конвейерного параллелизма заключается в использовании абстракции итератора для реализации операций в дереве запроса [8, 67]. Подобный подход впервые был использован при реализации System R [86] и получил называние синхронного конвейера. Основным недостатком синхронного конвейера является блокирующий характер операций конвейерной обработки отдельных гранул. Если некоторая операция задерживается с обработкой очередной гранулы данных, то она блокирует работу всего конвейера. Для преодоления указанного недостатка может быть использован асинхронный конвейер, в котором поставщик и потребитель работают независимо друг от друга, а данные передаются через некоторый буфер. Поставщик помещает производимые гранулы в буфер, а потребитель забирает гранулы из данного буфера в соответствующем порядке. При этом необходимо определенное управление потоком данных, которое препятствовало бы переполнению указанного буфера в случае, когда потребитель работает медленнее, чем поставщик. Подобный подход был использован в параллельной СУБД Volcano [66] и в распределенной СУБД R [77]. Различные механизмы реализации синхронных и асинхронных конвейеров в контексте распределенных баз данных были исследованы в работе [93]. Следует отметить, что степень конвейерного параллелизма в любом случае ограничена количеством операций, вовлекаемых в конвейер. При этом для реляционных систем баз данных длина конвейера редко превышает 10 операций. Поэтому для достижения более высокой степени распараллеливания наряду с конвейерным параллелизмом необходимо использовать внутриоперационный параллелизм.
Внутриоперационный параллелизм реализуется в основном в форме фрагментного параллелизма. Фрагментный параллелизм предполагает фрагментацию (разбиение на непересекающиеся части) отношения, являющегося аргументом реляционной операции [15]. Одиночная реляционная операция выполняется в виде нескольких параллельных процессов (агентов), каждый из которых обрабатывает отдельный фрагмент отношения. Получаемые результирующие фрагменты сливаются в общее результирующее отношение.
В реляционных системах баз данных фрагментация подразделяется на вертикальную и горизонтальную [15]. Вертикальная фрагментация подразумевает разбиение отношения на фрагменты по столбцам (атрибутам). Горизонтальная фрагментация подразумевает разбиение отношения на фрагменты по строкам (кортежам). Практически все параллельные СУБД, поддерживающие фрагментный параллелизм, используют только горизонтальную фрагментацию.
Доказательства эквивалентности преобразования запросов к запросам, допускающим параллельное исполнение
В разделе 2.4. показано, что подзапросы такого типа могут исполняться параллельно на машинах произвольной архитектуры, поэтому все получившиеся подзапросы в дереве разбора запроса могут быть вычислены независимо и параллельно. Следует заметить, что в общем случае дальнейшее вычисление запроса согласно дереву разбора можно проводить только при получении результатов всех нижестоящих в иерархии подзапросов и выражений.
Исходя из вышеизложенного замечания, можно сформулировать цели, которые должны достигаться посредством эквивалентных преобразований запросов [22]: 1. Правило преобразования из исходного запроса должно формировать новый запрос, содержащий априорно заданное число некоррелированных подзапросов. 2. Полученные подзапросы должны обладать приблизительно равной стоимостью исполнения, так как дальнейшее вычисление запроса возможно только после вычисления соответствующих подзапросов, и в случае существенного превышения времени исполнения одного подзапроса над остальными, друге узлы системы (не занятые вычислением подзапроса) могут простаивать. Таким образом, преобразования запроса должно контролировать баланс нагрузки между узлами системы путем соответствующего формирования подзапросов. 3. На верхних уровнях дерева разбора запроса преобразование должно оставлять наиболее «дешевые» операции. Под термином «дешевые» здесь подразумеваются операции, для реализации которых не требуется обработки большого количества записей, так как, к примеру, при их вычислении уже будет невозможно воспользоваться информацией содержащейся в индексах. 4. Преобразование, по возможности, не должно увеличивать объем отношений, получающихся при вычислении подзапросов для того, чтобы исключить передачу больших объемов данных между узлами системы. Значительный объем передачи может серьезно замедлить исполнение запроса и уменьшить выигрыш от параллельной обработки. Очевидно, что в общем случае существует больше одного правила для эквивалентного преобразования запроса, которые могут его подготавливать для параллельного исполнения, и при выборе различных правил можно добиваться различной итоговой скорости исполнения запроса. Детали реализации алгоритма выбора преобразования запроса будут обсуждаться в главе 3. Таким образом, препроцессор параллельного запроса должен, по заданному дереву запроса, формировать набор деревьев для эквивалентных запросов. В этих деревьях запроса должно содержаться необходимое количество поддеревьев, исполнение которых возможно проводить параллельно. Из этих деревьев, на основе оценки эффективности вычисления [8,87], выбирается дерево, согласно которому исполнение запроса будет выполнено с наименьшими накладными расходами. 2.3 Доказательства эквивалентности преобразования запросов к запросам, допускающим параллельное исполнение В этом разделе мы проведем доказательства для методов преобразования запросов, пригодных для параллельного исполнения в интерпретации раздела 2.2. Рассмотрим следующий запрос: Без ограничения общности можно считать, что условие инструкции WHERE носит произвольный характер. Обозначим его за L - фиксированное логическое выражение, вычислимое для каждого кортежа из R. Также, отношение R может не являться базовым, а быть получено в результате какой-либо операции (например - 0 соединения). Предположим, что в отношении R присутствует атрибут А, по которому мы будем проводить разделение, a Amin и Атах - минимальное и максимальное значение атрибута на всем отношении, соответственно. Мы не накладываем никаких ограничений на отсутствие вхождения атрибута А в выражение L, более того, если в нем присутствуют явные ограничения значений атрибута, то их целесообразно использовать в качестве значений Amin или Атт. Предположим, что нам необходимо получить п запросов для парал-лельного исполнения. Тогда выберем п-\ произвольную точку из отрезка Mmm/m-x ]» обозначая их как А,, и полагая, что Л = Атт и А„ = Атах. Пусть для всех точек Ai выполнены следующее два условия: Вообще говоря, преобразование (5), как это показано в [8], справедливо для множеств, а не для мультимножеств. Покажем, что при выполнении условия: данный закон остается справедливым и для мультимножеств. Более того, условие (6) является необходимым и достаточным для справедливости преобразования (5) для мультимножеств.
Отношение, представляющее собой результат вычисления левой части (5) состоит из кортежей R, для которых справедливо условие CorD. Пусть количество таких кортежей равно к. Правая часть (5) состоит из тех кортежей R, для которых справедливо условие С или тех кортеже, для которых справедливо условие D. Пусть количество таких записей равно / и т соответственно. Тогда, если кортеж находится в левой части (5), то он находится и в правой части (5), так как для него либо условие С, либо условие D будут истинны. Если кортеж находится в правой части (5), то истинно либо условие С, либо условие D, что влечет истинность выражения CorD. Поскольку ac(R)f]o-n(R) = , то С и D не могут принимать истинное значение для одного и того же кортежа, следовательно l + m = k .
Предположим противное o-(.(R)f]crl)(R) Ф 8 - это означает, что существует не менее одного кортежа, для которого crc(R) и ап(К) истинно одновременно. Предположим, что отношение R состоит из одного такого кортежа, тогда слева в равенстве (5) будет отношение, состоящее из одного кортежа, а справа будет отношение, состоящее их двух кортежей. Получили противоречие.
Алгоритм для преобразования запроса с агрегирующими функциями и оператором группирования атрибутов
Данный метод применим для запросов, в которых отсутствует инструкция GROUP BY. При этом в запросе допускается наличие нескольких таблиц и их соединения, применение оператора сортировки ORDER BY.
Поиск атрибута (атрибутов) разделения запросов целесообразно производить в следующем порядке: 1. В случае присутствия инструкции ORDER BY, целесообразно проводить разбиение по первому (первым) атрибутам данной инструкции (если они входят в подходящий индекс) и присутствуют в условии фильтрации WHERE. 2. Разделение по диапазонам на основе индекса, по которому производится фильтрация в инструкции WHERE. Применять такое разбиение целесообразно, так как в любом случае будет производиться отбор или фильтрация по атрибуту при выполнении запроса. 3. В случае присутствия инструкции ORDER BY, разделение по диапазонам по первому (первым) атрибутам данной инструкции, если отсутствуют подходящие атрибуты в инструкции фильтрации WHERE. 4. Разделение по диапазонам на основе индекса по атрибуту, из отношения, используемого в запросе. Замечание 1: В случае наличия понятия кластерного индекса в системе, целесообразно выбирать его атрибуты, на основе которых он построен, для разделения обрабатываемого отношения на диапазоны. Замечание 2: Выбор определенного метода разделения возможен только тогда, когда для этого есть подходящий атрибут (используется в запросе, или присутствует в базе - в зависимости от метода). Будем называть атрибут подходящим, если в результате его выбора в качестве параметра для алгоритма разделения, возможно сокращение объемов отношений, обрабатываемых на каждом из узлов системы, т.е. по значениям атрибута построен индекс и количество различных значений атрибута позволяет равномерно разделить отношение на заданному количеству серверов. Возможны случаи, когда атрибут будет подходящим, но выбор его не является оптимальным - например, если существует другой атрибут, который обеспечивает более эффективные условия фильтрации (т.е. в результате фильтрации по этому атрибуту итоговое количество кортежей в отношении будет меньше). В таком случае, необходимо производить выбор атрибута, обеспечивающего наилучшие условия фильтрации.
В другом случае возможна ситуация, когда дискретность изменения значений атрибута не позволяет обеспечить загрузку всех доступных ресурсов распределенной системы, даже если условие фильтрации является эффективным. К примеру, если у нас есть целочисленный атрибут, принимающий значения в диапазоне от 10 до 15, то мы можем параллельно проводить исполнение запроса не более чем на 6 серверах системы. В этом случае целесообразно проводить разделение по нескольким атрибутам отношения. Для эффективного разделения отношений по нескольким атрибутам, они должны входить в единый индекс в качестве его первых ключей. Тогда система сможет разделять отношения на основе нескольких атрибутов.
Обозначая за zj - диапазон изменения значений і-го атрибута с минимальным шагом дискретности получаем, что количество серверов, которые можно задействовать при исполнении запроса будет равно 11z, , где IN количество ключей в индексе. Таким образом, наличие двух-трех ключей в индексе должно обеспечить возможность полной загрузки системы, даже при малых значениях z,. Создание таких индексов остается за разработчиком базы данных. Выбор, в качестве атрибутов разделения атрибутов не являющихся первыми ключами одного индекса, не обеспечивает задания эффективных условий фильтрации кортежей [8].
Замечание 3: В случае присутствия в запросе инструкции ORDER BY, и выбора в качестве способа разделения алгоритма №2 или №4, потребуется проведение дополнительной сортировки полученного отношения, согласно условиям инструкции ORDER BY (о способе сортировки, который можно применить в данном случае, см. 3.6.). Эти способы параллельного исполнения требуют больше накладных расходов, чем те, которые основываются на алгоритмах № 1 и № 3.
Замечание 4: В случае отсутствия инструкции ORDER BY существует возможность начать формирование и возврат результатов итогового отношения после завершения исполнения запроса хотя бы одним из серверов. Естественно, полное формирование отношения возможно только по окончании обработки запросов всеми серверами распределенной системы. Более того, если был выбран способ разделения запроса между серверами согласно алгоритму №1 или алгоритму №3, то имеется возможность формирования и возврата итогового результата возвращенного і-м сервером, если сервера [1..І-1] уже вернули свои наборы данных. однако, в случае значительного отклонении распределения атрибута LSHIPDATE от нормального, возможен серьезный дисбаланс в загрузке системы. В случае присутствия инструкции ORDER BY программе пришлось бы дожидаться окончания работы самого последнего сервера для того, чтобы начать формирование итогового отношения (на самом деле инструкция ORDER BY вполне допустима и в рассматриваемом примере). Таким образом, обеспечение равномерной загрузки серверов распределенной системы является актуальной задачей для повышения скорости исполнения запроса. С целью повышения точности распределения баланса загрузки, будем производить выбор точек разбиения хк с учетом статистической информации, собранной по значениям атрибута. Для этого мы введем понятие гистограммы и покажем метод оценки плотности распределения атрибута.
Гистограмма для произвольного атрибута представляет собой кусочно-постоянную линейную функцию. Каждой части гистограммы соответствуют два значения с, - количество кортежей, попадающих в столбец гистограммы, dt - диапазон изменения значения (за d0 обозначим минимально возможное значение атрибута, который включен в статистическую информацию). Введем функцию плотности распределения кортежей p(c,d) = c/d. Основное предположение, которое используется при работе с гистограммами и оценки числа кортежей в выборке заключается в том, что распределение кортежей внутри одной полосы гистограммы носит равномерный характер. Существует несколько разновидностей алгоритма построения гистограмм по исходным данным, но все они полагают, что после построения гистограммы внутри отдельной полосы распределение значений остается равномерным (или близким к нему).
Проектирование информационной структуры базы данных для проведения тестирования
В данный момент поддерживаются только индексы, состоящие из значений одного атрибута, или по значениям первого атрибута индекса, состоящего из нескольких атрибутов. Информация о статистическом распределении значений индекса может предоставляться как самой СУБД, так и собираться какими-либо сторонними средствами.
Подчеркнем важность поддержания данных таблиц в актуальном состоянии. Если в таблице _sysstatindinfo оказывается информация, не соответствующая текущему состоянию базы данных, то это может привести к значительному дисбалансу при распределении нагрузки между серверами системы. Отметим, что система может успешно пользоваться данными из _sysstatindinfo, если изменения с момента последнего сбора статистики были незначительны. Однако если значения атрибутов MinValue и MaxValue отношения _sysstatind будут содержать не актуальную информацию, то в этом случае система будет возвращать искаженные результаты выполнения SQL-запроса. Поэтому система добавления информации в базу данных должна заботиться о поддержании данных атрибутов в актуальном состоянии. Это не является серьезной проблемой даже при удалении данных, так как по атрибутам исходного отношения построены индексы.
После построения списка «потенциальных кандидатов для атрибута разбиения» на его основе формируется список «кандидатов для атрибута разбиения». Формирование данного списка производится путем исключения из первичного списка атрибутов, по которым не возможно разделить отношение, согласно значениям атрибута, на заданное количество узлов.
В соответствии с видом запроса сформированный список «кандидатов для атрибута разбиения» подается на вход соответствующих алгоритмов преобразования запроса. После чего, проводится оценка эффективности исполнения модифицированных запросов. В данной реализации программы используется процедура получения оценки, реализованная в СУБД для которой производится подготовка запроса к параллельному исполнению. На основании этой оценки осуществляется выбор наиболее эффективного алгоритма параллельного исполнения запроса на основе одного из атрибутов отношений находящегося в списке «кандидатов для атрибута разбиения».
После этого производится преобразование запроса к набору запросов, пригодному для параллельного исполнения и собственно осуществляется само исполнение запросов на узлах системы. Исполнение запроса осуществляется путем отправки модифицированного запроса на узел каждой из систем, и последующего получения результата его исполнения.
По окончанию исполнения запроса создается файл, содержащий результаты исполнения запроса. В файле группируются результаты исполнения запросов с различных узлов системы. Появление данного выходного файла является сигналом окончания исполнения запроса.
Для проведения экспериментального исследования методов параллельного исполнения запросов в СУБД разработаем схему данных, определим алгоритмы заполнения данных и выберем ряд запросов, которые необходимо исполнить. За основу был взят подход, на основе которого разрабатывалась методика для проведения теста совета Transaction Processing Performance Council - TPC-D [94]. Членами подкомитета, который отвечает за разработку методики тестирования TPC-D, являются следующие организации: Compaq, Data General, Dell, EMC, HP, IBM, Informix, Microsoft, NCR, Oracle, Sequent, SGI, Sun, Sybase, Unisys и др. В отличие от многих других тестов, которые сосредоточены на небольших и средних транзакциях, тест TPC-D позиционируется его создателями как система, эмулирующая работу широкого ряда программ поддержки принятия решений (Decision Support Systems), которые оперируют продолжительными по времени запросами и обрабатывают большие массивы данных. В запросах теста отражены обобщенные реальные вопросы, которые требуется решать в системах данного класса. Опишем алгоритмы, которые использовались при генерировании содержимого отношений экспериментальной базы данных: Обозначение random означает равномерное распределение величин в указанном диапазоне; Обозначение unique within [х] означает произвольное значение из множества между 1 и х, уникальное для атрибута; Обозначение random value [х .. у] означает равномерное распределение между величинами х и у включительно, со средним значением (х+у)/2, и той же точностью, что х и у; Обозначение random string [list_name] представляет собой строку, случайно выбранную из списка строк, приведенного в приложении 2 с равной вероятностью; Обозначение text + [text, х] представляет собой строку, полученную соединением подстроки text, символа "# ", и строкового представления числа х; Обозначение random a-string [х] представляет собой строку длиной х состоящую из случайно сгенерированной алфавитно-цифровой последовательности, с алфавитом не менее 64 символов; Обозначение random v-string [х] представляет собой строку, состоящую из случайно сгенерированной алфавитно-цифровой последовательности, с алфавитом не менее 64 символов. Длина строки случайна и находится в пределах [0.4 х .. 1.6 х]. Она округляется вверх до следующего целого числа; Обозначение date представляет собой строку, состоящую из 4-х цифр года, 2-х цифр месяца и 2-х цифр дня. Дата должна лежать в пределах от 1992-01-0 Ідо 1998-12-31; - Обозначение phone number представляет собой строковое представление телефонного номера сгенерированного согласно примечанию 1; Обозначение text stringfx] обозначает строку, сгенерированную соглас но примечанию 2. Длина строки случайна и находится в пределах [0.4 х .. 1.6 х] округленная вверх до следующего целого числа. Опишем отношения, составляющие экспериментальную базу данных (табл. 6-13). Тип данных соответствует обозначению типа атрибута отношения принятого в Microsoft SQL Server.
