Перейти к основному содержимому

Функции поддержки B-дерева

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

order

Для каждой комбинации типов данных, для которых семейство операторов btree предоставляет операторы сравнения, оно должно предоставить функцию поддержки сравнения, зарегистрированную в pg_amproc с номером функции поддержки 1 и amproclefttype/amprocrighttype, равным левому и правому типам данных для сравнения (т.е. тем же типам данных, с которыми операторы сравнения зарегистрированы в pg_amop). Функция сравнения должна принимать два ненулевых значения A и B и возвращать значение int32, которое будет < 0, 0 или > 0, если A < B, A = B или A > B соответственно. Нулевой результат недопустим: все значения типа данных должны быть сопоставимы. Примеры смотрите в src/backend/access/nbtree/nbtcompare.c.

Если сравниваемые значения имеют сортируемый тип данных, опорной функции сравнения будет передан OID соответствующего правила сортировки через стандартный механизм PG_GET_COLLATION().

sortsupport

Опционально семейство операторов btree может предоставлять функцию(и) поддержки сортировки, зарегистрированную под номером 2. Эти функции позволяют реализовать сравнение для целей сортировки более эффективным способом, чем наивный вызов функции поддержки сравнения. API, связанные с этим, определены в src/include/utils/sortsupport.h.

in_range

Опционально семейство операторов btree может предоставлять функцию(и) поддержки in_range, зарегистрированную под номером 3. Они не используются во время операций с индексами btree; скорее, они расширяют семантику семейства операторов, чтобы оно могло поддерживать оконные клаузулы, содержащие типы RANGE offset PRECEDING и RANGE offset FOLLOWING frame bound. По сути, дополнительная информация заключается в том, как добавить или вычесть значение смещения таким образом, чтобы это было совместимо с упорядочиванием данных в семействе.

Функция in_range должна иметь сигнатуру:

in_range(val type1, base type1, offset type2, sub bool, less bool)
returns bool

val (значение) и base (база) должны быть одного типа, то есть одного из типов, поддерживаемых семейством операторов (то есть типа, для которого оно обеспечивает упорядочивание). Однако offset (смещение) может быть другого типа, который может быть иным, не поддерживаемым семейством. Например, встроенное семейство time_ops предоставляет функцию in_range, которая имеет offset типа interval. Семейство может предоставлять функции in_range для любого из своих поддерживаемых типов и одного или нескольких типов offset. Каждая функция in_range должна быть введена в pg_amproc с amproclefttype, равным type1, и amprocrighttype, равным type2.

Основная семантика функции in_range зависит от двух параметров булевого флага. Она должна складывать или вычитать base и offset, а затем сравнивать val с результатом, как показано ниже:

  • если !sub и !less, возвращаем val >= (base + offset);
  • если !sub и less, возвращаем val <= (base + offset);
  • если sub и !less, возвращаем val >= (base - offset);
  • если sub и less, возвращаем val <= (base - offset).

Примечание:

sub – вычитание, less – меньше.

Перед этим функция должна проверить знак offset: если он меньше нуля, выдать ошибку ERRCODE_INVALID_PRECEDING_OR_FOLLOWING_SIZE (22013) с текстом ошибки типа «invalid preceding or following size in window function». (Этого требует стандарт SQL, хотя нестандартные семейства операторов, возможно, решат проигнорировать это ограничение, поскольку семантическая необходимость в нем, по-видимому, невелика). Это требование делегировано функции in_range, так что коду ядра не нужно понимать, что означает «меньше нуля» для конкретного типа данных.

Дополнительное ожидание заключается в том, что функции in_range должны, если это возможно, избегать выброса ошибки, если base + offset или base - offset переполняются. Правильный результат сравнения может быть определен, даже если это значение выходит за пределы диапазона типа данных. Обратите внимание, что если тип данных включает такие понятия, как «бесконечность» или «NaN», может потребоваться дополнительное внимание, чтобы результаты in_range соответствовали нормальному порядку сортировки семейства операторов.

Результаты функции in_range должны соответствовать порядку сортировки, налагаемому семейством операторов. Точнее, при любых фиксированных значениях offset и sub, тогда:

  • Если in_range с less = true истинно для некоторых val1 и base, то оно должно быть истинно для каждого val2 <= val1 с той же base.
  • Если in_range с less = true ложно для некоторых val1 и base, то оно должно быть ложно для каждого val2 >= val1 с той же base.
  • Если in_range с less = true истинно для некоторых val и base1, то оно должно быть истинно для всех base2 >= base1 с тем же val.
  • Если in_range с less = true ложно для некоторых val и base1, то оно должно быть ложно для всех base2 <= base1 с тем же val.

Аналогичные утверждения с инвертированными условиями имеют место, если less = false.

Если упорядочиваемый тип (type1) является сортируемым, функции in_range будет передан OID соответствующего правила сортировки через стандартный механизм PG_GET_COLLATION().

Функции in_range не должны обрабатывать NULL-входы и обычно помечаются как строгие.

equalimage

Опционально семейство операторов btree может предоставлять функции поддержки equalimage («равенство подразумевает равенство изображений»), зарегистрированные под номером 4. Эти функции позволяют коду ядра определить, когда безопасно применять оптимизацию дедупликации btree. В настоящее время функции equalimage вызываются только при построении или перестройке индекса.

Функция equalimage должна иметь сигнатуру:

equalimage(opcintype oid) returns bool

Возвращаемое значение - это статическая информация о классе оператора и коллизии. Возвращение true означает, что функция упорядочивания для данного класса операторов гарантированно вернет 0 («аргументы равны») только в том случае, если ее аргументы A и B также взаимозаменяемы без потери семантической информации. Отсутствие регистрации функции equalimage или возвращение false указывает на то, что это условие не может быть выполнено.

Аргумент opcintype - это pg_type.oid типа данных, который индексирует класс оператора. Это удобство, которое позволяет повторно использовать одну и ту же базовую функцию equalimage в разных классах операторов. Если тип opcintype поддерживает правила сортировки, то в функцию equalimage будет передан соответствующий OID, используя стандартный механизм PG_GET_COLLATION().

С точки зрения класса операторов возвращаемое значение true означает, что возможно безопасное применение исключения дубликатов (или оно безопасно для правила сортировки, OID которого был передан функции equalimage). Однако основной код будет считать дедупликацию безопасной для индекса только в том случае, если каждый индексируемый столбец использует операторный класс, который регистрирует функцию equalimage, и каждая функция действительно возвращает true при вызове.

Равенство изображений - это почти то же условие, что и простое побитовое равенство. Есть одно тонкое отличие: при индексировании типа данных varlena представление на диске двух данных, равных по изображению, может не быть побитовым равенством из-за непоследовательного применения сжатия TOAST на входе. В общем случае, когда функция equalimage операторного класса возвращает true, можно предположить, что функция на C datum_image_eq() всегда будет согласована с функцией order операторного класса (при условии, что функции equalimage и order передается один и тот же идентификатор OID).

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

В классах операторов, входящих в состав основного дистрибутива PostgreSQL, принято регистрировать запасную, общую функцию equalimage. Большинство классов операторов регистрируют btequalimage(), что указывает на безусловную безопасность дедупликации. Операторы классов для типов данных, поддерживающих правила сортировки, например, для типа text, регистрируют функцию btvarstrequalimage(), которая устанавливает, что исключение дубликатов безопасно с детерминированными правилами сортировки. Для сохранения порядка в сторонних расширениях также рекомендуется регистрировать их собственные функции equalimage.

options

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

Функция поддержки опций должна иметь сигнатуру:

options(relopts local_relopts *) returns void

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

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