RDBMS vs GraphDB

February 03, 2022

Zu diesem Zweck hab ich mir von Oreilly 3 Bücher heruntergeladen und bin diese überflogen, um die Konzepte zu verstehen. Die in den Büchern vorgestellten Datenbanken verwendeten die sogenannte Gremlin Query Language. Trotzdem muss ich sagen: Ich war skeptisch – wie ich bei sehr vielen NoSQL Datenbanken skeptisch bin. Es gibt sicher einige gute (Cassandra, Redis, …) – aber viele scheinen mir auch klassische Sonntagsprojekte zu sein und haben niemals den Tiefgang und die Professionalität von e.g PostgreSQL.

Die Grenzen von Rekursiven CTEs

In einem Projekt hatten wir eine sehr einfache Situation: Es gab eine Produkt-Hierarchie. Es gab somit eine Produkttabelle und eine Produkt-2-Produkt Tabelle. In der Doku findet man ein einfaches Beispiel:

WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS (
        SELECT g.id, g.link, g.data, 1,
          ARRAY[g.id],
          false
        FROM graph g
      UNION ALL
        SELECT g.id, g.link, g.data, sg.depth + 1,
          path || g.id,
          g.id = ANY(path)
        FROM graph g, search_graph sg
        WHERE g.id = sg.link AND NOT cycle
)
SELECT * FROM search_graph;

Das erste Problem ist, dass man mit CTEs sehr schwer ungerichtete Graphen durchsuchen kann (ich habe lange gesucht und viel probiert – es ging nie performant). Ein ungerichteter Graph muss daher immer durch einen gerichteten abgebildet werden (sie hier).

Des Weiteren stößt man schnell an die Grenzen der Technik, wenn die Tiefe des Baumes groß wird. Folgender Graph liegt in einer Datenbank mit 18 Mio. Kästchen (Produkten) und 54 Mio. Verbindungen zwischen den Kästchen. Pro Graph würde ich im Durchschnitt 30 Kästchen schätzen (es wird vermutlich auf 100 Kästchen steigen). Und mit einer Tiefe – wie im Graph zu sehen ist – ist zu rechnen.

Michael Vodep

Alleine der rekursive CTE brauchte auf einem sehr performanten Server 1350ms und hatte in der Rekursion 2.999.345 Zeilen. Und das nur, wenn man mit einem der mittleren Knoten anfängt. Fängt man mit dem obesten Knoten an - nach 3 Minuten kein Ergebnis.

Hat man die einzelnen Produkte des Graphs abgefragt (SELECT * FROM product WHERE id IN(….)): 35ms. Und das zeigt auch die Stärken des RDBMS:

Abfrage von Zeilen geht super schnell
Constraints bzw. Fremdschlüsseln
Gutes Tooling wie PLPGSQL
Isolationlevels, SELECT FOR UPDATE usw. erlauben eine feine Steuerung der Concurrency
Gute Tools für Backup, Profiling, Replication usw.

Aber: wenn man Abhängigkeiten zwischen Datensätzen darstellen will – schwierig.

Iterativer Ansatz

Was natürlich auch geht: statt einem CTE einen iterativen PLPGSQL Ansatz. Selbe Datenbank wie oben. 54 Mio. Kanten - Graph aus 50 Knoten - man will alle verbunden Knoten finden.

DROP TABLE IF EXISTS edges, nodes;

CREATE TABLE nodes
(
  id INTEGER PRIMARY KEY
);

CREATE TABLE edges
(
  "from" INTEGER NOT NULL REFERENCES nodes(id),
  "to" INTEGER NOT NULL REFERENCES nodes(id)
);

INSERT INTO nodes SELECT generate_series(1,5);
INSERT INTO edges VALUES
(1,2),(2,3),(3,5),(3,4),(4,3),(3,1),(5,1);

CREATE OR REPLACE FUNCTION walk_graph(param_product_id INTEGER)
  RETURNS TABLE (id INTEGER)
  LANGUAGE plpgsql
