Индексы

В предыдущих темах мы изучали реляционную модель, логическое и физическое проектирование таблиц. Но до сих пор данные читались последовательным перебором: чтобы найти одну книгу по названию или один заказ по номеру, СУБД была вынуждена прочитать всю таблицу с диска страницу за страницей. В учебной базе с двумя тысячами строк это занимает миллисекунды, но в промышленной базе с миллионами записей последовательное сканирование превращает запрос в секундное ожидание и блокирует дисковую подсистему.

Эта тема посвящена индексам — вспомогательным структурам данных, которые связывают значения столбцов с физическими адресами строк таблицы (TID — Tuple Identifier). Мы разберём, как устроено классическое B-дерево, почему оно одинаково быстро находит единичные строки и диапазоны, как работают составные, частичные и покрывающие индексы, а также изучим специализированные типы индексов в PostgreSQL: GIN, GiST, BRIN и Hash.

Зачем нужны индексы

Последовательное чтение против прямого доступа

Пусть таблица заказов orders масштаба scale=50 содержит 1 000 000 строк и занимает около 450 МБ (примерно 25 000 страниц по 8 КиБ). Если мы выполняем простой запрос:

SELECT * FROM bookstore.orders WHERE customer_id = 12345;

Без индекса сервер выполняет последовательное сканирование (Seq Scan) ⁵: процесс чтения считывает с диска в буферный кэш все 25 000 страниц, проверяя каждую запись на соответствие предикату customer_id = 12345. Если искомых заказов всего три штуки, 99,99 % прочитанных данных оказываются бесполезными.

Индекс представляет собой упорядоченный список пар (ключ, TID). Зная customer_id = 12345, сервер за 3–4 операции чтения переходит по ветвям дерева к нужной листовой странице индекса, находит три указателя на строки (номер страницы и смещение внутри страницы) и считывает ровно те страницы таблицы, где эти строки физически находятся. Число дисковых обращений сокращается с 25 000 до 6–7.

Понятие селективности

Всегда ли индекс выгоднее последовательного сканирования? Нет. Эффективность индекса зависит от селективности предиката (англ. selectivity) — доли строк таблицы, удовлетворяющих условию ²³.

• Если предикат выбирает 0,01 % строк (высокая селективность), индекс даёт колоссальный выигрыш.
• Если же предикат выбирает 40 % строк (низкая селективность), обращение по индексу порождает 400 000 случайных чтений страниц таблицы. Каждое случайное чтение страницы (random_page_cost) на шпиндельных дисках и даже на SSD обходится планировщику дороже последовательного чтения (seq_page_cost), при котором ядро ОС использует упреждающее чтение (readahead). В этом случае планировщик PostgreSQL сознательно отказывается от индекса и выбирает последовательное чтение всей таблицы ¹.

B-дерево: фундаментальная структура хранения

По умолчанию в PostgreSQL команда CREATE INDEX создаёт B-дерево (точнее, его модификацию B^+-дерево с алгоритмом Lehman & Yao ⁴⁶).

Устройство B-дерева в PostgreSQL

B-дерево состоит из страниц размером 8 КиБ, организованных в сбалансированную иерархию ¹⁶:

1. Метастраница (Meta Page): блок 0, содержащий версию реализации, указатель на текущий корневой блок и статистику дерева.
2. Корневой узел (Root Page): вершина дерева, содержащая пары «ключ — номер дочернего блока».
3. Внутренние узлы (Internal Pages): промежуточные уровни маршрутизации поиска.
4. Листовые узлы (Leaf Pages): нижний уровень дерева, хранящий пары (ключ, TID). Все листовые страницы связаны между собой двусвязным списком через указатели btpo_prev и btpo_next.

Благодаря двусвязному списку листьев B-дерево одинаково эффективно обслуживает операторы равенства =, неравенства <, <=, >, >=, проверку принадлежности диапазону BETWEEN и упорядочивание ORDER BY.

Расчёт высоты дерева

Ключевое достоинство B-дерева — огромный коэффициент ветвления (англ. fanout). На одной странице 8 КиБ помещается от 200 до 400 ключей с указателями ¹.

• При коэффициенте ветвления B = 300:
  • Уровень 1 (корень): 300 записей.
  • Уровень 2: 300^2 = 90\,000 записей.
  • Уровень 3: 300^3 = 27\,000\,000 записей.
  • Уровень 4: 300^4 = 8\,100\,000\,000 записей (8 миллиардов!).

