БД:Теория:Глава 6

Глава 6: Индексы и Выполнение Запросов

В предыдущих главах мы научились создавать таблицы, наполнять их данными и извлекать эти данные с помощью SQL-запросов. Теперь разберемся, как СУБД выполняет эти запросы “под капотом” и как можно ускорить их выполнение с помощью индексов. Эта глава основана на материалах Лекций 6: “Индексы. Выполнение запросов” и Лекции 7: “Выполнение запросов”.

Часть 1: Повышение Производительности Запросов

Когда данных в таблицах становится много (тысячи, миллионы строк), даже простые запросы могут выполняться долго. Почему? Потому что в самом простом случае СУБД приходится последовательно просматривать всю таблицу, чтобы найти нужные строки (это называется полное сканирование таблицы или Sequential Scan).

Способы повышения производительности:

1. Грамотное проектирование модели данных: Это основа. Если модель данных изначально плохо спроектирована (например, ненормализована, что приводит к избыточности, или наоборот, излишне нормализована, что требует множества сложных соединений для простых задач), то оптимизировать запросы будет очень сложно.
2. Использование индексов: Создание дополнительных структур данных, которые позволяют СУБД быстро находить нужные строки по значениям в определенных столбцах, не просматривая всю таблицу. (Основная тема этой главы).
3. Оптимизация запросов: Переписывание SQL-запросов так, чтобы они были более понятны оптимизатору СУБД и могли быть выполнены более эффективно (например, избегая ненужных соединений или используя EXISTS вместо IN в некоторых случаях).
4. Настройка физических параметров СУБД: Оптимизация конфигурации сервера PostgreSQL (выделение памяти, настройка параллелизма, параметры ввода-вывода и т.д.).

Мы сосредоточимся на индексах и понимании выполнения запросов.

Часть 2: Индексы

Что такое Индекс?

Представьте себе предметный указатель в конце большой книги. Вместо того чтобы листать всю книгу в поисках нужного термина, вы смотрите в указатель, находите термин и видите номера страниц, где он встречается.

Индекс SQL работает похожим образом:

• Это отдельная структура данных (обычно хранящаяся в отдельном файле), связанная с таблицей.
• Он содержит копии значений из одного или нескольких столбцов таблицы.
• Эти значения в индексе упорядочены определенным образом (например, по алфавиту для строк, по возрастанию для чисел, или организованы в специфическую структуру данных типа хеш-таблицы).
• Каждое значение в индексе имеет указатель (ссылку, адрес, TID - Tuple Identifier) на те строки в основной таблице, где это значение встречается.

Как индекс помогает?

Рассмотрим таблицу STUDENT:

StudID	GroupID	Name
14	51	Ivan Petrov
23	53	Vladimir Ivanov
18	54	Eugene Serov
13	55	Gennady Surikov
25	56	Nikolay Petrov
25	58	Svetlana Ivanova
25	59	Antony Fedorov
18	63	Petr Menchikov
27	67	Gennady Klokov
23	69	Serge Vidov
18	72	Roman Klever
13	73	Pavel Borisov

И запрос:

SELECT * FROM STUDENT WHERE StudID = 18;

• Без индекса: СУБД читает каждую строку таблицы STUDENT и сравнивает значение в колонке StudID с числом 18. Если таблица большая (миллионы строк), это займет много времени, так как СУБД должна прочитать все данные с диска в память и проверить каждую строку.
• С индексом по StudID:
  1. СУБД обращается к структуре индекса по StudID.
  2. Если индекс, например, B-дерево (значения отсортированы), СУБД быстро находит значение 18 (например, используя бинарный поиск или навигацию по дереву).
  3. Из индекса СУБД получает указатели (TID) на строки в основной таблице, где StudID = 18.
  4. СУБД читает только эти конкретные строки из основной таблицы, используя полученные указатели. Это значительно быстрее, чем читать всю таблицу.

Пример (слайды 10-17, упрощенная иллюстрация):

Допустим, у нас есть упорядоченный список значений StudID (это и есть наш “игрушечный” индекс) и стрелки, указывающие на строки в основной таблице.

