Upload
genoveva-stuckert
View
105
Download
0
Embed Size (px)
Citation preview
2Jürgen Broß <[email protected]>
Speichertechnologie
•„Access Gap“ zwischen Hauptspeicher und Sekundärspeicher (wird sich in Zukunft nicht verändern) Anzahl der Plattenzugriffe das bestimmende Kostenmaß
•Plattenparameter:• Zugriffszeit = seek + rotation + transfer
• Übung: kaps (kilobyte accesses per second)
• Kapazität
•Wichtiger Fakt: Faktor bei Erhöhung Plattenkapazität wesentlich größer als der Faktor bei Verringerung der ZugriffszeitLesen und Schreiben von großen Datenmengen wird zum Problem
•Verringerung des Access Gap Problems:• RAID
• Datenbankpuffer
• Neue Speichertechnologien (Flash, MRAM, MEMS, Molecular Storage)
3Jürgen Broß <[email protected]>
Speicherverwaltung
•Abbildung von Relationen auf Sekundärspeicher:• Eine Betriebssystemdatei für jede Relation, jeden Index
Siehe ToyDB, Postgres• Eine Relation in mehreren Betriebssystemdateien• Mehrere Relationen in einer Betriebssystemdatei
z.B. bei Oracle• DBS steuert selbst Magnetplatte an und arbeitet mit den Blöcken in ihrer
Ursprungsform (raw device)
Nachteile bei Speicherung in Betriebssystemdateien?
4Jürgen Broß <[email protected]>
Speicherverwaltung
•Abbildung von Seiten auf (logische) Datenbankdateien:• Direct Mapping
Siehe ToyDB, Nachteile?• Dynamic Block Assignment:
0 1 .. 2 N
Virtual address space:
…
increase of DB space,assign free blocks.
Physical addresses determined by block table
5Jürgen Broß <[email protected]>
Pufferverwaltung
•Ziel: Minimierung der PlattenzugriffeNutze „Lokalität“ der Datenzugriffe
•Puffer: ausgezeichneter Bereich des Hauptspeichers•in Pufferrahmen gegliedert, jeder Pufferrahmen kann Seite der Platte aufnehmen•Aufgaben:
• Pufferverwaltung muß angeforderte Seiten im Puffer suchen (effiziente Suchverfahren)
• parallele Datenbanktransaktionen: geschickte Speicherzuteilung im Puffer, Fix/Unfix
• Puffer gefüllt: adäquate Seitenersetzungsstrategien
6Jürgen Broß <[email protected]>
Pufferverwaltung
•Alter der Seite im Puffer:• Alter einer Seite nach Einlagerung (die globale Strategie (G))• Alter einer Seite nach dem letztem• Referenzzeitpunkt (die Strategie des jüngsten Verhaltens (J))• Alter einer Seite wird nicht berücksichtigt (–)
•Anzahl der Referenzen auf Seite im Puffer:• Anzahl aller Referenzen auf eine Seite (die globale Strategie (G))• Anzahl nur der letzten Referenzen auf eine Seite (die Strategie des jüngsten
Verhaltens (J))• Anzahl der Referenzen wird nicht berücksichtigt (–)
7Jürgen Broß <[email protected]>
Pufferverwaltung
•Weitere Stichpunkte:•Lazy Write•Funktionale Partitionierung des Puffers
8Jürgen Broß <[email protected]>
Recordstrukturen
•Record-File: Logische Datei von Records, die die Tupel einer Relation repräsentieren
•Wie werden Records auf Seiten abgebildet? Seitenorganisation• TID-Konzept
• DB-Key
•Freispeicherverwaltung
•Adressierung von Feldern innerhalb eines Records? Recordstruktur• Feste Längen
• Variable Längen
• BLOBs
9Jürgen Broß <[email protected]>
Recordstrukturen
•RID = Seitennummer + Offset innerhalb der Seite• Probleme?
RID nicht stabil bei Verschieben innerhalb der Seite (Indexe betroffen)
•TID = Seitennummer + Offset in Rowdirectory• Ermöglicht einfaches Verschieben innerhalb der Seite
TID ist stabil in Bezug auf Verschieben innerhalb einer Seite• Verschieben auf andere Seite?
Proxy-Technik (maximal 2 Seitenzugriffe)
1. record2 3
4
10Jürgen Broß <[email protected]>
Recordstrukturen
•DB-Key-Konzept• Jeder Record erhält eindeutige Sequenznummer beim Einfügen• Sequenznummer eindeutig über die Recordlebenszeit• Abbildung auf physikalische Adresse?
Nutze spezielle Zuordnungstabelle, die DB-Keys auf Seitennummer + Row Directory Offset abbildet
• Vorteil:• Proxies nicht nötig, keine Reorganisation während der DB-Lebensdauer
• Nachteil:• Zuordnungstabelle kann sehr groß werden
Zusätzliche Kosten, wenn Zuordnungstabelle nicht in Hauptspeicher passt
11Jürgen Broß <[email protected]>
Recordstrukturen
•Freispeicherverwaltung auf Datenbankdatei-Ebene• Übung: Free Space Tabelle
• Informationen über den Freispeicher jeder Seite
• Tabelle wird zusammen mit Datenseiten in der Datei gespeichert
• Eine „Tabellenseite“ mit N Einträgen wird gefolgt von N Datenseiten
• Übung: Verkettete Liste mit freien Speicherseiten• Zeiger auf die nächste freie Seite
• Freie Seiten untereinander verkettet
12Jürgen Broß <[email protected]>
Recordstrukturen
•Adressierung von Felder: Wie wird der Bytestring innerhalb eines Records interpretiert?
• Feste Längen: Einfach, Information kann aus Schema geholt werden• Variable Längen: Speicherung der Längen nötig
•BLOBs:• Zeiger auf BS-Datei, Spannen über mehrere Records, Dictionary für
Positionierung (siehe auch TOASTED Files in Postgres)
RID byte [] data
FileID RecL FixL val val L val L val
Header: - File identifier- Record length- length of fixed part
Fixed length part:- fixed length attributes- Pointers to variable length fields
Variable length part
13Jürgen Broß <[email protected]>
Indexierung
•Dateiorganisation vs. Zugriffspfade• Dateiorganisation
• Heap: Keine Ordnung, Records werden in nächste Seite mit freiem Platz eingefügt
• Sequential: sortierte Speicherung von Records (meist über Primärschlüssel)
• Hash: gestreute Speicherung der Records
• Mehrdimensional: Siehe R-Baum
• Zugriffspade:• Nur zusätzliche Struktur, die effizienten Zugriff auf Mengen von Records erlaubt
• Auch über nicht Primary Key Attribute (Sekundärindex)
14Jürgen Broß <[email protected]>
Indexierung
•Sequentielle Dateiorganisation:• Indexsequentielle Datei mit ISAM• Probleme?
Vergrößerung der Datei bedingtÜberlaufseiten auf einer Indexebene
Einführung neuer Indexebenenötig, wenn zu viele Überlaufseiten
allgemein: Keine dynamischeAnpassung an wachsende undschrumpfende Dateien
15Jürgen Broß <[email protected]>
Indexierung
•B-Baum• Wichtigste Indexstruktur in Datenbanken• Dynamisch wachsende und schrumpfende Baumstruktur• Balanciert: Alle Blattknoten auf gleicher Ebene• Knoten sind Datenbankseiten• Absteigen im Baum bedeutet Sekundärspeicherzugriff
Höhe des Baums möglichst gering haltenMöglichst hoher Fan-Out in inneren Knoten (Schlüsselkompression, größere Blöcke)
• TIDs in Blättern vs. Records in Blättern (Key Sequenced File)Wann ist welche Variante effizienter?
16Jürgen Broß <[email protected]>
Indexierung
•Hashing:• Basisprinzip: h: {k| k ist Primärschlüssel} {a| a ist physikalische Adresse}• Vorteile:
• Sehr effizienter Zugriff
• Keine zusätzliche Datenstruktur
• Nachteile:• Kein sequentielle Zugriff
• Statisch? Vergrößerung der Datendatei? Hashfunktion muss angepasst werden
• Kollisionsauflösung: Verkettung von Seiten (Chaining mit Overflowbuckets)• Folding: Abbildung beliebiger Primärschlüssel auf Integerwerte
• Dynamische Hashfunktionen:• Extensible Hashing
17Jürgen Broß <[email protected]>
Indexierung
•Bitmap Indexe:• Prinzip: Für jeden Wert v eines Attributs wird Bitliste erstellt, die angibt ob
Tupel i den Wert v hat Länge der Bitlisten = Anzahl der Tupel• Maximal benötigte Anzahl von Bits = (#Tupel)²• Effizient bei Punktanfragen• Einfache Auswertung von komplexer Prädikate (…WHERE P1 & P2 | P3) durch
Bitoperation auf den Listen• Bereichsabfragen mit „Range Coded Bitmaps“
• Kompression von Bitlisten:• Lauflängenkodierung
• Variable Bytelängen Kodierung
18Jürgen Broß <[email protected]>
Multidimensionale Indexierung
•Warum multidimensionale Indexierung?• Unterschied zu Index über mehreren Attributen?
•Anwendungsgebiete:• GeoInformationssysteme: Nearest Neighbour query, Where-am-I query, etc.• Data Cubes: Gruppierung anhand mehrerer Dimensionen
•R-Baum:• Einträge sind d-dimensionale Hyperrechtecke• Blätter alle auf gleicher Ebene• m <= Füllgrad eines Knotens <= M• Bei Suche evtl. Absteigen in mehrere Teilbäume notwendig• Splitoperation unterscheidet sich stark zu der bei B-Bäumen
19Jürgen Broß <[email protected]>
Multidimensionale Indexierung
•K-D-Bäume:• K-dimensionaler binärer Suchbaum
• Alternierend auf jeder Ebene andere Dimension diskriminierend für Abstieg in linken oder rechten Teilbaum
• Die eigentlichen Indexeinträge stehen in den Blättern
• Eigentlich Hauptspeicherdatenstruktur: Abbildung auf Sekundärspeicher (Blöcke einer Festplatte) notwendig!Gruppierung innerer Knoten in Blöcke
20Jürgen Broß <[email protected]>
Anfragebearbeitung
•Überblick:• Ziel/Aufgabe von Anfragebearbeitung• 4 Phasen der Anfragebearbeitung
•Implementierung von Basisoperatoren:• Rückblick: Welche Basisoperationen gibt es?• Terminologie• Interne Operationen: Table Scan, Index Scan, Sortieren• One-Pass-Algorithmen• Two-Pass-Algorithmen
•Anfrageoptimierung• Algebraische (logische) Optimierung• Kostenbasierte Optimierung
21Jürgen Broß <[email protected]>
Anfragebearbeitung
•Überblick:• Ziel/Aufgabe: Möglichst effiziente Ausführung einer SQL-Anfrage bei
gegebener Datenbank und gegebenen Hardwareressourcen (Speicher, CPU, etc.)dominierende Kosten: Plattenzugriffe
• 4 Phasen:
22Jürgen Broß <[email protected]>
Anfragebearbeitung
•Rückblick: Basisoperationen
• Selektion σC
• Projektion
• Duplikateliminierung δ
• Mengenoperationen
• Gruppierung γ (mit Aggregatfunktionen Min/Max/Sum/Avg/Count/…)
• Join (Natural Join, Theta Join, Semi Join, Outer Join)
•Terminologie• One-Pass vs. Two-Pass-Algorithmus
• Unäre vs. Binäre Operationen
• Tuple-at-a-Time vs. Full-Relation Operationen
L- , ,
23Jürgen Broß <[email protected]>
Anfragebearbeitung
•Interne Operationen:• Table-Scan-Schnittstelle: Alle Tupel einer Relation in beliebiger Reihenfolge
genau einmal traversieren.• Index-Scan-Schnittstelle: Alle Tupel mit Attributwerten zwischen min und
max traversieren.• Sortieren:
• Problem: Puffergröße M kleiner als zu sortierende Relation R (Anzahl Blöcke = B(R))Relation kann nicht direkt im Hauptspeicher sortiert werden
• Externes Merge-Sort:• Phase1:
• Lade M Blöcke von R in Speicher und sortiere• Schreibe sortierte Sublisten blockweise auf Platte• Wiederhole bis alle Blöcke von R gelesen und in einer Subliste sortiert
• Phase2:• Es muss sichergestellt sein, dass Anzahl Sublisten <= M-1
sonst nicht mehr Two-Pass• Lade jeweils ersten Block einer Subliste in Pufferseite und merge mit
anderen Listen
24Jürgen Broß <[email protected]>
Anfragebearbeitung
•One-Pass-Algorithmen:• Selektion• Projektion ohne Duplikateliminierung• Mengenoperationen (Voraussetzung min(B(R), B(S)) <= M-1)• Join (Voraussetzung min(B(R), B(S)) <= M-1)
•Two-Pass-Algorithmen:• Duplikateliminierung (Hash-/Sort based)• Mengenoperationen (Hash-/Sort based)• Joins:
• Blockwise Nested Loop
• Index-Join
• Sort-Merge-Join
• Hash-Join
25Jürgen Broß <[email protected]>
Anfragebearbeitung
•Algebraische Optimierung: Umschreiben relationaler Ausdrücke
• Ziel: Finde äquivalente Formulierungen einer Anfrage mit kleineren Zwischenresultaten im Operatorbaum
• Technik basierend auf Heuristiken:• Selektion möglichst früh
• Projektion soweit wie möglich „nach unten“ schieben
• Join statt Kartesischem Produkt+Selektion
• …
• Wichtige Regeln:• Join ist kommutativ und assoziativ
• Vereinigung, Schnitt, Kreuzprodukt sind kommutativ
• Selektionen sind untereinander vertauschbar
• Vorbeischieben von Selektionen und Projektionen unter bestimmten Bedingungen
26Jürgen Broß <[email protected]>
Anfragebearbeitung
•Kostenbasierte Optimierung:• Gegeben: algebraisch optimierter Anfrageplan• Ziel: Finde (physikalischen) Ausführungsplan mit minimalen „Kosten“• Problem: Suchraum extrem groß unmöglich alle möglichen Pläne zu
betrachten
•Vorgehensweise:• Weise logischen Operatoren physikalische Operatoren zu (z.B. Join Index-
Join, Vereinigung Sort-based)• Weise physikalischen Operatoren Kosten zu (Kostenfunktion, Größe von
Zwischenergebnissen)• Finde kostenminimalen Plan durch Anwendung von Suchstrategien
27Jürgen Broß <[email protected]>
Anfragebearbeitung
•Benötigt: Kostenfunktion• Cost = costIO + c*costCPU (c := Gewichtungsfaktor)• Abschätzung der Kosten basierend auf Größe der Zwischenergebnisse• Größe Zwischenergebnissen Selektivität
•Selektivität = Erwartete Größe des Resultats / | Eingaberelation|
•Selektivitätsabschätzung• Annahme über die Verteilung der Attribute: Gleichverteilung, Zipfverteilung,
etc.• Histogramme• Statistiken lernen
•Histogramme: Equi-width vs. Equi-depth•Join Reihenfolge: Greedy, Dynamische Programmierung
28Jürgen Broß <[email protected]>
Recovery
•Fragenkatalog:• Was beschreibt ein Fehlermodell? (Welche Fehler treten auf, welche werden
behandelt? Häufigkeit der Fehler. MTTF/MTTR)• Welche Fehler behandelt typischerweise DBS-Fehlermodell?
(Systemfehler, Transaktionsabbruch, evtl. Plattenfehler, 9-11-Fehler)• Was sind Redo/Undo Operationen?• Verhältnis Recovery/Puffermanagement: Steal/noSteal, Force/noForce• WAL-Prinzip?• Commit-Rule?• WAL, Commit-Rule Zusammenhang mit Steal/noForce Policy?• Was ist Groupcommit?• Welche Logtypen gibt es? Wie unterscheiden sie sich? (Logisches-,
Physisches, Physiologisches Log)• Was sind Checkpoints? Unterschied zu Savepoints!• ARIES