УДК 004.65
Исследование работы стандартного оптимизатора реляционной СУБД и применение основных методов лексической оптимизации запросов в рамках АСУ ДонНТУ.
Скиба В.Е., Краснокутский В.А., Меренкова Л.Л.
ГОУВПО Донецкий национальный технический университет
кафедра компьютерной инженерии
email: skibaviktor@mail.ru
Аннотация
Скиба В.Е., Краснокутский В.А., Меренкова Л.Л. Исследование работы стандартного оптимизатора реляционной СУБД и применение основных методов лексической оптимизации запросов в рамках АСУ ДонНТУ. Изучена технология работы стандартного оптимизатора в реляционной СУБД на примере Microsoft SQL Server. Рассмотрены основные подходы в области оптимизации запросов, в частности, технология лексического преобразования для увеличения эффективности работы СУБД и уменьшения времени выполнения запроса.
Общая постановка задачи
Вопрос оптимизации запросов всегда является актуальным как для разработчиков баз данных, так и для программистов, которые с ними работают. В современных СУБД содержится компонент, называющийся оптимизатором, работу которого необходимо рассмотреть и выбрать возможные пути, как изменить запрос или БД таким образом, чтобы оптимизатор тратил меньше времени и ресурсов на построение плана выполнения запроса и его реализацию.
Существуют несколько различных подходов и методов оптимизации запросов, но первоочередным является лексическая оптимизация на уровне языка SQL с целью анализа текста запроса для выявления избыточности.
Исследование работы оптимизатора
Оптимизатор [1] — подкомпонент системы управления базой данных, который принимает входной аргумент в виде текста запроса и рассматривает возможные стратегии исполнения запроса, после чего выбирает из них наиболее эффективную. Выбранная стратегия и будет планом исполнения запроса. Оптимизатор принимает решение, учитывая такие факторы, как размер таблиц, из которых проводится выборка, существующие в таблицах индексы и всевозможные логические операторы (AND, OR, NOT), используемые в предложении WHERE.
Основной задачей оптимизатора является выборка наиболее эффективного плана выполнения запроса. Эта задача разбивается на 4 основных этапа, которые представлены на рисунке 1.
1) Синтаксический разбор(parsing). При выполнении синтаксического анализа, проверяется синтаксис запроса и запрос преобразовывается в дерево. После этого, выполняется проверка всех объектов базы данных, на которые ссылается запрос. (Например, проверка наличия в базе данных столбцов, указанных в запросе). После завершения работы создается окончательное дерево запроса.
2) Компиляция запроса (query compilation). На этом этапе дерево запроса компилируется оптимизатором.
3) Оптимизация запроса (query optimization). Оптимизатор в качестве входных параметров на данном этапе принимает скомпилированное дерево запроса и исследует различные стратегии обращения к данным, прежде чем решить, как обрабатывать данный запрос. Чтобы отыскать оптимальный план выполнения запроса, оптимизатор сначала выполняет анализ запроса, в процессе которого ищет аргументы поиска и операции соединения. Затем оптимизатор решает, какие индексы использовать. Индекс представляет собой структуру данных, которая позволяет получать быстрый доступ к одной или нескольким строкам данных. Rомпонент Database Engine, при поиске определенной строки из таблицы обращается к индексу, чтобы узнать ее физическое местонахождение. [1] Далее, если в запросе есть операции соединения, оптимизатор выбирает методы соединения и метод обработки.
4) Выполнение запроса (query execution). Созданный план выполнения сохраняется как основной и затем выполняется.
Рисунок 1. Основные этапы обработки запроса.
Лексическая оптимизация запросов
Для выполнения лексической оптимизации запросов единственным источником информации является сам текст запроса как лексическая конструкция. Иные сведения о базе данных и ее структуре в анализе не используются. Процесс лексической оптимизации включает в себя анализ ограничения запроса, сравнение содержащихся в нем условий с целью выявления избыточности.
Лексическая оптимизация может устранять неоптимальности запроса тремя различными способами:
1) Сокращение запроса - удаление избыточных условий, например, дублирующих одно другое или тождественно истинных, обработка которых является излишней с точки зрения выполнения запроса.
2) Усовершенствование — действие, при котором в некотором роде усложняется структура запроса, но это ведет к оптимизации его выполнения.
3) Преобразование запроса — изменение запроса, не относящееся ни к сокращениям, ни к усовершенствованиям запроса, и играющее роль, служебную по отношению к иным формам оптимизации запроса, например, стандартизация формы представления запроса.
Лексическая оптимизация путем сокращения запросов
Сокращение запросов является наиболее распространенным действием и предполагает собой повышение лаконичности и уменьшение условий выборки при сохранении семантической целостности. Если учесть то, что каждое условие в запросе требует определенных затрат ресурсов на обработку, то любые семантические повторы в ограничении выборки приводят к росту задержек на обработку запроса. Соответственно, устранение подобных случаев избыточности на стадии написания запроса до его компиляции и выполнения может существенным образом оптимизировать данный запрос.
Основные идеи лексической оптимизации путем сокращения запросов сводятся к следующим:
• Исключение избыточных операций;
• Упрощение выражений, использующих пустые отношения и тривиальные условия;
• Вынос общих выражений «за скобки».
Пример использования сокращения запросов путем использования реляционной алгебры для уменьшения логических выражений можно представить формулой [2]:
((a AND b) AND c OR (((a AND b) AND (c AND d)))) = > (a AND b AND c) OR (a AND b AND c AND d) (1)
Далее формулу (1) можно еще упростить получив в итоге:
(a AND b AND c) (2)
В ходе исследования был проведен эксперимент, в котором в качестве условий выборки были представлены аналогичные формулам (1) и (2) логические условия. Оба запроса выполнялись на центральном сервере ДонНТУ. Для достоверности результатов, каждый запрос выполнялся по 5 раз, так как загруженность центрального сервера в разные моменты времени может отличаться и это может оказать существенное влияние на время выполнения. Условия запросов представлены на рисунке 2.
Рисунок 2. Запрос до и после применения лексической оптимизации путем сокращения.
При выполнении двух данных запросов, имеется одинаковый набор данных, что свидетельствует о правильном применении законов реляционной алгебры. Временные параметры, которые необходимы для определения эффективности оптимизации сведены в таблицу 1. Результаты получены средствами отладчика запросов MS SQL Management Studio.
Таблица 1 — Результаты выполнения запроса до и после оптимизации.
Из результатов работы определено, что среднее время выполнения неоптимизированного запроса составляет 126.8мс, в то время как время выполнения оптимизированного запроса составило 111мс. Можно сделать вывод, что трансформация формулы (1) в (2) привела к уменьшению времени выполнения запроса на 12.5%.
Лексическая оптимизация путем усовершенствования запросов
Технология усовершенствования запросов базируется на усложнении структуры запроса, включении в него новых временных таблиц, использование которых позволяет сократить расходы на обработку исходного запроса. Большинство алгоритмов, решающих эту задачу, относятся к технологии «магических множеств» [2].
Алгоритм магических множеств относится к числу алгоритмов лексической оптимизации запроса. Он означает перезапись запроса, исключающую генерацию нерелевантных связей путем вычисления дополнительных таблиц, которые содержат связывания, используемые для ограничения таблицы, и действуют как фильтры.
Перезапись исходного запроса с использованием этих фильтров включает следующие основные этапы:
• анализ и поиск неоптимальных связей в рамках реализации запроса;
• создание дополнительных (магических) таблиц;
• интеграцию магических таблиц в уже существующее ограничение и изменение описания существующих условий.
Лексическая оптимизация путем преобразования запросов
Критерием классификации алгоритма как относящегося к числу алгоритмов простого преобразования является его функциональное предназначение [2]. Если итогом работы некоторого алгоритма должно стать обретение запросом более оптимальной формы с точки зрения того или иного критерия (например, числа условий в ограничении), то алгоритм может быть отнесен к числу алгоритмов сокращения или усовершенствования. Если же алгоритм, преобразует запрос к иному виду, к примеру, меняя порядок операций, то в данном случае речь идет о простом преобразовании запроса.
К технологиям преобразования нужно отнести алгоритмы стандартизации запросов, приведения их к универсальной стандартной форме в целях дальнейшей обработки. Наиболее распространенным видом преобразования запросов является перенос логических условий вниз по дереву запроса. Важным аспектом является перемещение селективных операций ниже конструктивных операций, таких, как соединение и декартово произведение, чтобы можно было выполнить селективные операции как можно раньше, для меньших ресурсозатрат.
Выводы
При выборке многосвязных данных большого объема в реляционных базах данных, вопрос оптимизации запросов является весьма актуальным, так как при большой загруженности сервера время выполнения запросов и затраты ресурсов могут играть большую роль.
При исследовании стандартного оптимизатора на примере Microsoft SQL Server были выявлены основные особенности и принципы его работы. Также рассмотрены основные методы лексической оптимизации запросов, проведен эксперимент оптимизации путем сокращения, который показал уменьшение времени выполнения запроса на 12,5%.
Литература
1. Microsoft SQL Server 2012. Руководство для начинающих: Пер. с англ. — СПб.:БХВ-Петербург, 2013, - 816 с.: ил.
2. Обзор развития методов лексической оптимизации запросов. Труды Института системного программирования РАН Том 23. 2012 г. Стр. 195-214.