diff options
Diffstat (limited to 'src/backend/optimizer/geqo/minspantree.c')
| -rw-r--r-- | src/backend/optimizer/geqo/minspantree.c | 198 |
1 files changed, 198 insertions, 0 deletions
diff --git a/src/backend/optimizer/geqo/minspantree.c b/src/backend/optimizer/geqo/minspantree.c new file mode 100644 index 0000000000..4e4c2ad11b --- /dev/null +++ b/src/backend/optimizer/geqo/minspantree.c @@ -0,0 +1,198 @@ +/*------------------------------------------------------------------------ +* +* minspantree.c-- +* routine to sort a join graph which is including cycles +* +* Copyright (c) 1994, Regents of the University of California +* +* +* IDENTIFICATION +* $Header: /cvsroot/pgsql/src/backend/optimizer/geqo/Attic/minspantree.c,v 1.1 1997/02/19 12:57:50 scrappy Exp $ +* +*------------------------------------------------------------------------- +*/ + +#include <values.h> + +#include "postgres.h" + +#include "nodes/pg_list.h" +#include "nodes/relation.h" +#include "nodes/primnodes.h" + +#include "utils/palloc.h" + +#include "optimizer/cost.h" + +/* + include "optimizer/geqo/tsp.h" + */ + +#include "optimizer/geqo/geqo_gene.h" +#include "optimizer/geqo/geqo.h" + +/* + * minspantree-- + * The function minspantree computes the minimum spanning tree + * for a given number of nodes and a given distance function. + * For each pair of nodes found to be connected, a given + * function is called. Nodes are denoted by the integer numbers + * 1 .. number_of_joins, where number_of_joins is the number of nodes. +*/ + +void +minspantree(Query *root, List *join_rels, Rel *garel) +{ + int number_of_rels = length(root->base_relation_list_); + int number_of_joins = length(join_rels); + int *connectto; + /* connectto[i] = 0, if node i is already connected */ + /* to the tree, otherwise connectto[i] is the node */ + /* nearest to i, which is already connected. */ + + Cost *disttoconnect; /* disttoconnect[i]: distance between i and connectto[i] */ + + Cost dist, /* temporary */ + mindist; /* minimal distance between connected and unconnected node */ + + Cost mstlength = 0.0; /* the total length of the minimum spanning tree */ + + int count; + int n, /* newly attached node */ + nextn, /* next node to be attached */ + tempn; + + int i, id1, id2; + List *r = NIL; + Rel *joinrel = NULL; + Rel **tmprel_array; + + + /* allocate memory for matrix tmprel_array[x][y] */ + tmprel_array = (Rel **) palloc((number_of_rels+1)*sizeof(Rel *)); + for (i=0; i<=number_of_rels; i++) + (tmprel_array[i] = (Rel *) palloc ((number_of_rels+1)*sizeof(Rel))); + + /* read relations of join-relations into tmprel_array */ + + foreach(r, join_rels) { + joinrel = (Rel *)lfirst(r); + id1 = (int)lfirst(joinrel->relids); + id2 = (int)lsecond(joinrel->relids); + + if (id1 > id2) { + tmprel_array[id2][id1] = *(Rel *)joinrel; + } + else { + tmprel_array[id1][id2] = *(Rel *)joinrel; /* ever reached? */ + } + } + + /* Trivial special cases handled first */ + /* garel is global in "tsp.h" */ + + if (number_of_joins <= 2) + { + i=1; + foreach(r, join_rels) { + garel[i] = *(Rel *)lfirst(r); + i++; + } + } + + + else if (number_of_joins == 3) + { + Rel *rel12 = (Rel *) &tmprel_array[1][2]; + Rel *rel13 = (Rel *) &tmprel_array[1][3]; + Rel *rel23 = (Rel *) &tmprel_array[2][3]; + if (rel12->cheapestpath->path_cost > rel13->cheapestpath->path_cost) + { + garel[1] = tmprel_array[1][3]; + if (rel12->cheapestpath->path_cost > rel23->cheapestpath->path_cost) + { + garel[2] = tmprel_array[2][3]; + } + else + { + garel[2] = tmprel_array[1][2]; + } + } + else + { + garel[1] = tmprel_array[1][2]; + if (rel13->cheapestpath->path_cost > rel23->cheapestpath->path_cost) + { + garel[2] = tmprel_array[2][3]; + } + else + { + garel[2] = tmprel_array[1][3]; + } + } + } + + + /* now the general case */ + else + { + connectto = (int *) palloc((number_of_rels+1)*sizeof(int)); + disttoconnect = (Cost *) palloc((number_of_rels+1)*sizeof(Cost)); + + nextn = 2; + for (tempn = 2; tempn <= number_of_rels; tempn++ ) + { + connectto[tempn] = 1; + disttoconnect[tempn] = (Cost) MAXFLOAT; + } + + joinrel = NULL; + n = 1; + i = 1; + for (count = 2; count <= number_of_rels; count++ ) + { + connectto[n] = 0; + mindist = (Cost) MAXFLOAT; + for (tempn = 2; tempn <= number_of_rels; tempn++ ) + { + if (connectto[tempn] != 0) + { + if (n > tempn) { + joinrel = (Rel *) &tmprel_array[tempn][n]; + } + else { + joinrel = (Rel *) &tmprel_array[n][tempn]; + } + dist = joinrel->cheapestpath->path_cost; + + if (dist < disttoconnect[tempn]) + { + disttoconnect[tempn] = dist; + connectto[tempn] = n; + } + if (disttoconnect[tempn] < mindist) + { + mindist = disttoconnect[tempn]; + nextn = tempn; + } + } + } + n = nextn; + if (n > connectto[n]) { + garel[i] = tmprel_array[connectto[n]][n]; + } + else { + garel[i] = tmprel_array[n][connectto[n]]; + } + i++; + } + + pfree(connectto); + pfree(disttoconnect); + + } + + for (i=0; i<=number_of_rels; i++) pfree(tmprel_array[i]); + pfree(tmprel_array); +} + |