[PATCH] Compression dictionaries for JSONB

On Fri, Apr 22, 2022 at 1:30 AM Aleksander Alekseev <
aleksander@timescale.com> wrote:

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]:
/messages/by-id/CAJ7c6TPx7N-bVw0dZ1ASCDQKZJHhBYkT6w4HV1LzfS+UUTUfmA@mail.gmail.com

--
Best regards,
Aleksander Alekseev

Hi,
For src/backend/catalog/pg_dict.c, please add license header.

+ elog(ERROR, "skipbytes > decoded_size - outoffset");

Include the values for skipbytes, decoded_size and outoffset.

Cheers

Hi Zhihong,

Many thanks for your feedback!

For src/backend/catalog/pg_dict.c, please add license header.

Fixed.

+ elog(ERROR, "skipbytes > decoded_size - outoffset");

Include the values for skipbytes, decoded_size and outoffset.

In fact, this code should never be executed, and if somehow it will
be, this information will not help us much to debug the issue. I made
corresponding changes to the error message and added the comments.

Here it the 2nd version of the patch:

- Includes changes named above
- Fixes a warning reported by cfbot
- Fixes some FIXME's
- The path includes some simple tests now
- A proper commit message was added

Please note that this is still a draft. Feedback is welcome.

--
Best regards,
Aleksander Alekseev

Hi hackers,

Here it the 2nd version of the patch:

- Includes changes named above
- Fixes a warning reported by cfbot
- Fixes some FIXME's
- The path includes some simple tests now
- A proper commit message was added

Here is the rebased version of the patch. Changes compared to v2 are minimal.

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?

I would like to receive a little bit more feedback before investing more time
into this effort. This will allow me, if necessary, to alter the overall design
more easily.

--
Best regards,
Aleksander Alekseev

On Wed, Jun 1, 2022 at 1:44 PM Aleksander Alekseev
<aleksander@timescale.com> 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.

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

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.

Current limitations (todo):
- 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

Hi Jacob,

Many thanks for your feedback!

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?

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.

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.

The algorithm is almost identical to the one I used in ZSON extension [1]https://github.com/afiskon/zson
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.

Current limitations (todo):
- 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.

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.

- 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?

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.

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?

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

On Thu, Jun 2, 2022 at 6:30 AM Aleksander Alekseev
<aleksander@timescale.com> wrote:

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?

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.

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.

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.

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.

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?

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.

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.

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.

- 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?

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.

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.)

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?

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.

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

On Fri, 13 May 2022 at 10:09, Aleksander Alekseev
<aleksander@timescale.com> wrote:

Hi hackers,

Here it the 2nd version of the patch:

- Includes changes named above
- Fixes a warning reported by cfbot
- Fixes some FIXME's
- The path includes some simple tests now
- A proper commit message was added

Here is the rebased version of the patch. Changes compared to v2 are minimal.

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?

I would like to receive a little bit more feedback before investing more time
into this effort. This will allow me, if necessary, to alter the overall design
more easily.

Sorry for the delayed reply. After the last thread, I've put some time
in looking into the "pluggable toaster" patches, which appears to want
to provide related things: Compressing typed data using an extensible
API. I think that that API is a better approach to increase the
compression ratio for JSONB.

That does not mean that I think that the basis of this patch is
incorrect, just that the current API (through new entries in the
pg_type and pg_casts catalogs) is not the right direction if/when
we're going to have a pluggable toaster API. The bulk of the patch
should still be usable, but I think that the way it interfaces with
the CREATE TABLE (column ...) APIs would need reworking to build on
top of the api's of the "pluggable toaster" patches (so, creating
toasters instead of types). I think that would allow for an overall
better user experience and better performance due to decreased need
for fully decompressed type casting.

Kind regards,

Matthias van de Meent.

Hi Matthias,

The bulk of the patch
should still be usable, but I think that the way it interfaces with
the CREATE TABLE (column ...) APIs would need reworking to build on
top of the api's of the "pluggable toaster" patches (so, creating
toasters instead of types). I think that would allow for an overall
better user experience and better performance due to decreased need
for fully decompressed type casting.

