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

 *

 * partbounds.c

 *    Support routines for manipulating partition bounds

 *

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

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

 *

 * IDENTIFICATION

 *      src/backend/partitioning/partbounds.c

 *

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

 */

#include "postgres.h"

#include "access/relation.h"

#include "access/table.h"

#include "access/tableam.h"

#include "catalog/namespace.h"

#include "catalog/partition.h"

#include "catalog/pg_inherits.h"

#include "catalog/pg_type.h"

#include "commands/tablecmds.h"

#include "common/hashfn.h"

#include "executor/executor.h"

#include "miscadmin.h"

#include "nodes/makefuncs.h"

#include "nodes/nodeFuncs.h"

#include "nodes/pathnodes.h"

#include "parser/parse_coerce.h"

#include "partitioning/partbounds.h"

#include "partitioning/partdesc.h"

#include "utils/array.h"

#include "utils/builtins.h"

#include "utils/datum.h"

#include "utils/fmgroids.h"

#include "utils/lsyscache.h"

#include "utils/partcache.h"

#include "utils/ruleutils.h"

#include "utils/snapmgr.h"

#include "utils/syscache.h"

/*

 * When qsort'ing partition bounds after reading from the catalog, each bound

 * is represented with one of the following structs.

 */

/* One bound of a hash partition */

typedef struct PartitionHashBound

{

  int     modulus;

  int     remainder;

  int     index;

} PartitionHashBound;

/* One value coming from some (index'th) list partition */

typedef struct PartitionListValue

{

  int     index;

  Datum   value;

} PartitionListValue;

/* One bound of a range partition */

typedef struct PartitionRangeBound

{

  int     index;

  Datum    *datums;     /* range bound datums */

  PartitionRangeDatumKind *kind;  /* the kind of each datum */

  bool    lower;      /* this is the lower (vs upper) bound */

} PartitionRangeBound;

/*

 * Mapping from partitions of a joining relation to partitions of a join

 * relation being computed (a.k.a merged partitions)

 */

typedef struct PartitionMap

{

  int     nparts;     /* number of partitions */

  int      *merged_indexes; /* indexes of merged partitions */

  bool     *merged;     /* flags to indicate whether partitions are

                 * merged with non-dummy partitions */

  bool    did_remapping;  /* did we re-map partitions? */

  int      *old_indexes;  /* old indexes of merged partitions if

                 * did_remapping */

} PartitionMap;

/* Macro for comparing two range bounds */

#define compare_range_bounds(partnatts, partsupfunc, partcollations, \

               bound1, bound2) \

  (partition_rbound_cmp(partnatts, partsupfunc, partcollations, \

              (bound1)->datums, (bound1)->kind, (bound1)->lower, \

              bound2))

static int32 qsort_partition_hbound_cmp(const void *a, const void *b);

static int32 qsort_partition_list_value_cmp(const void *a, const void *b,

                      void *arg);

static int32 qsort_partition_rbound_cmp(const void *a, const void *b,

                    void *arg);

static PartitionBoundInfo create_hash_bounds(PartitionBoundSpec **boundspecs,

                       int nparts, PartitionKey key, int **mapping);

static PartitionBoundInfo create_list_bounds(PartitionBoundSpec **boundspecs,

                       int nparts, PartitionKey key, int **mapping);

static PartitionBoundInfo create_range_bounds(PartitionBoundSpec **boundspecs,

                        int nparts, PartitionKey key, int **mapping);

static PartitionBoundInfo merge_list_bounds(FmgrInfo *partsupfunc,

                      Oid *partcollation,

                      RelOptInfo *outer_rel,

                      RelOptInfo *inner_rel,

                      JoinType jointype,

                      List **outer_parts,

                      List **inner_parts);

static PartitionBoundInfo merge_range_bounds(int partnatts,

                       FmgrInfo *partsupfuncs,

                       Oid *partcollations,

                       RelOptInfo *outer_rel,

                       RelOptInfo *inner_rel,

                       JoinType jointype,

                       List **outer_parts,

                       List **inner_parts);

