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

734 {
735  List *pathkeys;
736  Oid opfamily,
737  opcintype;
738  int16 strategy;
739  PathKey *cpathkey;
740 
741  /* Find the operator in pg_amop --- failure shouldn't happen */
742  if (!get_ordering_op_properties(opno,
743  &opfamily, &opcintype, &strategy))
744  elog(ERROR, "operator %u is not a valid ordering operator",
745  opno);
746 
747  cpathkey = make_pathkey_from_sortinfo(root,
748  expr,
749  nullable_relids,
750  opfamily,
751  opcintype,
752  exprCollation((Node *) expr),
753  (strategy == BTGreaterStrategyNumber),
754  (strategy == BTGreaterStrategyNumber),
755  0,
756  rel,
757  create_it);
758 
759  if (cpathkey)
760  pathkeys = list_make1(cpathkey);
761  else
762  pathkeys = NIL;
763 
764  return pathkeys;
765 }
signed short int16
Definition: c.h:345
#define NIL
Definition: pg_list.h:65
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
Definition: nodes.h:525
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:204
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:720
#define elog(elevel,...)
Definition: elog.h:226
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 469 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().

472 {
473  List *retval = NIL;
474  ListCell *lc;
475  int i;
476 
477  if (index->sortopfamily == NULL)
478  return NIL; /* non-orderable index */
479 
480  i = 0;
481  foreach(lc, index->indextlist)
482  {
483  TargetEntry *indextle = (TargetEntry *) lfirst(lc);
484  Expr *indexkey;
485  bool reverse_sort;
486  bool nulls_first;
487  PathKey *cpathkey;
488 
489  /*
490  * INCLUDE columns are stored in index unordered, so they don't
491  * support ordered index scan.
492  */
493  if (i >= index->nkeycolumns)
494  break;
495 
496  /* We assume we don't need to make a copy of the tlist item */
497  indexkey = indextle->expr;
498 
499  if (ScanDirectionIsBackward(scandir))
500  {
501  reverse_sort = !index->reverse_sort[i];
502  nulls_first = !index->nulls_first[i];
503  }
504  else
505  {
506  reverse_sort = index->reverse_sort[i];
507  nulls_first = index->nulls_first[i];
508  }
509 
510  /*
511  * OK, try to make a canonical pathkey for this sort key. Note we're
512  * underneath any outer joins, so nullable_relids should be NULL.
513  */
514  cpathkey = make_pathkey_from_sortinfo(root,
515  indexkey,
516  NULL,
517  index->sortopfamily[i],
518  index->opcintype[i],
519  index->indexcollations[i],
520  reverse_sort,
521  nulls_first,
522  0,
523  index->rel->relids,
524  false);
525 
526  if (cpathkey)
527  {
528  /*
529  * We found the sort key in an EquivalenceClass, so it's relevant
530  * for this query. Add it to list, unless it's redundant.
531  */
532  if (!pathkey_is_redundant(cpathkey, retval))
533  retval = lappend(retval, cpathkey);
534  }
535  else
536  {
537  /*
538  * Boolean index keys might be redundant even if they do not
539  * appear in an EquivalenceClass, because of our special treatment
540  * of boolean equality conditions --- see the comment for
541  * indexcol_is_bool_constant_for_query(). If that applies, we can
542  * continue to examine lower-order index columns. Otherwise, the
543  * sort key is not an interesting sort order for this query, so we
544  * should stop considering index columns; any lower-order sort
545  * keys won't be useful either.
546  */
548  break;
549  }
550 
551  i++;
552  }
553 
554  return retval;
555 }
#define NIL
Definition: pg_list.h:65
Oid * indexcollations
Definition: pathnodes.h:803
List * indextlist
Definition: pathnodes.h:816
Oid * sortopfamily
Definition: pathnodes.h:806
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
RelOptInfo * rel
Definition: pathnodes.h:791
Relids relids
Definition: pathnodes.h:641
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:135
List * lappend(List *list, void *datum)
Definition: list.c:322
#define lfirst(lc)
Definition: pg_list.h:190
Expr * expr
Definition: primnodes.h:1393
int nkeycolumns
Definition: pathnodes.h:800
Oid * opcintype
Definition: pathnodes.h:805
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:808
bool * reverse_sort
Definition: pathnodes.h:807
Definition: pg_list.h:50

◆ build_join_pathkeys()

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

Definition at line 1028 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().

1032 {
1033  if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
1034  return NIL;
1035 
1036  /*
1037  * This used to be quite a complex bit of code, but now that all pathkey
1038  * sublists start out life canonicalized, we don't have to do a darn thing
1039  * here!
1040  *
1041  * We do, however, need to truncate the pathkeys list, since it may
1042  * contain pathkeys that were useful for forming this joinrel but are
1043  * uninteresting to higher levels.
1044  */
1045  return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
1046 }
#define NIL
Definition: pg_list.h:65
List * truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
Definition: pathkeys.c:1816

◆ build_partition_pathkeys()

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

Definition at line 645 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().

