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, bool below_outer_join)
 
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, Relids nullable_relids, 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_rel, RelOptInfo *child_rel)
 
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)
 
int group_keys_reorder_by_pathkeys (List *pathkeys, List **group_pathkeys, List **group_clauses)
 
Listget_useful_group_keys_orderings (PlannerInfo *root, double nrows, List *path_pathkeys, List *pathkeys, List *clauses)
 
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, Relids nullable_relids, 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)
 
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)
 
PathKeymake_canonical_pathkey (PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
 
void add_paths_to_append_rel (PlannerInfo *root, RelOptInfo *rel, List *live_childrels)
 

Variables

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

Typedef Documentation

◆ ec_matches_callback_type

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

Definition at line 118 of file paths.h.

◆ join_search_hook_type

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

Definition at line 46 of file paths.h.

◆ set_join_pathlist_hook_type

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

Definition at line 37 of file paths.h.

◆ set_rel_pathlist_hook_type

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

Definition at line 30 of file paths.h.

Enumeration Type Documentation

◆ PathKeysComparison

Enumerator
PATHKEYS_EQUAL 
PATHKEYS_BETTER1 
PATHKEYS_BETTER2 
PATHKEYS_DIFFERENT 

Definition at line 195 of file paths.h.

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

Function Documentation

◆ add_child_join_rel_equivalences()

void add_child_join_rel_equivalences ( PlannerInfo root,
int  nappinfos,
AppendRelInfo **  appinfos,
RelOptInfo parent_rel,
RelOptInfo child_rel 
)

Definition at line 2678 of file equivclass.c.

2682 {
2683  Relids top_parent_relids = child_joinrel->top_parent_relids;
2684  Relids child_relids = child_joinrel->relids;
2685  Bitmapset *matching_ecs;
2686  MemoryContext oldcontext;
2687  int i;
2688 
2689  Assert(IS_JOIN_REL(child_joinrel) && IS_JOIN_REL(parent_joinrel));
2690 
2691  /* We need consider only ECs that mention the parent joinrel */
2692  matching_ecs = get_eclass_indexes_for_relids(root, top_parent_relids);
2693 
2694  /*
2695  * If we're being called during GEQO join planning, we still have to
2696  * create any new EC members in the main planner context, to avoid having
2697  * a corrupt EC data structure after the GEQO context is reset. This is
2698  * problematic since we'll leak memory across repeated GEQO cycles. For
2699  * now, though, bloat is better than crash. If it becomes a real issue
2700  * we'll have to do something to avoid generating duplicate EC members.
2701  */
2702  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
2703 
2704  i = -1;
2705  while ((i = bms_next_member(matching_ecs, i)) >= 0)
2706  {
2707  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2708  int num_members;
2709 
2710  /*
2711  * If this EC contains a volatile expression, then generating child
2712  * EMs would be downright dangerous, so skip it. We rely on a
2713  * volatile EC having only one EM.
2714  */
2715  if (cur_ec->ec_has_volatile)
2716  continue;
2717 
2718  /* Sanity check on get_eclass_indexes_for_relids result */
2719  Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids));
2720 
2721  /*
2722  * We don't use foreach() here because there's no point in scanning
2723  * newly-added child members, so we can stop after the last
2724  * pre-existing EC member.
2725  */
2726  num_members = list_length(cur_ec->ec_members);
2727  for (int pos = 0; pos < num_members; pos++)
2728  {
2729  EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2730 
2731  if (cur_em->em_is_const)
2732  continue; /* ignore consts here */
2733 
2734  /*
2735  * We consider only original EC members here, not
2736  * already-transformed child members.
2737  */
2738  if (cur_em->em_is_child)
2739  continue; /* ignore children here */
2740 
2741  /*
2742  * We may ignore expressions that reference a single baserel,
2743  * because add_child_rel_equivalences should have handled them.
2744  */
2745  if (bms_membership(cur_em->em_relids) != BMS_MULTIPLE)
2746  continue;
2747 
2748  /* Does this member reference child's topmost parent rel? */
2749  if (bms_overlap(cur_em->em_relids, top_parent_relids))
2750  {
2751  /* Yes, generate transformed child version */
2752  Expr *child_expr;
2753  Relids new_relids;
2754  Relids new_nullable_relids;
2755 
2756  if (parent_joinrel->reloptkind == RELOPT_JOINREL)
2757  {
2758  /* Simple single-level transformation */
2759  child_expr = (Expr *)
2761  (Node *) cur_em->em_expr,
2762  nappinfos, appinfos);
2763  }
2764  else
2765  {
2766  /* Must do multi-level transformation */
2767  Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
2768  child_expr = (Expr *)
2770  (Node *) cur_em->em_expr,
2771  child_relids,
2772  top_parent_relids);
2773  }
2774 
2775  /*
2776  * Transform em_relids to match. Note we do *not* do
2777  * pull_varnos(child_expr) here, as for example the
2778  * transformation might have substituted a constant, but we
2779  * don't want the child member to be marked as constant.
2780  */
2781  new_relids = bms_difference(cur_em->em_relids,
2782  top_parent_relids);
2783  new_relids = bms_add_members(new_relids, child_relids);
2784 
2785  /*
2786  * For nullable_relids, we must selectively replace parent
2787  * nullable relids with child ones.
2788  */
2789  new_nullable_relids = cur_em->em_nullable_relids;
2790  if (bms_overlap(new_nullable_relids, top_parent_relids))
2791  new_nullable_relids =
2793  new_nullable_relids,
2794  child_relids,
2795  top_parent_relids);
2796 
2797  (void) add_eq_member(cur_ec, child_expr,
2798  new_relids, new_nullable_relids,
2799  true, cur_em->em_datatype);
2800  }
2801  }
2802  }
2803 
2804  MemoryContextSwitchTo(oldcontext);
2805 }
Relids adjust_child_relids_multilevel(PlannerInfo *root, Relids relids, Relids child_relids, Relids top_parent_relids)
Definition: appendinfo.c:562
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, Relids child_relids, Relids top_parent_relids)
Definition: appendinfo.c:488
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1045
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:291
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:795
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:674
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
@ BMS_MULTIPLE
Definition: bitmapset.h:70
static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, Relids nullable_relids, bool is_child, Oid datatype)
Definition: equivclass.c:545
static Bitmapset * get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids)
Definition: equivclass.c:3194
int i
Definition: isn.c:73
Assert(fmt[strlen(fmt) - 1] !='\n')
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
#define IS_JOIN_REL(rel)
Definition: pathnodes.h:660
@ RELOPT_JOINREL
Definition: pathnodes.h:643
@ RELOPT_OTHER_JOINREL
Definition: pathnodes.h:645
static int list_length(const List *l)
Definition: pg_list.h:149
static void * list_nth(const List *list, int n)
Definition: pg_list.h:278
Relids ec_relids
Definition: pathnodes.h:994
List * ec_members
Definition: pathnodes.h:991
bool ec_has_volatile
Definition: pathnodes.h:997
Relids em_nullable_relids
Definition: pathnodes.h:1041
Definition: nodes.h:574
MemoryContext planner_cxt
Definition: pathnodes.h:336
List * eq_classes
Definition: pathnodes.h:250

References add_eq_member(), adjust_appendrel_attrs(), adjust_appendrel_attrs_multilevel(), adjust_child_relids_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_nullable_relids, EquivalenceMember::em_relids, PlannerInfo::eq_classes, get_eclass_indexes_for_relids(), i, IS_JOIN_REL, list_length(), list_nth(), MemoryContextSwitchTo(), PlannerInfo::planner_cxt, 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 2550 of file equivclass.c.

2554 {
2555  Relids top_parent_relids = child_rel->top_parent_relids;
2556  Relids child_relids = child_rel->relids;
2557  int i;
2558 
2559  /*
2560  * EC merging should be complete already, so we can use the parent rel's
2561  * eclass_indexes to avoid searching all of root->eq_classes.
2562  */
2563  Assert(root->ec_merging_done);
2564  Assert(IS_SIMPLE_REL(parent_rel));
2565 
2566  i = -1;
2567  while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0)
2568  {
2569  EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2570  int num_members;
2571 
2572  /*
2573  * If this EC contains a volatile expression, then generating child
2574  * EMs would be downright dangerous, so skip it. We rely on a
2575  * volatile EC having only one EM.
2576  */
2577  if (cur_ec->ec_has_volatile)
2578  continue;
2579 
2580  /* Sanity check eclass_indexes only contain ECs for parent_rel */
2581  Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids));
2582 
2583  /*
2584  * We don't use foreach() here because there's no point in scanning
2585  * newly-added child members, so we can stop after the last
2586  * pre-existing EC member.
2587  */
2588  num_members = list_length(cur_ec->ec_members);
2589  for (int pos = 0; pos < num_members; pos++)
2590  {
2591  EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
2592 
2593  if (cur_em->em_is_const)
2594  continue; /* ignore consts here */
2595 
2596  /*
2597  * We consider only original EC members here, not
2598  * already-transformed child members. Otherwise, if some original
2599  * member expression references more than one appendrel, we'd get
2600  * an O(N^2) explosion of useless derived expressions for
2601  * combinations of children. (But add_child_join_rel_equivalences
2602  * may add targeted combinations for partitionwise-join purposes.)
2603  */
2604  if (cur_em->em_is_child)
2605  continue; /* ignore children here */
2606 
2607  /* Does this member reference child's topmost parent rel? */
2608  if (bms_overlap(cur_em->em_relids, top_parent_relids))
2609  {
2610  /* Yes, generate transformed child version */
2611  Expr *child_expr;
2612  Relids new_relids;
2613  Relids new_nullable_relids;
2614 
2615  if (parent_rel->reloptkind == RELOPT_BASEREL)
2616  {
2617  /* Simple single-level transformation */
2618  child_expr = (Expr *)
2620  (Node *) cur_em->em_expr,
2621  1, &appinfo);
2622  }
2623  else
2624  {
2625  /* Must do multi-level transformation */
2626  child_expr = (Expr *)
2628  (Node *) cur_em->em_expr,
2629  child_relids,
2630  top_parent_relids);
2631  }
2632 
2633  /*
2634  * Transform em_relids to match. Note we do *not* do
2635  * pull_varnos(child_expr) here, as for example the
2636  * transformation might have substituted a constant, but we
2637  * don't want the child member to be marked as constant.
2638  */
2639  new_relids = bms_difference(cur_em->em_relids,
2640  top_parent_relids);
2641  new_relids = bms_add_members(new_relids, child_relids);
2642 
2643  /*
2644  * And likewise for nullable_relids. Note this code assumes
2645  * parent and child relids are singletons.
2646  */
2647  new_nullable_relids = cur_em->em_nullable_relids;
2648  if (bms_overlap(new_nullable_relids, top_parent_relids))
2649  {
2650  new_nullable_relids = bms_difference(new_nullable_relids,
2651  top_parent_relids);
2652  new_nullable_relids = bms_add_members(new_nullable_relids,
2653  child_relids);
2654  }
2655 
2656  (void) add_eq_member(cur_ec, child_expr,
2657  new_relids, new_nullable_relids,
2658  true, cur_em->em_datatype);
2659 
2660  /* Record this EC index for the child rel */
2661  child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
2662  }
2663  }
2664  }
2665 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:738
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:655
@ RELOPT_BASEREL
Definition: pathnodes.h:642
bool ec_merging_done
Definition: pathnodes.h:252
Relids relids
Definition: pathnodes.h:682
Relids top_parent_relids
Definition: pathnodes.h:757
RelOptKind reloptkind
Definition: pathnodes.h:679
Bitmapset * eclass_indexes
Definition: pathnodes.h:724

