Вопрос оптимизации запросов всегда является актуальным как для разработчиков баз данных, так и для программистов, которые с ними работают. В современных системах управления базами данных (СУБД) содержится компонент, называющийся оптимизатором. Необходимо рассмотреть его работу и выбрать возможные пути изменения запроса или базы данных (БД) таким образом, чтобы оптимизатор тратил меньше времени и ресурсов на построение плана выполнения запроса и его реализацию.
Существуют несколько различных подходов и методов оптимизации запросов, но первоочередным является лексическая оптимизация на уровне языка SQL с целью анализа текста запроса для выявления избыточности.
Организация учебного процесса является глобальной задачей в вузе, которая состоит из группы составных частей и требует множества ресурсов и времени. Поэтому очень важной задачей является автоматизация данного процесса.
Также актуальным вопросом в рамках действующей АСУ является оптимизация запросов на стадии их разработки, так как в большинстве задач используются большие запросы с множественной связкой таблиц между разными базами данных. На выполнение таких запросов может уходить до нескольких десятков секунд, так как происходит многократное соединение с сервером от различных пользователей. Поэтому оптимизировав запрос на стадии проектирования можно существенно снять нагрузку с сервера и ускорить работу приложений.
Научная новизна работы состоит в повышении эффективности существующих алгоритмов оптимизации запросов с целью улучшения работы действующей автоматизированной системы управления ДонНТУ.
Практическая часть состоит в разработке программы автоматизированного формирования нагрузки на кафедру в рамках всего ВУЗа, с целью уменьшения трудозатрат персонала кафедры.
Основной задачей в рамках данного проекта является разработка компьютерной программы для действующей АСУ вуза, реализующей формирование общей нагрузки по кафедре на базе информации из учебных планов вуза на заданный семестр и обеспечивающей минимизацию трудозатрат сотрудников кафедры при формировании нагрузки.
Список целей, которые необходимо выполнить в рамках магистерской работы:
1) Изучение технологии составления и формирования учебного процесса в ВУЗе;
2) Изучение технологии формирования нагрузки на кафедру в настоящее время;
3) Разработка плана по автоматизации процесса формирования нагрузки на кафедру;
4) Разработка структуры программного обеспечения (ПО) и набора необходимых функций.
5) Разработка структуры БД для реализации поставленной задачи.
Результатами успешного выполнения магистерской работы должны являться:
1) Desktop — версия приложения для автоматизированного формирования нагрузки на кафедру в рамках вуза;
2) Web — версия приложения для просмотра сформированной нагрузки.
3) Необходимая структура таблиц в БД, которые будут хранить полученные данные о нагрузке и будут участвовать в формировании нагрузки на преподавателей и при составлении расписания.
Существует множество видов и методов оптимизации запросов, исследованиями которых занимаются множество пользователей и программистов, работающими с базами данных.
Что касается вопроса об автоматизации процесса формирования нагрузки кафедры, то данная задача является довольно специфичной. Соответственно разработок в этой области намного меньше.
3.1 Обзор международных источников
В мире существует множество работ и публикаций на тему оптимизации запросов. Публикаций на тему автоматизированной нагрузки на кафедру найдено не было. Ниже приведен список наиболее популярных публикаций, авторы которых внесли весомый вклад в развитие данной отрасли.
Публикация Ionnidis Y. E. Query Optimization // The Computer Science and Engineering Handbook. Наиболее распространенная статья, в которой идет речь об основных понятиях и принципах оптимизации запросов [2].
Публикация Jarke M., Koch J. Query Optimization in Database Systems. Рассматривается методы семантической и логической оптимизации запросов [5].
Публикация Chaudhari S. An Overview of Query Optimization in Relational Systems. Рассматриваются методы оптимизации запросов в реляционных системах [6].
Публикация Graefe G. Query Evaluation Techniques for Large Databases. Рассмотрена концепция алгоритмов для управления системой доступа к большому набору данных [7].
Публикация Ozsu M. N., Valduriez P. Principles of Distributed Database Systems. В книге идет речь об особенностях работы с распределенными базами данных и СУБД [8].
3.2 Обзор национальных источников
В России и Украине также множество ученых занимается исследованиями в области оптимизации запросов. Список наиболее популярных публикаций будет приведен ниже.
В области разработок автоматизированных систем формирования нагрузки кафедры есть несколько разработок и публикаций Российских авторов. В качестве примера можно привести лабораторию математического моделирования и информационных систем (ММИС). Данная лаборатория занимается разработкой программного обеспечения для автоматизации учебного процесса высших учебных заведений. Была разработана автоматизированная система «Нагрузка ВУЗа», которая обеспечивает комплексный подход к формированию и распределению учебной нагрузки [9].
Публикация Гаврилец Е.З., Медведева О.А. Автоматизированная система формирования учебных планов и распределения учебной нагрузки преподавателей кафедры вуза. В данной статье описаны основные функции и возможности разработанной системы [10].
Публикация Каюгина С.М. Автоматизированная система расчета и распределения учебной нагрузки преподавателей кафедры вуза на базе платформы «1С». Статья посвящена решению вопроса автоматизации расчёта объёма учебной нагрузки и её распределения между преподавателями кафедры ВУЗа [11].
Публикация Зверев Д. Л. Оптимизация потоков простых SQL-запросов. В работе рассмотрены вопросы синтеза сложных запросов из множества простых [3].
3.3 Обзор локальных источников
Студентов, которые в рамках ДонНТУ занимались разработками в области автоматизации процесса формирования нагрузки на кафедру найдено не было, однако есть студенты, которые занимались исследованиями в области оптимизации запросов.
Работа магистра ДонНТУ Заславского В.А. Система оптимизации клиентских запросов к серверам распределённой базы данных. В работе идет речь о применении различных методов оптимизации запросов в частности, муравьиный алгоритм [12].
Работа магистра ДонНТУ Стародубцева М.В. Исследование методов доступа к данным MS SQL Server. В работе проводится исследование существующих провайдеров данным БД MS SQL Server на скорость доступа к записям таблиц [13].
Работа магистра ДонНТУ Бабич К.К. Оптимизации для высоконагруженных реляционных БД и альтернативные решения. В работе идет речь о создании высоконагруженной веб-системы и применении оптимизации реляционных баз данных, для решения задачи множественного доступа и высокой посещаемости [14].
Основополагающим элементом в формировании учебного процесса в семестре после разработки учебных планов является формирование нагрузки по кафедрам (рис.1). Реализовав автоматизацию данной проблемы, в дальнейшем можно будет автоматизировать задачи: «расчет нагрузки по преподавателям», «журнал учета выполненных работ преподавателя», а также решить весьма важную задачу автоматического составления расписания занятий по ВУЗу.
Рисунок 1. Схема формирования учебного процесса на семестр.
Программа будет осуществлять выборку данных из набора учебных планов, хранящихся в БД центрального сервера ВУЗа, согласно заданных параметров отбора: (учебный год, семестр, кафедра и др.), формировать кафедральную нагрузку с возможностью ее редактирования и утверждения.
4.1 Исследование процесса формирования нагрузки в настоящее время
В настоящее время, каждый факультет, формирует нагрузку на семестр только в рамках своего факультета на базе информации собственных учебных планов в локальной БД. Итоговый документ с нагрузкой по кафедрам в формате EXCEL сохраняется на центральный сервер в папку «Нагрузка». Потом, каждая кафедра вручную из отдельных файлов с нагрузкой по факультетам, составляет документ с общей нагрузкой по кафедре и производит его редактирование, согласно методике от Учебного отдела ВУЗа (рис. 2). Проектируемая программа должна минимизировать работу кафедры по формированию сводной нагрузки и автоматизировать данный процесс.
Рисунок 2. Процесс формирования нагрузки на кафедру в настоящее время
(анимация: 6 кадров, 5 циклов повторения, 72 килобайт)
4.2 Набор необходимых функций разрабатываемого приложения
Установлено, что программа должна включать в себя следующие функции:
1) Авторизация и определение программной роли пользователя и связанных с ней прав доступа и набора функций;
2) Выборка необходимых дисциплин в целом по ВУЗу по каждой кафедре из сборника учебных планов, хранящихся на Центральном сервере, согласно заданным параметрам (код кафедры, учебный год, семестр, и т.д.);
3) Выполнение функций объединения групп в потоки согласно установленных методик в вузе;
4) Расчет планируемого количества ставок по кафедре в зависимости от сформированной нагрузки;
5) Сохранение результатов работы в базе данных;
6) Визуализация нагрузки по кафедре в виде веб-приложения;
7) Формирование выходных отчетов по нагрузке кафедры;
Права пользователей и набор доступных функций программы будут инициализироваться в момент его авторизации при старте программы и определяться по присвоенной логину программной роли, закрепленной администратором системы. Зная необходимый набор функций, которыми должен обладать разрабатываемый продукт, можно построить схему процесса автоматизированного формирования нагрузки (рис.3).
Рисунок 3 — Схема процесса автоматизированного формирования нагрузки на кафедру при помощи разрабатываемого приложения.
4.3 Выбор языка программирования, среды разработки и базы данных для реализуемого проекта
Поскольку разработка будет являться частью действующей АСУ ВУЗа, то в качестве базы данных будет использоваться — Microsoft SQL Server 2012. Desktop версию программы целесообразно разрабатывать на языке программирования C#, так как компания Microsoft предоставляет удобный инструмент и среду для разработки приложений на данном языке. Также, язык C# легко связать с используемой базой данных, не прибегая к подключению сторонних продуктов или библиотек.
5.1 Исследование работы стандартного оптимизатора на примере MS SQL Server
Оптимизатор [1] — подкомпонент системы управления базой данных, который принимает входной аргумент в виде текста запроса и рассматривает возможные стратегии исполнения запроса, после чего выбирает из них наиболее эффективную. Выбранная стратегия и будет планом исполнения запроса. Оптимизатор принимает решение, учитывая такие факторы, как размер таблиц, из которых проводится выборка, существующие в таблицах индексы и всевозможные логические операторы (AND, OR, NOT), используемые в предложении WHERE.
Основной задачей оптимизатора является выборка наиболее эффективного плана выполнения запроса. Эта задача разбивается на 4 основных этапа, которые представлены на рисунке 4.
1) Синтаксический разбор(parsing). При выполнении синтаксического анализа, проверяется синтаксис запроса и запрос преобразовывается в дерево. После этого, выполняется проверка всех объектов базы данных, на которые ссылается запрос. (Например, проверка наличия в базе данных столбцов, указанных в запросе). После завершения работы создается окончательное дерево запроса.
2) Компиляция запроса (query compilation). На этом этапе дерево запроса компилируется оптимизатором.
3) Оптимизация запроса (query optimization). Оптимизатор в качестве входных параметров на данном этапе принимает скомпилированное дерево запроса и исследует различные стратегии обращения к данным, прежде чем решить, как обрабатывать данный запрос. Чтобы отыскать оптимальный план выполнения запроса, оптимизатор сначала выполняет анализ запроса, в процессе которого ищет аргументы поиска и операции соединения. Затем оптимизатор решает, какие индексы использовать. Далее, если в запросе есть операции соединения, оптимизатор выбирает методы соединения и метод обработки.
4) Выполнение запроса (query execution). Созданный план выполнения сохраняется как основной и затем выполняется.
Рисунок 4. Основные этапы обработки запроса.
5.2 Изучение и применение основных методов лексической оптимизации запросов
Для выполнения лексической оптимизации [2, 3] запросов, единственным источником информации является сам текст запроса как лексическая конструкция, и иные сведения о базе данных и ее структуре в анализе не используются. Процесс лексической оптимизации включает в себя анализ ограничения запроса, сравнение содержащихся в нем условий с целью выявления избыточности.
Лексическая оптимизация может устранять неоптимальности запроса тремя различными способами [4]:
1) Сокращение запроса - удаление избыточных условий, например, дублирующих одно другое или тождественно истинных, обработка которых является излишней с точки зрения выполнения запроса, а также условий, делающих запрос невыполнимым, противоречащих друг другу или тождественно ложных. При обнаружении таковых условий все ограничение или его часть признается ложной и исключается из выполнения запроса.
2) Усовершенствование — действие, при котором в некотором роде усложняется структура запроса, но ведет к оптимизации его выполнения.
3) Преобразование запроса — изменение запроса, не относящееся ни к сокращениям, ни к усовершенствованиям запроса, и играющее роль, служебную по отношению к иным формам оптимизации запроса, например, стандартизация формы представления запроса.
5.2.1. Лексическая оптимизация путем сокращения запросов
Сокращение запросов является наиболее распространенным и предполагает собой повышение лаконичности и уменьшение условий выборки при сохранении семантической целостности. Если учесть то, что каждое условие в запросе требует определенных затрат ресурсов на обработку, то любые семантические повторы в ограничении выборки приводят к росту задержек на обработку запроса. Аналогичным образом, выполнение тождественно ложных или правдивых условий повышает затраты системного времени на обработку и выполнение запроса. Соответственно, устранение подобных случаев избыточности на стадии написания запроса до его компиляции и выполнения может существенным образом оптимизировать данный запрос.
Основные идеи лексической оптимизации путем сокращения запросов сводятся к следующим:
• Исключение избыточных операций;
• Упрощение выражений, использующих пустые отношения и тривиальные условия;
• Вынос общих выражений «за скобки».
5.2.2. Лексическая оптимизация путем усовершенствования запросов
Технология усовершенствования запросов базируется на усложнении структуры запроса, включении в него новых табличных выражений, использование которых позволяет сократить расходы на обработку исходного запроса. Большинство алгоритмов, решающих эту задачу, относятся к технологии «магических множеств».
Алгоритм магических множеств относится к числу алгоритмов лексической оптимизации запроса. Он означает перезапись запроса, исключающую генерацию нерелевантных связей путем вычисления дополнительных виртуальных таблиц, которые содержат связывания, используемые для ограничения таблицы, и действуют как фильтры.
Перезапись исходного запроса с использованием этих фильтров включает следующие основные этапы:
• анализ и поиск неоптимальных связей в рамках реализации запроса;
• создание дополнительных (магических) таблиц и интеграцию магических таблиц в уже существующее ограничение и изменение описания существующих условий.
5.2.3. Лексическая оптимизация путем преобразования запросов
Критерием классификации алгоритма как относящегося к числу алгоритмов простого преобразования является его функциональное предназначение. Если итогом работы некоторого алгоритма должно стать обретение запросом более оптимальной формы с точки зрения того или иного критерия (например, числа условий в ограничении), то алгоритм может быть отнесен к числу алгоритмов сокращения или усовершенствования. Если же алгоритм, преобразует запрос к иному виду, к примеру, меняя порядок операций, то в данном случае речь идет о простом преобразовании запроса.
К технологиям преобразования нужно отнести алгоритмы стандартизации запросов, приведения их к универсальной стандартной форме в целях дальнейшей обработки. Наиболее распространенным видом преобразования запросов является перенос логических условий вниз по дереву запроса. Важным аспектом является перемещение селективных операций ниже конструктивных операций, таких как соединение и декартово произведение, чтобы выполнять селективные операции как можно раньше, так как на это тратится меньше ресурсов.
При выборке многосвязных данных большого объема в реляционных базах данных, вопрос оптимизации запросов является весьма актуальным, так как при большой загруженности сервера время выполнения запросов и затраты ресурсов могут играть большую роль.
При исследовании стандартного оптимизатора на примере Microsoft SQL Server были выявлены основные особенности и принципы его работы.
Также были проанализированы существующие технологии автоматизации учебного процесса, выявлены задачи, которые необходимо реализовать с целью дальнейшего развития АСУ ВУЗа, выбраны база данных и среда разработки, при помощи которых будет реализован проект.
1. Microsoft SQL Server 2012. Руководство для начинающих: Пер. с англ. — СПб.:БХВ-Петербург, 2013, - 816 с.: ил.
2. Ionnidis Y. E. Query Optimization // The Computer Science and Engineering Handbook. Boca Raton: CRC Press, 1996. Pp. 1038-1054.
3. Зверев Д. Л. Оптимизация потоков простых SQL-запросов: Диссертация кандидата технических наук: 05.13.11. Санкт-Петербург: Санкт-Петербургский Государственный Университет Аэрокосмического Приборостроения, 2005. 169 сс.
4. Обзор развития методов лексической оптимизации запросов. Труды Института системного программирования РАН Том 23. 2012 г. Стр. 195-214.
5. Jarke M., Koch J. Query Optimization in Database Systems // ACM Computing Surveys (CSUR), 1984. March, Volume 16, Issue 2. Pp. 111-152.
6. Chaudhari S. An Overview of Query Optimization in Relational Systems // Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. New York: SIGMOD, 1998. Pp. 34-43.
7. Graefe G. Query Evaluation Techniques for Large Databases // ACM Computing Surveys, 1993. Volume 25, Issue 2. P. 73-169.
8. Ozsu M. N., Valduriez P. Principles of Distributed Database Systems. Second Edition. New Jersey: Prentice Hall International, 1999. 666 pp.
9. Автоматизированная система «Нагрузка ВУЗа» [Электронный ресурс] // URL: http://www.mmis.ru/Default.aspx?tabid=170 (дата обращения: 03.05.2015).
10. Гаврилец Е.З., Медведева О.А. АВТОМАТИЗИРОВАННАЯ СИСТЕМА ФОРМИРОВАНИЯ УЧЕБНЫХ ПЛАНОВ И РАСПРЕДЕЛЕНИЯ УЧЕБНОЙ НАГРУЗКИ ПРЕПОДАВАТЕЛЕЙ КАФЕДРЫ ВУЗА // Современные наукоемкие технологии. — 2007. — № 2. — С. 40-41;
11. Каюгина С.М. Автоматизированная система расчета и распределения учебной нагрузки преподавателей кафедры вуза на базе платформы «1С» [Электронный ресурс] // Современные научные исследования и инновации. 2015. № 11, URL: http://web.snauka.ru/issues/2015/11/58943 (дата обращения: 03.05.2015).
12. Заславский В.А. Система оптимизации клиентских запросов к серверам распределённой базы данных. [Электронный ресурс] // Портал Магистров ДонНТУ, 2011г. URL: http://masters.donntu.ru/2011/fknt/zaslavskiy/ (дата обращения: 08.05.2015).
13. Стародубцев М.В. Исследование методов доступа к данным MS SQL Server. [Электронный ресурс] // Портал Магистров ДонНТУ, 2008г. URL: http://masters.donntu.ru/2008/fvti/starodubtsev/masterwork/index.htm (дата обращения: 08.05.2015).
14. Бабич К.К. Оптимизации для высоконагруженных реляционных БД и альтернативные решения. [Электронный ресурс] // Портал Магистров ДонНТУ, 2013г. URL: http://masters.donntu.ru/2013/fknt/babich/index.htm (дата обращения: 08.05.2015).
English
Українська