Индексы B-деревья
QHB включает в себя реализацию стандартной структуры данных индекса BTree (multi-way balanced tree). Любой тип данных, который может быть линейно упорядочен, может быть индексирован как B-дерево. Единственное ограничение заключается в том, что запись индекса не может превышать приблизительно одной трети страницы (после вынесения лишнего в TOAST, если это возможно).
Поскольку любой класс операторов B-дерева определяет порядок сортировки на своем типе данных, классы операторов B-дерева (точнее, семейства операторов) используются в QHB для сортировки в целом. Поэтому они приобрели некоторые функции, которые выходят за рамки того, что было бы необходимо только для поддержки B-деревьев, и их используют части системы, которые довольно далеки от методов доступа B-дерева.
Поведение классов операторов B-дерева
Класс операторов B-дерева должен предоставлять
пять операторов сравнения, < <= = >= >
. Можно было бы
ожидать, что <>
входит в эти операторы, но
это не так, потому что практически никогда не имеет смысл использовать индекс
для условия <>
. (Для некоторых целей
планировщик обрабатывает <>
как связанный с классом операторов B-дерева;
но он сразу вызывает его как NOT =
, а не ищет в pg_amop).
Если несколько типов данных имеют почти одинаковую семантику сортировки, их классы операторов можно сгруппировать в семейство операторов. Это выгодно, потому что позволяет планировщику делать выводы о межтиповых сравнениях. Каждый класс операторов в семействе должен содержать операторы для аргументов одинакового типа (и связанные с ними вспомогательные функции), в то время как операторы (плюс функция order) для аргументов разного типа являются необязательными. Однако рекомендуется включить полный набор межтиповых операторов в семейство, что гарантирует, что планировщик сможет вызвать любые условия сравнения, которые он выведет из транзитивности.
Существует несколько основных предположений, которым должно удовлетворять семейство операторов для B-деревьев:
-
Оператор
=
должен быть отношением эквивалентности, то есть для любых NOT NULL значенийA
,B
,C
:-
A = A
истинно (рефлексивность) -
A = B
влечетB = A
(симметричность) -
если
A = B
иB = C
, тоA = C
(транзитивность)
-
-
Оператор
<
должен представлять из себя отношение строгого порядка, то есть для любых NOT NULL значенийA
,B
,C
:-
A = A
ложно (антирефлексивность) -
если
A < B
иB < C
, тоA < C
(транзитивность)
-
-
Кроме того, порядок должен быть полным; то есть для любых NOT NULL значений
A
,B
должно быть верно ровно 1 утверждение из 3:A < B
, либоB < A
, либоA = B
(закон трихотомии)(Закон трихотомии требуется для использования семантики функций типа strcmp, возвращающих
-
/0
/+
в случае<
/=
/>
)
Остальные три оператора (> >= <=
) должны работать с тем же результатом, что и эквивалентная комбинация из <
и =
.
Для семейства операторов, поддерживающих несколько типов данных,
вышеуказанные законы должны выполняться, когда A
, B
, C
берутся
из любых типов данных в семействе. Закон транзитивности сложнее всего
обеспечить, поскольку в ситуациях разных типов это зависит от согласованности поведения
двух или трех различных операторов.
Для примера, нельзя поместить операторы для float8 и numeric в одно семейство,
по крайней мере не в сегодняшней ситуации, когда для сравнение float8 и numeric второе приводится тоже к типу float8. Найдутся 2 числа numeric X
и Y
, и число Z
типа float8,
такие что X < Y
, X = Z
и Y = Z
(нарушается транзитивность равенства). Дело в том, что из-за ограничения точности оба числа X
и Y
при приведении к float8 превращаются в одно и то же число.
Другое требование для семейства с несколькими типами данных заключается в том, что любые существующие неявные преобразования между типами данных, входящими в семейство операторов, должны сохранять результат сравнения.
Должно быть достаточно очевидно, почему B-дерево требует выполнения вышеприведенных законов внутри одного типа данных: без этого просто не будет чёткого упорядочивания ключей в дереве. Далее, чтобы был возможен индексный поиск при сравнении с ключом другого типа данных, требуется, чтобы сравнения вели себя разумно между двумя типами данных.
Соблюдение транзитивности для трех или более типов данных внутри семейства формально не обязательно для работы B-дерева, но некоторые оптимизации планировщика на это полагаются.
Вспомогательные функции B-дерева
B-дерево определяет одну обязательную и две факультативные вспомогательные функции:
-
order
Для каждой комбинации типов данных, для которых семейство операторов B-дерева предоставляет операторы сравнения, оно должно предоставить и функцию поддержки сравнения, зарегистрированную в pg_amproc как вспомогательная функция № 1 со свойствами amproclefttype/amprocrighttype равными типу левого и правого аргумента сравнения (т. е. тем же типам данных, с которыми зарегистрированы соответствующие операторы в pg_amop). Функция сравнения должна принимать NOT NULL значения
A
иB
и возвращать целое число, которое< 0
/0
/> 0
, когдаA < B
/A = B
/A > B
, соответственно. Результат NULL не допускается: все значения типа данных должны быть сравнимы.Если для типа данных применимы правила сортировки (COLLATION), то OID правила сортировки будет передан в вашу вспомогательную функцию сравнения, используя стандартный механизм PG_GET_COLLATION().
-
sortsupport
Опционально, семейство операторов B-дерева может предоставлять вспомогательную функцию №2 для оптимизированной сортировки. Эту функцию предоставляют (а B-дерево ее вызывает), чтобы ускорить сортировку. Если её не предоставить, то будут вызывать обычное попарное сравнение.
-
in_range
Опционально, семейство операторов B-дерева может предоставлять вспомогательную функцию №3 in_range. Она не используется при операциях B-дерева; она расширяет семантику семейства операторов, чтобы оно могло использоваться в аналитических (оконных) функциях, конкретно для вычисления границ рамки окна, заданных как RANGE offset PRECEDING или RANGE offset FOLLOWING (см. раздел Вызовы оконных функций).
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.
Что, собственно, это функция должна делать? Она должна "прибавить" или "вычесть" offset из base и после этого сравнить с val. Для комбинации флагов sub и less она должна возвращать:
-
если !sub и !less, результат val >= (base + offset)
-
если !sub и less, результат val <= (base + offset)
-
если sub и !less, результат val >= (base - offset)
-
если sub и less, результат val <= (base - offset)
Согласно стандарту SQL функция in_range должна проверить, что offset "неотрицательное", и в противном случае бросать ошибку ERRCODE_INVALID_PRECEDING_OR_FOLLOWING_SIZE (22013). Т.е. запрещено задавать границу рамки в виде RANGE BETWEEN -7 PRECEDING AND -5 FOLLOWING вместо RANGE BETWEEN 5 PRECEDING AND 7 FOLLOWING. Эта проверка возложена на in_range, потому что для пользовательских типов неочевидно, что является таким неправильным "отрицательным" значением. Если вы уверены, что "отрицательные" смещения корректно работают с вашим типом, то можете их разрешать.
Дополнительно ожидается, что не возникнет ошибок в случае переполнения при вычислении base + offset или base - offset; переполнение не должно помешать вашей функции выполнить сравнение. Также обратите внимание, чтобы при возникновение значений вроде "infinity" или "NaN" результат сравнения был корректным.
Функция in_range должна обладать "транзитивностью" совместно с обычными сравнениями класса операторов. Это можно формализовать следующими правилами:
-
если in_range(val1, ?, ?, ?, less = true) истинно, то после замены val1 на val2, такое что val2 <= val1, оно должно быть также истинно;
-
если in_range(val1, ?, ?, ?, less = true) ложно, то после замены val1 на val2, такое что val2 >= val1, оно должно быть также ложно;
-
если in_range(?, base1, ?, ?, less = true) истинно, то после замены base1 на base2, такое что base2 >= base1, оно должно быть также истинно;
-
если in_range(?, base1, ?, ?, less = true) ложно, то после замены base1 на base2, такое что base2 <= base1, оно должно быть также ложно;
-
при less = false должны выполнятся аналогичные утверждения (с инвертированными знаками)
Если для упорядочиваемого типа данных применимы правила сортировки (COLLATION), то OID правила сортировки будет передан в in_range, используя стандартный механизм PG_GET_COLLATION().
Функция in_range не обязана обрабатывать значение аргументов NULL и, скорее всего, будет строгой (STRICT)
-