head	1.28;
access;
symbols
	release_4_2:1.28
	aix_ok:1.28
	Version_2_1:1.15
	C_Demo_1:1.9
	Retrieve_x_qual:1.7
	Retrieve_x_all:1.6
	Retrieve_x_1:1.5;
locks; strict;
comment	@ * @;


1.28
date	92.07.23.15.15.17;	author joey;	state Exp;
branches;
next	1.27;

1.27
date	92.07.23.05.07.25;	author mer;	state Exp;
branches;
next	1.26;

1.26
date	92.07.22.06.57.11;	author joey;	state Exp;
branches;
next	1.25;

1.25
date	92.07.08.04.58.07;	author joey;	state Exp;
branches;
next	1.24;

1.24
date	92.06.16.22.50.42;	author joey;	state Exp;
branches;
next	1.23;

1.23
date	92.06.16.22.31.42;	author joey;	state Exp;
branches;
next	1.22;

1.22
date	92.03.31.23.12.43;	author mer;	state Exp;
branches;
next	1.21;

1.21
date	92.03.17.23.27.25;	author joey;	state Exp;
branches;
next	1.20;

1.20
date	92.01.21.16.42.20;	author hong;	state Exp;
branches;
next	1.19;

1.19
date	91.11.17.20.39.50;	author mer;	state Exp;
branches;
next	1.18;

1.18
date	91.11.15.16.26.42;	author hong;	state Exp;
branches;
next	1.17;

1.17
date	91.11.02.21.41.52;	author hong;	state Exp;
branches;
next	1.16;

1.16
date	91.05.23.18.27.28;	author kemnitz;	state Exp;
branches;
next	1.15;

1.15
date	90.09.25.16.35.16;	author kemnitz;	state Exp;
branches;
next	1.14;

1.14
date	89.10.17.13.45.25;	author cimarron;	state Exp;
branches;
next	1.13;

1.13
date	89.10.10.12.10.37;	author hirohama;	state Exp;
branches;
next	1.12;

1.12
date	89.10.09.18.06.08;	author hirohama;	state Exp;
branches;
next	1.11;

1.11
date	89.09.29.22.37.09;	author hirohama;	state Exp;
branches;
next	1.10;

1.10
date	89.09.29.14.39.09;	author hong;	state Exp;
branches;
next	1.9;

1.9
date	89.09.05.17.17.05;	author mao;	state C_Demo_1;
branches;
next	1.8;

1.8
date	89.08.23.16.02.28;	author ong;	state Exp;
branches;
next	1.7;

1.7
date	89.08.04.14.27.05;	author goh;	state Exp;
branches;
next	1.6;

1.6
date	89.08.04.13.22.56;	author goh;	state Exp;
branches;
next	1.5;

1.5
date	89.08.01.14.39.28;	author goh;	state Exp;
branches;
next	1.4;

1.4
date	89.08.01.14.39.03;	author goh;	state Exp;
branches;
next	1.3;

1.3
date	89.07.25.17.34.44;	author ong;	state Exp;
branches;
next	1.2;

1.2
date	89.07.20.15.56.23;	author ong;	state Exp;
branches;
next	1.1;

1.1
date	89.07.10.15.13.05;	author ong;	state Exp;
branches;
next	;


desc
@initial revision
@


1.28
log
@remove unused variables found by lint
@
text
@/*     
 *      FILE
 *     	path
 *     
 *      DESCRIPTION
 *     	Routines to find possible search paths for processing a query
 *     
 */
/* RcsId("$Header: /private/joey/pg/src/planner/path/RCS/allpaths.c,v 1.27 1992/07/23 05:07:25 mer Exp joey $"); */

/*     
 *      EXPORTS
 *     		find-paths
 */

#include <strings.h>

#include "nodes/pg_lisp.h"
#include "nodes/relation.h"
#include "nodes/relation.a.h"
#include "nodes/primnodes.h"
#include "nodes/primnodes.a.h"

#include "planner/allpaths.h"
#include "planner/internal.h"
#include "planner/indxpath.h"
#include "planner/orindxpath.h"
#include "planner/joinrels.h"
#include "planner/prune.h"
#include "planner/indexnode.h"
#include "planner/pathnode.h"
#include "planner/clauses.h"
#include "planner/xfunc.h"
#include "tcop/creatinh.h"
#include "lib/copyfuncs.h"

/*    
 *    	find-paths
 *    
 *    	Finds all possible access paths for executing a query, returning the
 *    	top level list of relation entries.  
 *    
 *    	'rels' is the list of single relation entries appearing in the query
 *    	'nest-level' is the current attribute nesting level being processed
 *    	'sortkeys' contains info on sorting of the result
 *    
 */

/*  .. subplanner   */

LispValue
find_paths(rels,nest_level,sortkeys)
     LispValue rels,sortkeys ;
     int nest_level;
{
    if( length(rels) > 0 && nest_level > 0 ) {
	/* Set the number of join(not nesting) levels yet to be processed. */
	
	int levels_left = length(rels);

	/* Find the base relation paths. */
	find_rel_paths(rels,nest_level,sortkeys);
	
	if( !sortkeys && (levels_left <= 1)) {
	    /* Unsorted single relation, no more processing is required. */
	    return(rels);   
	} 
	else {
	    /* 
	     * this means that joins or sorts are required.
	     * set selectivities of clauses that have not been set
	     * by an index.
	     */
	    set_rest_relselec(rels);
	    if(levels_left <= 1) {
		return(rels); 
	      } 
	    else {
		return(find_join_paths(rels,levels_left - 1,nest_level));
	      }
	  }
      }
    return(NULL);
}  /* end find_paths */

