LEO: самонастраивающийся оптимизатор запросов для DB2

2003 г

LEO: самонастраивающийся оптимизатор запросов для DB2

Волкер Маркл, Гай Лохман, Виджайшанкар Раман
24.04.2003

Перевод - Сергей Кузнецов
Открытые системы, #04/2003

Оригинал: V. Markl, G. M. Lohman, V. Raman. LEO: An autonomic query optimizer for DB2. IBM SYSTEMS JOURNAL, VOL 42, NO 1, 2003.

Структурированный язык запросов (Structured Query Language, SQL) стал производственным стандартом для формулировки запросов к реляционным системам управления базами данных главным образом потому, что пользователям нужно только указать, какие данные им требуются, не вдаваясь в подробности о том, как произвести доступ к этим данным.

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

В оптимизаторе запросов используется математическая модель выполнения запросов для автоматического определения наилучшего способа доступа к данным и обработки любого заданного SQL-запроса. Эта модель существенно зависит от того, как оптимизатор оценивает число строк, которые будут получены на каждом из шагов плана выполнения запроса (query execution plan, QEP), особенно для сложных запросов, включающих много предикатов и/или операций. Такие оценки опираются на статистику базы данных и допущения модели, которые для конкретной базы данных могут оказаться как верными, так и неверными. В статье обсуждается самонастраивающийся оптимизатор запросов LEO (LEarning Optimizer for DB2), который автоматически проверяет достоверность своей модели, не требуя какого-либо вмешательства пользователя для изменения некорректной статистики или оценок мощности результатов запросов. Производя мониторинг запросов при их выполнении, самонастраивающийся оптимизатор сравнивает свои оценки с реальной мощностью результата на каждом шаге QEP и вычисляет поправки для оценок. Эти поправки могут использоваться для оптимизации аналогичных запросов в будущем. Более того, обнаружение погрешностей оценок может инициировать повторную оптимизацию запроса в середине его выполнения. Автоматическое совершенствование модели оптимизатора может привести к уменьшению времени выполнения запроса на несколько порядков при незначительном увеличении затрат времени исполнения. LEO собирает данные о мощности результатов, получаемых при доступе к таблицам, и корректирует погрешность оценки для простых предикатов путем согласования статистики базы данных DB2 в расчете на будущие запросы.

Поразительный рост индустрии реляционных систем управления базами данных (РСУБД) за последние два десятилетия во многом объясняется стандартизацией структурированного языка запросов. SQL — декларативный язык, т. е. при его использовании требуется, чтобы пользователь указал только то, какие данные ему желательно получить, оставляя на долю оптимизатора запросов РСУБД принятие трудного решения о том, как лучше всего получить доступ к данным и обработать их. Для данного SQL-запроса может иметься много разных способов доступа к каждой из таблиц, к которой адресован запрос, способов соединения этих таблиц и, поскольку операция слияния коммутативна, способов упорядочения этих слияний и выполнения других операций, требуемых для окончательной обработки запроса. Тем самым, могут существовать сотни или даже тысячи возможных способов корректной обработки данного запроса. Например, пусть имеется следующий SQL-запрос:

SELECT name, age, salary
FROM employees
WHERE age > 60 AND city = ‘SAN JOSE ‘ AND salary < 60,000

В этом запросе ищутся имя, возраст и зарплата каждого служащего старше 60 лет, проживающего в Сан-Хосе и получающего менее 60 тыс. долл. в год. Каждое фильтрующее условие в разделе WHERE, соединенное с другими с помощью AND, называется предикатом. Поскольку этот запрос обращен только к одной таблице, не встает вопрос о выборе порядка соединений или методе их выполнения, но все равно оптимизатор может принимать во внимание много разных способов выполнения этого простого запроса в РСУБД. Всегда можно последовательно сканировать все строки в таблице, применяя каждый предикат к каждой строке. Либо, если существуют подходящие индексы, можно использовать один или несколько индексов для доступа только к тем строкам, которые удовлетворяют одному или нескольким предикатам. Так, индекс на столбце age позволил бы обращаться только к тем строкам, в которых значение возраста больше 60, а затем применять другие предикаты (касающиеся города и зарплаты). Наличие индекса на столбце city позволил бы ограничиться доступом только к тем строкам, в которых значение столбца городов равно «Сан-Хосе», а затем последовательно применять к извлекаемым строкам другие предикаты (касающиеся возраста и зарплаты). Или же могут быть использованы индексы на нескольких столбцах таблицы, например, комбинированный индекс по городу и возрасту или комбинированный индекс по городу и зарплате, если такие индексы существуют, либо стратегии, комбинирующие индексы (так называемая «конъюнкция индексов» — index ANDing). Какая стратегия окажется предпочтительней, зависит от характеристик базы данных, наличия различных индексов и того, насколько селективен каждый предикат, т.е. сколько строк удовлетворяют каждому из условий.

