PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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 (PlannerInfo *root, 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)
 
void setup_eclass_member_iterator (EquivalenceMemberIterator *it, EquivalenceClass *ec, Relids child_relids)
 
EquivalenceMembereclass_member_iterator_next (EquivalenceMemberIterator *it)
 
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)
 
void ec_clear_derived_clauses (EquivalenceClass *ec)
 
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, CompareType cmptype, 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 211 of file paths.h.

212{
213 PATHKEYS_EQUAL, /* pathkeys are identical */
214 PATHKEYS_BETTER1, /* pathkey 1 is a superset of pathkey 2 */
215 PATHKEYS_BETTER2, /* vice versa */
216 PATHKEYS_DIFFERENT, /* neither pathkey includes the other */
PathKeysComparison
Definition: paths.h:212
@ PATHKEYS_BETTER2
Definition: paths.h:215
@ PATHKEYS_BETTER1
Definition: paths.h:214
@ PATHKEYS_DIFFERENT
Definition: paths.h:216
@ PATHKEYS_EQUAL
Definition: paths.h:213

Function Documentation

◆ add_child_join_rel_equivalences()

void add_child_join_rel_equivalences ( PlannerInfo root,
int  nappinfos,
AppendRelInfo **  appinfos,
RelOptInfo parent_joinrel,
RelOptInfo child_joinrel 
)

Definition at line 2941 of file equivclass.c.

2945{
2946 Relids top_parent_relids = child_joinrel->top_parent_relids;
2947 Relids child_relids = child_joinrel->relids;
2948 Bitmapset *matching_ecs;
2949 MemoryContext oldcontext;
2950 int i;
2951
2952 Assert(IS_JOIN_REL(child_joinrel) && IS_JOIN_REL(parent_joinrel));
2953
2954 /* We need consider only ECs that mention the parent joinrel */
2955 matching_ecs = get_eclass_indexes_for_relids(root, top_parent_relids);
2956
2957 /*
2958 * If we're being called during GEQO join planning, we still have to
2959 * create any new EC members in the main planner context, to avoid having
2960 * a corrupt EC data structure after the GEQO context is reset. This is
2961 * problematic since we'll leak memory across repeated GEQO cycles. For
2962 * now, though, bloat is better than crash. If it becomes a real issue
2963 * we'll have to do something to avoid generating duplicate EC members.
2964 */
2965 oldcontext = MemoryContextSwitchTo(root->planner_cxt);
2966
2967 i = -1;
2968 while ((i = bms_next_member(matching_ecs, i)) >= 0)
2969 {
2970 EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2971
2972 /*
2973 * If this EC contains a volatile expression, then generating child
2974 * EMs would be downright dangerous, so skip it. We rely on a
2975 * volatile EC having only one EM.
2976 */
2977 if (cur_ec->ec_has_volatile)
2978 continue;
2979
2980 /* Sanity check on get_eclass_indexes_for_relids result */
2981 Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids));
2982
2983 foreach_node(EquivalenceMember, cur_em, cur_ec->ec_members)
2984 {
2985 if (cur_em->em_is_const)
2986 continue; /* ignore consts here */
2987
2988 /* Child members should not exist in ec_members */
2989 Assert(!cur_em->em_is_child);
2990
2991 /*
2992 * We may ignore expressions that reference a single baserel,
2993 * because add_child_rel_equivalences should have handled them.
2994 */
2995 if (bms_membership(cur_em->em_relids) != BMS_MULTIPLE)
2996 continue;
2997
2998 /* Does this member reference child's topmost parent rel? */
2999 if (bms_overlap(cur_em->em_relids, top_parent_relids))
3000 {
3001 /* Yes, generate transformed child version */
3002 Expr *child_expr;
3003 Relids new_relids;
3004
3005 if (parent_joinrel->reloptkind == RELOPT_JOINREL)
3006 {
3007 /* Simple single-level transformation */
3008 child_expr = (Expr *)
3010 (Node *) cur_em->em_expr,
3011 nappinfos, appinfos);
3012 }
3013 else
3014 {
3015 /* Must do multi-level transformation */
3016 Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
3017 child_expr = (Expr *)
3019 (Node *) cur_em->em_expr,
3020 child_joinrel,
3021 child_joinrel->top_parent);
3022 }
3023
3024 /*
3025 * Transform em_relids to match. Note we do *not* do
3026 * pull_varnos(child_expr) here, as for example the
3027 * transformation might have substituted a constant, but we
3028 * don't want the child member to be marked as constant.
3029 */
3030 new_relids = bms_difference(cur_em->em_relids,
3031 top_parent_relids);
3032 new_relids = bms_add_members(new_relids, child_relids);
3033
3034 /*
3035 * Add new child member to the EquivalenceClass. Because this
3036 * is a RELOPT_OTHER_JOINREL which has multiple component
3037 * relids, there is no ideal place to store these members in
3038 * the class. Ordinarily, child members are stored in the
3039 * ec_childmembers[] array element corresponding to their
3040 * relid, however, here we have multiple component relids, so
3041 * there's no single ec_childmembers[] array element to store
3042 * this member. So that we still correctly find this member
3043 * in loops iterating over an EquivalenceMemberIterator, we
3044 * opt to store the member in the ec_childmembers array in
3045 * only the first component relid slot of the array. This
3046 * allows the member to be found, providing callers of
3047 * setup_eclass_member_iterator() specify all the component
3048 * relids for the RELOPT_OTHER_JOINREL, which they do. If we
3049 * opted to store the member in each ec_childmembers[] element
3050 * for all the component relids, then that would just result
3051 * in eclass_member_iterator_next() finding the member
3052 * multiple times, which is a waste of effort.
3053 */
3055 cur_ec,
3056 -1,
3057 child_expr,
3058 new_relids,
3059 cur_em->em_jdomain,
3060 cur_em,
3061 cur_em->em_datatype,
3062 bms_next_member(child_joinrel->relids, -1));
3063 }
3064 }
3065 }
3066
3067 MemoryContextSwitchTo(oldcontext);
3068}
Node * adjust_appendrel_attrs(PlannerInfo *root, Node *node, int nappinfos, AppendRelInfo **appinfos)
Definition: appendinfo.c:200
Node * adjust_appendrel_attrs_multilevel(PlannerInfo *root, Node *node, RelOptInfo *childrel, RelOptInfo *parentrel)
Definition: appendinfo.c: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_child_eq_member(PlannerInfo *root, EquivalenceClass *ec, int ec_index, Expr *expr, Relids relids, JoinDomain *jdomain, EquivalenceMember *parent_em, Oid datatype, Index child_relid)
Definition: equivclass.c:661
static Bitmapset * get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
Definition: equivclass.c:3613
Assert(PointerIsAligned(start, uint64))
int i
Definition: isn.c:77
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
#define IS_JOIN_REL(rel)
Definition: pathnodes.h:871
@ RELOPT_JOINREL
Definition: pathnodes.h:855
@ RELOPT_OTHER_JOINREL
Definition: pathnodes.h:857
static void * list_nth(const List *list, int n)
Definition: pg_list.h:299
#define foreach_node(type, var, lst)
Definition: pg_list.h:496
tree ctl root
Definition: radixtree.h:1857
Definition: nodes.h:135
Relids relids
Definition: pathnodes.h:898
Relids top_parent_relids
Definition: pathnodes.h:1036
RelOptKind reloptkind
Definition: pathnodes.h:892

References add_child_eq_member(), adjust_appendrel_attrs(), adjust_appendrel_attrs_multilevel(), Assert(), bms_add_members(), bms_difference(), bms_membership(), BMS_MULTIPLE, bms_next_member(), bms_overlap(), EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, foreach_node, get_eclass_indexes_for_relids(), i, IS_JOIN_REL, list_nth(), MemoryContextSwitchTo(), RelOptInfo::relids, RELOPT_JOINREL, RELOPT_OTHER_JOINREL, RelOptInfo::reloptkind, root, and RelOptInfo::top_parent_relids.

Referenced by build_child_join_rel().

◆ add_child_rel_equivalences()

void add_child_rel_equivalences ( PlannerInfo root,
AppendRelInfo appinfo,
RelOptInfo parent_rel,
RelOptInfo child_rel 
)

Definition at line 2833 of file equivclass.c.

2837{
2838 Relids top_parent_relids = child_rel->top_parent_relids;
2839 Relids child_relids = child_rel->relids;
2840 int i;
2841
2842 /*
2843 * EC merging should be complete already, so we can use the parent rel's
2844 * eclass_indexes to avoid searching all of root->eq_classes.
2845 */
2846 Assert(root->ec_merging_done);
2847 Assert(IS_SIMPLE_REL(parent_rel));
2848
2849 i = -1;
2850 while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0)
2851 {
2852 EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2853
2854 /*
2855 * If this EC contains a volatile expression, then generating child
2856 * EMs would be downright dangerous, so skip it. We rely on a
2857 * volatile EC having only one EM.
2858 */
2859 if (cur_ec->ec_has_volatile)
2860 continue;
2861
2862 /* Sanity check eclass_indexes only contain ECs for parent_rel */
2863 Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids));
2864
2865 foreach_node(EquivalenceMember, cur_em, cur_ec->ec_members)
2866 {
2867 if (cur_em->em_is_const)
2868 continue; /* ignore consts here */
2869
2870 /* Child members should not exist in ec_members */
2871 Assert(!cur_em->em_is_child);
2872
2873 /*
2874 * Consider only members that reference and can be computed at
2875 * child's topmost parent rel. In particular we want to exclude
2876 * parent-rel Vars that have nonempty varnullingrels. Translating
2877 * those might fail, if the transformed expression wouldn't be a
2878 * simple Var; and in any case it wouldn't produce a member that
2879 * has any use in creating plans for the child rel.
2880 */
2881 if (bms_is_subset(cur_em->em_relids, top_parent_relids) &&
2882 !bms_is_empty(cur_em->em_relids))
2883 {
2884 /* OK, generate transformed child version */
2885 Expr *child_expr;
2886 Relids new_relids;
2887
2888 if (parent_rel->reloptkind == RELOPT_BASEREL)
2889 {
2890 /* Simple single-level transformation */
2891 child_expr = (Expr *)
2893 (Node *) cur_em->em_expr,
2894 1, &appinfo);
2895 }
2896 else
2897 {
2898 /* Must do multi-level transformation */
2899 child_expr = (Expr *)
2901 (Node *) cur_em->em_expr,
2902 child_rel,
2903 child_rel->top_parent);
2904 }
2905
2906 /*
2907 * Transform em_relids to match. Note we do *not* do
2908 * pull_varnos(child_expr) here, as for example the
2909 * transformation might have substituted a constant, but we
2910 * don't want the child member to be marked as constant.
2911 */
2912 new_relids = bms_difference(cur_em->em_relids,
2913 top_parent_relids);
2914 new_relids = bms_add_members(new_relids, child_relids);
2915
2917 cur_ec,
2918 i,
2919 child_expr,
2920 new_relids,
2921 cur_em->em_jdomain,
2922 cur_em,
2923 cur_em->em_datatype,
2924 child_rel->relid);
2925 }
2926 }
2927 }
2928}
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:412
#define bms_is_empty(a)
Definition: bitmapset.h:118
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:866
@ RELOPT_BASEREL
Definition: pathnodes.h:854
Index relid
Definition: pathnodes.h:945
Bitmapset * eclass_indexes
Definition: pathnodes.h:979

References add_child_eq_member(), adjust_appendrel_attrs(), adjust_appendrel_attrs_multilevel(), Assert(), bms_add_members(), bms_difference(), bms_is_empty, bms_is_subset(), bms_next_member(), EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, RelOptInfo::eclass_indexes, foreach_node, i, IS_SIMPLE_REL, list_nth(), RelOptInfo::relid, RelOptInfo::relids, RELOPT_BASEREL, RelOptInfo::reloptkind, root, and RelOptInfo::top_parent_relids.

Referenced by set_append_rel_size().

◆ add_outer_joins_to_relids()

Relids add_outer_joins_to_relids ( PlannerInfo root,
Relids  input_relids,
SpecialJoinInfo sjinfo,
List **  pushed_down_joins 
)

Definition at line 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_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:815
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:300
#define lfirst(lc)
Definition: pg_list.h:172
Relids min_righthand
Definition: pathnodes.h:3031
Relids commute_above_l
Definition: pathnodes.h:3036
JoinType jointype
Definition: pathnodes.h:3034
Relids commute_below_l
Definition: pathnodes.h:3038
Relids min_lefthand
Definition: pathnodes.h:3030

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:311
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:1806
Bitmapset * Relids
Definition: pathnodes.h:30
static int pg_leftmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:41
static int list_length(const List *l)
Definition: pg_list.h:152
#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:6483
Definition: pg_list.h:54
List * pathkeys
Definition: pathnodes.h:1802
Cardinality rows
Definition: pathnodes.h:1796
int parallel_workers
Definition: pathnodes.h:1793
Cost total_cost
Definition: pathnodes.h:1799
bool consider_parallel
Definition: pathnodes.h:914
List * pathlist
Definition: pathnodes.h:925
struct Path * cheapest_startup_path
Definition: pathnodes.h:928
struct Path * cheapest_total_path
Definition: pathnodes.h:929
bool consider_startup
Definition: pathnodes.h:910
List * partial_pathlist
Definition: pathnodes.h:927

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:5099
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:313
@ JOIN_FULL
Definition: nodes.h:301
@ JOIN_INNER
Definition: nodes.h:299
@ JOIN_UNIQUE_OUTER
Definition: nodes.h:322
@ JOIN_UNIQUE_INNER
Definition: nodes.h:323
@ JOIN_ANTI
Definition: nodes.h:314
List * mergeclause_list
Definition: pathnodes.h:3367
Relids param_source_rels
Definition: pathnodes.h:3371
SemiAntiJoinFactors semifactors
Definition: pathnodes.h:3370
SpecialJoinInfo * sjinfo
Definition: pathnodes.h:3369
Relids lateral_relids
Definition: pathnodes.h:940

References bms_add_members(), bms_difference(), bms_is_subset(), bms_join(), bms_overlap(), compute_semi_anti_join_factors(), enable_hashjoin, enable_mergejoin, hash_inner_and_outer(), JoinPathExtraData::inner_unique, innerrel_is_unique(), JOIN_ANTI, JOIN_FULL, JOIN_INNER, JOIN_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, SpecialJoinInfo::jointype, RelOptInfo::lateral_relids, lfirst, match_unsorted_outer(), JoinPathExtraData::mergeclause_list, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, JoinPathExtraData::param_source_rels, RelOptInfo::relids, RELOPT_OTHER_JOINREL, RelOptInfo::reloptkind, JoinPathExtraData::restrictlist, root, select_mergejoin_clauses(), JoinPathExtraData::semifactors, set_join_pathlist_hook, JoinPathExtraData::sjinfo, sort_inner_and_outer(), and RelOptInfo::top_parent_relids.

Referenced by populate_joinrel_with_paths().

◆ add_setop_child_rel_equivalences()

void add_setop_child_rel_equivalences ( PlannerInfo root,
RelOptInfo child_rel,
List child_tlist,
List setop_pathkeys 
)

Definition at line 3084 of file equivclass.c.

3086{
3087 ListCell *lc;
3088 ListCell *lc2 = list_head(setop_pathkeys);
3089
3090 foreach(lc, child_tlist)
3091 {
3093 EquivalenceMember *parent_em;
3094 PathKey *pk;
3095
3096 if (tle->resjunk)
3097 continue;
3098
3099 if (lc2 == NULL)
3100 elog(ERROR, "too few pathkeys for set operation");
3101
3102 pk = lfirst_node(PathKey, lc2);
3103 parent_em = linitial(pk->pk_eclass->ec_members);
3104
3105 /*
3106 * We can safely pass the parent member as the first member in the
3107 * ec_members list as this is added first in generate_union_paths,
3108 * likewise, the JoinDomain can be that of the initial member of the
3109 * Pathkey's EquivalenceClass. We pass -1 for ec_index since we
3110 * maintain the eclass_indexes for the child_rel after the loop.
3111 */
3113 pk->pk_eclass,
3114 -1,
3115 tle->expr,
3116 child_rel->relids,
3117 parent_em->em_jdomain,
3118 parent_em,
3119 exprType((Node *) tle->expr),
3120 child_rel->relid);
3121
3122 lc2 = lnext(setop_pathkeys, lc2);
3123 }
3124
3125 /*
3126 * transformSetOperationStmt() ensures that the targetlist never contains
3127 * any resjunk columns, so all eclasses that exist in 'root' must have
3128 * received a new member in the loop above. Add them to the child_rel's
3129 * eclass_indexes.
3130 */
3131 child_rel->eclass_indexes = bms_add_range(child_rel->eclass_indexes, 0,
3132 list_length(root->eq_classes) - 1);
3133}
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:226
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
JoinDomain * em_jdomain
Definition: pathnodes.h:1516
Expr * expr
Definition: primnodes.h:2219