/*    
 *    	find-rel-paths
 *    
 *    	Finds all paths available for scanning each relation entry in 
 *    	'rels'.  Sequential scan and any available indices are considered
 *    	if possible(indices are not considered for lower nesting levels).
 *    	All unique paths are attached to the relation's 'pathlist' field.
 *    
 *    	'level' is the current attribute nesting level, where 1 is the first.
 *    	'sortkeys' contains sort result info.
 *    
 *    	RETURNS:  'rels'.
 *	MODIFIES: rels
 *    
 */

/*  .. find-paths      */

LispValue
find_rel_paths(rels,level,sortkeys)
     LispValue rels,sortkeys ;
     int level;
{
     LispValue temp;
     Rel rel;
     
     foreach(temp,rels) {
	  LispValue sequential_scan_list;

	  rel = (Rel)CAR(temp);
	  sequential_scan_list = lispCons((LispValue)create_seqscan_path(rel),
					  LispNil);

	  if(level > 1) {
	       set_pathlist(rel,sequential_scan_list);
	       /* XXX casting a list to a Path */
	       set_unorderedpath(rel, (PathPtr)sequential_scan_list);
	       set_cheapestpath(rel, (PathPtr)sequential_scan_list);
	    } 
	  else {
	       LispValue rel_index_scan_list = 
		 find_index_paths(rel,find_relation_indices(rel),
				   get_clauseinfo(rel),
				   get_joininfo(rel),sortkeys);
	       LispValue or_index_scan_list = 
		 create_or_index_paths(rel,get_clauseinfo(rel));

	       set_pathlist(rel,add_pathlist(rel,sequential_scan_list,
					       append(rel_index_scan_list,
						       or_index_scan_list)));
	    } 
    
	  /* The unordered path is always the last in the list.  
	   * If it is not the cheapest path, prune it.
	   */
	  prune_rel_path(rel, (Path)last_element(get_pathlist(rel))); 
       }
     foreach(temp, rels) {
	 rel = (Rel)CAR(temp);
	 set_size(rel, compute_rel_size(rel));
	 set_width(rel, compute_rel_width(rel));
       }
     return(rels);

}  /* end find_rel_path */

/*    
 *    	find-join-paths
 *    
 *    	Find all possible joinpaths for a query by successively finding ways
 *    	to join single relations into join relations.  
 *
 *	if BushyPlanFlag is set, bushy tree plans will be generated:
 *	Find all possible joinpaths(bushy trees) for a query by systematically
 *	finding ways to join relations(both original and derived) together.
 *    
 *    	'outer-rels' is	the current list of relations for which join paths 
 *    		are to be found, i.e., he current list of relations that 
 *		have already been derived.
 *    	'levels-left' is the current join level being processed, where '1' is
 *    		the "last" level
 *    	'nest-level' is the current attribute nesting level
 *    
 *    	Returns the final level of join relations, i.e., the relation that is
 *	the result of joining all the original relations togehter.
 *    
 */

/*  .. find-join-paths, find-paths
 */
LispValue
find_join_paths(outer_rels,levels_left,nest_level)
     LispValue outer_rels;
     int levels_left, nest_level;
{
    LispValue x;
    Rel rel;

    /*
    * Determine all possible pairs of relations to be joined at this level.
    * Determine paths for joining these relation pairs and modify 'new-rels'
    * accordingly, then eliminate redundant join relations.
    */

    LispValue new_rels = find_join_rels(outer_rels);

    find_all_join_paths(new_rels, outer_rels, nest_level);

    new_rels = prune_joinrels(new_rels);

    /* 
    ** for each expensive predicate in each path in each distinct rel, 
    ** consider doing pullup  -- JMH 
    */
    if (XfuncMode != XFUNC_NOPULL && XfuncMode != XFUNC_OFF)
      foreach(x, new_rels)
	xfunc_trypullup((Rel)CAR(x));

    prune_rel_paths(new_rels);

    if(BushyPlanFlag) {
      /*
       * In case of bushy trees
       * if there is still a join between a join relation and another
       * relation, add a new joininfo that involves the join relation
       * to the joininfo list of the other relation
       */
      add_new_joininfos(new_rels,outer_rels);
    }

    foreach(x, new_rels) {
       rel = (Rel)CAR(x);
       set_size(rel, compute_rel_size(rel));
       set_width(rel, compute_rel_width(rel));
    }

    if(BushyPlanFlag) {
      /* 
       * prune rels that have been completely incorporated into
       * new join rels
       */
      outer_rels = prune_oldrels(outer_rels);
      /* 
       * merge join rels if then contain the same list of base rels
       */
      outer_rels = merge_joinrels(new_rels,outer_rels);
      _join_relation_list_ = outer_rels;
    }
   else {
       _join_relation_list_ = new_rels;
     }

    if(levels_left == 1) {
      if(BushyPlanFlag)
	 return(final_join_rels(outer_rels));
      else
	 return(new_rels);
    } 
    else {
      if(BushyPlanFlag)
	  return(find_join_paths(outer_rels, levels_left - 1, nest_level));
      else
	 return(find_join_paths(new_rels, levels_left - 1, nest_level));
    } 
}


/*
 * The following functions are solely for the purpose of debugging.
 */

/*
 * xStrcat --
 *	Special strcat which returns concatenation into a static buffer.
 */
static
char *xStrcat(s1, s2)
char *s1, *s2;
{
    static char stringbuf[100];
    sprintf(stringbuf, "%s%s",s1,s2);
    return stringbuf;
}

