Тема 3. Этапы проектирования баз данных — Практическое занятие №8: поиск по одному и нескольким полям

1. Проблема: как найти 1 запись среди 10 000 000?

Жизнь без индекса: Sequential Scan

Таблица в СУБД — это неупорядоченная «куча» (Heap) дисковых страниц по 8 КБ.

Поиск требует побайтового чтения ВСЕХ блоков диска.
Сложность: O(N) (линейная деградация).
Для таблицы на 20 ГБ: чтение 2 500 000 страниц.
Время отклика: от 5 до 40 секунд. Сервер парализован!

Поиск через B-Tree индекс

Сбалансированное дерево хранит упорядоченные ключи и физические указатели (TID).

Спуск от корня к листу за 3–4 операции ввода-вывода.
Сложность: O(log N).
Чтение: 3 страницы индекса + 1 страница кучи = 32 КБ!
Время отклика: < 0.05 миллисекунды (ускорение в 50 000 раз).

2. Точечный поиск по первичному и уникальному ключу

Предикат точного равенства

Запрос: WHERE id = 459102 или WHERE contract = 'DOG-2024-98'.

Узел плана выполнения: Index Scan (или Index Only Scan).
Селективность: ровно 1 строка (100% уникальность).
Исключен риск сканирования соседних страниц.

Пример SQL и структуры

CREATE UNIQUE INDEX idx_client_contract 
ON bank_clients (contract_number);

SELECT full_name, status, monthly_income
FROM bank_clients
WHERE contract_number = 'DOG-2024-98412';
-- План: Index Scan using idx_client_contract
-- Execution Time: 0.038 ms

3. Диапазонный поиск: Index Range Scan

Двусвязный список листьев B-Tree

Операторы: BETWEEN, >=, <=, >, <.

Шаг 1: Спуск от корня к левой границе диапазона за (\log N)$.
Шаг 2: Горизонтальное чтение листьев по цепочке указателей.
Шаг 3: Остановка на правой границе без повторного обхода дерева.
Клауза ORDER BY выполняется автоматически без процессорной сортировки!

Пример диапазонного фильтра

SELECT record_id, patient_name, visit_date
FROM medical_records
WHERE visit_date BETWEEN '2024-01-01' 
                     AND '2024-06-30'
ORDER BY visit_date ASC;
-- План: Index Scan using idx_med_date
-- Rows: 450, Filter: none, Sort: not needed

4. Сопоставление с шаблоном: оператор LIKE

Левый префикс: LIKE 'Иван%'

СУБД транслирует предикат в диапазон: col >= 'Иван' AND col < 'Ивао'.

Работает Index Range Scan по B-Tree.
Мгновенный отклик: доли миллисекунды.
Требование: класс varchar_pattern_ops для локалей UTF-8.

Ведущий процент: LIKE '%Иван%'

Первый символ неизвестен! Маршрутизация по B-Tree невозможна.

СУБД переходит в Sequential Scan.
Чтение терабайтов данных с диска.
Решение: триграммные индексы pg_trgm (GIN/GiST) или FTS.

5. Поиск по нескольким полям: Composite Index

Внутреннее устройство составного индекса

Индекс (region, status, income) упорядочивает строки по первому полю, затем по второму внутри равных первых, и по третьему внутри равных первых и вторых.

Что работает (Index Scan):

WHERE region = 'ХМАО'
WHERE region = 'ХМАО' AND status = 'ACTIVE'
WHERE region = 'ХМАО' AND status = 'ACTIVE' AND income > 100k

Что НЕ работает (Seq Scan):

WHERE status = 'ACTIVE' (пропущен префикс!)
WHERE income > 100000 (пропущен префикс!)
WHERE status = 'ACTIVE' AND income > 100000

6. Золотое правило: Равенство вперед, диапазон в конец

ОШИБКА: Диапазон на первом месте

CREATE INDEX idx ON orders (created_at, client_id);

Запрос: WHERE created_at > '2024-01-01' AND client_id = 42

СУБД читает тысячи записей за период, где перемешаны все клиенты.
Поле client_id проверяется в цикле фильтром на лету.
Высокая нагрузка на память и CPU.

ПРАВИЛЬНО: Равенство впереди диапазона

CREATE INDEX idx ON orders (client_id, created_at);

Запрос: WHERE client_id = 42 AND created_at > '2024-01-01'

B-Tree мгновенно локализует ровно ветвь клиента 42.
Внутри этой ветви сразу читается нужный диапазон дат.
Лишние строки чужих клиентов даже не загружаются в память!

7. Комбинированный поиск: Bitmap Index Scan

Когда один составной индекс отсутствует

В таблице есть отдельные индексы: idx_region и idx_status.

Запрос: WHERE region = 'ХМАО' AND status = 'ACTIVE'

СУБД строит битовые карты страниц для каждого индекса в RAM.
Выполняет побитовую операцию AND (пересечение) или OR (объединение).
Затем выполняет Bitmap Heap Scan — считывает с диска только те страницы кучи, где гарантированно есть совпадения.

Узлы в плане EXPLAIN