References add_eq_member(), adjust_appendrel_attrs(), adjust_appendrel_attrs_multilevel(), Assert(), bms_add_member(), bms_add_members(), bms_difference(), bms_is_subset(), bms_next_member(), bms_overlap(), 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_nullable_relids, 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 1286 of file allpaths.c.

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

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, fls(), 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, Path::param_info, RelOptInfo::partial_pathlist, AppendPath::path, PATH_REQ_OUTER, Path::pathkeys, PATHKEYS_EQUAL, RelOptInfo::pathlist, 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.
238  */
239  foreach(lc, root->join_info_list)
240  {
241  SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);
242 
243  /*
244  * SJ is relevant to this join if we have some part of its RHS
245  * (possibly not all of it), and haven't yet joined to its LHS. (This
246  * test is pretty simplistic, but should be sufficient considering the
247  * join has already been proven legal.) If the SJ is relevant, it
248  * presents constraints for joining to anything not in its RHS.
249  */
250  if (bms_overlap(joinrelids, sjinfo2->min_righthand) &&
251  !bms_overlap(joinrelids, sjinfo2->min_lefthand))
254  sjinfo2->min_righthand));
255 
256  /* full joins constrain both sides symmetrically */
257  if (sjinfo2->jointype == JOIN_FULL &&
258  bms_overlap(joinrelids, sjinfo2->min_lefthand) &&
259  !bms_overlap(joinrelids, sjinfo2->min_righthand))
262  sjinfo2->min_lefthand));
263  }
264 
265  /*
266  * However, when a LATERAL subquery is involved, there will simply not be
267  * any paths for the joinrel that aren't parameterized by whatever the
268  * subquery is parameterized by, unless its parameterization is resolved
269  * within the joinrel. So we might as well allow additional dependencies
270  * on whatever residual lateral dependencies the joinrel will have.
271  */
273  joinrel->lateral_relids);
274 
275  /*
276  * 1. Consider mergejoin paths where both relations must be explicitly
277  * sorted. Skip this if we can't mergejoin.
278  */
279  if (mergejoin_allowed)
280  sort_inner_and_outer(root, joinrel, outerrel, innerrel,
281  jointype, &extra);
282 
283  /*
284  * 2. Consider paths where the outer relation need not be explicitly
285  * sorted. This includes both nestloops and mergejoins where the outer
286  * path is already ordered. Again, skip this if we can't mergejoin.
287  * (That's okay because we know that nestloop can't handle right/full
288  * joins at all, so it wouldn't work in the prohibited cases either.)
289  */
290  if (mergejoin_allowed)
291  match_unsorted_outer(root, joinrel, outerrel, innerrel,
292  jointype, &extra);
293 
294 #ifdef NOT_USED
295 
296  /*
297  * 3. Consider paths where the inner relation need not be explicitly
298  * sorted. This includes mergejoins only (nestloops were already built in
299  * match_unsorted_outer).
300  *
301  * Diked out as redundant 2/13/2000 -- tgl. There isn't any really
302  * significant difference between the inner and outer side of a mergejoin,
303  * so match_unsorted_inner creates no paths that aren't equivalent to
304  * those made by match_unsorted_outer when add_paths_to_joinrel() is
305  * invoked with the two rels given in the other order.
306  */
307  if (mergejoin_allowed)
308  match_unsorted_inner(root, joinrel, outerrel, innerrel,
309  jointype, &extra);
310 #endif
311 
312  /*
313  * 4. Consider paths where both outer and inner relations must be hashed
314  * before being joined. As above, disregard enable_hashjoin for full
315  * joins, because there may be no other alternative.
316  */
317  if (enable_hashjoin || jointype == JOIN_FULL)
318  hash_inner_and_outer(root, joinrel, outerrel, innerrel,
319  jointype, &extra);
320 
321  /*
322  * 5. If inner and outer relations are foreign tables (or joins) belonging
323  * to the same server and assigned to the same user to check access
324  * permissions as, give the FDW a chance to push down joins.
325  */
326  if (joinrel->fdwroutine &&
328  joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
329  outerrel, innerrel,
330  jointype, &extra);
331 
332  /*
333  * 6. Finally, give extensions a chance to manipulate the path list.
334  */
336  set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
337  jointype, &extra);
338 }
bool innerrel_is_unique(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
Definition: analyzejoins.c:964
Bitmapset * bms_join(Bitmapset *a, Bitmapset *b)
Definition: bitmapset.c:951
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:5031
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:2222
static void sort_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1143
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:1967
static void match_unsorted_outer(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
Definition: joinpath.c:1593
@ JOIN_SEMI
Definition: nodes.h:763
@ JOIN_FULL
Definition: nodes.h:751
@ JOIN_INNER
Definition: nodes.h:749
@ JOIN_UNIQUE_OUTER
Definition: nodes.h:770
@ JOIN_UNIQUE_INNER
Definition: nodes.h:771
@ JOIN_ANTI
Definition: nodes.h:764
GetForeignJoinPaths_function GetForeignJoinPaths
Definition: fdwapi.h:223
List * mergeclause_list
Definition: pathnodes.h:2550
Relids param_source_rels
Definition: pathnodes.h:2554
SemiAntiJoinFactors semifactors
Definition: pathnodes.h:2553
SpecialJoinInfo * sjinfo
Definition: pathnodes.h:2552
List * join_info_list
Definition: pathnodes.h:267
Relids all_baserels
Definition: pathnodes.h:210
struct FdwRoutine * fdwroutine
Definition: pathnodes.h:737
Relids lateral_relids
Definition: pathnodes.h:707
Relids min_righthand
Definition: pathnodes.h:2273
JoinType jointype
Definition: pathnodes.h:2276
Relids min_lefthand
Definition: pathnodes.h:2272

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, RelOptInfo::fdwroutine, FdwRoutine::GetForeignJoinPaths, 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().

◆ build_expression_pathkey()

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

Definition at line 1305 of file pathkeys.c.

1311 {
1312  List *pathkeys;
1313  Oid opfamily,
1314  opcintype;
1315  int16 strategy;
1316  PathKey *cpathkey;
1317 
1318  /* Find the operator in pg_amop --- failure shouldn't happen */
1319  if (!get_ordering_op_properties(opno,
1320  &opfamily, &opcintype, &strategy))
1321  elog(ERROR, "operator %u is not a valid ordering operator",
1322  opno);
1323 
1324  cpathkey = make_pathkey_from_sortinfo(root,
1325  expr,
1326  nullable_relids,
1327  opfamily,
1328  opcintype,
1329  exprCollation((Node *) expr),
1330  (strategy == BTGreaterStrategyNumber),
1331  (strategy == BTGreaterStrategyNumber),
1332  0,
1333  rel,
1334  create_it);
1335 
1336  if (cpathkey)
1337  pathkeys = list_make1(cpathkey);
1338  else
1339  pathkeys = NIL;
1340 
1341  return pathkeys;
1342 }
signed short int16
Definition: c.h:428
#define ERROR
Definition: elog.h:33
#define elog(elevel,...)
Definition: elog.h:218
bool get_ordering_op_properties(Oid opno, Oid *opfamily, Oid *opcintype, int16 *strategy)
Definition: lsyscache.c:205
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:788
static PathKey * make_pathkey_from_sortinfo(PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid opfamily, Oid opcintype, Oid collation, bool reverse_sort, bool nulls_first, Index sortref, Relids rel, bool create_it)
Definition: pathkeys.c:182
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 1046 of file pathkeys.c.

1049 {
1050  List *retval = NIL;
1051  ListCell *lc;
1052  int i;
1053 
1054  if (index->sortopfamily == NULL)
1055  return NIL; /* non-orderable index */
1056 
1057  i = 0;
1058  foreach(lc, index->indextlist)
1059  {
1060  TargetEntry *indextle = (TargetEntry *) lfirst(lc);
1061  Expr *indexkey;
1062  bool reverse_sort;
1063  bool nulls_first;
1064  PathKey *cpathkey;
1065 
1066  /*
1067  * INCLUDE columns are stored in index unordered, so they don't
1068  * support ordered index scan.
1069  */
1070  if (i >= index->nkeycolumns)
1071  break;
1072 
1073  /* We assume we don't need to make a copy of the tlist item */
1074  indexkey = indextle->expr;
1075 
1076  if (ScanDirectionIsBackward(scandir))
1077  {
1078  reverse_sort = !index->reverse_sort[i];
1079  nulls_first = !index->nulls_first[i];
1080  }
1081  else
1082  {
1083  reverse_sort = index->reverse_sort[i];
1084  nulls_first = index->nulls_first[i];
1085  }
1086 
1087  /*
1088  * OK, try to make a canonical pathkey for this sort key. Note we're
1089  * underneath any outer joins, so nullable_relids should be NULL.
1090  */
1091  cpathkey = make_pathkey_from_sortinfo(root,
1092  indexkey,
1093  NULL,
1094  index->sortopfamily[i],
1095  index->opcintype[i],
1096  index->indexcollations[i],
1097  reverse_sort,
1098  nulls_first,
1099  0,
1100  index->rel->relids,
1101  false);
1102 
1103  if (cpathkey)
1104  {
1105  /*
1106  * We found the sort key in an EquivalenceClass, so it's relevant
1107  * for this query. Add it to list, unless it's redundant.
1108  */
1109  if (!pathkey_is_redundant(cpathkey, retval))
1110  retval = lappend(retval, cpathkey);
1111  }
1112  else
1113  {
1114  /*
1115  * Boolean index keys might be redundant even if they do not
1116  * appear in an EquivalenceClass, because of our special treatment
1117  * of boolean equality conditions --- see the comment for
1118  * indexcol_is_bool_constant_for_query(). If that applies, we can
1119  * continue to examine lower-order index columns. Otherwise, the
1120  * sort key is not an interesting sort order for this query, so we
1121  * should stop considering index columns; any lower-order sort
1122  * keys won't be useful either.
1123  */
1125  break;
1126  }
1127 
1128  i++;
1129  }
1130 
1131  return retval;
1132 }
bool indexcol_is_bool_constant_for_query(PlannerInfo *root, IndexOptInfo *index, int indexcol)
Definition: indxpath.c:3669
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:140
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
Expr * expr
Definition: primnodes.h:1716
Definition: type.h:90

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

1609 {
1610  if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
1611  return NIL;
1612 
1613  /*
1614  * This used to be quite a complex bit of code, but now that all pathkey
1615  * sublists start out life canonicalized, we don't have to do a darn thing
1616  * here!
1617  *
1618  * We do, however, need to truncate the pathkeys list, since it may
1619  * contain pathkeys that were useful for forming this joinrel but are
1620  * uninteresting to higher levels.
1621  */
1622  return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1623 }
@ JOIN_RIGHT
Definition: nodes.h:752
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:2441

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

1224 {
1225  List *retval = NIL;
1226  PartitionScheme partscheme = partrel->part_scheme;
1227  int i;
1228 
1229  Assert(partscheme != NULL);
1230  Assert(partitions_are_ordered(partrel->boundinfo, partrel->live_parts));
1231  /* For now, we can only cope with baserels */
1232  Assert(IS_SIMPLE_REL(partrel));
1233 
1234  for (i = 0; i < partscheme->partnatts; i++)
1235  {
1236  PathKey *cpathkey;
1237  Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]);
1238 
1239  /*
1240  * Try to make a canonical pathkey for this partkey.
1241  *
1242  * We're considering a baserel scan, so nullable_relids should be
1243  * NULL. Also, we assume the PartitionDesc lists any NULL partition
1244  * last, so we treat the scan like a NULLS LAST index: we have
1245  * nulls_first for backwards scan only.
1246  */
1247  cpathkey = make_pathkey_from_sortinfo(root,
1248  keyCol,
1249  NULL,
1250  partscheme->partopfamily[i],
1251  partscheme->partopcintype[i],
1252  partscheme->partcollation[i],
1253  ScanDirectionIsBackward(scandir),
1254  ScanDirectionIsBackward(scandir),
1255  0,
1256  partrel->relids,
1257  false);
1258 
1259 
1260  if (cpathkey)
1261  {
1262  /*
1263  * We found the sort key in an EquivalenceClass, so it's relevant
1264  * for this query. Add it to list, unless it's redundant.
1265  */
1266  if (!pathkey_is_redundant(cpathkey, retval))
1267  retval = lappend(retval, cpathkey);
1268  }
1269  else
1270  {
1271  /*
1272  * Boolean partition keys might be redundant even if they do not
1273  * appear in an EquivalenceClass, because of our special treatment
1274  * of boolean equality conditions --- see the comment for
1275  * partkey_is_bool_constant_for_query(). If that applies, we can
1276  * continue to examine lower-order partition keys. Otherwise, the
1277  * sort key is not an interesting sort order for this query, so we
1278  * should stop considering partition columns; any lower-order sort
1279  * keys won't be useful either.
1280  */
1281  if (!partkey_is_bool_constant_for_query(partrel, i))
1282  {
1283  *partialkeys = true;
1284  return retval;
1285  }
1286  }
1287  }
1288 
1289  *partialkeys = false;
1290  return retval;
1291 }
bool partitions_are_ordered(PartitionBoundInfo boundinfo, Bitmapset *live_parts)
Definition: partbounds.c:2863
static bool partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:1152
List ** partexprs
Definition: pathnodes.h:775
struct PartitionBoundInfoData * boundinfo
Definition: pathnodes.h:765
PartitionScheme part_scheme
Definition: pathnodes.h:761
Bitmapset * live_parts
Definition: pathnodes.h:771

