#CDB zapiska 1

\documentclass[12pt]{article}
% Эта строка — комментарий, она не будет показана в выходном файле
\usepackage{ucs}
\usepackage[utf8]{inputenc} % Включаем поддержку UTF8
\usepackage[russian]{babel}  % Включаем пакет для поддержки русского языка
\title{Отчёт по численным методам}
\date{}
\author{}

\usepackage{geometry} % А4, примерно 28-31 строк(а) на странице
    \geometry{paper=a4paper}
    \geometry{includehead=false} % Нет верх. колонтитула
    \geometry{includefoot=true}  % Есть номер страницы
    \geometry{bindingoffset=0mm} % Переплет    : 0  мм
    \geometry{top=20mm}          % Поле верхнее: 20 мм
    \geometry{bottom=25mm}       % Поле нижнее : 25 мм
    \geometry{left=25mm}         % Поле левое  : 25 мм
    \geometry{right=25mm}        % Поле правое : 25 мм
    \geometry{headsep=10mm}  % От края до верх. колонтитула: 10 мм
    \geometry{footskip=20mm} % От края до нижн. колонтитула: 20 мм
\usepackage{amsmath}    % \bar    (матрицы и проч. ...)
\usepackage{amsfonts}   % \mathbb (символ для множества действительных чисел и проч. ...)
\usepackage{mathtools}  % \abs, \norm
    \DeclarePairedDelimiter\abs{\lvert}{\rvert}
    \DeclarePairedDelimiter\norm{\lVert}{\rVert}
\usepackage{listings} %листинги

\lstset{
  basicstyle=\ttfamily,
  columns=fullflexible,
  keepspaces=true,
  frame=top,frame=bottom,
}

\usepackage[table,xcdraw]{xcolor}

 %для подсветки листинга javascript
 \usepackage{color}
\definecolor{lightgray}{rgb}{.9,.9,.9}
\definecolor{darkgray}{rgb}{.4,.4,.4}
\definecolor{purple}{rgb}{0.65, 0.12, 0.82}

