Subject: [PATCH] Compression dictionaries for JSONB

From: Aleksander Alekseev <[email-masked]>
Date: Fri, 22 Apr 2022 11:30:01 +0300

Hi hackers,

This is a follow-up thread to `RFC: compression dictionaries for JSONB`
[1]. I would like to share my current progress in order to get early
feedback. The patch is currently in a draft state but implements the basic
functionality. I did my best to account for all the great feedback I
previously got from Alvaro and Matthias.

Usage example:

```
CREATE TYPE mydict AS DICTIONARY OF jsonb ('aaa', 'bbb');

SELECT '{"aaa":"bbb"}' ::  mydict;
     mydict
----------------
 {"aaa": "bbb"}

SELECT ('{"aaa":"bbb"}' ::  mydict) -> 'aaa';
 ?column?
----------
 "bbb"
```

Here `mydict` works as a transparent replacement for `jsonb`. However, its
internal representation differs. The provided dictionary entries ('aaa',
'bbb') are stored in the new catalog table:

```
SELECT * FROM pg_dict;
  oid  | dicttypid | dictentry
-------+-----------+-----------
 39476 |     39475 | aaa
 39477 |     39475 | bbb
(2 rows)
```

When `mydict` sees 'aaa' in the document, it replaces it with the
corresponding code, in this case - 39476. For more details regarding the
compression algorithm and choosen compromises please see the comments in
the patch.

In pg_type `mydict` has typtype = TYPTYPE_DICT. It works the same way as
TYPTYPE_BASE with only difference: corresponding `<type>_in`
(pg_type.typinput) and `<another-type>_<type>` (pg_cast.castfunc)
procedures receive the dictionary Oid as a `typmod` argument. This way the
procedures can distinguish `mydict1` from `mydict2` and use the proper
compression dictionary.

The approach with alternative `typmod` role is arguably a bit hacky, but it
was the less invasive way to implement the feature I've found. I'm open to
alternative suggestions.

Current limitations (todo):
- ALTER TYPE is not implemented
- Tests and documentation are missing
- Autocomplete is missing

Future work (out of scope of this patch):
- Support types other than JSONB: TEXT, XML, etc
- Automatically updated dictionaries, e.g. during VACUUM
- Alternative compression algorithms. Note that this will not require any
further changes in the catalog, only the values we write to pg_type and
pg_cast will differ.

Open questions:
- Dictionary entries are currently stored as NameData, the same type that
is used for enums. Are we OK with the accompanying limitations? Any
alternative suggestions?
- All in all, am I moving the right direction?

Your feedback is very much welcomed!

[1]:
https://postgr.es/m/CAJ7c6TPx7N-bVw0dZ1ASCDQKZJHhBYkT6w4HV1LzfS%2BUUTUfmA%40mail.gmail.com

-- 
Best regards,
Aleksander Alekseev

---

From: Jacob Champion <[email-masked]>
Date: Wed, 1 Jun 2022 14:29:06 -0700

On Wed, Jun 1, 2022 at 1:44 PM Aleksander Alekseev
<[email-masked]> wrote:
> This is a follow-up thread to `RFC: compression dictionaries for JSONB` [1]. I would like to share my current progress in order to get early feedback. The patch is currently in a draft state but implements the basic functionality. I did my best to account for all the great feedback I previously got from Alvaro and Matthias.

I'm coming up to speed with this set of threads -- the following is
not a complete review by any means, and please let me know if I've
missed some of the history.

>   oid  | dicttypid | dictentry

I saw there was some previous discussion about dictionary size. It
looks like this approach would put all dictionaries into a shared OID
pool. Since I don't know what a "standard" use case is, is there any
risk of OID exhaustion for larger deployments with many dictionaries?
Or is 2**32 so comparatively large that it's not really a serious
concern?

> When `mydict` sees 'aaa' in the document, it replaces it with the corresponding code, in this case - 39476. For more details regarding the compression algorithm and choosen compromises please see the comments in the patch.

I see the algorithm description, but I'm curious to know whether it's
based on some other existing compression scheme, for the sake of
comparison. It seems like it shares similarities with the Snappy
scheme?

Could you talk more about what the expected ratios and runtime
characteristics are? Best I can see is that compression runtime is
something like O(n * e * log d) where n is the length of the input, e
is the maximum length of a dictionary entry, and d is the number of
entries in the dictionary. Since e and d are constant for a given
static dictionary, how well the dictionary is constructed is
presumably important.

> In pg_type `mydict` has typtype = TYPTYPE_DICT. It works the same way as TYPTYPE_BASE with only difference: corresponding `<type>_in` (pg_type.typinput) and `<another-type>_<type>` (pg_cast.castfunc) procedures receive the dictionary Oid as a `typmod` argument. This way the procedures can distinguish `mydict1` from `mydict2` and use the proper compression dictionary.
>
> The approach with alternative `typmod` role is arguably a bit hacky, but it was the less invasive way to implement the feature I've found. I'm open to alternative suggestions.

