Datenbanken - Lernzusammenfassung

Abfrageoptimierung

Wie Datenbanken SQL-Abfragen intern optimieren, umschreiben und ausführen

Definition: SQL-Abfragen so ausführen, dass sie möglichst schnell laufen und wenig Rechenaufwand verursachen. Die interne Struktur wird verändert - das Ergebnis bleibt immer identisch.

Optimierungsprozess

1
SQL-Abfrage einlesenParser erzeugt einen internen Syntaxbaum (Parse Tree)
2
Relationale AlgebraSyntaxbaum wird in algebraischen Ausdrucksbaum überführt
3
Query RewritingOptimizer schreibt den Ausdruck äquivalent, aber effizienter um
4
Ausführungsplan wählenAus mehreren möglichen Plänen wird der kostengünstigste ausgewählt

Relationale Algebra

SQL wird intern in algebraische Ausdrücke umgewandelt. Grundlage der Datenbankoptimierung.

σ - Selektion

Filtert Zeilen anhand einer Bedingung. Entspricht der WHERE-Klausel.

π - Projektion

Wählt bestimmte Spalten aus. Entspricht den Spalten im SELECT.

⨝ - Join (Verbund)

Verknüpft zwei Tabellen anhand einer gemeinsamen Bedingung. Entspricht JOIN.

Merksatz

Erst σ (filtern), dann π (projizieren) - das ist effizienter! Zuerst die Datenmenge reduzieren, dann Spalten auswählen.

-- SQL-Abfrage:
SELECT lname FROM l WHERE l.stadt = 'Paris';

-- Relationale Algebra:
π lname( σ stadt='Paris'(l) )
-- Erst filtern (σ), dann projizieren (π)

Query Rewriting

Das DBMS schreibt SQL-Abfragen automatisch um. Ergebnis bleibt gleich, Ausführung wird effizienter.

Predicate Pushdown

WHERE-Filter werden so früh wie möglich angewendet - vor Joins. Weniger Daten müssen geladen werden.

Projektion vorziehen

Nur wirklich benötigte Spalten werden gelesen. SELECT * wird auf tatsächlich verwendete Spalten reduziert.

Subquery-Elimination

Korrelierte Subqueries werden, wenn möglich, in effizientere JOIN-Operationen umgeschrieben.

Äquivalenzregeln

Optimizer nutzt algebraische Äquivalenzen, z.B. σ(A∧B) = σ(A)∘σ(B), um Ausdrücke umzuformen.

EXISTS vs. JOIN + DISTINCT

Schlechter Ansatz: JOIN + DISTINCT

SELECT DISTINCT l.lname
FROM l
JOIN ltp ON l.lnr = ltp.lnr;

JOIN erzeugt mehrere Zeilen pro Lieferant
DISTINCT muss danach alle Duplikate entfernen
Bei großen Tabellen sehr teuer

Besserer Ansatz: EXISTS

SELECT l.lname
FROM l
WHERE EXISTS (
  SELECT * FROM ltp
  WHERE ltp.lnr = l.lnr
);

Prüft nur, ob mindestens 1 Datensatz existiert
Stoppt beim ersten Treffer (Short-Circuit)
Keine Duplikate, kein DISTINCT nötig

Query Optimizer: RBO vs. CBO

Merkmal	Rule-Based Optimizer (RBO)	Cost-Based Optimizer (CBO) ✓
Funktionsweise	Festes Regelwerk ("Index immer vor Scan")	Schätzt Kosten anhand echter Statistiken
Statistiken	Kennt keine Tabellenstatistiken	Nutzt Kardinalität, Histogramme, Selektivität
Entscheidung	Unabhängig von tatsächlicher Datenmenge	Basiert auf I/O, CPU, Zeilenanzahl
Status	Veraltet (Oracle bis v7)	SQL Server, Oracle (ab v8), PostgreSQL, MySQL, MariaDB

CBO Kostenfaktoren

Anzahl Zeilen (Kardinalität) · Index-Selektivität · I/O-Operationen (Festplatte) · CPU-Aufwand (Sortierung, Hashing)

Indexierung

Ein Index ist eine separate Datenstruktur für schnellen Zugriff - ähnlich einem Inhaltsverzeichnis in einem Buch.

