Модуль 12 ⏱ ~27 мин чтения 📐 2 Mermaid диаграмм

4. ORDER BY, LIMIT

«Порядок не является естественным свойством реляционных данных; это иллюзия, создаваемая осознанными вычислениями. Если вы явно не требуете от машины упорядочивания, вы отдаете себя на милость физической фрагментации страниц».

Упорядочивание хаоса: Иллюзия порядка в реляционной алгебре

Одно из первых заблуждений, с которым сталкивается начинающий инженер — убеждение, что данные в таблице базы данных хранятся «по порядку добавления».
В строгой математической модели Эдгара Кодда таблицы представляют собой неупорядоченные множества (sets) кортежей. В теории множеств элементы не обладают порядковыми индексами.

Если вы отправляете запрос SELECT * FROM users без явной директивы сортировки, СУБД имеет полное законное право вернуть строки в произвольной последовательности. Более того, эта последовательность может непредсказуемо меняться от секунды к секунде.
Физический порядок отдачи строк определяется тем:

  • В каком порядке дисковые блоки (pages) вытесняются или поднимаются в буферный пул (Buffer Pool);
  • Как сработал параллельный сканер нескольких воркеров;
  • Как отработал фоновый сборщик мусора базы (например, процесс VACUUM в PostgreSQL, который очищает мертвые кортежи и освобождает пустоты внутри 8-килобайтных страниц для повторной записи новых строк).

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

Механика ORDER BY: RAM, Диск и B-Tree

С точки зрения Mechanical Sympathy, операция сортировки — один из самых тяжелых вычислительных этапов во всем конвейере базы данных. Процессор вынужден сравнивать значения ключей для миллионов пар записей, переставляя указатели в памяти.
На физическом уровне СУБД выбирает один из двух принципиально разных механизмов сортировки:

1. Сортировка в памяти (In-Memory Sort / FileSort)

Если результирующий набор строк невелик, СУБД собирает все отфильтрованные кортежи и выполняет их упорядочивание непосредственно в оперативной памяти (применяя оптимизированный QuickSort или Radix Sort).

В архитектуре PostgreSQL объем оперативной памяти, выделяемый под одну операцию сортировки внутри одного процесса бэкенда, жестко лимитируется параметром конфигурации work_mem (значение по умолчанию часто составляет скромные 4MB).

flowchart TD
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef aux      fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc
    classDef system   fill:#312e81,stroke:#a78bfa,stroke-width:1px,color:#f8fafc
    classDef data     fill:#132d29,stroke:#2dd4bf,stroke-width:1px,color:#f8fafc
    classDef network  fill:#881337,stroke:#fb7185,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    Rows["Входящий поток строк"]:::warning --> CheckMem{"Объем данных <= work_mem?"}
    CheckMem -->|"Да"| RAMSort["In-Memory QuickSort<br>Быстро в ОЗУ"]
    CheckMem -->|"Нет"| DiskSpill["External Merge Sort<br>Сброс чанков на диск"]
    DiskSpill --> DiskIO["Чтение/запись во временные файлы pgsql_tmp<br>Падение производительности в сотни раз"]
    RAMSort --> Output["Готовый отсортированный поток"]
    DiskIO --> Output

2. Сортировка по индексу (Index Sort)

Это наивысший стандарт производительности: лучшая сортировка — это та, которой не было вовсе.
Индекс B-Tree (B-дерево) хранит ключи в строго отсортированном порядке на уровне листовых узлов (leaf pages). Листовые страницы связаны между собой двусвязным списком (Doubly Linked List).

Если в запросе указано ORDER BY created_at, и по колонке created_at существует B-Tree индекс, оптимизатор полностью исключает этап сортировки!
Исполнитель базы просто выполняет спуск к первому листовому узлу индекса и последовательно считывает уже упорядоченные указатели на строки.

  • Для сортировки по возрастанию (ASC) B-Tree читается слева направо (Forward Index Scan).
  • Для сортировки по убыванию (DESC) двусвязный список листовых страниц сканируется справа налево (Backward Index Scan).

Это классический Index Scan, отрабатывающий практически с нулевыми затратами процессорного времени. Внутреннее устройство B-Tree страниц и навигацию по связным спискам мы детально препарируем в статье 2. B Tree индекс под капотом.

LIMIT и паттерн Top-N

Команда LIMIT N (в некоторых СУБД вроде MS SQL или Sybase — TOP N, а в стандартах ANSI SQL — FETCH FIRST N ROWS ONLY) представляет собой директиву раннего выхода (Early Stop). Как только конвейер исполнителя сгенерировал N строк, удовлетворяющих критериям, он немедленно обрывает дальнейшее чтение данных.

Комбинация ORDER BY и LIMIT без использования индекса включает в СУБД специальную оптимизацию — Top-N Heapsort.

Представьте запрос ORDER BY score DESC LIMIT 10 по таблице из 10 миллионов записей. Наивный подход потребовал бы отсортировать все 10 миллионов строк (с неизбежным сбросом на диск).
Но движок базы данных создает в оперативной памяти компактную структуру данных «двоичная куча» (Priority Queue / Bounded Heap) размером ровно в $N=10$ элементов. Проходя по таблице полным сканированием, СУБД удерживает в куче только 10 максимальных элементов, вытесняя меньшие значения. Эта операция требует ничтожного объема RAM, укладывается в микросекунды и никогда не сбрасывает данные на диск.

Mechanical Sympathy в Go: Аллокация памяти

