Содержание к диссертации
Введение
Глава 1. Анализ существующих методов построения оптимизаторов запросов 11
1.1. Процесс обработки запросов в СУБД 12
1.2. Анализ процесса оптимизации запросов 17
1.3. Обзор подходов к оптимизации запросов 20
1.3.1. Восходящий алгоритм System R 22
1.3.2. Восходящий расширяемый алгоритм Starburst 26
1.3.3. Нисходящий подход Exodus и Volcano 28
1.3.4. Нисходящий расширяемый подход Cascades 30
1.4. Обзор методов оценки стоимости операции соединения 32
1.4.1. Стоимостная модель Грэфа 32
1.4.2. Стоимостная модель Хэрриса 33
1.4.3. Обзор алгоритмов соединения Мишры и Эйчина 34
1.4.4. Стоимостная модель Шапиро 34
1.5. Выводы 35
Глава 2. Методы повышения эффективности нисходящей стратегии поиска 37
2.1. Анализ нисходящей стратегии поиска 38
2.1.1. Внутреннее представление пространства поиска 38
2.1.2. Алгоритм нисходящей стратегии поиска 41
2.1.3. Пример использования нисходящей стратегии поиска 45
2.1.4. Сравнение алгоритмов нисходящей и восходящей стратегий поиска..46
2.2. Методы поиска оптимального плана на основе нисходящей стратегии ...48
2.2.1. Анализ механизма отсечения групп 48
2.2.2. Метод увеличения стоимости мультивыражения 52
2.2.3. Метод генерации пространства поиска без декартовых произведений..54
2.3. Оценка эффективности разработанных методов поиска оптимального плана на основе нисходящей стратегии 64
2.3.1. Качественный анализ разработанного алгоритма нисходящей стратегии поиска 64
2.3.2. Оценка числа альтернативных деревьев поиска 67
2.3.3. Оценка числа мультивыражений в memo-структуре 73
2.3.4. Оценка преимуществ использования memo-структуры для представления пространства поиска 79
2.3.5. Количественный анализ разработанных методов поиска оптимального плана на основе нисходящей стратегии 81
2.4. Метод оценки стоимости операции соединения 83
2.4.1. В+ индекс и хеш-индекс 84
2.4.2. Соединение методом вложенных циклов 86
2.4.3. Соединение методом сортировки и слияния 89
2.5. Выводы 94
Глава 3. Разработка оптимизатора запросов с нисходящей стратегией поиска 95
3.1. Модель процесса оптимизации запросов 96
3.1.1. Модель логических операций 99
3.1.2. Модель физических операций 102
3.1.3. Модель правил генерации пространства поиска 106
3.1.4. Стоимостная модель 109
3.1.5. Стратегия поиска 111
3.2. Выбор архитектуры оптимизатора запросов 114
3.2.1. Компоненты оптимизатора запросов 114
3.2.2. Входные данные оптимизатора запросов 116
3.2.3. Выходные данные оптимизатора запросов 117
3.3. Разработка модуля поиска оптимального плана 118
3.3.1. Главный цикл оптимизации 120
3.3.2. Структура задач модуля поиска 121
3.3.3. Задачи модуля поиска 121
3.3.4. Применение правил 128
3.3.5. Пример работы модуля поиска 130
3.4. Разработка интерфейса взаимодействия пользователя с системой 133
3.5. Методика использования оптимизатора запросов 135
3.5.1. Назначение методики 135
3.5.2. Процедура оценки времени выполнения запроса 136
3.5.3. Метод оценки параметров стоимостной модели 137
3.5.4. Способы применения методики 138
3.6. Выводы 142
Глава 4. Использование разработанного оптимизатора запросов для анализа эффективности предложенных методов поиска оптимального плана и при разработке программных продуктов компании Сайбико ...143
4.1. Исследование эффективности предложенных методов поиска 144
4.1.1. Описание условий проведения исследований 144
4.1.2. Эффективность методов Ml и М2, реализующих механизм отсечения групп 146
4.1.3. Сравнение механизма отсечения групп и применения эвристик 148
4.1.4. Влияние числа соединяемых таблиц на размер пространства поиска. 149
4.2. Анализ адекватности получаемых результатов 150
4.2.1. Описание запросов теста ТРС-Н 150
4.2.2. Результаты оптимизации запросов с использованием предложенных методов поиска оптимального плана 152
4.3. Использование оптимизатора запросов при разработке СУБД для миникомпьютера Сайбико 156
4.3.1. Механизм использования оптимизатора в структуре СУБД 156
4.3.2. Оценка преимуществ от использования оптимизатора запросов 157
4.4. Использование разработанного оптимизатора и методики оценки времени выполнения запросов для анализа системы «Cybiko PDBS»... 159
4.4.1. Описание исследуемой системы 159
4.4.2. Анализ базового варианта системы 161
4.4.3. Усовершенствование системы 162
4.5. Выводы 164
Заключение 166
Литература 168
- Обзор методов оценки стоимости операции соединения
- Методы поиска оптимального плана на основе нисходящей стратегии
- Разработка интерфейса взаимодействия пользователя с системой
- Использование оптимизатора запросов при разработке СУБД для миникомпьютера Сайбико
Введение к работе
Актуальность темы. В настоящее время при разработке информационных систем широко используются системы управления базами данных (СУБД) на основе реляционной модели данных. Одной из составных частей этой модели являются методы оптимизации запросов, позволяющие анализировать множества альтернативных планов выполнения запросов и выбирать оптимальные планы их реализации.
Разработка эффективного оптимизатора запросов в составе СУБД остаётся одной из наиболее важных задач. Это позволяет существенно уменьшить время выполнения запросов в системах разных классов. Например, при принятии решений в системах организационного управления выполняются SQL-запросы, соединяющие несколько десятков таблиц. При этом существующие оптимизаторы в основном используют эвристические методы, что может приводить к выбору неоптимального плана выполнения запросов. Часто запросы выполняются часами. Другой класс систем, системы оперативной обработки информации, характеризуются большим числом клиентов и наличием дорогостоящей техники, обрабатывающий большой поток запросов. Уменьшение времени выполнения запросов для таких систем позволяет увеличить нагрузочную способность и сократить число единиц дорогостоящей техники.
Практика показывает, что подходы, используемые для оптимизации простых запросов в системах оперативной обработки информации, оказываются не столь эффективными для сложных аналитических запросов, выполняемых в системах организационного управления. Причиной этого является то, что восходящая стратегия оптимизации, разработанная более 15 лет назад для оптимизатора системы System R и не претерпевшая с тех пор значительных изменений, имеет один принципиальный недостаток, который ограничивает её применение для оптимизации сложных запросов: перед генерацией первого плана некото-
рой группы, оптимизируются все её дочерние группы. При этом нет возможности избежать генерации мультивыражений в группах, которые не являются частью оптимального плана, на основе информации, получаемой с верхнего уровня. В последние годы была предложена нисходящая стратегия оптимизации, позволяющая преодолеть недостаток восходящего подхода за счёт использования верхних и нижних границ стоимости для отсечения групп планов. Это делает её более перспективной для дальнейшего развития, однако в существующей реализации нисходящей стратегии оптимизации вероятность срабатывания механизма отсечения групп невелика, что обесценивает её преимущества. Поэтому разработка метода поиска оптимального плана, позволяющих использовать преимущества нисходящей стратегии и уменьшить время анализа пространства поиска за счёт сокращения числа рассматриваемых альтернативных планов, является актуальной задачей.
Цель работы. Целью работы является разработка новых методов поиска оптимального плана на основе нисходящей стратегии анализа альтернативных планов и использование полученных теоретических результатов при разработке оптимизатора запросов к СУБД.
В работе решены следующие задачи:
выполнен критический анализ существующих методов оптимизации выполнения запросов,
разработаны методы поиска оптимального плана с использованием нисходящей стратегии анализа альтернативных планов,
разработан оптимизатор запросов, реализующий предложенные методы нисходящей стратегии поиска,
проведён анализ эффективности предлагаемых методов поиска оптимального плана с помощью разработанного оптимизатора запросов,
выполнено исследование процесса обработки запросов в реальной вычислительной системе на этапе её реорганизации.
Объект исследования. Объектом исследования настоящей работы являются оптимизаторы запросов, встраиваемые в современные системы
7 управления базами данных с целью увеличения производительности выполнения запросов.
Предмет исследований. Предметом исследований настоящей работы являются процессы оптимизации запросов пользователей системами управления базами данных.
Научная новизна. В работе получены следующие новые научные результаты:
разработан новый метод поиска оптимального плана с использованием нисходящей стратегии анализа альтернативных планов, позволяющий уменьшить время поиска за счёт рационального выбора верхней и нижней границ стоимости выражений в memo-структуре,
предложен метод генерации пространства поиска, который позволяет определить все логически эквивалентные мультивыражения, описывающие альтернативные планы выполнения запроса, и исключить все планы, содержащие декартовы произведения,
получены формулы для оценки вероятности отсечения планов, содержащих декартовы произведения,
выведены формулы для оценки числа альтернативных деревьев поиска и необходимых для их представления мультивыражений в memo-структуре для различных типов деревьев поиска и топологий запросов,
получены формулы для оценки стоимостей операций соединения таблиц базы данных методом вложенных циклов и методом сортировки и слияния, учитывающие наличие и тип индексов по столбцам соединения, а также объём доступной оперативной памяти;
Методы исследования. Исследования проводились на основе комплексного использования теории реляционных баз данных, теории множеств, теории вероятности, теории графов, комбинаторики и теории формальных языков.
Практическая ценность полученных результатов. В работе для практического использования полученных результатов разработан оптими-
8 затор запросов, реализующий предложенные методы и алгоритмы нисходящей стратегии поиска. Оптимизатор позволяет задавать различные наборы логических и физических операторов, правил генерации и ограничений пространства поиска, анализировать эффективность использования индексов по различным атрибутам таблиц, прогнозировать время выполнения запросов к СУБД. Он может быть использован для исследования процесса обработки запросов в реальных вычислительных системах на этапах реорганизации и модернизации.
Внедрение результатов исследований. Разработанный оптимизатор запросов использован в качестве программного компонента при проектировании специальной системы управления базами данных для миникомпьюте-ра Сайбико, что позволило уменьшить время выполнения запросов в СУБД в среднем на 40%.
Разработанные методы, методика и оптимизатор запросов использованы в процессе исследования процесса обработки запросов в системе «Cybiko PDBS» на этапе её реорганизации с целью прогнозирования характеристик функционирования системы при добавлении к ней подсистемы поддержки принятия решений. Проанализированы планируемые запросы к СУБД, учитывающие сложный характер задач указанной подсистемы, и содержащие большое количество операторов соединения, агрегации и сортировки. В результате получены оценки времени выполнения этих запросов к СУБД. Для двух запросов получено время выполнения, превышающее установленный десятисекундный предел. Для устранения этих «узких мест» было предложено использовать индексы по столбцам соединения и сортировки. Анализ оптимизированного варианта системы показал, что время выполнения всех тестовых запросов не превышает установленные в требованиях к системе ограничения.
Публикации по теме работы. По материалам работы опубликовано 7 печатных работ.
9 Апробация работы. Материалы работы были изложены автором на следующих конференциях и семинарах:
Теоретическая конференция компании Сайбико, М., 2002.
НТС кафедры ИУ-5, МГТУ им. Н.Э. Баумана, М., 2003.
Структура диссертационной работы. В первой главе «Анализ существующих методов построения оптимизаторов запросов» приведено описание процесса обработки запросов в СУБД, выделены и проанализированы компоненты ядра СУБД, участвующие в обработке запросов пользователей. Выделены аспекты, определяющие процесс оптимизации запросов, приведена общая классификация подходов к оптимизации запросов, реализуемых в современных СУБД. Проведён анализ основных подходов к оптимизации запросов с точки зрения реализуемых стратегий поиска оптимального плана выполнения запроса. Проведён анализ существующих методов оценки стоимости операции соединения таблиц базы данных.
Во второй главе «Методы повышения эффективности нисходящей стратегии поиска» проведен анализ алгоритма нисходящей стратегии поиска, выполнено сравнение алгоритмов нисходящей и восходящей стратегий поиска. Разработаны новые методы поиска оптимального плана на основе нисходящей стратегии, позволяющие увеличить вероятность отсечения групп. Доказаны лемма и теорема, определяющие эффективный метод генерации пространства поиска с использованием нисходящей стратегии поиска. Получены формулы для оценки числа альтернативных деревьев поиска и необходимых для их представления мультивыражений в memo-структуре для различных типов деревьев поиска и топологий запросов. На их основе проведена оценка предлагаемых методов поиска на основе нисходящей стратегии. Предложена стоимостная модель для операций соединения таблиц базы данных методом вложенных циклов и методом сортировки и слияния.
В третьей главе «Разработка оптимизатора запросов с нисходящей стратегией поиска» предложена формализованная модель процесса оптимизации запросов, на основе модели разработаны архитектура и логический
10 проект оптимизатора запросов, реализующего предложенные методы нисходящей стратегии поиска, предложена методика использования оптимизатора запросов для прогнозирования времени выполнения запросов СУБД.
В четвертой главе «Использование разработанного оптимизатора запросов для анализа эффективности предложенных методов поиска оптимального плана и при разработке программных продуктов компании Сайбико» приведены результаты исследования эффективности предложенных методов поиска на основе нисходящей стратегии, описано использование оптимизатора запросов при разработке специальной СУБД для миникомпью-тера Сайбико, а также рассмотрены результаты исследований системы «Cybiko PDBS» с помощью разработанного оптимизатора запросов.
Обзор методов оценки стоимости операции соединения
Оптимизатор производит выбор оптимального плана выполнения запроса среди множества альтернативных планов. Применение той или иной стратегии поиска позволяет сформировать это множество планов (пространство поиска) и оценить полученные планы, присвоив им некоторые стоимостные оценки. Стоимость плана зависит от стоимостей составляющих его физических операторов. Известно, что операция соединения таблиц в процессе обработки запросов является наиболее важной. В данном разделе приводится анализ существующих методов оценки стоимости операции соединения двух таблиц базы данных, выделены их достоинства и недостатки. При этом рассматриваются следующие методы реализации операции соединения: метод вложенных циклов (МВЦ), методом сортировки и слияния (МСС) и хеш-соединение (ХС). 1.4.1. Стоимостная модель Грэфа
В работе Грэфа [79] рассматривается процесс обработки запросов для баз данных большого объёма. В этой публикации рассматриваются усовершенствованные алгоритмы МВЦ, учитывающие небольшой (по сравнению с размерами соединяемых отношений) объем доступной оперативной памяти (ОП). Усовершенствованный алгоритм МВЦ использует оперативную память для буферизации части внешнего отношения объемом М-К и части внутреннего отношения объемом К, проводя сравнение двух буферов, циклически подгружая оставшуюся часть внутреннего отношения объемом S-K. В работе [79] приведена следующая формула для оценки стоимости операции соединения МВЦ: где М - объём доступной оперативной памяти в страницах, R и S - число страниц в соединяемых отношениях.
Для соединения МСС исследована стоимость сортировки отношения. Большой объём отношения затрудняет проведение его сортировки в оперативной памяти. Для этого необходимо использовать специальные алгоритмы Merge Sort. Эти алгоритмы основаны на создании промежуточных файлов сортировки (run-файлы) и последующего их слияния. Для оценки времени выполнения сортировки в рассматриваемой работе предложено следующее выражение:
В данной работе также приведены результаты анализа алгоритма ХС, на основе которого получена формула для оценки его стоимости: где F - входное разветвление, С - размер кластера в страницах, Т - время чтения страницы, L - число уровней слияния. В работе [85] анализ алгоритмов соединения основан на оценке времени, требуемого для доступа и передачи страницы с диска, и стоимости обработки соединения в оперативной памяти (ОП). Сделано предположение о наличии небольшого объема свободной ОП, содержащей один или два указателя на каждую страницу БД. В алгоритме доступная ОП используется для размещения блоков «внешнего отношения» А и выполняется сравнение с блоками отношения В, циклически подгружаемыми в ОП для каждой группы блоков отношения А. В работе сделано предположение, что сравнение блоков в ОП производится с помощью хэш-соединения. В рассматриваемой работе приведены следующие формулы для оценки стоимости операций соединения МВЦ и МСС: число страниц в отношениях А и В, VR - число страниц в результирующем отношении R; В, ВА, Вв - число страниц, доступных в ОП, для отношений А и В; Тс, Tj, Тм - стоимости соответственно создания хэш-таблицы на страницу в ОП, соединения страницы с хэш-таблицей в памяти, слияния страниц в алгоритме SMJ; Ts, TV — стоимости сортировки страницы в ОП и передачи страницы из ОП на диск, Ks - константа сортировки.
В работе также анализируется алгоритм гибридного хеш-соединения и приведена формула для оценки его стоимости.
В работе [119] приведены результаты исследования различных алгоритмов соединений, выполнена их классификация, рассмотрены алгоритмы соединений, использующих специальные структуры данных и аппаратные особенности, проанализирована обработка соединений в распределённой среде. Однако относительно стоимостных моделей указывается только то, что в общем случае алгоритм МВЦ имеет производительность порядка 0(m n), алгоритм МСС -порядка 0(n logfi), ХС - порядка 0(m+n).
Работа [144] является наиболее фундаментальным исследованием стоимостных моделей алгоритмов операций соединения. Однако, в ней рассматриваются только операции соединения МСС и три алгоритма ХС. Для оценки стоимости операции соединения МСС получена следующая формула: где {R}, {S} - число кортежей в отношениях R и S, R, S - число блоков, занимаемых отношениями R и S, М - объем свободной ОП, сотр - время сравнения ключей в ОП, swap — время перестановки двух кортежей, Ю — время чтения блока с диска в ОП.
Для алгоритмов ХС проведено большое исследование и получены различные формулы стоимости, зависящие как от наличия индексов по столбцам соединения, так и объёма оперативной памяти. Даны рекомендации для выбора алгоритма реализации соединений для различных ситуаций.
Анализ методов оценки стоимости операции соединения показал, что для операции хеш-соединения (ХС) двух таблиц известны подробные формулы расчёта стоимости для различных физических реализаций [144]. Однако, для двух других физических реализаций операции соединения - методом вложенных циклов (МВЦ) и методом сортировки и слияния (МСС) - во всех известных автору формулах оценки стоимости [1.1-1.6] не учитывается наличие и тип доступных индексов, которые в значительной степени влияют на время выполнения операции соединения. Таким образом, важно исследовать влияние наличия индексов на оценки стоимости операции соединения МВЦ и МСС. 1) Проанализирован процесс обработки запросов в СУБД, выделены этапы обработки запроса и рассмотрены соответствующие компоненты СУБД. 2) Выполнен анализ процесса оптимизации запросов, выделены три основных понятия, определяющих процесс оптимизации запроса: пространство поиска, стоимостная модель и стратегия поиска. Сформулированы три признака и проведена классификация существующих подходов к процессу оптимизации запросов, реализуемых в современных СУБД, 3) Выделены и проанализированы существующие стратегии поиска, реализуемые оптимизаторами запросов. Показано, что существующие методы имеют ряд недостатков и ограничений:
Методы поиска оптимального плана на основе нисходящей стратегии
Как показано в разделе 2.1. настоящей работы основным преимуществом нисходящего оптимизатора запросов над восходящим является возможность использования механизма отсечения групп при оптимизации запроса. Отсечение группы - ситуация, при которой группа не будет оптимизирована, т.е. для неё не будет сгенерировано ни одно мультивыражение в про цессе оптимизации.
Отсечение группы является пассивным действием, т.е. группа никогда вручную не удаляется. Отсечённая группа будет содержать только одно мультивыражение, которое было использовано для её инициализации. Отсечение групп приводит к уменьшению числа мультивыражений, рассматриваемых в процессе оптимизации (сокращению пространства поиска) и, следовательно, к уменьшению времени оптимизации. При этом оптимизатор, который осуществляет отсечение групп, гарантированно строит оптимальные планы, в отличие от методов сокращения пространства поиска, основанных на эвристиках, при использовании которых возможен выбор неоптимального плана.
Количественный выигрыш от использования механизма отсечения групп зависит от частоты срабатывания отсечения. Чем чаще происходит отсечение групп, тем больше сокращается пространство поиска и тем меньше общее время оптимизации. Таким образом, представляется целесообразным разработка методов, позволяющих увеличивать вероятность отсечения групп в процессе оптимизации. Рассмотрим процесс вычисления стоимостей при оптимизации группы в соответствии с алгоритмом нисходящей стратегии поиска. На рис. 2.5. показан псевдокод рекурсивного алгоритма вычисления стоимостей: На рис. 2.6. графически изображен процесс изменения стоимостей в процессе оптимизации группы, затрагивающий N таблиц запроса соединения. Вычисление стоимостей в процессе оптимизации группы происходит следующим образом: 1. Вычисляется стоимость базового оператора текущего физического мультивыражения группы (см. (3) на рис. 2.5). 2. Производится сравнение этой стоимости с текущим значением верхней границы стоимости группы (см. (4) на рис. 2.5). 3. Если данная стоимость превышает верхнюю границу, то выполняется переход к следующему мультивыражению группы (см. цикл (2) на рис. 2.5), 4.
Вычисляются стоимости оптимальных планов первой и второй входных групп текущего физического мультивыражения путём оптимизации этих групп (см. цикл (5) и строку (6) на рис. 2.5), 5. Определяется стоимость текущего физического мультивыражения группы как сумма трёх указанных стоимостей: стоимости базового оператора (см. (3) на рис. 2.5) и стоимостей оптимальных планов первой и второй входных групп (см. (8) на рис. 2.5), 6. Производится сравнение стоимости текущего физического мультивыражения с текущим значением верхней границы стоимости группы (см. (9) на рис. 2.5), 7. Если эта стоимость меньше верхней границы, то верхняя граница стоимости группы устанавливается равной стоимости текущего физического мультивыражения (см. (9) на рис. 2.5), 8. Шаги с 1-ого по 7-ой повторяются для всех оставшихся мультивыражении исходной группы (см. цикл (2) на рис. 2.5). Полученная таким образом верхняя граница стоимости группы представляет собой стоимость оптимального мультивыражения группы и может быть использована при оптимизации групп, чьи мультивыражения содержат данную группу в качестве входов (на шаге 4). Таким образом, стоимость каждого мультивыражения в группе определяется в три этапа: 1. Вычисляется стоимость базового оператора мультивыражения. 2. Добавляется стоимость оптимального плана первого входа мультивыражения. 3. Добавляется стоимость оптимального плана второго входа мультивыражения.
Разработка интерфейса взаимодействия пользователя с системой
Время поиска оптимального плана выполнения запроса определяется размером пространства поиска, которое в свою очередь определяется числом возможных деревьев поиска для исходного запроса. Если рассматривать только случай использования операторов соединения и доступа к файлам, то это число есть число альтернативных порядков соединения или деревьев соединений.
Дерево соединений - это регулярное бинарное дерево, «листья» которого представляют собой базовые таблицы, которые указаны в исходном запросе, а промежуточные узлы моделируют операторы соединения. Эти операторы по 68 лучают входные таблицы через входные дуги и пересылают таблицу результата операции по выходной дуге к следующему оператору. «Корень» (вершина) дерева определяет результат всего запроса. Дерево соединений является бинарным, так как реляционный оператор соединения имеет два входа.
При поиске оптимального плана оптимизатор обычно строит деревья поиска одного из двух типов: лево-глубокие и упорядоченные кустовые (см. рис. 2.16). Лево-глубокое (левостороннее, левонаправленное, леволинейное, линейное) дерево поиска - это дерево поиска, в котором для каждого оператора соединения (промежуточного узла) хотя бы один из входов является базовой таблицей, в противном случае дерево соединений называется кустовым.
Кроме типа деревьев поиска, на построение которого настроен оптимизатор, размер генерируемого им пространства поиска зависит также от топологии графа исходного запроса (в дальнейшем будем говорить просто о топологии запроса). Существуют три типовые топологии запросов: линейная, звездообразная и полностью соединённая (см. рис. 2.17(a)).
Линейный (строковый) запрос для п отношений состоит из двух терминальных (крайних) отношений, каждое из которых соединено только с одним отношением, и и-2 внутренних отношений, каждое из которых соединено с двумя другими соседними отношениями. Связь между двумя отношениями означает наличие в исходном запросе предиката соединения для этих отношений. Звездообразный запрос для п отношений состоит из одной центрального отношения и пЛ терминальных отношений, которые соединены только с центральным. Полностью соединённый запрос для п отношений состоит из п отношений, каждое из которых соединено со всеми другими п-\ отношениями. Любой запрос можно представить в виде полностью соединённого запроса, достроив недостающие связи путём добавления фиктивного предиката соединения, который всегда имеет значение «истина». Добавленные таким образом связи, очевидно, будет представлять декартовы произведения соответствующих отношений.
Линейная и звездообразная топологии запросов представляют собой крайние случаи ациклических запросов [124]. Так линейный запрос содержит одну ветвь, а звездообразный — п ветвей графа запроса соединений п таблиц. В работе [124] показано, что количество альтернативных деревьев поиска для всех остальных топологий ациклических запросов (с 2-мя, 3-мя и т.д. ветвями при фиксированном числе отношений, см. рисунок 2.17(6)) лежит в интервале от числа деревьев поиска для линейных запросов до числа деревьев поиска для звездообразных запросов.
Найдём число возможных деревьев поиска для указанных топологий запросов и типов деревьев поиска. При этом будем рассматривать только логические деревья поиска, не рассматривая различные физические реализации операции соединения. Случай 1. Кустовое дерево, полностью соединённый запрос.
Этот случай даёт верхнюю границу числа возможных деревьев поиска. В работе [103] дана оценка числа деревьев поиска для этого случая:
Предполагается, что для каждого дерева поиска корневой узел имеет левый операнд, охватывающий к отношений и правый операнд, охватывающий (n-к) отношений. Поэтому число деревьев поиска определяется с помощью следующего выражения:
Далее путём достаточно сложных математических вычислений из (2.2) выводится искомая формула (2.1). В настоящей работе предлагается более простой вывод формулы (2.1) для числа деревьев поиска в рассматриваемом случае.
Из курса дискретной математики известно (например, [87]), что одной из интерпретаций последовательности Каталана является число бинарных деревьев поиска с п+1 листьями. Отсюда, число бинарных деревьев поиска с п «листьями» определяется (п-1)-ым числом Каталана. Так как «листья» в рассматриваемом дереве поиска не упорядочены, то можно менять их порядок любым способом для заданного дерева поиска. Это даёт п! различных расположений «листьев» в дереве поиска. Поэтому получим следующее число деревьев поиска:
Как указано выше, дерево определяется упорядоченной последовательностью «листьев». Первым оператором соединения в дереве поиска для звездооб разного запроса будет оператор соединения одного из терминальных отношений с центральным. Следовательно, существует 2 варианта для выбора первых двух «листьев» в дереве поиска: в качестве первого «листа» можно выбрать центральное отношение (одним способом) либо терминальное (п-1 способом). Третий и последующий «листы» можно выбрать из любых оставшихся терминальных отношений, т.е. п-2, п-3, ..., 2, 1 способами. Таким образом, общее число деревьев поиска в рассматриваемом случае может быть оценено как:
Этот же результат можно получить, заметив, что для звездообразного запроса каждое из п-1 терминальных отношений связано с остальными п-2 терминальными отношениями через центральное отношение, и после выполнения первой же операции соединения запрос становится «как бы» полностью соединённым запросом соединения, но уже для п-1 отношения. Используя полученный ранее результат (случай 4), получаем формулу 2(и -1)!.
Использование оптимизатора запросов при разработке СУБД для миникомпьютера Сайбико
Для оценки преимуществ использования memo-структуры для представления деревьев поиска в пространстве поиска, сравним результаты, полученные в разделах 2.3.2 и 2.3.3. Хотя в указанных разделах получены результаты для объектов различного типа (деревьев поиска и мультивыражений), возможность сравнения обусловлена тем, что оба типа объектов представляются в процессе работы оптимизатора похожими структурами данных (программными единицами), которые требуют расхода оперативной памяти и других ресурсов.
В табл. 5 представлено количество альтернативных деревьев поиска и необходимых для их представления мультивыражений в memo-структуре для запросов, включающих от 3 до 7 соединяемых отношений, для различных типов деревьев поиска и топологий запросов. Выигрыш, получаемый за счёт использования memo-структуры и мультивыражении, для конкретного типа конечного дерева поиска и топологии исходного запроса можно оценить, сравнив значение в соответствующей ячейке столбца «дерев.» со значением ячейки столбца «опер.». Например, для случая кустового дерева поиска и полностью соединённого исходного запроса существует 120 альтернативных деревьев поиска и требуется 54 мультивыражения (оператора соединения) для их представления. Следовательно, получаемый выигрыш равен (120-54)/120, то есть 55%.
Из рисунка видно, что наибольший выигрыш достигается для кустовых деревьев поиска, для которых при любой топологии исходного запроса соединения 6-ти отношений выигрыш составляет более 95%. Выигрыш, достигаемый для лево-глубоких деревьев поиска менее значителен, однако и в этом случае для полностью соединённых и звездообразных запросов выигрыш приближается к 90%, начиная с 7-8 отношений. Медленнее всего растёт величина выигрыша для линейных запросов при построении лево-глубоких деревьев поиска. Это объясняется малым числом деревьев для данного случая, поэтому выигрыш от использования memo-структуры начинает ощущаться только для запросов соединения 6 отношений и достигает величины 90% только для запросов с 11 отношениями. Отсутствие выигрыша в некоторых случаях для запросов, включающих малое число отношений (от 3 до 5), объясняется также малым числом деревьев поиска для этих случаев, а также учётом при подсчёте числа мульти-выражений п операторов доступа к базовым отношениям, которые не являются операторами соединения.
Таким образом, следует сделать вывод, что использование memo-структуры и мультивыражений для представления деревьев поиска в пространстве поиска позволяет получить значительный выигрыш как в оперативной памяти, так и в быстродействии работы оптимизатора запросов СУБД. Полученные в разделе 2.3.3 оценки числа мультивыражений, используемых для представления деревьев поиска в пространстве поиска, позволяют произвести количественный анализ предлагаемых в настоящей работе методов поиска оптимального плана. Как указывалось в разделе 2.3.1, величина получаемого выигрыша будет равна числу мультивыражений, которые будут содержаться во всех несвязанных группах пространства поиска. Эта величина Ыне_связ определяет насколько меньше мультивыражений будет генерировать оптимизатор по сравнению с полностью соединённым запросом Nnc. Отношение NHe_cBH3/Nnc может трактоваться как вероятность отсечения группы Ротс (исходя из классического определения вероятности).
Данная величина зависит от типа создаваемых деревьев поиска и топологии исходного запроса. Результаты разделов 2.3.2-2.3.4 позволяют выделить три случая, представленных ниже. Для оценки числа мультивыражений, которые будут содержаться во всех несвязанных группах пространства поиска для этого случая, воспользуемся теоремами 2 и 3 раздела 2.3.3:
Для оценки числа мультивыражений, которые будут содержаться во всех несвязанных группах пространства поиска для этого случая, воспользуемся теоремами 4 и 5 раздела 2.3.3:
Для оценки числа мультивыражений, которые будут содержаться во всех несвязанных группах пространства поиска для этого случая, воспользуемся теоремами 4 и 6 раздела 2.3.3: различных типов деревьев поиска и топологий исходного запроса, включающего от 3 до 13 соединяемых отношений. Из рисунка видно, что для линейных запросов при построении деревьев поиска любого типа вероятность отсечения приближается к 0.9, начиная с 7-ми соединяемых отношений. Для звездообразных запросов эта вероятность практически на зависит от числа соединяемых отношений и находится на уровне 0.5-0.55.
Результаты, полученные при использовании предположения ПР1 (см. раздел 2.3.1), являются завышенной оценкой получаемой вероятности отсечения. Однако, как показывают эксперименты с использованием разработанного оптимизатора запросов (см. главу 4), погрешность составляет менее 10%, что позволяет признать полученные теоретические оценки удовлетворительными.
Получение более точных оценок связано с неопределённостью ряда входных параметров: значения верхней границы группы к моменту оптимизации конкретного мультивыражения, уровня с которого произошел вызов функции оптимизации конкретной группы, размеров соединяемых отношений и, как следствие, стоимости конкретного мультивыражения и т.д. В настоящем разделе предлагается стоимостная модель для операций соединения двух отношений методом вложенных циклов и методом сортировки и слияния. В рамках модели предлагаются формулы для оценки стоимости процессорных инструкций и дискового ввода-вывода для (I) метода вложенных циклов в случаях: (1) файлового сканирования обоих таблиц, (2) файлового сканирования внешней таблицы и доступа по кластеризованному или некласте-ризованному хеш-индексу или В+ индексу к внутренней таблице; (II) для метода сортировки и слияния в случаях: (1) отсутствия индексов или наличия (2) кластеризованного или (3) некластеризованного В+ индекса по столбцу соединения внешней таблицы. Также для каждого из этих трёх случаев рассматриваются ситуации: отсутствия индексов или наличия кластеризованного или некластеризованного В+ индекса по столбцу соединения внутренней таблицы. В каждом из этих случаев для стоимости ввода-вывода предлагаются две формулы для различного числа доступных буферов памяти (Ь).
При использовании в операторе CREATE INDEX языка SQL параметра CLUSTERED для таблицы создается кластеризованный индекс по указанным столбцам. Кластеризованный индекс сортирует физически содержание таблицы в том порядке, в котором столбцы были указаны при создании индекса. СУБД позволяет создать только один кластеризованный индекс для таблицы, потому что невозможно упорядочить физически строки таблицы более чем одним способом. Отличительным свойством кластеризованного индекса является то, что его листья содержат страницы данных. При использовании в операторе CREATE INDEX параметра NONCLUSTERED для таблицы определяется не-кластеризованный индекс. Некластеризованный индекс имеет такую же структуру, как и кластеризованный, но с двумя важными отличиями. Первое - некла-стеризованные индексы не изменяют физический порядок расположения строк в таблице. Второе - листья некластеризованных индексов содержат ключ индекса и указатель на строку данных в таблице. По этой причине при использовании некластеризованного индекса поиск происходит в два этапа: сначала ищется указатель на строку в структуре индекса, а затем происходит поиск в таблице с использованием полученного указателя.
