Автор Егор Рогов
Мы уже обсуждали индексатор PostgreSQL и интерфейс методов доступа, а также хеш-индекс, один из методов доступа. Теперь мы рассмотрим B-дерево, наиболее традиционный и широко используемый индекс. Эта статья большая, так что наберитесь терпения.
Bдерево
Структура
Тип индекса B-tree, реализованный как метод доступа btree, подходит для данных, которые можно сортировать. Другими словами, для типа данных должны быть определены операторы больше, больше или равно, меньше, меньше или равно и равно. Обратите внимание, что одни и те же данные иногда могут быть отсортированы по-разному, что возвращает нас к понятию семейства операторов.
Как всегда, индексные строки B-дерева упакованы в страницы. На листовых страницах эти строки содержат данные для индексации (ключи) и ссылки на строки таблицы (TID). На внутренних страницах каждая строка ссылается на дочернюю страницу индекса и содержит минимальное значение на этой странице.
B-деревья имеют несколько важных особенностей:
- B-деревья сбалансированы, то есть каждая листовая страница отделена от корня одинаковым количеством внутренних страниц. Поэтому поиск любого значения занимает одинаковое время.
- B-деревья разветвлены, то есть каждая страница (обычно 8 КБ) содержит множество (сотни) TID. В результате глубина B-деревьев довольно мала, фактически до 4–5 для очень больших таблиц.
- Данные в индексе отсортированы по неубыванию (как между страницами, так и внутри каждой страницы), а страницы одного уровня связаны друг с другом двунаправленным списком. Таким образом, мы можем получить упорядоченный набор данных, просто обходя список в том или ином направлении, не возвращаясь каждый раз к корню.
Ниже приведен упрощенный пример индекса одного поля с целочисленными ключами.
Самая первая страница индекса — это метастраница, которая ссылается на корень индекса. Внутренние узлы расположены ниже корня, а конечные страницы — в самом нижнем ряду. Стрелки вниз представляют ссылки от листовых узлов к строкам таблицы (TID).
Поиск по равенству
Рассмотрим поиск значения в дереве по условию «индексированное-поле = выражение». Допустим, нас интересует ключ на 49.
Поиск начинается с корневого узла, и нам нужно определить, к какому из дочерних узлов спуститься. Зная о ключах в корневом узле (4, 32, 64), мы определяем диапазоны значений в дочерних узлах. Поскольку 32 ≤ 49 ‹ 64, нам нужно спуститься ко второму дочернему узлу. Далее тот же процесс рекурсивно повторяется, пока мы не достигнем конечного узла, из которого можно получить необходимые TID.
На самом деле ряд деталей усложняет этот, казалось бы, простой процесс. Например, индекс может содержать неуникальные ключи и может быть так много одинаковых значений, что они не поместятся на одной странице. Возвращаясь к нашему примеру, кажется, что мы должны спуститься от внутреннего узла по ссылке к значению 49. Но, как видно из рисунка, таким образом мы пропустим один из ключей «49» на предыдущей листовой странице. . Поэтому, как только мы нашли точно такой же ключ на внутренней странице, мы должны спуститься на одну позицию влево, а затем просмотреть строки индекса нижележащего уровня слева направо в поисках искомого ключа.
(Еще одна сложность заключается в том, что во время поиска другие процессы могут изменить данные: дерево может быть перестроено, страницы могут быть разделены на две и т. д. Все алгоритмы спроектированы таким образом, чтобы эти параллельные операции не мешали друг другу и не вызывали лишних блокировок. везде, где это возможно. Но мы не будем распространяться об этом.)
Поиск по неравенству
При поиске по условию «индексированное-поле ≤ выражение» (или «индексированное-поле ≥ выражение») , мы сначала находим значение (если есть) в индексе по условию равенства «indexed-field = expression», а затем проходим листовые страницы в соответствующем направлении к конец.
На рисунке показан этот процесс для n ≤ 35:
Операторы «больше» и «меньше» поддерживаются аналогичным образом, за исключением того, что первоначально найденное значение необходимо отбросить.
Поиск по диапазону
При поиске по диапазону «выражение1 ≤ индексированное-поле ≤ выражение2» мы находим значение по условию «индексированное-поле = выражение1», а затем продолжайте просматривать конечные страницы, пока выполняется условие «индексированное-поле ≤ выражение2»; или наоборот: начнем со второго выражения и идем в противоположном направлении, пока не дойдем до первого выражения.
На рисунке показан этот процесс для условия 23 ≤ n ≤ 64:
Пример
Давайте посмотрим на пример того, как выглядят планы запросов. Как обычно, мы используем демонстрационную базу данных, а в этот раз рассмотрим таблицу самолетов. Она содержит всего девять строк, и планировщик предпочел бы не использовать индекс, поскольку вся таблица умещается на одной странице. Но эта таблица интересна нам в иллюстративных целях.
demo=# select * from aircrafts;aircraft_code | model | range ---------------+---------------------+------- 773 | Boeing 777-300 | 11100 763 | Boeing 767-300 | 7900 SU9 | Sukhoi SuperJet-100 | 3000 320 | Airbus A320-200 | 5700 321 | Airbus A321-200 | 5600 319 | Airbus A319-100 | 6700 733 | Boeing 737-300 | 4200 CN1 | Cessna 208 Caravan | 1200 CR2 | Bombardier CRJ-200 | 2700 (9 rows)demo=# create index on aircrafts(range);demo=# set enable_seqscan = off;
(Или явно «создать индекс для самолетов, используя btree (диапазон)», но это B-дерево, которое строится по умолчанию.)
Поиск по равенству:
demo=# explain(costs off) select * from aircrafts where range = 3000;QUERY PLAN --------------------------------------------------- Index Scan using aircrafts_range_idx on aircrafts Index Cond: (range = 3000) (2 rows)
Поиск по неравенству:
demo=# explain(costs off) select * from aircrafts where range < 3000;QUERY PLAN --------------------------------------------------- Index Scan using aircrafts_range_idx on aircrafts Index Cond: (range < 3000) (2 rows)
И по диапазону:
demo=# explain(costs off) select * from aircrafts where range between 3000 and 5000;QUERY PLAN ----------------------------------------------------- Index Scan using aircrafts_range_idx on aircrafts Index Cond: ((range >= 3000) AND (range <= 5000)) (2 rows)
Сортировка
Еще раз подчеркнем, что при любом виде сканирования (индексном, только индексном или битовом) метод доступа «btree» возвращает упорядоченные данные, что мы хорошо видим на приведенных выше рисунках.
Поэтому, если таблица имеет индекс по условию сортировки, оптимизатор рассмотрит оба варианта: индексный просмотр таблицы, который легко возвращает отсортированные данные, и последовательный просмотр таблицы с последующей сортировкой результата.
Порядок сортировки
При создании индекса мы можем явно указать порядок сортировки. Например, мы можем создать индекс по дальности полета, в частности, так:
demo=# create index on aircrafts(range desc);В этом случае большие значения будут отображаться в дереве слева, а меньшие — справа. Зачем это нужно, если мы можем пройтись по индексированным значениям в любом направлении?
Цель - многоколоночные индексы. Создадим представление для показа моделей самолетов с условным делением на ближне-, средне- и дальнемагистральные:
demo=# create view aircrafts_v as select model, case when range < 4000 then 1 when range < 10000 then 2 else 3 end as class from aircrafts;demo=# select * from aircrafts_v;model | class ---------------------+------- Boeing 777-300 | 3 Boeing 767-300 | 2 Sukhoi SuperJet-100 | 1 Airbus A320-200 | 2 Airbus A321-200 | 2 Airbus A319-100 | 2 Boeing 737-300 | 2 Cessna 208 Caravan | 1 Bombardier CRJ-200 | 1 (9 rows)
И давайте создадим индекс (используя выражение):
demo=# create index on aircrafts(
(case when range < 4000 then 1 when range < 10000 then 2 else 3 end),
model);Теперь мы можем использовать этот индекс, чтобы отсортировать данные по обоим столбцам в порядке возрастания:
demo=# select class, model from aircrafts_v order by class, model;class | model -------+--------------------- 1 | Bombardier CRJ-200 1 | Cessna 208 Caravan 1 | Sukhoi SuperJet-100 2 | Airbus A319-100 2 | Airbus A320-200 2 | Airbus A321-200 2 | Boeing 737-300 2 | Boeing 767-300 3 | Boeing 777-300 (9 rows)demo=# explain(costs off) select class, model from aircrafts_v order by class, model;QUERY PLAN -------------------------------------------------------- Index Scan using aircrafts_case_model_idx on aircrafts (1 row)
Точно так же мы можем выполнить запрос для сортировки данных в порядке убывания:
demo=# select class, model from aircrafts_v order by class desc, model desc;class | model -------+--------------------- 3 | Boeing 777-300 2 | Boeing 767-300 2 | Boeing 737-300 2 | Airbus A321-200 2 | Airbus A320-200 2 | Airbus A319-100 1 | Sukhoi SuperJet-100 1 | Cessna 208 Caravan 1 | Bombardier CRJ-200 (9 rows)demo=# explain(costs off) select class, model from aircrafts_v order by class desc, model desc;QUERY PLAN ----------------------------------------------------------------- Index Scan BACKWARD using aircrafts_case_model_idx on aircrafts (1 row)
Однако мы не можем использовать этот индекс для получения данных, отсортированных по одному столбцу в порядке убывания и по другому столбцу в порядке возрастания. Это потребует сортировки отдельно:
demo=# explain(costs off) select class, model from aircrafts_v order by class ASC, model DESC;QUERY PLAN ------------------------------------------------- Sort Sort Key: (CASE ... END), aircrafts.model DESC -> Seq Scan on aircrafts (3 rows)
(Обратите внимание, что в крайнем случае планировщик выбрал последовательное сканирование вне зависимости от сделанной ранее настройки «enable_seqscan = off». Это связано с тем, что на самом деле эта настройка не запрещает сканирование таблицы, а лишь задает его астрономическую стоимость — пожалуйста, смотрите план с «расходы».)
Чтобы этот запрос использовал индекс, последний должен быть построен с нужным направлением сортировки:
demo=# create index aircrafts_case_asc_model_desc_idx on aircrafts( (case when range < 4000 then 1 when range < 10000 then 2 else 3 end) ASC, model DESC);demo=# explain(costs off) select class, model from aircrafts_v order by class ASC, model DESC;QUERY PLAN ----------------------------------------------------------------- Index Scan using aircrafts_case_asc_model_desc_idx on aircrafts (1 row)
Порядок столбцов
Еще одна проблема, возникающая при использовании индексов с несколькими столбцами, — это порядок перечисления столбцов в индексе. Для B-дерева этот порядок имеет огромное значение: данные внутри страниц будут сортироваться по первому полю, затем по второму и так далее.
Мы можем представить индекс, который мы построили на интервалах диапазонов и моделях, в символическом виде следующим образом:
На самом деле в таком маленьком индексе точно поместится одна корневая страница. На рисунке он намеренно распределен по нескольким страницам для наглядности.
Из этой диаграммы видно, что поиск по предикатам типа «класс = 3» (поиск только по первому полю) или «класс = 3 и модель = «Боинг 777–300»» (поиск по обоим полям) будет работать эффективно.
Однако поиск по предикату «модель = ‘Boeing 777–300’» будет куда менее эффективным: начиная с корня, мы не можем определить, на какой дочерний узел спускаться, поэтому придется спускаться на все. Это не означает, что такой индекс нельзя использовать — вопрос в его эффективности. Например, если бы у нас было три класса самолетов и очень много моделей в каждом классе, нам пришлось бы просматривать около трети индекса, и это могло быть более эффективно, чем полное сканирование таблицы… или нет.
Однако, если мы создадим такой индекс:
demo=# create index on aircrafts(
model,
(case when range < 4000 then 1 when range < 10000 then 2 else 3 end));порядок полей изменится:
С этим индексом поиск по предикату «модель = ‘Boeing 777–300’» будет работать эффективно, а поиск по предикату «класс = 3» — нет.
НУЛИ
Метод доступа «btree» индексирует значения NULL и поддерживает поиск по условиям IS NULL и IS NOT NULL.
Рассмотрим таблицу рейсов, где встречаются NULL:
demo=# create index on flights(actual_arrival);demo=# explain(costs off) select * from flights where actual_arrival is null;QUERY PLAN ------------------------------------------------------- Bitmap Heap Scan on flights Recheck Cond: (actual_arrival IS NULL) -> Bitmap Index Scan on flights_actual_arrival_idx Index Cond: (actual_arrival IS NULL) (4 rows)
NULL расположены на одном или другом конце листовых узлов в зависимости от того, как был создан индекс (NULLS FIRST или NULLS LAST). Это важно, если запрос включает сортировку: индекс можно использовать, если команда SELECT указывает тот же порядок NULL в своем предложении ORDER BY, что и порядок, указанный для построенного индекса (NULLS FIRST или NULLS LAST).
В следующем примере эти заказы одинаковы, поэтому мы можем использовать индекс:
demo=# explain(costs off) select * from flights order by actual_arrival NULLS LAST;QUERY PLAN -------------------------------------------------------- Index Scan using flights_actual_arrival_idx on flights (1 row)
А здесь эти порядки разные, и оптимизатор выбирает последовательное сканирование с последующей сортировкой:
demo=# explain(costs off) select * from flights order by actual_arrival NULLS FIRST;QUERY PLAN ---------------------------------------- Sort Sort Key: actual_arrival NULLS FIRST -> Seq Scan on flights (3 rows)
Чтобы использовать индекс, он должен быть создан с нулевыми значениями, расположенными в начале:
demo=# create index flights_nulls_first_idx on flights(actual_arrival NULLS FIRST);demo=# explain(costs off) select * from flights order by actual_arrival NULLS FIRST;QUERY PLAN ----------------------------------------------------- Index Scan using flights_nulls_first_idx on flights (1 row)
Подобные проблемы, безусловно, вызваны тем, что значения NULL не поддаются сортировке, то есть результат сравнения для NULL и любого другого значения не определен:
demo=# \pset null NULLdemo=# select null < 42;?column? ---------- NULL (1 row)
Это противоречит концепции B-дерева и не вписывается в общую схему. Однако значения NULL играют настолько важную роль в базах данных, что для них всегда приходится делать исключения.
Поскольку NULL можно индексировать, можно использовать индекс даже без каких-либо условий, наложенных на таблицу (поскольку индекс обязательно содержит информацию обо всех строках таблицы). Это может иметь смысл, если запрос требует упорядочения данных, а индекс обеспечивает необходимый порядок. В этом случае планировщик может выбрать индексный доступ, чтобы сэкономить на отдельной сортировке.
Характеристики
Посмотрим на свойства метода доступа btree (запросы уже предоставлены).
amname | name | pg_indexam_has_property
--------+---------------+-------------------------
btree | can_order | t
btree | can_unique | t
btree | can_multi_col | t
btree | can_exclude | tКак мы видели, B-дерево может упорядочивать данные и поддерживает уникальность — и это единственный метод доступа, предоставляющий нам подобные свойства. Многоколоночные индексы также разрешены, но другие методы доступа (хотя и не все) также могут поддерживать такие индексы. Мы обсудим поддержку ограничения EXCLUDE в следующий раз, и не без причины.
name | pg_index_has_property
---------------+-----------------------
clusterable | t
index_scan | t
bitmap_scan | t
backward_scan | tМетод доступа «btree» поддерживает оба метода получения значений: сканирование индекса, а также сканирование растрового изображения. И как мы могли видеть, метод доступа может проходить по дереву как «вперед», так и «назад».
name | pg_index_column_has_property
--------------------+------------------------------
asc | t
desc | f
nulls_first | f
nulls_last | t
orderable | t
distance_orderable | f
returnable | t
search_array | t
search_nulls | tПервые четыре свойства этого слоя объясняют, как именно упорядочены значения определенного столбца. В этом примере значения сортируются в порядке возрастания («asc»), а значения NULL предоставляются последними («nulls_last»). Но, как мы уже видели, возможны и другие комбинации.
Свойство search_array указывает на поддержку индексом таких выражений:
demo=# explain(costs off) select * from aircrafts where aircraft_code in ('733','763','773');QUERY PLAN ----------------------------------------------------------------- Index Scan using aircrafts_pkey on aircrafts Index Cond: (aircraft_code = ANY ('{733,763,773}'::bpchar[])) (2 rows)
Свойство «returnable» указывает на поддержку сканирования только индекса, что разумно, поскольку строки индекса сами хранят проиндексированные значения (в отличие, например, от хеш-индекса). Здесь имеет смысл сказать несколько слов о покрытии индексов на основе B-tree.
Уникальные индексы с дополнительными строками
Как мы обсуждали ранее, покрывающий индекс — это тот, в котором хранятся все значения, необходимые для запроса, при этом доступ к самой таблице не требуется (почти). Уникальный индекс может специально покрывать.
Но давайте предположим, что мы хотим добавить в уникальный индекс дополнительные столбцы, необходимые для запроса. Значения нового составного ключа теперь могут не быть уникальными, и тогда потребуются два индекса для одних и тех же столбцов: один уникальный (для поддержки ограничения целостности) и другой неуникальный (для использования в качестве покрытия). Это точно неэффективно.
В нашей компании Анастасия Лубенникова @lubennikovaav усовершенствовала метод «btree», чтобы в уникальный индекс можно было включать дополнительные неуникальные столбцы. Мы надеемся, что этот патч будет принят сообществом, чтобы стать частью PostgreSQL, но это произойдет не раньше, чем в версии 10. На данный момент патч доступен в версии Pro Standard 9.5+, и вот как он выглядит как.
На самом деле этот патч был добавлен в PostgreSQL 11.
Рассмотрим таблицу бронирования:
demo=# \d bookingsTable "bookings.bookings" Column | Type | Modifiers --------------+--------------------------+----------- book_ref | character(6) | not null book_date | timestamp with time zone | not null total_amount | numeric(10,2) | not null Indexes: "bookings_pkey" PRIMARY KEY, btree (book_ref) Referenced by: TABLE "tickets" CONSTRAINT "tickets_book_ref_fkey" FOREIGN KEY (book_ref) REFERENCES bookings(book_ref)
В этой таблице первичный ключ (book_ref, код бронирования) предоставляется обычным индексом «btree». Создадим новый уникальный индекс с дополнительным столбцом:
demo=# create unique index bookings_pkey2 on bookings(book_ref) INCLUDE (book_date);Теперь заменяем существующий индекс на новый (в транзакции, чтобы применить все изменения одновременно):
demo=# begin;demo=# alter table bookings drop constraint bookings_pkey cascade;demo=# alter table bookings add primary key using index bookings_pkey2;demo=# alter table tickets add foreign key (book_ref) references bookings (book_ref);demo=# commit;
Вот что мы получаем:
demo=# \d bookingsTable "bookings.bookings" Column | Type | Modifiers --------------+--------------------------+----------- book_ref | character(6) | not null book_date | timestamp with time zone | not null total_amount | numeric(10,2) | not null Indexes: "bookings_pkey2" PRIMARY KEY, btree (book_ref) INCLUDE (book_date) Referenced by: TABLE "tickets" CONSTRAINT "tickets_book_ref_fkey" FOREIGN KEY (book_ref) REFERENCES bookings(book_ref)
Теперь один и тот же индекс работает как уникальный и служит индексом покрытия для этого запроса, например:
demo=# explain(costs off) select book_ref, book_date from bookings where book_ref = '059FC4';QUERY PLAN -------------------------------------------------- Index Only Scan using bookings_pkey2 on bookings Index Cond: (book_ref = '059FC4'::bpchar) (2 rows)
Создание индекса
Общеизвестно, но не менее важно, что для большой таблицы лучше загружать туда данные без индексов, а нужные индексы создавать потом. Это не только быстрее, но и, скорее всего, индекс будет иметь меньший размер.
Дело в том, что создание индекса «btree» использует более эффективный процесс, чем построчная вставка значений в дерево. Грубо говоря, все данные, имеющиеся в таблице, сортируются и создаются конечные страницы этих данных. Затем над этим основанием «надстраиваются» внутренние страницы, пока вся пирамида не сойдется к корню.
Скорость этого процесса зависит от размера доступной оперативной памяти, который ограничен параметром «maintenance_work_mem». Таким образом, увеличение значения параметра может ускорить процесс. Для уникальных индексов выделяется память размером «work_mem» в дополнение к «maintenance_work_mem».
Семантика сравнения
В прошлый раз мы упомянули, что PostgreSQL нужно знать, какие хэш-функции вызывать для значений разных типов, и что эта связь хранится в методе доступа хэш. Точно так же система должна выяснить, как упорядочивать значения. Это необходимо для сортировок, группировок (иногда), объединений слиянием и т.д. PostgreSQL не привязывается к именам операторов (таким как ›, ‹, =), поскольку пользователи могут определять свой собственный тип данных и давать соответствующим операторам разные имена. Семейство операторов, используемое методом доступа btree, вместо этого определяет имена операторов.
Например, эти операторы сравнения используются в семействе операторов «bool_ops»:
postgres=# select amop.amopopr::regoperator as opfamily_operator, amop.amopstrategy from pg_am am, pg_opfamily opf, pg_amop amop where opf.opfmethod = am.oid and amop.amopfamily = opf.oid and am.amname = 'btree' and opf.opfname = 'bool_ops' order by amopstrategy;opfamily_operator | amopstrategy ---------------------+-------------- <(boolean,boolean) | 1 <=(boolean,boolean) | 2 =(boolean,boolean) | 3 >=(boolean,boolean) | 4 >(boolean,boolean) | 5 (5 rows)
Здесь мы видим пять операторов сравнения, но, как уже было сказано, не стоит полагаться на их названия. Чтобы выяснить, какое сравнение выполняет каждый оператор, вводится понятие стратегии. Для описания семантики операторов определены пять стратегий:
- 1 — меньше
- 2 — меньше или равно
- 3 — равно
- 4 — больше или равно
- 5 — больше
Некоторые семейства операторов могут содержать несколько операторов, реализующих одну стратегию. Например, семейство операторов «integer_ops» содержит следующие операторы для стратегии 1:
postgres=# select amop.amopopr::regoperator as opfamily_operator from pg_am am, pg_opfamily opf, pg_amop amop where opf.opfmethod = am.oid and amop.amopfamily = opf.oid and am.amname = 'btree' and opf.opfname = 'integer_ops' and amop.amopstrategy = 1 order by opfamily_operator;opfamily_operator ---------------------- <(integer,bigint) <(smallint,smallint) <(integer,integer) <(bigint,bigint) <(bigint,integer) <(smallint,integer) <(integer,smallint) <(smallint,bigint) <(bigint,smallint) (9 rows)
Благодаря этому оптимизатор может избежать приведения типов при сравнении значений разных типов, содержащихся в одном семействе операторов.
Поддержка индексов для нового типа данных
В документации приведен пример создания нового типа данных для комплексных чисел и класса операторов для сортировки значений этого типа. В этом примере используется язык C, что абсолютно разумно, когда критична скорость. Но ничто не мешает нам использовать чистый SQL для того же эксперимента, чтобы просто попытаться лучше понять семантику сравнения.
Создадим новый составной тип с двумя полями: реальной и мнимой частями.
postgres=# create type complex as (re float, im float);Мы можем создать таблицу с полем нового типа и добавить в таблицу несколько значений:
postgres=# create table numbers(x complex);postgres=# insert into numbers values ((0.0, 10.0)), ((1.0, 3.0)), ((1.0, 1.0));
Теперь возникает вопрос: как упорядочивать комплексные числа, если для них не определено отношение порядка в математическом смысле?
Как оказалось, операторы сравнения уже определены для нас:
postgres=# select * from numbers order by x;x -------- (0,10) (1,1) (1,3) (3 rows)
По умолчанию для составного типа сортировка выполняется покомпонентно: сначала сравниваются поля, затем вторые поля и т. д., примерно так же, как текстовые строки сравниваются посимвольно. Но мы можем определить другой порядок. Например, комплексные числа можно рассматривать как векторы и упорядочивать по модулю (длине), который вычисляется как квадратный корень из суммы квадратов координат (теорема Пифагора). Чтобы определить такой порядок, давайте создадим вспомогательную функцию, которая вычисляет модуль:
postgres=# create function modulus(a complex) returns float as $$
select sqrt(a.re*a.re + a.im*a.im);
$$ immutable language sql;Теперь мы систематически определим функции для всех пяти операторов сравнения, используя эту вспомогательную функцию:
postgres=# create function complex_lt(a complex, b complex) returns boolean as $$ select modulus(a) < modulus(b); $$ immutable language sql;postgres=# create function complex_le(a complex, b complex) returns boolean as $$ select modulus(a) <= modulus(b); $$ immutable language sql;postgres=# create function complex_eq(a complex, b complex) returns boolean as $$ select modulus(a) = modulus(b); $$ immutable language sql;postgres=# create function complex_ge(a complex, b complex) returns boolean as $$ select modulus(a) >= modulus(b); $$ immutable language sql;postgres=# create function complex_gt(a complex, b complex) returns boolean as $$ select modulus(a) > modulus(b); $$ immutable language sql;
И мы создадим соответствующие операторы. Чтобы проиллюстрировать, что их не нужно называть «›», «‹» и так далее, давайте дадим им «странные» имена.
postgres=# create operator #<#(leftarg=complex, rightarg=complex, procedure=complex_lt);postgres=# create operator #<=#(leftarg=complex, rightarg=complex, procedure=complex_le);postgres=# create operator #=#(leftarg=complex, rightarg=complex, procedure=complex_eq);postgres=# create operator #>=#(leftarg=complex, rightarg=complex, procedure=complex_ge);postgres=# create operator #>#(leftarg=complex, rightarg=complex, procedure=complex_gt);
На этом этапе мы можем сравнить числа:
postgres=# select (1.0,1.0)::complex #<# (1.0,3.0)::complex;?column? ---------- t (1 row)
В дополнение к пяти операторам, метод доступа «btree» требует определения еще одной функции (избыточной, но удобной): она должна возвращать -1, 0 или 1, если первое значение меньше, равно или больше второго. один. Эта вспомогательная функция называется поддержкой. Другие методы доступа могут потребовать определения других вспомогательных функций.
postgres=# create function complex_cmp(a complex, b complex) returns integer as $$
select case when modulus(a) < modulus(b) then -1
when modulus(a) > modulus(b) then 1
else 0
end;
$$ language sql;Теперь мы готовы создать класс операторов (и одноименное семейство операторов будет создано автоматически):
postgres=# create operator class complex_ops
default for type complex
using btree as
operator 1 #<#,
operator 2 #<=#,
operator 3 #=#,
operator 4 #>=#,
operator 5 #>#,
function 1 complex_cmp(complex,complex);Теперь сортировка работает как надо:
postgres=# select * from numbers order by x;x -------- (1,1) (1,3) (0,10) (3 rows)
И это обязательно будет поддерживаться индексом «btree».
Для полноты картины вы можете получить функции поддержки, используя этот запрос:
postgres=# select amp.amprocnum, amp.amproc, amp.amproclefttype::regtype, amp.amprocrighttype::regtype from pg_opfamily opf, pg_am am, pg_amproc amp where opf.opfname = 'complex_ops' and opf.opfmethod = am.oid and am.amname = 'btree' and amp.amprocfamily = opf.oid;amprocnum | amproc | amproclefttype | amprocrighttype -----------+-------------+----------------+----------------- 1 | complex_cmp | complex | complex (1 row)
Внутренности
Мы можем изучить внутреннюю структуру B-дерева, используя расширение «pageinspect».
demo=# create extension pageinspect;Метастраница индекса:
demo=# select * from bt_metap('ticket_flights_pkey');magic | version | root | level | fastroot | fastlevel --------+---------+------+-------+----------+----------- 340322 | 2 | 164 | 2 | 164 | 2 (1 row)
Самое интересное здесь — это уровень индекса: для индекса по двум столбцам для таблицы с миллионом строк требуется всего 2 уровня (не считая корня).
Статистическая информация по блоку 164 (корень):
demo=# select type, live_items, dead_items, avg_item_size, page_size, free_size from bt_page_stats('ticket_flights_pkey',164);type | live_items | dead_items | avg_item_size | page_size | free_size ------+------------+------------+---------------+-----------+----------- r | 33 | 0 | 31 | 8192 | 6984 (1 row)
И данные в блоке (поле «данные», которое здесь принесено в жертву ширине экрана, содержит значение ключа индексации в бинарном представлении):
demo=# select itemoffset, ctid, itemlen, left(data,56) as data from bt_page_items('ticket_flights_pkey',164) limit 5;itemoffset | ctid | itemlen | data ------------+---------+---------+---------------------------------------------------------- 1 | (3,1) | 8 | 2 | (163,1) | 32 | 1d 30 30 30 35 34 33 32 33 30 35 37 37 31 00 00 ff 5f 00 3 | (323,1) | 32 | 1d 30 30 30 35 34 33 32 34 32 33 36 36 32 00 00 4f 78 00 4 | (482,1) | 32 | 1d 30 30 30 35 34 33 32 35 33 30 38 39 33 00 00 4d 1e 00 5 | (641,1) | 32 | 1d 30 30 30 35 34 33 32 36 35 35 37 38 35 00 00 2b 09 00 (5 rows)
Первый элемент относится к методам и определяет верхнюю границу всех элементов в блоке (деталь реализации, которую мы не обсуждали), а сами данные начинаются со второго элемента. Понятно, что крайний левый дочерний узел — это блок 163, за которым следует блок 323 и так далее. Их, в свою очередь, можно исследовать с помощью тех же функций.
Теперь, по доброй традиции, имеет смысл ознакомиться с документацией, README и исходным кодом.
Еще одно потенциально полезное расширение — amcheck, которое будет включено в PostgreSQL 10, а для более ранних версий его можно получить на github. Это расширение проверяет логическую согласованность данных в B-деревьях и позволяет нам заранее обнаруживать ошибки.
Это правда, «amcheck» является частью PostgreSQL, начиная с версии 10.
