书接上文GaussDB关键技术原理：高弹性（一）从CBI索引方面对hashbucket进行了解读，本篇将从优化器剪枝、执行器两方面继续介绍hashbucket。

2.3 优化器剪枝

优化器是一个数据库管理系统中的重要组件，用于优化SQL查询语句的执行计划，从而提高查询性能。优化器的任务是找到最优的执行计划，使得查询结果能够以最快的速度返回。剪枝是一种优化技术，可以根据查询的语义和数据类型，选择最优的执行计划，避免不必要的计算和 IO 操作，提高查询效率。GaussDB中hash分片计划生成流程如图1所示，关键思想是在优化器阶段根据剪枝结果确定要扫描的buckets分片。

图1 hash分片计划生成流程

2.3.1 hash分片剪枝

hash分片剪枝分为静态剪枝和动态剪枝，静态剪枝是在优化器阶段根据表达式的过滤条件进行剪枝，动态剪枝是在执行器阶段根据运行时数据进行剪枝。在当前系统中，GaussDB只支持单分布键剪枝。下面以静态剪枝为例介绍优化器剪枝原理。

涉及到hash分片剪枝的表达式有两类：

• 集合运算表达式：AND OR
• 比较运算表达式：= 、!=

剪枝的过程就是集合运算的过程。先把基表上有关分布列的过滤条件抽取出来并转换为c1 op const AND c2 op const OR c3 op const ...的形式，然后针对每个表达式部分求解剪枝结果并进行集合运算(AND:INTERSECT, OR:UNION)，剪枝结果用集合进行表示，保存在结构体BucketInfo中。剪枝过程如下：

（1）确定能参与剪枝的条件。非分布列的条件不能剪枝（结果为全集）。

（2）以OR条件进行分组，对每个分布列 op const求出部分剪枝结果。

（3）进行集合运算求出整体剪枝结果。

算法入参为基表的表达式树如下图2，剪枝算法需要遍历表达式树，并对每个节点采取相应动作：

图2 表达式树示意图

• AND表达式：获取两边剪枝结果，求交集。
• OR表达式：获取两边剪枝结果，求并集。
• =表达式，分情况处理：var = const时，若var是分布列，对const求hashbucketid，返回[bucketid]剪枝结果，若var是非分布列，返回全集；var = non-const，返回全集。
• !=表达式，分情况处理：var是分布列，对const求hashbucketid，返回不包含bucketid的剪枝结果；var是非分布列，返回全集；var = non-const 返回全集。
• 其他表达式无法处理：返回全集。

EXPLAIN是一个用于分析查询语句执行计划的命令，通过分析一条简单SQL语句“select * from t1 where a = 3 and b !=3;”语句的执行计划来了解hashbucket优化器剪枝对生成执行计划的影响。执行计划的显示格式为“算子（算子修饰符）（算子估算代价 结果集行数 结果集宽度）”。语句的执行计划如下：

gaussdb=# explain verbose select * from t1 where a = 3 and b !=3;
                           QUERY PLAN
-----------------------------------------------------------------
 Streaming (type: GATHER)  (cost=0.06..1.25 rows=2 width=12)
   Output: a, b, c
   Node/s: datanode4
   ->  Seq Scan on gaussdb.t1  (cost=0.00..1.03 rows=2 width=12)
         Output: a, b, c
         Distribute Key: a
         Filter: ((t1.b <> 3) AND (t1.a = 3))
         Selected Buckets 1 of 1024 : 642
(8 rows)

• 第一层执行计划是用stream算子（网络数据传输算子）把DN4的数据汇总到CN；
• 第二层是SeqScan顺序扫描算子根据表达式“a=3 and b!= 3”剪枝得到剪枝结果。在表达式中b不是分布列，所以“b!=3”不参与剪枝，由条件“a=3”得到元组所在bucketid为642。在执行此查询语句时就只需要扫描bucketid为642的bucket分片包含的数据元组。

优化器剪枝结果保存在关键数据结构BucketInfo中，BucketInfo设计如下：

typedef struct BucketInfo {
    NodeTag type;
    List *buckets; /* 对应父表要扫描的bucket分片，DN只扫描自己的bucketid。如果剪枝状态不等于BUCKET_EMPTY，buckets为NULL那么表示扫描所有的分区 */
    HBucketPruningStatus status;  /* 表示剪枝结果的状态 */
    Expr *expr;
} BucketInfo;

其中，buckets表示剪枝得到的要扫描的bucket分片，status表示剪枝结果状态，分为：

• BUCKETS_UNINITIED：还未剪枝，结果未知。
• BUCKETS_FULL：生成包含所有bucket的bitmapset。
• BUCKETS_EMPTY：生成不包含bucket的剪枝结果。
• BUCKETS_PRUNED：不允许剪枝。

BucketInfo包含DN要扫描的分片信息，由CN下发给DN执行。在执行时，Scan算子通过剪枝结果状态和buckets列表获取到实际要扫描的bucketid，并通过系统表打开对应bucket的relation。注意下发的bucketids是全局的，DN通过bucketmap来判断哪些bucketid是本机的，只扫描本机的bucketid。

动态剪枝从DN上获取的表定位信息保存在关键数据结构DistqryRelationLocInfo中，设计如下：

typedef struct {
    Oid relid;                /* 表OID */
    char locatorType;         /* 定位器类型，LOCATOR_TYPE_HASH */
    List* partAttrNum;        /* 分布列属性 */
    List* node_list;           /* 数据所在的节点索引 */
    ListCell* roundRobinNode; /* 要使用的下一个节点的索引 */
    NameData gname;
    uint2* buckets_ptr; /* 指向本地bucket-node映射的指针 */
    bool   isbucket;
} DistqryRelationLocInfo;

