Pack Indexing for Time-Constrained In-Memory Query Processing

Abstract: Main memory databases management systems are used more often and in a wide spread of application scenarios. To take significant advantage of the main mem-ory read performance, most techniques known from traditional disk-centric database systems have to be adapted and re-designed. In the field of indexing, many main-memory-optimized index structures have been proposed. Most of these works aim at primary indexing. Secondary indexes are rarely considered in the context of main memory databases. Either query performance is sufficiently good without secondary indexing or main memory is a resource too scarce to invest in huge secondary indexes. A more subtle trade between benefit and costs of secondary indexing has not been considered so far. In this paper we present Pack Indexing, a secondary indexing technique for main memory databases that allows a precise trade-off between the benefit in query execution time gained with a secondary index and main memory invested for that index. Compared to traditional indexing, Pack Indexing achieves this by varying the granularity of indexing. We discuss the Pack Indexing concept in detail and describe how the concept can be implemented. To demonstrate the usefulness and the effectiveness of our approach, we present several experiments with different datasets.