Тема 3. Этапы проектирования баз данных — Практическое занятие №7
В реляционной алгебре Эдгара Кодда отношение (relation) математически строго определяется как подмножество декартова произведения доменов, то есть неупорядоченное множество кортежей. В реляционной таблице физический порядок строк на дисковых страницах кучи (Heap Pages) является недетерминированным и подвержен случайным факторам (порядок параллельной вставки, повторное использование блоков после DELETE, фоновая очистка VACUUM).
ORDER BY, клиентское приложение не имеет права делать никаких предположений о порядке следования строк в результирующем наборе.
Спецификация ANSI SQL определяет следующую структуру секции упорядочивания:
SELECT <список_полей>
FROM <источник_данных>
[WHERE <предикаты_фильтрации>]
ORDER BY <выражение_1> [ASC | DESC] [NULLS FIRST | NULLS LAST]
[, <выражение_2> [ASC | DESC] [NULLS FIRST | NULLS LAST] ...];При многоуровневой сортировке сравнение кортежей выполняется по правилу лексикографического порядка: сначала по выражению 1; если значения равны — по выражению 2; и так далее до разрешения коллизии.
Поскольку NULL обозначает отсутствие значения, он не может быть строго сравнен с константами (результат 5 > NULL есть UNKNOWN). Стандарт SQL возлагает позиционирование NULL на движок СУБД, предоставляя явные директивы:
| Директива | Позиция NULL в выборке | Типовое применение в бизнес-логике |
|---|---|---|
NULLS LAST |
Всегда в самом конце результирующего списка | Сортировка товаров по рейтингу от 5 до 1: товары без отзывов (rating IS NULL) выводятся в конце, а не на первых позициях. |
NULLS FIRST |
Всегда в самом начале результирующего списка | Мониторинг авиарейсов: срочные рейсы с неназначенным гейтом (gate IS NULL) выводятся вверху табло диспетчера. |
Строковые поля (VARCHAR, TEXT) сортируются на основе таблицы сопоставления (Collation). Разница между бинарным порядком (C/POSIX) и естественным языковым порядком (Natural Sort):
Синтаксис явного указания локали в запросе: ORDER BY student_last_name COLLATE "ru_RU" ASC.
Когда СУБД встречает узел плана Sort, оптимизатор принимает решение о выделении памяти на основе параметра процесса (например, work_mem в PostgreSQL, по умолчанию 4 MB):
SET work_mem = '64MB'; для конкретной сессии аналитического запроса либо создают специализированный B-Tree индекс, возвращающий строки в готовом порядке без выполнения операции Sort.
Запрос SELECT * FROM ledger ORDER BY id ASC LIMIT 20 OFFSET 500000; заставляет СУБД физически просканировать и отсортировать 500 020 кортежей, после чего 500 000 строк отбрасываются. Вычислительная сложность $O(N)$ делает запрос медленнее с каждой следующей страницей.
Основан на запоминании последнего значения ключа предыдущей страницы:
-- Запрос первой страницы:
SELECT id, contract_number, signed_date
FROM contracts
WHERE payout_sum > 500000
ORDER BY signed_date DESC, id DESC
LIMIT 20;
-- Запрос следующей страницы (Keyset Pagination):
SELECT id, contract_number, signed_date
FROM contracts
WHERE payout_sum > 500000
AND (signed_date, id) < ('2026-03-31', 48912)
ORDER BY signed_date DESC, id DESC
LIMIT 20;Используя B-Tree индекс по (signed_date, id), СУБД мгновенно переходит к нужной ветке дерева за время $O(\log N)$ и читает ровно 20 кортежей.
Потому что реляционная модель рассматривает отношение как неупорядоченное множество. СУБД вправе считывать блоки из кучи в произвольном порядке (особенно при многопоточном сканировании Parallel Seq Scan или после операций UPDATE/VACUUM).
В PostgreSQL по умолчанию NULL считается наибольшим возможным значением, поэтому при ASC попадает в конец (NULLS LAST). В MySQL NULL трактуется как наименьшее значение, поэтому при ASC выводится в начале.
Когда объем сортируемого набора данных (ключей и строк) превышает размер оперативной памяти, выделенной процессу параметром конфигурации (work_mem в PostgreSQL или sort_buffer_size в MySQL).
Потому что планировщик обязан физически прочитать и отбросить 1 000 000 строк. При Keyset пагинации поиск точки отсчета выполняется по индексу за $O(\log N)$ с чтением всего 20 строк.