Flattening (de)
Die Übersetzung: Ondřej Veverka
Flattening stellt eine der wenigen Fallen von PostgreSQL für Anfänger (manchmal auch für fortgeschrittene User) dar. Die Veranlassung für diesen Artikel war ein Gespräch mit einem Kollegen, der es vergeblich versuchte, PostgreSQL zum verwenden eines konkreten Indexes zu zwingen. In dieser Hinsicht ist PostgreSQL eine ziemlich störrische Schöpfung, die sich nicht bewegen lässt. Um die Grunde zu verstehen, warum PostgreSQL aufhört, den optimalen Durchführungsprogramm zu finden, müssen wir wenigsten den Prozess der Aussuchung des optimalen Durchführungsprogrammes verstehen. In dem Augenblick, wenn PostgreSQL in Probleme gerät, versucht man üblicherweise verschiedene Variationen einer problematischen SQL Abfrage (z.B. Benützung der Differenzierungstabelle) und dies ist nur ein Schritt vom Kennenlernen des Flatterings entfernt. Workaround ist mehr als einfach, wir müssen uns allerdings im Klaren sein, dass gerade Flattering uns Probleme schafft.
Es handelt sich nicht um ein häufiges Problem, außer einer Erwähnung in Disskussionen habe ich es das erste Mal in meinem Leben gesehen. Wer Diskussionen auf pg_performanceverfolgt, sollte es sofort identifizieren und beseitigen können. Wer hat aber die Zeit, um alle möglichen Konferenzen zu verfolgen. Unter normalen Umständen stellt Flattening kein Problem dar, ganz umgekehrt handelt es sich um eine nützliche Technik, die eine ganze Reihe von Fragen beschleunigt. Außerdem ist es auch eine Technik, ohne die im PostgreSQL die Ansichten nicht effektiv genutzt werden könnten.
Wenn die Prediktion versagt
Die Grundvoraussetzung für ein korrektes Verhalten des Optimaliseurs ist eine relativ genaue Abschätzung der Wirksamkeit von Prädikaten. Die beruht an den sog. Spaltenstatistiken. Zu jedem Attribut der Aufstellung wird ein Histogramm geführt, das heißt die Häufigkeit einzelner Wertklassen. Kann ich das Prädikat in eine konkrete Klasse einordnen, dann kann ich aufgrund der Spaltenanzahl in der Aufstellung anhand einer einfachen Multiplikation die Wirkung des Prädikats bestimmen. Die Spaltenstatistiken werden mit der Option ANALYZE aktualisiert. Solange dieser Befehl nicht gestartet wird, benützt PostgreSQL die Ausgangseinstellung, wenn vorausgesetzt wird, dass die Reihenzeile indirekt proportional der Spaltenanzahl ist. (ca. 1770 Zeilen für 3 Spalten). Die nächste Voraussetzung ist, dass die Verteilung der Werte vom bestimmten Atribut gleichmäßig ist. Genauso wie beim Prachett ist die Wahscheinlichkeit 1:1000000, dass beide Voraussetzungen erfüllt wären. Die Option ANALYZE aktualisiert die Statistiken so, dass aufgrund dieser Statistiken eine glaubwürdige Abschätzung durchzuführen ist:
root=# create table t1(a integer, b integer);
CREATE TABLE
root=# explain analyze select * from t1;
QUERY PLAN
------------------------------------------------------------------------------------------------
Seq Scan on t1 (cost=0.00..29.40 rows=1940 width=8) (actual time=0.004..0.004 rows=0 loops=1)
Total runtime: 0.055 ms
(2 rows)
root=# insert into t1 values(10,20);
INSERT 0 1
root=# ANALYZE t1;
ANALYZE
root=# explain analyze select * from t1;
QUERY PLAN
--------------------------------------------------------------------------------------------
Seq Scan on t1 (cost=0.00..1.01 rows=1 width=8) (actual time=0.009..0.012 rows=1 loops=1)
Total runtime: 0.066 ms
(2 rows)
Dass die Abschätzung der Zeilenanzahl (1940) von der wirklichen Zeilenanzahl (0) abweicht, signalisiert, dass etwas falsch ist. Nach der Option ANALYZE stimmt die Abschätzung mit der wirklichen Zeilenanzahl.
Zu ziemlich interessanten statistischen Angaben kann man gelangen, wenn man den Inhalt der Tabelle pg_stats abbildet (nach Zugabe von zehn zufälligen Angaben in t2 und Durchführung ANALYZE):
root=# select * from pg_stats where tablename = 't1';
schemaname | tablename | attname | null_frac | avg_width | n_distinct | most_common_vals | most_common_freqs | histogram_bounds | correlation
------------+-----------+---------+-----------+-----------+------------+------------------+-------------------------+------------------+-------------
root | t1 | a | 0 | 4 | -0.4 | {13,10,30} | {0.466667,0.2,0.133333} | {11,12,20} | 0.803571
root | t1 | b | 0 | 4 | -0.533333 | {30,20,91} | {0.4,0.133333,0.133333} | {40,45,66,87,90} | 0.996429
(2 rows)
Ein undirekter Beweis der Qualität dieser Lösung ist die Implementierung eines ähnlichen Algorytmus im RDBMS Firebird 2.x und MySQL.x. Nichts desto trotz ist die Abschätzung der Statistiken in folgenden Fällen nicht ganz nach den Regeln:
- Nutzung der Funktion LIKE (eine benützbare Abschätzung ist erst in der Version 8.2 eingebaut)
- Nutzung der Tabellenfunktionen (SRF), wenn vorausgesetzt wird, dass jede Funktion 1000 Zeilen zurückgibt ((korrigiert in 8.3, wenn der Aufwand der Funktion (Atributt COST) und die angenommene Anzahl der zurückgegebenen Zeilen (Atributt ROWS) mindestens grobgeschätzt eingestellt werden können).
root=# create or replace function foo() returns setof t1 as $$begin return; end; $$ language plpgsql rows 100;
CREATE FUNCTION
root=# explain select * from foo();
QUERY PLAN
-----------------------------------------------------------
Function Scan on foo (cost=0.00..26.00 rows=100 width=8)
(1 řádka)
- dass die Daten vom Charakter sind, der nicht ganz genau mit n Klassen aproximiert werden kann, wenn n in der Ausgangsposition gleich zehn ist. Stellen Sie sich vor, man hat 1000 Sammelstellen. 80% davon sind in Städten, wo jede Sammelstelle mindestens einmal täglich wenigstens einen Vermerk generiert. Die restlichen 20% sind in kleinen Orten, Holmen und Orten am Ende der Welt und diese 20% generieren insgesamt einen Vermerk pro Monat. Niemand kann sich wundern, dass im Histogramm mit 10 Klassen diese 20% aufgelöst werden. Die Folge sind optimale Fragen auf 80% der mehrheitlichen Sammelstellen und nicht optimale Fragen auf 20% der minoriten Sammelstellen. Es handelt sich um keinen PostgreSQL-Fehler. Wir können einfach mit der vorbestimmten Unterscheidungsebene die Wirklichkeit nicht genau feststellen. Man kann nur hoffen, dass die Anhebung der Klassenanzahl helfen kann. Technisch ist die Klassenanzahl auf 1000 begrenzt. Das reale Limit beträgt +/- drei hundert Klassen. Das Verlangen nach mehreren Klassen signalisiert etwas Faules in den Eingangsdaten und es ist notwendig eher die Daten zu reinigen oder das Datenmodel zu ändern.
Nehmen wir an, dass ich zufällig Paare aus dem Raum [1..800, 1..100] generieren werde. Dies entspricht 800 Sammelstellen, wo ich einen Wert von 1..100 messen kann. Um die Ungleichmäßigkleit in den Daten zu simulieren, beseitige ich für den Intervall 50-100 90% der Vermerke.
root=# insert into t1 select (random()*800)::int, (random()*100)::int from generate_series(1,15000);
INSERT 0 15000
root=# delete from t1 where a between 50 and 100 and b between 10 and 100;
DELETE 827
root=# analyze t1;
ANALYZE
root=# explain analyze select * from t1 where a = 120; -- baldes Treffen
QUERY PLAN
-------------------------------------------------------------------------------------------------
Seq Scan on t1 (cost=0.00..244.16 rows=18 width=8) (actual time=0.799..11.135 rows=20 loops=1)
Filter: (a = 120)
Total runtime: 11.250 ms
(3 rows)
root=# explain analyze select * from t1 where a = 55; -- Hier ist PostgreSQL bisschen daneben
QUERY PLAN
------------------------------------------------------------------------------------------------
Seq Scan on t1 (cost=0.00..244.16 rows=18 width=8) (actual time=6.151..11.145 rows=1 loops=1)
Filter: (a = 55)
Total runtime: 11.218 ms
(3 rows)
root=# ALTER TABLE t1 ALTER a SET statistics 1000;
ALTER TABLE
root=# analyze t1;
ANALYZE
root=# explain analyze select * from t1 where a = 120;
QUERY PLAN
-------------------------------------------------------------------------------------------------
Seq Scan on t1 (cost=0.00..244.16 rows=20 width=8) (actual time=0.771..12.432 rows=20 loops=1)
Filter: (a = 120)
Total runtime: 12.546 ms
(3 rows)
root=# explain analyze select * from t1 where a = 55; -- Es ist schon besser, ich bin aber am Maximum
QUERY PLAN
------------------------------------------------------------------------------------------------
Seq Scan on t1 (cost=0.00..244.16 rows=10 width=8) (actual time=6.081..10.537 rows=1 loops=1)
Filter: (a = 55)
Total runtime: 10.611 ms
(3 rows)
root=# explain analyze select * from t1 where a between 130 and 150 and b between 0 and 10;
QUERY PLAN
-------------------------------------------------------------------------------------------------
Seq Scan on t1 (cost=0.00..350.46 rows=46 width=8) (actual time=1.106..15.428 rows=47 loops=1)
Filter: ((a >= 130) AND (a <= 150) AND (b >= 0) AND (b <= 10))
Total runtime: 15.605 ms
(3 rows)
-- Für beide Attribute ist PostgreSQL auch nicht in Ordnung (Statistiken am Maximum)
root=# explain analyze select * from t1 where a between 65 and 85 and b between 0 and 10;
QUERY PLAN
------------------------------------------------------------------------------------------------
Seq Scan on t1 (cost=0.00..350.46 rows=5 width=8) (actual time=0.066..14.882 rows=51 loops=1)
Filter: ((a >= 65) AND (a <= 85) AND (b >= 0) AND (b <= 10))
Total runtime: 15.076 ms
(3 rows)
Einer der Gründe, warum die Anschätzung „daneben“ ist, ist der, dass es sich um zufällig generierte Daten handelt, die voneinander unabhängig sind. Auch die Testiermenge ist nicht allzu groß. Die wirklichen Daten haben zum Glück meistens einen anderen Charakter.
Sollte nicht einmal die Veränderung der Klassenanzahl nicht helfen, ist die Frage umzuschreiben und es sind zwei Varianten der Fragen vorzubereiten, evt. die Frage zu zerschlagen und die gespeicherte Prozedur zu schreiben (in unserem Falle die Prädikate meiden, die den Attribut „und“ beinhalten, wie es nur geht). Heißt es, dass die Statistiken auf hunderte von Klassen aufgestockt werden sollten? Ganz sicher nicht. Genauso wenig, wie neue Indexe gebildet werden. Hier würde sich um eine sog. vorzeitige Optimalisierung handeln (ich würde eher die Beifügung überstürzt benützen). Im SQL sollten wir Probleme erst in dem Augenblick lösen, wenn sie entstehen. Weder früher noch später. Dazu gibt es die Logierung der langsamen Fragen zur Verfügung. Die Kontrolle dieses Logos gehört zum täglichen Brot jedes richtigen dba.
Nun sollte klar sein, wann die Optimalisierung der durchgeführten Fragen fehlschlagen kann. Und wie ich erwähnt habe, der Flattening kann ausschließlich in solchen Fällen im Wege stehen. Ganz logisch, wenn alles funktioniert, wie es auch soll, interessiert sich niemand um die Details. Es handelt sich wirklich um atypische Fälle. Dass die Optimalisierung ausnahmsweise nicht funktioniert, ist bekannt. Leider, was in diesem Fall nicht bekannt ist, ist eine robuste Lösung, schnell genug, um ausnahmslos die Abschätzung des Effektes vom Prädikat lösen zu könnten.
Flattening
Was ist der Flattening? Das Flattening ist eine Methode, um eine SQL-Query mit einer differenzierten Tabelle in eine äquivalente SQL-Query ohne eine differenzierte Tabelle zu transformieren. Hier ein Beispiel:
select * from (select * from data where a = 10) s where s.b = 20; --> select * from data where a = 10 and b = 20;
der Außweis:
root=# explain select * from (select * from t1 where a = 20) s where s.b = 20;
QUERY PLAN
----------------------------------------------------
Seq Scan on t1 (cost=0.00..279.60 rows=1 width=8)
Filter: ((a = 20) AND (b = 20))
(2 rows)
root=# explain select * from t1 where a = 20 and b = 20;
QUERY PLAN
----------------------------------------------------
Seq Scan on t1 (cost=0.00..279.60 rows=1 width=8)
Filter: ((a = 20) AND (b = 20))
(2 rows)
Wo liegt das Problem? Im Verstehen der Klammer. In klassischen Programmiersprachen verändern die Klammern die Reihenfolge der Auswertung. Also erwarten wir, dass zuerst a = 10 ausgewertet wird (und adäquat dazu der Index über a ausgewertet wird), und danach über dem Ergebnis b = 20 ausgewertet wird. Dem ist aber nicht so. In diesem Fall dienen die Klammern allein der korrekten syntaktischen Schreibweise und haben mit der Auswertungsreihenfolge nichts zu tun. Wenn PostgreSQL den Index b bevorzugt, so können wir die Query tausendmal absetzen und PostgreSQL wird immer den Index b bevorzugen. Dank des Flattenings kommt die gestellte Query zurück und Pg wählt zwischen den Indices a und b wieder b. Man kann PostgreSQL nicht zu einem bestimmten Index zwingen. Noch einen Schritt zurück - Warum diese Query? Man benutzt solche Queries oft in der falschen Hoffnung, dass man PostgreSQL den korrekten Index in diesem Moment mitgeben könne, wenn PostgreSQL aufgrund falscher Statistiken den Überblick über die Situation verloren hat. Mann beachte, dess es nicht einfach gehen wird.
Nochmal zu dem Beispiel zurück. Wer stellt so anspruchsvolle Queries? Niemand. Und doch benutzt sie jeder, der mit Views arbeitet. Die Query aus dem Beispiel entspricht der folgenden Query
select * from pohled where b = 20 create view pohled as select * from data where a = 10.
Deswegen spielt das Flattening im PostgreSQL so eine bedeutende Rolle. Dank ihm besitzt die Verwendung von Views keinen Vorteil gegenüber einer direkten Query in der Aufstellung.
Wie kann man den PostgreSQL nun dazu zwingen, die Klammern zu beachten? Das Flattening kann nicht durchgeführt werden, solange die gestellte Query eine der Klauseln LIMIT oder OFFSET beinhaltet. Beides bedeutet für PostgreSQL LIMIT. LIMIT ist ziemlich unpraktisch und verändert die Semantik einer Query. Dafür ist OFFSET 0 eine Art nichts tuenden Einscheibsels, weswegen es auch benutzt wird. Kurz wurde auch die Einführung von sogenannten Hints (Hinweisen) überlegt, was sich letztendlich allerdings nicht durchgesetzt hat, da ein Hint für den Flattening-Verbot ein Hintertürchen für die Einführung der Hints für Indexe wäre und dies ist beim PostgreSQL tabu. Außerdem ist OFFSET 0 ein öffentliches Geheimnis, das Ihnen nicht verborgen bleibt, wenn Sie sich in der Community bewegen. Wozu also eine neue, nicht normgerechte Syntax ersinnen und implementieren? Sollte Sie diese Problematik interessieren, so empfehle ich unter pg_performance die Schlüsselworte Flattening und "OFFSET 0". Nebenbei ist es auch ein Grund, warum die View die Klausel LIMIT nicht beinhalten sollte.
root=# explain select * from (select * from t1 where a = 20 offset 0) s where s.b = 20;
QUERY PLAN
-----------------------------------------------------------------
Subquery Scan s (cost=0.00..244.42 rows=1 width=8)
Filter: (b = 20)
-> Limit (cost=0.00..244.16 rows=21 width=8)
-> Seq Scan on t1 (cost=0.00..244.16 rows=21 width=8)
Filter: (a = 20)
(5 rows)
Ich überlege, ob es noch eine andere ähnliche Hinterlist gibt, es fällt mir allerdings nichts ein. PostgreSQL funktioniert einfach und es helfen keine Tricks. Vor allem wenn sie nach Alchimie riechen. Ich erinnere mich, dass in 7.4, falls wir Indices nutzen wollten, mussten die Zahltypen explizit umgestaltet werden. Auf der anderen Seite ist 7.4 zwar eine verlässliche Datenbank, die das ihre geleistet hat, aber eben, weil sie ihres bereits geleistet hat (Anm. 7.4 war wahrscheinlich die erste verwendbare Version). Die Versionen 8.x sind um eine Generation weiter und ermöglichen den Programmierern sich besser auf die eigene Arbeit zu konzentrieren und bauen das ab, was ich als Alchimie bezeichne.
Als ich einige Tage später meinen Freund wieder mal gesehen habe und ihn gefragt habe, wie alles ausgegangen war, ob er den Offset Null benutzt hatte, hat er mir geantwortet, dass er es versucht hatte, nur hatte er zehntausend Queries dreitausendfach beschleunigt und die restlichen neunzig Prozent um dreihundert Prozent verlangsamt. Und vorläufig hatte er es sich überlegt. Nichts desto trotz, wenigstens habe er nicht das Gefühl, dass der PostgreSQL sich nicht über ihn lustig macht. Manchmal gibt es keine einfache Lösung.