Re: Hash index inserts serialise on the metapage tuple counter

Hi all,

v3 attached, on 8628df8891a. 0001 is v2's patch, rebased and otherwise
unchanged. 0002 is the split and overflow work I said v2 was waiting
for.

With the counter off the insert path, the waits left in a growing index
were on overflow pages.

Linear hashing splits buckets in order, so the buckets not yet split in
a round fill past a page and each get an overflow page, which they give
back when they are split. That's about one overflow allocation and one
free per split. Allocating took the metapage lock twice and searched
the bitmap page under an exclusive lock; freeing took the metapage lock
to lower hashm_firstfree.

0002:

- Searches the bitmap pages using the cached metapage, under a share
lock, and locks a bitmap page exclusively only to claim a bit. Bits
for pages not yet added are set, so a free bit always stands for an
existing page, but the cached copy may not know the splitpoint a new
page is in; it is refreshed before claiming a bit past what it knows.

- Locks the metapage only when nothing is free: it searches all bitmap
pages again from the first, then extends the index by 64 overflow
pages at once, leaving 63 free in the bitmap. XLOG_HASH_ADD_OVFL_PAGE
gains a page count, and registers the metapage only when it changes.

- Frees without the metapage. hashm_firstfree now only says which
bitmap page a search starts at. A page freed in an earlier bitmap
page is found by the search under the metapage lock before the index
grows, so it waits, but is not lost. That only matters past 32768
overflow pages.

- Locks the metapage only before a bitmap page, never while holding one.

Lock wait time summed over all backends, 10-row inserts at 64 clients
for 20s (1280 backend-seconds), mean of two runs:

v2 v3
bitmap page, allocate 78 s 9 s
metapage, allocate 23 s 2 s
bitmap page, free 15 s 2 s
metapage, free 6 s 0
metapage, refresh cached copy - 3 s

The metapage is now taken for allocation about 3500 times in that run,
against 88000.

Throughput moved less than that I'd expected. Testing on the same
c7i.24xlarge as before (64 vCPUs), pgbench on the other 32, median of 3
runs interleaved across builds:

10 rows per INSERT
clients 16 32 64 128 256
master 14471 13156 11493 9916 8569
v2 194268 223750 200518 207735 192457
v3 201624 227470 208918 218516 200836
btree 173797 237869 237800 227532 215764

1 row per INSERT
clients 16 64 128 256
v2 529010 665727 687972 694518
v3 519737 669429 708545 700054
btree 513265 666375 711535 722497

0002 is worth 2-5% at 10 rows, and single-row inserts are level with
btree as before. At 64 clients hash is still 12% behind btree, and the
index isn't what limits it any more.

As an experiment, I took WAL out with an UNLOGGED table and index, and
0002 shows what it removed:

10 rows per INSERT, UNLOGGED, growing index
clients 32 64 128
v2 418742 487044 421342
v3 436612 563457 502093
btree 321013 309160 325910

With WAL, both are waiting on WAL insertion (58% of hash backends in
LWLock:WALInsert, 45% for btree), and hash writes about 5% more WAL per
row, mostly split page images. On an index that doesn't split during
the run (built on 64M rows, all but 1/64 deleted, vacuumed) hash and
btree are level and 0002 makes no difference: 242k/193k/165k TPS at
32/64/128 clients for v3, 239k/180k/168k for btree. Hash also loses
more than btree as wal_buffers grows (16MB: 206k vs 241k; 256MB: 140k vs
222k), with or without 0002.

I haven't chased that; it's not in the code these patches touch but this
might become a target for exploration in the future.

I also tried keeping the count in the metapage as an unlogged hint, with
splits carrying it to the standby. That gained 0-2% on top of 0002, and
a standby's count could fall behind by every insert since the last split
or VACUUM, so I dropped that idea.

The cost of 0002 is a little space: up to 63 overflow pages from the
last batch that aren't used yet. In the delete-heavy run I measured
that as an additional 41 pages (9410 against 9369); the other runs match
master.

With 27caf4ca5ae in, wal_consistency_checking=hash now passes on master,
so I ran v3 that way: a standby replaying 16 writers into two hash
indexes, a delete and VACUUM, more inserts and a CREATE INDEX reports no
inconsistency, and its rows, metapages and probes match the primary's.

0002 also adds a regression test, hash_overflow_pages, covering the
batch, reuse without growing, frees and reuse of freed pages.

0002 changes XLOG_HASH_ADD_OVFL_PAGE, so like 0001 it's master-only and
needs an XLOG_PAGE_MAGIC bump at some point.

best.

-greg