Для таблицы в 1 миллион строк глубина дерева составляет всего 2–3 уровня (tree_level). Это означает, что доступ к любой строке гарантированно требует не более 3–4 чтений страниц.

Внутреннюю структуру B-дерева можно исследовать через стандартное расширение pageinspect:

SELECT tree_level, internal_pages, leaf_pages
FROM pgstatindex('bookstore.orders_pkey');

 tree_level | internal_pages | leaf_pages
------------+----------------+------------
          2 |             15 |       2740

Префиксный поиск и классы операторов

B-дерево по текстовому столбцу с типовой локалью использует сортировку по правилам национального алфавита (collation). В условиях вида WHERE email LIKE 'ivan%' планировщик часто не может использовать стандартный индекс, так как порядок символов в ICU-локали может отличаться от строгого побайтового сравнения.

Для поддержки быстрого поиска по префиксу шаблонных строк LIKE 'abc%' индекс создаётся со специальным классом операторов text_pattern_ops ⁵:

CREATE INDEX customer_email_prefix_idx ON bookstore.customer (email text_pattern_ops);

С этим классом операторов B-дерево упорядочивает байты по кодам ASCII/UTF-8, трансформируя условие LIKE 'ivan%' в диапазонное сканирование email >= 'ivan' AND email < 'ivao'.

Составные и покрывающие индексы

Правило левого префикса в составных индексах

Индекс может быть построен по нескольким столбцам:

CREATE INDEX orders_cust_created_idx ON bookstore.orders (customer_id, created_at);

В таком индексе записи отсортированы строго лексикографически: сначала по первому столбцу customer_id, а строки с одинаковым customer_id — по второму столбцу created_at.

Отсюда следует фундаментальное правило левого префикса ²:

• Запрос WHERE customer_id = 10 AND created_at >= '2024-01-01' использует индекс целиком;
• Запрос WHERE customer_id = 10 использует дерево для поиска диапазона покупателя;
• Запрос WHERE created_at >= '2024-01-01' не может использовать индекс эффективно, так как даты распределены по всем покупателям и не образуют непрерывного диапазона.

Покрывающие индексы (INCLUDE) и Index Only Scan

Обычное индексное сканирование (Index Scan) сначала находит TID в индексе, а затем обращается к таблице («куче» — heap), чтобы извлечь остальные столбцы запроса. Каждое обращение к куче требует чтения страницы.

Если все столбцы, запрошенные клиентом, уже содержатся в самом индексе, сервер может выполнить сканирование только индекса (Index Only Scan) ¹⁵. Но если добавить столбец в индекс обычным образом (CREATE INDEX ON orders (customer_id, status)), дерево будет сортировать данные и по status, тратя процессорное время на сравнение строк и расщепление страниц.

Конструкция INCLUDE добавляет неключевые столбцы только в листовые страницы дерева без участия в сортировке:

CREATE INDEX orders_cust_status_inc_idx ON bookstore.orders (customer_id) INCLUDE (status);

Запрос SELECT status FROM bookstore.orders WHERE customer_id = 42 считывает только индекс.

Тонкость: из-за механизма MVCC (многоверсионности, тема 12) индекс не хранит номера транзакций xmin/xmax. Чтобы убедиться, что найденная строка видна текущему снимку, PostgreSQL обращается к карте видимости (Visibility Map, VM) таблицы. Если бит страницы в карте видимости равен 1 (все строки страницы зафиксированы и видны всем), обращение к куче исключается полностью (Heap Fetches: 0) ¹.

Специализированные индексы

Частичные индексы (Partial Indexes)

Если запрос фильтрует строки по редкому значению флага, нет смысла индексировать миллионы неинтересных строк. Частичный индекс содержит предикат WHERE:

CREATE INDEX orders_unprocessed_idx ON bookstore.orders (created_at)
WHERE status IN ('pending', 'processing');

Если незавершённых заказов в интернет-магазине 0,5 %, частичный индекс займёт в 200 раз меньше места в оперативной памяти и не будет замедлять вставки завершённых заказов.

Индексы по выражениям

Если приложение часто ищет данные без учёта регистра, условие WHERE lower(email) = 'test@example.com' при обычном индексе по email приведёт к Seq Scan, так как функция lower() скрывает значение ключа от планировщика. Решение — индекс по выражению:

