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 205 of file paths.h.
206{
211} 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 2813 of file equivclass.c.
2817{
2820 Bitmapset *matching_ecs;
2821 MemoryContext oldcontext;
2823
2825
2826 /* We need consider only ECs that mention the parent joinrel */
2828
2829 /*
2830 * If we're being called during GEQO join planning, we still have to
2831 * create any new EC members in the main planner context, to avoid having
2832 * a corrupt EC data structure after the GEQO context is reset. This is
2833 * problematic since we'll leak memory across repeated GEQO cycles. For
2834 * now, though, bloat is better than crash. If it becomes a real issue
2835 * we'll have to do something to avoid generating duplicate EC members.
2836 */
2838
2839 i = -1;
2841 {
2843 int num_members;
2844
2845 /*
2846 * If this EC contains a volatile expression, then generating child
2847 * EMs would be downright dangerous, so skip it. We rely on a
2848 * volatile EC having only one EM.
2849 */
2851 continue;
2852
2853 /* Sanity check on get_eclass_indexes_for_relids result */
2855
2856 /*
2857 * We don't use foreach() here because there's no point in scanning
2858 * newly-added child members, so we can stop after the last
2859 * pre-existing EC member.
2860 */
2862 for (int pos = 0; pos < num_members; pos++)
2863 {
2865
2867 continue; /* ignore consts here */
2868
2869 /*
2870 * We consider only original EC members here, not
2871 * already-transformed child members.
2872 */
2874 continue; /* ignore children here */
2875
2876 /*
2877 * We may ignore expressions that reference a single baserel,
2878 * because add_child_rel_equivalences should have handled them.
2879 */
2881 continue;
2882
2883 /* Does this member reference child's topmost parent rel? */
2885 {
2886 /* Yes, generate transformed child version */
2887 Expr *child_expr;
2888 Relids new_relids;
2889
2891 {
2892 /* Simple single-level transformation */
2893 child_expr = (Expr *)
2896 nappinfos, appinfos);
2897 }
2898 else
2899 {
2900 /* Must do multi-level transformation */
2902 child_expr = (Expr *)
2905 child_joinrel,
2906 child_joinrel->top_parent);
2907 }
2908
2909 /*
2910 * Transform em_relids to match. Note we do *not* do
2911 * pull_varnos(child_expr) here, as for example the
2912 * transformation might have substituted a constant, but we
2913 * don't want the child member to be marked as constant.
2914 */
2916 top_parent_relids);
2917 new_relids = bms_add_members(new_relids, child_relids);
2918
2919 (void) add_eq_member(cur_ec, child_expr, new_relids,
2920 cur_em->em_jdomain,
2921 cur_em, cur_em->em_datatype);
2922 }
2923 }
2924 }
2925
2926 MemoryContextSwitchTo(oldcontext);
2927}
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:541
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:917
static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, JoinDomain *jdomain, EquivalenceMember *parent, Oid datatype)
Definition: equivclass.c:516
static Bitmapset * get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
Definition: equivclass.c:3388
Assert(PointerIsAligned(start, uint64))
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
Definition: bitmapset.h:50
Definition: pathnodes.h:1413
Definition: pathnodes.h:1464
Definition: primnodes.h:189
Definition: memnodes.h:118
Definition: nodes.h:129
References add_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, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_jdomain, EquivalenceMember::em_relids, get_eclass_indexes_for_relids(), i, IS_JOIN_REL, list_length(), 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 2691 of file equivclass.c.
2695{
2699
2700 /*
2701 * EC merging should be complete already, so we can use the parent rel's
2702 * eclass_indexes to avoid searching all of root->eq_classes.
2703 */
2706
2707 i = -1;
2709 {
2711 int num_members;
2712
2713 /*
2714 * If this EC contains a volatile expression, then generating child
2715 * EMs would be downright dangerous, so skip it. We rely on a
2716 * volatile EC having only one EM.
2717 */
2719 continue;
2720
2721 /* Sanity check eclass_indexes only contain ECs for parent_rel */
2723
2724 /*
2725 * We don't use foreach() here because there's no point in scanning
2726 * newly-added child members, so we can stop after the last
2727 * pre-existing EC member.
2728 */
2730 for (int pos = 0; pos < num_members; pos++)
2731 {
2733
2735 continue; /* ignore consts here */
2736
2737 /*
2738 * We consider only original EC members here, not
2739 * already-transformed child members. Otherwise, if some original
2740 * member expression references more than one appendrel, we'd get
2741 * an O(N^2) explosion of useless derived expressions for
2742 * combinations of children. (But add_child_join_rel_equivalences
2743 * may add targeted combinations for partitionwise-join purposes.)
2744 */
2746 continue; /* ignore children here */
2747
2748 /*
2749 * Consider only members that reference and can be computed at
2750 * child's topmost parent rel. In particular we want to exclude
2751 * parent-rel Vars that have nonempty varnullingrels. Translating
2752 * those might fail, if the transformed expression wouldn't be a
2753 * simple Var; and in any case it wouldn't produce a member that
2754 * has any use in creating plans for the child rel.
2755 */
2758 {
2759 /* OK, generate transformed child version */
2760 Expr *child_expr;
2761 Relids new_relids;
2762
2764 {
2765 /* Simple single-level transformation */
2766 child_expr = (Expr *)
2769 1, &appinfo);
2770 }
2771 else
2772 {
2773 /* Must do multi-level transformation */
2774 child_expr = (Expr *)
2777 child_rel,
2778 child_rel->top_parent);
2779 }
2780
2781 /*
2782 * Transform em_relids to match. Note we do *not* do
2783 * pull_varnos(child_expr) here, as for example the
2784 * transformation might have substituted a constant, but we
2785 * don't want the child member to be marked as constant.
2786 */
2788 top_parent_relids);
2789 new_relids = bms_add_members(new_relids, child_relids);
2790
2791 (void) add_eq_member(cur_ec, child_expr, new_relids,
2792 cur_em->em_jdomain,
2793 cur_em, cur_em->em_datatype);
2794
2795 /* Record this EC index for the child rel */
2797 }
2798 }
2799 }
2800}
References add_eq_member(), adjust_appendrel_attrs(), adjust_appendrel_attrs_multilevel(), Assert(), bms_add_member(), 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, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_jdomain, EquivalenceMember::em_relids, i, IS_SIMPLE_REL, list_length(), list_nth(), 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 802 of file joinrels.c.
805{
806 /* Nothing to do if this isn't an outer join with an assigned relid. */
808 return input_relids;
809
810 /*
811 * If it's not a left join, we have no rules that would permit executing
812 * it in non-syntactic order, so just form the syntactic relid set. (This
813 * is just a quick-exit test; we'd come to the same conclusion anyway,
814 * since its commute_below_l and commute_above_l sets must be empty.)
815 */
818
819 /*
820 * We cannot add the OJ relid if this join has been pushed into the RHS of
821 * a syntactically-lower left join per OJ identity 3. (If it has, then we
822 * cannot claim that its outputs represent the final state of its RHS.)
823 * There will not be any other OJs that can be added either, so we're
824 * done.
825 */
827 return input_relids;
828
829 /* OK to add OJ's own relid */
831
832 /*
833 * Contrariwise, if we are now forming the final result of such a commuted
834 * pair of OJs, it's time to add the relid(s) of the pushed-down join(s).
835 * We can skip this if this join was never a candidate to be pushed up.
836 */
838 {
840 ListCell *lc;
841
842 /*
843 * The current join could complete the nulling of more than one
844 * pushed-down join, so we have to examine all the SpecialJoinInfos.
845 * Because join_info_list was built in bottom-up order, it's
846 * sufficient to traverse it once: an ojrelid we add in one loop
847 * iteration would not have affected decisions of earlier iterations.
848 */
850 {
852
853 if (othersj == sjinfo ||
855 continue; /* definitely not interesting */
856
858 continue;
859
860 /* Add it if not already present but conditions now satisfied */
865 {
867 /* report such pushed down outer joins, if asked */
868 if (pushed_down_joins != NULL)
869 *pushed_down_joins = lappend(*pushed_down_joins, othersj);
870
871 /*
872 * We must also check any joins that othersj potentially
873 * commutes with. They likewise must appear later in
874 * join_info_list than othersj itself, so we can visit them
875 * later in this loop.
876 */
877 commute_above_rels = bms_add_members(commute_above_rels,
878 othersj->commute_above_l);
879 }
880 }
881 }
882
883 return input_relids;
884}
Definition: pathnodes.h:2925
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 1321 of file allpaths.c.
1323{
1325 bool subpaths_valid = true;
1327 bool startup_subpaths_valid = true;
1331 bool partial_subpaths_valid = true;
1332 bool pa_subpaths_valid;
1335 ListCell *l;
1336 double partial_rows = -1;
1337
1338 /* If appropriate, consider parallel append */
1340
1341 /*
1342 * For every non-dummy child, remember the cheapest path. Also, identify
1343 * all pathkeys (orderings) and parameterizations (required_outer sets)
1344 * available for the non-dummy member relations.
1345 */
1346 foreach(l, live_childrels)
1347 {
1349 ListCell *lcp;
1350 Path *cheapest_partial_path = NULL;
1351
1352 /*
1353 * If child has an unparameterized cheapest-total path, add that to
1354 * the unparameterized Append path we are constructing for the parent.
1355 * If not, there's no workable unparameterized path.
1356 *
1357 * With partitionwise aggregates, the child rel's pathlist may be
1358 * empty, so don't assume that a path exists here.
1359 */
1361 childrel->cheapest_total_path->param_info == NULL)
1363 &subpaths, NULL);
1364 else
1365 subpaths_valid = false;
1366
1367 /*
1368 * When the planner is considering cheap startup plans, we'll also
1369 * collect all the cheapest_startup_paths (if set) and build an
1370 * AppendPath containing those as subpaths.
1371 */
1373 {
1374 Path *cheapest_path;
1375
1376 /*
1377 * With an indication of how many tuples the query should provide,
1378 * the optimizer tries to choose the path optimal for that
1379 * specific number of tuples.
1380 */
1382 cheapest_path =
1383 get_cheapest_fractional_path(childrel,
1384 root->tuple_fraction);
1385 else
1386 cheapest_path = childrel->cheapest_startup_path;
1387
1388 /* cheapest_startup_path must not be a parameterized path. */
1389 Assert(cheapest_path->param_info == NULL);
1390 accumulate_append_subpath(cheapest_path,
1391 &startup_subpaths,
1392 NULL);
1393 }
1394 else
1395 startup_subpaths_valid = false;
1396
1397
1398 /* Same idea, but for a partial plan. */
1400 {
1402 accumulate_append_subpath(cheapest_partial_path,
1403 &partial_subpaths, NULL);
1404 }
1405 else
1406 partial_subpaths_valid = false;
1407
1408 /*
1409 * Same idea, but for a parallel append mixing partial and non-partial
1410 * paths.
1411 */
1412 if (pa_subpaths_valid)
1413 {
1414 Path *nppath = NULL;
1415
1416 nppath =
1418
1419 if (cheapest_partial_path == NULL && nppath == NULL)
1420 {
1421 /* Neither a partial nor a parallel-safe path? Forget it. */
1422 pa_subpaths_valid = false;
1423 }
1424 else if (nppath == NULL ||
1425 (cheapest_partial_path != NULL &&
1427 {
1428 /* Partial path is cheaper or the only option. */
1429 Assert(cheapest_partial_path != NULL);
1430 accumulate_append_subpath(cheapest_partial_path,
1431 &pa_partial_subpaths,
1432 &pa_nonpartial_subpaths);
1433 }
1434 else
1435 {
1436 /*
1437 * Either we've got only a non-partial path, or we think that
1438 * a single backend can execute the best non-partial path
1439 * faster than all the parallel backends working together can
1440 * execute the best partial path.
1441 *
1442 * It might make sense to be more aggressive here. Even if
1443 * the best non-partial path is more expensive than the best
1444 * partial path, it could still be better to choose the
1445 * non-partial path if there are several such paths that can
1446 * be given to different workers. For now, we don't try to
1447 * figure that out.
1448 */
1449 accumulate_append_subpath(nppath,
1450 &pa_nonpartial_subpaths,
1451 NULL);
1452 }
1453 }
1454
1455 /*
1456 * Collect lists of all the available path orderings and
1457 * parameterizations for all the children. We use these as a
1458 * heuristic to indicate which sort orderings and parameterizations we
1459 * should build Append and MergeAppend paths for.
1460 */
1462 {
1466
1467 /* Unsorted paths don't contribute to pathkey list */
1469 {
1470 ListCell *lpk;
1471 bool found = false;
1472
1473 /* Have we already seen this ordering? */
1474 foreach(lpk, all_child_pathkeys)
1475 {
1477
1479 childkeys) == PATHKEYS_EQUAL)
1480 {
1481 found = true;
1482 break;
1483 }
1484 }
1485 if (!found)
1486 {
1487 /* No, so add it to all_child_pathkeys */
1488 all_child_pathkeys = lappend(all_child_pathkeys,
1489 childkeys);
1490 }
1491 }
1492
1493 /* Unparameterized paths don't contribute to param-set list */
1494 if (childouter)
1495 {
1496 ListCell *lco;
1497 bool found = false;
1498
1499 /* Have we already seen this param set? */
1500 foreach(lco, all_child_outers)
1501 {
1503
1505 {
1506 found = true;
1507 break;
1508 }
1509 }
1510 if (!found)
1511 {
1512 /* No, so add it to all_child_outers */
1513 all_child_outers = lappend(all_child_outers,
1514 childouter);
1515 }
1516 }
1517 }
1518 }
1519
1520 /*
1521 * If we found unparameterized paths for all children, build an unordered,
1522 * unparameterized Append path for the rel. (Note: this is correct even
1523 * if we have zero or one live subpath due to constraint exclusion.)
1524 */
1525 if (subpaths_valid)
1528 -1));
1529
1530 /* build an AppendPath for the cheap startup paths, if valid */
1531 if (startup_subpaths_valid)
1534
1535 /*
1536 * Consider an append of unordered, unparameterized partial paths. Make
1537 * it parallel-aware if possible.
1538 */
1540 {
1541 AppendPath *appendpath;
1542 ListCell *lc;
1543 int parallel_workers = 0;
1544
1545 /* Find the highest number of workers requested for any subpath. */
1546 foreach(lc, partial_subpaths)
1547 {
1549
1551 }
1552 Assert(parallel_workers > 0);
1553
1554 /*
1555 * If the use of parallel append is permitted, always request at least
1556 * log2(# of children) workers. We assume it can be useful to have
1557 * extra workers in this case because they will be spread out across
1558 * the children. The precise formula is just a guess, but we don't
1559 * want to end up with a radically different answer for a table with N
1560 * partitions vs. an unpartitioned table with the same data, so the
1561 * use of some kind of log-scaling here seems to make some sense.
1562 */
1564 {
1565 parallel_workers = Max(parallel_workers,
1567 parallel_workers = Min(parallel_workers,
1569 }
1570 Assert(parallel_workers > 0);
1571
1572 /* Generate a partial append path. */
1574 NIL, NULL, parallel_workers,
1575 enable_parallel_append,
1576 -1);
1577
1578 /*
1579 * Make sure any subsequent partial paths use the same row count
1580 * estimate.
1581 */
1583
1584 /* Add the path. */
1586 }
1587
1588 /*
1589 * Consider a parallel-aware append using a mix of partial and non-partial
1590 * paths. (This only makes sense if there's at least one child which has
1591 * a non-partial path that is substantially cheaper than any partial path;
1592 * otherwise, we should use the append path added in the previous step.)
1593 */
1595 {
1596 AppendPath *appendpath;
1597 ListCell *lc;
1598 int parallel_workers = 0;
1599
1600 /*
1601 * Find the highest number of workers requested for any partial
1602 * subpath.
1603 */
1604 foreach(lc, pa_partial_subpaths)
1605 {
1607
1609 }
1610
1611 /*
1612 * Same formula here as above. It's even more important in this
1613 * instance because the non-partial paths won't contribute anything to
1614 * the planned number of parallel workers.
1615 */
1616 parallel_workers = Max(parallel_workers,
1618 parallel_workers = Min(parallel_workers,
1620 Assert(parallel_workers > 0);
1621
1623 pa_partial_subpaths,
1625 partial_rows);
1627 }
1628
1629 /*
1630 * Also build unparameterized ordered append paths based on the collected
1631 * list of child pathkeys.
1632 */
1633 if (subpaths_valid)
1635 all_child_pathkeys);
1636
1637 /*
1638 * Build Append paths for each parameterization seen among the child rels.
1639 * (This may look pretty expensive, but in most cases of practical
1640 * interest, the child rels will expose mostly the same parameterizations,
1641 * so that not that many cases actually get considered here.)
1642 *
1643 * The Append node itself cannot enforce quals, so all qual checking must
1644 * be done in the child paths. This means that to have a parameterized
1645 * Append path, we must have the exact same parameterization for each
1646 * child path; otherwise some children might be failing to check the
1647 * moved-down quals. To make them match up, we can try to increase the
1648 * parameterization of lesser-parameterized paths.
1649 */
1650 foreach(l, all_child_outers)
1651 {
1653 ListCell *lcr;
1654
1655 /* Select the child paths for an Append with this parameterization */
1656 subpaths = NIL;
1657 subpaths_valid = true;
1658 foreach(lcr, live_childrels)
1659 {
1662
1664 {
1665 /* failed to make a suitable path for this child */
1666 subpaths_valid = false;
1667 break;
1668 }
1669
1671 childrel,
1672 required_outer);
1674 {
1675 /* failed to make a suitable path for this child */
1676 subpaths_valid = false;
1677 break;
1678 }
1680 }
1681
1682 if (subpaths_valid)
1686 -1));
1687 }
1688
1689 /*
1690 * When there is only a single child relation, the Append path can inherit
1691 * any ordering available for the child rel's path, so that it's useful to
1692 * consider ordered partial paths. Above we only considered the cheapest
1693 * partial path for each child, but let's also make paths using any
1694 * partial paths that have pathkeys.
1695 */
1697 {
1699
1700 /* skip the cheapest partial path, since we already used that above */
1702 {
1704 AppendPath *appendpath;
1705
1706 /* skip paths with no pathkeys. */
1708 continue;
1709
1711 NIL, NULL,
1713 partial_rows);
1715 }
1716 }
1717}
static Path * get_cheapest_parameterized_child_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer)
Definition: allpaths.c:2032
static void generate_orderedappend_paths(PlannerInfo *root, RelOptInfo *rel, List *live_childrels, List *all_child_pathkeys)
Definition: allpaths.c:1747
static void accumulate_append_subpath(Path *path, List **subpaths, List **special_subpaths)
Definition: allpaths.c:2120
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:1300
Path * get_cheapest_fractional_path(RelOptInfo *rel, double tuple_fraction)
Definition: planner.c:6478
Definition: pathnodes.h:1966
Definition: pg_list.h:54
Definition: pathnodes.h:1655
Definition: pathnodes.h:884
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 JoinPathExtraData extra;
133 bool mergejoin_allowed = true;
134 ListCell *lc;
135 Relids joinrelids;
136
137 /*
138 * PlannerInfo doesn't contain the SpecialJoinInfos created for joins
139 * between child relations, even if there is a SpecialJoinInfo node for
140 * the join between the topmost parents. So, while calculating Relids set
141 * representing the restriction, consider relids of topmost parent of
142 * partitions.
143 */
145 joinrelids = joinrel->top_parent_relids;
146 else
147 joinrelids = joinrel->relids;
148
149 extra.restrictlist = restrictlist;
151 extra.sjinfo = sjinfo;
152 extra.param_source_rels = NULL;
153
154 /*
155 * See if the inner relation is provably unique for this outer rel.
156 *
157 * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
158 * matter since the executor can make the equivalent optimization anyway;
159 * we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, we
160 * must be considering a semijoin whose inner side is not provably unique
161 * (else reduce_unique_semijoins would've simplified it), so there's no
162 * point in calling innerrel_is_unique. However, if the LHS covers all of
163 * the semijoin's min_lefthand, then it's appropriate to set inner_unique
164 * because the path produced by create_unique_path will be unique relative
165 * to the LHS. (If we have an LHS that's only part of the min_lefthand,
166 * that is *not* true.) For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
167 * letting that value escape this module.
168 */
169 switch (jointype)
170 {
173
174 /*
175 * XXX it may be worth proving this to allow a Memoize to be
176 * considered for Nested Loop Semi/Anti Joins.
177 */
179 break;
182 outerrel->relids);
183 break;
186 joinrel->relids,
187 outerrel->relids,
188 innerrel,
189 JOIN_INNER,
190 restrictlist,
191 false);
192 break;
193 default:
195 joinrel->relids,
196 outerrel->relids,
197 innerrel,
198 jointype,
199 restrictlist,
200 false);
201 break;
202 }
203
204 /*
205 * Find potential mergejoin clauses. We can skip this if we are not
206 * interested in doing a mergejoin. However, mergejoin may be our only
207 * way of implementing a full outer join, so override enable_mergejoin if
208 * it's a full join.
209 */
212 joinrel,
213 outerrel,
214 innerrel,
215 restrictlist,
216 jointype,
217 &mergejoin_allowed);
218
219 /*
220 * If it's SEMI, ANTI, or inner_unique join, compute correction factors
221 * for cost estimation. These will be the same for all paths.
222 */
225 jointype, sjinfo, restrictlist,
226 &extra.semifactors);
227
228 /*
229 * Decide whether it's sensible to generate parameterized paths for this
230 * joinrel, and if so, which relations such paths should require. There
231 * is usually no need to create a parameterized result path unless there
232 * is a join order restriction that prevents joining one of our input rels
233 * directly to the parameter source rel instead of joining to the other
234 * input rel. (But see allow_star_schema_join().) This restriction
235 * reduces the number of parameterized paths we have to deal with at
236 * higher join levels, without compromising the quality of the resulting
237 * plan. We express the restriction as a Relids set that must overlap the
238 * parameterization of any proposed join path. Note: param_source_rels
239 * should contain only baserels, not OJ relids, so starting from
240 * all_baserels not all_query_rels is correct.
241 */
243 {
245
246 /*
247 * SJ is relevant to this join if we have some part of its RHS
248 * (possibly not all of it), and haven't yet joined to its LHS. (This
249 * test is pretty simplistic, but should be sufficient considering the
250 * join has already been proven legal.) If the SJ is relevant, it
251 * presents constraints for joining to anything not in its RHS.
252 */
257 sjinfo2->min_righthand));
258
259 /* full joins constrain both sides symmetrically */
265 sjinfo2->min_lefthand));
266 }
267
268 /*
269 * However, when a LATERAL subquery is involved, there will simply not be
270 * any paths for the joinrel that aren't parameterized by whatever the
271 * subquery is parameterized by, unless its parameterization is resolved
272 * within the joinrel. So we might as well allow additional dependencies
273 * on whatever residual lateral dependencies the joinrel will have.
274 */
276 joinrel->lateral_relids);
277
278 /*
279 * 1. Consider mergejoin paths where both relations must be explicitly
280 * sorted. Skip this if we can't mergejoin.
281 */
282 if (mergejoin_allowed)
284 jointype, &extra);
285
286 /*
287 * 2. Consider paths where the outer relation need not be explicitly
288 * sorted. This includes both nestloops and mergejoins where the outer
289 * path is already ordered. Again, skip this if we can't mergejoin.
290 * (That's okay because we know that nestloop can't handle
291 * right/right-anti/right-semi/full joins at all, so it wouldn't work in
292 * the prohibited cases either.)
293 */
294 if (mergejoin_allowed)
296 jointype, &extra);
297
298#ifdef NOT_USED
299
300 /*
301 * 3. Consider paths where the inner relation need not be explicitly
302 * sorted. This includes mergejoins only (nestloops were already built in
303 * match_unsorted_outer).
304 *
305 * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
306 * significant difference between the inner and outer side of a mergejoin,
307 * so match_unsorted_inner creates no paths that aren't equivalent to
308 * those made by match_unsorted_outer when add_paths_to_joinrel() is
309 * invoked with the two rels given in the other order.
310 */
311 if (mergejoin_allowed)
312 match_unsorted_inner(root, joinrel, outerrel, innerrel,
313 jointype, &extra);
314#endif
315
316 /*
317 * 4. Consider paths where both outer and inner relations must be hashed
318 * before being joined. As above, disregard enable_hashjoin for full
319 * joins, because there may be no other alternative.
320 */
323 jointype, &extra);
324
325 /*
326 * 5. If inner and outer relations are foreign tables (or joins) belonging
327 * to the same server and assigned to the same user to check access
328 * permissions as, give the FDW a chance to push down joins.
329 */
330 if (joinrel->fdwroutine &&
331 joinrel->fdwroutine->GetForeignJoinPaths)
332 joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
333 outerrel, innerrel,
334 jointype, &extra);
335
336 /*
337 * 6. Finally, give extensions a chance to manipulate the path list. They
338 * could add new paths (such as CustomPaths) by calling add_path(), or
339 * add_partial_path() if parallel aware. They could also delete or modify
340 * paths added by the core code.
341 */
344 jointype, &extra);
345}
bool innerrel_is_unique(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
Definition: analyzejoins.c:1281
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:5100
static List * select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
Definition: joinpath.c:2467
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1334
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:2197
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1789
Definition: pathnodes.h:3264
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 2943 of file equivclass.c.
2945{
2946 ListCell *lc;
2948
2949 foreach(lc, child_tlist)
2950 {
2952 EquivalenceMember *parent_em;
2953 PathKey *pk;
2954
2955 if (tle->resjunk)
2956 continue;
2957
2958 if (lc2 == NULL)
2960
2962 parent_em = linitial(pk->pk_eclass->ec_members);
2963
2964 /*
2965 * We can safely pass the parent member as the first member in the
2966 * ec_members list as this is added first in generate_union_paths,
2967 * likewise, the JoinDomain can be that of the initial member of the
2968 * Pathkey's EquivalenceClass.
2969 */
2970 add_eq_member(pk->pk_eclass,
2971 tle->expr,
2972 child_rel->relids,
2973 parent_em->em_jdomain,
2974 parent_em,
2976
2977 lc2 = lnext(setop_pathkeys, lc2);
2978 }
2979
2980 /*
2981 * transformSetOperationStmt() ensures that the targetlist never contains
2982 * any resjunk columns, so all eclasses that exist in 'root' must have
2983 * received a new member in the loop above. Add them to the child_rel's
2984 * eclass_indexes.
2985 */
2988}
Bitmapset * bms_add_range(Bitmapset *a, int lower, int upper)
Definition: bitmapset.c:1019
Definition: pathnodes.h:1497
Definition: primnodes.h:2216
References add_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::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 int16 strategy;
1010 PathKey *cpathkey;
1011
1012 /* Find the operator in pg_amop --- failure shouldn't happen */
1014 &opfamily, &opcintype, &strategy))
1016 opno);
1017
1019 expr,
1020 opfamily,
1021 opcintype,
1023 (strategy == BTGreaterStrategyNumber),
1024 (strategy == BTGreaterStrategyNumber),
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, int16 *strategy)
Definition: lsyscache.c:208
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 BTGreaterStrategyNumber, 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:4375
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 1294 of file pathkeys.c.
1298{
1299 /* RIGHT_SEMI should not come here */
1301
1303 jointype == JOIN_RIGHT ||
1304 jointype == JOIN_RIGHT_ANTI)
1306
1307 /*
1308 * This used to be quite a complex bit of code, but now that all pathkey
1309 * sublists start out life canonicalized, we don't have to do a darn thing
1310 * here!
1311 *
1312 * We do, however, need to truncate the pathkeys list, since it may
1313 * contain pathkeys that were useful for forming this joinrel but are
1314 * uninteresting to higher levels.
1315 */
1317}
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:2266
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:2852
static bool partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:844
Definition: pathnodes.h:613
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 471 of file equivclass.c.
472{
474
475 /*
476 * For a polymorphic-input-type opclass, just keep the same exposed type.
477 * RECORD opclasses work like polymorphic-type ones for this purpose.
478 */
479 if (IsPolymorphicType(req_type) || req_type == RECORDOID)
480 req_type = expr_type;
481
482 /*
483 * No work if the expression exposes the right type/collation already.
484 */
485 if (expr_type != req_type ||
487 {
488 /*
489 * If we have to change the type of the expression, set typmod to -1,
490 * since the new type may not have the same typmod interpretation.
491 * When we only have to change collation, preserve the exposed typmod.
492 */
493 int32 req_typmod;
494
495 if (expr_type != req_type)
496 req_typmod = -1;
497 else
499
500 /*
501 * Use applyRelabelType so that we preserve const-flatness. This is
502 * important since eval_const_expressions has already been applied.
503 */
505 req_type, req_typmod, req_collation,
507 }
508
509 return expr;
510}
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 3966 of file indxpath.c.
3967{
3968 List *clauselist;
3969 bool have_partial;
3970 bool is_target_rel;
3971 Relids otherrels;
3972 ListCell *lc;
3973
3974 /* Indexes are available only on base or "other" member relations. */
3976
3977 /*
3978 * Initialize the indrestrictinfo lists to be identical to
3979 * baserestrictinfo, and check whether there are any partial indexes. If
3980 * not, this is all we need to do.
3981 */
3982 have_partial = false;
3984 {
3986
3989 have_partial = true;
3990 }
3991 if (!have_partial)
3992 return;
3993
3994 /*
3995 * Construct a list of clauses that we can assume true for the purpose of
3996 * proving the index(es) usable. Restriction clauses for the rel are
3997 * always usable, and so are any join clauses that are "movable to" this
3998 * rel. Also, we can consider any EC-derivable join clauses (which must
3999 * be "movable to" this rel, by definition).
4000 */
4002
4003 /* Scan the rel's join clauses */
4005 {
4007
4008 /* Check if clause can be moved to this rel */
4010 continue;
4011
4012 clauselist = lappend(clauselist, rinfo);
4013 }
4014
4015 /*
4016 * Add on any equivalence-derivable join clauses. Computing the correct
4017 * relid sets for generate_join_implied_equalities is slightly tricky
4018 * because the rel could be a child rel rather than a true baserel, and in
4019 * that case we must subtract its parents' relid(s) from all_query_rels.
4020 * Additionally, we mustn't consider clauses that are only computable
4021 * after outer joins that can null the rel.
4022 */
4026 else
4029
4031 clauselist =
4032 list_concat(clauselist,
4035 otherrels),
4036 otherrels,
4037 rel,
4038 NULL));
4039
4040 /*
4041 * Normally we remove quals that are implied by a partial index's
4042 * predicate from indrestrictinfo, indicating that they need not be
4043 * checked explicitly by an indexscan plan using this index. However, if
4044 * the rel is a target relation of UPDATE/DELETE/MERGE/SELECT FOR UPDATE,
4045 * we cannot remove such quals from the plan, because they need to be in
4046 * the plan so that they will be properly rechecked by EvalPlanQual
4047 * testing. Some day we might want to remove such quals from the main
4048 * plan anyway and pass them through to EvalPlanQual via a side channel;
4049 * but for now, we just don't remove implied quals at all for target
4050 * relations.
4051 */
4054
4055 /*
4056 * Now try to prove each index predicate true, and compute the
4057 * indrestrictinfo lists for partial indexes. Note that we compute the
4058 * indrestrictinfo list even for non-predOK indexes; this might seem
4059 * wasteful, but we may be able to use such indexes in OR clauses, cf
4060 * generate_bitmap_or_paths().
4061 */
4063 {
4065 ListCell *lcr;
4066
4068 continue; /* ignore non-partial indexes here */
4069
4072 false);
4073
4074 /* If rel is an update target, leave indrestrictinfo as set above */
4075 if (is_target_rel)
4076 continue;
4077
4078 /* Else compute indrestrictinfo as the non-implied quals */
4081 {
4083
4084 /* predicate_implied_by() assumes first arg is immutable */
4089 }
4090 }
4091}
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:1161
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo)
Definition: equivclass.c:1386
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:503
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:1509
bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
Definition: restrictinfo.c:575
Definition: pathnodes.h:1138
Definition: pathnodes.h:2593
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 4236 of file allpaths.c.
4238{
4239 int parallel_workers = 0;
4240
4241 /*
4242 * If the user has set the parallel_workers reloption, use that; otherwise
4243 * select a default number of workers.
4244 */
4246 parallel_workers = rel->rel_parallel_workers;
4247 else
4248 {
4249 /*
4250 * If the number of pages being scanned is insufficient to justify a
4251 * parallel scan, just return zero ... unless it's an inheritance
4252 * child. In that case, we want to generate a parallel path here
4253 * anyway. It might not be worthwhile just for this relation, but
4254 * when combined with all of its inheritance siblings it may well pay
4255 * off.
4256 */
4258 ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
4259 (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
4260 return 0;
4261
4262 if (heap_pages >= 0)
4263 {
4264 int heap_parallel_threshold;
4265 int heap_parallel_workers = 1;
4266
4267 /*
4268 * Select the number of workers based on the log of the size of
4269 * the relation. This probably needs to be a good deal more
4270 * sophisticated, but we need something here for now. Note that
4271 * the upper limit of the min_parallel_table_scan_size GUC is
4272 * chosen to prevent overflow here.
4273 */
4276 {
4277 heap_parallel_workers++;
4278 heap_parallel_threshold *= 3;
4279 if (heap_parallel_threshold > INT_MAX / 3)
4280 break; /* avoid overflow */
4281 }
4282
4283 parallel_workers = heap_parallel_workers;
4284 }
4285
4286 if (index_pages >= 0)
4287 {
4288 int index_parallel_workers = 1;
4289 int index_parallel_threshold;
4290
4291 /* same calculation as for heap_pages above */
4294 {
4295 index_parallel_workers++;
4296 index_parallel_threshold *= 3;
4297 if (index_parallel_threshold > INT_MAX / 3)
4298 break; /* avoid overflow */
4299 }
4300
4301 if (parallel_workers > 0)
4302 parallel_workers = Min(parallel_workers, index_parallel_workers);
4303 else
4304 parallel_workers = index_parallel_workers;
4305 }
4306 }
4307
4308 /* In no case use more than caller supplied maximum number of workers */
4309 parallel_workers = Min(parallel_workers, max_workers);
4310
4311 return parallel_workers;
4312}
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(), 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_strategy,
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
1147 {
1152 ListCell *k;
1153
1155 continue; /* ignore children here */
1156
1157 foreach(k, subquery_tlist)
1158 {
1160 Var *outer_var;
1161 Expr *tle_expr;
1162 EquivalenceClass *outer_ec;
1163 PathKey *outer_pk;
1164 int score;
1165
1166 /* Is TLE actually available to the outer query? */
1167 outer_var = find_var_for_subquery_tle(rel, tle);
1168 if (!outer_var)
1169 continue;
1170
1171 /*
1172 * The targetlist entry is considered to match if it
1173 * matches after sort-key canonicalization. That is
1174 * needed since the sub_expr has been through the same
1175 * process.
1176 */
1178 sub_expr_type,
1179 sub_expr_coll);
1181 continue;
1182
1183 /* See if we have a matching EC for the TLE */
1185 (Expr *) outer_var,
1186 sub_eclass->ec_opfamilies,
1187 sub_expr_type,
1188 sub_expr_coll,
1189 0,
1190 rel->relids,
1191 false);
1192
1193 /*
1194 * If we don't find a matching EC, this sub-pathkey isn't
1195 * interesting to the outer query
1196 */
1197 if (!outer_ec)
1198 continue;
1199
1201 outer_ec,
1202 sub_pathkey->pk_opfamily,
1203 sub_pathkey->pk_strategy,
1204 sub_pathkey->pk_nulls_first);
1205 /* score = # of equivalence peers */
1207 /* +1 if it matches the proper query_pathkeys item */
1208 if (retvallen < outer_query_keys &&
1210 score++;
1211 if (score > best_score)
1212 {
1213 best_pathkey = outer_pk;
1214 best_score = score;
1215 }
1216 }
1217 }
1218 }
1219
1220 /*
1221 * If we couldn't find a representation of this sub_pathkey, we're
1222 * done (we can't use the ones to its right, either).
1223 */
1224 if (!best_pathkey)
1225 break;
1226
1227 /*
1228 * Eliminate redundant ordering info; could happen if outer query
1229 * equivalences subquery keys...
1230 */
1232 {
1233 retval = lappend(retval, best_pathkey);
1234 retvallen++;
1235 }
1236 }
1237
1238 return retval;
1239}
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:586
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:471
static Var * find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
Definition: pathkeys.c:1251
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:56
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_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, 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 241 of file indxpath.c.
242{
243 List *indexpaths;
244 List *bitindexpaths;
245 List *bitjoinpaths;
246 List *joinorclauses;
247 IndexClauseSet rclauseset;
248 IndexClauseSet jclauseset;
249 IndexClauseSet eclauseset;
250 ListCell *lc;
251
252 /* Skip the whole mess if no indexes */
254 return;
255
256 /* Bitmap paths are collected and then dealt with at the end */
257 bitindexpaths = bitjoinpaths = joinorclauses = NIL;
258
259 /* Examine each index in turn */
261 {
263
264 /* Protect limited-size array in IndexClauseSets */
266
267 /*
268 * Ignore partial indexes that do not match the query.
269 * (generate_bitmap_or_paths() might be able to do something with
270 * them, but that's of no concern here.)
271 */
273 continue;
274
275 /*
276 * Identify the restriction clauses that can match the index.
277 */
280
281 /*
282 * Build index paths from the restriction clauses. These will be
283 * non-parameterized paths. Plain paths go directly to add_path(),
284 * bitmap paths are added to bitindexpaths to be handled below.
285 */
287 &bitindexpaths);
288
289 /*
290 * Identify the join clauses that can match the index. For the moment
291 * we keep them separate from the restriction clauses. Note that this
292 * step finds only "loose" join clauses that have not been merged into
293 * EquivalenceClasses. Also, collect join OR clauses for later.
294 */
297 &jclauseset, &joinorclauses);
298
299 /*
300 * Look for EquivalenceClasses that can generate joinclauses matching
301 * the index.
302 */
305 &eclauseset);
306
307 /*
308 * If we found any plain or eclass join clauses, build parameterized
309 * index paths using them.
310 */
313 &rclauseset,
314 &jclauseset,
315 &eclauseset,
316 &bitjoinpaths);
317 }
318
319 /*
320 * Generate BitmapOrPaths for any suitable OR-clauses present in the
321 * restriction list. Add these to bitindexpaths.
322 */
325 bitindexpaths = list_concat(bitindexpaths, indexpaths);
326
327 /*
328 * Likewise, generate BitmapOrPaths for any suitable OR-clauses present in
329 * the joinclause list. Add these to bitjoinpaths.
330 */
332 joinorclauses, rel->baserestrictinfo);
333 bitjoinpaths = list_concat(bitjoinpaths, indexpaths);
334
335 /*
336 * If we found anything usable, generate a BitmapHeapPath for the most
337 * promising combination of restriction bitmap index paths. Note there
338 * will be only one such path no matter how many indexes exist. This
339 * should be sufficient since there's basically only one figure of merit
340 * (total cost) for such a path.
341 */
343 {
344 Path *bitmapqual;
345 BitmapHeapPath *bpath;
346
349 rel->lateral_relids, 1.0, 0);
351
352 /* create a partial bitmap heap path */
355 }
356
357 /*
358 * Likewise, if we found anything usable, generate BitmapHeapPaths for the
359 * most promising combinations of join bitmap index paths. Our strategy
360 * is to generate one such path for each distinct parameterization seen
361 * among the available bitmap index paths. This may look pretty
362 * expensive, but usually there won't be very many distinct
363 * parameterizations. (This logic is quite similar to that in
364 * consider_index_join_clauses, but we're working with whole paths not
365 * individual clauses.)
366 */
368 {
369 List *all_path_outers;
370
371 /* Identify each distinct parameterization seen in bitjoinpaths */
372 all_path_outers = NIL;
373 foreach(lc, bitjoinpaths)
374 {
377
378 all_path_outers = list_append_unique(all_path_outers,
379 required_outer);
380 }
381
382 /* Now, for each distinct parameterization set ... */
383 foreach(lc, all_path_outers)
384 {
386 List *this_path_set;
387 Path *bitmapqual;
388 Relids required_outer;
389 double loop_count;
390 BitmapHeapPath *bpath;
391 ListCell *lcp;
392
393 /* Identify all the bitmap join paths needing no more than that */
394 this_path_set = NIL;
395 foreach(lcp, bitjoinpaths)
396 {
398
400 this_path_set = lappend(this_path_set, path);
401 }
402
403 /*
404 * Add in restriction bitmap paths, since they can be used
405 * together with any join paths.
406 */
407 this_path_set = list_concat(this_path_set, bitindexpaths);
408
409 /* Select best AND combination for this parameterization */
411
412 /* And push that path into the mix */
413 required_outer = PATH_REQ_OUTER(bitmapqual);
416 required_outer, loop_count, 0);
418 }
419 }
420}
void create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual)
Definition: allpaths.c:4200
static Path * choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
Definition: indxpath.c:1729
static void match_join_clauses_to_index(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauseset, List **joinorclauses)
Definition: indxpath.c:2426
static void match_eclass_clauses_to_index(PlannerInfo *root, IndexOptInfo *index, IndexClauseSet *clauseset)
Definition: indxpath.c:2460
static void get_index_paths(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauses, List **bitindexpaths)
Definition: indxpath.c:717
static double get_loop_count(PlannerInfo *root, Index cur_relid, Relids outer_relids)
Definition: indxpath.c:2271
static void consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *rclauseset, IndexClauseSet *jclauseset, IndexClauseSet *eclauseset, List **bitindexpaths)
Definition: indxpath.c:438
static void match_restriction_clauses_to_index(PlannerInfo *root, IndexOptInfo *index, IndexClauseSet *clauseset)
Definition: indxpath.c:2410
static List * generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel, List *clauses, List *other_clauses)
Definition: indxpath.c:1573
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:1819
Definition: indxpath.c:56
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 4200 of file allpaths.c.
4202{
4203 int parallel_workers;
4204 double pages_fetched;
4205
4206 /* Compute heap pages for bitmap heap scan */
4208 NULL, NULL);
4209
4210 parallel_workers = compute_parallel_worker(rel, pages_fetched, -1,
4212
4213 if (parallel_workers <= 0)
4214 return;
4215
4217 bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
4218}
int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
Definition: allpaths.c:4236
double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, double loop_count, Cost *cost_p, double *tuples_p)
Definition: costsize.c:6499
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 498 of file tidpath.c.
499{
500 List *tidquals;
501 List *tidrangequals;
502 bool isCurrentOf;
503
504 /*
505 * If any suitable quals exist in the rel's baserestrict list, generate a
506 * plain (unparameterized) TidPath with them.
507 *
508 * We skip this when enable_tidscan = false, except when the qual is
509 * CurrentOfExpr. In that case, a TID scan is the only correct path.
510 */
512 &isCurrentOf);
513
515 {
516 /*
517 * This path uses no join clauses, but it could still have required
518 * parameterization due to LATERAL refs in its tlist.
519 */
521
523 required_outer));
524
525 /*
526 * When the qual is CurrentOfExpr, the path that we just added is the
527 * only one the executor can handle, so we should return before adding
528 * any others. Returning true lets the caller know not to add any
529 * others, either.
530 */
531 if (isCurrentOf)
532 return true;
533 }
534
535 /* Skip the rest if TID scans are disabled. */
537 return false;
538
539 /*
540 * If there are range quals in the baserestrict list, generate a
541 * TidRangePath.
542 */
544 rel);
545
547 {
548 /*
549 * This path uses no join clauses, but it could still have required
550 * parameterization due to LATERAL refs in its tlist.
551 */
553
555 tidrangequals,
556 required_outer));
557 }
558
559 /*
560 * Try to generate parameterized TidPaths using equality clauses extracted
561 * from EquivalenceClasses. (This is important since simple "t1.ctid =
562 * t2.ctid" clauses will turn into ECs.)
563 */
565 {
566 List *clauses;
567
568 /* Generate clauses, skipping any that join to lateral_referencers */
570 rel,
572 NULL,
573 rel->lateral_referencers);
574
575 /* Generate a path for each usable join clause */
577 }
578
579 /*
580 * Also consider parameterized TidPaths using "loose" join quals. Quals
581 * of the form "t1.ctid = t2.ctid" would turn into these if they are outer
582 * join quals, for example.
583 */
585
586 return false;
587}
List * generate_implied_equalities_for_column(PlannerInfo *root, RelOptInfo *rel, ec_matches_callback_type callback, void *callback_arg, Relids prohibited_rels)
Definition: equivclass.c:3015
TidRangePath * create_tidrangescan_path(PlannerInfo *root, RelOptInfo *rel, List *tidrangequals, Relids required_outer)
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_path(), RelOptInfo::baserestrictinfo, BuildParameterizedTidPaths(), 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, NIL, root, TidQualFromRestrictInfoList(), and TidRangeQualFromRestrictInfoList().
Referenced by set_plain_rel_pathlist().
◆ eclass_useful_for_merging()
| bool eclass_useful_for_merging | ( | PlannerInfo * | root, |
| EquivalenceClass * | eclass, | ||
| RelOptInfo * | rel | ||
| ) |
Definition at line 3267 of file equivclass.c.
3270{
3271 Relids relids;
3272 ListCell *lc;
3273
3275
3276 /*
3277 * Won't generate joinclauses if const or single-member (the latter test
3278 * covers the volatile case too)
3279 */
3281 return false;
3282
3283 /*
3284 * Note we don't test ec_broken; if we did, we'd need a separate code path
3285 * to look through ec_sources. Checking the members anyway is OK as a
3286 * possibly-overoptimistic heuristic.
3287 */
3288
3289 /* If specified rel is a child, we must consider the topmost parent rel */
3291 {
3293 relids = rel->top_parent_relids;
3294 }
3295 else
3296 relids = rel->relids;
3297
3298 /* If rel already includes all members of eclass, no point in searching */
3300 return false;
3301
3302 /* To join, we need a member not in the given rel */
3304 {
3306
3308 continue; /* ignore children here */
3309
3311 return true;
3312 }
3313
3314 return false;
3315}
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 2499 of file equivclass.c.
2500{
2501 ListCell *lc1;
2502
2504 {
2506 bool item1member = false;
2507 bool item2member = false;
2508 ListCell *lc2;
2509
2510 /* Never match to a volatile EC */
2512 continue;
2513
2514 /*
2515 * It's okay to consider ec_broken ECs here. Brokenness just means we
2516 * couldn't derive all the implied clauses we'd have liked to; it does
2517 * not invalidate our knowledge that the members are equal.
2518 */
2519
2520 /* Ignore if this EC doesn't use specified opfamily */
2523 continue;
2524
2526 {
2528
2530 continue; /* ignore children here */
2532 item1member = true;
2534 item2member = true;
2535 /* Exit as soon as equality is proven */
2536 if (item1member && item2member)
2537 return true;
2538 }
2539 }
2540 return false;
2541}
References 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 837 of file equivclass.c.
842{
843 List *exprvars;
844 ListCell *lc;
845
846 /*
847 * Pull out the Vars and quasi-Vars present in "exprs". In the typical
848 * non-appendrel case, this is just another representation of the same
849 * list. However, it does remove the distinction between the case of a
850 * list of plain expressions and a list of TargetEntrys.
851 */
853 PVC_INCLUDE_AGGREGATES |
854 PVC_INCLUDE_WINDOWFUNCS |
855 PVC_INCLUDE_PLACEHOLDERS |
857
859 {
861 List *emvars;
862 ListCell *lc2;
863
864 /*
865 * We shouldn't be trying to sort by an equivalence class that
866 * contains a constant, so no need to consider such cases any further.
867 */
869 continue;
870
871 /*
872 * Ignore child members unless they belong to the requested rel.
873 */
876 continue;
877
878 /*
879 * Match if all Vars and quasi-Vars are present in "exprs".
880 */
882 PVC_INCLUDE_AGGREGATES |
883 PVC_INCLUDE_WINDOWFUNCS |
884 PVC_INCLUDE_PLACEHOLDERS);
885 foreach(lc2, emvars)
886 {
888 break;
889 }
890 list_free(emvars);
891 if (lc2)
892 continue; /* we hit a non-available Var */
893
894 /*
895 * If requested, reject expressions that are not parallel-safe. We
896 * check this last because it's a rather expensive test.
897 */
898 if (require_parallel_safe &&
900 continue;
901
902 return em; /* found usable expression */
903 }
904
905 return NULL;
906}
References bms_is_subset(), EquivalenceClass::ec_members, 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, and root.
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 | ( | EquivalenceClass * | ec, |
| EquivalenceMember * | em | ||
| ) |
Definition at line 2651 of file equivclass.c.
2653{
2654 ListCell *lc;
2655
2659 {
2661
2662 /*
2663 * generate_base_implied_equalities_const will have put non-const
2664 * members on the left side of derived clauses.
2665 */
2666 if (rinfo->left_em == em)
2667 return rinfo;
2668 }
2669 return NULL;
2670}
References Assert(), EquivalenceClass::ec_derives, EquivalenceClass::ec_has_const, EquivalenceMember::em_is_const, and lfirst.
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 763 of file equivclass.c.
766{
767 ListCell *lc;
768
769 /* We ignore binary-compatible relabeling on both ends */
771 expr = ((RelabelType *) expr)->arg;
772
774 {
776 Expr *emexpr;
777
778 /*
779 * We shouldn't be trying to sort by an equivalence class that
780 * contains a constant, so no need to consider such cases any further.
781 */
783 continue;
784
785 /*
786 * Ignore child members unless they belong to the requested rel.
787 */
790 continue;
791
792 /*
793 * Match if same expression (after stripping relabel).
794 */
795 emexpr = em->em_expr;
798
800 return em;
801 }
802
803 return NULL;
804}
Definition: primnodes.h:1199
References arg, bms_is_subset(), EquivalenceClass::ec_members, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, equal(), IsA, and lfirst.
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 1543 of file pathkeys.c.
1546{
1549
1550 /* make sure we have eclasses cached in the clauses */
1552 {
1554
1556 }
1557
1559 {
1561 EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1564
1565 /*----------
1566 * A mergejoin clause matches a pathkey if it has the same EC.
1567 * If there are multiple matching clauses, take them all. In plain
1568 * inner-join scenarios we expect only one match, because
1569 * equivalence-class processing will have removed any redundant
1570 * mergeclauses. However, in outer-join scenarios there might be
1571 * multiple matches. An example is
1572 *
1573 * select * from a full join b
1574 * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1575 *
1576 * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1577 * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1578 * we *must* do so or we will be unable to form a valid plan.
1579 *
1580 * We expect that the given pathkeys list is canonical, which means
1581 * no two members have the same EC, so it's not possible for this
1582 * code to enter the same mergeclause into the result list twice.
1583 *
1584 * It's possible that multiple matching clauses might have different
1585 * ECs on the other side, in which case the order we put them into our
1586 * result makes a difference in the pathkeys required for the inner
1587 * input rel. However this routine hasn't got any info about which
1588 * order would be best, so we don't worry about that.
1589 *
1590 * It's also possible that the selected mergejoin clauses produce
1591 * a noncanonical ordering of pathkeys for the inner side, ie, we
1592 * might select clauses that reference b.v1, b.v2, b.v1 in that
1593 * order. This is not harmful in itself, though it suggests that
1594 * the clauses are partially redundant. Since the alternative is
1595 * to omit mergejoin clauses and thereby possibly fail to generate a
1596 * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1597 * has to delete duplicates when it constructs the inner pathkeys
1598 * list, and we also have to deal with such cases specially in
1599 * create_mergejoin_plan().
1600 *----------
1601 */
1603 {
1605 EquivalenceClass *clause_ec;
1606
1607 clause_ec = rinfo->outer_is_left ?
1608 rinfo->left_ec : rinfo->right_ec;
1609 if (clause_ec == pathkey_ec)
1610 matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1611 }
1612
1613 /*
1614 * If we didn't find a mergeclause, we're done --- any additional
1615 * sort-key positions in the pathkeys are useless. (But we can still
1616 * mergejoin if we found at least one mergeclause.)
1617 */
1619 break;
1620
1621 /*
1622 * If we did find usable mergeclause(s) for this sort-key position,
1623 * add them to result list.
1624 */
1625 mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1626 }
1627
1628 return mergeclauses;
1629}
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1509
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 1033 of file equivclass.c.
1034{
1035 int ec_index;
1036 ListCell *lc;
1037
1038 /*
1039 * At this point, we're done absorbing knowledge of equivalences in the
1040 * query, so no further EC merging should happen, and ECs remaining in the
1041 * eq_classes list can be considered canonical. (But note that it's still
1042 * possible for new single-member ECs to be added through
1043 * get_eclass_for_sort_expr().)
1044 */
1046
1047 ec_index = 0;
1049 {
1051 bool can_generate_joinclause = false;
1053
1056
1057 /*
1058 * Generate implied equalities that are restriction clauses.
1059 * Single-member ECs won't generate any deductions, either here or at
1060 * the join level.
1061 */
1063 {
1066 else
1068
1069 /* Recover if we failed to generate required derived clauses */
1072
1073 /* Detect whether this EC might generate join clauses */
1074 can_generate_joinclause =
1076 }
1077
1078 /*
1079 * Mark the base rels cited in each eclass (which should all exist by
1080 * now) with the eq_classes indexes of all eclasses mentioning them.
1081 * This will let us avoid searching in subsequent lookups. While
1082 * we're at it, we can mark base rels that have pending eclass joins;
1083 * this is a cheap version of has_relevant_eclass_joinclause().
1084 */
1085 i = -1;
1087 {
1089
1090 /* ignore the RTE_GROUP RTE */
1092 continue;
1093
1094 if (rel == NULL) /* must be an outer join */
1095 {
1097 continue;
1098 }
1099
1101
1103 ec_index);
1104
1105 if (can_generate_joinclause)
1107 }
1108
1109 ec_index++;
1110 }
1111}
static void generate_base_implied_equalities_broken(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1323
static void generate_base_implied_equalities_no_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1212
static void generate_base_implied_equalities_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1117
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 3085 of file allpaths.c.
3086{
3087 Path *cheapest_partial_path;
3088 Path *simple_gather_path;
3089 ListCell *lc;
3090 double rows;
3091 double *rowsp = NULL;
3092
3093 /* If there are no partial paths, there's nothing to do here. */
3095 return;
3096
3097 /* Should we override the rel's rowcount estimate? */
3098 if (override_rows)
3099 rowsp = &rows;
3100
3101 /*
3102 * The output of Gather is always unsorted, so there's only one partial
3103 * path of interest: the cheapest one. That will be the one at the front
3104 * of partial_pathlist because of the way add_partial_path works.
3105 */
3107 rows = compute_gather_rows(cheapest_partial_path);
3108 simple_gather_path = (Path *)
3110 NULL, rowsp);
3111 add_path(rel, simple_gather_path);
3112
3113 /*
3114 * For each useful ordering, we can consider an order-preserving Gather
3115 * Merge.
3116 */
3118 {
3120 GatherMergePath *path;
3121
3123 continue;
3124
3127 subpath->pathkeys, NULL, rowsp);
3129 }
3130}
GatherMergePath * create_gather_merge_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, List *pathkeys, Relids required_outer, double *rows)
Definition: pathnode.c:1962
GatherPath * create_gather_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, Relids required_outer, double *rows)
Definition: pathnode.c:2044
Definition: pathnodes.h:2088
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_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 3015 of file equivclass.c.
3020{
3023 Relids parent_relids;
3025
3026 /* Should be OK to rely on eclass_indexes */
3028
3029 /* Indexes are available only on base or "other" member relations. */
3031
3032 /* If it's a child rel, we'll need to know what its parent(s) are */
3033 if (is_child_rel)
3035 else
3036 parent_relids = NULL; /* not used, but keep compiler quiet */
3037
3038 i = -1;
3040 {
3042 EquivalenceMember *cur_em;
3043 ListCell *lc2;
3044
3045 /* Sanity check eclass_indexes only contain ECs for rel */
3047
3048 /*
3049 * Won't generate joinclauses if const or single-member (the latter
3050 * test covers the volatile case too)
3051 */
3053 continue;
3054
3055 /*
3056 * Scan members, looking for a match to the target column. Note that
3057 * child EC members are considered, but only when they belong to the
3058 * target relation. (Unlike regular members, the same expression
3059 * could be a child member of more than one EC. Therefore, it's
3060 * potentially order-dependent which EC a child relation's target
3061 * column gets matched to. This is annoying but it only happens in
3062 * corner cases, so for now we live with just reporting the first
3063 * match. See also get_eclass_for_sort_expr.)
3064 */
3065 cur_em = NULL;
3067 {
3071 break;
3072 cur_em = NULL;
3073 }
3074
3075 if (!cur_em)
3076 continue;
3077
3078 /*
3079 * Found our match. Scan the other EC members and attempt to generate
3080 * joinclauses.
3081 */
3083 {
3085 Oid eq_op;
3086 RestrictInfo *rinfo;
3087
3089 continue; /* ignore children here */
3090
3091 /* Make sure it'll be a join to a different rel */
3092 if (other_em == cur_em ||
3094 continue;
3095
3096 /* Forget it if caller doesn't want joins to this rel */
3098 continue;
3099
3100 /*
3101 * Also, if this is a child rel, avoid generating a useless join
3102 * to its parent rel(s).
3103 */
3104 if (is_child_rel &&
3106 continue;
3107
3108 eq_op = select_equality_operator(cur_ec,
3109 cur_em->em_datatype,
3110 other_em->em_datatype);
3112 continue;
3113
3114 /* set parent_ec to mark as redundant with other joinclauses */
3116 cur_em, other_em,
3117 cur_ec);
3118
3119 result = lappend(result, rinfo);
3120 }
3121
3122 /*
3123 * If somehow we failed to create any join clauses, we might as well
3124 * keep scanning the ECs for another match. But if we did make any,
3125 * we're done, because we don't want to return non-redundant clauses.
3126 */
3127 if (result)
3128 break;
3129 }
3130
3131 return result;
3132}
static RestrictInfo * create_join_clause(PlannerInfo *root, EquivalenceClass *ec, Oid opno, EquivalenceMember *leftem, EquivalenceMember *rightem, EquivalenceClass *parent_ec)
Definition: equivclass.c:1818
static Oid select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype)
Definition: equivclass.c:1782
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, 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, and select_equality_operator().
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 1386 of file equivclass.c.
1391{
1394 Relids nominal_inner_relids;
1395 Relids nominal_join_relids;
1396 Bitmapset *matching_ecs;
1398
1399 /* If inner rel is a child, extra setup work is needed */
1401 {
1403
1404 /* Fetch relid set for the topmost parent rel */
1405 nominal_inner_relids = inner_rel->top_parent_relids;
1406 /* ECs will be marked with the parent's relid, not the child's */
1407 nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1409 nominal_join_relids,
1410 sjinfo,
1411 NULL);
1412 }
1413 else
1414 {
1415 nominal_inner_relids = inner_relids;
1416 nominal_join_relids = join_relids;
1417 }
1418
1419 /*
1420 * Examine all potentially-relevant eclasses.
1421 *
1422 * If we are considering an outer join, we must include "join" clauses
1423 * that mention either input rel plus the outer join's relid; these
1424 * represent post-join filter clauses that have to be applied at this
1425 * join. We don't have infrastructure that would let us identify such
1426 * eclasses cheaply, so just fall back to considering all eclasses
1427 * mentioning anything in nominal_join_relids.
1428 *
1429 * At inner joins, we can be smarter: only consider eclasses mentioning
1430 * both input rels.
1431 */
1434 else
1436 outer_relids);
1437
1438 i = -1;
1440 {
1443
1444 /* ECs containing consts do not need any further enforcement */
1446 continue;
1447
1448 /* Single-member ECs won't generate any deductions */
1450 continue;
1451
1452 /* Sanity check that this eclass overlaps the join */
1454
1457 ec,
1458 join_relids,
1459 outer_relids,
1460 inner_relids);
1461
1462 /* Recover if we failed to generate required derived clauses */
1465 ec,
1466 nominal_join_relids,
1467 outer_relids,
1468 nominal_inner_relids,
1469 inner_rel);
1470
1471 result = list_concat(result, sublist);
1472 }
1473
1474 return result;
1475}
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1557
static Bitmapset * get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
Definition: equivclass.c:3422
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:1733
Relids add_outer_joins_to_relids(PlannerInfo *root, Relids input_relids, SpecialJoinInfo *sjinfo, List **pushed_down_joins)
Definition: joinrels.c:802
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 1486 of file equivclass.c.
1491{
1494 Relids nominal_inner_relids;
1495 Relids nominal_join_relids;
1496 ListCell *lc;
1497
1498 /* If inner rel is a child, extra setup work is needed */
1500 {
1502
1503 /* Fetch relid set for the topmost parent rel */
1504 nominal_inner_relids = inner_rel->top_parent_relids;
1505 /* ECs will be marked with the parent's relid, not the child's */
1506 nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1507 }
1508 else
1509 {
1510 nominal_inner_relids = inner_relids;
1511 nominal_join_relids = join_relids;
1512 }
1513
1514 foreach(lc, eclasses)
1515 {
1518
1519 /* ECs containing consts do not need any further enforcement */
1521 continue;
1522
1523 /* Single-member ECs won't generate any deductions */
1525 continue;
1526
1527 /* We can quickly ignore any that don't overlap the join, too */
1529 continue;
1530
1533 ec,
1534 join_relids,
1535 outer_relids,
1536 inner_relids);
1537
1538 /* Recover if we failed to generate required derived clauses */
1541 ec,
1542 nominal_join_relids,
1543 outer_relids,
1544 nominal_inner_relids,
1545 inner_rel);
1546
1547 result = list_concat(result, sublist);
1548 }
1549
1550 return result;
1551}
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 4324 of file allpaths.c.
4325{
4327 int cnt_parts;
4328 int num_parts;
4329 RelOptInfo **part_rels;
4330
4331 /* Handle only join relations here. */
4333 return;
4334
4335 /* We've nothing to do if the relation is not partitioned. */
4337 return;
4338
4339 /* The relation should have consider_partitionwise_join set. */
4341
4342 /* Guard against stack overflow due to overly deep partition hierarchy. */
4343 check_stack_depth();
4344
4345 num_parts = rel->nparts;
4346 part_rels = rel->part_rels;
4347
4348 /* Collect non-dummy child-joins. */
4349 for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
4350 {
4351 RelOptInfo *child_rel = part_rels[cnt_parts];
4352
4353 /* If it's been pruned entirely, it's certainly dummy. */
4354 if (child_rel == NULL)
4355 continue;
4356
4357 /* Make partitionwise join paths for this partitioned child-join. */
4359
4360 /* If we failed to make any path for this child, we must give up. */
4362 {
4363 /*
4364 * Mark the parent joinrel as unpartitioned so that later
4365 * functions treat it correctly.
4366 */
4367 rel->nparts = 0;
4368 return;
4369 }
4370
4371 /* Else, identify the cheapest path for it. */
4372 set_cheapest(child_rel);
4373
4374 /* Dummy children need not be scanned, so ignore those. */
4376 continue;
4377
4378#ifdef OPTIMIZER_DEBUG
4379 pprint(child_rel);
4380#endif
4381
4382 live_children = lappend(live_children, child_rel);
4383 }
4384
4385 /* If all child-joins are dummy, parent join is also dummy. */
4386 if (!live_children)
4387 {
4388 mark_dummy_rel(rel);
4389 return;
4390 }
4391
4392 /* Build additional paths for this rel from child-join paths. */
4394 list_free(live_children);
4395}
void generate_partitionwise_join_paths(PlannerInfo *root, RelOptInfo *rel)
Definition: allpaths.c:4324
void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels)
Definition: allpaths.c:1321
References add_paths_to_append_rel(), Assert(), check_stack_depth(), RelOptInfo::consider_partitionwise_join, generate_partitionwise_join_paths(), IS_DUMMY_REL, IS_JOIN_REL, IS_PARTITIONED_REL, lappend(), list_free(), mark_dummy_rel(), NIL, RelOptInfo::nparts, RelOptInfo::pathlist, pprint(), root, and set_cheapest().
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 3222 of file allpaths.c.
3223{
3224 ListCell *lc;
3225 double rows;
3226 double *rowsp = NULL;
3228 Path *cheapest_partial_path = NULL;
3229
3230 /* If there are no partial paths, there's nothing to do here. */
3232 return;
3233
3234 /* Should we override the rel's rowcount estimate? */
3235 if (override_rows)
3236 rowsp = &rows;
3237
3238 /* generate the regular gather (merge) paths */
3240
3241 /* consider incremental sort for interesting orderings */
3243
3244 /* used for explicit (full) sort paths */
3246
3247 /*
3248 * Consider sorted paths for each interesting ordering. We generate both
3249 * incremental and full sort.
3250 */
3251 foreach(lc, useful_pathkeys_list)
3252 {
3254 ListCell *lc2;
3255 bool is_sorted;
3256 int presorted_keys;
3257
3259 {
3261 GatherMergePath *path;
3262
3263 is_sorted = pathkeys_count_contained_in(useful_pathkeys,
3264 subpath->pathkeys,
3265 &presorted_keys);
3266
3267 /*
3268 * We don't need to consider the case where a subpath is already
3269 * fully sorted because generate_gather_paths already creates a
3270 * gather merge path for every subpath that has pathkeys present.
3271 *
3272 * But since the subpath is already sorted, we know we don't need
3273 * to consider adding a sort (full or incremental) on top of it,
3274 * so we can continue here.
3275 */
3276 if (is_sorted)
3277 continue;
3278
3279 /*
3280 * Try at least sorting the cheapest path and also try
3281 * incrementally sorting any path which is partially sorted
3282 * already (no need to deal with paths which have presorted keys
3283 * when incremental sort is disabled unless it's the cheapest
3284 * input path).
3285 */
3287 (presorted_keys == 0 || !enable_incremental_sort))
3288 continue;
3289
3290 /*
3291 * Consider regular sort for any path that's not presorted or if
3292 * incremental sort is disabled. We've no need to consider both
3293 * sort and incremental sort on the same path. We assume that
3294 * incremental sort is always faster when there are presorted
3295 * keys.
3296 *
3297 * This is not redundant with the gather paths created in
3298 * generate_gather_paths, because that doesn't generate ordered
3299 * output. Here we add an explicit sort to match the useful
3300 * ordering.
3301 */
3303 {
3305 rel,
3306 subpath,
3307 useful_pathkeys,
3308 -1.0);
3309 }
3310 else
3312 rel,
3313 subpath,
3314 useful_pathkeys,
3315 presorted_keys,
3316 -1);
3319 subpath,
3320 rel->reltarget,
3321 subpath->pathkeys,
3322 NULL,
3323 rowsp);
3324
3326 }
3327 }
3328}
static List * get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel, bool require_parallel_safe)
Definition: allpaths.c:3154
void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
Definition: allpaths.c:3085
bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
Definition: pathkeys.c:558
IncrementalSortPath * create_incremental_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, int presorted_keys, double limit_tuples)
Definition: pathnode.c:3032
SortPath * create_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, double limit_tuples)
Definition: pathnode.c:3082
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(), 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:124
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:69
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 586 of file equivclass.c.
594{
595 JoinDomain *jdomain;
596 Relids expr_relids;
597 EquivalenceClass *newec;
598 EquivalenceMember *newem;
599 ListCell *lc1;
600 MemoryContext oldcontext;
601
602 /*
603 * Ensure the expression exposes the correct type and collation.
604 */
605 expr = canonicalize_ec_expression(expr, opcintype, collation);
606
607 /*
608 * Since SortGroupClause nodes are top-level expressions (GROUP BY, ORDER
609 * BY, etc), they can be presumed to belong to the top JoinDomain.
610 */
612
613 /*
614 * Scan through the existing EquivalenceClasses for a match
615 */
617 {
619 ListCell *lc2;
620
621 /*
622 * Never match to a volatile EC, except when we are looking at another
623 * reference to the same volatile SortGroupClause.
624 */
626 (sortref == 0 || sortref != cur_ec->ec_sortref))
627 continue;
628
630 continue;
632 continue;
633
635 {
637
638 /*
639 * Ignore child members unless they match the request.
640 */
643 continue;
644
645 /*
646 * Match constants only within the same JoinDomain (see
647 * optimizer/README).
648 */
650 continue;
651
654 return cur_ec; /* Match! */
655 }
656 }
657
658 /* No match; does caller want a NULL result? */
659 if (!create_it)
660 return NULL;
661
662 /*
663 * OK, build a new single-member EC
664 *
665 * Here, we must be sure that we construct the EC in the right context.
666 */
668
671 newec->ec_collation = collation;
675 newec->ec_relids = NULL;
679 newec->ec_sortref = sortref;
680 newec->ec_min_security = UINT_MAX;
681 newec->ec_max_security = 0;
682 newec->ec_merged = NULL;
683
686
687 /*
688 * Get the precise set of relids appearing in the expression.
689 */
691
693 jdomain, NULL, opcintype);
694
695 /*
696 * add_eq_member doesn't check for volatile functions, set-returning
697 * functions, aggregates, or window functions, but such could appear in
698 * sort expressions; so we have to check whether its const-marking was
699 * correct.
700 */
702 {
707 {
710 }
711 }
712
714
715 /*
716 * If EC merging is already complete, we have to mop up by adding the new
717 * EC to the eclass_indexes of the relation(s) mentioned in it.
718 */
720 {
723
725 {
727
728 /* ignore the RTE_GROUP RTE */
730 continue;
731
732 if (rel == NULL) /* must be an outer join */
733 {
735 continue;
736 }
737
739
741 ec_index);
742 }
743 }
744
745 MemoryContextSwitchTo(oldcontext);
746
747 return newec;
748}
Definition: pathnodes.h:1351
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_collation, EquivalenceClass::ec_derives, 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, 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, and root.
Referenced by convert_subquery_pathkeys(), 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:1519
Definition: parsenodes.h:118
Definition: parsenodes.h:1445
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 3223 of file equivclass.c.
3224{
3225 Bitmapset *matched_ecs;
3227
3228 /* Examine only eclasses mentioning rel1 */
3230
3231 i = -1;
3233 {
3235 i);
3236
3237 /*
3238 * Won't generate joinclauses if single-member (this test covers the
3239 * volatile case too)
3240 */
3242 continue;
3243
3244 /*
3245 * Per the comment in have_relevant_eclass_joinclause, it's sufficient
3246 * to find an EC that mentions both this rel and some other rel.
3247 */
3249 return true;
3250 }
3251
3252 return false;
3253}
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 2315 of file pathkeys.c.
2316{
2318 return true; /* might be able to use pathkeys for merging */
2320 return true; /* might be able to use pathkeys for grouping */
2322 return true; /* might be able to use them for ordering */
2323 return false; /* definitely useless */
2324}
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_dangerous_phv()
| bool have_dangerous_phv | ( | PlannerInfo * | root, |
| Relids | outer_relids, | ||
| Relids | inner_params | ||
| ) |
Definition at line 1308 of file joinrels.c.
1310{
1311 ListCell *lc;
1312
1314 {
1316
1318 continue; /* ignore, could not be a nestloop param */
1320 continue; /* ignore, not relevant to this join */
1322 continue; /* safe, it can be eval'd within outerrel */
1323 /* Otherwise, it's potentially unsafe, so reject the join */
1324 return true;
1325 }
1326
1327 /* OK to perform the join */
1328 return false;
1329}
Definition: pathnodes.h:3108
References bms_is_subset(), bms_overlap(), lfirst, PlaceHolderInfo::ph_eval_at, and root.
Referenced by join_is_legal(), and try_nestloop_path().
◆ have_join_order_restriction()
| bool have_join_order_restriction | ( | PlannerInfo * | root, |
| RelOptInfo * | rel1, | ||
| RelOptInfo * | rel2 | ||
| ) |
Definition at line 1075 of file joinrels.c.
1077{
1078 bool result = false;
1079 ListCell *l;
1080
1081 /*
1082 * If either side has a direct lateral reference to the other, attempt the
1083 * join regardless of outer-join considerations.
1084 */
1087 return true;
1088
1089 /*
1090 * Likewise, if both rels are needed to compute some PlaceHolderVar,
1091 * attempt the join regardless of outer-join considerations. (This is not
1092 * very desirable, because a PHV with a large eval_at set will cause a lot
1093 * of probably-useless joins to be considered, but failing to do this can
1094 * cause us to fail to construct a plan at all.)
1095 */
1097 {
1099
1102 return true;
1103 }
1104
1105 /*
1106 * It's possible that the rels correspond to the left and right sides of a
1107 * degenerate outer join, that is, one with no joinclause mentioning the
1108 * non-nullable side; in which case we should force the join to occur.
1109 *
1110 * Also, the two rels could represent a clauseless join that has to be
1111 * completed to build up the LHS or RHS of an outer join.
1112 */
1114 {
1116
1117 /* ignore full joins --- other mechanisms handle them */
1119 continue;
1120
1121 /* Can we perform the SJ with these rels? */
1124 {
1125 result = true;
1126 break;
1127 }
1130 {
1131 result = true;
1132 break;
1133 }
1134
1135 /*
1136 * Might we need to join these rels to complete the RHS? We have to
1137 * use "overlap" tests since either rel might include a lower SJ that
1138 * has been proven to commute with this one.
1139 */
1142 {
1143 result = true;
1144 break;
1145 }
1146
1147 /* Likewise for the LHS. */
1150 {
1151 result = true;
1152 break;
1153 }
1154 }
1155
1156 /*
1157 * We do not force the join to occur if either input rel can legally be
1158 * joined to anything else using joinclauses. This essentially means that
1159 * clauseless bushy joins are put off as long as possible. The reason is
1160 * that when there is a join order restriction high up in the join tree
1161 * (that is, with many rels inside the LHS or RHS), we would otherwise
1162 * expend lots of effort considering very stupid join combinations within
1163 * its LHS or RHS.
1164 */
1165 if (result)
1166 {
1169 result = false;
1170 }
1171
1172 return result;
1173}
static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1244
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 3147 of file equivclass.c.
3149{
3150 Bitmapset *matching_ecs;
3152
3153 /*
3154 * Examine only eclasses mentioning both rel1 and rel2.
3155 *
3156 * Note that we do not consider the possibility of an eclass generating
3157 * "join" clauses that mention just one of the rels plus an outer join
3158 * that could be formed from them. Although such clauses must be
3159 * correctly enforced when we form the outer join, they don't seem like
3160 * sufficient reason to prioritize this join over other ones. The join
3161 * ordering rules will force the join to be made when necessary.
3162 */
3164 rel2->relids);
3165
3166 i = -1;
3168 {
3170 i);
3171
3172 /*
3173 * Sanity check that get_common_eclass_indexes gave only ECs
3174 * containing both rels.
3175 */
3178
3179 /*
3180 * Won't generate joinclauses if single-member (this test covers the
3181 * volatile case too)
3182 */
3184 continue;
3185
3186 /*
3187 * We do not need to examine the individual members of the EC, because
3188 * all that we care about is whether each rel overlaps the relids of
3189 * at least one member, and get_common_eclass_indexes() and the single
3190 * member check above are sufficient to prove that. (As with
3191 * have_relevant_joinclause(), it is not necessary that the EC be able
3192 * to form a joinclause relating exactly the two given rels, only that
3193 * it be able to form a joinclause mentioning both, and this will
3194 * surely be true if both of them overlap ec_relids.)
3195 *
3196 * Note we don't test ec_broken; if we did, we'd need a separate code
3197 * path to look through ec_sources. Checking the membership anyway is
3198 * OK as a possibly-overoptimistic heuristic.
3199 *
3200 * We don't test ec_has_const either, even though a const eclass won't
3201 * generate real join clauses. This is because if we had "WHERE a.x =
3202 * b.y and a.x = 42", it is worth considering a join between a and b,
3203 * since the join result is likely to be small even though it'll end
3204 * up being an unqualified nestloop.
3205 */
3206
3207 return true;
3208 }
3209
3210 return false;
3211}
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 4375 of file indxpath.c.
4378{
4379 ListCell *lc;
4380
4381 /* If the index isn't boolean, we can't possibly get a match */
4383 return false;
4384
4385 /* Check each restriction clause for the index's rel */
4387 {
4389
4390 /*
4391 * As in match_clause_to_indexcol, never match pseudoconstants to
4392 * indexes. (It might be semantically okay to do so here, but the
4393 * odds of getting a match are negligible, so don't waste the cycles.)
4394 */
4395 if (rinfo->pseudoconstant)
4396 continue;
4397
4398 /* See if we can match the clause's expression to the index column */
4400 return true;
4401 }
4402
4403 return false;
4404}
static IndexClause * match_boolean_index_clause(PlannerInfo *root, RestrictInfo *rinfo, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:2761
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 670 of file joinrels.c.
672{
673 sjinfo->type = T_SpecialJoinInfo;
674 sjinfo->min_lefthand = left_relids;
675 sjinfo->min_righthand = right_relids;
676 sjinfo->syn_lefthand = left_relids;
677 sjinfo->syn_righthand = right_relids;
679 sjinfo->ojrelid = 0;
680 sjinfo->commute_above_l = NULL;
681 sjinfo->commute_above_r = NULL;
682 sjinfo->commute_below_l = NULL;
683 sjinfo->commute_below_r = NULL;
684 /* we don't bother trying to make the remaining fields valid */
690}
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 1462 of file pathkeys.c.
1463{
1465 Oid lefttype,
1466 righttype;
1467
1468 /* Should be a mergeclause ... */
1470 /* ... with links not yet set */
1471 Assert(restrictinfo->left_ec == NULL);
1472 Assert(restrictinfo->right_ec == NULL);
1473
1474 /* Need the declared input types of the operator */
1476
1477 /* Find or create a matching EquivalenceClass for each side */
1478 restrictinfo->left_ec =
1481 restrictinfo->mergeopfamilies,
1482 lefttype,
1483 ((OpExpr *) clause)->inputcollid,
1484 0,
1485 NULL,
1486 true);
1487 restrictinfo->right_ec =
1490 restrictinfo->mergeopfamilies,
1491 righttype,
1492 ((OpExpr *) clause)->inputcollid,
1493 0,
1494 NULL,
1495 true);
1496}
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1397
Definition: primnodes.h:831
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 3325 of file equivclass.c.
3326{
3327 EquivalenceClass *parent_ec = rinfo->parent_ec;
3328 ListCell *lc;
3329
3330 /* Fail if it's not a potentially-redundant clause from some EC */
3331 if (parent_ec == NULL)
3332 return false;
3333
3334 foreach(lc, clauselist)
3335 {
3337
3338 if (otherrinfo->parent_ec == parent_ec)
3339 return true;
3340 }
3341
3342 return false;
3343}
References lfirst.
Referenced by create_tidscan_plan().
◆ is_redundant_with_indexclauses()
| bool is_redundant_with_indexclauses | ( | RestrictInfo * | rinfo, |
| List * | indexclauses | ||
| ) |
Definition at line 3352 of file equivclass.c.
3353{
3354 EquivalenceClass *parent_ec = rinfo->parent_ec;
3355 ListCell *lc;
3356
3357 foreach(lc, indexclauses)
3358 {
3361
3362 /* If indexclause is lossy, it won't enforce the condition exactly */
3364 continue;
3365
3366 /* Match if it's same clause (pointer equality should be enough) */
3367 if (rinfo == otherrinfo)
3368 return true;
3369 /* Match if derived from same EC */
3370 if (parent_ec && otherrinfo->parent_ec == parent_ec)
3371 return true;
3372
3373 /*
3374 * No need to look at the derived clauses in iclause->indexquals; they
3375 * couldn't match if the parent clause didn't.
3376 */
3377 }
3378
3379 return false;
3380}
Definition: pathnodes.h:1790
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 73 of file joinrels.c.
74{
76 ListCell *r;
77 int k;
78
80
81 /* Set join_cur_level so that new joinrels are added to proper list */
82 root->join_cur_level = level;
83
84 /*
85 * First, consider left-sided and right-sided plans, in which rels of
86 * exactly level-1 member relations are joined against initial relations.
87 * We prefer to join using join clauses, but if we find a rel of level-1
88 * members that has no join clauses, we will generate Cartesian-product
89 * joins against all initial rels not already contained in it.
90 */
91 foreach(r, joinrels[level - 1])
92 {
94
97 {
98 int first_rel;
99
100 /*
101 * There are join clauses or join order restrictions relevant to
102 * this rel, so consider joins between this rel and (only) those
103 * initial rels it is linked to by a clause or restriction.
104 *
105 * At level 2 this condition is symmetric, so there is no need to
106 * look at initial rels before this one in the list; we already
107 * considered such joins when we were at the earlier rel. (The
108 * mirror-image joins are handled automatically by make_join_rel.)
109 * In later passes (level > 2), we join rels of the previous level
110 * to each initial rel they don't already include but have a join
111 * clause or restriction with.
112 */
113 if (level == 2) /* consider remaining initial rels */
114 first_rel = foreach_current_index(r) + 1;
115 else
116 first_rel = 0;
117
119 }
120 else
121 {
122 /*
123 * Oops, we have a relation that is not joined to any other
124 * relation, either directly or by join-order restrictions.
125 * Cartesian product time.
126 *
127 * We consider a cartesian product with each not-already-included
128 * initial rel, whether it has other join clauses or not. At
129 * level 2, if there are two or more clauseless initial rels, we
130 * will redundantly consider joining them in both directions; but
131 * such cases aren't common enough to justify adding complexity to
132 * avoid the duplicated effort.
133 */
135 old_rel,
136 joinrels[1]);
137 }
138 }
139
140 /*
141 * Now, consider "bushy plans" in which relations of k initial rels are
142 * joined to relations of level-k initial rels, for 2 <= k <= level-2.
143 *
144 * We only consider bushy-plan joins for pairs of rels where there is a
145 * suitable join clause (or join order restriction), in order to avoid
146 * unreasonable growth of planning time.
147 */
148 for (k = 2;; k++)
149 {
150 int other_level = level - k;
151
152 /*
153 * Since make_join_rel(x, y) handles both x,y and y,x cases, we only
154 * need to go as far as the halfway point.
155 */
156 if (k > other_level)
157 break;
158
159 foreach(r, joinrels[k])
160 {
162 int first_rel;
163 ListCell *r2;
164
165 /*
166 * We can ignore relations without join clauses here, unless they
167 * participate in join-order restrictions --- then we might have
168 * to force a bushy join plan.
169 */
172 continue;
173
174 if (k == other_level) /* only consider remaining rels */
175 first_rel = foreach_current_index(r) + 1;
176 else
177 first_rel = 0;
178
179 for_each_from(r2, joinrels[other_level], first_rel)
180 {
182
184 {
185 /*
186 * OK, we can build a rel of the right level from this
187 * pair of rels. Do so if there is at least one relevant
188 * join clause or join order restriction.
189 */
192 {
194 }
195 }
196 }
197 }
198 }
199
200 /*----------
201 * Last-ditch effort: if we failed to find any usable joins so far, force
202 * a set of cartesian-product joins to be generated. This handles the
203 * special case where all the available rels have join clauses but we
204 * cannot use any of those clauses yet. This can only happen when we are
205 * considering a join sub-problem (a sub-joinlist) and all the rels in the
206 * sub-problem have only join clauses with rels outside the sub-problem.
207 * An example is
208 *
209 * SELECT ... FROM a INNER JOIN b ON TRUE, c, d, ...
210 * WHERE a.w = c.x and b.y = d.z;
211 *
212 * If the "a INNER JOIN b" sub-problem does not get flattened into the
213 * upper level, we must be willing to make a cartesian join of a and b;
214 * but the code above will not have done so, because it thought that both
215 * a and b have joinclauses. We consider only left-sided and right-sided
216 * cartesian joins in this case (no bushy).
217 *----------
218 */
220 {
221 /*
222 * This loop is just like the first one, except we always call
223 * make_rels_by_clauseless_joins().
224 */
225 foreach(r, joinrels[level - 1])
226 {
228
230 old_rel,
231 joinrels[1]);
232 }
233
234 /*----------
235 * When special joins are involved, there may be no legal way
236 * to make an N-way join for some values of N. For example consider
237 *
238 * SELECT ... FROM t1 WHERE
239 * x IN (SELECT ... FROM t2,t3 WHERE ...) AND
240 * y IN (SELECT ... FROM t4,t5 WHERE ...)
241 *
242 * We will flatten this query to a 5-way join problem, but there are
243 * no 4-way joins that join_is_legal() will consider legal. We have
244 * to accept failure at level 4 and go on to discover a workable
245 * bushy plan at level 5.
246 *
247 * However, if there are no special joins and no lateral references
248 * then join_is_legal() should never fail, and so the following sanity
249 * check is useful.
250 *----------
251 */
254 !root->hasLateralRTEs)
256 }
257}
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:314
RelOptInfo * make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:705
bool have_join_order_restriction(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:1075
static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1188
static void make_rels_by_clause_joins(PlannerInfo *root, RelOptInfo *old_rel, List *other_rels, int first_rel_idx)
Definition: joinrels.c:280
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, | ||
| int | strategy, | ||
| 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 strategy == pk->pk_strategy &&
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_strategy = strategy;
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_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, 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 1854 of file pathkeys.c.
1857{
1859 EquivalenceClass *lastoeclass;
1860 PathKey *opathkey;
1861 ListCell *lc;
1862 ListCell *lop;
1863
1864 lastoeclass = NULL;
1865 opathkey = NULL;
1866 lop = list_head(outer_pathkeys);
1867
1868 foreach(lc, mergeclauses)
1869 {
1871 EquivalenceClass *oeclass;
1872 EquivalenceClass *ieclass;
1873 PathKey *pathkey;
1874
1876
1877 if (rinfo->outer_is_left)
1878 {
1879 oeclass = rinfo->left_ec;
1880 ieclass = rinfo->right_ec;
1881 }
1882 else
1883 {
1884 oeclass = rinfo->right_ec;
1885 ieclass = rinfo->left_ec;
1886 }
1887
1888 /* outer eclass should match current or next pathkeys */
1889 /* we check this carefully for debugging reasons */
1890 if (oeclass != lastoeclass)
1891 {
1892 if (!lop)
1895 lop = lnext(outer_pathkeys, lop);
1896 lastoeclass = opathkey->pk_eclass;
1897 if (oeclass != lastoeclass)
1899 }
1900
1901 /*
1902 * Often, we'll have same EC on both sides, in which case the outer
1903 * pathkey is also canonical for the inner side, and we can skip a
1904 * useless search.
1905 */
1906 if (ieclass == oeclass)
1907 pathkey = opathkey;
1908 else
1910 ieclass,
1911 opathkey->pk_opfamily,
1912 opathkey->pk_strategy,
1913 opathkey->pk_nulls_first);
1914
1915 /*
1916 * Don't generate redundant pathkeys (which can happen if multiple
1917 * mergeclauses refer to the same EC). Because we do this, the output
1918 * pathkey list isn't necessarily ordered like the mergeclauses, which
1919 * complicates life for create_mergejoin_plan(). But if we didn't,
1920 * we'd have a noncanonical sort key list, which would be bad; for one
1921 * reason, it certainly wouldn't match any available sort order for
1922 * the input relation.
1923 */
1925 pathkeys = lappend(pathkeys, pathkey);
1926 }
1927
1928 return pathkeys;
1929}
References elog, ERROR, lappend(), lfirst, list_head(), lnext(), make_canonical_pathkey(), NIL, pathkey_is_redundant(), PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, 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 705 of file joinrels.c.
706{
707 Relids joinrelids;
708 SpecialJoinInfo *sjinfo;
709 bool reversed;
711 SpecialJoinInfo sjinfo_data;
712 RelOptInfo *joinrel;
713 List *restrictlist;
714
715 /* We should never try to join two overlapping sets of rels. */
717
718 /* Construct Relids set that identifies the joinrel (without OJ as yet). */
720
721 /* Check validity and determine join type. */
723 &sjinfo, &reversed))
724 {
725 /* invalid join path */
726 bms_free(joinrelids);
727 return NULL;
728 }
729
730 /*
731 * Add outer join relid(s) to form the canonical relids. Any added outer
732 * joins besides sjinfo itself are appended to pushed_down_joins.
733 */
735 &pushed_down_joins);
736
737 /* Swap rels if needed to match the join info. */
738 if (reversed)
739 {
740 RelOptInfo *trel = rel1;
741
742 rel1 = rel2;
743 rel2 = trel;
744 }
745
746 /*
747 * If it's a plain inner join, then we won't have found anything in
748 * join_info_list. Make up a SpecialJoinInfo so that selectivity
749 * estimation functions will know what's being joined.
750 */
751 if (sjinfo == NULL)
752 {
753 sjinfo = &sjinfo_data;
755 }
756
757 /*
758 * Find or build the join RelOptInfo, and compute the restrictlist that
759 * goes with this particular joining.
760 */
762 sjinfo, pushed_down_joins,
763 &restrictlist);
764
765 /*
766 * If we've already proven this join is empty, we needn't consider any
767 * more paths for it.
768 */
770 {
771 bms_free(joinrelids);
772 return joinrel;
773 }
774
775 /* Add paths to the join relation. */
777 restrictlist);
778
779 bms_free(joinrelids);
780
781 return joinrel;
782}
static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, SpecialJoinInfo *sjinfo, List *restrictlist)
Definition: joinrels.c:894
void init_dummy_sjinfo(SpecialJoinInfo *sjinfo, Relids left_relids, Relids right_relids)
Definition: joinrels.c:670
static bool join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, Relids joinrelids, SpecialJoinInfo **sjinfo_p, bool *reversed_p)
Definition: joinrels.c:350
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:665
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(), 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 171 of file allpaths.c.
172{
173 RelOptInfo *rel;
174 Index rti;
175 double total_pages;
176
177 /* Mark base rels as to whether we care about fast-start plans */
179
180 /*
181 * Compute size estimates and consider_parallel flags for each base rel.
182 */
184
185 /*
186 * We should now have size estimates for every actual table involved in
187 * the query, and we also know which if any have been deleted from the
188 * query by join removal, pruned by partition pruning, or eliminated by
189 * constraint exclusion. So we can now compute total_table_pages.
190 *
191 * Note that appendrels are not double-counted here, even though we don't
192 * bother to distinguish RelOptInfos for appendrel parents, because the
193 * parents will have pages = 0.
194 *
195 * XXX if a table is self-joined, we will count it once per appearance,
196 * which perhaps is the wrong thing ... but that's not completely clear,
197 * and detecting self-joins here is difficult, so ignore it for now.
198 */
199 total_pages = 0;
201 {
203
204 /* there may be empty slots corresponding to non-baserel RTEs */
205 if (brel == NULL)
206 continue;
207
209
211 continue;
212
214 total_pages += (double) brel->pages;
215 }
216 root->total_table_pages = total_pages;
217
218 /*
219 * Generate access paths for each base rel.
220 */
222
223 /*
224 * Generate access paths for the entire join tree.
225 */
227
228 /*
229 * The result should join all and only the query's base + outer-join rels.
230 */
232
233 return rel;
234}
static void set_base_rel_consider_startup(PlannerInfo *root)
Definition: allpaths.c:247
static void set_base_rel_pathlists(PlannerInfo *root)
Definition: allpaths.c:333
static RelOptInfo * make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
Definition: allpaths.c:3338
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(), and set_base_rel_sizes().
Referenced by query_planner().
◆ make_pathkeys_for_sortclauses()
| List * make_pathkeys_for_sortclauses | ( | PlannerInfo * | root, |
| List * | sortclauses, | ||
| List * | tlist | ||
| ) |
Definition at line 1335 of file pathkeys.c.
1338{
1339 List *result;
1340 bool sortable;
1341
1343 &sortclauses,
1344 tlist,
1345 false,
1346 false,
1347 &sortable,
1348 false);
1349 /* It's caller error if not all clauses were sortable */
1350 Assert(sortable);
1351 return result;
1352}
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:1380
References Assert(), make_pathkeys_for_sortclauses_extended(), and root.
Referenced by adjust_group_pathkeys_for_groupagg(), 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 1380 of file pathkeys.c.
1387{
1389 ListCell *l;
1390
1391 *sortable = true;
1392 foreach(l, *sortclauses)
1393 {
1395 Expr *sortkey;
1396 PathKey *pathkey;
1397
1400 {
1401 *sortable = false;
1402 continue;
1403 }
1404 if (remove_group_rtindex)
1405 {
1407 sortkey = (Expr *)
1410 NULL);
1411 }
1413 sortkey,
1414 sortcl->sortop,
1415 sortcl->reverse_sort,
1416 sortcl->nulls_first,
1417 sortcl->tleSortGroupRef,
1418 true);
1419 if (pathkey->pk_eclass->ec_sortref == 0 && set_ec_sortref)
1420 {
1421 /*
1422 * Copy the sortref if it hasn't been set yet. That may happen if
1423 * the EquivalenceClass was constructed from a WHERE clause, i.e.
1424 * it doesn't have a target reference at all.
1425 */
1426 pathkey->pk_eclass->ec_sortref = sortcl->tleSortGroupRef;
1427 }
1428
1429 /* Canonical form eliminates redundant ordering keys */
1431 pathkeys = lappend(pathkeys, pathkey);
1432 else if (remove_redundant)
1433 *sortclauses = foreach_delete_current(*sortclauses, l);
1434 }
1435 return pathkeys;
1436}
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:1375
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 1385 of file joinrels.c.
1386{
1387 MemoryContext oldcontext;
1388
1389 /* Already marked? */
1391 return;
1392
1393 /* No, so choose correct context to make the dummy path in */
1395
1396 /* Set dummy size estimate */
1397 rel->rows = 0;
1398
1399 /* Evict any previously chosen paths */
1402
1403 /* Set up the dummy path */
1406 0, false, -1));
1407
1408 /* Set or update cheapest_total_path and related fields */
1409 set_cheapest(rel);
1410
1411 MemoryContextSwitchTo(oldcontext);
1412}
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_simple_rel(), generate_partitionwise_join_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 2560 of file equivclass.c.
2563{
2565 AttrNumber var1attno = fkinfo->conkey[colno];
2567 AttrNumber var2attno = fkinfo->confkey[colno];
2568 Oid eqop = fkinfo->conpfeqop[colno];
2572 Bitmapset *matching_ecs;
2574
2575 /* Consider only eclasses mentioning both relations */
2580 rel2->eclass_indexes);
2581
2582 i = -1;
2584 {
2586 i);
2587 EquivalenceMember *item1_em = NULL;
2588 EquivalenceMember *item2_em = NULL;
2589 ListCell *lc2;
2590
2591 /* Never match to a volatile EC */
2593 continue;
2594 /* It's okay to consider "broken" ECs here, see exprs_known_equal */
2595
2597 {
2599 Var *var;
2600
2602 continue; /* ignore children here */
2603
2604 /* EM must be a Var, possibly with RelabelType */
2609 continue;
2610
2611 /* Match? */
2613 item1_em = em;
2615 item2_em = em;
2616
2617 /* Have we found both PK and FK column in this EC? */
2618 if (item1_em && item2_em)
2619 {
2620 /*
2621 * Succeed if eqop matches EC's opfamilies. We could test
2622 * this before scanning the members, but it's probably cheaper
2623 * to test for member matches first.
2624 */
2626 opfamilies = get_mergejoin_opfamilies(eqop);
2628 {
2629 fkinfo->eclass[colno] = ec;
2630 fkinfo->fk_eclass_member[colno] = item2_em;
2631 return ec;
2632 }
2633 /* Otherwise, done with this EC, move on to the next */
2634 break;
2635 }
2636 }
2637 }
2638 return NULL;
2639}
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:292
struct EquivalenceClass * eclass[INDEX_MAX_KEYS]
Definition: pathnodes.h:1285
struct EquivalenceMember * fk_eclass_member[INDEX_MAX_KEYS]
Definition: pathnodes.h:1287
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 4426 of file indxpath.c.
4429{
4430 int indkey;
4431
4432 /*
4433 * Ignore any RelabelType node above the operand. This is needed to be
4434 * able to apply indexscanning in binary-compatible-operator cases. Note:
4435 * we can assume there is at most one RelabelType node;
4436 * eval_const_expressions() will have simplified if more than one.
4437 */
4440
4441 indkey = index->indexkeys[indexcol];
4442 if (indkey != 0)
4443 {
4444 /*
4445 * Simple index column; operand must be a matching Var.
4446 */
4449 indkey == ((Var *) operand)->varattno &&
4450 ((Var *) operand)->varnullingrels == NULL)
4451 return true;
4452 }
4453 else
4454 {
4455 /*
4456 * Index expression; find the correct expression. (This search could
4457 * be avoided, at the cost of complicating all the callers of this
4458 * routine; doesn't seem worth it.)
4459 */
4460 ListCell *indexpr_item;
4462 Node *indexkey;
4463
4466 {
4468 {
4469 if (indexpr_item == NULL)
4472 }
4473 }
4474 if (indexpr_item == NULL)
4477
4478 /*
4479 * Does it match the operand? Again, strip any relabeling.
4480 */
4483
4485 return true;
4486 }
4487
4488 return false;
4489}
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_ext().
◆ 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(), cost_append(), create_append_plan(), create_gather_merge_path(), create_gather_merge_plan(), create_merge_append_path(), create_merge_append_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(), 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(), create_mergejoin_plan(), create_one_window_path(), create_ordered_paths(), create_window_paths(), gather_grouping_paths(), generate_useful_gather_paths(), initial_cost_mergejoin(), make_ordered_path(), pathkeys_useful_for_ordering(), and pathkeys_useful_for_setop().
◆ process_equivalence()
| bool process_equivalence | ( | PlannerInfo * | root, |
| RestrictInfo ** | p_restrictinfo, | ||
| JoinDomain * | jdomain | ||
| ) |
Definition at line 117 of file equivclass.c.
120{
121 RestrictInfo *restrictinfo = *p_restrictinfo;
123 Oid opno,
124 collation,
125 item1_type,
126 item2_type;
127 Expr *item1;
128 Expr *item2;
129 Relids item1_relids,
130 item2_relids;
131 List *opfamilies;
132 EquivalenceClass *ec1,
133 *ec2;
134 EquivalenceMember *em1,
135 *em2;
136 ListCell *lc1;
137 int ec2_idx;
138
139 /* Should not already be marked as having generated an eclass */
140 Assert(restrictinfo->left_ec == NULL);
141 Assert(restrictinfo->right_ec == NULL);
142
143 /* Reject if it is potentially postponable by security considerations */
145 return false;
146
147 /* Extract info from given clause */
149 opno = ((OpExpr *) clause)->opno;
150 collation = ((OpExpr *) clause)->inputcollid;
153 item1_relids = restrictinfo->left_relids;
154 item2_relids = restrictinfo->right_relids;
155
156 /*
157 * Ensure both input expressions expose the desired collation (their types
158 * should be OK already); see comments for canonicalize_ec_expression.
159 */
160 item1 = canonicalize_ec_expression(item1,
162 collation);
163 item2 = canonicalize_ec_expression(item2,
165 collation);
166
167 /*
168 * Clauses of the form X=X cannot be translated into EquivalenceClasses.
169 * We'd either end up with a single-entry EC, losing the knowledge that
170 * the clause was present at all, or else make an EC with duplicate
171 * entries, causing other issues.
172 */
174 {
175 /*
176 * If the operator is strict, then the clause can be treated as just
177 * "X IS NOT NULL". (Since we know we are considering a top-level
178 * qual, we can ignore the difference between FALSE and NULL results.)
179 * It's worth making the conversion because we'll typically get a much
180 * better selectivity estimate than we would for X=X.
181 *
182 * If the operator is not strict, we can't be sure what it will do
183 * with NULLs, so don't attempt to optimize it.
184 */
187 {
189
190 ntest->arg = item1;
192 ntest->argisrow = false; /* correct even if composite arg */
193 ntest->location = -1;
194
195 *p_restrictinfo =
197 (Expr *) ntest,
198 restrictinfo->is_pushed_down,
199 restrictinfo->has_clone,
200 restrictinfo->is_clone,
201 restrictinfo->pseudoconstant,
202 restrictinfo->security_level,
203 NULL,
204 restrictinfo->incompatible_relids,
205 restrictinfo->outer_relids);
206 }
207 return false;
208 }
209
210 /*
211 * We use the declared input types of the operator, not exprType() of the
212 * inputs, as the nominal datatypes for opfamily lookup. This presumes
213 * that btree operators are always registered with amoplefttype and
214 * amoprighttype equal to their declared input types. We will need this
215 * info anyway to build EquivalenceMember nodes, and by extracting it now
216 * we can use type comparisons to short-circuit some equal() tests.
217 */
218 op_input_types(opno, &item1_type, &item2_type);
219
220 opfamilies = restrictinfo->mergeopfamilies;
221
222 /*
223 * Sweep through the existing EquivalenceClasses looking for matches to
224 * item1 and item2. These are the possible outcomes:
225 *
226 * 1. We find both in the same EC. The equivalence is already known, so
227 * there's nothing to do.
228 *
229 * 2. We find both in different ECs. Merge the two ECs together.
230 *
231 * 3. We find just one. Add the other to its EC.
232 *
233 * 4. We find neither. Make a new, two-entry EC.
234 *
235 * Note: since all ECs are built through this process or the similar
236 * search in get_eclass_for_sort_expr(), it's impossible that we'd match
237 * an item in more than one existing nonvolatile EC. So it's okay to stop
238 * at the first match.
239 */
240 ec1 = ec2 = NULL;
241 em1 = em2 = NULL;
242 ec2_idx = -1;
244 {
246 ListCell *lc2;
247
248 /* Never match to a volatile EC */
250 continue;
251
252 /*
253 * The collation has to match; check this first since it's cheaper
254 * than the opfamily comparison.
255 */
257 continue;
258
259 /*
260 * A "match" requires matching sets of btree opfamilies. Use of
261 * equal() for this test has implications discussed in the comments
262 * for get_mergejoin_opfamilies().
263 */
265 continue;
266
268 {
270
272
273 /*
274 * Match constants only within the same JoinDomain (see
275 * optimizer/README).
276 */
278 continue;
279
280 if (!ec1 &&
281 item1_type == cur_em->em_datatype &&
283 {
284 ec1 = cur_ec;
285 em1 = cur_em;
286 if (ec2)
287 break;
288 }
289
290 if (!ec2 &&
291 item2_type == cur_em->em_datatype &&
293 {
294 ec2 = cur_ec;
295 ec2_idx = foreach_current_index(lc1);
296 em2 = cur_em;
297 if (ec1)
298 break;
299 }
300 }
301
302 if (ec1 && ec2)
303 break;
304 }
305
306 /* Sweep finished, what did we find? */
307
308 if (ec1 && ec2)
309 {
310 /* If case 1, nothing to do, except add to sources */
311 if (ec1 == ec2)
312 {
315 restrictinfo->security_level);
317 restrictinfo->security_level);
318 /* mark the RI as associated with this eclass */
319 restrictinfo->left_ec = ec1;
320 restrictinfo->right_ec = ec1;
321 /* mark the RI as usable with this pair of EMs */
322 restrictinfo->left_em = em1;
323 restrictinfo->right_em = em2;
324 return true;
325 }
326
327 /*
328 * Case 2: need to merge ec1 and ec2. This should never happen after
329 * the ECs have reached canonical state; otherwise, pathkeys could be
330 * rendered non-canonical by the merge, and relation eclass indexes
331 * would get broken by removal of an eq_classes list entry.
332 */
335
336 /*
337 * We add ec2's items to ec1, then set ec2's ec_merged link to point
338 * to ec1 and remove ec2 from the eq_classes list. We cannot simply
339 * delete ec2 because that could leave dangling pointers in existing
340 * PathKeys. We leave it behind with a link so that the merged EC can
341 * be found.
342 */
348 /* can't need to set has_volatile */
350 ec2->ec_min_security);
352 ec2->ec_max_security);
353 ec2->ec_merged = ec1;
355 /* just to avoid debugging confusion w/ dangling pointers: */
359 ec2->ec_relids = NULL;
362 restrictinfo->security_level);
364 restrictinfo->security_level);
365 /* mark the RI as associated with this eclass */
366 restrictinfo->left_ec = ec1;
367 restrictinfo->right_ec = ec1;
368 /* mark the RI as usable with this pair of EMs */
369 restrictinfo->left_em = em1;
370 restrictinfo->right_em = em2;
371 }
372 else if (ec1)
373 {
374 /* Case 3: add item2 to ec1 */
375 em2 = add_eq_member(ec1, item2, item2_relids,
376 jdomain, NULL, item2_type);
379 restrictinfo->security_level);
381 restrictinfo->security_level);
382 /* mark the RI as associated with this eclass */
383 restrictinfo->left_ec = ec1;
384 restrictinfo->right_ec = ec1;
385 /* mark the RI as usable with this pair of EMs */
386 restrictinfo->left_em = em1;
387 restrictinfo->right_em = em2;
388 }
389 else if (ec2)
390 {
391 /* Case 3: add item1 to ec2 */
392 em1 = add_eq_member(ec2, item1, item1_relids,
393 jdomain, NULL, item1_type);
396 restrictinfo->security_level);
398 restrictinfo->security_level);
399 /* mark the RI as associated with this eclass */
400 restrictinfo->left_ec = ec2;
401 restrictinfo->right_ec = ec2;
402 /* mark the RI as usable with this pair of EMs */
403 restrictinfo->left_em = em1;
404 restrictinfo->right_em = em2;
405 }
406 else
407 {
408 /* Case 4: make a new, two-entry EC */
410
411 ec->ec_opfamilies = opfamilies;
412 ec->ec_collation = collation;
416 ec->ec_relids = NULL;
420 ec->ec_sortref = 0;
423 ec->ec_merged = NULL;
424 em1 = add_eq_member(ec, item1, item1_relids,
425 jdomain, NULL, item1_type);
426 em2 = add_eq_member(ec, item2, item2_relids,
427 jdomain, NULL, item2_type);
428
430
431 /* mark the RI as associated with this eclass */
432 restrictinfo->left_ec = ec;
433 restrictinfo->right_ec = ec;
434 /* mark the RI as usable with this pair of EMs */
435 restrictinfo->left_em = em1;
436 restrictinfo->right_em = em2;
437 }
438
439 return true;
440}
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:1961
References add_eq_member(), NullTest::arg, Assert(), bms_join(), canonicalize_ec_expression(), RestrictInfo::clause, EquivalenceClass::ec_broken, EquivalenceClass::ec_collation, EquivalenceClass::ec_derives, 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 2432 of file equivclass.c.
2433{
2434 ListCell *lc;
2435
2437 {
2439
2440 /* Need do anything only for a multi-member, no-const EC. */
2442 {
2443 ListCell *lc2;
2444
2446 {
2449 PVC_RECURSE_AGGREGATES |
2450 PVC_RECURSE_WINDOWFUNCS |
2451 PVC_INCLUDE_PLACEHOLDERS);
2452
2455 }
2456 }
2457 }
2458}
void add_vars_to_attr_needed(PlannerInfo *root, List *vars, Relids where_needed)
Definition: initsplan.c:353
Definition: regcomp.c:282
References add_vars_to_attr_needed(), 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 2002 of file equivclass.c.
2003{
2004 bool found;
2005 ListCell *cell;
2006
2007 /* Outer loop repeats until we find no more deductions */
2008 do
2009 {
2010 found = false;
2011
2012 /* Process the LEFT JOIN clauses */
2014 {
2016
2018 {
2020
2021 found = true;
2022 /* remove it from the list */
2023 root->left_join_clauses =
2025 /* throw back a dummy replacement clause (see notes above) */
2028 rinfo->is_pushed_down,
2029 rinfo->has_clone,
2030 rinfo->is_clone,
2031 false, /* pseudoconstant */
2032 0, /* security_level */
2033 rinfo->required_relids,
2034 rinfo->incompatible_relids,
2035 rinfo->outer_relids);
2037 }
2038 }
2039
2040 /* Process the RIGHT JOIN clauses */
2042 {
2044
2046 {
2048
2049 found = true;
2050 /* remove it from the list */
2051 root->right_join_clauses =
2053 /* throw back a dummy replacement clause (see notes above) */
2056 rinfo->is_pushed_down,
2057 rinfo->has_clone,
2058 rinfo->is_clone,
2059 false, /* pseudoconstant */
2060 0, /* security_level */
2061 rinfo->required_relids,
2062 rinfo->incompatible_relids,
2063 rinfo->outer_relids);
2065 }
2066 }
2067
2068 /* Process the FULL JOIN clauses */
2070 {
2072
2074 {
2076
2077 found = true;
2078 /* remove it from the list */
2079 root->full_join_clauses =
2081 /* throw back a dummy replacement clause (see notes above) */
2084 rinfo->is_pushed_down,
2085 rinfo->has_clone,
2086 rinfo->is_clone,
2087 false, /* pseudoconstant */
2088 0, /* security_level */
2089 rinfo->required_relids,
2090 rinfo->incompatible_relids,
2091 rinfo->outer_relids);
2093 }
2094 }
2095 } while (found);
2096
2097 /* Now, any remaining clauses have to be thrown back */
2099 {
2101
2103 }
2105 {
2107
2109 }
2111 {
2113
2115 }
2116}
static bool reconsider_outer_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo, bool outer_on_left)
Definition: equivclass.c:2124
static bool reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo)
Definition: equivclass.c:2247
void distribute_restrictinfo_to_rels(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: initsplan.c:3213
Definition: pathnodes.h:2954
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 922 of file equivclass.c.
924{
926 EquivalenceMember *em;
927 ListCell *lc;
928
929 /*
930 * Reject volatile ECs immediately; such sorts must always be postponed.
931 */
933 return false;
934
935 /*
936 * Try to find an EM directly matching some reltarget member.
937 */
939 {
941
943 if (!em)
944 continue;
945
946 /*
947 * Reject expressions involving set-returning functions, as those
948 * can't be computed early either. (Note: this test and the following
949 * one are effectively checking properties of targetexpr, so there's
950 * no point in asking whether some other EC member would be better.)
951 */
953 continue;
954
955 /*
956 * If requested, reject expressions that are not parallel-safe. We
957 * check this last because it's a rather expensive test.
958 */
959 if (require_parallel_safe &&
961 continue;
962
963 return true;
964 }
965
966 /*
967 * Try to find an expression computable from the reltarget.
968 */
970 require_parallel_safe);
971 if (!em)
972 return false;
973
974 /*
975 * Reject expressions involving set-returning functions, as those can't be
976 * computed early either. (There's no point in looking for another EC
977 * member in this case; since SRFs can't appear in WHERE, they cannot
978 * belong to multi-member ECs.)
979 */
981 return false;
982
983 return true;
984}
EquivalenceMember * find_ec_member_matching_expr(EquivalenceClass *ec, Expr *expr, Relids relids)
Definition: equivclass.c:763
EquivalenceMember * find_computable_ec_member(PlannerInfo *root, EquivalenceClass *ec, List *exprs, Relids relids, bool require_parallel_safe)
Definition: equivclass.c:837
Definition: pathnodes.h:1562
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_ext()
| bool relation_has_unique_index_ext | ( | PlannerInfo * | root, |
| RelOptInfo * | rel, | ||
| List * | restrictlist, | ||
| List * | exprlist, | ||
| List * | oprlist, | ||
| List ** | extra_clauses | ||
| ) |
Definition at line 4177 of file indxpath.c.
4181{
4182 ListCell *ic;
4183
4185
4186 /* Short-circuit if no indexes... */
4188 return false;
4189
4190 /*
4191 * Examine the rel's restriction clauses for usable var = const clauses
4192 * that we can add to the restrictlist.
4193 */
4195 {
4197
4198 /*
4199 * Note: can_join won't be set for a restriction clause, but
4200 * mergeopfamilies will be if it has a mergejoinable operator and
4201 * doesn't contain volatile functions.
4202 */
4204 continue; /* not mergejoinable */
4205
4206 /*
4207 * The clause certainly doesn't refer to anything but the given rel.
4208 * If either side is pseudoconstant then we can use it.
4209 */
4211 {
4212 /* righthand side is inner */
4213 restrictinfo->outer_is_left = true;
4214 }
4216 {
4217 /* lefthand side is inner */
4218 restrictinfo->outer_is_left = false;
4219 }
4220 else
4221 continue;
4222
4223 /* OK, add to list */
4224 restrictlist = lappend(restrictlist, restrictinfo);
4225 }
4226
4227 /* Short-circuit the easy case */
4229 return false;
4230
4231 /* Examine each index of the relation ... */
4233 {
4237
4238 /*
4239 * If the index is not unique, or not immediately enforced, or if it's
4240 * a partial index, it's useless here. We're unable to make use of
4241 * predOK partial unique indexes due to the fact that
4242 * check_index_predicates() also makes use of join predicates to
4243 * determine if the partial index is usable. Here we need proofs that
4244 * hold true before any joins are evaluated.
4245 */
4247 continue;
4248
4249 /*
4250 * Try to find each index column in the lists of conditions. This is
4251 * O(N^2) or worse, but we expect all the lists to be short.
4252 */
4254 {
4255 bool matched = false;
4256 ListCell *lc;
4257 ListCell *lc2;
4258
4259 foreach(lc, restrictlist)
4260 {
4262 Node *rexpr;
4263
4264 /*
4265 * The condition's equality operator must be a member of the
4266 * index opfamily, else it is not asserting the right kind of
4267 * equality behavior for this index. We check this first
4268 * since it's probably cheaper than match_index_to_operand().
4269 */
4271 continue;
4272
4273 /*
4274 * XXX at some point we may need to check collations here too.
4275 * For the moment we assume all collations reduce to the same
4276 * notion of equality.
4277 */
4278
4279 /* OK, see if the condition operand matches the index key */
4280 if (rinfo->outer_is_left)
4282 else
4284
4286 {
4287 matched = true; /* column is unique */
4288
4290 {
4291 MemoryContext oldMemCtx =
4293
4294 /*
4295 * Add filter clause into a list allowing caller to
4296 * know if uniqueness have made not only by join
4297 * clauses.
4298 */
4300 bms_is_empty(rinfo->right_relids));
4301 if (extra_clauses)
4302 exprs = lappend(exprs, rinfo);
4303 MemoryContextSwitchTo(oldMemCtx);
4304 }
4305
4306 break;
4307 }
4308 }
4309
4310 if (matched)
4311 continue;
4312
4313 forboth(lc, exprlist, lc2, oprlist)
4314 {
4317
4318 /* See if the expression matches the index key */
4320 continue;
4321
4322 /*
4323 * The equality operator must be a member of the index
4324 * opfamily, else it is not asserting the right kind of
4325 * equality behavior for this index. We assume the caller
4326 * determined it is an equality operator, so we don't need to
4327 * check any more tightly than this.
4328 */
4330 continue;
4331
4332 /*
4333 * XXX at some point we may need to check collations here too.
4334 * For the moment we assume all collations reduce to the same
4335 * notion of equality.
4336 */
4337
4338 matched = true; /* column is unique */
4339 break;
4340 }
4341
4342 if (!matched)
4343 break; /* no match; this index doesn't help us */
4344 }
4345
4346 /* Matched all key columns of this index? */
4348 {
4349 if (extra_clauses)
4350 *extra_clauses = exprs;
4351 return true;
4352 }
4353 }
4354
4355 return false;
4356}
bool match_index_to_operand(Node *operand, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:4426
Definition: preproc-array_of_struct.c:43
References Assert(), RelOptInfo::baserestrictinfo, bms_is_empty, bms_membership(), BMS_SINGLETON, RestrictInfo::clause, forboth, get_leftop(), get_rightop(), RelOptInfo::indexlist, lappend(), lfirst, lfirst_oid, list_length(), list_member_oid(), match_index_to_operand(), MemoryContextSwitchTo(), NIL, op_in_opfamily(), and root.
Referenced by rel_is_distinct_for(), and relation_has_unique_index_for().
◆ relation_has_unique_index_for()
| bool relation_has_unique_index_for | ( | PlannerInfo * | root, |
| RelOptInfo * | rel, | ||
| List * | restrictlist, | ||
| List * | exprlist, | ||
| List * | oprlist | ||
| ) |
Definition at line 4162 of file indxpath.c.
4165{
4167 exprlist, oprlist, NULL);
4168}
bool relation_has_unique_index_ext(PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List *exprlist, List *oprlist, List **extra_clauses)
Definition: indxpath.c:4177
References relation_has_unique_index_ext(), and root.
Referenced by create_unique_path().
◆ select_outer_pathkeys_for_merge()
| List * select_outer_pathkeys_for_merge | ( | PlannerInfo * | root, |
| List * | mergeclauses, | ||
| RelOptInfo * | joinrel | ||
| ) |
Definition at line 1658 of file pathkeys.c.
1661{
1664 EquivalenceClass **ecs;
1665 int *scores;
1666 int necs;
1667 ListCell *lc;
1669
1670 /* Might have no mergeclauses */
1671 if (nClauses == 0)
1673
1674 /*
1675 * Make arrays of the ECs used by the mergeclauses (dropping any
1676 * duplicates) and their "popularity" scores.
1677 */
1680 necs = 0;
1681
1682 foreach(lc, mergeclauses)
1683 {
1685 EquivalenceClass *oeclass;
1686 int score;
1687 ListCell *lc2;
1688
1689 /* get the outer eclass */
1691
1692 if (rinfo->outer_is_left)
1693 oeclass = rinfo->left_ec;
1694 else
1695 oeclass = rinfo->right_ec;
1696
1697 /* reject duplicates */
1699 {
1701 break;
1702 }
1704 continue;
1705
1706 /* compute score */
1707 score = 0;
1709 {
1711
1712 /* Potential future join partner? */
1715 score++;
1716 }
1717
1718 ecs[necs] = oeclass;
1719 scores[necs] = score;
1720 necs++;
1721 }
1722
1723 /*
1724 * Find out if we have all the ECs mentioned in query_pathkeys; if so we
1725 * can generate a sort order that's also useful for final output. If we
1726 * only have a prefix of the query_pathkeys, and that prefix is the entire
1727 * join condition, then it's useful to use the prefix as the pathkeys as
1728 * this increases the chances that an incremental sort will be able to be
1729 * used by the upper planner.
1730 */
1732 {
1733 int matches = 0;
1734
1736 {
1738 EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1739
1741 {
1743 break; /* found match */
1744 }
1746 break; /* didn't find match */
1747
1748 matches++;
1749 }
1750 /* if we got to the end of the list, we have them all */
1751 if (lc == NULL)
1752 {
1753 /* copy query_pathkeys as starting point for our output */
1755 /* mark their ECs as already-emitted */
1757 {
1759 EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1760
1762 {
1764 {
1765 scores[j] = -1;
1766 break;
1767 }
1768 }
1769 }
1770 }
1771
1772 /*
1773 * If we didn't match to all of the query_pathkeys, but did match to
1774 * all of the join clauses then we'll make use of these as partially
1775 * sorted input is better than nothing for the upper planner as it may
1776 * lead to incremental sorts instead of full sorts.
1777 */
1778 else if (matches == nClauses)
1779 {
1781
1782 /* we have all of the join pathkeys, so nothing more to do */
1783 pfree(ecs);
1784 pfree(scores);
1785
1786 return pathkeys;
1787 }
1788 }
1789
1790 /*
1791 * Add remaining ECs to the list in popularity order, using a default sort
1792 * ordering. (We could use qsort() here, but the list length is usually
1793 * so small it's not worth it.)
1794 */
1795 for (;;)
1796 {
1797 int best_j;
1798 int best_score;
1799 EquivalenceClass *ec;
1800 PathKey *pathkey;
1801
1802 best_j = 0;
1803 best_score = scores[0];
1805 {
1807 {
1808 best_j = j;
1809 best_score = scores[j];
1810 }
1811 }
1812 if (best_score < 0)
1813 break; /* all done */
1814 ec = ecs[best_j];
1815 scores[best_j] = -1;
1817 ec,
1819 BTLessStrategyNumber,
1820 false);
1821 /* can't be redundant because no duplicate ECs */
1823 pathkeys = lappend(pathkeys, pathkey);
1824 }
1825
1826 pfree(ecs);
1827 pfree(scores);
1828
1829 return pathkeys;
1830}
References Assert(), bms_overlap(), BTLessStrategyNumber, 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().
◆ standard_join_search()
| RelOptInfo * standard_join_search | ( | PlannerInfo * | root, |
| int | levels_needed, | ||
| List * | initial_rels | ||
| ) |
Definition at line 3443 of file allpaths.c.
3444{
3445 int lev;
3446 RelOptInfo *rel;
3447
3448 /*
3449 * This function cannot be invoked recursively within any one planning
3450 * problem, so join_rel_level[] can't be in use already.
3451 */
3453
3454 /*
3455 * We employ a simple "dynamic programming" algorithm: we first find all
3456 * ways to build joins of two jointree items, then all ways to build joins
3457 * of three items (from two-item joins and single items), then four-item
3458 * joins, and so on until we have considered all ways to join all the
3459 * items into one rel.
3460 *
3461 * root->join_rel_level[j] is a list of all the j-item rels. Initially we
3462 * set root->join_rel_level[1] to represent all the single-jointree-item
3463 * relations.
3464 */
3466
3467 root->join_rel_level[1] = initial_rels;
3468
3469 for (lev = 2; lev <= levels_needed; lev++)
3470 {
3471 ListCell *lc;
3472
3473 /*
3474 * Determine all possible pairs of relations to be joined at this
3475 * level, and build paths for making each one from every available
3476 * pair of lower-level relations.
3477 */
3479
3480 /*
3481 * Run generate_partitionwise_join_paths() and
3482 * generate_useful_gather_paths() for each just-processed joinrel. We
3483 * could not do this earlier because both regular and partial paths
3484 * can get added to a particular joinrel at multiple times within
3485 * join_search_one_level.
3486 *
3487 * After that, we're done creating paths for the joinrel, so run
3488 * set_cheapest().
3489 */
3491 {
3493
3494 /* Create paths for partitionwise joins. */
3496
3497 /*
3498 * Except for the topmost scan/join rel, consider gathering
3499 * partial paths. We'll do the same for the topmost scan/join rel
3500 * once we know the final targetlist (see grouping_planner's and
3501 * its call to apply_scanjoin_target_to_paths).
3502 */
3505
3506 /* Find and save the cheapest paths for this rel */
3507 set_cheapest(rel);
3508
3509#ifdef OPTIMIZER_DEBUG
3510 pprint(rel);
3511#endif
3512 }
3513 }
3514
3515 /*
3516 * We should have a single rel at the final level.
3517 */
3521
3523
3524 root->join_rel_level = NULL;
3525
3526 return rel;
3527}
void generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
Definition: allpaths.c:3222
void join_search_one_level(PlannerInfo *root, int level)
Definition: joinrels.c:73
References Assert(), bms_equal(), elog, ERROR, generate_partitionwise_join_paths(), generate_useful_gather_paths(), 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 1957 of file pathkeys.c.
1960{
1962 PathKey *pathkey;
1963 EquivalenceClass *pathkey_ec;
1964 bool matched_pathkey;
1965 ListCell *lip;
1967
1968 /* No pathkeys => no mergeclauses (though we don't expect this case) */
1971 /* Initialize to consider first pathkey */
1972 lip = list_head(pathkeys);
1974 pathkey_ec = pathkey->pk_eclass;
1975 lip = lnext(pathkeys, lip);
1976 matched_pathkey = false;
1977
1978 /* Scan mergeclauses to see how many we can use */
1980 {
1982 EquivalenceClass *clause_ec;
1983
1984 /* Assume we needn't do update_mergeclause_eclasses again here */
1985
1986 /* Check clause's inner-rel EC against current pathkey */
1987 clause_ec = rinfo->outer_is_left ?
1988 rinfo->right_ec : rinfo->left_ec;
1989
1990 /* If we don't have a match, attempt to advance to next pathkey */
1991 if (clause_ec != pathkey_ec)
1992 {
1993 /* If we had no clauses matching this inner pathkey, must stop */
1994 if (!matched_pathkey)
1995 break;
1996
1997 /* Advance to next inner pathkey, if any */
1998 if (lip == NULL)
1999 break;
2001 pathkey_ec = pathkey->pk_eclass;
2002 lip = lnext(pathkeys, lip);
2003 matched_pathkey = false;
2004 }
2005
2006 /* If mergeclause matches current inner pathkey, we can use it */
2007 if (clause_ec == pathkey_ec)
2008 {
2009 new_mergeclauses = lappend(new_mergeclauses, rinfo);
2010 matched_pathkey = true;
2011 }
2012 else
2013 {
2014 /* Else, no hope of adding any more mergeclauses */
2015 break;
2016 }
2017 }
2018
2019 return new_mergeclauses;
2020}
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 2266 of file pathkeys.c.
2269{
2270 int nuseful;
2271 int nuseful2;
2272
2275 if (nuseful2 > nuseful)
2276 nuseful = nuseful2;
2278 if (nuseful2 > nuseful)
2279 nuseful = nuseful2;
2281 if (nuseful2 > nuseful)
2282 nuseful = nuseful2;
2284 if (nuseful2 > nuseful)
2285 nuseful = nuseful2;
2286
2287 /*
2288 * Note: not safe to modify input list destructively, but we can avoid
2289 * copying the list if we're not actually going to change it
2290 */
2291 if (nuseful == 0)
2294 return pathkeys;
2295 else
2297}
static int pathkeys_useful_for_setop(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2251
static int pathkeys_useful_for_distinct(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2220
static int pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2156
static int pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2186
static int pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:2052
References list_copy_head(), list_length(), NIL, pathkeys_useful_for_distinct(), pathkeys_useful_for_grouping(), pathkeys_useful_for_merging(), pathkeys_useful_for_ordering(), pathkeys_useful_for_setop(), 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 1509 of file pathkeys.c.
1510{
1511 /* Should be a merge clause ... */
1513 /* ... with pointers already set */
1514 Assert(restrictinfo->left_ec != NULL);
1515 Assert(restrictinfo->right_ec != NULL);
1516
1517 /* Chase up to the top as needed */
1518 while (restrictinfo->left_ec->ec_merged)
1519 restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
1520 while (restrictinfo->right_ec->ec_merged)
1521 restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
1522}
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_geqo
|
extern |
Definition at line 79 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 80 of file allpaths.c.
Referenced by make_rel_from_joinlist().
◆ join_search_hook
|
extern |
Definition at line 88 of file allpaths.c.
Referenced by make_rel_from_joinlist().
◆ min_parallel_index_scan_size
|
extern |
Definition at line 82 of file allpaths.c.
Referenced by compute_parallel_worker(), and parallel_vacuum_compute_workers().
◆ min_parallel_table_scan_size
|
extern |
Definition at line 81 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 85 of file allpaths.c.
Referenced by set_rel_pathlist().
