PostgreSQL Source Code  git master
pathkeys.c File Reference
Include dependency graph for pathkeys.c:

Go to the source code of this file.

Functions

static bool pathkey_is_redundant (PathKey *new_pathkey, List *pathkeys)
 
static bool matches_boolean_partition_clause (RestrictInfo *rinfo, RelOptInfo *partrel, int partkeycol)
 
static Varfind_var_for_subquery_tle (RelOptInfo *rel, TargetEntry *tle)
 
static bool right_merge_direction (PlannerInfo *root, PathKey *pathkey)
 
PathKeymake_canonical_pathkey (PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
 
static PathKeymake_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)
 
static PathKeymake_pathkey_from_sortop (PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid ordering_op, bool nulls_first, Index sortref, bool create_it)
 
PathKeysComparison compare_pathkeys (List *keys1, List *keys2)
 
bool pathkeys_contained_in (List *keys1, List *keys2)
 
bool pathkeys_count_contained_in (List *keys1, List *keys2, int *n_common)
 
Pathget_cheapest_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
 
Pathget_cheapest_fractional_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, double fraction)
 
Pathget_cheapest_parallel_safe_total_inner (List *paths)
 
Listbuild_index_pathkeys (PlannerInfo *root, IndexOptInfo *index, ScanDirection scandir)
 
static bool partkey_is_bool_constant_for_query (RelOptInfo *partrel, int partkeycol)
 
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)
 
static int pathkeys_useful_for_merging (PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
 
static int pathkeys_useful_for_ordering (PlannerInfo *root, List *pathkeys)
 
Listtruncate_useless_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
 
bool has_useful_pathkeys (PlannerInfo *root, RelOptInfo *rel)
 

Function Documentation

◆ build_expression_pathkey()

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

Definition at line 782 of file pathkeys.c.

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

Referenced by set_function_pathlist().

788 {
789  List *pathkeys;
790  Oid opfamily,
791  opcintype;
792  int16 strategy;
793  PathKey *cpathkey;
794 
795  /* Find the operator in pg_amop --- failure shouldn't happen */
796  if (!get_ordering_op_properties(opno,
797  &opfamily, &opcintype, &strategy))
798  elog(ERROR, "operator %u is not a valid ordering operator",
799  opno);
800 
801  cpathkey = make_pathkey_from_sortinfo(root,
802  expr,
803  nullable_relids,
804  opfamily,
805  opcintype,
806  exprCollation((Node *) expr),
807  (strategy == BTGreaterStrategyNumber),
808  (strategy == BTGreaterStrategyNumber),
809  0,
810  rel,
811  create_it);
812 
813  if (cpathkey)
814  pathkeys = list_make1(cpathkey);
815  else
816  pathkeys = NIL;
817 
818  return pathkeys;
819 }
signed short int16
Definition: c.h:354
#define NIL
Definition: pg_list.h:65
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
Definition: nodes.h:529
unsigned int Oid
Definition: postgres_ext.h:31
#define list_make1(x1)
Definition: pg_list.h:227
#define ERROR
Definition: elog.h:43
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:719
#define elog(elevel,...)
Definition: elog.h:214
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:177
Definition: pg_list.h:50

◆ build_index_pathkeys()

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

Definition at line 523 of file pathkeys.c.

References TargetEntry::expr, i, indexcol_is_bool_constant_for_query(), IndexOptInfo::indexcollations, IndexOptInfo::indextlist, lappend(), lfirst, make_pathkey_from_sortinfo(), NIL, IndexOptInfo::nkeycolumns, IndexOptInfo::nulls_first, IndexOptInfo::opcintype, pathkey_is_redundant(), IndexOptInfo::rel, RelOptInfo::relids, IndexOptInfo::reverse_sort, ScanDirectionIsBackward, and IndexOptInfo::sortopfamily.

Referenced by build_index_paths().

526 {
527  List *retval = NIL;
528  ListCell *lc;
529  int i;
530 
531  if (index->sortopfamily == NULL)
532  return NIL; /* non-orderable index */
533 
534  i = 0;
535  foreach(lc, index->indextlist)
536  {
537  TargetEntry *indextle = (TargetEntry *) lfirst(lc);
538  Expr *indexkey;
539  bool reverse_sort;
540  bool nulls_first;
541  PathKey *cpathkey;
542 
543  /*
544  * INCLUDE columns are stored in index unordered, so they don't
545  * support ordered index scan.
546  */
547  if (i >= index->nkeycolumns)
548  break;
549 
550  /* We assume we don't need to make a copy of the tlist item */
551  indexkey = indextle->expr;
552 
553  if (ScanDirectionIsBackward(scandir))
554  {
555  reverse_sort = !index->reverse_sort[i];
556  nulls_first = !index->nulls_first[i];
557  }
558  else
559  {
560  reverse_sort = index->reverse_sort[i];
561  nulls_first = index->nulls_first[i];
562  }
563 
564  /*
565  * OK, try to make a canonical pathkey for this sort key. Note we're
566  * underneath any outer joins, so nullable_relids should be NULL.
567  */
568  cpathkey = make_pathkey_from_sortinfo(root,
569  indexkey,
570  NULL,
571  index->sortopfamily[i],
572  index->opcintype[i],
573  index->indexcollations[i],
574  reverse_sort,
575  nulls_first,
576  0,
577  index->rel->relids,
578  false);
579 
580  if (cpathkey)
581  {
582  /*
583  * We found the sort key in an EquivalenceClass, so it's relevant
584  * for this query. Add it to list, unless it's redundant.
585  */
586  if (!pathkey_is_redundant(cpathkey, retval))
587  retval = lappend(retval, cpathkey);
588  }
589  else
590  {
591  /*
592  * Boolean index keys might be redundant even if they do not
593  * appear in an EquivalenceClass, because of our special treatment
594  * of boolean equality conditions --- see the comment for
595  * indexcol_is_bool_constant_for_query(). If that applies, we can
596  * continue to examine lower-order index columns. Otherwise, the
597  * sort key is not an interesting sort order for this query, so we
598  * should stop considering index columns; any lower-order sort
599  * keys won't be useful either.
600  */
602  break;
603  }
604 
605  i++;
606  }
607 
608  return retval;
609 }
#define NIL
Definition: pg_list.h:65
Oid * indexcollations
Definition: pathnodes.h:832
List * indextlist
Definition: pathnodes.h:846
Oid * sortopfamily
Definition: pathnodes.h:835
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
RelOptInfo * rel
Definition: pathnodes.h:820
Relids relids
Definition: pathnodes.h:665
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:135
List * lappend(List *list, void *datum)
Definition: list.c:321
#define lfirst(lc)
Definition: pg_list.h:190
Expr * expr
Definition: primnodes.h:1407
int nkeycolumns
Definition: pathnodes.h:829
Oid * opcintype
Definition: pathnodes.h:834
bool indexcol_is_bool_constant_for_query(IndexOptInfo *index, int indexcol)
Definition: indxpath.c:3757
int i
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:177
bool * nulls_first
Definition: pathnodes.h:837
bool * reverse_sort
Definition: pathnodes.h:836
Definition: pg_list.h:50

◆ build_join_pathkeys()

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

Definition at line 1082 of file pathkeys.c.

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

1086 {
1087  if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
1088  return NIL;
1089 
1090  /*
1091  * This used to be quite a complex bit of code, but now that all pathkey
1092  * sublists start out life canonicalized, we don't have to do a darn thing
1093  * here!
1094  *
1095  * We do, however, need to truncate the pathkeys list, since it may
1096  * contain pathkeys that were useful for forming this joinrel but are
1097  * uninteresting to higher levels.
1098  */
1099  return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1100 }
#define NIL
Definition: pg_list.h:65
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:1870

◆ build_partition_pathkeys()

List* build_partition_pathkeys ( PlannerInfo root,
RelOptInfo partrel,
ScanDirection  scandir,
bool partialkeys 
)

Definition at line 699 of file pathkeys.c.

References Assert, RelOptInfo::boundinfo, i, IS_SIMPLE_REL, lappend(), linitial, make_pathkey_from_sortinfo(), NIL, RelOptInfo::nparts, 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().

701 {
702  List *retval = NIL;
703  PartitionScheme partscheme = partrel->part_scheme;
704  int i;
705 
706  Assert(partscheme != NULL);
707  Assert(partitions_are_ordered(partrel->boundinfo, partrel->nparts));
708  /* For now, we can only cope with baserels */
709  Assert(IS_SIMPLE_REL(partrel));
710 
711  for (i = 0; i < partscheme->partnatts; i++)
712  {
713  PathKey *cpathkey;
714  Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]);
715 
716  /*
717  * Try to make a canonical pathkey for this partkey.
718  *
719  * We're considering a baserel scan, so nullable_relids should be
720  * NULL. Also, we assume the PartitionDesc lists any NULL partition
721  * last, so we treat the scan like a NULLS LAST index: we have
722  * nulls_first for backwards scan only.
723  */
724  cpathkey = make_pathkey_from_sortinfo(root,
725  keyCol,
726  NULL,
727  partscheme->partopfamily[i],
728  partscheme->partopcintype[i],
729  partscheme->partcollation[i],
730  ScanDirectionIsBackward(scandir),
731  ScanDirectionIsBackward(scandir),
732  0,
733  partrel->relids,
734  false);
735 
736 
737  if (cpathkey)
738  {
739  /*
740  * We found the sort key in an EquivalenceClass, so it's relevant
741  * for this query. Add it to list, unless it's redundant.
742  */
743  if (!pathkey_is_redundant(cpathkey, retval))
744  retval = lappend(retval, cpathkey);
745  }
746  else
747  {
748  /*
749  * Boolean partition keys might be redundant even if they do not
750  * appear in an EquivalenceClass, because of our special treatment
751  * of boolean equality conditions --- see the comment for
752  * partkey_is_bool_constant_for_query(). If that applies, we can
753  * continue to examine lower-order partition keys. Otherwise, the
754  * sort key is not an interesting sort order for this query, so we
755  * should stop considering partition columns; any lower-order sort
756  * keys won't be useful either.
757  */
758  if (!partkey_is_bool_constant_for_query(partrel, i))
759  {
760  *partialkeys = true;
761  return retval;
762  }
763  }
764  }
765 
766  *partialkeys = false;
767  return retval;
768 }
#define NIL
Definition: pg_list.h:65
static bool partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:629
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:638
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
List ** partexprs
Definition: pathnodes.h:753
#define linitial(l)
Definition: pg_list.h:195
int nparts
Definition: pathnodes.h:743
Relids relids
Definition: pathnodes.h:665
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:135
List * lappend(List *list, void *datum)
Definition: list.c:321
struct PartitionBoundInfoData * boundinfo
Definition: pathnodes.h:746
bool partitions_are_ordered(PartitionBoundInfo boundinfo, int nparts)
Definition: partbounds.c:2750
#define Assert(condition)
Definition: c.h:738
int i
PartitionScheme part_scheme
Definition: pathnodes.h:742
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:177
Definition: pg_list.h:50

