Содержание к диссертации
Введение
Глава 1. Современное состояние проблемы оптимизации SQL-запросов 9
Ї.І. Ход обработки запроса 9
1.2. Логическая оптимизация 10
1.3. Семантическая оптимизация 11
1.4. Построение возможных планов выполнения запроса и выбор оптимального из них 13
1.5. Выводы 23
Глава 2. Разработка метода оптимизации 25
2.1. Оптимизация потоков SQL-запросов 25
2.2. Критерии оптимизации 26
2.3. Выделение оптимизируемых классов задач и разработка метода оптимизации для них 35
2.3.1. Каскадные таблицы 35
2.3.2. Таблицы, зависимые только от одного уровня 44
2.3.3. Таблицы, имеющие зависимости более чем от одного столбца 52
2.3.4. Таблицы, имеющие фильтры и обратные зависимости 53
2,3.5.Таблицы смешанного типа 57
2.4. Сравнительный анализ предлагаемого метода оптимизации и существующих методов 58
2.5. Модель системы, реализующей предлагаемый метод оптимизации 59
2.6. Выводы 63
Глава 3. Оценка избыточности и времени выполнения при проведении оптимизации 65
3.1. Параметры, используемые для оценок 66
3.2. Оценка избыточности данных 70
3.2.1. Каскадные таблицы 70
3.2.2. Таблицы, зависимые только от одного уровня ...75
3.3. Оценка времени обработки запросов сервером 77
3.3.1. Анализ способов доступа к данным 78
3.3.2. Анализ методов выполнения операции соединения и разработка оценки времени обработки запросов для них 78
3.3.2.1. Метод вложенных циклов 78
3.3.2.2. Метод хэш-соединения 94
3.3.2.3. Метод соединения слиянием 100
3.3.3. Особые случаи и разработка оценки времени обработки запросов для них 104
3.3.3.1. Использование кластеров 104
3.3.3.2. Использование материализованных представлений 106
3.3.3.3. Использование битовых индексов соединения 108
3.4. Выводы 109
Глава 4. Разработка метода синтеза запросов 111
4.1. Этапы проведения синтеза 111
4.2. Выделение подпотоков запросов, подлежащих оптимизации 111
4.3. Преобразование множества простых запросов, составляющих выделенный подпоток, к одному сложному 134
4.4. Проверка целесообразности преобразования 139
4.5. Выводы 141
Заключение 142
Литература
- Семантическая оптимизация
- Выделение оптимизируемых классов задач и разработка метода оптимизации для них
- Таблицы, зависимые только от одного уровня
- Выделение подпотоков запросов, подлежащих оптимизации
Введение к работе
Актуальность темы. В настоящее время для хранения и обработки данных активно используются реляционные базы данных. Размер баз данных, т.е. объем хранимых данных, может варьироваться в широком диапазоне ~ от килобайтов до терабайтов. Понятно, что чем больше размер отношений базы данных, тем больше уходит времени на поиск нужной информации, т.е. увеличивается время обработки запросов сервером. Кроме того, в последнее время базы данных используются для публикаций данных в интернет. В этом случае количество пользователей базы данных, которые обращаются к ней в данный момент времени, может значительно возрастать. В результате опять же возрастает нагрузка па сервер. С одной стороны эту проблему пытаются решать увеличением производительности компьютеров, на которых находятся системы управления базами данных (СУБД). Однако, простого увеличения производительности компьютеров, конечно же, недостаточно; часто гораздо большего эффекта можно добиться с помощью изменения алгоритмов обработки SQL-запросов. Так, например, использование одноуровневых индексов взамен сканирования таблицы, позволяет добиться логарифмической зависимости скорости выполнения запроса от количества занимаемых страниц данных (при сканировании таблицы зависимость линейная). При использовании индексов в виде сбалансированных деревьев получаемый выигрыш еще больше. В то же время, повышение скорости работы внешней памяти дает лишь линейное увеличение производительности обработки запросов.
Таким образом, хотя работы по оптимизации SQL-запросов ведутся уже не одно десятилетие, в настоящее время они вовсе не потеряли актуальности. Напротив, в связи с увеличением темпов роста объема информации и нагрузки на сервер баз данных, такие работы стали еще более актуальны.
Оптимизировать выполнение запросов можно по различным критериям - по скорости выполнения, по загрузке процессора, по объему используемой памяти и т.д. Обычно при оптимизации SQL-запросов, главной целью является минимизация времени выполнения запроса, но поскольку при выполнении конкретного запроса самой дорогостоящей операцией является обращение к диску, то и параметром
5 оптимизации, как правило, является количество обращений к диску. Другим важным критерием является требуемое для обработки запроса процессорное время. Остальными составляющими, как правило, пренебрегают.
На сегодняшний день существует множество способов увеличения скорости выполнения запросов - это и использование дополнительных структур, таких как индексы и хэш-функции и использование материализованных и секционированных представлений и различные алгоритмы выполнения операций соединения и ограничения, ведение статистики данных, т.е. распределения значений в таблицах и многие другие. Построением плана запроса, т.е. его компиляцией занимается специальный компонент СУБД - оптимизатор. При составлении плана выполнения запроса, оптимизатор рассматривает наличие вспомогательных структур, рациональность использования того или иного алгоритма выполнения операций, на основе этого составляет несколько планов выполнения, оценивает стоимость выполнения каждого из них и выбирает наилучший. При этом, поскольку все множество возможных планов слишком велико, то составлять их все и потом оценивать и выискивать самый лучший было бы слишком дорого и превысило бы выигрыш от проведения оптимизации. Т.е. сам процесс оптимизации стал бы занимать времени больше чем выполнение неоптимизированного запроса. Поэтому, составляется не все множество возможных планов, а только некоторое его подмножество, из которых в дальнейшем уже выбирается наилучший. Таким образом, не гарантируется выбор оптимального плана из всех возможных. В связи с этим, по сегодняшний день идут работы с одной стороны по разработке новых структур, позволяющих уменьшить количество обращений к диску при выполнении запроса, а с другой стороны по повышению эффективности самого оптимизатора запросов, т.е. алгоритма выбора возможных планов выполнения.
В диссертационной работе рассматриваются не отдельные SQL-запросы, а потоки запросов и возможность их оптимизации. При этом, SQL-запросы условно делятся на простые и сложные. Простые запросы - это запросы, не содержащие соединений отношений. Такие запросы строятся на основе одного отношения. При наличии мелсду отношениями связи типа М:М допускается использование соединения одного из исходных отношений с промежуточным отношением, реализующим эту связь. Сложные запросы - это запросы, строящиеся на основе нескольких отношений.
Целью работы является разработка и исследование метода оптимизации взаимодействия пользовательских приложений определенных типов и баз данных путем синтеза сложных SQL-запросов из множества простых.
Задачи исследования:
Анализ существующих методов оптимизации SQL-запросов и выявление их недостатков, касающихся оптимизации не одиночных запросов, а потоков запросов; выявление классов задач для которых актуально проведение оптимизации потоков запросов и их классификация.
Разработка математической модели оценки времени обработки потоков запросов для рассматриваемых типов приложений.
Разработка модели преобразования потока SQL-запросов. Проведение синтеза сложных SQL-запросов из множества простых и построение на ее основе системы, предназначенной для выполнения синтеза.
Методы исследования. Для решения указанных задач в диссертационной работе использовалась теория реляционных баз данных, теория множеств, математическая теория отношений, теория систем управления базами данных, теория алгоритмов, метод системного анализа.
Положения, выносимые на защиту:
Модель таблиц с внутренними зависимостями.
Модель взаимодействия между приложением и базой данных.
Результаты анализа влияния предлагаемого метода оптимизации на основные составляющие критерия оптимизации.
Алгоритм обработки результатов синтезированных запросов в прикладном приложении.
Алгоритм синтеза сложных запросов из множества простых.
Практическая ценность. Разработанная на основе предложенного метода программа позволяет выдавать рекомендации по оптимизации потока SQL-запросов,
7 которые пользовательское приложение генерирует для обращения к базе данных. Модификация текста программы с учетом выданных рекомендаций, позволяет существенно повысить эффективность взаимодействия приложения и базы данных. Получаемый выигрыш зависит от множества факторов, описанных в диссертационной работе. Среди таких факторов - размеры отношений в базе данных, наличие на них дополнительных структур, эффективность предикатов SQL-запросов, количество уровней вложенности в таблицах, выдаваемых пользователю и т.д. Увеличение выигрыша растет при увеличении этих параметров. В связи с этим затруднительно дать точную оценку получаемого выигрыша. Для проводимых экспериментов время взаимодействия было уменьшено в среднем в 7 раз. Для определенных случаев, выигрыш может быть и существенно больше. В других случаях выполнение синтеза может не дать никакого выигрыша и даже сказаться отрицательно. В таких случаях проводить его нецелесообразно. Соответственно, программа не будет выдавать рекомендаций по его проведению. Получение выигрыша при использовании выдаваемых рекомендаций говорит об эффективности предложенного метода для определенных классов задач и параметров базы данных.
Внедрение результатов работы. Основные теоретические и экспериментальные результаты работы были внедрены в ГУП «Санкт-Петербургский Информационно-аналитический центр» и в учебном процессе СПбГУАП. Программная система, разработанная по результатам выполнения диссертационной работы, была зарегистрирована в отраслевом фонде алгоритмов и программ, о чем было получено свидетельство № 3763. Акты о внедрении приведены в приложении 4.
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на 5-ой, 6-ой и 7-ой научных сессиях аспирантов ГУАП в 2002-2004 годах, на пятой международной многопрофильной конференции молодых ученых и студентов «Актуальные проблемы современной науки», а так же на научных семинарах кафедры 44 - вычислительных систем и сетей ГУАП и представлены в публикациях [6, 8, 12, 13, 15, 18].
Структура диссертации. Диссертационная работа состоит введения, четырех глав, заключения и трех приложений. В первой главе работы описывается совремешгое
8 состояние проблемы оптимизации SQL-запросов. Рассказывается об этапах обработки запросов и возможностях оптимизации на каждом из них. Объясняется, какие параметры могут подлежать оптимизации, и какими способами она может проводиться. Показывается, что оптимизация запросов носит довольно условный характер и не гарантируется реальная оптимальность полученного плана. Рассказывается об исследованиях в области глобальной оптимизации запросов.
Во второй главе рассматривается критерий оптимизации в предлагаемом методе и его составляющие. Для этого рассматривается модель взаимодействия между приложением и базой данных. Далее приводится описание предлагаемого метода оптимизации, а также проводится классификация классов приложений, подлежащих этому методу. Для проведения классификации разрабатывается модель таблиц с внутренними зависимостями. Показывается, что для обработки результатов оптимизации необходимо изменить алгоритм клиентского приложения и приводятся необходимые алгоритмы. Далее проводится анализ предлагаемого метода и сравнение его с существующими способами оптимизации.
Третья глава посвящена оценке наиболее важных составляющих рассматриваемого критерия оптимизации. Аналитически показывается, что предлагаемый способ оптимизации во многих случаях позволяет получить выигрыш при его применении. Выводятся формулы для оценки рассматриваемых составляющих критерия оптимизации для различных ситуаций (наличие дополнительных структур в БД и использование различных алгоритмов выполнения реляционных операций). Формулы выводятся как для случая проведения предлагаемой оптимизации, так и без него, после чего проводится анализ полученных результатов. Показывается, что выигрыш в основном достигается за счет увеличение вариативности, которая становится доступна оптимизатору запросов, встроенному в СУБД.
В четвертой главе разрабатывается метод синтеза сложных запросов из потока простых. Производится разбиение синтеза на этапы и подробно описываются эти этапы. Этапами проведения синтеза является выделение подпотоков запросов, подлежащих оптимизации, преобразование каждого из таких подпотоков к одному сложному запросу и проверка рациональности преобразования.
Семантическая оптимизация
На этапе семантической оптимизации используется информация об используемых объектах. Например, рассмотрим некое представление. Представление изначально представляло собой статическое определение динамического отношения, созданного из одного или более наборов строк в соответствии с заданным критерием.
Т.е. по сути это виртуальное отношение, составленное с помощью запроса из других отношений. С представлением можно работать так же, как и с обычным отношением (ну или почти так же). Итак, в основе представления лежит SQL запрос. Пусть теперь подается некий SQL запрос на выборку из этого отношения. Если подходить в лоб, то нужно сначала выполнить запрос, на котором основано представление, а потом к полученному результату применить поданный пользователем запрос. Однако, если на этапе составления плана запроса пользователя учитывать информацию об описании данного представления, то результат может быть гораздо лучше. В [27, 75, 86] приводится множество примеров использования семантической оптимизации. Пусть, например, имеется описание:
Create view Viewl as select "from tablel wherefieldl=0 а подаваемый запрос имеет вид select from viewl where field1—1
Сам по себе этот запрос не оптимизировать. Однако, если учесть описание представления, то будет понятно, что условие ложно для всех кортежей отношения tablel. Таким образом нет необходимости его сканировать.
Даже если бы в результате рассмотрения совместно двух запросов не оказалось бы, как в приведенном примере, предиката ограничения в виде константы, слияние запроса с текстом запроса представления, как правило, дает большую эффективность, чем материализация представления с последующим выполнением запроса с полученной материализацией.
Другим примером использования семантической информации может служить использование информации о наложенных ограничениях целостности. Например, если наложено ограничение целостности, позволяющее иметь в отношении кортежи со значениями одного из атрибутов в заданном диапазоне только при условии, что другой атрибут будет иметь строго заданное значение. Например, пусть имеется отношение Employee, имеющее среди прочих атрибутов, атрибут Rank - должность и Salary - оклад. И пусть наложено ограничение целостности, указывающее что оіслад в диапазоне от 20000 до 30000 могут иметь только начальники отделов. Тогда запрос Select "from Employee where salary=23000 может быть преобразован к запросу Select " from Employee where rank= начальник отдела and sa!ary=23000
Такое преобразование в ряде случаев может быть весьма полезным, поскольку позволяет использовать дополнительные структуры, наложенные на атрибут rank. К тому же, количество различных значений атрибута rank гораздо меньше количество разных значений атрибута salary, что может быть эффективно использовано оптимизатором. Запрос
Select from Employee where salary between 20000 and 30000 вообще может быть сведен к запросу Select from Employee where rank— начальник отдела
Когда проведена логическая и семантическая оптимизации, начинается более низкоуровневая оптимизация. Теперь строится план выполнения запроса. В [27, 69] освещаются вопросы эффективного выбора лучшего плана.
Как уже говорилось, одному запросу может соответствовать множество планов. Это множество планов очень велико. Если ставить задачу непременно найти оптимальный план, то конечно же надо сгенерировать как можно большее количество альтернативных планов из этого множества. Однако, если поступать таким образом, то можем получить случай, когда само формирование оптимального плана займет больше времени чем само его выполнение даже в неоптимизированном виде. Поэтому используется некоторое ограниченное множество возможных планов. При этом существует некоторая вероятность того, что оптимальный план просто не будет рассмотрен, но так как формирование этого множества рассматриваемых планов осуществляется по специальному алгоритму, то эта вероятность невелика. Рассмотрим, например возможный алгоритм формирования множества рассматриваемых планов. В нем используется два подхода - использование динамического программирования и использование интересных упорядочений. Суть метода динамического программирования состоит в том, что если рассматриваем запрос, состоящий из нескольких соединений, то необязательно рассматривать все возможные планы
Выделение оптимизируемых классов задач и разработка метода оптимизации для них
Для описания каскадных таблиц (а также и случаев рассматриваемых далее), введем несколько предварительных определений. Для начала введем операцию внешнего соединения. Среди стандартных операций реляционной алгебры нет такой операции, поэтому приходится вводить ее специально.
Результат внешнего соединения похож на результат обычного условного соединения будет, но будет включать все кортежи из первого отношения, а не только те, для которых во втором соединяемом отношении найдены кортежи в соответствии с предикатом соединения. Вместо значений атрибутов кортежей второго отношения, для которых не выполнено условие соединения, в результат будут попадать неопределенные значения (NULL-значения).
Более формально опишем это следующим образом:
Пусть имеются отношения R, и R2 со схемами Sm = {Л, В) и SR2 = (В, С) где А, В и С - подмножества множества атрибутов отношений R, и R2. Операцией сравнения (R-S 9 R2 S) будем называть некоторое корректное логическое выражение, включающее в качестве аргументов атрибуты из множеств К,.В и R2.B. Введем отношение R, со схемой, эквивалентной схеме отношения R,: S — S 112 "Т и содержащее всего один кортеж, все атрибуты которого имеют неопределенное значение (NULL). Пусть отношение R3 = RX[B] \ R2[]; R4=R3[R3.B,=R1.B, &R3.B2=R,.B2 &...&R3.Bk=R1.BJRI B„B,,..,Bte5
Тогда операцией внешнего условного соединения отношений R, и R2 по условию KVB в R2.B будем называть результат выполнения операции: R,[R,.B в R2.B]R2=CR,CR,.B 9 R2.B]R2) u( i?2 )
Далее, при описании различных классов задач будет необходимо показать, что можно использовать как простые условные соединения, так и внешние условные соединения. Для того, чтобы легче это формализовать, введем общую операцию соединения: R.fRj.B в" R2.B]R2 = RI[R,.B R2.B]R2 R,[R,.B в R2.B]R2 Пусть между отношениями Rj и R, существует связь типа 1 :М, либо же связь типа М:М, реализуемая введением промежуточного отношения Si2. Если в таблицу, выдаваемую пользователю, выводятся данные из R, и R,, используя операцию R,[R..A0n R,.BTR, (R,[R A6 " S,,.A]S,?)[S,?.B в" R,.B]R, х ,1.4. ,. і.ч2. 2 или соответственно ч u 2 J -2yL u - J -, то будем обозначать это как R,[R.A в R2.B]R2 rf RJRpA " R2.B]R2= К1\К1Лвл R2.B]R2 (R,[R,.A в" SI2.A]S]2)[Sl2.B 0Л R2.B]R2
Теперь перейдем непосредственно к каскадным таблицам. В простом случае каскадная таблица, основанная на отношениях Rp R2, R3,.„, Rin получается путем выполнения операции (((R.tRpA в" R2.B] R2) [R,.A в" RrB] R3) ...R ) [R .A в" R„,B] Rm
После выполнения указанных соединений, выполняется проецирование на необходимые для вывода столбцы и денормализация, заключающаяся в объединении (группировке) всех одинаковых значений атрибута отношения R; (ie [2..М]). соответствующих одному набору значений атрибутов отношений Rp..., RM .
Например, пусть имеются отношения Facultets, Cafedras, Groups, Students. И пусть надо построить таблицу вида:
Такая таблица является каскадной, поскольку удовлетворяет описанным выше правилам. Каскадную таблицу можно описать системой зависимостей Col2=F(Col{) Col3 = F(Col2) Cohi =F(CO!H-I) 2.9) , где Coli - i-ый столбец таблицы; М - число столбцов; F - зависимость. Это не функция в общепринятом математическом смысле, это форма записи визуализации. Она лишь показывает, что столбец, являющийся аргументом имеет больший уровень вложенности (меньший порядок группировки) чем столбец, являющийся результатом зависимости. Причем уровень вложенности аргумента больше ровно на 1.
Можно сказать, что если для формирования таблицы используется операция R PR А й R R1 Л lL - J !, то имеет место зависимость Col[=F(Col7) (Со/,-атрибут отношения R,, Со12 атрибут отношения R2). Если же используется операция R TR А О R Гіі R lL г 2 2, то имеет место либо зависимость CoI} = F(Col2), либо зависимость Col2 = F{Col ). Допускается возможность той или другой зависимости ввиду того, что применяется операция обычного условного соединения.
Чтобы не было путаницы, отметим, что F - это вовсе не функциональная или многозначная зависимость, или же зависимость соединения, определения которых активно используются в реляционной теории, напомним определения УТИХ зависимостей ([3]):
Функциональная зависимость (ФЗ): Пусть имеется отношение R. а X и Y — произвольными подмножествами множества атрибутов R. Y функционально зависимо от X тогда и только тогда когда в любой момент времени каждое значение X связано в точности с одним значением Y.
Многозначная зависимость (МЗ): Пусть имеется отношение R, а А. В и С являются произвольными подмножествами множества атрибутов R. В многозначно зависит от А тогда и только тогда, когда множество значений В. соответствующее заданной паре (значение А, значение С) отношения R, зависит от А. и не зависит от С.
Зависимость соединения (ЗС): Пусть имеется отношение R, а А. В,,,. . Z произвольными подмножествами множества атрибутов R. Отношение R удовлетворяет зависимости соединения (А, В, ..., Z) тогда и только тогда, когда оно равносильно соединению своих проекций с подмножествами атрибутов А. В Z.
Зависимость F ближе по смыслу к понятию многозначной зависимости, но все приведенные выше определения работают с отношениями, а не с таблицами (различие указано выше).
При построении такой таблицы наиболее простым и естественным и наиболее часто применяемым подходом является сделать запрос па выборку из отношения самого верхнего уровня вложенности (Facultet); затем для каждого выбранного кортежа сделать запрос на соответствующие ему кортежи из отношения второго уровня вложенности; затем повторить то же самое для каждого выбранного кортежа из этого отношения и т.д. Т.е. поток SQL-запросов для конкретного приведенного примера будет выглядеть следующим образом; Select id, name from facultet Select id. name from Cafedra where facultet- 1 Select: id, name from Group where Cafedra=12 Select fio from student where group=I23 Select fiо from student where groups 124 Select id, name from Group where Cafedra=13 Select, fio from, student, where group ==131 Select fto fi-от student where group=132
Таблицы, зависимые только от одного уровня
Теперь рассмотрим случай таблиц, зависимых только от одного уровня. Сначала также рассмотрим объем передаваемых данных без проведения оптимизации. Так же, как и в случае каскадных таблиц, тут будет один запрос на отношение Rlf результат которого будет содержать ] кортежей. Объем выбранных (и соответственно передаваемых) данных из первого отношения составит Л ш l. Над каждым из оставшихся отношений выполняется столько запросов, сколько будет выбрано кортежей из отношения R{, т.е. запросов. Запрос над произвольным отношением R, (2 =i =k) вернет (1 i)j 2 кортежей. Таким образом, все запросы к N 1 IN I -г, отношению Ri вернут і і Li г кортежей. В байтах это составит 1 "" . Суммарный объем передаваемых данных (из всех отношений) плюс служебная информация составит: ЩЧ Щ, If Cw/ #, + 0, ) + 1/( 1ъ СкаВ Нк +Ct_e) = = Nl I1 (C,eff l+i](JN1J II CM ff/+C(ei()) =2 " (3.15)
Теперь рассмотрим, какой объем данных будет передаваться после проведения оптимизации. Как уже объяснялось, по сути, после проведения оптимизации, будут выполняться соединения между отношением Ri и каждым из оставшихся соединений с учетом предикатов соединения и ограничения " 25 3 к и 1 2 -3 ] 4 . Соответственно, каждый из этих промежуточных результатов будет содержать 1 кортежей (г=2...к), а объем данных этих промежуточных результатов N I IN / (С Я + С Я) составит ] і. ч «" " " J байт. Далее между этими промежуточными результатами производится операция декартова соединения, результат которого и является окончательным результатом. Тогда количество полученных кортежей можно оценить по формуле h(Nx I} JN„ Ч) - W /,/- Я(ЛУ(Ми :Ч) 1=2 1=2 , а объем передаваемой информации по формуле C"=N14 JNia4 N14 JN[,4 ... Nl4 JN,k4r (Сш Я+См/ Я1+См, Яз+... + Сы/ Я) + Сея = ПЩЧ МиЧ,) ) + = к Л_ ": i-i (3.16)
Нетрудно заметить, что объем передаваемых данных после проведения оптимизации существенно превышает объем передаваемых до оптимизации, который оценивается по формуле (3.15). Так же, как и для каскадных таблиц, необходимо уточнить оценку (3,16), учтя то, что таблицы, зависимые только от первого уровня в чистом виде, предполагают использование внешних соединений (т.е. присутствуют фильтры типа а, а не (3). В случае, если количество уровней - 2 (к=2), то при замене единственного соединения внутреннего на внешнее добавится 1 у-2 кортежей в результирующий набор данных, или можно сказать, что их количество увеличится с 1 ] 1,2 2 д0 I I 1,2 2 I I 1,2 1 I V 1,2 2 \,1\ ГТрИ ЭТОМ ВСЄ атрибуты, принадлежащие отношению Rx и попавшие в результирующий набор данных, будут иметь значения этих атрибутов, а атрибуты, принадлежащие отношению J?, - либо значения атрибутов из отношения R2, либо значения NULL - в зависимости от того, есть ли соответствующие данному кортежу из R{ кортежи в R2.
Для тех кортежей, которые содержат реальные значения атрибутов отношения R2, как ..- ( ІаіҐНі уже было сказано выше, ооъем данных на кортеж составит 1а" -, а для тех. V/ И / которые заполняются значениями NULL - 2 2 . Доля тех и других кортежей в JNl242 результирующем наборе данных составит соответственно -2 - - и ща ./Л и /2-н у, 2
. В случае, когда к 2, аналогичные рассуждения проведем для соединения отношений J2j с каждым из остальных отношений, поскольку до выполнения декартова произведения эти соединения выполняются независимо друг от друга. Учтя все эти соображения, модифицируем формулу (3. ] 6) и получим опенку для таблиц, зависимых только от первого уровня с учетом внешних соединений (т.е. для таблиц, зависимых только от первого уровня в чистом виде): Ж, /, со.,
Стоит заметить, что размер данных из отношения R] (Ciall- Hi) вынесен из под знака суммы (в отличии от формулы (3.16)), поскольку в его атрибутах никогда не будет содержаться значений NULL (за исключением случаев, когда значения NULL находились непосредственно в кортежах отношения Rx).
Оценка времени обработки запросов сервером Одной из наиболее ресурсоемких операций (в плане обращении к физическому диску) является операция соединения. В зависимости от исходных отношений и наличия у них индексов могут применяться различные способы выполнения ЭТОЙ операции. Для того, чтобы оценивать количество обращений к диску, а значит и параметр Т03С, необходимо рассмотреть все возможные способы выполнения операции соединения. Поскольку всего в запросе может участвовать множество отношений, то обычно мы их обозначаем с помощью индексов. При рассмотрении способов соединений учтем, что операция соединения - двухоиерандная операция и поэтому, для простоты, будем обозначать одно из отношений R. а другое S.
Выделение подпотоков запросов, подлежащих оптимизации
Итак, в предыдущей главе было рассмотрено, почему синтез сложного запроса из множества простых запросов может привести к увеличению производительности. Теперь следует рассмотреть, как, собственно, можно проводить этот синтез.
Сейчас мы будем исходить из того, что на входе имеем поток запросов и информацию о структуре базы данных. Получить поток запросов не представляет большого труда. В различных СУБД имеются для этого свои средства, позволяющие по заданному фильтру фиксировать события, происходящие в СУБД (в том числе отлавливать поступающие запросы). Информацию о структуре базы данных, к которой выполняются запросы нетрудно получить. обращаясь к ее системным таблицам.
На выходе мы хотим получить оптимизированный поток запросов, т.о. такой поток, в котором часть запросов (простых) будет заменена на синтезированные из них сложные запросы.
Синтез должен выполняться із три этапа. На первом этапе нужно анализировать исходный поток запросов с целью обнаружения в нем частей (подію го ков), которые могут подлежать синтезу. Тут должно выполняться соотнесение подпотоков запросов к одному из рассмотренных выше классов задач, которые могут подлежать оптимизации и. собственно, выделение отдельных запросов, составляющих такие подпотоки. На втором этапе нужно провести сам синтез, т.е. преобразование множества простых запросов, составляющих выделенный подпоток к одному сложному. Наконец, на третьем этапе, нужно проанализировать - действительно ли будет выгодно выполнение подобного преобразования?
Сложность выделения подпотока запросов, подходящих под рассмотренные классы задач, подлежащие оптимизации заключается в том. что такой подпоток пе представляет собой часть потока, ограниченного с двух сторон. Т.е. нельзя указать два запроса в потоке и сказать, что это, соответственно, первый и последний запрос в
112 гюдпотоке, и все запросы между ними также входят в этот подпоток. Запросы, хронологически находящиеся между самым первым и самым последним запросом подиотока, и не принимающих участия в процессе оптимизации могут рассматриваться как помехи. Эти помехи осложняют выделение нужных подпотоков.
Для начала рассмотрим выделение подпотоков в самом простом случае - при отсутствии помех. Это означает, что если есть часть запросов, из которых можно синтезировать сложный запрос, то между ними нет не относящихся к ним других запросов.
Пусть строится каскадная таблица, показанная в таблице 2.1. Соответственно для ее построения на СУБД подается следующий поток запросов: Select id, name from facultet Select id, name from Cafedra where facultet=1 Select id, name from Group where Cafedra—12 Select fio from student where group=123 Select fio from student where group=124 Select id, name from Group where Cafedra=13 Selectfio from student where group=131 Select fio from student where group=132 Select id, name from Cafedra where facultet=2 Select id, name from Group where Cafedra=21 Select fio from student where group=211 Select fro from student where group=222
Будем перебирать их по очереди в порядке фактического поступления их на сервер. Для каждого запроса выбирается отношение, из которого выбираются данные для отображения пользователю, т.е. те отношения, атрибуты которых находятся в списке выбора запроса. Если в списке выбора имеются атрибуты из более, чем одного отношения, на основе которого строится запрос, то такой запрос пропускается и далее не рассматривается (в данном примере таких запросов нет). Выбранное отношение будем называть основным для данного запроса.
Производится проверка - существует ли в системе объект, описывающий это отношение. Если нет, то это значит, что рассматриваемый запрос - первый из серии ему подобных. Так, для рассматриваемого в примере потока запросов, первые четыре из запроса будут первыми среди подобных себе, поскольку каждый из них обращается к отношению, к которому пс обращались предыдущие запросы. В этом случае создается объект, описывающий данное отношение. С помощью системной информации, определяется какие внешние ключи имеет отношение, на котором строится запрос (т.е. отношение, из которого выбираются атрибуты для построения таблиц). Данные о внешних ключах записываются во вновь созданный объект.
Теперь нужно проверить предикат ограничения запроса на наличие в нем условий на значение какого-либо внешнего ключа его основного отношения. Предикат ограничения представляет собой множество логических условий, соединенных логическими операциями и/или/не: имена внешних ключей отношения записаны в объекте, который это отношение описывает. Таким образом, не составит труда определить, содержит ли предикат ограничения условия па внешние ключи. Теперь установим связи с объектами, описывающими отношения, которые имеют связи типа 1:М с отношением, на котором строится рассматриваемый запрос. Другими словами, с теми отношениями, на которые указывают внешние ключи, присутствующие в предикате ограничения рассматриваемого запроса.
Если же при проверке существования объекта, описывающего отношение, такой объект в системе нашелся, то соответственно его создавать не нале, а достаточно сопоставить рассматриваемый запрос такому объекту.
