PostgreSQL Source Code  git master
paths.h File Reference
#include "nodes/pathnodes.h"
Include dependency graph for paths.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs

typedef void(* set_rel_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte)
 
typedef void(* set_join_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
 
typedef RelOptInfo *(* join_search_hook_type) (PlannerInfo *root, int levels_needed, List *initial_rels)
 
typedef bool(* ec_matches_callback_type) (PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg)
 

Enumerations

enum  PathKeysComparison { PATHKEYS_EQUAL , PATHKEYS_BETTER1 , PATHKEYS_BETTER2 , PATHKEYS_DIFFERENT }
 

Functions

RelOptInfomake_one_rel (PlannerInfo *root, List *joinlist)
 
RelOptInfostandard_join_search (PlannerInfo *root, int levels_needed, List *initial_rels)
 
void generate_gather_paths (PlannerInfo *root, RelOptInfo *rel, bool override_rows)
 
void generate_useful_gather_paths (PlannerInfo *root, RelOptInfo *rel, bool override_rows)
 
int compute_parallel_worker (RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
 
void create_partial_bitmap_paths (PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual)
 
void generate_partitionwise_join_paths (PlannerInfo *root, RelOptInfo *rel)
 
void create_index_paths (PlannerInfo *root, RelOptInfo *rel)
 
bool relation_has_unique_index_for (PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List *exprlist, List *oprlist)
 
bool 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)
 
void 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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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 *sortable)
 
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 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 117 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 45 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 36 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 29 of file paths.h.

Enumeration Type Documentation

◆ PathKeysComparison

Enumerator
PATHKEYS_EQUAL 
PATHKEYS_BETTER1 
PATHKEYS_BETTER2 
PATHKEYS_DIFFERENT 

Definition at line 193 of file paths.h.

194 {
195  PATHKEYS_EQUAL, /* pathkeys are identical */
196  PATHKEYS_BETTER1, /* pathkey 1 is a superset of pathkey 2 */
197  PATHKEYS_BETTER2, /* vice versa */
198  PATHKEYS_DIFFERENT /* neither pathkey includes the other */
PathKeysComparison
Definition: paths.h:194
@ PATHKEYS_BETTER2
Definition: paths.h:197
@ PATHKEYS_BETTER1
Definition: paths.h:196
@ PATHKEYS_DIFFERENT
Definition: paths.h:198
@ PATHKEYS_EQUAL
Definition: paths.h:195

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

2709 {
2710  Relids top_parent_relids = child_joinrel->top_parent_relids;
2711  Relids child_relids = child_joinrel->relids;
2712  Bitmapset *matching_ecs;
2713  MemoryContext oldcontext;
2714  int i;
2715 
2716  Assert(IS_JOIN_REL(child_joinrel) && IS_JOIN_REL(parent_joinrel));
2717 
2718  /* We need consider only ECs that mention the parent joinrel */
2719  matching_ecs = get_eclass_indexes_for_relids(root, top_parent_relids);
2720 
2721  /*
2722  * If we're being called during GEQO join planning, we still have to
2723  * create any new EC members in the main planner context, to avoid having
2724  * a corrupt EC data structure after the GEQO context is reset. This is
2725  * problematic since we'll leak memory across repeated GEQO cycles. For
2726  * now, though, bloat is better than crash. If it becomes a real issue
2727  * we'll have to do something to avoid generating duplicate EC members.
2728  */
2729  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
2730 
2731  i = -1;
2732  while ((i = bms_next_member(matching_ecs, i)) >= 0)
2733  {
2734  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2735  int num_members;
2736 
2737  /*
2738  * If this EC contains a volatile expression, then generating child
2739  * EMs would be downright dangerous, so skip it. We rely on a
2740  * volatile EC having only one EM.
2741  */
2742  if (cur_ec->ec_has_volatile)
2743  continue;
2744 
2745  /* Sanity check on get_eclass_indexes_for_relids result */
2746  Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids));
2747 
2748  /*
2749  * We don't use foreach() here because there's no point in scanning
2750  * newly-added child members, so we can stop after the last
2751  * pre-existing EC member.
2752  */
2753  num_members = list_length(cur_ec->ec_members);
2754  for (int pos = 0; pos < num_members; pos++)
2755  {
2756  EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2757 
2758  if (cur_em->em_is_const)
2759  continue; /* ignore consts here */
2760 
2761  /*
2762  * We consider only original EC members here, not
2763  * already-transformed child members.
2764  */
2765  if (cur_em->em_is_child)
2766  continue; /* ignore children here */
2767 
2768  /*
2769  * We may ignore expressions that reference a single baserel,
2770  * because add_child_rel_equivalences should have handled them.
2771  */
2772  if (bms_membership(cur_em->em_relids) != BMS_MULTIPLE)
2773  continue;
2774 
2775  /* Does this member reference child's topmost parent rel? */
2776  if (bms_overlap(cur_em->em_relids, top_parent_relids))
2777  {
2778  /* Yes, generate transformed child version */
2779  Expr *child_expr;
2780  Relids new_relids;
2781 
2782  if (parent_joinrel->reloptkind == RELOPT_JOINREL)
2783  {
2784  /* Simple single-level transformation */
2785  child_expr = (Expr *)
2787  (Node *) cur_em->em_expr,
2788  nappinfos, appinfos);
2789  }
2790  else
2791  {
2792  /* Must do multi-level transformation */
2793  Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
2794  child_expr = (Expr *)
2796  (Node *) cur_em->em_expr,
2797  child_joinrel,
2798  child_joinrel->top_parent);
2799  }
2800 
2801  /*
2802  * Transform em_relids to match. Note we do *not* do
2803  * pull_varnos(child_expr) here, as for example the
2804  * transformation might have substituted a constant, but we
2805  * don't want the child member to be marked as constant.
2806  */
2807  new_relids = bms_difference(cur_em->em_relids,
2808  top_parent_relids);
2809  new_relids = bms_add_members(new_relids, child_relids);
2810 
2811  (void) add_eq_member(cur_ec, child_expr, new_relids,
2812  cur_em->em_jdomain,
2813  cur_em, cur_em->em_datatype);
2814  }
2815  }
2816  }
2817 
2818  MemoryContextSwitchTo(oldcontext);
2819 }
Node * adjust_appendrel_attrs(PlannerInfo *root, Node *node, int nappinfos, AppendRelInfo **appinfos)
Definition: appendinfo.c:195
Node * adjust_appendrel_attrs_multilevel(PlannerInfo *root, Node *node, RelOptInfo *childrel, RelOptInfo *parentrel)
Definition: appendinfo.c:520
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1047
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:292
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:796
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:675
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:495
@ BMS_MULTIPLE
Definition: bitmapset.h:75
static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, JoinDomain *jdomain, EquivalenceMember *parent, Oid datatype)
Definition: equivclass.c:514
static Bitmapset * get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
Definition: equivclass.c:3208
int i
Definition: isn.c:73
Assert(fmt[strlen(fmt) - 1] !='\n')
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:138
#define IS_JOIN_REL(rel)
Definition: pathnodes.h:839
@ RELOPT_JOINREL
Definition: pathnodes.h:822
@ RELOPT_OTHER_JOINREL
Definition: pathnodes.h:824
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
JoinDomain * em_jdomain
Definition: pathnodes.h:1434
Definition: nodes.h:129
List * eq_classes
Definition: pathnodes.h:314
Relids relids
Definition: pathnodes.h:866
Relids top_parent_relids
Definition: pathnodes.h:998
RelOptKind reloptkind
Definition: pathnodes.h:860

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, PlannerInfo::eq_classes, get_eclass_indexes_for_relids(), i, IS_JOIN_REL, list_length(), list_nth(), MemoryContextSwitchTo(), RelOptInfo::relids, RELOPT_JOINREL, RELOPT_OTHER_JOINREL, RelOptInfo::reloptkind, 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 2583 of file equivclass.c.

2587 {
2588  Relids top_parent_relids = child_rel->top_parent_relids;
2589  Relids child_relids = child_rel->relids;
2590  int i;
2591 
2592  /*
2593  * EC merging should be complete already, so we can use the parent rel's
2594  * eclass_indexes to avoid searching all of root->eq_classes.
2595  */
2596  Assert(root->ec_merging_done);
2597  Assert(IS_SIMPLE_REL(parent_rel));
2598 
2599  i = -1;
2600  while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0)
2601  {
2602  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2603  int num_members;
2604 
2605  /*
2606  * If this EC contains a volatile expression, then generating child
2607  * EMs would be downright dangerous, so skip it. We rely on a
2608  * volatile EC having only one EM.
2609  */
2610  if (cur_ec->ec_has_volatile)
2611  continue;
2612 
2613  /* Sanity check eclass_indexes only contain ECs for parent_rel */
2614  Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids));
2615 
2616  /*
2617  * We don't use foreach() here because there's no point in scanning
2618  * newly-added child members, so we can stop after the last
2619  * pre-existing EC member.
2620  */
2621  num_members = list_length(cur_ec->ec_members);
2622  for (int pos = 0; pos < num_members; pos++)
2623  {
2624  EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2625 
2626  if (cur_em->em_is_const)
2627  continue; /* ignore consts here */
2628 
2629  /*
2630  * We consider only original EC members here, not
2631  * already-transformed child members. Otherwise, if some original
2632  * member expression references more than one appendrel, we'd get
2633  * an O(N^2) explosion of useless derived expressions for
2634  * combinations of children. (But add_child_join_rel_equivalences
2635  * may add targeted combinations for partitionwise-join purposes.)
2636  */
2637  if (cur_em->em_is_child)
2638  continue; /* ignore children here */
2639 
2640  /*
2641  * Consider only members that reference and can be computed at
2642  * child's topmost parent rel. In particular we want to exclude
2643  * parent-rel Vars that have nonempty varnullingrels. Translating
2644  * those might fail, if the transformed expression wouldn't be a
2645  * simple Var; and in any case it wouldn't produce a member that
2646  * has any use in creating plans for the child rel.
2647  */
2648  if (bms_is_subset(cur_em->em_relids, top_parent_relids) &&
2649  !bms_is_empty(cur_em->em_relids))
2650  {
2651  /* OK, generate transformed child version */
2652  Expr *child_expr;
2653  Relids new_relids;
2654 
2655  if (parent_rel->reloptkind == RELOPT_BASEREL)
2656  {
2657  /* Simple single-level transformation */
2658  child_expr = (Expr *)
2660  (Node *) cur_em->em_expr,
2661  1, &appinfo);
2662  }
2663  else
2664  {
2665  /* Must do multi-level transformation */
2666  child_expr = (Expr *)
2668  (Node *) cur_em->em_expr,
2669  child_rel,
2670  child_rel->top_parent);
2671  }
2672 
2673  /*
2674  * Transform em_relids to match. Note we do *not* do
2675  * pull_varnos(child_expr) here, as for example the
2676  * transformation might have substituted a constant, but we
2677  * don't want the child member to be marked as constant.
2678  */
2679  new_relids = bms_difference(cur_em->em_relids,
2680  top_parent_relids);
2681  new_relids = bms_add_members(new_relids, child_relids);
2682 
2683  (void) add_eq_member(cur_ec, child_expr, new_relids,
2684  cur_em->em_jdomain,
2685  cur_em, cur_em->em_datatype);
2686 
2687  /* Record this EC index for the child rel */
2688  child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
2689  }
2690  }
2691  }
2692 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:316
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:739
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:704
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:834
@ RELOPT_BASEREL
Definition: pathnodes.h:821
bool ec_merging_done
Definition: pathnodes.h:317
Bitmapset * eclass_indexes
Definition: pathnodes.h:941

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, PlannerInfo::ec_merging_done, 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, PlannerInfo::eq_classes, i, IS_SIMPLE_REL, list_length(), list_nth(), RelOptInfo::relids, RELOPT_BASEREL, RelOptInfo::reloptkind, and RelOptInfo::top_parent_relids.

Referenced by set_append_rel_size().

◆ add_paths_to_append_rel()

void add_paths_to_append_rel ( PlannerInfo root,
RelOptInfo rel,
List live_childrels 
)

Definition at line 1267 of file allpaths.c.