Haven't looked at this closely enough to develop an opinion yet.

> - ALTER TYPE is not implemented

That reminds me. How do people expect to generate a "good" dictionary
in practice? Would they somehow get the JSONB representations out of
Postgres and run a training program over the blobs? I see some
reference to training functions in the prior threads but don't see any
breadcrumbs in the code.

> - Alternative compression algorithms. Note that this will not require any further changes in the catalog, only the values we write to pg_type and pg_cast will differ.

Could you expand on this? I.e. why would alternative algorithms not
need catalog changes? It seems like the only schemes that could be
used with pg_catalog.pg_dict are those that expect to map a byte
string to a number. Is that general enough to cover other standard
compression algorithms?

> Open questions:
> - Dictionary entries are currently stored as NameData, the same type that is used for enums. Are we OK with the accompanying limitations? Any alternative suggestions?

It does feel a little weird to have a hard limit on the entry length,
since that also limits the compression ratio. But it also limits the
compression runtime, so maybe it's a worthwhile tradeoff.

It also seems strange to use a dictionary of C strings to compress
binary data; wouldn't we want to be able to compress zero bytes too?

Hope this helps,
--Jacob

---

From: Aleksander Alekseev <[email-masked]>
Date: Thu, 2 Jun 2022 16:30:20 +0300

Hi Jacob,

Many thanks for your feedback!

> Or is 2**32 so comparatively large that it's not really a serious

I agree, this is a drawback of the current implementation. To be honest,
I simply followed the example of how ENUMs are implemented. I'm not 100% sure
if we should be worried here (apparently, freed OIDs are reused). I'm OK with
using a separate sequence if someone could second this. This is the first time
I'm altering the catalog so I'm not certain what the best practices are.

> static dictionary, how well the dictionary is constructed is

The algorithm is almost identical to the one I used in ZSON extension [1]
except the fact that ZSON uses 16-bit codes. In docs/benchmark.md you will find
approximate ratios to expect, etc. The reasons why this particular algorithm
was chosen are:

1. It was extensively tested in the past and seem to work OK for existing
   ZSON users.
2. It doesn't use any knowledge regarding the data structure and thus can be
   reused for TEXT/XML/etc as-is.
3. Previously we agreed that at some point users will be able to change the
   algorithm (the same way as they can do it for TOAST now) so which algorithm
   will be used in the first implementation is not that important. I simply
   choose the already existing one.

> reference to training functions in the prior threads but don't see any

So far we agreed that in the first implementation it will be done manually.
In the future it will be possible to update the dictionaries automatically
during VACUUM. The idea of something similar to zson_learn() procedure, as
I recall, didn't get much support, so we probably will not have it, or at least
it is not a priority.

> string to a number. Is that general enough to cover other standard

Sure. When creating a new dictionary pg_type and pg_cast are modified like this:

 =# CREATE TYPE mydict AS DICTIONARY OF JSONB ('abcdef', 'ghijkl');
CREATE TYPE
 =# SELECT * FROM pg_type WHERE typname = 'mydict';
-[ RECORD 1 ]--+---------------
oid            | 16397
typname        | mydict
typnamespace   | 2200
...
typarray       | 16396
typinput       | dictionary_in
typoutput      | dictionary_out
...

=# SELECT c.*, p.proname FROM pg_cast AS c
     LEFT JOIN pg_proc AS p
     ON p.oid = c.castfunc
      WHERE c.castsource = 16397 or c.casttarget = 16397;
-[ RECORD 1 ]-----------------
oid         | 16400
castsource  | 3802
casttarget  | 16397
castfunc    | 9866
castcontext | a
castmethod  | f
proname     | jsonb_dictionary
-[ RECORD 2 ]-----------------
oid         | 16401
castsource  | 16397
casttarget  | 3802
castfunc    | 9867
castcontext | i
castmethod  | f
proname     | dictionary_jsonb
-[ RECORD 3 ]-----------------
oid         | 16402
castsource  | 16397
casttarget  | 17
castfunc    | 9868
castcontext | e
castmethod  | f
proname     | dictionary_bytea

In order to add a new algorithm you simply need to provide alternatives
to dictionary_in / dictionary_out / jsonb_dictionary / dictionary_jsonb and
specify them in the catalog instead. The catalog schema will remain the same.

> binary data; wouldn't we want to be able to compress zero bytes too?

That's a good point. Again, here I simply followed the example of the ENUMs
implementation. Since compression dictionaries are intended to be used with
text-like types such as JSONB, (and also JSON, TEXT and XML in the future),
choosing Name type seemed to be a reasonable compromise. Dictionary entries are
most likely going to store JSON keys, common words used in the TEXT, etc.
However, I'm fine with any alternative scheme if somebody experienced with the
PostgreSQL catalog could second this.

[1]: https://github.com/afiskon/zson

