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: }

Defined functions

aggregate defined in line 22; used 1 times
agspace defined in line 277; used 3 times
checkagg defined in line 393; used 2 times
chklink defined in line 611; used 1 times
chkwidth defined in line 303; used 3 times
cprime defined in line 334; used 2 times
  • in line 423(2)
findagg defined in line 232; used 3 times
getrange defined in line 358; used 1 times
modtree defined in line 565; used 3 times
opt_bylist defined in line 471; used 2 times
sameafcn defined in line 639; used 8 times
sameagg defined in line 438; used 2 times
varfind defined in line 663; used 7 times

Defined variables

Aggnext defined in line 20; used 4 times
Hlimit defined in line 468; used 2 times
Hnext defined in line 468; used 6 times

Defined struct's

agglist defined in line 6; used 12 times
hitlist defined in line 14; used 6 times
Last modified: 1995-04-14
Generated: 2016-12-26
Generated by src2html V0.67
page hit count: 4419
Valid CSS Valid XHTML 1.0 Strict