postgresql что такое индексы

Индексы в PostgreSQL

В нашем техническом блоге на www.habrahabr.ru свыше трех десятков статей о СУБД PostgreSQL, написанных сотрудниками компании Postgres Professional для всех тех пользователей, администраторов СУБД, разработчиков приложений и систем, которые хотят расширить свои знания о СУБД PostgreSQL и о базах данных вообще. Недавно руководитель образовательных программ нашей компании Егор Рогов опубликовал пятую часть в цикле статей об «Индексах в PostgreSQL». С момента открытия этого цикла, статьи Егора Рогова были прочитаны более 60 тысяч раз, и весь цикл пользуется неизменным интересом со стороны разработчиков и администраторов СУБД.

Индексы в PostgreSQL — часть 1

В этой серии статей речь пойдет об индексах в PostgreSQL.

Любой вопрос можно рассматривать с разных точек зрения. Мы будем говорить о том, что должно интересовать прикладного разработчика, использующего СУБД: какие индексы существуют, почему в PostgreSQL их так много разных, и как их использовать для ускорения запросов. Пожалуй, тему можно было бы раскрыть и меньшим числом слов, но мы втайне надеемся на любознательного разработчика, которому также интересны и подробности внутреннего устройства, тем более, что понимание таких подробностей позволяет не только прислушиваться к чужому мнению, но и делать собственные выводы.

Индексы в PostgreSQL — часть 2

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

Все свойства методов доступа представлены в таблице pg_am (am — access method). Из этой таблицы можно получить и сам список доступных методов: btree, hash, gist, gin, spgist, brin

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

Индексы в PostgreSQL — часть 3

В первой статье мы рассмотрели механизм индексирования PostgreSQL, во второй — интерфейс методов доступа, и теперь готовы к разговору о конкретных типах индексов. Начнем с хеш-индекса.

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

Индексы в PostgreSQL — часть 4

Мы уже рассмотрели механизм индексирования PostgreSQL и интерфейс методов доступа, а также один из методов доступа — хеш-индекс. Сейчас поговорим о самом традиционном и используемом индексе — B-дереве. Глава получилась большой, запасайтесь терпением.

Индекс btree, он же B-дерево, пригоден для данных, которые можно отсортировать. Иными словами, для типа данных должны быть определены операторы «больше», «больше или равно», «меньше», «меньше или равно» и «равно». Заметьте, что одни и те же данные иногда можно сортировать разными способами, что возвращает нас к концепции семейства операторов.

Индексы в PostgreSQL — часть 5

GiST — сокращение от «generalized search tree». Это сбалансированное дерево поиска, точно так же, как и рассмотренный ранее b-tree.

В чем же разница? Индекс b-tree жестко привязан к семантике сравнения: поддержка операторов «больше», «меньше», «равно» — это все, на что он способен (зато способен очень хорошо!). Но в современных базах хранятся и такие типы данных, для которых эти операторы просто не имеют смысла: геоданные, текстовые документы, картинки…

На пятой части цикл статей об индексах в СУБД PostgreSQL не заканчивается и уже сейчас Егор Рогов пишет продолжение.

Источник

Индексы в PostgreSQL

Авторизуйтесь

Индексы в PostgreSQL

Full Stack Developer в DataArt

В статье я расскажу о предназначении и основах принципов работы объектов баз данных — индексов. На примере СУБД PostgreSQL коротко рассмотрим несколько разных типов индексов и классов задач, для которых они применимы. В конце материала поделюсь ссылками на статьи с более глубоким описанием внутреннего устройства индексов в PostgreSQL.

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

Предназначение индексов

Простейший метод решения задачи поиска записей в базе данных, удовлетворяющих определенному критерию, — полный перебор. Но с ростом количества записей производительность такого подхода будет заметно падать. Для повышения производительности поиска создаются вспомогательные структуры — индексы. Используя индексы, можно существенно поднять скорость поиска, потому что данные в индексе хранятся в форме, позволяющей нам в процессе поиска не рассматривать области, которые заведомо не могут содержать искомые элементы.

