![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to strategy.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / ingres / source / ovqp|
Return to strategy.c CVS log | Up to [CSRG BSD Unix] / 43BSD / ingres / source / ovqp |
1.1 root 1: # include <ingres.h>
2: # include <aux.h>
3: # include <catalog.h>
4: # include <symbol.h>
5: # include <tree.h>
6: # include "../decomp/globs.h"
7: # include "strategy.h"
8: # include <btree.h>
9: # include <sccs.h>
10: # include <errors.h>
11:
12: SCCSID(@(#)strategy.c 8.4 2/8/85)
13:
14: /*
15: ** STRATEGY
16: **
17: ** Attempts to limit access scan to less than the entire De.ov_source
18: ** relation by finding a key which can be used for associative
19: ** access to the De.ov_source reln or an index thereon. The key is
20: ** constructed from domain-value specifications found in the
21: ** clauses of the qualification list using sub-routine findsimp
22: ** in findsimp.c and other subroutines in file key.c
23: */
24:
25: strategy()
26: {
27: register int i, j, allexact;
28: struct accessparam sourceparm, indexparm;
29: struct index itup, rtup;
30: struct key lowikey[MAXKEYS+1], highikey[MAXKEYS+1];
31: struct key lowbkey[MAXKEYS+1], highbkey[MAXKEYS+1];
32: register DESC *d;
33: DESC *openindex();
34: extern DESC Inddes;
35: char *tp;
36: long l_lid[MAXLID], h_lid[MAXLID];
37: int keytype;
38: long last_lid();
39: long page, l, t;
40: int lidsize;
41: struct locator tidloc;
42: extern int Btree_fd;
43:
44: # ifdef xOTR1
45: if (tTf(70, 0))
46: printf("STRATEGY\tSource=%.12s\tNewq = %d\n",
47: De.ov_source ? De.ov_source->reldum.relid : "(none)",
48: De.de_newq);
49: # endif
50:
51: while (De.de_newq) /* if De.de_newq=TRUE then compute a new strategy */
52: /* NOTE: This while loop is executed only once */
53: {
54: De.ov_scanr = De.ov_source;
55:
56: if (!De.ov_scanr)
57: return (1); /* return immediately if there is no source relation */
58:
59: De.ov_fmode = NOKEY; /* assume a find mode with no key */
60:
61: if (!De.ov_qlist)
62: break; /* if no qualification then you must scan entire rel */
63: /*
64: ** Here we check for the special condition
65: ** of a where clause consisting only of a tid.
66: */
67: if (tid_only_test())
68: return(1);
69:
70: /* copy structure of source relation into sourceparm */
71: paramd(De.ov_source, &sourceparm);
72:
73: /* if source is unkeyed and has no sec index then give up */
74: if (sourceparm.mode == NOKEY && De.ov_source->reldum.relindxd <= 0 && !De.ov_source->reldum.reldim)
75: break;
76:
77: /* find all simple clauses if any */
78: if (!findsimps())
79: break; /* break if there are no simple clauses */
80:
81: /* Four steps are now performed to try and find a key.
82: ** First if the relation is hashed then an exact key is search for
83: **
84: ** Second if there are secondary indexes, then a search is made
85: ** for an exact key. If that fails then a check is made for
86: ** a range key. The result of the rangekey check is saved.
87: **
88: ** A step to check for possible use of Btrees is made here,
89: ** although in actuality, an exact btreekey search is used
90: ** after an exact range key search but before a range key search.
91: ** A BTree range search is used only as a last alternative
92: ** to a no key search.
93: **
94: ** Third if the relation is an ISAM a check is made for
95: ** an exact key or a range key.
96: **
97: ** Fourth if there is a secondary index, then if step two
98: ** found a key, that key is used.
99: **
100: ** Lastly, give up and scan the entire relation
101: */
102:
103: /* step one. Try to find exact key on primary */
104: if (exactkey(&sourceparm, De.ov_lkey_struct))
105: {
106: De.ov_fmode = EXACTKEY;
107: break;
108: }
109:
110: /* step two. If there is an index, try to find an exactkey on one of them */
111: if (De.ov_source->reldum.relindxd > 0)
112: {
113:
114: opencatalog("indexes", OR_READ);
115: setkey(&Inddes, &itup, De.ov_source->reldum.relid, IRELIDP);
116: setkey(&Inddes, &itup, De.ov_source->reldum.relowner, IOWNERP);
117: if (i = find(&Inddes, EXACTKEY, &De.ov_lotid, &De.ov_hitid, (char *)&itup))
118: syserr("strategy:find indexes %d", i);
119:
120: while (!(i = get(&Inddes, &De.ov_lotid, &De.ov_hitid, (char *)&itup, NXTTUP)))
121: {
122: # ifdef xOTR1
123: if (tTf(70, 3))
124: printup(&Inddes, (char *)&itup);
125: # endif
126: if (!bequal(itup.irelidp, De.ov_source->reldum.relid, MAXNAME) ||
127: !bequal(itup.iownerp, De.ov_source->reldum.relowner, 2))
128: continue;
129: parami(&itup, &indexparm);
130: if (exactkey(&indexparm, De.ov_lkey_struct))
131: {
132: De.ov_fmode = EXACTKEY;
133: d = openindex(itup.irelidi);
134: /* temp check for 6.0 index */
135: if ((int) d->reldum.relindxd == -1)
136: ov_err(BADSECINDX);
137: De.ov_scanr = d;
138: break;
139: }
140: if (De.ov_fmode == LRANGEKEY)
141: continue; /* a range key on a s.i. has already been found */
142: if (allexact = rangekey(&indexparm, lowikey, highikey))
143: {
144: bmove((char *)&itup, (char *)&rtup, sizeof itup); /* save tuple */
145: De.ov_fmode = LRANGEKEY;
146: }
147: }
148: if (i < 0)
149: syserr("stragery:bad get from index-rel %d", i);
150: /* If an exactkey on a secondary index was found, look no more. */
151: if (De.ov_fmode == EXACTKEY)
152: break;
153: }
154:
155: /* attempt to use Btree in aiding search */
156: if (i = btreekey(lowbkey, highbkey))
157: {
158: if (i > 0)
159: De.ov_fmode = BTREEKEY;
160: else if (De.ov_fmode != LRANGEKEY)
161: /* use range key search over btree range search */
162: {
163: keytype = i;
164: De.ov_fmode = BTREERANGE;
165: }
166: }
167:
168: /* step three. Look for a range key on primary */
169: if (i = rangekey(&sourceparm, De.ov_lkey_struct, De.ov_hkey_struct))
170: {
171: if (i < 0)
172: De.ov_fmode = EXACTKEY;
173: else if (De.ov_fmode == BTREEKEY)
174: /* use exact btree search over range search */
175: {
176: bmove((char *) lowbkey, (char *) De.ov_lkey_struct, sizeof lowbkey);
177: bmove((char *) highbkey, (char *) De.ov_hkey_struct, sizeof highbkey);
178: }
179: else
180: De.ov_fmode = LRANGEKEY;
181: break;
182: }
183:
184: if (De.ov_fmode == BTREEKEY)
185: {
186: bmove((char *) lowbkey, (char *) De.ov_lkey_struct, sizeof lowbkey);
187: bmove((char *) highbkey, (char *) De.ov_hkey_struct, sizeof highbkey);
188: break;
189: }
190:
191: /* last step. If a secondary index range key was found, use it */
192: if (De.ov_fmode == LRANGEKEY)
193: {
194: if (allexact < 0)
195: De.ov_fmode = EXACTKEY;
196: d = openindex(rtup.irelidi);
197: /* temp check for 6.0 index */
198: if ((int) d->reldum.relindxd == -1)
199: ov_err(BADSECINDX);
200: De.ov_scanr = d;
201: bmove((char *)lowikey, (char *)De.ov_lkey_struct, sizeof lowikey);
202: bmove((char *)highikey, (char *)De.ov_hkey_struct, sizeof highikey);
203: break;
204: }
205:
206: /* nothing will work. give up! */
207: break;
208:
209: }
210:
211: /* check for De.de_newq = FALSE and no source relation */
212: if (!De.ov_scanr)
213: return (1);
214: /*
215: ** At this point the strategy is determined.
216: **
217: ** If De.ov_fmode is EXACTKEY then De.ov_lkey_struct contains
218: ** the pointers to the keys.
219: **
220: ** If De.ov_fmode is LRANGEKEY then De.ov_lkey_struct contains
221: ** the pointers to the low keys and De.ov_hkey_struct
222: ** contains pointers to the high keys.
223: **
224: ** If De.ov_fmode is BTREEKEY then De.ov_lkey_struct contains
225: ** pointers to the key lid.
226: **
227: ** If De.ov_fmode is BTREERANGE then lowbkey contains pointers
228: ** to the low key lid and highbkey contains pointers to the
229: ** high key lid.
230: **
231: ** If De.ov_fmode is NOKEY, then a full scan will be performed
232: */
233: # ifdef xOTR1
234: if (tTf(70, -1))
235: printf("De.ov_fmode= %d\n",De.ov_fmode);
236: # endif
237:
238: if (De.ov_fmode == BTREERANGE)
239: /* requires special type of search to limit tid scan */
240: {
241: for (i = 0; i < De.ov_scanr->reldum.reldim; ++i)
242: {
243: l_lid[i] = 0;
244: h_lid[i] = 0;
245: }
246: lidsize = LIDSIZE * De.ov_scanr->reldum.reldim;
247: /* get low lids */
248: if (keytype == -1 || keytype == -3)
249: {
250: tp = De.ov_keyl + De.ov_scanr->reldum.relwid - lidsize;
251: bmove(l_lid, tp, lidsize);
252: setallkey(lowbkey, De.ov_keyl);
253: bmove(tp, l_lid, lidsize);
254: }
255: /* get high lids */
256: if (keytype == -2 || keytype == -3)
257: {
258: tp = De.ov_keyh + De.ov_scanr->reldum.relwid - lidsize;
259: bmove(h_lid, tp, lidsize);
260: setallkey(highbkey, De.ov_keyh);
261: bmove(tp, h_lid, lidsize);
262: }
263: Btree_fd = De.ov_scanr->btree_fd;
264: /* scan through lids to fill in unprovided lids and to check
265: ** for lids that are too big
266: */
267: page = RT;
268: for (i = 0; i < De.ov_scanr->reldum.reldim; ++i)
269: {
270: if (l_lid[i] <= 0)
271: l_lid[i] = 1;
272: l = last_lid(page) - 1;
273: if (h_lid < 0)
274: return(0);
275: if (!h_lid[i] || h_lid[i] > l)
276: h_lid[i] = l;
277: if ((t = get_tid(page, h_lid[i], &tidloc)) < 0)
278: syserr("bad gettid in strategy, lid = %ld\n", h_lid[i]);
279: page = t;
280: }
281: /* check whether lo > hi */
282: for (i = 0; i < De.ov_scanr->reldum.reldim; ++i)
283: if (l_lid[i] < h_lid[i])
284: break;
285: else if (l_lid[i] > h_lid[i])
286: return(0);
287: # ifdef xOTR1
288: if (tTf(70,0))
289: for (i = 0 ; i < De.ov_scanr->reldum.reldim; ++i)
290: printf("hi = %ld, lo = %ld\n", h_lid[i], l_lid[i]);
291: # endif
292: /* find the smallest and largest possible tids of the lids
293: ** within the provided range */
294: btreerange(De.ov_scanr, l_lid, h_lid, &De.ov_lotid, &De.ov_hitid);
295: }
296: else
297: {
298: /* set up the key tuples */
299: if (De.ov_fmode != NOKEY)
300: {
301: if (setallkey(De.ov_lkey_struct, De.ov_keyl))
302: return (0); /* query false. There is a simple
303: ** clause which can never be satisfied.
304: ** These simple clauses can be choosey!
305: */
306: }
307:
308: if (i = find(De.ov_scanr, De.ov_fmode, &De.ov_lotid, &De.ov_hitid, De.ov_keyl))
309: syserr("strategy:find1 %.12s, %d", De.ov_scanr->reldum.relid, i);
310:
311: if (De.ov_fmode == LRANGEKEY)
312: {
313: setallkey(De.ov_hkey_struct, De.ov_keyh);
314: if (i = find(De.ov_scanr, HRANGEKEY, &De.ov_lotid, &De.ov_hitid, De.ov_keyh))
315: syserr("strategy:find2 %.12s, %d", De.ov_scanr->reldum.relid, i);
316: }
317: }
318:
319: # ifdef xOTR1
320: if (tTf(70, 1))
321: {
322: printf("Lo");
323: dumptid(&De.ov_lotid);
324: printf("Hi");
325: dumptid(&De.ov_hitid);
326: }
327: # endif
328:
329: return (1);
330: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.