1269 {
1270  List *subpaths = NIL;
1271  bool subpaths_valid = true;
1272  List *partial_subpaths = NIL;
1273  List *pa_partial_subpaths = NIL;
1274  List *pa_nonpartial_subpaths = NIL;
1275  bool partial_subpaths_valid = true;
1276  bool pa_subpaths_valid;
1277  List *all_child_pathkeys = NIL;
1278  List *all_child_outers = NIL;
1279  ListCell *l;
1280  double partial_rows = -1;
1281 
1282  /* If appropriate, consider parallel append */
1283  pa_subpaths_valid = enable_parallel_append && rel->consider_parallel;
1284 
1285  /*
1286  * For every non-dummy child, remember the cheapest path. Also, identify
1287  * all pathkeys (orderings) and parameterizations (required_outer sets)
1288  * available for the non-dummy member relations.
1289  */
1290  foreach(l, live_childrels)
1291  {
1292  RelOptInfo *childrel = lfirst(l);
1293  ListCell *lcp;
1294  Path *cheapest_partial_path = NULL;
1295 
1296  /*
1297  * If child has an unparameterized cheapest-total path, add that to
1298  * the unparameterized Append path we are constructing for the parent.
1299  * If not, there's no workable unparameterized path.
1300  *
1301  * With partitionwise aggregates, the child rel's pathlist may be
1302  * empty, so don't assume that a path exists here.
1303  */
1304  if (childrel->pathlist != NIL &&
1305  childrel->cheapest_total_path->param_info == NULL)
1307  &subpaths, NULL);
1308  else
1309  subpaths_valid = false;
1310 
1311  /* Same idea, but for a partial plan. */
1312  if (childrel->partial_pathlist != NIL)
1313  {
1314  cheapest_partial_path = linitial(childrel->partial_pathlist);
1315  accumulate_append_subpath(cheapest_partial_path,
1316  &partial_subpaths, NULL);
1317  }
1318  else
1319  partial_subpaths_valid = false;
1320 
1321  /*
1322  * Same idea, but for a parallel append mixing partial and non-partial
1323  * paths.
1324  */
1325  if (pa_subpaths_valid)
1326  {
1327  Path *nppath = NULL;
1328 
1329  nppath =
1331 
1332  if (cheapest_partial_path == NULL && nppath == NULL)
1333  {
1334  /* Neither a partial nor a parallel-safe path? Forget it. */
1335  pa_subpaths_valid = false;
1336  }
1337  else if (nppath == NULL ||
1338  (cheapest_partial_path != NULL &&
1339  cheapest_partial_path->total_cost < nppath->total_cost))
1340  {
1341  /* Partial path is cheaper or the only option. */
1342  Assert(cheapest_partial_path != NULL);
1343  accumulate_append_subpath(cheapest_partial_path,
1344  &pa_partial_subpaths,
1345  &pa_nonpartial_subpaths);
1346  }
1347  else
1348  {
1349  /*
1350  * Either we've got only a non-partial path, or we think that
1351  * a single backend can execute the best non-partial path
1352  * faster than all the parallel backends working together can
1353  * execute the best partial path.
1354  *
1355  * It might make sense to be more aggressive here. Even if
1356  * the best non-partial path is more expensive than the best
1357  * partial path, it could still be better to choose the
1358  * non-partial path if there are several such paths that can
1359  * be given to different workers. For now, we don't try to
1360  * figure that out.
1361  */
1363  &pa_nonpartial_subpaths,
1364  NULL);
1365  }
1366  }
1367 
1368  /*
1369  * Collect lists of all the available path orderings and
1370  * parameterizations for all the children. We use these as a
1371  * heuristic to indicate which sort orderings and parameterizations we
1372  * should build Append and MergeAppend paths for.
1373  */
1374  foreach(lcp, childrel->pathlist)
1375  {
1376  Path *childpath = (Path *) lfirst(lcp);
1377  List *childkeys = childpath->pathkeys;
1378  Relids childouter = PATH_REQ_OUTER(childpath);
1379 
1380  /* Unsorted paths don't contribute to pathkey list */
1381  if (childkeys != NIL)
1382  {
1383  ListCell *lpk;
1384  bool found = false;
1385 
1386  /* Have we already seen this ordering? */
1387  foreach(lpk, all_child_pathkeys)
1388  {
1389  List *existing_pathkeys = (List *) lfirst(lpk);
1390 
1391  if (compare_pathkeys(existing_pathkeys,
1392  childkeys) == PATHKEYS_EQUAL)
1393  {
1394  found = true;
1395  break;
1396  }
1397  }
1398  if (!found)
1399  {
1400  /* No, so add it to all_child_pathkeys */
1401  all_child_pathkeys = lappend(all_child_pathkeys,
1402  childkeys);
1403  }
1404  }
1405 
1406  /* Unparameterized paths don't contribute to param-set list */
1407  if (childouter)
1408  {
1409  ListCell *lco;
1410  bool found = false;
1411 
1412  /* Have we already seen this param set? */
1413  foreach(lco, all_child_outers)
1414  {
1415  Relids existing_outers = (Relids) lfirst(lco);
1416 
1417  if (bms_equal(existing_outers, childouter))
1418  {
1419  found = true;
1420  break;
1421  }
1422  }
1423  if (!found)
1424  {
1425  /* No, so add it to all_child_outers */
1426  all_child_outers = lappend(all_child_outers,
1427  childouter);
1428  }
1429  }
1430  }
1431  }
1432 
1433  /*
1434  * If we found unparameterized paths for all children, build an unordered,
1435  * unparameterized Append path for the rel. (Note: this is correct even
1436  * if we have zero or one live subpath due to constraint exclusion.)
1437  */
1438  if (subpaths_valid)
1439  add_path(rel, (Path *) create_append_path(root, rel, subpaths, NIL,
1440  NIL, NULL, 0, false,
1441  -1));
1442 
1443  /*
1444  * Consider an append of unordered, unparameterized partial paths. Make
1445  * it parallel-aware if possible.
1446  */
1447  if (partial_subpaths_valid && partial_subpaths != NIL)
1448  {
1449  AppendPath *appendpath;
1450  ListCell *lc;
1451  int parallel_workers = 0;
1452 
1453  /* Find the highest number of workers requested for any subpath. */
1454  foreach(lc, partial_subpaths)
1455  {
1456  Path *path = lfirst(lc);
1457 
1458  parallel_workers = Max(parallel_workers, path->parallel_workers);
1459  }
1460  Assert(parallel_workers > 0);
1461 
1462  /*
1463  * If the use of parallel append is permitted, always request at least
1464  * log2(# of children) workers. We assume it can be useful to have
1465  * extra workers in this case because they will be spread out across
1466  * the children. The precise formula is just a guess, but we don't
1467  * want to end up with a radically different answer for a table with N
1468  * partitions vs. an unpartitioned table with the same data, so the
1469  * use of some kind of log-scaling here seems to make some sense.
1470  */
1472  {
1473  parallel_workers = Max(parallel_workers,
1474  pg_leftmost_one_pos32(list_length(live_childrels)) + 1);
1475  parallel_workers = Min(parallel_workers,
1477  }
1478  Assert(parallel_workers > 0);
1479 
1480  /* Generate a partial append path. */
1481  appendpath = create_append_path(root, rel, NIL, partial_subpaths,
1482  NIL, NULL, parallel_workers,
1484  -1);
1485 
1486  /*
1487  * Make sure any subsequent partial paths use the same row count
1488  * estimate.
1489  */
1490  partial_rows = appendpath->path.rows;
1491 
1492  /* Add the path. */
1493  add_partial_path(rel, (Path *) appendpath);
1494  }
1495 
1496  /*
1497  * Consider a parallel-aware append using a mix of partial and non-partial
1498  * paths. (This only makes sense if there's at least one child which has
1499  * a non-partial path that is substantially cheaper than any partial path;
1500  * otherwise, we should use the append path added in the previous step.)
1501  */
1502  if (pa_subpaths_valid && pa_nonpartial_subpaths != NIL)
1503  {
1504  AppendPath *appendpath;
1505  ListCell *lc;
1506  int parallel_workers = 0;
1507 
1508  /*
1509  * Find the highest number of workers requested for any partial
1510  * subpath.
1511  */
1512  foreach(lc, pa_partial_subpaths)
1513  {
1514  Path *path = lfirst(lc);
1515 
1516  parallel_workers = Max(parallel_workers, path->parallel_workers);
1517  }
1518 
1519  /*
1520  * Same formula here as above. It's even more important in this
1521  * instance because the non-partial paths won't contribute anything to
1522  * the planned number of parallel workers.
1523  */
1524  parallel_workers = Max(parallel_workers,
1525  pg_leftmost_one_pos32(list_length(live_childrels)) + 1);
1526  parallel_workers = Min(parallel_workers,
1528  Assert(parallel_workers > 0);
1529 
1530  appendpath = create_append_path(root, rel, pa_nonpartial_subpaths,
1531  pa_partial_subpaths,
1532  NIL, NULL, parallel_workers, true,
1533  partial_rows);
1534  add_partial_path(rel, (Path *) appendpath);
1535  }
1536 
1537  /*
1538  * Also build unparameterized ordered append paths based on the collected
1539  * list of child pathkeys.
1540  */
1541  if (subpaths_valid)
1542  generate_orderedappend_paths(root, rel, live_childrels,
1543  all_child_pathkeys);
1544 
1545  /*
1546  * Build Append paths for each parameterization seen among the child rels.
1547  * (This may look pretty expensive, but in most cases of practical
1548  * interest, the child rels will expose mostly the same parameterizations,
1549  * so that not that many cases actually get considered here.)
1550  *
1551  * The Append node itself cannot enforce quals, so all qual checking must
1552  * be done in the child paths. This means that to have a parameterized
1553  * Append path, we must have the exact same parameterization for each
1554  * child path; otherwise some children might be failing to check the
1555  * moved-down quals. To make them match up, we can try to increase the
1556  * parameterization of lesser-parameterized paths.
1557  */
1558  foreach(l, all_child_outers)
1559  {
1560  Relids required_outer = (Relids) lfirst(l);
1561  ListCell *lcr;
1562 
1563  /* Select the child paths for an Append with this parameterization */
1564  subpaths = NIL;
1565  subpaths_valid = true;
1566  foreach(lcr, live_childrels)
1567  {
1568  RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr);
1569  Path *subpath;
1570 
1571  if (childrel->pathlist == NIL)
1572  {
1573  /* failed to make a suitable path for this child */
1574  subpaths_valid = false;
1575  break;
1576  }
1577 
1579  childrel,
1580  required_outer);
1581  if (subpath == NULL)
1582  {
1583  /* failed to make a suitable path for this child */
1584  subpaths_valid = false;
1585  break;
1586  }
1587  accumulate_append_subpath(subpath, &subpaths, NULL);
1588  }
1589 
1590  if (subpaths_valid)
1591  add_path(rel, (Path *)
1592  create_append_path(root, rel, subpaths, NIL,
1593  NIL, required_outer, 0, false,
1594  -1));
1595  }
1596 
1597  /*
1598  * When there is only a single child relation, the Append path can inherit
1599  * any ordering available for the child rel's path, so that it's useful to
1600  * consider ordered partial paths. Above we only considered the cheapest
1601  * partial path for each child, but let's also make paths using any
1602  * partial paths that have pathkeys.
1603  */
1604  if (list_length(live_childrels) == 1)
1605  {
1606  RelOptInfo *childrel = (RelOptInfo *) linitial(live_childrels);
1607 
1608  /* skip the cheapest partial path, since we already used that above */
1609  for_each_from(l, childrel->partial_pathlist, 1)
1610  {
1611  Path *path = (Path *) lfirst(l);
1612  AppendPath *appendpath;
1613 
1614  /* skip paths with no pathkeys. */
1615  if (path->pathkeys == NIL)
1616  continue;
1617 
1618  appendpath = create_append_path(root, rel, NIL, list_make1(path),
1619  NIL, NULL,
1620  path->parallel_workers, true,
1621  partial_rows);
1622  add_partial_path(rel, (Path *) appendpath);
1623  }
1624  }
1625 }
static Path * get_cheapest_parameterized_child_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer)
Definition: allpaths.c:1929
static void generate_orderedappend_paths(PlannerInfo *root, RelOptInfo *rel, List *live_childrels, List *all_child_pathkeys)
Definition: allpaths.c:1655
static void accumulate_append_subpath(Path *path, List **subpaths, List **special_subpaths)
Definition: allpaths.c:2017
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:94
#define Min(x, y)
Definition: c.h:988
#define Max(x, y)
Definition: c.h:982
int max_parallel_workers_per_gather
Definition: costsize.c:133
bool enable_parallel_append
Definition: costsize.c:151
List * lappend(List *list, void *datum)
Definition: list.c:338
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:241
Path * get_cheapest_parallel_safe_total_inner(List *paths)
Definition: pathkeys.c:498
PathKeysComparison compare_pathkeys(List *keys1, List *keys2)
Definition: pathkeys.c:301
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:1244
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:749
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1647
Bitmapset * Relids
Definition: pathnodes.h:30
static int pg_leftmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:26
#define lfirst(lc)
Definition: pg_list.h:172
#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:1643
Cardinality rows
Definition: pathnodes.h:1638
int parallel_workers
Definition: pathnodes.h:1635
Cost total_cost
Definition: pathnodes.h:1640
bool consider_parallel
Definition: pathnodes.h:882
List * pathlist
Definition: pathnodes.h:893
struct Path * cheapest_total_path
Definition: pathnodes.h:897
List * partial_pathlist
Definition: pathnodes.h:895

References accumulate_append_subpath(), add_partial_path(), add_path(), Assert(), bms_equal(), RelOptInfo::cheapest_total_path, compare_pathkeys(), RelOptInfo::consider_parallel, 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(), 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 123 of file joinpath.c.

130 {
131  JoinPathExtraData extra;
132  bool mergejoin_allowed = true;
133  ListCell *lc;
134  Relids joinrelids;
135 
136  /*
137  * PlannerInfo doesn't contain the SpecialJoinInfos created for joins
138  * between child relations, even if there is a SpecialJoinInfo node for
139  * the join between the topmost parents. So, while calculating Relids set
140  * representing the restriction, consider relids of topmost parent of
141  * partitions.
142  */
143  if (joinrel->reloptkind == RELOPT_OTHER_JOINREL)
144  joinrelids = joinrel->top_parent_relids;
145  else
146  joinrelids = joinrel->relids;
147 
148  extra.restrictlist = restrictlist;
149  extra.mergeclause_list = NIL;
150  extra.sjinfo = sjinfo;
151  extra.param_source_rels = NULL;
152 
153  /*
154  * See if the inner relation is provably unique for this outer rel.
155  *
156  * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
157  * matter since the executor can make the equivalent optimization anyway;
158  * we need not expend planner cycles on proofs. For JOIN_UNIQUE_INNER, we
159  * must be considering a semijoin whose inner side is not provably unique
160  * (else reduce_unique_semijoins would've simplified it), so there's no
161  * point in calling innerrel_is_unique. However, if the LHS covers all of
162  * the semijoin's min_lefthand, then it's appropriate to set inner_unique
163  * because the path produced by create_unique_path will be unique relative
164  * to the LHS. (If we have an LHS that's only part of the min_lefthand,
165  * that is *not* true.) For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
166  * letting that value escape this module.
167  */
168  switch (jointype)
169  {
170  case JOIN_SEMI:
171  case JOIN_ANTI:
172 
173  /*
174  * XXX it may be worth proving this to allow a Memoize to be
175  * considered for Nested Loop Semi/Anti Joins.
176  */
177  extra.inner_unique = false; /* well, unproven */
178  break;
179  case JOIN_UNIQUE_INNER:
180  extra.inner_unique = bms_is_subset(sjinfo->min_lefthand,
181  outerrel->relids);
182  break;
183  case JOIN_UNIQUE_OUTER:
184  extra.inner_unique = innerrel_is_unique(root,
185  joinrel->relids,
186  outerrel->relids,
187  innerrel,
188  JOIN_INNER,
189  restrictlist,
190  false);
191  break;
192  default:
193  extra.inner_unique = innerrel_is_unique(root,
194  joinrel->relids,
195  outerrel->relids,
196  innerrel,
197  jointype,
198  restrictlist,
199  false);
200  break;
201  }
202 
203  /*
204  * Find potential mergejoin clauses. We can skip this if we are not
205  * interested in doing a mergejoin. However, mergejoin may be our only
206  * way of implementing a full outer join, so override enable_mergejoin if
207  * it's a full join.
208  */
209  if (enable_mergejoin || jointype == JOIN_FULL)
211  joinrel,
212  outerrel,
213  innerrel,
214  restrictlist,
215  jointype,
216  &mergejoin_allowed);
217 
218  /*
219  * If it's SEMI, ANTI, or inner_unique join, compute correction factors
220  * for cost estimation. These will be the same for all paths.
221  */
222  if (jointype == JOIN_SEMI || jointype == JOIN_ANTI || extra.inner_unique)
223  compute_semi_anti_join_factors(root, joinrel, outerrel, innerrel,
224  jointype, sjinfo, restrictlist,
225  &extra.semifactors);
226 
227  /*
228  * Decide whether it's sensible to generate parameterized paths for this
229  * joinrel, and if so, which relations such paths should require. There
230  * is usually no need to create a parameterized result path unless there
231  * is a join order restriction that prevents joining one of our input rels
232  * directly to the parameter source rel instead of joining to the other
233  * input rel. (But see allow_star_schema_join().) This restriction
234  * reduces the number of parameterized paths we have to deal with at
235  * higher join levels, without compromising the quality of the resulting
236  * plan. We express the restriction as a Relids set that must overlap the
237  * parameterization of any proposed join path. Note: param_source_rels
238  * should contain only baserels, not OJ relids, so starting from
239  * all_baserels not all_query_rels is correct.
240  */
241  foreach(lc, root->join_info_list)
242  {
243  SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);
244 
245  /*
246  * SJ is relevant to this join if we have some part of its RHS
247  * (possibly not all of it), and haven't yet joined to its LHS. (This
248  * test is pretty simplistic, but should be sufficient considering the
249  * join has already been proven legal.) If the SJ is relevant, it
250  * presents constraints for joining to anything not in its RHS.
251  */
252  if (bms_overlap(joinrelids, sjinfo2->min_righthand) &&
253  !bms_overlap(joinrelids, sjinfo2->min_lefthand))
256  sjinfo2->min_righthand));
257 
258  /* full joins constrain both sides symmetrically */
259  if (sjinfo2->jointype == JOIN_FULL &&
260  bms_overlap(joinrelids, sjinfo2->min_lefthand) &&
261  !bms_overlap(joinrelids, sjinfo2->min_righthand))
264  sjinfo2->min_lefthand));
265  }
266 
267  /*
268  * However, when a LATERAL subquery is involved, there will simply not be
269  * any paths for the joinrel that aren't parameterized by whatever the
270  * subquery is parameterized by, unless its parameterization is resolved
271  * within the joinrel. So we might as well allow additional dependencies
272  * on whatever residual lateral dependencies the joinrel will have.
273  */
275  joinrel->lateral_relids);
276 
277  /*
278  * 1. Consider mergejoin paths where both relations must be explicitly
279  * sorted. Skip this if we can't mergejoin.
280  */
281  if (mergejoin_allowed)
282  sort_inner_and_outer(root, joinrel, outerrel, innerrel,
283  jointype, &extra);
284 
285  /*
286  * 2. Consider paths where the outer relation need not be explicitly
287  * sorted. This includes both nestloops and mergejoins where the outer
288  * path is already ordered. Again, skip this if we can't mergejoin.
289  * (That's okay because we know that nestloop can't handle right/full
290  * joins at all, so it wouldn't work in the prohibited cases either.)
291  */
292  if (mergejoin_allowed)
293  match_unsorted_outer(root, joinrel, outerrel, innerrel,
294  jointype, &extra);
295 
296 #ifdef NOT_USED
297 
298  /*
299  * 3. Consider paths where the inner relation need not be explicitly
300  * sorted. This includes mergejoins only (nestloops were already built in
301  * match_unsorted_outer).
302  *
303  * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
304  * significant difference between the inner and outer side of a mergejoin,
305  * so match_unsorted_inner creates no paths that aren't equivalent to
306  * those made by match_unsorted_outer when add_paths_to_joinrel() is
307  * invoked with the two rels given in the other order.
308  */
309  if (mergejoin_allowed)
310  match_unsorted_inner(root, joinrel, outerrel, innerrel,
311  jointype, &extra);
312 #endif
313 
314  /*
315  * 4. Consider paths where both outer and inner relations must be hashed
316  * before being joined. As above, disregard enable_hashjoin for full
317  * joins, because there may be no other alternative.
318  */
319  if (enable_hashjoin || jointype == JOIN_FULL)
320  hash_inner_and_outer(root, joinrel, outerrel, innerrel,
321  jointype, &extra);
322 
323  /*
324  * 5. If inner and outer relations are foreign tables (or joins) belonging
325  * to the same server and assigned to the same user to check access
326  * permissions as, give the FDW a chance to push down joins.
327  */
328  if (joinrel->fdwroutine &&
329  joinrel->fdwroutine->GetForeignJoinPaths)
330  joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
331  outerrel, innerrel,
332  jointype, &extra);
333 
334  /*
335  * 6. Finally, give extensions a chance to manipulate the path list.
336  */
338  set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
339  jointype, &extra);
340 }
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:953
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:4729
bool enable_hashjoin
Definition: costsize.c:147
bool enable_mergejoin
Definition: costsize.c:146
static List * select_mergejoin_clauses(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, List *restrictlist, JoinType jointype, bool *mergejoin_allowed)
Definition: joinpath.c:2280
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1201
set_join_pathlist_hook_type set_join_pathlist_hook
Definition: joinpath.c:30
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:2025
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1651
@ JOIN_SEMI
Definition: nodes.h:318
@ JOIN_FULL
Definition: nodes.h:306
@ JOIN_INNER
Definition: nodes.h:304
@ JOIN_UNIQUE_OUTER
Definition: nodes.h:325
@ JOIN_UNIQUE_INNER
Definition: nodes.h:326
@ JOIN_ANTI
Definition: nodes.h:319
List * mergeclause_list
Definition: pathnodes.h:3168
Relids param_source_rels
Definition: pathnodes.h:3172
SemiAntiJoinFactors semifactors
Definition: pathnodes.h:3171
SpecialJoinInfo * sjinfo
Definition: pathnodes.h:3170
List * join_info_list
Definition: pathnodes.h:340
Relids all_baserels
Definition: pathnodes.h:255
Relids lateral_relids
Definition: pathnodes.h:908
Relids min_righthand
Definition: pathnodes.h:2835
JoinType jointype
Definition: pathnodes.h:2838
Relids min_lefthand
Definition: pathnodes.h:2834