В большей части современных оптимизаторов запросов наилучший план выполнения запроса (QEP, или просто план) определяется путем математического моделирования затрат на выполнение каждого плана из набора альтернативных QEP и выбора плана с самой низкой оцененной стоимостью. Стоимость выполнения существенно зависит от числа строк, которые будут обработаны каждой операцией в QEP, поэтому оптимизатор оценивает стоимость главным образом инкрементально, по мере применения каждого из предикатов. Методы оценки мощности (т.е. числа строк) результата после того, как были применены один или несколько предикатов, являлись предметом многих исследований, проводившихся в последние 20 лет [1-5]. Чтобы избежать обращений к базе данных при оптимизации запросов, эта оценка обычно опирается, прежде всего, на статистику характеристик базы данных, в частности, число строк в каждой таблице. Мощность каждого из промежуточных результатов выводится инкрементальным образом, путем умножения числа строк в базовой таблице на коэффициент фильтрации, или селективности, для каждого предиката в запросе. Этот коэффициент вычисляется на основе статистических параметров столбцов, к которым применяется данный предикат, таких как число различных значений или гистограмма их распределения. Селективность предиката P, по существу, представляет собой вероятность того, что некоторая строка в таблице будет удовлетворять условию предиката P, и эта селективность зависит от характеристик базы данных. Например, в приведенном выше запросе предикат на столбце city мог бы быть достаточно селективным, если бы база данных была всемирной базой данных крупной международной компании, но мог бы оказаться значительно менее селективным, если бы база данных содержала сведения обо всех служащих небольшой начинающей компании, базирующейся в Сан-Хосе. В последнем случае предикаты на age и/или salary были бы более селективными. Оптимизатор отдал бы предпочтение тем QEP, в которых могли бы использоваться индексы для применения наиболее селективных предикатов, и тем QEP, в которых используется простое сканирование таблиц, если индексов не существует или если, по оценкам оптимизатора, большинство записей о служащих удовлетворяет всем предикатам. В DB2 выбор QEP опирается исключительно на детализированные оценки стоимости каждого из конкурирующих планов, а не на такую упрощенную эвристику.

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

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

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

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

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

Принцип включения. Селективность предиката слияния X.a = Y.b обычно определяется как 1/max {|a|, |b|}, где |b| — это число различных значений в столбце b. Это неявно предполагает наличие «принципа включения», означающего, что для каждого значения из меньшего домена имеется пара в большем домене. К счастью, это предположение зачастую истинно для большинства соединений между первичным ключом таблицы (например, номером продукта в таблице «Продукты» (Products)) и ссылкой на этот ключ (внешним ключом) в другой таблице (например, в таблице «Заказы» (Orders)).

В тех ситуациях, когда эти предположения неверны, возникают существенные ошибки в оценках мощности и, следовательно, стоимости, что приводит к выбору неоптимальных планов. По опыту авторов, основная причина серьезных ошибок моделирования — некорректная оценка мощности, от которой зависит стоимость. Для данной мощности оценки стоимости могут отклоняться от истины на 10-15%, но оценки мощности могут отклоняться от истинных значений на несколько порядков, если базовые предположения неверны или сомнительны. Хотя достигнут значительный успех при использовании гистограмм для определения и корректировки скашивания данных [6-8], а также при использовании образцов для сбора актуальной статистики [9, 10], пока не существует исчерпывающего подхода к исправлению всех модельных ошибок вне зависимости от их источника.

