Расширяемость
Классы операторов
16
Авторские права
© Postgres Professional, 2017–2024
Авторы: Егор Рогов, Павел Лузанов, Илья Баштанов, Игорь Гнатюк
Фото: Олег Бартунов (монастырь Пху и пик Бхрикути, Непал)
Использование материалов курса
Некоммерческое использование материалов курса (презентации,
демонстрации) разрешается без ограничений. Коммерческое
использование возможно только с письменного разрешения компании
Postgres Professional. Запрещается внесение изменений в материалы
курса.
Обратная связь
Отзывы, замечания и предложения направляйте по адресу:
Отказ от ответственности
Компания Postgres Professional не несет никакой ответственности за
любые повреждения и убытки, включая потерю дохода, нанесенные
прямым или непрямым, специальным или случайным использованием
материалов курса. Компания Postgres Professional не предоставляет
каких-либо гарантий на материалы курса. Материалы курса
предоставляются на основе принципа «как есть» и компания Postgres
Professional не обязана предоставлять сопровождение, поддержку,
обновления, расширения и изменения.
2
Темы
Методы доступа (типы индексов)
Классы и семейства операторов
Метод доступа btree и создание класса операторов для него
Идея метода доступа gist и примеры его использования
3
Методы доступа
Определяют способ получения данных
Табличные методы доступа — организация данных
и чтение всей таблицы
Индексные методы доступа (типы индексов) —
быстрый доступ к небольшой части данных
алгоритмы, связанные с поисковой структурой данных
эффективная одновременная работа
страничная организация данных
журналирование операций
Методы доступа определяют способ получения данных. Их можно
разделить на табличные и индексные методы.
Табличный метод определяет организацию данных в таблице и
работает, когда надо прочитать все данные (Seq Scan). В PostgreSQL
существует единственный табличный метод heap, и других готовых
методов (таких, например, как колоночное хранилище) еще нет, но они
должны появиться в будущем.
Индексный метод доступа работает, когда надо быстро получить часть
данных (обычно небольшую) с помощью индекса.
Индексный метод можно рассматривать как каркас, который реализует
основные алгоритмы для работы с индексной структурой данных,
а также берет на себя заботу о низкоуровневых деталях, таких как:
●
эффективная конкурентная работа с индексной структурой (в том
числе стратегия блокирования);
●
страничная организация данных индекса;
●
журналирование операций над индексом в WAL.
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
Однако не все типы данных сортируемы. Например, не имеют
естественной упорядоченности геометрические фигуры (точки,
прямоугольники и т. п.), диапазоны, массивы и т. п. Конечно, для таких
типов данных можно определить операции сравнения, но практической
пользы от них будет немного. Важнее уметь использовать индексы,
например, для поиска точек, входящих в заданную область или
в массив, т. е. для операторов, отличных от «больше», «меньше» и т. п.
B-дерево здесь не годится, но идею индексирования с помощью
сбалансированного дерева можно обобщить. При поиске по дереву
в каждом узле принимается решение, в каком поддереве (в общем
случае — в нескольких поддеревьях) продолжить поиск. Для этого
каждому поддереву ставится в соответствие условие (предикат),
которому удовлетворяют все находящиеся в нем данные.
Класс операторов для GiST (generalized search tree — обобщенное
дерево поиска) определяет, как выглядит предикат, и еще многие
детали, необходимые для эффективной работы.
Идею работы GiST-индексов рассмотрим на примере точек на
плоскости.
Плоскость разбивается на несколько прямоугольников, которые
в сумме покрывают все индексируемые точки. Эти прямоугольники
составляют верхний уровень дерева.
Как видно на рисунке, прямоугольники могут пересекаться (хотя это
и уменьшает эффективность поиска).
10
Метод доступа GiST
На следующем уровне дерева каждый из больших прямоугольников
распадается на прямоугольники меньшего размера.
11
Метод доступа GiST
На последнем уровне дерева каждый ограничивающий прямоугольник
будет содержать столько точек, сколько помещается на одну индексную
страницу.
Общее условие разбиения таково: прямоугольник родительской
вершины охватывает все прямоугольники соответствующего поддерева.
Это позволяет, например, быстро находить точки, лежащие внутри
определенной области:
1) находим прямоугольники, пересекающиеся с заданной областью,
на верхнем уровне индекса;
2) спускаемся в выбранные поддеревья и повторяем поиск в них.
Такой алгоритм индексирования называется R-деревом.
13
Итоги
PostgreSQL предоставляет разнообразную индексную
поддержку любых типов данных, включая пользовательские
Методы доступа — каркас индексирования,
реализующий основной алгоритм и низкоуровневые детали
btree, hash, gist, sp-gist, gin, brin...
Классы операторов связывают метод с типами данных
В этой теме рассматриваются лишь самые основные понятия,
связанные с индексной поддержкой.
Заинтересованным в подробностях рекомендуем внимательно
ознакомиться с разделами документации, ссылки на которые
приведены в комментариях к слайдам, а также с главами 4 и 5 книги
14
Практика
1. Добавьте в таблицу retail_prices ограничение целостности,
не позволяющее создать пересекающиеся диапазоны
действия цен для одной книги.
Проверьте план выполнения запроса для поиска актуальной
цены (get_retail_price). Использует ли он индекс, созданный
для поддержки ограничения целостности?
2. Сортировка книг в приложении по формату издания работает
неверно, поскольку значения типа для формата издания
упорядочиваются лексикографически. Сделайте так, чтобы
значения упорядочивались по площади книжной страницы
и проверьте, что сортировка в приложении исправилась.
1. Пример похожего ограничения целостности приводился
в демонстрации.
Если индекс не будет использоваться запросом из функции
get_retail_price, дело может быть в том, что в таблице retail_prices
слишком мало строк и полное сканирование оказывается выгоднее.
Чтобы проверить применимость индекса, вы можете либо добавить
больше строк в таблицу, либо временно запретить использование
полного сканирования:
SET enable_seqscan = off;
2. Создайте класс операторов для метода доступа btree и типа данных
book_format, как было показано в демонстрации.
15
Практика+
1. В таблице хранятся даты событий. Какой индекс позволит
ускорить запросы вида «найти определенное количество
событий, наиболее близких по времени к указанной дате»?
Проверьте.
2. Расширение pg_trgm добавляет функции и операторы для
работы с триграммами, а также индексную поддержку.
В частности, GiST-индекс ускоряет поиск по условиям вида
столбец LIKE '%что-то%'
Проверьте работу индекса. Найдите в системном каталоге
все доступные операторы для класса gist_trgm_ops.
Что в случае триграмм может служить общим предикатом,
которому удовлетворяют все данные поддерева?
2. Триграммы — это последовательности из трех символов, на которые
разбивается строка. Например, из «что-то» получаются следующие
триграммы: « ч», « чт», «что», «то-», «о-т», «-то», «то », «о ».
Триграммы позволяют определять «похожесть» строк: если и в одной,
и в другой много одинаковых триграмм, то и сами строки похожи.
Поиск по LIKE, где в начале шаблона находятся обычные символы
('что-то%') ускоряется и простым индексом на основе B-дерева.
Но такой индекс бесполезен, если шаблон начинается с %.
Для проверки можно воспользоваться таблицей с данными почтовой
рассылки pgsql-hackers. Чтобы восстановить эту таблицу в базу данных
ext_opclasses, выполните команду:
student$ zcat ~/mail_messages.sql.gz | psql -d ext_opclasses
В качестве запроса можно использовать следующий:
SELECT count(*)
FROM mail_messages
WHERE subject ILIKE '%magic%';
