Infobright 查询优化

May 28, 2014

友情提示：如果你只想迅速了解本文中给出的优化建议，请直接翻到最后面，不过我还是希望你可以看看前面的内容。

为了更好的理解和写出适合 Infobright 的 SQL 语句，在本文中我会首先介绍 Infobright 的结构， 然后再解释 SQL 语句是如何执行的，最后给出一些优化建议。当然，我不想把本文写的枯燥、难读， 所以我会尽量使用例子和示例图说明。让我们先从一般性的介绍开始 …

简介

Infobright 是一个列式存储的数据库，和其对应的是行式存储的数据库，如图所示。简要列一下它们的主要使用场景：

image

  • 列式存储用于：1）只有个别列涉及的海量应用；2）统计报表（sum、count etc）
  • 行式存储用于：1）所有列都涉及的应用；2）需要事务处理的应用。

Infobright 比较突出的优点是查询效率高，以及压缩比高（通常10 : 1），下面的章节就是来解释 Infobright 是怎么办到的。

整体结构

如下图所示，这是 Infobright 整体结构图，看起来略显复杂，不过在本文中我们只需要关注三个部分。 它们分别是：

  • Data Pack：存放数据。
  • Knowledge Grid：存放关于数据的统计信息。
  • The Granular Computing Engine：根据数据统计信息，进行查询优化。

下面我们依次来看这三个部分。

image

Data Pack

我们首先来看位于最底层的 Data Pack（后面简称 DP 或者 Pack），前面说过 Infobright 是按列存储的，它在存储每一列时，会把连续的 65536 个 item 分为一组，这样的每一组就称为一个 Data Pack。

例如，现在有一个表 T，它有两个列 A 和 B，并有 300000 行记录，那么 Infobright 将会有类似下面这样的 Packs：

image

这些 Packs 都是压缩存储的，整体结构图中的 Compressor/Decompressor 就是来做这事的，由于 Infobright 对每一个 Pack 都进行了数据类型相关的压缩，因此压缩比很高。压缩比和 Load 时的顺序以及数据类型有关，这里不详细写了，大家有兴趣的话，可以看看阿稳的一些优化经验 – 再次优化完成一个infobright表 和 infobright的bigint型与varchar型效率对比 。

Knowledge Grid

Infobright 的 Knowledge Grid（后面简称 KG）由 Data Pack Nodes（DPN）和 Knowledge Nodes（KN）组成。

Data Pack Nodes（DPN）

DPN 主要记录了每一个 DP 的简单统计信息。例如，对于数值类型的列而言，DPN 中包括了：min value，max value，sum，num of non-null elements 和 count 这些信息。每一个 DP 都有一个相应的 DPN。

还是以上文中的例子来说，假设表 T 中的列 A、B 都是数值类型的，为了简单，我们假设表中没有空值，而且在下面的表中不给出 num of non-null elements 和 count 的值了。

+---------------+-----+-----+--------+-----+-----+------+
| Packs Numbers |      DPNs of A     |    DPNs of B     |
+               +-----+-----+--------+-----+-----+------+
| Columns A & B | Min | Max |    SUM | Min | Max |  SUM |
+===============+=====+=====+========+=====+=====+======+
| Packs A1 & B1 |   0 |   5 |  10000 |   0 |   5 | 1000 |
+---------------+-----+-----+--------+-----+-----+------+
| Packs A2 & B2 |   0 |   2 |   2055 |   0 |   2 |  100 |
+---------------+-----+-----+--------+-----+-----+------+
| Packs A3 & B3 |   7 |   8 | 500000 |   0 |   1 |  100 |
+---------------+-----+-----+--------+-----+-----+------+
| Packs A4 & B4 |   0 |   5 |  30000 |   0 |   5 |  100 |
+---------------+-----+-----+--------+-----+-----+------+
| Packs A5 & B5 |  -4 |  10 |     12 | -15 |   0 |  -40 |
+---------------+-----+-----+--------+-----+-----+------+

当执行查询时 Infobright 首先会检查 DPN 中的信息，以确定要不要解压相应的 DP（后面有例子来展示）。虽然存放在 DPN 的信息比较简单，但这已经足够优化大多数简单的查询了。

Knowledge Nodes（KN）

为了优化复杂的查询（JOIN，SUB-QUERY等），Infobright 需要更多的统计信息，这正是 KN 所要做的。 KN 主要分为3个类，分别是 HIST、CMAP、Pack-To-Pack。简单来说，HIST 是针对数值类型的统计信息，CMAP 是针对字符类型的统计信息，Pack-To-Pack 是表与表之间，列与列之间的统计信息。

HIST（histogram）

DPN 中记录了 MIN，MAX 这样简单的统计信息，比如一个 DPN 的 MIN 和 MAX 是 100 和 10000，那么我们此时可以确定 10001 和 9 肯定不在该 DP 中，但是对于 500 我们就不确定了，如果只有 DPN 的话，现在就需要解压该 DP 了。HIST 的目的其实很简单，就是提供更具体的统计信息，以减少解压相应 DP 的机会。 HIST 把 MIN ~ MAX 区间细分为 1024 个小区间，然后统计每个小区间是否有数据。假设上面提到的 DP 有如下的 HIST 记录，那我们现在就可以确定 500 也不在该 DP，所以就不需要解压这个 DP 了。

