A cost-based range estimation for mapping top-k selection queries over relational databases

Anteneh Ayanso, Paulo B. Goes, Kumar Mehta

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


Finding efficient methods for supporting top-k relational queries has received significant attention in academic research. One of the approaches in the recent literature is query-mapping, in which top-k queries are mapped (translated) into equivalent range queries that relational database systems (RDBMSs) normally support. This approach combines the advantage of simplicity as well as practicality by avoiding the need for modifications to the query engine, or specialized data structures or indexing techniques to handle top-k queries separately. However, existing methods following this approach fall short of adequately modeling the problem environment and providing consistent results. In this article, the authors propose a cost-based range estimation model for the query-mapping approach. They provide a methodology for trading-off relevant query execution cost components and mapping a top-k query into a cost-optimal range query for efficient execution. Their experiments on real world and synthetic data sets show that the proposed strategy not only avoids the need to calibrate workloads on specific database contents, but also performs at least as well as prior methods.

Original languageEnglish (US)
Pages (from-to)1-25
Number of pages25
JournalJournal of Database Management
Issue number4
StatePublished - Oct 2009


  • Cost model
  • Query processing
  • Query-mapping
  • Relational databases
  • Top-k query
  • Tradeoff analysis
  • Uncertainty modeling

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'A cost-based range estimation for mapping top-k selection queries over relational databases'. Together they form a unique fingerprint.

Cite this