References PlannerInfo::all_baserels, 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, PlannerInfo::join_info_list, 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, 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().

◆ append_pathkeys()

List* append_pathkeys ( List target,
List source 
)

Definition at line 105 of file pathkeys.c.

106 {
107  ListCell *lc;
108 
109  Assert(target != NIL);
110 
111  foreach(lc, source)
112  {
113  PathKey *pk = lfirst_node(PathKey, lc);
114 
115  if (!pathkey_is_redundant(pk, target))
116  target = lappend(target, pk);
117  }
118  return target;
119 }
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:157
#define lfirst_node(type, lc)
Definition: pg_list.h:176
static rewind_source * source
Definition: pg_rewind.c:81

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

Referenced by adjust_group_pathkeys_for_groupagg().

◆ build_expression_pathkey()

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

Definition at line 799 of file pathkeys.c.

804 {
805  List *pathkeys;
806  Oid opfamily,
807  opcintype;
808  int16 strategy;
809  PathKey *cpathkey;
810 
811  /* Find the operator in pg_amop --- failure shouldn't happen */
812  if (!get_ordering_op_properties(opno,
813  &opfamily, &opcintype, &strategy))
814  elog(ERROR, "operator %u is not a valid ordering operator",
815  opno);
816 
817  cpathkey = make_pathkey_from_sortinfo(root,
818  expr,
819  opfamily,
820  opcintype,
821  exprCollation((Node *) expr),
822  (strategy == BTGreaterStrategyNumber),
823  (strategy == BTGreaterStrategyNumber),
824  0,
825  rel,
826  create_it);
827 
828  if (cpathkey)
829  pathkeys = list_make1(cpathkey);
830  else
831  pathkeys = NIL;
832 
833  return pathkeys;
834 }
signed short int16
Definition: c.h:477
#define ERROR
Definition: elog.h:39
bool get_ordering_op_properties(Oid opno, Oid *opfamily, Oid *opcintype, int16 *strategy)
Definition: lsyscache.c:206
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:764
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:196
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(), and NIL.

Referenced by set_function_pathlist().

◆ build_index_pathkeys()

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

Definition at line 539 of file pathkeys.c.

542 {
543  List *retval = NIL;
544  ListCell *lc;
545  int i;
546 
547  if (index->sortopfamily == NULL)
548  return NIL; /* non-orderable index */
549 
550  i = 0;
551  foreach(lc, index->indextlist)
552  {
553  TargetEntry *indextle = (TargetEntry *) lfirst(lc);
554  Expr *indexkey;
555  bool reverse_sort;
556  bool nulls_first;
557  PathKey *cpathkey;
558 
559  /*
560  * INCLUDE columns are stored in index unordered, so they don't
561  * support ordered index scan.
562  */
563  if (i >= index->nkeycolumns)
564  break;
565 
566  /* We assume we don't need to make a copy of the tlist item */
567  indexkey = indextle->expr;
568 
569  if (ScanDirectionIsBackward(scandir))
570  {
571  reverse_sort = !index->reverse_sort[i];
572  nulls_first = !index->nulls_first[i];
573  }
574  else
575  {
576  reverse_sort = index->reverse_sort[i];
577  nulls_first = index->nulls_first[i];
578  }
579 
580  /*
581  * OK, try to make a canonical pathkey for this sort key.
582  */
583  cpathkey = make_pathkey_from_sortinfo(root,
584  indexkey,
585  index->sortopfamily[i],
586  index->opcintype[i],
587  index->indexcollations[i],
588  reverse_sort,
589  nulls_first,
590  0,
591  index->rel->relids,
592  false);
593 
594  if (cpathkey)
595  {
596  /*
597  * We found the sort key in an EquivalenceClass, so it's relevant
598  * for this query. Add it to list, unless it's redundant.
599  */
600  if (!pathkey_is_redundant(cpathkey, retval))
601  retval = lappend(retval, cpathkey);
602  }
603  else
604  {
605  /*
606  * Boolean index keys might be redundant even if they do not
607  * appear in an EquivalenceClass, because of our special treatment
608  * of boolean equality conditions --- see the comment for
609  * indexcol_is_bool_constant_for_query(). If that applies, we can
610  * continue to examine lower-order index columns. Otherwise, the
611  * sort key is not an interesting sort order for this query, so we
612  * should stop considering index columns; any lower-order sort
613  * keys won't be useful either.
614  */
616  break;
617  }
618 
619  i++;
620  }
621 
622  return retval;
623 }
bool indexcol_is_bool_constant_for_query(PlannerInfo *root, IndexOptInfo *index, int indexcol)
Definition: indxpath.c:3665
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
Expr * expr
Definition: primnodes.h:1722
Definition: type.h:95

References TargetEntry::expr, i, indexcol_is_bool_constant_for_query(), lappend(), lfirst, make_pathkey_from_sortinfo(), NIL, pathkey_is_redundant(), 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 1093 of file pathkeys.c.

1097 {
1098  if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
1099  return NIL;
1100 
1101  /*
1102  * This used to be quite a complex bit of code, but now that all pathkey
1103  * sublists start out life canonicalized, we don't have to do a darn thing
1104  * here!
1105  *
1106  * We do, however, need to truncate the pathkeys list, since it may
1107  * contain pathkeys that were useful for forming this joinrel but are
1108  * uninteresting to higher levels.
1109  */
1110  return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1111 }
@ JOIN_RIGHT
Definition: nodes.h:307
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:1943

References JOIN_FULL, JOIN_RIGHT, NIL, 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 718 of file pathkeys.c.

720 {
721  List *retval = NIL;
722  PartitionScheme partscheme = partrel->part_scheme;
723  int i;
724 
725  Assert(partscheme != NULL);
726  Assert(partitions_are_ordered(partrel->boundinfo, partrel->live_parts));
727  /* For now, we can only cope with baserels */
728  Assert(IS_SIMPLE_REL(partrel));
729 
730  for (i = 0; i < partscheme->partnatts; i++)
731  {
732  PathKey *cpathkey;
733  Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]);
734 
735  /*
736  * Try to make a canonical pathkey for this partkey.
737  *
738  * We assume the PartitionDesc lists any NULL partition last, so we
739  * treat the scan like a NULLS LAST index: we have nulls_first for
740  * backwards scan only.
741  */
742  cpathkey = make_pathkey_from_sortinfo(root,
743  keyCol,
744  partscheme->partopfamily[i],
745  partscheme->partopcintype[i],
746  partscheme->partcollation[i],
747  ScanDirectionIsBackward(scandir),
748  ScanDirectionIsBackward(scandir),
749  0,
750  partrel->relids,
751  false);
752 
753 
754  if (cpathkey)
755  {
756  /*
757  * We found the sort key in an EquivalenceClass, so it's relevant
758  * for this query. Add it to list, unless it's redundant.
759  */
760  if (!pathkey_is_redundant(cpathkey, retval))
761  retval = lappend(retval, cpathkey);
762  }
763  else
764  {
765  /*
766  * Boolean partition keys might be redundant even if they do not
767  * appear in an EquivalenceClass, because of our special treatment
768  * of boolean equality conditions --- see the comment for
769  * partkey_is_bool_constant_for_query(). If that applies, we can
770  * continue to examine lower-order partition keys. Otherwise, the
771  * sort key is not an interesting sort order for this query, so we
772  * should stop considering partition columns; any lower-order sort
773  * keys won't be useful either.
774  */
775  if (!partkey_is_bool_constant_for_query(partrel, i))
776  {
777  *partialkeys = true;
778  return retval;
779  }
780  }
781  }
782 
783  *partialkeys = false;
784  return retval;
785 }
bool partitions_are_ordered(PartitionBoundInfo boundinfo, Bitmapset *live_parts)
Definition: partbounds.c:2853
static bool partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:643
Bitmapset * live_parts
Definition: pathnodes.h:1028

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

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

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

3303 {
3304  List *clauselist;
3305  bool have_partial;
3306  bool is_target_rel;
3307  Relids otherrels;
3308  ListCell *lc;
3309 
3310  /* Indexes are available only on base or "other" member relations. */
3311  Assert(IS_SIMPLE_REL(rel));
3312 
3313  /*
3314  * Initialize the indrestrictinfo lists to be identical to
3315  * baserestrictinfo, and check whether there are any partial indexes. If
3316  * not, this is all we need to do.
3317  */
3318  have_partial = false;
3319  foreach(lc, rel->indexlist)
3320  {
3322 
3323  index->indrestrictinfo = rel->baserestrictinfo;
3324  if (index->indpred)
3325  have_partial = true;
3326  }
3327  if (!have_partial)
3328  return;
3329 
3330  /*
3331  * Construct a list of clauses that we can assume true for the purpose of
3332  * proving the index(es) usable. Restriction clauses for the rel are
3333  * always usable, and so are any join clauses that are "movable to" this
3334  * rel. Also, we can consider any EC-derivable join clauses (which must
3335  * be "movable to" this rel, by definition).
3336  */
3337  clauselist = list_copy(rel->baserestrictinfo);
3338 
3339  /* Scan the rel's join clauses */
3340  foreach(lc, rel->joininfo)
3341  {
3342  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3343 
3344  /* Check if clause can be moved to this rel */
3345  if (!join_clause_is_movable_to(rinfo, rel))
3346  continue;
3347 
3348  clauselist = lappend(clauselist, rinfo);
3349  }
3350 
3351  /*
3352  * Add on any equivalence-derivable join clauses. Computing the correct
3353  * relid sets for generate_join_implied_equalities is slightly tricky
3354  * because the rel could be a child rel rather than a true baserel, and in
3355  * that case we must subtract its parents' relid(s) from all_query_rels.
3356  */
3357  if (rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
3358  otherrels = bms_difference(root->all_query_rels,
3359  find_childrel_parents(root, rel));
3360  else
3361  otherrels = bms_difference(root->all_query_rels, rel->relids);
3362 
3363  if (!bms_is_empty(otherrels))
3364  clauselist =
3365  list_concat(clauselist,
3367  bms_union(rel->relids,
3368  otherrels),
3369  otherrels,
3370  rel));
3371 
3372  /*
3373  * Normally we remove quals that are implied by a partial index's
3374  * predicate from indrestrictinfo, indicating that they need not be
3375  * checked explicitly by an indexscan plan using this index. However, if
3376  * the rel is a target relation of UPDATE/DELETE/MERGE/SELECT FOR UPDATE,
3377  * we cannot remove such quals from the plan, because they need to be in
3378  * the plan so that they will be properly rechecked by EvalPlanQual
3379  * testing. Some day we might want to remove such quals from the main
3380  * plan anyway and pass them through to EvalPlanQual via a side channel;
3381  * but for now, we just don't remove implied quals at all for target
3382  * relations.
3383  */
3384  is_target_rel = (bms_is_member(rel->relid, root->all_result_relids) ||
3385  get_plan_rowmark(root->rowMarks, rel->relid) != NULL);
3386 
3387  /*
3388  * Now try to prove each index predicate true, and compute the
3389  * indrestrictinfo lists for partial indexes. Note that we compute the
3390  * indrestrictinfo list even for non-predOK indexes; this might seem
3391  * wasteful, but we may be able to use such indexes in OR clauses, cf
3392  * generate_bitmap_or_paths().
3393  */
3394  foreach(lc, rel->indexlist)
3395  {
3397  ListCell *lcr;
3398 
3399  if (index->indpred == NIL)
3400  continue; /* ignore non-partial indexes here */
3401 
3402  if (!index->predOK) /* don't repeat work if already proven OK */
3403  index->predOK = predicate_implied_by(index->indpred, clauselist,
3404  false);
3405 
3406  /* If rel is an update target, leave indrestrictinfo as set above */
3407  if (is_target_rel)
3408  continue;
3409 
3410  /* Else compute indrestrictinfo as the non-implied quals */
3411  index->indrestrictinfo = NIL;
3412  foreach(lcr, rel->baserestrictinfo)
3413  {
3414  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcr);
3415 
3416  /* predicate_implied_by() assumes first arg is immutable */
3417  if (contain_mutable_functions((Node *) rinfo->clause) ||
3419  index->indpred, false))
3420  index->indrestrictinfo = lappend(index->indrestrictinfo, rinfo);
3421  }
3422  }
3423 }
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:428
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:226
bool contain_mutable_functions(Node *clause)
Definition: clauses.c:365
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
Definition: equivclass.c:1375
List * list_copy(const List *oldlist)
Definition: list.c:1572
List * list_concat(List *list1, const List *list2)
Definition: list.c:560
@ RELOPT_OTHER_MEMBER_REL
Definition: pathnodes.h:823
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:487
Relids find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
Definition: relnode.c:1446
bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel)
Definition: restrictinfo.c:607
Relids all_query_rels
Definition: pathnodes.h:269
List * rowMarks
Definition: pathnodes.h:371
Relids all_result_relids
Definition: pathnodes.h:354
List * baserestrictinfo
Definition: pathnodes.h:974
List * joininfo
Definition: pathnodes.h:980
Index relid
Definition: pathnodes.h:913
List * indexlist
Definition: pathnodes.h:933
Expr * clause
Definition: pathnodes.h:2520

References PlannerInfo::all_query_rels, PlannerInfo::all_result_relids, Assert(), RelOptInfo::baserestrictinfo, 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, predicate_implied_by(), RelOptInfo::relid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, and PlannerInfo::rowMarks.

Referenced by set_plain_rel_size(), and set_tablesample_rel_size().

◆ compare_pathkeys()

PathKeysComparison compare_pathkeys ( List keys1,
List keys2 
)

Definition at line 301 of file pathkeys.c.

302 {
303  ListCell *key1,
304  *key2;
305 
306  /*
307  * Fall out quickly if we are passed two identical lists. This mostly
308  * catches the case where both are NIL, but that's common enough to
309  * warrant the test.
310  */
311  if (keys1 == keys2)
312  return PATHKEYS_EQUAL;
313 
314  forboth(key1, keys1, key2, keys2)
315  {
316  PathKey *pathkey1 = (PathKey *) lfirst(key1);
317  PathKey *pathkey2 = (PathKey *) lfirst(key2);
318 
319  if (pathkey1 != pathkey2)
320  return PATHKEYS_DIFFERENT; /* no need to keep looking */
321  }
322 
323  /*
324  * If we reached the end of only one list, the other is longer and
325  * therefore not a subset.
326  */
327  if (key1 != NULL)
328  return PATHKEYS_BETTER1; /* key1 is longer */
329  if (key2 != NULL)
330  return PATHKEYS_BETTER2; /* key2 is longer */
331  return PATHKEYS_EQUAL;
332 }
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:467

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

4130 {
4131  int parallel_workers = 0;
4132 
4133  /*
4134  * If the user has set the parallel_workers reloption, use that; otherwise
4135  * select a default number of workers.
4136  */
4137  if (rel->rel_parallel_workers != -1)
4138  parallel_workers = rel->rel_parallel_workers;
4139  else
4140  {
4141  /*
4142  * If the number of pages being scanned is insufficient to justify a
4143  * parallel scan, just return zero ... unless it's an inheritance
4144  * child. In that case, we want to generate a parallel path here
4145  * anyway. It might not be worthwhile just for this relation, but
4146  * when combined with all of its inheritance siblings it may well pay
4147  * off.
4148  */
4149  if (rel->reloptkind == RELOPT_BASEREL &&
4150  ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
4151  (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
4152  return 0;
4153 
4154  if (heap_pages >= 0)
4155  {
4156  int heap_parallel_threshold;
4157  int heap_parallel_workers = 1;
4158 
4159  /*
4160  * Select the number of workers based on the log of the size of
4161  * the relation. This probably needs to be a good deal more
4162  * sophisticated, but we need something here for now. Note that
4163  * the upper limit of the min_parallel_table_scan_size GUC is
4164  * chosen to prevent overflow here.
4165  */
4166  heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
4167  while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
4168  {
4169  heap_parallel_workers++;
4170  heap_parallel_threshold *= 3;
4171  if (heap_parallel_threshold > INT_MAX / 3)
4172  break; /* avoid overflow */
4173  }
4174 
4175  parallel_workers = heap_parallel_workers;
4176  }
4177 
4178  if (index_pages >= 0)
4179  {
4180  int index_parallel_workers = 1;
4181  int index_parallel_threshold;
4182 
4183  /* same calculation as for heap_pages above */
4184  index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
4185  while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
4186  {
4187  index_parallel_workers++;
4188  index_parallel_threshold *= 3;
4189  if (index_parallel_threshold > INT_MAX / 3)
4190  break; /* avoid overflow */
4191  }
4192 
4193  if (parallel_workers > 0)
4194  parallel_workers = Min(parallel_workers, index_parallel_workers);
4195  else
4196  parallel_workers = index_parallel_workers;
4197  }
4198  }
4199 
4200  /* In no case use more than caller supplied maximum number of workers */
4201  parallel_workers = Min(parallel_workers, max_workers);
4202 
4203  return parallel_workers;
4204 }
int min_parallel_index_scan_size
Definition: allpaths.c:67
int min_parallel_table_scan_size
Definition: allpaths.c:66
uint32 BlockNumber
Definition: block.h:31
int rel_parallel_workers
Definition: pathnodes.h:945

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

856 {
857  List *retval = NIL;
858  int retvallen = 0;
859  int outer_query_keys = list_length(root->query_pathkeys);
860  ListCell *i;
861 
862  foreach(i, subquery_pathkeys)
863  {
864  PathKey *sub_pathkey = (PathKey *) lfirst(i);
865  EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
866  PathKey *best_pathkey = NULL;
867 
868  if (sub_eclass->ec_has_volatile)
869  {
870  /*
871  * If the sub_pathkey's EquivalenceClass is volatile, then it must
872  * have come from an ORDER BY clause, and we have to match it to
873  * that same targetlist entry.
874  */
875  TargetEntry *tle;
876  Var *outer_var;
877 
878  if (sub_eclass->ec_sortref == 0) /* can't happen */
879  elog(ERROR, "volatile EquivalenceClass has no sortref");
880  tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
881  Assert(tle);
882  /* Is TLE actually available to the outer query? */
883  outer_var = find_var_for_subquery_tle(rel, tle);
884  if (outer_var)
885  {
886  /* We can represent this sub_pathkey */
887  EquivalenceMember *sub_member;
888  EquivalenceClass *outer_ec;
889 
890  Assert(list_length(sub_eclass->ec_members) == 1);
891  sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
892 
893  /*
894  * Note: it might look funny to be setting sortref = 0 for a
895  * reference to a volatile sub_eclass. However, the
896  * expression is *not* volatile in the outer query: it's just
897  * a Var referencing whatever the subquery emitted. (IOW, the
898  * outer query isn't going to re-execute the volatile
899  * expression itself.) So this is okay.
900  */
901  outer_ec =
903  (Expr *) outer_var,
904  sub_eclass->ec_opfamilies,
905  sub_member->em_datatype,
906  sub_eclass->ec_collation,
907  0,
908  rel->relids,
909  false);
910 
911  /*
912  * If we don't find a matching EC, sub-pathkey isn't
913  * interesting to the outer query
914  */
915  if (outer_ec)
916  best_pathkey =
918  outer_ec,
919  sub_pathkey->pk_opfamily,
920  sub_pathkey->pk_strategy,
921  sub_pathkey->pk_nulls_first);
922  }
923  }
924  else
925  {
926  /*
927  * Otherwise, the sub_pathkey's EquivalenceClass could contain
928  * multiple elements (representing knowledge that multiple items
929  * are effectively equal). Each element might match none, one, or
930  * more of the output columns that are visible to the outer query.
931  * This means we may have multiple possible representations of the
932  * sub_pathkey in the context of the outer query. Ideally we
933  * would generate them all and put them all into an EC of the
934  * outer query, thereby propagating equality knowledge up to the
935  * outer query. Right now we cannot do so, because the outer
936  * query's EquivalenceClasses are already frozen when this is
937  * called. Instead we prefer the one that has the highest "score"
938  * (number of EC peers, plus one if it matches the outer
939  * query_pathkeys). This is the most likely to be useful in the
940  * outer query.
941  */
942  int best_score = -1;
943  ListCell *j;
944 
945  foreach(j, sub_eclass->ec_members)
946  {
947  EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
948  Expr *sub_expr = sub_member->em_expr;
949  Oid sub_expr_type = sub_member->em_datatype;
950  Oid sub_expr_coll = sub_eclass->ec_collation;
951  ListCell *k;
952 
953  if (sub_member->em_is_child)
954  continue; /* ignore children here */
955 
956  foreach(k, subquery_tlist)
957  {
958  TargetEntry *tle = (TargetEntry *) lfirst(k);
959  Var *outer_var;
960  Expr *tle_expr;
961  EquivalenceClass *outer_ec;
962  PathKey *outer_pk;
963  int score;
964 
965  /* Is TLE actually available to the outer query? */
966  outer_var = find_var_for_subquery_tle(rel, tle);
967  if (!outer_var)
968  continue;
969 
970  /*
971  * The targetlist entry is considered to match if it
972  * matches after sort-key canonicalization. That is
973  * needed since the sub_expr has been through the same
974  * process.
975  */
976  tle_expr = canonicalize_ec_expression(tle->expr,
977  sub_expr_type,
978  sub_expr_coll);
979  if (!equal(tle_expr, sub_expr))
980  continue;
981 
982  /* See if we have a matching EC for the TLE */
983  outer_ec = get_eclass_for_sort_expr(root,
984  (Expr *) outer_var,
985  sub_eclass->ec_opfamilies,
986  sub_expr_type,
987  sub_expr_coll,
988  0,
989  rel->relids,
990  false);
991 
992  /*
993  * If we don't find a matching EC, this sub-pathkey isn't
994  * interesting to the outer query
995  */
996  if (!outer_ec)
997  continue;
998 
999  outer_pk = make_canonical_pathkey(root,
1000  outer_ec,
1001  sub_pathkey->pk_opfamily,
1002  sub_pathkey->pk_strategy,
1003  sub_pathkey->pk_nulls_first);
1004  /* score = # of equivalence peers */
1005  score = list_length(outer_ec->ec_members) - 1;
1006  /* +1 if it matches the proper query_pathkeys item */
1007  if (retvallen < outer_query_keys &&
1008  list_nth(root->query_pathkeys, retvallen) == outer_pk)
1009  score++;
1010  if (score > best_score)
1011  {
1012  best_pathkey = outer_pk;
1013  best_score = score;
1014  }
1015  }
1016  }
1017  }
1018 
1019  /*
1020  * If we couldn't find a representation of this sub_pathkey, we're
1021  * done (we can't use the ones to its right, either).
1022  */
1023  if (!best_pathkey)
1024  break;
1025 
1026  /*
1027  * Eliminate redundant ordering info; could happen if outer query
1028  * equivalences subquery keys...
1029  */
1030  if (!pathkey_is_redundant(best_pathkey, retval))
1031  {
1032  retval = lappend(retval, best_pathkey);
1033  retvallen++;
1034  }
1035  }
1036 
1037  return retval;
1038 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:225
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:469
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:584
int j
Definition: isn.c:74
static Var * find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
Definition: pathkeys.c:1050
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:54
List * ec_opfamilies
Definition: pathnodes.h:1378
bool pk_nulls_first
Definition: pathnodes.h:1466
int pk_strategy
Definition: pathnodes.h:1465
Oid pk_opfamily
Definition: pathnodes.h:1464
List * query_pathkeys
Definition: pathnodes.h:385
Definition: primnodes.h:223
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, PlannerInfo::query_pathkeys, and RelOptInfo::relids.

Referenced by set_subquery_pathlist().

◆ create_index_paths()

void create_index_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 235 of file indxpath.c.

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

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, and RelOptInfo::relid.

Referenced by set_plain_rel_pathlist().

◆ create_partial_bitmap_paths()

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

Definition at line 4092 of file allpaths.c.

4094 {
4095  int parallel_workers;
4096  double pages_fetched;
4097 
4098  /* Compute heap pages for bitmap heap scan */
4099  pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
4100  NULL, NULL);
4101 
4102  parallel_workers = compute_parallel_worker(rel, pages_fetched, -1,
4104 
4105  if (parallel_workers <= 0)
4106  return;
4107 
4108  add_partial_path(rel, (Path *) create_bitmap_heap_path(root, rel,
4109  bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
4110 }
int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
Definition: allpaths.c:4128
double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, int loop_count, Cost *cost, double *tuple)
Definition: costsize.c:6144

References add_partial_path(), compute_bitmap_pages(), compute_parallel_worker(), create_bitmap_heap_path(), RelOptInfo::lateral_relids, and max_parallel_workers_per_gather.

Referenced by create_index_paths().

◆ create_tidscan_paths()

void create_tidscan_paths ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 460 of file tidpath.c.

461 {
462  List *tidquals;
463  List *tidrangequals;
464 
465  /*
466  * If any suitable quals exist in the rel's baserestrict list, generate a
467  * plain (unparameterized) TidPath with them.
468  */
469  tidquals = TidQualFromRestrictInfoList(root, rel->baserestrictinfo, rel);
470 
471  if (tidquals != NIL)
472  {
473  /*
474  * This path uses no join clauses, but it could still have required
475  * parameterization due to LATERAL refs in its tlist.
476  */
477  Relids required_outer = rel->lateral_relids;
478 
479  add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
480  required_outer));
481  }
482 
483  /*
484  * If there are range quals in the baserestrict list, generate a
485  * TidRangePath.
486  */
488  rel);
489 
490  if (tidrangequals != NIL)
491  {
492  /*
493  * This path uses no join clauses, but it could still have required
494  * parameterization due to LATERAL refs in its tlist.
495  */
496  Relids required_outer = rel->lateral_relids;
497 
498  add_path(rel, (Path *) create_tidrangescan_path(root, rel,
499  tidrangequals,
500  required_outer));
501  }
502 
503  /*
504  * Try to generate parameterized TidPaths using equality clauses extracted
505  * from EquivalenceClasses. (This is important since simple "t1.ctid =
506  * t2.ctid" clauses will turn into ECs.)
507  */
508  if (rel->has_eclass_joins)
509  {
510  List *clauses;
511 
512  /* Generate clauses, skipping any that join to lateral_referencers */
514  rel,
516  NULL,
517  rel->lateral_referencers);
518 
519  /* Generate a path for each usable join clause */
520  BuildParameterizedTidPaths(root, rel, clauses);
521  }
522 
523  /*
524  * Also consider parameterized TidPaths using "loose" join quals. Quals
525  * of the form "t1.ctid = t2.ctid" would turn into these if they are outer
526  * join quals, for example.
527  */
528  BuildParameterizedTidPaths(root, rel, rel->joininfo);
529 }
List * generate_implied_equalities_for_column(PlannerInfo *root, RelOptInfo *rel, ec_matches_callback_type callback, void *callback_arg, Relids prohibited_rels)
Definition: equivclass.c:2846
TidPath * create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals, Relids required_outer)
Definition: pathnode.c:1183
TidRangePath * create_tidrangescan_path(PlannerInfo *root, RelOptInfo *rel, List *tidrangequals, Relids required_outer)
Definition: pathnode.c:1212
Relids lateral_referencers
Definition: pathnodes.h:931
bool has_eclass_joins
Definition: pathnodes.h:982
static void BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
Definition: tidpath.c:388
static List * TidQualFromRestrictInfoList(PlannerInfo *root, List *rlist, RelOptInfo *rel)
Definition: tidpath.c:277
static List * TidRangeQualFromRestrictInfoList(List *rlist, RelOptInfo *rel)
Definition: tidpath.c:360
static bool ec_member_matches_ctid(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg)
Definition: tidpath.c:443