-- 
Best regards,
Aleksander Alekseev

---

From: Jacob Champion <[email-masked]>
Date: Thu, 2 Jun 2022 15:21:26 -0700

> I'm altering the catalog so I'm not certain what the best practices are.

I think reuse should be fine (if a bit slower, but offhand that
doesn't seem like an important bottleneck). Users may be unamused to
find that one large dictionary has prevented the creation of any new
entries in other dictionaries, though. But again, I have no intuition
for the size of a production-grade compression dictionary, and maybe
it's silly to assume that normal use would ever reach the OID limit.

> approximate ratios to expect, etc.

That's assuming a machine-trained dictionary, though, which isn't part
of the proposal now. Is there a performance/ratio sample for a "best
practice" hand-written dictionary?

> I recall, didn't get much support, so we probably will not have it, or at least

Hm... I'm skeptical that a manually-constructed set of compression
dictionaries would be maintainable over time or at scale. But I'm not
the target audience so I will let others weigh in here instead.

> specify them in the catalog instead. The catalog schema will remain the same.

The catalog schemas for pg_type and pg_cast would. But would the
current pg_dict schema be generally applicable to other cross-table
compression schemes? It seems narrowly tailored -- which is not a
problem for a proof of concept patch; I'm just not seeing how other
standard compression schemes might make use of an OID-to-NameData map.
My naive understanding is that they have their own dictionary
structures.

(You could of course hack in any general structure you needed by
treating pg_dict like a list of chunks, but that seems wasteful and
slow, especially given the 63-byte chunk limit, and even more likely
to exhaust the shared OID pool. I think LZMA dictionaries can be huge,
as one example.)

> PostgreSQL catalog could second this.

I think Matthias back in the first thread was hoping for the ability
to compress duplicated JSON objects as well; it seems like that
wouldn't be possible with the current scheme. (Again I have no
intuition for which use cases are must-haves.) I'm wondering if
pg_largeobject would be an alternative catalog to draw inspiration
from... specifically the use of bytea as the stored value, and of a
two-column primary key.

But take all my suggestions with a dash of salt :D I'm new to this space.

Thanks!
--Jacob

---

From: Simon Riggs <[email-masked]>
Date: Thu, 23 Jun 2022 16:48:48 +0100

> I'm altering the catalog so I'm not certain what the best practices are.

The goal of this patch is great, thank you for working on this (and ZSON).

The approach chosen has a few downsides that I'm not happy with yet.

* Assigning OIDs for each dictionary entry is not a great idea. I
don't see why you would need to do that; just assign monotonically
ascending keys for each dictionary, as we do for AttrNums.

* There is a limit on SQL statement size, which will effectively limit
the size of dictionaries, but the examples are unrealistically small,
so this isn't clear as a limitation, but it would be in practice. It
would be better to specify a filename, which can be read in when the
DDL executes. This can be put into pg_dump output in a similar way to
the COPY data for a table is, so once read in it stays static.

* The dictionaries are only allowed for certain datatypes. This should
not be specifically limited by this patch, i.e. user defined types
should not be rejected.

* Dictionaries have no versioning. Any list of data items changes over
time, so how do we express that? Enums were also invented as static
lists originally, then had to be modified later to accomodate
additions and revisions, so let's think about that now, even if we
don't add all of the commands in one go. Currently we would have to
create a whole new dictionary if even one word changes. Ideally, we
want the dictionary to have a top-level name and then have multiple
versions over time. Let's agree how we are going do these things, so
we can make sure the design and code allows for those future
enhancements.
i.e. how will we do ALTER TABLE ... UPGRADE DICTIONARY without causing
a table rewrite?

* Does the order of entries in the dictionary allow us to express a
priority? i.e. to allow Huffman coding.

Thanks for your efforts - this is a very important patch.

-- 
Simon Riggs                http://www.EnterpriseDB.com/

---

From: Aleksander Alekseev <[email-masked]>
Date: Tue, 28 Jun 2022 15:37:14 +0300

Hi Simon,

I'm going to submit an updated version of the patch in a bit. I just
wanted to reply to some of your questions / comments.

> Dictionaries have no versioning. [...]

> Does the order of entries in the dictionary allow us to express a priority? i.e. to allow Huffman coding. [...]

This is something we discussed in the RFC thread. I got an impression
that the consensus was reached:

1. To simply use 32-bit codes in the compressed documents, instead of
16-bit ones as it was done in ZSON;
2. Not to use any sort of variable-length coding;
3. Not to use dictionary versions. New codes can be added to the
existing dictionaries by executing ALTER TYPE mydict ADD ENTRY. (This
also may answer your comment regarding a limit on SQL statement size.)
4. The compression scheme can be altered in the future if needed.
Every compressed document stores algorithm_version (1 byte).

Does this plan of action sound OK to you? At this point it is not too
difficult to make design changes.

-- 
Best regards,
Aleksander Alekseev