647 {
648  List *retval = NIL;
649  PartitionScheme partscheme = partrel->part_scheme;
650  int i;
651 
652  Assert(partscheme != NULL);
653  Assert(partitions_are_ordered(partrel->boundinfo, partrel->nparts));
654  /* For now, we can only cope with baserels */
655  Assert(IS_SIMPLE_REL(partrel));
656 
657  for (i = 0; i < partscheme->partnatts; i++)
658  {
659  PathKey *cpathkey;
660  Expr *keyCol = (Expr *) linitial(partrel->partexprs[i]);
661 
662  /*
663  * Try to make a canonical pathkey for this partkey.
664  *
665  * We're considering a baserel scan, so nullable_relids should be
666  * NULL. Also, we assume the PartitionDesc lists any NULL partition
667  * last, so we treat the scan like a NULLS LAST index: we have
668  * nulls_first for backwards scan only.
669  */
670  cpathkey = make_pathkey_from_sortinfo(root,
671  keyCol,
672  NULL,
673  partscheme->partopfamily[i],
674  partscheme->partopcintype[i],
675  partscheme->partcollation[i],
676  ScanDirectionIsBackward(scandir),
677  ScanDirectionIsBackward(scandir),
678  0,
679  partrel->relids,
680  false);
681 
682 
683  if (cpathkey)
684  {
685  /*
686  * We found the sort key in an EquivalenceClass, so it's relevant
687  * for this query. Add it to list, unless it's redundant.
688  */
689  if (!pathkey_is_redundant(cpathkey, retval))
690  retval = lappend(retval, cpathkey);
691  }
692  else
693  {
694  /*
695  * Boolean partition keys might be redundant even if they do not
696  * appear in an EquivalenceClass, because of our special treatment
697  * of boolean equality conditions --- see the comment for
698  * partkey_is_bool_constant_for_query(). If that applies, we can
699  * continue to examine lower-order partition keys. Otherwise, the
700  * sort key is not an interesting sort order for this query, so we
701  * should stop considering partition columns; any lower-order sort
702  * keys won't be useful either.
703  */
704  if (!partkey_is_bool_constant_for_query(partrel, i))
705  {
706  *partialkeys = true;
707  return retval;
708  }
709  }
710  }
711 
712  *partialkeys = false;
713  return retval;
714 }
#define NIL
Definition: pg_list.h:65
static bool partkey_is_bool_constant_for_query(RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:575
#define IS_SIMPLE_REL(rel)
Definition: pathnodes.h:614
#define ScanDirectionIsBackward(direction)
Definition: sdir.h:41
List ** partexprs
Definition: pathnodes.h:724
#define linitial(l)
Definition: pg_list.h:195
int nparts
Definition: pathnodes.h:719
Relids relids
Definition: pathnodes.h:641
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:135
List * lappend(List *list, void *datum)
Definition: list.c:322
struct PartitionBoundInfoData * boundinfo
Definition: pathnodes.h:720
bool partitions_are_ordered(PartitionBoundInfo boundinfo, int nparts)
Definition: partbounds.c:876
#define Assert(condition)
Definition: c.h:732
int i
PartitionScheme part_scheme
Definition: pathnodes.h:718
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 784 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().

787 {
788  List *retval = NIL;
789  int retvallen = 0;
790  int outer_query_keys = list_length(root->query_pathkeys);
791  ListCell *i;
792 
793  foreach(i, subquery_pathkeys)
794  {
795  PathKey *sub_pathkey = (PathKey *) lfirst(i);
796  EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
797  PathKey *best_pathkey = NULL;
798 
799  if (sub_eclass->ec_has_volatile)
800  {
801  /*
802  * If the sub_pathkey's EquivalenceClass is volatile, then it must
803  * have come from an ORDER BY clause, and we have to match it to
804  * that same targetlist entry.
805  */
806  TargetEntry *tle;
807  Var *outer_var;
808 
809  if (sub_eclass->ec_sortref == 0) /* can't happen */
810  elog(ERROR, "volatile EquivalenceClass has no sortref");
811  tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
812  Assert(tle);
813  /* Is TLE actually available to the outer query? */
814  outer_var = find_var_for_subquery_tle(rel, tle);
815  if (outer_var)
816  {
817  /* We can represent this sub_pathkey */
818  EquivalenceMember *sub_member;
819  EquivalenceClass *outer_ec;
820 
821  Assert(list_length(sub_eclass->ec_members) == 1);
822  sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
823 
824  /*
825  * Note: it might look funny to be setting sortref = 0 for a
826  * reference to a volatile sub_eclass. However, the
827  * expression is *not* volatile in the outer query: it's just
828  * a Var referencing whatever the subquery emitted. (IOW, the
829  * outer query isn't going to re-execute the volatile
830  * expression itself.) So this is okay. Likewise, it's
831  * correct to pass nullable_relids = NULL, because we're
832  * underneath any outer joins appearing in the outer query.
833  */
834  outer_ec =
836  (Expr *) outer_var,
837  NULL,
838  sub_eclass->ec_opfamilies,
839  sub_member->em_datatype,
840  sub_eclass->ec_collation,
841  0,
842  rel->relids,
843  false);
844 
845  /*
846  * If we don't find a matching EC, sub-pathkey isn't
847  * interesting to the outer query
848  */
849  if (outer_ec)
850  best_pathkey =
852  outer_ec,
853  sub_pathkey->pk_opfamily,
854  sub_pathkey->pk_strategy,
855  sub_pathkey->pk_nulls_first);
856  }
857  }
858  else
859  {
860  /*
861  * Otherwise, the sub_pathkey's EquivalenceClass could contain
862  * multiple elements (representing knowledge that multiple items
863  * are effectively equal). Each element might match none, one, or
864  * more of the output columns that are visible to the outer query.
865  * This means we may have multiple possible representations of the
866  * sub_pathkey in the context of the outer query. Ideally we
867  * would generate them all and put them all into an EC of the
868  * outer query, thereby propagating equality knowledge up to the
869  * outer query. Right now we cannot do so, because the outer
870  * query's EquivalenceClasses are already frozen when this is
871  * called. Instead we prefer the one that has the highest "score"
872  * (number of EC peers, plus one if it matches the outer
873  * query_pathkeys). This is the most likely to be useful in the
874  * outer query.
875  */
876  int best_score = -1;
877  ListCell *j;
878 
879  foreach(j, sub_eclass->ec_members)
880  {
881  EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
882  Expr *sub_expr = sub_member->em_expr;
883  Oid sub_expr_type = sub_member->em_datatype;
884  Oid sub_expr_coll = sub_eclass->ec_collation;
885  ListCell *k;
886 
887  if (sub_member->em_is_child)
888  continue; /* ignore children here */
889 
890  foreach(k, subquery_tlist)
891  {
892  TargetEntry *tle = (TargetEntry *) lfirst(k);
893  Var *outer_var;
894  Expr *tle_expr;
895  EquivalenceClass *outer_ec;
896  PathKey *outer_pk;
897  int score;
898 
899  /* Is TLE actually available to the outer query? */
900  outer_var = find_var_for_subquery_tle(rel, tle);
901  if (!outer_var)
902  continue;
903 
904  /*
905  * The targetlist entry is considered to match if it
906  * matches after sort-key canonicalization. That is
907  * needed since the sub_expr has been through the same
908  * process.
909  */
910  tle_expr = canonicalize_ec_expression(tle->expr,
911  sub_expr_type,
912  sub_expr_coll);
913  if (!equal(tle_expr, sub_expr))
914  continue;
915 
916  /* See if we have a matching EC for the TLE */
917  outer_ec = get_eclass_for_sort_expr(root,
918  (Expr *) outer_var,
919  NULL,
920  sub_eclass->ec_opfamilies,
921  sub_expr_type,
922  sub_expr_coll,
923  0,
924  rel->relids,
925  false);
926 
927  /*
928  * If we don't find a matching EC, this sub-pathkey isn't
929  * interesting to the outer query
930  */
931  if (!outer_ec)
932  continue;
933 
934  outer_pk = make_canonical_pathkey(root,
935  outer_ec,
936  sub_pathkey->pk_opfamily,
937  sub_pathkey->pk_strategy,
938  sub_pathkey->pk_nulls_first);
939  /* score = # of equivalence peers */
940  score = list_length(outer_ec->ec_members) - 1;
941  /* +1 if it matches the proper query_pathkeys item */
942  if (retvallen < outer_query_keys &&
943  list_nth(root->query_pathkeys, retvallen) == outer_pk)
944  score++;
945  if (score > best_score)
946  {
947  best_pathkey = outer_pk;
948  best_score = score;
949  }
950  }
951  }
952  }
953 
954  /*
955  * If we couldn't find a representation of this sub_pathkey, we're
956  * done (we can't use the ones to its right, either).
957  */
958  if (!best_pathkey)
959  break;
960 
961  /*
962  * Eliminate redundant ordering info; could happen if outer query
963  * equivalences subquery keys...
964  */
965  if (!pathkey_is_redundant(best_pathkey, retval))
966  {
967  retval = lappend(retval, best_pathkey);
968  retvallen++;
969  }
970  }
971 
972  return retval;
973 }
#define NIL
Definition: pg_list.h:65
List * query_pathkeys
Definition: pathnodes.h:296
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3008
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:167
int pk_strategy
Definition: pathnodes.h:1013
#define linitial(l)
Definition: pg_list.h:195
bool pk_nulls_first
Definition: pathnodes.h:1014
#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:641
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:985
List * lappend(List *list, void *datum)
Definition: list.c:322
List * ec_opfamilies
Definition: pathnodes.h:932
#define Assert(condition)
Definition: c.h:732
#define lfirst(lc)
Definition: pg_list.h:190
Expr * expr
Definition: primnodes.h:1393
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1011
static int list_length(const List *l)
Definition: pg_list.h:169
bool ec_has_volatile
Definition: pathnodes.h:940
Oid pk_opfamily
Definition: pathnodes.h:1012
#define elog(elevel,...)
Definition: elog.h:226
int i
Definition: pg_list.h:50
List * ec_members
Definition: pathnodes.h:934