References add_path(), RelOptInfo::baserestrictinfo, BuildParameterizedTidPaths(), create_tidrangescan_path(), create_tidscan_path(), ec_member_matches_ctid(), generate_implied_equalities_for_column(), RelOptInfo::has_eclass_joins, RelOptInfo::joininfo, RelOptInfo::lateral_referencers, RelOptInfo::lateral_relids, NIL, 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 3087 of file equivclass.c.

3090 {
3091  Relids relids;
3092  ListCell *lc;
3093 
3094  Assert(!eclass->ec_merged);
3095 
3096  /*
3097  * Won't generate joinclauses if const or single-member (the latter test
3098  * covers the volatile case too)
3099  */
3100  if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
3101  return false;
3102 
3103  /*
3104  * Note we don't test ec_broken; if we did, we'd need a separate code path
3105  * to look through ec_sources. Checking the members anyway is OK as a
3106  * possibly-overoptimistic heuristic.
3107  */
3108 
3109  /* If specified rel is a child, we must consider the topmost parent rel */
3110  if (IS_OTHER_REL(rel))
3111  {
3113  relids = rel->top_parent_relids;
3114  }
3115  else
3116  relids = rel->relids;
3117 
3118  /* If rel already includes all members of eclass, no point in searching */
3119  if (bms_is_subset(eclass->ec_relids, relids))
3120  return false;
3121 
3122  /* To join, we need a member not in the given rel */
3123  foreach(lc, eclass->ec_members)
3124  {
3125  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
3126 
3127  if (cur_em->em_is_child)
3128  continue; /* ignore children here */
3129 
3130  if (!bms_overlap(cur_em->em_relids, relids))
3131  return true;
3132  }
3133 
3134  return false;
3135 }
#define IS_OTHER_REL(rel)
Definition: pathnodes.h:849
static struct cvec * eclass(struct vars *v, chr c, int cases)
Definition: regc_locale.c:504

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 
)

Definition at line 2401 of file equivclass.c.

2402 {
2403  ListCell *lc1;
2404 
2405  foreach(lc1, root->eq_classes)
2406  {
2407  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2408  bool item1member = false;
2409  bool item2member = false;
2410  ListCell *lc2;
2411 
2412  /* Never match to a volatile EC */
2413  if (ec->ec_has_volatile)
2414  continue;
2415 
2416  foreach(lc2, ec->ec_members)
2417  {
2419 
2420  if (em->em_is_child)
2421  continue; /* ignore children here */
2422  if (equal(item1, em->em_expr))
2423  item1member = true;
2424  else if (equal(item2, em->em_expr))
2425  item2member = true;
2426  /* Exit as soon as equality is proven */
2427  if (item1member && item2member)
2428  return true;
2429  }
2430  }
2431  return false;
2432 }

References EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, PlannerInfo::eq_classes, equal(), and lfirst.

Referenced by add_unique_group_var().

◆ find_computable_ec_member()

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

Definition at line 823 of file equivclass.c.

828 {
829  ListCell *lc;
830 
831  foreach(lc, ec->ec_members)
832  {
834  List *exprvars;
835  ListCell *lc2;
836 
837  /*
838  * We shouldn't be trying to sort by an equivalence class that
839  * contains a constant, so no need to consider such cases any further.
840  */
841  if (em->em_is_const)
842  continue;
843 
844  /*
845  * Ignore child members unless they belong to the requested rel.
846  */
847  if (em->em_is_child &&
848  !bms_is_subset(em->em_relids, relids))
849  continue;
850 
851  /*
852  * Match if all Vars and quasi-Vars are available in "exprs".
853  */
854  exprvars = pull_var_clause((Node *) em->em_expr,
858  foreach(lc2, exprvars)
859  {
860  if (!is_exprlist_member(lfirst(lc2), exprs))
861  break;
862  }
863  list_free(exprvars);
864  if (lc2)
865  continue; /* we hit a non-available Var */
866 
867  /*
868  * If requested, reject expressions that are not parallel-safe. We
869  * check this last because it's a rather expensive test.
870  */
871  if (require_parallel_safe &&
872  !is_parallel_safe(root, (Node *) em->em_expr))
873  continue;
874 
875  return em; /* found usable expression */
876  }
877 
878  return NULL;
879 }
bool is_parallel_safe(PlannerInfo *root, Node *node)
Definition: clauses.c:634
static bool is_exprlist_member(Expr *node, List *exprs)
Definition: equivclass.c:889
void list_free(List *list)
Definition: list.c:1545
#define PVC_INCLUDE_WINDOWFUNCS
Definition: optimizer.h:185
#define PVC_INCLUDE_PLACEHOLDERS
Definition: optimizer.h:187
#define PVC_INCLUDE_AGGREGATES
Definition: optimizer.h:183
List * pull_var_clause(Node *node, int flags)
Definition: var.c:617

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

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

2545 {
2546  ListCell *lc;
2547 
2548  Assert(ec->ec_has_const);
2549  Assert(!em->em_is_const);
2550  foreach(lc, ec->ec_derives)
2551  {
2552  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2553 
2554  /*
2555  * generate_base_implied_equalities_const will have put non-const
2556  * members on the left side of derived clauses.
2557  */
2558  if (rinfo->left_em == em)
2559  return rinfo;
2560  }
2561  return NULL;
2562 }

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

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

1312 {
1313  List *mergeclauses = NIL;
1314  ListCell *i;
1315 
1316  /* make sure we have eclasses cached in the clauses */
1317  foreach(i, restrictinfos)
1318  {
1319  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1320 
1321  update_mergeclause_eclasses(root, rinfo);
1322  }
1323 
1324  foreach(i, pathkeys)
1325  {
1326  PathKey *pathkey = (PathKey *) lfirst(i);
1327  EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1328  List *matched_restrictinfos = NIL;
1329  ListCell *j;
1330 
1331  /*----------
1332  * A mergejoin clause matches a pathkey if it has the same EC.
1333  * If there are multiple matching clauses, take them all. In plain
1334  * inner-join scenarios we expect only one match, because
1335  * equivalence-class processing will have removed any redundant
1336  * mergeclauses. However, in outer-join scenarios there might be
1337  * multiple matches. An example is
1338  *
1339  * select * from a full join b
1340  * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1341  *
1342  * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1343  * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1344  * we *must* do so or we will be unable to form a valid plan.
1345  *
1346  * We expect that the given pathkeys list is canonical, which means
1347  * no two members have the same EC, so it's not possible for this
1348  * code to enter the same mergeclause into the result list twice.
1349  *
1350  * It's possible that multiple matching clauses might have different
1351  * ECs on the other side, in which case the order we put them into our
1352  * result makes a difference in the pathkeys required for the inner
1353  * input rel. However this routine hasn't got any info about which
1354  * order would be best, so we don't worry about that.
1355  *
1356  * It's also possible that the selected mergejoin clauses produce
1357  * a noncanonical ordering of pathkeys for the inner side, ie, we
1358  * might select clauses that reference b.v1, b.v2, b.v1 in that
1359  * order. This is not harmful in itself, though it suggests that
1360  * the clauses are partially redundant. Since the alternative is
1361  * to omit mergejoin clauses and thereby possibly fail to generate a
1362  * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1363  * has to delete duplicates when it constructs the inner pathkeys
1364  * list, and we also have to deal with such cases specially in
1365  * create_mergejoin_plan().
1366  *----------
1367  */
1368  foreach(j, restrictinfos)
1369  {
1370  RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1371  EquivalenceClass *clause_ec;
1372 
1373  clause_ec = rinfo->outer_is_left ?
1374  rinfo->left_ec : rinfo->right_ec;
1375  if (clause_ec == pathkey_ec)
1376  matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1377  }
1378 
1379  /*
1380  * If we didn't find a mergeclause, we're done --- any additional
1381  * sort-key positions in the pathkeys are useless. (But we can still
1382  * mergejoin if we found at least one mergeclause.)
1383  */
1384  if (matched_restrictinfos == NIL)
1385  break;
1386 
1387  /*
1388  * If we did find usable mergeclause(s) for this sort-key position,
1389  * add them to result list.
1390  */
1391  mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1392  }
1393 
1394  return mergeclauses;
1395 }
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1275

References i, j, lappend(), lfirst, list_concat(), NIL, 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 1031 of file equivclass.c.

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

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, PlannerInfo::ec_merging_done, EquivalenceClass::ec_relids, RelOptInfo::eclass_indexes, PlannerInfo::eq_classes, generate_base_implied_equalities_broken(), generate_base_implied_equalities_const(), generate_base_implied_equalities_no_const(), RelOptInfo::has_eclass_joins, i, lfirst, list_length(), PlannerInfo::outer_join_rels, RELOPT_BASEREL, and RelOptInfo::reloptkind.

Referenced by query_planner().

◆ generate_gather_paths()

void generate_gather_paths ( PlannerInfo root,
RelOptInfo rel,
bool  override_rows 
)

Definition at line 2993 of file allpaths.c.

2994 {
2995  Path *cheapest_partial_path;
2996  Path *simple_gather_path;
2997  ListCell *lc;
2998  double rows;
2999  double *rowsp = NULL;
3000 
3001  /* If there are no partial paths, there's nothing to do here. */
3002  if (rel->partial_pathlist == NIL)
3003  return;
3004 
3005  /* Should we override the rel's rowcount estimate? */
3006  if (override_rows)
3007  rowsp = &rows;
3008 
3009  /*
3010  * The output of Gather is always unsorted, so there's only one partial
3011  * path of interest: the cheapest one. That will be the one at the front
3012  * of partial_pathlist because of the way add_partial_path works.
3013  */
3014  cheapest_partial_path = linitial(rel->partial_pathlist);
3015  rows =
3016  cheapest_partial_path->rows * cheapest_partial_path->parallel_workers;
3017  simple_gather_path = (Path *)
3018  create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
3019  NULL, rowsp);
3020  add_path(rel, simple_gather_path);
3021 
3022  /*
3023  * For each useful ordering, we can consider an order-preserving Gather
3024  * Merge.
3025  */
3026  foreach(lc, rel->partial_pathlist)
3027  {
3028  Path *subpath = (Path *) lfirst(lc);
3029  GatherMergePath *path;
3030 
3031  if (subpath->pathkeys == NIL)
3032  continue;
3033 
3034  rows = subpath->rows * subpath->parallel_workers;
3035  path = create_gather_merge_path(root, rel, subpath, rel->reltarget,
3036  subpath->pathkeys, NULL, rowsp);
3037  add_path(rel, &path->path);
3038  }
3039 }
GatherMergePath * create_gather_merge_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, List *pathkeys, Relids required_outer, double *rows)
Definition: pathnode.c:1873
GatherPath * create_gather_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, Relids required_outer, double *rows)
Definition: pathnode.c:1964
struct PathTarget * reltarget
Definition: pathnodes.h:888

References add_path(), create_gather_merge_path(), create_gather_path(), lfirst, linitial, NIL, Path::parallel_workers, RelOptInfo::partial_pathlist, GatherMergePath::path, RelOptInfo::reltarget, Path::rows, and subpath().

Referenced by create_partial_distinct_paths(), and 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 2846 of file equivclass.c.

2851 {
2852  List *result = NIL;
2853  bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
2854  Relids parent_relids;
2855  int i;
2856 
2857  /* Should be OK to rely on eclass_indexes */
2858  Assert(root->ec_merging_done);
2859 
2860  /* Indexes are available only on base or "other" member relations. */
2861  Assert(IS_SIMPLE_REL(rel));
2862 
2863  /* If it's a child rel, we'll need to know what its parent(s) are */
2864  if (is_child_rel)
2865  parent_relids = find_childrel_parents(root, rel);
2866  else
2867  parent_relids = NULL; /* not used, but keep compiler quiet */
2868 
2869  i = -1;
2870  while ((i = bms_next_member(rel->eclass_indexes, i)) >= 0)
2871  {
2872  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2873  EquivalenceMember *cur_em;
2874  ListCell *lc2;
2875 
2876  /* Sanity check eclass_indexes only contain ECs for rel */
2877  Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
2878 
2879  /*
2880  * Won't generate joinclauses if const or single-member (the latter
2881  * test covers the volatile case too)
2882  */
2883  if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
2884  continue;
2885 
2886  /*
2887  * Scan members, looking for a match to the target column. Note that
2888  * child EC members are considered, but only when they belong to the
2889  * target relation. (Unlike regular members, the same expression
2890  * could be a child member of more than one EC. Therefore, it's
2891  * potentially order-dependent which EC a child relation's target
2892  * column gets matched to. This is annoying but it only happens in
2893  * corner cases, so for now we live with just reporting the first
2894  * match. See also get_eclass_for_sort_expr.)
2895  */
2896  cur_em = NULL;
2897  foreach(lc2, cur_ec->ec_members)
2898  {
2899  cur_em = (EquivalenceMember *) lfirst(lc2);
2900  if (bms_equal(cur_em->em_relids, rel->relids) &&
2901  callback(root, rel, cur_ec, cur_em, callback_arg))
2902  break;
2903  cur_em = NULL;
2904  }
2905 
2906  if (!cur_em)
2907  continue;
2908 
2909  /*
2910  * Found our match. Scan the other EC members and attempt to generate
2911  * joinclauses.
2912  */
2913  foreach(lc2, cur_ec->ec_members)
2914  {
2915  EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
2916  Oid eq_op;
2917  RestrictInfo *rinfo;
2918 
2919  if (other_em->em_is_child)
2920  continue; /* ignore children here */
2921 
2922  /* Make sure it'll be a join to a different rel */
2923  if (other_em == cur_em ||
2924  bms_overlap(other_em->em_relids, rel->relids))
2925  continue;
2926 
2927  /* Forget it if caller doesn't want joins to this rel */
2928  if (bms_overlap(other_em->em_relids, prohibited_rels))
2929  continue;
2930 
2931  /*
2932  * Also, if this is a child rel, avoid generating a useless join
2933  * to its parent rel(s).
2934  */
2935  if (is_child_rel &&
2936  bms_overlap(parent_relids, other_em->em_relids))
2937  continue;
2938 
2939  eq_op = select_equality_operator(cur_ec,
2940  cur_em->em_datatype,
2941  other_em->em_datatype);
2942  if (!OidIsValid(eq_op))
2943  continue;
2944 
2945  /* set parent_ec to mark as redundant with other joinclauses */
2946  rinfo = create_join_clause(root, cur_ec, eq_op,
2947  cur_em, other_em,
2948  cur_ec);
2949 
2950  result = lappend(result, rinfo);
2951  }
2952 
2953  /*
2954  * If somehow we failed to create any join clauses, we might as well
2955  * keep scanning the ECs for another match. But if we did make any,
2956  * we're done, because we don't want to return non-redundant clauses.
2957  */
2958  if (result)
2959  break;
2960  }
2961 
2962  return result;
2963 }
#define OidIsValid(objectId)
Definition: c.h:759
static RestrictInfo * create_join_clause(PlannerInfo *root, EquivalenceClass *ec, Oid opno, EquivalenceMember *leftem, EquivalenceMember *rightem, EquivalenceClass *parent_ec)
Definition: equivclass.c:1785
static Oid select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype)
Definition: equivclass.c:1749
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, PlannerInfo::ec_merging_done, EquivalenceClass::ec_relids, RelOptInfo::eclass_indexes, EquivalenceMember::em_datatype, EquivalenceMember::em_is_child, EquivalenceMember::em_relids, PlannerInfo::eq_classes, find_childrel_parents(), i, IS_SIMPLE_REL, lappend(), lfirst, list_length(), list_nth(), NIL, OidIsValid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, 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 
)

Definition at line 1375 of file equivclass.c.

