Research On Key Techniques Of Parallel Multiple Query Processing

This dissertation addresses the techniques of multiple query processing in parallel database systems, and proposed a self-adaptive multi-phase parallel multi-query processing method called MP~2. It can overcome the disadvantages in the traditional methods of multi-query processing.In this dissertation, methods to decide the property of a common operator (CO for short) are proposed and proved. Two kinds of extracting approach, strong factoring and weak factoring, are described formally, and the correctness and equivalencesufficiency and necessity that weak or strong common operator belongs to fat, thin, normal or equivalent CO is proved, also. The costs of exploiting weak CO or strong CO with different properties under different conditions are analyzed and compared. According to this, a complete set of rules for deciding what extracting approach is appropriate for different cases is put forward, which provide a theoretic base for extracting CO.In this dissertation, a heuristic parallel coloring algorithm for extracting common subplan (CSP for short) for two queries is brought forward. It prunes the search space and fastens the search process by coloring and assembling the sharing nodes found. It can provide fine granularity of sharing and efficiently avoid the interference of the order of the multi-join operations. Also, to a large extent, it avoids the interference of the order of the multiple set operations as well as extracting approaches. Based on this, a parallel multi-group appended merge algorithm extracting CSP for more queries is proposed.In this dissertation, three methods for distributing operator trees are given so that they can be optimized in parallel. Cost-based optimization for multi-query operator forest can reuse the information coming from single-query optimization. Three methods for computing the total cost of a multi-plan for a query are also presented.The multi-dependency among the multi-query tasks complicates the multi-query scheduler. A heuristic approach for partitioning each subplan into tasks is...