Efficient Processing of Ad-Hoc Top-k Aggregate Queries in OLAP

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

Permalink

https://hdl.handle.net/2142/11065 Copy

Description

Title

Efficient Processing of Ad-Hoc Top-k Aggregate Queries in OLAP

Author(s)

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

Issue Date

2005-06

Keyword(s)

Web search; database systems

Abstract

In this paper, we develop a principled framework for efficient processing of ad-hoc top-k (ranking) aggregate queries in OLAP. Such queries provide the k groups with the highest aggregates to decision makers. Essential support of top-k aggregate queries is lacking in current RDBMSs, which process such queries in a naive and overkill materialize- group-sort scheme, therefore can be prohibitively inefficient. Our new framework is based on two fundamental properties, the Group-Ranking and Tuple-Ranking Principles. The principles dictate group-ordering and tuple-ordering requirement that together guide the query processor toward the optimal aggregate query processing. To realize the requirements, we propose a new execution model and address the challenges of implementing new query operators, enabling efficient top-k aggregate query plans that are both group- aware and rank-aware. The experimental study validates our framework by demonstrating orders of magnitude performance improvement in the new query plans, compared with the traditional approach.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11065

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections