2.11BSD#431 - /usr/ingres/source/decomp/decision.c

   1: # include   "../ingres.h"
   2: # include   "../symbol.h"
   3: # include   "../tree.h"
   4: # include   "decomp.h"
   5: 
   6: /*
   7: ** DECISION -- This file contains code related to deciding how to
   8: **	process the remaining query. The main routine is decision()
   9: **	and the other routines are called only by decision. The routine
  10: **	in this file include:
  11: **
  12: **	Decision -- Decides how to process a query.
  13: **
  14: **	Fixtl     -- Determines the target list for each component.
  15: **
  16: **	Fixresult -- Determines the result relation for the next query
  17: **
  18: **	Fixrange  -- Adjust the range table after a query
  19: **
  20: **	Fixovlap  -- Fixes trees in cases where reduction is used
  21: **
  22: **	Rmovlap   -- Restores trees in cases where reduction was used.
  23: **
  24: **	Listcomp  -- Debugging routine.
  25: */
  26: 
  27: 
  28: 
  29: 
  30: decision(root, qmode, result_num, buf)
  31: struct querytree    *root;
  32: int         qmode;
  33: int         result_num;
  34: char            *buf;
  35: 
  36: /*
  37: **	Decision is given a subquery and decides how to process it.
  38: **	The choices are:
  39: **		Disjoint pieces -- The original query had disjoint components.
  40: **					Do each component separately.
  41: **		Reduction       -- The query is joined by a single variable.
  42: **					Reduce the query on that joining variable
  43: **					and do each component separately.
  44: **		Substitution    -- The query is neither disjoint nor reducible.
  45: **					Process by tuple substitution.
  46: **
  47: **	Notice that decision() is recursive and will call itself on each
  48: **	subcomponent it decides to do. Decision calls various support
  49: **	routines in the file "reduction.c".
  50: */
  51: 
  52: {
  53:     register struct querytree   **qp;
  54:     register struct complist    *clist;
  55:     register int            ovlapvar;
  56:     struct complist         *cp, *buildlist(), *order();
  57:     int             i, onepiece, qtrue, map;
  58:     int             mark, mark1, cand_map;
  59:     struct querytree        *tree, *newtree, *construct();
  60:     struct querytree        *qlist[MAXRANGE], *copy_ands();
  61:     int             newqmode;
  62:     int             ovlaprelnum, newr;
  63:     int             locrange[MAXRANGE];
  64: 
  65: #	ifdef xDTR1
  66:     if (tTf(15, -1))
  67:     {
  68:         printf("DECISION root=%l,vc=%d,res=%d\n", root, ((struct qt_root *)root)->tvarc, result_num);
  69:     }
  70: #	endif
  71:     mark = markbuf(buf);
  72:     if (((struct qt_root *)root)->tvarc < 3)
  73:     {
  74:         /* setup to do as one single piece */
  75:         onepiece = TRUE;
  76:     }
  77:     else
  78:     {
  79:         /* break the query apart if possible */
  80: 
  81:         /* build component list */
  82:         clist = buildlist(root, buf);
  83: #		ifdef xDTR1
  84:         if (tTf(15, 2))
  85:             listcomp(clist, "Original Comp");
  86: #		endif
  87: 
  88:         /* is query completely connected or disjoint */
  89:         map = ((struct qt_root *)root)->lvarm | ((struct qt_root *)root)->rvarm;
  90:         onepiece = algorithm(clist, map);
  91: #		ifdef xDTR1
  92:         if (tTf(15, 1))
  93:             printf("Orig query %s\n", onepiece ? "connected" : "disjoint");
  94: #		endif
  95:         /* assume there is no joining variable */
  96:         ovlapvar = -1;
  97: 
  98:         if (onepiece)
  99:         {
 100:             /*
 101: 			** Try to reduce a single connected piece.
 102: 			** In turn each variable will be logically
 103: 			** removed from the query and a test will
 104: 			** be made to see if the query is still
 105: 			** connected.
 106: 			*/
 107: 
 108:             cand_map = map;
 109:             for (i = 1; cand_map; i <<= 1)
 110:             {
 111:                 if ((cand_map & i) == 0)
 112:                     continue;
 113:                 cand_map &= ~i;
 114:                 freebuf(buf, mark);
 115:                 clist = buildlist(root, buf);
 116:                 if (algorithm(clist, map & ~i) == 0)
 117:                 {
 118:                     ovlapvar = bitpos(i);
 119:                     ovlaprelnum = Rangev[ovlapvar].relnum;
 120:                     onepiece = FALSE;
 121:                     break;
 122:                 }
 123:             }
 124: #			ifdef xDTR1
 125:             if (tTf(15, 1))
 126:             {
 127:                 if (ovlapvar < 0)
 128:                     printf("Query not reducible\n");
 129:                 else
 130:                 {
 131:                     printf("Query Reducible on %d\n", ovlapvar);
 132:                     if (tTf(15, 3))
 133:                         listcomp(clist, "After reduct");
 134:                 }
 135:             }
 136: #			endif
 137:         }
 138: 
 139:         /*
 140: 		** If query is more than one piece, build trees
 141: 		** for each piece.
 142: 		*/
 143: 
 144:         if (!onepiece)
 145:         {
 146:             /* order pieces */
 147:             clist = order(clist, ovlapvar);
 148: #			ifdef xDTR1
 149:             if (tTf(15, 4))
 150:                 listcomp(clist, "After ordering");
 151: #			endif
 152:             cp = clist;
 153:             qp = qlist;
 154:             do
 155:             {
 156:                 *qp++ = construct(root, cp, buf);
 157:             } while (cp = cp->nextcomp);
 158:             *qp++ = 0;
 159:         }
 160:     }
 161: 
 162:     /*
 163: 	** The query is now either the one original piece or
 164: 	** is in multiple pieces. The information in clist
 165: 	** is no longer needed and now the ordered pieces
 166: 	** will be processed.
 167: 	*/
 168: 
 169:     if (onepiece)
 170:     {
 171:         freebuf(buf, mark);
 172:         qtrue = decompy(root, qmode, result_num, buf);
 173:     }
 174:     else
 175:     {
 176:         /* the query is in pieces. prepare to process */
 177: 
 178:         newquery(locrange); /* save state of range table */
 179: 
 180:         /* determine the target list for each piece of the query */
 181:         for (qp = qlist; tree = *qp++; )
 182:             fixtl(tree, qp, ovlapvar, buf);
 183: 
 184:         /* adjust refs to ovlapvar since domain #'s could have changed */
 185:         fixovlap(qlist, ovlapvar, buf);
 186: 
 187: 
 188:         /* now process each component */
 189:         mark1 = markbuf(buf);
 190:         for (qp = qlist; tree = *qp++; )
 191:         {
 192: 
 193: #			ifdef xDTR1
 194:             if (tTf(15, 6))
 195:                 printree(tree, "Next piece");
 196: #			endif
 197: 
 198:             /* determine result relation name */
 199:             newr = fixresult(root, tree, &newqmode, qmode, result_num);
 200: 
 201:             /*
 202: 			** Run the query. If reduction is being
 203: 			** performed, the actual tree given to
 204: 			** the decision routine must be a copy
 205: 			** to protect from the recursive call changing
 206: 			** the tree. Any work done at this level,
 207: 			** must be to the original tree
 208: 			*/
 209:             newtree = tree;
 210:             if (ovlapvar != -1)
 211:             {
 212:                 freebuf(buf, mark1);
 213:                 newtree = copy_ands(tree, buf);
 214:             }
 215:             qtrue = decision(newtree, newqmode, newr, buf);
 216: 
 217:             /* fix up the range table */
 218:             fixrange(root, tree, ovlapvar, ovlaprelnum, newr);
 219: 
 220:             /* if last piece was false then done */
 221:             if (!qtrue)
 222:                 break;
 223: 
 224:         }
 225: 
 226:         /* restore the trees */
 227:         rmovlap(qlist, ovlapvar);
 228: 
 229:         /* restore range table back to original */
 230:         endquery(locrange, TRUE);   /* reopen previous range */
 231: 
 232:         /* return any buffer space used */
 233:         freebuf(buf, mark);
 234:     }
 235: 
 236:     /* all done with query */
 237:     return (qtrue);
 238: }
 239: 
 240: 
 241: fixresult(root, tree1, newmode, origmode, resnum)
 242: struct querytree    *root;
 243: struct querytree    *tree1;
 244: int         *newmode;
 245: int         origmode;
 246: int         resnum;
 247: 
 248: /*
 249: ** Fixresult -- Determine result relation for "tree" query.
 250: **	If "tree" is the original target list piece then use the
 251: **		original relation and mode.
 252: **	If "tree" is a reduction piece then create a temporary relation
 253: **		for it.
 254: **	If "tree" is a disjoint piece then there is no target list nor
 255: **		result relation.
 256: **
 257: **	Return:
 258: **		result relation number
 259: **	Side Effects:
 260: **		*newmode is set to the query mode of the next piece
 261: */
 262: 
 263: {
 264:     register struct querytree   *tree;
 265:     register int            newresult;
 266: 
 267:     tree = tree1;
 268:     *newmode = mdRETR;
 269:     if (tree->left->sym.type != TREE)
 270:     {
 271:         if (tree != root)
 272:         {
 273:             /* make new result for reduction step */
 274:             newresult = mak_t_rel(tree, "r", -1);
 275:         }
 276:         else
 277:         {
 278:             /* final piece with original result and mode */
 279:             newresult = resnum;
 280:             *newmode = origmode;
 281:         }
 282:     }
 283:     else
 284:         newresult = NORESULT;
 285:     return (newresult);
 286: }
 287: 
 288: 
 289: fixrange(root, tree, ovlapvar, reductnum, newrelnum)
 290: struct querytree    *root;
 291: struct querytree    *tree;
 292: int         ovlapvar;
 293: int         reductnum;
 294: int         newrelnum;
 295: 
 296: /*
 297: **	Update range table after a reduction has been processed.
 298: **	Only the intermiediate reductions will affect the range
 299: **	table. The last piece does not.
 300: */
 301: 
 302: {
 303:     register int    old;
 304:     register int    i;
 305: 
 306:     if (root != tree)
 307:     {
 308:         /* this is an intermediate piece */
 309:         i = ovlapvar;
 310: 
 311:         if (newrelnum >= 0)
 312:         {
 313:             old = new_range(i, newrelnum);
 314:             if (old != reductnum)
 315:                 dstr_rel(old);
 316:             openr1(i);
 317:         }
 318:     }
 319: }
 320: 
 321: 
 322: fixovlap(qlist, ovlapvar, buf)
 323: struct querytree    *qlist[];
 324: int         ovlapvar;
 325: char            *buf;
 326: 
 327: /*
 328: ** Fixovlap -- Adjust subsequent trees which reference the reduction var
 329: **
 330: **	If the first query in list redefines the reduction variable
 331: **	(if any) then each subsequent query which references the
 332: **	reduction variable is adjusted.
 333: **	Since there may be multiple pieces,
 334: **	subsequence redefinitions are done without
 335: **	reallocating buffer space.
 336: **
 337: */
 338: 
 339: {
 340:     register struct querytree   **qp, *piece, **qp1;
 341:     struct querytree        *next;
 342:     int             ovmap;
 343: 
 344:     ovmap = 1 << ovlapvar;
 345: 
 346:     /* for each piece, if it redefines ovlapvar, then fix up rest */
 347:     for (qp = qlist; piece = *qp++; )
 348:     {
 349:         if (((struct qt_root *)piece)->lvarm & ovmap)
 350:         {
 351:             for (qp1 = qp; next = *qp1++; )
 352:             {
 353:                 if ((((struct qt_root *)next)->lvarm | ((struct qt_root *)next)->rvarm) & ovmap)
 354:                 {
 355:                     tempvar(next, mksqlist(piece, ovlapvar), buf);
 356:                     buf = NULL; /* do not allocate on subsequent refs */
 357:                 }
 358:             }
 359:         }
 360:     }
 361: }
 362: 
 363: 
 364: rmovlap(qlist, ovlapvar)
 365: struct querytree    *qlist[];
 366: int         ovlapvar;
 367: 
 368: /*
 369: ** Rmovlap -- Restore query trees back to their original state.
 370: **
 371: **	Rmovlap undoes the effect of fixovlap(). Any references
 372: **	to the reduction variable which were adjusted are now
 373: **	reverted back to the original reference. Note that the
 374: **	first piece is not effected by fixovlap.
 375: */
 376: 
 377: {
 378:     register struct querytree   **qp, *tree;
 379:     register int            ovmap;
 380: 
 381:     if (ovmap = (1 << ovlapvar))
 382:     {
 383:         /* for each piece, remove any tempvars */
 384:         for (qp = &qlist[1]; tree = *qp++; )
 385:         {
 386:             origvar(tree, mksqlist(tree, ovlapvar));
 387:         }
 388:     }
 389: }
 390: 
 391: 
 392: 
 393: 
 394: fixtl(tree1, qp1, ovlapvar, buf)
 395: struct querytree    *tree1;
 396: struct querytree    *qp1[];
 397: int         ovlapvar;
 398: char            *buf;
 399: 
 400: /*
 401: ** Fixtl -- Determine what the target list of each tree should be.
 402: **
 403: **	Fixtl takes each query which references the reduction variable
 404: **	and looks for references to that variable in subsequent queries.
 405: **	Dfind will build a target list which includes every domain
 406: **	which will later be referenced.
 407: */
 408: 
 409: {
 410:     register struct querytree   *tree, **qp, *next;
 411:     int             var, map;
 412: 
 413:     tree = tree1;
 414:     var = ovlapvar;
 415:     map = 1 << var;
 416: 
 417:     /*
 418: 	** if the last tree referenced the overlap variable then
 419: 	** try to fix next tree
 420: 	*/
 421:     if (((struct qt_root *)tree)->rvarm & map)
 422:     {
 423:         qp = qp1;
 424:         while (next = *qp++)
 425:         {
 426:             if ((((struct qt_root *)next)->lvarm | ((struct qt_root *)next)->rvarm) & map)
 427:                 dfind(next, buf, mksqlist(tree, var));
 428:         }
 429:     }
 430: }
 431: 
 432: 
 433: 
 434: # ifdef xDTR1
 435: listcomp(list, mesg)
 436: struct complist *list;
 437: char        *mesg;
 438: 
 439: /*
 440: **	This is strictly a debuggin routine used for
 441: **	printing component lists.
 442: */
 443: 
 444: {
 445:     register struct complist    *c, *cl;
 446:     register int            i;
 447: 
 448:     if (tTf(15, 14))
 449:     {
 450:         printf("%s\n", mesg);
 451:         i = -1;
 452: 
 453:         for (cl = list; cl; cl = cl->nextcomp)
 454:         {
 455:             i++;
 456:             printf("Component %d:map=%o\n", i, cl->bitmap);
 457:             for (c = cl; c; c = c->linkcomp)
 458:             {
 459:                 printf("%l, ", c->clause);
 460:                 if (tTf(15, 15))
 461:                 {
 462:                     printree(c->clause->left, "");
 463:                     writenod(c->clause);
 464:                 }
 465:             }
 466:             printf("\n");
 467:         }
 468:     }
 469: }
 470: # endif

Defined functions