MIME-Version: 1.0
Content-Type: multipart/mixed;
 boundary="=_3653c22c96a8279816914bd7f3ae15ef"
Content-Transfer-Encoding: 7bit
Date: Tue, 10 Aug 2021 11:52:59 +0300
From: Yura Sokolov <y.sokolov@postgrespro.ru>
To: pgsql-hackers@lists.postgresql.org
Cc: Andres Freund <andres@anarazel.de>, Tomas Vondra
 <tomas.vondra@2ndquadrant.com>
Subject: Bug in huge simplehash
User-Agent: Roundcube Webmail/1.4.0
Message-ID: <b1f7f32737c3438136f64b26f4852b96@postgrespro.ru>
Archived-At: 
 <https://www.postgresql.org/message-id/b1f7f32737c3438136f64b26f4852b96%40postgrespro.ru>
Precedence: bulk

--=_3653c22c96a8279816914bd7f3ae15ef
Content-Transfer-Encoding: 7bit
Content-Type: text/plain; charset=US-ASCII;
 format=flowed

Good day, hackers.

Our client caught process stuck in tuplehash_grow. There was a query 
like
`select ts, count(*) from really_huge_partitioned_table group by ts`, 
and
planner decided to use hash aggregation.

Backtrace shows that oldsize were 2147483648 at the moment. While 
newsize
were optimized, looks like it were SH_MAX_SIZE.

#0  0x0000000000603d0c in tuplehash_grow (tb=0x7f18c3c284c8, 
newsize=<optimized out>) at ../../../src/include/lib/simplehash.h:457
         hash = 2147483654
         startelem = 1
         curelem = 1
         oldentry = 0x7f00c299e0d8
         oldsize = 2147483648
         olddata = 0x7f00c299e048
         newdata = 0x32e0448
         i = 6
         copyelem = 6

EXPLAIN shows that there are 2604186278 rows in all partitions, but 
planner
thinks there will be only 200 unique rows after group by. Looks like we 
was
mistaken.

  Finalize GroupAggregate  (cost=154211885.42..154211936.09 rows=200 
width=16)
     Group Key: really_huge_partitioned_table.ts
     ->  Gather Merge  (cost=154211885.42..154211932.09 rows=400 
width=16)
           Workers Planned: 2
           ->  Sort  (cost=154210885.39..154210885.89 rows=200 width=16)
                 Sort Key: really_huge_partitioned_table.ts
                 ->  Partial HashAggregate  
(cost=154210875.75..154210877.75 rows=200 width=16)
                       Group Key: really_huge_partitioned_table.ts
                       ->  Append  (cost=0.43..141189944.36 
rows=2604186278 width=8)
                             ->  Parallel Index Only Scan using 
really_huge_partitioned_table_001_idx2 on 
really_huge_partitioned_table_001  (cost=0.43..108117.92 rows=2236977 
width=8)
                             ->  Parallel Index Only Scan using 
really_huge_partitioned_table_002_idx2 on 
really_huge_partitioned_table_002  (cost=0.43..114928.19 rows=2377989 
width=8)
                             .... and more than 400 partitions more

After some investigation I found bug that is present in simplehash from 
its
beginning:

- sizemask is set only in SH_COMPUTE_PARAMETERS . And it is set in this 
way:

         /* now set size */
         tb->size = size;

         if (tb->size == SH_MAX_SIZE)
                 tb->sizemask = 0;
         else
                 tb->sizemask = tb->size - 1;

   that means, when we are resizing to SH_MAX_SIZE, sizemask becomes 
zero.

- then sizemask is used to SH_INITIAL_BUCKET and SH_NEXT to compute 
initial and
   next position:

   SH_INITIAL_BUCKET(SH_TYPE * tb, uint32 hash)
     return hash & tb->sizemask;
   SH_NEXT(SH_TYPE * tb, uint32 curelem, uint32 startelem)
     curelem = (curelem + 1) & tb->sizemask;

- and then SH_GROW stuck in element placing loop:

   startelem = SH_INITIAL_BUCKET(tb, hash);
   curelem = startelem;
   while (true)
     curelem = SH_NEXT(tb, curelem, startelem);

There is Assert(curelem != startelem) in SH_NEXT, but since no one test 
it
with 2 billion elements, it were not triggered. And Assert is not 
compiled
in production code.

Attached patch fixes it with removing condition and type casting:

         /* now set size */
         tb->size = size;
         tb->sizemask = (uint32)(size - 1);


OOOOOOPS

While writting this letter, I looke at newdata in the frame of 
tuplehash_grow:

     newdata = 0x32e0448

It is bellow 4GB border. Allocator does not allocate many-gigabytes 
chunks
(and we certainly need 96GB in this case) in sub 4GB address space. 
Because
mmap doesn't do this.

