对PostgreSQL 的 hash join 的原理的学习_sql

概述开始 PostgreSQL 名人 momjian 的文章指出了其pseudo code： for (j = 0; j < length(inner); j++)　　hash_key = hash(inner[j]);　　append(hash_store[hash_key], inner[j]);for (i = 0; i < length(outer); i++)　　hash_key =

开始

Postgresql 名人 momjian 的文章指出了其pseudo code：

for (j = 0; j < length(inner); j++)　　hash_key = hash(inner[j]);　　append(hash_store[hash_key],inner[j]);for (i = 0; i < length(outer); i++)　　hash_key = hash(outer[i]);　　0; j < length(hash_store[hash_key]); j++)　　　　if (outer[i] == hash_store[hash_key][j])　　　　　　output(outer[i],inner[j]);

为了看的更加清楚一点，加上自己的注释：

//利用 inner 表，来构造 hash 表(放在内存里) 0; j < length(inner); j++) { hash_key = hash(inner[j]); append(hash_store[hash_key],inner[j]); } 对 outer 表的每一个元素，进行遍历 0; i < length(outer); i++) { 拿到 outer 表中的某个元素，进行 hash运算，得到其 hash_key 值 hash_key = hash(outer[i]); 用上面刚得到的 hash_key值，来对 hash 表进行探测（假定hash表中有此key 值）采用 length (hash_store[hash_Key]) 是因为，hash算法构造完hash 表后，有可能出现一个key值处有多个元素的情况。例如： hash_key 100 ，对应 a,c,e；而 hash_key 200 ，对应 d; hash_key 300，对应 f; 也就是说，如下的遍历，其实是对拥有相同的（此处是上面刚运算的，特定的）hash_key 值的各个元素的遍历 0; j < length(hash_store[hash_key]); j++) { 如果找到了匹配值，则输出一行结果 if (outer[i] == hash_store[hash_key][j]) output(outer[i],inner[j]); } } [作者：技术者高健@博客园 mail:[email protected]]

实践一下：

postgres=# \d employee          table "public.employee" Column |         Type          | ModifIErs --------+-----------------------+----------- ID     | integer               |  name   | character varying(20) |  deptno | integer               |  age    | integer               | Indexes:    IDx_ID_dept" btree (ID,deptno)postgres=# \d deptment           table public.deptment"  Column  |         Type          | ModifIErs ----------+-----------------------+----------- deptno   | integer               |  deptname | character varying(20) | postgres=# postgres=# select count(*) from employee; count -------1000(1 row)postgres=# from deptment; count -------102(1 row)postgres=#

执行计划：

postgres=# explain select a.name,b.deptname from employee a,deptment b where a.deptno=b.deptno;                               query PLAN                                ------------------------------------------------------------------------- Hash Join  (cost=3.29..34.05 rows=1000 wIDth=14)   Hash Cond: (a.deptno = b.deptno)   ->  Seq Scan on employee a  (cost=0.00..17.00 rows=10)   ->  Hash  (cost=2.02..2.02 rows=102 wIDth=12)         ->  Seq Scan on deptment b  (cost=12)(5 rows)postgres=#