[prev] 43 [next]

Selection in Heaps

For all selection queries, the only possible strategy is:

// select * from R where C
f = openFile(fileName("R"),READ);
for (p = 0; p < nPages(f); p++) {
    buf = readPage(f, p);
    for (i = 0; i < nTuples(buf); i++) {
        tup = getTuple(buf,i);
        if (tup satisfies C)
            add tup to result set
    }
}

i.e. linear scan through file searching for matching tuples