Cypher沒有循環，沒有雙重路徑

Question

我目前正在建模一個數據庫超過50.000個節點，每個節點有2個定向關係。我嘗試獲取一個輸入節點（根節點）的所有節點，這些節點通過一個關係連接到它，並且這些節點的所有子節點都是這樣，直到到達與該根節點直接和間接連接的每個節點。

String query = 
    "MATCH (m {title:{title},namespaceID:{namespaceID}})-[:categorieLinkTo*..]->(n) " + 
    "RETURN DISTINCT n.title AS Title, n.namespaceID " + 
    "ORDER BY n.title"; 

Result result = db.execute(query, params); 
String infos = result.resultAsString(); 

我已閱讀，運行時更可能發生在爲O（n^x）中，但我不能找到排除例如環或多個路徑在一個節點的任何命令，所以查詢採用在2小時內簡單這對我的用例來說是不可接受的。

Answer 1

對於簡單的關係表達式，Cypher支架排除多個關係通過強制uniqueness自動：

雖然模式匹配，Neo4j的確保爲不包括其中相同的圖形關係被發現多次在一個單一的圖案匹配。

的文檔不是這是否適用於可變長度的路徑完全清楚 - 讓我們設計一個小實驗確認：

CREATE 
    (n1:Node {name: "n1"}), 
    (n2:Node {name: "n2"}), 
    (n3:Node {name: "n3"}), 
    (n4:Node {name: "n4"}), 
    (n1)-[:REL]->(n2), 
    (n2)-[:REL]->(n3), 
    (n3)-[:REL]->(n2), 
    (n2)-[:REL]->(n4) 

這導致如下圖：

查詢有：

MATCH (n:Node {name:"n1"})-[:REL*..]->(m) 
RETURN m 

結果是：

╒══════════╕ 
│m   │ 
╞══════════╡ 
│{name: n2}│ 
├──────────┤ 
│{name: n3}│ 
├──────────┤ 
│{name: n2}│ 
├──────────┤ 
│{name: n4}│ 
├──────────┤ 
│{name: n4}│ 
└──────────┘ 

正如你可以看到n4包含多次（因爲它可以與避免循環，並通過循環的那麼順利訪問）。 與PROFILE檢查執行：

所以我們應該用DISTINCT擺脫重複的：

MATCH (n:Node {name:"n1"})-[:REL*..]->(m) 
RETURN DISTINCT m 

結果是：

╒══════════╕ 
│m   │ 
╞══════════╡ 
│{name: n2}│ 
├──────────┤ 
│{name: n3}│ 
├──────────┤ 
│{name: n4}│ 
└──────────┘ 

再次檢查用PROFILE執行：

Answer 2

確實有一些事情我們可以做，以改善此查詢。

其中之一，你根本沒有使用標籤。由於您沒有使用標籤，因此輸入節點上的匹配無法利用您可能擁有的任何模式索引，並且它必須掃描所有訪問和比較屬性的50k節點，直到找到所有節點給定的標題和命名空間（當發現它時它不會停止，因爲它不知道是否有其他節點滿足條件）。您可以通過單獨匹配開始節點來檢查時間。

爲了改善這一點，您的節點應該被標記，並且您的起始節點上的匹配應該包含標籤，並且您的title和namespaceID屬性應該被編入索引。

僅此一項就可以顯着提高查詢速度。

接下來的問題是，如果剩下的瓶頸更多歸因於排序，或返回一個巨大的結果集？

您可以通過限制返回的結果來檢查單獨排序的成本。

在匹配後，您可以將此用於查詢的結尾。

WITH DISTINCT n 
ORDER BY n.title 
LIMIT 10 
RETURN n.title AS Title, n.namespaceID 
ORDER BY n.title 

同樣，在做任何性能優化的時候，你就應該剖析你的查詢（至少在合理時間內完成的）並解釋說，正在時間的荒謬量檢查查詢的那些計劃。

Answer 3

public static HashSet<Node> breadthFirst(String name, int namespace, GraphDatabaseService db) { 

     // Hashmap for storing the cypher query and its parameters 
     Map<String, Object> params = new HashMap<>(); 


     // Adding the title and namespaceID as parameters to the Hashmap 
     params.put("title", name); 
     params.put("namespaceID", namespace); 

     /*it is a simple BFS with these variables below 
     * basically a Queue (touched) as usual, a Set to store the nodes 
     * which have been used (finished), a return variable and 2 result 
     * variables for the queries 
     */ 
     Node startNode = null; 
     String query = "Match (n{title:{title},namespaceID:{namespaceID}})-[:categorieLinkTo]-> (m) RETURN m"; 
     Queue<Node> touched = new LinkedList<Node>(); 
     HashSet<Node>finished = new HashSet<Node>(); 
     HashSet<Node> returnResult = new HashSet<Node>(); 

     Result iniResult = null; 
     Result tempResult=null; 

     /*the part below get the direct nodes and puts them 
     * into the queue 
     */ 
      try (Transaction tx = db.beginTx()) { 
       iniResult =db.execute(query,params); 


       while(iniResult.hasNext()){ 
        Map<String,Object> iniNode=iniResult.next(); 
        startNode=(Node) iniNode.get("m"); 
        touched.add(startNode); 
        finished.add(startNode); 
       } 
       tx.success(); 
       }catch (QueryExecutionException e) { 
       logger.error("Fehler bei Ausführung der Anfrage", e); 
       } 

      /*and now we just execute the BFS (don't think i need more to 
      * say here.. we are all pros ;)) 
      * as usual, marking every node we have visited 
      * and saving every visited node. 
      * the difficult part had been the casting from 
      * and to node and result, everything else is pretty much 
      * straightforward. I think the variables explain their self 
      * via their name.... 
      */ 

       while(! (touched.isEmpty())){ 
       try (Transaction tx = db.beginTx()) { 
        Node currNode=touched.poll(); 
        returnResult.add(currNode); 

        tempResult=null;    
        Map<String, Object> paramsTemp = new HashMap<>(); 
        paramsTemp.put("title",currNode.getProperty("title").toString()); 
        paramsTemp.put("namespaceID", 14); 
        String tempQuery = "MATCH (n{title:{title},namespaceID:{namespaceID}})-[:categorieLinkTo] -> (m) RETURN m"; 
        tempResult = db.execute(tempQuery,paramsTemp); 



       while(tempResult.hasNext()){ 
        Map<String, Object> currResult= null; 
        currResult=tempResult.next(); 
        Node tempCurrNode = (Node) currResult.get("m"); 

        if (!finished.contains(tempCurrNode)){ 
         touched.add(tempCurrNode); 
         finished.add(tempCurrNode); 


        } 


        } 


       tx.success(); 
      }catch (QueryExecutionException f) { 
       logger.error("Fehler bei Ausführung der Anfrage", f); 
      } 
     }  


     return returnResult; 

} 

因爲我無法找到一個合適的Cypher表達式，所以我自己寫了一個漂亮的BFS - 它看起來很有效。