Объясняя необъяснимое

Объясняя необъяснимое

Разработка веб-сайтов*PostgreSQL*SQL*
Перевод
Автор оригинала: Hubert Lubaczewski
 
Друзья, мы с радостью продолжаем публикацию интересных материалов, посвященных самым разнообразным аспектам работы с PostgreSQL. Сегодняшний перевод открывает целую серию статей за авторством Hubert Lubaczewski, которые наверняка заинтересуют широкий круг читателей.

Одна из первых вещей, которую слышит новоиспеченный администратор баз данных – «используй EXPLAIN». И при первой же попытке он сталкивается c непостижимым:

                                                        QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=146.63..148.65 rows=808 width=138) (actual time=55.009..55.012 rows=71 loops=1)
   Sort Key: n.nspname, p.proname, (pg_get_function_arguments(p.oid))
   Sort Method: quicksort  Memory: 43kB
   ->  Hash Join  (cost=1.14..107.61 rows=808 width=138) (actual time=42.495..54.854 rows=71 loops=1)
         Hash Cond: (p.pronamespace = n.oid)
         ->  Seq Scan on pg_proc p  (cost=0.00..89.30 rows=808 width=78) (actual time=0.052..53.465 rows=2402 loops=1)
               Filter: pg_function_is_visible(oid)
         ->  Hash  (cost=1.09..1.09 rows=4 width=68) (actual time=0.011..0.011 rows=4 loops=1)
               Buckets: 1024  Batches: 1  Memory Usage: 1kB
               ->  Seq Scan on pg_namespace n  (cost=0.00..1.09 rows=4 width=68) (actual time=0.005..0.007 rows=4 loops=1)
                     Filter: ((nspname <> 'pg_catalog'::name) AND (nspname <> 'information_schema'::name))

Что бы это могло значить?

Бесполезно пытаться сразу понять представленный выше explain. Давайте лучше начнем с чего-то попроще. Но перед этим я хотел бы, чтобы вы поняли одну важную вещь:

PostgreSQL запоминает

Это значит, что PostgreSQL хранит некоторую мета-информацию (информацию об информации). Количество строк, количество различных значений, наиболее распространенные значения и так далее. Для больших таблиц эта информация основывается на случайной выборке, но в целом Постгрес действительно многое знает о наших данных.

Итак, давайте рассмотрим простой запрос и его explain:

$ explain select * from test where i = 1;
                      QUERY PLAN                      
------------------------------------------------------
 Seq Scan on test  (cost=0.00..40.00 rows=12 width=4)
   Filter: (i = 1)
(2 rows)

Запрос достаточно прост и, как мне кажется, не требует никаких дополнительных комментариев.

В explain первая строка и все строки, начинающиеся с “->» – это операции. Остальные строки – дополнительная информация к операции выше.

В нашем случае есть всего одна операция – последовательное сканирование таблицы test.

Также есть дополнительная информация о фильтре.

Последовательное сканирование означает, что PostgreSQL будет «открывать» данные из таблицы и читать их. Теоретически, он может отфильтровывать (удалять) строки, но, в целом, готов прочитать и вернуть всю таблицу целиком.

Почему готов? Объясню через минуту.

Итак, строка Seqscan информирует нас о том, что мы сканируем таблицу в последовательном режиме. И что таблица называется “test» (хотя вот тут кроется одна из самых больших проблем explain – он не показывает схему, и это мне аукалось не один раз).

А что же это за числа в скобках после операции?

Хочу задать вам вопрос. У вас есть вот такая таблица:

Table "public.t"
   Column    |  Type   |                   Modifiers                    
-------------+---------+------------------------------------------------
 id          | integer | not null default nextval('t_id_seq'::regclass)
 some_column | integer | 
 something   | text    | 
Indexes:
    "t_pkey" PRIMARY KEY, btree (id)
    "q" btree (some_column)

Имея определение этой таблицы и запрос:

SELECT * FROM t where some_column = 123;

Как вы думаете, каким способом лучше всего выполнить этот запрос? Последовательно просканировать таблицу или использовать индекс?

Если ваш ответ: конечно, использовать индекс, на этой колонке есть индекс, так что такой способ будет быстрее, — то я спрошу: как насчет ситуации, когда в таблице всего одна строка, и она содержит значение some_column, равное 123?

Чтобы произвести последовательное сканирование, мне нужно прочитать всего одну страницу таблицы (8192 байт), и я получу строку. Для того чтобы использовать индекс, мне нужно прочитать страницу из индекса, проверить, есть ли в таблице строки, соответствующие условию, а потом прочитать страницу из таблицы.

В итоге – вдвое больше работы!

Вы могли бы сказать: «Конечно, но речь ведь об очень маленьких таблицах, так что скорость не имеет значения». Хорошо. Тогда давайте представим таблицу, в которой 10 миллиардов строк, и у каждой из них some_column = 123. Индекс здесь точно не поможет, а в реальности вообще серьезно ухудшит ситуацию.

Конечно, если у вас миллион строк и только у одной из них some_column = 123, сканирование индексов будет наиболее правильным решением.

Таким образом, невозможно сказать, будет ли данный запрос использовать индекс, и надо ли ему вообще использовать индекс (речь идёт об общих случаях). Чтобы понять это, вам нужно больше информации. И этот факт приводит нас к простому выводу: в зависимости от ситуации один способ получения данных будет лучше или хуже другого.

PostgreSQL (до определенного момента) проверяет все возможные сценарии. Он знает, сколько у вас строк и сколько строк (вероятнее всего) попадут под заданные критерии, поэтому может принимать весьма умные решения.

Но как принимаются эти решения? Именно это и показывает первый набор цифр в explain. Это затраты.

Некоторые думают, что затраты оцениваются в секундах. Это не так. Их единица измерения – «извлечение одной страницы в последовательном (sequential) порядке». То есть оценивается и время, и использование ресурсов.

В postgresql.conf вы могли заметить вот такие параметры:

seq_page_cost = 1.0                    # measured on an arbitrary scale
random_page_cost = 4.0                 # same scale as above
cpu_tuple_cost = 0.01                  # same scale as above
cpu_index_tuple_cost = 0.005           # same scale as above
cpu_operator_cost = 0.0025             # same scale as above

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

Давайте для примера создадим простую таблицу из 1000 строк с какими-нибудь текстами и индексом:

create table test (id serial primary key, some_text text);
CREATE TABLE
 
insert into test (some_text) select 'whatever' from generate_series(1,1000);
INSERT 0 1000

Мы видим, что запуск explain с условием по id выдаёт следующее:

explain select * from test where id = 50;
                              QUERY PLAN                               
-----------------------------------------------------------------------
 Index Scan using test_pkey on test  (cost=0.28..8.29 rows=1 width=36)
   Index Cond: (id = 50)
(2 rows)

А что если бы мы сказали постгресу, что сканирование индекса нельзя использовать ни при каких условиях?

explain select * from test where id = 50;
                               QUERY PLAN                               
------------------------------------------------------------------------
 Bitmap Heap Scan on test  (cost=4.28..8.30 rows=1 width=13)
   Recheck Cond: (id = 50)
   ->  Bitmap Index Scan on test_pkey  (cost=0.00..4.28 rows=1 width=0)
         Index Cond: (id = 50)
(4 rows)

И это тоже давайте отключим:

explain select * from test where id = 50;
                      QUERY PLAN                      
------------------------------------------------------
 Seq Scan on test  (cost=0.00..18.50 rows=1 width=13)
   Filter: (id = 50)
(2 rows)

OK, а теперь давайте выведем их рядом друг с другом:

Index Scan using test_pkey on test  (cost=0.28..8.29 rows=1 width=36)
Bitmap Heap Scan on test  (cost=4.28..8.30 rows=1 width=13)
Seq Scan on test  (cost=0.00..18.50 rows=1 width=13)

По умолчанию постгрес использует IndexScan. Почему? Всё просто – в данном случае это наименее затратный способ. Издержки составят 8.29, в то время как для bitmap heap scan (что бы это ни было) потребуется 8.30, а для seq scan – 18.5.

