Расширяемая, управляемая правилами оптимизация путем перезаписи запросов в Starburst

Хамид Пирамеш, Джозеф Хеллерстейн, Вакар Хасан

Перевод: Сергей КузнецовКузнецов (Кузнецова)— одна из самых распространённых русских фамилий. В «Списке общерусских фамилий», занимает 3 место. Самым распространённым сочетанием фамилии имени и отчества в России в XX веке считался Кузнецов Николай Иванович

ОригиналОригинал(от лат. originalis - первоначальный) — первоначальный, подлинный.: Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan. Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD International Conference on Management of Data, 1992. Текст доступен здесь.

Содержание

1. Введение

1.1 Запросы с путевыми выражениями

1.2 Замысел системы

1.3 Родственные работы

1.4 Структура статьи

2. Графовая модель запросов в Starburst

2.1 Среда для измерения эффективности

3. Набор правил перезаписи для гарантирования поглощения SELECT

3.1 Правила, гарантирующие поглощение представлений

3.2 Гарантирование слияния подзапросов с квантором существования

4. Процессор правил

5. Заключение: процессор и правила

6. Благодарности

Литература

Аннотация

В этой статье описывается средство перезаписи запросов (Query Rewrite) расширяемой системы баз данных Starburst. На использовании этого средства основывается новая фаза оптимизации запросов. Мы представляем набор правил перезаписи, используемых в Starburst для преобразования запросов в эквивалентные запросы для более быстрого выполнения, а также описываем процессорЦентральный процессор (ЦП, или центральное процессорное устройство— ЦПУ; англ.central processing unit, сокращенно— CPU, дословно— центральное обрабатывающее устройство)— электронный блок либо микросхема — исполнитель машинных инструкций (кода программ), главная часть аппаратного обеспечения компьютера или программируемого логического контроллера. Иногда называют микропроцессором или просто процессором. Изначально термин центральное процессорное устройство описывал специализированный класс логических машин, предназначенных для выполнения сложных компьютерных программ. Вследствие довольно точного соответствия этого назначения функциям существовавших в то время компьютерных процессоров, он естественным образом был перенесён на сами компьютеры. Начало применения термина и его аббревиатуры по отношению к компьютерным системам было положено в 1960-е годы. Устройство, архитектура и реализация процессоров с тех пор неоднократно менялись, однако их основные исполняемые функции остались теми же, что и прежде. продукционных правил, который используется в Starburst для выбора и выполнения этих правил. Приводятся примеры, демонстрирующие, что преобразования, которые производит Query Rewrite, приводят к сокращению времени выполнения на порядки. Это говорит о том, что перезапись запросов вообще и эти правила перезаписи в частности являются существенным шагом вперед в оптимизации запросов в современных системах баз данных.

1. Введение

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

В Query Rewrite преследуются две цели:

1. Сделать запросы как можно более декларативными: В языках баз данных, таких как SQL, часто возможны неудачно сформулированные запросы, являющиеся якобы декларативными, но навязывающие типичному оптимизатору планов выбор неоптимальных планов выполнения. Основная цель Query Rewrite состоит в том, чтобы преобразовать эти «процедурные» запросы в эквивалентные, но более декларативные запросы.
2. Использовать естественные эвристики: В Query Rewrite могут применяться некоторые эвристики, которые расцениваются в литературе как значимые. Типичным примеров этого является «проталкивание предикатов» («predicate pushdown»), когда предикаты применяются в запросе как можно раньше (т.е. они «проталкиваются» из своих исходных позиций ближе к обращениям к таблицам, в подзапросы, представления и т.д.). Такие правила могут существенно сократить время выполнения запроса, и хотя некоторые из этих эвристик используются в типичных оптимизаторах планов, при использовании Query Rewrite они могут применяться гораздо более общим образом.

