Роль процесса оптимизации в работе систем баз данных

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

Оптимизация является одной из сильных сторон реляционных баз данных [1], так как производится автоматически на довольно высоком семантическом уровне. Здесь оптимизатор (программа, выполняющая оптимизацию) представляет собой некий аналог искусственного интеллекта, а именно экспертной системы [2]. Это обусловлено тем, что в оптимизаторе «реализованы знания и опыт лучших из лучших программистов», благодаря чему этими знаниями и опытом могут воспользоваться менее квалифицированные специалисты. В противовес вышесказанному в нереляционных базах данных возможна лишь ручная оптимизация, при которой пользователь сам определяет, последовательность каких низкоуровневых процедур будет соответствовать определенному запросу. Данный подход является большим минусом подобных систем баз данных, так как любое неверно принятое пользователем решение не может быть исправлено системой [1].

Для того, чтобы наяву убедиться в том, что автоматическая оптимизация жизненно необходима системам баз данных, рассмотрим следующий пример. Пусть нам необходимо выбрать номера групп, в которых обучается хотя бы один отличник за все время обучения. Всего есть 100 групп и 5000 студентов, причем только 50 из них являются отличниками. Информация о группах хранится в переменной отношения A, а информация о студентах (для каждого студента проставлен его средний балл по итогам всех аттестаций за все время обучения) — в переменной отношения B, причем первичный ключ переменной отношения A является внешним по отношению к переменной отношения B. Имеется два возможных варианта выполнения поставленной задачи:

1. При использовании первого из них сначала произойдет соединение переменных отношения A и B по внешнему ключу, для выполнения которого потребуется найти для каждой из 5000 записей о студентах одну соответствующую запись из ста об учебных группах. В результате соединения будет получена новая переменная отношения (допустим, C) из 5000 соединенных кортежей, для хранения которой, вполне возможно, может даже не хватить места в оперативной памяти, из-за чего придется записать эту переменную отношения C на диск. Затем будет проведена выборка тех кортежей, в которых атрибут со значением среднего балла студента за все время обучения будет равен 5, но для проведения выборки потребуется опять загрузить переменную отношения C в оперативную память. Так как отличников всего 50, то новая полученная переменная отношения сможет поместиться в оперативной памяти. После этого будет проведена последняя операция, в ходе которого будет сформирован список групп, в которой обучаются эти отличники.
2. При использовании второго из них сначала будет проведена операция выборки, в результате которой будет сформирована переменная отношения, содержащая лишь записи о 50 студентах-отличниках. Затем эта переменная отношения будет соединена с переменной отношения, хранящей сведения об учебных группах, по внешнему ключу, причем новая переменная отношения также будет содержать 50 кортежей. Последний шаг с формированием списка групп полностью идентичен последнему шагу из первого варианта.

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

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

1. Для каждой переменной отношения:

– Кардинальность — количество кортежей [3];

– Количество страниц, занятых переменной отношения;

– Доля пространства, занимаемого переменной отношения;

2. Для каждого атрибута каждой переменной отношения:

– Количество различных значений атрибута;

– Второе наибольшее и второе наименьшие значения атрибута;

3. Для каждого индекса:

– Индикатор кластеризации (совпадает ли логический порядок значений ключа с порядком физического размещения);

– Количество листовых страниц в индексе;

– Количество уровней в индексе.

Именно эти данные помогают оптимизатору принять правильное решение о выполнении того или иного запроса. Но каков в целом алгоритм его действий?

Оптимизация любого запроса затрагивает следующие четыре стадии [1]:

1. Преобразование запроса во внутреннюю форму. На данной стадии запрос переводится в формат, удобный для машинной обработки, для чего удаляются различные внешние конструкции. Данная стадия является подготовительной — в ходе нее проводятся работы, необходимые на дальнейших этапах.
2. Преобразование запроса в каноническую форму. Оптимизация запроса на этом этапе все еще проходит в отрыве от данных и путей доступа к ним. Здесь происходит замена запроса эквивалентной ему канонической формой, представляющий собой некоторый более эффективный запрос. Это происходит из-за того, что любой запрос может быть сформирован как минимум десятком способов, многие из которых только из-за своей записи будут серьезно тормозить работу. Для выполнения этой стадии оптимизатор использует четко определенные законы преобразования.
3. Выбор потенциальных низкоуровневых процедур. На этой стадии во внимание принимаются все имеющиеся статистические показатели базы данных. Так, для каждого запроса, уже представленного в канонической форме, определяется серия операций более низкого уровня, для каждой из которых, в свою очередь, имеется набор процедур реализации еще более низкого уровня. С каждой такой процедурой реализации связана параметризованная формула стоимости, с помощью которой можно определить затраты, связанные с выполнением данной процедуры. В итоге происходит так называемый выбор пути доступа, в ходе которого для каждой операции в запросе подбирается несколько вариантов процедур реализации.
4. Генерация различных планов вычисления запроса и выбор плана с минимальными затратами. На этой стадии на основании выбора пути доступа формируются потенциальные планы запросы, из которых выбирается тот, суммарная стоимость процедур реализации которого является наименьшей.

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

Литература:

1. Дейт, К.Дж. Введение в системы баз данных, 8-е издание: Пер. с англ. / К.Дж. Дейт. — М.: Издательский дом «Вильямс», 2008. — 1328 с.: ил. — Парал. тит. англ.
2. Гаврилова, Т. А. Базы знаний интеллектуальных систем / Т. А. Гаврилова, В. Ф. Хорошевский. — СПб.: Питер, 2001. — 384 с.: ил.
3. Краморенко, Н. В. Базы данных. / Н. В. Краморенко. — Дальневосточный государственный университет, Тихоокеанский институт дистанционного образования и технологий. Режим доступа: https://imcs.dvfu.ru/struc/kkt/inform/studies/BD/dvgu085.pdf (дата обращения: 10.11.2016).