433
多字段，任意組合條件查詢(0建模) - 毫秒級實時圈人 實踐
標簽
PostgreSQL , 數組 , GIN索引 , 任意字段組合查詢 , 圈人 , ToB分析型業務 , 建模
背景
你也許在一家ToB的數據分析公司，你可能設計了一張表（包括用戶標識，及若幹已經統計好的的屬性值），你也許收集了一些用戶的數據，你也許要為客戶提供報表，你也許需要為客戶提供任意屬性值的組合查詢，並快速的返回結果給用戶。
這些需求應該是非常常見的ToB的數據平台公司的形態，頭痛的問題無法建模，因為B端的需求無法捉摸，任意組合查詢、要求實時響應。
你的客戶數據也許有幾十億上百億，客戶數據也許有幾百個屬性，用戶可能需要的是任意屬性組合的結果。
如果要快速響應，你的第一反應是不是對查詢條件建立索引呢？
比如
where col1=? and col2=? and col3<>? or col4=?;
這樣的SQL，你準備怎麼做到實時響應呢？(col1,col2)建立索引，col4建立索引，這樣是嗎？
但是用戶下次的請求肯又換條件了
where col3=1 or col100=?
是不是又要建col3, col100的索引呢？
你會發現根本沒有辦法優化，因為對應查詢的索引組合可能是成千上萬的。
PostgreSQL 對付任意字段檢索的黑科技
我在之前寫過一些關於任意字段查詢的實踐文章，廣泛應用於廣告營銷平台的圈人，ToB的圈人，前端頁麵的任意組合篩選等場景。
方法1，GIN複合索引
對需要參與查詢的字段，建立GIN的複合索引。
CASE如下：
《任意組合字段等效查詢, 探探PostgreSQL多列展開式B樹 (GIN)》
這個場景針對任意字段匹配的場景，PostgreSQL對於多個查詢條件，內部會使用索引+bitmapAnd或bitmapOr來篩選BLOCK，得到中間結果。
+---------------------------------------------+
|100000000001000000010000000000000111100000000| bitmap 1
|000001000001000100010000000001000010000000010| bitmap 2
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
|000000000001000000010000000000000010000000000| Combined bitmap
+-----------+-------+--------------+----------+
| | |
v v v
Used to scan the heap only for matching pages:
+---------------------------------------------+
|___________X_______X______________X__________|
+---------------------------------------------+
這種方法為什麼快呢？
原因是GIN索引實現了內部bitmapAnd or bitmapOr，實際上等效於對每個字段建立單獨的B-Tree索引（PostgreSQL對多個B-Tree索引也支持bitmapAnd, bitmapOr的合並）。
bitmapand,or原理如下：
《PostgreSQL bitmapAnd, bitmapOr, bitmap index scan, bitmap heap scan》
GIN的複合索引這種方法可以滿足以上需求，但是，當數據量非常龐大或者列非常多時，GIN索引會比較大。
方法1 優化技巧
建議可以拆成多張表（例如隨機拆分，或者按強製條件拆分）。降低GIN索引的大小，同時還可以利用PostgreSQL 10的多表並行特性，提升查詢性能。
PostgreSQL並行計算特性
PostgreSQL支持單表多核並行，也支持多表的並行查詢
單表並行，指一條SQL，在處理單張表的數據時，可以使用多個CPU進行運算。
多表並行，指的是一條SQL涉及到多張表的處理（例如APPEND SCAN）時，可以並行的處理多個表的SCAN。
多表並行是在PG 10版本加入的，PostgreSQL 10 append scan 並行
《PostgreSQL 10.0 preview sharding增強 - 支持Append節點並行》
方法2，行級全文檢索
將整行記錄轉換為一個大大的字符串，然後對整行記錄建立全文索引（PostgreSQL內置了全文索引的功能），搜索時即覆蓋了任意字段任意匹配的場景。
《PostgreSQL 如何高效解決 按任意字段分詞檢索的問題 - case 1》
此方法適用於不限定列，但是限定查詢條件的場景。
比如搜索 迪奧香水 ， 可以在表的任意字段匹配，（例如 店鋪名字、商品名字、用戶名字）。
方法3，bloom過濾
bloom方法過濾的效果有限，目前算是一種預覽特性，建議觀察使用。
《PostgreSQL 9.6 黑科技 bloom 算法索引，一個索引支撐任意列組合查詢》
方法4，數組化（同類應用 1 - 電商圈人）
每個用戶對應若幹個標簽，商家根據標簽的組合篩選人群。這是廣告商的慣用手法。
主要利用了PostgreSQL的數組類型、倒排索引，性能也是杠杠的。
《萬億級營銷(圈人)瀟灑的邁入毫秒時代 - 萬億user_tags級實時推薦係統數據庫設計》
這種方法為什麼快呢？
它采用了ARRAY元素倒排的方法，在查詢時，對查詢條件進行塊級BITMAP篩選，篩選後的數據落到少量的數據塊，再進行recheck選出最終結果。
本案例（多字段，任意組合條件 毫秒級實時圈人） 方法4 實踐
實際上文章開頭提到的場景，和電商圈人非常相似，所以也能使用電商圈人的方法。
怎麼實現呢？
1 多個字段轉換為數組
首先，將多個字段，轉換為一個數組字段。
例如
create table test(uid int8 primary key, tag1 int, tag2 text, tag3 int, tag4 text, tag5 timestamp, tag6 date, ...);
轉換為
create table test(uid int8 primary key, tag text[]);
例子
1, 1, 'man', 1023, 'football', '2017-01-01 10:00:00', '1989-09-01'
轉換為
1, array['tag1:1', 'tag2:man', 'tag3:1023', 'tag4:football', 'tag5:...', tag6:...']
2 階梯化（可選）
如果查詢中包含 =， <> 以外的查詢（如某些字段為年齡、銷售額、收入等，那麼可能有大於，小於的範圍查詢需求），那麼我們需要階梯化對應TAG的VALUE，階梯化的方法請參考
《恭迎萬億級營銷(圈人)瀟灑的邁入毫秒時代 - 萬億user_tags級實時推薦係統數據庫設計》
3 拆表（可選）
拆表的目的是並行，保持每個表的體量。
拆表的方法很多，可以隨機，可以按UID進行哈希。
拆表後，掃描所有的分區表，聚合結果即可。
拆表可以是本地拆分、也可以是跨庫拆分。本地拆分，實際上就是分區表。跨庫拆分則涉及到數據分發、聚合的過程。
跨庫分發和聚合的方法也很多：例如postgres_fdw+pg_pathman, plproxy, 程序實現等方法。請參考如下文檔
《PostgreSQL 9.6 sharding based on FDW & pg_pathman》
《PostgreSQL 最佳實踐 - 水平分庫(基於plproxy)》
《阿裏雲ApsaraDB RDS for PostgreSQL 最佳實踐 - 2 教你RDS PG的水平分庫》
《阿裏雲ApsaraDB RDS for PostgreSQL 最佳實踐 - 3 水平分庫 vs 單機 性能》
《阿裏雲ApsaraDB RDS for PostgreSQL 最佳實踐 - 4 水平分庫 之 節點擴展》
4 建立數組GIN索引
對數組字段建立GIN索引，建立GIN索引實際上就是倒排索引，數組元素作為KEY，行號作為VALUE的B樹。
例如搜索包含某個TAG的用戶，從GIN索引得到HEAP表行號，然後獲取記錄即可，速度非常快。
多個TAG組合查詢時，內部進行BITMAP and/or的合並，過濾到數據塊級別，然後通過數據塊獲取記錄，通過查詢條件FILTER，得到最終結果，速度也非常快。
關於GIN，多個TAG組合查詢的原理，可以參考這篇文檔。
《電商內容去重\內容篩選應用(實時識別轉載\盜圖\侵權?) - 文本、圖片集、商品集、數組相似判定的優化和索引技術》
5 圈人 <=> 數組組合查詢
將多個字段數組化後，圈人就變成了數組的操作，例如
where tag1=? and tag2=? or tag3=?
轉換為數組操作如下：
where arraycol @> array[tag1:?, tag2:?] or arraycol && [tag3:?]
數組查詢會走GIN索引掃描，速度快得驚人。
方法5，bitmap化（同類應用 2 - 圈人(基於阿裏雲 RDS PostgreSQL varbitx)）
這個用到的是bit的方法，當所有屬性的VALUE可以被窮舉時，例如可以窮舉到100萬或者多少，那麼我們可以使用這樣的方法來優化圈人的應用。
BIT相比數組的方法，BIT空間下降25倍左右，性能穩定。
但是BIT方法要求數據的寫入是合並式的，最好使用UDF完成，實際案例如下（包含數據合並的DEMO代碼）。
《阿裏雲RDS for PostgreSQL varbitx插件與實時畫像應用場景介紹》
《基於 阿裏雲 RDS PostgreSQL 打造實時用戶畫像推薦係統》
varbitx這種方法與bitmap數據庫pilosa如出一轍，但是PG有更強大的功能背景，推薦使用PG。
https://www.pilosa.com/docs/introduction/
小結
在PostgreSQL中，圈人業務場景的優化方法非常多，得益於PostgreSQL強大的功能。下麵小結一下每一種方法，
1. gin 複合索引，對需要參與查詢的列，構建GIN複合索引即可。PostgreSQL內部會對GIN的多個條件使用bitmapAnd, bitmapOr進行合並。
這種方法的使用最為簡便，但是當數據量或列非常多時，GIN索引會很大，GIN索引很大帶來一個問題，建立索引的速度較慢，將來維護索引的速度也較慢。
使用這種方法，建議對表進行本地分區、或者垮庫分區，將單表的數據量降低。(多列展開後的記錄數建議在1億左右，例如10列，則單表記錄數控製在1000萬)（經驗值，隨著硬件發展，以後可能更多）
同時GIN建議使用fastupdate和延遲合並的特性，加速插入、刪除、更新操作。
2. 獨立B-tree索引，需要參與查詢的列，每列單獨建立B-Tree索引(或者對應類型的其他索引例如brin, gin, gist, sp-gist, hash)，PostgreSQL內部會對多個索引查詢的結果使用bitmapAnd, bitmapOr進行合並。
這種方法使用也非常便捷，使用這種方法，建議對表進行本地分區、或者垮庫分區，將單表的數據量降低。單表記錄數建議控製在1億左右（經驗值，隨著硬件發展，以後可能更多）。
3. 數組化+GIN，類似與電商的圈人場景，查詢時使用數組的包含，相交操作符，實現索引檢索。
這種方法特別適合於已經構建好標簽（使用PostgreSQL數組）的場景，直接使用數組索引、數組的操作即可實現圈人。
萬億user_tags級，毫秒響應。
《恭迎萬億級營銷(圈人)瀟灑的邁入毫秒時代 - 萬億user_tags級實時推薦係統數據庫設計》
4. bit化，當標簽可以窮舉時，可以將標簽作為KEY，將USERID作為bit進行存儲，使用BIT的方法相比ARRAY，空間需求下降25倍，效率可以保持平穩。
這種方法將用戶和標簽做了一次倒轉，好處很明顯，支持任意組合的高效圈人。但是比較燒腦，也需要更多的開發工作量（這部分已經有UDF DEMO）。
建議
1. 省錢、高效、不怕燒腦
bit化。
2. 有錢、高效、能折騰
數組化+GIN
3. 有錢、高效、不能折騰
獨立B-Tree， GIN複合索引
最後更新：2017-06-08 11:32:06