static void init_partition_map(RelOptInfo *rel, PartitionMap *map);

static void free_partition_map(PartitionMap *map);

static bool is_dummy_partition(RelOptInfo *rel, int part_index);

static int  merge_matching_partitions(PartitionMap *outer_map,

                    PartitionMap *inner_map,

                    int outer_index,

                    int inner_index,

                    int *next_index);

static int  process_outer_partition(PartitionMap *outer_map,

                  PartitionMap *inner_map,

                  bool outer_has_default,

                  bool inner_has_default,

                  int outer_index,

                  int inner_default,

                  JoinType jointype,

                  int *next_index,

                  int *default_index);

static int  process_inner_partition(PartitionMap *outer_map,

                  PartitionMap *inner_map,

                  bool outer_has_default,

                  bool inner_has_default,

                  int inner_index,

                  int outer_default,

                  JoinType jointype,

                  int *next_index,

                  int *default_index);

static void merge_null_partitions(PartitionMap *outer_map,

                  PartitionMap *inner_map,

                  bool outer_has_null,

                  bool inner_has_null,

                  int outer_null,

                  int inner_null,

                  JoinType jointype,

                  int *next_index,

                  int *null_index);

static void merge_default_partitions(PartitionMap *outer_map,

                   PartitionMap *inner_map,

                   bool outer_has_default,

                   bool inner_has_default,

                   int outer_default,

                   int inner_default,

                   JoinType jointype,

                   int *next_index,

                   int *default_index);

static int  merge_partition_with_dummy(PartitionMap *map, int index,

                     int *next_index);

static void fix_merged_indexes(PartitionMap *outer_map,

                 PartitionMap *inner_map,

                 int nmerged, List *merged_indexes);

static void generate_matching_part_pairs(RelOptInfo *outer_rel,

                     RelOptInfo *inner_rel,

                     PartitionMap *outer_map,

                     PartitionMap *inner_map,

                     int nmerged,

                     List **outer_parts,

                     List **inner_parts);

static PartitionBoundInfo build_merged_partition_bounds(char strategy,

                            List *merged_datums,

                            List *merged_kinds,

                            List *merged_indexes,

                            int null_index,

                            int default_index);

static int  get_range_partition(RelOptInfo *rel,

                PartitionBoundInfo bi,

                int *lb_pos,

                PartitionRangeBound *lb,

                PartitionRangeBound *ub);

static int  get_range_partition_internal(PartitionBoundInfo bi,

                     int *lb_pos,

                     PartitionRangeBound *lb,

                     PartitionRangeBound *ub);

static bool compare_range_partitions(int partnatts, FmgrInfo *partsupfuncs,

                   Oid *partcollations,

                   PartitionRangeBound *outer_lb,

                   PartitionRangeBound *outer_ub,

                   PartitionRangeBound *inner_lb,

                   PartitionRangeBound *inner_ub,

                   int *lb_cmpval, int *ub_cmpval);

static void get_merged_range_bounds(int partnatts, FmgrInfo *partsupfuncs,

                  Oid *partcollations, JoinType jointype,

                  PartitionRangeBound *outer_lb,

                  PartitionRangeBound *outer_ub,

                  PartitionRangeBound *inner_lb,

                  PartitionRangeBound *inner_ub,

                  int lb_cmpval, int ub_cmpval,

                  PartitionRangeBound *merged_lb,

                  PartitionRangeBound *merged_ub);

static void add_merged_range_bounds(int partnatts, FmgrInfo *partsupfuncs,

                  Oid *partcollations,

                  PartitionRangeBound *merged_lb,

                  PartitionRangeBound *merged_ub,

                  int merged_index,

                  List **merged_datums,

                  List **merged_kinds,

                  List **merged_indexes);

static PartitionRangeBound *make_one_partition_rbound(PartitionKey key, int index,

                            List *datums, bool lower);

static int32 partition_hbound_cmp(int modulus1, int remainder1, int modulus2,

                  int remainder2);

static int32 partition_rbound_cmp(int partnatts, FmgrInfo *partsupfunc,

                  Oid *partcollation, Datum *datums1,

                  PartitionRangeDatumKind *kind1, bool lower1,

                  PartitionRangeBound *b2);

