Optimizing Equijoin Queries in Distributed Databases Where Relations are Hash Partitioned

Dennis Shasha, Tsong Li Wang

Research output: Contribution to journalArticlepeer-review


Consider the class of distributed database systems consisting of a set of nodes connected by a high bandwidth network. Each node consists of a processor, a random access memory, and a slower but much larger memory such as a disk. There is no shared memory among the nodes. The data are horizontally partitioned often using a hash function. Such a description characterizes many parallel or distributed database systems that have recently been proposed, both commercial and academic. We study the optimization problem that arises when the query processor must repartition the relations and intermediate results participating in a multijoin query. Using estimates of the sizes of intermediate relations, we show 1991 optimum solutions for closed chain queries; (2) the NP-completeness of the optimization problem for star, tree, and general graph queries; and (3) effective heuristics for these hard cases. Our general approach and many of our results extend to other attribute partitioning schemes, for example, sort-partitioning on attributes, and to partitioned object databases.

Original languageEnglish (US)
Pages (from-to)279-308
Number of pages30
JournalACM Transactions on Database Systems (TODS)
Issue number2
StatePublished - Jan 5 1991


  • NP-complete problems
  • equijoin
  • hashing
  • relational data models
  • spanning trees
  • systems

ASJC Scopus subject areas

  • Information Systems


Dive into the research topics of 'Optimizing Equijoin Queries in Distributed Databases Where Relations are Hash Partitioned'. Together they form a unique fingerprint.

Cite this