References Assert(), RelOptInfo::boundinfo, i, IS_SIMPLE_REL, lappend(), linitial, RelOptInfo::live_parts, make_pathkey_from_sortinfo(), NIL, RelOptInfo::part_scheme, PartitionSchemeData::partcollation, RelOptInfo::partexprs, 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 500 of file equivclass.c.

501 {
502  Oid expr_type = exprType((Node *) expr);
503 
504  /*
505  * For a polymorphic-input-type opclass, just keep the same exposed type.
506  * RECORD opclasses work like polymorphic-type ones for this purpose.
507  */
508  if (IsPolymorphicType(req_type) || req_type == RECORDOID)
509  req_type = expr_type;
510 
511  /*
512  * No work if the expression exposes the right type/collation already.
513  */
514  if (expr_type != req_type ||
515  exprCollation((Node *) expr) != req_collation)
516  {
517  /*
518  * If we have to change the type of the expression, set typmod to -1,
519  * since the new type may not have the same typmod interpretation.
520  * When we only have to change collation, preserve the exposed typmod.
521  */
522  int32 req_typmod;
523 
524  if (expr_type != req_type)
525  req_typmod = -1;
526  else
527  req_typmod = exprTypmod((Node *) expr);
528 
529  /*
530  * Use applyRelabelType so that we preserve const-flatness. This is
531  * important since eval_const_expressions has already been applied.
532  */
533  expr = (Expr *) applyRelabelType((Node *) expr,
534  req_type, req_typmod, req_collation,
535  COERCE_IMPLICIT_CAST, -1, false);
536  }
537 
538  return expr;
539 }
signed int int32
Definition: c.h:429
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:41
int32 exprTypmod(const Node *expr)
Definition: nodeFuncs.c:286
Node * applyRelabelType(Node *arg, Oid rtype, int32 rtypmod, Oid rcollid, CoercionForm rformat, int rlocation, bool overwrite_ok)
Definition: nodeFuncs.c:609
@ COERCE_IMPLICIT_CAST
Definition: primnodes.h:494

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

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

References PlannerInfo::all_baserels, 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 290 of file pathkeys.c.

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

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

4096 {
4097  int parallel_workers = 0;
4098 
4099  /*
4100  * If the user has set the parallel_workers reloption, use that; otherwise
4101  * select a default number of workers.
4102  */
4103  if (rel->rel_parallel_workers != -1)
4104  parallel_workers = rel->rel_parallel_workers;
4105  else
4106  {
4107  /*
4108  * If the number of pages being scanned is insufficient to justify a
4109  * parallel scan, just return zero ... unless it's an inheritance
4110  * child. In that case, we want to generate a parallel path here
4111  * anyway. It might not be worthwhile just for this relation, but
4112  * when combined with all of its inheritance siblings it may well pay
4113  * off.
4114  */
4115  if (rel->reloptkind == RELOPT_BASEREL &&
4116  ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
4117  (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
4118  return 0;
4119 
4120  if (heap_pages >= 0)
4121  {
4122  int heap_parallel_threshold;
4123  int heap_parallel_workers = 1;
4124 
4125  /*
4126  * Select the number of workers based on the log of the size of
4127  * the relation. This probably needs to be a good deal more
4128  * sophisticated, but we need something here for now. Note that
4129  * the upper limit of the min_parallel_table_scan_size GUC is
4130  * chosen to prevent overflow here.
4131  */
4132  heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
4133  while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
4134  {
4135  heap_parallel_workers++;
4136  heap_parallel_threshold *= 3;
4137  if (heap_parallel_threshold > INT_MAX / 3)
4138  break; /* avoid overflow */
4139  }
4140 
4141  parallel_workers = heap_parallel_workers;
4142  }
4143 
4144  if (index_pages >= 0)
4145  {
4146  int index_parallel_workers = 1;
4147  int index_parallel_threshold;
4148 
4149  /* same calculation as for heap_pages above */
4150  index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
4151  while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
4152  {
4153  index_parallel_workers++;
4154  index_parallel_threshold *= 3;
4155  if (index_parallel_threshold > INT_MAX / 3)
4156  break; /* avoid overflow */
4157  }
4158 
4159  if (parallel_workers > 0)
4160  parallel_workers = Min(parallel_workers, index_parallel_workers);
4161  else
4162  parallel_workers = index_parallel_workers;
4163  }
4164  }
4165 
4166  /* In no case use more than caller supplied maximum number of workers */
4167  parallel_workers = Min(parallel_workers, max_workers);
4168 
4169  return parallel_workers;
4170 }
int min_parallel_index_scan_size
Definition: allpaths.c:66
int min_parallel_table_scan_size
Definition: allpaths.c:65
uint32 BlockNumber
Definition: block.h:31
int rel_parallel_workers
Definition: pathnodes.h:728

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

1364 {
1365  List *retval = NIL;
1366  int retvallen = 0;
1367  int outer_query_keys = list_length(root->query_pathkeys);
1368  ListCell *i;
1369 
1370  foreach(i, subquery_pathkeys)
1371  {
1372  PathKey *sub_pathkey = (PathKey *) lfirst(i);
1373  EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
1374  PathKey *best_pathkey = NULL;
1375 
1376  if (sub_eclass->ec_has_volatile)
1377  {
1378  /*
1379  * If the sub_pathkey's EquivalenceClass is volatile, then it must
1380  * have come from an ORDER BY clause, and we have to match it to
1381  * that same targetlist entry.
1382  */
1383  TargetEntry *tle;
1384  Var *outer_var;
1385 
1386  if (sub_eclass->ec_sortref == 0) /* can't happen */
1387  elog(ERROR, "volatile EquivalenceClass has no sortref");
1388  tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
1389  Assert(tle);
1390  /* Is TLE actually available to the outer query? */
1391  outer_var = find_var_for_subquery_tle(rel, tle);
1392  if (outer_var)
1393  {
1394  /* We can represent this sub_pathkey */
1395  EquivalenceMember *sub_member;
1396  EquivalenceClass *outer_ec;
1397 
1398  Assert(list_length(sub_eclass->ec_members) == 1);
1399  sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
1400 
1401  /*
1402  * Note: it might look funny to be setting sortref = 0 for a
1403  * reference to a volatile sub_eclass. However, the
1404  * expression is *not* volatile in the outer query: it's just
1405  * a Var referencing whatever the subquery emitted. (IOW, the
1406  * outer query isn't going to re-execute the volatile
1407  * expression itself.) So this is okay. Likewise, it's
1408  * correct to pass nullable_relids = NULL, because we're
1409  * underneath any outer joins appearing in the outer query.
1410  */
1411  outer_ec =
1413  (Expr *) outer_var,
1414  NULL,
1415  sub_eclass->ec_opfamilies,
1416  sub_member->em_datatype,
1417  sub_eclass->ec_collation,
1418  0,
1419  rel->relids,
1420  false);
1421 
1422  /*
1423  * If we don't find a matching EC, sub-pathkey isn't
1424  * interesting to the outer query
1425  */
1426  if (outer_ec)
1427  best_pathkey =
1429  outer_ec,
1430  sub_pathkey->pk_opfamily,
1431  sub_pathkey->pk_strategy,
1432  sub_pathkey->pk_nulls_first);
1433  }
1434  }
1435  else
1436  {
1437  /*
1438  * Otherwise, the sub_pathkey's EquivalenceClass could contain
1439  * multiple elements (representing knowledge that multiple items
1440  * are effectively equal). Each element might match none, one, or
1441  * more of the output columns that are visible to the outer query.
1442  * This means we may have multiple possible representations of the
1443  * sub_pathkey in the context of the outer query. Ideally we
1444  * would generate them all and put them all into an EC of the
1445  * outer query, thereby propagating equality knowledge up to the
1446  * outer query. Right now we cannot do so, because the outer
1447  * query's EquivalenceClasses are already frozen when this is
1448  * called. Instead we prefer the one that has the highest "score"
1449  * (number of EC peers, plus one if it matches the outer
1450  * query_pathkeys). This is the most likely to be useful in the
1451  * outer query.
1452  */
1453  int best_score = -1;
1454  ListCell *j;
1455 
1456  foreach(j, sub_eclass->ec_members)
1457  {
1458  EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
1459  Expr *sub_expr = sub_member->em_expr;
1460  Oid sub_expr_type = sub_member->em_datatype;
1461  Oid sub_expr_coll = sub_eclass->ec_collation;
1462  ListCell *k;
1463 
1464  if (sub_member->em_is_child)
1465  continue; /* ignore children here */
1466 
1467  foreach(k, subquery_tlist)
1468  {
1469  TargetEntry *tle = (TargetEntry *) lfirst(k);
1470  Var *outer_var;
1471  Expr *tle_expr;
1472  EquivalenceClass *outer_ec;
1473  PathKey *outer_pk;
1474  int score;
1475 
1476  /* Is TLE actually available to the outer query? */
1477  outer_var = find_var_for_subquery_tle(rel, tle);
1478  if (!outer_var)
1479  continue;
1480 
1481  /*
1482  * The targetlist entry is considered to match if it
1483  * matches after sort-key canonicalization. That is
1484  * needed since the sub_expr has been through the same
1485  * process.
1486  */
1487  tle_expr = canonicalize_ec_expression(tle->expr,
1488  sub_expr_type,
1489  sub_expr_coll);
1490  if (!equal(tle_expr, sub_expr))
1491  continue;
1492 
1493  /* See if we have a matching EC for the TLE */
1494  outer_ec = get_eclass_for_sort_expr(root,
1495  (Expr *) outer_var,
1496  NULL,
1497  sub_eclass->ec_opfamilies,
1498  sub_expr_type,
1499  sub_expr_coll,
1500  0,
1501  rel->relids,
1502  false);
1503 
1504  /*
1505  * If we don't find a matching EC, this sub-pathkey isn't
1506  * interesting to the outer query
1507  */
1508  if (!outer_ec)
1509  continue;
1510 
1511  outer_pk = make_canonical_pathkey(root,
1512  outer_ec,
1513  sub_pathkey->pk_opfamily,
1514  sub_pathkey->pk_strategy,
1515  sub_pathkey->pk_nulls_first);
1516  /* score = # of equivalence peers */
1517  score = list_length(outer_ec->ec_members) - 1;
1518  /* +1 if it matches the proper query_pathkeys item */
1519  if (retvallen < outer_query_keys &&
1520  list_nth(root->query_pathkeys, retvallen) == outer_pk)
1521  score++;
1522  if (score > best_score)
1523  {
1524  best_pathkey = outer_pk;
1525  best_score = score;
1526  }
1527  }
1528  }
1529  }
1530 
1531  /*
1532  * If we couldn't find a representation of this sub_pathkey, we're
1533  * done (we can't use the ones to its right, either).
1534  */
1535  if (!best_pathkey)
1536  break;
1537 
1538  /*
1539  * Eliminate redundant ordering info; could happen if outer query
1540  * equivalences subquery keys...
1541  */
1542  if (!pathkey_is_redundant(best_pathkey, retval))
1543  {
1544  retval = lappend(retval, best_pathkey);
1545  retvallen++;
1546  }
1547  }
1548 
1549  return retval;
1550 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3564
EquivalenceClass * get_eclass_for_sort_expr(PlannerInfo *root, Expr *expr, Relids nullable_relids, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
Definition: equivclass.c:621
Expr * canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation)
Definition: equivclass.c:500
int j
Definition: isn.c:74
static Var * find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
Definition: pathkeys.c:1562
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:59
List * ec_opfamilies
Definition: pathnodes.h:989
bool pk_nulls_first
Definition: pathnodes.h:1071
int pk_strategy
Definition: pathnodes.h:1070
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1068
Oid pk_opfamily
Definition: pathnodes.h:1069
List * query_pathkeys
Definition: pathnodes.h:295
Definition: primnodes.h:196
TargetEntry * get_sortgroupref_tle(Index sortref, List *targetList)
Definition: tlist.c:334

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_eclass, 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  ListCell *lc;
365 
366  /* Identify each distinct parameterization seen in bitjoinpaths */
367  all_path_outers = NIL;
368  foreach(lc, bitjoinpaths)
369  {
370  Path *path = (Path *) lfirst(lc);
371  Relids required_outer = PATH_REQ_OUTER(path);
372 
373  if (!bms_equal_any(required_outer, all_path_outers))
374  all_path_outers = lappend(all_path_outers, required_outer);
375  }
376 
377  /* Now, for each distinct parameterization set ... */
378  foreach(lc, all_path_outers)
379  {
380  Relids max_outers = (Relids) lfirst(lc);
381  List *this_path_set;
382  Path *bitmapqual;
383  Relids required_outer;
384  double loop_count;
385  BitmapHeapPath *bpath;
386  ListCell *lcp;
387 
388  /* Identify all the bitmap join paths needing no more than that */
389  this_path_set = NIL;
390  foreach(lcp, bitjoinpaths)
391  {
392  Path *path = (Path *) lfirst(lcp);
393 
394  if (bms_is_subset(PATH_REQ_OUTER(path), max_outers))
395  this_path_set = lappend(this_path_set, path);
396  }
397 
398  /*
399  * Add in restriction bitmap paths, since they can be used
400  * together with any join paths.
401  */
402  this_path_set = list_concat(this_path_set, bitindexpaths);
403 
404  /* Select best AND combination for this parameterization */
405  bitmapqual = choose_bitmap_and(root, rel, this_path_set);
406 
407  /* And push that path into the mix */
408  required_outer = PATH_REQ_OUTER(bitmapqual);
409  loop_count = get_loop_count(root, rel->relid, required_outer);
410  bpath = create_bitmap_heap_path(root, rel, bitmapqual,
411  required_outer, loop_count, 0);
412  add_path(rel, (Path *) bpath);
413  }
414  }
415 }
void create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual)
Definition: allpaths.c:4058
#define MemSet(start, val, len)
Definition: c.h:1008
static Path * choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
Definition: indxpath.c:1362
static void match_join_clauses_to_index(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauseset, List **joinorclauses)
Definition: indxpath.c:2058
static void match_eclass_clauses_to_index(PlannerInfo *root, IndexOptInfo *index, IndexClauseSet *clauseset)
Definition: indxpath.c:2088
static bool bms_equal_any(Relids relids, List *relids_list)
Definition: indxpath.c:704
static void get_index_paths(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *clauses, List **bitindexpaths)
Definition: indxpath.c:733
static double get_loop_count(PlannerInfo *root, Index cur_relid, Relids outer_relids)
Definition: indxpath.c:1904
static void consider_index_join_clauses(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index, IndexClauseSet *rclauseset, IndexClauseSet *jclauseset, IndexClauseSet *eclauseset, List **bitindexpaths)
Definition: indxpath.c:433
static void match_restriction_clauses_to_index(PlannerInfo *root, IndexOptInfo *index, IndexClauseSet *clauseset)
Definition: indxpath.c:2043
static List * generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel, List *clauses, List *other_clauses)
Definition: indxpath.c:1255
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_equal_any(), 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_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 4058 of file allpaths.c.

