Return to selectv.c CVS log

Up to [CSRG BSD Unix] / 43BSD / ingres / source / decomp

Annotation of 43BSD/ingres/source/decomp/selectv.c, revision 1.1

1.1     ! root        1: # include      <ingres.h>
        !             2: # include      <symbol.h>
        !             3: # include      <tree.h>
        !             4: # include      "globs.h"
        !             5: # include      <sccs.h>
        !             6: 
        !             7: SCCSID(@(#)selectv.c   8.1     12/31/84)
        !             8: 
        !             9: /*
        !            10: **  SELECTV -- Select a variable for substitution
        !            11: **
        !            12: **     Selectv is called to determinimume the "best" variable
        !            13: **     to substitute for. The algorithm used is based on
        !            14: **     the Wong/Youseffi paper ERL M78/17. Selectv returns
        !            15: **     the variable to be substituted or it returns -1 which
        !            16: **     indicates that there is a relation with no tuples.
        !            17: **     If there is only one variable left, it is of course
        !            18: **     the one choosen.
        !            19: **
        !            20: **     For cases of more than one variable, a variable with
        !            21: **     0 or 1 tuples will always be choosen. Otherwise the
        !            22: **     variable with the smallest "costfunction" will be selected.
        !            23: **     In case of a tie, the variable with the smallest tuple count
        !            24: **     is selected.
        !            25: **
        !            26: **     The costfunction is:
        !            27: **             |Ri|
        !            28: **            ______
        !            29: **             Peffective i
        !            30: **
        !            31: **     where |Ri| = cardinality of variable i.
        !            32: **     and   Peff = The number of pages needed to be accessed to
        !            33: **                     safisfy a query on Ri assuminimumg all other
        !            34: **                     variables have been substituted for.
        !            35: **
        !            36: **
        !            37: **     Peff is only an estimate. The estimate is based on the
        !            38: **     storage structure of Ri and on whether Ri is used in
        !            39: **     the target list. Considering only equality clauses,
        !            40: **     the relation's structure is examinimumed to see if any
        !            41: **     can be used effectively. The following assumptions are
        !            42: **     made:
        !            43: **             useful hash: Peff = 1
        !            44: **             useful isam: Peff = 2
        !            45: **             useful hash sec index: Peff = 2
        !            46: **             useful isam sec index: Peff = 3
        !            47: **
        !            48: **     If there is no useful structure or if the relation is
        !            49: **     a heap then:
        !            50: **             Peff = number of pages Ri occupies
        !            51: **     If the relation is not in the target list then its
        !            52: **     function is only an existence test. Scanning can and
        !            53: **     is stopped the first time a tuple is found which satisfies.
        !            54: **     We assume that on the average only 1/4 of the pages
        !            55: **     will have to be examinimumed.
        !            56: **
        !            57: **     Parameters:
        !            58: **             root - root of the query
        !            59: **
        !            60: **     Returns:
        !            61: **             The variable to substitute for
        !            62: **                     or
        !            63: **             -1 if the query is false
        !            64: **
        !            65: **     Side Effects:
        !            66: **             can cause a relation to be opened since
        !            67: **             ckpkey needs to know the key structure.
        !            68: **
        !            69: **     Called By:
        !            70: **             decompy, decompz
        !            71: **
        !            72: **     Trace Flags:
        !            73: **             44
        !            74: */
        !            75: 
        !            76: selectv(root)
        !            77: register QTREE *root;
        !            78: {
        !            79:        int                             minimum, var, map, i;
        !            80:        register struct rang_tab        *rt, *rx;
        !            81:        long                            costfunc(), lx, lt;
        !            82: 
        !            83:        map = root->sym.value.sym_root.lvarm | root->sym.value.sym_root.rvarm;
        !            84: 
        !            85:        minimum = -1;
        !            86:        lx = 0;
        !            87:        rx = NULL;
        !            88: 
        !            89:        for (i = 1, var = 0; map; i <<= 1, var++)
        !            90:        {
        !            91:                if ((map & i) == 0)
        !            92:                        continue;
        !            93: 
        !            94:                map &= ~i;
        !            95:                rt = &De.de_rangev[var];
        !            96:                if (rx == NULL)
        !            97:                {
        !            98:                        rx = rt;
        !            99:                        minimum = var;
        !           100:                        if (map == 0 || rt->rtcnt < 2)
        !           101:                                break;
        !           102:                        lx = costfunc(root, var, rt);
        !           103:                }
        !           104:                else
        !           105:                {
        !           106:                        if (rt->rtcnt < 2)
        !           107:                        {
        !           108:                                rx = rt;
        !           109:                                minimum = var;
        !           110:                                break;
        !           111:                        }
        !           112: 
        !           113:                        lt = costfunc(root, var, rt);
        !           114:                        if (lt < lx)
        !           115:                        {
        !           116:                                rx = rt;
        !           117:                                minimum = var;
        !           118:                                lx = lt;
        !           119:                        }
        !           120:                }
        !           121:        }
        !           122: 
        !           123:        if (minimum == -1)
        !           124:                syserr("selectv:no source var");
        !           125: 
        !           126: #      ifdef xDTR1
        !           127:        if (tTf(44, 1))
        !           128:        {
        !           129:                printf("selectv:%d,tups=%ld,", minimum, rx->rtcnt);
        !           130:                printf("cf=%ld,", lx);
        !           131:                nodepr(root);
        !           132:        }
        !           133: #      endif
        !           134: 
        !           135:        if (rx->rtcnt == 0)
        !           136:                minimum = -1;
        !           137: 
        !           138:        return (minimum);
        !           139: }
        !           140: 
        !           141: 
        !           142: 
        !           143: long
        !           144: costfunc(root, var, rx)
        !           145: QTREE          *root;
        !           146: int            var;
        !           147: struct rang_tab        *rx;
        !           148: {
        !           149:        register struct rang_tab        *r;
        !           150:        register int                    i;
        !           151:        register char                   *lp;
        !           152:        char                            linkmap[MAXDOM];
        !           153:        long                            rel_page(), l;
        !           154:        int                             c_bug;
        !           155: 
        !           156:        r = rx;
        !           157: 
        !           158:        for (lp = linkmap, i = MAXDOM; i--; )
        !           159:                *lp++ = 0;
        !           160:        i = var;
        !           161: 
        !           162:        /*
        !           163:        ** The c-compiler does not know how to generate code
        !           164:        ** for the assignment of an short to a long inside
        !           165:        ** an "if" expression. Therefore the variable "c_bug"
        !           166:        ** is assigned the value of ckpkey inside the "if".
        !           167:        ** The value is assigned to "l" in the "else".
        !           168:        */
        !           169:        if (!findlinks(root, -1, i, linkmap) || (c_bug = ckpkey(linkmap, i)) == 0)
        !           170:        {
        !           171:                l = rel_pages(r->rtcnt, r->rtwid);
        !           172: 
        !           173:                /* if not in target list, assume 1/4 */
        !           174:                if ((root->sym.value.sym_root.lvarm & (01 << i)) == 0)
        !           175:                {
        !           176:                        l >>= 2;
        !           177:                        if (l == 0)
        !           178:                                l = 1;
        !           179:                }
        !           180:        }
        !           181:        else
        !           182:                l = c_bug;      /* l could not be assigned directly above */
        !           183: 
        !           184:        l = r->rtcnt / l;
        !           185: 
        !           186: #      ifdef xDTR1
        !           187:        if (tTf(44, 3))
        !           188:                printf("costfunc %d is %ld\n", i, l);
        !           189: #      endif
        !           190:        return (l);
        !           191: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.