993
高階魔方與數據編排 - 數據庫存儲優化之路
標簽
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進行結合，提高計算能力。
最後更新：2017-06-15 15:31:54