ПостПрочитал статью, первый раз столкнулся с таким явным вариантом рекурсивного сжатия https://15721.courses.cs.cmu.edu/spri…

Прочитал статью, первый раз столкнулся с таким явным вариантом рекурсивного сжатия https://15721.courses.cs.cmu.edu/spring2024/papers/03-data2/kuschewski-sigmod23.pdf Как по мне идея прикольная и достаточно простая: 1) Возьмём несколько простых и хороших алгоритмов сжатия, применим лучший из них 2) Затем сделаем тоже самое к получившимся данным 3) Делаем так пока это имеет смысл Нюанс, для того чтобы сделать шаг 1, нам нужно выбрать из н алгоритмов. Сделать это обычно можно только применив конкретные алгоритмы к данным, и выбрав тот, с которым получается лучше. Собственно в пейпере предлагается применять только к 1% данных от 64k энтрей в колонке, утверждается что получается при этом весьма хорошо. Вообще если вы не очень знакомы с открытыми форматами колоночного хранения данных, мне кажется тут довольно хорошо расписано верхнеуровнево https://15721.courses.cs.cmu.edu/spring2024/papers/02-data1/p3044-liu.pdf Ещё из интересного нигде выше нет varint-ов, вероятно потому что их коэффициент сжатия обычно весьма плох, хотя скорость расжатия может быть даже лучше чем у bitpacking (смотри streamvbyte) Если вдруг не знакомы с bitpacking/bitmap методами, советую эту статью https://dbucsd.github.io/paperpdfs/2017_2.pdf TLDR: * roaring bitmap, лучший выбор из битмап * pfor/simd bitpacking, block size 128/256, optional delta -- лучшие методы из bitpacking * bitpacking обычно лучше bitmap, для всего кроме интерсекшена / dense листов (имхо с интерсекшеном разница меньше чем утверждается в статье, так как "skip pointers" в ней достаточно плохо рассматривается) * имхо random access у roaring поприятнее Так вот по поводу varint, много где еще используется стандартный алгоритм: https://en.wikipedia.org/wiki/LEB128 Это очень печально, так как не смотря на простоту, такой алгоритм работает сильно хуже с branch предиктором, чем например utf-8 подход Есть несколько разных попыток это исправить, например https://github.com/ledbit/varint https://www.sqlite.org/src4/doc/trunk/www/varint.wiki Так что если вдруг у вас есть возможность сделать что-то новое/сломать обратную совместимость, и по какой-то причине вы используете отдельные varint-ы обратите внимание хотя бы на prefix варианты, которые работают значительно быстрее Если же у вас массив varint-ов, смотрите в сторону https://github.com/lemire/streamvbyte и аналогов (есть даже с LEB128 совместимые)