◆ find_mergeclauses_for_outer_pathkeys()

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

Definition at line 1208 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().

1211 {
1212  List *mergeclauses = NIL;
1213  ListCell *i;
1214 
1215  /* make sure we have eclasses cached in the clauses */
1216  foreach(i, restrictinfos)
1217  {
1218  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1219 
1220  update_mergeclause_eclasses(root, rinfo);
1221  }
1222 
1223  foreach(i, pathkeys)
1224  {
1225  PathKey *pathkey = (PathKey *) lfirst(i);
1226  EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
1227  List *matched_restrictinfos = NIL;
1228  ListCell *j;
1229 
1230  /*----------
1231  * A mergejoin clause matches a pathkey if it has the same EC.
1232  * If there are multiple matching clauses, take them all. In plain
1233  * inner-join scenarios we expect only one match, because
1234  * equivalence-class processing will have removed any redundant
1235  * mergeclauses. However, in outer-join scenarios there might be
1236  * multiple matches. An example is
1237  *
1238  * select * from a full join b
1239  * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
1240  *
1241  * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
1242  * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
1243  * we *must* do so or we will be unable to form a valid plan.
1244  *
1245  * We expect that the given pathkeys list is canonical, which means
1246  * no two members have the same EC, so it's not possible for this
1247  * code to enter the same mergeclause into the result list twice.
1248  *
1249  * It's possible that multiple matching clauses might have different
1250  * ECs on the other side, in which case the order we put them into our
1251  * result makes a difference in the pathkeys required for the inner
1252  * input rel. However this routine hasn't got any info about which
1253  * order would be best, so we don't worry about that.
1254  *
1255  * It's also possible that the selected mergejoin clauses produce
1256  * a noncanonical ordering of pathkeys for the inner side, ie, we
1257  * might select clauses that reference b.v1, b.v2, b.v1 in that
1258  * order. This is not harmful in itself, though it suggests that
1259  * the clauses are partially redundant. Since the alternative is
1260  * to omit mergejoin clauses and thereby possibly fail to generate a
1261  * plan altogether, we live with it. make_inner_pathkeys_for_merge()
1262  * has to delete duplicates when it constructs the inner pathkeys
1263  * list, and we also have to deal with such cases specially in
1264  * create_mergejoin_plan().
1265  *----------
1266  */
1267  foreach(j, restrictinfos)
1268  {
1269  RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
1270  EquivalenceClass *clause_ec;
1271 
1272  clause_ec = rinfo->outer_is_left ?
1273  rinfo->left_ec : rinfo->right_ec;
1274  if (clause_ec == pathkey_ec)
1275  matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
1276  }
1277 
1278  /*
1279  * If we didn't find a mergeclause, we're done --- any additional
1280  * sort-key positions in the pathkeys are useless. (But we can still
1281  * mergejoin if we found at least one mergeclause.)
1282  */
1283  if (matched_restrictinfos == NIL)
1284  break;
1285 
1286  /*
1287  * If we did find usable mergeclause(s) for this sort-key position,
1288  * add them to result list.
1289  */
1290  mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
1291  }
1292 
1293  return mergeclauses;
1294 }
#define NIL
Definition: pg_list.h:65
List * list_concat(List *list1, const List *list2)
Definition: list.c:516
EquivalenceClass * right_ec
Definition: pathnodes.h:1992
bool outer_is_left
Definition: pathnodes.h:1998
List * lappend(List *list, void *datum)
Definition: list.c:322
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1011
EquivalenceClass * left_ec
Definition: pathnodes.h:1991
int i
Definition: pg_list.h:50
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1174

