1. 背景介绍

StoneDB 采纳基于常识网格技术和列式存储引擎。该存储引擎为海量数据背景下 OLAP 利用而设计，通过列式存储数据、常识网格过滤、高效数据压缩等个性，为利用零碎提供低成本和高性能的数据查问反对。
本文旨在剖析 StoneDB 引擎的查问模块，包含：查问模块结构图、查问流程、常识网格、常识网格优化、优化算法。

2. StoneDB架构图

3. 查问模块结构图

SQL模块（Query Layer）

1.SQL Parser

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

2.Optimizer

优化器的次要作用是对SQL语句进行优化，包含抉择适合的索引，数据的读取形式，生成代价最小的执行打算。

3.Execute

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

4.Filter

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

5.DPN evaluation

依据DPN迭代判断包外面每条是否满足。

6.decompress

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

常识网格模块（Knowledge Grid）

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

对于大部分统计、聚合性查问，StoneDB 往往只须要应用常识网格就能返回查问后果，这是因为通过常识网格能够打消或大量缩小须要解压的数据包，升高 IO 耗费，进步查问响应工夫和网络利用率。例如：数据包节点记录了最大值、最小值、平均值、总和、总记录数、null 值的数量，如果想对某个列做聚合运算，那么常识网格就能依据这些元数据很快的失去后果，而无需再解压拜访底层的数据包。

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

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

2.常识节点（Knowledge Node）

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

4. 查问流程图


查问流程大抵步骤如下：

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

5. 常识网格

5.1 常识网络总览图

     常识网格由数据元信息节点 (MD) 和常识节点 (KN) 组成， 通过常识网格，StoneDB 引擎无需通过传统数据索引、数据分区、预测、手动调优或特定架构等形式就能高速解决简单的剖析查问。

5.2 元信息节点(MD)


数据元信息节点 (MD) 与数据节点 (DN) 之间放弃 1:1 关系，元信息节点中蕴含了其对应数据块中数据的相干信息：

  • 数据聚合函数值 (MIN，MAX，SUM，AVG 等)。
  • 记录数量 (count)。
  • 数据中的 null 记录标记。
  • 元信息节点在数据装载的时候就会构建，MD 为数据压缩， 聚合函数即席查问等技术提供了反对。
  • 常识节点 (KN) 除了根底元数据外，还包含数据特色以及更深度的数据统信息。
  • 常识网格存储在内存中，不便疾速查问。

数据结构：

struct DPN{}

获取DPN：

DPN &get_dpn

5.3 常识节点(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)。

6 常识网格优化器

对于来自客户端的申请，首先由查问优化器进行基于常识网格的优化，产生执行打算后再交给执行引擎去解决。
下图为执行流程：

  • 基于常识网格中的信息进行粗燥集(Rough Set)构建， 并确定此次申请所需应用到的数据节点。

    • 基于 KN 和 MD ，确定查问波及到的 DN 节点汇合，并将 DN 节点归类:

      • 关联 DN 节点:满足查问条件限度的数据节点(间接读取并返回)
      • 不确定性 DN 节点: 数据节点中局部数据满足查问条件(解压后进行解决再返回).
      • 非关联 DN 节点: 与查问条件齐全不相干(间接疏忽).

    • 执行打算构建时， 会齐全躲避非关联 DN， 仅读取并解压关联 DN， 依照特定状况决定是否读取不确定的 DN。

      • 例子： 对于一个查问申请， 通过KG能够确定 3 个关联性 DN 和 1 个不确定性 DN。如果此申请蕴含聚合函数。此时只须要解压不确定性 DN 并计算聚合值，再联合3个关联性 DN 中 MD上的统计值即可得出后果。如果此申请须要返回具体数据， 那么无论关联性 DN 还是不确定性 DN，都须要读取数据块并解压缩，以取得后果集。
  • 如果查问申请的后果能够间接从元信息节点 (MD) 中产生(例如 count， max， min 等操作)，则间接返回元信息节点中的数据，无需拜访物理数据文件.

  • 查问案例1：SELECT count(*) FROM students where score < 550。

    • 通过 KG 常识，查找蕴含 score < 550 的数据节点（DN），此处能够看到只有 A/B/C 三个节点波及到该查问。
    • 数据节点 A 与 B 属于关联 DN 节点， 只需间接从对应的 MD 节点中获取 count 值即可。
    • 数据节点 C 属于不确定性 DN 节点，须要读取数据块并解压， 执行函数计算后能力返回后果集。
    • 这里只有数据块C会被读取并解压，数据节点 A 与 B 并不耗费 IO 资源。

