9 октября 2026Команда Сарнас

Как ParadeDB ускоряет полнотекстовый поиск: механика оптимизаций BM25

В ParadeDB полнотекстовый поиск исполняется внутри Postgres, и это меняет цену каждого обращения к данным: то, что в обычном поисковике почти бесплатно, здесь оборачивается чтением отдельных страниц. Автор разбирает три оптимизации BM25-скоринга — переупаковку fieldnorms, выбор алгоритма прунинга и ленивое чтение — и показывает, как они повлияли на число страничных обращений и время запроса. Полезно тем, кто встраивает поисковые движки в реляционные СУБД и хочет понять, где именно расходуется время.

Полнотекстовый поиск в ParadeDB опирается на Tantivy — библиотеку, которая хранит postings и отдельно от них — fieldnorms. Когда поиск исполняется внутри Postgres, а не в памяти процесса с memory-mapped хранилищем, раскладка данных перестаёт быть нейтральной: то, что в обычном поисковике стоит дешёвого обращения к памяти, в Postgres превращается в отдельную страницу. Разбираем, как переупаковка fieldnorms, выбор алгоритма прунинга и ленивое чтение меняют число обращений к страницам и время запроса.

Исходная раскладка и откуда берутся лишние страницы

До оптимизации Tantivy хранил fieldnorms отдельно от postings, в массиве, индексируемом по DocId. Postings каждого терма — это список DocId, а fieldnorm-массив общий для всех документов. Fieldnorm в Tantivy крошечный: длина документа квантуется в однобайтовое значение fieldnorm_id — это квантование, при котором длина поля сжимается до одного байта. Одного байта достаточно, потому что BM25 использует норму лишь для грубой нормализации оценки, а не как точную длину.

При скоринге BM25 чтение postings терма идёт последовательно, но выборка соответствующих fieldnorms из общего массива по DocId прыгает по всему массиву. В памяти с memory-mapped хранилищем это дёшево, но в Postgres такой разброс означает касание множества отдельных страниц. Атрибуция обращений к страницам для запроса показала, что fieldnorms дали 1 513 обращений (83%), а всё остальное — postings, метаданные — 311 (17%). Для одного запроса это означало примерно 1 500 различных страниц fieldnorm.

Оптимизация 1: fieldnorms рядом с postings

Исправление — хранить массив fieldnorm рядом с каждым списком postings, в том же порядке, что и значения DocId в postings. Тогда скоринг читает fieldnorms последовательно вместе с postings, и разбросанные обращения исчезают.

Раскладка меняется так: fieldnorms больше не лежат одним общим массивом для всех документов, а дублируются для каждого терма — у каждого терма свой список DocId и свой список fieldnorm IDs.

Postings   Fieldnorms
"database": [DocId values]   "database": [fieldnorm IDs]
"rust":     [DocId values]   "rust":     [fieldnorm IDs]

Цена — рост объёма хранения: fieldnorm документа повторяется для каждого отдельного терма, который он содержит. Но это не значит умножения на число термов: в реальных корпусах у большинства термов короткие postings-списки и соответственно маленькие массивы fieldnorm. Для индекса HN на 28.7M документов изменение дало рост примерно на 9%.

Выигрыш оказался неравномерным. Для запросов с небольшим числом термов оптимизация дала огромное ускорение. В disjunction-запросах с многими термами чтения из буфера упали примерно на 80%, но время запроса снизилось лишь на 5% — это указывало на то, что узкое место сместилось с ввода-вывода на алгоритм.

Оптимизация 2: выбор алгоритма прунинга Blockmax

Профилирование показало, что большая часть времени уходит в цикл Blockmax WAND. Вместо него был выбран Blockmax-алгоритм с более высокой пропускной способностью. Реализована эвристика выбора: MAXSCORE применяется для дизъюнкций минимум из трёх термов с достаточно плотными постингами, WAND — во всех остальных случаях.

Отдельный эффект этой оптимизации виден в планировщике. Для prunable TopK стоимость drive_cost (полный проход по набору документов) исключается из оценки пути, потому что Block-WAND отсекает работу сублинейно и полная стоимость завысила бы оценку; вместо неё берётся стоимость вывода (~k строк). Это исключение применяется только для причин BlockWandPrunable и DocumentCount. Для причин CostModel, CostModelLimited, PerSegment и RowHeuristic drive_cost сохраняется.