void
printclauseinfo(ind,cl)
char *ind;
List cl;
{
    LispValue xc;
    char indent[100];
    strcpy(indent, ind);
    foreach(xc,cl) {
       CInfo c = (CInfo)CAR(xc);
       if(c == (CInfo)NULL) continue;
       printf("\n%sClauseInfo:	CInfo%lx",indent,(long)c);
       printf("\n%sOp:		%u",indent,get_opno((Oper)get_op((List)get_clause(c))));
       printf("\n%sLeftOp:	",indent);
       lispDisplay(get_varid(get_leftop((List)get_clause(c))));
       printf("\n%sRightOp:	",indent);
       lispDisplay(get_varid(get_rightop((List)get_clause(c))));
       printf("\n%sSelectivity:	%lg\n",indent,get_selectivity(c));
    }
}

void
printjoininfo(ind,jl)
char *ind;
List jl;
{
    LispValue xj;
    char indent[100];
    strcpy(indent, ind);
    foreach(xj,jl) {
	JInfo j = (JInfo)CAR(xj);
	if(joininfo_inactive(j)) continue;
	printf("\n%sJoinInfo:	JInfo%lx",indent,(long)j);
	printf("\n%sOtherRels:	",indent);
	lispDisplay(get_otherrels(j));
	printf("\n%sClauseInfo:	",indent);
	printclauseinfo(xStrcat(indent, "	"),get_jinfoclauseinfo(j));
    }
}

void
printpath(ind,p)
char *ind;
Path p;
{
    char indent[100];
    strcpy(indent, ind);
	if(p == (Path)NULL) return;
	printf("%sPath:	0x%lx",indent,(long)p);
	printf("\n%sParent:	",indent);
	lispDisplay(get_relids(get_parent(p)));
	printf("\n%sPathType:	%ld",indent,get_pathtype(p));
	printf("\n%sCost:	%lg",indent,get_path_cost(p));
	switch(get_pathtype(p))  {
	case T_NestLoop:
		printf("\n%sClauseInfo:	\n",indent);
		printclauseinfo(xStrcat(indent,"	"),get_pathclauseinfo((JoinPath)p));
		printf("%sOuterJoinPath:	\n",indent);
		printpath(xStrcat(indent,"	"),get_outerjoinpath((JoinPath)p));
		printf("%sInnerJoinPath:	\n",indent);
		printpath(xStrcat(indent,"	"),get_innerjoinpath((JoinPath)p));
		printf("%sOuterJoinCost:	%lg",indent,get_outerjoincost(p));
		printf("\n%sJoinId:	",indent);
		lispDisplay(get_joinid(p));
		break;
	case T_MergeJoin:
		printf("\n%sClauseInfo: \n",indent);
                printclauseinfo(xStrcat(indent,"       "),get_pathclauseinfo((JoinPath)p));
                printf("%sOuterJoinPath:        \n",indent);
                printpath(xStrcat(indent," "),get_outerjoinpath((JoinPath)p));
                printf("%sInnerJoinPath:        \n",indent);
                printpath(xStrcat(indent," "),get_innerjoinpath((JoinPath)p));
                printf("%sOuterJoinCost:        %lg",indent,get_outerjoincost(p));
                printf("\n%sJoinId:     ",indent);
                lispDisplay(get_joinid(p));
		printf("\n%sMergeClauses:	",indent);
		lispDisplay(get_path_mergeclauses((MergePath)p));
		printf("\n%sOuterSortKeys:	",indent);
		lispDisplay(get_outersortkeys((MergePath)p));
		printf("\n%sInnerSortKeys:	",indent);
		lispDisplay(get_innersortkeys((MergePath)p));
		break;
	case T_HashJoin:
                printf("\n%sClauseInfo: \n",indent);
                printclauseinfo(xStrcat(indent,"       "),get_pathclauseinfo((JoinPath)p));
                printf("%sOuterJoinPath:        \n",indent);
                printpath(xStrcat(indent," "),get_outerjoinpath((JoinPath)p));
		printf("%sInnerJoinPath:        \n",indent);
                printpath(xStrcat(indent," "),get_innerjoinpath((JoinPath)p));
                printf("%sOuterJoinCost:        %lg",indent,get_outerjoincost(p));
                printf("\n%sJoinId:     ",indent);
                lispDisplay(get_joinid(p));
		printf("\n%sHashClauses:	",indent);
		lispDisplay(get_path_hashclauses((HashPath)p));
		printf("\n%sOuterHashKeys:	",indent);
		lispDisplay(get_outerhashkeys((HashPath)p));
		printf("\n%sInnerHashKeys:	",indent);
		lispDisplay(get_innerhashkeys((HashPath)p));
		break;
	case T_IndexScan:
		printf("\n%sIndexQual:	",indent);
		lispDisplay(get_indexqual((IndexPath)p));
		break;
	}
	printf("\n");
}

void
printpathlist(ind, pl)
char *ind;
LispValue pl;
{
    LispValue xp;
    char indent[100];
    strcpy(indent,ind);
    foreach(xp,pl) {
	Path p = (Path)CAR(xp);
	printpath(indent,p);
    }
}

void
printrels(ind,rl)
char *ind;
List rl;
{
    LispValue xr;
    char indent[100];
    strcpy(indent,ind);
    foreach(xr,rl) {
	Rel r = (Rel)CAR(xr);
	if(r == (Rel)NULL) continue;
	printf("\n%sRel:	Rel%lx",indent,(long)r);
	printf("\n%sRelid:	",indent);
	lispDisplay(get_relids(r));
	printf("\n%sSize:	%u",indent,get_size(r));
	printf("\n%sPathlist:	\n",indent);
	printpathlist(xStrcat(indent,"	"),get_pathlist(r));
	printf("%sClauseInfo:	\n",indent);
	printclauseinfo(xStrcat(indent,"	"),get_clauseinfo(r));
	printf("%sJoinInfo:	",indent);
	printjoininfo(xStrcat(indent,"	"),get_joininfo(r));
     }
}

void
PrintRels(rl)
List rl;
{
    printrels("",rl);
    printf("\n");
}

void
PRel(r)
Rel r;
{
    printrels("",lispCons((LispValue)r,LispNil));
}
@