◆ compare_pathkeys()

PathKeysComparison compare_pathkeys ( List keys1,
List keys2 
)

Definition at line 285 of file pathkeys.c.

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

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

◆ convert_subquery_pathkeys()

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

Definition at line 838 of file pathkeys.c.

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

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

◆ find_mergeclauses_for_outer_pathkeys()

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

Definition at line 1262 of file pathkeys.c.

References i, 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().

1265 {
1266  List *mergeclauses = NIL;
1267  ListCell *i;
1268 
1269  /* make sure we have eclasses cached in the clauses */
1270  foreach(i, restrictinfos)
1271  {
1272  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1273 
1274  update_mergeclause_eclasses(root, rinfo);
1275  }
1276 
1277  foreach(i, pathkeys)
1278  {
1279  PathKey *pathkey = (PathKey *) lfirst(i);
1280  EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1281  List *matched_restrictinfos = NIL;
1282  ListCell *j;
1283 
1284  /*----------
1285  * A mergejoin clause matches a pathkey if it has the same EC.
1286  * If there are multiple matching clauses, take them all. In plain
1287  * inner-join scenarios we expect only one match, because
1288  * equivalence-class processing will have removed any redundant
1289  * mergeclauses. However, in outer-join scenarios there might be
1290  * multiple matches. An example is
1291  *
1292  * select * from a full join b
1293  * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1294  *
1295  * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1296  * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1297  * we *must* do so or we will be unable to form a valid plan.
1298  *
1299  * We expect that the given pathkeys list is canonical, which means
1300  * no two members have the same EC, so it's not possible for this
1301  * code to enter the same mergeclause into the result list twice.
1302  *
1303  * It's possible that multiple matching clauses might have different
1304  * ECs on the other side, in which case the order we put them into our
1305  * result makes a difference in the pathkeys required for the inner
1306  * input rel. However this routine hasn't got any info about which
1307  * order would be best, so we don't worry about that.
1308  *
1309  * It's also possible that the selected mergejoin clauses produce
1310  * a noncanonical ordering of pathkeys for the inner side, ie, we
1311  * might select clauses that reference b.v1, b.v2, b.v1 in that
1312  * order. This is not harmful in itself, though it suggests that
1313  * the clauses are partially redundant. Since the alternative is
1314  * to omit mergejoin clauses and thereby possibly fail to generate a
1315  * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1316  * has to delete duplicates when it constructs the inner pathkeys
1317  * list, and we also have to deal with such cases specially in
1318  * create_mergejoin_plan().
1319  *----------
1320  */
1321  foreach(j, restrictinfos)
1322  {
1323  RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1324  EquivalenceClass *clause_ec;
1325 
1326  clause_ec = rinfo->outer_is_left ?
1327  rinfo->left_ec : rinfo->right_ec;
1328  if (clause_ec == pathkey_ec)
1329  matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1330  }
1331 
1332  /*
1333  * If we didn't find a mergeclause, we're done --- any additional
1334  * sort-key positions in the pathkeys are useless. (But we can still
1335  * mergejoin if we found at least one mergeclause.)
1336  */
1337  if (matched_restrictinfos == NIL)
1338  break;
1339 
1340  /*
1341  * If we did find usable mergeclause(s) for this sort-key position,
1342  * add them to result list.
1343  */
1344  mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1345  }
1346 
1347  return mergeclauses;
1348 }
#define NIL
Definition: pg_list.h:65
List * list_concat(List *list1, const List *list2)
Definition: list.c:515
EquivalenceClass * right_ec
Definition: pathnodes.h:2034
bool outer_is_left
Definition: pathnodes.h:2040
List * lappend(List *list, void *datum)
Definition: list.c:321
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1041
EquivalenceClass * left_ec
Definition: pathnodes.h:2033
int i
Definition: pg_list.h:50
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1228

