Обсуждение: RFI: Extending the TOAST Pointer

Hi Nikita,

> this part of the PostgreSQL screams to be revised and improved

I completely agree. The problem with TOAST pointers is that they are
not extendable at the moment which prevents adding new compression
algorithms (e.g. ZSTD), new features like compression dictionaries
[1], etc. I suggest we add extensibility in order to solve this
problem for the foreseeable future for everyone.

> where Custom TOAST Pointer is distinguished from Regular one by va_flag field
> which is a part of varlena header

I don't think that varlena header is the best place to distinguish a
classical TOAST pointer from an extended one. On top of that I don't
see any free bits that would allow adding such a flag to the on-disk
varlena representation [2].

The current on-disk TOAST pointer representation is following:

```
typedef struct varatt_external
{
int32 va_rawsize; /* Original data size (includes header) */
uint32 va_extinfo; /* External saved size (without header) and
                              * compression method */
Oid va_valueid; /* Unique ID of value within TOAST table */
Oid va_toastrelid; /* RelID of TOAST table containing it */
} varatt_external;
```

Note that currently only 2 compression methods are supported:

```
typedef enum ToastCompressionId
{
TOAST_PGLZ_COMPRESSION_ID = 0,
TOAST_LZ4_COMPRESSION_ID = 1,
TOAST_INVALID_COMPRESSION_ID = 2
} ToastCompressionId;
```

I suggest adding a new flag that will mark an extended TOAST format:

```
typedef enum ToastCompressionId
{
TOAST_PGLZ_COMPRESSION_ID = 0,
TOAST_LZ4_COMPRESSION_ID = 1,
TOAST_RESERVED_COMPRESSION_ID = 2,
TOAST_HAS_EXTENDED_FORMAT = 3,
} ToastCompressionId;
```

For an extended format we add a varint (utf8-like) bitmask right after
varatt_external that marks the features supported in this particular
instance of the pointer. The rest of the data is interpreted depending
on the bits set. This will allow us to extend the pointers
indefinitely.

Note that the proposed approach doesn't require running any
migrations. Note also that I described only the on-disk
representation. We can tweak the in-memory representation as we want
without affecting the end user.

Thoughts?

[1]: https://commitfest.postgresql.org/43/3626/
[2]:
https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f=src/include/postgres.h;h=0446daa0e61722067bb75aa693a92b38736e12df;hb=164d174bbf9a3aba719c845497863cd3c49a3ad0#l178


-- 
Best regards,
Aleksander Alekseev

On Thu, 18 May 2023 at 12:52, Aleksander Alekseev
<aleksander@timescale.com> wrote:
>
> Hi Nikita,
>
> > this part of the PostgreSQL screams to be revised and improved
>
> I completely agree. The problem with TOAST pointers is that they are
> not extendable at the moment which prevents adding new compression
> algorithms (e.g. ZSTD), new features like compression dictionaries
> [1], etc. I suggest we add extensibility in order to solve this
> problem for the foreseeable future for everyone.
>
> > where Custom TOAST Pointer is distinguished from Regular one by va_flag field
> > which is a part of varlena header
>
> I don't think that varlena header is the best place to distinguish a
> classical TOAST pointer from an extended one. On top of that I don't
> see any free bits that would allow adding such a flag to the on-disk
> varlena representation [2].
>
> The current on-disk TOAST pointer representation is following:
>
> ```
> typedef struct varatt_external
> {
> int32 va_rawsize; /* Original data size (includes header) */
> uint32 va_extinfo; /* External saved size (without header) and
>                               * compression method */
> Oid va_valueid; /* Unique ID of value within TOAST table */
> Oid va_toastrelid; /* RelID of TOAST table containing it */
> } varatt_external;
> ```

No, that's inaccurate. The complete on-disk representation of a varatt is

{
    uint8       va_header;      /* Always 0x80 or 0x01 */
    uint8       va_tag;         /* Type of datum */
    char        va_data[FLEXIBLE_ARRAY_MEMBER]; /* Type-dependent
data, for toasted values that's currently only a varatt_external */
} varattrib_1b_e;

With va_tag being filled with one of the vartag_external values:

typedef enum vartag_external
{
    VARTAG_INDIRECT = 1,
    VARTAG_EXPANDED_RO = 2,
    VARTAG_EXPANDED_RW = 3,
    VARTAG_ONDISK = 18
} vartag_external;

This enum still has many options to go before it exceeds the maximum
of the uint8 va_tag field. Therefore, I don't think we have no disk
representations left, nor do I think we'll need to add another option
to the ToastCompressionId enum.
As an example, we can add another VARTAG option for dictionary-enabled
external toast; like what the pluggable toast patch worked on. I think
we can salvage some ideas from that patch, even if the main idea got
stuck.

Kind regards,

Matthias van de Meent
Neon Inc.

Hi,

> No, that's inaccurate. The complete on-disk representation of a varatt is
>
> {
>     uint8       va_header;      /* Always 0x80 or 0x01 */
>     uint8       va_tag;         /* Type of datum */
>     char        va_data[FLEXIBLE_ARRAY_MEMBER]; /* Type-dependent
> data, for toasted values that's currently only a varatt_external */
> } varattrib_1b_e;
>
> With va_tag being filled with one of the vartag_external values:
>
> typedef enum vartag_external
> {
>     VARTAG_INDIRECT = 1,
>     VARTAG_EXPANDED_RO = 2,
>     VARTAG_EXPANDED_RW = 3,
>     VARTAG_ONDISK = 18
> } vartag_external;
>
> This enum still has many options to go before it exceeds the maximum
> of the uint8 va_tag field. Therefore, I don't think we have no disk
> representations left, nor do I think we'll need to add another option
> to the ToastCompressionId enum.
> As an example, we can add another VARTAG option for dictionary-enabled
> external toast; like what the pluggable toast patch worked on. I think
> we can salvage some ideas from that patch, even if the main idea got
> stuck.

The problem here is that the comments are ambiguous regarding what to
call "TOAST pointer" exactly. I proposed a patch for this but it was
not accepted [1].

So the exact on-disk representation of a TOAST'ed value (for
little-endian machines) is:

0b00000001, 18 (va_tag), (varatt_external here)

Where 18 is sizeof(varatt_external) + 2, because the length includes
the length of the header.

I agree that va_tag can have another use. But since we are going to
make varatt_external variable in size (otherwise I don't see how it
could be really **extendable**) I don't think this is the right
approach.

Also I agree that this particular statement is incorrect:

> This will allow us to extend the pointers indefinitely.

varatt_external is going to be limited to 255. But it seems to be a
reasonable limitation for the nearest 10-20 years or so.

[1]: https://commitfest.postgresql.org/39/3820/

-- 
Best regards,
Aleksander Alekseev

Hi,

> I agree that va_tag can have another use. But since we are going to
> make varatt_external variable in size (otherwise I don't see how it
> could be really **extendable**) I don't think this is the right
> approach.

On second thought, perhaps we are talking more or less about the same thing?

It doesn't matter what will be used as a sign of presence of a varint
bitmask in the pointer. My initial proposal to use ToastCompressionId
for this is probably redundant since va_tag > 18 will already tell
that.

-- 
Best regards,
Aleksander Alekseev

On Thu, 18 May 2023 at 15:12, Aleksander Alekseev
<aleksander@timescale.com> wrote:
>
> Hi,
>
> > I agree that va_tag can have another use. But since we are going to
> > make varatt_external variable in size (otherwise I don't see how it
> > could be really **extendable**) I don't think this is the right
> > approach.

Why would we modify va_tag=18; data=varatt_external? A different
va_tag option would allow us to keep the current layout around without
much maintenance and a consistent low overhead.

> On second thought, perhaps we are talking more or less about the same thing?
>
> It doesn't matter what will be used as a sign of presence of a varint
> bitmask in the pointer. My initial proposal to use ToastCompressionId
> for this is probably redundant since va_tag > 18 will already tell
> that.

I'm not sure "extendable" would be the right word, but as I see it:

1. We need more space to store more metadata;
2. Essentially all bits in varatt_external are already accounted for; and
3. There are still many options left in va_tag

It seems to me that adding a new variant to va_att for marking new
features in the toast infrastructure makes the most sense, as we'd
also be able to do the new things like varints etc without needing to
modify existing toast paths significantly.