static int  partition_range_bsearch(int partnatts, FmgrInfo *partsupfunc,

                  Oid *partcollation,

                  PartitionBoundInfo boundinfo,

                  PartitionRangeBound *probe, int32 *cmpval);

static Expr *make_partition_op_expr(PartitionKey key, int keynum,

                  uint16 strategy, Expr *arg1, Expr *arg2);

static Oid  get_partition_operator(PartitionKey key, int col,

                   StrategyNumber strategy, bool *need_relabel);

static List *get_qual_for_hash(Relation parent, PartitionBoundSpec *spec);

static List *get_qual_for_list(Relation parent, PartitionBoundSpec *spec);

static List *get_qual_for_range(Relation parent, PartitionBoundSpec *spec,

                bool for_default);

static void get_range_key_properties(PartitionKey key, int keynum,

                   PartitionRangeDatum *ldatum,

                   PartitionRangeDatum *udatum,

                   ListCell **partexprs_item,

                   Expr **keyCol,

                   Const **lower_val, Const **upper_val);

static List *get_range_nulltest(PartitionKey key);

/*

 * get_qual_from_partbound

 *    Given a parser node for partition bound, return the list of executable

 *    expressions as partition constraint

 */

List *

get_qual_from_partbound(Relation parent, PartitionBoundSpec *spec)

{

  PartitionKey key = RelationGetPartitionKey(parent);

  List     *my_qual = NIL;

  Assert(key != NULL);

  switch (key->strategy)

  {

    case PARTITION_STRATEGY_HASH:

      Assert(spec->strategy == PARTITION_STRATEGY_HASH);

      my_qual = get_qual_for_hash(parent, spec);

      break;

    case PARTITION_STRATEGY_LIST:

      Assert(spec->strategy == PARTITION_STRATEGY_LIST);

      my_qual = get_qual_for_list(parent, spec);

      break;

    case PARTITION_STRATEGY_RANGE:

      Assert(spec->strategy == PARTITION_STRATEGY_RANGE);

      my_qual = get_qual_for_range(parent, spec, false);

      break;

  }

  return my_qual;

}

/*

 *  partition_bounds_create

 *    Build a PartitionBoundInfo struct from a list of PartitionBoundSpec

 *    nodes

 *

 * This function creates a PartitionBoundInfo and fills the values of its

 * various members based on the input list.  Importantly, 'datums' array will

 * contain Datum representation of individual bounds (possibly after

 * de-duplication as in case of range bounds), sorted in a canonical order

 * defined by qsort_partition_* functions of respective partitioning methods.

 * 'indexes' array will contain as many elements as there are bounds (specific

 * exceptions to this rule are listed in the function body), which represent

 * the 0-based canonical positions of partitions.

 *

 * Upon return from this function, *mapping is set to an array of

 * list_length(boundspecs) elements, each of which maps the original index of

 * a partition to its canonical index.

 *

 * Note: The objects returned by this function are wholly allocated in the

 * current memory context.

 */

PartitionBoundInfo

partition_bounds_create(PartitionBoundSpec **boundspecs, int nparts,

            PartitionKey key, int **mapping)

{

  int     i;

  Assert(nparts > 0);

  /*

   * For each partitioning method, we first convert the partition bounds

   * from their parser node representation to the internal representation,

   * along with any additional preprocessing (such as de-duplicating range

   * bounds).  Resulting bound datums are then added to the 'datums' array

   * in PartitionBoundInfo.  For each datum added, an integer indicating the

   * canonical partition index is added to the 'indexes' array.

   *

   * For each bound, we remember its partition's position (0-based) in the

   * original list to later map it to the canonical index.

   */

  /*

   * Initialize mapping array with invalid values, this is filled within

   * each sub-routine below depending on the bound type.

   */

  *mapping = palloc_array(int, nparts);

  for (i = 0; i < nparts; i++)

    (*mapping)[i] = -1;

  switch (key->strategy)

  {

    case PARTITION_STRATEGY_HASH:

      return create_hash_bounds(boundspecs, nparts, key, mapping);

    case PARTITION_STRATEGY_LIST:

      return create_list_bounds(boundspecs, nparts, key, mapping);

    case PARTITION_STRATEGY_RANGE:

      return create_range_bounds(boundspecs, nparts, key, mapping);

  }

  Assert(false);

  return NULL;       /* keep compiler quiet */

}