Primärindex

Automatisch auf dem Primärschlüssel
Garantiert Eindeutigkeit
In SQL Server = Clustered Index auf PK
Immer vorhanden solange PK definiert

Clustered Index

Bestimmt physische Speicherreihenfolge
Nur EINER pro Tabelle möglich
Tabelle IST der Index (B-Baum)
Sehr effizient für Bereichsabfragen (BETWEEN, >, <)

Non-Clustered Index

Separate Datenstruktur, zeigt auf Zeilen
Mehrere pro Tabelle möglich
Sinnvoll für häufig gefilterte Spalten
Extra Speicher + Pflegeaufwand

Index Scan vs. Index Seek

Index Scan	Index Seek ✓
Liest ALLE Zeilen sequenziell durch	Springt direkt zur gesuchten Zeile im B-Baum
Ähnlich wie vollständiger Tabellenscan	Traversiert nur nötigen Pfad (logarithmisch)
Gut bei geringer Selektivität (viele Treffer)	Extrem effizient bei hoher Selektivität
`WHERE price > 35` (viele Zeilen)	`WHERE tnr = 3` (genau eine Zeile)

Join-Strategien

Nested Loop Join

FOR EACH row_a IN A:
  FOR EACH row_b IN B:
    IF match: output

✓ Eine Tabelle sehr klein

✗ Teuer bei 2 großen Tabellen: O(n×m)

Hash Join

build_hash(A)
FOR EACH row_b IN B:
  probe hash_table

✓ Große, unsortierte Tabellen ohne Indizes

✗ Benötigt Arbeitsspeicher für Hash-Tabelle

Merge Join

sort(A), sort(B)
merge sorted streams
-- sehr I/O-effizient

✓ Daten bereits sortiert / Indizes vorhanden

✗ Sortierung kostet Zeit wenn unsortiert

Partitionierung & Statistiken

Partitionierung

Partition Pruning

Große Tabellen in kleinere, logische Segmente aufteilen. Optimizer liest nur relevante Partitionen.

Range: nach Wertebereichen (z.B. Jahr)
List: nach definierten Werten
Hash: gleichmäßige Verteilung

Statistiken im DBMS

Kostengrundlage des CBO

Zeilenanzahl (Kardinalität) pro Tabelle
Werteverteilung: Histogramme für Spalten
Anzahl eindeutiger Werte (Selektivität)
Veraltet → falscher Plan!

SQL Server: sp_updatestats
Oracle: DBMS_STATS.GATHER_TABLE_STATS

Ausführungsplan analysieren

SQL Server

SET SHOWPLAN_ALL ON

Baumstruktur - Leserichtung: Bottom-Up!

Unten: Zuerst ausgeführt (Clustered Index Scans)
Mitte: Aggregation & Joins (Hash Match)
Oben: Zuletzt (Sort, Filter/HAVING)

Oracle

EXPLAIN PLAN FOR <SQL>;

Tabellarisch: Id, Operation, Rows, Cost, Time

access(..) → Join-Bedingung, nutzt Index
filter(..) → Filterbedingung, kein Index

Nachteile & Grenzen

Zu viele Indizes

Beschleunigen SELECT, verlangsamen INSERT/UPDATE/DELETE. Balance ist notwendig.

Veraltete Statistiken

Führen zu suboptimalen Plänen. Regelmäßige Aktualisierung ist entscheidend.

Kleine Datenmengen

Bei wenigen Hundert Zeilen ist Tabellenscan genauso schnell wie Index.

Overhead Planberechnung

Bei sehr einfachen Abfragen kann der Optimierungsaufwand den Gewinn übersteigen.

Optimizer nicht optimal

Bei komplexen Queries mit vielen Joins. Dann helfen Optimizer Hints.

Kein Row-Level Trigger

SQL Server: nur Statement-Level. Oracle hat FOR EACH ROW.

Data Warehouse

Architektur · ETL · Schemata · Materialized Views · Optimierung

Definition (Bill Inmon, 1990): Ein DWH ist eine zentrale, themenorientierte, integrierte, nicht-flüchtige und zeitbezogene Sammlung von Daten zur Entscheidungsunterstützung.

Die 4 Merkmale eines DWH