LEO [11] обучается при обнаружении любой ошибки моделирования в любой точке QEP, автоматически сравнивая свои оценки с реальными мощностями промежуточных результатов запроса. Определение того, в какой точке плана возникла существенная ошибка, позволяет повторно оптимизировать запрос в этой точке [12] и динамически настраивать модель оптимизатора для лучшей оптимизации последующих запросов. Со временем этот метод обратной связи приводит к накоплению эмпирической информации, которая расширяет и настраивает статистику базы данных для той ее части, к которой чаще всего обращаются пользователи. Эта информация не только повышает качество оценок оптимизатора, но и также определяет, где следует сконцентрировать сбор статистики, и может даже избавить от необходимости сбора статистики.

Обучающийся оптимизатор

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

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

Рис. 1. Отложенное обучение

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

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

Механизм замедленного обучения реализован с использованием DB2 Universal Database (UDB) для платформ Linux, Unix и Windows. Эксперименты с прототипом [18] показали, что мониторинг занимает менее 4% всего времени исполнения запроса, в то время как производительность может увеличиться на несколько порядков, особенно в тех случаях, когда оптимизатор «понимает», что нужно использовать метод массивного соединения, а не метод соединения на основе вложенных циклов, по причине большой мощности входных данных.

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

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

Поскольку повторная оптимизация требует определенных затрат, то когда она оправдана?
Как можно эффективно выполнить повторную оптимизацию?

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

Рис. 2. План запроса, который может оптимизироваться динамически

Так, на рис. 2 показан план запроса для простого соединения двух таблиц, в котором группировка/ агрегация таблицы Orders по столбцу Product_Id выполняется до соединения. Для выполнения сортировки, которая может понадобиться для выполнения этой агрегации, необходимо полностью сформировать все входные данные до начала сортировки; эти данные образуют таблицу TEMP. Поскольку большая часть агрегатных функций может вычисляться в инкрементальном режиме, по мере сортировки строк, в своем окончательном виде TEMP будет содержать результат выполнения раздела GROUP BY. Оптимальный алгоритм соединения (соединение методом вложенных циклов, соединение через хеширование или соединение слиянием) для последующего соединения Orders и Products критически зависит от размера результата GROUP BY. Оптимизатор запросов может выбрать неоптимальный алгоритм слияния при переоценке или недооценке размера этого результата.

Однако во время выполнения запроса оптимизатор может отслеживать размер результата GROUP BY и повторно оптимизировать при обнаружении серьезных ошибок оценки, например, изменяя при необходимости алгоритм соединения. Такая повторная оптимизация усложняется для более сложных планов запросов с несколькими точками материализации. В [12] предлагается оформлять TEMP в виде таблиц и преобразовывать часть плана запроса, оставшуюся после формирования TEMP, в SQL-запрос, который снова передается оптимизатору запросов. К сожалению, у этого подхода имеются два недостатка. Во-первых, может оказаться, что использование таблиц TEMP в том виде, в каком они существуют, не является оптимальным. В тех случаях, когда размер TEMP оказывается намного больше, чем предполагалось, в оптимальном плане может повторно использоваться только часть TEMP, или TEMP может вообще полностью игнорироваться, если в полностью новом плане напрямую используются базовые таблицы. Во-вторых, часть плана, оставшуюся после формирования TEMP, не всегда можно выразить в виде оператора SQL, особенно в этой части содержатся операции обновления, возникающие по причине наличия подзапросов.

Более хороший подход состоит в том, чтобы не оформлять TEMP в виде таблиц, а определять их как материализованные представления [13] (в DB2 их называют Automatic Summary Table [14]) и предоставлять их определения оптимизатору запросов. Тогда оптимизатор может опираться на стандартные методы проверки соответствия представлений [15] для определения того, какие TEMP стоит использовать повторно. Затраты на повторную оптимизацию с использованием дополнительных материализованных представлений практически идентичны затратам на оптимизацию исходного запроса, поскольку от оптимизатора требуется всего лишь рассмотрение одного альтернативного метода доступа к промежуточной таблице для каждого материализованного представления.