◆ find_var_for_subquery_tle()

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

Definition at line 985 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().

986 {
987  ListCell *lc;
988 
989  /* If the TLE is resjunk, it's certainly not visible to the outer query */
990  if (tle->resjunk)
991  return NULL;
992 
993  /* Search the rel's targetlist to see what it will return */
994  foreach(lc, rel->reltarget->exprs)
995  {
996  Var *var = (Var *) lfirst(lc);
997 
998  /* Ignore placeholders */
999  if (!IsA(var, Var))
1000  continue;
1001  Assert(var->varno == rel->relid);
1002 
1003  /* If we find a Var referencing this TLE, we're good */
1004  if (var->varattno == tle->resno)
1005  return copyObject(var); /* Make a copy for safety */
1006  }
1007  return NULL;
1008 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:576
AttrNumber varattno
Definition: primnodes.h:172
Definition: primnodes.h:167
bool resjunk
Definition: primnodes.h:1400
AttrNumber resno
Definition: primnodes.h:1394
Index relid
Definition: pathnodes.h:669
Index varno
Definition: primnodes.h:170
List * exprs
Definition: pathnodes.h:1044
#define Assert(condition)
Definition: c.h:732
#define lfirst(lc)
Definition: pg_list.h:190
#define copyObject(obj)
Definition: nodes.h:641
struct PathTarget * reltarget
Definition: pathnodes.h:652

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

399 {
400  Path *matched_path = NULL;
401  ListCell *l;
402 
403  foreach(l, paths)
404  {
405  Path *path = (Path *) lfirst(l);
406 
407  /*
408  * Since cost comparison is a lot cheaper than pathkey comparison, do
409  * that first. (XXX is that still true?)
410  */
411  if (matched_path != NULL &&
412  compare_fractional_path_costs(matched_path, path, fraction) <= 0)
413  continue;
414 
415  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
416  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
417  matched_path = path;
418  }
419  return matched_path;
420 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1133
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:324
List * pathkeys
Definition: pathnodes.h:1128
#define lfirst(lc)
Definition: pg_list.h:190
int compare_fractional_path_costs(Path *path1, Path *path2, double fraction)
Definition: pathnode.c:118

◆ get_cheapest_parallel_safe_total_inner()

Path* get_cheapest_parallel_safe_total_inner ( List paths)

Definition at line 428 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().

429 {
430  ListCell *l;
431 
432  foreach(l, paths)
433  {
434  Path *innerpath = (Path *) lfirst(l);
435 
436  if (innerpath->parallel_safe &&
437  bms_is_empty(PATH_REQ_OUTER(innerpath)))
438  return innerpath;
439  }
440 
441  return NULL;
442 }
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1133
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:1120

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

354 {
355  Path *matched_path = NULL;
356  ListCell *l;
357 
358  foreach(l, paths)
359  {
360  Path *path = (Path *) lfirst(l);
361 
362  /*
363  * Since cost comparison is a lot cheaper than pathkey comparison, do
364  * that first. (XXX is that still true?)
365  */
366  if (matched_path != NULL &&
367  compare_path_costs(matched_path, path, cost_criterion) <= 0)
368  continue;
369 
370  if (require_parallel_safe && !path->parallel_safe)
371  continue;
372 
373  if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
374  bms_is_subset(PATH_REQ_OUTER(path), required_outer))
375  matched_path = path;
376  }
377  return matched_path;
378 }
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:72
#define PATH_REQ_OUTER(path)
Definition: pathnodes.h:1133
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:324
List * pathkeys
Definition: pathnodes.h:1128
#define lfirst(lc)
Definition: pg_list.h:190
bool parallel_safe
Definition: pathnodes.h:1120

◆ has_useful_pathkeys()

bool has_useful_pathkeys ( PlannerInfo root,
RelOptInfo rel 
)

Definition at line 1856 of file pathkeys.c.

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

Referenced by build_index_paths(), and set_append_rel_size().

1857 {
1858  if (rel->joininfo != NIL || rel->has_eclass_joins)
1859  return true; /* might be able to use pathkeys for merging */
1860  if (root->query_pathkeys != NIL)
1861  return true; /* might be able to use them for ordering */
1862  return false; /* definitely useless */
1863 }
bool has_eclass_joins
Definition: pathnodes.h:709
#define NIL
Definition: pg_list.h:65
List * query_pathkeys
Definition: pathnodes.h:296
List * joininfo
Definition: pathnodes.h:707

◆ initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1125 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().

1126 {
1127  Expr *clause = restrictinfo->clause;
1128  Oid lefttype,
1129  righttype;
1130 
1131  /* Should be a mergeclause ... */
1132  Assert(restrictinfo->mergeopfamilies != NIL);
1133  /* ... with links not yet set */
1134  Assert(restrictinfo->left_ec == NULL);
1135  Assert(restrictinfo->right_ec == NULL);
1136 
1137  /* Need the declared input types of the operator */
1138  op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
1139 
1140  /* Find or create a matching EquivalenceClass for each side */
1141  restrictinfo->left_ec =
1143  (Expr *) get_leftop(clause),
1144  restrictinfo->nullable_relids,
1145  restrictinfo->mergeopfamilies,
1146  lefttype,
1147  ((OpExpr *) clause)->inputcollid,
1148  0,
1149  NULL,
1150  true);
1151  restrictinfo->right_ec =
1153  (Expr *) get_rightop(clause),
1154  restrictinfo->nullable_relids,
1155  restrictinfo->mergeopfamilies,
1156  righttype,
1157  ((OpExpr *) clause)->inputcollid,
1158  0,
1159  NULL,
1160  true);
1161 }
#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:1992
unsigned int Oid
Definition: postgres_ext.h:31
List * mergeopfamilies
Definition: pathnodes.h:1988
void op_input_types(Oid opno, Oid *lefttype, Oid *righttype)
Definition: lsyscache.c:1165
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:70
Expr * clause
Definition: pathnodes.h:1943
Relids nullable_relids
Definition: pathnodes.h:1967
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:82
#define Assert(condition)
Definition: c.h:732
EquivalenceClass * left_ec
Definition: pathnodes.h:1991

