Индексы 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)