References add_child_eq_member(), bms_add_range(), RelOptInfo::eclass_indexes, elog, EquivalenceMember::em_jdomain, ERROR, TargetEntry::expr, exprType(), lfirst_node, linitial, list_head(), list_length(), lnext(), RelOptInfo::relid, RelOptInfo::relids, and root.

Referenced by build_setop_child_paths().

◆ append_pathkeys()

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 CompareType cmptype;
1010 PathKey *cpathkey;
1011
1012 /* Find the operator in pg_amop --- failure shouldn't happen */
1014 &opfamily, &opcintype, &cmptype))
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 (cmptype == COMPARE_GT),
1024 (cmptype == COMPARE_GT),
1025 0,
1026 rel,
1027 create_it);
1028
1029 if (cpathkey)
1030 pathkeys = list_make1(cpathkey);
1031 else
1032 pathkeys = NIL;
1033
1034 return pathkeys;
1035}
CompareType
Definition: cmptype.h:32
@ COMPARE_GT
Definition: cmptype.h:38
bool get_ordering_op_properties(Oid opno, Oid *opfamily, Oid *opcintype, CompareType *cmptype)
Definition: lsyscache.c:265
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:30

References COMPARE_GT, elog, ERROR, exprCollation(), get_ordering_op_properties(), list_make1, make_pathkey_from_sortinfo(), NIL, and root.

Referenced by set_function_pathlist().

◆ build_index_pathkeys()

List * build_index_pathkeys ( PlannerInfo root,
IndexOptInfo index,
ScanDirection  scandir 
)

Definition at line 740 of file pathkeys.c.

743{
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 1295 of file pathkeys.c.

1299{
1300 /* RIGHT_SEMI should not come here */
1301 Assert(jointype != JOIN_RIGHT_SEMI);
1302
1303 if (jointype == JOIN_FULL ||
1304 jointype == JOIN_RIGHT ||
1305 jointype == JOIN_RIGHT_ANTI)
1306 return NIL;
1307
1308 /*
1309 * This used to be quite a complex bit of code, but now that all pathkey
1310 * sublists start out life canonicalized, we don't have to do a darn thing
1311 * here!
1312 *
1313 * We do, however, need to truncate the pathkeys list, since it may
1314 * contain pathkeys that were useful for forming this joinrel but are
1315 * uninteresting to higher levels.
1316 */
1317 return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1318}
@ JOIN_RIGHT
Definition: nodes.h:302
@ JOIN_RIGHT_SEMI
Definition: nodes.h:315
@ JOIN_RIGHT_ANTI
Definition: nodes.h:316
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:2270

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:1066

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 545 of file equivclass.c.

546{
547 Oid expr_type = exprType((Node *) expr);
548
549 /*
550 * For a polymorphic-input-type opclass, just keep the same exposed type.
551 * RECORD opclasses work like polymorphic-type ones for this purpose.
552 */
553 if (IsPolymorphicType(req_type) || req_type == RECORDOID)
554 req_type = expr_type;
555
556 /*
557 * No work if the expression exposes the right type/collation already.
558 */
559 if (expr_type != req_type ||
560 exprCollation((Node *) expr) != req_collation)
561 {
562 /*
563 * If we have to change the type of the expression, set typmod to -1,
564 * since the new type may not have the same typmod interpretation.
565 * When we only have to change collation, preserve the exposed typmod.
566 */
567 int32 req_typmod;
568
569 if (expr_type != req_type)
570 req_typmod = -1;
571 else
572 req_typmod = exprTypmod((Node *) expr);
573
574 /*
575 * Use applyRelabelType so that we preserve const-flatness. This is
576 * important since eval_const_expressions has already been applied.
577 */
578 expr = (Expr *) applyRelabelType((Node *) expr,
579 req_type, req_typmod, req_collation,
580 COERCE_IMPLICIT_CAST, -1, false);
581 }
582
583 return expr;
584}
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:371
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo)
Definition: equivclass.c:1550
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:856
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:1012
List * joininfo
Definition: pathnodes.h:1018
List * indexlist
Definition: pathnodes.h:971
Relids nulling_relids
Definition: pathnodes.h:965
Expr * clause
Definition: pathnodes.h:2700

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 4234 of file allpaths.c.

4236{
4237 int parallel_workers = 0;
4238
4239 /*
4240 * If the user has set the parallel_workers reloption, use that; otherwise
4241 * select a default number of workers.
4242 */
4243 if (rel->rel_parallel_workers != -1)
4244 parallel_workers = rel->rel_parallel_workers;
4245 else
4246 {
4247 /*
4248 * If the number of pages being scanned is insufficient to justify a
4249 * parallel scan, just return zero ... unless it's an inheritance
4250 * child. In that case, we want to generate a parallel path here
4251 * anyway. It might not be worthwhile just for this relation, but
4252 * when combined with all of its inheritance siblings it may well pay
4253 * off.
4254 */
4255 if (rel->reloptkind == RELOPT_BASEREL &&
4256 ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
4257 (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
4258 return 0;
4259
4260 if (heap_pages >= 0)
4261 {
4262 int heap_parallel_threshold;
4263 int heap_parallel_workers = 1;
4264
4265 /*
4266 * Select the number of workers based on the log of the size of
4267 * the relation. This probably needs to be a good deal more
4268 * sophisticated, but we need something here for now. Note that
4269 * the upper limit of the min_parallel_table_scan_size GUC is
4270 * chosen to prevent overflow here.
4271 */
4272 heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
4273 while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
4274 {
4275 heap_parallel_workers++;
4276 heap_parallel_threshold *= 3;
4277 if (heap_parallel_threshold > INT_MAX / 3)
4278 break; /* avoid overflow */
4279 }
4280
4281 parallel_workers = heap_parallel_workers;
4282 }
4283
4284 if (index_pages >= 0)
4285 {
4286 int index_parallel_workers = 1;
4287 int index_parallel_threshold;
4288
4289 /* same calculation as for heap_pages above */
4290 index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
4291 while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
4292 {
4293 index_parallel_workers++;
4294 index_parallel_threshold *= 3;
4295 if (index_parallel_threshold > INT_MAX / 3)
4296 break; /* avoid overflow */
4297 }
4298
4299 if (parallel_workers > 0)
4300 parallel_workers = Min(parallel_workers, index_parallel_workers);
4301 else
4302 parallel_workers = index_parallel_workers;
4303 }
4304 }
4305
4306 /* In no case use more than caller supplied maximum number of workers */
4307 parallel_workers = Min(parallel_workers, max_workers);
4308
4309 return parallel_workers;
4310}
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:983

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_cmptype,
1122 sub_pathkey->pk_nulls_first);
1123 }
1124 }
1125 else
1126 {
1127 /*
1128 * Otherwise, the sub_pathkey's EquivalenceClass could contain
1129 * multiple elements (representing knowledge that multiple items
1130 * are effectively equal). Each element might match none, one, or
1131 * more of the output columns that are visible to the outer query.
1132 * This means we may have multiple possible representations of the
1133 * sub_pathkey in the context of the outer query. Ideally we
1134 * would generate them all and put them all into an EC of the
1135 * outer query, thereby propagating equality knowledge up to the
1136 * outer query. Right now we cannot do so, because the outer
1137 * query's EquivalenceClasses are already frozen when this is
1138 * called. Instead we prefer the one that has the highest "score"
1139 * (number of EC peers, plus one if it matches the outer
1140 * query_pathkeys). This is the most likely to be useful in the
1141 * outer query.
1142 */
1143 int best_score = -1;
1144 ListCell *j;
1145
1146 /* Ignore children here */
1147 foreach(j, sub_eclass->ec_members)
1148 {
1149 EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
1150 Expr *sub_expr = sub_member->em_expr;
1151 Oid sub_expr_type = sub_member->em_datatype;
1152 Oid sub_expr_coll = sub_eclass->ec_collation;
1153 ListCell *k;
1154
1155 /* Child members should not exist in ec_members */
1156 Assert(!sub_member->em_is_child);
1157
1158 foreach(k, subquery_tlist)
1159 {
1160 TargetEntry *tle = (TargetEntry *) lfirst(k);
1161 Var *outer_var;
1162 Expr *tle_expr;
1163 EquivalenceClass *outer_ec;
1164 PathKey *outer_pk;
1165 int score;
1166
1167 /* Is TLE actually available to the outer query? */
1168 outer_var = find_var_for_subquery_tle(rel, tle);
1169 if (!outer_var)
1170 continue;
1171
1172 /*
1173 * The targetlist entry is considered to match if it
1174 * matches after sort-key canonicalization. That is
1175 * needed since the sub_expr has been through the same
1176 * process.
1177 */
1178 tle_expr = canonicalize_ec_expression(tle->expr,
1179 sub_expr_type,
1180 sub_expr_coll);
1181 if (!equal(tle_expr, sub_expr))
1182 continue;
1183
1184 /* See if we have a matching EC for the TLE */
1185 outer_ec = get_eclass_for_sort_expr(root,
1186 (Expr *) outer_var,
1187 sub_eclass->ec_opfamilies,
1188 sub_expr_type,
1189 sub_expr_coll,
1190 0,
1191 rel->relids,
1192 false);
1193
1194 /*
1195 * If we don't find a matching EC, this sub-pathkey isn't
1196 * interesting to the outer query
1197 */
1198 if (!outer_ec)
1199 continue;
1200
1201 outer_pk = make_canonical_pathkey(root,
1202 outer_ec,
1203 sub_pathkey->pk_opfamily,
1204 sub_pathkey->pk_cmptype,
1205 sub_pathkey->pk_nulls_first);
1206 /* score = # of equivalence peers */
1207 score = list_length(outer_ec->ec_members) - 1;
1208 /* +1 if it matches the proper query_pathkeys item */
1209 if (retvallen < outer_query_keys &&
1210 list_nth(root->query_pathkeys, retvallen) == outer_pk)
1211 score++;
1212 if (score > best_score)
1213 {
1214 best_pathkey = outer_pk;
1215 best_score = score;
1216 }
1217 }
1218 }
1219 }
1220
1221 /*
1222 * If we couldn't find a representation of this sub_pathkey, we're
1223 * done (we can't use the ones to its right, either).
1224 */
1225 if (!best_pathkey)
1226 break;
1227
1228 /*
1229 * Eliminate redundant ordering info; could happen if outer query
1230 * equivalences subquery keys...
1231 */
1232 if (!pathkey_is_redundant(best_pathkey, retval))
1233 {
1234 retval = lappend(retval, best_pathkey);
1235 retvallen++;
1236 }
1237 }
1238
1239 return retval;
1240}
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:736
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:545
int j
Definition: isn.c:78
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, CompareType cmptype, bool nulls_first)
Definition: pathkeys.c:56
static Var * find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
Definition: pathkeys.c:1252
List * ec_opfamilies
Definition: pathnodes.h:1450
CompareType pk_cmptype
Definition: pathnodes.h:1606
bool pk_nulls_first
Definition: pathnodes.h:1607
Oid pk_opfamily
Definition: pathnodes.h:1605
Definition: primnodes.h:262
TargetEntry * get_sortgroupref_tle(Index sortref, List *targetList)
Definition: tlist.c:345

References Assert(), canonicalize_ec_expression(), EquivalenceClass::ec_collation, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_sortref, elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, equal(), ERROR, TargetEntry::expr, find_var_for_subquery_tle(), get_eclass_for_sort_expr(), get_sortgroupref_tle(), i, j, lappend(), lfirst, linitial, list_length(), list_nth(), make_canonical_pathkey(), NIL, pathkey_is_redundant(), PathKey::pk_cmptype, PathKey::pk_nulls_first, PathKey::pk_opfamily, RelOptInfo::relids, and root.

Referenced by build_setop_child_paths(), set_cte_pathlist(), and set_subquery_pathlist().

◆ create_index_paths()

void create_index_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 239 of file indxpath.c.

240{
241 List *indexpaths;
242 List *bitindexpaths;
243 List *bitjoinpaths;
244 List *joinorclauses;
245 IndexClauseSet rclauseset;
246 IndexClauseSet jclauseset;
247 IndexClauseSet eclauseset;
248 ListCell *lc;
249
250 /* Skip the whole mess if no indexes */
251 if (rel->indexlist == NIL)
252 return;
253
254 /* Bitmap paths are collected and then dealt with at the end */
255 bitindexpaths = bitjoinpaths = joinorclauses = NIL;
256
257 /* Examine each index in turn */
258 foreach(lc, rel->indexlist)
259 {
261
262 /* Protect limited-size array in IndexClauseSets */
263 Assert(index->nkeycolumns <= INDEX_MAX_KEYS);
264
265 /*
266 * Ignore partial indexes that do not match the query.
267 * (generate_bitmap_or_paths() might be able to do something with
268 * them, but that's of no concern here.)
269 */
270 if (index->indpred != NIL && !index->predOK)
271 continue;
272
273 /*
274 * Identify the restriction clauses that can match the index.
275 */
276 MemSet(&rclauseset, 0, sizeof(rclauseset));
278
279 /*
280 * Build index paths from the restriction clauses. These will be
281 * non-parameterized paths. Plain paths go directly to add_path(),
282 * bitmap paths are added to bitindexpaths to be handled below.
283 */
284 get_index_paths(root, rel, index, &rclauseset,
285 &bitindexpaths);
286
287 /*
288 * Identify the join clauses that can match the index. For the moment
289 * we keep them separate from the restriction clauses. Note that this
290 * step finds only "loose" join clauses that have not been merged into
291 * EquivalenceClasses. Also, collect join OR clauses for later.
292 */
293 MemSet(&jclauseset, 0, sizeof(jclauseset));
295 &jclauseset, &joinorclauses);
296
297 /*
298 * Look for EquivalenceClasses that can generate joinclauses matching
299 * the index.
300 */
301 MemSet(&eclauseset, 0, sizeof(eclauseset));
303 &eclauseset);
304
305 /*
306 * If we found any plain or eclass join clauses, build parameterized
307 * index paths using them.
308 */
309 if (jclauseset.nonempty || eclauseset.nonempty)
311 &rclauseset,
312 &jclauseset,
313 &eclauseset,
314 &bitjoinpaths);
315 }
316
317 /*
318 * Generate BitmapOrPaths for any suitable OR-clauses present in the
319 * restriction list. Add these to bitindexpaths.
320 */
321 indexpaths = generate_bitmap_or_paths(root, rel,
322 rel->baserestrictinfo, NIL);
323 bitindexpaths = list_concat(bitindexpaths, indexpaths);
324
325 /*
326 * Likewise, generate BitmapOrPaths for any suitable OR-clauses present in
327 * the joinclause list. Add these to bitjoinpaths.
328 */
329 indexpaths = generate_bitmap_or_paths(root, rel,
330 joinorclauses, rel->baserestrictinfo);
331 bitjoinpaths = list_concat(bitjoinpaths, indexpaths);
332
333 /*
334 * If we found anything usable, generate a BitmapHeapPath for the most
335 * promising combination of restriction bitmap index paths. Note there
336 * will be only one such path no matter how many indexes exist. This
337 * should be sufficient since there's basically only one figure of merit
338 * (total cost) for such a path.
339 */
340 if (bitindexpaths != NIL)
341 {
342 Path *bitmapqual;
343 BitmapHeapPath *bpath;
344
345 bitmapqual = choose_bitmap_and(root, rel, bitindexpaths);
346 bpath = create_bitmap_heap_path(root, rel, bitmapqual,
347 rel->lateral_relids, 1.0, 0);
348 add_path(rel, (Path *) bpath);
349
350 /* create a partial bitmap heap path */
351 if (rel->consider_parallel && rel->lateral_relids == NULL)
352 create_partial_bitmap_paths(root, rel, bitmapqual);
353 }
354
355 /*
356 * Likewise, if we found anything usable, generate BitmapHeapPaths for the
357 * most promising combinations of join bitmap index paths. Our strategy
358 * is to generate one such path for each distinct parameterization seen
359 * among the available bitmap index paths. This may look pretty
360 * expensive, but usually there won't be very many distinct
361 * parameterizations. (This logic is quite similar to that in
362 * consider_index_join_clauses, but we're working with whole paths not
363 * individual clauses.)
364 */
365 if (bitjoinpaths != NIL)
366 {
367 List *all_path_outers;
368
369 /* Identify each distinct parameterization seen in bitjoinpaths */
370 all_path_outers = NIL;
371 foreach(lc, bitjoinpaths)
372 {
373 Path *path = (Path *) lfirst(lc);
374 Relids required_outer = PATH_REQ_OUTER(path);
375
376 all_path_outers = list_append_unique(all_path_outers,
377 required_outer);
378 }
379
380 /* Now, for each distinct parameterization set ... */
381 foreach(lc, all_path_outers)
382 {
383 Relids max_outers = (Relids) lfirst(lc);
384 List *this_path_set;
385 Path *bitmapqual;
386 Relids required_outer;
387 double loop_count;
388 BitmapHeapPath *bpath;
389 ListCell *lcp;
390
391 /* Identify all the bitmap join paths needing no more than that */
392 this_path_set = NIL;
393 foreach(lcp, bitjoinpaths)
394 {
395 Path *path = (Path *) lfirst(lcp);
396
397 if (bms_is_subset(PATH_REQ_OUTER(path), max_outers))
398 this_path_set = lappend(this_path_set, path);
399 }
400
401 /*
402 * Add in restriction bitmap paths, since they can be used
403 * together with any join paths.
404 */
405 this_path_set = list_concat(this_path_set, bitindexpaths);
406
407 /* Select best AND combination for this parameterization */
408 bitmapqual = choose_bitmap_and(root, rel, this_path_set);
409
410 /* And push that path into the mix */
411 required_outer = PATH_REQ_OUTER(bitmapqual);
412 loop_count = get_loop_count(root, rel->relid, required_outer);
413 bpath = create_bitmap_heap_path(root, rel, bitmapqual,
414 required_outer, loop_count, 0);
415 add_path(rel, (Path *) bpath);
416 }
417 }
418}
void create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual)
Definition: allpaths.c:4198
#define MemSet(start, val, len)
Definition: c.h:991
static Path * choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
Definition: indxpath.c:1784
static void match_join_clauses_to_index(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauseset, List **joinorclauses)
Definition: indxpath.c:2481
static void match_eclass_clauses_to_index(PlannerInfo *root, IndexOptInfo *index, IndexClauseSet *clauseset)
Definition: indxpath.c:2515
static void get_index_paths(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauses, List **bitindexpaths)
Definition: indxpath.c:715
static double get_loop_count(PlannerInfo *root, Index cur_relid, Relids outer_relids)
Definition: indxpath.c:2326
static void consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *rclauseset, IndexClauseSet *jclauseset, IndexClauseSet *eclauseset, List **bitindexpaths)
Definition: indxpath.c:436
static void match_restriction_clauses_to_index(PlannerInfo *root, IndexOptInfo *index, IndexClauseSet *clauseset)
Definition: indxpath.c:2465
static List * generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel, List *clauses, List *other_clauses)
Definition: indxpath.c:1628
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:55