1.27
log
@prune the join rels *before* considering xfunc pullup
@
text
@d9 1
a9 1
/* RcsId("$Header: /private/mer/pg/src/planner/path/RCS/allpaths.c,v 1.26 1992/07/22 06:57:11 joey Exp mer $"); */
a68 1
	    LispValue x;
a110 1
     LispValue tmppath;
d181 1
a181 1
    LispValue x, y;
a182 2
    Path curpath;
    LispValue tmp_rels;
@


1.26
log
@don't pullup if XfuncMode = XFUNC_NOPULL
@
text
@d9 1
a9 1
/* RcsId("$Header: /private/joey/pg/src/planner/path/RCS/allpaths.c,v 1.25 1992/07/08 04:58:07 joey Exp joey $"); */
d198 6
a203 2
    /* for each expensive predicate in each path in each rel, consider 
       doing pullup  -- JMH */
a207 1
    new_rels = prune_joinrels(new_rels);
@


1.25
log
@removed the copy of the clauseinfo of the rel into the path nodes.
This is now done in the create_xxx_node functions.
@
text
@d9 1
a9 1
/* RcsId("$Header: /private/joey/pg/src/planner/path/RCS/allpaths.c,v 1.24 1992/06/16 22:50:42 joey Exp joey $"); */
d200 1
a200 1
    if (XfuncMode != XFUNC_OFF)
@


1.24
log
@fix a warning message
@
text
@d9 1
a9 1
/* RcsId("$Header: /private/joey/pg/src/planner/path/RCS/allpaths.c,v 1.23 1992/06/16 22:31:42 joey Exp joey $"); */
a143 6

	  /* copy clauseinfo list into each path for expensive function 
	     processing */
	  foreach(tmppath, get_pathlist(rel))
	    set_locclauseinfo((Path)CAR(tmppath),
			      (List)CopyObject(get_clauseinfo(rel)));
@


1.23
log
@No longer bother sorting clauses in scan rels.  Calls new pullup
routines.
@
text
@d9 1
a9 1
/* RcsId("$Header: /usr/private/joey/pg/src/planner/path/RCS/allpaths.c,v 1.22 1992/03/31 23:12:43 mer Exp joey $"); */
d149 1
a149 1
			      CopyObject(get_clauseinfo(rel)));
@


1.22
log
@change accessor functions into macros
@
text
@d9 1
a9 1
/* RcsId("$Header: /users/mer/pg/src/planner/path/RCS/allpaths.c,v 1.21 1992/03/17 23:27:25 joey Exp mer $"); */
d34 2
a63 6
	/* sort the clauses in the base relations by expense
	**   -- JMH 2/24/92
	*/
	if (XfuncMode != XFUNC_OFF)
	  xfunc_rellist_sortprds(rels);

d112 1
d145 5
d189 1
a189 1
    LispValue x;
d191 2
d203 6
@


1.21
log
@add calls to expensive function code
@
text
@d9 1
a9 1
/* RcsId("$Header: /usr/private/joey/pg/src/planner/path/RCS/allpaths.c,v 1.20 1992/01/21 16:42:20 hong Exp joey $"); */
d127 2
a128 2
	       set_unorderedpath(rel, (Path)sequential_scan_list);
	       set_cheapestpath(rel, (Path)sequential_scan_list);
@


1.20
log
@set size and width of Rel nodes
@
text
@d9 1
a9 1
/* RcsId("$Header: RCS/allpaths.c,v 1.19 91/11/17 20:39:50 mer Exp Locker: hong $"); */
d33 1
d58 1
a58 1
	
d61 7
@


1.19
log
@prototyping
@
text
@d9 1
a9 1
/* RcsId("$Header: /users/mer/postgres/src/planner/path/RCS/allpaths.c,v 1.18 1991/11/15 16:26:42 hong Exp $"); */
a65 1
	    Rel rel;
d69 1
a69 1
	     * by an index.  also set sizes and widths of relations.
a71 5
	    foreach(x, rels) {
		rel = (Rel)CAR(x);
		set_size(rel, compute_rel_size(rel));
		set_width(rel, compute_rel_width(rel));
	    }
d140 5
@


1.18
log
@planner prototyping
@
text
@d9 1
a9 1
/* RcsId("$Header: RCS/allpaths.c,v 1.17 91/11/02 21:41:52 hong Exp $"); */
d119 2
a120 1
	  sequential_scan_list = lispCons(create_seqscan_path(rel), LispNil);
d417 1
a417 1
    printrels("",lispCons(r,LispNil));
@


1.17
log
@cleaned up bushy tree plan generation code.
@
text
@d9 1
a9 1
/* RcsId("$Header: RCS/allpaths.c,v 1.16 91/05/23 18:27:28 kemnitz Exp Locker: hong $"); */
d20 3
d30 3
d123 3
a125 2
	       set_unorderedpath(rel,sequential_scan_list);
	       set_cheapestpath(rel,sequential_scan_list);
d143 1
a143 1
	  prune_rel_path(rel, last_element(get_pathlist(rel))); 
d271 1
a271 1
       printf("\n%sOp:		%u",indent,get_opno(get_op(get_clause(c))));
d273 1
a273 1
       lispDisplay(get_varid(get_leftop(get_clause(c))),0);
d275 1
a275 1
       lispDisplay(get_varid(get_rightop(get_clause(c))),0);
a286 1
    bool joininfo_inactive();
d293 1
a293 1
	lispDisplay(get_otherrels(j),0);
d309 1
a309 1
	lispDisplay(get_relids(get_parent(p)),0);
d315 1
a315 1
		printclauseinfo(xStrcat(indent,"	"),get_pathclauseinfo(p));
d317 1
a317 1
		printpath(xStrcat(indent,"	"),get_outerjoinpath(p));
