Algorithm : Pipe Hash

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 T_s of T also rooted at T including all groupbys that contain s */
P_s = maximum number of partitions of root(T) possible if partitioned on .
We choose such that
memory required by T_s / P_s < memory available,
T_s is the largest over all subsets of S.
remove T_s from T.
This leaves T - T_s, a forest of smaller trees ; add this to the worklist ;
return T_s ;

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 ;