\lstdefinelanguage{JavaScript}{
  keywords={typeof, new, true, false, catch, function, return, null, catch, switch, var, if, in, while, do, else, case, break},
  keywordstyle=\color{blue}\bfseries,
  ndkeywords={class, export, boolean, throw, implements, import, this},
  ndkeywordstyle=\color{darkgray}\bfseries,
  identifierstyle=\color{black},
  sensitive=false,
  comment=[l]{//},
  morecomment=[s]{/*}{*/},
  commentstyle=\color{purple}\ttfamily,
  stringstyle=\color{red}\ttfamily,
  morestring=[b]',
  morestring=[b]"
}

\lstset{
   language=JavaScript,
   %backgroundcolor=\color{lightgray},
   extendedchars=true,
   basicstyle=\footnotesize\ttfamily,
   showstringspaces=false,
   showspaces=false,
   %numbers=left,
   %numberstyle=\footnotesize,
   %numbersep=9pt,
   %tabsize=2,
   breaklines=true,
   showtabs=false,
   captionpos=b
}


\begin{document}
    \newpage
    {
        \thispagestyle{empty}
        \centering

        \textbf{
        МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ Н. Э. БАУМАНА \\
        Факультет информатики и систем управления \\
        Кафедра теоретической информатики и компьютерных технологий}
        \bigskip
        \bigskip
        \bigskip
        \bigskip
        \bigskip
        \bigskip
        \bigskip

        \vfill

        {\large Лабораторная работа №3}\\
        по курсу <<Численные методы>>\\
    \LARGE{<<Построение для таблично-заданной функции \\
            кубического сплайна,\\
            сплайна Акимы, \\
            Б-сплайна>>\\ }
    \normalsize

        \bigskip
        \vfill
        \hfill\parbox{5cm} {
            Выполнил:\\

            Проверила:\\

        }
        \vspace{\fill}


        Москва \number\year
        \clearpage
    }
    \newpage
    {
        \tableofcontents
        \clearpage
    }




    {
        \section{ВВЕДЕНИЕ}
    }

    Основная цель данной работы - конвертировать базу данных автоматизированной системы тестирования T-BMSTU, используемой на кафедре ИУ9 для проведения лабортаторных работ по курсам программирования, в формат MySQL. Сравнить производительность новой реализации базы и, при необходимости, оптимизировать запрос к базе, либо оптимизировать имеющуюся базу данных в новом формате. \\

    В ходе работы будет исследована имеющаяся исходная реализация базы в формате SQLite. Затем, данные из исходной базы будут извлечены и перенесены в новую, целевую базу данных с помощью конвертера. Затем в новый формат будет конвертирован модельный SQL запрос и будет исследовано его выполнение на новой базе данных. Этот запрос будет оптимизирован под целевую реализацию базы данных. \\

    Путем сравнения производительности реализаций ``новой'' и ``старой'' баз данных и запросов будет принято решение о целесообразности перехода на новую реализацию.

    \clearpage



        {
            \section{НЕОБХОДИМЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ}
        }

        Прежде всего стоит рассмтореть отличительные черты исходной и целевой СУБД. После этого мы сможем заключить, возможна ли в теории выгода от прехода от одной СУБД к другой.\\


        {
            \subsection{SQLite. Преимущества и недостатки}
        }

    SQLite является популярной встраиваемой реляционной базой данных. Релиз последней на данный момент версии одноименной СУБД (SQLite 3.14.1) состоялся в августе 2016 года. СУБД выпускается под общественной (public domain) лицензией, не накладывающей никаких ограничений на использование.

    Рассторим теперь особенности базы данных:\\


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

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


    Однако, у такой реализации есть и обратная сторона. Простота реализации достигается за счет того, что во время записи весь файл блокируется одним процессом. А значит, несколько процессов, одновременно подключенных к базе могут лишь считывать данные, в то время, как только один из них может изменять эти данные. Этот принцип, ``читают многие - пишет один'', является одним из недостатков этой СУБД. \\

    Еще одним недостатком является отсутствие полной поддержки SQL-92:
    \begin{itemize}
        \item[] Не поддерживается, например, удаление или изменение столбца в таблице:
            \begin{itemize}
            \item[] \verb| ALTER TABLE DROP COLUMN ... |
            \item[] \verb| ALTER TABLE ALTER COLUMN ... | отсутствуют в SQLite
            \end{itemize}
        \item[] Опущены \verb| RIGHT OUTER JOIN | и \verb| FOR EACH STATEMENT |
        \item[] По умолчанию отключена поддержка foreign key
        \item[] Недоступны хранимые процедуры
        \item[] Триггеры SQLite намного менее функциональны, нежели триггеры других СУБД
    \end{itemize}

    Для взаимодйствия с SQLite из приложений отсутствуют официальные драйвера. Таковых нет ни под JDBC, ни под ADO.Net, ни под ODBC. Отстутствие этого ``из коробки'' яляется существенным минусом SQLite.\\


    Еще одной особенностью SQLite является ``слабая типизация'', или концепция ``близости типов'' (type affinity). Так, тип столбца не определяет тип хранимого в этом столбце значения. В любой столбец может быть записано любое значение, а сам тип столбца используется для приведения значений к одному типу при сравнении значений. Все это позволяет создавать таблицу ``простым''  \verb| CREATE TABLE sampleTable| \verb|(col1, col2, col3) | без указания чего либо еще, что является недопустимым и недоступным в других СУБД.

    Однако, в SQLite доступны лишь 5 типов данных:
    \begin{itemize}
        \item[] NULL
        \item[] INTEGER (знаковое целое число до 8 байт)
        \item[] REAL (число с плавающей точкой, 8 байт в формате IEEE)
        \item[] TEXT (строка в кодировке UTF-8 или UTF-16)
        \item[] BLOB (входное значение, `как есть`)
    \end{itemize}

        Согласно руководству, для хранения типа Boolean рекомендуется использовать INTEGER 0 или 1, а Date и Time типы хранить в виде строк. Вышесказанное является одновременно как недостатком, так и достоинством и не может быть однозначно интерпретировано в рамках `общих` задачах. \\


    В SQLite также отсутствуют какие-либо механизмы репликации.

    Отсутствует система пользователей.

    Отсутствует возможность увеличения производительности.\\

    Несмторя на все это, SQLite является отличным кандидатом на использование в качестве встраиваемой системы и пользуется большой популярностью в этой сфере.


        {
            \subsection{MySQL. Преимущества и недостатки}
        }

        Теперь взглянем на целевую базу данных, MySQL.

        MySQL является самой распространенной СУБД. Разрабатывается корпорацией Oracle, как доступная под универсальной общественной лицензией GNU (GNU General Public License) замена промышленной БД Oracle.

        Рассмотрим особенности MySQL:\\


        MySQL разработана в соответствии с ``классической'' клиент-серверной архитектурой и поддерживает все основные ОС. Для работы с базой из приложений имеются официальные драйвера ADO.Net, JDBC и ODBC. Хотя количество языков, поддерживаемых API MySQL и меньше, чем у SQLite, недостатком это не является, так как упущены не самые популярные в настоящее время языки, такие, как Basic, Forth и Fortran.\\


        MySQL поддерживает большое количество типов данных:
            \begin{itemize}
            \item[] TINYINT (BOOL), SMALLINT, MEDIUMINT, INTEGER, BIGINT для целочисленных значений
            \item[] FLOAT, DOUBLE, NUMERIC, REAL для значений с плавающей точкой
            \item[] DATE, TIME, DATETIME, YEAR, TIMESTAMP для значений даты и времени
            \item[] CHAR, VARCHAR для строковых значений фиксированной / переменной длины
        \item[] TINYTEXT, TEXT, MEDIUMTEXT, LONGTEXT для тектовых значений длины $2^{8}-1$ / $2^{16}-1$ / $2^{24}-1$ / $2^{32}-1$ соответственно
            \item[] TINYBLOB, BLOB, MEDIUMBLOB, LONGBLOB для значений `как есть`
            \item[] ENUM, SET для занчений типа перечисление / множество
            \end{itemize}

    Это является существенным преимуществом MySQL перед SQLite, так как таблицы могут быть построены более оптимально в соответствии с бизнес логикой.\\


    Поддерживается почти полный стандарт SQL-92 (DML, DDL, DCL), хотя и присутствует проприетарное расширение синтаксиса. В частности, в этой БД используется свой синтаксис для написания триггеров, а также хранимых процедур, что не поддерживаются в SQLite. Однако, стоит отметить, что в MySQL упущены, в частности, INSTEAD OF триггеры, хотя они и могут быть самостоятельно реализованы отдельно.\\


    В Mysql присутствуют механизмы репликации, так как разработчики создавали функциональность по заказу лицензионных пользователей и это (репликация) является важным фактором при выборе БД для коммерческого использования. Так, поддерживается
        \begin{itemize}
            \item[] Многомастерная (Multi-master replication) репликация. Данные в данном случае хранятся группой устройств и могут быть изменены любым устройством из этой группы `мастеров`, так и
            \item[] Система с ведущими и ведомыми устройствами (Master-slave), где ведущая база данных рассматривается, как `авторитетный` источник данных, а подчиненные синхронизируются с ней.
        \end{itemize}

    Все это существенно повышает надежность работы этой БД и отличает ее от SQLite, где механизмы репликации впринципе отсутствуют.\\


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

    Присутствуют мехнизмы управления уровнем доступа пользователей, хотя отсутствуют механизмы деления пользователей на роли и группы.

    Система Mysql масштабируема.

    Также, среди преимуществ можно отметить наличие множества ``движков'' (database engine), каждый из которых обладает своими преимуществами и может быть выбран согласно решаемой задаче. В ходе работы некоторые из движков будут рассмторены чуть подробнее.

    Благодаря свободному доступу к исходному коду, эта СУБД может быть подстроена под индивидуальное решение. А вывсокая популярность системы обеспечивает наличие поддержки по многим возможным проблемам.\\


    Исходя из всего вышеперечисленного, переход с SQLite на MySQL видится разумным в рамках большей части задач общего назначения. MySQL объективно обладает большим числом преимуществ перед SQLite.

    Однако, в рамках курсовой работы рассматривается конкретная база данных автоматизированной системы тестирования T-BMSTU. И для оценки реальной выгоды от перехода с одной базы на другую необходимо прежде всего оценить уместность преимуществ MySQL перед SQLite в рамках конкретной задачи.

    Для этого рассмторим теперь исходную базу данных T-BMSTU.

    \bigskip


    {
        \section{ИЗУЧЕНИЕ ВХОДНЫХ ДАННЫХ}
    }

    Исходными данными курсовой работы являются SQL скрипт создания базы данных, непосредственно база данных в виде файла {\it tbmstu.db} и запрос, формирующий выборку данных из базы для отображения на Web-сервере тестирования.\\

    {
        \subsection{Исходная база данных T-BMSTU}
    }
    Взглянем на схему базы данных

    <здесь будет схема базы>
    %тут картинка схемы большая будет и вертикальная мб даже

    Исходная база данных содержит в себе 22 таблицы:
    \begin{verbatim}
        Institutions
        Subjects
        Modules
        Groups
        RelGroupsModules
        Persons
        Sessions
        CurrentAdmins
        CurrentTaskAuthors
        Students
        ModuleAuthors
        Approvers
        Languages
        Tasks
        RelTasksLanguages
        RelLanguagesModules
        Submissions
        FailedTests
        Comments
        Approvements
        RelTasksModules
    \end{verbatim}

        %отсортировать в порядке создания как по скрипту

    Также имеются 6 представлений:
    \begin{verbatim}
        TimeDesc
        RelModulesInstitutions
        RelSubmissionsApprovers
        FinalApprovements
        PersonRoles
        RelStudentsTasks
    \end{verbatim}

    Присутствуют 7 триггеров, выводящих сообщение об ошибке, в случае нарушений работы с внешники ключами (вставки и обновления):
    \begin{verbatim}
        fki_RelGroupsModules
        fku_RelGroupsModules
        fki_Tasks_PersonId
        fku_Tasks_PersonId
        fki_Approvements_PersonId
        fku_Approvements_PersonId
        fku_Submissions_PassedTests
    \end{verbatim}

    Назначение таблиц, представлений и триггеров понятно из их названий.

    В большинстве таблиц в базе хранится по несколько десятков записей - это таблицы со списками студентов групп, предметов и модулей, таблица-временная шкала, таблица авторов заданий. Есть таблицы на одну или несколько сотен записей: аккаунты в системе, задания, проверяющие и вспомогательные таблицы. Есть таблица университетов с одной записью, так как на данный момент система применятеся только в МГТУ. И есть 4 таблицы с десятками тысяч записей. В порядке убывания по количеству записей (по данным на февраль 2016):

    \begin{itemize}
        \item[] Sessions, ~ 130 тыс. записей
        \item[] Submissions, ~ 80 тыс. записей
        \item[] Comments, ~ 70 тыс. записей
        \item[] Approvements, ~70 тыс. записей.
    \end{itemize}

    Очевидно, что работа с этими таблицами представляет наибольшую сложность не только по причине частой записи в них, но и по причине того, что эти таблицы имеют дочерние записи и ссылаются на большое число других таблиц. Рассмотрим, например таблицу (скрипт создания) решений, отправленных на сервер тестирования - таблицу {\it Submissions}:\\


\begin{lstlisting}[caption={Скрипт создания таблицы Submissions}, label={lst:table_submissions}]
CREATE TABLE Submissions (
    SubmissionID    INTEGER NOT NULL PRIMARY KEY,

    PersonID    INTEGER NOT NULL,
    GroupID     INTEGER NOT NULL,
    TaskID      INTEGER NOT NULL,
    ModuleID    INTEGER NOT NULL,
    SubmissionTime  TEXT NOT NULL CHECK (length(SubmissionTime) < 32),

    LanguageID  INTEGER NOT NULL,
    SourceCode  TEXT NOT NULL CHECK (length(SourceCode) < 50*1024),
    Draft       INTEGER CHECK (Draft = 0 OR Draft = 1),

    SentToTestTime  TEXT,
    PassedTests INTEGER,
    TestingServerId INTEGER,

    UNIQUE (PersonID, GroupID, TaskID, ModuleID, SubmissionTime),
    FOREIGN KEY (PersonID, GroupID) REFERENCES Students
                                    ON DELETE CASCADE ON UPDATE CASCADE,
    FOREIGN KEY (TaskID, ModuleID)  REFERENCES RelTasksModules
                                    ON DELETE RESTRICT ON UPDATE CASCADE,
    FOREIGN KEY (GroupID, ModuleID) REFERENCES RelGroupsModules
                                    ON DELETE RESTRICT ON UPDATE CASCADE,
    FOREIGN KEY (TaskID, LanguageID) REFERENCES RelTasksLanguages
                                    ON DELETE RESTRICT ON UPDATE CASCADE,
    FOREIGN KEY (LanguageID, ModuleID) REFERENCES RelLanguagesModules
                                    ON DELETE RESTRICT ON UPDATE CASCADE
);
        \end{lstlisting}


    Как видно из листинга ~\ref{lst:table_submissions}, эта таблица ссылается сразу на 5 других таблиц. А значит, при добавлении записи в нее необходимо обратиться сразу к 5 таблицам. Также с этой таблицей работает триггер {\it fku\_Submissions\_PassedTests}, проверяющий наличие валидного сервера тестирования, назначенного по решению.

    Тут же становятся видны ограничения, озвученные ранее при анализе SQLite ``из коробки'', такие, как ограниченное число типов данных: {\it SubmissionTime} хранится в виде строки TEXT, {\it Dratf} хранится в виде INTEGER'а. Из-за этого приходится осуществлять валидацию входных данных проверяя длину или значние.

    Также необходимо соблюдение уникальности группы полей {\it PersonID, GroupID, TaskID, ModuleID, SubmissionTime} и PRIMARY KEY.

    Работа с этой таблицей весьма труднозатратна относительно работы с остальными таблицами в рамках базы данных.

    У этой таблицы имеются сразу 4 вручную созданных индекса. Учтем это в дальнейшем при возможной оптимизации этой таблицы. \\

    Таблиц, подобных этой, в базе еще 3. Нужно отметить, что таблица {\it Sessions} выделяется среди ``крупных таблиц'' своими размерами, а также относительной простотой работы: в ней есть только валидация ip-адреса по длине и ссылка на таблицу пользователей сервера для прикрепления его к сеансу. Поиск по этой таблице не нужен, поэтому есть только стандартный PRIMARY KEY

    Эти 4 таблицы постоянно используются в ходе работы сервера. Данные в них обновляются постоянно.

    Большинство данных остальных таблиц редактируется либо с началом модуля (например, таблицы {\it Modules, Tasks}), либо семестра (такие, как {\it Subjects, Groups, TimeScale}), либо с началом учебного года ({\it Persons, Groups, TimeScale}). Таблицы {\it Languages, CurrentAdmins, CurrentTaskAuthors, Institutions} редактируются еще реже. То есть, данные большей части таблиц редактируются совсем не часто. Но, бОльшая часть данных всей базы редактируется постоянно. Учтем это в дальнейшем.\\

    {
        \subsection{Исходный запрос к базе}
    }

    Во входных данных также присутствует запрос к описанной выше базе. Этот запрос формирует выборку данных для отображения на странце Web-сервера.
    Взглянем на запрос в его первоначальном варианте:\\

        %шрифт листинга поменьше бы чтоб хотя ы на 2 страницы

        \begin{lstlisting}[caption={Скрипт выборки из базы}, label={lst:bigq}]
SELECT DISTINCT
    Institutions.InstitutionId, Institutions.InstitutionName,
        /*****/
    Groups.GroupId, Groups.TimeId, TimeDesc.TimeName, Groups.GroupName,
        /*****/
    Subjects.SubjectId, Subjects.SubjectName,
        /*****/
    Modules.ModuleId, Modules.ModuleNo, Modules.ModuleName, Modules.MinRating,
    RelGroupsModules.ExpireTime, IsStudent, IsApprover,
        /*****/
    StTaskId, StTaskNo, StTaskName, StTaskRating, Status,
        /*****/
    SubmissionId, SubmPersonId, SubmLogin, SubmFirstName,
    SubmLastName, SubmTaskId, SubmTaskName, SubmissionTime
FROM (
    SELECT GroupId, ModuleId, max(IsStudent) AS IsStudent,
                              max(IsApprover) AS IsApprover
    FROM (
        SELECT Students.GroupId, ModuleId, 1 AS IsStudent, 0 AS IsApprover
        FROM Students
        JOIN RelGroupsModules USING(GroupId)
        WHERE PersonId = 1
        UNION SELECT GroupId, ModuleId, 0 AS IsStudent, 1 AS IsApprover
        FROM Approvers
        WHERE PersonId = 1
        )
    GROUP BY GroupId, ModuleId
    )
JOIN RelGroupsModules USING(GroupId, ModuleId)
JOIN Groups USING(GroupId)
JOIN Institutions USING(InstitutionId)
JOIN TimeDesc USING(TimeId)
JOIN Modules USING(ModuleId)
JOIN Subjects USING(SubjectId)
LEFT OUTER JOIN (
    SELECT * FROM (
        SELECT DISTINCT GroupId, ModuleId,
            TaskId AS StTaskId, TaskNo AS StTaskNo, TaskName AS StTaskName,
            TaskRating AS StTaskRating,
            (CASE
                WHEN count(SubmissionId) = 0 THEN 0
                WHEN max(AcceptedInTime) = 1 THEN 3
                WHEN max(AcceptedOutdated) = 1 THEN 4
                WHEN count(SubmissionId) > count(AcceptedInTime)+
                                           count(AcceptedOutdated) THEN 1
                ELSE 2
            END) AS Status,
            NULL AS SubmissionId, NULL AS SubmPersonId,
            NULL AS SubmLogin, NULL AS SubmFirstName,
            NULL AS SubmLastName, NULL AS SubmTaskId,
            NULL AS SubmTaskName, NULL AS SubmissionTime
        FROM (
            SELECT DISTINCT Students.PersonId,
                RelGroupsModules.GroupId, RelGroupsModules.ModuleId,
                RelTasksModules.TaskId, RelTasksModules.TaskNo, Tasks.TaskName,
                RelTasksModules.TaskRating, Submissions.SubmissionId,
                (SELECT Accepted
                FROM Approvements
                WHERE Approvements.SubmissionId = Submissions.SubmissionId
                    AND (RelGroupsModules.ExpireTime IS NULL
                    OR Submissions.SubmissionTime < RelGroupsModules.ExpireTime)
                ORDER BY ApprovementTime DESC
                LIMIT 1
                ) AS AcceptedInTime,
                (SELECT Accepted
                FROM Approvements
                WHERE Approvements.SubmissionId = Submissions.SubmissionId
                    AND RelGroupsModules.ExpireTime IS NOT NULL
                    AND Submissions.SubmissionTime >= RelGroupsModules.ExpireTime
                ORDER BY ApprovementTime DESC
                LIMIT 1
                ) AS AcceptedOutdated
            FROM Students, RelGroupsModules
            LEFT OUTER JOIN RelTasksModules USING(ModuleId)
            LEFT OUTER JOIN Tasks USING(TaskId)
            LEFT OUTER JOIN Submissions
                ON Submissions.PersonId = 1
                AND Submissions.GroupId = RelGroupsModules.GroupId
                AND Submissions.TaskId = RelTasksModules.TaskId
                AND Submissions.ModuleId = RelGroupsModules.ModuleId
                AND (Submissions.Draft IS NULL OR Submissions.Draft = 0)
            WHERE Students.PersonId = 1 AND
                Students.GroupId = RelGroupsModules.GroupId
            )
        GROUP BY GroupId, ModuleId, TaskId
        )
    UNION SELECT DISTINCT Approvers.GroupId, Approvers.ModuleId,
        NULL AS StTaskId, NULL AS StTaskNo, NULL AS StTaskName,
        NULL AS StTaskRating, 0 AS Status,
        Submissions.SubmissionId, Submissions.PersonId AS SubmPersonId,
        Persons.Login AS SubmLogin, Persons.FirstName AS SubmFirstName,
        Persons.LastName AS SubmLastName, Tasks.TaskId AS SubmTaskId,
        Tasks.TaskName AS SubmTaskName, Submissions.SubmissionTime
    FROM Approvers
    LEFT OUTER JOIN Submissions
        ON Submissions.GroupId = Approvers.GroupId
        AND Submissions.ModuleId = Approvers.ModuleId
        AND Draft = 0
        AND NOT EXISTS (
            SELECT * FROM Approvements
            WHERE Approvements.SubmissionId = Submissions.SubmissionId
        )
    LEFT OUTER JOIN Tasks
        ON Tasks.TaskId = Submissions.TaskId
    LEFT OUTER JOIN Persons
        ON Persons.PersonId = Submissions.PersonId
    WHERE Approvers.PersonId = 1
    ) AS Cont
    ON Cont.GroupId = Groups.GroupId
    AND Cont.ModuleId = Modules.ModuleId
ORDER BY
    Institutions.InstitutionId ASC,
    Groups.TimeId DESC,
    Groups.GroupId ASC,
    SubjectId ASC,
    ModuleNo ASC,
    StTaskNo ASC,
    SubmissionTime ASC;
        \end{lstlisting}

        В запросе из Листинга ~\ref{lst:bigq} присутствуют 11 выборок с помощью SELECT из большей части таблиц базы. В том числе есть обращения к ``большим'' таблицам - {\it Submissions} и {\it Approvements}. Присутствует множество объединений таблиц, несколько группировок по учебным модулям и группам а также с использованием агрегирующих функций, несколько DISTINCT выборок и сортировок.

        Выполнять оптимизации согласно заданию, будем ``с оглядкой'' на этот запрос.\\


        \clearpage

        {
                \section{ПОРТИРОВАНИЕ БАЗЫ ДАННЫХ}
            }

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

        Стандартные реверс-инжиниринговые утилиты для портирования могут некорректно взаимодействовать со схемой базы данных и в результате некоторые таблицы могут не создаться, а внутреннее устройство других будет отличаться. К тому же нам необходимо произвести некоторые изменения типов согласно best practices, описанных в руководстве пользователя MySQL. %здесь ссыль

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


        Так как обе СУБД не полностью поддерживают формат SQL-92, простым запуском скрипта создания базы обойтись не удастся. Преобразуем исходный скрипт с учетом отличий диалекта SQL, используемого в SQLite от диалекта, используемого в MySQL. Также выполним преобразования типов данных, заменив строки, содержащие даты и время на тип DATETIME. Другие строковые константы заменим на тип VARCHAR, более предпочтительный в рамках MySQL. Своеобразный Boolean в SQLite, реализованый через INTEGER и проверку значений с помощью CHECK() заменим на TINYINT, являющийся, аналогом BOOLEAN'а в MySQL. Проведем еще некоторые преобразования и портируем триггеры, переведя их на проприетарный синткасис триггеров и хранимых прцедур MySQL.\\


        Считаем, что схема базы данных уже подготовлена. Напишем небольшую утилиту на $C\#$, которая с помощью технологии ADO.Net доступа приложений на платформе .Net к данным выберет все данные из базы SQLite и вставит в подготовленную схему базы MySQL. Единственной возможной проблемой является отсутствие официальных драйверов SQLite для ADO.Net, однако это решается загрузкой аналога  через встроенный менеджер пакетов NuGet. Запускаем утилиту и получаем на выходе наполненную базу данных MySQL с описанными выше изменениями. Триггеры необходимо добавить вручную.

        Поскольку никаких других существенных изменений сделано не было, схема базы данных и внутреннее устройство таблиц с точностью до типов некоторых столбцов остались без изменений и повторно приводить их не имеет смысла. Портирование на этом завершено. Считаем, что имеется полный MySQL аналог исходной SQLite базы.\\


        {
                \section{MYSQL ОПТИМИЗАЦИИ}
            }

            На данный момент имеется база данных MySQL. Можно считать, что все дальнейшие операции, если не оговорено иное, происходят над ней.

            Запрос, рассмотренный ранее в Листинге ~\ref{lst:bigq} не сработает в своем исходном виде на новой базе из-за отличия используемых диалектов. В MySQL у каждой выборки должен быть свой алиас (alias, псевдоним). Проименуем все таблицы в запросе, добавив к ним соответствующие технические наименования.

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

            Перейдем теперь к главной части этой работы - исследованию и оптимизации запроса и/или базы.\\


            {
                \subsection{Исследование выполнения запроса на базе MySQL}
            }

            Как уже отмечалось ранее, у MySQL имеются некоторые преимущества перед SQLite. Среди них - наличие команды EXPLAIN. При выполненеии любого запроса, оптимизатор запросов MySQL создает наиболее оптимальный план его выполнения. Этот план можно посмтореть с помощью команды EXPLAIN. Эта команда является одним из самых мощных инструментов разработчика, доступных в MySQL. \\

            Выполним эту команду вместе с запросом из Листинга ~\ref{lst:bigq}:
            %здесь результат

            <здесь результат первого EXPLAINа>
            %ссылка на рез-т эксплэина

            Взглянем на результат выполнения запроса в таблице <ссылка на рез-т explain'а>.
            Результат выполнения состоит из 11 столбцов:
            \begin{itemize}
                \item[] Id - порядковый номер SELECT'а внутри запроса
                \item[] Select\_type - тип запроса SELECT. Среди возможных значений:
                \begin{itemize}
                    \item[] PRIMARY - самый внешний запрос в JOIN'е
                    \item[] DERIVED - данный запрос является подзапросом
                    \item[] SUBQUERY - первый SELECT в подзапросе
                    \item[] UNION - второй или последующий SELECT в UNION'е
                    \item[] UNION RESULT - результат UNION'а
            \end{itemize}
            \item[] Table - таблица, к которой относится строка результата
            \item[] Type - тип связыания таблиц. Среди возможных значений:
            \begin{itemize}
                    \item[] Const - таблица имеет только одну соответствующую строку, которая проиндексирована. Таблица в данном случае читается лишь раз и в дальнейшем значение строки воспринимается, как константа. Это наиболее быстрый тип свзяывания
                    \item[] Eq\_ref - все части PRIMARY KEY или UNIQUE NOT NULL индекса используются для связывания. Еще один наилучший тип связывания
                    \item[] Ref - прямая ссылка. Все строки индексного столбца противопоставляются строкам предыдущей таблицы. Неплохой вариант
                    \item[] Index - сканирование всего индексного дерева для поиска строк
                    \item[] All - худший тип связи. Для нахождения строк используется полнотекстовое сканирование таблицы. Указывает на отсутствие подходящих индексов в таблице
            \end{itemize}
            \item[] Possible\_keys - возможные индексы. Возможно, они не используются. Значение NULL указывает на отсутствие подходящих индексов в таблице.
            \item[] Key - фактически использованный ключ. Может отличаться от указанных в {\it Possible\_keys} значений
            \item[] Key\_len - длина используемого ключа
            \item[] Ref - столбцы или константы, которые сравниваются с индексом
            \item[] Rows - число обработанных записей
            \item[] Filtered - процент отфильтрованных записей
            \item[] Extra - дополнительная информация об обработке запроса. Среди возможных значений:
            \begin{itemize}
                    \item[] Using index - информация получена с применением индексного дерева без доп. поиска для чтения строки. Возможно при всех проиндексированных столбцах.
                    \item[] Using temporary - создане временной таблицы. Например, при ORDER BY на наборе стобцов, отличном от набора в GROUP BY
                    \item[] Using filesort - Дополнительный проход с сохранением ключей строк, которые попали под условие WHERE и последующей сортировкой самих ключей.
                    \item[] Using join buffer (Block Nested Loop) - использование буфера для сохранения таблиц с последующим их объединением путем выборки подходящих строк из буфера
            \end{itemize}
        \end{itemize}

        Выше представлена интерпретация зачений резульатат EXPLAIN'а. Оценим результат нашего запроса:
        \begin{itemize}
            \item[] В процессе выполнения запроса полнотекстово сканируются сразу 6 таблиц, которые вполедствие хранятся в виде временных таблиц ({\it type: all})
            \item[] В первой выборке присутствует полное сканирование индексного дерева первой просматриваемой таблицы ({\it type: index}), несмотря на то, что в таблице содержится одна запись
            \item[] Большая длина используемого ключа таблицы первой выборки
            \item[] Использование индексного дерева ({\it extra: using index}) для создания временной таблицы ({\it extra: using temporary}) и дополнительный проход по временной таблице для сортировки ({\it extra: using filesort}) при том, что в таблице 1 запись
            \item[] Большое количество вложенных ({\it Select\_type: DERIVED}) запросов, 10 подзапросов
            \item[] Присутствуют 2 таблицы ({\it id: 5,6}) с большим количеством просмотренных записей (относительно результата запроса) ({\it rows: 2247})
            \item[] Отсутствуют данные о ключах в шести запросах ({\it id: 1, 4, 5, null, 2, null})
            \item[] Отсутствуют данные о количестве/проценте обработанных строк ({\it rows/filtered: null}) в процессе объединения ({\it select\_type: union reslut}) выборок {\it id:5 + id:10} и {\it id:3 + id:4}
        \end{itemize}



        {
                \subsection{Оптимизация запроса}
            }

        ``Узкие места'' запроса на данный момент ясны. Присупим к оптимизации запроса. Для этого вновь обратимся к best practices по оптимизации запросов из  руководства к MySQL и выполним некоторые преобразования.\\

        {
                \subsubsection{Оптимизация условия WHERE}
            }

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

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

        Среди возможных доступных, но еще не примененных оптимизаций выделяется ``углубление'' условия WHERE в запросе. Так, при JOIN'е выборка строк, подходящих под условие, будет осуществляться до объединения, а значит при выполнении запроса не придется просматривать конечную ``большую'' выборку.

        Протестируем для начала возможность подобной оптимизации:\\

\begin{lstlisting}[caption={тестовый запрос до оптимизации WHERE}, label={lst:test1where_before}]
SELECT SQL_NO_CACHE p.personID,  m.moduleID, s.taskID
    FROM submissions s
    JOIN persons p ON s.PersonID = p.PersonID
    JOIN modules m ON s.ModuleID = m.ModuleID
    WHERE p.PersonID BETWEEN 92 AND 109 AND m.ModuleName LIKE `%C%';
\end{lstlisting}


\begin{lstlisting}[caption={тестовый запрос после оптимизации WHERE}, label={lst:test1where_after}]
SELECT SQL_NO_CACHE p.personID, m.moduleID, s.taskID
    FROM submissions s
    JOIN (SELECT personID FROM persons
        WHERE PersonID BETWEEN 92 AND 109) p
    ON p.PersonID = s.PersonID
    JOIN (SELECT moduleID FROM modules WHERE ModuleName LIKE '%C%') m
    ON m.ModuleID = s.ModuleID;
\end{lstlisting}

\begin{table}[h]
    \caption {Сравнение таймингов запросов}
    \label {test1where}
    \begin{tabular}{|l|c|c|}
    \hline
    Запрос                  & Тайминг клиентской стороны & Тайминг серверной стророны                                                                                                                                                                                       \\ \hline
    До оптимизации     & 0.0471                     & 0.0463                                                                                                                                                                                                           \\ \hline
    После оптимизации  & 0.0313                     & 0.0317                                                                                                                                                                                                           \\ \hline
    \end{tabular}
\end{table}

%\begin{table}[h]
%    \caption {test1where}
%    \begin{tabular}{|l|}
%    \hline
%    Test query before                                                                                                                                                                                                                                                                                                                                      \\ \hline
%    \verb|SELECT SQL_NO_CACHE p.personID,  m.moduleID, s.taskID|\\ \verb|   FROM submissions s|\\ \verb|   JOIN persons p ON s.PersonID = p.PersonID|\\ \verb|   JOIN modules m ON s.ModuleID = m.ModuleID|\\ \verb|   WHERE p.PersonID BETWEEN 92 AND 109|\\ \verb|       AND m.ModuleName LIKE '%Программирование%';|                                                                          \\ \hline
%    Client side timing: 0.0471\\Server side timing: 0.0463                                                                                                                                                                                                                                                                                                 \\ \hline
%    Test query after                                                                                                                                                                                                                                                                                                                                       \\ \hline
%    \verb|SELECT SQL_NO_CACHE p.personID, m.moduleID, s.taskID|\\ \verb|    FROM submissions s|\\ \verb|    JOIN (SELECT personID FROM persons|\\ \verb|           WHERE PersonID BETWEEN 92 AND 109) p|\\ \verb|       ON p.PersonID = s.PersonID|\\ \verb|    JOIN (SELECT moduleID FROM modules|\\ \verb|           WHERE ModuleName LIKE `%Программирование%') m|\\ \verb|       ON m.ModuleID = s.ModuleID;|\\ \hline
%    Client side timing: 0.0313\\Server side timing: 0.0317                                                                                                                                                                                                                                                                                                 \\ \hline
%    \end{tabular}
%\end{table}

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

\begin{lstlisting}[caption={основной запрос до I оптимизации WHERE}, label={lst:bigq_where1_before}]
FROM Students as a3, RelGroupsModules as a4
LEFT OUTER JOIN RelTasksModules USING(ModuleId)
LEFT OUTER JOIN Tasks USING(TaskId)
LEFT OUTER JOIN Submissions
    ON Submissions.PersonId = 1 AND ...
    AND (Submissions.Draft IS NULL OR Submissions.Draft = 0)
WHERE a3.PersonId = 1
    AND a3.GroupId = a4.GroupId
\end{lstlisting}


\begin{lstlisting}[caption={основной запрос после I оптимизации WHERE}, label={lst:bigq_where1_after}]
FROM (
    SELECT PersonID, a3.GroupID, ModuleID, ExpireTime
        FROM Students as a3,
        relgroupsmodules as a4
        WHERE a3.PersonId = 1
            AND a3.GroupID = a4.GroupId
) as pg
\end{lstlisting}

%\begin{table}[h]
%    \caption {main1where1}
%    \begin{tabular}{|l|}
%    \hline
%    Main query before                                                                                                                                                                                                                                                                                                                                                                                                                                                                         \\ \hline
%               FROM Students as a3, RelGroupsModules as a4\\           LEFT OUTER JOIN RelTasksModules USING(ModuleId) \\          LEFT OUTER JOIN Tasks USING(TaskId) \\          LEFT OUTER JOIN Submissions \\              ON Submissions.PersonId = 1 \\              AND Submissions.GroupId = a4.GroupId \\             AND Submissions.TaskId = RelTasksModules.TaskId \\              AND Submissions.ModuleId = a4.ModuleId \\               AND (Submissions.Draft IS NULL OR Submissions.Draft = 0) \\         WHERE a3.PersonId = 1 AND \\                a3.GroupId = a4.GroupId  \\ \hline
%    Main query after                                                                                                                                                                                                                                                                                                                                                                                                                                                                          \\ \hline
%    FROM (\\           select PersonID, a3.GroupID, ModuleID, ExpireTime                               \#5\\           from Students as a3,\\              relgroupsmodules as a4\\            WHERE a3.PersonId = 1\\             AND a3.GroupID = a4.GroupId\\       ) as pg                                                                                                                                                                                                                                                                                        \\ \hline
%    \end{tabular}
%\end{table}

        На листингах ~\ref{lst:bigq_where1_before} и ~\ref{lst:bigq_where1_after} представлены запрос до и после оптимизации, озвученной выше. Существует еще одна возможность применить оптимизацию к основному запросу:\\

\begin{lstlisting}[caption={основной запрос до II оптимизации WHERE}, label={lst:bigq_where2_before}]
SELECT * FROM ( ... )
UNION SELECT ... FROM ...
LEFT OUTER JOIN Persons
    ON Persons.PersonId = Submissions.PersonId
WHERE a1.PersonId = 1
\end{lstlisting}

\begin{lstlisting}[caption={основной запрос после II оптимизации WHERE}, label={lst:bigq_where2_after}]
UNION SELECT ... FROM (
    SELECT * FROM Approvers
        WHERE PersonID = 1
) AS a1
\end{lstlisting}
%~\ref{lst:    }

        На листингах ~\ref{lst:bigq_where2_before} и ~\ref{lst:bigq_where2_after} применена еще одна аналогичная оптимизация WHERE.
%
%\begin{table}[h]
%    \caption {main1where2}
%    \begin{tabular}{|l|}
%    \hline
%    Main query before                                                                                                                                                                                 \\ \hline
%    SELECT * FROM ( ... )\\UNION SELECT ...\\LEFT OUTER JOIN Submissions \\LEFT OUTER JOIN Tasks \\\\LEFT OUTER JOIN Persons \\        ON Persons.PersonId = Submissions.PersonId \\   WHERE a1.PersonId = 1  \\ \hline
%    Main query after                                                                                                                                                                                  \\ \hline
%    \\\\        \\                                                                                                             \\ \hline
%    \end{tabular}
%\end{table}

        {
            \subsubsection{Оптимизация ORDER BY / GROUP BY}
        }

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

        Самым важным предусловием в данном случае является наличие индекса по всем столбцам, фигурирующим в GROUP BY. В таком случае создания дополнительной таблицы может не потребоваться и она будет заменена работой с индексным деревом.\\


        В MySQL заложены 2 способа выполнения GROUP BY запроса с использованием индексов:
        \begin{itemize}
            \item[] Loose Index Scan - ``свободное'' сканирование индеса. Самый эффективный способ обработки GROUP BY - когда индекс используется чтобы выбрать столбцы группировки. MySQL может в данном случае выгодно использовать свойство хранения ключей, подразумевающее их сортировку. Это свойство позволяет выбирать группы из индекса без необходимости рассматривать все ключи, удовлетворяющие условию WHERE. Сканирование в таком случае принято называть ``свободным''. Столбцы, фигурирующие в GROUP BY при этом обязательно должны составлять префикс в каком-либо из индексов. Есть и еще одно условие - допустимы только агрегирующие функции MIN() и MAX() и ссылаются они при этом на один и тот же столбец, присутствующий в индексе и следующий непосредственно за столбцами GROUP BY. Для стоблцов должны быть созданы полноценные индексы, индексирующие значения соответствующих столбцов полностью. В случае, если все это будет выполнено, в столбце {\it Extra} соответствующей выборки будет значение {\it Using index for group-by}. Однако, добиться выполнения всех этих условий довольно сложно. В таком случае применяется Tight Index Scan.
            \item[] Tight Index Scan - ``плотное'' сканирование индекса. В случае, если условия для свободного сканирования не могут быть выполнены, все еще можно добиться результата без создания дополнительной таблицы. Если в условии WHERE присутствует проверка диапазона значений, данный метод читает лишь индексы, удовлетворяющие условиям. Иначе он запускает сканирование индекса. Лишь после этих операций начинается группировка значений.
        \end{itemize}

        Проверим оптимизацию на примере, в котором применяется форсированное использование индекса:\\

\begin{lstlisting}[caption={тестовый запрос до оптимизации ORDER BY}, label={lst:test_order_before}]
SELECT SQL_NO_CACHE * FROM persons
    HAVING FirstName LIKE '%a%'
    ORDER BY FirstName;
\end{lstlisting}
%~\ref{lst:}

\begin{lstlisting}[caption={тестовый запрос после оптимизации ORDER BY}, label={lst:test_order_after}]
CREATE INDEX PersonsFirstNameIndex ON Persons(FirstName);
SELECT SQL_NO_CACHE * FROM persons FORCE INDEX (PersonsFirstNameIndex)
    HAVING FirstName LIKE '%a%'
    ORDER BY FirstName;
\end{lstlisting}
%~\ref{lst:}

        Выполним оба запроса. Сравним результаты выполнения:

\begin{table}[h]
    \caption {Сравнение таймингов запросов}
    \label {test1where}
    \begin{tabular}{|l|c|c|}
    \hline
    Запрос                  & Тайминг клиентской стороны & Тайминг серверной стророны                                                                                                                                                                                       \\ \hline
    До оптимизации     & 0.0160                     & 0.0159                                                                                                                                                                                                           \\ \hline
    После оптимизации  & 0.0                     & 0.0018                                                                                                                                                                                                           \\ \hline
    \end{tabular}
\end{table}

%
%\begin{table}[h]
%    \caption {test2order}
%    \begin{tabular}{|l|}
%    \hline
%    Test query before                                                                                                                                                                                                                                                                                        \\ \hline
%    SELECT SQL\_NO\_CACHE * FROM persons\\ HAVING FirstName LIKE '\%а\%'\\    ORDER BY FirstName;                                                                                                                                                                                                            \\ \hline
%    Client side timing: 0.0160\\Server side timing: 0.0159                                                                                                                                                                                                                                                   \\ \hline
%    Test query after                                                                                                                                                                                                                                                                                         \\ \hline
%    CREATE INDEX PersonsFirstNameIndex ON Persons(FirstName); \\\\SELECT SQL\_NO\_CACHE * FROM persons FORCE INDEX (PersonsFirstNameIndex)\\   HAVING FirstName LIKE '\%а\%'\\    ORDER BY FirstName;                                                                                                          \\ \hline
%    Client side timing: 0.0\\Server side timing: 0.0018                                                                                                                                                                                                                                                      \\ \hline
%    \end{tabular}
%\end{table}

        Как следует из результатов выше, данная оптимизация возможна. Для оптимизации ``боевого'' запроса мы можем добавить индесы на сорируемые /группируемые поля, либо добиться использования левых префиксов уже имеющихся индексов. В данном случае постараемся избавить от повторной выборки (таблицы {\it a7} и {\it a8}):\\

\begin{lstlisting}[caption={основной запрос до I оптимизации GROUP BY}, label={lst:bigq_group1_before}]
SELECT ...
    FROM (
    SELECT DISTINCT ... FROM ...
    GROUP BY GroupId, ModuleId, TaskId
) as a8
\end{lstlisting}
%~\ref{lst:}

\begin{lstlisting}[caption={основной запрос после I оптимизации GROUP BY}, label={lst:bigq_group1_after}]
SELECT ...
    FROM ( ... ) AS a7
GROUP BY GroupId, ModuleId, TaskId
\end{lstlisting}
%~\ref{lst:}


%\begin{table}
%    \caption {main2groupby1}
%    \begin{tabular}{|l|}
%    \hline
%    Main query before                                                              \\ \hline
%    SELECT DISTINCT ...\\FROM ...\\GROUP BY GroupId, ModuleId, TaskId \\         \\ \hline
%    Main query after                                                               \\ \hline
%    SELECT DISTINCT ...\\FROM ...\\... ) as a7\\GROUP BY GroupId, ModuleId, TaskId \\ \hline
%    \end{tabular}
%\end{table}

        Итак, мы избавлись от дублирующей выборки, как следует из Листингов ~\ref{lst:bigq_group1_before} и ~\ref{lst:bigq_group1_after}. Применим эту же оптимизацию еще раз:\\


\begin{lstlisting}[caption={основной запрос до II оптимизации GROUP BY}, label={lst:bigq_group2_before}]
(SELECT GroupId, ModuleId, max(IsStudent) AS IsStudent, max(IsApprover) AS IsApprover
    FROM (
        ...
    ) as a10
    GROUP BY GroupId, ModuleId
) as a12
\end{lstlisting}
%~\ref{lst:}

\begin{lstlisting}[caption={основной запрос после II оптимизации GROUP BY}, label={lst:bigq_group2_after}]
(SELECT GroupId, ModuleId, IsStudent, IsApprover
    FROM WorkRole
        ...
    GROUP BY GroupId, ModuleId
) as a12
\end{lstlisting}
%~\ref{lst:}

%\begin{table}
%    \caption {main2groupby2}
%    \begin{tabular}{|l|}
%    \hline
%    Main query before                                                                                                                                              \\ \hline
%    SELECT ...\\   FROM ( SELECT ... FROM ...\\        JOIN ...\\      WHERE ...\\     UNION SELECT ... FROM...\\      WHERE ...\\     ) as a10\\  GROUP BY GroupId, ModuleId \\   ) as a12 \\ \hline
%    Main query after                                                                                                                                               \\ \hline
%    CREATE INDEX ... ON WorkRole(GroupID, ModuleID)\\ \\SELECT ... FROM WorkRole \\WHERE ...\\ GROUP BY GroupId, ModuleId \\   ) as a12                               \\ \hline
%    \end{tabular}
%\end{table}

        Согласно Листингам ~\ref{lst:bigq_group2_before} и ~\ref{lst:bigq_group2_after} мы сократили количество используемых таблиц, введя дополнительную таблицу {\it WorkRole}, речь о которой подробнее будет немного позднее. Сейчас стоит лишь отметить, что в запросе задействован алгоритм группировки по индексам.

        Оптимизируем теперь и ORDER BY с одним допущением. Поскольку система T-BMSTU на данный момент используется только в МГТУ, обращение к таблице {\it Institutions} можно заменить выборкой из этой таблицы константы:\\