CREATE INDEX customer_lower_email_idx ON bookstore.customer (lower(email));

Другие методы доступа: GIN, GiST, BRIN, Hash

PostgreSQL поддерживает подключаемую архитектуру методов доступа к индексам ¹⁵:

Инвертированный индекс GIN

В B-дереве строка индекса содержит (значение, TID). В GIN (Generalized Inverted Index) ⁷ индексируются элементы, входящие в состав составных значений (слова текста, элементы массива или ключи/значения JSONB). GIN строит список TID для каждого отдельного элемента:

CREATE INDEX book_attrs_gin_idx ON bookstore.book USING gin (attrs);

Запрос SELECT * FROM bookstore.book WHERE attrs @> '{"binding": "hard"}'; мгновенно находит книги по инвертированному списку ключа binding. А расширение pg_trgm позволяет с помощью GIN ускорять поиск произвольных подстрок LIKE '%слово%' за счёт индексирования 3-буквенных сочетаний (триграмм).

Блочный индекс BRIN

В аналитических таблицах и журналах событий строки вставляются монотонно по времени. Значит, на страницах в начале диска лежат старые даты, а в конце — свежие. BRIN (Block Range Index) хранит только минимальное и максимальное значение столбца для диапазона страниц (по умолчанию 128 блоков = 1 МБ).

• Размер BRIN-индекса для таблицы на 100 млн строк составляет считанные сотни килобайт!
• При поиске WHERE created_at >= '2024-06-01' BRIN позволяет мгновенно отбросить 95 % страниц диска, читая только блоки с подходящими экстремумами.

Эксплуатация индексов и пагинация

Цена индексов и HOT-обновления

Каждый созданный индекс ускоряет чтение, но замедляет INSERT, UPDATE и DELETE, так как СУБД обязана синхронно обновить все деревья индексов.

Для смягчения этой проблемы в PostgreSQL реализован механизм HOT (Heap-Only Tuples) ¹: если при операции UPDATE значения индексируемых столбцов не изменились, а на текущей странице таблицы есть свободное место, новая версия строки создаётся на той же странице без добавления записей в индексы. Старая и новая версии связываются цепочкой прямо внутри страницы.

Обслуживание: CONCURRENTLY и разрастание

Команда CREATE INDEX требует эксклюзивной блокировки SHARE, разрешающей чтение, но блокирующей любые операции записи INSERT/UPDATE/DELETE. На рабочей базе с миллионами строк создание индекса может длиться минуты, парализуя сервис.

Для изменения структуры без простоя применяется конкурентное создание ⁵:

CREATE INDEX CONCURRENTLY idx_orders_date ON bookstore.orders (created_at);

В режиме CONCURRENTLY сервер сканирует таблицу в два прохода, не блокируя пишущие транзакции. Если при построении произошёл сбой, индекс помечается как INVALID и требует удаления либо перестроения утилитой REINDEX CONCURRENTLY.

Пагинация по ключу (Keyset) против OFFSET

При отображении каталогов в веб-приложениях традиционно используется смещение LIMIT 20 OFFSET 100000.

Конструкция OFFSET 100000 вынуждает сервер прочитать по индексу 100 000 строк, отбросить их и вернуть только следующие 20. На 5000-й странице сайта запрос начинает зависать на секунды.

Промышленный стандарт решения этой проблемы — пагинация по ключу (keyset pagination / seek method) ²:

-- Быстрый переход к следующей странице:
SELECT order_id, created_at, status
FROM bookstore.orders
WHERE (created_at, order_id) < ('2024-05-15 14:30:00+03', 451200)
ORDER BY created_at DESC, order_id DESC
LIMIT 20;

Благодаря составному индексу (created_at, order_id) планировщик не перебирает 100 000 строк, а делает точечный спуск по дереву прямо к первому элементу следующей страницы, гарантируя одинаковое время отклика (1–2 мс) как на первой, так и на миллионной странице.

Итоги темы

Индексы — главный инструмент обеспечения производительности реляционных баз данных. Классическое B-дерево обеспечивает логарифмическую сложность O(\log N) операций поиска, вставки и диапазонного чтения. Составные индексы подчиняются правилу левого префикса, а конструкция INCLUDE реализует Index Only Scan, исключая обращения к страницам кучи при актуальной карте видимости. Для специализированных сценариев PostgreSQL предоставляет инвертированные индексы GIN для JSONB и текстового поиска, а также компактные зонные индексы BRIN для упорядоченных во времени журналов.