Если провести аналогию между базой данных и книгой, индексами можно считать оглавление книги и предметный указатель. Действительно, если бы у нас не было таких «индексов», для поиска конкретной главы или для поиска определения какого-то понятия пришлось бы листать и читать всю книгу целиком, пока не найдем то, что нужно. Имея оглавление и предметный указатель, нам нужно просмотреть существенно меньший объем данных, после чего мы точно узнаем номер страницы книги, на которой находится то, что мы ищем. Индексы в базах данных по сути устроены так же, как оглавление или как предметный указатель книги.

18–20 ноября, Онлайн, Беcплатно

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

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

2 4 5 10 23 34 38 58 112 114 115 110 123 134 138 158 180

Допустим, необходимо определить, содержит ли этот отсортированный список число 158. Для этого:

В итоге метод бинарного поиска дал нам результат всего за три шага. При полном переборе с начала списка нам потребовалось бы 16 шагов. Бинарный поиск имеет алгоритмическую сложность O(log(n)). Используя формулы алгоритмической сложности O(n) и O(log(n)), мы можем оценить, как будет меняться приблизительное количество операций при поиске разными способами с ростом объема данных:

Результат впечатляет. Храня данные в отсортированном виде, мы не только снизили скорость поиска по ним, но и колоссально сократили скорость замедления поиска при росте объема данных.

Использование индексов в базе данных дает аналогичный результат. Принцип работы одного из важнейших индексов в базе данных (индекс на основе B-дерева) основан именно на рассмотренном нами выше принципе — возможности хранить данные в отсортированном виде.

Индексы в PostgreSQL

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

SELECT * FROM table_name WHERE P(column_name) = 1

Предикат P может вычисляться от значения нескольких колонок. В этом случае для ускорения запроса используется индекс, построенный не для одной колонки, а для нескольких. Такие индексы называют составными.

Если мы хотим ускорить выполнение запроса, условие которого вычисляется по одной или нескольким колонкам, в PostgreSQL нам необходимо создать для этих колонок индекс с помощью команды CREATE INDEX :

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

Например, индекс может поддерживать ограничение на уникальность и не допускать появления в таблице нескольких строк, значения индексируемых столбцов у которых совпадают. Для этого при создании индекса указывают ключевое слово UNIQUE :

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

CREATE INDEX index_name ON table_name(lower(text_field))

И такой индекс уже может успешно применяться для ускорения нашего запроса.

CREATE INDEX index_name ON table_name USING GIST (column_name)

B-tree

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

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

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

Выполнение этих и многих других запросов может быть ускорено с помощью B-дерева. Кроме того, индекс на основе B-дерева ускоряет сортировку результатов, если в ORDER BY указано проиндексированное поле.

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

Однако хранить индекс просто в виде отсортированного массива мы не можем, т. к. данные могут модифицироваться: значения могут меняться, записи — удаляться или добавляться. Чтобы эффективно поддерживать хранение индексируемых данных в отсортированном виде, индекс хранят в виде сбалансированного сильно ветвящегося дерева, называемого B-деревом (B-tree).

Корневой узел B-дерева содержит в упорядоченном виде несколько значений из общего набора, допустим, t элементов. Тогда все остальные элементы можно распределить по t+1 дочерним поддеревьям по следующему правилу:

Каждое поддерево, в свою очередь, тоже является B-деревом, имеет корневой элемент и строится далее рекурсивно по такому же принципу.

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

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

Кроме того, важное и полезное свойство B-дерева при его использовании в СУБД — возможность эффективно хранить его во внешней памяти. Каждый узел B-дерева обычно хранит такой объем данных, который может быть эффективно записан на диск или прочитан за одну операцию ввода-вывода. B-дерево даже может не помещаться целиком в оперативной памяти. В этом случае СУБД может держать в памяти только узлы верхнего уровня (которые вероятно будут часто использоваться при поиске), читая узлы нижних уровней только при необходимости.

Индекс на основе B-дерева может ускорять запросы, которые используют не целиком входящие в индекс поля, а любую часть, начиная с начала. Например, индекс может ускорить запрос LIKE для поиска строк, которые начинаются с заданной подстроки:

SELECT * FROM table_name WHERE text_field LIKE ‘start_substring%’

Если индекс построен по нескольким колонкам, он может ускорять запросы, в которых фигурируют одна или несколько первых колонок. Поэтому важен порядок, в котором мы указываем колонки при создании индекса. Допустим, у нас есть индекс по колонкам col_1 и col_2. Тогда он может использоваться в том числе для ускорения запроса вида:

SELECT * FROM table_name WHERE col_1 = 123

И нам не нужно создавать отдельный индекс для колонки col_1. Будет использоваться составной индекс (col_1, col_2).

Однако для запроса только по колонке col_2 такой составной индекс уже использовать не получится.

Подробнее, как индекс на основе B-дерева реализован в PostgreSQL, см. статью.

GiST и SP-GiST

GiST — сокращение от «generalized search tree». Это сбалансированное дерево поиска, точно так же, как и рассмотренный ранее b-tree. Но b-tree применимо только к тем типам данных, для которых имеет смысл операция сравнения и есть возможность упорядочивания. Но PostgreSQL позволяет хранить и такие данные, для которых операция упорядочивания не имеет смысла, например, геоданные и геометрические объекты.

Тут на помощь приходит индексный метод GiST. Он позволяет распределить данные любого типа по сбалансированному дереву и использовать это дерево для поиска по самым разным условиям. Если при построении B-дерева мы сортируем все множество объектов и делим его на части по принципу больше-меньше, при построении GiST индексов можно реализовать любой принцип разбиения любого множества объектов.

Например, в GiST-индекс можно уложить R-дерево для пространственных данных с поддержкой операторов взаимного расположения (находится слева, справа; содержит и т. д.). Такой индекс доступен в PostgreSQL и может быть полезен при разработке геоинформационных систем, в которых возникают запросы вида «получить множество объектов на карте, находящихся от заданной точки на расстоянии не более 1 км».

SP-GiST похож GiST, но он позволяет создавать несбалансированные деревья. Такие деревья могут быть полезны при разбиении множества на непересекающиеся объекты. Буквы SP означают space partitioning. К такому типу индексов можно отнести kd-деревья, реализация которых присутствует в PostgreSQL. Его, как и R-дерево, можно использовать для ускорения запросов геометрического поиска. Свойство непересечения упрощает принятие решений при вставке и поиске. С другой стороны, получающиеся деревья, как правило, слабо ветвисты, что усложняет их эффективное хранение во внешней памяти.

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

Подробнее об алгоритмах, лежащих в основе R- и kd-деревьев см. раз и два, а об их реализации и использовании в PostgreSQL см. в этой и этой статье.

Заключение

Индексы — важнейший инструмент баз данных, ускоряющий поиск. Он не бесплатен, создавать много индексов без лишней необходимости не стоит — индексы занимают дополнительную память, и при любом обновлении проиндексированных данных СУБД должна выполнять дополнительную работу по поддержанию индекса в актуальном состоянии.

PostgreSQL поддерживает разные типы индексов для разных задач:

Источник

Индексы в PostgreSQL — 9

В прошлых статьях мы рассмотрели механизм индексирования PostgreSQL, интерфейс методов доступа и следующие методы: хеш-индексы, B-деревья, GiST, SP-GiST, GIN и RUM. Тема этой статьи — BRIN-индексы.

Общая идея

В отличие от индексов, с которыми мы уже познакомились, идея BRIN не в том, чтобы быстро найти нужные строки, а в том, чтобы избежать просмотра заведомо ненужных. Это всегда неточный индекс: он вообще не содержит TID-ов табличных строк.

Упрощенно говоря, BRIN хорошо работает для тех столбцов, значения в которых коррелируют с их физическим расположением в таблице. Иными словами, если запрос без предложения ORDER BY выдает значения столбца практически в порядке возрастания или убывания (и при этом по столбцу нет индексов).

Метод доступа создавался в рамках европейского проекта по сверхбольшим аналитическим базам данных Axle с прицелом на таблицы размером в единицы и десятки терабайт. Важное свойство BRIN, позволяющее создавать индексы на таких таблицах — небольшой размер и минимальные накладные расходы на поддержание.

Работает это следующим образом. Таблица разбивается на зоны (range) размером в несколько страниц (или блоков, что то же самое) — отсюда и название: Block Range Index, BRIN. Для каждой зоны в индексе сохраняется сводная информация о данных в этой зоне. Как правило, это минимальное и максимальное значения, но бывает и иначе, как мы увидим дальше. Если при выполнении запроса, содержащего условие на столбец, искомые значения не попадают в диапазон, то всю зону можно смело пропускать; если же попадают — все строки во всех блоках зоны придется просмотреть и выбрать среди них подходящие.

