Home // International Journal On Advances in Software, volume 7, numbers 1 and 2, 2014 // View article

Implementation Variants for Position Lists

Authors:
Andreas Schmidt
Daniel Kimmig
Steffen Scholz

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 a 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. We additionally extended the existing WAH library for compressed bitvectors by a number of new methods to be used for the purpose of implementing the functionality of Position Lists based on (compressed) bitvectors. 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: 391 to 401

Copyright: Copyright (c) to authors, 2014. Used with permission.

Publication date: June 30, 2014

Published in: journal

ISSN: 1942-2628