References add_path(), Assert(), RelOptInfo::baserestrictinfo, bms_is_subset(), choose_bitmap_and(), consider_index_join_clauses(), RelOptInfo::consider_parallel, create_bitmap_heap_path(), create_partial_bitmap_paths(), generate_bitmap_or_paths(), get_index_paths(), get_loop_count(), INDEX_MAX_KEYS, RelOptInfo::indexlist, lappend(), RelOptInfo::lateral_relids, lfirst, list_append_unique(), list_concat(), match_eclass_clauses_to_index(), match_join_clauses_to_index(), match_restriction_clauses_to_index(), MemSet, NIL, IndexClauseSet::nonempty, PATH_REQ_OUTER, RelOptInfo::relid, and root.

Referenced by set_plain_rel_pathlist().

◆ create_partial_bitmap_paths()

void create_partial_bitmap_paths ( PlannerInfo root,
RelOptInfo rel,
Path bitmapqual 
)

Definition at line 4198 of file allpaths.c.

4200{
4201 int parallel_workers;
4202 double pages_fetched;
4203
4204 /* Compute heap pages for bitmap heap scan */
4205 pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
4206 NULL, NULL);
4207
4208 parallel_workers = compute_parallel_worker(rel, pages_fetched, -1,
4210
4211 if (parallel_workers <= 0)
4212 return;
4213
4215 bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
4216}
int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
Definition: allpaths.c:4234
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:3239
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:969
bool has_eclass_joins
Definition: pathnodes.h:1020
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().

◆ ec_clear_derived_clauses()

void ec_clear_derived_clauses ( EquivalenceClass ec)

Definition at line 3831 of file equivclass.c.

3832{
3834 ec->ec_derives_list = NIL;
3835
3836 if (ec->ec_derives_hash)
3837 {
3838 derives_destroy(ec->ec_derives_hash);
3839 ec->ec_derives_hash = NULL;
3840 }
3841}
void list_free(List *list)
Definition: list.c:1546
struct derives_hash * ec_derives_hash
Definition: pathnodes.h:1457
List * ec_derives_list
Definition: pathnodes.h:1456

References EquivalenceClass::ec_derives_hash, EquivalenceClass::ec_derives_list, list_free(), and NIL.

Referenced by process_equivalence(), remove_rel_from_eclass(), and update_eclasses().

◆ eclass_member_iterator_next()

EquivalenceMember * eclass_member_iterator_next ( EquivalenceMemberIterator it)

Definition at line 3175 of file equivclass.c.

3176{
3177 while (it->current_list != NULL)
3178 {
3179 while (it->current_cell != NULL)
3180 {
3182
3183 nextcell:
3186 return em;
3187 }
3188
3189 /* Search for the next list to return members from */
3190 while ((it->current_relid = bms_next_member(it->child_relids, it->current_relid)) > 0)
3191 {
3192 /*
3193 * Be paranoid in case we're given relids above what we've sized
3194 * the ec_childmembers array to.
3195 */
3196 if (it->current_relid >= it->ec->ec_childmembers_size)
3197 return NULL;
3198
3200
3201 /* If there are members in this list, use it. */
3202 if (it->current_list != NIL)
3203 {
3204 /* point current_cell to the head of this list */
3206 goto nextcell;
3207 }
3208 }
3209 return NULL;
3210 }
3211
3212 return NULL;
3213}
int ec_childmembers_size
Definition: pathnodes.h:1452
List ** ec_childmembers
Definition: pathnodes.h:1454
EquivalenceClass * ec
Definition: pathnodes.h:1572

References bms_next_member(), EquivalenceMemberIterator::child_relids, EquivalenceMemberIterator::current_cell, EquivalenceMemberIterator::current_list, EquivalenceMemberIterator::current_relid, EquivalenceMemberIterator::ec, EquivalenceClass::ec_childmembers, EquivalenceClass::ec_childmembers_size, lfirst_node, list_head(), lnext(), and NIL.

Referenced by find_computable_ec_member(), find_ec_member_matching_expr(), find_em_for_rel(), generate_implied_equalities_for_column(), generate_join_implied_equalities_normal(), get_eclass_for_sort_expr(), and match_pathkeys_to_index().

◆ eclass_useful_for_merging()

bool eclass_useful_for_merging ( PlannerInfo root,
EquivalenceClass eclass,
RelOptInfo rel 
)

Definition at line 3490 of file equivclass.c.

3493{
3494 Relids relids;
3495 ListCell *lc;
3496
3497 Assert(!eclass->ec_merged);
3498
3499 /*
3500 * Won't generate joinclauses if const or single-member (the latter test
3501 * covers the volatile case too)
3502 */
3503 if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
3504 return false;
3505
3506 /*
3507 * Note we don't test ec_broken; if we did, we'd need a separate code path
3508 * to look through ec_sources. Checking the members anyway is OK as a
3509 * possibly-overoptimistic heuristic.
3510 */
3511
3512 /* If specified rel is a child, we must consider the topmost parent rel */
3513 if (IS_OTHER_REL(rel))
3514 {
3516 relids = rel->top_parent_relids;
3517 }
3518 else
3519 relids = rel->relids;
3520
3521 /* If rel already includes all members of eclass, no point in searching */
3522 if (bms_is_subset(eclass->ec_relids, relids))
3523 return false;
3524
3525 /*
3526 * To join, we need a member not in the given rel. Ignore children here.
3527 */
3528 foreach(lc, eclass->ec_members)
3529 {
3530 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
3531
3532 /* Child members should not exist in ec_members */
3533 Assert(!cur_em->em_is_child);
3534
3535 if (!bms_overlap(cur_em->em_relids, relids))
3536 return true;
3537 }
3538
3539 return false;
3540}
#define IS_OTHER_REL(rel)
Definition: pathnodes.h:881
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 2648 of file equivclass.c.

2649{
2650 ListCell *lc1;
2651
2652 foreach(lc1, root->eq_classes)
2653 {
2655 bool item1member = false;
2656 bool item2member = false;
2657 ListCell *lc2;
2658
2659 /* Never match to a volatile EC */
2660 if (ec->ec_has_volatile)
2661 continue;
2662
2663 /*
2664 * It's okay to consider ec_broken ECs here. Brokenness just means we
2665 * couldn't derive all the implied clauses we'd have liked to; it does
2666 * not invalidate our knowledge that the members are equal.
2667 */
2668
2669 /* Ignore if this EC doesn't use specified opfamily */
2670 if (OidIsValid(opfamily) &&
2671 !list_member_oid(ec->ec_opfamilies, opfamily))
2672 continue;
2673
2674 /* Ignore children here */
2675 foreach(lc2, ec->ec_members)
2676 {
2678
2679 /* Child members should not exist in ec_members */
2680 Assert(!em->em_is_child);
2681 if (equal(item1, em->em_expr))
2682 item1member = true;
2683 else if (equal(item2, em->em_expr))
2684 item2member = true;
2685 /* Exit as soon as equality is proven */
2686 if (item1member && item2member)
2687 return true;
2688 }
2689 }
2690 return false;
2691}
#define OidIsValid(objectId)
Definition: c.h:746
bool list_member_oid(const List *list, Oid datum)
Definition: list.c:722

References Assert(), EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, equal(), lfirst, list_member_oid(), OidIsValid, and root.

Referenced by add_unique_group_var(), and have_partkey_equi_join().

◆ find_computable_ec_member()

EquivalenceMember * find_computable_ec_member ( PlannerInfo root,
EquivalenceClass ec,
List exprs,
Relids  relids,
bool  require_parallel_safe 
)

Definition at line 991 of file equivclass.c.

996{
997 List *exprvars;
1000
1001 /*
1002 * Pull out the Vars and quasi-Vars present in "exprs". In the typical
1003 * non-appendrel case, this is just another representation of the same
1004 * list. However, it does remove the distinction between the case of a
1005 * list of plain expressions and a list of TargetEntrys.
1006 */
1007 exprvars = pull_var_clause((Node *) exprs,
1012
1013 setup_eclass_member_iterator(&it, ec, relids);
1014 while ((em = eclass_member_iterator_next(&it)) != NULL)
1015 {
1016 List *emvars;
1017 ListCell *lc2;
1018
1019 /*
1020 * We shouldn't be trying to sort by an equivalence class that
1021 * contains a constant, so no need to consider such cases any further.
1022 */
1023 if (em->em_is_const)
1024 continue;
1025
1026 /*
1027 * Ignore child members unless they belong to the requested rel.
1028 */
1029 if (em->em_is_child &&
1030 !bms_is_subset(em->em_relids, relids))
1031 continue;
1032
1033 /*
1034 * Match if all Vars and quasi-Vars are present in "exprs".
1035 */
1036 emvars = pull_var_clause((Node *) em->em_expr,
1040 foreach(lc2, emvars)
1041 {
1042 if (!list_member(exprvars, lfirst(lc2)))
1043 break;
1044 }
1045 list_free(emvars);
1046 if (lc2)
1047 continue; /* we hit a non-available Var */
1048
1049 /*
1050 * If requested, reject expressions that are not parallel-safe. We
1051 * check this last because it's a rather expensive test.
1052 */
1053 if (require_parallel_safe &&
1054 !is_parallel_safe(root, (Node *) em->em_expr))
1055 continue;
1056
1057 return em; /* found usable expression */
1058 }
1059
1060 return NULL;
1061}
bool is_parallel_safe(PlannerInfo *root, Node *node)
Definition: clauses.c:754
void setup_eclass_member_iterator(EquivalenceMemberIterator *it, EquivalenceClass *ec, Relids child_relids)
Definition: equivclass.c:3156
EquivalenceMember * eclass_member_iterator_next(EquivalenceMemberIterator *it)
Definition: equivclass.c:3175
bool list_member(const List *list, const void *datum)
Definition: list.c:661
#define PVC_INCLUDE_WINDOWFUNCS
Definition: optimizer.h:194
#define PVC_INCLUDE_PLACEHOLDERS
Definition: optimizer.h:196
#define PVC_INCLUDE_CONVERTROWTYPES
Definition: optimizer.h:198
#define PVC_INCLUDE_AGGREGATES
Definition: optimizer.h:192
List * pull_var_clause(Node *node, int flags)
Definition: var.c:653

References bms_is_subset(), eclass_member_iterator_next(), EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, is_parallel_safe(), lfirst, list_free(), list_member(), pull_var_clause(), PVC_INCLUDE_AGGREGATES, PVC_INCLUDE_CONVERTROWTYPES, PVC_INCLUDE_PLACEHOLDERS, PVC_INCLUDE_WINDOWFUNCS, root, and setup_eclass_member_iterator().

Referenced by prepare_sort_from_pathkeys(), and relation_can_be_sorted_early().

◆ find_derived_clause_for_ec_member()

RestrictInfo * find_derived_clause_for_ec_member ( PlannerInfo root,
EquivalenceClass ec,
EquivalenceMember em 
)

Definition at line 2804 of file equivclass.c.

2807{
2808 Assert(ec->ec_has_const);
2809 Assert(!em->em_is_const);
2810
2811 return ec_search_derived_clause_for_ems(root, ec, em, NULL, NULL);
2812}
static RestrictInfo * ec_search_derived_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec, EquivalenceMember *leftem, EquivalenceMember *rightem, EquivalenceClass *parent_ec)
Definition: equivclass.c:3893

References Assert(), EquivalenceClass::ec_has_const, ec_search_derived_clause_for_ems(), EquivalenceMember::em_is_const, and root.

Referenced by get_foreign_key_join_selectivity().

◆ find_ec_member_matching_expr()

EquivalenceMember * find_ec_member_matching_expr ( EquivalenceClass ec,
Expr expr,
Relids  relids 
)

Definition at line 916 of file equivclass.c.

919{
922
923 /* We ignore binary-compatible relabeling on both ends */
924 while (expr && IsA(expr, RelabelType))
925 expr = ((RelabelType *) expr)->arg;
926
927 setup_eclass_member_iterator(&it, ec, relids);
928 while ((em = eclass_member_iterator_next(&it)) != NULL)
929 {
930 Expr *emexpr;
931
932 /*
933 * We shouldn't be trying to sort by an equivalence class that
934 * contains a constant, so no need to consider such cases any further.
935 */
936 if (em->em_is_const)
937 continue;
938
939 /*
940 * Ignore child members unless they belong to the requested rel.
941 */
942 if (em->em_is_child &&
943 !bms_is_subset(em->em_relids, relids))
944 continue;
945
946 /*
947 * Match if same expression (after stripping relabel).
948 */
949 emexpr = em->em_expr;
950 while (emexpr && IsA(emexpr, RelabelType))
951 emexpr = ((RelabelType *) emexpr)->arg;
952
953 if (equal(emexpr, expr))
954 return em;
955 }
956
957 return NULL;
958}
#define IsA(nodeptr, _type_)
Definition: nodes.h:164

References bms_is_subset(), eclass_member_iterator_next(), EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, equal(), IsA, and setup_eclass_member_iterator().

Referenced by make_unique_from_pathkeys(), prepare_sort_from_pathkeys(), and relation_can_be_sorted_early().

◆ find_mergeclauses_for_outer_pathkeys()

List * find_mergeclauses_for_outer_pathkeys ( PlannerInfo root,
List pathkeys,
List restrictinfos 
)

Definition at line 1544 of file pathkeys.c.

1547{
1548 List *mergeclauses = NIL;
1549 ListCell *i;
1550
1551 /* make sure we have eclasses cached in the clauses */
1552 foreach(i, restrictinfos)
1553 {
1554 RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1555
1557 }
1558
1559 foreach(i, pathkeys)
1560 {
1561 PathKey *pathkey = (PathKey *) lfirst(i);
1562 EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1563 List *matched_restrictinfos = NIL;
1564 ListCell *j;
1565
1566 /*----------
1567 * A mergejoin clause matches a pathkey if it has the same EC.
1568 * If there are multiple matching clauses, take them all. In plain
1569 * inner-join scenarios we expect only one match, because
1570 * equivalence-class processing will have removed any redundant
1571 * mergeclauses. However, in outer-join scenarios there might be
1572 * multiple matches. An example is
1573 *
1574 * select * from a full join b
1575 * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1576 *
1577 * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1578 * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1579 * we *must* do so or we will be unable to form a valid plan.
1580 *
1581 * We expect that the given pathkeys list is canonical, which means
1582 * no two members have the same EC, so it's not possible for this
1583 * code to enter the same mergeclause into the result list twice.
1584 *
1585 * It's possible that multiple matching clauses might have different
1586 * ECs on the other side, in which case the order we put them into our
1587 * result makes a difference in the pathkeys required for the inner
1588 * input rel. However this routine hasn't got any info about which
1589 * order would be best, so we don't worry about that.
1590 *
1591 * It's also possible that the selected mergejoin clauses produce
1592 * a noncanonical ordering of pathkeys for the inner side, ie, we
1593 * might select clauses that reference b.v1, b.v2, b.v1 in that
1594 * order. This is not harmful in itself, though it suggests that
1595 * the clauses are partially redundant. Since the alternative is
1596 * to omit mergejoin clauses and thereby possibly fail to generate a
1597 * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1598 * has to delete duplicates when it constructs the inner pathkeys
1599 * list, and we also have to deal with such cases specially in
1600 * create_mergejoin_plan().
1601 *----------
1602 */
1603 foreach(j, restrictinfos)
1604 {
1605 RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1606 EquivalenceClass *clause_ec;
1607
1608 clause_ec = rinfo->outer_is_left ?
1609 rinfo->left_ec : rinfo->right_ec;
1610 if (clause_ec == pathkey_ec)
1611 matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1612 }
1613
1614 /*
1615 * If we didn't find a mergeclause, we're done --- any additional
1616 * sort-key positions in the pathkeys are useless. (But we can still
1617 * mergejoin if we found at least one mergeclause.)
1618 */
1619 if (matched_restrictinfos == NIL)
1620 break;
1621
1622 /*
1623 * If we did find usable mergeclause(s) for this sort-key position,
1624 * add them to result list.
1625 */
1626 mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1627 }
1628
1629 return mergeclauses;
1630}
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1510

References i, j, lappend(), lfirst, list_concat(), NIL, root, and update_mergeclause_eclasses().

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

◆ generate_base_implied_equalities()

void generate_base_implied_equalities ( PlannerInfo root)

Definition at line 1188 of file equivclass.c.

1189{
1190 int ec_index;
1191 ListCell *lc;
1192
1193 /*
1194 * At this point, we're done absorbing knowledge of equivalences in the
1195 * query, so no further EC merging should happen, and ECs remaining in the
1196 * eq_classes list can be considered canonical. (But note that it's still
1197 * possible for new single-member ECs to be added through
1198 * get_eclass_for_sort_expr().)
1199 */
1200 root->ec_merging_done = true;
1201
1202 ec_index = 0;
1203 foreach(lc, root->eq_classes)
1204 {
1206 bool can_generate_joinclause = false;
1207 int i;
1208
1209 Assert(ec->ec_merged == NULL); /* else shouldn't be in list */
1210 Assert(!ec->ec_broken); /* not yet anyway... */
1211
1212 /*
1213 * Generate implied equalities that are restriction clauses.
1214 * Single-member ECs won't generate any deductions, either here or at
1215 * the join level.
1216 */
1217 if (list_length(ec->ec_members) > 1)
1218 {
1219 if (ec->ec_has_const)
1221 else
1223
1224 /* Recover if we failed to generate required derived clauses */
1225 if (ec->ec_broken)
1227
1228 /* Detect whether this EC might generate join clauses */
1229 can_generate_joinclause =
1231 }
1232
1233 /*
1234 * Mark the base rels cited in each eclass (which should all exist by
1235 * now) with the eq_classes indexes of all eclasses mentioning them.
1236 * This will let us avoid searching in subsequent lookups. While
1237 * we're at it, we can mark base rels that have pending eclass joins;
1238 * this is a cheap version of has_relevant_eclass_joinclause().
1239 */
1240 i = -1;
1241 while ((i = bms_next_member(ec->ec_relids, i)) > 0)
1242 {
1243 RelOptInfo *rel = root->simple_rel_array[i];
1244
1245 /* ignore the RTE_GROUP RTE */
1246 if (i == root->group_rtindex)
1247 continue;
1248
1249 if (rel == NULL) /* must be an outer join */
1250 {
1251 Assert(bms_is_member(i, root->outer_join_rels));
1252 continue;
1253 }
1254
1256
1258 ec_index);
1259
1260 if (can_generate_joinclause)
1261 rel->has_eclass_joins = true;
1262 }
1263
1264 ec_index++;
1265 }
1266}
static void generate_base_implied_equalities_broken(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1487
static void generate_base_implied_equalities_no_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1371
static void generate_base_implied_equalities_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1272
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:1468

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 3083 of file allpaths.c.

3084{
3085 Path *cheapest_partial_path;
3086 Path *simple_gather_path;
3087 ListCell *lc;
3088 double rows;
3089 double *rowsp = NULL;
3090
3091 /* If there are no partial paths, there's nothing to do here. */
3092 if (rel->partial_pathlist == NIL)
3093 return;
3094
3095 /* Should we override the rel's rowcount estimate? */
3096 if (override_rows)
3097 rowsp = &rows;
3098
3099 /*
3100 * The output of Gather is always unsorted, so there's only one partial
3101 * path of interest: the cheapest one. That will be the one at the front
3102 * of partial_pathlist because of the way add_partial_path works.
3103 */
3104 cheapest_partial_path = linitial(rel->partial_pathlist);
3105 rows = compute_gather_rows(cheapest_partial_path);
3106 simple_gather_path = (Path *)
3107 create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
3108 NULL, rowsp);
3109 add_path(rel, simple_gather_path);
3110
3111 /*
3112 * For each useful ordering, we can consider an order-preserving Gather
3113 * Merge.
3114 */
3115 foreach(lc, rel->partial_pathlist)
3116 {
3117 Path *subpath = (Path *) lfirst(lc);
3118 GatherMergePath *path;
3119
3120 if (subpath->pathkeys == NIL)
3121 continue;
3122
3125 subpath->pathkeys, NULL, rowsp);
3126 add_path(rel, &path->path);
3127 }
3128}
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:920

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 3239 of file equivclass.c.

