Benchmarking Join Order Selection For Complex Joins

Multi-table join queries are common in online analytical processing databases.The Join Order Selection problem,also known as the Join Order Optimization problem,is one of the most critical tasks in handling multi-table join queries.It aims to choose the cheapest join order from the available alternatives.However,the enormous search space of join orders and the complexity of optimizing queries with different join shapes make it difficult to find an optimal join order in an efficient way.Although there are many optimization algorithms for Join Order Selection,existing benchmarks,evaluation tools and real-world application workloads are not suitable for evaluating these join order selection strategies,because they cannot configure the number of joins or cover all join shapes.In order to provide a generic method that can effectively evaluate join order selection strategies,this dissertation designs and implements an evaluation method for Join Order Selection.This dissertation designs a data generation method that supports data skew and data correlations based on deterministic data generation mechanisms.Besides,this dissertation defines a join template generation algorithm that supports different join shapes and a generic parameter instantiation algorithm for generating test scenarios.Finally,this dissertation designs and implements a tool for evaluating join order selection strategies.The main contributions of this dissertation are as follows:1.Generate large-scale data with data skew and data correlation by a deterministic data generation method.The method enables data scaling and data migration with minimal storage costs.2.Propose a shape-oriented join template generation method,which is able to generate queries with different join shapes and arbitrary number of joins.The method can generate a large number of queries which satisfy syntactic and semantic correctness at low time complexity.3.Design a generic parameter instantiation algorithm to support parameter instantiation under a variety of complex join conditions.The algorithm is able to generate a rich variety of predicates and to ensure that multi-table join queries are valid.4.Implement an automated tool for evaluating join order selection strategies,which can be adapted to a variety of common database management systems and used to evaluate the quality of Join Order Selection in query optimizers.In summary,this dissertation investigates the problem of evaluating complex Join Order Selection in query optimization,and designs a deterministic rule-based test scenario generation method.This dissertation apply the tool on Ocean Base,Ti DB,Postgre SQL and My SQL,the experiments show that it is effective to evaluate the performance of Join Order Selection in query optimizers.