7. 优化算法

7.1 Comment Lookup

Comment Lookup 只能显式地应用在 char 或者 varchar 下面。Comment Lookup能够缩小存储空间，进步压缩率，对 char 和 varchar 字段采纳 comment lookup 能够进步查问效率。
Comment Lookup 实现机制很像位图索引，实现上利用简短的数值类型代替char字段已获得更好的查问性能和压缩比率。Comment Lookup 的应用除了对数据类型有要求，对数据也有肯定的要求。个别要求数据类别的总数小于10000并且当前列的单元数量/类别数量大于10。Comment Lookup 比拟适宜年龄，性别，省份这一类型的字段。
Comment Lookup 应用很简略，在创立数据库表的时候如下定义即可：

act char(15) comment 'lookup',part char(4) comment 'lookup',

7.2 join算法

StoneDB 反对 NESTED LOOP JOIN，SORT MERGE JOIN，HASH JOIN和MAP JOIN 算法。

StoneDB 通过 EvaluateConditionJoinWeight 评估 join 权重，依据 UpdateJoinCondition 扭转 join 条件，ChooseJoinAlgorithm 抉择join算法。

7.2.1 NESTED LOOP JOIN

对于被连贯的数据子集较小的状况，嵌套循环连贯是个较好的抉择。在嵌套循环中，内表被表面驱动，表面返回的每一行都要在内表中检索找到与它匹配的行，因而整个查问返回的后果集不能太大（大于1 万不适宜），要把返回子集较小表的作为表面，CBO 默认表面是驱动表 （CBO：基于老本优化），而且在内表的连贯字段上肯定要有索引。通过 JoinerGeneral::ExecuteOuterJoinLoop 函数进入 NESTED LOOP JOIN 计算。

7.2.2 SORT MERGE JOIN

通常状况下散列连贯的成果都比排序合并连贯要好，然而如果行源曾经被排过序，在执行排序合并连贯时不须要再排序了，这时排序合并连贯的性能会优于散列连贯。

Sort Merge join 用在没有索引，并且数据曾经排序的状况。函数 JoinerSort::ExecuteJoinConditions 进入算法，Join关联过程遵循小表扫描 MarkUsedDims(dims1)，大表匹配 MarkUsedDims(dims2)。

7.2 HASH JOIN

散列连贯是 CBO 做大数据集连贯时的罕用形式，优化器应用两个表中较小的表（或数据源）利用连贯键在内存中建设散列表，而后扫描较大的表并探测散列表，找出与散列表匹配的行。
这种形式实用于较小的表齐全能够放于内存中的状况，这样总成本就是拜访两个表的老本之和。然而在表很大的状况下并不能齐全放入内存，这时优化器会将它宰割成若干不同的分区，不能放入内存的局部就把该分区写入磁盘的长期段，此时要有较大的长期段从而尽量进步 I/O 的性能。通过函数 JoinerHash::ExecuteJoinConditions 进入 JoinerHash::ExecuteJoin 执行 HASH JOIN 算法，如果 ini_join_parallel>0，调用ProxyHashJoiner/ParallelHashJoiner 并行执行。

7.2.4 MAP JOIN

Map join 实用于一个大表和一个或多个小表执行 join 操作的场景。整个join过程蕴含 map、shuffle 和reduce 三个阶段。通常状况下，join 操作在 reduce 阶段执行表连贯。map join 操作是在 map 阶段执行的，大量缩短了数据传输的工夫，晋升了系统资源的利用率，从而起到了优化作业的作用，并且 map join 会将指定的小表全副加载到执行 join 操作的程序的内存中，从而放慢 join 的速度。

通过 JoinerMapped::ExecuteJoinConditions 进入MAP JOIN算法，依据 JoinerMapped::GenerateFunction 生产map函数，调用 map_function 的 Init 执行 map join。