|
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. |
 Search Authors in
BASE:
Moerkotte, Guido
;
DeHaan, David
;
May, Norman
;
Nica, Anisoara
;
Böhm, Alexander
Google Scholar:
Moerkotte, Guido
;
DeHaan, David
;
May, Norman
;
Nica, Anisoara
;
Böhm, Alexander
You have found an error? Please let us know about your desired correction here: E-Mail
Actions (login required)
 |
Show item |
|
|
