Nested-Loop-Join: Wie viele Vergleiche und wie viele Seitenzugriffe?

Angenommen, Sie haben zwei Beziehungen R und S , wobei R 1000 Tupel und 100 Seitenzugriffe hat und S 50 Tupel und 25 Seitenzugriffe hat.

Angenommen, R ist die äußere Beziehung, wie viele Tupelvergleiche und Seitenzugriffe werden dann durchgeführt?

Und wie viele Seitenzugriffe, wenn R die innere Beziehung ist?

for each tuple r in R do
   for each tuple s in S do
      if r and s satisfy the join condition
         then output the tuple (r,s)

Um herauszufinden, wie viele Tupelvergleiche durchgeführt werden, muss ich 1000 * 50 = 50000 durchführen, da der Algorithmus dies "für jedes" Tupel ausführt und wir insgesamt 1000 Tupel für R und 50 Tupel für S haben Insgesamt 50000 Vergleiche.

Aber woher weiß man jetzt die Seitenzugriffe? Wenn R außerhalb ist, haben wir (1000 Tupel) * (25 Seitenzugriffe für S ) + (100 Seitenzugriffe für R ) = 25100 Seitenzugriffe?

Und wenn R drin ist, dann: 50 * 100 + 25 = 5025 Seitenzugriffe

Ich bin mir nicht sicher, ob es so richtig ist .. oder wie wird das richtig gemacht, bitteee? : /

Wir können SQL Server dazu zwingen, genau dies zu tun und zu sehen, was tatsächlich passiert.

R hat 1000 Tupel und 100 Seitenzugriffe = 10 Tupel / Seite = 806 Bytes / Tupel.
S hat 50 Tupel und 25 Seitenzugriffe = 2 Tupel / Seite = 4030 Bytes / Tupel.

Dies sind die Tabellen:

drop table if exists dbo.R;
drop table if exists dbo.S;
go

create table dbo.R(n int, filler char(785)  not null default '');
create table dbo.S(n int, filler char(3990) not null default '');

Die Füllspaltengrößen wurden abgerundet, um den Zeilenaufwand zu berücksichtigen. Beachten Sie, dass es keine Indizes gibt. Ich habe eine "Zahlentabelle", mit der ich R und S auffülle:

insert dbo.R(n) select Number from dbo.Numbers where Number between 1 and 1000;
insert dbo.S(n) select Number from dbo.Numbers where Number between 1 and 50;

Wir können überprüfen, wie viele Seiten betroffen sind:

set statistics io on;

select * from R
select * from S

Die Registerkarte Nachrichten von SSMS wird angezeigt

Table 'R'. Scan count 1, logical reads 100, ...
Table 'S'. Scan count 1, logical reads 25, ...

Wir haben genau die richtige Anzahl von Seiten. Ein bisschen Jiggery-Pokery wird das Verhalten bekommen, das Sie untersuchen möchten

select *
from dbo.R              -- R will be outer
inner loop join dbo.S
    on r.N = s.N
option
(
  force order,          -- dictate which table is outer and which inner
  NO_PERFORMANCE_SPOOL  -- stop the QO from doing something clever but distracting
);

select *
from dbo.S              -- S will be outer
inner loop join dbo.R
    on r.N = s.N
option (force order, NO_PERFORMANCE_SPOOL);

Dies gibt dies auf der Registerkarte Nachrichten an (innere Tabelle wird vor der äußeren Tabelle aufgelistet)

Table 'S'. Scan count 1, logical reads 25000, ...
Table 'R'. Scan count 1, logical reads 100, ...

Table 'R'. Scan count 1, logical reads 5000, ..
Table 'S'. Scan count 1, logical reads 25, ...

In SQL Server erfolgt die Ausführung der Abfrage zeilenweise. Für jede Zeile in der äußeren Tabelle wird auf die entsprechenden Zeilen in der inneren Tabelle verwiesen. Da es keine Indizes gibt, besteht die einzige Möglichkeit darin, jedes Mal alle Zeilen (dh alle Seiten) aus der inneren Tabelle zu lesen. Für R-join-S haben wir 1.000 äußere Zeilen mal 25 innere Seiten, die 25.000 innere Seitenreferenzen plus natürlich 100 äußere Seitenreferenzen ergeben. Für S-join-R gibt es 50 Zeilen mal 100 Seiten mit 5.000 inneren Seitenreferenzen plus 25 äußeren Seitenreferenzen.

In Bezug auf Tupelvergleiche sind Sie richtig - es wird O (R) xO (S) -Vergleiche geben - 50.000. Dies wird durch einen Blick auf den Abfrageplan unterstützt. Für beide Abfragen beträgt die "Anzahl der gelesenen Zeilen" für die inneren Tabellenreferenzen jeweils 50.000.

Wenn Indizes vorhanden sind, hat der Abfrageoptimierer (QO) andere Optionen als einen Tabellenscan. Rückspulen können für doppelte äußere Schlüssel verwendet werden. Bei nicht übereinstimmenden Schlüsseln dürfen keine Seiten gelesen werden. Im Extremfall, in dem eine Einschränkung besagt, dass keine Übereinstimmungen möglich sind, wird möglicherweise nicht einmal auf die innere Tabelle verwiesen.

Die Wahrheit ist mehr involviert als das, was Sie erkennen. Es ist wahr, dass die äußere Eingabe des Joins 1000 logische Lesevorgänge erfordert, jedoch nur, wenn der Join-Schlüssel eindeutig ist. Ist dies nicht der Fall, kann der Optimierer es vorsortieren und mehrere Zeilen gleichzeitig abrufen und alle übereinstimmen. Für die innere Schleife wird ein vollständiger Scan pro Iteration angenommen. Der Optimierer bevorzugt normalerweise verschachtelte Schleifen, wenn die innere Eingabe indiziert ist. In diesem Fall wird die Anzahl der Seitenabrufe durch die Kardinalität dieses Satzes bestimmt.

Meine 5 Cent - mach dir keine Sorgen um Details der physischen Implementierung. Investieren Sie Ihre Ressourcen in die Perfektionierung des Datenmodells, des Schemas und des Codes. Lassen Sie den Motor sich um verschachtelte Schleifen kümmern.

HTH