https://www.vldb.org/pvldb/vol16/p2132-afroozeh.pdf
Прочитал тут статью с VLDB про формат данных в базах данных, который даёт много идей на подумать. Даже есть репозиторий https://github.com/cwida/FastLanes
Авторы ставят перед собой несколько целей для дизайна формата хранения целых чисел
* SIMD friendly
* Поддерживает все виды несложного сжатия: parquet, delta encoding, RLE
Ну так как я что-то делал в этой области, статья написано хорошо! Упрощённо: предлагается хранить, например, не 64 битные числа, а каждый байт в 8 колонках. Для меньшего количества бит происходит более интересное чередование, но суть похожа, все это пакуется в 1024 битные регистры.
Чтобы поддержать такое сжатие и воспользоваться всеми преимуществами, авторы перебирали форматы и научились в целом находить Наименьшее Общее Кратное того, как биты должны быть расположены, чтобы все 3 формата сжатия удовлетворить. К сожалению, не обходится без большого количества табличных значений, что опять даёт возможность пользоваться не всем и видеть преимущества на больших данных, когда нужно обработать много памяти и заиспользовать всю её пропускную способность. В итоге получились регистры из 1024 бит, но с поддержкой всех SIMDов всех современных процессоров и неплохими бенчмарками.
Из интересных деталей про "НОК формата", авторы разбирают как они пытались уменьшить зависимость данных. В delta encoding (или префикс суммы) у вас каждое значение зависит от предыдущего. Но можно хранить 4 начальных значения и теперь суммировать 4 числа одновременно, что выдаёт баланс между пропускной способностью и уровнем сжатия. Такими transposed штуками и подбирали создание формата.
Себе взял на заметку, буду тестировать, но я минимально рад, что хотя бы нашёл время почитать статью.
Прочитал тут статью с VLDB про формат данных в базах данных, который даёт много идей на подумать. Даже есть репозиторий https://github.com/cwida/FastLanes
Авторы ставят перед собой несколько целей для дизайна формата хранения целых чисел
* SIMD friendly
* Поддерживает все виды несложного сжатия: parquet, delta encoding, RLE
Ну так как я что-то делал в этой области, статья написано хорошо! Упрощённо: предлагается хранить, например, не 64 битные числа, а каждый байт в 8 колонках. Для меньшего количества бит происходит более интересное чередование, но суть похожа, все это пакуется в 1024 битные регистры.
Чтобы поддержать такое сжатие и воспользоваться всеми преимуществами, авторы перебирали форматы и научились в целом находить Наименьшее Общее Кратное того, как биты должны быть расположены, чтобы все 3 формата сжатия удовлетворить. К сожалению, не обходится без большого количества табличных значений, что опять даёт возможность пользоваться не всем и видеть преимущества на больших данных, когда нужно обработать много памяти и заиспользовать всю её пропускную способность. В итоге получились регистры из 1024 бит, но с поддержкой всех SIMDов всех современных процессоров и неплохими бенчмарками.
Из интересных деталей про "НОК формата", авторы разбирают как они пытались уменьшить зависимость данных. В delta encoding (или префикс суммы) у вас каждое значение зависит от предыдущего. Но можно хранить 4 начальных значения и теперь суммировать 4 числа одновременно, что выдаёт баланс между пропускной способностью и уровнем сжатия. Такими transposed штуками и подбирали создание формата.
Себе взял на заметку, буду тестировать, но я минимально рад, что хотя бы нашёл время почитать статью.