Индекс (упорядоченный StudID)	Таблица STUDENT (StudID, GroupID, Name)
13 →	14, 51, Ivan Petrov
13 →	23, 53, Vladimir Ivanov
14 →	18, 54, Eugene Serov <– Нужная строка
18 →	13, 55, Gennady Surikov
18 →	25, 56, Nikolay Petrov
18 →	25, 58, Svetlana Ivanova
23 →	25, 59, Antony Fedorov
23 →	18, 63, Petr Menchikov <– Нужная строка
25 →	27, 67, Gennady Klokov
25 →	23, 69, Serge Vidov
25 →	18, 72, Roman Klever <– Нужная строка
27 →	13, 73, Pavel Borisov

1. Запрос: SELECT * FROM STUDENT WHERE StudID = 18;
2. СУБД смотрит в индекс.
3. Поскольку индекс отсортирован (в нашем примере это простой список, но представьте более сложную структуру), СУБД быстро находит первое вхождение 18.
4. Берет указатель и читает строку 18, 54, Eugene Serov.
5. Переходит к следующему значению 18 в индексе.
6. Берет указатель и читает строку 18, 63, Petr Menchikov.
7. Переходит к следующему значению 18 в индексе.
8. Берет указатель и читает строку 18, 72, Roman Klever.
9. Следующее значение в индексе уже 23 (или больше 18). Поиск завершен.

Вместо сканирования всех 12 строк таблицы, мы быстро нашли 3 нужные строки через индекс.

Важные моменты:

• Индексы работают неявно: Вам не нужно указывать в SELECT-запросе, какой индекс использовать. Оптимизатор СУБД сам решает, использовать ли индекс и какой именно, на основе статистики данных и стоимости выполнения разных планов.
• Иногда СУБД может не использовать индекс, даже если он есть. Например, если запрос выбирает очень большую часть таблицы (проще прочитать всю таблицу), или если условия в WHERE таковы, что индекс неприменим (например, функция над индексированным столбцом WHERE upper(StudName) = 'ИВАНОВ').

Когда Индексы Полезны?

Индексы ускоряют операции, включающие:

• Поиск строк по условиям (WHERE): Особенно для условий равенства (=), диапазонных запросов (>, <, BETWEEN) по индексированному столбцу.
• Соединения таблиц (JOIN): Индексы по столбцам, участвующим в условии ON, значительно ускоряют поиск совпадающих строк в соединяемых таблицах. Первичные и уникальные ключи автоматически индексируются в PostgreSQL, что ускоряет соединения по ним.
• Поиск минимального/максимального значения (MIN(), MAX()): Если столбец индексирован (например, B-деревом), СУБД может просто взять первое/последнее значение из индекса, не сканируя таблицу.
• Сортировку (ORDER BY): Если порядок сортировки совпадает с порядком индекса (или обратен ему, и индекс это поддерживает), СУБД может избежать фактической сортировки данных, просто прочитав строки в порядке индекса.
• Группировку (GROUP BY): Индексы могут помочь СУБД быстрее найти строки, относящиеся к одной группе.

Недостатки Индексов:

1. Занимают место на диске и в памяти: Индекс — это дополнительная структура данных. Чем больше индексов, тем больше места они занимают.
2. Замедляют операции записи (INSERT, UPDATE, DELETE): При изменении данных в индексированном столбце или добавлении/удалении строки СУБД должна обновить не только саму таблицу, но и все связанные с ней индексы. Это добавляет накладные расходы. Чем больше индексов на таблице, тем медленнее будут операции записи.
   • Пример (слайд 23-24): DELETE FROM STUDENT WHERE GroupID = 54; Если по GroupID есть индекс, то СУБД должна не только удалить строку из таблицы STUDENT, но и удалить соответствующие записи из индекса по GroupID, а также, возможно, из индекса по StudID (если StudID был ключом этого индекса и строка удаляется).
3. Неэффективны на маленьких таблицах: Если таблица настолько мала, что целиком помещается в несколько блоков памяти, СУБД прочитает ее полностью быстрее, чем будет обращаться к индексу.
4. Неэффективны при выборке больших объемов данных: Если запрос выбирает значительную часть таблицы (например, WHERE column > 0, где почти все значения больше нуля), СУБД, скорее всего, решит, что проще прочитать всю таблицу последовательно (Seq Scan), чем много раз обращаться к индексу и затем к разным частям таблицы за строками (Index Scan + много случайных чтений с диска, что медленнее последовательного).

