Индексы BRIN

Введение
Обслуживание индекса
Встроенные классы операторов
Расширяемость

Введение

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

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

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

Размер диапазона блоков определяется во время создания индекса параметром pages_per_range. Количество записей индекса будет равно размеру таблицы в страницах, деленному на выбранное значение pages_per_range. Чем меньше число, тем больше размер индекса, но и тем выше его точность.

Обслуживание индекса

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

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

Обсчёт "новых" диапазонов происходит при работе VACUUM. Вакуум можно запустить вручную, также обсчёт можно инициировать вызовом функции brin_summarize_new_values(regclass). Если включить параметр autosummarize, то "новые" диапазоны будут пересчитываться в фоне процессом Автовакуума. Если он не успевает это делать, то в журнале сервера могут появиться сообщения вида

LOG:  request for BRIN range summarization for index "brin_wi_idx" page 128 was not recorded

По умолчанию параметр autosummarize выключен, т.к. это увеличивает нагрузку системы.

При удалении строк из таблицы не происходит пересчёта BRIN-индекса (это было бы слишком долго). После массовых удалений можно пересчитать BRIN-индекс по конкретным диапазонам, выполнив brin_desummarize_range (regclass, bigint) + brin_summarize_range (regclass, bigint), или по всей таблице, перестроив индекс целиком. Если этого не сделать, индекс будет говорить, что в таком-то диапазоне возможно есть такие-то данные даже после того, как вы удалите все такие данные.

Встроенные классы операторов

Основной дистрибутив QHB включает классы операторов BRIN, показанные в следующей таблице.

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

Имя	Индексируемый тип данных	Поддерживаемые операторы при поиске
int8_minmax_ops	bigint	`< <= = >= >`
bit_minmax_ops	bit	`< <= = >= >`
varbit_minmax_ops	bit varying	`< <= = >= >`
bytea_minmax_ops	bytea	`< <= = >= >`
bpchar_minmax_ops	character	`< <= = >= >`
char_minmax_ops	"char"	`< <= = >= >`
date_minmax_ops	date	`< <= = >= >`
float8_minmax_ops	double precision	`< <= = >= >`
inet_minmax_ops	inet	`< <= = >= >`
int4_minmax_ops	integer	`< <= = >= >`
interval_minmax_ops	interval	`< <= = >= >`
macaddr_minmax_ops	macaddr	`< <= = >= >`
macaddr8_minmax_ops	macaddr8	`< <= = >= >`
name_minmax_ops	name	`< <= = >= >`
numeric_minmax_ops	numeric	`< <= = >= >`
pg_lsn_minmax_ops	pg_lsn	`< <= = >= >`
oid_minmax_ops	oid	`< <= = >= >`
float4_minmax_ops	real	`< <= = >= >`
int2_minmax_ops	smallint	`< <= = >= >`
text_minmax_ops	text	`< <= = >= >`
tid_minmax_ops	tid	`< <= = >= >`
date_minmax_ops	date	`< <= = >= >`
timestamp_minmax_ops	timestamp without time zone	`< <= = >= >`
timestamptz_minmax_ops	timestamp with time zone	`< <= = >= >`
time_minmax_ops	time without time zone	`< <= = >= >`
timetz_minmax_ops	time with time zone	`< <= = >= >`
uuid_minmax_ops	uuid	`< <= = >= >`
box_inclusion_ops	box	<< &< && &> >> ~= @> <@ &<\| <<\| \|>> \|&>
network_inclusion_ops	inet	`&& >>= <<= = >> <<`
range_inclusion_ops	любой тип-диапазон	<< &< && &> >> @> <@ -\|- = < <= = > >=

Расширяемость

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

Все, что требуется, чтобы BRIN-индекс заработал, - это реализовать несколько пользовательских методов, которые определят поведение сводных значений, хранящихся в индексе, и их взаимодействие с ключами сканирования (= значениями в столбце таблицы). У BRIN-индексов четкий интерфейс, дающий хорошую расширяемость и переиспользование кода.

Существует четыре метода, которые должен предоставить класс оператора для использования в BRIN:

```
BrinOpcInfo *opcInfo(Oid type_oid)
```
Возвращает внутреннюю информацию о сводных данных индексированных столбцов. Конкретнее, должна вернуть указатель на структуру BrinOpcInfo, выделенную с помощью palloc. Определение структуры такое:
```
typedef struct BrinOpcInfo
{
    /* Количество совместно проиндексированных столбцов */
    uint16      oi_nstored;

    /* Приватные данные класса оператора */
    void       *oi_opaque;

    /* Элементы кеша типов для проиндексированных столбцов */
    TypeCacheEntry *oi_typcache[FLEXIBLE_ARRAY_MEMBER];
} BrinOpcInfo;
```
Brinpcinfo::oi_opaque используется для передачи информации между методами класса операторов во время сканирования индекса.
```
bool consistent(BrinDesc *bdesc, BrinValues *column, ScanKey key)
```
Вернуть, входит ли key (то, что ищут) в сводное значение column из индекса. key->sk_attno содержит номер столбца — это важно, если у вас многоколоночный индекс
```
bool addValue(BrinDesc *bdesc, BrinValues *column, Datum newval, bool isnull)
```
Обновить сводную информацию диапазона column с учетом нового значения столбца newval. Вернуть true, если column изменилось
```
bool unionTuples(BrinDesc *bdesc, BrinValues *a, BrinValues *b)
```
Объединить две сводки: изменить сводку a, включив в нее сводку b. Не надо менять сводку b! Вернуть false, если не потребовалось менять a (т.к. уже a полностью включало b).

