Record Details

Pipelining in multi-query optimization

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Pipelining in multi-query optimization
 
Creator DALVI, NILESH N
SANGHAI, SUMIT K
ROY, PRASAN
SUDARSHAN, S
 
Subject multi-query optimization
algorithms
heuristic methods
computational complexity
query processing
 
Description Database systems frequently have to execute a set of related queries, which share several common subexpressions. Multi-query optimization exploits this, by finding evaluation plans that share common results. Current approaches to multi-query optimization assume that common subexpressions are materialized. Significant performance benefits can be had if common subexpressions are pipelined to their uses, without being materialized. However, plans with pipelining may not always be realizable with limited buffer space, as we show. We present a general model for schedules with pipelining, and present a necessary and sufficient condition for determining validity of a schedule under our model. We show that finding a valid schedule with minimum cost is NP-hard. We present a greedy heuristic for finding good schedules. Finally, we present a performance study that shows the benefit of our algorithms on batches of queries from the TPCD benchmark.
 
Publisher Elsevier
 
Date 2009-09-19T07:12:43Z
2011-11-25T15:28:39Z
2011-12-26T13:05:10Z
2011-12-27T05:51:19Z
2009-09-19T07:12:43Z
2011-11-25T15:28:39Z
2011-12-26T13:05:10Z
2011-12-27T05:51:19Z
2003
 
Type Article
 
Identifier Journal of Computer and System Sciences 66(4), 728-762
0022-0000
http://dx.doi.org/10.1016/S0022-0000(03)00031-X
http://hdl.handle.net/10054/1644
http://dspace.library.iitb.ac.in/xmlui/handle/10054/1644
 
Language en