4060 {
4061  int parallel_workers;
4062  double pages_fetched;
4063 
4064  /* Compute heap pages for bitmap heap scan */
4065  pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
4066  NULL, NULL);
4067 
4068  parallel_workers = compute_parallel_worker(rel, pages_fetched, -1,
4070 
4071  if (parallel_workers <= 0)
4072  return;
4073 
4074  add_partial_path(rel, (Path *) create_bitmap_heap_path(root, rel,
4075  bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
4076 }
int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
Definition: allpaths.c:4094
double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, int loop_count, Cost *cost, double *tuple)
Definition: costsize.c:6442

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 459 of file tidpath.c.

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

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

3076 {
3077  Relids relids;
3078  ListCell *lc;
3079 
3080  Assert(!eclass->ec_merged);
3081 
3082  /*
3083  * Won't generate joinclauses if const or single-member (the latter test
3084  * covers the volatile case too)
3085  */
3086  if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
3087  return false;
3088 
3089  /*
3090  * Note we don't test ec_broken; if we did, we'd need a separate code path
3091  * to look through ec_sources. Checking the members anyway is OK as a
3092  * possibly-overoptimistic heuristic.
3093  */
3094 
3095  /* If specified rel is a child, we must consider the topmost parent rel */
3096  if (IS_OTHER_REL(rel))
3097  {
3099  relids = rel->top_parent_relids;
3100  }
3101  else
3102  relids = rel->relids;
3103 
3104  /* If rel already includes all members of eclass, no point in searching */
3105  if (bms_is_subset(eclass->ec_relids, relids))
3106  return false;
3107 
3108  /* To join, we need a member not in the given rel */
3109  foreach(lc, eclass->ec_members)
3110  {
3111  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
3112 
3113  if (cur_em->em_is_child)
3114  continue; /* ignore children here */
3115 
3116  if (!bms_overlap(cur_em->em_relids, relids))
3117  return true;
3118  }
3119 
3120  return false;
3121 }
#define IS_OTHER_REL(rel)
Definition: pathnodes.h:670
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 2368 of file equivclass.c.

2369 {
2370  ListCell *lc1;
2371 
2372  foreach(lc1, root->eq_classes)
2373  {
2374  EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
2375  bool item1member = false;
2376  bool item2member = false;
2377  ListCell *lc2;
2378 
2379  /* Never match to a volatile EC */
2380  if (ec->ec_has_volatile)
2381  continue;
2382 
2383  foreach(lc2, ec->ec_members)
2384  {
2386 
2387  if (em->em_is_child)
2388  continue; /* ignore children here */
2389  if (equal(item1, em->em_expr))
2390  item1member = true;
2391  else if (equal(item2, em->em_expr))
2392  item2member = true;
2393  /* Exit as soon as equality is proven */
2394  if (item1member && item2member)
2395  return true;
2396  }
2397  }
2398  return false;
2399 }

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

867 {
868  ListCell *lc;
869 
870  foreach(lc, ec->ec_members)
871  {
873  List *exprvars;
874  ListCell *lc2;
875 
876  /*
877  * We shouldn't be trying to sort by an equivalence class that
878  * contains a constant, so no need to consider such cases any further.
879  */
880  if (em->em_is_const)
881  continue;
882 
883  /*
884  * Ignore child members unless they belong to the requested rel.
885  */
886  if (em->em_is_child &&
887  !bms_is_subset(em->em_relids, relids))
888  continue;
889 
890  /*
891  * Match if all Vars and quasi-Vars are available in "exprs".
892  */
893  exprvars = pull_var_clause((Node *) em->em_expr,
897  foreach(lc2, exprvars)
898  {
899  if (!is_exprlist_member(lfirst(lc2), exprs))
900  break;
901  }
902  list_free(exprvars);
903  if (lc2)
904  continue; /* we hit a non-available Var */
905 
906  /*
907  * If requested, reject expressions that are not parallel-safe. We
908  * check this last because it's a rather expensive test.
909  */
910  if (require_parallel_safe &&
911  !is_parallel_safe(root, (Node *) em->em_expr))
912  continue;
913 
914  return em; /* found usable expression */
915  }
916 
917  return NULL;
918 }
bool is_parallel_safe(PlannerInfo *root, Node *node)
Definition: clauses.c:683
static bool is_exprlist_member(Expr *node, List *exprs)
Definition: equivclass.c:928
void list_free(List *list)
Definition: list.c:1505
#define PVC_INCLUDE_WINDOWFUNCS
Definition: optimizer.h:190
#define PVC_INCLUDE_PLACEHOLDERS
Definition: optimizer.h:192
#define PVC_INCLUDE_AGGREGATES
Definition: optimizer.h:188
List * pull_var_clause(Node *node, int flags)
Definition: var.c:604

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

2512 {
2513  ListCell *lc;
2514 
2515  Assert(ec->ec_has_const);
2516  Assert(!em->em_is_const);
2517  foreach(lc, ec->ec_derives)
2518  {
2519  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2520 
2521  /*
2522  * generate_base_implied_equalities_const will have put non-const
2523  * members on the left side of derived clauses.
2524  */
2525  if (rinfo->left_em == em)
2526  return rinfo;
2527  }
2528  return NULL;
2529 }
List * ec_derives
Definition: pathnodes.h:993
EquivalenceMember * left_em
Definition: pathnodes.h:2128

References Assert(), EquivalenceClass::ec_derives, EquivalenceClass::ec_has_const, EquivalenceMember::em_is_const, RestrictInfo::left_em, 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 797 of file equivclass.c.

800 {
801  ListCell *lc;
802 
803  /* We ignore binary-compatible relabeling on both ends */
804  while (expr && IsA(expr, RelabelType))
805  expr = ((RelabelType *) expr)->arg;
806 
807  foreach(lc, ec->ec_members)
808  {
810  Expr *emexpr;
811 
812  /*
813  * We shouldn't be trying to sort by an equivalence class that
814  * contains a constant, so no need to consider such cases any further.
815  */
816  if (em->em_is_const)
817  continue;
818 
819  /*
820  * Ignore child members unless they belong to the requested rel.
821  */
822  if (em->em_is_child &&
823  !bms_is_subset(em->em_relids, relids))
824  continue;
825 
826  /*
827  * Match if same expression (after stripping relabel).
828  */
829  emexpr = em->em_expr;
830  while (emexpr && IsA(emexpr, RelabelType))
831  emexpr = ((RelabelType *) emexpr)->arg;
832 
833  if (equal(emexpr, expr))
834  return em;
835  }
836 
837  return NULL;
838 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:624
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 1785 of file pathkeys.c.

1788 {
1789  List *mergeclauses = NIL;
1790  ListCell *i;
1791 
1792  /* make sure we have eclasses cached in the clauses */
1793  foreach(i, restrictinfos)
1794  {
1795  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1796 
1797  update_mergeclause_eclasses(root, rinfo);
1798  }
1799 
1800  foreach(i, pathkeys)
1801  {
1802  PathKey *pathkey = (PathKey *) lfirst(i);
1803  EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1804  List *matched_restrictinfos = NIL;
1805  ListCell *j;
1806 
1807  /*----------
1808  * A mergejoin clause matches a pathkey if it has the same EC.
1809  * If there are multiple matching clauses, take them all. In plain
1810  * inner-join scenarios we expect only one match, because
1811  * equivalence-class processing will have removed any redundant
1812  * mergeclauses. However, in outer-join scenarios there might be
1813  * multiple matches. An example is
1814  *
1815  * select * from a full join b
1816  * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1817  *
1818  * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1819  * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1820  * we *must* do so or we will be unable to form a valid plan.
1821  *
1822  * We expect that the given pathkeys list is canonical, which means
1823  * no two members have the same EC, so it's not possible for this
1824  * code to enter the same mergeclause into the result list twice.
1825  *
1826  * It's possible that multiple matching clauses might have different
1827  * ECs on the other side, in which case the order we put them into our
1828  * result makes a difference in the pathkeys required for the inner
1829  * input rel. However this routine hasn't got any info about which
1830  * order would be best, so we don't worry about that.
1831  *
1832  * It's also possible that the selected mergejoin clauses produce
1833  * a noncanonical ordering of pathkeys for the inner side, ie, we
1834  * might select clauses that reference b.v1, b.v2, b.v1 in that
1835  * order. This is not harmful in itself, though it suggests that
1836  * the clauses are partially redundant. Since the alternative is
1837  * to omit mergejoin clauses and thereby possibly fail to generate a
1838  * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1839  * has to delete duplicates when it constructs the inner pathkeys
1840  * list, and we also have to deal with such cases specially in
1841  * create_mergejoin_plan().
1842  *----------
1843  */
1844  foreach(j, restrictinfos)
1845  {
1846  RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1847  EquivalenceClass *clause_ec;
1848 
1849  clause_ec = rinfo->outer_is_left ?
1850  rinfo->left_ec : rinfo->right_ec;
1851  if (clause_ec == pathkey_ec)
1852  matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1853  }
1854 
1855  /*
1856  * If we didn't find a mergeclause, we're done --- any additional
1857  * sort-key positions in the pathkeys are useless. (But we can still
1858  * mergejoin if we found at least one mergeclause.)
1859  */
1860  if (matched_restrictinfos == NIL)
1861  break;
1862 
1863  /*
1864  * If we did find usable mergeclause(s) for this sort-key position,
1865  * add them to result list.
1866  */
1867  mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1868  }
1869 
1870  return mergeclauses;
1871 }
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1751
EquivalenceClass * left_ec
Definition: pathnodes.h:2126
bool outer_is_left
Definition: pathnodes.h:2133
EquivalenceClass * right_ec
Definition: pathnodes.h:2127

References i, j, lappend(), RestrictInfo::left_ec, lfirst, list_concat(), NIL, RestrictInfo::outer_is_left, PathKey::pk_eclass, RestrictInfo::right_ec, 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 1070 of file equivclass.c.

1071 {
1072  int ec_index;
1073  ListCell *lc;
1074 
1075  /*
1076  * At this point, we're done absorbing knowledge of equivalences in the
1077  * query, so no further EC merging should happen, and ECs remaining in the
1078  * eq_classes list can be considered canonical. (But note that it's still
1079  * possible for new single-member ECs to be added through
1080  * get_eclass_for_sort_expr().)
1081  */
1082  root->ec_merging_done = true;
1083 
1084  ec_index = 0;
1085  foreach(lc, root->eq_classes)
1086  {
1088  bool can_generate_joinclause = false;
1089  int i;
1090 
1091  Assert(ec->ec_merged == NULL); /* else shouldn't be in list */
1092  Assert(!ec->ec_broken); /* not yet anyway... */
1093 
1094  /*
1095  * Generate implied equalities that are restriction clauses.
1096  * Single-member ECs won't generate any deductions, either here or at
1097  * the join level.
1098  */
1099  if (list_length(ec->ec_members) > 1)
1100  {
1101  if (ec->ec_has_const)
1103  else
1105 
1106  /* Recover if we failed to generate required derived clauses */
1107  if (ec->ec_broken)
1109 
1110  /* Detect whether this EC might generate join clauses */
1111  can_generate_joinclause =
1113  }
1114 
1115  /*
1116  * Mark the base rels cited in each eclass (which should all exist by
1117  * now) with the eq_classes indexes of all eclasses mentioning them.
1118  * This will let us avoid searching in subsequent lookups. While
1119  * we're at it, we can mark base rels that have pending eclass joins;
1120  * this is a cheap version of has_relevant_eclass_joinclause().
1121  */
1122  i = -1;
1123  while ((i = bms_next_member(ec->ec_relids, i)) > 0)
1124  {
1125  RelOptInfo *rel = root->simple_rel_array[i];
1126 
1127  Assert(rel->reloptkind == RELOPT_BASEREL);
1128 
1130  ec_index);
1131 
1132  if (can_generate_joinclause)
1133  rel->has_eclass_joins = true;
1134  }
1135 
1136  ec_index++;
1137  }
1138 }
static void generate_base_implied_equalities_broken(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1346
static void generate_base_implied_equalities_no_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1239
static void generate_base_implied_equalities_const(PlannerInfo *root, EquivalenceClass *ec)
Definition: equivclass.c:1144
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:1003
struct RelOptInfo ** simple_rel_array
Definition: pathnodes.h:186

References Assert(), bms_add_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(), RELOPT_BASEREL, RelOptInfo::reloptkind, and PlannerInfo::simple_rel_array.

Referenced by query_planner().

◆ generate_gather_paths()

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

Definition at line 2953 of file allpaths.c.

2954 {
2955  Path *cheapest_partial_path;
2956  Path *simple_gather_path;
2957  ListCell *lc;
2958  double rows;
2959  double *rowsp = NULL;
2960 
2961  /* If there are no partial paths, there's nothing to do here. */
2962  if (rel->partial_pathlist == NIL)
2963  return;
2964 
2965  /* Should we override the rel's rowcount estimate? */
2966  if (override_rows)
2967  rowsp = &rows;
2968 
2969  /*
2970  * The output of Gather is always unsorted, so there's only one partial
2971  * path of interest: the cheapest one. That will be the one at the front
2972  * of partial_pathlist because of the way add_partial_path works.
2973  */
2974  cheapest_partial_path = linitial(rel->partial_pathlist);
2975  rows =
2976  cheapest_partial_path->rows * cheapest_partial_path->parallel_workers;
2977  simple_gather_path = (Path *)
2978  create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
2979  NULL, rowsp);
2980  add_path(rel, simple_gather_path);
2981 
2982  /*
2983  * For each useful ordering, we can consider an order-preserving Gather
2984  * Merge.
2985  */
2986  foreach(lc, rel->partial_pathlist)
2987  {
2988  Path *subpath = (Path *) lfirst(lc);
2989  GatherMergePath *path;
2990 
2991  if (subpath->pathkeys == NIL)
2992  continue;
2993 
2994  rows = subpath->rows * subpath->parallel_workers;
2995  path = create_gather_merge_path(root, rel, subpath, rel->reltarget,
2996  subpath->pathkeys, NULL, rowsp);
2997  add_path(rel, &path->path);
2998  }
2999 }
GatherMergePath * create_gather_merge_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, List *pathkeys, Relids required_outer, double *rows)
Definition: pathnode.c:1861
GatherPath * create_gather_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, Relids required_outer, double *rows)
Definition: pathnode.c:1952
struct PathTarget * reltarget
Definition: pathnodes.h:693

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

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

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

