3.HashJoin 节点 postgres=# explain select a.*,b.* from test_dm a join test_dm2 b on a.xxx = b.xxx; QUERY PLAN -------------------------------------------------------------------------------- Hash Join (cost=34846.00..305803.23 rows=1000000 width=137) Hash Cond: ((b.xxx)::text = (a.xxx)::text) -> Seq Scan on test_dm2 b (cost=0.00..223457.17 rows=10000017 width=69) -> Hash (cost=22346.00..22346.00 rows=1000000 width=68) -> Seq Scan on test_dm a (cost=0.00..22346.00 rows=1000000 width=68) (5 行)
Hashjoin节点实现了Hash连接算法，它能够实现前面说到的六种连接方式。
以下我们以表R(左关系)与表S(右关系)连接为例，说明Hash连接的实现过程。
1)对一个表(例如S)进行Hash时，其块和桶数量的确定和划分方法如下：①首先对S分块(batch),估算存储S所占用的空间(inner_rel_bytes), Hash所使用的内存空间被定义为 1 兆(hash_table_bytes)，则分块的数量 nbatch = ceil(inner_rel_bytes/hash_table_bytes)。
②在内存中，每一个块又被划分为大小为10个元组的桶，因此，个数为nbucket = (hash_table_bytes/tuplesize)/10,其中tuplesize为元组大小的估计值。
③对于一个Hash值为hashvalue的元组，其所属的分块号为(hashvalue/nbucket)%nbatch,其对应的桶号为hashvalue%nbucket。
④在PostgreSQL实现中，为了能够使用位操作(位与和移位)实现取模和取余操作，将nbatch和nbucket取为不小于计算值的2的n次,并使得2^log2_nbuckets = nbucket,则块号的计算方法为(hashvalue >> log2_nbuckets)&(nbatch - 1)，桶号计算式为hashvalue&(nbucket - 1)。
2)执行HashJoin的算法：①顺序获取S中的所有元组，对每一条元组进行Hash,并通过Hash结果获取块号和桶号。对于块号为0的元组，放人内存对应的桶内；否则放入为右关系每个块分别建立的临时文件中。此时，标记当前在内存中的块号curbatch为0。
②从R中获取元组，进行Hash,获取元组块号和桶号。当块号等于当前在内存中的块号时,直接扫描对应的桶，找寻满足条件的元组并进行连接；否则，将其存人为左关系每个块分别建立的临时文件中。执行过程，直到R被扫描完毕。
③从S的块号curbatch + 1对应的临时文件中读取所有存储的元组，将其Hash到相应的桶内，并将curbatch加1。
④从R的块号curbatch对应的临时文件中依次读取所存储的元组，计算其桶号，并扫描桶中S的元组，寻找满足连接条件的元组进行连接。
⑤重复步骤3和4,直到所有的块都被扫描为止。
为了实现上述过程，Hashjoin定义结构如下所示，其中扩展定义了计算左右关系Hash值和Hash值比较的表达式。执行状态节点中存储了各种执行过程中用到的数据结构。和NestLoop节点类似，HashJoinState节点也定义了与NestLoop相同的几个属性。特别需要介绍的是，hj_CurBucketNo用于标记当前放人内存的块号，CurHashValue用于保存当前扫描的左子树元组计算得到的Hash值。此外，hj_CurBucketNo用于标记另一个优化结构对应的桶号，针对于会生成多个块的右关系，当左关系比较大且无序时，PostgreSQL在内存中分配了另一块内存空间，专门用于存储左关系在Hash属性上出现频率较高的Hash值所对应的右关系元组，每个桶对应一个Hash值，这样可以提高连接的效率。至于左关系中哪些Hash值的出现频率较高，可以从pg_statistic系统表中记录的统计信息中获取。这种方式被称为skew方法。
HashJoinState的数据结构
typedef struct HashJoinState { JoinState js; /* its first field is NodeTag */ List *hashclauses; // list of ExprState nodes ,original form of the hashjoin condition List *hj_OuterHashKeys; // list of ExprState nodes ,the outer hash keys in the hashjoin condition List *hj_InnerHashKeys; // list of ExprState nodes ,the inner hash keys in the hashjoin condition List *hj_HashOperators; // list of operator OIDs ,the join operators in the hashjoin condition HashJoinTable hj_HashTable; // hash table for the hashjoin uint32 hj_CurHashValue; // hash value for current outer tuple int hj_CurBucketNo; // regular bucket# for current outer tuple int hj_CurSkewBucketNo; // skew bucket# for current outer tuple HashJoinTuple hj_CurTuple; // last inner tuple matched to current outer tuple, or NULL if starting search (hj_CurXXX variables are undefined if // variables are undefined if OuterTupleSlot is empty!) TupleTableSlot *hj_OuterTupleSlot; // tuple slot for outer tuples TupleTableSlot *hj_HashTupleSlot; // tuple slot for inner (hashed) tuples TupleTableSlot *hj_NullOuterTupleSlot; // prepared null tuple for right/full outer joins TupleTableSlot *hj_NullInnerTupleSlot; // prepared null tuple for left/full outer joins TupleTableSlot *hj_FirstOuterTupleSlot; // first tuple retrieved from outer plan int hj_JoinState; // current state of ExecHashJoin state machine bool hj_MatchedOuter; // true if found a join match for current outer bool hj_OuterNotEmpty; // true if outer relation known not empty } HashJoinState;HashJoin的数据结构：
typedef struct HashJoin { Join join; List *hashclauses; } HashJoin;