OK, но издержки обозначаются двумя числами: number..number. Что это такое, и почему я говорю только о втором числе? Если бы мы учитывали первое число, то победителем оказался бы seq scan, так как у него это значение равно нулю, а у indexscan – 0.28, и аж 4.28 у bitmap heap scan.

Значение издержек выводится в диапазоне (number ..number), потому что оно показывает затраты на строку начала операции и затраты на получение всех строк (под всеми имеются в виду возвращенные этой операцией, а не все, имеющиеся в таблице).

Каковы начальные издержки? Для seqscan их нет – вы просто читаете страницу и возвращаете строки. И всё. Но, например, для сортировки набора данных вам нужно прочитать все данные и действительно отсортировать их прежде, чем рассматривать возможность возврата даже первой из строк. Это хорошо видно на следующем explain:

                            QUERY PLAN                             
-------------------------------------------------------------------
 Sort  (cost=22.88..23.61 rows=292 width=202)
   Sort Key: relfilenode
   ->  Seq Scan on pg_class  (cost=0.00..10.92 rows=292 width=202)
(3 rows)

Обратите внимание, что начальные затраты для Sort – 22.88, в то время как общие издержки составят всего 23.61. Так что возвращение строк из Sort с точки зрения затрат незначительно, а вот их сортировка – да.

Следующая информация в explain – это “rows». Это приблизительное количество строк, которое, как считает PostgreSQL, эта операция способна вернуть (она может вернуть меньше, например, в случае наличия LIMIT). Это также очень важно для некоторых операций — например, объединений (join). Объединение двух таблиц, в которых суммарно имеется 20 строк, может осуществляться множеством способов, и, по большому счету, неважно, каким именно. Но когда вы объединяете таблицу из миллиона строк с таблицей из миллиарда строк, способ, которым вы это делаете, очень важен (я говорю не об inner join / left join, а скорее о hash join, nested loop, merge join – если вы не понимаете, о чем речь, не переживайте, я всё объясню чуть позже).

Конечно, это число может быть оценено неверно – по многим причинам. Иногда это не имеет значения, а иногда имеет. Но о неправильных оценках мы поговорим позже.

Последний кусочек информации – ширина (width). Это оценка PostgreSQL того, сколько, в среднем, байт содержится в одной строке, возвращенной в рамках данной операции. Например:

explain select * from pg_class;
                         QUERY PLAN                          
-------------------------------------------------------------
 Seq Scan on pg_class  (cost=0.00..10.92 rows=292 width=202)
(1 row)
 
explain select relname, relkind from pg_class;
                         QUERY PLAN                         
------------------------------------------------------------
 Seq Scan on pg_class  (cost=0.00..10.92 rows=292 width=65)
(1 row)

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

А теперь внимание, наиболее важная информация: explain’ы – это деревья. Верхнему узлу требуются данные от узлов, расположенных под ним.

Давайте рассмотрим этот план.

