PostgreSQL 圖式搜尋(graph search)實踐 - 百億級圖譜，毫秒響應

PostgreSQL , CTE , 遞歸查詢 , cycle , depth , loop , deep , level , 層級 , array , row array , JSON

圖式搜尋是PostgreSQL在（包括流計算、全文檢索、圖式搜尋、K-V存儲、圖像搜尋、指紋搜尋、空間資料、時序資料、推薦等）諸多特性中的一個。

采用CTE文法，可以很友善的實作圖式搜尋（N度搜尋、最短路徑、點、邊屬性等）。

其中圖式搜尋中的：層級深度，是否循環，路徑，都是可表述的。

<a href="https://github.com/digoal/blog/blob/master/201801/20180102_04_pic_001.png" target="_blank"></a>

<a href="https://github.com/digoal/blog/blob/master/201801/20180102_04_pic_002.jpg" target="_blank"></a>

建立1000萬使用者，每5萬作為一個有牽連的群體，平均每個使用者牽連500個使用者，形成50億的大規模關系網。

在此基礎上，示範如下

1、如何實作N度搜尋，邊的屬性檢視，以及最短路徑搜尋等需求。

2、如何去除循環點，如何控制深度，如何展示路徑等。

3、如何生成繪圖資料。

1、建表，表結構如下，可以描述點、邊。

2、生成測試資料：

3、資料約340GB

1、當路徑中重複出現某個點時，說明發生了循環。

2、每遞歸一次，深度加1。

SQL如下：

N度搜尋，如上SQL，輸入sg.depth &lt;= N。

例如，搜尋ROOT=31208的三度資料。

去掉搜尋深度，并且在查詢遞歸表的語句中，加上WHERE條件（過濾C2）以及LIMIT 1 即可。

例如搜尋 1 到 100 的最短路徑。

如果要控制深度，比如5度以内搜不到就不搜了，把搜尋深度的條件再加進去即可。

為了提高響應速度，使用遊标傳回。

響應時間飛快，毫秒級響應。

層級越深，傳回的記錄就越多，而實際上在圖搜尋中，并不需要傳回每個層級的所有記錄，（例如隻傳回相關性較高的前N條，或者是滿足權重大于多少的，前N條），進而控制每個層級的記錄數。

例如，搜尋root=31208的3度資料，同時限制每個層級傳回100條。

響應速度3.2毫秒。(理由很簡單，因為每一個層級都是索引命中，結合PG的cluster特性(按c1排序存儲)，可以降低塊數，再次提高性能)

壓測，TPS：1.2萬，平均響應時間5.2毫秒。

将冗長的SQL封裝成UDF，可以簡化應用調用的接口。

使用舉例：

使用舉例，

使用PostgreSQL的CTE文法，可以非常友善的實作圖式搜尋的需求，包括N度搜尋、最短路徑搜尋，路徑、點、邊屬性(邊的屬性使用JSON存儲，友善架構設計。)展示，層級深度控制和展示，控制每一層的傳回數，控制每一層的傳回順序和權重等 等）。

性能方面，PG 10 ON ECS的環境，50億的點邊網絡，N度搜尋、最短路徑搜尋，響應時間都在毫秒級（其中3度搜尋，每層100條限制，僅2.1毫秒，TPS達到1.2萬）。

以上查詢，可以封裝成PostgreSQL的plpgsql UDF接口，便于業務調用（暴露一些輸入條件即可）。

<a href="https://github.com/digoal/blog/blob/master/201612/20161213_01.md">《金融風控、公安刑偵、社會關系、人脈分析等需求分析與資料庫實作 - PostgreSQL圖資料庫場景應用》</a>

<a href="https://www.postgresql.org/docs/10/static/queries-with.html">https://www.postgresql.org/docs/10/static/queries-with.html</a>