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_18: This paper extends earlier research on hash-join algorithms to a multiprocessor architecture. Implementations of a number of centralized join algorithms are described and measured. Evaluation of these algorithms served to verify earlier analylical results. In addition, they demonstrate that bit vector filtering provides dramatic improvement in the performance of all algorithms including the sort mergejoin algorithm. Multiprocessor configurations of the centralized Grace and Hybrid hash-join algorithms are also presented. Both algorithms arc shown to provide linear increases in throughput with corresponding increases in processor and disk resources.
@cite_22: This chapter describes how statements in the SQL language are processed by the R* distributed relational database management system. R* is an experimental adaptation of System R to the distributed environment. The R* prototype is currently operational on multiple machines running the MVS operating system, and is undergoing evaluation. The R* system is a confederation of autonomous, locally-administered databases that may be geographically dispersed, yet which appear to the user as a single database. Naming conventions permit R* to access tables at remote sites without resorting to a centralized or replicated catalog, and without the user having to specify either the current location of or the communication commands required to access that table. SQL data definition statements affecting remote sites are interpreted through a distributed recursive call mechanism. Tables may be moved physically to other databases without affecting existing SQL statements. SQL data manipulation statements are compiled at each site having a table referenced in the statement, coordinated by the site at which the statement originated. As part of compilation, the distributed optimization process chooses the best place and the best way to access tables and join them together. Optimization uses dynamic programming and careful pruning to minimize total estimated execution cost at all sites, which is a linear combination of CPU, I O, and communications (both per-message and per-byte) costs.
@cite_54: The authors deal with two major issues to exploit inter-operator parallelism within a multijoin query: join sequence scheduling and processor allocation. For the first issue, they propose and evaluate by simulation several methods to determine the general join sequences, or the bush execution trees. Despite their simplicity, the proposed heuristics can lead to the general join sequences which significantly outperform the optimal sequential join sequence. In addition, several heuristics to determine the processor allocation, categorized by bottom-up and top-down approaches, were derived and evaluated by simulation. As confirmed by the simulation, by first using the join sequence heuristics to build a busy tree and then applying the concept of synchronous execution time to the busy tree for processor allocation, an efficient two-step approach to schedule and execute multijoin queries in a multiprocessor system can be obtained. >
@cite_9: Big data analytics often requires processing complex queries using massive parallelism, where the main performance metrics is the communication cost incurred during data reshuffling. In this paper, we describe a system that can compute efficiently complex join queries, including queries with cyclic joins, on a massively parallel architecture. We build on two independent lines of work for multi-join query evaluation: a communication-optimal algorithm for distributed evaluation, and a worst-case optimal algorithm for sequential evaluation. We evaluate these algorithms together, then describe novel, practical optimizations for both algorithms.
@cite_43: The authors describe their approach to the optimization of query execution plans in XPRS, a multi-user parallel database machine based on a shared-memory multi-processor and a disk array. The main difficulties in this optimization problem are the compile-time unknown parameters such as available buffer size and number of free processors, and the enormous search space of possible parallel plans. The authors deal with these problems with a novel two phase optimization strategy which dramatically reduces the search space and allows run time parameters without significantly compromising plan optimality. They present their two phase strategy and give experimental evidence from XPRS benchmarks that indicate that it almost always produces optimal plans. >
Prior research has extensively studied parallel and distributed query optimization techniques. R* was an early research prototype that optimized queries to minimize data transfer costs in a shared-nothing environment @cite_22 . @cite_54 proposed to generate parallel query plans in two phases: first generate the optimal query plan for a single node, and then to parallelize it for a multi-processor environment. Hong and Stonebraker @cite_43 showed that two phase optimization produces good query plans for shared-memory systems. Researchers have also studied parallel hash join algorithms. DeWitt and Gerber @cite_18 introduced multi-processor versions of popular hash join algorithms for a single join and evaluated their advantages and disadvantages in a multi-processor environment. Recently, @cite_9 propose a novel distributed multi-way join algorithm that has been theoretically proven to have better performance than evaluating the multi-way join as a series of binary joins.