Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA

Summary: Proposes q-error-bounded histograms with a cardinality threshold θ to speed up query-plan estimates. Leverages SAP HANA's order-preserving dictionary encoding for fast θ,q-acceptability tests; yields sub-second histogram construction and ~5% storage. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4908
Venue: SIGMOD
Year: 2014
Pagerank: 6.1189424e-05
Overall Rank: 5,693 | 60.95%
DOI: 10.1145/2588555.2595629

Incoming Non-self Citations Over Time

Authors

1. Guido Moerkotte (University of Mannheim)
2. David DeHaan (SAP)
3. Norman May (SAP)
4. Anisoara Nica (SAP)
5. Alexander Boehm (SAP)

BibTeX Citation

@inproceedings{moerkotte_sigmod14,
        title = {{Exploiting Ordered Dictionaries to Efficiently Construct Histograms with Q-Error Guarantees in SAP HANA}},
        author = {Moerkotte, Guido and DeHaan, David and May, Norman and Nica, Anisoara and Boehm, Alexander},
        series = {{SIGMOD} '14},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2588555.2595629},
        url = {https://dl.acm.org/doi/10.1145/2588555.2595629},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,170	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011827259
1,536	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	0.00010460864
3,162	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB	7.6785856e-05
6,907	Statisticum: Data Statistics Management in SAP HANA	2017	VLDB	5.7417459e-05
8,183	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	5.4714466e-05
9,192	Efficient and Effective Cardinality Estimation for Skyline Family	2023	SIGMOD	5.3058708e-05
9,455	Small Selectivities Matter: Lifting the Burden of Empty Samples	2021	SIGMOD	5.2653318e-05
9,618	SplineSketch: Even More Accurate Quantiles with Error Guarantees	2026	SIGMOD	5.2434488e-05
9,666	Constructing Join Histograms from Histograms with q-error Guarantees	2016	SIGMOD	5.2406474e-05
10,891	Cardinality Estimation for Having-Clauses	2025	VLDB	5.093636e-05
11,644	Index-Based Join Size Estimation Using Adaptive Sampling	2021	SIGMOD	5.093636e-05
12,178	Multi-dimensional Data Statistics for Columnar In-Memory Databases	2014	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
165	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.00027693424
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
288	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00022296371
388	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019410042
940	Enhancements to SQL Server Column Stores	2013	SIGMOD	0.00013081205
8,998	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	5.3355988e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,178	Multi-dimensional Data Statistics for Columnar In-Memory Databases	2014	SIGMOD
2	7,554	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB
3	6,907	Statisticum: Data Statistics Management in SAP HANA	2017	VLDB
4	4,889	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS
5	9,666	Constructing Join Histograms from Histograms with q-error Guarantees	2016	SIGMOD
6	274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD
7	435	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB
8	388	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB
9	3,575	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS
10	267	Optimal Histograms with Quality Guarantees	1998	VLDB