Wymuszanie odrębnego przepływu

19

Mam taki stół:

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

Zasadniczo śledzenie aktualizacji obiektów o rosnącym ID.

Konsument tej tabeli wybiera fragment 100 różnych identyfikatorów obiektów, uporządkowanych według UpdateIdi rozpoczynając od określonego UpdateId. Zasadniczo, śledząc, gdzie przerwał, a następnie sprawdzając wszelkie aktualizacje.

Uważam, że jest to interesujący problem z optymalizacją, ponieważ byłem w stanie wygenerować maksymalnie optymalny plan zapytań, pisząc zapytania, które akurat robią to, co chcę z powodu indeksów, ale nie gwarantuję tego, czego chcę:

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

Gdzie @fromUpdateIdjest parametr procedury składowanej.

Z planem:

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

Z powodu wykorzystywanego wyszukiwania UpdateIdindeksu wyniki są już ładne i uporządkowane od najniższego do najwyższego identyfikatora aktualizacji, tak jak chcę. I to generuje odrębny plan przepływu , czego chcę. Ale porządkowanie oczywiście nie jest gwarantowanym zachowaniem, więc nie chcę go używać.

Ta sztuczka daje również ten sam plan zapytań (choć ze zbędnym TOP):

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

Chociaż nie jestem pewien (i nie podejrzewam), czy to naprawdę gwarantuje zamówienie.

Jedno z zapytań, które miałem nadzieję, że SQL Server będzie wystarczająco inteligentny, aby uprościć to, ale w końcu generuje bardzo zły plan zapytań:

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

Z planem:

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

Próbuję znaleźć sposób na wygenerowanie optymalnego planu z wyszukiwaniem indeksu UpdateIdi przepływem odrębnym do usuwania duplikatów ObjectId. Jakieś pomysły?

Przykładowe dane, jeśli chcesz. Obiekty rzadko będą miały więcej niż jedną aktualizację i prawie nigdy nie powinny mieć więcej niż jednej aktualizacji w zestawie 100 wierszy, dlatego właśnie mam wyraźny przepływ , chyba że jest coś lepszego, o czym nie wiem? Jednak nie ma gwarancji, że jeden ObjectIdnie będzie miał więcej niż 100 wierszy w tabeli. Tabela ma ponad 1 000 000 wierszy i oczekuje się szybkiego wzrostu.

Załóżmy, że użytkownik tego ma inny sposób na znalezienie odpowiedniego następnego @fromUpdateId. Nie ma potrzeby zwracania go w tym zapytaniu.

Cory Nelson
źródło

Odpowiedzi:

15

Optymalizator programu SQL Server nie może opracować wymaganego planu wykonania z wymaganą gwarancją, ponieważ operator Hash Match Flow Distinct nie zachowuje zamówień.

Chociaż nie jestem pewien (i nie podejrzewam), czy to naprawdę gwarantuje zamówienie.

W wielu przypadkach możesz obserwować zachowanie porządku, ale jest to szczegół implementacji; nie ma gwarancji, więc nie możesz na niej polegać. Jak zawsze kolejność prezentacji może być zagwarantowana tylko przez ORDER BYklauzulę najwyższego poziomu .

Przykład

Poniższy skrypt pokazuje, że Hash Match Flow Distinct nie zachowuje porządku. Ustawia przedmiotową tabelę z pasującymi liczbami 1-50 000 w obu kolumnach:

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;

Zapytanie testowe to:

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));

Szacowany plan pokazuje odrębne wyszukiwanie i przepływ indeksu:

Szacowany plan

Wydaje się, że wyjście na pewno jest uporządkowane od:

Początek wyników

... ale dalsze spadające wartości zaczynają „brakować”:

Rozpadający się wzór

...i ostatecznie:

Wybucha chaos

Wyjaśnienie w tym konkretnym przypadku jest takie, że operator skrótu wylewa:

Plan po wykonaniu

Gdy partycja się rozleje, wszystkie wiersze, które mają skrót do tej samej partycji, również się przeleją. Rozlane partycje są przetwarzane później, przełamując oczekiwanie, że napotkane odrębne wartości zostaną natychmiast wyemitowane w kolejności ich otrzymania.


Istnieje wiele sposobów na napisanie wydajnego zapytania w celu uzyskania żądanego uporządkowanego wyniku, takiego jak rekurencja lub użycie kursora. Nie można tego jednak zrobić za pomocą funkcji Hash Match Flow Distinct .

Paul White mówi GoFundMonica
źródło
11