1379 {
1380  List *result = NIL;
1381  Relids inner_relids = inner_rel->relids;
1382  Relids nominal_inner_relids;
1383  Relids nominal_join_relids;
1384  Bitmapset *matching_ecs;
1385  int i;
1386 
1387  /* If inner rel is a child, extra setup work is needed */
1388  if (IS_OTHER_REL(inner_rel))
1389  {
1390  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1391 
1392  /* Fetch relid set for the topmost parent rel */
1393  nominal_inner_relids = inner_rel->top_parent_relids;
1394  /* ECs will be marked with the parent's relid, not the child's */
1395  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1396  }
1397  else
1398  {
1399  nominal_inner_relids = inner_relids;
1400  nominal_join_relids = join_relids;
1401  }
1402 
1403  /*
1404  * Get all eclasses that mention both inner and outer sides of the join
1405  */
1406  matching_ecs = get_common_eclass_indexes(root, nominal_inner_relids,
1407  outer_relids);
1408 
1409  i = -1;
1410  while ((i = bms_next_member(matching_ecs, i)) >= 0)
1411  {
1413  List *sublist = NIL;
1414 
1415  /* ECs containing consts do not need any further enforcement */
1416  if (ec->ec_has_const)
1417  continue;
1418 
1419  /* Single-member ECs won't generate any deductions */
1420  if (list_length(ec->ec_members) <= 1)
1421  continue;
1422 
1423  /* Sanity check that this eclass overlaps the join */
1424  Assert(bms_overlap(ec->ec_relids, nominal_join_relids));
1425 
1426  if (!ec->ec_broken)
1428  ec,
1429  join_relids,
1430  outer_relids,
1431  inner_relids);
1432 
1433  /* Recover if we failed to generate required derived clauses */
1434  if (ec->ec_broken)
1436  ec,
1437  nominal_join_relids,
1438  outer_relids,
1439  nominal_inner_relids,
1440  inner_rel);
1441 
1442  result = list_concat(result, sublist);
1443  }
1444 
1445  return result;
1446 }
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1524
static Bitmapset * get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
Definition: equivclass.c:3238
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:1700

References Assert(), bms_is_empty(), bms_next_member(), bms_overlap(), bms_union(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, PlannerInfo::eq_classes, generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), get_common_eclass_indexes(), i, IS_OTHER_REL, list_concat(), list_length(), list_nth(), NIL, RelOptInfo::relids, 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 1453 of file equivclass.c.

1458 {
1459  List *result = NIL;
1460  Relids inner_relids = inner_rel->relids;
1461  Relids nominal_inner_relids;
1462  Relids nominal_join_relids;
1463  ListCell *lc;
1464 
1465  /* If inner rel is a child, extra setup work is needed */
1466  if (IS_OTHER_REL(inner_rel))
1467  {
1468  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1469 
1470  /* Fetch relid set for the topmost parent rel */
1471  nominal_inner_relids = inner_rel->top_parent_relids;
1472  /* ECs will be marked with the parent's relid, not the child's */
1473  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1474  }
1475  else
1476  {
1477  nominal_inner_relids = inner_relids;
1478  nominal_join_relids = join_relids;
1479  }
1480 
1481  foreach(lc, eclasses)
1482  {
1484  List *sublist = NIL;
1485 
1486  /* ECs containing consts do not need any further enforcement */
1487  if (ec->ec_has_const)
1488  continue;
1489 
1490  /* Single-member ECs won't generate any deductions */
1491  if (list_length(ec->ec_members) <= 1)
1492  continue;
1493 
1494  /* We can quickly ignore any that don't overlap the join, too */
1495  if (!bms_overlap(ec->ec_relids, nominal_join_relids))
1496  continue;
1497 
1498  if (!ec->ec_broken)
1500  ec,
1501  join_relids,
1502  outer_relids,
1503  inner_relids);
1504 
1505  /* Recover if we failed to generate required derived clauses */
1506  if (ec->ec_broken)
1508  ec,
1509  nominal_join_relids,
1510  outer_relids,
1511  nominal_inner_relids,
1512  inner_rel);
1513 
1514  result = list_concat(result, sublist);
1515  }
1516 
1517  return result;
1518 }

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

4217 {
4218  List *live_children = NIL;
4219  int cnt_parts;
4220  int num_parts;
4221  RelOptInfo **part_rels;
4222 
4223  /* Handle only join relations here. */
4224  if (!IS_JOIN_REL(rel))
4225  return;
4226 
4227  /* We've nothing to do if the relation is not partitioned. */
4228  if (!IS_PARTITIONED_REL(rel))
4229  return;
4230 
4231  /* The relation should have consider_partitionwise_join set. */
4233 
4234  /* Guard against stack overflow due to overly deep partition hierarchy. */
4236 
4237  num_parts = rel->nparts;
4238  part_rels = rel->part_rels;
4239 
4240  /* Collect non-dummy child-joins. */
4241  for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
4242  {
4243  RelOptInfo *child_rel = part_rels[cnt_parts];
4244 
4245  /* If it's been pruned entirely, it's certainly dummy. */
4246  if (child_rel == NULL)
4247  continue;
4248 
4249  /* Make partitionwise join paths for this partitioned child-join. */
4250  generate_partitionwise_join_paths(root, child_rel);
4251 
4252  /* If we failed to make any path for this child, we must give up. */
4253  if (child_rel->pathlist == NIL)
4254  {
4255  /*
4256  * Mark the parent joinrel as unpartitioned so that later
4257  * functions treat it correctly.
4258  */
4259  rel->nparts = 0;
4260  return;
4261  }
4262 
4263  /* Else, identify the cheapest path for it. */
4264  set_cheapest(child_rel);
4265 
4266  /* Dummy children need not be scanned, so ignore those. */
4267  if (IS_DUMMY_REL(child_rel))
4268  continue;
4269 
4270 #ifdef OPTIMIZER_DEBUG
4271  debug_print_rel(root, child_rel);
4272 #endif
4273 
4274  live_children = lappend(live_children, child_rel);
4275  }
4276 
4277  /* If all child-joins are dummy, parent join is also dummy. */
4278  if (!live_children)
4279  {
4280  mark_dummy_rel(rel);
4281  return;
4282  }
4283 
4284  /* Build additional paths for this rel from child-join paths. */
4285  add_paths_to_append_rel(root, rel, live_children);
4286  list_free(live_children);
4287 }
void generate_partitionwise_join_paths(PlannerInfo *root, RelOptInfo *rel)
Definition: allpaths.c:4216
void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels)
Definition: allpaths.c:1267
void mark_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1271
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:244
#define IS_DUMMY_REL(r)
Definition: pathnodes.h:1914
#define IS_PARTITIONED_REL(rel)
Definition: pathnodes.h:1051
void check_stack_depth(void)
Definition: postgres.c:3454
bool consider_partitionwise_join
Definition: pathnodes.h:988

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

3132 {
3133  ListCell *lc;
3134  double rows;
3135  double *rowsp = NULL;
3136  List *useful_pathkeys_list = NIL;
3137  Path *cheapest_partial_path = NULL;
3138 
3139  /* If there are no partial paths, there's nothing to do here. */
3140  if (rel->partial_pathlist == NIL)
3141  return;
3142 
3143  /* Should we override the rel's rowcount estimate? */
3144  if (override_rows)
3145  rowsp = &rows;
3146 
3147  /* generate the regular gather (merge) paths */
3148  generate_gather_paths(root, rel, override_rows);
3149 
3150  /* consider incremental sort for interesting orderings */
3151  useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel, true);
3152 
3153  /* used for explicit (full) sort paths */
3154  cheapest_partial_path = linitial(rel->partial_pathlist);
3155 
3156  /*
3157  * Consider sorted paths for each interesting ordering. We generate both
3158  * incremental and full sort.
3159  */
3160  foreach(lc, useful_pathkeys_list)
3161  {
3162  List *useful_pathkeys = lfirst(lc);
3163  ListCell *lc2;
3164  bool is_sorted;
3165  int presorted_keys;
3166 
3167  foreach(lc2, rel->partial_pathlist)
3168  {
3169  Path *subpath = (Path *) lfirst(lc2);
3170  GatherMergePath *path;
3171 
3172  is_sorted = pathkeys_count_contained_in(useful_pathkeys,
3173  subpath->pathkeys,
3174  &presorted_keys);
3175 
3176  /*
3177  * We don't need to consider the case where a subpath is already
3178  * fully sorted because generate_gather_paths already creates a
3179  * gather merge path for every subpath that has pathkeys present.
3180  *
3181  * But since the subpath is already sorted, we know we don't need
3182  * to consider adding a sort (full or incremental) on top of it,
3183  * so we can continue here.
3184  */
3185  if (is_sorted)
3186  continue;
3187 
3188  /*
3189  * Try at least sorting the cheapest path and also try
3190  * incrementally sorting any path which is partially sorted
3191  * already (no need to deal with paths which have presorted keys
3192  * when incremental sort is disabled unless it's the cheapest
3193  * input path).
3194  */
3195  if (subpath != cheapest_partial_path &&
3196  (presorted_keys == 0 || !enable_incremental_sort))
3197  continue;
3198 
3199  /*
3200  * Consider regular sort for any path that's not presorted or if
3201  * incremental sort is disabled. We've no need to consider both
3202  * sort and incremental sort on the same path. We assume that
3203  * incremental sort is always faster when there are presorted
3204  * keys.
3205  *
3206  * This is not redundant with the gather paths created in
3207  * generate_gather_paths, because that doesn't generate ordered
3208  * output. Here we add an explicit sort to match the useful
3209  * ordering.
3210  */
3211  if (presorted_keys == 0 || !enable_incremental_sort)
3212  {
3213  subpath = (Path *) create_sort_path(root,
3214  rel,
3215  subpath,
3216  useful_pathkeys,
3217  -1.0);
3218  rows = subpath->rows * subpath->parallel_workers;
3219  }
3220  else
3222  rel,
3223  subpath,
3224  useful_pathkeys,
3225  presorted_keys,
3226  -1);
3227  path = create_gather_merge_path(root, rel,
3228  subpath,
3229  rel->reltarget,
3230  subpath->pathkeys,
3231  NULL,
3232  rowsp);
3233 
3234  add_path(rel, &path->path);
3235  }
3236  }
3237 }
void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
Definition: allpaths.c:2993
static List * get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel, bool require_parallel_safe)
Definition: allpaths.c:3063
bool enable_incremental_sort
Definition: costsize.c:141
bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
Definition: pathkeys.c:359
SortPath * create_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, double limit_tuples)
Definition: pathnode.c:2959
IncrementalSortPath * create_incremental_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, int presorted_keys, double limit_tuples)
Definition: pathnode.c:2910

References add_path(), 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, and subpath().

Referenced by apply_scanjoin_target_to_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 465 of file pathkeys.c.

469 {
470  Path *matched_path = NULL;
471  ListCell *l;
472 
473  foreach(l, paths)
474  {
475  Path *path = (Path *) lfirst(l);
476 
477  /*
478  * Since cost comparison is a lot cheaper than pathkey comparison, do
479  * that first. (XXX is that still true?)
480  */
481  if (matched_path != NULL &&
482  compare_fractional_path_costs(matched_path, path, fraction) <= 0)
483  continue;
484 
485  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
486  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
487  matched_path = path;
488  }
489  return matched_path;
490 }
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:340
int compare_fractional_path_costs(Path *path1, Path *path2, double fraction)
Definition: pathnode.c:117

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

499 {
500  ListCell *l;
501 
502  foreach(l, paths)
503  {
504  Path *innerpath = (Path *) lfirst(l);
505 
506  if (innerpath->parallel_safe &&
507  bms_is_empty(PATH_REQ_OUTER(innerpath)))
508  return innerpath;
509  }
510 
511  return NULL;
512 }
bool parallel_safe
Definition: pathnodes.h:1633

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

424 {
425  Path *matched_path = NULL;
426  ListCell *l;
427 
428  foreach(l, paths)
429  {
430  Path *path = (Path *) lfirst(l);
431 
432  /*
433  * Since cost comparison is a lot cheaper than pathkey comparison, do
434  * that first. (XXX is that still true?)
435  */
436  if (matched_path != NULL &&
437  compare_path_costs(matched_path, path, cost_criterion) <= 0)
438  continue;
439 
440  if (require_parallel_safe && !path->parallel_safe)
441  continue;
442 
443  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
444  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
445  matched_path = path;
446  }
447  return matched_path;
448 }
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:71

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(), 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 584 of file equivclass.c.

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

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, PlannerInfo::ec_merging_done, 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, PlannerInfo::eq_classes, equal(), ERROR, expression_returns_set(), i, PlannerInfo::join_domains, lappend(), lfirst, linitial_node, list_copy(), list_length(), makeNode, MemoryContextSwitchTo(), NIL, PlannerInfo::outer_join_rels, pull_varnos(), RELOPT_BASEREL, RELOPT_DEADREL, and RelOptInfo::reloptkind.

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

◆ has_relevant_eclass_joinclause()

bool has_relevant_eclass_joinclause ( PlannerInfo root,
RelOptInfo rel1 
)

Definition at line 3043 of file equivclass.c.

3044 {
3045  Bitmapset *matched_ecs;
3046  int i;
3047 
3048  /* Examine only eclasses mentioning rel1 */
3049  matched_ecs = get_eclass_indexes_for_relids(root, rel1->relids);
3050 
3051  i = -1;
3052  while ((i = bms_next_member(matched_ecs, i)) >= 0)
3053  {
3055  i);
3056 
3057  /*
3058  * Won't generate joinclauses if single-member (this test covers the
3059  * volatile case too)
3060  */
3061  if (list_length(ec->ec_members) <= 1)
3062  continue;
3063 
3064  /*
3065  * Per the comment in have_relevant_eclass_joinclause, it's sufficient
3066  * to find an EC that mentions both this rel and some other rel.
3067  */
3068  if (!bms_is_subset(ec->ec_relids, rel1->relids))
3069  return true;
3070  }
3071 
3072  return false;
3073 }

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

Referenced by build_join_rel().

◆ has_useful_pathkeys()

bool has_useful_pathkeys ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 1983 of file pathkeys.c.

1984 {
1985  if (rel->joininfo != NIL || rel->has_eclass_joins)
1986  return true; /* might be able to use pathkeys for merging */
1987  if (root->query_pathkeys != NIL)
1988  return true; /* might be able to use them for ordering */
1989  return false; /* definitely useless */
1990 }

References RelOptInfo::has_eclass_joins, RelOptInfo::joininfo, NIL, and PlannerInfo::query_pathkeys.

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

1196 {
1197  ListCell *lc;
1198 
1199  foreach(lc, root->placeholder_list)
1200  {
1201  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
1202 
1203  if (!bms_is_subset(phinfo->ph_eval_at, inner_params))
1204  continue; /* ignore, could not be a nestloop param */
1205  if (!bms_overlap(phinfo->ph_eval_at, outer_relids))
1206  continue; /* ignore, not relevant to this join */
1207  if (bms_is_subset(phinfo->ph_eval_at, outer_relids))
1208  continue; /* safe, it can be eval'd within outerrel */
1209  /* Otherwise, it's potentially unsafe, so reject the join */
1210  return true;
1211  }
1212 
1213  /* OK to perform the join */
1214  return false;
1215 }
Relids ph_eval_at
Definition: pathnodes.h:3025
List * placeholder_list
Definition: pathnodes.h:374

References bms_is_subset(), bms_overlap(), lfirst, PlaceHolderInfo::ph_eval_at, and PlannerInfo::placeholder_list.

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

