Введение
Возможность эффективного выполнения запросов в программном обеспечении СУБД.
Оптимизация запросов — это функция, присутствующая во многих реляционных системах управления базами данных, а также в других типах баз данных, таких как NoSQL и графовые базы данных. Оптимизатор запросов пытается определить наиболее эффективный способ выполнения заданного запроса, рассматривая возможные планы его выполнения. Как правило, пользователи не имеют прямого доступа к оптимизатору запросов: после отправки запросов на сервер базы данных и их разбора, они передаются оптимизатору запросов, где и происходит оптимизация. Оптимизатор присваивает оценочную "стоимость" каждому возможному плану выполнения и выбирает план с наименьшей стоимостью. Стоимость используется для оценки времени выполнения запроса с точки зрения количества необходимых операций ввода-вывода, длины пути процессора, объема буферного пространства на диске, времени обслуживания дискового хранилища, использования межсоединений между единицами параллелизма и других факторов, определяемых из словаря данных. Множество рассматриваемых планов выполнения формируется путем анализа возможных путей доступа (например, доступа по первичному индексу, вторичному индексу, полного сканирования файла) и различных методов соединения реляционных таблиц (например, сортировочное соединение, хэш-соединение, декартово произведение). Пространство поиска может быть весьма обширным в зависимости от сложности SQL-запроса. Существуют два типа оптимизации: логическая оптимизация, которая генерирует последовательность операций реляционной алгебры для решения запроса, и физическая оптимизация, которая определяет способы выполнения каждой операции.
Реализация
Большинство оптимизаторов запросов представляют планы запросов в виде дерева "узлов плана". Узел плана инкапсулирует единственную операцию, необходимую для выполнения запроса. Узлы организованы в виде дерева, по которому промежуточные результаты передаются снизу вверх. Каждый узел имеет ноль или более дочерних узлов — это узлы, выходные данные которых используются в качестве входных для родительского узла. Например, узел соединения (join) будет иметь два дочерних узла, представляющих два операнда соединения, в то время как узел сортировки будет иметь один дочерний узел (входные данные для сортировки). Листья дерева — это узлы, которые генерируют результаты путем сканирования диска, например, выполняя индексное или последовательное сканирование.
Присоединяйтесь к заказу
Выполнение плана запроса во многом определяется порядком, в котором таблицы соединяются. Например, при соединении 3 таблиц A, B, C размером 10 строк, 10 000 строк и 1 000 000 строк соответственно, план запроса, который сначала соединяет B и C, может занять на несколько порядков больше времени для выполнения, чем тот, который сначала соединяет A и C. Большинство оптимизаторов запросов определяют порядок соединения с помощью алгоритма динамического программирования, впервые разработанного в проекте базы данных System R компании IBM. Этот алгоритм работает в два этапа:
Во-первых, вычисляются все возможные способы доступа к каждой таблице в запросе. Каждая таблица в запросе может быть доступна посредством последовательного сканирования. Если для таблицы существует индекс, который можно использовать для ответа на предикат в запросе, также может быть использовано сканирование индекса. Для каждой таблицы оптимизатор записывает наиболее дешевый способ сканирования таблицы, а также наиболее дешевый способ сканирования таблицы, который выдает записи в определенном отсортированном порядке. Затем оптимизатор рассматривает объединение каждой пары таблиц, для которых существует условие соединения. Для каждой пары оптимизатор рассматривает доступные алгоритмы соединения, реализованные СУБД. Он сохраняет наиболее дешевый способ соединения каждой пары таблиц, а также наиболее дешевый способ соединения каждой пары таблиц, который выдает результат в соответствии с определенным порядком сортировки. Затем вычисляются все трехтабличные планы запросов путем соединения каждого двухтабличного плана, полученного на предыдущем этапе, с оставшимися таблицами в запросе. Порядок сортировки может избежать избыточной операции сортировки на более поздних этапах обработки запроса. Во-вторых, определенный порядок сортировки может ускорить последующее соединение, поскольку он группирует данные определенным образом.
Планирование запросов для вложенных запросов SQL
SQL-запрос в современной реляционной СУБД выполняет не только выборку и объединение данных. В частности, SQL-запросы часто содержат несколько вложенных уровней блоков SPJ (Select Project Join), реализуемых с помощью операторов GROUP BY, EXISTS и NOT EXISTS. В некоторых случаях такие вложенные SQL-запросы можно преобразовать в плоский запрос типа "выборка-проекция-соединение", но это не всегда возможно. Планы выполнения для вложенных SQL-запросов также могут быть построены с использованием того же алгоритма динамического программирования, что и для оптимизации порядка соединений, однако это может привести к значительному увеличению времени оптимизации запроса. Поэтому некоторые системы управления базами данных используют альтернативный подход, основанный на правилах, с применением модели графа запросов.
Оценка затрат
Одной из самых сложных задач в оптимизации запросов является точная оценка стоимости альтернативных планов выполнения запросов. Оптимизаторы оценивают стоимость планов запросов, используя математическую модель стоимости выполнения, которая в значительной степени опирается на оценки кардинальности, то есть количества кортежей, проходящих через каждое ребро в плане запроса. Оценка кардинальности, в свою очередь, зависит от оценок коэффициента отбора предикатов в запросе. Традиционно, системы управления базами данных оценивают селективность, используя достаточно подробную статистику о распределении значений в каждом столбце, например, гистограммы. Этот метод хорошо работает для оценки селективности отдельных предикатов. Однако многие запросы содержат сочетания предикатов, например, `select count(*) from R where R.make='Honda' and R.model='Accord'`. Предикаты запроса часто сильно коррелируют (например, `model='Accord'` подразумевает `make='Honda'`), и в общем случае очень сложно оценить селективность конъюнкции. Неточные оценки кардинальности и неучтенная корреляция – одна из основных причин, по которым оптимизаторы запросов выбирают неоптимальные планы выполнения. Именно поэтому администратору базы данных следует регулярно обновлять статистику базы данных, особенно после значительных операций загрузки или выгрузки данных.
Расширения
Классическая оптимизация запросов исходит из предположения, что планы запросов сравниваются на основе единственной метрики стоимости, как правило, времени выполнения, и что стоимость каждого плана запроса может быть вычислена без какой-либо неопределенности. Оба этих предположения не всегда выполняются на практике, и в научной литературе исследовано множество расширений классической оптимизации запросов, направленных на преодоление этих ограничений. Эти расширенные варианты задач отличаются способом моделирования стоимости отдельных планов запросов и целью оптимизации.
Оптимизация параметрических запросов
Классическая оптимизация запросов связывает каждый план запроса с одним скалярным значением стоимости. Параметрическая оптимизация запросов исходит из предположения, что стоимость плана запроса зависит от параметров, значения которых неизвестны на этапе оптимизации. Эти параметры могут, например, представлять селективность предикатов запроса, которые не полностью определены во время оптимизации, но будут предоставлены во время выполнения. Таким образом, параметрическая оптимизация запросов связывает каждый план запроса с функцией стоимости, которая отображает многомерное пространство параметров в одномерное пространство стоимости. Целью оптимизации обычно является генерация всех планов запросов, которые могут оказаться оптимальными для любой возможной комбинации значений параметров. Это приводит к набору релевантных планов запросов. Во время выполнения лучший план выбирается из этого набора, когда становятся известны истинные значения параметров. Преимущество параметрической оптимизации запросов заключается в том, что оптимизация (которая, как правило, является очень дорогостоящей операцией) не требуется во время выполнения.
Оптимизация многоцелевых запросов
Кроме времени выполнения часто используются и другие метрики затрат, которые важны при сравнении планов запросов. Например, в сценарии облачных вычислений следует сравнивать планы запросов не только по времени их выполнения, но и по стоимости их выполнения. Или, в контексте приближенной оптимизации запросов, можно выполнять планы запросов на случайно выбранных выборках входных данных, чтобы получить приближенные результаты с уменьшенными накладными расходами на выполнение. В таких случаях альтернативные планы запросов необходимо сравнивать не только по времени выполнения, но и по точности или надежности генерируемых ими данных. Многоцелевая оптимизация запросов моделирует стоимость плана запросов как вектор затрат, где каждый компонент вектора представляет собой стоимость, измеренную по различной метрике затрат. Классическая оптимизация запросов можно рассматривать как частный случай многоцелевой оптимизации запросов, в котором размерность пространства затрат (то есть количество компонентов вектора затрат) равно единице. Различные метрики затрат могут противоречить друг другу (например, может существовать план с минимальным временем выполнения и другой план с минимальными денежными затратами на выполнение в сценарии облачных вычислений). Поэтому целью оптимизации не является поиск плана запросов, минимизирующего все метрики затрат, а поиск плана запросов, обеспечивающего наилучший компромисс между различными метриками затрат. Что представляет собой наилучший компромисс, зависит от предпочтений пользователя (например, одни пользователи могут предпочесть более дешевый план, а другие – более быстрый в облачном сценарии). Следовательно, целью оптимизации является либо поиск наилучшего плана запросов на основе спецификации предпочтений пользователя, предоставленной оптимизатору в качестве входных данных (например, пользователи могут задавать веса для различных метрик затрат, чтобы выразить их относительную важность, или устанавливать жесткие ограничения на определенные метрики), либо генерация приближения множества Парето-оптимальных планов запросов (то есть планов, для которых не существует другого плана, превосходящего его по всем метрикам), чтобы пользователь мог выбрать предпочтительный компромисс из этого множества планов.