jjVtPVpu

1\documentclass[12pt]{article}
2% Эта строка — комментарий, она не будет показана в выходном файле
3\usepackage{ucs}
4\usepackage[utf8]{inputenc} % Включаем поддержку UTF8
5\usepackage[russian]{babel}  % Включаем пакет для поддержки русского языка
6\title{Отчёт по численным методам}
7\date{}
8\author{}
9 
10\usepackage{geometry} % А4, примерно 28-31 строк(а) на странице	
11    \geometry{paper=a4paper}
12    \geometry{includehead=false} % Нет верх. колонтитула
13    \geometry{includefoot=true}  % Есть номер страницы
14    \geometry{bindingoffset=0mm} % Переплет    : 0  мм
15    \geometry{top=20mm}          % Поле верхнее: 20 мм
16    \geometry{bottom=25mm}       % Поле нижнее : 25 мм 
17    \geometry{left=25mm}         % Поле левое  : 25 мм
18    \geometry{right=25mm}        % Поле правое : 25 мм
19    \geometry{headsep=10mm}  % От края до верх. колонтитула: 10 мм
20    \geometry{footskip=20mm} % От края до нижн. колонтитула: 20 мм 
21\usepackage{amsmath}    % \bar    (матрицы и проч. ...)
22\usepackage{amsfonts}   % \mathbb (символ для множества действительных чисел и проч. ...)
23\usepackage{mathtools}  % \abs, \norm
24    \DeclarePairedDelimiter\abs{\lvert}{\rvert}
25    \DeclarePairedDelimiter\norm{\lVert}{\rVert}
26\usepackage{listings} %листинги
27
28\lstset{
29  basicstyle=\ttfamily,
30  columns=fullflexible,
31  keepspaces=true,
32  frame=top,frame=bottom,
33}
34
35\usepackage[table,xcdraw]{xcolor}
36
37 %для подсветки листинга javascript
38 \usepackage{color}
39\definecolor{lightgray}{rgb}{.9,.9,.9}
40\definecolor{darkgray}{rgb}{.4,.4,.4}
41\definecolor{purple}{rgb}{0.65, 0.12, 0.82}
42
43\lstdefinelanguage{JavaScript}{
44  keywords={typeof, new, true, false, catch, function, return, null, catch, switch, var, if, in, while, do, else, case, break},
45  keywordstyle=\color{blue}\bfseries,
46  ndkeywords={class, export, boolean, throw, implements, import, this},
47  ndkeywordstyle=\color{darkgray}\bfseries,
48  identifierstyle=\color{black},
49  sensitive=false,
50  comment=[l]{//},
51  morecomment=[s]{/*}{*/},
52  commentstyle=\color{purple}\ttfamily,
53  stringstyle=\color{red}\ttfamily,
54  morestring=[b]',
55  morestring=[b]"
56}
57
58\lstset{
59   language=JavaScript,
60   %backgroundcolor=\color{lightgray},
61   extendedchars=true,
62   basicstyle=\footnotesize\ttfamily,
63   showstringspaces=false,
64   showspaces=false,
65   %numbers=left,
66   %numberstyle=\footnotesize,
67   %numbersep=9pt,
68   %tabsize=2,
69   breaklines=true,
70   showtabs=false,
71   captionpos=b
72}
73
74
75\begin{document}
76    \newpage
77    {
78        \thispagestyle{empty}
79        \centering
80        
81        \textbf{
82        МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ Н. Э. БАУМАНА \\
83        Факультет информатики и систем управления \\
84        Кафедра теоретической информатики и компьютерных технологий}
85        \bigskip
86        \bigskip
87        \bigskip
88        \bigskip
89        \bigskip
90        \bigskip
91        \bigskip
92
93        \vfill
94
95        {\large Лабораторная работа №3}\\
96        по курсу <<Численные методы>>\\
97	\LARGE{<<Построение для таблично-заданной функции \\
98			кубического сплайна,\\ 
99			сплайна Акимы, \\
100			Б-сплайна>>\\ }
101	\normalsize
102
103        \bigskip
104        \vfill
105        \hfill\parbox{5cm} {
106            Выполнил:\\
107
108            Проверила:\\
109
110        }
111        \vspace{\fill}
112
113        
114        Москва \number\year
115        \clearpage
116    }
117	\newpage
118	{
119		\tableofcontents
120		\clearpage
121	}
122	
123	
124	
125	
126    {
127        \section{ВВЕДЕНИЕ}
128    }
129	
130	Основная цель данной работы - конвертировать базу данных автоматизированной системы тестирования T-BMSTU, используемой на кафедре ИУ9 для проведения лабортаторных работ по курсам программирования, в формат MySQL. Сравнить производительность новой реализации базы и, при необходимости, оптимизировать запрос к базе, либо оптимизировать имеющуюся базу данных в новом формате. \\
131	
132	В ходе работы будет исследована имеющаяся исходная реализация базы в формате SQLite. Затем, данные из исходной базы будут извлечены и перенесены в новую, целевую базу данных с помощью конвертера. Затем в новый формат будет конвертирован модельный SQL запрос и будет исследовано его выполнение на новой базе данных. Этот запрос будет оптимизирован под целевую реализацию базы данных. \\
133	
134	Путем сравнения производительности реализаций ``новой'' и ``старой'' баз данных и запросов будет принято решение о целесообразности перехода на новую реализацию.
135	
136    \clearpage
137    
138    
139    
140    	{
141        	\section{НЕОБХОДИМЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ}
142    	}
143    
144    	Прежде всего стоит рассмтореть отличительные черты исходной и целевой СУБД. После этого мы сможем заключить, возможна ли в теории выгода от прехода от одной СУБД к другой.\\
145    
146    
147    	{
148    		\subsection{SQLite. Преимущества и недостатки}
149    	}
150    
151	SQLite является популярной встраиваемой реляционной базой данных. Релиз последней на данный момент версии одноименной СУБД (SQLite 3.14.1) состоялся в августе 2016 года. СУБД выпускается под общественной (public domain) лицензией, не накладывающей никаких ограничений на использование. 
152	
153	Рассторим теперь особенности базы данных:\\
154	
155	
156	Главным отличием SQLite от других баз данных является парадигма, в которой создана база. В отличие от большинста остальных баз данных, использующих клиент-серверную архитектуру, само приложение SQLite по сути является сервером. SQLite не является отдельным процессом. Вместо этого она предоставляет библиотеку для создания `подключений` к единственному файлу, в виде которого она находится в конечной системе.
157    
158    	Относительная простота реализации такого подхода является, пожалуй, главной отличительной чертой этой СУБД. Вся база хранится в одном файле. Это позволяет существенно экономить ресурсы системы, сокращает время отклика и существенно упрощает логику работы программ, использующих эту БД. База данных является единственным файлом в кросплатформенном формате, что обеспечивает бОльшую мобильность по сравнению с другими СУБД, так как для работы с БД в новой системе, развертывание базы не треубется. \\
159    	
160
161	Однако, у такой реализации есть и обратная сторона. Простота реализации достигается за счет того, что во время записи весь файл блокируется одним процессом. А значит, несколько процессов, одновременно подключенных к базе могут лишь считывать данные, в то время, как только один из них может изменять эти данные. Этот принцип, ``читают многие - пишет один'', является одним из недостатков этой СУБД. \\
162	
163	Еще одним недостатком является отсутствие полной поддержки SQL-92:
164	\begin{itemize}
165		\item[] Не поддерживается, например, удаление или изменение столбца в таблице: 
166			\begin{itemize}
167			\item[] \verb| ALTER TABLE DROP COLUMN ... |
168			\item[] \verb| ALTER TABLE ALTER COLUMN ... | отсутствуют в SQLite
169			\end{itemize}
170		\item[] Опущены \verb| RIGHT OUTER JOIN | и \verb| FOR EACH STATEMENT |
171		\item[] По умолчанию отключена поддержка foreign key
172		\item[] Недоступны хранимые процедуры
173		\item[] Триггеры SQLite намного менее функциональны, нежели триггеры других СУБД
174	\end{itemize}
175		
176	Для взаимодйствия с SQLite из приложений отсутствуют официальные драйвера. Таковых нет ни под JDBC, ни под ADO.Net, ни под ODBC. Отстутствие этого ``из коробки'' яляется существенным минусом SQLite.\\
177	
178		
179	Еще одной особенностью SQLite является ``слабая типизация'', или концепция ``близости типов'' (type affinity). Так, тип столбца не определяет тип хранимого в этом столбце значения. В любой столбец может быть записано любое значение, а сам тип столбца используется для приведения значений к одному типу при сравнении значений. Все это позволяет создавать таблицу ``простым''  \verb| CREATE TABLE sampleTable| \verb|(col1, col2, col3) | без указания чего либо еще, что является недопустимым и недоступным в других СУБД.
180	
181	Однако, в SQLite доступны лишь 5 типов данных: 
182	\begin{itemize}
183		\item[] NULL
184		\item[] INTEGER (знаковое целое число до 8 байт)
185		\item[] REAL (число с плавающей точкой, 8 байт в формате IEEE)
186		\item[] TEXT (строка в кодировке UTF-8 или UTF-16)
187		\item[] BLOB (входное значение, `как есть`)
188	\end{itemize}
189		
190		Согласно руководству, для хранения типа Boolean рекомендуется использовать INTEGER 0 или 1, а Date и Time типы хранить в виде строк. Вышесказанное является одновременно как недостатком, так и достоинством и не может быть однозначно интерпретировано в рамках `общих` задачах. \\
191		
192		
193	В SQLite также отсутствуют какие-либо механизмы репликации.
194	
195	Отсутствует система пользователей.
196	
197	Отсутствует возможность увеличения производительности.\\ 
198	
199	Несмторя на все это, SQLite является отличным кандидатом на использование в качестве встраиваемой системы и пользуется большой популярностью в этой сфере. 
200    	
201    	
202    	{
203    		\subsection{MySQL. Преимущества и недостатки}
204    	}
205    	
206    	Теперь взглянем на целевую базу данных, MySQL.
207    	
208    	MySQL является самой распространенной СУБД. Разрабатывается корпорацией Oracle, как доступная под универсальной общественной лицензией GNU (GNU General Public License) замена промышленной БД Oracle. 
209    	
210    	Рассмотрим особенности MySQL:\\
211    	
212    	
213    	MySQL разработана в соответствии с ``классической'' клиент-серверной архитектурой и поддерживает все основные ОС. Для работы с базой из приложений имеются официальные драйвера ADO.Net, JDBC и ODBC. Хотя количество языков, поддерживаемых API MySQL и меньше, чем у SQLite, недостатком это не является, так как упущены не самые популярные в настоящее время языки, такие, как Basic, Forth и Fortran.\\
214    	
215    
216    	MySQL поддерживает большое количество типов данных:
217    		\begin{itemize}
218    		\item[] TINYINT (BOOL), SMALLINT, MEDIUMINT, INTEGER, BIGINT для целочисленных значений
219	    	\item[] FLOAT, DOUBLE, NUMERIC, REAL для значений с плавающей точкой
220    		\item[] DATE, TIME, DATETIME, YEAR, TIMESTAMP для значений даты и времени
221    		\item[] CHAR, VARCHAR для строковых значений фиксированной / переменной длины
222		\item[] TINYTEXT, TEXT, MEDIUMTEXT, LONGTEXT для тектовых значений длины $2^{8}-1$ / $2^{16}-1$ / $2^{24}-1$ / $2^{32}-1$ соответственно
223    		\item[] TINYBLOB, BLOB, MEDIUMBLOB, LONGBLOB для значений `как есть`
224    		\item[] ENUM, SET для занчений типа перечисление / множество
225    		\end{itemize}
226    		
227	Это является существенным преимуществом MySQL перед SQLite, так как таблицы могут быть построены более оптимально в соответствии с бизнес логикой.\\
228	
229	
230	Поддерживается почти полный стандарт SQL-92 (DML, DDL, DCL), хотя и присутствует проприетарное расширение синтаксиса. В частности, в этой БД используется свой синтаксис для написания триггеров, а также хранимых процедур, что не поддерживаются в SQLite. Однако, стоит отметить, что в MySQL упущены, в частности, INSTEAD OF триггеры, хотя они и могут быть самостоятельно реализованы отдельно.\\
231	
232	
233	В Mysql присутствуют механизмы репликации, так как разработчики создавали функциональность по заказу лицензионных пользователей и это (репликация) является важным фактором при выборе БД для коммерческого использования. Так, поддерживается
234		\begin{itemize}
235			\item[] Многомастерная (Multi-master replication) репликация. Данные в данном случае хранятся группой устройств и могут быть изменены любым устройством из этой группы `мастеров`, так и 
236			\item[] Система с ведущими и ведомыми устройствами (Master-slave), где ведущая база данных рассматривается, как `авторитетный` источник данных, а подчиненные синхронизируются с ней.
237		\end{itemize}
238		
239	Все это существенно повышает надежность работы этой БД и отличает ее от SQLite, где механизмы репликации впринципе отсутствуют.\\
240	
241	
242	Mysql поддерживает многопоточную работу с помощью механизма блокировки таблиц или строк, что является более вариативной функциональностью, нежели захват всего файла базой SQLite.
243	
244	Присутствуют мехнизмы управления уровнем доступа пользователей, хотя отсутствуют механизмы деления пользователей на роли и группы.
245	
246	Система Mysql масштабируема.
247	
248	Также, среди преимуществ можно отметить наличие множества ``движков'' (database engine), каждый из которых обладает своими преимуществами и может быть выбран согласно решаемой задаче. В ходе работы некоторые из движков будут рассмторены чуть подробнее.
249	
250	Благодаря свободному доступу к исходному коду, эта СУБД может быть подстроена под индивидуальное решение. А вывсокая популярность системы обеспечивает наличие поддержки по многим возможным проблемам.\\
251	
252	
253	Исходя из всего вышеперечисленного, переход с SQLite на MySQL видится разумным в рамках большей части задач общего назначения. MySQL объективно обладает большим числом преимуществ перед SQLite. 
254	
255	Однако, в рамках курсовой работы рассматривается конкретная база данных автоматизированной системы тестирования T-BMSTU. И для оценки реальной выгоды от перехода с одной базы на другую необходимо прежде всего оценить уместность преимуществ MySQL перед SQLite в рамках конкретной задачи. 
256	
257	Для этого рассмторим теперь исходную базу данных T-BMSTU.
258	
259	\bigskip
260	
261	
262	{
263		\section{ИЗУЧЕНИЕ ВХОДНЫХ ДАННЫХ}
264	}
265	
266	Исходными данными курсовой работы являются SQL скрипт создания базы данных, непосредственно база данных в виде файла {\it tbmstu.db} и запрос, формирующий выборку данных из базы для отображения на Web-сервере тестирования.\\
267	
268	{
269		\subsection{Исходная база данных T-BMSTU}
270	}
271	Взглянем на схему базы данных
272	
273	<здесь будет схема базы>
274	%тут картинка схемы большая будет и вертикальная мб даже
275	
276	Исходная база данных содержит в себе 22 таблицы:
277	\begin{verbatim}
278        Institutions
279        Subjects
280        Modules
281        Groups
282        RelGroupsModules
283        Persons
284        Sessions
285        CurrentAdmins
286        CurrentTaskAuthors
287        Students
288        ModuleAuthors
289        Approvers
290        Languages
291        Tasks
292        RelTasksLanguages
293        RelLanguagesModules
294        Submissions
295        FailedTests
296        Comments
297        Approvements
298        RelTasksModules
299	\end{verbatim}
300		
301		%отсортировать в порядке создания как по скрипту
302
303	Также имеются 6 представлений:
304	\begin{verbatim}
305        TimeDesc
306        RelModulesInstitutions
307        RelSubmissionsApprovers
308        FinalApprovements
309        PersonRoles
310        RelStudentsTasks
311	\end{verbatim}
312	
313	Присутствуют 7 триггеров, выводящих сообщение об ошибке, в случае нарушений работы с внешники ключами (вставки и обновления):
314	\begin{verbatim}
315        fki_RelGroupsModules
316        fku_RelGroupsModules
317        fki_Tasks_PersonId
318        fku_Tasks_PersonId
319        fki_Approvements_PersonId
320        fku_Approvements_PersonId
321        fku_Submissions_PassedTests
322	\end{verbatim}
323	
324	Назначение таблиц, представлений и триггеров понятно из их названий.
325	
326	В большинстве таблиц в базе хранится по несколько десятков записей - это таблицы со списками студентов групп, предметов и модулей, таблица-временная шкала, таблица авторов заданий. Есть таблицы на одну или несколько сотен записей: аккаунты в системе, задания, проверяющие и вспомогательные таблицы. Есть таблица университетов с одной записью, так как на данный момент система применятеся только в МГТУ. И есть 4 таблицы с десятками тысяч записей. В порядке убывания по количеству записей (по данным на февраль 2016):
327	
328	\begin{itemize}
329		\item[] Sessions, ~ 130 тыс. записей
330		\item[] Submissions, ~ 80 тыс. записей
331		\item[] Comments, ~ 70 тыс. записей
332		\item[] Approvements, ~70 тыс. записей.
333	\end{itemize}
334	
335	Очевидно, что работа с этими таблицами представляет наибольшую сложность не только по причине частой записи в них, но и по причине того, что эти таблицы имеют дочерние записи и ссылаются на большое число других таблиц. Рассмотрим, например таблицу (скрипт создания) решений, отправленных на сервер тестирования - таблицу {\it Submissions}:\\
336		
337
338\begin{lstlisting}[caption={Скрипт создания таблицы Submissions}, label={lst:table_submissions}]
339CREATE TABLE Submissions (
340    SubmissionID    INTEGER NOT NULL PRIMARY KEY,
341 
342    PersonID    INTEGER NOT NULL,
343    GroupID     INTEGER NOT NULL,
344    TaskID      INTEGER NOT NULL,
345    ModuleID    INTEGER NOT NULL,
346    SubmissionTime  TEXT NOT NULL CHECK (length(SubmissionTime) < 32),
347 
348    LanguageID  INTEGER NOT NULL,
349    SourceCode  TEXT NOT NULL CHECK (length(SourceCode) < 50*1024),
350    Draft       INTEGER CHECK (Draft = 0 OR Draft = 1),
351 
352    SentToTestTime  TEXT,
353    PassedTests INTEGER,
354    TestingServerId INTEGER,
355 
356    UNIQUE (PersonID, GroupID, TaskID, ModuleID, SubmissionTime),
357    FOREIGN KEY (PersonID, GroupID) REFERENCES Students
358                                    ON DELETE CASCADE ON UPDATE CASCADE,
359    FOREIGN KEY (TaskID, ModuleID)  REFERENCES RelTasksModules
360                                    ON DELETE RESTRICT ON UPDATE CASCADE,
361    FOREIGN KEY (GroupID, ModuleID) REFERENCES RelGroupsModules
362                                    ON DELETE RESTRICT ON UPDATE CASCADE,
363    FOREIGN KEY (TaskID, LanguageID) REFERENCES RelTasksLanguages
364                                    ON DELETE RESTRICT ON UPDATE CASCADE,
365    FOREIGN KEY (LanguageID, ModuleID) REFERENCES RelLanguagesModules
366                                    ON DELETE RESTRICT ON UPDATE CASCADE
367);
368		\end{lstlisting}
369		
370
371	Как видно из листинга ~\ref{lst:table_submissions}, эта таблица ссылается сразу на 5 других таблиц. А значит, при добавлении записи в нее необходимо обратиться сразу к 5 таблицам. Также с этой таблицей работает триггер {\it fku\_Submissions\_PassedTests}, проверяющий наличие валидного сервера тестирования, назначенного по решению.
372	
373	Тут же становятся видны ограничения, озвученные ранее при анализе SQLite ``из коробки'', такие, как ограниченное число типов данных: {\it SubmissionTime} хранится в виде строки TEXT, {\it Dratf} хранится в виде INTEGER'а. Из-за этого приходится осуществлять валидацию входных данных проверяя длину или значние.
374	
375	Также необходимо соблюдение уникальности группы полей {\it PersonID, GroupID, TaskID, ModuleID, SubmissionTime} и PRIMARY KEY.
376	
377	Работа с этой таблицей весьма труднозатратна относительно работы с остальными таблицами в рамках базы данных.
378	
379	У этой таблицы имеются сразу 4 вручную созданных индекса. Учтем это в дальнейшем при возможной оптимизации этой таблицы. \\
380	
381	Таблиц, подобных этой, в базе еще 3. Нужно отметить, что таблица {\it Sessions} выделяется среди ``крупных таблиц'' своими размерами, а также относительной простотой работы: в ней есть только валидация ip-адреса по длине и ссылка на таблицу пользователей сервера для прикрепления его к сеансу. Поиск по этой таблице не нужен, поэтому есть только стандартный PRIMARY KEY
382	
383	Эти 4 таблицы постоянно используются в ходе работы сервера. Данные в них обновляются постоянно.
384	
385	Большинство данных остальных таблиц редактируется либо с началом модуля (например, таблицы {\it Modules, Tasks}), либо семестра (такие, как {\it Subjects, Groups, TimeScale}), либо с началом учебного года ({\it Persons, Groups, TimeScale}). Таблицы {\it Languages, CurrentAdmins, CurrentTaskAuthors, Institutions} редактируются еще реже. То есть, данные большей части таблиц редактируются совсем не часто. Но, бОльшая часть данных всей базы редактируется постоянно. Учтем это в дальнейшем.\\
386	
387	{
388		\subsection{Исходный запрос к базе}
389	}
390	
391	Во входных данных также присутствует запрос к описанной выше базе. Этот запрос формирует выборку данных для отображения на странце Web-сервера. 
392	Взглянем на запрос в его первоначальном варианте:\\
393		
394		%шрифт листинга поменьше бы чтоб хотя ы на 2 страницы
395		
396		\begin{lstlisting}[caption={Скрипт выборки из базы}, label={lst:bigq}]
397SELECT DISTINCT
398    Institutions.InstitutionId, Institutions.InstitutionName,
399        /*****/
400    Groups.GroupId, Groups.TimeId, TimeDesc.TimeName, Groups.GroupName,
401        /*****/
402    Subjects.SubjectId, Subjects.SubjectName,
403        /*****/
404    Modules.ModuleId, Modules.ModuleNo, Modules.ModuleName, Modules.MinRating, 
405    RelGroupsModules.ExpireTime, IsStudent, IsApprover,
406        /*****/
407    StTaskId, StTaskNo, StTaskName, StTaskRating, Status,
408        /*****/
409    SubmissionId, SubmPersonId, SubmLogin, SubmFirstName, 
410    SubmLastName, SubmTaskId, SubmTaskName, SubmissionTime
411FROM (
412    SELECT GroupId, ModuleId, max(IsStudent) AS IsStudent, 
413                              max(IsApprover) AS IsApprover
414    FROM (
415        SELECT Students.GroupId, ModuleId, 1 AS IsStudent, 0 AS IsApprover
416        FROM Students
417        JOIN RelGroupsModules USING(GroupId)
418        WHERE PersonId = 1
419        UNION SELECT GroupId, ModuleId, 0 AS IsStudent, 1 AS IsApprover
420        FROM Approvers
421        WHERE PersonId = 1
422        )
423    GROUP BY GroupId, ModuleId
424    )
425JOIN RelGroupsModules USING(GroupId, ModuleId)
426JOIN Groups USING(GroupId)
427JOIN Institutions USING(InstitutionId)
428JOIN TimeDesc USING(TimeId)
429JOIN Modules USING(ModuleId)
430JOIN Subjects USING(SubjectId)
431LEFT OUTER JOIN (
432    SELECT * FROM (
433        SELECT DISTINCT GroupId, ModuleId,
434            TaskId AS StTaskId, TaskNo AS StTaskNo, TaskName AS StTaskName,
435            TaskRating AS StTaskRating,
436            (CASE
437                WHEN count(SubmissionId) = 0 THEN 0
438                WHEN max(AcceptedInTime) = 1 THEN 3
439                WHEN max(AcceptedOutdated) = 1 THEN 4
440                WHEN count(SubmissionId) > count(AcceptedInTime)+
441                                           count(AcceptedOutdated) THEN 1
442                ELSE 2
443            END) AS Status,
444            NULL AS SubmissionId, NULL AS SubmPersonId,
445            NULL AS SubmLogin, NULL AS SubmFirstName,
446            NULL AS SubmLastName, NULL AS SubmTaskId,
447            NULL AS SubmTaskName, NULL AS SubmissionTime
448        FROM (
449            SELECT DISTINCT Students.PersonId,
450                RelGroupsModules.GroupId, RelGroupsModules.ModuleId,
451                RelTasksModules.TaskId, RelTasksModules.TaskNo, Tasks.TaskName,
452                RelTasksModules.TaskRating, Submissions.SubmissionId,
453                (SELECT Accepted
454                FROM Approvements
455                WHERE Approvements.SubmissionId = Submissions.SubmissionId
456                    AND (RelGroupsModules.ExpireTime IS NULL 
457                    OR Submissions.SubmissionTime < RelGroupsModules.ExpireTime)
458                ORDER BY ApprovementTime DESC
459                LIMIT 1
460                ) AS AcceptedInTime,
461                (SELECT Accepted
462                FROM Approvements
463                WHERE Approvements.SubmissionId = Submissions.SubmissionId
464                    AND RelGroupsModules.ExpireTime IS NOT NULL 
465                    AND Submissions.SubmissionTime >= RelGroupsModules.ExpireTime
466                ORDER BY ApprovementTime DESC
467                LIMIT 1
468                ) AS AcceptedOutdated
469            FROM Students, RelGroupsModules
470            LEFT OUTER JOIN RelTasksModules USING(ModuleId)
471            LEFT OUTER JOIN Tasks USING(TaskId)
472            LEFT OUTER JOIN Submissions
473                ON Submissions.PersonId = 1
474                AND Submissions.GroupId = RelGroupsModules.GroupId
475                AND Submissions.TaskId = RelTasksModules.TaskId
476                AND Submissions.ModuleId = RelGroupsModules.ModuleId
477                AND (Submissions.Draft IS NULL OR Submissions.Draft = 0)
478            WHERE Students.PersonId = 1 AND
479                Students.GroupId = RelGroupsModules.GroupId
480            )
481        GROUP BY GroupId, ModuleId, TaskId
482        )
483    UNION SELECT DISTINCT Approvers.GroupId, Approvers.ModuleId,
484        NULL AS StTaskId, NULL AS StTaskNo, NULL AS StTaskName,
485        NULL AS StTaskRating, 0 AS Status,
486        Submissions.SubmissionId, Submissions.PersonId AS SubmPersonId,
487        Persons.Login AS SubmLogin, Persons.FirstName AS SubmFirstName,
488        Persons.LastName AS SubmLastName, Tasks.TaskId AS SubmTaskId,
489        Tasks.TaskName AS SubmTaskName, Submissions.SubmissionTime
490    FROM Approvers
491    LEFT OUTER JOIN Submissions
492        ON Submissions.GroupId = Approvers.GroupId
493        AND Submissions.ModuleId = Approvers.ModuleId
494        AND Draft = 0
495        AND NOT EXISTS (
496            SELECT * FROM Approvements
497            WHERE Approvements.SubmissionId = Submissions.SubmissionId
498        )
499    LEFT OUTER JOIN Tasks
500        ON Tasks.TaskId = Submissions.TaskId
501    LEFT OUTER JOIN Persons
502        ON Persons.PersonId = Submissions.PersonId
503    WHERE Approvers.PersonId = 1
504    ) AS Cont
505    ON Cont.GroupId = Groups.GroupId
506    AND Cont.ModuleId = Modules.ModuleId
507ORDER BY
508    Institutions.InstitutionId ASC,
509    Groups.TimeId DESC,
510    Groups.GroupId ASC,
511    SubjectId ASC,
512    ModuleNo ASC,
513    StTaskNo ASC,
514    SubmissionTime ASC;
515		\end{lstlisting}
516		
517		В запросе из Листинга ~\ref{lst:bigq} присутствуют 11 выборок с помощью SELECT из большей части таблиц базы. В том числе есть обращения к ``большим'' таблицам - {\it Submissions} и {\it Approvements}. Присутствует множество объединений таблиц, несколько группировок по учебным модулям и группам а также с использованием агрегирующих функций, несколько DISTINCT выборок и сортировок.
518		
519		Выполнять оптимизации согласно заданию, будем ``с оглядкой'' на этот запрос.\\
520		
521		
522		\clearpage
523		
524		{
525	    		\section{ПОРТИРОВАНИЕ БАЗЫ ДАННЫХ}
526    		}
527		
528		Теперь, когда мы получили представление об устройсве исходной базы данных SQLite, потрируем ее на целевую платформу MySQL. 
529		
530		Стандартные реверс-инжиниринговые утилиты для портирования могут некорректно взаимодействовать со схемой базы данных и в результате некоторые таблицы могут не создаться, а внутреннее устройство других будет отличаться. К тому же нам необходимо произвести некоторые изменения типов согласно best practices, описанных в руководстве пользователя MySQL. %здесь ссыль
531		
532		В случае данной курсовой работы, у нас имеется преимущество перед такими утилитами в виде еще одного входного скрипта - скрипта создания базы. Все что необходимо сделать в данном случае - перенести непосредственно данные в подготовленную на новом месте схему.\\
533		
534		
535		Так как обе СУБД не полностью поддерживают формат SQL-92, простым запуском скрипта создания базы обойтись не удастся. Преобразуем исходный скрипт с учетом отличий диалекта SQL, используемого в SQLite от диалекта, используемого в MySQL. Также выполним преобразования типов данных, заменив строки, содержащие даты и время на тип DATETIME. Другие строковые константы заменим на тип VARCHAR, более предпочтительный в рамках MySQL. Своеобразный Boolean в SQLite, реализованый через INTEGER и проверку значений с помощью CHECK() заменим на TINYINT, являющийся, аналогом BOOLEAN'а в MySQL. Проведем еще некоторые преобразования и портируем триггеры, переведя их на проприетарный синткасис триггеров и хранимых прцедур MySQL.\\
536		
537		
538		Считаем, что схема базы данных уже подготовлена. Напишем небольшую утилиту на $C\#$, которая с помощью технологии ADO.Net доступа приложений на платформе .Net к данным выберет все данные из базы SQLite и вставит в подготовленную схему базы MySQL. Единственной возможной проблемой является отсутствие официальных драйверов SQLite для ADO.Net, однако это решается загрузкой аналога  через встроенный менеджер пакетов NuGet. Запускаем утилиту и получаем на выходе наполненную базу данных MySQL с описанными выше изменениями. Триггеры необходимо добавить вручную.
539		
540		Поскольку никаких других существенных изменений сделано не было, схема базы данных и внутреннее устройство таблиц с точностью до типов некоторых столбцов остались без изменений и повторно приводить их не имеет смысла. Портирование на этом завершено. Считаем, что имеется полный MySQL аналог исходной SQLite базы.\\
541		
542		
543		{
544	    		\section{MYSQL ОПТИМИЗАЦИИ}
545    		}
546    		
547    		На данный момент имеется база данных MySQL. Можно считать, что все дальнейшие операции, если не оговорено иное, происходят над ней. 
548    		
549    		Запрос, рассмотренный ранее в Листинге ~\ref{lst:bigq} не сработает в своем исходном виде на новой базе из-за отличия используемых диалектов. В MySQL у каждой выборки должен быть свой алиас (alias, псевдоним). Проименуем все таблицы в запросе, добавив к ним соответствующие технические наименования. 
550    		
551    		Теперь мы можем выполнить запрос на новой базе. Выполняем и фиксируем результат запроса, чтобы при дальнейшем его изменении их можно было сравнить и проверить, выдают они одинаковую выборку или нет.\\
552    		
553    		Перейдем теперь к главной части этой работы - исследованию и оптимизации запроса и/или базы.\\
554    		
555    		    		
556    		{
557	    		\subsection{Исследование выполнения запроса на базе MySQL}
558    		}
559    		
560    		Как уже отмечалось ранее, у MySQL имеются некоторые преимущества перед SQLite. Среди них - наличие команды EXPLAIN. При выполненеии любого запроса, оптимизатор запросов MySQL создает наиболее оптимальный план его выполнения. Этот план можно посмтореть с помощью команды EXPLAIN. Эта команда является одним из самых мощных инструментов разработчика, доступных в MySQL. \\
561    		
562    		Выполним эту команду вместе с запросом из Листинга ~\ref{lst:bigq}:
563    		%здесь результат
564    		
565    		<здесь результат первого EXPLAINа>
566    		%ссылка на рез-т эксплэина
567    		
568    		Взглянем на результат выполнения запроса в таблице <ссылка на рез-т explain'а>. 
569    		Результат выполнения состоит из 11 столбцов:
570    		\begin{itemize}
571    			\item[] Id - порядковый номер SELECT'а внутри запроса
572    			\item[] Select\_type - тип запроса SELECT. Среди возможных значений:
573    			\begin{itemize}
574    				\item[] PRIMARY - самый внешний запрос в JOIN'е
575    				\item[] DERIVED - данный запрос является подзапросом
576    				\item[] SUBQUERY - первый SELECT в подзапросе
577    				\item[] UNION - второй или последующий SELECT в UNION'е
578    				\item[] UNION RESULT - результат UNION'а
579			\end{itemize}
580			\item[] Table - таблица, к которой относится строка результата
581			\item[] Type - тип связыания таблиц. Среди возможных значений:
582			\begin{itemize}
583    				\item[] Const - таблица имеет только одну соответствующую строку, которая проиндексирована. Таблица в данном случае читается лишь раз и в дальнейшем значение строки воспринимается, как константа. Это наиболее быстрый тип свзяывания
584    				\item[] Eq\_ref - все части PRIMARY KEY или UNIQUE NOT NULL индекса используются для связывания. Еще один наилучший тип связывания
585    				\item[] Ref - прямая ссылка. Все строки индексного столбца противопоставляются строкам предыдущей таблицы. Неплохой вариант
586    				\item[] Index - сканирование всего индексного дерева для поиска строк
587    				\item[] All - худший тип связи. Для нахождения строк используется полнотекстовое сканирование таблицы. Указывает на отсутствие подходящих индексов в таблице
588			\end{itemize}			
589			\item[] Possible\_keys - возможные индексы. Возможно, они не используются. Значение NULL указывает на отсутствие подходящих индексов в таблице.
590			\item[] Key - фактически использованный ключ. Может отличаться от указанных в {\it Possible\_keys} значений
591			\item[] Key\_len - длина используемого ключа
592			\item[] Ref - столбцы или константы, которые сравниваются с индексом
593			\item[] Rows - число обработанных записей
594			\item[] Filtered - процент отфильтрованных записей
595			\item[] Extra - дополнительная информация об обработке запроса. Среди возможных значений:
596			\begin{itemize}
597    				\item[] Using index - информация получена с применением индексного дерева без доп. поиска для чтения строки. Возможно при всех проиндексированных столбцах.
598    				\item[] Using temporary - создане временной таблицы. Например, при ORDER BY на наборе стобцов, отличном от набора в GROUP BY
599    				\item[] Using filesort - Дополнительный проход с сохранением ключей строк, которые попали под условие WHERE и последующей сортировкой самих ключей.
600    				\item[] Using join buffer (Block Nested Loop) - использование буфера для сохранения таблиц с последующим их объединением путем выборки подходящих строк из буфера
601			\end{itemize}
602		\end{itemize}
603
604		Выше представлена интерпретация зачений резульатат EXPLAIN'а. Оценим результат нашего запроса:
605		\begin{itemize}
606			\item[] В процессе выполнения запроса полнотекстово сканируются сразу 6 таблиц, которые вполедствие хранятся в виде временных таблиц ({\it type: all})
607			\item[] В первой выборке присутствует полное сканирование индексного дерева первой просматриваемой таблицы ({\it type: index}), несмотря на то, что в таблице содержится одна запись
608			\item[] Большая длина используемого ключа таблицы первой выборки
609			\item[] Использование индексного дерева ({\it extra: using index}) для создания временной таблицы ({\it extra: using temporary}) и дополнительный проход по временной таблице для сортировки ({\it extra: using filesort}) при том, что в таблице 1 запись
610			\item[] Большое количество вложенных ({\it Select\_type: DERIVED}) запросов, 10 подзапросов
611			\item[] Присутствуют 2 таблицы ({\it id: 5,6}) с большим количеством просмотренных записей (относительно результата запроса) ({\it rows: 2247})
612			\item[] Отсутствуют данные о ключах в шести запросах ({\it id: 1, 4, 5, null, 2, null})
613			\item[] Отсутствуют данные о количестве/проценте обработанных строк ({\it rows/filtered: null}) в процессе объединения ({\it select\_type: union reslut}) выборок {\it id:5 + id:10} и {\it id:3 + id:4}
614		\end{itemize}
615		
616		
617		
618		{
619	    		\subsection{Оптимизация запроса}
620    		}
621		
622		``Узкие места'' запроса на данный момент ясны. Присупим к оптимизации запроса. Для этого вновь обратимся к best practices по оптимизации запросов из  руководства к MySQL и выполним некоторые преобразования.\\
623		
624		{
625        		\subsubsection{Оптимизация условия WHERE}
626    		}	
627	
628		Оптимизтор MySQL умеет удалять ненужные скобки, сворачивать константы, удалять ненужные условия. Однако, эти действия выполняются практически без затрат и выполнение этих преобразований вручную можно опустить, чтобы оставить запрос в более понятном и удобном для чтения виде. 
629		
630		В некотрых случаях, если все столбцы в индексе числовые, MySQL может читать строки из индекса, совсем не обращаясь непосредственно к данным.\\
631		
632		Среди возможных доступных, но еще не примененных оптимизаций выделяется ``углубление'' условия WHERE в запросе. Так, при JOIN'е выборка строк, подходящих под условие, будет осуществляться до объединения, а значит при выполнении запроса не придется просматривать конечную ``большую'' выборку.
633
634		Протестируем для начала возможность подобной оптимизации:\\
635
636\begin{lstlisting}[caption={тестовый запрос до оптимизации WHERE}, label={lst:test1where_before}]
637SELECT SQL_NO_CACHE p.personID,  m.moduleID, s.taskID
638	FROM submissions s
639	JOIN persons p ON s.PersonID = p.PersonID
640	JOIN modules m ON s.ModuleID = m.ModuleID
641	WHERE p.PersonID BETWEEN 92 AND 109 AND m.ModuleName LIKE `%C%';
642\end{lstlisting}
643
644
645\begin{lstlisting}[caption={тестовый запрос после оптимизации WHERE}, label={lst:test1where_after}]
646SELECT SQL_NO_CACHE p.personID, m.moduleID, s.taskID
647	FROM submissions s
648	JOIN (SELECT personID FROM persons
649		WHERE PersonID BETWEEN 92 AND 109) p
650	ON p.PersonID = s.PersonID
651	JOIN (SELECT moduleID FROM modules WHERE ModuleName LIKE '%C%') m
652	ON m.ModuleID = s.ModuleID;
653\end{lstlisting}
654
655\begin{table}[h]
656    \caption {Сравнение таймингов запросов}
657    \label {test1where}
658    \begin{tabular}{|l|c|c|}
659    \hline
660    Запрос                  & Тайминг клиентской стороны & Тайминг серверной стророны                                                                                                                                                                                       \\ \hline
661    До оптимизации     & 0.0471                     & 0.0463                                                                                                                                                                                                           \\ \hline
662    После оптимизации  & 0.0313                     & 0.0317                                                                                                                                                                                                           \\ \hline
663    \end{tabular}
664\end{table}
665
666%\begin{table}[h]
667%    \caption {test1where}
668%    \begin{tabular}{|l|}
669%    \hline
670%    Test query before                                                                                                                                                                                                                                                                                                                                      \\ \hline
671%    \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
672%    Client side timing: 0.0471\\Server side timing: 0.0463                                                                                                                                                                                                                                                                                                 \\ \hline
673%    Test query after                                                                                                                                                                                                                                                                                                                                       \\ \hline
674%    \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
675%    Client side timing: 0.0313\\Server side timing: 0.0317                                                                                                                                                                                                                                                                                                 \\ \hline
676%    \end{tabular}
677%\end{table}
678
679		Как видно, оптимизация при переносе условия вглубь запроса имеет место быть. Теперь применим эту оптимизацию к основному запросу:\\
680		
681\begin{lstlisting}[caption={основной запрос до I оптимизации WHERE}, label={lst:bigq_where1_before}]
682FROM Students as a3, RelGroupsModules as a4
683LEFT OUTER JOIN RelTasksModules USING(ModuleId) 
684LEFT OUTER JOIN Tasks USING(TaskId) 
685LEFT OUTER JOIN Submissions 
686	ON Submissions.PersonId = 1 AND ...
687	AND (Submissions.Draft IS NULL OR Submissions.Draft = 0) 
688WHERE a3.PersonId = 1 
689	AND a3.GroupId = a4.GroupId 
690\end{lstlisting}
691
692
693\begin{lstlisting}[caption={основной запрос после I оптимизации WHERE}, label={lst:bigq_where1_after}]
694FROM (
695	SELECT PersonID, a3.GroupID, ModuleID, ExpireTime
696		FROM Students as a3,
697		relgroupsmodules as a4
698		WHERE a3.PersonId = 1
699			AND a3.GroupID = a4.GroupId
700) as pg
701\end{lstlisting}
702		
703%\begin{table}[h]
704%    \caption {main1where1}
705%    \begin{tabular}{|l|}
706%    \hline
707%    Main query before                                                                                                                                                                                                                                                                                                                                                                                                                                                                         \\ \hline
708%    			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
709%    Main query after                                                                                                                                                                                                                                                                                                                                                                                                                                                                          \\ \hline
710%    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
711%    \end{tabular}
712%\end{table}
713
714		На листингах ~\ref{lst:bigq_where1_before} и ~\ref{lst:bigq_where1_after} представлены запрос до и после оптимизации, озвученной выше. Существует еще одна возможность применить оптимизацию к основному запросу:\\
715		
716\begin{lstlisting}[caption={основной запрос до II оптимизации WHERE}, label={lst:bigq_where2_before}]
717SELECT * FROM ( ... )
718UNION SELECT ... FROM ...
719LEFT OUTER JOIN Persons 
720	ON Persons.PersonId = Submissions.PersonId 
721WHERE a1.PersonId = 1
722\end{lstlisting}
723
724\begin{lstlisting}[caption={основной запрос после II оптимизации WHERE}, label={lst:bigq_where2_after}]
725UNION SELECT ... FROM (
726	SELECT * FROM Approvers
727		WHERE PersonID = 1
728) AS a1
729\end{lstlisting}
730%~\ref{lst:    }
731
732		На листингах ~\ref{lst:bigq_where2_before} и ~\ref{lst:bigq_where2_after} применена еще одна аналогичная оптимизация WHERE.
733%		
734%\begin{table}[h]
735%    \caption {main1where2}
736%    \begin{tabular}{|l|}
737%    \hline
738%    Main query before                                                                                                                                                                                 \\ \hline
739%    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
740%    Main query after                                                                                                                                                                                  \\ \hline
741%    \\\\        \\                                                                                                             \\ \hline
742%    \end{tabular}
743%\end{table}
744		
745		{
746			\subsubsection{Оптимизация ORDER BY / GROUP BY}
747		}
748		
749		При использовании GROUP BY в общем случае при выполнении запроса будет просканирована вся таблица, затем будет создана временная таблица для распределения записей по группам и применения к ним агрегирующих функций. Но, в некоторых случаях MySQL может поступить иначе, если имеет дело с индексами. 
750		
751		Самым важным предусловием в данном случае является наличие индекса по всем столбцам, фигурирующим в GROUP BY. В таком случае создания дополнительной таблицы может не потребоваться и она будет заменена работой с индексным деревом.\\
752		
753		
754		В MySQL заложены 2 способа выполнения GROUP BY запроса с использованием индексов:
755		\begin{itemize}
756			\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.
757			\item[] Tight Index Scan - ``плотное'' сканирование индекса. В случае, если условия для свободного сканирования не могут быть выполнены, все еще можно добиться результата без создания дополнительной таблицы. Если в условии WHERE присутствует проверка диапазона значений, данный метод читает лишь индексы, удовлетворяющие условиям. Иначе он запускает сканирование индекса. Лишь после этих операций начинается группировка значений. 
758		\end{itemize}
759		
760		Проверим оптимизацию на примере, в котором применяется форсированное использование индекса:\\
761		
762\begin{lstlisting}[caption={тестовый запрос до оптимизации ORDER BY}, label={lst:test_order_before}]
763SELECT SQL_NO_CACHE * FROM persons 
764	HAVING FirstName LIKE '%a%'
765	ORDER BY FirstName;
766\end{lstlisting}
767%~\ref{lst:}
768
769\begin{lstlisting}[caption={тестовый запрос после оптимизации ORDER BY}, label={lst:test_order_after}]
770CREATE INDEX PersonsFirstNameIndex ON Persons(FirstName);    
771SELECT SQL_NO_CACHE * FROM persons FORCE INDEX (PersonsFirstNameIndex)
772	HAVING FirstName LIKE '%a%'
773	ORDER BY FirstName;
774\end{lstlisting}
775%~\ref{lst:}
776
777		Выполним оба запроса. Сравним результаты выполнения:
778
779\begin{table}[h]
780    \caption {Сравнение таймингов запросов}
781    \label {test1where}
782    \begin{tabular}{|l|c|c|}
783    \hline
784    Запрос                  & Тайминг клиентской стороны & Тайминг серверной стророны                                                                                                                                                                                       \\ \hline
785    До оптимизации     & 0.0160                     & 0.0159                                                                                                                                                                                                           \\ \hline
786    После оптимизации  & 0.0                     & 0.0018                                                                                                                                                                                                           \\ \hline
787    \end{tabular}
788\end{table}
789
790%
791%\begin{table}[h]
792%    \caption {test2order}
793%    \begin{tabular}{|l|}
794%    \hline
795%    Test query before                                                                                                                                                                                                                                                                                        \\ \hline
796%    SELECT SQL\_NO\_CACHE * FROM persons\\	HAVING FirstName LIKE '\%а\%'\\    ORDER BY FirstName;                                                                                                                                                                                                            \\ \hline
797%    Client side timing: 0.0160\\Server side timing: 0.0159                                                                                                                                                                                                                                                   \\ \hline
798%    Test query after                                                                                                                                                                                                                                                                                         \\ \hline
799%    CREATE INDEX PersonsFirstNameIndex ON Persons(FirstName); \\\\SELECT SQL\_NO\_CACHE * FROM persons FORCE INDEX (PersonsFirstNameIndex)\\	HAVING FirstName LIKE '\%а\%'\\    ORDER BY FirstName;                                                                                                          \\ \hline
800%    Client side timing: 0.0\\Server side timing: 0.0018                                                                                                                                                                                                                                                      \\ \hline
801%    \end{tabular}
802%\end{table}
803		
804		Как следует из результатов выше, данная оптимизация возможна. Для оптимизации ``боевого'' запроса мы можем добавить индесы на сорируемые /группируемые поля, либо добиться использования левых префиксов уже имеющихся индексов. В данном случае постараемся избавить от повторной выборки (таблицы {\it a7} и {\it a8}):\\
805		
806\begin{lstlisting}[caption={основной запрос до I оптимизации GROUP BY}, label={lst:bigq_group1_before}]
807SELECT ...
808	FROM (
809	SELECT DISTINCT ... FROM ...
810	GROUP BY GroupId, ModuleId, TaskId
811) as a8
812\end{lstlisting}
813%~\ref{lst:}
814
815\begin{lstlisting}[caption={основной запрос после I оптимизации GROUP BY}, label={lst:bigq_group1_after}]
816SELECT ...
817	FROM ( ... ) AS a7
818GROUP BY GroupId, ModuleId, TaskId 
819\end{lstlisting}
820%~\ref{lst:}		
821		
822		
823%\begin{table}
824%    \caption {main2groupby1}
825%    \begin{tabular}{|l|}
826%    \hline
827%    Main query before                                                              \\ \hline
828%    SELECT DISTINCT ...\\FROM ...\\GROUP BY GroupId, ModuleId, TaskId \\		  \\ \hline
829%    Main query after                                                               \\ \hline
830%    SELECT DISTINCT ...\\FROM ...\\... ) as a7\\GROUP BY GroupId, ModuleId, TaskId \\ \hline
831%    \end{tabular}
832%\end{table}
833
834		Итак, мы избавлись от дублирующей выборки, как следует из Листингов ~\ref{lst:bigq_group1_before} и ~\ref{lst:bigq_group1_after}. Применим эту же оптимизацию еще раз:\\
835	
836		
837\begin{lstlisting}[caption={основной запрос до II оптимизации GROUP BY}, label={lst:bigq_group2_before}]
838(SELECT GroupId, ModuleId, max(IsStudent) AS IsStudent, max(IsApprover) AS IsApprover 
839	FROM ( 
840		...
841	) as a10
842	GROUP BY GroupId, ModuleId 
843) as a12
844\end{lstlisting}
845%~\ref{lst:}			
846		
847\begin{lstlisting}[caption={основной запрос после II оптимизации GROUP BY}, label={lst:bigq_group2_after}]
848(SELECT GroupId, ModuleId, IsStudent, IsApprover
849	FROM WorkRole 
850		...
851	GROUP BY GroupId, ModuleId 
852) as a12
853\end{lstlisting}
854%~\ref{lst:}
855		
856%\begin{table}
857%    \caption {main2groupby2}
858%    \begin{tabular}{|l|}
859%    \hline
860%    Main query before                                                                                                                                              \\ \hline
861%    SELECT ...\\	FROM ( SELECT ... FROM ...\\		JOIN ...\\		WHERE ...\\		UNION SELECT ... FROM...\\		WHERE ...\\		) as a10\\	GROUP BY GroupId, ModuleId \\	) as a12 \\ \hline
862%    Main query after                                                                                                                                               \\ \hline
863%    CREATE INDEX ... ON WorkRole(GroupID, ModuleID)\\ \\SELECT ... FROM WorkRole \\WHERE ...\\	GROUP BY GroupId, ModuleId \\	) as a12                               \\ \hline
864%    \end{tabular}
865%\end{table}
866
867		Согласно Листингам ~\ref{lst:bigq_group2_before} и ~\ref{lst:bigq_group2_after} мы сократили количество используемых таблиц, введя дополнительную таблицу {\it WorkRole}, речь о которой подробнее будет немного позднее. Сейчас стоит лишь отметить, что в запросе задействован алгоритм группировки по индексам. 
868		
869		Оптимизируем теперь и ORDER BY с одним допущением. Поскольку система T-BMSTU на данный момент используется только в МГТУ, обращение к таблице {\it Institutions} можно заменить выборкой из этой таблицы константы:\\
870		
871		
872\begin{lstlisting}[caption={основной запрос до оптимизации ORDER BY}, label={lst:bigq_order_before}]
873SELECT ... FROM ...
874JOIN ... ON ...
875...
876ORDER BY 
877	Institutions.InstitutionId ASC, ...
878\end{lstlisting}
879%~\ref{lst:}			
880		
881\begin{lstlisting}[caption={основной запрос после оптимизации ORDER BY}, label={lst:bigq_order_after}]
882SELECT ... FROM ...
883JOIN ... ON ...
884JOIN (SELECT institutions.InstitutionID, institutions.InstitutionName FROM ...
885	WHERE InstitutionID = 1) AS inst
886ORDER BY ...
887\end{lstlisting}
888%~\ref{lst:}
889
890%\begin{table}
891%    \caption {main2orderby1}
892%    \begin{tabular}{|l|}
893%    \hline
894%    Main query before                                                                                                                                                                              \\ \hline
895%    SELECT ... FROM ...\\\\...\\JOIN ... ON ...\\\\	Institutions.InstitutionId ASC, \\	...                                                                                 \\ \hline
896%    Main query after                                                                                                                                                                               \\ \hline
897%    SELECT ... FROM ...\\JOIN ... ON ...\\JOIN (SELECT institutions.InstitutionID, institutions.InstitutionName  FROM ...\\      WHERE InstitutionID = 1) AS inst\\JOIN ... ON ...\\ORDER BY \\... \\ \hline
898%    \end{tabular}
899%\end{table}
900		
901		Итак, мы сократили количество полей (см Листинги ~\ref{lst:bigq_order_before} и ~\ref{lst:bigq_order_after}), по которым происходит сортировка и теперь в одной из таблиц первичной выборки присутствует константная запись из таблицы, что немного ускоряет выполнение запроса.
902		
903		{
904		        \subsubsection{Оптимизация LIMIT X}
905    		}		
906    
907    		В некоторых случаях оптимизатор MySQL оптимизирует запрос, который имеет в своем составе LIMIT и не имеет при этом HAVING. Если в качестве лимита указано необльшое значение, MySQL вероятно предпочтет выолнить проход по индексам, в то время, как в обычном случае началось бы сканирование таблицы. 
908    		
909    		Если LIMIT используется совместно с ORDER BY, MySQL закончит сортировку, как только наберется достаточное для LIMIT'а количество строк. В случае с DISTINCT MySQL поступит аналогичным образом.\\
910    		
911    		Однако, комбинация ORDER BY вместе с LIMIT 1 может быть оптимизирована. Так, запрос вида \verb|SELECT col FROM table ORDER BY col LIMIT 1| может быть заменен на \verb|SELECT MIN(col) FROM table|. В случае, если столбец проиндексирован, MySQL просто вернет минимальное значение столбца из индекса, в то время, как LIMIT+ORDER BY должны упорядоченно обойти индекс. 
912    		
913    		Для начала проверим возможность оптимизации на таком тестовом запросе:\\
914    		
915\begin{lstlisting}[caption={тестовый запрос до оптимизации LIMIT}, label={lst:test_limit_before}]
916SELECT SQL_NO_CACHE LoginTime FROM Sessions
917	WHERE PersonID BETWEEN 92 AND 109
918	ORDER BY LoginTime DESC
919	LIMIT 1;
920\end{lstlisting}
921%~\ref{lst:}
922
923\begin{lstlisting}[caption={тестовый запрос после оптимизации LIMIT}, label={lst:test_limit_after}]
924SELECT SQL_NO_CACHE MAX(LoginTime) FROM Sessions
925	WHERE PersonID BETWEEN 92 AND 109;
926\end{lstlisting}
927%~\ref{lst:}
928
929		Выполним оба тестовых запроса. Сравним результаты выполнения:
930
931\begin{table}[h]
932    \caption {Сравнение таймингов запросов}
933    \label {test1where}
934    \begin{tabular}{|l|c|c|}
935    \hline
936    Запрос                  & Тайминг клиентской стороны & Тайминг серверной стророны                                                                                                                                                                                       \\ \hline
937    До оптимизации     & 0.0780                     & 0.0913                                                                                                                                                                                                           \\ \hline
938    После оптимизации  & 0.0470                     & 0.0501                                                                                                                                                                                                           \\ \hline
939    \end{tabular}
940\end{table}
941
942%    		
943%\begin{table}
944%    \caption {test3limit}
945%    \begin{tabular}{|l|}
946%    \hline
947%    Test query before                                                                                                                                                                                                                                                                                        \\ \hline
948%    SELECT SQL\_NO\_CACHE LoginTime FROM Sessions\\	WHERE PersonID BETWEEN 92 AND 109\\	ORDER BY LoginTime DESC\\    LIMIT 1;                                                                                                                                                                                \\ \hline
949%    Client side timing: 0.0780\\Server side timing: 0.0913                                                                                                                                                                                                                                                   \\ \hline
950%    Test query after                                                                                                                                                                                                                                                                                         \\ \hline
951%    SELECT SQL\_NO\_CACHE MAX(LoginTime) FROM Sessions\\	WHERE PersonID BETWEEN 92 AND 109;                                                                                                                                                                                                                  \\ \hline
952%    Client side timing: 0.0470\\Server side timing: 0.0501                                                                                                                                                                                                                                                   \\ \hline
953%    \end{tabular}
954%\end{table}
955    		
956    		Эта оптимизация дает незначительные преимущества в случае индексированных столбцов и небольшой выигрыш в случае отсутствия индексов. Оптимизация присутствует на Листингах ~\ref{lst:test_limit_before} и ~\ref{lst:test_limit_after}.
957    		
958    		Применим эту оптимизацию:\\
959    		
960    		
961\begin{lstlisting}[caption={основной запрос до оптимизации LIMIT}, label={lst:bigq_limit_before}]
962SELECT Accepted FROM approvements a6
963	JOIN submissions
964	JOIN relgroupsmodules a4
965	WHERE a6.SubmissionId = Submissions.SubmissionId 
966		AND (a4.ExpireTime IS NULL 
967		OR Submissions.SubmissionTime < a4.ExpireTime) 
968	ORDER BY ApprovementTime DESC 
969	LIMIT 1; 
970\end{lstlisting}
971%~\ref{lst:}
972
973\begin{lstlisting}[caption={основной запрос после оптимизации LIMIT}, label={lst:bigq_limit_after}]
974SELECT MAX(Accepted) FROM approvements a6
975	JOIN submissions
976	JOIN relgroupsmodules a4
977	WHERE a6.SubmissionId = Submissions.SubmissionId 
978		AND (a4.ExpireTime IS NULL 
979		OR Submissions.SubmissionTime < a4.ExpireTime) 
980		AND ApprovementTime = (SELECT MAX(ApprovementTime) 
981					FROM approvements);
982\end{lstlisting}
983%~\ref{lst:}
984
985
986%\begin{table}
987%    \caption {main3limi1}
988%    \begin{tabular}{|l|}
989%    \hline
990%    Main query before                                                                                                                                                                                                                                                                                                                   \\ \hline
991%    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
992%    Main query after                                                                                                                                                                                                                                                                                                                    \\ \hline
993%    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
994%    \end{tabular}
995%\end{table}
996
997		Доступна еще одна оптимизация в запросе, подобная изложенной на Листингах ~\ref{lst:bigq_limit_before} и ~\ref{lst:bigq_limit_after} . Опустим ее, так как их механики в запросе идентичны с точностью до знаков.
998    
999    		{
1000		        \subsubsection{Оптимизация UNION и DISTINCT}
1001    		}
1002    		
1003		Преобразование UNION в UNION ALL в запросе дает большую выгоду. Первым предположением является то, что это достигается за счет того, что UNION ALL'у не нужна дополнительная таблица для хранения результата, однако это не совсем верно. Обе формы объединения используют временную таблицу для генерации результата. 
1004		
1005		Интересен тот факт, что создание этой временной таблицы можно посмотреть с помощью SHOW STATUS. В обычном EXPLAIN'е этой дейстиве по-умолчанию скрыто. 
1006		
1007		Отличием же в выполнении этих запросов является то, что обычный UNION создает промежуточную таблицу, накладывает на нее индекс и лишь после этого приступает к выборке, удаляя дубликаты. В то же время UNION ALL пропускает эти действия, за счет чего и достигается повышение производительности.\\
1008		
1009		Проверим этот факт, выполнив запрос один раз с  объединением UNION, другой - с объединением UNION ALL, как показано на Листингах ~\ref{lst:test_union_before} и ~\ref{lst:test_union_after}:\\
1010		
1011
1012\begin{lstlisting}[caption={тестовый запрос до оптимизации UNION}, label={lst:test_union_before}]
1013SELECT DISTINCT personID, groupID, moduleID, taskID, SubmissionTime
1014	FROM Submissions WHERE PassedTests IS NOT NULL 
1015UNION 
1016SELECT DISTINCT personID, groupID, moduleID, taskID, SubmissionTime
1017	FROM Submissions WHERE PassedTests IS NULL;
1018\end{lstlisting}
1019%~\ref{lst:}
1020
1021\begin{lstlisting}[caption={тестовый запрос после оптимизации UNION}, label={lst:test_union_after}]
1022SELECT DISTINCT personID, groupID, moduleID, taskID 
1023	FROM Submissions WHERE PassedTests IS NOT NULL 
1024UNION ALL
1025SELECT DISTINCT personID, groupID, moduleID, taskID 
1026	FROM Submissions WHERE PassedTests IS NOT NULL;
1027\end{lstlisting}
1028%~\ref{lst:}
1029
1030		Выполним оба тестовых запроса. Сравним результаты выполнения:
1031
1032\begin{table}[h]
1033    \caption {Сравнение таймингов запросов}
1034    \label {test1where}
1035    \begin{tabular}{|l|c|c|}
1036    \hline
1037    Запрос                  & Тайминг клиентской стороны & Тайминг серверной стророны                                                                                                                                                                                       \\ \hline
1038    До оптимизации     & 0.1400                     & 0.1337                                                                                                                                                                                                           \\ \hline
1039    После оптимизации  & 0.0780                     & 0.0657                                                                                                                                                                                                           \\ \hline
1040    \end{tabular}
1041\end{table}
1042
1043%\begin{table}
1044%    \caption {test4union}
1045%    \begin{tabular}{|l|}
1046%    \hline
1047%    Test query before                                                                                                                                                                                                                                                                                        \\ \hline
1048%    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
1049%    Client side timing: 0.1400\\Server side timing: 0.1337                                                                                                                                                                                                                                                   \\ \hline
1050%    Test query after                                                                                                                                                                                                                                                                                         \\ \hline
1051%    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
1052%    Client side timing: 0.0780\\Server side timing: 0.0657                                                                                                                                                                                                                                                   \\ \hline
1053%    \end{tabular}
1054%\end{table}
1055		
1056		Основным моментом здесь является то, что в обоих запросах присутствуют ключевые слова DISTINCT. А значит, по схеме выполнения MySQL сначала сделает выборку из одной таблицы, отфильтровав дубликаты, затем поступит по аналогии со второй таблицей. Затем в запросе с обычным UNION, после объединения выборок во временную таблицу, MySQL добавит индексы и вновь отфильтрует результаты, пройдя по таблице. Однако в таблице к тому моменту уже не будет дубликатов и этот проход будет лишним. 
1057		
1058		Избавившись от него с помощью использования UNION ALL, мы получим выигрыш в производительности.
1059		
1060		Стоит также заметить, что как и в случае с GROUP BY / ORDER BY, MySQL может использовть лишь левые префиксы индексов для работы с ключами, и в целом DISTINCT иногда рассматривается оптимизатором, как частный случай GROUP BY.
1061    
1062    		Выполним описанные выше преобразования, так как аналогичные условия имеются в рассматриваемом нами запросе и запишем новые запросе в Листинги ~\ref{lst:bigq_union_before} и ~\ref{lst:bigq_union_after}:\\
1063  
1064  
1065\begin{lstlisting}[caption={основной запрос до оптимизации UNION}, label={lst:bigq_union_before}]
1066SELECT DISTINCT ... FROM ... AS a8
1067UNION
1068SELECT DISTINCT ... FROM ... AS a1
1069\end{lstlisting}
1070%~\ref{lst:}
1071
1072\begin{lstlisting}[caption={основной запрос после оптимизации UNION}, label={lst:bigq_union_after}]
1073SELECT DISTINCT ... FROM ... AS a7
1074UNION ALL
1075SELECT DISTINCT ... FROM ... AS a1
1076\end{lstlisting}
1077%~\ref{lst:}    
1078
1079		
1080%\begin{table}
1081%    \caption {main4union1}
1082%    \begin{tabular}{|l|}
1083%    \hline
1084%    Main query before                                                                 \\ \hline
1085%    SELECT DISTINCT ... FROM ... AS a8 \\UNION \\SELECT DISTINCT ... FROM ... AS a1   \\ \hline
1086%    Main query after                                                                  \\ \hline
1087%    SELECT DISTINCT ... FROM ... AS a7\\UNION ALL\\SELECT DISTINCT ... FROM ... AS a1 \\ \hline
1088%    \end{tabular}
1089%\end{table}
1090    
1091    
1092    		{
1093		        \subsubsection{Оптимизация LEFT и RIGHT JOIN}
1094    		}
1095    
1096    		MySQL выполняет объединение таблиц, например \verb|A LEFT JOIN B| подобным образом:
1097    		\begin{itemize}
1098    			\item[] Таблица B устанавливается зависимой от A и от всех таблиц, от которых зависит A. Таблица A в свою очередь устанваливается зависимой от всех таблиц, кроме B, которые используются в условии LEFT JOIN
1099    			\item[] Используется условие LEFT JOIN для того, чтобы решить, как выбрать записи из таблицы B
1100    			\item[] Выполняются все стандартные оптимизации входящих внутрь запроса условий
1101    			\item[] В случае, если в таблице B запись, соответствующая условию ON, и для которой в таблице A имеется запись, отсутствует, то в таблицу B дописывается запись со всеми столбцами, равными NULL
1102    			\item[] Новая запись в таблице со всеми параметрами, равными NULL, добавляется в результирующей выборке в соответствие непустой записи из таблицы A
1103		\end{itemize}
1104		
1105		Реализация RIGHT JOIN аналогична с точностью до порядка таблиц. Оптимизацией JOIN запросов является перестановка таблиц в запросах. Однако LEFT JOIN и STRAIGHT JOIN практически не оптимизируются.
1106		
1107		Еще одна форма объединения - STRAIGHT JOIN. Эта команда не дает оптимизатору выбора, кроме как принять порядок, заданный пользователем, вследствие чего никакие дополнительные преобарзования не производятся и запрос за счет этого ускоряется. Как и в остальных случаях упор делается на наличие индексов. Достигается это улучшение только в том, случае, если известно, что ``навязанный'' оптимзатору порядок соединения однозначно лучше чем тот, который может выбрать он сам. В большинстве случаев ``навязывание'' подобных условий оптимизатору может привести к обратному результату.\\
1108    
1109    		Навязвание использования индексов совместно с ``непереставляемым'' LEFT JOIN'ом уже рассматривалось ранее. Чтобы избежать дублирования, опустим этот момент здесь.
1110    
1111    		{
1112		        \subsubsection{Оптимизация IS (NOT) NULL}
1113    		}
1114    		
1115    		MySQL оптимизатор умеет удалять ненужны проверки на наличие /отсутстивие NULL значений. Так, если условие WHERE содержит проверку столбца {\it a} IS NULL при том, что сам столбец объявлен как NOT NULL, проверка будет удалена.
1116    		
1117    		Также, согласно 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}:\\
1118    		
1119\begin{lstlisting}[caption={основной запрос до оптимизации IS (NOT) NULL}, label={lst:bigq_null_before}]
1120(SELECT Accepted 
1121	FROM Approvements as a6
1122	WHERE a6.SubmissionId = Submissions.SubmissionId 
1123		AND (a4.ExpireTime IS NULL 
1124			OR Submissions.SubmissionTime < a4.ExpireTime)
1125\end{lstlisting}
1126%~\ref{lst:}
1127
1128\begin{lstlisting}[caption={основной запрос после оптимизации IS (NOT) NULL}, label={lst:bigq_null_after}]
1129(SELECT Accepted 
1130	FROM Approvements as a6
1131	WHERE a6.SubmissionId = Submissions.SubmissionId 
1132		AND (a4.ExpireTime > '0000-00-00 00:00:00' 
1133			OR Submissions.SubmissionTime < a4.ExpireTime)
1134\end{lstlisting}
1135%~\ref{lst:}   
1136
1137%\begin{table}
1138%    \caption {main6null1}
1139%    \begin{tabular}{|l|}
1140%    \hline
1141%    Main query before                                                                                                                                                                                                                                                            \\ \hline
1142%    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
1143%    Main query after                                                                                                                                                                                                                                                             \\ \hline
1144%    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
1145%    \end{tabular}
1146%\end{table}    		
1147    		
1148 		{
1149		        \subsection{MySQL и индексы}
1150    		}   
1151    
1152    		Лучший способ улучшить производительность операции SELECT это создать индексы на одном или нескольких столбцах, используемых в запросе. Индексы выступают в качетсве указателей на записи, позволяя быстро определить какие записи подходят под условие WHERE и выбрать остальные поля записи. 
1153    		
1154    		Все типы данных в MySQL могут быть проиндексированы. Все индексы в MySQL в рамках движка InnoDB, будь то PRIMARY, UNIQUE и INDEX, сохранены в B-беревьях. Индексные страницы при этом хранятся вместе с данными. MyISAM же использует для этих целей хеш-таблицы.
1155    		
1156    		И, хотя может возникнуть желание создать индексы по всем возможным столбцам, неиспользуемые и ненужные ндексы занимают место и отнимают у оптимизатора  MySQL время на поиск необходимиого ему оптимального индекса.
1157    		
1158    		Индексы также увеличивают ``стоимость'' операций вставки, удаления и обновления, так как каждый индекс должен быть обновлен.
1159    
1160    		MySQL поддерживает до 16 ключей на одной таблице. 
1161    		
1162    		Стобцы типов BLOB и TEXT поддерживают неполное индексирование. На столбцах типов CHAR и VARCHAR разрешено создавать частичные индексы, которые при этом могут составлять часть многостолбцового индекса.
1163    		
1164    		Как уже оговаривалось ранее, только крайние левые префиксы индекса могут быть использованы большинством операций. Однако, иногда выборка может быть произведена совсем без обращения к данным. Это происходит в том случае, если выбирается часть индекса по условию другой части индекса. Так, трехстолбцовый индекс на столбцах {\it (a, b, c, d)} дает поисковые преимущества в таких сочетаниях: {\it(a), (a, b), (a, b, c)}. При выборке же можно использовать столбец {\it c} в то время, как условие наложено на столбец {\it a} или {\it b}.\\
1165    
1166    		Ранее было отмечено, что данные большинства таблиц в исходной базе данных редактируются нечасто. Поэтому, на них можно без ограничений накладыватьь индексы. В базе присутствуют лишь 4 постоянно используемых таблицы, которые были отмечены ранее. На этих таблицах уже присутствуют индексы помимо PRIMARY и UNIQUE. Эти индексы, действительно, используются оптимизатором и ``утяжелять'' таблицы дополнительными индексами мы не будем. 
1167    		
1168    		Вместо этого добавим несколько индексов, возможное отсутствие некоторых из которых приводило к полму сканированию таблиц согласно первому результату EXPLAIN'а:\\
1169    		
1170    		\begin{verbatim}
1171CREATE INDEX InstitutionIDInstitutionNameIndex 
1172             ON Institutions(InstitutionID, InstitutionName);
1173CREATE INDEX GroupInstitutionTimeNameIndex 
1174             ON Groups (GroupID, InstitutionID, TimeID, GroupName);
1175CREATE INDEX GroupIndex ON Approvers (GroupID);
1176CREATE UNIQUE INDEX RelGroupsModulesExpireTimeGroupIDModuleIDUniqueIndex
1177             ON RelGroupsModules(ExpireTime, GroupID, ModuleID);
1178		\end{verbatim}
1179    
1180    		
1181    		{
1182		        \subsection{Другие оптимизации}
1183    		}   
1184    		
1185    		{
1186		        \subsubsection{Выбор движка базы данных}
1187    		}  
1188    		
1189    		Одной из особенностей MySQL является наличие большого числа движков, практически каждый из которых специализирован под конкретную задачу. Предполагается, что выбор движка происходит на этапе проектирования. Перечислим основные движки и озвучим их особенности:
1190    		
1191    		\begin{itemize}
1192    			\item[] MyISAM - не поддерживает транцзакции, но поддерживает полнотекстовый поиск. Внешние ключи недоступны. Данные и индексы хранятся отдельно. Сравнительно невысокая надежность хранения данных
1193    			\item[] Memory (ранее, HEAP) - отличается несравнимо быстрой работой с небольшими таблицами, так как хранит все временные таблицы в оперативной памяти. Практически не имеет конкурентов по скорости работы
1194    			\item[] Federated - федерация серверов, обеспечивающая высокую масштабируемость и высокую отказоустойчивость
1195    			\item[] CSV - хранит таблицы в CSV формате и позволяет редактировать их внешними приложениями. Отличается также невысокой стаблильнотсью работы
1196    			\item[] InnoDB - движок для таблиц ``общего'' назначения, тем не менее поддерживающий большие таблицы. Полная поддержка транзакций (ACID), внешних ключей. Максимальный объем - 64ТБ. По заявлениям разработчиков InnoDB - самый быстрый основанный ``на диске'' движок. Однако, сильно зависит от надлежащей индексации данных
1197    			\item[] Blackhole - движок, созданный для задач репликации.Не умеет самостоятельно хранить данные. Может выстпуть ``мастером'' в схеме репликации master-slave
1198    			\item[] Example - экспериментальный движок для разработчиков. Таблицы, основанные на нем не могут хранить данные и нужны в первую очередь для создания новых типов таблиц.
1199    		\end{itemize}
1200    		
1201    		Как было замечено ранее, в работе был выбран движок InnoDB по причине поддержки внешних ключей, транзакций и других функций ``из коробки''.
1202    		
1203    		
1204    		{
1205		        \subsubsection{Оптимизация некоторых типов данных}
1206    		}   
1207    
1208    		Одним из способов измерения производительности запросов MySQL называет измерение количества дисковых операций. Для небольших таблиц обычно можно найти строку одним обращением. Для больших таблиц, использующих дерево индексов, количество дисковых операции можно оценить формулой
1209    		
1210    		$$C=\frac{\ln row\_count}{\ln {\frac{index\_block\_length \times 2}{3 \times (index\_length + data\_pointer\_length)}}}$$
1211    		
1212    		Индексный блок обычно составляет 1024 байта, указатель - 4 байта.
1213    		
1214    		Можем оценить количество дисковых операций для таблицы {\it Submissions}:
1215    		
1216    		$$C=\frac{\ln 130'000}{\ln {\frac{1'024 \times 2}{3 \times (16 + 4)}}} = \frac{11.775}{3.530} \approx 3$$
1217    		
1218    		Итого, потребуется в среднем 3 дисковых операции для того, чтобы найти конкретную строку в таблице {\it Submissions}, вмещающей 130'000 записей при наличии на ней индекса длины 16.
1219    		
1220    		Логарифмическая зависимость объема таблицы позволяет оценить незначительность количества дисковых операций для большинства таблиц базы. Взяв абстрактную таблицу, содержащую, например, 300 записей и имеющую индекс длины 4 на столбце типа INTEGER выясним, что записи из подобных таблиц выбираются за одно обращение. Это еще раз подтверждает возможность наложения дополнительных индексов на подобные таблицы:
1221    		
1222    		$$C=\frac{\ln 300}{\ln {\frac{1'024 \times 2}{3 \times (4 + 4)}}} \approx 1$$
1223    		
1224    		И хотя в наше время скорость работы важнее объема затраченной памяти, в MySQL  рекомендуется содержать данные компактно. А значит, следуют и небольшие оптимизации некоторых таблиц базы данных:\\
1225    		
1226    		\begin{itemize}
1227    			\item[] TINYINT или MEDIUMINT препочтительнее ``обчыного'' типа INT, если это не проиворечит логике работы
1228    			\item[] NULL требует дополнительного места, а значит, ограничения в виде NOT NULL значений немного уменьшат место. Это преимущество в рассамтриваемой базе незначительно ввиду небольшого общего объема данных
1229    			\item[] Вынос логики работы с величинами времени и даты во вне. В базе при этом можно оставить значения типа TIMESTAMP или INT. Эта оптимизация значительнее предыдущих и может дать преимущество в несколько раз.
1230    		\end{itemize}
1231    		
1232    		{
1233		        \subsubsection{Оптимизация базы данных}
1234    		}
1235    		
1236    		В ходе рассмторения плана выполнения запроса было выявлено большое количество подзапросов, в том числе  с полным сканированием таблиц. Один из таких запросов, с {\it id=1} отмечен как {\it derived 2}, ссылающийся на подзапрос с {\it id=2}. Тот в свою очередь отмечен, как {\it derived 3}. Подзапрос с {\it id=3} представляет из себя 2 подзапроса - {\it a11} и {\it RelGroupsModules}. После этого выполняется выборка из таблицы {\it a9}. И лишь после этого происходит объединение этих подзапросов в результирующую выборку. Все это сочетается с неопределенностью ключей для всех этих выборок а также постоянным сканированием таблиц.
1237    		
1238    		Это можно исправить путем создания дополнительной таблицы. Назовем ее WorkRole. В нее перенесем функциональность под разделению ролей пользователей на студентов и принимающую их сторону:\\
1239    		
1240\begin{lstlisting}[caption={Скрипт создания таблицы WorkRole}, label={lst:table_workrole}]
1241CREATE TABLE WorkRole (
1242    PersonID        INTEGER NOT NULL REFERENCES Persons 
1243                            ON DELETE CASCADE ON UPDATE CASCADE,
1244    GroupID         INTEGER NOT NULL REFERENCES Groups 
1245                            ON DELETE CASCADE ON UPDATE CASCADE,
1246    ModuleID        INTEGER NOT NULL REFERENCES Modules 
1247                            ON DELETE CASCADE ON UPDATE CASCADE,
1248    
1249    IsStudent       TINYINT NOT NULL,
1250    IsApprover      TINYINT NOT NULL,
1251 
1252    PRIMARY KEY (PersonID, GroupID, ModuleID, IsStudent)
1253);
1254\end{lstlisting}
1255    		
1256    		Наличие ключа, состоящего из 4 столбцов объясняется спецификой выборки данных в запросе. Таблица носит  технический характер и создана с целью сбора данных для запроса. При этом необходимо наличие PRIMARY индекса в подобном порядке, чтобы впоследствие использовать его также как и в изначальной версии запроса.
1257
1258Создадим дополнительные индексы для выборки непосредственно ролей (так как в PRIMARY индексе при отсутствии выборки по префиксу {\it PersonID, GroupID, ModuleID}, исполнитель не сможет оптимально работать со столбцами {\it IsStudent} и {\it IsApprover}:\\
1259
1260\begin{verbatim}
1261CREATE INDEX WorkRoleIsStudentIndex ON WorkRole(PersonID, IsStudent);
1262CREATE INDEX WorkRoleIsApproverIndex ON WorkRole(PersonID, IsApprover);
1263\end{verbatim}
1264
1265		Чтобы не повлиять на текущую функциональность базы, все изначально имеющиеся в ней таблице редактировать не будем. Для работы же с этой вновь созданной таблицей создадим необходимые триггеры, которые изменяют данные внутри {\it WorkRole} основываясь на изменении данных в ``базовых'' для нее таблицах {\it Students} и {\it Approvers}.
1266		
1267		Перепишем ту часть запроса, которая некогда выполняла описанные выше действия, изменив порядок выполнения на работу с новой таблицей WorkRole, согласно Листингам ~\ref{lst:bigq_workrole_before} и ~\ref{lst:bigq_workrole_after}:\\
1268
1269\begin{lstlisting}[caption={основной запрос до внедрения таблицы WorkRole}, label={lst:bigq_workrole_before}]
1270SELECT GroupId, ModuleId, max(IsStudent) AS IsStudent, max(IsApprover) AS IsApprover 
1271	FROM ( 
1272		SELECT a11.GroupId, ModuleId, 1 AS IsStudent, 0 AS IsApprover 
1273			FROM Students as a11
1274			JOIN RelGroupsModules USING(GroupId) 
1275			WHERE PersonId = 1 
1276		UNION 
1277		SELECT GroupId, ModuleId, 0 AS IsStudent, 1 AS IsApprover 
1278			FROM Approvers as a9
1279			WHERE PersonId = 1 
1280		) as a10
1281	GROUP BY GroupId, ModuleId 
1282\end{lstlisting}
1283%~\ref{lst:}
1284
1285\begin{lstlisting}[caption={основной запрос после внедрения таблицы WorkRole}, label={lst:bigq_workrole_after}]
1286SELECT GroupId, ModuleId, IsStudent, IsApprover
1287	FROM WorkRole 
1288	WHERE PersonID = 1
1289	GROUP BY GroupId, ModuleId 
1290\end{lstlisting}
1291%~\ref{lst:}   		
1292
1293
1294%\begin{table}
1295%    \caption {WorkRole}
1296%    \begin{tabular}{|l|}
1297%    \hline
1298%    Main query before                                                                                                                                                                                                                                                                                                                                                                                                      \\ \hline
1299%    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
1300%    Main query after                                                                                                                                                                                                                                                                                                                                                                                                       \\ \hline
1301%    SELECT GroupId, ModuleId, IsStudent, IsApprover\\	FROM WorkRole \\    WHERE PersonID = 1\\	GROUP BY GroupId, ModuleId                                                                                                                                                                                                                                                                                                  \\ \hline
1302%    \end{tabular}
1303%\end{table}
1304
1305		\bigskip
1306    		
1307    		{
1308		        \section{ТЕСТИРОВАНИЕ}
1309    		}   
1310    		
1311    		{
1312		        \subsection{Сравнение производительности}
1313    		}
1314    		
1315    		На данный момент имеется оптимизированный по описанным выше пунктам запрос. Некоторые изменения в ходе работы коснулись и самой базы данных. Она также была оптимизирована.
1316    		
1317    		Все проводимые оптимизации не затрагивали результат выборки основоного запроса. Так что исходный запрос и получившийся в итоге, оптимизированный, можно считать идентичными по своей функциональности.
1318    		
1319		Взглянем на план выполнения нового запроса
1320		
1321		%вставить новый эксплэин
1322		<здесь новый EXPLAIN>
1323		
1324    		Вот что изменилось по сравнению с предыдущим выполнением EXPLAIN'а:
1325    			\begin{itemize}
1326    				\item[] Остались 2 полнотекстовых сканирования, вместо 6 первоначальных
1327    				\item[] Убрана неиспользуемая временная выборка, дублирующая подзапрос ({\it id = 4})
1328    				\item[] Остались лишь 7 подзапросов вместо 10 первоначальных
1329    				\item[] Перва выборка имеет максимально быстрый (после ({\it type=system}) тип объединения, а длина используемого ключа сокращена
1330    				\item[] Уменьшено общее количество участвующих в запросе строк
1331    			\end{itemize}
1332    			
1333		Согласно результатам EXPLAIN'ов, запрос, действительно, стал работать оптимальнее. В качестве результата представим таблицу профилирования запросов инструментом MySQL Profiler, которая не учитывает время подключения к базе данных, время ожидания открытия и закрытия таблиц, завершения других процессов и т.д., а показывает идеализированное ``чистое'' время выполнения:
1334		
1335\begin{table}[h]
1336    \caption {test1profiling}
1337    \begin{tabular}{|c|c|c|}
1338    \hline
1339    Тип действия         & Тайминг исходного запроса & Тайминг полученного запроса\\ \hline
1340     executing          & 0.000001      & 0.000001        \\
1341    Sending data        & 0.000005      & 0.000005        \\
1342    executing           & 0.000001      & 0.000001        \\
1343    Sending data        & 0.000005      & {\bf 0.000016 }       \\
1344    executing           & 0.000001      & 0.000001        \\
1345    Sending data        & 0.000005      & 0.000006        \\ \hline
1346    …                   & …             & …               \\ \hline
1347    Sending data        & 0.000006      & {\bf 0.000035  }      \\
1348    executing           & 0.000001      & 0.000002        \\
1349    Sending data        & {\bf 0.005742}      & 0.000046        \\
1350    executing           & 0.000003      & 0.000001        \\
1351    Sending data        & {\bf 0.031268}      & 0.023095        \\
1352    Creating sort index & {\bf 0.014082}      & 0.013395        \\
1353    end                 & 0.000011      & 0.000012        \\ \hline
1354    …                   & …             & …               \\ \hline
1355    query end           & 0.000013      & 0.000013        \\
1356    removing tmp table  & 0.000175      & {\bf 0.000201}        \\
1357    closing tables      & 0.000002      & 0.000004        \\
1358    removing tmp table  & 0.000004      & 0.000003        \\
1359    closing tables      & 0.000001      & 0.000005        \\
1360    freeing items       & 0.000127      & {\bf 0.000139}        \\
1361    cleaning up         & 0.000017      & 0.000018        \\ \hline
1362    \end{tabular}
1363\end{table}
1364		
1365    		Опустим бОльшую часть таблицы резульата, оставив только начало и наиболее отличительные моменты. Общее время выполнения первого запроса составляет около 0.06 секунды согласно профайлеру. Время выполнения второго, оптимизированного запроса составляет порядка 0.04 секунды. Как видно из результата, наибольший выигрыш происходит при отправке меньшего количества данных на сортировку - отправка отрабатывает почти на треть быстрее. Одна из введенных нами оптимизаций позволила не отправлять также значительную часть данных, в отличие от первого запроса, благодаря чему мы также получили выигрыш в производительности. Однако, среднее время ``уборки'' после запроса незначительно выросло, как следует из нижней части результата - действий после завершения формирования выборки.
1366    		При сравнении результатов запросов в SQLite и MySQL ситуация аналогичная с точностью до затрат по подключению непосредственно к базам данных (из утилиты основанной на ADO.Net). Это объясняется нивелированием преимуществ одной СУБД над другой за счет оптимизации общей их части - механики выполнения запросов, которая по большей части идентична. Результат закономерен.
1367    		
1368    		Выполним ``проверку статусов'' SELECT запросом \verb|SESSION STATUS LIKE `Select\%'|:
1369    		
1370\begin{table}[h]
1371    \caption {test2selects}
1372    \begin{tabular}{|c|c|c|}
1373    \hline
1374    Тип призведенного действия         & Исходный запрос & Новый запрос \\ \hline
1375    Select\_full\_join          & 1      & 0        \\
1376    Select\_range\_check           & 0      & 0        \\
1377    Select\_range           & 0      & 0        \\
1378    Select\_scan        & 6      & 2        \\ \hline
1379    \end{tabular}
1380\end{table}
1381
1382	Эти результаты мы могли наблюдать через EXPLAIN. Общее количество сканирований сократилось.
1383	
1384	Выполним проверку создания временных таблиц \verb|SESSION STATUS LIKE `Created_tmp\%'|:
1385
1386\begin{table}[h]
1387    \caption {test3temporaries}
1388    \begin{tabular}{|c|c|c|}
1389    \hline
1390    Тип произведенного действия         & Исходный запрос & Новый запрос \\ \hline
1391    Created\_tmp\_files          & 4      & 4        \\
1392    Created\_tmp\_tables          & 12      & 8        \\ \hline
1393    \end{tabular}
1394\end{table}
1395
1396    		Из результата этой выборки также видно уменьшение количества временно созданных таблиц с 12 до 8.
1397    		
1398    		{
1399		        \subsection{Оценка оптимизации}
1400    		}
1401    		
1402		Оптимизация, выполненная над базой не включала в себя масштабные изменения. Структура базы практически не затронута. Все изначально существовавшие таблицы сохранены, представления сохранены. Триггеры адаптированы и сохранены. Рефакторинг структуры базы не был произведен ввиду необходимости сохранить ее функционирующее состояние. 
1403		
1404		Изначально спроектированная база данных достаточно нормализована, не содержит избыточных данных, многозначных и многоцелевых столбцов. На данный момент в базе данных присутствует сравнительно небольшой объем данных. Основываясь на всем этом можно сделать вывод, что имеющаяся база данных в рефакторинге не нуждается, по крайней мере на данный момент.
1405		
1406    		Переход с SQLite на MySQL является спорным моментом, так как одним из плюсов СУБД SQLite является ее простота. Большинство преимуществ MySQL над SQLite в ходе данной работы задействованы не были и в целом являются преимуществами в специфических условиях. 
1407    		
1408    		
1409    		\clearpage
1410
1411    		{
1412        		\section{ЗАКЛЮЧЕНИЕ}
1413    		}
1414		
1415		В ходе работы над курсовым проектом было изучено поведение MySQL при обработке SQL запросов. Протестирована механика многих оптимизаций, которые могут быть применены ко входной базе данных. Большинство этих оптимизаций было осуществлено. Были оценены улучшившиеся показатели работы, были произведены тесты производительности полученной системы.\\
1416		
1417		{
1418		        \subsection{Возможные дальнейшие улучшения}
1419    		}
1420
1421    		Данная работы не может быть названа полностью законченной, так как абсолютно любую систему можно так или иначе улучшить. Вопрос состоит лишь в том, насколько необходимо ``улучшение'', и не приведет ли оно к противоположному результату в другом месте. Так, оптимизация конкретной базы данных в рамках работы шла ``с оглядкой'' на выполнение конкретного моделируемого запроса. \\
1422    		
1423    		При возникновении подобной необходимости в будущем, работа может быть продолжена и доведена до необходимиого состояния с учетом будущих потрбностей и возможностей.
1424   
1425   
1426   \newpage
1427   	<bibtexсписок литературы>
1428   
1429    \end{document}