Attributes in a data warehouse fact table typically have hierarchies defined on them (by means of auxiliary dimension tables). The product of the dimensional hierarchy levels forms a lattice and leads to a natural notion of query classes. Optimal clustering is a combinatorially explosive problem with a huge search space (doubly exponential in number of hierarchy levels). We identify an important subclass of clustering strategies called {\em lattice paths}, and present a dynamic programming algorithm for finding the optimal lattice path clustering, in time linear in the lattice size.

We additionally propose a technique called {\em snaking}, which when applied to a lattice path, always reduces its cost. For a representative class of star schemas, we show that for every workload, there is a snaked lattice path which is globally optimal. Further, we prove that the clustering obtained by applying snaking to the optimal lattice path is never much worse than the globally optimal snaked lattice path clustering. We show: (i) there are workloads where the often proposed Hilbert curve clustering can be arbitrarily worse than the optimal snaked lattice path, but (ii) when the workload is unknown a priori, the worst case performance of the Hilbert curve is better than that of snaked lattice paths.

We complement our analyses and validate the practical utility of our techniques with experiments using TPC-D benchmark data.