Re: Making all nbtree entries unique by having heap TIDs participate in comparisons

On Fri, Nov 2, 2018 at 3:06 AM Andrey Lepikhov
<a(dot)lepikhov(at)postgrespro(dot)ru> wrote:
> Documentation is full and clear. All non-trivial logic is commented
> accurately.

Glad you think so.

I had the opportunity to discuss this patch at length with Heikki
during pgConf.EU. I don't want to speak on his behalf, but I will say
that he seemed to understand all aspects of the patch series, and
seemed generally well disposed towards the high level design. The
high-level design is the most important aspect -- B-Trees can be
optimized in many ways, all at once, and we must be sure to come up
with something that enables most or all of them. I really care about
the long term perspective.

That conversation with Heikki eventually turned into a conversation
about reimplementing GIN using the nbtree code, which is actually
related to my patch series (sorted on heap TID is the first step to
optional run length encoding for duplicates). Heikki seemed to think
that we can throw out a lot of the optimizations within GIN, and add a
few new ones to nbtree, while still coming out ahead. This made the
general nbtree-as-GIN idea (which we've been talking about casually
for years) seem a lot more realistic to me. Anyway, he requested that
I support this long term goal by getting rid of the DESC TID sort
order thing -- that breaks GIN-style TID compression. It also
increases the WAL volume unnecessarily when a page is split that
contains all duplicates.

The DESC heap TID sort order thing probably needs to go. I'll probably
have to go fix the regression test failures that occur when ASC heap
TID order is used. (Technically those failures are a pre-existing
problem, a problem that I mask by using DESC order...which is weird.
The problem is masked in the master branch by accidental behaviors
around nbtree duplicates, which is something that deserves to die.
DESC order is closer to the accidental current behavior.)

> Patch applies cleanly on top of current master. Regression tests passed
> and my "Retail Indextuple deletion" use cases works without mistakes.

Cool.

> New BTScanInsert structure reduces parameters list of many functions and
> look fine. But it contains some optimization part ('restorebinsrch'
> field et al.). It is used very locally in the code -
> _bt_findinsertloc()->_bt_binsrch() routines calling. May be you localize
> this logic into separate struct, which will passed to _bt_binsrch() as
> pointer. Another routines may pass NULL value to this routine. It is may
> simplify usability of the struct.

Hmm. I see your point. I did it that way because the knowledge of
having cached an upper and lower bound for a binary search of a leaf
page needs to last for a relatively long time. I'll look into it
again, though.

> Due to the optimization the _bt_binsrch() size has grown twice. May be
> you move this to some service routine?

Maybe. There are some tricky details that seem to work against it.
I'll see if it's possible to polish that some more, though.

--
Peter Geoghegan