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

Variables

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

Typedef Documentation

◆ ec_matches_callback_type

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

Definition at line 119 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 202 of file paths.h.

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

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

2816 {
2817  Relids top_parent_relids = child_joinrel->top_parent_relids;
2818  Relids child_relids = child_joinrel->relids;
2819  Bitmapset *matching_ecs;
2820  MemoryContext oldcontext;
2821  int i;
2822 
2823  Assert(IS_JOIN_REL(child_joinrel) && IS_JOIN_REL(parent_joinrel));
2824 
2825  /* We need consider only ECs that mention the parent joinrel */
2826  matching_ecs = get_eclass_indexes_for_relids(root, top_parent_relids);
2827 
2828  /*
2829  * If we're being called during GEQO join planning, we still have to
2830  * create any new EC members in the main planner context, to avoid having
2831  * a corrupt EC data structure after the GEQO context is reset. This is
2832  * problematic since we'll leak memory across repeated GEQO cycles. For
2833  * now, though, bloat is better than crash. If it becomes a real issue
2834  * we'll have to do something to avoid generating duplicate EC members.
2835  */
2836  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
2837 
2838  i = -1;
2839  while ((i = bms_next_member(matching_ecs, i)) >= 0)
2840  {
2841  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2842  int num_members;
2843 
2844  /*
2845  * If this EC contains a volatile expression, then generating child
2846  * EMs would be downright dangerous, so skip it. We rely on a
2847  * volatile EC having only one EM.
2848  */
2849  if (cur_ec->ec_has_volatile)
2850  continue;
2851 
2852  /* Sanity check on get_eclass_indexes_for_relids result */
2853  Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids));
2854 
2855  /*
2856  * We don't use foreach() here because there's no point in scanning
2857  * newly-added child members, so we can stop after the last
2858  * pre-existing EC member.
2859  */
2860  num_members = list_length(cur_ec->ec_members);
2861  for (int pos = 0; pos < num_members; pos++)
2862  {
2863  EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2864 
2865  if (cur_em->em_is_const)
2866  continue; /* ignore consts here */
2867 
2868  /*
2869  * We consider only original EC members here, not
2870  * already-transformed child members.
2871  */
2872  if (cur_em->em_is_child)
2873  continue; /* ignore children here */
2874 
2875  /*
2876  * We may ignore expressions that reference a single baserel,
2877  * because add_child_rel_equivalences should have handled them.
2878  */
2879  if (bms_membership(cur_em->em_relids) != BMS_MULTIPLE)
2880  continue;
2881 
2882  /* Does this member reference child's topmost parent rel? */
2883  if (bms_overlap(cur_em->em_relids, top_parent_relids))
2884  {
2885  /* Yes, generate transformed child version */
2886  Expr *child_expr;
2887  Relids new_relids;
2888 
2889  if (parent_joinrel->reloptkind == RELOPT_JOINREL)
2890  {
2891  /* Simple single-level transformation */
2892  child_expr = (Expr *)
2894  (Node *) cur_em->em_expr,
2895  nappinfos, appinfos);
2896  }
2897  else
2898  {
2899  /* Must do multi-level transformation */
2900  Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
2901  child_expr = (Expr *)
2903  (Node *) cur_em->em_expr,
2904  child_joinrel,
2905  child_joinrel->top_parent);
2906  }
2907 
2908  /*
2909  * Transform em_relids to match. Note we do *not* do
2910  * pull_varnos(child_expr) here, as for example the
2911  * transformation might have substituted a constant, but we
2912  * don't want the child member to be marked as constant.
2913  */
2914  new_relids = bms_difference(cur_em->em_relids,
2915  top_parent_relids);
2916  new_relids = bms_add_members(new_relids, child_relids);
2917 
2918  (void) add_eq_member(cur_ec, child_expr, new_relids,
2919  cur_em->em_jdomain,
2920  cur_em, cur_em->em_datatype);
2921  }
2922  }
2923  }
2924 
2925  MemoryContextSwitchTo(oldcontext);
2926 }
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:525
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1306
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:346
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:917
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
#define Assert(condition)
Definition: c.h:863
static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, JoinDomain *jdomain, EquivalenceMember *parent, Oid datatype)
Definition: equivclass.c:516
static Bitmapset * get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
Definition: equivclass.c:3387
int i
Definition: isn.c:72
#define IS_JOIN_REL(rel)
Definition: pathnodes.h:844
@ RELOPT_JOINREL
Definition: pathnodes.h:828
@ RELOPT_OTHER_JOINREL
Definition: pathnodes.h:830
static int list_length(const List *l)
Definition: pg_list.h:152
static void * list_nth(const List *list, int n)
Definition: pg_list.h:299
MemoryContextSwitchTo(old_ctx)
tree ctl root
Definition: radixtree.h:1886
JoinDomain * em_jdomain
Definition: pathnodes.h:1448
Definition: nodes.h:129
Relids relids
Definition: pathnodes.h:871
Relids top_parent_relids
Definition: pathnodes.h:1009
RelOptKind reloptkind
Definition: pathnodes.h:865

References add_eq_member(), adjust_appendrel_attrs(), adjust_appendrel_attrs_multilevel(), Assert, bms_add_members(), bms_difference(), bms_membership(), BMS_MULTIPLE, bms_next_member(), bms_overlap(), EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_jdomain, EquivalenceMember::em_relids, get_eclass_indexes_for_relids(), i, IS_JOIN_REL, list_length(), list_nth(), MemoryContextSwitchTo(), RelOptInfo::relids, RELOPT_JOINREL, RELOPT_OTHER_JOINREL, RelOptInfo::reloptkind, root, and RelOptInfo::top_parent_relids.

Referenced by build_child_join_rel().

◆ add_child_rel_equivalences()

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

Definition at line 2690 of file equivclass.c.

2694 {
2695  Relids top_parent_relids = child_rel->top_parent_relids;
2696  Relids child_relids = child_rel->relids;
2697  int i;
2698 
2699  /*
2700  * EC merging should be complete already, so we can use the parent rel's
2701  * eclass_indexes to avoid searching all of root->eq_classes.
2702  */
2703  Assert(root->ec_merging_done);
2704  Assert(IS_SIMPLE_REL(parent_rel));
2705 
2706  i = -1;
2707  while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0)
2708  {
2709  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2710  int num_members;
2711 
2712  /*
2713  * If this EC contains a volatile expression, then generating child
2714  * EMs would be downright dangerous, so skip it. We rely on a
2715  * volatile EC having only one EM.
2716  */
2717  if (cur_ec->ec_has_volatile)
2718  continue;
2719 
2720  /* Sanity check eclass_indexes only contain ECs for parent_rel */
2721  Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids));
2722 
2723  /*
2724  * We don't use foreach() here because there's no point in scanning
2725  * newly-added child members, so we can stop after the last
2726  * pre-existing EC member.
2727  */
2728  num_members = list_length(cur_ec->ec_members);
2729  for (int pos = 0; pos < num_members; pos++)
2730  {
2731  EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2732 
2733  if (cur_em->em_is_const)
2734  continue; /* ignore consts here */
2735 
2736  /*
2737  * We consider only original EC members here, not
2738  * already-transformed child members. Otherwise, if some original
2739  * member expression references more than one appendrel, we'd get
2740  * an O(N^2) explosion of useless derived expressions for
2741  * combinations of children. (But add_child_join_rel_equivalences
2742  * may add targeted combinations for partitionwise-join purposes.)
2743  */
2744  if (cur_em->em_is_child)
2745  continue; /* ignore children here */
2746 
2747  /*
2748  * Consider only members that reference and can be computed at
2749  * child's topmost parent rel. In particular we want to exclude
2750  * parent-rel Vars that have nonempty varnullingrels. Translating
2751  * those might fail, if the transformed expression wouldn't be a
2752  * simple Var; and in any case it wouldn't produce a member that
2753  * has any use in creating plans for the child rel.
2754  */
2755  if (bms_is_subset(cur_em->em_relids, top_parent_relids) &&
2756  !bms_is_empty(cur_em->em_relids))
2757  {
2758  /* OK, generate transformed child version */
2759  Expr *child_expr;
2760  Relids new_relids;
2761 
2762  if (parent_rel->reloptkind == RELOPT_BASEREL)
2763  {
2764  /* Simple single-level transformation */
2765  child_expr = (Expr *)
2767  (Node *) cur_em->em_expr,
2768  1, &appinfo);
2769  }
2770  else
2771  {
2772  /* Must do multi-level transformation */
2773  child_expr = (Expr *)
2775  (Node *) cur_em->em_expr,
2776  child_rel,
2777  child_rel->top_parent);
2778  }
2779 
2780  /*
2781  * Transform em_relids to match. Note we do *not* do
2782  * pull_varnos(child_expr) here, as for example the
2783  * transformation might have substituted a constant, but we
2784  * don't want the child member to be marked as constant.
2785  */
2786  new_relids = bms_difference(cur_em->em_relids,
2787  top_parent_relids);
2788  new_relids = bms_add_members(new_relids, child_relids);
2789 
2790  (void) add_eq_member(cur_ec, child_expr, new_relids,
2791  cur_em->em_jdomain,
2792  cur_em, cur_em->em_datatype);
2793 
2794  /* Record this EC index for the child rel */
2795  child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
2796  }
2797  }
2798  }
2799 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:412
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:815
#define bms_is_empty(a)
Definition: bitmapset.h:118
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:839
@ RELOPT_BASEREL
Definition: pathnodes.h:827
Bitmapset * eclass_indexes
Definition: pathnodes.h:952

References add_eq_member(), adjust_appendrel_attrs(), adjust_appendrel_attrs_multilevel(), Assert, bms_add_member(), bms_add_members(), bms_difference(), bms_is_empty, bms_is_subset(), bms_next_member(), EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, RelOptInfo::eclass_indexes, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_jdomain, EquivalenceMember::em_relids, i, IS_SIMPLE_REL, list_length(), list_nth(), RelOptInfo::relids, RELOPT_BASEREL, RelOptInfo::reloptkind, root, and RelOptInfo::top_parent_relids.

Referenced by set_append_rel_size().

◆ add_outer_joins_to_relids()

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

Definition at line 801 of file joinrels.c.

804 {
805  /* Nothing to do if this isn't an outer join with an assigned relid. */
806  if (sjinfo == NULL || sjinfo->ojrelid == 0)
807  return input_relids;
808 
809  /*
810  * If it's not a left join, we have no rules that would permit executing
811  * it in non-syntactic order, so just form the syntactic relid set. (This
812  * is just a quick-exit test; we'd come to the same conclusion anyway,
813  * since its commute_below_l and commute_above_l sets must be empty.)
814  */
815  if (sjinfo->jointype != JOIN_LEFT)
816  return bms_add_member(input_relids, sjinfo->ojrelid);
817 
818  /*
819  * We cannot add the OJ relid if this join has been pushed into the RHS of
820  * a syntactically-lower left join per OJ identity 3. (If it has, then we
821  * cannot claim that its outputs represent the final state of its RHS.)
822  * There will not be any other OJs that can be added either, so we're
823  * done.
824  */
825  if (!bms_is_subset(sjinfo->commute_below_l, input_relids))
826  return input_relids;
827 
828  /* OK to add OJ's own relid */
829  input_relids = bms_add_member(input_relids, sjinfo->ojrelid);
830 
831  /*
832  * Contrariwise, if we are now forming the final result of such a commuted
833  * pair of OJs, it's time to add the relid(s) of the pushed-down join(s).
834  * We can skip this if this join was never a candidate to be pushed up.
835  */
836  if (sjinfo->commute_above_l)
837  {
838  Relids commute_above_rels = bms_copy(sjinfo->commute_above_l);
839  ListCell *lc;
840 
841  /*
842  * The current join could complete the nulling of more than one
843  * pushed-down join, so we have to examine all the SpecialJoinInfos.
844  * Because join_info_list was built in bottom-up order, it's
845  * sufficient to traverse it once: an ojrelid we add in one loop
846  * iteration would not have affected decisions of earlier iterations.
847  */
848  foreach(lc, root->join_info_list)
849  {
850  SpecialJoinInfo *othersj = (SpecialJoinInfo *) lfirst(lc);
851 
852  if (othersj == sjinfo ||
853  othersj->ojrelid == 0 || othersj->jointype != JOIN_LEFT)
854  continue; /* definitely not interesting */
855 
856  if (!bms_is_member(othersj->ojrelid, commute_above_rels))
857  continue;
858 
859  /* Add it if not already present but conditions now satisfied */
860  if (!bms_is_member(othersj->ojrelid, input_relids) &&
861  bms_is_subset(othersj->min_lefthand, input_relids) &&
862  bms_is_subset(othersj->min_righthand, input_relids) &&
863  bms_is_subset(othersj->commute_below_l, input_relids))
864  {
865  input_relids = bms_add_member(input_relids, othersj->ojrelid);
866  /* report such pushed down outer joins, if asked */
867  if (pushed_down_joins != NULL)
868  *pushed_down_joins = lappend(*pushed_down_joins, othersj);
869 
870  /*
871  * We must also check any joins that othersj potentially
872  * commutes with. They likewise must appear later in
873  * join_info_list than othersj itself, so we can visit them
874  * later in this loop.
875  */
876  commute_above_rels = bms_add_members(commute_above_rels,
877  othersj->commute_above_l);
878  }
879  }
880  }
881 
882  return input_relids;
883 }
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:510
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:122
List * lappend(List *list, void *datum)
Definition: list.c:339
@ JOIN_LEFT
Definition: nodes.h:294
#define lfirst(lc)
Definition: pg_list.h:172
Relids min_righthand
Definition: pathnodes.h:2905
Relids commute_above_l
Definition: pathnodes.h:2910
JoinType jointype
Definition: pathnodes.h:2908
Relids commute_below_l
Definition: pathnodes.h:2912
Relids min_lefthand
Definition: pathnodes.h:2904

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

