Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Общие соображения [ править ]

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

Реализация [ править ]

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

Порядок присоединения [ править ]

Производительность плана запроса во многом определяется порядком соединения таблиц. Например, при объединении 3 таблиц 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-запросов также можно выбрать с использованием того же алгоритма динамического программирования, который используется для упорядочивания соединений, но это может привести к огромному увеличению времени оптимизации запроса. Поэтому некоторые системы управления базами данных используют альтернативный подход, основанный на правилах, который использует модель графа запросов. [3]

Оценка стоимости [ править ]

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

Расширения [ править ]

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

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

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

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

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

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

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

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

Оптимизация многоцелевого параметрического запроса [ править ]

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

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

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

См. Также [ править ]

  • Фактор выбора присоединения
  • 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 . DOI : 10.1007 / s007780050037 . 
  6. ^ Траммер, Иммануил; Кох, Кристоф (2014). Аппроксимационные схемы для многоцелевой оптимизации запросов . SIGMOD. С. 1299–1310. arXiv : 1404.0046 .
  • Чаудхури, Сураджит (1998). «Обзор оптимизации запросов в реляционных системах» . Материалы симпозиума ACM по принципам систем баз данных . С. 34–43. DOI : 10.1145 / 275487.275492 .
  • Иоаннидис, Яннис (март 1996 г.). «Оптимизация запросов» . ACM Computing Surveys . 28 (1): 121–123. DOI : 10.1145 / 234313.234367 .
  • Селинджер, PG ; Астрахань, ММ; Чемберлин, Д. Д .; Лори, РА; Прайс, Т.Г. (1979). «Выбор пути доступа в системе управления реляционной базой данных». Материалы Международной конференции ACM SIGMOD 1979 года по управлению данными . С. 23–34. DOI : 10.1145 / 582095.582099 . ISBN 089791001X.