《面向分布式数据库的连接查询优化》文献阅读笔记

《面向分布式数据库的连接查询优化》文献阅读笔记，包含分布式数据库概述、基于分布式存储的数据库系统架构详解、分布式数据库连接查询优化框架。

中心主题

• 分布式数据库概述
  • 分布式数据库特性
    • 数据分布式存储：数据通过切分策略，分散存储于数据库集群中的各个节点
    • 计算与存储分离：计算节点与存储节点分别部署在不同的服务器上，便于各自的扩展
    • 节点之间通过网路进行数据的交互
  • 查询优化器
    • 搜索空间：查询请求的可选执行计划的集合
    • 代价模型
      • 包括
        • 代价函数
        • 数据统计信息
        • 中间结果集预估工具
      • 执行代价的主要衡量标准
        • 查询的执行时间
    • 搜索策略
  • 连接算法与半连接操作
    • 连接算法
      • 查询优化器的职责就是判断采用哪种算法，提升查询效率
      • 嵌套循环连接(NestLoop-Join)
        • 优缺点
          • 优点
            • 当数据量庞大时可以通过避免对数据进行排序来减少响应时间
          • 缺点
            • 由于两表每条记录之间都要进行判断是否符合连接条件，则数据规模越大，占用服务器的计算资源越多
        • 适用场景
          • 1.驱动表的数据规模不能太大或者是过滤后的结果集非常小
          • 2.被连接表中的连接条件列应该是主键或者有索引
      • 哈希连接(Hash-Join)
        • 三个阶段
          • 分区阶段
          • 索引表构建阶段
          • 探查阶段
        • 优缺点
          • 优点
            • 当连接状态的两张表中缺少可用的索引时，其性能优于其他连接算法，哈希连接通过扫描全表然后通过内存中的哈希表来进行匹配，避免了嵌套循环连接中大量随机读的问题
          • 缺点
            • 只能用于等值连接
            • CPU资源消耗比较严重
        • 适用于等值连接查询
        • 使用前提
          • 连接中的两张表缺少可用的索引
          • 当前数据库系统负载不高
      • 排序归并连接(Merge-Join)
        • 排序方法
          • 两阶段多路归并排序算法
          • 内排算法
        • 制约其效率的因素
          • 内排算法的性能
          • 两张表在连接属性上的重复值数量
        • 优缺点
          • 优点
            • 对每张表都只扫描一次，减少了磁盘I/O时间开销
          • 缺点
            • 需要对两张表进行排序，当数据量增加时，算法的效率会显著下降
    • 半连接操作
      • 优点
        • 减少数据的网络传输，降低查询的响应时间
• 基于分布式存储的数据库系统架构详解
  • 影响连接查询效率的主要因素
    • 本地的数据提取：将数据从服务器本地磁盘加载到内存，发送给计算节点
      • 并行度
    • 数据的网络传输：查询处理节点对远程数据存储节点发出网络请求，数据到达查询处理节点的速度直接影响最终的响应时间
      • 半连接操作
    • 连接算法的执行效率：当查询处理节点请求的数据到位后，将采用不同的连接算法对两张表的结果集进行连接运算
      • 连接算子
        • 哈希连接
        • 嵌套循环连接
        • 排序归并连接
  • 系统架构
  • OceanBase系统架构
    • 客户端
    • RootServer(RS)
    • UpdataServer(UPS)
    • 存储引擎ChunkServer(CS)
    • 查询处理引擎MergeServer(MS)