+---------+---------+-----+---------+-----+
| 100~109 | 110~109 | ... | 496~505 | ... |
+---------+---------+-----+---------+-----+
|       0 |       1 | ... |       0 | ... |
+---------+---------+-----+---------+-----+
CMAP （Character Map）

CMAP 是针对字符类型数据的统计信息，它统计了 1~64 位置处 ascii 字符的出现情况。

+-----+---+---+-----+----+
|     | 1 | 2 | ... | 64 |
+-----+---+---+-----+----+
|   A | 1 | 0 | ... |  0 |
+-----+---+---+-----+----+
|   B | 0 | 0 | ... |  1 |
+-----+---+---+-----+----+
| ... |   |   |     |    |
+-----+---+---+-----+----+
Pack-To-Pack

Pack-To-Pack 产生在涉及多个表的查询的时候（如 JOIN 查询），它提供了一些关于表的链接信息，利用 Pack-To-Pack，可以有效减少需要查看的 DP 数目，由于 Pack-To-Pack 产生于查询时刻（那 DPN、HIST、CMP 产生在什么时候？好问题，它们都产生于 Load 时刻），这里就不画图了，在后面看具体查询的执行时，再配图。

小结一下

KN 可以类比于传统数据库中的 INDEX，但是它不需要人工去建立，而是由系统自动生成的，其中 HIST、CMAP、DPN 生成于 load 数据的时候，Pack-To-Pack （我已经不想再写这么长的词了，后面我直接用 P2P 了）生成于查询的时候。

The Granular Computing Engine

好了，枯燥的定义终于完了（其实还有 3 个，不过我想用例子引出来，不想单列在这里了），现在我们来看看 DP、DPN、KN 是如何一起协作，来实现高效率的查询。

尽量减少需要解压的 DP。

这就是 Infobright 优化的本质，本质往往是简单，细节是复杂的、会把人搞晕的，所以在看后面的细节之前，请大家记住这点，这有助于后面的理解。

下面是一些具体的查询语句，我们还是以之前的表 T 为例。

Query 1：SELECT SUM(B) FROM T WHERE A > 6

+---------------+-----+-----+--------+-----+-----+------+
| Packs Numbers |      DPNs of A     |    DPNs of B     |
+               +-----+-----+--------+-----+-----+------+
| Columns A & B | Min | Max |    SUM | Min | Max |  SUM |
+===============+=====+=====+========+=====+=====+======+
| Packs A1 & B1 |   0 |   5 |  10000 |   0 |   5 | 1000 |
+---------------+-----+-----+--------+-----+-----+------+
| Packs A2 & B2 |   0 |   2 |   2055 |   0 |   2 |  100 |
+---------------+-----+-----+--------+-----+-----+------+
| Packs A3 & B3 |   7 |   8 | 500000 |   0 |   1 |  100 |
+---------------+-----+-----+--------+-----+-----+------+
| Packs A4 & B4 |   0 |   5 |  30000 |   0 |   5 |  100 |
+---------------+-----+-----+--------+-----+-----+------+
| Packs A5 & B5 |  -4 |  10 |     12 | -15 |   0 |  -40 |
+---------------+-----+-----+--------+-----+-----+------+

可以看到，DP A1、A2、A4 中不可能有满足条件 A > 6 的行，因为这些 DP 的最大值都小于6，我们称这种 DP 是 不相关的（Irrelevant） ，因此 DP B1、B2、B4 在计算 SUM(B) 就不用分析了，因为它们也是不相关的。

另外，我们也可以看到 DP A3 的所有行（131073 ~ 196608）都是 相关的（Relevant） ，因为它们都满足 A > 6。 这也意味着 DP B3 是相关的，DP B3 的 SUM 就是最终结果的一部分，此时 B3 的 DPN 中统计出了 B3 中所有数据的和（100），这个就是 Infobright 此时关于 DP B3 需要知道的全部信息了， 所以我们不需要解压 DP B3，并查看其具体内容了。

DP A5 是 可疑的（Suspect） ，因为我们只能知道有一些行满足 A > 6，但是不能确定具体的行。 因此 Infobright 需要解压 A5 和 B5，查看 262145 ~ 300000 行中哪些满足 A > 6，并且对相应的 B 进行求和。把该值和前面 B3 中得到的值加起来，就是我们最终的答案了。

可疑的 DP 会随着查询的执行而变为不相关的，例如下面的查询。

Query 2: SELECT MAX(B) FROM T WHERE A > 6

从 DP B3 的 DPN 中我们知道，B 在 131073 ~ 196608 行的最大值为 1，所以我们知道满足 A > 6 的行中至少有一个 B 的值为 1。 然后，从 DP B5 的 DPN 中可知，B 在行 262145 ~ 300000 的最大值为 0，比 1 小，所以此时 DP A5、B5 从可疑变成了不相关， Infobright 也不需要再去解压 A5、B5，而直接返回 1 作为最终答案。