Более того, если TEMP определяются в виде материализованных представлений, нет оснований ограничивать их использование только текущим запросом. Материализованные TEMP потенциально могут использоваться во всех последующих запросах таким же образом, как в них используются материализованные представления, определенные пользователями. Конечно, этот подход может привести к лавинообразному росту числа таких представлений, поэтому процессор запросов должен периодически удалять редко используемые представления; это сродни проблеме подвыбора материализованных представлений [16].

Проблемы самонастраивающейся оптимизации запросов

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

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

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

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

Для преодоления локального оптимума, вызванного завышенными оценками, необходимо исследовать недостоверные знания, используемые для вероятно неоптимальных, но многообещающих QEP, например, путем синхронного или асинхронного взятия образцов [10].

Выявление и использование корреляции. В практических приложениях между данными часто имеется корреляция. Например, в базе данных автомобилей селективность конъюнкции (make = «Honda» and model = «Accord») не равна произведению селективностей предикатов make = «Honda» и model = «Accord», поскольку между столбцами make и model имеется корреляция — только Honda выпускает модель Accord. Поскольку наличие корреляции нарушает предположение о независимости, в современных оптимизаторах оценки селективности для предикатов, в которых присутствует корреляция, могут отличаться от реальных значений на несколько порядков. Наш подход обеспечивает возможность выявлять и исправлять такие ошибки.

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

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

В [12] различие между предполагаемыми и реальными мощностями используется в качестве эвристики для определения того, нужно ли выполнять повторную оптимизацию. Однако вопрос состоит не в том, насколько неточны оценки оптимизатора, а в том, является ли план неоптимальным при новых значениях мощности и являются ли различия в стоимости настолько существенными, чтобы оправдать расходы на повторную оптимизацию. В одной из эвристик рассматривается природа операций плана и оценивается вероятность того, что изменение мощности входных данных операции сделает ее неоптимальной. Или же можно усовершенствовать оптимизатор таким образом, чтобы он предсказывал не только оптимальный план, но и также и тот диапазон селективности каждого предиката, внутри которого план является оптимальным. Предсказывать «чувствительность» любого плана по отношению к одному произвольному параметру исключительно сложно, поскольку в модели оценок имеются нелинейности.

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

Изучение иной информации. Обучение и адаптация к динамической среде не ограничиваются мощностью и селективностью. При использовании цикла обратной связи может быть обеспечена самопроверка достоверности значений стоимости и других параметров, оцениваемых в настоящее время оптимизатором. Например, основной аспект стоимости, число физических операций ввода/вывода, которое сейчас оценивается вероятностным образом на основе оцененного процента удач в предположении, что каждому приложению доступна часть пула буферов одного и того же размера. Оптимизатор мог бы проверить для данного плана достоверность этих оценок путем слежения за реальным вводом/выводом, реальным процентом удач и реальным числом операций доступа к таблицам. Другим примером является максимальный объем памяти, выделяемый для выполнения в плане конкретной сортировки в плане. Если бы СУБД определила с помощью обратной связи запроса, что операция сортировки не может быть выполнена в основной памяти, она могла бы отрегулировать размер «кучи», предназначенной для сортировки, чтобы избежать внешней сортировки при выполнении таких последующих операций.

Обратная связь не ограничивается службами и ресурсами, потребляемыми СУБД, а распространяется также и на приложения, обслуживаемые СУБД. Например, СУБД могла бы измерить, сколько строк из результата запроса действительно потребляется каждым приложением, и оптимизировать производительность каждого запроса именно для этой части результата путем, например, явного добавления к данному запросу раздела OPTIMIZE FOR <n> ROWS. Подобным образом, обратная связь при выполнении могла бы использоваться для автоматической установки многих устанавливаемых в настоящее время вручную конфигурационных параметров совместно используемых ресурсов. Физические параметры, такие как скорость сети, время доступа к диску и скорость обмена данными с диском, используются для определения веса вклада этих ресурсов в стоимость плана и обычно считаются постоянными после первоначальной настройки. Однако установка этих параметров на основе измеренных значений является более саморегулируемой и более точно фиксирует реальную скорость. Аналогичным образом, распределение памяти между различными буферными пулами, общий размер «кучи» для сортировки и так далее могут настраиваться автоматически с учетом процента удач, наблюдавшегося за последнее время.