◆ find_var_for_subquery_tle()

static Var * find_var_for_subquery_tle ( RelOptInfo rel,
TargetEntry tle 
)
static

Definition at line 1039 of file pathkeys.c.

References Assert, copyObject, PathTarget::exprs, IsA, lfirst, RelOptInfo::relid, RelOptInfo::reltarget, TargetEntry::resjunk, TargetEntry::resno, RangeQueryClause::var, Var::varattno, and Var::varno.

Referenced by convert_subquery_pathkeys().

1040 {
1041  ListCell *lc;
1042 
1043  /* If the TLE is resjunk, it's certainly not visible to the outer query */
1044  if (tle->resjunk)
1045  return NULL;
1046 
1047  /* Search the rel's targetlist to see what it will return */
1048  foreach(lc, rel->reltarget->exprs)
1049  {
1050  Var *var = (Var *) lfirst(lc);
1051 
1052  /* Ignore placeholders */
1053  if (!IsA(var, Var))
1054  continue;
1055  Assert(var->varno == rel->relid);
1056 
1057  /* If we find a Var referencing this TLE, we're good */
1058  if (var->varattno == tle->resno)
1059  return copyObject(var); /* Make a copy for safety */
1060  }
1061  return NULL;
1062 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:580
AttrNumber varattno
Definition: primnodes.h:186
Definition: primnodes.h:181
bool resjunk
Definition: primnodes.h:1414
AttrNumber resno
Definition: primnodes.h:1408
Index relid
Definition: pathnodes.h:693
Index varno
Definition: primnodes.h:184
List * exprs
Definition: pathnodes.h:1074
#define Assert(condition)
Definition: c.h:738
#define lfirst(lc)
Definition: pg_list.h:190
#define copyObject(obj)
Definition: nodes.h:645
struct PathTarget * reltarget
Definition: pathnodes.h:676

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

References bms_is_subset(), compare_fractional_path_costs(), lfirst, PATH_REQ_OUTER, Path::pathkeys, and pathkeys_contained_in().

Referenced by build_minmax_path().

453 {
454  Path *matched_path = NULL;
455  ListCell *l;
456 
457  foreach(l, paths)
458  {
459  Path *path = (Path *) lfirst(l);
460 
461  /*
462  * Since cost comparison is a lot cheaper than pathkey comparison, do
463  * that first. (XXX is that still true?)
464  */
465  if (matched_path != NULL &&
466  compare_fractional_path_costs(matched_path, path, fraction) <= 0)
467  continue;
468 
469  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
470  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
471  matched_path = path;
472  }
473  return matched_path;
474 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1163
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:324
List * pathkeys
Definition: pathnodes.h:1158
#define lfirst(lc)
Definition: pg_list.h:190
int compare_fractional_path_costs(Path *path1, Path *path2, double fraction)
Definition: pathnode.c:117

◆ get_cheapest_parallel_safe_total_inner()

Path* get_cheapest_parallel_safe_total_inner ( List paths)

Definition at line 482 of file pathkeys.c.

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

483 {
484  ListCell *l;
485 
486  foreach(l, paths)
487  {
488  Path *innerpath = (Path *) lfirst(l);
489 
490  if (innerpath->parallel_safe &&
491  bms_is_empty(PATH_REQ_OUTER(innerpath)))
492  return innerpath;
493  }
494 
495  return NULL;
496 }
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1163
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:701
#define lfirst(lc)
Definition: pg_list.h:190
bool parallel_safe
Definition: pathnodes.h:1150

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

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

408 {
409  Path *matched_path = NULL;
410  ListCell *l;
411 
412  foreach(l, paths)
413  {
414  Path *path = (Path *) lfirst(l);
415 
416  /*
417  * Since cost comparison is a lot cheaper than pathkey comparison, do
418  * that first. (XXX is that still true?)
419  */
420  if (matched_path != NULL &&
421  compare_path_costs(matched_path, path, cost_criterion) <= 0)
422  continue;
423 
424  if (require_parallel_safe && !path->parallel_safe)
425  continue;
426 
427  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
428  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
429  matched_path = path;
430  }
431  return matched_path;
432 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
int compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
Definition: pathnode.c:71
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1163
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:324
List * pathkeys
Definition: pathnodes.h:1158
#define lfirst(lc)
Definition: pg_list.h:190
bool parallel_safe
Definition: pathnodes.h:1150

◆ has_useful_pathkeys()

bool has_useful_pathkeys ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 1910 of file pathkeys.c.

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

Referenced by build_child_join_rel(), build_index_paths(), and set_append_rel_size().

1911 {
1912  if (rel->joininfo != NIL || rel->has_eclass_joins)
1913  return true; /* might be able to use pathkeys for merging */
1914  if (root->query_pathkeys != NIL)
1915  return true; /* might be able to use them for ordering */
1916  return false; /* definitely useless */
1917 }
bool has_eclass_joins
Definition: pathnodes.h:733
#define NIL
Definition: pg_list.h:65
List * query_pathkeys
Definition: pathnodes.h:298
List * joininfo
Definition: pathnodes.h:731

◆ initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1179 of file pathkeys.c.

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

1180 {
1181  Expr *clause = restrictinfo->clause;
1182  Oid lefttype,
1183  righttype;
1184 
1185  /* Should be a mergeclause ... */
1186  Assert(restrictinfo->mergeopfamilies != NIL);
1187  /* ... with links not yet set */
1188  Assert(restrictinfo->left_ec == NULL);
1189  Assert(restrictinfo->right_ec == NULL);
1190 
1191  /* Need the declared input types of the operator */
1192  op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1193 
1194  /* Find or create a matching EquivalenceClass for each side */
1195  restrictinfo->left_ec =
1197  (Expr *) get_leftop(clause),
1198  restrictinfo->nullable_relids,
1199  restrictinfo->mergeopfamilies,
1200  lefttype,
1201  ((OpExpr *) clause)->inputcollid,
1202  0,
1203  NULL,
1204  true);
1205  restrictinfo->right_ec =
1207  (Expr *) get_rightop(clause),
1208  restrictinfo->nullable_relids,
1209  restrictinfo->mergeopfamilies,
1210  righttype,
1211  ((OpExpr *) clause)->inputcollid,
1212  0,
1213  NULL,
1214  true);
1215 }
#define NIL
Definition: pg_list.h:65
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:625
EquivalenceClass * right_ec
Definition: pathnodes.h:2034
unsigned int Oid
Definition: postgres_ext.h:31
List * mergeopfamilies
Definition: pathnodes.h:2030
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1226
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:70
Expr * clause
Definition: pathnodes.h:1985
Relids nullable_relids
Definition: pathnodes.h:2009
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:82
#define Assert(condition)
Definition: c.h:738
EquivalenceClass * left_ec
Definition: pathnodes.h:2033

◆ make_canonical_pathkey()

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

Definition at line 54 of file pathkeys.c.

References PlannerInfo::canon_pathkeys, EquivalenceClass::ec_merged, 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().

57 {
58  PathKey *pk;
59  ListCell *lc;
60  MemoryContext oldcontext;
61 
62  /* Can't make canonical pathkeys if the set of ECs might still change */
63  if (!root->ec_merging_done)
64  elog(ERROR, "too soon to build canonical pathkeys");
65 
66  /* The passed eclass might be non-canonical, so chase up to the top */
67  while (eclass->ec_merged)
68  eclass = eclass->ec_merged;
69 
70  foreach(lc, root->canon_pathkeys)
71  {
72  pk = (PathKey *) lfirst(lc);
73  if (eclass == pk->pk_eclass &&
74  opfamily == pk->pk_opfamily &&
75  strategy == pk->pk_strategy &&
76  nulls_first == pk->pk_nulls_first)
77  return pk;
78  }
79 
80  /*
81  * Be sure canonical pathkeys are allocated in the main planning context.
82  * Not an issue in normal planning, but it is for GEQO.
83  */
84  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
85 
86  pk = makeNode(PathKey);
87  pk->pk_eclass = eclass;
88  pk->pk_opfamily = opfamily;
89  pk->pk_strategy = strategy;
90  pk->pk_nulls_first = nulls_first;
91 
92  root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
93 
94  MemoryContextSwitchTo(oldcontext);
95 
96  return pk;
97 }
bool ec_merging_done
Definition: pathnodes.h:268
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int pk_strategy
Definition: pathnodes.h:1043
static struct cvec * eclass(struct vars *v, chr c, int cases)
Definition: regc_locale.c:508
bool pk_nulls_first
Definition: pathnodes.h:1044
#define ERROR
Definition: elog.h:43
List * canon_pathkeys
Definition: pathnodes.h:270
List * lappend(List *list, void *datum)
Definition: list.c:321
#define makeNode(_type_)
Definition: nodes.h:577
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1041
Oid pk_opfamily
Definition: pathnodes.h:1042
#define elog(elevel,...)
Definition: elog.h:214
MemoryContext planner_cxt
Definition: pathnodes.h:331
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:976

◆ make_inner_pathkeys_for_merge()

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

Definition at line 1547 of file pathkeys.c.

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

1550 {
1551  List *pathkeys = NIL;
1552  EquivalenceClass *lastoeclass;
1553  PathKey *opathkey;
1554  ListCell *lc;
1555  ListCell *lop;
1556 
1557  lastoeclass = NULL;
1558  opathkey = NULL;
1559  lop = list_head(outer_pathkeys);
1560 
1561  foreach(lc, mergeclauses)
1562  {
1563  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1564  EquivalenceClass *oeclass;
1565  EquivalenceClass *ieclass;
1566  PathKey *pathkey;
1567 
1568  update_mergeclause_eclasses(root, rinfo);
1569 
1570  if (rinfo->outer_is_left)
1571  {
1572  oeclass = rinfo->left_ec;
1573  ieclass = rinfo->right_ec;
1574  }
1575  else
1576  {
1577  oeclass = rinfo->right_ec;
1578  ieclass = rinfo->left_ec;
1579  }
1580 
1581  /* outer eclass should match current or next pathkeys */
1582  /* we check this carefully for debugging reasons */
1583  if (oeclass != lastoeclass)
1584  {
1585  if (!lop)
1586  elog(ERROR, "too few pathkeys for mergeclauses");
1587  opathkey = (PathKey *) lfirst(lop);
1588  lop = lnext(outer_pathkeys, lop);
1589  lastoeclass = opathkey->pk_eclass;
1590  if (oeclass != lastoeclass)
1591  elog(ERROR, "outer pathkeys do not match mergeclause");
1592  }
1593 
1594  /*
1595  * Often, we'll have same EC on both sides, in which case the outer
1596  * pathkey is also canonical for the inner side, and we can skip a
1597  * useless search.
1598  */
1599  if (ieclass == oeclass)
1600  pathkey = opathkey;
1601  else
1602  pathkey = make_canonical_pathkey(root,
1603  ieclass,
1604  opathkey->pk_opfamily,
1605  opathkey->pk_strategy,
1606  opathkey->pk_nulls_first);
1607 
1608  /*
1609  * Don't generate redundant pathkeys (which can happen if multiple
1610  * mergeclauses refer to the same EC). Because we do this, the output
1611  * pathkey list isn't necessarily ordered like the mergeclauses, which
1612  * complicates life for create_mergejoin_plan(). But if we didn't,
1613  * we'd have a noncanonical sort key list, which would be bad; for one
1614  * reason, it certainly wouldn't match any available sort order for
1615  * the input relation.
1616  */
1617  if (!pathkey_is_redundant(pathkey, pathkeys))
1618  pathkeys = lappend(pathkeys, pathkey);
1619  }
1620 
1621  return pathkeys;
1622 }
#define NIL
Definition: pg_list.h:65
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:321
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:54
EquivalenceClass * right_ec
Definition: pathnodes.h:2034
int pk_strategy
Definition: pathnodes.h:1043
bool pk_nulls_first
Definition: pathnodes.h:1044
#define ERROR
Definition: elog.h:43
bool outer_is_left
Definition: pathnodes.h:2040
static ListCell * list_head(const List *l)
Definition: pg_list.h:125
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:135
List * lappend(List *list, void *datum)
Definition: list.c:321
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1041
Oid pk_opfamily
Definition: pathnodes.h:1042
EquivalenceClass * left_ec
Definition: pathnodes.h:2033
#define elog(elevel,...)
Definition: elog.h:214
Definition: pg_list.h:50
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1228

◆ make_pathkey_from_sortinfo()

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

Definition at line 177 of file pathkeys.c.

References BTEqualStrategyNumber, BTGreaterStrategyNumber, BTLessStrategyNumber, eclass(), elog, ERROR, get_eclass_for_sort_expr(), get_mergejoin_opfamilies(), get_opfamily_member(), make_canonical_pathkey(), and OidIsValid.

Referenced by build_expression_pathkey(), build_index_pathkeys(), build_partition_pathkeys(), and make_pathkey_from_sortop().

188 {
189  int16 strategy;
190  Oid equality_op;
191  List *opfamilies;
193 
194  strategy = reverse_sort ? BTGreaterStrategyNumber : BTLessStrategyNumber;
195 
196  /*
197  * EquivalenceClasses need to contain opfamily lists based on the family
198  * membership of mergejoinable equality operators, which could belong to
199  * more than one opfamily. So we have to look up the opfamily's equality
200  * operator and get its membership.
201  */
202  equality_op = get_opfamily_member(opfamily,
203  opcintype,
204  opcintype,
206  if (!OidIsValid(equality_op)) /* shouldn't happen */
207  elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
208  BTEqualStrategyNumber, opcintype, opcintype, opfamily);
209  opfamilies = get_mergejoin_opfamilies(equality_op);
210  if (!opfamilies) /* certainly should find some */
211  elog(ERROR, "could not find opfamilies for equality operator %u",
212  equality_op);
213 
214  /* Now find or (optionally) create a matching EquivalenceClass */
215  eclass = get_eclass_for_sort_expr(root, expr, nullable_relids,
216  opfamilies, opcintype, collation,
217  sortref, rel, create_it);
218 
219  /* Fail if no EC and !create_it */
220  if (!eclass)
221  return NULL;
222 
223  /* And finally we can find or create a PathKey node */
224  return make_canonical_pathkey(root, eclass, opfamily,
225  strategy, nulls_first);
226 }
signed short int16
Definition: c.h:354
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
List * get_mergejoin_opfamilies(Oid opno)
Definition: lsyscache.c:364
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:625
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:54
unsigned int Oid
Definition: postgres_ext.h:31
#define OidIsValid(objectId)
Definition: c.h:644
static struct cvec * eclass(struct vars *v, chr c, int cases)
Definition: regc_locale.c:508
#define ERROR
Definition: elog.h:43
Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, int16 strategy)
Definition: lsyscache.c:164
#define elog(elevel,...)
Definition: elog.h:214
#define BTLessStrategyNumber
Definition: stratnum.h:29
Definition: pg_list.h:50
#define BTEqualStrategyNumber
Definition: stratnum.h:31

