![[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.