d319 1
a319 1
		printpath(xStrcat(indent,"	"),get_innerjoinpath(p));
d322 1
a322 1
		lispDisplay(get_joinid(p),0);
d326 1
a326 2
                printclauseinfo(xStrcat(indent,"       "),get_pathclauseinfo(p
));
d328 1
a328 1
                printpath(xStrcat(indent," "),get_outerjoinpath(p));
d330 2
a331 3
                printpath(xStrcat(indent," "),get_innerjoinpath(p));
                printf("%sOuterJoinCost:        %lg",indent,get_outerjoincost(p
));
d333 1
a333 1
                lispDisplay(get_joinid(p),0);
d335 1
a335 1
		lispDisplay(get_path_mergeclauses(p),0);
d337 1
a337 1
		lispDisplay(get_outersortkeys(p),0);
d339 1
a339 1
		lispDisplay(get_innersortkeys(p),0);
d343 1
a343 2
                printclauseinfo(xStrcat(indent,"       "),get_pathclauseinfo(p
));
d345 4
a348 5
                printpath(xStrcat(indent," "),get_outerjoinpath(p));
                printf("%sInnerJoinPath:        \n",indent);
                printpath(xStrcat(indent," "),get_innerjoinpath(p));
                printf("%sOuterJoinCost:        %lg",indent,get_outerjoincost(p
));
d350 1
a350 1
                lispDisplay(get_joinid(p),0);
d352 1
a352 1
		lispDisplay(get_path_hashclauses(p),0);
d354 1
a354 1
		lispDisplay(get_outerhashkeys(p),0);
d356 1
a356 1
		lispDisplay(get_innerhashkeys(p),0);
d360 1
a360 1
		lispDisplay(get_indexqual(p),0);
d393 1
a393 1
	lispDisplay(get_relids(r),0);
@


1.16
log
@got rid of lint warning "has return(e); and return;"
@
text
@a0 1

d9 1
a9 1
/* RcsId ("$Header: RCS/allpaths.c,v 1.15 90/09/25 16:35:16 kemnitz Exp Locker: kemnitz $"); */
d16 1
a16 1
#include <strings.h>	/* XXX style */
a27 10
/* #include "allpaths.h"
   #include "internal.h"
   #include "indxpath.h"
   #include "orindxpath.h"
   #include "joinrels.h"
   #include "prune.h"
 */



d43 1
a43 1
find_paths (rels,nest_level,sortkeys)
d47 2
a48 2
    if ( length (rels) > 0 && nest_level > 0 ) {
	/* Set the number of join (not nesting) levels yet to be processed. */
d50 1
a50 1
	int levels_left = length (rels);
d53 2
a54 2
	find_rel_paths (rels,nest_level,sortkeys);
	if ( !sortkeys && (1 >= levels_left)) {
d56 1
a56 1
	    return (rels);   
d59 12
a70 9
	       
	    /* Joins or sorts are required. */
	    /* Compute the sizes, widths, and selectivities required for */
	    /* further join processing and/or sorts. */
	    LispValue rel;
	    set_rest_relselec (rels);
	    foreach (rel,rels) {
		set_size (CAR(rel),compute_rel_size (CAR(rel)));
		set_width (CAR(rel),compute_rel_width (CAR(rel)));
d72 1
a72 1
	    if(1 >= levels_left) {
d74 1
a74 1
	    } 
d76 4
a79 4
		return (find_join_paths (rels,levels_left - 1,nest_level));
	    }
	}
    }
d88 1
a88 1
 *    	if possible (indices are not considered for lower nesting levels).
