Supporting ad-hoc ranking aggregates

Chengkai Li, Kevin Chen Chuan Chang, Ihab F. Ilyas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationSIGMOD 2006 - Proceedings of the ACM SIGMOD International Conference on Management of Data
Pages61-72
Number of pages12
DOIs
StatePublished - Dec 1 2006
Event2006 ACM SIGMOD International Conference on Management of Data - Chicago, IL, United States
Duration: Jun 27 2006Jun 29 2006

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078

Other

Other2006 ACM SIGMOD International Conference on Management of Data
CountryUnited States
CityChicago, IL
Period6/27/066/29/06

    Fingerprint

Keywords

  • Aggregate query
  • Decision support
  • OLAP
  • Ranking
  • Top-k query processing

ASJC Scopus subject areas

  • Software
  • Information Systems

Cite this

Li, C., Chang, K. C. C., & Ilyas, I. F. (2006). Supporting ad-hoc ranking aggregates. In SIGMOD 2006 - Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 61-72). (Proceedings of the ACM SIGMOD International Conference on Management of Data). https://doi.org/10.1145/1142473.1142481