随着信息技术在教育领域的高速推进和深入应用，每时每刻都有大量且种类繁多的教育数据产生。如何能够在大规模数据库中及时获取有效且准确的信息，成为数据库管理技术研究的一个重要方向。面对这种数据和访问同时增长带来的沉重负载，很多基于单处理器和单计算机平台的传统数据库系统的处理能力已经显得捉襟见肘，这使得数据库的响应速度越来越慢，查询方式越来越复杂，而且对其持续稳定运行也带来了不利影响。本书在吸收国内外相关研究成果和实践经验的基础上，选择典型算法进行分析，对教育数据库查询过程中涉及的查询计划构建模型、查询计划执行策略以及数据操作算法三个主要方面展开研究，全面系统阐述了高性能数据库查询优化算法的相关理论，对查询优化算法的相关问题进行了论述。

“三通两平台”建设和应用深化，产生了大量数据，我们称为教育大数据。教育大数据包括学习过程之中师生方面的行为记录、学生学习结果的综合评定数据以及师生学习行为构成的学习关系型网络等。随着数据量的增大，传统数据库系统的处理能力已满足不了现在需求，如何能够准确有效地获取复杂的信息，提高数据库查询处理能力，成为当下急需解决的问题。片上多核处理器提升了片上计算能力和存储空间，提高了片上通信的速度和带宽，为高性能并行计算的应用提供了基础设施，���成本和功耗也为其普及提供了条件，片上多核处理器已成为未来较长一段时间内的发展趋势。多核处理器的这场硬件的革命自然也带动了软件的革命，大量的软件设计人员将多核处理器作为并行化程序设计的实现平台，多核平台与并行计算理论相结合，以多线程并行的方式提升应用程序的性能。



随着信息技术在教育领域的高速推进和深入应用，每时每刻都有大量且种类繁多的教育数据产生。如何能够在大规模数据库中及时获取有效且准确的信息，成为数据库管理技术研究的一个重要方向。鉴于此，笔者在参阅大量相关文献和经验总结的基础上，撰写了《CMP环境下教育数据库高性能查询优化算法的研究》一书。基于多核平台，研究利用并行计算技术，实现教育数据的高性能查询，是本书的研究目标。本书从传统的问题入手，选择典型算法进行分析，对教育数据库查询过程中涉及的查询计划构建模型、查询计划执行策略以及数据操作算法三个主要方面展开研究。



本书共由四个章节组成。**章主要对高性能数据库查询优化算法的研究背景、研究现状和研究意义等做了系统阐述，以便读者对高性能数据库查询优化的应用研究有一个基本认识。第二章对查询计划的构建进行了优化，提出了基于逻辑转换优化的自底向上连接枚举并行算法和基于逻辑转换优化的自顶向下连接枚举并行算法。通过连接子集对优化构建算法实现**的连接子集对构建，并对其合理性进行了证明。依托构建的有效连接子集对集合，对基于多核的自底向上连接枚举并行算法进行了研究，避免了线程执行的连接子集与其他线程运行的连接子集之间的依赖关系，实现了*优查询计划的并行构建。通过构建谓词扩展相称表，提出了可以支持多种连接的基于逻辑转换优化的自顶向下连接枚举并行算法。第三章对查询计划的构建进行了优化，提出基于查询子图相似性优化的查询计划构建算法。为了缓解搜索空间对于动态规划枚举算法的限制，通过基于查询子图相似性优化的查询计划构建算法，减少了构建的局部*优查询计划的数量，避免大量逻辑表达式的构建，一定程度上减少搜索空间。第四章首先提出基于多核硬件体系结构的查询计划并行执行框架，并给出了该框架相关的执行算法，然后以连接算法为**，提出基于基值多路分解的并行哈希连接算法。针对如何实现查询计划的多线程执行，获得*大的资源利用率，本书依据查询计划的执行粒度，提出了两个层次的新型优化方法，即*优查询计划的执行策略和操作算法的执行策略。这些执行策略在一定程度上避免了查询计划在执行过程中Cache访问缺失以及Cache访问冲突的发生，提高了查询计划的执行性能。



本书在吸收国内外相关研究成果和实践经验的基础上，阐述了高性能数据库查询优化算法的相关理论，全面系统地对查询优化算法的相关问题进行了论述。在本书的撰写过程中，笔者参考、借鉴了国内外相关文献资料，也得到了亲朋的支持，特此致以衷心的感谢。但由于时间紧迫和笔者水平有限，书中难免存在不足，希望同行和广大读者批评指正。





著者



2023年1月

**章绪论1 **节研究背景与问题提出/1 第二节多核体系架构及比较/2 一、多核体系架构/2 二、多核硬件体系结构与超线程技术的对比/3 三、多核与单核平台上多线程技术对比/4 第三节主要研究内容及现状/5 一、多核体系架构的发展/5 二、基于多核的数据库查询优化算法的研究/6 第四节本书主要内容/8 第二章查询计划的动态规划枚举构建算法11 **节引言/11 第二节自底向上枚举优化算法的研究/13 一、自底向上动态规划枚举算法/13 二、连接子集对优化构建算法的研究/15 三、连接子集对构架算法合理性证明/20 四、基于多核的自底向上连接枚举并行算法/25 第三节自顶向下枚举优化算法研究/33 一、自顶向下动态规划枚举算法/33 二、支持非内连接的自顶向下枚举算法/36 三、基于逻辑转换优化的并行自顶向下枚举算法/40 第四节算法性能评估/44 第五节本章总结/46 第三章查询计划的非枚举构建算法48 **节引言/48 第二节遗传算法/50 一、迭代改进算法/50 二、模拟退火算法/51 三、两阶段优化算法/51 第三节迭代动态规划算法/52 第四节基于查询图相似性的查询计划构建算法/53 一、相似查询子图集的DP算法/56 二、相似查询子图集的构建/58 三、相似子图查询计划的构建/63 第五节相似查询子图集构建算法的优化/65 一、优选相似种子对/65 二、优选相似子图集/67 三、基于相似查询子图集的IDP算法/68 第六节相似查询子图集的构建算法性能分析/70 第七节本章总结/72 第四章多核环境下查询计划的执行策略74 **节引言/74 第二节关系数据库系统固有并行性/76 第三节查询计划并行执行算法/78 一、数据流执行策略树/78 二、并行数据流执行策略图/81 三、工作量及缓冲区计算/86 四、并行执行策略的优化/89 第四节多核环境下Hash连接并行算法/90 一、常用连接操作并行算法/92 二、基于基值分解的并行哈希连接实现框架/92 三、基于基值分解的并行哈希连接实现算法/98 四、负载均衡优化/101 第五节多线程并行算法性能分析/106 第六节本章小结/108 参考文献109 后记112