имеет набор низкоуровневых процедур реализации. С каждой процедурой связана параметризованная формула стоимости, позволяющая оценить стоимость выполнения процедуры (т. е. уровень затрат, требуемых для ее выполнения). Чаще всего стоимость определяется путем подсчета количества необходимых операций ввода-вывода на внешнем носителе, но некоторые системы учитывают также время использования процессора и другие факторы.

Далее, используя сохраняемую в системном каталоге информацию о состоянии базы данных и сведения о взаимных зависимостях между «низкоувроневыми» операциями оптимизатор выбирает одну или несколько процедур-кандидатов для каждой операции в запросе. Этот процесс обычно называют выбором пути доступа.

Генерация различных вариантов планов вычисления запроса и выбор плана с минимальными затратами

На последней стадии процесса оптимизации создается набор потенциальных планов запроса, после чего осуществляется выбор лучшего (т. е. наименее дорогостоящего) плана выполнения запроса. Каждый план выполнения формируется как комбинация некоторого набора потенциальных процедур реализации, причем каждой «низкоуровневой» операции в запросе соответствует одна процедура. По сути, стоимость плана — это просто сумма стоимостей отдельных процедур, входящих в его состав.

На практике, вероятно, не стоит генерировать все возможные планы запроса, так как одни из них могут быть комбинаторными версиями других планов выполнения этого же запроса, и сам процесс выбора наиболее эффективного плана может стать чрезмерно дорогостоящим. При выборе плана с наименьшей стоимостью рекомендуется (возможно, даже требуется) руководствоваться некоторыми эвристическими правилами, позволяющими ограничить количество анализируемых планов запросов разумными пределами.

Поскольку все запросы, за исключением самых простых, требуют создания некоторых промежуточных результатов выполнения(по меньшей мере, концептуально), оптимизатор должен быть способен оценить размер этих промежуточных результатов и использовать полученные значения при вычислении формул стоимости. К сожалению, размеры промежуточных наборов данных сильно зависят от конкретных значений хранимых данных, поэтому точная оценка стоимости может оказаться достаточно сложной задачей.

11.2. Низкоуровневая оптимизация операции выборки

Существует несколько различных способов реализации операции выборки F, целесообразность применения которых зависит от структуры файла, в котором хранится отношение, а также от того, какими являются используемые в предикате F атрибуты — индексированными или хешированными. Ниже перечислены основные типы стратегий для простых предикатов (вида A B, где — операция сравнения):

•Линейный поиск (файл не отсортирован, индекс отсутствует) — может потребоваться выполнить просмотр каждого кортежа в каждом блоке или странице, чтобы проверить ее на соответствие заданному предикату.

•Двоичный поиск (упорядоченный файл, индекс отсутствует).

•Поиск по равенству ключа хеширования — если атрибут А является ключом хеширования файла, то для вычисления адреса назначения кортежа используется алгоритм хеширования.

•Условие равенства, применяемое к первичному ключу — для выборки единственного кор-

тежа, удовлетворяющей заданному условию, может использоваться первичный индекс.

•Условие не равенства (ă; ď; ; ą; ě), применяемое к первичному ключу — сначала потре-

буется воспользоваться индексом для поиска кортежа, удовлетворяющей условию равенства.

77

Если значения в индексе отсортированы, требуемые кортежи могут быть извлечены посредством доступа ко всем записям индекса, расположенным выше или ниже найденной.

•Условие равенства, применяемое к кластеризующему (вторичному) индексу.

•Условие равенства, применяемое к некластеризующему (вторичному) индексу.

•Условие неравенства, применяемое ко вторичному индексу в виде B+-дерева, — для по-

иска по условию ă или ď можно выполнить просмотр лист узлов дерева от минимального значения до сравниваемого, а для поиска по условиям ą или ě — от сравниваемого значения до максимального.

Составной предикат может быть представлен в виде конъюнктивной или дизъюнктивной нормальной форме

Если составной предикат не содержит дизъюнктивных выражений, для реализации операции выборки может использоваться один из следующих подходов.