Стратегии Применения Индексов:

• Анализируйте запросы: Какие столбцы часто используются в WHERE и JOIN? Какие операции преобладают — чтение или запись?
• Индексируйте столбцы в WHERE: Особенно те, по которым идет поиск на равенство или по диапазону и которые обладают хорошей селективностью (т.е. по значению в этом столбце можно отобрать небольшую долю строк таблицы). Индексировать столбец “пол” (М/Ж), где всего два значения, обычно бессмысленно, так как каждое значение выбирает примерно половину таблицы.
• Индексируйте столбцы внешних ключей: Это критически важно для ускорения JOIN. PostgreSQL не создает их автоматически для внешних ключей (в отличие от первичных/уникальных), поэтому это нужно делать вручную.
• Индексируйте столбцы в ORDER BY и GROUP BY: Если часто нужна сортировка или группировка по определенному столбцу.
• Используйте составные индексы: Если часто ищете по комбинации столбцов (WHERE col1 = ? AND col2 = ?), создайте индекс по (col1, col2). Порядок столбцов в составном индексе важен! Индекс по (col1, col2) может использоваться для запросов по col1 и для запросов по col1 И col2, но не для запросов только по col2.
• Не создавайте лишних индексов: Каждый индекс замедляет запись. Регулярно проверяйте и удаляйте неиспользуемые индексы.
• Первичные и уникальные ключи индексируются автоматически в PostgreSQL (с помощью B-Tree индекса).

Создание Индексов (CREATE INDEX)

CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ IF NOT EXISTS ] имя_индекса
ON имя_таблицы [ USING метод ]
( { имя_колонки | ( выражение ) } [ COLLATE имя_сортировки ] [ класс_операторов ] [ ASC | DESC ] [ NULLS { FIRST | LAST } ] [, ...] )
[ WITH ( параметр_хранения = значение [, ... ] ) ]
[ TABLESPACE имя_табличного_пространства ]
[ WHERE предикат ]; -- Частичный индекс

Полный синтаксис сложнее, здесь приведены основные части.

• UNIQUE: Создает уникальный индекс.
• CONCURRENTLY: (PostgreSQL) Позволяет создать индекс без длительной блокировки операций записи в таблицу.
• IF NOT EXISTS: Не выдавать ошибку, если индекс с таким именем уже существует.
• имя_индекса: Имя для вашего индекса.
• имя_таблицы: Таблица, для которой создается индекс.
• USING метод: Указывает тип индекса (btree, hash, gist, gin и др.). По умолчанию в PostgreSQL это btree.
• ( имя_колонки | ( выражение ) ... ): Список столбцов или выражений, по которым строится индекс.
• ASC | DESC: Порядок сортировки (для B-Tree).
• NULLS FIRST | NULLS LAST: Где размещать NULL-значения.
• WHERE предикат: Создает частичный индекс. Индексируются только строки, удовлетворяющие предикату. Полезно, если часто ищутся строки с определенным значением в одном столбце, а по другому нужно индексировать только подмножество.

Примеры:

-- Простой B-Tree индекс по одной колонке
CREATE INDEX idx_student_groupid ON student (GroupID);

-- Составной B-Tree индекс по двум колонкам
CREATE INDEX idx_student_surname_name ON student (Surname, Name);

-- Индекс по выражению (по фамилии в нижнем регистре)
CREATE INDEX idx_student_surname_lower ON student (lower(Surname));

-- Хеш-индекс (только для оператора равенства '=')
CREATE INDEX idx_student_name_hash ON student USING hash (Name);

-- Пример из слайда 29 (B-Tree по двум колонкам)
CREATE INDEX idx_example ON table_name USING btree (column1, column2);

Часть 3: Типы Индексов

PostgreSQL поддерживает несколько типов индексов, оптимизированных для разных задач.

