Фундаментальный теоретический конспект: Поиск по одному и нескольким полям

Дисциплина: ОП.08 Основы проектирования баз данных | Тема 3. Этапы проектирования баз данных (§2.2 с.7)

Практическое занятие №8 (Занятие 20, завершение 3 семестра, СИЭУиП)

1. Архитектурная проблема: поиск данных в промышленных базах

В реляционных СУБД (PostgreSQL, Oracle, MySQL, MS SQL Server) таблицы физически хранятся в виде неупорядоченного набора страниц (кучи — Heap). Каждая страница (в PostgreSQL по умолчанию 8 КБ) содержит набор кортежей (строк). При добавлении записи СУБД помещает ее на первую попавшуюся страницу, где есть свободное место. Физический порядок строк никак не связан с их логическим значением.

Когда приложение выполняет запрос с фильтрацией (WHERE column = value), перед оптимизатором встает выбор метода доступа к данным. От этого выбора зависит, ответит ли СУБД за 0.05 миллисекунды или зависнет на десятки секунд при нагрузке.

2. Сравнение стоимости физических операций поиска (Access Methods)

Планировщик запросов СУБД оценивает стоимость (Cost) выполнения различных путей доступа. Основные операторы сканирования представлены ниже:

+----------------------------------------------------------------------------------------------------+ | МЕТОДЫ ДОСТУПА К ДАННЫМ В РЕЛЯЦИОННОЙ СУБД (POSTGRESQL) | +----------------------------------------------------------------------------------------------------+ 1. SEQUENTIAL SCAN (Линейное сканирование кучи): O(N) [Дисковый файл таблицы (Heap)] ---> Читает ВСЕ страницы 8 КБ по порядку ---> Фильтрует строки в CPU * Стоимость: N_pages * seq_page_cost + N_tuples * cpu_tuple_cost * Применимость: Высокая селективность (запрос забирает > 15-20% таблицы) либо отсутствие индекса. 2. B-TREE INDEX SCAN (Прямое точечное индексное чтение): O(log N) [Корень B-Tree] ---> [Внутренний узел] ---> [Листовой узел: TID] ---> Точечное чтение кучи (TID -> Heap) * Стоимость: H * random_page_cost + 1 * random_page_cost * Применимость: Низкая селективность (выборка 1-100 строк из миллионов по ключу/равенству). 3. BITMAP INDEX SCAN + BITMAP HEAP SCAN (Битовое комбинированное чтение) [Индекс 1: Листья] \ /---> Сортировка страниц в памяти (TID Bitmap) ===> Битовые операции (AND / OR) = [Индекс 2: Листья] / \---> Пакетное физическое чтение страниц кучи * Стоимость: Компромисс между случайным и последовательным вводом-выводом. * Применимость: Диапазонный поиск средней селективности (1-5% таблицы) или объединение условий WHERE col1=A AND col2=B. 4. GIN INDEX SCAN (Generalized Inverted Index Scan): Полнотекстовый / JSONB поиск [Запрос: 'база' & 'проект'] ---> B-Tree лексем GIN ---> Списки Posting List ---> Битовое пересечение строк * Применимость: FTS (to_tsvector @@ to_tsquery), поиск элементов в массивах, триграммы pg_trgm. +----------------------------------------------------------------------------------------------------+

Метод доступа	Временная сложность	Характер ввода-вывода (I/O)	Зависимость от объема таблицы	Оптимальный профиль выборки
Sequential Scan (Seq Scan)	$O(N)$	Строго последовательное чтение больших блоков (Sequential I/O, OS readahead)	Линейная (удвоение таблицы удваивает время)	Выборка более 15–25% строк таблицы или маленькие таблицы (< 100 страниц).
B-Tree Index Scan	$O(\log N)$	Случайное чтение страниц (Random I/O: 3–4 страницы дерева + страницы кучи)	Логарифмическая (рост таблицы в 10 раз добавляет лишь 1 уровень дерева)	Точечный поиск по ключу (1 строка) или узкий диапазон (1–50 строк).
Bitmap Index Scan	$O(\log N + K)$	Смешанный: индекс читается по B-Tree, страницы кучи читаются в физическом порядке	Почти не зависит от общего объема при фиксированном размере ответа	Диапазоны средней длины (100–5000 строк) или логические связки `OR` / `AND` между разными индексами.
GIN Index Scan	$O(\sum \log M_i + L)$	Чтение Posting-листов инвертированного индекса и пересечение битовых карт	Зависит от частотности искомых лексем, а не от количества строк в базе	Полнотекстовый поиск (FTS), стемминг, поиск вхождения тегов и триграммных подстрок.

3. Правила проектирования составных индексов под поиск по нескольким полям

3.1. Структура составного B-Tree (Composite Index)

