Сортировка и группировка
Сортировка
16
Авторские права
© Postgres Professional, 2019–2024
Авторы: Егор Рогов, Павел Лузанов, Павел Толмачев, Илья Баштанов
Фото: Олег Бартунов (монастырь Пху и пик Бхрикути, Непал)
Использование материалов курса
Некоммерческое использование материалов курса (презентации,
демонстрации) разрешается без ограничений. Коммерческое
использование возможно только с письменного разрешения компании
Postgres Professional. Запрещается внесение изменений в материалы
курса.
Обратная связь
Отзывы, замечания и предложения направляйте по адресу:
Отказ от ответственности
Компания Postgres Professional не несет никакой ответственности за
любые повреждения и убытки, включая потерю дохода, нанесенные
прямым или непрямым, специальным или случайным использованием
материалов курса. Компания Postgres Professional не предоставляет
каких-либо гарантий на материалы курса. Материалы курса
предоставляются на основе принципа «как есть» и компания Postgres
Professional не обязана предоставлять сопровождение, поддержку,
обновления, расширения и изменения.
2
Темы
Получение отсортированных данных
Сортировка в памяти
Внешняя сортировка
Инкрементальная сортировка
Сортировка в параллельных планах
Сортировка при построении индекса
Оконные функции с сортировкой
3
Индексный доступ (В-дерево)
возвращает отсортированный набор строк
Последовательный доступ (Seq Scan)
возвращает неупорядоченный набор строк
необходима дополнительная операция сортировки
Получение данных
Как уже было сказано ранее, индексный доступ (при использовании
B-дерева) позволяет сразу же получить набор строк, отсортированный
по ключам индексирования.
Но что делать, если сортировка требуется по полям, для которых нет
индекса? В этом случае серверу приходится сначала получить данные
из таблицы с помощью последовательного сканирования, а затем
выполнить дополнительную операцию сортировки.
5
Быстрая сортировка (quick sort)
Частичная пирамидальная сортировка (top-N heapsort)
когда нужна только часть значений
Сортировка в памяти
В идеальном случае набор строк, подлежащий сортировке, целиком
помещается в память, ограниченную параметром work_mem. В этом
случае все строки просто сортируются алгоритмом быстрой
сортировки (quick sort) и результат возвращается родительскому узлу.
Если нужно получить лишь несколько первых строк отсортированного
набора (при использовании предложения LIMIT), сортировать весь
набор не обязательно. В этом случае сервер может применить
частичную пирамидальную сортировку (top-N heapsort), которая также
выполняется в оперативной памяти.
7
work_mem
Внешняя сортировка
namealbum_id
5
1
2
1
2
A Day in the Life
All Together Now
Another Girl
All You Need Is Love
Act Naturally
3 Across the Universe
5
1
A Day in the Life
All Together Now
quicksort
2 Another Girl
5
1
A Day in the Life
All Together Now
2 Another Girl
Если набор строк велик, он не поместится в память целиком. В таком
случае используется алгоритм внешней сортировки.
Набор строк читается в память, пока есть возможность, затем
сортируется и записывается во временный файл.
8
work_mem
Внешняя сортировка
namealbum_id
5
1
2
1
2
A Day in the Life
All Together Now
Another Girl
All You Need Is Love
Act Naturally
3 Across the Universe
quicksort
1
2
All You Need Is Love
Act Naturally
3 Across the Universe
1
2
All You Need Is Love
Act Naturally
3 Across the Universe5
1
A Day in the Life
All Together Now
2 Another Girl
temp_file_limit
Эта процедура повторяется столько раз, сколько необходимо, чтобы
записать все данные в файлы, каждый из которых по отдельности
отсортирован.
Напомним, что общий размер временных файлов сеанса (не включая
временные таблицы) ограничен значением параметра temp_file_limit.
9
work_mem
Внешняя сортировка
1 All You Need Is Love
1 All Together Now
слияние
1
2
All You Need Is Love
Act Naturally
3 Across the Universe5
1
A Day in the Life
All Together Now
2 Another Girl
Далее несколько файлов (два или более) соединяются с сохранением
порядка строк.
Для соединения не требуется много места в памяти, достаточно
разместить по одной строке из каждого файла (как в примере на
слайде). Среди этих строк выбирается минимальная (максимальная)
и возвращается как часть результата, а на ее место читается новая
строка из того же файла. На практике строки читаются не по одной,
а пакетами, чтобы ускорить ввод-вывод.
Если оперативной памяти недостаточно, чтобы соединить сразу все
файлы, сначала соединяется часть файлов и результат записывается
в новый временный файл, затем происходит соединение этих новых
файлов и так далее.
Мы не обсуждаем здесь все детали реализации сортировки, с ними
можно ознакомиться в файле src/backend/utils/sort/tuplesort.c.
История развития способов сортировки в PostgreSQL хорошо описана
в презентации Грегори Старка «Sorting Through The Ages»:
синхронный перевод доклада на русский язык доступен на сайте
11
Incremental Sort
namealbum_id
1
1
2
3
5
All You Need Is Love
All Together Now
Another Girl
Across the Universe
A Day in the Life
2 Act Naturally
1
1
All Together Now
All You Need Is Love
уже
отсортировано
3
5
Across the Universe
A Day in the Life
Act Naturally2
Another Girl2
Pre-sorted Groups
Full-sort Groups
сортировка
по полю name
сортировка
по всем полям
Если набор данных требуется отсортировать по ключам K
1
... K
m
... K
n
и при этом известно, что набор уже отсортирован по первым m ключам,
можно не пересортировывать все данные заново. Достаточно разбить
набор данных на группы, имеющие одинаковые значения начальных
ключей K
1
... K
m
(значения таких групп следуют друг за другом), и затем
отсортировать отдельно каждую из групп по оставшимся ключам
K
m+1
... K
n
. Такой способ называется инкрементальной сортировкой.
Алгоритм обрабатывает относительно крупные группы строк отдельно,
а небольшие объединяет и сортирует полностью. Поскольку
сортируемые наборы данных уменьшаются, уменьшается и требование
к доступному объему памяти. Но увеличение количества наборов
приводит к росту накладных расходов.
Наборы могут обрабатываться как в оперативной памяти, так и на
диске — если не хватает объема work_mem.
Инкрементальная сортировка позволяет выдавать результаты уже
после обработки первой группы, не дожидаясь сортировки всего
набора.
Отключить использование инкрементальной сортировки можно
с помощью параметра enable_incremental_sort.
13
Узел Gather Merge сохраняет порядок сортировки
выполняет слияние данных, поступающих от дочерних узлов
В параллельных планах
Gather
Merge
Sort
Sort Sort
Parallel Seq Scan Parallel Seq Scan Parallel Seq Scan
Сортировка может участвовать в параллельных планах. Каждый
рабочий процесс сортирует свою часть данных и передает результат
вышестоящему узлу, который собирает данные в единый набор.
Но узел Gather для этого не годится, поскольку он выдает результат
в том порядке, в котором строки поступают от рабочих процессов.
Поэтому в таких планах используется узел Gather Merge, сохраняющий
порядок сортировки поступающих строк. Для этого он реализует
алгоритм слияния, объединяя несколько отсортированных наборов
в один.
15
Построение B-дерева
Используется сортировка
сначала все строки сортируются
затем строки собираются в листовые индексные страницы
ссылки на них собираются в страницы следующего уровня
и так далее, пока не дойдем до корня
Может выполняться параллельно
max_parallel_maintenance_workers
Ограничение
maintenance_work_mem, так как операция не частая
При построении индекса (речь идет про B-дерево) сервер мог бы
добавлять записи в пустой индекс по одной, обрабатывая
последовательно строки таблицы. Но такой способ крайне
неэффективен.
Поэтому при создании и перестроении индекса используется
сортировка: все строки таблицы сортируются, и формируются записи,
которые раскладываются по листовым индексным страницам. Затем
достраиваются верхние уровни дерева, состоящие из ссылок на
элементы страниц нижележащего уровня, до тех пор, пока на
очередном уровне не получится одна страница — она и будет корнем
дерева.
Сортировка устроена точно так же, как рассматривалось выше. Однако
размер памяти ограничен не work_mem, а maintenance_work_mem,
поскольку операция создания индекса не слишком частая и имеет
смысл выделить для нее больше памяти.
Построение индекса может выполняться параллельно. Количество
рабочих процессов выбирается так же, как и при выполнении
параллельных запросов (в зависимости от размера таблицы), но
ограничено значением параметра max_parallel_maintenance_workers.
16
Окно определяет агрегируемую выборку для каждой строки
В отсортированном наборе границы рамки могут двигаться
1 2 3 4 5 1 2 3 4 5
1 2 3 4 5 1 2 3 4 5
1 2 3 4 5 1 2 3 4 5
1 2 3 4 5 1 2 3 4 5
1 2 3 4 5 1 2 3 4 5
Оконные функции
рамка
OVER () OVER (ORDER BY)
окно
Использование сортировки в оконных функциях имеет особенности.
В отличие от обычных агрегатных функций, оконные функции
вычисляются для каждой строки набора, не уменьшая его размер.
После имени функции в предложении OVER указывается окно,
определяющее набор строк, которую должна обработать оконная
функция в каждой строке набора. Такая выборка называется рамкой.
Если окно указано как OVER(), то рамка одинакова для каждой строки
и состоит из всех строк набора.
18
Итоги
Сортировка используется при выполнении запросов
и для построения B-деревьев
Существуют разные способы реализации сортировки
в памяти
внешняя (создаются временные файлы)
инкрементальная
Наличие индексов может позволить избежать сортировки
19
Практика
1. Какой план будет выбран для следующего запроса:
SELECT *
FROM flights
ORDER BY scheduled_departure;
Изменится ли план выполнения, если увеличить значение
work_mem до 32 Мбайт?
2. Создайте индекс по столбцам passenger_name и passenger_id
таблицы билетов (tickets). Потребовался ли временный файл
для выполнения этой операции?
2. Включите журналирование использования временных файлов,
установив значение параметра log_temp_files в ноль.
