Re: Locking B-tree leafs immediately in exclusive mode

On Mon, Jun 11, 2018 at 9:30 AM, Alexander Korotkov
<a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> On Mon, Jun 11, 2018 at 1:06 PM Simon Riggs <simon(at)2ndquadrant(dot)com> wrote:
>> It's a good idea. How does it perform with many duplicate entries?

I agree that this is a good idea. It independently occurred to me to
do this. The L&Y algorithm doesn't take a position on this at all,
supposing that *no* locks are needed at all (that's why I recommend
people skip L&Y and just read the Lanin & Shasha paper -- L&Y is
unnecessarily confusing). This idea seems relatively low risk.

> Our B-tree is currently maintaining duplicates unordered. So, during insertion
> we can traverse rightlinks in order to find page, which would fit new
> index tuple.
> However, in this case we're traversing pages in exclusive lock mode, and
> that happens already after re-lock. _bt_search() doesn't do anything with that.
> So, I assume there shouldn't be any degradation in the case of many
> duplicate entries.

BTW, I have a prototype patch that makes the keys at the leaf level
unique. It is actually an implementation of nbtree suffix truncation
that sometimes *adds* a new attribute in pivot tuples, rather than
truncating away non-distinguishing attributes -- it adds a special
heap TID attribute when it must. The patch typically increases fan-in,
of course, but the real goal was to make all entries at the leaf level
truly unique, as L&Y intended (we cannot do it without suffix
truncation because that will kill fan-in). My prototype has full
amcheck coverage, which really helped me gain confidence in my
approach.

There are still big problems with my patch, though. It seems to hurt
performance more often than it helps when there is a lot of
contention, so as things stand I don't see a path to making it
commitable. I am still going to clean it up some more and post it to
-hackers, though. I still think it's quite interesting. I am not
pursuing it much further now because it seems like my timing is bad --
not because it seems like a bad idea. I can imagine something like
zheap making this patch important again. I can also imagine someone
seeing something that I missed.

--
Peter Geoghegan