1316 {
1317  List *subpaths = NIL;
1318  bool subpaths_valid = true;
1319  List *startup_subpaths = NIL;
1320  bool startup_subpaths_valid = true;
1321  List *partial_subpaths = NIL;
1322  List *pa_partial_subpaths = NIL;
1323  List *pa_nonpartial_subpaths = NIL;
1324  bool partial_subpaths_valid = true;
1325  bool pa_subpaths_valid;
1326  List *all_child_pathkeys = NIL;
1327  List *all_child_outers = NIL;
1328  ListCell *l;
1329  double partial_rows = -1;
1330 
1331  /* If appropriate, consider parallel append */
1332  pa_subpaths_valid = enable_parallel_append && rel->consider_parallel;
1333 
1334  /*
1335  * For every non-dummy child, remember the cheapest path. Also, identify
1336  * all pathkeys (orderings) and parameterizations (required_outer sets)
1337  * available for the non-dummy member relations.
1338  */
1339  foreach(l, live_childrels)
1340  {
1341  RelOptInfo *childrel = lfirst(l);
1342  ListCell *lcp;
1343  Path *cheapest_partial_path = NULL;
1344 
1345  /*
1346  * If child has an unparameterized cheapest-total path, add that to
1347  * the unparameterized Append path we are constructing for the parent.
1348  * If not, there's no workable unparameterized path.
1349  *
1350  * With partitionwise aggregates, the child rel's pathlist may be
1351  * empty, so don't assume that a path exists here.
1352  */
1353  if (childrel->pathlist != NIL &&
1354  childrel->cheapest_total_path->param_info == NULL)
1356  &subpaths, NULL);
1357  else
1358  subpaths_valid = false;
1359 
1360  /*
1361  * When the planner is considering cheap startup plans, we'll also
1362  * collect all the cheapest_startup_paths (if set) and build an
1363  * AppendPath containing those as subpaths.
1364  */
1365  if (rel->consider_startup && childrel->cheapest_startup_path != NULL)
1366  {
1367  /* cheapest_startup_path must not be a parameterized path. */
1368  Assert(childrel->cheapest_startup_path->param_info == NULL);
1370  &startup_subpaths,
1371  NULL);
1372  }
1373  else
1374  startup_subpaths_valid = false;
1375 
1376 
1377  /* Same idea, but for a partial plan. */
1378  if (childrel->partial_pathlist != NIL)
1379  {
1380  cheapest_partial_path = linitial(childrel->partial_pathlist);
1381  accumulate_append_subpath(cheapest_partial_path,
1382  &partial_subpaths, NULL);
1383  }
1384  else
1385  partial_subpaths_valid = false;
1386 
1387  /*
1388  * Same idea, but for a parallel append mixing partial and non-partial
1389  * paths.
1390  */
1391  if (pa_subpaths_valid)
1392  {
1393  Path *nppath = NULL;
1394 
1395  nppath =
1397 
1398  if (cheapest_partial_path == NULL && nppath == NULL)
1399  {
1400  /* Neither a partial nor a parallel-safe path? Forget it. */
1401  pa_subpaths_valid = false;
1402  }
1403  else if (nppath == NULL ||
1404  (cheapest_partial_path != NULL &&
1405  cheapest_partial_path->total_cost < nppath->total_cost))
1406  {
1407  /* Partial path is cheaper or the only option. */
1408  Assert(cheapest_partial_path != NULL);
1409  accumulate_append_subpath(cheapest_partial_path,
1410  &pa_partial_subpaths,
1411  &pa_nonpartial_subpaths);
1412  }
1413  else
1414  {
1415  /*
1416  * Either we've got only a non-partial path, or we think that
1417  * a single backend can execute the best non-partial path
1418  * faster than all the parallel backends working together can
1419  * execute the best partial path.
1420  *
1421  * It might make sense to be more aggressive here. Even if
1422  * the best non-partial path is more expensive than the best
1423  * partial path, it could still be better to choose the
1424  * non-partial path if there are several such paths that can
1425  * be given to different workers. For now, we don't try to
1426  * figure that out.
1427  */
1429  &pa_nonpartial_subpaths,
1430  NULL);
1431  }
1432  }
1433 
1434  /*
1435  * Collect lists of all the available path orderings and
1436  * parameterizations for all the children. We use these as a
1437  * heuristic to indicate which sort orderings and parameterizations we
1438  * should build Append and MergeAppend paths for.
1439  */
1440  foreach(lcp, childrel->pathlist)
1441  {
1442  Path *childpath = (Path *) lfirst(lcp);
1443  List *childkeys = childpath->pathkeys;
1444  Relids childouter = PATH_REQ_OUTER(childpath);
1445 
1446  /* Unsorted paths don't contribute to pathkey list */
1447  if (childkeys != NIL)
1448  {
1449  ListCell *lpk;
1450  bool found = false;
1451 
1452  /* Have we already seen this ordering? */
1453  foreach(lpk, all_child_pathkeys)
1454  {
1455  List *existing_pathkeys = (List *) lfirst(lpk);
1456 
1457  if (compare_pathkeys(existing_pathkeys,
1458  childkeys) == PATHKEYS_EQUAL)
1459  {
1460  found = true;
1461  break;
1462  }
1463  }
1464  if (!found)
1465  {
1466  /* No, so add it to all_child_pathkeys */
1467  all_child_pathkeys = lappend(all_child_pathkeys,
1468  childkeys);
1469  }
1470  }
1471 
1472  /* Unparameterized paths don't contribute to param-set list */
1473  if (childouter)
1474  {
1475  ListCell *lco;
1476  bool found = false;
1477 
1478  /* Have we already seen this param set? */
1479  foreach(lco, all_child_outers)
1480  {
1481  Relids existing_outers = (Relids) lfirst(lco);
1482 
1483  if (bms_equal(existing_outers, childouter))
1484  {
1485  found = true;
1486  break;
1487  }
1488  }
1489  if (!found)
1490  {
1491  /* No, so add it to all_child_outers */
1492  all_child_outers = lappend(all_child_outers,
1493  childouter);
1494  }
1495  }
1496  }
1497  }
1498 
1499  /*
1500  * If we found unparameterized paths for all children, build an unordered,
1501  * unparameterized Append path for the rel. (Note: this is correct even
1502  * if we have zero or one live subpath due to constraint exclusion.)
1503  */
1504  if (subpaths_valid)
1505  add_path(rel, (Path *) create_append_path(root, rel, subpaths, NIL,
1506  NIL, NULL, 0, false,
1507  -1));
1508 
1509  /* build an AppendPath for the cheap startup paths, if valid */
1510  if (startup_subpaths_valid)
1511  add_path(rel, (Path *) create_append_path(root, rel, startup_subpaths,
1512  NIL, NIL, NULL, 0, false, -1));
1513 
1514  /*
1515  * Consider an append of unordered, unparameterized partial paths. Make
1516  * it parallel-aware if possible.
1517  */
1518  if (partial_subpaths_valid && partial_subpaths != NIL)
1519  {
1520  AppendPath *appendpath;
1521  ListCell *lc;
1522  int parallel_workers = 0;
1523 
1524  /* Find the highest number of workers requested for any subpath. */
1525  foreach(lc, partial_subpaths)
1526  {
1527  Path *path = lfirst(lc);
1528 
1529  parallel_workers = Max(parallel_workers, path->parallel_workers);
1530  }
1531  Assert(parallel_workers > 0);
1532 
1533  /*
1534  * If the use of parallel append is permitted, always request at least
1535  * log2(# of children) workers. We assume it can be useful to have
1536  * extra workers in this case because they will be spread out across
1537  * the children. The precise formula is just a guess, but we don't
1538  * want to end up with a radically different answer for a table with N
1539  * partitions vs. an unpartitioned table with the same data, so the
1540  * use of some kind of log-scaling here seems to make some sense.
1541  */
1543  {
1544  parallel_workers = Max(parallel_workers,
1545  pg_leftmost_one_pos32(list_length(live_childrels)) + 1);
1546  parallel_workers = Min(parallel_workers,
1548  }
1549  Assert(parallel_workers > 0);
1550 
1551  /* Generate a partial append path. */
1552  appendpath = create_append_path(root, rel, NIL, partial_subpaths,
1553  NIL, NULL, parallel_workers,
1555  -1);
1556 
1557  /*
1558  * Make sure any subsequent partial paths use the same row count
1559  * estimate.
1560  */
1561  partial_rows = appendpath->path.rows;
1562 
1563  /* Add the path. */
1564  add_partial_path(rel, (Path *) appendpath);
1565  }
1566 
1567  /*
1568  * Consider a parallel-aware append using a mix of partial and non-partial
1569  * paths. (This only makes sense if there's at least one child which has
1570  * a non-partial path that is substantially cheaper than any partial path;
1571  * otherwise, we should use the append path added in the previous step.)
1572  */
1573  if (pa_subpaths_valid && pa_nonpartial_subpaths != NIL)
1574  {
1575  AppendPath *appendpath;
1576  ListCell *lc;
1577  int parallel_workers = 0;
1578 
1579  /*
1580  * Find the highest number of workers requested for any partial
1581  * subpath.
1582  */
1583  foreach(lc, pa_partial_subpaths)
1584  {
1585  Path *path = lfirst(lc);
1586 
1587  parallel_workers = Max(parallel_workers, path->parallel_workers);
1588  }
1589 
1590  /*
1591  * Same formula here as above. It's even more important in this
1592  * instance because the non-partial paths won't contribute anything to
1593  * the planned number of parallel workers.
1594  */
1595  parallel_workers = Max(parallel_workers,
1596  pg_leftmost_one_pos32(list_length(live_childrels)) + 1);
1597  parallel_workers = Min(parallel_workers,
1599  Assert(parallel_workers > 0);
1600 
1601  appendpath = create_append_path(root, rel, pa_nonpartial_subpaths,
1602  pa_partial_subpaths,
1603  NIL, NULL, parallel_workers, true,
1604  partial_rows);
1605  add_partial_path(rel, (Path *) appendpath);
1606  }
1607 
1608  /*
1609  * Also build unparameterized ordered append paths based on the collected
1610  * list of child pathkeys.
1611  */
1612  if (subpaths_valid)
1613  generate_orderedappend_paths(root, rel, live_childrels,
1614  all_child_pathkeys);
1615 
1616  /*
1617  * Build Append paths for each parameterization seen among the child rels.
1618  * (This may look pretty expensive, but in most cases of practical
1619  * interest, the child rels will expose mostly the same parameterizations,
1620  * so that not that many cases actually get considered here.)
1621  *
1622  * The Append node itself cannot enforce quals, so all qual checking must
1623  * be done in the child paths. This means that to have a parameterized
1624  * Append path, we must have the exact same parameterization for each
1625  * child path; otherwise some children might be failing to check the
1626  * moved-down quals. To make them match up, we can try to increase the
1627  * parameterization of lesser-parameterized paths.
1628  */
1629  foreach(l, all_child_outers)
1630  {
1631  Relids required_outer = (Relids) lfirst(l);
1632  ListCell *lcr;
1633 
1634  /* Select the child paths for an Append with this parameterization */
1635  subpaths = NIL;
1636  subpaths_valid = true;
1637  foreach(lcr, live_childrels)
1638  {
1639  RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr);
1640  Path *subpath;
1641 
1642  if (childrel->pathlist == NIL)
1643  {
1644  /* failed to make a suitable path for this child */
1645  subpaths_valid = false;
1646  break;
1647  }
1648 
1650  childrel,
1651  required_outer);
1652  if (subpath == NULL)
1653  {
1654  /* failed to make a suitable path for this child */
1655  subpaths_valid = false;
1656  break;
1657  }
1658  accumulate_append_subpath(subpath, &subpaths, NULL);
1659  }
1660 
1661  if (subpaths_valid)
1662  add_path(rel, (Path *)
1663  create_append_path(root, rel, subpaths, NIL,
1664  NIL, required_outer, 0, false,
1665  -1));
1666  }
1667 
1668  /*
1669  * When there is only a single child relation, the Append path can inherit
1670  * any ordering available for the child rel's path, so that it's useful to
1671  * consider ordered partial paths. Above we only considered the cheapest
1672  * partial path for each child, but let's also make paths using any
1673  * partial paths that have pathkeys.
1674  */
1675  if (list_length(live_childrels) == 1)
1676  {
1677  RelOptInfo *childrel = (RelOptInfo *) linitial(live_childrels);
1678 
1679  /* skip the cheapest partial path, since we already used that above */
1680  for_each_from(l, childrel->partial_pathlist, 1)
1681  {
1682  Path *path = (Path *) lfirst(l);
1683  AppendPath *appendpath;
1684 
1685  /* skip paths with no pathkeys. */
1686  if (path->pathkeys == NIL)
1687  continue;
1688 
1689  appendpath = create_append_path(root, rel, NIL, list_make1(path),
1690  NIL, NULL,
1691  path->parallel_workers, true,
1692  partial_rows);
1693  add_partial_path(rel, (Path *) appendpath);
1694  }
1695  }
1696 }
static Path * get_cheapest_parameterized_child_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer)
Definition: allpaths.c:2011
static void generate_orderedappend_paths(PlannerInfo *root, RelOptInfo *rel, List *live_childrels, List *all_child_pathkeys)
Definition: allpaths.c:1726
static void accumulate_append_subpath(Path *path, List **subpaths, List **special_subpaths)
Definition: allpaths.c:2099
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:142
#define Min(x, y)
Definition: c.h:1009
#define Max(x, y)
Definition: c.h:1003
int max_parallel_workers_per_gather
Definition: costsize.c:143
bool enable_parallel_append
Definition: costsize.c:161
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:308
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:699
PathKeysComparison compare_pathkeys(List *keys1, List *keys2)
Definition: pathkeys.c:304
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_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:795
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:461
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1679
Bitmapset * Relids
Definition: pathnodes.h:30
static int pg_leftmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:41
#define NIL
Definition: pg_list.h:68
#define list_make1(x1)
Definition: pg_list.h:212
#define for_each_from(cell, lst, N)
Definition: pg_list.h:414
#define linitial(l)
Definition: pg_list.h:178
Definition: pg_list.h:54
List * pathkeys
Definition: pathnodes.h:1675
Cardinality rows
Definition: pathnodes.h:1669
int parallel_workers
Definition: pathnodes.h:1666
Cost total_cost
Definition: pathnodes.h:1672
bool consider_parallel
Definition: pathnodes.h:887
List * pathlist
Definition: pathnodes.h:898
struct Path * cheapest_startup_path
Definition: pathnodes.h:901
struct Path * cheapest_total_path
Definition: pathnodes.h:902
bool consider_startup
Definition: pathnodes.h:883
List * partial_pathlist
Definition: pathnodes.h:900

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_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;
180  case JOIN_UNIQUE_INNER:
181  extra.inner_unique = bms_is_subset(sjinfo->min_lefthand,
182  outerrel->relids);
183  break;
184  case JOIN_UNIQUE_OUTER:
186  joinrel->relids,
187  outerrel->relids,
188  innerrel,
189  JOIN_INNER,
190  restrictlist,
191  false);
192  break;
193  default:
195  joinrel->relids,
196  outerrel->relids,
197  innerrel,
198  jointype,
199  restrictlist,
200  false);
201  break;
202  }
203 
204  /*
205  * Find potential mergejoin clauses. We can skip this if we are not
206  * interested in doing a mergejoin. However, mergejoin may be our only
207  * way of implementing a full outer join, so override enable_mergejoin if
208  * it's a full join.
209  */
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:5091
bool enable_hashjoin
Definition: costsize.c:157
bool enable_mergejoin
Definition: costsize.c:156
static List * select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
Definition: joinpath.c:2467
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1334
set_join_pathlist_hook_type set_join_pathlist_hook
Definition: joinpath.c:33
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:2197
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1789
@ JOIN_SEMI
Definition: nodes.h:307
@ JOIN_FULL
Definition: nodes.h:295
@ JOIN_INNER
Definition: nodes.h:293
@ JOIN_UNIQUE_OUTER
Definition: nodes.h:316
@ JOIN_UNIQUE_INNER
Definition: nodes.h:317
@ JOIN_ANTI
Definition: nodes.h:308
List * mergeclause_list
Definition: pathnodes.h:3241
Relids param_source_rels
Definition: pathnodes.h:3245
SemiAntiJoinFactors semifactors
Definition: pathnodes.h:3244
SpecialJoinInfo * sjinfo
Definition: pathnodes.h:3243
Relids lateral_relids
Definition: pathnodes.h:913

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

2944 {
2945  ListCell *lc;
2946  ListCell *lc2 = list_head(setop_pathkeys);
2947 
2948  foreach(lc, child_tlist)
2949  {
2950  TargetEntry *tle = lfirst_node(TargetEntry, lc);
2951  EquivalenceMember *parent_em;
2952  PathKey *pk;
2953 
2954  if (tle->resjunk)
2955  continue;
2956 
2957  if (lc2 == NULL)
2958  elog(ERROR, "too few pathkeys for set operation");
2959 
2960  pk = lfirst_node(PathKey, lc2);
2961  parent_em = linitial(pk->pk_eclass->ec_members);
2962 
2963  /*
2964  * We can safely pass the parent member as the first member in the
2965  * ec_members list as this is added first in generate_union_paths,
2966  * likewise, the JoinDomain can be that of the initial member of the
2967  * Pathkey's EquivalenceClass.
2968  */
2969  add_eq_member(pk->pk_eclass,
2970  tle->expr,
2971  child_rel->relids,
2972  parent_em->em_jdomain,
2973  parent_em,
2974  exprType((Node *) tle->expr));
2975 
2976  lc2 = lnext(setop_pathkeys, lc2);
2977  }
2978 
2979  /*
2980  * transformSetOperationStmt() ensures that the targetlist never contains
2981  * any resjunk columns, so all eclasses that exist in 'root' must have
2982  * received a new member in the loop above. Add them to the child_rel's
2983  * eclass_indexes.
2984  */
2985  child_rel->eclass_indexes = bms_add_range(child_rel->eclass_indexes, 0,
2986  list_length(root->eq_classes) - 1);
2987 }
Bitmapset * bms_add_range(Bitmapset *a, int lower, int upper)
Definition: bitmapset.c:1019
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:42
#define lfirst_node(type, lc)
Definition: pg_list.h:176
static ListCell * list_head(const List *l)
Definition: pg_list.h:128
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:343
Expr * expr
Definition: primnodes.h:2190

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

Referenced by build_setop_child_paths().

◆ append_pathkeys()

List* append_pathkeys ( List target,
List source 
)

Definition at line 107 of file pathkeys.c.

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

References Assert, lappend(), lfirst_node, NIL, pathkey_is_redundant(), and source.

Referenced by adjust_group_pathkeys_for_groupagg(), and make_pathkeys_for_window().

◆ build_expression_pathkey()

List* build_expression_pathkey ( PlannerInfo root,
Expr expr,
Oid  opno,
Relids  rel,
bool  create_it 
)

Definition at line 1000 of file pathkeys.c.

1005 {
1006  List *pathkeys;
1007  Oid opfamily,
1008  opcintype;
1009  int16 strategy;
1010  PathKey *cpathkey;
1011 
1012  /* Find the operator in pg_amop --- failure shouldn't happen */
1013  if (!get_ordering_op_properties(opno,
1014  &opfamily, &opcintype, &strategy))
1015  elog(ERROR, "operator %u is not a valid ordering operator",
1016  opno);
1017 
1018  cpathkey = make_pathkey_from_sortinfo(root,
1019  expr,
1020  opfamily,
1021  opcintype,
1022  exprCollation((Node *) expr),
1023  (strategy == BTGreaterStrategyNumber),
1024  (strategy == BTGreaterStrategyNumber),
1025  0,
1026  rel,
1027  create_it);
1028 
1029  if (cpathkey)
1030  pathkeys = list_make1(cpathkey);
1031  else
1032  pathkeys = NIL;
1033 
1034  return pathkeys;
1035 }
signed short int16
Definition: c.h:507
bool get_ordering_op_properties(Oid opno, Oid *opfamily, Oid *opcintype, int16 *strategy)
Definition: lsyscache.c:207
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:816
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:31
#define BTGreaterStrategyNumber
Definition: stratnum.h:33

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

Referenced by set_function_pathlist().

◆ build_index_pathkeys()

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

Definition at line 740 of file pathkeys.c.