1. B-дерево (B-Tree):
   • Используется по умолчанию (USING btree).
   • Структура: Сбалансированное, многоуровневое дерево.
     • Листовые узлы: Содержат индексируемые значения (ключи) и указатели (TID - Tuple Identifier, адрес строки на диске) на строки таблицы. Ключи в листовых узлах отсортированы. Листовые узлы связаны между собой для быстрого последовательного прохода (полезно для диапазонных запросов).
     • Внутренние узлы (включая корневой): Содержат “разделители” (ключи) и ссылки на дочерние узлы. Помогают быстро сузить область поиска.
   • Преимущества: Очень универсальный. Эффективен для:
     • Поиска по равенству (=).
     • Диапазонных запросов (>, <, BETWEEN, LIKE 'abc%' (поиск по префиксу)).
     • Сортировки (ORDER BY).
     • Поиска NULL (IS NULL, IS NOT NULL).
     • Работы с MIN() и MAX().
   • Пример поиска (StudID = 85, слайды 36-41):
     1. Запрос: SELECT * FROM STUDENT WHERE StudID = 85;
     2. Начинаем с корневого узла (например, [3, 30, 63]).
     3. 85 > 63, идем по правой ветке к узлу (например, [63, 76, 88]).
     4. 76 < 85 <= 88, идем по ветке, соответствующей диапазону (88), к листовому узлу (например, содержащему ключи [76(tid), 85(tid)]).
     5. В листовом узле находим ключ 85 и соответствующий tid.
     6. По tid читаем строку из таблицы.
   • Пример диапазонного поиска (StudID >= 85, слайды 42-43):
     1. Аналогично находим первый ключ 85.
     2. Далее, благодаря связям между листовыми узлами, последовательно читаем следующие листовые узлы ([88(tid), 95(tid)] и т.д.), пока условие выполняется.
2. Хеш-индекс (Hash):
   • Структура: Основан на хеш-таблице. Для индексируемого значения вычисляется хеш-код, который используется как индекс в массиве “корзин” (buckets). Каждая корзина содержит указатели на строки таблицы, чьи индексируемые значения дали этот хеш-код.
   • Пример (слайды 46-49):
     • Значения: (23, 2), (34, 2), (34543, 4), (234, 4), (2355, 5)
     • Хеш-функция Hash_Function(val1, val2) дает, например:
       • Hash_Function(23, 2) -> ...2345 (хэш значение)
       • Hash_Function(34, 2) -> ...3423
       • Hash_Function(34543, 4) -> ...2345 (коллизия с первым!)
     • Хэш-индекс:
       • Корзина 2345: tid1 (для (23,2)), tid3 (для (34543,4))
       • Корзина 3423: tid2 (для (34,2))
     • При поиске, например, WHERE StudID=23 AND GroupID=2:
       1. Вычисляется Hash_Function(23, 2) -> ...2345.
       2. Смотрим в корзину 2345.
       3. Для каждой строки (tid1, tid3) в этой корзине проверяем точное совпадение исходных значений StudID и GroupID (т.к. в корзине могут быть коллизии).
   • Преимущества: Очень быстрый для операций поиска по точному равенству (=).
   • Недостатки:
     • Бесполезен для диапазонных запросов, сортировки, поиска по префиксу.
     • Менее эффективен при большом количестве коллизий (когда много разных значений попадают в одну корзину).
   • Когда использовать: Только если запросы к столбцу — это исключительно проверки на точное равенство (WHERE attr = 1), и другие операции не нужны. B-Tree обычно является более гибким выбором.
3. GiST (Generalized Search Tree - Обобщенное дерево поиска):
   • Гибкая инфраструктура для создания индексов для сложных типов данных (геометрические данные, диапазоны, некоторые виды текстового поиска).
   • Позволяет индексировать операции типа “пересекается”, “содержит”.
   • Используется расширениями, такими как PostGIS (для геоданных) и pg_trgm (для поиска по похожести строк - триграммам).
4. GIN (Generalized Inverted Index - Обобщенный инвертированный индекс):
   • Оптимизирован для индексации составных значений, где одно значение в столбце может содержать несколько “ключей” (например, массив слов в документе, элементы массива jsonb, элементы hstore).
   • Хранит карту “ключ из составного значения -> список строк, где этот ключ встречается”.
   • Преимущества: Очень эффективен для поиска строк, содержащих определенные значения внутри составного типа (например, найти все документы, содержащие слово ‘postgresql’).
   • Используется для полнотекстового поиска, индексации jsonb (операторы ?, ?|, ?&), hstore, массивов (операторы @>, <@, &&).

