PERF solutions for distributed query optimization. (c1999)

Abstract

The advent of telecommunication era and the constant development of hardware and network structures have encouraged the decentralization of data while increasing the needs to access information from different sites. Query optimization strategies aim to minimize the cost of transferring data across networks. This is achieved gradually by reducing the number of tuples transmitted from one site to another until it reaches the destination site. Many techniques and algorithms have been proposed to optimize queries. Perhaps one of the more important algorithms is the AHY algorithm that is implemented by Apers, Hevner and Yao in 1983 [5]. This algorithm consisted of three phases: - Local processing to filter unnecessary information. - Semi-join reduction that involves shipment of data from one site to another to be reduced. - Final assembly at the destination site. But somehow their approach suffered from several problems due to the redundancy of the semi-joins. Nowadays, a new technique called PERF (Partially Encoded Record Filters), presented by Kenneth Ross in 1995 seems to bring some improvement over semi-joins [7]. PERF joins are two-way semi-joins using a bit vectors as their backward phase. Upon performing a semi-join between two sites, data is sent from site A to site B, and then a bit vector representing the matching tuples is sent back to site A. Whenever such a semi-join is needed again, data will not be resent from site A to site B but the bit vector is used, hence reducing the cost on the network. Our research encompasses applying PERF joins to the AHY and the W algorithms, which both deal with query optimization. Programs were designed to implement both the original and the enhanced algorithms. Several experiments were conducted and the results showed a very considerable enhancement obtained by applying PERF concept to both algorithms. This major improvement leads us to further observation and studies.