Cypher no loops, no double paths

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(); 

Я прочитал, что среда выполнения является более вероятным в О (п^х), но не могу найти любую команду, которая исключает, например, петли или несколько путей к одному узлу, поэтому запрос принимает простой в течение 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 

Кроме того, при выполнении какой-либо настройки производительности, вы должны PROFILE ваших запросов (по крайней мере те, которые заканчивают в течение разумного периода времени) и EXPLAIN те, которые принимает абсурдное количество времени, чтобы рассмотреть запрос план.

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 - это работает.