Re: jsonb format is pessimal for toast compression

I looked into the issue reported in bug #11109. The problem appears to be
that jsonb's on-disk format is designed in such a way that the leading
portion of any JSON array or object will be fairly incompressible, because
it consists mostly of a strictly-increasing series of integer offsets.
This interacts poorly with the code in pglz_compress() that gives up if
it's found nothing compressible in the first first_success_by bytes of a
value-to-be-compressed. (first_success_by is 1024 in the default set of
compression parameters.)

As an example, here's gdb's report of the bitwise representation of the
example JSON value in the bug thread:

0x2ab85ac: 0x20000005 0x00000004 0x50003098 0x0000309f
0x2ab85bc: 0x000030ae 0x000030b8 0x000030cf 0x000030da
0x2ab85cc: 0x000030df 0x000030ee 0x00003105 0x6b6e756a
0x2ab85dc: 0x400000de 0x00000034 0x00000068 0x0000009c
0x2ab85ec: 0x000000d0 0x00000104 0x00000138 0x0000016c
0x2ab85fc: 0x000001a0 0x000001d4 0x00000208 0x0000023c
0x2ab860c: 0x00000270 0x000002a4 0x000002d8 0x0000030c
0x2ab861c: 0x00000340 0x00000374 0x000003a8 0x000003dc
0x2ab862c: 0x00000410 0x00000444 0x00000478 0x000004ac
0x2ab863c: 0x000004e0 0x00000514 0x00000548 0x0000057c
0x2ab864c: 0x000005b0 0x000005e4 0x00000618 0x0000064c
0x2ab865c: 0x00000680 0x000006b4 0x000006e8 0x0000071c
0x2ab866c: 0x00000750 0x00000784 0x000007b8 0x000007ec
0x2ab867c: 0x00000820 0x00000854 0x00000888 0x000008bc
0x2ab868c: 0x000008f0 0x00000924 0x00000958 0x0000098c
0x2ab869c: 0x000009c0 0x000009f4 0x00000a28 0x00000a5c
0x2ab86ac: 0x00000a90 0x00000ac4 0x00000af8 0x00000b2c
0x2ab86bc: 0x00000b60 0x00000b94 0x00000bc8 0x00000bfc
0x2ab86cc: 0x00000c30 0x00000c64 0x00000c98 0x00000ccc
0x2ab86dc: 0x00000d00 0x00000d34 0x00000d68 0x00000d9c
0x2ab86ec: 0x00000dd0 0x00000e04 0x00000e38 0x00000e6c
0x2ab86fc: 0x00000ea0 0x00000ed4 0x00000f08 0x00000f3c
0x2ab870c: 0x00000f70 0x00000fa4 0x00000fd8 0x0000100c
0x2ab871c: 0x00001040 0x00001074 0x000010a8 0x000010dc
0x2ab872c: 0x00001110 0x00001144 0x00001178 0x000011ac
0x2ab873c: 0x000011e0 0x00001214 0x00001248 0x0000127c
0x2ab874c: 0x000012b0 0x000012e4 0x00001318 0x0000134c
0x2ab875c: 0x00001380 0x000013b4 0x000013e8 0x0000141c
0x2ab876c: 0x00001450 0x00001484 0x000014b8 0x000014ec
0x2ab877c: 0x00001520 0x00001554 0x00001588 0x000015bc
0x2ab878c: 0x000015f0 0x00001624 0x00001658 0x0000168c
0x2ab879c: 0x000016c0 0x000016f4 0x00001728 0x0000175c
0x2ab87ac: 0x00001790 0x000017c4 0x000017f8 0x0000182c
0x2ab87bc: 0x00001860 0x00001894 0x000018c8 0x000018fc
0x2ab87cc: 0x00001930 0x00001964 0x00001998 0x000019cc
0x2ab87dc: 0x00001a00 0x00001a34 0x00001a68 0x00001a9c
0x2ab87ec: 0x00001ad0 0x00001b04 0x00001b38 0x00001b6c
0x2ab87fc: 0x00001ba0 0x00001bd4 0x00001c08 0x00001c3c
0x2ab880c: 0x00001c70 0x00001ca4 0x00001cd8 0x00001d0c
0x2ab881c: 0x00001d40 0x00001d74 0x00001da8 0x00001ddc
0x2ab882c: 0x00001e10 0x00001e44 0x00001e78 0x00001eac
0x2ab883c: 0x00001ee0 0x00001f14 0x00001f48 0x00001f7c
0x2ab884c: 0x00001fb0 0x00001fe4 0x00002018 0x0000204c
0x2ab885c: 0x00002080 0x000020b4 0x000020e8 0x0000211c
0x2ab886c: 0x00002150 0x00002184 0x000021b8 0x000021ec
0x2ab887c: 0x00002220 0x00002254 0x00002288 0x000022bc
0x2ab888c: 0x000022f0 0x00002324 0x00002358 0x0000238c
0x2ab889c: 0x000023c0 0x000023f4 0x00002428 0x0000245c
0x2ab88ac: 0x00002490 0x000024c4 0x000024f8 0x0000252c
0x2ab88bc: 0x00002560 0x00002594 0x000025c8 0x000025fc
0x2ab88cc: 0x00002630 0x00002664 0x00002698 0x000026cc
0x2ab88dc: 0x00002700 0x00002734 0x00002768 0x0000279c
0x2ab88ec: 0x000027d0 0x00002804 0x00002838 0x0000286c
0x2ab88fc: 0x000028a0 0x000028d4 0x00002908 0x0000293c
0x2ab890c: 0x00002970 0x000029a4 0x000029d8 0x00002a0c
0x2ab891c: 0x00002a40 0x00002a74 0x00002aa8 0x00002adc
0x2ab892c: 0x00002b10 0x00002b44 0x00002b78 0x00002bac
0x2ab893c: 0x00002be0 0x00002c14 0x00002c48 0x00002c7c
0x2ab894c: 0x00002cb0 0x00002ce4 0x00002d18 0x32343231
0x2ab895c: 0x74653534 0x74656577 0x33746577 0x77673534
0x2ab896c: 0x74657274 0x33347477 0x72777120 0x20717771
0x2ab897c: 0x65727771 0x20777120 0x66647372 0x73616b6c
0x2ab898c: 0x33353471 0x71772035 0x72777172 0x71727771
0x2ab899c: 0x77203277 0x72777172 0x71727771 0x33323233
0x2ab89ac: 0x6b207732 0x20657773 0x73616673 0x73207372
0x2ab89bc: 0x64736664 0x32343231 0x74653534 0x74656577
0x2ab89cc: 0x33746577 0x77673534 0x74657274 0x33347477
0x2ab89dc: 0x72777120 0x20717771 0x65727771 0x20777120
0x2ab89ec: 0x66647372 0x73616b6c 0x33353471 0x71772035
0x2ab89fc: 0x72777172 0x71727771 0x77203277 0x72777172
0x2ab8a0c: 0x71727771 0x33323233 0x6b207732 0x20657773
0x2ab8a1c: 0x73616673 0x73207372 0x64736664 0x32343231
0x2ab8a2c: 0x74653534 0x74656577 0x33746577 0x77673534
0x2ab8a3c: 0x74657274 0x33347477 0x72777120 0x20717771
0x2ab8a4c: 0x65727771 0x20777120 0x66647372 0x73616b6c
0x2ab8a5c: 0x33353471 0x71772035 0x72777172 0x71727771
0x2ab8a6c: 0x77203277 0x72777172 0x71727771 0x33323233
0x2ab8a7c: 0x6b207732 0x20657773 0x73616673 0x73207372
0x2ab8a8c: 0x64736664 0x32343231 0x74653534 0x74656577
0x2ab8a9c: 0x33746577 0x77673534 0x74657274 0x33347477
0x2ab8aac: 0x72777120 0x20717771 0x65727771 0x20777120
0x2ab8abc: 0x66647372 0x73616b6c 0x33353471 0x71772035
0x2ab8acc: 0x72777172 0x71727771 0x77203277 0x72777172
0x2ab8adc: 0x71727771 0x33323233 0x6b207732 0x20657773
0x2ab8aec: 0x73616673 0x73207372 0x64736664 0x32343231
0x2ab8afc: 0x74653534 0x74656577 0x33746577 0x77673534
...
0x2abb61c: 0x74657274 0x33347477 0x72777120 0x20717771
0x2abb62c: 0x65727771 0x20777120 0x66647372 0x73616b6c
0x2abb63c: 0x33353471 0x71772035 0x72777172 0x71727771
0x2abb64c: 0x77203277 0x72777172 0x71727771 0x33323233
0x2abb65c: 0x6b207732 0x20657773 0x73616673 0x73207372
0x2abb66c: 0x64736664 0x537a6962 0x41706574 0x73756220
0x2abb67c: 0x73656e69 0x74732073 0x45617065 0x746e6576
0x2abb68c: 0x656d6954 0x34313032 0x2d38302d 0x32203730
0x2abb69c: 0x33323a31 0x2e33333a 0x62393434 0x6f4c7a69
0x2abb6ac: 0x69746163 0x61506e6f 0x74736972 0x736e6172
0x2abb6bc: 0x69746361 0x61446e6f 0x30326574 0x302d3431
0x2abb6cc: 0x37302d38 0x3a313220 0x333a3332 0x34342e33

There is plenty of compressible data once we get into the repetitive
strings in the payload part --- but that starts at offset 944, and up to
that point there is nothing that pg_lzcompress can get a handle on. There
are, by definition, no sequences of 4 or more repeated bytes in that area.
I think in principle pg_lzcompress could decide to compress the 3-byte
sequences consisting of the high-order 24 bits of each offset; but it
doesn't choose to do so, probably because of the way its lookup hash table
works:

* pglz_hist_idx -
*
* Computes the history table slot for the lookup by the next 4
* characters in the input.
*
* NB: because we use the next 4 characters, we are not guaranteed to
* find 3-character matches; they very possibly will be in the wrong
* hash list. This seems an acceptable tradeoff for spreading out the
* hash keys more.

For jsonb header data, the "next 4 characters" are *always* different, so
only a chance hash collision can result in a match. There is therefore a
pretty good chance that no compression will occur before it gives up
because of first_success_by.

I'm not sure if there is any easy fix for this. We could possibly change
the default first_success_by value, but I think that'd just be postponing
the problem to larger jsonb objects/arrays, and it would hurt performance
for genuinely incompressible data. A somewhat painful, but not yet
out-of-the-question, alternative is to change the jsonb on-disk
representation. Perhaps the JEntry array could be defined as containing
element lengths instead of element ending offsets. Not sure though if
that would break binary searching for JSON object keys.

regards, tom lane

Apologies if this is a ridiculous suggestion, but I believe that swapping
out the compression algorithm (for Snappy, for example) has been discussed
in the past. I wonder if that algorithm is sufficiently different that it
would produce a better result, and if that might not be preferable to some
of the other options.

On Thu, Aug 7, 2014 at 11:17 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> I looked into the issue reported in bug #11109. The problem appears to be
> that jsonb's on-disk format is designed in such a way that the leading
> portion of any JSON array or object will be fairly incompressible, because
> it consists mostly of a strictly-increasing series of integer offsets.
> This interacts poorly with the code in pglz_compress() that gives up if
> it's found nothing compressible in the first first_success_by bytes of a
> value-to-be-compressed. (first_success_by is 1024 in the default set of
> compression parameters.)
>
> As an example, here's gdb's report of the bitwise representation of the
> example JSON value in the bug thread:
>
> 0x2ab85ac: 0x20000005 0x00000004 0x50003098 0x0000309f
> 0x2ab85bc: 0x000030ae 0x000030b8 0x000030cf 0x000030da
> 0x2ab85cc: 0x000030df 0x000030ee 0x00003105 0x6b6e756a
> 0x2ab85dc: 0x400000de 0x00000034 0x00000068 0x0000009c
> 0x2ab85ec: 0x000000d0 0x00000104 0x00000138 0x0000016c
> 0x2ab85fc: 0x000001a0 0x000001d4 0x00000208 0x0000023c
> 0x2ab860c: 0x00000270 0x000002a4 0x000002d8 0x0000030c
> 0x2ab861c: 0x00000340 0x00000374 0x000003a8 0x000003dc
> 0x2ab862c: 0x00000410 0x00000444 0x00000478 0x000004ac
> 0x2ab863c: 0x000004e0 0x00000514 0x00000548 0x0000057c
> 0x2ab864c: 0x000005b0 0x000005e4 0x00000618 0x0000064c
> 0x2ab865c: 0x00000680 0x000006b4 0x000006e8 0x0000071c
> 0x2ab866c: 0x00000750 0x00000784 0x000007b8 0x000007ec
> 0x2ab867c: 0x00000820 0x00000854 0x00000888 0x000008bc
> 0x2ab868c: 0x000008f0 0x00000924 0x00000958 0x0000098c
> 0x2ab869c: 0x000009c0 0x000009f4 0x00000a28 0x00000a5c
> 0x2ab86ac: 0x00000a90 0x00000ac4 0x00000af8 0x00000b2c
> 0x2ab86bc: 0x00000b60 0x00000b94 0x00000bc8 0x00000bfc
> 0x2ab86cc: 0x00000c30 0x00000c64 0x00000c98 0x00000ccc
> 0x2ab86dc: 0x00000d00 0x00000d34 0x00000d68 0x00000d9c
> 0x2ab86ec: 0x00000dd0 0x00000e04 0x00000e38 0x00000e6c
> 0x2ab86fc: 0x00000ea0 0x00000ed4 0x00000f08 0x00000f3c
> 0x2ab870c: 0x00000f70 0x00000fa4 0x00000fd8 0x0000100c
> 0x2ab871c: 0x00001040 0x00001074 0x000010a8 0x000010dc
> 0x2ab872c: 0x00001110 0x00001144 0x00001178 0x000011ac
> 0x2ab873c: 0x000011e0 0x00001214 0x00001248 0x0000127c
> 0x2ab874c: 0x000012b0 0x000012e4 0x00001318 0x0000134c
> 0x2ab875c: 0x00001380 0x000013b4 0x000013e8 0x0000141c
> 0x2ab876c: 0x00001450 0x00001484 0x000014b8 0x000014ec
> 0x2ab877c: 0x00001520 0x00001554 0x00001588 0x000015bc
> 0x2ab878c: 0x000015f0 0x00001624 0x00001658 0x0000168c
> 0x2ab879c: 0x000016c0 0x000016f4 0x00001728 0x0000175c
> 0x2ab87ac: 0x00001790 0x000017c4 0x000017f8 0x0000182c
> 0x2ab87bc: 0x00001860 0x00001894 0x000018c8 0x000018fc
> 0x2ab87cc: 0x00001930 0x00001964 0x00001998 0x000019cc
> 0x2ab87dc: 0x00001a00 0x00001a34 0x00001a68 0x00001a9c
> 0x2ab87ec: 0x00001ad0 0x00001b04 0x00001b38 0x00001b6c
> 0x2ab87fc: 0x00001ba0 0x00001bd4 0x00001c08 0x00001c3c
> 0x2ab880c: 0x00001c70 0x00001ca4 0x00001cd8 0x00001d0c
> 0x2ab881c: 0x00001d40 0x00001d74 0x00001da8 0x00001ddc
> 0x2ab882c: 0x00001e10 0x00001e44 0x00001e78 0x00001eac
> 0x2ab883c: 0x00001ee0 0x00001f14 0x00001f48 0x00001f7c
> 0x2ab884c: 0x00001fb0 0x00001fe4 0x00002018 0x0000204c
> 0x2ab885c: 0x00002080 0x000020b4 0x000020e8 0x0000211c
> 0x2ab886c: 0x00002150 0x00002184 0x000021b8 0x000021ec
> 0x2ab887c: 0x00002220 0x00002254 0x00002288 0x000022bc
> 0x2ab888c: 0x000022f0 0x00002324 0x00002358 0x0000238c
> 0x2ab889c: 0x000023c0 0x000023f4 0x00002428 0x0000245c
> 0x2ab88ac: 0x00002490 0x000024c4 0x000024f8 0x0000252c
> 0x2ab88bc: 0x00002560 0x00002594 0x000025c8 0x000025fc
> 0x2ab88cc: 0x00002630 0x00002664 0x00002698 0x000026cc
> 0x2ab88dc: 0x00002700 0x00002734 0x00002768 0x0000279c
> 0x2ab88ec: 0x000027d0 0x00002804 0x00002838 0x0000286c
> 0x2ab88fc: 0x000028a0 0x000028d4 0x00002908 0x0000293c
> 0x2ab890c: 0x00002970 0x000029a4 0x000029d8 0x00002a0c
> 0x2ab891c: 0x00002a40 0x00002a74 0x00002aa8 0x00002adc
> 0x2ab892c: 0x00002b10 0x00002b44 0x00002b78 0x00002bac
> 0x2ab893c: 0x00002be0 0x00002c14 0x00002c48 0x00002c7c
> 0x2ab894c: 0x00002cb0 0x00002ce4 0x00002d18 0x32343231
> 0x2ab895c: 0x74653534 0x74656577 0x33746577 0x77673534
> 0x2ab896c: 0x74657274 0x33347477 0x72777120 0x20717771
> 0x2ab897c: 0x65727771 0x20777120 0x66647372 0x73616b6c
> 0x2ab898c: 0x33353471 0x71772035 0x72777172 0x71727771
> 0x2ab899c: 0x77203277 0x72777172 0x71727771 0x33323233
> 0x2ab89ac: 0x6b207732 0x20657773 0x73616673 0x73207372
> 0x2ab89bc: 0x64736664 0x32343231 0x74653534 0x74656577
> 0x2ab89cc: 0x33746577 0x77673534 0x74657274 0x33347477
> 0x2ab89dc: 0x72777120 0x20717771 0x65727771 0x20777120
> 0x2ab89ec: 0x66647372 0x73616b6c 0x33353471 0x71772035
> 0x2ab89fc: 0x72777172 0x71727771 0x77203277 0x72777172
> 0x2ab8a0c: 0x71727771 0x33323233 0x6b207732 0x20657773
> 0x2ab8a1c: 0x73616673 0x73207372 0x64736664 0x32343231
> 0x2ab8a2c: 0x74653534 0x74656577 0x33746577 0x77673534
> 0x2ab8a3c: 0x74657274 0x33347477 0x72777120 0x20717771
> 0x2ab8a4c: 0x65727771 0x20777120 0x66647372 0x73616b6c
> 0x2ab8a5c: 0x33353471 0x71772035 0x72777172 0x71727771
> 0x2ab8a6c: 0x77203277 0x72777172 0x71727771 0x33323233
> 0x2ab8a7c: 0x6b207732 0x20657773 0x73616673 0x73207372
> 0x2ab8a8c: 0x64736664 0x32343231 0x74653534 0x74656577
> 0x2ab8a9c: 0x33746577 0x77673534 0x74657274 0x33347477
> 0x2ab8aac: 0x72777120 0x20717771 0x65727771 0x20777120
> 0x2ab8abc: 0x66647372 0x73616b6c 0x33353471 0x71772035
> 0x2ab8acc: 0x72777172 0x71727771 0x77203277 0x72777172
> 0x2ab8adc: 0x71727771 0x33323233 0x6b207732 0x20657773
> 0x2ab8aec: 0x73616673 0x73207372 0x64736664 0x32343231
> 0x2ab8afc: 0x74653534 0x74656577 0x33746577 0x77673534
> ...
> 0x2abb61c: 0x74657274 0x33347477 0x72777120 0x20717771
> 0x2abb62c: 0x65727771 0x20777120 0x66647372 0x73616b6c
> 0x2abb63c: 0x33353471 0x71772035 0x72777172 0x71727771
> 0x2abb64c: 0x77203277 0x72777172 0x71727771 0x33323233
> 0x2abb65c: 0x6b207732 0x20657773 0x73616673 0x73207372
> 0x2abb66c: 0x64736664 0x537a6962 0x41706574 0x73756220
> 0x2abb67c: 0x73656e69 0x74732073 0x45617065 0x746e6576
> 0x2abb68c: 0x656d6954 0x34313032 0x2d38302d 0x32203730
> 0x2abb69c: 0x33323a31 0x2e33333a 0x62393434 0x6f4c7a69
> 0x2abb6ac: 0x69746163 0x61506e6f 0x74736972 0x736e6172
> 0x2abb6bc: 0x69746361 0x61446e6f 0x30326574 0x302d3431
> 0x2abb6cc: 0x37302d38 0x3a313220 0x333a3332 0x34342e33
>
> There is plenty of compressible data once we get into the repetitive
> strings in the payload part --- but that starts at offset 944, and up to
> that point there is nothing that pg_lzcompress can get a handle on. There
> are, by definition, no sequences of 4 or more repeated bytes in that area.
> I think in principle pg_lzcompress could decide to compress the 3-byte
> sequences consisting of the high-order 24 bits of each offset; but it
> doesn't choose to do so, probably because of the way its lookup hash table
> works:
>
> * pglz_hist_idx -
> *
> * Computes the history table slot for the lookup by the next
> 4
> * characters in the input.
> *
> * NB: because we use the next 4 characters, we are not guaranteed to
> * find 3-character matches; they very possibly will be in the wrong
> * hash list. This seems an acceptable tradeoff for spreading out the
> * hash keys more.
>
> For jsonb header data, the "next 4 characters" are *always* different, so
> only a chance hash collision can result in a match. There is therefore a
> pretty good chance that no compression will occur before it gives up
> because of first_success_by.
>
> I'm not sure if there is any easy fix for this. We could possibly change
> the default first_success_by value, but I think that'd just be postponing
> the problem to larger jsonb objects/arrays, and it would hurt performance
> for genuinely incompressible data. A somewhat painful, but not yet
> out-of-the-question, alternative is to change the jsonb on-disk
> representation. Perhaps the JEntry array could be defined as containing
> element lengths instead of element ending offsets. Not sure though if
> that would break binary searching for JSON object keys.
>
> regards, tom lane
>

