Ulf Wendel

Eine reiche NoSQL-Anfragesprache?

Eine reiche Anfragesprache verspricht ein populäres NoSQL-System auf seiner Startseite. Reicher als SQL? Ist das auffinden von Informationen einfacher, kann ich besser suchen als mit SQL? Das System gehört zur Gruppe der dokumentenbasierten NoSQL-Stores und wirbt mit Schemafreiheit für sich. Es speichert BSON-Dokumente in Sammlungen. Das Dokument lässt sich grob mit einem Datensatz/Tupel aus einer Tabelle/Relation eines RDBMS vergleichen.

Etwas Relationenalgebra

SQL ist eine konkrete Anfragesprache für eine relationale Datenbank. Eine Anfragalgebra kann benutzt werden um eine Anfragesprache mathematisch exakt zu fassen. Das klingt gruselig für den praktisch orientierten Anwender. Es hilft aber, um sich der Frage zu nähern wie reich die eine oder andere Sprache ist und ist auch gleich vorbei. In der Relationenalgebra finden wir:

  • Projektion (Ausblenden von Spalten)
  • Selektion (Zeilen suchen)
  • Verbund (Tabellen verknüpfen)
  • Vereinigung (Tabellen vereinigen)
  • Differenz (Tabellen abziehen voneinander)
  • Spalten umbenennen (das ist nicht AS, brauchen wir in der Praxis nicht)

Einen Teil können wir gleich streichen. Der fragliche NoSQL-Store kann weder Dokumente noch Sammlungen verknüpfen, vereinigen oder die Differenz bilden. Ein Verbund lässt sich bestenfalls aus mehreren Einzelabfragen nachbauen. Irgendwie logisch – er ist eher als hierarchisch denn als relational zu bezeichnen. SQL-Äpfel und NoSQL-Orangen sind zwei verschiedene Dinge.

  • Projektion (Ausblenden von Spalten [Feldern])
  • Selektion (Zeilen [Dokumente] suchen)
  • Verbund (Tabellen verknüpfen)
  • Vereinigung (Tabellen vereinigen)
  • Differenz (Tabellen abziehen voneinander)
  • Spalten [Felder] umbenennen

Die Projektion

Im Rahmen der Projektion werden Spalten ausgewählt . Die Projektion findet sich gleich zu Beginn einer SELECT-Anfrage:

SELECT 
  [DISTINCT]
  Attribut |  arithmetrischer Ausdruck |  Aggregatfunktion

Gegeben sei eine Sammlung "leute" mit folgenden Dokumenten:

[
  {   "hausnummer" : 64,   "_id" : {   "$oid" : "50520155cc93742e0d0dac65"   },   "vorname" : "Ulf"   },
  {   "hausnummer" : 64,   "_id" : {   "$oid" : "50520263cc93742e0d0dac7e"   },   "vorname" : "Gandalf, der Pflegehamster"   }
]

In der Relationenalgebra filtert die Projektion Duplikate während SQL Multimengen von Tupeln zulässt. Ein SELET hausnummer FROM leute liefert zwei identische Ergebniszeilen (Tupel). Das optionale DISTINCT filtert die Duplikate: SELECT DISTINCT hausnummer FROM leute liefert dasselbe wie db.leute.distinct("hausnummer").

[
{ "hausnummer" : 64 }
]

Statt alle Attribute/Felder/Spalten auszulesen, gilt es nur "vorname" auszugeben. Der entsprechende SQL-Ausdruck wäre SELECT vorname FROM leute. Im NoSQL-Store lautet die Syntax db.leute.find({}, {vorname:1, _id:0}).

[
  {   "vorname" : "Ulf"   },
  {   "vorname" : "Gandalf, der Pflegehamster"   }
]

Als nächstes soll die Projektion einen arithmetrischen Ausdruck enthalten, in SQL: SELECT hausnummer + 1 FROM leute. Eine Entsprechung in der Anfragesprache des NoSQL-Stores konnte ich erst im Rahmen von MapReduce finden. MapReduce und SQL sind zwei verschiedene Kisten. Mehr dazu unten.

