| blob | cd6d72c7633447ad441535fb5de53c745918be37 |
1 /*-------------------------------------------------------------------------
2 *
3 * createplan.c
4 * Routines to create the desired plan for processing a query.
5 * Planning is complete, we just need to convert the selected
6 * Path into a Plan.
7 *
8 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
9 * Portions Copyright (c) 1994, Regents of the University of California
10 *
11 *
12 * IDENTIFICATION
13 * src/backend/optimizer/plan/createplan.c
14 *
15 *-------------------------------------------------------------------------
16 */
19 #include <limits.h>
20 #include <math.h>
47 /*
48 * Flag bits that can appear in the flags argument of create_plan_recurse().
49 * These can be OR-ed together.
50 *
51 * CP_EXACT_TLIST specifies that the generated plan node must return exactly
52 * the tlist specified by the path's pathtarget (this overrides both
53 * CP_SMALL_TLIST and CP_LABEL_TLIST, if those are set). Otherwise, the
54 * plan node is allowed to return just the Vars and PlaceHolderVars needed
55 * to evaluate the pathtarget.
56 *
57 * CP_SMALL_TLIST specifies that a narrower tlist is preferred. This is
58 * passed down by parent nodes such as Sort and Hash, which will have to
59 * store the returned tuples.
60 *
61 * CP_LABEL_TLIST specifies that the plan node must return columns matching
62 * any sortgrouprefs specified in its pathtarget, with appropriate
63 * ressortgroupref labels. This is passed down by parent nodes such as Sort
64 * and Group, which need these values to be available in their inputs.
65 *
66 * CP_IGNORE_TLIST specifies that the caller plans to replace the targetlist,
67 * and therefore it doesn't matter a bit what target list gets generated.
68 */
116 static RecursiveUnion *create_recursiveunion_plan(PlannerInfo *root, RecursiveUnionPath *best_path);
188 ScanDirection indexscandir);
194 ScanDirection indexscandir);
202 Index scanrelid);
209 Index scanrelid,
244 Oid skewTable,
245 AttrNumber skewColumn,
265 Relids relids,
274 Relids relids);
318 /*
319 * create_plan
320 * Creates the access plan for a query by recursively processing the
321 * desired tree of pathnodes, starting at the node 'best_path'. For
322 * every pathnode found, we create a corresponding plan node containing
323 * appropriate id, target list, and qualification information.
324 *
325 * The tlists and quals in the plan tree are still in planner format,
326 * ie, Vars still correspond to the parser's numbering. This will be
327 * fixed later by setrefs.c.
328 *
329 * best_path is the best access path
330 *
331 * Returns a Plan tree.
332 */
333 Plan *
335 {
338 /* plan_params should not be in use in current query level */
341 /* Initialize this module's workspace in PlannerInfo */
345 /* Recursively process the path tree, demanding the correct tlist result */
348 /*
349 * Make sure the topmost plan node's targetlist exposes the original
350 * column names and other decorative info. Targetlists generated within
351 * the planner don't bother with that stuff, but we must have it on the
352 * top-level tlist seen at execution time. However, ModifyTable plan
353 * nodes don't have a tlist matching the querytree targetlist.
354 */
358 /*
359 * Attach any initPlans created in this query level to the topmost plan
360 * node. (In principle the initplans could go in any plan node at or
361 * above where they're referenced, but there seems no reason to put them
362 * any lower than the topmost node for the query level. Also, see
363 * comments for SS_finalize_plan before you try to change this.)
364 */
367 /* Check we successfully assigned all NestLoopParams to plan nodes */
371 /*
372 * Reset plan_params to ensure param IDs used for nestloop params are not
373 * re-used later
374 */
378 }
380 /*
381 * create_plan_recurse
382 * Recursive guts of create_plan().
383 */
386 {
389 /* Guard against stack overflow due to overly complex plans */
393 {
421 flags);
426 flags);
430 {
433 flags);
434 }
436 {
439 }
441 {
444 }
445 else
446 {
447 /* Simple RTE_RESULT base relation */
450 }
459 flags);
464 flags);
468 {
471 flags);
472 }
473 else
474 {
478 flags);
479 }
488 flags);
493 flags);
503 else
504 {
508 }
517 flags);
526 flags);
535 flags);
546 }
549 }
551 /*
552 * create_scan_plan
553 * Create a scan plan for the parent relation of 'best_path'.
554 */
557 {
564 /*
565 * Extract the relevant restriction clauses from the parent relation. The
566 * executor must apply all these restrictions during the scan, except for
567 * pseudoconstants which we'll take care of below.
568 *
569 * If this is a plain indexscan or index-only scan, we need not consider
570 * restriction clauses that are implied by the index's predicate, so use
571 * indrestrictinfo not baserestrictinfo. Note that we can't do that for
572 * bitmap indexscans, since there's not necessarily a single index
573 * involved; but it doesn't matter since create_bitmap_scan_plan() will be
574 * able to get rid of such clauses anyway via predicate proof.
575 */
577 {
585 }
587 /*
588 * If this is a parameterized scan, we also need to enforce all the join
589 * clauses available from the outer relation(s).
590 *
591 * For paranoia's sake, don't modify the stored baserestrictinfo list.
592 */
597 /*
598 * Detect whether we have any pseudoconstant quals to deal with. Then, if
599 * we'll need a gating Result node, it will be able to project, so there
600 * are no requirements on the child's tlist.
601 */
606 /*
607 * For table scans, rather than using the relation targetlist (which is
608 * only those Vars actually needed by the query), we prefer to generate a
609 * tlist containing all Vars in order. This will allow the executor to
610 * optimize away projection of the table tuples, if possible.
611 *
612 * But if the caller is going to ignore our tlist anyway, then don't
613 * bother generating one at all. We use an exact equality test here, so
614 * that this only applies when CP_IGNORE_TLIST is the only flag set.
615 */
617 {
619 }
621 {
623 {
624 /* For index-only scan, the preferred tlist is the index's */
627 /*
628 * Transfer sortgroupref data to the replacement tlist, if
629 * requested (use_physical_tlist checked that this will work).
630 */
633 }
634 else
635 {
638 {
639 /* Failed because of dropped cols, so use regular method */
641 }
642 else
643 {
644 /* As above, transfer sortgroupref data to replacement tlist */
647 }
648 }
649 }
650 else
651 {
653 }
656 {
659 best_path,
660 tlist,
661 scan_clauses);
666 best_path,
667 tlist,
668 scan_clauses);
674 tlist,
675 scan_clauses,
682 tlist,
683 scan_clauses,
690 tlist,
691 scan_clauses);
697 tlist,
698 scan_clauses);
704 tlist,
705 scan_clauses);
711 tlist,
712 scan_clauses);
717 best_path,
718 tlist,
719 scan_clauses);
724 best_path,
725 tlist,
726 scan_clauses);
731 best_path,
732 tlist,
733 scan_clauses);
738 best_path,
739 tlist,
740 scan_clauses);
745 best_path,
746 tlist,
747 scan_clauses);
752 best_path,
753 tlist,
754 scan_clauses);
759 best_path,
760 tlist,
761 scan_clauses);
767 tlist,
768 scan_clauses);
774 tlist,
775 scan_clauses);
783 }
785 /*
786 * If there are any pseudoconstant clauses attached to this node, insert a
787 * gating Result node that evaluates the pseudoconstants as one-time
788 * quals.
789 */
794 }
796 /*
797 * Build a target list (ie, a list of TargetEntry) for the Path's output.
798 *
799 * This is almost just make_tlist_from_pathtarget(), but we also have to
800 * deal with replacing nestloop params.
801 */
804 {
811 {
815 /*
816 * If it's a parameterized path, there might be lateral references in
817 * the tlist, which need to be replaced with Params. There's no need
818 * to remake the TargetEntry nodes, so apply this to each list item
819 * separately.
820 */
825 resno,
826 NULL,
832 resno++;
833 }
835 }
837 /*
838 * use_physical_tlist
839 * Decide whether to use a tlist matching relation structure,
840 * rather than only those Vars actually referenced.
841 */
842 static bool
844 {
849 /*
850 * Forget it if either exact tlist or small tlist is demanded.
851 */
855 /*
856 * We can do this for real relation scans, subquery scans, function scans,
857 * tablefunc scans, values scans, and CTE scans (but not for, eg, joins).
858 */
867 /*
868 * Can't do it with inheritance cases either (mainly because Append
869 * doesn't project; this test may be unnecessary now that
870 * create_append_plan instructs its children to return an exact tlist).
871 */
875 /*
876 * Also, don't do it to a CustomPath; the premise that we're extracting
877 * columns from a simple physical tuple is unlikely to hold for those.
878 * (When it does make sense, the custom path creator can set up the path's
879 * pathtarget that way.)
880 */
884 /*
885 * If a bitmap scan's tlist is empty, keep it as-is. This may allow the
886 * executor to skip heap page fetches, and in any case, the benefit of
887 * using a physical tlist instead would be minimal.
888 */
893 /*
894 * Can't do it if any system columns or whole-row Vars are requested.
895 * (This could possibly be fixed but would take some fragile assumptions
896 * in setrefs.c, I think.)
897 */
899 {
902 }
904 /*
905 * Can't do it if the rel is required to emit any placeholder expressions,
906 * either.
907 */
909 {
915 }
917 /*
918 * Also, can't do it if CP_LABEL_TLIST is specified and path is requested
919 * to emit any sort/group columns that are not simple Vars. (If they are
920 * simple Vars, they should appear in the physical tlist, and
921 * apply_pathtarget_labeling_to_tlist will take care of getting them
922 * labeled again.) We also have to check that no two sort/group columns
923 * are the same Var, else that element of the physical tlist would need
924 * conflicting ressortgroupref labels.
925 */
927 {
932 {
936 {
938 {
945 }
946 else
948 }
949 i++;
950 }
951 }
954 }
956 /*
957 * get_gating_quals
958 * See if there are pseudoconstant quals in a node's quals list
959 *
960 * If the node's quals list includes any pseudoconstant quals,
961 * return just those quals.
962 */
965 {
966 /* No need to look if we know there are no pseudoconstants */
970 /* Sort into desirable execution order while still in RestrictInfo form */
973 /* Pull out any pseudoconstant quals from the RestrictInfo list */
975 }
977 /*
978 * create_gating_plan
979 * Deal with pseudoconstant qual clauses
980 *
981 * Add a gating Result node atop the already-built plan.
982 */
986 {
992 /*
993 * We might have a trivial Result plan already. Stacking one Result atop
994 * another is silly, so if that applies, just discard the input plan.
995 * (We're assuming its targetlist is uninteresting; it should be either
996 * the same as the result of build_path_tlist, or a simplified version.)
997 */
1000 {
1006 }
1008 /*
1009 * Since we need a Result node anyway, always return the path's requested
1010 * tlist; that's never a wrong choice, even if the parent node didn't ask
1011 * for CP_EXACT_TLIST.
1012 */
1015 splan);
1017 /*
1018 * Notice that we don't change cost or size estimates when doing gating.
1019 * The costs of qual eval were already included in the subplan's cost.
1020 * Leaving the size alone amounts to assuming that the gating qual will
1021 * succeed, which is the conservative estimate for planning upper queries.
1022 * We certainly don't want to assume the output size is zero (unless the
1023 * gating qual is actually constant FALSE, and that case is dealt with in
1024 * clausesel.c). Interpolating between the two cases is silly, because it
1025 * doesn't reflect what will really happen at runtime, and besides which
1026 * in most cases we have only a very bad idea of the probability of the
1027 * gating qual being true.
1028 */
1031 /* Gating quals could be unsafe, so better use the Path's safety flag */
1035 }
1037 /*
1038 * create_join_plan
1039 * Create a join plan for 'best_path' and (recursively) plans for its
1040 * inner and outer paths.
1041 */
1044 {
1049 {
1067 }
1069 /*
1070 * If there are any pseudoconstant clauses attached to this node, insert a
1071 * gating Result node that evaluates the pseudoconstants as one-time
1072 * quals.
1073 */
1077 gating_clauses);
1079 #ifdef NOT_USED
1081 /*
1082 * * Expensive function pullups may have pulled local predicates * into
1083 * this path node. Put them in the qpqual of the plan node. * JMH,
1084 * 6/15/92
1085 */
1090 #endif
1093 }
1095 /*
1096 * is_async_capable_path
1097 * Check whether a given Path node is async-capable.
1098 */
1099 static bool
1101 {
1103 {
1105 {
1112 }
1116 }
1118 }
1120 /*
1121 * create_append_plan
1122 * Create an Append plan for 'best_path' and (recursively) plans
1123 * for its subpaths.
1124 *
1125 * Returns a Plan node.
1126 */
1129 {
1147 /*
1148 * The subpaths list could be empty, if every child was proven empty by
1149 * constraint exclusion. In that case generate a dummy plan that returns
1150 * no rows.
1151 *
1152 * Note that an AppendPath with no members is also generated in certain
1153 * cases where there was no appending construct at all, but we know the
1154 * relation is empty (see set_dummy_rel_pathlist and mark_dummy_rel).
1155 */
1157 {
1158 /* Generate a Result plan with constant-FALSE gating qual */
1164 NULL);
1169 }
1171 /*
1172 * Otherwise build an Append plan. Note that if there's just one child,
1173 * the Append is pretty useless; but we wait till setrefs.c to get rid of
1174 * it. Doing so here doesn't work because the varno of the child scan
1175 * plan won't match the parent-rel Vars it'll be asked to emit.
1176 *
1177 * We don't have the actual creation of the Append node split out into a
1178 * separate make_xxx function. This is because we want to run
1179 * prepare_sort_from_pathkeys on it before we do so on the individual
1180 * child plans, to make cross-checking the sort info easier.
1181 */
1190 {
1191 /*
1192 * Compute sort column info, and adjust the Append's tlist as needed.
1193 * Because we pass adjust_tlist_in_place = true, we may ignore the
1194 * function result; it must be the same plan node. However, we then
1195 * need to detect whether any tlist entries were added.
1196 */
1199 NULL,
1207 }
1209 /* If appropriate, consider async append */
1214 /* Build the plan for each child */
1216 {
1220 /* Must insist that all children return the same tlist */
1223 /*
1224 * For ordered Appends, we must insert a Sort node if subplan isn't
1225 * sufficiently ordered.
1226 */
1228 {
1235 /*
1236 * Compute sort column info, and adjust subplan's tlist as needed.
1237 * We must apply prepare_sort_from_pathkeys even to subplans that
1238 * don't need an explicit sort, to make sure they are returning
1239 * the same sort key columns the Append expects.
1240 */
1243 nodeSortColIdx,
1251 /*
1252 * Check that we got the same sort key information. We just
1253 * Assert that the sortops match, since those depend only on the
1254 * pathkeys; but it seems like a good idea to check the sort
1255 * column numbers explicitly, to ensure the tlists match up.
1256 */
1268 /* Now, insert a Sort node if subplan isn't sufficiently ordered */
1270 {
1277 }
1278 }
1282 /* Check to see if subplan can be executed asynchronously */
1284 {
1287 }
1288 }
1290 /*
1291 * If any quals exist, they may be useful to perform further partition
1292 * pruning during execution. Gather information needed by the executor to
1293 * do partition pruning.
1294 */
1296 {
1302 {
1310 }
1313 partpruneinfo =
1316 prunequal);
1317 }
1326 /*
1327 * If prepare_sort_from_pathkeys added sort columns, but we were told to
1328 * produce either the exact tlist or a narrow tlist, we should get rid of
1329 * the sort columns again. We must inject a projection node to do so.
1330 */
1332 {
1334 orig_tlist_length);
1337 }
1338 else
1340 }
1342 /*
1343 * create_merge_append_plan
1344 * Create a MergeAppend plan for 'best_path' and (recursively) plans
1345 * for its subpaths.
1346 *
1347 * Returns a Plan node.
1348 */
1352 {
1364 /*
1365 * We don't have the actual creation of the MergeAppend node split out
1366 * into a separate make_xxx function. This is because we want to run
1367 * prepare_sort_from_pathkeys on it before we do so on the individual
1368 * child plans, to make cross-checking the sort info easier.
1369 */
1377 /*
1378 * Compute sort column info, and adjust MergeAppend's tlist as needed.
1379 * Because we pass adjust_tlist_in_place = true, we may ignore the
1380 * function result; it must be the same plan node. However, we then need
1381 * to detect whether any tlist entries were added.
1382 */
1385 NULL,
1394 /*
1395 * Now prepare the child plans. We must apply prepare_sort_from_pathkeys
1396 * even to subplans that don't need an explicit sort, to make sure they
1397 * are returning the same sort key columns the MergeAppend expects.
1398 */
1400 {
1409 /* Build the child plan */
1410 /* Must insist that all children return the same tlist */
1413 /* Compute sort column info, and adjust subplan's tlist as needed */
1424 /*
1425 * Check that we got the same sort key information. We just Assert
1426 * that the sortops match, since those depend only on the pathkeys;
1427 * but it seems like a good idea to check the sort column numbers
1428 * explicitly, to ensure the tlists really do match up.
1429 */
1441 /* Now, insert a Sort node if subplan isn't sufficiently ordered */
1443 {
1450 }
1453 }
1455 /*
1456 * If any quals exist, they may be useful to perform further partition
1457 * pruning during execution. Gather information needed by the executor to
1458 * do partition pruning.
1459 */
1461 {
1467 {
1475 }
1480 prunequal);
1481 }
1486 /*
1487 * If prepare_sort_from_pathkeys added sort columns, but we were told to
1488 * produce either the exact tlist or a narrow tlist, we should get rid of
1489 * the sort columns again. We must inject a projection node to do so.
1490 */
1492 {
1495 }
1496 else
1498 }
1500 /*
1501 * create_group_result_plan
1502 * Create a Result plan for 'best_path'.
1503 * This is only used for degenerate grouping cases.
1504 *
1505 * Returns a Plan node.
1506 */
1509 {
1516 /* best_path->quals is just bare clauses */
1524 }
1526 /*
1527 * create_project_set_plan
1528 * Create a ProjectSet plan for 'best_path'.
1529 *
1530 * Returns a Plan node.
1531 */
1534 {
1539 /* Since we intend to project, we don't need to constrain child tlist */
1549 }
1551 /*
1552 * create_material_plan
1553 * Create a Material plan for 'best_path' and (recursively) plans
1554 * for its subpaths.
1555 *
1556 * Returns a Plan node.
1557 */
1560 {
1564 /*
1565 * We don't want any excess columns in the materialized tuples, so request
1566 * a smaller tlist. Otherwise, since Material doesn't project, tlist
1567 * requirements pass through.
1568 */
1577 }
1579 /*
1580 * create_memoize_plan
1581 * Create a Memoize plan for 'best_path' and (recursively) plans for its
1582 * subpaths.
1583 *
1584 * Returns a Plan node.
1585 */
1588 {
1613 {
1619 i++;
1620 }
1631 }
1633 /*
1634 * create_unique_plan
1635 * Create a Unique plan for 'best_path' and (recursively) plans
1636 * for its subpaths.
1637 *
1638 * Returns a Plan node.
1639 */
1642 {
1656 /* Unique doesn't project, so tlist requirements pass through */
1659 /* Done if we don't need to do any actual unique-ifying */
1663 /*
1664 * As constructed, the subplan has a "flat" tlist containing just the Vars
1665 * needed here and at upper levels. The values we are supposed to
1666 * unique-ify may be expressions in these variables. We have to add any
1667 * such expressions to the subplan's tlist.
1668 *
1669 * The subplan may have a "physical" tlist if it is a simple scan plan. If
1670 * we're going to sort, this should be reduced to the regular tlist, so
1671 * that we don't sort more data than we need to. For hashing, the tlist
1672 * should be left as-is if we don't need to add any expressions; but if we
1673 * do have to add expressions, then a projection step will be needed at
1674 * runtime anyway, so we may as well remove unneeded items. Therefore
1675 * newtlist starts from build_path_tlist() not just a copy of the
1676 * subplan's tlist; and we don't install it into the subplan unless we are
1677 * sorting or stuff has to be added.
1678 */
1682 /* initialize modified subplan tlist as just the "required" vars */
1688 {
1694 {
1696 nextresno,
1697 NULL,
1700 nextresno++;
1702 }
1703 }
1705 /* Use change_plan_targetlist in case we need to insert a Result node */
1710 /*
1711 * Build control information showing which subplan output columns are to
1712 * be examined by the grouping step. Unfortunately we can't merge this
1713 * with the previous loop, since we didn't then know which version of the
1714 * subplan tlist we'd end up using.
1715 */
1723 {
1732 groupColPos++;
1733 }
1736 {
1739 /*
1740 * Get the hashable equality operators for the Agg node to use.
1741 * Normally these are the same as the IN clause operators, but if
1742 * those are cross-type operators then the equality operators are the
1743 * ones for the IN clause operators' RHS datatype.
1744 */
1748 {
1750 Oid eq_oper;
1754 in_oper);
1756 }
1758 /*
1759 * Since the Agg node is going to project anyway, we can give it the
1760 * minimum output tlist, without any stuff we might have added to the
1761 * subplan tlist.
1762 */
1764 NIL,
1765 AGG_HASHED,
1766 AGGSPLIT_SIMPLE,
1767 numGroupCols,
1768 groupColIdx,
1769 groupOperators,
1770 groupCollations,
1771 NIL,
1772 NIL,
1775 subplan);
1776 }
1777 else
1778 {
1782 /* Create an ORDER BY list to sort the input compatibly */
1785 {
1787 Oid sortop;
1788 Oid eqop;
1795 in_oper);
1797 /*
1798 * The Unique node will need equality operators. Normally these
1799 * are the same as the IN clause operators, but if those are
1800 * cross-type operators then the equality operators are the ones
1801 * for the IN clause operators' RHS datatype.
1802 */
1806 sortop);
1820 groupColPos++;
1821 }
1825 }
1827 /* Copy cost data from Path to Plan */
1831 }
1833 /*
1834 * create_gather_plan
1835 *
1836 * Create a Gather plan for 'best_path' and (recursively) plans
1837 * for its subpaths.
1838 */
1841 {
1846 /*
1847 * Push projection down to the child node. That way, the projection work
1848 * is parallelized, and there can be no system columns in the result (they
1849 * can't travel through a tuple queue because it uses MinimalTuple
1850 * representation).
1851 */
1857 NIL,
1861 subplan);
1865 /* use parallel mode for parallel plans. */
1869 }
1871 /*
1872 * create_gather_merge_plan
1873 *
1874 * Create a Gather Merge plan for 'best_path' and (recursively)
1875 * plans for its subpaths.
1876 */
1879 {
1885 /* As with Gather, project away columns in the workers. */
1888 /* Create a shell for a GatherMerge plan. */
1894 /* Assign the rescan Param. */
1897 /* Gather Merge is pointless with no pathkeys; use Gather instead. */
1900 /* Compute sort column info, and adjust subplan's tlist as needed */
1912 /*
1913 * All gather merge paths should have already guaranteed the necessary
1914 * sort order either by adding an explicit sort node or by using presorted
1915 * input. We can't simply add a sort here on additional pathkeys, because
1916 * we can't guarantee the sort would be safe. For example, expressions may
1917 * be volatile or otherwise parallel unsafe.
1918 */
1922 /* Now insert the subplan under GatherMerge. */
1925 /* use parallel mode for parallel plans. */
1929 }
1931 /*
1932 * create_projection_plan
1933 *
1934 * Create a plan tree to do a projection step and (recursively) plans
1935 * for its subpaths. We may need a Result node for the projection,
1936 * but sometimes we can just let the subplan do the work.
1937 */
1940 {
1946 /*
1947 * Convert our subpath to a Plan and determine whether we need a Result
1948 * node.
1949 *
1950 * In most cases where we don't need to project, creation_projection_path
1951 * will have set dummypp, but not always. First, some createplan.c
1952 * routines change the tlists of their nodes. (An example is that
1953 * create_merge_append_plan might add resjunk sort columns to a
1954 * MergeAppend.) Second, create_projection_path has no way of knowing
1955 * what path node will be placed on top of the projection path and
1956 * therefore can't predict whether it will require an exact tlist. For
1957 * both of these reasons, we have to recheck here.
1958 */
1960 {
1961 /*
1962 * Our caller doesn't really care what tlist we return, so we don't
1963 * actually need to project. However, we may still need to ensure
1964 * proper sortgroupref labels, if the caller cares about those.
1965 */
1971 }
1973 {
1974 /*
1975 * Our caller requires that we return the exact tlist, but no separate
1976 * result node is needed because the subpath is projection-capable.
1977 * Tell create_plan_recurse that we're going to ignore the tlist it
1978 * produces.
1979 */
1981 CP_IGNORE_TLIST);
1984 }
1985 else
1986 {
1987 /*
1988 * It looks like we need a result node, unless by good fortune the
1989 * requested tlist is exactly the one the child wants to produce.
1990 */
1994 }
1996 /*
1997 * If we make a different decision about whether to include a Result node
1998 * than create_projection_path did, we'll have made slightly wrong cost
1999 * estimates; but label the plan with the cost estimates we actually used,
2000 * not "corrected" ones. (XXX this could be cleaned up if we moved more
2001 * of the sortcolumn setup logic into Path creation, but that would add
2002 * expense to creating Paths we might end up not using.)
2003 */
2005 {
2006 /* Don't need a separate Result, just assign tlist to subplan */
2010 /* Label plan with the estimated costs we actually used */
2016 /* ... but don't change subplan's parallel_aware flag */
2017 }
2018 else
2019 {
2020 /* We need a Result node */
2024 }
2027 }
2029 /*
2030 * inject_projection_plan
2031 * Insert a Result node to do a projection step.
2032 *
2033 * This is used in a few places where we decide on-the-fly that we need a
2034 * projection step as part of the tree generated for some Path node.
2035 * We should try to get rid of this in favor of doing it more honestly.
2036 *
2037 * One reason it's ugly is we have to be told the right parallel_safe marking
2038 * to apply (since the tlist might be unsafe even if the child plan is safe).
2039 */
2042 {
2047 /*
2048 * In principle, we should charge tlist eval cost plus cpu_per_tuple per
2049 * row for the Result node. But the former has probably been factored in
2050 * already and the latter was not accounted for during Path construction,
2051 * so being formally correct might just make the EXPLAIN output look less
2052 * consistent not more so. Hence, just copy the subplan's cost.
2053 */
2058 }
2060 /*
2061 * change_plan_targetlist
2062 * Externally available wrapper for inject_projection_plan.
2063 *
2064 * This is meant for use by FDW plan-generation functions, which might
2065 * want to adjust the tlist computed by some subplan tree. In general,
2066 * a Result node is needed to compute the new tlist, but we can optimize
2067 * some cases.
2068 *
2069 * In most cases, tlist_parallel_safe can just be passed as the parallel_safe
2070 * flag of the FDW's own Path node.
2071 */
2072 Plan *
2074 {
2075 /*
2076 * If the top plan node can't do projections and its existing target list
2077 * isn't already what we need, we need to add a Result node to help it
2078 * along.
2079 */
2084 tlist_parallel_safe);
2085 else
2086 {
2087 /* Else we can just replace the plan node's tlist */
2090 }
2092 }
2094 /*
2095 * create_sort_plan
2096 *
2097 * Create a Sort plan for 'best_path' and (recursively) plans
2098 * for its subpaths.
2099 */
2102 {
2106 /*
2107 * We don't want any excess columns in the sorted tuples, so request a
2108 * smaller tlist. Otherwise, since Sort doesn't project, tlist
2109 * requirements pass through.
2110 */
2114 /*
2115 * make_sort_from_pathkeys indirectly calls find_ec_member_matching_expr,
2116 * which will ignore any child EC members that don't belong to the given
2117 * relids. Thus, if this sort path is based on a child relation, we must
2118 * pass its relids.
2119 */
2127 }
2129 /*
2130 * create_incrementalsort_plan
2131 *
2132 * Do the same as create_sort_plan, but create IncrementalSort plan.
2133 */
2137 {
2141 /* See comments in create_sort_plan() above */
2153 }
2155 /*
2156 * create_group_plan
2157 *
2158 * Create a Group plan for 'best_path' and (recursively) plans
2159 * for its subpaths.
2160 */
2163 {
2169 /*
2170 * Group can project, so no need to be terribly picky about child tlist,
2171 * but we do need grouping columns to be available
2172 */
2180 quals,
2187 subplan);
2192 }
2194 /*
2195 * create_upper_unique_plan
2196 *
2197 * Create a Unique plan for 'best_path' and (recursively) plans
2198 * for its subpaths.
2199 */
2202 {
2206 /*
2207 * Unique doesn't project, so tlist requirements pass through; moreover we
2208 * need grouping columns to be labeled.
2209 */
2220 }
2222 /*
2223 * create_agg_plan
2224 *
2225 * Create an Agg plan for 'best_path' and (recursively) plans
2226 * for its subpaths.
2227 */
2230 {
2236 /*
2237 * Agg can project, so no need to be terribly picky about child tlist, but
2238 * we do need grouping columns to be available
2239 */
2255 NIL,
2256 NIL,
2259 subplan);
2264 }
2266 /*
2267 * Given a groupclause for a collection of grouping sets, produce the
2268 * corresponding groupColIdx.
2269 *
2270 * root->grouping_map maps the tleSortGroupRef to the actual column position in
2271 * the input tuple. So we get the ref from the entries in the groupclause and
2272 * look them up there.
2273 */
2276 {
2288 {
2292 }
2295 }
2297 /*
2298 * create_groupingsets_plan
2299 * Create a plan for 'best_path' and (recursively) plans
2300 * for its subpaths.
2301 *
2302 * What we emit is an Agg plan with some vestigial Agg and Sort nodes
2303 * hanging off the side. The top Agg implements the last grouping set
2304 * specified in the GroupingSetsPath, and any additional grouping sets
2305 * each give rise to a subsidiary Agg and Sort node in the top Agg's
2306 * "chain" list. These nodes don't participate in the plan directly,
2307 * but they are a convenient way to represent the required data for
2308 * the extra steps.
2309 *
2310 * Returns a Plan node.
2311 */
2314 {
2323 /* Shouldn't get here without grouping sets */
2327 /*
2328 * Agg can project, so no need to be terribly picky about child tlist, but
2329 * we do need grouping columns to be available
2330 */
2333 /*
2334 * Compute the mapping from tleSortGroupRef to column index in the child's
2335 * tlist. First, identify max SortGroupRef in groupClause, for array
2336 * sizing.
2337 */
2340 {
2345 }
2349 /* Now look up the column numbers in the child's tlist */
2351 {
2356 }
2358 /*
2359 * During setrefs.c, we'll need the grouping_map to fix up the cols lists
2360 * in GroupingFunc nodes. Save it for setrefs.c to use.
2361 */
2365 /*
2366 * Generate the side nodes that describe the other sort and group
2367 * operations besides the top one. Note that we don't worry about putting
2368 * accurate cost estimates in the side nodes; only the topmost Agg node's
2369 * costs will be shown by EXPLAIN.
2370 */
2373 {
2377 {
2382 AggStrategy strat;
2387 {
2390 new_grpColIdx,
2391 subplan);
2392 }
2401 else
2405 NIL,
2406 strat,
2407 AGGSPLIT_SIMPLE,
2409 new_grpColIdx,
2413 NIL,
2416 sort_plan);
2418 /*
2419 * Remove stuff we don't need to avoid bloating debug output.
2420 */
2422 {
2425 }
2428 }
2429 }
2431 /*
2432 * Now make the real Agg node
2433 */
2434 {
2446 AGGSPLIT_SIMPLE,
2447 numGroupCols,
2448 top_grpColIdx,
2452 chain,
2455 subplan);
2457 /* Copy cost data from Path to Plan */
2459 }
2462 }
2464 /*
2465 * create_minmaxagg_plan
2466 *
2467 * Create a Result plan for 'best_path' and (recursively) plans
2468 * for its subpaths.
2469 */
2472 {
2477 /* Prepare an InitPlan for each aggregate's subquery. */
2479 {
2485 /*
2486 * Generate the plan for the subquery. We already have a Path, but we
2487 * have to convert it to a Plan and attach a LIMIT node above it.
2488 * Since we are entering a different planner context (subroot),
2489 * recurse to create_plan not create_plan_recurse.
2490 */
2499 /* Must apply correct cost/width data to Limit node */
2507 /* Convert the plan into an InitPlan in the outer query. */
2509 }
2511 /* Generate the output plan --- basically just a Result */
2518 /*
2519 * During setrefs.c, we'll need to replace references to the Agg nodes
2520 * with InitPlan output params. (We can't just do that locally in the
2521 * MinMaxAgg node, because path nodes above here may have Agg references
2522 * as well.) Save the mmaggregates list to tell setrefs.c to do that.
2523 */
2528 }
2530 /*
2531 * create_windowagg_plan
2532 *
2533 * Create a WindowAgg plan for 'best_path' and (recursively) plans
2534 * for its subpaths.
2535 */
2538 {
2555 /*
2556 * Choice of tlist here is motivated by the fact that WindowAgg will be
2557 * storing the input rows of window frames in a tuplestore; it therefore
2558 * behooves us to request a small tlist to avoid wasting space. We do of
2559 * course need grouping columns to be available.
2560 */
2566 /*
2567 * Convert SortGroupClause lists into arrays of attr indexes and equality
2568 * operators, as wanted by executor. (Note: in principle, it's possible
2569 * to drop some of the sort columns, if they were proved redundant by
2570 * pathkey logic. However, it doesn't seem worth going out of our way to
2571 * optimize such cases. In any case, we must *not* remove the ordering
2572 * column for RANGE OFFSET cases, as the executor needs that for in_range
2573 * tests even if it's known to be equal to some partitioning column.)
2574 */
2581 {
2589 partNumCols++;
2590 }
2598 {
2606 ordNumCols++;
2607 }
2609 /* And finally we can make the WindowAgg node */
2612 partNumCols,
2613 partColIdx,
2614 partOperators,
2615 partCollations,
2616 ordNumCols,
2617 ordColIdx,
2618 ordOperators,
2619 ordCollations,
2628 subplan);
2633 }
2635 /*
2636 * create_setop_plan
2637 *
2638 * Create a SetOp plan for 'best_path' and (recursively) plans
2639 * for its subpaths.
2640 */
2643 {
2648 /*
2649 * SetOp doesn't project, so tlist requirements pass through; moreover we
2650 * need grouping columns to be labeled.
2651 */
2655 /* Convert numGroups to long int --- but 'ware overflow! */
2660 subplan,
2664 numGroups);
2669 }
2671 /*
2672 * create_recursiveunion_plan
2673 *
2674 * Create a RecursiveUnion plan for 'best_path' and (recursively) plans
2675 * for its subpaths.
2676 */
2679 {
2686 /* Need both children to produce same tlist, so force it */
2692 /* Convert numGroups to long int --- but 'ware overflow! */
2696 leftplan,
2697 rightplan,
2700 numGroups);
2705 }
2707 /*
2708 * create_lockrows_plan
2709 *
2710 * Create a LockRows plan for 'best_path' and (recursively) plans
2711 * for its subpaths.
2712 */
2716 {
2720 /* LockRows doesn't project, so tlist requirements pass through */
2728 }
2730 /*
2731 * create_modifytable_plan
2732 * Create a ModifyTable plan for 'best_path'.
2733 *
2734 * Returns a Plan node.
2735 */
2738 {
2743 /* Subplan must produce exactly the specified tlist */
2746 /* Transfer resname/resjunk labeling, too, to keep executor happy */
2750 subplan,
2767 }
2769 /*
2770 * create_limit_plan
2771 *
2772 * Create a Limit plan for 'best_path' and (recursively) plans
2773 * for its subpaths.
2774 */
2777 {
2785 /* Limit doesn't project, so tlist requirements pass through */
2788 /* Extract information necessary for comparing rows for WITH TIES. */
2790 {
2801 {
2808 numUniqkeys++;
2809 }
2810 }
2821 }
2824 /*****************************************************************************
2825 *
2826 * BASE-RELATION SCAN METHODS
2827 *
2828 *****************************************************************************/
2831 /*
2832 * create_seqscan_plan
2833 * Returns a seqscan plan for the base relation scanned by 'best_path'
2834 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
2835 */
2839 {
2843 /* it should be a base rel... */
2847 /* Sort clauses into best execution order */
2850 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
2853 /* Replace any outer-relation variables with nestloop params */
2855 {
2858 }
2861 scan_clauses,
2862 scan_relid);
2867 }
2869 /*
2870 * create_samplescan_plan
2871 * Returns a samplescan plan for the base relation scanned by 'best_path'
2872 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
2873 */
2877 {
2883 /* it should be a base rel with a tablesample clause... */
2890 /* Sort clauses into best execution order */
2893 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
2896 /* Replace any outer-relation variables with nestloop params */
2898 {
2903 }
2906 scan_clauses,
2907 scan_relid,
2908 tsc);
2913 }
2915 /*
2916 * create_indexscan_plan
2917 * Returns an indexscan plan for the base relation scanned by 'best_path'
2918 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
2919 *
2920 * We use this for both plain IndexScans and IndexOnlyScans, because the
2921 * qual preprocessing work is the same for both. Note that the caller tells
2922 * us which to build --- we don't look at best_path->path.pathtype, because
2923 * create_bitmap_subplan needs to be able to override the prior decision.
2924 */
2931 {
2945 /* it should be a base rel... */
2949 /*
2950 * Extract the index qual expressions (stripped of RestrictInfos) from the
2951 * IndexClauses list, and prepare a copy with index Vars substituted for
2952 * table Vars. (This step also does replace_nestloop_params on the
2953 * fixed_indexquals.)
2954 */
2959 /*
2960 * Likewise fix up index attr references in the ORDER BY expressions.
2961 */
2964 /*
2965 * The qpqual list must contain all restrictions not automatically handled
2966 * by the index, other than pseudoconstant clauses which will be handled
2967 * by a separate gating plan node. All the predicates in the indexquals
2968 * will be checked (either by the index itself, or by nodeIndexscan.c),
2969 * but if there are any "special" operators involved then they must be
2970 * included in qpqual. The upshot is that qpqual must contain
2971 * scan_clauses minus whatever appears in indexquals.
2972 *
2973 * is_redundant_with_indexclauses() detects cases where a scan clause is
2974 * present in the indexclauses list or is generated from the same
2975 * EquivalenceClass as some indexclause, and is therefore redundant with
2976 * it, though not equal. (The latter happens when indxpath.c prefers a
2977 * different derived equality than what generate_join_implied_equalities
2978 * picked for a parameterized scan's ppi_clauses.) Note that it will not
2979 * match to lossy index clauses, which is critical because we have to
2980 * include the original clause in qpqual in that case.
2981 *
2982 * In some situations (particularly with OR'd index conditions) we may
2983 * have scan_clauses that are not equal to, but are logically implied by,
2984 * the index quals; so we also try a predicate_implied_by() check to see
2985 * if we can discard quals that way. (predicate_implied_by assumes its
2986 * first input contains only immutable functions, so we have to check
2987 * that.)
2988 *
2989 * Note: if you change this bit of code you should also look at
2990 * extract_nonindex_conditions() in costsize.c.
2991 */
2994 {
3006 }
3008 /* Sort clauses into best execution order */
3011 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3014 /*
3015 * We have to replace any outer-relation variables with nestloop params in
3016 * the indexqualorig, qpqual, and indexorderbyorig expressions. A bit
3017 * annoying to have to do this separately from the processing in
3018 * fix_indexqual_references --- rethink this when generalizing the inner
3019 * indexscan support. But note we can't really do this earlier because
3020 * it'd break the comparisons to predicates above ... (or would it? Those
3021 * wouldn't have outer refs)
3022 */
3024 {
3031 }
3033 /*
3034 * If there are ORDER BY expressions, look up the sort operators for their
3035 * result datatypes.
3036 */
3038 {
3042 /*
3043 * PathKey contains OID of the btree opfamily we're sorting by, but
3044 * that's not quite enough because we need the expression's datatype
3045 * to look up the sort operator in the operator family.
3046 */
3049 {
3053 Oid sortop;
3055 /* Get sort operator from opfamily */
3057 exprtype,
3058 exprtype,
3064 }
3065 }
3067 /*
3068 * For an index-only scan, we must mark indextlist entries as resjunk if
3069 * they are columns that the index AM can't return; this cues setrefs.c to
3070 * not generate references to those columns.
3071 */
3073 {
3077 {
3081 i++;
3082 }
3083 }
3085 /* Finally ready to build the plan node */
3088 qpqual,
3089 baserelid,
3090 indexoid,
3091 fixed_indexquals,
3092 stripped_indexquals,
3093 fixed_indexorderbys,
3096 else
3098 qpqual,
3099 baserelid,
3100 indexoid,
3101 fixed_indexquals,
3102 stripped_indexquals,
3103 fixed_indexorderbys,
3104 indexorderbys,
3105 indexorderbyops,
3111 }
3113 /*
3114 * create_bitmap_scan_plan
3115 * Returns a bitmap scan plan for the base relation scanned by 'best_path'
3116 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3117 */
3123 {
3133 /* it should be a base rel... */
3137 /* Process the bitmapqual tree into a Plan tree and qual lists */
3145 /*
3146 * The qpqual list must contain all restrictions not automatically handled
3147 * by the index, other than pseudoconstant clauses which will be handled
3148 * by a separate gating plan node. All the predicates in the indexquals
3149 * will be checked (either by the index itself, or by
3150 * nodeBitmapHeapscan.c), but if there are any "special" operators
3151 * involved then they must be added to qpqual. The upshot is that qpqual
3152 * must contain scan_clauses minus whatever appears in indexquals.
3153 *
3154 * This loop is similar to the comparable code in create_indexscan_plan(),
3155 * but with some differences because it has to compare the scan clauses to
3156 * stripped (no RestrictInfos) indexquals. See comments there for more
3157 * info.
3158 *
3159 * In normal cases simple equal() checks will be enough to spot duplicate
3160 * clauses, so we try that first. We next see if the scan clause is
3161 * redundant with any top-level indexqual by virtue of being generated
3162 * from the same EC. After that, try predicate_implied_by().
3163 *
3164 * Unlike create_indexscan_plan(), the predicate_implied_by() test here is
3165 * useful for getting rid of qpquals that are implied by index predicates,
3166 * because the predicate conditions are included in the "indexquals"
3167 * returned by create_bitmap_subplan(). Bitmap scans have to do it that
3168 * way because predicate conditions need to be rechecked if the scan
3169 * becomes lossy, so they have to be included in bitmapqualorig.
3170 */
3173 {
3187 }
3189 /* Sort clauses into best execution order */
3192 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3195 /*
3196 * When dealing with special operators, we will at this point have
3197 * duplicate clauses in qpqual and bitmapqualorig. We may as well drop
3198 * 'em from bitmapqualorig, since there's no point in making the tests
3199 * twice.
3200 */
3203 /*
3204 * We have to replace any outer-relation variables with nestloop params in
3205 * the qpqual and bitmapqualorig expressions. (This was already done for
3206 * expressions attached to plan nodes in the bitmapqualplan tree.)
3207 */
3209 {
3214 }
3216 /* Finally ready to build the plan node */
3218 qpqual,
3219 bitmapqualplan,
3220 bitmapqualorig,
3221 baserelid);
3226 }
3228 /*
3229 * Given a bitmapqual tree, generate the Plan tree that implements it
3230 *
3231 * As byproducts, we also return in *qual and *indexqual the qual lists
3232 * (in implicit-AND form, without RestrictInfos) describing the original index
3233 * conditions and the generated indexqual conditions. (These are the same in
3234 * simple cases, but when special index operators are involved, the former
3235 * list includes the special conditions while the latter includes the actual
3236 * indexable conditions derived from them.) Both lists include partial-index
3237 * predicates, because we have to recheck predicates as well as index
3238 * conditions if the bitmap scan becomes lossy.
3239 *
3240 * In addition, we return a list of EquivalenceClass pointers for all the
3241 * top-level indexquals that were possibly-redundantly derived from ECs.
3242 * This allows removal of scan_clauses that are redundant with such quals.
3243 * (We do not attempt to detect such redundancies for quals that are within
3244 * OR subtrees. This could be done in a less hacky way if we returned the
3245 * indexquals in RestrictInfo form, but that would be slower and still pretty
3246 * messy, since we'd have to build new RestrictInfos in many cases.)
3247 */
3251 {
3255 {
3263 /*
3264 * There may well be redundant quals among the subplans, since a
3265 * top-level WHERE qual might have gotten used to form several
3266 * different index quals. We don't try exceedingly hard to eliminate
3267 * redundancies, but we do eliminate obvious duplicates by using
3268 * list_concat_unique.
3269 */
3271 {
3283 /* Duplicates in indexECs aren't worth getting rid of */
3285 }
3297 }
3299 {
3308 /*
3309 * Here, we only detect qual-free subplans. A qual-free subplan would
3310 * cause us to generate "... OR true ..." which we may as well reduce
3311 * to just "true". We do not try to eliminate redundant subclauses
3312 * because (a) it's not as likely as in the AND case, and (b) we might
3313 * well be working with hundreds or even thousands of OR conditions,
3314 * perhaps from a long IN list. The performance of list_append_unique
3315 * would be unacceptable.
3316 */
3318 {
3338 }
3340 /*
3341 * In the presence of ScalarArrayOpExpr quals, we might have built
3342 * BitmapOrPaths with just one subpath; don't add an OR step.
3343 */
3345 {
3347 }
3348 else
3349 {
3358 }
3360 /*
3361 * If there were constant-TRUE subquals, the OR reduces to constant
3362 * TRUE. Also, avoid generating one-element ORs, which could happen
3363 * due to redundancy elimination or ScalarArrayOpExpr quals.
3364 */
3369 else
3375 else
3378 }
3380 {
3388 /* Use the regular indexscan plan build machinery... */
3392 /* then convert to a bitmap indexscan */
3397 /* and set its cost/width fields appropriately */
3405 /* Extract original index clauses, actual index quals, relevant ECs */
3410 {
3420 }
3421 /* We can add any index predicate conditions, too */
3423 {
3426 /*
3427 * We know that the index predicate must have been implied by the
3428 * query condition as a whole, but it may or may not be implied by
3429 * the conditions that got pushed into the bitmapqual. Avoid
3430 * generating redundant conditions.
3431 */
3433 {
3436 }
3437 }
3441 }
3442 else
3443 {
3446 }
3449 }
3451 /*
3452 * create_tidscan_plan
3453 * Returns a tidscan plan for the base relation scanned by 'best_path'
3454 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3455 */
3459 {
3464 /* it should be a base rel... */
3468 /*
3469 * The qpqual list must contain all restrictions not enforced by the
3470 * tidquals list. Since tidquals has OR semantics, we have to be careful
3471 * about matching it up to scan_clauses. It's convenient to handle the
3472 * single-tidqual case separately from the multiple-tidqual case. In the
3473 * single-tidqual case, we look through the scan_clauses while they are
3474 * still in RestrictInfo form, and drop any that are redundant with the
3475 * tidqual.
3476 *
3477 * In normal cases simple pointer equality checks will be enough to spot
3478 * duplicate RestrictInfos, so we try that first.
3479 *
3480 * Another common case is that a scan_clauses entry is generated from the
3481 * same EquivalenceClass as some tidqual, and is therefore redundant with
3482 * it, though not equal.
3483 *
3484 * Unlike indexpaths, we don't bother with predicate_implied_by(); the
3485 * number of cases where it could win are pretty small.
3486 */
3488 {
3493 {
3503 }
3505 }
3507 /* Sort clauses into best execution order */
3510 /* Reduce RestrictInfo lists to bare expressions; ignore pseudoconstants */
3514 /*
3515 * If we have multiple tidquals, it's more convenient to remove duplicate
3516 * scan_clauses after stripping the RestrictInfos. In this situation,
3517 * because the tidquals represent OR sub-clauses, they could not have come
3518 * from EquivalenceClasses so we don't have to worry about matching up
3519 * non-identical clauses. On the other hand, because tidpath.c will have
3520 * extracted those sub-clauses from some OR clause and built its own list,
3521 * we will certainly not have pointer equality to any scan clause. So
3522 * convert the tidquals list to an explicit OR clause and see if we can
3523 * match it via equal() to any scan clause.
3524 */
3529 /* Replace any outer-relation variables with nestloop params */
3531 {
3536 }
3539 scan_clauses,
3540 scan_relid,
3541 tidquals);
3546 }
3548 /*
3549 * create_tidrangescan_plan
3550 * Returns a tidrangescan plan for the base relation scanned by 'best_path'
3551 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3552 */
3556 {
3561 /* it should be a base rel... */
3565 /*
3566 * The qpqual list must contain all restrictions not enforced by the
3567 * tidrangequals list. tidrangequals has AND semantics, so we can simply
3568 * remove any qual that appears in it.
3569 */
3570 {
3575 {
3583 }
3585 }
3587 /* Sort clauses into best execution order */
3590 /* Reduce RestrictInfo lists to bare expressions; ignore pseudoconstants */
3594 /* Replace any outer-relation variables with nestloop params */
3596 {
3601 }
3604 scan_clauses,
3605 scan_relid,
3606 tidrangequals);
3611 }
3613 /*
3614 * create_subqueryscan_plan
3615 * Returns a subqueryscan plan for the base relation scanned by 'best_path'
3616 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3617 */
3621 {
3627 /* it should be a subquery base rel... */
3631 /*
3632 * Recursively create Plan from Path for subquery. Since we are entering
3633 * a different planner context (subroot), recurse to create_plan not
3634 * create_plan_recurse.
3635 */
3638 /* Sort clauses into best execution order */
3641 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3644 /* Replace any outer-relation variables with nestloop params */
3646 {
3651 }
3654 scan_clauses,
3655 scan_relid,
3656 subplan);
3661 }
3663 /*
3664 * create_functionscan_plan
3665 * Returns a functionscan plan for the base relation scanned by 'best_path'
3666 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3667 */
3671 {
3677 /* it should be a function base rel... */
3683 /* Sort clauses into best execution order */
3686 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3689 /* Replace any outer-relation variables with nestloop params */
3691 {
3694 /* The function expressions could contain nestloop params, too */
3696 }
3704 }
3706 /*
3707 * create_tablefuncscan_plan
3708 * Returns a tablefuncscan plan for the base relation scanned by 'best_path'
3709 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3710 */
3714 {
3720 /* it should be a function base rel... */
3726 /* Sort clauses into best execution order */
3729 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3732 /* Replace any outer-relation variables with nestloop params */
3734 {
3737 /* The function expressions could contain nestloop params, too */
3739 }
3742 tablefunc);
3747 }
3749 /*
3750 * create_valuesscan_plan
3751 * Returns a valuesscan plan for the base relation scanned by 'best_path'
3752 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3753 */
3757 {
3763 /* it should be a values base rel... */
3769 /* Sort clauses into best execution order */
3772 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3775 /* Replace any outer-relation variables with nestloop params */
3777 {
3780 /* The values lists could contain nestloop params, too */
3783 }
3786 values_lists);
3791 }
3793 /*
3794 * create_ctescan_plan
3795 * Returns a ctescan plan for the base relation scanned by 'best_path'
3796 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3797 */
3801 {
3809 Index levelsup;
3818 /*
3819 * Find the referenced CTE, and locate the SubPlan previously made for it.
3820 */
3824 {
3828 }
3830 /*
3831 * Note: cte_plan_ids can be shorter than cteList, if we are still working
3832 * on planning the CTEs (ie, this is a side-reference from another CTE).
3833 * So we mustn't use forboth here.
3834 */
3837 {
3842 ndx++;
3843 }
3851 {
3855 }
3859 /*
3860 * We need the CTE param ID, which is the sole member of the SubPlan's
3861 * setParam list.
3862 */
3865 /* Sort clauses into best execution order */
3868 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3871 /* Replace any outer-relation variables with nestloop params */
3873 {
3876 }
3884 }
3886 /*
3887 * create_namedtuplestorescan_plan
3888 * Returns a tuplestorescan plan for the base relation scanned by
3889 * 'best_path' with restriction clauses 'scan_clauses' and targetlist
3890 * 'tlist'.
3891 */
3895 {
3904 /* Sort clauses into best execution order */
3907 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3910 /* Replace any outer-relation variables with nestloop params */
3912 {
3915 }
3923 }
3925 /*
3926 * create_resultscan_plan
3927 * Returns a Result plan for the RTE_RESULT base relation scanned by
3928 * 'best_path' with restriction clauses 'scan_clauses' and targetlist
3929 * 'tlist'.
3930 */
3934 {
3943 /* Sort clauses into best execution order */
3946 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3949 /* Replace any outer-relation variables with nestloop params */
3951 {
3954 }
3961 }
3963 /*
3964 * create_worktablescan_plan
3965 * Returns a worktablescan plan for the base relation scanned by 'best_path'
3966 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3967 */
3971 {
3975 Index levelsup;
3983 /*
3984 * We need to find the worktable param ID, which is in the plan level
3985 * that's processing the recursive UNION, which is one level *below* where
3986 * the CTE comes from.
3987 */
3991 levelsup--;
3994 {
3998 }
4002 /* Sort clauses into best execution order */
4005 /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
4008 /* Replace any outer-relation variables with nestloop params */
4010 {
4013 }
4021 }
4023 /*
4024 * create_foreignscan_plan
4025 * Returns a foreignscan plan for the relation scanned by 'best_path'
4026 * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
4027 */
4031 {
4040 /* transform the child path if any */
4043 CP_EXACT_TLIST);
4045 /*
4046 * If we're scanning a base relation, fetch its OID. (Irrelevant if
4047 * scanning a join relation.)
4048 */
4050 {
4057 }
4059 /*
4060 * Sort clauses into best execution order. We do this first since the FDW
4061 * might have more info than we do and wish to adjust the ordering.
4062 */
4065 /*
4066 * Let the FDW perform its processing on the restriction clauses and
4067 * generate the plan node. Note that the FDW might remove restriction
4068 * clauses that it intends to execute remotely, or even add more (if it
4069 * has selected some join clauses for remote use but also wants them
4070 * rechecked locally).
4071 */
4073 best_path,
4075 outer_plan);
4077 /* Copy cost data from Path to Plan; no need to make FDW do this */
4080 /* Copy foreign server OID; likewise, no need to make FDW do this */
4083 /*
4084 * Likewise, copy the relids that are represented by this foreign scan. An
4085 * upper rel doesn't have relids set, but it covers all the base relations
4086 * participating in the underlying scan, so use root's all_baserels.
4087 */
4090 else
4093 /*
4094 * If this is a foreign join, and to make it valid to push down we had to
4095 * assume that the current user is the same as some user explicitly named
4096 * in the query, mark the finished plan as depending on the current user.
4097 */
4101 /*
4102 * Replace any outer-relation variables with nestloop params in the qual,
4103 * fdw_exprs and fdw_recheck_quals expressions. We do this last so that
4104 * the FDW doesn't have to be involved. (Note that parts of fdw_exprs or
4105 * fdw_recheck_quals could have come from join clauses, so doing this
4106 * beforehand on the scan_clauses wouldn't work.) We assume
4107 * fdw_scan_tlist contains no such variables.
4108 */
4110 {
4118 }
4120 /*
4121 * If rel is a base relation, detect whether any system columns are
4122 * requested from the rel. (If rel is a join relation, rel->relid will be
4123 * 0, but there can be no Var with relid 0 in the rel's targetlist or the
4124 * restriction clauses, so we skip this in that case. Note that any such
4125 * columns in base relations that were joined are assumed to be contained
4126 * in fdw_scan_tlist.) This is a bit of a kluge and might go away
4127 * someday, so we intentionally leave it out of the API presented to FDWs.
4128 */
4131 {
4136 /*
4137 * First, examine all the attributes needed for joins or final output.
4138 * Note: we must look at rel's targetlist, not the attr_needed data,
4139 * because attr_needed isn't computed for inheritance child rels.
4140 */
4143 /* Add all the attributes used by restriction clauses. */
4145 {
4149 }
4151 /* Now, are any system columns requested from rel? */
4153 {
4155 {
4158 }
4159 }
4162 }
4165 }
4167 /*
4168 * create_customscan_plan
4169 *
4170 * Transform a CustomPath into a Plan.
4171 */
4175 {
4181 /* Recursively transform child paths. */
4183 {
4185 CP_EXACT_TLIST);
4188 }
4190 /*
4191 * Sort clauses into the best execution order, although custom-scan
4192 * provider can reorder them again.
4193 */
4196 /*
4197 * Invoke custom plan provider to create the Plan node represented by the
4198 * CustomPath.
4199 */
4202 rel,
4203 best_path,
4204 tlist,
4205 scan_clauses,
4206 custom_plans));
4208 /*
4209 * Copy cost data from Path to Plan; no need to make custom-plan providers
4210 * do this
4211 */
4214 /* Likewise, copy the relids that are represented by this custom scan */
4217 /*
4218 * Replace any outer-relation variables with nestloop params in the qual
4219 * and custom_exprs expressions. We do this last so that the custom-plan
4220 * provider doesn't have to be involved. (Note that parts of custom_exprs
4221 * could have come from join clauses, so doing this beforehand on the
4222 * scan_clauses wouldn't work.) We assume custom_scan_tlist contains no
4223 * such variables.
4224 */
4226 {
4231 }
4234 }
4237 /*****************************************************************************
4238 *
4239 * JOIN METHODS
4240 *
4241 *****************************************************************************/
4246 {
4254 Relids outerrelids;
4258 /* NestLoop can project, so no need to be picky about child tlists */
4261 /* For a nestloop, include outer relids in curOuterRels for inner side */
4267 /* Restore curOuterRels */
4271 /* Sort join qual clauses into best execution order */
4274 /* Get the join qual clauses (in plain expression form) */
4275 /* Any pseudoconstant clauses are ignored here */
4277 {
4281 }
4282 else
4283 {
4284 /* We can treat all clauses alike for an inner join */
4287 }
4289 /* Replace any outer-relation variables with nestloop params */
4291 {
4296 }
4298 /*
4299 * Identify any nestloop parameters that should be supplied by this join
4300 * node, and remove them from root->curOuterParams.
4301 */
4306 joinclauses,
4307 otherclauses,
4308 nestParams,
4309 outer_plan,
4310 inner_plan,
4317 }
4322 {
4346 /*
4347 * MergeJoin can project, so we don't have to demand exact tlists from the
4348 * inputs. However, if we're intending to sort an input's result, it's
4349 * best to request a small tlist so we aren't sorting more data than
4350 * necessary.
4351 */
4358 /* Sort join qual clauses into best execution order */
4359 /* NB: do NOT reorder the mergeclauses */
4362 /* Get the join qual clauses (in plain expression form) */
4363 /* Any pseudoconstant clauses are ignored here */
4365 {
4369 }
4370 else
4371 {
4372 /* We can treat all clauses alike for an inner join */
4375 }
4377 /*
4378 * Remove the mergeclauses from the list of join qual clauses, leaving the
4379 * list of quals that must be checked as qpquals.
4380 */
4384 /*
4385 * Replace any outer-relation variables with nestloop params. There
4386 * should not be any in the mergeclauses.
4387 */
4389 {
4394 }
4396 /*
4397 * Rearrange mergeclauses, if needed, so that the outer variable is always
4398 * on the left; mark the mergeclause restrictinfos with correct
4399 * outer_is_left status.
4400 */
4404 /*
4405 * Create explicit sort nodes for the outer and inner paths if necessary.
4406 */
4408 {
4412 outer_relids);
4417 }
4418 else
4422 {
4426 inner_relids);
4431 }
4432 else
4435 /*
4436 * If specified, add a materialize node to shield the inner plan from the
4437 * need to handle mark/restore.
4438 */
4440 {
4443 /*
4444 * We assume the materialize will not spill to disk, and therefore
4445 * charge just cpu_operator_cost per tuple. (Keep this estimate in
4446 * sync with final_cost_mergejoin.)
4447 */
4452 }
4454 /*
4455 * Compute the opfamily/collation/strategy/nullsfirst arrays needed by the
4456 * executor. The information is in the pathkeys for the two inputs, but
4457 * we need to be careful about the possibility of mergeclauses sharing a
4458 * pathkey, as well as the possibility that the inner pathkeys are not in
4459 * an order matching the mergeclauses.
4460 */
4474 {
4482 /* fetch outer/inner eclass from mergeclause */
4484 {
4487 }
4488 else
4489 {
4492 }
4496 /*
4497 * We must identify the pathkey elements associated with this clause
4498 * by matching the eclasses (which should give a unique match, since
4499 * the pathkey lists should be canonical). In typical cases the merge
4500 * clauses are one-to-one with the pathkeys, but when dealing with
4501 * partially redundant query conditions, things are more complicated.
4502 *
4503 * lop and lip reference the first as-yet-unmatched pathkey elements.
4504 * If they're NULL then all pathkey elements have been matched.
4505 *
4506 * The ordering of the outer pathkeys should match the mergeclauses,
4507 * by construction (see find_mergeclauses_for_outer_pathkeys()). There
4508 * could be more than one mergeclause for the same outer pathkey, but
4509 * no pathkey may be entirely skipped over.
4510 */
4512 {
4513 /* doesn't match the current opathkey, so must match the next */
4521 }
4523 /*
4524 * The inner pathkeys likewise should not have skipped-over keys, but
4525 * it's possible for a mergeclause to reference some earlier inner
4526 * pathkey if we had redundant pathkeys. For example we might have
4527 * mergeclauses like "o.a = i.x AND o.b = i.y AND o.c = i.x". The
4528 * implied inner ordering is then "ORDER BY x, y, x", but the pathkey
4529 * mechanism drops the second sort by x as redundant, and this code
4530 * must cope.
4531 *
4532 * It's also possible for the implied inner-rel ordering to be like
4533 * "ORDER BY x, y, x DESC". We still drop the second instance of x as
4534 * redundant; but this means that the sort ordering of a redundant
4535 * inner pathkey should not be considered significant. So we must
4536 * detect whether this is the first clause matching an inner pathkey.
4537 */
4539 {
4543 {
4544 /* successful first match to this inner pathkey */
4547 }
4548 }
4550 {
4551 /* redundant clause ... must match something before lip */
4555 {
4562 }
4565 }
4567 /*
4568 * The pathkeys should always match each other as to opfamily and
4569 * collation (which affect equality), but if we're considering a
4570 * redundant inner pathkey, its sort ordering might not match. In
4571 * such cases we may ignore the inner pathkey's sort ordering and use
4572 * the outer's. (In effect, we're lying to the executor about the
4573 * sort direction of this inner column, but it does not matter since
4574 * the run-time row comparisons would only reach this column when
4575 * there's equality for the earlier column containing the same eclass.
4576 * There could be only one value in this column for the range of inner
4577 * rows having a given value in the earlier column, so it does not
4578 * matter which way we imagine this column to be ordered.) But a
4579 * non-redundant inner pathkey had better match outer's ordering too.
4580 */
4589 /* OK, save info for executor */
4594 i++;
4595 }
4597 /*
4598 * Note: it is not an error if we have additional pathkey elements (i.e.,
4599 * lop or lip isn't NULL here). The input paths might be better-sorted
4600 * than we need for the current mergejoin.
4601 */
4603 /*
4604 * Now we can build the mergejoin node.
4605 */
4607 joinclauses,
4608 otherclauses,
4609 mergeclauses,
4610 mergefamilies,
4611 mergecollations,
4612 mergestrategies,
4613 mergenullsfirst,
4614 outer_plan,
4615 inner_plan,
4620 /* Costs of sort and material steps are included in path cost already */
4624 }
4629 {
4647 /*
4648 * HashJoin can project, so we don't have to demand exact tlists from the
4649 * inputs. However, it's best to request a small tlist from the inner
4650 * side, so that we aren't storing more data than necessary. Likewise, if
4651 * we anticipate batching, request a small tlist from the outer side so
4652 * that we don't put extra data in the outer batch files.
4653 */
4658 CP_SMALL_TLIST);
4660 /* Sort join qual clauses into best execution order */
4662 /* There's no point in sorting the hash clauses ... */
4664 /* Get the join qual clauses (in plain expression form) */
4665 /* Any pseudoconstant clauses are ignored here */
4667 {
4671 }
4672 else
4673 {
4674 /* We can treat all clauses alike for an inner join */
4677 }
4679 /*
4680 * Remove the hashclauses from the list of join qual clauses, leaving the
4681 * list of quals that must be checked as qpquals.
4682 */
4686 /*
4687 * Replace any outer-relation variables with nestloop params. There
4688 * should not be any in the hashclauses.
4689 */
4691 {
4696 }
4698 /*
4699 * Rearrange hashclauses, if needed, so that the outer variable is always
4700 * on the left.
4701 */
4705 /*
4706 * If there is a single join clause and we can identify the outer variable
4707 * as a simple column reference, supply its identity for possible use in
4708 * skew optimization. (Note: in principle we could do skew optimization
4709 * with multiple join clauses, but we'd have to be able to determine the
4710 * most common combinations of outer values, which we don't currently have
4711 * enough stats for.)
4712 */
4714 {
4723 {
4729 {
4733 }
4734 }
4735 }
4737 /*
4738 * Collect hash related information. The hashed expressions are
4739 * deconstructed into outer/inner expressions, so they can be computed
4740 * separately (inner expressions are used to build the hashtable via Hash,
4741 * outer expressions to perform lookups of tuples from HashJoin's outer
4742 * plan in the hashtable). Also collect operator information necessary to
4743 * build the hashtable.
4744 */
4746 {
4753 }
4755 /*
4756 * Build the hash node and hash join node.
4757 */
4759 inner_hashkeys,
4760 skewTable,
4761 skewColumn,
4762 skewInherit);
4764 /*
4765 * Set Hash node's startup & total costs equal to total cost of input
4766 * plan; this only affects EXPLAIN display not decisions.
4767 */
4771 /*
4772 * If parallel-aware, the executor will also need an estimate of the total
4773 * number of rows expected from all participants so that it can size the
4774 * shared hash table.
4775 */
4777 {
4780 }
4783 joinclauses,
4784 otherclauses,
4785 hashclauses,
4786 hashoperators,
4787 hashcollations,
4788 outer_hashkeys,
4789 outer_plan,
4797 }
4800 /*****************************************************************************
4801 *
4802 * SUPPORTING ROUTINES
4803 *
4804 *****************************************************************************/
4806 /*
4807 * replace_nestloop_params
4808 * Replace outer-relation Vars and PlaceHolderVars in the given expression
4809 * with nestloop Params
4810 *
4811 * All Vars and PlaceHolderVars belonging to the relation(s) identified by
4812 * root->curOuterRels are replaced by Params, and entries are added to
4813 * root->curOuterParams if not already present.
4814 */
4817 {
4818 /* No setup needed for tree walk, so away we go */
4820 }
4824 {
4828 {
4831 /* Upper-level Vars should be long gone at this point */
4833 /* If not to be replaced, we can just return the Var unmodified */
4837 /* Replace the Var with a nestloop Param */
4839 }
4841 {
4844 /* Upper-level PlaceHolderVars should be long gone at this point */
4847 /*
4848 * Check whether we need to replace the PHV. We use bms_overlap as a
4849 * cheap/quick test to see if the PHV might be evaluated in the outer
4850 * rels, and then grab its PlaceHolderInfo to tell for sure.
4851 */
4855 {
4856 /*
4857 * We can't replace the whole PHV, but we might still need to
4858 * replace Vars or PHVs within its expression, in case it ends up
4859 * actually getting evaluated here. (It might get evaluated in
4860 * this plan node, or some child node; in the latter case we don't
4861 * really need to process the expression here, but we haven't got
4862 * enough info to tell if that's the case.) Flat-copy the PHV
4863 * node and then recurse on its expression.
4864 *
4865 * Note that after doing this, we might have different
4866 * representations of the contents of the same PHV in different
4867 * parts of the plan tree. This is OK because equal() will just
4868 * match on phid/phlevelsup, so setrefs.c will still recognize an
4869 * upper-level reference to a lower-level copy of the same PHV.
4870 */
4876 root);
4878 }
4879 /* Replace the PlaceHolderVar with a nestloop Param */
4881 }
4883 replace_nestloop_params_mutator,
4885 }
4887 /*
4888 * fix_indexqual_references
4889 * Adjust indexqual clauses to the form the executor's indexqual
4890 * machinery needs.
4891 *
4892 * We have three tasks here:
4893 * * Select the actual qual clauses out of the input IndexClause list,
4894 * and remove RestrictInfo nodes from the qual clauses.
4895 * * Replace any outer-relation Var or PHV nodes with nestloop Params.
4896 * (XXX eventually, that responsibility should go elsewhere?)
4897 * * Index keys must be represented by Var nodes with varattno set to the
4898 * index's attribute number, not the attribute number in the original rel.
4899 *
4900 * *stripped_indexquals_p receives a list of the actual qual clauses.
4901 *
4902 * *fixed_indexquals_p receives a list of the adjusted quals. This is a copy
4903 * that shares no substructure with the original; this is needed in case there
4904 * are subplans in it (we need two separate copies of the subplan tree, or
4905 * things will go awry).
4906 */
4907 static void
4910 {
4919 {
4925 {
4933 }
4934 }
4938 }
4940 /*
4941 * fix_indexorderby_references
4942 * Adjust indexorderby clauses to the form the executor's index
4943 * machinery needs.
4944 *
4945 * This is a simplified version of fix_indexqual_references. The input is
4946 * bare clauses and a separate indexcol list, instead of IndexClauses.
4947 */
4950 {
4959 {
4965 }
4968 }
4970 /*
4971 * fix_indexqual_clause
4972 * Convert a single indexqual clause to the form needed by the executor.
4973 *
4974 * We replace nestloop params here, and replace the index key variables
4975 * or expressions by index Var nodes.
4976 */
4980 {
4981 /*
4982 * Replace any outer-relation variables with nestloop params.
4983 *
4984 * This also makes a copy of the clause, so it's safe to modify it
4985 * in-place below.
4986 */
4990 {
4993 /* Replace the indexkey expression with an index Var. */
4995 index,
4996 indexcol);
4997 }
4999 {
5004 /* Replace the indexkey expressions with index Vars. */
5007 {
5009 index,
5011 }
5012 }
5014 {
5017 /* Replace the indexkey expression with an index Var. */
5019 index,
5020 indexcol);
5021 }
5023 {
5026 /* Replace the indexkey expression with an index Var. */
5028 index,
5029 indexcol);
5030 }
5031 else
5036 }
5038 /*
5039 * fix_indexqual_operand
5040 * Convert an indexqual expression to a Var referencing the index column.
5041 *
5042 * We represent index keys by Var nodes having varno == INDEX_VAR and varattno
5043 * equal to the index's attribute number (index column position).
5044 *
5045 * Most of the code here is just for sanity cross-checking that the given
5046 * expression actually matches the index column it's claimed to.
5047 */
5050 {
5055 /*
5056 * Remove any binary-compatible relabeling of the indexkey
5057 */
5064 {
5065 /* It's a simple index column */
5069 {
5074 }
5075 else
5077 }
5079 /* It's an index expression, so find and cross-check the expression */
5082 {
5084 {
5088 {
5095 {
5101 }
5102 else
5104 }
5106 }
5107 }
5109 /* Oops... */
5112 }
5114 /*
5115 * get_switched_clauses
5116 * Given a list of merge or hash joinclauses (as RestrictInfo nodes),
5117 * extract the bare clauses, and rearrange the elements within the
5118 * clauses, if needed, so the outer join variable is on the left and
5119 * the inner is on the right. The original clause data structure is not
5120 * touched; a modified list is returned. We do, however, set the transient
5121 * outer_is_left field in each RestrictInfo to show which side was which.
5122 */
5125 {
5130 {
5136 {
5137 /*
5138 * Duplicate just enough of the structure to allow commuting the
5139 * clause without changing the original list. Could use
5140 * copyObject, but a complete deep copy is overkill.
5141 */
5152 /* Commute it --- note this modifies the temp node in-place. */
5156 }
5157 else
5158 {
5162 }
5163 }
5165 }
5167 /*
5168 * order_qual_clauses
5169 * Given a list of qual clauses that will all be evaluated at the same
5170 * plan node, sort the list into the order we want to check the quals
5171 * in at runtime.
5172 *
5173 * When security barrier quals are used in the query, we may have quals with
5174 * different security levels in the list. Quals of lower security_level
5175 * must go before quals of higher security_level, except that we can grant
5176 * exceptions to move up quals that are leakproof. When security level
5177 * doesn't force the decision, we prefer to order clauses by estimated
5178 * execution cost, cheapest first.
5179 *
5180 * Ideally the order should be driven by a combination of execution cost and
5181 * selectivity, but it's not immediately clear how to account for both,
5182 * and given the uncertainty of the estimates the reliability of the decisions
5183 * would be doubtful anyway. So we just order by security level then
5184 * estimated per-tuple cost, being careful not to change the order when
5185 * (as is often the case) the estimates are identical.
5186 *
5187 * Although this will work on either bare clauses or RestrictInfos, it's
5188 * much faster to apply it to RestrictInfos, since it can re-use cost
5189 * information that is cached in RestrictInfos. XXX in the bare-clause
5190 * case, we are also not able to apply security considerations. That is
5191 * all right for the moment, because the bare-clause case doesn't occur
5192 * anywhere that barrier quals could be present, but it would be better to
5193 * get rid of it.
5194 *
5195 * Note: some callers pass lists that contain entries that will later be
5196 * removed; this is the easiest way to let this routine see RestrictInfos
5197 * instead of bare clauses. This is another reason why trying to consider
5198 * selectivity in the ordering would likely do the wrong thing.
5199 */
5202 {
5204 {
5206 Cost cost;
5207 Index security_level;
5215 /* No need to work hard for 0 or 1 clause */
5219 /*
5220 * Collect the items and costs into an array. This is to avoid repeated
5221 * cost_qual_eval work if the inputs aren't RestrictInfos.
5222 */
5226 {
5228 QualCost qcost;
5234 {
5237 /*
5238 * If a clause is leakproof, it doesn't have to be constrained by
5239 * its nominal security level. If it's also reasonably cheap
5240 * (here defined as 10X cpu_operator_cost), pretend it has
5241 * security_level 0, which will allow it to go in front of
5242 * more-expensive quals of lower security levels. Of course, that
5243 * will also force it to go in front of cheaper quals of its own
5244 * security level, which is not so great, but we can alleviate
5245 * that risk by applying the cost limit cutoff.
5246 */
5249 else
5251 }
5252 else
5254 i++;
5255 }
5257 /*
5258 * Sort. We don't use qsort() because it's not guaranteed stable for
5259 * equal keys. The expected number of entries is small enough that a
5260 * simple insertion sort should be good enough.
5261 */
5263 {
5267 /* insert newitem into the already-sorted subarray */
5269 {
5277 }
5279 }
5281 /* Convert back to a list */
5287 }
5289 /*
5290 * Copy cost and size info from a Path node to the Plan node created from it.
5291 * The executor usually won't use this info, but it's needed by EXPLAIN.
5292 * Also copy the parallel-related flags, which the executor *will* use.
5293 */
5294 static void
5296 {
5303 }
5305 /*
5306 * Copy cost and size info from a lower plan node to an inserted node.
5307 * (Most callers alter the info after copying it.)
5308 */
5309 static void
5311 {
5316 /* Assume the inserted node is not parallel-aware. */
5318 /* Assume the inserted node is parallel-safe, if child plan is. */
5320 }
5322 /*
5323 * Some places in this file build Sort nodes that don't have a directly
5324 * corresponding Path node. The cost of the sort is, or should have been,
5325 * included in the cost of the Path node we're working from, but since it's
5326 * not split out, we have to re-figure it using cost_sort(). This is just
5327 * to label the Sort node nicely for EXPLAIN.
5328 *
5329 * limit_tuples is as for cost_sort (in particular, pass -1 if no limit)
5330 */
5331 static void
5333 {
5337 /*
5338 * This function shouldn't have to deal with IncrementalSort plans because
5339 * they are only created from corresponding Path nodes.
5340 */
5348 work_mem,
5349 limit_tuples);
5356 }
5358 /*
5359 * bitmap_subplan_mark_shared
5360 * Set isshared flag in bitmap subplan so that it will be created in
5361 * shared memory.
5362 */
5363 static void
5365 {
5369 {
5372 }
5375 else
5377 }
5379 /*****************************************************************************
5380 *
5381 * PLAN NODE BUILDING ROUTINES
5382 *
5383 * In general, these functions are not passed the original Path and therefore
5384 * leave it to the caller to fill in the cost/width fields from the Path,
5385 * typically by calling copy_generic_path_info(). This convention is
5386 * somewhat historical, but it does support a few places above where we build
5387 * a plan node without having an exactly corresponding Path node. Under no
5388 * circumstances should one of these functions do its own cost calculations,
5389 * as that would be redundant with calculations done while building Paths.
5390 *
5391 *****************************************************************************/
5396 Index scanrelid)
5397 {
5408 }
5413 Index scanrelid,
5415 {
5427 }
5432 Index scanrelid,
5433 Oid indexid,
5439 ScanDirection indexscandir)
5440 {
5458 }
5463 Index scanrelid,
5464 Oid indexid,
5469 ScanDirection indexscandir)
5470 {
5487 }
5491 Oid indexid,
5494 {
5508 }
5515 Index scanrelid)
5516 {
5528 }
5533 Index scanrelid,
5535 {
5547 }
5552 Index scanrelid,
5554 {
5566 }
5571 Index scanrelid,
5573 {
5585 }
5590 Index scanrelid,
5593 {
5606 }
5611 Index scanrelid,
5613 {
5625 }
5630 Index scanrelid,
5632 {
5644 }
5649 Index scanrelid,
5652 {
5665 }
5670 Index scanrelid,
5672 {
5676 /* cost should be inserted by caller */
5685 }
5690 Index scanrelid,
5692 {
5704 }
5706 ForeignScan *
5709 Index scanrelid,
5715 {
5719 /* cost will be filled in by create_foreignscan_plan */
5726 /* these may be overridden by the FDW's PlanDirectModify callback. */
5730 /* fs_server will be filled in by create_foreignscan_plan */
5736 /* fs_relids will be filled in by create_foreignscan_plan */
5738 /* fsSystemCol will be filled in by create_foreignscan_plan */
5742 }
5751 {
5762 /*
5763 * convert SortGroupClause list into arrays of attr indexes and equality
5764 * operators, as wanted by executor
5765 */
5768 {
5780 {
5789 keyno++;
5790 }
5794 }
5798 }
5802 {
5813 }
5817 {
5828 }
5837 JoinType jointype,
5839 {
5853 }
5865 JoinType jointype,
5867 {
5884 }
5889 Oid skewTable,
5890 AttrNumber skewColumn,
5892 {
5907 }
5920 JoinType jointype,
5923 {
5942 }
5944 /*
5945 * make_sort --- basic routine to build a Sort plan node
5946 *
5947 * Caller must have built the sortColIdx, sortOperators, collations, and
5948 * nullsFirst arrays already.
5949 */
5954 {
5972 }
5974 /*
5975 * make_incrementalsort --- basic routine to build an IncrementalSort plan node
5976 *
5977 * Caller must have built the sortColIdx, sortOperators, collations, and
5978 * nullsFirst arrays already.
5979 */
5984 {
6003 }
6005 /*
6006 * prepare_sort_from_pathkeys
6007 * Prepare to sort according to given pathkeys
6008 *
6009 * This is used to set up for Sort, MergeAppend, and Gather Merge nodes. It
6010 * calculates the executor's representation of the sort key information, and
6011 * adjusts the plan targetlist if needed to add resjunk sort columns.
6012 *
6013 * Input parameters:
6014 * 'lefttree' is the plan node which yields input tuples
6015 * 'pathkeys' is the list of pathkeys by which the result is to be sorted
6016 * 'relids' identifies the child relation being sorted, if any
6017 * 'reqColIdx' is NULL or an array of required sort key column numbers
6018 * 'adjust_tlist_in_place' is true if lefttree must be modified in-place
6019 *
6020 * We must convert the pathkey information into arrays of sort key column
6021 * numbers, sort operator OIDs, collation OIDs, and nulls-first flags,
6022 * which is the representation the executor wants. These are returned into
6023 * the output parameters *p_numsortkeys etc.
6024 *
6025 * When looking for matches to an EquivalenceClass's members, we will only
6026 * consider child EC members if they belong to given 'relids'. This protects
6027 * against possible incorrect matches to child expressions that contain no
6028 * Vars.
6029 *
6030 * If reqColIdx isn't NULL then it contains sort key column numbers that
6031 * we should match. This is used when making child plans for a MergeAppend;
6032 * it's an error if we can't match the columns.
6033 *
6034 * If the pathkeys include expressions that aren't simple Vars, we will
6035 * usually need to add resjunk items to the input plan's targetlist to
6036 * compute these expressions, since a Sort or MergeAppend node itself won't
6037 * do any such calculations. If the input plan type isn't one that can do
6038 * projections, this means adding a Result node just to do the projection.
6039 * However, the caller can pass adjust_tlist_in_place = true to force the
6040 * lefttree tlist to be modified in-place regardless of whether the node type
6041 * can project --- we use this for fixing the tlist of MergeAppend itself.
6042 *
6043 * Returns the node which is to be the input to the Sort (either lefttree,
6044 * or a Result stacked atop lefttree).
6045 */
6048 Relids relids,
6056 {
6065 /*
6066 * We will need at most list_length(pathkeys) sort columns; possibly less
6067 */
6077 {
6083 Oid sortop;
6087 {
6088 /*
6089 * If the pathkey's EquivalenceClass is volatile, then it must
6090 * have come from an ORDER BY clause, and we have to match it to
6091 * that same targetlist entry.
6092 */
6099 }
6101 {
6102 /*
6103 * If we are given a sort column number to match, only consider
6104 * the single TLE at that position. It's possible that there is
6105 * no such TLE, in which case fall through and generate a resjunk
6106 * targetentry (we assume this must have happened in the parent
6107 * plan as well). If there is a TLE but it doesn't match the
6108 * pathkey's EC, we do the same, which is probably the wrong thing
6109 * but we'll leave it to caller to complain about the mismatch.
6110 */
6113 {
6116 {
6117 /* found expr at right place in tlist */
6119 }
6120 else
6122 }
6123 }
6124 else
6125 {
6126 /*
6127 * Otherwise, we can sort by any non-constant expression listed in
6128 * the pathkey's EquivalenceClass. For now, we take the first
6129 * tlist item found in the EC. If there's no match, we'll generate
6130 * a resjunk entry using the first EC member that is an expression
6131 * in the input's vars. (The non-const restriction only matters
6132 * if the EC is below_outer_join; but if it isn't, it won't
6133 * contain consts anyway, else we'd have discarded the pathkey as
6134 * redundant.)
6135 *
6136 * XXX if we have a choice, is there any way of figuring out which
6137 * might be cheapest to execute? (For example, int4lt is likely
6138 * much cheaper to execute than numericlt, but both might appear
6139 * in the same equivalence class...) Not clear that we ever will
6140 * have an interesting choice in practice, so it may not matter.
6141 */
6143 {
6147 {
6148 /* found expr already in tlist */
6151 }
6153 }
6154 }
6157 {
6158 /*
6159 * No matching tlist item; look for a computable expression.
6160 */
6166 /*
6167 * Do we need to insert a Result node?
6168 */
6171 {
6172 /* copy needed so we don't modify input's tlist below */
6176 }
6178 /* Don't bother testing is_projection_capable_plan again */
6181 /*
6182 * Add resjunk entry to input's tlist
6183 */
6186 NULL,
6190 }
6192 /*
6193 * Look up the correct sort operator from the PathKey's slightly
6194 * abstracted representation.
6195 */
6197 pk_datatype,
6198 pk_datatype,
6205 /* Add the column to the sort arrays */
6210 numsortkeys++;
6211 }
6213 /* Return results */
6221 }
6223 /*
6224 * make_sort_from_pathkeys
6225 * Create sort plan to sort according to given pathkeys
6226 *
6227 * 'lefttree' is the node which yields input tuples
6228 * 'pathkeys' is the list of pathkeys by which the result is to be sorted
6229 * 'relids' is the set of relations required by prepare_sort_from_pathkeys()
6230 */
6233 {
6240 /* Compute sort column info, and adjust lefttree as needed */
6242 relids,
6243 NULL,
6251 /* Now build the Sort node */
6255 }
6257 /*
6258 * make_incrementalsort_from_pathkeys
6259 * Create sort plan to sort according to given pathkeys
6260 *
6261 * 'lefttree' is the node which yields input tuples
6262 * 'pathkeys' is the list of pathkeys by which the result is to be sorted
6263 * 'relids' is the set of relations required by prepare_sort_from_pathkeys()
6264 * 'nPresortedCols' is the number of presorted columns in input tuples
6265 */
6269 {
6276 /* Compute sort column info, and adjust lefttree as needed */
6278 relids,
6279 NULL,
6287 /* Now build the Sort node */
6291 }
6293 /*
6294 * make_sort_from_sortclauses
6295 * Create sort plan to sort according to given sortclauses
6296 *
6297 * 'sortcls' is a list of SortGroupClauses
6298 * 'lefttree' is the node which yields input tuples
6299 */
6300 Sort *
6302 {
6311 /* Convert list-ish representation to arrays wanted by executor */
6320 {
6328 numsortkeys++;
6329 }
6334 }
6336 /*
6337 * make_sort_from_groupcols
6338 * Create sort plan to sort based on grouping columns
6339 *
6340 * 'groupcls' is the list of SortGroupClauses
6341 * 'grpColIdx' gives the column numbers to use
6342 *
6343 * This might look like it could be merged with make_sort_from_sortclauses,
6344 * but presently we *must* use the grpColIdx[] array to locate sort columns,
6345 * because the child plan's tlist is not marked with ressortgroupref info
6346 * appropriate to the grouping node. So, only the sort ordering info
6347 * is used from the SortGroupClause entries.
6348 */
6353 {
6362 /* Convert list-ish representation to arrays wanted by executor */
6371 {
6382 numsortkeys++;
6383 }
6388 }
6392 {
6402 }
6404 /*
6405 * materialize_finished_plan: stick a Material node atop a completed plan
6406 *
6407 * There are a couple of places where we want to attach a Material node
6408 * after completion of create_plan(), without any MaterialPath path.
6409 * Those places should probably be refactored someday to do this on the
6410 * Path representation, but it's not worth the trouble yet.
6411 */
6412 Plan *
6414 {
6420 /*
6421 * XXX horrid kluge: if there are any initPlans attached to the subplan,
6422 * move them up to the Material node, which is now effectively the top
6423 * plan node in its query level. This prevents failure in
6424 * SS_finalize_plan(), which see for comments. We don't bother adjusting
6425 * the subplan's cost estimate for this.
6426 */
6430 /* Set cost data */
6444 }
6450 {
6469 }
6471 Agg *
6477 {
6482 /* Reduce to long, but 'ware overflow! */
6503 }
6513 {
6538 /* WindowAgg nodes never have a qual clause */
6542 }
6552 {
6567 }
6569 /*
6570 * distinctList is a list of SortGroupClauses, identifying the targetlist items
6571 * that should be considered by the Unique filter. The input path must
6572 * already be sorted accordingly.
6573 */
6576 {
6591 /*
6592 * convert SortGroupClause list into arrays of attr indexes and equality
6593 * operators, as wanted by executor
6594 */
6601 {
6609 keyno++;
6610 }
6618 }
6620 /*
6621 * as above, but use pathkeys to identify the sort columns and semantics
6622 */
6625 {
6639 /*
6640 * Convert pathkeys list into arrays of attr indexes and equality
6641 * operators, as wanted by executor. This has a lot in common with
6642 * prepare_sort_from_pathkeys ... maybe unify sometime?
6643 */
6650 {
6656 Oid eqop;
6659 /* Ignore pathkeys beyond the specified number of columns */
6664 {
6665 /*
6666 * If the pathkey's EquivalenceClass is volatile, then it must
6667 * have come from an ORDER BY clause, and we have to match it to
6668 * that same targetlist entry.
6669 */
6676 }
6677 else
6678 {
6679 /*
6680 * Otherwise, we can use any non-constant expression listed in the
6681 * pathkey's EquivalenceClass. For now, we take the first tlist
6682 * item found in the EC.
6683 */
6685 {
6689 {
6690 /* found expr already in tlist */
6693 }
6695 }
6696 }
6701 /*
6702 * Look up the correct equality operator from the PathKey's slightly
6703 * abstracted representation.
6704 */
6706 pk_datatype,
6707 pk_datatype,
6708 BTEqualStrategyNumber);
6718 keyno++;
6719 }
6727 }
6736 {
6751 }
6753 /*
6754 * distinctList is a list of SortGroupClauses, identifying the targetlist
6755 * items that should be considered by the SetOp filter. The input path must
6756 * already be sorted accordingly.
6757 */
6762 {
6777 /*
6778 * convert SortGroupClause list into arrays of attr indexes and equality
6779 * operators, as wanted by executor
6780 */
6786 {
6794 keyno++;
6795 }
6808 }
6810 /*
6811 * make_lockrows
6812 * Build a LockRows plan node
6813 */
6816 {
6829 }
6831 /*
6832 * make_limit
6833 * Build a Limit plan node
6834 */
6835 Limit *
6839 {
6857 }
6859 /*
6860 * make_result
6861 * Build a Result plan node
6862 */
6867 {
6878 }
6880 /*
6881 * make_project_set
6882 * Build a ProjectSet plan node
6883 */
6887 {
6897 }
6899 /*
6900 * make_modifytable
6901 * Build a ModifyTable plan node
6902 */
6912 {
6930 /* setrefs.c will fill in the targetlist, if needed */
6940 {
6948 }
6949 else
6950 {
6953 /*
6954 * Here we convert the ON CONFLICT UPDATE tlist, if any, to the
6955 * executor's convention of having consecutive resno's. The actual
6956 * target column numbers are saved in node->onConflictCols. (This
6957 * could be done earlier, but there seems no need to.)
6958 */
6964 /*
6965 * If a set of unique index inference elements was provided (an
6966 * INSERT...ON CONFLICT "inference specification"), then infer
6967 * appropriate unique indexes (or throw an error if none are
6968 * available).
6969 */
6974 }
6981 /*
6982 * For each result relation that is a foreign table, allow the FDW to
6983 * construct private plan data, and accumulate it all into a list.
6984 */
6989 {
6995 /*
6996 * If possible, we want to get the FdwRoutine from our RelOptInfo for
6997 * the table. But sometimes we don't have a RelOptInfo and must get
6998 * it the hard way. (In INSERT, the target relation is not scanned,
6999 * so it's not a baserel; and there are also corner cases for
7000 * updatable views where the target rel isn't a baserel.)
7001 */
7004 {
7008 }
7009 else
7010 {
7016 else
7018 }
7020 /*
7021 * Try to modify the foreign table directly if (1) the FDW provides
7022 * callback functions needed for that and (2) there are no local
7023 * structures that need to be run for each modified row: row-level
7024 * triggers on the foreign table, stored generated columns, WITH CHECK
7025 * OPTIONs from parent views.
7026 */
7044 else
7047 i++;
7048 }
7053 }
7055 /*
7056 * is_projection_capable_path
7057 * Check whether a given Path node is able to do projection.
7058 */
7059 bool
7061 {
7062 /* Most plan types can project, so just list the ones that can't */
7064 {
7084 /*
7085 * Append can't project, but if an AppendPath is being used to
7086 * represent a dummy path, what will actually be generated is a
7087 * Result which can project.
7088 */
7092 /*
7093 * Although ProjectSet certainly projects, say "no" because we
7094 * don't want the planner to randomly replace its tlist with
7095 * something else; the SRFs have to stay at top level. This might
7096 * get relaxed later.
7097 */
7101 }
7103 }
7105 /*
7106 * is_projection_capable_plan
7107 * Check whether a given Plan node is able to do projection.
7108 */
7109 bool
7111 {
7112 /* Most plan types can project, so just list the ones that can't */
7114 {
7134 /*
7135 * Although ProjectSet certainly projects, say "no" because we
7136 * don't want the planner to randomly replace its tlist with
7137 * something else; the SRFs have to stay at top level. This might
7138 * get relaxed later.
7139 */
7143 }
7145 }