/*     
 *      FILE
 *     	path
 *     
 *      DESCRIPTION
 *     	Routines to find possible search paths for processing a query
 *     
 */
/* RcsId("$Header: /private/postgres/src/planner/path/RCS/allpaths.c,v 1.28 1992/07/23 15:15:17 joey Exp $"); */

/*     
 *      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));
}
