Оптимизация запросов

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

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

Запрос — это запрос информации из базы данных. Это может быть так просто, как «найти адрес человека с номером социального страхования 123-45-6789», или более сложно, например, «найти среднюю зарплату всех работающих женатых мужчин в Калифорнии в возрасте от 30 до 39 лет, которые зарабатывают меньше». чем их супруги». Результат запроса генерируется путем обработки строк в базе данных таким образом, чтобы получить запрошенную информацию. Поскольку структуры базы данных сложны, в большинстве случаев, особенно для не очень простых запросов, необходимые данные для запроса можно собрать из базы данных, обращаясь к ней разными способами, через разные структуры данных и в разном порядке. Каждый другой способ обычно требует разного времени обработки. Время обработки одного и того же запроса может сильно варьироваться — от долей секунды до часов, в зависимости от выбранного метода. Цель оптимизации запросов, которая представляет собой автоматизированный процесс, состоит в том, чтобы найти способ обработки данного запроса за минимальное время. Большая возможная разница во времени оправдывает выполнение оптимизации запросов, хотя поиск точного оптимального плана запроса среди всех возможностей обычно очень сложен, отнимает много времени сам по себе, может быть слишком дорогостоящим и часто практически невозможным. Таким образом, оптимизация запросов обычно пытается приблизиться к оптимальному путем сравнения нескольких разумных альтернатив, чтобы в разумные сроки предоставить «достаточно хороший» план, который обычно не сильно отклоняется от наилучшего возможного результата.

Общие соображения

Существует компромисс между количеством времени, потраченным на поиск лучшего плана запроса , и качеством выбора; оптимизатор может не выбрать лучший ответ самостоятельно. Системы управления базами данных разного качества имеют разные способы балансировки этих двух факторов. Оптимизаторы запросов на основе затрат оценивают использование ресурсов различными планами запросов и используют это как основу для выбора плана. Они назначают приблизительную «стоимость» каждому возможному плану запроса и выбирают план с наименьшей стоимостью. Затраты используются для оценки затрат времени выполнения на оценку запроса с точки зрения количества требуемых операций ввода-вывода, длины пути ЦП , объема дискового буферного пространства, времени обслуживания дискового хранилища, использования межсоединений между единицами параллелизма и других факторы, определяемые из словаря данных . Набор рассмотренных планов запросов формируется путем изучения возможных путей доступа (например, доступ к первичному индексу, доступ к вторичному индексу, полное сканирование файлов) и различных методов соединения реляционных таблиц (например, соединение слиянием , хэш-соединение , соединение продуктов ). Пространство поиска может стать довольно большим в зависимости от сложности SQL- запроса. Существует два типа оптимизации. Они состоят из логической оптимизации, которая генерирует последовательность реляционной алгебры для решения запроса, и физической оптимизации, которая используется для определения средств выполнения каждой операции.

Реализация

Большинство оптимизаторов запросов представляют планы запросов в виде дерева «узлов плана». Узел плана инкапсулирует одну операцию, необходимую для выполнения запроса. Узлы организованы в виде дерева, в котором промежуточные результаты перетекают снизу вверх. Каждый узел имеет ноль или более дочерних узлов — это узлы, выходные данные которых подаются в качестве входных данных родительскому узлу. Например, узел соединения будет иметь два дочерних узла, которые представляют два операнда соединения, тогда как узел сортировки будет иметь один дочерний узел (входные данные, подлежащие сортировке). Листья дерева — это узлы, которые дают результаты при сканировании диска, например, при выполнении индексного сканирования или последовательного сканирования.

Присоединяйтесь к заказу

Два возможных плана запроса для треугольного запроса R(A, B) ⋈ S(B, C) ⋈ T(A, C) ; первый сначала соединяет S и T и соединяет результат с R , второй сначала соединяет R и S и соединяет результат с T

Производительность плана запроса во многом определяется порядком соединения таблиц. Например, при объединении трех таблиц A, B, C размером 10 строк, 10 000 строк и 1 000 000 строк соответственно, план запроса, который сначала объединяет B и C, может занять на несколько порядков больше времени, чем тот, который первым присоединяется к A и C. Большинство оптимизаторов запросов определяют соединения порядок с помощью алгоритма динамического программирования, впервые использованного в IBM System R. проекте базы данных . Этот алгоритм работает в два этапа:

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

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

Планирование запросов для вложенных SQL-запросов

