Warum unterscheiden sich die Pläne, wenn die Abfragen logisch ähnlich sind?

19

Ich habe zwei Funktionen geschrieben, um die erste Hausaufgabenfrage von Tag 3 aus Seven Databases in Seven Weeks zu beantworten .

Erstellen Sie eine gespeicherte Prozedur, in der Sie einen Filmtitel oder den Namen eines beliebigen Schauspielers eingeben können. Daraufhin werden die fünf wichtigsten Vorschläge zurückgegeben, die entweder auf Filmen basieren, in denen der Schauspieler die Hauptrolle spielt, oder auf Filmen mit ähnlichen Genres.

Mein erster Versuch ist richtig aber langsam. Es kann bis zu 2000 ms dauern, bis ein Ergebnis zurückgegeben wird.

CREATE OR REPLACE FUNCTION suggest_movies(IN query text, IN result_limit integer DEFAULT 5)
  RETURNS TABLE(movie_id integer, title text) AS
$BODY$
WITH suggestions AS (

  SELECT
    actors.name AS entity_term,
    movies.movie_id AS suggestion_id,
    movies.title AS suggestion_title,
    1 AS rank
  FROM actors
  INNER JOIN movies_actors ON (actors.actor_id = movies_actors.actor_id)
  INNER JOIN movies ON (movies.movie_id = movies_actors.movie_id)

  UNION ALL

  SELECT
    searches.title AS entity_term,
    suggestions.movie_id AS suggestion_id,
    suggestions.title AS suggestion_title,
    RANK() OVER (PARTITION BY searches.movie_id ORDER BY cube_distance(searches.genre, suggestions.genre)) AS rank
  FROM movies AS searches
  INNER JOIN movies AS suggestions ON
    (searches.movie_id <> suggestions.movie_id) AND
    (cube_enlarge(searches.genre, 2, 18) @> suggestions.genre)
)
SELECT suggestion_id, suggestion_title
FROM suggestions
WHERE entity_term = query
ORDER BY rank, suggestion_id
LIMIT result_limit;
$BODY$
LANGUAGE sql;

Mein zweiter Versuch ist richtig und schnell. Ich habe es optimiert, indem ich den Filter vom CTE in jeden Teil der Verbindung gedrückt habe.

Ich habe diese Zeile aus der äußeren Abfrage entfernt:

WHERE entity_term = query

Ich habe diese Zeile zur ersten inneren Abfrage hinzugefügt:

WHERE actors.name = query

Ich habe diese Zeile zur zweiten inneren Abfrage hinzugefügt:

WHERE movies.title = query

Die zweite Funktion benötigt ungefähr 10 ms, um dasselbe Ergebnis zurückzugeben.

Außer den Funktionsdefinitionen unterscheidet sich in der Datenbank nichts.

Warum erstellt PostgreSQL für diese beiden logisch äquivalenten Abfragen so unterschiedliche Pläne?

