Exploiting ordered dictionaries to efficiently construct histograms with q-error guarantees in SAP HANA

Moerkotte, Guido ; DeHaan, David ; May, Norman ; Nica, Anisoara ; Böhm, Alexander

DOI: https://doi.org/10.1145/2588555.2595629
URL: http://dl.acm.org/citation.cfm?id=2595629
Additional URL: http://pi3.informatik.uni-mannheim.de/~norman/Moer...
Document Type: Conference or workshop publication
Year of publication: 2014
Book title: SIGMOD/PODS'14 : compilation proceedings of the 2014 ACM Symposium on Principles of Database Systems; ACM SIGMOD International Conference on Management of Data, and SIGMODS/PODS 2014 PhD Symposium; June 22 - 27, 2014, Snowbird, UT, USA
Page range: 361-372
Date of the conference: June 22-27, 2014
Publisher: Dyreson, Curtis
Place of publication: [New York, NY]
Publishing house: ACM
ISBN: 978-1-4503-2376-5
Publication language: English
Institution: School of Business Informatics and Mathematics > Practical Computer Science III (Moerkotte 1996-)
Subject: 004 Computer science, internet
Abstract: Histograms that guarantee a maximum multiplicative error (q-error) for estimates may significantly improve the plan quality of query optimizers. However, the construction time for histograms with maximum q-error was too high for practical use cases. In this paper we extend this concept with a threshold, i.e., an estimate or true cardinality θ, below which we do not care about the q-error because we still expect optimal plans. This allows us to develop far more efficient construction algorithms for histograms with bounded error. The test for θ, q-acceptability developed also exploits the order-preserving dictionary encoding of SAP HANA. We have integrated this family of histograms into SAP HANA, and we report on the construction time, histograms size, and estimation errors on real-world data sets. In virtually all cases the histograms can be constructed in far less than one second, requiring less than 5% of space compared to the original compressed data.
Additional information: CD-ROM

Dieser Eintrag ist Teil der Universitätsbibliographie.

Metadata export


+ Search Authors in

+ Page Views

Hits per month over past year

Detailed information

You have found an error? Please let us know about your desired correction here: E-Mail

Actions (login required)

Show item Show item