修改一个等值条件使SQL用上HASH JOIN的优化方法 - l1t1/note GitHub Wiki

为了解决“把数字从1到N放到圆周上，没有重复，每个相邻对之和都是一个平方数。”的问题，当N=36时编写了如下程序，

with recursive t(i) as (select * from generate_series(1,36 )),
  s(s) as (select i*i from t where i*i<36 +36 ),
  a(a,b,c)as (select t.i,t1.i,t.i+t1.i from t,t t1 where t.i<>t1.i and t.i+t1.i in (select s from s)),
  c(lv,l,r,bmp,path)
  as(select 1,1,a.b, (1::bigint<<(1-1))+(1::bigint<<(a.b-1)),array[1,a.b] from a where a.a=1
  union all
  select lv+1,c.r,a.b, bmp + (1::bigint<<(a.b-1)),path||array[a.b]from c,a where a.a=c.r and bmp & (1::bigint<<(a.b-1))=0 and lv<36 -1)
  select * from c where lv=36 -1 and 1+c.r in (select s from s)  ;
  
Run Time (s): real 4.691 user 12.708000 sys 1.448000

这个程序用递归方法从第1个数字接到第35个，中间结果都要保留，比较慢，而从第1个数字接到第18个是很快的，能否把两个18个数序列的两端接起来，形成一个圆周？所以有如下修改：

with recursive t(i) as (select * from generate_series(1,36 )),
  s(s) as (select i*i from t where i*i<36 +36 ),
  a(a,b,c)as (select t.i,t1.i,t.i+t1.i from t,t t1 where t.i<>t1.i and t.i+t1.i in (select s from s)),
  c(lv,l,r,bmp,path)
  as(select 1,1,a.b, (1::bigint<<(1-1))+(1::bigint<<(a.b-1)),array[1,a.b] from a where a.a=1
  union all
  select lv+1,c.r,a.b, bmp + (1::bigint<<(a.b-1)),path||array[a.b]from c,a where a.a=c.r and bmp & (1::bigint<<(a.b-1))=0 and lv<19 -1)
,c1 as(select * from c where lv=19-1 and bmp&2 =2)
,c2 as(select * from c where lv=19-1 and (bmp&2 =0 or r=2))
select * from c1,c2 where c1.r=c2.r and c1.bmp|c2.bmp=(1::bigint<<36)-1::bigint ;

Run Time (s): real 8.083 user 16.560000 sys 0.196000

两端连接已经考虑了某个数字（这里是2）只放在一边或者在连接处的优化，结果反而更慢，因为c1.bmp|c2.bmp=68719476735::bigint不能作为HASH JOIN的连接条件，只能用作过滤。把原表达式左边的c2.bmp列移动到右边，并作等价改写，就可以把这个等值条件用作HASH JOIN的关联条件了。

with recursive t(i) as (select * from generate_series(1,36 )),
  s(s) as (select i*i from t where i*i<36 +36 ),
  a(a,b,c)as (select t.i,t1.i,t.i+t1.i from t,t t1 where t.i<>t1.i and t.i+t1.i in (select s from s)),
  c(lv,l,r,bmp,path)
  as(select 1,1,a.b, (1::bigint<<(1-1))+(1::bigint<<(a.b-1)),array[1,a.b] from a where a.a=1
  union all
  select lv+1,c.r,a.b, bmp + (1::bigint<<(a.b-1)),path||array[a.b]from c,a where a.a=c.r and bmp & (1::bigint<<(a.b-1))=0 and lv<19 -1)
,c1 as(select * from c where lv=19-1 and bmp&2 =2)
,c2 as(select * from c where lv=19-1 and (bmp&2 =0 or r=2))
select * from c1,c2 where c1.r=c2.r and c1.bmp=(1::bigint<<36) -c2.bmp +(1::bigint<<(c2.r-1));

Run Time (s): real 0.581 user 1.552000 sys 0.212000