Themenorientiert

Daten rund um Geschäftsobjekte: Kunden, Produkte, Umsatz

Integriert

Einheitliches Format aus heterogenen Quellen

Nicht-flüchtig

Daten werden nicht gelöscht, sondern akkumuliert

Zeitbezogen

Historische Daten ermöglichen Trendanalysen

OLTP vs. OLAP

Merkmal	OLTP	OLAP
Zweck	Transaktionen (täglicher Betrieb)	Analysen & Berichte
Daten	Aktuell	Historisch
Abfragen	Einfach, sehr häufig	Komplex, selten
Optimiert für	Schreiben	Lesen
Beispiel	Kassensystem, Buchung	Jahresberichte, Dashboards

DWH-Architektur (6 Ebenen)

Quellsysteme

ERP · CRM · Flat Files

Staging Area

Rohdaten temporär

ETL / ELT

Transform · Bereinigen

Core DWH

3NF · Historie

Data Marts

Fachbereichsspezifisch

Reporting

BI Tools · Dashboards

ODS

Operational Data Store - Kurzfristige operative Berichte, nahe an OLTP

Data Lake

Rohdaten in Originalformat (strukturiert & unstrukturiert)

Data Lakehouse

Kombination: Flexibilität des Lake + Struktur des Warehouse

ETL-Prozess

E - Extract

Datenextraktion aus Quellsystemen
Full Load vs. Delta Load
Change Data Capture (CDC)
Formate: SQL, CSV, JSON, XML

T - Transform

Bereinigung (Null-Werte, Duplikate)
Standardisierung & Normalisierung
Aggregationen & Berechnungen
Business-Regel-Anwendung

L - Load

Laden ins Ziel-DWH
Full Load, Incremental, Upsert
Slowly Changing Dimensions (SCD)
Fehlerbehandlung & Logging

ELT (Extract-Load-Transform): Moderne Alternative - Transformation im DWH selbst (Snowflake, BigQuery). Schneller bei großen Datenmengen.

Normalisierung im DWH-Kontext

1NF

Atomare Werte, keine wiederholten Gruppen

2NF

1NF + keine partiellen Abhängigkeiten vom Schlüssel

3NF

2NF + keine transitiven Abhängigkeiten

BCNF

Jede Determinante ist ein Superschlüssel

DWH-Faustregel

Normalisierung verbessert Schreib-Performance & Wartbarkeit · Denormalisierung verbessert Lese-Performance für Analysen

Sternschema vs. Schneeflockenschema

Kriterium	Sternschema	Schneeflockenschema
Normalisierung	1NF/2NF - denormalisiert	3NF - normalisiert
Dimensionen	Alle Attribute in EINER Tabelle (Redundanz)	In Sub-Tabellen aufgeteilt (keine Redundanz)
Join-Ebenen	1 Ebene (Fact → Dim)	Mehrere Ebenen (Fact → Dim → Sub-Dim...)
Lese-Performance	Sehr schnell	Langsamer (mehr Joins)
Speicher	Mehr (Redundanz)	Weniger
Wartbarkeit	Aufwändiger	Einfacher
Empfehlung	BI, OLAP, Self-Service	Großes DWH, häufige Updates, Inmon-Ansatz

Sternschema - Sternschema wählen wenn...

Schnelle Abfrageperformance Priorität
Business Users direkt abfragen (Power BI, Tableau)
Dimensionen ändern sich selten
Data Mart für einen Fachbereich

Schneeflockenschema wählen wenn...

Speicherplatz ist knapp (große Dimensionen)
Dimensionsdaten ändern sich häufig
Hohe Datenintegrität nötig
Unternehmensweites Core-DWH (Inmon)

Praxis-Tipp

Viele DWHs nutzen Hybrid-Ansätze: Core DWH in 3NF (Schneeflockenschema), Data Marts in Sternschema für optimale Balance aus Flexibilität & Performance.

Slowly Changing Dimensions (SCD)

SCD Typ 0

Keine Änderung

Historische Daten unveränderlich. Neue Werte werden ignoriert.

Bsp: Geburtsdatum

SCD Typ 1

Überschreiben

Alter Wert wird überschrieben. Keine Historie.

Bsp: Tippfehler korrigieren