Способы создания нового класса операторов, совместимого с BRIN:

Стандартный дистрибутив включает поддержку двух семейств классов операторов: minmax и inclusion. Есть реализация соответствующих классов операторов для всех встроенных типов данных. Аналогичные классы операторов для других типов могут быть выведены без написания какого-либо кода. Достаточно просто объявить этот класс в системном каталоге. Обратите внимание, что в код вспомогательных функций этих семейств встроены некоторые предположения о семантике стратегий операторов.
Вы можете создать классы операторов с совершенно другой семантикой, реализовав четыре основных вспомогательные функции, описанных выше. Обратите внимание, что обратная совместимость между мажорными релизами не гарантируется: в следующих версиях может измениться интерфейс этих функций.

Использовать вспомогательные функции от семейства minmax, вместе с набором операторов для типа данных.

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

Член класса операторов	Какой объект использовать
Вспомогательная функция 1	внутренняя функция brin_minmax_opcinfo()
Вспомогательная функция 2	внутренняя функция brin_minmax_add_value()
Вспомогательная функция 3	внутренняя функция brin_minmax_consistent()
Вспомогательная функция 4	внутренняя функция brin_minmax_union()
Стратегия 1	оператор меньше
Стратегия 2	оператор меньше-или-равно
Стратегия 3	оператор равно
Стратегия 4	оператор больше-или-равно
Стратегия 5	оператор больше

Для создания класса оператора для сложного типа данных, наборы значений которого "обрамляются" "рамками" некоторого другого типа, можно использовать вспомогательные функции от семейства inclusion совместно с соответствующими операторами и дополнительными функциями, как показано в следующей таблице. Из них только одна дополнительная функция, которая может быть написана на любом языке, является обязательной. Реализация необязательных дополнительных функций позволяет некоторые оптимизации при работе индекса. Все операторы необязательные, но для некоторых операторов нужно реализовать другой для комплектности, как показано в таблице

Член класса операторов	Какой объект использовать	Требует наличия
Вспомогательная функция 1	внутренняя функция brin_inclusion_opcinfo()
Вспомогательная функция 2	внутренняя функция brin_inclusion_add_value()
Вспомогательная функция 3	внутренняя функция brin_inclusion_consistent()
Вспомогательная функция 4	внутренняя функция brin_inclusion_union()
Вспомогательная функция 11	функция для объединения двух элементов (обязательная)
Вспомогательная функция 12	дополнительная функция для проверки возможности слияния двух элементов
Вспомогательная функция 13	дополнительная функция, чтобы проверить, если элемент содержится в другом
Вспомогательная функция 14	необязательная функция для проверки, является ли элемент пустым
Стратегия 1	оператор левее	Стратегия 4
Стратегия 2	оператор не-выпирает-справа	Стратегия 5
Стратегия 3	оператор перекрывается
Стратегия 4	оператор не-выпирает-слева	Стратегия 1
Стратегия 5	оператор правее	Стратегия 2
Стратегия 6, 18	оператор такой-же-или-равен	Стратегия 7
Стратегия 7, 13, 16, 24, 25	оператор охватывает-или-равен
Стратегия 8, 14, 26, 27	оператор содержится-в-или-равен	Стратегия 3
Стратегия 9	оператор не-выпирает-сверху	Стратегия 11
Стратегия 10	оператор ниже	Стратегия 12
Стратегия 11	оператор выше	Стратегия 9
Стратегия 12	оператор не-выпирает-снизу	Стратегия 10
Стратегия 20	оператор меньше	Стратегия 5
Стратегия 21	оператор меньше-или-равно	Стратегия 5
Стратегия 22	оператор больше	Стратегия 1
Стратегия 23	оператор больше-или-равно	Стратегия 1

Номера вспомогательных функций 1-10 зарезервированы для внутренних функций BRIN, поэтому функции уровня SQL начинаются с числа 11. Вспомогательная функция номер 11 является главной, обязательной для построения индекса. Она принимает два аргумента того же типа, что и класс оператора, и возвращать их объединение. Класс оператора семейства inclusion может хранить результат объединения в другом типа данных, он задается параметром STORAGE. Возвращаемое значение функции №11 должно быть типа STORAGE.

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

И minmax, и inclusion поддерживают операторы, работающие с разными типами данных, хотя с ними зависимости становятся более сложными. Класс операторов minmax требует, чтобы был определен полный набор операторов с обоими аргументами, имеющими один и тот же тип. Это позволяет поддерживать дополнительные типы данных путем определения дополнительных наборов операторов. Стратегии класса операторов inclusion требуют, чтобы оператор принимал первый аргумент типа STORAGE, а второй аргумент типа данных столбца таблицы. Смотрите float4_minmax_ops в качестве примера расширения minmax, а также box_inclusion_ops в качестве примера расширения inclusion.

Документация по СУБД «Квант-Гибрид» 1.3.0

Индексы BRIN

Введение

Обслуживание индекса

Встроенные классы операторов

Расширяемость