Не будет ошибкой рассматривать BRIN не как индекс в обычном понимании, а как ускоритель последовательного сканирования таблицы. Можно посмотреть на него и как на альтернативу секционированию, если каждую зону считать отдельной «виртуальной» секцией.
Теперь рассмотрим устройство индекса более подробно.

Устройство

Первой (точнее, нулевой) в индексе идет страница с метаданными.

С некоторым отступом от метаданных находятся страницы со сводной информацией. Каждая индексная строка содержит сводку по какой-то одной зоне.

А между метастраницей и сводными данными располагаются страницы с обратной картой зон (reverse range map, сокращенно revmap). По сути, это массив указателей (TID-ов) на соответствующие индексные строки.

Для некоторых зон указатель в revmap может не вести ни к какой индексной строке (на рисунке отмечен серым цветом). В этом случае считается, что для этой зоны еще нет сводной информации.

Сканирование индекса

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

Алгоритм простой. Последовательно просматривается карта зон (то есть зоны перебираются в порядке их расположения в таблице). С помощью указателей определяются индексные строки со сводной информацией по каждой зоне. Если зона точно не содержит искомого значения, она пропускается; если может содержать (или если сводная информация отсутствует) — все страницы зоны добавляются к битовой карте. Получившаяся битовая карта используется дальше как обычно.

Обновление индекса

Интереснее обстоит дело с обновлением индекса при изменении таблицы.

При добавлении новой версии строки в табличную страницу мы определяем, к какой зоне она принадлежит, и по карте зон находим индексную строку со сводной информацией. Все это — простые арифметические операции. Пусть, например, размер зоны — 4 страницы, и на странице 13 появилась версия строки со значением «42». Номер зоны (начиная с нуля) равен 13 / 4 = 3, значит в revmap берем указательно со смещением 3 (четвертый по счету).

Минимальное значение для этой зоны — 31, максимальное — 40. Поскольку новое значение 42 выходит за эти пределы, обновляем максимальное значение (см. рисунок). Если же новое значение укладывается в существующие рамки, индекс обновлять не нужно.

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

При удалении строки… ничего не происходит. Можно заметить, что в каких-то случаях будет удалено минимальное или максимальное значение, и тогда диапазон можно было бы уменьшить. Но чтобы это определить, пришлось бы прочитать все значения в зоне, а это накладно.

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

Ну и обновление строки — это просто удаление старой версии и добавление новой.

Пример

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

Таблица будет иметь такой вид:

demo=# select count(*) from flights_bi;
count
———-
30517076
(1 row)

demo=# select pg_size_pretty(pg_total_relation_size(‘flights_bi’));
pg_size_pretty
—————-
4127 MB
(1 row)

Получилось 30 миллионов строк и 4 ГБ. Не бог весть какой объем, но для ноутбука годится: полное сканирование у меня выполняется около 10 секунд.

По каким столбцам строить индекс?

Поскольку BRIN-индексы имеют небольшой размер и невысокие накладные расходы, а обновления если и происходят, то нечасто, возникает та редкая ситуация, когда индексов можно создать много «на всякий случай», например, по всем полям, по которым пользователи-аналитики могут строить свои adhoc-запросы. Не пригодится — ладно, а даже не очень эффективный индекс все равно наверняка сработает лучше, чем полное сканирование. Конечно, есть поля, на которых индекс совсем бесполезен; их подскажет простой здравый смысл.

Но ограничиться таким советом было бы странно, поэтому попробуем сформулировать более точный критерий.

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

В нашем примере данные, очевидно, упорядочены по дням (как по scheduled_time, так и по actual_time — разница небольшая). Происходит это потому, что при добавлении строк в таблицу (в отсутствии удалений и обновлений) они укладываются в файл последовательно, одна за другой. В имитации загрузки мы даже не использовали предложение ORDER BY, поэтому в пределах дня даты в принципе могут быть перемешаны как угодно, но упорядоченность обязана присутствовать. Проверим:

На втором и третьем местах неожиданно оказались класс обслуживания fare_condition (столбец содержит три уникальных значения) и тип рейса flight_type (два уникальных значения). Это обманка: формально корреляция высокая, но на деле в нескольких подряд взятых страницах наверняка обнаружатся все возможные значения — а это значит, что толка от BRIN не будет.

Следом идет часовой пояс airport_utc_offset: в нашем примере внутри одного дневного цикла аэропорты «по построению» упорядочены по часовым поясам.

С этими двумя полями — временем и часовым поясом — мы и будем дальше экспериментировать.

Возможное нарушение корреляции

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

Отчасти с этим явлением можно бороться, уменьшая значение параметра хранения fillfactor, оставляя тем самым запас места на странице под будущие обновления. Вот только захочется ли увеличивать объем и без того огромной таблицы? Кроме того, это не решает вопрос с удалениями: они тоже «готовят ловушки» для новых строк, освобождая место где-то внутри существующих страниц. Из-за этого строки, которые иначе попали бы в конец файла, будут вставлены в какое-то произвольное место.

Кстати, забавный факт. Поскольку в BRIN-индексе нет ссылок на табличные строки, его наличие никак не должно мешать HOT-обновлениям — однако мешает.

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

Какой размер зоны выбрать?

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

Для этого мы можем выбрать уникальные значения столбца и посмотреть, на скольких страницах эти значения встречаются. Локализация значений увеличивает шансы на успешность применения BRIN-индекса. Более того, найденное количество страниц послужит подсказкой для определения размера зоны. Если же значение «размазано» по всем страницам таблицы — BRIN бесполезен.

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

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

demo=# select min(numblk), round(avg(numblk)) avg, max(numblk)
from (
select count(distinct (ctid::text::point)[0]) numblk
from flights_bi
group by scheduled_time::date
) t;
min | avg | max
——+——+——
1192 | 1500 | 1796
(1 row)

demo=# select relpages from pg_class where relname = ‘flights_bi’;
relpages
———-
528172
(1 row)

Видим, что каждый день распределен по страницам достаточно равномерно, и дни слабо перемешаны друг с другом (1500 × 365 = 547500, что ненамного превышает число страниц в таблице 528172). Это, собственно, и так понятно «по построению».

Ценная информация здесь — конкретное число страниц. При стандартном размере зоны в 128 страниц каждый день будет занимать от 9 до 14 зон. Это представляется адекватным: при запросе по конкретному дню можно ожидать погрешность в районе 10 %.

demo=# create index on flights_bi using brin(scheduled_time);
CREATE INDEX

Размер индекса всего-навсего 184 КБ:

demo=# select pg_size_pretty(pg_total_relation_size(‘flights_bi_scheduled_time_idx’));
pg_size_pretty
—————-
184 kB
(1 row)

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

Теперь посмотрим на часовые пояса. Тут тоже нельзя действовать «в лоб» — все значения надо поделить на число дневных «циклов», поскольку распределение повторяется внутри каждого дня. Кроме того, поскольку часовых поясов немного, можно посмотреть все распределение целиком:

demo=# select airport_utc_offset, count(distinct (ctid::text::point)[0])/365 numblk
from flights_bi
group by airport_utc_offset
order by 2;
airport_utc_offset | numblk
———————+———
12:00:00 | 6
06:00:00 | 8
02:00:00 | 10
11:00:00 | 13
08:00:00 | 28
09:00:00 | 29
10:00:00 | 40
04:00:00 | 47
07:00:00 | 110
05:00:00 | 231
03:00:00 | 932
(11 rows)

В среднем данные каждого часового пояса занимают 133 страницы за день, но распределение очень неравномерное: Петропавлоск-Камчатский и Анадырь укладываются всего в шесть страниц, а Москва и окрестности требуют девяти сотен. Размер зоны по умолчанию тут точно не годится; давайте для примера поставим 4 страницы.

demo=# create index on flights_bi using brin(airport_utc_offset) with (pages_per_range=4);
CREATE INDEX
demo=# select pg_size_pretty(pg_total_relation_size(‘flights_bi_airport_utc_offset_idx’));
pg_size_pretty
—————-
6528 kB
(1 row)

План выполнения