Если SQL-запрос завершается директивой LIMIT N, ваше Go-приложение на этапе компиляции получает ценнейшую информацию: точный верхний предел размера результирующего слайса.
Игнорирование этого факта превращает код в источник избыточных аллокаций и фрагментации кучи.

❌ Неэффективный код (Серия реаллокаций и лишняя нагрузка на GC):

Go 
var users []User // nil slice: len = 0, cap = 0
rows, _ := db.QueryContext(ctx, "SELECT id FROM users LIMIT 100")
defer rows.Close()

for rows.Next() {
    var u User
    _ = rows.Scan(&u.ID)
    // append вынужден многократно вызывать runtime.growslice,
    // выделять новые блоки памяти в куче и копировать старые элементы.
    users = append(users, u) 
}

✅ Идиоматичный Go (Zero Reallocations / Механическое сочувствие):

Go 
// Мы точно знаем верхнюю границу выборки, поэтому выделяем емкость (capacity) заранее.
// Длина (len) равна 0, чтобы append корректно заполнял элементы без лишних проверок.
users := make([]User, 0, 100) 

rows, err := db.QueryContext(ctx, "SELECT id FROM users LIMIT 100")
if err != nil {
    return nil, err
}
defer rows.Close()

for rows.Next() {
    var u User
    if err := rows.Scan(&u.ID); err != nil {
        return nil, err
    }
    // runtime.growslice НИКОГДА не будет вызван! Память аллоцирована ровно один раз.
    users = append(users, u)
}

Убийца производительности: OFFSET и глубокая пагинация

Подавляющее большинство веб-сервисов реализуют постраничную навигацию наивным сочетанием LIMIT и OFFSET:

SQL 
SELECT id, name FROM users ORDER BY created_at DESC LIMIT 50 OFFSET 100000;

Кажется, что мы элегантно запрашиваем 50 строк, начиная со стотысячной. Однако для сервера СУБД это катастрофа.

flowchart LR
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef aux      fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc
    classDef system   fill:#312e81,stroke:#a78bfa,stroke-width:1px,color:#f8fafc
    classDef data     fill:#132d29,stroke:#2dd4bf,stroke-width:1px,color:#f8fafc
    classDef network  fill:#881337,stroke:#fb7185,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    Start["Запрос OFFSET N"]:::entry --> Traverse["B-Tree поиск первого элемента"]
    Traverse --> Iterate["Последовательное чтение<br>листовых узлов"]
    Iterate -->|"Пропуск 1й строки"| Drop1["Отброшено"]
    Iterate -->|"Пропуск 2й строки"| Drop2["Отброшено"]
    Iterate -->|"..."| DropN["..."]
    Iterate -->|"Пропуск N-й строки"| DropX["Отброшено"]
    Iterate -->|"Чтение N+1 строки"| Keep["Сохранение в результат"]

Альтернатива: Keyset Pagination (Cursor / Seek Method)

В архитектуре высоконагруженных систем глубокий OFFSET находится под строжайшим запретом. Промышленным стандартом построения масштабируемых API является Keyset Pagination (пагинация по ключу или курсорный метод).

Его суть проста и гениальна: клиент запоминает значения граничных колонок последней записи на текущей странице и передает их в качестве фильтра WHERE для следующего запроса.

SQL 
-- 1. Запрос первой страницы
SELECT id, name, created_at 
FROM users 
ORDER BY created_at DESC, id DESC 
LIMIT 50;

-- Предположим, последний пользователь в полученной пачке имел:
-- created_at = '2023-10-01 12:00:00', id = 1042

-- 2. Запрос второй страницы (СТРОГО БЕЗ OFFSET!)
SELECT id, name, created_at 
FROM users 
WHERE (created_at, id) < ('2023-10-01 12:00:00', 1042)
ORDER BY created_at DESC, id DESC 
LIMIT 50;

Почему Keyset Pagination работает молниеносно при любом объеме данных?
Конструкция WHERE (created_at, id) < (...) позволяет СУБД выполнить точечный поиск по составному B-Tree индексу (Index Seek) за константное логарифмическое время O(log N). База спускается по дереву точно к записи 1042 и читает следующие 50 листовых записей. Вне зависимости от того, находится ли клиент на 2-й странице или на 2 000 000-й, время выполнения запроса остается стабильным — менее 1 миллисекунды. Сравните: сложность O(N) у OFFSET против O(log N) у Keyset Pagination!

Итог

  1. Таблицы в SQL — это математические множества без врожденного порядка. Любой детерминированный вывод требует явного ORDER BY.
  2. Сортировка без индексов ограничена параметром work_mem. Превышение лимита вызывает сброс временных файлов на диск (External Merge Sort), обрушивая производительность.
  3. Индекс B-Tree позволяет выполнять сортировку даром через обход связанного списка листовых узлов (Index Scan).
  4. LIMIT N в сочетании с сортировкой включает экономичный алгоритм Top-N Heapsort, предотвращающий сброс на диск для небольших выборок.
  5. В Go всегда предварительно аллоцируйте слайсы make([]T, 0, limit), исключая вызовы growslice и лишнее давление на сборщик мусора.
  6. OFFSET обладает катастрофической сложностью $\mathcal{O}(N)$ из-за особенностей MVCC. В масштабируемом бэкенде пагинация обязана строиться через Keyset Pagination (Cursor / Seek Method).

Мы досконально изучили чтение, фильтрацию и упорядочивание данных. Пришло время перейти к мутациям состояния базы данных и атомарным изменениям кортежей в следующей статье: 5. INSERT, UPDATE, DELETE.