Exploitation of pre-sortedness for sorting in query processing: The TempTris-algorithm for UB-Trees

Abstract

Bulk loading is used to efficiently build a table or access structure, if a large data set is available at index creation time, e.g., the spool process of a data warehouse or the creation of intermediate results during query processing. In this paper we introduce the TempTris algorithm that creates a multidimensional partitioning from a one-dimensionally sorted stream of tuples. In order to achieve that, TempTris exploits the fact that a one-dimensional order can be used as a partial multidimensional order for the creation of a multidimensional partitioning. In this way, TempTris avoids external sorting for the creation of a multidimensional index. In combination with the Tetris sort algorithm, TempTris can be used to create intermediate query processing results that can - without external sorting - be re-used to generate various sort orders. As example of this new processing technique we propose an efficient algorithm for computing an aggregation lattice. Thus, TempTris can also be used to speed up the processing of CUBE operators that frequently occur in OLAP applications.