◆ make_pathkey_from_sortop()

static PathKey* make_pathkey_from_sortop ( PlannerInfo root,
Expr expr,
Relids  nullable_relids,
Oid  ordering_op,
bool  nulls_first,
Index  sortref,
bool  create_it 
)
static

Definition at line 236 of file pathkeys.c.

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

Referenced by make_pathkeys_for_sortclauses().

243 {
244  Oid opfamily,
245  opcintype,
246  collation;
247  int16 strategy;
248 
249  /* Find the operator in pg_amop --- failure shouldn't happen */
250  if (!get_ordering_op_properties(ordering_op,
251  &opfamily, &opcintype, &strategy))
252  elog(ERROR, "operator %u is not a valid ordering operator",
253  ordering_op);
254 
255  /* Because SortGroupClause doesn't carry collation, consult the expr */
256  collation = exprCollation((Node *) expr);
257 
258  return make_pathkey_from_sortinfo(root,
259  expr,
260  nullable_relids,
261  opfamily,
262  opcintype,
263  collation,
264  (strategy == BTGreaterStrategyNumber),
265  nulls_first,
266  sortref,
267  NULL,
268  create_it);
269 }
signed short int16
Definition: c.h:354
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
Definition: nodes.h:529
unsigned int Oid
Definition: postgres_ext.h:31
#define ERROR
Definition: elog.h:43
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:719
#define elog(elevel,...)
Definition: elog.h:214
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:177

