tgoop.com/reverse13/727
Last Update:
Прочитал статью, первый раз столкнулся с таким явным вариантом рекурсивного сжатия 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 совместимые)
BY Loser story
Share with your friend now:
tgoop.com/reverse13/727