| blob | 5ab46123671773e7408404451f02b50256727fae |
1 /*-------------------------------------------------------------------------
2 *
3 * partprune.c
4 * Support for partition pruning during query planning and execution
5 *
6 * This module implements partition pruning using the information contained in
7 * a table's partition descriptor, query clauses, and run-time parameters.
8 *
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.
14 *
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.
19 *
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
24 * combination method.
25 *
26 * See gen_partprune_steps_internal() for more details on step generation.
27 *
28 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
29 * Portions Copyright (c) 1994, Regents of the University of California
30 *
31 * IDENTIFICATION
32 * src/backend/partitioning/partprune.c
33 *
34 *-------------------------------------------------------------------------
35 */
60 /*
61 * Information about a clause matched with a partition key.
62 */
64 {
70 * partition key */
74 /*
75 * PartClauseMatchStatus
76 * Describes the result of match_clause_to_partition_key()
77 */
79 {
80 PARTCLAUSE_NOMATCH,
81 PARTCLAUSE_MATCH_CLAUSE,
82 PARTCLAUSE_MATCH_NULLNESS,
83 PARTCLAUSE_MATCH_STEPS,
84 PARTCLAUSE_MATCH_CONTRADICT,
85 PARTCLAUSE_UNSUPPORTED
88 /*
89 * PartClauseTarget
90 * Identifies which qual clauses we can use for generating pruning steps
91 */
93 {
96 PARTTARGET_EXEC /* want to prune during each plan node scan */
99 /*
100 * GeneratePruningStepsContext
101 * Information about the current state of generation of "pruning steps"
102 * for a given set of clauses
103 *
104 * gen_partprune_steps() initializes and returns an instance of this struct.
105 *
106 * Note that has_mutable_op, has_mutable_arg, and has_exec_param are set if
107 * we found any potentially-useful-for-pruning clause having those properties,
108 * whether or not we actually used the clause in the steps list. This
109 * definition allows us to skip the PARTTARGET_EXEC pass in some cases.
110 */
112 {
113 /* Copies of input arguments for gen_partprune_steps: */
116 /* Result data: */
120 * values, *other than* exec params */
123 /* Working state: */
127 /* The result of performing one PartitionPruneStep */
129 {
130 /*
131 * The offsets of bounds (in a table's boundinfo) whose partition is
132 * selected by the pruning step.
133 */
149 PartClauseTarget target,
158 PartitionPruneCombineOp combineOp);
161 static PartClauseMatchStatus match_clause_to_partition_key(GeneratePruningStepsContext *context,
166 StrategyNumber step_opstrategy,
169 Oid step_lastcmpfn,
174 StrategyNumber step_opstrategy,
177 Oid step_lastcmpfn,
210 /*
211 * make_partition_pruneinfo
212 * Builds a PartitionPruneInfo which can be used in the executor to allow
213 * additional partition pruning to take place. Returns NULL when
214 * partition pruning would be useless.
215 *
216 * 'parentrel' is the RelOptInfo for an appendrel, and 'subpaths' is the list
217 * of scan paths for its child rels.
218 * 'prunequal' is a list of potential pruning quals (i.e., restriction
219 * clauses that are applicable to the appendrel).
220 */
221 PartitionPruneInfo *
225 {
234 /*
235 * Scan the subpaths to see which ones are scans of partition child
236 * relations, and identify their parent partitioned rels. (Note: we must
237 * restrict the parent partitioned rels to be parentrel or children of
238 * parentrel, otherwise we couldn't translate prunequal to match.)
239 *
240 * Also construct a temporary array to map from partition-child-relation
241 * relid to the index in 'subpaths' of the scan plan for that partition.
242 * (Use of "subplan" rather than "subpath" is a bit of a misnomer, but
243 * we'll let it stand.) For convenience, we use 1-based indexes here, so
244 * that zero can represent an un-filled array entry.
245 */
251 {
255 /* We don't consider partitioned joins here */
257 {
261 /*
262 * Traverse up to the pathrel's topmost partitioned parent,
263 * collecting parent relids as we go; but stop if we reach
264 * parentrel. (Normally, a pathrel's topmost partitioned parent
265 * is either parentrel or a UNION ALL appendrel child of
266 * parentrel. But when handling partitionwise joins of
267 * multi-level partitioning trees, we can see an append path whose
268 * parentrel is an intermediate partitioned table.)
269 */
270 do
271 {
279 /* accept this level as an interesting parent */
286 {
287 /*
288 * Found some relevant parent partitions, which may or may not
289 * overlap with partition trees we already found. Add new
290 * information to the allpartrelids list.
291 */
293 /* Also record the subplan in relid_subplan_map[] */
294 /* No duplicates please */
297 }
298 }
299 i++;
300 }
302 /*
303 * We now build a PartitionedRelPruneInfo for each topmost partitioned rel
304 * (omitting any that turn out not to have useful pruning quals).
305 */
308 {
314 prunequal,
315 partrelids,
316 relid_subplan_map,
319 /* When pruning is possible, record the matched subplans */
321 {
324 allmatchedsubplans);
325 }
326 }
330 /*
331 * If none of the partition hierarchies had any useful run-time pruning
332 * quals, then we can just not bother with run-time pruning.
333 */
337 /* Else build the result data structure */
341 /*
342 * Some subplans may not belong to any of the identified partitioned rels.
343 * This can happen for UNION ALL queries which include a non-partitioned
344 * table, or when some of the hierarchies aren't run-time prunable. Build
345 * a bitmapset of the indexes of all such subplans, so that the executor
346 * can identify which subplans should never be pruned.
347 */
349 {
352 /* Create the complement of allmatchedsubplans */
357 }
358 else
362 }
364 /*
365 * add_part_relids
366 * Add new info to a list of Bitmapsets of partitioned relids.
367 *
368 * Within 'allpartrelids', there is one Bitmapset for each topmost parent
369 * partitioned rel. Each Bitmapset contains the RT indexes of the topmost
370 * parent as well as its relevant non-leaf child partitions. Since (by
371 * construction of the rangetable list) parent partitions must have lower
372 * RT indexes than their children, we can distinguish the topmost parent
373 * as being the lowest set bit in the Bitmapset.
374 *
375 * 'partrelids' contains the RT indexes of a parent partitioned rel, and
376 * possibly some non-leaf children, that are newly identified as parents of
377 * some subpath rel passed to make_partition_pruneinfo(). These are added
378 * to an appropriate member of 'allpartrelids'.
379 *
380 * Note that the list contains only RT indexes of partitioned tables that
381 * are parents of some scan-level relation appearing in the 'subpaths' that
382 * make_partition_pruneinfo() is dealing with. Also, "topmost" parents are
383 * not allowed to be higher than the 'parentrel' associated with the append
384 * path. In this way, we avoid expending cycles on partitioned rels that
385 * can't contribute useful pruning information for the problem at hand.
386 * (It is possible for 'parentrel' to be a child partitioned table, and it
387 * is also possible for scan-level relations to be child partitioned tables
388 * rather than leaf partitions. Hence we must construct this relation set
389 * with reference to the particular append path we're dealing with, rather
390 * than looking at the full partitioning structure represented in the
391 * RelOptInfos.)
392 */
395 {
396 Index targetpart;
399 /* We can easily get the lowest set bit this way: */
403 /* Look for a matching topmost parent */
405 {
410 {
411 /* Found a match, so add any new RT indexes to this hierarchy */
415 }
416 }
417 /* No match, so add the new partition hierarchy to the list */
419 }
421 /*
422 * make_partitionedrel_pruneinfo
423 * Build a List of PartitionedRelPruneInfos, one for each interesting
424 * partitioned rel in a partitioning hierarchy. These can be used in the
425 * executor to allow additional partition pruning to take place.
426 *
427 * parentrel: rel associated with the appendpath being considered
428 * prunequal: potential pruning quals, represented for parentrel
429 * partrelids: Set of RT indexes identifying relevant partitioned tables
430 * within a single partitioning hierarchy
431 * relid_subplan_map[]: maps child relation relids to subplan indexes
432 * matchedsubplans: on success, receives the set of subplan indexes which
433 * were matched to this partition hierarchy
434 *
435 * If we cannot find any useful run-time pruning steps, return NIL.
436 * However, on success, each rel identified in partrelids will have
437 * an element in the result list, even if some of them are useless.
438 */
445 {
455 /*
456 * Examine each partitioned rel, constructing a temporary array to map
457 * from planner relids to index of the partitioned rel, and building a
458 * PartitionedRelPruneInfo for each partitioned rel.
459 *
460 * In this phase we discover whether runtime pruning is needed at all; if
461 * not, we can avoid doing further work.
462 */
468 {
475 GeneratePruningStepsContext context;
477 /*
478 * Fill the mapping array.
479 *
480 * relid_subpart_map maps relid of a non-leaf partition to the index
481 * in the returned PartitionedRelPruneInfo list of the info for that
482 * partition. We use 1-based indexes here, so that zero can represent
483 * an un-filled array entry.
484 */
488 /*
489 * Translate pruning qual, if necessary, for this partition.
490 *
491 * The first item in the list is the target partitioned relation.
492 */
494 {
497 /*
498 * The prunequal is presented to us as a qual for 'parentrel'.
499 * Frequently this rel is the same as targetpart, so we can skip
500 * an adjust_appendrel_attrs step. But it might not be, and then
501 * we have to translate. We update the prunequal parameter here,
502 * because in later iterations of the loop for child partitions,
503 * we want to translate from parent to child variables.
504 */
506 {
513 prunequal,
514 nappinfos,
515 appinfos);
518 }
521 }
522 else
523 {
524 /*
525 * For sub-partitioned tables the columns may not be in the same
526 * order as the parent, so we must translate the prunequal to make
527 * it compatible with this relation.
528 */
532 subpart,
533 targetpart);
534 }
536 /*
537 * Convert pruning qual to pruning steps. We may need to do this
538 * twice, once to obtain executor startup pruning steps, and once for
539 * executor per-scan pruning steps. This first pass creates startup
540 * pruning steps and detects whether there's any possibly-useful quals
541 * that would require per-scan pruning.
542 */
547 {
548 /*
549 * This shouldn't happen as the planner should have detected this
550 * earlier. However, we do use additional quals from parameterized
551 * paths here. These do only compare Params to the partition key,
552 * so this shouldn't cause the discovery of any new qual
553 * contradictions that were not previously discovered as the Param
554 * values are unknown during planning. Anyway, we'd better do
555 * something sane here, so let's just disable run-time pruning.
556 */
558 }
560 /*
561 * If no mutable operators or expressions appear in usable pruning
562 * clauses, then there's no point in running startup pruning, because
563 * plan-time pruning should have pruned everything prunable.
564 */
567 else
570 /*
571 * If no exec Params appear in potentially-usable pruning clauses,
572 * then there's no point in even thinking about per-scan pruning.
573 */
575 {
576 /* ... OK, we'd better think about it */
581 {
582 /* As above, skip run-time pruning if anything fishy happens */
584 }
588 /*
589 * Detect which exec Params actually got used; the fact that some
590 * were in available clauses doesn't mean we actually used them.
591 * Skip per-scan pruning if there are none.
592 */
597 }
598 else
599 {
600 /* No exec Params anywhere, so forget about scan-time pruning */
603 }
608 /* Begin constructing the PartitionedRelPruneInfo for this rel */
614 /* Remaining fields will be filled in the next loop */
617 }
620 {
621 /* No run-time pruning required. */
624 }
626 /*
627 * Run-time pruning will be required, so initialize other information.
628 * That includes two maps -- one needed to convert partition indexes of
629 * leaf partitions to the indexes of their subplans in the subplan list,
630 * another needed to convert partition indexes of sub-partitioned
631 * partitions to the indexes of their PartitionedRelPruneInfo in the
632 * PartitionedRelPruneInfo list.
633 */
635 {
644 /*
645 * Construct the subplan and subpart maps for this partitioning level.
646 * Here we convert to zero-based indexes, with -1 for empty entries.
647 * Also construct a Bitmapset of all partitions that are present (that
648 * is, not pruned already).
649 */
659 {
670 {
673 /* Record finding this subplan */
675 }
678 }
680 /*
681 * Ensure there were no stray PartitionedRelPruneInfo generated for
682 * partitioned tables that we have no sub-paths or
683 * sub-PartitionedRelPruneInfo for.
684 */
687 /* Record the maps and other information. */
693 }
700 }
702 /*
703 * gen_partprune_steps
704 * Process 'clauses' (typically a rel's baserestrictinfo list of clauses)
705 * and create a list of "partition pruning steps".
706 *
707 * 'target' tells whether to generate pruning steps for planning (use
708 * immutable clauses only), or for executor startup (use any allowable
709 * clause except ones containing PARAM_EXEC Params), or for executor
710 * per-scan pruning (use any allowable clause).
711 *
712 * 'context' is an output argument that receives the steps list as well as
713 * some subsidiary flags; see the GeneratePruningStepsContext typedef.
714 */
715 static void
718 {
719 /* Initialize all output values to zero/false/NULL */
724 /*
725 * If this partitioned table is in turn a partition, and it shares any
726 * partition keys with its parent, then it's possible that the hierarchy
727 * allows the parent a narrower range of values than some of its
728 * partitions (particularly the default one). This is normally not
729 * useful, but it can be to prune the default partition.
730 */
732 {
733 /* Make a copy to avoid modifying the passed-in List */
735 }
737 /* Down into the rabbit-hole. */
739 }
741 /*
742 * prune_append_rel_partitions
743 * Process rel's baserestrictinfo and make use of quals which can be
744 * evaluated during query planning in order to determine the minimum set
745 * of partitions which must be scanned to satisfy these quals. Returns
746 * the matching partitions in the form of a Bitmapset containing the
747 * partitions' indexes in the rel's part_rels array.
748 *
749 * Callers must ensure that 'rel' is a partitioned table.
750 */
751 Bitmapset *
753 {
756 GeneratePruningStepsContext gcontext;
757 PartitionPruneContext context;
761 /* If there are no partitions, return the empty set */
765 /*
766 * If pruning is disabled or if there are no clauses to prune with, return
767 * all partitions.
768 */
772 /*
773 * Process clauses to extract pruning steps that are usable at plan time.
774 * If the clauses are found to be contradictory, we can return the empty
775 * set.
776 */
783 /* If there's nothing usable, return all partitions */
787 /* Set up PartitionPruneContext */
799 /* These are not valid when being called from the planner */
804 /* Actual pruning happens here. */
806 }
808 /*
809 * get_matching_partitions
810 * Determine partitions that survive partition pruning
811 *
812 * Note: context->exprcontext must be valid when the pruning_steps were
813 * generated with a target other than PARTTARGET_PLANNER.
814 *
815 * Returns a Bitmapset of the RelOptInfo->part_rels indexes of the surviving
816 * partitions.
817 */
818 Bitmapset *
820 {
823 i;
829 /* If there are no pruning steps then all partitions match. */
831 {
834 }
836 /*
837 * Allocate space for individual pruning steps to store its result. Each
838 * slot will hold a PruneStepResult after performing a given pruning step.
839 * Later steps may use the result of one or more earlier steps. The
840 * result of applying all pruning steps is the value contained in the slot
841 * of the last pruning step.
842 */
846 {
850 {
861 results);
867 }
868 }
870 /*
871 * At this point we know the offsets of all the datums whose corresponding
872 * partitions need to be in the result, including special null-accepting
873 * and default partitions. Collect the actual partition indexes now.
874 */
881 {
888 {
889 /*
890 * In range partitioning cases, if a partition index is -1 it
891 * means that the bound at the offset is the upper bound for a
892 * range not covered by any partition (other than a possible
893 * default partition). In hash partitioning, the same means no
894 * partition has been defined for the corresponding remainder
895 * value.
896 *
897 * In either case, the value is still part of the queried range of
898 * values, so mark to scan the default partition if one exists.
899 */
902 }
905 }
907 /* Add the null and/or default partition if needed and present. */
909 {
913 }
915 {
920 }
923 }
925 /*
926 * gen_partprune_steps_internal
927 * Processes 'clauses' to generate a List of partition pruning steps. We
928 * return NIL when no steps were generated.
929 *
930 * These partition pruning steps come in 2 forms; operator steps and combine
931 * steps.
932 *
933 * Operator steps (PartitionPruneStepOp) contain details of clauses that we
934 * determined that we can use for partition pruning. These contain details of
935 * the expression which is being compared to the partition key and the
936 * comparison function.
937 *
938 * Combine steps (PartitionPruneStepCombine) instruct the partition pruning
939 * code how it should produce a single set of partitions from multiple input
940 * operator and other combine steps. A PARTPRUNE_COMBINE_INTERSECT type
941 * combine step will merge its input steps to produce a result which only
942 * contains the partitions which are present in all of the input operator
943 * steps. A PARTPRUNE_COMBINE_UNION combine step will produce a result that
944 * has all of the partitions from each of the input operator steps.
945 *
946 * For BoolExpr clauses, each argument is processed recursively. Steps
947 * generated from processing an OR BoolExpr will be combined using
948 * PARTPRUNE_COMBINE_UNION. AND BoolExprs get combined using
949 * PARTPRUNE_COMBINE_INTERSECT.
950 *
951 * Otherwise, the list of clauses we receive we assume to be mutually ANDed.
952 * We generate all of the pruning steps we can based on these clauses and then
953 * at the end, if we have more than 1 step, we combine each step with a
954 * PARTPRUNE_COMBINE_INTERSECT combine step. Single steps are returned as-is.
955 *
956 * If we find clauses that are mutually contradictory, or contradictory with
957 * the partitioning constraint, or a pseudoconstant clause that contains
958 * false, we set context->contradictory to true and return NIL (that is, no
959 * pruning steps). Caller should consider all partitions as pruned in that
960 * case.
961 */
965 {
974 /*
975 * If this partitioned relation has a default partition and is itself a
976 * partition (as evidenced by partition_qual being not NIL), we first
977 * check if the clauses contradict the partition constraint. If they do,
978 * there's no need to generate any steps as it'd already be proven that no
979 * partitions need to be scanned.
980 *
981 * This is a measure of last resort only to be used because the default
982 * partition cannot be pruned using the steps generated from clauses that
983 * contradict the parent's partition constraint; regular pruning, which is
984 * cheaper, is sufficient when no default partition exists.
985 */
988 {
991 }
995 {
999 /* Look through RestrictInfo, if any */
1003 /* Constant-false-or-null is contradictory */
1007 {
1010 }
1012 /* Get the BoolExpr's out of the way. */
1014 {
1015 /*
1016 * Generate steps for arguments.
1017 *
1018 * While steps generated for the arguments themselves will be
1019 * added to context->steps during recursion and will be evaluated
1020 * independently, collect their step IDs to be stored in the
1021 * combine step we'll be creating.
1022 */
1024 {
1029 /*
1030 * We can share the outer context area with the recursive
1031 * call, but contradictory had better not be true yet.
1032 */
1035 /*
1036 * Get pruning step for each arg. If we get contradictory for
1037 * all args, it means the OR expression is false as a whole.
1038 */
1040 {
1048 /* Keep context->contradictory clear till we're done */
1052 {
1053 /* Just ignore self-contradictory arguments. */
1055 }
1056 else
1060 {
1061 /*
1062 * gen_partprune_steps_internal() always adds a single
1063 * combine step when it generates multiple steps, so
1064 * here we can just pay attention to the last one in
1065 * the list. If it just generated one, then the last
1066 * one in the list is still the one we want.
1067 */
1071 }
1072 else
1073 {
1076 /*
1077 * The arg didn't contain a clause matching this
1078 * partition key. We cannot prune using such an arg.
1079 * To indicate that to the pruning code, we must
1080 * construct a dummy PartitionPruneStepCombine whose
1081 * source_stepids is set to an empty List.
1082 */
1084 PARTPRUNE_COMBINE_UNION);
1086 }
1087 }
1089 /* If all the OR arms are contradictory, we can stop */
1091 {
1094 }
1097 {
1101 PARTPRUNE_COMBINE_UNION);
1103 }
1105 }
1107 {
1111 /*
1112 * args may itself contain clauses of arbitrary type, so just
1113 * recurse and later combine the component partitions sets
1114 * using a combine step.
1115 */
1118 /* If any AND arm is contradictory, we can stop immediately */
1122 /*
1123 * gen_partprune_steps_internal() always adds a single combine
1124 * step when it generates multiple steps, so here we can just
1125 * pay attention to the last one in the list. If it just
1126 * generated one, then the last one in the list is still the
1127 * one we want.
1128 */
1133 }
1135 /*
1136 * Fall-through for a NOT clause, which if it's a Boolean clause,
1137 * will be handled in match_clause_to_partition_key(). We
1138 * currently don't perform any pruning for more complex NOT
1139 * clauses.
1140 */
1141 }
1143 /*
1144 * See if we can match this clause to any of the partition keys.
1145 */
1147 {
1157 {
1161 /*
1162 * Since we only allow strict operators, check for any
1163 * contradicting IS NULL.
1164 */
1166 {
1169 }
1176 {
1177 /*
1178 * check for conflicting IS NOT NULL as well as
1179 * contradicting strict clauses
1180 */
1183 {
1186 }
1188 }
1189 else
1190 {
1191 /* check for conflicting IS NULL */
1193 {
1196 }
1198 }
1207 /* We've nothing more to do if a contradiction was found. */
1213 /*
1214 * Clause didn't match this key, but it might match the
1215 * next one.
1216 */
1220 /* This clause cannot be used for pruning. */
1222 }
1224 /* done; go check the next clause. */
1226 }
1227 }
1229 /*-----------
1230 * Now generate some (more) pruning steps. We have three strategies:
1231 *
1232 * 1) Generate pruning steps based on IS NULL clauses:
1233 * a) For list partitioning, null partition keys can only be found in
1234 * the designated null-accepting partition, so if there are IS NULL
1235 * clauses containing partition keys we should generate a pruning
1236 * step that gets rid of all partitions but that one. We can
1237 * disregard any OpExpr we may have found.
1238 * b) For range partitioning, only the default partition can contain
1239 * NULL values, so the same rationale applies.
1240 * c) For hash partitioning, we only apply this strategy if we have
1241 * IS NULL clauses for all the keys. Strategy 2 below will take
1242 * care of the case where some keys have OpExprs and others have
1243 * IS NULL clauses.
1244 *
1245 * 2) If not, generate steps based on OpExprs we have (if any).
1246 *
1247 * 3) If this doesn't work either, we may be able to generate steps to
1248 * prune just the null-accepting partition (if one exists), if we have
1249 * IS NOT NULL clauses for all partition keys.
1250 */
1256 {
1259 /* Strategy 1 */
1263 }
1265 {
1268 /* Strategy 2 */
1271 }
1273 {
1276 /* Strategy 3 */
1280 }
1282 /*
1283 * Finally, if there are multiple steps, since the 'clauses' are mutually
1284 * ANDed, add an INTERSECT step to combine the partition sets resulting
1285 * from them and append it to the result list.
1286 */
1288 {
1293 {
1297 }
1300 PARTPRUNE_COMBINE_INTERSECT);
1302 }
1305 }
1307 /*
1308 * gen_prune_step_op
1309 * Generate a pruning step for a specific operator
1310 *
1311 * The step is assigned a unique step identifier and added to context's 'steps'
1312 * list.
1313 */
1319 {
1324 /*
1325 * For clauses that contain an <> operator, set opstrategy to
1326 * InvalidStrategy to signal get_matching_list_bounds to do the right
1327 * thing.
1328 */
1338 }
1340 /*
1341 * gen_prune_step_combine
1342 * Generate a pruning step for a combination of several other steps
1343 *
1344 * The step is assigned a unique step identifier and added to context's
1345 * 'steps' list.
1346 */
1350 PartitionPruneCombineOp combineOp)
1351 {
1361 }
1363 /*
1364 * gen_prune_steps_from_opexps
1365 * Generate and return a list of PartitionPruneStepOp that are based on
1366 * OpExpr and BooleanTest clauses that have been matched to the partition
1367 * key.
1368 *
1369 * 'keyclauses' is an array of List pointers, indexed by the partition key's
1370 * index. Each List element in the array can contain clauses that match to
1371 * the corresponding partition key column. Partition key columns without any
1372 * matched clauses will have an empty List.
1373 *
1374 * Some partitioning strategies allow pruning to still occur when we only have
1375 * clauses for a prefix of the partition key columns, for example, RANGE
1376 * partitioning. Other strategies, such as HASH partitioning, require clauses
1377 * for all partition key columns.
1378 *
1379 * When we return multiple pruning steps here, it's up to the caller to add a
1380 * relevant "combine" step to combine the returned steps. This is not done
1381 * here as callers may wish to include additional pruning steps before
1382 * combining them all.
1383 */
1387 {
1398 {
1402 /*
1403 * For range partitioning, if we have no clauses for the current key,
1404 * we can't consider any later keys either, so we can stop here.
1405 */
1410 /*
1411 * For hash partitioning, if a column doesn't have the necessary
1412 * equality clause, there should be an IS NULL clause, otherwise
1413 * pruning is not possible.
1414 */
1420 {
1422 Oid lefttype,
1423 righttype;
1425 /* Look up the operator's btree/hash strategy number. */
1435 {
1441 /*
1442 * We can't consider subsequent partition keys if the
1443 * clause for the current key contains a non-inclusive
1444 * operator.
1445 */
1462 }
1463 }
1465 /*
1466 * If we've decided that clauses for subsequent partition keys
1467 * wouldn't be useful for pruning, don't search any further.
1468 */
1471 }
1473 /*
1474 * Now, we have divided clauses according to their operator strategies.
1475 * Check for each strategy if we can generate pruning step(s) by
1476 * collecting a list of expressions whose values will constitute a vector
1477 * that can be used as a lookup key by a partition bound searching
1478 * function.
1479 */
1481 {
1484 {
1490 /*
1491 * For each clause under consideration for a given strategy,
1492 * we collect expressions from clauses for earlier keys, whose
1493 * operator strategy is inclusive, into a list called
1494 * 'prefix'. By appending the clause's own expression to the
1495 * 'prefix', we'll generate one step using the so generated
1496 * vector and assign the current strategy to it. Actually,
1497 * 'prefix' might contain multiple clauses for the same key,
1498 * in which case, we must generate steps for various
1499 * combinations of expressions of different keys, which
1500 * get_steps_using_prefix takes care of for us.
1501 */
1503 {
1505 {
1517 /*
1518 * If this is a clause for the first partition key,
1519 * there are no preceding expressions; generate a
1520 * pruning step without a prefix.
1521 *
1522 * Note that we pass NULL for step_nullkeys, because
1523 * we don't search list/range partition bounds where
1524 * some keys are NULL.
1525 */
1527 {
1534 NULL,
1535 NIL);
1538 }
1544 /*
1545 * We arrange clauses into prefix in ascending order
1546 * of their partition key numbers.
1547 */
1549 {
1552 /*
1553 * Expressions from = clauses can always be in the
1554 * prefix, provided they're from an earlier key.
1555 */
1557 {
1561 {
1564 }
1565 else
1566 {
1569 }
1570 }
1573 /*
1574 * If we're generating steps for </<= strategy, we
1575 * can add other <= clauses to the prefix,
1576 * provided they're from an earlier key.
1577 */
1580 {
1582 {
1586 {
1589 }
1590 else
1591 {
1594 }
1595 }
1597 }
1599 /*
1600 * If we're generating steps for >/>= strategy, we
1601 * can add other >= clauses to the prefix,
1602 * provided they're from an earlier key.
1603 */
1606 {
1608 {
1612 {
1615 }
1616 else
1617 {
1620 }
1621 }
1623 }
1625 /*
1626 * If this key has no clauses, prefix is not valid
1627 * anymore.
1628 */
1630 {
1633 }
1634 }
1636 /*
1637 * If prefix_valid, generate PartitionPruneStepOps.
1638 * Otherwise, we would not find clauses for a valid
1639 * subset of the partition keys anymore for the
1640 * strategy; give up on generating partition pruning
1641 * steps further for the strategy.
1642 *
1643 * As mentioned above, if 'prefix' contains multiple
1644 * expressions for the same key, the following will
1645 * generate multiple steps, one for each combination
1646 * of the expressions for different keys.
1647 *
1648 * Note that we pass NULL for step_nullkeys, because
1649 * we don't search list/range partition bounds where
1650 * some keys are NULL.
1651 */
1653 {
1660 NULL,
1661 prefix);
1663 }
1664 else
1666 }
1667 }
1669 }
1672 {
1675 /* For hash partitioning, we have just the = strategy. */
1677 {
1684 /*
1685 * Locate the clause for the greatest column. This may
1686 * not belong to the last partition key, but it is the
1687 * clause belonging to the last partition key we found a
1688 * clause for above.
1689 */
1692 /*
1693 * There might be multiple clauses which matched to that
1694 * partition key; find the first such clause. While at
1695 * it, add all the clauses before that one to 'prefix'.
1696 */
1699 {
1704 }
1706 /*
1707 * For each clause for the "last" column, after appending
1708 * the clause's own expression to the 'prefix', we'll
1709 * generate one step using the so generated vector and
1710 * assign = as its strategy. Actually, 'prefix' might
1711 * contain multiple clauses for the same key, in which
1712 * case, we must generate steps for various combinations
1713 * of expressions of different keys, which
1714 * get_steps_using_prefix will take care of for us.
1715 */
1717 {
1720 /*
1721 * Note that we pass nullkeys for step_nullkeys,
1722 * because we need to tell hash partition bound search
1723 * function which of the keys we found IS NULL clauses
1724 * for.
1725 */
1727 pc_steps =
1729 HTEqualStrategyNumber,
1734 nullkeys,
1735 prefix);
1737 }
1738 }
1740 }
1746 }
1749 }
1751 /*
1752 * If the partition key has a collation, then the clause must have the same
1753 * input collation. If the partition key is non-collatable, we assume the
1754 * collation doesn't matter, because while collation wasn't considered when
1755 * performing partitioning, the clause still may have a collation assigned
1756 * due to the other input being of a collatable type.
1757 *
1758 * See also IndexCollMatchesExprColl.
1759 */
1760 #define PartCollMatchesExprColl(partcoll, exprcoll) \
1761 ((partcoll) == InvalidOid || (partcoll) == (exprcoll))
1763 /*
1764 * match_clause_to_partition_key
1765 * Attempt to match the given 'clause' with the specified partition key.
1766 *
1767 * Return value is:
1768 * * PARTCLAUSE_NOMATCH if the clause doesn't match this partition key (but
1769 * caller should keep trying, because it might match a subsequent key).
1770 * Output arguments: none set.
1771 *
1772 * * PARTCLAUSE_MATCH_CLAUSE if there is a match.
1773 * Output arguments: *pc is set to a PartClauseInfo constructed for the
1774 * matched clause.
1775 *
1776 * * PARTCLAUSE_MATCH_NULLNESS if there is a match, and the matched clause was
1777 * either a "a IS NULL" or "a IS NOT NULL" clause.
1778 * Output arguments: *clause_is_not_null is set to false in the former case
1779 * true otherwise.
1780 *
1781 * * PARTCLAUSE_MATCH_STEPS if there is a match.
1782 * Output arguments: *clause_steps is set to the list of recursively
1783 * generated steps for the clause.
1784 *
1785 * * PARTCLAUSE_MATCH_CONTRADICT if the clause is self-contradictory, ie
1786 * it provably returns FALSE or NULL.
1787 * Output arguments: none set.
1788 *
1789 * * PARTCLAUSE_UNSUPPORTED if the clause doesn't match this partition key
1790 * and couldn't possibly match any other one either, due to its form or
1791 * properties (such as containing a volatile function).
1792 * Output arguments: none set.
1793 */
1794 static PartClauseMatchStatus
1799 {
1800 PartClauseMatchStatus boolmatchstatus;
1806 /*
1807 * Recognize specially shaped clauses that match a Boolean partition key.
1808 */
1813 {
1818 /* Do pruning with the Boolean equality operator. */
1822 /* We know that expr is of Boolean type. */
1829 }
1832 {
1836 Oid opno,
1837 op_lefttype,
1838 op_righttype,
1840 Oid cmpfn;
1853 /* check if the clause matches this partition key */
1857 {
1858 /*
1859 * It's only useful if we can commute the operator to put the
1860 * partkey on the left. If we can't, the clause can be deemed
1861 * UNSUPPORTED. Even if its leftop matches some later partkey, we
1862 * now know it has Vars on the right, so it's no use.
1863 */
1868 }
1869 else
1870 /* clause does not match this partition key, but perhaps next. */
1873 /*
1874 * Partition key match also requires collation match. There may be
1875 * multiple partkeys with the same expression but different
1876 * collations, so failure is NOMATCH.
1877 */
1881 /*
1882 * See if the operator is relevant to the partitioning opfamily.
1883 *
1884 * Normally we only care about operators that are listed as being part
1885 * of the partitioning operator family. But there is one exception:
1886 * the not-equals operators are not listed in any operator family
1887 * whatsoever, but their negators (equality) are. We can use one of
1888 * those if we find it, but only for list partitioning.
1889 *
1890 * Note: we report NOMATCH on failure, in case a later partkey has the
1891 * same expression but different opfamily. That's unlikely, but not
1892 * much more so than duplicate expressions with different collations.
1893 */
1895 {
1899 }
1900 else
1901 {
1905 /* See if the negator is equality */
1908 {
1914 }
1916 /* Nope, it's not <> either. */
1919 }
1921 /*
1922 * Only allow strict operators. This will guarantee nulls are
1923 * filtered. (This test is likely useless, since btree and hash
1924 * comparison operators are generally strict.)
1925 */
1929 /*
1930 * OK, we have a match to the partition key and a suitable operator.
1931 * Examine the other argument to see if it's usable for pruning.
1932 *
1933 * In most of these cases, we can return UNSUPPORTED because the same
1934 * failure would occur no matter which partkey it's matched to. (In
1935 * particular, now that we've successfully matched one side of the
1936 * opclause to a partkey, there is no chance that matching the other
1937 * side to another partkey will produce a usable result, since that'd
1938 * mean there are Vars on both sides.)
1939 *
1940 * Also, if we reject an argument for a target-dependent reason, set
1941 * appropriate fields of *context to report that. We postpone these
1942 * tests until after matching the partkey and the operator, so as to
1943 * reduce the odds of setting the context fields for clauses that do
1944 * not end up contributing to pruning steps.
1945 *
1946 * First, check for non-Const argument. (We assume that any immutable
1947 * subexpression will have been folded to a Const already.)
1948 */
1950 {
1953 /*
1954 * When pruning in the planner, we only support pruning using
1955 * comparisons to constants. We cannot prune on the basis of
1956 * anything that's not immutable. (Note that has_mutable_arg and
1957 * has_exec_param do not get set for this target value.)
1958 */
1962 /*
1963 * We can never prune using an expression that contains Vars.
1964 */
1968 /*
1969 * And we must reject anything containing a volatile function.
1970 * Stable functions are OK though.
1971 */
1975 /*
1976 * See if there are any exec Params. If so, we can only use this
1977 * expression during per-scan pruning.
1978 */
1981 {
1985 }
1986 else
1987 {
1988 /* It's potentially usable, but mutable */
1990 }
1991 }
1993 /*
1994 * Check whether the comparison operator itself is immutable. (We
1995 * assume anything that's in a btree or hash opclass is at least
1996 * stable, but we need to check for immutability.)
1997 */
1999 {
2002 /*
2003 * When pruning in the planner, we cannot prune with mutable
2004 * operators.
2005 */
2008 }
2010 /*
2011 * Now find the procedure to use, based on the types. If the clause's
2012 * other argument is of the same type as the partitioning opclass's
2013 * declared input type, we can use the procedure cached in
2014 * PartitionKey. If not, search for a cross-type one in the same
2015 * opfamily; if one doesn't exist, report no match.
2016 */
2019 else
2020 {
2022 {
2023 /*
2024 * For range and list partitioning, we need the ordering
2025 * procedure with lefttype being the partition key's type,
2026 * and righttype the clause's operator's right type.
2027 */
2030 cmpfn =
2036 /*
2037 * For hash partitioning, we need the hashing procedure
2038 * for the clause's type.
2039 */
2041 cmpfn =
2044 HASHEXTENDED_PROC);
2052 }
2056 }
2058 /*
2059 * Build the clause, passing the negator if applicable.
2060 */
2064 {
2069 }
2070 else
2071 {
2075 }
2082 }
2084 {
2097 /* check if the LHS matches this partition key */
2102 /*
2103 * See if the operator is relevant to the partitioning opfamily.
2104 *
2105 * In case of NOT IN (..), we get a '<>', which we handle if list
2106 * partitioning is in use and we're able to confirm that it's negator
2107 * is a btree equality operator belonging to the partitioning operator
2108 * family. As above, report NOMATCH for non-matching operator.
2109 */
2111 {
2112 Oid negator;
2119 {
2121 Oid lefttype,
2122 righttype;
2129 }
2130 else
2132 }
2134 /*
2135 * Only allow strict operators. This will guarantee nulls are
2136 * filtered. (This test is likely useless, since btree and hash
2137 * comparison operators are generally strict.)
2138 */
2142 /*
2143 * OK, we have a match to the partition key and a suitable operator.
2144 * Examine the array argument to see if it's usable for pruning. This
2145 * is identical to the logic for a plain OpExpr.
2146 */
2148 {
2151 /*
2152 * When pruning in the planner, we only support pruning using
2153 * comparisons to constants. We cannot prune on the basis of
2154 * anything that's not immutable. (Note that has_mutable_arg and
2155 * has_exec_param do not get set for this target value.)
2156 */
2160 /*
2161 * We can never prune using an expression that contains Vars.
2162 */
2166 /*
2167 * And we must reject anything containing a volatile function.
2168 * Stable functions are OK though.
2169 */
2173 /*
2174 * See if there are any exec Params. If so, we can only use this
2175 * expression during per-scan pruning.
2176 */
2179 {
2183 }
2184 else
2185 {
2186 /* It's potentially usable, but mutable */
2188 }
2189 }
2191 /*
2192 * Check whether the comparison operator itself is immutable. (We
2193 * assume anything that's in a btree or hash opclass is at least
2194 * stable, but we need to check for immutability.)
2195 */
2197 {
2200 /*
2201 * When pruning in the planner, we cannot prune with mutable
2202 * operators.
2203 */
2206 }
2208 /*
2209 * Examine the contents of the array argument.
2210 */
2213 {
2214 /*
2215 * For a constant array, convert the elements to a list of Const
2216 * nodes, one for each array element (excepting nulls).
2217 */
2220 int16 elemlen;
2226 i;
2228 /* If the array itself is null, the saop returns null */
2241 {
2244 /*
2245 * A null array element must lead to a null comparison result,
2246 * since saop_op is known strict. We can ignore it in the
2247 * useOr case, but otherwise it implies self-contradiction.
2248 */
2250 {
2254 }
2260 }
2261 }
2263 {
2266 /*
2267 * For a nested ArrayExpr, we don't know how to get the actual
2268 * scalar values out into a flat list, so we give up doing
2269 * anything with this ScalarArrayOpExpr.
2270 */
2274 /*
2275 * Otherwise, we can just use the list of element values.
2276 */
2278 }
2279 else
2280 {
2281 /* Give up on any other clause types. */
2283 }
2285 /*
2286 * Now generate a list of clauses, one for each array element, of the
2287 * form leftop saop_op elem_expr
2288 */
2291 {
2299 }
2301 /*
2302 * If we have an ANY clause and multiple elements, now turn the list
2303 * of clauses into an OR expression.
2304 */
2308 /* Finally, generate steps */
2315 }
2317 {
2324 /* Does arg match with this partition key column? */
2331 }
2333 /*
2334 * If we get here then the return value depends on the result of the
2335 * match_boolean_partition_clause call above. If the call returned
2336 * PARTCLAUSE_UNSUPPORTED then we're either not dealing with a bool qual
2337 * or the bool qual is not suitable for pruning. Since the qual didn't
2338 * match up to any of the other qual types supported here, then trying to
2339 * match it against any other partition key is a waste of time, so just
2340 * return PARTCLAUSE_UNSUPPORTED. If the qual just couldn't be matched to
2341 * this partition key, then it may match another, so return
2342 * PARTCLAUSE_NOMATCH. The only other value that
2343 * match_boolean_partition_clause can return is PARTCLAUSE_MATCH_CLAUSE,
2344 * and since that value was already dealt with above, then we can just
2345 * return boolmatchstatus.
2346 */
2348 }
2350 /*
2351 * get_steps_using_prefix
2352 * Generate list of PartitionPruneStepOp steps each consisting of given
2353 * opstrategy
2354 *
2355 * To generate steps, step_lastexpr and step_lastcmpfn are appended to
2356 * expressions and cmpfns, respectively, extracted from the clauses in
2357 * 'prefix'. Actually, since 'prefix' may contain multiple clauses for the
2358 * same partition key column, we must generate steps for various combinations
2359 * of the clauses of different keys.
2360 *
2361 * For list/range partitioning, callers must ensure that step_nullkeys is
2362 * NULL, and that prefix contains at least one clause for each of the
2363 * partition keys earlier than one specified in step_lastkeyno if it's
2364 * greater than zero. For hash partitioning, step_nullkeys is allowed to be
2365 * non-NULL, but they must ensure that prefix contains at least one clause
2366 * for each of the partition keys other than those specified in step_nullkeys
2367 * and step_lastkeyno.
2368 *
2369 * For both cases, callers must also ensure that clauses in prefix are sorted
2370 * in ascending order of their partition key numbers.
2371 */
2374 StrategyNumber step_opstrategy,
2377 Oid step_lastcmpfn,
2381 {
2385 /* Quick exit if there are no values to prefix with. */
2387 {
2391 step_opstrategy,
2392 step_op_is_ne,
2395 step_nullkeys);
2397 }
2399 /* Recurse to generate steps for various combinations. */
2401 step_opstrategy,
2402 step_op_is_ne,
2403 step_lastexpr,
2404 step_lastcmpfn,
2405 step_lastkeyno,
2406 step_nullkeys,
2407 prefix,
2410 }
2412 /*
2413 * get_steps_using_prefix_recurse
2414 * Recursively generate combinations of clauses for different partition
2415 * keys and start generating steps upon reaching clauses for the greatest
2416 * column that is less than the one for which we're currently generating
2417 * steps (that is, step_lastkeyno)
2418 *
2419 * 'prefix' is the list of PartClauseInfos.
2420 * 'start' is where we should start iterating for the current invocation.
2421 * 'step_exprs' and 'step_cmpfns' each contains the expressions and cmpfns
2422 * we've generated so far from the clauses for the previous part keys.
2423 */
2426 StrategyNumber step_opstrategy,
2429 Oid step_lastcmpfn,
2436 {
2441 /* Actually, recursion would be limited by PARTITION_MAX_KEYS. */
2444 /* Check if we need to recurse. */
2448 {
2452 /*
2453 * For each clause with cur_keyno, add its expr and cmpfn to
2454 * step_exprs and step_cmpfns, respectively, and recurse after setting
2455 * next_start to the ListCell of the first clause for the next
2456 * partition key.
2457 */
2459 {
2464 }
2468 {
2475 {
2476 /* Leave the original step_exprs unmodified. */
2480 /* Leave the original step_cmpfns unmodified. */
2483 }
2484 else
2485 {
2488 }
2491 step_opstrategy,
2492 step_op_is_ne,
2493 step_lastexpr,
2494 step_lastcmpfn,
2495 step_lastkeyno,
2496 step_nullkeys,
2497 prefix,
2498 next_start,
2499 step_exprs1,
2500 step_cmpfns1);
2505 }
2506 }
2507 else
2508 {
2509 /*
2510 * End the current recursion cycle and start generating steps, one for
2511 * each clause with cur_keyno, which is all clauses from here onward
2512 * till the end of the list. Note that for hash partitioning,
2513 * step_nullkeys is allowed to be non-empty, in which case step_exprs
2514 * would only contain expressions for the earlier partition keys that
2515 * are not specified in step_nullkeys.
2516 */
2520 /*
2521 * Note also that for hash partitioning, each partition key should
2522 * have either equality clauses or an IS NULL clause, so if a
2523 * partition key doesn't have an expression, it would be specified in
2524 * step_nullkeys.
2525 */
2531 {
2539 /* Leave the original step_exprs unmodified. */
2544 /* Leave the original step_cmpfns unmodified. */
2552 step_nullkeys);
2554 }
2555 }
2558 }
2560 /*
2561 * get_matching_hash_bounds
2562 * Determine offset of the hash bound matching the specified values,
2563 * considering that all the non-null values come from clauses containing
2564 * a compatible hash equality operator and any keys that are null come
2565 * from an IS NULL clause.
2566 *
2567 * Generally this function will return a single matching bound offset,
2568 * although if a partition has not been setup for a given modulus then we may
2569 * return no matches. If the number of clauses found don't cover the entire
2570 * partition key, then we'll need to return all offsets.
2571 *
2572 * 'opstrategy' if non-zero must be HTEqualStrategyNumber.
2573 *
2574 * 'values' contains Datums indexed by the partition key to use for pruning.
2575 *
2576 * 'nvalues', the number of Datums in the 'values' array.
2577 *
2578 * 'partsupfunc' contains partition hashing functions that can produce correct
2579 * hash for the type of the values contained in 'values'.
2580 *
2581 * 'nullkeys' is the set of partition keys that are null.
2582 */
2587 {
2594 uint64 rowHash;
2600 /*
2601 * For hash partitioning we can only perform pruning based on equality
2602 * clauses to the partition key or IS NULL clauses. We also can only
2603 * prune if we got values for all keys.
2604 */
2606 {
2607 /*
2608 * If there are any values, they must have come from clauses
2609 * containing an equality operator compatible with hash partitioning.
2610 */
2623 }
2624 else
2625 {
2626 /* Report all valid offsets into the boundinfo->indexes array. */
2629 }
2631 /*
2632 * There is neither a special hash null partition or the default hash
2633 * partition.
2634 */
2638 }
2640 /*
2641 * get_matching_list_bounds
2642 * Determine the offsets of list bounds matching the specified value,
2643 * according to the semantics of the given operator strategy
2644 *
2645 * scan_default will be set in the returned struct, if the default partition
2646 * needs to be scanned, provided one exists at all. scan_null will be set if
2647 * the special null-accepting partition needs to be scanned.
2648 *
2649 * 'opstrategy' if non-zero must be a btree strategy number.
2650 *
2651 * 'value' contains the value to use for pruning.
2652 *
2653 * 'nvalues', if non-zero, should be exactly 1, because of list partitioning.
2654 *
2655 * 'partsupfunc' contains the list partitioning comparison function to be used
2656 * to perform partition_list_bsearch
2657 *
2658 * 'nullkeys' is the set of partition keys that are null.
2659 */
2664 {
2668 minoff,
2669 maxoff;
2680 {
2681 /*
2682 * Nulls may exist in only one partition - the partition whose
2683 * accepted set of values includes null or the default partition if
2684 * the former doesn't exist.
2685 */
2688 else
2691 }
2693 /*
2694 * If there are no datums to compare keys with, but there are partitions,
2695 * just return the default partition if one exists.
2696 */
2698 {
2701 }
2706 /*
2707 * If there are no values to compare with the datums in boundinfo, it
2708 * means the caller asked for partitions for all non-null datums. Add
2709 * indexes of *all* partitions, including the default if any.
2710 */
2712 {
2718 }
2720 /* Special case handling of values coming from a <> operator clause. */
2722 {
2723 /*
2724 * First match to all bounds. We'll remove any matching datums below.
2725 */
2733 {
2735 /* We have a match. Remove from the result. */
2738 off);
2739 }
2741 /* Always include the default partition if any. */
2745 }
2747 /*
2748 * With range queries, always include the default list partition, because
2749 * list partitions divide the key space in a discontinuous manner, not all
2750 * values in the given range will have a partition assigned. This may not
2751 * technically be true for some data types (e.g. integer types), however,
2752 * we currently lack any sort of infrastructure to provide us with proofs
2753 * that would allow us to do anything smarter here.
2754 */
2759 {
2762 partcollation,
2766 {
2769 }
2770 else
2776 /* fall through */
2779 partcollation,
2783 {
2784 /* We don't want the matched datum to be in the result. */
2786 off++;
2787 }
2788 else
2789 {
2790 /*
2791 * This case means all partition bounds are greater, which in
2792 * turn means that all partitions satisfy this key.
2793 */
2795 }
2797 /*
2798 * off is greater than the numbers of datums we have partitions
2799 * for. The only possible partition that could contain a match is
2800 * the default partition, but we must've set context->scan_default
2801 * above anyway if one exists.
2802 */
2811 /* fall through */
2814 partcollation,
2818 off--;
2820 /*
2821 * off is smaller than the datums of all non-default partitions.
2822 * The only possible partition that could contain a match is the
2823 * default partition, but we must've set context->scan_default
2824 * above anyway if one exists.
2825 */
2835 }
2840 }
2843 /*
2844 * get_matching_range_bounds
2845 * Determine the offsets of range bounds matching the specified values,
2846 * according to the semantics of the given operator strategy
2847 *
2848 * Each datum whose offset is in result is to be treated as the upper bound of
2849 * the partition that will contain the desired values.
2850 *
2851 * scan_default is set in the returned struct if a default partition exists
2852 * and we're absolutely certain that it needs to be scanned. We do *not* set
2853 * it just because values match portions of the key space uncovered by
2854 * partitions other than default (space which we normally assume to belong to
2855 * the default partition): the final set of bounds obtained after combining
2856 * multiple pruning steps might exclude it, so we infer its inclusion
2857 * elsewhere.
2858 *
2859 * 'opstrategy' if non-zero must be a btree strategy number.
2860 *
2861 * 'values' contains Datums indexed by the partition key to use for pruning.
2862 *
2863 * 'nvalues', number of Datums in 'values' array. Must be <= context->partnatts.
2864 *
2865 * 'partsupfunc' contains the range partitioning comparison functions to be
2866 * used to perform partition_range_datum_bsearch or partition_rbound_datum_cmp
2867 * using.
2868 *
2869 * 'nullkeys' is the set of partition keys that are null.
2870 */
2875 {
2882 minoff,
2883 maxoff;
2892 /*
2893 * If there are no datums to compare keys with, or if we got an IS NULL
2894 * clause just return the default partition, if it exists.
2895 */
2897 {
2900 }
2905 /*
2906 * If there are no values to compare with the datums in boundinfo, it
2907 * means the caller asked for partitions for all non-null datums. Add
2908 * indexes of *all* partitions, including the default partition if one
2909 * exists.
2910 */
2912 {
2913 /* ignore key space not covered by any partitions */
2915 minoff++;
2917 maxoff--;
2925 }
2927 /*
2928 * If the query does not constrain all key columns, we'll need to scan the
2929 * default partition, if any.
2930 */
2935 {
2937 /* Look for the smallest bound that is = lookup value. */
2939 partcollation,
2940 boundinfo,
2945 {
2947 {
2948 /* There can only be zero or one matching partition. */
2951 }
2952 else
2953 {
2956 /*
2957 * Since the lookup value contains only a prefix of keys,
2958 * we must find other bounds that may also match the
2959 * prefix. partition_range_datum_bsearch() returns the
2960 * offset of one of them, find others by checking adjacent
2961 * bounds.
2962 */
2964 /*
2965 * First find greatest bound that's smaller than the
2966 * lookup value.
2967 */
2969 {
2970 int32 cmpval;
2972 cmpval =
2974 partcollation,
2980 off--;
2981 }
2985 partcollation,
2990 /*
2991 * We can treat 'off' as the offset of the smallest bound
2992 * to be included in the result, if we know it is the
2993 * upper bound of the partition in which the lookup value
2994 * could possibly exist. One case it couldn't is if the
2995 * bound, or precisely the matched portion of its prefix,
2996 * is not inclusive.
2997 */
2999 PARTITION_RANGE_DATUM_MINVALUE)
3000 off++;
3004 /*
3005 * Now find smallest bound that's greater than the lookup
3006 * value.
3007 */
3010 {
3011 int32 cmpval;
3014 partcollation,
3020 off++;
3021 }
3025 partcollation,
3030 /*
3031 * off + 1, then would be the offset of the greatest bound
3032 * to be included in the result.
3033 */
3035 }
3039 }
3040 else
3041 {
3042 /*
3043 * The lookup value falls in the range between some bounds in
3044 * boundinfo. 'off' would be the offset of the greatest bound
3045 * that is <= lookup value, so add off + 1 to the result
3046 * instead as the offset of the upper bound of the only
3047 * partition that may contain the lookup value. If 'off' is
3048 * -1 indicating that all bounds are greater, then we simply
3049 * end up adding the first bound's offset, that is, 0.
3050 */
3052 }
3058 /* fall through */
3061 /*
3062 * Look for the smallest bound that is > or >= lookup value and
3063 * set minoff to its offset.
3064 */
3066 partcollation,
3067 boundinfo,
3071 {
3072 /*
3073 * All bounds are greater than the lookup value, so include
3074 * all of them in the result.
3075 */
3077 }
3078 else
3079 {
3081 {
3082 /*
3083 * Since the lookup value contains only a prefix of keys,
3084 * we must find other bounds that may also match the
3085 * prefix. partition_range_datum_bsearch() returns the
3086 * offset of one of them, find others by checking adjacent
3087 * bounds.
3088 *
3089 * Based on whether the lookup values are inclusive or
3090 * not, we must either include the indexes of all such
3091 * bounds in the result (that is, set minoff to the index
3092 * of smallest such bound) or find the smallest one that's
3093 * greater than the lookup values and set minoff to that.
3094 */
3096 {
3097 int32 cmpval;
3101 cmpval =
3103 partcollation,
3111 }
3115 partcollation,
3121 }
3122 else
3123 {
3125 /*
3126 * lookup value falls in the range between some bounds in
3127 * boundinfo. off would be the offset of the greatest
3128 * bound that is <= lookup value, so add off + 1 to the
3129 * result instead as the offset of the upper bound of the
3130 * smallest partition that may contain the lookup value.
3131 */
3133 }
3134 }
3139 /* fall through */
3142 /*
3143 * Look for the greatest bound that is < or <= lookup value and
3144 * set maxoff to its offset.
3145 */
3147 partcollation,
3148 boundinfo,
3152 {
3153 /*
3154 * See the comment above.
3155 */
3157 {
3159 {
3160 int32 cmpval;
3165 partcollation,
3173 }
3177 partcollation,
3183 }
3185 /*
3186 * The lookup value falls in the range between some bounds in
3187 * boundinfo. 'off' would be the offset of the greatest bound
3188 * that is <= lookup value, so add off + 1 to the result
3189 * instead as the offset of the upper bound of the greatest
3190 * partition that may contain lookup value. If the lookup
3191 * value had exactly matched the bound, but it isn't
3192 * inclusive, no need add the adjacent partition.
3193 */
3196 else
3198 }
3199 else
3200 {
3201 /*
3202 * 'off' is -1 indicating that all bounds are greater, so just
3203 * set the first bound's offset as maxoff.
3204 */
3206 }
3212 }
3217 /*
3218 * If the smallest partition to return has MINVALUE (negative infinity) as
3219 * its lower bound, increment it to point to the next finite bound
3220 * (supposedly its upper bound), so that we don't inadvertently end up
3221 * scanning the default partition.
3222 */
3224 {
3228 PARTITION_RANGE_DATUM_MINVALUE)
3229 {
3230 minoff++;
3232 }
3233 }
3235 /*
3236 * If the previous greatest partition has MAXVALUE (positive infinity) as
3237 * its upper bound (something only possible to do with multi-column range
3238 * partitioning), we scan switch to it as the greatest partition to
3239 * return. Again, so that we don't inadvertently end up scanning the
3240 * default partition.
3241 */
3243 {
3247 PARTITION_RANGE_DATUM_MAXVALUE)
3248 {
3249 maxoff--;
3251 }
3252 }
3259 }
3261 /*
3262 * pull_exec_paramids
3263 * Returns a Bitmapset containing the paramids of all Params with
3264 * paramkind = PARAM_EXEC in 'expr'.
3265 */
3268 {
3274 }
3276 static bool
3278 {
3282 {
3288 }
3291 }
3293 /*
3294 * get_partkey_exec_paramids
3295 * Loop through given pruning steps and find out which exec Params
3296 * are used.
3297 *
3298 * Returns a Bitmapset of Param IDs.
3299 */
3302 {
3307 {
3315 {
3318 /* We can be quick for plain Consts */
3322 }
3323 }
3326 }
3328 /*
3329 * perform_pruning_base_step
3330 * Determines the indexes of datums that satisfy conditions specified in
3331 * 'opstep'.
3332 *
3333 * Result also contains whether special null-accepting and/or default
3334 * partition need to be scanned.
3335 */
3339 {
3343 nvalues;
3348 /*
3349 * There better be the same number of expressions and compare functions.
3350 */
3357 /*
3358 * Generate the partition lookup key that will be used by one of the
3359 * get_matching_*_bounds functions called below.
3360 */
3362 {
3363 /*
3364 * For hash partitioning, it is possible that values of some keys are
3365 * not provided in operator clauses, but instead the planner found
3366 * that they appeared in a IS NULL clause.
3367 */
3371 /*
3372 * For range partitioning, we must only perform pruning with values
3373 * for either all partition keys or a prefix thereof.
3374 */
3379 {
3381 Datum datum;
3383 Oid cmpfn;
3391 /*
3392 * Since we only allow strict operators in pruning steps, any
3393 * null-valued comparison value must cause the comparison to fail,
3394 * so that no partitions could match.
3395 */
3397 {
3406 }
3408 /* Set up the stepcmpfuncs entry, unless we already did */
3412 {
3413 /*
3414 * If the needed support function is the same one cached in
3415 * the relation's partition key, copy the cached FmgrInfo.
3416 * Otherwise (i.e., when we have a cross-type comparison), an
3417 * actual lookup is required.
3418 */
3423 else
3426 }
3429 nvalues++;
3433 }
3434 }
3436 /*
3437 * Point partsupfunc to the entry for the 0th key of this step; the
3438 * additional support functions, if any, follow consecutively.
3439 */
3444 {
3449 partsupfunc,
3463 partsupfunc,
3470 }
3473 }
3475 /*
3476 * perform_pruning_combine_step
3477 * Determines the indexes of datums obtained by combining those given
3478 * by the steps identified by cstep->source_stepids using the specified
3479 * combination method
3480 *
3481 * Since cstep may refer to the result of earlier steps, we also receive
3482 * step_results here.
3483 */
3488 {
3493 /*
3494 * A combine step without any source steps is an indication to not perform
3495 * any partition pruning. Return all datum indexes in that case.
3496 */
3498 {
3506 }
3509 {
3512 {
3516 /*
3517 * step_results[step_id] must contain a valid result, which is
3518 * confirmed by the fact that cstep's step_id is greater than
3519 * step_id and the fact that results of the individual steps
3520 * are evaluated in sequence of their step_ids.
3521 */
3527 /* Record any additional datum indexes from this step */
3531 /* Update whether to scan null and default partitions. */
3536 }
3542 {
3552 {
3553 /* Copy step's result the first time. */
3559 }
3560 else
3561 {
3562 /* Record datum indexes common to both steps */
3567 /* Update whether to scan null and default partitions. */
3572 }
3573 }
3575 }
3578 }
3580 /*
3581 * match_boolean_partition_clause
3582 *
3583 * If we're able to match the clause to the partition key as specially-shaped
3584 * boolean clause, set *outconst to a Const containing a true or false value
3585 * and return PARTCLAUSE_MATCH_CLAUSE. Returns PARTCLAUSE_UNSUPPORTED if the
3586 * clause is not a boolean clause or if the boolean clause is unsuitable for
3587 * partition pruning. Returns PARTCLAUSE_NOMATCH if it's a bool quals but
3588 * just does not match this partition key. *outconst is set to NULL in the
3589 * latter two cases.
3590 */
3591 static PartClauseMatchStatus
3594 {
3599 /*
3600 * Partitioning currently can only use built-in AMs, so checking for
3601 * built-in boolean opfamilies is good enough.
3602 */
3607 {
3610 /* Only IS [NOT] TRUE/FALSE are any good to us */
3627 }
3628 else
3629 {
3637 /* Compare to the partition key, and make up a clause ... */
3647 }
3650 }
3652 /*
3653 * partkey_datum_from_expr
3654 * Evaluate expression for potential partition pruning
3655 *
3656 * Evaluate 'expr'; set *value and *isnull to the resulting Datum and nullflag.
3657 *
3658 * If expr isn't a Const, its ExprState is in stateidx of the context
3659 * exprstate array.
3660 *
3661 * Note that the evaluated result may be in the per-tuple memory context of
3662 * context->exprcontext, and we may have leaked other memory there too.
3663 * This memory must be recovered by resetting that ExprContext after
3664 * we're done with the pruning operation (see execPartition.c).
3665 */
3666 static void
3670 {
3672 {
3673 /* We can always determine the value of a constant */
3678 }
3679 else
3680 {
3684 /*
3685 * We should never see a non-Const in a step unless the caller has
3686 * passed a valid ExprContext.
3687 *
3688 * When context->planstate is valid, context->exprcontext is same as
3689 * context->planstate->ps_ExprContext.
3690 */
3698 }
3699 }