Bitmap Heap Scan on bank_clients
  Recheck Cond: (region = 'ХМАО' AND status = 'ACTIVE')
  -> BitmapAnd
      -> Bitmap Index Scan on idx_region
      -> Bitmap Index Scan on idx_status

8. Полнотекстовый поиск: Стемминг и векторы

Почему LIKE не годится для текстов?

Не находит словоформы: «база», «базы», «базами».
Засоряется стоп-словами («и», «на», «в», «под»).
Не ранжирует результаты по релевантности.

Механизм to_tsvector и to_tsquery

to_tsvector — нормализует слова и удаляет шум:

to_tsvector('russian', 'Проектирование баз данных')
=> 'баз':2 'дан':3 'проектирован':1

to_tsquery — логическое выражение поиска:

to_tsquery('russian', 'база & проект:*')

Оператор проверки: tsvector @@ tsquery

9. Инвертированный индекс GIN (Generalized Inverted Index)

Архитектура GIN

Ключами B-Tree являются отдельные лексемы (слова), а не вся строка.
Каждая лексема ссылается на список идентификаторов строк (Posting List), содержащих это слово.
При поиске 'база' & 'нормализация' СУБД пересекает два коротких списка идентификаторов.

Синтаксис создания GIN

CREATE INDEX idx_books_fts 
ON books USING gin (
  to_tsvector('russian', 
    title || ' ' || coalesce(annotation, ''))
);

-- Поиск книги:
SELECT title, author_name 
FROM books 
WHERE to_tsvector('russian', title || ' ' || annotation) 
   @@ to_tsquery('russian', 'нормализац:* & реляцион:*');

10. Составление поискового протокола

Инженер баз данных не гадает о скорости, а оформляет поисковый протокол с фиксацией параметров оптимизатора:

Бизнес-сценарий: Какое действие пользователя обслуживается (поиск по договору, фильтрация каталога).
Спецификация предиката: Точный SQL-текст фильтра WHERE.
Используемый индекс: Имя индекса и его тип (Unique B-Tree, Composite, GIN).
Ожидаемый узел плана EXPLAIN: Index Scan, Bitmap Index Scan, Seq Scan.
Время отклика (Execution Time): Реальный замер в мс через EXPLAIN ANALYZE.
Селективность: Соотношение прочитанных строк к возвращенным.

11. Чек-лист проектирования поисковых запросов

Обязательные правила:

Точечный поиск оформлять через уникальные индексы.
В составном индексе равенства ставить ПЕРЕД диапазонами.
Для поиска LIKE 'prefix%' указывать varchar_pattern_ops.
Полнотекстовый поиск строить на tsvector и индексах GIN.
Всегда проверять планы через EXPLAIN (ANALYZE, BUFFERS).

Главные антипаттерны:

Использовать LIKE '%слово%' на миллионных таблицах без GIN-триграмм.
Создавать 10 отдельных индексов вместо одного продуманного составного.
Ставить диапазонную колонку первой в составном индексе.
Считать, что СУБД «сама всё поймет и ускорит без индекса».

12. 4 практических сценария в рабочем листе

Вариант 1. Интернет-банк

Номер договора (Unique B-Tree), маска ФИО ('Иван%'), составной фильтр: Регион + Статус + Доход.

Вариант 2. Каталог библиотеки

Поиск по ISBN, поиск по автору, полнотекстовый поиск по аннотации с GIN-индексом и стеммингом.

Вариант 3. Реестр медицинских карт

Полис ОМС, диапазон дат визитов (Index Range Scan), комбинированный поиск: Отделение + Диагноз (МКБ).

Вариант 4. IT Service Desk

Тикет по ID, префикс темы, очередь инженера: Исполнитель + Статус + Приоритет + Сортировка даты.

13. Критерии оценивания работы (0–4 балла)

Структура оценки:

2 балла: Корректность запросов точечного поиска по ключу и диапазона (Index Range Scan).
1 балл: Поиск по нескольким полям с соблюдением левого префикса и шаблона LIKE/FTS.
1 балл: Полнота поискового протокола, фиксация времени отклика и блок самопроверки.

Финал 3 семестра:

Данная работа подводит итог Темы 3 «Этапы проектирования баз данных».

Оценки за практическое занятие №8 идут в итоговую аттестационную ведомость семестра!

14. Инженерная культура: цена архитектурных ошибок

Тематический интернет-мем: «Exploits of a Mom» (культовый веб-комикс про «Little Bobby Tables», xkcd №327).
Автор: Randall Munroe. Первоисточник: xkcd.com/327. Лицензия: Creative Commons Attribution-NonCommercial 2.5 Generic (CC BY-NC 2.5).
Связь с темой занятия: Проектирование поисковых фильтров по текстовым полям и ключевым идентификаторам требует глубокого понимания архитектуры данных и экранирования параметров. Небрежное составление поисковых запросов приводит либо к зависанию сервера из-за полного Sequential Scan на миллионах строк, либо к катастрофическому взлому через SQL-инъекции в поисковых формах, как в легендарной истории с именем Robert'); DROP TABLE Students;--.