/*-------------------------------------------------------------------------

 *

 * nbtsplitloc.c

 *    Choose split point code for Postgres btree implementation.

 *

 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group

 * Portions Copyright (c) 1994, Regents of the University of California

 *

 *

 * IDENTIFICATION

 *    src/backend/access/nbtree/nbtsplitloc.c

 *

 *-------------------------------------------------------------------------

 */

#include "postgres.h"

#include "access/nbtree.h"

#include "access/tableam.h"

#include "common/int.h"

typedef enum

{

  /* strategy for searching through materialized list of split points */

  SPLIT_DEFAULT,        /* give some weight to truncation */

  SPLIT_MANY_DUPLICATES,    /* find minimally distinguishing point */

  SPLIT_SINGLE_VALUE,     /* leave left page almost full */

} FindSplitStrat;

typedef struct

{

  /* details of free space left by split */

  int16   curdelta;   /* current leftfree/rightfree delta */

  int16   leftfree;   /* space left on left page post-split */

  int16   rightfree;    /* space left on right page post-split */

  /* split point identifying fields (returned by _bt_findsplitloc) */

  OffsetNumber firstrightoff; /* first origpage item on rightpage */

  bool    newitemonleft;  /* new item goes on left, or right? */

} SplitPoint;

typedef struct

{

  /* context data for _bt_recsplitloc */

  Relation  rel;      /* index relation */

  Page    origpage;   /* page undergoing split */

  IndexTuple  newitem;    /* new item (cause of page split) */

  Size    newitemsz;    /* size of newitem (includes line pointer) */

  bool    is_leaf;    /* T if splitting a leaf page */

  bool    is_rightmost; /* T if splitting rightmost page on level */

  OffsetNumber newitemoff;  /* where the new item is to be inserted */

  int     leftspace;    /* space available for items on left page */

  int     rightspace;   /* space available for items on right page */

  int     olddataitemstotal;  /* space taken by old items */

  Size    minfirstrightsz;  /* smallest firstright size */

  /* candidate split point data */

  int     maxsplits;    /* maximum number of splits */

  int     nsplits;    /* current number of splits */

  SplitPoint *splits;     /* all candidate split points for page */

  int     interval;   /* current range of acceptable split points */

} FindSplitData;

static void _bt_recsplitloc(FindSplitData *state,

              OffsetNumber firstrightoff, bool newitemonleft,

              int olddataitemstoleft,

              Size firstrightofforigpagetuplesz);

static void _bt_deltasortsplits(FindSplitData *state, double fillfactormult,

                bool usemult);

static int  _bt_splitcmp(const void *arg1, const void *arg2);

static bool _bt_afternewitemoff(FindSplitData *state, OffsetNumber maxoff,

                int leaffillfactor, bool *usemult);

static bool _bt_adjacenthtid(ItemPointer lowhtid, ItemPointer highhtid);

static OffsetNumber _bt_bestsplitloc(FindSplitData *state, int perfectpenalty,

                   bool *newitemonleft, FindSplitStrat strategy);

static int  _bt_defaultinterval(FindSplitData *state);

static int  _bt_strategy(FindSplitData *state, SplitPoint *leftpage,

             SplitPoint *rightpage, FindSplitStrat *strategy);

static void _bt_interval_edges(FindSplitData *state,

                 SplitPoint **leftinterval, SplitPoint **rightinterval);

static inline int _bt_split_penalty(FindSplitData *state, SplitPoint *split);

static inline IndexTuple _bt_split_lastleft(FindSplitData *state,

                      SplitPoint *split);

static inline IndexTuple _bt_split_firstright(FindSplitData *state,

                        SplitPoint *split);

