Exploiting database parallelism in a message-passing multiprocessor

Parallel processing may well be the only means of satisfying the long-term performance requirements for database systems: an increase in throughput for transactions and a drastic decrease in response time for complex queries. In this paper, we review various alternatives, and then focus entirely on exploiting parallel-processing configurations in which general-purpose processors communicate only via message passing. In our configuration, the database is partitioned among the processors. This approach looks promising but offers challenging problems. The paper reports on our solutions to some of them: how to express strategies for efficiently executing complex queries, how to minimize overhead in operations such as parallel joins and sorts, and how to deal with transaction management in a highly distributed system. The paper ends with a discussion of the lessons we learned from exercising a prototype developed in IBM Research.