Объясняя необъяснимое. Часть 3
В рамках подготовки к конференции PG Day’16 мы продолжаем знакомить вас с интересными аспектами PostgreSQL. И сегодня предлагаем вам перевод третьей статьи из серии об explain.
В предыдущих постах этой серии я писал о том, как интерпретировать отдельно взятую строку в выводе анализа explain, его структуру, а также описал базовые операции получения данных (узлы дерева explain).
Сегодня мы перейдем к более сложным операциям.
Function scan
По большому счету, это так просто, что нет особой необходимости что-то объяснять. Но так как эта операция будет использоваться в следующих примерах, я всё же напишу о ней немного.
Function Scan – очень простой узел. Он запускает функцию, которая возвращает набор записей (recordset), – вот и всё. Он не будет запускать функции на подобие “lower()», а только те, которые потенциально вернут множество строк или столбцов. Когда функция вернет строки, они будут переданы в тот узел, который находится на уровень выше Function Scan в дереве плана, или клиенту, если Function Scan является корневым узлом.
Единственная дополнительная логика, которая здесь может возникнуть – это способность фильтровать полученные строки, как здесь:
Думаю, это довольно просто понять – sort берет выбранные записи и возвращает их отсортированными определенным образом.
Хоть это и просто, внутри скрывается интересная логика. Для начала, если память, требующаяся для сортировки, будет больше, чем значение work_mem, то произойдет переключение на дисковую сортировку:
Обратите внимание на изменение Sort Method в примере выше.
Ещё одно дополнительное свойство заключается в том, что Sort может менять свой метод работы, если вызывается операцией Limit, как вот здесь:
Обычно для сортировки выбранного набора данных вам нужно обработать его целиком. Но Постгрес знает, что если вам нужно лишь небольшое количество строк, ему не надо сортировать весь набор данных, достаточно получить только первые значения.
В нотации Big O общая сортировка имеет сложность O(m * log(m)), но Top-N имеет сложность O(m * log(n)), где m – число строк в таблице, а n – количество возвращаемых строк. Важно знать, что этот способ сортировки также использует гораздо меньше памяти (в конце концов, ему не нужно собирать весь набор данных из отсортированных строк, пары строк вполне достаточно), так что он с меньшей вероятностью будет использовать медленный диск для временных файлов.
Limit
Я использовал limit неоднократно, потому что он очень прост, но всё же давайте его подробно обсудим. Операция limit запускает свою субоперацию и возвращает только первые N строк из того, что вернула субоперация. Обычно после этого она останавливает субоперацию, но в некоторых случаях (например, вызов функции pl/PgSQL), субоперация уже завершила свою работу к тому моменту, когда она вернула первую строку.
Как вы видите, использование лимита во втором случае привело к тому, что вложенная операция Seq Scan завершила свою работу сразу после нахождения двух строк.
HashAggregate
Эта операция в основном применяется в случаях, когда вы используете GROUP BY и какие-нибудь агрегаты, вроде sum(), avg(), min(), max() и других.
HashAggregate делает следующее: для каждой строки, которую получает, она находит «ключ» GROUP BY (в данном случае – relkind). Затем в хэше (ассоциативном массиве, словаре) помещает выбранную строку в корзину, обозначенную данным ключом.
После того как все строки были обработаны, она сканирует хэш и возвращает по одной строке для каждого значения ключа, совершая уместные расчёты по необходимости (sum, min, avg и так далее).
Важно понимать, что HashAggregate должен просканировать все строки прежде, чем сможет вернуть хотя бы одну.
Это значит, что если в плане есть и HashAggregate, и Sort, мы можем использовать вплоть до 2 * work_mem. Такой план легко получить:
В реальности один запрос может использовать work_mem много раз, поскольку work_mem – это ограничение для операции. Поэтому если в запросе применяется 1000 HashAggregate’ов и Sort’ов (и других операций, использующих work_mem), общее потребление памяти может быть очень высоким.
Hash Join / Hash
Поскольку мы только что обсуждали HashAggregate, будет логично перейти к Hash Join.
Эта операция, в отличие от предыдущей, имеет две субоперации. Одна из них всегда “Hash», а вторая – что-нибудь другое.
Как понятно из названия, Hash Join используется для объединения двух наборов записей. Например, как здесь:
Это работает следующим образом: сначала Hash Join вызывает “Hash», который в свою очередь вызывает что-нибудь ещё (в нашем случае – Seq Scan по pg_namespace). Потом Hash создает в памяти (или на диске – в зависимости от размера) хэш/ассоциативный массив/словарь со строками из источника, хэшированными с помощью того, что используется для объединения данных (в нашем случае это столбец OID в pg_namespace).
Конечно, у вас может быть много строк для указанного ключа join (не в этом случае, поскольку я объединяю с помощью первичного ключа, но в целом вполне вероятно, что у вас будет множество строк для одного хэш-ключа).
В нотации Perl, то вывод Hash будет примерно таким:
Поскольку оба субсканирования могут быть операциями любого типа, они могут оказаться фильтрами, сканированием индексов или тем, что вы себе можете вообразить.
Последнее, о чем стоит упомянуть в связи с Hash Join/Hash – это то, что операция Hash, так же, как Sort и HashAggregate будет использовать память вплоть до work_mem.
Hash Join / Hash
Поскольку мы говорим об объединениях, стоит обсудить Nested Loop. Пример:
Это очень интересный план, потому что он может выполнять выбранные операции неоднократно.
Так же, как и у Hash Join, у Nested Loop есть двое «потомков». Сначала она запускает “Seq Scan» (в нашем примере, сначала она запускает первый узел), а затем, для каждой возвращенной строки (всего 2 строки в нашем примере), она запускает вторую операцию (Index Scan по pg_attribute в нашем случае).
Вы могли заметить, что у Index Scan в фактической метаинформации стоит “loops=2″. Это значит, что данная операция запускалась дважды, и другие значения (строки, время) являются средними показателями для всех запусков.
Давайте рассмотрим следующий план из explain.depesz.com. Заметьте, что фактическое время выполнения для всех операций index scan для categories – от 0.002 до 0.003мс. Но общее время, затраченное на этот узел – 78.852мс, потому что это сканирование индекса выполнялось более 26k раз.
Merge Join
Еще один метод объединения данных называется Merge Join. Он используется, если объединяемые наборы данных отсортированы (или могут быть отсортированы с небольшими затратами) с помощью ключа join.
У меня нет готового наглядного примера, поэтому я создам его искусственно с помощью подзапросов, которые сортируют данные перед объединением:
Merge Join, как и другие объединения, запускает две субоперации (Sort и Materialize в данном случае). Так как они обе возвращают данные отсортированными и порядок сортировки такой же, как в операции объединения, Pg может сканировать оба набора данных, возвращенных субоперациями, одновременно и просто проверить, совпадают ли идентификаторы.
Модификаторы Hash Join / Nested Loop / Merge Join
Во всех примерах выше я продемонстрировал, что операция Join возвращает строку только когда получает строки с обеих сторон объединения.
Но так бывает не всегда. У нас могут быть левые, правые и полные (LEFT/RIGHT/FULL OUTER JOIN) внешние объединения, а также так называемые анти-объединения (anti-joins).
Во всех этих случаях логика проста: у нас есть две стороны объединения – левая и правая. И когда сторона упоминается в объединении, оно возвращает новую строку, даже если на другой стороне нет соответствующих строк.
Так происходит с запросами вроде этого:
Вся остальная информация для Hash Join/Merge Join и Nested Loop одинакова, есть только небольшое изменение в логике того, когда генерируется вывод строки.
Вся обработка происходит так же, как в предыдущих примерах.
Как в этом примере:
Здесь Pg выполнил правую сторону (Index Scan по pg_attribute), захэшировал её, а затем выполнил левую сторону (Seq Scan по pg_class), возвращая только те строки, где не было вхождений в Hash для данного pg_class.oid.
Materialize
Эта операция уже была продемонстрирована в примере для Merge Join, но она может быть полезна и в других случаях.
У psql есть множество внутренних команд. Одна из них — \dTS, которая составляет список всех системных типов данных. Внутренне \dTS запускает этот запрос:
Для удобства просмотра я также загрузил этот план на explain.depesz.com.
Заметьте, что операция #9 – это Materialize. Почему?
Materialize вызывается Nested Loop Left Join – операцией #2. Мы знаем, что Nested Loop заставляет выбранную операцию выполняться многократно, в данном случае – 87 раз.
Правая часть объединения – Seq Scan по pg_namespace. Так что, теоретически, Постгрес должен выполнить последовательное сканирование по pg_namespace 87 раз. Если учесть, что единичное последовательное сканирование этой таблицы занимает 0.003мс, мы можем ожидать, что общее время будет составлять
Но Постгрес поступает умнее. Он понимает, что будет менее затратно просканировать таблицу один раз и построить в памяти образ всех её строк. Тогда в следующий раз не нужно будет сканировать таблицу, проверять информацию о видимости, парсить страницы данных. Он просто возьмет данные из памяти.
Благодаря этому общее время на всё (однократное чтение таблицы, подготовка образа данных в памяти и сканирование этого образа 87 раз) составило 0.087мс.
Вы можете сказать: «Хорошо, но почему merge join использовал materialize раньше, он ведь просто выполнял одно сканирование?» Давайте вспомним план:
Да, он запускался всего один раз. Проблема в том, что источник данных для Merge Join должен отвечать нескольким критериям. Некоторые из них очевидны (данные должны быть отсортированы), а другие менее очевидны, поскольку являются более техническими (данные должны быть просматриваемыми вперед и назад).
Из-за этих не слишком очевидных критериев Постгресу иногда приходится применять Materialize к данным, приходящим из источника (в нашем случае из Index Scan), чтобы у него были все необходимые возможности, когда дело дойдет до их использования.
Короче говоря, Materialize получает данные из нижележащей операции и размещает их в памяти (или частично в памяти), чтобы ими можно было быстрее воспользоваться, или добавляет им дополнительные свойства, которые предыдущая операция не предоставляет.
На сегодня это всё. Я думал, что на этом закончу, но есть ещё много операций, которые стоит описать, так что в этой серии будет ещё как минимум два поста (оставшиеся операции и статистическая информация).
Сортировка данных для преобразований «Слияние» и «Соединение слиянием»
В службах Службы Integration Servicesдля преобразований «Слияние» и «Соединение слиянием» необходимы отсортированные входные данные. Входные данные должны быть отсортированы физически, а параметры сортировки должны быть установлены на выходы и выходные столбцы источника или вышестоящего преобразования. Если параметры сортировки определяют, что данные отсортированы, но данные в действительности не отсортированы, операция слияния или соединения слиянием может дать непредвиденные результаты.
Сортировка данных
Сортировку данных можно выполнить одним из следующих способов.
В источнике — в инструкции, с помощью которой загружаются данные, — использовать предложение ORDER BY.
В потоке данных преобразование «Сортировка» должно предшествовать преобразованию «Слияние» или «Соединение слиянием».
Если данные являются строковыми, то и преобразование «Слияние», и преобразование «Соединение слиянием» ожидают, что строковые значения отсортированы с использованием параметров сортировки Windows. Чтобы строковые значения передавались преобразованиям «Слияние» и «Соединение слиянием», отсортированным с помощью параметров сортировки Windows, примените следующую процедуру.
Чтобы передавались строковые значения, отсортированные с помощью параметров сортировки Windows
Используйте преобразование «Сортировка» для сортировки данных.
Преобразование «Сортировка» использует параметры сортировки Windows для упорядочения строковых значений.
Настройка параметров сортировки данных
Есть два важных свойства сортировки, которые необходимо задать для источника или вышестоящего преобразования, которые предоставляют данные для преобразования «Слияние» или «Соединение слиянием».
Свойство IsSorted выхода показывает, были ли данные отсортированы. Это свойство должно иметь значение True.
Установка свойства IsSorted в значение True не приводит к сортировке данных. Это свойство только указывает компонентам нисходящего потока, что данные раньше были отсортированы.
Свойство SortKeyPosition выходных столбцов показывает, отсортирован ли столбец, порядок сортировки и последовательность, в которой сортируется несколько столбцов. Это свойство должно быть задано для каждого столбца отсортированных данных.
При сортировке данных с помощью преобразования «Сортировка» это преобразование задает оба свойства требуемым образом для преобразования «Слияние» или «Соединение слиянием». То есть преобразование «Сортировка» задает для свойства IsSorted своего выхода значение True и задает свойство SortKeyPosition своих выходных столбцов.
Однако если не отсортировать данные с помощью преобразования «Сортировка», то придется задавать эти свойства вручную на источнике или в вышестоящем преобразовании. С помощью следующей процедуры можно вручную настроить эти свойства на источнике или в вышестоящем преобразовании.
Задание атрибутов сортировки вручную на источнике или в компоненте преобразования
Чтобы открыть пакет, дважды щелкните его в обозревателе решений.
Найдите на вкладке Поток данных соответствующий источник или вышестоящее преобразование или перетащите его из области элементов в область конструктора.
Щелкните компонент правой кнопкой мыши и выберите пункт Показать расширенный редактор.
Щелкните Вывод и задайте для свойства IsSorted значение True.
Разверните элемент Выходные столбцы.
Щелкните столбец, который необходимо обозначить как отсортированный, и установите для его свойства SortKeyPosition отличное от нуля целое число, следуя следующим правилам.
Целое число должно представлять числовую последовательность начиная с 1 с добавлением по единице.
Положительные целые значения соответствуют возрастающему порядку сортировки.
Отрицательные целые значения соответствуют убывающему порядку сортировки. Если задано отрицательное целое число, положение столбца в последовательности сортировки будет определять абсолютное значение этого числа.
Значение 0 указывает на то, что столбец не отсортирован. Чтобы выходные столбцы не участвовали в сортировке, задайте значение 0.
В качестве примера настройки свойства SortKeyPosition рассмотрите приведенную ниже инструкцию Transact-SQL, которая загружает данные в источник.
SELECT * FROM MyTable ORDER BY ColumnA, ColumnB DESC, ColumnC
В этой инструкции свойство SortKeyPosition задается для каждого столбца следующим образом.
Задайте для свойства SortKeyPosition столбца ColumnA значение 1. Это показывает, что столбец ColumnA является первым при сортировке, а сортировка производится по возрастанию.
Задайте для свойства SortKeyPosition столбца ColumnB значение 2. Это показывает, что столбец ColumnB является вторым при сортировке, а сортировка производится по убыванию.
Задайте для свойства SortKeyPosition столбца ColumnC значение 3. Это показывает, что столбец ColumnC является третьим при сортировке, а сортировка производится по возрастанию.
Повторите шаг 8 для каждого отсортированного столбца.
Нажмите кнопку ОК.
SQL-Ex blog
Новости сайта «Упражнения SQL», статьи и переводы
Merge join (соединения слиянием)
Merge Joins
Merge Joins (соединения слиянием) теоретически являются самыми быстрыми физическими операторами соединения, однако они требуют, чтобы данные обоих входов были отсортированы.
Базовый алгоритм работает следующим образом: SQL Server сравнивает первые строки обоих отсортированных входов. Затем сравнение продолжается со следующими строками второго входа до тех пор, пока значения соответствуют значению первого входа.
Это эффективно, поскольку в большинстве случаев SQL Server не придется возвращаться и читать неоднократно одни и те же строки. Исключение имеет место, когда существуют дубликаты сравниваемых значений в обеих входных таблицах (или, точнее, когда SQL Server не имеет метаданных, которые бы сообщали, что в обеих таблицах отсутствуют дубликаты) и SQL Server вынужден выполнять соединение слиянием типа многие-ко-многим.
Соединение многие-ко-многим вынуждает SQL Server записывать любые дублирующиеся значения во второй таблице в рабочую таблицу в базе tempdb и проводить сравнения там. Если эти дублирующиеся значения также дублируются в первой таблице, то SQL Server будет сравнивать значения из первой таблицы со значениями, хранящимися в рабочей таблице.
Что показывают нам соединения слиянием?
Знание механизма выполнения merge join позволяет нам понять, что думает оптимизатор о наших данных и восходящих потоках данных от операторов соединения. Это дает нам возможность сосредоточиться на настройке производительности.
ЗАМЕЧАНИЕ. Всегда имеются исключения из правил. Merge join имеет самый быстрый алгоритм, поскольку каждую строку из входных источников данных требуется прочитать только один раз. Однако возможности оптимизации, имеющие место в других операторах соединения, могут при определенных обстоятельствах дать лучшую производительность.
Например, внешняя таблица с единственной строкой и индексированной внутренней таблице при использовании nested loops join (соединение вложенными циклами) превзойдет merge join при тех же условиях за счет оптимизации внутренних циклов:
Также могут быть ситуации, когда входы с множеством дубликатов записей, требующие использования рабочей таблицы, могут оказаться медленней, чем nested loop join.
Хотя, как упомянуто ранее, я нахожу подобные сценарии больше исключениями из правил использования merge join в реальном мире.
Запросы в PostgreSQL: 7. Сортировка и слияние
В предыдущих статьях я писал про этапы выполнения запросов, про статистику, про два основных вида доступа к данным — последовательное сканирование и индексное сканирование, — и успел рассказать о двух способах соединения — вложенном цикле и соединении хешированием.
В заключительной статье этой серии я расскажу про алгоритм слияния и про сортировку, и сравню все три способа соединения между собой.
Соединение слиянием
Соединение слиянием работает для наборов данных, отсортированных по ключу соединения, и возвращает отсортированный же результат. Входной набор может получиться заранее отсортированным в результате индексного сканирования или он может быть отсортирован явно.
Слияние отсортированных наборов
Вот пример соединения слиянием; оно представлено в плане выполнения узлом Merge Join:
Соединение выполняется за один проход по обоим наборам данных и не требует дополнительной памяти. Используются два указателя на текущие (изначально — первые) строки внутреннего и внешнего наборов.
Если ключи двух текущих строк не совпадают, один из указателей — тот, что ссылается на строку с меньшим ключом — продвигается на одну позицию вперед до тех пор, пока не будет найдено совпадение. Соответствующие друг другу строки возвращаются вышестоящему узлу, а указатель внутреннего набора данных продвигается на одну позицию вперед. Алгоритм продолжается до тех пор, пока один из наборов не закончится.
Такой алгоритм справляется с дубликатами ключей во внутреннем наборе данных, но, поскольку дубликаты могут быть и во внешнем наборе, алгоритм приходится немного усложнить: если после продвижения внешнего указателя ключ остается прежним, внутренний указатель возвращается назад на первую строку с тем же значением ключа. Таким образом, каждой строке из внешнего набора данных будут сопоставлены все строки с тем же ключом из внутреннего набора данных.
Для внешнего соединения алгоритм еще немного меняется, но общая идея остается той же самой.
Единственный оператор, на который рассчитано соединение слиянием — равенство, то есть поддерживаются только эквисоединения (хотя работа над поддержкой других условий тоже ведется).
Оценка стоимости. Рассмотрим приведенный выше пример:
В начальную стоимость соединения входят как минимум начальные стоимости дочерних узлов.
В общем случае для нахождения первого соответствия может потребоваться прочитать некоторую долю внешнего или внутреннего наборов данных. Оценку этой доли можно дать, сравнив (с помощью гистограммы) минимальные значения ключа соединения в двух наборах. Но в данном случае диапазон номеров билетов в обоих таблицах совпадает.
Полная стоимость соединения складывается из стоимостей получения данных от дочерних узлов и стоимости вычислений.
Поскольку алгоритм соединения останавливается, когда заканчивается один из наборов данных (конечно, кроме случая внешнего соединения), другой набор может быть прочитан не полностью. Оценку этой доли можно получить, сравнив максимальные значения ключа в двух наборах. В нашем случае оба набора будут прочитаны до конца, так что в полную стоимость соединения войдет сумма полных стоимостей обоих дочерних узлов.
Кроме того, при наличии дубликатов часть строк внешнего набора может быть прочитана несколько раз. Количество повторных чтений оценивается разностью кардинальностей результата соединения и внутреннего набора.
В нашем запросе эти кардинальности совпадают, что говорит об отсутствии дубликатов.
Необходимые вычисления состоят из сравнений ключей соединения и выдачи результирующих строк. Количество сравнений можно оценить суммой кардинальностей обоих наборов и количества повторных чтений строк внешнего набора; одно сравнение оценивается значением параметра cpu_operator_cost. Стоимость обработки одной результирующей строки оценивается, как обычно, значением параметра cpu_tuple_cost.
Подытоживая, для нашего примера стоимость соединения вычисляется следующим образом:
Параллельный режим
Соединение слиянием может использоваться в параллельных планах.
Сканирование внешнего набора строк выполняется рабочими процессами параллельно, но внутренний набор строк каждый рабочий процесс всегда читает самостоятельно.
Вот пример параллельного плана запроса, использующего соединение слиянием:
Полные и правые внешние соединения слиянием в параллельных планах не поддерживаются.
Модификации
Соединение слиянием поддерживает любые типы соединений. Единственное ограничение для полного и правого внешних соединений — условие соединения должно содержать только выражения, подходящие для слияния (равенство столбцов из внешнего и внутреннего наборов или равенство столбца константе). В остальных случаях результат соединения просто фильтруется по таким дополнительным выражениям после соединения, но для полного и правого соединений это невозможно.
Вот пример полного соединения, использующего алгоритм слияния:
Внутреннее и левое внешнее соединения слиянием сохраняют порядок сортировки. Но для полного и правого внешних соединений это не верно, поскольку между упорядоченными значениями внешнего набора данных могут быть вставлены неопределенные значения — а это нарушает сортировку. Поэтому здесь появляется узел Sort, восстанавливающий нужный порядок. Это, конечно, увеличивает стоимость плана и делает хеш-соединение более привлекательным, и, чтобы показать этот план, хеш-соединения пришлось отключить.
Но в следующем примере хеш-соединение используется все равно, поскольку это единственный способ выполнить полное соединение, содержащее условия в виде, который не поддерживается соединением слияния:
Сортировка
Если какой-то из наборов строк (а возможно, и оба) не отсортирован по ключу соединения, перед выполнением слияния он должен быть переупорядочен. Такая явная сортировка представляется в плане выполнения узлом Sort:
Здесь узел WindowAgg вычисляет оконную функцию по набору данных, предварительно отсортированному узлом Sort.
В арсенале планировщика имеется несколько способов сортировки данных. В примере, который я уже показывал, используется два из них (Sort Method). Как обычно, эти детали можно узнать, выполнив команду EXPLAIN ANALYZE :
Быстрая сортировка
Если сортируемый набор данных помещается в память, ограниченную значением параметра work_mem, применяется традиционная быстрая сортировка (quick sort). Этот алгоритм описан во всех учебниках и я не буду его повторять.
С точки зрения реализации сортировка выполняется специальным компонентом, который выбирает наиболее подходящий алгоритм сортировки.
Оценка стоимости. Возьмем пример сортировки небольшой таблицы:
Известно, что сортировка n значений имеет вычислительную сложность O(n log2n). Одна операция сравнения оценивается удвоенным значением параметра cpu_operator_cost. Поскольку результат можно получить, только прочитав и отсортировав весь набор данных, стоимость операций сравнения вместе с полной стоимостью дочернего узла составляет начальную стоимость сортировки.
В полную стоимость сортировки добавляется обработка каждой строки результата, которая оценивается значением параметра cpu_operator_cost (а не cpu_tuple_cost, как обычно, поскольку для узла Sort накладные расходы невелики).
В нашем примере стоимость вычисляется так:
Частичная пирамидальная сортировка
Если нужно отсортировать не весь набор данных, а только его часть (что определяется предложением LIMIT ), может применяться частичная пирамидальная сортировка (top-N heapsort). Точнее, этот алгоритм используется, если количество строк после сортировки уменьшается как минимум вдвое, или если входной набор строк не помещается целиком в отведенную оперативную память (но выходной набор при этом помещается).
Чтобы найти k максимальных (минимальных) значений из n, в структуру данных, называемую кучей, добавляются k первых строк. Затем по одной добавляются и все остальные строки, но после добавления каждой следующей строки из кучи изымается одно наименьшее (наибольшее) значение. В результате в куче остаются k искомых значений.
Куча (heap), используемая в этот алгоритме, является структурой данных и не имеет ничего общего с таблицами базы данных, которые часто называют этим же термином.
Оценка стоимости. Сложность алгоритма оценивается как O(n log2k), однако каждая операция обходится дороже, чем в случае быстрой сортировки. Поэтому формула расчета стоимости использует n log22k.
Внешняя сортировка
Если при чтении набора данных выясняется, что он слишком велик для сортировки в оперативной памяти, узел сортировки переключается на внешнюю сортировку слиянием (external merge).
Уже прочитанные строки сортируются в памяти алгоритмом быстрой сортировки и записываются во временный файл.
В освобожденную память читаются следующие строки и процедура повторяется до тех пор, пока все данные не будут записаны в несколько файлов, каждый из которых по отдельности отсортирован.
Далее несколько файлов объединяются в один примерно тем же алгоритмом, что используется и при соединении слиянием. Основное отличие состоит в том, что объединяться могут более двух файлов одновременно.
Для слияния не требуется много памяти. В принципе, достаточно располагать местом под одну строку для каждого файла. Из файлов читаются первые строки, среди них выбирается минимальная (или максимальная, в зависимости от направления сортировки) и возвращается как часть результата, а на ее место читается новая строка из соответствующего файла.
На практике строки читаются не по одной, а порциями по 32 страницы, чтобы уменьшить количество операций ввода-вывода. Количество файлов, которые объединяются за одну итерацию, определяется доступным местом в памяти, но меньше шести не используется никогда. Сверху это количество тоже ограничено (числом 500), поскольку при слишком большом числе файлов эффективность теряется.
Если объединить все отсортированные временные файлы за одну итерацию не получается, приходится выполнять слияние файлов по частям и записывать результат в новые временные файлы. Каждая такая итерация увеличивает объем записываемых и читаемых данных, поэтому чем больше оперативной памяти доступно, тем эффективнее будет выполняться внешняя сортировка.
На следующей итерации слияние продолжается уже с новыми файлами.
Финальное слияние обычно откладывается и выполняется на лету, когда вышестоящий узел плана запрашивает данные.
Более подробную статистику использование временных файлов можно получить в журнале сообщений, установив параметр log_temp_buffers.
Оценка стоимости. В качестве примера возьмем тот же план с внешней сортировкой:
Здесь к обычной стоимости сравнений (количество которых остается таким же, как и в случае быстрой сортировки в памяти) добавляется стоимость ввода-вывода. Все входные данные придется сначала записать на диск во временные файлы, а затем прочитать с диска при слиянии (причем, возможно, несколько раз, если количество созданных файлов будет превышать количество одновременно объединяемых наборов).
Обращение к диску (и запись, и чтение) оценивается как на три четверти последовательное и на одну четверть случайное.
Таким образом стоимость сортировки в нашем плане вычисляется так:
Инкрементальная сортировка
Инкрементальная сортировка уменьшает требования к памяти, разбивая весь набор на несколько меньших групп, а также позволяет начать выдавать результаты после обработки первой группы, не дожидаясь сортировки всего набора.
Реализация действует более тонко: отдельно обрабатываются только относительно крупные группы строк, а небольшие объединяются и сортируются полностью. Это уменьшает накладные расходы на запуск алгоритма сортировки.
В плане выполнения инкрементальная сортировка представлена узлом Incremental Sort:
Начиная с версии 14 инкрементальная сортировка может использоваться и для оконных функций:
Оценка стоимости. Расчет стоимости инкрементальной сортировки опирается на оценку количества групп и оценку сортировки группы среднего размера (которую мы уже рассмотрели).
Начальная стоимость отражает оценки сортировки одной (первой) группы, после чего узел уже может выдавать отсортированные строки, а полная стоимость учитывает сортировку всех групп:
Подробно останавливаться на вычислении оценок я не буду.
Параллельный режим
Сортировка может выполняться параллельно. Но, хотя рабочие процессы выдают свою часть данных в отсортированном виде, узел Gather ничего не знает про упорядоченность и может объединять данные только в порядке поступления. Чтобы сохранить сортировку, применяется другой узел — Gather Merge.
Узел Gather Merge использует двоичную кучу для упорядочения строк, поступающих от нескольких процессов. По сути, выполняется слияние нескольких отсортированных наборов строк, как при внешней сортировке, но алгоритм рассчитан на другие условия работы: на небольшое фиксированное число источников и получение строк по одной, без блочного доступа.
Оценка стоимости. Начальная стоимость узла Gather Merge опирается на начальную стоимость дочернего узла. К ней (как и в случае узла Gather) добавляется стоимость запуска процессов, которая оценивается значением параметра parallel_setup_cost.
Сюда же добавляется оценка построения двоичной кучи, что требует сортировки n значений по числу параллельных процессов (то есть n log2n). Одна операция сравнения оценивается удвоенным значением параметра cpu_operator_cost, и общая сумма обычно пренебрежимо мала, поскольку n невелико.
В полную стоимость входит получение всех данных дочерним узлом, который выполняется несколькими параллельными процессами, и стоимость пересылки строк от этих процессов. Пересылка одной строки оценивается значением параметра parallel_tuple_cost, увеличенным на 5 %, чтобы учесть возможные потери при ожидании получения очередных значений.
В полную стоимость входит также обновление двоичной кучи. Для каждой входящей строки данных это требует log2n операций сравнения и определенных вспомогательных действий (которые оцениваются значением cpu_operator_cost).
Вот еще один пример плана с узлом Gather Merge:
Этот план интересен тем, что рабочие процессы выполняют частичную агрегацию с помощью хеширования, затем полученные результаты сортируются узлом Sort (это дешево, поскольку после агрегации остается немного строк) и передаются ведущему процессу, который собирает полный результат в узле Gather Merge. Окончательная же агрегация выполняется не хешированием, а по отсортированному списку значений.
В данном случае количество параллельных процессов равно трем (включая основной) и стоимость узла Gather Merge вычисляется так:
Группировка и уникальные значения
Как мы только что видели, группировка значений для агрегации (и устранения дубликатов) может выполняться не только хешированием, но и с помощью сортировки. В отсортированном списке группы повторяющихся значений элементарно выделяются за один проход.
Выбор уникальных значений из отсортированного списка представляется в плане очень простым узлом Unique:
Для агрегации используется другой узел, GroupAggregate:
В параллельных планах такой узел будет называться Partial GroupAggregate, а узел, завершающий агрегацию, — Finalize GroupAggregate.
На первом этапе этот набор сканируется и значения группируются по aircraft_code (Group Key). По мере сканирования строки переупорядочиваются по столбцу flight_no (так, как это делает обычный узел Sort: либо быстрой сортировкой в памяти, если ее достаточно, либо внешней сортировкой на диске) и одновременно с этим записываются в хеш-таблицу с ключом departure_airport (так, как это делает агрегация хешированием: либо в памяти, либо с использованием временных файлов).
Наконец, сканируется хеш-таблица, подготовленная на первом этапе, и значения группируются по столбцу departure_airport (Hash Key).
Сравнение способов соединения
Итак, для соединения двух наборов данных могут использоваться три разных способа, каждый со своими достоинствами и недостатками.
Соединение вложенным циклом не требует никакой подготовительной работы и начинает возвращать результирующие строки сразу же. Это единственный из способов соединения, которому не требуется просматривать внутренний набор полностью, если для него есть эффективный индексный доступ. Эти свойства делают алгоритм вложенного цикла (в сочетании с индексами) идеальным механизмом для коротких OLTP-запросов, которые строятся на небольшой выборке строк.
Недостаток вложенного цикла проявляется с ростом объема данных. Для декартова произведения этот алгоритм имеет квадратичную сложность — затраты пропорциональны произведению размеров соединяемых наборов данных. Декартово произведение нечасто встречается на практике; обычно для каждой строки внешнего набора данных с помощью индекса просматривается некоторое количество строк внутреннего набора, и это среднее количество не зависит от размера всего набора данных (например, среднее количество билетов в одном бронировании не меняется с ростом количества бронирований и купленных билетов). Поэтому часто рост сложности будет линейным, а не квадратичным, хотя и с большим коэффициентом.
Важная особенность вложенного цикла состоит в его универсальности: поддерживаются любые условия соединения, в то время как остальные способы работают только с эквисоединениями. Это дает возможность выполнять любые запросы с любыми условиями (кроме полного соединения, которое не реализуется вложенным циклом), но надо помнить о том, что не-эквисоединение больших объемов будет выполняться заведомо неэффективно.
Соединение хешированием очень эффективно для больших наборов данных. При наличии достаточного объема памяти оно требует однократного просмотра двух наборов данных, то есть имеет линейную сложность. В сочетании с последовательным сканированием таблиц, соединение хешированием часто встречается в OLAP-запросах, вычисляющих результат на основании большого объема данных.
Для ситуаций, в которых время отклика важнее пропускной способности, хеш-соединение подходит хуже, поскольку результирующие строки не могут возвращаться, пока хеш-таблица не построена полностью.
Применение хеш-соединения ограничено эквисоединениями. Кроме того, тип данных должен допускать хеширование (это выполняется почти всегда).
Начиная с версии 14 вложенный цикл может иногда составить конкуренцию соединению хешированием за счет кеширования строк внутреннего набора в узле Memoize (также основанного на хеш-таблице). Выигрыш может достигаться за счет того, что соединение хешированием всегда просматривает внутренний набор строк полностью, а алгоритм вложенного цикла — нет.
Соединение слиянием отлично подходит и для коротких OLTP-запросов, и для длинных запросов OLAP. Оно имеет линейную сложность (требуется однократный просмотр соединяемых наборов строк), не требовательно к памяти и выдает результаты без предварительной подготовки. Единственная сложность состоит в том, что наборы данных должны быть отсортированы в правильном порядке. Наиболее эффективный способ добиться этого — получать данные от индексного сканирования. Это естественный вариант для небольшого количества строк; при большом объеме данных индексный доступ тоже может быть эффективен, если это только индексное сканирование с минимальными обращениями к таблице или вовсе без них.
Если подходящих индексов нет, то наборы данных придется сортировать, а сортировка требует памяти и имеет сложность выше линейной: O(n log2n). В таком случае соединение слиянием почти всегда проигрывает соединению хешированием — за исключением ситуации, когда результат нужен отсортированным.
К приятным свойствам соединения слиянием относится равноценность внешнего и внутреннего наборов строк. Эффективность и вложенного цикла, и хеш-соединения сильно зависит от того, правильно ли планировщик выберет, какой из наборов данных поставить внешним, а какой — внутренним.
Применение соединения слиянием ограничено эквисоединениями. Кроме того, тип данных должен иметь класс операторов для B-дерева.
На графике показана примерная зависимость стоимостей различных способов соединений двух таблиц от доли соединяемых строк.
Соединение вложенным циклом при высокой селективности использует индексный доступ к обоим таблицам; затем планировщик переключается на полное сканирование внешней таблицы и график становится линейным.
Соединения хешированием использует в этом примере полное сканирование обоих таблиц. «Ступенька» на графике возникает в тот момент, когда хеш-таблица перестает помещаться в оперативной памяти и пакеты начинают сбрасываться на диск.
Соединение слиянием с использованием индекса показывает небольшой линейный рост стоимости. При достаточном объеме work_mem соединение хешированием обычно оказывается эффективнее, но, когда дело доходит до временных файлов, соединение слиянием выигрывает.
Верхний график соединения слиянием с сортировкой показывает рост стоимости в ситуации, когда индексы недоступны, и данные приходится сортировать. Как и в случае хеширования, «ступенька» на графике вызвана недостатком памяти и необходимостью использовать для сортировки временные файлы.
Это только пример; в каждом конкретном случае соотношения стоимостей, разумеется, будут отличаться.
На этом я остановлюсь. Нельзя объять необъятное, но думаю, что основные моменты я охватил.
Материал этой и прошлых серий статей лег в основу книги, над которой я сейчас работаю, и которая, надеюсь, увидит свет уже в конце этого года. Спасибо всем, кто меня читает — ваши комментарии позволяют улучшить текст.