Оптимизация в System R

Мы сочли необходимым посвятить отдельный подраздел вопросам оптимизации, производимой в System R при компиляции запросов, по причине исключительной важности оптимизационных действий в реляционных СУБД вообще и в System R в частности. Только при наличии развитых оптимизаторов реляционные системы могут достичь приемлемого уровня эффективности.

Вообще с оптимизацией в реляционных системах связан очень широкий спектр проблем, которые мы более последовательно и полно рассмотриваем в отдельной статье [75]. Здесь же мы коротко рассмотрим особенности оптимизации в System R.

Прежде всего отметим, что судя по публикациям в System R применяется достаточно ограниченный набор оптимизационных приемов. Оптимизация главным образом сводится к выбору на основе стоимостных оценок наиболее эффективного способа выполнения компилируемого запроса. В этой постановке задача оптимизации включает два основных компонента: компонент выработки набора способов выполнения запросов и компонент оценки стоимости способа. Очень существенным моментом является обеспечение независимости этих компонентов: важно уметь расширять возможности компилятора за счет ввода новых возможных способов, не затрагивая компонент оценок. Как кажется, подход System R обладает этим свойством декомпозиции компонентов оптимизатора, и может быть поэтому ни в одной публикации не приводится полный перечень применяемых способов выполнения запросов - они меняются от версии к версии. Тем не менее мы постараемся привести обзор наиболее важных способов выполнения запросов на основе всех доступных публикаций.

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

Упоминается еще один способ выполнения запроса на выборку, в котором условие выборки представляет собой логическое выражение, состоящее из простых предикатов сравнения (типа "имя-поля операция-сравнения константа") и включающее только те поля, для которых существуют индексы. Способ состоит в том, что в соответствии с заданными простыми предикатами из индексов выбираются списки tid'ов кортежей, удовлетворяющих предикатам, а затем над этими списками выполняются теоретико-множественные операции объединения и пересечения (объединение соответствует логической операции "или" в логическом условии выборки, пересечение - "и"). Реальная выборка результирующих кортежей производится по произведенному таким образом окончательному списку tid'ов.

Здесь следует заметить, что в System R принято довольно простое решение по поводу выполнения запросов со вложенными подзапросами: они выполняются именно так, как указано в исходном запросе, т.е. до того, как выполняется внешний запрос, формируются результаты всех его вложенных подзапросов и т.д. В принципе это является упрощением; имеются работы, показывающие, что можно преобразовать запрос, содержащий вложенные подзапросы, к одноуровневому запросу, содержащему соединения отношений. При этом запрос в преобразованной форме допускает более эффективное выполнение. В System R оптимизационные преобразования этого типа не употребляются, и это, конечно, является ограничением этой системы. Справедливости ради заметим, что публикации, связанные с преобразованием запросов со вложенностями, появились позже основной части публикаций по System R.

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

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

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

3) Любым способом сканируется отношение S, и поочередно выбираются кортежи. Если очередной кортеж s удовлетворяет предикату ограничения на кортежи S из условия выборки, то этот кортеж заносится в область основной памяти V2, если в ней еще есть место. Если в V2 места уже нет, и значение поля соединения кортежа s меньше значения поля кортежа, находящегося в V2, с наибольшим значением поля соединения, то все кортежи с таким значением поля соединения удаляются из V2, а s - заносится. В противном случае s не заносится в V2. После окончания формирования V2 (завершения сканирования S) сканируется отношение R, и поочередно выбираются кортежи. Если очередной кортеж r удовлетворяет предикату ограничения из условия выборки, V2 просматиривается на предмет наличия кортежей с таким же, как у r, значением полей соединения. Если такие кортежи находятся, производится соединение кортежа r с каждым из них, и формируется очередная порция результирующего отношения. Если при формировании V2 не все кортежи отношения S, удовлетворяющие предикату ограничения, поместились в эту область, производится повторное сканирование отношения S, и формируется новое множество V2, в которое включатся только кортежи со значением полей соединения большим максимального значения поля соединения кортежей в предыдущем варианте V2. Снова сканируется R, и процесс повторяется. Для организации структуры V2 можно использовать двоичные деревья, хэш-таблицы и т.д.

4) Если существуют индексы для отношений R и S на полях соединения и для всех предикатов ограничения, то с использованием индексов ограничения формируются два списка tid'ов кортежей отношений R и S, удовлетворяющих предикатам ограничения. Эти два списка сортируются и заносятся в файлы R1 и S1. Путем параллельного просмотра индексов на полях соединения R и S находятся пары tid'ов кортежей, являющихся участниками соединения (без учета ограничений). Для каждой такой пары (tid1, tid2) проверяется, присутствуют ли tid1 в R1, а tid2 - в S1 (т.е. удовлетворяют ли кортежи предикатам ограничения). Если эти условия выполнены, соответствующие кортежи читаются и соединяются, образуя очередной кортеж результирующего отношения.

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

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

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

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

Для оценки стоимости плана выполнения запроса в различных генерациях System R могут использоваться разные меры (в [19] рассматриваются оценки стоимости в денежной и временной мерах). В оценочных формулах фигурируют число обменов с внешней памятью, которые по оценкам оптимизатора потребуются при выполнении запроса по данному плану, и оценка процессорного времени, требующегося для выполнения запроса (при этом время оценивается предполагаемым числом обращений к RSS при выполнении запроса по данному плану). Число обменов и число обращений к RSS, встречающиеся в оценочных формулах, подгоняются под единую меру за счет использования соответствующих коэффициентов. Числовые значения коэффициентов зависят от выбранной меры стоимости. Например, если мерой выступает время выполнения запроса, то определяющей составляющей стоимости должно быть число обменов; при выборе денежной меры больший вес должно иметь время процессора.

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

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

Набор оценочных формул, применяемых в оптимизаторе System R, описан в [19].

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

1) предполагается, что значения всех полей любого отношения распределены независимо;

2) предполагается, что значения любого поля любого отношения распределены равномерно.

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

В заключение заметим, что в настоящее время существует ряд работ, авторы которых пытаются решить проблему более точных оценок, используя достаточно простую статистику. Мы остановимся на этом в отдельной статье [75].

Назад | Содержание | Вперед