# Индексное сканирование

Рассмотрим таблицу бронирований:

    => \d bookings

                            Table "bookings.bookings"
        Column    |           Type           | Collation | Nullable | Default
    --------------+--------------------------+-----------+----------+---------
     book_ref     | character(6)             |           | not null |
     book_date    | timestamp with time zone |           | not null |
     total_amount | numeric(10,2)            |           | not null |
    Indexes:
        "bookings_pkey" PRIMARY KEY, btree (book_ref)
    Referenced by:
        TABLE "tickets" CONSTRAINT "tickets_book_ref_fkey" FOREIGN KEY (book_ref) REFERENCES bookings(book_ref)

Столбец book_ref является первичным ключом и для него автоматически был создан индекс bookings_pkey.

Проверим план запроса с поиском одного значения:

    => EXPLAIN SELECT * FROM bookings WHERE book_ref = 'CDE08B';

                                      QUERY PLAN
    -------------------------------------------------------------------------------
     Index Scan using bookings_pkey on bookings  (cost=0.43..8.45 rows=1 width=21)
       Index Cond: (book_ref = 'CDE08B'::bpchar)
    (2 rows)

Выбран метод доступа Index Scan, указано имя использованного индекса. Строкой ниже указано условие доступа.

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

Второе число - оценка чтения необходимых листовых страниц индекса и табличных страниц. Не стоит забывать, что один узел Index Scan подразумевает обращение и к индексу, и к таблице.

В данном случае, поскольку индекс уникальный, будет прочитана одна индексная страница и одна табличная. Каждое из чтений оценивается параметром random_page_cost:

    => SELECT current_setting('random_page_cost');

     current_setting
    -----------------
     4
    (1 row)

Его значение обычно больше, чем seq_page_cost, поскольку произвольный доступ стоит дороже (хотя для SSD-дисков этот параметр следует существенно уменьшать).

Итого получаем 8, и еще немного добавляет оценка процессорного времени на обработку строк.

В строке Index Cond плана указываются только те условия, по которым происходит обращение к индексу или которые могут быть проверены на уровне индекса.

Дополнительные условия, которые можно проверить только по таблице, отображаются в отдельной строке Filter:

    => EXPLAIN SELECT * FROM bookings
      WHERE book_ref = 'CDE08B' AND total_amount > 1000;

                                      QUERY PLAN
    -------------------------------------------------------------------------------
     Index Scan using bookings_pkey on bookings  (cost=0.43..8.45 rows=1 width=21)
       Index Cond: (book_ref = 'CDE08B'::bpchar)
       Filter: (total_amount > '1000'::numeric)
    (3 rows)

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

Индексное сканирование может выполняться в параллельном режиме. В качестве примера найдем сумму одной четверти всех бронирований:

    => EXPLAIN SELECT sum(total_amount) FROM bookings WHERE book_ref < '400000';

                                                        QUERY PLAN
    ------------------------------------------------------------------------------------------------------------------
     Finalize Aggregate  (cost=17164.90..17164.91 rows=1 width=32)
       ->  Gather  (cost=17164.67..17164.88 rows=2 width=32)
             Workers Planned: 2
             ->  Partial Aggregate  (cost=16164.67..16164.68 rows=1 width=32)
                   ->  Parallel Index Scan using bookings_pkey on bookings  (cost=0.43..15604.65 rows=224008 width=6)
                         Index Cond: (book_ref < '400000'::bpchar)
    (6 rows)

Аналогичный план мы уже видели при параллельном последовательном сканировании, но в данном случае данные читаются с помощью индекса - узел Parallel Index Scan.

Стоимость обусловлена двумя составляющими. Во-первых, стоимость доступа к 1/4 табличных страниц (поделенных между процессами) - аналогично последовательному сканированию:

    => SELECT round(
      (relpages / 4.0) * current_setting('seq_page_cost')::real +
      (reltuples / 4.0) / 2.4 * current_setting('cpu_tuple_cost')::real
    ) FROM pg_class WHERE relname = 'bookings';

     round
    -------
      5561
    (1 row)

Вторая составляющая - индексный доступ (не делится между процессами, так как индекс читается процессами последовательно, страница за страницей):

    => SELECT round(
      (relpages / 4.0) * current_setting('random_page_cost')::real +
      (reltuples / 4.0) * current_setting('cpu_index_tuple_cost')::real +
      (reltuples / 4.0) * current_setting('cpu_operator_cost')::real
    ) FROM pg_class WHERE relname = 'bookings_pkey';

     round
    -------
      9750
    (1 row)

Стоимость cpu_operator_cost учитывает необходимость сравнения значений (операция "меньше либо равно").

# Исключительно индексное сканирование

Если вся необходимая информация содержится в самом индексе, то нет необходимости обращаться к таблице - за исключением проверки видимости:

    => EXPLAIN SELECT book_ref FROM bookings WHERE book_ref <= '100000';

                                            QUERY PLAN
    -------------------------------------------------------------------------------------------
     Index Only Scan using bookings_pkey on bookings  (cost=0.43..4854.01 rows=139176 width=7)
       Index Cond: (book_ref <= '100000'::bpchar)
    (2 rows)

Посмотрим план с помощью EXPLAIN ANALYZE. Этот вариант команды EXPLAIN не просто показывает план, но и реально выполняет запрос, и вывод содержит больше полезных сведений.

    => EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF)
      SELECT book_ref FROM bookings WHERE book_ref <= '100000';

                                      QUERY PLAN
    ------------------------------------------------------------------------------
     Index Only Scan using bookings_pkey on bookings (actual rows=132109 loops=1)
       Index Cond: (book_ref <= '100000'::bpchar)
       Heap Fetches: 132109
     Planning time: 0.076 ms
     Execution time: 58.121 ms
    (5 rows)

