Best Practices für die Optimierung von Spanner-Graphabfragen

In diesem Dokument werden Best Practices zum Optimieren der Leistung von Spanner Graph-Abfragen beschrieben, darunter die folgenden Optimierungen:

  • Vermeiden Sie einen vollständigen Scan der Eingabetabelle für Knoten und Kanten.
  • Reduzieren Sie die Menge der Daten, die für die Abfrage aus dem Speicher gelesen werden müssen.
  • Größe der Zwischendaten verringern

Mit Knoten mit niedriger Kardinalität beginnen

Schreiben Sie den Path Traversal so, dass er mit den Knoten mit niedriger Kardinalität beginnt. So bleibt die Zwischenergebnismenge klein und die Abfrageausführung wird beschleunigt.

Die folgenden Abfragen haben beispielsweise dieselbe Semantik:

  • Vorwärtskanten-Traversal:

    GRAPH FinGraph
MATCH (p:Person {name:"Alex"})-[:Owns]->(a:Account {is_blocked: true})
RETURN p.id AS person_id, a.id AS account_id;

  • Kantenrückwärtslauf:

    GRAPH FinGraph
MATCH (a:Account {is_blocked:true})<-[:Owns]-(p:Person {name: "Alex"})
RETURN p.id AS person_id, a.id AS account_id;

Angenommen, es gibt weniger Personen mit dem Namen Alex als blockierte Konten. In diesem Fall empfehlen wir, diese Abfrage im Forward-Edge-Traversal zu schreiben.

Das Starten mit Knoten mit niedrigerer Kardinalität ist besonders wichtig für die Path Traversal mit variabler Länge. Im folgenden Beispiel wird die empfohlene Methode zum Suchen von Konten gezeigt, die sich innerhalb von drei Übertragungen eines bestimmten Kontos befinden.

GRAPH FinGraph
MATCH (:Account {id: 7})-[:Transfers]->{1,3}(a:Account)
RETURN a.id;

Alle Labels standardmäßig angeben

Spanner Graph leitet die infrage kommenden Knoten und Kantenlabels ab, wenn Labels weggelassen werden. Wir empfehlen, nach Möglichkeit Labels für alle Knoten und Kanten anzugeben, da diese Ableitung nicht immer möglich ist und möglicherweise mehr Labels als nötig gescannt werden.

Einzelne MATCH-Anweisung

Im folgenden Beispiel werden Konten gesucht, die durch maximal drei Übertragungen mit dem angegebenen Konto verknüpft sind:

GRAPH FinGraph
MATCH (src:Account {id: 7})-[:Transfers]->{1,3}(dst:Account)
RETURN dst.id;

Über MATCH-Anweisungen hinweg

Geben Sie Labels für Knoten und Kanten an, wenn sie sich auf dasselbe Element beziehen, aber über MATCH-Anweisungen hinweg verwendet werden.

Das folgende Beispiel veranschaulicht diesen empfohlenen Ansatz:

GRAPH FinGraph
MATCH (acct:Account {id: 7})-[:Transfers]->{1,3}(other_acct:Account)
RETURN acct, COUNT(DISTINCT other_acct) AS related_accts
GROUP BY acct

NEXT

MATCH (acct:Account)<-[:Owns]-(p:Person)
RETURN p.id AS person, acct.id AS acct, related_accts;

IS_FIRST zum Optimieren von Abfragen verwenden

Mit der Funktion IS_FIRST können Sie die Abfrageleistung verbessern, indem Sie Kanten stichprobenartig erfassen und Traversierungen in Diagrammen einschränken. Diese Funktion hilft, Knoten mit hoher Kardinalität zu verarbeiten und Multi-Hop-Abfragen zu optimieren.

Wenn die angegebene Stichprobengröße zu klein ist, werden bei der Abfrage möglicherweise keine Daten zurückgegeben. Daher müssen Sie möglicherweise verschiedene Stichprobengrößen ausprobieren, um das optimale Gleichgewicht zwischen zurückgegebenen Daten und verbesserter Abfrageleistung zu finden.

In diesen IS_FIRST-Beispielen wird FinGraph verwendet, ein Finanzdiagramm mit Account Knoten und Transfers Kanten für Geldüberweisungen. Informationen zum Erstellen der FinGraph und zum Ausführen der Beispielabfragen damit finden Sie unter Cloud Spanner Graph einrichten und abfragen.

Durchlaufene Kanten begrenzen, um die Abfrageleistung zu verbessern

