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

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

1. Дидактический регламент и детальный тайминг занятия

Дисциплина «ОП.08 Основы проектирования баз данных». Практическое занятие рассчитано на 2 академических часа. Ниже представлены два взаимосогласованных сценария реализации: основной регламент (80 минут) и сокращенный регламент (60 минут).

2. Теоретико-методический фундамент сортировки и фильтрации

2.1. Многоуровневая сортировка кортежей (Multi-Column ORDER BY)

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

Многоуровневая сортировка выполняется слева направо по принципу лексикографической иерархии:

SELECT product_id, category_id, rating, price 
FROM products 
WHERE is_available = TRUE 
ORDER BY category_id ASC, rating DESC, price ASC;

СУБД сначала группирует строки по первому критерию (category_id). Если значения первого критерия совпадают (коллизия), сравнение переходит ко второму полю (rating). Если совпадают и они — к третьему полю (price). Если после всех критериев остаются дубликаты, а первичный ключ не включен в ORDER BY, результирующий порядок строк является неустойчивым (non-deterministic).

2.2. Трехзначная логика и поведение NULL-значений (NULLS FIRST / NULLS LAST)

В реляционной модели значение NULL обозначает отсутствие данных или неизвестность (unknown). Значение NULL не равно ничему, включая другой NULL (NULL = NULL возвращает UNKNOWN). Однако при сортировке СУБД обязана позиционировать кортежи с NULL.

• Стандарт ANSI SQL-92: СУБД может считать NULL либо самым большим значением (больше любого существующего), либо самым маленьким, но обязана вести себя консистентно.
• Поведение PostgreSQL / Oracle: По умолчанию NULL считается «наибольшим» значением. Поэтому при ASC значения NULL выводятся в конце (NULLS LAST), а при DESC — в самом начале (NULLS FIRST).
• Поведение MySQL / MariaDB: По умолчанию NULL считается «наименьшим» значением (при ASC — в начале, при DESC — в конце).
• Явное управление (SQL-99): Для кроссплатформенной стабильности необходимо явно указывать спецификатор: ORDER BY rating DESC NULLS LAST или ORDER BY flight_gate ASC NULLS FIRST.

2.3. Локали и правила сравнения символов (Collation)

Сортировка текстовых полей напрямую зависит от установленного правила сопоставления символов (Collation). Collation определяет таблицу весов символов, регистрозависимость (case sensitivity) и акцентозависимость (accent sensitivity).

• Collation "C" / POSIX: Сортировка по бинарным кодам байтов UTF-8 / ASCII. Заглавные латинские буквы идут раньше строчных, а русские буквы сортируются по кодам таблицы. Буква «Ё» (код U+0401) окажется в начале алфавита, перед «А»!
• Локаль "ru_RU.UTF-8" / ICU: Алфавитная сортировка с учетом правил русского языка, где буква «е» и «ё» упорядочиваются корректно, а регистр игнорируется на первичном уровне сравнения (case-insensitive tie-breaking).
• Синтаксис явной локали: ORDER BY last_name COLLATE "ru_RU" ASC.

2.4. Физический алгоритм сортировки: External Merge Sort и work_mem

Когда СУБД получает команду на сортировку массива кортежей, планировщик оценивает объем данных и доступную оперативную память, выделяемую процессу (параметр work_mem в PostgreSQL или sort_buffer_size в MySQL).

1. In-Memory Sort (Quicksort / Top-N Heapsort): Если весь набор данных (или только ключи с указателями на строки — tuple pointers) умещается в work_mem, СУБД применяет быструю сортировку в ОЗУ. При наличии LIMIT k применяется алгоритм Top-N Heapsort с кучей размера $k$, что дает сложность $O(N \log k)$ без сортировки всей таблицы.
2. External Merge Sort (Внешняя сортировка слиянием): Если объем данных превышает work_mem:
   • Фаза 1 (Run Generation): Данные порциями считываются в память, сортируются в пределах work_mem и сбрасываются во временные файлы на диск в виде отсортированных серий (Runs).
   • Фаза 2 (Merge Passes): СУБД выполняет многопутевое слияние (Multi-way Merge) отсортированных серий с диска с использованием очереди с приоритетом (K-way Tournament Tree / Min-Heap). Если число серий велико, слияние происходит в несколько проходов.
   • План EXPLAIN: Sort Method: external merge Disk: 14256kB. Сброс на диск резко увеличивает задержку (I/O latency) в сотни раз!

2.5. Пагинация данных: LIMIT / OFFSET vs Keyset Pagination

Реализация постраничного вывода (Pagination) — классическая задача веб-разработки и проектирования БД.

• Смещение (Offset Pagination): SELECT * FROM items ORDER BY id LIMIT 20 OFFSET 100000;
  Проблема: СУБД вынуждена прочитать и отсортировать все 100 020 строк, отбросить первые 100 000 и вернуть последние 20. Сложность составляет $O(N)$, где $N = \text{OFFSET} + \text{LIMIT}$. При росте номера страницы сервер перегружается I/O операциями. Кроме того, при вставке новой строки между запросами пользователь видит дубликаты на стыке страниц.
• Курсорная пагинация (Keyset / Seek Method): SELECT * FROM items WHERE (created_at, id) < ($last_created, $last_id) ORDER BY created_at DESC, id DESC LIMIT 20;
  Преимущество: Поиск точки старта выполняется по B-Tree индексу за время $O(\log N)$, после чего извлекаются ровно 20 строк. Сложность константна независимо от глубины страниц ($O(1)$ относительно глубины пагинации).

2.6. Индексная поддержка предикатной фильтрации и сортировки

Оптимальное выполнение запроса с фильтрацией и сортировкой достигается созданием составного B-Tree индекса, поддерживающего правило «Равенство → Сортировка → Диапазон» (Equality, Sort, Range — ESR):

-- Запрос:
SELECT * FROM orders 
WHERE client_id = 42 AND status = 'COMPLETED' 
ORDER BY order_date DESC 
LIMIT 10;

-- Идеальный составной индекс:
CREATE INDEX idx_orders_client_status_date 
ON orders (client_id, status, order_date DESC);

Благодаря такому индексу СУБД использует узел Index Scan, двигаясь по дереву в уже отсортированном порядке без дополнительной операции в памяти Sort (zero-cost ordering).

3. Педагогические приемы и разбор типовых студенческих ошибок

Педагогический прием «Предсказание плана выполнения до запуска»

Преподаватель проецирует на экран SQL-запрос с фильтрацией и ORDER BY по двум таблицам и просит студентов предсказать:

1. Будет ли выполнен Index Scan или Seq Scan + Sort?
2. Где окажутся значения NULL: вверху или внизу списка?
3. Какой метод сортировки покажет EXPLAIN ANALYZE при work_mem = '4MB' на таблице в 1 000 000 записей?

Фиксация гипотез перед демонстрацией консоли включает когнитивное внимание и предотвращает пассивное запоминание.

Классификатор типовых студенческих ошибок