* Tom Lane (tgl(at)sss(dot)pgh(dot)pa(dot)us) wrote:
> I looked into the issue reported in bug #11109. The problem appears to be
> that jsonb's on-disk format is designed in such a way that the leading
> portion of any JSON array or object will be fairly incompressible, because
> it consists mostly of a strictly-increasing series of integer offsets.
> This interacts poorly with the code in pglz_compress() that gives up if
> it's found nothing compressible in the first first_success_by bytes of a
> value-to-be-compressed. (first_success_by is 1024 in the default set of
> compression parameters.)

I haven't looked at this in any detail, so take this with a grain of
salt, but what about teaching pglz_compress about using an offset
farther into the data, if the incoming data is quite a bit larger than
1k? This is just a test to see if it's worthwhile to keep going, no? I
wonder if this might even be able to be provided as a type-specific
option, to avoid changing the behavior for types other than jsonb in
this regard.

(I'm imaginging a boolean saying "pick a random sample", or perhaps a
function which can be called that'll return "here's where you wanna test
if this thing is gonna compress at all")

I'm rather disinclined to change the on-disk format because of this
specific test, that feels a bit like the tail wagging the dog to me,
especially as I do hope that some day we'll figure out a way to use a
better compression algorithm than pglz.

Thanks,

Stephen

On Fri, Aug 8, 2014 at 10:48 AM, Stephen Frost <sfrost(at)snowman(dot)net> wrote:

> * Tom Lane (tgl(at)sss(dot)pgh(dot)pa(dot)us) wrote:
> > I looked into the issue reported in bug #11109. The problem appears to
> be
> > that jsonb's on-disk format is designed in such a way that the leading
> > portion of any JSON array or object will be fairly incompressible,
> because
> > it consists mostly of a strictly-increasing series of integer offsets.
> > This interacts poorly with the code in pglz_compress() that gives up if
> > it's found nothing compressible in the first first_success_by bytes of a
> > value-to-be-compressed. (first_success_by is 1024 in the default set of
> > compression parameters.)
>
> I haven't looked at this in any detail, so take this with a grain of
> salt, but what about teaching pglz_compress about using an offset
> farther into the data, if the incoming data is quite a bit larger than
> 1k? This is just a test to see if it's worthwhile to keep going, no? I
> wonder if this might even be able to be provided as a type-specific
> option, to avoid changing the behavior for types other than jsonb in
> this regard.
>
>
+1 for offset. Or sample the data in the beginning, middle and end.
Obviously one could always come up with worst case, but.

> (I'm imaginging a boolean saying "pick a random sample", or perhaps a
> function which can be called that'll return "here's where you wanna test
> if this thing is gonna compress at all")
>
> I'm rather disinclined to change the on-disk format because of this
> specific test, that feels a bit like the tail wagging the dog to me,
> especially as I do hope that some day we'll figure out a way to use a
> better compression algorithm than pglz.
>
> Thanks,
>
> Stephen
>

--
Best Wishes,
Ashutosh Bapat
EnterpriseDB Corporation
The Postgres Database Company

On 08/07/2014 11:17 PM, Tom Lane wrote:
> I looked into the issue reported in bug #11109. The problem appears to be
> that jsonb's on-disk format is designed in such a way that the leading
> portion of any JSON array or object will be fairly incompressible, because
> it consists mostly of a strictly-increasing series of integer offsets.
> This interacts poorly with the code in pglz_compress() that gives up if
> it's found nothing compressible in the first first_success_by bytes of a
> value-to-be-compressed. (first_success_by is 1024 in the default set of
> compression parameters.)

[snip]

> There is plenty of compressible data once we get into the repetitive
> strings in the payload part --- but that starts at offset 944, and up to
> that point there is nothing that pg_lzcompress can get a handle on. There
> are, by definition, no sequences of 4 or more repeated bytes in that area.
> I think in principle pg_lzcompress could decide to compress the 3-byte
> sequences consisting of the high-order 24 bits of each offset; but it
> doesn't choose to do so, probably because of the way its lookup hash table
> works:
>
> * pglz_hist_idx -
> *
> * Computes the history table slot for the lookup by the next 4
> * characters in the input.
> *
> * NB: because we use the next 4 characters, we are not guaranteed to
> * find 3-character matches; they very possibly will be in the wrong
> * hash list. This seems an acceptable tradeoff for spreading out the
> * hash keys more.
>
> For jsonb header data, the "next 4 characters" are *always* different, so
> only a chance hash collision can result in a match. There is therefore a
> pretty good chance that no compression will occur before it gives up
> because of first_success_by.
>
> I'm not sure if there is any easy fix for this. We could possibly change
> the default first_success_by value, but I think that'd just be postponing
> the problem to larger jsonb objects/arrays, and it would hurt performance
> for genuinely incompressible data. A somewhat painful, but not yet
> out-of-the-question, alternative is to change the jsonb on-disk
> representation. Perhaps the JEntry array could be defined as containing
> element lengths instead of element ending offsets. Not sure though if
> that would break binary searching for JSON object keys.
>
>

Ouch.

Back when this structure was first presented at pgCon 2013, I wondered
if we shouldn't extract the strings into a dictionary, because of key
repetition, and convinced myself that this shouldn't be necessary
because in significant cases TOAST would take care of it.

Maybe we should have pglz_compress() look at the *last* 1024 bytes if it
can't find anything worth compressing in the first, for values larger
than a certain size.

It's worth noting that this is a fairly pathological case. AIUI the
example you constructed has an array with 100k string elements. I don't
think that's typical. So I suspect that unless I've misunderstood the
statement of the problem we're going to find that almost all the jsonb
we will be storing is still compressible.

cheers

andrew

Stephen Frost <sfrost(at)snowman(dot)net> writes:
> * Tom Lane (tgl(at)sss(dot)pgh(dot)pa(dot)us) wrote:
>> I looked into the issue reported in bug #11109. The problem appears to be
>> that jsonb's on-disk format is designed in such a way that the leading
>> portion of any JSON array or object will be fairly incompressible, because
>> it consists mostly of a strictly-increasing series of integer offsets.
>> This interacts poorly with the code in pglz_compress() that gives up if
>> it's found nothing compressible in the first first_success_by bytes of a
>> value-to-be-compressed. (first_success_by is 1024 in the default set of
>> compression parameters.)

> I haven't looked at this in any detail, so take this with a grain of
> salt, but what about teaching pglz_compress about using an offset
> farther into the data, if the incoming data is quite a bit larger than
> 1k? This is just a test to see if it's worthwhile to keep going, no?

Well, the point of the existing approach is that it's a *nearly free*
test to see if it's worthwhile to keep going; there's just one if-test
added in the outer loop of the compression code. (cf commit ad434473ebd2,
which added that along with some other changes.) AFAICS, what we'd have
to do to do it as you suggest would to execute compression on some subset
of the data and then throw away that work entirely. I do not find that
attractive, especially when for most datatypes there's no particular
reason to look at one subset instead of another.

> I'm rather disinclined to change the on-disk format because of this
> specific test, that feels a bit like the tail wagging the dog to me,
> especially as I do hope that some day we'll figure out a way to use a
> better compression algorithm than pglz.

I'm unimpressed by that argument too, for a number of reasons:

1. The real problem here is that jsonb is emitting quite a bit of
fundamentally-nonrepetitive data, even when the user-visible input is very
repetitive. That's a compression-unfriendly transformation by anyone's
measure. Assuming that some future replacement for pg_lzcompress() will
nonetheless be able to compress the data strikes me as mostly wishful
thinking. Besides, we'd more than likely have a similar early-exit rule
in any substitute implementation, so that we'd still be at risk even if
it usually worked.

2. Are we going to ship 9.4 without fixing this? I definitely don't see
replacing pg_lzcompress as being on the agenda for 9.4, whereas changing
jsonb is still within the bounds of reason.

Considering all the hype that's built up around jsonb, shipping a design
with a fundamental performance handicap doesn't seem like a good plan
to me. We could perhaps band-aid around it by using different compression
parameters for jsonb, although that would require some painful API changes
since toast_compress_datum() doesn't know what datatype it's operating on.

regards, tom lane

Andrew Dunstan <andrew(at)dunslane(dot)net> writes:
> On 08/07/2014 11:17 PM, Tom Lane wrote:
>> I looked into the issue reported in bug #11109. The problem appears to be
>> that jsonb's on-disk format is designed in such a way that the leading
>> portion of any JSON array or object will be fairly incompressible, because
>> it consists mostly of a strictly-increasing series of integer offsets.

> Ouch.

> Back when this structure was first presented at pgCon 2013, I wondered
> if we shouldn't extract the strings into a dictionary, because of key
> repetition, and convinced myself that this shouldn't be necessary
> because in significant cases TOAST would take care of it.

That's not really the issue here, I think. The problem is that a
relatively minor aspect of the representation, namely the choice to store
a series of offsets rather than a series of lengths, produces
nonrepetitive data even when the original input is repetitive.

> Maybe we should have pglz_compress() look at the *last* 1024 bytes if it
> can't find anything worth compressing in the first, for values larger
> than a certain size.

Not possible with anything like the current implementation, since it's
just an on-the-fly status check not a trial compression.

> It's worth noting that this is a fairly pathological case. AIUI the
> example you constructed has an array with 100k string elements. I don't
> think that's typical. So I suspect that unless I've misunderstood the
> statement of the problem we're going to find that almost all the jsonb
> we will be storing is still compressible.

Actually, the 100K-string example I constructed *did* compress. Larry's
example that's not compressing is only about 12kB. AFAICS, the threshold
for trouble is in the vicinity of 256 array or object entries (resulting
in a 1kB JEntry array). That doesn't seem especially high. There is a
probabilistic component as to whether the early-exit case will actually
fire, since any chance hash collision will probably result in some 3-byte
offset prefix getting compressed. But the fact that a beta tester tripped
over this doesn't leave me with a warm feeling about the odds that it
won't happen much in the field.

regards, tom lane

On 08/08/2014 11:18 AM, Tom Lane wrote:
> Andrew Dunstan <andrew(at)dunslane(dot)net> writes:
>> On 08/07/2014 11:17 PM, Tom Lane wrote:
>>> I looked into the issue reported in bug #11109. The problem appears to be
>>> that jsonb's on-disk format is designed in such a way that the leading
>>> portion of any JSON array or object will be fairly incompressible, because
>>> it consists mostly of a strictly-increasing series of integer offsets.
>
>> Back when this structure was first presented at pgCon 2013, I wondered
>> if we shouldn't extract the strings into a dictionary, because of key
>> repetition, and convinced myself that this shouldn't be necessary
>> because in significant cases TOAST would take care of it.
> That's not really the issue here, I think. The problem is that a
> relatively minor aspect of the representation, namely the choice to store
> a series of offsets rather than a series of lengths, produces
> nonrepetitive data even when the original input is repetitive.

It would certainly be worth validating that changing this would fix the
problem.

I don't know how invasive that would be - I suspect (without looking
very closely) not terribly much.

> 2. Are we going to ship 9.4 without fixing this? I definitely don't see
> replacing pg_lzcompress as being on the agenda for 9.4, whereas changing
> jsonb is still within the bounds of reason.
>
> Considering all the hype that's built up around jsonb, shipping a design
> with a fundamental performance handicap doesn't seem like a good plan
> to me. We could perhaps band-aid around it by using different compression
> parameters for jsonb, although that would require some painful API changes
> since toast_compress_datum() doesn't know what datatype it's operating on.
>
>

Yeah, it would be a bit painful, but after all finding out this sort of
thing is why we have betas.

cheers

andrew

Andrew Dunstan <andrew(at)dunslane(dot)net> writes:
> On 08/08/2014 11:18 AM, Tom Lane wrote:
>> That's not really the issue here, I think. The problem is that a
>> relatively minor aspect of the representation, namely the choice to store
>> a series of offsets rather than a series of lengths, produces
>> nonrepetitive data even when the original input is repetitive.

> It would certainly be worth validating that changing this would fix the
> problem.
> I don't know how invasive that would be - I suspect (without looking
> very closely) not terribly much.

I took a quick look and saw that this wouldn't be that easy to get around.
As I'd suspected upthread, there are places that do random access into a
JEntry array, such as the binary search in findJsonbValueFromContainer().
If we have to add up all the preceding lengths to locate the corresponding
value part, we lose the performance advantages of binary search. AFAICS
that's applied directly to the on-disk representation. I'd thought
perhaps there was always a transformation step to build a pointer list,
but nope.

regards, tom lane

On Fri, Aug 8, 2014 at 8:02 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Stephen Frost <sfrost(at)snowman(dot)net> writes:
> > * Tom Lane (tgl(at)sss(dot)pgh(dot)pa(dot)us) wrote:
>
> > I'm rather disinclined to change the on-disk format because of this
> > specific test, that feels a bit like the tail wagging the dog to me,
> > especially as I do hope that some day we'll figure out a way to use a
> > better compression algorithm than pglz.
>
> I'm unimpressed by that argument too, for a number of reasons:
>
> 1. The real problem here is that jsonb is emitting quite a bit of
> fundamentally-nonrepetitive data, even when the user-visible input is very
> repetitive. That's a compression-unfriendly transformation by anyone's
> measure. Assuming that some future replacement for pg_lzcompress() will
> nonetheless be able to compress the data strikes me as mostly wishful
> thinking. Besides, we'd more than likely have a similar early-exit rule
> in any substitute implementation, so that we'd still be at risk even if
> it usually worked.
>

Would an answer be to switch the location of the jsonb "header" data to the
end of the field as opposed to the beginning of the field? That would allow
pglz to see what it wants to see early on and go to work when possible?

Add an offset at the top of the field to show where to look - but then it
would be the same in terms of functionality outside of that? Or pretty
close?

John

John W Higgins <wishdev(at)gmail(dot)com> writes:
> Would an answer be to switch the location of the jsonb "header" data to the
> end of the field as opposed to the beginning of the field? That would allow
> pglz to see what it wants to see early on and go to work when possible?

Hm, might work. Seems a bit odd, but it would make pglz_compress happier.

OTOH, the big-picture issue here is that jsonb is generating
noncompressible data in the first place. Putting it somewhere else in the
Datum doesn't change the fact that we're going to have bloated storage,
even if we dodge the early-exit problem. (I suspect the compression
disadvantage vs text/plain-json that I showed yesterday is coming largely
from that offset array.) But I don't currently see how to avoid that and
still preserve the fast binary-search key lookup property, which is surely
a nice thing to have.

regards, tom lane

On 08/08/2014 12:04 PM, John W Higgins wrote:

>
> Would an answer be to switch the location of the jsonb "header" data
> to the end of the field as opposed to the beginning of the field? That
> would allow pglz to see what it wants to see early on and go to work
> when possible?
>
> Add an offset at the top of the field to show where to look - but then
> it would be the same in terms of functionality outside of that? Or
> pretty close?
>

That might make building up jsonb structures piece by piece as we do
difficult.

cheers

andrew

On 08/08/2014 11:54 AM, Tom Lane wrote:
> Andrew Dunstan <andrew(at)dunslane(dot)net> writes:
>> On 08/08/2014 11:18 AM, Tom Lane wrote:
>>> That's not really the issue here, I think. The problem is that a
>>> relatively minor aspect of the representation, namely the choice to store
>>> a series of offsets rather than a series of lengths, produces
>>> nonrepetitive data even when the original input is repetitive.
>> It would certainly be worth validating that changing this would fix the
>> problem.
>> I don't know how invasive that would be - I suspect (without looking
>> very closely) not terribly much.
> I took a quick look and saw that this wouldn't be that easy to get around.
> As I'd suspected upthread, there are places that do random access into a
> JEntry array, such as the binary search in findJsonbValueFromContainer().
> If we have to add up all the preceding lengths to locate the corresponding
> value part, we lose the performance advantages of binary search. AFAICS
> that's applied directly to the on-disk representation. I'd thought
> perhaps there was always a transformation step to build a pointer list,
> but nope.
>
>

It would be interesting to know what the performance hit would be if we
calculated the offsets/pointers on the fly, especially if we could cache
it somehow. The main benefit of binary search is in saving on
comparisons, especially of strings, ISTM, and that could still be
available - this would just be a bit of extra arithmetic.

cheers

andrew

> value-to-be-compressed. (first_success_by is 1024 in the default set of
> compression parameters.)

Curious idea: we could swap JEntry array and values: values in the
begining of type will be catched by pg_lzcompress. But we will need to
know offset of JEntry array, so header will grow up till 8 bytes
(actually, it will be a varlena header!)

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

> Curious idea: we could swap JEntry array and values: values in the
> begining of type will be catched by pg_lzcompress. But we will need to
> know offset of JEntry array, so header will grow up till 8 bytes
> (actually, it will be a varlena header!)

May be I wasn't clear:jsonb type will start from string collection
instead of JEntry array, JEntry array will be placed at the end of
object/array. so, pg_lzcompress will find repeatable 4-byte pieces in
first 1024 bytes of jsonb.

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

On Fri, Aug 8, 2014 at 11:02:26AM -0400, Tom Lane wrote:
> 2. Are we going to ship 9.4 without fixing this? I definitely don't see
> replacing pg_lzcompress as being on the agenda for 9.4, whereas changing
> jsonb is still within the bounds of reason.

FYI, pg_upgrade could be taught to refuse to upgrade from earlier 9.4
betas and report the problem JSONB columns.

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ Everyone has their own god. +

On 08/08/2014 08:02 AM, Tom Lane wrote:
> 2. Are we going to ship 9.4 without fixing this? I definitely don't see
> replacing pg_lzcompress as being on the agenda for 9.4, whereas changing
> jsonb is still within the bounds of reason.
>
> Considering all the hype that's built up around jsonb, shipping a design
> with a fundamental performance handicap doesn't seem like a good plan
> to me. We could perhaps band-aid around it by using different compression
> parameters for jsonb, although that would require some painful API changes
> since toast_compress_datum() doesn't know what datatype it's operating on.

I would rather ship late than ship a noncompressable JSONB.

One we ship 9.4, many users are going to load 100's of GB into JSONB
fields. Even if we fix the compressability issue in 9.5, those users
won't be able to fix the compression without rewriting all their data,
which could be prohibitive. And we'll be in a position where we have
to support the 9.4 JSONB format/compression technique for years so that
users aren't blocked from upgrading.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On Fri, Aug 8, 2014 at 9:14 PM, Teodor Sigaev <teodor(at)sigaev(dot)ru> wrote:

> Curious idea: we could swap JEntry array and values: values in the
>> begining of type will be catched by pg_lzcompress. But we will need to
>> know offset of JEntry array, so header will grow up till 8 bytes
>> (actually, it will be a varlena header!)
>>
>
> May be I wasn't clear:jsonb type will start from string collection instead
> of JEntry array, JEntry array will be placed at the end of object/array.
> so, pg_lzcompress will find repeatable 4-byte pieces in first 1024 bytes of
> jsonb.

Another idea I have is that store offset in each JEntry is not necessary to
have benefit of binary search. Namely what if we store offsets in each 8th
JEntry and length in others? The speed of binary search will be about the
same: overhead is only calculation offsets in the 8-entries chunk. But
lengths will probably repeat.

------
With best regards,
Alexander Korotkov.

