1: # include "../ingres.h" 2: # include "../tree.h" 3: # include "../symbol.h" 4: # include "decomp.h" 5: 6: struct agglist 7: { 8: struct querytree **father; /* addr of pointer to you */ 9: struct querytree *agpoint; /* pointer to aghead */ 10: struct querytree *agfather; /* is your father an aggregate? */ 11: int agvarno; /* var # assigned to aggr fnct */ 12: }; 13: 14: struct hitlist 15: { 16: struct querytree **trepr; /* position in tree to be changed */ 17: int byno; /* by-list position */ 18: }; 19: 20: struct agglist *Aggnext; 21: 22: aggregate(root) 23: struct querytree *root; 24: 25: /* 26: ** AGGREGATE - replace aggregates with their values 27: ** 28: ** Aggregate attempts to optimize aggregate processing 29: ** wherever possible. It replaces aggregates with their 30: ** values, and links aggregate functions which have 31: ** identical by-lists together. 32: ** 33: ** Note that for the sake of this code, A "prime" 34: ** aggregate is one in which duplicates are removed. 35: ** These are COUNTU, SUMU, and AVGU. 36: ** 37: ** Aggregate first forms a list of all aggregates in 38: ** the order they should be processed. 39: ** 40: ** For each aggregate, it looks at all other aggregates 41: ** to see if there are two simple aggregates 42: ** or if there is another aggregate funtion with the 43: ** same by-list. 44: ** 45: ** An attempt is made to run 46: ** as many aggregates as possible at once. This can be 47: ** done only if two or more aggregates have the same 48: ** qualifications and in the case of aggregate functions, 49: ** they must have identical by-lists. 50: ** Even then, certain combinations 51: ** of aggregates cannot occure together. The list is 52: ** itemized later in the code. 53: ** 54: ** Aggregate calls BYEVAL or AGEVAL to actually process 55: ** aggregate functions or aggregates respectively. 56: ** 57: */ 58: 59: { 60: struct agglist alist[MAXAGG + 1]; 61: struct querytree *rlist[MAXAGG + 1]; 62: struct agglist *al, *al1; 63: register struct querytree *agg, *aop1, *r; 64: struct querytree *aop, *agg1; 65: int i, simple_agg, varmap; 66: int attcnt, anyagg, attoff, twidth; 67: struct querytree *makavar(), *agspace(); 68: 69: al = alist; 70: Aggnext = al; 71: 72: findagg(&root, root); /* generate list of all aggregates */ 73: Aggnext->agpoint = 0; /* mark end of the list */ 74: anyagg = 0; 75: 76: varmap = ((struct qt_root *)root)->lvarm | ((struct qt_root *)root)->rvarm; 77: 78: /* process each aggregate */ 79: for (;agg = al->agpoint; al++) 80: { 81: 82: /* is this still an aggregate? */ 83: if (agg->sym.type != AGHEAD) 84: continue; 85: mapvar(agg, 0); /* map the aggregate tree */ 86: anyagg++; 87: 88: Sourcevar = bitpos(((struct qt_root *)agg)->lvarm | ((struct qt_root *)agg)->rvarm); 89: # ifdef xDTR1 90: if (tTf(6, 4)) 91: printf("Sourcevar=%d,rel=%s\n", Sourcevar, rangename(Sourcevar)); 92: # endif 93: 94: simple_agg = (agg->left->sym.type == AOP); /* TRUE if no bylist */ 95: aop = agg->left; /* assume it was TRUE */ 96: # ifdef xDTR1 97: if (tTf(6, 0)) 98: printf("%s\n", simple_agg ? "agg" : "agg-func"); 99: # endif 100: if (simple_agg) 101: { 102: /* simple aggregate */ 103: rlist[0] = agspace(aop); 104: twidth = ((struct qt_var *)aop)->frml & I1MASK; /* init width to the width of the aggregate */ 105: } 106: else 107: { 108: attoff = ((struct qt_res *)agg->left->left)->resno + 2; 109: aop = aop->right; /* find the AOP node */ 110: /* assign new source variable for aggregate */ 111: al->agvarno = getrange(&varmap); 112: /* compute width of bylist + count field */ 113: twidth = findwid(agg->left) + 4; 114: 115: /* make sure the aggregate does not exceed max dimensions */ 116: if (chkwidth(aop, &twidth, attoff)) 117: derror(AGFTOBIG); 118: } 119: attcnt = 1; /* one aggregate so far */ 120: 121: /* look for another identical aggregate */ 122: for (al1 = al + 1; agg1 = al1->agpoint; al1++) 123: { 124: 125: /* if agg is nested inside agg1 then ignore it */ 126: if (al->agfather == agg1 || agg1->sym.type != AGHEAD) 127: continue; 128: 129: /* split aggs and agg-func apart */ 130: /* check for identical aggregate */ 131: if (simple_agg) 132: { 133: aop1 = agg1->left; /* find AOP node */ 134: 135: if (aop1->sym.type != AOP) 136: continue; /* not a simple agg */ 137: 138: /* make sure they can be run together */ 139: if (checkagg(agg, aop, agg1, aop1) == 0) 140: continue; 141: 142: if ((i = sameagg(agg, aop1, attcnt)) >= 0) 143: { 144: /* found identical aggregate to rlist[i] */ 145: r = rlist[i]; 146: } 147: else 148: { 149: /* put this agg in with the others */ 150: 151: /* first make sure it won't exceed tuple length */ 152: if (chkwidth(aop1, &twidth, 0)) 153: continue; /* can't be included */ 154: r = rlist[attcnt++] = agspace(aop1); 155: 156: /* connect into tree */ 157: aop1->left = agg->left; 158: agg->left = aop1; 159: } 160: } 161: else 162: { 163: /* aggregate function */ 164: if (!sameafcn(agg->left->left, agg1->left->left)) 165: continue; 166: 167: aop1 = agg1->left->right; /* find AOP */ 168: 169: 170: if (checkagg(agg, aop, agg1, aop1) == 0) 171: { 172: /* same by-lists but they can't be run together */ 173: continue; 174: } 175: 176: if ((i = sameagg(agg, aop1, attcnt)) < 0) 177: { 178: /* make sure there is room */ 179: if (chkwidth(aop1, &twidth, attcnt + attoff)) 180: continue; 181: 182: /* add aggregate into tree */ 183: i = attcnt++; 184: 185: aop1->left = agg->left->right; 186: agg->left->right = aop1; 187: } 188: 189: r = makavar(aop1, al->agvarno, i + attoff); 190: } 191: /* replace aggregate in original tree with its value */ 192: *(al1->father) = r; 193: 194: /* remove aggregate from local list */ 195: agg1->sym.type = -1; 196: # ifdef xDTR1 197: if (tTf(6, 3)) 198: printf("including aghead %l\n", agg1); 199: # endif 200: } 201: 202: /* process aggregate */ 203: if (simple_agg) 204: { 205: rlist[attcnt] = 0; 206: ageval(agg, rlist); /* pass tree and result list */ 207: r = rlist[0]; 208: } 209: else 210: { 211: opt_bylist(&alist, agg); 212: byeval(al->agfather, agg, al->agvarno); 213: r = makavar(aop, al->agvarno, attoff); 214: } 215: /* 216: ** Link result into tree. al->father hold the address 217: ** &(tree->left) or &(tree->right). 218: */ 219: *(al->father) = r; 220: # ifdef xDTR1 221: if (tTf(6, 4)) 222: printree(*(al->father), "aggregate value"); 223: # endif 224: } 225: if (anyagg) 226: { 227: opt_bylist(&alist, root); 228: mapvar(root, 0); /* remap main tree */ 229: } 230: } 231: 232: findagg(nodep, agf) 233: struct querytree **nodep; 234: struct querytree *agf; 235: 236: /* 237: ** findagg builds a list of all aggregates 238: ** in the tree. It finds them by leftmost 239: ** innermost first. 240: ** 241: ** The parameters represent: 242: ** nodep: the address of the node pointing to you 243: ** eg. &(tree->left) or &(tree->right) 244: ** agf: the root node. or if we are inside 245: ** a nested aggregate, the AGHEAD node 246: */ 247: 248: { 249: register struct querytree *q, *f; 250: register struct agglist *list; 251: int agg; 252: 253: if ((q = *nodep) == NULL) 254: return; 255: 256: f = agf; 257: if (agg = (q->sym.type == AGHEAD)) 258: f = q; /* this aggregate is now the father root */ 259: 260: /* find all aggregates below */ 261: findagg(&(q->left), f); 262: findagg(&(q->right), f); 263: 264: /* if this is an aggregate, put it on the list */ 265: if (agg) 266: { 267: list = Aggnext; 268: list->father = nodep; 269: list->agpoint = q; 270: list->agfather = agf; 271: Aggnext++; 272: } 273: } 274: 275: 276: 277: struct querytree *agspace(aop) 278: struct querytree *aop; 279: 280: /* 281: ** Agspace allocates space for the result of 282: ** a simple aggregate. 283: */ 284: 285: { 286: register struct querytree *a, *r; 287: register int length; 288: struct querytree *need(); 289: 290: a = aop; 291: length = ((struct qt_var *)a)->frml & I1MASK; 292: 293: r = need(Qbuf, length + 6); 294: r->left = r->right = 0; 295: r->sym.type = ((struct qt_var *)a)->frmt; 296: r->sym.len = length; 297: 298: return (r); 299: } 300: 301: 302: 303: chkwidth(aop, widthp, domno) 304: struct querytree *aop; 305: int *widthp; 306: int domno; 307: 308: /* 309: ** Chkwidth -- make sure that the inclusion of another aggregate will 310: ** not exceed the system limit. This means that the total width 311: ** cannot exceed MAXTUP and the number of domains cannot exceed MAXDOM-1 312: */ 313: 314: { 315: register int width; 316: 317: width = *widthp; 318: 319: # ifdef xDTR1 320: if (tTf(6, 10)) 321: printf("agg width %d,dom %d\n", width, domno); 322: # endif 323: 324: width += (((struct qt_var *)aop)->frml & I1MASK); 325: 326: if (width > MAXTUP || domno > MAXDOM - 1) 327: return (1); 328: 329: *widthp = width; 330: return (0); 331: } 332: 333: 334: cprime(aop) 335: struct querytree *aop; 336: 337: /* 338: ** Determine whether an aggregate is prime 339: ** or a don't care aggregate. Returns TRUE 340: ** if COUNTU,SUMU,AVGU,MIN,MAX,ANY. 341: ** Returns false if COUNT,SUM,AVG. 342: */ 343: { 344: register int i; 345: 346: i = TRUE; 347: switch (aop->sym.value[0]) 348: { 349: case opCOUNT: 350: case opSUM: 351: case opAVG: 352: i = FALSE; 353: } 354: return (i); 355: } 356: 357: 358: getrange(varmap) 359: int *varmap; 360: 361: /* 362: ** Getrange find a free slot in the range table 363: ** for an aggregate function. 364: ** 365: ** If there are no free slots,derror is called 366: */ 367: 368: { 369: register int i, map, bit; 370: 371: map = *varmap; 372: 373: for (i = 0; i < MAXRANGE; i++) 374: { 375: /* if slot is used, continue */ 376: if ((bit = 1 << i) & map) 377: continue; 378: 379: map |= bit; /* "or" bit into the map */ 380: *varmap = map; 381: 382: # ifdef xDTR1 383: if (tTf(6, 10)) 384: printf("Assn var %d, map %o\n", i, map); 385: # endif 386: 387: return (i); 388: } 389: derror(NODESCAG); 390: } 391: 392: 393: checkagg(aghead1, aop1, aghead2, aop2) 394: struct querytree *aghead1; 395: struct querytree *aop1; 396: struct querytree *aghead2; 397: struct querytree *aop2; 398: { 399: register struct querytree *aop_1, *aop_2, *agg1; 400: int ok; 401: 402: /* two aggregate functions can be run together 403: ** according to the following table: 404: ** 405: ** prime !prime don't care 406: ** 407: ** prime afcn? never afcn? 408: ** !prime never always always 409: ** don't care afcn? always always 410: ** 411: ** don't care includes: ANY, MIN, MAX 412: ** afcn? means only if a-fcn's are identical 413: */ 414: 415: aop_1 = aop1; 416: aop_2 = aop2; 417: agg1 = aghead1; 418: 419: if (!prime(aop_1) && !prime(aop_2)) 420: ok = TRUE; 421: else 422: if (sameafcn(aop_1->right, aop_2->right)) 423: ok = cprime(aop_1) && cprime(aop_2); 424: else 425: ok = FALSE; 426: /* The two aggregates must range over the same variables */ 427: if ((((struct qt_root *)agg1)->lvarm | ((struct qt_root *)agg1)->rvarm) 428: != (((struct qt_root *)aghead2)->lvarm | ((struct qt_root *)aghead2)->rvarm)) 429: ok = FALSE; 430: 431: /* check the qualifications */ 432: if (ok) 433: ok = sameafcn(agg1->right, aghead2->right); 434: return (ok); 435: } 436: 437: 438: sameagg(aghead, newaop, agg_depth) 439: struct querytree *aghead; 440: struct querytree *newaop; 441: int agg_depth; 442: { 443: register struct querytree *agg, *newa; 444: register int i; 445: 446: agg = aghead; 447: newa = newaop; 448: agg = agg->left; 449: if (agg->sym.type == BYHEAD) 450: agg = agg->right; 451: 452: /* agg now points to first aggregate */ 453: for (i = 1; agg; agg = agg->left, i++) 454: if (sameafcn(agg->right, newa->right) && agg->sym.value[0] == newa->sym.value[0]) 455: { 456: # ifdef xDTR1 457: if (tTf(6, 6)) 458: printf("found identical aop %l\n", newa); 459: # endif 460: return (agg_depth - i); 461: } 462: 463: /* no match */ 464: return (-1); 465: } 466: 467: 468: struct hitlist *Hnext, *Hlimit; 469: 470: 471: opt_bylist(alist, root) 472: struct agglist *alist; 473: struct querytree *root; 474: { 475: register struct agglist *al; 476: register struct querytree *agg; 477: register struct hitlist *hl; 478: struct querytree **tpr, *tree, *lnodv[MAXDOM+2]; 479: struct hitlist hlist[30]; 480: int anyop, i, usedmap, vars, treemap; 481: extern struct querytree *makavar(); 482: 483: /* compute bitmap of all possible vars in tree (can include xtra vars) */ 484: treemap = ((struct qt_root *)root)->lvarm | ((struct qt_root *)root)->rvarm; 485: anyop = FALSE; 486: 487: /* scan the list of aggregates looking for one nested in root */ 488: for (al = alist; (agg = al->agpoint) && agg != root; al++) 489: { 490: if (agg->sym.type == AGHEAD && agg->left->sym.type == BYHEAD && 491: al->agfather == root) 492: { 493: 494: /* this aggregate function is nested in root */ 495: 496: /* make sure it has some vars of interest */ 497: if ((treemap & varfind(agg->left->left, NULL)) == 0) 498: continue; 499: 500: # ifdef xDTR1 501: if (tTf(6, 11)) 502: printree(agg, "nested agg"); 503: # endif 504: 505: /* form list of bydomains */ 506: lnodv[lnode(agg->left->left, lnodv, 0)] = 0; 507: usedmap = 0; 508: 509: Hnext = &hlist[0]; 510: Hlimit = &hlist[30]; 511: 512: /* find all possible replacements */ 513: vars = modtree(&root, lnodv, &usedmap); 514: 515: /* 516: ** All references to a variable must be replaced 517: ** in order to use this aggregates by-domains. 518: */ 519: if (usedmap && ((vars & usedmap) == 0)) 520: { 521: # ifdef xDTR1 522: if (tTf(6, 7)) 523: printf("Committed\n"); 524: # endif 525: /* success. Committ the tree changes */ 526: Hnext->trepr = NULL; 527: 528: for (hl = &hlist[0]; tpr = hl->trepr; hl++) 529: { 530: /* get bydomain number */ 531: i = hl->byno; 532: 533: /* get node being replaced */ 534: tree = *tpr; 535: 536: /* if it is already a var, just change it */ 537: if (tree->sym.type == VAR) 538: { 539: ((struct qt_var *)tree)->varno = al->agvarno; 540: ((struct qt_var *)tree)->attno = i + 2; 541: } 542: else 543: *tpr = makavar(lnodv[i], al->agvarno, i + 2); 544: 545: anyop = TRUE; 546: # ifdef xDTR1 547: if (tTf(6, 7)) 548: printree(*tpr, "modified tree"); 549: # endif 550: } 551: } 552: /* vars is now a map of the variables in the root */ 553: treemap = vars; 554: } 555: } 556: 557: /* if any changes were made, get rid of the unnecessary links */ 558: if (anyop) 559: chklink(root); 560: } 561: 562: 563: 564: 565: modtree(pnode, lnodv, replmap) 566: struct querytree **pnode; 567: struct querytree *lnodv[]; 568: int *replmap; 569: { 570: register struct querytree *tree; 571: register int vars, i; 572: struct querytree *afcn; 573: 574: /* point up current node */ 575: if ((tree = *pnode) == NULL) 576: return (0); 577: 578: /* examine each by-list for match on this subtree */ 579: for (i = 0; afcn = lnodv[i]; i++) 580: { 581: if (sameafcn(tree, afcn->right)) 582: { 583: # ifdef xDTR1 584: if (tTf(6, 9)) 585: printree(tree, "potential Jackpot"); 586: # endif 587: vars = varfind(tree, NULL); 588: if (Hnext == Hlimit) 589: return (vars); /* no more room */ 590: 591: /* record what needs to be done */ 592: Hnext->trepr = pnode; 593: Hnext->byno = i; 594: Hnext++; 595: *replmap |= vars; 596: return (0); 597: } 598: } 599: if (tree->sym.type == VAR) 600: return (01 << ((struct qt_var *)tree)->varno); 601: 602: /* try the subtrees */ 603: vars = modtree(&(tree->left), lnodv, replmap); 604: if ((vars & *replmap) == 0) 605: vars |= modtree(&(tree->right), lnodv, replmap); 606: 607: return (vars); 608: } 609: 610: 611: chklink(root) 612: struct querytree *root; 613: { 614: register struct querytree *r, *b, *last; 615: 616: last = root; 617: 618: for (r = last->right; r->sym.type != QLEND; r = r->right) 619: { 620: /* if this is an EQ node then check for an unnecessary compare */ 621: if ((b = r->left)->sym.type == BOP && ((struct qt_op *)b)->opno == opEQ) 622: { 623: if (sameafcn(b->left, b->right)) 624: { 625: # ifdef xDTR1 626: if (tTf(6, 5)) 627: printree(b, "unnec clause"); 628: # endif 629: last->right = r->right; 630: continue; 631: } 632: } 633: last = r; 634: } 635: } 636: 637: 638: 639: sameafcn(q1, q2) 640: struct querytree *q1, *q2; 641: { 642: 643: register struct querytree *t1, *t2; 644: register int len; 645: int type; 646: 647: t1 = q1; 648: t2 = q2; 649: 650: if (!(t1 && t2)) 651: return(!(t1 || t2)); 652: len = (t1->sym.len & 0377) + 2; 653: type = t1->sym.type; 654: if (type == VAR) 655: len = 6; 656: if (type == AND) 657: len = 2; 658: if (!bequal(&t1->sym, &t2->sym, len)) 659: return(0); 660: return(sameafcn(t1->left,t2->left) && sameafcn(t1->right,t2->right)); 661: } 662: 663: varfind(root, aghead) 664: struct querytree *root; 665: struct querytree *aghead; 666: 667: /* 668: ** varfind -- find all variables in the tree pointed to by "root". 669: ** Examine all parts of the tree except aggregates. For 670: ** aggregates, ignore simple aggregate and look only 671: ** at the by-lists of aggregate functions. If the aggregate 672: ** is "aghead" then ignore it. There is no reason to look 673: ** at yourself!!!! 674: ** This routine is called by byeval() to determine 675: ** whether to link the aggregate to the root tree. 676: ** 677: ** Curiosity note: since the tree being examined has not been 678: ** processed by decomp yet, ckvar does not need to be called 679: ** since the var could not have been altered. 680: */ 681: 682: { 683: register struct querytree *tree; 684: register int type; 685: 686: 687: if ((tree = root) == NULL) 688: return (0); 689: 690: if ((type = tree->sym.type) == AGHEAD) 691: { 692: /* ignore if it matches aghead */ 693: if (tree == aghead) 694: return (0); 695: /* if this is an aggregate function, look at bylist */ 696: tree = tree->left; 697: if ((type = tree->sym.type) != BYHEAD) 698: return (0); 699: } 700: 701: if (type == VAR) 702: return (1 << ((struct qt_var *)tree)->varno); 703: 704: return (varfind(tree->left, aghead) | varfind(tree->right, aghead)); 705: }
|
Last modified: 1995-04-14
Generated: 2016-12-26 |
Generated by src2html V0.67
page hit count: 4411 |
|