Запрос вида ORDER BY ... LIMIT 10 кажется одной из самых простых операций в SQL. Но в реальных системах на PostgreSQL эта задача может неожиданно превратиться в серьёзную проблему.
Команда ParadeDB показала довольно наглядный пример: простой запрос на 100-миллионной таблице выполняется примерно за 5 миллисекунд, но стоит добавить фильтр или полнотекстовый поиск — и время выполнения может вырасти до 30–37 секунд.
Это не баг и не плохая конфигурация базы. Это фундаментальное ограничение архитектуры традиционных индексов.
Разберёмся, почему это происходит и почему базы данных начинают заимствовать идеи у поисковых движков вроде Lucene.
Почему Top-K кажется простой задачей
В терминологии баз данных Top K означает:
«верни K лучших строк по определённому критерию».
Примеры таких запросов встречаются буквально везде:
📊 последние 10 событий в логах
🛒 20 самых популярных товаров
📱 10 самых релевантных результатов поиска
SQL для этого выглядит тривиально:
SELECT *
FROM logs
ORDER BY timestamp DESC
LIMIT 10;
Без индекса PostgreSQL вынужден отсортировать всю таблицу, поэтому на 100 миллионах строк такой запрос может занимать 15 секунд.
Но стоит создать индекс:
CREATE INDEX ON logs(timestamp);
— и всё резко ускоряется.
⚙️ Что происходит внутри
📄 B-tree хранит значения уже отсортированными
📍 PostgreSQL сразу прыгает к максимальному значению
🔄 затем просто читает следующие записи
В итоге сложность операции становится O(K) — база читает только нужные строки.
Отсюда и впечатляющие 5 миллисекунд.
Но стоит добавить фильтр — и всё ломается
Реальные запросы редко бывают такими простыми.
Чаще они выглядят примерно так:
SELECT *
FROM logs
WHERE severity < 3
ORDER BY timestamp DESC
LIMIT 10;
И тут PostgreSQL попадает в неприятную ситуацию.
Он может:
🔎 использовать индекс по timestamp
но тогда
📄 ему придётся проверять фильтр severity для каждой строки
или
📊 сначала отфильтровать строки
но тогда
📉 придётся сортировать результат.
В худшем случае база начинает сканировать огромную часть индекса, отбрасывая строки одну за другой.
Это и приводит к скачку времени выполнения.
Комбинаторный взрыв индексов
На первый взгляд решение очевидно: создать составной индекс.
CREATE INDEX ON logs(severity, timestamp);
Теперь PostgreSQL может сразу перейти к нужной части дерева.
Но проблема быстро выходит из-под контроля.
Допустим, в системе есть фильтры:
🌍 страна
⚠️ уровень ошибки
📅 время
🔎 текстовый поиск
Каждая комбинация требует нового индекса.
📦 Что происходит в реальности
📈 десятки индексов на одной таблице
💾 резкий рост размера базы
🐌 замедление операций записи
🧠 сложные планы выполнения запросов
Эту проблему в индустрии часто называют «комбинаторным взрывом индексов» — ситуацией, когда количество необходимых индексов стремительно растёт из-за множества возможных комбинаций фильтров и сортировок в запросах.
Полнотекстовый поиск делает всё ещё хуже
Ситуация становится совсем тяжёлой, когда в запрос добавляется поиск по тексту.
Пример:
SELECT *
FROM logs
WHERE message @@ to_tsquery('research team')
AND severity < 3
ORDER BY rank DESC
LIMIT 10;
Postgres использует для этого GIN-индекс — инвертированный индекс.
Но возникает фундаментальная проблема:
❌ GIN не хранит порядок документов
❌ PostgreSQL не умеет объединять сортировку из разных индексов
Поэтому план выполнения выглядит примерно так:
⚙️ GIN находит миллионы документов
📄 база вытаскивает строки из таблицы
🔍 применяет дополнительные фильтры
📊 сортирует результат
📦 возвращает Top-10.
Если совпадений много, это становится катастрофически дорого.
В эксперименте ParadeDB такой запрос занимал 37 секунд.
Почему поисковые системы работают иначе
Поисковые движки вроде Lucene или Tantivy проектировались с другой философией.
Они исходят из предположения, что:
🔎 запросы будут сложными
📊 фильтров будет много
⚡ Top-K нужен почти всегда.
Поэтому архитектура индексов там другая.
Основные компоненты:
🧠 инвертированный индекс
📊 колоночное хранение данных
Как работает инвертированный индекс
Инвертированный индекс хранит соответствие:
слово → список документов.
Пример:
research → [doc1, doc2]
database → [doc3]
Когда приходит запрос:
research AND database
поисковая система просто пересекает списки документов.
Это очень быстро.
Почему колоночное хранение ускоряет фильтры
В традиционных БД данные лежат построчно.
[id | country | severity]
В колоночной модели всё хранится иначе:
id: [1,2,3]
country: [US,CA,US]
severity: [2,9,1]
Это даёт несколько преимуществ.
⚡ быстрый случайный доступ
🧠 лучшее использование CPU-кэша
🧮 возможность SIMD-операций
Например, фильтр severity < 3 можно применить сразу к целому блоку значений.
Самый интересный трюк — Block WAND
Ещё одна оптимизация из мира поисковых систем называется Block WAND.
Идея довольно гениальная.
Поисковый движок хранит:
📊 максимальный возможный score для блока документов.
Если максимальный score блока ниже текущего порога Top-K — блок просто пропускается.
То есть движок даже не оценивает документы внутри блока.
Это позволяет отбрасывать огромные объёмы данных.
Результат: ускорение в десятки раз
Используя такую архитектуру, ParadeDB смогла ускорить тот же запрос.
Вместо:
⏱ 37 секунд в PostgreSQL
получилось:
⏱ ≈300 миллисекунд
на той же таблице 100 миллионов строк.
Это почти в 100 раз быстрее.
Почему это важнее, чем кажется
Проблема Top-K — это не академическая задача.
Она лежит в основе огромного количества систем:
🔎 поисковые движки
📱 рекомендательные системы
🛒 интернет-магазины
📊 аналитические платформы
Практически любой интерфейс, где есть «лучшие результаты», упирается именно в неё.
Мой взгляд: будущее баз данных — гибридное
Исторически базы данных и поисковые системы развивались отдельно.
PostgreSQL — для транзакций.
Elasticsearch — для поиска.
Но сегодня граница между ними постепенно исчезает.
Современные приложения хотят:
⚡ транзакционность
🔎 полнотекстовый поиск
📊 аналитические запросы
📈 персонализацию.
И держать три разных системы для этого всё менее удобно.
Поэтому появляются гибридные решения:
🧠 ParadeDB
🔎 Elasticsearch SQL
📊 ClickHouse search
📦 pgvector и другие расширения.
Вывод
Top-K — это хороший пример того, как простая задача превращается в сложную проблему, когда данные становятся огромными.
Классические B-tree индексы отлично работают для простых запросов.
Но современный поиск требует:
⚙️ гибких фильтров
⚙️ полнотекстового анализа
⚙️ сложных метрик релевантности.
И здесь архитектура поисковых систем оказывается гораздо эффективнее.
Скорее всего, будущее баз данных — это слияние двух миров:
транзакционных СУБД и поисковых движков.
И PostgreSQL уже начинает двигаться в эту сторону.
Источники
🔗 https://www.paradedb.com/blog/optimizing-top-k