1407 {
1408  List *result = NIL;
1409  Relids inner_relids = inner_rel->relids;
1410  Relids nominal_inner_relids;
1411  Relids nominal_join_relids;
1412  Bitmapset *matching_ecs;
1413  int i;
1414 
1415  /* If inner rel is a child, extra setup work is needed */
1416  if (IS_OTHER_REL(inner_rel))
1417  {
1418  Assert(!bms_is_empty(inner_rel->top_parent_relids));
1419 
1420  /* Fetch relid set for the topmost parent rel */
1421  nominal_inner_relids = inner_rel->top_parent_relids;
1422  /* ECs will be marked with the parent's relid, not the child's */
1423  nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
1424  }
1425  else
1426  {
1427  nominal_inner_relids = inner_relids;
1428  nominal_join_relids = join_relids;
1429  }
1430 
1431  /*
1432  * Get all eclasses that mention both inner and outer sides of the join
1433  */
1434  matching_ecs = get_common_eclass_indexes(root, nominal_inner_relids,
1435  outer_relids);
1436 
1437  i = -1;
1438  while ((i = bms_next_member(matching_ecs, i)) >= 0)
1439  {
1441  List *sublist = NIL;
1442 
1443  /* ECs containing consts do not need any further enforcement */
1444  if (ec->ec_has_const)
1445  continue;
1446 
1447  /* Single-member ECs won't generate any deductions */
1448  if (list_length(ec->ec_members) <= 1)
1449  continue;
1450 
1451  /* Sanity check that this eclass overlaps the join */
1452  Assert(bms_overlap(ec->ec_relids, nominal_join_relids));
1453 
1454  if (!ec->ec_broken)
1456  ec,
1457  join_relids,
1458  outer_relids,
1459  inner_relids);
1460 
1461  /* Recover if we failed to generate required derived clauses */
1462  if (ec->ec_broken)
1464  ec,
1465  nominal_join_relids,
1466  outer_relids,
1467  nominal_inner_relids,
1468  inner_rel);
1469 
1470  result = list_concat(result, sublist);
1471  }
1472 
1473  return result;
1474 }
static List * generate_join_implied_equalities_normal(PlannerInfo *root, EquivalenceClass *ec, Relids join_relids, Relids outer_relids, Relids inner_relids)
Definition: equivclass.c:1552
static Bitmapset * get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2)
Definition: equivclass.c:3218
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:1728

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

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

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

4183 {
4184  List *live_children = NIL;
4185  int cnt_parts;
4186  int num_parts;
4187  RelOptInfo **part_rels;
4188 
4189  /* Handle only join relations here. */
4190  if (!IS_JOIN_REL(rel))
4191  return;
4192 
4193  /* We've nothing to do if the relation is not partitioned. */
4194  if (!IS_PARTITIONED_REL(rel))
4195  return;
4196 
4197  /* The relation should have consider_partitionwise_join set. */
4199 
4200  /* Guard against stack overflow due to overly deep partition hierarchy. */
4202 
4203  num_parts = rel->nparts;
4204  part_rels = rel->part_rels;
4205 
4206  /* Collect non-dummy child-joins. */
4207  for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
4208  {
4209  RelOptInfo *child_rel = part_rels[cnt_parts];
4210 
4211  /* If it's been pruned entirely, it's certainly dummy. */
4212  if (child_rel == NULL)
4213  continue;
4214 
4215  /* Add partitionwise join paths for partitioned child-joins. */
4216  generate_partitionwise_join_paths(root, child_rel);
4217 
4218  set_cheapest(child_rel);
4219 
4220  /* Dummy children will not be scanned, so ignore those. */
4221  if (IS_DUMMY_REL(child_rel))
4222  continue;
4223 
4224 #ifdef OPTIMIZER_DEBUG
4225  debug_print_rel(root, child_rel);
4226 #endif
4227 
4228  live_children = lappend(live_children, child_rel);
4229  }
4230 
4231  /* If all child-joins are dummy, parent join is also dummy. */
4232  if (!live_children)
4233  {
4234  mark_dummy_rel(rel);
4235  return;
4236  }
4237 
4238  /* Build additional paths for this rel from child-join paths. */
4239  add_paths_to_append_rel(root, rel, live_children);
4240  list_free(live_children);
4241 }
void generate_partitionwise_join_paths(PlannerInfo *root, RelOptInfo *rel)
Definition: allpaths.c:4182
void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels)
Definition: allpaths.c:1286
void mark_dummy_rel(RelOptInfo *rel)
Definition: joinrels.c:1261
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:244
#define IS_DUMMY_REL(r)
Definition: pathnodes.h:1478
#define IS_PARTITIONED_REL(rel)
Definition: pathnodes.h:787
void check_stack_depth(void)
Definition: postgres.c:3500
int nparts
Definition: pathnodes.h:762
struct RelOptInfo ** part_rels
Definition: pathnodes.h:769
bool consider_partitionwise_join
Definition: pathnodes.h:755

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::part_rels, 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 3091 of file allpaths.c.

3092 {
3093  ListCell *lc;
3094  double rows;
3095  double *rowsp = NULL;
3096  List *useful_pathkeys_list = NIL;
3097  Path *cheapest_partial_path = NULL;
3098 
3099  /* If there are no partial paths, there's nothing to do here. */
3100  if (rel->partial_pathlist == NIL)
3101  return;
3102 
3103  /* Should we override the rel's rowcount estimate? */
3104  if (override_rows)
3105  rowsp = &rows;
3106 
3107  /* generate the regular gather (merge) paths */
3108  generate_gather_paths(root, rel, override_rows);
3109 
3110  /* consider incremental sort for interesting orderings */
3111  useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel, true);
3112 
3113  /* used for explicit (full) sort paths */
3114  cheapest_partial_path = linitial(rel->partial_pathlist);
3115 
3116  /*
3117  * Consider sorted paths for each interesting ordering. We generate both
3118  * incremental and full sort.
3119  */
3120  foreach(lc, useful_pathkeys_list)
3121  {
3122  List *useful_pathkeys = lfirst(lc);
3123  ListCell *lc2;
3124  bool is_sorted;
3125  int presorted_keys;
3126 
3127  foreach(lc2, rel->partial_pathlist)
3128  {
3129  Path *subpath = (Path *) lfirst(lc2);
3130  GatherMergePath *path;
3131 
3132  is_sorted = pathkeys_count_contained_in(useful_pathkeys,
3133  subpath->pathkeys,
3134  &presorted_keys);
3135 
3136  /*
3137  * We don't need to consider the case where a subpath is already
3138  * fully sorted because generate_gather_paths already creates a
3139  * gather merge path for every subpath that has pathkeys present.
3140  *
3141  * But since the subpath is already sorted, we know we don't need
3142  * to consider adding a sort (full or incremental) on top of it,
3143  * so we can continue here.
3144  */
3145  if (is_sorted)
3146  continue;
3147 
3148  /*
3149  * Consider regular sort for the cheapest partial path (for each
3150  * useful pathkeys). We know the path is not sorted, because we'd
3151  * not get here otherwise.
3152  *
3153  * This is not redundant with the gather paths created in
3154  * generate_gather_paths, because that doesn't generate ordered
3155  * output. Here we add an explicit sort to match the useful
3156  * ordering.
3157  */
3158  if (cheapest_partial_path == subpath)
3159  {
3160  Path *tmp;
3161 
3162  tmp = (Path *) create_sort_path(root,
3163  rel,
3164  subpath,
3165  useful_pathkeys,
3166  -1.0);
3167 
3168  rows = tmp->rows * tmp->parallel_workers;
3169 
3170  path = create_gather_merge_path(root, rel,
3171  tmp,
3172  rel->reltarget,
3173  tmp->pathkeys,
3174  NULL,
3175  rowsp);
3176 
3177  add_path(rel, &path->path);
3178 
3179  /* Fall through */
3180  }
3181 
3182  /*
3183  * Consider incremental sort, but only when the subpath is already
3184  * partially sorted on a pathkey prefix.
3185  */
3186  if (enable_incremental_sort && presorted_keys > 0)
3187  {
3188  Path *tmp;
3189 
3190  /*
3191  * We should have already excluded pathkeys of length 1
3192  * because then presorted_keys > 0 would imply is_sorted was
3193  * true.
3194  */
3195  Assert(list_length(useful_pathkeys) != 1);
3196 
3197  tmp = (Path *) create_incremental_sort_path(root,
3198  rel,
3199  subpath,
3200  useful_pathkeys,
3201  presorted_keys,
3202  -1);
3203 
3204  path = create_gather_merge_path(root, rel,
3205  tmp,
3206  rel->reltarget,
3207  tmp->pathkeys,
3208  NULL,
3209  rowsp);
3210 
3211  add_path(rel, &path->path);
3212  }
3213  }
3214  }
3215 }
void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
Definition: allpaths.c:2953
static List * get_useful_pathkeys_for_relation(PlannerInfo *root, RelOptInfo *rel, bool require_parallel_safe)
Definition: allpaths.c:3023
bool enable_incremental_sort
Definition: costsize.c:141
bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
Definition: pathkeys.c:866
SortPath * create_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, double limit_tuples)
Definition: pathnode.c:2942
IncrementalSortPath * create_incremental_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, int presorted_keys, double limit_tuples)
Definition: pathnode.c:2893

