The Final Result: The MV-Algorithm

1. For each argument column , create a list where is the longest prefix of column with at most a number and percentage %of variables
2. If then use the first clause as a separate partition (without indexing) else
   • sort the in descending order (w.r.t. their length) into the list
   • := length of first element in
   • := position of last column in with length with ;
     := length of this column;
     first elements of ;
     reorder w.r.t. selectivity
   • create a partition consisting of the first clauses; index the argument columns in ( index tree breadth)
   • for each constant/functor occurring multiply in one argument column of this partition do
     • form a procedure containing all selected clauses and the remaining argument columns in (only columns to the right of the current one)
     • apply the MV-Algorithm recursively to this procedure ( index tree depth)
3. If any clauses are left go to 1 else stop

Result of using the MV-Algorithm on our norm example:

In the above DAX, some sub-DAXes were pruned in order to reduce memory consumption. This pruning is performed by the pruning algorithm explained in [Ste92].

The benchmarks in appendix C give you an impression of the efficiency gains of the MV-Algorithm.