Choosing a set of Cuboid for Overlapped Computation

The goal is to identify subsets of search lattice which can be computed concurrently. The estimates cuboid sizes are available. If a cuboid can be computed with available memory, then it is marked Partition state. For some cuboid, it may be possible to allocate only one page, and they are marked in SortRun state. When a cuboid is in Parition state, its tuples can be pipelined for computing teh descendent cuboids in the same pass, while for the cuboids with SortRun state, the page is used to write out sorted runs for this cuboid on disk.
Following constraints are there for marking the cuboid state :

1.

A cuboid can be considered for computation if either its parent is the root of the subtree or the parent has been marked as being in the partition state.

2.

The total memory allocated to all the cuboids should not be more than available memory.

The heuristic of traversing the tree in Breadth First order is used here :

• Cuboids to the left have smaller partition size and hence require less memory. So consider these before the cuboids to the right.
• Cuboids with more number of attributes are bigger. Thus, they are given a higher priority for allocation.

Algorithm : Computing a Cuboid for (each tuple t of B) do
if (state == partition)then
process-partition(t)
else
process-sorted-run(t)
endif
write the final partition or sorted run currently in memory to disk
endfor
END

process-partition(t)
If t starts new partition, output the current paritition at the end of the cuboid, start a new one and make it current.
If t matches with an existing tuple in the partition, then recompute the aggregate.
If t is not same as the existing tuple, then insert it into the current partition.

process-sortrun(t)
If t starts a new sorted run, flush all its pages and start a new sorted run.
If t matches with the last tuple then recompute aggregate.
If t does not match the last tuple, append tuple to the end of the existing run. If, there is no space in the allocated memory for the sorted run, flush the pages in the memory to disk.