1.Если один из атрибутов в конъюнкте имеет индекс или является упорядоченным, то для выборки строк, удовлетворяющих заданному условию, можно использовать одну из рассмотренных стратегий для простой выборки, предложенных выше. Затем для каждой выбранной строки выполняется проверка на соответствие остальным входящим в предикат условиям.

2.Если выборка включает условие равенства для двух или нескольких атрибутов и для данной комбинации атрибутов существует составной индекс (или ключ хеширования), то можно выполнить прямой поиск в этом индексе (в соответствии с предложенными выше алгоритмами). Тип индекса определяет, какой из алгоритмов будет использован.

3.Если существуют вторичные индексы, созданные для одного или нескольких атрибутов, и эти атрибуты в предикате используются только в условиях поиска по равенству, то в том случае, если в индексах используются указатели на кортежи, а не на блоки данных, можно выполнить просмотр каждого из индексов с целью поиска кортежей, удовлетворяющих отдельным условиям. Затем строится пересечение для всех полученных наборов указателей, образующее результирующий набор указателей, удовлетворяющих всем этим условиям. Если индексы существуют не для всех используемых в предикате атрибутов, то выбранные строки дополнительно проверяются на соответствие оставшимся условиям.

Если одно из выражений в условии выборки содержит дизъюнкцию и это выражение требует выполнения линейного поиска, поскольку для него не существует подходящего индекса или не задан порядок сортировки, то вся операция выборки должна выполняться с помощью операции линейного поиска. Оптимизация операции выборки возможна только в том случае, если индекс или порядок сортировки существует для всех выражений в условии выборки и осуществляется за счет извлечения кортежей, удовлетворяющих каждому условию с последующим объединением полученных результирующих наборов.

11.3. Низкоуровневая оптимизация операции соединения

Операция соединения является самой дорогостоящей из всех операций реляционной алгебры (не считая операции декартова произведения) и одной из самых часто используемых.

Приведем основные стратегии реализации операций соединения:

•Соединение блоками или страницами с использованием вложенных циклов:

Соединение двух отношений выполняется каждый раз по одной строке. Во внешнем цикле выполняется последовательный перебор строк первого отношения R, а во внутреннем цикле последовательно просматриваются все строки второго отношения S. Но поскольку основной единицей обмена при чтении данных на дисковых устройствах является блок или страница, можно улучшить базовый алгоритм, создав еще два дополнительных цикла, предназначенных для обработки считанных с внешнего носителя блоков или страниц.

78

•Индексированное соединение блоками с использованием вложенных циклов:

Если для соединяемых атрибутов внутреннего отношения существует индекс (или хешфункция), то можно заменить неэффективную операцию просмотра файла более эффективным поиском по индексу. Для каждой строки отношения R выборка соответствующих строк отношения S осуществляется с помощью индекса.

•Соединение посредством сортировки слияния:

Для соединений по эквивалентности наиболее эффективный алгоритм реализуется в том случае, если оба отношения отсортированы по соединяемым атрибутам. В этом случае можно отыскать подходящие строки отношений R и S, выполнив слияние двух отношений. Если исходные отношения не отсортированы, можно предварительно выполнить их сортировку. Поскольку строки отношений отсортированы, те из них, которые содержат одинаковые значения соединяемого атрибута, гарантированно будут размещаться рядом.

Если предположить, что соединение выполняется для связи типа ”многие ко многим т. е. в обоих отношениях может существовать несколько строк с одним и тем же соединяемым значением, а также принять, что любой набор строк с одним и тем же соединяемым значением может быть полностью помещен в буфер базы данных, то каждый блок каждого из соединяемых отношений достаточно будет считать только один раз.

•Хешированное соединение:

Алгоритм может использоваться в случае естественного соединения (или эквисоединения) отношений R S но атрибуту . Суть этого алгоритма: на первом этапе, который называется этапом хеширования, происходит разбиение отношений R и S на разделы в соответствии со значениями некоторой хеш-функции, результаты вычисления которой дают равномерно распределенные случайные значения. Каждый полученный эквивалентный раздел отношений R и S должен иметь одни и те же значения соединяемых атрибутов, хотя он может содержать больше одного их значения. Алгоритм предусматривает проверку эквивалентных разделов на наличие одного и того же значения.

