聊聊簡單又不簡單的圖上多跳過濾查詢

来源:https://www.cnblogs.com/huaweiyun/archive/2023/04/13/17315014.html
-Advertisement-
Play Games

摘要：多跳查詢能力也是一個衡量產品性能非常重要的指標。 本文分享自華為雲社區《聊聊超級快的圖上多跳過濾查詢》，作者：弓乙。 在圖資料庫/圖計算領域，多跳查詢是一個非常常用的查詢，通常來說以下類型的查詢都可以算作是多跳過濾查詢： 1.查詢某個用戶的朋友認識的朋友 --二跳指定點label的查詢 2.查 ...


摘要：多跳查詢能力也是一個衡量產品性能非常重要的指標。

本文分享自華為雲社區《聊聊超級快的圖上多跳過濾查詢》，作者：弓乙。

在圖資料庫/圖計算領域，多跳查詢是一個非常常用的查詢，通常來說以下類型的查詢都可以算作是多跳過濾查詢：

1.查詢某個用戶的朋友認識的朋友 --二跳指定點label的查詢
2.查詢某個公司的上下游對外投資關係 --N跳指定方向過濾查詢
3.查詢某個公司實際持股股東 --N跳內帶過濾查詢
4.搜索可提供某個零部件的供貨商 --N跳內帶過濾的until查詢
5.局點變更影響分析 --N跳內帶過濾查詢

如下圖，可用3跳查詢得到網訊公司A所有的對外投資機構。

與此同時，多跳查詢能力也是一個衡量產品性能非常重要的指標，比如LDBC（Linked Data Benchmark Council）的互動式查詢場景下就設計了多個考察圖資料庫系統多跳查詢能力的測試用例，互動式查詢Interactive的Complex Query中有多個用例均為多跳查詢，如下圖是一個查朋友最近發送的消息的IC2用例，是一個經典的圖上2-hop查詢。

在圖計算的尺度里，多跳過濾某些情況下被稱為k-hop演算法，BFS,DFS演算法，區別僅在於traversal的策略是深度優先還是廣度優先。

而在圖資料庫中一般將多跳過濾看做是需要特殊優化的模式匹配查詢(cypher)或可組合的複合查詢(gremlin)。

以下展示常用的圖查詢語言gremlin/cypher的二跳查詢的寫法，結果均為返回李雷朋友的朋友：

gremlin: g.V('李雷').out('朋友').out('朋友')

 

cypher: match (n)-->(m1:朋友)-->(s1)-->(m2:朋友)-->(s2) where id(n)='李雷' return s2

這兩個語句輕盈又直觀，看起來一切都被解決地如此優雅。

但事實真的如此嗎？

很遺憾，當我們興緻勃勃地構圖，將數據導入圖數據，再使用類似上述語句查詢實際業務場景時，你也許會驚訝地發現，也許結果與我們所期待的並不一致。

接下來，我將展開說說為什麼使用多跳過濾查詢會比我們想象中的更複雜，瞭解了圖上遍歷的概念後，我們能把而基於多跳過濾這一特性，我們又能怎麼做使得這個重要的查詢又快又流程呢？

功能那些事兒

上面我們介紹了查詢一個用戶朋友的朋友的例子，這裡我們假設業務場景是向李雷推薦好友，思路是：向他推薦其好友的好友，但是推薦的好友中不應包含李雷本身的好友，比如圖中小明同時是李雷的一跳好友和二跳好友。這時我們不應向李雷推薦小明，因為她已經是李雷的好友了。

僅僅增加了一個返回的二跳鄰居不包含一跳鄰居這個條件，讓我們來看下與上面單純的2跳查詢的gremlin和cypher變成什麼樣了？

gremlin: 
g.V("李雷").repeat(out("朋友").simplePath().where(without('1hop')).store('1hop')).
times(2)

 

cypher: 
match (a)-[:朋友]->(d) where id(a)='李雷' with a, collect(d) as neighbor
match (a)-[:朋友]-(b)-[:friend]-(c)
where not (c in neighbor)
return c

