Введение в системы БД (542480), страница 168
Текст из файла (страница 168)
Оптимизация О1: КЕТКХЕЧЕ (Я.ЗНАКЕ) ИНЕКЕ Б.С1ТХ = 'Ьопдоп' АИО 3.3$ = БР.Я$ АНО БР.ЦТХ > 200 АНЮ ЯР.Р$ = Р'.Р$ Еще раз применим аналогичный прием к запросу О1, отделив от него запрос, в котором используется единственная переменная диапазона ЯР. Присвоим отделенному запросу имя 02, а оставшуюся после отделения часть запроса О1 назовем ()2. 02: КЕТК1ЕЧЕ 1НТО ЯР' (ЯР.3$, БР.Р$) ИНЕКЕ БР.ОТХ > 200 92: КЕТК1ЕЧЕ (Б.БМАНЕ) ИНЕКЕ Я.С1ТХ = 'Ьолг(оп' АНО 3.3$ = ЯР'.3$ АНО ЯР'.Р$ = Р'.Р$ Далее тем же методом отделим запрос с единственной переменной Я.
ОЗ: КЕТК1ЕЧЕ 1МТО Я' (3.3$, Б.ЗНАМЯ) ИНЕКЕ Б.С1ТХ = 'Ьопбол' О3: КЕТК1ЕЧЕ (Я'.ЗНАКЕ) ИНЕКЕ Б'.Б$ = БР'.3$ АНО БР'.Р$ = Р'.Р$ И наконец отделим еше один запрос, в котором используются переменные БР' и Р'. 04: КЕТК1ЕЧЕ 1ЫТО БР'' (БР'.Я$) ИНЕКЕ БР'.Р$ = Р'.Р$ О4: КЕТК1ЕЧЕ (Б'.БНАНЕ) ИНЕКЕ Б'.3$ = ЯР''.3$ В результате исходный запрос О0 оказался разбитым на три запроса с одной переменной, О1, 02 и 03 (каждый из которых является проекцией выборки), и два запроса с двумя переменными, 04 и О4 (кажлый нз которых является проекцией соединения).
Сложившуюся в результате ситуацию можно схематично представить в виде структуры, показанной на рис. 17.3. Рис. ) 7.3. Дерево декомпозиции запро- са ЦО Эту схему можно интерпретировать следующим образом. ° В запросах 01, 02 н ОЗ в качестве входных данных используются переменные- отношения Р, ЯР и Б (а точнее, те отношения, которые являются текущими значениями переменных-отношений Р, ЯР и Б) соответственно, которые и помешают результат своего выполнения во временные переменные-отношения Р', БР' и Б' соответственно. 656 Часть $'.
Дополнительные аспекты ° Далее выполняется запрос 04, использующий в качестве входных данных временные переменные-отношения Р' и БР' и помещающий результат своего выполнения во временную переменную-отношение БР ' '. ° Наконец выполняется запрос 04, использующий в качестве выходных данных переменные-отношения Я и ЯР' ', результат выполнения которого и является результатом выполнения исходного запроса. Обратите внимание, что запросы 01, 02 и 03 полностью независимы н их можно обрабатывать в любом порядке (предположительно даже параллельно). Запросы 03 и 04 также можно обрабатывать в любом порядке, но только после получения результатов выполнения запросов 01 и 02.
Запросы 04 и 04 нельзя подвергнуть дальнейшей декомпозиции, поэтому их следует обрабатывать с помощью метода подстановки кортежей (что обычно обозначает применение поиска последовательны.н перебараи (или метода "грубой силы"), поиска па индексу или поиска в хешираваннаи файле). В качестве примера рассмотрим выполнение запроса (24. Обратившись к обычному набору данных, используемых в этой книге для примеров, можно определить, что множество номеров поставщиков в атрибуте ЯР' ',3$ будет выглядеть так; ('31', '32', '34'). Каждое из этих трех значений по очереди должно быть подставлено в атрибут БР' '. 34.
В результате запрос 1)4 примет следующий вид. КЕЖ1ЕЧЕ (Б'.ЯЕАМЕ) КБЕКЕ 3'.34 = 'Я1' ОК Я'.34 = '32' ОК Б'.34 = '34' В [!7.3б) рассматриваются алгоритм разбиения исходного запроса на запросы с не- приводимыми компонентами и алгоритм выбора переменных для подстановки кортежей. Именно от этого последнего из двух указанных алгоритмов во многом зависит общий успех оптимизации. Кроме того, в данной работе предложены эвристические подходы для оценки стоимости того нли иного варианта (в системе !ХОКЕБ обычно, но не всегда, для подстановки используется отношение с наименьшей кардинальностью). Основная задача процесса оптимизации — избежать выполнения декартовых произведений и минимизировать количество сканируемых кортежей на каждом этапе вычислений.
В [17.3б) не представлены алгоритмы оптимизации запросов с одной переменной. Однако информация об этом уровне оптимизации присутствует в общем обзоре системы !ХОКЕБ [17.11). Для оптимизации запросов с одной переменной в СУБД 1ХОКЕБ, в основном, используются функции, аналогичные подобным функциям в других системах. Они применяют хранящиеся в каталоге статистические данные, на основе которых выбирают конкретный путь доступа к требуемым данным (например, индекс или хеш-таблицу).
В [17.37! представлены некоторые экспериментальные материалы (например, результаты измерения производительности для эталонного набора запросов), позволяющие сделать вывод, что описанные выше приемы оптимизации дают хорошие результаты и достаточно эффективны при применении на практике. Ниже приведены некоторые выводы, взятые из этой работы. 1.
Метод отделения — это лучшая из методик, которую можно применять на первом этапе оптимизации. 2. Если на первом этапе нужно выполнять подстановку кортежей, то лля этого лучше всего использовать переменную, по которой выполняется соединение. Глава 17. Оптимизация 657 3. Если к одной из переменных в запросе с двумя переменными применялась подстановка кортежей, то оптимальная тактика заключается в построении временного рабочего индекса или хеш-таблицы (если это еще не сделано) для того атрибута в другом отношении, по которому выполняется соединение.
В СУБД )ДОВЕЗ эта тактика активно применяется. 17.7. Реализация реляционных операторов В этом разделе представлено краткое описание некоторых очевидных методов реализации отдельных реляционных операторов, в частности оператора соединения. Включение данного материала в книгу было вызвано стремлением развеять ту таинственность, которая все еше витает над описанием процесса оптимизации.
Обсуждаемые далее методы соответствуют механизмам, которые в разделе! 7.3 были названы низкоуровневыми процедурами реализации. Зачечание. Более сложные приемы реализации описаны в аннотациях к определенным работам, ссылки на которые приведены в конце главы. Для простоты предположим, что кортежи и отношения физически хранятся на диске так, как они организованы логически. Далее будет рассмотрено выполнение операторов проекции, соединения и обобщения, причем под операторами обобщения будем понимать оба указанных ниже основных варианта. ) .
Обобщение, результат которого не включает атрибутов. 2. Обобщение, результат которого включает как минимум один атрибут. Первый вариант достаточно прост. Как правило, в этом случае выполняется просмотр всего отношения, для которого вычисляется обобщающая функция, за исключением варианта, когда для обобшаемого атрибута имеется индекс. В последнем случае значение обобщающей функции может быть вычислено исключительно по значениям в файле индекса, без необходимости обращения к самому отношению [)7.35), Например, рассмотрим выполнение следующего запроса.
БОММАЕ1ЕЕ БР АОО АХБ ( ЯТХ ) АБ АЯ Для вычисления его результатов достаточно просмотреть индекс по атрибуту ЦТХ (предполагается, что такой индекс существует), вовсе не касаясь сачой переменной- отношения поставок БР. Аналогичные соображения применимы и для функций СООМТ и БОИ (причем для функции СООМТ подойдет любой индекс). Что касается функций МАХ и И1М, то их результат можно получить, выполнив единственную операцию чтения последней (для функции ИАХ) или первой (для функции М1М) строки индекса (здесь вновь предполагается, что индекс для соответствующего атрибута уже существует).
Далее в этом разделе будут рассматриваться обобщающие функции только второго типа (т.е. такие, результат вычисления которых включает значения хотя бы одного атрибута). Ниже показан пример операции обобщения второго типа. БОММАМ1ХЕ БР РЕЕ Р ( Р)) ) АОО БОМ ( ЯТХ ) АБ ТОТЯТХ С точки зрения пользователя, операции проекции, соединения и операции обобщения второго типа, конечно, абсолютно не похожи одна на другую. Но с точки зрения реализации они имеют некоторое сходство, так как в каждом из случаев система должна сгруппи- 658 Часть г'. Дополнительные испекты ровать кортежи на основе значений некоторых атрибутов или комбинации атрибутов, В случае операции проекции подобная группировка позволяет системе исключить кортежи- дубликаты, в случае операции соединения — найти соответствующие друг другу кортежи, а в случае операции обоб~цения — вычислить отдельные обобщенные значения [например, по группам).
Существует несколько методов подобной группировки кортежей. 1. Последовательный просмотр (или метод "грубой силы"). 2. Поиск по индексу. 3. Поиск по хеш-таблице. 4. Слияние. 5. Хеширование. 6. Комбинация названных выше методов. На рис. 17.4-17.8 приведены псевдокоды процедур реализации перечисленных методов для операции соединения (операции проекции и обобщения оставлены читателю в качестве упражнения). На зтих рисунках используются следующие соглашения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