Der EXPLAIN ANALYZEPlan der ersten Funktion sieht folgendermaßen aus:

                                                                                       Limit  (cost=7774.18..7774.19 rows=5 width=44) (actual time=1738.566..1738.567 rows=5 loops=1)
   CTE suggestions
     ->  Append  (cost=332.56..7337.19 rows=19350 width=285) (actual time=7.113..1577.823 rows=383024 loops=1)
           ->  Subquery Scan on "*SELECT* 1"  (cost=332.56..996.80 rows=11168 width=33) (actual time=7.113..22.258 rows=11168 loops=1)
                 ->  Hash Join  (cost=332.56..885.12 rows=11168 width=33) (actual time=7.110..19.850 rows=11168 loops=1)
                       Hash Cond: (movies_actors.movie_id = movies.movie_id)
                       ->  Hash Join  (cost=143.19..514.27 rows=11168 width=18) (actual time=4.326..11.938 rows=11168 loops=1)
                             Hash Cond: (movies_actors.actor_id = actors.actor_id)
                             ->  Seq Scan on movies_actors  (cost=0.00..161.68 rows=11168 width=8) (actual time=0.013..1.648 rows=11168 loops=1)
                             ->  Hash  (cost=80.86..80.86 rows=4986 width=18) (actual time=4.296..4.296 rows=4986 loops=1)
                                   Buckets: 1024  Batches: 1  Memory Usage: 252kB
                                   ->  Seq Scan on actors  (cost=0.00..80.86 rows=4986 width=18) (actual time=0.009..1.681 rows=4986 loops=1)
                       ->  Hash  (cost=153.61..153.61 rows=2861 width=19) (actual time=2.768..2.768 rows=2861 loops=1)
                             Buckets: 1024  Batches: 1  Memory Usage: 146kB
                             ->  Seq Scan on movies  (cost=0.00..153.61 rows=2861 width=19) (actual time=0.003..1.197 rows=2861 loops=1)
           ->  Subquery Scan on "*SELECT* 2"  (cost=6074.48..6340.40 rows=8182 width=630) (actual time=1231.324..1528.188 rows=371856 loops=1)
                 ->  WindowAgg  (cost=6074.48..6258.58 rows=8182 width=630) (actual time=1231.324..1492.106 rows=371856 loops=1)
                       ->  Sort  (cost=6074.48..6094.94 rows=8182 width=630) (actual time=1231.307..1282.550 rows=371856 loops=1)
                             Sort Key: searches.movie_id, (cube_distance(searches.genre, suggestions_1.genre))
                             Sort Method: external sort  Disk: 21584kB
                             ->  Nested Loop  (cost=0.27..3246.72 rows=8182 width=630) (actual time=0.047..909.096 rows=371856 loops=1)
                                   ->  Seq Scan on movies searches  (cost=0.00..153.61 rows=2861 width=315) (actual time=0.003..0.676 rows=2861 loops=1)
                                   ->  Index Scan using movies_genres_cube on movies suggestions_1  (cost=0.27..1.05 rows=3 width=315) (actual time=0.016..0.277 rows=130 loops=2861)
                                         Index Cond: (cube_enlarge(searches.genre, 2::double precision, 18) @> genre)
                                         Filter: (searches.movie_id <> movie_id)
                                         Rows Removed by Filter: 1
   ->  Sort  (cost=436.99..437.23 rows=97 width=44) (actual time=1738.565..1738.566 rows=5 loops=1)
         Sort Key: suggestions.rank, suggestions.suggestion_id
         Sort Method: top-N heapsort  Memory: 25kB
         ->  CTE Scan on suggestions  (cost=0.00..435.38 rows=97 width=44) (actual time=1281.905..1738.531 rows=43 loops=1)
               Filter: (entity_term = 'Die Hard'::text)
               Rows Removed by Filter: 382981
 Total runtime: 1746.623 ms

Der EXPLAIN ANALYZEPlan der zweiten Abfrage sieht folgendermaßen aus:

 Limit  (cost=43.74..43.76 rows=5 width=44) (actual time=1.231..1.234 rows=5 loops=1)
   CTE suggestions
     ->  Append  (cost=4.86..43.58 rows=5 width=391) (actual time=1.029..1.141 rows=43 loops=1)
           ->  Subquery Scan on "*SELECT* 1"  (cost=4.86..20.18 rows=2 width=33) (actual time=0.047..0.047 rows=0 loops=1)
                 ->  Nested Loop  (cost=4.86..20.16 rows=2 width=33) (actual time=0.047..0.047 rows=0 loops=1)
                       ->  Nested Loop  (cost=4.58..19.45 rows=2 width=18) (actual time=0.045..0.045 rows=0 loops=1)
                             ->  Index Scan using actors_name on actors  (cost=0.28..8.30 rows=1 width=18) (actual time=0.045..0.045 rows=0 loops=1)
                                   Index Cond: (name = 'Die Hard'::text)
                             ->  Bitmap Heap Scan on movies_actors  (cost=4.30..11.13 rows=2 width=8) (never executed)
                                   Recheck Cond: (actor_id = actors.actor_id)
                                   ->  Bitmap Index Scan on movies_actors_actor_id  (cost=0.00..4.30 rows=2 width=0) (never executed)
                                         Index Cond: (actor_id = actors.actor_id)
                       ->  Index Scan using movies_pkey on movies  (cost=0.28..0.35 rows=1 width=19) (never executed)
                             Index Cond: (movie_id = movies_actors.movie_id)
           ->  Subquery Scan on "*SELECT* 2"  (cost=23.31..23.40 rows=3 width=630) (actual time=0.982..1.081 rows=43 loops=1)
                 ->  WindowAgg  (cost=23.31..23.37 rows=3 width=630) (actual time=0.982..1.064 rows=43 loops=1)
                       ->  Sort  (cost=23.31..23.31 rows=3 width=630) (actual time=0.963..0.971 rows=43 loops=1)
                             Sort Key: searches.movie_id, (cube_distance(searches.genre, suggestions_1.genre))
                             Sort Method: quicksort  Memory: 28kB
                             ->  Nested Loop  (cost=4.58..23.28 rows=3 width=630) (actual time=0.808..0.916 rows=43 loops=1)
                                   ->  Index Scan using movies_title on movies searches  (cost=0.28..8.30 rows=1 width=315) (actual time=0.025..0.027 rows=1 loops=1)
                                         Index Cond: (title = 'Die Hard'::text)
                                   ->  Bitmap Heap Scan on movies suggestions_1  (cost=4.30..14.95 rows=3 width=315) (actual time=0.775..0.844 rows=43 loops=1)
                                         Recheck Cond: (cube_enlarge(searches.genre, 2::double precision, 18) @> genre)
                                         Filter: (searches.movie_id <> movie_id)
                                         Rows Removed by Filter: 1
                                         ->  Bitmap Index Scan on movies_genres_cube  (cost=0.00..4.29 rows=3 width=0) (actual time=0.750..0.750 rows=44 loops=1)
                                               Index Cond: (cube_enlarge(searches.genre, 2::double precision, 18) @> genre)
   ->  Sort  (cost=0.16..0.17 rows=5 width=44) (actual time=1.230..1.231 rows=5 loops=1)
         Sort Key: suggestions.rank, suggestions.suggestion_id
         Sort Method: top-N heapsort  Memory: 25kB
         ->  CTE Scan on suggestions  (cost=0.00..0.10 rows=5 width=44) (actual time=1.034..1.187 rows=43 loops=1)
 Total runtime: 1.410 ms