不知道各位有什麼感覺？如果是不熟悉圖查詢語言的朋友們看到這裡一定兩眼發黑了吧哈哈。

不用擔心，如果我們靈活使用一些特性，也許事情會變得簡單，比如這是一個GES原生API多跳過濾查詢Path Query的json請求：

{
 "repeat": [{"operator": "outV"}],
 "times": 2,
 "vertices": ["李雷"],
 "strategy":"ShortestPath"
}

假如我們可以把它翻譯為gremlin的寫法的話，它大概是：

g.V('李雷').repeat(out()).times(2).strategy('ShortestPath')

以上的寫法除了strategy('ShortestPath')其他本身就是gremlin已經支持的語法，意為-查詢從李雷出發以ShortestPath為遍歷策略的二跳鄰居。

遍歷策略是什麼？

理解遍歷策略是瞭解多跳過濾的基石，我們這裡從圖論里幾個定義展開：

A walk is a finite or infinite sequence of edges which joins a sequence of vertices.[2]
Let G = (V, E, ϕ) be a graph. A finite walk is a sequence of edges (e1, e2, …, en − 1) for which there is a sequence of vertices (v1, v2, …, vn) such that ϕ(ei) = {vi, vi + 1} for i = 1, 2, …, n − 1. (v1, v2, …, vn) is the vertex sequence of the walk. The walk is closed if v1 = vn, and it is open otherwise. An infinite walk is a sequence of edges of the same type described here, but with no first or last vertex, and a semi-infinite walk (or ray) has a first vertex but no last vertex.
A trail is a walk in which all edges are distinct.[2]
A path is a trail in which all vertices (and therefore also all edges) are distinct

以上應用wiki中對於圖上不同的點集組成的邊集說明，詳情見Path (graph theory) - Wikipedia。

以下，我將幾個相似又不同的概念用四個維度區分開。

以上5個概念均指代在G=(V,E,φ)中，由點V,邊E組成的序列。

上圖中，對於序列a->c->d->f，我們可以將它稱為walk, trail, path，三者都可以。因為該序列的起點a與終點f不同，不屬於對序列要求close狀態circuit和cycle。

而序列a->c->a->c, 我們只能將其歸為walk。因為其不閉合不屬於circuit和cycle，且點有重覆(a,c兩個都有重覆)不屬於path，邊集有重覆(a->c的邊有重覆)不屬於trail。

遍歷策略對最終的結果和遍歷效率都有決定性的影響。

這裡簡單說明下新增的shortestPath策略：

  • Walk：以圖論中劃定的walk進行圖遍歷：即在traversal的過程中允許經過重覆的點和重覆的邊。
  • ShortestPath：以shortestPath的規則進行圖遍歷：即在BFS traversal的過程不會遍歷在前面跳數出現過的點。在這種模式下的路徑每個終點到起點都是最短路徑。

BFS與DFS

影響遍歷順序的另一個角度一般我們分為：

  • BFS - Breadth-first search 廣度優先搜索
  • DFS - Depth-first search 深度優先搜索

BFS在圖遍歷時會優先遍歷一個點的所有鄰居，再遍歷其鄰居的鄰居，而DFS會優先遍歷點的鄰居的鄰居，直到到達最深的節點。

我們可以設置一個batchSize，表示在進行BFS時不遍歷全部的鄰居，而是每層以batchSize的數量進行遍歷，然後再以batchSize的個數遍歷下一層鄰居。

可以推斷出，當batchSize=1時，該BFS約等於DFS的遍歷策略。

性能那些事兒

多跳過濾的性能受很多因素影響。以下總結一些會影響到性能的因素以供參考：

而對於不同規模的圖，多跳過濾查詢的TPS大部分情況下並不取決於圖的點邊規模，而是與圖的密度密切相關。

比如一個二跳查詢，那麼TPS就與該圖的二跳鄰居分佈強相關。

簡單來講，多跳過濾最終的性能主要受遍歷過程中觸達節點的個數影響。同樣規模的圖，其多跳過濾tps可能相差很大。大部分情況下基準測試僅提供橫向比較，考驗的是圖資料庫/圖引擎本身的性能指標，有一定參考價值，但仍以實際業務圖表現為主。

