# Сканирование по битовой карте

Будем рассматривать таблицу бронирований bookings.

Создадим на ней два дополнительных индекса:

    => CREATE INDEX ON bookings(book_date);

    CREATE INDEX

    => CREATE INDEX ON bookings(total_amount);

    CREATE INDEX

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

    => EXPLAIN SELECT * FROM bookings WHERE total_amount < 10000;

                                              QUERY PLAN
    -----------------------------------------------------------------------------------------------
     Bitmap Heap Scan on bookings  (cost=1082.76..15249.65 rows=57591 width=21)
       Recheck Cond: (total_amount < '10000'::numeric)
       ->  Bitmap Index Scan on bookings_total_amount_idx  (cost=0.00..1068.36 rows=57591 width=0)
             Index Cond: (total_amount < '10000'::numeric)
    (4 rows)

Выбран метод доступа Bitmap Scan. Он состоит из двух узлов:

- Bitmap Index Scan читает индекс и строит битовую карту;
- Bitmap Heap Scan читает табличные страницы, используя построенную карту.

Обратите внимание, что карта должна быть построена полностью, прежде чем ее можно будет использовать.

# Использование памяти

Узел Bitmap Heap Scan показывает условие перепроверки (Recheck Cond). Сама же перепроверка выполняется не всегда, а только при потере точности, когда битовая карта не помещается в память.

    => EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF)
      SELECT * FROM bookings WHERE total_amount < 10000;

                                        QUERY PLAN
    ----------------------------------------------------------------------------------
     Bitmap Heap Scan on bookings (actual rows=63944 loops=1)
       Recheck Cond: (total_amount < '10000'::numeric)
       Heap Blocks: exact=13335
       ->  Bitmap Index Scan on bookings_total_amount_idx (actual rows=63944 loops=1)
             Index Cond: (total_amount < '10000'::numeric)
     Planning time: 0.102 ms
     Execution time: 531.687 ms
    (7 rows)

Строка "Heap Blocks: exact" говорит о том, что все фрагменты битовой карты построены с точностью до строк - перепроверка не выполняется.

Уменьшим размер выделяемой памяти.

    => SET work_mem = '64kB';

    SET

    => EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF)
      SELECT * FROM bookings WHERE total_amount < 10000;

                                        QUERY PLAN
    ----------------------------------------------------------------------------------
     Bitmap Heap Scan on bookings (actual rows=63944 loops=1)
       Recheck Cond: (total_amount < '10000'::numeric)
       Rows Removed by Index Recheck: 1886695
       Heap Blocks: exact=926 lossy=12409
       ->  Bitmap Index Scan on bookings_total_amount_idx (actual rows=63944 loops=1)
             Index Cond: (total_amount < '10000'::numeric)
     Planning time: 0.113 ms
     Execution time: 423.633 ms
    (8 rows)

Во-первых, появились lossy-фрагменты битовой карты - с точностью до страниц. Во-вторых, указано, сколько строк не прошло перепроверку условия (Rows Removed by Index Recheck).

Восстановим значение параметра.

    => RESET work_mem;

    RESET

# Объединение битовых карт

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

    => EXPLAIN (COSTS OFF)
      SELECT * FROM bookings
      WHERE total_amount < 10000 OR total_amount > 100000;

                                            QUERY PLAN
    -------------------------------------------------------------------------------------------
     Bitmap Heap Scan on bookings
       Recheck Cond: ((total_amount < '10000'::numeric) OR (total_amount > '100000'::numeric))
       ->  BitmapOr
             ->  Bitmap Index Scan on bookings_total_amount_idx
                   Index Cond: (total_amount < '10000'::numeric)
             ->  Bitmap Index Scan on bookings_total_amount_idx
                   Index Cond: (total_amount > '100000'::numeric)
    (7 rows)

Здесь сначала были построены две битовые карты - по одной на каждое условие, а затем объединены побитовой операцией "или".

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

    => EXPLAIN (COSTS OFF)
      SELECT * FROM bookings
      WHERE total_amount < 10000
         OR book_date = bookings.now() - INTERVAL '1 day';

                                                                      QUERY PLAN
    -----------------------------------------------------------------------------------------------------------------------------------------------
     Bitmap Heap Scan on bookings
       Recheck Cond: ((total_amount < '10000'::numeric) OR (book_date = ('2017-08-15 18:00:00+03'::timestamp with time zone - '1 day'::interval)))
       ->  BitmapOr
             ->  Bitmap Index Scan on bookings_total_amount_idx
                   Index Cond: (total_amount < '10000'::numeric)
             ->  Bitmap Index Scan on bookings_book_date_idx
                   Index Cond: (book_date = ('2017-08-15 18:00:00+03'::timestamp with time zone - '1 day'::interval))
    (7 rows)

