标签

PostgreSQL , cluster , 预排 , 一维数据 , 多维数据 , 视觉编排 , 数据编排 , IO优化

---

背景

中华文化源远流长，比如这句古语“远水不救近火，远亲不如近邻”，在数据库的优化中亦有体现。接下来我们来揭示这个道理。

大多数数据库的存储为块存储，一个块里面可能涉及到多条记录，当用户输入查询条件进行数据检索时，即使返回的结果集较小，也可能需要扫描多个数据块，因为你不知道你要的记录落在哪些数据块里面。

例子

随机写入一批数据

create table tbl(id int, info text default repeat(random()::text,10), crt_time timestamp default now());  
insert into tbl (id) select random()*10000 from generate_series(1,1000000);  

查询ID<100的记录，这些记录落在哪些数据块里面？

postgres=# select ctid from tbl where id<100;  
    ctid      
------------  
 (4,10)  
 (6,32)  
 (7,33)  
 (17,14)  
 (22,15)  
 (22,16)  
 (25,2)  
 (29,21)  
 (41,13)  
 (42,27)  
 (43,27)  
 (54,11)  
 (54,33)  
 (56,1)  
 (60,13)  
。。。。。。  

可以看到，数据散落在不同的数据块里面。也就是说访问了很多数据块。

很多用户遇到了类似的问题，我做了一些总结和优化之道，请参考下面的文章。

《索引顺序扫描引发的堆扫描IO放大背后的统计学原理与解决办法》

《懒人推动社会进步 - 多列聚合, gin与数据分布(选择性)》

《索引扫描优化之 - GIN数据重组优化(按元素聚合) 想象在玩多阶魔方》

以上文章提到了优化的方法：数据重新编排存储。让数据尽量的根据搜索条件进行聚集，减少扫描成本。

数据存储优化 - 编排

数据存储编排的目的很简单，让数据尽量的根据搜索条件进行聚集，减少扫描成本。

但是数据种类不一样，编排优化也不太一样。前面提到的例子针对的都是一维的数据，一维数据的操作很简单，=, >, <, >=, <=, in等。

如果数据类型不是一维类型，而是多值类型或者异构类型呢？例如数组、空间类型、全文检索类型等。数据的编排还有这么简单吗？

一维数据编排

一维类型的编排，按搜索列排序是最简单有效的编排方法。业界也叫预排序，PostgreSQL术语叫cluster，通过cluster命令即可完成编排。

https://www.postgresql.org/docs/9.6/static/sql-cluster.html

多维数据编排

一位编排比较简单，但是多维编排会更加复杂。我通过一个游戏来说明编排的目的。

我们来玩一个游戏，假设全球有10000个国家，每个国家挑选若干人（每个国家挑选的人数可以不一样，例如A国家挑选了1000人，B国家挑选了10人，假设总共挑选了100万人）进行混合分组，每个分组包含了若干不同国家的人（每个分组每个国家仅限1人）。下面进行排队，横坐标为分组ID，纵坐标为国家ID。接下来要进行搬运游戏，从左导游，每个国家的人，需要将它手里的球搬运给右边的相同国家的人，如果他们相邻，则不计成本。如果他们之间隔了其他分组，则计算成本（相隔的分组个数）。最终计算每个国家的搬运成本，某些国家的搬运成本，或者所有国家相加的总搬运成本。

如何降低总成本，如何降低某些国家的成本，如何降低某个国家的成本？

例如第一种排列方式，1号国家的搬运成本为2， 6号，7号国家的搬运成本为1，其他国家的搬运成本为0。

第二种排列方式如下，所有国家的搬运成本都为0。

这就是数组类型编排要取得的目的，由于数组类型通常是按数组的元素进行检索的，因此我们需要根据元素来进行编排。数组类型的编排方式同样适用于全文检索类型，TOKEN类型。

其他类型的编排则根据数据类型来定，例如空间类型，可以根据GEOHASH的值进行排序编排。

下面我们讲一下数组类型编排的实现过程。

生成测试数据

生成随机数组的方法

postgres=# create or replace function gen_array(range int, cnt int) returns int[] as $$  
select array(select (random()*range)::int from generate_series(1,cnt) group by 1);  
$$ language sql strict volatile;  
CREATE FUNCTION  
  
postgres=# select gen_array(10,5);  
 gen_array   