SQL unterstützt folgende Aggregatfunktionen: COUNT(*), SUM(spalte), MAX(spalte), MIN(spalte), AVG(spalte). Der erste ist einfach: db.leute.count(). Dann wird es spannend, egal welche Funktion gewählt wird. Eine Möglichkeit ist MapReduce. Die zählt nicht. Die zweite Möglichkeit nennt sich nicht MapReduce obschon der Anwender eine "reduce"-Funktion selbst programmieren muß. Hier der Code für SUM(spalte): db.leute.group({key: {}, initial: {sum: 0}, reduce: function (doc, out) { out.sum += doc.hausnummer}}). Der Möglichkeiten nicht genug, gibt es noch eine dritte Syntax. Die kommt aber erst bei einer Gruppierung ins Spiel und ist damit an dieser Stelle raus.

[
  {   "sum" : 128  }
]

Zwischenergebnis Projektion

Nochmal: MapReduce zählt nicht. Ich vergleiche die eingebaute Anfragesprache an dieser Stelle.

  • Projektion (Ausblenden von Spalten): SELECT [DISTINCT] Attribut | arithmetrischer Ausdruck | Aggregatfunktion
    • DISTINCT
    • Attribut
    • arithmetrischer Ausdruck
    • Aggregatfunktion
      • COUNT(*)
      • SUM(spalte) (Benutzer liefert Funktion)
      • MAX(spalte) (Benutzer liefert Funktion)
      • MIN(spalte) (Benutzer liefert Funktion)
      • AVG(spalte) (Benutzer liefert Funktion)
  • Selektion (Zeilen suchen)
  • Verbund (Tabellen verknüpfen)
  • Vereinigung (Tabellen vereinigen)
  • Differenz (Tabellen abziehen voneinander)
  • Spalten umbenennen

Die einfache Selektion

Mit der WHERE-Klausel formuliert SQL die Selektion. Diese Betrachtung unterscheidet drei Fälle. Was gruselig aussieht, hilft sogleich beim Vergleich SQL vs. NoSQL-Anfragesprache.

WHERE  
  Konstanten-Selektion: Attribut = | != | < | <= | > | >=Konstante 
  Attribut-Selektion: Attribut = | != | < | <= | > | >= Attribut
  Verknüpfungen: (Attribut = | != | < | <= | > | >= Konstante|Attribut) und|oder|nicht (...)
  Ungewißheitsselektion: Attribut LIKE Konstante (Sonderzeichen: %| _)
  Nullselektion: Attribut IS NULL  

