Neo4j Cypher Abfrage um Knoten zu finden, die nicht zu langsam verbunden sind

Question

Gegeben haben wir das folgende Neo4j Schema (vereinfacht, aber es zeigt den wichtigen Punkt). Es gibt zwei Arten von Knoten NODE und VERSION. VERSION s sind über eine VERSION_OF Beziehung mit NODE verbunden. VERSION Knoten haben zwei Eigenschaften from und until, die den Gültigkeitszeitraum angeben - entweder oder beide können NULL sein (in Neo4j-Begriffen nicht vorhanden), um unbegrenzt zu bezeichnen. NODE s kann über eine HAS_CHILD Beziehung verbunden werden. Wiederum haben diese Beziehungen zwei Eigenschaften from und until, die den Gültigkeitszeitraum angeben - entweder oder beide können NULL (in Neo4j-Begriffen nicht vorhanden) sein, um unbegrenzt zu bezeichnen.

EDIT: Die Gültigkeitsdaten auf VERSION Knoten und HAS_CHILD Beziehungen unabhängig sind (auch wenn das Beispiel zufällig zeigt sie ausgerichtet sind).

Das Beispiel zeigt zwei NODE s A und B . A hat zwei VERSION s AV1 bis 6/30/17 und AV2 ausgehend von 7/1/17 während B hat nur eine Version BV1, die unbegrenzt ist. B ist mit A über eine HAS_CHILD Beziehung bis 6/30/17 verbunden.

Die Herausforderung besteht jetzt darin, das Diagramm für alle Knoten abzufragen, die kein Kind sind (das sind Stammknoten) zu einem bestimmten Zeitpunkt. In dem obigen Beispiel sollte die Abfrage nur B zurückgeben, wenn das Abfragedatum z. 6/1/17, aber es sollte B und A zurückgeben, wenn das Abfragedatum z.B. 8/1/17 (weil A ist kein Kind von B ab dem 1.7.17 mehr). heute

Die aktuelle Abfrage ist in etwa ähnlich ist, dass man:

MATCH (n1:NODE) 
OPTIONAL MATCH (n1)<-[c]-(n2:NODE), (n2)<-[:VERSION_OF]-(nv2:ITEM_VERSION) 
WHERE (c.from <= {date} <= c.until) 
AND (nv2.from <= {date} <= nv2.until) 
WITH n1 WHERE c IS NULL 
MATCH (n1)<-[:VERSION_OF]-(nv1:ITEM_VERSION) 
WHERE nv1.from <= {date} <= nv1.until 
RETURN n1, nv1 
ORDER BY toLower(nv1.title) ASC 
SKIP 0 LIMIT 15 

Diese Abfrage funktioniert relativ fein im Allgemeinen, aber es beginnt langsam wie die Hölle bekommen, wenn sie auf große Datensätze (vergleichbar mit realen Produktions Datensätze) verwendet. Mit 20-30k NODE s (und etwa der doppelten Anzahl von VERSION s) dauert die (echte) Abfrage etwa 500-700 ms auf einem kleinen Docker Container unter Mac OS X), was akzeptabel ist. Aber mit 1.5M NODE s (und etwa die doppelte Anzahl von VERSION s) die (echte) Abfrage dauert etwas mehr als 1 Minute auf einem Bare-Metal-Server (läuft nichts anderes als Neo4j). Das ist nicht wirklich akzeptabel.

Haben wir eine Option, diese Abfrage zu optimieren? Gibt es bessere Möglichkeiten, die Versionierung von NODE s (was ich bezweifle, ist das Leistungsproblem hier) oder die Gültigkeit von Beziehungen zu handhaben? Ich weiß, dass Beziehungseigenschaften nicht indiziert werden können, daher könnte es ein besseres Schema für die Handhabung der Gültigkeit dieser Beziehungen geben.

Jede Hilfe oder auch nur der geringste Hinweis wird sehr geschätzt.

EDIT nach answer from Michael Hunger:

1. Prozentsatz der Wurzelknoten:

   Bei dem aktuellen Beispiel Datensatz (1.5M Knoten) die Ergebnismenge enthält etwa 2k Zeilen. Das sind weniger als 1%.

