Database management systems (DBMSs) carefully optimize complex multi-join queries to avoid expensive disk I O. As servers today feature tens or hundreds of gigabytes of RAM, a significant fraction of many analytic databases becomes memory-resident. Even after careful tuning for an in-memory environment, a linear disk I O model such as the one implemented in PostgreSQL may make query response time predictions that are up to 2× slower than the optimal multi-join query plan over memory-resident data. This paper introduces a memory I O cost model to identify good evaluation strategies for complex query plans with multiple hash-based equi-joins over memory-resident data. The proposed cost model is carefully validated for accuracy using three different systems, including an Amazon EC2 instance, to control for hardware-specific differences. Prior work in parallel query evaluation has advocated right-deep and bushy trees for multi-join queries due to their greater parallelization and pipelining potential. A surprising finding is that the conventional wisdom from shared-nothing disk-based systems does not directly apply to the modern shared-everything memory hierarchy. As corroborated by our model, the performance gap between the optimal left-deep and right-deep query plan can grow to about 10× as the number of joins in the query increases.
@cite_42: In this paper we examine the problem of processing multi-way join queries (on the order of 10 joins) through hash-based join methods in a shared-nothing database machine. We first discuss how the choice of a format for a complex query can significantly affect performance in a multiprocessor database machine. Several query processing algorithms are then proposed and experimental results obtained from a simulation study are presented to demonstrate the tradeoffs of left-deep and right-deep scheduling strategies for complex join query evaluation. These results demonstrate that right-deep scheduling strategies can provi& significant performance advantages in large multiprocessor database machines under many circumstances, even when memory is limited.
The performance of different multi-join evaluation strategies has also been extensively studied. Schneider and DeWitt @cite_42 studied multi-way join query processing through hash-based methods in the Gamma parallel database system. They observed that trees with shallow hash-join build phases and a long probe pipeline ( right-deep'' trees) can provide significant performance advantages in large multiprocessor database machines. The key advantages of right-deep query trees are the ample parallelization potential, as each build subtree can be executed concurrently, and that no intermediate results need to be materialized in the long probe pipeline because results are streamed from one operator to the next.