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: }
|
Last modified: 1986-04-17
Generated: 2016-12-26 |
Generated by src2html V0.67
page hit count: 1101 |
|