Индексы 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_opsbigint< <= = >= >
bit_minmax_opsbit< <= = >= >
varbit_minmax_opsbit varying< <= = >= >
bytea_minmax_opsbytea< <= = >= >
bpchar_minmax_opscharacter< <= = >= >
char_minmax_ops"char"< <= = >= >
date_minmax_opsdate< <= = >= >
float8_minmax_opsdouble precision< <= = >= >
inet_minmax_opsinet< <= = >= >
int4_minmax_opsinteger< <= = >= >
interval_minmax_opsinterval< <= = >= >
macaddr_minmax_opsmacaddr< <= = >= >
macaddr8_minmax_opsmacaddr8< <= = >= >
name_minmax_opsname< <= = >= >
numeric_minmax_opsnumeric< <= = >= >
pg_lsn_minmax_opspg_lsn< <= = >= >
oid_minmax_opsoid< <= = >= >
float4_minmax_opsreal< <= = >= >
int2_minmax_opssmallint< <= = >= >
text_minmax_opstext< <= = >= >
tid_minmax_opstid< <= = >= >
date_minmax_opsdate< <= = >= >
timestamp_minmax_opstimestamp without time zone< <= = >= >
timestamptz_minmax_opstimestamp with time zone< <= = >= >
time_minmax_opstime without time zone< <= = >= >
timetz_minmax_opstime with time zone< <= = >= >
uuid_minmax_opsuuid< <= = >= >
box_inclusion_opsbox<< &< && &> >> ~= @> <@ &<| <<| |>> |&>
network_inclusion_opsinet&& >>= <<= = >> <<
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:

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

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

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

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

    Член класса операторовКакой объект использовать
    Вспомогательная функция 1внутренняя функция brin_minmax_opcinfo()
    Вспомогательная функция 2внутренняя функция brin_minmax_add_value()
    Вспомогательная функция 3внутренняя функция brin_minmax_consistent()
    Вспомогательная функция 4внутренняя функция brin_minmax_union()
    Стратегия 1оператор меньше
    Стратегия 2оператор меньше-или-равно
    Стратегия 3оператор равно
    Стратегия 4оператор больше-или-равно
    Стратегия 5оператор больше
  4. Для создания класса оператора для сложного типа данных, наборы значений которого "обрамляются" "рамками" некоторого другого типа, можно использовать вспомогательные функции от семейства 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.