743 {
744  List *retval = NIL;
745  ListCell *lc;
746  int i;
747 
748  if (index->sortopfamily == NULL)
749  return NIL; /* non-orderable index */
750 
751  i = 0;
752  foreach(lc, index->indextlist)
753  {
754  TargetEntry *indextle = (TargetEntry *) lfirst(lc);
755  Expr *indexkey;
756  bool reverse_sort;
757  bool nulls_first;
758  PathKey *cpathkey;
759 
760  /*
761  * INCLUDE columns are stored in index unordered, so they don't
762  * support ordered index scan.
763  */
764  if (i >= index->nkeycolumns)
765  break;
766 
767  /* We assume we don't need to make a copy of the tlist item */
768  indexkey = indextle->expr;
769 
770  if (ScanDirectionIsBackward(scandir))
771  {
772  reverse_sort = !index->reverse_sort[i];
773  nulls_first = !index->nulls_first[i];
774  }
775  else
776  {
777  reverse_sort = index->reverse_sort[i];
778  nulls_first = index->nulls_first[i];
779  }
780 
781  /*
782  * OK, try to make a canonical pathkey for this sort key.
783  */
784  cpathkey = make_pathkey_from_sortinfo(root,
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:4316
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:50
Definition: type.h:95

References TargetEntry::expr, i, indexcol_is_bool_constant_for_query(), lappend(), lfirst, make_pathkey_from_sortinfo(), NIL, pathkey_is_redundant(), root, and ScanDirectionIsBackward.

Referenced by build_index_paths().

◆ build_join_pathkeys()

List* build_join_pathkeys ( PlannerInfo root,
RelOptInfo joinrel,
JoinType  jointype,
List outer_pathkeys 
)

Definition at line 1294 of file pathkeys.c.

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

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  */
943  cpathkey = make_pathkey_from_sortinfo(root,
944  keyCol,
945  partscheme->partopfamily[i],
946  partscheme->partopcintype[i],
947  partscheme->partcollation[i],
948  ScanDirectionIsBackward(scandir),
949  ScanDirectionIsBackward(scandir),
950  0,
951  partrel->relids,
952  false);
953 
954 
955  if (cpathkey)
956  {
957  /*
958  * We found the sort key in an EquivalenceClass, so it's relevant
959  * for this query. Add it to list, unless it's redundant.
960  */
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  */
976  if (!partkey_is_bool_constant_for_query(partrel, i))
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:1039

References Assert, i, IS_SIMPLE_REL, lappend(), linitial, RelOptInfo::live_parts, make_pathkey_from_sortinfo(), NIL, PartitionSchemeData::partcollation, partitions_are_ordered(), partkey_is_bool_constant_for_query(), PartitionSchemeData::partnatts, PartitionSchemeData::partopcintype, PartitionSchemeData::partopfamily, pathkey_is_redundant(), RelOptInfo::relids, root, and ScanDirectionIsBackward.

Referenced by generate_orderedappend_paths().

◆ canonicalize_ec_expression()

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

Definition at line 471 of file equivclass.c.

472 {
473  Oid expr_type = exprType((Node *) expr);
474 
475  /*
476  * For a polymorphic-input-type opclass, just keep the same exposed type.
477  * RECORD opclasses work like polymorphic-type ones for this purpose.
478  */
479  if (IsPolymorphicType(req_type) || req_type == RECORDOID)
480  req_type = expr_type;
481 
482  /*
483  * No work if the expression exposes the right type/collation already.
484  */
485  if (expr_type != req_type ||
486  exprCollation((Node *) expr) != req_collation)
487  {
488  /*
489  * If we have to change the type of the expression, set typmod to -1,
490  * since the new type may not have the same typmod interpretation.
491  * When we only have to change collation, preserve the exposed typmod.
492  */
493  int32 req_typmod;
494 
495  if (expr_type != req_type)
496  req_typmod = -1;
497  else
498  req_typmod = exprTypmod((Node *) expr);
499 
500  /*
501  * Use applyRelabelType so that we preserve const-flatness. This is
502  * important since eval_const_expressions has already been applied.
503  */
504  expr = (Expr *) applyRelabelType((Node *) expr,
505  req_type, req_typmod, req_collation,
506  COERCE_IMPLICIT_CAST, -1, false);
507  }
508 
509  return expr;
510 }
signed int int32
Definition: c.h:508
int32 exprTypmod(const Node *expr)
Definition: nodeFuncs.c:298
Node * applyRelabelType(Node *arg, Oid rtype, int32 rtypmod, Oid rcollid, CoercionForm rformat, int rlocation, bool overwrite_ok)
Definition: nodeFuncs.c:631
@ COERCE_IMPLICIT_CAST
Definition: primnodes.h:736

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 3946 of file indxpath.c.

3947 {
3948  List *clauselist;
3949  bool have_partial;
3950  bool is_target_rel;
3951  Relids otherrels;
3952  ListCell *lc;
3953 
3954  /* Indexes are available only on base or "other" member relations. */
3955  Assert(IS_SIMPLE_REL(rel));
3956 
3957  /*
3958  * Initialize the indrestrictinfo lists to be identical to
3959  * baserestrictinfo, and check whether there are any partial indexes. If
3960  * not, this is all we need to do.
3961  */
3962  have_partial = false;
3963  foreach(lc, rel->indexlist)
3964  {
3966 
3967  index->indrestrictinfo = rel->baserestrictinfo;
3968  if (index->indpred)
3969  have_partial = true;
3970  }
3971  if (!have_partial)
3972  return;
3973 
3974  /*
3975  * Construct a list of clauses that we can assume true for the purpose of
3976  * proving the index(es) usable. Restriction clauses for the rel are
3977  * always usable, and so are any join clauses that are "movable to" this
3978  * rel. Also, we can consider any EC-derivable join clauses (which must
3979  * be "movable to" this rel, by definition).
3980  */
3981  clauselist = list_copy(rel->baserestrictinfo);
3982 
3983  /* Scan the rel's join clauses */
3984  foreach(lc, rel->joininfo)
3985  {
3986  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3987 
3988  /* Check if clause can be moved to this rel */
3989  if (!join_clause_is_movable_to(rinfo, rel))
3990  continue;
3991 
3992  clauselist = lappend(clauselist, rinfo);
3993  }
3994 
3995  /*
3996  * Add on any equivalence-derivable join clauses. Computing the correct
3997  * relid sets for generate_join_implied_equalities is slightly tricky
3998  * because the rel could be a child rel rather than a true baserel, and in
3999  * that case we must subtract its parents' relid(s) from all_query_rels.
4000  * Additionally, we mustn't consider clauses that are only computable
4001  * after outer joins that can null the rel.
4002  */
4003  if (rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
4004  otherrels = bms_difference(root->all_query_rels,
4005  find_childrel_parents(root, rel));
4006  else
4007  otherrels = bms_difference(root->all_query_rels, rel->relids);
4008  otherrels = bms_del_members(otherrels, rel->nulling_relids);
4009 
4010  if (!bms_is_empty(otherrels))
4011  clauselist =
4012  list_concat(clauselist,
4014  bms_union(rel->relids,
4015  otherrels),
4016  otherrels,
4017  rel,
4018  NULL));
4019 
4020  /*
4021  * Normally we remove quals that are implied by a partial index's
4022  * predicate from indrestrictinfo, indicating that they need not be
4023  * checked explicitly by an indexscan plan using this index. However, if
4024  * the rel is a target relation of UPDATE/DELETE/MERGE/SELECT FOR UPDATE,
4025  * we cannot remove such quals from the plan, because they need to be in
4026  * the plan so that they will be properly rechecked by EvalPlanQual
4027  * testing. Some day we might want to remove such quals from the main
4028  * plan anyway and pass them through to EvalPlanQual via a side channel;
4029  * but for now, we just don't remove implied quals at all for target
4030  * relations.
4031  */
4032  is_target_rel = (bms_is_member(rel->relid, root->all_result_relids) ||
4033  get_plan_rowmark(root->rowMarks, rel->relid) != NULL);
4034 
4035  /*
4036  * Now try to prove each index predicate true, and compute the
4037  * indrestrictinfo lists for partial indexes. Note that we compute the
4038  * indrestrictinfo list even for non-predOK indexes; this might seem
4039  * wasteful, but we may be able to use such indexes in OR clauses, cf
4040  * generate_bitmap_or_paths().
4041  */
4042  foreach(lc, rel->indexlist)
4043  {
4045  ListCell *lcr;
4046 
4047  if (index->indpred == NIL)
4048  continue; /* ignore non-partial indexes here */
4049 
4050  if (!index->predOK) /* don't repeat work if already proven OK */
4051  index->predOK = predicate_implied_by(index->indpred, clauselist,
4052  false);
4053 
4054  /* If rel is an update target, leave indrestrictinfo as set above */
4055  if (is_target_rel)
4056  continue;
4057 
4058  /* Else compute indrestrictinfo as the non-implied quals */
4059  index->indrestrictinfo = NIL;
4060  foreach(lcr, rel->baserestrictinfo)
4061  {
4062  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcr);
4063 
4064  /* predicate_implied_by() assumes first arg is immutable */
4065  if (contain_mutable_functions((Node *) rinfo->clause) ||
4067  index->indpred, false))
4068  index->indrestrictinfo = lappend(index->indrestrictinfo, rinfo);
4069  }
4070  }
4071 }
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:251
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:1161
bool contain_mutable_functions(Node *clause)
Definition: clauses.c:370
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo)
Definition: equivclass.c:1385
List * list_copy(const List *oldlist)
Definition: list.c:1573
List * list_concat(List *list1, const List *list2)
Definition: list.c:561
@ RELOPT_OTHER_MEMBER_REL
Definition: pathnodes.h:829
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:509
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:985
List * joininfo
Definition: pathnodes.h:991
Index relid
Definition: pathnodes.h:918
List * indexlist
Definition: pathnodes.h:944
Relids nulling_relids
Definition: pathnodes.h:938
Expr * clause
Definition: pathnodes.h:2574

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(), 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 4214 of file allpaths.c.

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

References Max, Min, min_parallel_index_scan_size, min_parallel_table_scan_size, RelOptInfo::rel_parallel_workers, RELOPT_BASEREL, and RelOptInfo::reloptkind.

Referenced by cost_index(), create_partial_bitmap_paths(), create_plain_partial_paths(), and plan_create_index_workers().

◆ convert_subquery_pathkeys()

List* convert_subquery_pathkeys ( PlannerInfo root,
RelOptInfo rel,
List subquery_pathkeys,
List subquery_tlist 
)

Definition at line 1054 of file pathkeys.c.

1057 {
1058  List *retval = NIL;
1059  int retvallen = 0;
1060  int outer_query_keys = list_length(root->query_pathkeys);
1061  ListCell *i;
1062 
1063  foreach(i, subquery_pathkeys)
1064  {
1065  PathKey *sub_pathkey = (PathKey *) lfirst(i);
1066  EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
1067  PathKey *best_pathkey = NULL;
1068 
1069  if (sub_eclass->ec_has_volatile)
1070  {
1071  /*
1072  * If the sub_pathkey's EquivalenceClass is volatile, then it must
1073  * have come from an ORDER BY clause, and we have to match it to
1074  * that same targetlist entry.
1075  */
1076  TargetEntry *tle;
1077  Var *outer_var;
1078 
1079  if (sub_eclass->ec_sortref == 0) /* can't happen */
1080  elog(ERROR, "volatile EquivalenceClass has no sortref");
1081  tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
1082  Assert(tle);
1083  /* Is TLE actually available to the outer query? */
1084  outer_var = find_var_for_subquery_tle(rel, tle);
1085  if (outer_var)
1086  {
1087  /* We can represent this sub_pathkey */
1088  EquivalenceMember *sub_member;
1089  EquivalenceClass *outer_ec;
1090 
1091  Assert(list_length(sub_eclass->ec_members) == 1);
1092  sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
1093 
1094  /*
1095  * Note: it might look funny to be setting sortref = 0 for a
1096  * reference to a volatile sub_eclass. However, the
1097  * expression is *not* volatile in the outer query: it's just
1098  * a Var referencing whatever the subquery emitted. (IOW, the
1099  * outer query isn't going to re-execute the volatile
1100  * expression itself.) So this is okay.
1101  */
1102  outer_ec =
1104  (Expr *) outer_var,
1105  sub_eclass->ec_opfamilies,
1106  sub_member->em_datatype,
1107  sub_eclass->ec_collation,
1108  0,
1109  rel->relids,
1110  false);
1111 
1112  /*
1113  * If we don't find a matching EC, sub-pathkey isn't
1114  * interesting to the outer query
1115  */
1116  if (outer_ec)
1117  best_pathkey =
1119  outer_ec,
1120  sub_pathkey->pk_opfamily,
1121  sub_pathkey->pk_strategy,
1122  sub_pathkey->pk_nulls_first);
1123  }
1124  }
1125  else
1126  {
1127  /*
1128  * Otherwise, the sub_pathkey's EquivalenceClass could contain
1129  * multiple elements (representing knowledge that multiple items
1130  * are effectively equal). Each element might match none, one, or
1131  * more of the output columns that are visible to the outer query.
1132  * This means we may have multiple possible representations of the
1133  * sub_pathkey in the context of the outer query. Ideally we
1134  * would generate them all and put them all into an EC of the
1135  * outer query, thereby propagating equality knowledge up to the
1136  * outer query. Right now we cannot do so, because the outer
1137  * query's EquivalenceClasses are already frozen when this is
1138  * called. Instead we prefer the one that has the highest "score"
1139  * (number of EC peers, plus one if it matches the outer
1140  * query_pathkeys). This is the most likely to be useful in the
1141  * outer query.
1142  */
1143  int best_score = -1;
1144  ListCell *j;
1145 
1146  foreach(j, sub_eclass->ec_members)
1147  {
1148  EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
1149  Expr *sub_expr = sub_member->em_expr;
1150  Oid sub_expr_type = sub_member->em_datatype;
1151  Oid sub_expr_coll = sub_eclass->ec_collation;
1152  ListCell *k;
1153 
1154  if (sub_member->em_is_child)
1155  continue; /* ignore children here */
1156 
1157  foreach(k, subquery_tlist)
1158  {
1159  TargetEntry *tle = (TargetEntry *) lfirst(k);
1160  Var *outer_var;
1161  Expr *tle_expr;
1162  EquivalenceClass *outer_ec;
1163  PathKey *outer_pk;
1164  int score;
1165 
1166  /* Is TLE actually available to the outer query? */
1167  outer_var = find_var_for_subquery_tle(rel, tle);
1168  if (!outer_var)
1169  continue;
1170 
1171  /*
1172  * The targetlist entry is considered to match if it
1173  * matches after sort-key canonicalization. That is
1174  * needed since the sub_expr has been through the same
1175  * process.
1176  */
1177  tle_expr = canonicalize_ec_expression(tle->expr,
1178  sub_expr_type,
1179  sub_expr_coll);
1180  if (!equal(tle_expr, sub_expr))
1181  continue;
1182 
1183  /* See if we have a matching EC for the TLE */
1184  outer_ec = get_eclass_for_sort_expr(root,
1185  (Expr *) outer_var,
1186  sub_eclass->ec_opfamilies,
1187  sub_expr_type,
1188  sub_expr_coll,
1189  0,
1190  rel->relids,
1191  false);
1192 
1193  /*
1194  * If we don't find a matching EC, this sub-pathkey isn't
1195  * interesting to the outer query
1196  */
1197  if (!outer_ec)
1198  continue;
1199 
1200  outer_pk = make_canonical_pathkey(root,
1201  outer_ec,
1202  sub_pathkey->pk_opfamily,
1203  sub_pathkey->pk_strategy,
1204  sub_pathkey->pk_nulls_first);
1205  /* score = # of equivalence peers */
1206  score = list_length(outer_ec->ec_members) - 1;
1207  /* +1 if it matches the proper query_pathkeys item */
1208  if (retvallen < outer_query_keys &&
1209  list_nth(root->query_pathkeys, retvallen) == outer_pk)
1210  score++;
1211  if (score > best_score)
1212  {
1213  best_pathkey = outer_pk;
1214  best_score = score;
1215  }
1216  }
1217  }
1218  }
1219 
1220  /*
1221  * If we couldn't find a representation of this sub_pathkey, we're
1222  * done (we can't use the ones to its right, either).
1223  */
1224  if (!best_pathkey)
1225  break;
1226 
1227  /*
1228  * Eliminate redundant ordering info; could happen if outer query
1229  * equivalences subquery keys...
1230  */
1231  if (!pathkey_is_redundant(best_pathkey, retval))
1232  {
1233  retval = lappend(retval, best_pathkey);
1234  retvallen++;
1235  }
1236  }
1237 
1238  return retval;
1239 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:223
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:471
EquivalenceClass * get_eclass_for_sort_expr(PlannerInfo *root, Expr *expr, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
Definition: equivclass.c:586
int j
Definition: isn.c:73
static Var * find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
Definition: pathkeys.c:1251
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:56
List * ec_opfamilies
Definition: pathnodes.h:1392
bool pk_nulls_first
Definition: pathnodes.h:1480
int pk_strategy
Definition: pathnodes.h:1479
Oid pk_opfamily
Definition: pathnodes.h:1478
Definition: primnodes.h:248
TargetEntry * get_sortgroupref_tle(Index sortref, List *targetList)
Definition: tlist.c:345

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

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

◆ create_index_paths()

void create_index_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 241 of file indxpath.c.

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

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

Referenced by set_plain_rel_pathlist().

◆ create_partial_bitmap_paths()

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

Definition at line 4178 of file allpaths.c.

4180 {
4181  int parallel_workers;
4182  double pages_fetched;
4183 
4184  /* Compute heap pages for bitmap heap scan */
4185  pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
4186  NULL, NULL);
4187 
4188  parallel_workers = compute_parallel_worker(rel, pages_fetched, -1,
4190 
4191  if (parallel_workers <= 0)
4192  return;
4193 
4195  bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
4196 }
int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
Definition: allpaths.c:4214
double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, double loop_count, Cost *cost_p, double *tuples_p)
Definition: costsize.c:6490

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  */
511  tidquals = TidQualFromRestrictInfoList(root, rel->baserestrictinfo, rel,
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,
573  rel->lateral_referencers);
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:3014
TidPath * create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals, Relids required_outer)
Definition: pathnode.c:1235
TidRangePath * create_tidrangescan_path(PlannerInfo *root, RelOptInfo *rel, List *tidrangequals, Relids required_outer)
Definition: pathnode.c:1264
Relids lateral_referencers
Definition: pathnodes.h:942
bool has_eclass_joins
Definition: pathnodes.h:993
static List * TidQualFromRestrictInfoList(PlannerInfo *root, List *rlist, RelOptInfo *rel, bool *isCurrentOf)
Definition: tidpath.c:281
static void BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
Definition: tidpath.c:426
static List * TidRangeQualFromRestrictInfoList(List *rlist, RelOptInfo *rel)
Definition: tidpath.c:398
static bool ec_member_matches_ctid(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg)
Definition: tidpath.c:481

References add_path(), RelOptInfo::baserestrictinfo, BuildParameterizedTidPaths(), create_tidrangescan_path(), create_tidscan_path(), ec_member_matches_ctid(), enable_tidscan, generate_implied_equalities_for_column(), RelOptInfo::has_eclass_joins, RelOptInfo::joininfo, RelOptInfo::lateral_referencers, RelOptInfo::lateral_relids, NIL, root, TidQualFromRestrictInfoList(), and TidRangeQualFromRestrictInfoList().

Referenced by set_plain_rel_pathlist().

◆ eclass_useful_for_merging()

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

Definition at line 3266 of file equivclass.c.

3269 {
3270  Relids relids;
3271  ListCell *lc;
3272 
3273  Assert(!eclass->ec_merged);
3274 
3275  /*
3276  * Won't generate joinclauses if const or single-member (the latter test
3277  * covers the volatile case too)
3278  */
3279  if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
3280  return false;
3281 
3282  /*
3283  * Note we don't test ec_broken; if we did, we'd need a separate code path
3284  * to look through ec_sources. Checking the members anyway is OK as a
3285  * possibly-overoptimistic heuristic.
3286  */
3287 
3288  /* If specified rel is a child, we must consider the topmost parent rel */
3289  if (IS_OTHER_REL(rel))
3290  {
3292  relids = rel->top_parent_relids;
3293  }
3294  else
3295  relids = rel->relids;
3296 
3297  /* If rel already includes all members of eclass, no point in searching */
3298  if (bms_is_subset(eclass->ec_relids, relids))
3299  return false;
3300 
3301  /* To join, we need a member not in the given rel */
3302  foreach(lc, eclass->ec_members)
3303  {
3304  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
3305 
3306  if (cur_em->em_is_child)
3307  continue; /* ignore children here */
3308 
3309  if (!bms_overlap(cur_em->em_relids, relids))
3310  return true;
3311  }
3312 
3313  return false;
3314 }
#define IS_OTHER_REL(rel)
Definition: pathnodes.h:854
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 2498 of file equivclass.c.

2499 {
2500  ListCell *lc1;
2501 
2502  foreach(lc1, root->eq_classes)
2503  {
2504  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2505  bool item1member = false;
2506  bool item2member = false;
2507  ListCell *lc2;
2508 
2509  /* Never match to a volatile EC */
2510  if (ec->ec_has_volatile)
2511  continue;
2512 
2513  /*
2514  * It's okay to consider ec_broken ECs here. Brokenness just means we
2515  * couldn't derive all the implied clauses we'd have liked to; it does
2516  * not invalidate our knowledge that the members are equal.
2517  */
2518 
2519  /* Ignore if this EC doesn't use specified opfamily */
2520  if (OidIsValid(opfamily) &&
2521  !list_member_oid(ec->ec_opfamilies, opfamily))
2522  continue;
2523 
2524  foreach(lc2, ec->ec_members)
2525  {
2527 
2528  if (em->em_is_child)
2529  continue; /* ignore children here */
2530  if (equal(item1, em->em_expr))
2531  item1member = true;
2532  else if (equal(item2, em->em_expr))
2533  item2member = true;
2534  /* Exit as soon as equality is proven */
2535  if (item1member && item2member)
2536  return true;
2537  }
2538  }
2539  return false;
2540 }
#define OidIsValid(objectId)
Definition: c.h:780
bool list_member_oid(const List *list, Oid datum)
Definition: list.c:722

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

Referenced by add_unique_group_var(), and have_partkey_equi_join().

◆ find_computable_ec_member()

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

Definition at line 837 of file equivclass.c.

