Re: Hash index inserts serialise on the metapage tuple counter

>> 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.
>
> Right, stated plainly: hashm_ntuples is already allowed to drift from the true
> tuple count between VACUUMs, batching or not. What VACUUM guarantees is a
> recompute at the end of a scan that saw no concurrent split/insert, not a bound
> on staleness under churn. So the counter is not a reliable tuple count today;
> its only consumer is the fill-factor test that decides when to split. My
> change makes it drift a bit more, in a direction that only delays splits. It
> doesn't introduce a new correctness dependency, because there isn't one to
> break.

Agreed, that this cannot cause any incorrectness issues.

>> 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 [...]
>
> This is a fair hit, but I think it rests on wanting a bounded counting error,
> and I'm not sure we need one. The count exists to time a split. A split is
> not a deadline; it's "the buckets are getting full, add more". If the index
> runs batch_size * nbackends tuples past the fill factor before someone splits,
> the cost is some extra overflow pages until the next inserter crosses the
> threshold and splits so self-correcting, and the fill factor is a soft target
> anyway. So I'd rather keep the batch fixed and accept a staleness that grows
> with concurrency than shrink the batch and reintroduce the contention at high
> client counts, which is the whole thing we're trying to remove.

I guess the question is if with too few / too many backends you're not
splitting too frequently / too infrequently or you're back to contention
problems.

> Where I do agree with you is the determinism point:
>
>> 2. [...] the splitting behavior is workload dependent and by that
>> non-deterministic. Which makes it hard to reason about [...]
>
> Yes. Split timing becoming a function of how many backends happened to be
> inserting is the part of batched counting I like least, more than the storage
> mess. It makes a reproduction depend on client count, which is exactly the
> kind of thing that turns a bug report into a week of "works here".

Exactly. Any alternative solution we come up with should be checked
against not having that problem.

>> Maybe using the number of overflow pages vs the number of bucket pages
>> would work okay enough?
>
> I tend to agree with this because it replaces a global counter with information
> the inserter already has in hand. An inserter that has to allocate or walk
> onto an overflow page for its bucket already knows that bucket is over-full;
> that's a local, lock-free signal that this bucket (hence, on average, the
> index) wants more buckets. No metapage write on the common path at all.

I thought about the total number of overflow pages. So we would need a
counter but one that changes less frequently than the row count.

> Your two objections to it are the real ones, though:
>
>> deletes will leave partially filled pages
>
> So overflow-page count lags downward after deletes: the index can look
> over-full and keep splitting when it isn't. But a hash index already doesn't
> reclaim buckets on delete (maxbucket never decreases) so "splits a bit eagerly
> after a delete-heavy phase" is closer to today's behaviour than the tuple
> counter is. I'd want to measure this first.
>
>> splitting overflow pages full of unique values won't cut down on the
>> number of overflow pages when splitting
>
> This is the one that actually worries me: if a bucket's overflow is caused by
> many duplicate keys (all hashing to the same bucket), splitting won't relieve
> it (the dups stay together) so an overflow-triggered split loops, splitting
> again and again without reducing overflow. The current code has the same
> pathology in slower motion (ntuples keeps rising, it keeps splitting), but a
> local overflow trigger could make it tighter. A guard would be needed: don't
> re-trigger on a bucket that didn't actually shed overflow across its last
> split, or cap splits-per-insert.

How about excluding the number of overflow pages that exists because of
duplicates? For non-duplicates, skew cannot realistically occur (thanks
to the uniform hashing). So the duplicate case is the only case to consider.

We could keep a counter for the duplicates-only overflow pages in the
meta page. Such counter would only change very infrequently. On delete,
we would consider duplicates-only overflow pages normal overflow pages
again and decrement the counter.

> So I think the plan is:
>
> 1. Settle that the counter's only job is approximate split timing (above).

Yes.

> 2. Prototype the overflow-vs-bucket signal and measure it on the same
> workload, specifically the delete-heavy and high-duplicate cases, which
> are where it can misbehave.

Which workload are you planning to test with?

> 3. Keep the batched counter in my back pocket as the fallback if the
> overflow signal can't be made to behave, it's not elegant but it does
> remove the contention.

Yes.

> I'll build (2) and report numbers, including the two adversarial cases, so
> we're comparing measured behaviour rather than intuitions. If the overflow
> signal holds up it's the better answer for the reasons you give.
Sounds good.

Consider doing something about the duplicates-only pages. It would be
interesting to contrast such a variant against one that simply ignores
the fact that duplicates-only pages cannot be split.

A workload that creates duplicates for every entry will be the
worst-case. Duplicates for a single entry would probably not matter much.

--
David Geier