963 {
964  bool result = false;
965  ListCell *l;
966 
967  /*
968  * If either side has a direct lateral reference to the other, attempt the
969  * join regardless of outer-join considerations.
970  */
971  if (bms_overlap(rel1->relids, rel2->direct_lateral_relids) ||
973  return true;
974 
975  /*
976  * Likewise, if both rels are needed to compute some PlaceHolderVar,
977  * attempt the join regardless of outer-join considerations. (This is not
978  * very desirable, because a PHV with a large eval_at set will cause a lot
979  * of probably-useless joins to be considered, but failing to do this can
980  * cause us to fail to construct a plan at all.)
981  */
982  foreach(l, root->placeholder_list)
983  {
984  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
985 
986  if (bms_is_subset(rel1->relids, phinfo->ph_eval_at) &&
987  bms_is_subset(rel2->relids, phinfo->ph_eval_at))
988  return true;
989  }
990 
991  /*
992  * It's possible that the rels correspond to the left and right sides of a
993  * degenerate outer join, that is, one with no joinclause mentioning the
994  * non-nullable side; in which case we should force the join to occur.
995  *
996  * Also, the two rels could represent a clauseless join that has to be
997  * completed to build up the LHS or RHS of an outer join.
998  */
999  foreach(l, root->join_info_list)
1000  {
1001  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
1002 
1003  /* ignore full joins --- other mechanisms handle them */
1004  if (sjinfo->jointype == JOIN_FULL)
1005  continue;
1006 
1007  /* Can we perform the SJ with these rels? */
1008  if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
1009  bms_is_subset(sjinfo->min_righthand, rel2->relids))
1010  {
1011  result = true;
1012  break;
1013  }
1014  if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
1015  bms_is_subset(sjinfo->min_righthand, rel1->relids))
1016  {
1017  result = true;
1018  break;
1019  }
1020 
1021  /*
1022  * Might we need to join these rels to complete the RHS? We have to
1023  * use "overlap" tests since either rel might include a lower SJ that
1024  * has been proven to commute with this one.
1025  */
1026  if (bms_overlap(sjinfo->min_righthand, rel1->relids) &&
1027  bms_overlap(sjinfo->min_righthand, rel2->relids))
1028  {
1029  result = true;
1030  break;
1031  }
1032 
1033  /* Likewise for the LHS. */
1034  if (bms_overlap(sjinfo->min_lefthand, rel1->relids) &&
1035  bms_overlap(sjinfo->min_lefthand, rel2->relids))
1036  {
1037  result = true;
1038  break;
1039  }
1040  }
1041 
1042  /*
1043  * We do not force the join to occur if either input rel can legally be
1044  * joined to anything else using joinclauses. This essentially means that
1045  * clauseless bushy joins are put off as long as possible. The reason is
1046  * that when there is a join order restriction high up in the join tree
1047  * (that is, with many rels inside the LHS or RHS), we would otherwise
1048  * expend lots of effort considering very stupid join combinations within
1049  * its LHS or RHS.
1050  */
1051  if (result)
1052  {
1053  if (has_legal_joinclause(root, rel1) ||
1054  has_legal_joinclause(root, rel2))
1055  result = false;
1056  }
1057 
1058  return result;
1059 }
static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1130
Relids direct_lateral_relids
Definition: pathnodes.h:906

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

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

2978 {
2979  Bitmapset *matching_ecs;
2980  int i;
2981 
2982  /* Examine only eclasses mentioning both rel1 and rel2 */
2983  matching_ecs = get_common_eclass_indexes(root, rel1->relids,
2984  rel2->relids);
2985 
2986  i = -1;
2987  while ((i = bms_next_member(matching_ecs, i)) >= 0)
2988  {
2990  i);
2991 
2992  /*
2993  * Sanity check that get_common_eclass_indexes gave only ECs
2994  * containing both rels.
2995  */
2996  Assert(bms_overlap(rel1->relids, ec->ec_relids));
2997  Assert(bms_overlap(rel2->relids, ec->ec_relids));
2998 
2999  /*
3000  * Won't generate joinclauses if single-member (this test covers the
3001  * volatile case too)
3002  */
3003  if (list_length(ec->ec_members) <= 1)
3004  continue;
3005 
3006  /*
3007  * We do not need to examine the individual members of the EC, because
3008  * all that we care about is whether each rel overlaps the relids of
3009  * at least one member, and get_common_eclass_indexes() and the single
3010  * member check above are sufficient to prove that. (As with
3011  * have_relevant_joinclause(), it is not necessary that the EC be able
3012  * to form a joinclause relating exactly the two given rels, only that
3013  * it be able to form a joinclause mentioning both, and this will
3014  * surely be true if both of them overlap ec_relids.)
3015  *
3016  * Note we don't test ec_broken; if we did, we'd need a separate code
3017  * path to look through ec_sources. Checking the membership anyway is
3018  * OK as a possibly-overoptimistic heuristic.
3019  *
3020  * We don't test ec_has_const either, even though a const eclass won't
3021  * generate real join clauses. This is because if we had "WHERE a.x =
3022  * b.y and a.x = 42", it is worth considering a join between a and b,
3023  * since the join result is likely to be small even though it'll end
3024  * up being an unqualified nestloop.
3025  */
3026 
3027  return true;
3028  }
3029 
3030  return false;
3031 }

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

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

3668 {
3669  ListCell *lc;
3670 
3671  /* If the index isn't boolean, we can't possibly get a match */
3672  if (!IsBooleanOpfamily(index->opfamily[indexcol]))
3673  return false;
3674 
3675  /* Check each restriction clause for the index's rel */
3676  foreach(lc, index->rel->baserestrictinfo)
3677  {
3678  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3679 
3680  /*
3681  * As in match_clause_to_indexcol, never match pseudoconstants to
3682  * indexes. (It might be semantically okay to do so here, but the
3683  * odds of getting a match are negligible, so don't waste the cycles.)
3684  */
3685  if (rinfo->pseudoconstant)
3686  continue;
3687 
3688  /* See if we can match the clause's expression to the index column */
3689  if (match_boolean_index_clause(root, rinfo, indexcol, index))
3690  return true;
3691  }
3692 
3693  return false;
3694 }
static bool IsBooleanOpfamily(Oid opfamily)
Definition: indxpath.c:2335
static IndexClause * match_boolean_index_clause(PlannerInfo *root, RestrictInfo *rinfo, int indexcol, IndexOptInfo *index)
Definition: indxpath.c:2360

References IsBooleanOpfamily(), lfirst, and match_boolean_index_clause().

Referenced by build_index_pathkeys().

◆ initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1228 of file pathkeys.c.

1229 {
1230  Expr *clause = restrictinfo->clause;
1231  Oid lefttype,
1232  righttype;
1233 
1234  /* Should be a mergeclause ... */
1235  Assert(restrictinfo->mergeopfamilies != NIL);
1236  /* ... with links not yet set */
1237  Assert(restrictinfo->left_ec == NULL);
1238  Assert(restrictinfo->right_ec == NULL);
1239 
1240  /* Need the declared input types of the operator */
1241  op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1242 
1243  /* Find or create a matching EquivalenceClass for each side */
1244  restrictinfo->left_ec =
1246  (Expr *) get_leftop(clause),
1247  restrictinfo->mergeopfamilies,
1248  lefttype,
1249  ((OpExpr *) clause)->inputcollid,
1250  0,
1251  NULL,
1252  true);
1253  restrictinfo->right_ec =
1255  (Expr *) get_rightop(clause),
1256  restrictinfo->mergeopfamilies,
1257  righttype,
1258  ((OpExpr *) clause)->inputcollid,
1259  0,
1260  NULL,
1261  true);
1262 }
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1340
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:93
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:81

References Assert(), RestrictInfo::clause, get_eclass_for_sort_expr(), get_leftop(), get_rightop(), NIL, and op_input_types().

Referenced by distribute_qual_to_rels().

◆ is_redundant_derived_clause()

bool is_redundant_derived_clause ( RestrictInfo rinfo,
List clauselist 
)

Definition at line 3145 of file equivclass.c.

3146 {
3147  EquivalenceClass *parent_ec = rinfo->parent_ec;
3148  ListCell *lc;
3149 
3150  /* Fail if it's not a potentially-redundant clause from some EC */
3151  if (parent_ec == NULL)
3152  return false;
3153 
3154  foreach(lc, clauselist)
3155  {
3156  RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
3157 
3158  if (otherrinfo->parent_ec == parent_ec)
3159  return true;
3160  }
3161 
3162  return false;
3163 }

References lfirst.

Referenced by create_tidscan_plan().

◆ is_redundant_with_indexclauses()

bool is_redundant_with_indexclauses ( RestrictInfo rinfo,
List indexclauses 
)

Definition at line 3172 of file equivclass.c.

3173 {
3174  EquivalenceClass *parent_ec = rinfo->parent_ec;
3175  ListCell *lc;
3176 
3177  foreach(lc, indexclauses)
3178  {
3179  IndexClause *iclause = lfirst_node(IndexClause, lc);
3180  RestrictInfo *otherrinfo = iclause->rinfo;
3181 
3182  /* If indexclause is lossy, it won't enforce the condition exactly */
3183  if (iclause->lossy)
3184  continue;
3185 
3186  /* Match if it's same clause (pointer equality should be enough) */
3187  if (rinfo == otherrinfo)
3188  return true;
3189  /* Match if derived from same EC */
3190  if (parent_ec && otherrinfo->parent_ec == parent_ec)
3191  return true;
3192 
3193  /*
3194  * No need to look at the derived clauses in iclause->indexquals; they
3195  * couldn't match if the parent clause didn't.
3196  */
3197  }
3198 
3199  return false;
3200 }
struct RestrictInfo * rinfo
Definition: pathnodes.h:1739

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

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

References Assert(), bms_overlap(), elog(), ERROR, for_each_cell, RelOptInfo::has_eclass_joins, has_join_restriction(), PlannerInfo::hasLateralRTEs, have_join_order_restriction(), have_relevant_joinclause(), PlannerInfo::join_cur_level, PlannerInfo::join_info_list, RelOptInfo::joininfo, lfirst, list_head(), lnext(), make_join_rel(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), NIL, and RelOptInfo::relids.

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

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

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

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

1623 {
1624  List *pathkeys = NIL;
1625  EquivalenceClass *lastoeclass;
1626  PathKey *opathkey;
1627  ListCell *lc;
1628  ListCell *lop;
1629 
1630  lastoeclass = NULL;
1631  opathkey = NULL;
1632  lop = list_head(outer_pathkeys);
1633 
1634  foreach(lc, mergeclauses)
1635  {
1636  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1637  EquivalenceClass *oeclass;
1638  EquivalenceClass *ieclass;
1639  PathKey *pathkey;
1640 
1641  update_mergeclause_eclasses(root, rinfo);
1642 
1643  if (rinfo->outer_is_left)
1644  {
1645  oeclass = rinfo->left_ec;
1646  ieclass = rinfo->right_ec;
1647  }
1648  else
1649  {
1650  oeclass = rinfo->right_ec;
1651  ieclass = rinfo->left_ec;
1652  }
1653 
1654  /* outer eclass should match current or next pathkeys */
1655  /* we check this carefully for debugging reasons */
1656  if (oeclass != lastoeclass)
1657  {
1658  if (!lop)
1659  elog(ERROR, "too few pathkeys for mergeclauses");
1660  opathkey = (PathKey *) lfirst(lop);
1661  lop = lnext(outer_pathkeys, lop);
1662  lastoeclass = opathkey->pk_eclass;
1663  if (oeclass != lastoeclass)
1664  elog(ERROR, "outer pathkeys do not match mergeclause");
1665  }
1666 
1667  /*
1668  * Often, we'll have same EC on both sides, in which case the outer
1669  * pathkey is also canonical for the inner side, and we can skip a
1670  * useless search.
1671  */
1672  if (ieclass == oeclass)
1673  pathkey = opathkey;
1674  else
1675  pathkey = make_canonical_pathkey(root,
1676  ieclass,
1677  opathkey->pk_opfamily,
1678  opathkey->pk_strategy,
1679  opathkey->pk_nulls_first);
1680 
1681  /*
1682  * Don't generate redundant pathkeys (which can happen if multiple
1683  * mergeclauses refer to the same EC). Because we do this, the output
1684  * pathkey list isn't necessarily ordered like the mergeclauses, which
1685  * complicates life for create_mergejoin_plan(). But if we didn't,
1686  * we'd have a noncanonical sort key list, which would be bad; for one
1687  * reason, it certainly wouldn't match any available sort order for
1688  * the input relation.
1689  */
1690  if (!pathkey_is_redundant(pathkey, pathkeys))
1691  pathkeys = lappend(pathkeys, pathkey);
1692  }
1693 
1694  return pathkeys;
1695 }

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

690 {
691  Relids joinrelids;
692  SpecialJoinInfo *sjinfo;
693  bool reversed;
694  SpecialJoinInfo sjinfo_data;
695  RelOptInfo *joinrel;
696  List *restrictlist;
697 
698  /* We should never try to join two overlapping sets of rels. */
699  Assert(!bms_overlap(rel1->relids, rel2->relids));
700 
701  /* Construct Relids set that identifies the joinrel (without OJ as yet). */
702  joinrelids = bms_union(rel1->relids, rel2->relids);
703 
704  /* Check validity and determine join type. */
705  if (!join_is_legal(root, rel1, rel2, joinrelids,
706  &sjinfo, &reversed))
707  {
708  /* invalid join path */
709  bms_free(joinrelids);
710  return NULL;
711  }
712 
713  /* If we have an outer join, add its RTI to form the canonical relids. */
714  if (sjinfo && sjinfo->ojrelid != 0)
715  joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid);
716 
717  /* Swap rels if needed to match the join info. */
718  if (reversed)
719  {
720  RelOptInfo *trel = rel1;
721 
722  rel1 = rel2;
723  rel2 = trel;
724  }
725 
726  /*
727  * If it's a plain inner join, then we won't have found anything in
728  * join_info_list. Make up a SpecialJoinInfo so that selectivity
729  * estimation functions will know what's being joined.
730  */
731  if (sjinfo == NULL)
732  {
733  sjinfo = &sjinfo_data;
734  sjinfo->type = T_SpecialJoinInfo;
735  sjinfo->min_lefthand = rel1->relids;
736  sjinfo->min_righthand = rel2->relids;
737  sjinfo->syn_lefthand = rel1->relids;
738  sjinfo->syn_righthand = rel2->relids;
739  sjinfo->jointype = JOIN_INNER;
740  sjinfo->ojrelid = 0;
741  sjinfo->commute_above_l = NULL;
742  sjinfo->commute_above_r = NULL;
743  sjinfo->commute_below = NULL;
744  /* we don't bother trying to make the remaining fields valid */
745  sjinfo->lhs_strict = false;
746  sjinfo->semi_can_btree = false;
747  sjinfo->semi_can_hash = false;
748  sjinfo->semi_operators = NIL;
749  sjinfo->semi_rhs_exprs = NIL;
750  }
751 
752  /*
753  * Find or build the join RelOptInfo, and compute the restrictlist that
754  * goes with this particular joining.
755  */
756  joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo,
757  &restrictlist);
758 
759  /*
760  * If we've already proven this join is empty, we needn't consider any
761  * more paths for it.
762  */
763  if (is_dummy_rel(joinrel))
764  {
765  bms_free(joinrelids);
766  return joinrel;
767  }
768 
769  /* Add paths to the join relation. */
770  populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo,
771  restrictlist);
772 
773  bms_free(joinrelids);
774 
775  return joinrel;
776 }
void bms_free(Bitmapset *a)
Definition: bitmapset.c:209
static void populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, RelOptInfo *joinrel, SpecialJoinInfo *sjinfo, List *restrictlist)
Definition: joinrels.c:786
bool is_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1222
static bool join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, Relids joinrelids, SpecialJoinInfo **sjinfo_p, bool *reversed_p)
Definition: joinrels.c:367
RelOptInfo * build_join_rel(PlannerInfo *root, Relids joinrelids, RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo, List **restrictlist_ptr)
Definition: relnode.c:632
Relids commute_above_r
Definition: pathnodes.h:2841
Relids syn_lefthand
Definition: pathnodes.h:2836
List * semi_rhs_exprs
Definition: pathnodes.h:2848
Relids commute_above_l
Definition: pathnodes.h:2840
Relids commute_below
Definition: pathnodes.h:2842
Relids syn_righthand
Definition: pathnodes.h:2837
List * semi_operators
Definition: pathnodes.h:2847

