1 /*-------------------------------------------------------------------------
4 * Support for partition pruning during query planning and execution
6 * This module implements partition pruning using the information contained in
7 * a table's partition descriptor, query clauses, and run-time parameters.
9 * During planning, clauses that can be matched to the table's partition key
10 * are turned into a set of "pruning steps", which are then executed to
11 * identify a set of partitions (as indexes in the RelOptInfo->part_rels
12 * array) that satisfy the constraints in the step. Partitions not in the set
13 * are said to have been pruned.
15 * A base pruning step may involve expressions whose values are only known
16 * during execution, such as Params, in which case pruning cannot occur
17 * entirely during planning. In that case, such steps are included alongside
18 * the plan, so that they can be used by the executor for further pruning.
20 * There are two kinds of pruning steps. A "base" pruning step represents
21 * tests on partition key column(s), typically comparisons to expressions.
22 * A "combine" pruning step represents a Boolean connector (AND/OR), and
23 * combines the outputs of some previous steps using the appropriate
26 * See gen_partprune_steps_internal() for more details on step generation.
28 * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
29 * Portions Copyright (c) 1994, Regents of the University of California
32 * src/backend/partitioning/partprune.c
34 *-------------------------------------------------------------------------
38 #include "access/hash.h"
39 #include "access/nbtree.h"
40 #include "catalog/pg_operator.h"
41 #include "catalog/pg_opfamily.h"
42 #include "catalog/pg_type.h"
43 #include "executor/executor.h"
44 #include "miscadmin.h"
45 #include "nodes/makefuncs.h"
46 #include "nodes/nodeFuncs.h"
47 #include "optimizer/appendinfo.h"
48 #include "optimizer/clauses.h"
49 #include "optimizer/pathnode.h"
50 #include "optimizer/planner.h"
51 #include "optimizer/predtest.h"
52 #include "optimizer/prep.h"
53 #include "optimizer/var.h"
54 #include "partitioning/partprune.h"
55 #include "partitioning/partbounds.h"
56 #include "rewrite/rewriteManip.h"
57 #include "utils/lsyscache.h"
61 * Information about a clause matched with a partition key.
63 typedef struct PartClauseInfo
65 int keyno; /* Partition key number (0 to partnatts - 1) */
66 Oid opno; /* operator used to compare partkey to expr */
67 bool op_is_ne; /* is clause's original operator <> ? */
68 Expr *expr; /* expr the partition key is compared to */
69 Oid cmpfn; /* Oid of function to compare 'expr' to the
71 int op_strategy; /* btree strategy identifying the operator */
75 * PartClauseMatchStatus
76 * Describes the result of match_clause_to_partition_key()
78 typedef enum PartClauseMatchStatus
81 PARTCLAUSE_MATCH_CLAUSE,
82 PARTCLAUSE_MATCH_NULLNESS,
83 PARTCLAUSE_MATCH_STEPS,
84 PARTCLAUSE_MATCH_CONTRADICT,
85 PARTCLAUSE_UNSUPPORTED
86 } PartClauseMatchStatus;
89 * GeneratePruningStepsContext
90 * Information about the current state of generation of "pruning steps"
91 * for a given set of clauses
93 * gen_partprune_steps() initializes an instance of this struct, which is used
94 * throughout the step generation process.
96 typedef struct GeneratePruningStepsContext
100 } GeneratePruningStepsContext;
102 /* The result of performing one PartitionPruneStep */
103 typedef struct PruneStepResult
106 * The offsets of bounds (in a table's boundinfo) whose partition is
107 * selected by the pruning step.
109 Bitmapset *bound_offsets;
111 bool scan_default; /* Scan the default partition? */
112 bool scan_null; /* Scan the partition for NULL values? */
116 static List *make_partitionedrel_pruneinfo(PlannerInfo *root,
117 RelOptInfo *parentrel,
118 int *relid_subplan_map,
119 List *partitioned_rels, List *prunequal,
120 Bitmapset **matchedsubplans);
121 static List *gen_partprune_steps(RelOptInfo *rel, List *clauses,
122 bool *contradictory);
123 static List *gen_partprune_steps_internal(GeneratePruningStepsContext *context,
124 RelOptInfo *rel, List *clauses,
125 bool *contradictory);
126 static PartitionPruneStep *gen_prune_step_op(GeneratePruningStepsContext *context,
127 StrategyNumber opstrategy, bool op_is_ne,
128 List *exprs, List *cmpfns, Bitmapset *nullkeys);
129 static PartitionPruneStep *gen_prune_step_combine(GeneratePruningStepsContext *context,
130 List *source_stepids,
131 PartitionPruneCombineOp combineOp);
132 static PartitionPruneStep *gen_prune_steps_from_opexps(PartitionScheme part_scheme,
133 GeneratePruningStepsContext *context,
134 List **keyclauses, Bitmapset *nullkeys);
135 static PartClauseMatchStatus match_clause_to_partition_key(RelOptInfo *rel,
136 GeneratePruningStepsContext *context,
137 Expr *clause, Expr *partkey, int partkeyidx,
138 bool *clause_is_not_null,
139 PartClauseInfo **pc, List **clause_steps);
140 static List *get_steps_using_prefix(GeneratePruningStepsContext *context,
141 StrategyNumber step_opstrategy,
146 Bitmapset *step_nullkeys,
148 static List *get_steps_using_prefix_recurse(GeneratePruningStepsContext *context,
149 StrategyNumber step_opstrategy,
154 Bitmapset *step_nullkeys,
158 static PruneStepResult *get_matching_hash_bounds(PartitionPruneContext *context,
159 StrategyNumber opstrategy, Datum *values, int nvalues,
160 FmgrInfo *partsupfunc, Bitmapset *nullkeys);
161 static PruneStepResult *get_matching_list_bounds(PartitionPruneContext *context,
162 StrategyNumber opstrategy, Datum value, int nvalues,
163 FmgrInfo *partsupfunc, Bitmapset *nullkeys);
164 static PruneStepResult *get_matching_range_bounds(PartitionPruneContext *context,
165 StrategyNumber opstrategy, Datum *values, int nvalues,
166 FmgrInfo *partsupfunc, Bitmapset *nullkeys);
167 static Bitmapset *pull_exec_paramids(Expr *expr);
168 static bool pull_exec_paramids_walker(Node *node, Bitmapset **context);
169 static bool analyze_partkey_exprs(PartitionedRelPruneInfo *pinfo, List *steps,
171 static PruneStepResult *perform_pruning_base_step(PartitionPruneContext *context,
172 PartitionPruneStepOp *opstep);
173 static PruneStepResult *perform_pruning_combine_step(PartitionPruneContext *context,
174 PartitionPruneStepCombine *cstep,
175 PruneStepResult **step_results);
176 static bool match_boolean_partition_clause(Oid partopfamily, Expr *clause,
177 Expr *partkey, Expr **outconst);
178 static bool partkey_datum_from_expr(PartitionPruneContext *context,
179 Expr *expr, int stateidx,
180 Datum *value, bool *isnull);
184 * make_partition_pruneinfo
185 * Builds a PartitionPruneInfo which can be used in the executor to allow
186 * additional partition pruning to take place. Returns NULL when
187 * partition pruning would be useless.
189 * 'parentrel' is the RelOptInfo for an appendrel, and 'subpaths' is the list
190 * of scan paths for its child rels.
192 * 'partitioned_rels' is a List containing Lists of relids of partitioned
193 * tables (a/k/a non-leaf partitions) that are parents of some of the child
194 * rels. Here we attempt to populate the PartitionPruneInfo by adding a
195 * 'prune_infos' item for each sublist in the 'partitioned_rels' list.
196 * However, some of the sets of partitioned relations may not require any
197 * run-time pruning. In these cases we'll simply not include a 'prune_infos'
198 * item for that set and instead we'll add all the subplans which belong to
199 * that set into the PartitionPruneInfo's 'other_subplans' field. Callers
200 * will likely never want to prune subplans which are mentioned in this field.
202 * 'prunequal' is a list of potential pruning quals.
205 make_partition_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
206 List *subpaths, List *partitioned_rels,
209 PartitionPruneInfo *pruneinfo;
210 Bitmapset *allmatchedsubplans = NULL;
211 int *relid_subplan_map;
217 * Construct a temporary array to map from planner relids to subplan
218 * indexes. For convenience, we use 1-based indexes here, so that zero
219 * can represent an un-filled array entry.
221 relid_subplan_map = palloc0(sizeof(int) * root->simple_rel_array_size);
224 * relid_subplan_map maps relid of a leaf partition to the index in
225 * 'subpaths' of the scan plan for that partition.
228 foreach(lc, subpaths)
230 Path *path = (Path *) lfirst(lc);
231 RelOptInfo *pathrel = path->parent;
233 Assert(IS_SIMPLE_REL(pathrel));
234 Assert(pathrel->relid < root->simple_rel_array_size);
235 /* No duplicates please */
236 Assert(relid_subplan_map[pathrel->relid] == 0);
238 relid_subplan_map[pathrel->relid] = i++;
241 /* We now build a PartitionedRelPruneInfo for each partitioned rel. */
243 foreach(lc, partitioned_rels)
245 List *rels = (List *) lfirst(lc);
247 Bitmapset *matchedsubplans = NULL;
249 pinfolist = make_partitionedrel_pruneinfo(root, parentrel,
254 /* When pruning is possible, record the matched subplans */
255 if (pinfolist != NIL)
257 prunerelinfos = lappend(prunerelinfos, pinfolist);
258 allmatchedsubplans = bms_join(matchedsubplans,
263 pfree(relid_subplan_map);
266 * If none of the partition hierarchies had any useful run-time pruning
267 * quals, then we can just not bother with run-time pruning.
269 if (prunerelinfos == NIL)
272 /* Else build the result data structure */
273 pruneinfo = makeNode(PartitionPruneInfo);
274 pruneinfo->prune_infos = prunerelinfos;
277 * Some subplans may not belong to any of the listed partitioned rels.
278 * This can happen for UNION ALL queries which include a non-partitioned
279 * table, or when some of the hierarchies aren't run-time prunable. Build
280 * a bitmapset of the indexes of all such subplans, so that the executor
281 * can identify which subplans should never be pruned.
283 if (bms_num_members(allmatchedsubplans) < list_length(subpaths))
285 Bitmapset *other_subplans;
287 /* Create the complement of allmatchedsubplans */
288 other_subplans = bms_add_range(NULL, 0, list_length(subpaths) - 1);
289 other_subplans = bms_del_members(other_subplans, allmatchedsubplans);
291 pruneinfo->other_subplans = other_subplans;
294 pruneinfo->other_subplans = NULL;
300 * make_partitionedrel_pruneinfo
301 * Build a List of PartitionedRelPruneInfos, one for each partitioned
302 * rel. These can be used in the executor to allow additional partition
303 * pruning to take place.
305 * Here we generate partition pruning steps for 'prunequal' and also build a
306 * data structure which allows mapping of partition indexes into 'subpaths'
309 * If no non-Const expressions are being compared to the partition key in any
310 * of the 'partitioned_rels', then we return NIL to indicate no run-time
311 * pruning should be performed. Run-time pruning would be useless since the
312 * pruning done during planning will have pruned everything that can be.
314 * On non-NIL return, 'matchedsubplans' is set to the subplan indexes which
315 * were matched to this partition hierarchy.
318 make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
319 int *relid_subplan_map,
320 List *partitioned_rels, List *prunequal,
321 Bitmapset **matchedsubplans)
323 RelOptInfo *targetpart = NULL;
324 List *pinfolist = NIL;
325 bool doruntimeprune = false;
326 int *relid_subpart_map;
327 Bitmapset *subplansfound = NULL;
332 * Construct a temporary array to map from planner relids to index of the
333 * partitioned_rel. For convenience, we use 1-based indexes here, so that
334 * zero can represent an un-filled array entry.
336 relid_subpart_map = palloc0(sizeof(int) * root->simple_rel_array_size);
339 * relid_subpart_map maps relid of a non-leaf partition to the index in
340 * 'partitioned_rels' of that rel (which will also be the index in the
341 * returned PartitionedRelPruneInfo list of the info for that partition).
344 foreach(lc, partitioned_rels)
346 Index rti = lfirst_int(lc);
348 Assert(rti < root->simple_rel_array_size);
349 /* No duplicates please */
350 Assert(relid_subpart_map[rti] == 0);
352 relid_subpart_map[rti] = i++;
355 /* We now build a PartitionedRelPruneInfo for each partitioned rel */
356 foreach(lc, partitioned_rels)
358 Index rti = lfirst_int(lc);
359 RelOptInfo *subpart = find_base_rel(root, rti);
360 PartitionedRelPruneInfo *pinfo;
361 Bitmapset *present_parts;
362 int nparts = subpart->nparts;
363 int partnatts = subpart->part_scheme->partnatts;
371 * The first item in the list is the target partitioned relation.
375 targetpart = subpart;
378 * The prunequal is presented to us as a qual for 'parentrel'.
379 * Frequently this rel is the same as targetpart, so we can skip
380 * an adjust_appendrel_attrs step. But it might not be, and then
381 * we have to translate. We update the prunequal parameter here,
382 * because in later iterations of the loop for child partitions,
383 * we want to translate from parent to child variables.
385 if (!bms_equal(parentrel->relids, subpart->relids))
388 AppendRelInfo **appinfos = find_appinfos_by_relids(root,
392 prunequal = (List *) adjust_appendrel_attrs(root, (Node *)
400 partprunequal = prunequal;
405 * For sub-partitioned tables the columns may not be in the same
406 * order as the parent, so we must translate the prunequal to make
407 * it compatible with this relation.
409 partprunequal = (List *)
410 adjust_appendrel_attrs_multilevel(root,
416 pruning_steps = gen_partprune_steps(subpart, partprunequal,
422 * This shouldn't happen as the planner should have detected this
423 * earlier. However, we do use additional quals from parameterized
424 * paths here. These do only compare Params to the partition key,
425 * so this shouldn't cause the discovery of any new qual
426 * contradictions that were not previously discovered as the Param
427 * values are unknown during planning. Anyway, we'd better do
428 * something sane here, so let's just disable run-time pruning.
434 * Construct the subplan and subpart maps for this partitioning level.
435 * Here we convert to zero-based indexes, with -1 for empty entries.
436 * Also construct a Bitmapset of all partitions that are present (that
437 * is, not pruned already).
439 subplan_map = (int *) palloc(nparts * sizeof(int));
440 subpart_map = (int *) palloc(nparts * sizeof(int));
441 present_parts = NULL;
443 for (i = 0; i < nparts; i++)
445 RelOptInfo *partrel = subpart->part_rels[i];
446 int subplanidx = relid_subplan_map[partrel->relid] - 1;
447 int subpartidx = relid_subpart_map[partrel->relid] - 1;
449 subplan_map[i] = subplanidx;
450 subpart_map[i] = subpartidx;
453 present_parts = bms_add_member(present_parts, i);
455 /* Record finding this subplan */
456 subplansfound = bms_add_member(subplansfound, subplanidx);
458 else if (subpartidx >= 0)
459 present_parts = bms_add_member(present_parts, i);
462 pinfo = makeNode(PartitionedRelPruneInfo);
463 pinfo->rtindex = rti;
464 pinfo->pruning_steps = pruning_steps;
465 pinfo->present_parts = present_parts;
466 pinfo->nparts = nparts;
467 pinfo->subplan_map = subplan_map;
468 pinfo->subpart_map = subpart_map;
470 /* Determine which pruning types should be enabled at this level */
471 doruntimeprune |= analyze_partkey_exprs(pinfo, pruning_steps,
474 pinfolist = lappend(pinfolist, pinfo);
477 pfree(relid_subpart_map);
481 /* No run-time pruning required. */
485 *matchedsubplans = subplansfound;
491 * gen_partprune_steps
492 * Process 'clauses' (a rel's baserestrictinfo list of clauses) and return
493 * a list of "partition pruning steps"
495 * If the clauses in the input list are contradictory or there is a
496 * pseudo-constant "false", *contradictory is set to true upon return.
499 gen_partprune_steps(RelOptInfo *rel, List *clauses, bool *contradictory)
501 GeneratePruningStepsContext context;
503 context.next_step_id = 0;
506 /* The clauses list may be modified below, so better make a copy. */
507 clauses = list_copy(clauses);
510 * For sub-partitioned tables there's a corner case where if the
511 * sub-partitioned table shares any partition keys with its parent, then
512 * it's possible that the partitioning hierarchy allows the parent
513 * partition to only contain a narrower range of values than the
514 * sub-partitioned table does. In this case it is possible that we'd
515 * include partitions that could not possibly have any tuples matching
516 * 'clauses'. The possibility of such a partition arrangement is perhaps
517 * unlikely for non-default partitions, but it may be more likely in the
518 * case of default partitions, so we'll add the parent partition table's
519 * partition qual to the clause list in this case only. This may result
520 * in the default partition being eliminated.
522 if (partition_bound_has_default(rel->boundinfo) &&
523 rel->partition_qual != NIL)
525 List *partqual = rel->partition_qual;
527 partqual = (List *) expression_planner((Expr *) partqual);
529 /* Fix Vars to have the desired varno */
531 ChangeVarNodes((Node *) partqual, 1, rel->relid, 0);
533 clauses = list_concat(clauses, partqual);
536 /* Down into the rabbit-hole. */
537 gen_partprune_steps_internal(&context, rel, clauses, contradictory);
539 return context.steps;
543 * prune_append_rel_partitions
544 * Returns RT indexes of the minimum set of child partitions which must
545 * be scanned to satisfy rel's baserestrictinfo quals.
547 * Callers must ensure that 'rel' is a partitioned table.
550 prune_append_rel_partitions(RelOptInfo *rel)
553 List *clauses = rel->baserestrictinfo;
556 PartitionPruneContext context;
557 Bitmapset *partindexes;
560 Assert(clauses != NIL);
561 Assert(rel->part_scheme != NULL);
563 /* If there are no partitions, return the empty set */
564 if (rel->nparts == 0)
568 * Process clauses. If the clauses are found to be contradictory, we can
569 * return the empty set.
571 pruning_steps = gen_partprune_steps(rel, clauses, &contradictory);
575 /* Set up PartitionPruneContext */
576 context.strategy = rel->part_scheme->strategy;
577 context.partnatts = rel->part_scheme->partnatts;
578 context.nparts = rel->nparts;
579 context.boundinfo = rel->boundinfo;
580 context.partcollation = rel->part_scheme->partcollation;
581 context.partsupfunc = rel->part_scheme->partsupfunc;
582 context.stepcmpfuncs = (FmgrInfo *) palloc0(sizeof(FmgrInfo) *
584 list_length(pruning_steps));
585 context.ppccontext = CurrentMemoryContext;
587 /* These are not valid when being called from the planner */
588 context.planstate = NULL;
589 context.exprstates = NULL;
590 context.exprhasexecparam = NULL;
591 context.evalexecparams = false;
593 /* Actual pruning happens here. */
594 partindexes = get_matching_partitions(&context, pruning_steps);
596 /* Add selected partitions' RT indexes to result. */
599 while ((i = bms_next_member(partindexes, i)) >= 0)
600 result = bms_add_member(result, rel->part_rels[i]->relid);
606 * get_matching_partitions
607 * Determine partitions that survive partition pruning
609 * Returns a Bitmapset of the RelOptInfo->part_rels indexes of the surviving
613 get_matching_partitions(PartitionPruneContext *context, List *pruning_steps)
616 int num_steps = list_length(pruning_steps),
618 PruneStepResult **results,
622 /* If there are no pruning steps then all partitions match. */
625 Assert(context->nparts > 0);
626 return bms_add_range(NULL, 0, context->nparts - 1);
630 * Allocate space for individual pruning steps to store its result. Each
631 * slot will hold a PruneStepResult after performing a given pruning step.
632 * Later steps may use the result of one or more earlier steps. The
633 * result of applying all pruning steps is the value contained in the slot
634 * of the last pruning step.
636 results = (PruneStepResult **)
637 palloc0(num_steps * sizeof(PruneStepResult *));
638 foreach(lc, pruning_steps)
640 PartitionPruneStep *step = lfirst(lc);
642 switch (nodeTag(step))
644 case T_PartitionPruneStepOp:
645 results[step->step_id] =
646 perform_pruning_base_step(context,
647 (PartitionPruneStepOp *) step);
650 case T_PartitionPruneStepCombine:
651 results[step->step_id] =
652 perform_pruning_combine_step(context,
653 (PartitionPruneStepCombine *) step,
658 elog(ERROR, "invalid pruning step type: %d",
659 (int) nodeTag(step));
664 * At this point we know the offsets of all the datums whose corresponding
665 * partitions need to be in the result, including special null-accepting
666 * and default partitions. Collect the actual partition indexes now.
668 final_result = results[num_steps - 1];
669 Assert(final_result != NULL);
672 while ((i = bms_next_member(final_result->bound_offsets, i)) >= 0)
674 int partindex = context->boundinfo->indexes[i];
677 * In range and hash partitioning cases, some slots may contain -1,
678 * indicating that no partition has been defined to accept a given
679 * range of data or for a given remainder, respectively. The default
680 * partition, if any, in case of range partitioning, will be added to
681 * the result, because the specified range still satisfies the query's
685 result = bms_add_member(result, partindex);
688 /* Add the null and/or default partition if needed and if present. */
689 if (final_result->scan_null)
691 Assert(context->strategy == PARTITION_STRATEGY_LIST);
692 Assert(partition_bound_accepts_nulls(context->boundinfo));
693 result = bms_add_member(result, context->boundinfo->null_index);
695 if (final_result->scan_default)
697 Assert(context->strategy == PARTITION_STRATEGY_LIST ||
698 context->strategy == PARTITION_STRATEGY_RANGE);
699 Assert(partition_bound_has_default(context->boundinfo));
700 result = bms_add_member(result, context->boundinfo->default_index);
707 * gen_partprune_steps_internal
708 * Processes 'clauses' to generate partition pruning steps.
710 * From OpExpr clauses that are mutually AND'd, we find combinations of those
711 * that match to the partition key columns and for every such combination,
712 * we emit a PartitionPruneStepOp containing a vector of expressions whose
713 * values are used as a look up key to search partitions by comparing the
714 * values with partition bounds. Relevant details of the operator and a
715 * vector of (possibly cross-type) comparison functions is also included with
718 * For BoolExpr clauses, we recursively generate steps for each argument, and
719 * return a PartitionPruneStepCombine of their results.
721 * The return value is a list of the steps generated, which are also added to
722 * the context's steps list. Each step is assigned a step identifier, unique
723 * even across recursive calls.
725 * If we find clauses that are mutually contradictory, or a pseudoconstant
726 * clause that contains false, we set *contradictory to true and return NIL
727 * (that is, no pruning steps). Caller should consider all partitions as
728 * pruned in that case. Otherwise, *contradictory is set to false.
730 * Note: the 'clauses' List may be modified inside this function. Callers may
731 * like to make a copy of it before passing them to this function.
734 gen_partprune_steps_internal(GeneratePruningStepsContext *context,
735 RelOptInfo *rel, List *clauses,
738 PartitionScheme part_scheme = rel->part_scheme;
739 List *keyclauses[PARTITION_MAX_KEYS];
740 Bitmapset *nullkeys = NULL,
742 bool generate_opsteps = false;
746 *contradictory = false;
748 memset(keyclauses, 0, sizeof(keyclauses));
751 Expr *clause = (Expr *) lfirst(lc);
754 /* Look through RestrictInfo, if any */
755 if (IsA(clause, RestrictInfo))
756 clause = ((RestrictInfo *) clause)->clause;
758 /* Constant-false-or-null is contradictory */
759 if (IsA(clause, Const) &&
760 (((Const *) clause)->constisnull ||
761 !DatumGetBool(((Const *) clause)->constvalue)))
763 *contradictory = true;
767 /* Get the BoolExpr's out of the way. */
768 if (IsA(clause, BoolExpr))
771 * Generate steps for arguments.
773 * While steps generated for the arguments themselves will be
774 * added to context->steps during recursion and will be evaluated
775 * independently, collect their step IDs to be stored in the
776 * combine step we'll be creating.
778 if (or_clause((Node *) clause))
780 List *arg_stepids = NIL;
781 bool all_args_contradictory = true;
785 * Get pruning step for each arg. If we get contradictory for
786 * all args, it means the OR expression is false as a whole.
788 foreach(lc1, ((BoolExpr *) clause)->args)
790 Expr *arg = lfirst(lc1);
791 bool arg_contradictory;
795 gen_partprune_steps_internal(context, rel,
798 if (!arg_contradictory)
799 all_args_contradictory = false;
803 PartitionPruneStep *step;
805 Assert(list_length(argsteps) == 1);
806 step = (PartitionPruneStep *) linitial(argsteps);
807 arg_stepids = lappend_int(arg_stepids, step->step_id);
812 * No steps either means that arg_contradictory is
813 * true or the arg didn't contain a clause matching
814 * this partition key.
816 * In case of the latter, we cannot prune using such
817 * an arg. To indicate that to the pruning code, we
818 * must construct a dummy PartitionPruneStepCombine
819 * whose source_stepids is set to an empty List.
820 * However, if we can prove using constraint exclusion
821 * that the clause refutes the table's partition
822 * constraint (if it's sub-partitioned), we need not
823 * bother with that. That is, we effectively ignore
826 List *partconstr = rel->partition_qual;
827 PartitionPruneStep *orstep;
829 /* Just ignore this argument. */
830 if (arg_contradictory)
835 partconstr = (List *)
836 expression_planner((Expr *) partconstr);
838 ChangeVarNodes((Node *) partconstr, 1,
840 if (predicate_refuted_by(partconstr,
846 orstep = gen_prune_step_combine(context, NIL,
847 PARTPRUNE_COMBINE_UNION);
848 arg_stepids = lappend_int(arg_stepids, orstep->step_id);
852 *contradictory = all_args_contradictory;
854 /* Check if any contradicting clauses were found */
858 if (arg_stepids != NIL)
860 PartitionPruneStep *step;
862 step = gen_prune_step_combine(context, arg_stepids,
863 PARTPRUNE_COMBINE_UNION);
864 result = lappend(result, step);
868 else if (and_clause((Node *) clause))
870 List *args = ((BoolExpr *) clause)->args;
876 * args may itself contain clauses of arbitrary type, so just
877 * recurse and later combine the component partitions sets
878 * using a combine step.
880 argsteps = gen_partprune_steps_internal(context, rel, args,
885 foreach(lc1, argsteps)
887 PartitionPruneStep *step = lfirst(lc1);
889 arg_stepids = lappend_int(arg_stepids, step->step_id);
892 if (arg_stepids != NIL)
894 PartitionPruneStep *step;
896 step = gen_prune_step_combine(context, arg_stepids,
897 PARTPRUNE_COMBINE_INTERSECT);
898 result = lappend(result, step);
904 * Fall-through for a NOT clause, which if it's a Boolean clause,
905 * will be handled in match_clause_to_partition_key(). We
906 * currently don't perform any pruning for more complex NOT
912 * Must be a clause for which we can check if one of its args matches
915 for (i = 0; i < part_scheme->partnatts; i++)
917 Expr *partkey = linitial(rel->partexprs[i]);
918 bool clause_is_not_null = false;
919 PartClauseInfo *pc = NULL;
920 List *clause_steps = NIL;
922 switch (match_clause_to_partition_key(rel, context,
927 case PARTCLAUSE_MATCH_CLAUSE:
931 * Since we only allow strict operators, check for any
932 * contradicting IS NULL.
934 if (bms_is_member(i, nullkeys))
936 *contradictory = true;
939 generate_opsteps = true;
940 keyclauses[i] = lappend(keyclauses[i], pc);
943 case PARTCLAUSE_MATCH_NULLNESS:
944 if (!clause_is_not_null)
946 /* check for conflicting IS NOT NULL */
947 if (bms_is_member(i, notnullkeys))
949 *contradictory = true;
952 nullkeys = bms_add_member(nullkeys, i);
956 /* check for conflicting IS NULL */
957 if (bms_is_member(i, nullkeys))
959 *contradictory = true;
962 notnullkeys = bms_add_member(notnullkeys, i);
966 case PARTCLAUSE_MATCH_STEPS:
967 Assert(clause_steps != NIL);
968 result = list_concat(result, clause_steps);
971 case PARTCLAUSE_MATCH_CONTRADICT:
972 /* We've nothing more to do if a contradiction was found. */
973 *contradictory = true;
976 case PARTCLAUSE_NOMATCH:
979 * Clause didn't match this key, but it might match the
984 case PARTCLAUSE_UNSUPPORTED:
985 /* This clause cannot be used for pruning. */
989 /* done; go check the next clause. */
995 * Now generate some (more) pruning steps. We have three strategies:
997 * 1) Generate pruning steps based on IS NULL clauses:
998 * a) For list partitioning, null partition keys can only be found in
999 * the designated null-accepting partition, so if there are IS NULL
1000 * clauses containing partition keys we should generate a pruning
1001 * step that gets rid of all partitions but that one. We can
1002 * disregard any OpExpr we may have found.
1003 * b) For range partitioning, only the default partition can contain
1004 * NULL values, so the same rationale applies.
1005 * c) For hash partitioning, we only apply this strategy if we have
1006 * IS NULL clauses for all the keys. Strategy 2 below will take
1007 * care of the case where some keys have OpExprs and others have
1010 * 2) If not, generate steps based on OpExprs we have (if any).
1012 * 3) If this doesn't work either, we may be able to generate steps to
1013 * prune just the null-accepting partition (if one exists), if we have
1014 * IS NOT NULL clauses for all partition keys.
1016 if (!bms_is_empty(nullkeys) &&
1017 (part_scheme->strategy == PARTITION_STRATEGY_LIST ||
1018 part_scheme->strategy == PARTITION_STRATEGY_RANGE ||
1019 (part_scheme->strategy == PARTITION_STRATEGY_HASH &&
1020 bms_num_members(nullkeys) == part_scheme->partnatts)))
1022 PartitionPruneStep *step;
1025 step = gen_prune_step_op(context, InvalidStrategy,
1026 false, NIL, NIL, nullkeys);
1027 result = lappend(result, step);
1029 else if (generate_opsteps)
1031 PartitionPruneStep *step;
1034 step = gen_prune_steps_from_opexps(part_scheme, context,
1035 keyclauses, nullkeys);
1037 result = lappend(result, step);
1039 else if (bms_num_members(notnullkeys) == part_scheme->partnatts)
1041 PartitionPruneStep *step;
1044 step = gen_prune_step_op(context, InvalidStrategy,
1045 false, NIL, NIL, NULL);
1046 result = lappend(result, step);
1050 * Finally, results from all entries appearing in result should be
1051 * combined using an INTERSECT combine step, if more than one.
1053 if (list_length(result) > 1)
1055 List *step_ids = NIL;
1059 PartitionPruneStep *step = lfirst(lc);
1061 step_ids = lappend_int(step_ids, step->step_id);
1064 if (step_ids != NIL)
1066 PartitionPruneStep *step;
1068 step = gen_prune_step_combine(context, step_ids,
1069 PARTPRUNE_COMBINE_INTERSECT);
1070 result = lappend(result, step);
1079 * Generate a pruning step for a specific operator
1081 * The step is assigned a unique step identifier and added to context's 'steps'
1084 static PartitionPruneStep *
1085 gen_prune_step_op(GeneratePruningStepsContext *context,
1086 StrategyNumber opstrategy, bool op_is_ne,
1087 List *exprs, List *cmpfns,
1088 Bitmapset *nullkeys)
1090 PartitionPruneStepOp *opstep = makeNode(PartitionPruneStepOp);
1092 opstep->step.step_id = context->next_step_id++;
1095 * For clauses that contain an <> operator, set opstrategy to
1096 * InvalidStrategy to signal get_matching_list_bounds to do the right
1099 opstep->opstrategy = op_is_ne ? InvalidStrategy : opstrategy;
1100 Assert(list_length(exprs) == list_length(cmpfns));
1101 opstep->exprs = exprs;
1102 opstep->cmpfns = cmpfns;
1103 opstep->nullkeys = nullkeys;
1105 context->steps = lappend(context->steps, opstep);
1107 return (PartitionPruneStep *) opstep;
1111 * gen_prune_step_combine
1112 * Generate a pruning step for a combination of several other steps
1114 * The step is assigned a unique step identifier and added to context's
1117 static PartitionPruneStep *
1118 gen_prune_step_combine(GeneratePruningStepsContext *context,
1119 List *source_stepids,
1120 PartitionPruneCombineOp combineOp)
1122 PartitionPruneStepCombine *cstep = makeNode(PartitionPruneStepCombine);
1124 cstep->step.step_id = context->next_step_id++;
1125 cstep->combineOp = combineOp;
1126 cstep->source_stepids = source_stepids;
1128 context->steps = lappend(context->steps, cstep);
1130 return (PartitionPruneStep *) cstep;
1134 * gen_prune_steps_from_opexps
1135 * Generate pruning steps based on clauses for partition keys
1137 * 'keyclauses' contains one list of clauses per partition key. We check here
1138 * if we have found clauses for a valid subset of the partition key. In some
1139 * cases, (depending on the type of partitioning being used) if we didn't
1140 * find clauses for a given key, we discard clauses that may have been
1141 * found for any subsequent keys; see specific notes below.
1143 static PartitionPruneStep *
1144 gen_prune_steps_from_opexps(PartitionScheme part_scheme,
1145 GeneratePruningStepsContext *context,
1146 List **keyclauses, Bitmapset *nullkeys)
1149 List *opsteps = NIL;
1150 List *btree_clauses[BTMaxStrategyNumber + 1],
1151 *hash_clauses[HTMaxStrategyNumber + 1];
1152 bool need_next_less,
1157 memset(btree_clauses, 0, sizeof(btree_clauses));
1158 memset(hash_clauses, 0, sizeof(hash_clauses));
1159 for (i = 0; i < part_scheme->partnatts; i++)
1161 List *clauselist = keyclauses[i];
1162 bool consider_next_key = true;
1165 * To be useful for pruning, we must have clauses for a prefix of
1166 * partition keys in the case of range partitioning. So, ignore
1167 * clauses for keys after this one.
1169 if (part_scheme->strategy == PARTITION_STRATEGY_RANGE &&
1174 * For hash partitioning, if a column doesn't have the necessary
1175 * equality clause, there should be an IS NULL clause, otherwise
1176 * pruning is not possible.
1178 if (part_scheme->strategy == PARTITION_STRATEGY_HASH &&
1179 clauselist == NIL && !bms_is_member(i, nullkeys))
1182 need_next_eq = need_next_less = need_next_greater = true;
1183 foreach(lc, clauselist)
1185 PartClauseInfo *pc = (PartClauseInfo *) lfirst(lc);
1189 /* Look up the operator's btree/hash strategy number. */
1190 if (pc->op_strategy == InvalidStrategy)
1191 get_op_opfamily_properties(pc->opno,
1192 part_scheme->partopfamily[i],
1198 switch (part_scheme->strategy)
1200 case PARTITION_STRATEGY_LIST:
1201 case PARTITION_STRATEGY_RANGE:
1203 PartClauseInfo *last = NULL;
1204 bool inclusive = false;
1207 * Add this clause to the list of clauses to be used
1208 * for pruning if this is the first such key for this
1209 * operator strategy or if it is consecutively next to
1210 * the last column for which a clause with this
1211 * operator strategy was matched.
1213 if (btree_clauses[pc->op_strategy] != NIL)
1214 last = llast(btree_clauses[pc->op_strategy]);
1217 i == last->keyno || i == last->keyno + 1)
1218 btree_clauses[pc->op_strategy] =
1219 lappend(btree_clauses[pc->op_strategy], pc);
1222 * We may not need the next clause if they're of
1225 switch (pc->op_strategy)
1227 case BTLessEqualStrategyNumber:
1230 case BTLessStrategyNumber:
1232 need_next_eq = need_next_less = false;
1234 case BTEqualStrategyNumber:
1235 /* always accept clauses for the next key. */
1237 case BTGreaterEqualStrategyNumber:
1240 case BTGreaterStrategyNumber:
1242 need_next_eq = need_next_greater = false;
1246 /* We may want to change our mind. */
1247 if (consider_next_key)
1248 consider_next_key = (need_next_eq ||
1254 case PARTITION_STRATEGY_HASH:
1255 if (pc->op_strategy != HTEqualStrategyNumber)
1256 elog(ERROR, "invalid clause for hash partitioning");
1257 hash_clauses[pc->op_strategy] =
1258 lappend(hash_clauses[pc->op_strategy], pc);
1262 elog(ERROR, "invalid partition strategy: %c",
1263 part_scheme->strategy);
1269 * If we've decided that clauses for subsequent partition keys
1270 * wouldn't be useful for pruning, don't search any further.
1272 if (!consider_next_key)
1277 * Now, we have divided clauses according to their operator strategies.
1278 * Check for each strategy if we can generate pruning step(s) by
1279 * collecting a list of expressions whose values will constitute a vector
1280 * that can be used as a lookup key by a partition bound searching
1283 switch (part_scheme->strategy)
1285 case PARTITION_STRATEGY_LIST:
1286 case PARTITION_STRATEGY_RANGE:
1288 List *eq_clauses = btree_clauses[BTEqualStrategyNumber];
1289 List *le_clauses = btree_clauses[BTLessEqualStrategyNumber];
1290 List *ge_clauses = btree_clauses[BTGreaterEqualStrategyNumber];
1294 * For each clause under consideration for a given strategy,
1295 * we collect expressions from clauses for earlier keys, whose
1296 * operator strategy is inclusive, into a list called
1297 * 'prefix'. By appending the clause's own expression to the
1298 * 'prefix', we'll generate one step using the so generated
1299 * vector and assign the current strategy to it. Actually,
1300 * 'prefix' might contain multiple clauses for the same key,
1301 * in which case, we must generate steps for various
1302 * combinations of expressions of different keys, which
1303 * get_steps_using_prefix takes care of for us.
1305 for (strat = 1; strat <= BTMaxStrategyNumber; strat++)
1307 foreach(lc, btree_clauses[strat])
1309 PartClauseInfo *pc = lfirst(lc);
1315 * Expressions from = clauses can always be in the
1316 * prefix, provided they're from an earlier key.
1318 foreach(lc1, eq_clauses)
1320 PartClauseInfo *eqpc = lfirst(lc1);
1322 if (eqpc->keyno == pc->keyno)
1324 if (eqpc->keyno < pc->keyno)
1325 prefix = lappend(prefix, eqpc);
1329 * If we're generating steps for </<= strategy, we can
1330 * add other <= clauses to the prefix, provided
1331 * they're from an earlier key.
1333 if (strat == BTLessStrategyNumber ||
1334 strat == BTLessEqualStrategyNumber)
1336 foreach(lc1, le_clauses)
1338 PartClauseInfo *lepc = lfirst(lc1);
1340 if (lepc->keyno == pc->keyno)
1342 if (lepc->keyno < pc->keyno)
1343 prefix = lappend(prefix, lepc);
1348 * If we're generating steps for >/>= strategy, we can
1349 * add other >= clauses to the prefix, provided
1350 * they're from an earlier key.
1352 if (strat == BTGreaterStrategyNumber ||
1353 strat == BTGreaterEqualStrategyNumber)
1355 foreach(lc1, ge_clauses)
1357 PartClauseInfo *gepc = lfirst(lc1);
1359 if (gepc->keyno == pc->keyno)
1361 if (gepc->keyno < pc->keyno)
1362 prefix = lappend(prefix, gepc);
1367 * As mentioned above, if 'prefix' contains multiple
1368 * expressions for the same key, the following will
1369 * generate multiple steps, one for each combination
1370 * of the expressions for different keys.
1372 * Note that we pass NULL for step_nullkeys, because
1373 * we don't search list/range partition bounds where
1374 * some keys are NULL.
1376 Assert(pc->op_strategy == strat);
1377 pc_steps = get_steps_using_prefix(context, strat,
1384 opsteps = list_concat(opsteps, list_copy(pc_steps));
1390 case PARTITION_STRATEGY_HASH:
1392 List *eq_clauses = hash_clauses[HTEqualStrategyNumber];
1394 /* For hash partitioning, we have just the = strategy. */
1395 if (eq_clauses != NIL)
1404 * Locate the clause for the greatest column. This may
1405 * not belong to the last partition key, but it is the
1406 * clause belonging to the last partition key we found a
1409 pc = llast(eq_clauses);
1412 * There might be multiple clauses which matched to that
1413 * partition key; find the first such clause. While at
1414 * it, add all the clauses before that one to 'prefix'.
1416 last_keyno = pc->keyno;
1417 foreach(lc, eq_clauses)
1420 if (pc->keyno == last_keyno)
1422 prefix = lappend(prefix, pc);
1426 * For each clause for the "last" column, after appending
1427 * the clause's own expression to the 'prefix', we'll
1428 * generate one step using the so generated vector and
1429 * assign = as its strategy. Actually, 'prefix' might
1430 * contain multiple clauses for the same key, in which
1431 * case, we must generate steps for various combinations
1432 * of expressions of different keys, which
1433 * get_steps_using_prefix will take care of for us.
1435 for_each_cell(lc1, lc)
1440 * Note that we pass nullkeys for step_nullkeys,
1441 * because we need to tell hash partition bound search
1442 * function which of the keys we found IS NULL clauses
1445 Assert(pc->op_strategy == HTEqualStrategyNumber);
1447 get_steps_using_prefix(context,
1448 HTEqualStrategyNumber,
1455 opsteps = list_concat(opsteps, list_copy(pc_steps));
1462 elog(ERROR, "invalid partition strategy: %c",
1463 part_scheme->strategy);
1467 /* Lastly, add a combine step to mutually AND these op steps, if needed */
1468 if (list_length(opsteps) > 1)
1470 List *opstep_ids = NIL;
1472 foreach(lc, opsteps)
1474 PartitionPruneStep *step = lfirst(lc);
1476 opstep_ids = lappend_int(opstep_ids, step->step_id);
1479 if (opstep_ids != NIL)
1480 return gen_prune_step_combine(context, opstep_ids,
1481 PARTPRUNE_COMBINE_INTERSECT);
1484 else if (opsteps != NIL)
1485 return linitial(opsteps);
1491 * If the partition key has a collation, then the clause must have the same
1492 * input collation. If the partition key is non-collatable, we assume the
1493 * collation doesn't matter, because while collation wasn't considered when
1494 * performing partitioning, the clause still may have a collation assigned
1495 * due to the other input being of a collatable type.
1497 * See also IndexCollMatchesExprColl.
1499 #define PartCollMatchesExprColl(partcoll, exprcoll) \
1500 ((partcoll) == InvalidOid || (partcoll) == (exprcoll))
1503 * match_clause_to_partition_key
1504 * Attempt to match the given 'clause' with the specified partition key.
1507 * * PARTCLAUSE_NOMATCH if the clause doesn't match this partition key (but
1508 * caller should keep trying, because it might match a subsequent key).
1509 * Output arguments: none set.
1511 * * PARTCLAUSE_MATCH_CLAUSE if there is a match.
1512 * Output arguments: *pc is set to a PartClauseInfo constructed for the
1515 * * PARTCLAUSE_MATCH_NULLNESS if there is a match, and the matched clause was
1516 * either a "a IS NULL" or "a IS NOT NULL" clause.
1517 * Output arguments: *clause_is_not_null is set to false in the former case
1520 * * PARTCLAUSE_MATCH_STEPS if there is a match.
1521 * Output arguments: *clause_steps is set to a list of PartitionPruneStep
1522 * generated for the clause.
1524 * * PARTCLAUSE_MATCH_CONTRADICT if the clause is self-contradictory, ie
1525 * it provably returns FALSE or NULL.
1526 * Output arguments: none set.
1528 * * PARTCLAUSE_UNSUPPORTED if the clause doesn't match this partition key
1529 * and couldn't possibly match any other one either, due to its form or
1530 * properties (such as containing a volatile function).
1531 * Output arguments: none set.
1533 static PartClauseMatchStatus
1534 match_clause_to_partition_key(RelOptInfo *rel,
1535 GeneratePruningStepsContext *context,
1536 Expr *clause, Expr *partkey, int partkeyidx,
1537 bool *clause_is_not_null, PartClauseInfo **pc,
1538 List **clause_steps)
1540 PartitionScheme part_scheme = rel->part_scheme;
1541 Oid partopfamily = part_scheme->partopfamily[partkeyidx],
1542 partcoll = part_scheme->partcollation[partkeyidx];
1546 * Recognize specially shaped clauses that match with the Boolean
1549 if (match_boolean_partition_clause(partopfamily, clause, partkey, &expr))
1551 PartClauseInfo *partclause;
1553 partclause = (PartClauseInfo *) palloc(sizeof(PartClauseInfo));
1554 partclause->keyno = partkeyidx;
1555 /* Do pruning with the Boolean equality operator. */
1556 partclause->opno = BooleanEqualOperator;
1557 partclause->op_is_ne = false;
1558 partclause->expr = expr;
1559 /* We know that expr is of Boolean type. */
1560 partclause->cmpfn = rel->part_scheme->partsupfunc[partkeyidx].fn_oid;
1561 partclause->op_strategy = InvalidStrategy;
1565 return PARTCLAUSE_MATCH_CLAUSE;
1567 else if (IsA(clause, OpExpr) &&
1568 list_length(((OpExpr *) clause)->args) == 2)
1570 OpExpr *opclause = (OpExpr *) clause;
1576 negator = InvalidOid;
1579 bool is_opne_listp = false;
1580 PartClauseInfo *partclause;
1582 leftop = (Expr *) get_leftop(clause);
1583 if (IsA(leftop, RelabelType))
1584 leftop = ((RelabelType *) leftop)->arg;
1585 rightop = (Expr *) get_rightop(clause);
1586 if (IsA(rightop, RelabelType))
1587 rightop = ((RelabelType *) rightop)->arg;
1588 opno = opclause->opno;
1590 /* check if the clause matches this partition key */
1591 if (equal(leftop, partkey))
1593 else if (equal(rightop, partkey))
1596 * It's only useful if we can commute the operator to put the
1597 * partkey on the left. If we can't, the clause can be deemed
1598 * UNSUPPORTED. Even if its leftop matches some later partkey, we
1599 * now know it has Vars on the right, so it's no use.
1601 opno = get_commutator(opno);
1602 if (!OidIsValid(opno))
1603 return PARTCLAUSE_UNSUPPORTED;
1607 /* clause does not match this partition key, but perhaps next. */
1608 return PARTCLAUSE_NOMATCH;
1611 * Partition key match also requires collation match. There may be
1612 * multiple partkeys with the same expression but different
1613 * collations, so failure is NOMATCH.
1615 if (!PartCollMatchesExprColl(partcoll, opclause->inputcollid))
1616 return PARTCLAUSE_NOMATCH;
1619 * Matched with this key. Now check various properties of the clause
1620 * to see if it's sane to use it for pruning. In most of these cases,
1621 * we can return UNSUPPORTED because the same failure would occur no
1622 * matter which partkey it's matched to.
1626 * We can't prune using an expression with Vars. (Report failure as
1627 * UNSUPPORTED, not NOMATCH: as in the no-commutator case above, we
1628 * now know there are Vars on both sides, so it's no good.)
1630 if (contain_var_clause((Node *) expr))
1631 return PARTCLAUSE_UNSUPPORTED;
1634 * Only allow strict operators. This will guarantee nulls are
1637 if (!op_strict(opno))
1638 return PARTCLAUSE_UNSUPPORTED;
1640 /* We can't use any volatile expressions to prune partitions. */
1641 if (contain_volatile_functions((Node *) expr))
1642 return PARTCLAUSE_UNSUPPORTED;
1645 * See if the operator is relevant to the partitioning opfamily.
1647 * Normally we only care about operators that are listed as being part
1648 * of the partitioning operator family. But there is one exception:
1649 * the not-equals operators are not listed in any operator family
1650 * whatsoever, but their negators (equality) are. We can use one of
1651 * those if we find it, but only for list partitioning.
1653 * Note: we report NOMATCH on failure, in case a later partkey has the
1654 * same expression but different opfamily. That's unlikely, but not
1655 * much more so than duplicate expressions with different collations.
1657 if (op_in_opfamily(opno, partopfamily))
1659 get_op_opfamily_properties(opno, partopfamily, false,
1660 &op_strategy, &op_lefttype,
1665 if (part_scheme->strategy != PARTITION_STRATEGY_LIST)
1666 return PARTCLAUSE_NOMATCH;
1668 /* See if the negator is equality */
1669 negator = get_negator(opno);
1670 if (OidIsValid(negator) && op_in_opfamily(negator, partopfamily))
1672 get_op_opfamily_properties(negator, partopfamily, false,
1673 &op_strategy, &op_lefttype,
1675 if (op_strategy == BTEqualStrategyNumber)
1676 is_opne_listp = true; /* bingo */
1679 /* Nope, it's not <> either. */
1681 return PARTCLAUSE_NOMATCH;
1685 * Now find the procedure to use, based on the types. If the clause's
1686 * other argument is of the same type as the partitioning opclass's
1687 * declared input type, we can use the procedure cached in
1688 * PartitionKey. If not, search for a cross-type one in the same
1689 * opfamily; if one doesn't exist, report no match.
1691 if (op_righttype == part_scheme->partopcintype[partkeyidx])
1692 cmpfn = part_scheme->partsupfunc[partkeyidx].fn_oid;
1695 switch (part_scheme->strategy)
1698 * For range and list partitioning, we need the ordering
1699 * procedure with lefttype being the partition key's type,
1700 * and righttype the clause's operator's right type.
1702 case PARTITION_STRATEGY_LIST:
1703 case PARTITION_STRATEGY_RANGE:
1705 get_opfamily_proc(part_scheme->partopfamily[partkeyidx],
1706 part_scheme->partopcintype[partkeyidx],
1707 op_righttype, BTORDER_PROC);
1711 * For hash partitioning, we need the hashing procedure
1712 * for the clause's type.
1714 case PARTITION_STRATEGY_HASH:
1716 get_opfamily_proc(part_scheme->partopfamily[partkeyidx],
1717 op_righttype, op_righttype,
1722 elog(ERROR, "invalid partition strategy: %c",
1723 part_scheme->strategy);
1724 cmpfn = InvalidOid; /* keep compiler quiet */
1728 if (!OidIsValid(cmpfn))
1729 return PARTCLAUSE_NOMATCH;
1733 * Build the clause, passing the negator if applicable.
1735 partclause = (PartClauseInfo *) palloc(sizeof(PartClauseInfo));
1736 partclause->keyno = partkeyidx;
1739 Assert(OidIsValid(negator));
1740 partclause->opno = negator;
1741 partclause->op_is_ne = true;
1742 partclause->op_strategy = InvalidStrategy;
1746 partclause->opno = opno;
1747 partclause->op_is_ne = false;
1748 partclause->op_strategy = op_strategy;
1750 partclause->expr = expr;
1751 partclause->cmpfn = cmpfn;
1755 return PARTCLAUSE_MATCH_CLAUSE;
1757 else if (IsA(clause, ScalarArrayOpExpr))
1759 ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
1760 Oid saop_op = saop->opno;
1761 Oid saop_coll = saop->inputcollid;
1762 Expr *leftop = (Expr *) linitial(saop->args),
1763 *rightop = (Expr *) lsecond(saop->args);
1769 if (IsA(leftop, RelabelType))
1770 leftop = ((RelabelType *) leftop)->arg;
1772 /* Check it matches this partition key */
1773 if (!equal(leftop, partkey) ||
1774 !PartCollMatchesExprColl(partcoll, saop->inputcollid))
1775 return PARTCLAUSE_NOMATCH;
1778 * Matched with this key. Check various properties of the clause to
1779 * see if it can sanely be used for partition pruning (this is mostly
1780 * the same as for a plain OpExpr).
1783 /* We can't prune using an expression with Vars. */
1784 if (contain_var_clause((Node *) rightop))
1785 return PARTCLAUSE_UNSUPPORTED;
1788 * Only allow strict operators. This will guarantee nulls are
1791 if (!op_strict(saop_op))
1792 return PARTCLAUSE_UNSUPPORTED;
1794 /* We can't use any volatile expressions to prune partitions. */
1795 if (contain_volatile_functions((Node *) rightop))
1796 return PARTCLAUSE_UNSUPPORTED;
1799 * In case of NOT IN (..), we get a '<>', which we handle if list
1800 * partitioning is in use and we're able to confirm that it's negator
1801 * is a btree equality operator belonging to the partitioning operator
1802 * family. As above, report NOMATCH for non-matching operator.
1804 if (!op_in_opfamily(saop_op, partopfamily))
1808 if (part_scheme->strategy != PARTITION_STRATEGY_LIST)
1809 return PARTCLAUSE_NOMATCH;
1811 negator = get_negator(saop_op);
1812 if (OidIsValid(negator) && op_in_opfamily(negator, partopfamily))
1818 get_op_opfamily_properties(negator, partopfamily,
1820 &lefttype, &righttype);
1821 if (strategy != BTEqualStrategyNumber)
1822 return PARTCLAUSE_NOMATCH;
1825 return PARTCLAUSE_NOMATCH; /* no useful negator */
1829 * First generate a list of Const nodes, one for each array element
1830 * (excepting nulls).
1833 if (IsA(rightop, Const))
1835 Const *arr = (Const *) rightop;
1836 ArrayType *arrval = DatumGetArrayTypeP(arr->constvalue);
1845 get_typlenbyvalalign(ARR_ELEMTYPE(arrval),
1846 &elemlen, &elembyval, &elemalign);
1847 deconstruct_array(arrval,
1848 ARR_ELEMTYPE(arrval),
1849 elemlen, elembyval, elemalign,
1850 &elem_values, &elem_nulls,
1852 for (i = 0; i < num_elems; i++)
1857 * A null array element must lead to a null comparison result,
1858 * since saop_op is known strict. We can ignore it in the
1859 * useOr case, but otherwise it implies self-contradiction.
1865 return PARTCLAUSE_MATCH_CONTRADICT;
1868 elem_expr = makeConst(ARR_ELEMTYPE(arrval), -1,
1869 arr->constcollid, elemlen,
1870 elem_values[i], false, elembyval);
1871 elem_exprs = lappend(elem_exprs, elem_expr);
1874 else if (IsA(rightop, ArrayExpr))
1876 ArrayExpr *arrexpr = castNode(ArrayExpr, rightop);
1879 * For a nested ArrayExpr, we don't know how to get the actual
1880 * scalar values out into a flat list, so we give up doing
1881 * anything with this ScalarArrayOpExpr.
1883 if (arrexpr->multidims)
1884 return PARTCLAUSE_UNSUPPORTED;
1886 elem_exprs = arrexpr->elements;
1890 /* Give up on any other clause types. */
1891 return PARTCLAUSE_UNSUPPORTED;
1895 * Now generate a list of clauses, one for each array element, of the
1896 * form saop_leftop saop_op elem_expr
1899 foreach(lc1, elem_exprs)
1901 Expr *rightop = (Expr *) lfirst(lc1),
1904 elem_clause = make_opclause(saop_op, BOOLOID, false,
1906 InvalidOid, saop_coll);
1907 elem_clauses = lappend(elem_clauses, elem_clause);
1911 * If we have an ANY clause and multiple elements, now turn the list
1912 * of clauses into an OR expression.
1914 if (saop->useOr && list_length(elem_clauses) > 1)
1915 elem_clauses = list_make1(makeBoolExpr(OR_EXPR, elem_clauses, -1));
1917 /* Finally, generate steps */
1919 gen_partprune_steps_internal(context, rel, elem_clauses,
1922 return PARTCLAUSE_MATCH_CONTRADICT;
1923 else if (*clause_steps == NIL)
1924 return PARTCLAUSE_UNSUPPORTED; /* step generation failed */
1925 return PARTCLAUSE_MATCH_STEPS;
1927 else if (IsA(clause, NullTest))
1929 NullTest *nulltest = (NullTest *) clause;
1930 Expr *arg = nulltest->arg;
1932 if (IsA(arg, RelabelType))
1933 arg = ((RelabelType *) arg)->arg;
1935 /* Does arg match with this partition key column? */
1936 if (!equal(arg, partkey))
1937 return PARTCLAUSE_NOMATCH;
1939 *clause_is_not_null = (nulltest->nulltesttype == IS_NOT_NULL);
1941 return PARTCLAUSE_MATCH_NULLNESS;
1944 return PARTCLAUSE_UNSUPPORTED;
1948 * get_steps_using_prefix
1949 * Generate list of PartitionPruneStepOp steps each consisting of given
1952 * To generate steps, step_lastexpr and step_lastcmpfn are appended to
1953 * expressions and cmpfns, respectively, extracted from the clauses in
1954 * 'prefix'. Actually, since 'prefix' may contain multiple clauses for the
1955 * same partition key column, we must generate steps for various combinations
1956 * of the clauses of different keys.
1959 get_steps_using_prefix(GeneratePruningStepsContext *context,
1960 StrategyNumber step_opstrategy,
1962 Expr *step_lastexpr,
1965 Bitmapset *step_nullkeys,
1968 /* Quick exit if there are no values to prefix with. */
1969 if (list_length(prefix) == 0)
1971 PartitionPruneStep *step;
1973 step = gen_prune_step_op(context,
1976 list_make1(step_lastexpr),
1977 list_make1_oid(step_lastcmpfn),
1979 return list_make1(step);
1982 /* Recurse to generate steps for various combinations. */
1983 return get_steps_using_prefix_recurse(context,
1995 * get_steps_using_prefix_recurse
1996 * Recursively generate combinations of clauses for different partition
1997 * keys and start generating steps upon reaching clauses for the greatest
1998 * column that is less than the one for which we're currently generating
1999 * steps (that is, step_lastkeyno)
2001 * 'start' is where we should start iterating for the current invocation.
2002 * 'step_exprs' and 'step_cmpfns' each contains the expressions and cmpfns
2003 * we've generated so far from the clauses for the previous part keys.
2006 get_steps_using_prefix_recurse(GeneratePruningStepsContext *context,
2007 StrategyNumber step_opstrategy,
2009 Expr *step_lastexpr,
2012 Bitmapset *step_nullkeys,
2021 /* Actually, recursion would be limited by PARTITION_MAX_KEYS. */
2022 check_stack_depth();
2024 /* Check if we need to recurse. */
2025 Assert(start != NULL);
2026 cur_keyno = ((PartClauseInfo *) lfirst(start))->keyno;
2027 if (cur_keyno < step_lastkeyno - 1)
2030 ListCell *next_start;
2033 * For each clause with cur_keyno, adds its expr and cmpfn to
2034 * step_exprs and step_cmpfns, respectively, and recurse after setting
2035 * next_start to the ListCell of the first clause for the next
2038 for_each_cell(lc, start)
2042 if (pc->keyno > cur_keyno)
2047 for_each_cell(lc, start)
2052 if (pc->keyno == cur_keyno)
2054 /* clean up before starting a new recursion cycle. */
2057 list_free(step_exprs);
2058 list_free(step_cmpfns);
2059 step_exprs = list_make1(pc->expr);
2060 step_cmpfns = list_make1_oid(pc->cmpfn);
2064 step_exprs = lappend(step_exprs, pc->expr);
2065 step_cmpfns = lappend_oid(step_cmpfns, pc->cmpfn);
2070 Assert(pc->keyno > cur_keyno);
2074 moresteps = get_steps_using_prefix_recurse(context,
2084 result = list_concat(result, moresteps);
2090 * End the current recursion cycle and start generating steps, one for
2091 * each clause with cur_keyno, which is all clauses from here onward
2092 * till the end of the list.
2094 Assert(list_length(step_exprs) == cur_keyno);
2095 for_each_cell(lc, start)
2097 PartClauseInfo *pc = lfirst(lc);
2098 PartitionPruneStep *step;
2102 Assert(pc->keyno == cur_keyno);
2104 /* Leave the original step_exprs unmodified. */
2105 step_exprs1 = list_copy(step_exprs);
2106 step_exprs1 = lappend(step_exprs1, pc->expr);
2107 step_exprs1 = lappend(step_exprs1, step_lastexpr);
2109 /* Leave the original step_cmpfns unmodified. */
2110 step_cmpfns1 = list_copy(step_cmpfns);
2111 step_cmpfns1 = lappend_oid(step_cmpfns1, pc->cmpfn);
2112 step_cmpfns1 = lappend_oid(step_cmpfns1, step_lastcmpfn);
2114 step = gen_prune_step_op(context,
2115 step_opstrategy, step_op_is_ne,
2116 step_exprs1, step_cmpfns1,
2118 result = lappend(result, step);
2126 * get_matching_hash_bounds
2127 * Determine offset of the hash bound matching the specified values,
2128 * considering that all the non-null values come from clauses containing
2129 * a compatible hash equality operator and any keys that are null come
2130 * from an IS NULL clause.
2132 * Generally this function will return a single matching bound offset,
2133 * although if a partition has not been setup for a given modulus then we may
2134 * return no matches. If the number of clauses found don't cover the entire
2135 * partition key, then we'll need to return all offsets.
2137 * 'opstrategy' if non-zero must be HTEqualStrategyNumber.
2139 * 'values' contains Datums indexed by the partition key to use for pruning.
2141 * 'nvalues', the number of Datums in the 'values' array.
2143 * 'partsupfunc' contains partition hashing functions that can produce correct
2144 * hash for the type of the values contained in 'values'.
2146 * 'nullkeys' is the set of partition keys that are null.
2148 static PruneStepResult *
2149 get_matching_hash_bounds(PartitionPruneContext *context,
2150 StrategyNumber opstrategy, Datum *values, int nvalues,
2151 FmgrInfo *partsupfunc, Bitmapset *nullkeys)
2153 PruneStepResult *result = (PruneStepResult *) palloc0(sizeof(PruneStepResult));
2154 PartitionBoundInfo boundinfo = context->boundinfo;
2155 int *partindices = boundinfo->indexes;
2156 int partnatts = context->partnatts;
2157 bool isnull[PARTITION_MAX_KEYS];
2160 int greatest_modulus;
2162 Assert(context->strategy == PARTITION_STRATEGY_HASH);
2165 * For hash partitioning we can only perform pruning based on equality
2166 * clauses to the partition key or IS NULL clauses. We also can only
2167 * prune if we got values for all keys.
2169 if (nvalues + bms_num_members(nullkeys) == partnatts)
2172 * If there are any values, they must have come from clauses
2173 * containing an equality operator compatible with hash partitioning.
2175 Assert(opstrategy == HTEqualStrategyNumber || nvalues == 0);
2177 for (i = 0; i < partnatts; i++)
2178 isnull[i] = bms_is_member(i, nullkeys);
2180 greatest_modulus = get_hash_partition_greatest_modulus(boundinfo);
2181 rowHash = compute_partition_hash_value(partnatts, partsupfunc,
2184 if (partindices[rowHash % greatest_modulus] >= 0)
2185 result->bound_offsets =
2186 bms_make_singleton(rowHash % greatest_modulus);
2190 /* Getting here means at least one hash partition exists. */
2191 Assert(boundinfo->ndatums > 0);
2192 result->bound_offsets = bms_add_range(NULL, 0,
2193 boundinfo->ndatums - 1);
2197 * There is neither a special hash null partition or the default hash
2200 result->scan_null = result->scan_default = false;
2206 * get_matching_list_bounds
2207 * Determine the offsets of list bounds matching the specified value,
2208 * according to the semantics of the given operator strategy
2209 * 'opstrategy' if non-zero must be a btree strategy number.
2211 * 'value' contains the value to use for pruning.
2213 * 'nvalues', if non-zero, should be exactly 1, because of list partitioning.
2215 * 'partsupfunc' contains the list partitioning comparison function to be used
2216 * to perform partition_list_bsearch
2218 * 'nullkeys' is the set of partition keys that are null.
2220 static PruneStepResult *
2221 get_matching_list_bounds(PartitionPruneContext *context,
2222 StrategyNumber opstrategy, Datum value, int nvalues,
2223 FmgrInfo *partsupfunc, Bitmapset *nullkeys)
2225 PruneStepResult *result = (PruneStepResult *) palloc0(sizeof(PruneStepResult));
2226 PartitionBoundInfo boundinfo = context->boundinfo;
2231 bool inclusive = false;
2232 Oid *partcollation = context->partcollation;
2234 Assert(context->strategy == PARTITION_STRATEGY_LIST);
2235 Assert(context->partnatts == 1);
2237 result->scan_null = result->scan_default = false;
2239 if (!bms_is_empty(nullkeys))
2242 * Nulls may exist in only one partition - the partition whose
2243 * accepted set of values includes null or the default partition if
2244 * the former doesn't exist.
2246 if (partition_bound_accepts_nulls(boundinfo))
2247 result->scan_null = true;
2249 result->scan_default = partition_bound_has_default(boundinfo);
2254 * If there are no datums to compare keys with, but there are partitions,
2255 * just return the default partition if one exists.
2257 if (boundinfo->ndatums == 0)
2259 result->scan_default = partition_bound_has_default(boundinfo);
2264 maxoff = boundinfo->ndatums - 1;
2267 * If there are no values to compare with the datums in boundinfo, it
2268 * means the caller asked for partitions for all non-null datums. Add
2269 * indexes of *all* partitions, including the default if any.
2273 Assert(boundinfo->ndatums > 0);
2274 result->bound_offsets = bms_add_range(NULL, 0,
2275 boundinfo->ndatums - 1);
2276 result->scan_default = partition_bound_has_default(boundinfo);
2280 /* Special case handling of values coming from a <> operator clause. */
2281 if (opstrategy == InvalidStrategy)
2284 * First match to all bounds. We'll remove any matching datums below.
2286 Assert(boundinfo->ndatums > 0);
2287 result->bound_offsets = bms_add_range(NULL, 0,
2288 boundinfo->ndatums - 1);
2290 off = partition_list_bsearch(partsupfunc, partcollation, boundinfo,
2292 if (off >= 0 && is_equal)
2295 /* We have a match. Remove from the result. */
2296 Assert(boundinfo->indexes[off] >= 0);
2297 result->bound_offsets = bms_del_member(result->bound_offsets,
2301 /* Always include the default partition if any. */
2302 result->scan_default = partition_bound_has_default(boundinfo);
2308 * With range queries, always include the default list partition, because
2309 * list partitions divide the key space in a discontinuous manner, not all
2310 * values in the given range will have a partition assigned. This may not
2311 * technically be true for some data types (e.g. integer types), however,
2312 * we currently lack any sort of infrastructure to provide us with proofs
2313 * that would allow us to do anything smarter here.
2315 if (opstrategy != BTEqualStrategyNumber)
2316 result->scan_default = partition_bound_has_default(boundinfo);
2320 case BTEqualStrategyNumber:
2321 off = partition_list_bsearch(partsupfunc,
2325 if (off >= 0 && is_equal)
2327 Assert(boundinfo->indexes[off] >= 0);
2328 result->bound_offsets = bms_make_singleton(off);
2331 result->scan_default = partition_bound_has_default(boundinfo);
2334 case BTGreaterEqualStrategyNumber:
2337 case BTGreaterStrategyNumber:
2338 off = partition_list_bsearch(partsupfunc,
2344 /* We don't want the matched datum to be in the result. */
2345 if (!is_equal || !inclusive)
2351 * This case means all partition bounds are greater, which in
2352 * turn means that all partitions satisfy this key.
2358 * off is greater than the numbers of datums we have partitions
2359 * for. The only possible partition that could contain a match is
2360 * the default partition, but we must've set context->scan_default
2361 * above anyway if one exists.
2363 if (off > boundinfo->ndatums - 1)
2369 case BTLessEqualStrategyNumber:
2372 case BTLessStrategyNumber:
2373 off = partition_list_bsearch(partsupfunc,
2377 if (off >= 0 && is_equal && !inclusive)
2381 * off is smaller than the datums of all non-default partitions.
2382 * The only possible partition that could contain a match is the
2383 * default partition, but we must've set context->scan_default
2384 * above anyway if one exists.
2393 elog(ERROR, "invalid strategy number %d", opstrategy);
2397 Assert(minoff >= 0 && maxoff >= 0);
2398 result->bound_offsets = bms_add_range(NULL, minoff, maxoff);
2404 * get_matching_range_bounds
2405 * Determine the offsets of range bounds matching the specified values,
2406 * according to the semantics of the given operator strategy
2408 * Each datum whose offset is in result is to be treated as the upper bound of
2409 * the partition that will contain the desired values.
2411 * If default partition needs to be scanned for given values, set scan_default
2412 * in result if present.
2414 * 'opstrategy' if non-zero must be a btree strategy number.
2416 * 'values' contains Datums indexed by the partition key to use for pruning.
2418 * 'nvalues', number of Datums in 'values' array. Must be <= context->partnatts.
2420 * 'partsupfunc' contains the range partitioning comparison functions to be
2421 * used to perform partition_range_datum_bsearch or partition_rbound_datum_cmp
2424 * 'nullkeys' is the set of partition keys that are null.
2426 static PruneStepResult *
2427 get_matching_range_bounds(PartitionPruneContext *context,
2428 StrategyNumber opstrategy, Datum *values, int nvalues,
2429 FmgrInfo *partsupfunc, Bitmapset *nullkeys)
2431 PruneStepResult *result = (PruneStepResult *) palloc0(sizeof(PruneStepResult));
2432 PartitionBoundInfo boundinfo = context->boundinfo;
2433 Oid *partcollation = context->partcollation;
2434 int partnatts = context->partnatts;
2435 int *partindices = boundinfo->indexes;
2441 bool inclusive = false;
2443 Assert(context->strategy == PARTITION_STRATEGY_RANGE);
2444 Assert(nvalues <= partnatts);
2446 result->scan_null = result->scan_default = false;
2449 * If there are no datums to compare keys with, or if we got an IS NULL
2450 * clause just return the default partition, if it exists.
2452 if (boundinfo->ndatums == 0 || !bms_is_empty(nullkeys))
2454 result->scan_default = partition_bound_has_default(boundinfo);
2459 maxoff = boundinfo->ndatums;
2462 * If there are no values to compare with the datums in boundinfo, it
2463 * means the caller asked for partitions for all non-null datums. Add
2464 * indexes of *all* partitions, including the default partition if one
2469 if (partindices[minoff] < 0)
2471 if (partindices[maxoff] < 0)
2474 result->scan_default = partition_bound_has_default(boundinfo);
2475 Assert(minoff >= 0 && maxoff >= 0);
2476 result->bound_offsets = bms_add_range(NULL, minoff, maxoff);
2482 * If the query does not constrain all key columns, we'll need to scan the
2483 * default partition, if any.
2485 if (nvalues < partnatts)
2486 result->scan_default = partition_bound_has_default(boundinfo);
2490 case BTEqualStrategyNumber:
2491 /* Look for the smallest bound that is = lookup value. */
2492 off = partition_range_datum_bsearch(partsupfunc,
2498 if (off >= 0 && is_equal)
2500 if (nvalues == partnatts)
2502 /* There can only be zero or one matching partition. */
2503 if (partindices[off + 1] >= 0)
2504 result->bound_offsets = bms_make_singleton(off + 1);
2506 result->scan_default =
2507 partition_bound_has_default(boundinfo);
2512 int saved_off = off;
2515 * Since the lookup value contains only a prefix of keys,
2516 * we must find other bounds that may also match the
2517 * prefix. partition_range_datum_bsearch() returns the
2518 * offset of one of them, find others by checking adjacent
2523 * First find greatest bound that's smaller than the
2531 partition_rbound_datum_cmp(partsupfunc,
2533 boundinfo->datums[off - 1],
2534 boundinfo->kind[off - 1],
2542 partition_rbound_datum_cmp(partsupfunc,
2544 boundinfo->datums[off],
2545 boundinfo->kind[off],
2549 * We can treat 'off' as the offset of the smallest bound
2550 * to be included in the result, if we know it is the
2551 * upper bound of the partition in which the lookup value
2552 * could possibly exist. One case it couldn't is if the
2553 * bound, or precisely the matched portion of its prefix,
2556 if (boundinfo->kind[off][nvalues] ==
2557 PARTITION_RANGE_DATUM_MINVALUE)
2563 * Now find smallest bound that's greater than the lookup
2567 while (off < boundinfo->ndatums - 1)
2571 cmpval = partition_rbound_datum_cmp(partsupfunc,
2573 boundinfo->datums[off + 1],
2574 boundinfo->kind[off + 1],
2582 partition_rbound_datum_cmp(partsupfunc,
2584 boundinfo->datums[off],
2585 boundinfo->kind[off],
2589 * off + 1, then would be the offset of the greatest bound
2590 * to be included in the result.
2596 * Skip if minoff/maxoff are actually the upper bound of a
2597 * un-assigned portion of values.
2599 if (partindices[minoff] < 0 && minoff < boundinfo->ndatums)
2601 if (partindices[maxoff] < 0 && maxoff >= 1)
2605 * There may exist a range of values unassigned to any
2606 * non-default partition between the datums at minoff and
2607 * maxoff. Add the default partition in that case.
2609 if (partition_bound_has_default(boundinfo))
2611 for (i = minoff; i <= maxoff; i++)
2613 if (partindices[i] < 0)
2615 result->scan_default = true;
2621 Assert(minoff >= 0 && maxoff >= 0);
2622 result->bound_offsets = bms_add_range(NULL, minoff, maxoff);
2624 else if (off >= 0) /* !is_equal */
2627 * The lookup value falls in the range between some bounds in
2628 * boundinfo. 'off' would be the offset of the greatest bound
2629 * that is <= lookup value, so add off + 1 to the result
2630 * instead as the offset of the upper bound of the only
2631 * partition that may contain the lookup value.
2633 if (partindices[off + 1] >= 0)
2634 result->bound_offsets = bms_make_singleton(off + 1);
2636 result->scan_default =
2637 partition_bound_has_default(boundinfo);
2642 * off < 0: the lookup value is smaller than all bounds, so
2643 * only the default partition qualifies, if there is one.
2645 result->scan_default = partition_bound_has_default(boundinfo);
2650 case BTGreaterEqualStrategyNumber:
2653 case BTGreaterStrategyNumber:
2656 * Look for the smallest bound that is > or >= lookup value and
2657 * set minoff to its offset.
2659 off = partition_range_datum_bsearch(partsupfunc,
2667 * All bounds are greater than the lookup value, so include
2668 * all of them in the result.
2674 if (is_equal && nvalues < partnatts)
2677 * Since the lookup value contains only a prefix of keys,
2678 * we must find other bounds that may also match the
2679 * prefix. partition_range_datum_bsearch() returns the
2680 * offset of one of them, find others by checking adjacent
2683 * Based on whether the lookup values are inclusive or
2684 * not, we must either include the indexes of all such
2685 * bounds in the result (that is, set minoff to the index
2686 * of smallest such bound) or find the smallest one that's
2687 * greater than the lookup values and set minoff to that.
2689 while (off >= 1 && off < boundinfo->ndatums - 1)
2694 nextoff = inclusive ? off - 1 : off + 1;
2696 partition_rbound_datum_cmp(partsupfunc,
2698 boundinfo->datums[nextoff],
2699 boundinfo->kind[nextoff],
2708 partition_rbound_datum_cmp(partsupfunc,
2710 boundinfo->datums[off],
2711 boundinfo->kind[off],
2714 minoff = inclusive ? off : off + 1;
2718 * lookup value falls in the range between some bounds in
2719 * boundinfo. off would be the offset of the greatest bound
2720 * that is <= lookup value, so add off + 1 to the result
2721 * instead as the offset of the upper bound of the smallest
2722 * partition that may contain the lookup value.
2729 case BTLessEqualStrategyNumber:
2732 case BTLessStrategyNumber:
2735 * Look for the greatest bound that is < or <= lookup value and
2736 * set minoff to its offset.
2738 off = partition_range_datum_bsearch(partsupfunc,
2746 * All bounds are greater than the key, so we could only
2747 * expect to find the lookup key in the default partition.
2749 result->scan_default = partition_bound_has_default(boundinfo);
2755 * See the comment above.
2757 if (is_equal && nvalues < partnatts)
2759 while (off >= 1 && off < boundinfo->ndatums - 1)
2764 nextoff = inclusive ? off + 1 : off - 1;
2765 cmpval = partition_rbound_datum_cmp(partsupfunc,
2767 boundinfo->datums[nextoff],
2768 boundinfo->kind[nextoff],
2777 partition_rbound_datum_cmp(partsupfunc,
2779 boundinfo->datums[off],
2780 boundinfo->kind[off],
2783 maxoff = inclusive ? off + 1 : off;
2787 * The lookup value falls in the range between some bounds in
2788 * boundinfo. 'off' would be the offset of the greatest bound
2789 * that is <= lookup value, so add off + 1 to the result
2790 * instead as the offset of the upper bound of the greatest
2791 * partition that may contain lookup value. If the lookup
2792 * value had exactly matched the bound, but it isn't
2793 * inclusive, no need add the adjacent partition.
2795 else if (!is_equal || inclusive)
2803 elog(ERROR, "invalid strategy number %d", opstrategy);
2808 * Skip a gap and when doing so, check if the bound contains a finite
2809 * value to decide if we need to add the default partition. If it's an
2810 * infinite bound, we need not add the default partition, as having an
2811 * infinite bound means the partition in question catches any values that
2812 * would otherwise be in the default partition.
2814 if (partindices[minoff] < 0)
2816 int lastkey = nvalues - 1;
2819 minoff < boundinfo->ndatums &&
2820 boundinfo->kind[minoff][lastkey] ==
2821 PARTITION_RANGE_DATUM_VALUE)
2822 result->scan_default = partition_bound_has_default(boundinfo);
2828 * Skip a gap. See the above comment about how we decide whether or not
2829 * to scan the default partition based whether the datum that will become
2830 * the maximum datum is finite or not.
2832 if (maxoff >= 1 && partindices[maxoff] < 0)
2834 int lastkey = nvalues - 1;
2837 maxoff <= boundinfo->ndatums &&
2838 boundinfo->kind[maxoff - 1][lastkey] ==
2839 PARTITION_RANGE_DATUM_VALUE)
2840 result->scan_default = partition_bound_has_default(boundinfo);
2845 if (partition_bound_has_default(boundinfo))
2848 * There may exist a range of values unassigned to any non-default
2849 * partition between the datums at minoff and maxoff. Add the default
2850 * partition in that case.
2852 for (i = minoff; i <= maxoff; i++)
2854 if (partindices[i] < 0)
2856 result->scan_default = true;
2862 Assert(minoff >= 0 && maxoff >= 0);
2863 if (minoff <= maxoff)
2864 result->bound_offsets = bms_add_range(NULL, minoff, maxoff);
2870 * pull_exec_paramids
2871 * Returns a Bitmapset containing the paramids of all Params with
2872 * paramkind = PARAM_EXEC in 'expr'.
2875 pull_exec_paramids(Expr *expr)
2877 Bitmapset *result = NULL;
2879 (void) pull_exec_paramids_walker((Node *) expr, &result);
2885 pull_exec_paramids_walker(Node *node, Bitmapset **context)
2889 if (IsA(node, Param))
2891 Param *param = (Param *) node;
2893 if (param->paramkind == PARAM_EXEC)
2894 *context = bms_add_member(*context, param->paramid);
2897 return expression_tree_walker(node, pull_exec_paramids_walker,
2902 * analyze_partkey_exprs
2903 * Loop through all pruning steps and identify which ones require
2904 * executor startup-time or executor run-time pruning.
2906 * Returns true if any executor partition pruning should be attempted at this
2907 * level. Also fills fields of *pinfo to record how to process each step.
2910 analyze_partkey_exprs(PartitionedRelPruneInfo *pinfo, List *steps,
2913 bool doruntimeprune = false;
2917 * Steps require run-time pruning if they contain EXEC_PARAM Params.
2918 * Otherwise, if their expressions aren't simple Consts, they require
2919 * startup-time pruning.
2921 pinfo->nexprs = list_length(steps) * partnatts;
2922 pinfo->hasexecparam = (bool *) palloc0(sizeof(bool) * pinfo->nexprs);
2923 pinfo->do_initial_prune = false;
2924 pinfo->do_exec_prune = false;
2925 pinfo->execparamids = NULL;
2929 PartitionPruneStepOp *step = (PartitionPruneStepOp *) lfirst(lc);
2933 if (!IsA(step, PartitionPruneStepOp))
2937 foreach(lc2, step->exprs)
2939 Expr *expr = lfirst(lc2);
2941 if (!IsA(expr, Const))
2943 Bitmapset *execparamids = pull_exec_paramids(expr);
2945 int stateidx = PruneCxtStateIdx(partnatts,
2949 Assert(stateidx < pinfo->nexprs);
2950 hasexecparams = !bms_is_empty(execparamids);
2951 pinfo->hasexecparam[stateidx] = hasexecparams;
2952 pinfo->execparamids = bms_join(pinfo->execparamids,
2956 pinfo->do_exec_prune = true;
2958 pinfo->do_initial_prune = true;
2960 doruntimeprune = true;
2966 return doruntimeprune;
2970 * perform_pruning_base_step
2971 * Determines the indexes of datums that satisfy conditions specified in
2974 * Result also contains whether special null-accepting and/or default
2975 * partition need to be scanned.
2977 static PruneStepResult *
2978 perform_pruning_base_step(PartitionPruneContext *context,
2979 PartitionPruneStepOp *opstep)
2985 Datum values[PARTITION_MAX_KEYS];
2986 FmgrInfo *partsupfunc;
2990 * There better be the same number of expressions and compare functions.
2992 Assert(list_length(opstep->exprs) == list_length(opstep->cmpfns));
2995 lc1 = list_head(opstep->exprs);
2996 lc2 = list_head(opstep->cmpfns);
2999 * Generate the partition lookup key that will be used by one of the
3000 * get_matching_*_bounds functions called below.
3002 for (keyno = 0; keyno < context->partnatts; keyno++)
3005 * For hash partitioning, it is possible that values of some keys are
3006 * not provided in operator clauses, but instead the planner found
3007 * that they appeared in a IS NULL clause.
3009 if (bms_is_member(keyno, opstep->nullkeys))
3013 * For range partitioning, we must only perform pruning with values
3014 * for either all partition keys or a prefix thereof.
3016 if (keyno > nvalues && context->strategy == PARTITION_STRATEGY_RANGE)
3026 stateidx = PruneCxtStateIdx(context->partnatts,
3027 opstep->step.step_id, keyno);
3028 if (partkey_datum_from_expr(context, expr, stateidx,
3034 * Since we only allow strict operators in pruning steps, any
3035 * null-valued comparison value must cause the comparison to
3036 * fail, so that no partitions could match.
3040 PruneStepResult *result;
3042 result = (PruneStepResult *) palloc(sizeof(PruneStepResult));
3043 result->bound_offsets = NULL;
3044 result->scan_default = false;
3045 result->scan_null = false;
3050 /* Set up the stepcmpfuncs entry, unless we already did */
3051 cmpfn = lfirst_oid(lc2);
3052 Assert(OidIsValid(cmpfn));
3053 if (cmpfn != context->stepcmpfuncs[stateidx].fn_oid)
3056 * If the needed support function is the same one cached
3057 * in the relation's partition key, copy the cached
3058 * FmgrInfo. Otherwise (i.e., when we have a cross-type
3059 * comparison), an actual lookup is required.
3061 if (cmpfn == context->partsupfunc[keyno].fn_oid)
3062 fmgr_info_copy(&context->stepcmpfuncs[stateidx],
3063 &context->partsupfunc[keyno],
3064 context->ppccontext);
3066 fmgr_info_cxt(cmpfn, &context->stepcmpfuncs[stateidx],
3067 context->ppccontext);
3070 values[keyno] = datum;
3080 * Point partsupfunc to the entry for the 0th key of this step; the
3081 * additional support functions, if any, follow consecutively.
3083 stateidx = PruneCxtStateIdx(context->partnatts, opstep->step.step_id, 0);
3084 partsupfunc = &context->stepcmpfuncs[stateidx];
3086 switch (context->strategy)
3088 case PARTITION_STRATEGY_HASH:
3089 return get_matching_hash_bounds(context,
3095 case PARTITION_STRATEGY_LIST:
3096 return get_matching_list_bounds(context,
3102 case PARTITION_STRATEGY_RANGE:
3103 return get_matching_range_bounds(context,
3110 elog(ERROR, "unexpected partition strategy: %d",
3111 (int) context->strategy);
3119 * perform_pruning_combine_step
3120 * Determines the indexes of datums obtained by combining those given
3121 * by the steps identified by cstep->source_stepids using the specified
3122 * combination method
3124 * Since cstep may refer to the result of earlier steps, we also receive
3125 * step_results here.
3127 static PruneStepResult *
3128 perform_pruning_combine_step(PartitionPruneContext *context,
3129 PartitionPruneStepCombine *cstep,
3130 PruneStepResult **step_results)
3133 PruneStepResult *result = NULL;
3137 * A combine step without any source steps is an indication to not perform
3138 * any partition pruning, we just return all partitions.
3140 result = (PruneStepResult *) palloc0(sizeof(PruneStepResult));
3141 if (list_length(cstep->source_stepids) == 0)
3143 PartitionBoundInfo boundinfo = context->boundinfo;
3145 result->bound_offsets = bms_add_range(NULL, 0, boundinfo->ndatums - 1);
3146 result->scan_default = partition_bound_has_default(boundinfo);
3147 result->scan_null = partition_bound_accepts_nulls(boundinfo);
3151 switch (cstep->combineOp)
3153 case PARTPRUNE_COMBINE_UNION:
3154 foreach(lc1, cstep->source_stepids)
3156 int step_id = lfirst_int(lc1);
3157 PruneStepResult *step_result;
3160 * step_results[step_id] must contain a valid result, which is
3161 * confirmed by the fact that cstep's step_id is greater than
3162 * step_id and the fact that results of the individual steps
3163 * are evaluated in sequence of their step_ids.
3165 if (step_id >= cstep->step.step_id)
3166 elog(ERROR, "invalid pruning combine step argument");
3167 step_result = step_results[step_id];
3168 Assert(step_result != NULL);
3170 /* Record any additional datum indexes from this step */
3171 result->bound_offsets = bms_add_members(result->bound_offsets,
3172 step_result->bound_offsets);
3174 /* Update whether to scan null and default partitions. */
3175 if (!result->scan_null)
3176 result->scan_null = step_result->scan_null;
3177 if (!result->scan_default)
3178 result->scan_default = step_result->scan_default;
3182 case PARTPRUNE_COMBINE_INTERSECT:
3184 foreach(lc1, cstep->source_stepids)
3186 int step_id = lfirst_int(lc1);
3187 PruneStepResult *step_result;
3189 if (step_id >= cstep->step.step_id)
3190 elog(ERROR, "invalid pruning combine step argument");
3191 step_result = step_results[step_id];
3192 Assert(step_result != NULL);
3196 /* Copy step's result the first time. */
3197 result->bound_offsets =
3198 bms_copy(step_result->bound_offsets);
3199 result->scan_null = step_result->scan_null;
3200 result->scan_default = step_result->scan_default;
3205 /* Record datum indexes common to both steps */
3206 result->bound_offsets =
3207 bms_int_members(result->bound_offsets,
3208 step_result->bound_offsets);
3210 /* Update whether to scan null and default partitions. */
3211 if (result->scan_null)
3212 result->scan_null = step_result->scan_null;
3213 if (result->scan_default)
3214 result->scan_default = step_result->scan_default;
3224 * match_boolean_partition_clause
3226 * Sets *outconst to a Const containing true or false value and returns true if
3227 * we're able to match the clause to the partition key as specially-shaped
3228 * Boolean clause. Returns false otherwise with *outconst set to NULL.
3231 match_boolean_partition_clause(Oid partopfamily, Expr *clause, Expr *partkey,
3238 if (!IsBooleanOpfamily(partopfamily))
3241 if (IsA(clause, BooleanTest))
3243 BooleanTest *btest = (BooleanTest *) clause;
3245 /* Only IS [NOT] TRUE/FALSE are any good to us */
3246 if (btest->booltesttype == IS_UNKNOWN ||
3247 btest->booltesttype == IS_NOT_UNKNOWN)
3250 leftop = btest->arg;
3251 if (IsA(leftop, RelabelType))
3252 leftop = ((RelabelType *) leftop)->arg;
3254 if (equal(leftop, partkey))
3255 *outconst = (btest->booltesttype == IS_TRUE ||
3256 btest->booltesttype == IS_NOT_FALSE)
3257 ? (Expr *) makeBoolConst(true, false)
3258 : (Expr *) makeBoolConst(false, false);
3265 bool is_not_clause = not_clause((Node *) clause);
3267 leftop = is_not_clause ? get_notclausearg(clause) : clause;
3269 if (IsA(leftop, RelabelType))
3270 leftop = ((RelabelType *) leftop)->arg;
3272 /* Compare to the partition key, and make up a clause ... */
3273 if (equal(leftop, partkey))
3274 *outconst = is_not_clause ?
3275 (Expr *) makeBoolConst(false, false) :
3276 (Expr *) makeBoolConst(true, false);
3277 else if (equal(negate_clause((Node *) leftop), partkey))
3278 *outconst = (Expr *) makeBoolConst(false, false);
3288 * partkey_datum_from_expr
3289 * Evaluate expression for potential partition pruning
3291 * Evaluate 'expr', whose ExprState is stateidx of the context exprstate
3292 * array; set *value and *isnull to the resulting Datum and nullflag.
3293 * Return true if evaluation was possible, otherwise false.
3295 * Note that the evaluated result may be in the per-tuple memory context of
3296 * context->planstate->ps_ExprContext, and we may have leaked other memory
3297 * there too. This memory must be recovered by resetting that ExprContext
3298 * after we're done with the pruning operation (see execPartition.c).
3301 partkey_datum_from_expr(PartitionPruneContext *context,
3302 Expr *expr, int stateidx,
3303 Datum *value, bool *isnull)
3305 if (IsA(expr, Const))
3307 /* We can always determine the value of a constant */
3308 Const *con = (Const *) expr;
3310 *value = con->constvalue;
3311 *isnull = con->constisnull;
3317 * When called from the executor we'll have a valid planstate so we
3318 * may be able to evaluate an expression which could not be folded to
3319 * a Const during planning. Since run-time pruning can occur both
3320 * during initialization of the executor or while it's running, we
3321 * must be careful here to evaluate expressions containing PARAM_EXEC
3322 * Params only when told it's OK.
3324 if (context->planstate &&
3325 (context->evalexecparams ||
3326 !context->exprhasexecparam[stateidx]))
3328 ExprState *exprstate;
3331 exprstate = context->exprstates[stateidx];
3332 ectx = context->planstate->ps_ExprContext;
3333 *value = ExecEvalExprSwitchContext(exprstate, ectx, isnull);
projects / postgresql / blob