Coole SQL-Optimierungen, die nicht vom Kostenmodell abhängen. Teil 1

Fünf einfache Optimierungen, die nur auf der Grundlage von Metadaten (d. h. Einschränkungen) und der Abfrage selbst implementiert werden können. Wir bieten Ihnen eine Adaption des Artikels von Lukas Eder an, die sich an diejenigen richtet, die über ein allgemeines Verständnis von Datenbanken und SQL sowie über einige praktische Erfahrungen mit DBMS verfügen . Kostenoptimierung ist eigentlich eine Standardmethode zur Optimierung von SQL-Abfragen in modernen Datenbanken. Aus diesem Grund ist es so schwierig, manuell einen komplexen Algorithmus in 3GL (Programmiersprachen der dritten Generation) zu schreiben, dessen Leistung den dynamisch berechneten Ausführungsplan eines modernen Optimierers übertreffen würde. Heute werden wir nicht auf die Kostenoptimierung eingehen, also auf die Optimierung basierend auf dem Kostenmodell der Datenbank. Wir werden uns viel einfachere Optimierungen ansehen. Diejenigen, die nur basierend auf Metadaten (d. h. Einschränkungen) und der Anfrage selbst implementiert werden können. Normalerweise ist ihre Implementierung für eine Datenbank kein Newton-Binom, da in diesem Fall jede Optimierung zu einem besseren Ausführungsplan führt, unabhängig vom Vorhandensein von Indizes, Datenmengen und der Schiefe der Datenverteilung. „Kein Newton-Binom“ bedeutet nicht, wie einfach die Optimierung zu implementieren ist, sondern ob sie durchgeführt werden sollte. Diese Optimierungen eliminieren unnötige, zusätzliche Arbeit [für die Datenbank] ( im Gegensatz zu unnötiger, erforderlicher Arbeit, über die ich bereits geschrieben habe ).

Wozu dienen diese Optimierungen?

Die meisten von ihnen werden verwendet für:

• Fehlerbehebungen in Abfragen;
• Ermöglicht die Wiederverwendung von Ansichten, ohne dass die Datenbank die Ansichtslogik tatsächlich ausführt.

Im ersten Fall könnte man sagen: „Na und, reparieren Sie einfach diese blöde SQL-Abfrage.“ Aber derjenige, der noch nie einen Fehler gemacht hat, soll zuerst einen Stein nach mir werfen. Besonders interessant ist der zweite Fall: Er gibt uns die Möglichkeit, komplexe Bibliotheken mit Ansichten und Tabellenfunktionen zu erstellen, die über mehrere Ebenen hinweg wiederverwendet werden können.

Verwendete Datenbanken

In diesem Artikel vergleichen wir 10 SQL-Optimierungen in den fünf am häufigsten verwendeten DBMS ( gemäß Datenbankrankings ):

• Oracle 12.2;
• MySQL 8.0.2;
• SQL Server 2014;
• PostgreSQL 9.6;
• DB2 LUW 10.5.

Eine andere Bewertung spiegelt dies fast wider. Wie üblich werde ich in diesem Artikel die Sakila-Datenbank abfragen . Hier ist eine Liste dieser zehn Arten von Optimierungen:

1. Transitive Schließung;
2. unmögliche Prädikate und unnötige Tabellenaufrufe;
3. Eliminierung von JOIN;
4. Beseitigung „bedeutungsloser“ Prädikate;
5. Projektionen in EXISTS-Unterabfragen;
6. Zusammenführung von Prädikaten;
7. nachweislich leere Mengen;
8. Einschränkungen CHECK;
9. unnötige reflexive Verbindungen;
10. Pushdown-Prädikate

Heute besprechen wir S. 1-3, im zweiten Teil - 4 und 5 und im Teil 3 - 6-10.

1. Transitiver Abschluss

Beginnen wir mit etwas Einfacherem: dem transitiven Abschluss . Dies ist ein triviales Konzept, das auf viele mathematische Operationen anwendbar ist, beispielsweise auf den Gleichheitsoperator. Es lässt sich in diesem Fall wie folgt formulieren: Wenn A = B und B = C, dann ist A = C.

Nicht schwer, oder? Dies hat jedoch einige interessante Implikationen für SQL-Optimierer. Schauen wir uns ein Beispiel an. Extrahieren wir alle Filme mit ACTOR_ID = 1:

SELECT first_name, last_name, film_id
FROM actor a
JOIN film_actor fa ON a.actor_id = fa.actor_id
WHERE a.actor_id = 1;

Das Ergebnis ist wie folgt:

FIRST_NAME      LAST_NAME  FILM_ID
PENELOPE        GUINESS    1
PENELOPE        GUINESS    23
PENELOPE        GUINESS    25
PENELOPE        GUINESS    106
PENELOPE        GUINESS    140
PENELOPE        GUINESS    166
...

Schauen wir uns nun den Plan zur Ausführung dieser Abfrage im Fall des Oracle DBMS an:

--------------------------------------------------------------
| Id  | Operation                    | Name          | Rows  |
--------------------------------------------------------------
|   0 | SELECT STATEMENT             |               |       |
|   1 |  NESTED LOOPS                |               |    19 |
|   2 |   TABLE ACCESS BY INDEX ROWID| ACTOR         |     1 |
|*  3 |    INDEX UNIQUE SCAN         | PK_ACTOR      |     1 |
|*  4 |   INDEX RANGE SCAN           | PK_FILM_ACTOR |    19 |
--------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   3 - access("A"."ACTOR_ID"=1)
   4 - access("FA"."ACTOR_ID"=1)

Besonders interessant ist hier der Abschnitt über Prädikate. Das Prädikat ACTOR_ID = 1 gilt aufgrund der transitiven Schließung sowohl für die Tabelle ACTOR als auch für die Tabelle FILM_ACTOR. Wenn:

• A.ACTOR_ID = 1 (из предиката WHERE) и…
• A.ACTOR_ID = FA.ACTOR_ID (из предиката ON)
  То:
• FA.ACTOR_ID = 1

Bei komplexeren Abfragen führt dies zu sehr schönen Ergebnissen. Insbesondere erhöht sich die Genauigkeit von Kardinalitätsschätzungen erheblich, da es möglich wird, Schätzungen basierend auf einem bestimmten konstanten Wert des Prädikats auszuwählen und nicht beispielsweise auf der durchschnittlichen Anzahl von Filmen nach Schauspielern, wie in der folgenden Abfrage (die zurückgibt). gleiches Ergebnis):

SELECT first_name, last_name, film_id
FROM actor a
JOIN film_actor fa ON a.actor_id = fa.actor_id
WHERE first_name = 'PENELOPE'
AND last_name = 'GUINESS'

Sein Plan:

----------------------------------------------------------------------------
| Id  | Operation                            | Name                | Rows  |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT                     |                     |       |
|   1 |  NESTED LOOPS                        |                     |     2 |
|*  2 |   TABLE ACCESS BY INDEX ROWID BATCHED| ACTOR               |     1 |
|*  3 |    INDEX RANGE SCAN                  | IDX_ACTOR_LAST_NAME |     3 |
|*  4 |   INDEX RANGE SCAN                   | PK_FILM_ACTOR       |    27 |
----------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   2 - filter("A"."FIRST_NAME"='PENELOPE')
   3 - access("A"."LAST_NAME"='GUINESS')
   4 - access("A"."ACTOR_ID"="FA"."ACTOR_ID")

Wie Sie sehen, wird die Anzahl der Zeilen in der Tabelle FILM_ACTOR überschätzt, während die Anzahl der NESTED LOOP unterschätzt wird. Hier sind ein paar interessante Werte:

SELECT count(*) FROM film_actor WHERE actor_id = 1;
SELECT avg(c) FROM (
  SELECT count(*) c FROM film_actor GROUP BY actor_id
);

Ergebnis:

19
27.315

Von hier stammen die Schätzungen. Wenn die Datenbank weiß, dass es sich um ACTOR_ID = 1 handelt, kann sie Statistiken über die Anzahl der Filme für diesen bestimmten Schauspieler sammeln . Wenn dies nicht der Fall ist (da der Standardmechanismus zur Erfassung von Statistiken FIRST_NAME/NACHNAME nicht mit ACTOR_ID korreliert), erhalten wir die durchschnittliche Anzahl von Filmen für alle Schauspieler . In diesem speziellen Fall ein einfacher, unwichtiger Fehler, aber in einer komplexen Abfrage kann er sich weiter ausbreiten, sich ansammeln und weiter in der Abfrage (weiter oben im Plan) zu einer falschen JOIN-Auswahl führen. Gestalten Sie Ihre Joins und einfachen Prädikate also, wann immer Sie können, so, dass sie die transitive Schließung nutzen. Welche anderen Datenbanken unterstützen diese Funktion?

DB2

Ja!

Explain Plan
-----------------------------------------------------------
ID | Operation              |                 Rows | Cost
 1 | RETURN                 |                      |   13
 2 |  NLJOIN                |              27 of 1 |   13
 3 |   FETCH ACTOR          |     1 of 1 (100.00%) |    6
 4 |    IXSCAN PK_ACTOR     |   1 of 200 (   .50%) |    0
 5 |   IXSCAN PK_FILM_ACTOR | 27 of 5462 (   .49%) |    6
