4.3BSD - /usr/ingres/source/decomp/decision.c

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

Defined functions