Составной индекс строится по нескольким столбцам: CREATE INDEX idx_name ON table (col1, col2, col3);. Важно понимать, как данные упорядочены внутри дерева:

Кортежи индекса отсортированы строго по col1.
Значения col2 отсортированы только внутри строк с одинаковым значением col1.
Значения col3 отсортированы только внутри строк с одинаковыми значениями col1 и col2.

Золотое правило левого префикса (Left-Prefix Rule):

Индекс (col1, col2, col3) может эффективно использоваться планировщиком для запросов, содержащих в WHERE:

Только col1 (префикс длины 1);
col1 AND col2 (префикс длины 2);
col1 AND col2 AND col3 (полный ключ).

Если в секции WHERE указаны только col2 или col3, индекс НЕ МОЖЕТ быть использован для логарифмического спуска (возможен только Index Full Scan, уступающий прямому Seq Scan).

3.2. Принцип «Равенства вперед, диапазоны в конец» (Equality First, Range Last)

Если поисковый запрос содержит как предикаты точного равенства (=), так и диапазонные условия (<, >, BETWEEN), колонки в составном индексе обязаны располагаться в строгой последовательности:

-- ПРАВИЛЬНО: равенства ставятся первыми, диапазон закрывает индекс
CREATE INDEX idx_orders_client_date ON orders (client_id, status, created_at);

-- Запрос использует индекс на 100% мощности:
SELECT * FROM orders 
WHERE client_id = 1042 
  AND status = 'COMPLETED' 
  AND created_at BETWEEN '2024-01-01' AND '2024-06-30';

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

Если создать индекс (created_at, client_id, status), то СУБД спустится в дерево по дате '2024-01-01' и пойдет сканировать все листовые страницы до '2024-06-30'. На этих страницах перемешаны миллионы разных клиентов и статусов! Поля client_id и status будут проверяться как обычный фильтр на лету (Filter condition), а не как ограничитель спуска B-Tree (Index Cond).

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

В PostgreSQL для строковых колонок B-Tree использует правила сортировки текущей локали (Collation). При локали ru_RU.UTF-8 стандартный B-Tree индекс не может оптимизировать предикат LIKE 'Иван%', потому что порядок сортировки символов в национальной локали зависит от регистра и составных правил языка.

-- Создание индекса со специальным операторным классом для быстрого LIKE по префиксу:
CREATE INDEX idx_clients_name_pfx ON clients (full_name varchar_pattern_ops);

4. Полнотекстовый поиск (Full-Text Search) и инвертированный индекс GIN

Для поиска фраз и слов в текстовых полях (статьи, книги, описания товаров, жалобы пользователей) реляционная СУБД предоставляет инструментарий полнотекстового поиска:

Векторизация текста (to_tsvector):

Функция разбирает текст на слова, удаляет знаки препинания и стоп-слова («в», «на», «и»), применяет стемминг (приведение к нормальной основе) и сохраняет отсортированный вектор лексем с номерами позиций.

SELECT to_tsvector('russian', 
  'Реляционные базы данных и проектирование');
-- Результат: 'баз':2 'дан':3 'проектирован':5 'реляцион':1

Поисковый запрос (to_tsquery):

Преобразует поисковую строку пользователя в логическую комбинацию лексем с поддержкой операторов & (И), | (ИЛИ), ! (НЕ), :* (префикс).

SELECT to_tsquery('russian', 
  'реляцион:* & баз:*');
-- Оператор проверки соответствия: @@
-- vector @@ query -> TRUE / FALSE

Для ускорения FTS-запросов создается GIN (Generalized Inverted Index):

-- Создание функционального GIN-индекса
CREATE INDEX idx_articles_fts ON articles USING gin (
  to_tsvector('russian', title || ' ' || content)
);

5. Контрольные вопросы для самопроверки студентов

Какова теоретическая и практическая сложность поиска по первичному ключу в таблице с B-Tree индексом? Какое количество дисковых страниц считывается при поиске одной записи из 10 000 000 строк?
В чем физическое отличие операции Index Scan от Bitmap Index Scan? Почему при выборке 2 000 строк планировщик предпочитает построить битовую карту страниц в оперативной памяти?
Объясните правило левого префикса в составном B-Tree индексе (A, B, C). Какие из запросов WHERE A = 1, WHERE B = 2, WHERE A = 1 AND B = 2, WHERE B = 2 AND C = 3 смогут использовать данный индекс для быстрого поиска?
Почему запрос WHERE name LIKE '%Петров' не может использовать стандартный B-Tree индекс на колонку name? Какой тип сканирования выберет СУБД?
Какую архитектурную задачу решает стемминг в полнотекстовом поиске? Чем инвертированный индекс GIN фундаментально отличается от дерева B-Tree?
Почему в составном индексе столбцы с условиями точного равенства должны располагаться левее столбцов с диапазонами?