В следующей теме мы изучим, как планировщик запросов на основе стоимостной модели решает, когда именно использовать эти индексы, как читать планы EXPLAIN (ANALYZE, BUFFERS) и оптимизировать сложные соединения.

Литература

1. Рогов Е. В. PostgreSQL 16 изнутри. — М.: ДМК Пресс, 2024.
2. Winand M. SQL Performance Explained. — 2012. https://use-the-index-luke.com/
3. Silberschatz A., Korth H. F., Sudarshan S. Database System Concepts. 7th ed. — McGraw-Hill, 2019.
4. Lehman P. L., Yao S. B. Efficient Locking for Concurrent Operations on B-Trees. — ACM Transactions on Database Systems, 1981, Vol. 6, No. 4, С. 650–670.
5. PostgreSQL Global Development Group. PostgreSQL 16 Documentation. Chapter 11. Indexes. — 2024. https://www.postgresql.org/docs/16/indexes.html
6. PostgreSQL Global Development Group. PostgreSQL 16 Documentation. Chapter 64. B-Tree Indexes. — 2024. https://www.postgresql.org/docs/16/btree.html
7. Bartunov O., Sigaev T. Generalized Inverted Index for PostgreSQL. — 2006.

Дополнительные материалы

Вопросы для самопроверки

1. Почему для поиска трёх строк в таблице на 1 миллион записей без индекса СУБД считывает 25 000 страниц, и как индекс решает эту проблему?
2. Что такое селективность предиката и почему при условии, выбирающем 40 % строк, планировщик отказывается от индекса в пользу Seq Scan?
3. Из каких типов страниц состоит B^+-дерево в PostgreSQL? Какую роль играет двусвязный список листовых страниц?
4. Рассчитайте предельную вместимость B-дерева высотой 3 уровня при коэффициенте ветвления B = 300.
5. Почему условие WHERE email LIKE 'user%' может не использовать стандартное B-дерево и как помогает класс операторов text_pattern_ops?
6. Сформулируйте правило левого префикса для составного индекса (a, b, c). Какие из условий (a, b), (b, c), (a, c) смогут использовать данный индекс?
7. Чем покрывающий индекс с предложением INCLUDE отличается от добавления столбца в тело составного индекса?
8. Что такое Index Only Scan и какую роль играет карта видимости (Visibility Map) таблицы? Почему при устаревшей карте видимости появляются Heap Fetches?
9. В каких сценариях выгодно создавать частичные индексы (WHERE ...)? Приведите пример из архитектуры интернет-магазина.
10. Почему запрос WHERE lower(email) = 'test@example.com' не может использовать обычный индекс по столбцу email?
11. В чём принципиальное различие между прямым B-деревом и инвертированным индексом GIN? Для каких типов данных незаменим GIN?
12. Как устроен зонный индекс BRIN и почему он занимает считанные килобайты на таблицах в десятки гигабайт?
13. Что такое HOT-обновления (Heap-Only Tuples) и при каких двух условиях они возможны?
14. Почему на рабочей базе данных создание индекса выполняют командой CREATE INDEX CONCURRENTLY? Какие блокировки выставляет обычный CREATE INDEX?
15. Почему пагинация LIMIT 20 OFFSET 100000 деградирует по времени и как метод поиска по ключу (keyset pagination) устраняет эту проблему?

Глоссарий темы

Шпаргалка по инструментам

Создание и управление индексами:

-- Обычное и конкурентное B-дерево:
CREATE INDEX idx_orders_customer ON bookstore.orders (customer_id);
CREATE INDEX CONCURRENTLY idx_orders_customer ON bookstore.orders (customer_id);

-- Составной индекс:
CREATE INDEX idx_orders_cust_date ON bookstore.orders (customer_id, created_at);

-- Покрывающий индекс:
CREATE INDEX idx_orders_covering ON bookstore.orders (customer_id) INCLUDE (status, created_at);

-- Частичный индекс:
CREATE INDEX idx_orders_active ON bookstore.orders (created_at) WHERE status = 'pending';

-- Индекс по выражению:
CREATE INDEX idx_customer_lower_email ON bookstore.customer (lower(email));

-- Префиксный текстовый класс операторов:
CREATE INDEX idx_cust_email_pattern ON bookstore.customer (email text_pattern_ops);