We'd need to stop using the va_tag as length indicator, but I don't
think it's currently assumed to be a length indicator anyway (see
VARSIZE_EXTERNAL(ptr)). By not using the varatt_external struct
currently in use, we could be able to get down to <18B toast pointers
as well, though I'd consider that unlikely.

Kind regards,

Matthias van de Meent
Neon, Inc.

Hi,

> We'd need to stop using the va_tag as length indicator, but I don't
> think it's currently assumed to be a length indicator anyway (see
> VARSIZE_EXTERNAL(ptr)). By not using the varatt_external struct
> currently in use, we could be able to get down to <18B toast pointers
> as well, though I'd consider that unlikely.

Agree.

Another thing we have to decide is what to do exactly in the scope of
this thread.

I imagine it as a refactoring that will find all the places that deal
with current TOAST pointer and changes them to something like:

```
switch(va_tag) {
  case DEFAULT_VA_TAG( equals 18 ):
    default_toast_process_case_abc(...);
  default:
    elog(ERROR, "Unknown TOAST tag")
}
```

So that next time somebody is going to need another type of TOAST
pointer this person will have only to add a corresponding tag and
handlers. (Something like "virtual methods" will produce a cleaner
code but will also break branch prediction, so I don't think we should
use those.)

I don't think we need an example of adding a new TOAST tag in scope of
this work since the default one is going to end up being such an
example.

Does it make sense?

-- 
Best regards,
Aleksander Alekseev

On Sun, 21 May 2023, 15:39 Aleksander Alekseev,
<aleksander@timescale.com> wrote:
>
> Hi,
>
> > We'd need to stop using the va_tag as length indicator, but I don't
> > think it's currently assumed to be a length indicator anyway (see
> > VARSIZE_EXTERNAL(ptr)). By not using the varatt_external struct
> > currently in use, we could be able to get down to <18B toast pointers
> > as well, though I'd consider that unlikely.
>
> Agree.
>
> Another thing we have to decide is what to do exactly in the scope of
> this thread.
>
> I imagine it as a refactoring that will find all the places that deal
> with current TOAST pointer and changes them to something like:
>
> ```
> switch(va_tag) {
>   case DEFAULT_VA_TAG( equals 18 ):
>     default_toast_process_case_abc(...);
>   default:
>     elog(ERROR, "Unknown TOAST tag")
> }
> ```

I'm not sure that we need all that.
Many places do some special handling for VARATT_IS_EXTERNAL because
decompressing or detoasting is expensive and doing that as late as
possible can be beneficial (e.g. EXPLAIN ANALYZE can run much faster
because we never detoast returned columns). But only very few of these
cases actually work on explicitly on-disk data: my IDE can't find any
uses of VARATT_IS_EXTERNAL_ONDISK (i.e. the actual TOASTed value)
outside the expected locations of the toast subsystems, amcheck, and
logical decoding (incl. the pgoutput plugin). I'm fairly sure we only
need to update existing paths in those subsystems to support another
format of external (but not the current VARTAG_ONDISK) data.

> So that next time somebody is going to need another type of TOAST
> pointer this person will have only to add a corresponding tag and
> handlers. (Something like "virtual methods" will produce a cleaner
> code but will also break branch prediction, so I don't think we should
> use those.)

Yeah, I'm also not super stoked about using virtual methods for a new
external toast implementation.

> I don't think we need an example of adding a new TOAST tag in scope of
> this work since the default one is going to end up being such an
> example.
>
> Does it make sense?

I see your point, but I do think we should also think about why we do
the change.

E.g.: Our current toast infra is built around 4 uint32 fields in the
toast pointer; but with this change in place we can devise a new toast
pointer that uses varint encoding on the length-indicating fields to
reduce the footprint of 18B to an expected 14 bytes.

Kind regards,

Matthias van de Meent
Neon, Inc.

Hi,

> I see your point, but I do think we should also think about why we do
> the change.

Personally at the moment I care only about implementing compression
dictionaries on top of this, as is discussed in the corresponding
thread [1]. I'm going to need new fields in the TOAST pointer's
including (but not necessarily limited to) dictionary id.

As I understand, Nikita is interested in implementing 64-bit TOAST
pointers [2]. I must admit I didn't follow that thread too closely but
I can imagine the needs are similar.