d102 1
a102 1
find_rel_paths (rels,level,sortkeys)
d109 1
a109 1
     foreach (temp,rels) {
d113 1
a113 3
	  sequential_scan_list =
	    lispCons(create_seqscan_path (rel),
		     LispNil);
d115 5
a119 5
	  if (level > 1) {
	       set_pathlist (rel,sequential_scan_list);
	       set_unorderedpath (rel,sequential_scan_list);
	       set_cheapestpath (rel,sequential_scan_list);
	  } 
a120 4
	       
	       /* XXX Because these routines destructively modify the 
		* relation data structures, the "let*" here is significant. 
		*/
d122 1
a122 1
		 find_index_paths (rel,find_relation_indices(rel),
d126 1
a126 1
		 create_or_index_paths (rel,get_clauseinfo (rel));
d128 2
a129 2
	       set_pathlist (rel,add_pathlist (rel,sequential_scan_list,
					       append (rel_index_scan_list,
d131 1
a131 1
	  } 
d134 1
a134 2
	   * If it is not 
	   * the cheapest path, prune it.
d136 1
d138 2
a139 1
	  prune_rel_path (rel,last_element (get_pathlist (rel))); 
a140 3
     }
     return(rels);   /* it should have been destructively modified above */

d149 3
a151 3
 *	In XPRS, bushy tree plans will by generated:
 *	Find all possible joinpaths (bushy trees) for a query by systematically
 *	finding ways to join relations (both original and derived) together.
d168 1
a168 1
find_join_paths (outer_rels,levels_left,nest_level)
d172 2
a173 6
  LispValue rel;
  LispValue prune_oldrels();
#ifdef _xprs_
  LispValue merge_joinrels();
  LispValue final_join_rels();
#endif /* _xprs_ */
d175 5
a179 3
  /* Determine all possible pairs of relations to be joined at this level. */
  /* Determine paths for joining these relation pairs and modify 'new-rels' */
  /* accordingly, then eliminate redundant join relations. */
d181 1
a181 1
  LispValue new_rels = find_join_rels (outer_rels);
d183 1
a183 4
  /* In case of bushy trees */
  /* if there is still a join between a join relation and another  */
  /* relation, add a new joininfo that involves the join relation  */
  /* to the joininfo list of the other relation  */
d185 2
a186 1
  find_all_join_paths (new_rels,outer_rels,nest_level);
d188 9
d198 5
a202 2
  new_rels = prune_joinrels (new_rels);
  prune_rel_paths (new_rels);
d204 15
a218 3
#ifdef _xprs_
  add_new_joininfos (new_rels,outer_rels);
#endif /* _xprs_ */
d220 12
a231 23
  foreach (rel,new_rels) {
       set_width (CAR(rel),compute_rel_width (CAR(rel)));
  }

#ifdef _xprs_
  outer_rels = prune_oldrels (outer_rels);
  outer_rels = merge_joinrels (new_rels,outer_rels);
#endif  /* _xprs_ */

  if(levels_left == 1) {
#ifdef _xprs_
	 return (final_join_rels (outer_rels));
#else /* _xprs_ */
       return (new_rels);
#endif /* _xprs_ */
  } 
  else {
#ifdef _xprs_
	return (find_join_paths (outer_rels,levels_left - 1,nest_level));
#else /* _xprs_ */
       return (find_join_paths (new_rels,levels_left - 1,nest_level));
#endif /* _xprs_ */
  } 
a233 1
/* The following functions are solely for the purpose of debugging */
d236 4
d244 1
a244 1
char *xStrcat (s1, s2)
d253 1
a253 1
printclauseinfo (ind,cl)
d260 1
a260 1
    foreach (xc,cl) {
d262 1
a262 1
       if (c == (CInfo)NULL) continue;
d264 1
a264 1
       printf("\n%sOp:		%u",indent,get_opno(get_op(get_clause (c))));
d266 1
a266 1
       lispDisplay (get_varid(get_leftop (get_clause (c))),0);
d268 2
a269 2
       lispDisplay (get_varid(get_rightop (get_clause (c))),0);
       printf("\n%sSelectivity:	%lg\n",indent,get_selectivity (c));
a272 1
#ifdef	_xprs_
d274 1
a274 1
printjoininfo (ind,jl)
d282 1
a282 1
    foreach (xj,jl) {
d284 1
a284 1
	if (joininfo_inactive(j)) continue;
d287 1
a287 1
	lispDisplay (get_otherrels (j),0);
d289 1
a289 1
	printclauseinfo (xStrcat(indent, "	"),get_jinfoclauseinfo(j));
a291 1
#endif	/* defined(_xprs_) */
d294 1
a294 1
printpath (ind,p)
d300 1
a300 1
	if (p == (Path)NULL) return;
d303 4
a306 4
	lispDisplay(get_relids (get_parent (p)),0);
	printf("\n%sPathType:	%ld",indent,get_pathtype (p));
	printf("\n%sCost:	%lg",indent,get_path_cost (p));
	switch (get_pathtype (p))  {
d309 1
a309 1
		printclauseinfo (xStrcat (indent,"	"),get_pathclauseinfo (p));
d311 1
a311 1
		printpath (xStrcat (indent,"	"),get_outerjoinpath (p));
d313 2
a314 2
		printpath (xStrcat (indent,"	"),get_innerjoinpath (p));
		printf("%sOuterJoinCost:	%lg",indent,get_outerjoincost (p));
d316 1
a316 1
		lispDisplay (get_joinid (p),0);
d320 1
a320 1
                printclauseinfo (xStrcat (indent,"       "),get_pathclauseinfo (p
d323 1
a323 1
                printpath (xStrcat (indent," "),get_outerjoinpath (p));
d325 2
a326 2
                printpath (xStrcat (indent," "),get_innerjoinpath (p));
                printf("%sOuterJoinCost:        %lg",indent,get_outerjoincost (p
d329 1
a329 1
                lispDisplay (get_joinid (p),0);
d331 1
a331 1
		lispDisplay (get_path_mergeclauses (p),0);
d333 1
a333 1
		lispDisplay (get_outersortkeys (p),0);
d335 1
a335 1
		lispDisplay (get_innersortkeys (p),0);
d339 1
a339 1
                printclauseinfo (xStrcat (indent,"       "),get_pathclauseinfo (p
d342 1
a342 1
                printpath (xStrcat (indent," "),get_outerjoinpath (p));
d344 2
a345 2
                printpath (xStrcat (indent," "),get_innerjoinpath (p));
                printf("%sOuterJoinCost:        %lg",indent,get_outerjoincost (p
d348 1
a348 1
                lispDisplay (get_joinid (p),0);
d350 1
a350 1
		lispDisplay (get_path_hashclauses (p),0);
d352 1
a352 1
		lispDisplay (get_outerhashkeys (p),0);
d354 1
a354 1
		lispDisplay (get_innerhashkeys (p),0);
d358 1
a358 1
		lispDisplay (get_indexqual (p),0);
d365 1
a365 1
printpathlist (ind, pl)
d372 1
a372 1
    foreach (xp,pl) {
d374 1
a374 1
	printpath (indent,p);
d379 1
a379 1
printrels (ind,rl)
d386 1
a386 1
    foreach (xr,rl) {
d388 1
a388 1
	if (r == (Rel)NULL) continue;
d391 2
a392 2
	lispDisplay(get_relids (r),0);
	printf("\n%sSize:	%u",indent,get_size (r));
d394 1
a394 1
	printpathlist (xStrcat(indent,"	"),get_pathlist (r));
d396 1
a396 2
	printclauseinfo (xStrcat(indent,"	"),get_clauseinfo (r));
#ifdef	_xprs_
d398 1
a398 2
	printjoininfo (xStrcat(indent,"	"),get_joininfo (r));
#endif	/* defined(_xprs_) */
d403 1
a403 1
PrintRels (rl)
d406 1
a406 1
    printrels ("",rl);
d411 1
a411 1
PRel (r)
d414 1
a414 1
    printrels ("",lispCons (r,LispNil));
@


1.15
log
@Updating from revision 1.14 to revision 1.15
@
text
@d10 1
a10 1
/* RcsId ("$Header: RCS/allpaths.c,v 1.15 90/08/14 11:09:18 cimarron Exp $"); */
d88 1
@


1.14
log
@changes to support MergeJoins in the executor.
@
text
@d10 1
a10 1
/* RcsId ("$Header: RCS/allpaths.c,v 1.13 89/10/10 12:10:37 hirohama Exp $"); */
d17 5
a21 2
#include "pg_lisp.h"
#include "relation.h"
a27 3

#include <strings.h>	/* XXX style */

@


1.13
log
@"strcat" -> "xStrcat"
@
text
@d10 1
a10 1
/* RcsId ("$Header: RCS/allpaths.c,v 1.12 89/10/09 18:06:08 hirohama Exp Locker: hirohama $"); */
d323 1
a323 1
	case T_MergeSort:
@


1.12
log
@removed local definition of strcat
other calls to strcat rely on side effect to s1
@
text
@d10 1
a10 1
/* RcsId ("$Header: RCS/allpaths.c,v 1.11 89/09/29 22:37:09 hirohama Exp Locker: hirohama $"); */
d243 5
a247 1
char *strcat (s1, s2)
a253 1
*/
d293 1
a293 1
	printclauseinfo (strcat(indent, "	"),get_jinfoclauseinfo(j));
d314 1
a314 1
		printclauseinfo (strcat (indent,"	"),get_pathclauseinfo (p));
d316 1
a316 1
		printpath (strcat (indent,"	"),get_outerjoinpath (p));
d318 1
a318 1
		printpath (strcat (indent,"	"),get_innerjoinpath (p));
d325 1
a325 1
                printclauseinfo (strcat (indent,"       "),get_pathclauseinfo (p
d328 1
a328 1
                printpath (strcat (indent," "),get_outerjoinpath (p));
d330 1
a330 1
                printpath (strcat (indent," "),get_innerjoinpath (p));
d344 1
a344 1
                printclauseinfo (strcat (indent,"       "),get_pathclauseinfo (p
d347 1
a347 1
                printpath (strcat (indent," "),get_outerjoinpath (p));
d349 1
a349 1
                printpath (strcat (indent," "),get_innerjoinpath (p));
d399 1
a399 1
	printpathlist (strcat(indent,"	"),get_pathlist (r));
d401 1
a401 1
	printclauseinfo (strcat(indent,"	"),get_clauseinfo (r));
d404 1
a404 1
	printjoininfo (strcat(indent,"	"),get_joininfo (r));
@


1.11
log
@removed printjoininfo which needs joininfo_inactive unless _xprs_
@
text
@d10 1
a10 1
/* RcsId ("$Header: RCS/allpaths.c,v 1.10 89/09/29 14:39:09 hong Exp Locker: hirohama $"); */
d26 1
d28 1
d242 1
d250 1
@


1.10
log
@added in bushy tree stuffs.  only function
find_join_paths() is modified.
@
text
@d10 1
a10 1
/* RcsId ("$Header: RCS/allpaths.c,v 1.9 89/09/05 17:17:05 mao C_Demo_1 Locker: hong $"); */
d269 1
d289 1
d395 1
d398 1
@


1.9
log
@Working version of C-only demo
@
text
@d10 1
a10 1
/* RcsId ("$Header: RCS/allpaths.c,v 1.8 89/08/23 16:02:28 ong Exp Locker: ong $"); */
d161 4
d167 2
a168 1
 *    		are to be found	
d173 2
a174 1
 *    	Returns the final level of join relations.
d186 5
d198 5
d209 4
d216 6
d223 3
d227 1
d230 3
d234 1
d236 175
@


1.8
log
@planner supports all but rules and mergesort
@
text
@d10 1
a10 1
/* RcsId ("$Header: allpaths.c,v 1.7 89/08/04 14:27:05 ong Locked $"); */
@


1.7
log
@reorganised header files
@
text
@d10 1
a10 1
/* RcsId ("$Header: allpaths.c,v 1.6 89/08/04 13:22:56 goh Locked $"); */
d63 1
a63 1
	if ( !sortkeys && (1 == levels_left)) {
d78 1
a78 1
	    if(1 == levels_left) {
d148 3
a150 2
    
	  prune_rel_path (rel,last_element (get_pathlist (rel)));
a187 1
  new_rels = prune_joinrels (new_rels);
a188 1
  /* Compute cost and sizes, then go on to next level of join processing. */
d190 1
d192 1
@


1.6
log
@checkin for retrieve (x.all)
@
text
@d10 1
a10 1
/* RcsId ("$Header: allpaths.c,v 1.5 89/08/01 14:39:28 goh Locked $"); */
a17 1
#include "internal.h"
d19 15
a33 5
#include "allpaths.h"
#include "indxpath.h"
#include "orindxpath.h"
#include "joinrels.h"
#include "prune.h"
@


1.5
log
@retrieve (x=1) checkin
@
text
@d10 1
a10 1
/* RcsId ("$Header: allpaths.c,v 1.4 89/08/01 14:39:03 goh Locked $"); */
d66 2
a67 2
		set_size (rel,compute_rel_size (rel));
		set_width (rel,compute_rel_width (rel));
d90 2
a91 1
 *    	Returns 'rels'.
d102 5
a106 1
     LispValue rel;
d108 5
a112 3
     foreach (rel,rels) {
	  LispValue sequential_scan_list = lispCons(create_seqscan_path (rel),
						    LispNil);
d184 1
a184 1
       set_width (rel,compute_rel_width (rel));
@


1.4
log
@retrieve (x=1) checkin
@
text
@d10 1
a10 1
/* RcsId ("$Header: allpaths.c,v 1.3 89/07/25 17:34:44 ong Exp $"); */
@


1.3
log
@Phase III
@
text
@d10 1
a10 1
/* RcsId ("$Header: allpaths.c,v 1.2 89/07/20 15:56:23 ong Locked $"); */
d47 12
a58 12
     if ( length (rels) > 0 && nest_level > 0 ) {
  /* Set the number of join (not nesting) levels yet to be processed. */
	  
	  int levels_left = length (rels);

	  /* Find the base relation paths. */
	  find_rel_paths (rels,nest_level,sortkeys);
	  if ( and ( not (sortkeys), (1 == levels_left))) {
	       /* Unsorted single relation, no more processing is required. */
	       return (rels);   
	  } 
	  else {
d60 17
a76 17
	       /* Joins or sorts are required. */
	       /* Compute the sizes, widths, and selectivities required for */
	       /* further join processing and/or sorts. */
	       LispValue rel;
	       set_rest_relselec (rels);
	       foreach (rel,rels) {
		    set_size (rel,compute_rel_size (rel));
		    set_width (rel,compute_rel_width (rel));
	       }
	       if(1 == levels_left) {
		    return(rels); 
	       } 
	       else {
		    return (find_join_paths (rels,levels_left - 1,nest_level));
	       }
	  }
     }
d104 2
a105 1
	  LispValue sequential_scan_list = list (create_seqscan_path (rel));
d108 2
a109 2
	       set_unordered_path (rel,sequential_scan_list);
	       set_cheapest_path (rel,sequential_scan_list);
d118 2
a119 2
				   get_clause_info(rel),
				   get_join_info(rel),sortkeys);
d121 1
a121 1
		 create_or_index_paths (rel,get_clause_info (rel));
d176 1
a176 1
  for (rel= CAR(new_rels); new_rels != LispNil; new_rels = CDR(new_rels)) {
@


1.2
log
@Phase II checkin.  May have a problem with the 
return value of function: find_rel_path().
@
text
@d10 1
a10 1
/* RcsId ("$Header: allpaths.c,v 1.1 89/07/10 15:13:05 ong Locked $"); */
d44 2
a45 1
     LispValue rels,nest_level,sortkeys ;
d47 1
a47 1
     if ( and (length (rels) > 0,nest_level > 0) ) {
a165 1
  /* XXX - let form, maybe incorrect */
d176 1
a176 1
    set_width (rel,compute_rel_width (rel));
d179 2
a180 2
      new_rels;
    } 
d182 1
a182 1
    find_join_paths (new_rels,levels_left - 1,nest_level);
@


1.1
log
@Initial revision
@
text
@d10 1
a10 1
/* RcsId ("$Header: allpaths.c,v 1.1 89/04/27 21:03:55 ong Locked $"); */
d18 7
a25 2
extern LispValue find_rel_paths();
extern LispValue find_join_paths();
d27 1
d46 4
a49 4
  if ( and (length (rels) > 0,nest_level > 0) ) {
    /* Set the number of join (not nesting) levels yet to be processed. */
    /* XXX - let form, maybe incorrect */
    LispValue levels_left = length (rels);
d51 25
a75 25
    /* Find the base relation paths. */
    find_rel_paths (rels,nest_level,sortkeys);
    if ( and ( not (sortkeys), (1 == levels_left))) {
      /* Unsorted single relation, no more processing is required. */
      rels;       /* returns rels */
    } 
    else {
      
      /* Joins or sorts are required. */
      /* Compute the sizes, widths, and selectivities required for */
      /* further join processing and/or sorts. */
      LispValue rel;
      set_rest_relselec (rels);
      for (rel = car(rels); rels != LispNil; rels = cdr(rels)) {
	set_size (rel,compute_rel_size (rel));
	set_width (rel,compute_rel_width (rel));
      }
      if(1 == levels_left) {
	rels;         /* returns rels */
      } 
      else {
	find_join_paths (rels,levels_left - 1,nest_level);
      }
    }
  }
d93 2
a94 2
/*  .. find-paths
 */
d97 2
a98 1
     LispValue rels,level,sortkeys ;
d100 1
a100 16
  LispValue rel;
  /* XXX Lisp Dolist - may be wrong. need to return rels */
  for (rel = car(rels) ; rels != LispNil ; rels = cdr(rels)) {
    /* XXX - let form, maybe incorrect */
    LispValue sequential_scan_list = list (create_seqscan_path (rel));
    if (level > 1) {
      set_pathlist (rel,sequential_scan_list);
      set_unordered_path (rel,sequential_scan_list);
      set_cheapest_path (rel,sequential_scan_list);
      
    } 
    else {
      
      /* XXX Because these routines destructively modify the */
      /* relation data structures, the "let*" here is significant. */
      /* XXX - let form, may be incorrect */
d102 18
a119 5
      LispValue rel_index_scan_list = 
	find_index_paths (rel,find_relation_indices(rel),get_clause_info(rel),
			  get_join_info(rel),sortkeys);
      LispValue or_index_scan_list = 
	create_or_index_paths (rel,get_clause_info (rel));
d121 4
a124 3
      set_pathlist (rel,add_pathlist (rel,sequential_scan_list,
		    append (rel_index_scan_list,or_index_scan_list)));
    } 
d126 4
a129 2
    /* The unordered path is always the last in the list.  If it is not */
    /* the cheapest path, prune it. */
d131 4
a134 2
    prune_rel_path (rel,last_element (get_pathlist (rel)));
  }
d157 2
a158 1
     LispValue outer_rels,levels_left,nest_level ;
d175 1
a175 1
  for (rel= car(new_rels); new_rels != LispNil; new_rels = cdr(new_rels)) {
@