\begin{lstlisting}[caption={основной запрос до оптимизации ORDER BY}, label={lst:bigq_order_before}]
SELECT ... FROM ...
JOIN ... ON ...
...
ORDER BY
    Institutions.InstitutionId ASC, ...
\end{lstlisting}
%~\ref{lst:}

\begin{lstlisting}[caption={основной запрос после оптимизации ORDER BY}, label={lst:bigq_order_after}]
SELECT ... FROM ...
JOIN ... ON ...
JOIN (SELECT institutions.InstitutionID, institutions.InstitutionName FROM ...
    WHERE InstitutionID = 1) AS inst
ORDER BY ...
\end{lstlisting}
%~\ref{lst:}

%\begin{table}
%    \caption {main2orderby1}
%    \begin{tabular}{|l|}
%    \hline
%    Main query before                                                                                                                                                                              \\ \hline
%    SELECT ... FROM ...\\\\...\\JOIN ... ON ...\\\\    Institutions.InstitutionId ASC, \\  ...                                                                                 \\ \hline
%    Main query after                                                                                                                                                                               \\ \hline
%    SELECT ... FROM ...\\JOIN ... ON ...\\JOIN (SELECT institutions.InstitutionID, institutions.InstitutionName  FROM ...\\      WHERE InstitutionID = 1) AS inst\\JOIN ... ON ...\\ORDER BY \\... \\ \hline
%    \end{tabular}
%\end{table}

        Итак, мы сократили количество полей (см Листинги ~\ref{lst:bigq_order_before} и ~\ref{lst:bigq_order_after}), по которым происходит сортировка и теперь в одной из таблиц первичной выборки присутствует константная запись из таблицы, что немного ускоряет выполнение запроса.

        {
                \subsubsection{Оптимизация LIMIT X}
            }

            В некоторых случаях оптимизатор MySQL оптимизирует запрос, который имеет в своем составе LIMIT и не имеет при этом HAVING. Если в качестве лимита указано необльшое значение, MySQL вероятно предпочтет выолнить проход по индексам, в то время, как в обычном случае началось бы сканирование таблицы.

            Если LIMIT используется совместно с ORDER BY, MySQL закончит сортировку, как только наберется достаточное для LIMIT'а количество строк. В случае с DISTINCT MySQL поступит аналогичным образом.\\

            Однако, комбинация ORDER BY вместе с LIMIT 1 может быть оптимизирована. Так, запрос вида \verb|SELECT col FROM table ORDER BY col LIMIT 1| может быть заменен на \verb|SELECT MIN(col) FROM table|. В случае, если столбец проиндексирован, MySQL просто вернет минимальное значение столбца из индекса, в то время, как LIMIT+ORDER BY должны упорядоченно обойти индекс.

            Для начала проверим возможность оптимизации на таком тестовом запросе:\\