/*

 *  _bt_findsplitloc() -- find an appropriate place to split a page.

 *

 * The main goal here is to equalize the free space that will be on each

 * split page, *after accounting for the inserted tuple*.  (If we fail to

 * account for it, we might find ourselves with too little room on the page

 * that it needs to go into!)

 *

 * If the page is the rightmost page on its level, we instead try to arrange

 * to leave the left split page fillfactor% full.  In this way, when we are

 * inserting successively increasing keys (consider sequences, timestamps,

 * etc) we will end up with a tree whose pages are about fillfactor% full,

 * instead of the 50% full result that we'd get without this special case.

 * This is the same as nbtsort.c produces for a newly-created tree.  Note

 * that leaf and nonleaf pages use different fillfactors.  Note also that

 * there are a number of further special cases where fillfactor is not

 * applied in the standard way.

 *

 * We are passed the intended insert position of the new tuple, expressed as

 * the offsetnumber of the tuple it must go in front of (this could be

 * maxoff+1 if the tuple is to go at the end).  The new tuple itself is also

 * passed, since it's needed to give some weight to how effective suffix

 * truncation will be.  The implementation picks the split point that

 * maximizes the effectiveness of suffix truncation from a small list of

 * alternative candidate split points that leave each side of the split with

 * about the same share of free space.  Suffix truncation is secondary to

 * equalizing free space, except in cases with large numbers of duplicates.

 * Note that it is always assumed that caller goes on to perform truncation,

 * even with pg_upgrade'd indexes where that isn't actually the case

 * (!heapkeyspace indexes).  See nbtree/README for more information about

 * suffix truncation.

 *

 * We return the index of the first existing tuple that should go on the

 * righthand page (which is called firstrightoff), plus a boolean

 * indicating whether the new tuple goes on the left or right page.  You

 * can think of the returned state as a point _between_ two adjacent data

 * items (lastleft and firstright data items) on an imaginary version of

 * origpage that already includes newitem.  The bool is necessary to

 * disambiguate the case where firstrightoff == newitemoff (i.e. it is

 * sometimes needed to determine if the firstright tuple for the split is

 * newitem rather than the tuple from origpage at offset firstrightoff).

 */

OffsetNumber

_bt_findsplitloc(Relation rel,

         Page origpage,

         OffsetNumber newitemoff,

         Size newitemsz,

         IndexTuple newitem,

         bool *newitemonleft)

