Для чего нужен TIN
Разработчики приложений используют текстовые индексы для реализации различных поисковых функций. Платформа электронной коммерции может искать топ-10 товаров, содержащих все ключевые слова в запросе:
SELECT * FROM products
WHERE description ==> 'stretch denim jeans'
ORDER BY tin.score(ctid) DESC
LIMIT 10Платформа для судебного обнаружения документов может выдавать каждый документ, содержащий одно или несколько ключевых слов, без забот о ранжировании:
SELECT * FROM emails
WHERE body ==> '[insider trading conspiracy]'Платформа для тегирования фотографий может показывать точное количество снимков с определённым тегом:
SELECT COUNT(*) FROM photos
WHERE tags ==> '"san francisco"';Большинству приложений также необходимо вставлять, обновлять и удалять документы даже при одновременном выполнении поисковых запросов. Результаты поиска должны включать новые или изменённые строки сразу же после фиксации транзакции.
Производительность TIN и бенчмарки
Команда провела бенчмарки для оценки производительности всех описанных выше сценариев и ещё нескольких. Проверялись рабочие нагрузки с:
- Запросами с конъюнкцией (все слова), дизъюнкцией (любое слово) и фразовыми запросами, а также комбинированными запросами.
- Подсчётом документов или выборкой топ-k по BM25.
- Одновременным написанием новых данных в индекс или без него.
Корпусы и рабочие нагрузки
TIN тестировался на различных текстовых корпусах: вся Википедия, коллекция комментариев Reddit объёмом 2,3 ТБ и смешанная нагрузка под названием «pile» с 797 ГБ открытых исследовательских работ, юридических документов, книг из публичного доступа и писем Enron. Результаты в статье получены из экспорта вопросов и ответов со Stack Exchange — корпус объёмом 85 ГБ с 150 млн документов.
Синтетическая выборка запросов была сгенерирована путём случайной выборки подстрок от 2 до 15 терминов. Каждую подстроку интерпретировали тремя способами: как конъюнкцию, как дизъюнкцию и как фразовый запрос — всего 1719 запросов.
Окружение тестирования
Бенчмарки запускались на AWS i7i.8xlarge EC2 с локальным NVMe хранилищем и современным CPU с поддержкой AVX-512. Для каждого расширения полнотекстового поиска настраивался PostgreSQL 18.6 в изолированном контейнере с ограничением 8 vCPU и 32 ГБ RAM — достаточно маленькой конфигурации для демонстрации производительности, когда индекс не помещается полностью в буфер PostgreSQL.
Фазы тестирования выполнялись последовательно, поэтому системы не конкурировали за ресурсы. Выбран выделенный EC2 экземпляр для минимизации операционных издержек, репликации и обеспечения воспроизводимости бенчмарков.
Для генерации поискового трафика использовался ParadeDB Benchmarker с собственной модификацией, добавляющей прогрев кэша перед измерением и метрики для прочитанных байт и WAL. Параметры PostgreSQL оставлены по умолчанию, кроме трёх: max_parallel_workers установлен на 8 (вместо 40), shared_buffers на 24 ГБ (вместо 128 МБ) и maintenance_work_mem на 24 ГБ (вместо 64 МБ) для соответствия ресурсам контейнера. Benchmarker запускался на том же EC2 экземпляре, что и целевой PostgreSQL, чтобы избежать влияния сетевой латентности.
Производительность TIN v1.0.2 сравнивалась со всеми другими индексами полнотекстового поиска PostgreSQL, способными выполнить рабочую нагрузку: ParadeDB v0.25.2, pg_textsearch v1.4.0 и встроенный GIN из PostgreSQL v18.6. Помимо TIN, только ParadeDB смог завершить все бенчмарки.
Время создания и размер индекса
Индексы занимали от 33% до 61% размера корпуса, их создание заняло от 8 до 129 минут. Три других системы исчерпали лимит в 32 ГБ RAM контейнера, поэтому для построения индексов была увеличена доступная памяти, как показано в таблице. Перед выполнением запросов контейнер вернули к 32 ГБ для всех.
| Общее время | Размер индекса | Требуемая RAM | |
|---|---|---|---|
| TIN | 8m10s | 50.7 GB | 32 GB |
| ParadeDB | 19m20s | 52.1 GB | 64 GB |
| pg_textsearch | 26m49s | 41.5 GB | 128 GB |
| Postgres GIN | 2h09m04s | 28.0 GB | 64 GB |
Смешанные запросы, топ-10 по рейтингу
Первый бенчмарк сравнивает TIN с ParadeDB для смешанных (конъюнкция, дизъюнкция, фраза) запросов с выборкой топ-10 результатов по BM25 без одновременного записи в индекс. TIN обрабатывает в 25 раз больше запросов в секунду, чем ParadeDB, с задержкой p99 в 26 раз ниже. GIN не может завершить этот бенчмарк, поскольку исчерпывает память при поиске дизъюнкций. pg_textsearch не выполняет бенчмарк, так как обрабатывает только дизъюнкции.
Конъюнкция и фразовые запросы, топ-10 по рейтингу
Следующий бенчмарк сравнивает TIN с ParadeDB и Postgres GIN для топ-10 запросов с конъюнкцией и фразами без записи. TIN и ParadeDB используют BM25 для ранжирования, GIN — ts_rank_cd. TIN обрабатывает в 10 раз больше запросов, чем ParadeDB, и в 541 раз больше, чем GIN, с задержкой p99 соответственно в 6 и 1356 раз ниже. pg_textsearch снова отсутствует, так как обрабатывает только дизъюнкции.
Дизъюнкция с одновременной записью
Третий результат сравнивает TIN с ParadeDB и pg_textsearch для дизъюнкции, топ-10 по BM25 с клиентом, целящимся на 1000 запросов UPDATE в секунду. TIN обрабатывает в 36 раз больше запросов, чем pg_textsearch, и в 57 раз больше, чем ParadeDB, с задержкой p99 на 24 и 36 раз ниже соответственно. За десятиминутный прогон TIN выполняет 270 279 обновлений, ParadeDB — 185 584, pg_textsearch — всего 735.
Подход ParadeDB к приёму записей снижает пропускную способность чтения и задержку. pg_textsearch поддерживает одинаковые 3,5 QPS для читателей с записью и без, поскольку непрерывный трафик чтения предотвращает получение записью необходимых блокировок — записи зависают через несколько секунд. GIN снова отсутствует, так как исчерпывает память на дизъюнкциях.
Когда индекс помещается в памяти
В начале упоминалось, что TIN неимоверно быстр. Последний график показывает, что могут сделать TIN, ParadeDB и Postgres GIN, когда индекс полностью помещается в shared buffers. Рабочая нагрузка считает (но не ранжирует) документы, соответствующие дизъюнкции, по Википедии — корпусу объёмом 8,0 ГБ. pg_textsearch отсутствует здесь, так как может выполнять только топ-k запросы, не подсчёт.
Полные результаты
Это, пожалуй, достаточно графиков, но это не охватывает все сценарии. Вот те же ситуации плюс несколько дополнительных в табличной форме. Колонка «MB/query» показывает, сколько данных каждый индекс прочитал с диска или кэша блоков на запрос. Меньшие числа TIN для MB/query — часть того, почему оно быстрее, и они также снижают влияние запросов TIN на кэш блоков и ёмкость I/O, благодаря чему другие запросы на том же сервере остаются быстрыми.
Конъюнкция, дизъюнкция и фразовые запросы; топ-10
┌────────────────────────────────────────────────────────────────────┐
│ QPS p99 MB/query Updates │
├─────────────────────────┬───────┬──────────┬───────────┬───────────┤
│ TIN - read-only │ 199 │ 256ms │ 65 │ │
│ - with updates │ 172 │ 284ms │ 88 │ 271,398 │
├─────────────────────────┼───────┼──────────┼───────────┼───────────┤
│ ParadeDB - read-only │ 7.9 │ 6,765ms │ 582 │ │
│ - with updates │ 6.0 │ 7,990ms │ 591 │ 193,487 │
└─────────────────────────┴───────┴──────────┴───────────┴───────────┘Конъюнкция и фразовые запросы; топ-10 (только чтение)
┌───────────────────────────────────────────────┐
│ QPS p99 MB/query │
├───────────┬───────┬───────────┬───────────┤
│ TIN │ 242 │ 212ms │ 73 │
├───────────┼───────┼───────────┼───────────┤
│ ParadeDB │ 24 │ 1,279ms │ 668 │
├───────────┼───────┼───────────┼───────────┤
│ Postgres GIN │ 0.4 │ 288,066ms │ 595 │
└───────────┴───────┴───────────┴───────────┘Дизъюнкция запросов; топ-10
┌────────────────────────────────────────────────────────────────────────┐
│ QPS p99 MB/query Updates │
├──────────────────────────────┬───────┬───────────┬─────────┬───────────┤
│ TIN - read-only │ 148 │ 324ms │ 48 │ │
│ - with updates │ 125 │ 354ms │ 77 │ 270,279 │
├──────────────────────────────┼───────┼───────────┼─────────┼───────────┤
│ ParadeDB - read-only │ 17 │ 2,385ms │ 303 │ │
│ - with updates │ 2.2 │ 12,634ms │ 394 │ 185,584 │
├──────────────────────────────┼───────┼───────────┼─────────┼───────────┤
│ pg_textsearch - read-only │ 3.5 │ 8,646ms │ 11,639 │ │
│ - with updates │ 3.5 │ 8,409ms │ 11,656 │ 735 │
└──────────────────────────────┴───────┴───────────┴─────────┴───────────┘Конъюнкция, дизъюнкция и фразовые запросы; COUNT(*) (только чтение)
┌─────────────────────────────────────────┐
│ QPS p99 MB/query │
├───────────┬───────┬──────────┬──────────┤
│ TIN │ 179 │ 438ms │ 97 │
├───────────┼───────┼──────────┼──────────┤
│ ParadeDB │ 10 │ 2,704ms │ 544 │
└───────────┴───────┴──────────┴──────────┘Дизъюнкция запросов; COUNT(*); корпус Википедии (только чтение)
┌───────────────────────────────────────────────────┐
│ QPS p99 MB/query │
├───────────────┬──────────┬─────────────┬──────────┤
│ TIN │ 10,260 │ 2ms │ 1.7 │
├───────────────┼──────────┼─────────────┼──────────┤
│ ParadeDB │ 291 │ 95ms │ 22 │
├───────────────┼──────────┼─────────────┼──────────┤
│ Postgres GIN │ 1.4 │ 30,292ms │ 2.5 │
└───────────────┴──────────┴─────────────┴──────────┘Как видно, в широком диапазоне сценариев TIN имеет пропускную способность как минимум в 8 раз выше конкурентов, читает намного меньше данных с диска и показывает лишь небольшое снижение производительности даже при обновлении сотен строк в секунду.
Почему TIN быстр
Производительность TIN в бенчмарках может быть трудноверна. Чтобы сделать её более убедительной или удовлетворить любопытство читателя, стоит объяснить архитектурные решения, обеспечивающие такую скорость. Вкратце: все постинги документов — это PostgreSQL ctid вместо последовательных идентификаторов документов, что позволяет использовать высоко векторизованные операции пересечения и объединения на современных CPU.
Идентификация документов
Текстовому индексу требуется идентификатор для каждой версии каждого документа, который он индексирует. Идентификаторы группируются в сильно сжатые списки постингов; каждый список отслеживает все документы, содержащие одно данное слово. В большом корпусе список постингов для частого слова вроде «the» может содержать миллиарды постингов, а для редкого термина вроде «xyz-9876» — всего несколько.
Большинство систем полнотекстового поиска организуют индексы в сегменты. Документы n, чьи постинги существуют в сегменте, обычно получают идентификаторы от 1 до n. Последовательные идентификаторы документов позволяют сжимать списки постингов, используя различные техники вроде дельта-кодирования и битовой упаковки. Но это также означает, что идентификаторы документов в разных сегментах назначаются независимо; ID документа 42 в сегменте 4 — совершенно другой документ, чем ID 42 в сегменте 7.
TIN также организует индекс по сегментам, но не для целей нумерации документов. Вместо этого TIN напрямую использует значение ctid PostgreSQL в качестве идентификатора документа.
Каждая версия каждой строки (кортежа), хранящейся в таблице PostgreSQL, имеет связанное значение ctid. ctid расшифровывается как «current tuple identifier» (текущий идентификатор кортежа). Любая вставленная или обновлённая строка получает новый ctid. Это 48-битное число, которое напрямую идентифицирует физическое местоположение кортежа в heap'е PostgreSQL. В текстовом представлении как (<номер блока>, <номер смещения>) верхние 32 бита указывают номер блока, а нижние 16 указывают смещение в этом блоке. Дальше верхнюю часть будут называть «номер страницы» или просто «страница».
Имея ctid (190, 17), известно, что представляемый кортеж находится на 17-й позиции на странице 190. Мгновенный поиск O(1)! Можно даже запрашивать и извлекать строки из heap'а напрямую, используя ctid:
-- получить первые 10 строк из "books" в физическом порядке heap'а
SELECT ctid, id, title FROM books ORDER BY ctid LIMIT 10;
-- не требуется сканирование! мгновенный O(1) поиск строки
SELECT * FROM books WHERE ctid = '(190, 17)';TIN напрямую использует ctid, потому что PostgreSQL тоже их использует внутри. Расширения PostgreSQL, реализующие новый тип индекса, должны возвращать ctid. Bitmap scan'ы в PostgreSQL поддерживаются потенциально неточными битовыми картами ctid. Внутренние типы индексов PostgreSQL (B-Tree, GIN, GiST и hash) используют ctid в качестве постингов. ctid есть везде в PostgreSQL.
Чтобы работать внутри PostgreSQL, система полнотекстового поиска, которая назначает последовательные идентификаторы, должна в какой-то момент преобразовать эти идентификаторы обратно в ctid для работы с PostgreSQL. И ParadeDB, и pg_textsearch поддерживают отдельную структуру данных именно для выполнения этого отображения. Если поиск по тексту соответствует 10 млн строк, ParadeDB и pg_textsearch должны выполнить 10 млн поисков идентификаторов в своих ctid отображениях. TIN полностью избегает этой работы.
48-битные идентификаторы — это сумасшествие
Обычные техники сжатия списков постингов плохо работают с несмежными 48-битными числами. Дельта-кодирование разрывается на границах каждой страницы, а битовые карты слишком разреженные для эффективности. К счастью, некоторые интересные свойства страниц PostgreSQL делают двухуровневое битовое кодирование практичным. Страница объёмом 8 КБ не может содержать более 291 кортежа (8192 байта минус 24 для заголовка страницы, делённое на минимум 28 на непустой кортеж), а для схем таблиц с TEXT и прочими колонками страницы часто содержат 32 или меньше кортежа.
Таким образом, список номеров страниц достаточно плотный для использования битовой карты, а внутри каждой страницы список номеров смещений достаточно плотный (и достаточно маленький) для использования крошечных битовых карт на страницу.
Сбережения по сравнению с наивным хранением 48-битных ctid значительны. Над всем корпусом часто встречающиеся термины приближаются к 1 биту на постинг, среднечастотные термины осели около 7 бит на постинг, а редкие термины могут приближаться к 25 битам на постинг. Термины, появляющиеся только один раз, вообще не хранятся как битовые карты.
Элизия работы и векторизация
Битовые карты уровня страницы TIN (какие страницы содержат данный термин) имеют 256 бит, что хорошо подходит для векторных регистров на любом x86 CPU с AVX2 или выше. Это позволяет несколько оптимизаций.
Рассмотрим запрос the AND rareword. TIN выполняет AND над битовыми картами уровня страницы — 256 бит (страниц) за раз. Любой бит, отсутствующий в пересечении, — это страница, чьи битовые карты уровня смещения TIN вообще не нужно декодировать.
Для COUNT(*) запросов дизъюнкции вроде the OR rareword TIN часто пропускает чтение списков постингов полностью. Метаданные индекса TIN хранят точные счётчики постингов каждого термина. Если битовые карты уровня страницы двух слов не имеют общих бит, то подсчёт их дизъюнкции — это просто сумма этих точных счётчиков постингов.
Каждая битовая карта уровня страницы помещается в один регистр AVX2, а каждая битовая карта уровня смещения помещается либо в один регистр AVX-512, либо в два регистра AVX2. Запросы конъюнкции и дизъюнкции — это просто инструкции AND и OR над этими векторными регистрами соответственно. Запросы, подсчитывающие количество совпадений, могут использовать встроенные инструкции CPU POPCNT для подсчёта бит в результирующей битовой карте. Дорогостоящие циклы и инструкции ветвления в значительной степени избегаются.
Запрос, желающий строк, а не счётчиков, вычисляет ctid из позиции бита, не получая его с диска. Позиция установленного бита является ctid.
Идентификаторы ctid документов, которые TIN возвращает PostgreSQL из данного сегмента, естественно идентифицируют страницы и кортежи внутри страницы в heap'е порядке. Это означает, что когда PostgreSQL нужно прочитать соответствующие кортежи из heap'а, это происходит в heap'е порядке. Даже на современных NVMe дисках последовательный доступ намного быстрее случайного; TIN получает эту оптимизацию бесплатно.
Решение MVCC
TIN возвращает результаты, корректные относительно MVCC, что означает, что выполняемое в любой момент времени выражение видит или работает только с кортежами, которые в данный момент видны ему. Это означает, что каждый результат запроса, поддерживаемый heap'ом, нуждается в проверке видимости относительно текущего снимка.
Проверки Heap'а
Есть несколько различных подходов к этому. Некоторые запросы по своей природе проверяются heap'ом:
SELECT a, b, c FROM lyrics WHERE content ==> 'give you up'Поскольку запрос возвращает фактические данные heap'а (колонки a, b, c), TIN должен получить из heap'а все совпадающие ctid, возвращённые ==> 'give you up' в любом случае. Когда TIN запрашивает у PostgreSQL физические данные кортежа за каждым ctid, PostgreSQL говорит TIN'у, видим ли этот кортеж текущему снимку. Если да, TIN его возвращает; в противном случае TIN переходит к следующему совпадающему ctid, пока все видимые совпадения не будут возвращены.
Карта видимости
Другие формы запросов могут выполняться подобно PostgreSQL «Index Only Scan», где ответ возвращается напрямую из индекса без касания heap'а (или по крайней мере с надеждой не касаться весь heap).
Рассмотрим запрос подсчёта только вроде:
SELECT COUNT(*) FROM lyrics WHERE content ==> 'give you up'Если каждая страница heap'а помечена как все-видимая, TIN может вернуть этот счёт, не касаясь ни одной страницы heap'а.
Не все данные статичны, конечно, и в случае мутировавших heap'ов TIN выполняет дополнительные оптимизации, чтобы гарантировать подсчёт только видимых строк, выполняя прямые пересечения с картой видимости PostgreSQL. Битовые карты уровня страницы TIN точно подходят для эффективного пересечения с картами видимости PostgreSQL, которые также являются битовыми картами уровня страницы. Только ctid на не-все-видимых страницах нуждаются в проверке против heap'а. Обычно индекс PostgreSQL возвращает все ctid, соответствующие независимо от видимости, а исполнитель PostgreSQL проверяет видимость каждого. TIN планирует пользовательские сканирования, которые перемещают проверки видимости в сам TIN, где они могут воспользоваться векторными инструкциями на битовых картах уровня страницы.
VACUUM и карта живучести TIN
Текстовые индексы, которые поддерживают удаление документов, обычно хранят какой-то список «tombstone» (надгробия), подходящий для их движка. TIN не исключение. TIN хранит карту живучести на сегмент, один бит на ctid, организованный так же, как работают битовые карты уровня страницы и смещения. Когда VACUUM запускается и определяет, что ctid был удалён из heap'а (в результате UPDATE или DELETE), TIN очищает бит живучести этого ctid. Группы страниц с по крайней мере одним очищенным битом помечаются, и когда запрос касается помеченной группы страниц, TIN также выполняет AND над битовыми картами смещения из списка постингов против карты живучести, поэтому никогда не возвращает и не подсчитывает кортеж, который действительно был удалён.
Сегменты и слияние
Когда впервые создаёт новый индекс для таблицы, TIN создаёт n неизменяемых сегментов, каждый содержащий постинги для 1/n страниц, связанных с этой таблицей в heap'е. По мере изменения данных TIN создаёт изменяемые сегменты, менее эффективные для поисков, но позволяющие легко вставлять новые документы. В конечном итоге фоновый воркер повышает каждый изменяемый сегмент до неизменяемого сегмента: неизменяющийся, но намного более эффективный для поиска.
Со временем TIN начнёт слиять неизменяемые сегменты в большие неизменяемые сегменты. Это также происходит в фоне.
Системы текстового индексирования, которые используют последовательные идентификаторы документов, обязаны переименовать все документы, когда создают новый слитый сегмент. Как упоминалось выше, ID документа 42 в сегменте 4 не то же самое, что ID 42 в сегменте 7. Таким образом, когда сегменты 4 и 7 слиты, должна быть применена новая нумерация к объединённому набору документов и вся информация каждого сегмента переупаковывается, переустанавливается и переписывается. Хотя слияние двух сегментов требует не совсем 2× хранилища, оно может быть близко.
TIN не страдает от проблемы переименования и связанных с ней побочных эффектов усиления записи.
Поскольку TIN использует значения PostgreSQL ctid в качестве идентификаторов документов, переименовывать нечего. Постинг вроде (190, 17) означает одно и то же в каждом сегменте. Битовые карты уровня страницы и смещения означают одно и то же в каждом сегменте. Когда TIN слиивает сегменты, многие битовые карты из каждого старого сегмента можно переиспользовать без изменений в новом сегменте. Их не нужно переустанавливать или даже копировать; TIN может просто переносить права владения битовыми картами, хранящимися на диске, из старых сегментов в новый. Это уменьшает усиление записи и экономит большую часть CPU и I/O затрат, обычно связанных с слиянием сегментов.
Заключение
Вот почему TIN как минимум в 8 раз быстрее в каждом бенчмарке: побочные эффекты выбора ctid в качестве собственного формата для каждого постинга в индексе.
Чтобы увидеть, как быстро TIN работает с текстовыми данными, можно больше узнать о функциональности или перейти прямо к руководству по началу работы.