3244{
3245 List *result = NIL;
3246 bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
3247 Relids parent_relids;
3248 int i;
3249
3250 /* Should be OK to rely on eclass_indexes */
3251 Assert(root->ec_merging_done);
3252
3253 /* Indexes are available only on base or "other" member relations. */
3254 Assert(IS_SIMPLE_REL(rel));
3255
3256 /* If it's a child rel, we'll need to know what its parent(s) are */
3257 if (is_child_rel)
3258 parent_relids = find_childrel_parents(root, rel);
3259 else
3260 parent_relids = NULL; /* not used, but keep compiler quiet */
3261
3262 i = -1;
3263 while ((i = bms_next_member(rel->eclass_indexes, i)) >= 0)
3264 {
3265 EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
3267 EquivalenceMember *cur_em;
3268 ListCell *lc2;
3269
3270 /* Sanity check eclass_indexes only contain ECs for rel */
3271 Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
3272
3273 /*
3274 * Won't generate joinclauses if const or single-member (the latter
3275 * test covers the volatile case too)
3276 */
3277 if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
3278 continue;
3279
3280 /*
3281 * Scan members, looking for a match to the target column. Note that
3282 * child EC members are considered, but only when they belong to the
3283 * target relation. (Unlike regular members, the same expression
3284 * could be a child member of more than one EC. Therefore, it's
3285 * potentially order-dependent which EC a child relation's target
3286 * column gets matched to. This is annoying but it only happens in
3287 * corner cases, so for now we live with just reporting the first
3288 * match. See also get_eclass_for_sort_expr.)
3289 */
3290 setup_eclass_member_iterator(&it, cur_ec, rel->relids);
3291 while ((cur_em = eclass_member_iterator_next(&it)) != NULL)
3292 {
3293 if (bms_equal(cur_em->em_relids, rel->relids) &&
3294 callback(root, rel, cur_ec, cur_em, callback_arg))
3295 break;
3296 }
3297
3298 if (!cur_em)
3299 continue;
3300
3301 /*
3302 * Found our match. Scan the other EC members and attempt to generate
3303 * joinclauses. Ignore children here.
3304 */
3305 foreach(lc2, cur_ec->ec_members)
3306 {
3307 EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
3308 Oid eq_op;
3309 RestrictInfo *rinfo;
3310
3311 /* Child members should not exist in ec_members */
3312 Assert(!other_em->em_is_child);
3313
3314 /* Make sure it'll be a join to a different rel */
3315 if (other_em == cur_em ||
3316 bms_overlap(other_em->em_relids, rel->relids))
3317 continue;
3318
3319 /* Forget it if caller doesn't want joins to this rel */
3320 if (bms_overlap(other_em->em_relids, prohibited_rels))
3321 continue;
3322
3323 /*
3324 * Also, if this is a child rel, avoid generating a useless join
3325 * to its parent rel(s).
3326 */
3327 if (is_child_rel &&
3328 bms_overlap(parent_relids, other_em->em_relids))
3329 continue;
3330
3331 eq_op = select_equality_operator(cur_ec,
3332 cur_em->em_datatype,
3333 other_em->em_datatype);
3334 if (!OidIsValid(eq_op))
3335 continue;
3336
3337 /* set parent_ec to mark as redundant with other joinclauses */
3338 rinfo = create_join_clause(root, cur_ec, eq_op,
3339 cur_em, other_em,
3340 cur_ec);
3341
3342 result = lappend(result, rinfo);
3343 }
3344
3345 /*
3346 * If somehow we failed to create any join clauses, we might as well
3347 * keep scanning the ECs for another match. But if we did make any,
3348 * we're done, because we don't want to return non-redundant clauses.
3349 */
3350 if (result)
3351 break;
3352 }
3353
3354 return result;
3355}
static RestrictInfo * create_join_clause(PlannerInfo *root, EquivalenceClass *ec, Oid opno, EquivalenceMember *leftem, EquivalenceMember *rightem, EquivalenceClass *parent_ec)
Definition: equivclass.c:1983
static Oid select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype)
Definition: equivclass.c:1948
static void callback(struct sockaddr *addr, struct sockaddr *mask, void *unused)
Definition: test_ifaddrs.c:46

References Assert(), bms_equal(), bms_is_subset(), bms_next_member(), bms_overlap(), callback(), create_join_clause(), EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, RelOptInfo::eclass_indexes, eclass_member_iterator_next(), EquivalenceMember::em_datatype, EquivalenceMember::em_is_child, EquivalenceMember::em_relids, find_childrel_parents(), i, IS_SIMPLE_REL, lappend(), lfirst, list_length(), list_nth(), NIL, OidIsValid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, root, select_equality_operator(), and setup_eclass_member_iterator().

Referenced by create_tidscan_paths(), match_eclass_clauses_to_index(), and postgresGetForeignPaths().

◆ generate_join_implied_equalities()

List * generate_join_implied_equalities ( PlannerInfo root,
Relids  join_relids,
Relids  outer_relids,
RelOptInfo inner_rel,
SpecialJoinInfo sjinfo 
)

Definition at line 1550 of file equivclass.c.

1555{
1556 List *result = NIL;
1557 Relids inner_relids = inner_rel->relids;
1558 Relids nominal_inner_relids;
1559 Relids nominal_join_relids;
1560 Bitmapset *matching_ecs;
1561 int i;
1562
1563 /* If inner rel is a child, extra setup work is needed */
1564 if (IS_OTHER_REL(inner_rel))
1565 {
1567
1568 /* Fetch relid set for the topmost parent rel */
1569 nominal_inner_relids = inner_rel->top_parent_relids;
1570 /* ECs will be marked with the parent's relid, not the child's */
1571 nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1572 nominal_join_relids = add_outer_joins_to_relids(root,
1573 nominal_join_relids,
1574 sjinfo,
1575 NULL);
1576 }
1577 else
1578 {
1579 nominal_inner_relids = inner_relids;
1580 nominal_join_relids = join_relids;
1581 }
1582
1583 /*
1584 * Examine all potentially-relevant eclasses.
1585 *
1586 * If we are considering an outer join, we must include "join" clauses
1587 * that mention either input rel plus the outer join's relid; these
1588 * represent post-join filter clauses that have to be applied at this
1589 * join. We don't have infrastructure that would let us identify such
1590 * eclasses cheaply, so just fall back to considering all eclasses
1591 * mentioning anything in nominal_join_relids.
1592 *
1593 * At inner joins, we can be smarter: only consider eclasses mentioning
1594 * both input rels.
1595 */
1596 if (sjinfo && sjinfo->ojrelid != 0)
1597 matching_ecs = get_eclass_indexes_for_relids(root, nominal_join_relids);
1598 else
1599 matching_ecs = get_common_eclass_indexes(root, nominal_inner_relids,
1600 outer_relids);
1601
1602 i = -1;
1603 while ((i = bms_next_member(matching_ecs, i)) >= 0)
1604 {
1605 EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
1606 List *sublist = NIL;
1607
1608 /* ECs containing consts do not need any further enforcement */
1609 if (ec->ec_has_const)
1610 continue;
1611
1612 /* Single-member ECs won't generate any deductions */
1613 if (list_length(ec->ec_members) <= 1)
1614 continue;
1615
1616 /* Sanity check that this eclass overlaps the join */
1617 Assert(bms_overlap(ec->ec_relids, nominal_join_relids));
1618
1619 if (!ec->ec_broken)
1621 ec,
1622 join_relids,
1623 outer_relids,
1624 inner_relids);
1625
1626 /* Recover if we failed to generate required derived clauses */
1627 if (ec->ec_broken)
1629 ec,
1630 nominal_join_relids,
1631 outer_relids,
1632 nominal_inner_relids,
1633 inner_rel);
1634
1635 result = list_concat(result, sublist);
1636 }
1637
1638 return result;
1639}
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1721
static Bitmapset * get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
Definition: equivclass.c:3647
static List * generate_join_implied_equalities_broken(PlannerInfo *root, EquivalenceClass *ec, Relids nominal_join_relids, Relids outer_relids, Relids nominal_inner_relids, RelOptInfo *inner_rel)
Definition: equivclass.c:1899
Relids add_outer_joins_to_relids(PlannerInfo *root, Relids input_relids, SpecialJoinInfo *sjinfo, List **pushed_down_joins)
Definition: joinrels.c: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 1650 of file equivclass.c.

1655{
1656 List *result = NIL;
1657 Relids inner_relids = inner_rel->relids;
1658 Relids nominal_inner_relids;
1659 Relids nominal_join_relids;
1660 ListCell *lc;
1661
1662 /* If inner rel is a child, extra setup work is needed */
1663 if (IS_OTHER_REL(inner_rel))
1664 {
1666
1667 /* Fetch relid set for the topmost parent rel */
1668 nominal_inner_relids = inner_rel->top_parent_relids;
1669 /* ECs will be marked with the parent's relid, not the child's */
1670 nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1671 }
1672 else
1673 {
1674 nominal_inner_relids = inner_relids;
1675 nominal_join_relids = join_relids;
1676 }
1677
1678 foreach(lc, eclasses)
1679 {
1681 List *sublist = NIL;
1682
1683 /* ECs containing consts do not need any further enforcement */
1684 if (ec->ec_has_const)
1685 continue;
1686
1687 /* Single-member ECs won't generate any deductions */
1688 if (list_length(ec->ec_members) <= 1)
1689 continue;
1690
1691 /* We can quickly ignore any that don't overlap the join, too */
1692 if (!bms_overlap(ec->ec_relids, nominal_join_relids))
1693 continue;
1694
1695 if (!ec->ec_broken)
1697 ec,
1698 join_relids,
1699 outer_relids,
1700 inner_relids);
1701
1702 /* Recover if we failed to generate required derived clauses */
1703 if (ec->ec_broken)
1705 ec,
1706 nominal_join_relids,
1707 outer_relids,
1708 nominal_inner_relids,
1709 inner_rel);
1710
1711 result = list_concat(result, sublist);
1712 }
1713
1714 return result;
1715}

References Assert(), bms_is_empty, bms_overlap(), bms_union(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), IS_OTHER_REL, lfirst, list_concat(), list_length(), NIL, RelOptInfo::relids, root, and RelOptInfo::top_parent_relids.

Referenced by get_joinrel_parampathinfo().

◆ generate_partitionwise_join_paths()

void generate_partitionwise_join_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 4322 of file allpaths.c.

