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

1. Реляционная природа порядка и миф о «самосортировке»

Реляционная аксиома Эдгара Кодда

Отношение — это математическое множество кортежей. Порядок элементов в множестве не определен.

Порядок строк на диске не гарантирует порядок выборки.
СУБД имеет право возвращать строки в любом порядке, если не указан ORDER BY.

Когда иллюзия порядка ломается

Параллельное сканирование (Parallel Seq Scan): потоки читают разные страницы одновременно.
Операции UPDATE/DELETE: новые версии строк пишутся на освободившиеся места.
Фоновая очистка (VACUUM): дефрагментация полностью перетасовывает страницы кучи.

2. Многоуровневая сортировка: иерархия полей

Лексикографический каскад

Сортировка выполняется слева направо:

SELECT title, category, rating, price 
FROM products 
ORDER BY category ASC, 
         rating DESC, 
         price ASC;

Сравнение переходит к следующему полю только при равенстве значений в предыдущем.

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

Если несколько строк идентичны по всем полям ORDER BY, их взаимное расположение случайно.

Золотое правило надежности: Всегда завершайте список сортировки первичным ключом (Tie-breaker): ORDER BY category ASC, rating DESC, id ASC.

3. Трехзначная логика: поведение NULL-значений

Различия диалектов по умолчанию

PostgreSQL / Oracle: NULL считается «наибольшим» значением.
ORDER BY col ASC → NULL в конце.
ORDER BY col DESC → NULL в начале!
MySQL / MariaDB: NULL считается «наименьшим» значением.

Явный контроль: NULLS FIRST / NULLS LAST

Спецификация стандарта SQL-99 устраняет двусмысленность:

-- Товары без рейтинга отправляем в конец:
ORDER BY rating DESC NULLS LAST;

-- Срочные авиарейсы без гейта ставим наверх:
ORDER BY departure_time ASC, gate ASC NULLS FIRST;

Гарантирует идентичное поведение во всех промышленных СУБД.

4. Локали и правила упорядочивания символов (Collation)

Ловушка бинарного сопоставления ("C" / POSIX)

Сортирует строки по байтовым кодам UTF-8/ASCII:

Буква «Ё» (U+0401) встает ПЕРЕД буквой «А» (U+0410)!
Слово «Ёлка» окажется в начале телефонного справочника, до «Абакана».
Все заглавные буквы выводятся отдельно от строчных.

Естественные локали (ICU / ru_RU.UTF-8)

Учитывают национальные правила алфавита:

SELECT last_name, first_name 
FROM students 
ORDER BY last_name COLLATE "ru_RU" ASC;

Буква «Ё» корректно упорядочивается рядом с «Е», регистронезависимое первичное сравнение.

5. Физические алгоритмы: Сортировка в ОЗУ (work_mem)

Выделение рабочей памяти

Параметр work_mem (PostgreSQL) определяет объем памяти для одной операции сортировки или хеширования.

Применяется индивидуально к каждому узлу плана запроса!
При 100 одновременных клиентах с work_mem = 64MB может потребоваться до 6.4 ГБ RAM.

In-Memory Quicksort и Top-N Heapsort

Quicksort: Быстрая сортировка в памяти массива указателей на кортежи.
Top-N Heapsort: При запросах вида ORDER BY ... LIMIT k память выделяется только под кучу из $ элементов. Сложность: (N \log k)$ вместо (N \log N)$.

6. Алгоритм External Merge Sort: сброс на диск

Когда данных больше, чем work_mem

СУБД переключается на внешнюю сортировку слиянием:

Run Generation: Порция данных считывается в память, сортируется и сбрасывается во временный файл серий (Run 1, Run 2...).
Multi-way Merge: Буферы серий одновременно сливаются через турнирное дерево (Min-Heap).

Цена сброса на диск (Disk Spill)

План запроса показывает:

Sort Method: external merge  Disk: 28416kB

Задержка (latency) запроса подскакивает с миллисекунд до секунд из-за дискового ввода-вывода (I/O Bottleneck).

7. Диагностика сортировки через EXPLAIN ANALYZE

Пример идеального плана (In-Memory)

->  Sort (cost=145.20..148.50 rows=1320)
      Sort Key: rating DESC, price ASC
      Sort Method: quicksort  Memory: 94kB

Все данные отсортированы в оперативной памяти за микросекунды.

Пример катастрофического плана (Disk Spill)

