Как известно, SQL — это декларативный язык описания операций, которые должны быть выполнены над данными, а за выбор способа выполнения этих операций отвечает СУБД, поэтому один и тот же запрос может выполняться множеством различных способов. Например, выбор записей из таблицы, удовлетворяющих некоторым условиям, можно осуществлять как с помощью последовательного прохода по всем записям таблицы, так и с использованием индексов. Объединение двух отношений по равенству можно выполнять путем объединения вложенными циклами, объединения слиянием и объединения с помощью хэш-таблицы [1]. Если в запросе требуется объединить три отношения и более, то число способов их объединения равно количеству различных двоичных корневых деревьев, имеющих эти отношения в качестве листьев.

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

Процесс поиска оптимального плана можно разделить на две части: оценку стоимости любого плана (то есть количества ресурсов, необходимых для его выполнения) и выбор плана с минимальной стоимостью. В случае, когда на сервере не выполняются другие задачи и запросы, оцениваемое время выполнения запроса прямо пропорционально количеству потраченных на него ресурсов, поэтому можно считать, что стоимость плана — это его время выполнения в некоторых условных единицах. С увеличением сложности запроса число планов растет экспоненциально, и нельзя просто перебрать все планы, оценить стоимость каждого и выбрать самый дешевый — для поиска оптимального плана обычно используются сложные алгоритмы дискретной оптимизации. Например, в СУБД PostgreSQL [2] применяются динамическое программирование по подмножествам для простых запросов и генетический алгоритм [3] для сложных. Динамическое программирование гарантирует нахождение плана с минимальной оценкой стоимости, однако оно неприменимо для запросов, объединяющих слишком много отношений. Для таких запросов используется генетический алгоритм, позволяющий вести оптимизацию в пространстве очень большой размерности. В принципе, в этой задаче можно использовать и другие методы дискретной оптимизации, например метод имитации отжига [4].

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

Для плана можно оценивать стоимость запуска (start-up cost) и общую стоимость (total cost). Первая показывает, сколько ресурсов план потратит еще до того, как выдаст первую запись, а вторая — сколько ресурсов в целом потребуется для выполнения плана. В большинстве случаев важна только общая стоимость, однако иногда (например, при планировании подзапроса внутри предиката EXISTS языка SQL) минимизируется именно стоимость запуска. Если количество возвращаемых кортежей ограничено в запросе параметром LIMIT, то планировщик использует и стоимость запуска, и общую стоимость плана для оценки числа ресурсов, которые план потратит, чтобы вернуть необходимое число кортежей.

Оценка стоимости плана выполняется в два шага. Сначала для каждой его вершины предсказывается, сколько в ней будет отобрано кортежей, затем на основе этой информации оценивается стоимость выполнения каждой вершины и, соответственно, всего плана. Если есть информация о количестве кортежей, отобранных в каждой вершине, то можно предсказать необходимые для выполнения каждой вершины ресурсы. Например, для сортировки требуется выполнить в среднем 1,39•Nlog2N операций сравнения, где N — количество сортируемых кортежей. Зная ресурсоемкость операции сравнения, можно получить ресурсоемкость сортировки. Аналогично можно оценить ресурсоемкость любой другой вершины плана. В моделях операций учитывается множество различных параметров системы: стоимость операций с диском (последовательный доступ к диску и случайный доступ считаются операциями разной стоимости), с индексами, стоимость обработки кортежа на процессоре.

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

SELECT name FROM users WHERE age < 25;

Для этого нужна информация о данных и статистика по ним, обычно представленная в виде разнообразных гистограмм. В этом примере неважно, сколько записей в таблице users, — для того чтобы оценить долю пользователей моложе 25 лет, достаточно просмотреть всего 20 значений (сегментов у гистограммы, рис. 1).

 

Рис. 1. Пример гистограммы описания данных
Рис. 1. Пример гистограммы описания данных

 

Доля кортежей в вершине, удовлетворяющих некоторому условию, по отношению ко всем обработанным кортежам называется выборочностью (англ. selectivity) этого условия (в приведенном примере она равна примерно 0,3). Для каждой вершины плана доля всех отобранных кортежей по отношению ко всем обработанным кортежам называется выборочностью этой вершины или совместной выборочностью всех условий данной вершины. Чтобы найти количество отобранных в вершине кортежей, нужно количество всех обрабатываемых в вершине кортежей умножить на выборочность этой вершины. Заметим, что с помощью гистограмм можно найти только выборочности отдельных условий, но не совместную выборочность условий в вершине. В общем случае совместная выборочность совокупности условий может быть любой — от 0 (например, у противоречащих друг другу условий age < 5 AND married = True) до минимальной выборочности условия из этой совокупности (например, для пары вложенных друг в друга условий age > 10 AND married = True). Вложенность и противоречивость условий очевидны для человека, но не для СУБД.