# Кластеризация

Если строки таблицы упорядочены так же, как и индекс, битовая карта становится излишней.

Продемонстрируем это с помощью команды CLUSTER. Сейчас строки таблицы физически упорядочены по номеру бронирования:

    => SELECT * FROM bookings LIMIT 10;

     book_ref |       book_date        | total_amount
    ----------+------------------------+--------------
     000004   | 2016-08-13 15:40:00+03 |     55800.00
     00000F   | 2017-07-05 03:12:00+03 |    265700.00
     000010   | 2017-01-08 19:45:00+03 |     50900.00
     000012   | 2017-07-14 09:02:00+03 |     37900.00
     000026   | 2016-08-30 11:08:00+03 |     95600.00
     00002D   | 2017-05-20 18:45:00+03 |    114700.00
     000034   | 2016-08-08 05:46:00+03 |     49100.00
     00003F   | 2016-12-12 15:02:00+03 |    109800.00
     000048   | 2016-09-17 01:57:00+03 |     92400.00
     00004A   | 2016-10-13 21:57:00+03 |     29000.00
    (10 rows)

Переупорядочим строки в соответствии с индексом по столбцу total_amount.

Пока идет процесс, обратите внимание:

- Команда CLUSTER устанавливает исключительную блокировку, поскольку полностью перестраивает таблицу (как VACUUM FULL);
- Строки упорядочиваются, но не поддерживаются в упорядоченном виде - в процессе работы кластеризация будет ухудшаться.

    => CLUSTER bookings USING bookings_total_amount_idx;

    CLUSTER

    => ANALYZE bookings;

    ANALYZE

Убедимся, что строки упорядочены по стоимости:

    => SELECT * FROM bookings LIMIT 10;

     book_ref |       book_date        | total_amount
    ----------+------------------------+--------------
     00F39E   | 2017-02-12 04:11:00+03 |      3400.00
     0103E1   | 2017-04-03 09:32:00+03 |      3400.00
     013695   | 2016-11-01 09:30:00+03 |      3400.00
     0158C0   | 2017-04-24 07:47:00+03 |      3400.00
     01AD57   | 2017-03-15 16:11:00+03 |      3400.00
     020E97   | 2017-01-02 12:25:00+03 |      3400.00
     021FD3   | 2017-05-27 10:20:00+03 |      3400.00
     0278C7   | 2017-02-04 17:42:00+03 |      3400.00
     029452   | 2016-12-10 13:51:00+03 |      3400.00
     0355DD   | 2016-09-19 13:22:00+03 |      3400.00
    (10 rows)

    => EXPLAIN SELECT * FROM bookings WHERE total_amount < 10000;

                                                QUERY PLAN
    --------------------------------------------------------------------------------------------------
     Index Scan using bookings_total_amount_idx on bookings  (cost=0.43..2372.66 rows=67899 width=21)
       Index Cond: (total_amount < '10000'::numeric)
    (2 rows)

Раньше использовалось сканирование по битовой карте, но теперь проще и выгодней сделать обычное индексное сканирование.

# Параллельное сканирование по битовой карте

Сканирование по битовой карте может работать в параллельном режиме. Сколько бронирований сделано за последние 2 месяца?

    => SELECT bookings.now() - INTERVAL '2 months' AS d \gset

    => EXPLAIN (COSTS OFF)
      SELECT count(*) FROM bookings WHERE book_date > :'d';

                                                   QUERY PLAN
    --------------------------------------------------------------------------------------------------------
     Finalize Aggregate
       ->  Gather
             Workers Planned: 2
             ->  Partial Aggregate
                   ->  Parallel Bitmap Heap Scan on bookings
                         Recheck Cond: (book_date > '2017-06-15 18:00:00+03'::timestamp with time zone)
                         ->  Bitmap Index Scan on bookings_book_date_idx
                               Index Cond: (book_date > '2017-06-15 18:00:00+03'::timestamp with time zone)
    (8 rows)

Узел Bitmap Index Scan выполняется ведущим процессом, который строит битовую карту. Параллельно выполняется только сканирование таблицы по уже готовой битовой карте - узел Parallel Bitmap Heap Scan.

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