經驗上，稀疏的圖性能表現大大好於稠密的圖。

多跳查詢的使用

為了簡化多跳過濾查詢的表達，我們用一些參數來表達查詢過程。如前面章節介紹過的遍歷策略，batchSize等。

本章我們將一一介紹以下特性參數：

接下來我們以GES的path query（filterquery version2版本）介面來舉例介紹多跳過濾查詢的使用。

該介面支持對多跳過濾查詢，迴圈執行遍歷查詢進行加速。可以看做是gremlin的repeat語句的擴充表達，例如以下gremlin語句：

g.V('1','2').repeat(out()).times(2).emit().dedup()

以下為該介面的2跳/3跳查詢在1億規模圖上的測試情況。

其中，

  • filterV2 - GES的多跳過程查詢原生介面，該API性能最佳，TPS與延遲表現優異。
  • Cypher - GES的cypher查詢(較老版本)。
  • Neo4j - Neo4j community 4.2.3版本cypher。
  • gremlin - GES的gremlin，未在圖中體現，實際性能最差，故未做對比。

請求樣例1

POST /ges/v1.0/{projectId}/graphs/{graphName}/action?action_id=path-query
{
"repeat": [{"operator": "outV"}
],
"emit": true,
"times": 2,
"vertices": [
 "1","2"
]
}

以上請求等價於gremlin語句：

g.V('1','2').repeat(out()).times(2).emit().dedup()####

特性參數簡要說明

速查參數表

filterV2的參數過於複雜，需要花一定的時間去理解？請看下麵總結出的速查表，幫助您快速使用repeat模式：

PS：strategy策略的說明查看下方

emit模式

emit是一個filtered query參數中對其他各個參數影響最大的參數。我們將其定義為，是否輸出query過程中的點，其含義也與gremlin中的emit一致。

下麵將介紹，在不同模式下emit的表現形式：

上圖中，假定我們從點a出發，執行filtered khop query的查詢。

strategy

圖遍歷過程中使用的策略，目前可選：ShortestPath和Walk。

  • Walk：以圖論中劃定的walk進行圖遍歷：即在traversal的過程中允許經過重覆的點和重覆的邊。
  • ShortestPath：以shortestPath的規則進行圖遍歷：即在BFS traversal的過程不會遍歷在前面跳數出現過的點。在這種模式下的路徑每個終點到起點都是最短路徑。

上圖中，假定我們從點a出發，執行query的4跳查詢。

Walk: a->c->a->b, a->c->a->c, a->c->d->f, a->c->d->c

ShortestPath: a->c->d->f

簡單查詢

1. 查詢從a出發的第三跳鄰居

使用gremlin查詢：

g.V('a').out().out().out()
g.V('a').repeat(out()).times(3)

以上兩種寫法是等效的，結果為點f。路徑為a->c->d->f。

對應在API參數為：

{
 "repeat": [
 {
 "operator": "outV"
 }
 ],
 "emit": false,
 "times": 3,
 "vertices": [
 "a"
 ]
}

2. 查詢從a出發的三跳內鄰居

使用gremlin查詢：

g.V('a').repeat(out()).times(3).emit()

結果為b,c,d,e,f。

對應在API參數為：

{
 "repeat": [
 {
 "operator": "outV"
 }
 ],
 "emit": true,
 "times": 3,
 "vertices": [
 "a"
 ]
}

組合模式說明

emit+strategy

1. 查詢第三跳鄰居

