# Занятие 10: Расширяемость / Классы операторов > Исходная страница в нативном Markdown: Расширяемость / Классы операторов --- Индекс LLMS: [llms.txt](/ru/llms.txt) --- > [!NOTE] > Эта страница извлечена из официального PDF в нативный Markdown. Текст слайдов, код и комментарии сохранены в порядке чтения; исходные PDF и HTML остаются эталоном макета. > **HTML source:** [dev2_10_ext_opclasses.html](https://edu.postgrespro.ru/16/dev2-16/dev2_10_ext_opclasses.html) > **Archive:** [DEV2-handouts-16.zip](https://edu.postgrespro.ru/16/DEV2-handouts-16.zip) > **Страниц PDF:** 27 ## Page 1: Расширяемость / Классы операторов {#source-page-001} ### Авторские права © Postgres Professional, 2017–2024 Авторы: Егор Рогов, Павел Лузанов, Илья Баштанов, Игорь Гнатюк Фото: Олег Бартунов (монастырь Пху и пик Бхрикути, Непал) ### Использование материалов курса Некоммерческое использование материалов курса (презентации, демонстрации) разрешается без ограничений. Коммерческое использование возможно только с письменного разрешения компании Postgres Professional. Запрещается внесение изменений в материалы курса. ### Обратная связь Отзывы, замечания и предложения направляйте по адресу: edu@postgrespro.ru ### Отказ от ответственности Компания Postgres Professional не несет никакой ответственности за любые повреждения и убытки, включая потерю дохода, нанесенные прямым или непрямым, специальным или случайным использованием материалов курса. Компания Postgres Professional не предоставляет каких-либо гарантий на материалы курса. Материалы курса предоставляются на основе принципа «как есть» и компания Postgres Professional не обязана предоставлять сопровождение, поддержку, обновления, расширения и изменения. ## Page 2: Темы {#source-page-002} - Методы доступа (типы индексов) - Классы и семейства операторов - Метод доступа btree и создание класса операторов для него - Идея метода доступа gist и примеры его использования ## Page 3: Методы доступа {#source-page-003} **Определяют способ получения данных** - Табличные методы доступа — организация данных и чтение всей таблицы - Индексные методы доступа (типы индексов) — быстрый доступ к небольшой части данных - алгоритмы, связанные с поисковой структурой данных - эффективная одновременная работа - страничная организация данных - журналирование операций ### Комментарии преподавателя Методы доступа определяют способ получения данных. Их можно разделить на табличные и индексные методы. Табличный метод определяет организацию данных в таблице и работает, когда надо прочитать все данные (Seq Scan). В PostgreSQL существует единственный табличный метод heap, и других готовых методов (таких, например, как колоночное хранилище) еще нет, но они должны появиться в будущем. Индексный метод доступа работает, когда надо быстро получить часть данных (обычно небольшую) с помощью индекса. Индексный метод можно рассматривать как каркас, который реализует основные алгоритмы для работы с индексной структурой данных, а также берет на себя заботу о низкоуровневых деталях, таких как: ● эффективная конкурентная работа с индексной структурой (в том числе стратегия блокирования); ● страничная организация данных индекса; ● журналирование операций над индексом в WAL. ## Page 4: Методы доступа {#source-page-004} ```sql => CREATE DATABASE ext_opclasses; ``` ```sql CREATE DATABASE ``` ```sql => \c ext_opclasses ``` ```text You are now connected to database "ext_opclasses" as user "student". ``` В версии 16 имеется единственный встроенный табличный метод доступа: ```sql => SELECT amname FROM pg_am WHERE amtype = 't'; ``` ```text amname -------- heap (1 row) ``` Зато много различных индексных методов доступа: ```sql => SELECT amname FROM pg_am WHERE amtype = 'i'; ``` ```text amname -------- btree hash gist gin spgist brin (6 rows) ``` С btree знакомы все — это «обычный» метод доступа на основе B-дерева, который используется по умолчанию и покрывает большинство потребностей. Остальные методы доступа также очень полезны, но в специальных ситуациях. Некоторые из них мы рассмотрим позже. Для получения информации мы делали запросы к таблицам системного каталога, однако в арсенале psql есть удобная команда, позволяющая получить информацию о методах доступа, классах и семействах операторов, ей дальше мы и будем пользоваться: ```text => \dA ``` ```text List of access methods Name | Type --------+------- brin | Index btree | Index gin | Index gist | Index hash | Index heap | Table spgist | Index (7 rows) ``` ## Page 5: Классы операторов {#source-page-005} ![Source slide page 5: Классы операторов](images/page-005.png){#source-figure-005 caption="Source slide page 5: Классы операторов"} **Набор операторов и вспомогательных функций, который используется методом доступа для работы с конкретным типом данных** ### Комментарии преподавателя Дальше мы будем говорить не о табличном, а об индексном доступе. Итак, с одной стороны есть индексный метод доступа (например, btree), а с другой — конкретные типы данных (такие, как integer, text и т. п.). Чтобы связать метод доступа с типами данных, используются классы операторов. Класс операторов состоит из набора операторов (и, при необходимости, вспомогательных функций), который реализует API индексного метода доступа. Важно, что часть логики индексирования находится в методе доступа, а часть — в классе операторов. Поэтому недостаточно понять только устройство метода доступа; надо учитывать и то, какой используется класс операторов. Для B-деревьев это не так очевидно, поскольку на долю класса операторов приходится совсем немного. Но в других методах доступа разные классы операторов могут радикально менять логику. Заметим также, что для одного и того же метода доступа и одного и того же типа данных может быть определено несколько классов операторов. В этом случае пользователь может выбирать то поведение, которое требуется. ## Page 6: Классы операторов {#source-page-006} Посмотрим, какие классы операторов определены для B-дерева и для разных типов данных. Для целых чисел: ```text => \dAc btree (smallint|integer|bigint) ``` ```text List of operator classes AM | Input type | Storage type | Operator class | Default? -------+------------+--------------+----------------+---------- btree | bigint | | int8_ops | yes btree | integer | | int4_ops | yes btree | smallint | | int2_ops | yes (3 rows) ``` Для удобства такие «похожие по смыслу» классы операторов объединяются в семейства операторов: ```text => \dAf btree (smallint|integer|bigint) ``` ```text List of operator families AM | Operator family | Applicable types -------+-----------------+--------------------------- btree | integer_ops | smallint, integer, bigint (1 row) ``` Семейства операторов позволяют планировщику работать с выражениями разных (но «похожих») типов, даже если они не приведены к одному общему. Вот классы операторов для типа text (если для одного типа есть несколько классов операторов, то один будет помечен для использования по умолчанию): ```text => \dAc btree text ``` ```text List of operator classes AM | Input type | Storage type | Operator class | Default? -------+------------+--------------+---------------------+---------- btree | text | | text_ops | yes btree | text | | text_pattern_ops | no btree | text | | varchar_ops | no btree | text | | varchar_pattern_ops | no (4 rows) ``` Классы операторов pattern\_ops отличаются от обычных тем, что сравнивают строки посимвольно, игнорируя правила сортировки (collation). А так можно посмотреть, какие операторы включены в конкретный класс операторов: ```text => \dAo btree bool_ops ``` ```text List of operators of operator families AM | Operator family | Operator | Strategy | Purpose -------+-----------------+---------------------+----------+--------- btree | bool_ops | <(boolean,boolean) | 1 | search btree | bool_ops | <=(boolean,boolean) | 2 | search btree | bool_ops | =(boolean,boolean) | 3 | search btree | bool_ops | >=(boolean,boolean) | 4 | search btree | bool_ops | >(boolean,boolean) | 5 | search (5 rows) ``` Метод доступа — это тип индекса, а собственно индекс — это конкретная структура, созданная на основе метода доступа, в которой для каждого столбца используется свой класс операторов. Пусть имеется какая-нибудь таблица: ```sql => CREATE TABLE t( id integer GENERATED ALWAYS AS IDENTITY, s text ); ``` ```sql CREATE TABLE ``` ```sql => INSERT INTO t(s) VALUES ('foo'), ('bar'), ('xy'), ('z'); ``` ## Page 7: Page 7 {#source-page-007} ```sql INSERT 0 4 ``` Привычная команда создания индекса выглядит так: ```sql CREATE INDEX ON t(id, s); ``` Но это просто сокращение для: ```sql => CREATE INDEX ON t USING btree -- метод доступа ( id int4_ops, -- класс операторов для integer s text_ops -- класс операторов по умолчанию для text ); ``` ```sql CREATE INDEX ``` ## Page 8: Метод доступа btree {#source-page-008} ![Source slide page 8: Метод доступа btree](images/page-008.png){#source-figure-008 caption="Source slide page 8: Метод доступа btree"} **Сбалансированное дерево, значения упорядочены** - метод применим только для сортируемых типов данных - API метода доступа определяет порядок сортировки ### Комментарии преподавателя Рассмотрим теперь несколько конкретных методов доступа, и начнем с B-деревьев. Эта структура данных представляет собой дерево (сбалансированное по высоте), которое содержит упорядоченные данные. В каждом узле хранится информация о том, какие диапазоны значений расположены в дочерних узлах. Это позволяет находить искомое значение, спускаясь от вершины дерева к листьям, каждый раз однозначно выбирая подходящий диапазон. Например, для поиска буквы «H» (на рисунке) мы начинаем с корня. Поскольку «A» <= «H» < «I», мы спускаемся в первый дочерний узел, и так далее. Итак, этот метод доступа применим только для сортируемых данных (к которым относятся большинство «обычных» типов данных). От класса операторов требуется только определить, как именно упорядочиваются значения конкретного типа. ## Page 9: Класс операторов для B-дерева {#source-page-009} Класс операторов для B-дерева определяет, как именно будут сортироваться значения в индексе. Для этого он включает пять операторов сравнения, как мы уже видели на примере bool\_ops. Определим перечислимый тип для единиц измерения информации: ```sql => CREATE TYPE capacity_units AS ENUM ( 'B', 'kB', 'MB', 'GB', 'TB', 'PB' ); ``` ```sql CREATE TYPE ``` И объявим составной тип данных для представления объема информации: ```sql => CREATE TYPE capacity AS ( amount integer, unit capacity_units ); ``` ```sql CREATE TYPE ``` Используем новый тип в таблице, которую заполним случайными значениями. ```sql => CREATE TABLE test ( cap capacity ); ``` ```sql CREATE TABLE ``` ```sql => INSERT INTO test SELECT ( (random()*1023)::integer, u.unit )::capacity FROM generate_series(1,100), unnest(enum_range(NULL::capacity_units)) AS u(unit); ``` ```sql INSERT 0 600 ``` По умолчанию значения составного типа сортируются в лексикографическом порядке, но этот порядок не совпадает с естественным порядком: ```sql => SELECT * FROM test ORDER BY cap LIMIT 10; ``` ```text cap --------- (1,kB) (1,MB) (1,PB) (2,GB) (2,PB) (6,PB) (7,GB) (11,PB) (14,MB) (15,MB) (10 rows) ``` Чтобы исправить сортировку, создадим класс операторов. Начнем с функции, которая пересчитает объем в байты. ```sql => CREATE FUNCTION capacity_to_bytes(a capacity) RETURNS numeric LANGUAGE sql STRICT IMMUTABLE RETURN a.amount::numeric * 1024::numeric ^ ( array_position(enum_range(a.unit), a.unit)-1 ); ``` ```sql CREATE FUNCTION ``` Помимо операторов сравнения нам понадобится еще одна вспомогательная функция — тоже для сравнения. Она должна возвращать: −1, если первый аргумент меньше второго; 0, если аргументы равны; 1, если первый аргумент больше второго. ## Page 10: Page 10 {#source-page-010} ```sql => CREATE FUNCTION capacity_cmp(a capacity, b capacity) RETURNS integer LANGUAGE sql STRICT IMMUTABLE RETURN CASE WHEN capacity_to_bytes(a) < capacity_to_bytes(b) THEN -1 WHEN capacity_to_bytes(a) > capacity_to_bytes(b) THEN 1 ELSE 0 END; ``` ```sql CREATE FUNCTION ``` С помощью этой функции мы определим пять операторов сравнения (и функции для них). Начнем с «меньше»: ```sql => CREATE FUNCTION capacity_lt(a capacity, b capacity) RETURNS boolean LANGUAGE sql IMMUTABLE STRICT RETURN capacity_cmp(a,b) < 0; ``` ```sql CREATE FUNCTION ``` ```sql => CREATE OPERATOR <( LEFTARG = capacity, RIGHTARG = capacity, FUNCTION = capacity_lt ); ``` ```sql CREATE OPERATOR ``` И аналогично остальные четыре. ```sql => CREATE FUNCTION capacity_le(a capacity, b capacity) RETURNS boolean LANGUAGE sql IMMUTABLE STRICT RETURN capacity_cmp(a,b) <= 0; ``` ```sql CREATE FUNCTION ``` ```sql => CREATE OPERATOR <=( LEFTARG = capacity, RIGHTARG = capacity, FUNCTION = capacity_le ); ``` ```sql CREATE OPERATOR ``` ```sql => CREATE FUNCTION capacity_eq(a capacity, b capacity) RETURNS boolean LANGUAGE sql IMMUTABLE STRICT RETURN capacity_cmp(a,b) = 0; ``` ```sql CREATE FUNCTION ``` ```sql => CREATE OPERATOR =( LEFTARG = capacity, RIGHTARG = capacity, FUNCTION = capacity_eq ); ``` ```sql CREATE OPERATOR ``` ```sql => CREATE FUNCTION capacity_ge(a capacity, b capacity) RETURNS boolean LANGUAGE sql IMMUTABLE STRICT RETURN capacity_cmp(a,b) >= 0; ``` ```sql CREATE FUNCTION ``` ```sql => CREATE OPERATOR >=( LEFTARG = capacity, RIGHTARG = capacity, FUNCTION = capacity_ge ); ``` ```sql CREATE OPERATOR ``` ```sql => CREATE FUNCTION capacity_gt(a capacity, b capacity) RETURNS boolean LANGUAGE sql IMMUTABLE STRICT RETURN capacity_cmp(a,b) > 0; ``` ```sql CREATE FUNCTION ``` ```sql => CREATE OPERATOR >( LEFTARG = capacity, RIGHTARG = capacity, FUNCTION = capacity_gt ); ``` ```sql CREATE OPERATOR ``` Готово. Мы уже можем правильно сравнивать объемы: ## Page 11: Page 11 {#source-page-011} ```sql => SELECT (1,'MB')::capacity > (512, 'kB')::capacity; ``` ```text ?column? ---------- t (1 row) ``` Чтобы значения были правильно упорядочены при выборке, нам осталось создать класс операторов. За каждым оператором закреплен собственный номер (в случае btree: 1 — «меньше» и т. д.), поэтому имена операторов могут быть любыми. ```sql => CREATE OPERATOR CLASS capacity_ops DEFAULT FOR TYPE capacity USING btree AS OPERATOR 1 <, OPERATOR 2 <=, OPERATOR 3 =, OPERATOR 4 >=, OPERATOR 5 >, FUNCTION 1 capacity_cmp(capacity,capacity); ``` ```sql CREATE OPERATOR CLASS ``` ```sql => SELECT * FROM test ORDER BY cap LIMIT 10; ``` ```text cap -------- (19,B) (25,B) (29,B) (39,B) (61,B) (69,B) (69,B) (89,B) (89,B) (92,B) (10 rows) ``` Теперь значения отсортированы правильно. Наш класс операторов будет использоваться по умолчанию при создании индекса: ```sql => CREATE INDEX ON test(cap); ``` ```sql CREATE INDEX ``` Любой индекс в PostgreSQL может использоваться только для выражений вида: ```text <индексированное-поле> <оператор> <выражение> ``` Причем оператор должен входить в соответствующий класс операторов. Будет ли использоваться созданный индекс в таком запросе? ```text => SET enable_seqscan = off; -- временно отключим последовательное сканирование ``` ```text SET ``` ```sql => EXPLAIN (costs off) SELECT * FROM test WHERE cap < (100,'B')::capacity; ``` ```text QUERY PLAN -------------------------------------------------------- Bitmap Heap Scan on test Filter: (capacity_cmp(cap, '(100,B)'::capacity) < 0) -> Bitmap Index Scan on test_cap_idx (3 rows) ``` Да, поскольку: поле test.cap проиндексировано с помощью метода доступа btree и класса операторов capacity\_ops; оператор < входит в класс операторов capacity\_ops. Поэтому и при доступе с помощью индекса значения будут возвращаться в правильном порядке: ```sql => SELECT * FROM test WHERE cap < (100,'B')::capacity ORDER BY cap; ``` ## Page 12: Page 12 {#source-page-012} ```text cap -------- (19,B) (25,B) (29,B) (39,B) (61,B) (69,B) (69,B) (89,B) (89,B) (92,B) (10 rows) ``` ## Page 13: Метод доступа GiST {#source-page-013} ![Source slide page 13: Метод доступа GiST](images/page-013.png){#source-figure-013 caption="Source slide page 13: Метод доступа GiST"} ### Комментарии преподавателя Однако не все типы данных сортируемы. Например, не имеют естественной упорядоченности геометрические фигуры (точки, прямоугольники и т. п.), диапазоны, массивы и т. п. Конечно, для таких типов данных можно определить операции сравнения, но практической пользы от них будет немного. Важнее уметь использовать индексы, например, для поиска точек, входящих в заданную область или в массив, т. е. для операторов, отличных от «больше», «меньше» и т. п. B-дерево здесь не годится, но идею индексирования с помощью сбалансированного дерева можно обобщить. При поиске по дереву в каждом узле принимается решение, в каком поддереве (в общем случае — в нескольких поддеревьях) продолжить поиск. Для этого каждому поддереву ставится в соответствие условие (предикат), которому удовлетворяют все находящиеся в нем данные. Класс операторов для GiST (generalized search tree — обобщенное дерево поиска) определяет, как выглядит предикат, и еще многие детали, необходимые для эффективной работы. Идею работы GiST-индексов рассмотрим на примере точек на плоскости. Плоскость разбивается на несколько прямоугольников, которые в сумме покрывают все индексируемые точки. Эти прямоугольники составляют верхний уровень дерева. Как видно на рисунке, прямоугольники могут пересекаться (хотя это и уменьшает эффективность поиска). ## Page 14: Метод доступа GiST {#source-page-014} ![Source slide page 14: Метод доступа GiST](images/page-014.png){#source-figure-014 caption="Source slide page 14: Метод доступа GiST"} ### Комментарии преподавателя На следующем уровне дерева каждый из больших прямоугольников распадается на прямоугольники меньшего размера. ## Page 15: Метод доступа GiST {#source-page-015} ![Source slide page 15: Метод доступа GiST](images/page-015.png){#source-figure-015 caption="Source slide page 15: Метод доступа GiST"} ### Комментарии преподавателя На последнем уровне дерева каждый ограничивающий прямоугольник будет содержать столько точек, сколько помещается на одну индексную страницу. Общее условие разбиения таково: прямоугольник родительской вершины охватывает все прямоугольники соответствующего поддерева. Это позволяет, например, быстро находить точки, лежащие внутри определенной области: 1) находим прямоугольники, пересекающиеся с заданной областью, на верхнем уровне индекса; 2) спускаемся в выбранные поддеревья и повторяем поиск в них. Такой алгоритм индексирования называется R-деревом. ## Page 16: Метод доступа GiST {#source-page-016} Какие именно операторы поддерживает GiST-индекс, существенно зависит от класса операторов. Информацию можно получить как из документации, так и из системного каталога. Возьмем, например, тип данных point (точки). Доступный класс операторов: ```text => \dAc gist point ``` ```text List of operator classes AM | Input type | Storage type | Operator class | Default? ------+------------+--------------+----------------+---------- gist | point | box | point_ops | yes (1 row) ``` Операторы в этом классе: ```text => \dAo gist point_ops ``` ```text List of operators of operator families AM | Operator family | Operator | Strategy | Purpose ------+-----------------+-------------------+----------+---------- gist | point_ops | <<(point,point) | 1 | search gist | point_ops | >>(point,point) | 5 | search gist | point_ops | ~=(point,point) | 6 | search gist | point_ops | <<|(point,point) | 10 | search gist | point_ops | |>>(point,point) | 11 | search gist | point_ops | <->(point,point) | 15 | ordering gist | point_ops | <^(point,point) | 29 | search gist | point_ops | >^(point,point) | 30 | search gist | point_ops | <@(point,box) | 28 | search gist | point_ops | <@(point,circle) | 68 | search gist | point_ops | <@(point,polygon) | 48 | search (11 rows) ``` В частности, оператор <@ проверяет, принадлежит ли точка одной из геометрических фигур. Создадим таблицу со случайными точками: ```sql => CREATE TABLE points ( p point ); ``` ```sql CREATE TABLE ``` ```sql => INSERT INTO points(p) SELECT point(1 - random()*2, 1 - random()*2) FROM generate_series(1,10_000); ``` ```sql INSERT 0 10000 ``` Сколько точек расположено в круге радиуса 0.1? ```sql => SELECT count(*) FROM points WHERE p <@ circle '((0,0),0.1)'; ``` ```text count ------- 74 (1 row) ``` Как выполняется такой запрос? ```sql => EXPLAIN (costs off) SELECT * FROM points WHERE p <@ circle '((0,0),0.1)'; ``` ```text QUERY PLAN ---------------------------------------- Seq Scan on points Filter: (p <@ '<(0,0),0.1>'::circle) (2 rows) ``` Полным перебором всей таблицы. Создание GiST-индекса позволит ускорить эту операцию. Класс операторов можно не указывать, он один. ## Page 17: Page 17 {#source-page-017} ```sql => CREATE INDEX ON points USING gist(p); ``` ```sql CREATE INDEX ``` ```sql => EXPLAIN (costs off) SELECT * FROM points WHERE p <@ circle '((0,0),0.1)'; ``` ```text QUERY PLAN -------------------------------------------------- Bitmap Heap Scan on points Recheck Cond: (p <@ '<(0,0),0.1>'::circle) -> Bitmap Index Scan on points_p_idx Index Cond: (p <@ '<(0,0),0.1>'::circle) (4 rows) ``` Еще один интересный оператор <-> вычисляет расстояние от одной точки до другой. Его можно использовать, чтобы найти точки, ближайшие к данной (так называемый поиск ближайших соседей, k-NN search): ```sql => SELECT * FROM points ORDER BY p <-> point '(0,0)' LIMIT 5; ``` ```text p ----------------------------------------------- (-0.008379708221054827,-0.004909517844374989) (0.0105701404343983,-0.0032920801688396395) (0.010698253417356085,0.009047952697135209) (0.006528645163156543,-0.01529100178511733) (-0.010100171908385303,-0.017978884746949753) (5 rows) ``` Эта операция (весьма непростая, если реализовывать ее в приложении) также ускоряется индексом: ```sql => EXPLAIN (costs off) SELECT * FROM points ORDER BY p <-> point '(0,0)' LIMIT 5; ``` ```text QUERY PLAN ---------------------------------------------------- Limit -> Index Only Scan using points_p_idx on points Order By: (p <-> '(0,0)'::point) (3 rows) ``` GiST-индекс можно построить и для столбца диапазонного типа: ```text => \dAo gist range_ops ``` ```text List of operators of operator families AM | Operator family | Operator | Strategy | Purpose ------+-----------------+-----------------------------+----------+--------- gist | range_ops | <<(anyrange,anyrange) | 1 | search gist | range_ops | &<(anyrange,anyrange) | 2 | search gist | range_ops | &&(anyrange,anyrange) | 3 | search gist | range_ops | &>(anyrange,anyrange) | 4 | search gist | range_ops | >>(anyrange,anyrange) | 5 | search gist | range_ops | -|-(anyrange,anyrange) | 6 | search gist | range_ops | @>(anyrange,anyrange) | 7 | search gist | range_ops | <@(anyrange,anyrange) | 8 | search gist | range_ops | =(anyrange,anyrange) | 18 | search gist | range_ops | @>(anyrange,anyelement) | 16 | search gist | range_ops | <<(anyrange,anymultirange) | 1 | search gist | range_ops | &<(anyrange,anymultirange) | 2 | search gist | range_ops | &&(anyrange,anymultirange) | 3 | search gist | range_ops | &>(anyrange,anymultirange) | 4 | search gist | range_ops | >>(anyrange,anymultirange) | 5 | search gist | range_ops | -|-(anyrange,anymultirange) | 6 | search gist | range_ops | @>(anyrange,anymultirange) | 7 | search gist | range_ops | <@(anyrange,anymultirange) | 8 | search (18 rows) ``` Здесь мы видим другой набор операторов. Одно из применений GiST-индекса — поддержка ограничений целостности типа EXCLUDE (ограничения исключения). Возьмем классический пример бронирования аудиторий: ```sql => CREATE TABLE booking ( during tstzrange NOT NULL ); ``` ## Page 18: Page 18 {#source-page-018} ```sql CREATE TABLE ``` Ограничение целостности можно сформулировать так: нельзя, чтобы в разных строках таблицы были два пересекающихся (оператор &&) диапазона. Такое ограничение можно задать декларативно на уровне базы данных: ```sql => ALTER TABLE booking ADD CONSTRAINT no_intersect EXCLUDE USING gist(during WITH &&); ``` ```sql ALTER TABLE ``` Проверим: ```sql => INSERT INTO booking(during) VALUES ('[today 12:00,today 14:00)'::tstzrange); ``` ```sql INSERT 0 1 ``` ```sql => INSERT INTO booking(during) VALUES ('[today 13:00,today 16:00)'::tstzrange); ``` ```text ERROR: conflicting key value violates exclusion constraint "no_intersect" DETAIL: Key (during)=(["2026-04-10 13:00:00+03","2026-04-10 16:00:00+03")) conflicts with existing key (during)=(["2026-04-10 12:00:00+03","2026-04-10 14:00:00+03")). ``` Частая ситуация — наличие дополнительного условия в таком ограничении целостности. Добавим номер аудитории: ```sql => ALTER TABLE booking ADD room integer NOT NULL DEFAULT 1; ``` ```sql ALTER TABLE ``` Но мы не сможем добавить этот столбец в ограничение целостности, поскольку класс операторов для метода gist и типа integer не определен. ```sql => ALTER TABLE booking DROP CONSTRAINT no_intersect; ``` ```sql ALTER TABLE ``` ```sql => ALTER TABLE booking ADD CONSTRAINT no_intersect EXCLUDE USING gist(during WITH &&, room WITH =); ``` ```text ERROR: data type integer has no default operator class for access method "gist" HINT: You must specify an operator class for the index or define a default operator class for the data type. ``` В этом случае поможет расширение btree\_gist, которое добавляет классы операторов для типов данных, которые обычно индексируются с помощью B-деревьев: ```sql => CREATE EXTENSION btree_gist; ``` ```sql CREATE EXTENSION ``` ```sql => ALTER TABLE booking ADD CONSTRAINT no_intersect EXCLUDE USING gist(during WITH &&, room WITH =); ``` ```sql ALTER TABLE ``` Теперь разные аудитории можно бронировать на одно время: ```sql => INSERT INTO booking(room, during) VALUES (2, '[today 13:00,today 16:00)'::tstzrange); ``` ```sql INSERT 0 1 ``` Но одну и ту же — нельзя: ```sql => INSERT INTO booking(room, during) VALUES (1, '[today 13:00,today 16:00)'::tstzrange); ``` ```text ERROR: conflicting key value violates exclusion constraint "no_intersect" DETAIL: Key (during, room)=(["2026-04-10 13:00:00+03","2026-04-10 16:00:00+03"), 1) conflicts with existing key (during, room)=(["2026-04-10 12:00:00+03","2026-04-10 14:00:00+03"), 1). ``` ## Page 19: Итоги {#source-page-019} **PostgreSQL предоставляет разнообразную индексную поддержку любых типов данных, включая пользовательские** - Методы доступа — каркас индексирования, реализующий основной алгоритм и низкоуровневые детали - btree, hash, gist, sp-gist, gin, brin... - Классы операторов связывают метод с типами данных ### Комментарии преподавателя В этой теме рассматриваются лишь самые основные понятия, связанные с индексной поддержкой. Заинтересованным в подробностях рекомендуем внимательно ознакомиться с разделами документации, ссылки на которые приведены в комментариях к слайдам, а также с главами 4 и 5 книги ## Page 20: Практика {#source-page-020} 1. Добавьте в таблицу retail\_prices ограничение целостности, не позволяющее создать пересекающиеся диапазоны действия цен для одной книги. Проверьте план выполнения запроса для поиска актуальной цены (get\_retail\_price). Использует ли он индекс, созданный для поддержки ограничения целостности? 2. Сортировка книг в приложении по формату издания работает неверно, поскольку значения типа для формата издания упорядочиваются лексикографически. Сделайте так, чтобы значения упорядочивались по площади книжной страницы и проверьте, что сортировка в приложении исправилась. ### Комментарии преподавателя 1. Пример похожего ограничения целостности приводился в демонстрации. Если индекс не будет использоваться запросом из функции get\_retail\_price, дело может быть в том, что в таблице retail\_prices слишком мало строк и полное сканирование оказывается выгоднее. Чтобы проверить применимость индекса, вы можете либо добавить больше строк в таблицу, либо временно запретить использование полного сканирования: SET enable\_seqscan = off; 2. Создайте класс операторов для метода доступа btree и типа данных book\_format, как было показано в демонстрации. ## Page 21: 1. Ограничение целостности для retail_prices {#source-page-021} Добавим ограничение целостности в таблицу: ```sql => CREATE EXTENSION btree_gist; ``` ```sql CREATE EXTENSION ``` ```sql => ALTER TABLE retail_prices ADD EXCLUDE USING gist(book_id WITH =, effective WITH &&); ``` ```sql ALTER TABLE ``` Такое ограничение гарантирует, что данные не будет повреждены, даже если в коде функции set\_retail\_price будет допущена ошибка. В функции get\_retail\_price используется запрос следующего вида: ```sql => EXPLAIN (costs off) SELECT rp.price FROM retail_prices rp WHERE rp.book_id = 1 AND rp.effective @> current_timestamp; ``` ```text QUERY PLAN ---------------------------------------------------------------- Seq Scan on retail_prices rp Filter: ((book_id = 1) AND (effective @> CURRENT_TIMESTAMP)) (2 rows) ``` Как видно из плана, таблица по-прежнему перебирается полностью. Но планировщик будет использовать созданный индекс, как только это окажется выгодным: ```text => BEGIN; ``` ```text BEGIN ``` ```sql => WITH s AS ( SELECT empapi.set_retail_price( b.book_id, 100.00, current_timestamp ), empapi.set_retail_price( b.book_id, 200.00, current_timestamp + interval '1 day' ), empapi.set_retail_price( b.book_id, 300.00, current_timestamp + interval '2 days' ) FROM books b ) SELECT count(*) FROM s; ``` ```text count ------- 100 (1 row) ``` ```sql => EXPLAIN (costs off) SELECT rp.price FROM retail_prices rp WHERE rp.book_id = 1 AND rp.effective @> current_timestamp; ``` ```text QUERY PLAN ----------------------------------------------------------------- Bitmap Heap Scan on retail_prices rp Recheck Cond: (effective @> CURRENT_TIMESTAMP) Filter: (book_id = 1) -> Bitmap Index Scan on retail_prices_book_id_effective_excl Index Cond: (effective @> CURRENT_TIMESTAMP) (5 rows) ``` ```text => ROLLBACK; ``` ```text ROLLBACK ``` ## Page 22: 2. Упорядочивание для форматов издания {#source-page-022} Создадим класс операторов, как было показано в демонстрации. ```sql => CREATE FUNCTION book_format_area(f book_format) RETURNS numeric LANGUAGE sql STRICT IMMUTABLE RETURN f.width::numeric * f.height::numeric / f.parts::numeric; ``` ```sql CREATE FUNCTION ``` ```sql => CREATE FUNCTION book_format_cmp(a book_format, b book_format) RETURNS integer LANGUAGE sql STRICT IMMUTABLE RETURN CASE WHEN book_format_area(a) < book_format_area(b) THEN -1 WHEN book_format_area(a) > book_format_area(b) THEN 1 ELSE 0 END; ``` ```sql CREATE FUNCTION ``` ```sql => CREATE FUNCTION book_format_lt(a book_format, b book_format) RETURNS boolean LANGUAGE sql IMMUTABLE STRICT RETURN book_format_cmp(a,b) < 0; ``` ```sql CREATE FUNCTION ``` ```sql => CREATE OPERATOR <( LEFTARG = book_format, RIGHTARG = book_format, FUNCTION = book_format_lt ); ``` ```sql CREATE OPERATOR ``` ```sql => CREATE FUNCTION book_format_le(a book_format, b book_format) RETURNS boolean LANGUAGE sql IMMUTABLE STRICT RETURN book_format_cmp(a,b) <= 0; ``` ```sql CREATE FUNCTION ``` ```sql => CREATE OPERATOR <=( LEFTARG = book_format, RIGHTARG = book_format, FUNCTION = book_format_le ); ``` ```sql CREATE OPERATOR ``` ```sql => CREATE FUNCTION book_format_eq(a book_format, b book_format) RETURNS boolean LANGUAGE sql IMMUTABLE STRICT RETURN book_format_cmp(a,b) = 0; ``` ```sql CREATE FUNCTION ``` ```sql => CREATE OPERATOR =( LEFTARG = book_format, RIGHTARG = book_format, FUNCTION = book_format_eq ); ``` ```sql CREATE OPERATOR ``` ```sql => CREATE FUNCTION book_format_ge(a book_format, b book_format) RETURNS boolean LANGUAGE sql IMMUTABLE STRICT RETURN book_format_cmp(a,b) >= 0; ``` ```sql CREATE FUNCTION ``` ```sql => CREATE OPERATOR >=( LEFTARG = book_format, RIGHTARG = book_format, FUNCTION = book_format_ge ); ``` ```sql CREATE OPERATOR ``` ```sql => CREATE FUNCTION book_format_gt(a book_format, b book_format) RETURNS boolean LANGUAGE sql IMMUTABLE STRICT RETURN book_format_cmp(a,b) > 0; ``` ```sql CREATE FUNCTION ``` ## Page 23: Page 23 {#source-page-023} ```sql => CREATE OPERATOR >( LEFTARG = book_format, RIGHTARG = book_format, FUNCTION = book_format_gt ); ``` ```sql CREATE OPERATOR ``` ```sql => CREATE OPERATOR CLASS book_format_ops DEFAULT FOR TYPE book_format USING btree AS OPERATOR 1 <, OPERATOR 2 <=, OPERATOR 3 =, OPERATOR 4 >=, OPERATOR 5 >, FUNCTION 1 book_format_cmp(book_format,book_format); ``` ```sql CREATE OPERATOR CLASS ``` Все готово. Проверим: ```sql => SELECT format FROM books GROUP BY format ORDER BY format; ``` ```text format ------------- (76,100,32) (84,108,32) (60,84,16) (60,88,16) (60,90,16) (66,90,16) (60,100,16) (70,90,16) (70,100,16) (84,108,16) (60,90,8) (11 rows) ``` ## Page 24: Практика+ {#source-page-024} 1. В таблице хранятся даты событий. Какой индекс позволит ускорить запросы вида «найти определенное количество событий, наиболее близких по времени к указанной дате»? Проверьте. 2. Расширение pg\_trgm добавляет функции и операторы для работы с триграммами, а также индексную поддержку. В частности, GiST-индекс ускоряет поиск по условиям вида столбец LIKE '%что-то%' - Проверьте работу индекса. Найдите в системном каталоге - все доступные операторы для класса gist\_trgm\_ops. - Что в случае триграмм может служить общим предикатом, - которому удовлетворяют все данные поддерева? ### Комментарии преподавателя 2. Триграммы — это последовательности из трех символов, на которые разбивается строка. Например, из «что-то» получаются следующие триграммы: « ч», « чт», «что», «то-», «о-т», «-то», «то », «о ». Триграммы позволяют определять «похожесть» строк: если и в одной, и в другой много одинаковых триграмм, то и сами строки похожи. Поиск по LIKE, где в начале шаблона находятся обычные символы ('что-то%') ускоряется и простым индексом на основе B-дерева. Но такой индекс бесполезен, если шаблон начинается с %. Для проверки можно воспользоваться таблицей с данными почтовой рассылки pgsql-hackers. Чтобы восстановить эту таблицу в базу данных ext\_opclasses, выполните команду: ```sh student$ zcat ~/mail_messages.sql.gz | psql -d ext_opclasses ``` В качестве запроса можно использовать следующий: ```sql SELECT count(*) FROM mail_messages WHERE subject ILIKE '%magic%'; ``` ## Page 25: 1. Индекс для событий {#source-page-025} ```sql => CREATE DATABASE ext_opclasses; ``` ```sql CREATE DATABASE ``` ```sql => \c ext_opclasses ``` ```text You are now connected to database "ext_opclasses" as user "student". ``` Создадим таблицу и заполним ее случайными данными: ```sql => CREATE TABLE events( date_happen timestamptz ); ``` ```sql CREATE TABLE ``` ```sql => INSERT INTO events(date_happen) -- события за 10 лет SELECT now() - 10*365*24*60*60 * random() * interval '1 sec' FROM generate_series(1,10_000); ``` ```sql INSERT 0 10000 ``` Поиск наиболее близких дат — задача поиска ближайших соседей. Метод доступа btree не поддерживает (пока) поиск ближайших соседей, поэтому придется воспользоваться методом gist (и расширением btree\_gist, добавляющим, в том числе, класс операторов для дат). ```sql => CREATE EXTENSION btree_gist; ``` ```sql CREATE EXTENSION ``` Ускорить необходимые нам запросы поможет GiST-индекс: ```sql => CREATE INDEX ON events USING gist(date_happen); ``` ```sql CREATE INDEX ``` Вот как может выглядеть запрос: ```sql => SELECT date_happen, date_happen <-> now() - interval '3 years' delta FROM events ORDER BY date_happen <-> now() - interval '3 years' LIMIT 10; ``` ```text date_happen | delta -------------------------------+----------------- 2023-04-10 15:40:22.508297+03 | 00:44:36.92209 2023-04-10 17:30:21.761684+03 | 01:05:22.331297 2023-04-10 12:10:17.098219+03 | 04:14:42.332168 2023-04-10 21:40:54.277702+03 | 05:15:54.847315 2023-04-10 09:40:55.587455+03 | 06:44:03.842932 2023-04-10 07:55:28.009215+03 | 08:29:31.421172 2023-04-10 04:06:11.379265+03 | 12:18:48.051122 2023-04-11 06:44:04.68727+03 | 14:19:05.256883 2023-04-11 09:32:27.407142+03 | 17:07:27.976755 2023-04-09 16:27:45.480714+03 | 23:57:13.949673 (10 rows) ``` Его план выполнения использует созданный индекс: ```sql => EXPLAIN (costs off) SELECT * FROM events ORDER BY date_happen <-> now() - interval '3 years' LIMIT 10; ``` ```text QUERY PLAN ------------------------------------------------------------------- Limit -> Index Only Scan using events_date_happen_idx on events Order By: (date_happen <-> (now() - '3 years'::interval)) (3 rows) ``` ### 2. Расширение pg\\\_trgm ## Page 26: Page 26 {#source-page-026} Установим расширение: ```sql => CREATE EXTENSION pg_trgm; ``` ```sql CREATE EXTENSION ``` Посмотрим, как с его помощью ускоряется поиск по условию LIKE, на примере таблицы с архивом почтовой рассылки. ```sh student$ zcat ~/mail_messages.sql.gz | psql -d ext_opclasses ``` ```text SET SET SET SET SET set_config ------------ (1 row) ``` ```sql SET SET SET SET ALTER TABLE DROP TABLE DROP SEQUENCE CREATE SEQUENCE SET SET CREATE TABLE COPY 356125 setval --------- 2317563 (1 row) ``` ```sql ALTER TABLE ``` ```text => \timing on ``` ```text Timing is on. ``` ```sql => SELECT count(*) FROM mail_messages WHERE subject ILIKE '%magic%'; ``` ```text count ------- 103 (1 row) ``` ```text Time: 922,627 ms ``` ```text => \timing off ``` ```text Timing is off. ``` Создадим индекс: ```sql => CREATE INDEX ON mail_messages USING gist(subject gist_trgm_ops); ``` ```sql CREATE INDEX ``` ```sql => EXPLAIN (costs off) SELECT count(*) FROM mail_messages WHERE subject ILIKE '%magic%'; ``` ```text QUERY PLAN ------------------------------------------------------------ Aggregate -> Bitmap Heap Scan on mail_messages Recheck Cond: (subject ~~* '%magic%'::text) -> Bitmap Index Scan on mail_messages_subject_idx Index Cond: (subject ~~* '%magic%'::text) (5 rows) ``` ```text => \timing on ``` ```text Timing is on. ``` ```sql => SELECT count(*) FROM mail_messages WHERE subject ILIKE '%magic%'; ``` ## Page 27: Page 27 {#source-page-027} ```text count ------- 103 (1 row) ``` ```text Time: 58,333 ms ``` ```text => \timing off ``` ```text Timing is off. ``` Операторы для класса операторов gist\_trgm\_ops: ```text => \dAo gist gist_trgm_ops ``` ```text List of operators of operator families AM | Operator family | Operator | Strategy | Purpose ------+-----------------+------------------+----------+---------- gist | gist_trgm_ops | %(text,text) | 1 | search gist | gist_trgm_ops | <->(text,text) | 2 | ordering gist | gist_trgm_ops | ~~(text,text) | 3 | search gist | gist_trgm_ops | ~~*(text,text) | 4 | search gist | gist_trgm_ops | ~(text,text) | 5 | search gist | gist_trgm_ops | ~*(text,text) | 6 | search gist | gist_trgm_ops | %>(text,text) | 7 | search gist | gist_trgm_ops | <->>(text,text) | 8 | ordering gist | gist_trgm_ops | %>>(text,text) | 9 | search gist | gist_trgm_ops | <->>>(text,text) | 10 | ordering gist | gist_trgm_ops | =(text,text) | 11 | search (11 rows) ``` Операторы ~~ и ~~\* эквивалентны LIKE и ILIKE; Операторы ~ и ~\* проверяют соответствие регулярному выражению (с учетом и без учета регистра). Значение остальных операторов описано на странице документации расширения pg\_trgm. Класс операторов для триграмм использует так называемое сигнатурное дерево. Триграммы заменяются на сигнатуры, то есть двоичные числа, в которых все биты нулевые, и лишь один определенный бит установлен в единицу. И вся строка заменяется на сигнатуру, которая вычисляется как побитовое ИЛИ сигнатур составляющих ее триграмм. Таким образом, вместо строки в индексе сохраняется одно число. Общим предикатом в сигнатурном дереве является побитовое ИЛИ всех сигнатур, которые находятся ниже в поддереве. Замена индексируемых элементов битовой сигнатурой позволяет индексировать с помощью GiST вообще все, что угодно (например, изображения). Но, к сожалению, это не слишком эффективный метод. Во-первых, число бит в сигнатуре ограничено, и поэтому некоторые разные элементы будут иметь одинаковую сигнатуру. Во-вторых, чем выше узел стоит в дереве, тем больше в его сигнатуре будет единиц. Это означает, что при поиске придется спускаться в лишние поддеревья и необходимо все время перепроверять полученные результаты. В теме «Слабоструктурированные данные» будет показан другой, более эффективный (но менее универсальный) метод доступа — GIN.