Exploiting early sorting and early partitioning for decision support queryprocessing

Decision support queries typically involve several joins, a grouping with a ggregation, and/or sorting of the result tuples. We propose two new classes of query evaluation algorithms that can be used to speed up the execution of such queries. The algorithms are based on (1) early sorting and (2) earl y partitioning - or a combination of both. The idea is to push the sorting and/or the partitioning to the leaves, i.e., the base relations, of the que ry evaluation plans (QEPs) and thereby avoid sorting or partitioning large intermediate results generated by the joins. Both early sorting and early p artitioning are used in combination with hash-based algorithms for evaluati ng the joints) and the grouping. To enable early sorting, the sort order ge nerated at an early stage of the QEP is retained through an arbitrary numbe r of so-called order-preserving hashjoins. To make early partitioning appli cable to a large class of decision support queries, we generalize the so-ca lled hash teams proposed by Graefe et al. [GBC98]. Hash teams allow to perf orm several hash-based operations (join and grouping! on the same attribute in one pass without repartitioning intermediate results. Our generalizatio n consists of indirectly partitioning the input data. indirect partitioning means partitioning the input data on an attribute that is not directly nee ded for the next hash-based operation, and it involves the construction of bitmaps to approximate the partitioning for the attribute that is needed in the next hash-based operation. Our performance experiments show that such QEPs based on early sorting, early partitioning, or both in combination per form significantly better than conventional strategies for many common clas ses of decision support queries.