Индексы B-деревья

QHB включает в себя реализацию стандартной структуры данных индекса B-дерева (многонаправленного сбалансированного дерева — btree). Любой тип данных, который можно отсортировать в четком линейном порядке, может быть загружен в индекс B-дерево. Единственное ограничение заключается в том, что запись индекса не может превышать приблизительно одной трети страницы (после сжатия TOAST, если применимо).

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

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

Класс операторов B-дерева должен предоставлять пять операторов сравнения: <, <=, =, >= и >. Можно было бы ожидать, что в эти операторы также должен входить <>, но это не так, потому что практически никогда не имеет смысл использовать <> в предложении WHERE для поиска по индексу. (Для некоторых целей планировщик обрабатывает <> как связанный с классом операторов B-дерева; но он находит данный оператор через отрицание оператора =, а не обращаясь к pg_amop).

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

Существует несколько основных предположений, которым должно удовлетворять семейство операторов для B-деревьев:

  • Оператор = должен быть отношением эквивалентности, то есть для любых отличных от 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 должно быть верно ровно 1 утверждение из 3: A < B, либо B < A, либо A = B (закон трихотомии)

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

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

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

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

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

Вспомогательные функции B-дерева

B-дерево определяет одну обязательную и четыре факультативные вспомогательные функции:

order

Для каждой комбинации типов данных, для которых семейство операторов
B-дерева предоставляет операторы сравнения, оно должно предоставить и
вспомогательную функцию сравнения, зарегистрированную в ***pg\_amproc*** как вспомогательная функция номер 1
со свойствами *amproclefttype/amprocrighttype*, равными левому и правому
типу данных сравнения (т. е. тем же типам данных, с которыми
зарегистрированы соответствующие операторы в ***pg\_amop***). Функция
сравнения должна принимать отличные от *NULL* значения **A** и **B** и возвращать
целое число, которое < 0, 0 или > 0, когда **A < B**, **A = B** или **A > B** соответственно.
Результат *NULL* не допускается: все значения типа данных должны быть
сравнимы.

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

<!-- not open source
Примеры реализации order ищите в файле *src/backend/access/nbtree/nbtcompare.c* -->    

sortsupport

Опционально семейство операторов B-дерева может предоставлять *вспомогательную(ые) функцию(и) сортировки*, регистрируемую как
вспомогательная функция номер 2. Эти функции позволяют
реализовывать сравнения для целей сортировки более эффективно, чем
при простом вызове вспомогательной функции сравнения.

<!-- not open source
API, участвующие в этом, определены в: *src/include/utils/sortsupport.h*.
-->
<!--  "(или несколько функций)" как их различает система, если они все №2 ?! -->

in_range

Опционально семейство операторов B-дерева может предоставлять вспомогательную(ые) функцию(и) *in\_range*, регистрируемую как
вспомогательная функция номер 3.
Такие функции не используется при операциях B-дерева; они
расширяют семантику семейства операторов, чтобы оно могло поддерживать оконные предложения, содержащие типы границ рамки **RANGE *смещение* PRECEDING** и
**RANGE *смещение* FOLLOWING** (см. раздел [Вызовы оконных функций]). По сути, дополнительная информация позволяет добавлять или вычитать значение ***смещения*** способом, соответствующим принятому в семействе порядку сортировки.

Функция *in\_range* должна иметь сигнатуру

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

***Значение*** и ***база*** должны быть одинакового типа, одного из поддерживаемых семейством операторов
(т. е. типом, для которого задается порядок). Однако ***смещение*** может быть другого типа,
который никаким другим образом данным семейством может и не поддерживаться.
Например, встроенное семейство операторов *time\_ops*  предоставляет
функцию *in\_range* которая имеет параметр ***смещение*** типа *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* с помощью стандартного механизма *PG\_GET\_COLLATION()* будет передан OID соответствующего правила сортировки.

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

equalimage

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

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

```SQL
equalimage(opcintype oid) returns bool
```

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

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

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

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

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

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

options

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

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

```sql
options(relopts local_relopts *) returns void
```

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

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

Реализация

В этом разделе изложена подробная информация о реализации индекса В-дерева, которая может быть полезна для специалистов.

Структура В-дерева

В QHB индексы В-деревья — это многоуровневые древовидные структуры, где каждый уровень дерева можно использовать в качестве двусвязного списка страниц. Единственная метастраница хранится в фиксированном положении в начале первого файла сегмента индекса. Все остальные страницы делятся на листовые и внутренние. Листовые страницы находятся на самом нижнем уровне дерева. Все остальные уровни состоят из внутренних страниц. Каждая листовая страница содержит кортежи, которые указывают на строки таблицы. Каждая внутренняя страница содержит кортежи, которые указывают на следующий уровень вниз по дереву. Обычно листовые страницы составляют более 99% всех страниц. Как внутренние, так и листовые страницы используют стандартный формат страницы, описанный в разделе Внутренняя структура страницы базы данных.

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

Дедупликация

Дубликат — это кортеж листовой страницы (кортеж, который указывает на строку таблицы), в котором все ключевые столбцы индекса содержат значения, совпадающие с соответствующими значениями столбца из по крайней мере еще одного кортежа листовой страницы в том же индексе. На практике дублирующиеся кортежи встречаются довольно часто. Индексы В-деревья могут использовать для дубликатов особое экономящее пространство представление при включении факультативного механизма — дедупликации.