Хотя принятой доктриной является то, что языки запросов должны быть декларативными, в своих примерПример рассматривается в риторике чаще всего в контексте доказательств и аргументов. Для Квинтилиана пример является одним из дополняющих, наглядных доводов к высказыванию, либо упоминанием полезного, настоящего или якобы существующего образца убеждения того, что определено тобой одним. Правда, в отличие от доказательств, связь с предметом обсуждения должна быть установлена прежде автором или оратором.ах мы покажем, что альтернативные, но эквивалентные формулировки запросов могут значительно изменять эффективность, часто на порядки. Отсюда происходит наше убеждениеУбеждение— элемент мировоззрения, придающий личности или социальной группе уверенность в своих взглядах на мир, знаниях и оценках реальной действительности. Убеждения направляют поведение и волевые действия. в том, что Query Rewrite является существенным шагом вперед в оптимизации запросов, поскольку этот компонентКомпонент— (от лат.componens, родительный падеж componentis — составляющий), составная часть, элемент чего-либо. В разных отраслях науки и техники может иметь дополнительное, более специфическое значение. гаранирует отсутствие влияние исходной формулировки запроса на эффективность его выполнения.

1.1 Запросы с путевыми выражениями

Цели перезаписи запросов, разъясненные выше, являются даже более существенными в объектно-ориентированных приложениях, в которых обычно генерируются усложенные запросы с «путевыми выражениями», связывающими разнообразные коллекции объектов [BTA90, LLOW91, LLPS91]. В таких приложениях как сложность логики, так и объем данных гораздо больше, чем в тридиционных приложениях СУБД [HSS88]. В результате возрастает важность оптимизации запросов.

Ниже приводится пример запроса с путевым выражением, представленный в синтаксисе Object SQL [BTA90]¹. Этот запрос является немного измененным примером, представленным в [BTA90]. База данных в примере содержит записи о пациентах. Медицинские записи являются множественными характеристиками пациентов. Все обращения к данным производятся через методыМетод (от греч. — «способ»)— систематизированная совокупность шагов, действий, которые необходимо предпринять, чтобы решить определенную задачу или достичь определенной цели. В отличие от области знаний или исследований, является авторским, то есть созданным конкретной персоной или группой персон, научной или практической школой. В силу своей ограниченности рамками действия и результата, методы имеют тенденцию морально устаревать, преобразовываясь в другие методы, развиваясь в соответствии с временем, достижениями технической и научной мысли, потребностями общества. Совокупность однородных методов принято называть подходом. Развитие методов является естественным следствием развития научной мысли.. Для заданной записи пациента медицинские записи возвращаются функцией get_medical_records. В примере выбираются записи о пациентах мужского пола, которым поставлен диагноз «малярия» (malaria) или «оспа» (smallpox) до '10/10/89'. В разделе FROM перечисляются пациенты, а в разделе WHERE пациенты ограничиваются до лиц мужского пола, и проверяется наличие диагнозов малярии или оспы, поставленных до указанной даты.