• 分布式数据库连接查询优化框架
  • 连接查询优化策略
    • 面向分布式存储架构的查询优化过程
      • 与通用查询优化过程的不同点：
      • 过程包括
        • 查询试行
        • 优化策略
        • 统计信息
          • 表的行数
          • 表的数据块数
          • 索引字段的行数不同值的个数
          • 服务器的CPU核心数
      • 特点
        • 只产生一个确定的查询计划动态调整
        • 连接方式：内连接
          • 原因：内连接中表的连接顺序可以任意的改变，可以使用结果集较小的表来过滤数据量较大的表
        • 查询计划树形：左深树
          • 优点：优化过程不需要考虑连接操作的顺序对优化效果的影响
          • 缺点：可能在最初选择了不能产生最优查询计划的树形
        • 进行优化前明确规定了连接执行的顺序
    • 具体的优化策略
      • 优化方向
        • 并行度
          • 优点
            • 使数据的请求与处理并行执行，提升数据的本地提取速度
            • 加快连接算法的执行效率，降低了连接查询的响应时间
        • 连接算子
          • 为哈希连接、嵌套循环连接、排序归并连接等连接算法的物理实现
        • 半连接操作
  • 三方面
    • 并发度
    • 连接算子
    • 半连接操作
  • 分布式数据连接查询优化框架
    • 主要模块详细设计方案
      • 优化策略模块
        •  
      • 连接算子并行任务模块
        •  
      • 半连接操作并行任务模块
        •  
      • 连接计算模块
        •  
• 连接算子与半连接操作的并行实现
  • 哈希连接与嵌套循环连接的并行实现
    • 哈希连接的并行实现设计
      • 
      • 设计方案包括
        • 连接算子并行任务模块
          • 根据连接算子操作符分发的任务，分配相应数量的任务线程来进行任务的处理并返回数据
        • 连接算子操作符
          • 负责任务的分发与结果的整合，最后将结果返回客户端
        • 优化策略模块
          • 负责判断使用哪种连接算子
      • 并行体现
        • 对R表与S表进行并行的分区处理
        • 对每一对分区<R1,S1>并行的构建哈希表，并行的进行数据的探测，并行的返回中间结果
    • 循环嵌套连接的实现流程
      • 
  • 并行的半连接操作
    • 半连接操作整体的执行流程
      • 
      • 半连接操作符
        • 负责任务的分发，结果的汇总
      • 连接算子操作符
        • 负责向半连接操作符索取数据
      • 半连接并行任务模块
        • 提高具体执行的任务线程
      • 优化策略模块
        • 给出是否使用半连接的优化建议
    • 任务线程的处理流程
      • 
    • 数据过滤方式
      • IN表达式
        • 
        • 执行流程
        • 优缺点
          • 优点：可以定位到具体的Data Block，不需要将所有的数据都扫描进内存
          • 缺点：当需要过滤数据变很多时，定位到的Data Block会有大量的重复，导致磁盘I/O的开销比全表扫描的I/O开销还要大
        • 适用场景
          • IN表达式适合过滤较少的数据，当数据量增多时可以采取并行过滤的方式，将过滤数据拆分成多个IN表达式并行的对右表数据进行过滤
      • Between表达式
        • 
        • 过滤方式
          • 对指定范围内的数据进行扫描，即按初始DataBlock与结束DataBlock顺序的扫描进内存（Between表达式中的最大值与最小值）
        • 优缺点
          • 优点
            • 顺序地将一定范围内的数据快速加载进内存当中，并且可以有效的控制磁盘I/O
          • 缺点
            • 左表的连接属性列只有几个数值，右表却有上万数值的情况下会有大量的无用数据被传回MergeServer，造成数据网络传输开销的增加
        • 适用场景
          • 适用于左表连接属性列的数据较多，并且右表连接属性列的值相对分散的情况，避免将大量无用的数据加载进内存
• 实验分析
  • 实验软硬件环境与实验数据设置
    • 系统软件环境
      • 1台主控节点：RootServer(RS)与UpdataServer(UPS)
        • 负责集群的管控与事务处理
      • 3台数据存储节点：ChunkServer(CS)
        • 负责存储实验数据
      • 1台查询处理引擎：MergeServer(MS)
        • 负责查询请求处理
    • 系统硬件环境
    • 实验数据设置
  • 实验验证连接查询框架的可行性与效率
    • 不同的数据过滤方式对响应时间的影响
    • 连接算子的执行效率
    • 半连接对查询效率的影响
    • 综合性能测试
• 总结与展望
  • 本文研究内容
  • 未来工作
    • 将研究如何在外连接的情况下，针对不同树形，在优化策略中增加响应的处理流程，动态的对连接查询进行优化
    • 资源的合理利用，既能保证单次查询的响应时间，又能相应的提高系统整体的并发度