在上面的圖中，如果按照[簡單查詢1](#1. 查詢從a出發的第三跳鄰居), 將得到點f, c, b。

路徑為a->c->a->b, a->c->d->f, a->c->d->c。

如果，我們只想得到f, 而不希望取到前兩跳已經出現過的點c和b。則需要使用strategy模式中的ShortestPath。ShortestPath模式保證API在traversal的過程中起始點到各點是最短路徑。該模式能夠有效降低多跳查詢中指數增長的查詢量。

gremlin的寫法為：

g.V("a").repeat(out().simplePath().where(without('hops')).store('hops')).times(3).path()

結果為僅為a->c->d->f。

對應在API參數為：

{
 "repeat": [
 {
 "operator": "outV"
 }
 ],
 "emit": false,
 "strategy": "ShortestPath",
 "times": 3,
 "vertices": [
 "a"
 ]
}

emit+until

1.提前終止traversal模式說明

我們以上面的圖來說明該模式，當我們不清楚查詢需要經過多少跳，但希望通過某些條件提前終止遍歷，可以用到until。

如以下兩個問題：

1.得到從a出發N跳內label=book的點。
2.得到從a出發N跳內所有點，停止查詢的條件為遇到label=book的點。

以上問題可以配合emit參數來解決，用gremlin可以寫為：

Q1: g.V('a').repeat(out()).until(hasLabel('book'))
Q2: g.V('a').repeat(out()).until(hasLabel('book')).emit()

與之對應的API為：

{
 "repeat": [
 {
 "operator": "outV"
 }
 ],
 "until": [
 {
 "vertex_filter": {
 "property_filter": {
 "leftvalue": {
            “label_name": ""
 },
 "predicate": "=",
 "rightvalue": {
 "value": "book"
 }
 }
 }
 }
 ],
 "emit": false/true,//這裡根據Q1,Q2的情況選擇emit的值。
 "times": 5,
 "vertices": [
 "a"
 ],
 "strategy": "Walk"
}

repeat模式說明

repeat+times

可通過參數repeat+times實現多種形式的多跳過濾及repeat模式過濾。

1.僅多跳過濾

gremlin的寫法為：

g.V("a").repeat(out().in()).times()
或
g.V("a").out().in()

對應在API參數為：

{
 "repeat": [
 {
 "operator": "outV"
 },
 {
 "operator": "inV"
 }
 ],
 "strategy": "Walk",
 "times": 2,
 "vertices": [
 "a"
 ]
}

2.repeat mode

假如我們從點a出發，查詢其帶方向的四跳鄰居。即：

gremlin的寫法為：

g.V('a').repeat(out('user').out().has('age',18)).times(2)
或
g.V('a').out('user').out().has('age',18).out('user').out().has('age',18)

對應在API參數為：

{
 "repeat": [
 {
 "operator": "outV",
 "edge_filter": {
 "property_filter": {
 "leftvalue": {
 "label_name": ""
 },
 "predicate": "=",
 "rightvalue": {
 "value": "user"
 }
 }
 }
 },
 {
 "operator": "outV",
 "vertex_filter": {
 "property_filter": {
 "property_name": {
 "label_name": "age"
 },
 "predicate": "=",
 "rightvalue": {
 "value": "18"
 }
 }
 }
 }
 ],
 "times": 4,
 "emit": false,
 "vertices": [
 "a"
 ]
}

by模式說明

by模式當前支持兩種形式：

  • select+by mode
  • by mode

by mode

該模式可針對輸出的點進行輸出格式上的過濾，返回的格式形如：

{
 "data": {
 "vertices": [
 {
 "id": "47",
 "label": "user"
 },
 {
 "id": "51",
 "label": "user"
 }
 ]
 }
}

例如針對二跳鄰居，我們可以通過參數by對id，label，property進行過濾：

g.V("a").repeat(out()).times(2).by(id())

轉化為filtered query V2的形式為：

{
 "repeat": [
 {
 "operator": "outV"
 }
 ],
 "times": 2,
 "vertices": [
 "a"
 ],
 "by": [{"id": true}]
}

select + by mode

該模式可任意選擇traverse路徑上經過的N層。但每層只能在by中指定一個輸出，返回的格式形如：

{
 "select": [
 ["李雷", "小明","小智"],
 ["李雷","韓梅梅", "小智"],
 ["李雷", "韓梅梅", "小霞"]
 ]
}

下麵我們來介紹一下select+by模式。如下圖，我們希望返回李雷的二跳鄰居的路徑情況。

{
 "repeat": [
 {
 "operator": "outV"
 }
 ],
 "times": 2,
 "vertices": [
 "李雷"
 ],
 "by": [{"id": true},{"id": true},{"id": true}],
 "select": ["v0", "v1", "v2"]
}

 

g.V('1').as('v0').both().as('v1').both().as('v2').select('v0','v1','v2').by(id()).select(values)

在上面body體中，我們使用select自帶的隱含層數別名v0, v1, v2。其分別表示用戶輸入的點集第0層-v0, K跳中的第1層-v1, K跳中的第2層-v2。

select中選中的別名與by中指定的格式一一對應。

以上案例輸出格式形如：

{
 "select": [
 ["李雷", "小明","小智"],
 ["李雷","韓梅梅", "小智"],
 ["李雷", "韓梅梅", "小霞"]
 ]
}

當然，我們也可以有更多的更豐富的輸出。比如我們希望將輸入點李雷的id和label都展示在路徑中，並且去掉了中間第一跳的好友小明和韓梅梅，直接顯示李雷及其第二跳好友的關係：

{
 "repeat": [
 {
 "operator": "outV"
 }
 ],
 "times": 2,
您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • socket 到底是個啥
    哈嘍大家好，我是鹹魚 我相信大家在面試過程中或多或少都會被問到這樣一個問題：你能解釋一下什麼是 socket 嗎 我記得我當初的回答很是淺顯：socket 也叫套接字，用來負責不同主機程式之間的網路通信連接，socket 的表現方式由四元組（ip地址：埠）組成 那麼今天，鹹魚將跟大家打開 sock ...
  • MIPI掃盲——D-PHY介紹
    原標題：【精品博文】MIPI掃盲——D-PHY介紹（一） D-PHY種的PHY是物理層（Physical）的意思，那麼D是什麼意思呢？在MIPI D-PHY的文檔中有提到過，D-PHY的最初版本的設計目標是500Mbits/s，而D是羅馬數字（拉丁文數字）中500 。同理C和M分別是羅馬數字中的10 ...
  • linux開發記錄：在linux環境下編寫代碼（1）
    terminal,vi 的使用: 0.進入與使用 用終端進入，相當於windows的cmd. ctrl+alt+T打開終端。 終端命令：ls查看文件夾下的文件 mkdir filename在當前目錄下創造一個文件夾 cd filename 進入某文件夾 . 代表當前目錄 .. 上層目錄 ping i ...
  • 讀SQL進階教程筆記11_關係資料庫基礎
    1. 1969年 1.1. 關係模型的創始人E.F. Codd（1923—2003） 1.1.1. 牛津大學數學專業 1.1.2. 一己之力奠定了關係模型的基礎 1.2. 論文《大型資料庫中關係存儲的可推導性、冗餘與一致性》 2. 1970年 2.1. 權威學術雜誌Communications of ...
  • 面試題百日百刷-kafka篇(三)
    鎖屏面試題百日百刷，每個工作日堅持更新面試題。請看到最後就能獲取你想要的,接下來的是今日的面試題： 1.如何保證Kafka的消息有序 Kafka對於消息的重覆、丟失、錯誤以及順序沒有嚴格的要求。 Kafka只能保證一個partition中的消息被某個consumer消費時是順序的，事實上，從Topi ...
  • ORACLE還原恢復啟動時資料庫報ORA-00704, ORA-00604, ORA-00904
    Oracle資料庫還原恢復後，執行alter database open resetlogs時遇到下麵錯誤。如下所示： SQL> alter database open resetlogs;alter database open resetlogs*ERROR at line 1:ORA-00603 ...
  • redis 工具類
    redis 工具類 /** * Redis 工具類 */ @Component public class RedisUtil { @Resource private RedisTemplate<String, Object> redisTemplate; public RedisUtil(Redis ...
  • 詳解GaussDB(DWS)的query_band負載識別與應用
    摘要：query_band是一個會話級別（session）的GUC參數，本身是字元串類型，支持任意形式字元組合。 本文分享自華為雲社區《GaussDB(DWS)的query_band負載識別與應用》，作者：門前一棵葡萄樹。 query_band概述 GaussDB(DWS)實現了基於query_ba ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類