842 {
843  List *exprvars;
844  ListCell *lc;
845 
846  /*
847  * Pull out the Vars and quasi-Vars present in "exprs". In the typical
848  * non-appendrel case, this is just another representation of the same
849  * list. However, it does remove the distinction between the case of a
850  * list of plain expressions and a list of TargetEntrys.
851  */
852  exprvars = pull_var_clause((Node *) exprs,
856 
857  foreach(lc, ec->ec_members)
858  {
860  List *emvars;
861  ListCell *lc2;
862 
863  /*
864  * We shouldn't be trying to sort by an equivalence class that
865  * contains a constant, so no need to consider such cases any further.
866  */
867  if (em->em_is_const)
868  continue;
869 
870  /*
871  * Ignore child members unless they belong to the requested rel.
872  */
873  if (em->em_is_child &&
874  !bms_is_subset(em->em_relids, relids))
875  continue;
876 
877  /*
878  * Match if all Vars and quasi-Vars are present in "exprs".
879  */
880  emvars = pull_var_clause((Node *) em->em_expr,
884  foreach(lc2, emvars)
885  {
886  if (!list_member(exprvars, lfirst(lc2)))
887  break;
888  }
889  list_free(emvars);
890  if (lc2)
891  continue; /* we hit a non-available Var */
892 
893  /*
894  * If requested, reject expressions that are not parallel-safe. We
895  * check this last because it's a rather expensive test.
896  */
897  if (require_parallel_safe &&
898  !is_parallel_safe(root, (Node *) em->em_expr))
899  continue;
900 
901  return em; /* found usable expression */
902  }
903 
904  return NULL;
905 }
bool is_parallel_safe(PlannerInfo *root, Node *node)
Definition: clauses.c:753
void list_free(List *list)
Definition: list.c:1546
bool list_member(const List *list, const void *datum)
Definition: list.c:661
#define PVC_INCLUDE_WINDOWFUNCS
Definition: optimizer.h:188
#define PVC_INCLUDE_PLACEHOLDERS
Definition: optimizer.h:190
#define PVC_INCLUDE_AGGREGATES
Definition: optimizer.h:186
List * pull_var_clause(Node *node, int flags)
Definition: var.c:612

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

Referenced by prepare_sort_from_pathkeys(), and relation_can_be_sorted_early().

◆ find_derived_clause_for_ec_member()

RestrictInfo* find_derived_clause_for_ec_member ( EquivalenceClass ec,
EquivalenceMember em 
)

Definition at line 2650 of file equivclass.c.

2652 {
2653  ListCell *lc;
2654 
2655  Assert(ec->ec_has_const);
2656  Assert(!em->em_is_const);
2657  foreach(lc, ec->ec_derives)
2658  {
2659  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2660 
2661  /*
2662  * generate_base_implied_equalities_const will have put non-const
2663  * members on the left side of derived clauses.
2664  */
2665  if (rinfo->left_em == em)
2666  return rinfo;
2667  }
2668  return NULL;
2669 }

References Assert, EquivalenceClass::ec_derives, EquivalenceClass::ec_has_const, EquivalenceMember::em_is_const, and lfirst.

Referenced by get_foreign_key_join_selectivity().

◆ find_ec_member_matching_expr()

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

Definition at line 763 of file equivclass.c.

766 {
767  ListCell *lc;
768 
769  /* We ignore binary-compatible relabeling on both ends */
770  while (expr && IsA(expr, RelabelType))
771  expr = ((RelabelType *) expr)->arg;
772 
773  foreach(lc, ec->ec_members)
774  {
776  Expr *emexpr;
777 
778  /*
779  * We shouldn't be trying to sort by an equivalence class that
780  * contains a constant, so no need to consider such cases any further.
781  */
782  if (em->em_is_const)
783  continue;
784 
785  /*
786  * Ignore child members unless they belong to the requested rel.
787  */
788  if (em->em_is_child &&
789  !bms_is_subset(em->em_relids, relids))
790  continue;
791 
792  /*
793  * Match if same expression (after stripping relabel).
794  */
795  emexpr = em->em_expr;
796  while (emexpr && IsA(emexpr, RelabelType))
797  emexpr = ((RelabelType *) emexpr)->arg;
798 
799  if (equal(emexpr, expr))
800  return em;
801  }
802 
803  return NULL;
804 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
void * arg

References arg, bms_is_subset(), EquivalenceClass::ec_members, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, equal(), IsA, and lfirst.

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

◆ find_mergeclauses_for_outer_pathkeys()

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

Definition at line 1543 of file pathkeys.c.

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

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

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

◆ generate_base_implied_equalities()

void generate_base_implied_equalities ( PlannerInfo root)

Definition at line 1032 of file equivclass.c.

1033 {
1034  int ec_index;
1035  ListCell *lc;
1036 
1037  /*
1038  * At this point, we're done absorbing knowledge of equivalences in the
1039  * query, so no further EC merging should happen, and ECs remaining in the
1040  * eq_classes list can be considered canonical. (But note that it's still
1041  * possible for new single-member ECs to be added through
1042  * get_eclass_for_sort_expr().)
1043  */
1044  root->ec_merging_done = true;
1045 
1046  ec_index = 0;
1047  foreach(lc, root->eq_classes)
1048  {
1050  bool can_generate_joinclause = false;
1051  int i;
1052 
1053  Assert(ec->ec_merged == NULL); /* else shouldn't be in list */
1054  Assert(!ec->ec_broken); /* not yet anyway... */
1055 
1056  /*
1057  * Generate implied equalities that are restriction clauses.
1058  * Single-member ECs won't generate any deductions, either here or at
1059  * the join level.
1060  */
1061  if (list_length(ec->ec_members) > 1)
1062  {
1063  if (ec->ec_has_const)
1065  else
1067 
1068  /* Recover if we failed to generate required derived clauses */
1069  if (ec->ec_broken)
1071 
1072  /* Detect whether this EC might generate join clauses */
1073  can_generate_joinclause =
1075  }
1076 
1077  /*
1078  * Mark the base rels cited in each eclass (which should all exist by
1079  * now) with the eq_classes indexes of all eclasses mentioning them.
1080  * This will let us avoid searching in subsequent lookups. While
1081  * we're at it, we can mark base rels that have pending eclass joins;
1082  * this is a cheap version of has_relevant_eclass_joinclause().
1083  */
1084  i = -1;
1085  while ((i = bms_next_member(ec->ec_relids, i)) > 0)
1086  {
1087  RelOptInfo *rel = root->simple_rel_array[i];
1088 
1089  /* ignore the RTE_GROUP RTE */
1090  if (i == root->group_rtindex)
1091  continue;
1092 
1093  if (rel == NULL) /* must be an outer join */
1094  {
1095  Assert(bms_is_member(i, root->outer_join_rels));
1096  continue;
1097  }
1098 
1099  Assert(rel->reloptkind == RELOPT_BASEREL);
1100 
1102  ec_index);
1103 
1104  if (can_generate_joinclause)
1105  rel->has_eclass_joins = true;
1106  }
1107 
1108  ec_index++;
1109  }
1110 }
static void generate_base_implied_equalities_broken(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1322
static void generate_base_implied_equalities_no_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1211
static void generate_base_implied_equalities_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1116
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:1405

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

3065 {
3066  Path *cheapest_partial_path;
3067  Path *simple_gather_path;
3068  ListCell *lc;
3069  double rows;
3070  double *rowsp = NULL;
3071 
3072  /* If there are no partial paths, there's nothing to do here. */
3073  if (rel->partial_pathlist == NIL)
3074  return;
3075 
3076  /* Should we override the rel's rowcount estimate? */
3077  if (override_rows)
3078  rowsp = &rows;
3079 
3080  /*
3081  * The output of Gather is always unsorted, so there's only one partial
3082  * path of interest: the cheapest one. That will be the one at the front
3083  * of partial_pathlist because of the way add_partial_path works.
3084  */
3085  cheapest_partial_path = linitial(rel->partial_pathlist);
3086  rows = compute_gather_rows(cheapest_partial_path);
3087  simple_gather_path = (Path *)
3088  create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
3089  NULL, rowsp);
3090  add_path(rel, simple_gather_path);
3091 
3092  /*
3093  * For each useful ordering, we can consider an order-preserving Gather
3094  * Merge.
3095  */
3096  foreach(lc, rel->partial_pathlist)
3097  {
3098  Path *subpath = (Path *) lfirst(lc);
3099  GatherMergePath *path;
3100 
3101  if (subpath->pathkeys == NIL)
3102  continue;
3103 
3104  rows = compute_gather_rows(subpath);
3105  path = create_gather_merge_path(root, rel, subpath, rel->reltarget,
3106  subpath->pathkeys, NULL, rowsp);
3107  add_path(rel, &path->path);
3108  }
3109 }
double compute_gather_rows(Path *path)
Definition: costsize.c:6601
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:893

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

3019 {
3020  List *result = NIL;
3021  bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
3022  Relids parent_relids;
3023  int i;
3024 
3025  /* Should be OK to rely on eclass_indexes */
3026  Assert(root->ec_merging_done);
3027 
3028  /* Indexes are available only on base or "other" member relations. */
3029  Assert(IS_SIMPLE_REL(rel));
3030 
3031  /* If it's a child rel, we'll need to know what its parent(s) are */
3032  if (is_child_rel)
3033  parent_relids = find_childrel_parents(root, rel);
3034  else
3035  parent_relids = NULL; /* not used, but keep compiler quiet */
3036 
3037  i = -1;
3038  while ((i = bms_next_member(rel->eclass_indexes, i)) >= 0)
3039  {
3040  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
3041  EquivalenceMember *cur_em;
3042  ListCell *lc2;
3043 
3044  /* Sanity check eclass_indexes only contain ECs for rel */
3045  Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
3046 
3047  /*
3048  * Won't generate joinclauses if const or single-member (the latter
3049  * test covers the volatile case too)
3050  */
3051  if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
3052  continue;
3053 
3054  /*
3055  * Scan members, looking for a match to the target column. Note that
3056  * child EC members are considered, but only when they belong to the
3057  * target relation. (Unlike regular members, the same expression
3058  * could be a child member of more than one EC. Therefore, it's
3059  * potentially order-dependent which EC a child relation's target
3060  * column gets matched to. This is annoying but it only happens in
3061  * corner cases, so for now we live with just reporting the first
3062  * match. See also get_eclass_for_sort_expr.)
3063  */
3064  cur_em = NULL;
3065  foreach(lc2, cur_ec->ec_members)
3066  {
3067  cur_em = (EquivalenceMember *) lfirst(lc2);
3068  if (bms_equal(cur_em->em_relids, rel->relids) &&
3069  callback(root, rel, cur_ec, cur_em, callback_arg))
3070  break;
3071  cur_em = NULL;
3072  }
3073 
3074  if (!cur_em)
3075  continue;
3076 
3077  /*
3078  * Found our match. Scan the other EC members and attempt to generate
3079  * joinclauses.
3080  */
3081  foreach(lc2, cur_ec->ec_members)
3082  {
3083  EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
3084  Oid eq_op;
3085  RestrictInfo *rinfo;
3086 
3087  if (other_em->em_is_child)
3088  continue; /* ignore children here */
3089 
3090  /* Make sure it'll be a join to a different rel */
3091  if (other_em == cur_em ||
3092  bms_overlap(other_em->em_relids, rel->relids))
3093  continue;
3094 
3095  /* Forget it if caller doesn't want joins to this rel */
3096  if (bms_overlap(other_em->em_relids, prohibited_rels))
3097  continue;
3098 
3099  /*
3100  * Also, if this is a child rel, avoid generating a useless join
3101  * to its parent rel(s).
3102  */
3103  if (is_child_rel &&
3104  bms_overlap(parent_relids, other_em->em_relids))
3105  continue;
3106 
3107  eq_op = select_equality_operator(cur_ec,
3108  cur_em->em_datatype,
3109  other_em->em_datatype);
3110  if (!OidIsValid(eq_op))
3111  continue;
3112 
3113  /* set parent_ec to mark as redundant with other joinclauses */
3114  rinfo = create_join_clause(root, cur_ec, eq_op,
3115  cur_em, other_em,
3116  cur_ec);
3117 
3118  result = lappend(result, rinfo);
3119  }
3120 
3121  /*
3122  * If somehow we failed to create any join clauses, we might as well
3123  * keep scanning the ECs for another match. But if we did make any,
3124  * we're done, because we don't want to return non-redundant clauses.
3125  */
3126  if (result)
3127  break;
3128  }
3129 
3130  return result;
3131 }
static RestrictInfo * create_join_clause(PlannerInfo *root, EquivalenceClass *ec, Oid opno, EquivalenceMember *leftem, EquivalenceMember *rightem, EquivalenceClass *parent_ec)
Definition: equivclass.c:1817
static Oid select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype)
Definition: equivclass.c:1781
static void callback(struct sockaddr *addr, struct sockaddr *mask, void *unused)
Definition: test_ifaddrs.c:46

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

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

◆ generate_join_implied_equalities()

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

Definition at line 1385 of file equivclass.c.

1390 {
1391  List *result = NIL;
1392  Relids inner_relids = inner_rel->relids;
1393  Relids nominal_inner_relids;
1394  Relids nominal_join_relids;
1395  Bitmapset *matching_ecs;
1396  int i;
1397 
1398  /* If inner rel is a child, extra setup work is needed */
1399  if (IS_OTHER_REL(inner_rel))
1400  {
1401  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1402 
1403  /* Fetch relid set for the topmost parent rel */
1404  nominal_inner_relids = inner_rel->top_parent_relids;
1405  /* ECs will be marked with the parent's relid, not the child's */
1406  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1407  nominal_join_relids = add_outer_joins_to_relids(root,
1408  nominal_join_relids,
1409  sjinfo,
1410  NULL);
1411  }
1412  else
1413  {
1414  nominal_inner_relids = inner_relids;
1415  nominal_join_relids = join_relids;
1416  }
1417 
1418  /*
1419  * Examine all potentially-relevant eclasses.
1420  *
1421  * If we are considering an outer join, we must include "join" clauses
1422  * that mention either input rel plus the outer join's relid; these
1423  * represent post-join filter clauses that have to be applied at this
1424  * join. We don't have infrastructure that would let us identify such
1425  * eclasses cheaply, so just fall back to considering all eclasses
1426  * mentioning anything in nominal_join_relids.
1427  *
1428  * At inner joins, we can be smarter: only consider eclasses mentioning
1429  * both input rels.
1430  */
1431  if (sjinfo && sjinfo->ojrelid != 0)
1432  matching_ecs = get_eclass_indexes_for_relids(root, nominal_join_relids);
1433  else
1434  matching_ecs = get_common_eclass_indexes(root, nominal_inner_relids,
1435  outer_relids);
1436 
1437  i = -1;
1438  while ((i = bms_next_member(matching_ecs, i)) >= 0)
1439  {
1440  EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
1441  List *sublist = NIL;
1442 
1443  /* ECs containing consts do not need any further enforcement */
1444  if (ec->ec_has_const)
1445  continue;
1446 
1447  /* Single-member ECs won't generate any deductions */
1448  if (list_length(ec->ec_members) <= 1)
1449  continue;
1450 
1451  /* Sanity check that this eclass overlaps the join */
1452  Assert(bms_overlap(ec->ec_relids, nominal_join_relids));
1453 
1454  if (!ec->ec_broken)
1456  ec,
1457  join_relids,
1458  outer_relids,
1459  inner_relids);
1460 
1461  /* Recover if we failed to generate required derived clauses */
1462  if (ec->ec_broken)
1464  ec,
1465  nominal_join_relids,
1466  outer_relids,
1467  nominal_inner_relids,
1468  inner_rel);
1469 
1470  result = list_concat(result, sublist);
1471  }
1472 
1473  return result;
1474 }
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1556
static Bitmapset * get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
Definition: equivclass.c:3421
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:1732
Relids add_outer_joins_to_relids(PlannerInfo *root, Relids input_relids, SpecialJoinInfo *sjinfo, List **pushed_down_joins)
Definition: joinrels.c:801

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(), and reduce_unique_semijoins().

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

1490 {
1491  List *result = NIL;
1492  Relids inner_relids = inner_rel->relids;
1493  Relids nominal_inner_relids;
1494  Relids nominal_join_relids;
1495  ListCell *lc;
1496 
1497  /* If inner rel is a child, extra setup work is needed */
1498  if (IS_OTHER_REL(inner_rel))
1499  {
1500  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1501 
1502  /* Fetch relid set for the topmost parent rel */
1503  nominal_inner_relids = inner_rel->top_parent_relids;
1504  /* ECs will be marked with the parent's relid, not the child's */
1505  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1506  }
1507  else
1508  {
1509  nominal_inner_relids = inner_relids;
1510  nominal_join_relids = join_relids;
1511  }
1512 
1513  foreach(lc, eclasses)
1514  {
1516  List *sublist = NIL;
1517 
1518  /* ECs containing consts do not need any further enforcement */
1519  if (ec->ec_has_const)
1520  continue;
1521 
1522  /* Single-member ECs won't generate any deductions */
1523  if (list_length(ec->ec_members) <= 1)
1524  continue;
1525 
1526  /* We can quickly ignore any that don't overlap the join, too */
1527  if (!bms_overlap(ec->ec_relids, nominal_join_relids))
1528  continue;
1529 
1530  if (!ec->ec_broken)
1532  ec,
1533  join_relids,
1534  outer_relids,
1535  inner_relids);
1536 
1537  /* Recover if we failed to generate required derived clauses */
1538  if (ec->ec_broken)
1540  ec,
1541  nominal_join_relids,
1542  outer_relids,
1543  nominal_inner_relids,
1544  inner_rel);
1545 
1546  result = list_concat(result, sublist);
1547  }
1548 
1549  return result;
1550 }

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

4303 {
4304  List *live_children = NIL;
4305  int cnt_parts;
4306  int num_parts;
4307  RelOptInfo **part_rels;
4308 
4309  /* Handle only join relations here. */
4310  if (!IS_JOIN_REL(rel))
4311  return;
4312 
4313  /* We've nothing to do if the relation is not partitioned. */
4314  if (!IS_PARTITIONED_REL(rel))
4315  return;
4316 
4317  /* The relation should have consider_partitionwise_join set. */
4319 
4320  /* Guard against stack overflow due to overly deep partition hierarchy. */
4322 
4323  num_parts = rel->nparts;
4324  part_rels = rel->part_rels;
4325 
4326  /* Collect non-dummy child-joins. */
4327  for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
4328  {
4329  RelOptInfo *child_rel = part_rels[cnt_parts];
4330 
4331  /* If it's been pruned entirely, it's certainly dummy. */
4332  if (child_rel == NULL)
4333  continue;
4334 
4335  /* Make partitionwise join paths for this partitioned child-join. */
4337 
4338  /* If we failed to make any path for this child, we must give up. */
4339  if (child_rel->pathlist == NIL)
4340  {
4341  /*
4342  * Mark the parent joinrel as unpartitioned so that later
4343  * functions treat it correctly.
4344  */
4345  rel->nparts = 0;
4346  return;
4347  }
4348 
4349  /* Else, identify the cheapest path for it. */
4350  set_cheapest(child_rel);
4351 
4352  /* Dummy children need not be scanned, so ignore those. */
4353  if (IS_DUMMY_REL(child_rel))
4354  continue;
4355 
4356 #ifdef OPTIMIZER_DEBUG
4357  pprint(child_rel);
4358 #endif
4359 
4360  live_children = lappend(live_children, child_rel);
4361  }
4362 
4363  /* If all child-joins are dummy, parent join is also dummy. */
4364  if (!live_children)
4365  {
4366  mark_dummy_rel(rel);
4367  return;
4368  }
4369 
4370  /* Build additional paths for this rel from child-join paths. */
4371  add_paths_to_append_rel(root, rel, live_children);
4372  list_free(live_children);
4373 }
void generate_partitionwise_join_paths(PlannerInfo *root, RelOptInfo *rel)
Definition: allpaths.c:4302
void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels)
Definition: allpaths.c:1314
void pprint(const void *obj)
Definition: print.c:54
void mark_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1384
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:269
#define IS_DUMMY_REL(r)
Definition: pathnodes.h:1956
#define IS_PARTITIONED_REL(rel)
Definition: pathnodes.h:1062
void check_stack_depth(void)
Definition: postgres.c:3563
bool consider_partitionwise_join
Definition: pathnodes.h:999

