Re: Hash index inserts serialise on the metapage tuple counter

> While looking at hash index behaviour under concurrency I found that
> single-row insert throughput stops scaling at a fairly low client count
> and then goes backwards, where an equivalent btree keeps scaling. The
> cause is the metapage, and I'd like to float a fix before writing a
> finished patch.
>
> The problem is that _hash_doinsert() takes an exclusive buffer lock on
> the metapage for every insert, solely to run:
>
> metap->hashm_ntuples += 1;
> do_expand = metap->hashm_ntuples >
> (double) metap->hashm_ffactor * (metap->hashm_maxbucket + 1);
>
> and to register the metapage in the insert's WAL record. Every inserter
> into the index therefore serialises on that one buffer. The v10
> metapage cache (293e24e5078) removed the metapage read from the lookup
> path, but the write on insert was left in place; Mithun Cy noted at the
> time that inserts still touch the metapage every time [1], and it
> doesn't seem to have been revisited.
>
> I wanted to be sure, so I did some measurements on a c7i.8xlarge (32
> vCPU, one NUMA node), data on tmpfs, synchronous_commit off,
> shared_buffers 16GB. pgbench, one single-row INSERT of a random int8
> per transaction, index pre-loaded with 2M rows, 20s per point, three
> runs averaged:
>
> clients 1 16 32 64
> btree 44k 514k 547k 597k
> hash 44k 364k 299k 273k
>
> Hash peaks around 16 clients and declines from there. Sampling
> pg_stat_activity at 32 clients, ~68% of hash inserter samples are in the
> buffer-content-lock wait; btree shows none.
>
> Timing LockBuffer(EXCLUSIVE) per buffer with a uprobe, one buffer
> accounts for 99.9% of the exclusive- lock wait time, and pg_buffercache
> maps it to block 0 of the index, the metapage.

+1 on fixing this.

> So here's what I propose to do, don't touch the metapage on most
> inserts. Each backend accumulates its own insert count for a given
> index and only takes the metapage lock once every N inserts, adding the
> batch and testing the split threshold then. hashm_ntuples only drives
> split timing, and VACUUM already recomputes it from scratch
> (hashbulkdelete -> hashm_ntuples = num_index_tuples), so a slightly
> stale counter costs at most a somewhat delayed split, never correctness.

The recomputed count is only used if no split or insert has occurred
since VACUUM started its scan. If there's constant churn on the table,
it can happen that hashm_ntuples is not recomputed for many VACUUM runs.

Beyond that, the batching benefit degrades as concurrency increases: to
maintain the same bound on the aggregate counting error, the batch size
must decrease inversely with the number of inserting backends, forcing
more frequent metapage updates precisely when contention is highest.
Keeping the batch size fixed instead allows more inserts to accumulate
unreported across backends, leaving the metapage count increasingly
stale as concurrency grows.

> With a proof-of-concept doing exactly this (batch size 64, attached),
> the hash numbers become:
>
> clients 1 16 32 64
> hash 44k 533k 557k 604k
>
> with that change hash now scales like btree (btree was 597k at 64).
> Regression and isolation tests pass; a streaming standby with 16
> concurrent inserters and splits replayed to the same hashm_ntuples and
> maxbucket as the primary, and index probes on the standby found every
> row.

Nice speedup!

> I was chasing something else when I found this, so the attached patch is
> a proof of concept, not a finished submission. It makes the point and
> the numbers are real, but it cuts corners I'd want the list's opinion on
> before building the real thing:
>
> - Where should the pending per-backend count live? The POC uses a
> fixed-size backend-local array keyed by relid, and simply loses the
> pending count when the backend exits (VACUUM fixes hashm_ntuples
> later). A cleaner home might be the relcache entry, flushed on
> relcache invalidation and at transaction end, but that has its own
> edge cases (invalidation dropping the count, subxact abort).
>
> - How stale may the split trigger be? With per-backend batching the
> index can run up to batch_size * nbackends tuples past the fill
> factor before anyone splits. That is self-correcting (every
> inserter that crosses the threshold tries to split), but it does
> mean the index can briefly carry more overflow pages than today.

I don't like the batched counting too much because:

1. It's involved to do properly as you pointed out yourself already.
2. If we don't care about the details such as flushing residual counter
increments, the splitting behavior is workload dependent and by that
non-deterministic. Which makes it hard to reason about when
investigating problems.
3. It has the inverse scaling problem as described above.

> - Is there any appetite for removing the global counter from the hot
> path entirely instead, and triggering a split from local information
> the inserter already has (e.g. having had to add or walk an overflow
> page)? That would also make inserts that don't split read-only on
> the metapage. It's a bigger change and I haven't prototyped it yet.
If we cannot come up with an alternative signal, the batched counting is
better than dying from lock contention. But I'm hoping we can do
something else.

Maybe using the number of overflow pages vs the number of bucket pages
would work okay enough? Of course, deletes will leave partially filled
pages and splitting overflow pages full of unique values won't cut down
on the number of overflow pages when splitting.

--
David Geier