Практические соображения

В процессе реализации LEO требовалось также учитывать некоторые практические соображения.

Клятва Гиппократа: «Не навреди!» Основная цель самонастраивающегося оптимизатора состоит в улучшении производительности запросов за счет настройки существующей модели на основе ранее выполненных запросов. В идеале эта настроенная модель обеспечивает улучшенный базис для принятия решений при выборе наилучшего плана выполнения запроса. Однако эти обретенные знания должны использоваться исключительно консервативно: не следует делать поспешные выводы, опираясь на неубедительные или отрывочные данные. В критических приложениях стабильность и надежность обработки запросов часто более приоритетны, чем оптимальность со случайным и непредсказуемым поведением. Если немедленно принимать во внимание поправки при оптимизации запросов, то в условиях весьма динамичной базы данных для одного и того же запроса могут генерироваться разные планы выполнения при каждом поступлении запроса, а это может привести к «пробуксовке» планов выполнения. Такой нестабильности можно избежать, если инициировать повторную оптимизацию запросов после того, как получаемые знания сошлись к фиксированной точке или достигли определенного порога надежности.

Согласованность статистики. В DB2 статистические показатели собираются для базовых таблиц, столбцов, индексов, функций и полей, и многие показатели являются взаимозависимыми. Пользователям DB2 дается возможность обновлять статистику в каталогах и выполнять при таких обновлениях проверку несогласованности. Самонастраивающийся оптимизатор должен аналогичным образом обеспечивать согласованность этих взаимозависимых статистик при корректировке любой из них. Скажем, число строк в таблице определяет число дисковых страниц, используемых для хранения этих строк. Поэтому при корректировке числа строк в таблице необходимо обеспечить согласованность с числом страниц для этой таблицы (например, изменив и этот параметр), иначе выбор плана может оказаться зависимым от вида используемой статистики. Необходимо сохранять и согласованность между индексными и табличными статистическими показателями, поскольку могут существовать взаимозависимости между числом различных значений столбца и числом строк в таблице. Однако увеличение числа строк не всегда приводит к увеличению числа различных значений. Хотя при последовательной вставке строк число различных значений в столбце date (дата) изменится, это маловероятно для такого столбца, как sex (пол), для которого предполагается наличие только значений male (мужской) или female (женский), вне зависимости от числа строк.

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

Заключение

Хотя сегодняшние оптимизаторы запросов автоматически определяют наилучший способ обработки декларативного SQL-запроса (запроса, в котором указывается только то, какие данные желательны), они делают это с помощью сложной математической модели, основанной на многих допущениях и параметрах. Идеи самонастраивающейся оптимизации запросов, кратко изложенные в данной статье, привели к реализации LEO. Путем самопроверки этих предположений и параметров с использованием информации обратной связи, накопленной по итогам выполнения предыдущих запросов, LEO представляет собой важный шаг к повышению качества оптимизации запросов и уменьшению потребности в «настройке» наиболее дорогостоящих проблемных запросов. В существующем прототипе LEO поддерживается замедленное изучение мощностей результатов обращений к таблицам и простых предикатов [18], при этом демонстрируется значительное увеличение производительность и низкие накладные расходы на мониторинг, составляющие менее 4% от общего времени выполнения запроса.

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

Литература