Das erste ist einfach: SELECT * FROM leute WHERE hausnummer = 64 entspricht db.leute.find({"hausnummer&quot: : 64}). Gleichtes gilt für die Paarung SELECT * FROM leute WHERE hausnummer > 1 und db.leute.find({"hausnummer" : {$gt:1}}).

Ein Vergleich von zwei Attrributen ist im NoSQL-Fall nur dann möglich, wenn der Anwender einen JavaScript-Ausdruck bereitstellt. Platt gesagt: der Anwender muß eine Funktion schreiben. Die Entsprechung eines SELECT * FROM leute WHERE hausnummer != vorname ist db.leute.find({$where : "this.hausnummer != this.vorname"}). Das Handbuch des NOSQL-Store merkt an, daß die Selektion mittels $where langsamer ist als die Verwendung der eingebauten Vergleiche.

Im SQL gibt es Verknüpfungen von Bedingungen mit AND, OR und NOT. Auf der anderen Seite sind die Namen $and, $or und $nor. Schachtelung funktioniert, Gleichstand.

LIKE bietet der NoSQL-Store nicht. Dafür einen auf regulären Ausdrücken basierten Textvergleich. LIKE kann mittels eines regulären Ausdrucks emuliert werden. Selbstverständlich kann auch MySQL reguläre Ausdrücke auswerten: RLIKE.

Ohne Schemata müssen drei Fälle beim Test auf NULL unterschieden werden: Dokumente bei denen das Attribut fehlt oder NULL enthält, Dokumente bei denen das Attribut vorhanden ist und den Wert NULL hat, Dokumente bei denen das Attribut nicht vorhanden ist. Alle drei Fälle sind abgedeckt. Damit lässt sich SQL IS NULL ausdrücken.

Zwischenfazit nach der einfachen Selektion

Wieder einmal muß der Anwender selbst Funktionen schreiben, das meiste geht jedoch.

  • Projektion (Ausblenden von Spalten): SELECT [DISTINCT] Attribut | arithmetrischer Ausdruck | Aggregatfunktion
    • DISTINCT
    • Attribut
    • arithmetrischer Ausdruck
    • Aggregatfunktion
      • COUNT(*)
      • SUM(spalte) (Benutzer liefert Funktion)
      • MAX(spalte) (Benutzer liefert Funktion)
      • MIN(spalte) (Benutzer liefert Funktion)
      • AVG(spalte) (Benutzer liefert Funktion)
  • Selektion (Zeilen suchen): WHERE Konstanten-Selektion: Attribut = | != | < | <= | > | &gt=Konstante.. (s.o.)
    • Konstanten-Selektion: Attribut = | != | < | <= | > | >=Konstante
    • Attribut-Selektion: Attribut = | != | < | <= | > | >= Attribut (Benutzer liefert Ausdruck/Funktion)
    • Verknüpfungen: (Attribut = | != | < | <= | > | >= Konstante|Attribut) und|oder|nicht (…)
    • Ungewißheitsselektion: Attribut LIKE Konstante (Sonderzeichen: %| _) (Emulation über Regular Expression, MySQL-Gegenstück: RLIKE)
    • Nullselektion: Attribut IS NULL
  • Verbund (Tabellen verknüpfen)
  • Vereinigung (Tabellen vereinigen)
  • Differenz (Tabellen abziehen voneinander)
  • Spalten umbenennen

Noch mehr zur Selektion: die geschachtelte Anfrage

Bereits in SQL-89 gibt es Unteranfragen, geschachtelte Anfragen, die unter WHERE vorkommen können.

WHERE  
   ...
  Quantifizierte Bedingung: ALL, ANY, IN, EXISTS

"Gibt’s doch!" mögen jetzt alle Leser aus rufen, die den Namen des NoSQL-Stores längt kennen. Falsch! Es gibt die Prädikate, es gibt keine geschachtelten Anfragen für, die Prädikate gedacht sind. db.leute.find({"hausnummer" : { $in : [1, 64] }}) entspricht SELECT * FROM leute WHERE hausnummer IN (1, 64).

Hingegen ist folgender SQL-Ausdruck nicht direkt in der Sprache des NoSQL-Store auszudrücken: SELECT * FROM leute WHERE hausnummer IN (SELECT hausnummer FROM pflegeeltern). Wie man leicht sieht, kommen wir hier in den Bereich des Verbunds.

Vorläufiges Fazit

Das Fazit ist nicht zu übersehen: SQL ist die reichere Anfragesprache.

  • Projektion (Ausblenden von Spalten): SELECT [DISTINCT] Attribut | arithmetrischer Ausdruck | Aggregatfunktion
    • DISTINCT
    • Attribut
    • arithmetrischer Ausdruck
    • Aggregatfunktion
      • COUNT(*)
      • SUM(spalte) (Benutzer liefert Funktion)
      • MAX(spalte) (Benutzer liefert Funktion)
      • MIN(spalte) (Benutzer liefert Funktion)
      • AVG(spalte) (Benutzer liefert Funktion)
  • Selektion (Zeilen suchen): WHERE Konstanten-Selektion: Attribut = | != | < | <= | > | &gt=Konstante.. (s.o.)
    • Konstanten-Selektion: Attribut = | != | < | <= | > | >=Konstante
    • Attribut-Selektion: Attribut = | != | < | <= | > | >= Attribut (Benutzer liefert Ausdruck/Funktion)
    • Verknüpfungen: (Attribut = | != | < | <= | > | >= Konstante|Attribut) und|oder|nicht (…)
    • Ungewißheitsselektion: Attribut LIKE Konstante (Sonderzeichen: %| _) (Emulation über Regular Expression, MySQL-Gegenstück: RLIKE)
    • Nullselektion: Attribut IS NULL
    • Quantifizierte Bedingung: ALL, ANY, IN, EXISTS (Keine Unteranfragen)
  • Verbund (Tabellen verknüpfen)
  • Vereinigung (Tabellen vereinigen)
  • Differenz (Tabellen abziehen voneinander)
  • Spalten umbenennen

MapReduce zählt nicht

Das vorläufige Fazit ist schon rot. Beim Fehlen des Selbstverbunds wird manch Programmierer rot. Und bei MapReduce werde ich es. Eine Anfragesprache sollte ad-hoc Formulierungen erlauben ohne ein Programm schreiben zu müssen. MapReduce benutzen bedeutet Funktionen und damit ein Programm zu schreiben. Eine Anfragesprache sollte optimierbar sein. Für MapReduce gibt es praktische keine Optimierungsregeln. Eine Anfragesprache sollte sicher sein indem Sinne, daß sie endlose Schleifen oder Ergebnisse verhindert. Jede Operation soll auf Mengen von Daten gleichzeitig arbeiten und nicht nur über einzelne Sätze/Tupel/Dokumente navigieren.

MapReduce ist raus in dieser Diskussion. Wer MapReduce sagt, der muß sich fragen warum er MySQL nicht ausschließlich über die InnoDB API anspricht. Ob nun JavaScript oder C ist doch egal…

Rant?

Nein. Es gibt einiges zu lernen für MySQL von den NoSQL-Stores. Aber ob diese konkrete Anfragesprache dazu gehört…

Happy hacking!

@Ulf_Wendel Follow me on Twitter

10 Comments

  1. Apache Hive erlaubt ad-hoc SQL Subset, das in MapReduce umgeschrieben wird. Hilft das?

  2. Ich mag den Begriff “NoSQL” nicht. Mein Toaster ist NoSQL…

    Wenn Leute “NoSQL” sagen, meinen sie meistens einen Key-Value-Store ohne komplexe Strukturen, sondern mit einer einfachen GET/PUT API, die auf den Key zielt.

    Und das beißt sich mit SQL überhaupt nicht. Ein MySQL-Server ist ein SQL-Layer auf einer Ebene von Storage-Engines, zB InnoDB, NDB, MyISAM.

    So ist es also möglich, SQL auf einem Key-Value-Store zu packen. Damit gewinnt man an Entwicklungsgeschwindigkeit. Einen Join in SQL schreibe ich nachts nach 10 Bier. Das in Key-Value-API-Calls umzusetzen wird weh tun.

    Zu MapReduce: MapReduce ist auch eine sehr einfache API. Aber dank Hive gibt es einen Ãœbersetzer von SQL nach MapReduce, der im Prinzip das gleiche macht wie der MySQL-Server.

    Kernel-C-Programmierung macht beim ersten Mal Spaß, danach will man Scriptsprachen benutzen, um sich nicht die Finger zu brechen.

    Oder wie es so schön heißt: “He who has never hacked sendmail.cf has no soul; he who has hacked sendmail.cf more than once has no brain.”

  3. Es gibt überall solche und solche Toaster. Ich schaute mir ein konkretes System an und verglich die Anfragesprache mit SQL. Dabei kam heraus, daß SQL mächtiger ist als die konkrete Anfragesprache des einen NoSQL-Systems.

    MapReduce ist nicht mit SQL zu vergleichen. Das sind zwei paar Schuhe. Deswegen ist es raus aus dem Vergleich.

    Skriptsprache oder C? Habe ich C, dann habe ich auch die Skriptsprache…

  4. MapReduce ist in dem Beispiel mit den direkten APIs von InnoDB, NDB oder BDB zu vergleichen. Der MySQL-Server legt eine SQL-Ebene drüber. Und das tut Hive bei MapReduce.

    Gib mir Deine SQL-Query und ich lasse die auf meinem Hadoop-Cluster laufen.

  5. MapReduce ist jenseits meines Vergleichs. Im Rahmen dieses Vergleichs/Blogposts betrachte ich MapReduce als keinen Maßstab. Anders als SQL lasse ich es nicht als Anfragesprache gelten, u.a. weil es nicht auf Mengen sondern auf einzelnen Zeilen/Tupeln/Dokumenten operiert.

    Ich wüsste nicht, warum ich Dir irgendeine SQL-Query geben sollte. Es ist völlig egal ob MapReduce das umsetzen kann. MapReduce ist auf einem zu niedrigen Level, um Gegenstand dieses Vergleichs zu sein.

  6. Deine Basisoperationen einer Relationenalgebra unterscheiden sich leicht von denen, die man in der klassischen Literatur findet. Vergleiche dazu auch http://blog.koehntopp.de/archives/2844-Was-bedeutet-eigentlich-Relationale-Algebra.html bei mir. Normal findet man Selektion, Projektion, Join (LEFT JOIN und INNER JOIN unterscheiden sich im Grunde nur in der Definition des Gleichheitsoperators bei NULL-Werten), Rename und Aggregation.

    Im Ergebnis macht das aber bei Deiner Auswertung mit Hinblick auf NoSQL-Sprachen keinen Unterschied, d.h. die Folgerungen aus Deinem Artikel bleiben unberührt.

    Die Argumente pro NoSQL sind in der Regel

    – Schemafreiheit. Das ist Unsinn, so etwas gibt es nicht (http://blog.koehntopp.de/archives/3056-Schemaless.html, http://blog.koehntopp.de/archives/3057-Zusammenfassung-Schemaless.html, jeweils auch die Kommentare).

    Die korrekte Behandlung des Problems wäre a) ein schnelles ALTER TABLE (man hängt sich also an einem Implementationsproblem einer konkreten, populären Implementierung auf) und b) die Einführung von NFNF (Non-First Normal Form) Datentypen wie Arrays oder Hashes als Spaltentyp (Der Hadoop Hive-Compiler bietet so etwas zum Beispiel an, aber im Kontext einer SQLish Abfragesprache).

    – horizontale Skalierbarkeit. Also die Möglichkeit des Sharding von Tabellen.

    Der Preis, den man dafür bezahlt ist hoch: Man begibt sich in das Gebiet der verteilten Datenbanken, und behielte man die Relationenalgebra als Abfragesprache muß man nun verteiltes Locking/Transaktionen, verteilten Join und verteilte Aggregation als Probleme lösen.

    Verteilte Aggregation ist im Grunde Map-Reduce mit einem groß geschriebenen Reduce.

    Verteiltes Locking und verteilte Transaktionen sind ein gelöstes Problem, aber die Lösungen sind teuer: 2PC und seine Nachfolger (3PC, …, Paxos) sind Synchronisationsprimitive, die sehr sensitiv auf Netzwerklatenz reagieren. Minimiert man den Einsatz dieser Synchronisationsprimitive, indem man ACID als Default aufgibt, und beschränkt man sich auf spezielle, idempotente (replayable, wiederabspielbare) Statements, wäre im Sinne eines mathematischen Beweises zu zeigen, daß dies immer noch genau so ausdrucksstark ist wie voll ACID SQL. Hat man das getan, gelangt man zu einem lebensfähigen BASE-Modell. Das heißt, man landet dann auf einem Queueing-System mit asynchronen Queues, wie es etwa MySQL Replikation ja darstellt.

    Und verteilter Join ist ein hartes Problem, für das es aber Lösungen gibt (Condition Pushdown, Batched Key Access, etc). MySQL Cluster ist bei aller Kritik eine erstaunlich gute Implementierung eines solchen Problems.

    NoSQL-Systeme haben in der Regel keine Antworten auf diese Probleme. Sie offerieren Sharding zu einem hohen Preis (keine Transaktionen, kein Join), und wälzen die Lösung dieser in der Informatik durchaus als “schwierig” bewerteten Probleme auf den Anwendungsprogrammierer ab. Das heißt, nicht nur implementiert der Kern der NoSQL-Engine diese Dinge nicht, sondern es existieren in der Nutzercommunity solcher Systeme auch keine Client Side Libraries, die sich generisch oder exemplarisch mit der Behandlung dieser Probleme beschäftigen: Jedem Anwendungsentwickler ist es also wieder selbst überlassen, eine Lösung für diese Dinge zu finden – in der Regel falsch, ineffizient oder halt gar nicht.

    Außerdem braucht jedes verteile, shardende NoSQL-System bei aller horizontalen Skalierbarkeit am Ende halt doch eine lokale Storage Engine, die Persistenz macht. Schaut man sich Beispiele an, bekommt man das Grauen: Jedes einzelne dieser Systeme ist lokal schlechter als MyISAM, und das ist nicht leicht.

    Hier MongoDB als Beispiel zu nehmen und zu kritisieren ist pointless, man schlägt keine wehrlosen, blutenden Gegner, die am Boden liegen. CouchDB ist da schon besser, stirbt aber an der dümmsten möglichen Implementierung von Vacuum und, wenn jemals von der Platte gelesen wird, auch in Disk Seeks. Redis – single threaded und full dump+delta machend – hat mindestens dieselben Probleme wie NDB-Cluster: Ein full dump von 192GB Speicher auf eine SSD dauert nun mal 15 Minuten und das ist als Abstand für Checkpoints in vielen Fällen zu groß. Und single threaded auf einer 16 Core-Box ist auch ein wenig lachhaft – startet man aber 16 Redis-Instanzen auf so einer Karre, gibt es nix ab Werk, das die Full Dumps dieser Instanzen orchestrieren würde (und schreibt man sich das, stellt man fest, daß es sich tot seekt, selbst auf einer SSD und selbst dann, wenn nur eine Instanz zur Zeit dumped).

    In der Zusammenfassung kann man sagen, daß es schon sinnvoll wäre, 40 Jahre Forschung, MVCC und das Buch von Gray nicht ganz zu ignorieren, wenn man mitspielen möchte.

  7. Schade, daß man Kommentare hier nicht “liken” kann :)
    Danke für diesen überaus lesenwerten Kommentar, Kris.

  8. Vielen Dank für den langen Kommentar, der mich hier unmittelbar nach dem Aufwachen im Bett erwarten. Was mich erwartet ist ein Todesstoß dessen Breite ich mir noch aufsparen wollte…

    NF^2, PNF ist bekannt und auf dem Radar. Weil ich bislang keine schöne Anfragesprache fand, ging ich absichtlich nicht auf geschachtelte Typen ein. Hier sitze ich seit drei Tagen gedanklich fest. Vielleicht könnte man sogar von funktionalen Shardunits sprechen, wenn man das ganze flott hinkriegt und mit nesten/entnesten verwurstelt.

    Zu den verteilten Systemen schnapp Dir mal “Replication: Theory and Practice”, Pedone. Es gibt ja einige “…” zwischen 3PC und Paxos, die interessant sind.

    Das von mir ansatzweise verprügelte Kind ist das Lauteste im Vorhof – genau das sollte es sein. CouchDB und Redis saßen schon wieder im Unterricht.

    Gute Bücher… der Gray ist schwer zu kriegen im Original.

  9. Pingback: Die wunderbare Welt von Isotopp