Please use this identifier to cite or link to this item:
Title: Sort-sharing-aware query processing
Authors: Cao, Y.
Bramandia, R. 
Chan, C.-Y. 
Tan, K.-L. 
Keywords: Cooperative sorting
Query processing
Sort operation
Sort sharing
Issue Date: 2012
Citation: Cao, Y., Bramandia, R., Chan, C.-Y., Tan, K.-L. (2012). Sort-sharing-aware query processing. VLDB Journal 21 (3) : 411-436. ScholarBank@NUS Repository.
Abstract: Many database applications require sorting a table (or relation) over multiple sort orders. Some examples include creation of multiple indices on a relation, generation of multiple reports from a table, evaluation of a complex query that involves multiple instances of a relation, and batch processing of a set of queries. In this paper, we study how to optimize multiple sortings of a table. We investigate the correlation between sort orders and exploit sort-sharing techniques of reusing the (partial) work done to sort a table on a particular order for another order. Specifically, we introduce a novel and powerful evaluation technique, called cooperative sorting, that enables sort sharing between seemingly non-related sort orders. Subsequently, given a specific set of sort orders, we determine the best combination of various sort-sharing techniques so as to minimize the total processing cost. We also develop techniques to make a traditional query optimizer extensible so that it will not miss the truly cheapest execution plan with the sort-sharing (post-) optimization turned on. We demonstrate the efficiency of our ideas with a prototype implementation in PostgreSQL and evaluate the performance using both TPC-DS benchmark and synthetic data. Our experimental results show significant performance improvement over the traditional evaluation scheme. © 2011 Springer-Verlag.
Source Title: VLDB Journal
ISSN: 10668888
DOI: 10.1007/s00778-011-0251-9
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Jun 20, 2022


checked on Jun 20, 2022

Page view(s)

checked on Jun 23, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.