Wenn Sie Graphen abfragen, kann die Anzahl der eingehenden oder ausgehenden Kanten für einige Knoten deutlich höher sein als für andere. Diese Knoten mit hoher Kardinalität werden manchmal als Superknoten oder Hub-Knoten bezeichnet. Superknoten können Leistungsprobleme verursachen, da bei Traversierungen durch sie möglicherweise riesige Datenmengen verarbeitet werden müssen, was zu Datenverzerrung und langen Ausführungszeiten führt.

Um eine Abfrage eines Graphen mit Superknoten zu optimieren, verwenden Sie die Funktion IS_FIRST in einer FILTER-Klausel, um die Anzahl der Kanten zu begrenzen, die die Abfrage von einem Knoten aus durchläuft. Da Konten in FinGraph möglicherweise deutlich mehr Transaktionen als andere haben, können Sie IS_FIRST verwenden, um eine ineffiziente Abfrage zu verhindern. Diese Technik ist besonders nützlich, wenn Sie keine vollständige Aufzählung aller Verbindungen von einem Superknoten benötigen.

Mit der folgenden Abfrage werden Konten (a2) gefunden, die direkt oder indirekt Überweisungen von gesperrten Konten (a1) erhalten. In der Abfrage wird IS_FIRST verwendet, um die Leistung zu verbessern, wenn ein Konto viele Überweisungen hat. Dazu wird die Anzahl der Transfers-Kanten begrenzt, die für jedes Account berücksichtigt werden.

GRAPH FinGraph
MATCH
(a1:Account {is_blocked: true})
-[e:Transfers WHERE e IN
  {
    MATCH -[selected_e:Transfers]->
    FILTER IS_FIRST(@max_transfers_per_account) OVER (
      PARTITION BY SOURCE_NODE_ID(selected_e)
      ORDER BY selected_e.create_time DESC)
    RETURN selected_e
  }
]->{1,5}
(a2:Account)
RETURN a1.id AS src_id, a2.id AS dst_id;

In diesem Beispiel wird Folgendes verwendet:

  • @max_transfers_per_account: Ein Abfrageparameter, der die maximale Anzahl von Transfers-Kanten angibt, die für jedes Konto (a1) berücksichtigt werden sollen.

  • PARTITION BY SOURCE_NODE_ID(selected_e): Sorgt dafür, dass das IS_FIRST-Limit unabhängig für jedes Konto (a1) gilt.

  • ORDER BY selected_e.create_time DESC: Gibt an, dass die letzten Übertragungen zurückgegeben werden.

Zwischenknoten für die Optimierung von Multi-Hop-Abfragen auswählen

Sie können die Abfrageeffizienz auch verbessern, indem Sie IS_FIRST verwenden, um Zwischenknoten in Multi-Hop-Abfragen zu erfassen. Diese Technik verbessert die Effizienz, indem die Anzahl der Pfade begrenzt wird, die bei jeder Zwischenstufe der Abfrage berücksichtigt werden. Dazu müssen Sie eine Multi-Hop-Abfrage in mehrere MATCH-Anweisungen aufteilen, die durch NEXT getrennt sind, und IS_FIRST in der Mitte anwenden, an der Sie Stichproben nehmen müssen:

GRAPH FinGraph
MATCH (a1:Account {is_blocked: true})-[e1:Transfers]->(a2:Account)
FILTER IS_FIRST(1) OVER (PARTITION BY a2)
RETURN a1, a2

NEXT

MATCH (a2)-[e2:Transfers]->(a3:Account)
RETURN a1.id AS src_id, a2.id AS mid_id, a3.id AS dst_id;

So optimiert IS_FIRST diese Abfrage:

  • Die Klausel FILTER IS_FIRST(1) OVER (PARTITION BY a2) wird in der ersten MATCH-Anweisung angewendet.

  • Für jeden Zwischenkontoknoten (a2) wird in IS_FIRST nur die erste eingehende Transfers-Kante (e1) berücksichtigt. Dadurch wird die Anzahl der Pfade, die in der zweiten MATCH-Anweisung untersucht werden müssen, reduziert.

  • Die Effizienz der gesamten Two-Hop-Abfrage wird verbessert, da für die zweite MATCH keine unnötigen Daten verarbeitet werden, insbesondere wenn a2 viele eingehende Übertragungen hat.

Faktorisierte Ausführung zur Optimierung von Abfragen verwenden

Sie können die Leistung von Spanner Graph-Abfragen optimieren, indem Sie eine Abfrage faktorisieren, die ein Graphenmuster durchläuft und doppelte Zwischenergebnisse erzeugt.