◆ 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:266
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
int pk_strategy
Definition: pathnodes.h:1013
static struct cvec * eclass(struct vars *v, chr c, int cases)
Definition: regc_locale.c:508
bool pk_nulls_first
Definition: pathnodes.h:1014
#define ERROR
Definition: elog.h:43
List * canon_pathkeys
Definition: pathnodes.h:268
List * lappend(List *list, void *datum)
Definition: list.c:322
#define makeNode(_type_)
Definition: nodes.h:573
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1011
Oid pk_opfamily
Definition: pathnodes.h:1012
#define elog(elevel,...)
Definition: elog.h:226
MemoryContext planner_cxt
Definition: pathnodes.h:329
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:946

◆ make_inner_pathkeys_for_merge()

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

Definition at line 1493 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().

1496 {
1497  List *pathkeys = NIL;
1498  EquivalenceClass *lastoeclass;
1499  PathKey *opathkey;
1500  ListCell *lc;
1501  ListCell *lop;
1502 
1503  lastoeclass = NULL;
1504  opathkey = NULL;
1505  lop = list_head(outer_pathkeys);
1506 
1507  foreach(lc, mergeclauses)
1508  {
1509  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1510  EquivalenceClass *oeclass;
1511  EquivalenceClass *ieclass;
1512  PathKey *pathkey;
1513 
1514  update_mergeclause_eclasses(root, rinfo);
1515 
1516  if (rinfo->outer_is_left)
1517  {
1518  oeclass = rinfo->left_ec;
1519  ieclass = rinfo->right_ec;
1520  }
1521  else
1522  {
1523  oeclass = rinfo->right_ec;
1524  ieclass = rinfo->left_ec;
1525  }
1526 
1527  /* outer eclass should match current or next pathkeys */
1528  /* we check this carefully for debugging reasons */
1529  if (oeclass != lastoeclass)
1530  {
1531  if (!lop)
1532  elog(ERROR, "too few pathkeys for mergeclauses");
1533  opathkey = (PathKey *) lfirst(lop);
1534  lop = lnext(outer_pathkeys, lop);
1535  lastoeclass = opathkey->pk_eclass;
1536  if (oeclass != lastoeclass)
1537  elog(ERROR, "outer pathkeys do not match mergeclause");
1538  }
1539 
1540  /*
1541  * Often, we'll have same EC on both sides, in which case the outer
1542  * pathkey is also canonical for the inner side, and we can skip a
1543  * useless search.
1544  */
1545  if (ieclass == oeclass)
1546  pathkey = opathkey;
1547  else
1548  pathkey = make_canonical_pathkey(root,
1549  ieclass,
1550  opathkey->pk_opfamily,
1551  opathkey->pk_strategy,
1552  opathkey->pk_nulls_first);
1553 
1554  /*
1555  * Don't generate redundant pathkeys (which can happen if multiple
1556  * mergeclauses refer to the same EC). Because we do this, the output
1557  * pathkey list isn't necessarily ordered like the mergeclauses, which
1558  * complicates life for create_mergejoin_plan(). But if we didn't,
1559  * we'd have a noncanonical sort key list, which would be bad; for one
1560  * reason, it certainly wouldn't match any available sort order for
1561  * the input relation.
1562  */
1563  if (!pathkey_is_redundant(pathkey, pathkeys))
1564  pathkeys = lappend(pathkeys, pathkey);
1565  }
1566 
1567  return pathkeys;
1568 }
#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:1992
int pk_strategy
Definition: pathnodes.h:1013
bool pk_nulls_first
Definition: pathnodes.h:1014
#define ERROR
Definition: elog.h:43
bool outer_is_left
Definition: pathnodes.h:1998
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:322
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1011
Oid pk_opfamily
Definition: pathnodes.h:1012
EquivalenceClass * left_ec
Definition: pathnodes.h:1991
#define elog(elevel,...)
Definition: elog.h:226
Definition: pg_list.h:50
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1174

◆ 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:345
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
List * get_mergejoin_opfamilies(Oid opno)
Definition: lsyscache.c:363
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:638
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:163
#define elog(elevel,...)
Definition: elog.h:226
#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:345
#define BTGreaterStrategyNumber
Definition: stratnum.h:33
Definition: nodes.h:525
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:204
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:720
#define elog(elevel,...)
Definition: elog.h:226
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 1071 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().

