13 Arten, einen (RDB)-Join zu verstehen

 (justinjaffray.com)
4 Punkte von GN⁺ 2023-07-04 | 1 Kommentare | Auf WhatsApp teilen
  • Der inner join in relationalen Datenbanken ist mehr als nur einfache SQL-Syntax; dieselbe Struktur lässt sich als Abfrage, verschachtelte Schleife, logisches Modell, Typprüfung oder aus algebraischer Sicht unterschiedlich interpretieren
  • In normalisierten Tabellen ist ein Join das praktischste Werkzeug, um Informationen, die ohne Duplikate gespeichert wurden, durch das Verfolgen von Referenzen wieder zusammenzuführen
  • Aus Implementierungssicht kann man ihn so verstehen, dass man Zeilenpaare durchläuft und nur die Kombinationen behält, die eine Bedingung erfüllen, oder dass man aus den Domänen der Spalten nur jene Wertekombinationen auswählt, die in beiden Relationen vorkommen
  • Im Programmiermodell lässt sich ein Join mit flatMap, SQL LATERAL, der Lösung des N+1-Problems in ORMs, trait-basierter Typprüfung in Rust und andThen der Set-Monade erklären
  • Mathematisch zeigen Graphpfade, minimale Modelle, die größte zulässige Relation, die kleinste obere Schranke einer Halbordnung und das Ringprodukt relationaler Ausdrücke dieselbe Eigenschaft eines Joins

In normalisierten Daten wird ein Join zur Abfrage

  • Am praktischsten kann man einen Join als Vorgang verstehen, einen bestimmten Wert abzufragen oder vorhandene Daten um redundante Informationen zu ergänzen
  • Das Beispiel beginnt mit einer Variante, user, country und country_code in einer einzigen Tabelle zu speichern
    • Für jeden gleichen country-Wert wird country_code wiederholt, wodurch Duplikate entstehen
    • Wenn sich Werte häufig ändern, müssen alle Stellen gemeinsam aktualisiert werden, was Fehler und Ineffizienz vergrößert
  • In der normalisierten Form wird die Beziehung zwischen country und country_code in eine separate Tabelle ausgelagert, und die Benutzertabelle verweist nur noch auf country_id
  • Wenn man users und countries über country_id mit INNER JOIN verbindet, erhält man wieder die ursprüngliche Form mit user, country und country_code
  • Im Folgenden wird angenommen, dass implizit über gleichnamige Spalten gejoint wird, ohne sich strikt an die Details der SQL-Syntax zu binden

Implementierungssicht: Join durch Iteration über Zeilen und Spalten

  • Für zwei Mengen R, S und ein Prädikat p durchläuft ein Join alle r ∈ R und s ∈ S und gibt nur die Fälle aus, für die p(r, s) wahr ist
    • Wenn das kartesische Produkt der beiden Kollektionen alle möglichen Zeilenverknüpfungen darstellt, ist der Join die Teilmenge, die die Bedingung erfüllt
  • Spaltenzentriert betrachtet ist die Domäne jeder Spalte die Menge ihrer möglichen Werte, und man durchläuft Kombinationen dieser Spaltenwerte
    • Bei R(a, b) und S(b, c) werden die Domänen von a, b und c durchlaufen
    • Nur wenn (a, b) in R und (b, c) in S enthalten ist, wird [a, b, c] ausgegeben

Join als kompatible alternative Realitäten

  • Das Beispiel mit John und Sally erklärt Joins als Verfahren, bei dem nur kompatible Realitäten übrig bleiben, in denen jede Person nur einen Teil der Informationen hat
  • John kennt die möglichen Kombinationen seines Haustiers und des streunenden Tiers, und Sally kennt ebenfalls die möglichen Kombinationen ihres Haustiers und des streunenden Tiers
    • Wenn John einen Hund hat und das streunende Tier ebenfalls ein Hund ist, und Sally eine Katze hat und das streunende Tier eine Maus ist, können diese Fälle nicht gleichzeitig wahr sein
    • Denn beide müssen dasselbe streunende Tier beobachtet haben
  • Wenn man die beiden Tabellen über stray joint, bleiben nur die Kombinationen aus Johns Haustier, dem streunenden Tier und Sallys Haustier übrig, die sich nicht widersprechen