На втором этапе, который называется этапом проверки, последовательно считывается каждый из разделов R и предпринимается попытка соединить содержащиеся в нем строки со строками эквивалентного раздела S. Если второй этап выполняется с помощью соединения вложенными циклами, то во внешнем цикле применяется раздел меньшего размера, допустим Ri. Весь раздел Ri считывается в память, после чего с диска считывается каждый блок эквивалентного ему раздела Si и в нем каждая строка используется для проверки наличия соответствующих строк в разделе Ri. Для повышения эффективности обычно в оперативной памяти формируется хеш-таблица для каждого раздела Rj с применением второй хеш-функции, отличной от той, с помощью которой выполняется разбиение отношений на разделы.

11.4.Низкоуровневая оптимизация операций проекции, объеди-

нения, пересечения и разности

Для реализации операции проекции необходимо выполнить следующую последовательность действий.

1.Удаление из отношения ненужных атрибутов.

2.Исключение из результирующей таблицы любых повторяющихся строк, появившихся в результате выполнения предыдущего этапа.

Второй этап выполнить сложнее, чем первый, но он требуется только в том случае, если атрибуты проекции не содержат ключ отношения.

Для теоретико-множественных операций (объединение, пересечение и разность) тоже требуется удаление дубликатов.

Рассмотрим несколько методов удаления кортежей-дубликатов:

79

•Исключение дубликатов с помощью сортировки

Суть данного подхода состоит в сортировке кортежей отношения с использованием всех (оставшихся в случае проекции) атрибутов в качестве ключа сортировки. Это приведет к переупорядочиванию кортежей таким образом, что повторяющиеся строки окажутся рядом и могут быть легко удалены.

•Удаление дубликатов с помощью хеширования

Подход с использованием хеширования может оказаться полезным в тех случаях, если доступное количество буферов блоков носителяпо сравнению с общим количеством блоков отношения R достаточно велико. Хеширование выполняется в два этапа: вначале происходит разбиение на разделы, а затем — удаление дубликатов. На этапе разбиения один буферный блок выделяется для чтения исходного отношения R, а оставшиеся N 1 блоки — для размещения выходных данных. К комбинации атрибутов отношения R применяется хеш-функция hp q

икортеж записывается в буфер в соответствии с вычисленным значением. Хеш-функция hp q выбирается таким образом, чтобы по ее значению все кортежи равномерно распределялись по N 1 разделам. Два кортежа, принадлежащие разным разделам, гарантированно не будут являться дубликатами, поскольку вычисленные для них значения хеш-функции оказались разными. В результате область поиска дубликатов сужается до размера отдельных разделов. На втором этапе выполняются следующие действия:

1)поочередное считывание содержимою каждого из созданных N 1 разделов;

2)применение к каждому считанному кортежу второй (отличной от первой) хэш-функции h2p q;

3)вставка кортежа и вычисленного для него значения в хеш-таблицу, размещенную в оперативной памяти;

4)если значение хеш-функции для некоторого ортежа оказалось таким же, как и для одного из предыдущих кортежей, выполняется проверка, являются ли эти строки одинаковыми, и удаление всех повторяющихся строк, кроме первой;

5)после обработки раздела все его кортежи из хеш-таблицы в оперативной памяти выводятся в результирующий файл.

Литература

1.Дейт К. Дж. Оптимизация / пер. с англ. К. А. Птицына // Введение в системы баз данных (глава 18). — 8-е изд. — М. : Издательский дом „Вильямс“, 2005.

2.Коннолли Т., Бегг К. Обработка запросов / пер. с англ. Р. Г. Имамутдинова, К. А. Птицына // Базы данных: проектирование, реализация и сопровождение (глава 20) / под ред. К. А. Птицына. — 3-е изд. — М. : Издательский дом „Вильямс“, 2003.

80