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

##### Functions

    costfunc          X
    selectv           X

       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

costfunc defined in line 154; used 3 times

- in line 90, 113, 124

selectv defined in line 84; used 2 times

- in /usr/ingres/source/decomp/decomp.c line 173, 274

Last modified: 1995-04-14 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1110 |