Join Processing in a Symmetric Parallel Environment (Classic Reprint)

Excerpt from Join Processing in a Symmetric Parallel Environment We present and analyze a strategy for procuring joins on a highly parallel computer architecture. We model the architecture as consisting of n identical processor-meraory clusters interconnected by a symmetric network onto which many processors may send at once. The strategy entails partitioning each relation horizontally based on a perfect hashing function applied to a key of the relation. The basic join algorithm consists of projecting each relation on the joining and result columns and then sending each truncated tuple to the jth processor if the hash function applied to the join columns of the tuple yields j. Processor j then performs a local join, producing the result. We consider three variations on the basic algorithm lot the case where the join columns of at least one relation do not include a key (so there will be duplicate values): combining, tagging, and smearing. Combining is a network operation, whereby network switches filter out some of the duplicate data destined for the same processor. As one might expect, this helps when there are many duplicates. Tagging changes the basic algorithm by having the originating processor project on the join columns only (not the result columns) on one of the relations, then send each truncated tuple to some desnnation processor. The destination processor sends this tuple back if it determines that the tuple's join column values are matched by some tuple in the other relation. We show that this improves performance when there arc far fewer distinct join column values than join and result column values. Smearing changes the bask algorithm by copying the tuples of one processor, say i, to several neighboring processors for, say relation S, in order to allow tuples from the other relation, say R, that would normally hash to i to hash to any of the neighbors of i. Our analysis depends on the properties of a particular interconnection scheme (the omega network),'our approach may be more generally applicable. 2. Related Work Our work is related to research in four areas: distributed query processing, especially (CH82, GS82]; semi-jotn-baied processing, particularly [BC81, B79); database machines, particularly (B79, KTM84); and parallel algorithms [BDFW83, V83]. General query optimization strategies for complex queries [GoodShmu82, JK84, Schm79] will be relevant to later stages of our work. Because we assume a network whose speed is comparable to local memory access time and we assume that this network can be shared, our cost assumptions differ from those made in much of the research on distributed query processing. (Our assumptions are based on the environment to be provided by the New York University ultracomputer.) Moreover, our design is based on partinoning relations across all processors In contrast, most distributed query processing research is concerned with minimizing the volume of communicated data in the absence of partitioning [BGWRR81, F.S80, HY78. HY79, WY76). Chu and Hurley [CH82J search for conditions that optimize both communication and processing costs About the Publisher Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to pre