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