References add_paths_to_append_rel(), Assert, check_stack_depth(), RelOptInfo::consider_partitionwise_join, 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 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 3201 of file allpaths.c.

3202 {
3203  ListCell *lc;
3204  double rows;
3205  double *rowsp = NULL;
3206  List *useful_pathkeys_list = NIL;
3207  Path *cheapest_partial_path = NULL;
3208 
3209  /* If there are no partial paths, there's nothing to do here. */
3210  if (rel->partial_pathlist == NIL)
3211  return;
3212 
3213  /* Should we override the rel's rowcount estimate? */
3214  if (override_rows)
3215  rowsp = &rows;
3216 
3217  /* generate the regular gather (merge) paths */
3218  generate_gather_paths(root, rel, override_rows);
3219 
3220  /* consider incremental sort for interesting orderings */
3221  useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel, true);
3222 
3223  /* used for explicit (full) sort paths */
3224  cheapest_partial_path = linitial(rel->partial_pathlist);
3225 
3226  /*
3227  * Consider sorted paths for each interesting ordering. We generate both
3228  * incremental and full sort.
3229  */
3230  foreach(lc, useful_pathkeys_list)
3231  {
3232  List *useful_pathkeys = lfirst(lc);
3233  ListCell *lc2;
3234  bool is_sorted;
3235  int presorted_keys;
3236 
3237  foreach(lc2, rel->partial_pathlist)
3238  {
3239  Path *subpath = (Path *) lfirst(lc2);
3240  GatherMergePath *path;
3241 
3242  is_sorted = pathkeys_count_contained_in(useful_pathkeys,
3243  subpath->pathkeys,
3244  &presorted_keys);
3245 
3246  /*
3247  * We don't need to consider the case where a subpath is already
3248  * fully sorted because generate_gather_paths already creates a
3249  * gather merge path for every subpath that has pathkeys present.
3250  *
3251  * But since the subpath is already sorted, we know we don't need
3252  * to consider adding a sort (full or incremental) on top of it,
3253  * so we can continue here.
3254  */
3255  if (is_sorted)
3256  continue;
3257 
3258  /*
3259  * Try at least sorting the cheapest path and also try
3260  * incrementally sorting any path which is partially sorted
3261  * already (no need to deal with paths which have presorted keys
3262  * when incremental sort is disabled unless it's the cheapest
3263  * input path).
3264  */
3265  if (subpath != cheapest_partial_path &&
3266  (presorted_keys == 0 || !enable_incremental_sort))
3267  continue;
3268 
3269  /*
3270  * Consider regular sort for any path that's not presorted or if
3271  * incremental sort is disabled. We've no need to consider both
3272  * sort and incremental sort on the same path. We assume that
3273  * incremental sort is always faster when there are presorted
3274  * keys.
3275  *
3276  * This is not redundant with the gather paths created in
3277  * generate_gather_paths, because that doesn't generate ordered
3278  * output. Here we add an explicit sort to match the useful
3279  * ordering.
3280  */
3281  if (presorted_keys == 0 || !enable_incremental_sort)
3282  {
3284  rel,
3285  subpath,
3286  useful_pathkeys,
3287  -1.0);
3288  }
3289  else
3291  rel,
3292  subpath,
3293  useful_pathkeys,
3294  presorted_keys,
3295  -1);
3296  rows = compute_gather_rows(subpath);
3297  path = create_gather_merge_path(root, rel,
3298  subpath,
3299  rel->reltarget,
3300  subpath->pathkeys,
3301  NULL,
3302  rowsp);
3303 
3304  add_path(rel, &path->path);
3305  }
3306  }
3307 }
void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
Definition: allpaths.c:3064
static List * get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel, bool require_parallel_safe)
Definition: allpaths.c:3133
bool enable_incremental_sort
Definition: costsize.c:151
bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
Definition: pathkeys.c:558
SortPath * create_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, double limit_tuples)
Definition: pathnode.c:3082
IncrementalSortPath * create_incremental_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, int presorted_keys, double limit_tuples)
Definition: pathnode.c:3032

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

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_orderedappend_paths(), generate_union_paths(), and get_cheapest_parameterized_child_path().

◆ get_eclass_for_sort_expr()

EquivalenceClass* get_eclass_for_sort_expr ( PlannerInfo root,
Expr expr,
List opfamilies,
Oid  opcintype,
Oid  collation,
Index  sortref,
Relids  rel,
bool  create_it 
)

Definition at line 586 of file equivclass.c.

594 {
595  JoinDomain *jdomain;
596  Relids expr_relids;
597  EquivalenceClass *newec;
598  EquivalenceMember *newem;
599  ListCell *lc1;
600  MemoryContext oldcontext;
601 
602  /*
603  * Ensure the expression exposes the correct type and collation.
604  */
605  expr = canonicalize_ec_expression(expr, opcintype, collation);
606 
607  /*
608  * Since SortGroupClause nodes are top-level expressions (GROUP BY, ORDER
609  * BY, etc), they can be presumed to belong to the top JoinDomain.
610  */
611  jdomain = linitial_node(JoinDomain, root->join_domains);
612 
613  /*
614  * Scan through the existing EquivalenceClasses for a match
615  */
616  foreach(lc1, root->eq_classes)
617  {
618  EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
619  ListCell *lc2;
620 
621  /*
622  * Never match to a volatile EC, except when we are looking at another
623  * reference to the same volatile SortGroupClause.
624  */
625  if (cur_ec->ec_has_volatile &&
626  (sortref == 0 || sortref != cur_ec->ec_sortref))
627  continue;
628 
629  if (collation != cur_ec->ec_collation)
630  continue;
631  if (!equal(opfamilies, cur_ec->ec_opfamilies))
632  continue;
633 
634  foreach(lc2, cur_ec->ec_members)
635  {
636  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
637 
638  /*
639  * Ignore child members unless they match the request.
640  */
641  if (cur_em->em_is_child &&
642  !bms_equal(cur_em->em_relids, rel))
643  continue;
644 
645  /*
646  * Match constants only within the same JoinDomain (see
647  * optimizer/README).
648  */
649  if (cur_em->em_is_const && cur_em->em_jdomain != jdomain)
650  continue;
651 
652  if (opcintype == cur_em->em_datatype &&
653  equal(expr, cur_em->em_expr))
654  return cur_ec; /* Match! */
655  }
656  }
657 
658  /* No match; does caller want a NULL result? */
659  if (!create_it)
660  return NULL;
661 
662  /*
663  * OK, build a new single-member EC
664  *
665  * Here, we must be sure that we construct the EC in the right context.
666  */
667  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
668 
669  newec = makeNode(EquivalenceClass);
670  newec->ec_opfamilies = list_copy(opfamilies);
671  newec->ec_collation = collation;
672  newec->ec_members = NIL;
673  newec->ec_sources = NIL;
674  newec->ec_derives = NIL;
675  newec->ec_relids = NULL;
676  newec->ec_has_const = false;
678  newec->ec_broken = false;
679  newec->ec_sortref = sortref;
680  newec->ec_min_security = UINT_MAX;
681  newec->ec_max_security = 0;
682  newec->ec_merged = NULL;
683 
684  if (newec->ec_has_volatile && sortref == 0) /* should not happen */
685  elog(ERROR, "volatile EquivalenceClass has no sortref");
686 
687  /*
688  * Get the precise set of relids appearing in the expression.
689  */
690  expr_relids = pull_varnos(root, (Node *) expr);
691 
692  newem = add_eq_member(newec, copyObject(expr), expr_relids,
693  jdomain, NULL, opcintype);
694 
695  /*
696  * add_eq_member doesn't check for volatile functions, set-returning
697  * functions, aggregates, or window functions, but such could appear in
698  * sort expressions; so we have to check whether its const-marking was
699  * correct.
700  */
701  if (newec->ec_has_const)
702  {
703  if (newec->ec_has_volatile ||
704  expression_returns_set((Node *) expr) ||
705  contain_agg_clause((Node *) expr) ||
706  contain_window_function((Node *) expr))
707  {
708  newec->ec_has_const = false;
709  newem->em_is_const = false;
710  }
711  }
712 
713  root->eq_classes = lappend(root->eq_classes, newec);
714 
715  /*
716  * If EC merging is already complete, we have to mop up by adding the new
717  * EC to the eclass_indexes of the relation(s) mentioned in it.
718  */
719  if (root->ec_merging_done)
720  {
721  int ec_index = list_length(root->eq_classes) - 1;
722  int i = -1;
723 
724  while ((i = bms_next_member(newec->ec_relids, i)) > 0)
725  {
726  RelOptInfo *rel = root->simple_rel_array[i];
727 
728  /* ignore the RTE_GROUP RTE */
729  if (i == root->group_rtindex)
730  continue;
731 
732  if (rel == NULL) /* must be an outer join */
733  {
734  Assert(bms_is_member(i, root->outer_join_rels));
735  continue;
736  }
737 
739 
741  ec_index);
742  }
743  }
744 
745  MemoryContextSwitchTo(oldcontext);
746 
747  return newec;
748 }
bool contain_agg_clause(Node *clause)
Definition: clauses.c:177
bool contain_window_function(Node *clause)
Definition: clauses.c:214
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:538
bool expression_returns_set(Node *clause)
Definition: nodeFuncs.c:758
#define copyObject(obj)
Definition: nodes.h:224
#define makeNode(_type_)
Definition: nodes.h:155
#define linitial_node(type, l)
Definition: pg_list.h:181
Index ec_min_security
Definition: pathnodes.h:1403
Index ec_max_security
Definition: pathnodes.h:1404
Relids pull_varnos(PlannerInfo *root, Node *node)
Definition: var.c:113

References add_eq_member(), Assert, bms_add_member(), bms_equal(), bms_is_member(), bms_next_member(), canonicalize_ec_expression(), contain_agg_clause(), contain_volatile_functions(), contain_window_function(), copyObject, EquivalenceClass::ec_broken, EquivalenceClass::ec_collation, EquivalenceClass::ec_derives, EquivalenceClass::ec_has_const, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_max_security, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_min_security, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_relids, EquivalenceClass::ec_sortref, EquivalenceClass::ec_sources, RelOptInfo::eclass_indexes, elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_jdomain, EquivalenceMember::em_relids, equal(), ERROR, expression_returns_set(), i, lappend(), lfirst, linitial_node, list_copy(), list_length(), makeNode, MemoryContextSwitchTo(), NIL, pull_varnos(), RELOPT_BASEREL, RelOptInfo::reloptkind, and root.

Referenced by convert_subquery_pathkeys(), initialize_mergeclause_eclasses(), and make_pathkey_from_sortinfo().

◆ get_useful_group_keys_orderings()

List* get_useful_group_keys_orderings ( PlannerInfo root,
Path path 
)

Definition at line 467 of file pathkeys.c.

468 {
469  Query *parse = root->parse;
470  List *infos = NIL;
471  GroupByOrdering *info;
472 
473  List *pathkeys = root->group_pathkeys;
474  List *clauses = root->processed_groupClause;
475 
476  /* always return at least the original pathkeys/clauses */
477  info = makeNode(GroupByOrdering);
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  {
513  info = makeNode(GroupByOrdering);
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));
535  Assert(list_length(info->pathkeys) == list_length(pinfo->pathkeys));
536  Assert(list_difference(info->clauses, pinfo->clauses) == NIL);
537  Assert(list_difference_ptr(info->pathkeys, pinfo->pathkeys) == 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_ptr(const List *list1, const List *list2)
Definition: list.c:1263
List * list_difference(const List *list1, const List *list2)
Definition: list.c:1237
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:1438

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

3223 {
3224  Bitmapset *matched_ecs;
3225  int i;
3226 
3227  /* Examine only eclasses mentioning rel1 */
3228  matched_ecs = get_eclass_indexes_for_relids(root, rel1->relids);
3229 
3230  i = -1;
3231  while ((i = bms_next_member(matched_ecs, i)) >= 0)
3232  {
3233  EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
3234  i);
3235 
3236  /*
3237  * Won't generate joinclauses if single-member (this test covers the
3238  * volatile case too)
3239  */
3240  if (list_length(ec->ec_members) <= 1)
3241  continue;
3242 
3243  /*
3244  * Per the comment in have_relevant_eclass_joinclause, it's sufficient
3245  * to find an EC that mentions both this rel and some other rel.
3246  */
3247  if (!bms_is_subset(ec->ec_relids, rel1->relids))
3248  return true;
3249  }
3250 
3251  return false;
3252 }

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

2278 {
2279  if (rel->joininfo != NIL || rel->has_eclass_joins)
2280  return true; /* might be able to use pathkeys for merging */
2281  if (root->group_pathkeys != NIL)
2282  return true; /* might be able to use pathkeys for grouping */
2283  if (root->query_pathkeys != NIL)
2284  return true; /* might be able to use them for ordering */
2285  return false; /* definitely useless */
2286 }

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 1307 of file joinrels.c.

1309 {
1310  ListCell *lc;
1311 
1312  foreach(lc, root->placeholder_list)
1313  {
1314  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
1315 
1316  if (!bms_is_subset(phinfo->ph_eval_at, inner_params))
1317  continue; /* ignore, could not be a nestloop param */
1318  if (!bms_overlap(phinfo->ph_eval_at, outer_relids))
1319  continue; /* ignore, not relevant to this join */
1320  if (bms_is_subset(phinfo->ph_eval_at, outer_relids))
1321  continue; /* safe, it can be eval'd within outerrel */
1322  /* Otherwise, it's potentially unsafe, so reject the join */
1323  return true;
1324  }
1325 
1326  /* OK to perform the join */
1327  return false;
1328 }
Relids ph_eval_at
Definition: pathnodes.h:3098

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 1074 of file joinrels.c.

1076 {
1077  bool result = false;
1078  ListCell *l;
1079 
1080  /*
1081  * If either side has a direct lateral reference to the other, attempt the
1082  * join regardless of outer-join considerations.
1083  */
1084  if (bms_overlap(rel1->relids, rel2->direct_lateral_relids) ||
1086  return true;
1087 
1088  /*
1089  * Likewise, if both rels are needed to compute some PlaceHolderVar,
1090  * attempt the join regardless of outer-join considerations. (This is not
1091  * very desirable, because a PHV with a large eval_at set will cause a lot
1092  * of probably-useless joins to be considered, but failing to do this can
1093  * cause us to fail to construct a plan at all.)
1094  */
1095  foreach(l, root->placeholder_list)
1096  {
1097  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
1098 
1099  if (bms_is_subset(rel1->relids, phinfo->ph_eval_at) &&
1100  bms_is_subset(rel2->relids, phinfo->ph_eval_at))
1101  return true;
1102  }
1103 
1104  /*
1105  * It's possible that the rels correspond to the left and right sides of a
1106  * degenerate outer join, that is, one with no joinclause mentioning the
1107  * non-nullable side; in which case we should force the join to occur.
1108  *
1109  * Also, the two rels could represent a clauseless join that has to be
1110  * completed to build up the LHS or RHS of an outer join.
1111  */
1112  foreach(l, root->join_info_list)
1113  {
1114  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
1115 
1116  /* ignore full joins --- other mechanisms handle them */
1117  if (sjinfo->jointype == JOIN_FULL)
1118  continue;
1119 
1120  /* Can we perform the SJ with these rels? */
1121  if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
1122  bms_is_subset(sjinfo->min_righthand, rel2->relids))
1123  {
1124  result = true;
1125  break;
1126  }
1127  if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
1128  bms_is_subset(sjinfo->min_righthand, rel1->relids))
1129  {
1130  result = true;
1131  break;
1132  }
1133 
1134  /*
1135  * Might we need to join these rels to complete the RHS? We have to
1136  * use "overlap" tests since either rel might include a lower SJ that
1137  * has been proven to commute with this one.
1138  */
1139  if (bms_overlap(sjinfo->min_righthand, rel1->relids) &&
1140  bms_overlap(sjinfo->min_righthand, rel2->relids))
1141  {
1142  result = true;
1143  break;
1144  }
1145 
1146  /* Likewise for the LHS. */
1147  if (bms_overlap(sjinfo->min_lefthand, rel1->relids) &&
1148  bms_overlap(sjinfo->min_lefthand, rel2->relids))
1149  {
1150  result = true;
1151  break;
1152  }
1153  }
1154 
1155  /*
1156  * We do not force the join to occur if either input rel can legally be
1157  * joined to anything else using joinclauses. This essentially means that
1158  * clauseless bushy joins are put off as long as possible. The reason is
1159  * that when there is a join order restriction high up in the join tree
1160  * (that is, with many rels inside the LHS or RHS), we would otherwise
1161  * expend lots of effort considering very stupid join combinations within
1162  * its LHS or RHS.
1163  */
1164  if (result)
1165  {
1166  if (has_legal_joinclause(root, rel1) ||
1167  has_legal_joinclause(root, rel2))
1168  result = false;
1169  }
1170 
1171  return result;
1172 }
static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1243
Relids direct_lateral_relids
Definition: pathnodes.h:911

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

