理解查询计划（Query Plan）
本文档介绍了查询计划的基础构成与阅读方式，并分别给出单机查询计划与并行查询计划的示例及说明。
1 什么是查询计划？
查询计划（又称执行计划或查询执行计划）是一次完整的查询流程中的重要一环。它由优化器选择并生成，是对一条 SQL 语句在数据库中执行过程的详细描述。
集中式数据库（如 PostgreSQL 等单机数据库）中，数据库节点实例拥有全部的数据，查询的过程也全部发生在同一台机器上，生成并执行单机查询计划即可满足查询需求。
而在分布式数据库（如 Greenplum、YMatrix）中，数据是分布在多个节点上的，需要用户在建表的时候就指定分布策略以及分布键，数据将会按分布策略和分布键分布在多个 Segment 节点实例上，每个 Segment 节点实例只拥有一部分数据。
因此，原有的单机查询计划已无法实现完整的查询，必须重新实现并行查询计划（或称为分布式查询计划），在数据分布的基础上确定如何高效地实现计算的并行化以及如何让计算更加贴近数据，即尽可能的在 Segment 节点实例上进行计算，避免在 Master 上进行计算，从而保证提供最好的查询性能。
2 查询计划如何生成？
在 YMatrix 中，表导入数据库完成后，需要首先使用 ANALYZE 命令采集统计信息。定期执行全库的 ANALYZE 也是有必要的。因为只有正确采集了统计信息，优化器才可准确地选择查询计划，从而提高查询处理的速度。
正确采集了统计信息后，可通过 EXPALIN 命令查看优化器针对指定 SQL 生成的不同的逻辑查询计划。查询优化器通常会生成多个可能的查询计划，然后选择最优的计划来执行查询。通过分析和理解查询计划，可以帮助开发人员和数据库管理员（DBA）优化查询性能并识别潜在的瓶颈。
3 查询计划由什么组成?
查询计划的结构是一种树结构，它由多个计划节点组成，每个节点代表一个查询操作，如扫描表、连接、聚集等，并将结果传递给父节点进行进一步处理。
查询计划中的每个节点都包含了其执行的详细信息，例如执行顺序、访问方式、并发度和预估成本等。查询计划树始于叶子节点，结束于根节点，可以通过遍历整个树来确定查询在数据库中的查询计划。
分布式查询计划中，最常见的计划节点类型及其运算方法（算子）如下：
| 计划节点类型 | 操作说明 | 标量化算子 | 向量化算子 |
|---|---|---|---|
| 扫描计划节点 | 负责扫描数据库中的表或索引 | SeqScan：顺序扫描表中的所有行 IndexScan：遍历一个索引以从表中取得行 BitmapHeapScan & BitmapIndexScan：两者常搭配使用。位图索引扫描对索引本身进行扫描并生成一个位图（索引规模会影响生成的位图粒度），随后位图堆扫描会根据位图索引扫描生成的位图对数据表进行扫描。 注意：索引扫描每次只从索引表中读取一条索引项，随即转向数据表判断其是否满足索引条件，需要不断交替访问索引表和数据表，适合精确的定位；位图扫描则不同，其明确地分为两个阶段。首先一次性从索引表中将满足条件的索引项全部取出，在内存中进行排序，然后根据取出的索引项访问数据表，适合大面积的定位 DynamicSeqScan：使用一个分区选择函数来选择分区 ParallelSeq：如启用并行，通常令并行查询的数量与 CPU 核心数量相等，以获最高的效率 |
MxVScan：MARS2/MARS3/AOCO 表中通过向量化执行引擎完成的顺序扫描操作 |
| 连接计划节点 | 负责将两个或多个表连接起来 | HashJoin：从较小的表构建一个哈希表，用连接列作为哈希键。然后扫描较大的表，为连接列计算哈希键并且探索哈希表寻找具有相同哈希键的行。HashCond 显示要被连接的列 NestedLoopJoin：在较大数据集的行上迭代，在每次迭代时从较小的数据集中扫描行。嵌套循环连接要求广播其中的一个表，这样一个表中的所有行才能与其他表中的所有行进行比较。不过，如果分布键与连接键相同，则本地进行嵌套循环连接即可，无需广播 MergeJoin：排序两个数据集并且将它们合并起来 |
MxVHashJoin：MARS2/MARS3/AOCO 表中通过向量化执行引擎完成的哈希连接操作 |
| 其他计划节点 | Materialize：能够缓存子查询执行结果到缓存中，即第一次被执行时生成的结果元组缓存，等待上层节点使用 Sort：对底层节点返回的元组进行排序 Group：对下层排序元组进行分组操作 Agg：执行聚集函数 Unique：执行去重操作 Hash：执行哈希运算，为 HashJoin 的辅助节点 Limit：处理 LIMIT/OFFSET 子句WindowAgg：处理窗口函数 LockRows：锁定所有选定行，可分别根据 FOR SHARE/FOR UPDATE 子句选择行SetOP：对多个数据集进行操作和组合，包括并集（ UNION）、交集（INTERSECT）和差集（EXCEPT/MINUS）等SubqueryScan：计算任何子查询 Append：将多个结果集合并为一个 Result：处理仅需一次计算的条件表达式或仅包含一个 VALUES 子句的 INSERT ... VALUES 语句GroupAgg：首先对数据按照聚集列进行排序，使聚集列相等的元组均相邻，再重新遍历排序后的数据，即可完成元组的去重和聚集函数的计算 HashAgg：无需排序，通过构建数据的哈希表对其进行分组聚集 Broadcast Motion：每一个 Segment 将自己的数据行发送给所有其他 Segment，使得每一个 Segment 节点实例都有一份完整的表数据本地拷贝 Redistribute Motion：每一个 Segment 根据重分布键重新计算数据，并且将其发送到对应的 Segment Gather Motion：来自所有 Segment 的结果数据被组装成一个单一的流。对大部分查询计划来说这是最后的操作 |
MxVMotion：MARS2/MARS3/AOCO 表中通过向量化执行引擎实现 Gather Motion MxVSort：MARS2/MARS3/AOCO 表中通过向量化执行引擎完成的排序操作 MxVResult：MARS2/MARS3/AOCO 表中通过向量化执行引擎完成的 Result 操作 MxVSubqueryScan：MARS2/MARS3/AOCO 表中通过向量化执行引擎完成的子查询扫描操作 MxVLimit：MARS2/MARS3/AOCO 表中通过向量化执行引擎完成的 Limit 操作 MxVHashAgg：MARS2/MARS3/AOCO 表中通过向量化执行引擎完成的 HashAgg 操作 MxVGroupAgg：MARS2/MARS3/AOCO 表中通过向量化执行引擎完成的 GroupAgg 操作 MxVAppend：MARS2/MARS3/AOCO 表中通过向量化执行引擎完成的 Append 操作 |
以上节点可以根据查询需要组合在一起，形成一个完整的查询计划。
4 查询计划如何阅读
查询计划由于其嵌套树结构，需要由下而上阅读。
在此分别给出一个单机查询计划和一个并行查询计划示例说明。
4.1 单机查询计划
首先创建两个表。（示例表在单机数据库 PostgreSQL 9.2 中创建）
=# CREATE TABLE sale (
cid int,
pid int,
pnum int,
qty float,
date timestamp
);=# CREATE TABLE customer (
cid int,
cname text,
cwechat text
);分别插入一些测试数据。
=# INSERT INTO sale (cid, pid, pnum, qty, date) VALUES
(1, 1, 1, 10.0, '2023-07-20 08:37:06'),
(2, 3, 6, 35.0, '2023-07-15 18:22:00'),
(3, 2, 1, 3.0, '2023-07-17 11:37:00'),
(4, 1, 2, 10.0, '2023-07-20 10:37:09'),
(5, 3, 2, 35.0, '2023-07-17 08:12:06'),
(6, 1, 1, 10.0, '2023-07-02 12:10:23'),
(7, 3, 1, 35.0, '2023-07-07 08:07:00'),
(8, 5, 3, 99.0, '2023-07-20 10:37:06'),
(9, 3, 1, 35.0, '2023-07-20 15:30:00'),
(10, 3, 1, 35.0, '2023-07-20 09:00:00');=# INSERT INTO customer (cid, cname, cwechat) VALUES
(1, 'kepler', 'kepler1997'),
(2, 'amiee', 'amiee1995'),
(3, 'lila', 'lila2002'),
(4, 'cici', 'cici1982'),
(5, 'damien', 'damien1983'),
(6, 'ariana', 'ariana1990'),
(7, 'kanye', 'kanye1960'),
(8, 'taylor', 'taylor1996'),
(9, 'michael', 'mike2005'),
(10, 'ray', 'ray1957');现在，我们想要连接 sale 和 customer 表共有的 cid 键来计算出每个顾客的销售额总数，同时分析此查询的查询计划。
在生成查询计划前需要首先采集其统计信息。
=# ANALYZE sale;
=# ANALYZE customer;生成查询计划。
=# EXPLAIN SELECT c.cname, sum(s.pnum * s.qty) AS amount FROM sale s, customer c WHERE s.cid = c.cid GROUP BY c.cname;
QUERY PLAN
------------------------------------------------------------------------------
HashAggregate (cost=2.56..2.66 rows=10 width=14)
Group Key: c.cname
-> Hash Join (cost=1.23..2.46 rows=10 width=18)
Hash Cond: (s.cid = c.cid)
-> Seq Scan on sale s (cost=0.00..1.10 rows=10 width=16)
-> Hash (cost=1.10..1.10 rows=10 width=10)
-> Seq Scan on customer c (cost=0.00..1.10 rows=10 width=10)
(7 rows)该查询计划有 2 个主要节点：Hash Join 和 HashAggregate。每一个节点包含三个代价估值：cost、 行数（rows）、以及行宽度（width），这几个估值可以帮助我们提前对该 SQL 的执行时间、结果集规模及数据传输和处理的复杂性有所了解。
此查询计划树结构图如下：
阅读一份查询计划需要理解它的嵌套结构。每个节点为一个子动作，数据计算与流动的操作顺序从下至上。可以看到，优化器首先规划了一个扫描操作，对 customer 表的扫描共产生 1.10 的代价值。扫描完毕重新构建了一张 Hash 表存储到内存中，同时对 sale 表进行扫描并进行 Hash 计算，然后以 cid 字段作为连接键与 Hash 表中的数据进行对比，到这一步启动代价和总代价分别为 1.23 和 2.46。最后将所有数据按照 cname 字段通过构建好的 Hash 表进行分组聚集，查询总代价为 2.66。
以下是对于上述查询计划中各个组成部分的详细解读（算子详解见上文表格）：
- Seq Scan：即 Sequential Scan，顺序扫描。如果被查询表没建索引，或需获取查询表的大多数数据，那么优化器大概率会采取此扫描方式。
- Hash：构造哈希表。在查询计划中 Hash 虽作为一个独立的计划节点显示，但实际上其并不是一个单独的节点，而是 Hash Join 节点的一部分。
- Hash Cond：显示要被连接的列。
- Hash Join：详见上文计划节点表。
- Group Key：指定的聚集键。
- HashAggregate：即 HashAgg ，详见上文计划节点表。
- cost：查询计划的成本估算。cost 的代价评估由两部分组成（中间由 “...” 分割）：
- 第一部分是启动代价，即返回第一行的代价。对于顺序扫描，启动成本通常接近于零，因为它可以立即开始获取行；对于排序操作则会较高，因为在执行引擎开始返回行之前需要完成大部分排序工作。
- 第二部分是总代价，即返回所有行的代价。注意：此处的代价并不指时间。
- rows：由计划节点输出的行数。这个数字可能会小于查询计划节点实际处理或者扫描的行数，它反映了
WHERE子句条件的选择度评估。总代价代表假设所有的行将被检索出来的代价评估，但并非总是这样（例如，如果你使用了LIMIT子句，情况可能不一样）。 - width：计划节点输出的所有列的以字节计的宽度。
4.2 并行查询计划
同上，首先创建两个表。（示例表在分布式数据库 YMatrix 5.1 中使用 MARS3 存储引擎创建）
创建 MARS3 表前需要首先创建主要用于时序相关功能的 matrixts 扩展。
=# CREATE EXTENSION matrixts;
=# CREATE TABLE sale (
cid int,
pid int,
pnum int,
qty float,
date timestamp
) USING MARS3
DISTRIBUTED BY (cid,date)
ORDER BY (cid,date);=# CREATE TABLE customer (
cid int,
cname text,
cwechat text
) USING MARS3
DISTRIBUTED BY (cid)
ORDER BY (cid);同上，分别插入相同的测试数据并采集统计信息。
完成后以相同的 SQL 语句生成查询计划，由于 YMatrix 默认开启向量化，查询计划中会调用大量向量化算子，这有助于查询性能的提升。
=# EXPLAIN SELECT c.cname, sum(s.pnum * s.qty) AS amount FROM sale s, customer c WHERE s.cid = c.cid GROUP BY c.cname;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------
Gather Motion 4:1 (slice1; segments: 4) (cost=72.26..72.44 rows=10 width=14)
-> GroupAggregate (cost=72.26..72.32 rows=2 width=14)
Group Key: c.cname
-> Sort (cost=72.26..72.27 rows=2 width=18)
Sort Key: c.cname
-> Redistribute Motion 4:4 (slice2; segments: 4) (cost=0.00..72.25 rows=2 width=18)
Hash Key: c.cname
-> Nested Loop (cost=0.00..72.20 rows=2 width=18)
Join Filter: (s.cid = c.cid)
-> Custom Scan (MxVMotion) Redistribute Motion 4:4 (slice3; segments: 4) (cost=0.00..36.07 rows=2 width=16)
Hash Key: s.cid
-> Custom Scan (MxVScan) on sale s (cost=0.00..36.02 rows=2 width=16)
-> Materialize (cost=0.00..36.04 rows=2 width=10)
-> Custom Scan (MxVScan) on customer c (cost=0.00..36.02 rows=2 width=10)
Optimizer: Postgres query optimizer
(15 rows)该查询计划有 6 个主要节点：Materialize、Redistribute Motion、Nested Loop、Sort、GroupAggregate 和 Gather Motion。每一个节点包含三个代价估值：cost、 行数（rows）、以及行宽度（width），这几个估值可以帮助我们提前对该 SQL 的执行时间、结果集规模及数据传输和处理的复杂性有所了解。
此查询计划树结构图如下：
可以看到，优化器首先规划了一个物化操作，对 customer 表的扫描与物化操作共产生约 36 的代价值。因为 customer 表在 Segment 上按照 cid 分布，而 sale 表是按照 (cid,date) 分布。因此 sale 表必须首先按照 cid 重新分布，才可分别在每个 Segment 本地连接两张表的相关元组。重分布完成后，以 s.cid = c.cid 过滤条件进行嵌套循环连接操作。可以看到，到达这一步时，此查询计划的总代价约为 72，已经对资源产生了较多消耗。再次地，由于查询语句中要求结果要根据 cname 字段分组，因此优化器规划了第二次重分布操作，并按照 cname 字段进行排序，最终完成分组聚集。经过以上几步，此查询已经计算完成，汇总给 Gather Motion 计划节点，由 Gather Motion 节点估算出查询总代价（72.32）并将结果发送给 Master。
以下是对于上述查询计划中各个组成部分的详细解读（算子详解见上文表格）：
- Materialize：详见上文计划节点表。
- MxVScan：详见上文计划节点表。
- MxVMotion：详见上文计划节点表。
- Hash Key：创建哈希表所制定的哈希键。
- Nested Loop：详见上文计划节点表。
- Join Filter：指定的连接过滤条件。
- Redistribute Motion：重分布算子。它在 Segment 节点实例之间移动元组以完成连接。
- Sort：详见上文计划节点表。
- Sort Key：指定的排序键。
- GroupAggregate：详见上文计划节点表。
- Group Key：指定的聚集键。
- Gather Motion：表示 Segment 节点实例何时将结果发回给 Master，Master 再将结果呈现给客户端。由于只要有 Motion 产生查询计划就会被切片，这个计划在其最顶层也有一个隐式的切片（slice 3）。不过不是所有的查询计划都需要此算子。例如
CREATE TABLE x AS SELECT...语句，因为元组都会被发送到新创建的表而不是发给 Master。 - segments：数据节点实例数量。
- slice：分布式数据库系统中，查询计划通常分为多个切片，每个切片负责计划的一部分，以便查询计划的各个部分可以由这些 Segments 并行处理。划分 slice 的边界为 Motion，每遇到 Motion 就会将 Motion 切开成为发送方和接收方。
- cost：见单机查询计划分析。
- rows：见单机查询计划分析。
- width：见单机查询计划分析。
此查询计划中 Segment 1 与 Segment 2 的 Slice 划分示意图如下：
