postgresql , cluster , 預排 , 一維資料 , 多元資料 , 視覺編排 , 資料編排 , io優化
中華文化源遠流長，比如這句古語“遠水不救近火，遠親不如近鄰”，在資料庫的優化中亦有展現。接下來我們來揭示這個道理。
大多數資料庫的存儲為塊存儲，一個塊裡面可能涉及到多條記錄，當使用者輸入查詢條件進行資料檢索時，即使傳回的結果集較小，也可能需要掃描多個資料塊，因為你不知道你要的記錄落在哪些資料塊裡面。
例子
随機寫入一批資料
查詢id<100的記錄，這些記錄落在哪些資料塊裡面？
可以看到，資料散落在不同的資料塊裡面。也就是說通路了很多資料塊。
很多使用者遇到了類似的問題，我做了一些總結和優化之道，請參考下面的文章。
<a href="https://github.com/digoal/blog/blob/master/201404/20140426_01.md">《索引順序掃描引發的堆掃描io放大背後的統計學原理與解決辦法》</a>
<a href="https://github.com/digoal/blog/blob/master/201706/20170612_04.md">《懶人推動社會進步 - 多列聚合, gin與資料分布(選擇性)》</a>
<a href="https://github.com/digoal/blog/blob/master/201706/20170612_05.md">《索引掃描優化之 - gin資料重組優化(按元素聚合) 想象在玩多階魔方》</a>
以上文章提到了優化的方法：資料重新編排存儲。讓資料盡量的根據搜尋條件進行聚集，減少掃描成本。
資料存儲編排的目的很簡單，讓資料盡量的根據搜尋條件進行聚集，減少掃描成本。
但是資料種類不一樣，編排優化也不太一樣。前面提到的例子針對的都是一維的資料，一維資料的操作很簡單，=, >, <, >=, <=, in等。
如果資料類型不是一維類型，而是多值類型或者異構類型呢？例如數組、空間類型、全文檢索類型等。資料的編排還有這麼簡單嗎？
一維類型的編排，按搜尋列排序是最簡單有效的編排方法。業界也叫預排序，postgresql術語叫cluster，通過cluster指令即可完成編排。
<a href="https://www.postgresql.org/docs/9.6/static/sql-cluster.html">https://www.postgresql.org/docs/9.6/static/sql-cluster.html</a>
一位編排比較簡單，但是多元編排會更加複雜。我通過一個遊戲來說明編排的目的。
我們來玩一個遊戲，假設全球有10000個國家，每個國家挑選若幹人（每個國家挑選的人數可以不一樣，例如a國家挑選了1000人，b國家挑選了10人，假設總共挑選了100萬人）進行混合分組，每個分組包含了若幹不同國家的人（每個分組每個國家僅限1人）。下面進行排隊，橫坐标為分組id，縱坐标為國家id。接下來要進行搬運遊戲，從左導遊，每個國家的人，需要将它手裡的球搬運給右邊的相同國家的人，如果他們相鄰，則不計成本。如果他們之間隔了其他分組，則計算成本（相隔的分組個數）。最終計算每個國家的搬運成本，某些國家的搬運成本，或者所有國家相加的總搬運成本。
如何降低總成本，如何降低某些國家的成本，如何降低某個國家的成本？
例如第一種排列方式，1号國家的搬運成本為2， 6号，7号國家的搬運成本為1，其他國家的搬運成本為0。
第二種排列方式如下，所有國家的搬運成本都為0。
這就是數組類型編排要取得的目的，由于數組類型通常是按數組的元素進行檢索的，是以我們需要根據元素來進行編排。數組類型的編排方式同樣适用于全文檢索類型，token類型。
其他類型的編排則根據資料類型來定，例如空間類型，可以根據geohash的值進行排序編排。
下面我們講一下數組類型編排的實作過程。
生成随機數組的方法
建立測試表，寫入随機數組
10條記錄，有多少種排列組合的可能呢？
postgresql有排列組合函數可以支援，如下。
排列組合，指行的排列順序。下面兩篇文檔中也涉及排列組合的例子。
<a href="https://github.com/digoal/blog/blob/master/201604/20160402_01.md">《postgresql n階乘計算, 排列組合計算 - 如何計算可變參數中有沒有重複參數》</a>
<a href="https://github.com/digoal/blog/blob/master/201704/20170410_02.md">《為什麼啤酒和紙尿褲最搭 - 用hybriddb/postgresql查詢商品營銷最佳組合》</a>
通過行号的順序，得到排列組合，驗證通過。
排列組合示例：
計算每一種排列組合，對應數組元素的聚合度（越靠近0(越小)，越聚合）
根據前面的聚合度算法，使用如下函數實作。
調用函數計算聚合度
選擇sum(affinity)最小的combo，就是最優的排列組合。将資料按這個順序調整，即可最大的優化性能。
資料編排是存儲層面的優化，是以存儲本身的屬性也決定了應該如何進行資料編排。
平面存儲，資料按順序在一個或多個平面上存儲，當從資料庫中順序搜尋一批資料時，在實體存儲層面也可能是相鄰的媒體。
是以前面提到的編排優化是非常有效的。
硬體特性是ssd或者3d存儲結構時，當從資料庫中順序搜尋一批資料時，在實體存儲層面也可能是相鄰的媒體，也可能不是，這個需要根據硬體廠商的寫特性。
前面的編排對硬體的優化效果可能就沒那麼好。編排算法應該充分考慮硬體的資料通路特性，才能達到最好的優化效果。
但是對記憶體的優化效果一定是有的。
從前面的例子來看，資料編排的方法會耗費大量的計算量，10條記錄就可能有300多萬種排列組合，使用cpu運算，計算每種組合的聚合度并不是最好的選擇。
對于此類編排聚合度的計算，視覺處理可能是更好的方法。
1、資料編排的目的和好處：讓資料更加緊湊，降低通路成本，節約記憶體。
2、編排應該考慮到多個方面：
資料的通路需求，比如是順序通路，還是随機通路，是通路等值資料，還是通路範文資料，是通路标量，還是通路多值類型、異構類型等。優化是需要針對通路需求的。
資料存儲的硬體特性，硬體是如何處理資料存儲和搜尋的。也決定了應該如何優化。
記憶體的硬體特性，同上。
軟硬體一體化。
3、postgresql不僅支援簡單的标量類型，還支援複雜的多值類型，例如array, range, json, hstore, gis, xml等。在資料編排優化層面更加的複雜。
一維類型的編排就好像隻需要完成魔方的一面
多元類型的編排需要完成所有面
随着多元類型元素的增加，記錄數的增加，編排難度也會呈指數上升
多元資料的編排，運算量非常龐大，使用gpu處理可能是一種更好的方法。
postgresql udf支援pl/cuda程式設計，可以很好的與gpu進行結合，提高計算能力。