\begin{lstlisting}[caption={тестовый запрос до оптимизации LIMIT}, label={lst:test_limit_before}]
SELECT SQL_NO_CACHE LoginTime FROM Sessions
    WHERE PersonID BETWEEN 92 AND 109
    ORDER BY LoginTime DESC
    LIMIT 1;
\end{lstlisting}
%~\ref{lst:}

\begin{lstlisting}[caption={тестовый запрос после оптимизации LIMIT}, label={lst:test_limit_after}]
SELECT SQL_NO_CACHE MAX(LoginTime) FROM Sessions
    WHERE PersonID BETWEEN 92 AND 109;
\end{lstlisting}
%~\ref{lst:}

        Выполним оба тестовых запроса. Сравним результаты выполнения:

\begin{table}[h]
    \caption {Сравнение таймингов запросов}
    \label {test1where}
    \begin{tabular}{|l|c|c|}
    \hline
    Запрос                  & Тайминг клиентской стороны & Тайминг серверной стророны                                                                                                                                                                                       \\ \hline
    До оптимизации     & 0.0780                     & 0.0913                                                                                                                                                                                                           \\ \hline
    После оптимизации  & 0.0470                     & 0.0501                                                                                                                                                                                                           \\ \hline
    \end{tabular}
\end{table}