2. ITEM_VERSION Knoten in der ersten MATCH:

   Wir die ITEM_VERSIONnv2 mit zu ITEM Knoten die Ergebnismenge zu filtern, die keine andere Verbindung ITEM Knoten am angegebenen Datum. Das bedeutet, dass entweder keine Beziehung existieren muss, die für das angegebene Datum gültig ist, oder dass das verbundene Element keine ITEM_VERSION hat, die für das angegebene Datum gültig ist. Ich versuche, dies zu verdeutlichen:

   // date 6/1/17 
   
   // n1 returned because relationship not valid 
   (nv1 ...)->(n1)-[X_HAS_CHILD ...6/30/17]->(n2)<-(nv2 ...) 
   
   // n1 not returned because relationship and connected item n2 valid 
   (nv1 ...)->(n1)-[X_HAS_CHILD ...]->(n2)<-(nv2 ...) 
   
   // n1 returned because connected item n2 not valid even though relationship is valid 
   (nv1 ...)->(n1)-[X_HAS_CHILD ...]->(n2)<-(nv2 ...6/30/17) 
   

3. Keine Verwendung von Beziehungstypen:

   Das Problem hierbei ist, dass die Software ein benutzerdefinierte Funktionen Schema und ITEM Knoten durch benutzerdefinierte Beziehung Typen verbunden . Da wir nicht mehrere Typen/Labels für eine Beziehung haben können, ist das einzige gemeinsame Merkmal für diese Art von Beziehungen, dass sie alle mit X_ beginnen. Das wurde hier aus dem vereinfachten Beispiel weggelassen. Würde die Suche mit dem Prädikat type(r) STARTS WITH 'X_' hier helfen?

Answer 1

Ich denke, ein guter Start für die Verbesserung auf Knoten unter Verwendung eines Index übereinstimmen würde, so dass Sie schnell eine kleinere relevante Teilmenge von Knoten zu suchen, bekommen. Ihr Ansatz muss jetzt alle Ihre: NODEs und alle ihre Beziehungen und Muster von ihnen jedes Mal überprüfen, die, wie Sie gefunden haben, nicht mit Ihren Daten skalieren.

Im Moment sind die einzigen Knoten in Ihrem Diagramm mit Datum/Uhrzeit-Eigenschaften Ihre: ITEM_VERSION-Knoten, also fangen wir damit an. Sie benötigen einen Index für: ITEM_VERSIONs von und bis Eigenschaften für schnelle Suche.

Die Nullen sind problematisch für Ihre Lookups, da jede Ungleichheit gegen einen Nullwert Null zurückgibt und die meisten Problemumgehungen für die Verwendung von Nullwerten (Verwendung von COALESCE() oder mehreren ANDs/ORs für Nullfälle) die Verwendung zu verhindern scheinen von Indexnachfragen, was der Punkt meines besonderen Vorschlags ist.

Ich möchte Sie ermutigen, Ihre nulls in von und bis mit min und max Werte zu ersetzen, die Sie Vorteil der Suche nach Knoten, die durch Indexsuche nehmen lassen sollten:

MATCH (version:ITEM_VERSION) 
WHERE version.from <= {date} <= version.until 
MATCH (version)<-[:VERSION_OF]-(node:NODE) 
... 

, die zumindest einen schnellen Zugriff zur Verfügung stellen sollten eine kleinere Teilmenge von Knoten am Anfang für die Fortsetzung Ihrer Abfrage.

Answer 2

Welche Neo4j Version verwenden Sie.

Welcher Prozentsatz Ihrer 1,5M-Knoten wird an Ihrem Beispieldatum als Stammverzeichnis gefunden, und wenn Sie nicht das Limit haben, wie viele Daten zurückkommen? Vielleicht ist das Problem nicht so sehr in der Übereinstimmung wie in der Sortierung am Ende?

Ich bin nicht sicher, warum Sie die VERSION-Knoten in Ihrem ersten Teil hatten, zumindest beschreiben Sie sie nicht als relevant für die Bestimmung eines Wurzelknotens.

Sie haben keine Beziehungstypen verwendet.

MATCH (n1:NODE) // matches 1.5M nodes 
// has to do 1.5M * degree optional matches 
OPTIONAL MATCH (n1)<-[c:HAS_CHILD]-(n2) WHERE (c.from <= {date} <= c.until) 
WITH n1 WHERE c IS NULL 
// how many root nodes are left? 
// # root nodes * version degree (1..2) 
MATCH (n1)<-[:VERSION_OF]-(nv1:ITEM_VERSION) 
WHERE nv1.from <= {date} <= nv1.until 
// has to sort all those 
WITH n1, nv1, toLower(nv1.title) as title 
RETURN n1, nv1 
ORDER BY title ASC 
SKIP 0 LIMIT 15