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

Considerations about Implementation Variants for Position Lists

Authors:
Andreas Schmidt
Daniel Kimmig

Keywords: Column stores, PositionList implementation variants, bitvector, compression, run length encoding, performance measure

Abstract:
Within “traditional” database systems (row store), the values of a tuple are usually stored in a physically connected manner. In a column store by contrast, all values of each single column are stored one after another. This orthogonal storage organization has the advantage that only data from columns which are of relevance to a query have to be loaded during query processing. Due to the storage organization of a row store, all columns of a tuple are loaded, despite the fact that only a small portion of them are of interest to processing. The orthogonal organization has some serious implications on query processing: While in a traditional row store, complex predicates can be evaluated at once, this is not possible in a column store. To evaluate complex conditions on multiple columns, an additional data structure is required, the so-called Position List. At first glance these Position Lists can easily be implemented as an dynamic array. But there are a number of situations where this is not the first choice in terms of memory consumption and time behavior. This paper will discuss some implementation alternatives based on (compressed) bitvectors. A number of tests will be reported and the runtime behavior and memory consumption of the different implementations will be presented. Finally, some recommendation will be made as to the situations in which the different implementation variants for Position Lists will be suited best. Their suitability depends strongly on the selectivity of a query or predicate.

Pages: 108 to 115

Copyright: Copyright (c) IARIA, 2013

Publication date: January 27, 2013

Published in: conference

ISSN: 2308-4332

ISBN: 978-1-61208-247-9

Location: Seville, Spain

Dates: from January 27, 2013 to February 1, 2013