On Fri, Aug 8, 2014 at 7:35 PM, Andrew Dunstan <andrew(at)dunslane(dot)net> wrote:
>> I took a quick look and saw that this wouldn't be that easy to get around.
>> As I'd suspected upthread, there are places that do random access into a
>> JEntry array, such as the binary search in findJsonbValueFromContainer().
>> If we have to add up all the preceding lengths to locate the corresponding
>> value part, we lose the performance advantages of binary search. AFAICS
>> that's applied directly to the on-disk representation. I'd thought
>> perhaps there was always a transformation step to build a pointer list,
>> but nope.
>
> It would be interesting to know what the performance hit would be if we
> calculated the offsets/pointers on the fly, especially if we could cache it
> somehow. The main benefit of binary search is in saving on comparisons,
> especially of strings, ISTM, and that could still be available - this would
> just be a bit of extra arithmetic.

I don't think binary search is the main problem here. Objects are
usually reasonably sized, while arrays are more likely to be huge. To
make matters worse, jsonb -> int goes from O(1) to O(n).

Regards,
Ants Aasma
--
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt
Web: http://www.postgresql-support.de

On 08/08/2014 06:17 AM, Tom Lane wrote:
> I looked into the issue reported in bug #11109. The problem appears to be
> that jsonb's on-disk format is designed in such a way that the leading
> portion of any JSON array or object will be fairly incompressible, because
> it consists mostly of a strictly-increasing series of integer offsets.
How hard and how expensive would it be to teach pg_lzcompress to
apply a delta filter on suitable data ?

So that instead of integers their deltas will be fed to the "real"
compressor

--
Hannu Krosing
PostgreSQL Consultant
Performance, Scalability and High Availability
2ndQuadrant Nordic OÜ

On Fri, Aug 8, 2014 at 12:41 PM, Ants Aasma <ants(at)cybertec(dot)at> wrote:
> I don't think binary search is the main problem here. Objects are
> usually reasonably sized, while arrays are more likely to be huge. To
> make matters worse, jsonb -> int goes from O(1) to O(n).

I don't think it's true that arrays are more likely to be huge. That
regression would be bad, but jsonb -> int is not the most compelling
operator by far. The indexable operators (in particular, @>) don't
support subscripting arrays like that, and with good reason.

--
Peter Geoghegan

On Fri, Aug 8, 2014 at 12:06 PM, Josh Berkus <josh(at)agliodbs(dot)com> wrote:
> One we ship 9.4, many users are going to load 100's of GB into JSONB
> fields. Even if we fix the compressability issue in 9.5, those users
> won't be able to fix the compression without rewriting all their data,
> which could be prohibitive. And we'll be in a position where we have
> to support the 9.4 JSONB format/compression technique for years so that
> users aren't blocked from upgrading.

FWIW, if we take the delicious JSON data as representative, a table
storing that data as jsonb is 1374 MB in size. Whereas an equivalent
table with the data typed using the original json datatype (but with
white space differences more or less ignored, because it was created
using a jsonb -> json cast), the same data is 1352 MB.

Larry's complaint is valid; this is a real problem, and I'd like to
fix it before 9.4 is out. However, let us not lose sight of the fact
that JSON data is usually a poor target for TOAST compression. With
idiomatic usage, redundancy is very much more likely to appear across
rows, and not within individual Datums. Frankly, we aren't doing a
very good job there, and doing better requires an alternative
strategy.

--
Peter Geoghegan

I was not complaining; I think JSONB is awesome.

But I am one of those people who would like to put 100's of GB (or more)
JSON files into Postgres and I am concerned about file size and possible
future changes to the format.

On Fri, Aug 8, 2014 at 7:10 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:

> On Fri, Aug 8, 2014 at 12:06 PM, Josh Berkus <josh(at)agliodbs(dot)com> wrote:
> > One we ship 9.4, many users are going to load 100's of GB into JSONB
> > fields. Even if we fix the compressability issue in 9.5, those users
> > won't be able to fix the compression without rewriting all their data,
> > which could be prohibitive. And we'll be in a position where we have
> > to support the 9.4 JSONB format/compression technique for years so that
> > users aren't blocked from upgrading.
>
> FWIW, if we take the delicious JSON data as representative, a table
> storing that data as jsonb is 1374 MB in size. Whereas an equivalent
> table with the data typed using the original json datatype (but with
> white space differences more or less ignored, because it was created
> using a jsonb -> json cast), the same data is 1352 MB.
>
> Larry's complaint is valid; this is a real problem, and I'd like to
> fix it before 9.4 is out. However, let us not lose sight of the fact
> that JSON data is usually a poor target for TOAST compression. With
> idiomatic usage, redundancy is very much more likely to appear across
> rows, and not within individual Datums. Frankly, we aren't doing a
> very good job there, and doing better requires an alternative
> strategy.
>
> --
> Peter Geoghegan
>

* Tom Lane (tgl(at)sss(dot)pgh(dot)pa(dot)us) wrote:
> Stephen Frost <sfrost(at)snowman(dot)net> writes:
> > * Tom Lane (tgl(at)sss(dot)pgh(dot)pa(dot)us) wrote:
> >> I looked into the issue reported in bug #11109. The problem appears to be
> >> that jsonb's on-disk format is designed in such a way that the leading
> >> portion of any JSON array or object will be fairly incompressible, because
> >> it consists mostly of a strictly-increasing series of integer offsets.
> >> This interacts poorly with the code in pglz_compress() that gives up if
> >> it's found nothing compressible in the first first_success_by bytes of a
> >> value-to-be-compressed. (first_success_by is 1024 in the default set of
> >> compression parameters.)
>
> > I haven't looked at this in any detail, so take this with a grain of
> > salt, but what about teaching pglz_compress about using an offset
> > farther into the data, if the incoming data is quite a bit larger than
> > 1k? This is just a test to see if it's worthwhile to keep going, no?
>
> Well, the point of the existing approach is that it's a *nearly free*
> test to see if it's worthwhile to keep going; there's just one if-test
> added in the outer loop of the compression code. (cf commit ad434473ebd2,
> which added that along with some other changes.) AFAICS, what we'd have
> to do to do it as you suggest would to execute compression on some subset
> of the data and then throw away that work entirely. I do not find that
> attractive, especially when for most datatypes there's no particular
> reason to look at one subset instead of another.

Ah, I see- we were using the first block as it means we can reuse the
work done on it if we decide to continue with the compression. Makes
sense. We could possibly arrange to have the amount attempted depend on
the data type, but you point out that we can't do that without teaching
lower components about types, which is less than ideal.

What about considering how large the object is when we are analyzing if
it compresses well overall? That is- for a larger object, make a larger
effort to compress it. There's clearly a pessimistic case which could
arise from that, but it may be better than the current situation.
There's a clear risk that such an algorithm may well be very type
specific, meaning that we make things worse for some types (eg: bytea's
which end up never compressing well we'd likely spend more CPU time
trying than we do today).

> 1. The real problem here is that jsonb is emitting quite a bit of
> fundamentally-nonrepetitive data, even when the user-visible input is very
> repetitive. That's a compression-unfriendly transformation by anyone's
> measure. Assuming that some future replacement for pg_lzcompress() will
> nonetheless be able to compress the data strikes me as mostly wishful
> thinking. Besides, we'd more than likely have a similar early-exit rule
> in any substitute implementation, so that we'd still be at risk even if
> it usually worked.

I agree that jsonb ends up being nonrepetitive in part, which is why
I've been trying to push the discussion in the direction of making it
more likely for the highly-compressible data to be considered rather
than the start of the jsonb object. I don't care for our compression
algorithm having to be catered to in this regard in general though as
the exact same problem could, and likely does, exist in some real life
bytea-using PG implementations.

I disagree that another algorithm wouldn't be able to manage better on
this data than pglz. pglz, from my experience, is notoriously bad a
certain data sets which other algorithms are not as poorly impacted by.

> 2. Are we going to ship 9.4 without fixing this? I definitely don't see
> replacing pg_lzcompress as being on the agenda for 9.4, whereas changing
> jsonb is still within the bounds of reason.

I'd really hate to ship 9.4 without a fix for this, but I have a similar
hard time with shipping 9.4 without the binary search component..

> Considering all the hype that's built up around jsonb, shipping a design
> with a fundamental performance handicap doesn't seem like a good plan
> to me. We could perhaps band-aid around it by using different compression
> parameters for jsonb, although that would require some painful API changes
> since toast_compress_datum() doesn't know what datatype it's operating on.

I don't like the idea of shipping with this handicap either.

Perhaps another options would be a new storage type which basically says
"just compress it, no matter what"? We'd be able to make that the
default for jsonb columns too, no? Again- I'll admit this is shooting
from the hip, but I wanted to get these thoughts out and I won't have
much more time tonight.

Thanks!

Stephen

* Bruce Momjian (bruce(at)momjian(dot)us) wrote:
> On Fri, Aug 8, 2014 at 11:02:26AM -0400, Tom Lane wrote:
> > 2. Are we going to ship 9.4 without fixing this? I definitely don't see
> > replacing pg_lzcompress as being on the agenda for 9.4, whereas changing
> > jsonb is still within the bounds of reason.
>
> FYI, pg_upgrade could be taught to refuse to upgrade from earlier 9.4
> betas and report the problem JSONB columns.

That is *not* a good solution..

Thanks,

Stephen

* Josh Berkus (josh(at)agliodbs(dot)com) wrote:
> On 08/08/2014 08:02 AM, Tom Lane wrote:
> > 2. Are we going to ship 9.4 without fixing this? I definitely don't see
> > replacing pg_lzcompress as being on the agenda for 9.4, whereas changing
> > jsonb is still within the bounds of reason.
> >
> > Considering all the hype that's built up around jsonb, shipping a design
> > with a fundamental performance handicap doesn't seem like a good plan
> > to me. We could perhaps band-aid around it by using different compression
> > parameters for jsonb, although that would require some painful API changes
> > since toast_compress_datum() doesn't know what datatype it's operating on.
>
> I would rather ship late than ship a noncompressable JSONB.
>
> One we ship 9.4, many users are going to load 100's of GB into JSONB
> fields. Even if we fix the compressability issue in 9.5, those users
> won't be able to fix the compression without rewriting all their data,
> which could be prohibitive. And we'll be in a position where we have
> to support the 9.4 JSONB format/compression technique for years so that
> users aren't blocked from upgrading.

Would you accept removing the binary-search capability from jsonb just
to make it compressable? I certainly wouldn't. I'd hate to ship late
also, but I'd be willing to support that if we can find a good solution
to keep both compressability and binary-search (and provided it doesn't
delay us many months..).

Thanks,

Stephen

Stephen Frost <sfrost(at)snowman(dot)net> writes:
> What about considering how large the object is when we are analyzing if
> it compresses well overall?

Hmm, yeah, that's a possibility: we could redefine the limit at which
we bail out in terms of a fraction of the object size instead of a fixed
limit. However, that risks expending a large amount of work before we
bail, if we have a very large incompressible object --- which is not
exactly an unlikely case. Consider for example JPEG images stored as
bytea, which I believe I've heard of people doing. Another issue is
that it's not real clear that that fixes the problem for any fractional
size we'd want to use. In Larry's example of a jsonb value that fails
to compress, the header size is 940 bytes out of about 12K, so we'd be
needing to trial-compress about 10% of the object before we reach
compressible data --- and I doubt his example is worst-case.

>> 1. The real problem here is that jsonb is emitting quite a bit of
>> fundamentally-nonrepetitive data, even when the user-visible input is very
>> repetitive. That's a compression-unfriendly transformation by anyone's
>> measure.

> I disagree that another algorithm wouldn't be able to manage better on
> this data than pglz. pglz, from my experience, is notoriously bad a
> certain data sets which other algorithms are not as poorly impacted by.

Well, I used to be considered a compression expert, and I'm going to
disagree with you here. It's surely possible that other algorithms would
be able to get some traction where pglz fails to get any, but that doesn't
mean that presenting them with hard-to-compress data in the first place is
a good design decision. There is no scenario in which data like this is
going to be friendly to a general-purpose compression algorithm. It'd
be necessary to have explicit knowledge that the data consists of an
increasing series of four-byte integers to be able to do much with it.
And then such an assumption would break down once you got past the
header ...

> Perhaps another options would be a new storage type which basically says
> "just compress it, no matter what"? We'd be able to make that the
> default for jsonb columns too, no?

Meh. We could do that, but it would still require adding arguments to
toast_compress_datum() that aren't there now. In any case, this is a
band-aid solution; and as Josh notes, once we ship 9.4 we are going to
be stuck with jsonb's on-disk representation pretty much forever.

regards, tom lane

On 08/08/2014 08:45 PM, Tom Lane wrote:
>> Perhaps another options would be a new storage type which basically says
>> "just compress it, no matter what"? We'd be able to make that the
>> default for jsonb columns too, no?
> Meh. We could do that, but it would still require adding arguments to
> toast_compress_datum() that aren't there now. In any case, this is a
> band-aid solution; and as Josh notes, once we ship 9.4 we are going to
> be stuck with jsonb's on-disk representation pretty much forever.
>

Yeah, and almost any other solution is likely to mean non-jsonb users
potentially paying a penalty for fixing this for jsonb. So if we can
adjust the jsonb layout to fix this problem I think we should do so.

cheers

andrew

* Tom Lane (tgl(at)sss(dot)pgh(dot)pa(dot)us) wrote:
> Stephen Frost <sfrost(at)snowman(dot)net> writes:
> > What about considering how large the object is when we are analyzing if
> > it compresses well overall?
>
> Hmm, yeah, that's a possibility: we could redefine the limit at which
> we bail out in terms of a fraction of the object size instead of a fixed
> limit. However, that risks expending a large amount of work before we
> bail, if we have a very large incompressible object --- which is not
> exactly an unlikely case. Consider for example JPEG images stored as
> bytea, which I believe I've heard of people doing. Another issue is
> that it's not real clear that that fixes the problem for any fractional
> size we'd want to use. In Larry's example of a jsonb value that fails
> to compress, the header size is 940 bytes out of about 12K, so we'd be
> needing to trial-compress about 10% of the object before we reach
> compressible data --- and I doubt his example is worst-case.

Agreed- I tried to allude to that in my prior mail, there's clearly a
concern that we'd make things worse in certain situations. Then again,
at least for that case, we could recommend changing the storage type to
EXTERNAL.

> >> 1. The real problem here is that jsonb is emitting quite a bit of
> >> fundamentally-nonrepetitive data, even when the user-visible input is very
> >> repetitive. That's a compression-unfriendly transformation by anyone's
> >> measure.
>
> > I disagree that another algorithm wouldn't be able to manage better on
> > this data than pglz. pglz, from my experience, is notoriously bad a
> > certain data sets which other algorithms are not as poorly impacted by.
>
> Well, I used to be considered a compression expert, and I'm going to
> disagree with you here. It's surely possible that other algorithms would
> be able to get some traction where pglz fails to get any, but that doesn't
> mean that presenting them with hard-to-compress data in the first place is
> a good design decision. There is no scenario in which data like this is
> going to be friendly to a general-purpose compression algorithm. It'd
> be necessary to have explicit knowledge that the data consists of an
> increasing series of four-byte integers to be able to do much with it.
> And then such an assumption would break down once you got past the
> header ...

I've wondered previously as to if we, perhaps, missed the boat pretty
badly by not providing an explicitly versioned per-type compression
capability, such that we wouldn't be stuck with one compression
algorith for all types, and would be able to version compression types
in a way that would allow us to change them over time, provided the
newer code always understands how to decode X-4 (or whatever) versions
back.

I do agree that it'd be great to represent every type in a highly
compressable way for the sake of the compression algorithm, but
I've not seen any good suggestions for how to make that happen and I've
got a hard time seeing how we could completely change the jsonb storage
format, retain the capabilities it has today, make it highly
compressible, and get 9.4 out this calendar year.

I expect we could trivially add padding into the jsonb header to make it
compress better, for the sake of this particular check, but then we're
going to always be compression jsonb, even when the user data isn't
actually terribly good for compression, spending a good bit of CPU time
while we're at it.

> > Perhaps another options would be a new storage type which basically says
> > "just compress it, no matter what"? We'd be able to make that the
> > default for jsonb columns too, no?
>
> Meh. We could do that, but it would still require adding arguments to
> toast_compress_datum() that aren't there now. In any case, this is a
> band-aid solution; and as Josh notes, once we ship 9.4 we are going to
> be stuck with jsonb's on-disk representation pretty much forever.

I agree that we need to avoid changing jsonb's on-disk representation.
Have I missed where a good suggestion has been made about how to do that
which preserves the binary-search capabilities and doesn't make the code
much more difficult? Trying to move the header to the end just for the
sake of this doesn't strike me as a good solution as it'll make things
quite a bit more complicated. Is there a way we could interleave the
likely-compressible user data in with the header instead? I've not
looked, but it seems like that's the only reasonable approach to address
this issue in this manner. If that's simply done, then great, but it
strikes me as unlikely to be..

I'll just throw out a bit of a counter-point to all this also though- we
don't try to focus on making our on-disk representation of data,
generally, very compressible even though there are filesystems, such as
ZFS, which might benefit from certain rearrangements of our on-disk
formats (no, I don't have any specific recommendations in this vein, but
I certainly don't see anyone else asking after it or asking for us to be
concerned about it). Compression is great and I'd hate to see us have a
format that will just work with it even though it might be beneficial in
many cases, but I feel the fault here is with the compression algorithm
and the decisions made as part of that operation and not really with
this particular data structure.

Thanks,

Stephen

Stephen Frost <sfrost(at)snowman(dot)net> writes:
> I agree that we need to avoid changing jsonb's on-disk representation.

... post-release, I assume you mean.

> Have I missed where a good suggestion has been made about how to do that
> which preserves the binary-search capabilities and doesn't make the code
> much more difficult?

We don't have one yet, but we've only been thinking about this for a few
hours.

> Trying to move the header to the end just for the
> sake of this doesn't strike me as a good solution as it'll make things
> quite a bit more complicated. Is there a way we could interleave the
> likely-compressible user data in with the header instead?

Yeah, I was wondering about that too, but I don't immediately see how to
do it without some sort of preprocessing step when we read the object
(which'd be morally equivalent to converting a series of lengths into a
pointer array). Binary search isn't going to work if the items it's
searching in aren't all the same size.

Having said that, I am not sure that a preprocessing step is a
deal-breaker. It'd be O(N), but with a pretty darn small constant factor,
and for plausible sizes of objects I think the binary search might still
dominate. Worth investigation perhaps.

regards, tom lane

* Tom Lane (tgl(at)sss(dot)pgh(dot)pa(dot)us) wrote:
> Stephen Frost <sfrost(at)snowman(dot)net> writes:
> > I agree that we need to avoid changing jsonb's on-disk representation.
>
> ... post-release, I assume you mean.

Yes.

> > Have I missed where a good suggestion has been made about how to do that
> > which preserves the binary-search capabilities and doesn't make the code
> > much more difficult?
>
> We don't have one yet, but we've only been thinking about this for a few
> hours.

Fair enough.

> > Trying to move the header to the end just for the
> > sake of this doesn't strike me as a good solution as it'll make things
> > quite a bit more complicated. Is there a way we could interleave the
> > likely-compressible user data in with the header instead?
>
> Yeah, I was wondering about that too, but I don't immediately see how to
> do it without some sort of preprocessing step when we read the object
> (which'd be morally equivalent to converting a series of lengths into a
> pointer array). Binary search isn't going to work if the items it's
> searching in aren't all the same size.
>
> Having said that, I am not sure that a preprocessing step is a
> deal-breaker. It'd be O(N), but with a pretty darn small constant factor,
> and for plausible sizes of objects I think the binary search might still
> dominate. Worth investigation perhaps.

For my part, I'm less concerned about a preprocessing step which happens
when we store the data and more concerned about ensuring that we're able
to extract data quickly. Perhaps that's simply because I'm used to
writes being more expensive than reads, but I'm not alone in that
regard either. I doubt I'll have time in the next couple of weeks to
look into this and if we're going to want this change for 9.4, we really
need someone working on it sooner than later. (to the crowd)- do we
have any takers for this investigation?

Thanks,

Stephen

