Warum ist diese Schätzung der Join-Kardinalität so groß?

Ich erlebe eine meiner Meinung nach unglaublich hohe Kardinalitätsschätzung für die folgende Abfrage:

SELECT dm.PRIMARY_ID
FROM
(
    SELECT COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID) PRIMARY_ID
    FROM X_DRIVING_TABLE dt
    LEFT OUTER JOIN X_DETAIL_1 d1 ON dt.ID = d1.ID
    LEFT OUTER JOIN X_DETAIL_LINK lnk ON d1.LINK_ID = lnk.LINK_ID
    LEFT OUTER JOIN X_DETAIL_2 d2 ON dt.ID = d2.ID
    LEFT OUTER JOIN X_DETAIL_3 d3 ON dt.ID = d3.ID
) dm
INNER JOIN X_LAST_TABLE lst ON dm.PRIMARY_ID = lst.JOIN_ID;

Der geschätzte Plan ist hier . Ich arbeite an einer Statistikkopie der Tabellen, daher kann ich keinen tatsächlichen Plan angeben. Ich denke jedoch nicht, dass es für dieses Problem sehr relevant ist.

SQL Server schätzt, dass 481577 Zeilen aus der abgeleiteten Tabelle "dm" zurückgegeben werden. Anschließend wird geschätzt, dass 4528030000 Zeilen zurückgegeben werden, nachdem die Verknüpfung zu X_LAST_TABLE ausgeführt wurde, JOIN_ID ist jedoch der Primärschlüssel von X_LAST_TIME. Ich würde eine Join-Kardinalitätsschätzung zwischen 0 und 481577 Zeilen erwarten. Stattdessen scheint die Zeilenschätzung 10% der Anzahl der Zeilen zu betragen, die ich beim Cross-Joining der äußeren und inneren Tabelle erhalten würde. Die Mathematik hierfür arbeitet mit einer Rundung: 481577 * 94025 * 0,1 = 45280277425, die auf 4528030000 gerundet wird.

Ich suche hauptsächlich nach einer Ursache für dieses Verhalten. Ich interessiere mich auch für einfache Problemumgehungen, empfehle jedoch nicht, das Datenmodell zu ändern oder temporäre Tabellen zu verwenden. Diese Abfrage ist eine Vereinfachung der Logik in einer Ansicht. Ich weiß, dass es keine gute Praxis ist, COALESCE an einigen Spalten durchzuführen und sich ihnen anzuschließen. Ein Teil des Ziels dieser Frage besteht darin, herauszufinden, ob ich die Neugestaltung des Datenmodells empfehlen muss.

Ich teste auf Microsoft SQL Server 2014 mit aktiviertem Legacy-Kardinalitätsschätzer. TF 4199 und andere sind an. Ich kann eine vollständige Liste der Ablaufverfolgungsflags angeben, wenn dies relevant ist.

Hier ist die relevanteste Tabellendefinition:

CREATE TABLE X_LAST_TABLE (
JOIN_ID NUMERIC(18, 0) NOT NULL
    CONSTRAINT PK_X_LAST_TABLE PRIMARY KEY CLUSTERED (JOIN_ID ASC)
);

Ich habe auch alle Tabellenerstellungsskripte zusammen mit ihren Statistiken als Skript erstellt, wenn jemand das Problem auf einem seiner Server reproduzieren möchte.

Um einige meiner Beobachtungen hinzuzufügen, korrigiert die Verwendung von TF 2312 die Schätzung, aber das ist für mich keine Option. TF 2301 korrigiert die Schätzung nicht. Durch Entfernen einer der Tabellen wird die Schätzung korrigiert. Seltsamerweise wird durch Ändern der Verknüpfungsreihenfolge von X_DETAIL_LINK auch die Schätzung korrigiert. Mit der Änderung der Join-Reihenfolge meine ich, die Abfrage neu zu schreiben und die Join-Reihenfolge nicht mit einem Hinweis zu erzwingen. Hier ist ein geschätzter Abfrageplan, wenn Sie nur die Reihenfolge der Joins ändern.

