[Перевод] Пересчёт расстояний в KNN-поиске: сокращаем разрыв между колоночным и построчным хранением

Manticore поддерживает построчное и колоночное хранение атрибутов. Построчное хорошо работает, когда данные помещаются в память. Колоночное особенно полезно, когда памяти не хватает: если запросу нужны лишь несколько атрибутов, читать и кешировать приходится в основном их, а не все данные подряд.

Но в KNN-поиске между двумя способами хранения была заметная разница в скорости. Для кандидатов, найденных HNSW, Manticore пересчитывает расстояния (rescoring) по исходным векторам без квантизации. При прежнем способе чтения колоночных данных этот этап занимал гораздо больше времени, чем при построчном хранении. В нашем тесте на DBpedia построчное хранение обрабатывало в 2,80–3,53 раза больше KNN-запросов в секунду.

Дело было не в самом колоночном хранении. Каждый вектор читался в один и тот же буфер и мог затереть предыдущий, поэтому Manticore не мог сохранить указатели на несколько векторов и обработать их вместе.

Мы изменили способ чтения колоночных данных: теперь файлы отображаются в память через mmap. Адреса векторов больше не меняются, когда читаются следующие векторы, а операционная система по-прежнему сама загружает нужные страницы файлов и освобождает память по мере необходимости. В результате Manticore стал обрабатывать в 2,57–3,13 раза больше KNN-запросов в секунду — это 85–92% от результата построчного хранения. При этом колоночное хранение по-прежнему хорошо работает с данными, которые не помещаются в память.

Насколько медленнее пересчёт расстояний при колоночном хранении?

Мы измерили скорость KNN-поиска на 16-ядерном AMD Ryzen 9 5950X на данных DBpedia:

• 975 000 векторов

• Размерность векторов — 1536

• 1-битная квантизация

• 5000 разных запросов за запуск

• Данные помещаются в память

• Oversampling и пересчёт расстояний - по умолчанию

Сначала мы сравнили построчное и колоночное хранение векторов:

Во всех трёх замерах построчное хранение обрабатывало в 2,80–3,53 раза больше запросов в секунду.

Обход графа в обоих случаях занимает одинаковое время. Разница возникает при пересчёте расстояний.

Почему важны настройки по умолчанию

По умолчанию при KNN-поиске Manticore отбирает кандидатов с запасом (oversampling), а затем пересчитывает для них расстояния:

• oversampling=3.0 утраивает запрошенное k перед поиском по HNSW. Так приближённый поиск находит больше кандидатов, чем запрос должен вернуть.

• rescore=1 читает исходные 32-битные векторы кандидатов, пересчитывает расстояния до них, заново сортирует кандидатов и возвращает k лучших.

То есть по умолчанию запрос выполняется так:

запрос k результатов -> отбор до 3 x k кандидатов -> пересчёт расстояний -> возврат k результатов

Поэтому значения k из теста нужно читать так:

Например, при k=500 поиск по HNSW идёт с k, равным 1500. Для найденных кандидатов расстояния пересчитываются точно, и возвращаются 500 лучших. Сколько раз на самом деле придётся читать данные с диска, зависит от фильтров, дисковых чанков и числа доступных кандидатов. Но цель остаётся прежней: найти втрое больше кандидатов, чем нужно результатов.

Oversampling и пересчёт расстояний улучшают качество ранжирования, особенно при работе с квантизованными векторами. Если их отключить, изменится привычный баланс между качеством и скоростью поиска. Поэтому ускорение поиска с настройками по умолчанию напрямую сказывается на обычных KNN-запросах.

Поиск по графу одинаковый, доступ к векторам — разный

При построчном и колоночном хранении поиск по графу HNSW работает одинаково: он ищет кандидатов в приближённом индексе и возвращает ID найденных документов. Способ хранения векторов начинает влиять на скорость только после этого — когда для пересчёта расстояний нужны исходные векторы кандидатов без квантизации.

При построчном хранении у каждого вектора в памяти есть свой адрес, который не меняется при чтении других векторов. Поэтому Manticore может сохранить указатели на несколько векторов, заранее подгрузить их данные и посчитать сразу несколько расстояний.

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

