【作者】 陈婷；

【导师】 张蓉；

【作者基本信息】 华东师范大学 ， 电子信息（专业学位）， 2023， 硕士

【摘要】 多表连接查询是分析型数据库中常见的负载。连接顺序选择问题,即从候选连接顺序集合中选出性能最优的连接顺序,是多表连接查询性能优化的关键问题。然而,查询处理的高效性要求与连接顺序的庞大搜索空间以及不同连接形状的优化复杂度之间存在矛盾,导致连接顺序选择成为难点问题。尽管目前存在许多连接顺序选择策略,如动态规划方法、启发式方法和基于学习的方法,但是现有的评测基准、评测工具和真实应用负载都不适用于评估各种连接顺序选择策略对于不同连接形状的优化效果,因为它们存在数据缺乏多样倾斜度和数据关联以及负载缺乏随机可控的连接数目、多样的连接形状和谓词等不足。为了提供一个通用的能够有效评估连接顺序选择策略的方法,本文设计并实现了面向复杂连接的连接顺序选择策略评测方法。具体来说,本文基于确定性数据生成机制设计了支持数据倾斜和数据关联的数据生成方法,定义了支持不同连接形状的连接模板生成算法和通用的复杂连接参数实例化算法,最终设计并实现了一款用于评估连接顺序选择策略优劣的工具。本文的主要贡献归纳如下:1.基于确定性数据生成机制,生成具有数据倾斜和数据关联的大规模数据,为连接顺序选择策略评测提供具有真实应用特征的测试场景,同时支持数据高效扩展和低代价迁移。2.定义了适用于不同连接形状的连接模板生成算法,支持例如链式、星型、树型、集团型等多种连接形状并且支持随机可控的连接数目,能够在低时间复杂度的基础上生成大量满足语法正确性和语义正确性的多表连接查询。3.设计了通用的参数实例化方法,支持在各种复杂连接条件下的参数实例化,能够实现基于数学运算符和逻辑运算符的复杂谓词,并确保最终生成的多表连接查询有效。4.搭建了一个自动化的连接顺序选择策略评测工具,能够适配各种常见的数据库管理系统,可服务于评测查询优化器的连接顺序选择优劣。综上所述,本文主要研究对查询优化中的复杂连接顺序选择评估的技术,设计了基于确定性规则的测试场景生成方法,探讨评测连接顺序选择策略的优劣问题。本文在集中式数据库Postgre SQL、My SQL和分布式数据库Ocean Base、Ti DB中进行连接顺序选择效果的评估实验,得到充分的实验结果,展示了方案的有效性。更多还原

【Abstract】 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.更多还原