Оптимизация 3: ленивое чтение

В разделе Closing Thoughts упомянуты «small optimizations related to lazy reading of other pieces of data» без перечисления конкретных оптимизаций. В коде ленивое чтение проявляется в нескольких местах.

Поиск по всем доступным сегментам индекса использует ленивый checkout из параллельного состояния, чтобы балансировать нагрузку между параллельными воркерами. Итератор по кандидатам забирает сегменты из общего состояния по одному и решает по каждому, принадлежит ли он воркеру, — так воркер не оценивает чужие сегменты. Метод, отдающий читателей сегментов, требует ленивого потребления входных идентификаторов сегментов, потому что некоторые вызывающие (в частности Top K) порождают их лениво, проверяя из разделяемого изменяемого состояния по ходу.

В Closing Thoughts названы и направления будущих оптимизаций: более эффективный Blockmax pruning и сокращение доступа к буферам.

Планировщик: как выбирается метод исполнения

Выбор между методами исполнения происходит в два этапа. На этапе планирования функция выбора сначала пытается использовать TopK: если у builder'а есть limit_offset и либо есть orderby_info, либо topk_pathkey_info равно PathKeyInfo::None, возвращается TopK с heaprelid, limit_offset, orderby_info и window_aggregates. Иначе проверяется колоночная способность; при успехе в список методов добавляется Columnar с planned_which_fast_fields и limit_offset. Если ни TopK, ни Columnar не подходят, возвращается Normal.

На этапе исполнения метод берётся из состояния: для Normal создаётся обычное состояние сканирования, для TopK — состояние Top K, для Columnar делается попытка вычислить набор fast fields и при успехе создаётся колоночное состояние, иначе — откат на Normal.

Отдельная проверка следит за тем, что запрос, которому положено использовать Top K, действительно его использует. Top K ожидается при наличии LIMIT, явного LIMIT, поискового запроса и отсутствия GROUP BY. Если ожидание не выполнено, выдаётся предупреждение с причиной и рекомендациями. Причины берутся из topk_pathkey_info: слишком много колонок в ORDER BY, проталкивается только префикс, колонки нельзя протолкнуть в индекс, оператор не совпадает с opclass индекса, коллация не байтово-упорядоченная, выражения с pdb.score() нельзя вычислить в индексе. Отключить предупреждение можно через SET paradedb.planner_warnings = 'off'.

Планировщик: проталкивание quals и join-предикаты

Извлечение quals начинается с попытки обработать весь список restrict_info целиком. Если полная выборка не удалась, делается частичная: каждый RestrictInfo перебирается по отдельности, неудачные пропускаются, и частичный результат принимается только если хотя бы один qual извлечён, использован наш оператор и все пропущенные клаузы являются SubPlan. Если quals всё ещё нет, из joininfo извлекаются Join-квалификации, но используются только при наличии нашего оператора и score/snippet.

При SubPlan в baserestrictinfo логика такая: SubPlan-клаузы пропускаются, остальные непротолкнутые клаузы добавляются в deferred_plan_quals, но если клауза содержит наш поисковый предикат, обработка отменяется. Проверка непроталкиваемых предикатов возвращает ошибку при наличии отложенных quals (например, для соблюдения row-level security), подзапросов, волатильных функций, а также если quals не были протолкнуты при непустом restrict_list.

Разделение предикатов на pushable и leaky опирается на классификацию безопасности: безопасные добавляются в pushable, leaky-клаузы с нашим оператором отменяет обработку (её нельзя ни протолкнуть, ни отложить), leaky-клауза без нашего оператора для базового отношения добавляется в pushable, если она вычисляется после клауз с меньшим security_level, иначе откладывается. Условие «после клауз с меньшим security_level» означает, что leaky base clause становится top-level heap-фильтром, а все клаузы с меньшим security_level (например, политика RLS) стали indexed conjunct без heap-выражений, — тогда heap-фильтр вычисляет клаузу только на документах, уже прошедших эти клаузы.

