ИНТЕГРАЦИЯ МЕТОДОВ МАШИННОГО ОБУЧЕНИЯ В ПЛАНИРОВЩИК SQL-ЗАПРОСОВ

В настоящее время базы данных являются неотъемлемой составляющей практически любой информационной системы и используются во многих областях: документальные базы данных в базах органов управления и власти; базы данных учёта продукции всех производственных сфер хозяйствования; базы данных транспортных систем; базы данных для хранения статистических данных и многие другие. [2]

Тенденции последних лет показывают стремительный рост объёмов данных самого различного происхождения и назначения. В процессе этого роста операции, выполняемые над данными, хранящимися в формализованном виде в базах данных, остаются неизменными. Исходя из этого, можно говорить о значительном росте необходимой для выполнения этих операций производительной мощности (особенно если речь идёт о коррелированных вложенных запросах).

SQL, представляет собой язык декларирования операций, что выполняются над данными, и оставляет выбор метода исполнения этих операций системе управления базами данных (СУБД). Так, при отборе кортежей из отношения, удовлетворяющих определённому условию, можно прибегнуть к последовательному проходу по всем кортежам отношения или использовать индексы. В случае объединения в запросе нескольких отношений, количество вариантов их объединения соразмерно количеству различающихся корневых двоичных деревьев, что имеют данные отношения в качестве листьев. [5]

Для повышения эффективности выполнения запроса необходимо выбрать план с наименьшими затратами ресурсов. В данном случае речь идёт о выборе метода выполнения запроса и способа объединения отношений (если это необходимо, но зачастую это именно так), иначе говоря – вершины плана. От правильности выбора плана зависит длительность выполнения запроса при прочих равных условиях.

Поиск самого эффективного плана представляет собой двухэтапный процесс:

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

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

Осуществление такой предикативной оценки плана выполняется пошагово. Прежде всего, для каждой его вершины находится предполагаемое число кортежей, что будут отобраны данным запросом, далее, основываясь на полученных данных, производится оценка стоимости выполнения каждой вершины и всего плана в целом. Так, при наличии числа записей, выбранных в каждой вершине, возможно вычислить ресурсоёмкость выполнения каждой вершины. Например, сортировка требует выполнения около  операций сравнения, где x – число кортежей для сортировки. При известном значении ресурсоёмкости операции сравнения возможно рассчитать ресурсоёмкость операции сортировки. Аналогичным образом рассчитывается ресурсоёмкость прочих операций в вершинах плана.

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

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

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

Данный факт и является узким местом планировщика выполнения запросов.

Для поиска закономерностей в наборе объектов, где объект – это вершина плана, целесообразно использовать методы машинного обучения. По набору простых ограничений на данные система машинного обучения будет генерировать некоторые коэффициенты совокупных условий, которые будут учтены в дальнейших расчётах. [3]

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

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

Планировщик запросов IBM System R, послуживший основой практически всех серьёзных реализаций СУБД, существующих на сегодняшний день, ведёт каталог статистики, содержащий характеристики таблиц и приближённое распределение значений внутри столбцов. Существенным недостатком этого планировщика является низкая частота адаптивности: статистические данные обновляются раз в день, а то и реже. Как следствие – к моменту анализа статистических данных последние могут уже потерять актуальность и не отражать настоящего положения вещей, что приведёт к неверному прогнозу.

Чунг-Мин-Чен и Ник Роуссопоулос предложили концепцию адаптивной селективности для усовершенствования планировщика запросов за счёт промежуточного сбора статистики при обработке запроса.

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

Таким образом, решается проблема актуальности статистических данных для осуществления расчётов системой машинного обучения. [6]

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

Заключение

В условиях стремительно растущей потребности в эффективных способах хранения и манипуляций с большими объёмами данных поиск новых решений является необходимым.

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

Список литературы:

1. Григорьев Ю. А., Остриков С. П. Оценка времени выполнения запросов с коррелированными подзапросами и операциями агрегирования // Вестник Московского государственного технического университета им. Н.Э. Баумана. – 2006. – №1. С. 1-12.
2. Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. – М.: Издательский дом “Вильяме”, 2005. – 1328 с.
3. Маркин С.Д., Ступина М.В. Машинное обучение: шаг навстречу будущему и сдерживающие факторы // Технические науки - от теории к практике: сб. ст. по матер. LXIX междунар. науч.-практ. конф. № 4(64). – Новосибирск: СибАК, 2017. – С. 26-32.
4. Мирошниченко Г. А. Реляционные базы данных: практические приёмы оптимальных решений. – СПб.: БХВ-Петербург, 2005. – 400 с.
5. Фиайли Крис, SQL: Руководство по изучению языка: Пер. с англ. – М.: ДМК Пресс, 2010. – 454 с.
6. Chung-Min Chen, Nick Roussopoulos. Adaptive selectivity estimation using query feedback // Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data. – Minneapolis: 1994. – P. 161-172.