AS $$
DECLARE
  var_queue INTEGER[] := ARRAY[param_product_id];
  var_product_ids INTEGER[] := ARRAY[param_product_id];
  var_iteration_product_ids INTEGER[];
  var_product_id INTEGER;
BEGIN

  WHILE array_length(var_queue, 1) > 0 LOOP
    RAISE NOTICE 'stack = %', var_queue;
  
    var_product_id := var_queue[array_upper(var_queue, 1)];
    var_queue := var_queue[1:array_upper(var_queue, 1) - 1];    
      
    var_iteration_product_ids := ARRAY(SELECT "to" FROM edges
      WHERE "from" = var_product_id
      AND NOT("to" = ANY(var_product_ids)));     
   
    var_product_ids := var_product_ids || var_iteration_product_ids;
    var_queue := var_queue || var_iteration_product_ids;  
  END LOOP;

  RETURN QUERY SELECT unnest(var_product_ids);
END $$;

SELECT * FROM walk_graph(3);

Funktioniert mit 40msec auch gut. Je nach Graph kann es dann schlechter werden. Da die Stärke eines RDBMS in der Zeilenabfrage ist, würde ich trotzdem Graphen nummerieren (mit anderen Worten: Gibt mir alle Knoten, welche zum Graph X gehören und nicht edge-walking).

Optimiert man das Ganze noch und nutzt die Stärke von SQL: 20msec

CREATE OR REPLACE FUNCTION walk_graph(param_node_id INTEGER)
  RETURNS TABLE (id INTEGER)
  LANGUAGE plpgsql
AS $$
DECLARE
  var_node_ids INTEGER[] := ARRAY[param_node_id];
  var_iteration_node_ids INTEGER[] := ARRAY[param_node_id];
BEGIN

  WHILE array_length(var_iteration_node_ids, 1) > 0 LOOP  
      
    var_iteration_node_ids := ARRAY(SELECT DISTINCT "to" FROM edges
      WHERE "from" = ANY(var_iteration_node_ids)
      AND NOT("to" = ANY(var_node_ids)));     
   
    var_node_ids := var_node_ids || var_iteration_node_ids;
  END LOOP;

  RETURN QUERY SELECT unnest(var_node_ids);
END $$;

Graphendatenbanken

Die Grundkonzepte:

Nodes: Haben Properties, die Eigenschaften des Knoten beschreiben
Edges: Verbinden Konten und können ebenfalls Eigenschaften haben

Eine Suche könnte wie folgt ausschauen:

1 sensor = dev.V().has("Sensor", "sensor_name", "1002688").
2 next()
3 dev.V(sensor). // look up a sensor
4 until(hasLabel("Tower")). // until you reach a tower
5 repeat(out("send"). // keep walking out the send edge
6 simplePath()) // remove cycles

Ebenfalls war in einem der Bücher ein Benchmark:

Michael Vodep

Das schaut schon mal alles sehr interessant aus. Aber ich vermisse sehr viele Dinge von einer RDBMS. Dazu noch zwei Links:

RDBMS Fehlentscheidung?

Zuerst dachte ich: RDBMS war eine Fehlentscheidung. Dann rief ich mir die Situation aber nochmal ins Gedächtnis:

30-100 Knoten im Durchschnitt – d.h. man hat eine hohe Clusterung von Daten
Klassische Abfragen: Gib mir alle Produkte eines Graphen mit dieser Eigenschaft oder alle Kanten mit jener Eigenschaft
Graphen wachsen mit der Zeit

D.h.: Irgendwie musste ich die CTE wieder loswerden. Die beste Lösung, die mir eingefallen ist (und die auch am logischsten ist): man führt einfach eine Tabelle „Graph“ ein und jedes Produkt verweist auf diese. Somit kann ich schnell sagen: SELECT * FROM product WHERE graph_id = 99 AND status = Foo.

Was ginge noch?

Ebenfalls könnte ich mir die PolyglotPersistence vorstellen. D.h. einfach die stärken des RDBMS und einer Graph-Datenbanken vereinen.