Планировщик: TopK и pathkeys

Проталкивание pathkeys в TopK начинается с извлечения стилей сортировки для ORDER BY с проверками сортируемости поля. Если стилей не больше предела MAX_TOPK_FEATURES, они возвращаются как пригодные целиком — Top K единственный исполнитель базового скана, поддерживающий сортировку, и поддерживает до этого числа order-by клауз. Если стилей больше, результат помечается как непригодный с причиной «слишком много колонок». Если удалось получить только префикс, результат тоже непригоден: Top K не может выполниться для префикса pathkeys, потому что отбрасывает результаты до того, как вступит в игру суффикс.

«Fast fields» в этом контексте — набор полей, извлекаемых на этапе выполнения по execution-time target list. Они должны быть подмножеством полей, запланированных на этапе планирования, иначе метод откатывается на Normal. Если все поля оказались служебными или junk, тоже происходит откат: между планированием и выполнением отсекается достаточно столбцов, чтобы использовать fast fields было бессмысленно.

Прунинг сегментов

Решение о том, может ли сегмент дать совпадения, принимается парой функций. Одна доказывает, что сегмент не может дать ни одного совпадения; вторая доказывает, что все документы сегмента удовлетворяют запросу (нужно для отрицаний).

Разбор запроса по полю: для «все документы» совпадение возможно, для «пусто» — невозможно, для термов и их множеств — проверка по термам, для диапазона — проверка по статистике поля, для прочих вариантов совпадение считается возможным (fail-open). Проверка диапазона доказывает невозможность совпадения только когда наблюдаемые границы исключают любое возможное значение: если статистики нет, совпадение считается возможным, иначе проверяется сравнимость границ и пересечение со статистикой. Проверка терма доказывает невозможность совпадения только когда наблюдаемые границы исключают терм: если статистики нет, совпадение считается возможным, иначе проверяется, что терм сравним с минимумом и максимумом и лежит между ними.

Ключевое свойство: невозможность совпадения доказывается только при наличии статистики, чьи наблюдаемые границы строго исключают значение. При отсутствии статистики или несравнимости совпадение считается возможным. Именно поэтому доказанная невозможность надёжна — она не может возникнуть из-за нехватки данных.

Зеркальная функция для «все документы подходят» доказывает это только когда условие выполнено: например, для диапазона требует, чтобы границы покрывали оба экстремума и поле было не nullable.

Прунинг сегментов: пограничные случаи

Прунинг опирается на статистики (минимум, максимум, nullable) и на пару доказательств (can_match, matches_all) с константами NEVER=(false,false), MAYBE=(true,false), ALWAYS=(true,true).

При NaN в статистиках или в терме сравнение отключается: если любое из значений — F64 NaN, значения считаются несравнимыми. Поэтому NaN в минимуме статистики, NaN в терме при конечных статистиках, NaN в границах диапазона — всё даёт MAYBE, то есть NaN не даёт ни исключения, ни гарантии.

При отсутствии статистик и терм, и диапазон дают MAYBE: отсутствие статистик не исключает сегмент. Nullable-сегменты не дают гарантии покрытия: константное поле (минимум равен максимуму) при nullable=false даёт ALWAYS для совпадающего терма, а при nullable=true — только MAYBE. Проверка покрытия диапазоном тоже требует, чтобы поле не было nullable.

Прунинг сегментов: согласование с Tantivy для boolean-запросов

Для boolean-запроса нужно определить, сколько положительных should-клауз реально требуется. Безопасное число определить нельзя, когда minimum_should_match отрицателен или когда у запроса ровно один положительный clause, нет must_not и запрошенный минимум больше числа should.

if minimum < 0 || (must + should == 1 && must_not == 0 && minimum as usize > should) {
    return None;
}

В остальных случаях берётся максимум из минимума и флага «must == 0 && should > 0», то есть при отсутствии must хотя бы один should обязателен.