1074 {
1075  List *pathkeys = NIL;
1076  ListCell *l;
1077 
1078  foreach(l, sortclauses)
1079  {
1080  SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
1081  Expr *sortkey;
1082  PathKey *pathkey;
1083 
1084  sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
1085  Assert(OidIsValid(sortcl->sortop));
1086  pathkey = make_pathkey_from_sortop(root,
1087  sortkey,
1088  root->nullable_baserels,
1089  sortcl->sortop,
1090  sortcl->nulls_first,
1091  sortcl->tleSortGroupRef,
1092  true);
1093 
1094  /* Canonical form eliminates redundant ordering keys */
1095  if (!pathkey_is_redundant(pathkey, pathkeys))
1096  pathkeys = lappend(pathkeys, pathkey);
1097  }
1098  return pathkeys;
1099 }
#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:1234
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:401
#define OidIsValid(objectId)
Definition: c.h:638
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:135
List * lappend(List *list, void *datum)
Definition: list.c:322
#define Assert(condition)
Definition: c.h:732
#define lfirst(lc)
Definition: pg_list.h:190
Relids nullable_baserels
Definition: pathnodes.h:233
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 610 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().

612 {
613  Node *clause = (Node *) rinfo->clause;
614  Node *partexpr = (Node *) linitial(partrel->partexprs[partkeycol]);
615 
616  /* Direct match? */
617  if (equal(partexpr, clause))
618  return true;
619  /* NOT clause? */
620  else if (is_notclause(clause))
621  {
622  Node *arg = (Node *) get_notclausearg((Expr *) clause);
623 
624  if (equal(partexpr, arg))
625  return true;
626  }
627 
628  return false;
629 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:3008
Definition: nodes.h:525
List ** partexprs
Definition: pathnodes.h:724
#define linitial(l)
Definition: pg_list.h:195
Expr * clause
Definition: pathnodes.h:1943
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 575 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().

576 {
577  PartitionScheme partscheme = partrel->part_scheme;
578  ListCell *lc;
579 
580  /* If the partkey isn't boolean, we can't possibly get a match */
581  if (!IsBooleanOpfamily(partscheme->partopfamily[partkeycol]))
582  return false;
583 
584  /* Check each restriction clause for the partitioned rel */
585  foreach(lc, partrel->baserestrictinfo)
586  {
587  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
588 
589  /* Ignore pseudoconstant quals, they won't match */
590  if (rinfo->pseudoconstant)
591  continue;
592 
593  /* See if we can match the clause's expression to the partkey column */
594  if (matches_boolean_partition_clause(rinfo, partrel, partkeycol))
595  return true;
596  }
597 
598  return false;
599 }
List * baserestrictinfo
Definition: pathnodes.h:703
bool pseudoconstant
Definition: pathnodes.h:1951
static bool matches_boolean_partition_clause(RestrictInfo *rinfo, RelOptInfo *partrel, int partkeycol)
Definition: pathkeys.c:610
#define lfirst(lc)
Definition: pg_list.h:190
PartitionScheme part_scheme
Definition: pathnodes.h:718

◆ 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:953
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1011

◆ pathkeys_contained_in()

◆ pathkeys_useful_for_merging()

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

Definition at line 1691 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().

1692 {
1693  int useful = 0;
1694  ListCell *i;
1695 
1696  foreach(i, pathkeys)
1697  {
1698  PathKey *pathkey = (PathKey *) lfirst(i);
1699  bool matched = false;
1700  ListCell *j;
1701 
1702  /* If "wrong" direction, not useful for merging */
1703  if (!right_merge_direction(root, pathkey))
1704  break;
1705 
1706  /*
1707  * First look into the EquivalenceClass of the pathkey, to see if
1708  * there are any members not yet joined to the rel. If so, it's
1709  * surely possible to generate a mergejoin clause using them.
1710  */
1711  if (rel->has_eclass_joins &&
1712  eclass_useful_for_merging(root, pathkey->pk_eclass, rel))
1713  matched = true;
1714  else
1715  {
1716  /*
1717  * Otherwise search the rel's joininfo list, which contains
1718  * non-EquivalenceClass-derivable join clauses that might
1719  * nonetheless be mergejoinable.
1720  */
1721  foreach(j, rel->joininfo)
1722  {
1723  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
1724 
1725  if (restrictinfo->mergeopfamilies == NIL)
1726  continue;
1727  update_mergeclause_eclasses(root, restrictinfo);
1728 
1729  if (pathkey->pk_eclass == restrictinfo->left_ec ||
1730  pathkey->pk_eclass == restrictinfo->right_ec)
1731  {
1732  matched = true;
1733  break;
1734  }
1735  }
1736  }
1737 
1738  /*
1739  * If we didn't find a mergeclause, we're done --- any additional
1740  * sort-key positions in the pathkeys are useless. (But we can still
1741  * mergejoin if we found at least one mergeclause.)
1742  */
1743  if (matched)
1744  useful++;
1745  else
1746  break;
1747  }
1748 
1749  return useful;
1750 }
bool has_eclass_joins
Definition: pathnodes.h:709
#define NIL
Definition: pg_list.h:65
bool eclass_useful_for_merging(PlannerInfo *root, EquivalenceClass *eclass, RelOptInfo *rel)
Definition: equivclass.c:2603
EquivalenceClass * right_ec
Definition: pathnodes.h:1992
List * mergeopfamilies
Definition: pathnodes.h:1988
List * joininfo
Definition: pathnodes.h:707
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1011
EquivalenceClass * left_ec
Definition: pathnodes.h:1991
int i
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1174
static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey)
Definition: pathkeys.c:1758

◆ pathkeys_useful_for_ordering()

static int pathkeys_useful_for_ordering ( PlannerInfo root,
List pathkeys 
)
static

Definition at line 1794 of file pathkeys.c.

References list_length(), NIL, pathkeys_contained_in(), and PlannerInfo::query_pathkeys.