Часть 4: Выполнение Запросов и Оптимизация

(Этот раздел повторяет и немного расширяет информацию из предыдущей версии методички, основываясь на слайдах Лекции 7).

Декларативность SQL: Пользователь указывает, что он хочет получить, а не как это сделать. СУБД сама решает, как выполнить запрос.

Этапы выполнения запроса в PostgreSQL:

1. Разбор запроса (Parser): SQL-текст преобразуется во внутреннее представление — дерево разбора (parse tree). Проверяется синтаксис.
2. Преобразование запроса (Rewriter/Analyzer): Дерево разбора анализируется, преобразуется с учетом правил и представлений (например, запрос к представлению заменяется на запрос к базовым таблицам). Семантическая проверка. Результат — дерево запроса (query tree).
3. Планировщик/Оптимизатор (Planner/Optimizer):
   • Генерирует множество возможных планов выполнения для дерева запроса, используя:
     • Законы реляционной алгебры для эквивалентных преобразований.
     • Информацию об имеющихся индексах.
     • Доступные алгоритмы выполнения операций (Seq Scan, Index Scan, Nested Loop Join, Hash Join, Merge Join, Sort, Aggregate и т.д.).
   • Оценивает стоимость каждого плана на основе статистики таблиц (количество строк, распределение значений, размер таблицы, кардинальность и т.д.) и стоимости операций (I/O, CPU).
   • Выбирает план с минимальной оцененной стоимостью.
   • Результат — план выполнения (execution plan).
4. Выполнение плана (Executor): План выполнения передается исполнителю, который шаг за шагом выполняет операции плана и возвращает результат.

План выполнения запроса:

• Это, по сути, программа, которую СУБД строит для ответа на SQL-запрос.
• Для одного SQL-запроса может существовать несколько эквивалентных планов, но с разной стоимостью выполнения.
• Критерий выбора плана: Оценочная стоимость (число обменов с диском, время обмена, загрузка CPU).

Оптимизация на основе Реляционной Алгебры:

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

• Пример (из слайдов 16-22 Лекции 7): sql SELECT * FROM STUDENTS ST JOIN EXAMS EXAM ON ST.ID = EXAM.STUD_ID WHERE ST.GROUP = '3100' AND ST.ID >= 150000;
  • План 1 (сначала JOIN, потом WHERE): σ(ST.GROUP='3100' ∧ ST.ID>=150000) (STUDENTS ⋈(ST.ID=EXAM.STUD_ID) EXAMS) Представление в виде дерева: сначала соединение, потом две операции выборки.
  • План 2 (сначала WHERE для STUDENTS, потом JOIN): (σ(ST.GROUP='3100' ∧ ST.ID>=150000) (STUDENTS)) ⋈(ST.ID=EXAM.STUD_ID) EXAMS Представление в виде дерева: сначала две операции выборки для STUDENTS, потом результат соединяется с EXAMS. Этот план обычно эффективнее, так как соединяется меньший объем данных.

Материализация vs Конвейерная Обработка (Pipelining):

• Материализация: Результат промежуточной операции полностью вычисляется и сохраняется во временную структуру, затем передается следующей операции.
• Конвейерная обработка: Как только первая операция производит первую строку результата, эта строка немедленно передается на вход следующей операции. Экономит ресурсы и время. Оптимизатор старается использовать конвейер. Левосторонние деревья планов хорошо подходят для конвейерной обработки (результат предыдущего соединения сразу идет на вход следующего).

Советы по построению (оптимизации) планов (что пытается делать оптимизатор):

• Использовать конвейерную обработку (левосторонние планы, избегать блокирующих операций типа полной сортировки без необходимости).
• Делать выборку как можно раньше.
• Делать проекцию как можно раньше.
• Грамотно планировать соединения (порядок, алгоритмы).
• Цель: Уменьшение размеров промежуточных данных => уменьшение числа операций чтения/записи во внешнюю память.

Влияние индексов на планы: Индексы могут кардинально изменить выбранный план, позволяя заменить полное сканирование таблицы (Seq Scan) на более эффективное индексное сканирование (Index Scan) или улучшить производительность соединений (Index Nested Loop Join).

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