4323{
4324 List *live_children = NIL;
4325 int cnt_parts;
4326 int num_parts;
4327 RelOptInfo **part_rels;
4328
4329 /* Handle only join relations here. */
4330 if (!IS_JOIN_REL(rel))
4331 return;
4332
4333 /* We've nothing to do if the relation is not partitioned. */
4334 if (!IS_PARTITIONED_REL(rel))
4335 return;
4336
4337 /* The relation should have consider_partitionwise_join set. */
4339
4340 /* Guard against stack overflow due to overly deep partition hierarchy. */
4342
4343 num_parts = rel->nparts;
4344 part_rels = rel->part_rels;
4345
4346 /* Collect non-dummy child-joins. */
4347 for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
4348 {
4349 RelOptInfo *child_rel = part_rels[cnt_parts];
4350
4351 /* If it's been pruned entirely, it's certainly dummy. */
4352 if (child_rel == NULL)
4353 continue;
4354
4355 /* Make partitionwise join paths for this partitioned child-join. */
4357
4358 /* If we failed to make any path for this child, we must give up. */
4359 if (child_rel->pathlist == NIL)
4360 {
4361 /*
4362 * Mark the parent joinrel as unpartitioned so that later
4363 * functions treat it correctly.
4364 */
4365 rel->nparts = 0;
4366 return;
4367 }
4368
4369 /* Else, identify the cheapest path for it. */
4370 set_cheapest(child_rel);
4371
4372 /* Dummy children need not be scanned, so ignore those. */
4373 if (IS_DUMMY_REL(child_rel))
4374 continue;
4375
4376#ifdef OPTIMIZER_DEBUG
4377 pprint(child_rel);
4378#endif
4379
4380 live_children = lappend(live_children, child_rel);
4381 }
4382
4383 /* If all child-joins are dummy, parent join is also dummy. */
4384 if (!live_children)
4385 {
4386 mark_dummy_rel(rel);
4387 return;
4388 }
4389
4390 /* Build additional paths for this rel from child-join paths. */
4391 add_paths_to_append_rel(root, rel, live_children);
4392 list_free(live_children);
4393}
void generate_partitionwise_join_paths(PlannerInfo *root, RelOptInfo *rel)
Definition: allpaths.c:4322
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:2083
#define IS_PARTITIONED_REL(rel)
Definition: pathnodes.h:1089
void check_stack_depth(void)
Definition: stack_depth.c:95
bool consider_partitionwise_join
Definition: pathnodes.h:1026

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 3220 of file allpaths.c.

3221{
3222 ListCell *lc;
3223 double rows;
3224 double *rowsp = NULL;
3225 List *useful_pathkeys_list = NIL;
3226 Path *cheapest_partial_path = NULL;
3227
3228 /* If there are no partial paths, there's nothing to do here. */
3229 if (rel->partial_pathlist == NIL)
3230 return;
3231
3232 /* Should we override the rel's rowcount estimate? */
3233 if (override_rows)
3234 rowsp = &rows;
3235
3236 /* generate the regular gather (merge) paths */
3237 generate_gather_paths(root, rel, override_rows);
3238
3239 /* consider incremental sort for interesting orderings */
3240 useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel, true);
3241
3242 /* used for explicit (full) sort paths */
3243 cheapest_partial_path = linitial(rel->partial_pathlist);
3244
3245 /*
3246 * Consider sorted paths for each interesting ordering. We generate both
3247 * incremental and full sort.
3248 */
3249 foreach(lc, useful_pathkeys_list)
3250 {
3251 List *useful_pathkeys = lfirst(lc);
3252 ListCell *lc2;
3253 bool is_sorted;
3254 int presorted_keys;
3255
3256 foreach(lc2, rel->partial_pathlist)
3257 {
3258 Path *subpath = (Path *) lfirst(lc2);
3259 GatherMergePath *path;
3260
3261 is_sorted = pathkeys_count_contained_in(useful_pathkeys,
3262 subpath->pathkeys,
3263 &presorted_keys);
3264
3265 /*
3266 * We don't need to consider the case where a subpath is already
3267 * fully sorted because generate_gather_paths already creates a
3268 * gather merge path for every subpath that has pathkeys present.
3269 *
3270 * But since the subpath is already sorted, we know we don't need
3271 * to consider adding a sort (full or incremental) on top of it,
3272 * so we can continue here.
3273 */
3274 if (is_sorted)
3275 continue;
3276
3277 /*
3278 * Try at least sorting the cheapest path and also try
3279 * incrementally sorting any path which is partially sorted
3280 * already (no need to deal with paths which have presorted keys
3281 * when incremental sort is disabled unless it's the cheapest
3282 * input path).
3283 */
3284 if (subpath != cheapest_partial_path &&
3285 (presorted_keys == 0 || !enable_incremental_sort))
3286 continue;
3287
3288 /*
3289 * Consider regular sort for any path that's not presorted or if
3290 * incremental sort is disabled. We've no need to consider both
3291 * sort and incremental sort on the same path. We assume that
3292 * incremental sort is always faster when there are presorted
3293 * keys.
3294 *
3295 * This is not redundant with the gather paths created in
3296 * generate_gather_paths, because that doesn't generate ordered
3297 * output. Here we add an explicit sort to match the useful
3298 * ordering.
3299 */
3300 if (presorted_keys == 0 || !enable_incremental_sort)
3301 {
3303 rel,
3304 subpath,
3305 useful_pathkeys,
3306 -1.0);
3307 }
3308 else
3310 rel,
3311 subpath,
3312 useful_pathkeys,
3313 presorted_keys,
3314 -1);
3316 path = create_gather_merge_path(root, rel,
3317 subpath,
3318 rel->reltarget,
3319 subpath->pathkeys,
3320 NULL,
3321 rowsp);
3322
3323 add_path(rel, &path->path);
3324 }
3325 }
3326}
static List * get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel, bool require_parallel_safe)
Definition: allpaths.c:3152
void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
Definition: allpaths.c:3083
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:1791

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 736 of file equivclass.c.

744{
745 JoinDomain *jdomain;
746 Relids expr_relids;
747 EquivalenceClass *newec;
748 EquivalenceMember *newem;
749 ListCell *lc1;
750 MemoryContext oldcontext;
751
752 /*
753 * Ensure the expression exposes the correct type and collation.
754 */
755 expr = canonicalize_ec_expression(expr, opcintype, collation);
756
757 /*
758 * Since SortGroupClause nodes are top-level expressions (GROUP BY, ORDER
759 * BY, etc), they can be presumed to belong to the top JoinDomain.
760 */
761 jdomain = linitial_node(JoinDomain, root->join_domains);
762
763 /*
764 * Scan through the existing EquivalenceClasses for a match
765 */
766 foreach(lc1, root->eq_classes)
767 {
768 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
770 EquivalenceMember *cur_em;
771
772 /*
773 * Never match to a volatile EC, except when we are looking at another
774 * reference to the same volatile SortGroupClause.
775 */
776 if (cur_ec->ec_has_volatile &&
777 (sortref == 0 || sortref != cur_ec->ec_sortref))
778 continue;
779
780 if (collation != cur_ec->ec_collation)
781 continue;
782 if (!equal(opfamilies, cur_ec->ec_opfamilies))
783 continue;
784
785 setup_eclass_member_iterator(&it, cur_ec, rel);
786 while ((cur_em = eclass_member_iterator_next(&it)) != NULL)
787 {
788 /*
789 * Ignore child members unless they match the request.
790 */
791 if (cur_em->em_is_child &&
792 !bms_equal(cur_em->em_relids, rel))
793 continue;
794
795 /*
796 * Match constants only within the same JoinDomain (see
797 * optimizer/README).
798 */
799 if (cur_em->em_is_const && cur_em->em_jdomain != jdomain)
800 continue;
801
802 if (opcintype == cur_em->em_datatype &&
803 equal(expr, cur_em->em_expr))
804 return cur_ec; /* Match! */
805 }
806 }
807
808 /* No match; does caller want a NULL result? */
809 if (!create_it)
810 return NULL;
811
812 /*
813 * OK, build a new single-member EC
814 *
815 * Here, we must be sure that we construct the EC in the right context.
816 */
817 oldcontext = MemoryContextSwitchTo(root->planner_cxt);
818
819 newec = makeNode(EquivalenceClass);
820 newec->ec_opfamilies = list_copy(opfamilies);
821 newec->ec_collation = collation;
822 newec->ec_childmembers_size = 0;
823 newec->ec_members = NIL;
824 newec->ec_childmembers = NULL;
825 newec->ec_sources = NIL;
826 newec->ec_derives_list = NIL;
827 newec->ec_derives_hash = NULL;
828 newec->ec_relids = NULL;
829 newec->ec_has_const = false;
831 newec->ec_broken = false;
832 newec->ec_sortref = sortref;
833 newec->ec_min_security = UINT_MAX;
834 newec->ec_max_security = 0;
835 newec->ec_merged = NULL;
836
837 if (newec->ec_has_volatile && sortref == 0) /* should not happen */
838 elog(ERROR, "volatile EquivalenceClass has no sortref");
839
840 /*
841 * Get the precise set of relids appearing in the expression.
842 */
843 expr_relids = pull_varnos(root, (Node *) expr);
844
845 newem = add_eq_member(newec, copyObject(expr), expr_relids,
846 jdomain, opcintype);
847
848 /*
849 * add_eq_member doesn't check for volatile functions, set-returning
850 * functions, aggregates, or window functions, but such could appear in
851 * sort expressions; so we have to check whether its const-marking was
852 * correct.
853 */
854 if (newec->ec_has_const)
855 {
856 if (newec->ec_has_volatile ||
857 expression_returns_set((Node *) expr) ||
858 contain_agg_clause((Node *) expr) ||
860 {
861 newec->ec_has_const = false;
862 newem->em_is_const = false;
863 }
864 }
865
866 root->eq_classes = lappend(root->eq_classes, newec);
867
868 /*
869 * If EC merging is already complete, we have to mop up by adding the new
870 * EC to the eclass_indexes of the relation(s) mentioned in it.
871 */
872 if (root->ec_merging_done)
873 {
874 int ec_index = list_length(root->eq_classes) - 1;
875 int i = -1;
876
877 while ((i = bms_next_member(newec->ec_relids, i)) > 0)
878 {
879 RelOptInfo *rel = root->simple_rel_array[i];
880
881 /* ignore the RTE_GROUP RTE */
882 if (i == root->group_rtindex)
883 continue;
884
885 if (rel == NULL) /* must be an outer join */
886 {
887 Assert(bms_is_member(i, root->outer_join_rels));
888 continue;
889 }
890
892
894 ec_index);
895 }
896 }
897
898 MemoryContextSwitchTo(oldcontext);
899
900 return newec;
901}
bool contain_agg_clause(Node *clause)
Definition: clauses.c:179
bool contain_window_function(Node *clause)
Definition: clauses.c:216
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:539
static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, JoinDomain *jdomain, Oid datatype)
Definition: equivclass.c:628
bool expression_returns_set(Node *clause)
Definition: nodeFuncs.c:763
#define copyObject(obj)
Definition: nodes.h:230
#define makeNode(_type_)
Definition: nodes.h:161
#define linitial_node(type, l)
Definition: pg_list.h:181
Index ec_min_security
Definition: pathnodes.h:1466
Index ec_max_security
Definition: pathnodes.h:1467
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_childmembers, EquivalenceClass::ec_childmembers_size, EquivalenceClass::ec_collation, EquivalenceClass::ec_derives_hash, EquivalenceClass::ec_derives_list, EquivalenceClass::ec_has_const, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_max_security, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_min_security, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_relids, EquivalenceClass::ec_sortref, EquivalenceClass::ec_sources, RelOptInfo::eclass_indexes, eclass_member_iterator_next(), elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_jdomain, EquivalenceMember::em_relids, equal(), ERROR, expression_returns_set(), i, lappend(), lfirst, linitial_node, list_copy(), list_length(), makeNode, MemoryContextSwitchTo(), NIL, pull_varnos(), RELOPT_BASEREL, RelOptInfo::reloptkind, root, and setup_eclass_member_iterator().

Referenced by convert_subquery_pathkeys(), 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:1452

References Assert(), GroupByOrdering::clauses, compare_pathkeys(), enable_group_by_reordering, enable_incremental_sort, for_each_from, forboth, group_keys_reorder_by_pathkeys(), lappend(), lfirst_node, linitial_node, list_difference(), list_difference_ptr(), list_length(), makeNode, NIL, parse(), GroupByOrdering::pathkeys, Path::pathkeys, pathkeys_contained_in(), PATHKEYS_EQUAL, root, and SortGroupClause::tleSortGroupRef.

Referenced by add_paths_to_grouping_rel(), and create_partial_grouping_paths().

◆ has_relevant_eclass_joinclause()

bool has_relevant_eclass_joinclause ( PlannerInfo root,
RelOptInfo rel1 
)

Definition at line 3446 of file equivclass.c.

3447{
3448 Bitmapset *matched_ecs;
3449 int i;
3450
3451 /* Examine only eclasses mentioning rel1 */
3452 matched_ecs = get_eclass_indexes_for_relids(root, rel1->relids);
3453
3454 i = -1;
3455 while ((i = bms_next_member(matched_ecs, i)) >= 0)
3456 {
3457 EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
3458 i);
3459
3460 /*
3461 * Won't generate joinclauses if single-member (this test covers the
3462 * volatile case too)
3463 */
3464 if (list_length(ec->ec_members) <= 1)
3465 continue;
3466
3467 /*
3468 * Per the comment in have_relevant_eclass_joinclause, it's sufficient
3469 * to find an EC that mentions both this rel and some other rel.
3470 */
3471 if (!bms_is_subset(ec->ec_relids, rel1->relids))
3472 return true;
3473 }
3474
3475 return false;
3476}

References bms_is_subset(), bms_next_member(), EquivalenceClass::ec_members, EquivalenceClass::ec_relids, get_eclass_indexes_for_relids(), i, list_length(), list_nth(), RelOptInfo::relids, and root.

Referenced by build_join_rel().

◆ has_useful_pathkeys()

bool has_useful_pathkeys ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 2319 of file pathkeys.c.

2320{
2321 if (rel->joininfo != NIL || rel->has_eclass_joins)
2322 return true; /* might be able to use pathkeys for merging */
2323 if (root->group_pathkeys != NIL)
2324 return true; /* might be able to use pathkeys for grouping */
2325 if (root->query_pathkeys != NIL)
2326 return true; /* might be able to use them for ordering */
2327 return false; /* definitely useless */
2328}

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:3224

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:938

References bms_is_subset(), bms_overlap(), RelOptInfo::direct_lateral_relids, has_legal_joinclause(), JOIN_FULL, SpecialJoinInfo::jointype, lfirst, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, PlaceHolderInfo::ph_eval_at, RelOptInfo::relids, and root.

Referenced by desirable_join(), join_search_one_level(), and make_rels_by_clause_joins().

◆ have_relevant_eclass_joinclause()

bool have_relevant_eclass_joinclause ( PlannerInfo root,
RelOptInfo rel1,
RelOptInfo rel2 
)

Definition at line 3370 of file equivclass.c.

3372{
3373 Bitmapset *matching_ecs;
3374 int i;
3375
3376 /*
3377 * Examine only eclasses mentioning both rel1 and rel2.
3378 *
3379 * Note that we do not consider the possibility of an eclass generating
3380 * "join" clauses that mention just one of the rels plus an outer join
3381 * that could be formed from them. Although such clauses must be
3382 * correctly enforced when we form the outer join, they don't seem like
3383 * sufficient reason to prioritize this join over other ones. The join
3384 * ordering rules will force the join to be made when necessary.
3385 */
3386 matching_ecs = get_common_eclass_indexes(root, rel1->relids,
3387 rel2->relids);
3388
3389 i = -1;
3390 while ((i = bms_next_member(matching_ecs, i)) >= 0)
3391 {
3392 EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
3393 i);
3394
3395 /*
3396 * Sanity check that get_common_eclass_indexes gave only ECs
3397 * containing both rels.
3398 */
3399 Assert(bms_overlap(rel1->relids, ec->ec_relids));
3400 Assert(bms_overlap(rel2->relids, ec->ec_relids));
3401
3402 /*
3403 * Won't generate joinclauses if single-member (this test covers the
3404 * volatile case too)
3405 */
3406 if (list_length(ec->ec_members) <= 1)
3407 continue;
3408
3409 /*
3410 * We do not need to examine the individual members of the EC, because
3411 * all that we care about is whether each rel overlaps the relids of
3412 * at least one member, and get_common_eclass_indexes() and the single
3413 * member check above are sufficient to prove that. (As with
3414 * have_relevant_joinclause(), it is not necessary that the EC be able
3415 * to form a joinclause relating exactly the two given rels, only that
3416 * it be able to form a joinclause mentioning both, and this will
3417 * surely be true if both of them overlap ec_relids.)
3418 *
3419 * Note we don't test ec_broken; if we did, we'd need a separate code
3420 * path to look through ec_sources. Checking the membership anyway is
3421 * OK as a possibly-overoptimistic heuristic.
3422 *
3423 * We don't test ec_has_const either, even though a const eclass won't
3424 * generate real join clauses. This is because if we had "WHERE a.x =
3425 * b.y and a.x = 42", it is worth considering a join between a and b,
3426 * since the join result is likely to be small even though it'll end
3427 * up being an unqualified nestloop.
3428 */
3429
3430 return true;
3431 }
3432
3433 return false;
3434}

