Параллельная сортировка

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

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

На практике скорость сортировки ограничивается временем сканирования данных из таблиц. Это ограничение в значительной мере снимается применением PDQ-алгоритмов параллельного сканирования.

Параллельное сканирование

Операции построения индексов, соединений, подготовки отчетов, необходимые в большинстве приложений, требуют сканирования больших объемов данных, если в них участвуют большие таблицы. Технология PDQ позволяет существенно снизить время сканирования. Если таблица фрагментирована, то секции сканируются параллельно, при этом выигрыш во времени примерно пропорционален числу дисков. При сканировании последовательных таблиц или индексов применяется конфигурация сервера OnLine DS с опережающим чтением - время отклика сокращается за счет того, что чтение очередных страниц идет параллельно с обработкой уже прочитанных.

Параллельное построение индексов

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

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

Пример OLTP-запроса: Есть ли свободный номер в какой-либо берлинской гостинице на 8-е декабря?

Пример DSS-запроса: Каковы будут затраты на реализацию стратегии X охраны здоровья сотрудников по сравнению со стратегией Y с учетом демографического профиля компании? Зависит ли эффективность стратегии от региона?

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

Ответы на запросы первого типа должны выдаваться практически мгновенно, запросы второго и третьего типов могут обслуживаться достаточно долго, но при отсутствии или малой интенсивности OLTP-приложений желательно получать ответы на DSS-запросы максимально быстро.

Технология PDQ используется в основном для быстрого выполнения DSS-запросов и пакетных приложений. Если ее применение ничем не ограничено, то сильно распараллеленное выполнение нескольких сложных запросов приводит к недопустимому замедлению OLTP-приложений, выполняющихся на том же сервере. Управление степенью распараллеливания запросов и долей системных ресурсов, выделяемых для PDQ-обработки, в среде INFORMIX-OnLine DS осуществляется при помощи нескольких параметров конфигурирования и переменных окружения, значения которых динамически настраиваемы. Значения этих параметров и переменных устанавливаются системными администраторами и, в определенной степени, прикладными программистами и пользователями.

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

Таким образом, режим работы сервера INFORMIX-OnLine DS может динамически изменяться. В часы наиболее активной работы приложений OLTP запросы DSS выполняются без распараллеливания (когда для каждого запроса создается всегда только один поток класса CPU) или с невысокой степенью распараллеливания. В остальное время, или на серверах, где приложения OLTP отсутствуют, устанавливается максимальная степень использования PDQ.

Собственно распределением ресурсов и приоритетов в соответствии с установленными значениями занимается специальная компонента сервера OnLine DS - Менеджер выделения памяти (Memory Grant Manager - MGM). Менеджер выделения памяти регулирует объем системных ресурсов, потребляемых PDQ-заданиями, а также:

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

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

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

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

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