/*------------------------------------------------------------------------ * * geqo_eval.c-- * Routines to evaluate query trees * * Copyright (c) 1994, Regents of the University of California * * $Id: geqo_eval.c,v 1.22 1998/08/10 02:26:16 momjian Exp $ * *------------------------------------------------------------------------- */ /* contributed by: =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= * Martin Utesch * Institute of Automatic Control * = = University of Mining and Technology = * utesch@aut.tu-freiberg.de * Freiberg, Germany * =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= */ #include "postgres.h" #include <math.h> #ifdef HAVE_LIMITS_H #include <limits.h> #ifndef MAXINT #define MAXINT INT_MAX #endif #else #include <values.h> #endif #include "nodes/pg_list.h" #include "nodes/relation.h" #include "nodes/primnodes.h" #include "utils/palloc.h" #include "utils/elog.h" #include "optimizer/internal.h" #include "optimizer/paths.h" #include "optimizer/pathnode.h" #include "optimizer/clauses.h" #include "optimizer/cost.h" #include "optimizer/tlist.h" #include "optimizer/joininfo.h" #include "optimizer/geqo_gene.h" #include "optimizer/geqo.h" #include "optimizer/geqo_paths.h" static List *gimme_clause_joins(Query *root, RelOptInfo *outer_rel, RelOptInfo *inner_rel); static RelOptInfo *gimme_clauseless_join(RelOptInfo *outer_rel, RelOptInfo *inner_rel); static RelOptInfo *init_join_rel(RelOptInfo *outer_rel, RelOptInfo *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 geqo_joinrel_size(RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel); static RelOptInfo *geqo_nth(int stop, List *rels); /* * geqo_eval-- * * Returns cost of a query tree as an individual of the population. */ Cost geqo_eval(Query *root, Gene *tour, int num_gene) { RelOptInfo *joinrel; Cost fitness; List *temp; /* remember root->join_rel_list ... */ /* because root->join_rel_list will be changed during the following */ temp = listCopy(root->join_rel_list); /* joinrel is readily processed query tree -- left-sided ! */ joinrel = gimme_tree(root, tour, 0, num_gene, NULL); /* compute fitness */ fitness = (Cost) joinrel->cheapestpath->path_cost; root->join_rel_list = listCopy(temp); pfree(joinrel); freeList(temp); return (fitness); } /* * gimme-tree -- * this program presumes that only LEFT-SIDED TREES are considered! * * 'outer_rel' is the preceeding join * * Returns a new join relation incorporating all joins in a left-sided tree. */ RelOptInfo * gimme_tree(Query *root, Gene *tour, int rel_count, int num_gene, RelOptInfo *outer_rel) { RelOptInfo *inner_rel; /* current relation */ int base_rel_index; List *new_rels = NIL; RelOptInfo *new_rel = NULL; if (rel_count < num_gene) { /* tree not yet finished */ /* tour[0] = 3; tour[1] = 1; tour[2] = 2 */ base_rel_index = (int) tour[rel_count]; inner_rel = (RelOptInfo *) geqo_nth(base_rel_index, root->base_rel_list); if (rel_count == 0) { /* processing first join with * base_rel_index = (int) tour[0] */ rel_count++; return gimme_tree(root, tour, rel_count, num_gene, inner_rel); } else { /* tree main part */ if (!(new_rels = gimme_clause_joins(root, outer_rel, inner_rel))) { if (BushyPlanFlag) { new_rels = lcons(gimme_clauseless_join(outer_rel, outer_rel), NIL); /* ??? MAU */ } else new_rels = lcons(gimme_clauseless_join(outer_rel, inner_rel), NIL); } /* process new_rel->pathlist */ find_all_join_paths(root, new_rels); /* prune new_rels */ /* MAU: is this necessary? */ /* * what's the matter if more than one new rel is left till * now? */ /* * joinrels in newrels with different ordering of relids are * not possible */ if (length(new_rels) > 1) new_rels = geqo_prune_rels(new_rels); if (length(new_rels) > 1) { /* should never be reached ... */ elog(DEBUG, "gimme_tree: still %d relations left", length(new_rels)); } /* get essential new relation */ new_rel = (RelOptInfo *) lfirst(new_rels); rel_count++; /* process new_rel->cheapestpath, new_rel->unorderedpath */ geqo_rel_paths(new_rel); /* processing of other new_rel attributes */ if (new_rel->size <= 0) new_rel->size = compute_rel_size(new_rel); new_rel->width = compute_rel_width(new_rel); root->join_rel_list = lcons(new_rel, NIL); return gimme_tree(root, tour, rel_count, num_gene, new_rel); } } return (outer_rel); /* tree finished ... */ } /* * gimme-clause-joins-- * * 'outer-rel' is the relation entry for the outer relation * 'inner-rel' is the relation entry for the inner relation * * Returns a list of new join relations. */ static List * gimme_clause_joins(Query *root, RelOptInfo *outer_rel, RelOptInfo *inner_rel) { List *join_list = NIL; List *i = NIL; List *joininfo_list = (List *) outer_rel->joininfo; foreach(i, joininfo_list) { JInfo *joininfo = (JInfo *) lfirst(i); RelOptInfo *rel = NULL; if (!joininfo->inactive) { List *other_rels = (List *) joininfo->otherrels; if (other_rels != NIL) { if ((length(other_rels) == 1)) { if (same(other_rels, inner_rel->relids)) { /* look if inner_rel is it... */ rel = init_join_rel(outer_rel, inner_rel, joininfo); } } else if (BushyPlanFlag) { /* ?!? MAU */ 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); } /* * gimme-clauseless-join-- * Given an outer relation 'outer-rel' and an inner relation * 'inner-rel', create a join relation between 'outer-rel' and 'inner-rel' * * Returns a new join relation. */ static RelOptInfo * gimme_clauseless_join(RelOptInfo *outer_rel, RelOptInfo *inner_rel) { return (init_join_rel(outer_rel, inner_rel, (JInfo *) NULL)); } /* * 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 RelOptInfo * init_join_rel(RelOptInfo *outer_rel, RelOptInfo *inner_rel, JInfo *joininfo) { RelOptInfo *joinrel = makeNode(RelOptInfo); 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, 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; geqo_joinrel_size(joinrel, outer_rel, inner_rel); 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) { List *or; JInfo *joininfo = (JInfo *) lfirst(xjoininfo); new_otherrels = joininfo->otherrels; foreach(or, new_otherrels) { if (intMember(lfirsti(or), join_relids)) new_otherrels = lremove((void *) lfirst(or), new_otherrels); } joininfo->otherrels = new_otherrels; if (new_otherrels != NIL) { 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->mergejoinable = joininfo->mergejoinable; other_joininfo->hashjoinable = joininfo->hashjoinable; other_joininfo->inactive = false; current_joininfo_list = lcons(other_joininfo, current_joininfo_list); } } } return (current_joininfo_list); } #ifdef NOTUSED /* * 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. */ static void geqo_add_new_joininfos(Query *root, List *joinrels, List *outerrels) { List *xjoinrel = NIL; List *xrelid = NIL; List *xrel = NIL; List *xjoininfo = NIL; RelOptInfo *rel; List *relids; List *super_rels; List *xsuper_rel = NIL; JInfo *new_joininfo; foreach(xjoinrel, joinrels) { RelOptInfo *joinrel = (RelOptInfo *) lfirst(xjoinrel); foreach(xrelid, joinrel->relids) { /* * length(joinrel->relids) should always be greater that 1, * because of *JOIN* */ /* * ! BUG BUG ! Relid relid = (Relid)lfirst(xrelid); RelOptInfo *rel = * get_join_rel(root, relid); */ /* * if ( (root->join_rel_list) != NIL ) { rel = * get_join_rel(root, xrelid); } else { rel = * get_base_rel(root, lfirsti(xrelid)); } */ /* NOTE: STILL BUGGY FOR CLAUSE-JOINS: */ /* * relids = lconsi(lfirsti(xrelid), NIL); rel = * rel_member(relids, outerrels); */ relids = lconsi(lfirsti(xrelid), NIL); rel = rel_member(relids, root->base_rel_list); add_superrels(rel, joinrel); } } foreach(xjoinrel, joinrels) { RelOptInfo *joinrel = (RelOptInfo *) lfirst(xjoinrel); foreach(xjoininfo, joinrel->joininfo) { JInfo *joininfo = (JInfo *) lfirst(xjoininfo); List *other_rels = joininfo->otherrels; List *clause_info = joininfo->jinfoclauseinfo; bool mergejoinable = joininfo->mergejoinable; bool hashjoinable = joininfo->hashjoinable; foreach(xrelid, other_rels) { /* * ! BUG BUG ! Relid relid = (Relid)lfirst(xrelid); RelOptInfo * *rel = get_join_rel(root, relid); */ /* * if ( (root->join_rel_list) != NIL ) { rel = * get_join_rel(root, xrelid); } else { rel = * get_base_rel(root, lfirsti(xrelid)); } */ /* NOTE: STILL BUGGY FOR CLAUSE-JOINS: */ /* * relids = lconsi(lfirsti(xrelid), NIL); rel = * rel_member(relids, outerrels); */ relids = lconsi(lfirsti(xrelid), NIL); rel = rel_member(relids, root->base_rel_list); super_rels = rel->superrels; new_joininfo = makeNode(JInfo); new_joininfo->otherrels = joinrel->relids; new_joininfo->jinfoclauseinfo = clause_info; new_joininfo->mergejoinable = mergejoinable; new_joininfo->hashjoinable = hashjoinable; new_joininfo->inactive = false; rel->joininfo = lappend(rel->joininfo, new_joininfo); foreach(xsuper_rel, super_rels) { RelOptInfo *super_rel = (RelOptInfo *) 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->mergejoinable = mergejoinable; new_joininfo->hashjoinable = hashjoinable; new_joininfo->inactive = false; joinrel->joininfo = lappend(joinrel->joininfo, new_joininfo); } } } } } } foreach(xrel, outerrels) { rel = (RelOptInfo *) 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. */ static List * geqo_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) { RelOptInfo *rel = (RelOptInfo *) 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(RelOptInfo *rel, RelOptInfo *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(RelOptInfo *rel1, RelOptInfo *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); } #endif /* NOTUSED */ /* * geqo_joinrel_size-- * compute estimate for join relation tuples, even for * long join queries; so get logarithm of size when MAXINT overflow; */ static void geqo_joinrel_size(RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel) { Cost temp; int ntuples; temp = (Cost) inner_rel->tuples * (Cost) outer_rel->tuples; /* cartesian product */ if (joinrel->clauseinfo) temp = temp * product_selec(joinrel->clauseinfo); if (temp >= (MAXINT - 1)) ntuples = ceil(geqo_log((double) temp, (double) GEQO_LOG_BASE)); else ntuples = ceil((double) temp); if (ntuples < 1) ntuples = 1; /* make the best case 1 instead of 0 */ joinrel->tuples = ntuples; } double geqo_log(double x, double b) { return (log(x) / log(b)); } static RelOptInfo * geqo_nth(int stop, List *rels) { List *r; int i = 1; foreach(r, rels) { if (i == stop) return lfirst(r); i++; } elog(ERROR, "geqo_nth: Internal error - ran off end of list"); return NULL; /* to keep compiler happy */ }