【源码解读】CockroachDB Hash Join算子逻辑解读

大家好，我是讯享网，很高兴认识大家。

关于CockroachDB

CockroachDB 是一个分布式关系型数据库，主要设计目标是可扩展，强一致和高可靠。CockroachDB 旨在无人为干预情况下，以极短的中断时间容忍磁盘、主机、机架甚至整个数据中心的故障。 CockroachDB 采用完全去中心化架构，集群中各个节点的地位完全对等，同时所有功能封装在一个二进制文件中，可以做到尽量不依赖配置文件直接部署。

关于Hash Join

所谓 Hash Join 就是在表的 join 时候选择一张表作为 buildSide 表来构造哈希表，另外一张表作为 probeSide 表，然后对 probeSide 表的每一行数据都去这个哈希表中查找是否有匹配的数据（其中 buildSide 表通常是小表，probeSide 表通常是较大的表）。

源码解读

本文解析源码位于cockroach/pkg/sql/opt/xform/coster.go

cockroach/coster.go at master · cockroachdb/cockroach · GitHub
讯享网https://github.com/cockroachdb/cockroach/blob/master/pkg/sql/opt/xform/coster.gocomputeHashJoinCost函数，大致位于779-837行

算子逻辑

Hash Join一般用于连接中，左右表数据量较大并且左表行数明显大于右表。连接过程中 Hash Join 为小表建立 hash table，读取大表的每一行，计算关联列的 hash key，通过 hash map 映射到对应元组。

代价计算涉及常数因子及辅助函数

常数因子

hugeCost：表示的是通常大于开销模型估计结果的一个代价值，hugeCost=1e100
cpuCostFactor：从 PostgreSQL 中的 DEFAULT_CPU_TUPLE_COST 借鉴而来，cpuCostFactor=0.01

辅助函数

computeFiltersCost：返回执行过滤器的设置和每行成本。这个函数的调用者应该添加 setupCost，并将 perRowCost 乘以预期要过滤的行数。

setupCost += cpuCostFactor perRowCost += cpuCostFactor

讯享网

此处是为了添加一个基本的 perRowCost，这样调用者就不需要有自己的每行基本成本

算子开销计算公式及流程

计算公式

Cost = 1.25 * leftRowCount + 1.75 * rightRowCount * cpuCostFactor + filterSetup + rowsProcessed * filterPerRow

其中 1.25 是左边计算 hashkey 的开销，1.75 是建立 hashtable 的开销

具体计算流程

首先判断 hint 是否禁止 HashJoin，禁止则返回 hugeCost，否则进入下一步。
得到leftRowCount 和 rightRowCount。
读表代价： cost := memo.Cost(1.25*leftRowCount+1.75*rightRowCount) * cpuCostFactor。
计算 filter cost。FiltersItem 筛选由包含 Select 或 Join 操作符的行，只有当所有条件都为 true 时，才过滤一行。如果该集合为空，则它永远不会过滤行；func ExtractJoinEqualityColumns 提取连接相等列，返回一对列（一个来自左边，一个来自右边），它们在连接中被约束为相等（并且具有等效类型）。
eqMap := util.FastIntMap{}定义相等过滤器。FastIntMap 当键和值都很小时，它更有效，它可以通过值传递。
估算重新计算的代价：cost += filterSetup。
计算两表连接后最终需要总行数的代价 cost+= memo.Cost(rowsProcessed) * filterPerRow，最后返回 cost 值。

实例测试

一般测试

SQL语句

讯享网SELECT * FROM customer JOIN nation ON (c_nationkey = n_nationkey) ;

表的情况

Input	Left Table: customer	Left row count=
Input	Right Table: nation	Right row count=25

实验结果

读表代价	filter cost	连接后的最终代价
leftRowCount =	filterPerRow = 0.01	cost+=memo.Cost(rowsProcessed)*filterPerRow
rightRowCount = 25	filterSetup = 0.01	cost+=memo.Cost(rowsProcessed)*filterPerRow
cost = 1875.4375	cost =1875.4475	cost = 3375.4475
Output: cost=3375.4475

Hash Join、Merge Join、Lookup Join 实验对比：