◆ make_pathkeys_for_sortclauses()

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

Definition at line 1125 of file pathkeys.c.

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

1128 {
1129  List *pathkeys = NIL;
1130  ListCell *l;
1131 
1132  foreach(l, sortclauses)
1133  {
1134  SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
1135  Expr *sortkey;
1136  PathKey *pathkey;
1137 
1138  sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
1139  Assert(OidIsValid(sortcl->sortop));
1140  pathkey = make_pathkey_from_sortop(root,
1141  sortkey,
1142  root->nullable_baserels,
1143  sortcl->sortop,
1144  sortcl->nulls_first,
1145  sortcl->tleSortGroupRef,
1146  true);
1147 
1148  /* Canonical form eliminates redundant ordering keys */
1149  if (!pathkey_is_redundant(pathkey, pathkeys))
1150  pathkeys = lappend(pathkeys, pathkey);
1151  }
1152  return pathkeys;
1153 }
#define NIL
Definition: pg_list.h:65
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:236
Index tleSortGroupRef
Definition: parsenodes.h:1257
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:401
#define OidIsValid(objectId)
Definition: c.h:644
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:135
List * lappend(List *list, void *datum)
Definition: list.c:321
#define Assert(condition)
Definition: c.h:738
#define lfirst(lc)
Definition: pg_list.h:190
Relids nullable_baserels
Definition: pathnodes.h:235
Definition: pg_list.h:50

◆ matches_boolean_partition_clause()

static bool matches_boolean_partition_clause ( RestrictInfo rinfo,
RelOptInfo partrel,
int  partkeycol 
)
static

Definition at line 664 of file pathkeys.c.

References arg, RestrictInfo::clause, equal(), get_notclausearg(), is_notclause(), linitial, and RelOptInfo::partexprs.

Referenced by partkey_is_bool_constant_for_query().