Many thanks for the feedback.

The "pluggable TOASTer" patch looks very interesting indeed. I'm
currently trying to make heads and tails of it and trying to figure
out if it can be used as a base for compression dictionaries,
especially for implementing the partial decompression. Hopefully I
will be able to contribute to it and to the dependent patch [1]https://commitfest.postgresql.org/38/3479/ in the
upcoming CF, at least as a tester/reviewer. Focusing our efforts on
[1]: https://commitfest.postgresql.org/38/3479/

My current impression of your idea is somewhat mixed at this point though.

Teodor's goal is to allow creating _extensions_ that implement
alternative TOAST strategies, which use alternative compression
algorithms and/or use the knowledge of the binary representation of
the particular type. For sure, this would be a nice thing to have.
However, during the discussion of the "compression dictionaries" RFC
the consensus was reached that the community wants to see it as a
_built_in_ functionality rather than an extension. Otherwise we could
simply add ZSON to /contrib/ as it was originally proposed.

So if we are going to keep "compression dictionaries" a built-in
functionality, putting artificial constraints on its particular
implementation, or adding artificial dependencies of two rather
complicated patches, is arguably a controversial idea. Especially
considering the fact that it was shown that the feature can be
implemented without these dependencies, in a very non-invasive way.

These are just my initial thoughts I would like to share though. I may
change my mind after diving deeper into a "pluggable TOASTer" patch.

I cc:'ed Teodor in case he would like to share his insights on the topic.

[1]: https://commitfest.postgresql.org/38/3479/

--
Best regards,
Aleksander Alekseev

Hi Matthias,

These are just my initial thoughts I would like to share though. I may
change my mind after diving deeper into a "pluggable TOASTer" patch.

I familiarized myself with the "pluggable TOASTer" thread and joined
the discussion [1]/messages/by-id/CAJ7c6TOMPiRs-CZ=A9hyzxOyqHhKXxLD8qCF5+GJuLjQBzOX4A@mail.gmail.com.

I'm afraid so far I failed to understand your suggestion to base
"compression dictionaries" patch on "pluggable TOASTer", considering
the fair amount of push-back it got from the community, not to mention
a somewhat raw state of the patchset. It's true that Teodor and I are
trying to address similar problems. This however doesn't mean that
there should be a dependency between these patches.

Also, I completely agree with Tomas [2]/messages/by-id/9ef14537-b33b-c63a-9938-e2b413db0a4c@enterprisedb.com:

My main point is that we should not be making too many radical
changes at once - it makes it much harder to actually get anything done.

IMO the patches don't depend on each other but rather complement each
other. The user can switch between different TOAST methods, and the
compression dictionaries can work on top of different TOAST methods.
Although there is also a high-level idea (according to the
presentations) to share common data between different TOASTed values,
similarly to what compression dictionaries do, by looking at the
current feedback and considering the overall complexity and the amount
of open questions (e.g. interaction with different TableAMs, etc), I
seriously doubt that this particular part of "pluggable TOASTer" will
end-up in the core.

[1]: /messages/by-id/CAJ7c6TOMPiRs-CZ=A9hyzxOyqHhKXxLD8qCF5+GJuLjQBzOX4A@mail.gmail.com
[2]: /messages/by-id/9ef14537-b33b-c63a-9938-e2b413db0a4c@enterprisedb.com

--
Best regards,
Aleksander Alekseev

On Thu, 2 Jun 2022 at 14:30, Aleksander Alekseev
<aleksander@timescale.com> wrote:

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?

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.

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/

Hi Simon,

Many thanks for your feedback!

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

Hi Alexander,

On Fri, 17 Jun 2022 at 17:04, Aleksander Alekseev
<aleksander@timescale.com> wrote:

These are just my initial thoughts I would like to share though. I may
change my mind after diving deeper into a "pluggable TOASTer" patch.

I familiarized myself with the "pluggable TOASTer" thread and joined
the discussion [1].

