在現實生活中，人們的各種社會活動，會産生很多的行為資料，比如購物、刷卡、打電話、開房、吃飯、玩遊戲、逛網站、聊天 等等。
如果可以把它當成一個虛拟現實（ar）的遊戲，我們所有的行為都被記錄下來了。
又比如，某些應用軟體，在征得你的同意的情況下，可能會記錄你的手機行為、你的運動軌迹等等，這些資料可能會不停的上報到業務資料庫中，每條記錄也許代表某個人的某一次行為。
全球人口非常多，每個人每時每刻都在産生行為資料的話，對于單個人的資料來說，他産生的第一條行為和他産生的第二條行為資料中間可能被其他使用者的資料擠進來（如果是堆表存儲的話，就意味着這兩條資料不在一起，可能相隔好多條記錄）。
除了我們常說的群體分析（大資料分析）以外，還涉及到微觀查詢。
比如最近很火的《三生三世十裡桃花》，天族也許會對翼族的首領（比如玄女）進行監控，微觀查詢他的所有軌迹。
又或者神盾局，對某些人物行為軌迹的明細跟蹤和查詢
為了提升資料的入庫速度，通常我們會使用堆表存儲，堆表存儲的最大特點是寫入極其之快，通常一台普通伺服器能做到gb/s的寫入速度，但是，如果你要頻繁根據使用者id查詢他産生的軌迹資料的話，會涉及大量的離散io。查詢性能也許就不如寫入性能了。
1. 聚集存儲
比如按照使用者id來聚集存儲，把每個人的資料按照他個人産生資料的順序進行聚集存儲（指實體媒體），那麼在根據使用者id進行查詢時（比如一次查詢出某人在某個時間段的所有行為，假設有1萬條記錄，那麼聚集前也許要掃描10000個資料塊，而聚集後也許隻需要掃描幾十個資料塊）。
2. 行列變換
将軌迹資料根據使用者id進行聚合，存入單行，比如某人每天産生1萬條軌迹資料，每天的軌迹資料聚合為一條。
聚合為一條後，掃描的資料塊可以明顯減少，提升按聚集key查詢的效率。
3. index only scan
将資料按key組織為b數，但是b樹葉子節點的相鄰節點并不一定是實體相鄰的，它們實際上是通過連結清單連接配接的，是以即使是index only scan，也不能保證不産生離散io，反而基本上都是離散io。隻是掃描的資料塊總數變少了。
是以這個場景，index only scan并不是個好主意哦。
對于以上三種方法，任何一種都隻能針對固定的key進行資料組織，是以，如果你的查詢不僅僅局限于使用者id，比如還有店鋪id，商品id等其他軌迹查詢次元，那麼一份資料不可避免的也會産生離散io。
此時，你可以使用存儲換時間，即每個查詢次元，各備援一份資料，每份資料選擇對應的聚集列（比如三份備援資料，分别對應聚集列：使用者id、商品id、店鋪id）。
postgresql 的表使用的是堆存儲，插入時根據fsm和空間搜尋算法尋找合适的資料塊，記錄插入到哪個資料塊是不受控制的。
對于資料追加型的場景，表的資料檔案會不斷擴大，在檔案末尾擴充資料塊來擴充存儲空間。
fsm算法參考
src/backend/storage/freespace/readme
那麼如何讓postgresql按照指定key聚集存儲呢，postgresql 提供了一個sql文法cluster，可以讓表按照指定索引的順序存儲。
ps，這種方法是一次性的，并不是實時的。
這種方法很适用于行為、軌迹資料，為什麼這麼說呢？
首先這種資料有時間次元，另一方面這種資料通常有被跟蹤對象的唯一辨別，例如使用者id，這個辨別即後期的查詢key。
我們可以對這類資料按被跟蹤對象的唯一辨別hash後分片，打散到多個資料庫或分區表。
同時在每個分區表，再按時間次元進行二級分區，比如按小時分區。
每個小時對前一個小時的資料使用cluster，對堆表按被跟蹤對象的唯一辨別進行聚集處理。
查詢時，按被跟蹤對象的唯一辨別+時間範圍進行檢索，掃描的資料塊就非常少（除了目前沒有聚集處理的資料）。
這種方法即能保證資料插入的高效，也能保證軌迹查詢的高效。
我們通常所認知的除了btree，hash索引，還有一種塊級索引brin，是針對聚集資料（流式資料、值與實體存儲線性相關）的一種輕量級索引。
比如每連續的128個資料塊，計算它們的統計資訊（邊界值、最大、最小值、count、sum、null值個數等）。
這種索引非常小，查詢性能也非常高。
有幾篇文檔介紹brin
<a href="../201604/20160414_01.md">《postgresql 物聯網黑科技 - 瘦身幾百倍的索引(brin index)》</a>
<a href="../201505/20150526_01.md">《postgresql 9.5 new feature - lets brin be used with r-tree-like indexing strategies for “inclusion” opclasses》</a>
<a href="../201504/20150419_01.md">《postgresql 9.5 new feature - brin (block range index) index》</a>
除了聚集存儲，還有一種提升軌迹查詢效率的方法。行列變換。
比如每個被跟蹤對象，一天産生1萬條記錄，将這1萬條資料聚合為一條。查詢時效率也非常高。
但是問題來了，這種方法不适合除了時間條件以外，還有其他查詢條件的場景。譬如某個使用者某個時間段内，在某個場所（這個是新增條件）的消費記錄。
這顯然需要一個新的索引來降低資料掃描。
排除這個需求，如果你隻有被跟蹤id+時間 兩個次元的查詢需求，那麼使用行列變換不失為一種好方法。
postgresql支援多種資料類型，包括 表類型，複合類型，數組、hstore、json。
表類型 - 在建立表時，自動被建立，指與表結構一緻的資料類型。
複合類型 - 使用者可以根據需要自己定義，比如定義一個複數類型 create type cmp as (c1 float8, c2 float8);
數組 - 基于基本類型的一維或者多元數組，表類型也支援數組，可用于行列變換，将多條記錄存儲為一個數組。
hstore - key-value類型，可以有多個kv組。
json - 無需多言。
行列變換後，我們留幾個字段：
被跟蹤id，時間段（時間範圍類型tsrange），合并字段（表數組、hstore、json都可以）
同一份資料，測試離散、聚集、行列變換後的性能。
1. 構造1萬個id，每個id一萬條記錄，總共1億記錄，全離散存儲。
2. 建立btree索引
3. 通過查詢實體行号、記錄，确認離散度
4. 軌迹查詢執行計劃，使用最優查詢計劃
5. 測試查詢性能qps、吞吐
6. top
使用 cluster test using (idx_test_id); 即可将test表轉換為以id字段聚集存儲。但是為了測試友善，我還是建立了2張聚集表。
1. 同一份資料，按照id聚集存儲，并建立btree索引。
2. 索引大小、軌迹查詢執行計劃、查詢效率
3. 通過查詢實體行号、記錄，确認已按id聚集存儲
4. 測試查詢性能qps、吞吐
5. top
1. 同一份資料，按照id聚集存儲，并建立brin索引。
bitmapscan 隐含了ctid sort，是以啟動時間就耗費了7.4毫秒。
如果brin未來支援index scan，而非bitmapscan，可以壓縮這部分時間，批量查詢效率達到和精确索引btree不相上下。
掃描的資料塊數量比非聚集存儲少了很多。
1. 同一份資料，按照id聚合為單行數組的存儲。
其他還可以選擇jsonb , hstore。
3. 行列變換後的資料舉例
top可以看出，test 表 array 存儲的效率并不高，你也許可以嘗試一下json或者hstore，可能更好。
試試jsonb
存儲格式
按key查詢軌迹 tps
輸出吞吐
cpu使用率
索引大小
表大小
離散存儲
1155
1155 萬行/s
99.8%
2.1 gb
7.3 gb
聚集存儲 btree索引
1840
1840 萬行/s
聚集存儲 brin索引
232 kb
行列變換 array
660
660 行/s
248 kb
4.5 gb
行列變換 jsonb
1255
1255 行/s
聚集存儲後，我們看到，按聚集列搜尋資料時，需要掃描的資料塊更少了，查詢效率明顯提升。
對于聚集列，不需要建立btree精确索引，使用brin索引就可以滿足高性能的查詢需求。節約了大量的空間，同時提升了資料的寫入效率。
聚集存儲還可以解決另一個問題，比如潛在的寬表需求（例如超過1萬個列的寬表，通過多行來表示，甚至每行的資料結構都可以不一樣，例如通過某個字段作為行頭，來表示行的資料結構）。
在核心層面實作聚集存儲，而不是通過cluster來實作。
資料插入就不能随便找個有足夠剩餘空間的page了，需要根據插入的聚集列的值，找到對應的page進行插入。
是以它可能依賴一顆以被跟蹤對象id為key的b樹，修改對應的fsm算法，在插入時，找到對應id的page。
不過随着資料的不斷寫入，很難保證單個id的所有值都在連續的實體空間中。總會有碎片存在的。
還有一點，如果采樣預配置設定的方式，一些不活躍的id，可能會浪費一些最小單元的空間（比如最小單元是1page)。
按key聚集存儲解決了按key查詢大量資料的io放大（由于離散存儲）問題，例如軌迹查詢，微觀查詢。
對于postgresql使用者來說，目前，你可以選擇行列變換，或者異步聚集存儲的方式來達到同樣的目的。
行列變換，你可以使用表級數組，或者jsonb來存儲聚集後的記錄，從效率來看jsonb更高，而值得優化的有兩處代碼pglz_decompress, escape_json。
對于異步聚集，你可以選擇聚集key，分區key（通常是時間）。異步的将上一個時間段的分區，按key進行聚合。
postgresql 聚集表的聚集key，你可以選擇brin索引，在幾乎不失查詢效率的同時，解決大量的存儲空間。
不管使用哪種方式，一張表隻能使用一種聚集key(s)，如果有多個聚集次元的查詢需求，為了達到最高的查詢效率，你可存儲多份備援資料，每份備援資料采用不同的聚集key。
将來，postgresql可能會在核心層面直接實作聚集存儲的選項。你也許隻需要輸入聚集key，最小存儲粒度、等參數，就可以将表建立為聚集表。
将來，postgresql brin索引可能會支援index scan，而不是目前僅有的bitmap scan。
<a href="../201612/20161216_01.md">《分析加速引擎黑科技 - llvm、列存、多核并行、算子複用 大聯姻 - 一起來開啟postgresql的百寶箱》</a>