Iain Samuel McLean Elder
quelle

Antworten:

21

Kein automatischer Prädikaten-Pushdown für CTEs

PostgreSQL 9.3 führt keinen Prädikat-Pushdown für CTEs durch.

Ein Optimierer, der Pushdown prädiziert, kann Where-Klauseln in innere Abfragen verschieben. Ziel ist es, irrelevante Daten so früh wie möglich herauszufiltern. Solange die neue Abfrage logisch äquivalent ist, ruft die Engine immer noch alle relevanten Daten ab, sodass nur schneller das richtige Ergebnis erzielt wird.

Kernentwickler Tom Lane spielt auf die Schwierigkeit an, die logische Äquivalenz auf der Mailingliste pgsql-performance zu bestimmen .

CTEs werden auch als Optimierungszäune behandelt. Dies ist weniger eine Einschränkung des Optimierers als vielmehr eine sinnvolle Semantik, wenn der CTE eine schreibbare Abfrage enthält.

Das Optimierungsprogramm unterscheidet nicht zwischen schreibgeschützten und schreibgeschützten CTEs und ist daher zu konservativ, wenn Pläne berücksichtigt werden. Die "Fencing" -Behandlung verhindert, dass der Optimierer die where-Klausel innerhalb des CTE verschiebt, obwohl wir sehen können, dass dies sicher ist.

Wir können warten, bis das PostgreSQL-Team die CTE-Optimierung verbessert hat. Um jedoch eine gute Leistung zu erzielen, müssen Sie Ihren Schreibstil ändern.

Umschreiben für die Leistung

Die Frage zeigt bereits einen Weg, um einen besseren Plan zu bekommen. Durch das Duplizieren der Filterbedingung wird der Effekt des Prädikat-Pushdowns im Wesentlichen hartcodiert.

In beiden Plänen kopiert die Engine die Ergebniszeilen in eine Arbeitstabelle, damit sie sortiert werden können. Je größer der Worktable, desto langsamer die Abfrage.

Der erste Plan kopiert alle Zeilen in den Basistabellen in die Arbeitstabelle und durchsucht diese, um das Ergebnis zu finden. Um noch langsamer zu werden, muss die Engine den gesamten Worktable scannen, da er keine Indizes enthält.

Das ist eine lächerliche Menge an unnötiger Arbeit. Es liest alle Daten in den Basistabellen zweimal, um die Antwort zu finden, wenn nur geschätzte 5 übereinstimmende Zeilen aus geschätzten 19350 Zeilen in den Basistabellen vorhanden sind.

Der zweite Plan verwendet die Indizes, um die übereinstimmenden Zeilen zu finden und kopiert nur diese in den Worktable. Der Index hat die Daten für uns effektiv gefiltert.

Auf Seite 85 von The Art of SQL erinnert Stéphane Faroult an die Erwartungen der Benutzer.

Endbenutzer passen ihre Geduld in hohem Maße an die Anzahl der zu erwartenden Reihen an: Wenn sie nach einer Nadel fragen, achten sie kaum auf die Größe des Heuhaufens.

