SQL Server

开发平台：
Unix_Linux

optim.c：源码内容
							/*
 *  optim.c - optimization of input tree for synthesator
 *
 *  This file is a part of GNU SQL Server
 *
 *  Copyright (c) 1996, 1997, Free Software Foundation, Inc
 *  Developed at the Institute of System Programming
 *  This file is written by Konstantin Dyshlevoi
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 *
 *  Contacts: gss@ispras.ru
 *
 */
/* $Id: optim.c,v 1.246 1997/03/31 11:02:34 kml Exp $ */
#include "global.h"
#include "syndef.h"
#include "inprtyp.h"
#include <assert.h>
#include "tassert.h"
#define USE_INDEXES   1
#define USE_SIMP_PRED 1
#define OPEN_SCAN_COST 10
#define DEFAULT_SEL    0.5
#define PRINT(x, y) /* PRINTF ((x, y)) */
#define PRINT_(x)   /* PRINTF ((x))    */
extern DataUnit *data_st;
extern i4_t   dt_ind, dt_max;
extern SH_Info *tr_arr;
extern i4_t tr_cnt, tr_max;
static i4_t  MAX_LNG = ((u4_t)(-1))/2;
static float FLT_MAX_LNG = (float)(((u4_t)(-1))/2);
MASK *TblBits, *TblAllBits, _AllTblMsk;
TXTREF *tbl_ind;
i4_t TblNum;
i4_t *CurTblOrder, *tab_col_num;
float *NumRowScans;
float BestCost;
i4_t *NumRows; /* number of rows for every table        */
i4_t DisNum;    /* number of AND sons in WHERE           *
	        * ( or 1 if there isn't AND in root )   */