/*

 * create_hash_bounds

 *    Create a PartitionBoundInfo for a hash partitioned table

 */

static PartitionBoundInfo

create_hash_bounds(PartitionBoundSpec **boundspecs, int nparts,

           PartitionKey key, int **mapping)

{

  PartitionBoundInfo boundinfo;

  PartitionHashBound *hbounds;

  int     i;

  int     greatest_modulus;

  Datum    *boundDatums;

  boundinfo = palloc0_object(PartitionBoundInfoData);

  boundinfo->strategy = key->strategy;

  /* No special hash partitions. */

  boundinfo->null_index = -1;

  boundinfo->default_index = -1;

  hbounds = palloc_array(PartitionHashBound, nparts);

  /* Convert from node to the internal representation */

  for (i = 0; i < nparts; i++)

  {

    PartitionBoundSpec *spec = boundspecs[i];

    if (spec->strategy != PARTITION_STRATEGY_HASH)

      elog(ERROR, "invalid strategy in partition bound spec");

    hbounds[i].modulus = spec->modulus;

    hbounds[i].remainder = spec->remainder;

    hbounds[i].index = i;

  }

  /* Sort all the bounds in ascending order */

  qsort(hbounds, nparts, sizeof(PartitionHashBound),

      qsort_partition_hbound_cmp);

  /* After sorting, moduli are now stored in ascending order. */

  greatest_modulus = hbounds[nparts - 1].modulus;

  boundinfo->ndatums = nparts;

  boundinfo->datums = palloc0_array(Datum *, nparts);

  boundinfo->kind = NULL;

  boundinfo->interleaved_parts = NULL;

  boundinfo->nindexes = greatest_modulus;

  boundinfo->indexes = (int *) palloc(greatest_modulus * sizeof(int));

  for (i = 0; i < greatest_modulus; i++)

    boundinfo->indexes[i] = -1;

  /*

   * In the loop below, to save from allocating a series of small datum

   * arrays, here we just allocate a single array and below we'll just

   * assign a portion of this array per partition.

   */

  boundDatums = (Datum *) palloc(nparts * 2 * sizeof(Datum));

  /*

   * For hash partitioning, there are as many datums (modulus and remainder

   * pairs) as there are partitions.  Indexes are simply values ranging from

   * 0 to (nparts - 1).

   */

  for (i = 0; i < nparts; i++)

  {

    int     modulus = hbounds[i].modulus;

    int     remainder = hbounds[i].remainder;

    boundinfo->datums[i] = &boundDatums[i * 2];

    boundinfo->datums[i][0] = Int32GetDatum(modulus);

    boundinfo->datums[i][1] = Int32GetDatum(remainder);

    while (remainder < greatest_modulus)

    {

      /* overlap? */

      Assert(boundinfo->indexes[remainder] == -1);

      boundinfo->indexes[remainder] = i;

      remainder += modulus;

    }

    (*mapping)[hbounds[i].index] = i;

  }

  pfree(hbounds);

  return boundinfo;

}

/*

 * get_non_null_list_datum_count

 *    Counts the number of non-null Datums in each partition.

 */

static int

get_non_null_list_datum_count(PartitionBoundSpec **boundspecs, int nparts)

{

  int     i;

  int     count = 0;

  for (i = 0; i < nparts; i++)

  {

    ListCell   *lc;

    foreach(lc, boundspecs[i]->listdatums)

    {

      Const    *val = lfirst_node(Const, lc);

      if (!val->constisnull)

        count++;

    }

  }

  return count;

}

/*

 * create_list_bounds

 *    Create a PartitionBoundInfo for a list partitioned table

 */

static PartitionBoundInfo

