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

On Fri, Mar 22, 2019 at 2:15 PM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> On Thu, Mar 21, 2019 at 10:28 AM Peter Geoghegan <pg(at)bowt(dot)ie> wrote:
> > I'll likely push the remaining two patches on Sunday or Monday.
>
> I noticed that if I initidb and run "make installcheck" with and
> without the "split after new tuple" optimization patch, the largest
> system catalog indexes shrink quite noticeably:

I pushed this final patch a week ago, as commit f21668f3, concluding
work on integrating the patch series.

I have some closing thoughts that I would like to close out the
project on. I was casually discussing this project over IM with Robert
the other day. I was asked a question I'd often asked myself about the
"split after new item" heuristics: What if you're wrong? What if some
"black swan" type workload fools your heuristics into bloating an
index uncontrollably?

I gave an answer to his question that may have seemed kind of
inscrutable. My intuition about the worst case for the heuristics is
based on its similarity to the worst case for quicksort. Any
real-world instance of quicksort going quadratic is essentially a case
where we *consistently* do the wrong thing when selecting a pivot. A
random pivot selection will still perform reasonably well, because
we'll still choose the median pivot on average. A malicious actor will
always be able to fool any quicksort implementation into going
quadratic [1] in certain circumstances. We're defending against
Murphy, not Machiavelli, though, so that's okay.

I think that I can produce a more tangible argument than this, though.
Attached patch removes every heuristic that limits the application of
the "split after new item" optimization (it doesn't force the
optimization in the case of rightmost splits, or in the case where the
new item happens to be first on the page, since caller isn't prepared
for that). This is an attempt to come up with a wildly exaggerated
worst case. Nevertheless, the consequences are not actually all that
bad. Summary:

* The "UK land registry" test case that I leaned on a lot for the
patch has a final index that's about 1% larger. However, it was about
16% smaller compared to Postgres without the patch, so this is not a
problem.

* Most of the TPC-C indexes are actually slightly smaller, because we
didn't quite go as far as we could have (TPC-C strongly rewards this
optimization). 8 out of the 10 indexes are either smaller or
unchanged. The customer name index is about 28% larger, though. The
oorder table index is also about 28% larger.

* TPC-E never benefits from the "split after new item" optimization,
and yet the picture isn't so bad here either. The holding history PK
is about 40% bigger, which is quite bad, and the biggest regression
overall. However, in other affected cases indexes are about 15%
larger, which is not that bad.

Also attached are the regressions from my test suite in the form of
diff files -- these are the full details of the regression, just in
case that's interesting to somebody.

This isn't the final word. I'm not asking anybody to accept with total
certainty that there can never be a "black swan" workload that the
heuristics consistently mishandle, leading to pathological
performance. However, I think it's fair to say that the risk of that
happening has been managed well. The attached test patch literally
removes any restraint on applying the optimization, and yet we
arguably do no worse than Postgres 11 would overall.

Once again, I would like to thank my collaborators for all their help,
especially Heikki.

[1] https://www.cs.dartmouth.edu/~doug/mdmspe.pdf
--
Peter Geoghegan