Проверка «может совпасть» в неопределённом случае не отбрасывает сегмент, а иначе требует, чтобы все must были возможны, ни один must_not не был гарантирован, и среди возможных should набралось нужное число совпадений. Проверка «все подходят» в неопределённом случае не подтверждает покрытие, а иначе требует, чтобы все must были гарантированы, ни один must_not не был возможен, и среди гарантированных should набралось нужное число. Тест проверяет согласование с Tantivy для одного clause при occur Must или Should и минимуме из 0, 1, 2, −1, сравнивая результаты обычного scorer и pruning_scorer.

Прунинг сегментов: опускание range-фильтра по партиционной колонке

При сканировании одной партиции range-фильтр по партиционной колонке опускается на полностью включённых сегментах и сохраняется на частично включённых. Условие опускания определяется той же проверкой покрытия: диапазон покрывает все документы только когда границы сравнимы, поле не nullable и нижняя граница содержит минимум, а верхняя — максимум.

stats.is_some_and(|stats| {
    bounds_comparable(stats, lower, upper)
        && !stats.nullable
        && lower_contains(lower, &stats.min)
        && upper_contains(upper, &stats.max)
})

Границы партиции при этом оборачиваются в запрос с нулевым скором, чтобы не влиять на скоры. Подготовка веса должна оставаться ленивой до фактического поиска: счётчик вызовов подготовки веса равен нулю до поиска и равен числу непустых групп сегментов после. Nullable-сегмент внутри диапазона партиции, владеющей NULL, считается полностью включённым и ищется без фильтра партиции, тогда как для партиции, не владеющей NULL, тот же сегмент остаётся частично включённым.

Segmented TopK: инжекция под сортировку

Правило включается только при включённом GUC paradedb.enable_segmented_topk; иначе план возвращается без изменений. Переписывание рекурсивно обходит детей, а затем пытается вставить узел под сортировку. Срабатывает это только для сортировки с заданным лимитом: берутся выражения сортировки и уже протолкнутый динамический фильтр, которого ожидается ровно один.

Далее ищется узел декодирования, у которого хотя бы одна колонка сортировки входит в deferred-поля (сопоставление по физическому индексу). При успехе новый узел вставляется под lookup (или под узел выборки, если он есть), а сортировка разворачивается — возвращается её ребёнок. Если сортировка требует deferred-колонок из нескольких разных индексов, инжекция отменяется: проверяется первый индекс и наличие колонки с другим индексом, пишется предупреждение, и остаётся стандартная сортировка.

Segmented TopK: per-segment буферизация и глобальный порог

Для каждого сегмента (плотный индекс 0..N) хранится свой буфер и его порог. Буфер заполняется пакетами, а при достижении ёмкости 2*K обрезается: QuickSelect выбирает K лучших строк, K-я записывается как локальный порог сегмента, буфер обрезается до K, и публикуется глобальный порог.

fn buffer_capacity(&self) -> usize {
    2 * self.k
}

Глобальный порог — это «best of the worst»: берётся худшая строка каждого полного сегмента (его локальный K-й порог), материализуется в глобальные значения, и выбирается наименьшая. Если использовать границу больше локального порога любого полного сегмента, можно отсечь конкурентные строки в других сегментах; минимальная из верхних границ даёт математически безопасный порог для глобального отсечения.

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

Segmented TopK: построение фильтра и материализация значений

Лексикографический фильтр строится как цепочка сравнений. Для каждого столбца сортировки выбирается оператор «меньше» при возрастании или «больше» при убывании, и сравнение оборачивается обработкой NULL в зависимости от порядка NULL и того, является ли порог NULL. Первый столбец даёт самостоятельный фильтр, каждый следующий присоединяется через AND к накопленному равенству всех предыдущих столбцов своим порогам, после чего все фильтры объединяются через OR. Для ORDER BY a ASC, b ASC с порогами (t_a, t_b) получается a < t_a OR (a = t_a AND b < t_b).

Материализация значений порога для каждого столбца: если столбец deferred, берётся term ordinal из массива UInt64 и через преобразование ordinal в строку или байты получается значение (Utf8View или BinaryView); при неудаче возвращается ошибка, а не NULL. Для не-deferred столбцов значение читается напрямую из массива. Полученные значения конвертируются в строку и кэшируются вместе с локальным порогом. Публикация перебирает порог каждого полного сегмента, выбирает минимальную строку и, если она изменилась, строит новый фильтр и обновляет динамический фильтр.