References Assert(), bms_next_member(), bms_overlap(), EquivalenceClass::ec_members, EquivalenceClass::ec_relids, get_common_eclass_indexes(), i, list_length(), list_nth(), RelOptInfo::relids, and root.

Referenced by have_relevant_joinclause().

◆ indexcol_is_bool_constant_for_query()

bool indexcol_is_bool_constant_for_query ( PlannerInfo root,
IndexOptInfo index,
int  indexcol 
)

Definition at line 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:2791
static IndexClause * match_boolean_index_clause(PlannerInfo *root, RestrictInfo *rinfo, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:2816

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:3037
Relids syn_lefthand
Definition: pathnodes.h:3032
List * semi_rhs_exprs
Definition: pathnodes.h:3045
Relids syn_righthand
Definition: pathnodes.h:3033
Relids commute_below_r
Definition: pathnodes.h:3039
List * semi_operators
Definition: pathnodes.h:3044

References SpecialJoinInfo::commute_above_l, SpecialJoinInfo::commute_above_r, SpecialJoinInfo::commute_below_l, SpecialJoinInfo::commute_below_r, JOIN_INNER, SpecialJoinInfo::jointype, SpecialJoinInfo::lhs_strict, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, SpecialJoinInfo::ojrelid, SpecialJoinInfo::semi_can_btree, SpecialJoinInfo::semi_can_hash, SpecialJoinInfo::semi_operators, SpecialJoinInfo::semi_rhs_exprs, SpecialJoinInfo::syn_lefthand, and SpecialJoinInfo::syn_righthand.

Referenced by approx_tuple_count(), build_child_join_sjinfo(), compute_semi_anti_join_factors(), consider_new_or_clause(), and make_join_rel().

◆ initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1463 of file pathkeys.c.

1464{
1465 Expr *clause = restrictinfo->clause;
1466 Oid lefttype,
1467 righttype;
1468
1469 /* Should be a mergeclause ... */
1470 Assert(restrictinfo->mergeopfamilies != NIL);
1471 /* ... with links not yet set */
1472 Assert(restrictinfo->left_ec == NULL);
1473 Assert(restrictinfo->right_ec == NULL);
1474
1475 /* Need the declared input types of the operator */
1476 op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1477
1478 /* Find or create a matching EquivalenceClass for each side */
1479 restrictinfo->left_ec =
1481 (Expr *) get_leftop(clause),
1482 restrictinfo->mergeopfamilies,
1483 lefttype,
1484 ((OpExpr *) clause)->inputcollid,
1485 0,
1486 NULL,
1487 true);
1488 restrictinfo->right_ec =
1490 (Expr *) get_rightop(clause),
1491 restrictinfo->mergeopfamilies,
1492 righttype,
1493 ((OpExpr *) clause)->inputcollid,
1494 0,
1495 NULL,
1496 true);
1497}
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1498
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 3550 of file equivclass.c.

3551{
3552 EquivalenceClass *parent_ec = rinfo->parent_ec;
3553 ListCell *lc;
3554
3555 /* Fail if it's not a potentially-redundant clause from some EC */
3556 if (parent_ec == NULL)
3557 return false;
3558
3559 foreach(lc, clauselist)
3560 {
3561 RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
3562
3563 if (otherrinfo->parent_ec == parent_ec)
3564 return true;
3565 }
3566
3567 return false;
3568}

References lfirst.

Referenced by create_tidscan_plan().

◆ is_redundant_with_indexclauses()

bool is_redundant_with_indexclauses ( RestrictInfo rinfo,
List indexclauses 
)

Definition at line 3577 of file equivclass.c.

3578{
3579 EquivalenceClass *parent_ec = rinfo->parent_ec;
3580 ListCell *lc;
3581
3582 foreach(lc, indexclauses)
3583 {
3584 IndexClause *iclause = lfirst_node(IndexClause, lc);
3585 RestrictInfo *otherrinfo = iclause->rinfo;
3586
3587 /* If indexclause is lossy, it won't enforce the condition exactly */
3588 if (iclause->lossy)
3589 continue;
3590
3591 /* Match if it's same clause (pointer equality should be enough) */
3592 if (rinfo == otherrinfo)
3593 return true;
3594 /* Match if derived from same EC */
3595 if (parent_ec && otherrinfo->parent_ec == parent_ec)
3596 return true;
3597
3598 /*
3599 * No need to look at the derived clauses in iclause->indexquals; they
3600 * couldn't match if the parent clause didn't.
3601 */
3602 }
3603
3604 return false;
3605}
struct RestrictInfo * rinfo
Definition: pathnodes.h:1895

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,
CompareType  cmptype,
bool  nulls_first 
)

Definition at line 56 of file pathkeys.c.

59{
60 PathKey *pk;
61 ListCell *lc;
62 MemoryContext oldcontext;
63
64 /* Can't make canonical pathkeys if the set of ECs might still change */
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 cmptype == pk->pk_cmptype &&
78 nulls_first == pk->pk_nulls_first)
79 return pk;
80 }
81
82 /*
83 * Be sure canonical pathkeys are allocated in the main planning context.
84 * Not an issue in normal planning, but it is for GEQO.
85 */
86 oldcontext = MemoryContextSwitchTo(root->planner_cxt);
87
88 pk = makeNode(PathKey);
89 pk->pk_eclass = eclass;
90 pk->pk_opfamily = opfamily;
91 pk->pk_cmptype = cmptype;
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_cmptype, PathKey::pk_nulls_first, PathKey::pk_opfamily, and root.

Referenced by convert_subquery_pathkeys(), get_useful_pathkeys_for_relation(), make_inner_pathkeys_for_merge(), make_pathkey_from_sortinfo(), and select_outer_pathkeys_for_merge().

◆ make_inner_pathkeys_for_merge()

List * make_inner_pathkeys_for_merge ( PlannerInfo root,
List mergeclauses,
List outer_pathkeys 
)

Definition at line 1858 of file pathkeys.c.

1861{
1862 List *pathkeys = NIL;
1863 EquivalenceClass *lastoeclass;
1864 PathKey *opathkey;
1865 ListCell *lc;
1866 ListCell *lop;
1867
1868 lastoeclass = NULL;
1869 opathkey = NULL;
1870 lop = list_head(outer_pathkeys);
1871
1872 foreach(lc, mergeclauses)
1873 {
1874 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1875 EquivalenceClass *oeclass;
1876 EquivalenceClass *ieclass;
1877 PathKey *pathkey;
1878
1880
1881 if (rinfo->outer_is_left)
1882 {
1883 oeclass = rinfo->left_ec;
1884 ieclass = rinfo->right_ec;
1885 }
1886 else
1887 {
1888 oeclass = rinfo->right_ec;
1889 ieclass = rinfo->left_ec;
1890 }
1891
1892 /* outer eclass should match current or next pathkeys */
1893 /* we check this carefully for debugging reasons */
1894 if (oeclass != lastoeclass)
1895 {
1896 if (!lop)
1897 elog(ERROR, "too few pathkeys for mergeclauses");
1898 opathkey = (PathKey *) lfirst(lop);
1899 lop = lnext(outer_pathkeys, lop);
1900 lastoeclass = opathkey->pk_eclass;
1901 if (oeclass != lastoeclass)
1902 elog(ERROR, "outer pathkeys do not match mergeclause");
1903 }
1904
1905 /*
1906 * Often, we'll have same EC on both sides, in which case the outer
1907 * pathkey is also canonical for the inner side, and we can skip a
1908 * useless search.
1909 */
1910 if (ieclass == oeclass)
1911 pathkey = opathkey;
1912 else
1913 pathkey = make_canonical_pathkey(root,
1914 ieclass,
1915 opathkey->pk_opfamily,
1916 opathkey->pk_cmptype,
1917 opathkey->pk_nulls_first);
1918
1919 /*
1920 * Don't generate redundant pathkeys (which can happen if multiple
1921 * mergeclauses refer to the same EC). Because we do this, the output
1922 * pathkey list isn't necessarily ordered like the mergeclauses, which
1923 * complicates life for create_mergejoin_plan(). But if we didn't,
1924 * we'd have a noncanonical sort key list, which would be bad; for one
1925 * reason, it certainly wouldn't match any available sort order for
1926 * the input relation.
1927 */
1928 if (!pathkey_is_redundant(pathkey, pathkeys))
1929 pathkeys = lappend(pathkeys, pathkey);
1930 }
1931
1932 return pathkeys;
1933}

References elog, ERROR, lappend(), lfirst, list_head(), lnext(), make_canonical_pathkey(), NIL, pathkey_is_redundant(), PathKey::pk_cmptype, PathKey::pk_nulls_first, PathKey::pk_opfamily, root, and update_mergeclause_eclasses().

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

◆ make_join_rel()

RelOptInfo * make_join_rel ( PlannerInfo root,
RelOptInfo rel1,
RelOptInfo rel2 
)

Definition at line 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:3336
unsigned int Index
Definition: c.h:585
BlockNumber pages
Definition: pathnodes.h:975

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 1336 of file pathkeys.c.

1339{
1340 List *result;
1341 bool sortable;
1342
1344 &sortclauses,
1345 tlist,
1346 false,
1347 false,
1348 &sortable,
1349 false);
1350 /* It's caller error if not all clauses were sortable */
1351 Assert(sortable);
1352 return result;
1353}
List * make_pathkeys_for_sortclauses_extended(PlannerInfo *root, List **sortclauses, List *tlist, bool remove_redundant, bool remove_group_rtindex, bool *sortable, bool set_ec_sortref)
Definition: pathkeys.c:1381

References Assert(), make_pathkeys_for_sortclauses_extended(), and root.

Referenced by adjust_group_pathkeys_for_groupagg(), generate_nonunion_paths(), generate_union_paths(), grouping_planner(), make_pathkeys_for_window(), minmax_qp_callback(), and standard_qp_callback().

◆ make_pathkeys_for_sortclauses_extended()

List * make_pathkeys_for_sortclauses_extended ( PlannerInfo root,
List **  sortclauses,
List tlist,
bool  remove_redundant,
bool  remove_group_rtindex,
bool *  sortable,
bool  set_ec_sortref 
)

Definition at line 1381 of file pathkeys.c.

1388{
1389 List *pathkeys = NIL;
1390 ListCell *l;
1391
1392 *sortable = true;
1393 foreach(l, *sortclauses)
1394 {
1395 SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
1396 Expr *sortkey;
1397 PathKey *pathkey;
1398
1399 sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
1400 if (!OidIsValid(sortcl->sortop))
1401 {
1402 *sortable = false;
1403 continue;
1404 }
1405 if (remove_group_rtindex)
1406 {
1407 Assert(root->group_rtindex > 0);
1408 sortkey = (Expr *)
1409 remove_nulling_relids((Node *) sortkey,
1410 bms_make_singleton(root->group_rtindex),
1411 NULL);
1412 }
1414 sortkey,
1415 sortcl->sortop,
1416 sortcl->reverse_sort,
1417 sortcl->nulls_first,
1418 sortcl->tleSortGroupRef,
1419 true);
1420 if (pathkey->pk_eclass->ec_sortref == 0 && set_ec_sortref)
1421 {
1422 /*
1423 * Copy the sortref if it hasn't been set yet. That may happen if
1424 * the EquivalenceClass was constructed from a WHERE clause, i.e.
1425 * it doesn't have a target reference at all.
1426 */
1427 pathkey->pk_eclass->ec_sortref = sortcl->tleSortGroupRef;
1428 }
1429
1430 /* Canonical form eliminates redundant ordering keys */
1431 if (!pathkey_is_redundant(pathkey, pathkeys))
1432 pathkeys = lappend(pathkeys, pathkey);
1433 else if (remove_redundant)
1434 *sortclauses = foreach_delete_current(*sortclauses, l);
1435 }
1436 return pathkeys;
1437}
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:738
Cardinality rows
Definition: pathnodes.h:904

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 2710 of file equivclass.c.

2713{
2714 Index var1varno = fkinfo->con_relid;
2715 AttrNumber var1attno = fkinfo->conkey[colno];
2716 Index var2varno = fkinfo->ref_relid;
2717 AttrNumber var2attno = fkinfo->confkey[colno];
2718 Oid eqop = fkinfo->conpfeqop[colno];
2719 RelOptInfo *rel1 = root->simple_rel_array[var1varno];
2720 RelOptInfo *rel2 = root->simple_rel_array[var2varno];
2721 List *opfamilies = NIL; /* compute only if needed */
2722 Bitmapset *matching_ecs;
2723 int i;
2724
2725 /* Consider only eclasses mentioning both relations */
2726 Assert(root->ec_merging_done);
2727 Assert(IS_SIMPLE_REL(rel1));
2728 Assert(IS_SIMPLE_REL(rel2));
2729 matching_ecs = bms_intersect(rel1->eclass_indexes,
2730 rel2->eclass_indexes);
2731
2732 i = -1;
2733 while ((i = bms_next_member(matching_ecs, i)) >= 0)
2734 {
2735 EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
2736 i);
2737 EquivalenceMember *item1_em = NULL;
2738 EquivalenceMember *item2_em = NULL;
2739 ListCell *lc2;
2740
2741 /* Never match to a volatile EC */
2742 if (ec->ec_has_volatile)
2743 continue;
2744
2745 /*
2746 * It's okay to consider "broken" ECs here, see exprs_known_equal.
2747 * Ignore children here.
2748 */
2749 foreach(lc2, ec->ec_members)
2750 {
2752 Var *var;
2753
2754 /* Child members should not exist in ec_members */
2755 Assert(!em->em_is_child);
2756
2757 /* EM must be a Var, possibly with RelabelType */
2758 var = (Var *) em->em_expr;
2759 while (var && IsA(var, RelabelType))
2760 var = (Var *) ((RelabelType *) var)->arg;
2761 if (!(var && IsA(var, Var)))
2762 continue;
2763
2764 /* Match? */
2765 if (var->varno == var1varno && var->varattno == var1attno)
2766 item1_em = em;
2767 else if (var->varno == var2varno && var->varattno == var2attno)
2768 item2_em = em;
2769
2770 /* Have we found both PK and FK column in this EC? */
2771 if (item1_em && item2_em)
2772 {
2773 /*
2774 * Succeed if eqop matches EC's opfamilies. We could test
2775 * this before scanning the members, but it's probably cheaper
2776 * to test for member matches first.
2777 */
2778 if (opfamilies == NIL) /* compute if we didn't already */
2779 opfamilies = get_mergejoin_opfamilies(eqop);
2780 if (equal(opfamilies, ec->ec_opfamilies))
2781 {
2782 fkinfo->eclass[colno] = ec;
2783 fkinfo->fk_eclass_member[colno] = item2_em;
2784 return ec;
2785 }
2786 /* Otherwise, done with this EC, move on to the next */
2787 break;
2788 }
2789 }
2790 }
2791 return NULL;
2792}
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:434
while(p+4<=pend)
struct EquivalenceClass * eclass[INDEX_MAX_KEYS]
Definition: pathnodes.h:1287
struct EquivalenceMember * fk_eclass_member[INDEX_MAX_KEYS]
Definition: pathnodes.h:1289
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}
void * arg

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 179 of file equivclass.c.

