Re: SPGist "triple parity" concept doesn't work

Greg Stark <stark(at)mit(dot)edu> writes:
> On Thu, Jun 6, 2013 at 10:46 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> : This rule guarantees that tuples on page M will have no children on page N,
>> : since (M+1) mod 3 != N mod 3.

> Even if the invariant was maintained why doesn't that just mean you
> need three concurrent inserts to create a deadlock?

Hm, good point. That reinforces my feeling that the page-number-based
approach isn't workable as a guarantee; though we might want to keep
that layout rule as a heuristic that would help reduce contention.

I thought a little bit about whether we could drop the requirement of
locking two tree levels during insertion descent, or at least recover
from deadlock if it did occur. One simple fix would be to do a
ConditionalLockBuffer on the child level, and if it fails, just abandon
the insertion attempt and start over. However that could lead to a lot
of wasted work when there's contention, so it's not terribly attractive
as-is. Another line of thought is to lock just the single parent tuple,
not its whole page, when descending --- then we can't deadlock unless
there are actual circularities in the index. We'd probably have to use
a heavyweight lock for that, which might be problematic for performance,
and I'm not exactly sure about timing of when to take that lock relative
to acquiring the page's buffer lock (which we'd still need). There are
probably some other ways to attack this.

regards, tom lane