Segmented TopK: финальная эмиссия и NULL

При финальной эмиссии в набор кандидатов сначала добавляются все строки из per-segment буферов, а затем — все pass-through строки. Pass-through строки включаются всегда, потому что у них был NULL-ординал хотя бы в одной deferred-колонке, и они не могли быть отфильтрованы по ординалам.

Для каждого кандидата по каждой колонке сортировки вычисляется значение: если колонка deferred, берётся её ординал; при наличии ординала значение материализуется, при отсутствии подставляется типизированный NULL. Типизированный NULL нужен потому, что NULL должен соответствовать объявленному типу поля конвертера строк: конвертер отвергает несоответствия. Для не-deferred колонок значение вычисляется напрямую из батча, а при ошибке тоже подставляется типизированный NULL. Затем все значения конвертируются одним вызовом, сортируются и берётся top K.

Что видит клиент в EXPLAIN

Для запроса с условием по title и сортировкой по pdb.score(id) DESC с LIMIT 10 EXPLAIN (ANALYZE, BUFFERS) показывает, что TIN затронул гораздо меньше страниц Postgres, чем ParadeDB. Атрибуция обращений по структурам данных дала 1 513 (83%) на fieldnorms и 311 (17%) на всё остальное. Причина — локальность: fieldnorms хранились отдельно от postings в массиве по DocId, и выборка прыгала по массиву, из-за чего запрос трогал примерно 1 500 различных страниц fieldnorm. После хранения массива fieldnorm рядом с каждым списком postings в том же порядке, что и DocId, обращения к fieldnorm упали с 1 500 страниц до 30.

Для запроса с длинным текстом и сортировкой по pdb.score(id) DESC с LIMIT 10 после оптимизации fieldnorms чтения буферов упали примерно на 80%, но время запроса снизилось лишь на 5% — это указывало на алгоритмическое узкое место, цикл Blockmax WAND.

В самом EXPLAIN выводится выбранный метод исполнения (берётся последний сегмент имени после ::), флаг Scores из потребности в скорах, а флаг полного индексного сканирования добавляется только если поисковый запрос инициализирован и является полным сканом. Оценки показываются только при включённом GUC и verbose: берётся существующий читатель (для EXPLAIN ANALYZE) либо создаётся временный по крупнейшему сегменту, и по нему строится дерево запроса с оценками.

Оценки строятся рекурсивно: берётся общее число документов, при отсутствии сегментов всем узлам проставляется ноль; иначе выбирается самый крупный сегмент, вычисляется его доля от общего числа документов, и для каждого узла сначала оцениваются дети. Для узлов «пусто» или «все документы» ровно с одним ребёнком оценка наследуется от ребёнка; иначе узел конвертируется в запрос, и если оценка по статистике дала значение, оно масштабируется долей крупнейшего сегмента; в противном случае строится вес и через оценку скорера получается количество, масштабируемое тем же коэффициентом.

Как сравнивали и что получилось

Методология

Запросы в бенчмарке Stack Exchange генерировались выборкой последовательных фрагментов слов из корпуса, что дало запросы вроде «is it», «to a», «is to». Все запросы ParadeDB были переведены на собственные операторы ||| (дизъюнкция), &&& (конъюнкция) и ### (фраза), чтобы избежать неявного поиска по всем индексированным текстовым полям.

Авторы отмечают две аномалии, непреднамеренно благоприятствовавшие TIN. Первая: запросы TIN использовали парсер строк ParadeDB через оператор @@@, но не были квалифицированы именем поля. При неквалифицированных запросах ParadeDB по умолчанию ищет по всем индексированным текстовым полям, а в наборе StackExchange проиндексированы оба столбца id и body, — то есть ParadeDB искала по двум столбцам на запрос, тогда как TIN — только по одному. Вторая: TIN применяет dense-term elision — во время запроса пропускает оценку любого термина, который встречается более чем в 10% корпуса (настраивается через dense_ratio). Это даёт приближение BM25 и может менять порядок результатов по сравнению с истинным BM25.

