Compile-Time Inter-Query Dependence Analysis

Most parallel databases exploit two types of parallelism: intra-query parallelism and inter-transaction concurrency. Between these two cases lies another type of parallelism: inter-query parallelism within a transaction or application. Exploiting inter-query parallelism requires either compiler support to automatically parallelize the existing embedded query programs, or programming support to write explicitly parallel query programs. In this paper, we present compiler analysis to automatically detect parallelism in the embedded query programs. We present compiler dependence test algorithms for detecting both internal and external dependences. We show that the properties of some special functions such as MIN and MAX can help reduce dependences. Finally, we discuss the potential use of dependences to improve the performance of embedded query application programs