PostgreSQL Source Code  git master
partbounds.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * partbounds.c
4  * Support routines for manipulating partition bounds
5  *
6  * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
7  * Portions Copyright (c) 1994, Regents of the University of California
8  *
9  * IDENTIFICATION
10  * src/backend/partitioning/partbounds.c
11  *
12  *-------------------------------------------------------------------------
13  */
14 
15 #include "postgres.h"
16 
17 #include "access/relation.h"
18 #include "access/table.h"
19 #include "access/tableam.h"
20 #include "catalog/partition.h"
21 #include "catalog/pg_inherits.h"
22 #include "catalog/pg_type.h"
23 #include "commands/tablecmds.h"
24 #include "common/hashfn.h"
25 #include "executor/executor.h"
26 #include "miscadmin.h"
27 #include "nodes/makefuncs.h"
28 #include "nodes/nodeFuncs.h"
29 #include "nodes/pathnodes.h"
30 #include "parser/parse_coerce.h"
32 #include "partitioning/partdesc.h"
33 #include "partitioning/partprune.h"
34 #include "utils/builtins.h"
35 #include "utils/datum.h"
36 #include "utils/fmgroids.h"
37 #include "utils/lsyscache.h"
38 #include "utils/partcache.h"
39 #include "utils/ruleutils.h"
40 #include "utils/snapmgr.h"
41 #include "utils/syscache.h"
42 
43 /*
44  * When qsort'ing partition bounds after reading from the catalog, each bound
45  * is represented with one of the following structs.
46  */
47 
48 /* One bound of a hash partition */
49 typedef struct PartitionHashBound
50 {
51  int modulus;
52  int remainder;
53  int index;
55 
56 /* One value coming from some (index'th) list partition */
57 typedef struct PartitionListValue
58 {
59  int index;
62 
63 /* One bound of a range partition */
64 typedef struct PartitionRangeBound
65 {
66  int index;
67  Datum *datums; /* range bound datums */
68  PartitionRangeDatumKind *kind; /* the kind of each datum */
69  bool lower; /* this is the lower (vs upper) bound */
71 
72 /*
73  * Mapping from partitions of a joining relation to partitions of a join
74  * relation being computed (a.k.a merged partitions)
75  */
76 typedef struct PartitionMap
77 {
78  int nparts; /* number of partitions */
79  int *merged_indexes; /* indexes of merged partitions */
80  bool *merged; /* flags to indicate whether partitions are
81  * merged with non-dummy partitions */
82  bool did_remapping; /* did we re-map partitions? */
83  int *old_indexes; /* old indexes of merged partitions if
84  * did_remapping */
85 } PartitionMap;
86 
87 /* Macro for comparing two range bounds */
88 #define compare_range_bounds(partnatts, partsupfunc, partcollations, \
89  bound1, bound2) \
90  (partition_rbound_cmp(partnatts, partsupfunc, partcollations, \
91  (bound1)->datums, (bound1)->kind, (bound1)->lower, \
92  bound2))
93 
94 static int32 qsort_partition_hbound_cmp(const void *a, const void *b);
95 static int32 qsort_partition_list_value_cmp(const void *a, const void *b,
96  void *arg);
97 static int32 qsort_partition_rbound_cmp(const void *a, const void *b,
98  void *arg);
100  int nparts, PartitionKey key, int **mapping);
102  int nparts, PartitionKey key, int **mapping);
104  int nparts, PartitionKey key, int **mapping);
105 static PartitionBoundInfo merge_list_bounds(FmgrInfo *partsupfunc,
106  Oid *collations,
107  RelOptInfo *outer_rel,
108  RelOptInfo *inner_rel,
109  JoinType jointype,
110  List **outer_parts,
111  List **inner_parts);
112 static PartitionBoundInfo merge_range_bounds(int partnatts,
113  FmgrInfo *partsupfuncs,
114  Oid *partcollations,
115  RelOptInfo *outer_rel,
116  RelOptInfo *inner_rel,
117  JoinType jointype,
118  List **outer_parts,
119  List **inner_parts);
120 static void init_partition_map(RelOptInfo *rel, PartitionMap *map);
121 static void free_partition_map(PartitionMap *map);
122 static bool is_dummy_partition(RelOptInfo *rel, int part_index);
123 static int merge_matching_partitions(PartitionMap *outer_map,
124  PartitionMap *inner_map,
125  int outer_part,
126  int inner_part,
127  int *next_index);
128 static int process_outer_partition(PartitionMap *outer_map,
129  PartitionMap *inner_map,
130  bool outer_has_default,
131  bool inner_has_default,
132  int outer_index,
133  int inner_default,
134  JoinType jointype,
135  int *next_index,
136  int *default_index);
137 static int process_inner_partition(PartitionMap *outer_map,
138  PartitionMap *inner_map,
139  bool outer_has_default,
140  bool inner_has_default,
141  int inner_index,
142  int outer_default,
143  JoinType jointype,
144  int *next_index,
145  int *default_index);
146 static void merge_null_partitions(PartitionMap *outer_map,
147  PartitionMap *inner_map,
148  bool outer_has_null,
149  bool inner_has_null,
150  int outer_null,
151  int inner_null,
152  JoinType jointype,
153  int *next_index,
154  int *null_index);
155 static void merge_default_partitions(PartitionMap *outer_map,
156  PartitionMap *inner_map,
157  bool outer_has_default,
158  bool inner_has_default,
159  int outer_default,
160  int inner_default,
161  JoinType jointype,
162  int *next_index,
163  int *default_index);
164 static int merge_partition_with_dummy(PartitionMap *map, int index,
165  int *next_index);
166 static void fix_merged_indexes(PartitionMap *outer_map,
167  PartitionMap *inner_map,
168  int nmerged, List *merged_indexes);
169 static void generate_matching_part_pairs(RelOptInfo *outer_rel,
170  RelOptInfo *inner_rel,
171  PartitionMap *outer_map,
172  PartitionMap *inner_map,
173  int nmerged,
174  List **outer_parts,
175  List **inner_parts);
177  List *merged_datums,
178  List *merged_kinds,
179  List *merged_indexes,
180  int null_index,
181  int default_index);
182 static int get_range_partition(RelOptInfo *rel,
184  int *lb_pos,
186  PartitionRangeBound *ub);
188  int *lb_pos,
190  PartitionRangeBound *ub);
191 static bool compare_range_partitions(int partnatts, FmgrInfo *partsupfuncs,
192  Oid *partcollations,
193  PartitionRangeBound *outer_lb,
194  PartitionRangeBound *outer_ub,
195  PartitionRangeBound *inner_lb,
196  PartitionRangeBound *inner_ub,
197  int *lb_cmpval, int *ub_cmpval);
198 static void get_merged_range_bounds(int partnatts, FmgrInfo *partsupfuncs,
199  Oid *partcollations, JoinType jointype,
200  PartitionRangeBound *outer_lb,
201  PartitionRangeBound *outer_ub,
202  PartitionRangeBound *inner_lb,
203  PartitionRangeBound *inner_ub,
204  int lb_cmpval, int ub_cmpval,
205  PartitionRangeBound *merged_lb,
206  PartitionRangeBound *merged_ub);
207 static void add_merged_range_bounds(int partnatts, FmgrInfo *partsupfuncs,
208  Oid *partcollations,
209  PartitionRangeBound *merged_lb,
210  PartitionRangeBound *merged_ub,
211  int merged_index,
212  List **merged_datums,
213  List **merged_kinds,
214  List **merged_indexes);
216  List *datums, bool lower);
217 static int32 partition_hbound_cmp(int modulus1, int remainder1, int modulus2,
218  int remainder2);
219 static int32 partition_rbound_cmp(int partnatts, FmgrInfo *partsupfunc,
220  Oid *partcollation, Datum *datums1,
221  PartitionRangeDatumKind *kind1, bool lower1,
222  PartitionRangeBound *b2);
223 static int partition_range_bsearch(int partnatts, FmgrInfo *partsupfunc,
224  Oid *partcollation,
225  PartitionBoundInfo boundinfo,
226  PartitionRangeBound *probe, int32 *cmpval);
228 static Expr *make_partition_op_expr(PartitionKey key, int keynum,
229  uint16 strategy, Expr *arg1, Expr *arg2);
231  StrategyNumber strategy, bool *need_relabel);
232 static List *get_qual_for_hash(Relation parent, PartitionBoundSpec *spec);
233 static List *get_qual_for_list(Relation parent, PartitionBoundSpec *spec);
234 static List *get_qual_for_range(Relation parent, PartitionBoundSpec *spec,
235  bool for_default);
236 static void get_range_key_properties(PartitionKey key, int keynum,
237  PartitionRangeDatum *ldatum,
238  PartitionRangeDatum *udatum,
239  ListCell **partexprs_item,
240  Expr **keyCol,
241  Const **lower_val, Const **upper_val);
243 
244 /*
245  * get_qual_from_partbound
246  * Given a parser node for partition bound, return the list of executable
247  * expressions as partition constraint
248  */
249 List *
251  PartitionBoundSpec *spec)
252 {
254  List *my_qual = NIL;
255 
256  Assert(key != NULL);
257 
258  switch (key->strategy)
259  {
262  my_qual = get_qual_for_hash(parent, spec);
263  break;
264 
267  my_qual = get_qual_for_list(parent, spec);
268  break;
269 
272  my_qual = get_qual_for_range(parent, spec, false);
273  break;
274 
275  default:
276  elog(ERROR, "unexpected partition strategy: %d",
277  (int) key->strategy);
278  }
279 
280  return my_qual;
281 }
282 
283 /*
284  * partition_bounds_create
285  * Build a PartitionBoundInfo struct from a list of PartitionBoundSpec
286  * nodes
287  *
288  * This function creates a PartitionBoundInfo and fills the values of its
289  * various members based on the input list. Importantly, 'datums' array will
290  * contain Datum representation of individual bounds (possibly after
291  * de-duplication as in case of range bounds), sorted in a canonical order
292  * defined by qsort_partition_* functions of respective partitioning methods.
293  * 'indexes' array will contain as many elements as there are bounds (specific
294  * exceptions to this rule are listed in the function body), which represent
295  * the 0-based canonical positions of partitions.
296  *
297  * Upon return from this function, *mapping is set to an array of
298  * list_length(boundspecs) elements, each of which maps the original index of
299  * a partition to its canonical index.
300  *
301  * Note: The objects returned by this function are wholly allocated in the
302  * current memory context.
303  */
306  PartitionKey key, int **mapping)
307 {
308  int i;
309 
310  Assert(nparts > 0);
311 
312  /*
313  * For each partitioning method, we first convert the partition bounds
314  * from their parser node representation to the internal representation,
315  * along with any additional preprocessing (such as de-duplicating range
316  * bounds). Resulting bound datums are then added to the 'datums' array
317  * in PartitionBoundInfo. For each datum added, an integer indicating the
318  * canonical partition index is added to the 'indexes' array.
319  *
320  * For each bound, we remember its partition's position (0-based) in the
321  * original list to later map it to the canonical index.
322  */
323 
324  /*
325  * Initialize mapping array with invalid values, this is filled within
326  * each sub-routine below depending on the bound type.
327  */
328  *mapping = (int *) palloc(sizeof(int) * nparts);
329  for (i = 0; i < nparts; i++)
330  (*mapping)[i] = -1;
331 
332  switch (key->strategy)
333  {
335  return create_hash_bounds(boundspecs, nparts, key, mapping);
336 
338  return create_list_bounds(boundspecs, nparts, key, mapping);
339 
341  return create_range_bounds(boundspecs, nparts, key, mapping);
342 
343  default:
344  elog(ERROR, "unexpected partition strategy: %d",
345  (int) key->strategy);
346  break;
347  }
348 
349  Assert(false);
350  return NULL; /* keep compiler quiet */
351 }
352 
353 /*
354  * create_hash_bounds
355  * Create a PartitionBoundInfo for a hash partitioned table
356  */
357 static PartitionBoundInfo
358 create_hash_bounds(PartitionBoundSpec **boundspecs, int nparts,
359  PartitionKey key, int **mapping)
360 {
361  PartitionBoundInfo boundinfo;
362  PartitionHashBound **hbounds = NULL;
363  int i;
364  int ndatums = 0;
365  int greatest_modulus;
366 
367  boundinfo = (PartitionBoundInfoData *)
369  boundinfo->strategy = key->strategy;
370  /* No special hash partitions. */
371  boundinfo->null_index = -1;
372  boundinfo->default_index = -1;
373 
374  ndatums = nparts;
375  hbounds = (PartitionHashBound **)
376  palloc(nparts * sizeof(PartitionHashBound *));
377 
378  /* Convert from node to the internal representation */
379  for (i = 0; i < nparts; i++)
380  {
381  PartitionBoundSpec *spec = boundspecs[i];
382 
383  if (spec->strategy != PARTITION_STRATEGY_HASH)
384  elog(ERROR, "invalid strategy in partition bound spec");
385 
386  hbounds[i] = (PartitionHashBound *) palloc(sizeof(PartitionHashBound));
387  hbounds[i]->modulus = spec->modulus;
388  hbounds[i]->remainder = spec->remainder;
389  hbounds[i]->index = i;
390  }
391 
392  /* Sort all the bounds in ascending order */
393  qsort(hbounds, nparts, sizeof(PartitionHashBound *),
395 
396  /* After sorting, moduli are now stored in ascending order. */
397  greatest_modulus = hbounds[ndatums - 1]->modulus;
398 
399  boundinfo->ndatums = ndatums;
400  boundinfo->datums = (Datum **) palloc0(ndatums * sizeof(Datum *));
401  boundinfo->indexes = (int *) palloc(greatest_modulus * sizeof(int));
402  for (i = 0; i < greatest_modulus; i++)
403  boundinfo->indexes[i] = -1;
404 
405  /*
406  * For hash partitioning, there are as many datums (modulus and remainder
407  * pairs) as there are partitions. Indexes are simply values ranging from
408  * 0 to (nparts - 1).
409  */
410  for (i = 0; i < nparts; i++)
411  {
412  int modulus = hbounds[i]->modulus;
413  int remainder = hbounds[i]->remainder;
414 
415  boundinfo->datums[i] = (Datum *) palloc(2 * sizeof(Datum));
416  boundinfo->datums[i][0] = Int32GetDatum(modulus);
417  boundinfo->datums[i][1] = Int32GetDatum(remainder);
418 
419  while (remainder < greatest_modulus)
420  {
421  /* overlap? */
422  Assert(boundinfo->indexes[remainder] == -1);
423  boundinfo->indexes[remainder] = i;
424  remainder += modulus;
425  }
426 
427  (*mapping)[hbounds[i]->index] = i;
428  pfree(hbounds[i]);
429  }
430  pfree(hbounds);
431 
432  return boundinfo;
433 }
434 
435 /*
436  * create_list_bounds
437  * Create a PartitionBoundInfo for a list partitioned table
438  */
439 static PartitionBoundInfo
440 create_list_bounds(PartitionBoundSpec **boundspecs, int nparts,
441  PartitionKey key, int **mapping)
442 {
443  PartitionBoundInfo boundinfo;
444  PartitionListValue **all_values = NULL;
445  ListCell *cell;
446  int i = 0;
447  int ndatums = 0;
448  int next_index = 0;
449  int default_index = -1;
450  int null_index = -1;
451  List *non_null_values = NIL;
452 
453  boundinfo = (PartitionBoundInfoData *)
455  boundinfo->strategy = key->strategy;
456  /* Will be set correctly below. */
457  boundinfo->null_index = -1;
458  boundinfo->default_index = -1;
459 
460  /* Create a unified list of non-null values across all partitions. */
461  for (i = 0; i < nparts; i++)
462  {
463  PartitionBoundSpec *spec = boundspecs[i];
464  ListCell *c;
465 
466  if (spec->strategy != PARTITION_STRATEGY_LIST)
467  elog(ERROR, "invalid strategy in partition bound spec");
468 
469  /*
470  * Note the index of the partition bound spec for the default
471  * partition. There's no datum to add to the list on non-null datums
472  * for this partition.
473  */
474  if (spec->is_default)
475  {
476  default_index = i;
477  continue;
478  }
479 
480  foreach(c, spec->listdatums)
481  {
482  Const *val = castNode(Const, lfirst(c));
483  PartitionListValue *list_value = NULL;
484 
485  if (!val->constisnull)
486  {
487  list_value = (PartitionListValue *)
488  palloc0(sizeof(PartitionListValue));
489  list_value->index = i;
490  list_value->value = val->constvalue;
491  }
492  else
493  {
494  /*
495  * Never put a null into the values array; save the index of
496  * the partition that stores nulls, instead.
497  */
498  if (null_index != -1)
499  elog(ERROR, "found null more than once");
500  null_index = i;
501  }
502 
503  if (list_value)
504  non_null_values = lappend(non_null_values, list_value);
505  }
506  }
507 
508  ndatums = list_length(non_null_values);
509 
510  /*
511  * Collect all list values in one array. Alongside the value, we also save
512  * the index of partition the value comes from.
513  */
514  all_values = (PartitionListValue **)
515  palloc(ndatums * sizeof(PartitionListValue *));
516  i = 0;
517  foreach(cell, non_null_values)
518  {
519  PartitionListValue *src = lfirst(cell);
520 
521  all_values[i] = (PartitionListValue *)
522  palloc(sizeof(PartitionListValue));
523  all_values[i]->value = src->value;
524  all_values[i]->index = src->index;
525  i++;
526  }
527 
528  qsort_arg(all_values, ndatums, sizeof(PartitionListValue *),
529  qsort_partition_list_value_cmp, (void *) key);
530 
531  boundinfo->ndatums = ndatums;
532  boundinfo->datums = (Datum **) palloc0(ndatums * sizeof(Datum *));
533  boundinfo->indexes = (int *) palloc(ndatums * sizeof(int));
534 
535  /*
536  * Copy values. Canonical indexes are values ranging from 0 to (nparts -
537  * 1) assigned to each partition such that all datums of a given partition
538  * receive the same value. The value for a given partition is the index of
539  * that partition's smallest datum in the all_values[] array.
540  */
541  for (i = 0; i < ndatums; i++)
542  {
543  int orig_index = all_values[i]->index;
544 
545  boundinfo->datums[i] = (Datum *) palloc(sizeof(Datum));
546  boundinfo->datums[i][0] = datumCopy(all_values[i]->value,
547  key->parttypbyval[0],
548  key->parttyplen[0]);
549 
550  /* If the old index has no mapping, assign one */
551  if ((*mapping)[orig_index] == -1)
552  (*mapping)[orig_index] = next_index++;
553 
554  boundinfo->indexes[i] = (*mapping)[orig_index];
555  }
556 
557  /*
558  * Set the canonical value for null_index, if any.
559  *
560  * It is possible that the null-accepting partition has not been assigned
561  * an index yet, which could happen if such partition accepts only null
562  * and hence not handled in the above loop which only looked at non-null
563  * values.
564  */
565  if (null_index != -1)
566  {
567  Assert(null_index >= 0);
568  if ((*mapping)[null_index] == -1)
569  (*mapping)[null_index] = next_index++;
570  boundinfo->null_index = (*mapping)[null_index];
571  }
572 
573  /* Set the canonical value for default_index, if any. */
574  if (default_index != -1)
575  {
576  /*
577  * The default partition accepts any value not specified in the lists
578  * of other partitions, hence it should not get mapped index while
579  * assigning those for non-null datums.
580  */
581  Assert(default_index >= 0);
582  Assert((*mapping)[default_index] == -1);
583  (*mapping)[default_index] = next_index++;
584  boundinfo->default_index = (*mapping)[default_index];
585  }
586 
587  /* All partitions must now have been assigned canonical indexes. */
588  Assert(next_index == nparts);
589  return boundinfo;
590 }
591 
592 /*
593  * create_range_bounds
594  * Create a PartitionBoundInfo for a range partitioned table
595  */
596 static PartitionBoundInfo
597 create_range_bounds(PartitionBoundSpec **boundspecs, int nparts,
598  PartitionKey key, int **mapping)
599 {
600  PartitionBoundInfo boundinfo;
601  PartitionRangeBound **rbounds = NULL;
602  PartitionRangeBound **all_bounds,
603  *prev;
604  int i,
605  k;
606  int ndatums = 0;
607  int default_index = -1;
608  int next_index = 0;
609 
610  boundinfo = (PartitionBoundInfoData *)
612  boundinfo->strategy = key->strategy;
613  /* There is no special null-accepting range partition. */
614  boundinfo->null_index = -1;
615  /* Will be set correctly below. */
616  boundinfo->default_index = -1;
617 
618  all_bounds = (PartitionRangeBound **)
619  palloc0(2 * nparts * sizeof(PartitionRangeBound *));
620 
621  /* Create a unified list of range bounds across all the partitions. */
622  ndatums = 0;
623  for (i = 0; i < nparts; i++)
624  {
625  PartitionBoundSpec *spec = boundspecs[i];
627  *upper;
628 
629  if (spec->strategy != PARTITION_STRATEGY_RANGE)
630  elog(ERROR, "invalid strategy in partition bound spec");
631 
632  /*
633  * Note the index of the partition bound spec for the default
634  * partition. There's no datum to add to the all_bounds array for
635  * this partition.
636  */
637  if (spec->is_default)
638  {
639  default_index = i;
640  continue;
641  }
642 
643  lower = make_one_partition_rbound(key, i, spec->lowerdatums, true);
644  upper = make_one_partition_rbound(key, i, spec->upperdatums, false);
645  all_bounds[ndatums++] = lower;
646  all_bounds[ndatums++] = upper;
647  }
648 
649  Assert(ndatums == nparts * 2 ||
650  (default_index != -1 && ndatums == (nparts - 1) * 2));
651 
652  /* Sort all the bounds in ascending order */
653  qsort_arg(all_bounds, ndatums,
654  sizeof(PartitionRangeBound *),
656  (void *) key);
657 
658  /* Save distinct bounds from all_bounds into rbounds. */
659  rbounds = (PartitionRangeBound **)
660  palloc(ndatums * sizeof(PartitionRangeBound *));
661  k = 0;
662  prev = NULL;
663  for (i = 0; i < ndatums; i++)
664  {
665  PartitionRangeBound *cur = all_bounds[i];
666  bool is_distinct = false;
667  int j;
668 
669  /* Is the current bound distinct from the previous one? */
670  for (j = 0; j < key->partnatts; j++)
671  {
672  Datum cmpval;
673 
674  if (prev == NULL || cur->kind[j] != prev->kind[j])
675  {
676  is_distinct = true;
677  break;
678  }
679 
680  /*
681  * If the bounds are both MINVALUE or MAXVALUE, stop now and treat
682  * them as equal, since any values after this point must be
683  * ignored.
684  */
685  if (cur->kind[j] != PARTITION_RANGE_DATUM_VALUE)
686  break;
687 
688  cmpval = FunctionCall2Coll(&key->partsupfunc[j],
689  key->partcollation[j],
690  cur->datums[j],
691  prev->datums[j]);
692  if (DatumGetInt32(cmpval) != 0)
693  {
694  is_distinct = true;
695  break;
696  }
697  }
698 
699  /*
700  * Only if the bound is distinct save it into a temporary array, i.e,
701  * rbounds which is later copied into boundinfo datums array.
702  */
703  if (is_distinct)
704  rbounds[k++] = all_bounds[i];
705 
706  prev = cur;
707  }
708 
709  /* Update ndatums to hold the count of distinct datums. */
710  ndatums = k;
711 
712  /*
713  * Add datums to boundinfo. Canonical indexes are values ranging from 0
714  * to nparts - 1, assigned in that order to each partition's upper bound.
715  * For 'datums' elements that are lower bounds, there is -1 in the
716  * 'indexes' array to signify that no partition exists for the values less
717  * than such a bound and greater than or equal to the previous upper
718  * bound.
719  */
720  boundinfo->ndatums = ndatums;
721  boundinfo->datums = (Datum **) palloc0(ndatums * sizeof(Datum *));
722  boundinfo->kind = (PartitionRangeDatumKind **)
723  palloc(ndatums *
724  sizeof(PartitionRangeDatumKind *));
725 
726  /*
727  * For range partitioning, an additional value of -1 is stored as the last
728  * element.
729  */
730  boundinfo->indexes = (int *) palloc((ndatums + 1) * sizeof(int));
731 
732  for (i = 0; i < ndatums; i++)
733  {
734  int j;
735 
736  boundinfo->datums[i] = (Datum *) palloc(key->partnatts *
737  sizeof(Datum));
738  boundinfo->kind[i] = (PartitionRangeDatumKind *)
739  palloc(key->partnatts *
740  sizeof(PartitionRangeDatumKind));
741  for (j = 0; j < key->partnatts; j++)
742  {
743  if (rbounds[i]->kind[j] == PARTITION_RANGE_DATUM_VALUE)
744  boundinfo->datums[i][j] =
745  datumCopy(rbounds[i]->datums[j],
746  key->parttypbyval[j],
747  key->parttyplen[j]);
748  boundinfo->kind[i][j] = rbounds[i]->kind[j];
749  }
750 
751  /*
752  * There is no mapping for invalid indexes.
753  *
754  * Any lower bounds in the rbounds array have invalid indexes
755  * assigned, because the values between the previous bound (if there
756  * is one) and this (lower) bound are not part of the range of any
757  * existing partition.
758  */
759  if (rbounds[i]->lower)
760  boundinfo->indexes[i] = -1;
761  else
762  {
763  int orig_index = rbounds[i]->index;
764 
765  /* If the old index has no mapping, assign one */
766  if ((*mapping)[orig_index] == -1)
767  (*mapping)[orig_index] = next_index++;
768 
769  boundinfo->indexes[i] = (*mapping)[orig_index];
770  }
771  }
772 
773  /* Set the canonical value for default_index, if any. */
774  if (default_index != -1)
775  {
776  Assert(default_index >= 0 && (*mapping)[default_index] == -1);
777  (*mapping)[default_index] = next_index++;
778  boundinfo->default_index = (*mapping)[default_index];
779  }
780 
781  /* The extra -1 element. */
782  Assert(i == ndatums);
783  boundinfo->indexes[i] = -1;
784 
785  /* All partitions must now have been assigned canonical indexes. */
786  Assert(next_index == nparts);
787  return boundinfo;
788 }
789 
790 /*
791  * Are two partition bound collections logically equal?
792  *
793  * Used in the keep logic of relcache.c (ie, in RelationClearRelation()).
794  * This is also useful when b1 and b2 are bound collections of two separate
795  * relations, respectively, because PartitionBoundInfo is a canonical
796  * representation of partition bounds.
797  */
798 bool
799 partition_bounds_equal(int partnatts, int16 *parttyplen, bool *parttypbyval,
801 {
802  int i;
803 
804  if (b1->strategy != b2->strategy)
805  return false;
806 
807  if (b1->ndatums != b2->ndatums)
808  return false;
809 
810  if (b1->null_index != b2->null_index)
811  return false;
812 
813  if (b1->default_index != b2->default_index)
814  return false;
815 
817  {
818  int greatest_modulus = get_hash_partition_greatest_modulus(b1);
819 
820  /*
821  * If two hash partitioned tables have different greatest moduli,
822  * their partition schemes don't match.
823  */
824  if (greatest_modulus != get_hash_partition_greatest_modulus(b2))
825  return false;
826 
827  /*
828  * We arrange the partitions in the ascending order of their moduli
829  * and remainders. Also every modulus is factor of next larger
830  * modulus. Therefore we can safely store index of a given partition
831  * in indexes array at remainder of that partition. Also entries at
832  * (remainder + N * modulus) positions in indexes array are all same
833  * for (modulus, remainder) specification for any partition. Thus
834  * datums array from both the given bounds are same, if and only if
835  * their indexes array will be same. So, it suffices to compare
836  * indexes array.
837  */
838  for (i = 0; i < greatest_modulus; i++)
839  if (b1->indexes[i] != b2->indexes[i])
840  return false;
841 
842 #ifdef USE_ASSERT_CHECKING
843 
844  /*
845  * Nonetheless make sure that the bounds are indeed same when the
846  * indexes match. Hash partition bound stores modulus and remainder
847  * at b1->datums[i][0] and b1->datums[i][1] position respectively.
848  */
849  for (i = 0; i < b1->ndatums; i++)
850  Assert((b1->datums[i][0] == b2->datums[i][0] &&
851  b1->datums[i][1] == b2->datums[i][1]));
852 #endif
853  }
854  else
855  {
856  for (i = 0; i < b1->ndatums; i++)
857  {
858  int j;
859 
860  for (j = 0; j < partnatts; j++)
861  {
862  /* For range partitions, the bounds might not be finite. */
863  if (b1->kind != NULL)
864  {
865  /* The different kinds of bound all differ from each other */
866  if (b1->kind[i][j] != b2->kind[i][j])
867  return false;
868 
869  /*
870  * Non-finite bounds are equal without further
871  * examination.
872  */
873  if (b1->kind[i][j] != PARTITION_RANGE_DATUM_VALUE)
874  continue;
875  }
876 
877  /*
878  * Compare the actual values. Note that it would be both
879  * incorrect and unsafe to invoke the comparison operator
880  * derived from the partitioning specification here. It would
881  * be incorrect because we want the relcache entry to be
882  * updated for ANY change to the partition bounds, not just
883  * those that the partitioning operator thinks are
884  * significant. It would be unsafe because we might reach
885  * this code in the context of an aborted transaction, and an
886  * arbitrary partitioning operator might not be safe in that
887  * context. datumIsEqual() should be simple enough to be
888  * safe.
889  */
890  if (!datumIsEqual(b1->datums[i][j], b2->datums[i][j],
891  parttypbyval[j], parttyplen[j]))
892  return false;
893  }
894 
895  if (b1->indexes[i] != b2->indexes[i])
896  return false;
897  }
898 
899  /* There are ndatums+1 indexes in case of range partitions */
900  if (b1->strategy == PARTITION_STRATEGY_RANGE &&
901  b1->indexes[i] != b2->indexes[i])
902  return false;
903  }
904  return true;
905 }
906 
907 /*
908  * Return a copy of given PartitionBoundInfo structure. The data types of bounds
909  * are described by given partition key specification.
910  *
911  * Note: it's important that this function and its callees not do any catalog
912  * access, nor anything else that would result in allocating memory other than
913  * the returned data structure. Since this is called in a long-lived context,
914  * that would result in unwanted memory leaks.
915  */
919 {
921  int i;
922  int ndatums;
923  int partnatts;
924  int num_indexes;
925  bool hash_part;
926  int natts;
927 
929 
930  dest->strategy = src->strategy;
931  ndatums = dest->ndatums = src->ndatums;
932  partnatts = key->partnatts;
933 
934  num_indexes = get_partition_bound_num_indexes(src);
935 
936  /* List partitioned tables have only a single partition key. */
937  Assert(key->strategy != PARTITION_STRATEGY_LIST || partnatts == 1);
938 
939  dest->datums = (Datum **) palloc(sizeof(Datum *) * ndatums);
940 
941  if (src->kind != NULL)
942  {
943  dest->kind = (PartitionRangeDatumKind **) palloc(ndatums *
944  sizeof(PartitionRangeDatumKind *));
945  for (i = 0; i < ndatums; i++)
946  {
947  dest->kind[i] = (PartitionRangeDatumKind *) palloc(partnatts *
948  sizeof(PartitionRangeDatumKind));
949 
950  memcpy(dest->kind[i], src->kind[i],
951  sizeof(PartitionRangeDatumKind) * key->partnatts);
952  }
953  }
954  else
955  dest->kind = NULL;
956 
957  /*
958  * For hash partitioning, datums array will have two elements - modulus
959  * and remainder.
960  */
961  hash_part = (key->strategy == PARTITION_STRATEGY_HASH);
962  natts = hash_part ? 2 : partnatts;
963 
964  for (i = 0; i < ndatums; i++)
965  {
966  int j;
967 
968  dest->datums[i] = (Datum *) palloc(sizeof(Datum) * natts);
969 
970  for (j = 0; j < natts; j++)
971  {
972  bool byval;
973  int typlen;
974 
975  if (hash_part)
976  {
977  typlen = sizeof(int32); /* Always int4 */
978  byval = true; /* int4 is pass-by-value */
979  }
980  else
981  {
982  byval = key->parttypbyval[j];
983  typlen = key->parttyplen[j];
984  }
985 
986  if (dest->kind == NULL ||
987  dest->kind[i][j] == PARTITION_RANGE_DATUM_VALUE)
988  dest->datums[i][j] = datumCopy(src->datums[i][j],
989  byval, typlen);
990  }
991  }
992 
993  dest->indexes = (int *) palloc(sizeof(int) * num_indexes);
994  memcpy(dest->indexes, src->indexes, sizeof(int) * num_indexes);
995 
996  dest->null_index = src->null_index;
997  dest->default_index = src->default_index;
998 
999  return dest;
1000 }
1001 
1002 /*
1003  * partition_bounds_merge
1004  * Check to see whether every partition of 'outer_rel' matches/overlaps
1005  * one partition of 'inner_rel' at most, and vice versa; and if so, build
1006  * and return the partition bounds for a join relation between the rels,
1007  * generating two lists of the matching/overlapping partitions, which are
1008  * returned to *outer_parts and *inner_parts respectively.
1009  *
1010  * The lists contain the same number of partitions, and the partitions at the
1011  * same positions in the lists indicate join pairs used for partitioned join.
1012  * If a partition on one side matches/overlaps multiple partitions on the other
1013  * side, this function returns NULL, setting *outer_parts and *inner_parts to
1014  * NIL.
1015  */
1018  FmgrInfo *partsupfunc, Oid *partcollation,
1019  RelOptInfo *outer_rel, RelOptInfo *inner_rel,
1020  JoinType jointype,
1021  List **outer_parts, List **inner_parts)
1022 {
1023  /*
1024  * Currently, this function is called only from try_partitionwise_join(),
1025  * so the join type should be INNER, LEFT, FULL, SEMI, or ANTI.
1026  */
1027  Assert(jointype == JOIN_INNER || jointype == JOIN_LEFT ||
1028  jointype == JOIN_FULL || jointype == JOIN_SEMI ||
1029  jointype == JOIN_ANTI);
1030 
1031  /* The partitioning strategies should be the same. */
1032  Assert(outer_rel->boundinfo->strategy == inner_rel->boundinfo->strategy);
1033 
1034  *outer_parts = *inner_parts = NIL;
1035  switch (outer_rel->boundinfo->strategy)
1036  {
1038 
1039  /*
1040  * For hash partitioned tables, we currently support partitioned
1041  * join only when they have exactly the same partition bounds.
1042  *
1043  * XXX: it might be possible to relax the restriction to support
1044  * cases where hash partitioned tables have missing partitions
1045  * and/or different moduli, but it's not clear if it would be
1046  * useful to support the former case since it's unusual to have
1047  * missing partitions. On the other hand, it would be useful to
1048  * support the latter case, but in that case, there is a high
1049  * probability that a partition on one side will match multiple
1050  * partitions on the other side, which is the scenario the current
1051  * implementation of partitioned join can't handle.
1052  */
1053  return NULL;
1054 
1056  return merge_list_bounds(partsupfunc,
1057  partcollation,
1058  outer_rel,
1059  inner_rel,
1060  jointype,
1061  outer_parts,
1062  inner_parts);
1063 
1065  return merge_range_bounds(partnatts,
1066  partsupfunc,
1067  partcollation,
1068  outer_rel,
1069  inner_rel,
1070  jointype,
1071  outer_parts,
1072  inner_parts);
1073 
1074  default:
1075  elog(ERROR, "unexpected partition strategy: %d",
1076  (int) outer_rel->boundinfo->strategy);
1077  return NULL; /* keep compiler quiet */
1078  }
1079 }
1080 
1081 /*
1082  * merge_list_bounds
1083  * Create the partition bounds for a join relation between list
1084  * partitioned tables, if possible
1085  *
1086  * In this function we try to find sets of matching partitions from both sides
1087  * by comparing list values stored in their partition bounds. Since the list
1088  * values appear in the ascending order, an algorithm similar to merge join is
1089  * used for that. If a partition on one side doesn't have a matching
1090  * partition on the other side, the algorithm tries to match it with the
1091  * default partition on the other side if any; if not, the algorithm tries to
1092  * match it with a dummy partition on the other side if it's on the
1093  * non-nullable side of an outer join. Also, if both sides have the default
1094  * partitions, the algorithm tries to match them with each other. We give up
1095  * if the algorithm finds a partition matching multiple partitions on the
1096  * other side, which is the scenario the current implementation of partitioned
1097  * join can't handle.
1098  */
1099 static PartitionBoundInfo
1100 merge_list_bounds(FmgrInfo *partsupfunc, Oid *partcollation,
1101  RelOptInfo *outer_rel, RelOptInfo *inner_rel,
1102  JoinType jointype,
1103  List **outer_parts, List **inner_parts)
1104 {
1105  PartitionBoundInfo merged_bounds = NULL;
1106  PartitionBoundInfo outer_bi = outer_rel->boundinfo;
1107  PartitionBoundInfo inner_bi = inner_rel->boundinfo;
1108  bool outer_has_default = partition_bound_has_default(outer_bi);
1109  bool inner_has_default = partition_bound_has_default(inner_bi);
1110  int outer_default = outer_bi->default_index;
1111  int inner_default = inner_bi->default_index;
1112  bool outer_has_null = partition_bound_accepts_nulls(outer_bi);
1113  bool inner_has_null = partition_bound_accepts_nulls(inner_bi);
1114  PartitionMap outer_map;
1115  PartitionMap inner_map;
1116  int outer_pos;
1117  int inner_pos;
1118  int next_index = 0;
1119  int null_index = -1;
1120  int default_index = -1;
1121  List *merged_datums = NIL;
1122  List *merged_indexes = NIL;
1123 
1124  Assert(*outer_parts == NIL);
1125  Assert(*inner_parts == NIL);
1126  Assert(outer_bi->strategy == inner_bi->strategy &&
1127  outer_bi->strategy == PARTITION_STRATEGY_LIST);
1128  /* List partitioning doesn't require kinds. */
1129  Assert(!outer_bi->kind && !inner_bi->kind);
1130 
1131  init_partition_map(outer_rel, &outer_map);
1132  init_partition_map(inner_rel, &inner_map);
1133 
1134  /*
1135  * If the default partitions (if any) have been proven empty, deem them
1136  * non-existent.
1137  */
1138  if (outer_has_default && is_dummy_partition(outer_rel, outer_default))
1139  outer_has_default = false;
1140  if (inner_has_default && is_dummy_partition(inner_rel, inner_default))
1141  inner_has_default = false;
1142 
1143  /*
1144  * Merge partitions from both sides. In each iteration we compare a pair
1145  * of list values, one from each side, and decide whether the
1146  * corresponding partitions match or not. If the two values match
1147  * exactly, move to the next pair of list values, otherwise move to the
1148  * next list value on the side with a smaller list value.
1149  */
1150  outer_pos = inner_pos = 0;
1151  while (outer_pos < outer_bi->ndatums || inner_pos < inner_bi->ndatums)
1152  {
1153  int outer_index = -1;
1154  int inner_index = -1;
1155  Datum *outer_datums;
1156  Datum *inner_datums;
1157  int cmpval;
1158  Datum *merged_datum = NULL;
1159  int merged_index = -1;
1160 
1161  if (outer_pos < outer_bi->ndatums)
1162  {
1163  /*
1164  * If the partition on the outer side has been proven empty,
1165  * ignore it and move to the next datum on the outer side.
1166  */
1167  outer_index = outer_bi->indexes[outer_pos];
1168  if (is_dummy_partition(outer_rel, outer_index))
1169  {
1170  outer_pos++;
1171  continue;
1172  }
1173  }
1174  if (inner_pos < inner_bi->ndatums)
1175  {
1176  /*
1177  * If the partition on the inner side has been proven empty,
1178  * ignore it and move to the next datum on the inner side.
1179  */
1180  inner_index = inner_bi->indexes[inner_pos];
1181  if (is_dummy_partition(inner_rel, inner_index))
1182  {
1183  inner_pos++;
1184  continue;
1185  }
1186  }
1187 
1188  /* Get the list values. */
1189  outer_datums = outer_pos < outer_bi->ndatums ?
1190  outer_bi->datums[outer_pos] : NULL;
1191  inner_datums = inner_pos < inner_bi->ndatums ?
1192  inner_bi->datums[inner_pos] : NULL;
1193 
1194  /*
1195  * We run this loop till both sides finish. This allows us to avoid
1196  * duplicating code to handle the remaining values on the side which
1197  * finishes later. For that we set the comparison parameter cmpval in
1198  * such a way that it appears as if the side which finishes earlier
1199  * has an extra value higher than any other value on the unfinished
1200  * side. That way we advance the values on the unfinished side till
1201  * all of its values are exhausted.
1202  */
1203  if (outer_pos >= outer_bi->ndatums)
1204  cmpval = 1;
1205  else if (inner_pos >= inner_bi->ndatums)
1206  cmpval = -1;
1207  else
1208  {
1209  Assert(outer_datums != NULL && inner_datums != NULL);
1210  cmpval = DatumGetInt32(FunctionCall2Coll(&partsupfunc[0],
1211  partcollation[0],
1212  outer_datums[0],
1213  inner_datums[0]));
1214  }
1215 
1216  if (cmpval == 0)
1217  {
1218  /* Two list values match exactly. */
1219  Assert(outer_pos < outer_bi->ndatums);
1220  Assert(inner_pos < inner_bi->ndatums);
1221  Assert(outer_index >= 0);
1222  Assert(inner_index >= 0);
1223 
1224  /*
1225  * Try merging both partitions. If successful, add the list value
1226  * and index of the merged partition below.
1227  */
1228  merged_index = merge_matching_partitions(&outer_map, &inner_map,
1229  outer_index, inner_index,
1230  &next_index);
1231  if (merged_index == -1)
1232  goto cleanup;
1233 
1234  merged_datum = outer_datums;
1235 
1236  /* Move to the next pair of list values. */
1237  outer_pos++;
1238  inner_pos++;
1239  }
1240  else if (cmpval < 0)
1241  {
1242  /* A list value missing from the inner side. */
1243  Assert(outer_pos < outer_bi->ndatums);
1244 
1245  /*
1246  * If the inner side has the default partition, or this is an
1247  * outer join, try to assign a merged partition to the outer
1248  * partition (see process_outer_partition()). Otherwise, the
1249  * outer partition will not contribute to the result.
1250  */
1251  if (inner_has_default || IS_OUTER_JOIN(jointype))
1252  {
1253  /* Get the outer partition. */
1254  outer_index = outer_bi->indexes[outer_pos];
1255  Assert(outer_index >= 0);
1256  merged_index = process_outer_partition(&outer_map,
1257  &inner_map,
1258  outer_has_default,
1259  inner_has_default,
1260  outer_index,
1261  inner_default,
1262  jointype,
1263  &next_index,
1264  &default_index);
1265  if (merged_index == -1)
1266  goto cleanup;
1267  merged_datum = outer_datums;
1268  }
1269 
1270  /* Move to the next list value on the outer side. */
1271  outer_pos++;
1272  }
1273  else
1274  {
1275  /* A list value missing from the outer side. */
1276  Assert(cmpval > 0);
1277  Assert(inner_pos < inner_bi->ndatums);
1278 
1279  /*
1280  * If the outer side has the default partition, or this is a FULL
1281  * join, try to assign a merged partition to the inner partition
1282  * (see process_inner_partition()). Otherwise, the inner
1283  * partition will not contribute to the result.
1284  */
1285  if (outer_has_default || jointype == JOIN_FULL)
1286  {
1287  /* Get the inner partition. */
1288  inner_index = inner_bi->indexes[inner_pos];
1289  Assert(inner_index >= 0);
1290  merged_index = process_inner_partition(&outer_map,
1291  &inner_map,
1292  outer_has_default,
1293  inner_has_default,
1294  inner_index,
1295  outer_default,
1296  jointype,
1297  &next_index,
1298  &default_index);
1299  if (merged_index == -1)
1300  goto cleanup;
1301  merged_datum = inner_datums;
1302  }
1303 
1304  /* Move to the next list value on the inner side. */
1305  inner_pos++;
1306  }
1307 
1308  /*
1309  * If we assigned a merged partition, add the list value and index of
1310  * the merged partition if appropriate.
1311  */
1312  if (merged_index >= 0 && merged_index != default_index)
1313  {
1314  merged_datums = lappend(merged_datums, merged_datum);
1315  merged_indexes = lappend_int(merged_indexes, merged_index);
1316  }
1317  }
1318 
1319  /*
1320  * If the NULL partitions (if any) have been proven empty, deem them
1321  * non-existent.
1322  */
1323  if (outer_has_null &&
1324  is_dummy_partition(outer_rel, outer_bi->null_index))
1325  outer_has_null = false;
1326  if (inner_has_null &&
1327  is_dummy_partition(inner_rel, inner_bi->null_index))
1328  inner_has_null = false;
1329 
1330  /* Merge the NULL partitions if any. */
1331  if (outer_has_null || inner_has_null)
1332  merge_null_partitions(&outer_map, &inner_map,
1333  outer_has_null, inner_has_null,
1334  outer_bi->null_index, inner_bi->null_index,
1335  jointype, &next_index, &null_index);
1336  else
1337  Assert(null_index == -1);
1338 
1339  /* Merge the default partitions if any. */
1340  if (outer_has_default || inner_has_default)
1341  merge_default_partitions(&outer_map, &inner_map,
1342  outer_has_default, inner_has_default,
1343  outer_default, inner_default,
1344  jointype, &next_index, &default_index);
1345  else
1346  Assert(default_index == -1);
1347 
1348  /* If we have merged partitions, create the partition bounds. */
1349  if (next_index > 0)
1350  {
1351  /* Fix the merged_indexes list if necessary. */
1352  if (outer_map.did_remapping || inner_map.did_remapping)
1353  {
1354  Assert(jointype == JOIN_FULL);
1355  fix_merged_indexes(&outer_map, &inner_map,
1356  next_index, merged_indexes);
1357  }
1358 
1359  /* Use maps to match partitions from inputs. */
1360  generate_matching_part_pairs(outer_rel, inner_rel,
1361  &outer_map, &inner_map,
1362  next_index,
1363  outer_parts, inner_parts);
1364  Assert(*outer_parts != NIL);
1365  Assert(*inner_parts != NIL);
1366  Assert(list_length(*outer_parts) == list_length(*inner_parts));
1367  Assert(list_length(*outer_parts) <= next_index);
1368 
1369  /* Make a PartitionBoundInfo struct to return. */
1370  merged_bounds = build_merged_partition_bounds(outer_bi->strategy,
1371  merged_datums,
1372  NIL,
1373  merged_indexes,
1374  null_index,
1375  default_index);
1376  Assert(merged_bounds);
1377  }
1378 
1379 cleanup:
1380  /* Free local memory before returning. */
1381  list_free(merged_datums);
1382  list_free(merged_indexes);
1383  free_partition_map(&outer_map);
1384  free_partition_map(&inner_map);
1385 
1386  return merged_bounds;
1387 }
1388 
1389 /*
1390  * merge_range_bounds
1391  * Create the partition bounds for a join relation between range
1392  * partitioned tables, if possible
1393  *
1394  * In this function we try to find sets of overlapping partitions from both
1395  * sides by comparing ranges stored in their partition bounds. Since the
1396  * ranges appear in the ascending order, an algorithm similar to merge join is
1397  * used for that. If a partition on one side doesn't have an overlapping
1398  * partition on the other side, the algorithm tries to match it with the
1399  * default partition on the other side if any; if not, the algorithm tries to
1400  * match it with a dummy partition on the other side if it's on the
1401  * non-nullable side of an outer join. Also, if both sides have the default
1402  * partitions, the algorithm tries to match them with each other. We give up
1403  * if the algorithm finds a partition overlapping multiple partitions on the
1404  * other side, which is the scenario the current implementation of partitioned
1405  * join can't handle.
1406  */
1407 static PartitionBoundInfo
1408 merge_range_bounds(int partnatts, FmgrInfo *partsupfuncs,
1409  Oid *partcollations,
1410  RelOptInfo *outer_rel, RelOptInfo *inner_rel,
1411  JoinType jointype,
1412  List **outer_parts, List **inner_parts)
1413 {
1414  PartitionBoundInfo merged_bounds = NULL;
1415  PartitionBoundInfo outer_bi = outer_rel->boundinfo;
1416  PartitionBoundInfo inner_bi = inner_rel->boundinfo;
1417  bool outer_has_default = partition_bound_has_default(outer_bi);
1418  bool inner_has_default = partition_bound_has_default(inner_bi);
1419  int outer_default = outer_bi->default_index;
1420  int inner_default = inner_bi->default_index;
1421  PartitionMap outer_map;
1422  PartitionMap inner_map;
1423  int outer_index;
1424  int inner_index;
1425  int outer_lb_pos;
1426  int inner_lb_pos;
1427  PartitionRangeBound outer_lb;
1428  PartitionRangeBound outer_ub;
1429  PartitionRangeBound inner_lb;
1430  PartitionRangeBound inner_ub;
1431  int next_index = 0;
1432  int default_index = -1;
1433  List *merged_datums = NIL;
1434  List *merged_kinds = NIL;
1435  List *merged_indexes = NIL;
1436 
1437  Assert(*outer_parts == NIL);
1438  Assert(*inner_parts == NIL);
1439  Assert(outer_bi->strategy == inner_bi->strategy &&
1440  outer_bi->strategy == PARTITION_STRATEGY_RANGE);
1441 
1442  init_partition_map(outer_rel, &outer_map);
1443  init_partition_map(inner_rel, &inner_map);
1444 
1445  /*
1446  * If the default partitions (if any) have been proven empty, deem them
1447  * non-existent.
1448  */
1449  if (outer_has_default && is_dummy_partition(outer_rel, outer_default))
1450  outer_has_default = false;
1451  if (inner_has_default && is_dummy_partition(inner_rel, inner_default))
1452  inner_has_default = false;
1453 
1454  /*
1455  * Merge partitions from both sides. In each iteration we compare a pair
1456  * of ranges, one from each side, and decide whether the corresponding
1457  * partitions match or not. If the two ranges overlap, move to the next
1458  * pair of ranges, otherwise move to the next range on the side with a
1459  * lower range. outer_lb_pos/inner_lb_pos keep track of the positions of
1460  * lower bounds in the datums arrays in the outer/inner
1461  * PartitionBoundInfos respectively.
1462  */
1463  outer_lb_pos = inner_lb_pos = 0;
1464  outer_index = get_range_partition(outer_rel, outer_bi, &outer_lb_pos,
1465  &outer_lb, &outer_ub);
1466  inner_index = get_range_partition(inner_rel, inner_bi, &inner_lb_pos,
1467  &inner_lb, &inner_ub);
1468  while (outer_index >= 0 || inner_index >= 0)
1469  {
1470  bool overlap;
1471  int ub_cmpval;
1472  int lb_cmpval;
1473  PartitionRangeBound merged_lb = {-1, NULL, NULL, true};
1474  PartitionRangeBound merged_ub = {-1, NULL, NULL, false};
1475  int merged_index = -1;
1476 
1477  /*
1478  * We run this loop till both sides finish. This allows us to avoid
1479  * duplicating code to handle the remaining ranges on the side which
1480  * finishes later. For that we set the comparison parameter cmpval in
1481  * such a way that it appears as if the side which finishes earlier
1482  * has an extra range higher than any other range on the unfinished
1483  * side. That way we advance the ranges on the unfinished side till
1484  * all of its ranges are exhausted.
1485  */
1486  if (outer_index == -1)
1487  {
1488  overlap = false;
1489  lb_cmpval = 1;
1490  ub_cmpval = 1;
1491  }
1492  else if (inner_index == -1)
1493  {
1494  overlap = false;
1495  lb_cmpval = -1;
1496  ub_cmpval = -1;
1497  }
1498  else
1499  overlap = compare_range_partitions(partnatts, partsupfuncs,
1500  partcollations,
1501  &outer_lb, &outer_ub,
1502  &inner_lb, &inner_ub,
1503  &lb_cmpval, &ub_cmpval);
1504 
1505  if (overlap)
1506  {
1507  /* Two ranges overlap; form a join pair. */
1508 
1509  PartitionRangeBound save_outer_ub;
1510  PartitionRangeBound save_inner_ub;
1511 
1512  /* Both partitions should not have been merged yet. */
1513  Assert(outer_index >= 0);
1514  Assert(outer_map.merged_indexes[outer_index] == -1 &&
1515  outer_map.merged[outer_index] == false);
1516  Assert(inner_index >= 0);
1517  Assert(inner_map.merged_indexes[inner_index] == -1 &&
1518  inner_map.merged[inner_index] == false);
1519 
1520  /*
1521  * Get the index of the merged partition. Both partitions aren't
1522  * merged yet, so the partitions should be merged successfully.
1523  */
1524  merged_index = merge_matching_partitions(&outer_map, &inner_map,
1525  outer_index, inner_index,
1526  &next_index);
1527  Assert(merged_index >= 0);
1528 
1529  /* Get the range bounds of the merged partition. */
1530  get_merged_range_bounds(partnatts, partsupfuncs,
1531  partcollations, jointype,
1532  &outer_lb, &outer_ub,
1533  &inner_lb, &inner_ub,
1534  lb_cmpval, ub_cmpval,
1535  &merged_lb, &merged_ub);
1536 
1537  /* Save the upper bounds of both partitions for use below. */
1538  save_outer_ub = outer_ub;
1539  save_inner_ub = inner_ub;
1540 
1541  /* Move to the next pair of ranges. */
1542  outer_index = get_range_partition(outer_rel, outer_bi, &outer_lb_pos,
1543  &outer_lb, &outer_ub);
1544  inner_index = get_range_partition(inner_rel, inner_bi, &inner_lb_pos,
1545  &inner_lb, &inner_ub);
1546 
1547  /*
1548  * If the range of a partition on one side overlaps the range of
1549  * the next partition on the other side, that will cause the
1550  * partition on one side to match at least two partitions on the
1551  * other side, which is the case that we currently don't support
1552  * partitioned join for; give up.
1553  */
1554  if (ub_cmpval > 0 && inner_index >= 0 &&
1555  compare_range_bounds(partnatts, partsupfuncs, partcollations,
1556  &save_outer_ub, &inner_lb) > 0)
1557  goto cleanup;
1558  if (ub_cmpval < 0 && outer_index >= 0 &&
1559  compare_range_bounds(partnatts, partsupfuncs, partcollations,
1560  &outer_lb, &save_inner_ub) < 0)
1561  goto cleanup;
1562 
1563  /*
1564  * A row from a non-overlapping portion (if any) of a partition on
1565  * one side might find its join partner in the default partition
1566  * (if any) on the other side, causing the same situation as
1567  * above; give up in that case.
1568  */
1569  if ((outer_has_default && (lb_cmpval > 0 || ub_cmpval < 0)) ||
1570  (inner_has_default && (lb_cmpval < 0 || ub_cmpval > 0)))
1571  goto cleanup;
1572  }
1573  else if (ub_cmpval < 0)
1574  {
1575  /* A non-overlapping outer range. */
1576 
1577  /* The outer partition should not have been merged yet. */
1578  Assert(outer_index >= 0);
1579  Assert(outer_map.merged_indexes[outer_index] == -1 &&
1580  outer_map.merged[outer_index] == false);
1581 
1582  /*
1583  * If the inner side has the default partition, or this is an
1584  * outer join, try to assign a merged partition to the outer
1585  * partition (see process_outer_partition()). Otherwise, the
1586  * outer partition will not contribute to the result.
1587  */
1588  if (inner_has_default || IS_OUTER_JOIN(jointype))
1589  {
1590  merged_index = process_outer_partition(&outer_map,
1591  &inner_map,
1592  outer_has_default,
1593  inner_has_default,
1594  outer_index,
1595  inner_default,
1596  jointype,
1597  &next_index,
1598  &default_index);
1599  if (merged_index == -1)
1600  goto cleanup;
1601  merged_lb = outer_lb;
1602  merged_ub = outer_ub;
1603  }
1604 
1605  /* Move to the next range on the outer side. */
1606  outer_index = get_range_partition(outer_rel, outer_bi, &outer_lb_pos,
1607  &outer_lb, &outer_ub);
1608  }
1609  else
1610  {
1611  /* A non-overlapping inner range. */
1612  Assert(ub_cmpval > 0);
1613 
1614  /* The inner partition should not have been merged yet. */
1615  Assert(inner_index >= 0);
1616  Assert(inner_map.merged_indexes[inner_index] == -1 &&
1617  inner_map.merged[inner_index] == false);
1618 
1619  /*
1620  * If the outer side has the default partition, or this is a FULL
1621  * join, try to assign a merged partition to the inner partition
1622  * (see process_inner_partition()). Otherwise, the inner
1623  * partition will not contribute to the result.
1624  */
1625  if (outer_has_default || jointype == JOIN_FULL)
1626  {
1627  merged_index = process_inner_partition(&outer_map,
1628  &inner_map,
1629  outer_has_default,
1630  inner_has_default,
1631  inner_index,
1632  outer_default,
1633  jointype,
1634  &next_index,
1635  &default_index);
1636  if (merged_index == -1)
1637  goto cleanup;
1638  merged_lb = inner_lb;
1639  merged_ub = inner_ub;
1640  }
1641 
1642  /* Move to the next range on the inner side. */
1643  inner_index = get_range_partition(inner_rel, inner_bi, &inner_lb_pos,
1644  &inner_lb, &inner_ub);
1645  }
1646 
1647  /*
1648  * If we assigned a merged partition, add the range bounds and index
1649  * of the merged partition if appropriate.
1650  */
1651  if (merged_index >= 0 && merged_index != default_index)
1652  add_merged_range_bounds(partnatts, partsupfuncs, partcollations,
1653  &merged_lb, &merged_ub, merged_index,
1654  &merged_datums, &merged_kinds,
1655  &merged_indexes);
1656  }
1657 
1658  /* Merge the default partitions if any. */
1659  if (outer_has_default || inner_has_default)
1660  merge_default_partitions(&outer_map, &inner_map,
1661  outer_has_default, inner_has_default,
1662  outer_default, inner_default,
1663  jointype, &next_index, &default_index);
1664  else
1665  Assert(default_index == -1);
1666 
1667  /* If we have merged partitions, create the partition bounds. */
1668  if (next_index > 0)
1669  {
1670  /*
1671  * Unlike the case of list partitioning, we wouldn't have re-merged
1672  * partitions, so did_remapping should be left alone.
1673  */
1674  Assert(!outer_map.did_remapping);
1675  Assert(!inner_map.did_remapping);
1676 
1677  /* Use maps to match partitions from inputs. */
1678  generate_matching_part_pairs(outer_rel, inner_rel,
1679  &outer_map, &inner_map,
1680  next_index,
1681  outer_parts, inner_parts);
1682  Assert(*outer_parts != NIL);
1683  Assert(*inner_parts != NIL);
1684  Assert(list_length(*outer_parts) == list_length(*inner_parts));
1685  Assert(list_length(*outer_parts) == next_index);
1686 
1687  /* Make a PartitionBoundInfo struct to return. */
1688  merged_bounds = build_merged_partition_bounds(outer_bi->strategy,
1689  merged_datums,
1690  merged_kinds,
1691  merged_indexes,
1692  -1,
1693  default_index);
1694  Assert(merged_bounds);
1695  }
1696 
1697 cleanup:
1698  /* Free local memory before returning. */
1699  list_free(merged_datums);
1700  list_free(merged_kinds);
1701  list_free(merged_indexes);
1702  free_partition_map(&outer_map);
1703  free_partition_map(&inner_map);
1704 
1705  return merged_bounds;
1706 }
1707 
1708 /*
1709  * init_partition_map
1710  * Initialize a PartitionMap struct for given relation
1711  */
1712 static void
1714 {
1715  int nparts = rel->nparts;
1716  int i;
1717 
1718  map->nparts = nparts;
1719  map->merged_indexes = (int *) palloc(sizeof(int) * nparts);
1720  map->merged = (bool *) palloc(sizeof(bool) * nparts);
1721  map->did_remapping = false;
1722  map->old_indexes = (int *) palloc(sizeof(int) * nparts);
1723  for (i = 0; i < nparts; i++)
1724  {
1725  map->merged_indexes[i] = map->old_indexes[i] = -1;
1726  map->merged[i] = false;
1727  }
1728 }
1729 
1730 /*
1731  * free_partition_map
1732  */
1733 static void
1735 {
1736  pfree(map->merged_indexes);
1737  pfree(map->merged);
1738  pfree(map->old_indexes);
1739 }
1740 
1741 /*
1742  * is_dummy_partition --- has partition been proven empty?
1743  */
1744 static bool
1745 is_dummy_partition(RelOptInfo *rel, int part_index)
1746 {
1747  RelOptInfo *part_rel;
1748 
1749  Assert(part_index >= 0);
1750  part_rel = rel->part_rels[part_index];
1751  if (part_rel == NULL || IS_DUMMY_REL(part_rel))
1752  return true;
1753  return false;
1754 }
1755 
1756 /*
1757  * merge_matching_partitions
1758  * Try to merge given outer/inner partitions, and return the index of a
1759  * merged partition produced from them if successful, -1 otherwise
1760  *
1761  * If the merged partition is newly created, *next_index is incremented.
1762  */
1763 static int
1765  int outer_index, int inner_index, int *next_index)
1766 {
1767  int outer_merged_index;
1768  int inner_merged_index;
1769  bool outer_merged;
1770  bool inner_merged;
1771 
1772  Assert(outer_index >= 0 && outer_index < outer_map->nparts);
1773  outer_merged_index = outer_map->merged_indexes[outer_index];
1774  outer_merged = outer_map->merged[outer_index];
1775  Assert(inner_index >= 0 && inner_index < inner_map->nparts);
1776  inner_merged_index = inner_map->merged_indexes[inner_index];
1777  inner_merged = inner_map->merged[inner_index];
1778 
1779  /*
1780  * Handle cases where we have already assigned a merged partition to each
1781  * of the given partitions.
1782  */
1783  if (outer_merged_index >= 0 && inner_merged_index >= 0)
1784  {
1785  /*
1786  * If the merged partitions are the same, no need to do anything;
1787  * return the index of the merged partitions. Otherwise, if each of
1788  * the given partitions has been merged with a dummy partition on the
1789  * other side, re-map them to either of the two merged partitions.
1790  * Otherwise, they can't be merged, so return -1.
1791  */
1792  if (outer_merged_index == inner_merged_index)
1793  {
1794  Assert(outer_merged);
1795  Assert(inner_merged);
1796  return outer_merged_index;
1797  }
1798  if (!outer_merged && !inner_merged)
1799  {
1800  /*
1801  * This can only happen for a list-partitioning case. We re-map
1802  * them to the merged partition with the smaller of the two merged
1803  * indexes to preserve the property that the canonical order of
1804  * list partitions is determined by the indexes assigned to the
1805  * smallest list value of each partition.
1806  */
1807  if (outer_merged_index < inner_merged_index)
1808  {
1809  outer_map->merged[outer_index] = true;
1810  inner_map->merged_indexes[inner_index] = outer_merged_index;
1811  inner_map->merged[inner_index] = true;
1812  inner_map->did_remapping = true;
1813  inner_map->old_indexes[inner_index] = inner_merged_index;
1814  return outer_merged_index;
1815  }
1816  else
1817  {
1818  inner_map->merged[inner_index] = true;
1819  outer_map->merged_indexes[outer_index] = inner_merged_index;
1820  outer_map->merged[outer_index] = true;
1821  outer_map->did_remapping = true;
1822  outer_map->old_indexes[outer_index] = outer_merged_index;
1823  return inner_merged_index;
1824  }
1825  }
1826  return -1;
1827  }
1828 
1829  /* At least one of the given partitions should not have yet been merged. */
1830  Assert(outer_merged_index == -1 || inner_merged_index == -1);
1831 
1832  /*
1833  * If neither of them has been merged, merge them. Otherwise, if one has
1834  * been merged with a dummy partition on the other side (and the other
1835  * hasn't yet been merged with anything), re-merge them. Otherwise, they
1836  * can't be merged, so return -1.
1837  */
1838  if (outer_merged_index == -1 && inner_merged_index == -1)
1839  {
1840  int merged_index = *next_index;
1841 
1842  Assert(!outer_merged);
1843  Assert(!inner_merged);
1844  outer_map->merged_indexes[outer_index] = merged_index;
1845  outer_map->merged[outer_index] = true;
1846  inner_map->merged_indexes[inner_index] = merged_index;
1847  inner_map->merged[inner_index] = true;
1848  *next_index = *next_index + 1;
1849  return merged_index;
1850  }
1851  if (outer_merged_index >= 0 && !outer_map->merged[outer_index])
1852  {
1853  Assert(inner_merged_index == -1);
1854  Assert(!inner_merged);
1855  inner_map->merged_indexes[inner_index] = outer_merged_index;
1856  inner_map->merged[inner_index] = true;
1857  outer_map->merged[outer_index] = true;
1858  return outer_merged_index;
1859  }
1860  if (inner_merged_index >= 0 && !inner_map->merged[inner_index])
1861  {
1862  Assert(outer_merged_index == -1);
1863  Assert(!outer_merged);
1864  outer_map->merged_indexes[outer_index] = inner_merged_index;
1865  outer_map->merged[outer_index] = true;
1866  inner_map->merged[inner_index] = true;
1867  return inner_merged_index;
1868  }
1869  return -1;
1870 }
1871 
1872 /*
1873  * process_outer_partition
1874  * Try to assign given outer partition a merged partition, and return the
1875  * index of the merged partition if successful, -1 otherwise
1876  *
1877  * If the partition is newly created, *next_index is incremented. Also, if it
1878  * is the default partition of the join relation, *default_index is set to the
1879  * index if not already done.
1880  */
1881 static int
1883  PartitionMap *inner_map,
1884  bool outer_has_default,
1885  bool inner_has_default,
1886  int outer_index,
1887  int inner_default,
1888  JoinType jointype,
1889  int *next_index,
1890  int *default_index)
1891 {
1892  int merged_index = -1;
1893 
1894  Assert(outer_index >= 0);
1895 
1896  /*
1897  * If the inner side has the default partition, a row from the outer
1898  * partition might find its join partner in the default partition; try
1899  * merging the outer partition with the default partition. Otherwise,
1900  * this should be an outer join, in which case the outer partition has to
1901  * be scanned all the way anyway; merge the outer partition with a dummy
1902  * partition on the other side.
1903  */
1904  if (inner_has_default)
1905  {
1906  Assert(inner_default >= 0);
1907 
1908  /*
1909  * If the outer side has the default partition as well, the default
1910  * partition on the inner side will have two matching partitions on
1911  * the other side: the outer partition and the default partition on
1912  * the outer side. Partitionwise join doesn't handle this scenario
1913  * yet.
1914  */
1915  if (outer_has_default)
1916  return -1;
1917 
1918  merged_index = merge_matching_partitions(outer_map, inner_map,
1919  outer_index, inner_default,
1920  next_index);
1921  if (merged_index == -1)
1922  return -1;
1923 
1924  /*
1925  * If this is a FULL join, the default partition on the inner side has
1926  * to be scanned all the way anyway, so the resulting partition will
1927  * contain all key values from the default partition, which any other
1928  * partition of the join relation will not contain. Thus the
1929  * resulting partition will act as the default partition of the join
1930  * relation; record the index in *default_index if not already done.
1931  */
1932  if (jointype == JOIN_FULL)
1933  {
1934  if (*default_index == -1)
1935  *default_index = merged_index;
1936  else
1937  Assert(*default_index == merged_index);
1938  }
1939  }
1940  else
1941  {
1942  Assert(IS_OUTER_JOIN(jointype));
1943  Assert(jointype != JOIN_RIGHT);
1944 
1945  /* If we have already assigned a partition, no need to do anything. */
1946  merged_index = outer_map->merged_indexes[outer_index];
1947  if (merged_index == -1)
1948  merged_index = merge_partition_with_dummy(outer_map, outer_index,
1949  next_index);
1950  }
1951  return merged_index;
1952 }
1953 
1954 /*
1955  * process_inner_partition
1956  * Try to assign given inner partition a merged partition, and return the
1957  * index of the merged partition if successful, -1 otherwise
1958  *
1959  * If the partition is newly created, *next_index is incremented. Also, if it
1960  * is the default partition of the join relation, *default_index is set to the
1961  * index if not already done.
1962  */
1963 static int
1965  PartitionMap *inner_map,
1966  bool outer_has_default,
1967  bool inner_has_default,
1968  int inner_index,
1969  int outer_default,
1970  JoinType jointype,
1971  int *next_index,
1972  int *default_index)
1973 {
1974  int merged_index = -1;
1975 
1976  Assert(inner_index >= 0);
1977 
1978  /*
1979  * If the outer side has the default partition, a row from the inner
1980  * partition might find its join partner in the default partition; try
1981  * merging the inner partition with the default partition. Otherwise,
1982  * this should be a FULL join, in which case the inner partition has to be
1983  * scanned all the way anyway; merge the inner partition with a dummy
1984  * partition on the other side.
1985  */
1986  if (outer_has_default)
1987  {
1988  Assert(outer_default >= 0);
1989 
1990  /*
1991  * If the inner side has the default partition as well, the default
1992  * partition on the outer side will have two matching partitions on
1993  * the other side: the inner partition and the default partition on
1994  * the inner side. Partitionwise join doesn't handle this scenario
1995  * yet.
1996  */
1997  if (inner_has_default)
1998  return -1;
1999 
2000  merged_index = merge_matching_partitions(outer_map, inner_map,
2001  outer_default, inner_index,
2002  next_index);
2003  if (merged_index == -1)
2004  return -1;
2005 
2006  /*
2007  * If this is an outer join, the default partition on the outer side
2008  * has to be scanned all the way anyway, so the resulting partition
2009  * will contain all key values from the default partition, which any
2010  * other partition of the join relation will not contain. Thus the
2011  * resulting partition will act as the default partition of the join
2012  * relation; record the index in *default_index if not already done.
2013  */
2014  if (IS_OUTER_JOIN(jointype))
2015  {
2016  Assert(jointype != JOIN_RIGHT);
2017  if (*default_index == -1)
2018  *default_index = merged_index;
2019  else
2020  Assert(*default_index == merged_index);
2021  }
2022  }
2023  else
2024  {
2025  Assert(jointype == JOIN_FULL);
2026 
2027  /* If we have already assigned a partition, no need to do anything. */
2028  merged_index = inner_map->merged_indexes[inner_index];
2029  if (merged_index == -1)
2030  merged_index = merge_partition_with_dummy(inner_map, inner_index,
2031  next_index);
2032  }
2033  return merged_index;
2034 }
2035 
2036 /*
2037  * merge_null_partitions
2038  * Merge the NULL partitions from a join's outer and inner sides.
2039  *
2040  * If the merged partition produced from them is the NULL partition of the join
2041  * relation, *null_index is set to the index of the merged partition.
2042  *
2043  * Note: We assume here that the join clause for a partitioned join is strict
2044  * because have_partkey_equi_join() requires that the corresponding operator
2045  * be mergejoinable, and we currently assume that mergejoinable operators are
2046  * strict (see MJEvalOuterValues()/MJEvalInnerValues()).
2047  */
2048 static void
2050  PartitionMap *inner_map,
2051  bool outer_has_null,
2052  bool inner_has_null,
2053  int outer_null,
2054  int inner_null,
2055  JoinType jointype,
2056  int *next_index,
2057  int *null_index)
2058 {
2059  bool consider_outer_null = false;
2060  bool consider_inner_null = false;
2061 
2062  Assert(outer_has_null || inner_has_null);
2063  Assert(*null_index == -1);
2064 
2065  /*
2066  * Check whether the NULL partitions have already been merged and if so,
2067  * set the consider_outer_null/consider_inner_null flags.
2068  */
2069  if (outer_has_null)
2070  {
2071  Assert(outer_null >= 0 && outer_null < outer_map->nparts);
2072  if (outer_map->merged_indexes[outer_null] == -1)
2073  consider_outer_null = true;
2074  }
2075  if (inner_has_null)
2076  {
2077  Assert(inner_null >= 0 && inner_null < inner_map->nparts);
2078  if (inner_map->merged_indexes[inner_null] == -1)
2079  consider_inner_null = true;
2080  }
2081 
2082  /* If both flags are set false, we don't need to do anything. */
2083  if (!consider_outer_null && !consider_inner_null)
2084  return;
2085 
2086  if (consider_outer_null && !consider_inner_null)
2087  {
2088  Assert(outer_has_null);
2089 
2090  /*
2091  * If this is an outer join, the NULL partition on the outer side has
2092  * to be scanned all the way anyway; merge the NULL partition with a
2093  * dummy partition on the other side. In that case
2094  * consider_outer_null means that the NULL partition only contains
2095  * NULL values as the key values, so the merged partition will do so;
2096  * treat it as the NULL partition of the join relation.
2097  */
2098  if (IS_OUTER_JOIN(jointype))
2099  {
2100  Assert(jointype != JOIN_RIGHT);
2101  *null_index = merge_partition_with_dummy(outer_map, outer_null,
2102  next_index);
2103  }
2104  }
2105  else if (!consider_outer_null && consider_inner_null)
2106  {
2107  Assert(inner_has_null);
2108 
2109  /*
2110  * If this is a FULL join, the NULL partition on the inner side has to
2111  * be scanned all the way anyway; merge the NULL partition with a
2112  * dummy partition on the other side. In that case
2113  * consider_inner_null means that the NULL partition only contains
2114  * NULL values as the key values, so the merged partition will do so;
2115  * treat it as the NULL partition of the join relation.
2116  */
2117  if (jointype == JOIN_FULL)
2118  *null_index = merge_partition_with_dummy(inner_map, inner_null,
2119  next_index);
2120  }
2121  else
2122  {
2123  Assert(consider_outer_null && consider_inner_null);
2124  Assert(outer_has_null);
2125  Assert(inner_has_null);
2126 
2127  /*
2128  * If this is an outer join, the NULL partition on the outer side (and
2129  * that on the inner side if this is a FULL join) have to be scanned
2130  * all the way anyway, so merge them. Note that each of the NULL
2131  * partitions isn't merged yet, so they should be merged successfully.
2132  * Like the above, each of the NULL partitions only contains NULL
2133  * values as the key values, so the merged partition will do so; treat
2134  * it as the NULL partition of the join relation.
2135  *
2136  * Note: if this an INNER/SEMI join, the join clause will never be
2137  * satisfied by two NULL values (see comments above), so both the NULL
2138  * partitions can be eliminated.
2139  */
2140  if (IS_OUTER_JOIN(jointype))
2141  {
2142  Assert(jointype != JOIN_RIGHT);
2143  *null_index = merge_matching_partitions(outer_map, inner_map,
2144  outer_null, inner_null,
2145  next_index);
2146  Assert(*null_index >= 0);
2147  }
2148  }
2149 }
2150 
2151 /*
2152  * merge_default_partitions
2153  * Merge the default partitions from a join's outer and inner sides.
2154  *
2155  * If the merged partition produced from them is the default partition of the
2156  * join relation, *default_index is set to the index of the merged partition.
2157  */
2158 static void
2160  PartitionMap *inner_map,
2161  bool outer_has_default,
2162  bool inner_has_default,
2163  int outer_default,
2164  int inner_default,
2165  JoinType jointype,
2166  int *next_index,
2167  int *default_index)
2168 {
2169  int outer_merged_index = -1;
2170  int inner_merged_index = -1;
2171 
2172  Assert(outer_has_default || inner_has_default);
2173 
2174  /* Get the merged partition indexes for the default partitions. */
2175  if (outer_has_default)
2176  {
2177  Assert(outer_default >= 0 && outer_default < outer_map->nparts);
2178  outer_merged_index = outer_map->merged_indexes[outer_default];
2179  }
2180  if (inner_has_default)
2181  {
2182  Assert(inner_default >= 0 && inner_default < inner_map->nparts);
2183  inner_merged_index = inner_map->merged_indexes[inner_default];
2184  }
2185 
2186  if (outer_has_default && !inner_has_default)
2187  {
2188  /*
2189  * If this is an outer join, the default partition on the outer side
2190  * has to be scanned all the way anyway; if we have not yet assigned a
2191  * partition, merge the default partition with a dummy partition on
2192  * the other side. The merged partition will act as the default
2193  * partition of the join relation (see comments in
2194  * process_inner_partition()).
2195  */
2196  if (IS_OUTER_JOIN(jointype))
2197  {
2198  Assert(jointype != JOIN_RIGHT);
2199  if (outer_merged_index == -1)
2200  {
2201  Assert(*default_index == -1);
2202  *default_index = merge_partition_with_dummy(outer_map,
2203  outer_default,
2204  next_index);
2205  }
2206  else
2207  Assert(*default_index == outer_merged_index);
2208  }
2209  else
2210  Assert(*default_index == -1);
2211  }
2212  else if (!outer_has_default && inner_has_default)
2213  {
2214  /*
2215  * If this is a FULL join, the default partition on the inner side has
2216  * to be scanned all the way anyway; if we have not yet assigned a
2217  * partition, merge the default partition with a dummy partition on
2218  * the other side. The merged partition will act as the default
2219  * partition of the join relation (see comments in
2220  * process_outer_partition()).
2221  */
2222  if (jointype == JOIN_FULL)
2223  {
2224  if (inner_merged_index == -1)
2225  {
2226  Assert(*default_index == -1);
2227  *default_index = merge_partition_with_dummy(inner_map,
2228  inner_default,
2229  next_index);
2230  }
2231  else
2232  Assert(*default_index == inner_merged_index);
2233  }
2234  else
2235  Assert(*default_index == -1);
2236  }
2237  else
2238  {
2239  Assert(outer_has_default && inner_has_default);
2240 
2241  /*
2242  * The default partitions have to be joined with each other, so merge
2243  * them. Note that each of the default partitions isn't merged yet
2244  * (see, process_outer_partition()/process_innerer_partition()), so
2245  * they should be merged successfully. The merged partition will act
2246  * as the default partition of the join relation.
2247  */
2248  Assert(outer_merged_index == -1);
2249  Assert(inner_merged_index == -1);
2250  Assert(*default_index == -1);
2251  *default_index = merge_matching_partitions(outer_map,
2252  inner_map,
2253  outer_default,
2254  inner_default,
2255  next_index);
2256  Assert(*default_index >= 0);
2257  }
2258 }
2259 
2260 /*
2261  * merge_partition_with_dummy
2262  * Assign given partition a new partition of a join relation
2263  *
2264  * Note: The caller assumes that the given partition doesn't have a non-dummy
2265  * matching partition on the other side, but if the given partition finds the
2266  * matching partition later, we will adjust the assignment.
2267  */
2268 static int
2269 merge_partition_with_dummy(PartitionMap *map, int index, int *next_index)
2270 {
2271  int merged_index = *next_index;
2272 
2273  Assert(index >= 0 && index < map->nparts);
2274  Assert(map->merged_indexes[index] == -1);
2275  Assert(!map->merged[index]);
2276  map->merged_indexes[index] = merged_index;
2277  /* Leave the merged flag alone! */
2278  *next_index = *next_index + 1;
2279  return merged_index;
2280 }
2281 
2282 /*
2283  * fix_merged_indexes
2284  * Adjust merged indexes of re-merged partitions
2285  */
2286 static void
2288  int nmerged, List *merged_indexes)
2289 {
2290  int *new_indexes;
2291  int merged_index;
2292  int i;
2293  ListCell *lc;
2294 
2295  Assert(nmerged > 0);
2296 
2297  new_indexes = (int *) palloc(sizeof(int) * nmerged);
2298  for (i = 0; i < nmerged; i++)
2299  new_indexes[i] = -1;
2300 
2301  /* Build the mapping of old merged indexes to new merged indexes. */
2302  if (outer_map->did_remapping)
2303  {
2304  for (i = 0; i < outer_map->nparts; i++)
2305  {
2306  merged_index = outer_map->old_indexes[i];
2307  if (merged_index >= 0)
2308  new_indexes[merged_index] = outer_map->merged_indexes[i];
2309  }
2310  }
2311  if (inner_map->did_remapping)
2312  {
2313  for (i = 0; i < inner_map->nparts; i++)
2314  {
2315  merged_index = inner_map->old_indexes[i];
2316  if (merged_index >= 0)
2317  new_indexes[merged_index] = inner_map->merged_indexes[i];
2318  }
2319  }
2320 
2321  /* Fix the merged_indexes list using the mapping. */
2322  foreach(lc, merged_indexes)
2323  {
2324  merged_index = lfirst_int(lc);
2325  Assert(merged_index >= 0);
2326  if (new_indexes[merged_index] >= 0)
2327  lfirst_int(lc) = new_indexes[merged_index];
2328  }
2329 
2330  pfree(new_indexes);
2331 }
2332 
2333 /*
2334  * generate_matching_part_pairs
2335  * Generate a pair of lists of partitions that produce merged partitions
2336  *
2337  * The lists of partitions are built in the order of merged partition indexes,
2338  * and returned in *outer_parts and *inner_parts.
2339  */
2340 static void
2342  PartitionMap *outer_map, PartitionMap *inner_map,
2343  int nmerged,
2344  List **outer_parts, List **inner_parts)
2345 {
2346  int outer_nparts = outer_map->nparts;
2347  int inner_nparts = inner_map->nparts;
2348  int *outer_indexes;
2349  int *inner_indexes;
2350  int max_nparts;
2351  int i;
2352 
2353  Assert(nmerged > 0);
2354  Assert(*outer_parts == NIL);
2355  Assert(*inner_parts == NIL);
2356 
2357  outer_indexes = (int *) palloc(sizeof(int) * nmerged);
2358  inner_indexes = (int *) palloc(sizeof(int) * nmerged);
2359  for (i = 0; i < nmerged; i++)
2360  outer_indexes[i] = inner_indexes[i] = -1;
2361 
2362  /* Set pairs of matching partitions. */
2363  Assert(outer_nparts == outer_rel->nparts);
2364  Assert(inner_nparts == inner_rel->nparts);
2365  max_nparts = Max(outer_nparts, inner_nparts);
2366  for (i = 0; i < max_nparts; i++)
2367  {
2368  if (i < outer_nparts)
2369  {
2370  int merged_index = outer_map->merged_indexes[i];
2371 
2372  if (merged_index >= 0)
2373  {
2374  Assert(merged_index < nmerged);
2375  outer_indexes[merged_index] = i;
2376  }
2377  }
2378  if (i < inner_nparts)
2379  {
2380  int merged_index = inner_map->merged_indexes[i];
2381 
2382  if (merged_index >= 0)
2383  {
2384  Assert(merged_index < nmerged);
2385  inner_indexes[merged_index] = i;
2386  }
2387  }
2388  }
2389 
2390  /* Build the list pairs. */
2391  for (i = 0; i < nmerged; i++)
2392  {
2393  int outer_index = outer_indexes[i];
2394  int inner_index = inner_indexes[i];
2395 
2396  /*
2397  * If both partitions are dummy, it means the merged partition that
2398  * had been assigned to the outer/inner partition was removed when
2399  * re-merging the outer/inner partition in
2400  * merge_matching_partitions(); ignore the merged partition.
2401  */
2402  if (outer_index == -1 && inner_index == -1)
2403  continue;
2404 
2405  *outer_parts = lappend(*outer_parts, outer_index >= 0 ?
2406  outer_rel->part_rels[outer_index] : NULL);
2407  *inner_parts = lappend(*inner_parts, inner_index >= 0 ?
2408  inner_rel->part_rels[inner_index] : NULL);
2409  }
2410 
2411  pfree(outer_indexes);
2412  pfree(inner_indexes);
2413 }
2414 
2415 /*
2416  * build_merged_partition_bounds
2417  * Create a PartitionBoundInfo struct from merged partition bounds
2418  */
2419 static PartitionBoundInfo
2420 build_merged_partition_bounds(char strategy, List *merged_datums,
2421  List *merged_kinds, List *merged_indexes,
2422  int null_index, int default_index)
2423 {
2424  PartitionBoundInfo merged_bounds;
2425  int ndatums = list_length(merged_datums);
2426  int pos;
2427  ListCell *lc;
2428 
2429  merged_bounds = (PartitionBoundInfo) palloc(sizeof(PartitionBoundInfoData));
2430  merged_bounds->strategy = strategy;
2431  merged_bounds->ndatums = ndatums;
2432 
2433  merged_bounds->datums = (Datum **) palloc(sizeof(Datum *) * ndatums);
2434  pos = 0;
2435  foreach(lc, merged_datums)
2436  merged_bounds->datums[pos++] = (Datum *) lfirst(lc);
2437 
2438  if (strategy == PARTITION_STRATEGY_RANGE)
2439  {
2440  Assert(list_length(merged_kinds) == ndatums);
2441  merged_bounds->kind = (PartitionRangeDatumKind **)
2442  palloc(sizeof(PartitionRangeDatumKind *) * ndatums);
2443  pos = 0;
2444  foreach(lc, merged_kinds)
2445  merged_bounds->kind[pos++] = (PartitionRangeDatumKind *) lfirst(lc);
2446 
2447  /* There are ndatums+1 indexes in the case of range partitioning. */
2448  merged_indexes = lappend_int(merged_indexes, -1);
2449  ndatums++;
2450  }
2451  else
2452  {
2453  Assert(strategy == PARTITION_STRATEGY_LIST);
2454  Assert(merged_kinds == NIL);
2455  merged_bounds->kind = NULL;
2456  }
2457 
2458  Assert(list_length(merged_indexes) == ndatums);
2459  merged_bounds->indexes = (int *) palloc(sizeof(int) * ndatums);
2460  pos = 0;
2461  foreach(lc, merged_indexes)
2462  merged_bounds->indexes[pos++] = lfirst_int(lc);
2463 
2464  merged_bounds->null_index = null_index;
2465  merged_bounds->default_index = default_index;
2466 
2467  return merged_bounds;
2468 }
2469 
2470 /*
2471  * get_range_partition
2472  * Get the next non-dummy partition of a range-partitioned relation,
2473  * returning the index of that partition
2474  *
2475  * *lb and *ub are set to the lower and upper bounds of that partition
2476  * respectively, and *lb_pos is advanced to the next lower bound, if any.
2477  */
2478 static int
2480  PartitionBoundInfo bi,
2481  int *lb_pos,
2482  PartitionRangeBound *lb,
2483  PartitionRangeBound *ub)
2484 {
2485  int part_index;
2486 
2488 
2489  do
2490  {
2491  part_index = get_range_partition_internal(bi, lb_pos, lb, ub);
2492  if (part_index == -1)
2493  return -1;
2494  } while (is_dummy_partition(rel, part_index));
2495 
2496  return part_index;
2497 }
2498 
2499 static int
2501  int *lb_pos,
2502  PartitionRangeBound *lb,
2503  PartitionRangeBound *ub)
2504 {
2505  /* Return the index as -1 if we've exhausted all lower bounds. */
2506  if (*lb_pos >= bi->ndatums)
2507  return -1;
2508 
2509  /* A lower bound should have at least one more bound after it. */
2510  Assert(*lb_pos + 1 < bi->ndatums);
2511 
2512  /* Set the lower bound. */
2513  lb->index = bi->indexes[*lb_pos];
2514  lb->datums = bi->datums[*lb_pos];
2515  lb->kind = bi->kind[*lb_pos];
2516  lb->lower = true;
2517  /* Set the upper bound. */
2518  ub->index = bi->indexes[*lb_pos + 1];
2519  ub->datums = bi->datums[*lb_pos + 1];
2520  ub->kind = bi->kind[*lb_pos + 1];
2521  ub->lower = false;
2522 
2523  /* The index assigned to an upper bound should be valid. */
2524  Assert(ub->index >= 0);
2525 
2526  /*
2527  * Advance the position to the next lower bound. If there are no bounds
2528  * left beyond the upper bound, we have reached the last lower bound.
2529  */
2530  if (*lb_pos + 2 >= bi->ndatums)
2531  *lb_pos = bi->ndatums;
2532  else
2533  {
2534  /*
2535  * If the index assigned to the bound next to the upper bound isn't
2536  * valid, that is the next lower bound; else, the upper bound is also
2537  * the lower bound of the next range partition.
2538  */
2539  if (bi->indexes[*lb_pos + 2] < 0)
2540  *lb_pos = *lb_pos + 2;
2541  else
2542  *lb_pos = *lb_pos + 1;
2543  }
2544 
2545  return ub->index;
2546 }
2547 
2548 /*
2549  * compare_range_partitions
2550  * Compare the bounds of two range partitions, and return true if the
2551  * two partitions overlap, false otherwise
2552  *
2553  * *lb_cmpval is set to -1, 0, or 1 if the outer partition's lower bound is
2554  * lower than, equal to, or higher than the inner partition's lower bound
2555  * respectively. Likewise, *ub_cmpval is set to -1, 0, or 1 if the outer
2556  * partition's upper bound is lower than, equal to, or higher than the inner
2557  * partition's upper bound respectively.
2558  */
2559 static bool
2560 compare_range_partitions(int partnatts, FmgrInfo *partsupfuncs,
2561  Oid *partcollations,
2562  PartitionRangeBound *outer_lb,
2563  PartitionRangeBound *outer_ub,
2564  PartitionRangeBound *inner_lb,
2565  PartitionRangeBound *inner_ub,
2566  int *lb_cmpval, int *ub_cmpval)
2567 {
2568  /*
2569  * Check if the outer partition's upper bound is lower than the inner
2570  * partition's lower bound; if so the partitions aren't overlapping.
2571  */
2572  if (compare_range_bounds(partnatts, partsupfuncs, partcollations,
2573  outer_ub, inner_lb) < 0)
2574  {
2575  *lb_cmpval = -1;
2576  *ub_cmpval = -1;
2577  return false;
2578  }
2579 
2580  /*
2581  * Check if the outer partition's lower bound is higher than the inner
2582  * partition's upper bound; if so the partitions aren't overlapping.
2583  */
2584  if (compare_range_bounds(partnatts, partsupfuncs, partcollations,
2585  outer_lb, inner_ub) > 0)
2586  {
2587  *lb_cmpval = 1;
2588  *ub_cmpval = 1;
2589  return false;
2590  }
2591 
2592  /* All other cases indicate overlapping partitions. */
2593  *lb_cmpval = compare_range_bounds(partnatts, partsupfuncs, partcollations,
2594  outer_lb, inner_lb);
2595  *ub_cmpval = compare_range_bounds(partnatts, partsupfuncs, partcollations,
2596  outer_ub, inner_ub);
2597  return true;
2598 }
2599 
2600 /*
2601  * get_merged_range_bounds
2602  * Given the bounds of range partitions to be joined, determine the bounds
2603  * of a merged partition produced from the range partitions
2604  *
2605  * *merged_lb and *merged_ub are set to the lower and upper bounds of the
2606  * merged partition.
2607  */
2608 static void
2609 get_merged_range_bounds(int partnatts, FmgrInfo *partsupfuncs,
2610  Oid *partcollations, JoinType jointype,
2611  PartitionRangeBound *outer_lb,
2612  PartitionRangeBound *outer_ub,
2613  PartitionRangeBound *inner_lb,
2614  PartitionRangeBound *inner_ub,
2615  int lb_cmpval, int ub_cmpval,
2616  PartitionRangeBound *merged_lb,
2617  PartitionRangeBound *merged_ub)
2618 {
2619  Assert(compare_range_bounds(partnatts, partsupfuncs, partcollations,
2620  outer_lb, inner_lb) == lb_cmpval);
2621  Assert(compare_range_bounds(partnatts, partsupfuncs, partcollations,
2622  outer_ub, inner_ub) == ub_cmpval);
2623 
2624  switch (jointype)
2625  {
2626  case JOIN_INNER:
2627  case JOIN_SEMI:
2628 
2629  /*
2630  * An INNER/SEMI join will have the rows that fit both sides, so
2631  * the lower bound of the merged partition will be the higher of
2632  * the two lower bounds, and the upper bound of the merged
2633  * partition will be the lower of the two upper bounds.
2634  */
2635  *merged_lb = (lb_cmpval > 0) ? *outer_lb : *inner_lb;
2636  *merged_ub = (ub_cmpval < 0) ? *outer_ub : *inner_ub;
2637  break;
2638 
2639  case JOIN_LEFT:
2640  case JOIN_ANTI:
2641 
2642  /*
2643  * A LEFT/ANTI join will have all the rows from the outer side, so
2644  * the bounds of the merged partition will be the same as the
2645  * outer bounds.
2646  */
2647  *merged_lb = *outer_lb;
2648  *merged_ub = *outer_ub;
2649  break;
2650 
2651  case JOIN_FULL:
2652 
2653  /*
2654  * A FULL join will have all the rows from both sides, so the
2655  * lower bound of the merged partition will be the lower of the
2656  * two lower bounds, and the upper bound of the merged partition
2657  * will be the higher of the two upper bounds.
2658  */
2659  *merged_lb = (lb_cmpval < 0) ? *outer_lb : *inner_lb;
2660  *merged_ub = (ub_cmpval > 0) ? *outer_ub : *inner_ub;
2661  break;
2662 
2663  default:
2664  elog(ERROR, "unrecognized join type: %d", (int) jointype);
2665  }
2666 }
2667 
2668 /*
2669  * add_merged_range_bounds
2670  * Add the bounds of a merged partition to the lists of range bounds
2671  */
2672 static void
2673 add_merged_range_bounds(int partnatts, FmgrInfo *partsupfuncs,
2674  Oid *partcollations,
2675  PartitionRangeBound *merged_lb,
2676  PartitionRangeBound *merged_ub,
2677  int merged_index,
2678  List **merged_datums,
2679  List **merged_kinds,
2680  List **merged_indexes)
2681 {
2682  int cmpval;
2683 
2684  if (!*merged_datums)
2685  {
2686  /* First merged partition */
2687  Assert(!*merged_kinds);
2688  Assert(!*merged_indexes);
2689  cmpval = 1;
2690  }
2691  else
2692  {
2693  PartitionRangeBound prev_ub;
2694 
2695  Assert(*merged_datums);
2696  Assert(*merged_kinds);
2697  Assert(*merged_indexes);
2698 
2699  /* Get the last upper bound. */
2700  prev_ub.index = llast_int(*merged_indexes);
2701  prev_ub.datums = (Datum *) llast(*merged_datums);
2702  prev_ub.kind = (PartitionRangeDatumKind *) llast(*merged_kinds);
2703  prev_ub.lower = false;
2704 
2705  /*
2706  * We pass lower1 = false to partition_rbound_cmp() to prevent it from
2707  * considering the last upper bound to be smaller than the lower bound
2708  * of the merged partition when the values of the two range bounds
2709  * compare equal.
2710  */
2711  cmpval = partition_rbound_cmp(partnatts, partsupfuncs, partcollations,
2712  merged_lb->datums, merged_lb->kind,
2713  false, &prev_ub);
2714  Assert(cmpval >= 0);
2715  }
2716 
2717  /*
2718  * If the lower bound is higher than the last upper bound, add the lower
2719  * bound with the index as -1 indicating that that is a lower bound; else,
2720  * the last upper bound will be reused as the lower bound of the merged
2721  * partition, so skip this.
2722  */
2723  if (cmpval > 0)
2724  {
2725  *merged_datums = lappend(*merged_datums, merged_lb->datums);
2726  *merged_kinds = lappend(*merged_kinds, merged_lb->kind);
2727  *merged_indexes = lappend_int(*merged_indexes, -1);
2728  }
2729 
2730  /* Add the upper bound and index of the merged partition. */
2731  *merged_datums = lappend(*merged_datums, merged_ub->datums);
2732  *merged_kinds = lappend(*merged_kinds, merged_ub->kind);
2733  *merged_indexes = lappend_int(*merged_indexes, merged_index);
2734 }
2735 
2736 /*
2737  * partitions_are_ordered
2738  * Determine whether the partitions described by 'boundinfo' are ordered,
2739  * that is partitions appearing earlier in the PartitionDesc sequence
2740  * contain partition keys strictly less than those appearing later.
2741  * Also, if NULL values are possible, they must come in the last
2742  * partition defined in the PartitionDesc.
2743  *
2744  * If out of order, or there is insufficient info to know the order,
2745  * then we return false.
2746  */
2747 bool
2749 {
2750  Assert(boundinfo != NULL);
2751 
2752  switch (boundinfo->strategy)
2753  {
2755 
2756  /*
2757  * RANGE-type partitioning guarantees that the partitions can be
2758  * scanned in the order that they're defined in the PartitionDesc
2759  * to provide sequential, non-overlapping ranges of tuples.
2760  * However, if a DEFAULT partition exists then it doesn't work, as
2761  * that could contain tuples from either below or above the
2762  * defined range, or tuples belonging to gaps between partitions.
2763  */
2764  if (!partition_bound_has_default(boundinfo))
2765  return true;
2766  break;
2767 
2769 
2770  /*
2771  * LIST partitioning can also guarantee ordering, but only if the
2772  * partitions don't accept interleaved values. We could likely
2773  * check for this by looping over the PartitionBound's indexes
2774  * array to check that the indexes are in order. For now, let's
2775  * just keep it simple and just accept LIST partitioning when
2776  * there's no DEFAULT partition, exactly one value per partition,
2777  * and optionally a NULL partition that does not accept any other
2778  * values. Such a NULL partition will come last in the
2779  * PartitionDesc, and the other partitions will be properly
2780  * ordered. This is a cheap test to make as it does not require
2781  * any per-partition processing. Maybe we'd like to handle more
2782  * complex cases in the future.
2783  */
2784  if (partition_bound_has_default(boundinfo))
2785  return false;
2786 
2787  if (boundinfo->ndatums + partition_bound_accepts_nulls(boundinfo)
2788  == nparts)
2789  return true;
2790  break;
2791 
2792  default:
2793  /* HASH, or some other strategy */
2794  break;
2795  }
2796 
2797  return false;
2798 }
2799 
2800 /*
2801  * check_new_partition_bound
2802  *
2803  * Checks if the new partition's bound overlaps any of the existing partitions
2804  * of parent. Also performs additional checks as necessary per strategy.
2805  */
2806 void
2808  PartitionBoundSpec *spec, ParseState *pstate)
2809 {
2811  PartitionDesc partdesc = RelationGetPartitionDesc(parent);
2812  PartitionBoundInfo boundinfo = partdesc->boundinfo;
2813  int with = -1;
2814  bool overlap = false;
2815  int overlap_location = -1;
2816 
2817  if (spec->is_default)
2818  {
2819  /*
2820  * The default partition bound never conflicts with any other
2821  * partition's; if that's what we're attaching, the only possible
2822  * problem is that one already exists, so check for that and we're
2823  * done.
2824  */
2825  if (boundinfo == NULL || !partition_bound_has_default(boundinfo))
2826  return;
2827 
2828  /* Default partition already exists, error out. */
2829  ereport(ERROR,
2830  (errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
2831  errmsg("partition \"%s\" conflicts with existing default partition \"%s\"",
2832  relname, get_rel_name(partdesc->oids[boundinfo->default_index])),
2833  parser_errposition(pstate, spec->location)));
2834  }
2835 
2836  switch (key->strategy)
2837  {
2839  {
2841  Assert(spec->remainder >= 0 && spec->remainder < spec->modulus);
2842 
2843  if (partdesc->nparts > 0)
2844  {
2845  Datum **datums = boundinfo->datums;
2846  int ndatums = boundinfo->ndatums;
2847  int greatest_modulus;
2848  int remainder;
2849  int offset;
2850  bool valid_modulus = true;
2851  int prev_modulus, /* Previous largest modulus */
2852  next_modulus; /* Next largest modulus */
2853 
2854  /*
2855  * Check rule that every modulus must be a factor of the
2856  * next larger modulus. For example, if you have a bunch
2857  * of partitions that all have modulus 5, you can add a
2858  * new partition with modulus 10 or a new partition with
2859  * modulus 15, but you cannot add both a partition with
2860  * modulus 10 and a partition with modulus 15, because 10
2861  * is not a factor of 15.
2862  *
2863  * Get the greatest (modulus, remainder) pair contained in
2864  * boundinfo->datums that is less than or equal to the
2865  * (spec->modulus, spec->remainder) pair.
2866  */
2867  offset = partition_hash_bsearch(boundinfo,
2868  spec->modulus,
2869  spec->remainder);
2870  if (offset < 0)
2871  {
2872  next_modulus = DatumGetInt32(datums[0][0]);
2873  valid_modulus = (next_modulus % spec->modulus) == 0;
2874  }
2875  else
2876  {
2877  prev_modulus = DatumGetInt32(datums[offset][0]);
2878  valid_modulus = (spec->modulus % prev_modulus) == 0;
2879 
2880  if (valid_modulus && (offset + 1) < ndatums)
2881  {
2882  next_modulus = DatumGetInt32(datums[offset + 1][0]);
2883  valid_modulus = (next_modulus % spec->modulus) == 0;
2884  }
2885  }
2886 
2887  if (!valid_modulus)
2888  ereport(ERROR,
2889  (errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
2890  errmsg("every hash partition modulus must be a factor of the next larger modulus")));
2891 
2892  greatest_modulus = get_hash_partition_greatest_modulus(boundinfo);
2893  remainder = spec->remainder;
2894 
2895  /*
2896  * Normally, the lowest remainder that could conflict with
2897  * the new partition is equal to the remainder specified
2898  * for the new partition, but when the new partition has a
2899  * modulus higher than any used so far, we need to adjust.
2900  */
2901  if (remainder >= greatest_modulus)
2902  remainder = remainder % greatest_modulus;
2903 
2904  /* Check every potentially-conflicting remainder. */
2905  do
2906  {
2907  if (boundinfo->indexes[remainder] != -1)
2908  {
2909  overlap = true;
2910  overlap_location = spec->location;
2911  with = boundinfo->indexes[remainder];
2912  break;
2913  }
2914  remainder += spec->modulus;
2915  } while (remainder < greatest_modulus);
2916  }
2917 
2918  break;
2919  }
2920 
2922  {
2924 
2925  if (partdesc->nparts > 0)
2926  {
2927  ListCell *cell;
2928 
2929  Assert(boundinfo &&
2930  boundinfo->strategy == PARTITION_STRATEGY_LIST &&
2931  (boundinfo->ndatums > 0 ||
2932  partition_bound_accepts_nulls(boundinfo) ||
2933  partition_bound_has_default(boundinfo)));
2934 
2935  foreach(cell, spec->listdatums)
2936  {
2937  Const *val = castNode(Const, lfirst(cell));
2938 
2939  overlap_location = val->location;
2940  if (!val->constisnull)
2941  {
2942  int offset;
2943  bool equal;
2944 
2945  offset = partition_list_bsearch(&key->partsupfunc[0],
2946  key->partcollation,
2947  boundinfo,
2948  val->constvalue,
2949  &equal);
2950  if (offset >= 0 && equal)
2951  {
2952  overlap = true;
2953  with = boundinfo->indexes[offset];
2954  break;
2955  }
2956  }
2957  else if (partition_bound_accepts_nulls(boundinfo))
2958  {
2959  overlap = true;
2960  with = boundinfo->null_index;
2961  break;
2962  }
2963  }
2964  }
2965 
2966  break;
2967  }
2968 
2970  {
2972  *upper;
2973  int cmpval;
2974 
2976  lower = make_one_partition_rbound(key, -1, spec->lowerdatums, true);
2977  upper = make_one_partition_rbound(key, -1, spec->upperdatums, false);
2978 
2979  /*
2980  * First check if the resulting range would be empty with
2981  * specified lower and upper bounds. partition_rbound_cmp
2982  * cannot return zero here, since the lower-bound flags are
2983  * different.
2984  */
2985  cmpval = partition_rbound_cmp(key->partnatts,
2986  key->partsupfunc,
2987  key->partcollation,
2988  lower->datums, lower->kind,
2989  true, upper);
2990  Assert(cmpval != 0);
2991  if (cmpval > 0)
2992  {
2993  /* Point to problematic key in the lower datums list. */
2994  PartitionRangeDatum *datum = list_nth(spec->lowerdatums,
2995  cmpval - 1);
2996 
2997  ereport(ERROR,
2998  (errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
2999  errmsg("empty range bound specified for partition \"%s\"",
3000  relname),
3001  errdetail("Specified lower bound %s is greater than or equal to upper bound %s.",
3004  parser_errposition(pstate, datum->location)));
3005  }
3006 
3007  if (partdesc->nparts > 0)
3008  {
3009  int offset;
3010 
3011  Assert(boundinfo &&
3012  boundinfo->strategy == PARTITION_STRATEGY_RANGE &&
3013  (boundinfo->ndatums > 0 ||
3014  partition_bound_has_default(boundinfo)));
3015 
3016  /*
3017  * Test whether the new lower bound (which is treated
3018  * inclusively as part of the new partition) lies inside
3019  * an existing partition, or in a gap.
3020  *
3021  * If it's inside an existing partition, the bound at
3022  * offset + 1 will be the upper bound of that partition,
3023  * and its index will be >= 0.
3024  *
3025  * If it's in a gap, the bound at offset + 1 will be the
3026  * lower bound of the next partition, and its index will
3027  * be -1. This is also true if there is no next partition,
3028  * since the index array is initialised with an extra -1
3029  * at the end.
3030  */
3031  offset = partition_range_bsearch(key->partnatts,
3032  key->partsupfunc,
3033  key->partcollation,
3034  boundinfo, lower,
3035  &cmpval);
3036 
3037  if (boundinfo->indexes[offset + 1] < 0)
3038  {
3039  /*
3040  * Check that the new partition will fit in the gap.
3041  * For it to fit, the new upper bound must be less
3042  * than or equal to the lower bound of the next
3043  * partition, if there is one.
3044  */
3045  if (offset + 1 < boundinfo->ndatums)
3046  {
3047  Datum *datums;
3049  bool is_lower;
3050 
3051  datums = boundinfo->datums[offset + 1];
3052  kind = boundinfo->kind[offset + 1];
3053  is_lower = (boundinfo->indexes[offset + 1] == -1);
3054 
3055  cmpval = partition_rbound_cmp(key->partnatts,
3056  key->partsupfunc,
3057  key->partcollation,
3058  datums, kind,
3059  is_lower, upper);
3060  if (cmpval < 0)
3061  {
3062  /*
3063  * Point to problematic key in the upper
3064  * datums list.
3065  */
3066  PartitionRangeDatum *datum =
3067  list_nth(spec->upperdatums, Abs(cmpval) - 1);
3068 
3069  /*
3070  * The new partition overlaps with the
3071  * existing partition between offset + 1 and
3072  * offset + 2.
3073  */
3074  overlap = true;
3075  overlap_location = datum->location;
3076  with = boundinfo->indexes[offset + 2];
3077  }
3078  }
3079  }
3080  else
3081  {
3082  /*
3083  * The new partition overlaps with the existing
3084  * partition between offset and offset + 1.
3085  */
3086  PartitionRangeDatum *datum;
3087 
3088  /*
3089  * Point to problematic key in the lower datums list;
3090  * if we have equality, point to the first one.
3091  */
3092  datum = cmpval == 0 ? linitial(spec->lowerdatums) :
3093  list_nth(spec->lowerdatums, Abs(cmpval) - 1);
3094  overlap = true;
3095  overlap_location = datum->location;
3096  with = boundinfo->indexes[offset + 1];
3097  }
3098  }
3099 
3100  break;
3101  }
3102 
3103  default:
3104  elog(ERROR, "unexpected partition strategy: %d",
3105  (int) key->strategy);
3106  }
3107 
3108  if (overlap)
3109  {
3110  Assert(with >= 0);
3111  ereport(ERROR,
3112  (errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
3113  errmsg("partition \"%s\" would overlap partition \"%s\"",
3114  relname, get_rel_name(partdesc->oids[with])),
3115  parser_errposition(pstate, overlap_location)));
3116  }
3117 }
3118 
3119 /*
3120  * check_default_partition_contents
3121  *
3122  * This function checks if there exists a row in the default partition that
3123  * would properly belong to the new partition being added. If it finds one,
3124  * it throws an error.
3125  */
3126 void
3128  PartitionBoundSpec *new_spec)
3129 {
3130  List *new_part_constraints;
3131  List *def_part_constraints;
3132  List *all_parts;
3133  ListCell *lc;
3134 
3135  new_part_constraints = (new_spec->strategy == PARTITION_STRATEGY_LIST)
3136  ? get_qual_for_list(parent, new_spec)
3137  : get_qual_for_range(parent, new_spec, false);
3138  def_part_constraints =
3139  get_proposed_default_constraint(new_part_constraints);
3140 
3141  /*
3142  * Map the Vars in the constraint expression from parent's attnos to
3143  * default_rel's.
3144  */
3145  def_part_constraints =
3146  map_partition_varattnos(def_part_constraints, 1, default_rel,
3147  parent);
3148 
3149  /*
3150  * If the existing constraints on the default partition imply that it will
3151  * not contain any row that would belong to the new partition, we can
3152  * avoid scanning the default partition.
3153  */
3154  if (PartConstraintImpliedByRelConstraint(default_rel, def_part_constraints))
3155  {
3156  ereport(DEBUG1,
3157  (errmsg("updated partition constraint for default partition \"%s\" is implied by existing constraints",
3158  RelationGetRelationName(default_rel))));
3159  return;
3160  }
3161 
3162  /*
3163  * Scan the default partition and its subpartitions, and check for rows
3164  * that do not satisfy the revised partition constraints.
3165  */
3166  if (default_rel->rd_rel->relkind == RELKIND_PARTITIONED_TABLE)
3167  all_parts = find_all_inheritors(RelationGetRelid(default_rel),
3168  AccessExclusiveLock, NULL);
3169  else
3170  all_parts = list_make1_oid(RelationGetRelid(default_rel));
3171 
3172  foreach(lc, all_parts)
3173  {
3174  Oid part_relid = lfirst_oid(lc);
3175  Relation part_rel;
3176  Expr *partition_constraint;
3177  EState *estate;
3178  ExprState *partqualstate = NULL;
3179  Snapshot snapshot;
3180  ExprContext *econtext;
3181  TableScanDesc scan;
3182  MemoryContext oldCxt;
3183  TupleTableSlot *tupslot;
3184 
3185  /* Lock already taken above. */
3186  if (part_relid != RelationGetRelid(default_rel))
3187  {
3188  part_rel = table_open(part_relid, NoLock);
3189 
3190  /*
3191  * Map the Vars in the constraint expression from default_rel's
3192  * the sub-partition's.
3193  */
3194  partition_constraint = make_ands_explicit(def_part_constraints);
3195  partition_constraint = (Expr *)
3196  map_partition_varattnos((List *) partition_constraint, 1,
3197  part_rel, default_rel);
3198 
3199  /*
3200  * If the partition constraints on default partition child imply
3201  * that it will not contain any row that would belong to the new
3202  * partition, we can avoid scanning the child table.
3203  */
3205  def_part_constraints))
3206  {
3207  ereport(DEBUG1,
3208  (errmsg("updated partition constraint for default partition \"%s\" is implied by existing constraints",
3209  RelationGetRelationName(part_rel))));
3210 
3211  table_close(part_rel, NoLock);
3212  continue;
3213  }
3214  }
3215  else
3216  {
3217  part_rel = default_rel;
3218  partition_constraint = make_ands_explicit(def_part_constraints);
3219  }
3220 
3221  /*
3222  * Only RELKIND_RELATION relations (i.e. leaf partitions) need to be
3223  * scanned.
3224  */
3225  if (part_rel->rd_rel->relkind != RELKIND_RELATION)
3226  {
3227  if (part_rel->rd_rel->relkind == RELKIND_FOREIGN_TABLE)
3228  ereport(WARNING,
3229  (errcode(ERRCODE_CHECK_VIOLATION),
3230  errmsg("skipped scanning foreign table \"%s\" which is a partition of default partition \"%s\"",
3231  RelationGetRelationName(part_rel),
3232  RelationGetRelationName(default_rel))));
3233 
3234  if (RelationGetRelid(default_rel) != RelationGetRelid(part_rel))
3235  table_close(part_rel, NoLock);
3236 
3237  continue;
3238  }
3239 
3240  estate = CreateExecutorState();
3241 
3242  /* Build expression execution states for partition check quals */
3243  partqualstate = ExecPrepareExpr(partition_constraint, estate);
3244 
3245  econtext = GetPerTupleExprContext(estate);
3246  snapshot = RegisterSnapshot(GetLatestSnapshot());
3247  tupslot = table_slot_create(part_rel, &estate->es_tupleTable);
3248  scan = table_beginscan(part_rel, snapshot, 0, NULL);
3249 
3250  /*
3251  * Switch to per-tuple memory context and reset it for each tuple
3252  * produced, so we don't leak memory.
3253  */
3255 
3256  while (table_scan_getnextslot(scan, ForwardScanDirection, tupslot))
3257  {
3258  econtext->ecxt_scantuple = tupslot;
3259 
3260  if (!ExecCheck(partqualstate, econtext))
3261  ereport(ERROR,
3262  (errcode(ERRCODE_CHECK_VIOLATION),
3263  errmsg("updated partition constraint for default partition \"%s\" would be violated by some row",
3264  RelationGetRelationName(default_rel)),
3265  errtable(default_rel)));
3266 
3267  ResetExprContext(econtext);
3269  }
3270 
3271  MemoryContextSwitchTo(oldCxt);
3272  table_endscan(scan);
3273  UnregisterSnapshot(snapshot);
3275  FreeExecutorState(estate);
3276 
3277  if (RelationGetRelid(default_rel) != RelationGetRelid(part_rel))
3278  table_close(part_rel, NoLock); /* keep the lock until commit */
3279  }
3280 }
3281 
3282 /*
3283  * get_hash_partition_greatest_modulus
3284  *
3285  * Returns the greatest modulus of the hash partition bound. The greatest
3286  * modulus will be at the end of the datums array because hash partitions are
3287  * arranged in the ascending order of their moduli and remainders.
3288  */
3289 int
3291 {
3292  Assert(bound && bound->strategy == PARTITION_STRATEGY_HASH);
3293  Assert(bound->datums && bound->ndatums > 0);
3294  Assert(DatumGetInt32(bound->datums[bound->ndatums - 1][0]) > 0);
3295 
3296  return DatumGetInt32(bound->datums[bound->ndatums - 1][0]);
3297 }
3298 
3299 /*
3300  * make_one_partition_rbound
3301  *
3302  * Return a PartitionRangeBound given a list of PartitionRangeDatum elements
3303  * and a flag telling whether the bound is lower or not. Made into a function
3304  * because there are multiple sites that want to use this facility.
3305  */
3306 static PartitionRangeBound *
3308 {
3309  PartitionRangeBound *bound;
3310  ListCell *lc;
3311  int i;
3312 
3313  Assert(datums != NIL);
3314 
3315  bound = (PartitionRangeBound *) palloc0(sizeof(PartitionRangeBound));
3316  bound->index = index;
3317  bound->datums = (Datum *) palloc0(key->partnatts * sizeof(Datum));
3318  bound->kind = (PartitionRangeDatumKind *) palloc0(key->partnatts *
3319  sizeof(PartitionRangeDatumKind));
3320  bound->lower = lower;
3321 
3322  i = 0;
3323  foreach(lc, datums)
3324  {
3326 
3327  /* What's contained in this range datum? */
3328  bound->kind[i] = datum->kind;
3329 
3330  if (datum->kind == PARTITION_RANGE_DATUM_VALUE)
3331  {
3332  Const *val = castNode(Const, datum->value);
3333 
3334  if (val->constisnull)
3335  elog(ERROR, "invalid range bound datum");
3336  bound->datums[i] = val->constvalue;
3337  }
3338 
3339  i++;
3340  }
3341 
3342  return bound;
3343 }
3344 
3345 /*
3346  * partition_rbound_cmp
3347  *
3348  * For two range bounds this decides whether the 1st one (specified by
3349  * datums1, kind1, and lower1) is <, =, or > the bound specified in *b2.
3350  *
3351  * 0 is returned if they are equal, otherwise a non-zero integer whose sign
3352  * indicates the ordering, and whose absolute value gives the 1-based
3353  * partition key number of the first mismatching column.
3354  *
3355  * partnatts, partsupfunc and partcollation give the number of attributes in the
3356  * bounds to be compared, comparison function to be used and the collations of
3357  * attributes, respectively.
3358  *
3359  * Note that if the values of the two range bounds compare equal, then we take
3360  * into account whether they are upper or lower bounds, and an upper bound is
3361  * considered to be smaller than a lower bound. This is important to the way
3362  * that RelationBuildPartitionDesc() builds the PartitionBoundInfoData
3363  * structure, which only stores the upper bound of a common boundary between
3364  * two contiguous partitions.
3365  */
3366 static int32
3367 partition_rbound_cmp(int partnatts, FmgrInfo *partsupfunc,
3368  Oid *partcollation,
3369  Datum *datums1, PartitionRangeDatumKind *kind1,
3370  bool lower1, PartitionRangeBound *b2)
3371 {
3372  int32 colnum = 0;
3373  int32 cmpval = 0; /* placate compiler */
3374  int i;
3375  Datum *datums2 = b2->datums;
3376  PartitionRangeDatumKind *kind2 = b2->kind;
3377  bool lower2 = b2->lower;
3378 
3379  for (i = 0; i < partnatts; i++)
3380  {
3381  /* Track column number in case we need it for result */
3382  colnum++;
3383 
3384  /*
3385  * First, handle cases where the column is unbounded, which should not
3386  * invoke the comparison procedure, and should not consider any later
3387  * columns. Note that the PartitionRangeDatumKind enum elements
3388  * compare the same way as the values they represent.
3389  */
3390  if (kind1[i] < kind2[i])
3391  return -colnum;
3392  else if (kind1[i] > kind2[i])
3393  return colnum;
3394  else if (kind1[i] != PARTITION_RANGE_DATUM_VALUE)
3395  {
3396  /*
3397  * The column bounds are both MINVALUE or both MAXVALUE. No later
3398  * columns should be considered, but we still need to compare
3399  * whether they are upper or lower bounds.
3400  */
3401  break;
3402  }
3403 
3404  cmpval = DatumGetInt32(FunctionCall2Coll(&partsupfunc[i],
3405  partcollation[i],
3406  datums1[i],
3407  datums2[i]));
3408  if (cmpval != 0)
3409  break;
3410  }
3411 
3412  /*
3413  * If the comparison is anything other than equal, we're done. If they
3414  * compare equal though, we still have to consider whether the boundaries
3415  * are inclusive or exclusive. Exclusive one is considered smaller of the
3416  * two.
3417  */
3418  if (cmpval == 0 && lower1 != lower2)
3419  cmpval = lower1 ? 1 : -1;
3420 
3421  return cmpval == 0 ? 0 : (cmpval < 0 ? -colnum : colnum);
3422 }
3423 
3424 /*
3425  * partition_rbound_datum_cmp
3426  *
3427  * Return whether range bound (specified in rb_datums and rb_kind)
3428  * is <, =, or > partition key of tuple (tuple_datums)
3429  *
3430  * n_tuple_datums, partsupfunc and partcollation give number of attributes in
3431  * the bounds to be compared, comparison function to be used and the collations
3432  * of attributes resp.
3433  */
3434 int32
3435 partition_rbound_datum_cmp(FmgrInfo *partsupfunc, Oid *partcollation,
3436  Datum *rb_datums, PartitionRangeDatumKind *rb_kind,
3437  Datum *tuple_datums, int n_tuple_datums)
3438 {
3439  int i;
3440  int32 cmpval = -1;
3441 
3442  for (i = 0; i < n_tuple_datums; i++)
3443  {
3444  if (rb_kind[i] == PARTITION_RANGE_DATUM_MINVALUE)
3445  return -1;
3446  else if (rb_kind[i] == PARTITION_RANGE_DATUM_MAXVALUE)
3447  return 1;
3448 
3449  cmpval = DatumGetInt32(FunctionCall2Coll(&partsupfunc[i],
3450  partcollation[i],
3451  rb_datums[i],
3452  tuple_datums[i]));
3453  if (cmpval != 0)
3454  break;
3455  }
3456 
3457  return cmpval;
3458 }
3459 
3460 /*
3461  * partition_hbound_cmp
3462  *
3463  * Compares modulus first, then remainder if modulus is equal.
3464  */
3465 static int32
3466 partition_hbound_cmp(int modulus1, int remainder1, int modulus2, int remainder2)
3467 {
3468  if (modulus1 < modulus2)
3469  return -1;
3470  if (modulus1 > modulus2)
3471  return 1;
3472  if (modulus1 == modulus2 && remainder1 != remainder2)
3473  return (remainder1 > remainder2) ? 1 : -1;
3474  return 0;
3475 }
3476 
3477 /*
3478  * partition_list_bsearch
3479  * Returns the index of the greatest bound datum that is less than equal
3480  * to the given value or -1 if all of the bound datums are greater
3481  *
3482  * *is_equal is set to true if the bound datum at the returned index is equal
3483  * to the input value.
3484  */
3485 int
3486 partition_list_bsearch(FmgrInfo *partsupfunc, Oid *partcollation,
3487  PartitionBoundInfo boundinfo,
3488  Datum value, bool *is_equal)
3489 {
3490  int lo,
3491  hi,
3492  mid;
3493 
3494  lo = -1;
3495  hi = boundinfo->ndatums - 1;
3496  while (lo < hi)
3497  {
3498  int32 cmpval;
3499 
3500  mid = (lo + hi + 1) / 2;
3501  cmpval = DatumGetInt32(FunctionCall2Coll(&partsupfunc[0],
3502  partcollation[0],
3503  boundinfo->datums[mid][0],
3504  value));
3505  if (cmpval <= 0)
3506  {
3507  lo = mid;
3508  *is_equal = (cmpval == 0);
3509  if (*is_equal)
3510  break;
3511  }
3512  else
3513  hi = mid - 1;
3514  }
3515 
3516  return lo;
3517 }
3518 
3519 /*
3520  * partition_range_bsearch
3521  * Returns the index of the greatest range bound that is less than or
3522  * equal to the given range bound or -1 if all of the range bounds are
3523  * greater
3524  *
3525  * Upon return from this function, *cmpval is set to 0 if the bound at the
3526  * returned index matches the input range bound exactly, otherwise a
3527  * non-zero integer whose sign indicates the ordering, and whose absolute
3528  * value gives the 1-based partition key number of the first mismatching
3529  * column.
3530  */
3531 static int
3532 partition_range_bsearch(int partnatts, FmgrInfo *partsupfunc,
3533  Oid *partcollation,
3534  PartitionBoundInfo boundinfo,
3535  PartitionRangeBound *probe, int32 *cmpval)
3536 {
3537  int lo,
3538  hi,
3539  mid;
3540 
3541  lo = -1;
3542  hi = boundinfo->ndatums - 1;
3543  while (lo < hi)
3544  {
3545  mid = (lo + hi + 1) / 2;
3546  *cmpval = partition_rbound_cmp(partnatts, partsupfunc,
3547  partcollation,
3548  boundinfo->datums[mid],
3549  boundinfo->kind[mid],
3550  (boundinfo->indexes[mid] == -1),
3551  probe);
3552  if (*cmpval <= 0)
3553  {
3554  lo = mid;
3555  if (*cmpval == 0)
3556  break;
3557  }
3558  else
3559  hi = mid - 1;
3560  }
3561 
3562  return lo;
3563 }
3564 
3565 /*
3566  * partition_range_datum_bsearch
3567  * Returns the index of the greatest range bound that is less than or
3568  * equal to the given tuple or -1 if all of the range bounds are greater
3569  *
3570  * *is_equal is set to true if the range bound at the returned index is equal
3571  * to the input tuple.
3572  */
3573 int
3574 partition_range_datum_bsearch(FmgrInfo *partsupfunc, Oid *partcollation,
3575  PartitionBoundInfo boundinfo,
3576  int nvalues, Datum *values, bool *is_equal)
3577 {
3578  int lo,
3579  hi,
3580  mid;
3581 
3582  lo = -1;
3583  hi = boundinfo->ndatums - 1;
3584  while (lo < hi)
3585  {
3586  int32 cmpval;
3587 
3588  mid = (lo + hi + 1) / 2;
3589  cmpval = partition_rbound_datum_cmp(partsupfunc,
3590  partcollation,
3591  boundinfo->datums[mid],
3592  boundinfo->kind[mid],
3593  values,
3594  nvalues);
3595  if (cmpval <= 0)
3596  {
3597  lo = mid;
3598  *is_equal = (cmpval == 0);
3599 
3600  if (*is_equal)
3601  break;
3602  }
3603  else
3604  hi = mid - 1;
3605  }
3606 
3607  return lo;
3608 }
3609 
3610 /*
3611  * partition_hash_bsearch
3612  * Returns the index of the greatest (modulus, remainder) pair that is
3613  * less than or equal to the given (modulus, remainder) pair or -1 if
3614  * all of them are greater
3615  */
3616 int
3618  int modulus, int remainder)
3619 {
3620  int lo,
3621  hi,
3622  mid;
3623 
3624  lo = -1;
3625  hi = boundinfo->ndatums - 1;
3626  while (lo < hi)
3627  {
3628  int32 cmpval,
3629  bound_modulus,
3630  bound_remainder;
3631 
3632  mid = (lo + hi + 1) / 2;
3633  bound_modulus = DatumGetInt32(boundinfo->datums[mid][0]);
3634  bound_remainder = DatumGetInt32(boundinfo->datums[mid][1]);
3635  cmpval = partition_hbound_cmp(bound_modulus, bound_remainder,
3636  modulus, remainder);
3637  if (cmpval <= 0)
3638  {
3639  lo = mid;
3640 
3641  if (cmpval == 0)
3642  break;
3643  }
3644  else
3645  hi = mid - 1;
3646  }
3647 
3648  return lo;
3649 }
3650 
3651 /*
3652  * qsort_partition_hbound_cmp
3653  *
3654  * Hash bounds are sorted by modulus, then by remainder.
3655  */
3656 static int32
3657 qsort_partition_hbound_cmp(const void *a, const void *b)
3658 {
3659  PartitionHashBound *h1 = (*(PartitionHashBound *const *) a);
3660  PartitionHashBound *h2 = (*(PartitionHashBound *const *) b);
3661 
3662  return partition_hbound_cmp(h1->modulus, h1->remainder,
3663  h2->modulus, h2->remainder);
3664 }
3665 
3666 /*
3667  * qsort_partition_list_value_cmp
3668  *
3669  * Compare two list partition bound datums.
3670  */
3671 static int32
3672 qsort_partition_list_value_cmp(const void *a, const void *b, void *arg)
3673 {
3674  Datum val1 = (*(PartitionListValue *const *) a)->value,
3675  val2 = (*(PartitionListValue *const *) b)->value;
3676  PartitionKey key = (PartitionKey) arg;
3677 
3679  key->partcollation[0],
3680  val1, val2));
3681 }
3682 
3683 /*
3684  * qsort_partition_rbound_cmp
3685  *
3686  * Used when sorting range bounds across all range partitions.
3687  */
3688 static int32
3689 qsort_partition_rbound_cmp(const void *a, const void *b, void *arg)
3690 {
3691  PartitionRangeBound *b1 = (*(PartitionRangeBound *const *) a);
3692  PartitionRangeBound *b2 = (*(PartitionRangeBound *const *) b);
3693  PartitionKey key = (PartitionKey) arg;
3694 
3695  return compare_range_bounds(key->partnatts, key->partsupfunc,
3696  key->partcollation,
3697  b1, b2);
3698 }
3699 
3700 /*
3701  * get_partition_bound_num_indexes
3702  *
3703  * Returns the number of the entries in the partition bound indexes array.
3704  */
3705 static int
3707 {
3708  int num_indexes;
3709 
3710  Assert(bound);
3711 
3712  switch (bound->strategy)
3713  {
3715 
3716  /*
3717  * The number of the entries in the indexes array is same as the
3718  * greatest modulus.
3719  */
3720  num_indexes = get_hash_partition_greatest_modulus(bound);
3721  break;
3722 
3724  num_indexes = bound->ndatums;
3725  break;
3726 
3728  /* Range partitioned table has an extra index. */
3729  num_indexes = bound->ndatums + 1;
3730  break;
3731 
3732  default:
3733  elog(ERROR, "unexpected partition strategy: %d",
3734  (int) bound->strategy);
3735  }
3736 
3737  return num_indexes;
3738 }
3739 
3740 /*
3741  * get_partition_operator
3742  *
3743  * Return oid of the operator of the given strategy for the given partition
3744  * key column. It is assumed that the partitioning key is of the same type as
3745  * the chosen partitioning opclass, or at least binary-compatible. In the
3746  * latter case, *need_relabel is set to true if the opclass is not of a
3747  * polymorphic type (indicating a RelabelType node needed on top), otherwise
3748  * false.
3749  */
3750 static Oid
3752  bool *need_relabel)
3753 {
3754  Oid operoid;
3755 
3756  /*
3757  * Get the operator in the partitioning opfamily using the opclass'
3758  * declared input type as both left- and righttype.
3759  */
3760  operoid = get_opfamily_member(key->partopfamily[col],
3761  key->partopcintype[col],
3762  key->partopcintype[col],
3763  strategy);
3764  if (!OidIsValid(operoid))
3765  elog(ERROR, "missing operator %d(%u,%u) in partition opfamily %u",
3766  strategy, key->partopcintype[col], key->partopcintype[col],
3767  key->partopfamily[col]);
3768 
3769  /*
3770  * If the partition key column is not of the same type as the operator
3771  * class and not polymorphic, tell caller to wrap the non-Const expression
3772  * in a RelabelType. This matches what parse_coerce.c does.
3773  */
3774  *need_relabel = (key->parttypid[col] != key->partopcintype[col] &&
3775  key->partopcintype[col] != RECORDOID &&
3776  !IsPolymorphicType(key->partopcintype[col]));
3777 
3778  return operoid;
3779 }
3780 
3781 /*
3782  * make_partition_op_expr
3783  * Returns an Expr for the given partition key column with arg1 and
3784  * arg2 as its leftop and rightop, respectively
3785  */
3786 static Expr *
3788  uint16 strategy, Expr *arg1, Expr *arg2)
3789 {
3790  Oid operoid;
3791  bool need_relabel = false;
3792  Expr *result = NULL;
3793 
3794  /* Get the correct btree operator for this partitioning column */
3795  operoid = get_partition_operator(key, keynum, strategy, &need_relabel);
3796 
3797  /*
3798  * Chosen operator may be such that the non-Const operand needs to be
3799  * coerced, so apply the same; see the comment in
3800  * get_partition_operator().
3801  */
3802  if (!IsA(arg1, Const) &&
3803  (need_relabel ||
3804  key->partcollation[keynum] != key->parttypcoll[keynum]))
3805  arg1 = (Expr *) makeRelabelType(arg1,
3806  key->partopcintype[keynum],
3807  -1,
3808  key->partcollation[keynum],
3810 
3811  /* Generate the actual expression */
3812  switch (key->strategy)
3813  {
3815  {
3816  List *elems = (List *) arg2;
3817  int nelems = list_length(elems);
3818 
3819  Assert(nelems >= 1);
3820  Assert(keynum == 0);
3821 
3822  if (nelems > 1 &&
3823  !type_is_array(key->parttypid[keynum]))
3824  {
3825  ArrayExpr *arrexpr;
3826  ScalarArrayOpExpr *saopexpr;
3827 
3828  /* Construct an ArrayExpr for the right-hand inputs */
3829  arrexpr = makeNode(ArrayExpr);
3830  arrexpr->array_typeid =
3831  get_array_type(key->parttypid[keynum]);
3832  arrexpr->array_collid = key->parttypcoll[keynum];
3833  arrexpr->element_typeid = key->parttypid[keynum];
3834  arrexpr->elements = elems;
3835  arrexpr->multidims = false;
3836  arrexpr->location = -1;
3837 
3838  /* Build leftop = ANY (rightop) */
3839  saopexpr = makeNode(ScalarArrayOpExpr);
3840  saopexpr->opno = operoid;
3841  saopexpr->opfuncid = get_opcode(operoid);
3842  saopexpr->useOr = true;
3843  saopexpr->inputcollid = key->partcollation[keynum];
3844  saopexpr->args = list_make2(arg1, arrexpr);
3845  saopexpr->location = -1;
3846 
3847  result = (Expr *) saopexpr;
3848  }
3849  else
3850  {
3851  List *elemops = NIL;
3852  ListCell *lc;
3853 
3854  foreach(lc, elems)
3855  {
3856  Expr *elem = lfirst(lc),
3857  *elemop;
3858 
3859  elemop = make_opclause(operoid,
3860  BOOLOID,
3861  false,
3862  arg1, elem,
3863  InvalidOid,
3864  key->partcollation[keynum]);
3865  elemops = lappend(elemops, elemop);
3866  }
3867 
3868  result = nelems > 1 ? makeBoolExpr(OR_EXPR, elemops, -1) : linitial(elemops);
3869  }
3870  break;
3871  }
3872 
3874  result = make_opclause(operoid,
3875  BOOLOID,
3876  false,
3877  arg1, arg2,
3878  InvalidOid,
3879  key->partcollation[keynum]);
3880  break;
3881 
3882  default:
3883  elog(ERROR, "invalid partitioning strategy");
3884  break;
3885  }
3886 
3887  return result;
3888 }
3889 
3890 /*
3891  * get_qual_for_hash
3892  *
3893  * Returns a CHECK constraint expression to use as a hash partition's
3894  * constraint, given the parent relation and partition bound structure.
3895  *
3896  * The partition constraint for a hash partition is always a call to the
3897  * built-in function satisfies_hash_partition().
3898  */
3899 static List *
3901 {
3903  FuncExpr *fexpr;
3904  Node *relidConst;
3905  Node *modulusConst;
3906  Node *remainderConst;
3907  List *args;
3908  ListCell *partexprs_item;
3909  int i;
3910 
3911  /* Fixed arguments. */
3912  relidConst = (Node *) makeConst(OIDOID,
3913  -1,
3914  InvalidOid,
3915  sizeof(Oid),
3917  false,
3918  true);
3919 
3920  modulusConst = (Node *) makeConst(INT4OID,
3921  -1,
3922  InvalidOid,
3923  sizeof(int32),
3924  Int32GetDatum(spec->modulus),
3925  false,
3926  true);
3927 
3928  remainderConst = (Node *) makeConst(INT4OID,
3929  -1,
3930  InvalidOid,
3931  sizeof(int32),
3932  Int32GetDatum(spec->remainder),
3933  false,
3934  true);
3935 
3936  args = list_make3(relidConst, modulusConst, remainderConst);
3937  partexprs_item = list_head(key->partexprs);
3938 
3939  /* Add an argument for each key column. */
3940  for (i = 0; i < key->partnatts; i++)
3941  {
3942  Node *keyCol;
3943 
3944  /* Left operand */
3945  if (key->partattrs[i] != 0)
3946  {
3947  keyCol = (Node *) makeVar(1,
3948  key->partattrs[i],
3949  key->parttypid[i],
3950  key->parttypmod[i],
3951  key->parttypcoll[i],
3952  0);
3953  }
3954  else
3955  {
3956  keyCol = (Node *) copyObject(lfirst(partexprs_item));
3957  partexprs_item = lnext(key->partexprs, partexprs_item);
3958  }
3959 
3960  args = lappend(args, keyCol);
3961  }
3962 
3963  fexpr = makeFuncExpr(F_SATISFIES_HASH_PARTITION,
3964  BOOLOID,
3965  args,
3966  InvalidOid,
3967  InvalidOid,
3969 
3970  return list_make1(fexpr);
3971 }
3972 
3973 /*
3974  * get_qual_for_list
3975  *
3976  * Returns an implicit-AND list of expressions to use as a list partition's
3977  * constraint, given the parent relation and partition bound structure.
3978  *
3979  * The function returns NIL for a default partition when it's the only
3980  * partition since in that case there is no constraint.
3981  */
3982 static List *
3984 {
3986  List *result;
3987  Expr *keyCol;
3988  Expr *opexpr;
3989  NullTest *nulltest;
3990  ListCell *cell;
3991  List *elems = NIL;
3992  bool list_has_null = false;
3993 
3994  /*
3995  * Only single-column list partitioning is supported, so we are worried
3996  * only about the partition key with index 0.
3997  */
3998  Assert(key->partnatts == 1);
3999 
4000  /* Construct Var or expression representing the partition column */
4001  if (key->partattrs[0] != 0)
4002  keyCol = (Expr *) makeVar(1,
4003  key->partattrs[0],
4004  key->parttypid[0],
4005  key->parttypmod[0],
4006  key->parttypcoll[0],
4007  0);
4008  else
4009  keyCol = (Expr *) copyObject(linitial(key->partexprs));
4010 
4011  /*
4012  * For default list partition, collect datums for all the partitions. The
4013  * default partition constraint should check that the partition key is
4014  * equal to none of those.
4015  */
4016  if (spec->is_default)
4017  {
4018  int i;
4019  int ndatums = 0;
4020  PartitionDesc pdesc = RelationGetPartitionDesc(parent);
4021  PartitionBoundInfo boundinfo = pdesc->boundinfo;
4022 
4023  if (boundinfo)
4024  {
4025  ndatums = boundinfo->ndatums;
4026 
4027  if (partition_bound_accepts_nulls(boundinfo))
4028  list_has_null = true;
4029  }
4030 
4031  /*
4032  * If default is the only partition, there need not be any partition
4033  * constraint on it.
4034  */
4035  if (ndatums == 0 && !list_has_null)
4036  return NIL;
4037 
4038  for (i = 0; i < ndatums; i++)
4039  {
4040  Const *val;
4041 
4042  /*
4043  * Construct Const from known-not-null datum. We must be careful
4044  * to copy the value, because our result has to be able to outlive
4045  * the relcache entry we're copying from.
4046  */
4047  val = makeConst(key->parttypid[0],
4048  key->parttypmod[0],
4049  key->parttypcoll[0],
4050  key->parttyplen[0],
4051  datumCopy(*boundinfo->datums[i],
4052  key->parttypbyval[0],
4053  key->parttyplen[0]),
4054  false, /* isnull */
4055  key->parttypbyval[0]);
4056 
4057  elems = lappend(elems, val);
4058  }
4059  }
4060  else
4061  {
4062  /*
4063  * Create list of Consts for the allowed values, excluding any nulls.
4064  */
4065  foreach(cell, spec->listdatums)
4066  {
4067  Const *val = castNode(Const, lfirst(cell));
4068 
4069  if (val->constisnull)
4070  list_has_null = true;
4071  else
4072  elems = lappend(elems, copyObject(val));
4073  }
4074  }
4075 
4076  if (elems)
4077  {
4078  /*
4079  * Generate the operator expression from the non-null partition
4080  * values.
4081  */
4083  keyCol, (Expr *) elems);
4084  }
4085  else
4086  {
4087  /*
4088  * If there are no partition values, we don't need an operator
4089  * expression.
4090  */
4091  opexpr = NULL;
4092  }
4093 
4094  if (!list_has_null)
4095  {
4096  /*
4097  * Gin up a "col IS NOT NULL" test that will be AND'd with the main
4098  * expression. This might seem redundant, but the partition routing
4099  * machinery needs it.
4100  */
4101  nulltest = makeNode(NullTest);
4102  nulltest->arg = keyCol;
4103  nulltest->nulltesttype = IS_NOT_NULL;
4104  nulltest->argisrow = false;
4105  nulltest->location = -1;
4106 
4107  result = opexpr ? list_make2(nulltest, opexpr) : list_make1(nulltest);
4108  }
4109  else
4110  {
4111  /*
4112  * Gin up a "col IS NULL" test that will be OR'd with the main
4113  * expression.
4114  */
4115  nulltest = makeNode(NullTest);
4116  nulltest->arg = keyCol;
4117  nulltest->nulltesttype = IS_NULL;
4118  nulltest->argisrow = false;
4119  nulltest->location = -1;
4120 
4121  if (opexpr)
4122  {
4123  Expr *or;
4124 
4125  or = makeBoolExpr(OR_EXPR, list_make2(nulltest, opexpr), -1);
4126  result = list_make1(or);
4127  }
4128  else
4129  result = list_make1(nulltest);
4130  }
4131 
4132  /*
4133  * Note that, in general, applying NOT to a constraint expression doesn't
4134  * necessarily invert the set of rows it accepts, because NOT (NULL) is
4135  * NULL. However, the partition constraints we construct here never
4136  * evaluate to NULL, so applying NOT works as intended.
4137  */
4138  if (spec->is_default)
4139  {
4140  result = list_make1(make_ands_explicit(result));
4141  result = list_make1(makeBoolExpr(NOT_EXPR, result, -1));
4142  }
4143 
4144  return result;
4145 }
4146 
4147 /*
4148  * get_qual_for_range
4149  *
4150  * Returns an implicit-AND list of expressions to use as a range partition's
4151  * constraint, given the parent relation and partition bound structure.
4152  *
4153  * For a multi-column range partition key, say (a, b, c), with (al, bl, cl)
4154  * as the lower bound tuple and (au, bu, cu) as the upper bound tuple, we
4155  * generate an expression tree of the following form:
4156  *
4157  * (a IS NOT NULL) and (b IS NOT NULL) and (c IS NOT NULL)
4158  * AND
4159  * (a > al OR (a = al AND b > bl) OR (a = al AND b = bl AND c >= cl))
4160  * AND
4161  * (a < au OR (a = au AND b < bu) OR (a = au AND b = bu AND c < cu))
4162  *
4163  * It is often the case that a prefix of lower and upper bound tuples contains
4164  * the same values, for example, (al = au), in which case, we will emit an
4165  * expression tree of the following form:
4166  *
4167  * (a IS NOT NULL) and (b IS NOT NULL) and (c IS NOT NULL)
4168  * AND
4169  * (a = al)
4170  * AND
4171  * (b > bl OR (b = bl AND c >= cl))
4172  * AND
4173  * (b < bu OR (b = bu AND c < cu))
4174  *
4175  * If a bound datum is either MINVALUE or MAXVALUE, these expressions are
4176  * simplified using the fact that any value is greater than MINVALUE and less
4177  * than MAXVALUE. So, for example, if cu = MAXVALUE, c < cu is automatically
4178  * true, and we need not emit any expression for it, and the last line becomes
4179  *
4180  * (b < bu) OR (b = bu), which is simplified to (b <= bu)
4181  *
4182  * In most common cases with only one partition column, say a, the following
4183  * expression tree will be generated: a IS NOT NULL AND a >= al AND a < au
4184  *
4185  * For default partition, it returns the negation of the constraints of all
4186  * the other partitions.
4187  *
4188  * External callers should pass for_default as false; we set it to true only
4189  * when recursing.
4190  */
4191 static List *
4193  bool for_default)
4194 {
4195  List *result = NIL;
4196  ListCell *cell1,
4197  *cell2,
4198  *partexprs_item,
4199  *partexprs_item_saved;
4200  int i,
4201  j;
4202  PartitionRangeDatum *ldatum,
4203  *udatum;
4205  Expr *keyCol;
4206  Const *lower_val,
4207  *upper_val;
4208  List *lower_or_arms,
4209  *upper_or_arms;
4210  int num_or_arms,
4211  current_or_arm;
4212  ListCell *lower_or_start_datum,
4213  *upper_or_start_datum;
4214  bool need_next_lower_arm,
4215  need_next_upper_arm;
4216 
4217  if (spec->is_default)
4218  {
4219  List *or_expr_args = NIL;
4220  PartitionDesc pdesc = RelationGetPartitionDesc(parent);
4221  Oid *inhoids = pdesc->oids;
4222  int nparts = pdesc->nparts,
4223  i;
4224 
4225  for (i = 0; i < nparts; i++)
4226  {
4227  Oid inhrelid = inhoids[i];
4228  HeapTuple tuple;
4229  Datum datum;
4230  bool isnull;
4231  PartitionBoundSpec *bspec;
4232 
4233  tuple = SearchSysCache1(RELOID, inhrelid);
4234  if (!HeapTupleIsValid(tuple))
4235  elog(ERROR, "cache lookup failed for relation %u", inhrelid);
4236 
4237  datum = SysCacheGetAttr(RELOID, tuple,
4238  Anum_pg_class_relpartbound,
4239  &isnull);
4240  if (isnull)
4241  elog(ERROR, "null relpartbound for relation %u", inhrelid);
4242 
4243  bspec = (PartitionBoundSpec *)
4245  if (!IsA(bspec, PartitionBoundSpec))
4246  elog(ERROR, "expected PartitionBoundSpec");
4247 
4248  if (!bspec->is_default)
4249  {
4250  List *part_qual;
4251 
4252  part_qual = get_qual_for_range(parent, bspec, true);
4253 
4254  /*
4255  * AND the constraints of the partition and add to
4256  * or_expr_args
4257  */
4258  or_expr_args = lappend(or_expr_args, list_length(part_qual) > 1
4259  ? makeBoolExpr(AND_EXPR, part_qual, -1)
4260  : linitial(part_qual));
4261  }
4262  ReleaseSysCache(tuple);
4263  }
4264 
4265  if (or_expr_args != NIL)
4266  {
4267  Expr *other_parts_constr;
4268 
4269  /*
4270  * Combine the constraints obtained for non-default partitions
4271  * using OR. As requested, each of the OR's args doesn't include
4272  * the NOT NULL test for partition keys (which is to avoid its
4273  * useless repetition). Add the same now.
4274  */
4275  other_parts_constr =
4278  list_length(or_expr_args) > 1
4279  ? makeBoolExpr(OR_EXPR, or_expr_args,
4280  -1)
4281  : linitial(or_expr_args)),
4282  -1);
4283 
4284  /*
4285  * Finally, the default partition contains everything *NOT*
4286  * contained in the non-default partitions.
4287  */
4288  result = list_make1(makeBoolExpr(NOT_EXPR,
4289  list_make1(other_parts_constr), -1));
4290  }
4291 
4292  return result;
4293  }
4294 
4295  /*
4296  * If it is the recursive call for default, we skip the get_range_nulltest
4297  * to avoid accumulating the NullTest on the same keys for each partition.
4298  */
4299  if (!for_default)
4300  result = get_range_nulltest(key);
4301 
4302  /*
4303  * Iterate over the key columns and check if the corresponding lower and
4304  * upper datums are equal using the btree equality operator for the
4305  * column's type. If equal, we emit single keyCol = common_value
4306  * expression. Starting from the first column for which the corresponding
4307  * lower and upper bound datums are not equal, we generate OR expressions
4308  * as shown in the function's header comment.
4309  */
4310  i = 0;
4311  partexprs_item = list_head(key->partexprs);
4312  partexprs_item_saved = partexprs_item; /* placate compiler */
4313  forboth(cell1, spec->lowerdatums, cell2, spec->upperdatums)
4314  {
4315  EState *estate;
4316  MemoryContext oldcxt;
4317  Expr *test_expr;
4318  ExprState *test_exprstate;
4319  Datum test_result;
4320  bool isNull;
4321 
4322  ldatum = castNode(PartitionRangeDatum, lfirst(cell1));
4323  udatum = castNode(PartitionRangeDatum, lfirst(cell2));
4324 
4325  /*
4326  * Since get_range_key_properties() modifies partexprs_item, and we
4327  * might need to start over from the previous expression in the later
4328  * part of this function, save away the current value.
4329  */
4330  partexprs_item_saved = partexprs_item;
4331 
4332  get_range_key_properties(key, i, ldatum, udatum,
4333  &partexprs_item,
4334  &keyCol,
4335  &lower_val, &upper_val);
4336 
4337  /*
4338  * If either value is NULL, the corresponding partition bound is
4339  * either MINVALUE or MAXVALUE, and we treat them as unequal, because
4340  * even if they're the same, there is no common value to equate the
4341  * key column with.
4342  */
4343  if (!lower_val || !upper_val)
4344  break;
4345 
4346  /* Create the test expression */
4347  estate = CreateExecutorState();
4348  oldcxt = MemoryContextSwitchTo(estate->es_query_cxt);
4349  test_expr = make_partition_op_expr(key, i, BTEqualStrategyNumber,
4350  (Expr *) lower_val,
4351  (Expr *) upper_val);
4352  fix_opfuncids((Node *) test_expr);
4353  test_exprstate = ExecInitExpr(test_expr, NULL);
4354  test_result = ExecEvalExprSwitchContext(test_exprstate,
4355  GetPerTupleExprContext(estate),
4356  &isNull);
4357  MemoryContextSwitchTo(oldcxt);
4358  FreeExecutorState(estate);
4359 
4360  /* If not equal, go generate the OR expressions */
4361  if (!DatumGetBool(test_result))
4362  break;
4363 
4364  /*
4365  * The bounds for the last key column can't be equal, because such a
4366  * range partition would never be allowed to be defined (it would have
4367  * an empty range otherwise).
4368  */
4369  if (i == key->partnatts - 1)
4370  elog(ERROR, "invalid range bound specification");
4371 
4372  /* Equal, so generate keyCol = lower_val expression */
4373  result = lappend(result,
4375  keyCol, (Expr *) lower_val));
4376 
4377  i++;
4378  }
4379 
4380  /* First pair of lower_val and upper_val that are not equal. */
4381  lower_or_start_datum = cell1;
4382  upper_or_start_datum = cell2;
4383 
4384  /* OR will have as many arms as there are key columns left. */
4385  num_or_arms = key->partnatts - i;
4386  current_or_arm = 0;
4387  lower_or_arms = upper_or_arms = NIL;
4388  need_next_lower_arm = need_next_upper_arm = true;
4389  while (current_or_arm < num_or_arms)
4390  {
4391  List *lower_or_arm_args = NIL,
4392  *upper_or_arm_args = NIL;
4393 
4394  /* Restart scan of columns from the i'th one */
4395  j = i;
4396  partexprs_item = partexprs_item_saved;
4397 
4398  for_both_cell(cell1, spec->lowerdatums, lower_or_start_datum,
4399  cell2, spec->upperdatums, upper_or_start_datum)
4400  {
4401  PartitionRangeDatum *ldatum_next = NULL,
4402  *udatum_next = NULL;
4403 
4404  ldatum = castNode(PartitionRangeDatum, lfirst(cell1));
4405  if (lnext(spec->lowerdatums, cell1))
4406  ldatum_next = castNode(PartitionRangeDatum,
4407  lfirst(lnext(spec->lowerdatums, cell1)));
4408  udatum = castNode(PartitionRangeDatum, lfirst(cell2));
4409  if (lnext(spec->upperdatums, cell2))
4410  udatum_next = castNode(PartitionRangeDatum,
4411  lfirst(lnext(spec->upperdatums, cell2)));
4412  get_range_key_properties(key, j, ldatum, udatum,
4413  &partexprs_item,
4414  &keyCol,
4415  &lower_val, &upper_val);
4416 
4417  if (need_next_lower_arm && lower_val)
4418  {
4419  uint16 strategy;
4420 
4421  /*
4422  * For the non-last columns of this arm, use the EQ operator.
4423  * For the last column of this arm, use GT, unless this is the
4424  * last column of the whole bound check, or the next bound
4425  * datum is MINVALUE, in which case use GE.
4426  */
4427  if (j - i < current_or_arm)
4428  strategy = BTEqualStrategyNumber;
4429  else if (j == key->partnatts - 1 ||
4430  (ldatum_next &&
4431  ldatum_next->kind == PARTITION_RANGE_DATUM_MINVALUE))
4432  strategy = BTGreaterEqualStrategyNumber;
4433  else
4434  strategy = BTGreaterStrategyNumber;
4435 
4436  lower_or_arm_args = lappend(lower_or_arm_args,
4437  make_partition_op_expr(key, j,
4438  strategy,
4439  keyCol,
4440  (Expr *) lower_val));
4441  }
4442 
4443  if (need_next_upper_arm && upper_val)
4444  {
4445  uint16 strategy;
4446 
4447  /*
4448  * For the non-last columns of this arm, use the EQ operator.
4449  * For the last column of this arm, use LT, unless the next
4450  * bound datum is MAXVALUE, in which case use LE.
4451  */
4452  if (j - i < current_or_arm)
4453  strategy = BTEqualStrategyNumber;
4454  else if (udatum_next &&
4455  udatum_next->kind == PARTITION_RANGE_DATUM_MAXVALUE)
4456  strategy = BTLessEqualStrategyNumber;
4457  else
4458  strategy = BTLessStrategyNumber;
4459 
4460  upper_or_arm_args = lappend(upper_or_arm_args,
4461  make_partition_op_expr(key, j,
4462  strategy,
4463  keyCol,
4464  (Expr *) upper_val));
4465  }
4466 
4467  /*
4468  * Did we generate enough of OR's arguments? First arm considers
4469  * the first of the remaining columns, second arm considers first
4470  * two of the remaining columns, and so on.
4471  */
4472  ++j;
4473  if (j - i > current_or_arm)
4474  {
4475  /*
4476  * We must not emit any more arms if the new column that will
4477  * be considered is unbounded, or this one was.
4478  */
4479  if (!lower_val || !ldatum_next ||
4480  ldatum_next->kind != PARTITION_RANGE_DATUM_VALUE)
4481  need_next_lower_arm = false;
4482  if (!upper_val || !udatum_next ||
4483  udatum_next->kind != PARTITION_RANGE_DATUM_VALUE)
4484  need_next_upper_arm = false;
4485  break;
4486  }
4487  }
4488 
4489  if (lower_or_arm_args != NIL)
4490  lower_or_arms = lappend(lower_or_arms,
4491  list_length(lower_or_arm_args) > 1
4492  ? makeBoolExpr(AND_EXPR, lower_or_arm_args, -1)
4493  : linitial(lower_or_arm_args));
4494 
4495  if (upper_or_arm_args != NIL)
4496  upper_or_arms = lappend(upper_or_arms,
4497  list_length(upper_or_arm_args) > 1
4498  ? makeBoolExpr(AND_EXPR, upper_or_arm_args, -1)
4499  : linitial(upper_or_arm_args));
4500 
4501  /* If no work to do in the next iteration, break away. */
4502  if (!need_next_lower_arm && !need_next_upper_arm)
4503  break;
4504 
4505  ++current_or_arm;
4506  }
4507 
4508  /*
4509  * Generate the OR expressions for each of lower and upper bounds (if
4510  * required), and append to the list of implicitly ANDed list of
4511  * expressions.
4512  */
4513  if (lower_or_arms != NIL)
4514  result = lappend(result,
4515  list_length(lower_or_arms) > 1
4516  ? makeBoolExpr(OR_EXPR, lower_or_arms, -1)
4517  : linitial(lower_or_arms));
4518  if (upper_or_arms != NIL)
4519  result = lappend(result,
4520  list_length(upper_or_arms) > 1
4521  ? makeBoolExpr(OR_EXPR, upper_or_arms, -1)
4522  : linitial(upper_or_arms));
4523 
4524  /*
4525  * As noted above, for non-default, we return list with constant TRUE. If
4526  * the result is NIL during the recursive call for default, it implies
4527  * this is the only other partition which can hold every value of the key
4528  * except NULL. Hence we return the NullTest result skipped earlier.
4529  */
4530  if (result == NIL)
4531  result = for_default
4532  ? get_range_nulltest(key)
4533  : list_make1(makeBoolConst(true, false));
4534 
4535  return result;
4536 }
4537 
4538 /*
4539  * get_range_key_properties
4540  * Returns range partition key information for a given column
4541  *
4542  * This is a subroutine for get_qual_for_range, and its API is pretty
4543  * specialized to that caller.
4544  *
4545  * Constructs an Expr for the key column (returned in *keyCol) and Consts
4546  * for the lower and upper range limits (returned in *lower_val and
4547  * *upper_val). For MINVALUE/MAXVALUE limits, NULL is returned instead of
4548  * a Const. All of these structures are freshly palloc'd.
4549  *
4550  * *partexprs_item points to the cell containing the next expression in
4551  * the key->partexprs list, or NULL. It may be advanced upon return.
4552  */
4553 static void
4555  PartitionRangeDatum *ldatum,
4556  PartitionRangeDatum *udatum,
4557  ListCell **partexprs_item,
4558  Expr **keyCol,
4559  Const **lower_val, Const **upper_val)
4560 {
4561  /* Get partition key expression for this column */
4562  if (key->partattrs[keynum] != 0)
4563  {
4564  *keyCol = (Expr *) makeVar(1,
4565  key->partattrs[keynum],
4566  key->parttypid[keynum],
4567  key->parttypmod[keynum],
4568  key->parttypcoll[keynum],
4569  0);
4570  }
4571  else
4572  {
4573  if (*partexprs_item == NULL)
4574  elog(ERROR, "wrong number of partition key expressions");
4575  *keyCol = copyObject(lfirst(*partexprs_item));
4576  *partexprs_item = lnext(key->partexprs, *partexprs_item);
4577  }
4578 
4579  /* Get appropriate Const nodes for the bounds */
4580  if (ldatum->kind == PARTITION_RANGE_DATUM_VALUE)
4581  *lower_val = castNode(Const, copyObject(ldatum->value));
4582  else
4583  *lower_val = NULL;
4584 
4585  if (udatum->kind == PARTITION_RANGE_DATUM_VALUE)
4586  *upper_val = castNode(Const, copyObject(udatum->value));
4587  else
4588  *upper_val = NULL;
4589 }
4590 
4591 /*
4592  * get_range_nulltest
4593  *
4594  * A non-default range partition table does not currently allow partition
4595  * keys to be null, so emit an IS NOT NULL expression for each key column.
4596  */
4597 static List *
4599 {
4600  List *result = NIL;
4601  NullTest *nulltest;
4602  ListCell *partexprs_item;
4603  int i;
4604 
4605  partexprs_item = list_head(key->partexprs);
4606  for (i = 0; i < key->partnatts; i++)
4607  {
4608  Expr *keyCol;
4609 
4610  if (key->partattrs[i] != 0)
4611  {
4612  keyCol = (Expr *) makeVar(1,
4613  key->partattrs[i],
4614  key->parttypid[i],
4615  key->parttypmod[i],
4616  key->parttypcoll[i],
4617  0);
4618  }
4619  else
4620  {
4621  if (partexprs_item == NULL)
4622  elog(ERROR, "wrong number of partition key expressions");
4623  keyCol = copyObject(lfirst(partexprs_item));
4624  partexprs_item = lnext(key->partexprs, partexprs_item);
4625  }
4626 
4627  nulltest = makeNode(NullTest);
4628  nulltest->arg = keyCol;
4629  nulltest->nulltesttype = IS_NOT_NULL;
4630  nulltest->argisrow = false;
4631  nulltest->location = -1;
4632  result = lappend(result, nulltest);
4633  }
4634 
4635  return result;
4636 }
4637 
4638 /*
4639  * compute_partition_hash_value
4640  *
4641  * Compute the hash value for given partition key values.
4642  */
4643 uint64
4644 compute_partition_hash_value(int partnatts, FmgrInfo *partsupfunc, Oid *partcollation,
4645  Datum *values, bool *isnull)
4646 {
4647  int i;
4648  uint64 rowHash = 0;
4650 
4651  for (i = 0; i < partnatts; i++)
4652  {
4653  /* Nulls are just ignored */
4654  if (!isnull[i])
4655  {
4656  Datum hash;
4657 
4658  Assert(OidIsValid(partsupfunc[i].fn_oid));
4659 
4660  /*
4661  * Compute hash for each datum value by calling respective
4662  * datatype-specific hash functions of each partition key
4663  * attribute.
4664  */
4665  hash = FunctionCall2Coll(&partsupfunc[i], partcollation[i],
4666  values[i], seed);
4667 
4668  /* Form a single 64-bit hash value */
4669  rowHash = hash_combine64(rowHash, DatumGetUInt64(hash));
4670  }
4671  }
4672 
4673  return rowHash;
4674 }
4675 
4676 /*
4677  * satisfies_hash_partition
4678  *
4679  * This is an SQL-callable function for use in hash partition constraints.
4680  * The first three arguments are the parent table OID, modulus, and remainder.
4681  * The remaining arguments are the value of the partitioning columns (or
4682  * expressions); these are hashed and the results are combined into a single
4683  * hash value by calling hash_combine64.
4684  *
4685  * Returns true if remainder produced when this computed single hash value is
4686  * divided by the given modulus is equal to given remainder, otherwise false.
4687  * NB: it's important that this never return null, as the constraint machinery
4688  * would consider that to be a "pass".
4689  *
4690  * See get_qual_for_hash() for usage.
4691  */
4692 Datum
4694 {
4695  typedef struct ColumnsHashData
4696  {
4697  Oid relid;
4698  int nkeys;
4699  Oid variadic_type;
4700  int16 variadic_typlen;
4701  bool variadic_typbyval;
4702  char variadic_typalign;
4703  Oid partcollid[PARTITION_MAX_KEYS];
4704  FmgrInfo partsupfunc[FLEXIBLE_ARRAY_MEMBER];
4705  } ColumnsHashData;
4706  Oid parentId;
4707  int modulus;
4708  int remainder;
4710  ColumnsHashData *my_extra;
4711  uint64 rowHash = 0;
4712 
4713  /* Return false if the parent OID, modulus, or remainder is NULL. */
4714  if (PG_ARGISNULL(0) || PG_ARGISNULL(1) || PG_ARGISNULL(2))
4715  PG_RETURN_BOOL(false);
4716  parentId = PG_GETARG_OID(0);
4717  modulus = PG_GETARG_INT32(1);
4718  remainder = PG_GETARG_INT32(2);
4719 
4720  /* Sanity check modulus and remainder. */
4721  if (modulus <= 0)
4722  ereport(ERROR,
4723  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
4724  errmsg("modulus for hash partition must be a positive integer")));
4725  if (remainder < 0)
4726  ereport(ERROR,
4727  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
4728  errmsg("remainder for hash partition must be a non-negative integer")));
4729  if (remainder >= modulus)
4730  ereport(ERROR,
4731  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
4732  errmsg("remainder for hash partition must be less than modulus")));
4733 
4734  /*
4735  * Cache hash function information.
4736  */
4737  my_extra = (ColumnsHashData *) fcinfo->flinfo->fn_extra;
4738  if (my_extra == NULL || my_extra->relid != parentId)
4739  {
4740  Relation parent;
4741  PartitionKey key;
4742  int j;
4743 
4744  /* Open parent relation and fetch partition key info */
4745  parent = relation_open(parentId, AccessShareLock);
4746  key = RelationGetPartitionKey(parent);
4747 
4748  /* Reject parent table that is not hash-partitioned. */
4749  if (key == NULL || key->strategy != PARTITION_STRATEGY_HASH)
4750  ereport(ERROR,
4751  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
4752  errmsg("\"%s\" is not a hash partitioned table",
4753  get_rel_name(parentId))));
4754 
4755  if (!get_fn_expr_variadic(fcinfo->flinfo))
4756  {
4757  int nargs = PG_NARGS() - 3;
4758 
4759  /* complain if wrong number of column values */
4760  if (key->partnatts != nargs)
4761  ereport(ERROR,
4762  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
4763  errmsg("number of partitioning columns (%d) does not match number of partition keys provided (%d)",
4764  key->partnatts, nargs)));
4765 
4766  /* allocate space for our cache */
4767  fcinfo->flinfo->fn_extra =
4768  MemoryContextAllocZero(fcinfo->flinfo->fn_mcxt,
4769  offsetof(ColumnsHashData, partsupfunc) +
4770  sizeof(FmgrInfo) * nargs);
4771  my_extra = (ColumnsHashData *) fcinfo->flinfo->fn_extra;
4772  my_extra->relid = parentId;
4773  my_extra->nkeys = key->partnatts;
4774  memcpy(my_extra->partcollid, key->partcollation,
4775  key->partnatts * sizeof(Oid));
4776 
4777  /* check argument types and save fmgr_infos */
4778  for (j = 0; j < key->partnatts; ++j)
4779  {
4780  Oid argtype = get_fn_expr_argtype(fcinfo->flinfo, j + 3);
4781 
4782  if (argtype != key->parttypid[j] && !IsBinaryCoercible(argtype, key->parttypid[j]))
4783  ereport(ERROR,
4784  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
4785  errmsg("column %d of the partition key has type \"%s\", but supplied value is of type \"%s\"",
4786  j + 1, format_type_be(key->parttypid[j]), format_type_be(argtype))));
4787 
4788  fmgr_info_copy(&my_extra->partsupfunc[j],
4789  &key->partsupfunc[j],
4790  fcinfo->flinfo->fn_mcxt);
4791  }
4792  }
4793  else
4794  {
4795  ArrayType *variadic_array = PG_GETARG_ARRAYTYPE_P(3);
4796 
4797  /* allocate space for our cache -- just one FmgrInfo in this case */
4798  fcinfo->flinfo->fn_extra =
4799  MemoryContextAllocZero(fcinfo->flinfo->fn_mcxt,
4800  offsetof(ColumnsHashData, partsupfunc) +
4801  sizeof(FmgrInfo));
4802  my_extra = (ColumnsHashData *) fcinfo->flinfo->fn_extra;
4803  my_extra->relid = parentId;
4804  my_extra->nkeys = key->partnatts;
4805  my_extra->variadic_type = ARR_ELEMTYPE(variadic_array);
4806  get_typlenbyvalalign(my_extra->variadic_type,
4807  &my_extra->variadic_typlen,
4808  &my_extra->variadic_typbyval,
4809  &my_extra->variadic_typalign);
4810  my_extra->partcollid[0] = key->partcollation[0];
4811 
4812  /* check argument types */
4813  for (j = 0; j < key->partnatts; ++j)
4814  if (key->parttypid[j] != my_extra->variadic_type)
4815  ereport(ERROR,
4816  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
4817  errmsg("column %d of the partition key has type \"%s\", but supplied value is of type \"%s\"",
4818  j + 1,
4819  format_type_be(key->parttypid[j]),
4820  format_type_be(my_extra->variadic_type))));
4821 
4822  fmgr_info_copy(&my_extra->partsupfunc[0],
4823  &key->partsupfunc[0],
4824  fcinfo->flinfo->fn_mcxt);
4825  }
4826 
4827  /* Hold lock until commit */
4828  relation_close(parent, NoLock);
4829  }
4830 
4831  if (!OidIsValid(my_extra->variadic_type))
4832  {
4833  int nkeys = my_extra->nkeys;
4834  int i;
4835 
4836  /*
4837  * For a non-variadic call, neither the number of arguments nor their
4838  * types can change across calls, so avoid the expense of rechecking
4839  * here.
4840  */
4841 
4842  for (i = 0; i < nkeys; i++)
4843  {
4844  Datum hash;
4845 
4846  /* keys start from fourth argument of function. */
4847  int argno = i + 3;
4848 
4849  if (PG_ARGISNULL(argno))
4850  continue;
4851 
4852  hash = FunctionCall2Coll(&my_extra->partsupfunc[i],
4853  my_extra->partcollid[i],
4854  PG_GETARG_DATUM(argno),
4855  seed);
4856 
4857  /* Form a single 64-bit hash value */
4858  rowHash = hash_combine64(rowHash, DatumGetUInt64(hash));
4859  }
4860  }
4861  else
4862  {
4863  ArrayType *variadic_array = PG_GETARG_ARRAYTYPE_P(3);
4864  int i;
4865  int nelems;
4866  Datum *datum;
4867  bool *isnull;
4868 
4869  deconstruct_array(variadic_array,
4870  my_extra->variadic_type,
4871  my_extra->variadic_typlen,
4872  my_extra->variadic_typbyval,
4873  my_extra->variadic_typalign,
4874  &datum, &isnull, &nelems);
4875 
4876  /* complain if wrong number of column values */
4877  if (nelems != my_extra->nkeys)
4878  ereport(ERROR,
4879  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
4880  errmsg("number of partitioning columns (%d) does not match number of partition keys provided (%d)",
4881  my_extra->nkeys, nelems)));
4882 
4883  for (i = 0; i < nelems; i++)
4884  {
4885  Datum hash;
4886 
4887  if (isnull[i])
4888  continue;
4889 
4890  hash = FunctionCall2Coll(&my_extra->partsupfunc[0],
4891  my_extra->partcollid[0],
4892  datum[i],
4893  seed);
4894 
4895  /* Form a single 64-bit hash value */
4896  rowHash = hash_combine64(rowHash, DatumGetUInt64(hash));
4897  }
4898  }
4899 
4900  PG_RETURN_BOOL(rowHash % modulus == remainder);
4901 }
Datum constvalue
Definition: primnodes.h:214
TupleTableSlot * table_slot_create(Relation relation, List **reglist)
Definition: tableam.c:91
#define list_make2(x1, x2)
Definition: pg_list.h:208
#define list_make3(x1, x2, x3)
Definition: pg_list.h:210
signed short int16
Definition: c.h:416
bool did_remapping
Definition: partbounds.c:82
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)
Definition: partbounds.c:2341
bool multidims
Definition: primnodes.h:1007
#define NIL
Definition: pg_list.h:65
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)
Definition: partbounds.c:2609
#define PG_GETARG_INT32(n)
Definition: fmgr.h:269
Definition: fmgr.h:56
static PartitionBoundInfo merge_list_bounds(FmgrInfo *partsupfunc, Oid *collations, RelOptInfo *outer_rel, RelOptInfo *inner_rel, JoinType jointype, List **outer_parts, List **inner_parts)
Definition: partbounds.c:1100
PartitionRangeDatumKind ** kind
Definition: partbounds.h:64
#define IsA(nodeptr, _type_)
Definition: nodes.h:578
PartitionRangeDatumKind * kind
Definition: partbounds.c:68
static Datum ExecEvalExprSwitchContext(ExprState *state, ExprContext *econtext, bool *isNull)
Definition: executor.h:307
#define DEBUG1
Definition: elog.h:25
void table_close(Relation relation, LOCKMODE lockmode)
Definition: table.c:167
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:434
MemoryContext fn_mcxt
Definition: fmgr.h:65
static int32 qsort_partition_hbound_cmp(const void *a, const void *b)
Definition: partbounds.c:3657
static PartitionBoundInfo build_merged_partition_bounds(char strategy, List *merged_datums, List *merged_kinds, List *merged_indexes, int null_index, int default_index)
Definition: partbounds.c:2420
Snapshot RegisterSnapshot(Snapshot snapshot)
Definition: snapmgr.c:810
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:310
#define DatumGetInt32(X)
Definition: postgres.h:472
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3028
Oid * partopfamily
Definition: partcache.h:33
Datum lower(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:44
FmgrInfo * partsupfunc
Definition: partcache.h:35
#define castNode(_type_, nodeptr)
Definition: nodes.h:596
static List * get_qual_for_hash(Relation parent, PartitionBoundSpec *spec)
Definition: partbounds.c:3900
PartitionRangeDatumKind
Definition: parsenodes.h:837
void get_typlenbyvalalign(Oid typid, int16 *typlen, bool *typbyval, char *typalign)
Definition: lsyscache.c:2164
static int merge_matching_partitions(PartitionMap *outer_map, PartitionMap *inner_map, int outer_part, int inner_part, int *next_index)
Definition: partbounds.c:1764
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:268
Oid get_array_type(Oid typid)
Definition: lsyscache.c:2669
void fix_opfuncids(Node *node)
Definition: nodeFuncs.c:1636
#define UInt64GetDatum(X)
Definition: postgres.h:648
bool datumIsEqual(Datum value1, Datum value2, bool typByVal, int typLen)
Definition: datum.c:222
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)
Definition: partbounds.c:1964
#define llast(l)
Definition: pg_list.h:194
List * get_qual_from_partbound(Relation rel, Relation parent, PartitionBoundSpec *spec)
Definition: partbounds.c:250
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:743
PartitionRangeDatumKind kind
Definition: parsenodes.h:848
#define AccessShareLock
Definition: lockdefs.h:36
#define FLEXIBLE_ARRAY_MEMBER
Definition: c.h:338
Definition: nodes.h:527
struct cursor * cur
Definition: ecpg.c:28
bool get_fn_expr_variadic(FmgrInfo *flinfo)
Definition: fmgr.c:1938
uint16 StrategyNumber
Definition: stratnum.h:22
int errcode(int sqlerrcode)
Definition: elog.c:691
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)
Definition: partbounds.c:2560
static List * get_range_nulltest(PartitionKey key)
Definition: partbounds.c:4598
void * stringToNode(const char *str)
Definition: read.c:89
static int32 qsort_partition_rbound_cmp(const void *a, const void *b, void *arg)
Definition: partbounds.c:3689
#define PARTITION_MAX_KEYS
Oid array_typeid
Definition: primnodes.h:1003
char * format_type_be(Oid type_oid)
Definition: format_type.c:339
Datum upper(PG_FUNCTION_ARGS)
Definition: oracle_compat.c:75
List * partexprs
Definition: partcache.h:30
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
Definition: fmgr.c:1152
static bool table_scan_getnextslot(TableScanDesc sscan, ScanDirection direction, TupleTableSlot *slot)
Definition: tableam.h:904
PartitionKey RelationGetPartitionKey(Relation rel)
Definition: partcache.c:54
struct PartitionRangeBound PartitionRangeBound
Form_pg_class rd_rel
Definition: rel.h:110
NameData relname
Definition: pg_class.h:38
unsigned int Oid
Definition: postgres_ext.h:31
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)
Definition: partbounds.c:1408
Const * makeConst(Oid consttype, int32 consttypmod, Oid constcollid, int constlen, Datum constvalue, bool constisnull, bool constbyval)
Definition: makefuncs.c:299
static uint64 hash_combine64(uint64 a, uint64 b)
Definition: hashfn.h:80
#define OidIsValid(objectId)
Definition: c.h:706
static void free_partition_map(PartitionMap *map)
Definition: partbounds.c:1734
ExprState * ExecPrepareExpr(Expr *node, EState *estate)
Definition: execExpr.c:491
Expr * make_opclause(Oid opno, Oid opresulttype, bool opretset, Expr *leftop, Expr *rightop, Oid opcollid, Oid inputcollid)
Definition: makefuncs.c:610
signed int int32
Definition: c.h:417
Expr * makeBoolExpr(BoolExprType boolop, List *args, int location)
Definition: makefuncs.c:369
PartitionBoundInfo boundinfo
Definition: partdesc.h:29
JoinType
Definition: nodes.h:694
#define BTLessEqualStrategyNumber
Definition: stratnum.h:30
static int get_range_partition_internal(PartitionBoundInfo bi, int *lb_pos, PartitionRangeBound *lb, PartitionRangeBound *ub)
Definition: partbounds.c:2500
#define Abs(x)
Definition: c.h:988
Definition: type.h:89
#define list_make1(x1)
Definition: pg_list.h:206
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)
Definition: partbounds.c:2673
void FreeExecutorState(EState *estate)
Definition: execUtils.c:185
static Expr * make_partition_op_expr(PartitionKey key, int keynum, uint16 strategy, Expr *arg1, Expr *arg2)
Definition: partbounds.c:3787
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)
Definition: partbounds.c:4554
#define GetPerTupleExprContext(estate)
Definition: executor.h:509
static PartitionRangeBound * make_one_partition_rbound(PartitionKey key, int index, List *datums, bool lower)
Definition: partbounds.c:3307
#define PG_GETARG_ARRAYTYPE_P(n)
Definition: array.h:251
int partition_range_datum_bsearch(FmgrInfo *partsupfunc, Oid *partcollation, PartitionBoundInfo boundinfo, int nvalues, Datum *values, bool *is_equal)
Definition: partbounds.c:3574
void check_new_partition_bound(char *relname, Relation parent, PartitionBoundSpec *spec, ParseState *pstate)
Definition: partbounds.c:2807
unsigned short uint16
Definition: c.h:428
void pfree(void *pointer)
Definition: mcxt.c:1057
MemoryContext es_query_cxt
Definition: execnodes.h:559
Oid * parttypcoll
Definition: partcache.h:46
#define linitial(l)
Definition: pg_list.h:174
#define ObjectIdGetDatum(X)
Definition: postgres.h:507
#define ERROR
Definition: elog.h:43
static TableScanDesc table_beginscan(Relation rel, Snapshot snapshot, int nkeys, struct ScanKeyData *key)
Definition: tableam.h:755
#define lfirst_int(lc)
Definition: pg_list.h:170
static void * list_nth(const List *list, int n)
Definition: pg_list.h:266
Oid get_fn_expr_argtype(FmgrInfo *flinfo, int argnum)
Definition: fmgr.c:1804
Relation relation_open(Oid relationId, LOCKMODE lockmode)
Definition: relation.c:48
static void fix_merged_indexes(PartitionMap *outer_map, PartitionMap *inner_map, int nmerged, List *merged_indexes)
Definition: partbounds.c:2287
Node * makeBoolConst(bool value, bool isnull)
Definition: makefuncs.c:357
struct PartitionMap PartitionMap
Expr * arg
Definition: primnodes.h:1234
#define IS_DUMMY_REL(r)
Definition: pathnodes.h:1423
void check_default_partition_contents(Relation parent, Relation default_rel, PartitionBoundSpec *new_spec)
Definition: partbounds.c:3127
static PartitionBoundInfo create_hash_bounds(PartitionBoundSpec **boundspecs, int nparts, PartitionKey key, int **mapping)
Definition: partbounds.c:358
void fmgr_info_copy(FmgrInfo *dstinfo, FmgrInfo *srcinfo, MemoryContext destcxt)
Definition: fmgr.c:612
int get_hash_partition_greatest_modulus(PartitionBoundInfo bound)
Definition: partbounds.c:3290
char * c
static PartitionBoundInfo create_list_bounds(PartitionBoundSpec **boundspecs, int nparts, PartitionKey key, int **mapping)
Definition: partbounds.c:440
#define NoLock
Definition: lockdefs.h:34
int32 partition_rbound_datum_cmp(FmgrInfo *partsupfunc, Oid *partcollation, Datum *rb_datums, PartitionRangeDatumKind *rb_kind, Datum *tuple_datums, int n_tuple_datums)
Definition: partbounds.c:3435
List * get_proposed_default_constraint(List *new_part_constraints)
Definition: partition.c:346
RelabelType * makeRelabelType(Expr *arg, Oid rtype, int32 rtypmod, Oid rcollid, CoercionForm rformat)
Definition: makefuncs.c:402
#define PG_GETARG_OID(n)
Definition: fmgr.h:275
void ExecDropSingleTupleTableSlot(TupleTableSlot *slot)
Definition: execTuples.c:1224
int errdetail(const char *fmt,...)
Definition: elog.c:1035
int nparts
Definition: pathnodes.h:744
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition: lsyscache.c:164
#define DatumGetBool(X)
Definition: postgres.h:393
static int32 partition_hbound_cmp(int modulus1, int remainder1, int modulus2, int remainder2)
Definition: partbounds.c:3466
static int merge_partition_with_dummy(PartitionMap *map, int index, int *next_index)
Definition: partbounds.c:2269
PartitionDesc RelationGetPartitionDesc(Relation rel)
Definition: partdesc.c:64
bool * merged
Definition: partbounds.c:80
static bool is_dummy_partition(RelOptInfo *rel, int part_index)
Definition: partbounds.c:1745
#define RelationGetRelationName(relation)
Definition: rel.h:491
#define partition_bound_has_default(bi)
Definition: partbounds.h:75
static ListCell * list_head(const List *l)
Definition: pg_list.h:125
int partition_hash_bsearch(PartitionBoundInfo boundinfo, int modulus, int remainder)
Definition: partbounds.c:3617
List * elements
Definition: primnodes.h:1006
static int get_partition_bound_num_indexes(PartitionBoundInfo b)
Definition: partbounds.c:3706
Var * makeVar(Index varno, AttrNumber varattno, Oid vartype, int32 vartypmod, Oid varcollid, Index varlevelsup)
Definition: makefuncs.c:66
Datum datumCopy(Datum value, bool typByVal, int typLen)
Definition: datum.c:131
EState * CreateExecutorState(void)
Definition: execUtils.c:89
List * lappend_int(List *list, int datum)
Definition: list.c:339
char * get_range_partbound_string(List *bound_datums)
Definition: ruleutils.c:11580
void UnregisterSnapshot(Snapshot snapshot)
Definition: snapmgr.c:852
bool IsBinaryCoercible(Oid srctype, Oid targettype)
List * lappend(List *list, void *datum)
Definition: list.c:321
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
Definition: qsort_arg.c:113
#define WARNING
Definition: elog.h:40
HeapTuple SearchSysCache1(int cacheId, Datum key1)
Definition: syscache.c:1115
Oid * partcollation
Definition: partcache.h:38
#define TextDatumGetCString(d)
Definition: builtins.h:87
PartitionBoundInfo partition_bounds_copy(PartitionBoundInfo src, PartitionKey key)
Definition: partbounds.c:917
int location
Definition: primnodes.h:221
List * es_tupleTable
Definition: execnodes.h:561
void * palloc0(Size size)
Definition: mcxt.c:981
int location
Definition: primnodes.h:1008
AttrNumber * partattrs
Definition: partcache.h:28
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
uintptr_t Datum
Definition: postgres.h:367
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1163
#define for_both_cell(cell1, list1, initcell1, cell2, list2, initcell2)
Definition: pg_list.h:456
Expr * make_ands_explicit(List *andclauses)
Definition: makefuncs.c:708
Datum SysCacheGetAttr(int cacheId, HeapTuple tup, AttrNumber attributeNumber, bool *isNull)
Definition: syscache.c:1376
#define list_make1_oid(x1)
Definition: pg_list.h:228
static void cleanup(void)
Definition: bootstrap.c:862
struct PartitionBoundInfoData * boundinfo
Definition: pathnodes.h:747
static Oid get_partition_operator(PartitionKey key, int col, StrategyNumber strategy, bool *need_relabel)
Definition: partbounds.c:3751
#define PARTITION_STRATEGY_HASH
Definition: parsenodes.h:801
NullTestType nulltesttype
Definition: primnodes.h:1235
#define partition_bound_accepts_nulls(bi)
Definition: partbounds.h:74
void * MemoryContextAllocZero(MemoryContext context, Size size)
Definition: mcxt.c:840
static void init_partition_map(RelOptInfo *rel, PartitionMap *map)
Definition: partbounds.c:1713
struct PartitionListValue PartitionListValue
int32 * parttypmod
Definition: partcache.h:42
int partition_list_bsearch(FmgrInfo *partsupfunc, Oid *partcollation, PartitionBoundInfo boundinfo, Datum value, bool *is_equal)
Definition: partbounds.c:3486
uint64 compute_partition_hash_value(int partnatts, FmgrInfo *partsupfunc, Oid *partcollation, Datum *values, bool *isnull)
Definition: partbounds.c:4644
#define InvalidOid
Definition: postgres_ext.h:36
RegProcedure get_opcode(Oid opno)
Definition: lsyscache.c:1202
static struct @143 value
#define ereport(elevel,...)
Definition: elog.h:155
static int32 partition_rbound_cmp(int partnatts, FmgrInfo *partsupfunc, Oid *partcollation, Datum *datums1, PartitionRangeDatumKind *kind1, bool lower1, PartitionRangeBound *b2)
Definition: partbounds.c:3367
static List * get_qual_for_range(Relation parent, PartitionBoundSpec *spec, bool for_default)
Definition: partbounds.c:4192
#define DatumGetUInt64(X)
Definition: postgres.h:634
#define Max(x, y)
Definition: c.h:976
#define makeNode(_type_)
Definition: nodes.h:575
bool partitions_are_ordered(PartitionBoundInfo boundinfo, int nparts)
Definition: partbounds.c:2748
bool * parttypbyval
Definition: partcache.h:44
#define PG_ARGISNULL(n)
Definition: fmgr.h:209
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
void relation_close(Relation relation, LOCKMODE lockmode)
Definition: relation.c:206
#define Assert(condition)
Definition: c.h:800
#define lfirst(lc)
Definition: pg_list.h:169
int16 * parttyplen
Definition: partcache.h:43
static int partition_range_bsearch(int partnatts, FmgrInfo *partsupfunc, Oid *partcollation, PartitionBoundInfo boundinfo, PartitionRangeBound *probe, int32 *cmpval)
Definition: partbounds.c:3532
Oid array_collid
Definition: primnodes.h:1004
struct RelOptInfo ** part_rels
Definition: pathnodes.h:751
int location
Definition: primnodes.h:1237
static int list_length(const List *l)
Definition: pg_list.h:149
int parser_errposition(ParseState *pstate, int location)
Definition: parse_node.c:110
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)
Definition: partbounds.c:2159
TupleTableSlot * ecxt_scantuple
Definition: execnodes.h:225
#define type_is_array(typid)
Definition: lsyscache.h:191
#define PG_NARGS()
Definition: fmgr.h:203
#define HASH_PARTITION_SEED
Definition: partition.h:20
#define PARTITION_STRATEGY_LIST
Definition: parsenodes.h:802
Snapshot GetLatestSnapshot(void)
Definition: snapmgr.c:325
#define GetPerTupleMemoryContext(estate)
Definition: executor.h:514
Oid element_typeid
Definition: primnodes.h:1005
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)
Definition: partbounds.c:1882
void deconstruct_array(ArrayType *array, Oid elmtype, int elmlen, bool elmbyval, char elmalign, Datum **elemsp, bool **nullsp, int *nelemsp)
Definition: arrayfuncs.c:3483
static void table_endscan(TableScanDesc scan)
Definition: tableam.h:863
static Datum values[MAXATTR]
Definition: bootstrap.c:165
#define PARTITION_STRATEGY_RANGE
Definition: parsenodes.h:803
#define AccessExclusiveLock
Definition: lockdefs.h:45
List * find_all_inheritors(Oid parentrelId, LOCKMODE lockmode, List **numparents)
Definition: pg_inherits.c:165
#define Int32GetDatum(X)
Definition: postgres.h:479
static PartitionBoundInfo create_range_bounds(PartitionBoundSpec **boundspecs, int nparts, PartitionKey key, int **mapping)
Definition: partbounds.c:597
void * palloc(Size size)
Definition: mcxt.c:950
int errmsg(const char *fmt,...)
Definition: elog.c:902
int * old_indexes
Definition: partbounds.c:83
bool partition_bounds_equal(int partnatts, int16 *parttyplen, bool *parttypbyval, PartitionBoundInfo b1, PartitionBoundInfo b2)
Definition: partbounds.c:799
Oid * partopcintype
Definition: partcache.h:34
void list_free(List *list)
Definition: list.c:1376
#define elog(elevel,...)
Definition: elog.h:228
int i
void * arg
bool ExecCheck(ExprState *state, ExprContext *econtext)
Definition: execExpr.c:598
#define compare_range_bounds(partnatts, partsupfunc, partcollations, bound1, bound2)
Definition: partbounds.c:88
bool argisrow
Definition: primnodes.h:1236
Datum satisfies_hash_partition(PG_FUNCTION_ARGS)
Definition: partbounds.c:4693
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
ExprState * ExecInitExpr(Expr *node, PlanState *parent)
Definition: execExpr.c:122
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:99
struct PartitionBoundInfoData * PartitionBoundInfo
Definition: partdefs.h:16
#define qsort(a, b, c, d)
Definition: port.h:497
#define copyObject(obj)
Definition: nodes.h:643
PartitionBoundInfo partition_bounds_merge(int partnatts, FmgrInfo *partsupfunc, Oid *partcollation, RelOptInfo *outer_rel, RelOptInfo *inner_rel, JoinType jointype, List **outer_parts, List **inner_parts)
Definition: partbounds.c:1017
#define BTLessStrategyNumber
Definition: stratnum.h:29
Relation table_open(Oid relationId, LOCKMODE lockmode)
Definition: table.c:39
static int32 qsort_partition_list_value_cmp(const void *a, const void *b, void *arg)
Definition: partbounds.c:3672
Definition: pg_list.h:50
static unsigned hash(unsigned *uv, int n)
Definition: rege_dfa.c:541
char * get_rel_name(Oid relid)
Definition: lsyscache.c:1845
int errtable(Relation rel)
Definition: relcache.c:5498
#define ARR_ELEMTYPE(a)
Definition: array.h:280
int * merged_indexes
Definition: partbounds.c:79
List * map_partition_varattnos(List *expr, int fromrel_varno, Relation to_rel, Relation from_rel)
Definition: partition.c:199
#define RelationGetRelid(relation)
Definition: rel.h:457
PartitionBoundInfo partition_bounds_create(PartitionBoundSpec **boundspecs, int nparts, PartitionKey key, int **mapping)
Definition: partbounds.c:305
long val
Definition: informix.c:664
static List * get_qual_for_list(Relation parent, PartitionBoundSpec *spec)
Definition: partbounds.c:3983
bool constisnull
Definition: primnodes.h:215
#define BTEqualStrategyNumber
Definition: stratnum.h:31
#define offsetof(type, field)
Definition: c.h:723
#define BTGreaterEqualStrategyNumber
Definition: stratnum.h:32
#define ResetExprContext(econtext)
Definition: executor.h:503
#define lfirst_oid(lc)
Definition: pg_list.h:171
bool PartConstraintImpliedByRelConstraint(Relation scanrel, List *partConstraint)
Definition: tablecmds.c:16142
FuncExpr * makeFuncExpr(Oid funcid, Oid rettype, List *args, Oid funccollid, Oid inputcollid, CoercionForm fformat)
Definition: makefuncs.c:519
struct PartitionKeyData * PartitionKey
Definition: partdefs.h:18
#define llast_int(l)
Definition: pg_list.h:195
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)
Definition: partbounds.c:2049
static int get_range_partition(RelOptInfo *rel, PartitionBoundInfo bi, int *lb_pos, PartitionRangeBound *lb, PartitionRangeBound *ub)
Definition: partbounds.c:2479
struct PartitionHashBound PartitionHashBound