References add_path(), Assert(), create_gather_merge_path(), create_incremental_sort_path(), create_sort_path(), enable_incremental_sort, generate_gather_paths(), get_useful_pathkeys_for_relation(), lfirst, linitial, list_length(), NIL, Path::parallel_workers, RelOptInfo::partial_pathlist, GatherMergePath::path, Path::pathkeys, pathkeys_count_contained_in(), RelOptInfo::reltarget, Path::rows, 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 972 of file pathkeys.c.

976 {
977  Path *matched_path = NULL;
978  ListCell *l;
979 
980  foreach(l, paths)
981  {
982  Path *path = (Path *) lfirst(l);
983 
984  /*
985  * Since cost comparison is a lot cheaper than pathkey comparison, do
986  * that first. (XXX is that still true?)
987  */
988  if (matched_path != NULL &&
989  compare_fractional_path_costs(matched_path, path, fraction) <= 0)
990  continue;
991 
992  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
993  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
994  matched_path = path;
995  }
996  return matched_path;
997 }
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:329
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 1005 of file pathkeys.c.

1006 {
1007  ListCell *l;
1008 
1009  foreach(l, paths)
1010  {
1011  Path *innerpath = (Path *) lfirst(l);
1012 
1013  if (innerpath->parallel_safe &&
1014  bms_is_empty(PATH_REQ_OUTER(innerpath)))
1015  return innerpath;
1016  }
1017 
1018  return NULL;
1019 }
bool parallel_safe
Definition: pathnodes.h:1200

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

931 {
932  Path *matched_path = NULL;
933  ListCell *l;
934 
935  foreach(l, paths)
936  {
937  Path *path = (Path *) lfirst(l);
938 
939  /*
940  * Since cost comparison is a lot cheaper than pathkey comparison, do
941  * that first. (XXX is that still true?)
942  */
943  if (matched_path != NULL &&
944  compare_path_costs(matched_path, path, cost_criterion) <= 0)
945  continue;
946 
947  if (require_parallel_safe && !path->parallel_safe)
948  continue;
949 
950  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
951  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
952  matched_path = path;
953  }
954  return matched_path;
955 }
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,
Relids  nullable_relids,
List opfamilies,
Oid  opcintype,
Oid  collation,
Index  sortref,
Relids  rel,
bool  create_it 
)

Definition at line 621 of file equivclass.c.

630 {
631  Relids expr_relids;
632  EquivalenceClass *newec;
633  EquivalenceMember *newem;
634  ListCell *lc1;
635  MemoryContext oldcontext;
636 
637  /*
638  * Ensure the expression exposes the correct type and collation.
639  */
640  expr = canonicalize_ec_expression(expr, opcintype, collation);
641 
642  /*
643  * Scan through the existing EquivalenceClasses for a match
644  */
645  foreach(lc1, root->eq_classes)
646  {
647  EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
648  ListCell *lc2;
649 
650  /*
651  * Never match to a volatile EC, except when we are looking at another
652  * reference to the same volatile SortGroupClause.
653  */
654  if (cur_ec->ec_has_volatile &&
655  (sortref == 0 || sortref != cur_ec->ec_sortref))
656  continue;
657 
658  if (collation != cur_ec->ec_collation)
659  continue;
660  if (!equal(opfamilies, cur_ec->ec_opfamilies))
661  continue;
662 
663  foreach(lc2, cur_ec->ec_members)
664  {
665  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
666 
667  /*
668  * Ignore child members unless they match the request.
669  */
670  if (cur_em->em_is_child &&
671  !bms_equal(cur_em->em_relids, rel))
672  continue;
673 
674  /*
675  * If below an outer join, don't match constants: they're not as
676  * constant as they look.
677  */
678  if (cur_ec->ec_below_outer_join &&
679  cur_em->em_is_const)
680  continue;
681 
682  if (opcintype == cur_em->em_datatype &&
683  equal(expr, cur_em->em_expr))
684  {
685  /*
686  * Match!
687  *
688  * Copy the sortref if it wasn't set yet. That may happen if
689  * the ec was constructed from WHERE clause, i.e. it doesn't
690  * have a target reference at all.
691  */
692  if (cur_ec->ec_sortref == 0 && sortref > 0)
693  cur_ec->ec_sortref = sortref;
694  return cur_ec;
695  }
696  }
697  }
698 
699  /* No match; does caller want a NULL result? */
700  if (!create_it)
701  return NULL;
702 
703  /*
704  * OK, build a new single-member EC
705  *
706  * Here, we must be sure that we construct the EC in the right context.
707  */
708  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
709 
710  newec = makeNode(EquivalenceClass);
711  newec->ec_opfamilies = list_copy(opfamilies);
712  newec->ec_collation = collation;
713  newec->ec_members = NIL;
714  newec->ec_sources = NIL;
715  newec->ec_derives = NIL;
716  newec->ec_relids = NULL;
717  newec->ec_has_const = false;
719  newec->ec_below_outer_join = false;
720  newec->ec_broken = false;
721  newec->ec_sortref = sortref;
722  newec->ec_min_security = UINT_MAX;
723  newec->ec_max_security = 0;
724  newec->ec_merged = NULL;
725 
726  if (newec->ec_has_volatile && sortref == 0) /* should not happen */
727  elog(ERROR, "volatile EquivalenceClass has no sortref");
728 
729  /*
730  * Get the precise set of nullable relids appearing in the expression.
731  */
732  expr_relids = pull_varnos(root, (Node *) expr);
733  nullable_relids = bms_intersect(nullable_relids, expr_relids);
734 
735  newem = add_eq_member(newec, copyObject(expr), expr_relids,
736  nullable_relids, false, opcintype);
737 
738  /*
739  * add_eq_member doesn't check for volatile functions, set-returning
740  * functions, aggregates, or window functions, but such could appear in
741  * sort expressions; so we have to check whether its const-marking was
742  * correct.
743  */
744  if (newec->ec_has_const)
745  {
746  if (newec->ec_has_volatile ||
747  expression_returns_set((Node *) expr) ||
748  contain_agg_clause((Node *) expr) ||
749  contain_window_function((Node *) expr))
750  {
751  newec->ec_has_const = false;
752  newem->em_is_const = false;
753  }
754  }
755 
756  root->eq_classes = lappend(root->eq_classes, newec);
757 
758  /*
759  * If EC merging is already complete, we have to mop up by adding the new
760  * EC to the eclass_indexes of the relation(s) mentioned in it.
761  */
762  if (root->ec_merging_done)
763  {
764  int ec_index = list_length(root->eq_classes) - 1;
765  int i = -1;
766 
767  while ((i = bms_next_member(newec->ec_relids, i)) > 0)
768  {
769  RelOptInfo *rel = root->simple_rel_array[i];
770 
771  Assert(rel->reloptkind == RELOPT_BASEREL ||
772  rel->reloptkind == RELOPT_DEADREL);
773 
775  ec_index);
776  }
777  }
778 
779  MemoryContextSwitchTo(oldcontext);
780 
781  return newec;
782 }
Bitmapset * bms_intersect(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:259
bool contain_agg_clause(Node *clause)
Definition: clauses.c:180
bool contain_window_function(Node *clause)
Definition: clauses.c:217
bool contain_volatile_functions(Node *clause)
Definition: clauses.c:496
bool expression_returns_set(Node *clause)
Definition: nodeFuncs.c:736
#define copyObject(obj)
Definition: nodes.h:689
#define makeNode(_type_)
Definition: nodes.h:621
@ RELOPT_DEADREL
Definition: pathnodes.h:648
Index ec_min_security
Definition: pathnodes.h:1001
bool ec_below_outer_join
Definition: pathnodes.h:998
List * ec_sources
Definition: pathnodes.h:992
Index ec_max_security
Definition: pathnodes.h:1002
Relids pull_varnos(PlannerInfo *root, Node *node)
Definition: var.c:100

References add_eq_member(), Assert(), bms_add_member(), bms_equal(), bms_intersect(), bms_next_member(), canonicalize_ec_expression(), contain_agg_clause(), contain_volatile_functions(), contain_window_function(), copyObject, EquivalenceClass::ec_below_outer_join, 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_relids, PlannerInfo::eq_classes, equal(), ERROR, expression_returns_set(), i, lappend(), lfirst, list_copy(), list_length(), makeNode, MemoryContextSwitchTo(), NIL, PlannerInfo::planner_cxt, pull_varnos(), RELOPT_BASEREL, RELOPT_DEADREL, RelOptInfo::reloptkind, and PlannerInfo::simple_rel_array.

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

◆ get_useful_group_keys_orderings()

List* get_useful_group_keys_orderings ( PlannerInfo root,
double  nrows,
List path_pathkeys,
List pathkeys,
List clauses 
)

Definition at line 745 of file pathkeys.c.

748 {
749  Query *parse = root->parse;
750  List *infos = NIL;
751  PathKeyInfo *info;
752  int n_preordered = 0;
753 
754  List *pathkeys = group_pathkeys;
755  List *clauses = group_clauses;
756 
757  /* always return at least the original pathkeys/clauses */
758  info = makeNode(PathKeyInfo);
759  info->pathkeys = pathkeys;
760  info->clauses = clauses;
761 
762  infos = lappend(infos, info);
763 
764  /*
765  * Should we try generating alternative orderings of the group keys? If
766  * not, we produce only the order specified in the query, i.e. the
767  * optimization is effectively disabled.
768  */
770  return infos;
771 
772  /* for grouping sets we can't do any reordering */
773  if (parse->groupingSets)
774  return infos;
775 
776  /*
777  * Try reordering pathkeys to minimize the sort cost, ignoring both the
778  * target ordering (ORDER BY) and ordering of the input path.
779  */
780  if (get_cheapest_group_keys_order(root, nrows, &pathkeys, &clauses,
781  n_preordered))
782  {
783  info = makeNode(PathKeyInfo);
784  info->pathkeys = pathkeys;
785  info->clauses = clauses;
786 
787  infos = lappend(infos, info);
788  }
789 
790  /*
791  * If the path is sorted in some way, try reordering the group keys to
792  * match as much of the ordering as possible - we get this sort for free
793  * (mostly).
794  *
795  * We must not do this when there are no grouping sets, because those use
796  * more complex logic to decide the ordering.
797  *
798  * XXX Isn't this somewhat redundant with presorted_keys? Actually, it's
799  * more a complement, because it allows benefiting from incremental sort
800  * as much as possible.
801  *
802  * XXX This does nothing if (n_preordered == 0). We shouldn't create the
803  * info in this case.
804  */
805  if (path_pathkeys)
806  {
807  n_preordered = group_keys_reorder_by_pathkeys(path_pathkeys,
808  &pathkeys,
809  &clauses);
810 
811  /* reorder the tail to minimize sort cost */
812  get_cheapest_group_keys_order(root, nrows, &pathkeys, &clauses,
813  n_preordered);
814 
815  /*
816  * reorder the tail to minimize sort cost
817  *
818  * XXX Ignore the return value - there may be nothing to reorder, in
819  * which case get_cheapest_group_keys_order returns false. But we
820  * still want to keep the keys reordered to path_pathkeys.
821  */
822  info = makeNode(PathKeyInfo);
823  info->pathkeys = pathkeys;
824  info->clauses = clauses;
825 
826  infos = lappend(infos, info);
827  }
828 
829  /*
830  * Try reordering pathkeys to minimize the sort cost (this time consider
831  * the ORDER BY clause, but only if set debug_group_by_match_order_by).
832  */
833  if (root->sort_pathkeys)
834  {
835  n_preordered = group_keys_reorder_by_pathkeys(root->sort_pathkeys,
836  &pathkeys,
837  &clauses);
838 
839  /*
840  * reorder the tail to minimize sort cost
841  *
842  * XXX Ignore the return value - there may be nothing to reorder, in
843  * which case get_cheapest_group_keys_order returns false. But we
844  * still want to keep the keys reordered to sort_pathkeys.
845  */
846  get_cheapest_group_keys_order(root, nrows, &pathkeys, &clauses,
847  n_preordered);
848 
849  /* keep the group keys reordered to match ordering of input path */
850  info = makeNode(PathKeyInfo);
851  info->pathkeys = pathkeys;
852  info->clauses = clauses;
853 
854  infos = lappend(infos, info);
855  }
856 
857  return infos;
858 }
static bool get_cheapest_group_keys_order(PlannerInfo *root, double nrows, List **group_pathkeys, List **group_clauses, int n_preordered)
Definition: pathkeys.c:584
bool enable_group_by_reordering
Definition: pathkeys.c:35
int group_keys_reorder_by_pathkeys(List *pathkeys, List **group_pathkeys, List **group_clauses)
Definition: pathkeys.c:352
static struct subre * parse(struct vars *, int, int, struct state *, struct state *)
Definition: regcomp.c:673
List * pathkeys
Definition: pathnodes.h:1080
List * clauses
Definition: pathnodes.h:1081
List * sort_pathkeys
Definition: pathnodes.h:300
Query * parse
Definition: pathnodes.h:162

References PathKeyInfo::clauses, enable_group_by_reordering, get_cheapest_group_keys_order(), group_keys_reorder_by_pathkeys(), lappend(), makeNode, NIL, parse(), PlannerInfo::parse, PathKeyInfo::pathkeys, and PlannerInfo::sort_pathkeys.

Referenced by add_paths_to_grouping_rel(), and create_partial_grouping_paths().

◆ group_keys_reorder_by_pathkeys()

int group_keys_reorder_by_pathkeys ( List pathkeys,
List **  group_pathkeys,
List **  group_clauses 
)

Definition at line 352 of file pathkeys.c.

354 {
355  List *new_group_pathkeys = NIL,
356  *new_group_clauses = NIL;
357  ListCell *lc;
358  int n;
359 
360  if (pathkeys == NIL || *group_pathkeys == NIL)
361  return 0;
362 
363  /*
364  * Walk the pathkeys (determining ordering of the input path) and see if
365  * there's a matching GROUP BY key. If we find one, we append it to the
366  * list, and do the same for the clauses.
367  *
368  * Once we find the first pathkey without a matching GROUP BY key, the
369  * rest of the pathkeys are useless and can't be used to evaluate the
370  * grouping, so we abort the loop and ignore the remaining pathkeys.
371  *
372  * XXX Pathkeys are built in a way to allow simply comparing pointers.
373  */
374  foreach(lc, pathkeys)
375  {
376  PathKey *pathkey = (PathKey *) lfirst(lc);
377  SortGroupClause *sgc;
378 
379  /* abort on first mismatch */
380  if (!list_member_ptr(*group_pathkeys, pathkey))
381  break;
382 
383  new_group_pathkeys = lappend(new_group_pathkeys, pathkey);
384 
386  *group_clauses);
387 
388  new_group_clauses = lappend(new_group_clauses, sgc);
389  }
390 
391  /* remember the number of pathkeys with a matching GROUP BY key */
392  n = list_length(new_group_pathkeys);
393 
394  /* append the remaining group pathkeys (will be treated as not sorted) */
395  *group_pathkeys = list_concat_unique_ptr(new_group_pathkeys,
396  *group_pathkeys);
397  *group_clauses = list_concat_unique_ptr(new_group_clauses,
398  *group_clauses);
399 
400  return n;
401 }
bool list_member_ptr(const List *list, const void *datum)
Definition: list.c:661
List * list_concat_unique_ptr(List *list1, const List *list2)
Definition: list.c:1386
SortGroupClause * get_sortgroupref_clause(Index sortref, List *clauses)
Definition: tlist.c:411

