Optimizing sort order query execution in balanced and nested grid files

Disk input/output (I/O) efficient query execution is an important topic with respect to DBMS performance. In this context, we elaborate on the construction of disk access plans for sort order queries in balanced and nested grid files. The key idea is to use the order information contained in the directory of the multiattribute search structure. The presented algorithms are shown to yield a significant decrease in the number of disk I/O operations by appropriate use of the order information. Two algorithms for the construction of appropriate disk access plans are proposed, namely a greedy approach and a heuristic divide-and-conquer approach. Both approaches yield considerable I/O savings compared to straightforward query processing without consideration of any directory order information. The former performs well for small buffer page allocations, i.e., for a small number of buffer pages relative to the number of data buckets processed in the query. The latter is superior to the greedy algorithm with respect to the total number of I/O operations and with respect to the overall maximum of buffer pages needed to achieve the minimal number of disk I/O operations. Both approaches rely on a binary trie as a temporary data structure. This trie is used as an explicit representation of the order information. The storage consumption of the temporary data structure is shown to be negligible in realistic cases, Even for pathological cases with respect to degenerated balanced and nested grid files, reasonable upper bounds can be given