Ist es möglich, einen suchbasierten Parallelplan für verschiedene Gruppen zu erhalten?

7

Ein Beispiel aus dieser Frage zeigt, dass SQL Server einen vollständigen Index-Scan auswählt, um eine Abfrage wie die folgende zu lösen:

select distinct [typeName] from [types]

Wobei [typeName] einen nicht gruppierten, nicht eindeutigen aufsteigenden Index enthält. Sein Beispiel hat 200 Millionen Zeilen, aber nur 76 eindeutige Werte. Es scheint, als wäre ein Suchplan mit dieser Dichte die bessere Wahl (~ 76 mehrfache binäre Suchen)?

Sein Fall könnte normalisiert werden, aber der Grund für die Frage ist, dass ich wirklich so etwas lösen möchte:

select TransactionId, max(CreatedUtc) 
from TxLog 
group by TransactionId

Es gibt einen Index für (TransactionId, MaxCreatedUtc).

Das Umschreiben mit einer normalisierten Quelle (dt) ändert nichts am Plan.

select dt.TransactionId, MaxCreatedUtc
 from [Transaction] dt -- distinct transactions
 cross apply
   (
        select Max(CreatedUtc) as MaxCreatedUtc 
          from TxLog tl
         where tl.TransactionId = dt.TransactionId         
   ) ca

Wenn Sie nur die CA-Unterabfrage als skalare UDF ausführen, wird ein Plan mit 1 Suche angezeigt.

select max(CreatedUtc) as MaxCreatedUtc
 from Pub.TransactionLog 
 where TransactionID = @TxId;

Die Verwendung dieser skalaren UDF in der ursprünglichen Abfrage scheint zu funktionieren, verliert jedoch die Parallelität (bekanntes Problem mit UDFs):

select t.typeName, 
       Pub.ufn_TransactionMaxCreatedUtc(t.TransactionId) as MaxCreatedUtc
  from Pub.[Transaction] t

Pläne für Cross gelten, nur die UDF, mit UDF

Beim Umschreiben mit einem Inline-TVF wird es wieder auf den Scan-basierten Plan zurückgesetzt.

Aus Antwort / Kommentar @ypercube:

select TransactionId, MaxCreatedUtc        
 from Pub.[Transaction]  t
  cross apply
   (
        select top (1) CreatedUtc as MaxCreatedUtc 
        from Pub.TransactionLog l
        where l.TransactionID = t.TransactionId
        order by CreatedUtc desc                     
   ) ca

Planen Sie mit top / order

Plan sieht gut aus. Keine Parallelität, aber sinnlos da so schnell. Muss dies irgendwann bei einem größeren Problem versuchen. Vielen Dank.

crokusek
quelle
"das möchte ich wirklich lösen" - ein Index Skip Scan würde das für Sie tun. Derzeit implementiert MS SQL Server diese Optimierung nicht. Es ist ein MS Connect-Element dafür geöffnet. Wenn ich den Link wieder finde, werde ich ihn posten.
Michael Green
3
Scan Connect-Element überspringen . Geschlossen, da es nicht repariert werden kann, aber das bedeutet nicht, dass es in Zukunft nicht mehr behoben wird. Nur dass es wahrscheinlich nicht wird :)
Paul White 9

Antworten:

9

Ich habe genau das gleiche Setup und habe die gleichen Phasen des Umschreibens der Abfrage durchlaufen.

In meinem Fall sind die Tabellennamen und die Bedeutung etwas unterschiedlich, aber die Gesamtstruktur ist dieselbe. Ihre Tabelle Transactionsentspricht meiner Tabelle PortalElevatorsunten. Es hat ~ 2000 Zeilen. Ihr Tisch TxLogentspricht meinem Tisch PlaybackStats. Es hat ~ 150 Millionen Zeilen. Es hat Index auf (ElevatorID, DataSourceRowID), genau wie Sie.

Ich werde verschiedene Varianten der Abfrage für die realen Daten ausführen und Ausführungspläne, E / A und Zeitstatistiken vergleichen. Ich verwende SQL Server 2008 Standard.

GROUP BY mit MAX

SELECT [ElevatorID], MAX([DataSourceRowID]) AS LastItemID
FROM [dbo].[PlaybackStats]
GROUP BY [ElevatorID]

gruppiere nach

Gruppe nach Statistiken

