近日，PostgreSQL 中国技术大会在杭州拉开帷幕。作为 PostgreSQL 技术畛域的年度盛会，PostgreSQL 中国技术大会曾经间断 12 年，为所有酷爱数据库技术的小伙伴们提供了一个凋谢单干、共享互助的平台。而本届大会，围绕着安全可靠、冲破、进化等主题，招集泛滥业内大咖和技术高手在这里进行技术切磋与思维碰撞。
作为国内云上数据和数据计算畛域的 Day-1 准独角兽，拓数派技术专家郭峰受邀缺席本次大会发表主题演讲。
在演讲中，郭峰介绍了 PieCloudDB Database 打造的全新优化器 ——「达奇」。「达奇」名称起源于一款深受年轻人青睐的游戏：《荒野大镖客》。游戏中一位名为「达奇」的 NPC 人物的口头禅正是「I have a plan」，和优化器的次要作用“不约而同”。
优化器是数据库系统中的一个重要组件，它“负责”对用户的查问申请进行解析、优化和执行打算的生成，使得查问后果可能以最快速度和最高效率失去返回。优化器通过生成最优的查问执行打算，来达到优化查问性能的目标。而执行打算的好坏往往会造成成千盈百的性能差别。PieCloudDB 打造的优化器「达奇」实现了大量的优化个性，作为数据库系统的“智囊团”，助 PieCloudDB 晋升性能。
四大阶段的优化个性
和 PostgreSQL 相似，PieCloudDB 查问优化的处理过程个别被分为四个阶段：预处理阶段，扫描 / 连贯优化阶段，扫描 / 连贯之外的优化阶段，后处理阶段。「达奇」在这四个解决阶段均做了大量优化。
在预处理阶段，优化器「达奇」会通过逻辑上的等价变动，将查问树转换为更加简略高效的等式。因为还未取得一些统计信息来帮忙计算代价信息，本阶段个别会通过一些被证实的规定来进行散发约束条件，简化表达式和连贯树打消无用连贯等操作。
- 把 IN, EXISTS 等类型的子查问转换为半连贯
PieCloudDB 会基于子查问所在的地位和作用的不同，将子查问分为子连贯（SubLink）和子查问（SubQuery）。子连贯因为呈现在 WHERE/ON 等约束条件中，常随同着 ANY/ALL/EXISTS 等谓语动词。如果执行器依照子连贯的形式解决，会对查问效率造成影响。且因为会产生子打算（SubPlan），优化空间无限。因而，在查问优化的预处理阶段，PieCloudDB 会尽可能地把子连贯转为 semi-join 或 anti-join，从而具备更大的优化空间。
以上面一段的 SQL 查问为 例：
SELECT … FROM foo WHERE EXISTS (SELECT 1FROM bar WHERE foo.a = bar.c);其中 EXISTS 里是一个子查问，PieCloudDB 会在预处理阶段将其变成一个 Semi-Join：
SELECT ... FROM foo *SEMI JOIN* bar ON foo.a = bar.c;- 晋升子查问
呈现在 FROM 关键字后的子句是子查问语句。如果不进行晋升优化，在对这类子查问做执行时，会先做一个独自的打算，生成一个 Sub-query scan，再与 Parent Query 做连贯，经常无奈找到最优解，造成较大的查问代价。
以上面的例子为例，如果不做任何晋升优化，会将 bar 和 baz 先做 JOIN 连贯，因为没有连贯条件，会间接将 bar 和 baz 做笛卡尔乘积，再和里面的 foo 做 JOIN 连贯：
SELECT * FROM foo JOIN (SELECT bar.c FROM bar JOIN baz ON TRUE) AS sub ON foo.a = sub.c;而做完晋升后，bar 和 baz 就在同一层面上，能够学生成 foo 和 bar 的 join，再与 baz 做 join 连贯，从而实现了代价更小：
SELECT * FROM foo JOIN (bar JOIN baz ON TRUE) ON foo.a = bar.c;- 把外连贯转换为内连贯 / 反连贯
外连贯对谓词下推以及连贯顺序搜索等都会有很多限度，因而「达奇」在预处理阶段会尽可能将外连贯转换为内连贯（Inner Join）或反连贯（Anti Join）。
在上面的 SQL 语句中，LEFT JOIN 的后果会产生一些以 NULL 结尾的 tuple，而 WHERE 条件中的等号为严格约束条件，意味着输出如果为 NULL，输入也必须是 NULL 或 FALSE。如果 bar 上的 column 为 NULL 值，则 bar.d = 42 的过滤后果为 FALSE。也就是说，LEFT JOIN 产生的以 NULL 填充的 tuple 会被 WHERE 条件过滤掉，此时，LEFT JOIN 就从语义上变为了 INNER JOIN。
SELECT ... FROM foo LEFT JOIN bar ON (...) WHERE bar.d = 42;在这样的状况下，PieCloudDB「达奇」优化器自动识别此类查问，并利用这样的优化机会，将外连贯转为内连贯。
SELECT ... FROM foo INNER JOIN bar ON (...) WHERE bar.d = 42;对于某些状况下的外连贯，PieCloudDB 优化器会在预处理阶段将外连贯转换为反连贯。以上面的 SQL 语句为例：
SELECT * FROM foo LEFT JOIN bar ON foo.a = bar.c WHERE bar.c IS NULL;同前例，LEFT JOIN 也会产生很多以 NULL 填充的 tuple 的后果集，此时 WHERE 条件限定只取 bar.c 为 NULL 的后果，此时的语义上 LEFT JOIN 就是一个反连贯。PieCloudDB 会在预处理阶段自动检测到这种优化机会，并会将外连贯转为内连贯：
SELECT * FROM foo *ANTI JOIN* bar ON foo.a = bar.c;除了这些优化，在预处理阶段，优化器「达奇」还实现了多个优化，包含：
- 散发约束条件
- 构建等价类
- 收集外连贯信息
- 打消无用连贯
- 简化表达式
等…
扫描 / 连贯优化阶段堪称是优化器处理过程中最简单的阶段。在这一阶段，优化器「达奇」会以代价驱动，解决查问语句中的 FROM 和 WHERE 局部，同时会思考到 ORDER BY 的信息。
在这一阶段，优化器「达奇」的解决次要能够分为两步。首先会为基表生成扫描门路，并计算扫描门路的代价和后果集大小，从而取得前面连贯操作的代价。第二个步骤中，「达奇」会搜寻整个连贯程序空间，为连贯操作生成最优的连贯门路。这一步骤的复杂度十分高（n！级别），PieCloudDB 采纳了动静布局和遗传算法两个算法来进行解决，并依据 GUC 值进行算法抉择。如果查问语句中波及外连贯，思考到外连贯对连贯程序的限度，无奈像内连贯那样随便切换连贯程序，会加大这一步骤的复杂度。
绝对于第二阶段，这一阶段尽管解决的事件很多，但复杂度绝对较低。在这一阶段，「达奇」会先解决 Group By、汇集、窗口函数、DISTINCT，再对汇合操作进行解决，最初再解决 ORDER BY。以上的每一步操作都会产生一个或多个门路，「达奇」会对这些门路依据代价大小进行筛选，并为筛选出的门路增加 LockRows，Limit，ModifyTable。
通过后面三个阶段，「达奇」曾经生成了一个大略的查问打算。在后处理阶段，「达奇」会把选出的最优门路转换为查问打算，并对最优打算进行一些调整。
针对分布式和云原生的优化个性
除了上述的优化个性，针对用户对于云上数据查问性能需求，PieCloudDB 优化器「达奇」对简单查问场景做了大量的优化和改良，实现了泛滥高阶的分布式与云原生个性。
在以上优化个性的根底上，「达奇」优化器拓展了泛滥针对分布式的优化个性。首先「达奇」引入了 Motion 的概念，使数据能够在不同的执行节点（Executor）之间挪动。利用 Motion，「达奇」能够产生分布式的查问打算。这些查问打算会被分为更小的单元，并被散发到不同的执行节点中并行执行。有了并行执行，很多简单查问都能进行进一步的优化，例如对于汇集操作，利用分布式的劣势，在执行节点之间能够通过多阶段汇集来晋升性能。
以这段查问为例来解说一下多阶段汇集，针对这段 SQL 查问，「达奇」会生成这样的查问打算：
因为存在一个去重的操作，「达奇」会进行三个阶段的汇集，在第一个阶段，PieCloudDB 会在每个执行节点上，以 a，b 为 group key 先做一个部分的汇集，这里就实现了一个部分去重的操作。接着，利用 Motion 做一次 Reshuffle 的操作，此时再进行一次汇集操作，实现全局去重。最初再依据 group key 实现最初的汇集操作，失去查问后果。
因为 PieCloudDB 的存储引擎「简墨」采纳的是对象存储的设计，联合这一设计，PieCloudDB 优化器「达奇」实现了更多高阶的优化，包含汇集下推、Block Skipping、预计算等。这里将对汇集下推进行介绍，对于「达奇」的其余云原生个性，欢送关注行将陆续推出的其余内容。
PieCloudDB 实现了汇集下推（Aggregate Pushdown），能够在查问执行打算中无效地缩小数据的传输和解决，进步查问效率。在剖析型场景中，SUM、AVG、MAX、MIN 等汇集操作是常见的操作，能够用来对数据库表中的数据进行聚合计算。大部分数据仓库在解决汇集操作时，通常须要先实现对表的扫描和连贯操作，之后再计算聚合函数。在数据量十分大的 状况下，这样的查问性能会比拟低。
而 PieCloudDB 优化器「达奇」实现的汇集下推优化策略，通过把汇集操作下推到连贯操作之前去执行，能够极大地缩小连贯操作须要解决的数据量，经测试，在某些状况下，性能会失去成百甚至上千倍的晋升。
以上面的 SQL 查问为例，这段查问须要对 t1 表和 t2 表进行连贯操作，在此基础上，依据 t1.a 做分组，来取得 t2.c 的平均值。在不进行汇集下推优化的状况下 ，会先实现 t1 和 t2 的连贯操作，再按 t1.a 的分组进行汇集操作。此时，如果 t1 和 t2 表都很大的话，进行连贯操作的代价很高， 会对性能产生肯定影响 。而在 进行汇集下推的优化下 ，会在连贯之前先做汇集操作，此时如果 t2.b 十分有汇集性，数据量会减小很多，此时再进行连贯操作， 性能会大幅提高。
查问优化器是数据库系统最重要、也是最简单的组件之一。PieCloudDB 作为一款云原生虚构数仓，将一直对优化器「达奇」进行打磨，在确保数据库系统的高效和稳固运行的前提下，一直驱动性能的晋升。
3 月 14 日，基于新一代云原生数仓虚拟化打造的 PieCloudDB「云上云」版已正式公布，欢送大家登录 www.openpie.com 收费试用。