Расширяемость
Классы операторов
12
Авторские права
© Postgres Professional, 2020 год.
Авторы: Егор Рогов, Павел Лузанов
Использование материалов курса
Некоммерческое использование материалов курса (презентации,
демонстрации) разрешается без ограничений. Коммерческое
использование возможно только с письменного разрешения компании
Postgres Professional. Запрещается внесение изменений в материалы
курса.
Обратная связь
Отзывы, замечания и предложения направляйте по адресу:
Отказ от ответственности
Компания Postgres Professional не несет никакой ответственности за
любые повреждения и убытки, включая потерю дохода, нанесенные
прямым или непрямым, специальным или случайным использованием
материалов курса. Компания Postgres Professional не предоставляет
каких-либо гарантий на материалы курса. Материалы курса
предоставляются на основе принципа «как есть» и компания Postgres
Professional не обязана предоставлять сопровождение, поддержку,
обновления, расширения и изменения.
2
Темы
Методы доступа (типы индексов)
Классы и семейства операторов
Метод доступа btree и создание класса операторов для него
Идея метода доступа gist и примеры его использования
3
Методы доступа
Определяют способ получения данных
Табличные методы доступа — организация данных
и чтение всей таблицы
Индексные методы доступа (типы индексов) —
быстрый доступ к небольшой части данных
алгоритмы, связанные с поисковой структурой данных
эффективная одновременная работа
страничная организация данных
журналирование операций
Методы доступа определяют способ получения данных. Их можно
разделить на табличные и индексные методы.
Табличный метод определяет организацию данных в таблице и
работает, когда надо прочитать все данные (Seq Scan). Долгое время
в PostgreSQL был единственный жестко определенный метод, но
в версии 12 появилась возможность создавать новые табличные
методы. Сейчас это скорее экспериментальная возможность, поэтому
других готовых методов (таких, например, как колоночное хранилище)
пока нет, но они должны появиться в будущем.
Индексный метод доступа работает, когда надо получить часть
данных (обычно небольшую) с помощью индекса.
Индексный метод можно рассматривать как каркас, который реализует
основные алгоритмы для работы с индексной структурой данных,
а также берет на себя заботу о низкоуровневых деталях, таких как:
- эффективная конкурентная работа с индексной структурой (в том
числе стратегия блокирования);
- страничная организация данных индекса;
- журналирование операций над индексом в WAL.
Возможность создания новых индексных методов без изменения ядра
системы появилась в версии 9.6.
5
Классы операторов
Набор операторов и вспомогательных функций,
который используется методом доступа
для работы с конкретным типом данных
btree
integer
text
date
text_pattern_ops
text_ops
date_ops
int4_ops
Дальше мы будем говорить не о табличном, а об индексном доступе.
Итак, с одной стороны есть индексный метод доступа (например, btree),
а с другой — конкретные типы данных (такие, как integer, text и т. п.).
Чтобы связать метод доступа с типами данными, используются классы
операторов. Класс операторов состоит из набора операторов (и, при
необходимости, вспомогательных функций), который реализует API
индексного метода доступа.
Важно, что часть логики индексирования находится в методе доступа,
а часть — в классе операторов. Поэтому недостаточно понять только
устройство метода доступа; надо учитывать и то, какой используется
класс операторов.
Для B-деревьев это не так очевидно, поскольку на долю класса
операторов приходится совсем немного. Но в других методах доступа
разные классы операторов могут радикально менять логику.
Заметим также, что для одного и того же метода доступа и одного и того
же типа данных может быть определено несколько классов операторов.
В этом случае пользователь может выбирать то поведение, которое
требуется.
7
Метод доступа btree
Сбалансированное дерево, значения упорядочены
метод применим только для сортируемых типов данных
API метода доступа определяет порядок сортировки
A B
C
D
E F
G
H I J K L
M
N O P Q R S T U V W X Y Z
A D G
I
L O
R U X
A
I
R
Рассмотрим теперь несколько конкретных методов доступа, и начнем
с B-деревьев.
Эта структура данных представляет собой дерево (сбалансированное
по высоте), которое содержит упорядоченные данные. В каждом узле
хранится информация о том, какие диапазоны значений расположены
в дочерних узлах.
Это позволяет находить искомое значение, спускаясь от вершины
дерева к листьям, каждый раз однозначно выбирая подходящий
диапазон. Например, для поиска буквы «H» (на рисунке) мы начинаем
с корня. Поскольку «A» <= «H» < «I», мы спускаемся в первый дочерний
узел, и так далее.
Итак, этот метод доступа применим только для сортируемых данных
(к которым относятся большинство «обычных» типов данных). От
класса операторов требуется только определить, как именно
упорядочиваются значения конкретного типа.
9
Метод доступа gist
Сбалансированное дерево, общий предикат
API метода доступа определяет, что представляет собой предикат
Однако не все типы данных сортируемы. Например, не имеют
естественной упорядоченности такие типы, как геометрические фигуры
(точки, прямоугольники и т. п.), диапазоны, массивы и т. п. Это не
значит, что для таких типов данных нельзя определить операции
сравнения, но практической пользы от них будет немного. Важнее
уметь использовать индексы, например, для поиска точек, входящих
в заданную область, или поиска элементов, входящих в массив, т. е.
для операторов, отличных от «больше», «меньше» и т. п.
B-дерево здесь не годится, но идею индексирования с помощью
сбалансированного дерева можно обобщить. Пусть для каждого
поддерева определено условие (предикат), которому удовлетворяют
все данные, попадающие в это поддерево. Тогда предикат можно
использовать для определения, в какое поддерево (в общем случае —
несколько поддеревьев) нужно спускаться при поиске.
Проще всего представить себе такой GiST-индекс на примере точек.
В этом случае предикатом выступает охватывающий прямоугольник,
а структура называется R-деревом. На рисунке она изображена
схематично. Верхний уровень представлен большим прямоугольником,
охватывающем все проиндексированные точки. На втором уровне
видим два меньших прямоугольника, на нижнем — еще более мелкие.
Суммарно все прямоугольники нижнего уровня охватывают все точки.
Такую же структуру можно построить и для диапазонных типов.
Класс операторов для GiST определяет, как выглядит предикат, и еще
многие детали, необходимые для эффективной работы.
11
Итоги
PostgreSQL предоставляет разнообразную индексную
поддержку любых типов данных, включая пользовательские
Методы доступа — каркас индексирования,
реализующий основной алгоритм и низкоуровневые детали
btree, hash, gist, sp-gist, gin, brin...
Классы операторов связывают метод с типами данных
В этой теме рассматриваются лишь самые основные понятия,
связанные с индексной поддержкой. Заинтересованным в подробностях
рекомендуем внимательно ознакомиться с разделами документации,
ссылки на которые приведены в комментариях к слайдам, а также
с серией статей:
12
Практика
1. Добавьте в таблицу retail_prices ограничение целостности, не
позволяющее создать пересекающиеся интервалы действия
цен для одной книги.
Проверьте план выполнения запроса для поиска актуальной
цены (get_retail_price). Использует ли он индекс, созданный
для поддержки ограничения целостности?
2. Сортировка книг в приложении по формату издания работает
неверно, поскольку значения типа для формата издания
упорядочиваются лексикографически. Сделайте так, чтобы
значения упорядочивались по площади книжной страницы
и проверьте, что сортировка в приложении исправилась.
1. Пример похожего ограничения целостности приводился
в демонстрации.
Если индекс не будет использоваться запросом из функции
get_retail_price, дело может быть в том, что в таблице retail_prices
слишком мало строк и полное сканирование оказывается выгоднее.
Чтобы проверить применимость индекса, вы можете либо добавить
больше строк в таблицу, либо временно запретить использование
полного сканирования:
SET enable_seqscan = off;
2. Создайте класс операторов для метода доступа btree и типа данных
book_format, как было показано в демонстрации.
13
Практика
1. В таблице хранятся даты событий. Какой индекс позволит
ускорить запросы вида «найти определенное количество
событий, наиболее близких по времени к указанной дате»?
Проверьте.
2. Расширение pg_trgm добавляет функции и операторы для
работы с триграммами, а также индексную поддержку.
В частности, GiST-индекс ускоряет поиск по условиям вида
столбец LIKE '%что-то%'
Проверьте работу индекса. Найдите в системном каталоге
все доступные операторы для класса gist_trgm_ops.
Что в случае триграмм может служить общим предикатом,
которому удовлетворяют все данные поддерева?
2. Триграммы — это последовательности из трех символов, на которые
разбивается строка. Например, из «что-то» получаются следующие
триграммы: « ч», « чт», «что», «то-», «о-т», «-то», «то », «о ».
Триграммы позволяют определять «похожесть» строк: если и в одной, и
в другой много одинаковых триграмм, то и сами строки похожи.
Поиск по LIKE, где в начале шаблона находятся обычные символы
('что-то%') ускоряется и простым индексом на основе B-дерева. Но
такой индекс бесполезен, если шаблон начинается с %.
Для проверки можно воспользоваться таблицей с данными почтовой
рассылки pgsql-hackers. Выполните команду
student$ zcat ~/mail_messages.sql.gz | psql -d ext_opclasses
чтобы восстановить эту таблицу в базу данных ext_opclasses.
В качестве запроса можно использовать следующий:
SELECT count(*)
FROM mail_messages
WHERE subject ILIKE '%magic%';
