Bringing order to query optimization

Giedrius Slivinskas, Christian S. Jensen, Richard T. Snodgrass

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


A variety of developments combine to highlight the need for respecting order when manipulating relations. For example, new functionality is being added to SQL to support OLAP-style querying in which order is frequently an important aspect. The set- or multiset-based frameworks for query optimization that are currently being taught to database students are increasingly inadequate. This paper presents a foundation for query optimization that extends existing frameworks to also capture ordering. A list-based relational algebra is provided along with three progressively stronger types of algebraic equivalences, concrete query transformation rules that obey the different equivalences, and a procedure for determining which types of transformation rules are applicable for optimizing a query. The exposition follows the style chosen by many textbooks, making it relatively easy to teach this material in continuation of the material covered in the textbooks, and to integrate this material into the textbooks.

Original languageEnglish (US)
Pages (from-to)5-14
Number of pages10
JournalSIGMOD Record
Issue number2
StatePublished - Jun 2002

ASJC Scopus subject areas

  • Software
  • Information Systems


Dive into the research topics of 'Bringing order to query optimization'. Together they form a unique fingerprint.

Cite this