On Sat, Aug 9, 2014 at 6:15 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
> Stephen Frost <sfrost(at)snowman(dot)net> writes:
> > What about considering how large the object is when we are analyzing if
> > it compresses well overall?
>
> Hmm, yeah, that's a possibility: we could redefine the limit at which
> we bail out in terms of a fraction of the object size instead of a fixed
> limit. However, that risks expending a large amount of work before we
> bail, if we have a very large incompressible object --- which is not
> exactly an unlikely case. Consider for example JPEG images stored as
> bytea, which I believe I've heard of people doing. Another issue is
> that it's not real clear that that fixes the problem for any fractional
> size we'd want to use. In Larry's example of a jsonb value that fails
> to compress, the header size is 940 bytes out of about 12K, so we'd be
> needing to trial-compress about 10% of the object before we reach
> compressible data --- and I doubt his example is worst-case.
>
> >> 1. The real problem here is that jsonb is emitting quite a bit of
> >> fundamentally-nonrepetitive data, even when the user-visible input is
very
> >> repetitive. That's a compression-unfriendly transformation by anyone's
> >> measure.
>
> > I disagree that another algorithm wouldn't be able to manage better on
> > this data than pglz. pglz, from my experience, is notoriously bad a
> > certain data sets which other algorithms are not as poorly impacted by.
>
> Well, I used to be considered a compression expert, and I'm going to
> disagree with you here. It's surely possible that other algorithms would
> be able to get some traction where pglz fails to get any,

During my previous work in this area, I had seen that some algorithms
use skipping logic which can be useful for incompressible data followed
by compressible data or in general as well. One of the technique could
be If we don't find any match for first 4 bytes, then skip 4 bytes
and if we don't find match again for next 8 bytes, then skip 8
bytes and keep on doing the same until we find first match in which
case it would go back to beginning of data. Now here we could follow
this logic until we actually compare total of first_success_by bytes.
There can be caveats in this particular scheme of skipping but I
just wanted to mention in general about the skipping idea to reduce
the number of situations where we will bail out even though there is
lot of compressible data.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Fri, Aug 8, 2014 at 08:25:04PM -0400, Stephen Frost wrote:
> * Bruce Momjian (bruce(at)momjian(dot)us) wrote:
> > On Fri, Aug 8, 2014 at 11:02:26AM -0400, Tom Lane wrote:
> > > 2. Are we going to ship 9.4 without fixing this? I definitely don't see
> > > replacing pg_lzcompress as being on the agenda for 9.4, whereas changing
> > > jsonb is still within the bounds of reason.
> >
> > FYI, pg_upgrade could be taught to refuse to upgrade from earlier 9.4
> > betas and report the problem JSONB columns.
>
> That is *not* a good solution..

If you change the JSONB binary format, and we can't read the old format,
that is the only option.

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ Everyone has their own god. +

akapila wrote
> On Sat, Aug 9, 2014 at 6:15 AM, Tom Lane &lt;

> tgl(at)(dot)pa

> &gt; wrote:
>>
>> Stephen Frost &lt;

> sfrost@

> &gt; writes:
>> > What about considering how large the object is when we are analyzing if
>> > it compresses well overall?
>>
>> Hmm, yeah, that's a possibility: we could redefine the limit at which
>> we bail out in terms of a fraction of the object size instead of a fixed
>> limit. However, that risks expending a large amount of work before we
>> bail, if we have a very large incompressible object --- which is not
>> exactly an unlikely case. Consider for example JPEG images stored as
>> bytea, which I believe I've heard of people doing. Another issue is
>> that it's not real clear that that fixes the problem for any fractional
>> size we'd want to use. In Larry's example of a jsonb value that fails
>> to compress, the header size is 940 bytes out of about 12K, so we'd be
>> needing to trial-compress about 10% of the object before we reach
>> compressible data --- and I doubt his example is worst-case.
>>
>> >> 1. The real problem here is that jsonb is emitting quite a bit of
>> >> fundamentally-nonrepetitive data, even when the user-visible input is
> very
>> >> repetitive. That's a compression-unfriendly transformation by
>> anyone's
>> >> measure.
>>
>> > I disagree that another algorithm wouldn't be able to manage better on
>> > this data than pglz. pglz, from my experience, is notoriously bad a
>> > certain data sets which other algorithms are not as poorly impacted by.
>>
>> Well, I used to be considered a compression expert, and I'm going to
>> disagree with you here. It's surely possible that other algorithms would
>> be able to get some traction where pglz fails to get any,
>
> During my previous work in this area, I had seen that some algorithms
> use skipping logic which can be useful for incompressible data followed
> by compressible data or in general as well.

Random thought from the sideline...

This particular data type has the novel (within PostgreSQL) design of both a
(feature oriented - and sizeable) header and a payload. Is there some way
to add that model into the storage system so that, at a higher level,
separate attempts are made to compress each section and then the compressed
(or not) results and written out adjacently and with a small header
indicating the length of the stored header and other meta data like whether
each part is compressed and even the type that data represents? For reading
back into memory the header-payload generic type is populated and then the
header and payload decompressed - as needed - then the two parts are fed
into the appropriate type constructor that understands and accepts the two
pieces.

Just hoping to spark an idea here - I don't know enough about the internals
to even guess how close I am to something feasible.

David J.

--
View this message in context: http://postgresql.1045698.n5.nabble.com/jsonb-format-is-pessimal-for-toast-compression-tp5814162p5814299.html
Sent from the PostgreSQL - hackers mailing list archive at Nabble.com.

Bruce,

* Bruce Momjian (bruce(at)momjian(dot)us) wrote:
> On Fri, Aug 8, 2014 at 08:25:04PM -0400, Stephen Frost wrote:
> > * Bruce Momjian (bruce(at)momjian(dot)us) wrote:
> > > FYI, pg_upgrade could be taught to refuse to upgrade from earlier 9.4
> > > betas and report the problem JSONB columns.
> >
> > That is *not* a good solution..
>
> If you change the JSONB binary format, and we can't read the old format,
> that is the only option.

Apologies- I had thought you were suggesting this for a 9.4 -> 9.5
conversion, not for just 9.4beta to 9.4. Adding that to pg_upgrade to
address folks upgrading from betas would certainly be fine.

Thanks,

Stephen

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Stephen Frost <sfrost(at)snowman(dot)net> writes:

>> Trying to move the header to the end just for the sake of this
>> doesn't strike me as a good solution as it'll make things quite
>> a bit more complicated.

Why is that?  How much harder would it be to add a single offset
field to the front to point to the part we're shifting to the end?
It is not all that unusual to put a directory at the end, like in
the .zip file format.

>> Is there a way we could interleave the likely-compressible user
>> data in with the header instead?
>
> Yeah, I was wondering about that too, but I don't immediately see
> how to do it without some sort of preprocessing step when we read
> the object (which'd be morally equivalent to converting a series
> of lengths into a pointer array).

That sounds far more complex and fragile than just moving the
indexes to the end.

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Kevin Grittner <kgrittn(at)ymail(dot)com> writes:
>> Stephen Frost <sfrost(at)snowman(dot)net> writes:
>>> Trying to move the header to the end just for the sake of this
>>> doesn't strike me as a good solution as it'll make things quite
>>> a bit more complicated.

> Why is that? How much harder would it be to add a single offset
> field to the front to point to the part we're shifting to the end?
> It is not all that unusual to put a directory at the end, like in
> the .zip file format.

Yeah, I was wondering that too. Arguably, directory-at-the-end would
be easier to work with for on-the-fly creation, not that we do any
such thing at the moment. I think the main thing that's bugging Stephen
is that doing that just to make pglz_compress happy seems like a kluge
(and I have to agree).

Here's a possibly more concrete thing to think about: we may very well
someday want to support JSONB object field or array element extraction
without reading all blocks of a large toasted JSONB value, if the value is
stored external without compression. We already went to the trouble of
creating analogous logic for substring extraction from a long uncompressed
text or bytea value, so I think this is a plausible future desire. With
the current format you could imagine grabbing the first TOAST chunk, and
then if you see the header is longer than that you can grab the remainder
of the header without any wasted I/O, and for the array-subscripting case
you'd now have enough info to fetch the element value from the body of
the JSONB without any wasted I/O. With directory-at-the-end you'd
have to read the first chunk just to get the directory pointer, and this
would most likely not give you any of the directory proper; but at least
you'd know exactly how big the directory is before you go to read it in.
The former case is probably slightly better. However, if you're doing an
object key lookup not an array element fetch, neither of these formats are
really friendly at all, because each binary-search probe probably requires
bringing in one or two toast chunks from the body of the JSONB value so
you can look at the key text. I'm not sure if there's a way to redesign
the format to make that less painful/expensive --- but certainly, having
the key texts scattered through the JSONB value doesn't seem like a great
thing from this standpoint.

regards, tom lane

On Sat, Aug 9, 2014 at 3:51 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Kevin Grittner <kgrittn(at)ymail(dot)com> writes:
>>> Stephen Frost <sfrost(at)snowman(dot)net> writes:
>>>> Trying to move the header to the end just for the sake of this
>>>> doesn't strike me as a good solution as it'll make things quite
>>>> a bit more complicated.
>
>> Why is that? How much harder would it be to add a single offset
>> field to the front to point to the part we're shifting to the end?
>> It is not all that unusual to put a directory at the end, like in
>> the .zip file format.
>
> Yeah, I was wondering that too. Arguably, directory-at-the-end would
> be easier to work with for on-the-fly creation, not that we do any
> such thing at the moment. I think the main thing that's bugging Stephen
> is that doing that just to make pglz_compress happy seems like a kluge
> (and I have to agree).
>
> Here's a possibly more concrete thing to think about: we may very well
> someday want to support JSONB object field or array element extraction
> without reading all blocks of a large toasted JSONB value, if the value is
> stored external without compression. We already went to the trouble of
> creating analogous logic for substring extraction from a long uncompressed
> text or bytea value, so I think this is a plausible future desire. With
> the current format you could imagine grabbing the first TOAST chunk, and
> then if you see the header is longer than that you can grab the remainder
> of the header without any wasted I/O, and for the array-subscripting case
> you'd now have enough info to fetch the element value from the body of
> the JSONB without any wasted I/O. With directory-at-the-end you'd
> have to read the first chunk just to get the directory pointer, and this
> would most likely not give you any of the directory proper; but at least
> you'd know exactly how big the directory is before you go to read it in.
> The former case is probably slightly better. However, if you're doing an
> object key lookup not an array element fetch, neither of these formats are
> really friendly at all, because each binary-search probe probably requires
> bringing in one or two toast chunks from the body of the JSONB value so
> you can look at the key text. I'm not sure if there's a way to redesign
> the format to make that less painful/expensive --- but certainly, having
> the key texts scattered through the JSONB value doesn't seem like a great
> thing from this standpoint.

I think that's a good point.

On the general topic, I don't think it's reasonable to imagine that
we're going to come up with a single heuristic that works well for
every kind of input data. What pglz is doing - assuming that if the
beginning of the data is incompressible then the rest probably is too
- is fundamentally reasonable, nonwithstanding the fact that it
doesn't happen to work out well for JSONB. We might be able to tinker
with that general strategy in some way that seems to fix this case and
doesn't appear to break others, but there's some risk in that, and
there's no obvious reason in my mind why PGLZ should be require to fly
blind. So I think it would be a better idea to arrange some method by
which JSONB (and perhaps other data types) can provide compression
hints to pglz.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> ... I think it would be a better idea to arrange some method by
> which JSONB (and perhaps other data types) can provide compression
> hints to pglz.

I agree with that as a long-term goal, but not sure if it's sane to
push into 9.4.

What we could conceivably do now is (a) add a datatype OID argument to
toast_compress_datum, and (b) hard-wire the selection of a different
compression-parameters struct if it's JSONBOID. The actual fix would
then be to increase the first_success_by field of this alternate struct.

I had been worrying about API-instability risks associated with (a),
but on reflection it seems unlikely that any third-party code calls
toast_compress_datum directly, and anyway it's not something we'd
be back-patching to before 9.4.

The main objection to (b) is that it wouldn't help for domains over jsonb
(and no, I don't want to insert a getBaseType call there to fix that).

A longer-term solution would be to make this some sort of type property
that domains could inherit, like typstorage is already. (Somebody
suggested dealing with this by adding more typstorage values, but
I don't find that attractive; typstorage is known in too many places.)
We'd need some thought about exactly what we want to expose, since
the specific knobs that pglz_compress has today aren't necessarily
good for the long term.

This is all kinda ugly really, but since I'm not hearing brilliant
ideas for redesigning jsonb's storage format, maybe this is the
best we can do for now.

regards, tom lane

On Mon, Aug 11, 2014 at 12:07 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> I think that's a good point.

I think that there may be something to be said for the current layout.
Having adjacent keys and values could take better advantage of CPU
cache characteristics. I've heard of approaches to improving B-Tree
locality that forced keys and values to be adjacent on individual
B-Tree pages [1], for example. I've heard of this more than once. And
FWIW, I believe based on earlier research of user requirements in this
area that very large jsonb datums are not considered all that
compelling. Document database systems have considerable limitations
here.

> On the general topic, I don't think it's reasonable to imagine that
> we're going to come up with a single heuristic that works well for
> every kind of input data. What pglz is doing - assuming that if the
> beginning of the data is incompressible then the rest probably is too
> - is fundamentally reasonable, nonwithstanding the fact that it
> doesn't happen to work out well for JSONB. We might be able to tinker
> with that general strategy in some way that seems to fix this case and
> doesn't appear to break others, but there's some risk in that, and
> there's no obvious reason in my mind why PGLZ should be require to fly
> blind. So I think it would be a better idea to arrange some method by
> which JSONB (and perhaps other data types) can provide compression
> hints to pglz.

If there is to be any effort to make jsonb a more effective target for
compression, I imagine that that would have to target redundancy
between JSON documents. With idiomatic usage, we can expect plenty of
it.

[1] http://www.vldb.org/conf/1999/P7.pdf , "We also forced each key
and child pointer to be adjacent to each other physically"
--
Peter Geoghegan

* Tom Lane (tgl(at)sss(dot)pgh(dot)pa(dot)us) wrote:
> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> > ... I think it would be a better idea to arrange some method by
> > which JSONB (and perhaps other data types) can provide compression
> > hints to pglz.
>
> I agree with that as a long-term goal, but not sure if it's sane to
> push into 9.4.

Agreed.

> What we could conceivably do now is (a) add a datatype OID argument to
> toast_compress_datum, and (b) hard-wire the selection of a different
> compression-parameters struct if it's JSONBOID. The actual fix would
> then be to increase the first_success_by field of this alternate struct.

Isn't the offset-to-compressable-data variable though, depending on the
number of keys, etc? Would we be increasing first_success_by based off
of some function which inspects the object?

> I had been worrying about API-instability risks associated with (a),
> but on reflection it seems unlikely that any third-party code calls
> toast_compress_datum directly, and anyway it's not something we'd
> be back-patching to before 9.4.

Agreed.

> The main objection to (b) is that it wouldn't help for domains over jsonb
> (and no, I don't want to insert a getBaseType call there to fix that).

While not ideal, that seems like an acceptable compromise for 9.4 to me.

> A longer-term solution would be to make this some sort of type property
> that domains could inherit, like typstorage is already. (Somebody
> suggested dealing with this by adding more typstorage values, but
> I don't find that attractive; typstorage is known in too many places.)

Think that was me and having it be something which domains can inherit
makes sense. Would be able to use this approach to introduce type
(and domains inheirited from that type) specific compression algorithms,
perhaps? Or even get to a point where we could have a chunk-based
compression scheme for certain types of objects (such as JSONB) where we
keep track of which keys exist at which points in the compressed object,
allowing us to skip to the specific chunk which contains the requested
key, similar to what we do with uncompressed data?

> We'd need some thought about exactly what we want to expose, since
> the specific knobs that pglz_compress has today aren't necessarily
> good for the long term.

Agreed.

> This is all kinda ugly really, but since I'm not hearing brilliant
> ideas for redesigning jsonb's storage format, maybe this is the
> best we can do for now.

This would certainly be an improvement over what's going on now, and I
love the idea of possibly being able to expand this in the future to do
more. What I'd hate to see is having all of this and only ever using it
to say "skip ahead another 1k for JSONB".

Thanks,

Stephen

Stephen Frost <sfrost(at)snowman(dot)net> writes:
> * Tom Lane (tgl(at)sss(dot)pgh(dot)pa(dot)us) wrote:
>> What we could conceivably do now is (a) add a datatype OID argument to
>> toast_compress_datum, and (b) hard-wire the selection of a different
>> compression-parameters struct if it's JSONBOID. The actual fix would
>> then be to increase the first_success_by field of this alternate struct.

> Isn't the offset-to-compressable-data variable though, depending on the
> number of keys, etc? Would we be increasing first_success_by based off
> of some function which inspects the object?

Given that this is a short-term hack, I'd be satisfied with setting it
to INT_MAX.

If we got more ambitious, we could consider improving the cutoff logic
so that it gives up at "x% of the object or n bytes, whichever comes
first"; but I'd want to see some hard evidence that that was useful
before adding any more cycles to pglz_compress.

regards, tom lane

* Peter Geoghegan (pg(at)heroku(dot)com) wrote:
> If there is to be any effort to make jsonb a more effective target for
> compression, I imagine that that would have to target redundancy
> between JSON documents. With idiomatic usage, we can expect plenty of
> it.

While I certainly agree, that's a rather different animal to address and
doesn't hold a lot of relevance to the current problem. Or, to put it
another way, I don't think anyone is going to be surprised that two rows
containing the same data (even if they're inserted in the same
transaction and have the same visibility information) are compressed
together in some fashion.

We've got a clear example of someone, quite reasonably, expecting their
JSONB object to be compressed using the normal TOAST mechanism, and
we're failing to do that in cases where it's actually a win to do so.
That's the focus of this discussion and what needs to be addressed
before 9.4 goes out.

Thanks,

Stephen

On Mon, Aug 11, 2014 at 1:01 PM, Stephen Frost <sfrost(at)snowman(dot)net> wrote:
> We've got a clear example of someone, quite reasonably, expecting their
> JSONB object to be compressed using the normal TOAST mechanism, and
> we're failing to do that in cases where it's actually a win to do so.
> That's the focus of this discussion and what needs to be addressed
> before 9.4 goes out.

Sure. I'm not trying to minimize that. We should fix it, certainly.
However, it does bear considering that JSON data, with each document
stored in a row is not an effective target for TOAST compression in
general, even as text.

--
Peter Geoghegan

On Fri, Aug 8, 2014 at 10:50 PM, Hannu Krosing <hannu(at)2ndquadrant(dot)com> wrote:
> How hard and how expensive would it be to teach pg_lzcompress to
> apply a delta filter on suitable data ?
>
> So that instead of integers their deltas will be fed to the "real"
> compressor

Has anyone given this more thought? I know this might not be 9.4
material, but to me it sounds like the most promising approach, if
it's workable. This isn't a made up thing, the 7z and LZMA formats
also have an optional delta filter.

Of course with JSONB the problem is figuring out which parts to apply
the delta filter to, and which parts not.

This would also help with integer arrays, containing for example
foreign key values to a serial column. There's bound to be some
redundancy, as nearby serial values are likely to end up close
together. In one of my past projects we used to store large arrays of
integer fkeys, deliberately sorted for duplicate elimination.

For an ideal case comparison, intar2 could be as large as intar1 when
compressed with a 4-byte wide delta filter:

create table intar1 as select array(select 1::int from
generate_series(1,1000000)) a;
create table intar2 as select array(select generate_series(1,1000000)::int) a;

In PostgreSQL 9.3 the sizes are:
select pg_column_size(a) from intar1;
45810
select pg_column_size(a) from intar2;
4000020

So a factor of 87 difference.

Regards,
Marti

On Mon, Aug 11, 2014 at 3:35 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
>> ... I think it would be a better idea to arrange some method by
>> which JSONB (and perhaps other data types) can provide compression
>> hints to pglz.
>
> I agree with that as a long-term goal, but not sure if it's sane to
> push into 9.4.
>
> What we could conceivably do now is (a) add a datatype OID argument to
> toast_compress_datum, and (b) hard-wire the selection of a different
> compression-parameters struct if it's JSONBOID. The actual fix would
> then be to increase the first_success_by field of this alternate struct.

I think it would be perfectly sane to do that for 9.4. It may not be
perfect, but neither is what we have now.

> A longer-term solution would be to make this some sort of type property
> that domains could inherit, like typstorage is already. (Somebody
> suggested dealing with this by adding more typstorage values, but
> I don't find that attractive; typstorage is known in too many places.)
> We'd need some thought about exactly what we want to expose, since
> the specific knobs that pglz_compress has today aren't necessarily
> good for the long term.

What would really be ideal here is if the JSON code could inform the
toast compression code "this many initial bytes are likely
incompressible, just pass them through without trying, and then start
compressing at byte N", where N is the byte following the TOC. But I
don't know that there's a reasonable way to implement that.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Mon, Aug 11, 2014 at 01:44:05PM -0700, Peter Geoghegan wrote:
> On Mon, Aug 11, 2014 at 1:01 PM, Stephen Frost <sfrost(at)snowman(dot)net> wrote:
> > We've got a clear example of someone, quite reasonably, expecting their
> > JSONB object to be compressed using the normal TOAST mechanism, and
> > we're failing to do that in cases where it's actually a win to do so.
> > That's the focus of this discussion and what needs to be addressed
> > before 9.4 goes out.
>
> Sure. I'm not trying to minimize that. We should fix it, certainly.
> However, it does bear considering that JSON data, with each document
> stored in a row is not an effective target for TOAST compression in
> general, even as text.

Seems we have two issues:

1) the header makes testing for compression likely to fail
2) use of pointers rather than offsets reduces compression potential

I understand we are focusing on #1, but how much does compression reduce
the storage size with and without #2? Seems we need to know that answer
before deciding if it is worth reducing the ability to do fast lookups
with #2.

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ Everyone has their own god. +

On Tue, Aug 12, 2014 at 8:00 PM, Bruce Momjian <bruce(at)momjian(dot)us> wrote:
> On Mon, Aug 11, 2014 at 01:44:05PM -0700, Peter Geoghegan wrote:
>> On Mon, Aug 11, 2014 at 1:01 PM, Stephen Frost <sfrost(at)snowman(dot)net> wrote:
>> > We've got a clear example of someone, quite reasonably, expecting their
>> > JSONB object to be compressed using the normal TOAST mechanism, and
>> > we're failing to do that in cases where it's actually a win to do so.
>> > That's the focus of this discussion and what needs to be addressed
>> > before 9.4 goes out.
>>
>> Sure. I'm not trying to minimize that. We should fix it, certainly.
>> However, it does bear considering that JSON data, with each document
>> stored in a row is not an effective target for TOAST compression in
>> general, even as text.
>
> Seems we have two issues:
>
> 1) the header makes testing for compression likely to fail
> 2) use of pointers rather than offsets reduces compression potential

I do think the best solution for 2 is what's been proposed already, to
do delta-coding of the pointers in chunks (ie, 1 pointer, 15 deltas,
repeat).

But it does make binary search quite more complex.

Alternatively, it could be somewhat compressed as follows:

Segment = 1 pointer head, 15 deltas
Pointer head = pointers[0]
delta[i] = pointers[i] - pointers[0] for i in 1..15

(delta to segment head, not previous value)

Now, you can have 4 types of segments. 8, 16, 32, 64 bits, which is
the size of the deltas. You achieve between 8x and 1x compression, and
even when 1x (no compression), you make it easier for pglz to find
something compressible.

Accessing it is also simple, if you have a segment index (tough part here).

Replace the 15 for something that makes such segment index very compact ;)