{

  BTPageOpaque opaque;

  int     leftspace,

        rightspace,

        olddataitemstotal,

        olddataitemstoleft,

        perfectpenalty,

        leaffillfactor;

  FindSplitData state;

  FindSplitStrat strategy;

  ItemId    itemid;

  OffsetNumber offnum,

        maxoff,

        firstrightoff;

  double    fillfactormult;

  bool    usemult;

  SplitPoint  leftpage,

        rightpage;

  opaque = BTPageGetOpaque(origpage);

  maxoff = PageGetMaxOffsetNumber(origpage);

  /* Total free space available on a btree page, after fixed overhead */

  leftspace = rightspace =

    PageGetPageSize(origpage) - SizeOfPageHeaderData -

    MAXALIGN(sizeof(BTPageOpaqueData));

  /* The right page will have the same high key as the old page */

  if (!P_RIGHTMOST(opaque))

  {

    itemid = PageGetItemId(origpage, P_HIKEY);

    rightspace -= (int) (MAXALIGN(ItemIdGetLength(itemid)) +

               sizeof(ItemIdData));

  }

  /* Count up total space in data items before actually scanning 'em */

  olddataitemstotal = rightspace - (int) PageGetExactFreeSpace(origpage);

  leaffillfactor = BTGetFillFactor(rel);

  /* Passed-in newitemsz is MAXALIGNED but does not include line pointer */

  newitemsz += sizeof(ItemIdData);

  state.rel = rel;

  state.origpage = origpage;

  state.newitem = newitem;

  state.newitemsz = newitemsz;

  state.is_leaf = P_ISLEAF(opaque);

  state.is_rightmost = P_RIGHTMOST(opaque);

  state.leftspace = leftspace;

  state.rightspace = rightspace;

  state.olddataitemstotal = olddataitemstotal;

  state.minfirstrightsz = SIZE_MAX;

  state.newitemoff = newitemoff;

  /* newitem cannot be a posting list item */

  Assert(!BTreeTupleIsPosting(newitem));

  /*

   * nsplits should never exceed maxoff because there will be at most as

   * many candidate split points as there are points _between_ tuples, once

   * you imagine that the new item is already on the original page (the

   * final number of splits may be slightly lower because not all points

   * between tuples will be legal).

   */

  state.maxsplits = maxoff;

  state.splits = palloc(sizeof(SplitPoint) * state.maxsplits);

  state.nsplits = 0;

  /*

   * Scan through the data items and calculate space usage for a split at

   * each possible position

   */

  olddataitemstoleft = 0;

  for (offnum = P_FIRSTDATAKEY(opaque);

     offnum <= maxoff;

     offnum = OffsetNumberNext(offnum))

  {

    Size    itemsz;

    itemid = PageGetItemId(origpage, offnum);

    itemsz = MAXALIGN(ItemIdGetLength(itemid)) + sizeof(ItemIdData);

    /*

     * When item offset number is not newitemoff, neither side of the

     * split can be newitem.  Record a split after the previous data item

     * from original page, but before the current data item from original

     * page. (_bt_recsplitloc() will reject the split when there are no

     * previous items, which we rely on.)

     */

    if (offnum < newitemoff)

      _bt_recsplitloc(&state, offnum, false, olddataitemstoleft, itemsz);

    else if (offnum > newitemoff)

      _bt_recsplitloc(&state, offnum, true, olddataitemstoleft, itemsz);

    else

    {

      /*

       * Record a split after all "offnum < newitemoff" original page

       * data items, but before newitem

       */

      _bt_recsplitloc(&state, offnum, false, olddataitemstoleft, itemsz);

      /*

       * Record a split after newitem, but before data item from

       * original page at offset newitemoff/current offset

       */

      _bt_recsplitloc(&state, offnum, true, olddataitemstoleft, itemsz);

    }

    olddataitemstoleft += itemsz;

  }

  /*

   * Record a split after all original page data items, but before newitem.

   * (Though only when it's possible that newitem will end up alone on new

   * right page.)

   */

  Assert(olddataitemstoleft == olddataitemstotal);

  if (newitemoff > maxoff)

    _bt_recsplitloc(&state, newitemoff, false, olddataitemstotal, 0);

  /*

   * I believe it is not possible to fail to find a feasible split, but just

   * in case ...

   */

  if (state.nsplits == 0)

    elog(ERROR, "could not find a feasible split point for index \"%s\"",

       RelationGetRelationName(rel));

  /*

   * Start search for a split point among list of legal split points.  Give

   * primary consideration to equalizing available free space in each half

   * of the split initially (start with default strategy), while applying

   * rightmost and split-after-new-item optimizations where appropriate.

   * Either of the two other fallback strategies may be required for cases

   * with a large number of duplicates around the original/space-optimal

   * split point.

   *

   * Default strategy gives some weight to suffix truncation in deciding a

   * split point on leaf pages.  It attempts to select a split point where a

   * distinguishing attribute appears earlier in the new high key for the

   * left side of the split, in order to maximize the number of trailing

   * attributes that can be truncated away.  Only candidate split points

   * that imply an acceptable balance of free space on each side are

   * considered.  See _bt_defaultinterval().

   */

  if (!state.is_leaf)

  {

    /* fillfactormult only used on rightmost page */

    usemult = state.is_rightmost;

    fillfactormult = BTREE_NONLEAF_FILLFACTOR / 100.0;

  }

  else if (state.is_rightmost)

  {

    /* Rightmost leaf page --  fillfactormult always used */

    usemult = true;

    fillfactormult = leaffillfactor / 100.0;

  }

  else if (_bt_afternewitemoff(&state, maxoff, leaffillfactor, &usemult))

  {

    /*

     * New item inserted at rightmost point among a localized grouping on

     * a leaf page -- apply "split after new item" optimization, either by

     * applying leaf fillfactor multiplier, or by choosing the exact split

     * point that leaves newitem as lastleft. (usemult is set for us.)

     */

    if (usemult)

    {

      /* fillfactormult should be set based on leaf fillfactor */

      fillfactormult = leaffillfactor / 100.0;

    }

    else

    {

      /* find precise split point after newitemoff */

      for (int i = 0; i < state.nsplits; i++)

      {

        SplitPoint *split = state.splits + i;

        if (split->newitemonleft &&

          newitemoff == split->firstrightoff)

        {

          pfree(state.splits);

          *newitemonleft = true;

          return newitemoff;

        }

      }

      /*

       * Cannot legally split after newitemoff; proceed with split

       * without using fillfactor multiplier.  This is defensive, and

       * should never be needed in practice.

       */

      fillfactormult = 0.50;

    }

  }

  else

  {

    /* Other leaf page.  50:50 page split. */

    usemult = false;

    /* fillfactormult not used, but be tidy */

    fillfactormult = 0.50;

  }

  /*

   * Save leftmost and rightmost splits for page before original ordinal

   * sort order is lost by delta/fillfactormult sort

   */

  leftpage = state.splits[0];

  rightpage = state.splits[state.nsplits - 1];

  /* Give split points a fillfactormult-wise delta, and sort on deltas */

  _bt_deltasortsplits(&state, fillfactormult, usemult);

  /* Determine split interval for default strategy */

  state.interval = _bt_defaultinterval(&state);

  /*

   * Determine if default strategy/split interval will produce a

   * sufficiently distinguishing split, or if we should change strategies.

   * Alternative strategies change the range of split points that are

   * considered acceptable (split interval), and possibly change

   * fillfactormult, in order to deal with pages with a large number of

   * duplicates gracefully.

   *

   * Pass low and high splits for the entire page (actually, they're for an

   * imaginary version of the page that includes newitem).  These are used

   * when the initial split interval encloses split points that are full of

   * duplicates, and we need to consider if it's even possible to avoid

   * appending a heap TID.

   */

  perfectpenalty = _bt_strategy(&state, &leftpage, &rightpage, &strategy);

  if (strategy == SPLIT_DEFAULT)

  {

    /*

     * Default strategy worked out (always works out with internal page).

     * Original split interval still stands.

     */

  }

  /*

   * Many duplicates strategy is used when a heap TID would otherwise be

   * appended, but the page isn't completely full of logical duplicates.

   *

   * The split interval is widened to include all legal candidate split

   * points.  There might be a few as two distinct values in the whole-page

   * split interval, though it's also possible that most of the values on

   * the page are unique.  The final split point will either be to the

   * immediate left or to the immediate right of the group of duplicate

   * tuples that enclose the first/delta-optimal split point (perfect

   * penalty was set so that the lowest delta split point that avoids

   * appending a heap TID will be chosen).  Maximizing the number of

   * attributes that can be truncated away is not a goal of the many

   * duplicates strategy.

   *

   * Single value strategy is used when it is impossible to avoid appending

   * a heap TID.  It arranges to leave the left page very full.  This

   * maximizes space utilization in cases where tuples with the same

   * attribute values span many pages.  Newly inserted duplicates will tend

   * to have higher heap TID values, so we'll end up splitting to the right

   * consistently.  (Single value strategy is harmless though not

   * particularly useful with !heapkeyspace indexes.)

   */

  else if (strategy == SPLIT_MANY_DUPLICATES)

  {

    Assert(state.is_leaf);

    /* Shouldn't try to truncate away extra user attributes */

    Assert(perfectpenalty ==

         IndexRelationGetNumberOfKeyAttributes(state.rel));

    /* No need to resort splits -- no change in fillfactormult/deltas */

    state.interval = state.nsplits;

  }

  else if (strategy == SPLIT_SINGLE_VALUE)

  {

    Assert(state.is_leaf);

    /* Split near the end of the page */

    usemult = true;

    fillfactormult = BTREE_SINGLEVAL_FILLFACTOR / 100.0;

    /* Resort split points with new delta */

    _bt_deltasortsplits(&state, fillfactormult, usemult);

    /* Appending a heap TID is unavoidable, so interval of 1 is fine */

    state.interval = 1;

  }

  /*

   * Search among acceptable split points (using final split interval) for

   * the entry that has the lowest penalty, and is therefore expected to

   * maximize fan-out.  Sets *newitemonleft for us.

   */

  firstrightoff = _bt_bestsplitloc(&state, perfectpenalty, newitemonleft,

                   strategy);

  pfree(state.splits);

  return firstrightoff;

}