Чем больше размерность векторов и чем выше k, тем сильнее это замедляет поиск. В тесте это видно на примере 60, 300 и 1500 кандидатов, но и при других значениях k причина замедления та же.

Обход HNSW в обоих случаях одинаковый, так что разница в скорости объясняется именно пересчётом расстояний.

Зачем тогда нужно колоночное хранение?

Колоночное хранение создавалось для случаев, когда все значения нужного атрибута не помещаются в память. При таком хранении значения одного атрибута лежат рядом. Например, страница файла, которую запрос читает ради price, содержит в основном другие значения price, а не цены вперемешку с категориями, датами и прочими атрибутами.

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

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

У замедления была причина попроще: при пересчёте расстояний векторы из разных мест файла читались через один и тот же буфер.

Как мы изменили чтение колоночных данных

С mmap у каждого вектора в колоночном файле появляется постоянный адрес.

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

Для пересчёта расстояний важно именно то, что адрес вектора не меняется при чтении других векторов. Его данные теперь доступны напрямую, без копирования в общий буфер. Это позволяет Manticore:

1. Сортировать кандидатов по дисковому чанку и row id, чтобы читать данные, которые лежат рядом.

2. Собирать указатели на векторы в группы до 256 кандидатов.

3. Заранее подгружать данные векторов.

4. Считать расстояния для всей группы: где возможно — обрабатывать векторы попарно, а оставшиеся — по одному.

Иными словами, mmap позволяет пересчитывать расстояния сразу для нескольких векторов — так, как Manticore уже делал при построчном хранении.

Когда данные помещаются в память: разрыв почти исчезает

Мы повторили тест на DBpedia с режимом mmap для колоночных данных и сравнили все три варианта:

При k=20 производительность при колоночном хранении выросла со 178 до 509 запросов в секунду (QPS) — в 2,86 раза по сравнению с режимом file. При k=100 — с 97 до 304 QPS, то есть в 3,13 раза. При k=500 — с 61 до 157 QPS, в 2,57 раза.

В режиме file скорость поиска с колоночным хранением составляла 28–36% от скорости с построчным. С mmap — уже 85–92%. Отставание от построчного хранения — 15,4% при k=20, 11,1% при k=100 и 8,2% при k=500.

Разрыв сокращается с ростом k, и это объяснимо: чем выше k, тем больше расстояний нужно пересчитать и тем больше выигрыш от обработки векторов группами. При k=500 колоночное хранение с mmap отстаёт от построчного всего примерно на 8%, а раньше работало примерно втрое медленнее.

В этом тесте данные помещались в память. Теперь посмотрим, что происходит, когда памяти не хватает, — именно для таких случаев и создавалось колоночное хранение.

Когда данные не помещаются в память: тест на taxi

Обычные поисковые запросы мы проверили на том же Ryzen 9 5950X, но на гораздо более объемном датасете taxi:

• 1,74 млрд документов

• 32 дисковых чанка

• 372 ГБ — полный размер таблицы

• 88 ГБ — размер колоночных файлов .spc, к которым обращались запросы

• 32 ГБ — лимит памяти Docker-контейнера

Объём колоночных данных, нужных запросам, в 2,75 раза превышал лимит памяти контейнера. Часть памяти занимал сам сервер, так что для страниц файлов оставалось меньше 32 ГБ. В таких условиях системе во время выполнения запросов приходится выгружать одни страницы и читать с диска другие.

Мы выполнили один и тот же набор запросов на двух вариантах данных:

• taxi: полная таблица из 1,74 млрд документов, которая не помещается в память.

• taxi1: один дисковый чанк, данные которого помещаются в память.

Всего было 17 запросов: полнотекстовый поиск, агрегации без фильтров, фильтры по равенству и диапазону, поиск по индексам и GROUP BY с большим и малым числом уникальных значений. Эти же запросы к taxi мы используем в открытых сравнительных тестах на db-benchmarks.com.

Для каждого режима доступа мы трижды выполнили весь набор запросов. Ниже приведено среднее арифметическое времени выполнения по данным сервера за эти три запуска. “Усы” на диаграмме показывают минимум и максимум. Каждое значение — суммарное время всех 17 запросов.

Результаты с холодным и прогретым кешем мы рассматриваем отдельно:

• Холодный кеш — первый измеряемый запуск запроса после сброса кеша.

• Прогретый кеш — среднее время 10 повторных запусков каждого запроса на taxi и 50 — на taxi1.

Запуски с холодным кешем

Меньше — лучше.

На всей таблице taxi с холодным кешем mmap оказался на 0,28% медленнее — разница несущественная.

На одном чанке, который помещается в память, mmap был на 1,54% быстрее: 832,667 мс против 845,667 мс. Выигрыш небольшой.

Запуски с прогретым кешем

Меньше — лучше.

На таблице, которая не помещается в память, с прогретым кешем mmap оказался на 0,12% медленнее — разница опять несущественная.

На чанке, который помещается в память, mmap был на 1,00% быстрее: 751,087 мс против 758,667 мс. Некоторые запросы с группировкой и фильтрами по диапазону ускорились, а отдельные простые агрегации немного замедлились. В целом скорость почти не изменилась.

И с холодным, и с прогретым кешем mmap почти не меняет скорость поиска без KNN. Когда нужные запросам колоночные файлы были больше доступной памяти, разницы практически не было. Когда один чанк помещался в память, mmap оказался немного быстрее.

Почему скорость поиска без KNN почти не изменилась

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

В Linux и обычное чтение файлов, и mmap работают через один и тот же страничный кеш ядра. В режиме file данные из кеша копируются в буфер приложения. С mmap приложение обращается к страницам файла напрямую через своё адресное пространство; если нужной страницы ещё нет в памяти, происходит page fault, и система её подгружает. Лимит памяти, механизмы вытеснения страниц и накопитель в обоих случаях одни и те же.

Этим и объясняется, почему скорость поиска без KNN почти не меняется. mmap позволяет сохранять указатели на векторы и пересчитывать расстояния группами, но загрузкой и выгрузкой страниц файлов в обоих режимах по-прежнему управляет операционная система.

Итоги

При настройках по умолчанию на пересчёт расстояний может уходить значительная часть времени KNN-поиска. Поиск отбирает втрое больше кандидатов, чем нужно результатов: для 500 результатов HNSW сначала ищет с k, равным 1500, а затем Manticore пересчитывает расстояния. Чем выше k, тем больше работы. Раньше при колоночном хранении в режиме file векторы читались по одному, и из-за этого Manticore обрабатывал на 64–72% меньше KNN-запросов в секунду, чем при построчном хранении, хотя обход HNSW работал одинаково.

С mmap адреса векторов не меняются при чтении следующих векторов, поэтому Manticore может обрабатывать их группами. На DBpedia Manticore с колоночным хранением стал обрабатывать в 2,57–3,13 раза больше запросов в секунду — это 85–92% от того, что даёт построчное хранение.

Тесты в условиях ограниченной памятью показали, что колоночное хранение сохранило и своё главное преимущество. Запросы обращались к 88 ГБ колоночных данных, а контейнеру было доступно всего 32 ГБ памяти. При этом время поиска без KNN выросло лишь на 0,28% с холодным кешем и на 0,12% с прогретым. На одном чанке, который помещался в память, время даже немного сократилось: на 1,54% с холодным кешем и на 1,00% с прогретым. В итоге пересчёт расстояний при стандартных настройках KNN стал значительно быстрее, а скорость поиска без KNN почти не изменилась — и когда памяти хватало, и когда её было мало. Поэтому теперь mmap используется для доступа к колоночным данным по умолчанию.

Настройка доступа к колоночным данным

Способ чтения колоночных файлов задаёт параметр access_columnar_attrs. По умолчанию это mmap, поэтому отдельно настраивать каждую таблицу не нужно. При создании таблицы режим можно указать явно:

CREATE TABLE products (
    title TEXT,
    embedding FLOAT_VECTOR
        KNN_TYPE='hnsw'
        KNN_DIMS='1536'
) ENGINE='columnar'
  access_columnar_attrs='mmap';

Прежний режим file тоже доступен. Чтобы использовать его по умолчанию на всём сервере, добавьте настройку в секцию searchd конфигурационного файла:

searchd {
    access_columnar_attrs = file
}

Этот параметр меняет только способ чтения колоночных файлов. Формат данных и синтаксис KNN-запросов остаются прежними.