Re: ZSTD TOAST compression, and an extensible compression method encoding

Hello, here is v11.

Two changes on top of v10, both in the dictionary area, plus a rebase on master
(065dc52f1a4). cfbot is green on all platforms. It does not touch 0003 or the
decode paths from the measurement thread.

0001 Decode the compression method in toast_external_info_get()
0002 Allow more than four TOAST compression methods
0003 Add zstd as a TOAST compression method
0004 Add TOAST compression dictionaries for zstd and lz4
0005 Add automatic dictionary evolution during ANALYZE

0001-0003 are unchanged.

Some callouts.

0004 folds the former abstraction and lz4-dictionary patches into one.

The split was artificial: the catalog, the column-local lifecycle, containment,
retirement and training are codec-independent, and only three calls differ per
codec (compress with a dictionary, decompress, decompress a prefix). So the
dictionary patch now carries both zstd_dict and lz4_dict from the start, with
the codec behind a small DictCompressRoutine. lz4 has no trainer of its own
and its headers point at zstd's ZDICT, so an lz4 dictionary is the same trained
bytes; only the compress/decompress calls change. For small, similar values,
which is where TOAST dictionaries help most, a dictionary roughly doubles lz4
(about +80% on ~1kB structured documents) and brings lz4+dict above plain zstd
while keeping lz4's lower decompression cost.

0005 automatic dictionary evolution, the open question from last time. (new)

A trained dictionary ages as a column's data drifts. This lets ANALYZE
retrain, opt-in per column (an attribute option, default off), on the block
sample ANALYZE already has, and never on the write path:

- Gates. Retrain only when the live row count has grown by a factor
since the current dictionary was trained, is past a floor, and the
current dictionary is older than a cooldown. A per-column cap bounds
how many dictionaries accumulate; at the cap it declines with a LOG
and suggests a rewrite, since retirement is still rewrite-bound.
- Adopt only on a win. Train a candidate on 80% of the sample,
compress the held-out 20% with both the current and the candidate
dictionary, and install the candidate only if it is at least a margin
smaller on data it was not trained on. The first dictionary is
adopted unconditionally.
- Off the fast path. All of this runs in the ANALYZE process. The
write path only reads the current dictionary OID, now cached in the
relcache (dict_install invalidates it), so a bulk load no longer
probes the catalog per value.
- Codec-agnostic. A codec adds only train() and a compressed-size
estimate, so zstd and lz4 share the whole policy.

Two pg_toast_dictionary columns feed the gates: tdtrainrows (the reltuples
estimate at training time) and tdtraintime.

Measured on drifting data: load one distribution, train, drift to a different
distribution, ANALYZE, rewrite, and compare the stored size of the drifted data
under three policies:

policy avg stored ratio
plain zstd (no dictionary) 868 B 3.94
stale dictionary (old data, kept) 892 B 3.83
evolved dictionary (retrained) 821 B 4.16

The point is the middle row: after drift a stale dictionary is worse than no
dictionary, because it mis-predicts the new data; evolution retrains
automatically and recovers the advantage (821 vs 892, about 8% smaller). The
decision is visible in the log at DEBUG1:

dictionary evolution for "v": heldout=6000 dictsize=65536
cur=5179154 cand=4910999 gain=5.2% adopt=1

When the distribution does not drift, the candidate does not beat the incumbent
by the margin, so nothing is installed and the dictionary count does not move.
The held-out test is a compression-ratio proxy, not an end-to-end TOAST
measurement; I think that is the right first cut, and the margin absorbs the
slack.

0005 depends only on 0004, so if the series is more than the thread wants to
carry at once I can hold it back and post it separately later.

The auto-training/retraining aspect is likely going to elicit a lot of good
design feedback and differing opinions, but I'd like those who participate in
the discussion about that to first acknowledge that the fundamental idea of
auto-retraining/evolution of dictionaries is an idea that they feel should be
in or out of this kind of solution explicitly and up front if possible. I do
think it is a good idea and should be in, but there should be functions to
manage dictionaries manually and a way to enable/disable the automatic piece.

my $0.02, fwiw. best.

-greg