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

##### Functions

    decision          X
    fixovlap          X
    fixrange          X
    fixresult         X
    fixtl             X
    listcomp          X
    rmovlap           X

       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

decision defined in line 30; used 3 times

- in line 215
- in /usr/ingres/source/decomp/decomp.c line 121, 219

fixovlap defined in line 322; used 1 times

- in line 185

fixrange defined in line 289; used 1 times

- in line 218

fixresult defined in line 241; used 1 times

- in line 199

fixtl defined in line 394; used 1 times

- in line 182

listcomp defined in line 435; used 3 times

- in line 85, 133, 150

rmovlap defined in line 364; used 1 times

- in line 227

Last modified: 1995-04-14 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1473 |