Действие механизма дедупликации заключается в периодическом объединении групп дублирующихся кортежей с образованием одного кортежа со списком идентификаторов для каждой группы. В таком представлении ключевое(ые) значение(я) столбца находятся в единственном экземпляре. Затем идет отсортированный массив идентификаторов TID, которые указывают на строки в таблице. Это значительно уменьшает размер хранимых индексов, где каждое значение (или каждая отдельная комбинация значений столбца) появляется, в среднем, несколько раз. Это может значительно сократить время отклика запросов и в целом существенно повысить скорость их обработки. Также могут сильно снизиться издержки на регулярную очистку индекса.

Примечание
Дедупликация В-дерева также эффективна при работе с «дубликатами», которые содержат значение NULL, несмотря на то, что значения NULL, согласно операторам = из любого класса операторов В-дерева, не считаются равными друг другу. С точки зрения любой части реализации, которая понимает дисковую структуру В-дерева, NULL — это просто еще одно значение из домена значений индекса.

Процесс дедупликации запускается только по необходимости, когда вставляется новый элемент, который не помещается на существующую листовую страницу. Это предотвращает (или, по крайней мере, откладывает) разделение листовой страницы. В отличие от кортежей со списком идентификаторов GIN, в B-дереве этим кортежам не нужно расширяться всякий раз, когда вставляется новый дубликат; они просто являются альтернативным физическим представлением исходного логического содержимого листовой страницы. При смешанной нагрузке типа чтение/запись такая модель ставит во главу угла согласованную производительность. Для большинства клиентских приложений дедупликация должна обеспечить как минимум удовлетворительное увеличение производительности. По умолчанию она включена.

Команды CREATE INDEX и REINDEX используют дедупликацию, чтобы создать кортежи со списком идентификаторов, хотя применяемая ими стратегия слегка отличается. Каждая группа обычных дублирующихся кортежей, обнаруженных во взятых из таблицы отсортированных входных данных, объединяется в кортеж со списком идентификаторов до того, как добавляется на текущую ожидающую листовую страницу. В каждый такой кортеж упаковывается максимально возможное количество идентификаторов TID. Листовые страницы записываются обычным способом, без каких-либо отдельных проходов для исключения дубликатов. Эта стратегия очень подходит командам CREATE INDEX и REINDEX, поскольку они относятся к разовым групповым операциям.

При рабочих нагрузках с преобладанием записи, которые не получают преимуществ от дедупликации из-за малого количества или отсутствия дублированных значений в индексах, ее применение приведет к небольшому постоянному снижению производительности (если только она явно не отключена). Чтобы отключить дедупликацию в отдельных индексах, можно воспользоваться параметром хранения deduplicate_items. При рабочих нагрузках только на чтение производственных издержек не возникает, поскольку кортежи со списком идентификаторов читаются по меньшей мере так же эффективно, как и кортежи в стандартном представлении. Поэтому обычно в таких случаях отключать дедупликацию бесполезно.

Непосредственно индексы В-деревья не учитывают, что в среде MVCC может быть несколько сохранившихся версий одной логической строки таблицы; для индекса каждый кортеж является независимым объектом, которому требуется отдельный элемент индекса. Иногда «версионные дубликаты» могут накапливаться и негативно влиять на время отклика и скорость обработки запросов. Обычно это случается при нагрузках с преобладанием UPDATE, где большая часть отдельных обновлений не может применить оптимизацию HOT (обычно вследствие того, что как минимум один столбец индекса подвергается изменению, требующему новый набор версий индексного кортежа — по одному новому кортежу для каждого индекса). В действительности дедупликация В-дерева устраняет разбухание индекса, вызванное тиражированием версий. Обратите внимание, что из-за тиражирования версий даже кортежи уникального индекса не обязательно физически уникальны при хранении на диске. К уникальным индексам оптимизация путем дедупликации применяется выборочно и нацеливается на те страницы, на которых могут содержаться версионные дубликаты. Глобальная же цель — дать команде VACUUM больше времени на выполнение, прежде чем из-за тиражирования версий произойдет «ненужное» разделение страницы.

Совет
Для определения того, следует ли дедупликации выполняться в уникальном индексе, применяется специальный эвристический алгоритм. Зачастую он может перейти напрямую к разделению листовой страницы без расходов на лишние циклы холостых проходов дедупликации. Если вас беспокоят издержки на бесполезную дедупликацию, можете выборочно задать значение deduplicate_items = off для отдельных индексов. В уникальных же индексах дедупликацию вполне можно оставить включенной — потери от этого будут невелики.

Из-за ограничений на уровне реализации дедупликацию можно использовать не везде. Безопасность ее применения определяется при выполнении команды CREATE INDEX или REINDEX.

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

  • Дедупликация не может применяться с типами text, varchar и char при использовании недетерменированного правила сортировки, т. к. среди равных значений должны сохраняться различия в регистре и диакритических знаках.

  • Дедупликация не может применяться с типом numeric, т. к. среди равных значений должен сохраняться масштаб числового отображения.

  • Дедупликация не может применяться с типом jsonb, т. к. внутри класса операторов В-дерева jsonb используется тип numeric.

  • Дедупликация не может применяться с типами float4 и float8, т. к. у этих типов разное представление для значений -0 и 0, которые при этом все равно считаются равными. Это различие должно быть сохранено.

Есть еще одно дополнительное ограничение на уровне реализации, которое может быть убрано в будущих версиях QHB:

  • Дедупликация не может применяться с типами-контейнерами (такими как составные или диапазонные типы или массивы).

Есть еще одно дополнительное ограничение на уровне реализации, которое действует независимо от используемого класса оператора или правила сортировки:

  • Дедупликация не может применяться в индексах с INCLUDE.