В рамках подготовки к конференции PG Day’16 мы продолжаем знакомить вас с интересными аспектами PostgreSQL. И сегодня предлагаем вам перевод третьей статьи из серии об explain.
В предыдущих постах этой серии я писал о том, как интерпретировать отдельно взятую строку в выводе анализа explain, его структуру, а также описал базовые операции получения данных (узлы дерева explain).
Сегодня мы перейдем к более сложным операциям.
Пример:
По большому счету, это так просто, что нет особой необходимости что-то объяснять. Но так как эта операция будет использоваться в следующих примерах, я всё же напишу о ней немного.
Function Scan – очень простой узел. Он запускает функцию, которая возвращает набор записей (recordset), – вот и всё. Он не будет запускать функции на подобие “lower()", а только те, которые потенциально вернут множество строк или столбцов. Когда функция вернет строки, они будут переданы в тот узел, который находится на уровень выше Function Scan в дереве плана, или клиенту, если Function Scan является корневым узлом.
Единственная дополнительная логика, которая здесь может возникнуть – это способность фильтровать полученные строки, как здесь:
Думаю, это довольно просто понять – sort берет выбранные записи и возвращает их отсортированными определенным образом.
Пример:
Хоть это и просто, внутри скрывается интересная логика. Для начала, если память, требующаяся для сортировки, будет больше, чем значение work_mem, то произойдет переключение на дисковую сортировку:
Обратите внимание на изменение Sort Method в примере выше.
В таких случаях Постгрес использует временные файлы, которые хранятся в директории $PGDATA/base/pgsql_tmp/. Конечно же, они будут удалены, как только в них исчезнет необходимость.
Ещё одно дополнительное свойство заключается в том, что Sort может менять свой метод работы, если вызывается операцией Limit, как вот здесь:
Обычно для сортировки выбранного набора данных вам нужно обработать его целиком. Но Постгрес знает, что если вам нужно лишь небольшое количество строк, ему не надо сортировать весь набор данных, достаточно получить только первые значения.
В нотации Big O общая сортировка имеет сложность O(m * log(m)), но Top-N имеет сложность O(m * log(n)), где m – число строк в таблице, а n – количество возвращаемых строк. Важно знать, что этот способ сортировки также использует гораздо меньше памяти (в конце концов, ему не нужно собирать весь набор данных из отсортированных строк, пары строк вполне достаточно), так что он с меньшей вероятностью будет использовать медленный диск для временных файлов.
Я использовал limit неоднократно, потому что он очень прост, но всё же давайте его подробно обсудим. Операция limit запускает свою субоперацию и возвращает только первые N строк из того, что вернула субоперация. Обычно после этого она останавливает субоперацию, но в некоторых случаях (например, вызов функции pl/PgSQL), субоперация уже завершила свою работу к тому моменту, когда она вернула первую строку.
Простой пример:
Как вы видите, использование лимита во втором случае привело к тому, что вложенная операция Seq Scan завершила свою работу сразу после нахождения двух строк.
Эта операция в основном применяется в случаях, когда вы используете GROUP BY и какие-нибудь агрегаты, вроде sum(), avg(), min(), max() и других.
Пример:
HashAggregate делает следующее: для каждой строки, которую получает, она находит «ключ» GROUP BY (в данном случае – relkind). Затем в хэше (ассоциативном массиве, словаре) помещает выбранную строку в корзину, обозначенную данным ключом.
После того как все строки были обработаны, она сканирует хэш и возвращает по одной строке для каждого значения ключа, совершая уместные расчёты по необходимости (sum, min, avg и так далее).
Важно понимать, что HashAggregate должен просканировать все строки прежде, чем сможет вернуть хотя бы одну.
Если вы это поняли, то, наверное, видите потенциальную проблему: что делать в ситуации, когда у вас миллионы строк? Хэш будет слишком большим, чтобы уместиться в памяти. И здесь мы снова будем использовать work_mem. Если сгенерированный хэш слишком велик, он будет «сливаться» на диск (опять в $PGDATA/base/pgsql_tmp).
Это значит, что если в плане есть и HashAggregate, и Sort, мы можем использовать вплоть до 2 * work_mem. Такой план легко получить:
В реальности один запрос может использовать work_mem много раз, поскольку work_mem – это ограничение для операции. Поэтому если в запросе применяется 1000 HashAggregate’ов и Sort’ов (и других операций, использующих work_mem), общее потребление памяти может быть очень высоким.
Поскольку мы только что обсуждали HashAggregate, будет логично перейти к Hash Join.
Эта операция, в отличие от предыдущей, имеет две субоперации. Одна из них всегда “Hash", а вторая – что-нибудь другое.
Как понятно из названия, Hash Join используется для объединения двух наборов записей. Например, как здесь:
Это работает следующим образом: сначала Hash Join вызывает “Hash", который в свою очередь вызывает что-нибудь ещё (в нашем случае – Seq Scan по pg_namespace). Потом Hash создает в памяти (или на диске – в зависимости от размера) хэш/ассоциативный массив/словарь со строками из источника, хэшированными с помощью того, что используется для объединения данных (в нашем случае это столбец OID в pg_namespace).
Конечно, у вас может быть много строк для указанного ключа join (не в этом случае, поскольку я объединяю с помощью первичного ключа, но в целом вполне вероятно, что у вас будет множество строк для одного хэш-ключа).
В нотации Perl, то вывод Hash будет примерно таким:
Потом Hash Join запускает вторую субоперацию (Seq Scan по pg_class в нашем случае) и, для каждой строки из неё, делает следующее:
Важно отметить, что обе стороны join выполняются всего один раз (в нашем случае и то, и другое является seq scan), но сначала та, что была вызвана операцией Hash, должна вернуть все строки, которые хранились в хэше, а вторая обрабатывается построчно, и некоторые строки будут пропущены, если они не существуют в хэше первой стороны (надеюсь, это предложение понятно, несмотря на обилие хэшей).
Поскольку оба субсканирования могут быть операциями любого типа, они могут оказаться фильтрами, сканированием индексов или тем, что вы себе можете вообразить.
Последнее, о чем стоит упомянуть в связи с Hash Join/Hash – это то, что операция Hash, так же, как Sort и HashAggregate будет использовать память вплоть до work_mem.
Поскольку мы говорим об объединениях, стоит обсудить 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. Он используется, если объединяемые наборы данных отсортированы (или могут быть отсортированы с небольшими затратами) с помощью ключа join.
У меня нет готового наглядного примера, поэтому я создам его искусственно с помощью подзапросов, которые сортируют данные перед объединением:
Merge Join, как и другие объединения, запускает две субоперации (Sort и Materialize в данном случае). Так как они обе возвращают данные отсортированными и порядок сортировки такой же, как в операции объединения, Pg может сканировать оба набора данных, возвращенных субоперациями, одновременно и просто проверить, совпадают ли идентификаторы.
Процедура выглядит следующим образом:
Это очень классный способ объединения наборов данных, но он работает только для отсортированных источников. Основываясь на текущей БД explain.depesz.com, существует:
Во всех примерах выше я продемонстрировал, что операция Join возвращает строку только когда получает строки с обеих сторон объединения.
Но так бывает не всегда. У нас могут быть левые, правые и полные (LEFT/RIGHT/FULL OUTER JOIN) внешние объединения, а также так называемые анти-объединения (anti-joins).
В случае с left/right joins названия операций меняются на:
Не существует Nested Loop Right Join, потому что Nested Loop всегда начинается слева и берет левую сторону как основу для цикла. Поэтому объединение, использующее RIGHT JOIN, которое будет работать с Nested Loop, внутренне трансформируется в LEFT JOIN, чтобы операция Nested Loop могла сработать.
Во всех этих случаях логика проста: у нас есть две стороны объединения – левая и правая. И когда сторона упоминается в объединении, оно возвращает новую строку, даже если на другой стороне нет соответствующих строк.
Так происходит с запросами вроде этого:
(или right join).
Вся остальная информация для Hash Join/Merge Join и Nested Loop одинакова, есть только небольшое изменение в логике того, когда генерируется вывод строки.
Есть также версия под названием Full Join со следующими именами операций:
В этом случае объединение генерирует новый вывод строки независимо от того, отсутствуют ли данные на какой-либо из сторон (до тех пор, пока данные есть хотя бы на одной стороне). Так происходит в случае:
Вся обработка происходит так же, как в предыдущих примерах.
Кроме того, есть так называемые Anti Join’ы. Названия их операций выглядят следующим образом:
В этих случаях Join выдаёт строку, только если правая сторона не находит ни одной строки. Это полезно, когда вы делаете что-нибудь, вроде “WHERE not exists ()" или “left join … where right_table.column is null".
Как в этом примере:
Здесь Pg выполнил правую сторону (Index Scan по pg_attribute), захэшировал её, а затем выполнил левую сторону (Seq Scan по pg_class), возвращая только те строки, где не было вхождений в Hash для данного pg_class.oid.
Эта операция уже была продемонстрирована в примере для 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мс, мы можем ожидать, что общее время будет составлять ~ 0.25мс.
Но Постгрес поступает умнее. Он понимает, что будет менее затратно просканировать таблицу один раз и построить в памяти образ всех её строк. Тогда в следующий раз не нужно будет сканировать таблицу, проверять информацию о видимости, парсить страницы данных. Он просто возьмет данные из памяти.
Благодаря этому общее время на всё (однократное чтение таблицы, подготовка образа данных в памяти и сканирование этого образа 87 раз) составило 0.087мс.
Вы можете сказать: «Хорошо, но почему merge join использовал materialize раньше, он ведь просто выполнял одно сканирование?» Давайте вспомним план:
Да, он запускался всего один раз. Проблема в том, что источник данных для Merge Join должен отвечать нескольким критериям. Некоторые из них очевидны (данные должны быть отсортированы), а другие менее очевидны, поскольку являются более техническими (данные должны быть просматриваемыми вперед и назад).
Из-за этих не слишком очевидных критериев Постгресу иногда приходится применять Materialize к данным, приходящим из источника (в нашем случае из Index Scan), чтобы у него были все необходимые возможности, когда дело дойдет до их использования.
Короче говоря, Materialize получает данные из нижележащей операции и размещает их в памяти (или частично в памяти), чтобы ими можно было быстрее воспользоваться, или добавляет им дополнительные свойства, которые предыдущая операция не предоставляет.
На сегодня это всё. Я думал, что на этом закончу, но есть ещё много операций, которые стоит описать, так что в этой серии будет ещё как минимум два поста (оставшиеся операции и статистическая информация).
В предыдущих постах этой серии я писал о том, как интерпретировать отдельно взятую строку в выводе анализа explain, его структуру, а также описал базовые операции получения данных (узлы дерева explain).
Сегодня мы перейдем к более сложным операциям.
Function scan
Пример:
$ explain analyze select * from generate_Series(1,10) i;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------
Function Scan on generate_series i (cost=0.00..10.00 rows=1000 width=4) (actual time=0.012..0.013 rows=10 loops=1)
Total runtime: 0.034 ms
(2 rows)
По большому счету, это так просто, что нет особой необходимости что-то объяснять. Но так как эта операция будет использоваться в следующих примерах, я всё же напишу о ней немного.
Function Scan – очень простой узел. Он запускает функцию, которая возвращает набор записей (recordset), – вот и всё. Он не будет запускать функции на подобие “lower()", а только те, которые потенциально вернут множество строк или столбцов. Когда функция вернет строки, они будут переданы в тот узел, который находится на уровень выше Function Scan в дереве плана, или клиенту, если Function Scan является корневым узлом.
Единственная дополнительная логика, которая здесь может возникнуть – это способность фильтровать полученные строки, как здесь:
$ explain analyze select * from generate_Series(1,10) i where i < 3;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
Function Scan on generate_series i (cost=0.00..12.50 rows=333 width=4) (actual time=0.012..0.014 rows=2 loops=1)
Filter: (i < 3)
Rows Removed by Filter: 8
Total runtime: 0.030 ms
(4 rows)
Sort
Думаю, это довольно просто понять – sort берет выбранные записи и возвращает их отсортированными определенным образом.
Пример:
$ explain analyze select * from pg_class order by relname;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------
Sort (cost=22.88..23.61 rows=292 width=203) (actual time=0.230..0.253 rows=295 loops=1)
Sort Key: relname
Sort Method: quicksort Memory: 103kB
-> Seq Scan on pg_class (cost=0.00..10.92 rows=292 width=203) (actual time=0.007..0.048 rows=295 loops=1)
Total runtime: 0.326 ms
(5 rows)
Хоть это и просто, внутри скрывается интересная логика. Для начала, если память, требующаяся для сортировки, будет больше, чем значение work_mem, то произойдет переключение на дисковую сортировку:
$ explain analyze select random() as x from generate_series(1,14000) i order by x;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
Sort (cost=62.33..64.83 rows=1000 width=0) (actual time=16.713..18.090 rows=14000 loops=1)
Sort Key: (random())
Sort Method: quicksort Memory: 998kB
-> Function Scan on generate_series i (cost=0.00..12.50 rows=1000 width=0) (actual time=2.036..4.533 rows=14000 loops=1)
Total runtime: 18.942 ms
(5 rows)
$ explain analyze select random() as x from generate_series(1,15000) i order by x;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
Sort (cost=62.33..64.83 rows=1000 width=0) (actual time=27.052..28.780 rows=15000 loops=1)
Sort Key: (random())
Sort Method: external merge Disk: 264kB
-> Function Scan on generate_series i (cost=0.00..12.50 rows=1000 width=0) (actual time=2.171..4.894 rows=15000 loops=1)
Total runtime: 29.767 ms
(5 rows)
Обратите внимание на изменение Sort Method в примере выше.
В таких случаях Постгрес использует временные файлы, которые хранятся в директории $PGDATA/base/pgsql_tmp/. Конечно же, они будут удалены, как только в них исчезнет необходимость.
Ещё одно дополнительное свойство заключается в том, что Sort может менять свой метод работы, если вызывается операцией Limit, как вот здесь:
$ explain analyze select * from pg_class order by relfilenode limit 5;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------
Limit (cost=15.77..15.78 rows=5 width=203) (actual time=0.119..0.120 rows=5 loops=1)
-> Sort (cost=15.77..16.50 rows=292 width=203) (actual time=0.118..0.118 rows=5 loops=1)
Sort Key: relfilenode
Sort Method: top-N heapsort Memory: 26kB
-> Seq Scan on pg_class (cost=0.00..10.92 rows=292 width=203) (actual time=0.005..0.047 rows=295 loops=1)
Total runtime: 0.161 ms
(6 rows)
Обычно для сортировки выбранного набора данных вам нужно обработать его целиком. Но Постгрес знает, что если вам нужно лишь небольшое количество строк, ему не надо сортировать весь набор данных, достаточно получить только первые значения.
В нотации Big O общая сортировка имеет сложность O(m * log(m)), но Top-N имеет сложность O(m * log(n)), где m – число строк в таблице, а n – количество возвращаемых строк. Важно знать, что этот способ сортировки также использует гораздо меньше памяти (в конце концов, ему не нужно собирать весь набор данных из отсортированных строк, пары строк вполне достаточно), так что он с меньшей вероятностью будет использовать медленный диск для временных файлов.
Limit
Я использовал limit неоднократно, потому что он очень прост, но всё же давайте его подробно обсудим. Операция limit запускает свою субоперацию и возвращает только первые N строк из того, что вернула субоперация. Обычно после этого она останавливает субоперацию, но в некоторых случаях (например, вызов функции pl/PgSQL), субоперация уже завершила свою работу к тому моменту, когда она вернула первую строку.
Простой пример:
$ explain analyze select * from pg_class;
QUERY PLAN
---------------------------------------------------------------------------------------------------------
Seq Scan on pg_class (cost=0.00..10.92 rows=292 width=203) (actual time=0.008..0.047 rows=295 loops=1)
Total runtime: 0.096 ms
(2 rows)
$ explain analyze select * from pg_class limit 2;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------
Limit (cost=0.00..0.07 rows=2 width=203) (actual time=0.009..0.010 rows=2 loops=1)
-> Seq Scan on pg_class (cost=0.00..10.92 rows=292 width=203) (actual time=0.008..0.009 rows=2 loops=1)
Total runtime: 0.045 ms
(3 rows)
Как вы видите, использование лимита во втором случае привело к тому, что вложенная операция Seq Scan завершила свою работу сразу после нахождения двух строк.
HashAggregate
Эта операция в основном применяется в случаях, когда вы используете GROUP BY и какие-нибудь агрегаты, вроде sum(), avg(), min(), max() и других.
Пример:
$ explain analyze select relkind, count(*) from pg_Class group by relkind;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------
HashAggregate (cost=12.38..12.42 rows=4 width=1) (actual time=0.223..0.224 rows=5 loops=1)
-> Seq Scan on pg_class (cost=0.00..10.92 rows=292 width=1) (actual time=0.008..0.053 rows=295 loops=1)
Total runtime: 0.273 ms
(3 rows)
HashAggregate делает следующее: для каждой строки, которую получает, она находит «ключ» GROUP BY (в данном случае – relkind). Затем в хэше (ассоциативном массиве, словаре) помещает выбранную строку в корзину, обозначенную данным ключом.
После того как все строки были обработаны, она сканирует хэш и возвращает по одной строке для каждого значения ключа, совершая уместные расчёты по необходимости (sum, min, avg и так далее).
Важно понимать, что HashAggregate должен просканировать все строки прежде, чем сможет вернуть хотя бы одну.
Если вы это поняли, то, наверное, видите потенциальную проблему: что делать в ситуации, когда у вас миллионы строк? Хэш будет слишком большим, чтобы уместиться в памяти. И здесь мы снова будем использовать work_mem. Если сгенерированный хэш слишком велик, он будет «сливаться» на диск (опять в $PGDATA/base/pgsql_tmp).
Это значит, что если в плане есть и HashAggregate, и Sort, мы можем использовать вплоть до 2 * work_mem. Такой план легко получить:
$ explain analyze select relkind, count(*) from pg_Class group by relkind order by relkind;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
Sort (cost=12.46..12.47 rows=4 width=1) (actual time=0.260..0.261 rows=5 loops=1)
Sort Key: relkind
Sort Method: quicksort Memory: 25kB
-> HashAggregate (cost=12.38..12.42 rows=4 width=1) (actual time=0.221..0.222 rows=5 loops=1)
-> Seq Scan on pg_class (cost=0.00..10.92 rows=292 width=1) (actual time=0.006..0.044 rows=295 loops=1)
Total runtime: 0.312 ms
(6 rows)
В реальности один запрос может использовать work_mem много раз, поскольку work_mem – это ограничение для операции. Поэтому если в запросе применяется 1000 HashAggregate’ов и Sort’ов (и других операций, использующих work_mem), общее потребление памяти может быть очень высоким.
Hash Join / Hash
Поскольку мы только что обсуждали HashAggregate, будет логично перейти к Hash Join.
Эта операция, в отличие от предыдущей, имеет две субоперации. Одна из них всегда “Hash", а вторая – что-нибудь другое.
Как понятно из названия, Hash Join используется для объединения двух наборов записей. Например, как здесь:
$ explain analyze select * from pg_class c join pg_namespace n on c.relnamespace = n.oid;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Hash Join (cost=1.14..16.07 rows=292 width=316) (actual time=0.036..0.343 rows=295 loops=1)
Hash Cond: (c.relnamespace = n.oid)
-> Seq Scan on pg_class c (cost=0.00..10.92 rows=292 width=203) (actual time=0.007..0.044 rows=295 loops=1)
-> Hash (cost=1.06..1.06 rows=6 width=117) (actual time=0.012..0.012 rows=6 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 1kB
-> Seq Scan on pg_namespace n (cost=0.00..1.06 rows=6 width=117) (actual time=0.004..0.005 rows=6 loops=1)
Total runtime: 0.462 ms
(7 rows)
Это работает следующим образом: сначала Hash Join вызывает “Hash", который в свою очередь вызывает что-нибудь ещё (в нашем случае – Seq Scan по pg_namespace). Потом Hash создает в памяти (или на диске – в зависимости от размера) хэш/ассоциативный массив/словарь со строками из источника, хэшированными с помощью того, что используется для объединения данных (в нашем случае это столбец OID в pg_namespace).
Конечно, у вас может быть много строк для указанного ключа join (не в этом случае, поскольку я объединяю с помощью первичного ключа, но в целом вполне вероятно, что у вас будет множество строк для одного хэш-ключа).
В нотации Perl, то вывод Hash будет примерно таким:
{
'123' => [ { data for row with OID = 123 }, ],
'256' => [ { data for row with OID = 256 }, ],
...
}
Потом Hash Join запускает вторую субоперацию (Seq Scan по pg_class в нашем случае) и, для каждой строки из неё, делает следующее:
- Проверяет, есть ли ключ join (pg_class.relnamespace в данном случае) в хэше, возвращенном операцией Hash.
- Если нет, данная строка из субоперации игнорируется (не будет возвращена).
- Если ключ существует, Hash Join берет строки из хэша и, основываясь на этой строке, с одной стороны, и всех строках хэша, с другой стороны, генерирует вывод строк.
Важно отметить, что обе стороны join выполняются всего один раз (в нашем случае и то, и другое является seq scan), но сначала та, что была вызвана операцией Hash, должна вернуть все строки, которые хранились в хэше, а вторая обрабатывается построчно, и некоторые строки будут пропущены, если они не существуют в хэше первой стороны (надеюсь, это предложение понятно, несмотря на обилие хэшей).
Поскольку оба субсканирования могут быть операциями любого типа, они могут оказаться фильтрами, сканированием индексов или тем, что вы себе можете вообразить.
Последнее, о чем стоит упомянуть в связи с Hash Join/Hash – это то, что операция Hash, так же, как Sort и HashAggregate будет использовать память вплоть до work_mem.
Hash Join / Hash
Поскольку мы говорим об объединениях, стоит обсудить Nested Loop. Пример:
$ explain analyze select a.* from pg_class c join pg_attribute a on c.oid = a.attrelid where c.relname in ( 'pg_class', 'pg_namespace' );
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.28..52.32 rows=16 width=203) (actual time=0.057..0.134 rows=46 loops=1)
-> Seq Scan on pg_class c (cost=0.00..11.65 rows=2 width=4) (actual time=0.043..0.080 rows=2 loops=1)
Filter: (relname = ANY ('{pg_class,pg_namespace}'::name[]))
Rows Removed by Filter: 291
-> Index Scan using pg_attribute_relid_attnum_index on pg_attribute a (cost=0.28..20.25 rows=8 width=203) (actual time=0.007..0.015 rows=23 loops=2)
Index Cond: (attrelid = c.oid)
Total runtime: 0.182 ms
Это очень интересный план, потому что он может выполнять выбранные операции неоднократно.
Так же, как и у 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 раз.
Так что обработка выглядит следующим образом:
- Nested Loop запускает первую сторону объединения единожды. Давайте назовем её “A".
- Для каждой строки из “A", запускается вторая операция (назовём её “B").
- Если “B" не вернула ни одной строки, данные из “A" игнорируются.
- Если “B" вернула строки, для каждой возвращаемой строки Nested Loop возвращает новую строку, основанную на текущих строках из A и B.
Merge Join
Еще один метод объединения данных называется Merge Join. Он используется, если объединяемые наборы данных отсортированы (или могут быть отсортированы с небольшими затратами) с помощью ключа join.
У меня нет готового наглядного примера, поэтому я создам его искусственно с помощью подзапросов, которые сортируют данные перед объединением:
$ explain analyze select * from
( select oid, * from pg_class order by oid) as c
join
( select * from pg_attribute a order by attrelid) as a
on c.oid = a.attrelid;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
Merge Join (cost=23.16..268.01 rows=2273 width=410) (actual time=0.658..3.779 rows=2274 loops=1)
Merge Cond: (pg_class.oid = a.attrelid)
-> Sort (cost=22.88..23.61 rows=292 width=207) (actual time=0.624..0.655 rows=293 loops=1)
Sort Key: pg_class.oid
Sort Method: quicksort Memory: 102kB
-> Seq Scan on pg_class (cost=0.00..10.92 rows=292 width=207) (actual time=0.011..0.211 rows=293 loops=1)
-> Materialize (cost=0.28..212.34 rows=2273 width=203) (actual time=0.028..1.264 rows=2274 loops=1)
-> Index Scan using pg_attribute_relid_attnum_index on pg_attribute a (cost=0.28..183.92 rows=2273 width=203) (actual time=0.015..0.752 rows=2274 loops=1)
Total runtime: 4.009 ms
(9 rows)
Merge Join, как и другие объединения, запускает две субоперации (Sort и Materialize в данном случае). Так как они обе возвращают данные отсортированными и порядок сортировки такой же, как в операции объединения, Pg может сканировать оба набора данных, возвращенных субоперациями, одновременно и просто проверить, совпадают ли идентификаторы.
Процедура выглядит следующим образом:
- если объединяемый столбец справа такой же, как объединяемый столбец слева:
- возвращаем новую объединённую строку, основанную на текущих строках справа и слева;
- берем следующую строку справа (или слева, если справа больше нет строк);
- возвращаемся к шагу 1;
- если объединяемый столбец справа «меньше», чем объединяемый столбец слева:
- берем следующую строку справа (если строк больше нет, заканчиваем обработку);
- возвращаемся к шагу 1;
- если объединяемый столбец справа «больше», чем объединяемый столбец слева:
- берем следующую строку слева (если строк больше нет, заканчиваем обработку);
- возвращаемся к шагу 1.
Это очень классный способ объединения наборов данных, но он работает только для отсортированных источников. Основываясь на текущей БД explain.depesz.com, существует:
- 44,721 плана, содержащих операцию “Nested Loop";
- 34,305 плана с “Hash Join";
- всего 8,889 плана, использующих “Merge Join".
Модификаторы Hash Join / Nested Loop / Merge Join
Во всех примерах выше я продемонстрировал, что операция Join возвращает строку только когда получает строки с обеих сторон объединения.
Но так бывает не всегда. У нас могут быть левые, правые и полные (LEFT/RIGHT/FULL OUTER JOIN) внешние объединения, а также так называемые анти-объединения (anti-joins).
В случае с left/right joins названия операций меняются на:
- Hash Left Join,
- Hash Right Join,
- Merge Left Join,
- Merge Right Join,
- Nested Loop Left Join.
Не существует Nested Loop Right Join, потому что Nested Loop всегда начинается слева и берет левую сторону как основу для цикла. Поэтому объединение, использующее RIGHT JOIN, которое будет работать с Nested Loop, внутренне трансформируется в LEFT JOIN, чтобы операция Nested Loop могла сработать.
Во всех этих случаях логика проста: у нас есть две стороны объединения – левая и правая. И когда сторона упоминается в объединении, оно возвращает новую строку, даже если на другой стороне нет соответствующих строк.
Так происходит с запросами вроде этого:
select * from a left join b on ...
(или right join).
Вся остальная информация для Hash Join/Merge Join и Nested Loop одинакова, есть только небольшое изменение в логике того, когда генерируется вывод строки.
Есть также версия под названием Full Join со следующими именами операций:
- Hash Full Join,
- Merge Full Join.
В этом случае объединение генерирует новый вывод строки независимо от того, отсутствуют ли данные на какой-либо из сторон (до тех пор, пока данные есть хотя бы на одной стороне). Так происходит в случае:
select * from a full join b ...
Вся обработка происходит так же, как в предыдущих примерах.
Кроме того, есть так называемые Anti Join’ы. Названия их операций выглядят следующим образом:
- Hash Anti Join,
- Merge Anti Join,
- Nested Loop Anti Join.
В этих случаях Join выдаёт строку, только если правая сторона не находит ни одной строки. Это полезно, когда вы делаете что-нибудь, вроде “WHERE not exists ()" или “left join … where right_table.column is null".
Как в этом примере:
$ explain analyze select * from pg_class c where not exists (select * from pg_attribute a where a.attrelid = c.oid and a.attnum = 10);
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
Hash Anti Join (cost=62.27..78.66 rows=250 width=203) (actual time=0.145..0.448 rows=251 loops=1)
Hash Cond: (c.oid = a.attrelid)
-> Seq Scan on pg_class c (cost=0.00..10.92 rows=292 width=207) (actual time=0.009..0.195 rows=293 loops=1)
-> Hash (cost=61.75..61.75 rows=42 width=4) (actual time=0.123..0.123 rows=42 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 2kB
-> Index Only Scan using pg_attribute_relid_attnum_index on pg_attribute a (cost=0.28..61.75 rows=42 width=4) (actual time=0.021..0.109 rows=42 loops=1)
Index Cond: (attnum = 10)
Heap Fetches: 0
Total runtime: 0.521 ms
(9 rows)
Здесь Pg выполнил правую сторону (Index Scan по pg_attribute), захэшировал её, а затем выполнил левую сторону (Seq Scan по pg_class), возвращая только те строки, где не было вхождений в Hash для данного pg_class.oid.
Materialize
Эта операция уже была продемонстрирована в примере для Merge Join, но она может быть полезна и в других случаях.
У psql есть множество внутренних команд. Одна из них — \dTS, которая составляет список всех системных типов данных. Внутренне \dTS запускает этот запрос:
SELECT n.nspname as "Schema",
pg_catalog.format_type(t.oid, NULL) AS "Name",
pg_catalog.obj_description(t.oid, 'pg_type') as "Description"
FROM pg_catalog.pg_type t
LEFT JOIN pg_catalog.pg_namespace n ON n.oid = t.typnamespace
WHERE (t.typrelid = 0 OR (SELECT c.relkind = 'c' FROM pg_catalog.pg_class c WHERE c.oid = t.typrelid))
AND NOT EXISTS(SELECT 1 FROM pg_catalog.pg_type el WHERE el.oid = t.typelem AND el.typarray = t.oid)
AND pg_catalog.pg_type_is_visible(t.oid)
ORDER BY 1, 2;
План у него такой:
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------
Sort (cost=2783.00..2783.16 rows=65 width=68) (actual time=3.883..3.888 rows=87 loops=1)
Sort Key: n.nspname, (format_type(t.oid, NULL::integer))
Sort Method: quicksort Memory: 39kB
-> Nested Loop Left Join (cost=16.32..2781.04 rows=65 width=68) (actual time=0.601..3.657 rows=87 loops=1)
Join Filter: (n.oid = t.typnamespace)
Rows Removed by Join Filter: 435
-> Hash Anti Join (cost=16.32..2757.70 rows=65 width=8) (actual time=0.264..0.981 rows=87 loops=1)
Hash Cond: ((t.typelem = el.oid) AND (t.oid = el.typarray))
-> Seq Scan on pg_type t (cost=0.00..2740.26 rows=81 width=12) (actual time=0.012..0.662 rows=157 loops=1)
Filter: (pg_type_is_visible(oid) AND ((typrelid = 0::oid) OR (SubPlan 1)))
Rows Removed by Filter: 185
SubPlan 1
-> Index Scan using pg_class_oid_index on pg_class c (cost=0.15..8.17 rows=1 width=1) (actual time=0.002..0.002 rows=1 loops=98)
Index Cond: (oid = t.typrelid)
-> Hash (cost=11.33..11.33 rows=333 width=8) (actual time=0.241..0.241 rows=342 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 14kB
-> Seq Scan on pg_type el (cost=0.00..11.33 rows=333 width=8) (actual time=0.002..0.130 rows=342 loops=1)
-> Materialize (cost=0.00..1.09 rows=6 width=68) (actual time=0.000..0.001 rows=6 loops=87)
-> Seq Scan on pg_namespace n (cost=0.00..1.06 rows=6 width=68) (actual time=0.002..0.003 rows=6 loops=1)
Total runtime: 3.959 ms
Для удобства просмотра я также загрузил этот план на explain.depesz.com.
Заметьте, что операция #9 – это Materialize. Почему?
Materialize вызывается Nested Loop Left Join – операцией #2. Мы знаем, что Nested Loop заставляет выбранную операцию выполняться многократно, в данном случае – 87 раз.
Правая часть объединения – Seq Scan по pg_namespace. Так что, теоретически, Постгрес должен выполнить последовательное сканирование по pg_namespace 87 раз. Если учесть, что единичное последовательное сканирование этой таблицы занимает 0.003мс, мы можем ожидать, что общее время будет составлять ~ 0.25мс.
Но Постгрес поступает умнее. Он понимает, что будет менее затратно просканировать таблицу один раз и построить в памяти образ всех её строк. Тогда в следующий раз не нужно будет сканировать таблицу, проверять информацию о видимости, парсить страницы данных. Он просто возьмет данные из памяти.
Благодаря этому общее время на всё (однократное чтение таблицы, подготовка образа данных в памяти и сканирование этого образа 87 раз) составило 0.087мс.
Вы можете сказать: «Хорошо, но почему merge join использовал materialize раньше, он ведь просто выполнял одно сканирование?» Давайте вспомним план:
$ explain analyze select * from
( select oid, * from pg_class order by oid) as c
join
( select * from pg_attribute a order by attrelid) as a
on c.oid = a.attrelid;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
Merge Join (cost=23.16..268.01 rows=2273 width=410) (actual time=0.658..3.779 rows=2274 loops=1)
Merge Cond: (pg_class.oid = a.attrelid)
-> Sort (cost=22.88..23.61 rows=292 width=207) (actual time=0.624..0.655 rows=293 loops=1)
Sort Key: pg_class.oid
Sort Method: quicksort Memory: 102kB
-> Seq Scan on pg_class (cost=0.00..10.92 rows=292 width=207) (actual time=0.011..0.211 rows=293 loops=1)
-> Materialize (cost=0.28..212.34 rows=2273 width=203) (actual time=0.028..1.264 rows=2274 loops=1)
-> Index Scan using pg_attribute_relid_attnum_index on pg_attribute a (cost=0.28..183.92 rows=2273 width=203) (actual time=0.015..0.752 rows=2274 loops=1)
Total runtime: 4.009 ms
(9 rows)
Да, он запускался всего один раз. Проблема в том, что источник данных для Merge Join должен отвечать нескольким критериям. Некоторые из них очевидны (данные должны быть отсортированы), а другие менее очевидны, поскольку являются более техническими (данные должны быть просматриваемыми вперед и назад).
Из-за этих не слишком очевидных критериев Постгресу иногда приходится применять Materialize к данным, приходящим из источника (в нашем случае из Index Scan), чтобы у него были все необходимые возможности, когда дело дойдет до их использования.
Короче говоря, Materialize получает данные из нижележащей операции и размещает их в памяти (или частично в памяти), чтобы ими можно было быстрее воспользоваться, или добавляет им дополнительные свойства, которые предыдущая операция не предоставляет.
На сегодня это всё. Я думал, что на этом закончу, но есть ещё много операций, которые стоит описать, так что в этой серии будет ещё как минимум два поста (оставшиеся операции и статистическая информация).