-- GIN для JSONB и триграмм (pg_trgm):
CREATE INDEX idx_book_attrs ON bookstore.book USING gin (attrs);
CREATE EXTENSION IF NOT EXISTS pg_trgm;
CREATE INDEX idx_book_title_trgm ON bookstore.book USING gin (title gin_trgm_ops);

-- BRIN для хронологических логов:
CREATE INDEX idx_orders_brin_date ON bookstore.orders USING brin (created_at) WITH (pages_per_range = 128);

-- Удаление и перестроение:
DROP INDEX CONCURRENTLY idx_orders_customer;
REINDEX TABLE CONCURRENTLY bookstore.orders;

Анализ структуры через pageinspect:

CREATE EXTENSION IF NOT EXISTS pageinspect;
SELECT * FROM bt_metap('bookstore.orders_pkey');
SELECT tree_level, internal_pages, leaf_pages, avg_leaf_density FROM pgstatindex('bookstore.orders_pkey');
SELECT * FROM bt_page_stats('bookstore.orders_pkey', 1);
SELECT itemoffset, ctid, itemlen, data FROM bt_page_items('bookstore.orders_pkey', 1) LIMIT 5;

Типичные ошибки

1. Неправильный порядок столбцов в составном индексе. Создание индекса (created_at, customer_id) для запроса WHERE customer_id = 123 делает индекс неэффективным. Столбец с проверкой на точное равенство всегда должен стоять левее диапазонных условий.
2. Использование функций над индексируемым столбцом. Условие WHERE date(created_at) = '2024-05-01' отключает обычный индекс по created_at. Правильно: диапазонное условие WHERE created_at >= '2024-05-01' AND created_at < '2024-05-02' либо индекс по выражению CREATE INDEX ON orders (date(created_at)).
3. Создание лишних индексов «на всякий случай». Каждый индекс замедляет вставку и обновление строк. Индексы нужны под реальные профили запросов приложения, а не на каждый столбец таблицы.
4. Забытый CONCURRENTLY на рабочей базе. Выполнение обычного CREATE INDEX блокирует запись в таблицу на всё время построения, вызывая таймауты в веб-приложении.
5. Глубокий OFFSET в интерфейсах. Использование OFFSET 50000 в API приводит к экспоненциальному росту времени ответа. Для больших списков следует использовать keyset-пагинацию.

Что почитать и посмотреть

• Рогов Е. В. PostgreSQL 16 изнутри — фундаментальная русскоязычная книга; главы о методах доступа и B-дереве.
• Use The Index, Luke! — интерактивное руководство Маркуса Винанда по индексам и производительности SQL.
• Документация PostgreSQL 16: Индексы.
• Lehman P. L., Yao S. B. Efficient Locking for Concurrent Operations on B-Trees — классическая статья 1981 года об алгоритме B-link tree.

Лабораторная работа 10. Индексы

• Раздел курса: тема 10 «Индексы»

Введение

До сих пор учебные запросы выполнялись на базе данных малого масштаба, где последовательное сканирование всей таблицы происходило мгновенно. В этой лабораторной работе мы переходим к базе данных bookstore50 масштаба scale=50, содержащей около 1 миллиона строк в таблице заказов и сотни тысяч связанных записей.

В этой работе вы на практике увидите разницу между последовательным чтением таблицы и доступом по индексам, исследуете внутреннее устройство B-дерева через системное расширение pageinspect, построите составные, частичные и покрывающие индексы, примените инвертированные индексы GIN для JSONB и ускорите пагинацию каталога в сотни раз с помощью метода поиска по ключу (keyset pagination).

Цель работы

Научиться проектировать, создавать и анализировать индексы в PostgreSQL, оценивать их влияние на время выполнения запросов, размер базы данных и скорость операций вставки.

После выполнения работы вы сможете:

• измерять время выполнения запроса и число прочитанных страниц буферного кэша с помощью EXPLAIN (ANALYZE, BUFFERS);
• исследовать внутреннюю структуру B-дерева через функции bt_metap и pgstatindex расширения pageinspect;
• определять правильный порядок столбцов в составном индексе на основе правила левого префикса;
• строить покрывающие индексы с предложением INCLUDE для достижения сканирования только индекса (Index Only Scan);
• оптимизировать объем индекса с помощью частичных индексов и индексов по выражениям;
• использовать инвертированные индексы GIN для поиска по атрибутам JSONB и нечёткого текстового поиска;
• заменять медленную пагинацию OFFSET на быстрый поиск по ключу (keyset pagination).

