当前位置: 首页>后端>正文

StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器

StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器,第1张

StoneDB 源码解读系列文章正式开启,预计以周更的形式跟大家见面,请多多支持~
本篇源码解读内容已进行直播分享,可在视频号观看直播回放,也可点击阅读原文跳转至 B 站观看回放视频。
PPT内容可在社区论坛中查看下载:https://forum.stonedb.io/t/topic/93

StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器,第2张

StoneDB 采用基于知识网格技术和列式存储引擎。该存储引擎为海量数据背景下 OLAP 应用而设计,通过列式存储数据、知识网格过滤、高效数据压缩等特性,为应用系统提供低成本和高性能的数据查询支持。

本文主要围绕 StoneDB 引擎的查询模块,包括:查询模块结构图、查询流程、知识网格等展开。

StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器,第3张

StoneDB 架构图

StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器,第4张
StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器,第5张

查询模块结构图

StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器,第6张

SQL模块(Query Layer)

  1. SQL Parser

    解析器的主要作用是解析SQL语句,最终生成语法树。解析器会对SQL语句进行语法和语义分析,如果有错误,则返回相应的错误信息。检查通过后,解析器会查询缓存,如果缓存中有对应的语句和查询结果,则直接返回结果,不进行接下来的优化和执行步骤。
    
  2. Optimizer

    优化器的主要作用是对SQL语句进行优化,包括选择合适的索引,数据的读取方式,生成代价最小的执行计划。
    
  3. Execute

    执行器的主要作用是判断操作的表是否有权限,如果有权限,会根据表的存储引擎定义,调用接口去读取数据,最后返回满足条件的查询结果。
    
  4. Filter

粗糙集过滤,找到可能包含的包。

  1. DPN evaluation

根据DPN迭代判断包里面每条是否满足。

  1. decompress

分片并行解压粗糙过滤后命中的包。

知识网格模块(Knowledge Grid)

   知识网格是由数据包节点和知识节点组成的。由于数据包都是压缩存放的,所以数据读取解压的代价比较高,在查询中如何做到读取尽量少的数据包是提升效率的关键。知识网格正是起到了这样的一个作用,它能够有效的过滤查询中不符合条件的数据,以最小的代价定位以数据包为最小单位的数据。知识网格的数据大小只占数据总量的1%以下,通常情况下可以加载到内存中,进一步提升查询效率。

   对于大部分统计、聚合性查询,StoneDB 往往只需要使用知识网格就能返回查询结果,这是因为通过知识网格可以消除或大量减少需要解压的数据包,降低 IO 消耗,提高查询响应时间和网络利用率。例如:数据包节点记录了最大值、最小值、平均值、总和、总记录数、null 值的数量,如果想对某个列做聚合运算,那么知识网格就能根据这些元数据很快的得到结果,而无需再解压访问底层的数据包。
  1. 数据包节点(Data Pack Node)

    数据包节点也称为元数据节点(Metadata Node),因为数据包节点记录了每个数据包中列的最大值、最小值、平均值、总和、总记录数、null 值的数量、压缩方式、占用的字节数。每一个数据包节点对应一个数据包。
    
  2. 知识节点(Knowledge Node)

    数据包节点的上一层是知识节点,记录了数据包之间或者列之间关系的元数据集合,比如值数据包的最小值与最大值的范围、列之间的关联关系。大部分的知识节点数据是装载数据的时候产生的,另外一部分是查询的时候产生的。
    
StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器,第7张

查询流程图

StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器,第8张

查询流程大致步骤如下:

  1. Client 连接

    与数据库建立连接,此过程遵循 MySQL5.6、5.7 的连接协议。

  2. SQL Parser

    对 SQL 语句进行语法和语义分析。
    

解析入口:

parse_sql()
  1. StoneDB Optimizer

    对 SQL 语句进行优化,生成代价最小的执行计划。

优化函数:

optimize_select()
  1. 知识网格

    StoneDB 在执行查询的时候会根据知识网络(Knowledge Grid)把 DP 分成三类:

    • 相关的 DP(Relevant Packs),满足查询条件限制的 DP
    • 不相关的 DP(Irrelevant Packs),不满足查询条件限制的 DP
    • 可疑的 DP(Suspect Packs),DP 里面的数据部分满足查询条件的限制

入口函数:

RCAttr::ApproxAnswerSize

获取DN:

Pack *get_pack(size_t i)
  1. 命中之后,解压相关包。

主函数:

CprsErr Decompress
  1. 返回结果集。

主函数:

ResultSender
StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器,第9张

知识网格

知识网络总览图

StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器,第10张

知识网格由数据元信息节点 (MD) 和知识节点 (KN) 组成, 通过知识网格,StoneDB 引擎无需通过传统数据索引、数据分区、预测、手动调优或特定架构等方式就能高速处理复杂的分析查询。

元信息节点(MD)

StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器,第11张

数据元信息节点 (MD) 与数据节点 (DN) 之间保持 1:1 关系,元信息节点中包含了其对应数据块中数据的相关信息:

  • 数据聚合函数值 (MIN,MAX,SUM,AVG 等)。
  • 记录数量 (count)。
  • 数据中的 null 记录标记。
  • 元信息节点在数据装载的时候就会构建,MD 为数据压缩, 聚合函数即席查询等技术提供了支持。
  • 知识节点 (KN) 除了基础元数据外,还包括数据特征以及更深度的数据统计信息。
  • 知识网格存储在内存中,方便快速查询。

数据结构:

struct DPN{}

获取DPN:

DPN &get_dpn

知识节点(KN)

StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器,第12张

Column Metadata 包含了该列的数据类型定义,约束条件等基础信息。

主类:

class impl

FieldRange 是一个标识数据节点 (DN) 中记录值范围段的标识 Map。针对数值类型的记录 (date/time, integer,decimal…),FieldRange 可以用来快速确认当前对应 DN 是否包含所需数据。FieldRange 的组成:

  • 从 MD 中获取数据块的 MAX 与 MIN,并将 MAX-MIN 划分为固定段(例如1024)。

  • 每个段中分别使用1个 bit 标识是否有记录存在于该范围内。

StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器,第13张

Char Map 是一个记录字符是否匹配的 Map。针对字符类型的记录(char,varchar等),CharMap 可以快速确定当前 DP 是否包含所需数据。

  • 统计当前 DN 内,1-64 长度中 ASCII 字符是否存在的标识值。
  • 字符检索时,按照字符顺序,依次对比字符标示值即可知道该 DN 是否包含匹配数据。
StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器,第14张

join nodes

StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器,第15张
  • 在 Join 查询时自动创建,以关系位图的形式,存储 Join 操作中关联 DataNode 的信息。
  • 存储在 Session 中,仅对当前 Client 生效。
  • 显著提高Join查询性能。减少无效 DN 扫描,避免无用 IO 的产生。

distributions

  • 统计当前 Column 中各记录的值分布信息。
  • 基于统计信息,和粗糙集 (RoughSet) 计算,提供近似查询支持 (Approximate Query)。
StoneDB 源码解读系列|查询模块流程及源码介绍——StoneDB 优化器,第16张

以上是本文全部内容。

如果您对我们的源码感兴趣,欢迎到我们的 GitHub 代码仓库阅读查看,觉得不错记得点个 Star 哦~

StoneDB 代码仓库:https://github.com/stoneatom/stonedb

StoneDB 社区官网:https://stonedb.io/


https://www.xamrdz.com/backend/3ru1936891.html

相关文章: