Datenbanken: Dbs2FS12Ueb W14 -

Zurück zu Dbs2.

Diese Übung umfasst zwei Teile: Der erste Teil befasst sich mit Indexstrukturen (Aufwand: ca. 1h) und ist eher theoretischer Natur, der zweite Teil ist eine praktische Übung zu Query optimization (Aufwand: ca. 1.5h).

Indexstrukturen ^

Vergleich Indexstrukturen ^

Vergleichen Sie B-Tree, Bitmap und Hash Table Indices anhand der folgenden drei Kriterien:

Für welche Arten von Spalten sind sie am besten geeignet (kleiner/grosser Wertebereich)?
Für welche Arten von Abfragen sind sie am effizientesten?
Wie sieht es mit der Effizienz von Updates aus?

B-Trees ^

Zur Repetition ^

Ein B-Baum mit Grad k hat folgende Eigenschaften:

Jeder Weg von der Wurzel zu einem Blatt hat die gleiche Länge.
Jeder Knoten ausser der Wurzel hat mindestens k und höchstens 2k Einträge. Die Wurzel hat zwischen einem und 2k Einträgen. Die Einträge werden in allen Knoten sortiert gehalten.
Alle Knoten mit n Einträgen, ausser den Blättern, haben n+1 Kinder.
Seien S1, ..., Sn die Schlüssel eines Knotens mit n+1 Kindern. V0, V1, ..., Vn seien die Verweise auf diese Kinder. Dann gilt:
- V0 weist auf den Teilbaum mit Schlüsseln kleiner als S1.
- V1 (i = 1, ..., n-1) weist auf den Teilbaum, dessen Schlüssel zwischen Si und Si+1 liegen.
- Vn weist auf den Teilbaum mit Schlüsseln grösser als Sn.
- In den Blattknoten sind die Zeiger nicht definiert.

Übung ^

Fügen Sie in einen anfänglich leeren B-Baum mit k = 2 die Zahlen eins bis zwanzig in aufsteigender Reihenfolge ein. Wie sieht es mit der Auslastung des B-Trees aus?

Bitmap Index ^

Gegeben ist die folgende Tabelle Person. Wie würde ein Bitmap Index für die Spalte titel aussehen?

person_id	name	titel
1	Alf A. Romeo	Prof.
2	Alma Nach	Dr.
3	Axel Haar	Dr.
4	Dennis Platz	Dr. habil.
5	Egon Zentrisch	Prof.
6	Heinz Fiction	Prof.
7	Jim Beam	Prof.
8	Klaus Uhr	Prof.
9	Sam Sonight	Dr.
10	Theo Dorant	Prof.

Lösungsvorschlag ^

http:files/Ex14.pdf

Query Optimization ^

Ziel ^

Optimierung ist ein wichtiger Teil beim Datenbank Performance-Tuning. In dieser Übung geht es darum, nachvollziehen zu können, wie PostgreSQL intern eine Query ausführt, welche Faktoren dabei eine Rolle spielen und welche Optimierungsmassnahmen daraus abgeleitet werden können.

Dokumentation ^

PostgreSQL Performance-Tipps : postgresql.org/docs/, wichtige Kapitel: 14.1 und 14.2 (Erklärung EXPLAIN)
Weitere Infos zu EXPLAIN: "Explaining Explain" (.pdf.)

Bemerkungen ^

PostgreSQL hält alle Kataloginformationen in Tabellen. Für diese Übung sind Folgende von besonderer Relevanz: pg_stats, pg_class, pg_indexes und pg_attribute. Diese können wie normale Tabellen abgefragt werden. Als Beispiel dient folgende Query:

SELECT * FROM pg_indexes WHERE tablename = 'orders'

Diese gibt uns alle Informationen über definierte Indizes in der Tabelle orders. Statistiken, die der Optimizer für Tabellen hält, können mit der folgenden Query abgefragt werden:

SELECT * FROM pg_stats where tablename = 'orders'

Die Beschreibung dieser Zahlen finden Sie hier. Allgemeine Informationen zu einer Tabelle kann man entweder über eine Query auf pg_class oder über das \d Kommando in psql in Erfahrung bringen.

Vorbereitung ^

Für diese Übung benötigen wir ein Datenset von entsprechender Grösse. Wir verwenden dazu die DVD-Beispieldatenbank "Dell Store2".

Laden Sie die Beispieldatenbank von pgfoundry.org (.tar.gz) oder von diesem Wiki als .tar.gz oder als .zip runter und entpacken Sie sie in ein Verzeichnis Ihrer Wahl. Starten Sie eine Konsole in diesem Verzeichnis.