I'm afraid so far I failed to understand your suggestion to base
"compression dictionaries" patch on "pluggable TOASTer", considering
the fair amount of push-back it got from the community, not to mention
a somewhat raw state of the patchset. It's true that Teodor and I are
trying to address similar problems. This however doesn't mean that
there should be a dependency between these patches.

The reason I think this is better implemented as a pluggable toaster
is because casts are necessarily opaque and require O(sizeofdata)
copies or processing. The toaster infrastructure that is proposed in
[0]: seems to improve on the O(sizeofdata) requirement for toast, but that will not work with casts.
that will not work with casts.

Also, I completely agree with Tomas [2]:

My main point is that we should not be making too many radical
changes at once - it makes it much harder to actually get anything done.

IMO the patches don't depend on each other but rather complement each
other. The user can switch between different TOAST methods, and the
compression dictionaries can work on top of different TOAST methods.

I don't think that is possible (or at least, not as performant). To
treat type X' as type X and use it as a stored medium instead, you
must have either the whole binary representation of X, or have access
to the internals of type X. I find it difficult to believe that casts
can be done without a full detoast (or otherwise without deep
knowledge about internal structure of the data type such as 'type A is
binary compatible with type X'), and as such I think this feature
'compression dictionaries' is competing with the 'pluggable toaster'
feature, if the one is used on top of the other. That is, the
dictionary is still created like in the proposed patches (though
preferably without the 64-byte NAMELEN limit), but the usage will be
through "TOASTER my_dict_enabled_toaster".

Additionally, I don't think we've ever accepted two different
implementations of the same concept, at least not without first having
good arguments why both competing implementations have obvious
benefits over the other, and both implementations being incompatible.

Although there is also a high-level idea (according to the
presentations) to share common data between different TOASTed values,
similarly to what compression dictionaries do, by looking at the
current feedback and considering the overall complexity and the amount
of open questions (e.g. interaction with different TableAMs, etc), I
seriously doubt that this particular part of "pluggable TOASTer" will
end-up in the core.

Yes, and that's why I think that this where this dictionary
infrastructure could provide value, as an alternative or extension to
the proposed jsonb toaster in the 'pluggable toaster' thread.

Kind regards,

Matthias van de Meent

Hi Matthias,

Although there is also a high-level idea (according to the
presentations) to share common data between different TOASTed values,
similarly to what compression dictionaries do, by looking at the
current feedback and considering the overall complexity and the amount
of open questions (e.g. interaction with different TableAMs, etc), I
seriously doubt that this particular part of "pluggable TOASTer" will
end-up in the core.

Yes, and that's why I think that this where this dictionary
infrastructure could provide value, as an alternative or extension to
the proposed jsonb toaster in the 'pluggable toaster' thread.

OK, I see your point now. And I think this is a very good point.
Basing "Compression dictionaries" on the API provided by "pluggable
TOASTer" can also be less hacky than what I'm currently doing with
`typmod` argument. I'm going to switch the implementation at some
point, unless anyone will object to the idea.

--
Best regards,
Aleksander Alekseev

Hi hackers,

OK, I see your point now. And I think this is a very good point.
Basing "Compression dictionaries" on the API provided by "pluggable
TOASTer" can also be less hacky than what I'm currently doing with
`typmod` argument. I'm going to switch the implementation at some
point, unless anyone will object to the idea.

Here is the rebased patch. I reworked the memory management a bit but
other than that there are no new changes.

So far we seem to have a consensus to:

1. Use bytea instead of NameData to store dictionary entries;

2. Assign monotonically ascending IDs to the entries instead of using
Oids, as it is done with pg_class.relnatts. In order to do this we
should either add a corresponding column to pg_type, or add a new
catalog table, e.g. pg_dict_meta. Personally I don't have a strong
opinion on what is better. Thoughts?

Both changes should be straightforward to implement and also are a
good exercise to newcomers.

I invite anyone interested to join this effort as a co-author! (since,
honestly, rewriting the same feature over and over again alone is
quite boring :D).

--
Best regards,
Aleksander Alekseev

Hi hackers,

I invite anyone interested to join this effort as a co-author!

Here is v5. Same as v4 but with a fixed compiler warning (thanks,
cfbot). Sorry for the noise.

--
Best regards,
Aleksander Alekseev

Hi hackers!

Aleksander, please point me in the right direction if it was mentioned
before, I have a few questions:

1) It is not clear for me, how do you see the life cycle of such a
dictionary? If it is meant to keep growing without
cleaning up/rebuilding it could affect performance in an undesirable way,
along with keeping unused data without
any means to get rid of them.
Also, I agree with Simon Riggs, using OIDs from the general pool for
dictionary entries is a bad idea.