下面我们来看一个用到 P2P 的例子。

Query3: SELECT MAX(X.D) FROM T JOIN X ON T.B = X.C WHERE T.A > 6

其中表 X 有 C、D 两个列，包含了 150000 行，并且每个列有 3 个 DP。它的 DPN 如下图所示 （和表 T 的表示方式一样，我们假设没有空值）。

+---------------+-----+-----+-----+-----+-----+-----+
| Packs Numbers |   DPNs of C     |   DPNs of D     |
+               +-----+-----+-----+-----+-----+-----+
| Columns C & D | Min | Max | SUM | Min | Max | SUM |
+===============+=====+=====+=====+=====+=====+=====+
| Packs C1 & D1 |  -1 |   5 | 100 |   0 |   5 | 100 |
+---------------+-----+-----+-----+-----+-----+-----+
| Packs C2 & D2 |  -2 |   2 | 100 |   0 |  33 | 100 |
+---------------+-----+-----+-----+-----+-----+-----+
| Packs C3 & D3 |  -7 |   8 |   1 |   0 |   8 | 100 |
+---------------+-----+-----+-----+-----+-----+-----+

从前面的分析可知，表 T 中需要关注的 DP 有 A3、A5、B3、B5（满足 T.A > 6）。 现在假设我们已经有了如下关于 T.B 和 X.C 的 P2P 可用（可能产出于之前的某次 JOIN 查询）。

+------+------+------+------+------+------+
|      | T.B1 | T.B2 | T.B3 | T.B4 | T.B5 |
+------+------+------+------+------+------+
| X.C1 |    0 |    1 |    0 |    1 |    0 |
+------+------+------+------+------+------+
| X.C2 |    1 |    0 |    0 |    0 |    1 |
+------+------+------+------+------+------+
| X.C3 |    1 |    1 |    0 |    1 |    0 |
+------+------+------+------+------+------+

其中，T.B1 指的是表 T 的 DP B1，X.C1 指的是表 X 的 DP C1，其他类似， 从中可以看出 T.B1 和 X.C1 没有相同的值（由数值 0 表明），同时也可以看出 T.B1 和 X.C2 至少有一个相同的值（由数值 1 表明）。

根据上面的 P2P 给我们提供的信息，我们可以把 B3 从我们的关注列表中删除， 因为它不可能和表 X 的任何一行匹配。现在就只剩下 B5 了，同时我们也可以看到 B5 只可能和 C2 匹配。

从目前所知道的信息中，我们已经可以确定 MAX(X.D) 值不会超过 33 （结合 DP D2）。 但是我们还不能确定具体的值，因为我们不知道 B5 和 C2 具体有哪些匹配的行，以及 A5 哪些行的值大于6。因此为了获得最终的答案， 我们需要首先解压这 3 个 DP，以确定具体是哪些行满足所有的条件，然后解压 D2 获得相应行的最大值。

查询优化建议

Infobright 优化是需要在不同层次上进行的（如配置、数据类型，查询语句等）， 在本文中只是简单列出官方文档中的几条建议（其他方面留到后续文章中详细介绍， 这篇文章已经稍长了）。

  1. 尽量有序导入数据。因为 Infobright 每一列会分成多个 DP，并在 DPN 中记录 DP 的统计信息，如果有序导入则可以使相邻数据差异变小，利于压缩和查询优化。例如，时间 date 按顺序导入的话，那么前一个 DP 的 max(date) <= 下一 DP 的 min(date)，查询时就可以减少可疑 DP，提高查询性能。
  2. SELECT 中尽量使用 WHERE 中出现的字段，WHERE 中的条件也尽量多些。因为 Infobright 可以根据 DPN 优化，从而减少需要查看的 DP。（避免 select * from …）
  3. 尽量避免使用 OR，如果可能应该使用 IN 作为替代。
  4. 临时表（Temp Tables）可以作为查询的中间结果。
  5. 尽量使用独立的子查询和 JOIN 操作代替非独立的子查询。P2P 可以帮助优化 JOIN 操作。

尽量避免以下操作：

  1. Creating JOINs with the JOIN condition defined as NOT BETWEEN（不好翻译，直接贴过来）。
  2. 使用跨越 Infobright 表和 MySQL 表的查询操作。
  3. UPDATE 和 DELETE 操作，因为该操作会破坏知识网格（KG），降低查询性能。

这里添加一些我们 IB 中出现的一些有问题的查询（后面会单独有一篇专门记录 IB 中的错误示例， 当然，我们会尽量抽象出来，避免个人信息）。

  1. 多次执行 “select … from … where user_key = xxx” 这样的 sql，每次变化的只是 user_key 的具体值。建议做法是把 user_key 收集成一个列表，然后用 “select … from … where user_key in (…)” 的方式。

最后

感谢你花时间读到这里，如果你有所收获，我会觉得“这辈子值了”。

写这篇文章的过程中我参考了以下资料：

  1. Infobright 白皮书（大多翻译的白皮书中的内容，稍加了些自己的理解）。
  2. Brighthouse: an analytic data warehouse for ad-hoc queries 论文。
  3. 一些网络资料。