Next: Overlap Method
Up: No Title
Previous: Algorithm : Pipe Sort
Input : Search lattice with group-by estimated sizes
Initialize worklist with MST (Minimum spanning Tree) of the
search lattice
while (worklist )
do begin
pick any tree T from the worklist ;
select-subtree(T)to be executed next ;
Compute-subtree(
);
select-subtree(T)
If memory required by T is less than available , return T;
Else, let S be the attributes of root(T)
/* we will pick
for partitioning root(T)
For any s we get a subtree Ts of T also rooted at T including
all groupbys that contain s */
Ps = maximum number of partitions of root(T) possible if partitioned on
.
We choose
such that
memory required by
Ts / Ps < memory available,
Ts is the largest over all subsets of S.
remove Ts from T.
This leaves T - Ts, a forest of smaller trees ; add this to
the worklist ;
return Ts ;
Compute-Subtree(T)
M = memory available ;
numParts = memory required by
;
Partition root of
into numParts ;
For each partition of root(
)
For each node n in
/* scan in a Breadth First Manner * //
compute all children n in One scan;
If n is cached, save it to disk and release memory occupied by its hashtable ;
Next: Overlap Method
Up: No Title
Previous: Algorithm : Pipe Sort
DBMS
1999-04-01