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

Query optimization

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

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

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

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

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

Выполнение

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

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

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

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

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

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

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

Оценка затрат

Одна из самых сложных проблем оптимизации запросов - это точно оценить стоимость альтернативных планов запросов. Оптимизаторы оценивают планы запросов с использованием математической модели затрат на выполнение запросов, которая в значительной степени зависит от оценок мощность, или количество кортежей, проходящих через каждое ребро в плане запроса. Оценка мощности, в свою очередь, зависит от оценок фактор выбора предикатов в запросе. Традиционно системы баз данных оценивают селективность с помощью довольно подробной статистики распределения значений в каждом столбце, например гистограммы. Этот метод хорошо работает для оценки избирательности отдельных предикатов. Однако многие запросы имеют союзы предикатов, таких как Выбрать считать(*) из р куда р.делать='Хонда' и р.модель=«Согласие». Предикаты запроса часто сильно коррелированы (например, model = 'Согласие' подразумевает make = 'Хонда'), и оценить селективность конъюнкта в целом очень сложно. Плохие оценки количества элементов и неперехваченная корреляция - одна из основных причин, по которым оптимизаторы запросов выбирают плохие планы запросов. Это одна из причин, почему администратор базы данных следует регулярно обновлять статистику базы данных, особенно после загрузки / выгрузки основных данных.

Расширения

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

Рекомендации

  1. ^ «Центр знаний IBM». www.ibm.com.
  2. ^ «Оптимизация стоимости Oracle SQL». www.dba-oracle.com.
  3. ^ "ОБЪЯСНИТЕ ПЛАН ЗАПРОСА". www.sqlite.org.
  4. ^ а б Труммер, Иммануил; Кох, Кристоф (2015). «Оптимизация многоцелевого параметрического запроса». VLDB: 221–232.
  5. ^ Иоаннидис, Яннис; Ng, Raymond T .; Шим, Кюсок; Селлис, Тимос К. (1997). «Параметрическая оптимизация запросов». VLDB. 6 (2): 132–151. CiteSeerX 10.1.1.33.696. Дои:10.1007 / s007780050037.
  6. ^ Труммер, Иммануил; Кох, Кристоф (2014). Аппроксимационные схемы для многоцелевой оптимизации запросов. SIGMOD. С. 1299–1310. arXiv:1404.0046.