P.G. Selinger, M.M. Astrahan, D.D. Chamberlin, R.A. Lorie, T.G. Price, "Access Path Selection in a Relational Database Management System", Proceedings of the ACM SIGMOD International Conference on Management of Data, Boston, MA, May 1979, ACM, New York (1979).
A. Van Gelder, "Multiple Join Size Estimation by Virtual Domains", Proceedings of the Twelfth ACM Symposium on Principles of Database Systems (1993 May).
A.N. Swami, K.B. Schiefer, "On the Estimation of Join Result Sizes", 4th International Conference on Extending Database Technology (1994 March).
R. Ahad, K.V.B. Rao, D. McLeod, "On Estimating the Cardinality of the Projection of a Database Relation", ACM Transactions on Database Systems 14, 1989, No. 1.
C. Lynch, "Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values", Proceedings of the 14th International Conference on Very Large Databases (1988 August).
Y.E. Ioannidis, S. Christodoulakis, "On the Propagation of Errors in the Size of Join Results", Proceedings of the ACM SIGMOD International Conference on Management of Data, Denver, CO, 1991 May, ACM, New York (1991).
V. Poosala, Y. Ioannidis, P. Haas, E. Shekita, "Improved Histograms for Selectivity Estimation of Range Predicates", Proceedings of the ACM SIGMOD International Conference on Management of Data, Montreal, Canada, June 1996, ACM, New York (1996).
V. Poosala, Y. Ioannidis, "Selectivity Estimation Without the Attribute Value Independence Assumption", Proceedings of the 23rd International Conference on Very Large Databases (VLDB 1997).
P. Haas, J. Naughton, S. Seshadri, and A. Swami, Selectivity and Cost Estimation for Joins Based on Random Sampling, Research Report RJ-9577, IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598 (1993).
T. Urhan, M. J. Franklin, L. Amsaleg, "Cost-Based Query Scrambling for Initial Delays", Proceedings of the ACM SIGMOD International Conference on Management of Data, Seattle, WA, June 1998, ACM, New York (1998).
M. Stillger, G. Lohman, V. Markl, M. Kandil, "LEO-DB2's Learning Optimizer", Proceedings of the 27th International Conference on Very Large Databases (September 2001).
N. Kabra, D. DeWitt, "Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans", Proceedings of the ACM SIGMOD International Conference on Management of Data (1998 June).
N. Roussopoulos, "Materialized Views and Data Warehouses", SIGMOD Record 27, No. 1, ACM, New York (1998).
M. Zaharioudakis, R. Cochrane, G. Lapis, H. Pirahesh, M. Urata, "Answering Complex SQL Queries Using Automatic Summary Tables", Proceedings of the ACM SIGMOD International Conference on Management of Data, Dallas, TX, May 2000, ACM, New York (2000).
S. Chaudhuri, R. Krishnamurthy, S. Potamianos, K. Shim, "Optimizing Queries with Materialized Views", Proceedings of the Eleventh International Conference on Data Engineering (1995 March).
R. Chirkova, A.Y. Halevy, D. Suciu, "A Formal Perspective on the View Selection Problem", Proceedings of the 27th International Conference on Very Large Databases (2001 September).
S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, "Optimization by Simulated Annealing", Science 220, No. 4598 (1983 May).
V. Markl, G. M. Lohman, "Learning Table Access Cardinalities with LEO", Proceedings of the ACM SIGMOD International Conference on Management of Data, Madison, WI, June 2002, ACM, New York (2002).

Волкер Маркл — научный сотрудник подразделения перспективных решений в области баз данных исследовательского центра IBM Almaden Research Center. Он ведет исследования в таких областях, как оптимизация запросов, индексация, самоуправляемые базы данных. Руководит проектом LEO, инициативой, посвященной самонастраивающимся вычислениям, цель которого — создание самонастраивающегося оптимизатора для DB2. Принимал участие в создании и разработке технологии индексации для системы управления реляционными базами данных TransBase HyperCube. Гай Лохман, более 20 лет занимающийся проблемами оптимизации реляционных запросов, руководит исследованиями в области перспективных методов оптимизации подразделения исследовательского центра IBM Almaden Research Center. Разработчик оптимизатора запросов для DB2 Universal Database. Руководил проектом по интеграции в DB2 UDB технологии компиляции запросов Starburst. До недавнего времени занимался разработкой и проектированием DB2 Index Advisor. Один из инициаторов проекта DB2 SMART (Self-Managing And Resource Tuning). Виджайшанкар Раман — научный сотрудник центра IBM Almaden Research Center. Специализируется на вопросах управления данными в системах метакомпьютинга и вопросах адаптивной оптимизации запросов, а также занимается алгоритмическим проектированием механизмов, фильтрацией и интеграцией данных. Один из результатов его исследований включен в состав свободно распространяемого программного обеспечения фильтрации данных Potter’s Wheel.

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

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