Оборудование и учебная среда

Работа выполняется в учебной базе данных bookstore50 (масштаб scale=50, около 450 МБ). Для выполнения работы потребуются:

• клиент psql;
• расширения PostgreSQL: pageinspect, pgstattuple, pg_trgm;
• скрипты из архива окружения lr-env.zip.

Подготовка базы данных перед началом работы:

# Распаковать архив окружения:
unzip lr-env.zip && cd lr-env

# Если база bookstore50 ещё не создана:
createdb bookstore50
psql -d bookstore50 -f schema.sql
psql -d bookstore50 -v scale=50 -f data.sql

# Привести индексы к исходному состоянию работы:
psql -d bookstore50 -f setup.sql

Порядок выполнения работы

Часть 1. Сравнение производительности: Seq Scan vs Index Scan

1. Подключитесь к базе bookstore50 в psql и включите измерение времени:

   \timing on
   SET search_path = bookstore, public;
   

2. Выполните запрос поиска заказов конкретного покупателя без индекса и сохраните план выполнения:

   EXPLAIN (ANALYZE, BUFFERS)
   SELECT * FROM orders WHERE customer_id = 12345;
   

   Обратите внимание на строку Seq Scan on orders, время выполнения (Execution Time) и число прочитанных страниц в буфере (Buffers: shared read=...).

3. Создайте B-дерево по столбцу customer_id и измерьте его размер:

   CREATE INDEX orders_customer_id_idx ON orders (customer_id);
   SELECT pg_size_pretty(pg_relation_size('orders_customer_id_idx'));
   

4. Повторите запрос поиска заказов. Сравните время выполнения и количество прочитанных блоков буферного кэша. Зафиксируйте переход планировщика к Bitmap Heap Scan или Index Scan.

Часть 2. Анатомия B-дерева через pageinspect

1. Подключите расширение pageinspect:

   CREATE EXTENSION IF NOT EXISTS pageinspect;
   

2. Получите метаданные индекса первичного ключа orders_pkey:

   SELECT * FROM bt_metap('bookstore.orders_pkey');
   

   Зафиксируйте номер корневого блока (root) и уровень дерева (level).

3. Запросите статистику B-дерева через функцию pgstatindex:

   SELECT tree_level, internal_pages, leaf_pages, avg_leaf_density
   FROM pgstatindex('bookstore.orders_pkey');
   

   Сравните реальную высоту дерева с теоретическим расчётом для 1 000 000 строк при коэффициенте ветвления B \approx 300.

4. Просмотрите записи корневой страницы B-дерева с помощью bt_page_items:

   SELECT itemoffset, ctid, itemlen
   FROM bt_page_items('bookstore.orders_pkey', (SELECT root FROM bt_metap('bookstore.orders_pkey')))
   LIMIT 5;
   

Часть 3. Составной индекс и правило левого префикса

1. Удалите одиночный индекс и создайте составной индекс (customer_id, created_at):

   DROP INDEX orders_customer_id_idx;
   CREATE INDEX orders_cust_created_idx ON orders (customer_id, created_at);
   

2. Проверьте планы выполнения трёх запросов:

   • Запрос А (оба столбца):

     EXPLAIN (ANALYZE, BUFFERS)
     SELECT * FROM orders WHERE customer_id = 12345 AND created_at >= '2024-01-01';
     

   • Запрос Б (только первый столбец):

     EXPLAIN (ANALYZE, BUFFERS)
     SELECT * FROM orders WHERE customer_id = 12345;
     

   • Запрос В (только второй столбец):

     EXPLAIN (ANALYZE, BUFFERS)
     SELECT * FROM orders WHERE created_at >= '2024-06-01';
     

3. Объясните, почему запрос В не может эффективно использовать индекс и выполняет Seq Scan.

Часть 4. Покрывающий индекс и Index Only Scan

1. Выполните запрос статуса заказа по покупателю:

   EXPLAIN (ANALYZE, BUFFERS)
   SELECT status FROM orders WHERE customer_id = 12345;
   

   Обратите внимание на строку Heap Fetches (число обращений к страницам таблицы).

2. Перестройте индекс, сделав его покрывающим с помощью INCLUDE:

   DROP INDEX orders_cust_created_idx;
   CREATE INDEX orders_cust_status_inc_idx ON orders (customer_id) INCLUDE (status);
   