References EquivalenceClass::ec_sortref, get_sortgroupref_clause(), lappend(), lfirst, list_concat_unique_ptr(), list_length(), list_member_ptr(), NIL, and PathKey::pk_eclass.

Referenced by get_useful_group_keys_orderings().

◆ has_relevant_eclass_joinclause()

bool has_relevant_eclass_joinclause ( PlannerInfo root,
RelOptInfo rel1 
)

Definition at line 3029 of file equivclass.c.

3030 {
3031  Bitmapset *matched_ecs;
3032  int i;
3033 
3034  /* Examine only eclasses mentioning rel1 */
3035  matched_ecs = get_eclass_indexes_for_relids(root, rel1->relids);
3036 
3037  i = -1;
3038  while ((i = bms_next_member(matched_ecs, i)) >= 0)
3039  {
3041  i);
3042 
3043  /*
3044  * Won't generate joinclauses if single-member (this test covers the
3045  * volatile case too)
3046  */
3047  if (list_length(ec->ec_members) <= 1)
3048  continue;
3049 
3050  /*
3051  * Per the comment in have_relevant_eclass_joinclause, it's sufficient
3052  * to find an EC that mentions both this rel and some other rel.
3053  */
3054  if (!bms_is_subset(ec->ec_relids, rel1->relids))
3055  return true;
3056  }
3057 
3058  return false;
3059 }

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

2485 {
2486  if (rel->joininfo != NIL || rel->has_eclass_joins)
2487  return true; /* might be able to use pathkeys for merging */
2488  if (root->group_pathkeys != NIL)
2489  return true; /* might be able to use pathkeys for grouping */
2490  if (root->query_pathkeys != NIL)
2491  return true; /* might be able to use them for ordering */
2492  return false; /* definitely useless */
2493 }
List * group_pathkeys
Definition: pathnodes.h:297

References PlannerInfo::group_pathkeys, 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 1184 of file joinrels.c.

1186 {
1187  ListCell *lc;
1188 
1189  foreach(lc, root->placeholder_list)
1190  {
1191  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
1192 
1193  if (!bms_is_subset(phinfo->ph_eval_at, inner_params))
1194  continue; /* ignore, could not be a nestloop param */
1195  if (!bms_overlap(phinfo->ph_eval_at, outer_relids))
1196  continue; /* ignore, not relevant to this join */
1197  if (bms_is_subset(phinfo->ph_eval_at, outer_relids))
1198  continue; /* safe, it can be eval'd within outerrel */
1199  /* Otherwise, it's potentially unsafe, so reject the join */
1200  return true;
1201  }
1202 
1203  /* OK to perform the join */
1204  return false;
1205 }
Relids ph_eval_at
Definition: pathnodes.h:2433
List * placeholder_list
Definition: pathnodes.h:291

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

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

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

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

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

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

References lfirst, match_boolean_index_clause(), and RestrictInfo::pseudoconstant.

Referenced by build_index_pathkeys().

◆ initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1702 of file pathkeys.c.

1703 {
1704  Expr *clause = restrictinfo->clause;
1705  Oid lefttype,
1706  righttype;
1707 
1708  /* Should be a mergeclause ... */
1709  Assert(restrictinfo->mergeopfamilies != NIL);
1710  /* ... with links not yet set */
1711  Assert(restrictinfo->left_ec == NULL);
1712  Assert(restrictinfo->right_ec == NULL);
1713 
1714  /* Need the declared input types of the operator */
1715  op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1716 
1717  /* Find or create a matching EquivalenceClass for each side */
1718  restrictinfo->left_ec =
1720  (Expr *) get_leftop(clause),
1721  restrictinfo->nullable_relids,
1722  restrictinfo->mergeopfamilies,
1723  lefttype,
1724  ((OpExpr *) clause)->inputcollid,
1725  0,
1726  NULL,
1727  true);
1728  restrictinfo->right_ec =
1730  (Expr *) get_rightop(clause),
1731  restrictinfo->nullable_relids,
1732  restrictinfo->mergeopfamilies,
1733  righttype,
1734  ((OpExpr *) clause)->inputcollid,
1735  0,
1736  NULL,
1737  true);
1738 }
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1339
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:83
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:71
Relids nullable_relids
Definition: pathnodes.h:2102
List * mergeopfamilies
Definition: pathnodes.h:2123

References Assert(), RestrictInfo::clause, get_eclass_for_sort_expr(), get_leftop(), get_rightop(), RestrictInfo::left_ec, RestrictInfo::mergeopfamilies, NIL, RestrictInfo::nullable_relids, op_input_types(), and RestrictInfo::right_ec.

Referenced by distribute_qual_to_rels().

◆ is_redundant_derived_clause()

bool is_redundant_derived_clause ( RestrictInfo rinfo,
List clauselist 
)

Definition at line 3131 of file equivclass.c.

3132 {
3133  EquivalenceClass *parent_ec = rinfo->parent_ec;
3134  ListCell *lc;
3135 
3136  /* Fail if it's not a potentially-redundant clause from some EC */
3137  if (parent_ec == NULL)
3138  return false;
3139 
3140  foreach(lc, clauselist)
3141  {
3142  RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
3143 
3144  if (otherrinfo->parent_ec == parent_ec)
3145  return true;
3146  }
3147 
3148  return false;
3149 }
EquivalenceClass * parent_ec
Definition: pathnodes.h:2112

References lfirst, and RestrictInfo::parent_ec.

Referenced by create_tidscan_plan().

◆ is_redundant_with_indexclauses()

bool is_redundant_with_indexclauses ( RestrictInfo rinfo,
List indexclauses 
)

Definition at line 3158 of file equivclass.c.

3159 {
3160  EquivalenceClass *parent_ec = rinfo->parent_ec;
3161  ListCell *lc;
3162 
3163  foreach(lc, indexclauses)
3164  {
3165  IndexClause *iclause = lfirst_node(IndexClause, lc);
3166  RestrictInfo *otherrinfo = iclause->rinfo;
3167 
3168  /* If indexclause is lossy, it won't enforce the condition exactly */
3169  if (iclause->lossy)
3170  continue;
3171 
3172  /* Match if it's same clause (pointer equality should be enough) */
3173  if (rinfo == otherrinfo)
3174  return true;
3175  /* Match if derived from same EC */
3176  if (parent_ec && otherrinfo->parent_ec == parent_ec)
3177  return true;
3178 
3179  /*
3180  * No need to look at the derived clauses in iclause->indexquals; they
3181  * couldn't match if the parent clause didn't.
3182  */
3183  }
3184 
3185  return false;
3186 }
#define lfirst_node(type, lc)
Definition: pg_list.h:172
struct RestrictInfo * rinfo
Definition: pathnodes.h:1303

References lfirst_node, IndexClause::lossy, RestrictInfo::parent_ec, 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:686
bool have_join_order_restriction(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Definition: joinrels.c:951
static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel)
Definition: joinrels.c:1064
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:417
static ListCell * list_head(const List *l)
Definition: pg_list.h:125
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:322
List ** join_rel_level
Definition: pathnodes.h:239
bool hasLateralRTEs
Definition: pathnodes.h:348
int join_cur_level
Definition: pathnodes.h:240

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, PlannerInfo::join_rel_level, 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 59 of file pathkeys.c.

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

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

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

