```   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
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:
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;
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: 	*/
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
selectv defined in line 84; used 2 times
 Last modified: 1995-04-14 Generated: 2016-12-26 Generated by src2html V0.67 page hit count: 2800