aboutsummaryrefslogtreecommitdiff
path: root/src/backend/optimizer/path/joinrels.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/backend/optimizer/path/joinrels.c')
-rw-r--r--src/backend/optimizer/path/joinrels.c528
1 files changed, 528 insertions, 0 deletions
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
new file mode 100644
index 00000000000..b26e3364f93
--- /dev/null
+++ b/src/backend/optimizer/path/joinrels.c
@@ -0,0 +1,528 @@
+/*-------------------------------------------------------------------------
+ *
+ * joinrels.c--
+ * Routines to determine which relations should be joined
+ *
+ * Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v 1.1.1.1 1996/07/09 06:21:36 scrappy Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "nodes/pg_list.h"
+#include "nodes/relation.h"
+
+#include "optimizer/internal.h"
+#include "optimizer/cost.h"
+#include "optimizer/paths.h"
+#include "optimizer/tlist.h"
+#include "optimizer/joininfo.h"
+#include "optimizer/pathnode.h"
+
+
+static List *find_clause_joins(Query *root, Rel *outer_rel, List *joininfo_list);
+static List *find_clauseless_joins(Rel *outer_rel, List *inner_rels);
+static Rel *init_join_rel(Rel *outer_rel, Rel *inner_rel, JInfo *joininfo);
+static List *new_join_tlist(List *tlist, List *other_relids,
+ int first_resdomno);
+static List *new_joininfo_list(List *joininfo_list, List *join_relids);
+static void add_superrels(Rel *rel, Rel *super_rel);
+static bool nonoverlap_rels(Rel *rel1, Rel *rel2);
+static bool nonoverlap_sets(List *s1, List *s2);
+static void set_joinrel_size(Rel *joinrel, Rel *outer_rel, Rel *inner_rel,
+ JInfo *jinfo);
+
+/*
+ * find-join-rels--
+ * Find all possible joins for each of the outer join relations in
+ * 'outer-rels'. A rel node is created for each possible join relation,
+ * and the resulting list of nodes is returned. If at all possible, only
+ * those relations for which join clauses exist are considered. If none
+ * of these exist for a given relation, all remaining possibilities are
+ * considered.
+ *
+ * 'outer-rels' is the list of rel nodes
+ *
+ * Returns a list of rel nodes corresponding to the new join relations.
+ */
+List *
+find_join_rels(Query *root, List *outer_rels)
+{
+ List *joins = NIL;
+ List *join_list = NIL;
+ List *r = NIL;
+
+ foreach(r, outer_rels) {
+ Rel *outer_rel = (Rel *)lfirst(r);
+
+ if(!(joins = find_clause_joins(root, outer_rel,outer_rel->joininfo)))
+ if (BushyPlanFlag)
+ joins = find_clauseless_joins(outer_rel,outer_rels);
+ else
+ joins = find_clauseless_joins(outer_rel,root->base_relation_list_);
+
+ join_list = nconc(join_list, joins);
+ }
+
+ return(join_list);
+}
+
+/*
+ * find-clause-joins--
+ * Determines whether joins can be performed between an outer relation
+ * 'outer-rel' and those relations within 'outer-rel's joininfo nodes
+ * (i.e., relations that participate in join clauses that 'outer-rel'
+ * participates in). This is possible if all but one of the relations
+ * contained within the join clauses of the joininfo node are already
+ * contained within 'outer-rel'.
+ *
+ * 'outer-rel' is the relation entry for the outer relation
+ * 'joininfo-list' is a list of join clauses which 'outer-rel'
+ * participates in
+ *
+ * Returns a list of new join relations.
+ */
+static List *
+find_clause_joins(Query *root, Rel *outer_rel, List *joininfo_list)
+{
+ List *join_list = NIL;
+ List *i = NIL;
+
+ foreach (i, joininfo_list) {
+ JInfo *joininfo = (JInfo*)lfirst(i);
+ Rel *rel;
+
+ if(!joininfo->inactive) {
+ List *other_rels = joininfo->otherrels;
+
+ if(other_rels != NIL) {
+ if(length(other_rels) == 1) {
+ rel = init_join_rel(outer_rel,
+ get_base_rel(root, lfirsti(other_rels)),
+ joininfo);
+ } else if (BushyPlanFlag) {
+ rel = init_join_rel(outer_rel,
+ get_join_rel(root, other_rels),
+ joininfo);
+ } else {
+ rel = NULL;
+ }
+
+ if (rel != NULL)
+ join_list = lappend(join_list, rel);
+ }
+ }
+ }
+
+ return(join_list);
+}
+
+/*
+ * find-clauseless-joins--
+ * Given an outer relation 'outer-rel' and a list of inner relations
+ * 'inner-rels', create a join relation between 'outer-rel' and each
+ * member of 'inner-rels' that isn't already included in 'outer-rel'.
+ *
+ * Returns a list of new join relations.
+ */
+static List *
+find_clauseless_joins(Rel *outer_rel, List *inner_rels)
+{
+ Rel *inner_rel;
+ List *t_list = NIL;
+ List *temp_node = NIL;
+ List *i = NIL;
+
+ foreach (i, inner_rels) {
+ inner_rel = (Rel *)lfirst(i);
+ if(nonoverlap_rels(inner_rel, outer_rel)) {
+ temp_node = lcons(init_join_rel(outer_rel,
+ inner_rel,
+ (JInfo*)NULL),
+ NIL);
+ t_list = nconc(t_list,temp_node);
+ }
+ }
+
+ return(t_list);
+}
+
+/*
+ * init-join-rel--
+ * Creates and initializes a new join relation.
+ *
+ * 'outer-rel' and 'inner-rel' are relation nodes for the relations to be
+ * joined
+ * 'joininfo' is the joininfo node(join clause) containing both
+ * 'outer-rel' and 'inner-rel', if any exists
+ *
+ * Returns the new join relation node.
+ */
+static Rel *
+init_join_rel(Rel *outer_rel, Rel *inner_rel, JInfo *joininfo)
+{
+ Rel *joinrel = makeNode(Rel);
+ List *joinrel_joininfo_list = NIL;
+ List *new_outer_tlist;
+ List *new_inner_tlist;
+
+ /*
+ * Create a new tlist by removing irrelevant elements from both
+ * tlists of the outer and inner join relations and then merging
+ * the results together.
+ */
+ new_outer_tlist =
+ new_join_tlist(outer_rel->targetlist, /* XXX 1-based attnos */
+ inner_rel->relids, 1);
+ new_inner_tlist =
+ new_join_tlist(inner_rel->targetlist, /* XXX 1-based attnos */
+ outer_rel->relids,
+ length(new_outer_tlist) + 1);
+
+ joinrel->relids = NIL;
+ joinrel->indexed = false;
+ joinrel->pages = 0;
+ joinrel->tuples = 0;
+ joinrel->width = 0;
+/* joinrel->targetlist = NIL;*/
+ joinrel->pathlist = NIL;
+ joinrel->unorderedpath = (Path *)NULL;
+ joinrel->cheapestpath = (Path *)NULL;
+ joinrel->pruneable = true;
+ joinrel->classlist = NULL;
+ joinrel->relam = InvalidOid;
+ joinrel->ordering = NULL;
+ joinrel->clauseinfo = NIL;
+ joinrel->joininfo = NULL;
+ joinrel->innerjoin = NIL;
+ joinrel->superrels = NIL;
+
+ joinrel->relids = lcons(outer_rel->relids, /* ??? aren't they lists? -ay */
+ lcons(inner_rel->relids, NIL));
+
+ new_outer_tlist = nconc(new_outer_tlist,new_inner_tlist);
+ joinrel->targetlist = new_outer_tlist;
+
+ if (joininfo) {
+ joinrel->clauseinfo = joininfo->jinfoclauseinfo;
+ if (BushyPlanFlag)
+ joininfo->inactive = true;
+ }
+
+ joinrel_joininfo_list =
+ new_joininfo_list(append(outer_rel->joininfo, inner_rel->joininfo),
+ intAppend(outer_rel->relids, inner_rel->relids));
+
+ joinrel->joininfo = joinrel_joininfo_list;
+
+ set_joinrel_size(joinrel, outer_rel, inner_rel, joininfo);
+
+ return(joinrel);
+}
+
+/*
+ * new-join-tlist--
+ * Builds a join relations's target list by keeping those elements that
+ * will be in the final target list and any other elements that are still
+ * needed for future joins. For a target list entry to still be needed
+ * for future joins, its 'joinlist' field must not be empty after removal
+ * of all relids in 'other-relids'.
+ *
+ * 'tlist' is the target list of one of the join relations
+ * 'other-relids' is a list of relids contained within the other
+ * join relation
+ * 'first-resdomno' is the resdom number to use for the first created
+ * target list entry
+ *
+ * Returns the new target list.
+ */
+static List *
+new_join_tlist(List *tlist,
+ List *other_relids,
+ int first_resdomno)
+{
+ int resdomno = first_resdomno - 1;
+ TargetEntry *xtl = NULL;
+ List *temp_node = NIL;
+ List *t_list = NIL;
+ List *i = NIL;
+ List *join_list = NIL;
+ bool in_final_tlist =false;
+
+
+ foreach(i,tlist) {
+ xtl= lfirst(i);
+ in_final_tlist = (join_list==NIL);
+ if( in_final_tlist) {
+ resdomno += 1;
+ temp_node =
+ lcons(create_tl_element(get_expr(xtl),
+ resdomno),
+ NIL);
+ t_list = nconc(t_list,temp_node);
+ }
+ }
+
+ return(t_list);
+}
+
+/*
+ * new-joininfo-list--
+ * Builds a join relation's joininfo list by checking for join clauses
+ * which still need to used in future joins involving this relation. A
+ * join clause is still needed if there are still relations in the clause
+ * not contained in the list of relations comprising this join relation.
+ * New joininfo nodes are only created and added to
+ * 'current-joininfo-list' if a node for a particular join hasn't already
+ * been created.
+ *
+ * 'current-joininfo-list' contains a list of those joininfo nodes that
+ * have already been built
+ * 'joininfo-list' is the list of join clauses involving this relation
+ * 'join-relids' is a list of relids corresponding to the relations
+ * currently being joined
+ *
+ * Returns a list of joininfo nodes, new and old.
+ */
+static List *
+new_joininfo_list(List *joininfo_list, List *join_relids)
+{
+ List *current_joininfo_list = NIL;
+ List *new_otherrels = NIL;
+ JInfo *other_joininfo = (JInfo*)NULL;
+ List *xjoininfo = NIL;
+
+ foreach (xjoininfo, joininfo_list) {
+ JInfo *joininfo = (JInfo*)lfirst(xjoininfo);
+
+ new_otherrels = joininfo->otherrels;
+ if (nonoverlap_sets(new_otherrels,join_relids)) {
+ other_joininfo = joininfo_member(new_otherrels,
+ current_joininfo_list);
+ if(other_joininfo) {
+ other_joininfo->jinfoclauseinfo =
+ (List*)LispUnion(joininfo->jinfoclauseinfo,
+ other_joininfo->jinfoclauseinfo);
+ }else {
+ other_joininfo = makeNode(JInfo);
+
+ other_joininfo->otherrels =
+ joininfo->otherrels;
+ other_joininfo->jinfoclauseinfo =
+ joininfo->jinfoclauseinfo;
+ other_joininfo->mergesortable =
+ joininfo->mergesortable;
+ other_joininfo->hashjoinable =
+ joininfo->hashjoinable;
+ other_joininfo->inactive = false;
+
+ current_joininfo_list = lcons(other_joininfo,
+ current_joininfo_list);
+ }
+ }
+ }
+
+ return(current_joininfo_list);
+}
+
+/*
+ * add-new-joininfos--
+ * For each new join relation, create new joininfos that
+ * use the join relation as inner relation, and add
+ * the new joininfos to those rel nodes that still
+ * have joins with the join relation.
+ *
+ * 'joinrels' is a list of join relations.
+ *
+ * Modifies the joininfo field of appropriate rel nodes.
+ */
+void
+add_new_joininfos(Query *root, List *joinrels, List *outerrels)
+{
+ List *xjoinrel = NIL;
+ List *xrelid = NIL;
+ List *xrel = NIL;
+ List *xjoininfo = NIL;
+
+ foreach(xjoinrel, joinrels) {
+ Rel *joinrel = (Rel *)lfirst(xjoinrel);
+ foreach(xrelid, joinrel->relids) {
+ Relid relid = (Relid)lfirst(xrelid);
+ Rel *rel = get_join_rel(root, relid);
+ add_superrels(rel,joinrel);
+ }
+ }
+ foreach(xjoinrel, joinrels) {
+ Rel *joinrel = (Rel *)lfirst(xjoinrel);
+
+ foreach(xjoininfo, joinrel->joininfo) {
+ JInfo *joininfo = (JInfo*)lfirst(xjoininfo);
+ List *other_rels = joininfo->otherrels;
+ List *clause_info = joininfo->jinfoclauseinfo;
+ bool mergesortable = joininfo->mergesortable;
+ bool hashjoinable = joininfo->hashjoinable;
+
+ foreach(xrelid, other_rels) {
+ Relid relid = (Relid)lfirst(xrelid);
+ Rel *rel = get_join_rel(root, relid);
+ List *super_rels = rel->superrels;
+ List *xsuper_rel = NIL;
+ JInfo *new_joininfo = makeNode(JInfo);
+
+ new_joininfo->otherrels = joinrel->relids;
+ new_joininfo->jinfoclauseinfo = clause_info;
+ new_joininfo->mergesortable = mergesortable;
+ new_joininfo->hashjoinable = hashjoinable;
+ new_joininfo->inactive = false;
+ rel->joininfo =
+ lappend(rel->joininfo, new_joininfo);
+
+ foreach(xsuper_rel, super_rels) {
+ Rel *super_rel = (Rel *)lfirst(xsuper_rel);
+
+ if( nonoverlap_rels(super_rel,joinrel) ) {
+ List *new_relids = super_rel->relids;
+ JInfo *other_joininfo =
+ joininfo_member(new_relids,
+ joinrel->joininfo);
+
+ if (other_joininfo) {
+ other_joininfo->jinfoclauseinfo =
+ (List*)LispUnion(clause_info,
+ other_joininfo->jinfoclauseinfo);
+ } else {
+ JInfo *new_joininfo = makeNode(JInfo);
+
+ new_joininfo->otherrels = new_relids;
+ new_joininfo->jinfoclauseinfo = clause_info;
+ new_joininfo->mergesortable = mergesortable;
+ new_joininfo->hashjoinable = hashjoinable;
+ new_joininfo->inactive = false;
+ joinrel->joininfo =
+ lappend(joinrel->joininfo,
+ new_joininfo);
+ }
+ }
+ }
+ }
+ }
+ }
+ foreach(xrel, outerrels) {
+ Rel *rel = (Rel *)lfirst(xrel);
+ rel->superrels = NIL;
+ }
+}
+
+/*
+ * final-join-rels--
+ * Find the join relation that includes all the original
+ * relations, i.e. the final join result.
+ *
+ * 'join-rel-list' is a list of join relations.
+ *
+ * Returns the list of final join relations.
+ */
+List *
+final_join_rels(List *join_rel_list)
+{
+ List *xrel = NIL;
+ List *temp = NIL;
+ List *t_list = NIL;
+
+ /*
+ * find the relations that has no further joins,
+ * i.e., its joininfos all have otherrels nil.
+ */
+ foreach(xrel,join_rel_list) {
+ Rel *rel = (Rel *)lfirst(xrel);
+ List *xjoininfo = NIL;
+ bool final = true;
+
+ foreach (xjoininfo, rel->joininfo) {
+ JInfo *joininfo = (JInfo*)lfirst(xjoininfo);
+
+ if (joininfo->otherrels != NIL) {
+ final = false;
+ break;
+ }
+ }
+ if (final) {
+ temp = lcons(rel, NIL);
+ t_list = nconc(t_list, temp);
+ }
+ }
+
+ return(t_list);
+}
+
+/*
+ * add_superrels--
+ * add rel to the temporary property list superrels.
+ *
+ * 'rel' a rel node
+ * 'super-rel' rel node of a join relation that includes rel
+ *
+ * Modifies the superrels field of rel
+ */
+static void
+add_superrels(Rel *rel, Rel *super_rel)
+{
+ rel->superrels = lappend(rel->superrels, super_rel);
+}
+
+/*
+ * nonoverlap-rels--
+ * test if two join relations overlap, i.e., includes the same
+ * relation.
+ *
+ * 'rel1' and 'rel2' are two join relations
+ *
+ * Returns non-nil if rel1 and rel2 do not overlap.
+ */
+static bool
+nonoverlap_rels(Rel *rel1, Rel *rel2)
+{
+ return(nonoverlap_sets(rel1->relids, rel2->relids));
+}
+
+static bool
+nonoverlap_sets(List *s1, List *s2)
+{
+ List *x = NIL;
+
+ foreach(x,s1) {
+ int e = lfirsti(x);
+ if(intMember(e,s2))
+ return(false);
+ }
+ return(true);
+}
+
+static void
+set_joinrel_size(Rel *joinrel, Rel *outer_rel, Rel *inner_rel, JInfo *jinfo)
+{
+ int ntuples;
+ float selec;
+
+ /* voodoo magic. but better than a size of 0. I have no idea why
+ we didn't set the size before. -ay 2/95 */
+ if (jinfo==NULL) {
+ /* worst case: the cartesian product */
+ ntuples = outer_rel->tuples * inner_rel->tuples;
+ } else {
+ selec = product_selec(jinfo->jinfoclauseinfo);
+/* ntuples = Min(outer_rel->tuples,inner_rel->tuples) * selec; */
+ ntuples = outer_rel->tuples * inner_rel->tuples * selec;
+ }
+
+ /* I bet sizes less than 1 will screw up optimization so
+ make the best case 1 instead of 0 - jolly*/
+ if (ntuples < 1)
+ ntuples = 1;
+
+ joinrel->tuples = ntuples;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-19 18:54:47 +0000