Flow Distinct erzwingen

19

Ich habe einen Tisch wie diesen:

CREATE TABLE Updates
(
    UpdateId INT NOT NULL IDENTITY(1,1) PRIMARY KEY,
    ObjectId INT NOT NULL
)

Verfolgen Sie im Wesentlichen Aktualisierungen von Objekten mit zunehmender ID.

Der Konsument dieser Tabelle wählt einen Teil von 100 verschiedenen Objekt-IDs aus, die nach UpdateIdeinem bestimmten geordnet sind und von diesem ausgehen UpdateId. Verfolgen Sie im Wesentlichen, wo es aufgehört hat, und fragen Sie dann nach Updates.

Ich habe dies als interessantes Optimierungsproblem empfunden, da ich nur durch das Schreiben von Abfragen einen maximal optimalen Abfrageplan generieren konnte passieren zu tun , was ich Indizes auf Grund will, aber nicht garantieren , was ich will:

SELECT DISTINCT TOP 100 ObjectId
FROM Updates
WHERE UpdateId > @fromUpdateId

Wo @fromUpdateIdist ein Parameter einer gespeicherten Prozedur?

Mit einem Plan von:

SELECT <- TOP <- Hash match (flow distinct, 100 rows touched) <- Index seek

Aufgrund der Suche nach dem verwendeten UpdateIdIndex sind die Ergebnisse bereits gut und werden von der niedrigsten zur höchsten Update-ID sortiert, wie ich es möchte. Und dies erzeugt einen Flow-eigenen Plan, den ich mir wünsche. Aber die Bestellung ist offensichtlich kein garantiertes Verhalten, deshalb möchte ich es nicht verwenden.

Dieser Trick führt auch zum gleichen Abfrageplan (allerdings mit einem redundanten TOP):

WITH ids AS
(
    SELECT ObjectId
    FROM Updates
    WHERE UpdateId > @fromUpdateId
    ORDER BY UpdateId OFFSET 0 ROWS
)
SELECT DISTINCT TOP 100 ObjectId FROM ids

Ich bin mir jedoch nicht sicher (und vermute nicht), ob dies wirklich eine Bestellung garantiert.

Eine Abfrage, von der ich gehofft habe, dass SQL Server so intelligent ist, dass sie vereinfacht werden kann, generiert jedoch einen sehr schlechten Abfrageplan:

SELECT TOP 100 ObjectId
FROM Updates
WHERE UpdateId > @fromUpdateId
GROUP BY ObjectId
ORDER BY MIN(UpdateId)

Mit einem Plan von:

SELECT <- Top N Sort <- Hash Match aggregate (50,000+ rows touched) <- Index Seek

Ich versuche einen Weg zu finden, um einen optimalen Plan mit einer Indexsuche UpdateIdund einem bestimmten Fluss zu generieren , um doppelte ObjectIds zu entfernen . Irgendwelche Ideen?

Beispieldaten, wenn Sie es wollen. Objekte werden selten mehr als ein Update haben und sollten fast nie mehr als ein Update in einem Satz von 100 Zeilen haben. Aus diesem Grund bin ich nach einem bestimmten Flow strebend , es sei denn, es gibt etwas Besseres, von dem ich nichts weiß. Es gibt jedoch keine Garantie dafür, dass eine einzelne ObjectIdTabelle nicht mehr als 100 Zeilen enthält. Die Tabelle hat über 1.000.000 Zeilen und wird voraussichtlich schnell wachsen.

Angenommen, der Benutzer hat einen anderen Weg, um den entsprechenden nächsten zu finden @fromUpdateId. In dieser Abfrage muss es nicht zurückgegeben werden.

Cory Nelson
quelle

Antworten:

15

Das SQL Server-Optimierungsprogramm kann den gewünschten Ausführungsplan nicht mit der erforderlichen Garantie erstellen, da der Operator " Hash Match Flow Distinct" die Reihenfolge nicht beibehält.

Ich bin mir jedoch nicht sicher (und vermute nicht), ob dies wirklich eine Bestellung garantiert.

In vielen Fällen können Sie die Beibehaltung der Reihenfolge beobachten , dies ist jedoch ein Implementierungsdetail. Es gibt keine Garantie, Sie können sich also nicht darauf verlassen. Die Reihenfolge der Präsentationen kann wie immer nur von einem Top-Level garantiert werdenORDER BY Klausel .

