Структурированный язык запросов
Производя мониторинг запросов при их выполнении, самонастраивающийся оптимизатор сравнивает свои оценки с реальной мощностью результата на каждом шаге 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] и динамически настраивать модель оптимизатора для лучшей оптимизации последующих запросов. Со временем этот метод обратной связи приводит к накоплению эмпирической информации, которая расширяет и настраивает статистику базы данных для той ее части, к которой чаще всего обращаются пользователи. Эта информация не только повышает качество оценок оптимизатора, но и также определяет, где следует сконцентрировать сбор статистики, и может даже избавить от необходимости сбора статистики.
