Что такое «сканирование кучи Bitmap» в плане запроса?

113

Я хочу знать принцип «сканирования кучи Bitmap», я знаю, что это часто происходит, когда я выполняю запрос с ORусловием.

Кто может объяснить принцип «сканирования кучи Bitmap»?

франки
источник

Ответы:

122

Лучшее объяснение исходит от Тома Лейна , автора алгоритма, если я не ошибаюсь. См. Также статью в Википедии .

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

Это отличается от сканирования индекса, при котором индекс просматривается построчно по порядку - это означает, что страница диска может посещаться несколько раз.


Re: вопрос в вашем комментарии ... Ага, именно так.

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

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

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

Дени де Бернарди
источник
Итак, «Растровое сканирование кучи»: страницу нельзя посещать более одного раза! но «Индекс может»: страницу можно посещать более одного раза, потому что индекс посещается построчно по порядку.
francs
Вероятно, происходит кеширование, когда страницы посещаются несколько раз: страница фактически будет загружена с диска в первый раз (медленно), а дальнейший доступ попадет в кеш в памяти (кеш Postgres (быстро) или кеш ОС (быстрее)) .
Matthieu
Также существует ситуация, index-only scanкогда в запросе доступен только индексированный столбец. в этом случае index-only scanне требуется доступ к данным кучи (страницы данных): postgresql.org/docs/12/indexes-index-only-scans.html
Алан,