Bruce Momjian <bruce(at)momjian(dot)us> writes:
> Seems we have two issues:
> 1) the header makes testing for compression likely to fail
> 2) use of pointers rather than offsets reduces compression potential

> I understand we are focusing on #1, but how much does compression reduce
> the storage size with and without #2? Seems we need to know that answer
> before deciding if it is worth reducing the ability to do fast lookups
> with #2.

That's a fair question. I did a very very simple hack to replace the item
offsets with item lengths -- turns out that that mostly requires removing
some code that changes lengths to offsets ;-). I then loaded up Larry's
example of a noncompressible JSON value, and compared pg_column_size()
which is just about the right thing here since it reports datum size after
compression. Remembering that the textual representation is 12353 bytes:

json: 382 bytes
jsonb, using offsets: 12593 bytes
jsonb, using lengths: 406 bytes

So this confirms my suspicion that the choice of offsets not lengths
is what's killing compressibility. If it used lengths, jsonb would be
very nearly as compressible as the original text.

Hack attached in case anyone wants to collect more thorough statistics.
We'd not actually want to do it like this because of the large expense
of recomputing the offsets on-demand all the time. (It does pass the
regression tests, for what that's worth.)

regards, tom lane

I wrote:
> That's a fair question. I did a very very simple hack to replace the item
> offsets with item lengths -- turns out that that mostly requires removing
> some code that changes lengths to offsets ;-). I then loaded up Larry's
> example of a noncompressible JSON value, and compared pg_column_size()
> which is just about the right thing here since it reports datum size after
> compression. Remembering that the textual representation is 12353 bytes:

> json: 382 bytes
> jsonb, using offsets: 12593 bytes
> jsonb, using lengths: 406 bytes

Oh, one more result: if I leave the representation alone, but change
the compression parameters to set first_success_by to INT_MAX, this
value takes up 1397 bytes. So that's better, but still more than a
3X penalty compared to using lengths. (Admittedly, this test value
probably is an outlier compared to normal practice, since it's a hundred
or so repetitions of the same two strings.)

regards, tom lane

On 08/13/2014 09:01 PM, Tom Lane wrote:
> I wrote:
>> That's a fair question. I did a very very simple hack to replace the item
>> offsets with item lengths -- turns out that that mostly requires removing
>> some code that changes lengths to offsets ;-). I then loaded up Larry's
>> example of a noncompressible JSON value, and compared pg_column_size()
>> which is just about the right thing here since it reports datum size after
>> compression. Remembering that the textual representation is 12353 bytes:
>> json: 382 bytes
>> jsonb, using offsets: 12593 bytes
>> jsonb, using lengths: 406 bytes
> Oh, one more result: if I leave the representation alone, but change
> the compression parameters to set first_success_by to INT_MAX, this
> value takes up 1397 bytes. So that's better, but still more than a
> 3X penalty compared to using lengths. (Admittedly, this test value
> probably is an outlier compared to normal practice, since it's a hundred
> or so repetitions of the same two strings.)
>
>

What does changing to lengths do to the speed of other operations?

cheers

andrew

Andrew Dunstan <andrew(at)dunslane(dot)net> writes:
> On 08/13/2014 09:01 PM, Tom Lane wrote:
>>> That's a fair question. I did a very very simple hack to replace the item
>>> offsets with item lengths -- turns out that that mostly requires removing
>>> some code that changes lengths to offsets ;-).

> What does changing to lengths do to the speed of other operations?

This was explicitly *not* an attempt to measure the speed issue. To do
a fair trial of that, you'd have to work a good bit harder, methinks.
Examining each of N items would involve O(N^2) work with the patch as
posted, but presumably you could get it down to less in most or all
cases --- in particular, sequential traversal could be done with little
added cost. But it'd take a lot more hacking.

regards, tom lane

On 08/14/2014 04:01 AM, Tom Lane wrote:
> I wrote:
>> That's a fair question. I did a very very simple hack to replace the item
>> offsets with item lengths -- turns out that that mostly requires removing
>> some code that changes lengths to offsets ;-). I then loaded up Larry's
>> example of a noncompressible JSON value, and compared pg_column_size()
>> which is just about the right thing here since it reports datum size after
>> compression. Remembering that the textual representation is 12353 bytes:
>
>> json: 382 bytes
>> jsonb, using offsets: 12593 bytes
>> jsonb, using lengths: 406 bytes
>
> Oh, one more result: if I leave the representation alone, but change
> the compression parameters to set first_success_by to INT_MAX, this
> value takes up 1397 bytes. So that's better, but still more than a
> 3X penalty compared to using lengths. (Admittedly, this test value
> probably is an outlier compared to normal practice, since it's a hundred
> or so repetitions of the same two strings.)

For comparison, here's a patch that implements the scheme that Alexander
Korotkov suggested, where we store an offset every 8th element, and a
length in the others. It compresses Larry's example to 525 bytes.
Increasing the "stride" from 8 to 16 entries, it compresses to 461 bytes.

A nice thing about this patch is that it's on-disk compatible with the
current format, hence initdb is not required.

(The current comments claim that the first element in an array always
has the JENTRY_ISFIRST flags set; that is wrong, there is no such flag.
I removed the flag in commit d9daff0e, but apparently failed to update
the comment and the accompanying JBE_ISFIRST macro. Sorry about that,
will fix. This patch uses the bit that used to be JENTRY_ISFIRST to mark
entries that store a length instead of an end offset.).

- Heikki

Heikki Linnakangas <hlinnakangas(at)vmware(dot)com> writes:
> For comparison, here's a patch that implements the scheme that Alexander
> Korotkov suggested, where we store an offset every 8th element, and a
> length in the others. It compresses Larry's example to 525 bytes.
> Increasing the "stride" from 8 to 16 entries, it compresses to 461 bytes.

> A nice thing about this patch is that it's on-disk compatible with the
> current format, hence initdb is not required.

TBH, I think that's about the only nice thing about it :-(. It's
conceptually a mess. And while I agree that this way avoids creating
a big-O performance issue for large arrays/objects, I think the micro
performance is probably going to be not so good. The existing code is
based on the assumption that JBE_OFF() and JBE_LEN() are negligibly cheap;
but with a solution like this, it's guaranteed that one or the other is
going to be not-so-cheap.

I think if we're going to do anything to the representation at all,
we need to refactor the calling code; at least fixing the JsonbIterator
logic so that it tracks the current data offset rather than expecting to
able to compute it at no cost.

The difficulty in arguing about this is that unless we have an agreed-on
performance benchmark test, it's going to be a matter of unsupported
opinions whether one solution is faster than another. Have we got
anything that stresses key lookup and/or array indexing?

regards, tom lane

On Wed, Aug 13, 2014 at 09:01:43PM -0400, Tom Lane wrote:
> I wrote:
> > That's a fair question. I did a very very simple hack to replace the item
> > offsets with item lengths -- turns out that that mostly requires removing
> > some code that changes lengths to offsets ;-). I then loaded up Larry's
> > example of a noncompressible JSON value, and compared pg_column_size()
> > which is just about the right thing here since it reports datum size after
> > compression. Remembering that the textual representation is 12353 bytes:
>
> > json: 382 bytes
> > jsonb, using offsets: 12593 bytes
> > jsonb, using lengths: 406 bytes
>
> Oh, one more result: if I leave the representation alone, but change
> the compression parameters to set first_success_by to INT_MAX, this
> value takes up 1397 bytes. So that's better, but still more than a
> 3X penalty compared to using lengths. (Admittedly, this test value
> probably is an outlier compared to normal practice, since it's a hundred
> or so repetitions of the same two strings.)

Uh, can we get compression for actual documents, rather than duplicate
strings?

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ Everyone has their own god. +

Bruce Momjian <bruce(at)momjian(dot)us> writes:
> Uh, can we get compression for actual documents, rather than duplicate
> strings?

[ shrug... ] What's your proposed set of "actual documents"?
I don't think we have any corpus of JSON docs that are all large
enough to need compression.

This gets back to the problem of what test case are we going to consider
while debating what solution to adopt.

regards, tom lane

On Thu, Aug 14, 2014 at 12:22:46PM -0400, Tom Lane wrote:
> Bruce Momjian <bruce(at)momjian(dot)us> writes:
> > Uh, can we get compression for actual documents, rather than duplicate
> > strings?
>
> [ shrug... ] What's your proposed set of "actual documents"?
> I don't think we have any corpus of JSON docs that are all large
> enough to need compression.
>
> This gets back to the problem of what test case are we going to consider
> while debating what solution to adopt.

Uh, we just one need one 12k JSON document from somewhere. Clearly this
is something we can easily get.

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ Everyone has their own god. +

On Thu, Aug 14, 2014 at 11:52 AM, Bruce Momjian <bruce(at)momjian(dot)us> wrote:
> On Thu, Aug 14, 2014 at 12:22:46PM -0400, Tom Lane wrote:
>> Bruce Momjian <bruce(at)momjian(dot)us> writes:
>> > Uh, can we get compression for actual documents, rather than duplicate
>> > strings?
>>
>> [ shrug... ] What's your proposed set of "actual documents"?
>> I don't think we have any corpus of JSON docs that are all large
>> enough to need compression.
>>
>> This gets back to the problem of what test case are we going to consider
>> while debating what solution to adopt.
>
> Uh, we just one need one 12k JSON document from somewhere. Clearly this
> is something we can easily get.

it's trivial to make a large json[b] document:
select length(to_json(array(select row(a.*) from pg_attribute a))::TEXT);

select

Bruce Momjian <bruce(at)momjian(dot)us> writes:
> On Thu, Aug 14, 2014 at 12:22:46PM -0400, Tom Lane wrote:
>> This gets back to the problem of what test case are we going to consider
>> while debating what solution to adopt.

> Uh, we just one need one 12k JSON document from somewhere. Clearly this
> is something we can easily get.

I would put little faith in a single document as being representative.

To try to get some statistics about a real-world case, I looked at the
delicio.us dataset that someone posted awhile back (1252973 JSON docs).
These have a minimum length (in text representation) of 604 bytes and
a maximum length of 5949 bytes, which means that they aren't going to
tell us all that much about large JSON docs, but this is better than
no data at all.

Since documents of only a couple hundred bytes aren't going to be subject
to compression, I made a table of four columns each containing the same
JSON data, so that each row would be long enough to force the toast logic
to try to do something. (Note that none of these documents are anywhere
near big enough to hit the refuses-to-compress problem.) Given that,
I get the following statistics for pg_column_size():

min max avg

JSON (text) representation 382 1155 526.5

HEAD's JSONB representation 493 1485 695.1

all-lengths representation 440 1257 615.3

So IOW, on this dataset the existing JSONB representation creates about
32% bloat compared to just storing the (compressed) user-visible text,
and switching to all-lengths would about halve that penalty.

Maybe this is telling us it's not worth changing the representation,
and we should just go do something about the first_success_by threshold
and be done. I'm hesitant to draw such conclusions on the basis of a
single use-case though, especially one that doesn't really have that
much use for compression in the first place. Do we have other JSON
corpuses to look at?

regards, tom lane

On Thu, Aug 14, 2014 at 10:57 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Maybe this is telling us it's not worth changing the representation,
> and we should just go do something about the first_success_by threshold
> and be done. I'm hesitant to draw such conclusions on the basis of a
> single use-case though, especially one that doesn't really have that
> much use for compression in the first place. Do we have other JSON
> corpuses to look at?

Yes. Pavel posted some representative JSON data a while back:
http://pgsql.cz/data/data.dump.gz (it's a plain dump)

--
Peter Geoghegan

On Thu, Aug 14, 2014 at 01:57:14PM -0400, Tom Lane wrote:
> Maybe this is telling us it's not worth changing the representation,
> and we should just go do something about the first_success_by threshold
> and be done. I'm hesitant to draw such conclusions on the basis of a
> single use-case though, especially one that doesn't really have that
> much use for compression in the first place. Do we have other JSON
> corpuses to look at?

Yes, that is what I was expecting --- once the whitespace and syntax
sugar is gone in JSONB, I was unclear how much compression would help.

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ Everyone has their own god. +

On 08/14/2014 11:13 AM, Bruce Momjian wrote:
> On Thu, Aug 14, 2014 at 01:57:14PM -0400, Tom Lane wrote:
>> Maybe this is telling us it's not worth changing the representation,
>> and we should just go do something about the first_success_by threshold
>> and be done. I'm hesitant to draw such conclusions on the basis of a
>> single use-case though, especially one that doesn't really have that
>> much use for compression in the first place. Do we have other JSON
>> corpuses to look at?
>
> Yes, that is what I was expecting --- once the whitespace and syntax
> sugar is gone in JSONB, I was unclear how much compression would help.

I thought the destruction case was when we have enough top-level keys
that the offsets are more than 1K total, though, yes?

So we need to test that set ...

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

I did quick test on the same bookmarks to test performance of 9.4beta2 and
9.4beta2+patch

The query was the same we used in pgcon presentation:
SELECT count(*) FROM jb WHERE jb @> '{"tags":[{"term":"NYC"}]}'::jsonb;

table size | time (ms)
9.4beta2: 1374 Mb | 1160
9.4beta2+patch: 1373 Mb | 1213

Yes, performance degrades, but not much. There is also small win in table
size, but bookmarks are not big, so it's difficult to say about compression.

Oleg

On Thu, Aug 14, 2014 at 9:57 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Bruce Momjian <bruce(at)momjian(dot)us> writes:
> > On Thu, Aug 14, 2014 at 12:22:46PM -0400, Tom Lane wrote:
> >> This gets back to the problem of what test case are we going to consider
> >> while debating what solution to adopt.
>
> > Uh, we just one need one 12k JSON document from somewhere. Clearly this
> > is something we can easily get.
>
> I would put little faith in a single document as being representative.
>
> To try to get some statistics about a real-world case, I looked at the
> delicio.us dataset that someone posted awhile back (1252973 JSON docs).
> These have a minimum length (in text representation) of 604 bytes and
> a maximum length of 5949 bytes, which means that they aren't going to
> tell us all that much about large JSON docs, but this is better than
> no data at all.
>
> Since documents of only a couple hundred bytes aren't going to be subject
> to compression, I made a table of four columns each containing the same
> JSON data, so that each row would be long enough to force the toast logic
> to try to do something. (Note that none of these documents are anywhere
> near big enough to hit the refuses-to-compress problem.) Given that,
> I get the following statistics for pg_column_size():
>
> min max avg
>
> JSON (text) representation 382 1155 526.5
>
> HEAD's JSONB representation 493 1485 695.1
>
> all-lengths representation 440 1257 615.3
>
> So IOW, on this dataset the existing JSONB representation creates about
> 32% bloat compared to just storing the (compressed) user-visible text,
> and switching to all-lengths would about halve that penalty.
>
> Maybe this is telling us it's not worth changing the representation,
> and we should just go do something about the first_success_by threshold
> and be done. I'm hesitant to draw such conclusions on the basis of a
> single use-case though, especially one that doesn't really have that
> much use for compression in the first place. Do we have other JSON
> corpuses to look at?
>
> regards, tom lane
>
>
> --
> Sent via pgsql-hackers mailing list (pgsql-hackers(at)postgresql(dot)org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers
>

I attached a json file of approximately 513K. It contains two repetitions
of a single json structure. The values are quasi-random. It might make a
decent test case of meaningfully sized data.

best

On Thu, Aug 14, 2014 at 2:25 PM, Oleg Bartunov <obartunov(at)gmail(dot)com> wrote:

> I did quick test on the same bookmarks to test performance of 9.4beta2 and
> 9.4beta2+patch
>
> The query was the same we used in pgcon presentation:
> SELECT count(*) FROM jb WHERE jb @> '{"tags":[{"term":"NYC"}]}'::jsonb;
>
> table size | time (ms)
> 9.4beta2: 1374 Mb | 1160
> 9.4beta2+patch: 1373 Mb | 1213
>
>
> Yes, performance degrades, but not much. There is also small win in
> table size, but bookmarks are not big, so it's difficult to say about
> compression.
>
> Oleg
>
>
>
> On Thu, Aug 14, 2014 at 9:57 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
>> Bruce Momjian <bruce(at)momjian(dot)us> writes:
>> > On Thu, Aug 14, 2014 at 12:22:46PM -0400, Tom Lane wrote:
>> >> This gets back to the problem of what test case are we going to
>> consider
>> >> while debating what solution to adopt.
>>
>> > Uh, we just one need one 12k JSON document from somewhere. Clearly this
>> > is something we can easily get.
>>
>> I would put little faith in a single document as being representative.
>>
>> To try to get some statistics about a real-world case, I looked at the
>> delicio.us dataset that someone posted awhile back (1252973 JSON docs).
>> These have a minimum length (in text representation) of 604 bytes and
>> a maximum length of 5949 bytes, which means that they aren't going to
>> tell us all that much about large JSON docs, but this is better than
>> no data at all.
>>
>> Since documents of only a couple hundred bytes aren't going to be subject
>> to compression, I made a table of four columns each containing the same
>> JSON data, so that each row would be long enough to force the toast logic
>> to try to do something. (Note that none of these documents are anywhere
>> near big enough to hit the refuses-to-compress problem.) Given that,
>> I get the following statistics for pg_column_size():
>>
>> min max avg
>>
>> JSON (text) representation 382 1155 526.5
>>
>> HEAD's JSONB representation 493 1485 695.1
>>
>> all-lengths representation 440 1257 615.3
>>
>> So IOW, on this dataset the existing JSONB representation creates about
>> 32% bloat compared to just storing the (compressed) user-visible text,
>> and switching to all-lengths would about halve that penalty.
>>
>> Maybe this is telling us it's not worth changing the representation,
>> and we should just go do something about the first_success_by threshold
>> and be done. I'm hesitant to draw such conclusions on the basis of a
>> single use-case though, especially one that doesn't really have that
>> much use for compression in the first place. Do we have other JSON
>> corpuses to look at?
>>
>> regards, tom lane
>>
>>
>> --
>> Sent via pgsql-hackers mailing list (pgsql-hackers(at)postgresql(dot)org)
>> To make changes to your subscription:
>> http://www.postgresql.org/mailpref/pgsql-hackers
>>
>
>

On Thu, Aug 14, 2014 at 3:49 PM, Larry White <ljw1001(at)gmail(dot)com> wrote:
> I attached a json file of approximately 513K. It contains two repetitions of
> a single json structure. The values are quasi-random. It might make a decent
> test case of meaningfully sized data.

I have a 59M in plain SQL (10M compressed, 51M on-disk table size)
collection of real-world JSON data.

This data is mostly counters and anciliary info stored in json for the
flexibility, more than anything else, since it's otherwise quite
structured: most values share a lot between each other (in key names)
but there's not much redundancy within single rows.

Value length stats (in text format):

min: 14
avg: 427
max: 23239

If anyone's interested, contact me personally (I gotta anonimize the
info a bit first, since it's production info, and it's too big to
attach on the ML).