Joins in Programmiermodellen

  • flatMap ist ursprünglich eine Funktion, die für jedes Element eines Arrays ein neues Array erzeugt und die Ergebnisse aneinanderhängt; sie lässt sich zur Implementierung von Joins verwenden
    • SELECT * FROM r INNER JOIN s ON p lässt sich als r.flatMap(x => s.filter(y => p(x, y))) ausdrücken
    • Die LATERAL-Syntax in einigen SQL-Varianten bringt Joins in eine flatMap-Form
  • Wenn die rechte Seite von LATERAL keine Spalten der linken Seite referenziert, ist sie äquivalent zum kartesischen Produkt
    • Query Decorrelation beruht darauf, Spaltenreferenzen auf der rechten Seite durch aufeinanderfolgende Umschreibungen zu entfernen
  • Auch das in ORMs häufige N+1-Problem lässt sich über Joins erklären
    • Wenn für jede Zeile einer Ergebnismenge zusätzliche Queries ausgeführt werden, sind bei verbindungsbasierten Datenbanken wie Postgres die Fixkosten jeder einzelnen Query hoch
    • Das Ergebnis der Aufforderung an die Datenbank, „alle diese Abfragen auszuführen“, ist ein Join wie users INNER JOIN countries
    • Bei In-Process-Datenbanken wie Sqlite fällt dieses Problem weniger ins Gewicht

Graphpfade und logische Modelle

  • Eine Relation verknüpft zwei Mengen und kann daher als Graph betrachtet werden
    • Die Tabelle users verbindet die Menge der Benutzernamen mit der Menge der country_id-Werte
    • Die Relation zwischen country_id und dem zweibuchstabigen Ländercode lässt sich ebenfalls als eigener Graph darstellen
  • Wenn die rechte Menge des ersten Graphen und die linke Menge des zweiten Graphen dieselbe Vertex-Menge teilen, kann man beide zu einem Ganzen zusammenfassen
  • Listet man alle Pfade auf, die von der linken Menge über den mittleren Vertex zur rechten Menge führen, erhält man den Join der beiden Relationen
  • In der formalen Logik werden Relationen als Prädikate betrachtet, und ein Modell ist die Menge von Fakten, die eine Menge von Aussagen wahr macht
    • Wenn users(A, B) und countries(B, C, D) wahr sind, folgt daraus die Implikation, dass Q(A, B, C, D) wahr ist
    • Es kann mehrere Modelle geben, die diese Bedingung erfüllen
    • Um das übliche Ergebnis zu erhalten, wählt man unter ihnen das kleinste Modell, das die Bedingung erfüllt
    • Dieses kleinste Modell ist identisch mit dem Join-Ergebnis von users und country

Join als Typprüfung

  • Typsysteme im ML-Stil ähneln Prolog und Datalog stark und lassen sich daher join-ähnlich ausdrücken
  • Im Rust-Beispiel werden Relationen als Traits definiert
    • Users und CountryCode übernehmen die Rolle der Relationen
    • Smudge, Sissel, Petee, Canada, UnitedStates, CA, US sind als konkrete Typen definiert
  • Trait-Implementierungen wie (Smudge, Canada): Users und (Canada, CA): CountryCode entsprechen den Zeilen einer Relation
  • Damit (A, B, C) im Join enthalten ist, muss (A, B): Users und (B, C): CountryCode gelten
  • test::<(Smudge, _, CA)>() besteht die Typprüfung, aber test::<(Smudge, _, US)>() scheitert, weil (Canada, US): CountryCode nicht implementiert ist

Join als Operation der Set-Monade

  • Das JavaScript-Beispiel mit Some und None beginnt damit, optionale Records zusammenzuführen
    • Wenn zwei Records dasselbe country haben, werden sie zusammengeführt und Some zurückgegeben
    • Wenn sie nicht kompatibel sind oder kein Wert vorhanden ist, wird None zurückgegeben
  • andThen entpackt den optionalen Wert und wendet die Merge-Funktion an
  • Wenn man bei gleicher combine-Funktion den Container durch Rel ersetzt, lassen sich Mengen von Relationen verarbeiten
    • Rel.map wendet eine Funktion auf alle Zeilen an
    • Rel.andThen hängt die aus jeder Zeile entstehenden Relationen per flatMap aneinander
  • Wenn auf die Relationen users und countries dieselbe combine-Funktion angewandt wird, erhält man ein Join-Ergebnis, in dem Smudge, Sissel und Petee mit ihren Ländercodes ergänzt sind