/*

 * Subroutine to record a particular point between two tuples (possibly the

 * new item) on page (ie, combination of firstrightoff and newitemonleft

 * settings) in *state for later analysis.  This is also a convenient point to

 * check if the split is legal (if it isn't, it won't be recorded).

 *

 * firstrightoff is the offset of the first item on the original page that

 * goes to the right page, and firstrightofforigpagetuplesz is the size of

 * that tuple.  firstrightoff can be > max offset, which means that all the

 * old items go to the left page and only the new item goes to the right page.

 * We don't actually use firstrightofforigpagetuplesz in that case (actually,

 * we don't use it for _any_ split where the firstright tuple happens to be

 * newitem).

 *

 * olddataitemstoleft is the total size of all old items to the left of the

 * split point that is recorded here when legal.  Should not include

 * newitemsz, since that is handled here.

 */

static void

_bt_recsplitloc(FindSplitData *state,

        OffsetNumber firstrightoff,

        bool newitemonleft,

        int olddataitemstoleft,

        Size firstrightofforigpagetuplesz)

{

  int16   leftfree,

        rightfree;

  Size    firstrightsz;

  Size    postingsz = 0;

  bool    newitemisfirstright;

  /* Is the new item going to be split point's firstright tuple? */

  newitemisfirstright = (firstrightoff == state->newitemoff &&

               !newitemonleft);

  if (newitemisfirstright)

    firstrightsz = state->newitemsz;

  else

  {

    firstrightsz = firstrightofforigpagetuplesz;

    /*

     * Calculate suffix truncation space saving when firstright tuple is a

     * posting list tuple, though only when the tuple is over 64 bytes

     * including line pointer overhead (arbitrary).  This avoids accessing

     * the tuple in cases where its posting list must be very small (if

     * tuple has one at all).

     *

     * Note: We don't do this in the case where firstright tuple is

     * newitem, since newitem cannot have a posting list.

     */

    if (state->is_leaf && firstrightsz > 64)

    {

      ItemId    itemid;

      IndexTuple  newhighkey;

      itemid = PageGetItemId(state->origpage, firstrightoff);

      newhighkey = (IndexTuple) PageGetItem(state->origpage, itemid);

      if (BTreeTupleIsPosting(newhighkey))

        postingsz = IndexTupleSize(newhighkey) -

          BTreeTupleGetPostingOffset(newhighkey);

    }

  }

  /* Account for all the old tuples */

  leftfree = state->leftspace - olddataitemstoleft;

  rightfree = state->rightspace -

    (state->olddataitemstotal - olddataitemstoleft);

  /*

   * The first item on the right page becomes the high key of the left page;

   * therefore it counts against left space as well as right space (we

   * cannot assume that suffix truncation will make it any smaller).  When

   * index has included attributes, then those attributes of left page high

   * key will be truncated leaving that page with slightly more free space.

   * However, that shouldn't affect our ability to find valid split

   * location, since we err in the direction of being pessimistic about free

   * space on the left half.  Besides, even when suffix truncation of

   * non-TID attributes occurs, the new high key often won't even be a

   * single MAXALIGN() quantum smaller than the firstright tuple it's based

   * on.

   *

   * If we are on the leaf level, assume that suffix truncation cannot avoid

   * adding a heap TID to the left half's new high key when splitting at the

   * leaf level.  In practice the new high key will often be smaller and

   * will rarely be larger, but conservatively assume the worst case.  We do

   * go to the trouble of subtracting away posting list overhead, though

   * only when it looks like it will make an appreciable difference.

   * (Posting lists are the only case where truncation will typically make

   * the final high key far smaller than firstright, so being a bit more

   * precise there noticeably improves the balance of free space.)

   */

  if (state->is_leaf)

    leftfree -= (int16) (firstrightsz +

               MAXALIGN(sizeof(ItemPointerData)) -

               postingsz);

  else

    leftfree -= (int16) firstrightsz;

  /* account for the new item */

  if (newitemonleft)

    leftfree -= (int16) state->newitemsz;

  else

    rightfree -= (int16) state->newitemsz;

  /*

   * If we are not on the leaf level, we will be able to discard the key

   * data from the first item that winds up on the right page.

   */

  if (!state->is_leaf)

    rightfree += (int16) firstrightsz -

      (int16) (MAXALIGN(sizeof(IndexTupleData)) + sizeof(ItemIdData));

  /* Record split if legal */

  if (leftfree >= 0 && rightfree >= 0)

  {

    Assert(state->nsplits < state->maxsplits);

    /* Determine smallest firstright tuple size among legal splits */

    state->minfirstrightsz = Min(state->minfirstrightsz, firstrightsz);

    state->splits[state->nsplits].curdelta = 0;

    state->splits[state->nsplits].leftfree = leftfree;

    state->splits[state->nsplits].rightfree = rightfree;

    state->splits[state->nsplits].firstrightoff = firstrightoff;

    state->splits[state->nsplits].newitemonleft = newitemonleft;

    state->nsplits++;

  }

}