On Thu, Aug 14, 2014 at 4:24 PM, Claudio Freire <klaussfreire(at)gmail(dot)com> wrote:
> On Thu, Aug 14, 2014 at 3:49 PM, Larry White <ljw1001(at)gmail(dot)com> wrote:
>> I attached a json file of approximately 513K. It contains two repetitions of
>> a single json structure. The values are quasi-random. It might make a decent
>> test case of meaningfully sized data.
>
>
> I have a 59M in plain SQL (10M compressed, 51M on-disk table size)
> collection of real-world JSON data.
>
> This data is mostly counters and anciliary info stored in json for the
> flexibility, more than anything else, since it's otherwise quite
> structured: most values share a lot between each other (in key names)
> but there's not much redundancy within single rows.
>
> Value length stats (in text format):
>
> min: 14
> avg: 427
> max: 23239
>
> If anyone's interested, contact me personally (I gotta anonimize the
> info a bit first, since it's production info, and it's too big to
> attach on the ML).

Oh, that one has a 13k toast, not very interesting.

But I've got another (very similar), 47M table, 40M toast, length distribution:

min: 19
avg: 474
max: 20370

Not sure why it's got a bigger toast having a similar distribution.
Tells just how meaningless min/avg/max stats are :(

Peter Geoghegan <pg(at)heroku(dot)com> writes:
> On Thu, Aug 14, 2014 at 10:57 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> Maybe this is telling us it's not worth changing the representation,
>> and we should just go do something about the first_success_by threshold
>> and be done. I'm hesitant to draw such conclusions on the basis of a
>> single use-case though, especially one that doesn't really have that
>> much use for compression in the first place. Do we have other JSON
>> corpuses to look at?

> Yes. Pavel posted some representative JSON data a while back:
> http://pgsql.cz/data/data.dump.gz (it's a plain dump)

I did some quick stats on that. 206560 rows

min max avg

external text representation 220 172685 880.3

JSON representation (compressed text) 224 78565 541.3

pg_column_size, JSONB HEAD repr. 225 82540 639.0

pg_column_size, all-lengths repr. 225 66794 531.1

So in this data, there definitely is some scope for compression:
just compressing the text gets about 38% savings. The all-lengths
hack is able to beat that slightly, but the all-offsets format is
well behind at 27%.

Not sure what to conclude. It looks from both these examples like
we're talking about a 10 to 20 percent size penalty for JSON objects
that are big enough to need compression. Is that beyond our threshold
of pain? I'm not sure, but there is definitely room to argue that the
extra I/O costs will swamp any savings we get from faster access to
individual fields or array elements.

regards, tom lane

On 15/08/14 09:47, Tom Lane wrote:
> Peter Geoghegan <pg(at)heroku(dot)com> writes:
>> On Thu, Aug 14, 2014 at 10:57 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>> Maybe this is telling us it's not worth changing the representation,
>>> and we should just go do something about the first_success_by threshold
>>> and be done. I'm hesitant to draw such conclusions on the basis of a
>>> single use-case though, especially one that doesn't really have that
>>> much use for compression in the first place. Do we have other JSON
>>> corpuses to look at?
>> Yes. Pavel posted some representative JSON data a while back:
>> http://pgsql.cz/data/data.dump.gz (it's a plain dump)
> I did some quick stats on that. 206560 rows
>
> min max avg
>
> external text representation 220 172685 880.3
>
> JSON representation (compressed text) 224 78565 541.3
>
> pg_column_size, JSONB HEAD repr. 225 82540 639.0
>
> pg_column_size, all-lengths repr. 225 66794 531.1
>
> So in this data, there definitely is some scope for compression:
> just compressing the text gets about 38% savings. The all-lengths
> hack is able to beat that slightly, but the all-offsets format is
> well behind at 27%.
>
> Not sure what to conclude. It looks from both these examples like
> we're talking about a 10 to 20 percent size penalty for JSON objects
> that are big enough to need compression. Is that beyond our threshold
> of pain? I'm not sure, but there is definitely room to argue that the
> extra I/O costs will swamp any savings we get from faster access to
> individual fields or array elements.
>
> regards, tom lane
>
>
Curious, would adding the standard deviation help in characterising the
distribution of data values?

Also you might like to consider additionally using the median value, and
possibly the 25% & 75% (or some such) values. I assume the 'avg' in
your table, refers to the arithmetic mean. Sometimes the median is a
better meaure of 'normal' than the arithmetic mean, and it can be useful
to note the difference between the two!

Graphing the values may also be useful. You might have 2, or more,
distinct populations which might show up as several distinct peaks - in
which case, this might suggest changes to the algorithm.

Many moons ago, I did a 400 level statistics course at University, of
which I've forgotten most. However, I'm aware of other potentially
useful measure, but I suspect that they would be too esoteric for the
current problem!

Cheers,
Gavin

So, here's a destruction test case:

200,000 JSON values (plus 2 key columns)
Average width 4K (+/- 1K)
183 keys per JSON value
keys 10 to 30 characters
105 float values
70 integer values
8 text and date values
no nesting

The "jsonic" table is JSON
The "jsonbish" table is JSONB

(I can't share this data set, but it makes a good test case)

And, we see the effect:

postgres=# select pg_size_pretty(pg_total_relation_size('jsonic'));
pg_size_pretty
----------------
394 MB
(1 row)

postgres=# select pg_size_pretty(pg_total_relation_size('jsonbish'));
pg_size_pretty
----------------
1147 MB
(1 row)

So, pretty bad; JSONB is 200% larger than JSON.

I don't think having 183 top-level keys is all that unreasonable of a
use case. Some folks will be migrating from Mongo, Redis or Couch to
PostgreSQL, and might have a whole denormalized schema in JSON.

BTW, I find this peculiar:

postgres=# select pg_size_pretty(pg_relation_size('jsonic'));

pg_size_pretty
----------------
383 MB
(1 row)

postgres=# select pg_size_pretty(pg_relation_size('jsonbish'));

pg_size_pretty
----------------
11 MB
(1 row)

Next up: Tom's patch and indexing!

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Josh Berkus <josh(at)agliodbs(dot)com> writes:
> So, here's a destruction test case:
> 200,000 JSON values (plus 2 key columns)
> Average width 4K (+/- 1K)
> 183 keys per JSON value

Is that 183 keys exactly each time, or is 183 the average?
If so, what's the min/max number of keys?

I ask because 183 would be below the threshold where I'd expect the
no-compression behavior to kick in.

> And, we see the effect:

> postgres=# select pg_size_pretty(pg_total_relation_size('jsonic'));
> pg_size_pretty
> ----------------
> 394 MB
> (1 row)

> postgres=# select pg_size_pretty(pg_total_relation_size('jsonbish'));
> pg_size_pretty
> ----------------
> 1147 MB
> (1 row)

> So, pretty bad; JSONB is 200% larger than JSON.

Ouch. But it's not clear how much of this is from the first_success_by
threshold and how much is from having poor compression even though we
escaped that trap.

> BTW, I find this peculiar:

> postgres=# select pg_size_pretty(pg_relation_size('jsonic'));

> pg_size_pretty
> ----------------
> 383 MB
> (1 row)

> postgres=# select pg_size_pretty(pg_relation_size('jsonbish'));

> pg_size_pretty
> ----------------
> 11 MB
> (1 row)

pg_relation_size is just the main data fork; it excludes TOAST.
So what we can conclude is that most of the data got toasted out-of-line
in jsonb, while very little did in json. That probably just comes from
the average datum size being close to the push-out-of-line threshold,
so that worse compression puts it over the edge.

It would be useful to see min/max/avg of pg_column_size() in both
these cases.

regards, tom lane

On 08/14/2014 04:02 PM, Tom Lane wrote:
> Josh Berkus <josh(at)agliodbs(dot)com> writes:
>> So, here's a destruction test case:
>> 200,000 JSON values (plus 2 key columns)
>> Average width 4K (+/- 1K)
>> 183 keys per JSON value
>
> Is that 183 keys exactly each time, or is 183 the average?

Each time exactly.

> It would be useful to see min/max/avg of pg_column_size() in both
> these cases.

Well, this is 9.4, so I can do better than that. How about quartiles?

thetype | colsize_distribution
---------+----------------------------
json | {1777,1803,1890,1940,4424}
jsonb | {5902,5926,5978,6002,6208}

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Josh Berkus <josh(at)agliodbs(dot)com> writes:
> On 08/14/2014 04:02 PM, Tom Lane wrote:
>> It would be useful to see min/max/avg of pg_column_size() in both
>> these cases.

> Well, this is 9.4, so I can do better than that. How about quartiles?

> thetype | colsize_distribution
> ---------+----------------------------
> json | {1777,1803,1890,1940,4424}
> jsonb | {5902,5926,5978,6002,6208}

OK. That matches with the observation about being mostly toasted or not
--- the threshold for pushing out-of-line would be something a little
under 2KB depending on the other columns you had in the table.

What's more, it looks like the jsonb data is pretty much never getting
compressed --- the min is too high for that. So I'm guessing that this
example is mostly about the first_success_by threshold preventing any
compression from happening. Please, before looking at my other patch,
try this: in src/backend/utils/adt/pg_lzcompress.c, change line 221
thusly:

- 1024, /* Give up if no compression in the first 1KB */
+ INT_MAX, /* Give up if no compression in the first 1KB */

then reload the jsonb data and give us the same stats on that.

regards, tom lane

> What's more, it looks like the jsonb data is pretty much never getting
> compressed --- the min is too high for that. So I'm guessing that this
> example is mostly about the first_success_by threshold preventing any
> compression from happening. Please, before looking at my other patch,
> try this: in src/backend/utils/adt/pg_lzcompress.c, change line 221
> thusly:
>
> - 1024, /* Give up if no compression in the first 1KB */
> + INT_MAX, /* Give up if no compression in the first 1KB */
>
> then reload the jsonb data and give us the same stats on that.

That helped things, but not as much as you'd think:

postgres=# select pg_size_pretty(pg_total_relation_size('jsonic'));

pg_size_pretty
----------------
394 MB
(1 row)

postgres=# select pg_size_pretty(pg_total_relation_size('jsonbish'));
pg_size_pretty
----------------
801 MB
(1 row)

What I find really strange is that the column size distribution is
exactly the same:

thetype | colsize_distribution
---------+----------------------------
json | {1777,1803,1890,1940,4424}
jsonb | {5902,5926,5978,6002,6208}

Shouldn't the lower end stuff be smaller?

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On 08/14/2014 04:47 PM, Josh Berkus wrote:
> thetype | colsize_distribution
> ---------+----------------------------
> json | {1777,1803,1890,1940,4424}
> jsonb | {5902,5926,5978,6002,6208}

Just realized my query was counting the whole row size instead of just
the column size. Here's just the JSON column:

Before changing to to INT_MAX:

thetype | colsize_distribution
---------+----------------------------
json | {1741,1767,1854,1904,2292}
jsonb | {3551,5866,5910,5958,6168}

After:

thetype | colsize_distribution
---------+----------------------------
json | {1741,1767,1854,1904,2292}
jsonb | {3515,3543,3636,3690,4038}

So that did improve things, just not as much as we'd like.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

> Before changing to to INT_MAX:
>
> thetype | colsize_distribution
> ---------+----------------------------
> json | {1741,1767,1854,1904,2292}
> jsonb | {3551,5866,5910,5958,6168}
>
> After:
>
> thetype | colsize_distribution
> ---------+----------------------------
> json | {1741,1767,1854,1904,2292}
> jsonb | {3515,3543,3636,3690,4038}
>
> So that did improve things, just not as much as we'd like.

And with Tom's test patch:

postgres=# select pg_size_pretty(pg_total_relation_size('jsonic'));

pg_size_pretty
----------------
394 MB
(1 row)

postgres=# select pg_size_pretty(pg_total_relation_size('jsonbish'));
pg_size_pretty
----------------
541 MB
(1 row)

thetype | colsize_distribution
---------+----------------------------
json | {1741,1767,1854,1904,2292}
jsonb | {2037,2114,2288,2348,2746}

Since that improved things a *lot*, just +40% instead of +200%, I
thought I'd test some select queries. I decided to test a GIN lookup
and value extraction, since indexed lookup is really what I care about.

9.4b2 no patches:

postgres=# explain analyze select row_to_json -> 'kt1_total_sum' from
jsonbish where row_to_json @> '{ "rpt_per_dt" : "2003-06-30" }';
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on jsonbish (cost=29.55..582.92 rows=200 width=18)
(actual time=20.814..2845.454 rows=100423 loops=1)
Recheck Cond: (row_to_json @> '{"rpt_per_dt": "2003-06-30"}'::jsonb)
Heap Blocks: exact=1471
-> Bitmap Index Scan on jsonbish_row_to_json_idx (cost=0.00..29.50
rows=200 width=0) (actual time=20.551..20.551 rows=100423 loops=1)
Index Cond: (row_to_json @> '{"rpt_per_dt": "2003-06-30"}'::jsonb)
Planning time: 0.102 ms
Execution time: 2856.179 ms

9.4b2 TL patch:

postgres=# explain analyze select row_to_json -> 'kt1_total_sum' from
jsonbish where row_to_json @> '{ "rpt_per_dt" : "2003-06-30" }';
QUERY
PLAN
-------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on jsonbish (cost=29.55..582.92 rows=200 width=18)
(actual time=24.071..5201.687 rows=100423 loops=1)
Recheck Cond: (row_to_json @> '{"rpt_per_dt": "2003-06-30"}'::jsonb)
Heap Blocks: exact=1471
-> Bitmap Index Scan on jsonbish_row_to_json_idx (cost=0.00..29.50
rows=200 width=0) (actual time=23.779..23.779 rows=100423 loops=1)
Index Cond: (row_to_json @> '{"rpt_per_dt": "2003-06-30"}'::jsonb)
Planning time: 0.098 ms
Execution time: 5214.212 ms

... so, an 80% increase in lookup and extraction time for swapping
offsets for lengths. That's actually all extraction time; I tried
removing the extraction from the query, and without it both queries are
close enough to be statstically insignificant.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Josh Berkus <josh(at)agliodbs(dot)com> writes:
> And with Tom's test patch:
> ...
> Since that improved things a *lot*, just +40% instead of +200%, I
> thought I'd test some select queries.

That test patch is not meant to be fast, its ambition was only to see
what the effects on storage size would be. So I find this unsurprising:

> ... so, an 80% increase in lookup and extraction time for swapping
> offsets for lengths.

We can certainly reduce that. The question was whether it would be
worth the effort to try. At this point, with three different test
data sets having shown clear space savings, I think it is worth
the effort. I'll poke into it tomorrow or over the weekend, unless
somebody beats me to it.

regards, tom lane

On 08/14/2014 07:24 PM, Tom Lane wrote:

> We can certainly reduce that. The question was whether it would be
> worth the effort to try. At this point, with three different test
> data sets having shown clear space savings, I think it is worth
> the effort. I'll poke into it tomorrow or over the weekend, unless
> somebody beats me to it.

Note that I specifically created that data set to be a worst case: many
top-level keys, no nesting, and small values. However, I don't think
it's an unrealistic worst case.

Interestingly, even on the unpatched, 1GB table case, the *index* on the
JSONB is only 60MB. Which shows just how terrific the improvement in
GIN index size/performance is.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Josh Berkus <josh(at)agliodbs(dot)com> writes:
> On 08/14/2014 07:24 PM, Tom Lane wrote:
>> We can certainly reduce that. The question was whether it would be
>> worth the effort to try. At this point, with three different test
>> data sets having shown clear space savings, I think it is worth
>> the effort. I'll poke into it tomorrow or over the weekend, unless
>> somebody beats me to it.

> Note that I specifically created that data set to be a worst case: many
> top-level keys, no nesting, and small values. However, I don't think
> it's an unrealistic worst case.

> Interestingly, even on the unpatched, 1GB table case, the *index* on the
> JSONB is only 60MB. Which shows just how terrific the improvement in
> GIN index size/performance is.

I've been poking at this, and I think the main explanation for your result
is that with more JSONB documents being subject to compression, we're
spending more time in pglz_decompress. There's no free lunch in that
department: if you want compressed storage it's gonna cost ya to
decompress. The only way I can get decompression and TOAST access to not
dominate the profile on cases of this size is to ALTER COLUMN SET STORAGE
PLAIN. However, when I do that, I do see my test patch running about 25%
slower overall than HEAD on an "explain analyze select jfield -> 'key'
from table" type of query with 200-key documents with narrow fields (see
attached perl script that generates the test data).

It seems difficult to improve much on that for this test case. I put some
logic into findJsonbValueFromContainer to calculate the offset sums just
once not once per binary-search iteration, but that only improved matters
5% at best. I still think it'd be worth modifying the JsonbIterator code
to avoid repetitive offset calculations, but that's not too relevant to
this test case.

Having said all that, I think this test is something of a contrived worst
case. More realistic cases are likely to have many fewer keys (so that
speed of the binary search loop is less of an issue) or else to have total
document sizes large enough that inline PLAIN storage isn't an option,
meaning that detoast+decompression costs will dominate.

regards, tom lane

I'm still getting up to speed on postgres development but I'd like to leave
an opinion.

We should add some sort of versionning to the jsonb format. This can be
explored in the future in many ways.

As for the current problem, we should explore the directory at the end
option. It should improve compression and keep good access performance.

A 4 byte header is sufficient to store the directory offset and some
versionning bits.
Em 15/08/2014 17:39, "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> escreveu:

> Josh Berkus <josh(at)agliodbs(dot)com> writes:
> > On 08/14/2014 07:24 PM, Tom Lane wrote:
> >> We can certainly reduce that. The question was whether it would be
> >> worth the effort to try. At this point, with three different test
> >> data sets having shown clear space savings, I think it is worth
> >> the effort. I'll poke into it tomorrow or over the weekend, unless
> >> somebody beats me to it.
>
> > Note that I specifically created that data set to be a worst case: many
> > top-level keys, no nesting, and small values. However, I don't think
> > it's an unrealistic worst case.
>
> > Interestingly, even on the unpatched, 1GB table case, the *index* on the
> > JSONB is only 60MB. Which shows just how terrific the improvement in
> > GIN index size/performance is.
>
> I've been poking at this, and I think the main explanation for your result
> is that with more JSONB documents being subject to compression, we're
> spending more time in pglz_decompress. There's no free lunch in that
> department: if you want compressed storage it's gonna cost ya to
> decompress. The only way I can get decompression and TOAST access to not
> dominate the profile on cases of this size is to ALTER COLUMN SET STORAGE
> PLAIN. However, when I do that, I do see my test patch running about 25%
> slower overall than HEAD on an "explain analyze select jfield -> 'key'
> from table" type of query with 200-key documents with narrow fields (see
> attached perl script that generates the test data).
>
> It seems difficult to improve much on that for this test case. I put some
> logic into findJsonbValueFromContainer to calculate the offset sums just
> once not once per binary-search iteration, but that only improved matters
> 5% at best. I still think it'd be worth modifying the JsonbIterator code
> to avoid repetitive offset calculations, but that's not too relevant to
> this test case.
>
> Having said all that, I think this test is something of a contrived worst
> case. More realistic cases are likely to have many fewer keys (so that
> speed of the binary search loop is less of an issue) or else to have total
> document sizes large enough that inline PLAIN storage isn't an option,
> meaning that detoast+decompression costs will dominate.
>
> regards, tom lane
>
>
>
> --
> Sent via pgsql-hackers mailing list (pgsql-hackers(at)postgresql(dot)org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers
>
>

On 08/15/2014 01:38 PM, Tom Lane wrote:
> I've been poking at this, and I think the main explanation for your result
> is that with more JSONB documents being subject to compression, we're
> spending more time in pglz_decompress. There's no free lunch in that
> department: if you want compressed storage it's gonna cost ya to
> decompress. The only way I can get decompression and TOAST access to not
> dominate the profile on cases of this size is to ALTER COLUMN SET STORAGE
> PLAIN. However, when I do that, I do see my test patch running about 25%
> slower overall than HEAD on an "explain analyze select jfield -> 'key'
> from table" type of query with 200-key documents with narrow fields (see
> attached perl script that generates the test data).