2) From (1) follows another question - I haven't seen any means for getting
rid of unused keys (or any other means
for dictionary cleanup). How could it be done?

3) Is the possible scenario legal - by some means a dictionary does not
contain some keys for entries? What happens then?

4) If one dictionary is used by several tables - I see future issues in
concurrent dictionary updates. This will for sure
affect performance and can cause unpredictable behavior for queries.

If you have any questions on Pluggable TOAST don't hesitate to ask me and
on JSONB Toaster you can ask Nikita Glukhov.

Thank you!

Regards,
Nikita Malakhov
Postgres Professional
https://postgrespro.ru/
On Mon, Jul 11, 2022 at 6:41 PM Aleksander Alekseev <
aleksander@timescale.com> wrote:

Hi Nikita,

Aleksander, please point me in the right direction if it was mentioned before, I have a few questions:

Thanks for your feedback. These are good questions indeed.

1) It is not clear for me, how do you see the life cycle of such a dictionary? If it is meant to keep growing without
cleaning up/rebuilding it could affect performance in an undesirable way, along with keeping unused data without
any means to get rid of them.
2) From (1) follows another question - I haven't seen any means for getting rid of unused keys (or any other means
for dictionary cleanup). How could it be done?

Good point. This was not a problem for ZSON since the dictionary size
was limited to 2**16 entries, the dictionary was immutable, and the
dictionaries had versions. For compression dictionaries we removed the
2**16 entries limit and also decided to get rid of versions. The idea
was that you can simply continue adding new entries, but no one
thought about the fact that this will consume the memory required to
decompress the document indefinitely.

Maybe we should return to the idea of limited dictionary size and
versions. Objections?

4) If one dictionary is used by several tables - I see future issues in concurrent dictionary updates. This will for sure
affect performance and can cause unpredictable behavior for queries.

You are right. Another reason to return to the idea of dictionary versions.

Also, I agree with Simon Riggs, using OIDs from the general pool for dictionary entries is a bad idea.

Yep, we agreed to stop using OIDs for this, however this was not
changed in the patch at this point. Please don't hesitate joining the
effort if you want to. I wouldn't mind taking a short break from this
patch.

3) Is the possible scenario legal - by some means a dictionary does not contain some keys for entries? What happens then?

No, we should either forbid removing dictionary entries or check that
all the existing documents are not using the entries being removed.

If you have any questions on Pluggable TOAST don't hesitate to ask me and on JSONB Toaster you can ask Nikita Glukhov.

Will do! Thanks for working on this and I'm looking forward to the
next version of the patch for the next round of review.

--
Best regards,
Aleksander Alekseev

Hi hackers!

Aleksander, I've carefully gone over discussion and still have some
questions to ask -

1) Is there any means of measuring overhead of dictionaries over vanilla
implementation? IMO it is a must because
JSON is a widely used functionality. Also, as it was mentioned before, to
check the dictionary value must be detoasted;

2) Storing dictionaries in one table. As I wrote before, this will surely
lead to locks and waits while inserting and updating
dictionaries, and could cause serious performance issues. And vacuuming
this table will lead to locks for all tables using
dictionaries until vacuum is complete;

3) JSON documents in production environments could be very complex and use
thousands of keys, so creating dictionary
directly in SQL statement is not very good approach, so it's another reason
to have means for creating dictionaries as a
separate tables and/or passing them as files or so;

4) Suggested mechanics, if put on top of the TOAST, could not benefit from
knowledge if internal JSON structure, which
is seen as important drawback in spite of extensive research work done on
working with JSON schema (storing, validating,
etc.), and also it cannot recognize and help to compress duplicated parts
of JSON document;