Last but not least I remember somebody on the mailing list suggested
adding ZSTD compression support for TOAST, besides LZ4. Assuming I
didn't dream it, the proposal was rejected due to the limited amount
of free bits in ToastCompressionId. It was argued that two possible
combinations that are left should be treated with care and ZSTD will
not bring enough value to the users compared to LZ4.

These are 3 recent cases I could recall. This being said I think our
solution should be generic enough to cover possible future cases
and/or cases unknown to us yet.

[1]: https://postgr.es/m/CAJ7c6TM7%2BsTvwREeL74Y5U91%2B5ymNobRbOmnDRfdTonq9trZyQ%40mail.gmail.com
[2]: https://commitfest.postgresql.org/43/4296/

-- 
Best regards,
Aleksander Alekseev

On Mon, 22 May 2023 at 18:13, Nikita Malakhov <hukutoc@gmail.com> wrote:
>
> Hi,

Could you  please not top-post.

> Aleksander, I'm interested in extending TOAST pointer in various ways.
> 64-bit TOAST value ID allows to resolve very complex issue for production
> systems with large tables and heavy update rate.

Cool. I agree that this would be nice, though it's quite unlikely
we'll ever be able to use much more than 32 bits concurrently with the
current 32-bit block IDs. But indeed, it is a good way of reducing
time spent searching for unused toast IDs.

> I agree with Matthias that there should not be processing of TOAST pointer
> internals outside TOAST macros. Currently, TOASTed value is distinguished
> as VARATT_IS_EXTERNAL_ONDISK, and it should stay this way. Adding
> compression requires another implementation (extension) of
> VARATT_EXTERNAL because current supports only 2 compression methods -
> it has only 1 bit responsible for compression method, and there is a safe
> way to do so, without affecting default TOAST mechanics - we must keep
> it this way for compatibility issues and not to break DB upgrade.
>
> Also, I must remind that we should not forget about field alignment inside
> the TOAST pointer.

What field alignment inside the TOAST pointers?
Current TOAST pointers are not aligned: the varatt_external struct is
copied into and from the va_data section of varattrib_1b_e when we
need to access the data; so as far as I know this struct has no
alignment to speak of.

> As it was already mentioned, it seems not very reasonable trying to save
> a byte or two while we are storing out-of-line values of at least 2 kb in size.

If we were talking about the data we're storing externally, sure. But
this is data we store in the original tuple, and moving that around is
relatively expensive. Reducing the aligned size of the toast pointer
can help reduce the size of the heap tuple, thus increasing the
efficiency of the primary data table.

Kind regards,

Matthias van de Meent
Neon, Inc.

On Mon, May 22, 2023 at 6:47 AM Aleksander Alekseev
<aleksander@timescale.com> wrote:
> Last but not least I remember somebody on the mailing list suggested
> adding ZSTD compression support for TOAST, besides LZ4. Assuming I
> didn't dream it, the proposal was rejected due to the limited amount
> of free bits in ToastCompressionId. It was argued that two possible
> combinations that are left should be treated with care and ZSTD will
> not bring enough value to the users compared to LZ4.

This thread, I think:

    https://www.postgresql.org/message-id/flat/YoMiNmkztrslDbNS%40paquier.xyz

--Jacob

On Thu, May 18, 2023 at 8:06 AM Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:
> This enum still has many options to go before it exceeds the maximum
> of the uint8 va_tag field. Therefore, I don't think we have no disk
> representations left, nor do I think we'll need to add another option
> to the ToastCompressionId enum.
> As an example, we can add another VARTAG option for dictionary-enabled
> external toast; like what the pluggable toast patch worked on. I think
> we can salvage some ideas from that patch, even if the main idea got
> stuck.

Adding another VARTAG option is somewhat different from adding another
ToastCompressionId. I think that right now we have embedded in various
places the idea that VARTAG_EXTERNAL is the only thing that shows up
on disk, and we'd need to track down all such places and adjust them
if we add other VARTAG types in the future. Depending on how it is to
be used, adding a new ToastCompressionId might be less work. However,
I don't think we can use the possibility of adding a new VARTAG value
as a reason why it's OK to use up the last possible ToastCompressionId
value for something non-extensible.