SELECT DISTINCT P
FROM Patient p IN Patient_Set
WHERE p.sex == 'male' &&
  EXISTS ( SELECT r
           FROM Medical_record r IN p.get_medical_record()
           WHERE r.get_date() < '10/10/89' &&
            (r.get_diagnosis() == 'Malaria' ||
             r.get diagnosis() == 'Smallpox');

В подобных запросах существенным образом используются путевые выражения, в которых для данной записи родственная информацияИнформация (от лат.informatio— осведомление, разъяснение, изложение, от лат.informare— придавать форму)— в широком смысле абстрактное понятие, имеющее множество значений, в зависимости от контекста. В узком смысле этого слова— сведения (сообщения, данные) независимо от формы их представления. Сведения об объектах живой или неживой природы, их свойств и взаимном влиянии друг на друга. получается через путь (например, взятие медицинских записей пациента). Запросы с путевыми выражениями очень распространены в сложных приложениях, таких как CAD/CAM. В общем случае запрос может включать много путевых выражений, и длина каждого из них может быть больше единицы. Нахождение эффективного плана выполнения для таких путевых выражений является проблемой, очень похожей на проблему оптимизации (вложенных) подзапросов SQL. Приведенный выше запрос обычно выполняется путем перечисления пациентов мужского пола и проверки медицинских записей для каждого пациента, проверки предикатов по дате и диагнозДигноз (греч. — распознавание)— заключение о сущности болезни и состоянии пациента, выраженное в принятой медицинской терминологии и основанное на всестороннем систематическом изучении пациента. Процесс установления диагноза называется диагностикой.у. Это равнозначно соединению с вложенным циклом, в котором порядок соединения диктуется пользователем – подзапрос обязательно является внутреннем циклом.

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

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

Дубликаты могут появляться даже и без преобразований запросов. Записи-дубликаты часто появляются в базовых или промежуточных результатах в приложениях и имеют большое значение для запросов с агрегатными функциями, например, запросов, в которых требуется среднее значение некоторого столбца. Дубликаты входят в модель SQL [ISO91] и ОО-модели, такие как [LLOW91] (как «мультимножества объектов» («bags of objects»). Потребность и важность допущения дубликатов в реалистичных реализациях являются общепризнаными, особенно в реляционных СУБД (РСУБД). Поэтому важно аккуратно обращаться с дубликатами, и этот вопрос находится в центре работы, представленной в этой статье.

1.2 Замысел системы

Естественно, мы не предлагаем находить оптимальное представление запроса, как и традиционные «оптимизаторы» планов не находят оптимального плана выполнения запроса. Скорее, мы строим набор эвристик перезаписи запросов, выражаемых в виде продукционных правил, которые работают вместе для достижения двух указанных выше целей перезаписи. Эти правила продукции управляются процессором правил, написанном именно для этого и интегрированным в Starburst. Разработка системы правил способствовала проведению наших экспериментов с преобразованиями запросов в двух отношениях.

Во-первых, парадигма системы правил облегчила нам использование усложеннных инициирующих взаимодействий между правилами перезаписи, оградив нас от задачи явной трассировки потокаПотока (болг. Потока) — село в Болгарии. Находится в Смолянской области, входит в общину Смолян. Население составляет 11 человек. управления между правилами. Часто это считают опасной сложностью систем правил ([ZH90], [Ras90], [HH91] и т.д.), но по нашему опыту система оказалась не только управляемой, но и действительно полезной. Во-вторых, система правил является отличной платформой для расширяемости, одной из ключевых целей Starburst. Эта расширяемостьРасширяемость (англ.extensibility) означает возможность сравнительно легкого добавления отдельных элементов сети (пользователей, компьютеров, приложений, служб), наращивания длины сегментов сети и замены существующей аппаратуры более мощной. позволила нам написать и проверить за последние два года десятки преобразований запросов, включая те, которые представлены в этой статье, преобразования на основе магических множеств [MFPR90a, MPR90, MFPR90b] и многие другие.

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

1.3 Родственные работы

Разработчики ранних РСУБД, таких как System R [ABC+ 76] и INGRES [SWK76] осознавали важность подстановки представлений и решали эту задачу для частных случаев. Несмотря на признанную важность таких преобразований, эти ранние схемы преобразований были применены лишь в немногих системах.

Ким [Kim82] первым задался вопросом о том, когда квантифицированные подзапросы можно заменить соединениями (или антисоединениями). Гански (Ganski) и Вонг (Wong) [GW87] и Дайал (Dayal) [Day87] проделали дополнительную работу по устранению вложенных подзапросов. В этих статьях признается важность поглощения подзапросов. В [Kim82, GW87] также решается проблемаПроблема (др.-греч. ) — положение, причинность, условие, вопрос, объект, который создаёт затруднение, побуждает к действию и связан с избыточностью или недостатком чего либо для сознания субъекта,например: процессора (движителя, калькулятора, компьютера,специалиста), знаний, ресурсов, регламента (упорядоченности, алгоритма, программы) и побуждает к действию или ограничивает его и соответственно неразрешён или нежелателен. В природе, вне деятельности человека, проблемы находят естественное разрешение и в последовательности движения форм материи есть этап в наблюдениях формализуемый человеком. Отличие природного процесса, разрешение проблемы как результат законов природы. Сущность проблемы для человека такова, что требует анализа, оценки, формирования идеи, концепции для поиска ответа (решение проблемы) с проверкой и подтверждением опытом. В природе это: Вода течёт вниз. Ветер качает деревья. Вода камень точит. и др., что естественно и непротиворечиво. ПРОБЛЕМОЙ преимущественно называется вопрос, не имеющий однозначного решения (степень неопределённости). Неопределённостью проблема отличается от задачи. Совокупность возможных вопросов взаимосвязанных объектом рассмотрения называется проблематикой. подзапросов, содержащих агрегацию. Мы описывали наш набор правил для работы с такими подзапросами в [MFPR90a, MPR90, MFPR90b].

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

Мы уделяем особое внимание ортогональности языка. Поэтому такие операции как UNION, INTERSECT и EXCEPT (эквивалент вычитания множеств в SQL) могут появляться в подзапросах, как этого и требует стандарт SQL [ISO91]. В упомянутых выше работах этим более сложным подзапросам вниманиеВнимание— избирательная направленность восприятия на тот или иной объект. не уделяется. Кроме того, наши правила гарантируют поглощение конъюнктов подзапросов с кванторами существования, состоящих из ограничения, проекции и соединения. Частично это стало возможным благодаря нашему аккуратному обращению с дубликатами.

Анфиндсен (Anfindsen) [Anf89] также провел исследования преобразований подзапросов, используя РСУБД DB2 для измерений эффективности. Как и мы, Анфиндсен отмечает улучшениеУлучшение— комплексная термической обработки металлов, включающая в себя закалку и последующий высокий отпуск. производительности на порядки. Однако автор ограничивается только преобразованиями, выдающими SQL-запрос, который может быть обработан DB2. В отличие от этого, наш подход является составной и интегральной частью РСУБД, что позволяет использовать более развитый внутренний язык и, следовательно, дает возможность производить большее число оптимизационных преобразований. Анфиндсен определяет понятие, близкое нашему условию-одного-кортежа (one-tuple-condition), поясняемому ниже, и приводит достаточные условия его удовлетворения.

К Starburst было добавлено много расширений [LLPS91], включая XNF, систему, поддерживающую запросы сложных объектов, в которой часто генерируются исключительно сложные SQL-запросы. Наша система выдержала испытание при использовании этими расширениями и в действительности именно она обеспечивает эффективную работу некоторых из них.

Работу, представленную в этой статье, не следует путать со средством перезаписи запросов в POSTGRES [SJGP90]. Перезапись запросов в POSTGRES является частью реализации для поддержки активной базы данных. В POSTGRES можно определить правило, говорящее о том, что поступающие запросы должны выполнять дополнительные или полностью другие действия по сравнению с теми, которые указал пользователь. В некоторых ситуациях POSTGRES реализует эту идею путем перезаписи запросов. Кстати, заметим, что преобразования запросов в POSTGRES направлены на изменение семантики запросов, а не эффективности. Например, перезапись в POSTGRES может использоваться для того, чтобы реализовать определяемую пользователями семантику обновлений представлений. В отличие от этого, мы делаем акцент на преобразовании в целях оптимизации выполнения запросов.

Ранняя версия системы правил Starburst Query Rewrite описана в [HP88].

1.4 Структура статьи

В разд. 2 описывается абстрактноеАбстракция (от лат.abstractio— «отвлечение»)— отвлечение в процессе познания от несущественных сторон, свойств, связей предмета или явления с целью выделения их существенных, закономерных признаков; абстрагирование; теоретическое обобщение как результат такого отвлечения. представление запросов, используемое в правилах перезаписи. Сами правила приводятся в разд. 3. В разд. 4 описывается процессор правил, разработанный для Query Rewrite. В разд. 5 содержится сводка результатов и заключение.

2. Графовая модель запросов в Starburst

Запросы внутри системы представляются в графовой модели (Query Graph Model, QGM). ЗадачаЗадача— проблемная ситуация с явно заданной целью, которую необходимо достичь; в более узком смысле задачей также называют саму эту цель, данную в рамках проблемной ситуации, то есть то, что требуется сделать. В первом значении задачей можно назвать, например, ситуацию, когда нужно достать предмет, находящийся очень высоко; второе значение слышно в указании: «Ваша задача — достать этот предмет». Несколько более жёсткое понимание «задачи» предполагает явными и определёнными не только цель, но и условия задачи, которая в этом случае определяется как осознанная проблемная ситуация с выделенными условиями (данным) и требованием (целью). Ещё более узкое определение называет задачей ситуацию с известным начальным состоянием системы и конечным состоянием системы, причём алгоритм достижения конечного состояния от начального известен (в отличие от проблемы, в случае которой алгоритм достижения конечного состояния системы не известен). QGM состоит в обеспечении более мощного и концептуально более управляемого представления запросов для уменьшения сложности компиляции и оптимизации запросов. В QGM поддерживаются произвольные операции над таблицами, операндами и результатами которых являются таблицы. Примерами операций являются SELECT, GROUP BY, UNION, INTERSECT и EXCEPT. Операция SELECT является частью Starburst SQL, обрабатывающей ограничение, проецирование и соединение.

Мы представляем граф QGM на примере. Предположим, что имеется следующий SQL-запрос:

SELECT DISTINCT q1.partno, q1.descr, q2.suppno
FROM inventory q1, quotations q2
WHERE q1.partno = q2.partno AND q1.descr='engine'
  AND q2.price ≤ ALL
         (SELECT q3.price FROM quotations q3
          WHERE q2.partno=q3.partno);

Рис. 1. Пример QGM-графа

Этот запрос выдает информацию о поставщиках и деталях, для которых цена данного поставщика меньше, чем у всех других поставщиков. На рис. 1 показана QGM для этого запроса. Граф состоит из четырех блоков. Блоки 1 и 2 ассоциированы с базовыми таблицами inventory и quotations. Блок 3 является блоком SELECTSELECT ("селект") — оператор DML языка SQL, возвращающий набор данных (выборку) из базы данных, удовлетворяющих заданному условию., ассоциированным с основной частью запроса, и блок 4 – это блок SELECT, ассоциированный с подзапросом. У каждого блока имеется заголовок и тело. Заголовок описывает результирующую таблицу, производимую блоком, а тело специфицирует операцию, требуемую для вычисления результирующей таблицы. Можно считать, что для базовых таблиц имеются пустые блоки, или что блоки для них не существуют.

Исследуем блок 3. В заголовке указаны столбцы результатРезультат— заключительное последствие последовательности действий или событий, выраженных качественно или количественно. Возможные результаты включают преимущество, неудобство, выгоду, потерю, ценность и победу.а partno, descr и suppno в соответствии со списком выборки запроса. СпецификацияСпецификация— (позднелат.specificatio, от лат. species - род, вид, разновидность и facio - делаю) инженерный термин, обозначающий набор требований и параметров, которым удовлетворяет некоторая сущность. К примеру, мост через реку удовлетворяет таким параметрам, как максимальный общий вес нагрузки, максимальная нагрузка на ось, максимальная скорость ветра ит.д. этих столбцов включает имена столбцов, типы и информацию об упорядоченности результата. В заголовке имеется булевский атрибут, называемый distinct, который указывает, содержит ли соответствующая таблица только различные кортежи (head.distinct = TRUE), или в ней содержатся дубликаты (head.distinct = FALSE).

Тело блока содержит граф. Вершины графа (черные круги в нашей диаграмме) представляют квантифицированные кортежные переменные, называемые квантификаторами. В блоке 3 имеются квантификаторы q1, q2 и q4. Областями определения квантификаторов q1 и q2 являются базовые таблицы inventory и quotations соответственно, и эти квантификаторы соответствуют ссылками на таблицы в разделе FROM SQL-запроса. Заметим, что узлы q1 и q2 связаны межблочными дугами с заголовками inventory и quotations. Дуга между q1 и q2 специфицирует предикат соединения. (Циклическая) дуга, присоединенная к q1, соответствует локальному предикату на q1.

В действительности, единственная межквантификаторная дуга представляет конъюнкт раздела WHERE в блоке запроса – конъюнкты представляются в диаграмме помеченным прямоугольником на дуге. Такие дуги также называются булевскими термами [SAC+79]. Квантификатор 3 является квантором всеобщности, ассоциированным с подзапросом ALL в разделе WHERE. Это выражает тот факт, что для всех кортежей, ассоциированных с q4, предикат, который представлен дугой между q2 и q4, является true.

В блоке 3 q1 и q2 участвуют в соединениях, и их столбцы используются в кортежах результата. Эти квантификаторы имеют тип F, поскольку они происходят из раздела FROM запроса. У квантификатора q4 тип A, представляющий квантор всебщности (ALL). Предикаты SQL EXISTS, IN, ANY и SOME принимают значение true, если, по крайней мере, один кортеж подзапроса удовлетворяет предикату. Следовательно, все эти предикаты являются экзистенциальными, и у квантификаторов, ассоциированных с такими подзапросами, имеется тип E. Каждый квантификаторКвантор— общее название для логических операций, ограничивающих область истинности какого-либо предиката. помечается столбцами, которые ему требуются из таблицы, являющейся его областью определения.

Блок 4 представляет подзапрос. Он содержит F-квантификатор q3 над таблицей quotations, и в нем имеется предикат, ссылающийся на q2 и q3.

В теле каждого блока имеется атрибут, называемый distinct, который может иметь значения ENFORCE, PRESERVE или PERMIT. ENFORCE означает, что операция должна удалять дубликаты, чтобы обеспечивать head.distinct = TRUE. PRESERVE означает, что операция может сохранять численность дубликатов, которые она порождает. Так может быть потому, что head.distinct = FALSE, или потому, что head.distinct = TRUE, но никакие дубликаты не могут существовать в результате операции даже без удаления дубликатов. PERMIT означает, что операции разрешается удалять (или генерировать) дубликаты произвольным образом. Например, у атрибута distinct блока 4 может иметься значение PERMIT, потому что этот блок используется в кванторе всеобщности (q4 в блоке 3), а кванторы всеобщности нечувствительны к кортежам-дубликатам. Это рассматривается более подробно в разд. 3.

Как и у каждого тела блока, у каждого квантификатора имеется атрибут distinct со значениями ENFORCE, PRESERVE или PERMIT. ENFORCE означает, что для квантификатора требуется обеспечение удаления дубликатов из таблицы, являющейся его областью определения. PRESERVE означает, что в этой таблице должно быть сохранено точное число дубликатов, и PERMIT означает, что в ней может содержаться произвольное число дубликатов. У квантификаторов существования и всеобщности всегда может иметься distinct = PERMIT, поскольку они нечувствительны к дубликатам.

Для каждого выходного столбца в теле может иметься ассоциированное выражение, которое соответствует выражению, допустимому в списке SELECT. На рис. 1 все эти выражения просто идентифицируют функции над столбцам квантификаторов.

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

РезультатРезультат— заключительное последствие последовательности действий или событий, выраженных качественно или количественно. Возможные результаты включают преимущество, неудобство, выгоду, потерю, ценность и победу. блока может использоваться несколько раз (например, представление можно использовать несколько раз в одном запросе), что создает общие подвыражения. Рекурсивные запросы создают циклы в QGM. По мере роста размеров графа возрастает и стоимость оптимизации. У запроса обычно обычно имеется 2-10 QGM-блоков. У существенно более сложных запросов, например, производимых XNF, это число составляет 10-100.

2.1 Среда для измерения эффективности

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

Для полной оценки производительности требуются определение тестовой базы данных и набор запросов для конкректной рабочей нагрузки. Мы ориентируемся на рабочую нагрузку сложных запросов (включающих подзапросы, представления и т.д.), а не на транзакционную рабочую нагрузку, где запросы относительно просты. Стандартная рабочая нагрузка сложных запросов отсутствует, хотя имеется несколько предложений ([TOB89, O'N89]). Для измерения воздействия на эффективность правил перезаписи мы используем вариант тестовой базы данных IBM DB2, описанной в [Loo86], объем которой увеличен в 10 раз.

Таб. 1. Тестовая база данных

Тестовая база данных DB2 основана на приложении отслеживания запасов (inventory) и контроля их уровня. У рабочих центров (workcenter) имеются месторасположения (locations, locatn). Изделия (item, itm) обрабатываются в месторасположениях рабочих центров, и эта связь сохраняется в таблице itl. Запись об изделиях, которые обрабатываются конкретным служащим, сохраняется в таблице wor. Для каждого изделия могут иметься заказы (itp). Некоторые физические характеристики этой базы данных показаны в таб. 1.

Поскольку система Query Rewrite может производит SQL-представления своих результатов, мы можем легко измерять ее воздействиеВоздействие— активное влияние субъекта на объект, не обязательно явное или с обратной связью. на широко используемые коммерческие СУБД. Это позволяет нам демонстрировать общую применимость перезаписи запросов для типичных СУБД, а не только для Starburst. Наши измерения производительности были проделаны для реляционной СУБД DB2. Мы измеряли использованное время (общее время, затраченное системой для выполнения запроса) и время ЦП (время занятости ЦП) для каждого запроса до и после применения правил перезаписи. Оба представления запроса проходили через обычный процесс компиляции запросов DB2, включая оптимизацию плана. Количественные показатели производительности приводятся в разд.3.

¹⁾ Этот язык предлагается в качестве стандартСтандарт (от англ.standard— норма, образец) в широком смысле слова— образец, эталон, модель, принимаемые за исходные для сопоставления с ними др. подобных объектов.ного объектно-ориентированного языка запросов и реализуется в некоторых коммерческих ООСУБД.

Содержание Вперёд