182{
183 RestrictInfo *restrictinfo = *p_restrictinfo;
184 Expr *clause = restrictinfo->clause;
185 Oid opno,
186 collation,
187 item1_type,
188 item2_type;
189 Expr *item1;
190 Expr *item2;
191 Relids item1_relids,
192 item2_relids;
193 List *opfamilies;
194 EquivalenceClass *ec1,
195 *ec2;
197 *em2;
198 ListCell *lc1;
199 int ec2_idx;
200
201 /* Should not already be marked as having generated an eclass */
202 Assert(restrictinfo->left_ec == NULL);
203 Assert(restrictinfo->right_ec == NULL);
204
205 /* Reject if it is potentially postponable by security considerations */
206 if (restrictinfo->security_level > 0 && !restrictinfo->leakproof)
207 return false;
208
209 /* Extract info from given clause */
210 Assert(is_opclause(clause));
211 opno = ((OpExpr *) clause)->opno;
212 collation = ((OpExpr *) clause)->inputcollid;
213 item1 = (Expr *) get_leftop(clause);
214 item2 = (Expr *) get_rightop(clause);
215 item1_relids = restrictinfo->left_relids;
216 item2_relids = restrictinfo->right_relids;
217
218 /*
219 * Ensure both input expressions expose the desired collation (their types
220 * should be OK already); see comments for canonicalize_ec_expression.
221 */
222 item1 = canonicalize_ec_expression(item1,
223 exprType((Node *) item1),
224 collation);
225 item2 = canonicalize_ec_expression(item2,
226 exprType((Node *) item2),
227 collation);
228
229 /*
230 * Clauses of the form X=X cannot be translated into EquivalenceClasses.
231 * We'd either end up with a single-entry EC, losing the knowledge that
232 * the clause was present at all, or else make an EC with duplicate
233 * entries, causing other issues.
234 */
235 if (equal(item1, item2))
236 {
237 /*
238 * If the operator is strict, then the clause can be treated as just
239 * "X IS NOT NULL". (Since we know we are considering a top-level
240 * qual, we can ignore the difference between FALSE and NULL results.)
241 * It's worth making the conversion because we'll typically get a much
242 * better selectivity estimate than we would for X=X.
243 *
244 * If the operator is not strict, we can't be sure what it will do
245 * with NULLs, so don't attempt to optimize it.
246 */
247 set_opfuncid((OpExpr *) clause);
248 if (func_strict(((OpExpr *) clause)->opfuncid))
249 {
250 NullTest *ntest = makeNode(NullTest);
251
252 ntest->arg = item1;
253 ntest->nulltesttype = IS_NOT_NULL;
254 ntest->argisrow = false; /* correct even if composite arg */
255 ntest->location = -1;
256
257 *p_restrictinfo =
259 (Expr *) ntest,
260 restrictinfo->is_pushed_down,
261 restrictinfo->has_clone,
262 restrictinfo->is_clone,
263 restrictinfo->pseudoconstant,
264 restrictinfo->security_level,
265 NULL,
266 restrictinfo->incompatible_relids,
267 restrictinfo->outer_relids);
268 }
269 return false;
270 }
271
272 /*
273 * We use the declared input types of the operator, not exprType() of the
274 * inputs, as the nominal datatypes for opfamily lookup. This presumes
275 * that btree operators are always registered with amoplefttype and
276 * amoprighttype equal to their declared input types. We will need this
277 * info anyway to build EquivalenceMember nodes, and by extracting it now
278 * we can use type comparisons to short-circuit some equal() tests.
279 */
280 op_input_types(opno, &item1_type, &item2_type);
281
282 opfamilies = restrictinfo->mergeopfamilies;
283
284 /*
285 * Sweep through the existing EquivalenceClasses looking for matches to
286 * item1 and item2. These are the possible outcomes:
287 *
288 * 1. We find both in the same EC. The equivalence is already known, so
289 * there's nothing to do.
290 *
291 * 2. We find both in different ECs. Merge the two ECs together.
292 *
293 * 3. We find just one. Add the other to its EC.
294 *
295 * 4. We find neither. Make a new, two-entry EC.
296 *
297 * Note: since all ECs are built through this process or the similar
298 * search in get_eclass_for_sort_expr(), it's impossible that we'd match
299 * an item in more than one existing nonvolatile EC. So it's okay to stop
300 * at the first match.
301 */
302 ec1 = ec2 = NULL;
303 em1 = em2 = NULL;
304 ec2_idx = -1;
305 foreach(lc1, root->eq_classes)
306 {
307 EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
308 ListCell *lc2;
309
310 /* Never match to a volatile EC */
311 if (cur_ec->ec_has_volatile)
312 continue;
313
314 /*
315 * The collation has to match; check this first since it's cheaper
316 * than the opfamily comparison.
317 */
318 if (collation != cur_ec->ec_collation)
319 continue;
320
321 /*
322 * A "match" requires matching sets of btree opfamilies. Use of
323 * equal() for this test has implications discussed in the comments
324 * for get_mergejoin_opfamilies().
325 */
326 if (!equal(opfamilies, cur_ec->ec_opfamilies))
327 continue;
328
329 /* We don't expect any children yet */
330 Assert(cur_ec->ec_childmembers == NULL);
331
332 foreach(lc2, cur_ec->ec_members)
333 {
334 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
335
336 /* Child members should not exist in ec_members */
337 Assert(!cur_em->em_is_child);
338
339 /*
340 * Match constants only within the same JoinDomain (see
341 * optimizer/README).
342 */
343 if (cur_em->em_is_const && cur_em->em_jdomain != jdomain)
344 continue;
345
346 if (!ec1 &&
347 item1_type == cur_em->em_datatype &&
348 equal(item1, cur_em->em_expr))
349 {
350 ec1 = cur_ec;
351 em1 = cur_em;
352 if (ec2)
353 break;
354 }
355
356 if (!ec2 &&
357 item2_type == cur_em->em_datatype &&
358 equal(item2, cur_em->em_expr))
359 {
360 ec2 = cur_ec;
361 ec2_idx = foreach_current_index(lc1);
362 em2 = cur_em;
363 if (ec1)
364 break;
365 }
366 }
367
368 if (ec1 && ec2)
369 break;
370 }
371
372 /* Sweep finished, what did we find? */
373
374 if (ec1 && ec2)
375 {
376 /* If case 1, nothing to do, except add to sources */
377 if (ec1 == ec2)
378 {
379 ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
381 restrictinfo->security_level);
383 restrictinfo->security_level);
384 /* mark the RI as associated with this eclass */
385 restrictinfo->left_ec = ec1;
386 restrictinfo->right_ec = ec1;
387 /* mark the RI as usable with this pair of EMs */
388 restrictinfo->left_em = em1;
389 restrictinfo->right_em = em2;
390 return true;
391 }
392
393 /*
394 * Case 2: need to merge ec1 and ec2. This should never happen after
395 * the ECs have reached canonical state; otherwise, pathkeys could be
396 * rendered non-canonical by the merge, and relation eclass indexes
397 * would get broken by removal of an eq_classes list entry.
398 */
399 if (root->ec_merging_done)
400 elog(ERROR, "too late to merge equivalence classes");
401
402 /*
403 * We add ec2's items to ec1, then set ec2's ec_merged link to point
404 * to ec1 and remove ec2 from the eq_classes list. We cannot simply
405 * delete ec2 because that could leave dangling pointers in existing
406 * PathKeys. We leave it behind with a link so that the merged EC can
407 * be found.
408 */
409 ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
410 ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
411
412 /*
413 * Appends ec2's derived clauses to ec1->ec_derives_list and adds them
414 * to ec1->ec_derives_hash if present.
415 */
417 ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
418 ec1->ec_has_const |= ec2->ec_has_const;
419 /* can't need to set has_volatile */
421 ec2->ec_min_security);
423 ec2->ec_max_security);
424 ec2->ec_merged = ec1;
425 root->eq_classes = list_delete_nth_cell(root->eq_classes, ec2_idx);
426 /* just to avoid debugging confusion w/ dangling pointers: */
427 ec2->ec_members = NIL;
428 ec2->ec_sources = NIL;
430 ec2->ec_relids = NULL;
431 ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
433 restrictinfo->security_level);
435 restrictinfo->security_level);
436 /* mark the RI as associated with this eclass */
437 restrictinfo->left_ec = ec1;
438 restrictinfo->right_ec = ec1;
439 /* mark the RI as usable with this pair of EMs */
440 restrictinfo->left_em = em1;
441 restrictinfo->right_em = em2;
442 }
443 else if (ec1)
444 {
445 /* Case 3: add item2 to ec1 */
446 em2 = add_eq_member(ec1, item2, item2_relids,
447 jdomain, item2_type);
448 ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
450 restrictinfo->security_level);
452 restrictinfo->security_level);
453 /* mark the RI as associated with this eclass */
454 restrictinfo->left_ec = ec1;
455 restrictinfo->right_ec = ec1;
456 /* mark the RI as usable with this pair of EMs */
457 restrictinfo->left_em = em1;
458 restrictinfo->right_em = em2;
459 }
460 else if (ec2)
461 {
462 /* Case 3: add item1 to ec2 */
463 em1 = add_eq_member(ec2, item1, item1_relids,
464 jdomain, item1_type);
465 ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
467 restrictinfo->security_level);
469 restrictinfo->security_level);
470 /* mark the RI as associated with this eclass */
471 restrictinfo->left_ec = ec2;
472 restrictinfo->right_ec = ec2;
473 /* mark the RI as usable with this pair of EMs */
474 restrictinfo->left_em = em1;
475 restrictinfo->right_em = em2;
476 }
477 else
478 {
479 /* Case 4: make a new, two-entry EC */
481
482 ec->ec_opfamilies = opfamilies;
483 ec->ec_collation = collation;
484 ec->ec_childmembers_size = 0;
485 ec->ec_members = NIL;
486 ec->ec_childmembers = NULL;
487 ec->ec_sources = list_make1(restrictinfo);
488 ec->ec_derives_list = NIL;
489 ec->ec_derives_hash = NULL;
490 ec->ec_relids = NULL;
491 ec->ec_has_const = false;
492 ec->ec_has_volatile = false;
493 ec->ec_broken = false;
494 ec->ec_sortref = 0;
495 ec->ec_min_security = restrictinfo->security_level;
496 ec->ec_max_security = restrictinfo->security_level;
497 ec->ec_merged = NULL;
498 em1 = add_eq_member(ec, item1, item1_relids,
499 jdomain, item1_type);
500 em2 = add_eq_member(ec, item2, item2_relids,
501 jdomain, item2_type);
502
503 root->eq_classes = lappend(root->eq_classes, ec);
504
505 /* mark the RI as associated with this eclass */
506 restrictinfo->left_ec = ec;
507 restrictinfo->right_ec = ec;
508 /* mark the RI as usable with this pair of EMs */
509 restrictinfo->left_em = em1;
510 restrictinfo->right_em = em2;
511 }
512
513 return true;
514}
void ec_clear_derived_clauses(EquivalenceClass *ec)
Definition: equivclass.c:3831
static void ec_add_derived_clauses(EquivalenceClass *ec, List *clauses)
Definition: equivclass.c:3733
List * list_delete_nth_cell(List *list, int n)
Definition: list.c:767
bool func_strict(Oid funcid)
Definition: lsyscache.c:1901
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:2703
Index security_level
Definition: pathnodes.h:2722
Relids outer_relids
Definition: pathnodes.h:2737
Relids incompatible_relids
Definition: pathnodes.h:2734
bool has_clone
Definition: pathnodes.h:2712

References add_eq_member(), NullTest::arg, Assert(), bms_join(), canonicalize_ec_expression(), RestrictInfo::clause, ec_add_derived_clauses(), EquivalenceClass::ec_broken, EquivalenceClass::ec_childmembers, EquivalenceClass::ec_childmembers_size, ec_clear_derived_clauses(), EquivalenceClass::ec_collation, EquivalenceClass::ec_derives_hash, EquivalenceClass::ec_derives_list, EquivalenceClass::ec_has_const, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_max_security, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_min_security, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_relids, EquivalenceClass::ec_sortref, EquivalenceClass::ec_sources, elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_jdomain, equal(), ERROR, exprType(), foreach_current_index, func_strict(), get_leftop(), get_rightop(), RestrictInfo::has_clone, RestrictInfo::incompatible_relids, RestrictInfo::is_clone, IS_NOT_NULL, is_opclause(), RestrictInfo::is_pushed_down, lappend(), lfirst, list_concat(), list_delete_nth_cell(), list_make1, NullTest::location, make_restrictinfo(), makeNode, Max, Min, NIL, NullTest::nulltesttype, op_input_types(), RestrictInfo::outer_relids, root, RestrictInfo::security_level, and set_opfuncid().

Referenced by distribute_qual_to_rels(), reconsider_full_join_clause(), and reconsider_outer_join_clause().

◆ rebuild_eclass_attr_needed()

void rebuild_eclass_attr_needed ( PlannerInfo root)

Definition at line 2574 of file equivclass.c.