Строка Heap Fetches показывает, сколько строк было проверено с помощью таблицы. Почему пришлось обращаться к таблице в нашем случае?

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

    => SELECT vacuum_count, autovacuum_count FROM pg_stat_all_tables
      WHERE relname='bookings';

     vacuum_count | autovacuum_count
    --------------+------------------
                0 |                0
    (1 row)

    => VACUUM bookings;

    VACUUM

    => EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF)
      SELECT book_ref FROM bookings WHERE book_ref <= '100000';

                                      QUERY PLAN
    ------------------------------------------------------------------------------
     Index Only Scan using bookings_pkey on bookings (actual rows=132109 loops=1)
       Index Cond: (book_ref <= '100000'::bpchar)
       Heap Fetches: 0
     Planning time: 0.137 ms
     Execution time: 53.357 ms
    (5 rows)

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

# Параллельное исключительно индексное сканирование

Исключительно индексное сканирование также может выполняться параллельно.

    => EXPLAIN SELECT count(book_ref) FROM bookings WHERE book_ref <= '400000';

                                                          QUERY PLAN
    -----------------------------------------------------------------------------------------------------------------------
     Finalize Aggregate  (cost=13736.89..13736.90 rows=1 width=8)
       ->  Gather  (cost=13736.67..13736.88 rows=2 width=8)
             Workers Planned: 2
             ->  Partial Aggregate  (cost=12736.67..12736.68 rows=1 width=8)
                   ->  Parallel Index Only Scan using bookings_pkey on bookings  (cost=0.43..12176.65 rows=224008 width=7)
                         Index Cond: (book_ref <= '400000'::bpchar)
    (6 rows)

Стоимость доступа к таблице здесь учитывает только обработку строк, без ввода-вывода:

    => SELECT round(
      (reltuples / 4.0) / 2.4 * current_setting('cpu_tuple_cost')::real
    ) FROM pg_class WHERE relname = 'bookings';

     round
    -------
      2199
    (1 row)

Вклад индексного доступа остается прежним.

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

# Сортировка

Есть два способа выполнить сортировку. Первый - получить строки сканированием подходящего индекса: в этом случае данные автоматически будут отсортированы.

    => EXPLAIN SELECT * FROM flights ORDER BY flight_id;

                                         QUERY PLAN
    -------------------------------------------------------------------------------------
     Index Scan using flights_pkey on flights  (cost=0.42..7558.54 rows=214867 width=63)
    (1 row)

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

    => EXPLAIN SELECT * FROM flights ORDER BY flight_id DESC;

                                              QUERY PLAN
    ----------------------------------------------------------------------------------------------
     Index Scan Backward using flights_pkey on flights  (cost=0.42..7558.54 rows=214867 width=63)
    (1 row)

В этом случае мы спускаемся от корня дерева к правому листовому узлу, и проходим по списку листовых страниц в обратном порядке.

Второй способ - выполнить последовательное сканирование таблицы и затем отсортировать полученные данные. Чтобы посмотреть на план такого запроса, запретим индексный доступ (аналогично можно запретить и другие методы доступа):

    => SET enable_indexscan = off;

    SET

    => EXPLAIN SELECT * FROM flights ORDER BY flight_id;

                                  QUERY PLAN
    ----------------------------------------------------------------------
     Sort  (cost=31675.96..32213.12 rows=214867 width=63)
       Sort Key: flight_id
       ->  Seq Scan on flights  (cost=0.00..4564.67 rows=214867 width=63)
    (3 rows)

Здесь появляется узел Sort, получающий данные и сортирующий их.

Чтобы выполнить сортировку, надо получить весь набор данных полностью. Это неэффективно, если в результате требуется только часть выборки. Обратите внимание на стоимость:

    => EXPLAIN SELECT * FROM flights ORDER BY flight_id LIMIT 100;

                                     QUERY PLAN
    ----------------------------------------------------------------------------
     Limit  (cost=12776.73..12776.98 rows=100 width=63)
       ->  Sort  (cost=12776.73..13313.90 rows=214867 width=63)
             Sort Key: flight_id
             ->  Seq Scan on flights  (cost=0.00..4564.67 rows=214867 width=63)
    (4 rows)

Хоть стоимость и высока, она все же меньше, чем в предыдущем примере. Почему?

Дело в том, что в арсенале планировщика есть разные способы сортировки:

    => EXPLAIN (ANALYZE, TIMING OFF)
      SELECT * FROM flights ORDER BY flight_id LIMIT 100;

                                                   QUERY PLAN
    ---------------------------------------------------------------------------------------------------------
     Limit  (cost=12776.73..12776.98 rows=100 width=63) (actual rows=100 loops=1)
       ->  Sort  (cost=12776.73..13313.90 rows=214867 width=63) (actual rows=100 loops=1)
             Sort Key: flight_id
             Sort Method: top-N heapsort  Memory: 37kB
             ->  Seq Scan on flights  (cost=0.00..4564.67 rows=214867 width=63) (actual rows=214867 loops=1)
     Planning time: 0.105 ms
     Execution time: 80.333 ms
    (7 rows)

Здесь фактически не сортируется весь набор, а 100 раз находится максимальное значение.

А индексное сканирование позволяет получать данные по мере необходимости. Сравните стоимость с предыдущим вариантом:

    => RESET enable_indexscan;

    RESET

    => EXPLAIN SELECT * FROM flights ORDER BY flight_id LIMIT 100;

                                            QUERY PLAN
    -------------------------------------------------------------------------------------------
     Limit  (cost=0.42..3.94 rows=100 width=63)
       ->  Index Scan using flights_pkey on flights  (cost=0.42..7558.54 rows=214867 width=63)
    (2 rows)

Конец демонстрации.