For projects like this, the details matter a lot. If the goal is to
add a new compression type that behaves like the existing compression
types, more or less, then I think we should allocate the last
ToastCompressionId bit to mean "some other compression ID" and add a
1-byte header that says which one is in use. But if the new feature
being added is enough different from the other compression methods,
then it might be better to do it in some other way e.g. a new VARTAG.

--
Robert Haas
EDB: http://www.enterprisedb.com

On Tue, May 23, 2023 at 12:33:50PM -0400, Robert Haas wrote:
> For projects like this, the details matter a lot. If the goal is to
> add a new compression type that behaves like the existing compression
> types, more or less, then I think we should allocate the last
> ToastCompressionId bit to mean "some other compression ID" and add a
> 1-byte header that says which one is in use. But if the new feature
> being added is enough different from the other compression methods,
> then it might be better to do it in some other way e.g. a new VARTAG.

Agreed.  While the compression argument and the possibility to add
more options to toast pointers are very appealing, FWIW, I'd like to
think that the primary target is the 4-byte OID assignment limit of
where backends loop infinitely until a OID can be found, which can be
a real pain for users with a large number of blobs or just enough
toast data to trigger it.

Saying that even if I sent the patch for zstd on toast..
--
Michael

On Tue, 23 May 2023 at 18:34, Robert Haas <robertmhaas@gmail.com> wrote:
>
> On Thu, May 18, 2023 at 8:06 AM Matthias van de Meent
> <boekewurm+postgres@gmail.com> wrote:
> > This enum still has many options to go before it exceeds the maximum
> > of the uint8 va_tag field. Therefore, I don't think we have no disk
> > representations left, nor do I think we'll need to add another option
> > to the ToastCompressionId enum.
> > As an example, we can add another VARTAG option for dictionary-enabled
> > external toast; like what the pluggable toast patch worked on. I think
> > we can salvage some ideas from that patch, even if the main idea got
> > stuck.
>
> Adding another VARTAG option is somewhat different from adding another
> ToastCompressionId. I think that right now we have embedded in various
> places the idea that VARTAG_EXTERNAL is the only thing that shows up
> on disk, and we'd need to track down all such places and adjust them
> if we add other VARTAG types in the future. Depending on how it is to
> be used, adding a new ToastCompressionId might be less work. However,
> I don't think we can use the possibility of adding a new VARTAG value
> as a reason why it's OK to use up the last possible ToastCompressionId
> value for something non-extensible.

I think you might not have picked up on what I was arguing for, but I
agree with what you just said.

My comment on not needing to invent a new ToastCompressionId was on
the topic of adding capabilities^ to toast pointers that do things
differently than the current TOAST and need more info than just sizes,
2x 32-bit ID and a compression algorithm.

^ capabilities such as compression dictionaries (which would need to
store a dictionary ID in the pointer), TOAST IDs that are larger than
32 bits, and other such advances.

Kind regards,

Matthias van de Meent
Neon, Inc.

On Wed, May 24, 2023 at 11:50:21AM +0200, Matthias van de Meent wrote:
> I think you might not have picked up on what I was arguing for, but I
> agree with what you just said.
>
> My comment on not needing to invent a new ToastCompressionId was on
> the topic of adding capabilities^ to toast pointers that do things
> differently than the current TOAST and need more info than just sizes,
> 2x 32-bit ID and a compression algorithm.

I am not sure to understand why a new vartag is really required just
for the sake of compression when it comes to VARTAG_EXTERNAL, because
that's where the compression information is stored for ages.  The code
footprint gets more invasive, as well if you add more compression
methods as a new vartag implies more code areas to handle.

> ^ capabilities such as compression dictionaries (which would need to
> store a dictionary ID in the pointer), TOAST IDs that are larger than
> 32 bits, and other such advances.

Saying that, I don't really see why we cannot just do both, because it
is clear that many other projects want to fill in more data into
varlena headers for their own needs.  Hence, I would do:
1) Use the last bit of va_extinfo in varatt_external to link it more
info related to compression, and keep the compression information
close to varatt_external.
2) Add a new kind of "custom" vartag, for what any other requirements
want it to be.
--
Michael