-----------  
 {9,1,5,8}  
(1 row)  
  
postgres=# select gen_array(10, 20);  
       gen_array          
------------------------  
 {9,3,1,4,5,2,7,6,8,10}  
(1 row)  
  
postgres=# select gen_array(100,10) from generate_series(1,100);  
            gen_array               
----------------------------------  
 {9,16,51,72,31,27,20,63,41,65}  
 {88,1,59,39,87,28,24,32,21}  
 {69,78,34,11,84,79,97,80,85,56}  
 {3,90,42,81,83,41,76,99,65,25}  
 {14,4,42,50,37,13,72,75,29,74}  
 {23,92,53,74,77,71,93,82}  
 {1,16,81,51,79,76,62,94,77}  
 {48,64,18,35,43,36,54,41,29,98}  
 {100,84,28,99,80,8,85,77,10,33}  
 {96,31,39,7,87,53,36,54,30,77}  
 {70,49,90,91,13,40,31,54,97,94}  
 {58,55,35,75,29,6,65,56,98}  
......  

建立测试表，写入随机数组

postgres=# create table tbl2(id int, arr int[]);  
CREATE TABLE  
  
postgres=# insert into tbl2 select id, gen_array(10,10) from generate_series(1,10) t(id);  
INSERT 0 10  
  
postgres=# select * from tbl2 limit 10;  
 id |         arr           
----+---------------------  
  1 | {1,5,2,6,8}  
  2 | {1,4,5,2,7,6,8,0}  
  3 | {9,1,5,2,7,6,8}  
  4 | {3,1,4,5,2,7,6}  
  5 | {9,1,5,2,7,8,10}  
  6 | {9,3,1,2,7,6,8}  
  7 | {9,3,1,5,2,7,8}  
  8 | {3,1,4,5,2,6,10}  
  9 | {9,3,1,4,5,2,7,6,8}  
 10 | {3,1,5,7,6,10,0}  
(10 rows)  

10条记录，有多少种排列组合的可能呢？

PostgreSQL有排列组合函数可以支持，如下。

postgres=# \df *.*fac*  
                             List of functions  
   Schema   |    Name     | Result data type | Argument data types |  Type    
------------+-------------+------------------+---------------------+--------  
 pg_catalog | factorial   | numeric          | bigint              | normal  
 pg_catalog | numeric_fac | numeric          | bigint              | normal  
(2 rows)  
  
postgres=# select factorial(10);  
 factorial   
-----------  
   3628800  
(1 row)  
  
postgres=# select numeric_fac(10);  
 numeric_fac   
-------------  
     3628800  
(1 row)  
  
postgres=# select 10*9*8*7*6*5*4*3*2;  
 ?column?   
----------  
  3628800  
(1 row)  
  
postgres=# select 10!;  
 ?column?   
----------  
  3628800  
(1 row)  
  
postgres=# \do+ !  
                                      List of operators  
   Schema   | Name | Left arg type | Right arg type | Result type |  Function   | Description   
------------+------+---------------+----------------+-------------+-------------+-------------  
 pg_catalog | !    | bigint        |                | numeric     | numeric_fac | factorial  
(1 row)  

排列组合

排列组合，指行的排列顺序。下面两篇文档中也涉及排列组合的例子。

《PostgreSQL n阶乘计算, 排列组合计算 - 如何计算可变参数中有没有重复参数》

《为什么啤酒和纸尿裤最搭 - 用HybridDB/PostgreSQL查询商品营销最佳组合》

通过行号的顺序，得到排列组合，验证通过。

postgres=#  WITH RECURSIVE cte AS (  
     SELECT array[ctid] AS combo, ctid, 1 AS ct   
     FROM tbl2  
   UNION ALL   
     SELECT array_append(cte.combo, t.ctid), t.ctid, ct + 1   
     FROM cte, tbl2 t  
     WHERE ct <= 10  -- 10是 tbl2的count(*)，即自关联10次，得到所有排列组合  
       AND array_position(cte.combo, t.ctid) is null  -- 元素去重  
)   
SELECT count(combo) FROM cte where ct=10;  -- 10是 tbl2的count(*)  
  
  count    
---------  
 3628800  
(1 row)  

排列组合示例：