3148 {
3149  Bitmapset *matching_ecs;
3150  int i;
3151 
3152  /*
3153  * Examine only eclasses mentioning both rel1 and rel2.
3154  *
3155  * Note that we do not consider the possibility of an eclass generating
3156  * "join" clauses that mention just one of the rels plus an outer join
3157  * that could be formed from them. Although such clauses must be
3158  * correctly enforced when we form the outer join, they don't seem like
3159  * sufficient reason to prioritize this join over other ones. The join
3160  * ordering rules will force the join to be made when necessary.
3161  */
3162  matching_ecs = get_common_eclass_indexes(root, rel1->relids,
3163  rel2->relids);
3164 
3165  i = -1;
3166  while ((i = bms_next_member(matching_ecs, i)) >= 0)
3167  {
3168  EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
3169  i);
3170 
3171  /*
3172  * Sanity check that get_common_eclass_indexes gave only ECs
3173  * containing both rels.
3174  */
3175  Assert(bms_overlap(rel1->relids, ec->ec_relids));
3176  Assert(bms_overlap(rel2->relids, ec->ec_relids));
3177 
3178  /*
3179  * Won't generate joinclauses if single-member (this test covers the
3180  * volatile case too)
3181  */
3182  if (list_length(ec->ec_members) <= 1)
3183  continue;
3184 
3185  /*
3186  * We do not need to examine the individual members of the EC, because
3187  * all that we care about is whether each rel overlaps the relids of
3188  * at least one member, and get_common_eclass_indexes() and the single
3189  * member check above are sufficient to prove that. (As with
3190  * have_relevant_joinclause(), it is not necessary that the EC be able
3191  * to form a joinclause relating exactly the two given rels, only that
3192  * it be able to form a joinclause mentioning both, and this will
3193  * surely be true if both of them overlap ec_relids.)
3194  *
3195  * Note we don't test ec_broken; if we did, we'd need a separate code
3196  * path to look through ec_sources. Checking the membership anyway is
3197  * OK as a possibly-overoptimistic heuristic.
3198  *
3199  * We don't test ec_has_const either, even though a const eclass won't
3200  * generate real join clauses. This is because if we had "WHERE a.x =
3201  * b.y and a.x = 42", it is worth considering a join between a and b,
3202  * since the join result is likely to be small even though it'll end
3203  * up being an unqualified nestloop.
3204  */
3205 
3206  return true;
3207  }
3208 
3209  return false;
3210 }

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 4316 of file indxpath.c.

4319 {
4320  ListCell *lc;
4321 
4322  /* If the index isn't boolean, we can't possibly get a match */
4323  if (!IsBooleanOpfamily(index->opfamily[indexcol]))
4324  return false;
4325 
4326  /* Check each restriction clause for the index's rel */
4327  foreach(lc, index->rel->baserestrictinfo)
4328  {
4329  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
4330 
4331  /*
4332  * As in match_clause_to_indexcol, never match pseudoconstants to
4333  * indexes. (It might be semantically okay to do so here, but the
4334  * odds of getting a match are negligible, so don't waste the cycles.)
4335  */
4336  if (rinfo->pseudoconstant)
4337  continue;
4338 
4339  /* See if we can match the clause's expression to the index column */
4340  if (match_boolean_index_clause(root, rinfo, indexcol, index))
4341  return true;
4342  }
4343 
4344  return false;
4345 }
static bool IsBooleanOpfamily(Oid opfamily)
Definition: indxpath.c:2724
static IndexClause * match_boolean_index_clause(PlannerInfo *root, RestrictInfo *rinfo, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:2749

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 669 of file joinrels.c.

671 {
672  sjinfo->type = T_SpecialJoinInfo;
673  sjinfo->min_lefthand = left_relids;
674  sjinfo->min_righthand = right_relids;
675  sjinfo->syn_lefthand = left_relids;
676  sjinfo->syn_righthand = right_relids;
677  sjinfo->jointype = JOIN_INNER;
678  sjinfo->ojrelid = 0;
679  sjinfo->commute_above_l = NULL;
680  sjinfo->commute_above_r = NULL;
681  sjinfo->commute_below_l = NULL;
682  sjinfo->commute_below_r = NULL;
683  /* we don't bother trying to make the remaining fields valid */
684  sjinfo->lhs_strict = false;
685  sjinfo->semi_can_btree = false;
686  sjinfo->semi_can_hash = false;
687  sjinfo->semi_operators = NIL;
688  sjinfo->semi_rhs_exprs = NIL;
689 }
Relids commute_above_r
Definition: pathnodes.h:2911
Relids syn_lefthand
Definition: pathnodes.h:2906
List * semi_rhs_exprs
Definition: pathnodes.h:2919
Relids syn_righthand
Definition: pathnodes.h:2907
Relids commute_below_r
Definition: pathnodes.h:2913
List * semi_operators
Definition: pathnodes.h:2918

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

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

◆ initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1462 of file pathkeys.c.

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

3325 {
3326  EquivalenceClass *parent_ec = rinfo->parent_ec;
3327  ListCell *lc;
3328 
3329  /* Fail if it's not a potentially-redundant clause from some EC */
3330  if (parent_ec == NULL)
3331  return false;
3332 
3333  foreach(lc, clauselist)
3334  {
3335  RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
3336 
3337  if (otherrinfo->parent_ec == parent_ec)
3338  return true;
3339  }
3340 
3341  return false;
3342 }

References lfirst.

Referenced by create_tidscan_plan().

◆ is_redundant_with_indexclauses()

bool is_redundant_with_indexclauses ( RestrictInfo rinfo,
List indexclauses 
)

Definition at line 3351 of file equivclass.c.

3352 {
3353  EquivalenceClass *parent_ec = rinfo->parent_ec;
3354  ListCell *lc;
3355 
3356  foreach(lc, indexclauses)
3357  {
3358  IndexClause *iclause = lfirst_node(IndexClause, lc);
3359  RestrictInfo *otherrinfo = iclause->rinfo;
3360 
3361  /* If indexclause is lossy, it won't enforce the condition exactly */
3362  if (iclause->lossy)
3363  continue;
3364 
3365  /* Match if it's same clause (pointer equality should be enough) */
3366  if (rinfo == otherrinfo)
3367  return true;
3368  /* Match if derived from same EC */
3369  if (parent_ec && otherrinfo->parent_ec == parent_ec)
3370  return true;
3371 
3372  /*
3373  * No need to look at the derived clauses in iclause->indexquals; they
3374  * couldn't match if the parent clause didn't.
3375  */
3376  }
3377 
3378  return false;
3379 }
struct RestrictInfo * rinfo
Definition: pathnodes.h:1768

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 72 of file joinrels.c.

73 {
74  List **joinrels = root->join_rel_level;
75  ListCell *r;
76  int k;
77 
78  Assert(joinrels[level] == NIL);
79 
80  /* Set join_cur_level so that new joinrels are added to proper list */
81  root->join_cur_level = level;
82 
83  /*
84  * First, consider left-sided and right-sided plans, in which rels of
85  * exactly level-1 member relations are joined against initial relations.
86  * We prefer to join using join clauses, but if we find a rel of level-1
87  * members that has no join clauses, we will generate Cartesian-product
88  * joins against all initial rels not already contained in it.
89  */
90  foreach(r, joinrels[level - 1])
91  {
92  RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
93 
94  if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
95  has_join_restriction(root, old_rel))
96  {
97  int first_rel;
98 
99  /*
100  * There are join clauses or join order restrictions relevant to
101  * this rel, so consider joins between this rel and (only) those
102  * initial rels it is linked to by a clause or restriction.
103  *
104  * At level 2 this condition is symmetric, so there is no need to
105  * look at initial rels before this one in the list; we already
106  * considered such joins when we were at the earlier rel. (The
107  * mirror-image joins are handled automatically by make_join_rel.)
108  * In later passes (level > 2), we join rels of the previous level
109  * to each initial rel they don't already include but have a join
110  * clause or restriction with.
111  */
112  if (level == 2) /* consider remaining initial rels */
113  first_rel = foreach_current_index(r) + 1;
114  else
115  first_rel = 0;
116 
117  make_rels_by_clause_joins(root, old_rel, joinrels[1], first_rel);
118  }
119  else
120  {
121  /*
122  * Oops, we have a relation that is not joined to any other
123  * relation, either directly or by join-order restrictions.
124  * Cartesian product time.
125  *
126  * We consider a cartesian product with each not-already-included
127  * initial rel, whether it has other join clauses or not. At
128  * level 2, if there are two or more clauseless initial rels, we
129  * will redundantly consider joining them in both directions; but
130  * such cases aren't common enough to justify adding complexity to
131  * avoid the duplicated effort.
132  */
134  old_rel,
135  joinrels[1]);
136  }
137  }
138 
139  /*
140  * Now, consider "bushy plans" in which relations of k initial rels are
141  * joined to relations of level-k initial rels, for 2 <= k <= level-2.
142  *
143  * We only consider bushy-plan joins for pairs of rels where there is a
144  * suitable join clause (or join order restriction), in order to avoid
145  * unreasonable growth of planning time.
146  */
147  for (k = 2;; k++)
148  {
149  int other_level = level - k;
150 
151  /*
152  * Since make_join_rel(x, y) handles both x,y and y,x cases, we only
153  * need to go as far as the halfway point.
154  */
155  if (k > other_level)
156  break;
157 
158  foreach(r, joinrels[k])
159  {
160  RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
161  int first_rel;
162  ListCell *r2;
163 
164  /*
165  * We can ignore relations without join clauses here, unless they
166  * participate in join-order restrictions --- then we might have
167  * to force a bushy join plan.
168  */
169  if (old_rel->joininfo == NIL && !old_rel->has_eclass_joins &&
170  !has_join_restriction(root, old_rel))
171  continue;
172 
173  if (k == other_level) /* only consider remaining rels */
174  first_rel = foreach_current_index(r) + 1;
175  else
176  first_rel = 0;
177 
178  for_each_from(r2, joinrels[other_level], first_rel)
179  {
180  RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
181 
182  if (!bms_overlap(old_rel->relids, new_rel->relids))
183  {
184  /*
185  * OK, we can build a rel of the right level from this
186  * pair of rels. Do so if there is at least one relevant
187  * join clause or join order restriction.
188  */
189  if (have_relevant_joinclause(root, old_rel, new_rel) ||
190  have_join_order_restriction(root, old_rel, new_rel))
191  {
192  (void) make_join_rel(root, old_rel, new_rel);
193  }
194  }
195  }
196  }
197  }
198 
199  /*----------
200  * Last-ditch effort: if we failed to find any usable joins so far, force
201  * a set of cartesian-product joins to be generated. This handles the
202  * special case where all the available rels have join clauses but we
203  * cannot use any of those clauses yet. This can only happen when we are
204  * considering a join sub-problem (a sub-joinlist) and all the rels in the
205  * sub-problem have only join clauses with rels outside the sub-problem.
206  * An example is
207  *
208  * SELECT ... FROM a INNER JOIN b ON TRUE, c, d, ...
209  * WHERE a.w = c.x and b.y = d.z;
210  *
211  * If the "a INNER JOIN b" sub-problem does not get flattened into the
212  * upper level, we must be willing to make a cartesian join of a and b;
213  * but the code above will not have done so, because it thought that both
214  * a and b have joinclauses. We consider only left-sided and right-sided
215  * cartesian joins in this case (no bushy).
216  *----------
217  */
218  if (joinrels[level] == NIL)
219  {
220  /*
221  * This loop is just like the first one, except we always call
222  * make_rels_by_clauseless_joins().
223  */
224  foreach(r, joinrels[level - 1])
225  {
226  RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
227 
229  old_rel,
230  joinrels[1]);
231  }
232 
233  /*----------
234  * When special joins are involved, there may be no legal way
235  * to make an N-way join for some values of N. For example consider
236  *
237  * SELECT ... FROM t1 WHERE
238  * x IN (SELECT ... FROM t2,t3 WHERE ...) AND
239  * y IN (SELECT ... FROM t4,t5 WHERE ...)
240  *
241  * We will flatten this query to a 5-way join problem, but there are
242  * no 4-way joins that join_is_legal() will consider legal. We have
243  * to accept failure at level 4 and go on to discover a workable
244  * bushy plan at level 5.
245  *
246  * However, if there are no special joins and no lateral references
247  * then join_is_legal() should never fail, and so the following sanity
248  * check is useful.
249  *----------
250  */
251  if (joinrels[level] == NIL &&
252  root->join_info_list == NIL &&
253  !root->hasLateralRTEs)
254  elog(ERROR, "failed to build any %d-way joins", level);
255  }
256 }
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:313
RelOptInfo * make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:704
bool have_join_order_restriction(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:1074
static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1187
static void make_rels_by_clause_joins(PlannerInfo *root, RelOptInfo *old_rel, List *other_rels, int first_rel_idx)
Definition: joinrels.c:279
#define foreach_current_index(var_or_cell)
Definition: pg_list.h:403

References Assert, bms_overlap(), elog, ERROR, for_each_from, foreach_current_index, RelOptInfo::has_eclass_joins, has_join_restriction(), have_join_order_restriction(), have_relevant_joinclause(), RelOptInfo::joininfo, lfirst, make_join_rel(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), NIL, RelOptInfo::relids, and root.

Referenced by standard_join_search().

◆ make_canonical_pathkey()

PathKey* make_canonical_pathkey ( PlannerInfo root,
EquivalenceClass eclass,
Oid  opfamily,
int  strategy,
bool  nulls_first 
)

Definition at line 56 of file pathkeys.c.

59 {
60  PathKey *pk;
61  ListCell *lc;
62  MemoryContext oldcontext;
63 
64  /* Can't make canonical pathkeys if the set of ECs might still change */
65  if (!root->ec_merging_done)
66  elog(ERROR, "too soon to build canonical pathkeys");
67 
68  /* The passed eclass might be non-canonical, so chase up to the top */
69  while (eclass->ec_merged)
70  eclass = eclass->ec_merged;
71 
72  foreach(lc, root->canon_pathkeys)
73  {
74  pk = (PathKey *) lfirst(lc);
75  if (eclass == pk->pk_eclass &&
76  opfamily == pk->pk_opfamily &&
77  strategy == pk->pk_strategy &&
78  nulls_first == pk->pk_nulls_first)
79  return pk;
80  }
81 
82  /*
83  * Be sure canonical pathkeys are allocated in the main planning context.
84  * Not an issue in normal planning, but it is for GEQO.
85  */
86  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
87 
88  pk = makeNode(PathKey);
89  pk->pk_eclass = eclass;
90  pk->pk_opfamily = opfamily;
91  pk->pk_strategy = strategy;
92  pk->pk_nulls_first = nulls_first;
93 
94  root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
95 
96  MemoryContextSwitchTo(oldcontext);
97 
98  return pk;
99 }

References eclass(), elog, ERROR, lappend(), lfirst, makeNode, MemoryContextSwitchTo(), PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, and root.

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

◆ make_inner_pathkeys_for_merge()

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

Definition at line 1854 of file pathkeys.c.

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

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

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

◆ make_join_rel()

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

Definition at line 704 of file joinrels.c.

705 {
706  Relids joinrelids;
707  SpecialJoinInfo *sjinfo;
708  bool reversed;
709  List *pushed_down_joins = NIL;
710  SpecialJoinInfo sjinfo_data;
711  RelOptInfo *joinrel;
712  List *restrictlist;
713 
714  /* We should never try to join two overlapping sets of rels. */
715  Assert(!bms_overlap(rel1->relids, rel2->relids));
716 
717  /* Construct Relids set that identifies the joinrel (without OJ as yet). */
718  joinrelids = bms_union(rel1->relids, rel2->relids);
719 
720  /* Check validity and determine join type. */
721  if (!join_is_legal(root, rel1, rel2, joinrelids,
722  &sjinfo, &reversed))
723  {
724  /* invalid join path */
725  bms_free(joinrelids);
726  return NULL;
727  }
728 
729  /*
730  * Add outer join relid(s) to form the canonical relids. Any added outer
731  * joins besides sjinfo itself are appended to pushed_down_joins.
732  */
733  joinrelids = add_outer_joins_to_relids(root, joinrelids, sjinfo,
734  &pushed_down_joins);
735 
736  /* Swap rels if needed to match the join info. */
737  if (reversed)
738  {
739  RelOptInfo *trel = rel1;
740 
741  rel1 = rel2;
742  rel2 = trel;
743  }
744 
745  /*
746  * If it's a plain inner join, then we won't have found anything in
747  * join_info_list. Make up a SpecialJoinInfo so that selectivity
748  * estimation functions will know what's being joined.
749  */
750  if (sjinfo == NULL)
751  {
752  sjinfo = &sjinfo_data;
753  init_dummy_sjinfo(sjinfo, rel1->relids, rel2->relids);
754  }
755 
756  /*
757  * Find or build the join RelOptInfo, and compute the restrictlist that
758  * goes with this particular joining.
759  */
760  joinrel = build_join_rel(root, joinrelids, rel1, rel2,
761  sjinfo, pushed_down_joins,
762  &restrictlist);
763 
764  /*
765  * If we've already proven this join is empty, we needn't consider any
766  * more paths for it.
767  */
768  if (is_dummy_rel(joinrel))
769  {
770  bms_free(joinrelids);
771  return joinrel;
772  }
773 
774  /* Add paths to the join relation. */
775  populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo,
776  restrictlist);
777 
778  bms_free(joinrelids);
779 
780  return joinrel;
781 }
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:893
bool is_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1335
void init_dummy_sjinfo(SpecialJoinInfo *sjinfo, Relids left_relids, Relids right_relids)
Definition: joinrels.c:669
static bool join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, Relids joinrelids, SpecialJoinInfo **sjinfo_p, bool *reversed_p)
Definition: joinrels.c:349
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:3317
unsigned int Index
Definition: c.h:619
BlockNumber pages
Definition: pathnodes.h:948

References Assert, bms_equal(), IS_DUMMY_REL, IS_SIMPLE_REL, make_rel_from_joinlist(), RelOptInfo::pages, RelOptInfo::relid, RelOptInfo::relids, root, set_base_rel_consider_startup(), set_base_rel_pathlists(), and set_base_rel_sizes().

Referenced by query_planner().

◆ make_pathkeys_for_sortclauses()

List* make_pathkeys_for_sortclauses ( PlannerInfo root,
List sortclauses,
List tlist 
)

Definition at line 1335 of file pathkeys.c.

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

References Assert, make_pathkeys_for_sortclauses_extended(), and root.

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

◆ make_pathkeys_for_sortclauses_extended()

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

Definition at line 1380 of file pathkeys.c.

1387 {
1388  List *pathkeys = NIL;
1389  ListCell *l;
1390 
1391  *sortable = true;
1392  foreach(l, *sortclauses)
1393  {
1394  SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
1395  Expr *sortkey;
1396  PathKey *pathkey;
1397 
1398  sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
1399  if (!OidIsValid(sortcl->sortop))
1400  {
1401  *sortable = false;
1402  continue;
1403  }
1404  if (remove_group_rtindex)
1405  {
1406  Assert(root->group_rtindex > 0);
1407  sortkey = (Expr *)
1408  remove_nulling_relids((Node *) sortkey,
1409  bms_make_singleton(root->group_rtindex),
1410  NULL);
1411  }
1412  pathkey = make_pathkey_from_sortop(root,
1413  sortkey,
1414  sortcl->sortop,
1415  sortcl->reverse_sort,
1416  sortcl->nulls_first,
1417  sortcl->tleSortGroupRef,
1418  true);
1419  if (pathkey->pk_eclass->ec_sortref == 0 && set_ec_sortref)
1420  {
1421  /*
1422  * Copy the sortref if it hasn't been set yet. That may happen if
1423  * the EquivalenceClass was constructed from a WHERE clause, i.e.
1424  * it doesn't have a target reference at all.
1425  */
1426  pathkey->pk_eclass->ec_sortref = sortcl->tleSortGroupRef;
1427  }
1428 
1429  /* Canonical form eliminates redundant ordering keys */
1430  if (!pathkey_is_redundant(pathkey, pathkeys))
1431  pathkeys = lappend(pathkeys, pathkey);
1432  else if (remove_redundant)
1433  *sortclauses = foreach_delete_current(*sortclauses, l);
1434  }
1435  return pathkeys;
1436 }
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:216
static PathKey * make_pathkey_from_sortop(PlannerInfo *root, Expr *expr, Oid ordering_op, bool reverse_sort, bool nulls_first, Index sortref, bool create_it)
Definition: pathkeys.c:256
#define foreach_delete_current(lst, var_or_cell)
Definition: pg_list.h:391
Node * remove_nulling_relids(Node *node, const Bitmapset *removable_relids, const Bitmapset *except_relids)
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:379

References Assert, bms_make_singleton(), foreach_delete_current, get_sortgroupclause_expr(), lappend(), lfirst, make_pathkey_from_sortop(), NIL, SortGroupClause::nulls_first, OidIsValid, pathkey_is_redundant(), remove_nulling_relids(), SortGroupClause::reverse_sort, root, SortGroupClause::sortop, and SortGroupClause::tleSortGroupRef.

Referenced by make_pathkeys_for_sortclauses(), make_pathkeys_for_window(), and standard_qp_callback().

◆ mark_dummy_rel()

void mark_dummy_rel ( RelOptInfo rel)

Definition at line 1384 of file joinrels.c.

1385 {
1386  MemoryContext oldcontext;
1387 
1388  /* Already marked? */
1389  if (is_dummy_rel(rel))
1390  return;
1391 
1392  /* No, so choose correct context to make the dummy path in */
1393  oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
1394 
1395  /* Set dummy size estimate */
1396  rel->rows = 0;
1397 
1398  /* Evict any previously chosen paths */
1399  rel->pathlist = NIL;
1400  rel->partial_pathlist = NIL;
1401 
1402  /* Set up the dummy path */
1403  add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NIL,
1404  NIL, rel->lateral_relids,
1405  0, false, -1));
1406 
1407  /* Set or update cheapest_total_path and related fields */
1408  set_cheapest(rel);
1409 
1410  MemoryContextSwitchTo(oldcontext);
1411 }
MemoryContext GetMemoryChunkContext(void *pointer)
Definition: mcxt.c:707
Cardinality rows
Definition: pathnodes.h:877

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

2562 {
2563  Index var1varno = fkinfo->con_relid;
2564  AttrNumber var1attno = fkinfo->conkey[colno];
2565  Index var2varno = fkinfo->ref_relid;
2566  AttrNumber var2attno = fkinfo->confkey[colno];
2567  Oid eqop = fkinfo->conpfeqop[colno];
2568  RelOptInfo *rel1 = root->simple_rel_array[var1varno];
2569  RelOptInfo *rel2 = root->simple_rel_array[var2varno];
2570  List *opfamilies = NIL; /* compute only if needed */
2571  Bitmapset *matching_ecs;
2572  int i;
2573 
2574  /* Consider only eclasses mentioning both relations */
2575  Assert(root->ec_merging_done);
2576  Assert(IS_SIMPLE_REL(rel1));
2577  Assert(IS_SIMPLE_REL(rel2));
2578  matching_ecs = bms_intersect(rel1->eclass_indexes,
2579  rel2->eclass_indexes);
2580 
2581  i = -1;
2582  while ((i = bms_next_member(matching_ecs, i)) >= 0)
2583  {
2584  EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
2585  i);
2586  EquivalenceMember *item1_em = NULL;
2587  EquivalenceMember *item2_em = NULL;
2588  ListCell *lc2;
2589 
2590  /* Never match to a volatile EC */
2591  if (ec->ec_has_volatile)
2592  continue;
2593  /* It's okay to consider "broken" ECs here, see exprs_known_equal */
2594 
2595  foreach(lc2, ec->ec_members)
2596  {
2598  Var *var;
2599 
2600  if (em->em_is_child)
2601  continue; /* ignore children here */
2602 
2603  /* EM must be a Var, possibly with RelabelType */
2604  var = (Var *) em->em_expr;
2605  while (var && IsA(var, RelabelType))
2606  var = (Var *) ((RelabelType *) var)->arg;
2607  if (!(var && IsA(var, Var)))
2608  continue;
2609 
2610  /* Match? */
2611  if (var->varno == var1varno && var->varattno == var1attno)
2612  item1_em = em;
2613  else if (var->varno == var2varno && var->varattno == var2attno)
2614  item2_em = em;
2615 
2616  /* Have we found both PK and FK column in this EC? */
2617  if (item1_em && item2_em)
2618  {
2619  /*
2620  * Succeed if eqop matches EC's opfamilies. We could test
2621  * this before scanning the members, but it's probably cheaper
2622  * to test for member matches first.
2623  */
2624  if (opfamilies == NIL) /* compute if we didn't already */
2625  opfamilies = get_mergejoin_opfamilies(eqop);
2626  if (equal(opfamilies, ec->ec_opfamilies))
2627  {
2628  fkinfo->eclass[colno] = ec;
2629  fkinfo->fk_eclass_member[colno] = item2_em;
2630  return ec;
2631  }
2632  /* Otherwise, done with this EC, move on to the next */
2633  break;
2634  }
2635  }
2636  }
2637  return NULL;
2638 }
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:366
while(p+4<=pend)
struct EquivalenceClass * eclass[INDEX_MAX_KEYS]
Definition: pathnodes.h:1259
struct EquivalenceMember * fk_eclass_member[INDEX_MAX_KEYS]
Definition: pathnodes.h:1261
AttrNumber varattno
Definition: primnodes.h:260
int varno
Definition: primnodes.h:255

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 4367 of file indxpath.c.

4370 {
4371  int indkey;
4372 
4373  /*
4374  * Ignore any RelabelType node above the operand. This is needed to be
4375  * able to apply indexscanning in binary-compatible-operator cases. Note:
4376  * we can assume there is at most one RelabelType node;
4377  * eval_const_expressions() will have simplified if more than one.
4378  */
4379  if (operand && IsA(operand, RelabelType))
4380  operand = (Node *) ((RelabelType *) operand)->arg;
4381 
4382  indkey = index->indexkeys[indexcol];
4383  if (indkey != 0)
4384  {
4385  /*
4386  * Simple index column; operand must be a matching Var.
4387  */
4388  if (operand && IsA(operand, Var) &&
4389  index->rel->relid == ((Var *) operand)->varno &&
4390  indkey == ((Var *) operand)->varattno &&
4391  ((Var *) operand)->varnullingrels == NULL)
4392  return true;
4393  }
4394  else
4395  {
4396  /*
4397  * Index expression; find the correct expression. (This search could
4398  * be avoided, at the cost of complicating all the callers of this
4399  * routine; doesn't seem worth it.)
4400  */
4401  ListCell *indexpr_item;
4402  int i;
4403  Node *indexkey;
4404 
4405  indexpr_item = list_head(index->indexprs);
4406  for (i = 0; i < indexcol; i++)
4407  {
4408  if (index->indexkeys[i] == 0)
4409  {
4410  if (indexpr_item == NULL)
4411  elog(ERROR, "wrong number of index expressions");
4412  indexpr_item = lnext(index->indexprs, indexpr_item);
4413  }
4414  }
4415  if (indexpr_item == NULL)
4416  elog(ERROR, "wrong number of index expressions");
4417  indexkey = (Node *) lfirst(indexpr_item);
4418 
4419  /*
4420  * Does it match the operand? Again, strip any relabeling.
4421  */
4422  if (indexkey && IsA(indexkey, RelabelType))
4423  indexkey = (Node *) ((RelabelType *) indexkey)->arg;
4424 
4425  if (equal(indexkey, operand))
4426  return true;
4427  }
4428 
4429  return false;
4430 }

References arg, elog, equal(), ERROR, i, IsA, lfirst, list_head(), and lnext().

Referenced by ec_member_matches_indexcol(), expand_indexqual_rowcompare(), get_actual_variable_range(), group_similar_or_args(), match_boolean_index_clause(), match_clause_to_indexcol(), match_clause_to_ordering_op(), match_funcclause_to_indexcol(), match_opclause_to_indexcol(), match_orclause_to_indexcol(), match_rowcompare_to_indexcol(), match_saopclause_to_indexcol(), and relation_has_unique_index_for().

◆ pathkeys_contained_in()

◆ 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_final_distinct_paths(), create_mergejoin_plan(), create_one_window_path(), create_ordered_paths(), create_partial_distinct_paths(), create_window_paths(), gather_grouping_paths(), generate_useful_gather_paths(), initial_cost_mergejoin(), make_ordered_path(), pathkeys_useful_for_ordering(), and pathkeys_useful_for_setop().

◆ process_equivalence()

bool process_equivalence ( PlannerInfo root,
RestrictInfo **  p_restrictinfo,
JoinDomain jdomain 
)

Definition at line 117 of file equivclass.c.

120 {
121  RestrictInfo *restrictinfo = *p_restrictinfo;
122  Expr *clause = restrictinfo->clause;
123  Oid opno,
124  collation,
125  item1_type,
126  item2_type;
127  Expr *item1;
128  Expr *item2;
129  Relids item1_relids,
130  item2_relids;
131  List *opfamilies;
132  EquivalenceClass *ec1,
133  *ec2;
134  EquivalenceMember *em1,
135  *em2;
136  ListCell *lc1;
137  int ec2_idx;
138 
139  /* Should not already be marked as having generated an eclass */
140  Assert(restrictinfo->left_ec == NULL);
141  Assert(restrictinfo->right_ec == NULL);
142 
143  /* Reject if it is potentially postponable by security considerations */
144  if (restrictinfo->security_level > 0 && !restrictinfo->leakproof)
145  return false;
146 
147  /* Extract info from given clause */
148  Assert(is_opclause(clause));
149  opno = ((OpExpr *) clause)->opno;
150  collation = ((OpExpr *) clause)->inputcollid;
151  item1 = (Expr *) get_leftop(clause);
152  item2 = (Expr *) get_rightop(clause);
153  item1_relids = restrictinfo->left_relids;
154  item2_relids = restrictinfo->right_relids;
155 
156  /*
157  * Ensure both input expressions expose the desired collation (their types
158  * should be OK already); see comments for canonicalize_ec_expression.
159  */
160  item1 = canonicalize_ec_expression(item1,
161  exprType((Node *) item1),
162  collation);
163  item2 = canonicalize_ec_expression(item2,
164  exprType((Node *) item2),
165  collation);
166 
167  /*
168  * Clauses of the form X=X cannot be translated into EquivalenceClasses.
169  * We'd either end up with a single-entry EC, losing the knowledge that
170  * the clause was present at all, or else make an EC with duplicate
171  * entries, causing other issues.
172  */
173  if (equal(item1, item2))
174  {
175  /*
176  * If the operator is strict, then the clause can be treated as just
177  * "X IS NOT NULL". (Since we know we are considering a top-level
178  * qual, we can ignore the difference between FALSE and NULL results.)
179  * It's worth making the conversion because we'll typically get a much
180  * better selectivity estimate than we would for X=X.
181  *
182  * If the operator is not strict, we can't be sure what it will do
183  * with NULLs, so don't attempt to optimize it.
184  */
185  set_opfuncid((OpExpr *) clause);
186  if (func_strict(((OpExpr *) clause)->opfuncid))
187  {
188  NullTest *ntest = makeNode(NullTest);
189 
190  ntest->arg = item1;
191  ntest->nulltesttype = IS_NOT_NULL;
192  ntest->argisrow = false; /* correct even if composite arg */
193  ntest->location = -1;
194 
195  *p_restrictinfo =
197  (Expr *) ntest,
198  restrictinfo->is_pushed_down,
199  restrictinfo->has_clone,
200  restrictinfo->is_clone,
201  restrictinfo->pseudoconstant,
202  restrictinfo->security_level,
203  NULL,
204  restrictinfo->incompatible_relids,
205  restrictinfo->outer_relids);
206  }
207  return false;
208  }
209 
210  /*
211  * We use the declared input types of the operator, not exprType() of the
212  * inputs, as the nominal datatypes for opfamily lookup. This presumes
213  * that btree operators are always registered with amoplefttype and
214  * amoprighttype equal to their declared input types. We will need this
215  * info anyway to build EquivalenceMember nodes, and by extracting it now
216  * we can use type comparisons to short-circuit some equal() tests.
217  */
218  op_input_types(opno, &item1_type, &item2_type);
219 
220  opfamilies = restrictinfo->mergeopfamilies;
221 
222  /*
223  * Sweep through the existing EquivalenceClasses looking for matches to
224  * item1 and item2. These are the possible outcomes:
225  *
226  * 1. We find both in the same EC. The equivalence is already known, so
227  * there's nothing to do.
228  *
229  * 2. We find both in different ECs. Merge the two ECs together.
230  *
231  * 3. We find just one. Add the other to its EC.
232  *
233  * 4. We find neither. Make a new, two-entry EC.
234  *
235  * Note: since all ECs are built through this process or the similar
236  * search in get_eclass_for_sort_expr(), it's impossible that we'd match
237  * an item in more than one existing nonvolatile EC. So it's okay to stop
238  * at the first match.
239  */
240  ec1 = ec2 = NULL;
241  em1 = em2 = NULL;
242  ec2_idx = -1;
243  foreach(lc1, root->eq_classes)
244  {
245  EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
246  ListCell *lc2;
247 
248  /* Never match to a volatile EC */
249  if (cur_ec->ec_has_volatile)
250  continue;
251 
252  /*
253  * The collation has to match; check this first since it's cheaper
254  * than the opfamily comparison.
255  */
256  if (collation != cur_ec->ec_collation)
257  continue;
258 
259  /*
260  * A "match" requires matching sets of btree opfamilies. Use of
261  * equal() for this test has implications discussed in the comments
262  * for get_mergejoin_opfamilies().
263  */
264  if (!equal(opfamilies, cur_ec->ec_opfamilies))
265  continue;
266 
267  foreach(lc2, cur_ec->ec_members)
268  {
269  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
270 
271  Assert(!cur_em->em_is_child); /* no children yet */
272 
273  /*
274  * Match constants only within the same JoinDomain (see
275  * optimizer/README).
276  */
277  if (cur_em->em_is_const && cur_em->em_jdomain != jdomain)
278  continue;
279 
280  if (!ec1 &&
281  item1_type == cur_em->em_datatype &&
282  equal(item1, cur_em->em_expr))
283  {
284  ec1 = cur_ec;
285  em1 = cur_em;
286  if (ec2)
287  break;
288  }
289 
290  if (!ec2 &&
291  item2_type == cur_em->em_datatype &&
292  equal(item2, cur_em->em_expr))
293  {
294  ec2 = cur_ec;
295  ec2_idx = foreach_current_index(lc1);
296  em2 = cur_em;
297  if (ec1)
298  break;
299  }
300  }
301 
302  if (ec1 && ec2)
303  break;
304  }
305 
306  /* Sweep finished, what did we find? */
307 
308  if (ec1 && ec2)
309  {
310  /* If case 1, nothing to do, except add to sources */
311  if (ec1 == ec2)
312  {
313  ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
314  ec1->ec_min_security = Min(ec1->ec_min_security,
315  restrictinfo->security_level);
316  ec1->ec_max_security = Max(ec1->ec_max_security,
317  restrictinfo->security_level);
318  /* mark the RI as associated with this eclass */
319  restrictinfo->left_ec = ec1;
320  restrictinfo->right_ec = ec1;
321  /* mark the RI as usable with this pair of EMs */
322  restrictinfo->left_em = em1;
323  restrictinfo->right_em = em2;
324  return true;
325  }
326 
327  /*
328  * Case 2: need to merge ec1 and ec2. This should never happen after
329  * the ECs have reached canonical state; otherwise, pathkeys could be
330  * rendered non-canonical by the merge, and relation eclass indexes
331  * would get broken by removal of an eq_classes list entry.
332  */
333  if (root->ec_merging_done)
334  elog(ERROR, "too late to merge equivalence classes");
335 
336  /*
337  * We add ec2's items to ec1, then set ec2's ec_merged link to point
338  * to ec1 and remove ec2 from the eq_classes list. We cannot simply
339  * delete ec2 because that could leave dangling pointers in existing
340  * PathKeys. We leave it behind with a link so that the merged EC can
341  * be found.
342  */
343  ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
344  ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
345  ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
346  ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
347  ec1->ec_has_const |= ec2->ec_has_const;
348  /* can't need to set has_volatile */
349  ec1->ec_min_security = Min(ec1->ec_min_security,
350  ec2->ec_min_security);
351  ec1->ec_max_security = Max(ec1->ec_max_security,
352  ec2->ec_max_security);
353  ec2->ec_merged = ec1;
354  root->eq_classes = list_delete_nth_cell(root->eq_classes, ec2_idx);
355  /* just to avoid debugging confusion w/ dangling pointers: */
356  ec2->ec_members = NIL;
357  ec2->ec_sources = NIL;
358  ec2->ec_derives = NIL;
359  ec2->ec_relids = NULL;
360  ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
361  ec1->ec_min_security = Min(ec1->ec_min_security,
362  restrictinfo->security_level);
363  ec1->ec_max_security = Max(ec1->ec_max_security,
364  restrictinfo->security_level);
365  /* mark the RI as associated with this eclass */
366  restrictinfo->left_ec = ec1;
367  restrictinfo->right_ec = ec1;
368  /* mark the RI as usable with this pair of EMs */
369  restrictinfo->left_em = em1;
370  restrictinfo->right_em = em2;
371  }
372  else if (ec1)
373  {
374  /* Case 3: add item2 to ec1 */
375  em2 = add_eq_member(ec1, item2, item2_relids,
376  jdomain, NULL, item2_type);
377  ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
378  ec1->ec_min_security = Min(ec1->ec_min_security,
379  restrictinfo->security_level);
380  ec1->ec_max_security = Max(ec1->ec_max_security,
381  restrictinfo->security_level);
382  /* mark the RI as associated with this eclass */
383  restrictinfo->left_ec = ec1;
384  restrictinfo->right_ec = ec1;
385  /* mark the RI as usable with this pair of EMs */
386  restrictinfo->left_em = em1;
387  restrictinfo->right_em = em2;
388  }
389  else if (ec2)
390  {
391  /* Case 3: add item1 to ec2 */
392  em1 = add_eq_member(ec2, item1, item1_relids,
393  jdomain, NULL, item1_type);
394  ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
395  ec2->ec_min_security = Min(ec2->ec_min_security,
396  restrictinfo->security_level);
397  ec2->ec_max_security = Max(ec2->ec_max_security,
398  restrictinfo->security_level);
399  /* mark the RI as associated with this eclass */
400  restrictinfo->left_ec = ec2;
401  restrictinfo->right_ec = ec2;
402  /* mark the RI as usable with this pair of EMs */
403  restrictinfo->left_em = em1;
404  restrictinfo->right_em = em2;
405  }
406  else
407  {
408  /* Case 4: make a new, two-entry EC */
410 
411  ec->ec_opfamilies = opfamilies;
412  ec->ec_collation = collation;
413  ec->ec_members = NIL;
414  ec->ec_sources = list_make1(restrictinfo);
415  ec->ec_derives = NIL;
416  ec->ec_relids = NULL;
417  ec->ec_has_const = false;
418  ec->ec_has_volatile = false;
419  ec->ec_broken = false;
420  ec->ec_sortref = 0;
421  ec->ec_min_security = restrictinfo->security_level;
422  ec->ec_max_security = restrictinfo->security_level;
423  ec->ec_merged = NULL;
424  em1 = add_eq_member(ec, item1, item1_relids,
425  jdomain, NULL, item1_type);
426  em2 = add_eq_member(ec, item2, item2_relids,
427  jdomain, NULL, item2_type);
428 
429  root->eq_classes = lappend(root->eq_classes, ec);
430 
431  /* mark the RI as associated with this eclass */
432  restrictinfo->left_ec = ec;
433  restrictinfo->right_ec = ec;
434  /* mark the RI as usable with this pair of EMs */
435  restrictinfo->left_em = em1;
436  restrictinfo->right_em = em2;
437  }
438 
439  return true;
440 }
List * list_delete_nth_cell(List *list, int n)
Definition: list.c:767
bool func_strict(Oid funcid)
Definition: lsyscache.c:1761
void set_opfuncid(OpExpr *opexpr)
Definition: nodeFuncs.c:1861
static bool is_opclause(const void *clause)
Definition: nodeFuncs.h:76
@ IS_NOT_NULL
Definition: primnodes.h:1952
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:1959
ParseLoc location
Definition: primnodes.h:1962
Expr * arg
Definition: primnodes.h:1958
bool is_pushed_down
Definition: pathnodes.h:2577
Index security_level
Definition: pathnodes.h:2596
Relids outer_relids
Definition: pathnodes.h:2611
Relids incompatible_relids
Definition: pathnodes.h:2608
bool has_clone
Definition: pathnodes.h:2586

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

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