->  Sort (cost=85420..88120 rows=540000)
      Sort Key: created_at DESC
      Sort Method: external merge  Disk: 42100kB
      Buffers: shared hit=4210 read=18400, 
               temp read=5260 written=5260

Десятки мегабайт временных файлов перегружают дисковую подсистему сервера!

8. Постраничная навигация: Почему OFFSET убивает СУБД

Иллюзия простоты: LIMIT n OFFSET m

SELECT * FROM ledger 
ORDER BY id 
LIMIT 20 OFFSET 500000;

СУБД вынуждена:

Прочитать и отсортировать все 500 020 строк.
Перемотать и выбросить первые 500 000 строк.
Вернуть 20 оставшихся.

Сложность (N)$ — запрос падает по тайм-ауту на далеких страницах!

Аномалия сдвига данных (Page Drift)

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

9. Архитектурный стандарт: Курсорная пагинация (Keyset)

Принцип курсора (Seek Method)

Вместо смещения запоминаем кортеж последней увиденной записи:

SELECT id, reg_date, amount 
FROM contracts 
WHERE (reg_date, id) < (, ) 
ORDER BY reg_date DESC, id DESC 
LIMIT 20;

Поиск стартовой точки по составному B-Tree индексу выполняется за (\log N)$.

Преимущества Keyset пагинации

Константная скорость: 1-я и 1000-я страница открываются за одинаковые 2 мс.
Отсутствие дубликатов: вставка новых записей не сбивает курсор.
Нулевой сброс на диск: сортировка поддержана индексом.

10. Фильтрация WHERE и предикаты поиска (SARGable)

Антипаттерн: Non-SARGable выражения

Вызовы функций к колонкам ломают использование индексов:

-- ПЛОХО: полный Seq Scan!
WHERE EXTRACT(YEAR FROM doc_date) = 2026;
WHERE lower(username) = 'ivan';
WHERE amount + 100 > 5000;

СУБД обязана вычислить функцию для каждой из миллионов строк таблицы.

Паттерн: SARGable диапазоны

Оставляйте колонку чистой для прямого спуска по B-Tree:

-- ОТЛИЧНО: быстрый Index Range Scan!
WHERE doc_date >= '2026-01-01' 
  AND doc_date < '2027-01-01';
WHERE amount > 4900;

11. Золотое правило индексов: ESR (Equality, Sort, Range)

Оптимизация запроса «WHERE + ORDER BY»

SELECT * FROM tickets 
WHERE status = 'OPEN' 
  AND department_id = 5 
  AND priority > 3 
ORDER BY created_at DESC 
LIMIT 10;

Идеальный порядок колонок в B-Tree

E (Equality): status, department_id (точные равенства первыми).
S (Sort): created_at DESC (устраняет отдельный узел Sort в плане).
R (Range): priority (диапазонная фильтрация).

Результат: мгновенный Index Scan без выделения памяти на сортировку!

12. Текстовая фильтрация: Семантика LIKE и индексы

Префиксный поиск (B-Tree совместимый)

WHERE last_name LIKE 'Иван%';

Превращается в диапазон: last_name >= 'Иван' AND last_name < 'Ивао'. Полностью поддерживается B-Tree индексом!

Поиск по подстроке и суффиксу

WHERE last_name LIKE '%иванов%';

Символ % в начале отключает B-Tree. Требуется либо Seq Scan, либо специализированный триграммный индекс (GIN/GiST с расширением pg_trgm).

13. Инженерный чек-лист архитектора запросов

Что ОБЯЗАТЕЛЬНО нужно внедрять:

Всегда указывать ORDER BY, если порядок критичен для бизнес-логики.
Явно прописывать NULLS FIRST / NULLS LAST при сортировке по убыванию.
Добавлять первичный ключ в конец сортировки для детерминизма.
Заменять OFFSET на Keyset-пагинацию в нагруженных интерфейсах.
Проверять локаль Collation для кириллических справочников.

Чего КАТЕГОРИЧЕСКИ НЕЛЬЗЯ допускать:

Сортировать миллионные выборки без поддерживающего индекса.
Использовать глубокие смещения OFFSET 100000.
Оборачивать столбцы в функции внутри условия WHERE.
Игнорировать план external merge Disk в EXPLAIN.

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).
Связь с темой занятия: Проектирование фильтрации и сортировки кортежей требует безупречной инженерной дисциплины: от корректного обезвреживания пользовательского ввода до защиты СУБД от катастрофических сбросов сортировки на диск (external merge Disk) и деградации серверов на тяжелых пагинациях с миллионными OFFSET.