Predicate Information
 4 - START (Q2.ACTOR_ID = 1)
      STOP (Q2.ACTOR_ID = 1)
 5 - START (1 = Q1.ACTOR_ID)
      STOP (1 = Q1.ACTOR_ID)

Übrigens, wenn Sie solche coolen Ausführungspläne mögen, schauen Sie sich das Drehbuch von Markus Winand an .

MySQL

Leider sind MySQL-Ausführungspläne für diese Art der Analyse nicht gut geeignet. Das Prädikat selbst fehlt in den Ausgabeinformationen:

ID  SELECT TYPE  TABLE  TYPE   REF    ROWS
------------------------------------------
1   SIMPLE       a      const  const  1
1   SIMPLE       fa     ref    const  19

Aber die Tatsache, dass const zweimal in der REF-Spalte angegeben wird, zeigt, dass beide Tabellen nach einem konstanten Wert suchen. Gleichzeitig sieht der Abfrageplan mit FIRST_NAME/LAST_NAME so aus:

ID  SELECT TYPE  TABLE  TYPE   REF         ROWS
-----------------------------------------------
1   SIMPLE       a      ref    const       3
1   SIMPLE       fa     ref    a.actor_id  27

Und wie Sie sehen können, verweist die REF jetzt auf die Spalte aus dem JOIN-Prädikat. Der Kardinalitätswert ist fast derselbe wie in Oracle. Also ja, MySQL unterstützt auch transitive Schließungen.

PostgreSQL

Ja!

QUERY PLAN
------------------------------------------------------------------------------------
Nested Loop  (cost=4.49..40.24 rows=27 width=15)
  ->  Seq Scan on actor a  (cost=0.00..4.50 rows=1 width=17)
        Filter: (actor_id = 1)
  ->  Bitmap Heap Scan on film_actor fa  (cost=4.49..35.47 rows=27 width=4)
        Recheck Cond: (actor_id = 1)
        ->  Bitmap Index Scan on film_actor_pkey  (cost=0.00..4.48 rows=27 width=0)
              Index Cond: (actor_id = 1)

SQL Server

Ja!

|--Nested Loops(Inner Join)
     |--Nested Loops(Inner Join)
     |    |--Index Seek (SEEK:([a].[actor_id]=(1)))
     |    |--RID Lookup
     |--Index Seek (SEEK:([fa].[actor_id]=(1)))

Zusammenfassung

Alle unsere Datenbanken unterstützen die transitive Schließung. Warten Sie jedoch auf #6 im nächsten Teil des Artikels. Es gibt komplexe Fälle transitiver Schließung, die nicht alle Datenbanken verarbeiten können.

2. Unmögliche Prädikate und unnötige Tabellenaufrufe

Das ist eine völlig dumme Optimierung, aber warum nicht? Wenn Benutzer unmögliche Prädikate schreiben, warum sollten sie sich dann die Mühe machen, sie auszuführen? Hier sind einige Beispiele:

-- "Очевидный"
SELECT * FROM actor WHERE 1 = 0
-- "Хитрый"
SELECT * FROM actor WHERE NULL = NULL

Die erste Abfrage wird offensichtlich niemals Ergebnisse liefern, aber die gleiche Aussage gilt auch für die zweite. Denn obwohl NULL IS NULL immer TRUE ist, ist das Ergebnis der Berechnung NULL = NULL NULL, was nach der dreiwertigen Logik gleichbedeutend mit FALSE ist. Das ist ziemlich selbsterklärend. Lassen Sie uns also gleich herausfinden, welche Datenbanken diese Optimierung durchführen.

DB2

Ja!

Explain Plan
-----------------------------------
ID | Operation      |   Rows | Cost
 1 | RETURN         |        |    0
 2 |  TBSCAN GENROW | 0 of 0 |    0

Wie Sie sehen, ist der Zugriff auf die ACTOR-Tabelle vollständig vom Plan ausgeschlossen. Es enthält nur die GENROW-Operation, die Nullzeilen generiert. Perfekt.

MySQL

Ja!

ID  SELECT TYPE  TABLE   EXTRAS
-----------------------------------------
1   SIMPLE         Impossible WHERE

Dieses Mal war MySQL so freundlich, uns über die unmögliche WHERE-Klausel zu informieren. Danke! Dies erleichtert insbesondere im Vergleich zu anderen Datenbanken die Analyse erheblich.

Orakel

Ja!

---------------------------------------------------------------
| Id  | Operation          | Name  | Starts | E-Rows | A-Rows |
---------------------------------------------------------------
|   0 | SELECT STATEMENT   |       |      1 |        |      0 |
|*  1 |  FILTER            |       |      1 |        |      0 |
|   2 |   TABLE ACCESS FULL| ACTOR |      0 |    200 |      0 |
---------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter(NULL IS NOT NULL)