Eine Graphabfrage kann im faktorisierten Modus ausgeführt werden. Dabei werden Pfadpräfixe mit hoher Kardinalität dedupliziert, bevor der Rest des Pfads durchlaufen wird. Diese Optimierung verbessert die Abfrageleistung, da wiederholte Schlüsselvergleiche oder Hash-Tabellen-Probes während der Ausführung von Diagrammabfragen reduziert werden. Wenn Sie eine Abfrage faktorisieren möchten, fügen Sie den Hinweis @{factorized_mode} auf der Ebene des einzelnen Musterdurchlaufs oder auf Abfrageebene hinzu.

Legen Sie für factorized_mode einen der folgenden Werte fest:

  • factorize_left: Optimiert das Durchlaufen von Diagrammen, bei denen viele Pfade auf wenigen Knoten zusammenlaufen. In Spanner Graph werden Pfade anhand der Zielknoten-ID dedupliziert. Anschließend werden Knoteneigenschaften abgerufen, um redundante Arbeit zu vermeiden.

  • factorize_both: Optimiert nicht lineare Anfragen mit mehreren untergeordneten Pfaden, die Knoten gemeinsam nutzen. Bei Spanner Graph werden keine Zwischenergebnisse für jeden Pfad unabhängig voneinander generiert. Stattdessen wird jeder Teilpfad einmal berechnet und dann kombiniert. Das Kreuzprodukt der Ergebnisse wird bis zum Ende verzögert. Verwenden Sie diese Option für Muster wie Dreiecke oder Verzweigungen.

Weitere Informationen zu Hinweisen zum Durchlaufen finden Sie unter Graph-Hinweise.

Die folgenden Beispiele zeigen, wie Sie Hinweise zum faktorisierten Modus verwenden, um die Leistung von Diagrammanfragen zu verbessern. Erstellen Sie das FinGraph-Schema in Cloud Spanner Graph einrichten und abfragen, um den Beispielcode auszuführen.

Zwischenergebnisse in einer linearen Abfrage reduzieren

Betrügerische Konten weisen oft ein hohes Transaktionsvolumen auf. Abfragen, mit denen diese Konten ermittelt werden sollen, können große Zwischenergebnisse generieren, von denen viele Duplikate sind, da sie auf eine kleine Anzahl von Zielkonten ausgerichtet sind. Das Abrufen betrügerischer Knoteneigenschaften aus diesen redundanten Zwischenergebnissen erfordert unnötige Berechnungen, die die Abfrageleistung erheblich verlangsamen können.

Der Hinweis @{factorized_mode} behebt dieses Problem, indem er die Abfrageausführung optimiert. Das folgende Beispiel zeigt, wie Sie diesen Hinweis verwenden, um Konto- und Transaktionsdetails abzurufen. Es werden Überweisungen von einem bekannten gesperrten Konto zu potenziell betrügerischen Konten verfolgt, die ein bis drei Schritte entfernt sind. Die nicht optimierte Version dieser Abfrage ist auf dem zweiten Tab verfügbar.

Faktorisierte Abfrage 

GRAPH FinGraph
MATCH (a1:Account {is_blocked: true})-[e1:Transfers]->{1,3}@{factorized_mode=factorize_left}(a2:Account)
LET total_amount = SUM(e1.amount)
RETURN a2.id, a2.create_time, total_amount;

Nicht optimierte Abfrage 

GRAPH FinGraph
MATCH (a1:Account {is_blocked: true})-[e1:Transfers]->{1,3}(a2:Account)
LET total_amount = SUM(e1.amount)
RETURN a2.id, a2.create_time, total_amount;

Wenn die Anzahl der unterschiedlichen Zielknoten a2 viel kleiner ist als die Anzahl der Pfade zu a2, wird durch diese Technik redundante Arbeit vermieden. Das ist in Betrugsnetzwerken üblich, in denen Vermittler Geld an einige wenige Empfänger überweisen. Der faktorisiert Hinweis führt die folgenden Aktionen aus:

  • Hiermit werden alle Pfade mit ein bis drei Kanten ab einem blockierten Knoten und die Summe der Transfers entlang dieser Pfade ermittelt.

  • Bestimmt die Anzahl der unterschiedlichen Zielknoten a2.

  • Ruft die create_time für jeden eindeutigen Zielknoten a2 nur einmal ab.

  • Kombiniert die create_time für jeden Knoten a2 mit der Liste der Pfade, die zu a2 führen, um das Abfrageergebnis zu bilden.

Generierung von Zwischenergebnissen in komplexen nicht linearen Abfragen aufschieben

