https://news.ycombinator.com/item?id=41005355 статья от YDB как искали баги с помощью jepsen фреймворка, с ссылками на пр-ы

В последнее время я занимаюсь векторным поиском, поэтому захотелось написать про одну интересную и новую статью об этом.

https://research.google/blog/soar-new-algorithms-for-even-faster-vector-search-with-scann

Статья хорошо написана, но наверное будет сложно понять если не знать некоторых деталей:

Проблема:
Хочется быстро выдавать из n векторов top k ближайших по некоторой функции расстояния (max inner product, cosine, l2 distance, etc) к вектору q, dimensions которого d

Решения:
1. Последовательный перебор, работает за O(n * k * d), это ускоряется с помощью simd и thread параллелизма или даже gpu, но работает все равно не быстро (банально много нужно прочитать с диска).

1. Можно строить структуры данных подобные kd-tree/r-tree (разница в том, что первое про разбиение пространства, а второе про создание баундов).
   К сожалению они плохо работают на больших размерностях (> 3):
   2.1 kd потому что разбиение на каждом уровне происходит по одному из dimensions, а это мало что говорит о расстоянии для больших dimensions
   2.2 r потому что баунд боксы почти всегда оверлапятся

В итоге используются разные приблизительные методы, которые будут работать с recall < 1
recall = (count of approximate top k in exact top k) / k

Тут можно разделить на три подхода: quantization (уменьшение размера или размерности исходных данных), структуры данных для исходных данных, и комбинация этих двух подходов.

1. Как уменьшить объем исходных данных:
   1.1. scalar quantization -- обычно исходные вектора имеют координаты float32 => можно их преобразовать в int8, или даже более маленькие множества, это может дать ускорение в несколько раз (< 32).
   1.2 product quantization -- разобьём исходный вектор размера d на m частей, для каждой части сделаем k(256) кластеров (например с помощью kmeans). Затем для каждого вектора из датасета каждый из m кусочков заменим на индекс соответствующего ему кластера.
   В итоге вместо вектора из d float32, получим вектор из m uint8 (типичные значения m d/(4 ~ 16), соответственно типичное сжатие в 16-64 раза, с довольно хорошим качеством)

2.1 Какие структура данных используются?
1.1 hnsw, не буду описывать подробно, просто это вариант когда мы поверх исходного датасета строим примерный граф. Он наиболее популярный, так как имплементации достаточно простые (in memory как правило) и работают быстро на поиске. Из недостатков требует много памяти и медленный на построении. Есть интересные версии, DiskANN, с некоторыми заимствованиями из других подходов.
1.2 ivf -- разобьём исходные датасет на кластера каким то способом (например kmeans (scann -- google alloydb) или 2-means + randomize (annoy -- spotify)) и запишем к каждому из них список id исходных векторов
1.3 Предыдущий подход в чистом виде редко используется, ivf (kmeans) tree, аналогичен, только вместо того чтобы иметь огромные кластера, строится дерево из кластеров.

Ну и собственно интересный момент, в случае ivf подобных методов, чтобы вектора были более похожими (для более точной компрессии с помощью PQ), можно вместо исходных векторов компрессить cluster vector - cluster center, обозначим за r.

А теперь подходим к статье:

Когда вы используете ivf-like метод основное засчет чего вы теряете либо recall, либо rps это те вектора которые близки к границам кластеров.

Первая мысль которая приходит как это исправить: давайте id исходного вектора класть не в ближайший кластер, а в два ближайших.

На практике это даст незначительное улучшение.

В статье же рассказывается, что для inner product подобных расстояний, можно при выборе второго кластер хотеть чтобы r_1 и r_2 были почти ортогональны (если точнее, то угол влияет на выбор).

Это даёт качественное улучшение recall.

Все, можете идти открывать свой стартап про векторный поиск :)
А если серьезно, то специализированные базы данных векторного поиска это история только про хайп, там качественно ничего интересного не сделано к сожалению.

Почти все хорошее в этой области от пары рисерчей и google, ms, fb (и немного от нормальных баз данных, timescale pgvector например)

Мне вмержили коммит в абсеил, удивительное событие https://github.com/abseil/abseil-cpp/commit/cbfe51b2c01da330ff292b145de91346a5950163 А вообще хотел написать, что я недавно закончил работать в ArangoDB. Главное, я понял как можно делать поиск и как не…

Мне вмержили коммит в абсеил, удивительное событие
https://github.com/abseil/abseil-cpp/commit/cbfe51b2c01da330ff292b145de91346a5950163

А вообще хотел написать, что я недавно закончил работать в ArangoDB.
Главное, я понял как можно делать поиск и как не стоит делать базы данных ;)

Сейчас устроился в YDB в СПб офис, так что если есть кто-то кто не против познакомиться лично, я был бы рад.

GitHub

PR #1672: Optimize StrJoin with tuple without user defined formatter · abseil/abseil-cpp@cbfe51b