SCD Typ 2 ✓ Häufigste

Neue Zeile

Neue Zeile eingefügt. Alte als inaktiv markiert (gültig_bis). Vollständige Historie.

Bsp: Adressänderung

SCD Typ 3

Neue Spalte

Neuer Wert in neuer Spalte. Alter Wert bleibt. Begrenzte Historie.

Bsp: vorherige_Abteilung

Materialized Views

Normale View	Materialized View
Virtuelle Tabelle	Physisch gespeichertes Ergebnis
Abfrage wird bei Zugriff ausgeführt	Vorberechnetes Resultat
Immer aktuell	Muss regelmäßig refreshed werden
Langsam bei komplexen Abfragen	Sehr schnell bei Lesezugriff
Kein Speicherplatz	Benötigt Speicherplatz

COMPLETE

Vollständige Neuberechnung

FAST

Nur geänderte Daten (mit MV-Log)

FORCE

Fast wenn möglich, sonst Complete

ON COMMIT / ON DEMAND

Zeitpunkt des Refreshs

NoSQL

Klassifizierung · CAP-Theorem · BASE-Theorem · Hadoop

NoSQL = "Not only SQL" - Nicht-relationaler Ansatz ohne feste Tabellenschemata bzw. Joins. Für Anwendungsfälle, bei denen herkömmliche relationale Datenbanken an ihre Grenzen stoßen.

SQL vs. NoSQL - Vergleich

Merkmal	SQL	NoSQL
Datenmodell	Relational (Tabellen)	Key-Value, Document, Wide Column, Graph
Schema	Fest, starr vordefiniert	Dynamisch, schemafrei
Skalierbarkeit	Vertikal (mehr Ressourcen zu einem Server)	Horizontal (weitere Server/Knoten hinzufügen)
Transaktionen	ACID	CAP / BASE
Optimierung	Komplexe Abfragen & Transaktionen	Große Datenmengen & Echtzeitanalysen
Anwendungen	Finanzsysteme, CRM	Big Data, IoT, Echtzeitanalyse

NoSQL-Arten (Core Stores)

Key-Value Stores

Einfachste Form

Sammlung von Key/Value-Paaren. 1 Wert je Schlüssel. Zugriff nur über Schlüssel: get(key), put(key, value)

RedisAmazon DynamoDB

Sehr hohe Datenmenge, geringe Abfragekomplexität

Document Stores

Semistrukturierte Daten

Speicherung von JSON-Dokumenten. Einfache Abfragesprache. Zugriff über Schlüssel.

MongoDBCouchbase

Wide Column Stores

Dynamische Spalten

Tabellen mit Zeilen und sehr vielen dynamischen Spalten. Zugriff über Schlüssel oder SQL-ähnliche Abfragen.

CassandraApache HBaseBigTable

Graph Databases

Knoten & Kanten

Daten als Knoten und Kanten mit Eigenschaften. Datenbankabfragen inkl. Graphenalgorithmen.

Neo4jOrientDB

Geringere Datenmenge, hohe Abfragekomplexität

Größe vs. Komplexität

Key-Value Stores: hohe Datenmenge, geringe Komplexität → Column Families → Document Stores → Graph Databases: geringere Datenmenge, hohe Komplexität

ACID-Prinzip (Recap)

A - Atomicity

Veränderung vollständig oder gar nicht (All or Nothing)

C - Consistency

Von einem konsistenten Zustand in den nächsten

I - Isolation

Transaktionen dürfen sich nicht beeinflussen

D - Durability

Veränderungen sind dauerhaft abgespeichert

CAP-Theorem

