Optimization of Distributed Queries: A Survey
Dr. Emad Abuelrub,
Department of Computer Science
Zarka Private University
Jordan
Email: abuelrub@zpu.edu.jo
Tel: +962-5-382-1100 / ext 1400
Fax: +962-5-3821117


The future of large database systems lies into the realm of distributed computing. The main reason for this is that distributed computing can be constructed at low cost without the need for any specialized technology, using existing sequential computer and relatively cheap computer networks. The great commercial success of database systems is partly due to the development of sophisticated query optimization technologies, where users pose queries in a declarative way using SQL or OQL and the optimizer of the database system finds a good way (i.e., plan) to execute these queries. The optimizer, for example, determines which indices should be used to execute a query and in which order the operations of a query (e.g., joins, selects, and projects) should be executed. To this end, the optimizer enumerates alternative plans, estimates the cost of every plan using a cost model, and chooses the plan with lowest cost. Selecting the optimal execution strategy for a query is NP-hard in the number of relations. For complex queries with many relations, this incurs a prohibitive optimization cost. Therefore, the actual objective of the optimizer is to find a strategy close to optimal and to avoid bad strategies. The selection of the optimal strategy generally requires the prediction of execution cost of the alternative candidate ordering prior to actually executing the query. The execution cost is expressed as a weighted combination of I/O, CPU, and communication costs.

In this talk, we will discuss some of the ways in which queries can be optimized for distributed environments. First, the problem of query processing and optimization is briefly discussed. Different kinds of search spaces and search strategies are evaluated showing the advantages and disadvantages of each strategy. Second, cost models are discussed. Finally, the talk concludes with results and highlights some future directions.


Speaker Biography

Emad Abuelrub is an associate professor and the dean of the Faculty of Science and Information Technology at Zarqa Private University, Jordan. He received his Bachelor degrees in computer engineering and computer science from Oklahoma State University, USA, in 1984 and 1985, respectively. He then joined the Alabama A&M University, USA, where he obtained his MSc degree in computer science in 1987. He completed his PhD degree in computer science from Louisiana State University, USA, in 1993. His areas of interest include parallel and distributed systems, interconnection networks, fault-tolerance computing, parallel algorithms, and parallel architectures. He is a member of the IEEE, ACM, and JEA.

 

Home Top