/*

 * Subroutine to assign space deltas to materialized array of candidate split

 * points based on current fillfactor, and to sort array using that fillfactor

 */

static void

_bt_deltasortsplits(FindSplitData *state, double fillfactormult,

          bool usemult)

{

  for (int i = 0; i < state->nsplits; i++)

  {

    SplitPoint *split = state->splits + i;

    int16   delta;

    if (usemult)

      delta = fillfactormult * split->leftfree -

        (1.0 - fillfactormult) * split->rightfree;

    else

      delta = split->leftfree - split->rightfree;

    if (delta < 0)

      delta = -delta;

    /* Save delta */

    split->curdelta = delta;

  }

  qsort(state->splits, state->nsplits, sizeof(SplitPoint), _bt_splitcmp);

}

/*

 * qsort-style comparator used by _bt_deltasortsplits()

 */

static int

_bt_splitcmp(const void *arg1, const void *arg2)

{

  SplitPoint *split1 = (SplitPoint *) arg1;

  SplitPoint *split2 = (SplitPoint *) arg2;

  return pg_cmp_s16(split1->curdelta, split2->curdelta);

}

/*

 * Subroutine to determine whether or not a non-rightmost leaf page should be

 * split immediately after the would-be original page offset for the

 * new/incoming tuple (or should have leaf fillfactor applied when new item is

 * to the right on original page).  This is appropriate when there is a

 * pattern of localized monotonically increasing insertions into a composite

 * index, where leading attribute values form local groupings, and we

 * anticipate further insertions of the same/current grouping (new item's

 * grouping) in the near future.  This can be thought of as a variation on

 * applying leaf fillfactor during rightmost leaf page splits, since cases

 * that benefit will converge on packing leaf pages leaffillfactor% full over

 * time.

 *

 * We may leave extra free space remaining on the rightmost page of a "most

 * significant column" grouping of tuples if that grouping never ends up

 * having future insertions that use the free space.  That effect is

 * self-limiting; a future grouping that becomes the "nearest on the right"

 * grouping of the affected grouping usually puts the extra free space to good

 * use.

 *

 * Caller uses optimization when routine returns true, though the exact action

 * taken by caller varies.  Caller uses original leaf page fillfactor in

 * standard way rather than using the new item offset directly when *usemult

 * was also set to true here.  Otherwise, caller applies optimization by

 * locating the legal split point that makes the new tuple the lastleft tuple

 * for the split.

 */