В большинстве существующих СУБД условия считаются независимыми — вероятность того, что одновременно выполняются оба условия, равна произведению их вероятностей, однако в прикладном смысле можно понимать независимость условий как то, что истинность одного условия не влияет на выборочность другого. Например, среди всех кортежей, отобранных по условию married = True, выборочности условий age < 5 и age > 10 равны 0 и 1 соответственно, в то время как среди всех кортежей в таблице они равны 0,07 и 0,85 соответственно. С другой стороны, истинность условия city = 'Moscow' практически не влияет на выборочность условия age < 25, их можно считать независимыми. Поэтому совместная выборочность этих условий равна произведению их выборочностей.

В компании Postgres Professional было проведено исследование на тесте производительности TPC-H, выявившее наиболее значимые недостатки оценки стоимости плана. Были сгенерированы и выполнены запросы, по вершинам планов которых собрана статистика (рис. 2, 3).

 

Рис. 2. Зависимость истинного количества кортежей от предсказанного
Рис. 2. Зависимость истинного количества кортежей от предсказанного

 

Рис. 3. Зависимость времени работы вершины плана от ее стоимости, если количество кортежей предсказано правильно
Рис. 3. Зависимость времени работы вершины плана от ее стоимости, если количество кортежей предсказано правильно

 

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

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

Один из способов обработки зависимых условий состоит в использовании многомерных гистограмм, однако с увеличением размерности и сохранением той же точности объемы ресурсов, требуемые для работы с многомерной гистограммой, растут экспоненциально. Например, если в одномерном случае гистограммы по трем столбцам имеют по 100 сегментов каждая (всего 300 значений), то одна трехмерная гистограмма сравнимой точности будет иметь уже 100х100х100 = 1 млн сегментов. Оценка выборочности по таким гистограммам будет точнее, однако и ресурсов потребует существенно больше, поэтому обычно приходится ограничиваться гистограммами маленькой размерности (2–8 измерений). Отсюда следует другая проблема этого метода — нужно понять, для каких пар (троек, четверок и т. д.) столбцов имеет смысл строить многомерные гистограммы, а для каких нет. И здесь либо требуется хороший администратор базы данных, который будет вручную анализировать планы ресурсоемких запросов, определять корреляции между столбцами и указывать, какие гистограммы нужно достроить, либо нужна программа, которая с помощью статистических тестов попытается найти зависимые друг от друга столбцы. Однако не для всех зависимых столбцов имеет смысл строить гистограммы, поэтому программа должна анализировать совместную встречаемость столбцов в запросах. Например, в СУБД PostgreSQL cуществует возможность использования многомерных гистограмм, но все решения, предложенные сообществом разработчиков этой базы, либо требуют вручную задавать, для каких столбцов эти многомерные гистограммы должны быть построены, либо не анализируют совместную встречаемость столбцов в запросах, что влечет за собой создание большого числа ненужных многомерных гистограмм

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

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

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

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

 

Рис. 4. Оценка выборочности: а — до машинного обучения; б — после машинного обучения
Рис. 4. Оценка выборочности: а — до машинного обучения; б — после машинного обучения

 

 

Рис. 5. Производительность при выполнении запросов
Рис. 5. Производительность при выполнении запросов

 

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

***

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

Литература

  1. Bruce Momjian. Explaining the Postgres Query Optimizer. URL: https://momjian.us/main/writings/pgsql/optimizer.pdf (дата обращения: 18.03.2016).
  2. Иван Панченко. PostgreSQL: вчера, сегодня, завтра // Открытые системы.СУБД. — 2015. — № 3. — С. 34–37. URL: http://www.osp.ru/os/2015/03/13046900 (дата обращения: 18.03.2016).
  3. Панченко Т. В. Генетические алгоритмы: учебно-методическое пособие / Под ред. Ю. Ю. Тарасевича. — Астрахань: Издательский дом «Астраханский университет», 2007. — 87 с.
  4. Лопатин А. С. Метод отжига // Стохастическая оптимизация в информатике. — 2005. — Т. 1. — С. 133–149.

Олег Иванов (o.ivanov@postgrespro.ru) — Postgres Professional, ВМК МГУ им. М.В. Ломоносова (Москва). Автор выражает признательность Бартунову О.С. за предложенную им идею применения машинного обучения в планировщике СУБД.