Методическое руководство преподавателя

1. Детальный тайминг занятия (основной 80 минут и сокращенный 60 минут)

Занятие 20 завершает учебную программу 3-го семестра. Главная цель — закрепить умение проектировать эффективные поисковые запросы по одному и нескольким полям, сопоставлять физические механизмы поиска СУБД с предикатами запроса и составлять строгий поисковый протокол с анализом времени отклика и планов выполнения.

2. Архитектура поисковых механизмов реляционных СУБД

2.1. Точечный поиск по ключу: Index Scan и сложность $O(\log N)$

Точечный поиск по равенству (WHERE primary_key = constant) опирается на классическую древовидную структуру B-Tree (Balanced Tree). В таблице без индекса поиск требует Sequential Scan — чтения всех $M$ дисковых страниц (блоков по 8 КБ в PostgreSQL), что приводит к вычислительной сложности $O(N)$ и катастрофической деградации дискового ввода-вывода (I/O Bottleneck).

2.2. Диапазонный поиск: Index Range Scan и горизонтальные связи листьев

Диапазонные предикаты (WHERE column BETWEEN A AND B, >=, <=) эксплуатируют фундаментальное свойство B-Tree: все листовые узлы связаны между собой двусвязным списком в строго отсортированном порядке.

• Фаза 1 (Спуск от корня): Алгоритм за $O(\log N)$ шагов находит листовой блок, содержащий левую границу диапазона $A$.
• Фаза 2 (Листовой проход): СУБД больше не возвращается к корневому или промежуточным узлам. Чтение кортежей выполняется последовательно по указателям листьев вперед до достижения границы $B$.
• Сортировка: Клауза ORDER BY column выполняется без накладных расходов на процессорную сортировку (Elimination of Sort Node), поскольку данные уже поступают в идеальном физическом порядке.

2.3. Сопоставление с шаблоном: оператор LIKE и правило левого префикса

Один из самых коварных разделов проектирования запросов — поиск по строковым маскам:

2.4. Полнотекстовый поиск (FTS): стемминг, стоп-слова и инвертированный индекс GIN

Когда требуется искать слова и фразы в неструктурированных текстах (аннотации книг, описания товаров, история обращений), оператор LIKE терпит крах не только по скорости, но и по смыслу (он не учитывает окончания, падежи и предлоги).

Полнотекстовый поиск в PostgreSQL базируется на трех компонентах:

1. Стемминг (Stemming): Морфологический редуктор (Snowball) отсекает окончания и суффиксы, приводя слова к единой нормальной лексеме (например, «базами», «баз», «базе» $\to$ лексема 'баз').
2. Словари стоп-слов: Фильтрация частотного языкового шума (предлоги «и», «в», «на», союзы, местоимения), который не несет смысловой нагрузки при поиске.
3. Типы данных tsvector и tsquery: Документ конвертируется в отсортированный список нормализованных лексем с их позициями (to_tsvector('russian', text)), а поисковый запрос — в булево выражение лексем (to_tsquery('russian', 'база & проект')). Сопоставление выполняется бинарным оператором @@.
4. Инвертированный индекс GIN (Generalized Inverted Index): В B-Tree ключ — это целая колонка, указывающая на строку. В GIN ключами B-Tree являются отдельные лексемы (слова), а в листьях хранятся отсортированные списки идентификаторов всех строк (Posting Lists), содержащих это слово. Поиск любого сочетания слов выполняется за доли миллисекунды через пересечение битовых карт (Bitmap Index Scan).

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

Поисковый протокол — это профессиональный отчет инженера баз данных, фиксирующий поведение оптимизатора запросов при различных формах фильтрации. Протокол должен содержать:

• Формулировку бизнес-задачи и точный SQL-предикат секции WHERE.
• Наличие и спецификацию покрывающего индекса (B-Tree составной, Unique, GIN, Partial).
• Ожидаемый узел плана исполнения EXPLAIN (Seq Scan, Index Scan, Index Only Scan, Bitmap Index Scan, Bitmap Heap Scan).
• Метрики производительности: расчетная стоимость (Startup Cost / Total Cost) и реальное время отклика в миллисекундах (Execution Time).
• Анализ селективности: сколько строк отсекается на уровне индекса и сколько строк реально возвращается клиенту.

4. Типовые ошибки студентов и педагогические приемы устранения