xxhash для Postgres — быстрый поиск по текстовым ключам

[press_a_key]

Большая разрядность практически на нет сводит шансы коллизии, но если она и возникнет, достаточно добавить пробел к тексту для исправления ситуации.

Не совсем понял, а как потом искать по этому индексу, не зная, подвергся он коллизии или нет?

[Anrol]

r_o_m_k_o_l_a ответил исчерпывающе, я в итоге так и сделал, вспомнил сейчас. Добавление символов - суффиксов плохое решение. для поиска создается два хша - один от текста, другой от текста + суффикс. Плохо.

[r_o_m_k_o_l_a]

Спасибо за расширение, история с переполнением при клиентском хешировании знакома до боли.

Про коллизии. Формулировка «добавляем пробел, и конфликт решён» меняет исходные данные, и дальше сравнение по ключу перестаёт быть честным. Надёжнее считать хеш префильтром, а не идентичностью: искать по индексу на bigint, а совпадение подтверждать сравнением самой строки. Стоит это один лишний предикат в запросе, зато при коллизии вы получите две записи вместо одной молча склеенной. На 64 битах коллизия действительно редкая, но неприятность от неё не масштабируется вместе с вероятностью.

Про то, чтобы не ставить расширение. В самом Postgres уже есть hashtextextended(text, int8), отдаёт готовый bigint. Проверил на 17.9: hashtextextended('привет', 0) даёт 4964103119925780619. Для дедупликации при загрузке этого обычно достаточно, а расширение на прод-базе — отдельная история с обновлениями и правами.

И на случай, если хеш всё-таки считается снаружи и приходит беззнаковым: перевод в диапазон bigint делается без битовой магии, обычным сдвигом через numeric — (x::numeric - 18446744073709551616)::bigint. Для 18446744073709551615 получается -1.

[Anrol]

Проверил на 17.9: hashtextextended('привет', 0) даёт 4964103119925780619

Не совпадает с xxhash, свой алгоритм у postgres. Мне было важно генерировать одинаковый хэш везде, и в скриптах Питона и на сервере, это дает свободу.