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

StoneDB 源码解读系列文章正式开启，预计以周更的形式跟大家见面，请多多支持~

本篇源码解读内容已进行直播分享，可在视频号观看直播回放，也可点击阅读原文跳转至 B 站观看回放视频。

PPT 内容可在社区论坛中查看下载：https://forum.stonedb.io/t/topic/93

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

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

StoneDB 架构图

查询模块结构图

SQL 模块（Query Layer）

a. SQL Parser

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

b. Optimizer

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

c. Execute

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

d. Filter

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

e. DPN evaluation

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

f. Decompress

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

知识网格模块（Knowledge Grid）

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

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

a. 数据包节点（Data Pack Node）

数据包节点也称为元数据节点（Metadata Node），因为数据包节点记录了每个数据包中列的最大值、最小值、平均值、总和、总记录数、null 值的数量、压缩方式、占用的字节数。每一个数据包节点对应一个数据包。

b. 知识节点（Knowledge Node）

数据包节点的上一层是知识节点，记录了数据包之间或者列之间关系的元数据集合，比如值数据包的最小值与最大值的范围、列之间的关联关系。大部分的知识节点数据是装载数据的时候产生的，另外一部分是查询的时候产生的。

查询流程图

查询流程大致步骤如下：

1. Client 连接

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

2. SQL Parser

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

解析入口：

parse_sql()

3. StoneDB Optimizer

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

优化函数：

optimize_select()

4. 知识网格

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)

5. 命中之后，解压相关包。

主函数：

CprsErr Decompress

6. 返回结果集。

主函数：

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/

磨刀不误砍柴工，数据压缩，带来的可不止空间节省 | StoneDB数据库观察

为什么 MySQL 使用 B+ 树？| StoneDB数据库观察

主流开源分析引擎梳理，看看你最中意谁？| StoneDB数据库观察

带你来吃瓜！Andy Pavlo教授带您一文回顾数据库的2022年

2023 年十大战略技术趋势中哪一项最需要 HTAP ？

存算一体 VS 存算分离 ，IT发展下的技术迭代

数据库独角兽SingleStore：没有HTAP，机器学习和人工智能都是不切实际的

前Oracle技术部门总监：面向场景，HTAP到底是刚需还是炒作？