◆ rebuild_eclass_attr_needed()

void rebuild_eclass_attr_needed ( PlannerInfo root)

Definition at line 2431 of file equivclass.c.

2432 {
2433  ListCell *lc;
2434 
2435  foreach(lc, root->eq_classes)
2436  {
2438 
2439  /* Need do anything only for a multi-member, no-const EC. */
2440  if (list_length(ec->ec_members) > 1 && !ec->ec_has_const)
2441  {
2442  ListCell *lc2;
2443 
2444  foreach(lc2, ec->ec_members)
2445  {
2446  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
2447  List *vars = pull_var_clause((Node *) cur_em->em_expr,
2451 
2453  list_free(vars);
2454  }
2455  }
2456  }
2457 }
void add_vars_to_attr_needed(PlannerInfo *root, List *vars, Relids where_needed)
Definition: initsplan.c:352
#define PVC_RECURSE_AGGREGATES
Definition: optimizer.h:187
#define PVC_RECURSE_WINDOWFUNCS
Definition: optimizer.h:189
Definition: regcomp.c:282

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

Referenced by remove_rel_from_query().

◆ reconsider_outer_join_clauses()

void reconsider_outer_join_clauses ( PlannerInfo root)

Definition at line 2001 of file equivclass.c.

2002 {
2003  bool found;
2004  ListCell *cell;
2005 
2006  /* Outer loop repeats until we find no more deductions */
2007  do
2008  {
2009  found = false;
2010 
2011  /* Process the LEFT JOIN clauses */
2012  foreach(cell, root->left_join_clauses)
2013  {
2014  OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2015 
2016  if (reconsider_outer_join_clause(root, ojcinfo, true))
2017  {
2018  RestrictInfo *rinfo = ojcinfo->rinfo;
2019 
2020  found = true;
2021  /* remove it from the list */
2022  root->left_join_clauses =
2023  foreach_delete_current(root->left_join_clauses, cell);
2024  /* throw back a dummy replacement clause (see notes above) */
2025  rinfo = make_restrictinfo(root,
2026  (Expr *) makeBoolConst(true, false),
2027  rinfo->is_pushed_down,
2028  rinfo->has_clone,
2029  rinfo->is_clone,
2030  false, /* pseudoconstant */
2031  0, /* security_level */
2032  rinfo->required_relids,
2033  rinfo->incompatible_relids,
2034  rinfo->outer_relids);
2036  }
2037  }
2038 
2039  /* Process the RIGHT JOIN clauses */
2040  foreach(cell, root->right_join_clauses)
2041  {
2042  OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2043 
2044  if (reconsider_outer_join_clause(root, ojcinfo, false))
2045  {
2046  RestrictInfo *rinfo = ojcinfo->rinfo;
2047 
2048  found = true;
2049  /* remove it from the list */
2050  root->right_join_clauses =
2051  foreach_delete_current(root->right_join_clauses, cell);
2052  /* throw back a dummy replacement clause (see notes above) */
2053  rinfo = make_restrictinfo(root,
2054  (Expr *) makeBoolConst(true, false),
2055  rinfo->is_pushed_down,
2056  rinfo->has_clone,
2057  rinfo->is_clone,
2058  false, /* pseudoconstant */
2059  0, /* security_level */
2060  rinfo->required_relids,
2061  rinfo->incompatible_relids,
2062  rinfo->outer_relids);
2064  }
2065  }
2066 
2067  /* Process the FULL JOIN clauses */
2068  foreach(cell, root->full_join_clauses)
2069  {
2070  OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2071 
2072  if (reconsider_full_join_clause(root, ojcinfo))
2073  {
2074  RestrictInfo *rinfo = ojcinfo->rinfo;
2075 
2076  found = true;
2077  /* remove it from the list */
2078  root->full_join_clauses =
2079  foreach_delete_current(root->full_join_clauses, cell);
2080  /* throw back a dummy replacement clause (see notes above) */
2081  rinfo = make_restrictinfo(root,
2082  (Expr *) makeBoolConst(true, false),
2083  rinfo->is_pushed_down,
2084  rinfo->has_clone,
2085  rinfo->is_clone,
2086  false, /* pseudoconstant */
2087  0, /* security_level */
2088  rinfo->required_relids,
2089  rinfo->incompatible_relids,
2090  rinfo->outer_relids);
2092  }
2093  }
2094  } while (found);
2095 
2096  /* Now, any remaining clauses have to be thrown back */
2097  foreach(cell, root->left_join_clauses)
2098  {
2099  OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2100 
2102  }
2103  foreach(cell, root->right_join_clauses)
2104  {
2105  OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2106 
2108  }
2109  foreach(cell, root->full_join_clauses)
2110  {
2111  OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
2112 
2114  }
2115 }
static bool reconsider_outer_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo, bool outer_on_left)
Definition: equivclass.c:2123
static bool reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo)
Definition: equivclass.c:2246
void distribute_restrictinfo_to_rels(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: initsplan.c:2954
Node * makeBoolConst(bool value, bool isnull)
Definition: makefuncs.c:359
RestrictInfo * rinfo
Definition: pathnodes.h:2933
Relids required_relids
Definition: pathnodes.h:2605

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

923 {
924  PathTarget *target = rel->reltarget;
925  EquivalenceMember *em;
926  ListCell *lc;
927 
928  /*
929  * Reject volatile ECs immediately; such sorts must always be postponed.
930  */
931  if (ec->ec_has_volatile)
932  return false;
933 
934  /*
935  * Try to find an EM directly matching some reltarget member.
936  */
937  foreach(lc, target->exprs)
938  {
939  Expr *targetexpr = (Expr *) lfirst(lc);
940 
941  em = find_ec_member_matching_expr(ec, targetexpr, rel->relids);
942  if (!em)
943  continue;
944 
945  /*
946  * Reject expressions involving set-returning functions, as those
947  * can't be computed early either. (Note: this test and the following
948  * one are effectively checking properties of targetexpr, so there's
949  * no point in asking whether some other EC member would be better.)
950  */
951  if (expression_returns_set((Node *) em->em_expr))
952  continue;
953 
954  /*
955  * If requested, reject expressions that are not parallel-safe. We
956  * check this last because it's a rather expensive test.
957  */
958  if (require_parallel_safe &&
959  !is_parallel_safe(root, (Node *) em->em_expr))
960  continue;
961 
962  return true;
963  }
964 
965  /*
966  * Try to find an expression computable from the reltarget.
967  */
968  em = find_computable_ec_member(root, ec, target->exprs, rel->relids,
969  require_parallel_safe);
970  if (!em)
971  return false;
972 
973  /*
974  * Reject expressions involving set-returning functions, as those can't be
975  * computed early either. (There's no point in looking for another EC
976  * member in this case; since SRFs can't appear in WHERE, they cannot
977  * belong to multi-member ECs.)
978  */
979  if (expression_returns_set((Node *) em->em_expr))
980  return false;
981 
982  return true;
983 }
EquivalenceMember * find_ec_member_matching_expr(EquivalenceClass *ec, Expr *expr, Relids relids)
Definition: equivclass.c:763
EquivalenceMember * find_computable_ec_member(PlannerInfo *root, EquivalenceClass *ec, List *exprs, Relids relids, bool require_parallel_safe)
Definition: equivclass.c:837
List * exprs
Definition: pathnodes.h:1542

References EquivalenceClass::ec_has_volatile, EquivalenceMember::em_expr, expression_returns_set(), PathTarget::exprs, find_computable_ec_member(), find_ec_member_matching_expr(), is_parallel_safe(), lfirst, RelOptInfo::relids, RelOptInfo::reltarget, and root.

Referenced by get_useful_pathkeys_for_relation().

◆ relation_has_unique_index_for()

bool relation_has_unique_index_for ( PlannerInfo root,
RelOptInfo rel,
List restrictlist,
List exprlist,
List oprlist 
)

Definition at line 4142 of file indxpath.c.

4145 {
4146  ListCell *ic;
4147 
4148  Assert(list_length(exprlist) == list_length(oprlist));
4149 
4150  /* Short-circuit if no indexes... */
4151  if (rel->indexlist == NIL)
4152  return false;
4153 
4154  /*
4155  * Examine the rel's restriction clauses for usable var = const clauses
4156  * that we can add to the restrictlist.
4157  */
4158  foreach(ic, rel->baserestrictinfo)
4159  {
4160  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(ic);
4161 
4162  /*
4163  * Note: can_join won't be set for a restriction clause, but
4164  * mergeopfamilies will be if it has a mergejoinable operator and
4165  * doesn't contain volatile functions.
4166  */
4167  if (restrictinfo->mergeopfamilies == NIL)
4168  continue; /* not mergejoinable */
4169 
4170  /*
4171  * The clause certainly doesn't refer to anything but the given rel.
4172  * If either side is pseudoconstant then we can use it.
4173  */
4174  if (bms_is_empty(restrictinfo->left_relids))
4175  {
4176  /* righthand side is inner */
4177  restrictinfo->outer_is_left = true;
4178  }
4179  else if (bms_is_empty(restrictinfo->right_relids))
4180  {
4181  /* lefthand side is inner */
4182  restrictinfo->outer_is_left = false;
4183  }
4184  else
4185  continue;
4186 
4187  /* OK, add to list */
4188  restrictlist = lappend(restrictlist, restrictinfo);
4189  }
4190 
4191  /* Short-circuit the easy case */
4192  if (restrictlist == NIL && exprlist == NIL)
4193  return false;
4194 
4195  /* Examine each index of the relation ... */
4196  foreach(ic, rel->indexlist)
4197  {
4198  IndexOptInfo *ind = (IndexOptInfo *) lfirst(ic);
4199  int c;
4200 
4201  /*
4202  * If the index is not unique, or not immediately enforced, or if it's
4203  * a partial index, it's useless here. We're unable to make use of
4204  * predOK partial unique indexes due to the fact that
4205  * check_index_predicates() also makes use of join predicates to
4206  * determine if the partial index is usable. Here we need proofs that
4207  * hold true before any joins are evaluated.
4208  */
4209  if (!ind->unique || !ind->immediate || ind->indpred != NIL)
4210  continue;
4211 
4212  /*
4213  * Try to find each index column in the lists of conditions. This is
4214  * O(N^2) or worse, but we expect all the lists to be short.
4215  */
4216  for (c = 0; c < ind->nkeycolumns; c++)
4217  {
4218  bool matched = false;
4219  ListCell *lc;
4220  ListCell *lc2;
4221 
4222  foreach(lc, restrictlist)
4223  {
4224  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
4225  Node *rexpr;
4226 
4227  /*
4228  * The condition's equality operator must be a member of the
4229  * index opfamily, else it is not asserting the right kind of
4230  * equality behavior for this index. We check this first
4231  * since it's probably cheaper than match_index_to_operand().
4232  */
4233  if (!list_member_oid(rinfo->mergeopfamilies, ind->opfamily[c]))
4234  continue;
4235 
4236  /*
4237  * XXX at some point we may need to check collations here too.
4238  * For the moment we assume all collations reduce to the same
4239  * notion of equality.
4240  */
4241 
4242  /* OK, see if the condition operand matches the index key */
4243  if (rinfo->outer_is_left)
4244  rexpr = get_rightop(rinfo->clause);
4245  else
4246  rexpr = get_leftop(rinfo->clause);
4247 
4248  if (match_index_to_operand(rexpr, c, ind))
4249  {
4250  matched = true; /* column is unique */
4251  break;
4252  }
4253  }
4254 
4255  if (matched)
4256  continue;
4257 
4258  forboth(lc, exprlist, lc2, oprlist)
4259  {
4260  Node *expr = (Node *) lfirst(lc);
4261  Oid opr = lfirst_oid(lc2);
4262 
4263  /* See if the expression matches the index key */
4264  if (!match_index_to_operand(expr, c, ind))
4265  continue;
4266 
4267  /*
4268  * The equality operator must be a member of the index
4269  * opfamily, else it is not asserting the right kind of
4270  * equality behavior for this index. We assume the caller
4271  * determined it is an equality operator, so we don't need to
4272  * check any more tightly than this.
4273  */
4274  if (!op_in_opfamily(opr, ind->opfamily[c]))
4275  continue;
4276 
4277  /*
4278  * XXX at some point we may need to check collations here too.
4279  * For the moment we assume all collations reduce to the same
4280  * notion of equality.
4281  */
4282 
4283  matched = true; /* column is unique */
4284  break;
4285  }
4286 
4287  if (!matched)
4288  break; /* no match; this index doesn't help us */
4289  }
4290 
4291  /* Matched all key columns of this index? */
4292  if (c == ind->nkeycolumns)
4293  return true;
4294  }
4295 
4296  return false;
4297 }
bool match_index_to_operand(Node *operand, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:4367
bool op_in_opfamily(Oid opno, Oid opfamily)
Definition: lsyscache.c:66
#define lfirst_oid(lc)
Definition: pg_list.h:174
char * c

References Assert, RelOptInfo::baserestrictinfo, bms_is_empty, RestrictInfo::clause, forboth, get_leftop(), get_rightop(), RelOptInfo::indexlist, lappend(), lfirst, lfirst_oid, list_length(), list_member_oid(), match_index_to_operand(), NIL, and op_in_opfamily().

Referenced by create_unique_path(), and rel_is_distinct_for().

◆ select_outer_pathkeys_for_merge()

List* select_outer_pathkeys_for_merge ( PlannerInfo root,
List mergeclauses,
RelOptInfo joinrel 
)

Definition at line 1658 of file pathkeys.c.

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

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

Referenced by sort_inner_and_outer().

◆ standard_join_search()

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

Definition at line 3422 of file allpaths.c.

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

References Assert, bms_equal(), elog, ERROR, generate_partitionwise_join_paths(), generate_useful_gather_paths(), join_search_one_level(), lfirst, linitial, list_length(), NIL, palloc0(), pprint(), RelOptInfo::relids, root, and set_cheapest().

Referenced by make_rel_from_joinlist().

◆ trim_mergeclauses_for_inner_pathkeys()

List* trim_mergeclauses_for_inner_pathkeys ( PlannerInfo root,
List mergeclauses,
List pathkeys 
)

Definition at line 1957 of file pathkeys.c.

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

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

Referenced by generate_mergejoin_paths().

◆ truncate_useless_pathkeys()

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

Definition at line 2231 of file pathkeys.c.

2234 {
2235  int nuseful;
2236  int nuseful2;
2237 
2238  nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
2239  nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
2240  if (nuseful2 > nuseful)
2241  nuseful = nuseful2;
2242  nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
2243  if (nuseful2 > nuseful)
2244  nuseful = nuseful2;
2245  nuseful2 = pathkeys_useful_for_setop(root, pathkeys);
2246  if (nuseful2 > nuseful)
2247  nuseful = nuseful2;
2248 
2249  /*
2250  * Note: not safe to modify input list destructively, but we can avoid
2251  * copying the list if we're not actually going to change it
2252  */
2253  if (nuseful == 0)
2254  return NIL;
2255  else if (nuseful == list_length(pathkeys))
2256  return pathkeys;
2257  else
2258  return list_copy_head(pathkeys, nuseful);
2259 }
static int pathkeys_useful_for_setop(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2216
static int pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2156
static int pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:2186
static int pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:2052

References list_copy_head(), list_length(), NIL, pathkeys_useful_for_grouping(), pathkeys_useful_for_merging(), pathkeys_useful_for_ordering(), pathkeys_useful_for_setop(), and root.

Referenced by build_index_paths(), and build_join_pathkeys().

◆ update_mergeclause_eclasses()

void update_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1509 of file pathkeys.c.

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

References Assert, and NIL.

Referenced by find_mergeclauses_for_outer_pathkeys(), get_useful_ecs_for_relation(), make_inner_pathkeys_for_merge(), pathkeys_useful_for_merging(), select_mergejoin_clauses(), and select_outer_pathkeys_for_merge().

Variable Documentation

◆ enable_geqo

PGDLLIMPORT bool enable_geqo
extern

Definition at line 79 of file allpaths.c.

Referenced by make_rel_from_joinlist().

◆ enable_group_by_reordering

PGDLLIMPORT bool enable_group_by_reordering
extern

Definition at line 32 of file pathkeys.c.

Referenced by get_useful_group_keys_orderings().

◆ geqo_threshold

PGDLLIMPORT int geqo_threshold
extern

Definition at line 80 of file allpaths.c.

Referenced by make_rel_from_joinlist().

◆ join_search_hook

PGDLLIMPORT join_search_hook_type join_search_hook
extern

Definition at line 88 of file allpaths.c.

Referenced by make_rel_from_joinlist().

◆ min_parallel_index_scan_size

PGDLLIMPORT int min_parallel_index_scan_size
extern

Definition at line 82 of file allpaths.c.

Referenced by compute_parallel_worker(), and parallel_vacuum_compute_workers().

◆ min_parallel_table_scan_size

PGDLLIMPORT int min_parallel_table_scan_size
extern

Definition at line 81 of file allpaths.c.

Referenced by compute_parallel_worker().

◆ set_join_pathlist_hook

PGDLLIMPORT set_join_pathlist_hook_type set_join_pathlist_hook
extern

Definition at line 33 of file joinpath.c.

Referenced by add_paths_to_joinrel().

◆ set_rel_pathlist_hook

PGDLLIMPORT set_rel_pathlist_hook_type set_rel_pathlist_hook
extern

Definition at line 85 of file allpaths.c.

Referenced by set_rel_pathlist().