Часть 5: Алгоритмы Выполнения Соединений (JOIN)

(Детальное описание алгоритмов было в предыдущей версии, здесь краткое повторение с акцентом на примеры из Лекции 7)

1. Nested Loop Join (Соединение вложенными циклами):
   • R ⋈_condition S (R - внешнее, S - внутреннее отношение)
   • Простой: Для каждой строки r из R, просматриваем все строки s из S. Если condition(r, s) истинно, добавляем r + s в результат.
     • Пример (слайды 54-70 Лекции 7): Таблицы Groups и Students. Для первой группы из Groups перебираются все студенты из Students. Потом для второй группы из Groups снова перебираются все студенты из Students, и так далее.
   • Block Nested Loop: Внешнее отношение R читается блоками (несколько страниц). Для каждого блока R, сканируется вся внутренняя таблица S. Уменьшает число полных сканирований S.
     • Пример (слайды 88-91 Лекции 7): Если в буфере помещается блок из 4 страниц Groups, то для этого блока один раз сканируется вся таблица Students. Затем загружается следующий блок Groups и снова сканируется вся Students. Эффективнее, если внешняя таблица меньше внутренней.
   • Index Nested Loop: Если по столбцу соединения во внутренней таблице S есть индекс. Для каждой строки r из R выполняется быстрый поиск по индексу в S.
2. Sort-Merge Join (Соединение слиянием):
   • Обе таблицы (R и S) сортируются по атрибутам соединения.
   • Затем отсортированные таблицы “сливаются” (как при merge sort), одновременно проходя по обеим и комбинируя строки с совпадающими значениями атрибутов соединения.
   • Пример (слайды 93-99 Лекции 7): Таблицы Groups и Students (предполагается, что они уже отсортированы по GroupID). Указатели одновременно движутся по обеим таблицам.

Часть 6: Просмотр Плана Выполнения в PostgreSQL

Команда EXPLAIN показывает план, который СУБД выбрала для выполнения запроса.

• EXPLAIN <SQL_ЗАПРОС>;: Показывает план выполнения, но не выполняет сам запрос.
  • Вывод (слайд 103-104): QUERY PLAN --------------------------------------------------------------------- Seq Scan on Students (cost=0.00..309.00 rows=900 width=170)
    • Seq Scan on Students: Операция — последовательное сканирование таблицы Students.
    • cost=0.00..309.00: Оценочная стоимость (начальная..общая).
    • rows=900: Оценочное количество строк, которое вернет эта операция.
    • width=170: Оценочный средний размер строки.
  • Вывод с индексом (слайд 105): QUERY PLAN ---------------------------------------------------------------------------------------- Index Scan using students_studid_pkey on students (cost=0.32..8.34 rows=1 width=150) Index Cond: (StudId = 942)
    • Index Scan using students_studid_pkey on students: Используется индекс students_studid_pkey.
    • Index Cond: (StudId = 942): Условие, применяемое к индексу.
• EXPLAIN ANALYZE <SQL_ЗАПРОС>;: Выполняет запрос и показывает реальный план выполнения с фактическим временем выполнения каждой операции и количеством строк.

  • Вывод (примерный, на основе слайда 106):

    EXPLAIN ANALYZE SELECT * FROM students WHERE StudID = 942;
    
    QUERY PLAN
    ------------------------------------------------------------------------------------------------------------------------------------
     Index Scan using students_studid_pkey on students  (cost=0.29..8.30 rows=1 width=153) (actual time=0.020..0.021 rows=1 loops=1)
       Index Cond: (studid = 942)
     Planning Time: 0.075 ms
     Execution Time: 0.035 ms
    (4 rows)
    

    • (actual time=0.020..0.021 rows=1 loops=1): Фактическое время (начало..конец), фактическое число строк, сколько раз узел выполнялся.
    • Planning Time: Время, затраченное на планирование/оптимизацию.
    • Execution Time: Общее время выполнения запроса (включая планирование, если не используется SET anl_separate_planning_info = on; или аналогичная опция).

Анализ вывода EXPLAIN (особенно EXPLAIN ANALYZE) помогает понять, почему запрос выполняется медленно, используются ли индексы, корректны ли оценки оптимизатора, и какие части запроса являются “бутылочным горлышком”.