static bool

_bt_afternewitemoff(FindSplitData *state, OffsetNumber maxoff,

          int leaffillfactor, bool *usemult)

{

  int16   nkeyatts;

  ItemId    itemid;

  IndexTuple  tup;

  int     keepnatts;

  Assert(state->is_leaf && !state->is_rightmost);

  nkeyatts = IndexRelationGetNumberOfKeyAttributes(state->rel);

  /* Single key indexes not considered here */

  if (nkeyatts == 1)

    return false;

  /* Ascending insertion pattern never inferred when new item is first */

  if (state->newitemoff == P_FIRSTKEY)

    return false;

  /*

   * Only apply optimization on pages with equisized tuples, since ordinal

   * keys are likely to be fixed-width.  Testing if the new tuple is

   * variable width directly might also work, but that fails to apply the

   * optimization to indexes with a numeric_ops attribute.

   *

   * Conclude that page has equisized tuples when the new item is the same

   * width as the smallest item observed during pass over page, and other

   * non-pivot tuples must be the same width as well.  (Note that the

   * possibly-truncated existing high key isn't counted in

   * olddataitemstotal, and must be subtracted from maxoff.)

   */

  if (state->newitemsz != state->minfirstrightsz)

    return false;

  if (state->newitemsz * (maxoff - 1) != state->olddataitemstotal)

    return false;

  /*

   * Avoid applying optimization when tuples are wider than a tuple

   * consisting of two non-NULL int8/int64 attributes (or four non-NULL

   * int4/int32 attributes)

   */

  if (state->newitemsz >

    MAXALIGN(sizeof(IndexTupleData) + sizeof(int64) * 2) +

    sizeof(ItemIdData))

    return false;

  /*

   * At least the first attribute's value must be equal to the corresponding

   * value in previous tuple to apply optimization.  New item cannot be a

   * duplicate, either.

   *

   * Handle case where new item is to the right of all items on the existing

   * page.  This is suggestive of monotonically increasing insertions in

   * itself, so the "heap TID adjacency" test is not applied here.

   */

  if (state->newitemoff > maxoff)

  {

    itemid = PageGetItemId(state->origpage, maxoff);

    tup = (IndexTuple) PageGetItem(state->origpage, itemid);

    keepnatts = _bt_keep_natts_fast(state->rel, tup, state->newitem);

    if (keepnatts > 1 && keepnatts <= nkeyatts)

    {

      *usemult = true;

      return true;

    }

    return false;

  }

  /*

   * "Low cardinality leading column, high cardinality suffix column"

   * indexes with a random insertion pattern (e.g., an index with a boolean

   * column, such as an index on '(book_is_in_print, book_isbn)') present us

   * with a risk of consistently misapplying the optimization.  We're

   * willing to accept very occasional misapplication of the optimization,

   * provided the cases where we get it wrong are rare and self-limiting.

   *

   * Heap TID adjacency strongly suggests that the item just to the left was

   * inserted very recently, which limits overapplication of the

   * optimization.  Besides, all inappropriate cases triggered here will

   * still split in the middle of the page on average.

   */

  itemid = PageGetItemId(state->origpage, OffsetNumberPrev(state->newitemoff));

  tup = (IndexTuple) PageGetItem(state->origpage, itemid);

  /* Do cheaper test first */

  if (BTreeTupleIsPosting(tup) ||

    !_bt_adjacenthtid(&tup->t_tid, &state->newitem->t_tid))

    return false;

  /* Check same conditions as rightmost item case, too */

  keepnatts = _bt_keep_natts_fast(state->rel, tup, state->newitem);

  if (keepnatts > 1 && keepnatts <= nkeyatts)

  {

    double    interp = (double) state->newitemoff / ((double) maxoff + 1);

    double    leaffillfactormult = (double) leaffillfactor / 100.0;

    /*

     * Don't allow caller to split after a new item when it will result in

     * a split point to the right of the point that a leaf fillfactor

     * split would use -- have caller apply leaf fillfactor instead

     */

    *usemult = interp > leaffillfactormult;

    return true;

  }

  return false;

}

