PostgreSQL Source Code git master
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 }
 

Functions

RelOptInfomake_one_rel (PlannerInfo *root, List *joinlist)
 
RelOptInfostandard_join_search (PlannerInfo *root, int levels_needed, List *initial_rels)
 
void generate_gather_paths (PlannerInfo *root, RelOptInfo *rel, bool override_rows)
 
void generate_useful_gather_paths (PlannerInfo *root, RelOptInfo *rel, bool override_rows)
 
int compute_parallel_worker (RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
 
void create_partial_bitmap_paths (PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual)
 
void generate_partitionwise_join_paths (PlannerInfo *root, RelOptInfo *rel)
 
void create_index_paths (PlannerInfo *root, RelOptInfo *rel)
 
bool relation_has_unique_index_for (PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List *exprlist, List *oprlist)
 
bool relation_has_unique_index_ext (PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List *exprlist, List *oprlist, List **extra_clauses)
 
bool indexcol_is_bool_constant_for_query (PlannerInfo *root, IndexOptInfo *index, int indexcol)
 
bool match_index_to_operand (Node *operand, int indexcol, IndexOptInfo *index)
 
void check_index_predicates (PlannerInfo *root, RelOptInfo *rel)
 
bool create_tidscan_paths (PlannerInfo *root, RelOptInfo *rel)
 
void add_paths_to_joinrel (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist)
 
void join_search_one_level (PlannerInfo *root, int level)
 
RelOptInfomake_join_rel (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 
Relids add_outer_joins_to_relids (PlannerInfo *root, Relids input_relids, SpecialJoinInfo *sjinfo, List **pushed_down_joins)
 
bool have_join_order_restriction (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 
bool have_dangerous_phv (PlannerInfo *root, Relids outer_relids, Relids inner_params)
 
void mark_dummy_rel (RelOptInfo *rel)
 
void init_dummy_sjinfo (SpecialJoinInfo *sjinfo, Relids left_relids, Relids right_relids)
 
bool process_equivalence (PlannerInfo *root, RestrictInfo **p_restrictinfo, JoinDomain *jdomain)
 
Exprcanonicalize_ec_expression (Expr *expr, Oid req_type, Oid req_collation)
 
void reconsider_outer_join_clauses (PlannerInfo *root)
 
void rebuild_eclass_attr_needed (PlannerInfo *root)
 
EquivalenceClassget_eclass_for_sort_expr (PlannerInfo *root, Expr *expr, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
 
EquivalenceMemberfind_ec_member_matching_expr (EquivalenceClass *ec, Expr *expr, Relids relids)
 
EquivalenceMemberfind_computable_ec_member (PlannerInfo *root, EquivalenceClass *ec, List *exprs, Relids relids, bool require_parallel_safe)
 
bool relation_can_be_sorted_early (PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, bool require_parallel_safe)
 
void generate_base_implied_equalities (PlannerInfo *root)
 
Listgenerate_join_implied_equalities (PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo)
 
Listgenerate_join_implied_equalities_for_ecs (PlannerInfo *root, List *eclasses, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
 
bool exprs_known_equal (PlannerInfo *root, Node *item1, Node *item2, Oid opfamily)
 
EquivalenceClassmatch_eclasses_to_foreign_key_col (PlannerInfo *root, ForeignKeyOptInfo *fkinfo, int colno)
 
RestrictInfofind_derived_clause_for_ec_member (EquivalenceClass *ec, EquivalenceMember *em)
 
void add_child_rel_equivalences (PlannerInfo *root, AppendRelInfo *appinfo, RelOptInfo *parent_rel, RelOptInfo *child_rel)
 
void add_child_join_rel_equivalences (PlannerInfo *root, int nappinfos, AppendRelInfo **appinfos, RelOptInfo *parent_joinrel, RelOptInfo *child_joinrel)
 
void add_setop_child_rel_equivalences (PlannerInfo *root, RelOptInfo *child_rel, List *child_tlist, List *setop_pathkeys)
 
Listgenerate_implied_equalities_for_column (PlannerInfo *root, RelOptInfo *rel, ec_matches_callback_type callback, void *callback_arg, Relids prohibited_rels)
 
bool have_relevant_eclass_joinclause (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 
bool has_relevant_eclass_joinclause (PlannerInfo *root, RelOptInfo *rel1)
 
bool eclass_useful_for_merging (PlannerInfo *root, EquivalenceClass *eclass, RelOptInfo *rel)
 
bool is_redundant_derived_clause (RestrictInfo *rinfo, List *clauselist)
 
bool is_redundant_with_indexclauses (RestrictInfo *rinfo, List *indexclauses)
 
PathKeysComparison compare_pathkeys (List *keys1, List *keys2)
 
bool pathkeys_contained_in (List *keys1, List *keys2)
 
bool pathkeys_count_contained_in (List *keys1, List *keys2, int *n_common)
 
Listget_useful_group_keys_orderings (PlannerInfo *root, Path *path)
 
Pathget_cheapest_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
 
Pathget_cheapest_fractional_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, double fraction)
 
Pathget_cheapest_parallel_safe_total_inner (List *paths)
 
Listbuild_index_pathkeys (PlannerInfo *root, IndexOptInfo *index, ScanDirection scandir)
 
Listbuild_partition_pathkeys (PlannerInfo *root, RelOptInfo *partrel, ScanDirection scandir, bool *partialkeys)
 
Listbuild_expression_pathkey (PlannerInfo *root, Expr *expr, Oid opno, Relids rel, bool create_it)
 
Listconvert_subquery_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *subquery_pathkeys, List *subquery_tlist)
 
Listbuild_join_pathkeys (PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
 
Listmake_pathkeys_for_sortclauses (PlannerInfo *root, List *sortclauses, List *tlist)
 
Listmake_pathkeys_for_sortclauses_extended (PlannerInfo *root, List **sortclauses, List *tlist, bool remove_redundant, bool remove_group_rtindex, bool *sortable, bool set_ec_sortref)
 
void initialize_mergeclause_eclasses (PlannerInfo *root, RestrictInfo *restrictinfo)
 
void update_mergeclause_eclasses (PlannerInfo *root, RestrictInfo *restrictinfo)
 
Listfind_mergeclauses_for_outer_pathkeys (PlannerInfo *root, List *pathkeys, List *restrictinfos)
 
Listselect_outer_pathkeys_for_merge (PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
 
Listmake_inner_pathkeys_for_merge (PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
 
Listtrim_mergeclauses_for_inner_pathkeys (PlannerInfo *root, List *mergeclauses, List *pathkeys)
 
Listtruncate_useless_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
 
bool has_useful_pathkeys (PlannerInfo *root, RelOptInfo *rel)
 
Listappend_pathkeys (List *target, List *source)
 
PathKeymake_canonical_pathkey (PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
 
void add_paths_to_append_rel (PlannerInfo *root, RelOptInfo *rel, List *live_childrels)
 

Variables

PGDLLIMPORT bool enable_geqo
 
PGDLLIMPORT int geqo_threshold
 
PGDLLIMPORT int min_parallel_table_scan_size
 
PGDLLIMPORT int min_parallel_index_scan_size
 
PGDLLIMPORT bool enable_group_by_reordering
 
PGDLLIMPORT set_rel_pathlist_hook_type set_rel_pathlist_hook
 
PGDLLIMPORT set_join_pathlist_hook_type set_join_pathlist_hook
 
PGDLLIMPORT join_search_hook_type join_search_hook
 

Typedef Documentation

◆ ec_matches_callback_type

typedef bool(* ec_matches_callback_type) (PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg)

Definition at line 122 of file paths.h.

◆ join_search_hook_type

typedef RelOptInfo *(* join_search_hook_type) (PlannerInfo *root, int levels_needed, List *initial_rels)

Definition at line 46 of file paths.h.

◆ set_join_pathlist_hook_type

typedef void(* set_join_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)

Definition at line 37 of file paths.h.

◆ set_rel_pathlist_hook_type

typedef void(* set_rel_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte)

Definition at line 30 of file paths.h.

Enumeration Type Documentation

◆ PathKeysComparison

Enumerator
PATHKEYS_EQUAL 
PATHKEYS_BETTER1 
PATHKEYS_BETTER2 
PATHKEYS_DIFFERENT 

Definition at line 205 of file paths.h.

206{
207 PATHKEYS_EQUAL, /* pathkeys are identical */
208 PATHKEYS_BETTER1, /* pathkey 1 is a superset of pathkey 2 */
209 PATHKEYS_BETTER2, /* vice versa */
210 PATHKEYS_DIFFERENT, /* neither pathkey includes the other */
PathKeysComparison
Definition: paths.h:206
@ PATHKEYS_BETTER2
Definition: paths.h:209
@ PATHKEYS_BETTER1
Definition: paths.h:208
@ PATHKEYS_DIFFERENT
Definition: paths.h:210
@ PATHKEYS_EQUAL
Definition: paths.h:207

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{
2818 Relids top_parent_relids = child_joinrel->top_parent_relids;
2819 Relids child_relids = child_joinrel->relids;
2820 Bitmapset *matching_ecs;
2821 MemoryContext oldcontext;
2822 int i;
2823
2824 Assert(IS_JOIN_REL(child_joinrel) && IS_JOIN_REL(parent_joinrel));
2825
2826 /* We need consider only ECs that mention the parent joinrel */
2827 matching_ecs = get_eclass_indexes_for_relids(root, top_parent_relids);
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 */
2837 oldcontext = MemoryContextSwitchTo(root->planner_cxt);
2838
2839 i = -1;
2840 while ((i = bms_next_member(matching_ecs, i)) >= 0)
2841 {
2842 EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
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 */
2850 if (cur_ec->ec_has_volatile)
2851 continue;
2852
2853 /* Sanity check on get_eclass_indexes_for_relids result */
2854 Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids));
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 */
2861 num_members = list_length(cur_ec->ec_members);
2862 for (int pos = 0; pos < num_members; pos++)
2863 {
2864 EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2865
2866 if (cur_em->em_is_const)
2867 continue; /* ignore consts here */
2868
2869 /*
2870 * We consider only original EC members here, not
2871 * already-transformed child members.
2872 */
2873 if (cur_em->em_is_child)
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 */
2880 if (bms_membership(cur_em->em_relids) != BMS_MULTIPLE)
2881 continue;
2882
2883 /* Does this member reference child's topmost parent rel? */
2884 if (bms_overlap(cur_em->em_relids, top_parent_relids))
2885 {
2886 /* Yes, generate transformed child version */
2887 Expr *child_expr;
2888 Relids new_relids;
2889
2890 if (parent_joinrel->reloptkind == RELOPT_JOINREL)
2891 {
2892 /* Simple single-level transformation */
2893 child_expr = (Expr *)
2895 (Node *) cur_em->em_expr,
2896 nappinfos, appinfos);
2897 }
2898 else
2899 {
2900 /* Must do multi-level transformation */
2901 Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
2902 child_expr = (Expr *)
2904 (Node *) cur_em->em_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 */
2915 new_relids = bms_difference(cur_em->em_relids,
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
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1306
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:917
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:781
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:582
@ BMS_MULTIPLE
Definition: bitmapset.h:73
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))
int i
Definition: isn.c:74
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
#define IS_JOIN_REL(rel)
Definition: pathnodes.h:868
@ RELOPT_JOINREL
Definition: pathnodes.h:852
@ RELOPT_OTHER_JOINREL
Definition: pathnodes.h:854
static int list_length(const List *l)
Definition: pg_list.h:152
static void * list_nth(const List *list, int n)
Definition: pg_list.h:299
tree ctl root
Definition: radixtree.h:1857
JoinDomain * em_jdomain
Definition: pathnodes.h:1474
Definition: nodes.h:129
Relids relids
Definition: pathnodes.h:895
Relids top_parent_relids
Definition: pathnodes.h:1033
RelOptKind reloptkind
Definition: pathnodes.h:889

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{
2696 Relids top_parent_relids = child_rel->top_parent_relids;
2697 Relids child_relids = child_rel->relids;
2698 int i;
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 */
2704 Assert(root->ec_merging_done);
2705 Assert(IS_SIMPLE_REL(parent_rel));
2706
2707 i = -1;
2708 while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0)
2709 {
2710 EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
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 */
2718 if (cur_ec->ec_has_volatile)
2719 continue;
2720
2721 /* Sanity check eclass_indexes only contain ECs for parent_rel */
2722 Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids));
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 */
2729 num_members = list_length(cur_ec->ec_members);
2730 for (int pos = 0; pos < num_members; pos++)
2731 {
2732 EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2733
2734 if (cur_em->em_is_const)
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 */
2745 if (cur_em->em_is_child)
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 */
2756 if (bms_is_subset(cur_em->em_relids, top_parent_relids) &&
2757 !bms_is_empty(cur_em->em_relids))
2758 {
2759 /* OK, generate transformed child version */
2760 Expr *child_expr;
2761 Relids new_relids;
2762
2763 if (parent_rel->reloptkind == RELOPT_BASEREL)
2764 {
2765 /* Simple single-level transformation */
2766 child_expr = (Expr *)
2768 (Node *) cur_em->em_expr,
2769 1, &appinfo);
2770 }
2771 else
2772 {
2773 /* Must do multi-level transformation */
2774 child_expr = (Expr *)
2776 (Node *) cur_em->em_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 */
2787 new_relids = bms_difference(cur_em->em_relids,
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 */
2796 child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
2797 }
2798 }
2799 }
2800}
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:412
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:815
#define bms_is_empty(a)
Definition: bitmapset.h:118
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:863
@ RELOPT_BASEREL
Definition: pathnodes.h:851
Bitmapset * eclass_indexes
Definition: pathnodes.h:976

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. */
807 if (sjinfo == NULL || sjinfo->ojrelid == 0)
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 */
816 if (sjinfo->jointype != JOIN_LEFT)
817 return bms_add_member(input_relids, sjinfo->ojrelid);
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 */
826 if (!bms_is_subset(sjinfo->commute_below_l, input_relids))
827 return input_relids;
828
829 /* OK to add OJ's own relid */
830 input_relids = bms_add_member(input_relids, sjinfo->ojrelid);
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 */
837 if (sjinfo->commute_above_l)
838 {
839 Relids commute_above_rels = bms_copy(sjinfo->commute_above_l);
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 */
849 foreach(lc, root->join_info_list)
850 {
851 SpecialJoinInfo *othersj = (SpecialJoinInfo *) lfirst(lc);
852
853 if (othersj == sjinfo ||
854 othersj->ojrelid == 0 || othersj->jointype != JOIN_LEFT)
855 continue; /* definitely not interesting */
856
857 if (!bms_is_member(othersj->ojrelid, commute_above_rels))
858 continue;
859
860 /* Add it if not already present but conditions now satisfied */
861 if (!bms_is_member(othersj->ojrelid, input_relids) &&
862 bms_is_subset(othersj->min_lefthand, input_relids) &&
863 bms_is_subset(othersj->min_righthand, input_relids) &&
864 bms_is_subset(othersj->commute_below_l, input_relids))
865 {
866 input_relids = bms_add_member(input_relids, othersj->ojrelid);
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}
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:510
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:122
List * lappend(List *list, void *datum)
Definition: list.c:339
@ JOIN_LEFT
Definition: nodes.h:294
#define lfirst(lc)
Definition: pg_list.h:172
Relids min_righthand
Definition: pathnodes.h:2930
Relids commute_above_l
Definition: pathnodes.h:2935
JoinType jointype
Definition: pathnodes.h:2933
Relids commute_below_l
Definition: pathnodes.h:2937
Relids min_lefthand
Definition: pathnodes.h:2929

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{
1324 List *subpaths = NIL;
1325 bool subpaths_valid = true;
1326 List *startup_subpaths = NIL;
1327 bool startup_subpaths_valid = true;
1328 List *partial_subpaths = NIL;
1329 List *pa_partial_subpaths = NIL;
1330 List *pa_nonpartial_subpaths = NIL;
1331 bool partial_subpaths_valid = true;
1332 bool pa_subpaths_valid;
1333 List *all_child_pathkeys = NIL;
1334 List *all_child_outers = NIL;
1335 ListCell *l;
1336 double partial_rows = -1;
1337
1338 /* If appropriate, consider parallel append */
1339 pa_subpaths_valid = enable_parallel_append && rel->consider_parallel;
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 {
1348 RelOptInfo *childrel = lfirst(l);
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 */
1360 if (childrel->pathlist != NIL &&
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 */
1372 if (rel->consider_startup && childrel->cheapest_startup_path != NULL)
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 */
1381 if (root->tuple_fraction > 0.0)
1382 cheapest_path =
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. */
1399 if (childrel->partial_pathlist != NIL)
1400 {
1401 cheapest_partial_path = linitial(childrel->partial_pathlist);
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 &&
1426 cheapest_partial_path->total_cost < nppath->total_cost))
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 */
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 */
1461 foreach(lcp, childrel->pathlist)
1462 {
1463 Path *childpath = (Path *) lfirst(lcp);
1464 List *childkeys = childpath->pathkeys;
1465 Relids childouter = PATH_REQ_OUTER(childpath);
1466
1467 /* Unsorted paths don't contribute to pathkey list */
1468 if (childkeys != NIL)
1469 {
1470 ListCell *lpk;
1471 bool found = false;
1472
1473 /* Have we already seen this ordering? */
1474 foreach(lpk, all_child_pathkeys)
1475 {
1476 List *existing_pathkeys = (List *) lfirst(lpk);
1477
1478 if (compare_pathkeys(existing_pathkeys,
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 {
1502 Relids existing_outers = (Relids) lfirst(lco);
1503
1504 if (bms_equal(existing_outers, childouter))
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)
1526 add_path(rel, (Path *) create_append_path(root, rel, subpaths, NIL,
1527 NIL, NULL, 0, false,
1528 -1));
1529
1530 /* build an AppendPath for the cheap startup paths, if valid */
1531 if (startup_subpaths_valid)
1532 add_path(rel, (Path *) create_append_path(root, rel, startup_subpaths,
1533 NIL, NIL, NULL, 0, false, -1));
1534
1535 /*
1536 * Consider an append of unordered, unparameterized partial paths. Make
1537 * it parallel-aware if possible.
1538 */
1539 if (partial_subpaths_valid && partial_subpaths != NIL)
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 {
1548 Path *path = lfirst(lc);
1549
1550 parallel_workers = Max(parallel_workers, path->parallel_workers);
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,
1566 pg_leftmost_one_pos32(list_length(live_childrels)) + 1);
1567 parallel_workers = Min(parallel_workers,
1569 }
1570 Assert(parallel_workers > 0);
1571
1572 /* Generate a partial append path. */
1573 appendpath = create_append_path(root, rel, NIL, partial_subpaths,
1574 NIL, NULL, parallel_workers,
1576 -1);
1577
1578 /*
1579 * Make sure any subsequent partial paths use the same row count
1580 * estimate.
1581 */
1582 partial_rows = appendpath->path.rows;
1583
1584 /* Add the path. */
1585 add_partial_path(rel, (Path *) appendpath);
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 */
1594 if (pa_subpaths_valid && pa_nonpartial_subpaths != NIL)
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 {
1606 Path *path = lfirst(lc);
1607
1608 parallel_workers = Max(parallel_workers, path->parallel_workers);
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,
1617 pg_leftmost_one_pos32(list_length(live_childrels)) + 1);
1618 parallel_workers = Min(parallel_workers,
1620 Assert(parallel_workers > 0);
1621
1622 appendpath = create_append_path(root, rel, pa_nonpartial_subpaths,
1623 pa_partial_subpaths,
1624 NIL, NULL, parallel_workers, true,
1625 partial_rows);
1626 add_partial_path(rel, (Path *) appendpath);
1627 }
1628
1629 /*
1630 * Also build unparameterized ordered append paths based on the collected
1631 * list of child pathkeys.
1632 */
1633 if (subpaths_valid)
1634 generate_orderedappend_paths(root, rel, live_childrels,
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 {
1652 Relids required_outer = (Relids) lfirst(l);
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 {
1660 RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr);
1661 Path *subpath;
1662
1663 if (childrel->pathlist == NIL)
1664 {
1665 /* failed to make a suitable path for this child */
1666 subpaths_valid = false;
1667 break;
1668 }
1669
1671 childrel,
1672 required_outer);
1673 if (subpath == NULL)
1674 {
1675 /* failed to make a suitable path for this child */
1676 subpaths_valid = false;
1677 break;
1678 }
1679 accumulate_append_subpath(subpath, &subpaths, NULL);
1680 }
1681
1682 if (subpaths_valid)
1683 add_path(rel, (Path *)
1684 create_append_path(root, rel, subpaths, NIL,
1685 NIL, required_outer, 0, false,
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 */
1696 if (list_length(live_childrels) == 1)
1697 {
1698 RelOptInfo *childrel = (RelOptInfo *) linitial(live_childrels);
1699
1700 /* skip the cheapest partial path, since we already used that above */
1701 for_each_from(l, childrel->partial_pathlist, 1)
1702 {
1703 Path *path = (Path *) lfirst(l);
1704 AppendPath *appendpath;
1705
1706 /* skip paths with no pathkeys. */
1707 if (path->pathkeys == NIL)
1708 continue;
1709
1710 appendpath = create_append_path(root, rel, NIL, list_make1(path),
1711 NIL, NULL,
1712 path->parallel_workers, true,
1713 partial_rows);
1714 add_partial_path(rel, (Path *) appendpath);
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
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:142
#define Min(x, y)
Definition: c.h:975
#define Max(x, y)
Definition: c.h:969
int max_parallel_workers_per_gather
Definition: costsize.c:143
bool enable_parallel_append
Definition: costsize.c:161
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:308
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
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:461
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1705
Bitmapset * Relids
Definition: pathnodes.h:30
static int pg_leftmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:41
#define NIL
Definition: pg_list.h:68
#define list_make1(x1)
Definition: pg_list.h:212
#define for_each_from(cell, lst, N)
Definition: pg_list.h:414
#define linitial(l)
Definition: pg_list.h:178
Path * get_cheapest_fractional_path(RelOptInfo *rel, double tuple_fraction)
Definition: planner.c:6478
Definition: pg_list.h:54
List * pathkeys
Definition: pathnodes.h:1701
Cardinality rows
Definition: pathnodes.h:1695
int parallel_workers
Definition: pathnodes.h:1692
Cost total_cost
Definition: pathnodes.h:1698
bool consider_parallel
Definition: pathnodes.h:911
List * pathlist
Definition: pathnodes.h:922
struct Path * cheapest_startup_path
Definition: pathnodes.h:925
struct Path * cheapest_total_path
Definition: pathnodes.h:926
bool consider_startup
Definition: pathnodes.h:907
List * partial_pathlist
Definition: pathnodes.h:924

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 */
144 if (joinrel->reloptkind == RELOPT_OTHER_JOINREL)
145 joinrelids = joinrel->top_parent_relids;
146 else
147 joinrelids = joinrel->relids;
148
149 extra.restrictlist = restrictlist;
150 extra.mergeclause_list = NIL;
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 {
171 case JOIN_SEMI:
172 case JOIN_ANTI:
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 */
178 extra.inner_unique = false; /* well, unproven */
179 break;
182 outerrel->relids);
183 break;
186 joinrel->relids,
187 outerrel->relids,
188 innerrel,
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 */
210 if (enable_mergejoin || jointype == JOIN_FULL)
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 */
223 if (jointype == JOIN_SEMI || jointype == JOIN_ANTI || extra.inner_unique)
224 compute_semi_anti_join_factors(root, joinrel, outerrel, innerrel,
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 */
242 foreach(lc, root->join_info_list)
243 {
244 SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);
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 */
253 if (bms_overlap(joinrelids, sjinfo2->min_righthand) &&
254 !bms_overlap(joinrelids, sjinfo2->min_lefthand))
256 bms_difference(root->all_baserels,
257 sjinfo2->min_righthand));
258
259 /* full joins constrain both sides symmetrically */
260 if (sjinfo2->jointype == JOIN_FULL &&
261 bms_overlap(joinrelids, sjinfo2->min_lefthand) &&
262 !bms_overlap(joinrelids, sjinfo2->min_righthand))
264 bms_difference(root->all_baserels,
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)
283 sort_inner_and_outer(root, joinrel, outerrel, innerrel,
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)
295 match_unsorted_outer(root, joinrel, outerrel, innerrel,
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 */
321 if (enable_hashjoin || jointype == JOIN_FULL)
322 hash_inner_and_outer(root, joinrel, outerrel, innerrel,
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 */
343 set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
344 jointype, &extra);
345}
bool innerrel_is_unique(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:1230
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
bool enable_hashjoin
Definition: costsize.c:157
bool enable_mergejoin
Definition: costsize.c:156
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
set_join_pathlist_hook_type set_join_pathlist_hook
Definition: joinpath.c:33
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
@ JOIN_SEMI
Definition: nodes.h:307
@ JOIN_FULL
Definition: nodes.h:295
@ JOIN_INNER
Definition: nodes.h:293
@ JOIN_UNIQUE_OUTER
Definition: nodes.h:316
@ JOIN_UNIQUE_INNER
Definition: nodes.h:317
@ JOIN_ANTI
Definition: nodes.h:308
List * mergeclause_list
Definition: pathnodes.h:3266
Relids param_source_rels
Definition: pathnodes.h:3270
SemiAntiJoinFactors semifactors
Definition: pathnodes.h:3269
SpecialJoinInfo * sjinfo
Definition: pathnodes.h:3268
Relids lateral_relids
Definition: pathnodes.h:937

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;
2947 ListCell *lc2 = list_head(setop_pathkeys);
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)
2959 elog(ERROR, "too few pathkeys for set operation");
2960
2961 pk = lfirst_node(PathKey, lc2);
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,
2975 exprType((Node *) tle->expr));
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 */
2986 child_rel->eclass_indexes = bms_add_range(child_rel->eclass_indexes, 0,
2987 list_length(root->eq_classes) - 1);
2988}
Bitmapset * bms_add_range(Bitmapset *a, int lower, int upper)
Definition: bitmapset.c:1019
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:42
#define lfirst_node(type, lc)
Definition: pg_list.h:176
static ListCell * list_head(const List *l)
Definition: pg_list.h:128
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:343
Expr * expr
Definition: primnodes.h:2219

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()

List * append_pathkeys ( List target,
List source 
)

Definition at line 107 of file pathkeys.c.

108{
109 ListCell *lc;
110
111 Assert(target != NIL);
112
113 foreach(lc, source)
114 {
115 PathKey *pk = lfirst_node(PathKey, lc);
116
117 if (!pathkey_is_redundant(pk, target))
118 target = lappend(target, pk);
119 }
120 return target;
121}
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:159
static rewind_source * source
Definition: pg_rewind.c:89

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))
1015 elog(ERROR, "operator %u is not a valid ordering operator",
1016 opno);
1017
1019 expr,
1020 opfamily,
1021 opcintype,
1022 exprCollation((Node *) expr),
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}
int16_t int16
Definition: c.h:497
bool get_ordering_op_properties(Oid opno, Oid *opfamily, Oid *opcintype, int16 *strategy)
Definition: lsyscache.c:208
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:821
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
unsigned int Oid
Definition: postgres_ext.h:32
#define BTGreaterStrategyNumber
Definition: stratnum.h:33

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{
744 List *retval = NIL;
745 ListCell *lc;
746 int i;
747
748 if (index->sortopfamily == NULL)
749 return NIL; /* non-orderable index */
750
751 i = 0;
752 foreach(lc, index->indextlist)
753 {
754 TargetEntry *indextle = (TargetEntry *) lfirst(lc);
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 */
764 if (i >= index->nkeycolumns)
765 break;
766
767 /* We assume we don't need to make a copy of the tlist item */
768 indexkey = indextle->expr;
769
770 if (ScanDirectionIsBackward(scandir))
771 {
772 reverse_sort = !index->reverse_sort[i];
773 nulls_first = !index->nulls_first[i];
774 }
775 else
776 {
777 reverse_sort = index->reverse_sort[i];
778 nulls_first = index->nulls_first[i];
779 }
780
781 /*
782 * OK, try to make a canonical pathkey for this sort key.
783 */
785 indexkey,
786 index->sortopfamily[i],
787 index->opcintype[i],
788 index->indexcollations[i],
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 */
801 if (!pathkey_is_redundant(cpathkey, retval))
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
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:50
Definition: type.h:96

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 */
1300 Assert(jointype != JOIN_RIGHT_SEMI);
1301
1302 if (jointype == JOIN_FULL ||
1303 jointype == JOIN_RIGHT ||
1304 jointype == JOIN_RIGHT_ANTI)
1305 return NIL;
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 */
1316 return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1317}
@ JOIN_RIGHT
Definition: nodes.h:296
@ JOIN_RIGHT_SEMI
Definition: nodes.h:309
@ JOIN_RIGHT_ANTI
Definition: nodes.h:310
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{
922 List *retval = NIL;
923 PartitionScheme partscheme = partrel->part_scheme;
924 int i;
925
926 Assert(partscheme != NULL);
927 Assert(partitions_are_ordered(partrel->boundinfo, partrel->live_parts));
928 /* For now, we can only cope with baserels */
929 Assert(IS_SIMPLE_REL(partrel));
930
931 for (i = 0; i < partscheme->partnatts; i++)
932 {
933 PathKey *cpathkey;
934 Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]);
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,
945 partscheme->partopfamily[i],
946 partscheme->partopcintype[i],
947 partscheme->partcollation[i],
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 */
961 if (!pathkey_is_redundant(cpathkey, retval))
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
Bitmapset * live_parts
Definition: pathnodes.h:1063

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()

Expr * canonicalize_ec_expression ( Expr expr,
Oid  req_type,
Oid  req_collation 
)

Definition at line 471 of file equivclass.c.

472{
473 Oid expr_type = exprType((Node *) expr);
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 ||
486 exprCollation((Node *) expr) != req_collation)
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
498 req_typmod = exprTypmod((Node *) expr);
499
500 /*
501 * Use applyRelabelType so that we preserve const-flatness. This is
502 * important since eval_const_expressions has already been applied.
503 */
504 expr = (Expr *) applyRelabelType((Node *) expr,
505 req_type, req_typmod, req_collation,
506 COERCE_IMPLICIT_CAST, -1, false);
507 }
508
509 return expr;
510}
int32_t int32
Definition: c.h:498
int32 exprTypmod(const Node *expr)
Definition: nodeFuncs.c:301
Node * applyRelabelType(Node *arg, Oid rtype, int32 rtypmod, Oid rcollid, CoercionForm rformat, int rlocation, bool overwrite_ok)
Definition: nodeFuncs.c:636
@ COERCE_IMPLICIT_CAST
Definition: primnodes.h:753

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. */
3975 Assert(IS_SIMPLE_REL(rel));
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;
3983 foreach(lc, rel->indexlist)
3984 {
3986
3987 index->indrestrictinfo = rel->baserestrictinfo;
3988 if (index->indpred)
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 */
4001 clauselist = list_copy(rel->baserestrictinfo);
4002
4003 /* Scan the rel's join clauses */
4004 foreach(lc, rel->joininfo)
4005 {
4006 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
4007
4008 /* Check if clause can be moved to this rel */
4009 if (!join_clause_is_movable_to(rinfo, 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 */
4024 otherrels = bms_difference(root->all_query_rels,
4026 else
4027 otherrels = bms_difference(root->all_query_rels, rel->relids);
4028 otherrels = bms_del_members(otherrels, rel->nulling_relids);
4029
4030 if (!bms_is_empty(otherrels))
4031 clauselist =
4032 list_concat(clauselist,
4034 bms_union(rel->relids,
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 */
4052 is_target_rel = (bms_is_member(rel->relid, root->all_result_relids) ||
4053 get_plan_rowmark(root->rowMarks, rel->relid) != NULL);
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 */
4062 foreach(lc, rel->indexlist)
4063 {
4065 ListCell *lcr;
4066
4067 if (index->indpred == NIL)
4068 continue; /* ignore non-partial indexes here */
4069
4070 if (!index->predOK) /* don't repeat work if already proven OK */
4071 index->predOK = predicate_implied_by(index->indpred, clauselist,
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 */
4079 index->indrestrictinfo = NIL;
4080 foreach(lcr, rel->baserestrictinfo)
4081 {
4082 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcr);
4083
4084 /* predicate_implied_by() assumes first arg is immutable */
4085 if (contain_mutable_functions((Node *) rinfo->clause) ||
4087 index->indpred, false))
4088 index->indrestrictinfo = lappend(index->indrestrictinfo, rinfo);
4089 }
4090 }
4091}
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:1161
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:251
bool contain_mutable_functions(Node *clause)
Definition: clauses.c:369
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo)
Definition: equivclass.c:1386
List * list_concat(List *list1, const List *list2)
Definition: list.c:561
List * list_copy(const List *oldlist)
Definition: list.c:1573
@ RELOPT_OTHER_MEMBER_REL
Definition: pathnodes.h:853
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
List * baserestrictinfo
Definition: pathnodes.h:1009
List * joininfo
Definition: pathnodes.h:1015
Index relid
Definition: pathnodes.h:942
List * indexlist
Definition: pathnodes.h:968
Relids nulling_relids
Definition: pathnodes.h:962
Expr * clause
Definition: pathnodes.h:2599

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)
315 return PATHKEYS_EQUAL;
316
317 forboth(key1, keys1, key2, keys2)
318 {
319 PathKey *pathkey1 = (PathKey *) lfirst(key1);
320 PathKey *pathkey2 = (PathKey *) lfirst(key2);
321
322 if (pathkey1 != pathkey2)
323 return PATHKEYS_DIFFERENT; /* no need to keep looking */
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)
331 return PATHKEYS_BETTER1; /* key1 is longer */
332 if (key2 != NULL)
333 return PATHKEYS_BETTER2; /* key2 is longer */
334 return PATHKEYS_EQUAL;
335}
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:518

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 */
4245 if (rel->rel_parallel_workers != -1)
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 */
4257 if (rel->reloptkind == RELOPT_BASEREL &&
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 */
4274 heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
4275 while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
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 */
4292 index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
4293 while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
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}
int min_parallel_index_scan_size
Definition: allpaths.c:82
int min_parallel_table_scan_size
Definition: allpaths.c:81
uint32 BlockNumber
Definition: block.h:31
int rel_parallel_workers
Definition: pathnodes.h:980

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{
1058 List *retval = NIL;
1059 int retvallen = 0;
1060 int outer_query_keys = list_length(root->query_pathkeys);
1061 ListCell *i;
1062
1063 foreach(i, subquery_pathkeys)
1064 {
1065 PathKey *sub_pathkey = (PathKey *) lfirst(i);
1066 EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
1067 PathKey *best_pathkey = NULL;
1068
1069 if (sub_eclass->ec_has_volatile)
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
1079 if (sub_eclass->ec_sortref == 0) /* can't happen */
1080 elog(ERROR, "volatile EquivalenceClass has no sortref");
1081 tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
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
1091 Assert(list_length(sub_eclass->ec_members) == 1);
1092 sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
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;
1144 ListCell *j;
1145
1146 foreach(j, sub_eclass->ec_members)
1147 {
1148 EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
1149 Expr *sub_expr = sub_member->em_expr;
1150 Oid sub_expr_type = sub_member->em_datatype;
1151 Oid sub_expr_coll = sub_eclass->ec_collation;
1152 ListCell *k;
1153
1154 if (sub_member->em_is_child)
1155 continue; /* ignore children here */
1156
1157 foreach(k, subquery_tlist)
1158 {
1159 TargetEntry *tle = (TargetEntry *) lfirst(k);
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 */
1177 tle_expr = canonicalize_ec_expression(tle->expr,
1178 sub_expr_type,
1179 sub_expr_coll);
1180 if (!equal(tle_expr, sub_expr))
1181 continue;
1182
1183 /* See if we have a matching EC for the TLE */
1184 outer_ec = get_eclass_for_sort_expr(root,
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
1200 outer_pk = make_canonical_pathkey(root,
1201 outer_ec,
1202 sub_pathkey->pk_opfamily,
1203 sub_pathkey->pk_strategy,
1204 sub_pathkey->pk_nulls_first);
1205 /* score = # of equivalence peers */
1206 score = list_length(outer_ec->ec_members) - 1;
1207 /* +1 if it matches the proper query_pathkeys item */
1208 if (retvallen < outer_query_keys &&
1209 list_nth(root->query_pathkeys, retvallen) == outer_pk)
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 */
1231 if (!pathkey_is_redundant(best_pathkey, retval))
1232 {
1233 retval = lappend(retval, best_pathkey);
1234 retvallen++;
1235 }
1236 }
1237
1238 return retval;
1239}
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:223
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
int j
Definition: isn.c:75
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
List * ec_opfamilies
Definition: pathnodes.h:1418
bool pk_nulls_first
Definition: pathnodes.h:1506
int pk_strategy
Definition: pathnodes.h:1505
Oid pk_opfamily
Definition: pathnodes.h:1504
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 */
253 if (rel->indexlist == NIL)
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 */
260 foreach(lc, rel->indexlist)
261 {
263
264 /* Protect limited-size array in IndexClauseSets */
265 Assert(index->nkeycolumns <= INDEX_MAX_KEYS);
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 */
272 if (index->indpred != NIL && !index->predOK)
273 continue;
274
275 /*
276 * Identify the restriction clauses that can match the index.
277 */
278 MemSet(&rclauseset, 0, sizeof(rclauseset));
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 */
286 get_index_paths(root, rel, index, &rclauseset,
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 */
295 MemSet(&jclauseset, 0, sizeof(jclauseset));
297 &jclauseset, &joinorclauses);
298
299 /*
300 * Look for EquivalenceClasses that can generate joinclauses matching
301 * the index.
302 */
303 MemSet(&eclauseset, 0, sizeof(eclauseset));
305 &eclauseset);
306
307 /*
308 * If we found any plain or eclass join clauses, build parameterized
309 * index paths using them.
310 */
311 if (jclauseset.nonempty || eclauseset.nonempty)
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 */
323 indexpaths = generate_bitmap_or_paths(root, rel,
324 rel->baserestrictinfo, NIL);
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 */
331 indexpaths = generate_bitmap_or_paths(root, rel,
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 */
342 if (bitindexpaths != NIL)
343 {
344 Path *bitmapqual;
345 BitmapHeapPath *bpath;
346
347 bitmapqual = choose_bitmap_and(root, rel, bitindexpaths);
348 bpath = create_bitmap_heap_path(root, rel, bitmapqual,
349 rel->lateral_relids, 1.0, 0);
350 add_path(rel, (Path *) bpath);
351
352 /* create a partial bitmap heap path */
353 if (rel->consider_parallel && rel->lateral_relids == NULL)
354 create_partial_bitmap_paths(root, rel, bitmapqual);
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 */
367 if (bitjoinpaths != NIL)
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 {
375 Path *path = (Path *) lfirst(lc);
376 Relids required_outer = PATH_REQ_OUTER(path);
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 {
385 Relids max_outers = (Relids) lfirst(lc);
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 {
397 Path *path = (Path *) lfirst(lcp);
398
399 if (bms_is_subset(PATH_REQ_OUTER(path), max_outers))
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 */
410 bitmapqual = choose_bitmap_and(root, rel, this_path_set);
411
412 /* And push that path into the mix */
413 required_outer = PATH_REQ_OUTER(bitmapqual);
414 loop_count = get_loop_count(root, rel->relid, required_outer);
415 bpath = create_bitmap_heap_path(root, rel, bitmapqual,
416 required_outer, loop_count, 0);
417 add_path(rel, (Path *) bpath);
418 }
419 }
420}
void create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual)
Definition: allpaths.c:4200
#define MemSet(start, val, len)
Definition: c.h:991
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
List * list_append_unique(List *list, void *datum)
Definition: list.c:1343
BitmapHeapPath * create_bitmap_heap_path(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual, Relids required_outer, double loop_count, int parallel_degree)
Definition: pathnode.c:1098
#define INDEX_MAX_KEYS
bool nonempty
Definition: indxpath.c:57

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 */
4207 pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
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
514 if (tidquals != NIL && (enable_tidscan || isCurrentOf))
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 */
520 Relids required_outer = rel->lateral_relids;
521
522 add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
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. */
536 if (!enable_tidscan)
537 return false;
538
539 /*
540 * If there are range quals in the baserestrict list, generate a
541 * TidRangePath.
542 */
544 rel);
545
546 if (tidrangequals != NIL)
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 */
552 Relids required_outer = rel->lateral_relids;
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 */
564 if (rel->has_eclass_joins)
565 {
566 List *clauses;
567
568 /* Generate clauses, skipping any that join to lateral_referencers */
570 rel,
572 NULL,
574
575 /* Generate a path for each usable join clause */
576 BuildParameterizedTidPaths(root, rel, clauses);
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}
bool enable_tidscan
Definition: costsize.c:149
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
Relids lateral_referencers
Definition: pathnodes.h:966
bool has_eclass_joins
Definition: pathnodes.h:1017
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
3274 Assert(!eclass->ec_merged);
3275
3276 /*
3277 * Won't generate joinclauses if const or single-member (the latter test
3278 * covers the volatile case too)
3279 */
3280 if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
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 */
3290 if (IS_OTHER_REL(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 */
3299 if (bms_is_subset(eclass->ec_relids, relids))
3300 return false;
3301
3302 /* To join, we need a member not in the given rel */
3303 foreach(lc, eclass->ec_members)
3304 {
3305 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
3306
3307 if (cur_em->em_is_child)
3308 continue; /* ignore children here */
3309
3310 if (!bms_overlap(cur_em->em_relids, relids))
3311 return true;
3312 }
3313
3314 return false;
3315}
#define IS_OTHER_REL(rel)
Definition: pathnodes.h:878
static struct cvec * eclass(struct vars *v, chr c, int cases)
Definition: regc_locale.c:500

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
2503 foreach(lc1, root->eq_classes)
2504 {
2506 bool item1member = false;
2507 bool item2member = false;
2508 ListCell *lc2;
2509
2510 /* Never match to a volatile EC */
2511 if (ec->ec_has_volatile)
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 */
2521 if (OidIsValid(opfamily) &&
2522 !list_member_oid(ec->ec_opfamilies, opfamily))
2523 continue;
2524
2525 foreach(lc2, ec->ec_members)
2526 {
2528
2529 if (em->em_is_child)
2530 continue; /* ignore children here */
2531 if (equal(item1, em->em_expr))
2532 item1member = true;
2533 else if (equal(item2, em->em_expr))
2534 item2member = true;
2535 /* Exit as soon as equality is proven */
2536 if (item1member && item2member)
2537 return true;
2538 }
2539 }
2540 return false;
2541}
#define OidIsValid(objectId)
Definition: c.h:746
bool list_member_oid(const List *list, Oid datum)
Definition: list.c:722

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 */
852 exprvars = pull_var_clause((Node *) exprs,
857
858 foreach(lc, ec->ec_members)
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 */
868 if (em->em_is_const)
869 continue;
870
871 /*
872 * Ignore child members unless they belong to the requested rel.
873 */
874 if (em->em_is_child &&
875 !bms_is_subset(em->em_relids, relids))
876 continue;
877
878 /*
879 * Match if all Vars and quasi-Vars are present in "exprs".
880 */
881 emvars = pull_var_clause((Node *) em->em_expr,
885 foreach(lc2, emvars)
886 {
887 if (!list_member(exprvars, lfirst(lc2)))
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}
bool is_parallel_safe(PlannerInfo *root, Node *node)
Definition: clauses.c:752
void list_free(List *list)
Definition: list.c:1546
bool list_member(const List *list, const void *datum)
Definition: list.c:661
#define PVC_INCLUDE_WINDOWFUNCS
Definition: optimizer.h:189
#define PVC_INCLUDE_PLACEHOLDERS
Definition: optimizer.h:191
#define PVC_INCLUDE_CONVERTROWTYPES
Definition: optimizer.h:193
#define PVC_INCLUDE_AGGREGATES
Definition: optimizer.h:187
List * pull_var_clause(Node *node, int flags)
Definition: var.c:653

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
2656 Assert(ec->ec_has_const);
2657 Assert(!em->em_is_const);
2658 foreach(lc, ec->ec_derives)
2659 {
2660 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
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 */
770 while (expr && IsA(expr, RelabelType))
771 expr = ((RelabelType *) expr)->arg;
772
773 foreach(lc, ec->ec_members)
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 */
782 if (em->em_is_const)
783 continue;
784
785 /*
786 * Ignore child members unless they belong to the requested rel.
787 */
788 if (em->em_is_child &&
789 !bms_is_subset(em->em_relids, relids))
790 continue;
791
792 /*
793 * Match if same expression (after stripping relabel).
794 */
795 emexpr = em->em_expr;
796 while (emexpr && IsA(emexpr, RelabelType))
797 emexpr = ((RelabelType *) emexpr)->arg;
798
799 if (equal(emexpr, expr))
800 return em;
801 }
802
803 return NULL;
804}
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
void * arg

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{
1547 List *mergeclauses = NIL;
1548 ListCell *i;
1549
1550 /* make sure we have eclasses cached in the clauses */
1551 foreach(i, restrictinfos)
1552 {
1553 RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1554
1556 }
1557
1558 foreach(i, pathkeys)
1559 {
1560 PathKey *pathkey = (PathKey *) lfirst(i);
1561 EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1562 List *matched_restrictinfos = NIL;
1563 ListCell *j;
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 */
1602 foreach(j, restrictinfos)
1603 {
1604 RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
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 */
1618 if (matched_restrictinfos == NIL)
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 */
1045 root->ec_merging_done = true;
1046
1047 ec_index = 0;
1048 foreach(lc, root->eq_classes)
1049 {
1051 bool can_generate_joinclause = false;
1052 int i;
1053
1054 Assert(ec->ec_merged == NULL); /* else shouldn't be in list */
1055 Assert(!ec->ec_broken); /* not yet anyway... */
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 */
1062 if (list_length(ec->ec_members) > 1)
1063 {
1064 if (ec->ec_has_const)
1066 else
1068
1069 /* Recover if we failed to generate required derived clauses */
1070 if (ec->ec_broken)
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;
1086 while ((i = bms_next_member(ec->ec_relids, i)) > 0)
1087 {
1088 RelOptInfo *rel = root->simple_rel_array[i];
1089
1090 /* ignore the RTE_GROUP RTE */
1091 if (i == root->group_rtindex)
1092 continue;
1093
1094 if (rel == NULL) /* must be an outer join */
1095 {
1096 Assert(bms_is_member(i, root->outer_join_rels));
1097 continue;
1098 }
1099
1101
1103 ec_index);
1104
1105 if (can_generate_joinclause)
1106 rel->has_eclass_joins = true;
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
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:1431

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. */
3094 if (rel->partial_pathlist == NIL)
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 */
3106 cheapest_partial_path = linitial(rel->partial_pathlist);
3107 rows = compute_gather_rows(cheapest_partial_path);
3108 simple_gather_path = (Path *)
3109 create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
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 */
3117 foreach(lc, rel->partial_pathlist)
3118 {
3119 Path *subpath = (Path *) lfirst(lc);
3120 GatherMergePath *path;
3121
3122 if (subpath->pathkeys == NIL)
3123 continue;
3124
3127 subpath->pathkeys, NULL, rowsp);
3128 add_path(rel, &path->path);
3129 }
3130}
double compute_gather_rows(Path *path)
Definition: costsize.c:6610
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
struct PathTarget * reltarget
Definition: pathnodes.h:917

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{
3021 List *result = NIL;
3022 bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
3023 Relids parent_relids;
3024 int i;
3025
3026 /* Should be OK to rely on eclass_indexes */
3027 Assert(root->ec_merging_done);
3028
3029 /* Indexes are available only on base or "other" member relations. */
3030 Assert(IS_SIMPLE_REL(rel));
3031
3032 /* If it's a child rel, we'll need to know what its parent(s) are */
3033 if (is_child_rel)
3034 parent_relids = find_childrel_parents(root, rel);
3035 else
3036 parent_relids = NULL; /* not used, but keep compiler quiet */
3037
3038 i = -1;
3039 while ((i = bms_next_member(rel->eclass_indexes, i)) >= 0)
3040 {
3041 EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
3042 EquivalenceMember *cur_em;
3043 ListCell *lc2;
3044
3045 /* Sanity check eclass_indexes only contain ECs for rel */
3046 Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
3047
3048 /*
3049 * Won't generate joinclauses if const or single-member (the latter
3050 * test covers the volatile case too)
3051 */
3052 if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
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;
3066 foreach(lc2, cur_ec->ec_members)
3067 {
3068 cur_em = (EquivalenceMember *) lfirst(lc2);
3069 if (bms_equal(cur_em->em_relids, rel->relids) &&
3070 callback(root, rel, cur_ec, cur_em, callback_arg))
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 */
3082 foreach(lc2, cur_ec->ec_members)
3083 {
3084 EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
3085 Oid eq_op;
3086 RestrictInfo *rinfo;
3087
3088 if (other_em->em_is_child)
3089 continue; /* ignore children here */
3090
3091 /* Make sure it'll be a join to a different rel */
3092 if (other_em == cur_em ||
3093 bms_overlap(other_em->em_relids, rel->relids))
3094 continue;
3095
3096 /* Forget it if caller doesn't want joins to this rel */
3097 if (bms_overlap(other_em->em_relids, prohibited_rels))
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 &&
3105 bms_overlap(parent_relids, other_em->em_relids))
3106 continue;
3107
3108 eq_op = select_equality_operator(cur_ec,
3109 cur_em->em_datatype,
3110 other_em->em_datatype);
3111 if (!OidIsValid(eq_op))
3112 continue;
3113
3114 /* set parent_ec to mark as redundant with other joinclauses */
3115 rinfo = create_join_clause(root, cur_ec, eq_op,
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{
1392 List *result = NIL;
1393 Relids inner_relids = inner_rel->relids;
1394 Relids nominal_inner_relids;
1395 Relids nominal_join_relids;
1396 Bitmapset *matching_ecs;
1397 int i;
1398
1399 /* If inner rel is a child, extra setup work is needed */
1400 if (IS_OTHER_REL(inner_rel))
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);
1408 nominal_join_relids = add_outer_joins_to_relids(root,
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 */
1432 if (sjinfo && sjinfo->ojrelid != 0)
1433 matching_ecs = get_eclass_indexes_for_relids(root, nominal_join_relids);
1434 else
1435 matching_ecs = get_common_eclass_indexes(root, nominal_inner_relids,
1436 outer_relids);
1437
1438 i = -1;
1439 while ((i = bms_next_member(matching_ecs, i)) >= 0)
1440 {
1441 EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
1442 List *sublist = NIL;
1443
1444 /* ECs containing consts do not need any further enforcement */
1445 if (ec->ec_has_const)
1446 continue;
1447
1448 /* Single-member ECs won't generate any deductions */
1449 if (list_length(ec->ec_members) <= 1)
1450 continue;
1451
1452 /* Sanity check that this eclass overlaps the join */
1453 Assert(bms_overlap(ec->ec_relids, nominal_join_relids));
1454
1455 if (!ec->ec_broken)
1457 ec,
1458 join_relids,
1459 outer_relids,
1460 inner_relids);
1461
1462 /* Recover if we failed to generate required derived clauses */
1463 if (ec->ec_broken)
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{
1492 List *result = NIL;
1493 Relids inner_relids = inner_rel->relids;
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 */
1499 if (IS_OTHER_REL(inner_rel))
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 {
1517 List *sublist = NIL;
1518
1519 /* ECs containing consts do not need any further enforcement */
1520 if (ec->ec_has_const)
1521 continue;
1522
1523 /* Single-member ECs won't generate any deductions */
1524 if (list_length(ec->ec_members) <= 1)
1525 continue;
1526
1527 /* We can quickly ignore any that don't overlap the join, too */
1528 if (!bms_overlap(ec->ec_relids, nominal_join_relids))
1529 continue;
1530
1531 if (!ec->ec_broken)
1533 ec,
1534 join_relids,
1535 outer_relids,
1536 inner_relids);
1537
1538 /* Recover if we failed to generate required derived clauses */
1539 if (ec->ec_broken)
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{
4326 List *live_children = NIL;
4327 int cnt_parts;
4328 int num_parts;
4329 RelOptInfo **part_rels;
4330
4331 /* Handle only join relations here. */
4332 if (!IS_JOIN_REL(rel))
4333 return;
4334
4335 /* We've nothing to do if the relation is not partitioned. */
4336 if (!IS_PARTITIONED_REL(rel))
4337 return;
4338
4339 /* The relation should have consider_partitionwise_join set. */
4341
4342 /* Guard against stack overflow due to overly deep partition hierarchy. */
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. */
4361 if (child_rel->pathlist == NIL)
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. */
4375 if (IS_DUMMY_REL(child_rel))
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. */
4393 add_paths_to_append_rel(root, rel, live_children);
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
void pprint(const void *obj)
Definition: print.c:54
void mark_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1385
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:269
#define IS_DUMMY_REL(r)
Definition: pathnodes.h:1982
#define IS_PARTITIONED_REL(rel)
Definition: pathnodes.h:1086
void check_stack_depth(void)
Definition: stack_depth.c:95
bool consider_partitionwise_join
Definition: pathnodes.h:1023

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;
3227 List *useful_pathkeys_list = NIL;
3228 Path *cheapest_partial_path = NULL;
3229
3230 /* If there are no partial paths, there's nothing to do here. */
3231 if (rel->partial_pathlist == NIL)
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 */
3239 generate_gather_paths(root, rel, override_rows);
3240
3241 /* consider incremental sort for interesting orderings */
3242 useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel, true);
3243
3244 /* used for explicit (full) sort paths */
3245 cheapest_partial_path = linitial(rel->partial_pathlist);
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 {
3253 List *useful_pathkeys = lfirst(lc);
3254 ListCell *lc2;
3255 bool is_sorted;
3256 int presorted_keys;
3257
3258 foreach(lc2, rel->partial_pathlist)
3259 {
3260 Path *subpath = (Path *) lfirst(lc2);
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 */
3286 if (subpath != cheapest_partial_path &&
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 */
3302 if (presorted_keys == 0 || !enable_incremental_sort)
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);
3318 path = create_gather_merge_path(root, rel,
3319 subpath,
3320 rel->reltarget,
3321 subpath->pathkeys,
3322 NULL,
3323 rowsp);
3324
3325 add_path(rel, &path->path);
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 enable_incremental_sort
Definition: costsize.c:151
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 {
676 Path *path = (Path *) lfirst(l);
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
686 if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
687 bms_is_subset(PATH_REQ_OUTER(path), required_outer))
688 matched_path = path;
689 }
690 return matched_path;
691}
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:343
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()

Path * get_cheapest_parallel_safe_total_inner ( List paths)

Definition at line 699 of file pathkeys.c.

700{
701 ListCell *l;
702
703 foreach(l, paths)
704 {
705 Path *innerpath = (Path *) lfirst(l);
706
707 if (innerpath->parallel_safe &&
708 bms_is_empty(PATH_REQ_OUTER(innerpath)))
709 return innerpath;
710 }
711
712 return NULL;
713}
bool parallel_safe
Definition: pathnodes.h:1690

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 {
630 Path *path = (Path *) lfirst(l);
631
632 /* If required, reject paths that are not parallel-safe */
633 if (require_parallel_safe && !path->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
644 if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
645 bms_is_subset(PATH_REQ_OUTER(path), required_outer))
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 */
611 jdomain = linitial_node(JoinDomain, root->join_domains);
612
613 /*
614 * Scan through the existing EquivalenceClasses for a match
615 */
616 foreach(lc1, root->eq_classes)
617 {
618 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
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 */
625 if (cur_ec->ec_has_volatile &&
626 (sortref == 0 || sortref != cur_ec->ec_sortref))
627 continue;
628
629 if (collation != cur_ec->ec_collation)
630 continue;
631 if (!equal(opfamilies, cur_ec->ec_opfamilies))
632 continue;
633
634 foreach(lc2, cur_ec->ec_members)
635 {
636 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
637
638 /*
639 * Ignore child members unless they match the request.
640 */
641 if (cur_em->em_is_child &&
642 !bms_equal(cur_em->em_relids, rel))
643 continue;
644
645 /*
646 * Match constants only within the same JoinDomain (see
647 * optimizer/README).
648 */
649 if (cur_em->em_is_const && cur_em->em_jdomain != jdomain)
650 continue;
651
652 if (opcintype == cur_em->em_datatype &&
653 equal(expr, cur_em->em_expr))
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 */
667 oldcontext = MemoryContextSwitchTo(root->planner_cxt);
668
669 newec = makeNode(EquivalenceClass);
670 newec->ec_opfamilies = list_copy(opfamilies);
671 newec->ec_collation = collation;
672 newec->ec_members = NIL;
673 newec->ec_sources = NIL;
674 newec->ec_derives = NIL;
675 newec->ec_relids = NULL;
676 newec->ec_has_const = false;
678 newec->ec_broken = false;
679 newec->ec_sortref = sortref;
680 newec->ec_min_security = UINT_MAX;
681 newec->ec_max_security = 0;
682 newec->ec_merged = NULL;
683
684 if (newec->ec_has_volatile && sortref == 0) /* should not happen */
685 elog(ERROR, "volatile EquivalenceClass has no sortref");
686
687 /*
688 * Get the precise set of relids appearing in the expression.
689 */
690 expr_relids = pull_varnos(root, (Node *) expr);
691
692 newem = add_eq_member(newec, copyObject(expr), expr_relids,
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 */
701 if (newec->ec_has_const)
702 {
703 if (newec->ec_has_volatile ||
704 expression_returns_set((Node *) expr) ||
705 contain_agg_clause((Node *) expr) ||
707 {
708 newec->ec_has_const = false;
709 newem->em_is_const = false;
710 }
711 }
712
713 root->eq_classes = lappend(root->eq_classes, newec);
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 */
719 if (root->ec_merging_done)
720 {
721 int ec_index = list_length(root->eq_classes) - 1;
722 int i = -1;
723
724 while ((i = bms_next_member(newec->ec_relids, i)) > 0)
725 {
726 RelOptInfo *rel = root->simple_rel_array[i];
727
728 /* ignore the RTE_GROUP RTE */
729 if (i == root->group_rtindex)
730 continue;
731
732 if (rel == NULL) /* must be an outer join */
733 {
734 Assert(bms_is_member(i, root->outer_join_rels));
735 continue;
736 }
737
739
741 ec_index);
742 }
743 }
744
745 MemoryContextSwitchTo(oldcontext);
746
747 return newec;
748}
bool contain_agg_clause(Node *clause)
Definition: clauses.c:177
bool contain_window_function(Node *clause)
Definition: clauses.c:214
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:537
bool expression_returns_set(Node *clause)
Definition: nodeFuncs.c:763
#define copyObject(obj)
Definition: nodes.h:224
#define makeNode(_type_)
Definition: nodes.h:155
#define linitial_node(type, l)
Definition: pg_list.h:181
Index ec_min_security
Definition: pathnodes.h:1429
Index ec_max_security
Definition: pathnodes.h:1430
Relids pull_varnos(PlannerInfo *root, Node *node)
Definition: var.c:114

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{
469 Query *parse = root->parse;
470 List *infos = NIL;
471 GroupByOrdering *info;
472
473 List *pathkeys = root->group_pathkeys;
474 List *clauses = root->processed_groupClause;
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 */
493 if (parse->groupingSets)
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 */
501 if (path->pathkeys &&
502 !pathkeys_contained_in(path->pathkeys, root->group_pathkeys))
503 {
504 int n;
505
506 n = group_keys_reorder_by_pathkeys(path->pathkeys, &pathkeys, &clauses,
507 root->num_groupby_pathkeys);
508
509 if (n > 0 &&
510 (enable_incremental_sort || n == root->num_groupby_pathkeys) &&
511 compare_pathkeys(pathkeys, root->group_pathkeys) != PATHKEYS_EQUAL)
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
532 info = lfirst_node(GroupByOrdering, lc);
533
534 Assert(list_length(info->clauses) == list_length(pinfo->clauses));
536 Assert(list_difference(info->clauses, pinfo->clauses) == NIL);
538
539 forboth(lc1, info->clauses, lc2, info->pathkeys)
540 {
542 PathKey *pk = lfirst_node(PathKey, lc2);
543
544 Assert(pk->pk_eclass->ec_sortref == sgc->tleSortGroupRef);
545 }
546 }
547 }
548#endif
549 return infos;
550}
List * list_difference(const List *list1, const List *list2)
Definition: list.c:1237
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
bool enable_group_by_reordering
Definition: pathkeys.c:32
static struct subre * parse(struct vars *v, int stopper, int type, struct state *init, struct state *final)
Definition: regcomp.c:717
Index tleSortGroupRef
Definition: parsenodes.h:1447

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;
3226 int i;
3227
3228 /* Examine only eclasses mentioning rel1 */
3229 matched_ecs = get_eclass_indexes_for_relids(root, rel1->relids);
3230
3231 i = -1;
3232 while ((i = bms_next_member(matched_ecs, i)) >= 0)
3233 {
3234 EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
3235 i);
3236
3237 /*
3238 * Won't generate joinclauses if single-member (this test covers the
3239 * volatile case too)
3240 */
3241 if (list_length(ec->ec_members) <= 1)
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 */
3248 if (!bms_is_subset(ec->ec_relids, rel1->relids))
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{
2317 if (rel->joininfo != NIL || rel->has_eclass_joins)
2318 return true; /* might be able to use pathkeys for merging */
2319 if (root->group_pathkeys != NIL)
2320 return true; /* might be able to use pathkeys for grouping */
2321 if (root->query_pathkeys != NIL)
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
1313 foreach(lc, root->placeholder_list)
1314 {
1315 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
1316
1317 if (!bms_is_subset(phinfo->ph_eval_at, inner_params))
1318 continue; /* ignore, could not be a nestloop param */
1319 if (!bms_overlap(phinfo->ph_eval_at, outer_relids))
1320 continue; /* ignore, not relevant to this join */
1321 if (bms_is_subset(phinfo->ph_eval_at, outer_relids))
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}
Relids ph_eval_at
Definition: pathnodes.h:3123

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 */
1085 if (bms_overlap(rel1->relids, rel2->direct_lateral_relids) ||
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 */
1096 foreach(l, root->placeholder_list)
1097 {
1098 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
1099
1100 if (bms_is_subset(rel1->relids, phinfo->ph_eval_at) &&
1101 bms_is_subset(rel2->relids, phinfo->ph_eval_at))
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 */
1113 foreach(l, root->join_info_list)
1114 {
1115 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
1116
1117 /* ignore full joins --- other mechanisms handle them */
1118 if (sjinfo->jointype == JOIN_FULL)
1119 continue;
1120
1121 /* Can we perform the SJ with these rels? */
1122 if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
1123 bms_is_subset(sjinfo->min_righthand, rel2->relids))
1124 {
1125 result = true;
1126 break;
1127 }
1128 if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
1129 bms_is_subset(sjinfo->min_righthand, rel1->relids))
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 */
1140 if (bms_overlap(sjinfo->min_righthand, rel1->relids) &&
1141 bms_overlap(sjinfo->min_righthand, rel2->relids))
1142 {
1143 result = true;
1144 break;
1145 }
1146
1147 /* Likewise for the LHS. */
1148 if (bms_overlap(sjinfo->min_lefthand, rel1->relids) &&
1149 bms_overlap(sjinfo->min_lefthand, rel2->relids))
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 {
1167 if (has_legal_joinclause(root, rel1) ||
1169 result = false;
1170 }
1171
1172 return result;
1173}
static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1244
Relids direct_lateral_relids
Definition: pathnodes.h:935

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;
3151 int i;
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 */
3163 matching_ecs = get_common_eclass_indexes(root, rel1->relids,
3164 rel2->relids);
3165
3166 i = -1;
3167 while ((i = bms_next_member(matching_ecs, i)) >= 0)
3168 {
3169 EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
3170 i);
3171
3172 /*
3173 * Sanity check that get_common_eclass_indexes gave only ECs
3174 * containing both rels.
3175 */
3176 Assert(bms_overlap(rel1->relids, ec->ec_relids));
3177 Assert(bms_overlap(rel2->relids, ec->ec_relids));
3178
3179 /*
3180 * Won't generate joinclauses if single-member (this test covers the
3181 * volatile case too)
3182 */
3183 if (list_length(ec->ec_members) <= 1)
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 */
4382 if (!IsBooleanOpfamily(index->opfamily[indexcol]))
4383 return false;
4384
4385 /* Check each restriction clause for the index's rel */
4386 foreach(lc, index->rel->baserestrictinfo)
4387 {
4388 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
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 */
4399 if (match_boolean_index_clause(root, rinfo, indexcol, index))
4400 return true;
4401 }
4402
4403 return false;
4404}
static bool IsBooleanOpfamily(Oid opfamily)
Definition: indxpath.c:2736
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;
678 sjinfo->jointype = JOIN_INNER;
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 */
685 sjinfo->lhs_strict = false;
686 sjinfo->semi_can_btree = false;
687 sjinfo->semi_can_hash = false;
688 sjinfo->semi_operators = NIL;
689 sjinfo->semi_rhs_exprs = NIL;
690}
Relids commute_above_r
Definition: pathnodes.h:2936
Relids syn_lefthand
Definition: pathnodes.h:2931
List * semi_rhs_exprs
Definition: pathnodes.h:2944
Relids syn_righthand
Definition: pathnodes.h:2932
Relids commute_below_r
Definition: pathnodes.h:2938
List * semi_operators
Definition: pathnodes.h:2943

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{
1464 Expr *clause = restrictinfo->clause;
1465 Oid lefttype,
1466 righttype;
1467
1468 /* Should be a mergeclause ... */
1469 Assert(restrictinfo->mergeopfamilies != NIL);
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 */
1475 op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1476
1477 /* Find or create a matching EquivalenceClass for each side */
1478 restrictinfo->left_ec =
1480 (Expr *) get_leftop(clause),
1481 restrictinfo->mergeopfamilies,
1482 lefttype,
1483 ((OpExpr *) clause)->inputcollid,
1484 0,
1485 NULL,
1486 true);
1487 restrictinfo->right_ec =
1489 (Expr *) get_rightop(clause),
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
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:95
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:83

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 {
3336 RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
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 {
3359 IndexClause *iclause = lfirst_node(IndexClause, lc);
3360 RestrictInfo *otherrinfo = iclause->rinfo;
3361
3362 /* If indexclause is lossy, it won't enforce the condition exactly */
3363 if (iclause->lossy)
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}
struct RestrictInfo * rinfo
Definition: pathnodes.h:1794

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{
75 List **joinrels = root->join_rel_level;
76 ListCell *r;
77 int k;
78
79 Assert(joinrels[level] == NIL);
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 {
93 RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
94
95 if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
96 has_join_restriction(root, old_rel))
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
118 make_rels_by_clause_joins(root, old_rel, joinrels[1], first_rel);
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 {
161 RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
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 */
170 if (old_rel->joininfo == NIL && !old_rel->has_eclass_joins &&
171 !has_join_restriction(root, old_rel))
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 {
181 RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
182
183 if (!bms_overlap(old_rel->relids, new_rel->relids))
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 */
190 if (have_relevant_joinclause(root, old_rel, new_rel) ||
191 have_join_order_restriction(root, old_rel, new_rel))
192 {
193 (void) make_join_rel(root, old_rel, new_rel);
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 */
219 if (joinrels[level] == NIL)
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 {
227 RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
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 */
252 if (joinrels[level] == NIL &&
253 root->join_info_list == NIL &&
254 !root->hasLateralRTEs)
255 elog(ERROR, "failed to build any %d-way joins", level);
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
#define foreach_current_index(var_or_cell)
Definition: pg_list.h:403

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 */
65 if (!root->ec_merging_done)
66 elog(ERROR, "too soon to build canonical pathkeys");
67
68 /* The passed eclass might be non-canonical, so chase up to the top */
69 while (eclass->ec_merged)
70 eclass = eclass->ec_merged;
71
72 foreach(lc, root->canon_pathkeys)
73 {
74 pk = (PathKey *) lfirst(lc);
75 if (eclass == pk->pk_eclass &&
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 */
86 oldcontext = MemoryContextSwitchTo(root->planner_cxt);
87
88 pk = makeNode(PathKey);
89 pk->pk_eclass = eclass;
90 pk->pk_opfamily = opfamily;
91 pk->pk_strategy = strategy;
92 pk->pk_nulls_first = nulls_first;
93
94 root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
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{
1858 List *pathkeys = NIL;
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 {
1870 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
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)
1893 elog(ERROR, "too few pathkeys for mergeclauses");
1894 opathkey = (PathKey *) lfirst(lop);
1895 lop = lnext(outer_pathkeys, lop);
1896 lastoeclass = opathkey->pk_eclass;
1897 if (oeclass != lastoeclass)
1898 elog(ERROR, "outer pathkeys do not match mergeclause");
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
1909 pathkey = make_canonical_pathkey(root,
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 */
1924 if (!pathkey_is_redundant(pathkey, pathkeys))
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;
710 List *pushed_down_joins = NIL;
711 SpecialJoinInfo sjinfo_data;
712 RelOptInfo *joinrel;
713 List *restrictlist;
714
715 /* We should never try to join two overlapping sets of rels. */
716 Assert(!bms_overlap(rel1->relids, rel2->relids));
717
718 /* Construct Relids set that identifies the joinrel (without OJ as yet). */
719 joinrelids = bms_union(rel1->relids, rel2->relids);
720
721 /* Check validity and determine join type. */
722 if (!join_is_legal(root, rel1, rel2, joinrelids,
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 */
734 joinrelids = add_outer_joins_to_relids(root, joinrelids, sjinfo,
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;
754 init_dummy_sjinfo(sjinfo, rel1->relids, rel2->relids);
755 }
756
757 /*
758 * Find or build the join RelOptInfo, and compute the restrictlist that
759 * goes with this particular joining.
760 */
761 joinrel = build_join_rel(root, joinrelids, rel1, rel2,
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 */
769 if (is_dummy_rel(joinrel))
770 {
771 bms_free(joinrelids);
772 return joinrel;
773 }
774
775 /* Add paths to the join relation. */
776 populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo,
777 restrictlist);
778
779 bms_free(joinrelids);
780
781 return joinrel;
782}
void bms_free(Bitmapset *a)
Definition: bitmapset.c:239
static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, SpecialJoinInfo *sjinfo, List *restrictlist)
Definition: joinrels.c:894
bool is_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1336
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;
200 for (rti = 1; rti < root->simple_rel_array_size; rti++)
201 {
202 RelOptInfo *brel = root->simple_rel_array[rti];
203
204 /* there may be empty slots corresponding to non-baserel RTEs */
205 if (brel == NULL)
206 continue;
207
208 Assert(brel->relid == rti); /* sanity check on array */
209
210 if (IS_DUMMY_REL(brel))
211 continue;
212
213 if (IS_SIMPLE_REL(brel))
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 */
226 rel = make_rel_from_joinlist(root, joinlist);
227
228 /*
229 * The result should join all and only the query's base + outer-join rels.
230 */
231 Assert(bms_equal(rel->relids, root->all_query_rels));
232
233 return rel;
234}
static void set_base_rel_sizes(PlannerInfo *root)
Definition: allpaths.c:290
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
unsigned int Index
Definition: c.h:585
BlockNumber pages
Definition: pathnodes.h:972

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{
1388 List *pathkeys = NIL;
1389 ListCell *l;
1390
1391 *sortable = true;
1392 foreach(l, *sortclauses)
1393 {
1394 SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
1395 Expr *sortkey;
1396 PathKey *pathkey;
1397
1398 sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
1399 if (!OidIsValid(sortcl->sortop))
1400 {
1401 *sortable = false;
1402 continue;
1403 }
1404 if (remove_group_rtindex)
1405 {
1406 Assert(root->group_rtindex > 0);
1407 sortkey = (Expr *)
1408 remove_nulling_relids((Node *) sortkey,
1409 bms_make_singleton(root->group_rtindex),
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 */
1430 if (!pathkey_is_redundant(pathkey, pathkeys))
1431 pathkeys = lappend(pathkeys, pathkey);
1432 else if (remove_redundant)
1433 *sortclauses = foreach_delete_current(*sortclauses, l);
1434 }
1435 return pathkeys;
1436}
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:216
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
#define foreach_delete_current(lst, var_or_cell)
Definition: pg_list.h:391
Node * remove_nulling_relids(Node *node, const Bitmapset *removable_relids, const Bitmapset *except_relids)
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? */
1390 if (is_dummy_rel(rel))
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 */
1400 rel->pathlist = NIL;
1401 rel->partial_pathlist = NIL;
1402
1403 /* Set up the dummy path */
1404 add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NIL,
1405 NIL, rel->lateral_relids,
1406 0, false, -1));
1407
1408 /* Set or update cheapest_total_path and related fields */
1409 set_cheapest(rel);
1410
1411 MemoryContextSwitchTo(oldcontext);
1412}
MemoryContext GetMemoryChunkContext(void *pointer)
Definition: mcxt.c:707
Cardinality rows
Definition: pathnodes.h:901

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{
2564 Index var1varno = fkinfo->con_relid;
2565 AttrNumber var1attno = fkinfo->conkey[colno];
2566 Index var2varno = fkinfo->ref_relid;
2567 AttrNumber var2attno = fkinfo->confkey[colno];
2568 Oid eqop = fkinfo->conpfeqop[colno];
2569 RelOptInfo *rel1 = root->simple_rel_array[var1varno];
2570 RelOptInfo *rel2 = root->simple_rel_array[var2varno];
2571 List *opfamilies = NIL; /* compute only if needed */
2572 Bitmapset *matching_ecs;
2573 int i;
2574
2575 /* Consider only eclasses mentioning both relations */
2576 Assert(root->ec_merging_done);
2577 Assert(IS_SIMPLE_REL(rel1));
2578 Assert(IS_SIMPLE_REL(rel2));
2579 matching_ecs = bms_intersect(rel1->eclass_indexes,
2580 rel2->eclass_indexes);
2581
2582 i = -1;
2583 while ((i = bms_next_member(matching_ecs, i)) >= 0)
2584 {
2585 EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
2586 i);
2587 EquivalenceMember *item1_em = NULL;
2588 EquivalenceMember *item2_em = NULL;
2589 ListCell *lc2;
2590
2591 /* Never match to a volatile EC */
2592 if (ec->ec_has_volatile)
2593 continue;
2594 /* It's okay to consider "broken" ECs here, see exprs_known_equal */
2595
2596 foreach(lc2, ec->ec_members)
2597 {
2599 Var *var;
2600
2601 if (em->em_is_child)
2602 continue; /* ignore children here */
2603
2604 /* EM must be a Var, possibly with RelabelType */
2605 var = (Var *) em->em_expr;
2606 while (var && IsA(var, RelabelType))
2607 var = (Var *) ((RelabelType *) var)->arg;
2608 if (!(var && IsA(var, Var)))
2609 continue;
2610
2611 /* Match? */
2612 if (var->varno == var1varno && var->varattno == var1attno)
2613 item1_em = em;
2614 else if (var->varno == var2varno && var->varattno == var2attno)
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 */
2625 if (opfamilies == NIL) /* compute if we didn't already */
2626 opfamilies = get_mergejoin_opfamilies(eqop);
2627 if (equal(opfamilies, ec->ec_opfamilies))
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}
int16 AttrNumber
Definition: attnum.h:21
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:292
List * get_mergejoin_opfamilies(Oid opno)
Definition: lsyscache.c:367
while(p+4<=pend)
struct EquivalenceClass * eclass[INDEX_MAX_KEYS]
Definition: pathnodes.h:1285
struct EquivalenceMember * fk_eclass_member[INDEX_MAX_KEYS]
Definition: pathnodes.h:1287
AttrNumber varattno
Definition: primnodes.h:274
int varno
Definition: primnodes.h:269

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 */
4438 if (operand && IsA(operand, RelabelType))
4439 operand = (Node *) ((RelabelType *) operand)->arg;
4440
4441 indkey = index->indexkeys[indexcol];
4442 if (indkey != 0)
4443 {
4444 /*
4445 * Simple index column; operand must be a matching Var.
4446 */
4447 if (operand && IsA(operand, Var) &&
4448 index->rel->relid == ((Var *) operand)->varno &&
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;
4461 int i;
4462 Node *indexkey;
4463
4464 indexpr_item = list_head(index->indexprs);
4465 for (i = 0; i < indexcol; i++)
4466 {
4467 if (index->indexkeys[i] == 0)
4468 {
4469 if (indexpr_item == NULL)
4470 elog(ERROR, "wrong number of index expressions");
4471 indexpr_item = lnext(index->indexprs, indexpr_item);
4472 }
4473 }
4474 if (indexpr_item == NULL)
4475 elog(ERROR, "wrong number of index expressions");
4476 indexkey = (Node *) lfirst(indexpr_item);
4477
4478 /*
4479 * Does it match the operand? Again, strip any relabeling.
4480 */
4481 if (indexkey && IsA(indexkey, RelabelType))
4482 indexkey = (Node *) ((RelabelType *) indexkey)->arg;
4483
4484 if (equal(indexkey, operand))
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()

◆ pathkeys_count_contained_in()

bool pathkeys_count_contained_in ( List keys1,
List keys2,
int *  n_common 
)

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 }
573 else if (keys1 == NIL)
574 {
575 *n_common = 0;
576 return true;
577 }
578 else if (keys2 == NIL)
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 {
590 PathKey *pathkey1 = (PathKey *) lfirst(key1);
591 PathKey *pathkey2 = (PathKey *) lfirst(key2);
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;
122 Expr *clause = restrictinfo->clause;
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;
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 */
144 if (restrictinfo->security_level > 0 && !restrictinfo->leakproof)
145 return false;
146
147 /* Extract info from given clause */
148 Assert(is_opclause(clause));
149 opno = ((OpExpr *) clause)->opno;
150 collation = ((OpExpr *) clause)->inputcollid;
151 item1 = (Expr *) get_leftop(clause);
152 item2 = (Expr *) get_rightop(clause);
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,
161 exprType((Node *) item1),
162 collation);
163 item2 = canonicalize_ec_expression(item2,
164 exprType((Node *) 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 */
173 if (equal(item1, item2))
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 */
185 set_opfuncid((OpExpr *) clause);
186 if (func_strict(((OpExpr *) clause)->opfuncid))
187 {
188 NullTest *ntest = makeNode(NullTest);
189
190 ntest->arg = item1;
191 ntest->nulltesttype = IS_NOT_NULL;
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;
243 foreach(lc1, root->eq_classes)
244 {
245 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
246 ListCell *lc2;
247
248 /* Never match to a volatile EC */
249 if (cur_ec->ec_has_volatile)
250 continue;
251
252 /*
253 * The collation has to match; check this first since it's cheaper
254 * than the opfamily comparison.
255 */
256 if (collation != cur_ec->ec_collation)
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 */
264 if (!equal(opfamilies, cur_ec->ec_opfamilies))
265 continue;
266
267 foreach(lc2, cur_ec->ec_members)
268 {
269 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
270
271 Assert(!cur_em->em_is_child); /* no children yet */
272
273 /*
274 * Match constants only within the same JoinDomain (see
275 * optimizer/README).
276 */
277 if (cur_em->em_is_const && cur_em->em_jdomain != jdomain)
278 continue;
279
280 if (!ec1 &&
281 item1_type == cur_em->em_datatype &&
282 equal(item1, cur_em->em_expr))
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 &&
292 equal(item2, cur_em->em_expr))
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 {
313 ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
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 */
333 if (root->ec_merging_done)
334 elog(ERROR, "too late to merge equivalence classes");
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 */
343 ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
344 ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
345 ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
346 ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
347 ec1->ec_has_const |= ec2->ec_has_const;
348 /* can't need to set has_volatile */
350 ec2->ec_min_security);
352 ec2->ec_max_security);
353 ec2->ec_merged = ec1;
354 root->eq_classes = list_delete_nth_cell(root->eq_classes, ec2_idx);
355 /* just to avoid debugging confusion w/ dangling pointers: */
356 ec2->ec_members = NIL;
357 ec2->ec_sources = NIL;
358 ec2->ec_derives = NIL;
359 ec2->ec_relids = NULL;
360 ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
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);
377 ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
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);
394 ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
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;
413 ec->ec_members = NIL;
414 ec->ec_sources = list_make1(restrictinfo);
415 ec->ec_derives = NIL;
416 ec->ec_relids = NULL;
417 ec->ec_has_const = false;
418 ec->ec_has_volatile = false;
419 ec->ec_broken = false;
420 ec->ec_sortref = 0;
421 ec->ec_min_security = restrictinfo->security_level;
422 ec->ec_max_security = restrictinfo->security_level;
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
429 root->eq_classes = lappend(root->eq_classes, ec);
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}
List * list_delete_nth_cell(List *list, int n)
Definition: list.c:767
bool func_strict(Oid funcid)
Definition: lsyscache.c:1800
void set_opfuncid(OpExpr *opexpr)
Definition: nodeFuncs.c:1872
static bool is_opclause(const void *clause)
Definition: nodeFuncs.h:76
@ IS_NOT_NULL
Definition: primnodes.h:1957
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
NullTestType nulltesttype
Definition: primnodes.h:1964
ParseLoc location
Definition: primnodes.h:1967
Expr * arg
Definition: primnodes.h:1963
bool is_pushed_down
Definition: pathnodes.h:2602
Index security_level
Definition: pathnodes.h:2621
Relids outer_relids
Definition: pathnodes.h:2636
Relids incompatible_relids
Definition: pathnodes.h:2633
bool has_clone
Definition: pathnodes.h:2611

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
2436 foreach(lc, root->eq_classes)
2437 {
2439
2440 /* Need do anything only for a multi-member, no-const EC. */
2441 if (list_length(ec->ec_members) > 1 && !ec->ec_has_const)
2442 {
2443 ListCell *lc2;
2444
2445 foreach(lc2, ec->ec_members)
2446 {
2447 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
2448 List *vars = pull_var_clause((Node *) cur_em->em_expr,
2452
2454 list_free(vars);
2455 }
2456 }
2457 }
2458}
void add_vars_to_attr_needed(PlannerInfo *root, List *vars, Relids where_needed)
Definition: initsplan.c:353
#define PVC_RECURSE_AGGREGATES
Definition: optimizer.h:188
#define PVC_RECURSE_WINDOWFUNCS
Definition: optimizer.h:190
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 */
2013 foreach(cell, root->left_join_clauses)
2014 {
2015 OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2016
2017 if (reconsider_outer_join_clause(root, ojcinfo, true))
2018 {
2019 RestrictInfo *rinfo = ojcinfo->rinfo;
2020
2021 found = true;
2022 /* remove it from the list */
2023 root->left_join_clauses =
2024 foreach_delete_current(root->left_join_clauses, cell);
2025 /* throw back a dummy replacement clause (see notes above) */
2026 rinfo = make_restrictinfo(root,
2027 (Expr *) makeBoolConst(true, false),
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 */
2041 foreach(cell, root->right_join_clauses)
2042 {
2043 OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2044
2045 if (reconsider_outer_join_clause(root, ojcinfo, false))
2046 {
2047 RestrictInfo *rinfo = ojcinfo->rinfo;
2048
2049 found = true;
2050 /* remove it from the list */
2051 root->right_join_clauses =
2052 foreach_delete_current(root->right_join_clauses, cell);
2053 /* throw back a dummy replacement clause (see notes above) */
2054 rinfo = make_restrictinfo(root,
2055 (Expr *) makeBoolConst(true, false),
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 */
2069 foreach(cell, root->full_join_clauses)
2070 {
2071 OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2072
2073 if (reconsider_full_join_clause(root, ojcinfo))
2074 {
2075 RestrictInfo *rinfo = ojcinfo->rinfo;
2076
2077 found = true;
2078 /* remove it from the list */
2079 root->full_join_clauses =
2080 foreach_delete_current(root->full_join_clauses, cell);
2081 /* throw back a dummy replacement clause (see notes above) */
2082 rinfo = make_restrictinfo(root,
2083 (Expr *) makeBoolConst(true, false),
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 */
2098 foreach(cell, root->left_join_clauses)
2099 {
2100 OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2101
2103 }
2104 foreach(cell, root->right_join_clauses)
2105 {
2106 OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2107
2109 }
2110 foreach(cell, root->full_join_clauses)
2111 {
2112 OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
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
Node * makeBoolConst(bool value, bool isnull)
Definition: makefuncs.c:408
RestrictInfo * rinfo
Definition: pathnodes.h:2958
Relids required_relids
Definition: pathnodes.h:2630

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{
925 PathTarget *target = rel->reltarget;
927 ListCell *lc;
928
929 /*
930 * Reject volatile ECs immediately; such sorts must always be postponed.
931 */
932 if (ec->ec_has_volatile)
933 return false;
934
935 /*
936 * Try to find an EM directly matching some reltarget member.
937 */
938 foreach(lc, target->exprs)
939 {
940 Expr *targetexpr = (Expr *) lfirst(lc);
941
942 em = find_ec_member_matching_expr(ec, targetexpr, rel->relids);
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 */
969 em = find_computable_ec_member(root, ec, target->exprs, rel->relids,
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
List * exprs
Definition: pathnodes.h:1568

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
4184 Assert(list_length(exprlist) == list_length(oprlist));
4185
4186 /* Short-circuit if no indexes... */
4187 if (rel->indexlist == NIL)
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 */
4194 foreach(ic, rel->baserestrictinfo)
4195 {
4196 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(ic);
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 */
4203 if (restrictinfo->mergeopfamilies == NIL)
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 */
4210 if (bms_is_empty(restrictinfo->left_relids))
4211 {
4212 /* righthand side is inner */
4213 restrictinfo->outer_is_left = true;
4214 }
4215 else if (bms_is_empty(restrictinfo->right_relids))
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 */
4228 if (restrictlist == NIL && exprlist == NIL)
4229 return false;
4230
4231 /* Examine each index of the relation ... */
4232 foreach(ic, rel->indexlist)
4233 {
4235 int c;
4236 List *exprs = NIL;
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 */
4246 if (!ind->unique || !ind->immediate || ind->indpred != NIL)
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 */
4253 for (c = 0; c < ind->nkeycolumns; c++)
4254 {
4255 bool matched = false;
4256 ListCell *lc;
4257 ListCell *lc2;
4258
4259 foreach(lc, restrictlist)
4260 {
4261 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
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 */
4270 if (!list_member_oid(rinfo->mergeopfamilies, ind->opfamily[c]))
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)
4281 rexpr = get_rightop(rinfo->clause);
4282 else
4283 rexpr = get_leftop(rinfo->clause);
4284
4285 if (match_index_to_operand(rexpr, c, ind))
4286 {
4287 matched = true; /* column is unique */
4288
4289 if (bms_membership(rinfo->clause_relids) == BMS_SINGLETON)
4290 {
4291 MemoryContext oldMemCtx =
4292 MemoryContextSwitchTo(root->planner_cxt);
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 */
4299 Assert(bms_is_empty(rinfo->left_relids) ||
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 {
4315 Node *expr = (Node *) lfirst(lc);
4316 Oid opr = lfirst_oid(lc2);
4317
4318 /* See if the expression matches the index key */
4319 if (!match_index_to_operand(expr, c, ind))
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 */
4329 if (!op_in_opfamily(opr, ind->opfamily[c]))
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? */
4347 if (c == ind->nkeycolumns)
4348 {
4349 if (extra_clauses)
4350 *extra_clauses = exprs;
4351 return true;
4352 }
4353 }
4354
4355 return false;
4356}
@ BMS_SINGLETON
Definition: bitmapset.h:72
bool match_index_to_operand(Node *operand, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:4426
bool op_in_opfamily(Oid opno, Oid opfamily)
Definition: lsyscache.c:67
#define lfirst_oid(lc)
Definition: pg_list.h:174
char * c

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{
4166 return relation_has_unique_index_ext(root, rel, restrictlist,
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{
1662 List *pathkeys = NIL;
1663 int nClauses = list_length(mergeclauses);
1664 EquivalenceClass **ecs;
1665 int *scores;
1666 int necs;
1667 ListCell *lc;
1668 int j;
1669
1670 /* Might have no mergeclauses */
1671 if (nClauses == 0)
1672 return NIL;
1673
1674 /*
1675 * Make arrays of the ECs used by the mergeclauses (dropping any
1676 * duplicates) and their "popularity" scores.
1677 */
1678 ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
1679 scores = (int *) palloc(nClauses * sizeof(int));
1680 necs = 0;
1681
1682 foreach(lc, mergeclauses)
1683 {
1684 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
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 */
1698 for (j = 0; j < necs; j++)
1699 {
1700 if (ecs[j] == oeclass)
1701 break;
1702 }
1703 if (j < necs)
1704 continue;
1705
1706 /* compute score */
1707 score = 0;
1708 foreach(lc2, oeclass->ec_members)
1709 {
1711
1712 /* Potential future join partner? */
1713 if (!em->em_is_const && !em->em_is_child &&
1714 !bms_overlap(em->em_relids, joinrel->relids))
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 */
1731 if (root->query_pathkeys)
1732 {
1733 int matches = 0;
1734
1735 foreach(lc, root->query_pathkeys)
1736 {
1737 PathKey *query_pathkey = (PathKey *) lfirst(lc);
1738 EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1739
1740 for (j = 0; j < necs; j++)
1741 {
1742 if (ecs[j] == query_ec)
1743 break; /* found match */
1744 }
1745 if (j >= necs)
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 */
1754 pathkeys = list_copy(root->query_pathkeys);
1755 /* mark their ECs as already-emitted */
1756 foreach(lc, root->query_pathkeys)
1757 {
1758 PathKey *query_pathkey = (PathKey *) lfirst(lc);
1759 EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1760
1761 for (j = 0; j < necs; j++)
1762 {
1763 if (ecs[j] == query_ec)
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 {
1780 pathkeys = list_copy_head(root->query_pathkeys, matches);
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];
1804 for (j = 1; j < necs; j++)
1805 {
1806 if (scores[j] > best_score)
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;
1816 pathkey = make_canonical_pathkey(root,
1817 ec,
1820 false);
1821 /* can't be redundant because no duplicate ECs */
1822 Assert(!pathkey_is_redundant(pathkey, pathkeys));
1823 pathkeys = lappend(pathkeys, pathkey);
1824 }
1825
1826 pfree(ecs);
1827 pfree(scores);
1828
1829 return pathkeys;
1830}
List * list_copy_head(const List *oldlist, int len)
Definition: list.c:1593
void pfree(void *pointer)
Definition: mcxt.c:1524
void * palloc(Size size)
Definition: mcxt.c:1317
#define linitial_oid(l)
Definition: pg_list.h:180
#define BTLessStrategyNumber
Definition: stratnum.h:29

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 */
3452 Assert(root->join_rel_level == NULL);
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 */
3465 root->join_rel_level = (List **) palloc0((levels_needed + 1) * sizeof(List *));
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 */
3490 foreach(lc, root->join_rel_level[lev])
3491 {
3492 rel = (RelOptInfo *) lfirst(lc);
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 */
3503 if (!bms_equal(rel->relids, root->all_query_rels))
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 */
3518 if (root->join_rel_level[levels_needed] == NIL)
3519 elog(ERROR, "failed to build any %d-way joins", levels_needed);
3520 Assert(list_length(root->join_rel_level[levels_needed]) == 1);
3521
3522 rel = (RelOptInfo *) linitial(root->join_rel_level[levels_needed]);
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
void * palloc0(Size size)
Definition: mcxt.c:1347

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{
1961 List *new_mergeclauses = NIL;
1962 PathKey *pathkey;
1963 EquivalenceClass *pathkey_ec;
1964 bool matched_pathkey;
1965 ListCell *lip;
1966 ListCell *i;
1967
1968 /* No pathkeys => no mergeclauses (though we don't expect this case) */
1969 if (pathkeys == NIL)
1970 return NIL;
1971 /* Initialize to consider first pathkey */
1972 lip = list_head(pathkeys);
1973 pathkey = (PathKey *) lfirst(lip);
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 */
1979 foreach(i, mergeclauses)
1980 {
1981 RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
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;
2000 pathkey = (PathKey *) lfirst(lip);
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
2273 nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
2274 nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
2275 if (nuseful2 > nuseful)
2276 nuseful = nuseful2;
2277 nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
2278 if (nuseful2 > nuseful)
2279 nuseful = nuseful2;
2280 nuseful2 = pathkeys_useful_for_distinct(root, pathkeys);
2281 if (nuseful2 > nuseful)
2282 nuseful = nuseful2;
2283 nuseful2 = pathkeys_useful_for_setop(root, pathkeys);
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)
2292 return NIL;
2293 else if (nuseful == list_length(pathkeys))
2294 return pathkeys;
2295 else
2296 return list_copy_head(pathkeys, nuseful);
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 ... */
1512 Assert(restrictinfo->mergeopfamilies != NIL);
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}

References Assert(), and NIL.

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

PGDLLIMPORT bool enable_geqo
extern

Definition at line 79 of file allpaths.c.

Referenced by make_rel_from_joinlist().

◆ enable_group_by_reordering

PGDLLIMPORT bool enable_group_by_reordering
extern

Definition at line 32 of file pathkeys.c.

Referenced by get_useful_group_keys_orderings().

◆ geqo_threshold

PGDLLIMPORT int geqo_threshold
extern

Definition at line 80 of file allpaths.c.

Referenced by make_rel_from_joinlist().

◆ join_search_hook

PGDLLIMPORT join_search_hook_type join_search_hook
extern

Definition at line 88 of file allpaths.c.

Referenced by make_rel_from_joinlist().

◆ min_parallel_index_scan_size

PGDLLIMPORT int 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

PGDLLIMPORT int min_parallel_table_scan_size
extern

Definition at line 81 of file allpaths.c.

Referenced by compute_parallel_worker().

◆ set_join_pathlist_hook

PGDLLIMPORT set_join_pathlist_hook_type set_join_pathlist_hook
extern

Definition at line 33 of file joinpath.c.

Referenced by add_paths_to_joinrel().

◆ set_rel_pathlist_hook

PGDLLIMPORT set_rel_pathlist_hook_type set_rel_pathlist_hook
extern

Definition at line 85 of file allpaths.c.

Referenced by set_rel_pathlist().