Pipelining in multi-query optimization
DSpace at IIT Bombay
View Archive InfoField | 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
|
|