Оптимизаторы с гибкой структурой

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

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

В то же время, на самом деле единственным по-существу жестким компонентом СУБД является компонент, связанный с физической организацией баз данных на внешней памяти и осуществляющий доступ к данным нижнего уровня (например, RSS в System R). В принципе СУБД допускает любую стратегию выполнения запроса, не выходящую за пределы возможностей этого компонента. На этом и основана идея подхода, который мы рассмотрим в этом подразделе. Этот подход достаточно новый, публикаций на эту тему пока немного, и мы ограничимся рассмотрением одной работы [104], которая, на наш взгляд, характерна для подхода в целом. При этом мы не будем касаться деталей организации СУБД Starburst, с разработкой которой связана статья, а сосредоточимся исключительно на особенностях оптимизатора запросов этой системы.

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

Для функционирования оптимизатора должно быть задано множество планов, описывающих стратегии выполнения операций, STARs (Strategy Alternative Rules). Правила формулируются на специально разработанном языке. Каждое правило определяет именованный, параметризованный объект в терминах одного или более альтернативных определений. Альтернативные определения выражаются в терминах одного или более других STAR или примитивных предопределенных операторов LOLEPOP (Low-Level-Plan-Operator). В терминах System R LOLEPOP соответствует оператору интерфейса RSS. Примером STAR может быть следующее правило:

                          ¦ ACCESS (Heap, T, C, P)
                          ¦
                          ¦ IF Storage (T) = 'heap'
                          ¦
                          ¦ ACCESS (BTree, T, C, P)
                          ¦
    TableScan (T, C, P) = + IF Storage (T) = 'Btree'
                          ¦
                          ¦ ACCESS (RTree, T, C, P)
                          ¦
                          ¦ IF Storage (T) = 'Rtree'
                          L

Параметры STAR Tablescan T, C и P задают, соответственно, имя отношения, набор выбираемых столбцов и простой предикат выборки. ACCESS - LOLEPOP, соответствующий доступу на физическом уровне к очередному кортежу отношения, организованному одним из допустимых в Starburst способов. Правило TableScan означает, что для сканирования отношения может быть использован LOLEPOP ACCESS в одном из трех режимов в соответствии с типом физической организации отношения. В этом примере альтернативные определения являются взаимоисключающими, поскольку каждое отношение физически организовано только одним из трех способов. В общем случае взаимное исключение не требуется. Например, STAR TableAccess, определяющее возможный доступ к отношению, может иметь вид:

TableAccess (T, C, P) =
   ¦TableScan (T, C, P)
   ¦
   +FOR ALL i IN I(T): GET (TableScan (i, {TID}, P}, T, C, P)
   ¦
   ¦  IF CONDITION1
   L

Это правило при том же смысле параметров T, C и P, что и в предыдущем примере, задает множество допустимых стратегий доступа к отношению. Необходимые пояснения: считается, что каждое отношение включает предопределенное поле с именем TID, содержащее уникальные идентификаторы кортежей. GET - это LOLEPOP, обеспечивающая доступ к кортежу отношения по его TID'у. Наконец, вторая альтернатива будет рассматриваться только в том случаю, если к моменту рассмотрения оптимизатором этого правила условие CONDITION1 будет истинным, и при этом будет порождено множество стратегий доступа к отношению на основе всех определенных на его полях индексов. Заметим, что STAR TableScan, используемое в определении STAR TableAccess, не соответствует приведенному ранее определению Tablescan: в этом определении отсутствовала альтернатива сканирования через индекс. Соответствующее расширение определения очевидно. Еще раз подчеркнем, что альтерантивы STAR TableAccess не являются взаимно исключающими. Это правило порождает множество стратегий.

В результате работы оптимизатора под управлением заданного набора правил порождается множество планов выполнения запроса (QEP - Query Evaluation Plan). Каждый план представляет собой совокупность вложенных вызовов LOLEPOP. Интерпретация каждого плана соответствует выполнению запроса. При этом правила формулируются таким образом, что при выработке каждого плана автоматически формируется его оценка. Коротко рассмотрим, как реально обрабатывается запрос в оптимизаторе СУБД Starburst под управлением заданного набора правил.

Работа компонента оптимизатора, генерирующего альтернативные планы выполнения запроса и производящего оценки порождаемых планов на основе набора правил (STAR-процессора), основывается на наличии четырех структур памяти: массива, в котором хранятся STAR во внутреннем представлении; области, содержащей сгенерированные "хорошие" планы с разными свойствами (понятие хорошего плана и его свойств мы уточним ниже); дерева вызовов, хранящего структуру вызовов STAR; списка указателей еще не обработанных вызовов. Первые две структуры сохраняются в процессе оптимизации в то время, как две последние создаются в рабочей области, выделяемой при каждом вызове STAR-процессора. Массив STAR - внешний параметр оптимизатора, остающийся неизменным в процессе оптимизации; "хорошие" планы, т.е. наиболее дешевые планы выполнения с разными свойствами, порождаются в ходе оптимизации.

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