Посмотрим теперь, как работают наши индексы. Выберем какой-нибудь день, скажем, неделю назад («сегодня» определяется в демо-базе функцией bookings.now):

Как видим, планировщик использовал созданный индекс. Насколько он точен? Об этом говорит соотношение числа строк, удовлетворяющих условиям выборки (rows узла Bitmap Heap Scan), к общему числу строк, которое было получено с помощью индекса (то же плюс Rows Removed by Index Recheck). В нашем случае 83954 / (83954 + 12045) — примерно 90 %, как и ожидалось (ото дня ко дню это значение будет меняться).

Откуда появилось число 16640 в actual rows узла Bitmap Index Scan? Дело в том, что этот узел плана строит неточную (постраничную) битовую карту и понятия не имеет, сколько строк она затронет, а показать что-то надо. Поэтому от безысходности считается, что на каждой странице мы найдем 10 строк. Всего битовая карта содержит 1664 страниц (это значение видно из «Heap Blocks: lossy=1664») — получается как раз 16640. В общем, это бессмысленное число, на него не надо обращать внимание.

Что с аэропортами? Для примера возьмем часовой пояс Владивостока, занимающий 28 страниц в день:

demo=# explain (costs off,analyze)
select *
from flights_bi
where airport_utc_offset = interval ‘8 hours’;
QUERY PLAN
———————————————————————————-
Bitmap Heap Scan on flights_bi (actual time=75.151..192.210 rows=587353 loops=1)
Recheck Cond: (airport_utc_offset = ’08:00:00′::interval)
Rows Removed by Index Recheck: 191318
Heap Blocks: lossy=13380
-> Bitmap Index Scan on flights_bi_airport_utc_offset_idx
(actual time=74.999..74.999 rows=133800 loops=1)
Index Cond: (airport_utc_offset = ’08:00:00′::interval)
Planning time: 0.168 ms
Execution time: 212.278 ms

Снова планировщик использует созданный BRIN-индекс. Точность хуже (около 75 % в данном случае), но это ожидаемо: корреляция-то ниже.

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

Сравнение с B-деревом

Что, если построить обычный индекс B-дерево по тому же полю, что и BRIN?

demo=# create index flights_bi_scheduled_time_btree on flights_bi(scheduled_time);
CREATE INDEX
demo=# select pg_size_pretty(pg_total_relation_size(‘flights_bi_scheduled_time_btree’));
pg_size_pretty
—————-
654 MB
(1 row)

Он получился в несколько тысяч раз больше, чем наш BRIN! Правда, и скорость выполнения запроса немного увеличилась — планировщик понял по статистике, что данные физически упорядочены и не надо строить битовую карту, и, главное, не нужно перепроверять индексное условие:

demo=# explain (costs off,analyze)
select *
from flights_bi
where scheduled_time >= :d and scheduled_time
В этом прелесть BRIN: жертвуем эффективностью, но выигрываем очень много места.

Классы операторов

minmax

Для типов данных, значения которых можно сравнивать между собой, сводная информация состоит из минимального и максимального значений. Соответствующие классы операторов содержат в названии minmax, например, date_minmax_ops. Собственно, их мы до сих пор и рассматривали, и таких большинство.

inclusive

Не для всех типов данных определены операции сравнения. Например, их нет для точек (тип point), которыми представлены координаты аэропортов. Кстати, именно поэтому статистика не показывает корреляцию для этого столбца:

demo=# select attname, correlation
from pg_stats
where tablename=’flights_bi’ and attname = ‘airport_coord’;
attname | correlation
—————+————-
airport_coord |
(1 row)

Но для многих из таких типов можно ввести понятие «ограничивающей области», например, ограничивающий прямоугольник для геометрических фигур. Мы подробно говорили о том, как это свойство используется индексом GiST. Аналогично и BRIN позволяет собирать сводную информацию о столбцах таких типов: ограничивающая область для всех значений внутри зоны и является сводным значением.

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

demo=# create index on flights_bi using brin (box(airport_coord)) with (pages_per_range=1);
CREATE INDEX

Даже в таком экстремальном варианте индекс занимает всего 30 МБ:

demo=# select pg_size_pretty(pg_total_relation_size(‘flights_bi_box_idx’));
pg_size_pretty
—————-
30 MB
(1 row)

