>> 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