/*

 * Subroutine for determining if two heap TIDS are "adjacent".

 *

 * Adjacent means that the high TID is very likely to have been inserted into

 * heap relation immediately after the low TID, probably during the current

 * transaction.

 */

static bool

_bt_adjacenthtid(ItemPointer lowhtid, ItemPointer highhtid)

{

  BlockNumber lowblk,

        highblk;

  lowblk = ItemPointerGetBlockNumber(lowhtid);

  highblk = ItemPointerGetBlockNumber(highhtid);

  /* Make optimistic assumption of adjacency when heap blocks match */

  if (lowblk == highblk)

    return true;

  /* When heap block one up, second offset should be FirstOffsetNumber */

  if (lowblk + 1 == highblk &&

    ItemPointerGetOffsetNumber(highhtid) == FirstOffsetNumber)

    return true;

  return false;

}

/*

 * Subroutine to find the "best" split point among candidate split points.

 * The best split point is the split point with the lowest penalty among split

 * points that fall within current/final split interval.  Penalty is an

 * abstract score, with a definition that varies depending on whether we're

 * splitting a leaf page or an internal page.  See _bt_split_penalty() for

 * details.

 *

 * "perfectpenalty" is assumed to be the lowest possible penalty among

 * candidate split points.  This allows us to return early without wasting

 * cycles on calculating the first differing attribute for all candidate

 * splits when that clearly cannot improve our choice (or when we only want a

 * minimally distinguishing split point, and don't want to make the split any

 * more unbalanced than is necessary).

 *

 * We return the index of the first existing tuple that should go on the right

 * page, plus a boolean indicating if new item is on left of split point.

 */

static OffsetNumber

_bt_bestsplitloc(FindSplitData *state, int perfectpenalty,

         bool *newitemonleft, FindSplitStrat strategy)

{

  int     bestpenalty,

        lowsplit;

  int     highsplit = Min(state->interval, state->nsplits);

  SplitPoint *final;

  bestpenalty = INT_MAX;

  lowsplit = 0;

  for (int i = lowsplit; i < highsplit; i++)

  {

    int     penalty;

    penalty = _bt_split_penalty(state, state->splits + i);

    if (penalty < bestpenalty)

    {

      bestpenalty = penalty;

      lowsplit = i;

    }

    if (penalty <= perfectpenalty)

      break;

  }

  final = &state->splits[lowsplit];

  /*

   * There is a risk that the "many duplicates" strategy will repeatedly do

   * the wrong thing when there are monotonically decreasing insertions to

   * the right of a large group of duplicates.   Repeated splits could leave

   * a succession of right half pages with free space that can never be

   * used.  This must be avoided.

   *

   * Consider the example of the leftmost page in a single integer attribute

   * NULLS FIRST index which is almost filled with NULLs.  Monotonically

   * decreasing integer insertions might cause the same leftmost page to

   * split repeatedly at the same point.  Each split derives its new high

   * key from the lowest current value to the immediate right of the large

   * group of NULLs, which will always be higher than all future integer

   * insertions, directing all future integer insertions to the same

   * leftmost page.

   */

  if (strategy == SPLIT_MANY_DUPLICATES && !state->is_rightmost &&

    !final->newitemonleft && final->firstrightoff >= state->newitemoff &&

    final->firstrightoff < state->newitemoff + 9)

  {

    /*

     * Avoid the problem by performing a 50:50 split when the new item is

     * just to the right of the would-be "many duplicates" split point.

     * (Note that the test used for an insert that is "just to the right"

     * of the split point is conservative.)

     */

    final = &state->splits[0];

  }

  *newitemonleft = final->newitemonleft;

  return final->firstrightoff;

}

#define LEAF_SPLIT_DISTANCE     0.050

#define INTERNAL_SPLIT_DISTANCE   0.075

/*

 * Return a split interval to use for the default strategy.  This is a limit

 * on the number of candidate split points to give further consideration to.

 * Only a fraction of all candidate splits points (those located at the start

 * of the now-sorted splits array) fall within the split interval.  Split

 * interval is applied within _bt_bestsplitloc().

 *

 * Split interval represents an acceptable range of split points -- those that

 * have leftfree and rightfree values that are acceptably balanced.  The final

 * split point chosen is the split point with the lowest "penalty" among split

 * points in this split interval (unless we change our entire strategy, in

 * which case the interval also changes -- see _bt_strategy()).

 *

 * The "Prefix B-Trees" paper calls split interval sigma l for leaf splits,

 * and sigma b for internal ("branch") splits.  It's hard to provide a

 * theoretical justification for the size of the split interval, though it's

 * clear that a small split interval can make tuples on level L+1 much smaller

 * on average, without noticeably affecting space utilization on level L.

 * (Note that the way that we calculate split interval might need to change if

 * suffix truncation is taught to truncate tuples "within" the last

 * attribute/datum for data types like text, which is more or less how it is

 * assumed to work in the paper.)

 */