References Assert(), bms_add_member(), bms_free(), bms_overlap(), bms_union(), build_join_rel(), SpecialJoinInfo::commute_above_l, SpecialJoinInfo::commute_above_r, SpecialJoinInfo::commute_below, is_dummy_rel(), JOIN_INNER, join_is_legal(), SpecialJoinInfo::jointype, SpecialJoinInfo::lhs_strict, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, SpecialJoinInfo::ojrelid, populate_joinrel_with_paths(), RelOptInfo::relids, SpecialJoinInfo::semi_can_btree, SpecialJoinInfo::semi_can_hash, SpecialJoinInfo::semi_operators, SpecialJoinInfo::semi_rhs_exprs, SpecialJoinInfo::syn_lefthand, and SpecialJoinInfo::syn_righthand.

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

157 {
158  RelOptInfo *rel;
159  Index rti;
160  double total_pages;
161 
162  /* Mark base rels as to whether we care about fast-start plans */
164 
165  /*
166  * Compute size estimates and consider_parallel flags for each base rel.
167  */
168  set_base_rel_sizes(root);
169 
170  /*
171  * We should now have size estimates for every actual table involved in
172  * the query, and we also know which if any have been deleted from the
173  * query by join removal, pruned by partition pruning, or eliminated by
174  * constraint exclusion. So we can now compute total_table_pages.
175  *
176  * Note that appendrels are not double-counted here, even though we don't
177  * bother to distinguish RelOptInfos for appendrel parents, because the
178  * parents will have pages = 0.
179  *
180  * XXX if a table is self-joined, we will count it once per appearance,
181  * which perhaps is the wrong thing ... but that's not completely clear,
182  * and detecting self-joins here is difficult, so ignore it for now.
183  */
184  total_pages = 0;
185  for (rti = 1; rti < root->simple_rel_array_size; rti++)
186  {
187  RelOptInfo *brel = root->simple_rel_array[rti];
188 
189  /* there may be empty slots corresponding to non-baserel RTEs */
190  if (brel == NULL)
191  continue;
192 
193  Assert(brel->relid == rti); /* sanity check on array */
194 
195  if (IS_DUMMY_REL(brel))
196  continue;
197 
198  if (IS_SIMPLE_REL(brel))
199  total_pages += (double) brel->pages;
200  }
201  root->total_table_pages = total_pages;
202 
203  /*
204  * Generate access paths for each base rel.
205  */
207 
208  /*
209  * Generate access paths for the entire join tree.
210  */
211  rel = make_rel_from_joinlist(root, joinlist);
212 
213  /*
214  * The result should join all and only the query's base + outer-join rels.
215  */
216  Assert(bms_equal(rel->relids, root->all_query_rels));
217 
218  return rel;
219 }
static void set_base_rel_sizes(PlannerInfo *root)
Definition: allpaths.c:275
static void set_base_rel_consider_startup(PlannerInfo *root)
Definition: allpaths.c:232
static void set_base_rel_pathlists(PlannerInfo *root)
Definition: allpaths.c:318
static RelOptInfo * make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
Definition: allpaths.c:3247
unsigned int Index
Definition: c.h:598
int simple_rel_array_size
Definition: pathnodes.h:232
Cardinality total_table_pages
Definition: pathnodes.h:478
BlockNumber pages
Definition: pathnodes.h:937

References PlannerInfo::all_query_rels, Assert(), bms_equal(), IS_DUMMY_REL, IS_SIMPLE_REL, make_rel_from_joinlist(), RelOptInfo::pages, RelOptInfo::relid, RelOptInfo::relids, set_base_rel_consider_startup(), set_base_rel_pathlists(), set_base_rel_sizes(), PlannerInfo::simple_rel_array_size, and PlannerInfo::total_table_pages.

Referenced by query_planner().

◆ make_pathkeys_for_sortclauses()

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

Definition at line 1129 of file pathkeys.c.

1132 {
1133  List *result;
1134  bool sortable;
1135 
1137  &sortclauses,
1138  tlist,
1139  false,
1140  &sortable);
1141  /* It's caller error if not all clauses were sortable */
1142  Assert(sortable);
1143  return result;
1144 }
List * make_pathkeys_for_sortclauses_extended(PlannerInfo *root, List **sortclauses, List *tlist, bool remove_redundant, bool *sortable)
Definition: pathkeys.c:1166

References Assert(), and make_pathkeys_for_sortclauses_extended().

Referenced by adjust_group_pathkeys_for_groupagg(), generate_nonunion_paths(), grouping_planner(), make_pathkeys_for_window(), make_union_unique(), 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 sortable 
)

Definition at line 1166 of file pathkeys.c.

1171 {
1172  List *pathkeys = NIL;
1173  ListCell *l;
1174 
1175  *sortable = true;
1176  foreach(l, *sortclauses)
1177  {
1178  SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
1179  Expr *sortkey;
1180  PathKey *pathkey;
1181 
1182  sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
1183  if (!OidIsValid(sortcl->sortop))
1184  {
1185  *sortable = false;
1186  continue;
1187  }
1188  pathkey = make_pathkey_from_sortop(root,
1189  sortkey,
1190  sortcl->sortop,
1191  sortcl->nulls_first,
1192  sortcl->tleSortGroupRef,
1193  true);
1194 
1195  /* Canonical form eliminates redundant ordering keys */
1196  if (!pathkey_is_redundant(pathkey, pathkeys))
1197  pathkeys = lappend(pathkeys, pathkey);
1198  else if (remove_redundant)
1199  *sortclauses = foreach_delete_current(*sortclauses, l);
1200  }
1201  return pathkeys;
1202 }
static PathKey * make_pathkey_from_sortop(PlannerInfo *root, Expr *expr, Oid ordering_op, bool nulls_first, Index sortref, bool create_it)
Definition: pathkeys.c:254
#define foreach_delete_current(lst, cell)
Definition: pg_list.h:390
Index tleSortGroupRef
Definition: parsenodes.h:1392
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:379

References foreach_delete_current, get_sortgroupclause_expr(), lappend(), lfirst, make_pathkey_from_sortop(), NIL, SortGroupClause::nulls_first, OidIsValid, pathkey_is_redundant(), SortGroupClause::sortop, and SortGroupClause::tleSortGroupRef.

Referenced by make_pathkeys_for_sortclauses(), and standard_qp_callback().

◆ mark_dummy_rel()

void mark_dummy_rel ( RelOptInfo rel)

Definition at line 1271 of file joinrels.c.

1272 {
1273  MemoryContext oldcontext;
1274 
1275  /* Already marked? */
1276  if (is_dummy_rel(rel))
1277  return;
1278 
1279  /* No, so choose correct context to make the dummy path in */
1280  oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
1281 
1282  /* Set dummy size estimate */
1283  rel->rows = 0;
1284 
1285  /* Evict any previously chosen paths */
1286  rel->pathlist = NIL;
1287  rel->partial_pathlist = NIL;
1288 
1289  /* Set up the dummy path */
1290  add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NIL,
1291  NIL, rel->lateral_relids,
1292  0, false, -1));
1293 
1294  /* Set or update cheapest_total_path and related fields */
1295  set_cheapest(rel);
1296 
1297  MemoryContextSwitchTo(oldcontext);
1298 }
MemoryContext GetMemoryChunkContext(void *pointer)
Definition: mcxt.c:600
Cardinality rows
Definition: pathnodes.h:872

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

2455 {
2456  Index var1varno = fkinfo->con_relid;
2457  AttrNumber var1attno = fkinfo->conkey[colno];
2458  Index var2varno = fkinfo->ref_relid;
2459  AttrNumber var2attno = fkinfo->confkey[colno];
2460  Oid eqop = fkinfo->conpfeqop[colno];
2461  RelOptInfo *rel1 = root->simple_rel_array[var1varno];
2462  RelOptInfo *rel2 = root->simple_rel_array[var2varno];
2463  List *opfamilies = NIL; /* compute only if needed */
2464  Bitmapset *matching_ecs;
2465  int i;
2466 
2467  /* Consider only eclasses mentioning both relations */
2468  Assert(root->ec_merging_done);
2469  Assert(IS_SIMPLE_REL(rel1));
2470  Assert(IS_SIMPLE_REL(rel2));
2471  matching_ecs = bms_intersect(rel1->eclass_indexes,
2472  rel2->eclass_indexes);
2473 
2474  i = -1;
2475  while ((i = bms_next_member(matching_ecs, i)) >= 0)
2476  {
2478  i);
2479  EquivalenceMember *item1_em = NULL;
2480  EquivalenceMember *item2_em = NULL;
2481  ListCell *lc2;
2482 
2483  /* Never match to a volatile EC */
2484  if (ec->ec_has_volatile)
2485  continue;
2486  /* Note: it seems okay to match to "broken" eclasses here */
2487 
2488  foreach(lc2, ec->ec_members)
2489  {
2491  Var *var;
2492 
2493  if (em->em_is_child)
2494  continue; /* ignore children here */
2495 
2496  /* EM must be a Var, possibly with RelabelType */
2497  var = (Var *) em->em_expr;
2498  while (var && IsA(var, RelabelType))
2499  var = (Var *) ((RelabelType *) var)->arg;
2500  if (!(var && IsA(var, Var)))
2501  continue;
2502 
2503  /* Match? */
2504  if (var->varno == var1varno && var->varattno == var1attno)
2505  item1_em = em;
2506  else if (var->varno == var2varno && var->varattno == var2attno)
2507  item2_em = em;
2508 
2509  /* Have we found both PK and FK column in this EC? */
2510  if (item1_em && item2_em)
2511  {
2512  /*
2513  * Succeed if eqop matches EC's opfamilies. We could test
2514  * this before scanning the members, but it's probably cheaper
2515  * to test for member matches first.
2516  */
2517  if (opfamilies == NIL) /* compute if we didn't already */
2518  opfamilies = get_mergejoin_opfamilies(eqop);
2519  if (equal(opfamilies, ec->ec_opfamilies))
2520  {
2521  fkinfo->eclass[colno] = ec;
2522  fkinfo->fk_eclass_member[colno] = item2_em;
2523  return ec;
2524  }
2525  /* Otherwise, done with this EC, move on to the next */
2526  break;
2527  }
2528  }
2529  }
2530  return NULL;
2531 }
int16 AttrNumber
Definition: attnum.h:21
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:260
List * get_mergejoin_opfamilies(Oid opno)
Definition: lsyscache.c:365
while(p+4<=pend)
struct EquivalenceClass * eclass[INDEX_MAX_KEYS]
Definition: pathnodes.h:1245
struct EquivalenceMember * fk_eclass_member[INDEX_MAX_KEYS]
Definition: pathnodes.h:1247
AttrNumber varattno
Definition: primnodes.h:235
int varno
Definition: primnodes.h:230

References Assert(), bms_intersect(), bms_next_member(), ForeignKeyOptInfo::con_relid, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, PlannerInfo::ec_merging_done, EquivalenceClass::ec_opfamilies, ForeignKeyOptInfo::eclass, RelOptInfo::eclass_indexes, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, PlannerInfo::eq_classes, equal(), ForeignKeyOptInfo::fk_eclass_member, get_mergejoin_opfamilies(), i, IS_SIMPLE_REL, IsA, lfirst, list_nth(), NIL, ForeignKeyOptInfo::ref_relid, 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 3716 of file indxpath.c.

3719 {
3720  int indkey;
3721 
3722  /*
3723  * Ignore any RelabelType node above the operand. This is needed to be
3724  * able to apply indexscanning in binary-compatible-operator cases. Note:
3725  * we can assume there is at most one RelabelType node;
3726  * eval_const_expressions() will have simplified if more than one.
3727  */
3728  if (operand && IsA(operand, RelabelType))
3729  operand = (Node *) ((RelabelType *) operand)->arg;
3730 
3731  indkey = index->indexkeys[indexcol];
3732  if (indkey != 0)
3733  {
3734  /*
3735  * Simple index column; operand must be a matching Var.
3736  */
3737  if (operand && IsA(operand, Var) &&
3738  index->rel->relid == ((Var *) operand)->varno &&
3739  indkey == ((Var *) operand)->varattno &&
3740  ((Var *) operand)->varnullingrels == NULL)
3741  return true;
3742  }
3743  else
3744  {
3745  /*
3746  * Index expression; find the correct expression. (This search could
3747  * be avoided, at the cost of complicating all the callers of this
3748  * routine; doesn't seem worth it.)
3749  */
3750  ListCell *indexpr_item;
3751  int i;
3752  Node *indexkey;
3753 
3754  indexpr_item = list_head(index->indexprs);
3755  for (i = 0; i < indexcol; i++)
3756  {
3757  if (index->indexkeys[i] == 0)
3758  {
3759  if (indexpr_item == NULL)
3760  elog(ERROR, "wrong number of index expressions");
3761  indexpr_item = lnext(index->indexprs, indexpr_item);
3762  }
3763  }
3764  if (indexpr_item == NULL)
3765  elog(ERROR, "wrong number of index expressions");
3766  indexkey = (Node *) lfirst(indexpr_item);
3767 
3768  /*
3769  * Does it match the operand? Again, strip any relabeling.
3770  */
3771  if (indexkey && IsA(indexkey, RelabelType))
3772  indexkey = (Node *) ((RelabelType *) indexkey)->arg;
3773 
3774  if (equal(indexkey, operand))
3775  return true;
3776  }
3777 
3778  return false;
3779 }

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(), match_boolean_index_clause(), match_clause_to_indexcol(), match_clause_to_ordering_op(), match_funcclause_to_indexcol(), match_opclause_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 359 of file pathkeys.c.

360 {
361  int n = 0;
362  ListCell *key1,
363  *key2;
364 
365  /*
366  * See if we can avoiding looping through both lists. This optimization
367  * gains us several percent in planning time in a worst-case test.
368  */
369  if (keys1 == keys2)
370  {
371  *n_common = list_length(keys1);
372  return true;
373  }
374  else if (keys1 == NIL)
375  {
376  *n_common = 0;
377  return true;
378  }
379  else if (keys2 == NIL)
380  {
381  *n_common = 0;
382  return false;
383  }
384 
385  /*
386  * If both lists are non-empty, iterate through both to find out how many
387  * items are shared.
388  */
389  forboth(key1, keys1, key2, keys2)
390  {
391  PathKey *pathkey1 = (PathKey *) lfirst(key1);
392  PathKey *pathkey2 = (PathKey *) lfirst(key2);
393 
394  if (pathkey1 != pathkey2)
395  {
396  *n_common = n;
397  return false;
398  }
399  n++;
400  }
401 
402  /* If we ended with a null value, then we've processed the whole list. */
403  *n_common = n;
404  return (key1 == NULL);
405 }

References forboth, lfirst, list_length(), and NIL.

Referenced by add_paths_to_grouping_rel(), create_final_distinct_paths(), create_one_window_path(), create_ordered_paths(), create_partial_distinct_paths(), create_partial_grouping_paths(), create_window_paths(), gather_grouping_paths(), generate_useful_gather_paths(), and pathkeys_useful_for_ordering().

◆ process_equivalence()

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

Definition at line 118 of file equivclass.c.

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