postgres=#  WITH RECURSIVE cte AS (    
     SELECT array[ctid] AS combo, ctid, 1 AS ct   
     FROM tbl2  
   UNION ALL   
     SELECT array_append(cte.combo, t.ctid), t.ctid, ct + 1   
     FROM cte, tbl2 t  
     WHERE ct <= (select count(*) from tbl2)   
       AND array_position(cte.combo, t.ctid) is null  
)   
SELECT combo FROM cte where ct=10 limit 10;  
                                       combo                                          
------------------------------------------------------------------------------------  
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,7)","(0,8)","(0,9)","(0,10)"}  
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,7)","(0,8)","(0,10)","(0,9)"}  
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,7)","(0,9)","(0,8)","(0,10)"}  
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,7)","(0,9)","(0,10)","(0,8)"}  
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,7)","(0,10)","(0,8)","(0,9)"}  
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,7)","(0,10)","(0,9)","(0,8)"}  
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,8)","(0,7)","(0,9)","(0,10)"}  
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,8)","(0,7)","(0,10)","(0,9)"}  
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,8)","(0,9)","(0,7)","(0,10)"}  
 {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,8)","(0,9)","(0,10)","(0,7)"}  
(10 rows)  

统计每一种排列组合，各个元素的检索成本

计算每一种排列组合，对应数组元素的聚合度（越靠近0(越小)，越聚合）

根据前面的聚合度算法，使用如下函数实现。

create or replace function cal_affinity(OUT o_combo tid[], OUT affinity int8) returns setof record as $$  
declare  
  ccc int8;     -- tbl2总共多少条记录  
  v_tid tid[];  -- 行号组合  
  vv_tid tid;   -- 行号  
  i1 int := 1;  -- 正处于第几行  
  i2 int[];     -- 与tbl2.arr同类型的数组，存储所有元素  
  i3 int[];     -- 上一次元素出现在第几行，下标=i2 中元素的位置  
  i4 int[];     -- 每个元素的聚合度累计值  
  v_i4 int;     -- 每个元素单独的聚合度  
  sum_i4 int8;  -- i4的sum  
  x int;        -- 第几个循环  
  v_arr int[];  -- tbl2 数组  
  i_arr int;    -- tbl2 数组元素  
begin  
  select count(*) into ccc from tbl2;  
  select array(select distinct(unnest(arr)) from tbl2) into i2;  
  
-- 排列组合循环  
for v_tid in   
  WITH RECURSIVE cte AS (    
       SELECT array[ctid] AS combo, ctid, 1 AS ct   
       FROM tbl2  
     UNION ALL   
       SELECT array_append(cte.combo, t.ctid), t.ctid, ct + 1   
       FROM cte, tbl2 t  
       WHERE ct <= ccc  
         AND array_position(cte.combo, t.ctid) is null  
  )   
  SELECT combo FROM cte where ct=ccc limit 10   --  只计算10种组合  
  -- 3628800种组合实在太多了，我挑选一些进行计算，验证聚合度结果。  
loop  
    
  -- 按行号循环  
  foreach vv_tid in array v_tid   
  loop  
      
    -- 生成tbl2当前行的数组  
    select arr into v_arr from tbl2 where ctid=vv_tid;  
  
    -- 按tbl2数组元素循环，计算每个元素的聚合度累加  
    foreach i_arr in array v_arr  
    loop  
      -- 获取元素下标 array_position(i2, i_arr)  
      -- i1=1，处于第一行  
  
      -- 计算聚合度，真实场景应该改成数据块是否相邻，而不是行号  
      if i1=1 then  
	-- 第一行  
	i4[array_position(i2, i_arr)] := 0;  
      else  
        -- 不是第一行  
	if i4[array_position(i2, i_arr)] is null then  
          -- 该元素第一次出现  
	  i4[array_position(i2, i_arr)] := 0;  
	else  
	  -- 该元素不是第一次出现  
	  i4[array_position(i2, i_arr)] := i4[array_position(i2, i_arr)] + greatest((i1 - i3[array_position(i2, i_arr)] - 1), 0);  -- 防止单行元素重复计算错误  
	end if;  
      end if;  
        
      -- 元素最后一次出现在第几行  
      i3[array_position(i2, i_arr)] := i1;  
    end loop;  
  
    -- 行号+1  
    i1 := i1 + 1;  
  end loop;  
  
  -- 输出该排列组合的所有元素的聚合度，总聚合度  
  select sum(unnest) into sum_i4 from (select unnest(i4)) t;  
  raise notice 'combo: %, sum(affinity): %', v_tid, sum_i4;  
  x := 1;  
  foreach v_i4 in array i4  
  loop  
    raise notice 'elements: %, affinity: %', i2[x], v_i4;  
    x := x+1;  
  end loop;  
    
  -- 初始化变量  
  i1 := 1;  
  i3 := '{}';  
  i4 := '{}';  