Gruppe von io

Das gleiche wie für Sie optimiert den Index und aggregiert die Ergebnisse. Langsam.

Einzelne Reihe

Mal sehen, was der Optimierer tun würde, wenn ich MAXnur eine Zeile anfordern würde :

SELECT MAX([dbo].[PlaybackStats].[DataSourceRowID]) AS LastItemID
FROM [dbo].[PlaybackStats]
WHERE [dbo].[PlaybackStats].ElevatorID = 1

Individuell

Das Optimierungsprogramm ist intelligent genug, um den Index zu verwenden, und es führt eine Suche durch. Übrigens können wir sehen, dass der Optimierer den TOPOperator verwendet, obwohl die Abfrage ihn nicht hat. Dies ist ein beredtes Zeichen dafür , dass Optimierungsweg MAXund TOPetwas gemeinsam im Motor haben, aber sie sind verschieden , wie wir weiter unten sehen werden.

KREUZ MIT MAX

SELECT
    [dbo].[PortalElevators].elevatorsId
    ,LastItemID
FROM
    [dbo].[PortalElevators]
    CROSS APPLY
    (
        SELECT MAX([dbo].[PlaybackStats].[DataSourceRowID]) AS LastItemID
        FROM [dbo].[PlaybackStats]
        WHERE [dbo].[PlaybackStats].ElevatorID = [dbo].[PortalElevators].elevatorsId
    ) AS CA
;

Kreuz mit max

Kreuz mit max Statistiken anwenden

Kreuz mit max io anwenden

Das Optimierungsprogramm scannt weiterhin den Index. Es ist nicht klug genug, hier MAXin TOPSuchanfragen zu konvertieren und diese zu scannen. Langsam. Ich habe ursprünglich nicht an diese Variante gedacht, mein nächster Versuch war skalares UDF.

Skalare UDF

Ich habe gesehen, dass dieser Plan für das Abrufen MAXeiner einzelnen Zeile eine Indexsuche hatte, also habe ich diese einfache Abfrage in eine skalare UDF eingefügt.

CREATE FUNCTION [dbo].[GetElevatorLastID]
(
    @ParamElevatorID int
)
RETURNS bigint
AS
BEGIN
    DECLARE @Result bigint;
    SELECT @Result = MAX([dbo].[PlaybackStats].[DataSourceRowID])
    FROM [dbo].[PlaybackStats]
    WHERE [dbo].[PlaybackStats].ElevatorID = @ParamElevatorID;
    RETURN @Result;
END

SELECT
    [dbo].[PortalElevators].elevatorsId
    ,[dbo].[GetElevatorLastID]([dbo].[PortalElevators].elevatorsId) AS LastItemID
FROM
    [dbo].[PortalElevators]
;

udf

udf stats

udf io

Es läuft schnell. Zumindest viel schneller als Group by. Leider zeigt der Ausführungsplan keine Details zu UDF und was noch schlimmer ist, er zeigt nicht die tatsächlichen E / A-Statistiken (er enthält keine von UDF generierten E / A). Sie müssen Profiler ausführen, um alle Aufrufe der Funktion und ihre Statistiken anzuzeigen. Dieser Plan zeigt nur 6 Lesevorgänge. Der Plan für die einzelne Zeile enthält 4 Lesevorgänge, sodass die tatsächliche Zahl in der Nähe von: liegt 6 + 2779 * 4 = 6 + 11,116 = 11,122.

CROSS APPLY mit TOP

Schließlich entdeckte ich das CROSS APPLYund wie es angewendet werden kann ;-) in diesem Fall.

SELECT
    [dbo].[PortalElevators].elevatorsId
    ,LastItemID
FROM
    [dbo].[PortalElevators]
    CROSS APPLY
    (
        SELECT TOP(1) [dbo].[PlaybackStats].[DataSourceRowID] AS LastItemID
        FROM [dbo].[PlaybackStats]
        WHERE [dbo].[PlaybackStats].ElevatorID = [dbo].[PortalElevators].elevatorsId
        ORDER BY [dbo].[PlaybackStats].[DataSourceRowID] DESC
    ) AS CA
;

Kreuz mit oben auftragen

Kreuz mit Top-Statistiken anwenden

Kreuz mit Top Io anwenden

