StoneDB 源码解读系列文章正式开启，预计以周更的形式跟大家见面，请多多支持~
本篇源码解读内容已进行直播分享，可在视频号观看直播回放，也可点击阅读原文跳转至 B 站观看回放视频。
PPT内容可在社区论坛中查看下载：https://forum.stonedb.io/t/topic/93
StoneDB 采用基于知识网格技术和列式存储引擎。该存储引擎为海量数据背景下 OLAP 应用而设计，通过列式存储数据、知识网格过滤、高效数据压缩等特性，为应用系统提供低成本和高性能的数据查询支持。
本文主要围绕 StoneDB 引擎的查询模块，包括：查询模块结构图、查询流程、知识网格等展开。
StoneDB 架构图
查询模块结构图
SQL模块（Query Layer）
-
SQL Parser
解析器的主要作用是解析SQL语句，最终生成语法树。解析器会对SQL语句进行语法和语义分析，如果有错误，则返回相应的错误信息。检查通过后，解析器会查询缓存，如果缓存中有对应的语句和查询结果，则直接返回结果，不进行接下来的优化和执行步骤。 -
Optimizer
优化器的主要作用是对SQL语句进行优化，包括选择合适的索引，数据的读取方式，生成代价最小的执行计划。 -
Execute
执行器的主要作用是判断操作的表是否有权限，如果有权限，会根据表的存储引擎定义，调用接口去读取数据，最后返回满足条件的查询结果。 Filter
粗糙集过滤，找到可能包含的包。
- DPN evaluation
根据DPN迭代判断包里面每条是否满足。
- decompress
分片并行解压粗糙过滤后命中的包。
知识网格模块（Knowledge Grid）
知识网格是由数据包节点和知识节点组成的。由于数据包都是压缩存放的，所以数据读取解压的代价比较高，在查询中如何做到读取尽量少的数据包是提升效率的关键。知识网格正是起到了这样的一个作用，它能够有效的过滤查询中不符合条件的数据，以最小的代价定位以数据包为最小单位的数据。知识网格的数据大小只占数据总量的1%以下，通常情况下可以加载到内存中，进一步提升查询效率。
对于大部分统计、聚合性查询，StoneDB 往往只需要使用知识网格就能返回查询结果，这是因为通过知识网格可以消除或大量减少需要解压的数据包，降低 IO 消耗，提高查询响应时间和网络利用率。例如：数据包节点记录了最大值、最小值、平均值、总和、总记录数、null 值的数量，如果想对某个列做聚合运算，那么知识网格就能根据这些元数据很快的得到结果，而无需再解压访问底层的数据包。
-
数据包节点（Data Pack Node）
数据包节点也称为元数据节点（Metadata Node），因为数据包节点记录了每个数据包中列的最大值、最小值、平均值、总和、总记录数、null 值的数量、压缩方式、占用的字节数。每一个数据包节点对应一个数据包。 -
知识节点（Knowledge Node）
数据包节点的上一层是知识节点，记录了数据包之间或者列之间关系的元数据集合，比如值数据包的最小值与最大值的范围、列之间的关联关系。大部分的知识节点数据是装载数据的时候产生的，另外一部分是查询的时候产生的。
查询流程图
查询流程大致步骤如下：
-
Client 连接
与数据库建立连接，此过程遵循 MySQL5.6、5.7 的连接协议。
-
SQL Parser
对 SQL 语句进行语法和语义分析。
解析入口：
parse_sql()
-
StoneDB Optimizer
对 SQL 语句进行优化，生成代价最小的执行计划。
优化函数：
optimize_select()
-
知识网格
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)
- 命中之后，解压相关包。
主函数：
CprsErr Decompress
- 返回结果集。
主函数：
ResultSender
知识网格
知识网络总览图
知识网格由数据元信息节点 (MD) 和知识节点 (KN) 组成， 通过知识网格，StoneDB 引擎无需通过传统数据索引、数据分区、预测、手动调优或特定架构等方式就能高速处理复杂的分析查询。
元信息节点(MD)
数据元信息节点 (MD) 与数据节点 (DN) 之间保持 1:1 关系，元信息节点中包含了其对应数据块中数据的相关信息：
- 数据聚合函数值 (MIN，MAX，SUM，AVG 等)。
- 记录数量 (count)。
- 数据中的 null 记录标记。
- 元信息节点在数据装载的时候就会构建，MD 为数据压缩， 聚合函数即席查询等技术提供了支持。
- 知识节点 (KN) 除了基础元数据外，还包括数据特征以及更深度的数据统计信息。
- 知识网格存储在内存中，方便快速查询。
数据结构：
struct DPN{}
获取DPN：
DPN &get_dpn
知识节点(KN)
Column Metadata 包含了该列的数据类型定义，约束条件等基础信息。
主类：
class impl
FieldRange 是一个标识数据节点 (DN) 中记录值范围段的标识 Map。针对数值类型的记录 (date/time， integer，decimal…)，FieldRange 可以用来快速确认当前对应 DN 是否包含所需数据。FieldRange 的组成：
从 MD 中获取数据块的 MAX 与 MIN，并将 MAX-MIN 划分为固定段(例如1024)。
每个段中分别使用1个 bit 标识是否有记录存在于该范围内。
Char Map 是一个记录字符是否匹配的 Map。针对字符类型的记录(char，varchar等)，CharMap 可以快速确定当前 DP 是否包含所需数据。
- 统计当前 DN 内，1-64 长度中 ASCII 字符是否存在的标识值。
- 字符检索时，按照字符顺序，依次对比字符标示值即可知道该 DN 是否包含匹配数据。
join nodes
- 在 Join 查询时自动创建，以关系位图的形式，存储 Join 操作中关联 DataNode 的信息。
- 存储在 Session 中，仅对当前 Client 生效。
- 显著提高Join查询性能。减少无效 DN 扫描，避免无用 IO 的产生。
distributions
- 统计当前 Column 中各记录的值分布信息。
- 基于统计信息，和粗糙集 (RoughSet) 计算，提供近似查询支持 (Approximate Query)。
以上是本文全部内容。
如果您对我们的源码感兴趣，欢迎到我们的 GitHub 代码仓库阅读查看，觉得不错记得点个 Star 哦~
StoneDB 代码仓库：https://github.com/stoneatom/stonedb
StoneDB 社区官网：https://stonedb.io/