create_list_bounds(PartitionBoundSpec **boundspecs, int nparts,

           PartitionKey key, int **mapping)

{

  PartitionBoundInfo boundinfo;

  PartitionListValue *all_values;

  int     i;

  int     j;

  int     ndatums;

  int     next_index = 0;

  int     default_index = -1;

  int     null_index = -1;

  Datum    *boundDatums;

  boundinfo = palloc0_object(PartitionBoundInfoData);

  boundinfo->strategy = key->strategy;

  /* Will be set correctly below. */

  boundinfo->null_index = -1;

  boundinfo->default_index = -1;

  ndatums = get_non_null_list_datum_count(boundspecs, nparts);

  all_values = (PartitionListValue *)

    palloc(ndatums * sizeof(PartitionListValue));

  /* Create a unified list of non-null values across all partitions. */

  for (j = 0, i = 0; i < nparts; i++)

  {

    PartitionBoundSpec *spec = boundspecs[i];

    ListCell   *c;

    if (spec->strategy != PARTITION_STRATEGY_LIST)

      elog(ERROR, "invalid strategy in partition bound spec");

    /*

     * Note the index of the partition bound spec for the default

     * partition.  There's no datum to add to the list on non-null datums

     * for this partition.

     */

    if (spec->is_default)

    {

      default_index = i;

      continue;

    }

    foreach(c, spec->listdatums)

    {

      Const    *val = lfirst_node(Const, c);

      if (!val->constisnull)

      {

        all_values[j].index = i;

        all_values[j].value = val->constvalue;

        j++;

      }

      else

      {

        /*

         * Never put a null into the values array; save the index of

         * the partition that stores nulls, instead.

         */

        if (null_index != -1)

          elog(ERROR, "found null more than once");

        null_index = i;

      }

    }

  }

  /* ensure we found a Datum for every slot in the all_values array */

  Assert(j == ndatums);

  qsort_arg(all_values, ndatums, sizeof(PartitionListValue),

        qsort_partition_list_value_cmp, key);

  boundinfo->ndatums = ndatums;

  boundinfo->datums = palloc0_array(Datum *, ndatums);

  boundinfo->kind = NULL;

  boundinfo->interleaved_parts = NULL;

  boundinfo->nindexes = ndatums;

  boundinfo->indexes = (int *) palloc(ndatums * sizeof(int));

  /*

   * In the loop below, to save from allocating a series of small datum

   * arrays, here we just allocate a single array and below we'll just

   * assign a portion of this array per datum.

   */

  boundDatums = (Datum *) palloc(ndatums * sizeof(Datum));

  /*

   * Copy values.  Canonical indexes are values ranging from 0 to (nparts -

   * 1) assigned to each partition such that all datums of a given partition

   * receive the same value. The value for a given partition is the index of

   * that partition's smallest datum in the all_values[] array.

   */

  for (i = 0; i < ndatums; i++)

  {

    int     orig_index = all_values[i].index;

    boundinfo->datums[i] = &boundDatums[i];

    boundinfo->datums[i][0] = datumCopy(all_values[i].value,

                      key->parttypbyval[0],

                      key->parttyplen[0]);

    /* If the old index has no mapping, assign one */

    if ((*mapping)[orig_index] == -1)

      (*mapping)[orig_index] = next_index++;

    boundinfo->indexes[i] = (*mapping)[orig_index];

  }

  pfree(all_values);

  /*

   * Set the canonical value for null_index, if any.

   *

   * It is possible that the null-accepting partition has not been assigned

   * an index yet, which could happen if such partition accepts only null

   * and hence not handled in the above loop which only looked at non-null

   * values.

   */

  if (null_index != -1)

  {

    Assert(null_index >= 0);

    if ((*mapping)[null_index] == -1)

      (*mapping)[null_index] = next_index++;

    boundinfo->null_index = (*mapping)[null_index];

  }

  /* Set the canonical value for default_index, if any. */

  if (default_index != -1)

  {

    /*

     * The default partition accepts any value not specified in the lists

     * of other partitions, hence it should not get mapped index while

     * assigning those for non-null datums.

     */

    Assert(default_index >= 0);

    Assert((*mapping)[default_index] == -1);

    (*mapping)[default_index] = next_index++;

    boundinfo->default_index = (*mapping)[default_index];

  }

  /*

   * Calculate interleaved partitions.  Here we look for partitions which

   * might be interleaved with other partitions and set a bit in

   * interleaved_parts for any partitions which may be interleaved with

   * another partition.

   */

  /*

   * There must be multiple partitions to have any interleaved partitions,

   * otherwise there's nothing to interleave with.

   */

  if (nparts > 1)

  {

    /*

     * Short-circuit check to see if only 1 Datum is allowed per

     * partition.  When this is true there's no need to do the more

     * expensive checks to look for interleaved values.

     */

    if (boundinfo->ndatums +

      partition_bound_accepts_nulls(boundinfo) +

      partition_bound_has_default(boundinfo) != nparts)

    {

      int     last_index = -1;

      /*

       * Since the indexes array is sorted in Datum order, if any

       * partitions are interleaved then it will show up by the

       * partition indexes not being in ascending order.  Here we check

       * for that and record all partitions that are out of order.

       */

      for (i = 0; i < boundinfo->nindexes; i++)

      {

        int     index = boundinfo->indexes[i];

        if (index < last_index)

          boundinfo->interleaved_parts = bms_add_member(boundinfo->interleaved_parts,

                                  index);

        /*

         * Otherwise, if the null_index exists in the indexes array,

         * then the NULL partition must also allow some other Datum,

         * therefore it's "interleaved".

         */

        else if (partition_bound_accepts_nulls(boundinfo) &&

             index == boundinfo->null_index)

          boundinfo->interleaved_parts = bms_add_member(boundinfo->interleaved_parts,

                                  index);

        last_index = index;

      }

    }

    /*

     * The DEFAULT partition is the "catch-all" partition that can contain

     * anything that does not belong to any other partition.  If there are

     * any other partitions then the DEFAULT partition must be marked as

     * interleaved.

     */

    if (partition_bound_has_default(boundinfo))

      boundinfo->interleaved_parts = bms_add_member(boundinfo->interleaved_parts,

                              boundinfo->default_index);

  }

  /* All partitions must now have been assigned canonical indexes. */

  Assert(next_index == nparts);

  return boundinfo;

}

/*

 * create_range_bounds

 *    Create a PartitionBoundInfo for a range partitioned table

 */

static PartitionBoundInfo

create_range_bounds(PartitionBoundSpec **boundspecs, int nparts,

          PartitionKey key, int **mapping)

{

  PartitionBoundInfo boundinfo;

  PartitionRangeBound **rbounds = NULL;

  PartitionRangeBound **all_bounds,

         *prev;

  int     i,

        k,

        partnatts;

  int     ndatums = 0;

  int     default_index = -1;

  int     next_index = 0;

  Datum    *boundDatums;

  PartitionRangeDatumKind *boundKinds;

  boundinfo = palloc0_object(PartitionBoundInfoData);

  boundinfo->strategy = key->strategy;

  /* There is no special null-accepting range partition. */

  boundinfo->null_index = -1;

  /* Will be set correctly below. */

  boundinfo->default_index = -1;

  all_bounds = palloc0_array(PartitionRangeBound *, 2 * nparts);

  /* Create a unified list of range bounds across all the partitions. */

  ndatums = 0;

  for (i = 0; i < nparts; i++)

  {

    PartitionBoundSpec *spec = boundspecs[i];

    PartitionRangeBound *lower,

           *upper;

    if (spec->strategy != PARTITION_STRATEGY_RANGE)

      elog(ERROR, "invalid strategy in partition bound spec");

    /*

     * Note the index of the partition bound spec for the default

     * partition.  There's no datum to add to the all_bounds array for

     * this partition.

     */

    if (spec->is_default)

    {

      default_index = i;

      continue;

    }

    lower = make_one_partition_rbound(key, i, spec->lowerdatums, true);

    upper = make_one_partition_rbound(key, i, spec->upperdatums, false);

    all_bounds[ndatums++] = lower;

    all_bounds[ndatums++] = upper;

  }

  Assert(ndatums == nparts * 2 ||

       (default_index != -1 && ndatums == (nparts - 1) * 2));

  /* Sort all the bounds in ascending order */

  qsort_arg(all_bounds, ndatums,

        sizeof(PartitionRangeBound *),

        qsort_partition_rbound_cmp,

        key);

  /* Save distinct bounds from all_bounds into rbounds. */

  rbounds = (PartitionRangeBound **)

    palloc(ndatums * sizeof(PartitionRangeBound *));

  k = 0;

  prev = NULL;

  for (i = 0; i < ndatums; i++)

  {

    PartitionRangeBound *cur = all_bounds[i];

    bool    is_distinct = false;

    int     j;

    /* Is the current bound distinct from the previous one? */

    for (j = 0; j < key->partnatts; j++)

    {

      Datum   cmpval;

      if (prev == NULL || cur->kind[j] != prev->kind[j])

      {

        is_distinct = true;

        break;

      }

      /*

       * If the bounds are both MINVALUE or MAXVALUE, stop now and treat

       * them as equal, since any values after this point must be

       * ignored.

       */

      if (cur->kind[j] != PARTITION_RANGE_DATUM_VALUE)

        break;

      cmpval = FunctionCall2Coll(&key->partsupfunc[j],

                     key->partcollation[j],

                     cur->datums[j],

                     prev->datums[j]);

      if (DatumGetInt32(cmpval) != 0)

      {

        is_distinct = true;

        break;

      }

    }

    /*

     * Only if the bound is distinct save it into a temporary array, i.e,

     * rbounds which is later copied into boundinfo datums array.

     */

    if (is_distinct)

      rbounds[k++] = all_bounds[i];

    prev = cur;

  }

  pfree(all_bounds);

  /* Update ndatums to hold the count of distinct datums. */

  ndatums = k;

  /*

   * Add datums to boundinfo.  Canonical indexes are values ranging from 0

   * to nparts - 1, assigned in that order to each partition's upper bound.

   * For 'datums' elements that are lower bounds, there is -1 in the

   * 'indexes' array to signify that no partition exists for the values less

   * than such a bound and greater than or equal to the previous upper

   * bound.

   */

  boundinfo->ndatums = ndatums;

  boundinfo->datums = palloc0_array(Datum *, ndatums);

  boundinfo->kind = palloc0_array(PartitionRangeDatumKind *, ndatums);

  boundinfo->interleaved_parts = NULL;

  /*

   * For range partitioning, an additional value of -1 is stored as the last

   * element of the indexes[] array.

   */

  boundinfo->nindexes = ndatums + 1;

  boundinfo->indexes = palloc_array(int, (ndatums + 1));

  /*

   * In the loop below, to save from allocating a series of small arrays,

   * here we just allocate a single array for Datums and another for

   * PartitionRangeDatumKinds, below we'll just assign a portion of these

   * arrays in each loop.

   */

  partnatts = key->partnatts;

  boundDatums = (Datum *) palloc(ndatums * partnatts * sizeof(Datum));

  boundKinds = palloc_array(PartitionRangeDatumKind, ndatums * partnatts);

  for (i = 0; i < ndatums; i++)

  {

    int     j;

    boundinfo->datums[i] = &boundDatums[i * partnatts];

    boundinfo->kind[i] = &boundKinds[i * partnatts];

    for (j = 0; j < partnatts; j++)

    {

      if (rbounds[i]->kind[j] == PARTITION_RANGE_DATUM_VALUE)

        boundinfo->datums[i][j] =

          datumCopy(rbounds[i]->datums[j],

                key->parttypbyval[j],

                key->parttyplen[j]);

      boundinfo->kind[i][j] = rbounds[i]->kind[j];

    }

    /*

     * There is no mapping for invalid indexes.

     *

     * Any lower bounds in the rbounds array have invalid indexes

     * assigned, because the values between the previous bound (if there

     * is one) and this (lower) bound are not part of the range of any

     * existing partition.

     */

    if (rbounds[i]->lower)

      boundinfo->indexes[i] = -1;

    else

    {

      int     orig_index = rbounds[i]->index;

      /* If the old index has no mapping, assign one */

      if ((*mapping)[orig_index] == -1)

        (*mapping)[orig_index] = next_index++;

      boundinfo->indexes[i] = (*mapping)[orig_index];

    }

  }

  pfree(rbounds);

  /* Set the canonical value for default_index, if any. */

  if (default_index != -1)

  {

    Assert(default_index >= 0 && (*mapping)[default_index] == -1);

    (*mapping)[default_index] = next_index++;

    boundinfo->default_index = (*mapping)[default_index];

  }

  /* The extra -1 element. */

  Assert(i == ndatums);

  boundinfo->indexes[i] = -1;

  /* All partitions must now have been assigned canonical indexes. */

  Assert(next_index == nparts);

  return boundinfo;

}