I went to check SH_GROW and.... It is `SH_GROW(SH_TYPE *tb, uint32 
newsize)`
:-(((
Therefore when `tb->size == SH_MAX_SIZE/2` and we call `SH_GROW(tb, 
tb->size * 2)`,
then SH_GROW(tb, 0) is called due to truncation.
And SH_COMPUTE_PARAMETERS is also accepts `uint32 newsize`.

Ahh... ok, patch is updated to fix this as well.


regards.

-----

Yura Sokolov
y.sokolov@postgrespro.ru
funny.falcon@gmail.com
--=_3653c22c96a8279816914bd7f3ae15ef
Content-Transfer-Encoding: base64
Content-Type: text/x-diff;
 name=0001-Fix-new-size-and-sizemask-computaton-in-simplehash.h.patch
Content-Disposition: attachment;
 filename=0001-Fix-new-size-and-sizemask-computaton-in-simplehash.h.patch;
 size=1472

RnJvbSBhODI4M2QzYTE3YzYzMGE2NWUxYjQyZjg2MTdlMDc4NzNhMzBmYmM3IE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiBZdXJhIFNva29sb3YgPHkuc29rb2xvdkBwb3N0Z3Jlc3Byby5y
dT4KRGF0ZTogVHVlLCAxMCBBdWcgMjAyMSAxMTo1MToxNiArMDMwMApTdWJqZWN0OiBbUEFUQ0hd
IEZpeCBuZXcgc2l6ZSBhbmQgc2l6ZW1hc2sgY29tcHV0YXRvbiBpbiBzaW1wbGVoYXNoLmgKCkZp
eCBjb3VwbGUgb2YgMzIvNjRiaXQgcmVsYXRlZCBlcnJvcnMgaW4gc2ltcGxlaGFzaC5oOgotIHNp
emUgb2YgU0hfR1JPVyBhbmQgU0hfQ09NUFVURV9QQVJBTUVURVJTIGFyZ3VtZW50cwotIGNvbXB1
dGF0aW9uIG9mIHRiLT5zaXplbWFzay4KLS0tCiBzcmMvaW5jbHVkZS9saWIvc2ltcGxlaGFzaC5o
IHwgMTAgKysrLS0tLS0tLQogMSBmaWxlIGNoYW5nZWQsIDMgaW5zZXJ0aW9ucygrKSwgNyBkZWxl
dGlvbnMoLSkKCmRpZmYgLS1naXQgYS9zcmMvaW5jbHVkZS9saWIvc2ltcGxlaGFzaC5oIGIvc3Jj
L2luY2x1ZGUvbGliL3NpbXBsZWhhc2guaAppbmRleCBkYTUxNzgxZTk4ZS4uMjI4NzYwMWNmYTEg
MTAwNjQ0Ci0tLSBhL3NyYy9pbmNsdWRlL2xpYi9zaW1wbGVoYXNoLmgKKysrIGIvc3JjL2luY2x1
ZGUvbGliL3NpbXBsZWhhc2guaApAQCAtMzAyLDcgKzMwMiw3IEBAIFNIX1NDT1BFIHZvaWQgU0hf
U1RBVChTSF9UWVBFICogdGIpOwogICogdGhlIGhhc2h0YWJsZS4KICAqLwogc3RhdGljIGlubGlu
ZSB2b2lkCi1TSF9DT01QVVRFX1BBUkFNRVRFUlMoU0hfVFlQRSAqIHRiLCB1aW50MzIgbmV3c2l6
ZSkKK1NIX0NPTVBVVEVfUEFSQU1FVEVSUyhTSF9UWVBFICogdGIsIHVpbnQ2NCBuZXdzaXplKQog
ewogCXVpbnQ2NAkJc2l6ZTsKIApAQCAtMzIyLDExICszMjIsNyBAQCBTSF9DT01QVVRFX1BBUkFN
RVRFUlMoU0hfVFlQRSAqIHRiLCB1aW50MzIgbmV3c2l6ZSkKIAogCS8qIG5vdyBzZXQgc2l6ZSAq
LwogCXRiLT5zaXplID0gc2l6ZTsKLQotCWlmICh0Yi0+c2l6ZSA9PSBTSF9NQVhfU0laRSkKLQkJ
dGItPnNpemVtYXNrID0gMDsKLQllbHNlCi0JCXRiLT5zaXplbWFzayA9IHRiLT5zaXplIC0gMTsK
Kwl0Yi0+c2l6ZW1hc2sgPSAodWludDMyKShzaXplIC0gMSk7CiAKIAkvKgogCSAqIENvbXB1dGUg
dGhlIG5leHQgdGhyZXNob2xkIGF0IHdoaWNoIHdlIG5lZWQgdG8gZ3JvdyB0aGUgaGFzaCB0YWJs
ZQpAQCAtNDc2LDcgKzQ3Miw3IEBAIFNIX1JFU0VUKFNIX1RZUEUgKiB0YikKICAqIHBlcmZvcm1h
bmNlLXdpc2UsIHdoZW4ga25vd24gYXQgc29tZSBwb2ludC4KICAqLwogU0hfU0NPUEUgdm9pZAot
U0hfR1JPVyhTSF9UWVBFICogdGIsIHVpbnQzMiBuZXdzaXplKQorU0hfR1JPVyhTSF9UWVBFICog
dGIsIHVpbnQ2NCBuZXdzaXplKQogewogCXVpbnQ2NAkJb2xkc2l6ZSA9IHRiLT5zaXplOwogCVNI
X0VMRU1FTlRfVFlQRSAqb2xkZGF0YSA9IHRiLT5kYXRhOwotLSAKMi4zMi4wCgo=
--=_3653c22c96a8279816914bd7f3ae15ef--