Целые запросы, состоящие из распространённых слов, оказались неожиданностью. На них TIN пропускал большую часть работы по скорингу, тогда как ParadeDB вычислял точные оценки, и именно эти запросы доминировали в списке наибольших разрывов по задержке.

Результаты

Метрика	Значение
Обращения к fieldnorm до оптимизации	1 500 страниц
Обращения к fieldnorm после оптимизации	30 страниц
Рост индекса HN на 28.7M	около 9%
Чтения буфера в disjunction-запросе	упали примерно на 80%
Время запроса в том же случае	снизилось лишь на 5%
p50 для запроса с 10 термами	снизилась примерно в 6 раз
p95 для запроса с 10 термами	снизилась примерно в 8 раз
ParadeDB на HN 28.7M	в 2 раза быстрее TIN
ParadeDB QPS	344.6
TIN QPS	145.7

Оговорки

TIN затронул гораздо меньше страниц Postgres на запросе, и ParadeDB предположила, что это и есть основная причина его большей скорости. Это преимущество усилилось бы на датасете StackExchange, когда часть чтений идёт с диска. Но число страниц само по себе не показывает общую производительность: после оптимизации fieldnorms чтения буферов упали примерно на 80%, а время запроса — лишь на 5%, потому что узкое место сместилось на алгоритм. Сравнение QPS отражает конкретный набор запросов и корпус; на запросах, целиком состоящих из распространённых слов, TIN пропускает большую часть скоринга, что даёт приближение BM25, а не точные оценки.

Идентификаторы документов и их влияние на раскладку

ParadeDB использует u32 DocId, потому что плотные, отсортированные, уникальные целые числа лучше всего сжимаются, и большинство поисковых систем применяют u32 DocId. Переход на 48-битный идентификатор не даёт выигрыша сам по себе: 48 бит ctid — это конкатенация чисел из двух разных доменов — номеров блоков (миллионы) и смещений кортежей (не более 291).

Плотные u32 DocId упрощают связь postings с колоночным хранилищем: внутри сегмента документ 42 соответствует строке 42 в каждой колонке, поэтому значение можно получить напрямую. Это нужно для Top K по полю, range-фильтров и фасетов. ctid же указывает физическое место в Postgres, например страницу 190, слот 17, и не даёт позицию в колонке: чтобы получить значение, нужно сначала определить, какая строка колонки соответствует (190, 17), что требует отображения или эквивалентного поиска.

Компромисс в том, что при использовании ctid устраняется отображение между DocId и ctid и появляются эффективные bitmap-операции и проверки видимости, но ParadeDB всё равно нуждается в колоночном представлении для остальных поисковых задач. Если TIN решит его сделать, ей, вероятно, придётся заплатить ту же стоимость трансляции ctid/DocId, только в обратном направлении.

Что из этого следует на практике

Переупаковка fieldnorms рядом с postings — это обмен места на локальность: fieldnorm документа дублируется для каждого терма, но рост на реальных корпусах оказался умеренным (около 9% для индекса 28.7M), потому что у большинства термов короткие postings-списки. Выигрыш при этом неравномерен: для запросов с небольшим числом термов он огромен, а в disjunction-запросах с многими термами снижение чтений буферов почти не отражается на времени — узкое место уходит в алгоритм.

Когда снижение числа чтений буферов не даёт пропорционального ускорения, стоит смотреть на алгоритм прунинга, а не на ввод-вывод. Эвристика выбора между MAXSCORE и WAND по числу термов и плотности постингов позволяет не платить за менее подходящий алгоритм.

Прунинг сегментов безопасен по построению: он возвращает «не подходит» только при наличии статистики, чьи границы строго исключают значение, а при отсутствии статистики, NaN или несравнимости — «возможно». Это значит, что отсутствие статистик не приводит к пропуску совпадений, но и не даёт ускорения.

Выбор идентификатора документа — не деталь реализации, а решение, определяющее раскладку: плотные u32 DocId дают прямую связь postings с колоночным хранилищем и лучшее сжатие, тогда как ctid устраняет отображение и упрощает bitmap-операции и проверки видимости, но не даёт позицию в колонке.