end loop;  
-- 行号循环  
end;  
$$ language plpgsql strict;  

调用函数计算聚合度

select * from cal_affinity();  
  
NOTICE:  combo: {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,7)","(0,8)","(0,9)","(0,10)"}, sum(affinity): 23  
NOTICE:  elements: 7, affinity: 1  
NOTICE:  elements: 9, affinity: 2  
NOTICE:  elements: 3, affinity: 1  
NOTICE:  elements: 1, affinity: 0  
NOTICE:  elements: 4, affinity: 4  
NOTICE:  elements: 6, affinity: 2  
NOTICE:  elements: 8, affinity: 2  
NOTICE:  elements: 5, affinity: 1  
NOTICE:  elements: 2, affinity: 0  
NOTICE:  elements: 10, affinity: 3  
NOTICE:  elements: 0, affinity: 7  
NOTICE:  combo: {"(0,1)","(0,2)","(0,3)","(0,4)","(0,5)","(0,6)","(0,7)","(0,8)","(0,10)","(0,9)"}, sum(affinity): 25  
NOTICE:  elements: 7, affinity: 1  
NOTICE:  elements: 9, affinity: 3  
NOTICE:  elements: 3, affinity: 1  
NOTICE:  elements: 1, affinity: 0  
NOTICE:  elements: 4, affinity: 5  
NOTICE:  elements: 6, affinity: 2  
NOTICE:  elements: 8, affinity: 3  
NOTICE:  elements: 5, affinity: 1  
NOTICE:  elements: 2, affinity: 1  
NOTICE:  elements: 10, affinity: 2  
NOTICE:  elements: 0, affinity: 6  
  
.....  
  

选择sum(affinity)最小的combo，就是最优的排列组合。将数据按这个顺序调整，即可最大的优化性能。

存储

数据编排是存储层面的优化，所以存储本身的属性也决定了应该如何进行数据编排。

平面存储

平面存储，数据按顺序在一个或多个平面上存储，当从数据库中顺序搜索一批数据时，在物理存储层面也可能是相邻的介质。

所以前面提到的编排优化是非常有效的。

SSD、3D存储

硬件特性是SSD或者3D存储结构时，当从数据库中顺序搜索一批数据时，在物理存储层面也可能是相邻的介质，也可能不是，这个需要根据硬件厂商的写特性。

前面的编排对硬件的优化效果可能就没那么好。编排算法应该充分考虑硬件的数据访问特性，才能达到最好的优化效果。

但是对内存的优化效果一定是有的。

GPU - 视觉编排

从前面的例子来看，数据编排的方法会耗费大量的计算量，10条记录就可能有300多万种排列组合，使用CPU运算，计算每种组合的聚合度并不是最好的选择。

对于此类编排聚合度的计算，视觉处理可能是更好的方法。

小结

1、数据编排的目的和好处：让数据更加紧凑，降低访问成本，节约内存。

2、编排应该考虑到多个方面：

数据的访问需求，比如是顺序访问，还是随机访问，是访问等值数据，还是访问范文数据，是访问标量，还是访问多值类型、异构类型等。优化是需要针对访问需求的。

数据存储的硬件特性，硬件是如何处理数据存储和搜索的。也决定了应该如何优化。

内存的硬件特性，同上。

软硬件一体化。

3、PostgreSQL不仅支持简单的标量类型，还支持复杂的多值类型，例如array, range, json, hstore, gis, xml等。在数据编排优化层面更加的复杂。

一维类型的编排就好像只需要完成魔方的一面

多维类型的编排需要完成所有面

随着多维类型元素的增加，记录数的增加，编排难度也会呈指数上升

多维数据的编排，运算量非常庞大，使用GPU处理可能是一种更好的方法。

PostgreSQL UDF支持pl/cuda编程，可以很好的与GPU进行结合，提高计算能力。