Skip to main navigation Skip to search Skip to main content

How to juggle columns: An entropy-based approach for table compression

  • Marcus Paradies*
  • , Christian Lemke
  • , Hasso Plattner
  • , Wolfgang Lehner
  • , Kai Uwe Sattler
  • , Alexander Zeier
  • , Jens Krueger
  • *Corresponding author for this work

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

Abstract

Many relational databases exhibit complex dependencies between data attributes, caused either by the nature of the underlying data or by explicitly denormalized schemas. In data warehouse scenarios, calculated key figures may be materialized or hierarchy levels may be held within a single dimension table. Such column correlations and the resulting data redundancy may result in additional storage requirements. They may also result in bad query performance if inappropriate independence assumptions are made during query compilation. In this paper, we tackle the specific problem of detecting functional dependencies between columns to improve the compression rate for column-based database systems, which both reduces main memory consumption and improves query performance. Although a huge variety of algorithms have been proposed for detecting column dependencies in databases, we maintain that increased data volumes and recent developments in hardware architectures demand novel algorithms with much lower runtime overhead and smaller memory footprint. Our novel approach is based on entropy estimations and exploits a combination of sampling and multiple heuristics to render it applicable for a wide range of use cases. We demonstrate the quality of our approach by means of an implementation within the SAP NetWeaver BusinessWarehouse Accelerator. Our experiments indicate that our approach scales well with the number of columns and produces reliable dependence structure information. This both reduces memory consumption and improves performance for nontrivial queries.

Original languageEnglish
Title of host publicationProceedings of the 14th International Database Engineering and Applications Symposium, IDEAS '10
Number of pages11
Publication date2010
Pages205-215
ISBN (Print)9781605589008
DOIs
Publication statusPublished - 2010
Externally publishedYes
Event14th International Database Engineering and Applications Symposium, IDEAS '10 - Montreal, QC, Canada
Duration: 16 Aug 2010 → 18 Aug 2010

Conference

Conference14th International Database Engineering and Applications Symposium, IDEAS '10
Country/TerritoryCanada
CityMontreal, QC
Period16/08/2010 → 18/08/2010
SponsorACM, BytePress, Concordia University
SeriesACM International Conference Proceeding Series

Fingerprint

Dive into the research topics of 'How to juggle columns: An entropy-based approach for table compression'. Together they form a unique fingerprint.

Cite this