150
多階魔方複原在數據優化中的應用
標簽
PostgreSQL , 元素分布 , 減少HEAP IO , 數據聚集重組
背景
前一篇文章介紹了一個場景，利用多列索引，多種索引接口（GIN\BTREE\BRIN...）以及PostgreSQL內置的bitmapAnd, bitmapOr等手段，提升廣告營銷實時搜索性能，同時兼顧開發工作量。
《懶人推動社會進步 - 多列聚合, gin與數據分布(選擇性)》
其中在講到GIN索引的優化時，留了一個懸念，到底如何通過調整數據分布，降低GIN索引掃描的IO放大，提高掃描效率？
3、gin數據分布優化
如果是普通類型，則線性相關越好，掃描或返回多條數據的效率越高。
如果是多值類型（如數組、全文檢索、TOKENs），則元素越集中（元素聚類分析，橫坐標為行號，縱坐標為元素值，數據分布越集中），效率越高。
元素集中通常不好實現，但是我們可以有集中方法來聚集數據，
1. 根據元素的出現頻率進行排序重組，當用戶搜索高頻詞時，掃描的塊更少，減少IO放大。
2. 根據（被搜索元素的次數*命中條數）的值進行排序，按排在最前的元素進行聚集，逐級聚集。
(以上方法可能比較燒腦，下次發一篇文檔專門講GIN的數據重組優化)
聚集有什麼用呢？如何聚集呢？
數據分布例子
例子
假設有6條記錄，每條記錄存儲了一些VALUE（數組），6條記錄方便演示。
圖形化如下
當搜索包含2的數據時，需要掃描第1,2條記錄。
當搜索包含1的數據時，需要掃描第1,3,5條記錄。（1,3,5離散分布，即現實中包含1的數據，很可能在不同數據塊中，那麼需要掃描更多的數據塊）。
接下來做一個簡單的存儲調整，將數據進行重排。
圖形化如下
很顯然，現在沒有離散的數據了，對同一個元素來說，更加的緊密相連，例如搜索包含1的數據時，他們是相鄰的記錄（現實中極有可能在同一個數據塊中）。
說到數據重分布，就涉及到聚集的問題了，如何讓同一個元素，盡量的靠在一起呢？
你需要了解一些數據科學計算的知識，可以參考一下:
真實情況下，幾乎不可能做到每一個元素的行都是緊密相鄰的，就像玩“不可複原的（有BUG的）”多階魔方。你怎麼轉，都不可能做到麵麵俱到。
我們隻能通過科學計算，盡可能的找到最終態較好的數據分布狀態。
最後更新：2017-06-13 02:32:17