62.2. Поведение классов операторов B-дерева

Как показано в Таблице 38.2, класс операторов btree должен предоставить пять операторов сравнения, <, <=, =, >= и >. Хотя можно было ожидать, что частью этого класса будет и оператор <>, но это не так, потому что использовать <> в предложении WHERE для поиска по индексу практически бесполезно. (Для некоторых целей планировщик условно относит оператор <> к классу операторов btree, но он находит данный оператор как отрицание оператора =, а не обращаясь к pg_amop.)

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

Семейство операторов btree должно удовлетворять нескольким базовым положениям:

  • Оператор = должен представлять отношение эквивалентности; то есть для всех отличных от NULL значений A, B, C определённого типа данных:

    • A = A — истина (рефлексивность)

    • если A = B, то B = A (симметрия)

    • если A = B и B = C, то A = C (транзитивность)

  • Оператор < должен представлять отношение строгого упорядочивания; то есть для всех отличных от NULL значений A, B, C:

    • A < A — ложно (антирефлексивность)

    • если A < B и B < C, то A < C (транзитивность)

  • Более того, упорядочивание действует глобально; то есть для любых отличных от NULL значений A, B:

    • истинным является ровно одно из условий: A < B, A = B или B < A (трихотомия)

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

Остальные три оператора определяются через операторы = и < очевидным образом и должны работать согласованно с последними.

Для семейства операторов, поддерживающего несколько типов данных, вышеперечисленные законы должны выполняться при значениях A, B, C, относящихся к любым типам из семейства. Транзитивность обеспечить сложнее всего, так как в ситуациях с разными типами она требует согласованного поведения двух или трёх различных операторов. Так например, в одном семействе операторов не смогут работать типы float8 и numeric, по крайней мере при текущем подходе, когда значения numeric преобразуются во float8 для сравнения с float8. Из-за ограниченной точности типа float8 различные значения numeric могут оказаться равными одному значению float8, что нарушит закон транзитивности.

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

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

Для реализации поиска с сортировкой по расстоянию (поиска ближайших соседей) требуется определить только оператор расстояния (обычно обозначаемый <->) с соответствующим семейством операторов для сравнения расстояний в классе операторов индекса. Эти операторы должны удовлетворять следующим положениям относительно любых отличных от NULL значений A, B, C целевого типа данных:

  • A <-> B = B <-> A (симметрия)

  • если A = B, то A <-> C = B <-> C (эквивалентность расстояния)

  • если (A <= B и B <= C) или (A >= B и B >= C), то A <-> B <= A <-> C (монотонность)