SQL-запрос к современной реляционной СУБД делает больше, чем просто выборку и объединение. В частности, SQL-запросы часто вкладывают несколько слоев блоков SPJ (Select-Project-Join) с помощью операторов group by , Exists и Not Exists . В некоторых случаях такие вложенные SQL-запросы можно объединить в запрос select-project-join, но не всегда. Планы запросов для вложенных SQL-запросов также можно выбирать с использованием того же алгоритма динамического программирования, который используется для упорядочивания соединений, но это может привести к значительному увеличению времени оптимизации запросов. Поэтому некоторые системы управления базами данных используют альтернативный подход, основанный на правилах, который использует модель графа запросов.

Оценка стоимости

Одной из самых сложных проблем оптимизации запросов является точная оценка стоимости альтернативных планов запросов. Оптимизаторы оценивают планы запросов, используя математическую модель затрат на выполнение запроса, которая в значительной степени зависит от оценок мощности или количества кортежей, проходящих через каждое ребро в плане запроса. Оценка мощности, в свою очередь, зависит от оценок коэффициента отбора предикатов в запросе. Традиционно системы баз данных оценивают избирательность с помощью довольно подробной статистики распределения значений в каждом столбце, например гистограмм . Этот метод хорошо работает для оценки избирательности отдельных предикатов. Однако во многих запросах есть соединения предикатов, таких как select count(*) from R where R.make='Honda' and R.model='Accord'. Предикаты запроса часто сильно коррелируют (например, model='Accord' подразумевает make='Honda'), и оценить избирательность конъюнкта в целом очень сложно. Плохие оценки кардинальности и неуловленная корреляция — одни из основных причин, по которым оптимизаторы запросов выбирают плохие планы запросов. Это одна из причин, по которой администратор базы данных должен регулярно обновлять статистику базы данных, особенно после загрузки/выгрузки крупных данных.

Расширения

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

Параметрическая оптимизация запросов

Классическая оптимизация запросов связывает каждый план запроса с одним скалярным значением стоимости. Параметрическая оптимизация запросов предполагает, что стоимость плана запроса зависит от параметров, значения которых неизвестны во время оптимизации. Такие параметры могут, например, отражать избирательность предикатов запроса, которые не полностью определены во время оптимизации, но будут предоставлены во время выполнения. Таким образом, параметрическая оптимизация запросов связывает каждый план запроса с функцией стоимости, которая отображает многомерное пространство параметров в одномерное пространство затрат.

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

Многоцелевая оптимизация запросов

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

Многоцелевая оптимизация запросов моделирует стоимость плана запроса как вектор стоимости, где каждый компонент вектора представляет стоимость в соответствии с различной метрикой стоимости. Классическую оптимизацию запросов можно рассматривать как частный случай многокритериальной оптимизации запросов, где размерность пространства стоимости (т. е. количество компонентов вектора стоимости) равна единице.

Различные показатели затрат могут конфликтовать друг с другом (например, в сценарии облачных вычислений может существовать один план с минимальным временем выполнения и другой план с минимальной денежной комиссией за выполнение). Следовательно, цель оптимизации не может состоять в том, чтобы найти план запроса, который минимизирует все показатели стоимости, а должна состоять в том, чтобы найти план запроса, который реализует лучший компромисс между различными метриками стоимости. Какой компромисс будет лучшим, зависит от предпочтений пользователя (например, некоторые пользователи могут предпочесть более дешевый план, а другие — более быстрый план в облачном сценарии). Таким образом, цель оптимизации состоит в том, чтобы либо найти лучший план запроса на основе некоторой спецификации пользовательских предпочтений, предоставленной в качестве входных данных для оптимизатора (например, пользователи могут определять веса между различными метриками затрат, чтобы выразить относительную важность, или определять жесткие границы затрат для определенных метрик). или генерировать аппроксимацию набора оптимальных по Парето планов запроса (т. е. планов, в которых ни один другой план не имеет лучшей стоимости согласно всем показателям), чтобы пользователь мог выбрать предпочтительный компромисс по стоимости из этого набора планов.

Многоцелевая

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

Ряд инструментов отображают планы выполнения запросов , чтобы показать, какие операции требуют наибольшей стоимости обработки. Microsoft SMS, ApexSQLPlan, Hana и Tableau — вот некоторые примеры. Исправление этих проблем, обнаруженных в этих планах, может сократить время выполнения на десятки процентов, а в некоторых случаях может сократить двумерный поиск до линейного.

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

См. также

• Присоединиться к фактору выбора
• Переписывание запроса
• Саргабельный запрос