%
%\begin{table}
%    \caption {test3limit}
%    \begin{tabular}{|l|}
%    \hline
%    Test query before                                                                                                                                                                                                                                                                                        \\ \hline
%    SELECT SQL\_NO\_CACHE LoginTime FROM Sessions\\    WHERE PersonID BETWEEN 92 AND 109\\ ORDER BY LoginTime DESC\\    LIMIT 1;                                                                                                                                                                                \\ \hline
%    Client side timing: 0.0780\\Server side timing: 0.0913                                                                                                                                                                                                                                                   \\ \hline
%    Test query after                                                                                                                                                                                                                                                                                         \\ \hline
%    SELECT SQL\_NO\_CACHE MAX(LoginTime) FROM Sessions\\   WHERE PersonID BETWEEN 92 AND 109;                                                                                                                                                                                                                  \\ \hline
%    Client side timing: 0.0470\\Server side timing: 0.0501                                                                                                                                                                                                                                                   \\ \hline
%    \end{tabular}
%\end{table}

            Эта оптимизация дает незначительные преимущества в случае индексированных столбцов и небольшой выигрыш в случае отсутствия индексов. Оптимизация присутствует на Листингах ~\ref{lst:test_limit_before} и ~\ref{lst:test_limit_after}.

            Применим эту оптимизацию:\\