Beispiel

Das folgende Skript zeigt, dass Hash Match Flow Distinct die Reihenfolge nicht beibehält. Es richtet die fragliche Tabelle mit den übereinstimmenden Nummern 1-50.000 in beiden Spalten ein:

IF OBJECT_ID(N'dbo.Updates', N'U') IS NOT NULL
    DROP TABLE dbo.Updates;
GO
CREATE TABLE Updates
(
    UpdateId INT NOT NULL IDENTITY(1,1),
    ObjectId INT NOT NULL,

    CONSTRAINT PK_Updates_UpdateId PRIMARY KEY (UpdateId)
);
GO
INSERT dbo.Updates (ObjectId)
SELECT TOP (50000)
    ObjectId =
        ROW_NUMBER() OVER (
            ORDER BY C1.[object_id]) 
FROM sys.columns AS C1
CROSS JOIN sys.columns AS C2
ORDER BY
    ObjectId;

Die Testabfrage lautet:

DECLARE @Rows bigint = 50000;

-- Optimized for 1 row, but will be 50,000 when executed
SELECT DISTINCT TOP (@Rows)
    U.ObjectId 
FROM dbo.Updates AS U
WHERE 
    U.UpdateId > 0
OPTION (OPTIMIZE FOR (@Rows = 1));

Der geschätzte Plan zeigt, dass Indexsuche und -fluss unterschiedlich sind:

Geschätzter Plan

Die Ausgabe scheint sicherlich zu beginnen mit:

Beginn der Ergebnisse

... aber weiter unten beginnen Werte zu "fehlen":

Das Muster bricht zusammen

...und schließlich:

Chaos bricht aus

Die Erklärung in diesem speziellen Fall ist, dass der Hash-Operator Folgendes verschüttet:

Plan nach der Ausführung

Sobald eine Partition verschüttet wird, werden auch alle Zeilen verschüttet, die zur selben Partition gehören. Verschüttete Partitionen werden später verarbeitet, was der Erwartung widerspricht, dass bestimmte Werte sofort in der Reihenfolge ausgegeben werden, in der sie empfangen wurden.


Es gibt viele Möglichkeiten, eine effiziente Abfrage zu schreiben, um das gewünschte geordnete Ergebnis zu erzielen, z. B. eine Rekursion oder die Verwendung eines Cursors. Mit Hash Match Flow Distinct ist dies jedoch nicht möglich .

Paul White sagt GoFundMonica
quelle
11

Ich bin mit dieser Antwort unzufrieden, da ich es nicht geschafft habe, einen Flow-eindeutigen Operator zusammen mit Ergebnissen zu erhalten, die garantiert korrekt sind. Ich habe jedoch eine Alternative, die bei korrekten Ergebnissen eine gute Leistung bringen sollte. Leider muss ein nicht gruppierter Index für die Tabelle erstellt werden.

Ich näherte mich diesem Problem, indem ich versuchte, mir eine Kombination von Spalten vorzustellen, die ich verwenden konnte, ORDER BYum die richtigen Ergebnisse zu erzielen DISTINCT, nachdem ich sie angewendet hatte. Der Mindestwert von UpdateIdpro ObjectIdzusammen mit ObjectIdist eine solche Kombination. Wenn Sie jedoch direkt nach dem Minimum fragen, werden UpdateIdanscheinend alle Zeilen aus der Tabelle gelesen. Stattdessen können wir indirekt den Mindestwert von UpdateIdmit einem anderen Join an der Tabelle abfragen. Die Idee ist, die UpdatesTabelle der Reihe nach zu durchsuchen und alle Zeilen auszuschließen, für die UpdateIdnicht der Mindestwert für diese Zeilen festgelegt istObjectId , und die ersten 100 Zeilen beizubehalten. Aufgrund Ihrer Beschreibung der Datenverteilung sollten wir nicht sehr viele Zeilen wegwerfen müssen.

Zur Datenvorbereitung habe ich eine Million Zeilen in eine Tabelle mit zwei Zeilen für jede einzelne ObjectId eingefügt:

INSERT INTO Updates WITH (TABLOCK)
SELECT t.RN / 2
FROM 
(
    SELECT TOP 1000000 -1 + ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) RN
    FROM master..spt_values t1
    CROSS JOIN master..spt_values t2
) t;

CREATE INDEX IX On Updates (Objectid, UpdateId);

Der nicht gruppierte Index auf Objectidund UpdateIdist wichtig. Dies ermöglicht es uns, Zeilen, die nicht das Minimum von UpdateIdper haben, effizient zu löschen Objectid. Es gibt viele Möglichkeiten, eine Abfrage zu schreiben, die der obigen Beschreibung entspricht. Hier ist ein solcher Weg mit NOT EXISTS:

DECLARE @fromUpdateId INT = 9999;
SELECT ObjectId
FROM (
    SELECT DISTINCT TOP 100 u1.UpdateId, u1.ObjectId
    FROM Updates u1
    WHERE UpdateId > @fromUpdateId
    AND NOT EXISTS (
        SELECT 1
        FROM Updates u2
        WHERE u2.UpdateId > @fromUpdateId
        AND u1.ObjectId = u2.ObjectId
        AND u2.UpdateId < u1.UpdateId
    )
    ORDER BY u1.UpdateId, u1.ObjectId
) t;

Hier ist ein Bild des Abfrageplans :

Abfrageplan

Im besten Fall führt SQL Server nur 100 Index-Suchvorgänge für den nicht gruppierten Index durch. Um zu simulieren, dass ich sehr viel Pech habe, habe ich die Abfrage so geändert, dass die ersten 5000 Zeilen an den Client zurückgegeben werden. Dies führte zu 9999 Index-Suchvorgängen. Es ist also so, als würde man einen Durchschnitt von 100 Zeilen pro Unterscheidung erhalten ObjectId. Hier ist die Ausgabe von SET STATISTICS IO, TIME ON:

Tabelle 'Updates'. Scananzahl 10000, logische Lesevorgänge 31900, physische Lesevorgänge 0

SQL Server-Ausführungszeiten: CPU-Zeit = 31 ms, verstrichene Zeit = 42 ms.

Joe Obbish
quelle
9

Ich liebe die Frage - Flow Distinct ist einer meiner Lieblingsoperatoren.

Nun die Garantie das Problem. Wenn Sie sich vorstellen, dass der FD-Operator Zeilen in einer geordneten Reihenfolge aus dem Seek-Operator zieht und jede Zeile so produziert, wie sie eindeutig ist, erhalten Sie die Zeilen in der richtigen Reihenfolge. Es ist jedoch schwer zu erkennen, ob es einige Szenarien gibt, in denen der FD nicht jeweils eine einzelne Zeile verarbeitet.

Theoretisch könnte der FD 100 Zeilen von der Suche anfordern und sie in der Reihenfolge produzieren, in der sie benötigt werden.

Die Abfragehinweise OPTION (FAST 1, MAXDOP 1)könnten hilfreich sein, da nicht mehr Zeilen vom Suchoperator abgerufen werden, als er benötigt. Ist es eine Garantie ? Nicht ganz. Es könnte sich immer noch dafür entscheiden, eine Seite mit Zeilen gleichzeitig zu ziehen, oder so ähnlich.

Ich denke mit OPTION (FAST 1, MAXDOP 1), Ihre OFFSETVersion würde Ihnen viel Vertrauen in die Bestellung geben, aber es ist keine Garantie.

Rob Farley
quelle
Wie ich es verstanden habe, besteht das Problem darin, dass der Flow Distinct-Operator eine Hash-Tabelle verwendet, die auf die Festplatte übertragen werden kann. Bei einem Überlauf werden Zeilen, die mit dem noch im RAM befindlichen Teil verarbeitet werden können, sofort verarbeitet, die anderen Zeilen werden jedoch erst verarbeitet, wenn die übergelaufenen Daten von der Festplatte zurückgelesen werden. Soweit ich weiß, kann kein Operator, der eine Hash-Tabelle (z. B. einen Hash-Join) verwendet, aufgrund seines Überlaufverhaltens die Ordnung gewährleisten.
sam.bishop
Richtig. Siehe die Antwort von Paul White.
Rob Farley