Graph-Abfragen haben oft eine komplexe Struktur, die aus mehreren linearen Teilpfadmuster besteht. Das folgende Beispiel zeigt eine Abfrage, mit der Transaktionen analysiert werden, die von einem Konto mit id gleich 1 stammen. In dieser Abfrage werden alle Zielkonten anhand ihres create_time in drei verschiedene Gruppen eingeteilt:

  • In den letzten 30 Tagen
  • Vor 30 bis 90 Tagen
  • Älter als 90 Tage

Die Abfrage gibt alle Dreifach-Tupel und den Gesamttransaktionsbetrag für diese Transaktionen zurück.

Der Hinweis @{factorized_mode=factorize_both} optimiert die Abfrageausführung, indem eine frühzeitige Materialisierung von Zwischenergebnissen vermieden wird. Dabei wird die Tatsache genutzt, dass alle untergeordneten Pfade in der MATCH-Klausel bedingt unabhängig sind, wenn der Wert des Startknotens a bekannt ist. Bei factorize_both werden die ersten beiden Unterpfade unabhängig voneinander ausgewertet. Die Auswertung des letzten Unterpfads wird nicht wiederholt.

Faktorisierte Abfrage 

GRAPH FinGraph
MATCH (a:Account {id: 1})-[e1:Transfers]->(a1:Account),
  @{factorized_mode=factorize_both}(a:Account)-[e2:Transfers]->(a2:Account),
  (a:Account)-[e3:Transfers]->(a3:Account)
WHERE e1.create_time < TIMESTAMP_SUB(CURRENT_TIMESTAMP(), INTERVAL 90 DAY)
  AND e2.create_time >= TIMESTAMP_SUB(CURRENT_TIMESTAMP(), INTERVAL 90 DAY)
  AND e2.create_time < TIMESTAMP_SUB(CURRENT_TIMESTAMP(), INTERVAL 30 DAY)
  AND e3.create_time >= TIMESTAMP_SUB(CURRENT_TIMESTAMP(), INTERVAL 30 DAY)
LET total_amount = e1.amount + e2.amount + e3.amount
RETURN a1.id as a1_id, a2.id as a2_id, a3.id as a3_id, total_amount;

Nicht optimierte Abfrage 

GRAPH FinGraph
MATCH (a:Account {id: 1})-[e1:Transfers]->(a1:Account),
  (a:Account)-[e2:Transfers]->(a2:Account),
  (a:Account)-[e3:Transfers]->(a3:Account)
WHERE e1.create_time < TIMESTAMP_SUB(CURRENT_TIMESTAMP(), INTERVAL 90 DAY)
  AND e2.create_time >= TIMESTAMP_SUB(CURRENT_TIMESTAMP(), INTERVAL 90 DAY)
  AND e2.create_time < TIMESTAMP_SUB(CURRENT_TIMESTAMP(), INTERVAL 30 DAY)
  AND e3.create_time >= TIMESTAMP_SUB(CURRENT_TIMESTAMP(), INTERVAL 30 DAY)
LET total_amount = e1.amount + e2.amount + e3.amount
RETURN a1.id as a1_id, a2.id as a2_id, a3.id as a3_id, total_amount;

Bei einem bestimmten Startkonto mit id = 1 führt jede ausgehende Transfers-Kante zu mehreren unabhängigen Zielknoten. Dazu ein Beispiel:

  • M ist die Anzahl der Konten (a1) mit Übertragungen im Bereich (-inf, 90 DAYS).

  • N ist die Anzahl der Konten (a2) mit Übertragungen im Bereich [90 DAYS, 30 DAYS).

  • K ist die Anzahl der Konten (a3) mit Übertragungen im Bereich [30 DAYS, +inf).

Bei der nicht optimierten Abfrage werden Zwischenergebnisse frühzeitig generiert. Der zweite Unterpfad wird M-mal und der dritte Unterpfad M * N-mal berechnet. Im Gegensatz dazu wird die Abfrageausführung durch eine faktorisierte Version optimiert, indem Folgendes erfolgt:

  • M Zielknoten (a1) für den ersten Unterpfad abrufen und eine Gruppe von a1-Knoten vorübergehend speichern.

  • N Zielknoten (a2) für den zweiten Unterpfad nur einmal abrufen und eine Reihe von a2-Knoten vorübergehend speichern.

  • K-Zielknoten (a3) für den letzten Unterpfad nur einmal abrufen.

  • Mengenprodukt zwischen temporären Zwischenergebnissen erstellen, um das Produkt aus M × N × K Datensätzen zu erhalten.

Nächste Schritte