\begin{lstlisting}[caption={основной запрос до оптимизации LIMIT}, label={lst:bigq_limit_before}]
SELECT Accepted FROM approvements a6
    JOIN submissions
    JOIN relgroupsmodules a4
    WHERE a6.SubmissionId = Submissions.SubmissionId
        AND (a4.ExpireTime IS NULL
        OR Submissions.SubmissionTime < a4.ExpireTime)
    ORDER BY ApprovementTime DESC
    LIMIT 1;
\end{lstlisting}
%~\ref{lst:}

\begin{lstlisting}[caption={основной запрос после оптимизации LIMIT}, label={lst:bigq_limit_after}]
SELECT MAX(Accepted) FROM approvements a6
    JOIN submissions
    JOIN relgroupsmodules a4
    WHERE a6.SubmissionId = Submissions.SubmissionId
        AND (a4.ExpireTime IS NULL
        OR Submissions.SubmissionTime < a4.ExpireTime)
        AND ApprovementTime = (SELECT MAX(ApprovementTime)
                    FROM approvements);
\end{lstlisting}
%~\ref{lst:}


%\begin{table}
%    \caption {main3limi1}
%    \begin{tabular}{|l|}
%    \hline
%    Main query before                                                                                                                                                                                                                                                                                                                   \\ \hline
%    SELECT Accepted \\ FROM approvements a6\\    JOIN submissions\\    JOIN relgroupsmodules a4\\  WHERE a6.SubmissionId = Submissions.SubmissionId \\     AND (a4.ExpireTime IS NULL \\           OR Submissions.SubmissionTime < a4.ExpireTime) \\   ORDER BY ApprovementTime DESC \\    LIMIT 1;                                                      \\ \hline
%    Main query after                                                                                                                                                                                                                                                                                                                    \\ \hline
%    SELECT MAX(Accepted)\\ FROM approvements a6\\    JOIN submissions\\    JOIN relgroupsmodules a4\\    WHERE a6.SubmissionId = Submissions.SubmissionId \\       AND (a4.ExpireTime IS NULL \\           OR Submissions.SubmissionTime < a4.ExpireTime) \\        AND ApprovementTime = (SELECT MAX(ApprovementTime) \\                              FROM approvements); \\ \hline
%    \end{tabular}
%\end{table}

        Доступна еще одна оптимизация в запросе, подобная изложенной на Листингах ~\ref{lst:bigq_limit_before} и ~\ref{lst:bigq_limit_after} . Опустим ее, так как их механики в запросе идентичны с точностью до знаков.

            {
                \subsubsection{Оптимизация UNION и DISTINCT}
            }

        Преобразование UNION в UNION ALL в запросе дает большую выгоду. Первым предположением является то, что это достигается за счет того, что UNION ALL'у не нужна дополнительная таблица для хранения результата, однако это не совсем верно. Обе формы объединения используют временную таблицу для генерации результата.

        Интересен тот факт, что создание этой временной таблицы можно посмотреть с помощью SHOW STATUS. В обычном EXPLAIN'е этой дейстиве по-умолчанию скрыто.

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

        Проверим этот факт, выполнив запрос один раз с  объединением UNION, другой - с объединением UNION ALL, как показано на Листингах ~\ref{lst:test_union_before} и ~\ref{lst:test_union_after}:\\


\begin{lstlisting}[caption={тестовый запрос до оптимизации UNION}, label={lst:test_union_before}]
SELECT DISTINCT personID, groupID, moduleID, taskID, SubmissionTime
    FROM Submissions WHERE PassedTests IS NOT NULL
UNION
SELECT DISTINCT personID, groupID, moduleID, taskID, SubmissionTime
    FROM Submissions WHERE PassedTests IS NULL;
\end{lstlisting}
%~\ref{lst:}

\begin{lstlisting}[caption={тестовый запрос после оптимизации UNION}, label={lst:test_union_after}]
SELECT DISTINCT personID, groupID, moduleID, taskID
    FROM Submissions WHERE PassedTests IS NOT NULL
UNION ALL
SELECT DISTINCT personID, groupID, moduleID, taskID
    FROM Submissions WHERE PassedTests IS NOT NULL;
\end{lstlisting}
%~\ref{lst:}

        Выполним оба тестовых запроса. Сравним результаты выполнения:

\begin{table}[h]
    \caption {Сравнение таймингов запросов}
    \label {test1where}
    \begin{tabular}{|l|c|c|}
    \hline
    Запрос                  & Тайминг клиентской стороны & Тайминг серверной стророны                                                                                                                                                                                       \\ \hline
    До оптимизации     & 0.1400                     & 0.1337                                                                                                                                                                                                           \\ \hline
    После оптимизации  & 0.0780                     & 0.0657                                                                                                                                                                                                           \\ \hline
    \end{tabular}
\end{table}

%\begin{table}
%    \caption {test4union}
%    \begin{tabular}{|l|}
%    \hline
%    Test query before                                                                                                                                                                                                                                                                                        \\ \hline
%    SELECT DISTINCT personID, groupID, moduleID, taskID, SubmissionTime\\  FROM Submissions WHERE PassedTests IS NOT NULL \\UNION \\SELECT DISTINCT personID, groupID, moduleID, taskID, SubmissionTime\\  FROM Submissions WHERE PassedTests IS NULL;                                                         \\ \hline
%    Client side timing: 0.1400\\Server side timing: 0.1337                                                                                                                                                                                                                                                   \\ \hline
%    Test query after                                                                                                                                                                                                                                                                                         \\ \hline
%    SELECT DISTINCT personID, groupID, moduleID, taskID \\ FROM Submissions WHERE PassedTests IS NOT NULL \\UNION ALL\\SELECT DISTINCT personID, groupID, moduleID, taskID \\  FROM Submissions WHERE PassedTests IS NOT NULL;                                                                                \\ \hline
%    Client side timing: 0.0780\\Server side timing: 0.0657                                                                                                                                                                                                                                                   \\ \hline
%    \end{tabular}
%\end{table}

        Основным моментом здесь является то, что в обоих запросах присутствуют ключевые слова DISTINCT. А значит, по схеме выполнения MySQL сначала сделает выборку из одной таблицы, отфильтровав дубликаты, затем поступит по аналогии со второй таблицей. Затем в запросе с обычным UNION, после объединения выборок во временную таблицу, MySQL добавит индексы и вновь отфильтрует результаты, пройдя по таблице. Однако в таблице к тому моменту уже не будет дубликатов и этот проход будет лишним.

        Избавившись от него с помощью использования UNION ALL, мы получим выигрыш в производительности.

        Стоит также заметить, что как и в случае с GROUP BY / ORDER BY, MySQL может использовть лишь левые префиксы индексов для работы с ключами, и в целом DISTINCT иногда рассматривается оптимизатором, как частный случай GROUP BY.

            Выполним описанные выше преобразования, так как аналогичные условия имеются в рассматриваемом нами запросе и запишем новые запросе в Листинги ~\ref{lst:bigq_union_before} и ~\ref{lst:bigq_union_after}:\\


\begin{lstlisting}[caption={основной запрос до оптимизации UNION}, label={lst:bigq_union_before}]
SELECT DISTINCT ... FROM ... AS a8
UNION
SELECT DISTINCT ... FROM ... AS a1
\end{lstlisting}
%~\ref{lst:}

\begin{lstlisting}[caption={основной запрос после оптимизации UNION}, label={lst:bigq_union_after}]
SELECT DISTINCT ... FROM ... AS a7
UNION ALL
SELECT DISTINCT ... FROM ... AS a1
\end{lstlisting}
%~\ref{lst:}


%\begin{table}
%    \caption {main4union1}
%    \begin{tabular}{|l|}
%    \hline
%    Main query before                                                                 \\ \hline
%    SELECT DISTINCT ... FROM ... AS a8 \\UNION \\SELECT DISTINCT ... FROM ... AS a1   \\ \hline
%    Main query after                                                                  \\ \hline
%    SELECT DISTINCT ... FROM ... AS a7\\UNION ALL\\SELECT DISTINCT ... FROM ... AS a1 \\ \hline
%    \end{tabular}
%\end{table}


            {
                \subsubsection{Оптимизация LEFT и RIGHT JOIN}
            }

            MySQL выполняет объединение таблиц, например \verb|A LEFT JOIN B| подобным образом:
            \begin{itemize}
                \item[] Таблица B устанавливается зависимой от A и от всех таблиц, от которых зависит A. Таблица A в свою очередь устанваливается зависимой от всех таблиц, кроме B, которые используются в условии LEFT JOIN
                \item[] Используется условие LEFT JOIN для того, чтобы решить, как выбрать записи из таблицы B
                \item[] Выполняются все стандартные оптимизации входящих внутрь запроса условий
                \item[] В случае, если в таблице B запись, соответствующая условию ON, и для которой в таблице A имеется запись, отсутствует, то в таблицу B дописывается запись со всеми столбцами, равными NULL
                \item[] Новая запись в таблице со всеми параметрами, равными NULL, добавляется в результирующей выборке в соответствие непустой записи из таблицы A
        \end{itemize}

        Реализация RIGHT JOIN аналогична с точностью до порядка таблиц. Оптимизацией JOIN запросов является перестановка таблиц в запросах. Однако LEFT JOIN и STRAIGHT JOIN практически не оптимизируются.

        Еще одна форма объединения - STRAIGHT JOIN. Эта команда не дает оптимизатору выбора, кроме как принять порядок, заданный пользователем, вследствие чего никакие дополнительные преобарзования не производятся и запрос за счет этого ускоряется. Как и в остальных случаях упор делается на наличие индексов. Достигается это улучшение только в том, случае, если известно, что ``навязанный'' оптимзатору порядок соединения однозначно лучше чем тот, который может выбрать он сам. В большинстве случаев ``навязывание'' подобных условий оптимизатору может привести к обратному результату.\\

            Навязвание использования индексов совместно с ``непереставляемым'' LEFT JOIN'ом уже рассматривалось ранее. Чтобы избежать дублирования, опустим этот момент здесь.

            {
                \subsubsection{Оптимизация IS (NOT) NULL}
            }

            MySQL оптимизатор умеет удалять ненужны проверки на наличие /отсутстивие NULL значений. Так, если условие WHERE содержит проверку столбца {\it a} IS NULL при том, что сам столбец объявлен как NOT NULL, проверка будет удалена.

            Также, согласно best practices, не рекомендуется использовать значения типа NULL на столбцах типов DATE, TIME и DATETIME. Убрав поддержку NULL значений и заменив ее сравнением с ``новым отсутствующим'' значением, например стандартной NULL-датой 0000-00-00 00:00:00, обеспечим выолнение best practices в рамках таблицы. Оптимизация представлена на Листингах ~\ref{lst:bigq_null_before} и ~\ref{lst:bigq_null_after}:\\

