关于数据库:StoneDB-join-算法分析查询模块

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。