/*

 * Are two partition bound collections logically equal?

 *

 * Used in the keep logic of relcache.c (ie, in RelationClearRelation()).

 * This is also useful when b1 and b2 are bound collections of two separate

 * relations, respectively, because PartitionBoundInfo is a canonical

 * representation of partition bounds.

 */

bool

partition_bounds_equal(int partnatts, int16 *parttyplen, bool *parttypbyval,

             PartitionBoundInfo b1, PartitionBoundInfo b2)

{

  int     i;

  if (b1->strategy != b2->strategy)

    return false;

  if (b1->ndatums != b2->ndatums)

    return false;

  if (b1->nindexes != b2->nindexes)

    return false;

  if (b1->null_index != b2->null_index)

    return false;

  if (b1->default_index != b2->default_index)

    return false;

  /* For all partition strategies, the indexes[] arrays have to match */

  for (i = 0; i < b1->nindexes; i++)

  {

    if (b1->indexes[i] != b2->indexes[i])

      return false;

  }

  /* Finally, compare the datums[] arrays */

  if (b1->strategy == PARTITION_STRATEGY_HASH)

  {

    /*

     * We arrange the partitions in the ascending order of their moduli

     * and remainders.  Also every modulus is factor of next larger

     * modulus.  Therefore we can safely store index of a given partition

     * in indexes array at remainder of that partition.  Also entries at

     * (remainder + N * modulus) positions in indexes array are all same

     * for (modulus, remainder) specification for any partition.  Thus the

     * datums arrays from the given bounds are the same, if and only if

     * their indexes arrays are the same.  So, it suffices to compare the

     * indexes arrays.

     *

     * Nonetheless make sure that the bounds are indeed the same when the

     * indexes match.  Hash partition bound stores modulus and remainder

     * at b1->datums[i][0] and b1->datums[i][1] position respectively.

     */

#ifdef USE_ASSERT_CHECKING

    for (i = 0; i < b1->ndatums; i++)

      Assert((b1->datums[i][0] == b2->datums[i][0] &&

          b1->datums[i][1] == b2->datums[i][1]));

#endif

  }

  else

  {

    for (i = 0; i < b1->ndatums; i++)

    {

      int     j;

      for (j = 0; j < partnatts; j++)

      {

        /* For range partitions, the bounds might not be finite. */

        if (b1->kind != NULL)

        {

          /* The different kinds of bound all differ from each other */

          if (b1->kind[i][j] != b2->kind[i][j])

            return false;

          /*

           * Non-finite bounds are equal without further

           * examination.

           */

          if (b1->kind[i][j] != PARTITION_RANGE_DATUM_VALUE)

            continue;

        }

        /*

         * Compare the actual values. Note that it would be both

         * incorrect and unsafe to invoke the comparison operator

         * derived from the partitioning specification here.  It would

         * be incorrect because we want the relcache entry to be

         * updated for ANY change to the partition bounds, not just

         * those that the partitioning operator thinks are

         * significant.  It would be unsafe because we might reach

         * this code in the context of an aborted transaction, and an

         * arbitrary partitioning operator might not be safe in that

         * context.  datumIsEqual() should be simple enough to be

         * safe.

         */