На первой фазе производятся действия, аналогичные действиям макропроцессоров: каждый узел в дереве вызовов заменяется на его определение применением соответствующего правила из STAR-массива с подстановкой аргументов старого узла вместо параметров определения. Все аргументы, являющиеся вызовами, обрабатываются таким же образом. Этот процесс продолжается, пока не будут обработаны все вызовы. Порядок обработки узлов определяется приоритетами, присваиваемыми каждому вызову в списке необработанных вызовов.

При вызове STAR-процессора с TableAccess (EMP, {NAME, ADDRESS}, {EMP.SAL < 30.000, EMP.AGE > 45}) дерево вызовов инициализируется таким образом, как показано на Рис.4. Далее в STAR-массиве ищется STAR с именем TableAccess. Пусть, как и раньше, определение TableAccess имеет вид

TableAccess (T, C, P) =
   ¦TableScan (T, C, P)
   ¦
   +FOR ALL i IN I(T): GET (TableScan (i, {TID}, P}, T, C, P)
   ¦
   ¦  IF CONDITION1
   L

Имеются два альтернативных определения: первая альтернатива вызывает STAR с именем TableScan, вторая - LOLEPOP с именем GET. Пусть условие CONDITION1 - истинно, и I (EMP) = {INDEX1, INDEX3}. Вторая альтернатива повторяется для каждого i, принадлежащего I (T).

При подстановке параметров для каждого нового узла каждый параметр в определении заменяется на соответствующий аргумент в вызове. Например, параметр T заменяется на EMP. Во втором альтернативном определении первый параметр является вызовом STAR с именем TableScan, на который указывает ссылка из первого аргумента узла GET. Указатель на TableScan получает приоритет и заносится в список необработанных вызовов.

Дерево вызовов после выполнения одной итерации первой фазы алгоритма показано на Рис.5. Для выработки плана, т.е. полной редукции всех STAR к LOLEPOP, потребуются еще по крайней мере три итерации, поскольку в дереве имеется STAR TableScan, не сведенное к LOLEPOP.

На второй фазе обработка начинается с наиболее вложенного LOLEPOP (обычно это LOLEPOP ACCESS, относящийся к хранимой таблице). Обработка производится "снизу вверх" с вызовом функции свойств каждого LOLEPOP. Каждая функция использует параметры вызова LOLEPOP, включая планы и их свойства. Стоимость рассматривается как часть вектора свойств и считается для каждого LOLEPOP как сумма его собственной стоимости и стоимостей всех его входных параметров-планов.

Предположим, что в нашем примере в полностью расширенной форме получаются два альтернативных плана:

	ACCESS (HEAP, EMP, {NAME, ADDRESS},
	{EMP.SAL < 30.000, EMP.AGE > 45}) и
	GET (ACCESS (BTree, INDEX1, {TID}, EMP.AGE > 45),
	EMP, {NAME, ADDRESS}, EMP.SAL < 30.000).

В первой альтернативе нет вложенности, поэтому нужно вызвать только функцию свойств для LOLEPOP ACCESS. Эта функция выработает вектор свойств, характеризующих стоимость и эффект этого плана: из отношения EMP будут выбираться значения полей NAME, ADDRESS и TID (TID выбирается всегда) с применением предикатов на SAL и AGE; при выборе не будет поддерживаться какой-либо порядок кортежей.

Во второй альтернативе наиболее вложенный LOLEPOP ACCESS с INDEX1. Функция свойств этого LOLEPOP выработает вектор свойств, содержащий информацию от том, что выбираются только TID'ы кортежей EMP; применяется только предикат на AGE; кортежи выбираются в порядке возрастания значений поля AGE. Теперь можно вычислить функцию свойств LOLEPOP GET по его входным параметрам и их свойствам (для первого параметра). Функция свойств для GET объединяет имена полей, которые предписано выбирать GET, c именами полей, обеспечиваемых входным потоком (определяемым первым аргументом). То же касается предикатов. Следовательно, в векторе свойств GET будет указано, что выбираются значения полей NAME, ADDRESS, TID под управлением предикатов EMP.SAL < 30.000 и EMP.AGE > 45. Эти свойства идентичны свойствам предыдущей альтернативы. Однако свойства порядка кортежей иные.

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

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

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

Следуя [104], мы изложили только общие идеи построения управляемого прпвилами оптимизатора. Интересные проблемы, не отраженные в [104], связаны с построением языка описания правил и проверкой корректности системы правил при формировании их внутреннего представления. Нам неизвестны публикации, в которых рассматривались бы эти проблемы, хотя, поскольку система Starburst функционирует, в ней они каким-то образом решены.

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