Referenced by truncate_useless_pathkeys().

1795 {
1796  if (root->query_pathkeys == NIL)
1797  return 0; /* no special ordering requested */
1798 
1799  if (pathkeys == NIL)
1800  return 0; /* unordered path */
1801 
1802  if (pathkeys_contained_in(root->query_pathkeys, pathkeys))
1803  {
1804  /* It's useful ... or at least the first N keys are */
1805  return list_length(root->query_pathkeys);
1806  }
1807 
1808  return 0; /* path ordering not useful */
1809 }
#define NIL
Definition: pg_list.h:65
List * query_pathkeys
Definition: pathnodes.h:296
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:324
static int list_length(const List *l)
Definition: pg_list.h:169

◆ right_merge_direction()

static bool right_merge_direction ( PlannerInfo root,
PathKey pathkey 
)
static

Definition at line 1758 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().

1759 {
1760  ListCell *l;
1761 
1762  foreach(l, root->query_pathkeys)
1763  {
1764  PathKey *query_pathkey = (PathKey *) lfirst(l);
1765 
1766  if (pathkey->pk_eclass == query_pathkey->pk_eclass &&
1767  pathkey->pk_opfamily == query_pathkey->pk_opfamily)
1768  {
1769  /*
1770  * Found a matching query sort column. Prefer this pathkey's
1771  * direction iff it matches. Note that we ignore pk_nulls_first,
1772  * which means that a sort might be needed anyway ... but we still
1773  * want to prefer only one of the two possible directions, and we
1774  * might as well use this one.
1775  */
1776  return (pathkey->pk_strategy == query_pathkey->pk_strategy);
1777  }
1778  }
1779 
1780  /* If no matching ORDER BY request, prefer the ASC direction */
1781  return (pathkey->pk_strategy == BTLessStrategyNumber);
1782 }
List * query_pathkeys
Definition: pathnodes.h:296
int pk_strategy
Definition: pathnodes.h:1013
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1011
Oid pk_opfamily
Definition: pathnodes.h:1012
#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 1321 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().

1324 {
1325  List *pathkeys = NIL;
1326  int nClauses = list_length(mergeclauses);
1327  EquivalenceClass **ecs;
1328  int *scores;
1329  int necs;
1330  ListCell *lc;
1331  int j;
1332 
1333  /* Might have no mergeclauses */
1334  if (nClauses == 0)
1335  return NIL;
1336 
1337  /*
1338  * Make arrays of the ECs used by the mergeclauses (dropping any
1339  * duplicates) and their "popularity" scores.
1340  */
1341  ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
1342  scores = (int *) palloc(nClauses * sizeof(int));
1343  necs = 0;
1344 
1345  foreach(lc, mergeclauses)
1346  {
1347  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1348  EquivalenceClass *oeclass;
1349  int score;
1350  ListCell *lc2;
1351 
1352  /* get the outer eclass */
1353  update_mergeclause_eclasses(root, rinfo);
1354 
1355  if (rinfo->outer_is_left)
1356  oeclass = rinfo->left_ec;
1357  else
1358  oeclass = rinfo->right_ec;
1359 
1360  /* reject duplicates */
1361  for (j = 0; j < necs; j++)
1362  {
1363  if (ecs[j] == oeclass)
1364  break;
1365  }
1366  if (j < necs)
1367  continue;
1368 
1369  /* compute score */
1370  score = 0;
1371  foreach(lc2, oeclass->ec_members)
1372  {
1374 
1375  /* Potential future join partner? */
1376  if (!em->em_is_const && !em->em_is_child &&
1377  !bms_overlap(em->em_relids, joinrel->relids))
1378  score++;
1379  }
1380 
1381  ecs[necs] = oeclass;
1382  scores[necs] = score;
1383  necs++;
1384  }
1385 
1386  /*
1387  * Find out if we have all the ECs mentioned in query_pathkeys; if so we
1388  * can generate a sort order that's also useful for final output. There is
1389  * no percentage in a partial match, though, so we have to have 'em all.
1390  */
1391  if (root->query_pathkeys)
1392  {
1393  foreach(lc, root->query_pathkeys)
1394  {
1395  PathKey *query_pathkey = (PathKey *) lfirst(lc);
1396  EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1397 
1398  for (j = 0; j < necs; j++)
1399  {
1400  if (ecs[j] == query_ec)
1401  break; /* found match */
1402  }
1403  if (j >= necs)
1404  break; /* didn't find match */
1405  }
1406  /* if we got to the end of the list, we have them all */
1407  if (lc == NULL)
1408  {
1409  /* copy query_pathkeys as starting point for our output */
1410  pathkeys = list_copy(root->query_pathkeys);
1411  /* mark their ECs as already-emitted */
1412  foreach(lc, root->query_pathkeys)
1413  {
1414  PathKey *query_pathkey = (PathKey *) lfirst(lc);
1415  EquivalenceClass *query_ec = query_pathkey->pk_eclass;
1416 
1417  for (j = 0; j < necs; j++)
1418  {
1419  if (ecs[j] == query_ec)
1420  {
1421  scores[j] = -1;
1422  break;
1423  }
1424  }
1425  }
1426  }
1427  }
1428 
1429  /*
1430  * Add remaining ECs to the list in popularity order, using a default sort
1431  * ordering. (We could use qsort() here, but the list length is usually
1432  * so small it's not worth it.)
1433  */
1434  for (;;)
1435  {
1436  int best_j;
1437  int best_score;
1438  EquivalenceClass *ec;
1439  PathKey *pathkey;
1440 
1441  best_j = 0;
1442  best_score = scores[0];
1443  for (j = 1; j < necs; j++)
1444  {
1445  if (scores[j] > best_score)
1446  {
1447  best_j = j;
1448  best_score = scores[j];
1449  }
1450  }
1451  if (best_score < 0)
1452  break; /* all done */
1453  ec = ecs[best_j];
1454  scores[best_j] = -1;
1455  pathkey = make_canonical_pathkey(root,
1456  ec,
1459  false);
1460  /* can't be redundant because no duplicate ECs */
1461  Assert(!pathkey_is_redundant(pathkey, pathkeys));
1462  pathkeys = lappend(pathkeys, pathkey);
1463  }
1464 
1465  pfree(ecs);
1466  pfree(scores);
1467 
1468  return pathkeys;
1469 }
#define NIL
Definition: pg_list.h:65
List * query_pathkeys
Definition: pathnodes.h:296
List * list_copy(const List *oldlist)
Definition: list.c:1404
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:1992
void pfree(void *pointer)
Definition: mcxt.c:1056
bool outer_is_left
Definition: pathnodes.h:1998
Relids relids
Definition: pathnodes.h:641
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
Definition: pathkeys.c:135
List * lappend(List *list, void *datum)
Definition: list.c:322
List * ec_opfamilies
Definition: pathnodes.h:932
#define Assert(condition)
Definition: c.h:732
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1011
#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:1991
#define BTLessStrategyNumber
Definition: stratnum.h:29
Definition: pg_list.h:50
void update_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: pathkeys.c:1174
List * ec_members
Definition: pathnodes.h:934