2575{
2576 ListCell *lc;
2577
2578 foreach(lc, root->eq_classes)
2579 {
2581
2582 /*
2583 * We don't expect any EC child members to exist at this point. Ensure
2584 * that's the case, otherwise, we might be getting asked to do
2585 * something this function hasn't been coded for.
2586 */
2587 Assert(ec->ec_childmembers == NULL);
2588
2589 /* Need do anything only for a multi-member, no-const EC. */
2590 if (list_length(ec->ec_members) > 1 && !ec->ec_has_const)
2591 {
2592 ListCell *lc2;
2593
2594 foreach(lc2, ec->ec_members)
2595 {
2596 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
2597 List *vars = pull_var_clause((Node *) cur_em->em_expr,
2601
2603 list_free(vars);
2604 }
2605 }
2606 }
2607}
void add_vars_to_attr_needed(PlannerInfo *root, List *vars, Relids where_needed)
Definition: initsplan.c:353
#define PVC_RECURSE_AGGREGATES
Definition: optimizer.h:193
#define PVC_RECURSE_WINDOWFUNCS
Definition: optimizer.h:195
Definition: regcomp.c:282

References add_vars_to_attr_needed(), Assert(), EquivalenceClass::ec_childmembers, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, EquivalenceMember::em_expr, lfirst, list_free(), list_length(), pull_var_clause(), PVC_INCLUDE_PLACEHOLDERS, PVC_RECURSE_AGGREGATES, PVC_RECURSE_WINDOWFUNCS, and root.

Referenced by remove_leftjoinrel_from_query(), and remove_self_join_rel().

◆ reconsider_outer_join_clauses()

void reconsider_outer_join_clauses ( PlannerInfo root)

Definition at line 2135 of file equivclass.c.

2136{
2137 bool found;
2138 ListCell *cell;
2139
2140 /* Outer loop repeats until we find no more deductions */
2141 do
2142 {
2143 found = false;
2144
2145 /* Process the LEFT JOIN clauses */
2146 foreach(cell, root->left_join_clauses)
2147 {
2148 OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2149
2150 if (reconsider_outer_join_clause(root, ojcinfo, true))
2151 {
2152 RestrictInfo *rinfo = ojcinfo->rinfo;
2153
2154 found = true;
2155 /* remove it from the list */
2156 root->left_join_clauses =
2157 foreach_delete_current(root->left_join_clauses, cell);
2158 /* throw back a dummy replacement clause (see notes above) */
2159 rinfo = make_restrictinfo(root,
2160 (Expr *) makeBoolConst(true, false),
2161 rinfo->is_pushed_down,
2162 rinfo->has_clone,
2163 rinfo->is_clone,
2164 false, /* pseudoconstant */
2165 0, /* security_level */
2166 rinfo->required_relids,
2167 rinfo->incompatible_relids,
2168 rinfo->outer_relids);
2170 }
2171 }
2172
2173 /* Process the RIGHT JOIN clauses */
2174 foreach(cell, root->right_join_clauses)
2175 {
2176 OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2177
2178 if (reconsider_outer_join_clause(root, ojcinfo, false))
2179 {
2180 RestrictInfo *rinfo = ojcinfo->rinfo;
2181
2182 found = true;
2183 /* remove it from the list */
2184 root->right_join_clauses =
2185 foreach_delete_current(root->right_join_clauses, cell);
2186 /* throw back a dummy replacement clause (see notes above) */
2187 rinfo = make_restrictinfo(root,
2188 (Expr *) makeBoolConst(true, false),
2189 rinfo->is_pushed_down,
2190 rinfo->has_clone,
2191 rinfo->is_clone,
2192 false, /* pseudoconstant */
2193 0, /* security_level */
2194 rinfo->required_relids,
2195 rinfo->incompatible_relids,
2196 rinfo->outer_relids);
2198 }
2199 }
2200
2201 /* Process the FULL JOIN clauses */
2202 foreach(cell, root->full_join_clauses)
2203 {
2204 OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2205
2206 if (reconsider_full_join_clause(root, ojcinfo))
2207 {
2208 RestrictInfo *rinfo = ojcinfo->rinfo;
2209
2210 found = true;
2211 /* remove it from the list */
2212 root->full_join_clauses =
2213 foreach_delete_current(root->full_join_clauses, cell);
2214 /* throw back a dummy replacement clause (see notes above) */
2215 rinfo = make_restrictinfo(root,
2216 (Expr *) makeBoolConst(true, false),
2217 rinfo->is_pushed_down,
2218 rinfo->has_clone,
2219 rinfo->is_clone,
2220 false, /* pseudoconstant */
2221 0, /* security_level */
2222 rinfo->required_relids,
2223 rinfo->incompatible_relids,
2224 rinfo->outer_relids);
2226 }
2227 }
2228 } while (found);
2229
2230 /* Now, any remaining clauses have to be thrown back */
2231 foreach(cell, root->left_join_clauses)
2232 {
2233 OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2234
2236 }
2237 foreach(cell, root->right_join_clauses)
2238 {
2239 OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2240
2242 }
2243 foreach(cell, root->full_join_clauses)
2244 {
2245 OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2246
2248 }
2249}
static bool reconsider_outer_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo, bool outer_on_left)
Definition: equivclass.c:2257
static bool reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo)
Definition: equivclass.c:2384
void distribute_restrictinfo_to_rels(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: initsplan.c:3227
Node * makeBoolConst(bool value, bool isnull)
Definition: makefuncs.c:408
RestrictInfo * rinfo
Definition: pathnodes.h:3059
Relids required_relids
Definition: pathnodes.h:2731

References distribute_restrictinfo_to_rels(), foreach_delete_current, RestrictInfo::has_clone, RestrictInfo::incompatible_relids, RestrictInfo::is_clone, RestrictInfo::is_pushed_down, lfirst, make_restrictinfo(), makeBoolConst(), RestrictInfo::outer_relids, reconsider_full_join_clause(), reconsider_outer_join_clause(), RestrictInfo::required_relids, OuterJoinClauseInfo::rinfo, and root.

Referenced by query_planner().

◆ relation_can_be_sorted_early()

bool relation_can_be_sorted_early ( PlannerInfo root,
RelOptInfo rel,
EquivalenceClass ec,
bool  require_parallel_safe 
)

Definition at line 1077 of file equivclass.c.

1079{
1080 PathTarget *target = rel->reltarget;
1082 ListCell *lc;
1083
1084 /*
1085 * Reject volatile ECs immediately; such sorts must always be postponed.
1086 */
1087 if (ec->ec_has_volatile)
1088 return false;
1089
1090 /*
1091 * Try to find an EM directly matching some reltarget member.
1092 */
1093 foreach(lc, target->exprs)
1094 {
1095 Expr *targetexpr = (Expr *) lfirst(lc);
1096
1097 em = find_ec_member_matching_expr(ec, targetexpr, rel->relids);
1098 if (!em)
1099 continue;
1100
1101 /*
1102 * Reject expressions involving set-returning functions, as those
1103 * can't be computed early either. (Note: this test and the following
1104 * one are effectively checking properties of targetexpr, so there's
1105 * no point in asking whether some other EC member would be better.)
1106 */
1107 if (expression_returns_set((Node *) em->em_expr))
1108 continue;
1109
1110 /*
1111 * If requested, reject expressions that are not parallel-safe. We
1112 * check this last because it's a rather expensive test.
1113 */
1114 if (require_parallel_safe &&
1115 !is_parallel_safe(root, (Node *) em->em_expr))
1116 continue;
1117
1118 return true;
1119 }
1120
1121 /*
1122 * Try to find an expression computable from the reltarget.
1123 */
1124 em = find_computable_ec_member(root, ec, target->exprs, rel->relids,
1125 require_parallel_safe);
1126 if (!em)
1127 return false;
1128
1129 /*
1130 * Reject expressions involving set-returning functions, as those can't be
1131 * computed early either. (There's no point in looking for another EC
1132 * member in this case; since SRFs can't appear in WHERE, they cannot
1133 * belong to multi-member ECs.)
1134 */
1135 if (expression_returns_set((Node *) em->em_expr))
1136 return false;
1137
1138 return true;
1139}
EquivalenceMember * find_ec_member_matching_expr(EquivalenceClass *ec, Expr *expr, Relids relids)
Definition: equivclass.c:916
EquivalenceMember * find_computable_ec_member(PlannerInfo *root, EquivalenceClass *ec, List *exprs, Relids relids, bool require_parallel_safe)
Definition: equivclass.c:991
List * exprs
Definition: pathnodes.h:1669

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 1659 of file pathkeys.c.

1662{
1663 List *pathkeys = NIL;
1664 int nClauses = list_length(mergeclauses);
1665 EquivalenceClass **ecs;
1666 int *scores;
1667 int necs;
1668 ListCell *lc;
1669 int j;
1670
1671 /* Might have no mergeclauses */
1672 if (nClauses == 0)
1673 return NIL;
1674
1675 /*
1676 * Make arrays of the ECs used by the mergeclauses (dropping any
1677 * duplicates) and their "popularity" scores.
1678 */
1679 ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
1680 scores = (int *) palloc(nClauses * sizeof(int));
1681 necs = 0;
1682
1683 foreach(lc, mergeclauses)
1684 {
1685 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1686 EquivalenceClass *oeclass;
1687 int score;
1688 ListCell *lc2;
1689
1690 /* get the outer eclass */
1692
1693 if (rinfo->outer_is_left)
1694 oeclass = rinfo->left_ec;
1695 else
1696 oeclass = rinfo->right_ec;
1697
1698 /* reject duplicates */
1699 for (j = 0; j < necs; j++)
1700 {
1701 if (ecs[j] == oeclass)
1702 break;
1703 }
1704 if (j < necs)
1705 continue;
1706
1707 /* compute score */
1708 score = 0;
1709 foreach(lc2, oeclass->ec_members)
1710 {
1712
1713 /* Child members should not exist in ec_members */
1714 Assert(!em->em_is_child);
1715
1716 /* Potential future join partner? */
1717 if (!em->em_is_const &&
1718 !bms_overlap(em->em_relids, joinrel->relids))
1719 score++;
1720 }
1721
1722 ecs[necs] = oeclass;
1723 scores[necs] = score;
1724 necs++;
1725 }
1726
1727 /*
1728 * Find out if we have all the ECs mentioned in query_pathkeys; if so we
1729 * can generate a sort order that's also useful for final output. If we
1730 * only have a prefix of the query_pathkeys, and that prefix is the entire
1731 * join condition, then it's useful to use the prefix as the pathkeys as
1732 * this increases the chances that an incremental sort will be able to be
1733 * used by the upper planner.
1734 */
1735 if (root->query_pathkeys)
1736 {
1737 int matches = 0;
1738
1739 foreach(lc, root->query_pathkeys)
1740 {
1741 PathKey *query_pathkey = (PathKey *) lfirst(lc);
1742 EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1743
1744 for (j = 0; j < necs; j++)
1745 {
1746 if (ecs[j] == query_ec)
1747 break; /* found match */
1748 }
1749 if (j >= necs)
1750 break; /* didn't find match */
1751
1752 matches++;
1753 }
1754 /* if we got to the end of the list, we have them all */
1755 if (lc == NULL)
1756 {
1757 /* copy query_pathkeys as starting point for our output */
1758 pathkeys = list_copy(root->query_pathkeys);
1759 /* mark their ECs as already-emitted */
1760 foreach(lc, root->query_pathkeys)
1761 {
1762 PathKey *query_pathkey = (PathKey *) lfirst(lc);
1763 EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1764
1765 for (j = 0; j < necs; j++)
1766 {
1767 if (ecs[j] == query_ec)
1768 {
1769 scores[j] = -1;
1770 break;
1771 }
1772 }
1773 }
1774 }
1775
1776 /*
1777 * If we didn't match to all of the query_pathkeys, but did match to
1778 * all of the join clauses then we'll make use of these as partially
1779 * sorted input is better than nothing for the upper planner as it may
1780 * lead to incremental sorts instead of full sorts.
1781 */
1782 else if (matches == nClauses)
1783 {
1784 pathkeys = list_copy_head(root->query_pathkeys, matches);
1785
1786 /* we have all of the join pathkeys, so nothing more to do */
1787 pfree(ecs);
1788 pfree(scores);
1789
1790 return pathkeys;
1791 }
1792 }
1793
1794 /*
1795 * Add remaining ECs to the list in popularity order, using a default sort
1796 * ordering. (We could use qsort() here, but the list length is usually
1797 * so small it's not worth it.)
1798 */
1799 for (;;)
1800 {
1801 int best_j;
1802 int best_score;
1803 EquivalenceClass *ec;
1804 PathKey *pathkey;
1805
1806 best_j = 0;
1807 best_score = scores[0];
1808 for (j = 1; j < necs; j++)
1809 {
1810 if (scores[j] > best_score)
1811 {
1812 best_j = j;
1813 best_score = scores[j];
1814 }
1815 }
1816 if (best_score < 0)
1817 break; /* all done */
1818 ec = ecs[best_j];
1819 scores[best_j] = -1;
1820 pathkey = make_canonical_pathkey(root,
1821 ec,
1823 COMPARE_LT,
1824 false);
1825 /* can't be redundant because no duplicate ECs */
1826 Assert(!pathkey_is_redundant(pathkey, pathkeys));
1827 pathkeys = lappend(pathkeys, pathkey);
1828 }
1829
1830 pfree(ecs);
1831 pfree(scores);
1832
1833 return pathkeys;
1834}
@ COMPARE_LT
Definition: cmptype.h:34
List * list_copy_head(const List *oldlist, int len)
Definition: list.c:1593
void pfree(void *pointer)
Definition: mcxt.c:2147
void * palloc(Size size)
Definition: mcxt.c:1940
#define linitial_oid(l)
Definition: pg_list.h:180

References Assert(), bms_overlap(), COMPARE_LT, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, j, lappend(), lfirst, linitial_oid, list_copy(), list_copy_head(), list_length(), make_canonical_pathkey(), NIL, palloc(), pathkey_is_redundant(), pfree(), RelOptInfo::relids, root, and update_mergeclause_eclasses().

Referenced by sort_inner_and_outer().

◆ setup_eclass_member_iterator()

◆ standard_join_search()

RelOptInfo * standard_join_search ( PlannerInfo root,
int  levels_needed,
List initial_rels 
)

Definition at line 3441 of file allpaths.c.

3442{
3443 int lev;
3444 RelOptInfo *rel;
3445
3446 /*
3447 * This function cannot be invoked recursively within any one planning
3448 * problem, so join_rel_level[] can't be in use already.
3449 */
3450 Assert(root->join_rel_level == NULL);
3451
3452 /*
3453 * We employ a simple "dynamic programming" algorithm: we first find all
3454 * ways to build joins of two jointree items, then all ways to build joins
3455 * of three items (from two-item joins and single items), then four-item
3456 * joins, and so on until we have considered all ways to join all the
3457 * items into one rel.
3458 *
3459 * root->join_rel_level[j] is a list of all the j-item rels. Initially we
3460 * set root->join_rel_level[1] to represent all the single-jointree-item
3461 * relations.
3462 */
3463 root->join_rel_level = (List **) palloc0((levels_needed + 1) * sizeof(List *));
3464
3465 root->join_rel_level[1] = initial_rels;
3466
3467 for (lev = 2; lev <= levels_needed; lev++)
3468 {
3469 ListCell *lc;
3470
3471 /*
3472 * Determine all possible pairs of relations to be joined at this
3473 * level, and build paths for making each one from every available
3474 * pair of lower-level relations.
3475 */
3477
3478 /*
3479 * Run generate_partitionwise_join_paths() and
3480 * generate_useful_gather_paths() for each just-processed joinrel. We
3481 * could not do this earlier because both regular and partial paths
3482 * can get added to a particular joinrel at multiple times within
3483 * join_search_one_level.
3484 *
3485 * After that, we're done creating paths for the joinrel, so run
3486 * set_cheapest().
3487 */
3488 foreach(lc, root->join_rel_level[lev])
3489 {
3490 rel = (RelOptInfo *) lfirst(lc);
3491
3492 /* Create paths for partitionwise joins. */
3494
3495 /*
3496 * Except for the topmost scan/join rel, consider gathering
3497 * partial paths. We'll do the same for the topmost scan/join rel
3498 * once we know the final targetlist (see grouping_planner's and
3499 * its call to apply_scanjoin_target_to_paths).
3500 */
3501 if (!bms_equal(rel->relids, root->all_query_rels))
3503
3504 /* Find and save the cheapest paths for this rel */
3505 set_cheapest(rel);
3506
3507#ifdef OPTIMIZER_DEBUG
3508 pprint(rel);
3509#endif
3510 }
3511 }
3512
3513 /*
3514 * We should have a single rel at the final level.
3515 */
3516 if (root->join_rel_level[levels_needed] == NIL)
3517 elog(ERROR, "failed to build any %d-way joins", levels_needed);
3518 Assert(list_length(root->join_rel_level[levels_needed]) == 1);
3519
3520 rel = (RelOptInfo *) linitial(root->join_rel_level[levels_needed]);
3521
3522 root->join_rel_level = NULL;
3523
3524 return rel;
3525}
void generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
Definition: allpaths.c:3220
void join_search_one_level(PlannerInfo *root, int level)
Definition: joinrels.c:73
void * palloc0(Size size)
Definition: mcxt.c:1970

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 1961 of file pathkeys.c.

1964{
1965 List *new_mergeclauses = NIL;
1966 PathKey *pathkey;
1967 EquivalenceClass *pathkey_ec;
1968 bool matched_pathkey;
1969 ListCell *lip;
1970 ListCell *i;
1971
1972 /* No pathkeys => no mergeclauses (though we don't expect this case) */
1973 if (pathkeys == NIL)
1974 return NIL;
1975 /* Initialize to consider first pathkey */
1976 lip = list_head(pathkeys);
1977 pathkey = (PathKey *) lfirst(lip);
1978 pathkey_ec = pathkey->pk_eclass;
1979 lip = lnext(pathkeys, lip);
1980 matched_pathkey = false;
1981
1982 /* Scan mergeclauses to see how many we can use */
1983 foreach(i, mergeclauses)
1984 {
1985 RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1986 EquivalenceClass *clause_ec;
1987
1988 /* Assume we needn't do update_mergeclause_eclasses again here */
1989
1990 /* Check clause's inner-rel EC against current pathkey */
1991 clause_ec = rinfo->outer_is_left ?
1992 rinfo->right_ec : rinfo->left_ec;
1993
1994 /* If we don't have a match, attempt to advance to next pathkey */
1995 if (clause_ec != pathkey_ec)
1996 {
1997 /* If we had no clauses matching this inner pathkey, must stop */
1998 if (!matched_pathkey)
1999 break;
2000
2001 /* Advance to next inner pathkey, if any */
2002 if (lip == NULL)
2003 break;
2004 pathkey = (PathKey *) lfirst(lip);
2005 pathkey_ec = pathkey->pk_eclass;
2006 lip = lnext(pathkeys, lip);
2007 matched_pathkey = false;
2008 }
2009
2010 /* If mergeclause matches current inner pathkey, we can use it */
2011 if (clause_ec == pathkey_ec)
2012 {
2013 new_mergeclauses = lappend(new_mergeclauses, rinfo);
2014 matched_pathkey = true;
2015 }
2016 else
2017 {
2018 /* Else, no hope of adding any more mergeclauses */
2019 break;
2020 }
2021 }
2022
2023 return new_mergeclauses;
2024}

References i, lappend(), lfirst, list_head(), lnext(), and NIL.

Referenced by generate_mergejoin_paths().

◆ truncate_useless_pathkeys()

List * truncate_useless_pathkeys ( PlannerInfo root,
RelOptInfo rel,
List pathkeys 
)

Definition at line 2270 of file pathkeys.c.

2273{
2274 int nuseful;
2275 int nuseful2;
2276
2277 nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
2278 nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
2279 if (nuseful2 > nuseful)
2280 nuseful = nuseful2;
2281 nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
2282 if (nuseful2 > nuseful)
2283 nuseful = nuseful2;
2284 nuseful2 = pathkeys_useful_for_distinct(root, pathkeys);
2285 if (nuseful2 > nuseful)
2286 nuseful = nuseful2;
2287 nuseful2 = pathkeys_useful_for_setop(root, pathkeys);
2288 if (nuseful2 > nuseful)
2289 nuseful = nuseful2;
2290
2291 /*
2292 * Note: not safe to modify input list destructively, but we can avoid
2293 * copying the list if we're not actually going to change it
2294 */
2295 if (nuseful == 0)
2296 return NIL;
2297 else if (nuseful == list_length(pathkeys))
2298 return pathkeys;
2299 else
2300 return list_copy_head(pathkeys, nuseful);
2301}
static int pathkeys_useful_for_setop(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2255
static int pathkeys_useful_for_distinct(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2224
static int pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2160
static int pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2190
static int pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:2056

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 1510 of file pathkeys.c.

1511{
1512 /* Should be a merge clause ... */
1513 Assert(restrictinfo->mergeopfamilies != NIL);
1514 /* ... with pointers already set */
1515 Assert(restrictinfo->left_ec != NULL);
1516 Assert(restrictinfo->right_ec != NULL);
1517
1518 /* Chase up to the top as needed */
1519 while (restrictinfo->left_ec->ec_merged)
1520 restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
1521 while (restrictinfo->right_ec->ec_merged)
1522 restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
1523}

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