5) A small test issue - if dictionaried' JSON has a key which is equal to
OID used in a dictionary for some other key?

In Pluggable TOAST we suggest that as an improvement compression should be
put inside the Toaster as an option,
thus the Toaster could have maximum benefits from knowledge of data
internal structure (and in future use JSON Schema).
For using in special Toaster for JSON datatype compression dictionaries
seem to be very valuable addition, but now I
have to agree that this feature in current state is competing with
Pluggable TOAST.

Thank you!

Regards,
Nikita Malakhov
Postgres Professional
https://postgrespro.ru/

On Tue, Jul 12, 2022 at 3:15 PM Aleksander Alekseev <
aleksander@timescale.com> wrote:

Hi Nikita,

Thanks for your feedback!

Aleksander, I've carefully gone over discussion and still have some questions to ask -

1) Is there any means of measuring overhead of dictionaries over vanilla implementation? IMO it is a must because
JSON is a widely used functionality. Also, as it was mentioned before, to check the dictionary value must be detoasted;

Not sure what overhead you have in mind. The patch doesn't affect the
vanilla JSONB implementation.

2) Storing dictionaries in one table. As I wrote before, this will surely lead to locks and waits while inserting and updating
dictionaries, and could cause serious performance issues. And vacuuming this table will lead to locks for all tables using
dictionaries until vacuum is complete;

I believe this is true to some degree. But doesn't the same generally
apply to the rest of catalog tables?

I'm not that concerned about inserting/updating since this is a rare
operation. Vacuuming shouldn't be such a problem unless the user
creates/deletes dictionaries all the time.

Am I missing something?

3) JSON documents in production environments could be very complex and use thousands of keys, so creating dictionary
directly in SQL statement is not very good approach, so it's another reason to have means for creating dictionaries as a
separate tables and/or passing them as files or so;

Yes, it was proposed to update dictionaries automatically e.g. during
the VACUUM of the table that contains compressed documents. This is
simply out of scope of this particular patch. It was argued that the
manual update should be supported too, which is implemented in this
patch.

4) Suggested mechanics, if put on top of the TOAST, could not benefit from knowledge if internal JSON structure, which
is seen as important drawback in spite of extensive research work done on working with JSON schema (storing, validating,
etc.), and also it cannot recognize and help to compress duplicated parts of JSON document;

Could you please elaborate on this a bit and/or maybe give an example? ...

In Pluggable TOAST we suggest that as an improvement compression should be put inside the Toaster as an option,
thus the Toaster could have maximum benefits from knowledge of data internal structure (and in future use JSON Schema).

... Current implementation doesn't use the knowledge of JSONB format,
that's true. This is because previously we agreed there is no "one
size fits all" compression method, thus several are going to be
supported eventually. The current algorithm was chosen merely as the
one that is going to work good enough for any data type, not just
JSONB. Nothing prevents an alternative compression method from using
the knowledge of JSONB structure.

As, I believe, Matthias pointed out above, only partial decompression
would be a challenge. This is indeed something that would be better to
implement somewhere closer to the TOAST level. Other than that I'm not
sure what you mean.

5) A small test issue - if dictionaried' JSON has a key which is equal to OID used in a dictionary for some other key?

Again, I'm having difficulties understanding the case you are
describing. Could you give a specific example?

For using in special Toaster for JSON datatype compression dictionaries seem to be very valuable addition, but now I
have to agree that this feature in current state is competing with Pluggable TOAST.

I disagree with the word "competing" here. Again, Matthias had a very
good point about this above.

In short, pluggable TOAST is a low-level internal mechanism, but it
doesn't provide a good interface for the end user and has several open
issues. The most important one IMO is how it is supposed to work with
pluggable AMs in the general case. "Compression dictionaries" have a
good user interface, and the implementation is not that important. The
current implementation uses casts, as the only option available at the
moment. But nothing prevents it from using Pluggable TOAST if this
will produce a cleaner code (I believe it will) and will allow
delivering partial decompression (this is yet to be figured out).

--
Best regards,
Aleksander Alekseev