\begin{lstlisting}[caption={основной запрос до оптимизации IS (NOT) NULL}, label={lst:bigq_null_before}]
(SELECT Accepted
    FROM Approvements as a6
    WHERE a6.SubmissionId = Submissions.SubmissionId
        AND (a4.ExpireTime IS NULL
            OR Submissions.SubmissionTime < a4.ExpireTime)
\end{lstlisting}
%~\ref{lst:}

\begin{lstlisting}[caption={основной запрос после оптимизации IS (NOT) NULL}, label={lst:bigq_null_after}]
(SELECT Accepted
    FROM Approvements as a6
    WHERE a6.SubmissionId = Submissions.SubmissionId
        AND (a4.ExpireTime > '0000-00-00 00:00:00'
            OR Submissions.SubmissionTime < a4.ExpireTime)
\end{lstlisting}
%~\ref{lst:}

%\begin{table}
%    \caption {main6null1}
%    \begin{tabular}{|l|}
%    \hline
%    Main query before                                                                                                                                                                                                                                                            \\ \hline
%    SELECT Accepted \\FROM Approvements as a5\\WHERE a5.SubmissionId = Submissions.SubmissionId \\AND a4.ExpireTime IS NOT NULL AND Submissions.SubmissionTime >= a4.ExpireTime \\ORDER BY ApprovementTime DESC \\LIMIT 1                                                        \\ \hline
%    Main query after                                                                                                                                                                                                                                                             \\ \hline
%    SELECT Accepted                                                                \#7\\               FROM Approvements as a5\\               WHERE a5.SubmissionId = Submissions.SubmissionId \\                 AND a4.ExpireTime > '0000-00-00 00:00:00' \\AND Submissions.SubmissionTime >= pg.ExpireTime \\              ORDER BY ApprovementTime DESC \\                LIMIT 1  \\ \hline
%    \end{tabular}
%\end{table}

        {
                \subsection{MySQL и индексы}
            }

            Лучший способ улучшить производительность операции SELECT это создать индексы на одном или нескольких столбцах, используемых в запросе. Индексы выступают в качетсве указателей на записи, позволяя быстро определить какие записи подходят под условие WHERE и выбрать остальные поля записи.

            Все типы данных в MySQL могут быть проиндексированы. Все индексы в MySQL в рамках движка InnoDB, будь то PRIMARY, UNIQUE и INDEX, сохранены в B-беревьях. Индексные страницы при этом хранятся вместе с данными. MyISAM же использует для этих целей хеш-таблицы.

            И, хотя может возникнуть желание создать индексы по всем возможным столбцам, неиспользуемые и ненужные ндексы занимают место и отнимают у оптимизатора  MySQL время на поиск необходимиого ему оптимального индекса.

            Индексы также увеличивают ``стоимость'' операций вставки, удаления и обновления, так как каждый индекс должен быть обновлен.

            MySQL поддерживает до 16 ключей на одной таблице.

            Стобцы типов BLOB и TEXT поддерживают неполное индексирование. На столбцах типов CHAR и VARCHAR разрешено создавать частичные индексы, которые при этом могут составлять часть многостолбцового индекса.

            Как уже оговаривалось ранее, только крайние левые префиксы индекса могут быть использованы большинством операций. Однако, иногда выборка может быть произведена совсем без обращения к данным. Это происходит в том случае, если выбирается часть индекса по условию другой части индекса. Так, трехстолбцовый индекс на столбцах {\it (a, b, c, d)} дает поисковые преимущества в таких сочетаниях: {\it(a), (a, b), (a, b, c)}. При выборке же можно использовать столбец {\it c} в то время, как условие наложено на столбец {\it a} или {\it b}.\\

            Ранее было отмечено, что данные большинства таблиц в исходной базе данных редактируются нечасто. Поэтому, на них можно без ограничений накладыватьь индексы. В базе присутствуют лишь 4 постоянно используемых таблицы, которые были отмечены ранее. На этих таблицах уже присутствуют индексы помимо PRIMARY и UNIQUE. Эти индексы, действительно, используются оптимизатором и ``утяжелять'' таблицы дополнительными индексами мы не будем.

            Вместо этого добавим несколько индексов, возможное отсутствие некоторых из которых приводило к полму сканированию таблиц согласно первому результату EXPLAIN'а:\\

            \begin{verbatim}
CREATE INDEX InstitutionIDInstitutionNameIndex
             ON Institutions(InstitutionID, InstitutionName);
CREATE INDEX GroupInstitutionTimeNameIndex
             ON Groups (GroupID, InstitutionID, TimeID, GroupName);
CREATE INDEX GroupIndex ON Approvers (GroupID);
CREATE UNIQUE INDEX RelGroupsModulesExpireTimeGroupIDModuleIDUniqueIndex
             ON RelGroupsModules(ExpireTime, GroupID, ModuleID);
        \end{verbatim}


            {
                \subsection{Другие оптимизации}
            }

            {
                \subsubsection{Выбор движка базы данных}
            }

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

            \begin{itemize}
                \item[] MyISAM - не поддерживает транцзакции, но поддерживает полнотекстовый поиск. Внешние ключи недоступны. Данные и индексы хранятся отдельно. Сравнительно невысокая надежность хранения данных
                \item[] Memory (ранее, HEAP) - отличается несравнимо быстрой работой с небольшими таблицами, так как хранит все временные таблицы в оперативной памяти. Практически не имеет конкурентов по скорости работы
                \item[] Federated - федерация серверов, обеспечивающая высокую масштабируемость и высокую отказоустойчивость
                \item[] CSV - хранит таблицы в CSV формате и позволяет редактировать их внешними приложениями. Отличается также невысокой стаблильнотсью работы
                \item[] InnoDB - движок для таблиц ``общего'' назначения, тем не менее поддерживающий большие таблицы. Полная поддержка транзакций (ACID), внешних ключей. Максимальный объем - 64ТБ. По заявлениям разработчиков InnoDB - самый быстрый основанный ``на диске'' движок. Однако, сильно зависит от надлежащей индексации данных
                \item[] Blackhole - движок, созданный для задач репликации.Не умеет самостоятельно хранить данные. Может выстпуть ``мастером'' в схеме репликации master-slave
                \item[] Example - экспериментальный движок для разработчиков. Таблицы, основанные на нем не могут хранить данные и нужны в первую очередь для создания новых типов таблиц.
            \end{itemize}

            Как было замечено ранее, в работе был выбран движок InnoDB по причине поддержки внешних ключей, транзакций и других функций ``из коробки''.


            {
                \subsubsection{Оптимизация некоторых типов данных}
            }

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

            $$C=\frac{\ln row\_count}{\ln {\frac{index\_block\_length \times 2}{3 \times (index\_length + data\_pointer\_length)}}}$$

            Индексный блок обычно составляет 1024 байта, указатель - 4 байта.

            Можем оценить количество дисковых операций для таблицы {\it Submissions}:

            $$C=\frac{\ln 130'000}{\ln {\frac{1'024 \times 2}{3 \times (16 + 4)}}} = \frac{11.775}{3.530} \approx 3$$

            Итого, потребуется в среднем 3 дисковых операции для того, чтобы найти конкретную строку в таблице {\it Submissions}, вмещающей 130'000 записей при наличии на ней индекса длины 16.

            Логарифмическая зависимость объема таблицы позволяет оценить незначительность количества дисковых операций для большинства таблиц базы. Взяв абстрактную таблицу, содержащую, например, 300 записей и имеющую индекс длины 4 на столбце типа INTEGER выясним, что записи из подобных таблиц выбираются за одно обращение. Это еще раз подтверждает возможность наложения дополнительных индексов на подобные таблицы:

            $$C=\frac{\ln 300}{\ln {\frac{1'024 \times 2}{3 \times (4 + 4)}}} \approx 1$$

            И хотя в наше время скорость работы важнее объема затраченной памяти, в MySQL  рекомендуется содержать данные компактно. А значит, следуют и небольшие оптимизации некоторых таблиц базы данных:\\

            \begin{itemize}
                \item[] TINYINT или MEDIUMINT препочтительнее ``обчыного'' типа INT, если это не проиворечит логике работы
                \item[] NULL требует дополнительного места, а значит, ограничения в виде NOT NULL значений немного уменьшат место. Это преимущество в рассамтриваемой базе незначительно ввиду небольшого общего объема данных
                \item[] Вынос логики работы с величинами времени и даты во вне. В базе при этом можно оставить значения типа TIMESTAMP или INT. Эта оптимизация значительнее предыдущих и может дать преимущество в несколько раз.
            \end{itemize}

            {
                \subsubsection{Оптимизация базы данных}
            }

            В ходе рассмторения плана выполнения запроса было выявлено большое количество подзапросов, в том числе  с полным сканированием таблиц. Один из таких запросов, с {\it id=1} отмечен как {\it derived 2}, ссылающийся на подзапрос с {\it id=2}. Тот в свою очередь отмечен, как {\it derived 3}. Подзапрос с {\it id=3} представляет из себя 2 подзапроса - {\it a11} и {\it RelGroupsModules}. После этого выполняется выборка из таблицы {\it a9}. И лишь после этого происходит объединение этих подзапросов в результирующую выборку. Все это сочетается с неопределенностью ключей для всех этих выборок а также постоянным сканированием таблиц.

            Это можно исправить путем создания дополнительной таблицы. Назовем ее WorkRole. В нее перенесем функциональность под разделению ролей пользователей на студентов и принимающую их сторону:\\

\begin{lstlisting}[caption={Скрипт создания таблицы WorkRole}, label={lst:table_workrole}]
CREATE TABLE WorkRole (
    PersonID        INTEGER NOT NULL REFERENCES Persons
                            ON DELETE CASCADE ON UPDATE CASCADE,
    GroupID         INTEGER NOT NULL REFERENCES Groups
                            ON DELETE CASCADE ON UPDATE CASCADE,
    ModuleID        INTEGER NOT NULL REFERENCES Modules
                            ON DELETE CASCADE ON UPDATE CASCADE,

    IsStudent       TINYINT NOT NULL,
    IsApprover      TINYINT NOT NULL,

    PRIMARY KEY (PersonID, GroupID, ModuleID, IsStudent)
);
\end{lstlisting}

            Наличие ключа, состоящего из 4 столбцов объясняется спецификой выборки данных в запросе. Таблица носит  технический характер и создана с целью сбора данных для запроса. При этом необходимо наличие PRIMARY индекса в подобном порядке, чтобы впоследствие использовать его также как и в изначальной версии запроса.

Создадим дополнительные индексы для выборки непосредственно ролей (так как в PRIMARY индексе при отсутствии выборки по префиксу {\it PersonID, GroupID, ModuleID}, исполнитель не сможет оптимально работать со столбцами {\it IsStudent} и {\it IsApprover}:\\

\begin{verbatim}
CREATE INDEX WorkRoleIsStudentIndex ON WorkRole(PersonID, IsStudent);
CREATE INDEX WorkRoleIsApproverIndex ON WorkRole(PersonID, IsApprover);
\end{verbatim}

        Чтобы не повлиять на текущую функциональность базы, все изначально имеющиеся в ней таблице редактировать не будем. Для работы же с этой вновь созданной таблицей создадим необходимые триггеры, которые изменяют данные внутри {\it WorkRole} основываясь на изменении данных в ``базовых'' для нее таблицах {\it Students} и {\it Approvers}.

        Перепишем ту часть запроса, которая некогда выполняла описанные выше действия, изменив порядок выполнения на работу с новой таблицей WorkRole, согласно Листингам ~\ref{lst:bigq_workrole_before} и ~\ref{lst:bigq_workrole_after}:\\

\begin{lstlisting}[caption={основной запрос до внедрения таблицы WorkRole}, label={lst:bigq_workrole_before}]
SELECT GroupId, ModuleId, max(IsStudent) AS IsStudent, max(IsApprover) AS IsApprover
    FROM (
        SELECT a11.GroupId, ModuleId, 1 AS IsStudent, 0 AS IsApprover
            FROM Students as a11
            JOIN RelGroupsModules USING(GroupId)
            WHERE PersonId = 1
        UNION
        SELECT GroupId, ModuleId, 0 AS IsStudent, 1 AS IsApprover
            FROM Approvers as a9
            WHERE PersonId = 1
        ) as a10
    GROUP BY GroupId, ModuleId
\end{lstlisting}
%~\ref{lst:}

\begin{lstlisting}[caption={основной запрос после внедрения таблицы WorkRole}, label={lst:bigq_workrole_after}]
SELECT GroupId, ModuleId, IsStudent, IsApprover
    FROM WorkRole
    WHERE PersonID = 1
    GROUP BY GroupId, ModuleId
\end{lstlisting}
%~\ref{lst:}


%\begin{table}
%    \caption {WorkRole}
%    \begin{tabular}{|l|}
%    \hline
%    Main query before                                                                                                                                                                                                                                                                                                                                                                                                      \\ \hline
%    SELECT GroupId, ModuleId, max(IsStudent) AS IsStudent, max(IsApprover) AS IsApprover \\    FROM ( \\       SELECT a11.GroupId, ModuleId, 1 AS IsStudent, 0 AS IsApprover \\        FROM Students as a11\\      JOIN RelGroupsModules USING(GroupId) \\     WHERE PersonId = 1 \\       UNION SELECT GroupId, ModuleId, 0 AS IsStudent, 1 AS IsApprover \\      FROM Approvers as a9\\      WHERE PersonId = 1 \\       ) as a10\\  GROUP BY GroupId, ModuleId  \\ \hline
%    Main query after                                                                                                                                                                                                                                                                                                                                                                                                       \\ \hline
%    SELECT GroupId, ModuleId, IsStudent, IsApprover\\  FROM WorkRole \\    WHERE PersonID = 1\\    GROUP BY GroupId, ModuleId                                                                                                                                                                                                                                                                                                  \\ \hline
%    \end{tabular}
%\end{table}

        \bigskip

            {
                \section{ТЕСТИРОВАНИЕ}
            }

            {
                \subsection{Сравнение производительности}
            }

            На данный момент имеется оптимизированный по описанным выше пунктам запрос. Некоторые изменения в ходе работы коснулись и самой базы данных. Она также была оптимизирована.

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

        Взглянем на план выполнения нового запроса

        %вставить новый эксплэин
        <здесь новый EXPLAIN>

            Вот что изменилось по сравнению с предыдущим выполнением EXPLAIN'а:
                \begin{itemize}
                    \item[] Остались 2 полнотекстовых сканирования, вместо 6 первоначальных
                    \item[] Убрана неиспользуемая временная выборка, дублирующая подзапрос ({\it id = 4})
                    \item[] Остались лишь 7 подзапросов вместо 10 первоначальных
                    \item[] Перва выборка имеет максимально быстрый (после ({\it type=system}) тип объединения, а длина используемого ключа сокращена
                    \item[] Уменьшено общее количество участвующих в запросе строк
                \end{itemize}

        Согласно результатам EXPLAIN'ов, запрос, действительно, стал работать оптимальнее. В качестве результата представим таблицу профилирования запросов инструментом MySQL Profiler, которая не учитывает время подключения к базе данных, время ожидания открытия и закрытия таблиц, завершения других процессов и т.д., а показывает идеализированное ``чистое'' время выполнения:

\begin{table}[h]
    \caption {test1profiling}
    \begin{tabular}{|c|c|c|}
    \hline
    Тип действия         & Тайминг исходного запроса & Тайминг полученного запроса\\ \hline
     executing          & 0.000001      & 0.000001        \\
    Sending data        & 0.000005      & 0.000005        \\
    executing           & 0.000001      & 0.000001        \\
    Sending data        & 0.000005      & {\bf 0.000016 }       \\
    executing           & 0.000001      & 0.000001        \\
    Sending data        & 0.000005      & 0.000006        \\ \hline
    …                   & …             & …               \\ \hline
    Sending data        & 0.000006      & {\bf 0.000035  }      \\
    executing           & 0.000001      & 0.000002        \\
    Sending data        & {\bf 0.005742}      & 0.000046        \\
    executing           & 0.000003      & 0.000001        \\
    Sending data        & {\bf 0.031268}      & 0.023095        \\
    Creating sort index & {\bf 0.014082}      & 0.013395        \\
    end                 & 0.000011      & 0.000012        \\ \hline
    …                   & …             & …               \\ \hline
    query end           & 0.000013      & 0.000013        \\
    removing tmp table  & 0.000175      & {\bf 0.000201}        \\
    closing tables      & 0.000002      & 0.000004        \\
    removing tmp table  & 0.000004      & 0.000003        \\
    closing tables      & 0.000001      & 0.000005        \\
    freeing items       & 0.000127      & {\bf 0.000139}        \\
    cleaning up         & 0.000017      & 0.000018        \\ \hline
    \end{tabular}
\end{table}

            Опустим бОльшую часть таблицы резульата, оставив только начало и наиболее отличительные моменты. Общее время выполнения первого запроса составляет около 0.06 секунды согласно профайлеру. Время выполнения второго, оптимизированного запроса составляет порядка 0.04 секунды. Как видно из результата, наибольший выигрыш происходит при отправке меньшего количества данных на сортировку - отправка отрабатывает почти на треть быстрее. Одна из введенных нами оптимизаций позволила не отправлять также значительную часть данных, в отличие от первого запроса, благодаря чему мы также получили выигрыш в производительности. Однако, среднее время ``уборки'' после запроса незначительно выросло, как следует из нижней части результата - действий после завершения формирования выборки.
            При сравнении результатов запросов в SQLite и MySQL ситуация аналогичная с точностью до затрат по подключению непосредственно к базам данных (из утилиты основанной на ADO.Net). Это объясняется нивелированием преимуществ одной СУБД над другой за счет оптимизации общей их части - механики выполнения запросов, которая по большей части идентична. Результат закономерен.

            Выполним ``проверку статусов'' SELECT запросом \verb|SESSION STATUS LIKE `Select\%'|:

\begin{table}[h]
    \caption {test2selects}
    \begin{tabular}{|c|c|c|}
    \hline
    Тип призведенного действия         & Исходный запрос & Новый запрос \\ \hline
    Select\_full\_join          & 1      & 0        \\
    Select\_range\_check           & 0      & 0        \\
    Select\_range           & 0      & 0        \\
    Select\_scan        & 6      & 2        \\ \hline
    \end{tabular}
\end{table}

    Эти результаты мы могли наблюдать через EXPLAIN. Общее количество сканирований сократилось.

    Выполним проверку создания временных таблиц \verb|SESSION STATUS LIKE `Created_tmp\%'|:

\begin{table}[h]
    \caption {test3temporaries}
    \begin{tabular}{|c|c|c|}
    \hline
    Тип произведенного действия         & Исходный запрос & Новый запрос \\ \hline
    Created\_tmp\_files          & 4      & 4        \\
    Created\_tmp\_tables          & 12      & 8        \\ \hline
    \end{tabular}
\end{table}

            Из результата этой выборки также видно уменьшение количества временно созданных таблиц с 12 до 8.

            {
                \subsection{Оценка оптимизации}
            }

        Оптимизация, выполненная над базой не включала в себя масштабные изменения. Структура базы практически не затронута. Все изначально существовавшие таблицы сохранены, представления сохранены. Триггеры адаптированы и сохранены. Рефакторинг структуры базы не был произведен ввиду необходимости сохранить ее функционирующее состояние.

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

            Переход с SQLite на MySQL является спорным моментом, так как одним из плюсов СУБД SQLite является ее простота. Большинство преимуществ MySQL над SQLite в ходе данной работы задействованы не были и в целом являются преимуществами в специфических условиях.


            \clearpage

            {
                \section{ЗАКЛЮЧЕНИЕ}
            }

        В ходе работы над курсовым проектом было изучено поведение MySQL при обработке SQL запросов. Протестирована механика многих оптимизаций, которые могут быть применены ко входной базе данных. Большинство этих оптимизаций было осуществлено. Были оценены улучшившиеся показатели работы, были произведены тесты производительности полученной системы.\\

        {
                \subsection{Возможные дальнейшие улучшения}
            }

            Данная работы не может быть названа полностью законченной, так как абсолютно любую систему можно так или иначе улучшить. Вопрос состоит лишь в том, насколько необходимо ``улучшение'', и не приведет ли оно к противоположному результату в другом месте. Так, оптимизация конкретной базы данных в рамках работы шла ``с оглядкой'' на выполнение конкретного моделируемого запроса. \\

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


   \newpage
    <bibtexсписок литературы>

    \end{document}