cross join



  • Guten Tag,

    kurze Verständnisfrage.
    ich habe 3 Tabellen A B C

    Wenn ich Daten abfrage über alle 3 Tabellen wird doch generell ein Cross join
    gemacht oder nicht?

    Meine Ergebistabelle hätte also eine Gesamtzeilenanzahl von
    Anzahl Datensätze A * Anzahl Datensätze B * Anzahl Datensätze C

    und auf diese Ergebnistabelle wird dann die Where-Klausel angewand.

    Die Anzahl der Datensätze in der Ergebnistabelle ist unabhängig von inner join, left join etc richtig?

    Grüße
    Stephan

    PS: Ich frage weil wir hätten in unserem Beispiel 3 Tabbellen.
    A 900000 Datensätze
    B min 900000 Datensätze
    C 200000 Datensätze

    das wären 162 Billiarden Datensätze, aus der mithilfe der Where_Klausel das Richtige Ergebnis selektiert wird?



  • adonis schrieb:

    ich habe 3 Tabellen A B C

    Wenn ich Daten abfrage über alle 3 Tabellen wird doch generell ein Cross join
    gemacht oder nicht?

    Es wird das gemacht was du schreibst.
    Wenn du schreibst SELECT ... FROM a, b, c ... dann bekommst du einen CROSS JOIN.
    Wenn du schreibst SELECT ... FROM a CROSS JOIN b ... dann bekommst du auch einen CROSS JOIN.
    Wenn du schreibst SELECT ... FROM a XXX JOIN b ... dann bekommst du einen XXX JOIN. Wobei XXX dann LEFT, RIGHT oder FULL OUTER sein kann.

    adonis schrieb:

    Meine Ergebistabelle hätte also eine Gesamtzeilenanzahl von
    Anzahl Datensätze A * Anzahl Datensätze B * Anzahl Datensätze C

    und auf diese Ergebnistabelle wird dann die Where-Klausel angewand.

    Ich würde es nicht Ergebnistabelle nennen sondern eher "Liste der Kandidaten" oder so.

    Und bei den anderen JOIN Arten kommen natürlich noch die jeweiligen IN Klauseln dazu.
    (Joins die keine CROSS Joins sind schreibt man normalerweise nicht ohne IN Klausel, weil es ohne IN Klausel irgendwie keinen Sinn macht.)

    adonis schrieb:

    Die Anzahl der Datensätze in der Ergebnistabelle ist unabhängig von inner join, left join etc richtig?

    Jain.
    Kommt drauf an was du mit "Anzahl der Datensätze in der Ergebnistabelle" genau meinst.
    Bei A LEFT JOIN B bekommst du auf jeden Fall alle Zeilen aus A, auch wenn es keine Kombination in A x B gibt für die die "IN" Klausel erfüllt ist.
    Man könnte also sagen dass bei LEFT, RIGHT bzw. FULL OUTER JOIN noch weitere Kandidaten dazukommen.

    adonis schrieb:

    PS: Ich frage weil wir hätten in unserem Beispiel 3 Tabbellen.
    A 900000 Datensätze
    B min 900000 Datensätze
    C 200000 Datensätze

    das wären 162 Billiarden Datensätze, aus der mithilfe der Where_Klausel das Richtige Ergebnis selektiert wird?

    Ja. Wobei das kein Problem ist, vorausgesetzt du filterst so dass das DBMS nicht wirklich alle Kandidaten durchgehen muss.

    Angenommen du willst A x B mit WHERE A.x = B.y. Und angenommen auf B.y gibt es einen Index.

    Dann kann das DBMS z.B. einfach hergehen und alle A Datensätze der Reihe nach durchgehen. Und für jeden A Datensatz im Index für das Feld B.y nachgucken ob es passende Zeilen gibt. Und dann nur die Ergebniszeilen für die im Index gefundenen B Zeilen erzeugen.

    Und das Nachgucken in so einem Index erfordert eben nicht dass man alle Index-Einträge anguckt, sondern geht wesentlich schneller. (Der Index ist ja sortiert und normalerweise als sog. B-Baum implementiert. Dadurch kann man selbst in einem Index über mehrere Milliarden Zeilen relativ schnell gucken ob es einen Eintrag mit einem bestimmten Wert gibt. Dazu muss man üblicherweise nur ein paar wenige Pages laden und ein paar zig bis paar hundert Werte vergleichen.)

    Und das ist nur die einfachste Art zu joinen - nennt sich "nested loops join". Die meisten DBMS beherrschen zusätzlich noch andere Arten zu joinen. Insgesamt kann man damit auf sehr gute Performance kommen. Je nachdem wie viele Zeilen übrig bleiben, und wie gut sich der JOIN eignet optimiert zu werden, kann so ein JOIN wie du ihn beschrieben hast sogar viel schneller sein als wenn du drei ungefilterte SELECT auf die drei einzelnen Tabellen machen würdest.



  • Danke für die ausführliche beschreibung.

    Wie sieht es aus mit den Selektierten Columns, z.B. ein Kontaktdatensatz
    hat ja einige Attribute. Werden die erst angehängt nachdem die Kandidaten Selektiert wurden? Ansonsten könnte man schon in Speicherprobleme laufen oder?



  • adonis schrieb:

    Wie sieht es aus mit den Selektierten Columns, z.B. ein Kontaktdatensatz
    hat ja einige Attribute. Werden die erst angehängt nachdem die Kandidaten Selektiert wurden?

    Kommt drauf an.
    Und zwar darauf was der Optimizer für besser hält.

    Nehmen wir an du joinst zwei Tabellen, A und B, anhand irgend einer ID Spalte.
    Sowas wie

    SELECT * FROM A INNER JOIN B ON A.SomeID = b.SomeOtherID
    

    Und angenommen der Optimizer meint es wäre klug hier einen Nested Loops Join zu verwenden mit A auf der linken Seite (äussere Schleife) und B auf der rechten Seite (innere Schleife). Nehmen wir weiters an dass die Tabelle A keinen Index für das Feld SomeID hat.

    Dann muss die Tabelle A sowieso komplett gelesen werden ("Full Table Scan").

    In dem Fall wird der Optimizer einen Query-Plan erstellen der wirklich die kompletten Daten von A liest und direkt weitergibt, falls für die jeweilige A Zeile ein oder mehrere passende Zeilen in B gefunden werden. Würde ja keinen Sinn machen die Daten zu verwerfen und dann nochmal zu laden. (Ein Nested Loops Join muss ja immer nur eine Zeile pro Tabelle im Speicher halten!)

    In anderen Fällen ... ist es anders 🙂 Speziell wenn Indexe verwendet werden können um zu ermitteln welche Kandidaten "benötigt" werden. Diese Indexe enthalten oft (meist) nicht alle benötigten Felder. Also müssen diese Felder aus den Tabellen geladen werden ("RID Lookup" bzw. "Clustered Index Seek"), nachdem ermittelt wurde welche Kandidaten im Ergebnis übrigbleiben.

    Um das obige Beispiel wieder aufzugreifen: Angenommen es gäbe doch einen Index auf das Feld A.SomeID (der auch nur dieses eine Feld enthält), und die Tabelle A wäre sehr sehr sehr breit. Und angenommen wir bleiben (warum auch immer) bei einem Nested Loops Join mit A auf der linken Seite. Dann könnte man die Query auch so durchführen, dass man auf der linken Seite des Nested Loops Join nicht einen Table-Scan macht (der recht lange dauern würde, weil die Tabelle ja sooooo breit ist), sondern einen Index-Scan (der viel schneller geht, weil der Index ja viel schmäler ist). Und da im Index eben nur SomeID abgelegt ist, müsste das DBMS die restlichen Felder für A dann nachladen. Wenn im Ergebnis ausreichend wenig Zeilen übrig bleiben (sagen wir es werden weniger als 0.1% der Zeilen aus A benötigt), kann das ordentlich viel schneller sein als mit dem Full Table Scan.

    BTW: Wenn man nur weniger Felder abfragt, und diese alle in dem Index enthalten sind den das DBMS für einen Join oder eine Filterbedingung verwenden kann, dann kann das DBMS sich den (teuren) RID Lookup bzw. Clustered Index Seek sparen, und direkt die Daten aus dem Index verwenden. So einen Index nennt man dann (bezogen auf die Abfrage) "covering index", weil er eben alles "abdeckt" was die Abfrage benötigt. Das ist oft eine gute Möglichkeit bestimmte Abfragen zu beschleunigen. Und was dadurch auch klar wird: man sollte sich angewöhnen nur die Spalten zu selektieren die man auch wirklich benötigt. Weil man es dem Optimizer dadurch u.U. ermöglicht einen wesentlich schnelleren Plan zu erstellen.

    adonis schrieb:

    Ansonsten könnte man schon in Speicherprobleme laufen oder?

    Jain.
    Erstmal "materealisiert" ein DBMS nicht alle Kandidaten wenn es nicht muss. Selbst wenn man einen CROSS JOIN ohne jegliche Filter macht, der Abermilliarden von Datensätzen ausspuckt, kann dieses Ergebnis oft "Stück für Stück" erzeugt und an die Anwendung weitergegeben werden. Genau so wie wenn du z.B. zwei verschachtelte Schleifen machst, wobei jede eine Million durchläufe macht. Insgesamt also eine Billion Durchläufe. Wenn jetzt die innere Schleife z.B. einfach eine Zeile auf die Konsole ausgibt, dann gibst du insgesamt eine Billion Zeilen aus. Dein Programm wird aber kaum Speicher benötigen - du gibst ja immer nur eine Zeile aus.

    Und dann sind Datenbank-Server auch nicht darauf angewiesen alle Zwischenergebnisse ins RAM zu packen. Normalerweise hat ein Datenbank-Server eigene Files oder sogar ganze Disks die er als Zwischenspeicher verwenden kann. D.h. selbst wenn ein Server mit nur 1 GB RAM ein Zwischenergebnis von 10 GB benötigt, dann kann er das machen. Auch ohne virtuellen Speicher vom OS. Er packt dann einfach so lange ins RAM bis sein selbst auferlegtes Limit erreicht ist, und dann fängt er an das Zwischenergebnis auf die Disk zu schreiben. Und bei Bedarf wieder nachzuladen. Das bremst natürlich, aber auch das ist etwas was bei den Heuristiken des Optimizers idealerweise berücksichtigt wird.


Log in to reply