Bei verteilten Systemen können nur zwei von drei Eigenschaften gleichzeitig garantiert werden. (Brewer's Theorem)

C - Consistency

Alle Clients sehen zur selben Zeit die gleichen Daten. Lesezugriffe auf jedem Knoten liefern den aktuellen wert.

A - Availability

System muss in vorher definierter Reaktionszeit reagieren. Knotenausfälle beeinflussen andere aktive Knoten nicht.

P - Partition Tolerance

Gesamtsystem bleibt bei Ausfall einzelner Kommunikationsverbindungen lauffähig. Replikation auf mehrere Server nötig.

CA - Consistency + Availability

Kein verteiltes System (kein P). Daten konsistent solange alle Knoten online.

MySQLSQL ServerMariaDB

CP - Consistency + Partition Tolerance

Konsistent & ausfallsicher. Verfügbarkeit wird geopfert - Transaktionen werden blockiert bis alle Knoten synchron.

HBaseMongoDBRedis

AP - Availability + Partition Tolerance

Immer verfügbar, auch bei Knotenausfall. Konsistenz nicht garantiert (Eventually Consistent).

CassandraCouchDBRiak

BASE-Theorem

AP-Ansatz: priorisiert Verfügbarkeit und Ausfallsicherheit über Konsistenz. Gegensatz zu ACID.

B - Basically Available

Benutzer können jederzeit gleichzeitig zugreifen, müssen nicht auf andere Transaktionen warten.

S - Soft State

Daten haben einen vorübergehenden Zustand (Übergangszustand) bis alle Transaktionen abgeschlossen sind.

E - Eventually Consistent

Abfragen können unterschiedliche Ergebnisse liefern je nach Knoten. Konsistenz ist nicht zu jedem Zeitpunkt gewährleistet.

ACID	BASE
Starke Konsistenz	Schwache Konsistenz (veraltete Daten ok)
Isolation	Availability first
Verfügbarkeit eingeschränkt	Best effort Verfügbarkeit
Konservativ (pessimistisch)	Schneller
Zuverlässige Datenqualität	Ungefähre Antworten sind ok

Hadoop

Framework zur Speicherung und Verarbeitung von sehr großen Datenmengen (Big Data) auf vielen Computern gleichzeitig. Basiert auf dem MapReduce-Algorithmus und den Grundideen des Google-Dateisystems.

HDFS

Verteiltes Dateisystem

NameNode verwaltet Metadaten. DataNodes speichern die Datenblöcke. Daten werden aufgeteilt und repliziert.

YARN

Resource Manager

ResourceManager + NodeManager + ApplicationManager. Verteilt Jobs auf CPU/Speicher im Cluster.

MapReduce

Parallele Verarbeitung

Gilt als veraltet. Wird durch DAG-basierte Engines (Apache Spark, TEZ) ersetzt.

Hadoop Common

Basis-Bibliotheken

Stellt grundlegende Tools und Bibliotheken für alle Komponenten bereit.

MapReduce-Ablauf

1
Split (Aufteilen)Datenmenge wird in kleinere Teile aufgeteilt und an verfügbare Nodes verteilt. Jeder Datensatz hat einen Schlüssel-Wert (Key).
2
Map()Map-Funktion generiert Key/Value-Paare aus den Eingabedaten und speichert diese zwischen.
3
Shuffle & SortBerechnete Keys werden den Reduce-Nodes zugewiesen. Reduce-Nodes holen Datensätze entsprechend dem zugewiesenen Key.
4
Reduce()Fasst Key/Value-Paare anhand des Schlüssels zusammen und berechnet die Summe. Ausgabe ist wieder ein Key/Value-Paar.

MapReduce Beispiel - Word Count

Input: "Deer Bear River / Car Car River / Deer Car Bear"
Map: Deer→1, Bear→1, River→1, Car→1, Car→1 ...
Shuffle: Gruppiert gleiche Schlüssel · Reduce: Bear→2, Car→3, Deer→2, River→2

Wann SQL, wann NoSQL?

Eigenschaft	SQL wählen wenn...	NoSQL wählen wenn...
Datenstruktur	Strukturiertes tabellarisches Format	Flexibles Schema, unstrukturierte Daten
Skalierbarkeit	Vertikale Skalierung ausreichend	Horizontale Skalierung für hohen Traffic
Transaktionen	ACID-Compliance entscheidend	Eventually Consistent akzeptabel, Verfügbarkeit Priorität
Abfragen	Komplexe Joins, Aggregationen	Einfache Key-Value-Suchen, verteilte Abfragen
Performance	Konsistenz wichtiger als Geschwindigkeit	Echtzeitverarbeitung wichtiger

Fazit

Weder relationale Modelle noch NoSQL-Modelle sind für alle Projekte gleich gut nutzbar - Use whatever makes your product useful.