Ich weiß, dass COALESCEes keine gute Praxis ist, ein paar Spalten zu bearbeiten und sich ihnen anzuschließen.

Das Generieren guter Kardinalitäts- und Verteilungsschätzungen ist schwierig genug, wenn das Schema 3NF + (mit Schlüsseln und Einschränkungen) und die Abfrage relational und in erster Linie SPJG (Auswahl-Projektion-Join-Gruppierung nach) ist. Das CE-Modell baut auf diesen Prinzipien auf. Je ungewöhnlicher oder nicht relationaler eine Abfrage ist, desto näher kommt man den Grenzen dessen, was das Kardinalitäts- und Selektivitäts-Framework handhaben kann. Gehen Sie zu weit und CE wird aufgeben und raten .

Der größte Teil des MCVE-Beispiels ist einfaches SPJ (kein G), allerdings mit überwiegend äußeren Equijoins (modelliert als inneres Join plus Antisemijoin) anstelle des einfacheren inneren Equijoins (oder Semijoins). Alle Relationen haben Schlüssel, jedoch keine Fremdschlüssel oder andere Einschränkungen. Alle bis auf einen Joins sind Eins-zu-Viele, was gut ist.

Die Ausnahme ist die Viele-zu-Viele- Verknüpfung zwischen X_DETAIL_1und X_DETAIL_LINK. Die einzige Funktion dieses Joins im MCVE ist das potenzielle Duplizieren von Zeilen in X_DETAIL_1. Dies ist eine ungewöhnliche Sache.

Einfache Gleichheitsprädikate (Auswahlen) und Skalaroperatoren sind ebenfalls besser. Zum Beispiel funktioniert Attribut-Vergleich-gleiches Attribut / Konstante im Modell normalerweise gut. Es ist relativ "einfach", Histogramme und Häufigkeitsstatistiken zu ändern, um die Anwendung solcher Prädikate widerzuspiegeln.

COALESCEwird auf gebaut CASE, was wiederum intern als implementiert wird IIF(und dies war schon lange wahr, bevor es IIFin der Transact-SQL-Sprache erschien). Die CE - Modelle IIFals ein UNIONmit zwei sich gegenseitig ausschließende Kinder, bestehend jeweils aus einem Projekt auf einer Auswahl an der Eingangs Beziehung. Jede der aufgelisteten Komponenten verfügt über eine Modellunterstützung, sodass das Kombinieren relativ einfach ist. Je mehr Abstraktionen überlagert werden, desto ungenauer ist das Endergebnis - ein Grund, warum größere Ausführungspläne in der Regel weniger stabil und zuverlässig sind.

ISNULLAuf der anderen Seite ist intrinsische zum Motor. Es wird nicht mehr mit Grundkomponenten aufgebaut. Das Anwenden des Effekts ISNULLauf ein Histogramm ist beispielsweise so einfach wie das Ersetzen des Schritts für NULLWerte (und das Komprimieren nach Bedarf). Es ist immer noch relativ undurchsichtig, wie es skalare Operatoren tun, und wird daher am besten vermieden, wenn dies möglich ist. Trotzdem ist es im Allgemeinen optimiererfreundlicher (weniger optimiererunfreundlich) als ein auf CASE-basierendes alternatives Verfahren.

Das CE (70 und 120+) ist selbst für SQL Server-Standards sehr komplex. Es geht nicht darum, jedem Operator eine einfache Logik (mit einer geheimen Formel) zuzuweisen. Das CE kennt Schlüssel und funktionale Abhängigkeiten. Es kann anhand von Häufigkeiten, multivariaten Statistiken und Histogrammen schätzen. und es gibt jede Menge Sonderfälle, Verfeinerungen, Checks & Balances und unterstützende Strukturen. Sie schätzt zB Verknüpfungen häufig auf mehrere Arten (Häufigkeit, Histogramm) und entscheidet über ein Ergebnis oder eine Anpassung basierend auf den Unterschieden zwischen den beiden.

Eine letzte grundlegende Sache, die behandelt werden muss: Die erste Kardinalitätsschätzung wird für jede Operation in der Abfragestruktur von unten nach oben ausgeführt. Selektivität und Kardinalität werden zuerst für Blattoperatoren abgeleitet (Basisrelationen). Geänderte Histogramme und Dichte- / Frequenzinformationen werden für übergeordnete Bediener abgeleitet. Je höher der Baum, desto geringer ist die Qualität der Schätzungen, da sich häufig Fehler ansammeln.

Diese einzelne anfängliche umfassende Schätzung stellt einen Ausgangspunkt dar und tritt auf, lange bevor ein endgültiger Ausführungsplan in Betracht gezogen wird (dies geschieht weit vor der Kompilierungsphase des Trivialplans). Der Abfragebaum an dieser Stelle spiegelt in der Regel die geschriebene Form der Abfrage ziemlich genau wider (obwohl Unterabfragen entfernt und Vereinfachungen angewendet wurden usw.).

Unmittelbar nach der ersten Schätzung führt SQL Server eine heuristische Join-Neuordnung durch, bei der lose gesagt versucht wird, die Struktur neu anzuordnen, um kleinere Tabellen und Joins mit hoher Selektivität zuerst zu platzieren. Es wird auch versucht, innere Verknüpfungen vor äußeren Verknüpfungen zu positionieren und Produkte zu kreuzen. Seine Fähigkeiten sind nicht umfangreich; ihre Bemühungen sind nicht erschöpfend; und physische Kosten werden nicht berücksichtigt (da sie noch nicht existieren - nur statistische Informationen und Metadateninformationen sind vorhanden). Die heuristische Neuordnung ist am erfolgreichsten bei einfachen inneren Equijoin-Bäumen. Sie soll einen "besseren" Ausgangspunkt für eine kostenbasierte Optimierung bieten.

Warum ist diese Schätzung der Join-Kardinalität so groß?

Die MCVE hat eine "ungewöhnliche", meist redundante Viele-zu-Viele- Verknüpfung und eine Equi-Verknüpfung mit COALESCEdem Prädikat. Der Operator-Baum hat auch einen inneren Verknüpfungs- Letzten , der durch die heuristische Verknüpfungs-Neuordnung nicht an eine bevorzugtere Position verschoben werden konnte. Abgesehen von allen Skalaren und Projektionen lautet der Verknüpfungsbaum wie folgt:

LogOp_Join [ Card=4.52803e+009 ]
    LogOp_LeftOuterJoin [ Card=481577 ]
        LogOp_LeftOuterJoin [ Card=481577 ]
            LogOp_LeftOuterJoin [ Card=481577 ]
                LogOp_LeftOuterJoin [ Card=481577 ]
                LogOp_Get TBL: X_DRIVING_TABLE(alias TBL: dt) [ Card=481577 ]
                LogOp_Get TBL: X_DETAIL_1(alias TBL: d1) [ Card=70 ]
                LogOp_Get TBL: X_DETAIL_LINK(alias TBL: lnk) [ Card=47 ]
            LogOp_Get TBL: X_DETAIL_2(alias TBL: d2) X_DETAIL_2 [ Card=119 ]
        LogOp_Get TBL: X_DETAIL_3(alias TBL: d3) X_DETAIL_3 [ Card=281 ]
    LogOp_Get TBL: X_LAST_TABLE(alias TBL: lst) X_LAST_TABLE [ Card=94025 ]

Beachten Sie, dass die fehlerhafte endgültige Schätzung bereits vorliegt. Es wird als Card=4.52803e+009Gleitkommawert mit doppelter Genauigkeit 4.5280277425e + 9 (4528027742.5 in Dezimal) gedruckt und intern gespeichert.

Die abgeleitete Tabelle in der ursprünglichen Abfrage wurde entfernt und die Projektionen normalisiert. Eine SQL-Darstellung des Baums, an dem die erste Kardinalitäts- und Selektivitätsschätzung durchgeführt wurde, ist:

SELECT 
    PRIMARY_ID = COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)
FROM X_DRIVING_TABLE dt
LEFT OUTER JOIN X_DETAIL_1 d1
    ON dt.ID = d1.ID
LEFT OUTER JOIN X_DETAIL_LINK lnk 
    ON d1.LINK_ID = lnk.LINK_ID
LEFT OUTER JOIN X_DETAIL_2 d2 
    ON dt.ID = d2.ID
LEFT OUTER JOIN X_DETAIL_3 d3 
    ON dt.ID = d3.ID
INNER JOIN X_LAST_TABLE lst 
    ON lst.JOIN_ID = COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)

(Abgesehen davon ist die Wiederholung COALESCEauch im endgültigen Plan vorhanden - einmal im endgültigen Berechnungsskalar und einmal auf der Innenseite des inneren Joins).

Beachten Sie die endgültige Verknüpfung. Diese innere Verknüpfung ist (per Definition) das kartesische Produkt von X_LAST_TABLEund der vorhergehenden Verknüpfungsausgabe, wobei eine Auswahl (Verknüpfungsprädikat) von lst.JOIN_ID = COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)angewendet wird. Die Kardinalität des kartesischen Produkts ist einfach 481577 * 94025 = 45280277425.

Dazu müssen wir die Selektivität des Prädikats bestimmen und anwenden. Die Kombination des undurchsichtigen erweiterten COALESCEBaums (in Bezug auf UNIONund IIF, denken Sie daran) zusammen mit der Auswirkung auf die Schlüsselinformationen, abgeleiteten Histogramme und Häufigkeiten der früheren "ungewöhnlichen", meist redundanten, kombinierten Viele-zu-Viele-Außenverknüpfung bedeutet, dass das CE nicht dazu in der Lage ist Leiten Sie eine akzeptable Schätzung auf eine der normalen Arten ab.

Infolgedessen wird die Guess Logic aufgerufen. Die Vermutungslogik ist mäßig komplex, wobei Schichten von "gebildeten" Vermutungsalgorithmen und "nicht so gebildeten" Vermutungsalgorithmen ausprobiert werden. Wenn keine bessere Basis für eine Vermutung gefunden wird, verwendet das Modell eine Vermutung des letzten Auswegs, die für einen Gleichheitsvergleich wie folgt lautet: sqllang!x_Selectivity_Equal= feste 0,1-Selektivität (10% Vermutung):

-- the moment of doom
movsd xmm0,mmword ptr [sqllang!x_Selectivity_Equal

Das Ergebnis ist 0,1 Selektivität für das kartesische Produkt: 481577 * 94025 * 0,1 = 4528027742,5 (~ 4,52803e + 009), wie zuvor erwähnt.

Schreibt neu

Wenn die problematische Verknüpfung auskommentiert wird , wird eine bessere Schätzung erstellt, da die feste Selektivität "Vermutung des letzten Auswegs" vermieden wird (Schlüsselinformationen werden von den 1-M- Verknüpfungen beibehalten). Die Qualität der Schätzung ist immer noch wenig zuverlässig, da ein COALESCEJoin-Prädikat überhaupt nicht CE-kompatibel ist. Die revidierte Schätzung hat zumindest Blick vernünftigen Menschen, nehme ich an.

Wenn die Abfrage so geschrieben wird, dass der äußere Join X_DETAIL_LINK den letzten Platz einnimmt, kann die heuristische Neuordnung sie durch den endgültigen inneren Join ersetzen X_LAST_TABLE. Wenn Sie den inneren Join direkt neben das Problem stellen, können Sie mit den eingeschränkten Möglichkeiten einer frühen Nachbestellung die endgültige Schätzung verbessern, da die Auswirkungen des meist redundanten "ungewöhnlichen" äußeren Joins nach der heiklen Selektivitätsschätzung auftreten für COALESCE. Auch hier sind die Schätzungen kaum besser als feste Vermutungen und würden einer entschlossenen gerichtlichen Gegenprüfung wahrscheinlich nicht standhalten.

Das Neuordnen einer Mischung aus inneren und äußeren Verknüpfungen ist schwierig und zeitaufwendig (selbst bei der vollständigen Optimierung in Stufe 2 wird nur eine begrenzte Teilmenge der theoretischen Schritte versucht).

Die ISNULLin Max Vernons Antwort vorgeschlagene Verschachtelung vermeidet die festgelegte Rettung, aber die endgültige Schätzung ist eine unwahrscheinliche Null (aus Gründen des Anstands zu einer Zeile angehoben). Dies könnte genauso gut eine feste Schätzung von 1 Zeile sein, für alle statistischen Grundlagen, die die Berechnung hat.

Ich würde eine Join-Kardinalitätsschätzung zwischen 0 und 481577 Zeilen erwarten.

Dies ist eine vernünftige Erwartung, auch wenn man akzeptiert, dass die Kardinalitätsschätzung zu unterschiedlichen Zeitpunkten (während der kostenbasierten Optimierung) auf physikalisch unterschiedlichen, aber logisch und semantisch identischen Teilbäumen erfolgen kann - wobei der endgültige Plan eine Art zusammengenähter Best-Of-Plan ist am besten (pro Memogruppe). Das Fehlen einer planweiten Konsistenzgarantie bedeutet nicht, dass ein einzelner Join in der Lage sein sollte, sich über Seriosität hinwegzusetzen, das verstehe ich.

Auf der anderen Seite ist die Hoffnung schon verloren, wenn wir die Vermutung des letzten Auswegs haben. Warum also die Mühe machen? Wir haben alle Tricks ausprobiert und aufgegeben. Nicht zuletzt ist die wilde Endabschätzung ein gutes Warnsignal dafür, dass bei der Kompilierung und Optimierung dieser Abfrage im CE nicht alles gut gelaufen ist.

Als ich das MCVE ausprobierte, erstellte das 120+ CE eine Null (= 1) -Zeilenendschätzung (wie die verschachtelte ISNULL) für die ursprüngliche Abfrage, was für meine Denkweise ebenso inakzeptabel ist.

Die eigentliche Lösung besteht wahrscheinlich in einer Designänderung, um einfache Equi-Joins ohne COALESCEoder ISNULLund im Idealfall Fremdschlüssel und andere für die Abfragekompilierung nützliche Einschränkungen zu ermöglichen.

Ich glaube, dass der Compute ScalarOperator, der sich aus dem COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)Beitritt X_LAST_TABLE.JOIN_IDergibt, die Hauptursache für das Problem ist. In der Vergangenheit war es schwierig, Rechenskalare genau zu berechnen ^{1 , 2} .

Da Sie ein minimal verifizierbares Beispiel (danke!) Mit genauen Statistiken angegeben haben, kann ich die Abfrage so umschreiben, dass für den Join nicht mehr die CASEFunktionalität erforderlich COALESCEist, die erweitert wurde, was zu genaueren Zeilenschätzungen und anscheinend zu mehr führt genaue Gesamtkalkulation ^{Siehe Anhang am Ende.} :

SELECT COALESCE(dm.d1ID, dm.d2ID, dm.d3ID)
FROM
(
    SELECT d1ID = d1.JOIN_ID
        , d2ID = d2.JOIN_ID
        , d3ID = d3.JOIN_ID
    FROM X_DRIVING_TABLE dt
    LEFT OUTER JOIN X_DETAIL_1 d1 ON dt.ID = d1.ID
    LEFT OUTER JOIN X_DETAIL_LINK lnk ON d1.LINK_ID = lnk.LINK_ID
    LEFT OUTER JOIN X_DETAIL_2 d2 ON dt.ID = d2.ID
    LEFT OUTER JOIN X_DETAIL_3 d3 ON dt.ID = d3.ID
) dm
INNER JOIN X_LAST_TABLE lst 
    ON (dm.d1ID IS NOT NULL AND dm.d1ID = lst.JOIN_ID)
    OR (dm.d1ID IS NULL AND dm.d2ID IS NOT NULL AND dm.d2ID = lst.JOIN_ID)
    OR (dm.d1ID IS NULL AND dm.d2ID IS NULL AND dm.d3ID IS NOT NULL AND dm.d3ID = lst.JOIN_ID);

Während das xID IS NOT NULLtechnisch nicht erforderlich ist, da das ID = JOIN_IDnicht mit Nullwerten verknüpft wird, habe ich sie einbezogen, da es die Absicht klarer darstellt.

Plan 1 und Plan 2

Plan 1:

Plan 2:

Die neue Abfrage profitiert von der Parallelisierung. Zu beachten ist auch, dass die neue Abfrage eine geschätzte Ausgabezahl von 1 aufweist, die am Ende des Tages möglicherweise schlechter ist als die Schätzung von 4528030000 für die ursprüngliche Abfrage. Die Teilbaumkosten für den Auswahloperator in der neuen Abfrage liegen bei 243210, während die ursprünglichen Kosten bei 536.535 liegen, was deutlich weniger ist. Trotzdem glaube ich nicht, dass die erste Schätzung der Realität nahe kommt.

Anhang 1.

Nach weiteren Gesprächen mit verschiedenen Personen zu The Heap ™, die durch eine Diskussion mit @Lamak angeregt wurden, scheint meine obige Beobachtungsabfrage trotz der Parallelität eine schreckliche Leistung zu erbringen. Eine Lösung, die sowohl eine gute Leistung als auch gute Kardinalitätsschätzungen ermöglicht, besteht darin, die COALESCE(x,y,z)durch eine zu ersetzen ISNULL(ISNULL(x, y), z), wie in:

SELECT dm.PRIMARY_ID
FROM
(
    SELECT ISNULL(ISNULL(d1.JOIN_ID, d2.JOIN_ID), d3.JOIN_ID) PRIMARY_ID
    FROM X_DRIVING_TABLE dt
    LEFT OUTER JOIN X_DETAIL_1 d1 ON dt.ID = d1.ID
    LEFT OUTER JOIN X_DETAIL_LINK lnk ON d1.LINK_ID = lnk.LINK_ID
    LEFT OUTER JOIN X_DETAIL_2 d2 ON dt.ID = d2.ID
    LEFT OUTER JOIN X_DETAIL_3 d3 ON dt.ID = d3.ID
) dm
INNER JOIN X_LAST_TABLE lst ON dm.PRIMARY_ID = lst.JOIN_ID;

COALESCEwird CASEvom Abfrageoptimierer in eine Anweisung "under the covers" umgewandelt. Aus diesem Grund fällt es dem Kardinalitätsschätzer schwerer, zuverlässige Statistiken für die darin vergrabenen Spalten zu ermitteln COALESCE. ISNULLEine intrinsische Funktion zu sein, ist für den Kardinalitätsschätzer viel "offener". Es ist auch nichts wert, ISNULLdas optimiert werden kann, wenn bekannt ist, dass das Ziel nicht nullwertfähig ist.

Der Plan für die ISNULLVariante sieht folgendermaßen aus:

(Fügen Sie die Planversion hier ein ).

Zu Ihrer Information, wir danken Sentry One für ihren großartigen Plan Explorer, mit dem ich die obigen grafischen Pläne erstellt habe.

Gemäß Ihrer Join-Bedingung kann die Tabelle auf so viele Arten angeordnet werden, dass "auf eine bestimmte Art und Weise geändert" wird, um das Ergebnis zu korrigieren.

Angenommen, Sie erhalten ein korrektes Ergebnis, wenn Sie nur eine Tabelle verbinden.

SELECT COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID) PRIMARY_ID
    FROM X_DRIVING_TABLE dt
    LEFT OUTER JOIN X_DETAIL_1 d1 ON dt.ID = d1.ID
    LEFT OUTER JOIN X_DETAIL_LINK lnk ON d1.LINK_ID = lnk.LINK_ID

Hier können Sie anstelle von X_DETAIL_1entweder X_DETAIL_2oder verwenden X_DETAIL_3.

Daher sind Zweck der Ruhe 2 Tabellen nicht klar.

Es ist, als hätten Sie den Tisch X_DETAIL_1in zwei weitere Teile geteilt.

Wahrscheinlich „ es gibt Fehler in dem Sie die Tabellen bevölkern . “ Im Idealfall X_DETAIL_1, X_DETAIL_2und X_DETAIL_3soll die gleiche Menge von Zeilen enthalten.

Eine oder mehrere Tabellen enthalten jedoch eine unerwünschte Anzahl von Zeilen.

Entschuldigung, wenn ich falsch liege.