3. Выполните запрос повторно. Убедитесь, что метод доступа сменился на Index Only Scan, а Heap Fetches равен нулю при актуальной карте видимости (выполните VACUUM orders при необходимости).

Часть 5. Частичные индексы и поиск по выражению

1. Частичный индекс: создайте частичный индекс только для незавершённых заказов:

   CREATE INDEX orders_active_idx ON orders (created_at)
   WHERE status IN ('pending', 'processing');
   SELECT pg_size_pretty(pg_relation_size('orders_active_idx'));
   

   Сравните размер этого индекса с полным индексом по дате. Убедитесь, что запрос выборки активных заказов использует частичный индекс.

2. Индекс по выражению: создайте индекс для регистронезависимого поиска пользователей по email:

   CREATE INDEX customer_lower_email_idx ON customer (lower(email));
   EXPLAIN (ANALYZE, BUFFERS)
   SELECT * FROM customer WHERE lower(email) = 'user12345@example.com';
   

Часть 6. Индексы GIN и BRIN

1. GIN для JSONB: постройте инвертированный индекс по атрибутам книг:

   CREATE INDEX book_attrs_gin_idx ON book USING gin (attrs);
   EXPLAIN (ANALYZE, BUFFERS)
   SELECT title FROM book WHERE attrs @> '{"binding": "hard"}';
   

2. BRIN по хронологическим данным: создайте индекс BRIN по дате создания заказа:

   CREATE INDEX orders_created_brin_idx ON orders USING brin (created_at);
   SELECT pg_size_pretty(pg_relation_size('orders_created_brin_idx'));
   

   Сравните размер BRIN-индекса с размером аналогичного B-дерева.

Часть 7. Оптимизация пагинации: Keyset vs OFFSET

1. Замерьте время выборки 100 000-й страницы каталога через классический OFFSET:

   CREATE INDEX IF NOT EXISTS orders_created_id_idx ON orders (created_at DESC, order_id DESC);
   EXPLAIN (ANALYZE, BUFFERS)
   SELECT order_id, created_at, status
   FROM orders
   ORDER BY created_at DESC, order_id DESC
   LIMIT 20 OFFSET 100000;
   

2. Выполните тот же переход методом поиска по ключу (keyset pagination):

   -- Подставьте значения created_at и order_id с предыдущей страницы:
   EXPLAIN (ANALYZE, BUFFERS)
   SELECT order_id, created_at, status
   FROM orders
   WHERE (created_at, order_id) < ('2024-04-10 12:00:00+03', 450000)
   ORDER BY created_at DESC, order_id DESC
   LIMIT 20;
   

   Сравните время выполнения и количество прочитанных блоков в обоих случаях.

Что должно получиться

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

1. Запрос по customer_id на базе scale=50 без индекса выполняет Seq Scan (чтение ~25 000 блоков буфера), а с индексом — Bitmap Heap Scan / Index Scan (чтение менее 10 блоков) с ускорением в сотни раз.
2. Высота B-дерева для 1 миллиона записей в orders_pkey составляет 2 уровня (tree_level = 2), что подтверждает логарифмическую масштабируемость O(\log N).
3. Составной индекс (customer_id, created_at) ускоряет фильтрацию по обоим столбцам и только по customer_id, но игнорируется при поиске только по created_at.
4. Покрывающий индекс с INCLUDE (status) переводит запрос в режим Index Only Scan с нулевым обращением к куче (Heap Fetches: 0).
5. Частичный индекс orders_active_idx занимает менее 5 % от размера полного индекса таблицы.
6. Keyset-пагинация возвращает результат за 1–2 мс, тогда как запрос с OFFSET 100000 сканирует тысячи строк и выполняется в десятки раз дольше.

Журнал работы

В журнал работы занесите:

1. Таблицу сравнения времени выполнения и прочитанных буферов (Buffers: shared hit/read) для запросов без индекса и с B-деревом.
2. Вывод функций bt_metap и pgstatindex для индекса первичного ключа с расчётом теоретической высоты дерева.
3. Планы выполнения запросов А, Б, В для составного индекса с объяснением правила левого префикса.
4. Размеры и время выполнения запросов для индексов B-tree, GIN и BRIN.
5. Сравнительный анализ времени выборки страницы через OFFSET 100000 и keyset pagination.