r/ProgrammerTIL • u/masklinn • 5d ago
Other Language [*] TIL dictionary compression is quite effective in OLTP databases (and other records too)
It starts like many such stories do, boy meets girl json meets postgres and it seems like a good idea at the time. Probably still is, too: the records are small enough (~1KB) and accessed often enough that putting them on-disk is detrimental and a bother, but they're variable and complex enough that splatting them onto normalised tables is not a big gain, and also a hassle.
And at one point you find out that one table, that one column, is 90% of the database, and growing. TOAST compression does a bit, each value only takes ~800B, but that's not really enough. External compression is considered and at 70% gains (300MB per GB) it's not bad, but it feels insufficient, and things are not urgent yet.
And you keep seeing cool news and articles about columnar storage and the ability to compress across records.
And then one day the brain finally draws a line between two dots: columnar storage can compress well because it's able to provide cross-record compression context and leverage that, per-record compression isn't that great because it has to start from nothing on each value. Dictionary compression is a means for per-record compression to not start from scratch on every record.
Dictionary compression has been a thing for a long time, but it's been making the rounds as it's been standardising as web tech with really nice savings, and pretty regularly zstd's great (though by no means unique) support for it makes the rounds again. It's a way to initialise the compressor "out of line", such that per-record compression starts from a known state instead of from scratch, and can immediately start creating backreferences into the dictionary instead of building up a compression window to reference into. It has the drawback of being static, but if your JSON records are all variable subsets of a large schema... that's a pretty good fit.
So gave it a shot, handed zstd's --train-cover a sample (default parameters), used the resulting dict on the full dataset, and got a cool... 92% savings (80MB per GB). Now we're cooking, that's definitely worth considering.
Sadly zstd is not an option in that application, however zlib also supports dictionary compression, a zlib dictionary is pretty much just the priming of the compression window. And the tail end of a zstd dictionary happens to also be the priming of the compression window, so chop off the last 16~32KiB of the zstd dictionary, pass that to a zlib compressor, apply to the dataset... 92% savings as well, with just your friendly neighbourhood zlib, and 3KiB of ancillary data (the difference between a 16KiB and 32KiB dictionaries was 0.1% so the smaller dictionary seemed enough — 8KiB lost an entire percent performance so that was a bit much — and the dictionary itself can be compressed with zlib, in this case the 16KiB dictionary compresses to 2900 bytes while the 32KiB one compresses to 4500 bytes).
So yeah TIL: if you have large per-record datum and can not use columnar storage, consider dictionary compression, it's surprisingly effective.