static int

_bt_defaultinterval(FindSplitData *state)

{

  SplitPoint *spaceoptimal;

  int16   tolerance,

        lowleftfree,

        lowrightfree,

        highleftfree,

        highrightfree;

  /*

   * Determine leftfree and rightfree values that are higher and lower than

   * we're willing to tolerate.  Note that the final split interval will be

   * about 10% of nsplits in the common case where all non-pivot tuples

   * (data items) from a leaf page are uniformly sized.  We're a bit more

   * aggressive when splitting internal pages.

   */

  if (state->is_leaf)

    tolerance = state->olddataitemstotal * LEAF_SPLIT_DISTANCE;

  else

    tolerance = state->olddataitemstotal * INTERNAL_SPLIT_DISTANCE;

  /* First candidate split point is the most evenly balanced */

  spaceoptimal = state->splits;

  lowleftfree = spaceoptimal->leftfree - tolerance;

  lowrightfree = spaceoptimal->rightfree - tolerance;

  highleftfree = spaceoptimal->leftfree + tolerance;

  highrightfree = spaceoptimal->rightfree + tolerance;

  /*

   * Iterate through split points, starting from the split immediately after

   * 'spaceoptimal'.  Find the first split point that divides free space so

   * unevenly that including it in the split interval would be unacceptable.

   */

  for (int i = 1; i < state->nsplits; i++)

  {

    SplitPoint *split = state->splits + i;

    /* Cannot use curdelta here, since its value is often weighted */

    if (split->leftfree < lowleftfree || split->rightfree < lowrightfree ||

      split->leftfree > highleftfree || split->rightfree > highrightfree)

      return i;

  }

  return state->nsplits;

}

/*

 * Subroutine to decide whether split should use default strategy/initial

 * split interval, or whether it should finish splitting the page using

 * alternative strategies (this is only possible with leaf pages).

 *

 * Caller uses alternative strategy (or sticks with default strategy) based

 * on how *strategy is set here.  Return value is "perfect penalty", which is

 * passed to _bt_bestsplitloc() as a final constraint on how far caller is

 * willing to go to avoid appending a heap TID when using the many duplicates

 * strategy (it also saves _bt_bestsplitloc() useless cycles).

 */

static int

_bt_strategy(FindSplitData *state, SplitPoint *leftpage,

       SplitPoint *rightpage, FindSplitStrat *strategy)

{

  IndexTuple  leftmost,

        rightmost;

  SplitPoint *leftinterval,

         *rightinterval;

  int     perfectpenalty;

  int     indnkeyatts = IndexRelationGetNumberOfKeyAttributes(state->rel);

  /* Assume that alternative strategy won't be used for now */

  *strategy = SPLIT_DEFAULT;

  /*

   * Use smallest observed firstright item size for entire page (actually,

   * entire imaginary version of page that includes newitem) as perfect

   * penalty on internal pages.  This can save cycles in the common case

   * where most or all splits (not just splits within interval) have

   * firstright tuples that are the same size.

   */

  if (!state->is_leaf)

    return state->minfirstrightsz;

  /*

   * Use leftmost and rightmost tuples from leftmost and rightmost splits in

   * current split interval

   */

  _bt_interval_edges(state, &leftinterval, &rightinterval);

  leftmost = _bt_split_lastleft(state, leftinterval);

  rightmost = _bt_split_firstright(state, rightinterval);

  /*

   * If initial split interval can produce a split point that will at least

   * avoid appending a heap TID in new high key, we're done.  Finish split

   * with default strategy and initial split interval.

   */

  perfectpenalty = _bt_keep_natts_fast(state->rel, leftmost, rightmost);

  if (perfectpenalty <= indnkeyatts)

    return perfectpenalty;

  /*

   * Work out how caller should finish split when even their "perfect"

   * penalty for initial/default split interval indicates that the interval

   * does not contain even a single split that avoids appending a heap TID.

   *

   * Use the leftmost split's lastleft tuple and the rightmost split's

   * firstright tuple to assess every possible split.

   */

  leftmost = _bt_split_lastleft(state, leftpage);

  rightmost = _bt_split_firstright(state, rightpage);

  /*

   * If page (including new item) has many duplicates but is not entirely