Ok, that probably falls under the heading of "acceptable tradeoffs" then.

> Having said all that, I think this test is something of a contrived worst
> case. More realistic cases are likely to have many fewer keys (so that
> speed of the binary search loop is less of an issue) or else to have total
> document sizes large enough that inline PLAIN storage isn't an option,
> meaning that detoast+decompression costs will dominate.

This was intended to be a worst case. However, I don't think that it's
the last time we'll see the case of having 100 to 200 keys each with
short values. That case was actually from some XML data which I'd
already converted into a regular table (hence every row having 183
keys), but if JSONB had been available when I started the project, I
might have chosen to store it as JSONB instead. It occurs to me that
the matching data from a personals website would very much fit the
pattern of having between 50 and 200 keys, each of which has a short value.

So we don't need to *optimize* for that case, but it also shouldn't be
disastrously slow or 300% of the size of comparable TEXT. Mind you, I
don't find +80% to be disastrously slow (especially not with a space
savings of 60%), so maybe that's good enough.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Arthur Silva <arthurprs(at)gmail(dot)com> writes:
> We should add some sort of versionning to the jsonb format. This can be
> explored in the future in many ways.

If we end up making an incompatible change to the jsonb format, I would
support taking the opportunity to stick a version ID in there. But
I don't want to force a dump/reload cycle *only* to do that.

> As for the current problem, we should explore the directory at the end
> option. It should improve compression and keep good access performance.

Meh. Pushing the directory to the end is just a band-aid, and since it
would still force a dump/reload, it's not a very enticing band-aid.
The only thing it'd really fix is the first_success_by issue, which
we could fix *without* a dump/reload by using different compression
parameters for jsonb. Moving the directory to the end, by itself,
does nothing to fix the problem that the directory contents aren't
compressible --- and we now have pretty clear evidence that that is a
significant issue. (See for instance Josh's results that increasing
first_success_by did very little for the size of his dataset.)

I think the realistic alternatives at this point are either to
switch to all-lengths as in my test patch, or to use the hybrid approach
of Heikki's test patch. IMO the major attraction of Heikki's patch
is that it'd be upward compatible with existing beta installations,
ie no initdb required (but thus, no opportunity to squeeze in a version
identifier either). It's not showing up terribly well in the performance
tests I've been doing --- it's about halfway between HEAD and my patch on
that extract-a-key-from-a-PLAIN-stored-column test. But, just as with my
patch, there are things that could be done to micro-optimize it by
touching a bit more code.

I did some quick stats comparing compressed sizes for the delicio.us
data, printing quartiles as per Josh's lead:

all-lengths {440,569,609,655,1257}
Heikki's patch {456,582,624,671,1274}
HEAD {493,636,684,744,1485}