◆ trim_mergeclauses_for_inner_pathkeys()

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

Definition at line 1596 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().

1599 {
1600  List *new_mergeclauses = NIL;
1601  PathKey *pathkey;
1602  EquivalenceClass *pathkey_ec;
1603  bool matched_pathkey;
1604  ListCell *lip;
1605  ListCell *i;
1606 
1607  /* No pathkeys => no mergeclauses (though we don't expect this case) */
1608  if (pathkeys == NIL)
1609  return NIL;
1610  /* Initialize to consider first pathkey */
1611  lip = list_head(pathkeys);
1612  pathkey = (PathKey *) lfirst(lip);
1613  pathkey_ec = pathkey->pk_eclass;
1614  lip = lnext(pathkeys, lip);
1615  matched_pathkey = false;
1616 
1617  /* Scan mergeclauses to see how many we can use */
1618  foreach(i, mergeclauses)
1619  {
1620  RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
1621  EquivalenceClass *clause_ec;
1622 
1623  /* Assume we needn't do update_mergeclause_eclasses again here */
1624 
1625  /* Check clause's inner-rel EC against current pathkey */
1626  clause_ec = rinfo->outer_is_left ?
1627  rinfo->right_ec : rinfo->left_ec;
1628 
1629  /* If we don't have a match, attempt to advance to next pathkey */
1630  if (clause_ec != pathkey_ec)
1631  {
1632  /* If we had no clauses matching this inner pathkey, must stop */
1633  if (!matched_pathkey)
1634  break;
1635 
1636  /* Advance to next inner pathkey, if any */
1637  if (lip == NULL)
1638  break;
1639  pathkey = (PathKey *) lfirst(lip);
1640  pathkey_ec = pathkey->pk_eclass;
1641  lip = lnext(pathkeys, lip);
1642  matched_pathkey = false;
1643  }
1644 
1645  /* If mergeclause matches current inner pathkey, we can use it */
1646  if (clause_ec == pathkey_ec)
1647  {
1648  new_mergeclauses = lappend(new_mergeclauses, rinfo);
1649  matched_pathkey = true;
1650  }
1651  else
1652  {
1653  /* Else, no hope of adding any more mergeclauses */
1654  break;
1655  }
1656  }
1657 
1658  return new_mergeclauses;
1659 }
#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:1992
bool outer_is_left
Definition: pathnodes.h:1998
static ListCell * list_head(const List *l)
Definition: pg_list.h:125
List * lappend(List *list, void *datum)
Definition: list.c:322
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1011
EquivalenceClass * left_ec
Definition: pathnodes.h:1991
int i
Definition: pg_list.h:50

◆ truncate_useless_pathkeys()

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

Definition at line 1816 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().

1819 {
1820  int nuseful;
1821  int nuseful2;
1822 
1823  nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
1824  nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
1825  if (nuseful2 > nuseful)
1826  nuseful = nuseful2;
1827 
1828  /*
1829  * Note: not safe to modify input list destructively, but we can avoid
1830  * copying the list if we're not actually going to change it
1831  */
1832  if (nuseful == 0)
1833  return NIL;
1834  else if (nuseful == list_length(pathkeys))
1835  return pathkeys;
1836  else
1837  return list_truncate(list_copy(pathkeys), nuseful);
1838 }
#define NIL
Definition: pg_list.h:65
List * list_truncate(List *list, int new_size)
Definition: list.c:586
List * list_copy(const List *oldlist)
Definition: list.c:1404
static int pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
Definition: pathkeys.c:1794
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:1691

◆ update_mergeclause_eclasses()

void update_mergeclause_eclasses ( PlannerInfo root,
RestrictInfo restrictinfo 
)

Definition at line 1174 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().

1175 {
1176  /* Should be a merge clause ... */
1177  Assert(restrictinfo->mergeopfamilies != NIL);
1178  /* ... with pointers already set */
1179  Assert(restrictinfo->left_ec != NULL);
1180  Assert(restrictinfo->right_ec != NULL);
1181 
1182  /* Chase up to the top as needed */
1183  while (restrictinfo->left_ec->ec_merged)
1184  restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
1185  while (restrictinfo->right_ec->ec_merged)
1186  restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
1187 }
#define NIL
Definition: pg_list.h:65
EquivalenceClass * right_ec
Definition: pathnodes.h:1992
List * mergeopfamilies
Definition: pathnodes.h:1988
#define Assert(condition)
Definition: c.h:732
EquivalenceClass * left_ec
Definition: pathnodes.h:1991
struct EquivalenceClass * ec_merged
Definition: pathnodes.h:946