paths.h File Reference
#include "nodes/pathnodes.h"
Include dependency graph for paths.h:
This graph shows which files directly or indirectly include this file:
Go to the source code of this file.
Typedefs | |
| typedef void(* | set_rel_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte) |
| typedef void(* | set_join_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra) |
| typedef RelOptInfo *(* | join_search_hook_type) (PlannerInfo *root, int levels_needed, List *initial_rels) |
| typedef bool(* | ec_matches_callback_type) (PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg) |
Enumerations | |
| enum | PathKeysComparison { PATHKEYS_EQUAL , PATHKEYS_BETTER1 , PATHKEYS_BETTER2 , PATHKEYS_DIFFERENT } |
Typedef Documentation
◆ ec_matches_callback_type
| typedef bool(* ec_matches_callback_type) (PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg) |
◆ join_search_hook_type
| typedef RelOptInfo *(* join_search_hook_type) (PlannerInfo *root, int levels_needed, List *initial_rels) |
◆ set_join_pathlist_hook_type
| typedef void(* set_join_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra) |
◆ set_rel_pathlist_hook_type
| typedef void(* set_rel_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte) |
Enumeration Type Documentation
◆ PathKeysComparison
| enum PathKeysComparison |
| Enumerator | |
|---|---|
| PATHKEYS_EQUAL | |
| PATHKEYS_BETTER1 | |
| PATHKEYS_BETTER2 | |
| PATHKEYS_DIFFERENT | |
Definition at line 210 of file paths.h.
211{
216} PathKeysComparison;
Function Documentation
◆ add_child_join_rel_equivalences()
| void add_child_join_rel_equivalences | ( | PlannerInfo * | root, |
| int | nappinfos, | ||
| AppendRelInfo ** | appinfos, | ||
| RelOptInfo * | parent_joinrel, | ||
| RelOptInfo * | child_joinrel | ||
| ) |
Definition at line 2941 of file equivclass.c.
2945{
2948 Bitmapset *matching_ecs;
2949 MemoryContext oldcontext;
2951
2953
2954 /* We need consider only ECs that mention the parent joinrel */
2956
2957 /*
2958 * If we're being called during GEQO join planning, we still have to
2959 * create any new EC members in the main planner context, to avoid having
2960 * a corrupt EC data structure after the GEQO context is reset. This is
2961 * problematic since we'll leak memory across repeated GEQO cycles. For
2962 * now, though, bloat is better than crash. If it becomes a real issue
2963 * we'll have to do something to avoid generating duplicate EC members.
2964 */
2966
2967 i = -1;
2969 {
2971
2972 /*
2973 * If this EC contains a volatile expression, then generating child
2974 * EMs would be downright dangerous, so skip it. We rely on a
2975 * volatile EC having only one EM.
2976 */
2978 continue;
2979
2980 /* Sanity check on get_eclass_indexes_for_relids result */
2982
2984 {
2985 if (cur_em->em_is_const)
2986 continue; /* ignore consts here */
2987
2988 /* Child members should not exist in ec_members */
2989 Assert(!cur_em->em_is_child);
2990
2991 /*
2992 * We may ignore expressions that reference a single baserel,
2993 * because add_child_rel_equivalences should have handled them.
2994 */
2996 continue;
2997
2998 /* Does this member reference child's topmost parent rel? */
3000 {
3001 /* Yes, generate transformed child version */
3002 Expr *child_expr;
3003 Relids new_relids;
3004
3006 {
3007 /* Simple single-level transformation */
3008 child_expr = (Expr *)
3010 (Node *) cur_em->em_expr,
3011 nappinfos, appinfos);
3012 }
3013 else
3014 {
3015 /* Must do multi-level transformation */
3017 child_expr = (Expr *)
3019 (Node *) cur_em->em_expr,
3020 child_joinrel,
3021 child_joinrel->top_parent);
3022 }
3023
3024 /*
3025 * Transform em_relids to match. Note we do *not* do
3026 * pull_varnos(child_expr) here, as for example the
3027 * transformation might have substituted a constant, but we
3028 * don't want the child member to be marked as constant.
3029 */
3030 new_relids = bms_difference(cur_em->em_relids,
3031 top_parent_relids);
3032 new_relids = bms_add_members(new_relids, child_relids);
3033
3034 /*
3035 * Add new child member to the EquivalenceClass. Because this
3036 * is a RELOPT_OTHER_JOINREL which has multiple component
3037 * relids, there is no ideal place to store these members in
3038 * the class. Ordinarily, child members are stored in the
3039 * ec_childmembers[] array element corresponding to their
3040 * relid, however, here we have multiple component relids, so
3041 * there's no single ec_childmembers[] array element to store
3042 * this member. So that we still correctly find this member
3043 * in loops iterating over an EquivalenceMemberIterator, we
3044 * opt to store the member in the ec_childmembers array in
3045 * only the first component relid slot of the array. This
3046 * allows the member to be found, providing callers of
3047 * setup_eclass_member_iterator() specify all the component
3048 * relids for the RELOPT_OTHER_JOINREL, which they do. If we
3049 * opted to store the member in each ec_childmembers[] element
3050 * for all the component relids, then that would just result
3051 * in eclass_member_iterator_next() finding the member
3052 * multiple times, which is a waste of effort.
3053 */
3055 cur_ec,
3056 -1,
3057 child_expr,
3058 new_relids,
3059 cur_em->em_jdomain,
3060 cur_em,
3061 cur_em->em_datatype,
3063 }
3064 }
3065 }
3066
3067 MemoryContextSwitchTo(oldcontext);
3068}
Node * adjust_appendrel_attrs(PlannerInfo *root, Node *node, int nappinfos, AppendRelInfo **appinfos)
Definition: appendinfo.c:200
Node * adjust_appendrel_attrs_multilevel(PlannerInfo *root, Node *node, RelOptInfo *childrel, RelOptInfo *parentrel)
Definition: appendinfo.c:592
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:346
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:916
static EquivalenceMember * add_child_eq_member(PlannerInfo *root, EquivalenceClass *ec, int ec_index, Expr *expr, Relids relids, JoinDomain *jdomain, EquivalenceMember *parent_em, Oid datatype, Index child_relid)
Definition: equivclass.c:661
static Bitmapset * get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
Definition: equivclass.c:3613
Assert(PointerIsAligned(start, uint64))
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
Definition: bitmapset.h:50
Definition: pathnodes.h:1556
Definition: pathnodes.h:1617
Definition: primnodes.h:189
Definition: memnodes.h:118
Definition: nodes.h:135
References add_child_eq_member(), adjust_appendrel_attrs(), adjust_appendrel_attrs_multilevel(), Assert(), bms_add_members(), bms_difference(), bms_membership(), BMS_MULTIPLE, bms_next_member(), bms_overlap(), EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, foreach_node, get_eclass_indexes_for_relids(), i, IS_JOIN_REL, list_nth(), MemoryContextSwitchTo(), RelOptInfo::relids, RELOPT_JOINREL, RELOPT_OTHER_JOINREL, RelOptInfo::reloptkind, root, and RelOptInfo::top_parent_relids.
Referenced by build_child_join_rel().
◆ add_child_rel_equivalences()
| void add_child_rel_equivalences | ( | PlannerInfo * | root, |
| AppendRelInfo * | appinfo, | ||
| RelOptInfo * | parent_rel, | ||
| RelOptInfo * | child_rel | ||
| ) |
Definition at line 2833 of file equivclass.c.
2837{
2841
2842 /*
2843 * EC merging should be complete already, so we can use the parent rel's
2844 * eclass_indexes to avoid searching all of root->eq_classes.
2845 */
2848
2849 i = -1;
2851 {
2853
2854 /*
2855 * If this EC contains a volatile expression, then generating child
2856 * EMs would be downright dangerous, so skip it. We rely on a
2857 * volatile EC having only one EM.
2858 */
2860 continue;
2861
2862 /* Sanity check eclass_indexes only contain ECs for parent_rel */
2864
2866 {
2867 if (cur_em->em_is_const)
2868 continue; /* ignore consts here */
2869
2870 /* Child members should not exist in ec_members */
2871 Assert(!cur_em->em_is_child);
2872
2873 /*
2874 * Consider only members that reference and can be computed at
2875 * child's topmost parent rel. In particular we want to exclude
2876 * parent-rel Vars that have nonempty varnullingrels. Translating
2877 * those might fail, if the transformed expression wouldn't be a
2878 * simple Var; and in any case it wouldn't produce a member that
2879 * has any use in creating plans for the child rel.
2880 */
2882 !bms_is_empty(cur_em->em_relids))
2883 {
2884 /* OK, generate transformed child version */
2885 Expr *child_expr;
2886 Relids new_relids;
2887
2889 {
2890 /* Simple single-level transformation */
2891 child_expr = (Expr *)
2893 (Node *) cur_em->em_expr,
2894 1, &appinfo);
2895 }
2896 else
2897 {
2898 /* Must do multi-level transformation */
2899 child_expr = (Expr *)
2901 (Node *) cur_em->em_expr,
2902 child_rel,
2903 child_rel->top_parent);
2904 }
2905
2906 /*
2907 * Transform em_relids to match. Note we do *not* do
2908 * pull_varnos(child_expr) here, as for example the
2909 * transformation might have substituted a constant, but we
2910 * don't want the child member to be marked as constant.
2911 */
2912 new_relids = bms_difference(cur_em->em_relids,
2913 top_parent_relids);
2914 new_relids = bms_add_members(new_relids, child_relids);
2915
2917 cur_ec,
2918 i,
2919 child_expr,
2920 new_relids,
2921 cur_em->em_jdomain,
2922 cur_em,
2923 cur_em->em_datatype,
2924 child_rel->relid);
2925 }
2926 }
2927 }
2928}
References add_child_eq_member(), adjust_appendrel_attrs(), adjust_appendrel_attrs_multilevel(), Assert(), bms_add_members(), bms_difference(), bms_is_empty, bms_is_subset(), bms_next_member(), EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, RelOptInfo::eclass_indexes, foreach_node, i, IS_SIMPLE_REL, list_nth(), RelOptInfo::relid, RelOptInfo::relids, RELOPT_BASEREL, RelOptInfo::reloptkind, root, and RelOptInfo::top_parent_relids.
Referenced by set_append_rel_size().
◆ add_outer_joins_to_relids()
| Relids add_outer_joins_to_relids | ( | PlannerInfo * | root, |
| Relids | input_relids, | ||
| SpecialJoinInfo * | sjinfo, | ||
| List ** | pushed_down_joins | ||
| ) |
Definition at line 800 of file joinrels.c.
803{
804 /* Nothing to do if this isn't an outer join with an assigned relid. */
806 return input_relids;
807
808 /*
809 * If it's not a left join, we have no rules that would permit executing
810 * it in non-syntactic order, so just form the syntactic relid set. (This
811 * is just a quick-exit test; we'd come to the same conclusion anyway,
812 * since its commute_below_l and commute_above_l sets must be empty.)
813 */
816
817 /*
818 * We cannot add the OJ relid if this join has been pushed into the RHS of
819 * a syntactically-lower left join per OJ identity 3. (If it has, then we
820 * cannot claim that its outputs represent the final state of its RHS.)
821 * There will not be any other OJs that can be added either, so we're
822 * done.
823 */
825 return input_relids;
826
827 /* OK to add OJ's own relid */
829
830 /*
831 * Contrariwise, if we are now forming the final result of such a commuted
832 * pair of OJs, it's time to add the relid(s) of the pushed-down join(s).
833 * We can skip this if this join was never a candidate to be pushed up.
834 */
836 {
838 ListCell *lc;
839
840 /*
841 * The current join could complete the nulling of more than one
842 * pushed-down join, so we have to examine all the SpecialJoinInfos.
843 * Because join_info_list was built in bottom-up order, it's
844 * sufficient to traverse it once: an ojrelid we add in one loop
845 * iteration would not have affected decisions of earlier iterations.
846 */
848 {
850
851 if (othersj == sjinfo ||
853 continue; /* definitely not interesting */
854
856 continue;
857
858 /* Add it if not already present but conditions now satisfied */
863 {
865 /* report such pushed down outer joins, if asked */
866 if (pushed_down_joins != NULL)
867 *pushed_down_joins = lappend(*pushed_down_joins, othersj);
868
869 /*
870 * We must also check any joins that othersj potentially
871 * commutes with. They likewise must appear later in
872 * join_info_list than othersj itself, so we can visit them
873 * later in this loop.
874 */
875 commute_above_rels = bms_add_members(commute_above_rels,
876 othersj->commute_above_l);
877 }
878 }
879 }
880
881 return input_relids;
882}
Definition: pathnodes.h:3113
Definition: pg_list.h:46
References bms_add_member(), bms_add_members(), bms_copy(), bms_is_member(), bms_is_subset(), SpecialJoinInfo::commute_above_l, SpecialJoinInfo::commute_below_l, JOIN_LEFT, SpecialJoinInfo::jointype, lappend(), lfirst, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, SpecialJoinInfo::ojrelid, and root.
Referenced by generate_join_implied_equalities(), and make_join_rel().
◆ add_paths_to_append_rel()
| void add_paths_to_append_rel | ( | PlannerInfo * | root, |
| RelOptInfo * | rel, | ||
| List * | live_childrels | ||
| ) |
Definition at line 1404 of file allpaths.c.
1406{
1408 bool subpaths_valid = true;
1410 bool startup_subpaths_valid = true;
1414 bool partial_subpaths_valid = true;
1415 bool pa_subpaths_valid;
1418 ListCell *l;
1419 double partial_rows = -1;
1420
1421 /* If appropriate, consider parallel append */
1423
1424 /*
1425 * For every non-dummy child, remember the cheapest path. Also, identify
1426 * all pathkeys (orderings) and parameterizations (required_outer sets)
1427 * available for the non-dummy member relations.
1428 */
1429 foreach(l, live_childrels)
1430 {
1432 ListCell *lcp;
1433 Path *cheapest_partial_path = NULL;
1434
1435 /*
1436 * If child has an unparameterized cheapest-total path, add that to
1437 * the unparameterized Append path we are constructing for the parent.
1438 * If not, there's no workable unparameterized path.
1439 *
1440 * With partitionwise aggregates, the child rel's pathlist may be
1441 * empty, so don't assume that a path exists here.
1442 */
1444 childrel->cheapest_total_path->param_info == NULL)
1446 &subpaths, NULL);
1447 else
1448 subpaths_valid = false;
1449
1450 /*
1451 * When the planner is considering cheap startup plans, we'll also
1452 * collect all the cheapest_startup_paths (if set) and build an
1453 * AppendPath containing those as subpaths.
1454 */
1456 {
1457 Path *cheapest_path;
1458
1459 /*
1460 * With an indication of how many tuples the query should provide,
1461 * the optimizer tries to choose the path optimal for that
1462 * specific number of tuples.
1463 */
1465 cheapest_path =
1466 get_cheapest_fractional_path(childrel,
1467 root->tuple_fraction);
1468 else
1469 cheapest_path = childrel->cheapest_startup_path;
1470
1471 /* cheapest_startup_path must not be a parameterized path. */
1472 Assert(cheapest_path->param_info == NULL);
1473 accumulate_append_subpath(cheapest_path,
1474 &startup_subpaths,
1475 NULL);
1476 }
1477 else
1478 startup_subpaths_valid = false;
1479
1480
1481 /* Same idea, but for a partial plan. */
1483 {
1485 accumulate_append_subpath(cheapest_partial_path,
1486 &partial_subpaths, NULL);
1487 }
1488 else
1489 partial_subpaths_valid = false;
1490
1491 /*
1492 * Same idea, but for a parallel append mixing partial and non-partial
1493 * paths.
1494 */
1495 if (pa_subpaths_valid)
1496 {
1497 Path *nppath = NULL;
1498
1499 nppath =
1501
1502 if (cheapest_partial_path == NULL && nppath == NULL)
1503 {
1504 /* Neither a partial nor a parallel-safe path? Forget it. */
1505 pa_subpaths_valid = false;
1506 }
1507 else if (nppath == NULL ||
1508 (cheapest_partial_path != NULL &&
1510 {
1511 /* Partial path is cheaper or the only option. */
1512 Assert(cheapest_partial_path != NULL);
1513 accumulate_append_subpath(cheapest_partial_path,
1514 &pa_partial_subpaths,
1515 &pa_nonpartial_subpaths);
1516 }
1517 else
1518 {
1519 /*
1520 * Either we've got only a non-partial path, or we think that
1521 * a single backend can execute the best non-partial path
1522 * faster than all the parallel backends working together can
1523 * execute the best partial path.
1524 *
1525 * It might make sense to be more aggressive here. Even if
1526 * the best non-partial path is more expensive than the best
1527 * partial path, it could still be better to choose the
1528 * non-partial path if there are several such paths that can
1529 * be given to different workers. For now, we don't try to
1530 * figure that out.
1531 */
1532 accumulate_append_subpath(nppath,
1533 &pa_nonpartial_subpaths,
1534 NULL);
1535 }
1536 }
1537
1538 /*
1539 * Collect lists of all the available path orderings and
1540 * parameterizations for all the children. We use these as a
1541 * heuristic to indicate which sort orderings and parameterizations we
1542 * should build Append and MergeAppend paths for.
1543 */
1545 {
1549
1550 /* Unsorted paths don't contribute to pathkey list */
1552 {
1553 ListCell *lpk;
1554 bool found = false;
1555
1556 /* Have we already seen this ordering? */
1557 foreach(lpk, all_child_pathkeys)
1558 {
1560
1562 childkeys) == PATHKEYS_EQUAL)
1563 {
1564 found = true;
1565 break;
1566 }
1567 }
1568 if (!found)
1569 {
1570 /* No, so add it to all_child_pathkeys */
1571 all_child_pathkeys = lappend(all_child_pathkeys,
1572 childkeys);
1573 }
1574 }
1575
1576 /* Unparameterized paths don't contribute to param-set list */
1577 if (childouter)
1578 {
1579 ListCell *lco;
1580 bool found = false;
1581
1582 /* Have we already seen this param set? */
1583 foreach(lco, all_child_outers)
1584 {
1586
1588 {
1589 found = true;
1590 break;
1591 }
1592 }
1593 if (!found)
1594 {
1595 /* No, so add it to all_child_outers */
1596 all_child_outers = lappend(all_child_outers,
1597 childouter);
1598 }
1599 }
1600 }
1601 }
1602
1603 /*
1604 * If we found unparameterized paths for all children, build an unordered,
1605 * unparameterized Append path for the rel. (Note: this is correct even
1606 * if we have zero or one live subpath due to constraint exclusion.)
1607 */
1608 if (subpaths_valid)
1611 -1));
1612
1613 /* build an AppendPath for the cheap startup paths, if valid */
1614 if (startup_subpaths_valid)
1617
1618 /*
1619 * Consider an append of unordered, unparameterized partial paths. Make
1620 * it parallel-aware if possible.
1621 */
1623 {
1624 AppendPath *appendpath;
1625 ListCell *lc;
1626 int parallel_workers = 0;
1627
1628 /* Find the highest number of workers requested for any subpath. */
1629 foreach(lc, partial_subpaths)
1630 {
1632
1634 }
1635 Assert(parallel_workers > 0);
1636
1637 /*
1638 * If the use of parallel append is permitted, always request at least
1639 * log2(# of children) workers. We assume it can be useful to have
1640 * extra workers in this case because they will be spread out across
1641 * the children. The precise formula is just a guess, but we don't
1642 * want to end up with a radically different answer for a table with N
1643 * partitions vs. an unpartitioned table with the same data, so the
1644 * use of some kind of log-scaling here seems to make some sense.
1645 */
1647 {
1648 parallel_workers = Max(parallel_workers,
1650 parallel_workers = Min(parallel_workers,
1652 }
1653 Assert(parallel_workers > 0);
1654
1655 /* Generate a partial append path. */
1657 NIL, NULL, parallel_workers,
1658 enable_parallel_append,
1659 -1);
1660
1661 /*
1662 * Make sure any subsequent partial paths use the same row count
1663 * estimate.
1664 */
1666
1667 /* Add the path. */
1669 }
1670
1671 /*
1672 * Consider a parallel-aware append using a mix of partial and non-partial
1673 * paths. (This only makes sense if there's at least one child which has
1674 * a non-partial path that is substantially cheaper than any partial path;
1675 * otherwise, we should use the append path added in the previous step.)
1676 */
1678 {
1679 AppendPath *appendpath;
1680 ListCell *lc;
1681 int parallel_workers = 0;
1682
1683 /*
1684 * Find the highest number of workers requested for any partial
1685 * subpath.
1686 */
1687 foreach(lc, pa_partial_subpaths)
1688 {
1690
1692 }
1693
1694 /*
1695 * Same formula here as above. It's even more important in this
1696 * instance because the non-partial paths won't contribute anything to
1697 * the planned number of parallel workers.
1698 */
1699 parallel_workers = Max(parallel_workers,
1701 parallel_workers = Min(parallel_workers,
1703 Assert(parallel_workers > 0);
1704
1706 pa_partial_subpaths,
1708 partial_rows);
1710 }
1711
1712 /*
1713 * Also build unparameterized ordered append paths based on the collected
1714 * list of child pathkeys.
1715 */
1716 if (subpaths_valid)
1718 all_child_pathkeys);
1719
1720 /*
1721 * Build Append paths for each parameterization seen among the child rels.
1722 * (This may look pretty expensive, but in most cases of practical
1723 * interest, the child rels will expose mostly the same parameterizations,
1724 * so that not that many cases actually get considered here.)
1725 *
1726 * The Append node itself cannot enforce quals, so all qual checking must
1727 * be done in the child paths. This means that to have a parameterized
1728 * Append path, we must have the exact same parameterization for each
1729 * child path; otherwise some children might be failing to check the
1730 * moved-down quals. To make them match up, we can try to increase the
1731 * parameterization of lesser-parameterized paths.
1732 */
1733 foreach(l, all_child_outers)
1734 {
1736 ListCell *lcr;
1737
1738 /* Select the child paths for an Append with this parameterization */
1739 subpaths = NIL;
1740 subpaths_valid = true;
1741 foreach(lcr, live_childrels)
1742 {
1745
1747 {
1748 /* failed to make a suitable path for this child */
1749 subpaths_valid = false;
1750 break;
1751 }
1752
1754 childrel,
1755 required_outer);
1757 {
1758 /* failed to make a suitable path for this child */
1759 subpaths_valid = false;
1760 break;
1761 }
1763 }
1764
1765 if (subpaths_valid)
1769 -1));
1770 }
1771
1772 /*
1773 * When there is only a single child relation, the Append path can inherit
1774 * any ordering available for the child rel's path, so that it's useful to
1775 * consider ordered partial paths. Above we only considered the cheapest
1776 * partial path for each child, but let's also make paths using any
1777 * partial paths that have pathkeys.
1778 */
1780 {
1782
1783 /* skip the cheapest partial path, since we already used that above */
1785 {
1787 AppendPath *appendpath;
1788
1789 /* skip paths with no pathkeys. */
1791 continue;
1792
1794 NIL, NULL,
1796 partial_rows);
1798 }
1799 }
1800}
static Path * get_cheapest_parameterized_child_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer)
Definition: allpaths.c:2138
static void generate_orderedappend_paths(PlannerInfo *root, RelOptInfo *rel, List *live_childrels, List *all_child_pathkeys)
Definition: allpaths.c:1832
static void accumulate_append_subpath(Path *path, List **subpaths, List **special_subpaths)
Definition: allpaths.c:2226
PathKeysComparison compare_pathkeys(List *keys1, List *keys2)
Definition: pathkeys.c:304
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:699
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:795
AppendPath * create_append_path(PlannerInfo *root, RelOptInfo *rel, List *subpaths, List *partial_subpaths, List *pathkeys, Relids required_outer, int parallel_workers, bool parallel_aware, double rows)
Definition: pathnode.c:1301
Path * get_cheapest_fractional_path(RelOptInfo *rel, double tuple_fraction)
Definition: planner.c:6601
Definition: pathnodes.h:2178
Definition: pg_list.h:54
Definition: pathnodes.h:1867
Definition: pathnodes.h:916
References accumulate_append_subpath(), add_partial_path(), add_path(), Assert(), bms_equal(), RelOptInfo::cheapest_startup_path, RelOptInfo::cheapest_total_path, compare_pathkeys(), RelOptInfo::consider_parallel, RelOptInfo::consider_startup, create_append_path(), enable_parallel_append, for_each_from, generate_orderedappend_paths(), get_cheapest_fractional_path(), get_cheapest_parallel_safe_total_inner(), get_cheapest_parameterized_child_path(), lappend(), lfirst, linitial, list_length(), list_make1, Max, max_parallel_workers_per_gather, Min, NIL, Path::parallel_workers, RelOptInfo::partial_pathlist, AppendPath::path, PATH_REQ_OUTER, Path::pathkeys, PATHKEYS_EQUAL, RelOptInfo::pathlist, pg_leftmost_one_pos32(), root, Path::rows, subpath(), and Path::total_cost.
Referenced by apply_scanjoin_target_to_paths(), create_partitionwise_grouping_paths(), generate_partitionwise_join_paths(), and set_append_rel_pathlist().
◆ add_paths_to_joinrel()
| void add_paths_to_joinrel | ( | PlannerInfo * | root, |
| RelOptInfo * | joinrel, | ||
| RelOptInfo * | outerrel, | ||
| RelOptInfo * | innerrel, | ||
| JoinType | jointype, | ||
| SpecialJoinInfo * | sjinfo, | ||
| List * | restrictlist | ||
| ) |
Definition at line 124 of file joinpath.c.
131{
132 JoinType save_jointype = jointype;
133 JoinPathExtraData extra;
134 bool mergejoin_allowed = true;
135 ListCell *lc;
136 Relids joinrelids;
137
138 /*
139 * PlannerInfo doesn't contain the SpecialJoinInfos created for joins
140 * between child relations, even if there is a SpecialJoinInfo node for
141 * the join between the topmost parents. So, while calculating Relids set
142 * representing the restriction, consider relids of topmost parent of
143 * partitions.
144 */
146 joinrelids = joinrel->top_parent_relids;
147 else
148 joinrelids = joinrel->relids;
149
150 extra.restrictlist = restrictlist;
152 extra.sjinfo = sjinfo;
153 extra.param_source_rels = NULL;
154
155 /*
156 * See if the inner relation is provably unique for this outer rel.
157 *
158 * We have some special cases: for JOIN_SEMI, it doesn't matter since the
159 * executor can make the equivalent optimization anyway. It also doesn't
160 * help enable use of Memoize, since a semijoin with a provably unique
161 * inner side should have been reduced to an inner join in that case.
162 * Therefore, we need not expend planner cycles on proofs. (For
163 * JOIN_ANTI, although it doesn't help the executor for the same reason,
164 * it can benefit Memoize paths.) For JOIN_UNIQUE_INNER, we must be
165 * considering a semijoin whose inner side is not provably unique (else
166 * reduce_unique_semijoins would've simplified it), so there's no point in
167 * calling innerrel_is_unique. However, if the LHS covers all of the
168 * semijoin's min_lefthand, then it's appropriate to set inner_unique
169 * because the unique relation produced by create_unique_paths will be
170 * unique relative to the LHS. (If we have an LHS that's only part of the
171 * min_lefthand, that is *not* true.) For JOIN_UNIQUE_OUTER, pass
172 * JOIN_INNER to avoid letting that value escape this module.
173 */
174 switch (jointype)
175 {
178 break;
181 outerrel->relids);
182 break;
185 joinrel->relids,
186 outerrel->relids,
187 innerrel,
188 JOIN_INNER,
189 restrictlist,
190 false);
191 break;
192 default:
194 joinrel->relids,
195 outerrel->relids,
196 innerrel,
197 jointype,
198 restrictlist,
199 false);
200 break;
201 }
202
203 /*
204 * If the outer or inner relation has been unique-ified, handle as a plain
205 * inner join.
206 */
208 jointype = JOIN_INNER;
209
210 /*
211 * Find potential mergejoin clauses. We can skip this if we are not
212 * interested in doing a mergejoin. However, mergejoin may be our only
213 * way of implementing a full outer join, so override enable_mergejoin if
214 * it's a full join.
215 */
218 joinrel,
219 outerrel,
220 innerrel,
221 restrictlist,
222 jointype,
223 &mergejoin_allowed);
224
225 /*
226 * If it's SEMI, ANTI, or inner_unique join, compute correction factors
227 * for cost estimation. These will be the same for all paths.
228 */
231 jointype, sjinfo, restrictlist,
232 &extra.semifactors);
233
234 /*
235 * Decide whether it's sensible to generate parameterized paths for this
236 * joinrel, and if so, which relations such paths should require. There
237 * is usually no need to create a parameterized result path unless there
238 * is a join order restriction that prevents joining one of our input rels
239 * directly to the parameter source rel instead of joining to the other
240 * input rel. (But see allow_star_schema_join().) This restriction
241 * reduces the number of parameterized paths we have to deal with at
242 * higher join levels, without compromising the quality of the resulting
243 * plan. We express the restriction as a Relids set that must overlap the
244 * parameterization of any proposed join path. Note: param_source_rels
245 * should contain only baserels, not OJ relids, so starting from
246 * all_baserels not all_query_rels is correct.
247 */
249 {
251
252 /*
253 * SJ is relevant to this join if we have some part of its RHS
254 * (possibly not all of it), and haven't yet joined to its LHS. (This
255 * test is pretty simplistic, but should be sufficient considering the
256 * join has already been proven legal.) If the SJ is relevant, it
257 * presents constraints for joining to anything not in its RHS.
258 */
263 sjinfo2->min_righthand));
264
265 /* full joins constrain both sides symmetrically */
271 sjinfo2->min_lefthand));
272 }
273
274 /*
275 * However, when a LATERAL subquery is involved, there will simply not be
276 * any paths for the joinrel that aren't parameterized by whatever the
277 * subquery is parameterized by, unless its parameterization is resolved
278 * within the joinrel. So we might as well allow additional dependencies
279 * on whatever residual lateral dependencies the joinrel will have.
280 */
282 joinrel->lateral_relids);
283
284 /*
285 * 1. Consider mergejoin paths where both relations must be explicitly
286 * sorted. Skip this if we can't mergejoin.
287 */
288 if (mergejoin_allowed)
290 jointype, &extra);
291
292 /*
293 * 2. Consider paths where the outer relation need not be explicitly
294 * sorted. This includes both nestloops and mergejoins where the outer
295 * path is already ordered. Again, skip this if we can't mergejoin.
296 * (That's okay because we know that nestloop can't handle
297 * right/right-anti/right-semi/full joins at all, so it wouldn't work in
298 * the prohibited cases either.)
299 */
300 if (mergejoin_allowed)
302 jointype, &extra);
303
304#ifdef NOT_USED
305
306 /*
307 * 3. Consider paths where the inner relation need not be explicitly
308 * sorted. This includes mergejoins only (nestloops were already built in
309 * match_unsorted_outer).
310 *
311 * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
312 * significant difference between the inner and outer side of a mergejoin,
313 * so match_unsorted_inner creates no paths that aren't equivalent to
314 * those made by match_unsorted_outer when add_paths_to_joinrel() is
315 * invoked with the two rels given in the other order.
316 */
317 if (mergejoin_allowed)
318 match_unsorted_inner(root, joinrel, outerrel, innerrel,
319 jointype, &extra);
320#endif
321
322 /*
323 * 4. Consider paths where both outer and inner relations must be hashed
324 * before being joined. As above, disregard enable_hashjoin for full
325 * joins, because there may be no other alternative.
326 */
329 jointype, &extra);
330
331 /*
332 * 5. If inner and outer relations are foreign tables (or joins) belonging
333 * to the same server and assigned to the same user to check access
334 * permissions as, give the FDW a chance to push down joins.
335 */
336 if (joinrel->fdwroutine &&
337 joinrel->fdwroutine->GetForeignJoinPaths)
338 joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
339 outerrel, innerrel,
340 save_jointype, &extra);
341
342 /*
343 * 6. Finally, give extensions a chance to manipulate the path list. They
344 * could add new paths (such as CustomPaths) by calling add_path(), or
345 * add_partial_path() if parallel aware. They could also delete or modify
346 * paths added by the core code.
347 */
350 save_jointype, &extra);
351}
bool innerrel_is_unique(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
Definition: analyzejoins.c:1305
void compute_semi_anti_join_factors(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist, SemiAntiJoinFactors *semifactors)
Definition: costsize.c:5139
static List * select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
Definition: joinpath.c:2354
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1368
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:2127
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1792
Definition: pathnodes.h:3495
References bms_add_members(), bms_difference(), bms_is_subset(), bms_join(), bms_overlap(), compute_semi_anti_join_factors(), enable_hashjoin, enable_mergejoin, hash_inner_and_outer(), JoinPathExtraData::inner_unique, innerrel_is_unique(), JOIN_ANTI, JOIN_FULL, JOIN_INNER, JOIN_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, SpecialJoinInfo::jointype, RelOptInfo::lateral_relids, lfirst, match_unsorted_outer(), JoinPathExtraData::mergeclause_list, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, JoinPathExtraData::param_source_rels, RelOptInfo::relids, RELOPT_OTHER_JOINREL, RelOptInfo::reloptkind, JoinPathExtraData::restrictlist, root, select_mergejoin_clauses(), JoinPathExtraData::semifactors, set_join_pathlist_hook, JoinPathExtraData::sjinfo, sort_inner_and_outer(), and RelOptInfo::top_parent_relids.
Referenced by populate_joinrel_with_paths().
◆ add_setop_child_rel_equivalences()
| void add_setop_child_rel_equivalences | ( | PlannerInfo * | root, |
| RelOptInfo * | child_rel, | ||
| List * | child_tlist, | ||
| List * | setop_pathkeys | ||
| ) |
Definition at line 3084 of file equivclass.c.
3086{
3087 ListCell *lc;
3089
3090 foreach(lc, child_tlist)
3091 {
3093 EquivalenceMember *parent_em;
3094 PathKey *pk;
3095
3096 if (tle->resjunk)
3097 continue;
3098
3099 if (lc2 == NULL)
3101
3103 parent_em = linitial(pk->pk_eclass->ec_members);
3104
3105 /*
3106 * We can safely pass the parent member as the first member in the
3107 * ec_members list as this is added first in generate_union_paths,
3108 * likewise, the JoinDomain can be that of the initial member of the
3109 * Pathkey's EquivalenceClass. We pass -1 for ec_index since we
3110 * maintain the eclass_indexes for the child_rel after the loop.
3111 */
3113 pk->pk_eclass,
3114 -1,
3115 tle->expr,
3116 child_rel->relids,
3117 parent_em->em_jdomain,
3118 parent_em,
3120 child_rel->relid);
3121
3122 lc2 = lnext(setop_pathkeys, lc2);
3123 }
3124
3125 /*
3126 * transformSetOperationStmt() ensures that the targetlist never contains
3127 * any resjunk columns, so all eclasses that exist in 'root' must have
3128 * received a new member in the loop above. Add them to the child_rel's
3129 * eclass_indexes.
3130 */
3133}
Bitmapset * bms_add_range(Bitmapset *a, int lower, int upper)
Definition: bitmapset.c:1018
Definition: pathnodes.h:1709
Definition: primnodes.h:2236
References add_child_eq_member(), bms_add_range(), RelOptInfo::eclass_indexes, elog, EquivalenceMember::em_jdomain, ERROR, TargetEntry::expr, exprType(), lfirst_node, linitial, list_head(), list_length(), lnext(), RelOptInfo::relid, RelOptInfo::relids, and root.
Referenced by build_setop_child_paths().
◆ append_pathkeys()
Definition at line 107 of file pathkeys.c.
108{
109 ListCell *lc;
110
112
114 {
116
118 target = lappend(target, pk);
119 }
120 return target;
121}
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:159
References Assert(), lappend(), lfirst_node, NIL, pathkey_is_redundant(), and source.
Referenced by adjust_group_pathkeys_for_groupagg(), and make_pathkeys_for_window().
◆ build_expression_pathkey()
| List * build_expression_pathkey | ( | PlannerInfo * | root, |
| Expr * | expr, | ||
| Oid | opno, | ||
| Relids | rel, | ||
| bool | create_it | ||
| ) |
Definition at line 1000 of file pathkeys.c.
1005{
1006 List *pathkeys;
1007 Oid opfamily,
1008 opcintype;
1009 CompareType cmptype;
1010 PathKey *cpathkey;
1011
1012 /* Find the operator in pg_amop --- failure shouldn't happen */
1014 &opfamily, &opcintype, &cmptype))
1016 opno);
1017
1019 expr,
1020 opfamily,
1021 opcintype,
1023 (cmptype == COMPARE_GT),
1024 (cmptype == COMPARE_GT),
1025 0,
1026 rel,
1027 create_it);
1028
1029 if (cpathkey)
1030 pathkeys = list_make1(cpathkey);
1031 else
1032 pathkeys = NIL;
1033
1034 return pathkeys;
1035}
bool get_ordering_op_properties(Oid opno, Oid *opfamily, Oid *opcintype, CompareType *cmptype)
Definition: lsyscache.c:266
static PathKey * make_pathkey_from_sortinfo(PlannerInfo *root, Expr *expr, Oid opfamily, Oid opcintype, Oid collation, bool reverse_sort, bool nulls_first, Index sortref, Relids rel, bool create_it)
Definition: pathkeys.c:198
References COMPARE_GT, elog, ERROR, exprCollation(), get_ordering_op_properties(), list_make1, make_pathkey_from_sortinfo(), NIL, and root.
Referenced by set_function_pathlist().
◆ build_index_pathkeys()
| List * build_index_pathkeys | ( | PlannerInfo * | root, |
| IndexOptInfo * | index, | ||
| ScanDirection | scandir | ||
| ) |
Definition at line 740 of file pathkeys.c.
743{
745 ListCell *lc;
747
750
751 i = 0;
753 {
755 Expr *indexkey;
756 bool reverse_sort;
757 bool nulls_first;
758 PathKey *cpathkey;
759
760 /*
761 * INCLUDE columns are stored in index unordered, so they don't
762 * support ordered index scan.
763 */
765 break;
766
767 /* We assume we don't need to make a copy of the tlist item */
768 indexkey = indextle->expr;
769
771 {
774 }
775 else
776 {
779 }
780
781 /*
782 * OK, try to make a canonical pathkey for this sort key.
783 */
785 indexkey,
789 reverse_sort,
790 nulls_first,
791 0,
792 index->rel->relids,
793 false);
794
795 if (cpathkey)
796 {
797 /*
798 * We found the sort key in an EquivalenceClass, so it's relevant
799 * for this query. Add it to list, unless it's redundant.
800 */
802 retval = lappend(retval, cpathkey);
803 }
804 else
805 {
806 /*
807 * Boolean index keys might be redundant even if they do not
808 * appear in an EquivalenceClass, because of our special treatment
809 * of boolean equality conditions --- see the comment for
810 * indexcol_is_bool_constant_for_query(). If that applies, we can
811 * continue to examine lower-order index columns. Otherwise, the
812 * sort key is not an interesting sort order for this query, so we
813 * should stop considering index columns; any lower-order sort
814 * keys won't be useful either.
815 */
817 break;
818 }
819
820 i++;
821 }
822
823 return retval;
824}
bool indexcol_is_bool_constant_for_query(PlannerInfo *root, IndexOptInfo *index, int indexcol)
Definition: indxpath.c:4304
References TargetEntry::expr, i, indexcol_is_bool_constant_for_query(), lappend(), lfirst, make_pathkey_from_sortinfo(), NIL, pathkey_is_redundant(), root, and ScanDirectionIsBackward.
Referenced by build_index_paths().
◆ build_join_pathkeys()
| List * build_join_pathkeys | ( | PlannerInfo * | root, |
| RelOptInfo * | joinrel, | ||
| JoinType | jointype, | ||
| List * | outer_pathkeys | ||
| ) |
Definition at line 1295 of file pathkeys.c.
1299{
1300 /* RIGHT_SEMI should not come here */
1302
1304 jointype == JOIN_RIGHT ||
1305 jointype == JOIN_RIGHT_ANTI)
1307
1308 /*
1309 * This used to be quite a complex bit of code, but now that all pathkey
1310 * sublists start out life canonicalized, we don't have to do a darn thing
1311 * here!
1312 *
1313 * We do, however, need to truncate the pathkeys list, since it may
1314 * contain pathkeys that were useful for forming this joinrel but are
1315 * uninteresting to higher levels.
1316 */
1318}
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:2200
References Assert(), JOIN_FULL, JOIN_RIGHT, JOIN_RIGHT_ANTI, JOIN_RIGHT_SEMI, NIL, root, and truncate_useless_pathkeys().
Referenced by consider_parallel_mergejoin(), consider_parallel_nestloop(), match_unsorted_outer(), and sort_inner_and_outer().
◆ build_partition_pathkeys()
| List * build_partition_pathkeys | ( | PlannerInfo * | root, |
| RelOptInfo * | partrel, | ||
| ScanDirection | scandir, | ||
| bool * | partialkeys | ||
| ) |
Definition at line 919 of file pathkeys.c.
921{
923 PartitionScheme partscheme = partrel->part_scheme;
925
926 Assert(partscheme != NULL);
928 /* For now, we can only cope with baserels */
930
932 {
933 PathKey *cpathkey;
935
936 /*
937 * Try to make a canonical pathkey for this partkey.
938 *
939 * We assume the PartitionDesc lists any NULL partition last, so we
940 * treat the scan like a NULLS LAST index: we have nulls_first for
941 * backwards scan only.
942 */
944 keyCol,
948 ScanDirectionIsBackward(scandir),
949 ScanDirectionIsBackward(scandir),
950 0,
951 partrel->relids,
952 false);
953
954
955 if (cpathkey)
956 {
957 /*
958 * We found the sort key in an EquivalenceClass, so it's relevant
959 * for this query. Add it to list, unless it's redundant.
960 */
962 retval = lappend(retval, cpathkey);
963 }
964 else
965 {
966 /*
967 * Boolean partition keys might be redundant even if they do not
968 * appear in an EquivalenceClass, because of our special treatment
969 * of boolean equality conditions --- see the comment for
970 * partkey_is_bool_constant_for_query(). If that applies, we can
971 * continue to examine lower-order partition keys. Otherwise, the
972 * sort key is not an interesting sort order for this query, so we
973 * should stop considering partition columns; any lower-order sort
974 * keys won't be useful either.
975 */
977 {
978 *partialkeys = true;
979 return retval;
980 }
981 }
982 }
983
984 *partialkeys = false;
985 return retval;
986}
bool partitions_are_ordered(PartitionBoundInfo boundinfo, Bitmapset *live_parts)
Definition: partbounds.c:2853
static bool partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:844
Definition: pathnodes.h:629
References Assert(), i, IS_SIMPLE_REL, lappend(), linitial, RelOptInfo::live_parts, make_pathkey_from_sortinfo(), NIL, PartitionSchemeData::partcollation, partitions_are_ordered(), partkey_is_bool_constant_for_query(), PartitionSchemeData::partnatts, PartitionSchemeData::partopcintype, PartitionSchemeData::partopfamily, pathkey_is_redundant(), RelOptInfo::relids, root, and ScanDirectionIsBackward.
Referenced by generate_orderedappend_paths().
◆ canonicalize_ec_expression()
Definition at line 545 of file equivclass.c.
546{
548
549 /*
550 * For a polymorphic-input-type opclass, just keep the same exposed type.
551 * RECORD opclasses work like polymorphic-type ones for this purpose.
552 */
553 if (IsPolymorphicType(req_type) || req_type == RECORDOID)
554 req_type = expr_type;
555
556 /*
557 * No work if the expression exposes the right type/collation already.
558 */
559 if (expr_type != req_type ||
561 {
562 /*
563 * If we have to change the type of the expression, set typmod to -1,
564 * since the new type may not have the same typmod interpretation.
565 * When we only have to change collation, preserve the exposed typmod.
566 */
567 int32 req_typmod;
568
569 if (expr_type != req_type)
570 req_typmod = -1;
571 else
573
574 /*
575 * Use applyRelabelType so that we preserve const-flatness. This is
576 * important since eval_const_expressions has already been applied.
577 */
579 req_type, req_typmod, req_collation,
581 }
582
583 return expr;
584}
Node * applyRelabelType(Node *arg, Oid rtype, int32 rtypmod, Oid rcollid, CoercionForm rformat, int rlocation, bool overwrite_ok)
Definition: nodeFuncs.c:636
References applyRelabelType(), COERCE_IMPLICIT_CAST, exprCollation(), exprType(), and exprTypmod().
Referenced by convert_subquery_pathkeys(), get_eclass_for_sort_expr(), and process_equivalence().
◆ check_index_predicates()
| void check_index_predicates | ( | PlannerInfo * | root, |
| RelOptInfo * | rel | ||
| ) |
Definition at line 3942 of file indxpath.c.
3943{
3944 List *clauselist;
3945 bool have_partial;
3946 bool is_target_rel;
3947 Relids otherrels;
3948 ListCell *lc;
3949
3950 /* Indexes are available only on base or "other" member relations. */
3952
3953 /*
3954 * Initialize the indrestrictinfo lists to be identical to
3955 * baserestrictinfo, and check whether there are any partial indexes. If
3956 * not, this is all we need to do.
3957 */
3958 have_partial = false;
3960 {
3962
3965 have_partial = true;
3966 }
3967 if (!have_partial)
3968 return;
3969
3970 /*
3971 * Construct a list of clauses that we can assume true for the purpose of
3972 * proving the index(es) usable. Restriction clauses for the rel are
3973 * always usable, and so are any join clauses that are "movable to" this
3974 * rel. Also, we can consider any EC-derivable join clauses (which must
3975 * be "movable to" this rel, by definition).
3976 */
3978
3979 /* Scan the rel's join clauses */
3981 {
3983
3984 /* Check if clause can be moved to this rel */
3986 continue;
3987
3988 clauselist = lappend(clauselist, rinfo);
3989 }
3990
3991 /*
3992 * Add on any equivalence-derivable join clauses. Computing the correct
3993 * relid sets for generate_join_implied_equalities is slightly tricky
3994 * because the rel could be a child rel rather than a true baserel, and in
3995 * that case we must subtract its parents' relid(s) from all_query_rels.
3996 * Additionally, we mustn't consider clauses that are only computable
3997 * after outer joins that can null the rel.
3998 */
4002 else
4005
4007 clauselist =
4008 list_concat(clauselist,
4011 otherrels),
4012 otherrels,
4013 rel,
4014 NULL));
4015
4016 /*
4017 * Normally we remove quals that are implied by a partial index's
4018 * predicate from indrestrictinfo, indicating that they need not be
4019 * checked explicitly by an indexscan plan using this index. However, if
4020 * the rel is a target relation of UPDATE/DELETE/MERGE/SELECT FOR UPDATE,
4021 * we cannot remove such quals from the plan, because they need to be in
4022 * the plan so that they will be properly rechecked by EvalPlanQual
4023 * testing. Some day we might want to remove such quals from the main
4024 * plan anyway and pass them through to EvalPlanQual via a side channel;
4025 * but for now, we just don't remove implied quals at all for target
4026 * relations.
4027 */
4030
4031 /*
4032 * Now try to prove each index predicate true, and compute the
4033 * indrestrictinfo lists for partial indexes. Note that we compute the
4034 * indrestrictinfo list even for non-predOK indexes; this might seem
4035 * wasteful, but we may be able to use such indexes in OR clauses, cf
4036 * generate_bitmap_or_paths().
4037 */
4039 {
4041 ListCell *lcr;
4042
4044 continue; /* ignore non-partial indexes here */
4045
4048 false);
4049
4050 /* If rel is an update target, leave indrestrictinfo as set above */
4051 if (is_target_rel)
4052 continue;
4053
4054 /*
4055 * If index is !amoptionalkey, also leave indrestrictinfo as set
4056 * above. Otherwise we risk removing all quals for the first index
4057 * key and then not being able to generate an indexscan at all. It
4058 * would be better to be more selective, but we've not yet identified
4059 * which if any of the quals match the first index key.
4060 */
4062 continue;
4063
4064 /* Else compute indrestrictinfo as the non-implied quals */
4067 {
4069
4070 /* predicate_implied_by() assumes first arg is immutable */
4075 }
4076 }
4077}
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:1160
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo)
Definition: equivclass.c:1550
bool predicate_implied_by(List *predicate_list, List *clause_list, bool weak)
Definition: predtest.c:152
PlanRowMark * get_plan_rowmark(List *rowmarks, Index rtindex)
Definition: preptlist.c:526
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:1631
bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
Definition: restrictinfo.c:575
Definition: pathnodes.h:1251
Definition: pathnodes.h:2786
References Assert(), RelOptInfo::baserestrictinfo, bms_del_members(), bms_difference(), bms_is_empty, bms_is_member(), bms_union(), RestrictInfo::clause, contain_mutable_functions(), find_childrel_parents(), generate_join_implied_equalities(), get_plan_rowmark(), RelOptInfo::indexlist, IS_SIMPLE_REL, join_clause_is_movable_to(), RelOptInfo::joininfo, lappend(), lfirst, list_concat(), list_copy(), list_make1, NIL, RelOptInfo::nulling_relids, predicate_implied_by(), RelOptInfo::relid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, and root.
Referenced by set_plain_rel_size(), and set_tablesample_rel_size().
◆ compare_pathkeys()
| PathKeysComparison compare_pathkeys | ( | List * | keys1, |
| List * | keys2 | ||
| ) |
Definition at line 304 of file pathkeys.c.
305{
306 ListCell *key1,
307 *key2;
308
309 /*
310 * Fall out quickly if we are passed two identical lists. This mostly
311 * catches the case where both are NIL, but that's common enough to
312 * warrant the test.
313 */
314 if (keys1 == keys2)
316
317 forboth(key1, keys1, key2, keys2)
318 {
321
322 if (pathkey1 != pathkey2)
324 }
325
326 /*
327 * If we reached the end of only one list, the other is longer and
328 * therefore not a subset.
329 */
330 if (key1 != NULL)
332 if (key2 != NULL)
335}
References forboth, lfirst, PATHKEYS_BETTER1, PATHKEYS_BETTER2, PATHKEYS_DIFFERENT, and PATHKEYS_EQUAL.
Referenced by add_partial_path(), add_partial_path_precheck(), add_path(), add_path_precheck(), add_paths_to_append_rel(), adjust_group_pathkeys_for_groupagg(), get_useful_group_keys_orderings(), get_useful_pathkeys_for_distinct(), pathkeys_contained_in(), and set_cheapest().
◆ compute_parallel_worker()
| int compute_parallel_worker | ( | RelOptInfo * | rel, |
| double | heap_pages, | ||
| double | index_pages, | ||
| int | max_workers | ||
| ) |
Definition at line 4702 of file allpaths.c.
4704{
4705 int parallel_workers = 0;
4706
4707 /*
4708 * If the user has set the parallel_workers reloption, use that; otherwise
4709 * select a default number of workers.
4710 */
4712 parallel_workers = rel->rel_parallel_workers;
4713 else
4714 {
4715 /*
4716 * If the number of pages being scanned is insufficient to justify a
4717 * parallel scan, just return zero ... unless it's an inheritance
4718 * child. In that case, we want to generate a parallel path here
4719 * anyway. It might not be worthwhile just for this relation, but
4720 * when combined with all of its inheritance siblings it may well pay
4721 * off.
4722 */
4724 ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
4725 (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
4726 return 0;
4727
4728 if (heap_pages >= 0)
4729 {
4730 int heap_parallel_threshold;
4731 int heap_parallel_workers = 1;
4732
4733 /*
4734 * Select the number of workers based on the log of the size of
4735 * the relation. This probably needs to be a good deal more
4736 * sophisticated, but we need something here for now. Note that
4737 * the upper limit of the min_parallel_table_scan_size GUC is
4738 * chosen to prevent overflow here.
4739 */
4742 {
4743 heap_parallel_workers++;
4744 heap_parallel_threshold *= 3;
4745 if (heap_parallel_threshold > INT_MAX / 3)
4746 break; /* avoid overflow */
4747 }
4748
4749 parallel_workers = heap_parallel_workers;
4750 }
4751
4752 if (index_pages >= 0)
4753 {
4754 int index_parallel_workers = 1;
4755 int index_parallel_threshold;
4756
4757 /* same calculation as for heap_pages above */
4760 {
4761 index_parallel_workers++;
4762 index_parallel_threshold *= 3;
4763 if (index_parallel_threshold > INT_MAX / 3)
4764 break; /* avoid overflow */
4765 }
4766
4767 if (parallel_workers > 0)
4768 parallel_workers = Min(parallel_workers, index_parallel_workers);
4769 else
4770 parallel_workers = index_parallel_workers;
4771 }
4772 }
4773
4774 /* In no case use more than caller supplied maximum number of workers */
4775 parallel_workers = Min(parallel_workers, max_workers);
4776
4777 return parallel_workers;
4778}
References Max, Min, min_parallel_index_scan_size, min_parallel_table_scan_size, RelOptInfo::rel_parallel_workers, RELOPT_BASEREL, and RelOptInfo::reloptkind.
Referenced by cost_index(), create_partial_bitmap_paths(), create_plain_partial_paths(), create_tidscan_paths(), and plan_create_index_workers().
◆ convert_subquery_pathkeys()
| List * convert_subquery_pathkeys | ( | PlannerInfo * | root, |
| RelOptInfo * | rel, | ||
| List * | subquery_pathkeys, | ||
| List * | subquery_tlist | ||
| ) |
Definition at line 1054 of file pathkeys.c.
1057{
1059 int retvallen = 0;
1062
1064 {
1066 EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
1067 PathKey *best_pathkey = NULL;
1068
1070 {
1071 /*
1072 * If the sub_pathkey's EquivalenceClass is volatile, then it must
1073 * have come from an ORDER BY clause, and we have to match it to
1074 * that same targetlist entry.
1075 */
1076 TargetEntry *tle;
1077 Var *outer_var;
1078
1082 Assert(tle);
1083 /* Is TLE actually available to the outer query? */
1084 outer_var = find_var_for_subquery_tle(rel, tle);
1085 if (outer_var)
1086 {
1087 /* We can represent this sub_pathkey */
1088 EquivalenceMember *sub_member;
1089 EquivalenceClass *outer_ec;
1090
1093
1094 /*
1095 * Note: it might look funny to be setting sortref = 0 for a
1096 * reference to a volatile sub_eclass. However, the
1097 * expression is *not* volatile in the outer query: it's just
1098 * a Var referencing whatever the subquery emitted. (IOW, the
1099 * outer query isn't going to re-execute the volatile
1100 * expression itself.) So this is okay.
1101 */
1102 outer_ec =
1104 (Expr *) outer_var,
1105 sub_eclass->ec_opfamilies,
1106 sub_member->em_datatype,
1107 sub_eclass->ec_collation,
1108 0,
1109 rel->relids,
1110 false);
1111
1112 /*
1113 * If we don't find a matching EC, sub-pathkey isn't
1114 * interesting to the outer query
1115 */
1116 if (outer_ec)
1117 best_pathkey =
1119 outer_ec,
1120 sub_pathkey->pk_opfamily,
1121 sub_pathkey->pk_cmptype,
1122 sub_pathkey->pk_nulls_first);
1123 }
1124 }
1125 else
1126 {
1127 /*
1128 * Otherwise, the sub_pathkey's EquivalenceClass could contain
1129 * multiple elements (representing knowledge that multiple items
1130 * are effectively equal). Each element might match none, one, or
1131 * more of the output columns that are visible to the outer query.
1132 * This means we may have multiple possible representations of the
1133 * sub_pathkey in the context of the outer query. Ideally we
1134 * would generate them all and put them all into an EC of the
1135 * outer query, thereby propagating equality knowledge up to the
1136 * outer query. Right now we cannot do so, because the outer
1137 * query's EquivalenceClasses are already frozen when this is
1138 * called. Instead we prefer the one that has the highest "score"
1139 * (number of EC peers, plus one if it matches the outer
1140 * query_pathkeys). This is the most likely to be useful in the
1141 * outer query.
1142 */
1143 int best_score = -1;
1145
1146 /* Ignore children here */
1148 {
1153 ListCell *k;
1154
1155 /* Child members should not exist in ec_members */
1157
1158 foreach(k, subquery_tlist)
1159 {
1161 Var *outer_var;
1162 Expr *tle_expr;
1163 EquivalenceClass *outer_ec;
1164 PathKey *outer_pk;
1165 int score;
1166
1167 /* Is TLE actually available to the outer query? */
1168 outer_var = find_var_for_subquery_tle(rel, tle);
1169 if (!outer_var)
1170 continue;
1171
1172 /*
1173 * The targetlist entry is considered to match if it
1174 * matches after sort-key canonicalization. That is
1175 * needed since the sub_expr has been through the same
1176 * process.
1177 */
1179 sub_expr_type,
1180 sub_expr_coll);
1182 continue;
1183
1184 /* See if we have a matching EC for the TLE */
1186 (Expr *) outer_var,
1187 sub_eclass->ec_opfamilies,
1188 sub_expr_type,
1189 sub_expr_coll,
1190 0,
1191 rel->relids,
1192 false);
1193
1194 /*
1195 * If we don't find a matching EC, this sub-pathkey isn't
1196 * interesting to the outer query
1197 */
1198 if (!outer_ec)
1199 continue;
1200
1202 outer_ec,
1203 sub_pathkey->pk_opfamily,
1204 sub_pathkey->pk_cmptype,
1205 sub_pathkey->pk_nulls_first);
1206 /* score = # of equivalence peers */
1208 /* +1 if it matches the proper query_pathkeys item */
1209 if (retvallen < outer_query_keys &&
1211 score++;
1212 if (score > best_score)
1213 {
1214 best_pathkey = outer_pk;
1215 best_score = score;
1216 }
1217 }
1218 }
1219 }
1220
1221 /*
1222 * If we couldn't find a representation of this sub_pathkey, we're
1223 * done (we can't use the ones to its right, either).
1224 */
1225 if (!best_pathkey)
1226 break;
1227
1228 /*
1229 * Eliminate redundant ordering info; could happen if outer query
1230 * equivalences subquery keys...
1231 */
1233 {
1234 retval = lappend(retval, best_pathkey);
1235 retvallen++;
1236 }
1237 }
1238
1239 return retval;
1240}
EquivalenceClass * get_eclass_for_sort_expr(PlannerInfo *root, Expr *expr, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
Definition: equivclass.c:736
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:545
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, CompareType cmptype, bool nulls_first)
Definition: pathkeys.c:56
static Var * find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
Definition: pathkeys.c:1252
Definition: primnodes.h:262
TargetEntry * get_sortgroupref_tle(Index sortref, List *targetList)
Definition: tlist.c:345
References Assert(), canonicalize_ec_expression(), EquivalenceClass::ec_collation, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_sortref, elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, equal(), ERROR, TargetEntry::expr, find_var_for_subquery_tle(), get_eclass_for_sort_expr(), get_sortgroupref_tle(), i, j, lappend(), lfirst, linitial, list_length(), list_nth(), make_canonical_pathkey(), NIL, pathkey_is_redundant(), PathKey::pk_cmptype, PathKey::pk_nulls_first, PathKey::pk_opfamily, RelOptInfo::relids, and root.
Referenced by build_setop_child_paths(), set_cte_pathlist(), and set_subquery_pathlist().
◆ create_index_paths()
| void create_index_paths | ( | PlannerInfo * | root, |
| RelOptInfo * | rel | ||
| ) |
Definition at line 240 of file indxpath.c.
241{
242 List *indexpaths;
243 List *bitindexpaths;
244 List *bitjoinpaths;
245 List *joinorclauses;
246 IndexClauseSet rclauseset;
247 IndexClauseSet jclauseset;
248 IndexClauseSet eclauseset;
249 ListCell *lc;
250
251 /* Skip the whole mess if no indexes */
253 return;
254
255 /* Bitmap paths are collected and then dealt with at the end */
256 bitindexpaths = bitjoinpaths = joinorclauses = NIL;
257
258 /* Examine each index in turn */
260 {
262
263 /* Protect limited-size array in IndexClauseSets */
265
266 /*
267 * Ignore partial indexes that do not match the query.
268 * (generate_bitmap_or_paths() might be able to do something with
269 * them, but that's of no concern here.)
270 */
272 continue;
273
274 /*
275 * Identify the restriction clauses that can match the index.
276 */
279
280 /*
281 * Build index paths from the restriction clauses. These will be
282 * non-parameterized paths. Plain paths go directly to add_path(),
283 * bitmap paths are added to bitindexpaths to be handled below.
284 */
286 &bitindexpaths);
287
288 /*
289 * Identify the join clauses that can match the index. For the moment
290 * we keep them separate from the restriction clauses. Note that this
291 * step finds only "loose" join clauses that have not been merged into
292 * EquivalenceClasses. Also, collect join OR clauses for later.
293 */
296 &jclauseset, &joinorclauses);
297
298 /*
299 * Look for EquivalenceClasses that can generate joinclauses matching
300 * the index.
301 */
304 &eclauseset);
305
306 /*
307 * If we found any plain or eclass join clauses, build parameterized
308 * index paths using them.
309 */
312 &rclauseset,
313 &jclauseset,
314 &eclauseset,
315 &bitjoinpaths);
316 }
317
318 /*
319 * Generate BitmapOrPaths for any suitable OR-clauses present in the
320 * restriction list. Add these to bitindexpaths.
321 */
324 bitindexpaths = list_concat(bitindexpaths, indexpaths);
325
326 /*
327 * Likewise, generate BitmapOrPaths for any suitable OR-clauses present in
328 * the joinclause list. Add these to bitjoinpaths.
329 */
331 joinorclauses, rel->baserestrictinfo);
332 bitjoinpaths = list_concat(bitjoinpaths, indexpaths);
333
334 /*
335 * If we found anything usable, generate a BitmapHeapPath for the most
336 * promising combination of restriction bitmap index paths. Note there
337 * will be only one such path no matter how many indexes exist. This
338 * should be sufficient since there's basically only one figure of merit
339 * (total cost) for such a path.
340 */
342 {
343 Path *bitmapqual;
344 BitmapHeapPath *bpath;
345
348 rel->lateral_relids, 1.0, 0);
350
351 /* create a partial bitmap heap path */
354 }
355
356 /*
357 * Likewise, if we found anything usable, generate BitmapHeapPaths for the
358 * most promising combinations of join bitmap index paths. Our strategy
359 * is to generate one such path for each distinct parameterization seen
360 * among the available bitmap index paths. This may look pretty
361 * expensive, but usually there won't be very many distinct
362 * parameterizations. (This logic is quite similar to that in
363 * consider_index_join_clauses, but we're working with whole paths not
364 * individual clauses.)
365 */
367 {
368 List *all_path_outers;
369
370 /* Identify each distinct parameterization seen in bitjoinpaths */
371 all_path_outers = NIL;
372 foreach(lc, bitjoinpaths)
373 {
376
377 all_path_outers = list_append_unique(all_path_outers,
378 required_outer);
379 }
380
381 /* Now, for each distinct parameterization set ... */
382 foreach(lc, all_path_outers)
383 {
385 List *this_path_set;
386 Path *bitmapqual;
387 Relids required_outer;
388 double loop_count;
389 BitmapHeapPath *bpath;
390 ListCell *lcp;
391
392 /* Identify all the bitmap join paths needing no more than that */
393 this_path_set = NIL;
394 foreach(lcp, bitjoinpaths)
395 {
397
399 this_path_set = lappend(this_path_set, path);
400 }
401
402 /*
403 * Add in restriction bitmap paths, since they can be used
404 * together with any join paths.
405 */
406 this_path_set = list_concat(this_path_set, bitindexpaths);
407
408 /* Select best AND combination for this parameterization */
410
411 /* And push that path into the mix */
412 required_outer = PATH_REQ_OUTER(bitmapqual);
415 required_outer, loop_count, 0);
417 }
418 }
419}
void create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual)
Definition: allpaths.c:4666
static Path * choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
Definition: indxpath.c:1785
static void match_join_clauses_to_index(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauseset, List **joinorclauses)
Definition: indxpath.c:2482
static void match_eclass_clauses_to_index(PlannerInfo *root, IndexOptInfo *index, IndexClauseSet *clauseset)
Definition: indxpath.c:2516
static void get_index_paths(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauses, List **bitindexpaths)
Definition: indxpath.c:716
static double get_loop_count(PlannerInfo *root, Index cur_relid, Relids outer_relids)
Definition: indxpath.c:2327
static void consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *rclauseset, IndexClauseSet *jclauseset, IndexClauseSet *eclauseset, List **bitindexpaths)
Definition: indxpath.c:437
static void match_restriction_clauses_to_index(PlannerInfo *root, IndexOptInfo *index, IndexClauseSet *clauseset)
Definition: indxpath.c:2466
static List * generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel, List *clauses, List *other_clauses)
Definition: indxpath.c:1629
BitmapHeapPath * create_bitmap_heap_path(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual, Relids required_outer, double loop_count, int parallel_degree)
Definition: pathnode.c:1098
Definition: pathnodes.h:2031
Definition: indxpath.c:55
References add_path(), Assert(), RelOptInfo::baserestrictinfo, bms_is_subset(), choose_bitmap_and(), consider_index_join_clauses(), RelOptInfo::consider_parallel, create_bitmap_heap_path(), create_partial_bitmap_paths(), generate_bitmap_or_paths(), get_index_paths(), get_loop_count(), INDEX_MAX_KEYS, RelOptInfo::indexlist, lappend(), RelOptInfo::lateral_relids, lfirst, list_append_unique(), list_concat(), match_eclass_clauses_to_index(), match_join_clauses_to_index(), match_restriction_clauses_to_index(), MemSet, NIL, IndexClauseSet::nonempty, PATH_REQ_OUTER, RelOptInfo::relid, and root.
Referenced by set_plain_rel_pathlist().
◆ create_partial_bitmap_paths()
| void create_partial_bitmap_paths | ( | PlannerInfo * | root, |
| RelOptInfo * | rel, | ||
| Path * | bitmapqual | ||
| ) |
Definition at line 4666 of file allpaths.c.
4668{
4669 int parallel_workers;
4670 double pages_fetched;
4671
4672 /* Compute heap pages for bitmap heap scan */
4674 NULL, NULL);
4675
4676 parallel_workers = compute_parallel_worker(rel, pages_fetched, -1,
4678
4679 if (parallel_workers <= 0)
4680 return;
4681
4683 bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
4684}
int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
Definition: allpaths.c:4702
double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, double loop_count, Cost *cost_p, double *tuples_p)
Definition: costsize.c:6539
References add_partial_path(), compute_bitmap_pages(), compute_parallel_worker(), create_bitmap_heap_path(), RelOptInfo::lateral_relids, max_parallel_workers_per_gather, and root.
Referenced by create_index_paths().
◆ create_tidscan_paths()
| bool create_tidscan_paths | ( | PlannerInfo * | root, |
| RelOptInfo * | rel | ||
| ) |
Definition at line 497 of file tidpath.c.
498{
499 List *tidquals;
500 List *tidrangequals;
501 bool isCurrentOf;
502
503 /*
504 * If any suitable quals exist in the rel's baserestrict list, generate a
505 * plain (unparameterized) TidPath with them.
506 *
507 * We skip this when enable_tidscan = false, except when the qual is
508 * CurrentOfExpr. In that case, a TID scan is the only correct path.
509 */
511 &isCurrentOf);
512
514 {
515 /*
516 * This path uses no join clauses, but it could still have required
517 * parameterization due to LATERAL refs in its tlist.
518 */
520
522 required_outer));
523
524 /*
525 * When the qual is CurrentOfExpr, the path that we just added is the
526 * only one the executor can handle, so we should return before adding
527 * any others. Returning true lets the caller know not to add any
528 * others, either.
529 */
530 if (isCurrentOf)
531 return true;
532 }
533
534 /* Skip the rest if TID scans are disabled. */
536 return false;
537
538 /*
539 * If there are range quals in the baserestrict list, generate a
540 * TidRangePath.
541 */
543 rel);
544
546 {
547 /*
548 * This path uses no join clauses, but it could still have required
549 * parameterization due to LATERAL refs in its tlist.
550 */
552
554 tidrangequals,
555 required_outer,
556 0));
557
558 /* If appropriate, consider parallel tid range scan. */
560 {
561 int parallel_workers;
562
565
566 if (parallel_workers > 0)
568 rel,
569 tidrangequals,
570 required_outer,
571 parallel_workers));
572 }
573 }
574
575 /*
576 * Try to generate parameterized TidPaths using equality clauses extracted
577 * from EquivalenceClasses. (This is important since simple "t1.ctid =
578 * t2.ctid" clauses will turn into ECs.)
579 */
581 {
582 List *clauses;
583
584 /* Generate clauses, skipping any that join to lateral_referencers */
586 rel,
588 NULL,
589 rel->lateral_referencers);
590
591 /* Generate a path for each usable join clause */
593 }
594
595 /*
596 * Also consider parameterized TidPaths using "loose" join quals. Quals
597 * of the form "t1.ctid = t2.ctid" would turn into these if they are outer
598 * join quals, for example.
599 */
601
602 return false;
603}
List * generate_implied_equalities_for_column(PlannerInfo *root, RelOptInfo *rel, ec_matches_callback_type callback, void *callback_arg, Relids prohibited_rels)
Definition: equivclass.c:3239
TidRangePath * create_tidrangescan_path(PlannerInfo *root, RelOptInfo *rel, List *tidrangequals, Relids required_outer, int parallel_workers)
Definition: pathnode.c:1264
TidPath * create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals, Relids required_outer)
Definition: pathnode.c:1235
static List * TidQualFromRestrictInfoList(PlannerInfo *root, List *rlist, RelOptInfo *rel, bool *isCurrentOf)
Definition: tidpath.c:281
static void BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
Definition: tidpath.c:426
static List * TidRangeQualFromRestrictInfoList(List *rlist, RelOptInfo *rel)
Definition: tidpath.c:398
static bool ec_member_matches_ctid(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg)
Definition: tidpath.c:481
References add_partial_path(), add_path(), RelOptInfo::baserestrictinfo, BuildParameterizedTidPaths(), compute_parallel_worker(), RelOptInfo::consider_parallel, create_tidrangescan_path(), create_tidscan_path(), ec_member_matches_ctid(), enable_tidscan, generate_implied_equalities_for_column(), RelOptInfo::has_eclass_joins, RelOptInfo::joininfo, RelOptInfo::lateral_referencers, RelOptInfo::lateral_relids, max_parallel_workers_per_gather, NIL, RelOptInfo::pages, root, TidQualFromRestrictInfoList(), and TidRangeQualFromRestrictInfoList().
Referenced by set_plain_rel_pathlist().
◆ ec_clear_derived_clauses()
| void ec_clear_derived_clauses | ( | EquivalenceClass * | ec | ) |
Definition at line 3831 of file equivclass.c.
3832{
3835
3837 {
3838 derives_destroy(ec->ec_derives_hash);
3839 ec->ec_derives_hash = NULL;
3840 }
3841}
References EquivalenceClass::ec_derives_hash, EquivalenceClass::ec_derives_list, list_free(), and NIL.
Referenced by process_equivalence(), remove_rel_from_eclass(), and update_eclasses().
◆ eclass_member_iterator_next()
| EquivalenceMember * eclass_member_iterator_next | ( | EquivalenceMemberIterator * | it | ) |
Definition at line 3175 of file equivclass.c.
3176{
3178 {
3180 {
3181 EquivalenceMember *em;
3182
3183 nextcell:
3186 return em;
3187 }
3188
3189 /* Search for the next list to return members from */
3191 {
3192 /*
3193 * Be paranoid in case we're given relids above what we've sized
3194 * the ec_childmembers array to.
3195 */
3197 return NULL;
3198
3200
3201 /* If there are members in this list, use it. */
3203 {
3204 /* point current_cell to the head of this list */
3206 goto nextcell;
3207 }
3208 }
3209 return NULL;
3210 }
3211
3212 return NULL;
3213}
References bms_next_member(), EquivalenceMemberIterator::child_relids, EquivalenceMemberIterator::current_cell, EquivalenceMemberIterator::current_list, EquivalenceMemberIterator::current_relid, EquivalenceMemberIterator::ec, EquivalenceClass::ec_childmembers, EquivalenceClass::ec_childmembers_size, lfirst_node, list_head(), lnext(), and NIL.
Referenced by find_computable_ec_member(), find_ec_member_matching_expr(), find_em_for_rel(), generate_implied_equalities_for_column(), generate_join_implied_equalities_normal(), get_eclass_for_sort_expr(), and match_pathkeys_to_index().
◆ eclass_useful_for_merging()
| bool eclass_useful_for_merging | ( | PlannerInfo * | root, |
| EquivalenceClass * | eclass, | ||
| RelOptInfo * | rel | ||
| ) |
Definition at line 3490 of file equivclass.c.
3493{
3494 Relids relids;
3495 ListCell *lc;
3496
3498
3499 /*
3500 * Won't generate joinclauses if const or single-member (the latter test
3501 * covers the volatile case too)
3502 */
3504 return false;
3505
3506 /*
3507 * Note we don't test ec_broken; if we did, we'd need a separate code path
3508 * to look through ec_sources. Checking the members anyway is OK as a
3509 * possibly-overoptimistic heuristic.
3510 */
3511
3512 /* If specified rel is a child, we must consider the topmost parent rel */
3514 {
3516 relids = rel->top_parent_relids;
3517 }
3518 else
3519 relids = rel->relids;
3520
3521 /* If rel already includes all members of eclass, no point in searching */
3523 return false;
3524
3525 /*
3526 * To join, we need a member not in the given rel. Ignore children here.
3527 */
3529 {
3531
3532 /* Child members should not exist in ec_members */
3534
3536 return true;
3537 }
3538
3539 return false;
3540}
References Assert(), bms_is_empty, bms_is_subset(), bms_overlap(), eclass(), EquivalenceMember::em_is_child, EquivalenceMember::em_relids, IS_OTHER_REL, lfirst, list_length(), RelOptInfo::relids, and RelOptInfo::top_parent_relids.
Referenced by get_useful_ecs_for_relation(), and pathkeys_useful_for_merging().
◆ exprs_known_equal()
| bool exprs_known_equal | ( | PlannerInfo * | root, |
| Node * | item1, | ||
| Node * | item2, | ||
| Oid | opfamily | ||
| ) |
Definition at line 2648 of file equivclass.c.
2649{
2650 ListCell *lc1;
2651
2653 {
2655 bool item1member = false;
2656 bool item2member = false;
2657 ListCell *lc2;
2658
2659 /* Never match to a volatile EC */
2661 continue;
2662
2663 /*
2664 * It's okay to consider ec_broken ECs here. Brokenness just means we
2665 * couldn't derive all the implied clauses we'd have liked to; it does
2666 * not invalidate our knowledge that the members are equal.
2667 */
2668
2669 /* Ignore if this EC doesn't use specified opfamily */
2672 continue;
2673
2674 /* Ignore children here */
2676 {
2678
2679 /* Child members should not exist in ec_members */
2682 item1member = true;
2684 item2member = true;
2685 /* Exit as soon as equality is proven */
2686 if (item1member && item2member)
2687 return true;
2688 }
2689 }
2690 return false;
2691}
References Assert(), EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, equal(), lfirst, list_member_oid(), OidIsValid, and root.
Referenced by add_unique_group_var(), and have_partkey_equi_join().
◆ find_computable_ec_member()
| EquivalenceMember * find_computable_ec_member | ( | PlannerInfo * | root, |
| EquivalenceClass * | ec, | ||
| List * | exprs, | ||
| Relids | relids, | ||
| bool | require_parallel_safe | ||
| ) |
Definition at line 991 of file equivclass.c.
996{
997 List *exprvars;
998 EquivalenceMemberIterator it;
999 EquivalenceMember *em;
1000
1001 /*
1002 * Pull out the Vars and quasi-Vars present in "exprs". In the typical
1003 * non-appendrel case, this is just another representation of the same
1004 * list. However, it does remove the distinction between the case of a
1005 * list of plain expressions and a list of TargetEntrys.
1006 */
1008 PVC_INCLUDE_AGGREGATES |
1009 PVC_INCLUDE_WINDOWFUNCS |
1010 PVC_INCLUDE_PLACEHOLDERS |
1011 PVC_INCLUDE_CONVERTROWTYPES);
1012
1013 setup_eclass_member_iterator(&it, ec, relids);
1015 {
1016 List *emvars;
1017 ListCell *lc2;
1018
1019 /*
1020 * We shouldn't be trying to sort by an equivalence class that
1021 * contains a constant, so no need to consider such cases any further.
1022 */
1024 continue;
1025
1026 /*
1027 * Ignore child members unless they belong to the requested rel.
1028 */
1031 continue;
1032
1033 /*
1034 * Match if all Vars and quasi-Vars are present in "exprs".
1035 */
1037 PVC_INCLUDE_AGGREGATES |
1038 PVC_INCLUDE_WINDOWFUNCS |
1039 PVC_INCLUDE_PLACEHOLDERS);
1040 foreach(lc2, emvars)
1041 {
1043 break;
1044 }
1045 list_free(emvars);
1046 if (lc2)
1047 continue; /* we hit a non-available Var */
1048
1049 /*
1050 * If requested, reject expressions that are not parallel-safe. We
1051 * check this last because it's a rather expensive test.
1052 */
1053 if (require_parallel_safe &&
1055 continue;
1056
1057 return em; /* found usable expression */
1058 }
1059
1060 return NULL;
1061}
void setup_eclass_member_iterator(EquivalenceMemberIterator *it, EquivalenceClass *ec, Relids child_relids)
Definition: equivclass.c:3156
EquivalenceMember * eclass_member_iterator_next(EquivalenceMemberIterator *it)
Definition: equivclass.c:3175
Definition: pathnodes.h:1682
References bms_is_subset(), eclass_member_iterator_next(), EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, is_parallel_safe(), lfirst, list_free(), list_member(), pull_var_clause(), PVC_INCLUDE_AGGREGATES, PVC_INCLUDE_CONVERTROWTYPES, PVC_INCLUDE_PLACEHOLDERS, PVC_INCLUDE_WINDOWFUNCS, root, and setup_eclass_member_iterator().
Referenced by prepare_sort_from_pathkeys(), and relation_can_be_sorted_early().
◆ find_derived_clause_for_ec_member()
| RestrictInfo * find_derived_clause_for_ec_member | ( | PlannerInfo * | root, |
| EquivalenceClass * | ec, | ||
| EquivalenceMember * | em | ||
| ) |
Definition at line 2804 of file equivclass.c.
2807{
2810
2812}
static RestrictInfo * ec_search_derived_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec, EquivalenceMember *leftem, EquivalenceMember *rightem, EquivalenceClass *parent_ec)
Definition: equivclass.c:3893
References Assert(), EquivalenceClass::ec_has_const, ec_search_derived_clause_for_ems(), EquivalenceMember::em_is_const, and root.
Referenced by get_foreign_key_join_selectivity().
◆ find_ec_member_matching_expr()
| EquivalenceMember * find_ec_member_matching_expr | ( | EquivalenceClass * | ec, |
| Expr * | expr, | ||
| Relids | relids | ||
| ) |
Definition at line 916 of file equivclass.c.
919{
920 EquivalenceMemberIterator it;
921 EquivalenceMember *em;
922
923 /* We ignore binary-compatible relabeling on both ends */
925 expr = ((RelabelType *) expr)->arg;
926
927 setup_eclass_member_iterator(&it, ec, relids);
929 {
930 Expr *emexpr;
931
932 /*
933 * We shouldn't be trying to sort by an equivalence class that
934 * contains a constant, so no need to consider such cases any further.
935 */
937 continue;
938
939 /*
940 * Ignore child members unless they belong to the requested rel.
941 */
944 continue;
945
946 /*
947 * Match if same expression (after stripping relabel).
948 */
949 emexpr = em->em_expr;
951 emexpr = ((RelabelType *) emexpr)->arg;
952
954 return em;
955 }
956
957 return NULL;
958}
Definition: primnodes.h:1215
References bms_is_subset(), eclass_member_iterator_next(), EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, equal(), IsA, and setup_eclass_member_iterator().
Referenced by make_unique_from_pathkeys(), prepare_sort_from_pathkeys(), and relation_can_be_sorted_early().
◆ find_mergeclauses_for_outer_pathkeys()
| List * find_mergeclauses_for_outer_pathkeys | ( | PlannerInfo * | root, |
| List * | pathkeys, | ||
| List * | restrictinfos | ||
| ) |
Definition at line 1544 of file pathkeys.c.
1547{
1550
1551 /* make sure we have eclasses cached in the clauses */
1553 {
1555
1557 }
1558
1560 {
1562 EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1565
1566 /*----------
1567 * A mergejoin clause matches a pathkey if it has the same EC.
1568 * If there are multiple matching clauses, take them all. In plain
1569 * inner-join scenarios we expect only one match, because
1570 * equivalence-class processing will have removed any redundant
1571 * mergeclauses. However, in outer-join scenarios there might be
1572 * multiple matches. An example is
1573 *
1574 * select * from a full join b
1575 * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1576 *
1577 * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1578 * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1579 * we *must* do so or we will be unable to form a valid plan.
1580 *
1581 * We expect that the given pathkeys list is canonical, which means
1582 * no two members have the same EC, so it's not possible for this
1583 * code to enter the same mergeclause into the result list twice.
1584 *
1585 * It's possible that multiple matching clauses might have different
1586 * ECs on the other side, in which case the order we put them into our
1587 * result makes a difference in the pathkeys required for the inner
1588 * input rel. However this routine hasn't got any info about which
1589 * order would be best, so we don't worry about that.
1590 *
1591 * It's also possible that the selected mergejoin clauses produce
1592 * a noncanonical ordering of pathkeys for the inner side, ie, we
1593 * might select clauses that reference b.v1, b.v2, b.v1 in that
1594 * order. This is not harmful in itself, though it suggests that
1595 * the clauses are partially redundant. Since the alternative is
1596 * to omit mergejoin clauses and thereby possibly fail to generate a
1597 * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1598 * has to delete duplicates when it constructs the inner pathkeys
1599 * list, and we also have to deal with such cases specially in
1600 * create_mergejoin_plan().
1601 *----------
1602 */
1604 {
1606 EquivalenceClass *clause_ec;
1607
1608 clause_ec = rinfo->outer_is_left ?
1609 rinfo->left_ec : rinfo->right_ec;
1610 if (clause_ec == pathkey_ec)
1611 matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1612 }
1613
1614 /*
1615 * If we didn't find a mergeclause, we're done --- any additional
1616 * sort-key positions in the pathkeys are useless. (But we can still
1617 * mergejoin if we found at least one mergeclause.)
1618 */
1620 break;
1621
1622 /*
1623 * If we did find usable mergeclause(s) for this sort-key position,
1624 * add them to result list.
1625 */
1626 mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1627 }
1628
1629 return mergeclauses;
1630}
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1510
References i, j, lappend(), lfirst, list_concat(), NIL, root, and update_mergeclause_eclasses().
Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().
◆ generate_base_implied_equalities()
| void generate_base_implied_equalities | ( | PlannerInfo * | root | ) |
Definition at line 1188 of file equivclass.c.
1189{
1190 int ec_index;
1191 ListCell *lc;
1192
1193 /*
1194 * At this point, we're done absorbing knowledge of equivalences in the
1195 * query, so no further EC merging should happen, and ECs remaining in the
1196 * eq_classes list can be considered canonical. (But note that it's still
1197 * possible for new single-member ECs to be added through
1198 * get_eclass_for_sort_expr().)
1199 */
1201
1202 ec_index = 0;
1204 {
1206 bool can_generate_joinclause = false;
1208
1211
1212 /*
1213 * Generate implied equalities that are restriction clauses.
1214 * Single-member ECs won't generate any deductions, either here or at
1215 * the join level.
1216 */
1218 {
1221 else
1223
1224 /* Recover if we failed to generate required derived clauses */
1227
1228 /* Detect whether this EC might generate join clauses */
1229 can_generate_joinclause =
1231 }
1232
1233 /*
1234 * Mark the base rels cited in each eclass (which should all exist by
1235 * now) with the eq_classes indexes of all eclasses mentioning them.
1236 * This will let us avoid searching in subsequent lookups. While
1237 * we're at it, we can mark base rels that have pending eclass joins;
1238 * this is a cheap version of has_relevant_eclass_joinclause().
1239 */
1240 i = -1;
1242 {
1244
1245 /* ignore the RTE_GROUP RTE */
1247 continue;
1248
1249 if (rel == NULL) /* must be an outer join */
1250 {
1252 continue;
1253 }
1254
1256
1258 ec_index);
1259
1260 if (can_generate_joinclause)
1262 }
1263
1264 ec_index++;
1265 }
1266}
static void generate_base_implied_equalities_broken(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1487
static void generate_base_implied_equalities_no_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1371
static void generate_base_implied_equalities_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1272
References Assert(), bms_add_member(), bms_is_member(), bms_membership(), BMS_MULTIPLE, bms_next_member(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_relids, RelOptInfo::eclass_indexes, generate_base_implied_equalities_broken(), generate_base_implied_equalities_const(), generate_base_implied_equalities_no_const(), RelOptInfo::has_eclass_joins, i, lfirst, list_length(), RELOPT_BASEREL, RelOptInfo::reloptkind, and root.
Referenced by query_planner().
◆ generate_gather_paths()
| void generate_gather_paths | ( | PlannerInfo * | root, |
| RelOptInfo * | rel, | ||
| bool | override_rows | ||
| ) |
Definition at line 3188 of file allpaths.c.
3189{
3190 Path *cheapest_partial_path;
3191 Path *simple_gather_path;
3192 ListCell *lc;
3193 double rows;
3194 double *rowsp = NULL;
3195
3196 /* If there are no partial paths, there's nothing to do here. */
3198 return;
3199
3200 /* Should we override the rel's rowcount estimate? */
3201 if (override_rows)
3202 rowsp = &rows;
3203
3204 /*
3205 * The output of Gather is always unsorted, so there's only one partial
3206 * path of interest: the cheapest one. That will be the one at the front
3207 * of partial_pathlist because of the way add_partial_path works.
3208 */
3210 rows = compute_gather_rows(cheapest_partial_path);
3211 simple_gather_path = (Path *)
3213 NULL, rowsp);
3214 add_path(rel, simple_gather_path);
3215
3216 /*
3217 * For each useful ordering, we can consider an order-preserving Gather
3218 * Merge.
3219 */
3221 {
3223 GatherMergePath *path;
3224
3226 continue;
3227
3230 subpath->pathkeys, NULL, rowsp);
3232 }
3233}
GatherMergePath * create_gather_merge_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, List *pathkeys, Relids required_outer, double *rows)
Definition: pathnode.c:1751
GatherPath * create_gather_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, Relids required_outer, double *rows)
Definition: pathnode.c:1803
Definition: pathnodes.h:2274
References add_path(), compute_gather_rows(), create_gather_merge_path(), create_gather_path(), lfirst, linitial, NIL, RelOptInfo::partial_pathlist, GatherMergePath::path, RelOptInfo::reltarget, root, and subpath().
Referenced by generate_useful_gather_paths().
◆ generate_grouped_paths()
| void generate_grouped_paths | ( | PlannerInfo * | root, |
| RelOptInfo * | grouped_rel, | ||
| RelOptInfo * | rel | ||
| ) |
Definition at line 3442 of file allpaths.c.
3444{
3446 AggClauseCosts agg_costs;
3447 bool can_hash;
3448 bool can_sort;
3449 Path *cheapest_total_path = NULL;
3450 Path *cheapest_partial_path = NULL;
3451 double dNumGroups = 0;
3452 double dNumPartialGroups = 0;
3454
3456 {
3457 mark_dummy_rel(grouped_rel);
3458 return;
3459 }
3460
3461 /*
3462 * We push partial aggregation only to the lowest possible level in the
3463 * join tree that is deemed useful.
3464 */
3466 !agg_info->agg_useful)
3467 return;
3468
3471
3472 /*
3473 * Determine whether it's possible to perform sort-based implementations
3474 * of grouping, and generate the pathkeys that represent the grouping
3475 * requirements in that case.
3476 */
3478 if (can_sort)
3479 {
3480 RelOptInfo *top_grouped_rel;
3481 List *top_group_tlist;
3482
3483 top_grouped_rel = IS_OTHER_REL(rel) ?
3484 rel->top_parent->grouped_rel : grouped_rel;
3485 top_group_tlist =
3487
3488 group_pathkeys =
3490 top_group_tlist);
3491 }
3492
3493 /*
3494 * Determine whether we should consider hash-based implementations of
3495 * grouping.
3496 */
3500
3501 /*
3502 * Consider whether we should generate partially aggregated non-partial
3503 * paths. We can only do this if we have a non-partial path.
3504 */
3506 {
3507 cheapest_total_path = rel->cheapest_total_path;
3508 Assert(cheapest_total_path != NULL);
3509 }
3510
3511 /*
3512 * If parallelism is possible for grouped_rel, then we should consider
3513 * generating partially-grouped partial paths. However, if the ungrouped
3514 * rel has no partial paths, then we can't.
3515 */
3517 {
3519 Assert(cheapest_partial_path != NULL);
3520 }
3521
3522 /* Estimate number of partial groups. */
3523 if (cheapest_total_path != NULL)
3525 agg_info->group_exprs,
3526 cheapest_total_path->rows,
3527 NULL, NULL);
3528 if (cheapest_partial_path != NULL)
3530 agg_info->group_exprs,
3531 cheapest_partial_path->rows,
3532 NULL, NULL);
3533
3534 if (can_sort && cheapest_total_path != NULL)
3535 {
3536 ListCell *lc;
3537
3538 /*
3539 * Use any available suitably-sorted path as input, and also consider
3540 * sorting the cheapest-total path and incremental sort on any paths
3541 * with presorted keys.
3542 *
3543 * To save planning time, we ignore parameterized input paths unless
3544 * they are the cheapest-total path.
3545 */
3547 {
3549 Path *path;
3550 bool is_sorted;
3551 int presorted_keys;
3552
3553 /*
3554 * Ignore parameterized paths that are not the cheapest-total
3555 * path.
3556 */
3557 if (input_path->param_info &&
3558 input_path != cheapest_total_path)
3559 continue;
3560
3561 is_sorted = pathkeys_count_contained_in(group_pathkeys,
3562 input_path->pathkeys,
3563 &presorted_keys);
3564
3565 /*
3566 * Ignore paths that are not suitably or partially sorted, unless
3567 * they are the cheapest total path (no need to deal with paths
3568 * which have presorted keys when incremental sort is disabled).
3569 */
3570 if (!is_sorted && input_path != cheapest_total_path &&
3571 (presorted_keys == 0 || !enable_incremental_sort))
3572 continue;
3573
3574 /*
3575 * Since the path originates from a non-grouped relation that is
3576 * not aware of eager aggregation, we must ensure that it provides
3577 * the correct input for partial aggregation.
3578 */
3580 grouped_rel,
3581 input_path,
3582 agg_info->agg_input);
3583
3584 if (!is_sorted)
3585 {
3586 /*
3587 * We've no need to consider both a sort and incremental sort.
3588 * We'll just do a sort if there are no presorted keys and an
3589 * incremental sort when there are presorted keys.
3590 */
3593 grouped_rel,
3594 path,
3595 group_pathkeys,
3596 -1.0);
3597 else
3599 grouped_rel,
3600 path,
3601 group_pathkeys,
3602 presorted_keys,
3603 -1.0);
3604 }
3605
3606 /*
3607 * qual is NIL because the HAVING clause cannot be evaluated until
3608 * the final value of the aggregate is known.
3609 */
3611 grouped_rel,
3612 path,
3613 agg_info->target,
3614 AGG_SORTED,
3615 AGGSPLIT_INITIAL_SERIAL,
3616 agg_info->group_clauses,
3617 NIL,
3618 &agg_costs,
3619 dNumGroups);
3620
3621 add_path(grouped_rel, path);
3622 }
3623 }
3624
3625 if (can_sort && cheapest_partial_path != NULL)
3626 {
3627 ListCell *lc;
3628
3629 /* Similar to above logic, but for partial paths. */
3631 {
3633 Path *path;
3634 bool is_sorted;
3635 int presorted_keys;
3636
3637 is_sorted = pathkeys_count_contained_in(group_pathkeys,
3638 input_path->pathkeys,
3639 &presorted_keys);
3640
3641 /*
3642 * Ignore paths that are not suitably or partially sorted, unless
3643 * they are the cheapest partial path (no need to deal with paths
3644 * which have presorted keys when incremental sort is disabled).
3645 */
3646 if (!is_sorted && input_path != cheapest_partial_path &&
3647 (presorted_keys == 0 || !enable_incremental_sort))
3648 continue;
3649
3650 /*
3651 * Since the path originates from a non-grouped relation that is
3652 * not aware of eager aggregation, we must ensure that it provides
3653 * the correct input for partial aggregation.
3654 */
3656 grouped_rel,
3657 input_path,
3658 agg_info->agg_input);
3659
3660 if (!is_sorted)
3661 {
3662 /*
3663 * We've no need to consider both a sort and incremental sort.
3664 * We'll just do a sort if there are no presorted keys and an
3665 * incremental sort when there are presorted keys.
3666 */
3669 grouped_rel,
3670 path,
3671 group_pathkeys,
3672 -1.0);
3673 else
3675 grouped_rel,
3676 path,
3677 group_pathkeys,
3678 presorted_keys,
3679 -1.0);
3680 }
3681
3682 /*
3683 * qual is NIL because the HAVING clause cannot be evaluated until
3684 * the final value of the aggregate is known.
3685 */
3687 grouped_rel,
3688 path,
3689 agg_info->target,
3690 AGG_SORTED,
3691 AGGSPLIT_INITIAL_SERIAL,
3692 agg_info->group_clauses,
3693 NIL,
3694 &agg_costs,
3695 dNumPartialGroups);
3696
3697 add_partial_path(grouped_rel, path);
3698 }
3699 }
3700
3701 /*
3702 * Add a partially-grouped HashAgg Path where possible
3703 */
3704 if (can_hash && cheapest_total_path != NULL)
3705 {
3706 Path *path;
3707
3708 /*
3709 * Since the path originates from a non-grouped relation that is not
3710 * aware of eager aggregation, we must ensure that it provides the
3711 * correct input for partial aggregation.
3712 */
3714 grouped_rel,
3715 cheapest_total_path,
3716 agg_info->agg_input);
3717
3718 /*
3719 * qual is NIL because the HAVING clause cannot be evaluated until the
3720 * final value of the aggregate is known.
3721 */
3723 grouped_rel,
3724 path,
3725 agg_info->target,
3726 AGG_HASHED,
3727 AGGSPLIT_INITIAL_SERIAL,
3728 agg_info->group_clauses,
3729 NIL,
3730 &agg_costs,
3731 dNumGroups);
3732
3733 add_path(grouped_rel, path);
3734 }
3735
3736 /*
3737 * Now add a partially-grouped HashAgg partial Path where possible
3738 */
3739 if (can_hash && cheapest_partial_path != NULL)
3740 {
3741 Path *path;
3742
3743 /*
3744 * Since the path originates from a non-grouped relation that is not
3745 * aware of eager aggregation, we must ensure that it provides the
3746 * correct input for partial aggregation.
3747 */
3749 grouped_rel,
3750 cheapest_partial_path,
3751 agg_info->agg_input);
3752
3753 /*
3754 * qual is NIL because the HAVING clause cannot be evaluated until the
3755 * final value of the aggregate is known.
3756 */
3758 grouped_rel,
3759 path,
3760 agg_info->target,
3761 AGG_HASHED,
3762 AGGSPLIT_INITIAL_SERIAL,
3763 agg_info->group_clauses,
3764 NIL,
3765 &agg_costs,
3766 dNumPartialGroups);
3767
3768 add_partial_path(grouped_rel, path);
3769 }
3770}
bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
Definition: pathkeys.c:558
List * make_pathkeys_for_sortclauses(PlannerInfo *root, List *sortclauses, List *tlist)
Definition: pathkeys.c:1336
ProjectionPath * create_projection_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target)
Definition: pathnode.c:2525
IncrementalSortPath * create_incremental_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, int presorted_keys, double limit_tuples)
Definition: pathnode.c:2793
SortPath * create_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, double limit_tuples)
Definition: pathnode.c:2842
AggPath * create_agg_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, AggStrategy aggstrategy, AggSplit aggsplit, List *groupClause, List *qual, const AggClauseCosts *aggcosts, double numGroups)
Definition: pathnode.c:2995
void get_agg_clause_costs(PlannerInfo *root, AggSplit aggsplit, AggClauseCosts *costs)
Definition: prepagg.c:559
double estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, List **pgset, EstimationInfo *estinfo)
Definition: selfuncs.c:3768
Definition: pathnodes.h:59
Definition: pathnodes.h:1189
List * make_tlist_from_pathtarget(PathTarget *target)
Definition: tlist.c:624
References add_partial_path(), add_path(), AGG_HASHED, RelOptInfo::agg_info, RelAggInfo::agg_input, AGG_SORTED, RelAggInfo::agg_useful, AGGSPLIT_INITIAL_SERIAL, RelAggInfo::apply_agg_at, Assert(), bms_equal(), RelOptInfo::cheapest_total_path, RelOptInfo::consider_parallel, create_agg_path(), create_incremental_sort_path(), create_projection_path(), create_sort_path(), enable_incremental_sort, estimate_num_groups(), get_agg_clause_costs(), RelAggInfo::group_clauses, RelAggInfo::group_exprs, RelOptInfo::grouped_rel, grouping_is_hashable(), grouping_is_sortable(), IS_DUMMY_REL, IS_OTHER_REL, lfirst, linitial, make_pathkeys_for_sortclauses(), make_tlist_from_pathtarget(), mark_dummy_rel(), MemSet, NIL, RelOptInfo::partial_pathlist, Path::pathkeys, pathkeys_count_contained_in(), RelOptInfo::pathlist, RelOptInfo::relids, root, Path::rows, and RelAggInfo::target.
Referenced by generate_partitionwise_join_paths(), merge_clump(), set_grouped_rel_pathlist(), and standard_join_search().
◆ generate_implied_equalities_for_column()
| List * generate_implied_equalities_for_column | ( | PlannerInfo * | root, |
| RelOptInfo * | rel, | ||
| ec_matches_callback_type | callback, | ||
| void * | callback_arg, | ||
| Relids | prohibited_rels | ||
| ) |
Definition at line 3239 of file equivclass.c.
3244{
3247 Relids parent_relids;
3249
3250 /* Should be OK to rely on eclass_indexes */
3252
3253 /* Indexes are available only on base or "other" member relations. */
3255
3256 /* If it's a child rel, we'll need to know what its parent(s) are */
3257 if (is_child_rel)
3259 else
3260 parent_relids = NULL; /* not used, but keep compiler quiet */
3261
3262 i = -1;
3264 {
3266 EquivalenceMemberIterator it;
3267 EquivalenceMember *cur_em;
3268 ListCell *lc2;
3269
3270 /* Sanity check eclass_indexes only contain ECs for rel */
3272
3273 /*
3274 * Won't generate joinclauses if const or single-member (the latter
3275 * test covers the volatile case too)
3276 */
3278 continue;
3279
3280 /*
3281 * Scan members, looking for a match to the target column. Note that
3282 * child EC members are considered, but only when they belong to the
3283 * target relation. (Unlike regular members, the same expression
3284 * could be a child member of more than one EC. Therefore, it's
3285 * potentially order-dependent which EC a child relation's target
3286 * column gets matched to. This is annoying but it only happens in
3287 * corner cases, so for now we live with just reporting the first
3288 * match. See also get_eclass_for_sort_expr.)
3289 */
3292 {
3295 break;
3296 }
3297
3298 if (!cur_em)
3299 continue;
3300
3301 /*
3302 * Found our match. Scan the other EC members and attempt to generate
3303 * joinclauses. Ignore children here.
3304 */
3306 {
3308 Oid eq_op;
3309 RestrictInfo *rinfo;
3310
3311 /* Child members should not exist in ec_members */
3313
3314 /* Make sure it'll be a join to a different rel */
3315 if (other_em == cur_em ||
3317 continue;
3318
3319 /* Forget it if caller doesn't want joins to this rel */
3321 continue;
3322
3323 /*
3324 * Also, if this is a child rel, avoid generating a useless join
3325 * to its parent rel(s).
3326 */
3327 if (is_child_rel &&
3329 continue;
3330
3331 eq_op = select_equality_operator(cur_ec,
3332 cur_em->em_datatype,
3333 other_em->em_datatype);
3335 continue;
3336
3337 /* set parent_ec to mark as redundant with other joinclauses */
3339 cur_em, other_em,
3340 cur_ec);
3341
3342 result = lappend(result, rinfo);
3343 }
3344
3345 /*
3346 * If somehow we failed to create any join clauses, we might as well
3347 * keep scanning the ECs for another match. But if we did make any,
3348 * we're done, because we don't want to return non-redundant clauses.
3349 */
3350 if (result)
3351 break;
3352 }
3353
3354 return result;
3355}
static RestrictInfo * create_join_clause(PlannerInfo *root, EquivalenceClass *ec, Oid opno, EquivalenceMember *leftem, EquivalenceMember *rightem, EquivalenceClass *parent_ec)
Definition: equivclass.c:1983
static Oid select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype)
Definition: equivclass.c:1948
static void callback(struct sockaddr *addr, struct sockaddr *mask, void *unused)
Definition: test_ifaddrs.c:46
References Assert(), bms_equal(), bms_is_subset(), bms_next_member(), bms_overlap(), callback(), create_join_clause(), EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, RelOptInfo::eclass_indexes, eclass_member_iterator_next(), EquivalenceMember::em_datatype, EquivalenceMember::em_is_child, EquivalenceMember::em_relids, find_childrel_parents(), i, IS_SIMPLE_REL, lappend(), lfirst, list_length(), list_nth(), NIL, OidIsValid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, root, select_equality_operator(), and setup_eclass_member_iterator().
Referenced by create_tidscan_paths(), match_eclass_clauses_to_index(), and postgresGetForeignPaths().
◆ generate_join_implied_equalities()
| List * generate_join_implied_equalities | ( | PlannerInfo * | root, |
| Relids | join_relids, | ||
| Relids | outer_relids, | ||
| RelOptInfo * | inner_rel, | ||
| SpecialJoinInfo * | sjinfo | ||
| ) |
Definition at line 1550 of file equivclass.c.
1555{
1558 Relids nominal_inner_relids;
1559 Relids nominal_join_relids;
1560 Bitmapset *matching_ecs;
1562
1563 /* If inner rel is a child, extra setup work is needed */
1565 {
1567
1568 /* Fetch relid set for the topmost parent rel */
1569 nominal_inner_relids = inner_rel->top_parent_relids;
1570 /* ECs will be marked with the parent's relid, not the child's */
1571 nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1573 nominal_join_relids,
1574 sjinfo,
1575 NULL);
1576 }
1577 else
1578 {
1579 nominal_inner_relids = inner_relids;
1580 nominal_join_relids = join_relids;
1581 }
1582
1583 /*
1584 * Examine all potentially-relevant eclasses.
1585 *
1586 * If we are considering an outer join, we must include "join" clauses
1587 * that mention either input rel plus the outer join's relid; these
1588 * represent post-join filter clauses that have to be applied at this
1589 * join. We don't have infrastructure that would let us identify such
1590 * eclasses cheaply, so just fall back to considering all eclasses
1591 * mentioning anything in nominal_join_relids.
1592 *
1593 * At inner joins, we can be smarter: only consider eclasses mentioning
1594 * both input rels.
1595 */
1598 else
1600 outer_relids);
1601
1602 i = -1;
1604 {
1607
1608 /* ECs containing consts do not need any further enforcement */
1610 continue;
1611
1612 /* Single-member ECs won't generate any deductions */
1614 continue;
1615
1616 /* Sanity check that this eclass overlaps the join */
1618
1621 ec,
1622 join_relids,
1623 outer_relids,
1624 inner_relids);
1625
1626 /* Recover if we failed to generate required derived clauses */
1629 ec,
1630 nominal_join_relids,
1631 outer_relids,
1632 nominal_inner_relids,
1633 inner_rel);
1634
1635 result = list_concat(result, sublist);
1636 }
1637
1638 return result;
1639}
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1721
static Bitmapset * get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
Definition: equivclass.c:3647
static List * generate_join_implied_equalities_broken(PlannerInfo *root, EquivalenceClass *ec, Relids nominal_join_relids, Relids outer_relids, Relids nominal_inner_relids, RelOptInfo *inner_rel)
Definition: equivclass.c:1899
Relids add_outer_joins_to_relids(PlannerInfo *root, Relids input_relids, SpecialJoinInfo *sjinfo, List **pushed_down_joins)
Definition: joinrels.c:800
References add_outer_joins_to_relids(), Assert(), bms_is_empty, bms_next_member(), bms_overlap(), bms_union(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), get_common_eclass_indexes(), get_eclass_indexes_for_relids(), i, IS_OTHER_REL, list_concat(), list_length(), list_nth(), NIL, SpecialJoinInfo::ojrelid, RelOptInfo::relids, root, and RelOptInfo::top_parent_relids.
Referenced by build_joinrel_restrictlist(), check_index_predicates(), get_baserel_parampathinfo(), get_joinrel_parampathinfo(), reduce_unique_semijoins(), and remove_self_joins_one_group().
◆ generate_join_implied_equalities_for_ecs()
| List * generate_join_implied_equalities_for_ecs | ( | PlannerInfo * | root, |
| List * | eclasses, | ||
| Relids | join_relids, | ||
| Relids | outer_relids, | ||
| RelOptInfo * | inner_rel | ||
| ) |
Definition at line 1650 of file equivclass.c.
1655{
1658 Relids nominal_inner_relids;
1659 Relids nominal_join_relids;
1660 ListCell *lc;
1661
1662 /* If inner rel is a child, extra setup work is needed */
1664 {
1666
1667 /* Fetch relid set for the topmost parent rel */
1668 nominal_inner_relids = inner_rel->top_parent_relids;
1669 /* ECs will be marked with the parent's relid, not the child's */
1670 nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1671 }
1672 else
1673 {
1674 nominal_inner_relids = inner_relids;
1675 nominal_join_relids = join_relids;
1676 }
1677
1678 foreach(lc, eclasses)
1679 {
1682
1683 /* ECs containing consts do not need any further enforcement */
1685 continue;
1686
1687 /* Single-member ECs won't generate any deductions */
1689 continue;
1690
1691 /* We can quickly ignore any that don't overlap the join, too */
1693 continue;
1694
1697 ec,
1698 join_relids,
1699 outer_relids,
1700 inner_relids);
1701
1702 /* Recover if we failed to generate required derived clauses */
1705 ec,
1706 nominal_join_relids,
1707 outer_relids,
1708 nominal_inner_relids,
1709 inner_rel);
1710
1711 result = list_concat(result, sublist);
1712 }
1713
1714 return result;
1715}
References Assert(), bms_is_empty, bms_overlap(), bms_union(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), IS_OTHER_REL, lfirst, list_concat(), list_length(), NIL, RelOptInfo::relids, root, and RelOptInfo::top_parent_relids.
Referenced by get_joinrel_parampathinfo().
◆ generate_partitionwise_join_paths()
| void generate_partitionwise_join_paths | ( | PlannerInfo * | root, |
| RelOptInfo * | rel | ||
| ) |
Definition at line 4790 of file allpaths.c.
4791{
4793 int cnt_parts;
4794 int num_parts;
4795 RelOptInfo **part_rels;
4796
4797 /* Handle only join relations here. */
4799 return;
4800
4801 /* We've nothing to do if the relation is not partitioned. */
4803 return;
4804
4805 /* The relation should have consider_partitionwise_join set. */
4807
4808 /* Guard against stack overflow due to overly deep partition hierarchy. */
4809 check_stack_depth();
4810
4811 num_parts = rel->nparts;
4812 part_rels = rel->part_rels;
4813
4814 /* Collect non-dummy child-joins. */
4815 for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
4816 {
4817 RelOptInfo *child_rel = part_rels[cnt_parts];
4818
4819 /* If it's been pruned entirely, it's certainly dummy. */
4820 if (child_rel == NULL)
4821 continue;
4822
4823 /* Make partitionwise join paths for this partitioned child-join. */
4825
4826 /* If we failed to make any path for this child, we must give up. */
4828 {
4829 /*
4830 * Mark the parent joinrel as unpartitioned so that later
4831 * functions treat it correctly.
4832 */
4833 rel->nparts = 0;
4834 return;
4835 }
4836
4837 /* Else, identify the cheapest path for it. */
4838 set_cheapest(child_rel);
4839
4840 /* Dummy children need not be scanned, so ignore those. */
4842 continue;
4843
4844 /*
4845 * Except for the topmost scan/join rel, consider generating partial
4846 * aggregation paths for the grouped relation on top of the paths of
4847 * this partitioned child-join. After that, we're done creating paths
4848 * for the grouped relation, so run set_cheapest().
4849 */
4853 root->all_query_rels))
4854 {
4856
4858
4860 set_cheapest(grouped_rel);
4861 }
4862
4863#ifdef OPTIMIZER_DEBUG
4864 pprint(child_rel);
4865#endif
4866
4867 live_children = lappend(live_children, child_rel);
4868 }
4869
4870 /* If all child-joins are dummy, parent join is also dummy. */
4871 if (!live_children)
4872 {
4873 mark_dummy_rel(rel);
4874 return;
4875 }
4876
4877 /* Build additional paths for this rel from child-join paths. */
4879 list_free(live_children);
4880}
void generate_partitionwise_join_paths(PlannerInfo *root, RelOptInfo *rel)
Definition: allpaths.c:4790
void generate_grouped_paths(PlannerInfo *root, RelOptInfo *grouped_rel, RelOptInfo *rel)
Definition: allpaths.c:3442
void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels)
Definition: allpaths.c:1404
References add_paths_to_append_rel(), Assert(), bms_equal(), check_stack_depth(), RelOptInfo::consider_partitionwise_join, generate_grouped_paths(), generate_partitionwise_join_paths(), RelOptInfo::grouped_rel, IS_DUMMY_REL, IS_GROUPED_REL, IS_JOIN_REL, IS_OTHER_REL, IS_PARTITIONED_REL, lappend(), list_free(), mark_dummy_rel(), NIL, RelOptInfo::nparts, RelOptInfo::pathlist, pprint(), RelOptInfo::relids, root, set_cheapest(), and RelOptInfo::top_parent_relids.
Referenced by generate_partitionwise_join_paths(), merge_clump(), and standard_join_search().
◆ generate_useful_gather_paths()
| void generate_useful_gather_paths | ( | PlannerInfo * | root, |
| RelOptInfo * | rel, | ||
| bool | override_rows | ||
| ) |
Definition at line 3325 of file allpaths.c.
3326{
3327 ListCell *lc;
3328 double rows;
3329 double *rowsp = NULL;
3331 Path *cheapest_partial_path = NULL;
3332
3333 /* If there are no partial paths, there's nothing to do here. */
3335 return;
3336
3337 /* Should we override the rel's rowcount estimate? */
3338 if (override_rows)
3339 rowsp = &rows;
3340
3341 /* generate the regular gather (merge) paths */
3343
3344 /* consider incremental sort for interesting orderings */
3346
3347 /* used for explicit (full) sort paths */
3349
3350 /*
3351 * Consider sorted paths for each interesting ordering. We generate both
3352 * incremental and full sort.
3353 */
3354 foreach(lc, useful_pathkeys_list)
3355 {
3357 ListCell *lc2;
3358 bool is_sorted;
3359 int presorted_keys;
3360
3362 {
3364 GatherMergePath *path;
3365
3366 is_sorted = pathkeys_count_contained_in(useful_pathkeys,
3367 subpath->pathkeys,
3368 &presorted_keys);
3369
3370 /*
3371 * We don't need to consider the case where a subpath is already
3372 * fully sorted because generate_gather_paths already creates a
3373 * gather merge path for every subpath that has pathkeys present.
3374 *
3375 * But since the subpath is already sorted, we know we don't need
3376 * to consider adding a sort (full or incremental) on top of it,
3377 * so we can continue here.
3378 */
3379 if (is_sorted)
3380 continue;
3381
3382 /*
3383 * Try at least sorting the cheapest path and also try
3384 * incrementally sorting any path which is partially sorted
3385 * already (no need to deal with paths which have presorted keys
3386 * when incremental sort is disabled unless it's the cheapest
3387 * input path).
3388 */
3390 (presorted_keys == 0 || !enable_incremental_sort))
3391 continue;
3392
3393 /*
3394 * Consider regular sort for any path that's not presorted or if
3395 * incremental sort is disabled. We've no need to consider both
3396 * sort and incremental sort on the same path. We assume that
3397 * incremental sort is always faster when there are presorted
3398 * keys.
3399 *
3400 * This is not redundant with the gather paths created in
3401 * generate_gather_paths, because that doesn't generate ordered
3402 * output. Here we add an explicit sort to match the useful
3403 * ordering.
3404 */
3406 {
3408 rel,
3409 subpath,
3410 useful_pathkeys,
3411 -1.0);
3412 }
3413 else
3415 rel,
3416 subpath,
3417 useful_pathkeys,
3418 presorted_keys,
3419 -1);
3422 subpath,
3423 rel->reltarget,
3424 subpath->pathkeys,
3425 NULL,
3426 rowsp);
3427
3429 }
3430 }
3431}
static List * get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel, bool require_parallel_safe)
Definition: allpaths.c:3257
void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
Definition: allpaths.c:3188
References add_path(), compute_gather_rows(), create_gather_merge_path(), create_incremental_sort_path(), create_sort_path(), enable_incremental_sort, generate_gather_paths(), get_useful_pathkeys_for_relation(), lfirst, linitial, NIL, RelOptInfo::partial_pathlist, GatherMergePath::path, pathkeys_count_contained_in(), RelOptInfo::reltarget, root, and subpath().
Referenced by apply_scanjoin_target_to_paths(), create_partial_distinct_paths(), create_partial_unique_paths(), gather_grouping_paths(), merge_clump(), set_rel_pathlist(), and standard_join_search().
◆ get_cheapest_fractional_path_for_pathkeys()
| Path * get_cheapest_fractional_path_for_pathkeys | ( | List * | paths, |
| List * | pathkeys, | ||
| Relids | required_outer, | ||
| double | fraction | ||
| ) |
Definition at line 666 of file pathkeys.c.
670{
671 Path *matched_path = NULL;
672 ListCell *l;
673
674 foreach(l, paths)
675 {
677
678 /*
679 * Since cost comparison is a lot cheaper than pathkey comparison, do
680 * that first. (XXX is that still true?)
681 */
682 if (matched_path != NULL &&
683 compare_fractional_path_costs(matched_path, path, fraction) <= 0)
684 continue;
685
688 matched_path = path;
689 }
690 return matched_path;
691}
int compare_fractional_path_costs(Path *path1, Path *path2, double fraction)
Definition: pathnode.c:125
References bms_is_subset(), compare_fractional_path_costs(), lfirst, PATH_REQ_OUTER, Path::pathkeys, and pathkeys_contained_in().
Referenced by build_minmax_path(), and generate_orderedappend_paths().
◆ get_cheapest_parallel_safe_total_inner()
Definition at line 699 of file pathkeys.c.
700{
701 ListCell *l;
702
703 foreach(l, paths)
704 {
706
709 return innerpath;
710 }
711
712 return NULL;
713}
References bms_is_empty, lfirst, Path::parallel_safe, and PATH_REQ_OUTER.
Referenced by add_paths_to_append_rel(), hash_inner_and_outer(), match_unsorted_outer(), and sort_inner_and_outer().
◆ get_cheapest_path_for_pathkeys()
| Path * get_cheapest_path_for_pathkeys | ( | List * | paths, |
| List * | pathkeys, | ||
| Relids | required_outer, | ||
| CostSelector | cost_criterion, | ||
| bool | require_parallel_safe | ||
| ) |
Definition at line 620 of file pathkeys.c.
624{
625 Path *matched_path = NULL;
626 ListCell *l;
627
628 foreach(l, paths)
629 {
631
632 /* If required, reject paths that are not parallel-safe */
634 continue;
635
636 /*
637 * Since cost comparison is a lot cheaper than pathkey comparison, do
638 * that first. (XXX is that still true?)
639 */
640 if (matched_path != NULL &&
641 compare_path_costs(matched_path, path, cost_criterion) <= 0)
642 continue;
643
646 matched_path = path;
647 }
648 return matched_path;
649}
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:70
References bms_is_subset(), compare_path_costs(), lfirst, Path::parallel_safe, PATH_REQ_OUTER, Path::pathkeys, and pathkeys_contained_in().
Referenced by generate_mergejoin_paths(), generate_nonunion_paths(), generate_orderedappend_paths(), generate_union_paths(), and get_cheapest_parameterized_child_path().
◆ get_eclass_for_sort_expr()
| EquivalenceClass * get_eclass_for_sort_expr | ( | PlannerInfo * | root, |
| Expr * | expr, | ||
| List * | opfamilies, | ||
| Oid | opcintype, | ||
| Oid | collation, | ||
| Index | sortref, | ||
| Relids | rel, | ||
| bool | create_it | ||
| ) |
Definition at line 736 of file equivclass.c.
744{
745 JoinDomain *jdomain;
746 Relids expr_relids;
747 EquivalenceClass *newec;
748 EquivalenceMember *newem;
749 ListCell *lc1;
750 MemoryContext oldcontext;
751
752 /*
753 * Ensure the expression exposes the correct type and collation.
754 */
755 expr = canonicalize_ec_expression(expr, opcintype, collation);
756
757 /*
758 * Since SortGroupClause nodes are top-level expressions (GROUP BY, ORDER
759 * BY, etc), they can be presumed to belong to the top JoinDomain.
760 */
762
763 /*
764 * Scan through the existing EquivalenceClasses for a match
765 */
767 {
769 EquivalenceMemberIterator it;
770 EquivalenceMember *cur_em;
771
772 /*
773 * Never match to a volatile EC, except when we are looking at another
774 * reference to the same volatile SortGroupClause.
775 */
777 (sortref == 0 || sortref != cur_ec->ec_sortref))
778 continue;
779
781 continue;
783 continue;
784
785 setup_eclass_member_iterator(&it, cur_ec, rel);
787 {
788 /*
789 * Ignore child members unless they match the request.
790 */
793 continue;
794
795 /*
796 * Match constants only within the same JoinDomain (see
797 * optimizer/README).
798 */
800 continue;
801
804 return cur_ec; /* Match! */
805 }
806 }
807
808 /* No match; does caller want a NULL result? */
809 if (!create_it)
810 return NULL;
811
812 /*
813 * OK, build a new single-member EC
814 *
815 * Here, we must be sure that we construct the EC in the right context.
816 */
818
821 newec->ec_collation = collation;
822 newec->ec_childmembers_size = 0;
824 newec->ec_childmembers = NULL;
827 newec->ec_derives_hash = NULL;
828 newec->ec_relids = NULL;
832 newec->ec_sortref = sortref;
833 newec->ec_min_security = UINT_MAX;
834 newec->ec_max_security = 0;
835 newec->ec_merged = NULL;
836
839
840 /*
841 * Get the precise set of relids appearing in the expression.
842 */
844
846 jdomain, opcintype);
847
848 /*
849 * add_eq_member doesn't check for volatile functions, set-returning
850 * functions, aggregates, or window functions, but such could appear in
851 * sort expressions; so we have to check whether its const-marking was
852 * correct.
853 */
855 {
860 {
863 }
864 }
865
867
868 /*
869 * If EC merging is already complete, we have to mop up by adding the new
870 * EC to the eclass_indexes of the relation(s) mentioned in it.
871 */
873 {
876
878 {
880
881 /* ignore the RTE_GROUP RTE */
883 continue;
884
885 if (rel == NULL) /* must be an outer join */
886 {
888 continue;
889 }
890
892
894 ec_index);
895 }
896 }
897
898 MemoryContextSwitchTo(oldcontext);
899
900 return newec;
901}
static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, JoinDomain *jdomain, Oid datatype)
Definition: equivclass.c:628
Definition: pathnodes.h:1464
References add_eq_member(), Assert(), bms_add_member(), bms_equal(), bms_is_member(), bms_next_member(), canonicalize_ec_expression(), contain_agg_clause(), contain_volatile_functions(), contain_window_function(), copyObject, EquivalenceClass::ec_broken, EquivalenceClass::ec_childmembers, EquivalenceClass::ec_childmembers_size, EquivalenceClass::ec_collation, EquivalenceClass::ec_derives_hash, EquivalenceClass::ec_derives_list, EquivalenceClass::ec_has_const, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_max_security, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_min_security, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_relids, EquivalenceClass::ec_sortref, EquivalenceClass::ec_sources, RelOptInfo::eclass_indexes, eclass_member_iterator_next(), elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_jdomain, EquivalenceMember::em_relids, equal(), ERROR, expression_returns_set(), i, lappend(), lfirst, linitial_node, list_copy(), list_length(), makeNode, MemoryContextSwitchTo(), NIL, pull_varnos(), RELOPT_BASEREL, RelOptInfo::reloptkind, root, and setup_eclass_member_iterator().
Referenced by convert_subquery_pathkeys(), get_eclass_for_sortgroupclause(), initialize_mergeclause_eclasses(), and make_pathkey_from_sortinfo().
◆ get_useful_group_keys_orderings()
| List * get_useful_group_keys_orderings | ( | PlannerInfo * | root, |
| Path * | path | ||
| ) |
Definition at line 467 of file pathkeys.c.
468{
471 GroupByOrdering *info;
472
475
476 /* always return at least the original pathkeys/clauses */
478 info->pathkeys = pathkeys;
479 info->clauses = clauses;
480 infos = lappend(infos, info);
481
482 /*
483 * Should we try generating alternative orderings of the group keys? If
484 * not, we produce only the order specified in the query, i.e. the
485 * optimization is effectively disabled.
486 */
488 return infos;
489
490 /*
491 * Grouping sets have own and more complex logic to decide the ordering.
492 */
494 return infos;
495
496 /*
497 * If the path is sorted in some way, try reordering the group keys to
498 * match the path as much of the ordering as possible. Then thanks to
499 * incremental sort we would get this sort as cheap as possible.
500 */
503 {
504 int n;
505
507 root->num_groupby_pathkeys);
508
509 if (n > 0 &&
512 {
514 info->pathkeys = pathkeys;
515 info->clauses = clauses;
516
517 infos = lappend(infos, info);
518 }
519 }
520
521#ifdef USE_ASSERT_CHECKING
522 {
524 ListCell *lc;
525
526 /* Test consistency of info structures */
527 for_each_from(lc, infos, 1)
528 {
529 ListCell *lc1,
530 *lc2;
531
533
538
540 {
543
545 }
546 }
547 }
548#endif
549 return infos;
550}
List * list_difference_ptr(const List *list1, const List *list2)
Definition: list.c:1263
static int group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys, List **group_clauses, int num_groupby_pathkeys)
Definition: pathkeys.c:370
static struct subre * parse(struct vars *v, int stopper, int type, struct state *init, struct state *final)
Definition: regcomp.c:717
Definition: pathnodes.h:1731
Definition: parsenodes.h:118
Definition: parsenodes.h:1467
References Assert(), GroupByOrdering::clauses, compare_pathkeys(), enable_group_by_reordering, enable_incremental_sort, for_each_from, forboth, group_keys_reorder_by_pathkeys(), lappend(), lfirst_node, linitial_node, list_difference(), list_difference_ptr(), list_length(), makeNode, NIL, parse(), GroupByOrdering::pathkeys, Path::pathkeys, pathkeys_contained_in(), PATHKEYS_EQUAL, root, and SortGroupClause::tleSortGroupRef.
Referenced by add_paths_to_grouping_rel(), and create_partial_grouping_paths().
◆ has_relevant_eclass_joinclause()
| bool has_relevant_eclass_joinclause | ( | PlannerInfo * | root, |
| RelOptInfo * | rel1 | ||
| ) |
Definition at line 3446 of file equivclass.c.
3447{
3448 Bitmapset *matched_ecs;
3450
3451 /* Examine only eclasses mentioning rel1 */
3453
3454 i = -1;
3456 {
3458 i);
3459
3460 /*
3461 * Won't generate joinclauses if single-member (this test covers the
3462 * volatile case too)
3463 */
3465 continue;
3466
3467 /*
3468 * Per the comment in have_relevant_eclass_joinclause, it's sufficient
3469 * to find an EC that mentions both this rel and some other rel.
3470 */
3472 return true;
3473 }
3474
3475 return false;
3476}
References bms_is_subset(), bms_next_member(), EquivalenceClass::ec_members, EquivalenceClass::ec_relids, get_eclass_indexes_for_relids(), i, list_length(), list_nth(), RelOptInfo::relids, and root.
Referenced by build_join_rel().
◆ has_useful_pathkeys()
| bool has_useful_pathkeys | ( | PlannerInfo * | root, |
| RelOptInfo * | rel | ||
| ) |
Definition at line 2291 of file pathkeys.c.
2292{
2294 return true; /* might be able to use pathkeys for merging */
2296 return true; /* the upper planner might need them */
2297
2298 return false; /* definitely useless */
2299}
References RelOptInfo::has_eclass_joins, RelOptInfo::joininfo, NIL, and root.
Referenced by build_child_join_rel(), build_index_paths(), and set_append_rel_size().
◆ have_join_order_restriction()
| bool have_join_order_restriction | ( | PlannerInfo * | root, |
| RelOptInfo * | rel1, | ||
| RelOptInfo * | rel2 | ||
| ) |
Definition at line 1254 of file joinrels.c.
1256{
1257 bool result = false;
1258 ListCell *l;
1259
1260 /*
1261 * If either side has a direct lateral reference to the other, attempt the
1262 * join regardless of outer-join considerations.
1263 */
1266 return true;
1267
1268 /*
1269 * Likewise, if both rels are needed to compute some PlaceHolderVar,
1270 * attempt the join regardless of outer-join considerations. (This is not
1271 * very desirable, because a PHV with a large eval_at set will cause a lot
1272 * of probably-useless joins to be considered, but failing to do this can
1273 * cause us to fail to construct a plan at all.)
1274 */
1276 {
1278
1281 return true;
1282 }
1283
1284 /*
1285 * It's possible that the rels correspond to the left and right sides of a
1286 * degenerate outer join, that is, one with no joinclause mentioning the
1287 * non-nullable side; in which case we should force the join to occur.
1288 *
1289 * Also, the two rels could represent a clauseless join that has to be
1290 * completed to build up the LHS or RHS of an outer join.
1291 */
1293 {
1295
1296 /* ignore full joins --- other mechanisms handle them */
1298 continue;
1299
1300 /* Can we perform the SJ with these rels? */
1303 {
1304 result = true;
1305 break;
1306 }
1309 {
1310 result = true;
1311 break;
1312 }
1313
1314 /*
1315 * Might we need to join these rels to complete the RHS? We have to
1316 * use "overlap" tests since either rel might include a lower SJ that
1317 * has been proven to commute with this one.
1318 */
1321 {
1322 result = true;
1323 break;
1324 }
1325
1326 /* Likewise for the LHS. */
1329 {
1330 result = true;
1331 break;
1332 }
1333 }
1334
1335 /*
1336 * We do not force the join to occur if either input rel can legally be
1337 * joined to anything else using joinclauses. This essentially means that
1338 * clauseless bushy joins are put off as long as possible. The reason is
1339 * that when there is a join order restriction high up in the join tree
1340 * (that is, with many rels inside the LHS or RHS), we would otherwise
1341 * expend lots of effort considering very stupid join combinations within
1342 * its LHS or RHS.
1343 */
1344 if (result)
1345 {
1348 result = false;
1349 }
1350
1351 return result;
1352}
static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1423
Definition: pathnodes.h:3296
References bms_is_subset(), bms_overlap(), RelOptInfo::direct_lateral_relids, has_legal_joinclause(), JOIN_FULL, SpecialJoinInfo::jointype, lfirst, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, PlaceHolderInfo::ph_eval_at, RelOptInfo::relids, and root.
Referenced by desirable_join(), join_search_one_level(), and make_rels_by_clause_joins().
◆ have_relevant_eclass_joinclause()
| bool have_relevant_eclass_joinclause | ( | PlannerInfo * | root, |
| RelOptInfo * | rel1, | ||
| RelOptInfo * | rel2 | ||
| ) |
Definition at line 3370 of file equivclass.c.
3372{
3373 Bitmapset *matching_ecs;
3375
3376 /*
3377 * Examine only eclasses mentioning both rel1 and rel2.
3378 *
3379 * Note that we do not consider the possibility of an eclass generating
3380 * "join" clauses that mention just one of the rels plus an outer join
3381 * that could be formed from them. Although such clauses must be
3382 * correctly enforced when we form the outer join, they don't seem like
3383 * sufficient reason to prioritize this join over other ones. The join
3384 * ordering rules will force the join to be made when necessary.
3385 */
3387 rel2->relids);
3388
3389 i = -1;
3391 {
3393 i);
3394
3395 /*
3396 * Sanity check that get_common_eclass_indexes gave only ECs
3397 * containing both rels.
3398 */
3401
3402 /*
3403 * Won't generate joinclauses if single-member (this test covers the
3404 * volatile case too)
3405 */
3407 continue;
3408
3409 /*
3410 * We do not need to examine the individual members of the EC, because
3411 * all that we care about is whether each rel overlaps the relids of
3412 * at least one member, and get_common_eclass_indexes() and the single
3413 * member check above are sufficient to prove that. (As with
3414 * have_relevant_joinclause(), it is not necessary that the EC be able
3415 * to form a joinclause relating exactly the two given rels, only that
3416 * it be able to form a joinclause mentioning both, and this will
3417 * surely be true if both of them overlap ec_relids.)
3418 *
3419 * Note we don't test ec_broken; if we did, we'd need a separate code
3420 * path to look through ec_sources. Checking the membership anyway is
3421 * OK as a possibly-overoptimistic heuristic.
3422 *
3423 * We don't test ec_has_const either, even though a const eclass won't
3424 * generate real join clauses. This is because if we had "WHERE a.x =
3425 * b.y and a.x = 42", it is worth considering a join between a and b,
3426 * since the join result is likely to be small even though it'll end
3427 * up being an unqualified nestloop.
3428 */
3429
3430 return true;
3431 }
3432
3433 return false;
3434}
References Assert(), bms_next_member(), bms_overlap(), EquivalenceClass::ec_members, EquivalenceClass::ec_relids, get_common_eclass_indexes(), i, list_length(), list_nth(), RelOptInfo::relids, and root.
Referenced by have_relevant_joinclause().
◆ indexcol_is_bool_constant_for_query()
| bool indexcol_is_bool_constant_for_query | ( | PlannerInfo * | root, |
| IndexOptInfo * | index, | ||
| int | indexcol | ||
| ) |
Definition at line 4304 of file indxpath.c.
4307{
4308 ListCell *lc;
4309
4310 /* If the index isn't boolean, we can't possibly get a match */
4312 return false;
4313
4314 /* Check each restriction clause for the index's rel */
4316 {
4318
4319 /*
4320 * As in match_clause_to_indexcol, never match pseudoconstants to
4321 * indexes. (It might be semantically okay to do so here, but the
4322 * odds of getting a match are negligible, so don't waste the cycles.)
4323 */
4324 if (rinfo->pseudoconstant)
4325 continue;
4326
4327 /* See if we can match the clause's expression to the index column */
4329 return true;
4330 }
4331
4332 return false;
4333}
static IndexClause * match_boolean_index_clause(PlannerInfo *root, RestrictInfo *rinfo, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:2817
References IsBooleanOpfamily(), lfirst, match_boolean_index_clause(), and root.
Referenced by build_index_pathkeys().
◆ init_dummy_sjinfo()
| void init_dummy_sjinfo | ( | SpecialJoinInfo * | sjinfo, |
| Relids | left_relids, | ||
| Relids | right_relids | ||
| ) |
Definition at line 664 of file joinrels.c.
666{
667 sjinfo->type = T_SpecialJoinInfo;
668 sjinfo->min_lefthand = left_relids;
669 sjinfo->min_righthand = right_relids;
670 sjinfo->syn_lefthand = left_relids;
671 sjinfo->syn_righthand = right_relids;
673 sjinfo->ojrelid = 0;
674 sjinfo->commute_above_l = NULL;
675 sjinfo->commute_above_r = NULL;
676 sjinfo->commute_below_l = NULL;
677 sjinfo->commute_below_r = NULL;
678 /* we don't bother trying to make the remaining fields valid */
684}
References SpecialJoinInfo::commute_above_l, SpecialJoinInfo::commute_above_r, SpecialJoinInfo::commute_below_l, SpecialJoinInfo::commute_below_r, JOIN_INNER, SpecialJoinInfo::jointype, SpecialJoinInfo::lhs_strict, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, SpecialJoinInfo::ojrelid, SpecialJoinInfo::semi_can_btree, SpecialJoinInfo::semi_can_hash, SpecialJoinInfo::semi_operators, SpecialJoinInfo::semi_rhs_exprs, SpecialJoinInfo::syn_lefthand, and SpecialJoinInfo::syn_righthand.
Referenced by approx_tuple_count(), build_child_join_sjinfo(), compute_semi_anti_join_factors(), consider_new_or_clause(), and make_join_rel().
◆ initialize_mergeclause_eclasses()
| void initialize_mergeclause_eclasses | ( | PlannerInfo * | root, |
| RestrictInfo * | restrictinfo | ||
| ) |
Definition at line 1463 of file pathkeys.c.
1464{
1466 Oid lefttype,
1467 righttype;
1468
1469 /* Should be a mergeclause ... */
1471 /* ... with links not yet set */
1472 Assert(restrictinfo->left_ec == NULL);
1473 Assert(restrictinfo->right_ec == NULL);
1474
1475 /* Need the declared input types of the operator */
1477
1478 /* Find or create a matching EquivalenceClass for each side */
1479 restrictinfo->left_ec =
1482 restrictinfo->mergeopfamilies,
1483 lefttype,
1484 ((OpExpr *) clause)->inputcollid,
1485 0,
1486 NULL,
1487 true);
1488 restrictinfo->right_ec =
1491 restrictinfo->mergeopfamilies,
1492 righttype,
1493 ((OpExpr *) clause)->inputcollid,
1494 0,
1495 NULL,
1496 true);
1497}
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1525
Definition: primnodes.h:846
References Assert(), RestrictInfo::clause, get_eclass_for_sort_expr(), get_leftop(), get_rightop(), NIL, op_input_types(), and root.
Referenced by distribute_qual_to_rels().
◆ is_redundant_derived_clause()
| bool is_redundant_derived_clause | ( | RestrictInfo * | rinfo, |
| List * | clauselist | ||
| ) |
Definition at line 3550 of file equivclass.c.
3551{
3552 EquivalenceClass *parent_ec = rinfo->parent_ec;
3553 ListCell *lc;
3554
3555 /* Fail if it's not a potentially-redundant clause from some EC */
3556 if (parent_ec == NULL)
3557 return false;
3558
3559 foreach(lc, clauselist)
3560 {
3562
3563 if (otherrinfo->parent_ec == parent_ec)
3564 return true;
3565 }
3566
3567 return false;
3568}
References lfirst.
Referenced by create_tidscan_plan().
◆ is_redundant_with_indexclauses()
| bool is_redundant_with_indexclauses | ( | RestrictInfo * | rinfo, |
| List * | indexclauses | ||
| ) |
Definition at line 3577 of file equivclass.c.
3578{
3579 EquivalenceClass *parent_ec = rinfo->parent_ec;
3580 ListCell *lc;
3581
3582 foreach(lc, indexclauses)
3583 {
3586
3587 /* If indexclause is lossy, it won't enforce the condition exactly */
3589 continue;
3590
3591 /* Match if it's same clause (pointer equality should be enough) */
3592 if (rinfo == otherrinfo)
3593 return true;
3594 /* Match if derived from same EC */
3595 if (parent_ec && otherrinfo->parent_ec == parent_ec)
3596 return true;
3597
3598 /*
3599 * No need to look at the derived clauses in iclause->indexquals; they
3600 * couldn't match if the parent clause didn't.
3601 */
3602 }
3603
3604 return false;
3605}
Definition: pathnodes.h:2002
References lfirst_node, IndexClause::lossy, and IndexClause::rinfo.
Referenced by create_indexscan_plan(), extract_nonindex_conditions(), and has_indexed_join_quals().
◆ join_search_one_level()
| void join_search_one_level | ( | PlannerInfo * | root, |
| int | level | ||
| ) |
Definition at line 78 of file joinrels.c.
79{
81 ListCell *r;
82 int k;
83
85
86 /* Set join_cur_level so that new joinrels are added to proper list */
87 root->join_cur_level = level;
88
89 /*
90 * First, consider left-sided and right-sided plans, in which rels of
91 * exactly level-1 member relations are joined against initial relations.
92 * We prefer to join using join clauses, but if we find a rel of level-1
93 * members that has no join clauses, we will generate Cartesian-product
94 * joins against all initial rels not already contained in it.
95 */
96 foreach(r, joinrels[level - 1])
97 {
99
102 {
103 int first_rel;
104
105 /*
106 * There are join clauses or join order restrictions relevant to
107 * this rel, so consider joins between this rel and (only) those
108 * initial rels it is linked to by a clause or restriction.
109 *
110 * At level 2 this condition is symmetric, so there is no need to
111 * look at initial rels before this one in the list; we already
112 * considered such joins when we were at the earlier rel. (The
113 * mirror-image joins are handled automatically by make_join_rel.)
114 * In later passes (level > 2), we join rels of the previous level
115 * to each initial rel they don't already include but have a join
116 * clause or restriction with.
117 */
118 if (level == 2) /* consider remaining initial rels */
119 first_rel = foreach_current_index(r) + 1;
120 else
121 first_rel = 0;
122
124 }
125 else
126 {
127 /*
128 * Oops, we have a relation that is not joined to any other
129 * relation, either directly or by join-order restrictions.
130 * Cartesian product time.
131 *
132 * We consider a cartesian product with each not-already-included
133 * initial rel, whether it has other join clauses or not. At
134 * level 2, if there are two or more clauseless initial rels, we
135 * will redundantly consider joining them in both directions; but
136 * such cases aren't common enough to justify adding complexity to
137 * avoid the duplicated effort.
138 */
140 old_rel,
141 joinrels[1]);
142 }
143 }
144
145 /*
146 * Now, consider "bushy plans" in which relations of k initial rels are
147 * joined to relations of level-k initial rels, for 2 <= k <= level-2.
148 *
149 * We only consider bushy-plan joins for pairs of rels where there is a
150 * suitable join clause (or join order restriction), in order to avoid
151 * unreasonable growth of planning time.
152 */
153 for (k = 2;; k++)
154 {
155 int other_level = level - k;
156
157 /*
158 * Since make_join_rel(x, y) handles both x,y and y,x cases, we only
159 * need to go as far as the halfway point.
160 */
161 if (k > other_level)
162 break;
163
164 foreach(r, joinrels[k])
165 {
167 int first_rel;
168 ListCell *r2;
169
170 /*
171 * We can ignore relations without join clauses here, unless they
172 * participate in join-order restrictions --- then we might have
173 * to force a bushy join plan.
174 */
177 continue;
178
179 if (k == other_level) /* only consider remaining rels */
180 first_rel = foreach_current_index(r) + 1;
181 else
182 first_rel = 0;
183
184 for_each_from(r2, joinrels[other_level], first_rel)
185 {
187
189 {
190 /*
191 * OK, we can build a rel of the right level from this
192 * pair of rels. Do so if there is at least one relevant
193 * join clause or join order restriction.
194 */
197 {
199 }
200 }
201 }
202 }
203 }
204
205 /*----------
206 * Last-ditch effort: if we failed to find any usable joins so far, force
207 * a set of cartesian-product joins to be generated. This handles the
208 * special case where all the available rels have join clauses but we
209 * cannot use any of those clauses yet. This can only happen when we are
210 * considering a join sub-problem (a sub-joinlist) and all the rels in the
211 * sub-problem have only join clauses with rels outside the sub-problem.
212 * An example is
213 *
214 * SELECT ... FROM a INNER JOIN b ON TRUE, c, d, ...
215 * WHERE a.w = c.x and b.y = d.z;
216 *
217 * If the "a INNER JOIN b" sub-problem does not get flattened into the
218 * upper level, we must be willing to make a cartesian join of a and b;
219 * but the code above will not have done so, because it thought that both
220 * a and b have joinclauses. We consider only left-sided and right-sided
221 * cartesian joins in this case (no bushy).
222 *----------
223 */
225 {
226 /*
227 * This loop is just like the first one, except we always call
228 * make_rels_by_clauseless_joins().
229 */
230 foreach(r, joinrels[level - 1])
231 {
233
235 old_rel,
236 joinrels[1]);
237 }
238
239 /*----------
240 * When special joins are involved, there may be no legal way
241 * to make an N-way join for some values of N. For example consider
242 *
243 * SELECT ... FROM t1 WHERE
244 * x IN (SELECT ... FROM t2,t3 WHERE ...) AND
245 * y IN (SELECT ... FROM t4,t5 WHERE ...)
246 *
247 * We will flatten this query to a 5-way join problem, but there are
248 * no 4-way joins that join_is_legal() will consider legal. We have
249 * to accept failure at level 4 and go on to discover a workable
250 * bushy plan at level 5.
251 *
252 * However, if there are no special joins and no lateral references
253 * then join_is_legal() should never fail, and so the following sanity
254 * check is useful.
255 *----------
256 */
259 !root->hasLateralRTEs)
261 }
262}
bool have_relevant_joinclause(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joininfo.c:39
static void make_rels_by_clauseless_joins(PlannerInfo *root, RelOptInfo *old_rel, List *other_rels)
Definition: joinrels.c:319
RelOptInfo * make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:699
bool have_join_order_restriction(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:1254
static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1367
static void make_rels_by_clause_joins(PlannerInfo *root, RelOptInfo *old_rel, List *other_rels, int first_rel_idx)
Definition: joinrels.c:285
References Assert(), bms_overlap(), elog, ERROR, for_each_from, foreach_current_index, RelOptInfo::has_eclass_joins, has_join_restriction(), have_join_order_restriction(), have_relevant_joinclause(), RelOptInfo::joininfo, lfirst, make_join_rel(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), NIL, RelOptInfo::relids, and root.
Referenced by standard_join_search().
◆ make_canonical_pathkey()
| PathKey * make_canonical_pathkey | ( | PlannerInfo * | root, |
| EquivalenceClass * | eclass, | ||
| Oid | opfamily, | ||
| CompareType | cmptype, | ||
| bool | nulls_first | ||
| ) |
Definition at line 56 of file pathkeys.c.
59{
60 PathKey *pk;
61 ListCell *lc;
62 MemoryContext oldcontext;
63
64 /* Can't make canonical pathkeys if the set of ECs might still change */
67
68 /* The passed eclass might be non-canonical, so chase up to the top */
71
73 {
76 opfamily == pk->pk_opfamily &&
77 cmptype == pk->pk_cmptype &&
78 nulls_first == pk->pk_nulls_first)
79 return pk;
80 }
81
82 /*
83 * Be sure canonical pathkeys are allocated in the main planning context.
84 * Not an issue in normal planning, but it is for GEQO.
85 */
87
89 pk->pk_eclass = eclass;
90 pk->pk_opfamily = opfamily;
91 pk->pk_cmptype = cmptype;
92 pk->pk_nulls_first = nulls_first;
93
95
96 MemoryContextSwitchTo(oldcontext);
97
98 return pk;
99}
References eclass(), elog, ERROR, lappend(), lfirst, makeNode, MemoryContextSwitchTo(), PathKey::pk_cmptype, PathKey::pk_nulls_first, PathKey::pk_opfamily, and root.
Referenced by convert_subquery_pathkeys(), get_useful_pathkeys_for_relation(), make_inner_pathkeys_for_merge(), make_pathkey_from_sortinfo(), and select_outer_pathkeys_for_merge().
◆ make_inner_pathkeys_for_merge()
| List * make_inner_pathkeys_for_merge | ( | PlannerInfo * | root, |
| List * | mergeclauses, | ||
| List * | outer_pathkeys | ||
| ) |
Definition at line 1858 of file pathkeys.c.
1861{
1863 EquivalenceClass *lastoeclass;
1864 PathKey *opathkey;
1865 ListCell *lc;
1866 ListCell *lop;
1867
1868 lastoeclass = NULL;
1869 opathkey = NULL;
1870 lop = list_head(outer_pathkeys);
1871
1872 foreach(lc, mergeclauses)
1873 {
1875 EquivalenceClass *oeclass;
1876 EquivalenceClass *ieclass;
1877 PathKey *pathkey;
1878
1880
1881 if (rinfo->outer_is_left)
1882 {
1883 oeclass = rinfo->left_ec;
1884 ieclass = rinfo->right_ec;
1885 }
1886 else
1887 {
1888 oeclass = rinfo->right_ec;
1889 ieclass = rinfo->left_ec;
1890 }
1891
1892 /* outer eclass should match current or next pathkeys */
1893 /* we check this carefully for debugging reasons */
1894 if (oeclass != lastoeclass)
1895 {
1896 if (!lop)
1899 lop = lnext(outer_pathkeys, lop);
1900 lastoeclass = opathkey->pk_eclass;
1901 if (oeclass != lastoeclass)
1903 }
1904
1905 /*
1906 * Often, we'll have same EC on both sides, in which case the outer
1907 * pathkey is also canonical for the inner side, and we can skip a
1908 * useless search.
1909 */
1910 if (ieclass == oeclass)
1911 pathkey = opathkey;
1912 else
1914 ieclass,
1915 opathkey->pk_opfamily,
1916 opathkey->pk_cmptype,
1917 opathkey->pk_nulls_first);
1918
1919 /*
1920 * Don't generate redundant pathkeys (which can happen if multiple
1921 * mergeclauses refer to the same EC). Because we do this, the output
1922 * pathkey list isn't necessarily ordered like the mergeclauses, which
1923 * complicates life for create_mergejoin_plan(). But if we didn't,
1924 * we'd have a noncanonical sort key list, which would be bad; for one
1925 * reason, it certainly wouldn't match any available sort order for
1926 * the input relation.
1927 */
1929 pathkeys = lappend(pathkeys, pathkey);
1930 }
1931
1932 return pathkeys;
1933}
References elog, ERROR, lappend(), lfirst, list_head(), lnext(), make_canonical_pathkey(), NIL, pathkey_is_redundant(), PathKey::pk_cmptype, PathKey::pk_nulls_first, PathKey::pk_opfamily, root, and update_mergeclause_eclasses().
Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().
◆ make_join_rel()
| RelOptInfo * make_join_rel | ( | PlannerInfo * | root, |
| RelOptInfo * | rel1, | ||
| RelOptInfo * | rel2 | ||
| ) |
Definition at line 699 of file joinrels.c.
700{
701 Relids joinrelids;
702 SpecialJoinInfo *sjinfo;
703 bool reversed;
705 SpecialJoinInfo sjinfo_data;
706 RelOptInfo *joinrel;
707 List *restrictlist;
708
709 /* We should never try to join two overlapping sets of rels. */
711
712 /* Construct Relids set that identifies the joinrel (without OJ as yet). */
714
715 /* Check validity and determine join type. */
717 &sjinfo, &reversed))
718 {
719 /* invalid join path */
720 bms_free(joinrelids);
721 return NULL;
722 }
723
724 /*
725 * Add outer join relid(s) to form the canonical relids. Any added outer
726 * joins besides sjinfo itself are appended to pushed_down_joins.
727 */
729 &pushed_down_joins);
730
731 /* Swap rels if needed to match the join info. */
732 if (reversed)
733 {
734 RelOptInfo *trel = rel1;
735
736 rel1 = rel2;
737 rel2 = trel;
738 }
739
740 /*
741 * If it's a plain inner join, then we won't have found anything in
742 * join_info_list. Make up a SpecialJoinInfo so that selectivity
743 * estimation functions will know what's being joined.
744 */
745 if (sjinfo == NULL)
746 {
747 sjinfo = &sjinfo_data;
749 }
750
751 /*
752 * Find or build the join RelOptInfo, and compute the restrictlist that
753 * goes with this particular joining.
754 */
756 sjinfo, pushed_down_joins,
757 &restrictlist);
758
759 /*
760 * If we've already proven this join is empty, we needn't consider any
761 * more paths for it.
762 */
764 {
765 bms_free(joinrelids);
766 return joinrel;
767 }
768
769 /* Build a grouped join relation for 'joinrel' if possible. */
771 restrictlist);
772
773 /* Add paths to the join relation. */
775 restrictlist);
776
777 bms_free(joinrelids);
778
779 return joinrel;
780}
static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, SpecialJoinInfo *sjinfo, List *restrictlist)
Definition: joinrels.c:1072
void init_dummy_sjinfo(SpecialJoinInfo *sjinfo, Relids left_relids, Relids right_relids)
Definition: joinrels.c:664
static void make_grouped_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, SpecialJoinInfo *sjinfo, List *restrictlist)
Definition: joinrels.c:916
static bool join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, Relids joinrelids, SpecialJoinInfo **sjinfo_p, bool *reversed_p)
Definition: joinrels.c:355
RelOptInfo * build_join_rel(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo, List *pushed_down_joins, List **restrictlist_ptr)
Definition: relnode.c:780
References add_outer_joins_to_relids(), Assert(), bms_free(), bms_overlap(), bms_union(), build_join_rel(), init_dummy_sjinfo(), is_dummy_rel(), join_is_legal(), make_grouped_join_rel(), NIL, populate_joinrel_with_paths(), RelOptInfo::relids, and root.
Referenced by join_search_one_level(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), and merge_clump().
◆ make_one_rel()
| RelOptInfo * make_one_rel | ( | PlannerInfo * | root, |
| List * | joinlist | ||
| ) |
Definition at line 177 of file allpaths.c.
178{
179 RelOptInfo *rel;
180 Index rti;
181 double total_pages;
182
183 /* Mark base rels as to whether we care about fast-start plans */
185
186 /*
187 * Compute size estimates and consider_parallel flags for each base rel.
188 */
190
191 /*
192 * Build grouped relations for simple rels (i.e., base or "other" member
193 * relations) where possible.
194 */
196
197 /*
198 * We should now have size estimates for every actual table involved in
199 * the query, and we also know which if any have been deleted from the
200 * query by join removal, pruned by partition pruning, or eliminated by
201 * constraint exclusion. So we can now compute total_table_pages.
202 *
203 * Note that appendrels are not double-counted here, even though we don't
204 * bother to distinguish RelOptInfos for appendrel parents, because the
205 * parents will have pages = 0.
206 *
207 * XXX if a table is self-joined, we will count it once per appearance,
208 * which perhaps is the wrong thing ... but that's not completely clear,
209 * and detecting self-joins here is difficult, so ignore it for now.
210 */
211 total_pages = 0;
213 {
215
216 /* there may be empty slots corresponding to non-baserel RTEs */
217 if (brel == NULL)
218 continue;
219
221
223 continue;
224
226 total_pages += (double) brel->pages;
227 }
228 root->total_table_pages = total_pages;
229
230 /*
231 * Generate access paths for each base rel.
232 */
234
235 /*
236 * Generate access paths for the entire join tree.
237 */
239
240 /*
241 * The result should join all and only the query's base + outer-join rels.
242 */
244
245 return rel;
246}
static void set_base_rel_consider_startup(PlannerInfo *root)
Definition: allpaths.c:259
static void set_base_rel_pathlists(PlannerInfo *root)
Definition: allpaths.c:378
static RelOptInfo * make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
Definition: allpaths.c:3780
static void setup_simple_grouped_rels(PlannerInfo *root)
Definition: allpaths.c:344
References Assert(), bms_equal(), IS_DUMMY_REL, IS_SIMPLE_REL, make_rel_from_joinlist(), RelOptInfo::pages, RelOptInfo::relid, RelOptInfo::relids, root, set_base_rel_consider_startup(), set_base_rel_pathlists(), set_base_rel_sizes(), and setup_simple_grouped_rels().
Referenced by query_planner().
◆ make_pathkeys_for_sortclauses()
| List * make_pathkeys_for_sortclauses | ( | PlannerInfo * | root, |
| List * | sortclauses, | ||
| List * | tlist | ||
| ) |
Definition at line 1336 of file pathkeys.c.
1339{
1340 List *result;
1341 bool sortable;
1342
1344 &sortclauses,
1345 tlist,
1346 false,
1347 false,
1348 &sortable,
1349 false);
1350 /* It's caller error if not all clauses were sortable */
1351 Assert(sortable);
1352 return result;
1353}
List * make_pathkeys_for_sortclauses_extended(PlannerInfo *root, List **sortclauses, List *tlist, bool remove_redundant, bool remove_group_rtindex, bool *sortable, bool set_ec_sortref)
Definition: pathkeys.c:1381
References Assert(), make_pathkeys_for_sortclauses_extended(), and root.
Referenced by adjust_group_pathkeys_for_groupagg(), create_unique_paths(), generate_grouped_paths(), generate_nonunion_paths(), generate_union_paths(), grouping_planner(), make_pathkeys_for_window(), minmax_qp_callback(), and standard_qp_callback().
◆ make_pathkeys_for_sortclauses_extended()
| List * make_pathkeys_for_sortclauses_extended | ( | PlannerInfo * | root, |
| List ** | sortclauses, | ||
| List * | tlist, | ||
| bool | remove_redundant, | ||
| bool | remove_group_rtindex, | ||
| bool * | sortable, | ||
| bool | set_ec_sortref | ||
| ) |
Definition at line 1381 of file pathkeys.c.
1388{
1390 ListCell *l;
1391
1392 *sortable = true;
1393 foreach(l, *sortclauses)
1394 {
1396 Expr *sortkey;
1397 PathKey *pathkey;
1398
1401 {
1402 *sortable = false;
1403 continue;
1404 }
1405 if (remove_group_rtindex)
1406 {
1408 sortkey = (Expr *)
1411 NULL);
1412 }
1414 sortkey,
1415 sortcl->sortop,
1416 sortcl->reverse_sort,
1417 sortcl->nulls_first,
1418 sortcl->tleSortGroupRef,
1419 true);
1420 if (pathkey->pk_eclass->ec_sortref == 0 && set_ec_sortref)
1421 {
1422 /*
1423 * Copy the sortref if it hasn't been set yet. That may happen if
1424 * the EquivalenceClass was constructed from a WHERE clause, i.e.
1425 * it doesn't have a target reference at all.
1426 */
1427 pathkey->pk_eclass->ec_sortref = sortcl->tleSortGroupRef;
1428 }
1429
1430 /* Canonical form eliminates redundant ordering keys */
1432 pathkeys = lappend(pathkeys, pathkey);
1433 else if (remove_redundant)
1434 *sortclauses = foreach_delete_current(*sortclauses, l);
1435 }
1436 return pathkeys;
1437}
static PathKey * make_pathkey_from_sortop(PlannerInfo *root, Expr *expr, Oid ordering_op, bool reverse_sort, bool nulls_first, Index sortref, bool create_it)
Definition: pathkeys.c:256
Node * remove_nulling_relids(Node *node, const Bitmapset *removable_relids, const Bitmapset *except_relids)
Definition: rewriteManip.c:1328
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:379
References Assert(), bms_make_singleton(), foreach_delete_current, get_sortgroupclause_expr(), lappend(), lfirst, make_pathkey_from_sortop(), NIL, SortGroupClause::nulls_first, OidIsValid, pathkey_is_redundant(), remove_nulling_relids(), SortGroupClause::reverse_sort, root, SortGroupClause::sortop, and SortGroupClause::tleSortGroupRef.
Referenced by make_pathkeys_for_sortclauses(), make_pathkeys_for_window(), and standard_qp_callback().
◆ mark_dummy_rel()
| void mark_dummy_rel | ( | RelOptInfo * | rel | ) |
Definition at line 1513 of file joinrels.c.
1514{
1515 MemoryContext oldcontext;
1516
1517 /* Already marked? */
1519 return;
1520
1521 /* No, so choose correct context to make the dummy path in */
1523
1524 /* Set dummy size estimate */
1525 rel->rows = 0;
1526
1527 /* Evict any previously chosen paths */
1530
1531 /* Set up the dummy path */
1534 0, false, -1));
1535
1536 /* Set or update cheapest_total_path and related fields */
1537 set_cheapest(rel);
1538
1539 MemoryContextSwitchTo(oldcontext);
1540}
References add_path(), create_append_path(), GetMemoryChunkContext(), is_dummy_rel(), RelOptInfo::lateral_relids, MemoryContextSwitchTo(), NIL, RelOptInfo::partial_pathlist, RelOptInfo::pathlist, RelOptInfo::rows, and set_cheapest().
Referenced by build_setop_child_paths(), build_simple_rel(), generate_grouped_paths(), generate_nonunion_paths(), generate_partitionwise_join_paths(), generate_union_paths(), and populate_joinrel_with_paths().
◆ match_eclasses_to_foreign_key_col()
| EquivalenceClass * match_eclasses_to_foreign_key_col | ( | PlannerInfo * | root, |
| ForeignKeyOptInfo * | fkinfo, | ||
| int | colno | ||
| ) |
Definition at line 2710 of file equivclass.c.
2713{
2715 AttrNumber var1attno = fkinfo->conkey[colno];
2717 AttrNumber var2attno = fkinfo->confkey[colno];
2718 Oid eqop = fkinfo->conpfeqop[colno];
2722 Bitmapset *matching_ecs;
2724
2725 /* Consider only eclasses mentioning both relations */
2730 rel2->eclass_indexes);
2731
2732 i = -1;
2734 {
2736 i);
2737 EquivalenceMember *item1_em = NULL;
2738 EquivalenceMember *item2_em = NULL;
2739 ListCell *lc2;
2740
2741 /* Never match to a volatile EC */
2743 continue;
2744
2745 /*
2746 * It's okay to consider "broken" ECs here, see exprs_known_equal.
2747 * Ignore children here.
2748 */
2750 {
2752 Var *var;
2753
2754 /* Child members should not exist in ec_members */
2756
2757 /* EM must be a Var, possibly with RelabelType */
2762 continue;
2763
2764 /* Match? */
2766 item1_em = em;
2768 item2_em = em;
2769
2770 /* Have we found both PK and FK column in this EC? */
2771 if (item1_em && item2_em)
2772 {
2773 /*
2774 * Succeed if eqop matches EC's opfamilies. We could test
2775 * this before scanning the members, but it's probably cheaper
2776 * to test for member matches first.
2777 */
2779 opfamilies = get_mergejoin_opfamilies(eqop);
2781 {
2782 fkinfo->eclass[colno] = ec;
2783 fkinfo->fk_eclass_member[colno] = item2_em;
2784 return ec;
2785 }
2786 /* Otherwise, done with this EC, move on to the next */
2787 break;
2788 }
2789 }
2790 }
2791 return NULL;
2792}
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:292
struct EquivalenceClass * eclass[INDEX_MAX_KEYS]
Definition: pathnodes.h:1398
struct EquivalenceMember * fk_eclass_member[INDEX_MAX_KEYS]
Definition: pathnodes.h:1400
References Assert(), bms_intersect(), bms_next_member(), ForeignKeyOptInfo::con_relid, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, ForeignKeyOptInfo::eclass, RelOptInfo::eclass_indexes, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, equal(), ForeignKeyOptInfo::fk_eclass_member, get_mergejoin_opfamilies(), i, IS_SIMPLE_REL, IsA, lfirst, list_nth(), NIL, ForeignKeyOptInfo::ref_relid, root, Var::varattno, Var::varno, and while().
Referenced by match_foreign_keys_to_quals().
◆ match_index_to_operand()
| bool match_index_to_operand | ( | Node * | operand, |
| int | indexcol, | ||
| IndexOptInfo * | index | ||
| ) |
Definition at line 4355 of file indxpath.c.
4358{
4359 int indkey;
4360
4361 /*
4362 * Ignore any RelabelType node above the operand. This is needed to be
4363 * able to apply indexscanning in binary-compatible-operator cases. Note:
4364 * we can assume there is at most one RelabelType node;
4365 * eval_const_expressions() will have simplified if more than one.
4366 */
4369
4370 indkey = index->indexkeys[indexcol];
4371 if (indkey != 0)
4372 {
4373 /*
4374 * Simple index column; operand must be a matching Var.
4375 */
4378 indkey == ((Var *) operand)->varattno &&
4379 ((Var *) operand)->varnullingrels == NULL)
4380 return true;
4381 }
4382 else
4383 {
4384 /*
4385 * Index expression; find the correct expression. (This search could
4386 * be avoided, at the cost of complicating all the callers of this
4387 * routine; doesn't seem worth it.)
4388 */
4389 ListCell *indexpr_item;
4391 Node *indexkey;
4392
4395 {
4397 {
4398 if (indexpr_item == NULL)
4401 }
4402 }
4403 if (indexpr_item == NULL)
4406
4407 /*
4408 * Does it match the operand? Again, strip any relabeling.
4409 */
4412
4414 return true;
4415 }
4416
4417 return false;
4418}
References arg, elog, equal(), ERROR, i, IsA, lfirst, list_head(), and lnext().
Referenced by ec_member_matches_indexcol(), expand_indexqual_rowcompare(), get_actual_variable_range(), group_similar_or_args(), match_boolean_index_clause(), match_clause_to_indexcol(), match_clause_to_ordering_op(), match_funcclause_to_indexcol(), match_opclause_to_indexcol(), match_orclause_to_indexcol(), match_rowcompare_to_indexcol(), match_saopclause_to_indexcol(), and relation_has_unique_index_for().
◆ pathkeys_contained_in()
Definition at line 343 of file pathkeys.c.
344{
346 {
349 return true;
350 default:
351 break;
352 }
353 return false;
354}
References compare_pathkeys(), PATHKEYS_BETTER2, and PATHKEYS_EQUAL.
Referenced by add_paths_with_pathkeys_for_rel(), adjust_foreign_grouping_path_cost(), consider_groupingsets_paths(), create_gather_merge_path(), create_gather_merge_plan(), create_mergejoin_plan(), generate_mergejoin_paths(), generate_nonunion_paths(), generate_orderedappend_paths(), get_cheapest_fractional_path_for_pathkeys(), get_cheapest_path_for_pathkeys(), get_useful_group_keys_orderings(), GetExistingLocalJoinPath(), initial_cost_mergejoin(), try_mergejoin_path(), and try_partial_mergejoin_path().
◆ pathkeys_count_contained_in()
Definition at line 558 of file pathkeys.c.
559{
560 int n = 0;
561 ListCell *key1,
562 *key2;
563
564 /*
565 * See if we can avoiding looping through both lists. This optimization
566 * gains us several percent in planning time in a worst-case test.
567 */
568 if (keys1 == keys2)
569 {
570 *n_common = list_length(keys1);
571 return true;
572 }
574 {
575 *n_common = 0;
576 return true;
577 }
579 {
580 *n_common = 0;
581 return false;
582 }
583
584 /*
585 * If both lists are non-empty, iterate through both to find out how many
586 * items are shared.
587 */
588 forboth(key1, keys1, key2, keys2)
589 {
592
593 if (pathkey1 != pathkey2)
594 {
595 *n_common = n;
596 return false;
597 }
598 n++;
599 }
600
601 /* If we ended with a null value, then we've processed the whole list. */
602 *n_common = n;
603 return (key1 == NULL);
604}
References forboth, lfirst, list_length(), and NIL.
Referenced by build_setop_child_paths(), cost_append(), count_common_leading_pathkeys_ordered(), create_append_plan(), create_final_unique_paths(), create_merge_append_path(), create_merge_append_plan(), create_one_window_path(), create_ordered_paths(), create_partial_unique_paths(), create_window_paths(), gather_grouping_paths(), generate_grouped_paths(), generate_useful_gather_paths(), GetExistingLocalJoinPath(), make_ordered_path(), try_mergejoin_path(), and try_partial_mergejoin_path().
◆ process_equivalence()
| bool process_equivalence | ( | PlannerInfo * | root, |
| RestrictInfo ** | p_restrictinfo, | ||
| JoinDomain * | jdomain | ||
| ) |
Definition at line 179 of file equivclass.c.
182{
183 RestrictInfo *restrictinfo = *p_restrictinfo;
185 Oid opno,
186 collation,
187 item1_type,
188 item2_type;
189 Expr *item1;
190 Expr *item2;
191 Relids item1_relids,
192 item2_relids;
193 List *opfamilies;
194 EquivalenceClass *ec1,
195 *ec2;
196 EquivalenceMember *em1,
197 *em2;
198 ListCell *lc1;
199 int ec2_idx;
200
201 /* Should not already be marked as having generated an eclass */
202 Assert(restrictinfo->left_ec == NULL);
203 Assert(restrictinfo->right_ec == NULL);
204
205 /* Reject if it is potentially postponable by security considerations */
207 return false;
208
209 /* Extract info from given clause */
211 opno = ((OpExpr *) clause)->opno;
212 collation = ((OpExpr *) clause)->inputcollid;
215 item1_relids = restrictinfo->left_relids;
216 item2_relids = restrictinfo->right_relids;
217
218 /*
219 * Ensure both input expressions expose the desired collation (their types
220 * should be OK already); see comments for canonicalize_ec_expression.
221 */
222 item1 = canonicalize_ec_expression(item1,
224 collation);
225 item2 = canonicalize_ec_expression(item2,
227 collation);
228
229 /*
230 * Clauses of the form X=X cannot be translated into EquivalenceClasses.
231 * We'd either end up with a single-entry EC, losing the knowledge that
232 * the clause was present at all, or else make an EC with duplicate
233 * entries, causing other issues.
234 */
236 {
237 /*
238 * If the operator is strict, then the clause can be treated as just
239 * "X IS NOT NULL". (Since we know we are considering a top-level
240 * qual, we can ignore the difference between FALSE and NULL results.)
241 * It's worth making the conversion because we'll typically get a much
242 * better selectivity estimate than we would for X=X.
243 *
244 * If the operator is not strict, we can't be sure what it will do
245 * with NULLs, so don't attempt to optimize it.
246 */
249 {
251
252 ntest->arg = item1;
254 ntest->argisrow = false; /* correct even if composite arg */
255 ntest->location = -1;
256
257 *p_restrictinfo =
259 (Expr *) ntest,
260 restrictinfo->is_pushed_down,
261 restrictinfo->has_clone,
262 restrictinfo->is_clone,
263 restrictinfo->pseudoconstant,
264 restrictinfo->security_level,
265 NULL,
266 restrictinfo->incompatible_relids,
267 restrictinfo->outer_relids);
268 }
269 return false;
270 }
271
272 /*
273 * We use the declared input types of the operator, not exprType() of the
274 * inputs, as the nominal datatypes for opfamily lookup. This presumes
275 * that btree operators are always registered with amoplefttype and
276 * amoprighttype equal to their declared input types. We will need this
277 * info anyway to build EquivalenceMember nodes, and by extracting it now
278 * we can use type comparisons to short-circuit some equal() tests.
279 */
280 op_input_types(opno, &item1_type, &item2_type);
281
282 opfamilies = restrictinfo->mergeopfamilies;
283
284 /*
285 * Sweep through the existing EquivalenceClasses looking for matches to
286 * item1 and item2. These are the possible outcomes:
287 *
288 * 1. We find both in the same EC. The equivalence is already known, so
289 * there's nothing to do.
290 *
291 * 2. We find both in different ECs. Merge the two ECs together.
292 *
293 * 3. We find just one. Add the other to its EC.
294 *
295 * 4. We find neither. Make a new, two-entry EC.
296 *
297 * Note: since all ECs are built through this process or the similar
298 * search in get_eclass_for_sort_expr(), it's impossible that we'd match
299 * an item in more than one existing nonvolatile EC. So it's okay to stop
300 * at the first match.
301 */
302 ec1 = ec2 = NULL;
303 em1 = em2 = NULL;
304 ec2_idx = -1;
306 {
308 ListCell *lc2;
309
310 /* Never match to a volatile EC */
312 continue;
313
314 /*
315 * The collation has to match; check this first since it's cheaper
316 * than the opfamily comparison.
317 */
319 continue;
320
321 /*
322 * A "match" requires matching sets of btree opfamilies. Use of
323 * equal() for this test has implications discussed in the comments
324 * for get_mergejoin_opfamilies().
325 */
327 continue;
328
329 /* We don't expect any children yet */
331
333 {
335
336 /* Child members should not exist in ec_members */
338
339 /*
340 * Match constants only within the same JoinDomain (see
341 * optimizer/README).
342 */
344 continue;
345
346 if (!ec1 &&
347 item1_type == cur_em->em_datatype &&
349 {
350 ec1 = cur_ec;
351 em1 = cur_em;
352 if (ec2)
353 break;
354 }
355
356 if (!ec2 &&
357 item2_type == cur_em->em_datatype &&
359 {
360 ec2 = cur_ec;
361 ec2_idx = foreach_current_index(lc1);
362 em2 = cur_em;
363 if (ec1)
364 break;
365 }
366 }
367
368 if (ec1 && ec2)
369 break;
370 }
371
372 /* Sweep finished, what did we find? */
373
374 if (ec1 && ec2)
375 {
376 /* If case 1, nothing to do, except add to sources */
377 if (ec1 == ec2)
378 {
381 restrictinfo->security_level);
383 restrictinfo->security_level);
384 /* mark the RI as associated with this eclass */
385 restrictinfo->left_ec = ec1;
386 restrictinfo->right_ec = ec1;
387 /* mark the RI as usable with this pair of EMs */
388 restrictinfo->left_em = em1;
389 restrictinfo->right_em = em2;
390 return true;
391 }
392
393 /*
394 * Case 2: need to merge ec1 and ec2. This should never happen after
395 * the ECs have reached canonical state; otherwise, pathkeys could be
396 * rendered non-canonical by the merge, and relation eclass indexes
397 * would get broken by removal of an eq_classes list entry.
398 */
401
402 /*
403 * We add ec2's items to ec1, then set ec2's ec_merged link to point
404 * to ec1 and remove ec2 from the eq_classes list. We cannot simply
405 * delete ec2 because that could leave dangling pointers in existing
406 * PathKeys. We leave it behind with a link so that the merged EC can
407 * be found.
408 */
411
412 /*
413 * Appends ec2's derived clauses to ec1->ec_derives_list and adds them
414 * to ec1->ec_derives_hash if present.
415 */
419 /* can't need to set has_volatile */
421 ec2->ec_min_security);
423 ec2->ec_max_security);
424 ec2->ec_merged = ec1;
426 /* just to avoid debugging confusion w/ dangling pointers: */
429 ec_clear_derived_clauses(ec2);
430 ec2->ec_relids = NULL;
433 restrictinfo->security_level);
435 restrictinfo->security_level);
436 /* mark the RI as associated with this eclass */
437 restrictinfo->left_ec = ec1;
438 restrictinfo->right_ec = ec1;
439 /* mark the RI as usable with this pair of EMs */
440 restrictinfo->left_em = em1;
441 restrictinfo->right_em = em2;
442 }
443 else if (ec1)
444 {
445 /* Case 3: add item2 to ec1 */
446 em2 = add_eq_member(ec1, item2, item2_relids,
447 jdomain, item2_type);
450 restrictinfo->security_level);
452 restrictinfo->security_level);
453 /* mark the RI as associated with this eclass */
454 restrictinfo->left_ec = ec1;
455 restrictinfo->right_ec = ec1;
456 /* mark the RI as usable with this pair of EMs */
457 restrictinfo->left_em = em1;
458 restrictinfo->right_em = em2;
459 }
460 else if (ec2)
461 {
462 /* Case 3: add item1 to ec2 */
463 em1 = add_eq_member(ec2, item1, item1_relids,
464 jdomain, item1_type);
467 restrictinfo->security_level);
469 restrictinfo->security_level);
470 /* mark the RI as associated with this eclass */
471 restrictinfo->left_ec = ec2;
472 restrictinfo->right_ec = ec2;
473 /* mark the RI as usable with this pair of EMs */
474 restrictinfo->left_em = em1;
475 restrictinfo->right_em = em2;
476 }
477 else
478 {
479 /* Case 4: make a new, two-entry EC */
481
482 ec->ec_opfamilies = opfamilies;
483 ec->ec_collation = collation;
484 ec->ec_childmembers_size = 0;
486 ec->ec_childmembers = NULL;
489 ec->ec_derives_hash = NULL;
490 ec->ec_relids = NULL;
494 ec->ec_sortref = 0;
497 ec->ec_merged = NULL;
498 em1 = add_eq_member(ec, item1, item1_relids,
499 jdomain, item1_type);
500 em2 = add_eq_member(ec, item2, item2_relids,
501 jdomain, item2_type);
502
504
505 /* mark the RI as associated with this eclass */
506 restrictinfo->left_ec = ec;
507 restrictinfo->right_ec = ec;
508 /* mark the RI as usable with this pair of EMs */
509 restrictinfo->left_em = em1;
510 restrictinfo->right_em = em2;
511 }
512
513 return true;
514}
void ec_clear_derived_clauses(EquivalenceClass *ec)
Definition: equivclass.c:3831
static void ec_add_derived_clauses(EquivalenceClass *ec, List *clauses)
Definition: equivclass.c:3733
RestrictInfo * make_restrictinfo(PlannerInfo *root, Expr *clause, bool is_pushed_down, bool has_clone, bool is_clone, bool pseudoconstant, Index security_level, Relids required_relids, Relids incompatible_relids, Relids outer_relids)
Definition: restrictinfo.c:52
Definition: primnodes.h:1981
References add_eq_member(), NullTest::arg, Assert(), bms_join(), canonicalize_ec_expression(), RestrictInfo::clause, ec_add_derived_clauses(), EquivalenceClass::ec_broken, EquivalenceClass::ec_childmembers, EquivalenceClass::ec_childmembers_size, ec_clear_derived_clauses(), EquivalenceClass::ec_collation, EquivalenceClass::ec_derives_hash, EquivalenceClass::ec_derives_list, EquivalenceClass::ec_has_const, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_max_security, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_min_security, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_relids, EquivalenceClass::ec_sortref, EquivalenceClass::ec_sources, elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_jdomain, equal(), ERROR, exprType(), foreach_current_index, func_strict(), get_leftop(), get_rightop(), RestrictInfo::has_clone, RestrictInfo::incompatible_relids, RestrictInfo::is_clone, IS_NOT_NULL, is_opclause(), RestrictInfo::is_pushed_down, lappend(), lfirst, list_concat(), list_delete_nth_cell(), list_make1, NullTest::location, make_restrictinfo(), makeNode, Max, Min, NIL, NullTest::nulltesttype, op_input_types(), RestrictInfo::outer_relids, root, RestrictInfo::security_level, and set_opfuncid().
Referenced by distribute_qual_to_rels(), reconsider_full_join_clause(), and reconsider_outer_join_clause().
◆ rebuild_eclass_attr_needed()
| void rebuild_eclass_attr_needed | ( | PlannerInfo * | root | ) |
Definition at line 2574 of file equivclass.c.
2575{
2576 ListCell *lc;
2577
2579 {
2581
2582 /*
2583 * We don't expect any EC child members to exist at this point. Ensure
2584 * that's the case, otherwise, we might be getting asked to do
2585 * something this function hasn't been coded for.
2586 */
2588
2589 /* Need do anything only for a multi-member, no-const EC. */
2591 {
2592 ListCell *lc2;
2593
2595 {
2598 PVC_RECURSE_AGGREGATES |
2599 PVC_RECURSE_WINDOWFUNCS |
2600 PVC_INCLUDE_PLACEHOLDERS);
2601
2604 }
2605 }
2606 }
2607}
void add_vars_to_attr_needed(PlannerInfo *root, List *vars, Relids where_needed)
Definition: initsplan.c:360
Definition: regcomp.c:282
References add_vars_to_attr_needed(), Assert(), EquivalenceClass::ec_childmembers, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, EquivalenceMember::em_expr, lfirst, list_free(), list_length(), pull_var_clause(), PVC_INCLUDE_PLACEHOLDERS, PVC_RECURSE_AGGREGATES, PVC_RECURSE_WINDOWFUNCS, and root.
Referenced by remove_leftjoinrel_from_query(), and remove_self_join_rel().
◆ reconsider_outer_join_clauses()
| void reconsider_outer_join_clauses | ( | PlannerInfo * | root | ) |
Definition at line 2135 of file equivclass.c.
2136{
2137 bool found;
2138 ListCell *cell;
2139
2140 /* Outer loop repeats until we find no more deductions */
2141 do
2142 {
2143 found = false;
2144
2145 /* Process the LEFT JOIN clauses */
2147 {
2149
2151 {
2153
2154 found = true;
2155 /* remove it from the list */
2156 root->left_join_clauses =
2158 /* throw back a dummy replacement clause (see notes above) */
2161 rinfo->is_pushed_down,
2162 rinfo->has_clone,
2163 rinfo->is_clone,
2164 false, /* pseudoconstant */
2165 0, /* security_level */
2166 rinfo->required_relids,
2167 rinfo->incompatible_relids,
2168 rinfo->outer_relids);
2170 }
2171 }
2172
2173 /* Process the RIGHT JOIN clauses */
2175 {
2177
2179 {
2181
2182 found = true;
2183 /* remove it from the list */
2184 root->right_join_clauses =
2186 /* throw back a dummy replacement clause (see notes above) */
2189 rinfo->is_pushed_down,
2190 rinfo->has_clone,
2191 rinfo->is_clone,
2192 false, /* pseudoconstant */
2193 0, /* security_level */
2194 rinfo->required_relids,
2195 rinfo->incompatible_relids,
2196 rinfo->outer_relids);
2198 }
2199 }
2200
2201 /* Process the FULL JOIN clauses */
2203 {
2205
2207 {
2209
2210 found = true;
2211 /* remove it from the list */
2212 root->full_join_clauses =
2214 /* throw back a dummy replacement clause (see notes above) */
2217 rinfo->is_pushed_down,
2218 rinfo->has_clone,
2219 rinfo->is_clone,
2220 false, /* pseudoconstant */
2221 0, /* security_level */
2222 rinfo->required_relids,
2223 rinfo->incompatible_relids,
2224 rinfo->outer_relids);
2226 }
2227 }
2228 } while (found);
2229
2230 /* Now, any remaining clauses have to be thrown back */
2232 {
2234
2236 }
2238 {
2240
2242 }
2244 {
2246
2248 }
2249}
static bool reconsider_outer_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo, bool outer_on_left)
Definition: equivclass.c:2257
static bool reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo)
Definition: equivclass.c:2384
void distribute_restrictinfo_to_rels(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: initsplan.c:3560
Definition: pathnodes.h:3142
References distribute_restrictinfo_to_rels(), foreach_delete_current, RestrictInfo::has_clone, RestrictInfo::incompatible_relids, RestrictInfo::is_clone, RestrictInfo::is_pushed_down, lfirst, make_restrictinfo(), makeBoolConst(), RestrictInfo::outer_relids, reconsider_full_join_clause(), reconsider_outer_join_clause(), RestrictInfo::required_relids, OuterJoinClauseInfo::rinfo, and root.
Referenced by query_planner().
◆ relation_can_be_sorted_early()
| bool relation_can_be_sorted_early | ( | PlannerInfo * | root, |
| RelOptInfo * | rel, | ||
| EquivalenceClass * | ec, | ||
| bool | require_parallel_safe | ||
| ) |
Definition at line 1077 of file equivclass.c.
1079{
1081 EquivalenceMember *em;
1082 ListCell *lc;
1083
1084 /*
1085 * Reject volatile ECs immediately; such sorts must always be postponed.
1086 */
1088 return false;
1089
1090 /*
1091 * Try to find an EM directly matching some reltarget member.
1092 */
1094 {
1096
1098 if (!em)
1099 continue;
1100
1101 /*
1102 * Reject expressions involving set-returning functions, as those
1103 * can't be computed early either. (Note: this test and the following
1104 * one are effectively checking properties of targetexpr, so there's
1105 * no point in asking whether some other EC member would be better.)
1106 */
1108 continue;
1109
1110 /*
1111 * If requested, reject expressions that are not parallel-safe. We
1112 * check this last because it's a rather expensive test.
1113 */
1114 if (require_parallel_safe &&
1116 continue;
1117
1118 return true;
1119 }
1120
1121 /*
1122 * Try to find an expression computable from the reltarget.
1123 */
1125 require_parallel_safe);
1126 if (!em)
1127 return false;
1128
1129 /*
1130 * Reject expressions involving set-returning functions, as those can't be
1131 * computed early either. (There's no point in looking for another EC
1132 * member in this case; since SRFs can't appear in WHERE, they cannot
1133 * belong to multi-member ECs.)
1134 */
1136 return false;
1137
1138 return true;
1139}
EquivalenceMember * find_ec_member_matching_expr(EquivalenceClass *ec, Expr *expr, Relids relids)
Definition: equivclass.c:916
EquivalenceMember * find_computable_ec_member(PlannerInfo *root, EquivalenceClass *ec, List *exprs, Relids relids, bool require_parallel_safe)
Definition: equivclass.c:991
Definition: pathnodes.h:1774
References EquivalenceClass::ec_has_volatile, EquivalenceMember::em_expr, expression_returns_set(), PathTarget::exprs, find_computable_ec_member(), find_ec_member_matching_expr(), is_parallel_safe(), lfirst, RelOptInfo::relids, RelOptInfo::reltarget, and root.
Referenced by get_useful_pathkeys_for_relation().
◆ relation_has_unique_index_for()
| bool relation_has_unique_index_for | ( | PlannerInfo * | root, |
| RelOptInfo * | rel, | ||
| List * | restrictlist, | ||
| List ** | extra_clauses | ||
| ) |
Definition at line 4146 of file indxpath.c.
4148{
4149 ListCell *ic;
4150
4151 /* Short-circuit if no indexes... */
4153 return false;
4154
4155 /*
4156 * Examine the rel's restriction clauses for usable var = const clauses
4157 * that we can add to the restrictlist.
4158 */
4160 {
4162
4163 /*
4164 * Note: can_join won't be set for a restriction clause, but
4165 * mergeopfamilies will be if it has a mergejoinable operator and
4166 * doesn't contain volatile functions.
4167 */
4169 continue; /* not mergejoinable */
4170
4171 /*
4172 * The clause certainly doesn't refer to anything but the given rel.
4173 * If either side is pseudoconstant then we can use it.
4174 */
4176 {
4177 /* righthand side is inner */
4178 restrictinfo->outer_is_left = true;
4179 }
4181 {
4182 /* lefthand side is inner */
4183 restrictinfo->outer_is_left = false;
4184 }
4185 else
4186 continue;
4187
4188 /* OK, add to list */
4189 restrictlist = lappend(restrictlist, restrictinfo);
4190 }
4191
4192 /* Short-circuit the easy case */
4194 return false;
4195
4196 /* Examine each index of the relation ... */
4198 {
4202
4203 /*
4204 * If the index is not unique, or not immediately enforced, or if it's
4205 * a partial index, it's useless here. We're unable to make use of
4206 * predOK partial unique indexes due to the fact that
4207 * check_index_predicates() also makes use of join predicates to
4208 * determine if the partial index is usable. Here we need proofs that
4209 * hold true before any joins are evaluated.
4210 */
4212 continue;
4213
4214 /*
4215 * Try to find each index column in the list of conditions. This is
4216 * O(N^2) or worse, but we expect all the lists to be short.
4217 */
4219 {
4220 ListCell *lc;
4221
4222 foreach(lc, restrictlist)
4223 {
4225 Node *rexpr;
4226
4227 /*
4228 * The condition's equality operator must be a member of the
4229 * index opfamily, else it is not asserting the right kind of
4230 * equality behavior for this index. We check this first
4231 * since it's probably cheaper than match_index_to_operand().
4232 */
4234 continue;
4235
4236 /*
4237 * XXX at some point we may need to check collations here too.
4238 * For the moment we assume all collations reduce to the same
4239 * notion of equality.
4240 */
4241
4242 /* OK, see if the condition operand matches the index key */
4243 if (rinfo->outer_is_left)
4245 else
4247
4249 {
4251 {
4252 MemoryContext oldMemCtx =
4254
4255 /*
4256 * Add filter clause into a list allowing caller to
4257 * know if uniqueness have made not only by join
4258 * clauses.
4259 */
4261 bms_is_empty(rinfo->right_relids));
4262 if (extra_clauses)
4263 exprs = lappend(exprs, rinfo);
4264 MemoryContextSwitchTo(oldMemCtx);
4265 }
4266
4267 break; /* found a match; column is unique */
4268 }
4269 }
4270
4271 if (lc == NULL)
4272 break; /* no match; this index doesn't help us */
4273 }
4274
4275 /* Matched all key columns of this index? */
4277 {
4278 if (extra_clauses)
4279 *extra_clauses = exprs;
4280 return true;
4281 }
4282 }
4283
4284 return false;
4285}
bool match_index_to_operand(Node *operand, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:4355
Definition: preproc-array_of_struct.c:43
References Assert(), RelOptInfo::baserestrictinfo, bms_is_empty, bms_membership(), BMS_SINGLETON, RestrictInfo::clause, get_leftop(), get_rightop(), RelOptInfo::indexlist, lappend(), lfirst, list_member_oid(), match_index_to_operand(), MemoryContextSwitchTo(), NIL, and root.
Referenced by rel_is_distinct_for().
◆ select_outer_pathkeys_for_merge()
| List * select_outer_pathkeys_for_merge | ( | PlannerInfo * | root, |
| List * | mergeclauses, | ||
| RelOptInfo * | joinrel | ||
| ) |
Definition at line 1659 of file pathkeys.c.
1662{
1665 EquivalenceClass **ecs;
1666 int *scores;
1667 int necs;
1668 ListCell *lc;
1670
1671 /* Might have no mergeclauses */
1672 if (nClauses == 0)
1674
1675 /*
1676 * Make arrays of the ECs used by the mergeclauses (dropping any
1677 * duplicates) and their "popularity" scores.
1678 */
1681 necs = 0;
1682
1683 foreach(lc, mergeclauses)
1684 {
1686 EquivalenceClass *oeclass;
1687 int score;
1688 ListCell *lc2;
1689
1690 /* get the outer eclass */
1692
1693 if (rinfo->outer_is_left)
1694 oeclass = rinfo->left_ec;
1695 else
1696 oeclass = rinfo->right_ec;
1697
1698 /* reject duplicates */
1700 {
1702 break;
1703 }
1705 continue;
1706
1707 /* compute score */
1708 score = 0;
1710 {
1712
1713 /* Child members should not exist in ec_members */
1715
1716 /* Potential future join partner? */
1719 score++;
1720 }
1721
1722 ecs[necs] = oeclass;
1723 scores[necs] = score;
1724 necs++;
1725 }
1726
1727 /*
1728 * Find out if we have all the ECs mentioned in query_pathkeys; if so we
1729 * can generate a sort order that's also useful for final output. If we
1730 * only have a prefix of the query_pathkeys, and that prefix is the entire
1731 * join condition, then it's useful to use the prefix as the pathkeys as
1732 * this increases the chances that an incremental sort will be able to be
1733 * used by the upper planner.
1734 */
1736 {
1737 int matches = 0;
1738
1740 {
1742 EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1743
1745 {
1747 break; /* found match */
1748 }
1750 break; /* didn't find match */
1751
1752 matches++;
1753 }
1754 /* if we got to the end of the list, we have them all */
1755 if (lc == NULL)
1756 {
1757 /* copy query_pathkeys as starting point for our output */
1759 /* mark their ECs as already-emitted */
1761 {
1763 EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1764
1766 {
1768 {
1769 scores[j] = -1;
1770 break;
1771 }
1772 }
1773 }
1774 }
1775
1776 /*
1777 * If we didn't match to all of the query_pathkeys, but did match to
1778 * all of the join clauses then we'll make use of these as partially
1779 * sorted input is better than nothing for the upper planner as it may
1780 * lead to incremental sorts instead of full sorts.
1781 */
1782 else if (matches == nClauses)
1783 {
1785
1786 /* we have all of the join pathkeys, so nothing more to do */
1787 pfree(ecs);
1788 pfree(scores);
1789
1790 return pathkeys;
1791 }
1792 }
1793
1794 /*
1795 * Add remaining ECs to the list in popularity order, using a default sort
1796 * ordering. (We could use qsort() here, but the list length is usually
1797 * so small it's not worth it.)
1798 */
1799 for (;;)
1800 {
1801 int best_j;
1802 int best_score;
1803 EquivalenceClass *ec;
1804 PathKey *pathkey;
1805
1806 best_j = 0;
1807 best_score = scores[0];
1809 {
1811 {
1812 best_j = j;
1813 best_score = scores[j];
1814 }
1815 }
1816 if (best_score < 0)
1817 break; /* all done */
1818 ec = ecs[best_j];
1819 scores[best_j] = -1;
1821 ec,
1823 COMPARE_LT,
1824 false);
1825 /* can't be redundant because no duplicate ECs */
1827 pathkeys = lappend(pathkeys, pathkey);
1828 }
1829
1830 pfree(ecs);
1831 pfree(scores);
1832
1833 return pathkeys;
1834}
References Assert(), bms_overlap(), COMPARE_LT, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, j, lappend(), lfirst, linitial_oid, list_copy(), list_copy_head(), list_length(), make_canonical_pathkey(), NIL, palloc(), pathkey_is_redundant(), pfree(), RelOptInfo::relids, root, and update_mergeclause_eclasses().
Referenced by sort_inner_and_outer().
◆ setup_eclass_member_iterator()
| void setup_eclass_member_iterator | ( | EquivalenceMemberIterator * | it, |
| EquivalenceClass * | ec, | ||
| Relids | child_relids | ||
| ) |
Definition at line 3156 of file equivclass.c.
3158{
3159 it->ec = ec;
3160 /* no need to set this if the class has no child members array set */
3162 it->current_relid = -1;
3165}
References EquivalenceMemberIterator::child_relids, EquivalenceMemberIterator::current_cell, EquivalenceMemberIterator::current_list, EquivalenceMemberIterator::current_relid, EquivalenceMemberIterator::ec, EquivalenceClass::ec_childmembers, EquivalenceClass::ec_members, and list_head().
Referenced by find_computable_ec_member(), find_ec_member_matching_expr(), find_em_for_rel(), generate_implied_equalities_for_column(), generate_join_implied_equalities_normal(), get_eclass_for_sort_expr(), and match_pathkeys_to_index().
◆ standard_join_search()
| RelOptInfo * standard_join_search | ( | PlannerInfo * | root, |
| int | levels_needed, | ||
| List * | initial_rels | ||
| ) |
Definition at line 3885 of file allpaths.c.
3886{
3887 int lev;
3888 RelOptInfo *rel;
3889
3890 /*
3891 * This function cannot be invoked recursively within any one planning
3892 * problem, so join_rel_level[] can't be in use already.
3893 */
3895
3896 /*
3897 * We employ a simple "dynamic programming" algorithm: we first find all
3898 * ways to build joins of two jointree items, then all ways to build joins
3899 * of three items (from two-item joins and single items), then four-item
3900 * joins, and so on until we have considered all ways to join all the
3901 * items into one rel.
3902 *
3903 * root->join_rel_level[j] is a list of all the j-item rels. Initially we
3904 * set root->join_rel_level[1] to represent all the single-jointree-item
3905 * relations.
3906 */
3908
3909 root->join_rel_level[1] = initial_rels;
3910
3911 for (lev = 2; lev <= levels_needed; lev++)
3912 {
3913 ListCell *lc;
3914
3915 /*
3916 * Determine all possible pairs of relations to be joined at this
3917 * level, and build paths for making each one from every available
3918 * pair of lower-level relations.
3919 */
3921
3922 /*
3923 * Run generate_partitionwise_join_paths() and
3924 * generate_useful_gather_paths() for each just-processed joinrel. We
3925 * could not do this earlier because both regular and partial paths
3926 * can get added to a particular joinrel at multiple times within
3927 * join_search_one_level.
3928 *
3929 * After that, we're done creating paths for the joinrel, so run
3930 * set_cheapest().
3931 *
3932 * In addition, we also run generate_grouped_paths() for the grouped
3933 * relation of each just-processed joinrel, and run set_cheapest() for
3934 * the grouped relation afterwards.
3935 */
3937 {
3938 bool is_top_rel;
3939
3941
3943
3944 /* Create paths for partitionwise joins. */
3946
3947 /*
3948 * Except for the topmost scan/join rel, consider gathering
3949 * partial paths. We'll do the same for the topmost scan/join rel
3950 * once we know the final targetlist (see grouping_planner's and
3951 * its call to apply_scanjoin_target_to_paths).
3952 */
3953 if (!is_top_rel)
3955
3956 /* Find and save the cheapest paths for this rel */
3957 set_cheapest(rel);
3958
3959 /*
3960 * Except for the topmost scan/join rel, consider generating
3961 * partial aggregation paths for the grouped relation on top of
3962 * the paths of this rel. After that, we're done creating paths
3963 * for the grouped relation, so run set_cheapest().
3964 */
3966 {
3968
3970
3972 set_cheapest(grouped_rel);
3973 }
3974
3975#ifdef OPTIMIZER_DEBUG
3976 pprint(rel);
3977#endif
3978 }
3979 }
3980
3981 /*
3982 * We should have a single rel at the final level.
3983 */
3987
3989
3990 root->join_rel_level = NULL;
3991
3992 return rel;
3993}
void generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
Definition: allpaths.c:3325
void join_search_one_level(PlannerInfo *root, int level)
Definition: joinrels.c:78
References Assert(), bms_equal(), elog, ERROR, generate_grouped_paths(), generate_partitionwise_join_paths(), generate_useful_gather_paths(), RelOptInfo::grouped_rel, IS_GROUPED_REL, join_search_one_level(), lfirst, linitial, list_length(), NIL, palloc0(), pprint(), RelOptInfo::relids, root, and set_cheapest().
Referenced by make_rel_from_joinlist().
◆ trim_mergeclauses_for_inner_pathkeys()
| List * trim_mergeclauses_for_inner_pathkeys | ( | PlannerInfo * | root, |
| List * | mergeclauses, | ||
| List * | pathkeys | ||
| ) |
Definition at line 1961 of file pathkeys.c.
1964{
1966 PathKey *pathkey;
1967 EquivalenceClass *pathkey_ec;
1968 bool matched_pathkey;
1969 ListCell *lip;
1971
1972 /* No pathkeys => no mergeclauses (though we don't expect this case) */
1975 /* Initialize to consider first pathkey */
1976 lip = list_head(pathkeys);
1978 pathkey_ec = pathkey->pk_eclass;
1979 lip = lnext(pathkeys, lip);
1980 matched_pathkey = false;
1981
1982 /* Scan mergeclauses to see how many we can use */
1984 {
1986 EquivalenceClass *clause_ec;
1987
1988 /* Assume we needn't do update_mergeclause_eclasses again here */
1989
1990 /* Check clause's inner-rel EC against current pathkey */
1991 clause_ec = rinfo->outer_is_left ?
1992 rinfo->right_ec : rinfo->left_ec;
1993
1994 /* If we don't have a match, attempt to advance to next pathkey */
1995 if (clause_ec != pathkey_ec)
1996 {
1997 /* If we had no clauses matching this inner pathkey, must stop */
1998 if (!matched_pathkey)
1999 break;
2000
2001 /* Advance to next inner pathkey, if any */
2002 if (lip == NULL)
2003 break;
2005 pathkey_ec = pathkey->pk_eclass;
2006 lip = lnext(pathkeys, lip);
2007 matched_pathkey = false;
2008 }
2009
2010 /* If mergeclause matches current inner pathkey, we can use it */
2011 if (clause_ec == pathkey_ec)
2012 {
2013 new_mergeclauses = lappend(new_mergeclauses, rinfo);
2014 matched_pathkey = true;
2015 }
2016 else
2017 {
2018 /* Else, no hope of adding any more mergeclauses */
2019 break;
2020 }
2021 }
2022
2023 return new_mergeclauses;
2024}
References i, lappend(), lfirst, list_head(), lnext(), and NIL.
Referenced by generate_mergejoin_paths().
◆ truncate_useless_pathkeys()
| List * truncate_useless_pathkeys | ( | PlannerInfo * | root, |
| RelOptInfo * | rel, | ||
| List * | pathkeys | ||
| ) |
Definition at line 2200 of file pathkeys.c.
2203{
2204 int nuseful;
2205 int nuseful2;
2207
2208 /*
2209 * Here we determine how many items in 'pathkeys' might be useful for
2210 * various Path sort ordering requirements the planner has. Operations
2211 * such as ORDER BY require a Path's pathkeys to match the PathKeys of the
2212 * ORDER BY in the same order, however operations such as GROUP BY and
2213 * DISTINCT are less critical as a Unique or GroupAggregate only need to
2214 * care that all PathKeys exist in their subpath, and don't need to care
2215 * if they're in the same order as the clause in the query.
2216 */
2218 pathkeys);
2219
2220 /* Short-circuit at any point we discover *all* pathkeys are useful */
2221 if (nuseful == ntotal)
2222 return pathkeys;
2223
2225 pathkeys);
2226 if (nuseful2 == ntotal)
2227 return pathkeys;
2228
2229 nuseful = Max(nuseful, nuseful2);
2231 pathkeys);
2232 if (nuseful2 == ntotal)
2233 return pathkeys;
2234
2235 nuseful = Max(nuseful, nuseful2);
2236
2237 /*
2238 * Check if these pathkeys are useful for GROUP BY or DISTINCT. The order
2239 * of the pathkeys does not matter here as Unique and GroupAggregate for
2240 * these operations can take advantage of Paths presorted by any of the
2241 * GROUP BY/DISTINCT pathkeys.
2242 */
2244 pathkeys);
2245 if (nuseful2 == ntotal)
2246 return pathkeys;
2247
2248 nuseful = Max(nuseful, nuseful2);
2250 pathkeys);
2251
2252 if (nuseful2 == ntotal)
2253 return pathkeys;
2254
2255 nuseful = Max(nuseful, nuseful2);
2256
2257 /*
2258 * Finally, check how many PathKeys might be useful for Merge Joins. This
2259 * is a bit more expensive, so do it last and only if we've not figured
2260 * out that all the pathkeys are useful already.
2261 */
2263 nuseful = Max(nuseful, nuseful2);
2264
2265 /*
2266 * Note: not safe to modify input list destructively, but we can avoid
2267 * copying the list if we're not actually going to change it
2268 */
2269 if (nuseful == ntotal)
2270 return pathkeys;
2271 else
2273}
static int count_common_leading_pathkeys_ordered(List *keys1, List *keys2)
Definition: pathkeys.c:2154
static int count_common_leading_pathkeys_unordered(List *keys1, List *keys2)
Definition: pathkeys.c:2169
static int pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:2056
References count_common_leading_pathkeys_ordered(), count_common_leading_pathkeys_unordered(), list_copy_head(), list_length(), Max, pathkeys_useful_for_merging(), and root.
Referenced by build_index_paths(), and build_join_pathkeys().
◆ update_mergeclause_eclasses()
| void update_mergeclause_eclasses | ( | PlannerInfo * | root, |
| RestrictInfo * | restrictinfo | ||
| ) |
Definition at line 1510 of file pathkeys.c.
1511{
1512 /* Should be a merge clause ... */
1514 /* ... with pointers already set */
1515 Assert(restrictinfo->left_ec != NULL);
1516 Assert(restrictinfo->right_ec != NULL);
1517
1518 /* Chase up to the top as needed */
1519 while (restrictinfo->left_ec->ec_merged)
1520 restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
1521 while (restrictinfo->right_ec->ec_merged)
1522 restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
1523}
Referenced by find_mergeclauses_for_outer_pathkeys(), get_useful_ecs_for_relation(), make_inner_pathkeys_for_merge(), pathkeys_useful_for_merging(), select_mergejoin_clauses(), and select_outer_pathkeys_for_merge().
Variable Documentation
◆ enable_eager_aggregate
|
extern |
Definition at line 82 of file allpaths.c.
Referenced by setup_eager_aggregation().
◆ enable_geqo
|
extern |
Definition at line 81 of file allpaths.c.
Referenced by make_rel_from_joinlist().
◆ enable_group_by_reordering
|
extern |
Definition at line 32 of file pathkeys.c.
Referenced by get_useful_group_keys_orderings().
◆ geqo_threshold
|
extern |
Definition at line 83 of file allpaths.c.
Referenced by make_rel_from_joinlist().
◆ join_search_hook
|
extern |
Definition at line 92 of file allpaths.c.
Referenced by make_rel_from_joinlist().
◆ min_eager_agg_group_size
|
extern |
Definition at line 84 of file allpaths.c.
Referenced by create_rel_agg_info().
◆ min_parallel_index_scan_size
|
extern |
Definition at line 86 of file allpaths.c.
Referenced by compute_parallel_worker(), and parallel_vacuum_compute_workers().
◆ min_parallel_table_scan_size
|
extern |
Definition at line 85 of file allpaths.c.
Referenced by compute_parallel_worker().
◆ set_join_pathlist_hook
|
extern |
Definition at line 33 of file joinpath.c.
Referenced by add_paths_to_joinrel().
◆ set_rel_pathlist_hook
|
extern |
Definition at line 89 of file allpaths.c.
Referenced by set_rel_pathlist().