В нём 5 операций: сортировка, hash join, seq scan, hash и снова seq scan. PostgreSQL выполняет верхнюю операцию – сортировку, которая в свою очередь выполняет следующую, находящуюся прямо под ней (hash join) и получает данные от нее. Hash join, чтобы вернуть данные в сортировку, должен запустить seq scan (по pg_proc) и hash (#4). И, наконец, hash, чтобы вернуть данные, должно прогнать seq scan по pg_namespace.

Очень важно понимать, что некоторые операции могут возвращать данные мгновенно или, что ещё важнее, постепенно. Например, Seq Scan. А некоторые не могут. К примеру, здесь мы видим, что Hash (#4) имеет те же начальные издержки, что и его «субоперация» seq scan для «всех строк». Это значит, что для начала операции hash (для того, чтобы она могла вернуть хоть одну строку), нужно прочитать все строки из её субопераций.

Часть о постепенном возврате строк становится особенно важна, когда вы начинаете писать функции. Давайте рассмотрим вот такую функцию:

CREATE OR REPLACE FUNCTION public.test()
 RETURNS SETOF integer
 LANGUAGE plpgsql
AS $function$
declare
    i int4;
begin
    for i in 1..3 loop
        return next i;
        perform pg_sleep(1);
    end loop;
    return;
end;
$function$;

Если вы ничего не поняли, не волнуйтесь. Функция возвращает 3 строки, каждая из которых содержит одно целое число – 1, 2 и 3. Важно то, что она засыпает на 1 секунду после возвращения каждой строки.

Это значит, что если я сделаю вот так:

select * from test();

Мне придётся ждать результатов 3 секунды.

Но как долго придётся ждать возвращения при вот таком раскладе:

select * from test() limit 1;

Давайте посмотрим:

\timing
Timing is on.
 
select * from test() limit 1;
 test 
------
    1
(1 row)
 
Time: 3005.334 ms

Те же 3 секунды. Почему? Потому что PL/pgSQL (и большинство, если не все, языков PL/*) не могут возвращать частичные результаты. Кажется, что могут – с помощью “return next» – но на самом деле все результаты хранятся в буфере и возвращаются вместе, когда исполнение функции завершается.

С другой стороны, «нормальные» операции обычно могут возвращать частичные данные. Это можно увидеть, если провести какую-нибудь банальную операцию, вроде последовательного сканирования, на непростой таблице:

create table t as
    select i as id,
        repeat('depesz', 100)::text as payload
    from generate_series(1,1000000) i;

По этой таблице видно, что:

explain analyze select * from t;
                                                   QUERY PLAN                                                   
----------------------------------------------------------------------------------------------------------------
 Seq Scan on t  (cost=0.00..185834.82 rows=10250082 width=36) (actual time=0.015..232.380 rows=1000000 loops=1)
 Total runtime: 269.666 ms
(2 rows)
 
explain analyze select * from t limit 1;
                                                  QUERY PLAN                                                  
--------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..0.02 rows=1 width=36) (actual time=0.003..0.003 rows=1 loops=1)
   ->  Seq Scan on t  (cost=0.00..185834.82 rows=10250082 width=36) (actual time=0.003..0.003 rows=1 loops=1)
 Total runtime: 0.016 ms
(3 rows)

(пожалуйста, смотрите пока только на “Total runtime: ..»)

Как вы видите, последовательное сканирование закончилось очень быстро – сразу как только удовлетворило аппетит LIMIT ровно на 1 строку.

Пожалуйста, отметьте, что здесь даже издержки (которые не являются лучшим критерием для сравнения запросов) показывают, что верхний узел (seq scan в первом запросе и limit во втором) имеет очень разные значения для возврата всех рядов – 185834.82 против 0.02.

Так что первые 4 числа для любой операции (две оценки затрат, кол-во строк и ширина) являются приблизительными. Они могут оказаться правильными, а могут и не оказаться.

Другие 4 числа, которые вы получаете, когда запускаете “EXPLAIN ANALYZE query» или “EXPLAIN ( ANALYZE on ) query», показывают реальные результаты.

Время по-прежнему указывается диапазоном, но на этот раз это реальное время. Именно столько времени PostgreSQL потратил на работу над данной операцией (в среднем, потому что он мог прогонять одну и ту же операцию множество раз). И так же, как издержки, время представлено диапазоном: время на начало выполнения операции и время на возврат всех данных. Давайте проверим этот план:

$ explain analyze select * from t limit 100;
                                                  QUERY PLAN                                                  
--------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..9.33 rows=100 width=608) (actual time=0.008..0.152 rows=100 loops=1)
   ->  Seq Scan on t  (cost=0.00..93333.86 rows=999986 width=608) (actual time=0.007..0.133 rows=100 loops=1)
 Total runtime: 0.181 ms
(3 rows)

Как вы видите, время начала операции для Limit – 0.008 (единица измерения тут – миллисекунды). Так происходит, потому что Seq Scan (который Limit вызвал для получения данных) потребовалось 0.007мс для возвращения первой строки, а потом еще 0.001мс ушло на обработку внутри самого limit.

Далее (после возврата первой строки), limit продолжил получать данные из Seq Scan, пока не получил 100 строк. Тогда он прекратил последовательное сканирование (это произошло через 0.133мс после начала запроса) и завершился сам еще через 0.019мс.

Фактическое количество строк, как становится ясно из названия, показывает, сколько строк (в среднем) эта операция вернула. А loop показывает, сколько всего раз эта операция выполнялась.

В каком случае операция будет вызываться более одного раза? Например, в некоторых случаях с join или вложенными запросами. Это будет похоже на вот этот план.

Отметьте, что в третьей операции всего два цикла. Это значит, что данный seq scan был запущен дважды, возвращал, в среднем, 1 строку и для завершения ему, в среднем, требовалось 0.160мс. Так что общее время, затраченное на эту конкретную операцию: 2 * 0.160мс = 0.32мс (что указано в колонках exclusive/inclusive на explain.depesz.com).

Очень часто низкая производительность запроса связана с тем, что ему пришлось много раз выполнять цикл по какому-то подзапросу. Например, как здесь.

(Конечно, это не значит, что во всем виноват постгрес, выбравший такой план. Возможно, других вариантов просто не было или они оказались ещё более затратными).

В примере выше стоит обратить внимание на то, что, хотя фактическое время операции 3 – всего лишь 0.003мс, эта операция производилась более 26000 раз, что в итоге вылилось в почти 79мс затраченного времени.

Думаю, на этом теоретическая информация, необходимая для чтения explain’ов, исчерпана. Скорее всего, вы до сих пор не понимаете, что означают операции и другая информация, но, по крайней мере, теперь вы знаете, что означают числа и в чем разница между explain (который показывает затраты в абстрактных единицах измерения, основанных на приблизительной оценке случайных примеров) и explain analyze (который показывает фактическое время, число строк и время выполнения в единицах измерения, которые позволяют сравнивать разные запросы).

Как всегда, я боюсь, что пропустил много вещей, которые могут быть важны, но не попались мне на глаза, или (что ещё хуже) я посчитал их “очевидными”. Если вам покажется, что чего-то не хватает, пожалуйста, сообщите мне, и я постараюсь восполнить пробелы как можно скорее.

Но хочу также добавить, что планирую развить этот текст ещё в 2-3 публикациях, в которых больше расскажу о том:

  • какие бывают операции, как они работают и чего стоит ожидать, когда вы видите их в выводе explain;
  • что такое статистика, как Pg её получает, как её просматривать и как извлечь из неё максимум пользы.

Самая базовая операция – это последовательное сканирование (Seq Scan).

Она выглядит вот так:

explain analyze select * from pg_class;
                                               QUERY PLAN                                                
---------------------------------------------------------------------------------------------------------
 Seq Scan on pg_class  (cost=0.00..10.92 rows=292 width=202) (actual time=0.009..0.049 rows=295 loops=1)
 Total runtime: 0.249 ms
(2 rows)

Это самая простая операция из всех возможных – PostgreSQL открывает файл с таблицей, читает строки одну за другой и возвращает их пользователю или расположенному выше узлу дерева explain, например, LIMIT, как здесь:

explain analyze select * from pg_class limit 2;
                                                 QUERY PLAN                                                  
-------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..0.07 rows=2 width=202) (actual time=0.014..0.014 rows=2 loops=1)
   ->  Seq Scan on pg_class  (cost=0.00..10.92 rows=292 width=202) (actual time=0.009..0.009 rows=2 loops=1)
 Total runtime: 0.132 ms
(3 rows)

Важно понимать, что порядок возврата строк не является каким-то определенным. Они возвращаются не «в порядке вставки» или «последняя обновленная строка – первой», или ещё что-то в том же духе. Параллельные выборки, обновления, удаления, чистки (vacuums) могут менять порядок следования строк в любое время.

Seq Scan может фильтровать строки – то есть отбрасывать некоторые при возврате. Это происходит, например, когда вы добавляете условие “WHERE»:

explain analyze select * from pg_class where relname ~ 'a';
                                               QUERY PLAN                                                
---------------------------------------------------------------------------------------------------------
 Seq Scan on pg_class  (cost=0.00..11.65 rows=227 width=202) (actual time=0.030..0.294 rows=229 loops=1)
   Filter: (relname ~ 'a'::text)
   Rows Removed by Filter: 66
 Total runtime: 0.379 ms
(4 rows)

Как вы видите, теперь у нас появилась информация “Filter:”. И, поскольку у меня версия СУБД 9.2 или новее, я также получил комментарий «Строки удалены фильтром» (“Rows removed by filter»).

Следующий тип узла — “Index Scan».

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

explain analyze select * from pg_class where oid = 1247;
                                                          QUERY PLAN                                                           
-------------------------------------------------------------------------------------------------------------------------------
 Index Scan using pg_class_oid_index on pg_class  (cost=0.15..8.17 rows=1 width=202) (actual time=0.007..0.007 rows=1 loops=1)
   Index Cond: (oid = 1247::oid)
 Total runtime: 0.077 ms
(3 rows)

Всё просто – у нас есть индекс, соответствующий условию, так что PostgreSQL:

  • открывает индекс;
  • в индексе, если находит, где (в данных таблицы) могут быть строки, соответствующие данному условию:
    • открывает таблицу;
    • получает строку(-и), указанную(-ые) индексом;
  • если строки могут быть возвращены – то есть, если они видимы в текущей сессии – они возвращаются.

Конечно, вы можете спросить: как строка может быть невидимой? Это может случиться с удаленными строками, которые всё ещё находятся в таблице (не были вычищены vacuum). Или со строками, которые были обновлены. Или были вставлены, но после текущей транзакции.

Index Scan также используется, когда вы хотите отсортировать какие-то данные, используя порядок сортировки в индексе, например:

explain analyze select * from pg_class order by oid limit 10;
                                                               QUERY PLAN                                                                
-----------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.15..1.67 rows=10 width=206) (actual time=0.017..0.029 rows=10 loops=1)
   ->  Index Scan using pg_class_oid_index on pg_class  (cost=0.15..44.53 rows=292 width=206) (actual time=0.014..0.026 rows=10 loops=1)
 Total runtime: 0.145 ms
(3 rows)

Здесь нет условия, но мы легко можем его добавить вот таким образом:

explain analyze select * from pg_class where oid > 1247 order by oid limit 10;
                                                               QUERY PLAN                                                               
----------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.15..4.03 rows=10 width=206) (actual time=0.021..0.035 rows=10 loops=1)
   ->  Index Scan using pg_class_oid_index on pg_class  (cost=0.15..37.84 rows=97 width=206) (actual time=0.017..0.031 rows=10 loops=1)
         Index Cond: (oid > 1247::oid)
 Total runtime: 0.132 ms
(4 rows)

В этих случаях PG находит начальную точку отсчета в индексе (либо первую строку, которая старше 1247, либо просто самую маленькую величину в индексе), а потом просто возвращает следующие строки/значения, пока условие Limit не будет удовлетворено.

Есть версия Index Scan под названием “Index Scan Backward», которая делает то же самое, но используется для сканирования в порядке по убыванию:

 

explain analyze select * from pg_class where oid < 1247 order by oid desc limit 10;
                                                                   QUERY PLAN                                                                    
-------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.15..4.03 rows=10 width=206) (actual time=0.012..0.026 rows=10 loops=1)
   ->  Index Scan Backward using pg_class_oid_index on pg_class  (cost=0.15..37.84 rows=97 width=206) (actual time=0.009..0.022 rows=10 loops=1)
         Index Cond: (oid < 1247::oid)
 Total runtime: 0.119 ms
(4 rows)

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

Ещё одна схожая операция — “Index Only Scan».

Давайте создадим простую таблицу:

create table test (id serial primary key, i int4);
CREATE TABLE
 
insert into test (i) select random() * 1000000000 from generate_series(1,100000);
INSERT 0 100000
 
vacuum analyze test;
VACUUM

Это даёт нам таблицу вроде этой:

select * from test limit 10;
 id |     i     
----+-----------
  1 | 546119592
  2 | 253476978
  3 | 235791031
  4 | 654694043
  5 | 187647296
  6 | 709050245
  7 | 210316749
  8 | 348927354
  9 | 120463097
 10 |   5611946
(10 rows)

Здесь у меня есть индекс по id:

\d test
                         Table "public.test"
 Column |  Type   |                     Modifiers                     
--------+---------+---------------------------------------------------
 id     | integer | not null default nextval('test_id_seq'::regclass)
 i      | integer | 
Indexes:
    "test_pkey" PRIMARY KEY, btree (id)

Так что, если определенные условия выполняются (чуть позже расскажу об этом подробнее), я могу получить вот такой план:

explain analyze select id from test order by id asc limit 10;
                                                             QUERY PLAN                                                             
------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.29..0.55 rows=10 width=4) (actual time=0.039..0.042 rows=10 loops=1)
   ->  Index Only Scan using test_pkey on test  (cost=0.29..2604.29 rows=100000 width=4) (actual time=0.036..0.038 rows=10 loops=1)
         Heap Fetches: 0
 Total runtime: 0.092 ms
(4 rows)

Обратите внимание на слово “Only» в “Index Only Scan».

Это значит, что Постгрес понял, что я выбираю только данные (колонки) из индекса. И, возможно, ему не нужно ничего проверять в файлах таблицы. Так что он будет возвращать данные прямо из индекса.

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

Сложность в том, что для корректной работы, Index должен содержать информацию о том, что данные строки находятся на страницах, не подвергавшихся изменениям «в последнее время». То есть, для использования Index Only Scans ваша таблица должна быть хорошо вычищена с помощью vacuum. Но, с запущенным autovacuum это не должно стать проблемой.

Последний тип сканирования таблицы – так называемый Bitmap Index Scan. Он выглядит вот так:

 

explain analyze select * from test where i < 100000;
                                                 QUERY PLAN                                                  
-------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on test  (cost=4.37..39.99 rows=10 width=8) (actual time=0.025..0.110 rows=13 loops=1)
   Recheck Cond: (i < 100000)
   ->  Bitmap Index Scan on i1  (cost=0.00..4.37 rows=10 width=0) (actual time=0.013..0.013 rows=13 loops=1)
         Index Cond: (i < 100000)
 Total runtime: 0.154 ms
(5 rows)

(если вы читаете внимательно, то заметили, что он использует индекс, о создании которого я ранее не говорил. Это легко сделать: create index i1 on test (i);).

Bitmap Scans всегда состоят, минимум, из двух узлов. Сначала (на нижнем уровне) идет Bitmap Index Scan, а затем – Bitmap Heap Scan.

Как это работает?

Допустим, в вашей таблице 100000 страниц (это около 780MB). Bitmap Index Scan создаст битовую карту, где каждой странице вашей таблицы будет соответствовать один бит. Так что, в этом случае мы получим блок памяти на 100,000 бит ~ 12.5 кБ. Все эти биты будут установлены в 0. Затем, Bitmap Index Scan установит некоторые биты в 1, в зависимости от того, на какой странице таблицы может находиться строка, которую нужно вернуть.

Эта часть вообще не затрагивает данные в таблице. После того как это будет сделано – то есть когда все страницы, на которых находятся строки, которые нужно вернуть, будут «помечены» – эта битовая карта перейдет на уровень выше, к узлу Bitmap Heap Scan, который читает их в более последовательной манере.

В чем смысл такой операции? Обычные Index Scans вызывают случайные операции ввода/вывода – страницы с диска загружаются в случайном порядке. А это медленно. По крайней мере, на вращающихся дисках.

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

Bitmap Index Scans объединяет оба случая: когда вам нужно много строк из таблицы, но не все, и когда строки, которые вы будете возвращать, находятся не в одном блоке (что было бы оправдано, если бы я производил операцию “… where id < …»). У сканирований битовых карт есть ещё одно интересное свойство – они могут объединять две операции или два индекса, как в этом примере:

explain analyze select * from test where i < 5000000 or i > 950000000;
                                                       QUERY PLAN                                                       
------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on test  (cost=107.36..630.60 rows=5323 width=8) (actual time=1.023..4.353 rows=5386 loops=1)
   Recheck Cond: ((i < 5000000) OR (i > 950000000))
   ->  BitmapOr  (cost=107.36..107.36 rows=5349 width=0) (actual time=0.922..0.922 rows=0 loops=1)
         ->  Bitmap Index Scan on i1  (cost=0.00..12.25 rows=527 width=0) (actual time=0.120..0.120 rows=491 loops=1)
               Index Cond: (i < 5000000)
         ->  Bitmap Index Scan on i1  (cost=0.00..92.46 rows=4822 width=0) (actual time=0.799..0.799 rows=4895 loops=1)
               Index Cond: (i > 950000000)
 Total runtime: 4.765 ms
(8 rows)

Здесь мы видим два сканирования Bitmap Index (их может быть больше), которые потом объединяются (но не так, как при операции “JOIN» в SQL!) с помощью BitmapOr.

Как вы помните, вывод Bitmap Index Scan – это битовая карта (блок памяти с единицами и нулями). Имея несколько таких битовых карт, вы можете легко производить на них логические операции: Or, And или Not.

Здесь мы видим, что две таких битовых карты были объединены с помощью оператора Or, и получившаяся битовая карта была передана в Bitmap Heap Scan, который загрузил подходящие строки из таблицы.

Хотя здесь оба сканирования индекса используют один и тот же индекс, так бывает не всегда. Например, давайте быстро добавим ещё несколько колонок:

alter table test add column j int4 default random() * 1000000000;
ALTER TABLE
alter table test add column h int4 default random() * 1000000000;
ALTER TABLE
create index i2 on test (j);
CREATE INDEX
create index i3 on test (h);
CREATE INDEX

А вот что получается:

explain analyze select * from test where j < 50000000 and i < 50000000 and h > 950000000;
                                                       QUERY PLAN                                                       
------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on test  (cost=280.76..323.61 rows=12 width=16) (actual time=2.295..2.352 rows=11 loops=1)
   Recheck Cond: ((h > 950000000) AND (j < 50000000) AND (i < 50000000))
   ->  BitmapAnd  (cost=280.76..280.76 rows=12 width=0) (actual time=2.278..2.278 rows=0 loops=1)
         ->  Bitmap Index Scan on i3  (cost=0.00..92.53 rows=4832 width=0) (actual time=0.546..0.546 rows=4938 loops=1)
               Index Cond: (h > 950000000)
         ->  Bitmap Index Scan on i2  (cost=0.00..93.76 rows=4996 width=0) (actual time=0.783..0.783 rows=5021 loops=1)
               Index Cond: (j < 50000000)
         ->  Bitmap Index Scan on i1  (cost=0.00..93.96 rows=5022 width=0) (actual time=0.798..0.798 rows=4998 loops=1)
               Index Cond: (i < 50000000)
 Total runtime: 2.428 ms
(10 rows)

Три сканирования Bitmap Index Scan, каждое из которых использует свой индекс, битовые карты объединены с помощью битовой операции “and», и результат скармливается Bitmap Heap Scan.

Если вы интересуетесь, почему BitmapAnd показывает “Actual rows = 0″, ответ прост: этот узел вообще не имеет дела со строками (только битовая карта страниц диска). Так что он не может вернуть строки.

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

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 в нашем случае) и, для каждой строки из неё, делает следующее:

  1. Проверяет, есть ли ключ join (pg_class.relnamespace в данном случае) в хэше, возвращенном операцией Hash.
  2. Если нет, данная строка из субоперации игнорируется (не будет возвращена).
  3. Если ключ существует, 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 раз.

Так что обработка выглядит следующим образом:

  1. Nested Loop запускает первую сторону объединения единожды. Давайте назовем её “A».
  2. Для каждой строки из “A», запускается вторая операция (назовём её “B»).
  3. Если “B» не вернула ни одной строки, данные из “A» игнорируются.
  4. Если “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 получает данные из нижележащей операции и размещает их в памяти (или частично в памяти), чтобы ими можно было быстрее воспользоваться, или добавляет им дополнительные свойства, которые предыдущая операция не предоставляет.

Unique

Название операции говорит само за себя – она удаляет дублирующие данные.

Такое может случиться, например, когда вы делаете следующее:

select distinct field from table

В более свежих версиях Постгреса этот запрос будет осуществлен с помощью HashAggregate.

Проблема Unique заключается в том, что данные для неё должны быть отсортированы. Не потому, что этой операции нужны данные в определенном порядке, а для того, чтобы все строки с одинаковыми значениями были «вместе».

Это делает Unique реально классной операцией (в тех случаях, когда её можно использовать), так как она практически не требует памяти. Она просто сравнивает значение в предыдущей строке с текущим и, если они одинаковые, отбрасывает его. Вот и всё.

Таким образом, мы можем стимулировать её использование, предварительно отсортировав данные:

$ explain select distinct relkind from (select relkind from pg_class order by relkind) as x;
                              QUERY PLAN
-----------------------------------------------------------------------
 Unique  (cost=22.88..27.26 rows=4 width=1)
   ->  Sort  (cost=22.88..23.61 rows=292 width=1)
         Sort Key: pg_class.relkind
         ->  Seq Scan on pg_class  (cost=0.00..10.92 rows=292 width=1)
(4 rows)

 

Append

Этот план просто запускает множество субопераций и возвращает все возвращенные ими строки в виде общего результата.

Это используется запросами UNION/UNION ALL:

$ explain select oid from pg_class union all select oid from pg_proc union all select oid from pg_database;
                           QUERY PLAN                            
-----------------------------------------------------------------
 Append  (cost=0.00..104.43 rows=2943 width=4)
   ->  Seq Scan on pg_class  (cost=0.00..10.92 rows=292 width=4)
   ->  Seq Scan on pg_proc  (cost=0.00..92.49 rows=2649 width=4)
   ->  Seq Scan on pg_database  (cost=0.00..1.02 rows=2 width=4)
(4 rows)

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

Обратите внимание, что я использовал UNION ALL. Если бы я использовал UNION, мы бы получили следующее:

$ explain select oid from pg_class union select oid from pg_proc union select oid from pg_database;
                              QUERY PLAN                               
-----------------------------------------------------------------------
 HashAggregate  (cost=141.22..170.65 rows=2943 width=4)
   ->  Append  (cost=0.00..133.86 rows=2943 width=4)
         ->  Seq Scan on pg_class  (cost=0.00..10.92 rows=292 width=4)
         ->  Seq Scan on pg_proc  (cost=0.00..92.49 rows=2649 width=4)
         ->  Seq Scan on pg_database  (cost=0.00..1.02 rows=2 width=4)
(5 rows)

Так происходит, потому что UNION удаляет дублируюшие строки, что в данном случае было произведено операцией HashAggregate.

Result

Result появляется, в основном, в очень простых тестовых запросах. Эта операция используется, когда ваш запрос выбирает какое-либо постоянное значение (или значения):

$ explain select 1, 2;
                QUERY PLAN                
------------------------------------------
 Result  (cost=0.00..0.01 rows=1 width=0)
(1 row)

Помимо тестовых запросов её можно встретить в запросах, которые делают что-то вроде «вставить, но только если это не будет дублированием данных»:

$ explain insert into t (i) select 1 where not exists (select * from t where i = 1);
                             QUERY PLAN                              
---------------------------------------------------------------------
 Insert on t  (cost=3.33..3.35 rows=1 width=4)
   ->  Result  (cost=3.33..3.34 rows=1 width=0)
         One-Time Filter: (NOT $0)
         InitPlan 1 (returns $0)
           ->  Seq Scan on t t_1  (cost=0.00..40.00 rows=12 width=0)
                 Filter: (i = 1)
(6 rows)

 

Values Scan

Так же, как Result, Values Scan используется для возвращения простых введенных в запросе данных, но в данном случае это может быть целый набор записей, основанный на функциональности VALUES().

Если вдруг вы не в курсе, вы можете выбрать множество строк и множество столбцов без какой-либо таблицы, просто используя синтаксис VALUES, как в этом примере:

$ select * from ( values (1, 'hubert'), (2, 'depesz'), (3, 'lubaczewski') ) as t (a,b);
 a |      b      
---+-------------
 1 | hubert
 2 | depesz
 3 | lubaczewski
(3 rows)

План такого запроса выглядит следующим образом:

                          QUERY PLAN                          
--------------------------------------------------------------
 Values Scan on "*VALUES*"  (cost=0.00..0.04 rows=3 width=36)
(1 row)

Эта операция обычно используется в INSERT’ах, но у неё есть и другие способы применения, например, кастомная сортировка.

GroupAggregate

Эта операция схожа с HashAggregate, о которой мы говорили ранее.

Разница в том, что для работы GroupAggregate данные должны быть отсортированы с помощью того столбца или столбцов, которые вы использовали в условии GROUP BY.

Как и Unique, GroupAggregate использует очень мало памяти, но требует упорядоченности данных.

Пример:

$ explain select relkind, count(*) from (select relkind from pg_class order by relkind) x group by relkind;
                              QUERY PLAN                               
-----------------------------------------------------------------------
 GroupAggregate  (cost=22.88..28.03 rows=4 width=1)
   ->  Sort  (cost=22.88..23.61 rows=292 width=1)
         Sort Key: pg_class.relkind
         ->  Seq Scan on pg_class  (cost=0.00..10.92 rows=292 width=1)
(4 rows)

 

HashSetOp

Эта операция используется операциями INTERSECT/EXCEPT (с опциональным модификатором «ALL»).

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

Мы видим, что, в отличие от UNION, эти операции работают с двумя источниками данных:

$ explain select * from (select oid from pg_Class order by oid) x intersect all select * from (select oid from pg_proc order by oid) y;
                                                 QUERY PLAN                                                  
-------------------------------------------------------------------------------------------------------------
 HashSetOp Intersect All  (cost=0.15..170.72 rows=292 width=4)
   ->  Append  (cost=0.15..163.36 rows=2941 width=4)
         ->  Subquery Scan on "*SELECT* 1"  (cost=0.15..18.37 rows=292 width=4)
               ->  Index Only Scan using pg_class_oid_index on pg_class  (cost=0.15..12.53 rows=292 width=4)
         ->  Subquery Scan on "*SELECT* 2"  (cost=0.28..145.00 rows=2649 width=4)
               ->  Index Only Scan using pg_proc_oid_index on pg_proc  (cost=0.28..92.02 rows=2649 width=4)
(6 rows)

А с тремя источниками у нас получится более сложное дерево:

$ explain select * from (select oid from pg_Class order by oid) x intersect all select * from (select oid from pg_proc order by oid) y intersect all select * from (Select oid from pg_database order by oid) as w;
                                                          QUERY PLAN                                                           
-------------------------------------------------------------------------------------------------------------------------------
 HashSetOp Intersect All  (cost=1.03..172.53 rows=2 width=4)
   ->  Append  (cost=1.03..171.79 rows=294 width=4)
         ->  Subquery Scan on "*SELECT* 3"  (cost=1.03..1.07 rows=2 width=4)
               ->  Sort  (cost=1.03..1.03 rows=2 width=4)
                     Sort Key: pg_database.oid
                     ->  Seq Scan on pg_database  (cost=0.00..1.02 rows=2 width=4)
         ->  Result  (cost=0.15..170.72 rows=292 width=4)
               ->  HashSetOp Intersect All  (cost=0.15..170.72 rows=292 width=4)
                     ->  Append  (cost=0.15..163.36 rows=2941 width=4)
                           ->  Subquery Scan on "*SELECT* 1"  (cost=0.15..18.37 rows=292 width=4)
                                 ->  Index Only Scan using pg_class_oid_index on pg_class  (cost=0.15..12.53 rows=292 width=4)
                           ->  Subquery Scan on "*SELECT* 2"  (cost=0.28..145.00 rows=2649 width=4)
                                 ->  Index Only Scan using pg_proc_oid_index on pg_proc  (cost=0.28..92.02 rows=2649 width=4)
(13 rows)

 

CTE Scan

Эта операция схожа с уже упомянутой операцией Materialize. Она запускает часть запроса и сохраняет ее вывод, чтобы он мог быть использован другой частью (или частями) запроса.

Пример:

$ explain analyze with x as (select relname, relkind from pg_class) select relkind, count(*), (select count(*) from x) from x group by relkind;
                                                   QUERY PLAN                                                    
-----------------------------------------------------------------------------------------------------------------
 HashAggregate  (cost=24.80..26.80 rows=200 width=1) (actual time=0.466..0.468 rows=6 loops=1)
   CTE x
     ->  Seq Scan on pg_class  (cost=0.00..10.92 rows=292 width=65) (actual time=0.009..0.127 rows=295 loops=1)
   InitPlan 2 (returns $1)
     ->  Aggregate  (cost=6.57..6.58 rows=1 width=0) (actual time=0.085..0.085 rows=1 loops=1)
           ->  CTE Scan on x x_1  (cost=0.00..5.84 rows=292 width=0) (actual time=0.000..0.055 rows=295 loops=1)
   ->  CTE Scan on x  (cost=0.00..5.84 rows=292 width=1) (actual time=0.012..0.277 rows=295 loops=1)
 Total runtime: 0.524 ms
(8 rows)

Обратите внимание, что pg_class сканируется всего один раз – строка #6. Но его результаты хранятся в “x» и потом сканируются дважды – внутри агрегата (строка #9) и операцией HashAggregate (10).

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

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

InitPlan

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

Допустим, вы хотите вот такой запрос:

$ explain select * from pg_class where relkind = (select relkind from pg_class order by random() limit 1);
                                        QUERY PLAN                                        
------------------------------------------------------------------------------------------
 Seq Scan on pg_class  (cost=13.11..24.76 rows=73 width=203)
   Filter: (relkind = $0)
   InitPlan 1 (returns $0)
     ->  Limit  (cost=13.11..13.11 rows=1 width=1)
           ->  Sort  (cost=13.11..13.84 rows=292 width=1)
                 Sort Key: (random())
                 ->  Seq Scan on pg_class pg_class_1  (cost=0.00..11.65 rows=292 width=1)
(7 rows)

В этом случае необходимо запустить limit/sort/seq-scan до обычного последовательного сканирования по pg_class, потому что Постгресу нужно будет сравнить значение relkind со значением, возвращенным подзапросом.

С другой стороны, я мог бы написать:

$ explain select *, (select length('depesz')) from pg_class;
                         QUERY PLAN                          
-------------------------------------------------------------
 Seq Scan on pg_class  (cost=0.01..10.93 rows=292 width=203)
   InitPlan 1 (returns $0)
     ->  Result  (cost=0.00..0.01 rows=1 width=0)
(3 rows)

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

Конечно, у вас может быть много единичных планов (init plans), как здесь:

$ explain select *, (select length('depesz')) from pg_class where relkind = (select relkind from pg_class order by random() limit 1);
                                        QUERY PLAN                                        
------------------------------------------------------------------------------------------
 Seq Scan on pg_class  (cost=13.12..24.77 rows=73 width=203)
   Filter: (relkind = $1)
   InitPlan 1 (returns $0)
     ->  Result  (cost=0.00..0.01 rows=1 width=0)
   InitPlan 2 (returns $1)
     ->  Limit  (cost=13.11..13.11 rows=1 width=1)
           ->  Sort  (cost=13.11..13.84 rows=292 width=1)
                 Sort Key: (random())
                 ->  Seq Scan on pg_class pg_class_1  (cost=0.00..11.65 rows=292 width=1)
(9 rows)

Но стоит учитывать одну деталь – init plan’ы внутри одного запроса нумеруются «глобально», а не по операциям.

SubPlan

SubPlan’ы чем-то похожи на NestedLoop. В том смысле, что они тоже могут вызываться много раз.

SubPlan вызывается, чтобы посчитать данные из субзапроса, которые реально зависят от текущей строки.

Например:

$ explain analyze select c.relname, c.relkind, (Select count(*) from pg_Class x where c.relkind = x.relkind) from pg_Class c;
                                                      QUERY PLAN                                                       
-----------------------------------------------------------------------------------------------------------------------
 Seq Scan on pg_class c  (cost=0.00..3468.93 rows=292 width=65) (actual time=0.135..26.717 rows=295 loops=1)
   SubPlan 1
     ->  Aggregate  (cost=11.83..11.84 rows=1 width=0) (actual time=0.090..0.090 rows=1 loops=295)
           ->  Seq Scan on pg_class x  (cost=0.00..11.65 rows=73 width=0) (actual time=0.010..0.081 rows=93 loops=295)
                 Filter: (c.relkind = relkind)
                 Rows Removed by Filter: 202
 Total runtime: 26.783 ms
(7 rows)

Для каждой строки, возвращенной сканированием по «pg_class as c», Постгрес должен запустить SubPlan, который проверяет, сколько строк в pg_class имеют такое же (как у только что обработанной строки) значение в столбце relkind.

Обратите внимание на «loops=295» в строке «Seq Scan on pg_class x» и соответствующее ему значение «rows=295» в узле «Seq Scan on pg_class c».

Другие?

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

Если у вас есть план с операцией, о которой я не рассказал, и вам он непонятен, напишите мне, пожалуйста, в комментариях ссылку на вывод explain на explain.depesz.com, название операции и версию Посгреса, в которой она вам встретилась. Я постараюсь найти всю возможную информацию по таким кейсам и дать вам развернутый ответ.

В заключительном посте я постараюсь объяснить, почему Постгрес выбирает «Операцию X», а не «Операцию Y».

Возможно, вы слышали, что планировщик PostgreSQL выбирает операции, основываясь на статистике. Какой статистике?

Давайте представим самый простой сценарий из возможных:

SELECT * FROM table WHERE column = some_value;

Если у всех строк в таблиц одинаковое значение some_value, тогда применение к столбцу индекса (потенциально существующего) не имеет смысла.

С другой стороны, если значения в столбце уникальны (или почти уникальны), использование индекса – отличная идея.

Давайте посмотрим, что происходит:

create table test ( all_the_same int4, almost_unique int4 );
CREATE TABLE
 
insert into test ( all_the_same, almost_unique )
    select 123, random() * 1000000 from generate_series(1,100000);
INSERT 0 100000

Итак, у меня есть таблица на 100,000 строк, в которой столбец «all_the_same» всегда имеет одинаковые значения (123), а столбец almost_unique, как понятно из названия, почти уникален:

select count(*), count(distinct almost_unique) from test;
 count  | count 
--------+-------
 100000 | 95142
(1 row)

Теперь, чтобы сделать их равными, я создам два простых индекса:

create index i1 on test (all_the_same);
CREATE INDEX
 
create index i2 on test (almost_unique);
CREATE INDEX

Ок, тестовая конфигурация готова. А как насчет планов?

explain select * from test where all_the_same = 123;
                         QUERY PLAN                         
------------------------------------------------------------
 Seq Scan on test  (cost=0.00..1693.00 rows=100000 width=8)
   Filter: (all_the_same = 123)
(2 rows)
 
explain select * from test where almost_unique = 123;
                          QUERY PLAN                           
---------------------------------------------------------------
 Index Scan using i2 on test  (cost=0.29..8.31 rows=1 width=8)
   Index Cond: (almost_unique = 123)
(2 rows)

Как видите, Постгрес сделал мудрый выбор. Но здесь вызывает интерес оценочное значение «rows=». Откуда он знает, сколько строк может вернуть запрос?
Ответ лежит в команде ANALYZE или VACUUM ANALYZE.

Когда вы применяете к таблице «ANALYZE», Постгрес берет некий «случайный образец» (random sample) (через секунду расскажу об этом подробнее) и получает какие-то статистические данные. Что это за статистика, где она, и можем ли мы её увидеть? Конечно, можем:

select * from pg_statistic where starelid = 'test'::regclass;
-[ RECORD 1 ]-----------------------------------------------------------------------------
starelid    | 16882
staattnum   | 1
stainherit  | f
stanullfrac | 0
stawidth    | 4
stadistinct | 1
stakind1    | 1
stakind2    | 3
stakind3    | 0
stakind4    | 0
stakind5    | 0
staop1      | 96
staop2      | 97
staop3      | 0
staop4      | 0
staop5      | 0
stanumbers1 | {1}
stanumbers2 | {1}
stanumbers3 | [null]
stanumbers4 | [null]
stanumbers5 | [null]
stavalues1  | {123}
stavalues2  | [null]
stavalues3  | [null]
stavalues4  | [null]
stavalues5  | [null]
-[ RECORD 2 ]-----------------------------------------------------------------------------
starelid    | 16882
staattnum   | 2
stainherit  | f
stanullfrac | 0
stawidth    | 4
stadistinct | -0.92146
stakind1    | 1
stakind2    | 2
stakind3    | 3
stakind4    | 0
stakind5    | 0
staop1      | 96
staop2      | 97
staop3      | 97
staop4      | 0
staop5      | 0
stanumbers1 | {0.0001,0.0001,0.0001,0.0001,0.0001,0.0001,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05}
stanumbers2 | [null]
stanumbers3 | {-0.000468686}
stanumbers4 | [null]
stanumbers5 | [null]
stavalues1  | {21606,27889,120502,289914,417495,951355,283,1812,3774,6028,6229,10372,12234,13291,18309,18443,21758,22565,26634,28392,28413,31208,32890,36563,39277,40574,44527,49954,53344,53863,56492,56715,60856,62993,64294,65275,65355,68353,71194,74718,77205,82096,82783,84764,85301,87498,90990,94043,97304,98779,101181,103700,103889,106288,108562,110796,113154,117850,121578,122643,123874,126299,129236,129332,129512,134430,134980,136987,137368,138175,139001,141519,142934,143432,143707,144501,148633,152481,154327,157067,157799,162437,164072,164337,165942,167611,170319,171047,177383,184134,188702,189005,191786,192718,196330,197851,199457,202652,202689,205983}
stavalues2  | {2,10560,20266,31061,40804,50080,59234,69240,79094,89371,99470,109557,119578,130454,140809,152052,162656,173855,183914,194263,204593,214876,224596,233758,243246,253552,264145,273855,283780,294475,303972,314544,324929,335008,346169,356505,367395,376639,387302,397004,407093,416615,426646,436146,445701,455588,466463,475910,485228,495434,505425,515853,525374,534824,545387,554794,563591,573721,584021,593368,602935,613238,623317,633947,643431,653397,664177,673976,684042,694791,703922,714113,724602,735848,745596,754477,764171,772535,781924,791652,801703,812487,822196,831618,841665,850722,861532,872067,881570,891654,901595,910975,921698,931785,940716,950623,960551,970261,979855,989540,999993}
stavalues3  | [null]
stavalues4  | [null]
stavalues5  | [null]

Эта таблица (pg_statistic), безусловно, описана в документации, но всё равно довольно загадочна. Конечно, вы можете найти очень точное объяснение в исходниках, но это (обычно) не лучшее решение.

К счастью, существует view для этой таблицы, который содержит те же самые данные в более «читабельном» представлении:

select * from pg_stats where tablename = 'test';
-[ RECORD 1 ]----------+------------------------------------------------------------------
schemaname             | public
tablename              | test
attname                | all_the_same
inherited              | f
null_frac              | 0
avg_width              | 4
n_distinct             | 1
most_common_vals       | {123}
most_common_freqs      | {1}
histogram_bounds       | [null]
correlation            | 1
most_common_elems      | [null]
most_common_elem_freqs | [null]
elem_count_histogram   | [null]
-[ RECORD 2 ]----------+------------------------------------------------------------------
schemaname             | public
tablename              | test
attname                | almost_unique
inherited              | f
null_frac              | 0
avg_width              | 4
n_distinct             | -0.92146
most_common_vals       | {21606,27889,120502,289914,417495,951355,283,1812,3774,6028,6229,10372,12234,13291,18309,18443,21758,22565,26634,28392,28413,31208,32890,36563,39277,40574,44527,49954,53344,53863,56492,56715,60856,62993,64294,65275,65355,68353,71194,74718,77205,82096,82783,84764,85301,87498,90990,94043,97304,98779,101181,103700,103889,106288,108562,110796,113154,117850,121578,122643,123874,126299,129236,129332,129512,134430,134980,136987,137368,138175,139001,141519,142934,143432,143707,144501,148633,152481,154327,157067,157799,162437,164072,164337,165942,167611,170319,171047,177383,184134,188702,189005,191786,192718,196330,197851,199457,202652,202689,205983}
most_common_freqs      | {0.0001,0.0001,0.0001,0.0001,0.0001,0.0001,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05}
histogram_bounds       | {2,10560,20266,31061,40804,50080,59234,69240,79094,89371,99470,109557,119578,130454,140809,152052,162656,173855,183914,194263,204593,214876,224596,233758,243246,253552,264145,273855,283780,294475,303972,314544,324929,335008,346169,356505,367395,376639,387302,397004,407093,416615,426646,436146,445701,455588,466463,475910,485228,495434,505425,515853,525374,534824,545387,554794,563591,573721,584021,593368,602935,613238,623317,633947,643431,653397,664177,673976,684042,694791,703922,714113,724602,735848,745596,754477,764171,772535,781924,791652,801703,812487,822196,831618,841665,850722,861532,872067,881570,891654,901595,910975,921698,931785,940716,950623,960551,970261,979855,989540,999993}
correlation            | -0.000468686
most_common_elems      | [null]
most_common_elem_freqs | [null]
elem_count_histogram   | [null]

Отлично. Так какие же знания мы можем отсюда почерпнуть?

Столбцы schemaname, tablename и attname кажутся очевидными. Inherited просто сообщает, содержат ли значения этой таблицы значения из любых таблиц, которые унаследовали этот столбец.

Так что, если бы я создал таблицу:

create table z () inherits (test);

А потом добавил в эту таблицу z какие-то данные, то статистика таблицы test показала бы «inherited = true».

Остальные столбцы означают следующее:

  • null_frac — сколько строк имеют значение null в данном столбце. Это доля, поэтому значение будет от 0 до 1.
  • avg_width — средняя ширина (прим. пер.: размер) данных в этом столбце. Это не очень интересно, если ширина постоянна (как у int4 в этом примере), а вот в случае с любыми типами данных с переменной шириной (как у text/varchar/numeric) это может пригодиться.
  • n_distinct — очень интересная величина. Если она положительная (1+), то это будет просто ориентировочное число (не доля!) различных значений, как мы видим в случае со столбцом all_the_same, где n_distinct справедливо равна 1. А если она отрицательная, то смысл меняется: n_distinct показывает, какая доля строк имеет уникальное значение. Поэтому, в случае с almost_unique статистика полагает, что 92.146% строк имеют уникальное значение (что немного меньше 95.142%, которые я показывал ранее). Значения могут быть неверны из-за той штуки с «случайным образцом», которую я уже упоминал и чуть позже объясню подробно.
  • most_common_vals — массив наиболее распространенных значений в этой таблице.
  • most_common_freqs — как часто встречаются значения из most_common_vals — это тоже доля, так что максимальное значение — 1 (но это будет означать, что у нас всего одно значение в most_common_vals). Здесь, в almost_unique, мы видим, что Постгрес «думает», что значения 21606, 27889, 120502, 289914, 417495, 951355 встречаются чаще всего, но это не так. Опять же, во всём виноват эффект «случайного образца».
  • histogram_bounds — массив значений, который делит (или должен делить — снова всё упирается в «случайный образец») весь набор данных на группы с одинаковым количеством строк. То есть количество строк almost_unique между 2 и 10560 такое же (более-менее), как и количество строк almost_unique между 931785 и 940716.
  • correlation — это очень интересная статистика, она показывает, есть ли корреляция между физической сортировкой строк на диске и значениями. Эта величина может меняться от -1 до 1, и чем ближе она к -1/1, тем больше корреляция. Например, после запуска «CLUSTER test using i2», который пересортировывает таблицу в порядке almost_unique, я получил корреляцию 0.919358 — гораздо лучше по сравнению с предыдущим значением -0.000468686.
    most_common_elems, most_common_elem_freqs и elem_count_histogram такие же, как most_common_vals, most_common_freqs и histogram_bounds, но для нескалярных типов данных (то есть, arrays, tsvectors и alike).

Основываясь на этих данных, PostgreSQL может приблизительно оценить, сколько строк будет возвращено любой выбранной частью запроса, и, исходя из этой информации, решить, что лучше использовать: seq scan, index scan или bitmap index scan. А при объединении — какая операция должна быть быстрее: Hash Join, Merge Join или, быть может, Nested Loop.

Если вы внимательно изучили представленные выше данные, то могли задаться вопросом: это достаточно обширный набор выходных данных, в массивах most_common_vals/most_common_freqs/histogram_bounds содержится много значений. Почему же их так много?

Причина проста — всё дело в настройках. В postgresql.conf вы можете найти переменную default_statistics_target. Эта переменная говорит Постгресу, сколько значений хранить в этих массивах. В моём случае (по умолчанию) это число равно 100. Но вы можете легко изменить его. Внести изменение в postgresql.conf, или даже для каждого отдельно взятого столбца вот таким образом:

alter table test alter column almost_unique set statistics 5;

После применения ALTER (и ANALYZE) данные в pg_stats существенно укорачиваются:

select * from pg_stats where tablename = 'test' and not inherited and attname = 'almost_unique';
-[ RECORD 1 ]----------+---------------------------------------------------------
schemaname             | public
tablename              | test
attname                | almost_unique
inherited              | f
null_frac              | 0
avg_width              | 4
n_distinct             | -0.92112
most_common_vals       | {114832,3185,3774,6642,11984}
most_common_freqs      | {0.0001,6.66667e-05,6.66667e-05,6.66667e-05,6.66667e-05}
histogram_bounds       | {2,199470,401018,596414,798994,999964}
correlation            | 1
most_common_elems      | [null]
most_common_elem_freqs | [null]
elem_count_histogram   | [null]

Изменение statistic target также имеет ещё один эффект.

Давайте я вам покажу. Для начала я откачу изменения в подсчете статистики, которые я внёс с помощью ALTER TABLE:

alter table test alter column almost_unique set statistics -1;

А теперь сделаем следующее:

$ analyze verbose test;
INFO:  analyzing "public.test"
INFO:  "test": scanned 443 of 443 pages, containing 100000 live rows and 0 dead rows; 30000 rows in sample, 100000 estimated total rows
ANALYZE
 
$ alter table test alter column almost_unique set statistics 10;
ALTER TABLE
 
$ alter table test alter column all_the_same set statistics 10;
ALTER TABLE
 
$ analyze verbose test;
INFO:  analyzing "public.test"
INFO:  "test": scanned 443 of 443 pages, containing 100000 live rows and 0 dead rows; 3000 rows in sample, 100000 estimated total rows
ANALYZE

Заметьте, что второй analyze протестировал всего 3000 строк, а не 30000, как первый.

Это и есть «случайный образец».

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

Поэтому Постгрес поступает умнее.

Во-первых, он читает случайную часть страниц в таблице (напоминаю: каждая страница — это 8кБ данных). Сколько именно? 300 * statistics_target.

Это значит, что в моём случае с default_statistics_target = 100 он прочитает 30000 страниц (в моей таблице столько нет, поэтому Постгрес прочитает их все).

Из этих страниц ANALYZE берет только информацию о живых и мёртвых строках. Затем он получает данные о случайном образце строк — снова 300 * statistics target — и считает статистику по столбцу, основываясь на этих данных.

В моём случае в таблице было 100,000 строк, но с default_statistics_target = 100 только треть была проанализирована. А, с учетом значения statistics target, количество проанализированных строк ещё меньше — всего 3000.

Вы могли бы сказать: ОК, но в таком случае эта статистика неточная. Может так случиться, что какое-нибудь супер-распространенное значение не попалось ни в одной из просканированных строк. Конечно, вы правы. Это возможно. Хотя и не слишком вероятно. Вы берете случайную часть данных. Шансы, что вы получите x% таблицы, в которой нет ни одной строки с каким-то значением, которое присутствует во всех остальных строках, ничтожно малы.

Это также значит, что в некоторых случаях запуск analyze будет «ломать» ваши запросы. Например, вы получите статистику по другим страницам, и выйдет так, что некоторые значения окажутся пропущены (или наоборот — вы получите в most_common_vals не такие уж распространенные значения, просто так получилось, что Постгрес выбрал подходящие страницы/строки, чтобы их увидеть). И на основании такой статистики Pg будет генерировать неоптимальные планы.

Если вы столкнётесь с такой ситуацией, решить её достаточно просто — увеличьте statistics target. Это заставит analyze работать усерднее и сканировать больше строк, поэтому шансы, что подобное повторится, станут ещё меньше.

Но в установке больших значений statistics target есть определенные недостатки. Во-первых, ANALYZE приходится больше работать, но это вопрос эксплуатации, так что он нас не слишком волнует (обычно). Основная же проблема заключается в том, что, чем больше данных в pg_statistic, тем больше данных должно приниматься во внимание планировщиком Pg. Поэтому, как бы ни было заманчиво установить default_statistics_target на максимум в 10,000, в реальности я не встречал баз данных, в которых это значение было бы таким высоким.

Текущие 100 по умолчанию установлены, начиная с версии 8.4. В предыдущих версиях значение по-умолчанию было 10, и на irc часто встречались советы его увеличить. Теперь со значением 100 всё более-менее настроено.

Последнее, о чем мне придётся рассказать, хоть и не очень хочется, — настройки, которые заставляют планировщик Постгреса использовать разные операции.

Во-первых, объясню, почему мне не хочется об этом говорить: я точно знаю, что этим можно легко злоупотребить. Так что запомните: эти настройки нужны для поиска проблем, а не для их решения. Приложение, которое будет использовать их в рабочем режиме, можно, как минимум, заподозрить в том, что оно сломано. И да, я знаю, что иногда приходится так делать. Но это «иногда» случается крайне редко.

Теперь, когда я вас предупредил, давайте посмотрим, что можно сделать.

В postgresql.conf у вас есть несколько настроек:

enable_bitmapscan = on
enable_hashagg = on
enable_hashjoin = on
enable_indexscan = on
enable_indexonlyscan = on
enable_material = on
enable_mergejoin = on
enable_nestloop = on
enable_seqscan = on
enable_sort = on
enable_tidscan = on

Эти настройки нужны для отключения выбранных операций.

Например, переключение enable_seqscan на false (это можно сделать с помощью команды SET в сессии SQL, вам не нужно изменять postgresql.conf) приведёт к тому, что планировщик будет использовать всё, что только можно, дабы избежать последовательного сканирования.

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

Приведем пример. В отношении нашей тестовой таблицы мы знаем, что поиск с помощью «all_the_same = 123» будет использовать последовательное сканирование, потому что оно не требует больших затрат:

explain select * from test where all_the_same = 123;
                         QUERY PLAN                         
------------------------------------------------------------
 Seq Scan on test  (cost=0.00..1693.00 rows=100000 width=8)
   Filter: (all_the_same = 123)
(2 rows)

Но если мы отключим seq scan:

set enable_seqscan = false;
SET
explain select * from test where all_the_same = 123;
                              QUERY PLAN                               
-----------------------------------------------------------------------
 Index Scan using i1 on test  (cost=0.29..3300.29 rows=100000 width=8)
   Index Cond: (all_the_same = 123)
(2 rows)

Мы видим, что оценочная стоимость получения тех же данных с помощью index scan ~ в два раза выше (3300.29 против 1693).

Если я удалю i1 индекс:

drop index i1;
DROP INDEX
set enable_seqscan = false;
SET
explain select * from test where all_the_same = 123;
                                 QUERY PLAN                                  
-----------------------------------------------------------------------------
 Seq Scan on test  (cost=10000000000.00..10000001693.00 rows=100000 width=8)
   Filter: (all_the_same = 123)
(2 rows)

И мы видим, что, когда других возможностей, кроме последовательного сканирования, нет (интересно, что Постгрес не выбрал провести index scan по i2, хотя у этого индекса есть указатели на все строки в таблице), затраты взлетели до 10,000,000,000 — именно это enable_* = false и делает.

Думаю, на этом всё. Если вы прочитали всю серию, теперь вам должно хватать знаний, чтобы понимать, что происходит и, что важнее, — почему.

Добавить комментарий