1_Datenbankstatistiken

Die Anfrageverarbeitung inbesonders die kostenbasierte Optimierung benötigt statistische Informationen. Diese Statstiken werden im Systemkatalog der Datenbank abgelegt und müssen regelmäßig aktualisiert werden, um ihre Genauigkeit zu gewährleisten.

• Statistken regelmäßig zu aktualisieren ist notwendig und kritisch sein
  • Aktualisierung der Statistik bei jeder Änderungsoperation zu aufwändig, daher
  • Periodische Aktualisierungen zu Zeitpunkten mit geringer Last auf die Datenbank

Werte für Relation

• Für jede Basisrelation R gilt:
  • ntuples(R): Anzahl Tupel in Relation 𝑅 (Kardinalität)
  • bfactor(R): Blockungsfaktor von R (dieser gibt an, wie viele Tupel der Relation R in einen Block passen)
  • nblocks(R): Anzahl der Blöcke zur Speicherung von R

$$\text{nblocks}(R)=\lceil \frac{\text{ntuples}(R)}{\text{bfactor}(R)}\rceil$$

Eineckige Klammern bedeuten das Aufrunden vom Resultat

Werte für Attribute

• Für jedes Attribut A jeder BasisRelation R:
  • ndistict ${}_A(R)$: Anzahl unterschiedliche Werte von A in R
  • min ${}_A(R)$, max ${}_A(R)$: minimaler und maximaler Wert von A in R
  • SC ${}_A(R)$: Selektionskardinalität von A in R. d.h durschnittliche Anzahl der Tupel, die eine Gleichheitsbedingung mit A erfüllen.

Wenn die Werte gleichverteilt sind und mindestens ein Wert die Bedingung erfüllt,

Beispiel

Angenommen, eine Relation R hat 1000 Tupel und das Attribut A hat 10 unterschiedliche Werte. Wenn die Werte von A gleichverteilt sind, erfüllt im Durchschnitt jeder Wert die Bedingung für 100 Tupel (1000 / 10 = 100). Daher ist die Selektionskardinalität SC_A(R) = 100:

Wenn die Werte nicht gleichverteilt sind, können Histogramme verwendet werden, um die Selektionskardinalität genauer abzuschätzen

Selektionskardinalität Gleichheitsbedingung

Abschätzung der Selektionskardinalität für die Bedingungen:

Selektionskardinalität UND/ODER

Abschätzung der Selektionskardinalität für zusammengesetzte Bedingungen:

(Baum-)Index

• Für Index I über Attributmenge A:
  • nlevels ${}_A(I)$: Anzahl Ebenen
  • nlfblocks ${}_A(I)$: Anzahl der Blöckedie Blatt bilden.

Beispiel

Schätzfehler bei Gleichverteilung

Histogramme statt Gleichverteilung

Zusammenfassung

Datenbankstatistiken werden verwendet, um die Kosten verschiedener Ausführungspläne für Anfragen abzuschätzen und den effizientesten Plan auszuwählen. So kann anhand der Selektionskardinalität abgeschätzt werden, wie viele Tupel eine bestimmte Selektionsoperation zurückgeben wird. Diese Information ist wichtig, um zu entscheiden, welche Indizes verwendet werden sollen und in welcher Reihenfolge die Operationen ausgeführt werden sollen.