Сканирование по битовой карте (bitmap scan) - это один из методов поиска данных в PostgreSQL, который состоит из 2-ух основных вида узлов, которые можно увидеть при выводе древа плана, используя EXPLAIN ANALYZE VERBOSE:
1). bitmap index scan, первичное сканирование по индексу с построением битовой карты. Операция в данном узле, сама по себе, не извлекает данные. Она создает битовую карту с местоположением строк. Таких операций может быть несколько.
2). bitmap heap scan, финальная операция в узле древа плана, которая уже использует ранее сформированную битовую карту из предыдущего этапа, уже для взятия данных.
При этом, стоит отметить такие детали:
- узлов с bitmap index scan может быть несколько, это зависит от количества данных в таблице, используемых индексов при исполнении SQL-запроса.
- когда применяется несколько несколько bitmap index scan операций, далее могут примениться операции BitmapAnd или BitmapOr напротив созданных битовых карт, формируя результирующую битовую карту, которая передасться уже в узел bitmap heap scan.
А при каких конкретно условиях применяется метод bitmap сканирования?
Cуществуют иные методы сканирования, как:
- последовательное сканирование (sequential scan).
- индексное сканирование (index scan/index only scan).
- и другие, как CTE/TID scan... Но, в рамках данной статьи, для более релевантного сравнения с bitmap сканированием - возьмем первые два метода.
Так вот, можно представить bitmap сканирование, как некую "середину" между последовательным сканированием и индексным сканированием:
- похоже на последовательное сканирование, оно использует преимущества чтения данных, представленных в больших объемах.
- но и похоже на индексное сканирование, оно использует индексы для определения - какие данные необходимо взять.
Давайте подготовим SQL DDL код с заполнением таблицы в 1 миллион строк и применим SQL-запрос, который будет использовать метод bitmap сканирования:
Вывод плана с узлами bitmap index scan/bitmap heap scan, можно увидеть исполнив последний SELECT-запрос с "EXPLAIN ANALYZE VERBOSE..." частью.
Вы можете немного подкорректировать код, чтобы увидеть:
1). изменение поведения планировщика (оптимизатора), он выберет иной метод сканирования.
2). эффективность bitmap сканирования, относительно пункта №1 .
Что для этого необходимо? Оберните SQL-запрос с EXPLAIN ANALYZE часть в явный транзакционный блок и удалите в нем - индекс с последующей отменой действия через ROLLBACK:
START TRANSACTION;
DROP INDEX idx_orders_order_date;
<сам SQL-запрос, который использует bitmap узлы>
ROLLBACK;
Из вывода плана запроса, видно:
- что bitmap сканирование сменилось на sequential scan (последовательное сканирование).
- если вы повторно, несколько раз, исполните прежнюю версию SQL-запроса и версию в транзакционном блоке, где появилось последовательное сканирование, то "execution time" в среднем будет в 2-а раза быстрее у bitmap сканирования. При этом на статистку в выводе плана не влияют дополнительные инструкции в виде DROP INDEX или ROLLBACK, т.к. EXPLAIN ANALYZE применится сугубо к SELECT-части, и выводится статистика конкретно для него.
Теперь, немного углубимся в детали логики bitmap сканирования. Общая логика всего механизма выглядит следующим образом:
1). Битовая карта создается динамически для каждого нового SQL-запроса с bitmap сканированием. При этом, она не может быть повторно переиспользована в других SQL-запросах, и по завершению запроса - битовая карта высвобождается из памяти (ОЗУ).
2). Битовая карта представляет собой массив битов, размер которого соответствует количеству heap-страниц при сканировании.
3). Bitmap index scan устанавливает значения битов в массиве битовой карты на основе адреса heap-страницы, на который указывает индекс. При обнаружении записи индекса, соответствующей условию поиска - находится адрес heap-страницы на которую указывает запись самого индекса. И затем, соответствующий бит в битовой карте устанавливается в значение равное "1", используя побитовое смещение. Ключевым моментом является, что сами значения не считываются на данном этапе. Считывается именно своего рода "указатель" на heap-страницу, которая содержит нужное результирующее значение для SQL-запроса.
4). Если было использовано несколько bitmap index scan операций, то для каждой bitmap index scan операции в узле - создается своя битовая карта. И действие из пункта №3 повторяется. И далее применяются BitmapAnd (логическое произведение битовых карт) и BitmapOr (логическое сложение битовых карт), формируя результирующую битовую карту.
5). Далее, результирующая битовая карта передается в узел с bitmap heap scan, где данная операция считывает искомые значения в более последовательной манере, используя данную результирующую битовую карту из адресов страниц, внутри которых хранятся искомые значения. При этом важный момент, что операция на данном этапе, хоть и последовательная, но за счет первичного сканирования считываются только необходимые страницы, пропуская ненужные. По большой степени, в этом и заключается прелесть bitmap сканирования.
6). Сам механизм по чтению heap-страниц в узле bitmap heap scan выглядит так, что происходит переход к началу каждой страницы, помеченной битом - "1", и происходит считывание значений из нее. Каждая прочитанная страница повторно проверяется на соответствие условию из SQL-запроса.
7). Финально, получив искомые значения в bitmap heap scan - пользователю PostgreSQL выдается результат по исполненному SQL-запросу.
Визуально это можно представить следующим образом:
<bitmap index scan №1>
{1 0 0 1 0 0 0 1} битовая карта №1
<bitmap index scan №2>
{1 0 0 0 1 0 0 1} битовая карта №2
<логическое И, т.е. BitmapAnd>
{1 0 0 0 0 0 0 1} результирующая битовая карта
<bitmap heap scan>
Далее из результирующей карты {1 0 0 0 0 0 0 1}, где биты равны значению "1", берутся адреса heap-страниц. Это страницы №1 и №8 , условно в нашем примере. Страницы от №2 до №7 - пропускаются. И считываются значения, удовлетворяющие SQL-запросу пользователя, из страниц №1 и №8.
Иные важные детали:
- стоит отметить важный момент, что адрес строки в записи индекса указывает на ctid (её идентификатор, иными словами идентификатор кортежа), который является комбинацией указателя (номера) heap-страницы и смещения внутри этой же страницы. Bitmap сканирование игнорирует данные "смещения", т.к. сканирование все равно будет проверять всю страницу, и установит значения бит в битовой карте в "1", если хотя бы одна строка на этой странице соответствует условию.
- при кластеризации данных из таблицы (использование оператора CLUSTER), для планировщика использование битовой карты может стать невыгодным, и тогда произойдет стандартное индексное сканирование.
Есть ли взаимосвязь work_mem с работой bitmap сканирования и может ли это негативно повлиять на работу самого процесса сканирования?
Да, взаимосвязь существует. Низкое значение work_mem может повлиять на потерю точности и спровоцировать появление lossy heap-блоков, ввиду того что формируемые битовые карты не поместятся в память, выделенной с помощью work_mem.
Вы можете повторить SQL-запрос с выводом плана запроса bitmap-узлов, который я ранее указал в данной статье, установив минимальное значение для work_mem:
SET work_mem = '64kB';
Повторите исходный запрос с данным значением, и увидите следующую статистику:
Что ухудшилось?
- появились lossy heap-блоки битовых карт.
- и указано, столько строк не прошло перепроверку (Rows Removed by Index Recheck).
Bitmap heap scan может использовать heap-блоки, которые либо напрямую указывают на необходимые строки (exact heap blocks), либо грубо говоря, указывают в "общем/неточном" направлении строк (lossy heap blocks). Более точный механизм несомненно лучше, но потребует больше памяти (work_mem). Нехватка памяти в виде ограниченного значения "work_mem" параметра не позволит использовать точные битовые карты, и тогда PostgreSQL может начать использовать менее эффективные - неточные битовые карты. В свою очередь, неточные битовые карты будут требовать дополнительной проверки для каждой искомой строки при bitmap сканировании.
Постскриптум:
- при написании статьи использовалась следующая версия PostgreSQL v16.3
- к сожалению, Дзен перестал поддерживать функционал вставки исходного программного кода с syntax highlighting, на момент написания данной статьи. Про схожие проблемы рассказывают и другие Дзен-авторы: https://dzen.ru/a/XtUGaNtXXh9qY-gb поэтому вместо исходного кода, Вы видите комбинацию из картинки и ссылки на SQL-код в GitHub Gist. Прошу прощения за неудобства!