Der zweite Plan skaliert mit der Nadel, sodass Ihre Benutzer mit größerer Wahrscheinlichkeit zufrieden sind.

Für Wartbarkeit umschreiben

Die neue Abfrage ist schwieriger zu verwalten, da Sie einen Fehler einführen können, indem Sie eine Filterepisode ändern, die andere jedoch nicht.

Wäre es nicht großartig, wenn wir alles nur einmal schreiben und trotzdem eine gute Leistung erzielen könnten?

Wir können. Das Optimierungsprogramm gibt Pushdown für Unterabfragen vor.

Ein einfacheres Beispiel ist leichter zu erklären.

CREATE TABLE a (c INT);

CREATE TABLE b (c INT);

CREATE INDEX a_c ON a(c);

CREATE INDEX b_c ON b(c);

INSERT INTO a SELECT 1 FROM generate_series(1, 1000000);

INSERT INTO b SELECT 2 FROM a;

INSERT INTO a SELECT 3;

Dadurch werden zwei Tabellen mit jeweils einer indizierten Spalte erstellt. Zusammen enthalten sie eine Million 1s, eine Million 2s und eins 3.

Sie können die Nadel 3mit einer dieser Abfragen finden.

-- CTE
EXPLAIN ANALYZE
WITH cte AS (
  SELECT c FROM a
  UNION ALL
  SELECT c FROM b
)
SELECT c FROM cte WHERE c = 3;

-- Subquery
EXPLAIN ANALYZE
SELECT c
FROM (
  SELECT c FROM a
  UNION ALL
  SELECT c FROM b
) AS subquery
WHERE c = 3;

Der Plan für den CTE ist langsam. Die Engine scannt drei Tabellen und liest ungefähr vier Millionen Zeilen. Es dauert fast 1000 Millisekunden.

CTE Scan on cte  (cost=33275.00..78275.00 rows=10000 width=4) (actual time=471.412..943.225 rows=1 loops=1)
  Filter: (c = 3)
  Rows Removed by Filter: 2000000
  CTE cte
    ->  Append  (cost=0.00..33275.00 rows=2000000 width=4) (actual time=0.011..409.573 rows=2000001 loops=1)
          ->  Seq Scan on a  (cost=0.00..14425.00 rows=1000000 width=4) (actual time=0.010..114.869 rows=1000001 loops=1)
          ->  Seq Scan on b  (cost=0.00..18850.00 rows=1000000 width=4) (actual time=5.530..104.674 rows=1000000 loops=1)
Total runtime: 948.594 ms

Der Plan für die Unterabfrage ist schnell. Die Engine sucht nur nach jedem Index. Es dauert weniger als eine Millisekunde.

Append  (cost=0.42..8.88 rows=2 width=4) (actual time=0.021..0.038 rows=1 loops=1)
  ->  Index Only Scan using a_c on a  (cost=0.42..4.44 rows=1 width=4) (actual time=0.020..0.021 rows=1 loops=1)
        Index Cond: (c = 3)
        Heap Fetches: 1
  ->  Index Only Scan using b_c on b  (cost=0.42..4.44 rows=1 width=4) (actual time=0.016..0.016 rows=0 loops=1)
        Index Cond: (c = 3)
        Heap Fetches: 0
Total runtime: 0.065 ms

Siehe SQLFiddle für eine interaktive Version.

Iain Samuel McLean Elder
quelle
0

Die Pläne in Postgres 12 sind die gleichen

Die Frage stellte sich zu Postgres 9.3. Fünf Jahre später ist diese Version veraltet, aber was hat sich geändert?

PostgreSQL 12 integriert jetzt CTEs wie diese.

Inline WITH-Abfragen (allgemeine Tabellenausdrücke)

Gängige Tabellenausdrücke (auch als WITHAbfragen bezeichnet) können jetzt automatisch in eine Abfrage eingefügt werden, wenn sie a) nicht rekursiv sind, b) keine Nebenwirkungen haben und c) in einem späteren Teil einer Abfrage nur einmal referenziert werden. Dies beseitigt einen "Optimierungszaun", der seit Einführung der WITHKlausel in PostgreSQL 8.4 existiert

Bei Bedarf können Sie eine WITH-Abfrage mithilfe der MATERIALIZED-Klausel zum Materialisieren zwingen, z

WITH c AS MATERIALIZED ( SELECT * FROM a WHERE a.x % 4 = 0 ) SELECT * FROM c JOIN d ON d.y = a.x;
Iain Samuel McLean Elder
quelle