Home // DBKDA 2012, The Fourth International Conference on Advances in Databases, Knowledge, and Data Applications // View article

A Case for Inverted Indices in In-Memory Databases

Authors:
Jens Krueger
Johannes Wust
Martin Faust
Tim Berning
Hasso Plattner

Keywords: In-Memory Database; Inverted Index; Index Maintenance

Abstract:
Recent database research has focused on in-memory databases, which can be used in mixed workload scenarios, enabling OLTP and OLAP queries on the same database en- gine. These compressed column-oriented database systems use a differential store concept to enable fast inserting and require a merge process to compact the data periodically in a compressed main partition that is changed by the merge process only. This characteristic feature calls for a re-evaluation of the performance of inverted indices. In this paper we present a use case for an inverted index in a column-oriented in-memory database system to reduce the total costs of query processing in a mixed workload environment. We evaluate the benefits and drawbacks of using the index structure to answer queries and the costs of maintaining the index, especially during the merge process. An analytical model is introduced to compute the theoretical cost of index scans. Furthermore a comparison between different index maintenance strategies is presented. The theoretical findings are verified in a prototypic implementation within the HYRISE database system. Our contributions are an analytical framework to evaluate the benefit of an inverted index during query execution, the verification in an in-memory database system, and an evaluation of different index maintenance strategies. From the presented findings we conclude that indexing can be an efficient instrument to meet the performance requirements in a mixed-workload and main memory-based environment.

Pages: 15 to 24

Copyright: Copyright (c) IARIA, 2012

Publication date: February 29, 2012

Published in: conference

ISSN: 2308-4332

ISBN: 978-1-61208-185-4

Location: Saint Gilles, Reunion

Dates: from February 29, 2012 to March 5, 2012