Wir sehen, dass der Plan immer noch den Zugriff auf die ACTOR-Tabelle erwähnt und die erwartete Anzahl von Zeilen immer noch 200 beträgt, aber es gibt auch eine Filteroperation (FILTER) mit Id=1, bei der es nie TRUE geben wird. Da Oracle den Standard-SQL-Datentyp Boolean nicht mag , zeigt Oracle im Plan NULL IS NOT NULL statt nur FALSE an. Na ja... Aber im Ernst, achten Sie auf dieses Prädikat. Ich hatte Gelegenheit, Ausführungspläne mit Teilbäumen mit 1000 Zeilen und extrem hohen Kostenwerten zu debuggen, nur um im Nachhinein festzustellen, dass der gesamte Teilbaum durch den NULL IS NOT NULL-Filter „abgeschnitten“ wurde. Ein wenig entmutigend, sage ich Ihnen.

PostgreSQL

Ja!

QUERY PLAN
-------------------------------------------
Result  (cost=0.00..0.00 rows=0 width=228)
  One-Time Filter: false

Schon besser. Keine lästigen ACTOR-Tabellenaufrufe und ein nettes kleines FALSE-Prädikat.

SQL Server?

Ja!

|--Constant Scan

SQL Server nennt dies einen „ konstanten Scan“, also einen Scan, bei dem nichts passiert – ähnlich wie bei DB2. Alle unsere Datenbanken können unmögliche Prädikate ausschließen:

3. Eliminieren Sie JOINs

Im vorherigen Abschnitt haben wir unnötige Tabellenzugriffe bei Einzeltabellenabfragen beobachtet. Aber was passiert, wenn der JOIN keinen von mehreren Tabellenzugriffen erfordert? Ich habe bereits in einem früheren Beitrag in meinem Blog über die Eliminierung von JOIN geschrieben . Die SQL-Engine ist in der Lage, anhand des Abfragetyps und des Vorhandenseins von Primär- und Fremdschlüsseln zu bestimmen, ob ein bestimmter JOIN in einer bestimmten Abfrage tatsächlich benötigt wird oder ob seine Eliminierung keinen Einfluss auf die Semantik der Abfrage hat. In allen nächsten drei Beispielen ist JOIN nicht erforderlich. Eine innere ...-zu-Eins-Verknüpfung kann durch einen NOT NULL-Fremdschlüssel eliminiert werden. Stattdessen:

SELECT first_name, last_name
FROM customer c
JOIN address a ON c.address_id = a.address_id

Die Datenbank kann Folgendes tun:

SELECT first_name, last_name
FROM customer c

Ein INNER JOIN vom Typ „...-to-one“ kann ersetzt werden, wenn ein Nullable-Fremdschlüssel vorhanden ist. Die obige Abfrage funktioniert, wenn der Fremdschlüssel einer NOT NULL-Einschränkung unterliegt. Wenn nicht, zum Beispiel wie in dieser Anfrage:

SELECT title
FROM film f
JOIN language l ON f.original_language_id = l.language_id

dann kann JOIN immer noch entfernt werden, aber Sie müssen das NOT NULL-Prädikat hinzufügen, etwa so:

SELECT title
FROM film
WHERE original_language_id IS NOT NULL

Ein OUTER JOIN vom Typ „...-to-one“ kann entfernt werden, wenn ein eindeutiger Schlüssel vorhanden ist. An Stelle von:

SELECT first_name, last_name
FROM customer c
LEFT JOIN address a ON c.address_id = a.address_id

Die Datenbank kann wiederum Folgendes tun:

SELECT first_name, last_name
FROM customer c

... auch wenn kein Fremdschlüssel für CUSTOMER.ADDRESS_ID vorhanden ist. Die eindeutige äußere Verbindung (DISTINCT OUTER JOIN) vom Typ „...-to-many“ kann entfernt werden. An Stelle von:

SELECT DISTINCT first_name, last_name
FROM actor a
LEFT JOIN film_actor fa ON a.actor_id = fa.actor_id

Die Datenbank kann Folgendes tun:

SELECT DISTINCT first_name, last_name
FROM actor a

Alle diese Beispiele wurden im vorherigen Artikel ausführlich untersucht, daher werde ich mich nicht wiederholen, sondern nur alles zusammenfassen, was verschiedene Datenbanken eliminieren können: Leider können nicht alle Datenbanken alle Arten von Verbindungen auflösen. DB2 und SQL Server sind hier die unangefochtenen Spitzenreiter! Fortsetzung folgt