Berechnung der Kosten von Block Nested Loop Joins

Question

Ich versuche, die Kosten für die (effizienteste) Block Nested Loop Join in Bezug auf NDPR (Anzahl der Datenträger Seite liest) zu berechnen. Angenommen, Sie haben eine Abfrage der Form:

SELECT COUNT(*) 
FROM county JOIN mcd 
ON count.state_code = mcd.state_code 
AND county.fips_code = mcd.fips_code 
WHERE county.state_code = @NO 

wo @NO für einen Zustandscode auf jeder Ausführung der Abfrage ersetzt wird.

Ich weiß, dass ich die NPDR ableiten kann mit: NPDR(R x S) = |Pages(R)| + Pages(R)/B - 2 . |P ages(S)|

(wo die kleinere Tabelle als äußere verwendet wird, um weniger Seite zu erzeugen, liest Ergo:. R = Kreis, S = mcd).

Ich weiß auch, dass die Seitengröße = 2048 Bytes

Pointer = 8 byte 
Num. rows in mcd table = 35298 
Num. rows in county table = 3141 
Free memory buffer pages B = 100 
Pages(X) = (rowsize)(numrows)/pagesize 

Was ich versuche, ist, herauszufinden, wie die „WHERE county.state_code = @NO“ meine Kosten auswirkt?

Danke für Ihre Zeit.

Answer 1

Zuerst ein paar Beobachtungen in Bezug auf die Formel, die Sie schreibt:

• Ich bin mir nicht sicher, warum es Sie „B - 2“ schreiben statt „B - 1“. Aus theoretischer Sicht benötigen Sie eine einzelne Pufferseite, die in Beziehung S gelesen werden soll (Sie können dies tun, indem Sie jeweils eine Seite lesen).

• Stellen Sie sicher, dass Sie alle Klammern verwenden. Ich würde die Formel schreiben:
  NPDR(R x S) = |Pages(R)| + |Pages(R)|/(B-2) * |Pages(S)|

• Die alle Zahlen in der Formel werden müßten aufzurunden (aber das ist Erbsenzählerei).

• Die Erklärung für die allgemeine BNLJ Formel:
  

  • Sie lesen in so viele Tupel von der kleineren Relation (R), wie Sie Wert im Speicher (B-1 oder B-2 Seiten halten Tupel).

  • Für jede Gruppe von B-2 Seiten im Wert von Tupeln, haben Sie dann die ganze S Beziehung lesen (| Seiten (S) |) R. die kommen für diesen speziellen Bereich der Beziehung führen

  • Am Ende des Joins wird die Relation R genau einmal gelesen und die Relation S wird so oft gelesen, wie wir den Speicherpuffer gefüllt haben, nämlich |Pages(R)|/(B-2) mal.

Nun ist die Antwort:

• In Ihrem Beispiel ein Auswahlkriterium Relation R angewandt (Tabelle Land in diesem Fall). Dies ist der WHERE county.state_code = @NO Teil der Abfrage. Daher gilt die generische Formel nicht direkt.

• Beim Lesen von Relation R (d.h., Tabelle Land in Ihrem Beispiel), können wir alle nicht-qualifizierenden Tupel verwerfen, die nicht mit den Selektionskriterien übereinstimmen. Unter der Annahme, dass es in den USA 50 Staaten gibt und dass alle Staaten die gleiche Anzahl von Landkreisen haben, qualifizieren sich nur 2% der Tupel in der Tabelle Land im Durchschnitt und müssen im Speicher gespeichert werden. Dies reduziert die Anzahl der Iterationen der inneren Schleife des Joins (d. H. Die Anzahl der Male, die wir benötigen, um Relation S/Tabellen-mcs zu scannen). Die 2% -Zahl ist offensichtlich nur der erwartete Durchschnitt und wird sich abhängig vom tatsächlich gegebenen Zustand ändern.

• Die Formel für Ihr Problem wird daher:
  NPDR(R x S) = |Pages(County)| + |Pages(County)|/(B - 2) * |Counties in state @NO|/|Rows in table County| * |Pages(Mcd)|