TY - GEN
T1 - Supporting ad-hoc ranking aggregates
AU - Li, Chengkai
AU - Chang, Kevin Chen Chuan
AU - Ilyas, Ihab F.
N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2006
Y1 - 2006
N2 - This paper presents a principled framework for efficient processing of ad-hoc top-k (ranking) aggregate queries, which provide the k groups with the highest aggregates as results. Essential support of such queries is lacking in current systems, which process the queries in a nave materialize-group-sort scheme that can be prohibitively inefficient. Our framework is based on three fundamental principles. The Upper-Bound Principle dictates the requirements of early pruning, and the Group-Ranking and Tuple-Ranking Principles dictate group-ordering and tuple-ordering requirements. They together guide the query processor toward a provably optimal tuple schedule for aggregate query processing. We propose a new execution framework to apply the principles and requirements. We address the challenges in realizing the framework and implementing new query operators, enabling efficient group-aware and rank-aware query plans. The experimental study validates our framework by demonstrating orders of magnitude performance improvement in the new query plans, compared with the traditional plans.
AB - This paper presents a principled framework for efficient processing of ad-hoc top-k (ranking) aggregate queries, which provide the k groups with the highest aggregates as results. Essential support of such queries is lacking in current systems, which process the queries in a nave materialize-group-sort scheme that can be prohibitively inefficient. Our framework is based on three fundamental principles. The Upper-Bound Principle dictates the requirements of early pruning, and the Group-Ranking and Tuple-Ranking Principles dictate group-ordering and tuple-ordering requirements. They together guide the query processor toward a provably optimal tuple schedule for aggregate query processing. We propose a new execution framework to apply the principles and requirements. We address the challenges in realizing the framework and implementing new query operators, enabling efficient group-aware and rank-aware query plans. The experimental study validates our framework by demonstrating orders of magnitude performance improvement in the new query plans, compared with the traditional plans.
KW - Aggregate query
KW - Decision support
KW - OLAP
KW - Ranking
KW - Top-k query processing
UR - http://www.scopus.com/inward/record.url?scp=34250767109&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34250767109&partnerID=8YFLogxK
U2 - 10.1145/1142473.1142481
DO - 10.1145/1142473.1142481
M3 - Conference contribution
AN - SCOPUS:34250767109
SN - 1595934340
SN - 9781595934345
T3 - Proceedings of the ACM SIGMOD International Conference on Management of Data
SP - 61
EP - 72
BT - SIGMOD 2006 - Proceedings of the ACM SIGMOD International Conference on Management of Data
T2 - 2006 ACM SIGMOD International Conference on Management of Data
Y2 - 27 June 2006 through 29 June 2006
ER -