i4_t SPNum;     /* number of Simple Predicates for Query */
Simp_Pred_Info *SP_Arr;
SP_Ind_Info **SP_Ind_Arr;
Col_Stat_Info *col_stat;
i4_t *fin_nums;
/* optimizator works only with input trees of procedurizator */
#define CHECK_SEL_ERR(er) { if (er < 0) yyfatal (" Can't get statistic info n"); }
float
Mk_Sel (i4_t tbl_num, i4_t col_num, TXTREF col_node, TXTREF SP_Tree, i4_t prdc_num)
     /* estimation of selectivity for predicate */
{
  TXTREF col_ptr   = DOWN_TRN (SP_Tree);
  TXTREF right_ptr = RIGHT_TRN (col_ptr);
  TXTREF cur_ptr;
  VCBREF Tab, CurClm;
  float sel = DEFAULT_SEL, min_sel = 1.0 / ((float) NumRows[tbl_num]);
  i4_t sign = 0, err, op = CODE_TRN (SP_Tree);
  col_stat_info **col_info;
  
  if (op == EQU)
    return min_sel;
  
  if (SP_Arr[prdc_num].SQ_cost || SP_Arr[prdc_num].Depend != TblBits[tbl_num]
      || SP_Arr[prdc_num].SP_Num != 1 || !Is_Comp_Code (op))
    return sel;
  
  for (cur_ptr = right_ptr; cur_ptr; cur_ptr = DOWN_TRN (cur_ptr))
    if (CODE_TRN (cur_ptr) == UMINUS)
      sign = BitNOT (sign);
    else
      if (CODE_TRN (cur_ptr) != NOOP)
	break;
  
  if (cur_ptr && CODE_TRN (cur_ptr) == CONST)
    /* SP has type : col_name 'op' constant */
    {
      VADR nd;
      DataUnit cnst;
      
      nd = VMALLOC (1, TRNode);
      prepare_CONST (cur_ptr, nd);
      cnst = *V_PTR (V_PTR (nd, TRNode)->Ptr.off, DataUnit);
      vmfree (nd);
      
      if (sign)
	{
	  DtPush;
	  DtCurEl = cnst;
	  err = oper (UMINUS, 1);
	  CHECK_SEL_ERR (err);
	  cnst = DtCurEl;
	  DtPop;
	}
      /* there is right value of SP in *const now */
      
      Tab = COR_TBL (COL_TBL (col_node));
      if (CODE_TRN (Tab) == TMPTABLE)
        return sel;
      for (CurClm = TBL_COLS (Tab); CurClm; CurClm = RIGHT_TRN (CurClm))
	if (COL_NO (CurClm) == col_num)
	  break;
      assert (CurClm);
      
      col_info = (col_stat_info **)(&(COL_STAT (CurClm)));
      if (!(*col_info))
	/* making statistic info about column : min & max values */
	{
	  *col_info = TYP_ALLOC (1, col_stat_info);
	  err = get_col_stat ((TBL_TABID (Tab)).untabid, col_num, *col_info);
	  CHECK_SEL_ERR (err);
	  
	  if ((*col_info)->min.dat.nl_fl == NULL_VALUE ||
	      (*col_info)->max.dat.nl_fl == NULL_VALUE)
	    {
	      i4_t spn, flist[2], nf = 0;
              i4_t min_change_fl = FALSE, max_change_fl = FALSE;
	      char fl[2];
	      DataUnit *du[2];
	      col_change_info ch_info;
              
	      if ((*col_info)->min.dat.nl_fl == NULL_VALUE)
		{
		  du[nf] = &((*col_info)->min);
		  du[nf]->type = COL_TYPE (CurClm);
		  min_change_fl = TRUE;
		  flist[nf] = col_num;
		  fl[nf++] = FN_MIN;
		}
	      if ((*col_info)->max.dat.nl_fl == NULL_VALUE)
		{
		  du[nf] = &((*col_info)->max);
		  du[nf]->type = COL_TYPE (CurClm);
		  max_change_fl = TRUE;
		  flist[nf] = col_num;
		  fl[nf++] = FN_MAX;
		}
	      
	      err = func (&TBL_TABID (Tab), &spn, 0, NULL, du, nf, flist, fl);
	      CHECK_SEL_ERR (err);
              ch_info.del_min.dat.nl_fl = UNKNOWN_VALUE;
              ch_info.del_max.dat.nl_fl = UNKNOWN_VALUE;
              
              if (min_change_fl)
                ch_info.ins_min = (*col_info)->min;
              else
                ch_info.ins_min.dat.nl_fl = UNKNOWN_VALUE;
              
              if (max_change_fl)
                ch_info.ins_max = (*col_info)->max;
              else
                ch_info.ins_max.dat.nl_fl = UNKNOWN_VALUE;
              
              put_col_stat ((TBL_TABID (Tab)).untabid, col_num, &ch_info);
	    }
	}
      
      if ((*col_info)->min.dat.nl_fl == NULL_VALUE ||
	  (*col_info)->max.dat.nl_fl == NULL_VALUE)
	/* column is empty or consists only of NULL VALUES */
	sel = min_sel;
      else
	{
	  sel = sel_const (op, &cnst, &((*col_info)->min), &((*col_info)->max));
	  CHECK_SEL_ERR (sel);
	  if (!sel)
	    sel = min_sel;
	}
    }
  
  return sel;
} /* Mk_Sel */
void
Mk_SP_Info (TXTREF SP_Tree, i4_t prdc_num)
/* Making information about simple predicate               *
 * SP_Tree and placing it to SP_Ind_Arr for correspondent  *
 * table and predicate (its number = prdc_num).            */
{
  TXTREF col_ptr = DOWN_TRN (SP_Tree), col_node, CurInd;
  MASK Depend;
  i4_t tbl_num;
  SP_Ind_Info *res;
  if (CODE_TRN (col_ptr) == NOOP)
    col_ptr = DOWN_TRN (col_ptr);
  assert (col_ptr && CODE_TRN (col_ptr) == COLPTR);
  col_node = OBJ_DESC (col_ptr);
  assert (col_node && CODE_TRN (col_node) == SCOLUMN);
  
  Depend = COR_MASK (COL_TBL (col_node));
  
  /* finding of corresponding table : */
  for (tbl_num = 0; tbl_num < TblNum; tbl_num++)
    if (TblBits[tbl_num] == Depend)
      break;
  assert (tbl_num < TblNum);
  
  res = SP_Ind_Arr[tbl_num] + prdc_num;
    
  res->ColNum = COL_NO (col_node);
  res->category = (CODE_TRN (SP_Tree) == EQU) ? 1 : 2;
  res->Sel = Mk_Sel (tbl_num, res->ColNum, col_node, SP_Tree, prdc_num);
  
  for (CurInd = tbl_ind[tbl_num]; CurInd; CurInd = RIGHT_TRN (CurInd))
    if (COL_NO (OBJ_DESC (DOWN_TRN (CurInd))) == res->ColNum)
      break;
  res->IndExists = (CurInd != TNULL);
  res->tree = SP_Tree;
} /* Mk_SP_Info */
float
EstCostOrder (i4_t *res_row_num)
/* Making estimation of query cost accordingly      *
 * current order of tables in query                 *
 * Functin returns value < 0  if it decides not to  *
 * make all steps of estimation because the cost of *
 * this order >> BestCost (if BestCost > 0)         *
 * In another case it returns estimated cost (>=0)  */
{
  MASK Depend = _AllTblMsk;
  i4_t tbl_num, prdc_num, i, real_num, ColNum;
  float cost_all = 0.0, row_num = 1.0;
  float ind_best_sel, sel;
  SP_Ind_Info *CurIndInfo;
  
  /* estimation of the cost of tables scanning */
  for (tbl_num = 0; tbl_num < TblNum; tbl_num++)
    {
      ind_best_sel = 1.0;
      real_num = CurTblOrder [tbl_num];
      TblAllBits[tbl_num] = Depend = BitOR (Depend, TblBits [real_num]);
      
      /* init of array for information about culumns */
      for (i = 0; i < tab_col_num[real_num]; i++)
	col_stat[i].Sel = 1.0;
      
      /* checking information about SPs for current table */
      for (prdc_num = 0; prdc_num < SPNum; prdc_num++)
	if (!(SP_Arr[prdc_num].flag) /* this predicate wasn't used yet */ &&
	    CAN_BE_USED (SP_Arr[prdc_num].Depend, Depend)
	    /* predicate can be used now */)
	  {
	    SP_Arr[prdc_num].flag++;
	    CurIndInfo = (SP_Ind_Arr[real_num]) + prdc_num;
	    if (CurIndInfo->Sel)
	      /* this predicate is SP for current table */
	      {
		ColNum = CurIndInfo->ColNum;
		if (col_stat[ColNum].Sel > CurIndInfo->Sel)
		  {
		    col_stat[ColNum].Sel = CurIndInfo->Sel;
		    if (CurIndInfo->IndExists /* there is index for the column of this SP */
			&& col_stat[ColNum].Sel < ind_best_sel)
		      ind_best_sel = col_stat[ColNum].Sel;
		  }
	      }
	  }
      
     /* finding of common selectivity of all simple predicates for current table */
      for (i = 0, sel = 1.0; i < tab_col_num[real_num]; i++)
	sel *=col_stat[i].Sel;
     
      /* adding of default selectivity for the rest of predicates */
      for (prdc_num = SPNum; prdc_num < DisNum; prdc_num++)
	if (!(SP_Arr[prdc_num].flag) /* this predicate wasn't used yet */ &&
	    CAN_BE_USED (SP_Arr[prdc_num].Depend, Depend)
	    /* predicate can be used now */)
	  {
	    SP_Arr[prdc_num].flag++;
            sel *= DEFAULT_SEL;
          }
      
      NumRowScans [tbl_num] = NumRows[real_num] * ind_best_sel * row_num;
      /* in NumRowScans [i] - estimated number of row's readings from i-th table */
      cost_all += NumRowScans [tbl_num] + OPEN_SCAN_COST * row_num;
      row_num *= NumRows[real_num] * sel;
      
    } /* for tbl_num: tables handling */
      
  for (prdc_num = 0; prdc_num < DisNum; prdc_num++)
    SP_Arr[prdc_num].flag = 0;
      
  /* adding of the cost of all subqueries */
  for (prdc_num = 0; prdc_num < DisNum; prdc_num++)
    {
      for (tbl_num = 0; tbl_num < TblNum; tbl_num++)
        if (CAN_BE_USED (SP_Arr[prdc_num].SQ_deps, TblAllBits[tbl_num]))
          break;
      assert (tbl_num < TblNum);
      
      /* tbl_num - number of the last (in order) table *
       * that is referenced in the predicate           */
      cost_all += SP_Arr[prdc_num].SQ_cost * NumRowScans [tbl_num];
    }
  
  *res_row_num = (row_num < 1.0) ? 1 :
    ((row_num < FLT_MAX_LNG) ? (i4_t)row_num : MAX_LNG);
  
  return cost_all;
} /* EstCostOrder */
i4_t *
NextOrder (void)
/* making in array CurTblOrder[] next order of tables' numbers *
 * returns NULL if all orders was already generated            *
 *	   else - pointer to array with new order              */
{
  i4_t i, j, bound_vl, bound_num;
  
  for (fin_nums[0] = CurTblOrder[TblNum - 1], i = TblNum - 1; i; i--)
    if (CurTblOrder[i - 1] < CurTblOrder[i])
      break;
    else
      fin_nums[TblNum - i] = CurTblOrder[i - 1];
  
  if (!i)
    return NULL; /* all orders was generated */
  
  bound_num = i - 1;
  bound_vl = CurTblOrder[bound_num];
  
  for (j = 0; fin_nums[j] < bound_vl; j++)
    CurTblOrder[i++] = fin_nums[j];
  
  CurTblOrder[bound_num] = fin_nums[j++];
  CurTblOrder[i++] = bound_vl;
    
  for (; i < TblNum; i++, j++)
    CurTblOrder[i] = fin_nums[j];
  
  return CurTblOrder;
} /* NextOrder */
float
opt_query (TXTREF FromNode, i4_t *res_row_num)
     /* returns the cost of query */
{
  TXTREF sp_tree, fir_el, last_el = TNULL, CurInd, Ind, CurIndCol;
  TXTREF ScanNode, Tab, SelectNode, WhereNode = TNULL, WhereTree = TNULL;
  i4_t i, j, k, ColNum, tbl_num, prdc_num;
  i4_t sp_clm_tab_num; /* number of columns for which there are simple *
                       * predicates only for table (not for index)    */
  Simp_Pred_Info TmpEl;
  VADR *Tab_SP, *Ind_SP;
  VADR Tree;
  MASK Depend, tmp_dep, *CurTblBits;
  i4_t real_num, CurTblNum;
  i4_t *BestTblOrder;
  TXTREF *TblPtr, TblPtrCur;
  SP_Ind_Info *CurIndInfo, *Heap = NULL;
  Col_Stat_Info best_ind_info;
  i4_t max_col_num = 0, unused_prdc, Cur_in_Heap;
  MASK AllTblMsk;
  float cost, sel, tmp_build_cost = 0.0;
  TRNode *trnode_dn;
  VADR trnode_dn_rh;
  i4_t categ_1, categ_2;
  i4_t row_num, best_row_num = 0;
  
  SelectNode = RIGHT_TRN (FromNode);
  WhereNode = (SelectNode) ? RIGHT_TRN (SelectNode) : TNULL;
  if (WhereNode)
    {
      if (CODE_TRN (WhereNode) != WHERE)
	WhereNode = RIGHT_TRN (WhereNode);
    }
  
  CurTblNum = ARITY_TRN (FromNode);
  assert (CurTblNum > 0);
  CurTblBits   = TYP_ALLOC (CurTblNum, MASK);
  for (tbl_num = 0, TblPtrCur = DOWN_TRN (FromNode);
       tbl_num < CurTblNum; tbl_num++, TblPtrCur = RIGHT_TRN (TblPtrCur))
    CurTblBits[tbl_num] = COR_MASK (TABL_DESC (TblPtrCur));
  
  if (WhereNode)
    {
      Simp_Pred_Info *SP_temp;
      WhereTree = DOWN_TRN (WhereNode);
      DisNum = SP_Extract (WhereTree, CurTblBits, CurTblNum, &SP_temp);
      /* after function SP_Extract tree WhereTree can't be used */
      SP_Arr = SP_temp;
    }
  else
    {
      DisNum = 0;
      SP_Arr = NULL;
    }
  
  SPNum        = 0;
  TblNum       = CurTblNum;
  TblBits      = CurTblBits;
  fin_nums     = TYP_ALLOC (TblNum, i4_t);
  BestTblOrder = TYP_ALLOC (TblNum, i4_t);
  CurTblOrder  = TYP_ALLOC (TblNum, i4_t);
  tab_col_num  = TYP_ALLOC (TblNum, i4_t);
  TblPtr       = TYP_ALLOC (TblNum, TXTREF);
  SP_Ind_Arr   = TYP_ALLOC (TblNum, SP_Ind_Info *);
  NumRows      = TYP_ALLOC (TblNum, i4_t);
  TblAllBits   = TYP_ALLOC (TblNum, MASK);
  tbl_ind      = TYP_ALLOC (TblNum, TXTREF);
  NumRowScans  = TYP_ALLOC (TblNum, float);
  
  /* filling of statistic information about tables */
  for (tbl_num = 0, TblPtrCur = DOWN_TRN (FromNode), AllTblMsk = 0;
       tbl_num < TblNum; tbl_num++, TblPtrCur = RIGHT_TRN (TblPtrCur))
    {
      ScanNode = TABL_DESC (TblPtrCur);
      TblPtr[tbl_num] = TblPtrCur;
      Tab = COR_TBL (ScanNode);
      tab_col_num[tbl_num] = ColNum = TBL_NCOLS (Tab);
      tbl_ind[tbl_num] = (CODE_TRN (Tab) == TABLE) ? IND_INFO (Tab) : TNULL;
      if (max_col_num < ColNum)
	max_col_num = ColNum;
      if (CODE_TRN (Tab) == TABLE)
	{
          i4_t rc = get_nrows ((TBL_TABID (Tab)).untabid);
          NumRows[tbl_num] = 2; /* for statistic using purpose */
          if (rc > 0)
            NumRows[tbl_num] = rc;
          else if (rc < 0) /* if error was registered */
            {
              yyerror("Required 'nrows' data was not found"); /*!!!!!*/
              errors --;
            }
 	}
      else
	{
	  assert (CODE_TRN (Tab) == TMPTABLE);
	  NumRows[tbl_num] = NROWS_EST (Tab);
	  tmp_build_cost += BUILD_COST (Tab);
	}
      AllTblMsk = BitOR (AllTblMsk, TblBits[tbl_num]);
    }
  _AllTblMsk = BitNOT (AllTblMsk);
  col_stat = (max_col_num) ? TYP_ALLOC (max_col_num, Col_Stat_Info): NULL;
  if (WhereNode)
    {
      assert (DisNum);
      /* all SP are moving to the beginning of SP_Arr */
      for (i = 0, j = DisNum - 1; i < j;)
	{
	  while (SP_Arr[i].SP_Num && i < j)
	    i++;
	  while (!(SP_Arr[j].SP_Num) && i < j)
	    j--;
	  if (i < j)
	    /* i-th and j-th elements are changed by places */
	    {
	      TmpEl = SP_Arr[i];
	      SP_Arr[i] = SP_Arr[j];
	      SP_Arr[j] = TmpEl;
	    }
	}
      assert (i == j);
      SPNum = (SP_Arr[i].SP_Num) ? i + 1 : i;
      /* there are (SPNum) Simple Predicates & (DisNum - SPNum) others */
      if (SPNum)
	{
	  Heap  = TYP_ALLOC (TblNum * SPNum, SP_Ind_Info);
	  for (tbl_num = 0, Cur_in_Heap = 0; tbl_num < TblNum;
               tbl_num++, Cur_in_Heap += SPNum)
	    {
	      SP_Ind_Arr[tbl_num] = Heap + Cur_in_Heap;
            }
	  for (prdc_num = 0; prdc_num < SPNum; prdc_num++)
	    for (sp_tree = SP_Arr[prdc_num].SP_Trees;
		 sp_tree; sp_tree = RIGHT_TRN (sp_tree))
	      /* for all interpretations of prdc_num-th disjunct as SP : */
	      Mk_SP_Info (sp_tree, prdc_num);
	}
    } /* if (WhereNode) */
  /* End of working structures filling */
  /* initial order of tables */
  for (tbl_num = 0; tbl_num < TblNum; tbl_num++)
    BestTblOrder[tbl_num] = CurTblOrder[tbl_num] = tbl_num;
  BestCost = 0.0;
  /* optimization of table order in query */
  PRINT_ ("n");
  do {
    /* EstCostOrder returns value < 0  if this function decided
       not to make all steps of estimation because the cost of
       this order >> BestCost */
    cost = EstCostOrder (&row_num);
    
    PRINT_ ("ntable order: (");
    for (i = 0; i < TblNum; i++)
      { PRINT ("%d ", CurTblOrder[i]); }
    PRINT (") cost = %f", cost);
    
    if (cost > 0 && (cost < BestCost || !BestCost))
      {
	for (tbl_num = 0; tbl_num < TblNum; tbl_num++)
	  BestTblOrder[tbl_num] = CurTblOrder[tbl_num];
	BestCost = cost;
	best_row_num = row_num;
      }
  } while (NextOrder ());
  PRINT_ ("n");
  /* NextOrder returns FALSE when all orders was generated, else - TRUE */
  assert (best_row_num);
  
  BestCost += tmp_build_cost;
  if (res_row_num)
    *res_row_num = best_row_num;
  
  /* changing of tables' order in query */
  for (tbl_num = 0, DOWN_TRN (FromNode) = TblPtr[BestTblOrder[0]];
       tbl_num < TblNum - 1; tbl_num++)
    RIGHT_TRN (TblPtr[BestTblOrder[tbl_num]]) =
      TblPtr[BestTblOrder[tbl_num+1]];
  RIGHT_TRN (TblPtr[BestTblOrder[tbl_num]]) = TNULL;
  unused_prdc = DisNum;
  if (USE_INDEXES)
    /* indexes choosing and forming of          *
     * Simple Predicates for tables and indexes */
    for (Depend = _AllTblMsk, tbl_num = 0; tbl_num < TblNum; tbl_num++)
      {
        sp_clm_tab_num = 0;
        real_num = BestTblOrder [tbl_num];
        ScanNode = TABL_DESC (TblPtr [real_num]);
        Tab = COR_TBL (ScanNode);	/* ScanNode must be not NULL */
        Depend = BitOR (Depend, TblBits [real_num]);
        /* @ if (CODE_TRN (Tab) != TABLE) continue; : can we use SPs for TMPTABLEs ? @ */
        COR_TAB_SP (ScanNode) = VMALLOC (TBL_NCOLS (Tab), VADR);
      
        /* init of array for information about culumns */
        for (i = 0; i < tab_col_num[real_num]; i++)
          col_stat[i].Sel = 1.0;
        /* checking information about SPs and compiling SPs in Tab_SP */
        for (prdc_num = 0; prdc_num < SPNum; prdc_num++)
          if (!(SP_Arr[prdc_num].flag) /* this SP wasn't used yet */ &&
              CAN_BE_USED (SP_Arr[prdc_num].Depend, Depend)
              /* SP can be used now */                               &&
              (SP_Ind_Arr[real_num][prdc_num]).Sel
              /* this predicate is SP for current table */             )
            {
              SP_Arr[prdc_num].flag++;
              unused_prdc--;
              CurIndInfo = (SP_Ind_Arr[real_num]) + prdc_num;
	    
              sp_tree = CurIndInfo->tree;
              Tree = Tr_RecLoad (sp_tree, &tmp_dep, FALSE, NULL);
	    
              /* saving dependency of right part of SP */
              assert ((trnode_dn = NextDn (V_PTR (Tree, TRNode))));
              trnode_dn_rh = (trnode_dn->Rh).off;
              if (trnode_dn_rh)
                SET (tr, trnode_dn_rh, NextRh (trnode_dn)->Depend);
	    
              ColNum = CurIndInfo->ColNum;
              if (col_stat[ColNum].Sel > CurIndInfo->Sel)
                col_stat[ColNum].Sel = CurIndInfo->Sel;
              if (CurIndInfo->category == 1)
                (col_stat[ColNum].num_categ_1)++;
              else
                (col_stat[ColNum].num_categ_2)++;
              Tab_SP = V_PTR (COR_TAB_SP (ScanNode), VADR);
              if (Tab_SP[ColNum])
                (V_PTR (Tree, TRNode)->Rh).off = Tab_SP[ColNum];
              else
                sp_clm_tab_num++;
              Tab_SP[ColNum] = Tree;
            }		/* if */
        /* index for current table choosing */
        if (tbl_ind[real_num]) /* there are indexes for current table */
          {
            Ind = TNULL;
            best_ind_info.Sel = 1.0;
            
            for (CurInd = tbl_ind[real_num]; CurInd; CurInd = RIGHT_TRN (CurInd))
              {
                sel = 1.0; /* in sel we accumulate selectivity *
                            * for current index (CurInd)       */
                for (CurIndCol = DOWN_TRN (CurInd);
                     CurIndCol; CurIndCol = RIGHT_TRN (CurIndCol))
                  {
                    ColNum = COL_NO (OBJ_DESC (CurIndCol));
                    if (col_stat[ColNum].Sel < 1.0)
                      {
                        sel *= col_stat[ColNum].Sel;
                        if (!(col_stat[ColNum].num_categ_1))
                          break;
                      }
                    else
                      break;
                  }
                
                ColNum = COL_NO (OBJ_DESC (DOWN_TRN (CurInd)));
                categ_1 = col_stat[ColNum].num_categ_1;
                categ_2 = col_stat[ColNum].num_categ_2;
                if ((best_ind_info.Sel > sel) ||
                    ( (best_ind_info.Sel == sel) &&
                      ( (best_ind_info.num_categ_1 < categ_1) ||
                        ((best_ind_info.num_categ_1 == categ_1) &&
                         (best_ind_info.num_categ_2 < categ_2)) ) ))
                  {
                    Ind = CurInd;
                    best_ind_info.Sel = sel;
                    best_ind_info.num_categ_1 = categ_1;
                    best_ind_info.num_categ_2 = categ_2;
                  }
              }
            /* Ind - pointer to found index descriptor */
            if (!Ind && COR_IND_SP (ScanNode))
              {
                Ind = COR_IND_SP (ScanNode);
                COR_IND_SP (ScanNode) = TNULL;
              }
            
            if (Ind)
              {
                if (!COR_TID (ScanNode))
                  COR_TID (ScanNode) = VMALLOC (1, UnId);
                V_PTR (COR_TID (ScanNode), UnId)->i = IND_INDID (Ind);
                IND_CLM_CNT (ScanNode) = ARITY_TRN (Ind);
                COR_IND_SP (ScanNode) = VMALLOC (ARITY_TRN (Ind), VADR);
                Ind_SP = V_PTR (COR_IND_SP (ScanNode), VADR);
                
                for (CurIndCol = DOWN_TRN (Ind), k = 0;
                     CurIndCol; CurIndCol = RIGHT_TRN (CurIndCol), k++)
                  {
                    ColNum = COL_NO (OBJ_DESC (CurIndCol));
                    Tab_SP = V_PTR (COR_TAB_SP (ScanNode), VADR);
                    if (Tab_SP[ColNum])
                      /* there are simple predicates for k-th column of index */
                      {
                        sp_clm_tab_num--;
                        Ind_SP[k] = Tab_SP[ColNum];
                        Tab_SP[ColNum] = VNULL;
                        if (!(col_stat[ColNum].num_categ_1))
                          /* for index's column there isn't SP 'EQU' */
                          break;
                      }
                    else
                      break;
                  }
              } /* if (Ind) */
		      
            if (!sp_clm_tab_num && COR_TAB_SP (ScanNode))
              /* all simple predicates was moved for index */
              {
                vmfree (COR_TAB_SP (ScanNode));
                COR_TAB_SP (ScanNode) = VNULL;
              }
          } /* if (tbl_ind[real_num]) :            *
             * there are indexes for current table */
      } /* for : tbl_num - tables handling finished */
  if (DisNum)
    if (!unused_prdc)	/* WHERE must be deleted */
      {
        free_tree (RIGHT_TRN (SelectNode));
        RIGHT_TRN (SelectNode) = TNULL;
      }
    else
      /* all not used disjuncts must be saved in WHERE */
      {
        for (fir_el = TNULL, prdc_num = 0; prdc_num < DisNum; prdc_num++)
          if (!SP_Arr[prdc_num].flag)
            /* this predicate was not used as simple one */
            if (fir_el)
              last_el = RIGHT_TRN (last_el) = SP_Arr[prdc_num].SP_Trees;
            else
              fir_el = last_el = SP_Arr[prdc_num].SP_Trees;
        
        assert (fir_el && last_el);
        RIGHT_TRN (last_el) = TNULL;
        
        if (unused_prdc > 1)
          {
            WhereNode = DOWN_TRN (WhereNode);
            TASSERT (CODE_TRN (WhereNode) == AND, WhereNode);
          }
        else
          if (CODE_TRN (WhereTree) == AND)
            free_node (WhereTree);
        
        DOWN_TRN (WhereNode) = fir_el;
      }
  
  if (col_stat)
    xfree (col_stat);
  if (SP_Arr)
    xfree (SP_Arr);
  if (Heap)
    xfree (Heap);
  
  xfree (fin_nums);
  xfree (BestTblOrder);
  xfree (CurTblOrder);
  xfree (tab_col_num);
  xfree (TblPtr);
  xfree (SP_Ind_Arr);
  xfree (NumRows);
  xfree (TblBits);
  xfree (TblAllBits);
  xfree (tbl_ind);
  xfree (NumRowScans);
  return BestCost;
}     /* opt_query */

						