On resource scheduling of multi-join queries in parallel database systems (Q1313743)

This paper presents a two-phase approach to optimizing multi-join queries. Phase 1 produces an operator tree that reflects the join ordering and methods for a query without considering runtime resources. Phase 2 comprises two steps: 1) the operator tree is decomposed into a set of tasks, each of which is a set of joins that can be executed in a pipelined fashion, 2) the tasks are scheduled for execution. We study three scheduling algorithms. While algorithm MaxShelf processes the tasks serially, algorithm MinShelf exploits inter-task prallelism totally. However, it is algorithm FlexiShelf, a hybrid of the two extremes, that performs best.