Оптимизация запросов является функцией многих систем управления реляционными базами данных и других баз данных, таких как NoSQL и графовые базы данных . Оптимизатор запросов пытается определить наиболее эффективный способ выполнения данного запроса, рассматривая возможные планы запросов . [1]
Как правило, пользователи не могут получить прямой доступ к оптимизатору запросов: как только запросы отправляются на сервер базы данных и анализируются парсером, они затем передаются оптимизатору запросов, где происходит оптимизация. [2] [3] Однако некоторые движки баз данных позволяют направлять оптимизатор запросов с помощью подсказок .
Запрос — это запрос информации из базы данных. Он может быть таким же простым, как «найти адрес человека с номером социального страхования 123-45-6789», или более сложным, как «найти среднюю зарплату всех работающих женатых мужчин в Калифорнии в возрасте от 30 до 39 лет, которые зарабатывают меньше своих супругов». Результат запроса генерируется путем обработки строк в базе данных таким образом, чтобы получить запрошенную информацию. Поскольку структуры баз данных в большинстве случаев сложны, и особенно для не очень простых запросов, необходимые данные для запроса можно собрать из базы данных, обратившись к ней разными способами, через разные структуры данных и в разном порядке. [4] Каждый разный способ обычно требует разного времени обработки. Время обработки одного и того же запроса может иметь большой разброс, от доли секунды до часов, в зависимости от выбранного метода. Целью оптимизации запросов, которая является автоматизированным процессом, является поиск способа обработки заданного запроса за минимальное время. Большая возможная дисперсия во времени оправдывает выполнение оптимизации запросов, хотя поиск точного оптимального плана запроса среди всех возможностей обычно очень сложен, требует много времени сам по себе, может быть слишком дорогим и часто практически невозможным. Таким образом, оптимизация запросов обычно пытается приблизиться к оптимуму, сравнивая несколько разумных альтернатив, чтобы предоставить за разумное время «достаточно хороший» план, который обычно не сильно отличается от наилучшего возможного результата.
Существует компромисс между количеством времени, потраченного на определение лучшего плана запроса , и качеством выбора; оптимизатор может не выбрать лучший ответ самостоятельно. Различные качества систем управления базами данных имеют разные способы балансировки этих двух факторов. Оптимизаторы запросов на основе стоимости оценивают ресурсозатраты различных планов запросов и используют это в качестве основы для выбора плана. [5] [6] Они назначают предполагаемую «стоимость» каждому возможному плану запроса и выбирают план с наименьшей стоимостью. Стоимость используется для оценки стоимости выполнения оценки запроса с точки зрения количества требуемых операций ввода-вывода, длины пути ЦП , объема дискового буферного пространства, времени обслуживания дискового хранилища и использования межсоединений между единицами параллелизма и других факторов, определяемых из словаря данных . Набор рассматриваемых планов запросов формируется путем изучения возможных путей доступа (например, доступ к первичному индексу, доступ к вторичному индексу, полное сканирование файла) и различных методов соединения реляционных таблиц (например, соединение слиянием , хэш-соединение , соединение продукта). Пространство поиска может стать довольно большим в зависимости от сложности запроса SQL . Существует два типа оптимизации. Они состоят из логической оптимизации, которая генерирует последовательность реляционной алгебры для решения запроса, и физической оптимизации, которая используется для определения средств выполнения каждой операции.
Большинство оптимизаторов запросов представляют планы запросов как дерево «узлов плана». Узел плана инкапсулирует одну операцию, которая требуется для выполнения запроса. Узлы организованы в виде дерева, в котором промежуточные результаты перетекают снизу дерева наверх. Каждый узел имеет ноль или более дочерних узлов — это узлы, выходные данные которых подаются в качестве входных данных в родительский узел. Например, узел соединения будет иметь два дочерних узла, которые представляют два операнда соединения, тогда как узел сортировки будет иметь один дочерний узел (входные данные для сортировки). Листья дерева — это узлы, которые выдают результаты путем сканирования диска, например, путем выполнения сканирования индекса или последовательного сканирования.
Производительность плана запроса во многом определяется порядком, в котором объединяются таблицы. Например, при объединении 3 таблиц A, B, C размером 10 строк, 10 000 строк и 1 000 000 строк соответственно, план запроса, который сначала объединяет B и C, может занять на несколько порядков больше времени для выполнения, чем тот, который сначала объединяет A и C. Большинство оптимизаторов запросов определяют порядок объединения с помощью динамического алгоритма программирования, впервые разработанного в проекте базы данных System R компании IBM [ требуется ссылка ] . Этот алгоритм работает в два этапа:
Порядок сортировки может избежать избыточной операции сортировки позже при обработке запроса. Во-вторых, определенный порядок сортировки может ускорить последующее соединение, поскольку он кластеризует данные определенным образом.
SQL-запрос к современной реляционной СУБД делает больше, чем просто выборки и соединения. В частности, SQL-запросы часто вкладывают несколько слоев блоков SPJ (Select-Project-Join) с помощью операторов group by , exists и not exist. В некоторых случаях такие вложенные SQL-запросы можно свести к запросу select-project-join, но не всегда. Планы запросов для вложенных SQL-запросов также можно выбирать с использованием того же алгоритма динамического программирования, который используется для упорядочивания соединений, но это может привести к огромному увеличению времени оптимизации запросов. Поэтому некоторые системы управления базами данных используют альтернативный подход на основе правил, который использует модель графа запросов. [7]
Одной из самых сложных проблем в оптимизации запросов является точная оценка затрат на альтернативные планы запросов. Оптимизаторы оценивают затраты на планы запросов, используя математическую модель затрат на выполнение запросов, которая в значительной степени опирается на оценки мощности или количества кортежей, проходящих через каждое ребро в плане запроса. Оценка мощности, в свою очередь, зависит от оценок фактора выбора предикатов в запросе. Традиционно системы баз данных оценивают селективности с помощью довольно подробной статистики распределения значений в каждом столбце, такой как гистограммы . Этот метод хорошо подходит для оценки селективностей отдельных предикатов. Однако во многих запросах есть конъюнкции предикатов, такие как . Предикаты запросов часто сильно коррелируют (например, подразумевает ), и очень сложно оценить селективность конъюнкта в целом. Плохие оценки мощности и неуловленная корреляция являются одной из основных причин, по которой оптимизаторы запросов выбирают плохие планы запросов. Это одна из причин, по которой администратор базы данных должен регулярно обновлять статистику базы данных, особенно после крупных загрузок/выгрузок данных.select count(*) from R where R.make='Honda' and R.model='Accord'model='Accord'make='Honda'
Классическая оптимизация запросов предполагает, что планы запросов сравниваются по одной единственной метрике стоимости, обычно времени выполнения, и что стоимость каждого плана запроса может быть рассчитана без неопределенности. Оба предположения иногда нарушаются на практике [8] , и в исследовательской литературе были изучены многочисленные расширения классической оптимизации запросов, которые преодолевают эти ограничения. Эти расширенные варианты задач различаются тем, как они моделируют стоимость отдельных планов запросов, и с точки зрения их цели оптимизации.
Классическая оптимизация запросов связывает каждый план запроса с одним скалярным значением стоимости. Параметрическая оптимизация запросов [9] предполагает, что стоимость плана запроса зависит от параметров, значения которых неизвестны во время оптимизации. Такие параметры могут, например, представлять селективность предикатов запроса, которые не полностью определены во время оптимизации, но будут предоставлены во время выполнения. Таким образом, параметрическая оптимизация запросов связывает каждый план запроса с функцией стоимости, которая отображается из многомерного пространства параметров в одномерное пространство стоимости.
Целью оптимизации обычно является генерация всех планов запросов, которые могут быть оптимальными для любой из возможных комбинаций значений параметров. Это дает набор соответствующих планов запросов. Во время выполнения из этого набора выбирается лучший план, как только становятся известны истинные значения параметров. Преимущество параметрической оптимизации запросов заключается в том, что оптимизация (которая, как правило, является очень дорогой операцией) избегается во время выполнения.
Часто существуют и другие показатели стоимости в дополнение к времени выполнения, которые имеют значение для сравнения планов запросов. Например, в сценарии облачных вычислений следует сравнивать планы запросов не только с точки зрения того, сколько времени требуется для их выполнения, но и с точки зрения того, сколько денег стоит их выполнение. Или в контексте приблизительной оптимизации запросов можно выполнять планы запросов на случайно выбранных образцах входных данных, чтобы получить приблизительные результаты с уменьшенными накладными расходами на выполнение. В таких случаях альтернативные планы запросов необходимо сравнивать с точки зрения времени их выполнения, а также с точки зрения точности или надежности данных, которые они генерируют.
Многоцелевая оптимизация запросов [10] моделирует стоимость плана запроса как вектор стоимости, где каждый компонент вектора представляет стоимость в соответствии с другой метрикой стоимости. Классическая оптимизация запросов может рассматриваться как частный случай многоцелевой оптимизации запросов, где размерность пространства стоимости (т. е. количество компонентов вектора стоимости) равна единице.
Различные метрики стоимости могут конфликтовать друг с другом (например, может быть один план с минимальным временем выполнения и другой план с минимальными денежными сборами за выполнение в сценарии облачных вычислений). Поэтому целью оптимизации не может быть поиск плана запроса, который минимизирует все метрики стоимости, а должен быть поиск плана запроса, который реализует наилучший компромисс между различными метриками стоимости. Какой компромисс будет наилучшим, зависит от предпочтений пользователя (например, некоторые пользователи могут предпочесть более дешевый план, а другие — более быстрый план в облачном сценарии). Таким образом, целью оптимизации является либо поиск наилучшего плана запроса на основе некоторой спецификации пользовательских предпочтений, предоставленных в качестве входных данных для оптимизатора (например, пользователи могут определять веса между различными метриками стоимости, чтобы выразить относительную важность или определить жесткие границы стоимости для определенных метрик), либо создание приближения набора оптимальных по Парето планов запросов (т. е. планов, таких, что никакой другой план не имеет лучшей стоимости по всем метрикам), так что пользователь может выбрать предпочтительный компромисс стоимости из этого набора планов.
Многоцелевая параметрическая оптимизация запросов [8] обобщает параметрическую и многоцелевую оптимизацию запросов. Планы сравниваются по нескольким метрикам стоимости, а стоимость плана может зависеть от параметров, значения которых неизвестны во время оптимизации. Поэтому стоимость плана запроса моделируется как функция от многомерного пространства параметров к многомерному пространству стоимости. Целью оптимизации является создание набора планов запросов, которые могут быть оптимальными для каждой возможной комбинации значений параметров и предпочтений пользователя.
Ряд инструментов отображают планы выполнения запросов, чтобы показать, какие операции имеют самую высокую стоимость обработки. Microsoft SMS, ApexSQLPlan, Hana и Tableau — вот некоторые примеры. Исправление этих проблем, обнаруженных в этих планах, может сократить время выполнения на десятки процентов, а в некоторых случаях может сократить двумерные поиски до линейных.
Одним из основных и самых простых контрольных списков оптимизации является использование операций, для эффективного выполнения которых разработано большинство RDMS. См. Sargable .