Erstellen Sie eine neue Datenbank und füllen Sie sie mit den Daten (das Füllen dauert ca. eine halbe Minute):

Variante Windows:
$ createdb -U postgres dellstore2
$ psql -U postgres -f dellstore2-normal-1.0.sql -d dellstore2
Variante Linux:
$ createdb -U postgres dellstore2
$ createlang -U postgres plpgsql dellstore2
$ psql -U postgres -f dellstore2-normal-1.0.sql -d dellstore2

Aktualisieren Sie die Tabellenstatistiken für das query planning mit dem folgenden Kommando:
```
$ psql -U postgres -d dellstore2 -c "VACUUM VERBOSE ANALYZE"
```

Basics Explain mit Seq Scan und Caching Behaviour ^

Verbinden Sie mit der Datenbank dellstore2:
```
$ psql -U postgres -d dellstore2
```

Führen Sie die folgende Query mit aktivierter Zeitmessung aus:

dellstore2=# \timing
dellstore2=# SELECT count(*) FROM customers;

Nutzen Sie nun EXPLAIN ANALYZE mit derselben Query. Wie können Sie sich den grossen Zeitunterschied zur vorhergehenden Messung erklären? Achten Sie auch auf "hot/cold cache". Unter Linux können Sie die Caches folgendermassen leeren um "cold cache performance" zu bekommen (unter Windows tuts ein Reboot):
```
$ pg_ctl stop
$ sudo su -
# sync
# echo 3 > /proc/sys/vm/drop_caches
# logout
$ pg_ctl start -l $PGLOG
```
Mit der folgenden Query können Sie die Datentransferrate für die Tabelle customers herausfinden. Vergleichen Sie diesen Wert bei cold und bei hot cache.
```
dellstore2=> select pg_size_pretty(CAST(pg_relation_size('customers') / 7.994 * 1000 as int8)) AS bytes_per_second;
```
Nutzen Sie die angegebene Dokumentation zu EXPLAIN und versuchen Sie die Zahlen des Query Plans des vorher mit SELECT COUNT... erzeugten Outputs zu analysieren. Nutzen Sie dazu die folgende Formel um den Kostenwert nachzurechnen
```
(disk_pages_read * seq_page_cost) + (rows_scanned * cpu_tuple_cost)
```

wobei seq_page_cost standardmässig 1.0 und cpu_tuple_cost 0.01 ist. Hinweis: disk_pages_read und rows_scanned finden Sie über die Tabelle pg_class heraus.

Führen Sie nun die folgende Query aus:

EXPLAIN ANALYZE SELECT COUNT(*) FROM customers WHERE age < 50;

Wie Sie sehen, wird der Suchbereich ca. um die Hälfe eingegrenzt durch die WHERE Bedingung. Wieso sind die Kosten nicht dementsprechend gesunken?

Index Scan ^

Versuchen Sie eine EXPLAIN Abfrage unter Nutzung des Indizes für die Tabelle customers durchzuführen und analysieren Sie den Query Plan.
In welchen zwei Aspekten unterscheidet sich der Index Scan von dem Seq Scan hauptsächlich?
PostgreSQL kann Indizes kombinieren wenn zwei von diesen relevant sind um eine Query beantworten zu können. Die customers Tabelle hat einen Index sowohl auf customerid als auch auf username. Führen Sie folgende simple Query mit EXPLAIN ANALYZE aus und analyzieren Sie den Query Plan:
```
SELECT customerid, username FROM customers WHERE customerid < 10000 AND username < 'user100';
```

Können Sie sich vorstellen, wieso der Query Optimizer sich entschieden hat einen komplexen Query Plan mit zwei Indizes zu verwenden anstatt einfach nach username zu suchen was zum gleichen Resultat geführt hätte?

Aggregate Scan ^

Nutzen Sie eine Aggregate Function wie AVG, MAX oder SUM auf der Tabelle customers mit Hilfe von EXPLAIN ANALYZE. Interpretieren Sie den Query Plan.
Verwenden Sie eine Aggregate Function zusammen mit einem Index damit nicht mehr jede Row in der Tabelle gelesen werden muss.

Nested Loop ^

Führen Sie die folgende Query aus:

EXPLAIN ANALYZE SELECT * FROM orders, orderlines WHERE orders.totalamount = 329.78 AND orders.orderid = orderlines.orderid;

Versuchen Sie die berechneten Werte nachzuvollziehen. Was kann bei einem Nested Loop schief gehen?

Lösungsvorschlag ^

http:files/query_optimization.pdf