7 ms·
One of the things we've learned from columnar data stores and compression formats is that choosing the correct stride order really matters. I noticed this a de
by infogulch 3y ago
One of the things we've learned from columnar data stores and compression formats is that choosing the correct stride order really matters.
I noticed this a decade ago when I stumbled on a voxel engine that used some complex height map compression scheme for game map data. It seemed gratuitous to me, so I tried the simplest thing I could come up with: gzipping a 3D array of voxel colors. It didn't really work until I chose the right stride order (xyz, zyx, yzx, etc) and then suddenly it was 5x better.
The parquet format has the BYTE_STREAM_SPLIT encoding strategy which basically splits an array of floats/doubles into 4/8 arrays of bytes so they can be compressed independently.
https://parquet.apache.org/docs/file-format/data-pages/encodings/ https://parquet.apache.org/docs/file-format/data-pages/encod...
Just choosing the correct stride order before compression is still underutilized. It's also undersupported in our tools too; e.g. that voxel engine used numpy, but it was a pita to get numpy to transparently change the stride order in the memory representation without also affecting the indexing order.
- hugh-avherald 3y agoWhat is stride order?
- pxeger1 3y agoIt means the order in which you serialise a multi-dimensional array. So for this 2D table: 1262 3418 9076 Because it’s 2D it has two stride orders, xy and yx, i.e. row-major and column-major, which would be 126234189076 and 139240617286 respectively.
- enizor2 3y agoThe BYTE_STREAM_SPLIT is a Z-order (also known as Morton encoding). As it is better a preserving locality, it usually performs really well compared to classical "orthogonal" orders. It also is really simple to implement as it boils down to interleaving bits or bytes.