666 {
667  Node *clause = (Node *) rinfo->clause;
668  Node *partexpr = (Node *) linitial(partrel->partexprs[partkeycol]);
669 
670  /* Direct match? */
671  if (equal(partexpr, clause))
672  return true;
673  /* NOT clause? */
674  else if (is_notclause(clause))
675  {
676  Node *arg = (Node *) get_notclausearg((Expr *) clause);
677 
678  if (equal(partexpr, arg))
679  return true;
680  }
681 
682  return false;
683 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3033
Definition: nodes.h:529
List ** partexprs
Definition: pathnodes.h:753
#define linitial(l)
Definition: pg_list.h:195
Expr * clause
Definition: pathnodes.h:1985
static bool is_notclause(const void *clause)
Definition: nodeFuncs.h:112
static Expr * get_notclausearg(const void *notclause)
Definition: nodeFuncs.h:121
void * arg

◆ partkey_is_bool_constant_for_query()

static bool partkey_is_bool_constant_for_query ( RelOptInfo partrel,
int  partkeycol 
)
static

Definition at line 629 of file pathkeys.c.

References RelOptInfo::baserestrictinfo, lfirst, matches_boolean_partition_clause(), RelOptInfo::part_scheme, PartitionSchemeData::partopfamily, and RestrictInfo::pseudoconstant.

Referenced by build_partition_pathkeys().

630 {
631  PartitionScheme partscheme = partrel->part_scheme;
632  ListCell *lc;
633 
634  /* If the partkey isn't boolean, we can't possibly get a match */
635  if (!IsBooleanOpfamily(partscheme->partopfamily[partkeycol]))
636  return false;
637 
638  /* Check each restriction clause for the partitioned rel */
639  foreach(lc, partrel->baserestrictinfo)
640  {
641  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
642 
643  /* Ignore pseudoconstant quals, they won't match */
644  if (rinfo->pseudoconstant)
645  continue;
646 
647  /* See if we can match the clause's expression to the partkey column */
648  if (matches_boolean_partition_clause(rinfo, partrel, partkeycol))
649  return true;
650  }
651 
652  return false;
653 }
List * baserestrictinfo
Definition: pathnodes.h:727
bool pseudoconstant
Definition: pathnodes.h:1993
static bool matches_boolean_partition_clause(RestrictInfo *rinfo, RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:664
#define lfirst(lc)
Definition: pg_list.h:190
PartitionScheme part_scheme
Definition: pathnodes.h:742

◆ pathkey_is_redundant()

static bool pathkey_is_redundant ( PathKey new_pathkey,
List pathkeys 
)
static

Definition at line 135 of file pathkeys.c.

References EC_MUST_BE_REDUNDANT, lfirst, and PathKey::pk_eclass.

Referenced by build_index_pathkeys(), build_partition_pathkeys(), convert_subquery_pathkeys(), make_inner_pathkeys_for_merge(), make_pathkeys_for_sortclauses(), and select_outer_pathkeys_for_merge().

136 {
137  EquivalenceClass *new_ec = new_pathkey->pk_eclass;
138  ListCell *lc;
139 
140  /* Check for EC containing a constant --- unconditionally redundant */
141  if (EC_MUST_BE_REDUNDANT(new_ec))
142  return true;
143 
144  /* If same EC already used in list, then redundant */
145  foreach(lc, pathkeys)
146  {
147  PathKey *old_pathkey = (PathKey *) lfirst(lc);
148 
149  if (new_ec == old_pathkey->pk_eclass)
150  return true;
151  }
152 
153  return false;
154 }
#define EC_MUST_BE_REDUNDANT(eclass)
Definition: pathnodes.h:983
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1041

◆ pathkeys_contained_in()

◆ pathkeys_count_contained_in()

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

Definition at line 343 of file pathkeys.c.

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

Referenced by add_paths_to_grouping_rel(), create_ordered_paths(), create_partial_grouping_paths(), gather_grouping_paths(), generate_useful_gather_paths(), and pathkeys_useful_for_ordering().

344 {
345  int n = 0;
346  ListCell *key1,
347  *key2;
348 
349  /*
350  * See if we can avoiding looping through both lists. This optimization
351  * gains us several percent in planning time in a worst-case test.
352  */
353  if (keys1 == keys2)
354  {
355  *n_common = list_length(keys1);
356  return true;
357  }
358  else if (keys1 == NIL)
359  {
360  *n_common = 0;
361  return true;
362  }
363  else if (keys2 == NIL)
364  {
365  *n_common = 0;
366  return false;
367  }
368 
369  /*
370  * If both lists are non-empty, iterate through both to find out how many
371  * items are shared.
372  */
373  forboth(key1, keys1, key2, keys2)
374  {
375  PathKey *pathkey1 = (PathKey *) lfirst(key1);
376  PathKey *pathkey2 = (PathKey *) lfirst(key2);
377 
378  if (pathkey1 != pathkey2)
379  {
380  *n_common = n;
381  return false;
382  }
383  n++;
384  }
385 
386  /* If we ended with a null value, then we've processed the whole list. */
387  *n_common = n;
388  return (key1 == NULL);
389 }
#define NIL
Definition: pg_list.h:65
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:419
#define lfirst(lc)
Definition: pg_list.h:190
static int list_length(const List *l)
Definition: pg_list.h:169

◆ pathkeys_useful_for_merging()

static int pathkeys_useful_for_merging ( PlannerInfo root,
RelOptInfo rel,
List pathkeys 
)
static

Definition at line 1745 of file pathkeys.c.

References eclass_useful_for_merging(), RelOptInfo::has_eclass_joins, i, RelOptInfo::joininfo, RestrictInfo::left_ec, lfirst, RestrictInfo::mergeopfamilies, NIL, PathKey::pk_eclass, RestrictInfo::right_ec, right_merge_direction(), and update_mergeclause_eclasses().

Referenced by truncate_useless_pathkeys().

1746 {
1747  int useful = 0;
1748  ListCell *i;
1749 
1750  foreach(i, pathkeys)
1751  {
1752  PathKey *pathkey = (PathKey *) lfirst(i);
1753  bool matched = false;
1754  ListCell *j;
1755 
1756  /* If "wrong" direction, not useful for merging */
1757  if (!right_merge_direction(root, pathkey))
1758  break;
1759 
1760  /*
1761  * First look into the EquivalenceClass of the pathkey, to see if
1762  * there are any members not yet joined to the rel. If so, it's
1763  * surely possible to generate a mergejoin clause using them.
1764  */
1765  if (rel->has_eclass_joins &&
1766  eclass_useful_for_merging(root, pathkey->pk_eclass, rel))
1767  matched = true;
1768  else
1769  {
1770  /*
1771  * Otherwise search the rel's joininfo list, which contains
1772  * non-EquivalenceClass-derivable join clauses that might
1773  * nonetheless be mergejoinable.
1774  */
1775  foreach(j, rel->joininfo)
1776  {
1777  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
1778 
1779  if (restrictinfo->mergeopfamilies == NIL)
1780  continue;
1781  update_mergeclause_eclasses(root, restrictinfo);
1782 
1783  if (pathkey->pk_eclass == restrictinfo->left_ec ||
1784  pathkey->pk_eclass == restrictinfo->right_ec)
1785  {
1786  matched = true;
1787  break;
1788  }
1789  }
1790  }
1791 
1792  /*
1793  * If we didn't find a mergeclause, we're done --- any additional
1794  * sort-key positions in the pathkeys are useless. (But we can still
1795  * mergejoin if we found at least one mergeclause.)
1796  */
1797  if (matched)
1798  useful++;
1799  else
1800  break;
1801  }
1802 
1803  return useful;
1804 }
bool has_eclass_joins
Definition: pathnodes.h:733
#define NIL
Definition: pg_list.h:65
bool eclass_useful_for_merging(PlannerInfo *root, EquivalenceClass *eclass, RelOptInfo *rel)
Definition: equivclass.c:2766
EquivalenceClass * right_ec
Definition: pathnodes.h:2034
List * mergeopfamilies
Definition: pathnodes.h:2030
List * joininfo
Definition: pathnodes.h:731
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1041
EquivalenceClass * left_ec
Definition: pathnodes.h:2033
int i
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1228
static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey)
Definition: pathkeys.c:1812

◆ pathkeys_useful_for_ordering()

static int pathkeys_useful_for_ordering ( PlannerInfo root,
List pathkeys 
)
static

Definition at line 1849 of file pathkeys.c.

References NIL, pathkeys_count_contained_in(), and PlannerInfo::query_pathkeys.

Referenced by truncate_useless_pathkeys().

1850 {
1851  int n_common_pathkeys;
1852 
1853  if (root->query_pathkeys == NIL)
1854  return 0; /* no special ordering requested */
1855 
1856  if (pathkeys == NIL)
1857  return 0; /* unordered path */
1858 
1859  (void) pathkeys_count_contained_in(root->query_pathkeys, pathkeys,
1860  &n_common_pathkeys);
1861 
1862  return n_common_pathkeys;
1863 }
#define NIL
Definition: pg_list.h:65
List * query_pathkeys
Definition: pathnodes.h:298
bool pathkeys_count_contained_in(List *keys1, List *keys2, int *n_common)
Definition: pathkeys.c:343

◆ right_merge_direction()

static bool right_merge_direction ( PlannerInfo root,
PathKey pathkey 
)
static

Definition at line 1812 of file pathkeys.c.

References BTLessStrategyNumber, lfirst, PathKey::pk_eclass, PathKey::pk_opfamily, PathKey::pk_strategy, and PlannerInfo::query_pathkeys.

Referenced by pathkeys_useful_for_merging().

1813 {
1814  ListCell *l;
1815 
1816  foreach(l, root->query_pathkeys)
1817  {
1818  PathKey *query_pathkey = (PathKey *) lfirst(l);
1819 
1820  if (pathkey->pk_eclass == query_pathkey->pk_eclass &&
1821  pathkey->pk_opfamily == query_pathkey->pk_opfamily)
1822  {
1823  /*
1824  * Found a matching query sort column. Prefer this pathkey's
1825  * direction iff it matches. Note that we ignore pk_nulls_first,
1826  * which means that a sort might be needed anyway ... but we still
1827  * want to prefer only one of the two possible directions, and we
1828  * might as well use this one.
1829  */
1830  return (pathkey->pk_strategy == query_pathkey->pk_strategy);
1831  }
1832  }
1833 
1834  /* If no matching ORDER BY request, prefer the ASC direction */
1835  return (pathkey->pk_strategy == BTLessStrategyNumber);
1836 }
List * query_pathkeys
Definition: pathnodes.h:298
int pk_strategy
Definition: pathnodes.h:1043
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1041
Oid pk_opfamily
Definition: pathnodes.h:1042
#define BTLessStrategyNumber
Definition: stratnum.h:29

◆ select_outer_pathkeys_for_merge()

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

Definition at line 1375 of file pathkeys.c.

References Assert, bms_overlap(), BTLessStrategyNumber, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, lappend(), RestrictInfo::left_ec, lfirst, linitial_oid, list_copy(), list_length(), make_canonical_pathkey(), NIL, RestrictInfo::outer_is_left, palloc(), pathkey_is_redundant(), pfree(), PathKey::pk_eclass, PlannerInfo::query_pathkeys, RelOptInfo::relids, RestrictInfo::right_ec, and update_mergeclause_eclasses().

Referenced by sort_inner_and_outer().

1378 {
1379  List *pathkeys = NIL;
1380  int nClauses = list_length(mergeclauses);
1381  EquivalenceClass **ecs;
1382  int *scores;
1383  int necs;
1384  ListCell *lc;
1385  int j;
1386 
1387  /* Might have no mergeclauses */
1388  if (nClauses == 0)
1389  return NIL;
1390 
1391  /*
1392  * Make arrays of the ECs used by the mergeclauses (dropping any
1393  * duplicates) and their "popularity" scores.
1394  */
1395  ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
1396  scores = (int *) palloc(nClauses * sizeof(int));
1397  necs = 0;
1398 
1399  foreach(lc, mergeclauses)
1400  {
1401  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1402  EquivalenceClass *oeclass;
1403  int score;
1404  ListCell *lc2;
1405 
1406  /* get the outer eclass */
1407  update_mergeclause_eclasses(root, rinfo);
1408 
1409  if (rinfo->outer_is_left)
1410  oeclass = rinfo->left_ec;
1411  else
1412  oeclass = rinfo->right_ec;
1413 
1414  /* reject duplicates */
1415  for (j = 0; j < necs; j++)
1416  {
1417  if (ecs[j] == oeclass)
1418  break;
1419  }
1420  if (j < necs)
1421  continue;
1422 
1423  /* compute score */
1424  score = 0;
1425  foreach(lc2, oeclass->ec_members)
1426  {
1428 
1429  /* Potential future join partner? */
1430  if (!em->em_is_const && !em->em_is_child &&
1431  !bms_overlap(em->em_relids, joinrel->relids))
1432  score++;
1433  }
1434 
1435  ecs[necs] = oeclass;
1436  scores[necs] = score;
1437  necs++;
1438  }
1439 
1440  /*
1441  * Find out if we have all the ECs mentioned in query_pathkeys; if so we
1442  * can generate a sort order that's also useful for final output. There is
1443  * no percentage in a partial match, though, so we have to have 'em all.
1444  */
1445  if (root->query_pathkeys)
1446  {
1447  foreach(lc, root->query_pathkeys)
1448  {
1449  PathKey *query_pathkey = (PathKey *) lfirst(lc);
1450  EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1451 
1452  for (j = 0; j < necs; j++)
1453  {
1454  if (ecs[j] == query_ec)
1455  break; /* found match */
1456  }
1457  if (j >= necs)
1458  break; /* didn't find match */
1459  }
1460  /* if we got to the end of the list, we have them all */
1461  if (lc == NULL)
1462  {
1463  /* copy query_pathkeys as starting point for our output */
1464  pathkeys = list_copy(root->query_pathkeys);
1465  /* mark their ECs as already-emitted */
1466  foreach(lc, root->query_pathkeys)
1467  {
1468  PathKey *query_pathkey = (PathKey *) lfirst(lc);
1469  EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1470 
1471  for (j = 0; j < necs; j++)
1472  {
1473  if (ecs[j] == query_ec)
1474  {
1475  scores[j] = -1;
1476  break;
1477  }
1478  }
1479  }
1480  }
1481  }
1482 
1483  /*
1484  * Add remaining ECs to the list in popularity order, using a default sort
1485  * ordering. (We could use qsort() here, but the list length is usually
1486  * so small it's not worth it.)
1487  */
1488  for (;;)
1489  {
1490  int best_j;
1491  int best_score;
1492  EquivalenceClass *ec;
1493  PathKey *pathkey;
1494 
1495  best_j = 0;
1496  best_score = scores[0];
1497  for (j = 1; j < necs; j++)
1498  {
1499  if (scores[j] > best_score)
1500  {
1501  best_j = j;
1502  best_score = scores[j];
1503  }
1504  }
1505  if (best_score < 0)
1506  break; /* all done */
1507  ec = ecs[best_j];
1508  scores[best_j] = -1;
1509  pathkey = make_canonical_pathkey(root,
1510  ec,
1513  false);
1514  /* can't be redundant because no duplicate ECs */
1515  Assert(!pathkey_is_redundant(pathkey, pathkeys));
1516  pathkeys = lappend(pathkeys, pathkey);
1517  }
1518 
1519  pfree(ecs);
1520  pfree(scores);
1521 
1522  return pathkeys;
1523 }
#define NIL
Definition: pg_list.h:65
List * query_pathkeys
Definition: pathnodes.h:298
List * list_copy(const List *oldlist)
Definition: list.c:1403
PathKey * make_canonical_pathkey(PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
Definition: pathkeys.c:54
EquivalenceClass * right_ec
Definition: pathnodes.h:2034
void pfree(void *pointer)
Definition: mcxt.c:1056
bool outer_is_left
Definition: pathnodes.h:2040
Relids relids
Definition: pathnodes.h:665
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:135
List * lappend(List *list, void *datum)
Definition: list.c:321
List * ec_opfamilies
Definition: pathnodes.h:962
#define Assert(condition)
Definition: c.h:738
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1041
#define linitial_oid(l)
Definition: pg_list.h:197
static int list_length(const List *l)
Definition: pg_list.h:169
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:494
void * palloc(Size size)
Definition: mcxt.c:949
EquivalenceClass * left_ec
Definition: pathnodes.h:2033
#define BTLessStrategyNumber
Definition: stratnum.h:29
Definition: pg_list.h:50
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1228
List * ec_members
Definition: pathnodes.h:964

◆ trim_mergeclauses_for_inner_pathkeys()

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

Definition at line 1650 of file pathkeys.c.

References i, lappend(), RestrictInfo::left_ec, lfirst, list_head(), lnext(), NIL, RestrictInfo::outer_is_left, PathKey::pk_eclass, and RestrictInfo::right_ec.

Referenced by generate_mergejoin_paths().

1653 {
1654  List *new_mergeclauses = NIL;
1655  PathKey *pathkey;
1656  EquivalenceClass *pathkey_ec;
1657  bool matched_pathkey;
1658  ListCell *lip;
1659  ListCell *i;
1660 
1661  /* No pathkeys => no mergeclauses (though we don't expect this case) */
1662  if (pathkeys == NIL)
1663  return NIL;
1664  /* Initialize to consider first pathkey */
1665  lip = list_head(pathkeys);
1666  pathkey = (PathKey *) lfirst(lip);
1667  pathkey_ec = pathkey->pk_eclass;
1668  lip = lnext(pathkeys, lip);
1669  matched_pathkey = false;
1670 
1671  /* Scan mergeclauses to see how many we can use */
1672  foreach(i, mergeclauses)
1673  {
1674  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1675  EquivalenceClass *clause_ec;
1676 
1677  /* Assume we needn't do update_mergeclause_eclasses again here */
1678 
1679  /* Check clause's inner-rel EC against current pathkey */
1680  clause_ec = rinfo->outer_is_left ?
1681  rinfo->right_ec : rinfo->left_ec;
1682 
1683  /* If we don't have a match, attempt to advance to next pathkey */
1684  if (clause_ec != pathkey_ec)
1685  {
1686  /* If we had no clauses matching this inner pathkey, must stop */
1687  if (!matched_pathkey)
1688  break;
1689 
1690  /* Advance to next inner pathkey, if any */
1691  if (lip == NULL)
1692  break;
1693  pathkey = (PathKey *) lfirst(lip);
1694  pathkey_ec = pathkey->pk_eclass;
1695  lip = lnext(pathkeys, lip);
1696  matched_pathkey = false;
1697  }
1698 
1699  /* If mergeclause matches current inner pathkey, we can use it */
1700  if (clause_ec == pathkey_ec)
1701  {
1702  new_mergeclauses = lappend(new_mergeclauses, rinfo);
1703  matched_pathkey = true;
1704  }
1705  else
1706  {
1707  /* Else, no hope of adding any more mergeclauses */
1708  break;
1709  }
1710  }
1711 
1712  return new_mergeclauses;
1713 }
#define NIL
Definition: pg_list.h:65
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:321
EquivalenceClass * right_ec
Definition: pathnodes.h:2034
bool outer_is_left
Definition: pathnodes.h:2040
static ListCell * list_head(const List *l)
Definition: pg_list.h:125
List * lappend(List *list, void *datum)
Definition: list.c:321
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1041
EquivalenceClass * left_ec
Definition: pathnodes.h:2033
int i
Definition: pg_list.h:50

◆ truncate_useless_pathkeys()

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

Definition at line 1870 of file pathkeys.c.

References list_copy(), list_length(), list_truncate(), NIL, pathkeys_useful_for_merging(), and pathkeys_useful_for_ordering().

Referenced by build_index_paths(), and build_join_pathkeys().

1873 {
1874  int nuseful;
1875  int nuseful2;
1876 
1877  nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
1878  nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
1879  if (nuseful2 > nuseful)
1880  nuseful = nuseful2;
1881 
1882  /*
1883  * Note: not safe to modify input list destructively, but we can avoid
1884  * copying the list if we're not actually going to change it
1885  */
1886  if (nuseful == 0)
1887  return NIL;
1888  else if (nuseful == list_length(pathkeys))
1889  return pathkeys;
1890  else
1891  return list_truncate(list_copy(pathkeys), nuseful);
1892 }
#define NIL
Definition: pg_list.h:65
List * list_truncate(List *list, int new_size)
Definition: list.c:585
List * list_copy(const List *oldlist)
Definition: list.c:1403
static int pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:1849
static int list_length(const List *l)
Definition: pg_list.h:169
static int pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:1745

◆ update_mergeclause_eclasses()

void update_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1228 of file pathkeys.c.

References Assert, EquivalenceClass::ec_merged, RestrictInfo::left_ec, RestrictInfo::mergeopfamilies, NIL, and RestrictInfo::right_ec.

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

1229 {
1230  /* Should be a merge clause ... */
1231  Assert(restrictinfo->mergeopfamilies != NIL);
1232  /* ... with pointers already set */
1233  Assert(restrictinfo->left_ec != NULL);
1234  Assert(restrictinfo->right_ec != NULL);
1235 
1236  /* Chase up to the top as needed */
1237  while (restrictinfo->left_ec->ec_merged)
1238  restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
1239  while (restrictinfo->right_ec->ec_merged)
1240  restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
1241 }
#define NIL
Definition: pg_list.h:65
EquivalenceClass * right_ec
Definition: pathnodes.h:2034
List * mergeopfamilies
Definition: pathnodes.h:2030
#define Assert(condition)
Definition: c.h:738
EquivalenceClass * left_ec
Definition: pathnodes.h:2033
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:976