@conference {13369,
	title = {Flow Algorithms for Parallel Query Optimization},
	booktitle = {IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008},
	year = {2008},
	month = {2008/04/07/12},
	pages = {754 - 763},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We address the problem of minimizing the response time of a multi-way join query using pipelined (inter-operator) parallelism, in a parallel or a distributed environment. We observe that in order to fully exploit the parallelism in the system, we must consider a new class of ";interleaving"; plans, where multiple query plans are used simultaneously to minimize the response time of a query (or to maximize the tuple-throughput of the system). We cast the query planning problem in this environment as a ";flow maximization problem";, and present polynomial-time algorithms that (statically) find the optimal set of plans to use for a given query, for a large class of multi-way join queries. Our proposed algorithms also naturally extend to query optimization over web services. Finally we present an extensive experimental evaluation that demonstrates both the need to consider such plans in parallel query processing and the effectiveness of our algorithms.},
	keywords = {Casting, computational complexity, Cost function, Databases, Delay, distributed environment, Educational institutions, flow maximization algorithm, Interleaved codes, interoperator parallelism, minimisation, multiway join query response time minimization problem, parallel database, Parallel databases, parallel query optimization, Partitioning algorithms, pipeline processing, pipelined parallelism, polynomial-time algorithm, query planning problem, Query processing, Web service, Web services},
	isbn = {978-1-4244-1836-7},
	doi = {10.1109/ICDE.2008.4497484},
	author = {Deshpande, Amol and Hellerstein,L.}
}
@article {17870,
	title = {Active semantic caching to optimize multidimensional data analysis in parallel and distributed environments},
	journal = {Parallel Computing},
	volume = {33},
	year = {2007},
	month = {2007/08//},
	pages = {497 - 520},
	abstract = {In this paper, we present a multi-query optimization framework based on the concept of active semantic caching. The framework permits the identification and transparent reuse of data and computation in the presence of multiple queries (or query batches) that specify user-defined operators and aggregations originating from scientific data-analysis applications. We show how query scheduling techniques, coupled with intelligent cache replacement policies, can further improve the performance of query processing by leveraging the active semantic caching operators. We also propose a methodology for functionally decomposing complex queries in terms of primitives so that multiple reuse sites are exposed to the query optimizer, to increase the amount of reuse. The optimization framework and the database system implemented with it are designed to be efficient irrespective of the underlying parallel and/or distributed machine configuration. We present experimental results highlighting the performance improvements obtained by our methods using real scientific data-analysis applications on multiple parallel and distributed processing configurations (e.g., single symmetric multiprocessor (SMP) machine, cluster of SMP nodes, and a Grid computing configuration).},
	keywords = {Active semantic caching, Parallel databases, Query optimization, Scientific data analysis},
	isbn = {0167-8191},
	doi = {10.1016/j.parco.2007.03.001},
	url = {http://www.sciencedirect.com/science/article/pii/S0167819107000506},
	author = {Andrade,Henrique and Kurc,Tahsin and Sussman, Alan and Saltz,Joel}
}
