Warum optimiert SQL Server die UNIONs nicht?

7

Betrachten Sie diese Abfragen ( SQL Fiddle ):

Abfrage 1:

SELECT * INTO #TMP1 FROM Foo
UNION
SELECT * FROM Boo
UNION
SELECT * FROM Koo;

Abfrage 2:

SELECT * INTO #TMP2 FROM Foo
UNION
SELECT * FROM Boo
UNION ALL
SELECT * FROM Koo;

Beachten Sie, dass sich Koo nicht mit Boo / Foo überschneidet, sodass das Endergebnis dasselbe ist. Die Frage ist, warum die erste UNION / UNION- Kombination nicht zu einer einzigen SORT-Operation zusammengeführt wird.

孔夫子
quelle
2
MERGEjoin ist optimierter als SORT. Es hat eine lineare Komplexität und erfordert keine Speicherzuweisung.
Martin Smith

Antworten:

18

Das Abfrageoptimierungsprogramm verfügt über n-ary-Operatoren, obwohl die Ausführungsengine eher weniger hat. Zur Veranschaulichung werde ich eine vereinfachte Version Ihrer Tabellen verwenden - (SQL Fiddle) .

SELECT DISTINCT
    number
INTO foo
FROM master..spt_values
WHERE 
    number < 1000;

SELECT DISTINCT
    number
INTO boo
FROM master..spt_values
WHERE 
    number between 300 and 1005;

SELECT DISTINCT
    number
INTO koo
FROM master..spt_values
WHERE 
    number > 1006;

ALTER TABLE dbo.foo ADD PRIMARY KEY (number);
ALTER TABLE dbo.boo ADD PRIMARY KEY (number);
ALTER TABLE dbo.koo ADD PRIMARY KEY (number);

Schauen wir uns angesichts dieser Tabellen und Daten den Eingabebaum für eine Drei-Wege- UNIONAbfrage an:

SELECT f.number FROM dbo.foo AS f
UNION
SELECT b.number FROM dbo.boo AS b
UNION
SELECT k.number FROM dbo.koo AS k
OPTION (QUERYTRACEON 3604, QUERYTRACEON 8605);

LogOp_Union
    OUTPUT(COL: Union1006 )
    CHILD(QCOL: [f].number)
    CHILD(QCOL: [b].number)
    CHILD(QCOL: [k].number)
    LogOp_Project
        LogOp_Get TBL: dbo.foo(alias TBL: f)
        AncOp_PrjList 
    LogOp_Project
        LogOp_Get TBL: dbo.boo(alias TBL: b)
        AncOp_PrjList 
    LogOp_Project
        LogOp_Get TBL: dbo.koo(alias TBL: k)
        AncOp_PrjList 

Der logische Vereinigungsoperator hat einen Ausgang und drei untergeordnete Eingänge. Nach der kostenbasierten Optimierung ist der ausgewählte physische Baum eine Zusammenführungsverbindung mit drei Eingaben:

SELECT f.number FROM dbo.foo AS f
UNION
SELECT b.number FROM dbo.boo AS b
UNION
SELECT k.number FROM dbo.koo AS k
OPTION (QUERYTRACEON 3604, QUERYTRACEON 8607);

PhyOp_MergeUnion
    PhyOp_Range TBL: dbo.foo(alias TBL: f)(1) ASC
    PhyOp_Range TBL: dbo.boo(alias TBL: b)(1) ASC
    PhyOp_Range TBL: dbo.koo(alias TBL: k)(1) ASC

Die Ausgabe des Optimierers wird in eine Form überarbeitet, die die Ausführungs-Engine (ohne n-ary Merge Union) verarbeiten kann:

Gewerkschaftsplan zusammenführen

Durch das Umschreiben nach der Optimierung wird das N-Ary PhyOp_MergeUnionin mehrere Merge Union-Operatoren aufgeteilt. Beachten Sie, dass alle geschätzten Kosten mit dem "ursprünglichen" Gewerkschaftsbetreiber verbunden bleiben - die anderen haben eine Kostenschätzung von Null.

Die Gründe des Optimierers für Gewerkschaften, die n-ary-Operatoren verwenden, liefern eine Erklärung dafür, warum es nicht in Betracht gezogen wird, Ihr erstes Beispiel in denselben Plan wie das zweite Beispiel umzuschreiben (die Drei-Wege-Vereinigung ist ein einzelner Baumknoten).

Der zweite Grund ist, dass es keine Einschränkungen gibt, um die „fehlende Überlappung“ durchzusetzen. Bevor Einschränkungen bestehen, kann eine Vereinigung zwischen boound es kookann nicht garantiert werden, dass keine Duplikate erzeugt werden. Daher erhalten wir einen Plan zum Entfernen von Duplikaten (in diesem Fall eine Zusammenführungsunion):

SELECT b.number FROM dbo.boo AS b
UNION
SELECT k.number FROM dbo.koo AS k;

Boo / Koo ohne Einschränkungen

Durch Hinzufügen der folgenden Einschränkungen wird sichergestellt, dass die Nichtüberlappungsbedingung nicht verletzt werden kann, ohne die zwischengespeicherten Pläne für die Abfrage ungültig zu machen:

ALTER TABLE dbo.foo WITH CHECK ADD CHECK (number < 1000);
ALTER TABLE dbo.boo WITH CHECK ADD CHECK (number BETWEEN 300 AND 1005);
ALTER TABLE dbo.koo WITH CHECK ADD CHECK (number > 1006);

Jetzt kann der Optimierer sicher einfach verketten:

Boo / Koo mit Einschränkungen

Selbst mit diesen Einschränkungen wird die Drei-Wege-Vereinigungsabfrage immer noch als drei Vereinigungen angezeigt, da der Optimierer normalerweise nicht in Betracht zieht, n-ary-Operatoren aufzuteilen, um Alternativen zu untersuchen. Der n-ary-Operator ist sehr nützlich, um den Suchraum unter Kontrolle zu halten. Ein Auseinanderbrechen wäre oft kontraproduktiv, da der Optimierer das Ziel hat, schnell einen guten Plan zu finden.

SELECT f.number FROM dbo.foo AS f
UNION
SELECT b.number FROM dbo.boo AS b
UNION
SELECT k.number FROM dbo.koo AS k;

Gewerkschaftsplan mit Einschränkungen zusammenführen

Wenn als UNIONund geschrieben UNION ALL, kann ein n-ary-Operator nicht mehr verwendet werden (die Typen stimmen nicht überein), sodass der Baum separate Knoten hat:

SELECT f.number FROM dbo.foo AS f
UNION
SELECT b.number FROM dbo.boo AS b
UNION ALL
SELECT k.number FROM dbo.koo AS k
OPTION (QUERYTRACEON 3604, QUERYTRACEON 8605);

LogOp_UnionAll
    OUTPUT(COL: Union1007 )
    CHILD(COL: Union1004 )
    CHILD(QCOL: [k].number)

    LogOp_Union
        OUTPUT(COL: Union1004 )
        CHILD(QCOL: [f].number)
        CHILD(QCOL: [b].number)

        LogOp_Project
            LogOp_Get TBL: dbo.foo(alias TBL: f)
            AncOp_PrjList 

        LogOp_Project
            LogOp_Get TBL: dbo.boo(alias TBL: b)
            AncOp_PrjList 

    LogOp_Project
        LogOp_Get TBL: dbo.koo(alias TBL: k)
        AncOp_PrjList 
Paul White 9
quelle
3

SQL Server verfügt über 3-Wege-Set-Operationen. Der Operator CONCATENATION akzeptiert n Eingaben. Gegeben zum Beispiel zehn Tabellen:

CREATE TABLE Test01 (SomeKey INTEGER NOT NULL, SomeAttribute VARCHAR(80)); 
CREATE TABLE Test02 (SomeKey INTEGER NOT NULL, SomeAttribute VARCHAR(80));
CREATE TABLE Test03 (SomeKey INTEGER NOT NULL, SomeAttribute VARCHAR(80));
CREATE TABLE Test04 (SomeKey INTEGER NOT NULL, SomeAttribute VARCHAR(80));
CREATE TABLE Test05 (SomeKey INTEGER NOT NULL, SomeAttribute VARCHAR(80));
CREATE TABLE Test06 (SomeKey INTEGER NOT NULL, SomeAttribute VARCHAR(80));
CREATE TABLE Test07 (SomeKey INTEGER NOT NULL, SomeAttribute VARCHAR(80));
CREATE TABLE Test08 (SomeKey INTEGER NOT NULL, SomeAttribute VARCHAR(80));
CREATE TABLE Test09 (SomeKey INTEGER NOT NULL, SomeAttribute VARCHAR(80));
CREATE TABLE Test10 (SomeKey INTEGER NOT NULL, SomeAttribute VARCHAR(80));

und eine Abfrage, die alles vereint, um eine Zeile in jeder Tabelle mit demselben Schlüssel zu finden:

SELECT * FROM
(
SELECT * FROM Test01 UNION ALL
SELECT * FROM Test02 UNION ALL
SELECT * FROM Test03 UNION ALL
SELECT * FROM Test04 UNION ALL
SELECT * FROM Test05 UNION ALL
SELECT * FROM Test06 UNION ALL
SELECT * FROM Test07 UNION ALL
SELECT * FROM Test08 UNION ALL
SELECT * FROM Test09 UNION ALL
SELECT * FROM Test10
) AS Bunch
WHERE SomeKey = 39;

Es wird ein Abfrageplan angezeigt, bei dem die Zeilen übereinstimmen (mit dem Prädikat Pushdown im Operator TABLE SCAN) und dann alle Ergebnisse in den SELECTOperator verkettet werden.

Der Grund dafür, dass Sie keinen Plan zusammenführen und dann sortieren, ist, dass er sehr langsam ist und die Sortierung nicht erforderlich ist, um den UNIONVorgang zu implementieren . In Ihren BOO-, FOO- und KOO-Tabellen haben Sie einen Primärschlüssel deklariert. Wenn der CLUSTERED INDEX SCAN-Accessor die Zeilen auflistet, werden sie garantiert in der Reihenfolge des zugrunde liegenden Clustered-Index erstellt. Das Verketten von zwei Sätzen und das Sortieren des Ergebnisses ist viel langsamer als die Verwendung des Operators MERGE JOIN, und der Operator MJ kann sehr einfach verwendet werden, da beide Sätze sortiert und indiziert sind.

MikeB
quelle