67.3. Опорные функции B-деревьев

Как показано в Таблице 38.9, btree определяет одну необходимую и четыре необязательных опорных функции. Таким образом, пользователь может задать пять методов:

order

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

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

sortsupport

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

in_range

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

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

in_range(значение type1, база type1, смещение type2, вычитание bool, меньше bool)
returns bool

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

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

  • если !вычитание и !меньше, возвращается значение >= (база + смещение)

  • если !вычитание и меньше, возвращается значение <= (база + смещение)

  • если вычитание и !меньше, возвращается значение >= (база - смещение)

  • если вычитание и меньше, возвращается значение <= (база - смещение)

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

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

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

  • Если in_range с меньше = true возвращает true для некоторого значения1 и базы, true должно возвращаться для каждого значения2 <= значению1 с той же базой.

  • Если in_range с меньше = true возвращает false для некоторого значения1 и базы, false должно возвращаться для любого значения2 >= значению1 с той же базой.

  • Если in_range с меньше = true возвращает true для некоторого значения и базы1, true должно возвращаться для каждой базы2 >= базе1 с тем же значением.

  • Если in_range с меньше = true возвращает false для некоторого значения и базы1, false должно возвращаться для любой базы2 <= базе1 с тем же значением.

Аналогичные утверждения с противоположными условиями должны выполняться при меньше = false.

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

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

equalimage

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

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

equalimage(opcintype oid) returns bool

Её результатом будет статическая информация о классе операторов и правиле сортировки. Результат true означает, что функция order для класса операторов будет возвращать 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 класса операторов (при условии передачи обеим функциям одинакового OID правила сортировки).

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

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

options

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

Опорная функция options должна иметь сигнатуру

options(relopts local_relopts *) returns void

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

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