2073 {
2074  List *pathkeys = NIL;
2075  EquivalenceClass *lastoeclass;
2076  PathKey *opathkey;
2077  ListCell *lc;
2078  ListCell *lop;
2079 
2080  lastoeclass = NULL;
2081  opathkey = NULL;
2082  lop = list_head(outer_pathkeys);
2083 
2084  foreach(lc, mergeclauses)
2085  {
2086  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2087  EquivalenceClass *oeclass;
2088  EquivalenceClass *ieclass;
2089  PathKey *pathkey;
2090 
2091  update_mergeclause_eclasses(root, rinfo);
2092 
2093  if (rinfo->outer_is_left)
2094  {
2095  oeclass = rinfo->left_ec;
2096  ieclass = rinfo->right_ec;
2097  }
2098  else
2099  {
2100  oeclass = rinfo->right_ec;
2101  ieclass = rinfo->left_ec;
2102  }
2103 
2104  /* outer eclass should match current or next pathkeys */
2105  /* we check this carefully for debugging reasons */
2106  if (oeclass != lastoeclass)
2107  {
2108  if (!lop)
2109  elog(ERROR, "too few pathkeys for mergeclauses");
2110  opathkey = (PathKey *) lfirst(lop);
2111  lop = lnext(outer_pathkeys, lop);
2112  lastoeclass = opathkey->pk_eclass;
2113  if (oeclass != lastoeclass)
2114  elog(ERROR, "outer pathkeys do not match mergeclause");
2115  }
2116 
2117  /*
2118  * Often, we'll have same EC on both sides, in which case the outer
2119  * pathkey is also canonical for the inner side, and we can skip a
2120  * useless search.
2121  */
2122  if (ieclass == oeclass)
2123  pathkey = opathkey;
2124  else
2125  pathkey = make_canonical_pathkey(root,
2126  ieclass,
2127  opathkey->pk_opfamily,
2128  opathkey->pk_strategy,
2129  opathkey->pk_nulls_first);
2130 
2131  /*
2132  * Don't generate redundant pathkeys (which can happen if multiple
2133  * mergeclauses refer to the same EC). Because we do this, the output
2134  * pathkey list isn't necessarily ordered like the mergeclauses, which
2135  * complicates life for create_mergejoin_plan(). But if we didn't,
2136  * we'd have a noncanonical sort key list, which would be bad; for one
2137  * reason, it certainly wouldn't match any available sort order for
2138  * the input relation.
2139  */
2140  if (!pathkey_is_redundant(pathkey, pathkeys))
2141  pathkeys = lappend(pathkeys, pathkey);
2142  }
2143 
2144  return pathkeys;
2145 }

References elog, ERROR, lappend(), RestrictInfo::left_ec, lfirst, list_head(), lnext(), make_canonical_pathkey(), NIL, RestrictInfo::outer_is_left, pathkey_is_redundant(), PathKey::pk_eclass, PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, RestrictInfo::right_ec, 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 686 of file joinrels.c.

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

References Assert(), bms_free(), bms_overlap(), bms_union(), build_join_rel(), SpecialJoinInfo::delay_upper_joins, is_dummy_rel(), JOIN_INNER, join_is_legal(), SpecialJoinInfo::jointype, SpecialJoinInfo::lhs_strict, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, populate_joinrel_with_paths(), RelOptInfo::relids, SpecialJoinInfo::semi_can_btree, SpecialJoinInfo::semi_can_hash, SpecialJoinInfo::semi_operators, SpecialJoinInfo::semi_rhs_exprs, SpecialJoinInfo::syn_lefthand, SpecialJoinInfo::syn_righthand, T_SpecialJoinInfo, and SpecialJoinInfo::type.

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

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

References PlannerInfo::all_baserels, Assert(), bms_add_member(), bms_equal(), IS_DUMMY_REL, IS_SIMPLE_REL, make_rel_from_joinlist(), RelOptInfo::pages, RelOptInfo::relid, RelOptInfo::relids, RELOPT_BASEREL, RelOptInfo::reloptkind, set_base_rel_consider_startup(), set_base_rel_pathlists(), set_base_rel_sizes(), PlannerInfo::simple_rel_array, 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 1648 of file pathkeys.c.

1651 {
1652  List *pathkeys = NIL;
1653  ListCell *l;
1654 
1655  foreach(l, sortclauses)
1656  {
1657  SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
1658  Expr *sortkey;
1659  PathKey *pathkey;
1660 
1661  sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
1662  Assert(OidIsValid(sortcl->sortop));
1663  pathkey = make_pathkey_from_sortop(root,
1664  sortkey,
1665  root->nullable_baserels,
1666  sortcl->sortop,
1667  sortcl->nulls_first,
1668  sortcl->tleSortGroupRef,
1669  true);
1670 
1671  /* Canonical form eliminates redundant ordering keys */
1672  if (!pathkey_is_redundant(pathkey, pathkeys))
1673  pathkeys = lappend(pathkeys, pathkey);
1674  }
1675  return pathkeys;
1676 }
static PathKey * make_pathkey_from_sortop(PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid ordering_op, bool nulls_first, Index sortref, bool create_it)
Definition: pathkeys.c:241
Relids nullable_baserels
Definition: pathnodes.h:218
Index tleSortGroupRef
Definition: parsenodes.h:1305
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:368

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

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

◆ mark_dummy_rel()

void mark_dummy_rel ( RelOptInfo rel)

Definition at line 1261 of file joinrels.c.

1262 {
1263  MemoryContext oldcontext;
1264 
1265  /* Already marked? */
1266  if (is_dummy_rel(rel))
1267  return;
1268 
1269  /* No, so choose correct context to make the dummy path in */
1270  oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
1271 
1272  /* Set dummy size estimate */
1273  rel->rows = 0;
1274 
1275  /* Evict any previously chosen paths */
1276  rel->pathlist = NIL;
1277  rel->partial_pathlist = NIL;
1278 
1279  /* Set up the dummy path */
1280  add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NIL,
1281  NIL, rel->lateral_relids,
1282  0, false, -1));
1283 
1284  /* Set or update cheapest_total_path and related fields */
1285  set_cheapest(rel);
1286 
1287  MemoryContextSwitchTo(oldcontext);
1288 }
static MemoryContext GetMemoryChunkContext(void *pointer)
Definition: memutils.h:114
Cardinality rows
Definition: pathnodes.h:685

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

2422 {
2423  Index var1varno = fkinfo->con_relid;
2424  AttrNumber var1attno = fkinfo->conkey[colno];
2425  Index var2varno = fkinfo->ref_relid;
2426  AttrNumber var2attno = fkinfo->confkey[colno];
2427  Oid eqop = fkinfo->conpfeqop[colno];
2428  RelOptInfo *rel1 = root->simple_rel_array[var1varno];
2429  RelOptInfo *rel2 = root->simple_rel_array[var2varno];
2430  List *opfamilies = NIL; /* compute only if needed */
2431  Bitmapset *matching_ecs;
2432  int i;
2433 
2434  /* Consider only eclasses mentioning both relations */
2435  Assert(root->ec_merging_done);
2436  Assert(IS_SIMPLE_REL(rel1));
2437  Assert(IS_SIMPLE_REL(rel2));
2438  matching_ecs = bms_intersect(rel1->eclass_indexes,
2439  rel2->eclass_indexes);
2440 
2441  i = -1;
2442  while ((i = bms_next_member(matching_ecs, i)) >= 0)
2443  {
2445  i);
2446  EquivalenceMember *item1_em = NULL;
2447  EquivalenceMember *item2_em = NULL;
2448  ListCell *lc2;
2449 
2450  /* Never match to a volatile EC */
2451  if (ec->ec_has_volatile)
2452  continue;
2453  /* Note: it seems okay to match to "broken" eclasses here */
2454 
2455  foreach(lc2, ec->ec_members)
2456  {
2458  Var *var;
2459 
2460  if (em->em_is_child)
2461  continue; /* ignore children here */
2462 
2463  /* EM must be a Var, possibly with RelabelType */
2464  var = (Var *) em->em_expr;
2465  while (var && IsA(var, RelabelType))
2466  var = (Var *) ((RelabelType *) var)->arg;
2467  if (!(var && IsA(var, Var)))
2468  continue;
2469 
2470  /* Match? */
2471  if (var->varno == var1varno && var->varattno == var1attno)
2472  item1_em = em;
2473  else if (var->varno == var2varno && var->varattno == var2attno)
2474  item2_em = em;
2475 
2476  /* Have we found both PK and FK column in this EC? */
2477  if (item1_em && item2_em)
2478  {
2479  /*
2480  * Succeed if eqop matches EC's opfamilies. We could test
2481  * this before scanning the members, but it's probably cheaper
2482  * to test for member matches first.
2483  */
2484  if (opfamilies == NIL) /* compute if we didn't already */
2485  opfamilies = get_mergejoin_opfamilies(eqop);
2486  if (equal(opfamilies, ec->ec_opfamilies))
2487  {
2488  fkinfo->eclass[colno] = ec;
2489  fkinfo->fk_eclass_member[colno] = item2_em;
2490  return ec;
2491  }
2492  /* Otherwise, done with this EC, move on to the next */
2493  break;
2494  }
2495  }
2496  }
2497  return NULL;
2498 }
int16 AttrNumber
Definition: attnum.h:21
List * get_mergejoin_opfamilies(Oid opno)
Definition: lsyscache.c:364
while(p+4<=pend)
Oid conpfeqop[INDEX_MAX_KEYS]
Definition: pathnodes.h:911
AttrNumber confkey[INDEX_MAX_KEYS]
Definition: pathnodes.h:910
struct EquivalenceClass * eclass[INDEX_MAX_KEYS]
Definition: pathnodes.h:919
AttrNumber conkey[INDEX_MAX_KEYS]
Definition: pathnodes.h:909
struct EquivalenceMember * fk_eclass_member[INDEX_MAX_KEYS]
Definition: pathnodes.h:921
AttrNumber varattno
Definition: primnodes.h:200
int varno
Definition: primnodes.h:198

References Assert(), bms_intersect(), bms_next_member(), ForeignKeyOptInfo::con_relid, ForeignKeyOptInfo::confkey, ForeignKeyOptInfo::conkey, ForeignKeyOptInfo::conpfeqop, 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, PlannerInfo::simple_rel_array, 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 3720 of file indxpath.c.

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

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

867 {
868  int n = 0;
869  ListCell *key1,
870  *key2;
871 
872  /*
873  * See if we can avoiding looping through both lists. This optimization
874  * gains us several percent in planning time in a worst-case test.
875  */
876  if (keys1 == keys2)
877  {
878  *n_common = list_length(keys1);
879  return true;
880  }
881  else if (keys1 == NIL)
882  {
883  *n_common = 0;
884  return true;
885  }
886  else if (keys2 == NIL)
887  {
888  *n_common = 0;
889  return false;
890  }
891 
892  /*
893  * If both lists are non-empty, iterate through both to find out how many
894  * items are shared.
895  */
896  forboth(key1, keys1, key2, keys2)
897  {
898  PathKey *pathkey1 = (PathKey *) lfirst(key1);
899  PathKey *pathkey2 = (PathKey *) lfirst(key2);
900 
901  if (pathkey1 != pathkey2)
902  {
903  *n_common = n;
904  return false;
905  }
906  n++;
907  }
908 
909  /* If we ended with a null value, then we've processed the whole list. */
910  *n_common = n;
911  return (key1 == NULL);
912 }

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

Referenced by add_paths_to_grouping_rel(), create_one_window_path(), create_ordered_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,
bool  below_outer_join 
)

Definition at line 119 of file equivclass.c.

122 {
123  RestrictInfo *restrictinfo = *p_restrictinfo;
124  Expr *clause = restrictinfo->clause;
125  Oid opno,
126  collation,
127  item1_type,
128  item2_type;
129  Expr *item1;
130  Expr *item2;
131  Relids item1_relids,
132  item2_relids,
133  item1_nullable_relids,
134  item2_nullable_relids;
135  List *opfamilies;
136  EquivalenceClass *ec1,
137  *ec2;
138  EquivalenceMember *em1,
139  *em2;
140  ListCell *lc1;
141  int ec2_idx;
142 
143  /* Should not already be marked as having generated an eclass */
144  Assert(restrictinfo->left_ec == NULL);
145  Assert(restrictinfo->right_ec == NULL);
146 
147  /* Reject if it is potentially postponable by security considerations */
148  if (restrictinfo->security_level > 0 && !restrictinfo->leakproof)
149  return false;
150 
151  /* Extract info from given clause */
152  Assert(is_opclause(clause));
153  opno = ((OpExpr *) clause)->opno;
154  collation = ((OpExpr *) clause)->inputcollid;
155  item1 = (Expr *) get_leftop(clause);
156  item2 = (Expr *) get_rightop(clause);
157  item1_relids = res