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