4.3BSD - /usr/ingres/source/decomp/selectv.c

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

Defined functions