Debian Codegraph @

src/backend/partitioning/partprune.c

raw
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-2025, 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 */
36 #include "postgres.h"
37
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_proc.h"
43 #include "catalog/pg_type.h"
44 #include "executor/executor.h"
45 #include "miscadmin.h"
46 #include "nodes/makefuncs.h"
47 #include "nodes/nodeFuncs.h"
48 #include "optimizer/appendinfo.h"
49 #include "optimizer/cost.h"
50 #include "optimizer/optimizer.h"
51 #include "optimizer/pathnode.h"
52 #include "optimizer/placeholder.h"
53 #include "parser/parsetree.h"
54 #include "partitioning/partbounds.h"
55 #include "partitioning/partprune.h"
56 #include "utils/array.h"
57 #include "utils/lsyscache.h"
58
59
60 /*
61 * Information about a clause matched with a partition key.
62 */
63 typedef struct PartClauseInfo
64 {
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
70 * partition key */
71 int op_strategy; /* btree strategy identifying the operator */
72 } PartClauseInfo;
73
74 /*
75 * PartClauseMatchStatus
76 * Describes the result of match_clause_to_partition_key()
77 */
78 typedef enum PartClauseMatchStatus
79 {
80 PARTCLAUSE_NOMATCH,
81 PARTCLAUSE_MATCH_CLAUSE,
82 PARTCLAUSE_MATCH_NULLNESS,
83 PARTCLAUSE_MATCH_STEPS,
84 PARTCLAUSE_MATCH_CONTRADICT,
85 PARTCLAUSE_UNSUPPORTED,
86 } PartClauseMatchStatus;
87
88 /*
89 * PartClauseTarget
90 * Identifies which qual clauses we can use for generating pruning steps
91 */
92 typedef enum PartClauseTarget
93 {
94 PARTTARGET_PLANNER, /* want to prune during planning */
95 PARTTARGET_INITIAL, /* want to prune during executor startup */
96 PARTTARGET_EXEC, /* want to prune during each plan node scan */
97 } PartClauseTarget;
98
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 */
111 typedef struct GeneratePruningStepsContext
112 {
113 /* Copies of input arguments for gen_partprune_steps: */
114 RelOptInfo *rel; /* the partitioned relation */
115 PartClauseTarget target; /* use-case we're generating steps for */
116 /* Result data: */
117 List *steps; /* list of PartitionPruneSteps */
118 bool has_mutable_op; /* clauses include any stable operators */
119 bool has_mutable_arg; /* clauses include any mutable comparison
120 * values, *other than* exec params */
121 bool has_exec_param; /* clauses include any PARAM_EXEC params */
122 bool contradictory; /* clauses were proven self-contradictory */
123 /* Working state: */
124 int next_step_id;
125 } GeneratePruningStepsContext;
126
127 /* The result of performing one PartitionPruneStep */
128 typedef struct PruneStepResult
129 {
130 /*
131 * The offsets of bounds (in a table's boundinfo) whose partition is
132 * selected by the pruning step.
133 */
134 Bitmapset *bound_offsets;
135
136 bool scan_default; /* Scan the default partition? */
137 bool scan_null; /* Scan the partition for NULL values? */
138 } PruneStepResult;
139
140
141 static List *add_part_relids(List *allpartrelids, Bitmapset *partrelids);
142 static List *make_partitionedrel_pruneinfo(PlannerInfo *root,
143 RelOptInfo *parentrel,
144 List *prunequal,
145 Bitmapset *partrelids,
146 int *relid_subplan_map,
147 Bitmapset **matchedsubplans);
148 static void gen_partprune_steps(RelOptInfo *rel, List *clauses,
149 PartClauseTarget target,
150 GeneratePruningStepsContext *context);
151 static List *gen_partprune_steps_internal(GeneratePruningStepsContext *context,
152 List *clauses);
153 static PartitionPruneStep *gen_prune_step_op(GeneratePruningStepsContext *context,
154 StrategyNumber opstrategy, bool op_is_ne,
155 List *exprs, List *cmpfns, Bitmapset *nullkeys);
156 static PartitionPruneStep *gen_prune_step_combine(GeneratePruningStepsContext *context,
157 List *source_stepids,
158 PartitionPruneCombineOp combineOp);
159 static List *gen_prune_steps_from_opexps(GeneratePruningStepsContext *context,
160 List **keyclauses, Bitmapset *nullkeys);
161 static PartClauseMatchStatus match_clause_to_partition_key(GeneratePruningStepsContext *context,
162 Expr *clause, Expr *partkey, int partkeyidx,
163 bool *clause_is_not_null,
164 PartClauseInfo **pc, List **clause_steps);
165 static List *get_steps_using_prefix(GeneratePruningStepsContext *context,
166 StrategyNumber step_opstrategy,
167 bool step_op_is_ne,
168 Expr *step_lastexpr,
169 Oid step_lastcmpfn,
170 Bitmapset *step_nullkeys,
171 List *prefix);
172 static List *get_steps_using_prefix_recurse(GeneratePruningStepsContext *context,
173 StrategyNumber step_opstrategy,
174 bool step_op_is_ne,
175 Expr *step_lastexpr,
176 Oid step_lastcmpfn,
177 Bitmapset *step_nullkeys,
178 List *prefix,
179 ListCell *start,
180 List *step_exprs,
181 List *step_cmpfns);
182 static PruneStepResult *get_matching_hash_bounds(PartitionPruneContext *context,
183 StrategyNumber opstrategy, Datum *values, int nvalues,
184 FmgrInfo *partsupfunc, Bitmapset *nullkeys);
185 static PruneStepResult *get_matching_list_bounds(PartitionPruneContext *context,
186 StrategyNumber opstrategy, Datum value, int nvalues,
187 FmgrInfo *partsupfunc, Bitmapset *nullkeys);
188 static PruneStepResult *get_matching_range_bounds(PartitionPruneContext *context,
189 StrategyNumber opstrategy, Datum *values, int nvalues,
190 FmgrInfo *partsupfunc, Bitmapset *nullkeys);
191 static Bitmapset *pull_exec_paramids(Expr *expr);
192 static bool pull_exec_paramids_walker(Node *node, Bitmapset **context);
193 static Bitmapset *get_partkey_exec_paramids(List *steps);
194 static PruneStepResult *perform_pruning_base_step(PartitionPruneContext *context,
195 PartitionPruneStepOp *opstep);
196 static PruneStepResult *perform_pruning_combine_step(PartitionPruneContext *context,
197 PartitionPruneStepCombine *cstep,
198 PruneStepResult **step_results);
199 static PartClauseMatchStatus match_boolean_partition_clause(Oid partopfamily,
200 Expr *clause,
201 Expr *partkey,
202 Expr **outconst,
203 bool *notclause);
204 static void partkey_datum_from_expr(PartitionPruneContext *context,
205 Expr *expr, int stateidx,
206 Datum *value, bool *isnull);
207
208
209 /*
210 * make_partition_pruneinfo
211 * Checks if the given set of quals can be used to build pruning steps
212 * that the executor can use to prune away unneeded partitions. If
213 * suitable quals are found then a PartitionPruneInfo is built and tagged
214 * onto the PlannerInfo's partPruneInfos list.
215 *
216 * The return value is the 0-based index of the item added to the
217 * partPruneInfos list or -1 if nothing was added.
218 *
219 * 'parentrel' is the RelOptInfo for an appendrel, and 'subpaths' is the list
220 * of scan paths for its child rels.
221 * 'prunequal' is a list of potential pruning quals (i.e., restriction
222 * clauses that are applicable to the appendrel).
223 */
224 int
225 make_partition_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
226 List *subpaths,
227 List *prunequal)
228 {
229 PartitionPruneInfo *pruneinfo;
230 Bitmapset *allmatchedsubplans = NULL;
231 List *allpartrelids;
232 List *prunerelinfos;
233 int *relid_subplan_map;
234 ListCell *lc;
235 int i;
236
237 /*
238 * Scan the subpaths to see which ones are scans of partition child
239 * relations, and identify their parent partitioned rels. (Note: we must
240 * restrict the parent partitioned rels to be parentrel or children of
241 * parentrel, otherwise we couldn't translate prunequal to match.)
242 *
243 * Also construct a temporary array to map from partition-child-relation
244 * relid to the index in 'subpaths' of the scan plan for that partition.
245 * (Use of "subplan" rather than "subpath" is a bit of a misnomer, but
246 * we'll let it stand.) For convenience, we use 1-based indexes here, so
247 * that zero can represent an un-filled array entry.
248 */
249 allpartrelids = NIL;
250 relid_subplan_map = palloc0(sizeof(int) * root->simple_rel_array_size);
251
252 i = 1;
253 foreach(lc, subpaths)
254 {
255 Path *path = (Path *) lfirst(lc);
256 RelOptInfo *pathrel = path->parent;
257
258 /* We don't consider partitioned joins here */
259 if (pathrel->reloptkind == RELOPT_OTHER_MEMBER_REL)
260 {
261 RelOptInfo *prel = pathrel;
262 Bitmapset *partrelids = NULL;
263
264 /*
265 * Traverse up to the pathrel's topmost partitioned parent,
266 * collecting parent relids as we go; but stop if we reach
267 * parentrel. (Normally, a pathrel's topmost partitioned parent
268 * is either parentrel or a UNION ALL appendrel child of
269 * parentrel. But when handling partitionwise joins of
270 * multi-level partitioning trees, we can see an append path whose
271 * parentrel is an intermediate partitioned table.)
272 */
273 do
274 {
275 AppendRelInfo *appinfo;
276
277 Assert(prel->relid < root->simple_rel_array_size);
278 appinfo = root->append_rel_array[prel->relid];
279 prel = find_base_rel(root, appinfo->parent_relid);
280 if (!IS_PARTITIONED_REL(prel))
281 break; /* reached a non-partitioned parent */
282 /* accept this level as an interesting parent */
283 partrelids = bms_add_member(partrelids, prel->relid);
284 if (prel == parentrel)
285 break; /* don't traverse above parentrel */
286 } while (prel->reloptkind == RELOPT_OTHER_MEMBER_REL);
287
288 if (partrelids)
289 {
290 /*
291 * Found some relevant parent partitions, which may or may not
292 * overlap with partition trees we already found. Add new
293 * information to the allpartrelids list.
294 */
295 allpartrelids = add_part_relids(allpartrelids, partrelids);
296 /* Also record the subplan in relid_subplan_map[] */
297 /* No duplicates please */
298 Assert(relid_subplan_map[pathrel->relid] == 0);
299 relid_subplan_map[pathrel->relid] = i;
300 }
301 }
302 i++;
303 }
304
305 /*
306 * We now build a PartitionedRelPruneInfo for each topmost partitioned rel
307 * (omitting any that turn out not to have useful pruning quals).
308 */
309 prunerelinfos = NIL;
310 foreach(lc, allpartrelids)
311 {
312 Bitmapset *partrelids = (Bitmapset *) lfirst(lc);
313 List *pinfolist;
314 Bitmapset *matchedsubplans = NULL;
315
316 pinfolist = make_partitionedrel_pruneinfo(root, parentrel,
317 prunequal,
318 partrelids,
319 relid_subplan_map,
320 &matchedsubplans);
321
322 /* When pruning is possible, record the matched subplans */
323 if (pinfolist != NIL)
324 {
325 prunerelinfos = lappend(prunerelinfos, pinfolist);
326 allmatchedsubplans = bms_join(matchedsubplans,
327 allmatchedsubplans);
328 }
329 }
330
331 pfree(relid_subplan_map);
332
333 /*
334 * If none of the partition hierarchies had any useful run-time pruning
335 * quals, then we can just not bother with run-time pruning.
336 */
337 if (prunerelinfos == NIL)
338 return -1;
339
340 /* Else build the result data structure */
341 pruneinfo = makeNode(PartitionPruneInfo);
342 pruneinfo->relids = bms_copy(parentrel->relids);
343 pruneinfo->prune_infos = prunerelinfos;
344
345 /*
346 * Some subplans may not belong to any of the identified partitioned rels.
347 * This can happen for UNION ALL queries which include a non-partitioned
348 * table, or when some of the hierarchies aren't run-time prunable. Build
349 * a bitmapset of the indexes of all such subplans, so that the executor
350 * can identify which subplans should never be pruned.
351 */
352 if (bms_num_members(allmatchedsubplans) < list_length(subpaths))
353 {
354 Bitmapset *other_subplans;
355
356 /* Create the complement of allmatchedsubplans */
357 other_subplans = bms_add_range(NULL, 0, list_length(subpaths) - 1);
358 other_subplans = bms_del_members(other_subplans, allmatchedsubplans);
359
360 pruneinfo->other_subplans = other_subplans;
361 }
362 else
363 pruneinfo->other_subplans = NULL;
364
365 root->partPruneInfos = lappend(root->partPruneInfos, pruneinfo);
366
367 return list_length(root->partPruneInfos) - 1;
368 }
369
370 /*
371 * add_part_relids
372 * Add new info to a list of Bitmapsets of partitioned relids.
373 *
374 * Within 'allpartrelids', there is one Bitmapset for each topmost parent
375 * partitioned rel. Each Bitmapset contains the RT indexes of the topmost
376 * parent as well as its relevant non-leaf child partitions. Since (by
377 * construction of the rangetable list) parent partitions must have lower
378 * RT indexes than their children, we can distinguish the topmost parent
379 * as being the lowest set bit in the Bitmapset.
380 *
381 * 'partrelids' contains the RT indexes of a parent partitioned rel, and
382 * possibly some non-leaf children, that are newly identified as parents of
383 * some subpath rel passed to make_partition_pruneinfo(). These are added
384 * to an appropriate member of 'allpartrelids'.
385 *
386 * Note that the list contains only RT indexes of partitioned tables that
387 * are parents of some scan-level relation appearing in the 'subpaths' that
388 * make_partition_pruneinfo() is dealing with. Also, "topmost" parents are
389 * not allowed to be higher than the 'parentrel' associated with the append
390 * path. In this way, we avoid expending cycles on partitioned rels that
391 * can't contribute useful pruning information for the problem at hand.
392 * (It is possible for 'parentrel' to be a child partitioned table, and it
393 * is also possible for scan-level relations to be child partitioned tables
394 * rather than leaf partitions. Hence we must construct this relation set
395 * with reference to the particular append path we're dealing with, rather
396 * than looking at the full partitioning structure represented in the
397 * RelOptInfos.)
398 */
399 static List *
400 add_part_relids(List *allpartrelids, Bitmapset *partrelids)
401 {
402 Index targetpart;
403 ListCell *lc;
404
405 /* We can easily get the lowest set bit this way: */
406 targetpart = bms_next_member(partrelids, -1);
407 Assert(targetpart > 0);
408
409 /* Look for a matching topmost parent */
410 foreach(lc, allpartrelids)
411 {
412 Bitmapset *currpartrelids = (Bitmapset *) lfirst(lc);
413 Index currtarget = bms_next_member(currpartrelids, -1);
414
415 if (targetpart == currtarget)
416 {
417 /* Found a match, so add any new RT indexes to this hierarchy */
418 currpartrelids = bms_add_members(currpartrelids, partrelids);
419 lfirst(lc) = currpartrelids;
420 return allpartrelids;
421 }
422 }
423 /* No match, so add the new partition hierarchy to the list */
424 return lappend(allpartrelids, partrelids);
425 }
426
427 /*
428 * make_partitionedrel_pruneinfo
429 * Build a List of PartitionedRelPruneInfos, one for each interesting
430 * partitioned rel in a partitioning hierarchy. These can be used in the
431 * executor to allow additional partition pruning to take place.
432 *
433 * parentrel: rel associated with the appendpath being considered
434 * prunequal: potential pruning quals, represented for parentrel
435 * partrelids: Set of RT indexes identifying relevant partitioned tables
436 * within a single partitioning hierarchy
437 * relid_subplan_map[]: maps child relation relids to subplan indexes
438 * matchedsubplans: on success, receives the set of subplan indexes which
439 * were matched to this partition hierarchy
440 *
441 * If we cannot find any useful run-time pruning steps, return NIL.
442 * However, on success, each rel identified in partrelids will have
443 * an element in the result list, even if some of them are useless.
444 */
445 static List *
446 make_partitionedrel_pruneinfo(PlannerInfo *root, RelOptInfo *parentrel,
447 List *prunequal,
448 Bitmapset *partrelids,
449 int *relid_subplan_map,
450 Bitmapset **matchedsubplans)
451 {
452 RelOptInfo *targetpart = NULL;
453 List *pinfolist = NIL;
454 bool doruntimeprune = false;
455 int *relid_subpart_map;
456 Bitmapset *subplansfound = NULL;
457 ListCell *lc;
458 int rti;
459 int i;
460
461 /*
462 * Examine each partitioned rel, constructing a temporary array to map
463 * from planner relids to index of the partitioned rel, and building a
464 * PartitionedRelPruneInfo for each partitioned rel.
465 *
466 * In this phase we discover whether runtime pruning is needed at all; if
467 * not, we can avoid doing further work.
468 */
469 relid_subpart_map = palloc0(sizeof(int) * root->simple_rel_array_size);
470
471 i = 1;
472 rti = -1;
473 while ((rti = bms_next_member(partrelids, rti)) > 0)
474 {
475 RelOptInfo *subpart = find_base_rel(root, rti);
476 PartitionedRelPruneInfo *pinfo;
477 List *partprunequal;
478 List *initial_pruning_steps;
479 List *exec_pruning_steps;
480 Bitmapset *execparamids;
481 GeneratePruningStepsContext context;
482
483 /*
484 * Fill the mapping array.
485 *
486 * relid_subpart_map maps relid of a non-leaf partition to the index
487 * in the returned PartitionedRelPruneInfo list of the info for that
488 * partition. We use 1-based indexes here, so that zero can represent
489 * an un-filled array entry.
490 */
491 Assert(rti < root->simple_rel_array_size);
492 relid_subpart_map[rti] = i++;
493
494 /*
495 * Translate pruning qual, if necessary, for this partition.
496 *
497 * The first item in the list is the target partitioned relation.
498 */
499 if (!targetpart)
500 {
501 targetpart = subpart;
502
503 /*
504 * The prunequal is presented to us as a qual for 'parentrel'.
505 * Frequently this rel is the same as targetpart, so we can skip
506 * an adjust_appendrel_attrs step. But it might not be, and then
507 * we have to translate. We update the prunequal parameter here,
508 * because in later iterations of the loop for child partitions,
509 * we want to translate from parent to child variables.
510 */
511 if (!bms_equal(parentrel->relids, subpart->relids))
512 {
513 int nappinfos;
514 AppendRelInfo **appinfos = find_appinfos_by_relids(root,
515 subpart->relids,
516 &nappinfos);
517
518 prunequal = (List *) adjust_appendrel_attrs(root, (Node *)
519 prunequal,
520 nappinfos,
521 appinfos);
522
523 pfree(appinfos);
524 }
525
526 partprunequal = prunequal;
527 }
528 else
529 {
530 /*
531 * For sub-partitioned tables the columns may not be in the same
532 * order as the parent, so we must translate the prunequal to make
533 * it compatible with this relation.
534 */
535 partprunequal = (List *)
536 adjust_appendrel_attrs_multilevel(root,
537 (Node *) prunequal,
538 subpart,
539 targetpart);
540 }
541
542 /*
543 * Convert pruning qual to pruning steps. We may need to do this
544 * twice, once to obtain executor startup pruning steps, and once for
545 * executor per-scan pruning steps. This first pass creates startup
546 * pruning steps and detects whether there's any possibly-useful quals
547 * that would require per-scan pruning.
548 */
549 gen_partprune_steps(subpart, partprunequal, PARTTARGET_INITIAL,
550 &context);
551
552 if (context.contradictory)
553 {
554 /*
555 * This shouldn't happen as the planner should have detected this
556 * earlier. However, we do use additional quals from parameterized
557 * paths here. These do only compare Params to the partition key,
558 * so this shouldn't cause the discovery of any new qual
559 * contradictions that were not previously discovered as the Param
560 * values are unknown during planning. Anyway, we'd better do
561 * something sane here, so let's just disable run-time pruning.
562 */
563 return NIL;
564 }
565
566 /*
567 * If no mutable operators or expressions appear in usable pruning
568 * clauses, then there's no point in running startup pruning, because
569 * plan-time pruning should have pruned everything prunable.
570 */
571 if (context.has_mutable_op || context.has_mutable_arg)
572 initial_pruning_steps = context.steps;
573 else
574 initial_pruning_steps = NIL;
575
576 /*
577 * If no exec Params appear in potentially-usable pruning clauses,
578 * then there's no point in even thinking about per-scan pruning.
579 */
580 if (context.has_exec_param)
581 {
582 /* ... OK, we'd better think about it */
583 gen_partprune_steps(subpart, partprunequal, PARTTARGET_EXEC,
584 &context);
585
586 if (context.contradictory)
587 {
588 /* As above, skip run-time pruning if anything fishy happens */
589 return NIL;
590 }
591
592 exec_pruning_steps = context.steps;
593
594 /*
595 * Detect which exec Params actually got used; the fact that some
596 * were in available clauses doesn't mean we actually used them.
597 * Skip per-scan pruning if there are none.
598 */
599 execparamids = get_partkey_exec_paramids(exec_pruning_steps);
600
601 if (bms_is_empty(execparamids))
602 exec_pruning_steps = NIL;
603 }
604 else
605 {
606 /* No exec Params anywhere, so forget about scan-time pruning */
607 exec_pruning_steps = NIL;
608 execparamids = NULL;
609 }
610
611 if (initial_pruning_steps || exec_pruning_steps)
612 doruntimeprune = true;
613
614 /* Begin constructing the PartitionedRelPruneInfo for this rel */
615 pinfo = makeNode(PartitionedRelPruneInfo);
616 pinfo->rtindex = rti;
617 pinfo->initial_pruning_steps = initial_pruning_steps;
618 pinfo->exec_pruning_steps = exec_pruning_steps;
619 pinfo->execparamids = execparamids;
620 /* Remaining fields will be filled in the next loop */
621
622 pinfolist = lappend(pinfolist, pinfo);
623 }
624
625 if (!doruntimeprune)
626 {
627 /* No run-time pruning required. */
628 pfree(relid_subpart_map);
629 return NIL;
630 }
631
632 /*
633 * Run-time pruning will be required, so initialize other information.
634 * That includes two maps -- one needed to convert partition indexes of
635 * leaf partitions to the indexes of their subplans in the subplan list,
636 * another needed to convert partition indexes of sub-partitioned
637 * partitions to the indexes of their PartitionedRelPruneInfo in the
638 * PartitionedRelPruneInfo list.
639 */
640 foreach(lc, pinfolist)
641 {
642 PartitionedRelPruneInfo *pinfo = lfirst(lc);
643 RelOptInfo *subpart = find_base_rel(root, pinfo->rtindex);
644 Bitmapset *present_parts;
645 int nparts = subpart->nparts;
646 int *subplan_map;
647 int *subpart_map;
648 Oid *relid_map;
649 int *leafpart_rti_map;
650
651 /*
652 * Construct the subplan and subpart maps for this partitioning level.
653 * Here we convert to zero-based indexes, with -1 for empty entries.
654 * Also construct a Bitmapset of all partitions that are present (that
655 * is, not pruned already).
656 */
657 subplan_map = (int *) palloc(nparts * sizeof(int));
658 memset(subplan_map, -1, nparts * sizeof(int));
659 subpart_map = (int *) palloc(nparts * sizeof(int));
660 memset(subpart_map, -1, nparts * sizeof(int));
661 relid_map = (Oid *) palloc0(nparts * sizeof(Oid));
662 leafpart_rti_map = (int *) palloc0(nparts * sizeof(int));
663 present_parts = NULL;
664
665 i = -1;
666 while ((i = bms_next_member(subpart->live_parts, i)) >= 0)
667 {
668 RelOptInfo *partrel = subpart->part_rels[i];
669 int subplanidx;
670 int subpartidx;
671
672 Assert(partrel != NULL);
673
674 subplan_map[i] = subplanidx = relid_subplan_map[partrel->relid] - 1;
675 subpart_map[i] = subpartidx = relid_subpart_map[partrel->relid] - 1;
676 relid_map[i] = planner_rt_fetch(partrel->relid, root)->relid;
677
678 /*
679 * Track the RT indexes of "leaf" partitions so they can be
680 * included in the PlannerGlobal.prunableRelids set, indicating
681 * relations that may be pruned during executor startup.
682 *
683 * Only leaf partitions with a valid subplan that are prunable
684 * using initial pruning are added to prunableRelids. So
685 * partitions without a subplan due to constraint exclusion will
686 * remain in PlannedStmt.unprunableRelids.
687 */
688 if (subplanidx >= 0)
689 {
690 present_parts = bms_add_member(present_parts, i);
691
692 /*
693 * Non-leaf partitions may appear here when they use an
694 * unflattened Append or MergeAppend. These should not be
695 * included in prunableRelids.
696 */
697 if (partrel->nparts == -1)
698 leafpart_rti_map[i] = (int) partrel->relid;
699
700 /* Record finding this subplan */
701 subplansfound = bms_add_member(subplansfound, subplanidx);
702 }
703 else if (subpartidx >= 0)
704 present_parts = bms_add_member(present_parts, i);
705 }
706
707 /*
708 * Ensure there were no stray PartitionedRelPruneInfo generated for
709 * partitioned tables that we have no sub-paths or
710 * sub-PartitionedRelPruneInfo for.
711 */
712 Assert(!bms_is_empty(present_parts));
713
714 /* Record the maps and other information. */
715 pinfo->present_parts = present_parts;
716 pinfo->nparts = nparts;
717 pinfo->subplan_map = subplan_map;
718 pinfo->subpart_map = subpart_map;
719 pinfo->relid_map = relid_map;
720 pinfo->leafpart_rti_map = leafpart_rti_map;
721 }
722
723 pfree(relid_subpart_map);
724
725 *matchedsubplans = subplansfound;
726
727 return pinfolist;
728 }
729
730 /*
731 * gen_partprune_steps
732 * Process 'clauses' (typically a rel's baserestrictinfo list of clauses)
733 * and create a list of "partition pruning steps".
734 *
735 * 'target' tells whether to generate pruning steps for planning (use
736 * immutable clauses only), or for executor startup (use any allowable
737 * clause except ones containing PARAM_EXEC Params), or for executor
738 * per-scan pruning (use any allowable clause).
739 *
740 * 'context' is an output argument that receives the steps list as well as
741 * some subsidiary flags; see the GeneratePruningStepsContext typedef.
742 */
743 static void
744 gen_partprune_steps(RelOptInfo *rel, List *clauses, PartClauseTarget target,
745 GeneratePruningStepsContext *context)
746 {
747 /* Initialize all output values to zero/false/NULL */
748 memset(context, 0, sizeof(GeneratePruningStepsContext));
749 context->rel = rel;
750 context->target = target;
751
752 /*
753 * If this partitioned table is in turn a partition, and it shares any
754 * partition keys with its parent, then it's possible that the hierarchy
755 * allows the parent a narrower range of values than some of its
756 * partitions (particularly the default one). This is normally not
757 * useful, but it can be to prune the default partition.
758 */
759 if (partition_bound_has_default(rel->boundinfo) && rel->partition_qual)
760 {
761 /* Make a copy to avoid modifying the passed-in List */
762 clauses = list_concat_copy(clauses, rel->partition_qual);
763 }
764
765 /* Down into the rabbit-hole. */
766 (void) gen_partprune_steps_internal(context, clauses);
767 }
768
769 /*
770 * prune_append_rel_partitions
771 * Process rel's baserestrictinfo and make use of quals which can be
772 * evaluated during query planning in order to determine the minimum set
773 * of partitions which must be scanned to satisfy these quals. Returns
774 * the matching partitions in the form of a Bitmapset containing the
775 * partitions' indexes in the rel's part_rels array.
776 *
777 * Callers must ensure that 'rel' is a partitioned table.
778 */
779 Bitmapset *
780 prune_append_rel_partitions(RelOptInfo *rel)
781 {
782 List *clauses = rel->baserestrictinfo;
783 List *pruning_steps;
784 GeneratePruningStepsContext gcontext;
785 PartitionPruneContext context;
786
787 Assert(rel->part_scheme != NULL);
788
789 /* If there are no partitions, return the empty set */
790 if (rel->nparts == 0)
791 return NULL;
792
793 /*
794 * If pruning is disabled or if there are no clauses to prune with, return
795 * all partitions.
796 */
797 if (!enable_partition_pruning || clauses == NIL)
798 return bms_add_range(NULL, 0, rel->nparts - 1);
799
800 /*
801 * Process clauses to extract pruning steps that are usable at plan time.
802 * If the clauses are found to be contradictory, we can return the empty
803 * set.
804 */
805 gen_partprune_steps(rel, clauses, PARTTARGET_PLANNER,
806 &gcontext);
807 if (gcontext.contradictory)
808 return NULL;
809 pruning_steps = gcontext.steps;
810
811 /* If there's nothing usable, return all partitions */
812 if (pruning_steps == NIL)
813 return bms_add_range(NULL, 0, rel->nparts - 1);
814
815 /* Set up PartitionPruneContext */
816 context.strategy = rel->part_scheme->strategy;
817 context.partnatts = rel->part_scheme->partnatts;
818 context.nparts = rel->nparts;
819 context.boundinfo = rel->boundinfo;
820 context.partcollation = rel->part_scheme->partcollation;
821 context.partsupfunc = rel->part_scheme->partsupfunc;
822 context.stepcmpfuncs = (FmgrInfo *) palloc0(sizeof(FmgrInfo) *
823 context.partnatts *
824 list_length(pruning_steps));
825 context.ppccontext = CurrentMemoryContext;
826
827 /* These are not valid when being called from the planner */
828 context.planstate = NULL;
829 context.exprcontext = NULL;
830 context.exprstates = NULL;
831
832 /* Actual pruning happens here. */
833 return get_matching_partitions(&context, pruning_steps);
834 }
835
836 /*
837 * get_matching_partitions
838 * Determine partitions that survive partition pruning
839 *
840 * Note: context->exprcontext must be valid when the pruning_steps were
841 * generated with a target other than PARTTARGET_PLANNER.
842 *
843 * Returns a Bitmapset of the RelOptInfo->part_rels indexes of the surviving
844 * partitions.
845 */
846 Bitmapset *
847 get_matching_partitions(PartitionPruneContext *context, List *pruning_steps)
848 {
849 Bitmapset *result;
850 int num_steps = list_length(pruning_steps),
851 i;
852 PruneStepResult **results,
853 *final_result;
854 ListCell *lc;
855 bool scan_default;
856
857 /* If there are no pruning steps then all partitions match. */
858 if (num_steps == 0)
859 {
860 Assert(context->nparts > 0);
861 return bms_add_range(NULL, 0, context->nparts - 1);
862 }
863
864 /*
865 * Allocate space for individual pruning steps to store its result. Each
866 * slot will hold a PruneStepResult after performing a given pruning step.
867 * Later steps may use the result of one or more earlier steps. The
868 * result of applying all pruning steps is the value contained in the slot
869 * of the last pruning step.
870 */
871 results = (PruneStepResult **)
872 palloc0(num_steps * sizeof(PruneStepResult *));
873 foreach(lc, pruning_steps)
874 {
875 PartitionPruneStep *step = lfirst(lc);
876
877 switch (nodeTag(step))
878 {
879 case T_PartitionPruneStepOp:
880 results[step->step_id] =
881 perform_pruning_base_step(context,
882 (PartitionPruneStepOp *) step);
883 break;
884
885 case T_PartitionPruneStepCombine:
886 results[step->step_id] =
887 perform_pruning_combine_step(context,
888 (PartitionPruneStepCombine *) step,
889 results);
890 break;
891
892 default:
893 elog(ERROR, "invalid pruning step type: %d",
894 (int) nodeTag(step));
895 }
896 }
897
898 /*
899 * At this point we know the offsets of all the datums whose corresponding
900 * partitions need to be in the result, including special null-accepting
901 * and default partitions. Collect the actual partition indexes now.
902 */
903 final_result = results[num_steps - 1];
904 Assert(final_result != NULL);
905 i = -1;
906 result = NULL;
907 scan_default = final_result->scan_default;
908 while ((i = bms_next_member(final_result->bound_offsets, i)) >= 0)
909 {
910 int partindex;
911
912 Assert(i < context->boundinfo->nindexes);
913 partindex = context->boundinfo->indexes[i];
914
915 if (partindex < 0)
916 {
917 /*
918 * In range partitioning cases, if a partition index is -1 it
919 * means that the bound at the offset is the upper bound for a
920 * range not covered by any partition (other than a possible
921 * default partition). In hash partitioning, the same means no
922 * partition has been defined for the corresponding remainder
923 * value.
924 *
925 * In either case, the value is still part of the queried range of
926 * values, so mark to scan the default partition if one exists.
927 */
928 scan_default |= partition_bound_has_default(context->boundinfo);
929 continue;
930 }
931
932 result = bms_add_member(result, partindex);
933 }
934
935 /* Add the null and/or default partition if needed and present. */
936 if (final_result->scan_null)
937 {
938 Assert(context->strategy == PARTITION_STRATEGY_LIST);
939 Assert(partition_bound_accepts_nulls(context->boundinfo));
940 result = bms_add_member(result, context->boundinfo->null_index);
941 }
942 if (scan_default)
943 {
944 Assert(context->strategy == PARTITION_STRATEGY_LIST ||
945 context->strategy == PARTITION_STRATEGY_RANGE);
946 Assert(partition_bound_has_default(context->boundinfo));
947 result = bms_add_member(result, context->boundinfo->default_index);
948 }
949
950 return result;
951 }
952
953 /*
954 * gen_partprune_steps_internal
955 * Processes 'clauses' to generate a List of partition pruning steps. We
956 * return NIL when no steps were generated.
957 *
958 * These partition pruning steps come in 2 forms; operator steps and combine
959 * steps.
960 *
961 * Operator steps (PartitionPruneStepOp) contain details of clauses that we
962 * determined that we can use for partition pruning. These contain details of
963 * the expression which is being compared to the partition key and the
964 * comparison function.
965 *
966 * Combine steps (PartitionPruneStepCombine) instruct the partition pruning
967 * code how it should produce a single set of partitions from multiple input
968 * operator and other combine steps. A PARTPRUNE_COMBINE_INTERSECT type
969 * combine step will merge its input steps to produce a result which only
970 * contains the partitions which are present in all of the input operator
971 * steps. A PARTPRUNE_COMBINE_UNION combine step will produce a result that
972 * has all of the partitions from each of the input operator steps.
973 *
974 * For BoolExpr clauses, each argument is processed recursively. Steps
975 * generated from processing an OR BoolExpr will be combined using
976 * PARTPRUNE_COMBINE_UNION. AND BoolExprs get combined using
977 * PARTPRUNE_COMBINE_INTERSECT.
978 *
979 * Otherwise, the list of clauses we receive we assume to be mutually ANDed.
980 * We generate all of the pruning steps we can based on these clauses and then
981 * at the end, if we have more than 1 step, we combine each step with a
982 * PARTPRUNE_COMBINE_INTERSECT combine step. Single steps are returned as-is.
983 *
984 * If we find clauses that are mutually contradictory, or contradictory with
985 * the partitioning constraint, or a pseudoconstant clause that contains
986 * false, we set context->contradictory to true and return NIL (that is, no
987 * pruning steps). Caller should consider all partitions as pruned in that
988 * case.
989 */
990 static List *
991 gen_partprune_steps_internal(GeneratePruningStepsContext *context,
992 List *clauses)
993 {
994 PartitionScheme part_scheme = context->rel->part_scheme;
995 List *keyclauses[PARTITION_MAX_KEYS];
996 Bitmapset *nullkeys = NULL,
997 *notnullkeys = NULL;
998 bool generate_opsteps = false;
999 List *result = NIL;
1000 ListCell *lc;
1001
1002 /*
1003 * If this partitioned relation has a default partition and is itself a
1004 * partition (as evidenced by partition_qual being not NIL), we first
1005 * check if the clauses contradict the partition constraint. If they do,
1006 * there's no need to generate any steps as it'd already be proven that no
1007 * partitions need to be scanned.
1008 *
1009 * This is a measure of last resort only to be used because the default
1010 * partition cannot be pruned using the steps generated from clauses that
1011 * contradict the parent's partition constraint; regular pruning, which is
1012 * cheaper, is sufficient when no default partition exists.
1013 */
1014 if (partition_bound_has_default(context->rel->boundinfo) &&
1015 predicate_refuted_by(context->rel->partition_qual, clauses, false))
1016 {
1017 context->contradictory = true;
1018 return NIL;
1019 }
1020
1021 memset(keyclauses, 0, sizeof(keyclauses));
1022 foreach(lc, clauses)
1023 {
1024 Expr *clause = (Expr *) lfirst(lc);
1025 int i;
1026
1027 /* Look through RestrictInfo, if any */
1028 if (IsA(clause, RestrictInfo))
1029 clause = ((RestrictInfo *) clause)->clause;
1030
1031 /* Constant-false-or-null is contradictory */
1032 if (IsA(clause, Const) &&
1033 (((Const *) clause)->constisnull ||
1034 !DatumGetBool(((Const *) clause)->constvalue)))
1035 {
1036 context->contradictory = true;
1037 return NIL;
1038 }
1039
1040 /* Get the BoolExpr's out of the way. */
1041 if (IsA(clause, BoolExpr))
1042 {
1043 /*
1044 * Generate steps for arguments.
1045 *
1046 * While steps generated for the arguments themselves will be
1047 * added to context->steps during recursion and will be evaluated
1048 * independently, collect their step IDs to be stored in the
1049 * combine step we'll be creating.
1050 */
1051 if (is_orclause(clause))
1052 {
1053 List *arg_stepids = NIL;
1054 bool all_args_contradictory = true;
1055 ListCell *lc1;
1056
1057 /*
1058 * We can share the outer context area with the recursive
1059 * call, but contradictory had better not be true yet.
1060 */
1061 Assert(!context->contradictory);
1062
1063 /*
1064 * Get pruning step for each arg. If we get contradictory for
1065 * all args, it means the OR expression is false as a whole.
1066 */
1067 foreach(lc1, ((BoolExpr *) clause)->args)
1068 {
1069 Expr *arg = lfirst(lc1);
1070 bool arg_contradictory;
1071 List *argsteps;
1072
1073 argsteps = gen_partprune_steps_internal(context,
1074 list_make1(arg));
1075 arg_contradictory = context->contradictory;
1076 /* Keep context->contradictory clear till we're done */
1077 context->contradictory = false;
1078
1079 if (arg_contradictory)
1080 {
1081 /* Just ignore self-contradictory arguments. */
1082 continue;
1083 }
1084 else
1085 all_args_contradictory = false;
1086
1087 if (argsteps != NIL)
1088 {
1089 /*
1090 * gen_partprune_steps_internal() always adds a single
1091 * combine step when it generates multiple steps, so
1092 * here we can just pay attention to the last one in
1093 * the list. If it just generated one, then the last
1094 * one in the list is still the one we want.
1095 */
1096 PartitionPruneStep *last = llast(argsteps);
1097
1098 arg_stepids = lappend_int(arg_stepids, last->step_id);
1099 }
1100 else
1101 {
1102 PartitionPruneStep *orstep;
1103
1104 /*
1105 * The arg didn't contain a clause matching this
1106 * partition key. We cannot prune using such an arg.
1107 * To indicate that to the pruning code, we must
1108 * construct a dummy PartitionPruneStepCombine whose
1109 * source_stepids is set to an empty List.
1110 */
1111 orstep = gen_prune_step_combine(context, NIL,
1112 PARTPRUNE_COMBINE_UNION);
1113 arg_stepids = lappend_int(arg_stepids, orstep->step_id);
1114 }
1115 }
1116
1117 /* If all the OR arms are contradictory, we can stop */
1118 if (all_args_contradictory)
1119 {
1120 context->contradictory = true;
1121 return NIL;
1122 }
1123
1124 if (arg_stepids != NIL)
1125 {
1126 PartitionPruneStep *step;
1127
1128 step = gen_prune_step_combine(context, arg_stepids,
1129 PARTPRUNE_COMBINE_UNION);
1130 result = lappend(result, step);
1131 }
1132 continue;
1133 }
1134 else if (is_andclause(clause))
1135 {
1136 List *args = ((BoolExpr *) clause)->args;
1137 List *argsteps;
1138
1139 /*
1140 * args may itself contain clauses of arbitrary type, so just
1141 * recurse and later combine the component partitions sets
1142 * using a combine step.
1143 */
1144 argsteps = gen_partprune_steps_internal(context, args);
1145
1146 /* If any AND arm is contradictory, we can stop immediately */
1147 if (context->contradictory)
1148 return NIL;
1149
1150 /*
1151 * gen_partprune_steps_internal() always adds a single combine
1152 * step when it generates multiple steps, so here we can just
1153 * pay attention to the last one in the list. If it just
1154 * generated one, then the last one in the list is still the
1155 * one we want.
1156 */
1157 if (argsteps != NIL)
1158 result = lappend(result, llast(argsteps));
1159
1160 continue;
1161 }
1162
1163 /*
1164 * Fall-through for a NOT clause, which if it's a Boolean clause,
1165 * will be handled in match_clause_to_partition_key(). We
1166 * currently don't perform any pruning for more complex NOT
1167 * clauses.
1168 */
1169 }
1170
1171 /*
1172 * See if we can match this clause to any of the partition keys.
1173 */
1174 for (i = 0; i < part_scheme->partnatts; i++)
1175 {
1176 Expr *partkey = linitial(context->rel->partexprs[i]);
1177 bool clause_is_not_null = false;
1178 PartClauseInfo *pc = NULL;
1179 List *clause_steps = NIL;
1180
1181 switch (match_clause_to_partition_key(context,
1182 clause, partkey, i,
1183 &clause_is_not_null,
1184 &pc, &clause_steps))
1185 {
1186 case PARTCLAUSE_MATCH_CLAUSE:
1187 Assert(pc != NULL);
1188
1189 /*
1190 * Since we only allow strict operators, check for any
1191 * contradicting IS NULL.
1192 */
1193 if (bms_is_member(i, nullkeys))
1194 {
1195 context->contradictory = true;
1196 return NIL;
1197 }
1198 generate_opsteps = true;
1199 keyclauses[i] = lappend(keyclauses[i], pc);
1200 break;
1201
1202 case PARTCLAUSE_MATCH_NULLNESS:
1203 if (!clause_is_not_null)
1204 {
1205 /*
1206 * check for conflicting IS NOT NULL as well as
1207 * contradicting strict clauses
1208 */
1209 if (bms_is_member(i, notnullkeys) ||
1210 keyclauses[i] != NIL)
1211 {
1212 context->contradictory = true;
1213 return NIL;
1214 }
1215 nullkeys = bms_add_member(nullkeys, i);
1216 }
1217 else
1218 {
1219 /* check for conflicting IS NULL */
1220 if (bms_is_member(i, nullkeys))
1221 {
1222 context->contradictory = true;
1223 return NIL;
1224 }
1225 notnullkeys = bms_add_member(notnullkeys, i);
1226 }
1227 break;
1228
1229 case PARTCLAUSE_MATCH_STEPS:
1230 Assert(clause_steps != NIL);
1231 result = list_concat(result, clause_steps);
1232 break;
1233
1234 case PARTCLAUSE_MATCH_CONTRADICT:
1235 /* We've nothing more to do if a contradiction was found. */
1236 context->contradictory = true;
1237 return NIL;
1238
1239 case PARTCLAUSE_NOMATCH:
1240
1241 /*
1242 * Clause didn't match this key, but it might match the
1243 * next one.
1244 */
1245 continue;
1246
1247 case PARTCLAUSE_UNSUPPORTED:
1248 /* This clause cannot be used for pruning. */
1249 break;
1250 }
1251
1252 /* done; go check the next clause. */
1253 break;
1254 }
1255 }
1256
1257 /*-----------
1258 * Now generate some (more) pruning steps. We have three strategies:
1259 *
1260 * 1) Generate pruning steps based on IS NULL clauses:
1261 * a) For list partitioning, null partition keys can only be found in
1262 * the designated null-accepting partition, so if there are IS NULL
1263 * clauses containing partition keys we should generate a pruning
1264 * step that gets rid of all partitions but that one. We can
1265 * disregard any OpExpr we may have found.
1266 * b) For range partitioning, only the default partition can contain
1267 * NULL values, so the same rationale applies.
1268 * c) For hash partitioning, we only apply this strategy if we have
1269 * IS NULL clauses for all the keys. Strategy 2 below will take
1270 * care of the case where some keys have OpExprs and others have
1271 * IS NULL clauses.
1272 *
1273 * 2) If not, generate steps based on OpExprs we have (if any).
1274 *
1275 * 3) If this doesn't work either, we may be able to generate steps to
1276 * prune just the null-accepting partition (if one exists), if we have
1277 * IS NOT NULL clauses for all partition keys.
1278 */
1279 if (!bms_is_empty(nullkeys) &&
1280 (part_scheme->strategy == PARTITION_STRATEGY_LIST ||
1281 part_scheme->strategy == PARTITION_STRATEGY_RANGE ||
1282 (part_scheme->strategy == PARTITION_STRATEGY_HASH &&
1283 bms_num_members(nullkeys) == part_scheme->partnatts)))
1284 {
1285 PartitionPruneStep *step;
1286
1287 /* Strategy 1 */
1288 step = gen_prune_step_op(context, InvalidStrategy,
1289 false, NIL, NIL, nullkeys);
1290 result = lappend(result, step);
1291 }
1292 else if (generate_opsteps)
1293 {
1294 List *opsteps;
1295
1296 /* Strategy 2 */
1297 opsteps = gen_prune_steps_from_opexps(context, keyclauses, nullkeys);
1298 result = list_concat(result, opsteps);
1299 }
1300 else if (bms_num_members(notnullkeys) == part_scheme->partnatts)
1301 {
1302 PartitionPruneStep *step;
1303
1304 /* Strategy 3 */
1305 step = gen_prune_step_op(context, InvalidStrategy,
1306 false, NIL, NIL, NULL);
1307 result = lappend(result, step);
1308 }
1309
1310 /*
1311 * Finally, if there are multiple steps, since the 'clauses' are mutually
1312 * ANDed, add an INTERSECT step to combine the partition sets resulting
1313 * from them and append it to the result list.
1314 */
1315 if (list_length(result) > 1)
1316 {
1317 List *step_ids = NIL;
1318 PartitionPruneStep *final;
1319
1320 foreach(lc, result)
1321 {
1322 PartitionPruneStep *step = lfirst(lc);
1323
1324 step_ids = lappend_int(step_ids, step->step_id);
1325 }
1326
1327 final = gen_prune_step_combine(context, step_ids,
1328 PARTPRUNE_COMBINE_INTERSECT);
1329 result = lappend(result, final);
1330 }
1331
1332 return result;
1333 }
1334
1335 /*
1336 * gen_prune_step_op
1337 * Generate a pruning step for a specific operator
1338 *
1339 * The step is assigned a unique step identifier and added to context's 'steps'
1340 * list.
1341 */
1342 static PartitionPruneStep *
1343 gen_prune_step_op(GeneratePruningStepsContext *context,
1344 StrategyNumber opstrategy, bool op_is_ne,
1345 List *exprs, List *cmpfns,
1346 Bitmapset *nullkeys)
1347 {
1348 PartitionPruneStepOp *opstep = makeNode(PartitionPruneStepOp);
1349
1350 opstep->step.step_id = context->next_step_id++;
1351
1352 /*
1353 * For clauses that contain an <> operator, set opstrategy to
1354 * InvalidStrategy to signal get_matching_list_bounds to do the right
1355 * thing.
1356 */
1357 opstep->opstrategy = op_is_ne ? InvalidStrategy : opstrategy;
1358 Assert(list_length(exprs) == list_length(cmpfns));
1359 opstep->exprs = exprs;
1360 opstep->cmpfns = cmpfns;
1361 opstep->nullkeys = nullkeys;
1362
1363 context->steps = lappend(context->steps, opstep);
1364
1365 return (PartitionPruneStep *) opstep;
1366 }
1367
1368 /*
1369 * gen_prune_step_combine
1370 * Generate a pruning step for a combination of several other steps
1371 *
1372 * The step is assigned a unique step identifier and added to context's
1373 * 'steps' list.
1374 */
1375 static PartitionPruneStep *
1376 gen_prune_step_combine(GeneratePruningStepsContext *context,
1377 List *source_stepids,
1378 PartitionPruneCombineOp combineOp)
1379 {
1380 PartitionPruneStepCombine *cstep = makeNode(PartitionPruneStepCombine);
1381
1382 cstep->step.step_id = context->next_step_id++;
1383 cstep->combineOp = combineOp;
1384 cstep->source_stepids = source_stepids;
1385
1386 context->steps = lappend(context->steps, cstep);
1387
1388 return (PartitionPruneStep *) cstep;
1389 }
1390
1391 /*
1392 * gen_prune_steps_from_opexps
1393 * Generate and return a list of PartitionPruneStepOp that are based on
1394 * OpExpr and BooleanTest clauses that have been matched to the partition
1395 * key.
1396 *
1397 * 'keyclauses' is an array of List pointers, indexed by the partition key's
1398 * index. Each List element in the array can contain clauses that match to
1399 * the corresponding partition key column. Partition key columns without any
1400 * matched clauses will have an empty List.
1401 *
1402 * Some partitioning strategies allow pruning to still occur when we only have
1403 * clauses for a prefix of the partition key columns, for example, RANGE
1404 * partitioning. Other strategies, such as HASH partitioning, require clauses
1405 * for all partition key columns.
1406 *
1407 * When we return multiple pruning steps here, it's up to the caller to add a
1408 * relevant "combine" step to combine the returned steps. This is not done
1409 * here as callers may wish to include additional pruning steps before
1410 * combining them all.
1411 */
1412 static List *
1413 gen_prune_steps_from_opexps(GeneratePruningStepsContext *context,
1414 List **keyclauses, Bitmapset *nullkeys)
1415 {
1416 PartitionScheme part_scheme = context->rel->part_scheme;
1417 List *opsteps = NIL;
1418 List *btree_clauses[BTMaxStrategyNumber + 1],
1419 *hash_clauses[HTMaxStrategyNumber + 1];
1420 int i;
1421 ListCell *lc;
1422
1423 memset(btree_clauses, 0, sizeof(btree_clauses));
1424 memset(hash_clauses, 0, sizeof(hash_clauses));
1425 for (i = 0; i < part_scheme->partnatts; i++)
1426 {
1427 List *clauselist = keyclauses[i];
1428 bool consider_next_key = true;
1429
1430 /*
1431 * For range partitioning, if we have no clauses for the current key,
1432 * we can't consider any later keys either, so we can stop here.
1433 */
1434 if (part_scheme->strategy == PARTITION_STRATEGY_RANGE &&
1435 clauselist == NIL)
1436 break;
1437
1438 /*
1439 * For hash partitioning, if a column doesn't have the necessary
1440 * equality clause, there should be an IS NULL clause, otherwise
1441 * pruning is not possible.
1442 */
1443 if (part_scheme->strategy == PARTITION_STRATEGY_HASH &&
1444 clauselist == NIL && !bms_is_member(i, nullkeys))
1445 return NIL;
1446
1447 foreach(lc, clauselist)
1448 {
1449 PartClauseInfo *pc = (PartClauseInfo *) lfirst(lc);
1450 Oid lefttype,
1451 righttype;
1452
1453 /* Look up the operator's btree/hash strategy number. */
1454 if (pc->op_strategy == InvalidStrategy)
1455 get_op_opfamily_properties(pc->opno,
1456 part_scheme->partopfamily[i],
1457 false,
1458 &pc->op_strategy,
1459 &lefttype,
1460 &righttype);
1461
1462 switch (part_scheme->strategy)
1463 {
1464 case PARTITION_STRATEGY_LIST:
1465 case PARTITION_STRATEGY_RANGE:
1466 btree_clauses[pc->op_strategy] =
1467 lappend(btree_clauses[pc->op_strategy], pc);
1468
1469 /*
1470 * We can't consider subsequent partition keys if the
1471 * clause for the current key contains a non-inclusive
1472 * operator.
1473 */
1474 if (pc->op_strategy == BTLessStrategyNumber ||
1475 pc->op_strategy == BTGreaterStrategyNumber)
1476 consider_next_key = false;
1477 break;
1478
1479 case PARTITION_STRATEGY_HASH:
1480 if (pc->op_strategy != HTEqualStrategyNumber)
1481 elog(ERROR, "invalid clause for hash partitioning");
1482 hash_clauses[pc->op_strategy] =
1483 lappend(hash_clauses[pc->op_strategy], pc);
1484 break;
1485
1486 default:
1487 elog(ERROR, "invalid partition strategy: %c",
1488 part_scheme->strategy);
1489 break;
1490 }
1491 }
1492
1493 /*
1494 * If we've decided that clauses for subsequent partition keys
1495 * wouldn't be useful for pruning, don't search any further.
1496 */
1497 if (!consider_next_key)
1498 break;
1499 }
1500
1501 /*
1502 * Now, we have divided clauses according to their operator strategies.
1503 * Check for each strategy if we can generate pruning step(s) by
1504 * collecting a list of expressions whose values will constitute a vector
1505 * that can be used as a lookup key by a partition bound searching
1506 * function.
1507 */
1508 switch (part_scheme->strategy)
1509 {
1510 case PARTITION_STRATEGY_LIST:
1511 case PARTITION_STRATEGY_RANGE:
1512 {
1513 List *eq_clauses = btree_clauses[BTEqualStrategyNumber];
1514 List *le_clauses = btree_clauses[BTLessEqualStrategyNumber];
1515 List *ge_clauses = btree_clauses[BTGreaterEqualStrategyNumber];
1516 int strat;
1517
1518 /*
1519 * For each clause under consideration for a given strategy,
1520 * we collect expressions from clauses for earlier keys, whose
1521 * operator strategy is inclusive, into a list called
1522 * 'prefix'. By appending the clause's own expression to the
1523 * 'prefix', we'll generate one step using the so generated
1524 * vector and assign the current strategy to it. Actually,
1525 * 'prefix' might contain multiple clauses for the same key,
1526 * in which case, we must generate steps for various
1527 * combinations of expressions of different keys, which
1528 * get_steps_using_prefix takes care of for us.
1529 */
1530 for (strat = 1; strat <= BTMaxStrategyNumber; strat++)
1531 {
1532 foreach(lc, btree_clauses[strat])
1533 {
1534 PartClauseInfo *pc = lfirst(lc);
1535 ListCell *eq_start;
1536 ListCell *le_start;
1537 ListCell *ge_start;
1538 ListCell *lc1;
1539 List *prefix = NIL;
1540 List *pc_steps;
1541 bool prefix_valid = true;
1542 bool pk_has_clauses;
1543 int keyno;
1544
1545 /*
1546 * If this is a clause for the first partition key,
1547 * there are no preceding expressions; generate a
1548 * pruning step without a prefix.
1549 *
1550 * Note that we pass NULL for step_nullkeys, because
1551 * we don't search list/range partition bounds where
1552 * some keys are NULL.
1553 */
1554 if (pc->keyno == 0)
1555 {
1556 Assert(pc->op_strategy == strat);
1557 pc_steps = get_steps_using_prefix(context, strat,
1558 pc->op_is_ne,
1559 pc->expr,
1560 pc->cmpfn,
1561 NULL,
1562 NIL);
1563 opsteps = list_concat(opsteps, pc_steps);
1564 continue;
1565 }
1566
1567 eq_start = list_head(eq_clauses);
1568 le_start = list_head(le_clauses);
1569 ge_start = list_head(ge_clauses);
1570
1571 /*
1572 * We arrange clauses into prefix in ascending order
1573 * of their partition key numbers.
1574 */
1575 for (keyno = 0; keyno < pc->keyno; keyno++)
1576 {
1577 pk_has_clauses = false;
1578
1579 /*
1580 * Expressions from = clauses can always be in the
1581 * prefix, provided they're from an earlier key.
1582 */
1583 for_each_cell(lc1, eq_clauses, eq_start)
1584 {
1585 PartClauseInfo *eqpc = lfirst(lc1);
1586
1587 if (eqpc->keyno == keyno)
1588 {
1589 prefix = lappend(prefix, eqpc);
1590 pk_has_clauses = true;
1591 }
1592 else
1593 {
1594 Assert(eqpc->keyno > keyno);
1595 break;
1596 }
1597 }
1598 eq_start = lc1;
1599
1600 /*
1601 * If we're generating steps for </<= strategy, we
1602 * can add other <= clauses to the prefix,
1603 * provided they're from an earlier key.
1604 */
1605 if (strat == BTLessStrategyNumber ||
1606 strat == BTLessEqualStrategyNumber)
1607 {
1608 for_each_cell(lc1, le_clauses, le_start)
1609 {
1610 PartClauseInfo *lepc = lfirst(lc1);
1611
1612 if (lepc->keyno == keyno)
1613 {
1614 prefix = lappend(prefix, lepc);
1615 pk_has_clauses = true;
1616 }
1617 else
1618 {
1619 Assert(lepc->keyno > keyno);
1620 break;
1621 }
1622 }
1623 le_start = lc1;
1624 }
1625
1626 /*
1627 * If we're generating steps for >/>= strategy, we
1628 * can add other >= clauses to the prefix,
1629 * provided they're from an earlier key.
1630 */
1631 if (strat == BTGreaterStrategyNumber ||
1632 strat == BTGreaterEqualStrategyNumber)
1633 {
1634 for_each_cell(lc1, ge_clauses, ge_start)
1635 {
1636 PartClauseInfo *gepc = lfirst(lc1);
1637
1638 if (gepc->keyno == keyno)
1639 {
1640 prefix = lappend(prefix, gepc);
1641 pk_has_clauses = true;
1642 }
1643 else
1644 {
1645 Assert(gepc->keyno > keyno);
1646 break;
1647 }
1648 }
1649 ge_start = lc1;
1650 }
1651
1652 /*
1653 * If this key has no clauses, prefix is not valid
1654 * anymore.
1655 */
1656 if (!pk_has_clauses)
1657 {
1658 prefix_valid = false;
1659 break;
1660 }
1661 }
1662
1663 /*
1664 * If prefix_valid, generate PartitionPruneStepOps.
1665 * Otherwise, we would not find clauses for a valid
1666 * subset of the partition keys anymore for the
1667 * strategy; give up on generating partition pruning
1668 * steps further for the strategy.
1669 *
1670 * As mentioned above, if 'prefix' contains multiple
1671 * expressions for the same key, the following will
1672 * generate multiple steps, one for each combination
1673 * of the expressions for different keys.
1674 *
1675 * Note that we pass NULL for step_nullkeys, because
1676 * we don't search list/range partition bounds where
1677 * some keys are NULL.
1678 */
1679 if (prefix_valid)
1680 {
1681 Assert(pc->op_strategy == strat);
1682 pc_steps = get_steps_using_prefix(context, strat,
1683 pc->op_is_ne,
1684 pc->expr,
1685 pc->cmpfn,
1686 NULL,
1687 prefix);
1688 opsteps = list_concat(opsteps, pc_steps);
1689 }
1690 else
1691 break;
1692 }
1693 }
1694 break;
1695 }
1696
1697 case PARTITION_STRATEGY_HASH:
1698 {
1699 List *eq_clauses = hash_clauses[HTEqualStrategyNumber];
1700
1701 /* For hash partitioning, we have just the = strategy. */
1702 if (eq_clauses != NIL)
1703 {
1704 PartClauseInfo *pc;
1705 List *pc_steps;
1706 List *prefix = NIL;
1707 int last_keyno;
1708 ListCell *lc1;
1709
1710 /*
1711 * Locate the clause for the greatest column. This may
1712 * not belong to the last partition key, but it is the
1713 * clause belonging to the last partition key we found a
1714 * clause for above.
1715 */
1716 pc = llast(eq_clauses);
1717
1718 /*
1719 * There might be multiple clauses which matched to that
1720 * partition key; find the first such clause. While at
1721 * it, add all the clauses before that one to 'prefix'.
1722 */
1723 last_keyno = pc->keyno;
1724 foreach(lc, eq_clauses)
1725 {
1726 pc = lfirst(lc);
1727 if (pc->keyno == last_keyno)
1728 break;
1729 prefix = lappend(prefix, pc);
1730 }
1731
1732 /*
1733 * For each clause for the "last" column, after appending
1734 * the clause's own expression to the 'prefix', we'll
1735 * generate one step using the so generated vector and
1736 * assign = as its strategy. Actually, 'prefix' might
1737 * contain multiple clauses for the same key, in which
1738 * case, we must generate steps for various combinations
1739 * of expressions of different keys, which
1740 * get_steps_using_prefix will take care of for us.
1741 */
1742 for_each_cell(lc1, eq_clauses, lc)
1743 {
1744 pc = lfirst(lc1);
1745
1746 /*
1747 * Note that we pass nullkeys for step_nullkeys,
1748 * because we need to tell hash partition bound search
1749 * function which of the keys we found IS NULL clauses
1750 * for.
1751 */
1752 Assert(pc->op_strategy == HTEqualStrategyNumber);
1753 pc_steps =
1754 get_steps_using_prefix(context,
1755 HTEqualStrategyNumber,
1756 false,
1757 pc->expr,
1758 pc->cmpfn,
1759 nullkeys,
1760 prefix);
1761 opsteps = list_concat(opsteps, pc_steps);
1762 }
1763 }
1764 break;
1765 }
1766
1767 default:
1768 elog(ERROR, "invalid partition strategy: %c",
1769 part_scheme->strategy);
1770 break;
1771 }
1772
1773 return opsteps;
1774 }
1775
1776 /*
1777 * If the partition key has a collation, then the clause must have the same
1778 * input collation. If the partition key is non-collatable, we assume the
1779 * collation doesn't matter, because while collation wasn't considered when
1780 * performing partitioning, the clause still may have a collation assigned
1781 * due to the other input being of a collatable type.
1782 *
1783 * See also IndexCollMatchesExprColl.
1784 */
1785 #define PartCollMatchesExprColl(partcoll, exprcoll) \
1786 ((partcoll) == InvalidOid || (partcoll) == (exprcoll))
1787
1788 /*
1789 * match_clause_to_partition_key
1790 * Attempt to match the given 'clause' with the specified partition key.
1791 *
1792 * Return value is:
1793 * * PARTCLAUSE_NOMATCH if the clause doesn't match this partition key (but
1794 * caller should keep trying, because it might match a subsequent key).
1795 * Output arguments: none set.
1796 *
1797 * * PARTCLAUSE_MATCH_CLAUSE if there is a match.
1798 * Output arguments: *pc is set to a PartClauseInfo constructed for the
1799 * matched clause.
1800 *
1801 * * PARTCLAUSE_MATCH_NULLNESS if there is a match, and the matched clause was
1802 * either a "a IS NULL" or "a IS NOT NULL" clause.
1803 * Output arguments: *clause_is_not_null is set to false in the former case
1804 * true otherwise.
1805 *
1806 * * PARTCLAUSE_MATCH_STEPS if there is a match.
1807 * Output arguments: *clause_steps is set to the list of recursively
1808 * generated steps for the clause.
1809 *
1810 * * PARTCLAUSE_MATCH_CONTRADICT if the clause is self-contradictory, ie
1811 * it provably returns FALSE or NULL.
1812 * Output arguments: none set.
1813 *
1814 * * PARTCLAUSE_UNSUPPORTED if the clause doesn't match this partition key
1815 * and couldn't possibly match any other one either, due to its form or
1816 * properties (such as containing a volatile function).
1817 * Output arguments: none set.
1818 *
1819 * Note that when pulling up a subquery, the clause operands may get wrapped
1820 * in PlaceHolderVars to enforce separate identity or as a result of outer
1821 * joins. We must strip such no-op PlaceHolderVars before comparing operands
1822 * to the partition key, otherwise the equal() checks will fail to recognize
1823 * valid matches. This is safe because the clauses here are always
1824 * relation-scan-level expressions, where a PlaceHolderVar with empty
1825 * phnullingrels is effectively a no-op. Stripping may also bring separate
1826 * RelabelType nodes into adjacency, so we must loop when peeling those.
1827 */
1828 static PartClauseMatchStatus
1829 match_clause_to_partition_key(GeneratePruningStepsContext *context,
1830 Expr *clause, Expr *partkey, int partkeyidx,
1831 bool *clause_is_not_null, PartClauseInfo **pc,
1832 List **clause_steps)
1833 {
1834 PartClauseMatchStatus boolmatchstatus;
1835 PartitionScheme part_scheme = context->rel->part_scheme;
1836 Oid partopfamily = part_scheme->partopfamily[partkeyidx],
1837 partcoll = part_scheme->partcollation[partkeyidx];
1838 Expr *expr;
1839 bool notclause;
1840
1841 /*
1842 * Recognize specially shaped clauses that match a Boolean partition key.
1843 */
1844 boolmatchstatus = match_boolean_partition_clause(partopfamily, clause,
1845 partkey, &expr,
1846 &notclause);
1847
1848 if (boolmatchstatus == PARTCLAUSE_MATCH_CLAUSE)
1849 {
1850 PartClauseInfo *partclause;
1851
1852 /*
1853 * For bool tests in the form of partkey IS NOT true and IS NOT false,
1854 * we invert these clauses. Effectively, "partkey IS NOT true"
1855 * becomes "partkey IS false OR partkey IS NULL". We do this by
1856 * building an OR BoolExpr and forming a clause just like that and
1857 * punt it off to gen_partprune_steps_internal() to generate pruning
1858 * steps.
1859 */
1860 if (notclause)
1861 {
1862 List *new_clauses;
1863 List *or_clause;
1864 BooleanTest *new_booltest = (BooleanTest *) copyObject(clause);
1865 NullTest *nulltest;
1866
1867 /* We expect 'notclause' to only be set to true for BooleanTests */
1868 Assert(IsA(clause, BooleanTest));
1869
1870 /* reverse the bool test */
1871 if (new_booltest->booltesttype == IS_NOT_TRUE)
1872 new_booltest->booltesttype = IS_FALSE;
1873 else if (new_booltest->booltesttype == IS_NOT_FALSE)
1874 new_booltest->booltesttype = IS_TRUE;
1875 else
1876 {
1877 /*
1878 * We only expect match_boolean_partition_clause to return
1879 * PARTCLAUSE_MATCH_CLAUSE for IS_NOT_TRUE and IS_NOT_FALSE.
1880 */
1881 Assert(false);
1882 }
1883
1884 nulltest = makeNode(NullTest);
1885 nulltest->arg = copyObject(partkey);
1886 nulltest->nulltesttype = IS_NULL;
1887 nulltest->argisrow = false;
1888 nulltest->location = -1;
1889
1890 new_clauses = list_make2(new_booltest, nulltest);
1891 or_clause = list_make1(makeBoolExpr(OR_EXPR, new_clauses, -1));
1892
1893 /* Finally, generate steps */
1894 *clause_steps = gen_partprune_steps_internal(context, or_clause);
1895
1896 if (context->contradictory)
1897 return PARTCLAUSE_MATCH_CONTRADICT; /* shouldn't happen */
1898 else if (*clause_steps == NIL)
1899 return PARTCLAUSE_UNSUPPORTED; /* step generation failed */
1900 return PARTCLAUSE_MATCH_STEPS;
1901 }
1902
1903 partclause = (PartClauseInfo *) palloc(sizeof(PartClauseInfo));
1904 partclause->keyno = partkeyidx;
1905 /* Do pruning with the Boolean equality operator. */
1906 partclause->opno = BooleanEqualOperator;
1907 partclause->op_is_ne = false;
1908 partclause->expr = expr;
1909 /* We know that expr is of Boolean type. */
1910 partclause->cmpfn = part_scheme->partsupfunc[partkeyidx].fn_oid;
1911 partclause->op_strategy = InvalidStrategy;
1912
1913 *pc = partclause;
1914
1915 return PARTCLAUSE_MATCH_CLAUSE;
1916 }
1917 else if (boolmatchstatus == PARTCLAUSE_MATCH_NULLNESS)
1918 {
1919 /*
1920 * Handle IS UNKNOWN and IS NOT UNKNOWN. These just logically
1921 * translate to IS NULL and IS NOT NULL.
1922 */
1923 *clause_is_not_null = notclause;
1924 return PARTCLAUSE_MATCH_NULLNESS;
1925 }
1926 else if (IsA(clause, OpExpr) &&
1927 list_length(((OpExpr *) clause)->args) == 2)
1928 {
1929 OpExpr *opclause = (OpExpr *) clause;
1930 Expr *leftop,
1931 *rightop;
1932 Oid opno,
1933 op_lefttype,
1934 op_righttype,
1935 negator = InvalidOid;
1936 Oid cmpfn;
1937 int op_strategy;
1938 bool is_opne_listp = false;
1939 PartClauseInfo *partclause;
1940
1941 leftop = (Expr *) get_leftop(clause);
1942 leftop = (Expr *) strip_noop_phvs((Node *) leftop);
1943 while (IsA(leftop, RelabelType))
1944 leftop = ((RelabelType *) leftop)->arg;
1945 rightop = (Expr *) get_rightop(clause);
1946 rightop = (Expr *) strip_noop_phvs((Node *) rightop);
1947 while (IsA(rightop, RelabelType))
1948 rightop = ((RelabelType *) rightop)->arg;
1949 opno = opclause->opno;
1950
1951 /* check if the clause matches this partition key */
1952 if (equal(leftop, partkey))
1953 expr = rightop;
1954 else if (equal(rightop, partkey))
1955 {
1956 /*
1957 * It's only useful if we can commute the operator to put the
1958 * partkey on the left. If we can't, the clause can be deemed
1959 * UNSUPPORTED. Even if its leftop matches some later partkey, we
1960 * now know it has Vars on the right, so it's no use.
1961 */
1962 opno = get_commutator(opno);
1963 if (!OidIsValid(opno))
1964 return PARTCLAUSE_UNSUPPORTED;
1965 expr = leftop;
1966 }
1967 else
1968 /* clause does not match this partition key, but perhaps next. */
1969 return PARTCLAUSE_NOMATCH;
1970
1971 /*
1972 * Partition key match also requires collation match. There may be
1973 * multiple partkeys with the same expression but different
1974 * collations, so failure is NOMATCH.
1975 */
1976 if (!PartCollMatchesExprColl(partcoll, opclause->inputcollid))
1977 return PARTCLAUSE_NOMATCH;
1978
1979 /*
1980 * See if the operator is relevant to the partitioning opfamily.
1981 *
1982 * Normally we only care about operators that are listed as being part
1983 * of the partitioning operator family. But there is one exception:
1984 * the not-equals operators are not listed in any operator family
1985 * whatsoever, but their negators (equality) are. We can use one of
1986 * those if we find it, but only for list partitioning.
1987 *
1988 * Note: we report NOMATCH on failure if the negator isn't the
1989 * equality operator for the partkey's opfamily as other partkeys may
1990 * have the same expression but different opfamily. That's unlikely,
1991 * but not much more so than duplicate expressions with different
1992 * collations.
1993 */
1994 if (op_in_opfamily(opno, partopfamily))
1995 {
1996 get_op_opfamily_properties(opno, partopfamily, false,
1997 &op_strategy, &op_lefttype,
1998 &op_righttype);
1999 }
2000 else
2001 {
2002 /* not supported for anything apart from LIST partitioned tables */
2003 if (part_scheme->strategy != PARTITION_STRATEGY_LIST)
2004 return PARTCLAUSE_UNSUPPORTED;
2005
2006 /* See if the negator is equality */
2007 negator = get_negator(opno);
2008 if (OidIsValid(negator) && op_in_opfamily(negator, partopfamily))
2009 {
2010 get_op_opfamily_properties(negator, partopfamily, false,
2011 &op_strategy, &op_lefttype,
2012 &op_righttype);
2013 if (op_strategy == BTEqualStrategyNumber)
2014 is_opne_listp = true; /* bingo */
2015 }
2016
2017 /* Nope, it's not <> either. */
2018 if (!is_opne_listp)
2019 return PARTCLAUSE_NOMATCH;
2020 }
2021
2022 /*
2023 * Only allow strict operators. This will guarantee nulls are
2024 * filtered. (This test is likely useless, since btree and hash
2025 * comparison operators are generally strict.)
2026 */
2027 if (!op_strict(opno))
2028 return PARTCLAUSE_UNSUPPORTED;
2029
2030 /*
2031 * OK, we have a match to the partition key and a suitable operator.
2032 * Examine the other argument to see if it's usable for pruning.
2033 *
2034 * In most of these cases, we can return UNSUPPORTED because the same
2035 * failure would occur no matter which partkey it's matched to. (In
2036 * particular, now that we've successfully matched one side of the
2037 * opclause to a partkey, there is no chance that matching the other
2038 * side to another partkey will produce a usable result, since that'd
2039 * mean there are Vars on both sides.)
2040 *
2041 * Also, if we reject an argument for a target-dependent reason, set
2042 * appropriate fields of *context to report that. We postpone these
2043 * tests until after matching the partkey and the operator, so as to
2044 * reduce the odds of setting the context fields for clauses that do
2045 * not end up contributing to pruning steps.
2046 *
2047 * First, check for non-Const argument. (We assume that any immutable
2048 * subexpression will have been folded to a Const already.)
2049 */
2050 if (!IsA(expr, Const))
2051 {
2052 Bitmapset *paramids;
2053
2054 /*
2055 * When pruning in the planner, we only support pruning using
2056 * comparisons to constants. We cannot prune on the basis of
2057 * anything that's not immutable. (Note that has_mutable_arg and
2058 * has_exec_param do not get set for this target value.)
2059 */
2060 if (context->target == PARTTARGET_PLANNER)
2061 return PARTCLAUSE_UNSUPPORTED;
2062
2063 /*
2064 * We can never prune using an expression that contains Vars.
2065 */
2066 if (contain_var_clause((Node *) expr))
2067 return PARTCLAUSE_UNSUPPORTED;
2068
2069 /*
2070 * And we must reject anything containing a volatile function.
2071 * Stable functions are OK though.
2072 */
2073 if (contain_volatile_functions((Node *) expr))
2074 return PARTCLAUSE_UNSUPPORTED;
2075
2076 /*
2077 * See if there are any exec Params. If so, we can only use this
2078 * expression during per-scan pruning.
2079 */
2080 paramids = pull_exec_paramids(expr);
2081 if (!bms_is_empty(paramids))
2082 {
2083 context->has_exec_param = true;
2084 if (context->target != PARTTARGET_EXEC)
2085 return PARTCLAUSE_UNSUPPORTED;
2086 }
2087 else
2088 {
2089 /* It's potentially usable, but mutable */
2090 context->has_mutable_arg = true;
2091 }
2092 }
2093
2094 /*
2095 * Check whether the comparison operator itself is immutable. (We
2096 * assume anything that's in a btree or hash opclass is at least
2097 * stable, but we need to check for immutability.)
2098 */
2099 if (op_volatile(opno) != PROVOLATILE_IMMUTABLE)
2100 {
2101 context->has_mutable_op = true;
2102
2103 /*
2104 * When pruning in the planner, we cannot prune with mutable
2105 * operators.
2106 */
2107 if (context->target == PARTTARGET_PLANNER)
2108 return PARTCLAUSE_UNSUPPORTED;
2109 }
2110
2111 /*
2112 * Now find the procedure to use, based on the types. If the clause's
2113 * other argument is of the same type as the partitioning opclass's
2114 * declared input type, we can use the procedure cached in
2115 * PartitionKey. If not, search for a cross-type one in the same
2116 * opfamily; if one doesn't exist, report no match.
2117 */
2118 if (op_righttype == part_scheme->partopcintype[partkeyidx])
2119 cmpfn = part_scheme->partsupfunc[partkeyidx].fn_oid;
2120 else
2121 {
2122 switch (part_scheme->strategy)
2123 {
2124 /*
2125 * For range and list partitioning, we need the ordering
2126 * procedure with lefttype being the partition key's type,
2127 * and righttype the clause's operator's right type.
2128 */
2129 case PARTITION_STRATEGY_LIST:
2130 case PARTITION_STRATEGY_RANGE:
2131 cmpfn =
2132 get_opfamily_proc(part_scheme->partopfamily[partkeyidx],
2133 part_scheme->partopcintype[partkeyidx],
2134 op_righttype, BTORDER_PROC);
2135 break;
2136
2137 /*
2138 * For hash partitioning, we need the hashing procedure
2139 * for the clause's type.
2140 */
2141 case PARTITION_STRATEGY_HASH:
2142 cmpfn =
2143 get_opfamily_proc(part_scheme->partopfamily[partkeyidx],
2144 op_righttype, op_righttype,
2145 HASHEXTENDED_PROC);
2146 break;
2147
2148 default:
2149 elog(ERROR, "invalid partition strategy: %c",
2150 part_scheme->strategy);
2151 cmpfn = InvalidOid; /* keep compiler quiet */
2152 break;
2153 }
2154
2155 if (!OidIsValid(cmpfn))
2156 return PARTCLAUSE_NOMATCH;
2157 }
2158
2159 /*
2160 * Build the clause, passing the negator if applicable.
2161 */
2162 partclause = (PartClauseInfo *) palloc(sizeof(PartClauseInfo));
2163 partclause->keyno = partkeyidx;
2164 if (is_opne_listp)
2165 {
2166 Assert(OidIsValid(negator));
2167 partclause->opno = negator;
2168 partclause->op_is_ne = true;
2169 partclause->op_strategy = InvalidStrategy;
2170 }
2171 else
2172 {
2173 partclause->opno = opno;
2174 partclause->op_is_ne = false;
2175 partclause->op_strategy = op_strategy;
2176 }
2177 partclause->expr = expr;
2178 partclause->cmpfn = cmpfn;
2179
2180 *pc = partclause;
2181
2182 return PARTCLAUSE_MATCH_CLAUSE;
2183 }
2184 else if (IsA(clause, ScalarArrayOpExpr))
2185 {
2186 ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
2187 Oid saop_op = saop->opno;
2188 Oid saop_coll = saop->inputcollid;
2189 Expr *leftop = (Expr *) linitial(saop->args),
2190 *rightop = (Expr *) lsecond(saop->args);
2191 List *elem_exprs,
2192 *elem_clauses;
2193 ListCell *lc1;
2194
2195 leftop = (Expr *) strip_noop_phvs((Node *) leftop);
2196 while (IsA(leftop, RelabelType))
2197 leftop = ((RelabelType *) leftop)->arg;
2198
2199 /* check if the LHS matches this partition key */
2200 if (!equal(leftop, partkey) ||
2201 !PartCollMatchesExprColl(partcoll, saop->inputcollid))
2202 return PARTCLAUSE_NOMATCH;
2203
2204 /*
2205 * See if the operator is relevant to the partitioning opfamily.
2206 *
2207 * In case of NOT IN (..), we get a '<>', which we handle if list
2208 * partitioning is in use and we're able to confirm that it's negator
2209 * is a btree equality operator belonging to the partitioning operator
2210 * family. As above, report NOMATCH for non-matching operator.
2211 */
2212 if (!op_in_opfamily(saop_op, partopfamily))
2213 {
2214 Oid negator;
2215
2216 if (part_scheme->strategy != PARTITION_STRATEGY_LIST)
2217 return PARTCLAUSE_NOMATCH;
2218
2219 negator = get_negator(saop_op);
2220 if (OidIsValid(negator) && op_in_opfamily(negator, partopfamily))
2221 {
2222 int strategy;
2223 Oid lefttype,
2224 righttype;
2225
2226 get_op_opfamily_properties(negator, partopfamily,
2227 false, &strategy,
2228 &lefttype, &righttype);
2229 if (strategy != BTEqualStrategyNumber)
2230 return PARTCLAUSE_NOMATCH;
2231 }
2232 else
2233 return PARTCLAUSE_NOMATCH; /* no useful negator */
2234 }
2235
2236 /*
2237 * Only allow strict operators. This will guarantee nulls are
2238 * filtered. (This test is likely useless, since btree and hash
2239 * comparison operators are generally strict.)
2240 */
2241 if (!op_strict(saop_op))
2242 return PARTCLAUSE_UNSUPPORTED;
2243
2244 /*
2245 * OK, we have a match to the partition key and a suitable operator.
2246 * Examine the array argument to see if it's usable for pruning. This
2247 * is identical to the logic for a plain OpExpr.
2248 */
2249 if (!IsA(rightop, Const))
2250 {
2251 Bitmapset *paramids;
2252
2253 /*
2254 * When pruning in the planner, we only support pruning using
2255 * comparisons to constants. We cannot prune on the basis of
2256 * anything that's not immutable. (Note that has_mutable_arg and
2257 * has_exec_param do not get set for this target value.)
2258 */
2259 if (context->target == PARTTARGET_PLANNER)
2260 return PARTCLAUSE_UNSUPPORTED;
2261
2262 /*
2263 * We can never prune using an expression that contains Vars.
2264 */
2265 if (contain_var_clause((Node *) rightop))
2266 return PARTCLAUSE_UNSUPPORTED;
2267
2268 /*
2269 * And we must reject anything containing a volatile function.
2270 * Stable functions are OK though.
2271 */
2272 if (contain_volatile_functions((Node *) rightop))
2273 return PARTCLAUSE_UNSUPPORTED;
2274
2275 /*
2276 * See if there are any exec Params. If so, we can only use this
2277 * expression during per-scan pruning.
2278 */
2279 paramids = pull_exec_paramids(rightop);
2280 if (!bms_is_empty(paramids))
2281 {
2282 context->has_exec_param = true;
2283 if (context->target != PARTTARGET_EXEC)
2284 return PARTCLAUSE_UNSUPPORTED;
2285 }
2286 else
2287 {
2288 /* It's potentially usable, but mutable */
2289 context->has_mutable_arg = true;
2290 }
2291 }
2292
2293 /*
2294 * Check whether the comparison operator itself is immutable. (We
2295 * assume anything that's in a btree or hash opclass is at least
2296 * stable, but we need to check for immutability.)
2297 */
2298 if (op_volatile(saop_op) != PROVOLATILE_IMMUTABLE)
2299 {
2300 context->has_mutable_op = true;
2301
2302 /*
2303 * When pruning in the planner, we cannot prune with mutable
2304 * operators.
2305 */
2306 if (context->target == PARTTARGET_PLANNER)
2307 return PARTCLAUSE_UNSUPPORTED;
2308 }
2309
2310 /*
2311 * Examine the contents of the array argument.
2312 */
2313 elem_exprs = NIL;
2314 if (IsA(rightop, Const))
2315 {
2316 /*
2317 * For a constant array, convert the elements to a list of Const
2318 * nodes, one for each array element (excepting nulls).
2319 */
2320 Const *arr = (Const *) rightop;
2321 ArrayType *arrval;
2322 int16 elemlen;
2323 bool elembyval;
2324 char elemalign;
2325 Datum *elem_values;
2326 bool *elem_nulls;
2327 int num_elems,
2328 i;
2329
2330 /* If the array itself is null, the saop returns null */
2331 if (arr->constisnull)
2332 return PARTCLAUSE_MATCH_CONTRADICT;
2333
2334 arrval = DatumGetArrayTypeP(arr->constvalue);
2335 get_typlenbyvalalign(ARR_ELEMTYPE(arrval),
2336 &elemlen, &elembyval, &elemalign);
2337 deconstruct_array(arrval,
2338 ARR_ELEMTYPE(arrval),
2339 elemlen, elembyval, elemalign,
2340 &elem_values, &elem_nulls,
2341 &num_elems);
2342 for (i = 0; i < num_elems; i++)
2343 {
2344 Const *elem_expr;
2345
2346 /*
2347 * A null array element must lead to a null comparison result,
2348 * since saop_op is known strict. We can ignore it in the
2349 * useOr case, but otherwise it implies self-contradiction.
2350 */
2351 if (elem_nulls[i])
2352 {
2353 if (saop->useOr)
2354 continue;
2355 return PARTCLAUSE_MATCH_CONTRADICT;
2356 }
2357
2358 elem_expr = makeConst(ARR_ELEMTYPE(arrval), -1,
2359 arr->constcollid, elemlen,
2360 elem_values[i], false, elembyval);
2361 elem_exprs = lappend(elem_exprs, elem_expr);
2362 }
2363 }
2364 else if (IsA(rightop, ArrayExpr))
2365 {
2366 ArrayExpr *arrexpr = castNode(ArrayExpr, rightop);
2367
2368 /*
2369 * For a nested ArrayExpr, we don't know how to get the actual
2370 * scalar values out into a flat list, so we give up doing
2371 * anything with this ScalarArrayOpExpr.
2372 */
2373 if (arrexpr->multidims)
2374 return PARTCLAUSE_UNSUPPORTED;
2375
2376 /*
2377 * Otherwise, we can just use the list of element values.
2378 */
2379 elem_exprs = arrexpr->elements;
2380 }
2381 else
2382 {
2383 /* Give up on any other clause types. */
2384 return PARTCLAUSE_UNSUPPORTED;
2385 }
2386
2387 /*
2388 * Now generate a list of clauses, one for each array element, of the
2389 * form leftop saop_op elem_expr
2390 */
2391 elem_clauses = NIL;
2392 foreach(lc1, elem_exprs)
2393 {
2394 Expr *elem_clause;
2395
2396 elem_clause = make_opclause(saop_op, BOOLOID, false,
2397 leftop, lfirst(lc1),
2398 InvalidOid, saop_coll);
2399 elem_clauses = lappend(elem_clauses, elem_clause);
2400 }
2401
2402 /*
2403 * If we have an ANY clause and multiple elements, now turn the list
2404 * of clauses into an OR expression.
2405 */
2406 if (saop->useOr && list_length(elem_clauses) > 1)
2407 elem_clauses = list_make1(makeBoolExpr(OR_EXPR, elem_clauses, -1));
2408
2409 /* Finally, generate steps */
2410 *clause_steps = gen_partprune_steps_internal(context, elem_clauses);
2411 if (context->contradictory)
2412 return PARTCLAUSE_MATCH_CONTRADICT;
2413 else if (*clause_steps == NIL)
2414 return PARTCLAUSE_UNSUPPORTED; /* step generation failed */
2415 return PARTCLAUSE_MATCH_STEPS;
2416 }
2417 else if (IsA(clause, NullTest))
2418 {
2419 NullTest *nulltest = (NullTest *) clause;
2420 Expr *arg = nulltest->arg;
2421
2422 arg = (Expr *) strip_noop_phvs((Node *) arg);
2423 while (IsA(arg, RelabelType))
2424 arg = ((RelabelType *) arg)->arg;
2425
2426 /* Does arg match with this partition key column? */
2427 if (!equal(arg, partkey))
2428 return PARTCLAUSE_NOMATCH;
2429
2430 *clause_is_not_null = (nulltest->nulltesttype == IS_NOT_NULL);
2431
2432 return PARTCLAUSE_MATCH_NULLNESS;
2433 }
2434
2435 /*
2436 * If we get here then the return value depends on the result of the
2437 * match_boolean_partition_clause call above. If the call returned
2438 * PARTCLAUSE_UNSUPPORTED then we're either not dealing with a bool qual
2439 * or the bool qual is not suitable for pruning. Since the qual didn't
2440 * match up to any of the other qual types supported here, then trying to
2441 * match it against any other partition key is a waste of time, so just
2442 * return PARTCLAUSE_UNSUPPORTED. If the qual just couldn't be matched to
2443 * this partition key, then it may match another, so return
2444 * PARTCLAUSE_NOMATCH. The only other value that
2445 * match_boolean_partition_clause can return is PARTCLAUSE_MATCH_CLAUSE,
2446 * and since that value was already dealt with above, then we can just
2447 * return boolmatchstatus.
2448 */
2449 return boolmatchstatus;
2450 }
2451
2452 /*
2453 * get_steps_using_prefix
2454 * Generate a list of PartitionPruneStepOps based on the given input.
2455 *
2456 * 'step_lastexpr' and 'step_lastcmpfn' are the Expr and comparison function
2457 * belonging to the final partition key that we have a clause for. 'prefix'
2458 * is a list of PartClauseInfos for partition key numbers prior to the given
2459 * 'step_lastexpr' and 'step_lastcmpfn'. 'prefix' may contain multiple
2460 * PartClauseInfos belonging to a single partition key. We will generate a
2461 * PartitionPruneStepOp for each combination of the given PartClauseInfos
2462 * using, at most, one PartClauseInfo per partition key.
2463 *
2464 * For LIST and RANGE partitioned tables, callers must ensure that
2465 * step_nullkeys is NULL, and that prefix contains at least one clause for
2466 * each of the partition keys prior to the key that 'step_lastexpr' and
2467 * 'step_lastcmpfn' belong to.
2468 *
2469 * For HASH partitioned tables, callers must ensure that 'prefix' contains at
2470 * least one clause for each of the partition keys apart from the final key
2471 * (the expr and comparison function for the final key are in 'step_lastexpr'
2472 * and 'step_lastcmpfn'). A bit set in step_nullkeys can substitute clauses
2473 * in the 'prefix' list for any given key. If a bit is set in 'step_nullkeys'
2474 * for a given key, then there must be no PartClauseInfo for that key in the
2475 * 'prefix' list.
2476 *
2477 * For each of the above cases, callers must ensure that PartClauseInfos in
2478 * 'prefix' are sorted in ascending order of keyno.
2479 */
2480 static List *
2481 get_steps_using_prefix(GeneratePruningStepsContext *context,
2482 StrategyNumber step_opstrategy,
2483 bool step_op_is_ne,
2484 Expr *step_lastexpr,
2485 Oid step_lastcmpfn,
2486 Bitmapset *step_nullkeys,
2487 List *prefix)
2488 {
2489 /* step_nullkeys must be empty for RANGE and LIST partitioned tables */
2490 Assert(step_nullkeys == NULL ||
2491 context->rel->part_scheme->strategy == PARTITION_STRATEGY_HASH);
2492
2493 /*
2494 * No recursive processing is required when 'prefix' is an empty list.
2495 * This occurs when there is only 1 partition key column.
2496 */
2497 if (prefix == NIL)
2498 {
2499 PartitionPruneStep *step;
2500
2501 step = gen_prune_step_op(context,
2502 step_opstrategy,
2503 step_op_is_ne,
2504 list_make1(step_lastexpr),
2505 list_make1_oid(step_lastcmpfn),
2506 step_nullkeys);
2507 return list_make1(step);
2508 }
2509
2510 /* Recurse to generate steps for every combination of clauses. */
2511 return get_steps_using_prefix_recurse(context,
2512 step_opstrategy,
2513 step_op_is_ne,
2514 step_lastexpr,
2515 step_lastcmpfn,
2516 step_nullkeys,
2517 prefix,
2518 list_head(prefix),
2519 NIL, NIL);
2520 }
2521
2522 /*
2523 * get_steps_using_prefix_recurse
2524 * Generate and return a list of PartitionPruneStepOps using the 'prefix'
2525 * list of PartClauseInfos starting at the 'start' cell.
2526 *
2527 * When 'prefix' contains multiple PartClauseInfos for a single partition key
2528 * we create a PartitionPruneStepOp for each combination of duplicated
2529 * PartClauseInfos. The returned list will contain a PartitionPruneStepOp
2530 * for each unique combination of input PartClauseInfos containing at most one
2531 * PartClauseInfo per partition key.
2532 *
2533 * 'prefix' is the input list of PartClauseInfos sorted by keyno.
2534 * 'start' marks the cell that searching the 'prefix' list should start from.
2535 * 'step_exprs' and 'step_cmpfns' each contains the expressions and cmpfns
2536 * we've generated so far from the clauses for the previous part keys.
2537 */
2538 static List *
2539 get_steps_using_prefix_recurse(GeneratePruningStepsContext *context,
2540 StrategyNumber step_opstrategy,
2541 bool step_op_is_ne,
2542 Expr *step_lastexpr,
2543 Oid step_lastcmpfn,
2544 Bitmapset *step_nullkeys,
2545 List *prefix,
2546 ListCell *start,
2547 List *step_exprs,
2548 List *step_cmpfns)
2549 {
2550 List *result = NIL;
2551 ListCell *lc;
2552 int cur_keyno;
2553 int final_keyno;
2554
2555 /* Actually, recursion would be limited by PARTITION_MAX_KEYS. */
2556 check_stack_depth();
2557
2558 Assert(start != NULL);
2559 cur_keyno = ((PartClauseInfo *) lfirst(start))->keyno;
2560 final_keyno = ((PartClauseInfo *) llast(prefix))->keyno;
2561
2562 /* Check if we need to recurse. */
2563 if (cur_keyno < final_keyno)
2564 {
2565 PartClauseInfo *pc;
2566 ListCell *next_start;
2567
2568 /*
2569 * Find the first PartClauseInfo belonging to the next partition key,
2570 * the next recursive call must start iteration of the prefix list
2571 * from that point.
2572 */
2573 for_each_cell(lc, prefix, start)
2574 {
2575 pc = lfirst(lc);
2576
2577 if (pc->keyno > cur_keyno)
2578 break;
2579 }
2580
2581 /* record where to start iterating in the next recursive call */
2582 next_start = lc;
2583
2584 /*
2585 * For each PartClauseInfo with keyno set to cur_keyno, add its expr
2586 * and cmpfn to step_exprs and step_cmpfns, respectively, and recurse
2587 * using 'next_start' as the starting point in the 'prefix' list.
2588 */
2589 for_each_cell(lc, prefix, start)
2590 {
2591 List *moresteps;
2592 List *step_exprs1,
2593 *step_cmpfns1;
2594
2595 pc = lfirst(lc);
2596 if (pc->keyno == cur_keyno)
2597 {
2598 /* Leave the original step_exprs unmodified. */
2599 step_exprs1 = list_copy(step_exprs);
2600 step_exprs1 = lappend(step_exprs1, pc->expr);
2601
2602 /* Leave the original step_cmpfns unmodified. */
2603 step_cmpfns1 = list_copy(step_cmpfns);
2604 step_cmpfns1 = lappend_oid(step_cmpfns1, pc->cmpfn);
2605 }
2606 else
2607 {
2608 /* check the 'prefix' list is sorted correctly */
2609 Assert(pc->keyno > cur_keyno);
2610 break;
2611 }
2612
2613 moresteps = get_steps_using_prefix_recurse(context,
2614 step_opstrategy,
2615 step_op_is_ne,
2616 step_lastexpr,
2617 step_lastcmpfn,
2618 step_nullkeys,
2619 prefix,
2620 next_start,
2621 step_exprs1,
2622 step_cmpfns1);
2623 result = list_concat(result, moresteps);
2624
2625 list_free(step_exprs1);
2626 list_free(step_cmpfns1);
2627 }
2628 }
2629 else
2630 {
2631 /*
2632 * End the current recursion cycle and start generating steps, one for
2633 * each clause with cur_keyno, which is all clauses from here onward
2634 * till the end of the list. Note that for hash partitioning,
2635 * step_nullkeys is allowed to be non-empty, in which case step_exprs
2636 * would only contain expressions for the partition keys that are not
2637 * specified in step_nullkeys.
2638 */
2639 Assert(list_length(step_exprs) == cur_keyno ||
2640 !bms_is_empty(step_nullkeys));
2641
2642 /*
2643 * Note also that for hash partitioning, each partition key should
2644 * have either equality clauses or an IS NULL clause, so if a
2645 * partition key doesn't have an expression, it would be specified in
2646 * step_nullkeys.
2647 */
2648 Assert(context->rel->part_scheme->strategy
2649 != PARTITION_STRATEGY_HASH ||
2650 list_length(step_exprs) + 2 + bms_num_members(step_nullkeys) ==
2651 context->rel->part_scheme->partnatts);
2652 for_each_cell(lc, prefix, start)
2653 {
2654 PartClauseInfo *pc = lfirst(lc);
2655 PartitionPruneStep *step;
2656 List *step_exprs1,
2657 *step_cmpfns1;
2658
2659 Assert(pc->keyno == cur_keyno);
2660
2661 /* Leave the original step_exprs unmodified. */
2662 step_exprs1 = list_copy(step_exprs);
2663 step_exprs1 = lappend(step_exprs1, pc->expr);
2664 step_exprs1 = lappend(step_exprs1, step_lastexpr);
2665
2666 /* Leave the original step_cmpfns unmodified. */
2667 step_cmpfns1 = list_copy(step_cmpfns);
2668 step_cmpfns1 = lappend_oid(step_cmpfns1, pc->cmpfn);
2669 step_cmpfns1 = lappend_oid(step_cmpfns1, step_lastcmpfn);
2670
2671 step = gen_prune_step_op(context,
2672 step_opstrategy, step_op_is_ne,
2673 step_exprs1, step_cmpfns1,
2674 step_nullkeys);
2675 result = lappend(result, step);
2676 }
2677 }
2678
2679 return result;
2680 }
2681
2682 /*
2683 * get_matching_hash_bounds
2684 * Determine offset of the hash bound matching the specified values,
2685 * considering that all the non-null values come from clauses containing
2686 * a compatible hash equality operator and any keys that are null come
2687 * from an IS NULL clause.
2688 *
2689 * Generally this function will return a single matching bound offset,
2690 * although if a partition has not been setup for a given modulus then we may
2691 * return no matches. If the number of clauses found don't cover the entire
2692 * partition key, then we'll need to return all offsets.
2693 *
2694 * 'opstrategy' if non-zero must be HTEqualStrategyNumber.
2695 *
2696 * 'values' contains Datums indexed by the partition key to use for pruning.
2697 *
2698 * 'nvalues', the number of Datums in the 'values' array.
2699 *
2700 * 'partsupfunc' contains partition hashing functions that can produce correct
2701 * hash for the type of the values contained in 'values'.
2702 *
2703 * 'nullkeys' is the set of partition keys that are null.
2704 */
2705 static PruneStepResult *
2706 get_matching_hash_bounds(PartitionPruneContext *context,
2707 StrategyNumber opstrategy, Datum *values, int nvalues,
2708 FmgrInfo *partsupfunc, Bitmapset *nullkeys)
2709 {
2710 PruneStepResult *result = (PruneStepResult *) palloc0(sizeof(PruneStepResult));
2711 PartitionBoundInfo boundinfo = context->boundinfo;
2712 int *partindices = boundinfo->indexes;
2713 int partnatts = context->partnatts;
2714 bool isnull[PARTITION_MAX_KEYS];
2715 int i;
2716 uint64 rowHash;
2717 int greatest_modulus;
2718 Oid *partcollation = context->partcollation;
2719
2720 Assert(context->strategy == PARTITION_STRATEGY_HASH);
2721
2722 /*
2723 * For hash partitioning we can only perform pruning based on equality
2724 * clauses to the partition key or IS NULL clauses. We also can only
2725 * prune if we got values for all keys.
2726 */
2727 if (nvalues + bms_num_members(nullkeys) == partnatts)
2728 {
2729 /*
2730 * If there are any values, they must have come from clauses
2731 * containing an equality operator compatible with hash partitioning.
2732 */
2733 Assert(opstrategy == HTEqualStrategyNumber || nvalues == 0);
2734
2735 for (i = 0; i < partnatts; i++)
2736 isnull[i] = bms_is_member(i, nullkeys);
2737
2738 rowHash = compute_partition_hash_value(partnatts, partsupfunc, partcollation,
2739 values, isnull);
2740
2741 greatest_modulus = boundinfo->nindexes;
2742 if (partindices[rowHash % greatest_modulus] >= 0)
2743 result->bound_offsets =
2744 bms_make_singleton(rowHash % greatest_modulus);
2745 }
2746 else
2747 {
2748 /* Report all valid offsets into the boundinfo->indexes array. */
2749 result->bound_offsets = bms_add_range(NULL, 0,
2750 boundinfo->nindexes - 1);
2751 }
2752
2753 /*
2754 * There is neither a special hash null partition or the default hash
2755 * partition.
2756 */
2757 result->scan_null = result->scan_default = false;
2758
2759 return result;
2760 }
2761
2762 /*
2763 * get_matching_list_bounds
2764 * Determine the offsets of list bounds matching the specified value,
2765 * according to the semantics of the given operator strategy
2766 *
2767 * scan_default will be set in the returned struct, if the default partition
2768 * needs to be scanned, provided one exists at all. scan_null will be set if
2769 * the special null-accepting partition needs to be scanned.
2770 *
2771 * 'opstrategy' if non-zero must be a btree strategy number.
2772 *
2773 * 'value' contains the value to use for pruning.
2774 *
2775 * 'nvalues', if non-zero, should be exactly 1, because of list partitioning.
2776 *
2777 * 'partsupfunc' contains the list partitioning comparison function to be used
2778 * to perform partition_list_bsearch
2779 *
2780 * 'nullkeys' is the set of partition keys that are null.
2781 */
2782 static PruneStepResult *
2783 get_matching_list_bounds(PartitionPruneContext *context,
2784 StrategyNumber opstrategy, Datum value, int nvalues,
2785 FmgrInfo *partsupfunc, Bitmapset *nullkeys)
2786 {
2787 PruneStepResult *result = (PruneStepResult *) palloc0(sizeof(PruneStepResult));
2788 PartitionBoundInfo boundinfo = context->boundinfo;
2789 int off,
2790 minoff,
2791 maxoff;
2792 bool is_equal;
2793 bool inclusive = false;
2794 Oid *partcollation = context->partcollation;
2795
2796 Assert(context->strategy == PARTITION_STRATEGY_LIST);
2797 Assert(context->partnatts == 1);
2798
2799 result->scan_null = result->scan_default = false;
2800
2801 if (!bms_is_empty(nullkeys))
2802 {
2803 /*
2804 * Nulls may exist in only one partition - the partition whose
2805 * accepted set of values includes null or the default partition if
2806 * the former doesn't exist.
2807 */
2808 if (partition_bound_accepts_nulls(boundinfo))
2809 result->scan_null = true;
2810 else
2811 result->scan_default = partition_bound_has_default(boundinfo);
2812 return result;
2813 }
2814
2815 /*
2816 * If there are no datums to compare keys with, but there are partitions,
2817 * just return the default partition if one exists.
2818 */
2819 if (boundinfo->ndatums == 0)
2820 {
2821 result->scan_default = partition_bound_has_default(boundinfo);
2822 return result;
2823 }
2824
2825 minoff = 0;
2826 maxoff = boundinfo->ndatums - 1;
2827
2828 /*
2829 * If there are no values to compare with the datums in boundinfo, it
2830 * means the caller asked for partitions for all non-null datums. Add
2831 * indexes of *all* partitions, including the default if any.
2832 */
2833 if (nvalues == 0)
2834 {
2835 Assert(boundinfo->ndatums > 0);
2836 result->bound_offsets = bms_add_range(NULL, 0,
2837 boundinfo->ndatums - 1);
2838 result->scan_default = partition_bound_has_default(boundinfo);
2839 return result;
2840 }
2841
2842 /* Special case handling of values coming from a <> operator clause. */
2843 if (opstrategy == InvalidStrategy)
2844 {
2845 /*
2846 * First match to all bounds. We'll remove any matching datums below.
2847 */
2848 Assert(boundinfo->ndatums > 0);
2849 result->bound_offsets = bms_add_range(NULL, 0,
2850 boundinfo->ndatums - 1);
2851
2852 off = partition_list_bsearch(partsupfunc, partcollation, boundinfo,
2853 value, &is_equal);
2854 if (off >= 0 && is_equal)
2855 {
2856
2857 /* We have a match. Remove from the result. */
2858 Assert(boundinfo->indexes[off] >= 0);
2859 result->bound_offsets = bms_del_member(result->bound_offsets,
2860 off);
2861 }
2862
2863 /* Always include the default partition if any. */
2864 result->scan_default = partition_bound_has_default(boundinfo);
2865
2866 return result;
2867 }
2868
2869 /*
2870 * With range queries, always include the default list partition, because
2871 * list partitions divide the key space in a discontinuous manner, not all
2872 * values in the given range will have a partition assigned. This may not
2873 * technically be true for some data types (e.g. integer types), however,
2874 * we currently lack any sort of infrastructure to provide us with proofs
2875 * that would allow us to do anything smarter here.
2876 */
2877 if (opstrategy != BTEqualStrategyNumber)
2878 result->scan_default = partition_bound_has_default(boundinfo);
2879
2880 switch (opstrategy)
2881 {
2882 case BTEqualStrategyNumber:
2883 off = partition_list_bsearch(partsupfunc,
2884 partcollation,
2885 boundinfo, value,
2886 &is_equal);
2887 if (off >= 0 && is_equal)
2888 {
2889 Assert(boundinfo->indexes[off] >= 0);
2890 result->bound_offsets = bms_make_singleton(off);
2891 }
2892 else
2893 result->scan_default = partition_bound_has_default(boundinfo);
2894 return result;
2895
2896 case BTGreaterEqualStrategyNumber:
2897 inclusive = true;
2898 /* fall through */
2899 case BTGreaterStrategyNumber:
2900 off = partition_list_bsearch(partsupfunc,
2901 partcollation,
2902 boundinfo, value,
2903 &is_equal);
2904 if (off >= 0)
2905 {
2906 /* We don't want the matched datum to be in the result. */
2907 if (!is_equal || !inclusive)
2908 off++;
2909 }
2910 else
2911 {
2912 /*
2913 * This case means all partition bounds are greater, which in
2914 * turn means that all partitions satisfy this key.
2915 */
2916 off = 0;
2917 }
2918
2919 /*
2920 * off is greater than the numbers of datums we have partitions
2921 * for. The only possible partition that could contain a match is
2922 * the default partition, but we must've set context->scan_default
2923 * above anyway if one exists.
2924 */
2925 if (off > boundinfo->ndatums - 1)
2926 return result;
2927
2928 minoff = off;
2929 break;
2930
2931 case BTLessEqualStrategyNumber:
2932 inclusive = true;
2933 /* fall through */
2934 case BTLessStrategyNumber:
2935 off = partition_list_bsearch(partsupfunc,
2936 partcollation,
2937 boundinfo, value,
2938 &is_equal);
2939 if (off >= 0 && is_equal && !inclusive)
2940 off--;
2941
2942 /*
2943 * off is smaller than the datums of all non-default partitions.
2944 * The only possible partition that could contain a match is the
2945 * default partition, but we must've set context->scan_default
2946 * above anyway if one exists.
2947 */
2948 if (off < 0)
2949 return result;
2950
2951 maxoff = off;
2952 break;
2953
2954 default:
2955 elog(ERROR, "invalid strategy number %d", opstrategy);
2956 break;
2957 }
2958
2959 Assert(minoff >= 0 && maxoff >= 0);
2960 result->bound_offsets = bms_add_range(NULL, minoff, maxoff);
2961 return result;
2962 }
2963
2964
2965 /*
2966 * get_matching_range_bounds
2967 * Determine the offsets of range bounds matching the specified values,
2968 * according to the semantics of the given operator strategy
2969 *
2970 * Each datum whose offset is in result is to be treated as the upper bound of
2971 * the partition that will contain the desired values.
2972 *
2973 * scan_default is set in the returned struct if a default partition exists
2974 * and we're absolutely certain that it needs to be scanned. We do *not* set
2975 * it just because values match portions of the key space uncovered by
2976 * partitions other than default (space which we normally assume to belong to
2977 * the default partition): the final set of bounds obtained after combining
2978 * multiple pruning steps might exclude it, so we infer its inclusion
2979 * elsewhere.
2980 *
2981 * 'opstrategy' must be a btree strategy number.
2982 *
2983 * 'values' contains Datums indexed by the partition key to use for pruning.
2984 *
2985 * 'nvalues', number of Datums in 'values' array. Must be <= context->partnatts.
2986 *
2987 * 'partsupfunc' contains the range partitioning comparison functions to be
2988 * used to perform partition_range_datum_bsearch or partition_rbound_datum_cmp
2989 * using.
2990 *
2991 * 'nullkeys' is the set of partition keys that are null.
2992 */
2993 static PruneStepResult *
2994 get_matching_range_bounds(PartitionPruneContext *context,
2995 StrategyNumber opstrategy, Datum *values, int nvalues,
2996 FmgrInfo *partsupfunc, Bitmapset *nullkeys)
2997 {
2998 PruneStepResult *result = (PruneStepResult *) palloc0(sizeof(PruneStepResult));
2999 PartitionBoundInfo boundinfo = context->boundinfo;
3000 Oid *partcollation = context->partcollation;
3001 int partnatts = context->partnatts;
3002 int *partindices = boundinfo->indexes;
3003 int off,
3004 minoff,
3005 maxoff;
3006 bool is_equal;
3007 bool inclusive = false;
3008
3009 Assert(context->strategy == PARTITION_STRATEGY_RANGE);
3010 Assert(nvalues <= partnatts);
3011
3012 result->scan_null = result->scan_default = false;
3013
3014 /*
3015 * If there are no datums to compare keys with, or if we got an IS NULL
3016 * clause just return the default partition, if it exists.
3017 */
3018 if (boundinfo->ndatums == 0 || !bms_is_empty(nullkeys))
3019 {
3020 result->scan_default = partition_bound_has_default(boundinfo);
3021 return result;
3022 }
3023
3024 minoff = 0;
3025 maxoff = boundinfo->ndatums;
3026
3027 /*
3028 * If there are no values to compare with the datums in boundinfo, it
3029 * means the caller asked for partitions for all non-null datums. Add
3030 * indexes of *all* partitions, including the default partition if one
3031 * exists.
3032 */
3033 if (nvalues == 0)
3034 {
3035 result->scan_default = partition_bound_has_default(boundinfo);
3036 Assert(partindices[minoff] >= -1 &&
3037 partindices[maxoff] >= -1);
3038 result->bound_offsets = bms_add_range(NULL, minoff, maxoff);
3039
3040 return result;
3041 }
3042
3043 /*
3044 * If the query does not constrain all key columns, we'll need to scan the
3045 * default partition, if any.
3046 */
3047 if (nvalues < partnatts)
3048 result->scan_default = partition_bound_has_default(boundinfo);
3049
3050 switch (opstrategy)
3051 {
3052 case BTEqualStrategyNumber:
3053 /* Look for the smallest bound that is = lookup value. */
3054 off = partition_range_datum_bsearch(partsupfunc,
3055 partcollation,
3056 boundinfo,
3057 nvalues, values,
3058 &is_equal);
3059
3060 if (off >= 0 && is_equal)
3061 {
3062 if (nvalues == partnatts)
3063 {
3064 /* There can only be zero or one matching partition. */
3065 result->bound_offsets = bms_make_singleton(off + 1);
3066 return result;
3067 }
3068 else
3069 {
3070 int saved_off = off;
3071
3072 /*
3073 * Since the lookup value contains only a prefix of keys,
3074 * we must find other bounds that may also match the
3075 * prefix. partition_range_datum_bsearch() returns the
3076 * offset of one of them, find others by checking adjacent
3077 * bounds.
3078 */
3079
3080 /*
3081 * First find greatest bound that's smaller than the
3082 * lookup value.
3083 */
3084 while (off >= 1)
3085 {
3086 int32 cmpval;
3087
3088 cmpval =
3089 partition_rbound_datum_cmp(partsupfunc,
3090 partcollation,
3091 boundinfo->datums[off - 1],
3092 boundinfo->kind[off - 1],
3093 values, nvalues);
3094 if (cmpval != 0)
3095 break;
3096 off--;
3097 }
3098
3099 Assert(0 ==
3100 partition_rbound_datum_cmp(partsupfunc,
3101 partcollation,
3102 boundinfo->datums[off],
3103 boundinfo->kind[off],
3104 values, nvalues));
3105
3106 /*
3107 * We can treat 'off' as the offset of the smallest bound
3108 * to be included in the result, if we know it is the
3109 * upper bound of the partition in which the lookup value
3110 * could possibly exist. One case it couldn't is if the
3111 * bound, or precisely the matched portion of its prefix,
3112 * is not inclusive.
3113 */
3114 if (boundinfo->kind[off][nvalues] ==
3115 PARTITION_RANGE_DATUM_MINVALUE)
3116 off++;
3117
3118 minoff = off;
3119
3120 /*
3121 * Now find smallest bound that's greater than the lookup
3122 * value.
3123 */
3124 off = saved_off;
3125 while (off < boundinfo->ndatums - 1)
3126 {
3127 int32 cmpval;
3128
3129 cmpval = partition_rbound_datum_cmp(partsupfunc,
3130 partcollation,
3131 boundinfo->datums[off + 1],
3132 boundinfo->kind[off + 1],
3133 values, nvalues);
3134 if (cmpval != 0)
3135 break;
3136 off++;
3137 }
3138
3139 Assert(0 ==
3140 partition_rbound_datum_cmp(partsupfunc,
3141 partcollation,
3142 boundinfo->datums[off],
3143 boundinfo->kind[off],
3144 values, nvalues));
3145
3146 /*
3147 * off + 1, then would be the offset of the greatest bound
3148 * to be included in the result.
3149 */
3150 maxoff = off + 1;
3151 }
3152
3153 Assert(minoff >= 0 && maxoff >= 0);
3154 result->bound_offsets = bms_add_range(NULL, minoff, maxoff);
3155 }
3156 else
3157 {
3158 /*
3159 * The lookup value falls in the range between some bounds in
3160 * boundinfo. 'off' would be the offset of the greatest bound
3161 * that is <= lookup value, so add off + 1 to the result
3162 * instead as the offset of the upper bound of the only
3163 * partition that may contain the lookup value. If 'off' is
3164 * -1 indicating that all bounds are greater, then we simply
3165 * end up adding the first bound's offset, that is, 0.
3166 */
3167 result->bound_offsets = bms_make_singleton(off + 1);
3168 }
3169
3170 return result;
3171
3172 case BTGreaterEqualStrategyNumber:
3173 inclusive = true;
3174 /* fall through */
3175 case BTGreaterStrategyNumber:
3176
3177 /*
3178 * Look for the smallest bound that is > or >= lookup value and
3179 * set minoff to its offset.
3180 */
3181 off = partition_range_datum_bsearch(partsupfunc,
3182 partcollation,
3183 boundinfo,
3184 nvalues, values,
3185 &is_equal);
3186 if (off < 0)
3187 {
3188 /*
3189 * All bounds are greater than the lookup value, so include
3190 * all of them in the result.
3191 */
3192 minoff = 0;
3193 }
3194 else
3195 {
3196 if (is_equal && nvalues < partnatts)
3197 {
3198 /*
3199 * Since the lookup value contains only a prefix of keys,
3200 * we must find other bounds that may also match the
3201 * prefix. partition_range_datum_bsearch() returns the
3202 * offset of one of them, find others by checking adjacent
3203 * bounds.
3204 *
3205 * Based on whether the lookup values are inclusive or
3206 * not, we must either include the indexes of all such
3207 * bounds in the result (that is, set minoff to the index
3208 * of smallest such bound) or find the smallest one that's
3209 * greater than the lookup values and set minoff to that.
3210 */
3211 while (off >= 1 && off < boundinfo->ndatums - 1)
3212 {
3213 int32 cmpval;
3214 int nextoff;
3215
3216 nextoff = inclusive ? off - 1 : off + 1;
3217 cmpval =
3218 partition_rbound_datum_cmp(partsupfunc,
3219 partcollation,
3220 boundinfo->datums[nextoff],
3221 boundinfo->kind[nextoff],
3222 values, nvalues);
3223 if (cmpval != 0)
3224 break;
3225
3226 off = nextoff;
3227 }
3228
3229 Assert(0 ==
3230 partition_rbound_datum_cmp(partsupfunc,
3231 partcollation,
3232 boundinfo->datums[off],
3233 boundinfo->kind[off],
3234 values, nvalues));
3235
3236 minoff = inclusive ? off : off + 1;
3237 }
3238 else
3239 {
3240
3241 /*
3242 * lookup value falls in the range between some bounds in
3243 * boundinfo. off would be the offset of the greatest
3244 * bound that is <= lookup value, so add off + 1 to the
3245 * result instead as the offset of the upper bound of the
3246 * smallest partition that may contain the lookup value.
3247 */
3248 minoff = off + 1;
3249 }
3250 }
3251 break;
3252
3253 case BTLessEqualStrategyNumber:
3254 inclusive = true;
3255 /* fall through */
3256 case BTLessStrategyNumber:
3257
3258 /*
3259 * Look for the greatest bound that is < or <= lookup value and
3260 * set maxoff to its offset.
3261 */
3262 off = partition_range_datum_bsearch(partsupfunc,
3263 partcollation,
3264 boundinfo,
3265 nvalues, values,
3266 &is_equal);
3267 if (off >= 0)
3268 {
3269 /*
3270 * See the comment above.
3271 */
3272 if (is_equal && nvalues < partnatts)
3273 {
3274 while (off >= 1 && off < boundinfo->ndatums - 1)
3275 {
3276 int32 cmpval;
3277 int nextoff;
3278
3279 nextoff = inclusive ? off + 1 : off - 1;
3280 cmpval = partition_rbound_datum_cmp(partsupfunc,
3281 partcollation,
3282 boundinfo->datums[nextoff],
3283 boundinfo->kind[nextoff],
3284 values, nvalues);
3285 if (cmpval != 0)
3286 break;
3287
3288 off = nextoff;
3289 }
3290
3291 Assert(0 ==
3292 partition_rbound_datum_cmp(partsupfunc,
3293 partcollation,
3294 boundinfo->datums[off],
3295 boundinfo->kind[off],
3296 values, nvalues));
3297
3298 maxoff = inclusive ? off + 1 : off;
3299 }
3300
3301 /*
3302 * The lookup value falls in the range between some bounds in
3303 * boundinfo. 'off' would be the offset of the greatest bound
3304 * that is <= lookup value, so add off + 1 to the result
3305 * instead as the offset of the upper bound of the greatest
3306 * partition that may contain lookup value. If the lookup
3307 * value had exactly matched the bound, but it isn't
3308 * inclusive, no need add the adjacent partition.
3309 */
3310 else if (!is_equal || inclusive)
3311 maxoff = off + 1;
3312 else
3313 maxoff = off;
3314 }
3315 else
3316 {
3317 /*
3318 * 'off' is -1 indicating that all bounds are greater, so just
3319 * set the first bound's offset as maxoff.
3320 */
3321 maxoff = off + 1;
3322 }
3323 break;
3324
3325 default:
3326 elog(ERROR, "invalid strategy number %d", opstrategy);
3327 break;
3328 }
3329
3330 Assert(minoff >= 0 && minoff <= boundinfo->ndatums);
3331 Assert(maxoff >= 0 && maxoff <= boundinfo->ndatums);
3332
3333 /*
3334 * If the smallest partition to return has MINVALUE (negative infinity) as
3335 * its lower bound, increment it to point to the next finite bound
3336 * (supposedly its upper bound), so that we don't inadvertently end up
3337 * scanning the default partition.
3338 */
3339 if (minoff < boundinfo->ndatums && partindices[minoff] < 0)
3340 {
3341 int lastkey = nvalues - 1;
3342
3343 if (boundinfo->kind[minoff][lastkey] ==
3344 PARTITION_RANGE_DATUM_MINVALUE)
3345 {
3346 minoff++;
3347 Assert(boundinfo->indexes[minoff] >= 0);
3348 }
3349 }
3350
3351 /*
3352 * If the previous greatest partition has MAXVALUE (positive infinity) as
3353 * its upper bound (something only possible to do with multi-column range
3354 * partitioning), we scan switch to it as the greatest partition to
3355 * return. Again, so that we don't inadvertently end up scanning the
3356 * default partition.
3357 */
3358 if (maxoff >= 1 && partindices[maxoff] < 0)
3359 {
3360 int lastkey = nvalues - 1;
3361
3362 if (boundinfo->kind[maxoff - 1][lastkey] ==
3363 PARTITION_RANGE_DATUM_MAXVALUE)
3364 {
3365 maxoff--;
3366 Assert(boundinfo->indexes[maxoff] >= 0);
3367 }
3368 }
3369
3370 Assert(minoff >= 0 && maxoff >= 0);
3371 if (minoff <= maxoff)
3372 result->bound_offsets = bms_add_range(NULL, minoff, maxoff);
3373
3374 return result;
3375 }
3376
3377 /*
3378 * pull_exec_paramids
3379 * Returns a Bitmapset containing the paramids of all Params with
3380 * paramkind = PARAM_EXEC in 'expr'.
3381 */
3382 static Bitmapset *
3383 pull_exec_paramids(Expr *expr)
3384 {
3385 Bitmapset *result = NULL;
3386
3387 (void) pull_exec_paramids_walker((Node *) expr, &result);
3388
3389 return result;
3390 }
3391
3392 static bool
3393 pull_exec_paramids_walker(Node *node, Bitmapset **context)
3394 {
3395 if (node == NULL)
3396 return false;
3397 if (IsA(node, Param))
3398 {
3399 Param *param = (Param *) node;
3400
3401 if (param->paramkind == PARAM_EXEC)
3402 *context = bms_add_member(*context, param->paramid);
3403 return false;
3404 }
3405 return expression_tree_walker(node, pull_exec_paramids_walker, context);
3406 }
3407
3408 /*
3409 * get_partkey_exec_paramids
3410 * Loop through given pruning steps and find out which exec Params
3411 * are used.
3412 *
3413 * Returns a Bitmapset of Param IDs.
3414 */
3415 static Bitmapset *
3416 get_partkey_exec_paramids(List *steps)
3417 {
3418 Bitmapset *execparamids = NULL;
3419 ListCell *lc;
3420
3421 foreach(lc, steps)
3422 {
3423 PartitionPruneStepOp *step = (PartitionPruneStepOp *) lfirst(lc);
3424 ListCell *lc2;
3425
3426 if (!IsA(step, PartitionPruneStepOp))
3427 continue;
3428
3429 foreach(lc2, step->exprs)
3430 {
3431 Expr *expr = lfirst(lc2);
3432
3433 /* We can be quick for plain Consts */
3434 if (!IsA(expr, Const))
3435 execparamids = bms_join(execparamids,
3436 pull_exec_paramids(expr));
3437 }
3438 }
3439
3440 return execparamids;
3441 }
3442
3443 /*
3444 * perform_pruning_base_step
3445 * Determines the indexes of datums that satisfy conditions specified in
3446 * 'opstep'.
3447 *
3448 * Result also contains whether special null-accepting and/or default
3449 * partition need to be scanned.
3450 */
3451 static PruneStepResult *
3452 perform_pruning_base_step(PartitionPruneContext *context,
3453 PartitionPruneStepOp *opstep)
3454 {
3455 ListCell *lc1,
3456 *lc2;
3457 int keyno,
3458 nvalues;
3459 Datum values[PARTITION_MAX_KEYS];
3460 FmgrInfo *partsupfunc;
3461 int stateidx;
3462
3463 /*
3464 * There better be the same number of expressions and compare functions.
3465 */
3466 Assert(list_length(opstep->exprs) == list_length(opstep->cmpfns));
3467
3468 nvalues = 0;
3469 lc1 = list_head(opstep->exprs);
3470 lc2 = list_head(opstep->cmpfns);
3471
3472 /*
3473 * Generate the partition lookup key that will be used by one of the
3474 * get_matching_*_bounds functions called below.
3475 */
3476 for (keyno = 0; keyno < context->partnatts; keyno++)
3477 {
3478 /*
3479 * For hash partitioning, it is possible that values of some keys are
3480 * not provided in operator clauses, but instead the planner found
3481 * that they appeared in a IS NULL clause.
3482 */
3483 if (bms_is_member(keyno, opstep->nullkeys))
3484 continue;
3485
3486 /*
3487 * For range partitioning, we must only perform pruning with values
3488 * for either all partition keys or a prefix thereof.
3489 */
3490 if (keyno > nvalues && context->strategy == PARTITION_STRATEGY_RANGE)
3491 break;
3492
3493 if (lc1 != NULL)
3494 {
3495 Expr *expr;
3496 Datum datum;
3497 bool isnull;
3498 Oid cmpfn;
3499
3500 expr = lfirst(lc1);
3501 stateidx = PruneCxtStateIdx(context->partnatts,
3502 opstep->step.step_id, keyno);
3503 partkey_datum_from_expr(context, expr, stateidx,
3504 &datum, &isnull);
3505
3506 /*
3507 * Since we only allow strict operators in pruning steps, any
3508 * null-valued comparison value must cause the comparison to fail,
3509 * so that no partitions could match.
3510 */
3511 if (isnull)
3512 {
3513 PruneStepResult *result;
3514
3515 result = (PruneStepResult *) palloc(sizeof(PruneStepResult));
3516 result->bound_offsets = NULL;
3517 result->scan_default = false;
3518 result->scan_null = false;
3519
3520 return result;
3521 }
3522
3523 /* Set up the stepcmpfuncs entry, unless we already did */
3524 cmpfn = lfirst_oid(lc2);
3525 Assert(OidIsValid(cmpfn));
3526 if (cmpfn != context->stepcmpfuncs[stateidx].fn_oid)
3527 {
3528 /*
3529 * If the needed support function is the same one cached in
3530 * the relation's partition key, copy the cached FmgrInfo.
3531 * Otherwise (i.e., when we have a cross-type comparison), an
3532 * actual lookup is required.
3533 */
3534 if (cmpfn == context->partsupfunc[keyno].fn_oid)
3535 fmgr_info_copy(&context->stepcmpfuncs[stateidx],
3536 &context->partsupfunc[keyno],
3537 context->ppccontext);
3538 else
3539 fmgr_info_cxt(cmpfn, &context->stepcmpfuncs[stateidx],
3540 context->ppccontext);
3541 }
3542
3543 values[keyno] = datum;
3544 nvalues++;
3545
3546 lc1 = lnext(opstep->exprs, lc1);
3547 lc2 = lnext(opstep->cmpfns, lc2);
3548 }
3549 }
3550
3551 /*
3552 * Point partsupfunc to the entry for the 0th key of this step; the
3553 * additional support functions, if any, follow consecutively.
3554 */
3555 stateidx = PruneCxtStateIdx(context->partnatts, opstep->step.step_id, 0);
3556 partsupfunc = &context->stepcmpfuncs[stateidx];
3557
3558 switch (context->strategy)
3559 {
3560 case PARTITION_STRATEGY_HASH:
3561 return get_matching_hash_bounds(context,
3562 opstep->opstrategy,
3563 values, nvalues,
3564 partsupfunc,
3565 opstep->nullkeys);
3566
3567 case PARTITION_STRATEGY_LIST:
3568 return get_matching_list_bounds(context,
3569 opstep->opstrategy,
3570 values[0], nvalues,
3571 &partsupfunc[0],
3572 opstep->nullkeys);
3573
3574 case PARTITION_STRATEGY_RANGE:
3575 return get_matching_range_bounds(context,
3576 opstep->opstrategy,
3577 values, nvalues,
3578 partsupfunc,
3579 opstep->nullkeys);
3580
3581 default:
3582 elog(ERROR, "unexpected partition strategy: %d",
3583 (int) context->strategy);
3584 break;
3585 }
3586
3587 return NULL;
3588 }
3589
3590 /*
3591 * perform_pruning_combine_step
3592 * Determines the indexes of datums obtained by combining those given
3593 * by the steps identified by cstep->source_stepids using the specified
3594 * combination method
3595 *
3596 * Since cstep may refer to the result of earlier steps, we also receive
3597 * step_results here.
3598 */
3599 static PruneStepResult *
3600 perform_pruning_combine_step(PartitionPruneContext *context,
3601 PartitionPruneStepCombine *cstep,
3602 PruneStepResult **step_results)
3603 {
3604 PruneStepResult *result = (PruneStepResult *) palloc0(sizeof(PruneStepResult));
3605 bool firststep;
3606 ListCell *lc1;
3607
3608 /*
3609 * A combine step without any source steps is an indication to not perform
3610 * any partition pruning. Return all datum indexes in that case.
3611 */
3612 if (cstep->source_stepids == NIL)
3613 {
3614 PartitionBoundInfo boundinfo = context->boundinfo;
3615
3616 result->bound_offsets =
3617 bms_add_range(NULL, 0, boundinfo->nindexes - 1);
3618 result->scan_default = partition_bound_has_default(boundinfo);
3619 result->scan_null = partition_bound_accepts_nulls(boundinfo);
3620 return result;
3621 }
3622
3623 switch (cstep->combineOp)
3624 {
3625 case PARTPRUNE_COMBINE_UNION:
3626 foreach(lc1, cstep->source_stepids)
3627 {
3628 int step_id = lfirst_int(lc1);
3629 PruneStepResult *step_result;
3630
3631 /*
3632 * step_results[step_id] must contain a valid result, which is
3633 * confirmed by the fact that cstep's step_id is greater than
3634 * step_id and the fact that results of the individual steps
3635 * are evaluated in sequence of their step_ids.
3636 */
3637 if (step_id >= cstep->step.step_id)
3638 elog(ERROR, "invalid pruning combine step argument");
3639 step_result = step_results[step_id];
3640 Assert(step_result != NULL);
3641
3642 /* Record any additional datum indexes from this step */
3643 result->bound_offsets = bms_add_members(result->bound_offsets,
3644 step_result->bound_offsets);
3645
3646 /* Update whether to scan null and default partitions. */
3647 if (!result->scan_null)
3648 result->scan_null = step_result->scan_null;
3649 if (!result->scan_default)
3650 result->scan_default = step_result->scan_default;
3651 }
3652 break;
3653
3654 case PARTPRUNE_COMBINE_INTERSECT:
3655 firststep = true;
3656 foreach(lc1, cstep->source_stepids)
3657 {
3658 int step_id = lfirst_int(lc1);
3659 PruneStepResult *step_result;
3660
3661 if (step_id >= cstep->step.step_id)
3662 elog(ERROR, "invalid pruning combine step argument");
3663 step_result = step_results[step_id];
3664 Assert(step_result != NULL);
3665
3666 if (firststep)
3667 {
3668 /* Copy step's result the first time. */
3669 result->bound_offsets =
3670 bms_copy(step_result->bound_offsets);
3671 result->scan_null = step_result->scan_null;
3672 result->scan_default = step_result->scan_default;
3673 firststep = false;
3674 }
3675 else
3676 {
3677 /* Record datum indexes common to both steps */
3678 result->bound_offsets =
3679 bms_int_members(result->bound_offsets,
3680 step_result->bound_offsets);
3681
3682 /* Update whether to scan null and default partitions. */
3683 if (result->scan_null)
3684 result->scan_null = step_result->scan_null;
3685 if (result->scan_default)
3686 result->scan_default = step_result->scan_default;
3687 }
3688 }
3689 break;
3690 }
3691
3692 return result;
3693 }
3694
3695 /*
3696 * match_boolean_partition_clause
3697 *
3698 * If we're able to match the clause to the partition key as specially-shaped
3699 * boolean clause, set *outconst to a Const containing a true, false or NULL
3700 * value, set *notclause according to if the clause was in the "not" form,
3701 * i.e. "IS NOT TRUE", "IS NOT FALSE" or "IS NOT UNKNOWN" and return
3702 * PARTCLAUSE_MATCH_CLAUSE for "IS [NOT] (TRUE|FALSE)" clauses and
3703 * PARTCLAUSE_MATCH_NULLNESS for "IS [NOT] UNKNOWN" clauses. Otherwise,
3704 * return PARTCLAUSE_UNSUPPORTED if the clause cannot be used for partition
3705 * pruning, and PARTCLAUSE_NOMATCH for supported clauses that do not match this
3706 * 'partkey'.
3707 */
3708 static PartClauseMatchStatus
3709 match_boolean_partition_clause(Oid partopfamily, Expr *clause, Expr *partkey,
3710 Expr **outconst, bool *notclause)
3711 {
3712 Expr *leftop;
3713
3714 *outconst = NULL;
3715 *notclause = false;
3716
3717 /*
3718 * Partitioning currently can only use built-in AMs, so checking for
3719 * built-in boolean opfamilies is good enough.
3720 */
3721 if (!IsBuiltinBooleanOpfamily(partopfamily))
3722 return PARTCLAUSE_UNSUPPORTED;
3723
3724 if (IsA(clause, BooleanTest))
3725 {
3726 BooleanTest *btest = (BooleanTest *) clause;
3727
3728 leftop = btest->arg;
3729 leftop = (Expr *) strip_noop_phvs((Node *) leftop);
3730 while (IsA(leftop, RelabelType))
3731 leftop = ((RelabelType *) leftop)->arg;
3732
3733 if (equal(leftop, partkey))
3734 {
3735 switch (btest->booltesttype)
3736 {
3737 case IS_NOT_TRUE:
3738 *notclause = true;
3739 /* fall through */
3740 case IS_TRUE:
3741 *outconst = (Expr *) makeBoolConst(true, false);
3742 return PARTCLAUSE_MATCH_CLAUSE;
3743 case IS_NOT_FALSE:
3744 *notclause = true;
3745 /* fall through */
3746 case IS_FALSE:
3747 *outconst = (Expr *) makeBoolConst(false, false);
3748 return PARTCLAUSE_MATCH_CLAUSE;
3749 case IS_NOT_UNKNOWN:
3750 *notclause = true;
3751 /* fall through */
3752 case IS_UNKNOWN:
3753 return PARTCLAUSE_MATCH_NULLNESS;
3754 default:
3755 return PARTCLAUSE_UNSUPPORTED;
3756 }
3757 }
3758 /* does not match partition key */
3759 return PARTCLAUSE_NOMATCH;
3760 }
3761 else
3762 {
3763 bool is_not_clause = is_notclause(clause);
3764
3765 leftop = is_not_clause ? get_notclausearg(clause) : clause;
3766
3767 leftop = (Expr *) strip_noop_phvs((Node *) leftop);
3768 while (IsA(leftop, RelabelType))
3769 leftop = ((RelabelType *) leftop)->arg;
3770
3771 /* Compare to the partition key, and make up a clause ... */
3772 if (equal(leftop, partkey))
3773 *outconst = (Expr *) makeBoolConst(!is_not_clause, false);
3774 else if (equal(negate_clause((Node *) leftop), partkey))
3775 *outconst = (Expr *) makeBoolConst(is_not_clause, false);
3776 else
3777 return PARTCLAUSE_NOMATCH;
3778
3779 return PARTCLAUSE_MATCH_CLAUSE;
3780 }
3781 }
3782
3783 /*
3784 * partkey_datum_from_expr
3785 * Evaluate expression for potential partition pruning
3786 *
3787 * Evaluate 'expr'; set *value and *isnull to the resulting Datum and nullflag.
3788 *
3789 * If expr isn't a Const, its ExprState is in stateidx of the context
3790 * exprstate array.
3791 *
3792 * Note that the evaluated result may be in the per-tuple memory context of
3793 * context->exprcontext, and we may have leaked other memory there too.
3794 * This memory must be recovered by resetting that ExprContext after
3795 * we're done with the pruning operation (see execPartition.c).
3796 */
3797 static void
3798 partkey_datum_from_expr(PartitionPruneContext *context,
3799 Expr *expr, int stateidx,
3800 Datum *value, bool *isnull)
3801 {
3802 if (IsA(expr, Const))
3803 {
3804 /* We can always determine the value of a constant */
3805 Const *con = (Const *) expr;
3806
3807 *value = con->constvalue;
3808 *isnull = con->constisnull;
3809 }
3810 else
3811 {
3812 ExprState *exprstate;
3813 ExprContext *ectx;
3814
3815 /*
3816 * We should never see a non-Const in a step unless the caller has
3817 * passed a valid ExprContext.
3818 */
3819 Assert(context->exprcontext != NULL);
3820
3821 exprstate = context->exprstates[stateidx];
3822 ectx = context->exprcontext;
3823 *value = ExecEvalExprSwitchContext(exprstate, ectx, isnull);
3824 }
3825 }