Die größte zulässige Relation und der Join einer Halbordnung

  • Eine dritte Relation T, die alle Spalten zweier Relationen R und S besitzt und keine neuen Informationen erfindet, wird als zulässig definiert
    • Wenn man irgendeine Zeile aus T auf die Spalten von R projiziert, muss diese Zeile in R vorhanden sein
    • Entsprechend muss sie bei Projektion auf die Spalten von S auch in S vorhanden sein
  • Zum Beispiel ist Smudge, Canada, US nicht zulässig
    • Betrachtet man nur country und country_code, ergibt sich Canada, US, und diese Zeile existiert nicht in S
  • Auch die leere Relation ist zulässig, aber die größte zulässige Relation enthält Smudge-Canada-CA, Sissel-Canada-CA, Petee-United States-US
  • Diese größte zulässige Relation ist der Join der beiden Relationen
  • In der Sicht auf Halbordnungen wird R ≤ Q wie folgt definiert
    • Q enthält alle Spalten von R
    • Wenn man jede Zeile von Q auf die Spalten von R projiziert, erhält man eine Zeile aus R
  • In dieser Halbordnung existiert die kleinste obere Schranke R ∨ S von R und S; sie entspricht genau dem relationalen Join

Join als Ringprodukt

  • Relationen lassen sich auch algebraisch ausdrücken
    • Eine einzelne Zeile wird als Produkt aus Spalten-Wert-Paaren dargestellt
    • Eine Relation wird als Summe mehrerer Zeilen dargestellt
  • Zum Beispiel wird ein Term aus user = Smudge und country_id = 1 zu einer einzelnen Zeile
  • Zur Vereinfachung des Ausdrucks werden zusätzliche Regeln eingeführt
    • Idempotenz: [x = y][x = y] = [x = y]
    • Widerspruch: [x = y][x = z] = 0 if y ≠ z
  • Multipliziert man die Benutzerrelation R mit der Länder-Lookup-Relation S und expandiert mittels Distributiv- und Kommutativgesetz, verschwinden widersprüchliche Terme und nur kompatible Terme bleiben übrig
  • Der verbleibende Ausdruck ist Smudge-1-Canada-CA, Sissel-1-Canada-CA, Petee-2-United States-US; das ist exakt der Join der beiden Relationen
  • Diese Sichtweise kann auch als Tensor Contraction verstanden werden

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-07-04
Hacker-News-Kommentare

  • Seit ich angefangen habe, Joins in räumlichen Dimensionen zu denken, sind sie viel leichter zu verstehen
    Wenn man jede Dimension wie Dim_X, Dim_Y, Dim_Z als eigene Tabelle hält und sie über dieselbe EntityId verknüpft, kann man das so sehen, als würde man die 3-dimensionale Position einer Entität zusammensetzen
    Um 3 Dimensionen zu bilden, braucht man mindestens 2 innere Joins, und nicht-räumliche Dimensionen wie Zeit lassen sich auf die gleiche Weise erweitern
    Wenn man die Zeit nicht einschränkt, wird daraus ein Bericht, der alle Positionen enthält, die eine Entität im Zeitverlauf hatte
    Wenn man das Konzept so verinnerlicht hat, dass man andere Join-Typen im Kopf mit dem Schema „rotieren“ kann, lassen sich auch diese Varianten leichter verstehen

    • Das erinnert an HyperDex. Dort werden Werte attributbasiert in einen mehrdimensionalen Hyperraum gehasht und für Indizes verwendet
      https://dbdb.io/db/hyperdex
    • Das scheint eher nahe an einer Übernormalisierung der Daten zu sein. Bei BCNF würde man normalerweise einfach eine Tabelle wie EntityPosition(EntityId, X, Y, Z) verwenden
      Allerdings erinnert das Zusammensetzen vieler Dimensionsfragmente und der Umgang mit Aggregationen eher an Data Warehousing
    • Ich frage mich schon immer, warum man Syntax wie JOIN oder INNER JOIN verwendet. Es wirkt viel klarer, Tabellen in FROM aufzulisten und die Join-Bedingung im WHERE-Teil wie eine Gleichung auszudrücken
      Wenn in einer komplexen FROM-Klausel mehrere JOINs gemischt sind, wird es schwer lesbar, und äquivalente Bedingungsausdrücke in WHERE zu lesen wirkt intuitiver
    • Ich frage mich, ob man alle Joins so verstehen kann, dass sie Varianten eines Cross Join sind

  • Die Sichtweise Nummer 0 ist: „Ein Join ist ein Operator der relationalen Algebra“
    https://en.m.wikipedia.org/wiki/Relational_algebra
    Der natürliche Join R ⋈ S ist die Menge von Tupelkombinationen mit gemeinsamen Attributnamen und eine relationale Operation, die dem logischen AND entspricht
    ⋈ kann man als kartesisches Produkt betrachten, bei dem Zeilen, die nicht ins Ergebnis gehören dürfen, per Prädikat herausgefiltert werden, und große Teile von SQL lassen sich aus dieser Perspektive gut verstehen

    • In der funktionalen Interpretation der Relationstheorie ist ein Join eine Funktionskomposition; erstaunlich, dass diese Perspektive fehlt
    • In der Erklärung als „verschachtelte Schleifen über Zeilen“ steckt bereits die Sicht auf Cross Product + Prädikat

  • Ich suche seit einigen Tagen Material zur Implementierung von Query Execution/Planning, aber gute Quellen zur Implementierungsseite von Prädikaten, bestehenden Indizes und Joins sind schwer zu finden
    Die Google-Suchergebnisse sind mit Anleitungen zur Nutzung überflutet
    Bisher habe ich nur Material der CMU Database Group gefunden, und das ist ausgezeichnet

    • Zu diesem Thema gibt es ein kostenloses Buch mit 700 Seiten: „Building Query Compilers“
      https://pi3.informatik.uni-mannheim.de/~moer/querycompiler.p...
      Hilfreich könnte auch die TUM-Vorlesung „Database Systems on Modern CPU Architectures“ sein; vom Material aus 2020 gibt es vollständige Videoaufzeichnungen
      https://db.in.tum.de/teaching/ss20/moderndbs/?lang=en
    • Ich weiß nicht, ob es genau die gewünschte Tiefe hat, aber der Optimierungsüberblick und die Query-Planner-Dokumentation von SQLite sind sehenswert
      https://www.sqlite.org/optoverview.html
      https://www.sqlite.org/queryplanner.html
    • In solchen Fällen empfehle ich oft, die Postgres-Dokumentation und den Quellcode zu lesen. Der Code ist auch ziemlich gut lesbar
      https://www.postgresql.org/docs/current/planner-optimizer.ht...
    • Das ist ein ziemlich spezialisiertes Thema, daher ist es schwer, gute Lehrbücher zu finden; es hängt davon ab, wie tief du einsteigen willst und welche Teile dich interessieren
      Query Execution und Query Planning sind praktisch fast getrennte Themen
      Als Arbeit zur Join-Optimierung halte ich das ursprüngliche Selinger-Paper immer noch für das beste
      https://courses.cs.duke.edu/compsci516/cps216/spring03/paper...
      Es unterstützt keine Outer Joins, und es wurden effizientere Verfahren entwickelt, aber für alle, die sich mit Optimierern der System-R-Familie beschäftigen, ist es immer noch vertraut zu lesen
      Auch src/backend/optimizer/README von Postgres enthält viel Material, das man anderswo kaum findet
      Die Vorlesungen von Andy Pavlo an der CMU sind fast die einzigen Online-Quellen, die dieses Thema wirklich erklären, und das PDF „Building Query Compilers“ ist zwar unvollständig, enthält aber zentrale Arbeiten von Moerkotte u. a. und ist daher für moderne Implementierungen sehenswert
      Anwendbare Indizes zu finden ist meist nicht schwer, weil man im Grunde nur prüfen muss, ob ein sargable predicate vorliegt, aber Selektivitätsschätzung ist schwierig, und die Schätzung nach Joins gehört im Optimierer zu den härtesten Problemen überhaupt
      Zum Beispiel ist es nicht trivial abzuschätzen, wie hoch die Gesamtselektivität aller drei Bedingungen ist, wenn A=x AND B=y AND C=z vorliegt und nur Selektivitäts-/Kardinalitätsinformationen für die Indizes (A,B) und (B,C) vorhanden sind
      Es gibt sogar Arbeiten, die zur Lösung dieses Problems einen Solver für „quadratic cone programming“ verlangen
    • Als ich vor dem Suchbegriff query planning noch relational algebra ergänzt habe, kamen auf den ersten Blick deutlich mehr implementierungsnahe Ergebnisse heraus

  • Die 14. Methode ist der Multi-Join; sie wird auch „Worst-Case-Optimal Join“ genannt, aber der Name ist nicht besonders gut.
    Gemeint ist, dass statt jeweils zwei Tabellen zu joinen und dabei fortlaufend Zwischenergebnisse zu erzeugen, drei oder mehr Tabellen ohne Zwischenergebnisse gemeinsam gejoint werden.
    Ein zugehöriger Blogbeitrag und ein kurzes Video gibt es unter https://relational.ai/blog/dovetail-join, das Originalpapier unter https://dl.acm.org/doi/pdf/10.1145/3180143.
    Ich arbeite bei RelationalAI, und wir sowie einige andere junge Datenbankfirmen bringen diesen neuen Join-Algorithmus, der in der Forschung etwa 10 Jahre lang untersucht wurde, auf den Markt.

    • Justins Einführung zu WCOJ ist ebenfalls ziemlich gut.
      https://justinjaffray.com/a-gentle-ish-introduction-to-worst...
    • Wenn man die Eingabe negiert, also in das Komplement der Menge umwandelt, wird das AND des Joins zu NOR, und Tetris nutzt genau das aus.
      Die Worst-Case-Schranke wird dadurch nicht strenger als bei zustandslosen/streaming WCOJs, aber reale Daten haben oft deutlich kleinere Box-Zertifikate.
      Ich habe nicht gesehen, ob Dovetail Join rekursive Abfragen unterstützt, also beliebiges Datalog, bei dem nur die Ausgaberelation angegeben wird und die Zwischenrelationen von der Engine automatisch verarbeitet werden.
      Ich würde gern wissen, ob solche Abfragen unterstützt werden.

  • Es sollte mehr solche Artikel geben, die die Feinheiten des relationalen Modells vor allem Entwicklern auf Anwendungsebene zeigen.
    Auch die Erklärung und Betrachtung aus Sicht der funktionalen Programmierung ist prägnant und überzeugend.

  • Es wirkt, als wäre wieder einmal eine Gelegenheit verpasst worden, das N+1-Problem zu erklären.
    Auch ein Join auf einen nicht geclusterten Index ist immer noch N+1, nur eben N+1 auf der Festplatte statt N+1 über Netzwerk und Festplatte.

    • Das klingt nach „Es hätte auch das X-Problem behandeln sollen, das mich interessiert, und dann wäre es okay gewesen, wenn der Artikel länger wird.“

  • Ein Inner Join ist ein kartesisches Produkt mit einer Bedingung.

    • Zwischen dem Erzeugen eines kartesischen Produkts und anschließendem Filtern per Bedingung und dem direkten Erzeugen der Bedingung besteht ein großer Performance-Unterschied.
      Ein Inner Join mit Gleichheitsbedingung erzeugt die Bedingung direkt, während eine Ungleichheitsbedingung tatsächlich ausgewertet werden muss.

  • Gute Erklärung. Die Aussage „Der richtige Weg ist, Tabellen zu normalisieren“ stimmt für transaktionale Datenbanken, aber in Data Warehouses ist ein gewisses Maß an Denormalisierung weithin akzeptiert.

  • Das Beispiel zur Normalisierung erinnert mich an früher, als ich Tabellen mit numerischen Primärschlüsseln statt Strings entworfen habe, weil ich dachte, sie seien schneller.
    Dann hatte man bedeutungslose ids, und um den tatsächlich gewünschten eindeutigen Wert zu bekommen, brauchte man Joins.
    Irgendwann wurde mir klar, dass man Joins reduzieren kann, wenn zwei Tabellen denselben eindeutigen Schlüssel verwenden, und das war einfach, aber effektiv.

    • Trotzdem habe ich gern in jeder Tabelle ein eigenes id-Feld. Das hilft beim Logging, und man muss sich nicht mit dem „echten“ Schlüssel aus mehreren Feldern befassen.
      Stattdessen legt man auf String-Werte einen eindeutigen Index und, noch wichtiger, die Integritätsconstraints darauf.
      Eine Tabelle voller bedeutungsvoller Strings ist viel leichter zu lesen als eine Tabelle voller numerischer ids oder UUIDs.