(As before, this is pg_column_size of the jsonb within a table whose rows
are wide enough to force tuptoaster.c to try to compress the jsonb;
otherwise many of these values wouldn't get compressed.) These documents
don't have enough keys to trigger the first_success_by issue, so that
HEAD doesn't look too awful, but still there's about an 11% gain from
switching from offsets to lengths. Heikki's method captures much of
that but not all.

Personally I'd prefer to go to the all-lengths approach, but a large
part of that comes from a subjective assessment that the hybrid approach
is too messy. Others might well disagree.

In case anyone else wants to do measurements on some more data sets,
attached is a copy of Heikki's patch updated to apply against git tip.

regards, tom lane

On Fri, Aug 15, 2014 at 8:19 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Arthur Silva <arthurprs(at)gmail(dot)com> writes:
> > We should add some sort of versionning to the jsonb format. This can be
> > explored in the future in many ways.
>
> If we end up making an incompatible change to the jsonb format, I would
> support taking the opportunity to stick a version ID in there. But
> I don't want to force a dump/reload cycle *only* to do that.
>
> > As for the current problem, we should explore the directory at the end
> > option. It should improve compression and keep good access performance.
>
> Meh. Pushing the directory to the end is just a band-aid, and since it
> would still force a dump/reload, it's not a very enticing band-aid.
> The only thing it'd really fix is the first_success_by issue, which
> we could fix *without* a dump/reload by using different compression
> parameters for jsonb. Moving the directory to the end, by itself,
> does nothing to fix the problem that the directory contents aren't
> compressible --- and we now have pretty clear evidence that that is a
> significant issue. (See for instance Josh's results that increasing
> first_success_by did very little for the size of his dataset.)
>
> I think the realistic alternatives at this point are either to
> switch to all-lengths as in my test patch, or to use the hybrid approach
> of Heikki's test patch. IMO the major attraction of Heikki's patch
> is that it'd be upward compatible with existing beta installations,
> ie no initdb required (but thus, no opportunity to squeeze in a version
> identifier either). It's not showing up terribly well in the performance
> tests I've been doing --- it's about halfway between HEAD and my patch on
> that extract-a-key-from-a-PLAIN-stored-column test. But, just as with my
> patch, there are things that could be done to micro-optimize it by
> touching a bit more code.
>
> I did some quick stats comparing compressed sizes for the delicio.us
> data, printing quartiles as per Josh's lead:
>
> all-lengths {440,569,609,655,1257}
> Heikki's patch {456,582,624,671,1274}
> HEAD {493,636,684,744,1485}
>
> (As before, this is pg_column_size of the jsonb within a table whose rows
> are wide enough to force tuptoaster.c to try to compress the jsonb;
> otherwise many of these values wouldn't get compressed.) These documents
> don't have enough keys to trigger the first_success_by issue, so that
> HEAD doesn't look too awful, but still there's about an 11% gain from
> switching from offsets to lengths. Heikki's method captures much of
> that but not all.
>
> Personally I'd prefer to go to the all-lengths approach, but a large
> part of that comes from a subjective assessment that the hybrid approach
> is too messy. Others might well disagree.
>
> In case anyone else wants to do measurements on some more data sets,
> attached is a copy of Heikki's patch updated to apply against git tip.
>
> regards, tom lane
>
>
I agree that versioning might sound silly at this point, but lets keep it
in mind.
Row level compression is very slow itself, so it sounds odd to me paying
25% performance penalty everywhere for the sake of having better
compression ratio in the dictionary area.
Consider, for example, an optimization that stuffs integers (up to 28 bits)
inside the JEntry itself. That alone would save 8 bytes for each integer.

On 08/15/2014 04:19 PM, Tom Lane wrote:
> Personally I'd prefer to go to the all-lengths approach, but a large
> part of that comes from a subjective assessment that the hybrid approach
> is too messy. Others might well disagree.
>
> In case anyone else wants to do measurements on some more data sets,
> attached is a copy of Heikki's patch updated to apply against git tip.

Note that this is not 100% comparable because I'm running it against git
clone, and the earlier tests were against beta2. However, the Heikki
patch looks like a bust on this dataset -- see below.

postgres=# select pg_size_pretty(pg_total_relation_size('jsonic'));
pg_size_pretty
----------------
394 MB
(1 row)

postgres=# select pg_size_pretty(pg_total_relation_size('jsonbish'));

pg_size_pretty
----------------
542 MB

Extraction Test:

postgres=# explain analyze select row_to_json -> 'kt1_total_sum' from
jsonbish where row_to_json @> '{ "rpt_per_dt" : "2003-06-30" }';
QUERY
PLAN
-------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on jsonbish (cost=29.55..582.92 rows=200 width=18)
(actual time=22.742..5281.823 rows=100423 loops=1)
Recheck Cond: (row_to_json @> '{"rpt_per_dt": "2003-06-30"}'::jsonb)
Heap Blocks: exact=1471
-> Bitmap Index Scan on jsonbish_row_to_json_idx (cost=0.00..29.50
rows=200 width=0) (actual time=22.445..22.445 rows=100423 loops=1)
Index Cond: (row_to_json @> '{"rpt_per_dt": "2003-06-30"}'::jsonb)
Planning time: 0.095 ms
Execution time: 5292.047 ms
(7 rows)

So, that extraction test is about 1% *slower* than the basic Tom Lane
lengths-only patch, and still 80% slower than original JSONB. And it's
the same size as the lengths-only version.

Huh?

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Josh Berkus <josh(at)agliodbs(dot)com> writes:
> On 08/15/2014 04:19 PM, Tom Lane wrote:
>> Personally I'd prefer to go to the all-lengths approach, but a large
>> part of that comes from a subjective assessment that the hybrid approach
>> is too messy. Others might well disagree.

> ... So, that extraction test is about 1% *slower* than the basic Tom Lane
> lengths-only patch, and still 80% slower than original JSONB. And it's
> the same size as the lengths-only version.

Since it's looking like this might be the direction we want to go, I took
the time to flesh out my proof-of-concept patch. The attached version
takes care of cosmetic issues (like fixing the comments), and includes
code to avoid O(N^2) penalties in findJsonbValueFromContainer and
JsonbIteratorNext. I'm not sure whether those changes will help
noticeably on Josh's test case; for me, they seemed worth making, but
they do not bring the code back to full speed parity with the all-offsets
version. But as we've been discussing, it seems likely that those costs
would be swamped by compression and I/O considerations in most scenarios
with large documents; and of course for small documents it hardly matters.

Even if we don't go this way, there are parts of this patch that would
need to get committed. I found for instance that convertJsonbArray and
convertJsonbObject have insufficient defenses against overflowing the
overall length field for the array or object.

For my own part, I'm satisfied with the patch as attached (modulo the
need to teach pg_upgrade about the incompatibility). There remains the
question of whether to take this opportunity to add a version ID to the
binary format. I'm not as excited about that idea as I originally was;
having now studied the code more carefully, I think that any expansion
would likely happen by adding more type codes and/or commandeering the
currently-unused high-order bit of JEntrys. We don't need a version ID
in the header for that. Moreover, if we did have such an ID, it would be
notationally painful to get it to most of the places that might need it.

regards, tom lane

On 08/20/2014 08:29 AM, Tom Lane wrote:
> Since it's looking like this might be the direction we want to go, I took
> the time to flesh out my proof-of-concept patch. The attached version
> takes care of cosmetic issues (like fixing the comments), and includes
> code to avoid O(N^2) penalties in findJsonbValueFromContainer and
> JsonbIteratorNext

OK, will test.

This means we need a beta3, no?

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Josh Berkus <josh(at)agliodbs(dot)com> writes:
> This means we need a beta3, no?

If we change the on-disk format, I'd say so. So we don't want to wait
around too long before deciding.

regards, tom lane

On 08/20/2014 08:29 AM, Tom Lane wrote:
> Josh Berkus <josh(at)agliodbs(dot)com> writes:
>> On 08/15/2014 04:19 PM, Tom Lane wrote:
>>> Personally I'd prefer to go to the all-lengths approach, but a large
>>> part of that comes from a subjective assessment that the hybrid approach
>>> is too messy. Others might well disagree.
>
>> ... So, that extraction test is about 1% *slower* than the basic Tom Lane
>> lengths-only patch, and still 80% slower than original JSONB. And it's
>> the same size as the lengths-only version.
>
> Since it's looking like this might be the direction we want to go, I took
> the time to flesh out my proof-of-concept patch. The attached version
> takes care of cosmetic issues (like fixing the comments), and includes
> code to avoid O(N^2) penalties in findJsonbValueFromContainer and
> JsonbIteratorNext. I'm not sure whether those changes will help
> noticeably on Josh's test case; for me, they seemed worth making, but
> they do not bring the code back to full speed parity with the all-offsets
> version. But as we've been discussing, it seems likely that those costs
> would be swamped by compression and I/O considerations in most scenarios
> with large documents; and of course for small documents it hardly matters.

Table sizes and extraction times are unchanged from the prior patch
based on my workload.

We should be comparing all-lengths vs length-and-offset maybe using
another workload as well ...

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

What data are you using right now Josh?

There's the github archive http://www.githubarchive.org/
Here's some sample data https://gist.github.com/igrigorik/2017462

--
Arthur Silva

On Wed, Aug 20, 2014 at 6:09 PM, Josh Berkus <josh(at)agliodbs(dot)com> wrote:

> On 08/20/2014 08:29 AM, Tom Lane wrote:
> > Josh Berkus <josh(at)agliodbs(dot)com> writes:
> >> On 08/15/2014 04:19 PM, Tom Lane wrote:
> >>> Personally I'd prefer to go to the all-lengths approach, but a large
> >>> part of that comes from a subjective assessment that the hybrid
> approach
> >>> is too messy. Others might well disagree.
> >
> >> ... So, that extraction test is about 1% *slower* than the basic Tom
> Lane
> >> lengths-only patch, and still 80% slower than original JSONB. And it's
> >> the same size as the lengths-only version.
> >
> > Since it's looking like this might be the direction we want to go, I took
> > the time to flesh out my proof-of-concept patch. The attached version
> > takes care of cosmetic issues (like fixing the comments), and includes
> > code to avoid O(N^2) penalties in findJsonbValueFromContainer and
> > JsonbIteratorNext. I'm not sure whether those changes will help
> > noticeably on Josh's test case; for me, they seemed worth making, but
> > they do not bring the code back to full speed parity with the all-offsets
> > version. But as we've been discussing, it seems likely that those costs
> > would be swamped by compression and I/O considerations in most scenarios
> > with large documents; and of course for small documents it hardly
> matters.
>
> Table sizes and extraction times are unchanged from the prior patch
> based on my workload.
>
> We should be comparing all-lengths vs length-and-offset maybe using
> another workload as well ...
>
> --
> Josh Berkus
> PostgreSQL Experts Inc.
> http://pgexperts.com
>

On 08/20/2014 03:42 PM, Arthur Silva wrote:
> What data are you using right now Josh?

The same data as upthread.

Can you test the three patches (9.4 head, 9.4 with Tom's cleanup of
Heikki's patch, and 9.4 with Tom's latest lengths-only) on your workload?

I'm concerned that my workload is unusual and don't want us to make this
decision based entirely on it.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On Thu, Aug 21, 2014 at 6:20 PM, Josh Berkus <josh(at)agliodbs(dot)com> wrote:

> On 08/20/2014 03:42 PM, Arthur Silva wrote:
> > What data are you using right now Josh?
>
> The same data as upthread.
>
> Can you test the three patches (9.4 head, 9.4 with Tom's cleanup of
> Heikki's patch, and 9.4 with Tom's latest lengths-only) on your workload?
>
> I'm concerned that my workload is unusual and don't want us to make this
> decision based entirely on it.
>
> --
> Josh Berkus
> PostgreSQL Experts Inc.
> http://pgexperts.com
>

Here's my test results so far with the github archive data.

It's important to keep in mind that the PushEvent event objects that I use
in the queries only contains a small number of keys (8 to be precise), so
these tests don't really stress the changed code.

Anyway, in this dataset (with the small objects) using the all-lengths
patch provide small compression savings but the overhead is minimal.

----------------

Test data: 610MB of Json -- 341969 items

Index size (jsonb_ops): 331MB

Test query 1: SELECT data->'url', data->'actor' FROM t_json WHERE data @>
'{"type": "PushEvent"}'
Test query 1 items: 169732

Test query 2: SELECT data FROM t_json WHERE data @> '{"type": "PushEvent"}'
Test query 2 items:

----------------
HEAD (aka, all offsets) EXTENDED
Size: 374MB
Toast Size: 145MB

Test query 1 runtime: 680ms
Test query 2 runtime: 405ms
----------------
HEAD (aka, all offsets) EXTERNAL
Size: 366MB
Toast Size: 333MB

Test query 1 runtime: 505ms
Test query 2 runtime: 350ms
----------------
All Lengths (Tom Lane patch) EXTENDED
Size: 379MB
Toast Size: 108MB

Test query 1 runtime: 720ms
Test query 2 runtime: 420ms
----------------
All Lengths (Tom Lane patch) EXTERNAL
Size: 366MB
Toast Size: 333MB

Test query 1 runtime: 525ms
Test query 2 runtime: 355ms

--
Arthur Silva

On 08/16/2014 02:19 AM, Tom Lane wrote:
> I think the realistic alternatives at this point are either to
> switch to all-lengths as in my test patch, or to use the hybrid approach
> of Heikki's test patch. IMO the major attraction of Heikki's patch
> is that it'd be upward compatible with existing beta installations,
> ie no initdb required (but thus, no opportunity to squeeze in a version
> identifier either). It's not showing up terribly well in the performance
> tests I've been doing --- it's about halfway between HEAD and my patch on
> that extract-a-key-from-a-PLAIN-stored-column test. But, just as with my
> patch, there are things that could be done to micro-optimize it by
> touching a bit more code.
>
> I did some quick stats comparing compressed sizes for the delicio.us
> data, printing quartiles as per Josh's lead:
>
> all-lengths {440,569,609,655,1257}
> Heikki's patch {456,582,624,671,1274}
> HEAD {493,636,684,744,1485}
>
> (As before, this is pg_column_size of the jsonb within a table whose rows
> are wide enough to force tuptoaster.c to try to compress the jsonb;
> otherwise many of these values wouldn't get compressed.) These documents
> don't have enough keys to trigger the first_success_by issue, so that
> HEAD doesn't look too awful, but still there's about an 11% gain from
> switching from offsets to lengths. Heikki's method captures much of
> that but not all.
>
> Personally I'd prefer to go to the all-lengths approach, but a large
> part of that comes from a subjective assessment that the hybrid approach
> is too messy. Others might well disagree.

It's not too pretty, no. But it would be nice to not have to make a
tradeoff between lookup speed and compressibility.

Yet another idea is to store all lengths, but add an additional array of
offsets to JsonbContainer. The array would contain the offset of, say,
every 16th element. It would be very small compared to the lengths
array, but would greatly speed up random access on a large array/object.

- Heikki

Heikki Linnakangas <hlinnakangas(at)vmware(dot)com> writes:
> On 08/16/2014 02:19 AM, Tom Lane wrote:
>> I think the realistic alternatives at this point are either to
>> switch to all-lengths as in my test patch, or to use the hybrid approach
>> of Heikki's test patch. ...
>> Personally I'd prefer to go to the all-lengths approach, but a large
>> part of that comes from a subjective assessment that the hybrid approach
>> is too messy. Others might well disagree.

> It's not too pretty, no. But it would be nice to not have to make a
> tradeoff between lookup speed and compressibility.

> Yet another idea is to store all lengths, but add an additional array of
> offsets to JsonbContainer. The array would contain the offset of, say,
> every 16th element. It would be very small compared to the lengths
> array, but would greatly speed up random access on a large array/object.

That does nothing to address my basic concern about the patch, which is
that it's too complicated and therefore bug-prone. Moreover, it'd lose
on-disk compatibility which is really the sole saving grace of the
proposal.

My feeling about it at this point is that the apparent speed gain from
using offsets is illusory: in practically all real-world cases where there
are enough keys or array elements for it to matter, costs associated with
compression (or rather failure to compress) will dominate any savings we
get from offset-assisted lookups. I agree that the evidence for this
opinion is pretty thin ... but the evidence against it is nonexistent.

regards, tom lane

On 08/26/2014 07:51 AM, Tom Lane wrote:
> My feeling about it at this point is that the apparent speed gain from
> using offsets is illusory: in practically all real-world cases where there
> are enough keys or array elements for it to matter, costs associated with
> compression (or rather failure to compress) will dominate any savings we
> get from offset-assisted lookups. I agree that the evidence for this
> opinion is pretty thin ... but the evidence against it is nonexistent.

Well, I have shown one test case which shows where lengths is a net
penalty. However, for that to be the case, you have to have the
following conditions *all* be true:

* lots of top-level keys
* short values
* rows which are on the borderline for TOAST
* table which fits in RAM

... so that's a "special case" and if it's sub-optimal, no bigee. Also,
it's not like it's an order-of-magnitude slower.

Anyway, I called for feedback on by blog, and have gotten some:

http://www.databasesoup.com/2014/08/the-great-jsonb-tradeoff.html

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Josh Berkus <josh(at)agliodbs(dot)com> writes:
> Anyway, I called for feedback on by blog, and have gotten some:
> http://www.databasesoup.com/2014/08/the-great-jsonb-tradeoff.html

I was hoping you'd get some useful data from that, but so far it seems
like a rehash of points made in the on-list thread :-(

regards, tom lane

On 08/26/2014 11:40 AM, Tom Lane wrote:
> Josh Berkus <josh(at)agliodbs(dot)com> writes:
>> Anyway, I called for feedback on by blog, and have gotten some:
>> http://www.databasesoup.com/2014/08/the-great-jsonb-tradeoff.html
>
> I was hoping you'd get some useful data from that, but so far it seems
> like a rehash of points made in the on-list thread :-(
>
> regards, tom lane

yah, me too. :-(

Unfortunately even the outside commentors don't seem to understand that
storage size *is* related to speed, it's exchanging I/O speed for CPU speed.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Josh Berkus <josh(at)agliodbs(dot)com> writes:
> On 08/26/2014 11:40 AM, Tom Lane wrote:
>> I was hoping you'd get some useful data from that, but so far it seems
>> like a rehash of points made in the on-list thread :-(

> Unfortunately even the outside commentors don't seem to understand that
> storage size *is* related to speed, it's exchanging I/O speed for CPU speed.

Yeah, exactly. Given current hardware trends, data compression is
becoming more of a win not less as time goes on: CPU cycles are cheap
even compared to main memory access, let alone mass storage. So I'm
thinking we want to adopt a compression-friendly data format even if
it measures out as a small loss currently.

I wish it were cache-friendly too, per the upthread tangent about having
to fetch keys from all over the place within a large JSON object.

... and while I was typing that sentence, lightning struck. The existing
arrangement of object subfields with keys and values interleaved is just
plain dumb. We should rearrange that as all the keys in order, then all
the values in the same order. Then the keys are naturally adjacent in
memory and object-key searches become much more cache-friendly: you
probably touch most of the key portion of the object, but none of the
values portion, until you know exactly what part of the latter to fetch.
This approach might complicate the lookup logic marginally but I bet not
very much; and it will be a huge help if we ever want to do smart access
to EXTERNAL (non-compressed) JSON values.

I will go prototype that just to see how much code rearrangement is
required.

regards, tom lane

On 2014-08-26 15:01:27 -0400, Tom Lane wrote:
> Josh Berkus <josh(at)agliodbs(dot)com> writes:
> > On 08/26/2014 11:40 AM, Tom Lane wrote:
> >> I was hoping you'd get some useful data from that, but so far it seems
> >> like a rehash of points made in the on-list thread :-(
>
> > Unfortunately even the outside commentors don't seem to understand that
> > storage size *is* related to speed, it's exchanging I/O speed for CPU speed.
>
> Yeah, exactly. Given current hardware trends, data compression is
> becoming more of a win not less as time goes on: CPU cycles are cheap
> even compared to main memory access, let alone mass storage. So I'm
> thinking we want to adopt a compression-friendly data format even if
> it measures out as a small loss currently.

On the other hand the majority of databases these day fit into main
memory due to its increasing sizes and postgres is more often CPU than
IO bound.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On 26 August 2014 11:34, Josh Berkus <josh(at)agliodbs(dot)com> wrote:

> On 08/26/2014 07:51 AM, Tom Lane wrote:
> > My feeling about it at this point is that the apparent speed gain from
> > using offsets is illusory: in practically all real-world cases where
> there
> > are enough keys or array elements for it to matter, costs associated with
> > compression (or rather failure to compress) will dominate any savings we
> > get from offset-assisted lookups. I agree that the evidence for this
> > opinion is pretty thin ... but the evidence against it is nonexistent.
>
> Well, I have shown one test case which shows where lengths is a net
> penalty. However, for that to be the case, you have to have the
> following conditions *all* be true:
>
> * lots of top-level keys
> * short values
> * rows which are on the borderline for TOAST
> * table which fits in RAM
>
> ... so that's a "special case" and if it's sub-optimal, no bigee. Also,
> it's not like it's an order-of-magnitude slower.
>
> Anyway, I called for feedback on by blog, and have gotten some:
>
> http://www.databasesoup.com/2014/08/the-great-jsonb-tradeoff.html

It would be really interesting to see your results with column STORAGE
EXTERNAL for that benchmark. I think it is important to separate out the
slowdown due to decompression now being needed vs that inherent in the new
format, we can always switch off compression on a per-column basis using
STORAGE EXTERNAL.

My JSON data has smallish objects with a small number of keys, it barely
compresses at all with the patch and shows similar results to Arthur's
data. Across ~500K rows I get:

encoded=# select count(properties->>'submitted_by') from compressed;
count
--------
431948
(1 row)

Time: 250.512 ms

encoded=# select count(properties->>'submitted_by') from uncompressed;
count
--------
431948
(1 row)

Time: 218.552 ms

Laurence

Andres Freund <andres(at)2ndquadrant(dot)com> writes:
> On 2014-08-26 15:01:27 -0400, Tom Lane wrote:
>> Yeah, exactly. Given current hardware trends, data compression is
>> becoming more of a win not less as time goes on: CPU cycles are cheap
>> even compared to main memory access, let alone mass storage. So I'm
>> thinking we want to adopt a compression-friendly data format even if
>> it measures out as a small loss currently.

> On the other hand the majority of databases these day fit into main
> memory due to its increasing sizes and postgres is more often CPU than
> IO bound.

Well, better data compression helps make that true ;-). And don't forget
cache effects; actual main memory is considered slow these days.

regards, tom lane

On Tue, Aug 26, 2014 at 4:01 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Josh Berkus <josh(at)agliodbs(dot)com> writes:
>> On 08/26/2014 11:40 AM, Tom Lane wrote:
>>> I was hoping you'd get some useful data from that, but so far it seems
>>> like a rehash of points made in the on-list thread :-(
>
>> Unfortunately even the outside commentors don't seem to understand that
>> storage size *is* related to speed, it's exchanging I/O speed for CPU speed.
>
> Yeah, exactly. Given current hardware trends, data compression is
> becoming more of a win not less as time goes on: CPU cycles are cheap
> even compared to main memory access, let alone mass storage. So I'm
> thinking we want to adopt a compression-friendly data format even if
> it measures out as a small loss currently.
>
> I wish it were cache-friendly too, per the upthread tangent about having
> to fetch keys from all over the place within a large JSON object.

What about my earlier proposal?

An in-memory compressed representation would greatly help cache
locality, more so if you pack keys as you mentioned.

On 2014-08-26 15:17:13 -0400, Tom Lane wrote:
> Andres Freund <andres(at)2ndquadrant(dot)com> writes:
> > On 2014-08-26 15:01:27 -0400, Tom Lane wrote:
> >> Yeah, exactly. Given current hardware trends, data compression is
> >> becoming more of a win not less as time goes on: CPU cycles are cheap
> >> even compared to main memory access, let alone mass storage. So I'm
> >> thinking we want to adopt a compression-friendly data format even if
> >> it measures out as a small loss currently.
>
> > On the other hand the majority of databases these day fit into main
> > memory due to its increasing sizes and postgres is more often CPU than
> > IO bound.
>
> Well, better data compression helps make that true ;-).

People disable toast compression though because it results in better
performance :(. Part of that could be fixed by a faster compression
method, part of it by decompressing less often. But still.

> And don't forget cache effects; actual main memory is considered slow
> these days.

Right. But that plays the other way round too. Compressed datums need to
be copied to be accessed uncompressed. Whereas at least in comparison to
inline compressed datums that's not necessary.

Anyway, that's just to say that I don't really agree that CPU overhead
is a worthy price to pay for storage efficiency if the gains are small.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Tue, Aug 26, 2014 at 12:27 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> Anyway, that's just to say that I don't really agree that CPU overhead
> is a worthy price to pay for storage efficiency if the gains are small.

+1

--
Peter Geoghegan

On 08/26/2014 12:27 PM, Andres Freund wrote:
> Anyway, that's just to say that I don't really agree that CPU overhead
> is a worthy price to pay for storage efficiency if the gains are small.

But in this case the gains aren't small; we're talking up to 60% smaller
storage.

Testing STORAGE EXTENDED soon.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

I wrote:
> I wish it were cache-friendly too, per the upthread tangent about having
> to fetch keys from all over the place within a large JSON object.

> ... and while I was typing that sentence, lightning struck. The existing
> arrangement of object subfields with keys and values interleaved is just
> plain dumb. We should rearrange that as all the keys in order, then all
> the values in the same order. Then the keys are naturally adjacent in
> memory and object-key searches become much more cache-friendly: you
> probably touch most of the key portion of the object, but none of the
> values portion, until you know exactly what part of the latter to fetch.
> This approach might complicate the lookup logic marginally but I bet not
> very much; and it will be a huge help if we ever want to do smart access
> to EXTERNAL (non-compressed) JSON values.

> I will go prototype that just to see how much code rearrangement is
> required.

This looks pretty good from a coding point of view. I have not had time
yet to see if it affects the speed of the benchmark cases we've been
trying. I suspect that it won't make much difference in them. I think
if we do decide to make an on-disk format change, we should seriously
consider including this change.

The same concept could be applied to offset-based storage of course,
although I rather doubt that we'd make that combination of choices since
it would be giving up on-disk compatibility for benefits that are mostly
in the future.

Attached are two patches: one is a "delta" against the last jsonb-lengths
patch I posted, and the other is a "merged" patch showing the total change
from HEAD, for ease of application.

regards, tom lane

Tom, here's the results with github data (8 top level keys) only. Here's a
sample object https://gist.github.com/igrigorik/2017462

All-Lenghts + Cache-Aware EXTERNAL
Query 1: 516ms
Query 2: 350ms

The difference is small but I's definitely faster, which makes sense since
cache line misses are probably slightly reduced.
As in the previous runs, I ran the query a dozen times and took the average
after excluding runs with a high deviation.

compare to (copied from my previous email)

HEAD (aka, all offsets) EXTERNAL
Test query 1 runtime: 505ms
Test query 2 runtime: 350ms

All Lengths (Tom Lane patch) EXTERNAL
Test query 1 runtime: 525ms
Test query 2 runtime: 355ms

--
Arthur Silva

On Tue, Aug 26, 2014 at 7:11 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> I wrote:
> > I wish it were cache-friendly too, per the upthread tangent about having
> > to fetch keys from all over the place within a large JSON object.
>
> > ... and while I was typing that sentence, lightning struck. The existing
> > arrangement of object subfields with keys and values interleaved is just
> > plain dumb. We should rearrange that as all the keys in order, then all
> > the values in the same order. Then the keys are naturally adjacent in
> > memory and object-key searches become much more cache-friendly: you
> > probably touch most of the key portion of the object, but none of the
> > values portion, until you know exactly what part of the latter to fetch.
> > This approach might complicate the lookup logic marginally but I bet not
> > very much; and it will be a huge help if we ever want to do smart access
> > to EXTERNAL (non-compressed) JSON values.
>
> > I will go prototype that just to see how much code rearrangement is
> > required.
>
> This looks pretty good from a coding point of view. I have not had time
> yet to see if it affects the speed of the benchmark cases we've been
> trying. I suspect that it won't make much difference in them. I think
> if we do decide to make an on-disk format change, we should seriously
> consider including this change.
>
> The same concept could be applied to offset-based storage of course,
> although I rather doubt that we'd make that combination of choices since
> it would be giving up on-disk compatibility for benefits that are mostly
> in the future.
>
> Attached are two patches: one is a "delta" against the last jsonb-lengths
> patch I posted, and the other is a "merged" patch showing the total change
> from HEAD, for ease of application.
>
> regards, tom lane
>
>

On Tue, Aug 26, 2014 at 8:41 PM, Arthur Silva <arthurprs(at)gmail(dot)com> wrote:
> The difference is small but I's definitely faster, which makes sense since
> cache line misses are probably slightly reduced.
> As in the previous runs, I ran the query a dozen times and took the average
> after excluding runs with a high deviation.

I'm not surprised that it hasn't beaten HEAD. I haven't studied the
problem in detail, but I don't think that the "cache awareness" of the
new revision is necessarily a distinct advantage.

--
Peter Geoghegan

Peter Geoghegan <pg(at)heroku(dot)com> writes:
> I'm not surprised that it hasn't beaten HEAD. I haven't studied the
> problem in detail, but I don't think that the "cache awareness" of the
> new revision is necessarily a distinct advantage.

I doubt it's a significant advantage in the current state of the code;
I'm happy if it's not a loss. I was looking ahead to someday fetching key
values efficiently from large EXTERNAL (ie out-of-line-but-not-compressed)
JSON values, analogously to the existing optimization for fetching text
substrings from EXTERNAL text values. As mentioned upthread, the current
JSONB representation would be seriously unfriendly to such a thing.

regards, tom lane

It won't be faster by any means, but it should definitely be incorporated
if any format changes are made (like Tom already suggested).

I think it's important we gather at least 2 more things before making any
calls:
* Josh tests w/ cache aware patch, which should confirm cache aware is
indeed prefered
* Tests with toast hacked to use lz4 instead, which might ease any decisions

--
Arthur Silva

On Wed, Aug 27, 2014 at 12:53 AM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:

> On Tue, Aug 26, 2014 at 8:41 PM, Arthur Silva <arthurprs(at)gmail(dot)com> wrote:
> > The difference is small but I's definitely faster, which makes sense
> since
> > cache line misses are probably slightly reduced.
> > As in the previous runs, I ran the query a dozen times and took the
> average
> > after excluding runs with a high deviation.
>
> I'm not surprised that it hasn't beaten HEAD. I haven't studied the
> problem in detail, but I don't think that the "cache awareness" of the
> new revision is necessarily a distinct advantage.
>
> --
> Peter Geoghegan
>

On Wed, Aug 27, 2014 at 1:09 AM, Arthur Silva <arthurprs(at)gmail(dot)com> wrote:

> It won't be faster by any means, but it should definitely be incorporated
> if any format changes are made (like Tom already suggested).
>
> I think it's important we gather at least 2 more things before making any
> calls:
> * Josh tests w/ cache aware patch, which should confirm cache aware is
> indeed prefered
> * Tests with toast hacked to use lz4 instead, which might ease any
> decisions
>
>
> --
> Arthur Silva
>
>
>
> On Wed, Aug 27, 2014 at 12:53 AM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
>
>> On Tue, Aug 26, 2014 at 8:41 PM, Arthur Silva <arthurprs(at)gmail(dot)com>
>> wrote:
>> > The difference is small but I's definitely faster, which makes sense
>> since
>> > cache line misses are probably slightly reduced.
>> > As in the previous runs, I ran the query a dozen times and took the
>> average
>> > after excluding runs with a high deviation.
>>
>> I'm not surprised that it hasn't beaten HEAD. I haven't studied the
>> problem in detail, but I don't think that the "cache awareness" of the
>> new revision is necessarily a distinct advantage.
>>
>> --
>> Peter Geoghegan
>>
>
>
I'm attaching a quick-n-dirty patch that uses lz4 compression instead of
pglz in case someone wants to experiment with it. Seems to work in my test
env, I'll make more tests when I get home.

PS: gotta love gmail fixed defaults of top-posting...

On 08/12/2014 10:58 AM, Robert Haas wrote:
> What would really be ideal here is if the JSON code could inform the
> toast compression code "this many initial bytes are likely
> incompressible, just pass them through without trying, and then start
> compressing at byte N", where N is the byte following the TOC. But I
> don't know that there's a reasonable way to implement that.
>

Sorry, being late for the party.

Anyhow, this strikes me as a good basic direction of thought. But I
think we should put the burden on the data type, not on toast. To do
that data types could have an optional toast_hint_values() function,
which the toast code can call with the actual datum at hand and its
default parameter array. The hint values function then can modify that
parameter array, telling toast how much to skip, how hard to try (or not
at all) and so on. A data type specific function should know much better
how to figure out how compressible a particular datum may be.

Certainly nothing for 9.4, but it might require changing the toast API
in a different way than just handing it an oid and hard-coding the
JASONBOID case into toast for 9.4. If we are going to change the API, we
might as well do it right.

Regards,
Jan

--
Jan Wieck
Senior Software Engineer
http://slony.info

On 08/08/2014 10:21 AM, Andrew Dunstan wrote:
>
> On 08/07/2014 11:17 PM, Tom Lane wrote:
>> I looked into the issue reported in bug #11109. The problem appears to be
>> that jsonb's on-disk format is designed in such a way that the leading
>> portion of any JSON array or object will be fairly incompressible, because
>> it consists mostly of a strictly-increasing series of integer offsets.
>> This interacts poorly with the code in pglz_compress() that gives up if
>> it's found nothing compressible in the first first_success_by bytes of a
>> value-to-be-compressed. (first_success_by is 1024 in the default set of
>> compression parameters.)
>
> [snip]
>
>> There is plenty of compressible data once we get into the repetitive
>> strings in the payload part --- but that starts at offset 944, and up to
>> that point there is nothing that pg_lzcompress can get a handle on. There
>> are, by definition, no sequences of 4 or more repeated bytes in that area.
>> I think in principle pg_lzcompress could decide to compress the 3-byte
>> sequences consisting of the high-order 24 bits of each offset; but it
>> doesn't choose to do so, probably because of the way its lookup hash table
>> works:
>>
>> * pglz_hist_idx -
>> *
>> * Computes the history table slot for the lookup by the next 4
>> * characters in the input.
>> *
>> * NB: because we use the next 4 characters, we are not guaranteed to
>> * find 3-character matches; they very possibly will be in the wrong
>> * hash list. This seems an acceptable tradeoff for spreading out the
>> * hash keys more.
>>
>> For jsonb header data, the "next 4 characters" are *always* different, so
>> only a chance hash collision can result in a match. There is therefore a
>> pretty good chance that no compression will occur before it gives up
>> because of first_success_by.
>>
>> I'm not sure if there is any easy fix for this. We could possibly change
>> the default first_success_by value, but I think that'd just be postponing
>> the problem to larger jsonb objects/arrays, and it would hurt performance
>> for genuinely incompressible data. A somewhat painful, but not yet
>> out-of-the-question, alternative is to change the jsonb on-disk
>> representation. Perhaps the JEntry array could be defined as containing
>> element lengths instead of element ending offsets. Not sure though if
>> that would break binary searching for JSON object keys.
>>
>>
>
>
> Ouch.
>
> Back when this structure was first presented at pgCon 2013, I wondered
> if we shouldn't extract the strings into a dictionary, because of key
> repetition, and convinced myself that this shouldn't be necessary
> because in significant cases TOAST would take care of it.
>
> Maybe we should have pglz_compress() look at the *last* 1024 bytes if it
> can't find anything worth compressing in the first, for values larger
> than a certain size.
>
> It's worth noting that this is a fairly pathological case. AIUI the
> example you constructed has an array with 100k string elements. I don't
> think that's typical. So I suspect that unless I've misunderstood the
> statement of the problem we're going to find that almost all the jsonb
> we will be storing is still compressible.

I also think that a substantial part of the problem of coming up with a
"representative" data sample is because the size of the incompressible
data at the beginning is somewhat tied to the overall size of the datum
itself. This may or may not be true in any particular use case, but as a
general rule of thumb I would assume that the larger the JSONB document,
the larger the offset array at the beginning.

Would changing 1024 to a fraction of the datum length for the time being
give us enough room to come up with a proper solution for 9.5?

Regards,
Jan

--
Jan Wieck
Senior Software Engineer
http://slony.info

On 08/08/2014 11:18 AM, Tom Lane wrote:
> Andrew Dunstan <andrew(at)dunslane(dot)net> writes:
>> On 08/07/2014 11:17 PM, Tom Lane wrote:
>>> I looked into the issue reported in bug #11109. The problem appears to be
>>> that jsonb's on-disk format is designed in such a way that the leading
>>> portion of any JSON array or object will be fairly incompressible, because
>>> it consists mostly of a strictly-increasing series of integer offsets.
>
>> Ouch.
>
>> Back when this structure was first presented at pgCon 2013, I wondered
>> if we shouldn't extract the strings into a dictionary, because of key
>> repetition, and convinced myself that this shouldn't be necessary
>> because in significant cases TOAST would take care of it.
>
> That's not really the issue here, I think. The problem is that a
> relatively minor aspect of the representation, namely the choice to store
> a series of offsets rather than a series of lengths, produces
> nonrepetitive data even when the original input is repetitive.

This is only because the input data was exact copies of the same strings
over and over again. PGLZ can very well compress slightly less identical
strings of varying lengths too. Not as well, but well enough. But I
suspect such input data would make it fail again, even with lengths.

Regards,
Jan

--
Jan Wieck
Senior Software Engineer
http://slony.info