Nie jestem usatysfakcjonowany tą odpowiedzią, ponieważ nie udało mi się uzyskać odrębnego operatora przepływu wraz z wynikami, które gwarantowałyby poprawność. Mam jednak alternatywę, która powinna uzyskać dobrą wydajność i prawidłowe wyniki. Niestety wymaga to utworzenia tabeli nieklastrowanej w tabeli.

Podszedłem do tego problemu, próbując wymyślić kombinację kolumn, którą mogłem, ORDER BYi uzyskać poprawne wyniki po zastosowaniu DISTINCTdo nich. Minimalna wartość UpdateIdper ObjectIdwraz z ObjectIdjest jedną taką kombinacją. Jednak bezpośrednie pytanie o minimum UpdateIdwydaje się skutkować odczytaniem wszystkich wierszy z tabeli. Zamiast tego możemy pośrednio poprosić o minimalną wartość UpdateIdprzy kolejnym złączeniu do tabeli. Chodzi o to, aby zeskanować Updatestabelę w kolejności, wyrzucić wszystkie wiersze, dla których UpdateIdnie jest to minimalna wartość dla tego wiersza ObjectId, i zachować pierwsze 100 wierszy. Na podstawie twojego opisu dystrybucji danych nie powinniśmy musieć wyrzucać zbyt wielu wierszy.

W celu przygotowania danych umieściłem 1 milion wierszy w tabeli z 2 wierszami dla każdego odrębnego obiektu ObjectId:

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);

Indeks nieklastrowany jest włączony Objectidi UpdateIdjest ważny. Pozwala nam to skutecznie wyrzucać wiersze, które nie mają minimalnej liczby UpdateIdna Objectid. Istnieje wiele sposobów napisania zapytania zgodnego z powyższym opisem. Oto jeden z takich sposobów 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;

Oto zdjęcie planu zapytań :

plan zapytań

W najlepszym przypadku SQL Server wykona tylko 100 wyszukiwań indeksu względem indeksu nieklastrowanego. Aby zasymulować uzyskanie bardzo pecha, zmieniłem zapytanie, aby zwrócić pierwsze 5000 wierszy do klienta. Doprowadziło to do poszukiwań indeksu 9999, więc jest to jak uzyskanie średnio 100 wierszy na odrębność ObjectId. Oto dane wyjściowe z SET STATISTICS IO, TIME ON:

Tabela „Aktualizacje”. Liczba skanów 10000, logiczne odczyty 31900, fizyczne odczyty 0

Czasy wykonania programu SQL Server: czas procesora = 31 ms, czas, który upłynął = 42 ms.

Joe Obbish
źródło
9

Podoba mi się pytanie - Flow Distinct jest jednym z moich ulubionych operatorów.

Teraz problemem jest gwarancja . Gdy pomyślisz o tym, że operator FD ciągnie rzędy od operatora Seek w uporządkowany sposób, produkując każdy wiersz, ponieważ określa go jako unikalny, da to wiersze we właściwej kolejności. Ale trudno jest ustalić, czy mogą istnieć scenariusze, w których FD nie obsługuje pojedynczego wiersza na raz.

Teoretycznie FD może zażądać 100 wierszy od Seek i produkować je w dowolnej kolejności, w jakiej ich potrzebuje.

Wskazówki dotyczące zapytania OPTION (FAST 1, MAXDOP 1)mogą pomóc, ponieważ pozwoli to uniknąć uzyskiwania większej liczby wierszy niż potrzebuje operator wyszukiwania. Czy to jednak gwarancja ? Nie do końca. Nadal może zdecydować o ciągnięciu strony wierszy na raz lub coś w tym rodzaju.

Myślę, że OPTION (FAST 1, MAXDOP 1)twoja OFFSETwersja dałaby ci dużo pewności co do zamówienia, ale nie jest to gwarancją.

Rob Farley
źródło
Jak rozumiem, problem polega na tym, że operator Flow Distinct używa tabeli mieszającej, która może się rozlać na dysk. W przypadku wycieku wiersze, które można przetworzyć przy użyciu części nadal znajdującej się w pamięci RAM, są przetwarzane natychmiast, ale pozostałe wiersze nie są przetwarzane, dopóki rozlane dane nie zostaną odczytane z dysku. Z tego, co mogę powiedzieć, żaden operator korzystający z tabeli mieszającej (takiej jak Hash Join) nie ma gwarancji zachowania porządku ze względu na zachowanie związane z rozlewaniem.
sam.bishop
Poprawny. Zobacz odpowiedź Paula White'a.
Rob Farley