PGLZ Compression Optimization - Mailing list pgsql-hackers

   LZ4 and Zstandard are both excellent and well-maintained open-source
projects.  However, they remain optional dependencies maintained outside
the PostgreSQL project, while PGLZ is an implementation that PostgreSQL
ships and controls itself.

Given the known performance gap between PGLZ and modern compression
algorithms, I wanted to explore a simple question: rather than relying
only on external libraries for better compression performance, can we
also improve PostgreSQL's own built-in compression algorithm?

This patch grew out of that idea.  It is not intended to replace LZ4 or
Zstandard, but to make PostgreSQL's self-contained compression option
substantially more competitive.
The attached RFC patch explores a self-contained modernization of PGLZ.

For inputs of at least 32KB, the encoder first tries a new byte-aligned
stream format.  It uses a single-candidate LZ77 parser, a 65535-byte
history window, literal runs, fixed-width offsets, and ULEB128 length
extensions.  This format is designed primarily for fast decoding.

If that representation cannot satisfy the compression strategy, a second
format can encode literals with canonical Huffman codes.  Smaller inputs
and unsuccessful modern-format attempts continue to use the legacy PGLZ
representation.

The patch also optimizes the legacy path with a rolling hash, indexed
history rings, bounded candidate searches, word/SIMD match extension,
and an AVX2 implementation selected by PostgreSQL's runtime CPU check.
Other platforms use PostgreSQL's existing SIMD abstraction.

The new streams begin with a sequence that is invalid in the legacy
format, allowing the decoder to distinguish them without changing the
external TOAST compression identifier.  The new decoder continues to
read existing legacy PGLZ values.  Compatibility is one-way: an
unpatched server cannot decode values written in either new format.

The implementation is self-contained.  It does not link to or incorporate
source code from LZ4 or Zstandard.

I benchmarked the 51,975-byte example-large.json input, repeated 4,100
times per run.  The following are medians of five runs on ARM64 macOS,
compiled with Apple clang -O3, based on master at 1ae87df63ff:
                         master       patched          LZ4  compression MB/s        325.9        2137.3        2811.2  decompression MB/s     2831.1        7582.5       11777.8  compressed bytes        14370         12445         12802

On this input, the patch made PGLZ compression about 6.6 times faster
and decompression about 2.7 times faster than master.  The resulting
stream was 13.4% smaller.  It remains slower than LZ4, especially during
decompression.

Testing performed:

* clean out-of-tree build with --with-lz4 and --with-zstd
* make check: all 245 tests passed
* 24,820 full and partial round-trip cases under ASan and UBSan
* tests for partial decompression and malformed version-3 streams
* git diff --check

This is intentionally an RFC because it changes the PGLZ on-disk stream
and is currently a large patch.  I would especially appreciate feedback
on:

* whether the one-way compatibility model is acceptable
* whether having both the byte-aligned and Huffman fallback formats is  worth the implementation complexity
* whether the 32KB selection threshold is reasonable
* whether the legacy hot-path changes should be submitted separately

For transparency, I used an AI coding assistant while prototyping parts
of this patch.  I reviewed and tested the resulting implementation and
took responsibility for maintaining and revising it.