Imported from GitHub PR https://github.com/abseil/abseil-cpp/pull/1672 https://github.com/abseil/abseil-cpp/discussions/1671 Merge ddcbb2466b2c9c4048d60be7e58cf47f935c257d into eba8db7baf6c326870...

Забавная штука https://disc.bu.edu/papers/vldb23-mun

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

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

А вот как оптимизации для row oriented формата выглядит действительно прикольно, жаль мало применимо.

DiSC lab

On-the-fly Data Transformation in Action — DiSC lab

Proceedings of the VLDB Endowment, Vol. 16(12), 2023 Ju Hyoung Mun, Konstantinos Karatsenidis, Tarikul Islam Papon, Shahin Roozkhosh, Denis Hoornaert, Ahmed Sanaullah, Ulrich Drepper, Renato Mancuso, Manos Athanassoulis Official PDF | Local PDF | Code

Я конечно все понимаю, не очень популярный инвалидский дистрибутив и все дела. Но у всех зависает wildcard search по контенту пакетов в alpine? https://pkgs.alpinelinux.org/contents и попробовать поискать что-то в духе symbolizer

GitHub

lzcnt enabled varint size calculation for proto · protocolbuffers/protobuf@7315f6d

The x86 microbenchmark speedups here are only representative for packed repeated primitive fields, as they benefit from some improved vectorization. For normal cases like non-repeated fields, the ...

Я конечно все понимаю, не очень популярный ~~инвалидский~~ дистрибутив и все дела.
Но у всех зависает wildcard search по контенту пакетов в alpine?
https://pkgs.alpinelinux.org/contents и попробовать поискать что-то в духе *symbolizer*

Недавно в userver добавили реализацию счётчика на основе rseq -- restartable sequence.

Идея не новая и встречалась как один из юзкейсов, когда это все добавлялось в ядро (4.18).
Но в опенсурсе таких реализаций не встречал.

Основное преимущество перед per thread счётчиком, то что thread-ов обычно больше cpu-cores, и как следствие чтения получаются быстрее, а записи аналогичны.

Вообще впервые я встретил применение rseq в google tcmalloc, как замену per thread спискам блоков.
И на мой взгляд это одна из лучших идей, которые я видел в современных аллокаторах. Потому что для очень большого числа программ, это сильно улучшает использование памяти.

rseq исторически был сделан как раз для tcmalloc, хотя вероятно в гугле также заюзали и для метрикоподобных счётчиков.

Ещё из интересного в glibc 2.35 затащили инициализацию rseq и в целом начали использовать для sched_getcpu.
Вроде бы это произошло потому что пришли люди из mysql в redhat и сказали, а у нас медленно с вашим sched_getcpu, если сделать с rseq будет быстрее.
Юзкейс аналогичный, шардированный счётчик.

Недавно читал про разные olap query execution engines: velox, photon, etc. Есть интересный момент, о котором я думал раньше, но не встречал на практике. Предлагается для строковых функций (lower, upper, reverse, etc) делать предположение об инпуте, ASCII…

Недавно читал про разные olap query execution engines: velox, photon, etc.
Есть интересный момент, о котором я думал раньше, но не встречал на практике.

Предлагается для строковых функций (lower, upper, reverse, etc) делать предположение об инпуте, ASCII он или нет.

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

velox использует такой подход: Сделаем проверку на ASCII для инпута, если мы о нём ничего не знаем.
Как правило эту проверку нужно сделать только один раз для инпут данных, так как большинство строковых функций принимая ASCII вернут так же ASCII.
плюсы:
не требует ничего от стораджа
минусы:
определяет ASCII или нет каждый раз
значительная часть времени для ASCII строк уходит на проверку, если бы мы знали заранее, что у нас только ASCII, было бы быстрее
незначительно медленнее utf-8

photon менее понятно, так как кода нет, но можно сказать что они так же имеют специализированные варианты функций.
И возможно сохраняют некоторую мета информацию о колонке, насколько много в ней ASCII строк и нужно ли делать дополнительные проверки.
плюсы:
читай минусы velox
минусы:
дополнительные вычисления на вставке/компактизации данных

В заключение скажу что мне стало куда более очевидно, что для любой обработки строк стоит хотя бы сделать ASCII специализацию, и проброс ASCII or UTF-8, чтобы не считать это каждый раз.
Например в lucene, да и у нас в поисковом движке, этого нет (при вставке текста, он проходит через множество функций токенизации), а сейчас я уверен, что это стоило бы попробовать сделать.

Ещё есть прикольный момент, который я подсмотрел в реализации velox: часто специализация строковой функции для ASCII, реализацией совпадает с аналогом для последовательности байт, соответственно код можно переиспользовать.

https://vldb.org/pvldb/vol15/p3372-pedreira.pdf
https://people.eecs.berkeley.edu/~matei/papers/2022/sigmod_photon.pdf