2.11BSD#431 - /usr/ingres/source/decomp/selectv.c

   1: # include   "../ingres.h"
   2: # include   "../symbol.h"
   3: # include   "../tree.h"
   4: # include   "decomp.h"
   5: 
   6: /*
   7: **  SELECTV -- Select a variable for substitution
   8: **
   9: **	Selectv is called to determine the "best" variable
  10: **	to substitute for. The algorithm used is based on
  11: **	the Wong/Youseffi paper ERL M78/17. Selectv returns
  12: **	the variable to be substituted or it returns -1 which
  13: **	indicates that there is a relation with no tuples.
  14: **	If there is only one variable left, it is of course
  15: **	the one choosen.
  16: **
  17: **	For cases of more than one variable, a variable with
  18: **	0 or 1 tuples will always be choosen. Otherwise the
  19: **	variable with the smallest "costfunction" will be selected.
  20: **	In case of a tie, the variable with the smallest tuple count
  21: **	is selected.
  22: **
  23: **	The costfunction is:
  24: **		|Ri|
  25: **	       ______
  26: **		Peffective i
  27: **
  28: **	where |Ri| = cardinality of variable i.
  29: **	and   Peff = The number of pages needed to be accessed to
  30: **			safisfy a query on Ri assuming all other
  31: **			variables have been substituted for.
  32: **
  33: **
  34: **	Peff is only an estimate. The estimate is based on the
  35: **	storage structure of Ri and on whether Ri is used in
  36: **	the target list. Considering only equality clauses,
  37: **	the relation's structure is examined to see if any
  38: **	can be used effectively. The following assumptions are
  39: **	made:
  40: **		useful hash: Peff = 1
  41: **		useful isam: Peff = 2
  42: **		useful hash sec index: Peff = 2
  43: **		useful isam sec index: Peff = 3
  44: **
  45: **	If there is no useful structure or if the relation is
  46: **	a heap then:
  47: **		Peff = number of pages Ri occupies
  48: **	If the relation is not in the target list then its
  49: **	function is only an existence test. Scanning can and
  50: **	is stopped the first time a tuple is found which satisfies.
  51: **	We assume that on the average only 1/4 of the pages
  52: **	will have to be examined.
  53: **
  54: **	Parameters:
  55: **		root1 - root of the query
  56: **
  57: **	Returns:
  58: **		The variable to substitute for
  59: **			or
  60: **		-1 if the query is false
  61: **
  62: **	Side Effects:
  63: **		can cause a relation to be opened since
  64: **		ckpkey needs to know the key structure.
  65: **
  66: **	Requires:
  67: **		findlinks
  68: **		ckpkey
  69: **		rel_pages
  70: **
  71: **	Called By:
  72: **		decompy, decompz
  73: **
  74: **	Trace Flags:
  75: **		4
  76: **
  77: **	Syserrs:
  78: **		If selectv is called with a constant query
  79: **
  80: **	History:
  81: **		1/31/79 (rse) -- written
  82: */
  83: 
  84: selectv(root1)
  85: struct querytree    *root1;
  86: {
  87:     register struct querytree   *root;
  88:     int             min, var, map, i;
  89:     register struct rang_tab    *rt, *rx;
  90:     long                costfunc(), lx, lt;
  91: 
  92:     root = root1;
  93: 
  94:     map = ((struct qt_root *)root)->lvarm | ((struct qt_root *)root)->rvarm;
  95: 
  96:     min = -1;
  97:     lx = 0;
  98:     rx = NULL;
  99: 
 100:     for (i = 1, var = 0; map; i <<= 1, var++)
 101:     {
 102:         if ((map & i) == 0)
 103:             continue;
 104: 
 105:         map &= ~i;
 106:         rt = &Rangev[var];
 107:         if (rx == NULL)
 108:         {
 109:             rx = rt;
 110:             min = var;
 111:             if (map == 0 || rt->rtcnt < 2)
 112:                 break;
 113:             lx = costfunc(root, var, rt);
 114:         }
 115:         else
 116:         {
 117:             if (rt->rtcnt < 2)
 118:             {
 119:                 rx = rt;
 120:                 min = var;
 121:                 break;
 122:             }
 123: 
 124:             lt = costfunc(root, var, rt);
 125:             if (lt < lx)
 126:             {
 127:                 rx = rt;
 128:                 min = var;
 129:                 lx = lt;
 130:             }
 131:         }
 132:     }
 133: 
 134:     if (min == -1)
 135:         syserr("selectv:no source var");
 136: 
 137: #	ifdef xDTR1
 138:     if (tTf(4, 1))
 139:     {
 140:         printf("selectv:%d,tups=%s,", min, locv(rx->rtcnt));
 141:         printf("cf=%s,", locv(lx));
 142:         writenod(root);
 143:     }
 144: #	endif
 145: 
 146:     if (rx->rtcnt == 0)
 147:         min = -1;
 148: 
 149:     return (min);
 150: }
 151: 
 152: 
 153: 
 154: long costfunc(root, var, rx)
 155: struct querytree    *root;
 156: int         var;
 157: struct rang_tab     *rx;
 158: {
 159:     register struct rang_tab    *r;
 160:     register int            i;
 161:     register char           *lp;
 162:     char                linkmap[MAXDOM];
 163:     long                rel_page(), l;
 164:     int             c_bug;
 165: 
 166:     r = rx;
 167: 
 168:     for (lp = linkmap, i = MAXDOM; i--; )
 169:         *lp++ = 0;
 170:     i = var;
 171: 
 172:     /*
 173: 	** The c-compiler does not know how to generate code
 174: 	** for the assignment of an int to a long inside
 175: 	** an "if" expression. Therefore the variable "c_bug"
 176: 	** is assigned the value of ckpkey inside the "if".
 177: 	** The value is assigned to "l" in the "else".
 178: 	*/
 179:     if (!findlinks(root, -1, i, linkmap) || (c_bug = ckpkey(linkmap, i)) == 0)
 180:     {
 181:         l = rel_pages(r->rtcnt, r->rtwid);
 182: 
 183:         /* if not in target list, assume 1/4 */
 184:         if ((((struct qt_root *)root)->lvarm & (01 << i)) == 0)
 185:         {
 186:             l >>= 2;
 187:             if (l == 0)
 188:                 l = 1;
 189:         }
 190:     }
 191:     else
 192:         l = c_bug;  /* l could not be assigned directly above */
 193: 
 194:     l = r->rtcnt / l;
 195: 
 196: #	ifdef xDTR1
 197:     if (tTf(4, 3))
 198:         printf("costfunc %d is %s\n", i, locv(l));
 199: #	endif
 200:     return (l);
 201: }

Defined functions