pgsql: Refactor nbtree insertion scankeys.

Refactor nbtree insertion scankeys.

Use dedicated struct to represent nbtree insertion scan keys. Having a
dedicated struct makes the difference between search type scankeys and
insertion scankeys a lot clearer, and simplifies the signature of
several related functions. This is based on a suggestion by Andrey
Lepikhov.

Streamline how unique index insertions cache binary search progress.
Cache the state of in-progress binary searches within _bt_check_unique()
for later instead of having callers avoid repeating the binary search in
an ad-hoc manner. This makes it easy to add a new optimization:
_bt_check_unique() now falls out of its loop immediately in the common
case where it's already clear that there couldn't possibly be a
duplicate.

The new _bt_check_unique() scheme makes it a lot easier to manage cached
binary search effort afterwards, from within _bt_findinsertloc(). This
is needed for the upcoming patch to make nbtree tuples unique by
treating heap TID as a final tiebreaker column. Unique key binary
searches need to restore lower and upper bounds. They cannot simply
continue to use the >= lower bound as the offset to insert at, because
the heap TID tiebreaker column must be used in comparisons for the
restored binary search (unlike the original _bt_check_unique() binary
search, where scankey's heap TID column must be omitted).

Author: Peter Geoghegan, Heikki Linnakangas
Reviewed-By: Heikki Linnakangas, Andrey Lepikhov
Discussion: https://postgr.es/m/CAH2-WzmE6AhUdk9NdWBf4K3HjWXZBX3+umC7mH7+WDrKcRtsOw@mail.gmail.com

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/e5adcb789d80ba565ccacb1ed4341a7c29085238

Modified Files
--------------
contrib/amcheck/verify_nbtree.c | 52 ++---
src/backend/access/nbtree/README | 29 +--
src/backend/access/nbtree/nbtinsert.c | 400 +++++++++++++++++++---------------
src/backend/access/nbtree/nbtpage.c | 12 +-
src/backend/access/nbtree/nbtsearch.c | 227 +++++++++++++------
src/backend/access/nbtree/nbtsort.c | 8 +-
src/backend/access/nbtree/nbtutils.c | 94 +++-----
src/backend/utils/sort/tuplesort.c | 16 +-
src/include/access/nbtree.h | 78 +++++--
9 files changed, 529 insertions(+), 387 deletions(-)