Hier ist der Optimierer klug genug, um ~ 2000 Suchvorgänge durchzuführen. Sie können sehen, dass die Anzahl der Lesevorgänge viel geringer ist als für group by. Schnell.

Interessanterweise ist die Anzahl der Lesevorgänge hier (11.850) etwas höher als die mit UDF (11.122) geschätzten Lesevorgänge. Tabellen-E / A-Statistiken mit CROSS APPLY11.844 Lesevorgängen und 2.779 Scan-Zählwerten der großen Tabelle geben die 11,844 / 2,779 ~= 4.26Lesevorgänge pro Indexsuche an. Bei der Suche nach einigen Werten werden höchstwahrscheinlich 4 Lesevorgänge und bei einigen 5 mit einem Durchschnitt von 4,26 verwendet. Es gibt 2.779 Suchvorgänge, aber es gibt nur Werte für 2.130 Zeilen. Wie gesagt, es ist schwierig, mit UDF ohne Profiler eine echte Anzahl von Lesevorgängen zu erhalten.

Rekursiver CTE

Wie in den Kommentaren erwähnt, beschrieb Paul White eine Methode zum Überspringen des rekursiven Index- Scans, um bestimmte Werte in einer großen Tabelle zu finden, ohne einen vollständigen Index-Scan durchzuführen, aber Index-Suchen rekursiv durchzuführen. Um die Rekursion zu starten, müssen wir den Wert MINoder MAXfür einen Anker finden, und dann addiert jeder Rekursionsschritt nacheinander den nächsten Wert. Der Beitrag erklärt es im Detail.

WITH RecursiveCTE
AS
(
    -- Anchor
    SELECT TOP (1) [ElevatorID], [DataSourceRowID]
    FROM [dbo].[PlaybackStats]
    ORDER BY [ElevatorID] DESC, [DataSourceRowID] DESC

    UNION ALL

    -- Recursive
    SELECT R.[ElevatorID], R.[DataSourceRowID]
    FROM
    (
        -- Number the rows
        SELECT
            T.[ElevatorID], T.[DataSourceRowID]
            ,ROW_NUMBER() OVER (ORDER BY T.[ElevatorID] DESC, T.[DataSourceRowID] DESC) AS rn
        FROM
            [dbo].[PlaybackStats] AS T
            INNER JOIN RecursiveCTE AS R ON R.[ElevatorID] > T.[ElevatorID]
    ) AS R
    WHERE
        -- Only the row that sorts lowest
        R.rn = 1
)
SELECT [ElevatorID], [DataSourceRowID]
FROM RecursiveCTE
OPTION (MAXRECURSION 0);

rekursiv

rekursive Statistiken

rekursives io

Es ist ziemlich schnell, obwohl es fast doppelt so viele Lesevorgänge ausführt wie CROSS APPLY. Es liest 12.781 ein Worktableund 8.524 ein PlaybackStats. Auf der anderen Seite werden so viele Suchvorgänge ausgeführt, wie unterschiedliche Werte in der großen Tabelle vorhanden sind. CROSS APPLYmit TOPführt so viele Suchvorgänge durch, wie Zeilen in der kleinen Tabelle vorhanden sind. In meinem Fall hat eine kleine Tabelle 2.779 Zeilen, aber eine große Tabelle hat nur 2.130 verschiedene Werte.

Zusammenfassung

                         Logical Reads       Duration
CROSS APPLY with MAX           482,121          6,604
GROUP BY with MAX              482,123          6,581
Scalar UDF                    ~ 11,122            728
Recursive                       21,305             30
CROSS APPLY with TOP            11,850              9 (nine!)

Ich habe jede Abfrage dreimal ausgeführt und die beste Zeit ausgewählt. Es gab keine physischen Lesungen.

Fazit

In diesem speziellen greatest-n-per-groupProblemfall haben wir:

  • n=1;;
  • Die Anzahl der Gruppen ist viel kleiner als die Anzahl der Zeilen in einer Tabelle.
  • es gibt einen geeigneten Index;

Zwei beste Methoden sind:

  1. Falls wir eine kleine Tabelle mit der Liste der Gruppen haben, ist die beste Methode CROSS APPLYmit TOP.

  2. Wenn wir nur eine große Tabelle haben, ist die beste Methode Recursive Index Skip Scan.

Vladimir Baranov
quelle
1
Dies verdient mehr Stimmen.
AgentFire