PostgreSQL nestloop/hash/merge join讲解
背景
PostgreSQL 9.2 beta1 release notes中指出
Improve the planner’s ability to use nested loops with inner index scans.
到目前为止我还不是特别肯定这句话到底是不是要说PostgreSQL 9.2 支持index only scan了, 因此inner index scan可以满足nested loop场景的需求, 否则不仅仅扫描index , 还要扫描heap tuple.
怎么解释呢? 来看一个例子 :
test=> explain analyze select t2.* from t2 join t1 on (t1.id=t2.id) where t2.info in (select 'digoal'||generate_series(100,2000));
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.03..5.94 rows=1 width=17) (actual time=1.260..36.725 rows=1901 loops=1)
-> Nested Loop (cost=0.03..5.09 rows=1 width=17) (actual time=1.250..29.892 rows=1901 loops=1)
-> HashAggregate (cost=0.03..0.04 rows=1 width=32) (actual time=1.187..1.892 rows=1901 loops=1)
-> Result (cost=0.00..0.02 rows=1 width=0) (actual time=0.042..0.607 rows=1901 loops=1)
-> Index Scan using idx_t2_info on t2 (cost=0.00..5.04 rows=1 width=17) (actual time=0.014..0.014 rows=1 loops=1901)
Index Cond: (info = (('digoal'::text || (generate_series(100, 2000))::text)))
-> Index Scan using idx_t1_id on t1 (cost=0.00..0.83 rows=1 width=4) (actual time=0.003..0.003 rows=1 loops=1901)
Index Cond: (id = t2.id)
Total runtime: 41.824 ms
(9 rows)
上面这个例子, 输出列只包含了t2表的列, 并且在过滤条件中t1表只有id这个列出现了. 因此在这个执行计划中, 从始至终都不需要检索t1表的id以外的其他列, 所以在嵌套循环中使用的idx_t1_id索引在扫描时允许发生index only scan. 这是否就是9.2所说的inner index scan呢?
而在其他版本的PostgreSQL中nested loop join也是支持index scan的(注意不是inner index scan).
例如
PostgreSQL 9.1 :
pgdba2000@db-172-16-3-33-> psql test test
psql (9.1.3)
Type "help" for help.
test=> create table t1 (id int,info text);
CREATE TABLE
test=> create table t2 (id int,info text);
CREATE TABLE
test=> insert into t1 select generate_series(1,10000000),'digoal'||generate_series(1,10000000);
INSERT 0 10000000
test=> insert into t2 select generate_series(1,10000000),'digoal'||generate_series(1,10000000);
INSERT 0 10000000
test=> create index idx_t1_id on t1(id);
CREATE INDEX
test=> create index idx_t2_id on t2(id);
CREATE INDEX
test=> analyze t1;
ANALYZE
test=> analyze t2;
ANALYZE
test=> explain select * from t2 join t1 on (t1.id=t2.id) where t2.id between 10000 and 20000;
QUERY PLAN
--------------------------------------------------------------------------------
Nested Loop (cost=0.00..41432.17 rows=9347 width=34)
-> Index Scan using idx_t2_id on t2 (cost=0.00..300.74 rows=9347 width=17)
Index Cond: ((id >= 10000) AND (id <= 20000))
-> Index Scan using idx_t1_id on t1 (cost=0.00..4.39 rows=1 width=17)
Index Cond: (id = t2.id)
(5 rows)
PostgreSQL 9.2 :
pg92@db-172-16-3-150-> psql digoal postgres
psql (9.2beta1)
Type "help" for help.
digoal=# create table t1 (id int,info text) ;
CREATE TABLE
digoal=# create table t2 (id int,info text) ;
CREATE TABLE
digoal=# insert into t1 select generate_series(1,10000000),'digoal'||generate_series(1,10000000);
INSERT 0 10000000
digoal=# insert into t2 select generate_series(1,10000000),'digoal'||generate_series(1,10000000);
INSERT 0 10000000
digoal=# create index idx_t1_id on t1 (id);
CREATE INDEX
digoal=# create index idx_t2_id on t2 (id);
CREATE INDEX
digoal=# analyze t1;
ANALYZE
digoal=# analyze t2;
ANALYZE
digoal=# explain select * from t2 join t1 on (t1.id=t2.id) where t2.id between 10000 and 20000;
QUERY PLAN
--------------------------------------------------------------------------------
Nested Loop (cost=0.00..43968.06 rows=9567 width=34)
-> Index Scan using idx_t2_id on t2 (cost=0.00..252.18 rows=9567 width=17)
Index Cond: ((id >= 10000) AND (id <= 20000))
-> Index Scan using idx_t1_id on t1 (cost=0.00..4.56 rows=1 width=17)
Index Cond: (id = t2.id)
(5 rows)
从执行计划上看9.1和9.2并没有差别.
接下来针对PostgreSQL支持的几种join方法简单的介绍一下.
原文 :
If the query requires joining two or more relations, plans for joining relations are considered after all feasible plans have been found for scanning single relations. The three available join strategies are:
nested loop join: The right relation is scanned once for every row found in the left relation. This strategy is easy to implement but can be very time consuming. (However, if the right relation can be scanned with an index scan, this can be a good strategy. It is possible to use values from the current row of the left relation as keys for the index scan of the right.)
merge join: Each relation is sorted on the join attributes before the join starts. Then the two relations are scanned in parallel, and matching rows are combined to form join rows. This kind of join is more attractive because each relation has to be scanned only once. The required sorting might be achieved either by an explicit sort step, or by scanning the relation in the proper order using an index on the join key.
hash join: the right relation is first scanned and loaded into a hash table, using its join attributes as hash keys. Next the left relation is scanned and the appropriate values of every row found are used as hash keys to locate the matching rows in the table.
接下来分别测试讲解 :
一、nested loop join:
digoal=# explain select * from t2 join t1 on (t1.id=t2.id) where t2.info='digoal';
QUERY PLAN
---------------------------------------------------------------------------
Nested Loop (cost=0.00..229697.53 rows=1 width=34)
-> Seq Scan on t2 (cost=0.00..229692.74 rows=1 width=17)
Filter: (info = 'digoal'::text)
-> Index Scan using idx_t1_id on t1 (cost=0.00..4.78 rows=1 width=17)
Index Cond: (id = t2.id)
(5 rows)
Nested Loop 过程 :
1. t2表进行扫描, 过滤条件info = ‘digoal’.
2. t2表根据过滤条件输出的中间结果, 每一条中间结果, t1表都根据索引idx_t1_id扫一遍, 过滤条件id= t2.id.
二、merge join:
digoal=# explain select * from t2 join t1 on (t1.id=t2.id) ;
QUERY PLAN
---------------------------------------------------------------------------------------
Merge Join (cost=11.00..616234.57 rows=9999682 width=34)
Merge Cond: (t2.id = t1.id)
-> Index Scan using idx_t2_id on t2 (cost=0.00..255616.56 rows=9999682 width=17)
-> Index Scan using idx_t1_id on t1 (cost=0.00..255621.77 rows=10000198 width=17)
(4 rows)
Merge Join 过程 :
1. 注意merge join需要两个JOIN的表的KEY都是先排好顺序的. 这里用到了两个索引, 所以没有排序过程.
2. merge join的好处是两个表都只扫描一次. 而nested loop的话其中一个表扫描一次, 另一个表则循环多次.
接下来看看如果没有索引的话, merge join是需要事先排序的.
digoal=# set enable_hashjoin=off;
SET
digoal=# explain select * from t2 join t1 on (t1.info=t2.info) ;
QUERY PLAN
--------------------------------------------------------------------------------
Merge Join (cost=2327542.28..2440038.97 rows=9999682 width=34)
Merge Cond: (t1.info = t2.info)
-> Sort (cost=1163797.91..1166297.96 rows=10000198 width=17)
Sort Key: t1.info
-> Seq Scan on t1 (cost=0.00..227197.98 rows=10000198 width=17)
-> Materialize (cost=1163744.38..1168744.22 rows=9999682 width=17)
-> Sort (cost=1163744.38..1166244.30 rows=9999682 width=17)
Sort Key: t2.info
-> Seq Scan on t2 (cost=0.00..227192.82 rows=9999682 width=17)
(9 rows)
可以看出两个表JOIN的KEY是info列, 这个列上没有索引, 所以先两个表都全表扫描, 然后按照info排序, 然后是merge join.
三、hash join
digoal=# explain select * from t1 join t2 on (t1.info=t2.info) where t2.id between 1 and 1000;
QUERY PLAN
------------------------------------------------------------------------------------
Hash Join (cost=38.70..230996.31 rows=956 width=34)
Hash Cond: (t1.info = t2.info)
-> Seq Scan on t1 (cost=0.00..227197.98 rows=10000198 width=17)
-> Hash (cost=28.90..28.90 rows=956 width=17)
-> Index Scan using idx_t2_id on t2 (cost=0.00..28.90 rows=956 width=17)
Index Cond: ((id >= 1) AND (id <= 1000))
(6 rows)
Hash Join 过程 :
1. 首先扫描t2表, 过滤条件是t2.id between 1 and 1000, 这里由于t2上id有索引, 所以是走的index scan, 扫描后的结果放到一个Hash表中. Hash key就是两个表关联的列, 这里也就是id列.
2. 然后扫描t1表, 扫描到的ID列的值用于去匹配Hash表的KEY值, 匹配到则输出.
hash join和merge join被关联的两个表都只扫描一次, nested loop join则被关联的表其中一个扫描一次, (如果前一个表的扫描结果有多行输出)另一个扫描多次.
参考
http://www.postgresql.org/docs/devel/static/planner-optimizer.html