其中，partAttrNum表示分布列属性，relid表示表的oid，locatorType表示定位器类型，在hashbucket动态剪枝场景中默认设为LOCATOR_TYPE_HASH。

2.4 执行器

执行器是GaussDB数据库核心组件之一，负责执行优化器生成的执行计划，将查询结果返回给用户。在执行过程中，执行器会根据执行计划的不同节点进行相应的操作，如扫描、聚合、排序等。

以堆表索引扫描为例介绍执行器的工作。执行器会根据优化器生成的扫描计划，先初始化扫描相关的数据结构，创建扫描键，指定初始化扫描目标；在索引中查询满足条件的索引元组，并获取该元组内记录的bucketid以及tid（元组id），获取相应的bucket分片（文件），从而缩小目标元组的扫描范围；最后执行器根据之前获取的tid读取上述锁定bucket分片中的block，获取目标元组并返回给客户端。

2.4.1 hash分片执行器扫描

GaussDB支持普通表和分区表扫描，其中分区表扫描是基于普通表来实现的，主要区别是普通表仅扫描一个数据文件，分区表可以理解为扫描多个数据文件。hashbucket表为了更均匀的切分数据文件，把数据按照hash进行分片，支持两种hash方案，即在普通表上支持hash分片，和在分区表上支持hash分片。

2.4.1.1 hash分片扫描流程

当前GaussDB涉及到hash分片扫描的执行算子有：SeqScan（顺序扫描算子）、IndexScan（索引扫描算子）、IndexOnlyScan（仅索引扫描算子）、TidScan（Tuple ID扫描算子）、BitmapIndexScan（位图索引扫描算子）等。每一个算子都可能经过初始化、执行、重置、结束四个阶段。以顺序扫描表的初始化为例，下图3展示增加hash分区后的初始化流程图。其中红色分支是为hash分区表新增的路径。对于其他扫描方式的处理方式类似。

图3 顺序扫描初始化流程图

（1）判断扫描表是否为hash分区表

上图中比较重要的一步是如何区分待扫描的对象是否存在hash分片。在元数据设计中，一个表是否存在hash分片由字段relbucket标识。因此，在扫描对象时，我们仅需要读取这个字段来判断是否存在hash分片。

（2）获取普通表的hash分片的文件号

执行计划中给出了要扫描的对象和表的hash分片号，需要根据这两个信息来获取分片对应的数据文件编号。Relation中保存了每个bucketid对应的文件编号, 可以直接读取。

（3）hashbucket表扫描

普通堆表仅管理一个物理数据文件，hashbucket表需要管理若干个bucket，每个bucket相当于一个普通堆表。对于普通堆表，在初始化阶段生成扫描描述符，用于记录扫描状态；在扫描阶段从数据库文件中读取数据；在扫描结束阶段释放占有的资源。扫描hashbucket表时，需要扫描其所有的bucket，在操作单个bucket时，借助普通堆表的访问接口，复用普通堆表的执行器框架。

2.4.1.2 hash分片表访问接口

用户视角不关注hashbucket表和普通堆表的存储和读取方式，因此我们在堆表和hashbucket表上封装一层通用扫描处理程序，在执行器框架中调用通用接口。普通堆表又抽象出一层TableAM层区分astore表和ustore表，由抽象接口根据表类型动态绑定具体的调用接口，目前hashbucket表仅支持astore存储，所以TableAM层不在此描述。

在表扫描开始时会创建堆表或hashbucket表的扫描描述器，表访问接口会判断当前表是否是hashbucket表，根据表是否是hashbucket表执行相应的访问接口。hashbucket表复用普通堆表的访问接口，由于hashbucket表底层管理了多个堆表，当一个bucket分片扫描完成时，即当前bucket分片中没有数据可读，会切换到下一个bucket进行读取，如此循环直到所有bucket都被读取。

hashbucket表的扫描描述符HBktTblScanDescData 数据结构定义为：

typedef struct HBktTblScanDescData {
    Relation rs_rd;     /* 哈希分片表的Relation */
    struct ScanOperator * scan_state;
    oidvector* h_bkt_list;  /* bucket列表，用于管理待扫描的bucket */
    int      curr_slot; /* 记录当前正在扫描的bucket编号 */
    Relation curr_bkt_rel; /* 当前扫描bucket的堆表结构 */
    TableScanDesc * curr_bkt_scan; /* 当前bucket的TableScan算子 */
} HBktTblScanDescData;

创建hashbucket表扫描描述符HBktTblScanDesc流程如下：

• 从BucketInfo中加载待扫描的buckets。
• 创建并初始化扫描描述符HBktTblScanDesc。
• 打开第一个待扫描的bucket。
• 为当前扫描的bucket开启一个Heap表扫描描述符HeapScanDesc。

对应 SamplingScan、BitmapHeapScan、TidScan等方式的描述符创建流程类似，仅需要为当前处理的bucket创建相应的heap扫描方式。

对于其他访问接口类似，即借助堆表的接口操作每一个bucket。当一个bucket访问完成时，需要切换到下一个bucket，具体实现不再详述。

2.4.1.3 hash分片索引访问接口

索引的访问接口抽象和表接口的抽象类似。封装hashbucket表和非hashbucket表索引扫描的通用接口，在执行器框架中调用通用接口，在TableAm层区分astore和ustore绑定不同接口。hashbucket表的索引访问接口也同样是使用普通堆表的接口，扫描完一个分片之后，切换到下一个分片，具体实现不再赘述。

以上内容从优化器剪枝、执行器两方面对hashbucket进行了解读，下篇将从段页式方面继续介绍GaussDB高弹性技术，敬请期待！