Теперь мы можем писать запросы, ограничивая аэропорты координатами. Например, так:

demo=# select airport_code, airport_name
from airports
where box(coordinates)
Правда, планировщик откажется использовать наш индекс.

demo=# analyze flights_bi;
ANALYZE
demo=# explain select * from flights_bi
where box(airport_coord)
Почему? Давайте запретим полное сканирование и посмотрим.

demo=# set enable_seqscan = off;
SET
demo=# explain select * from flights_bi
where box(airport_coord) Bitmap Index Scan on flights_bi_box_idx
(cost=0.00..14072.04 rows=30517076 width=0)
Index Cond: (box(airport_coord)
Оказывается, индекс может использоваться, но планировщик полагает, что битовую карту придется построить по всей таблице целиком — неудивительно, что в таком случае он предпочитает полное сканирование. Проблема здесь в том, что для геометрических типов PostgreSQL не собирает никакой статистики, так что планировщику приходится действовать вслепую:

demo=# select * from pg_stats where tablename = ‘flights_bi_box_idx’ \gx
-[ RECORD 1 ]———-+——————-
schemaname | bookings
tablename | flights_bi_box_idx
attname | box
inherited | f
null_frac | 0
avg_width | 32
n_distinct | 0
most_common_vals |
most_common_freqs |
histogram_bounds |
correlation |
most_common_elems |
most_common_elem_freqs |
elem_count_histogram |

Увы. Но к самому индексу претензий нет, он работает, и неплохо:

demo=# explain (costs off,analyze)
select * from flights_bi where box(airport_coord) Bitmap Index Scan on flights_bi_box_idx
(actual time=158.083..158.083 rows=147720 loops=1)
Index Cond: (box(airport_coord)
Вывод, видимо, такой: если от геометрии нужно хоть что-то нетривиальное, нужен PostGIS. Во всяком случае, статистику он собирать умеет.

Внутри

Заглянуть внутрь BRIN-индекса позволяет штатное расширение pageinspect.

Во-первых, метаинформация подскажет нам размер зоны и сколько страниц отведено под revmap:

demo=# select * from brin_metapage_info(get_raw_page(‘flights_bi_scheduled_time_idx’,0));
magic | version | pagesperrange | lastrevmappage
————+———+—————+—————-
0xA8109CFA | 1 | 128 | 3
(1 row)

Здесь страницы с 1 по 3 — revmap, остальное — сводные данные. Можно получить из revmap ссылки на сводные данные каждой зоны. Скажем, информация о первой зоне, охватывающей первые 128 страниц таблицы, находится тут:

demo=# select * from brin_revmap_data(get_raw_page(‘flights_bi_scheduled_time_idx’,1)) limit 1;
pages
———
(6,197)
(1 row)

А вот сами сводные данные:

demo=# select * from brin_revmap_data(get_raw_page(‘flights_bi_scheduled_time_idx’,1)) offset 1 limit 1;
pages
———
(6,198)
(1 row)

Для inclusion-классов в поле value будет отображаться нечто наподобие

Свойства

Напомню, что соответствующие запросы приводились ранее.

amname | name | pg_indexam_has_property
———+—————+————————-
brin | can_order | f
brin | can_unique | f
brin | can_multi_col | t
brin | can_exclude | f

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

name | pg_index_has_property
—————+————————
clusterable | f
index_scan | f
bitmap_scan | t
backward_scan | f

Очевидно, что поддерживается только сканирование по битовой карте.

А вот отсутствие кластеризации может вызвать недоумение. Казалось бы, раз BRIN-индекс чувствителем к физическому порядку строк, то логично было бы и уметь кластеризовать данные по нему? Но нет, разве что можно создать «обычный» индекс (B-дерево или GiST, смотря по типу данных) и кластеризовать по нему. А впрочем, захочется ли вам кластеризовать предположительно огромную таблицу, учитывая эксклюзивную блокировку, время работы и расход места на диске во время перестроения?

Свойства уровня столбца:

name | pg_index_column_has_property
———————+——————————
asc | f
desc | f
nulls_first | f
nulls_last | f
orderable | f
distance_orderable | f
returnable | f
search_array | f
search_nulls | t

Тут сплошные «прочерки», кроме возможности работы с неопределенными значениями.

Источник