Dlaczego moje zapytanie SELECT DISTINCT TOP N skanuje całą tabelę?

Natknąłem się na kilka SELECT DISTINCT TOP Nzapytań, które wydają się być słabo zoptymalizowane przez optymalizator zapytań SQL Server. Zacznijmy od trywialnego przykładu: tabela z milionami wierszy z dwiema naprzemiennymi wartościami. Użyję GetNums funkcji do generowania danych:

DROP TABLE IF EXISTS X_2_DISTINCT_VALUES;

CREATE TABLE X_2_DISTINCT_VALUES (PK INT IDENTITY (1, 1), VAL INT NOT NULL);

INSERT INTO X_2_DISTINCT_VALUES WITH (TABLOCK) (VAL)
SELECT N % 2
FROM dbo.GetNums(1000000);

UPDATE STATISTICS X_2_DISTINCT_VALUES WITH FULLSCAN;

Dla następującego zapytania:

SELECT DISTINCT TOP 2 VAL
FROM X_2_DISTINCT_VALUES
OPTION (MAXDOP 1);

SQL Server może znaleźć dwie różne wartości, skanując pierwszą stronę danych tabeli, ale zamiast tego skanuje wszystkie dane . Dlaczego SQL Server nie skanuje, dopóki nie znajdzie żądanej liczby różnych wartości?

W przypadku tego pytania użyj następujących danych testowych, które zawierają 10 milionów wierszy z 10 odrębnymi wartościami wygenerowanymi w blokach:

DROP TABLE IF EXISTS X_10_DISTINCT_HEAP;

CREATE TABLE X_10_DISTINCT_HEAP (VAL VARCHAR(10) NOT NULL);

INSERT INTO X_10_DISTINCT_HEAP WITH (TABLOCK)
SELECT REPLICATE(CHAR(65 + (N / 100000 ) % 10 ), 10)
FROM dbo.GetNums(10000000);

UPDATE STATISTICS X_10_DISTINCT_HEAP WITH FULLSCAN;

Odpowiedzi dla tabeli z indeksem klastrowym są również dopuszczalne:

DROP TABLE IF EXISTS X_10_DISTINCT_CI;

CREATE TABLE X_10_DISTINCT_CI (PK INT IDENTITY (1, 1), VAL VARCHAR(10) NOT NULL, PRIMARY KEY (PK));

INSERT INTO X_10_DISTINCT_CI WITH (TABLOCK) (VAL)
SELECT REPLICATE(CHAR(65 + (N / 100000 ) % 10 ), 10)
FROM dbo.GetNums(10000000);

UPDATE STATISTICS X_10_DISTINCT_CI WITH FULLSCAN;

Poniższe zapytanie skanuje wszystkie 10 milionów wierszy z tabeli . Jak mogę uzyskać coś, co nie skanuje całego stołu? Używam SQL Server 2016 SP1.

SELECT DISTINCT TOP 10 VAL
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1);

Istnieją trzy różne reguły optymalizatora, które mogą wykonać DISTINCToperację w powyższym zapytaniu. Poniższe zapytanie generuje błąd, który sugeruje, że lista jest wyczerpująca:

SELECT DISTINCT TOP 10 ID
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1, QUERYRULEOFF GbAggToSort, QUERYRULEOFF GbAggToHS, QUERYRULEOFF GbAggToStrm);

Msg 8622, poziom 16, stan 1, wiersz 1

Procesor zapytań nie mógł wygenerować planu zapytania ze względu na wskazówki zdefiniowane w tym zapytaniu. Ponownie wprowadź zapytanie bez podawania wskazówek i bez użycia SET FORCEPLAN.

GbAggToSortimplementuje agregację według grup (odrębne) jako odrębny sort. Jest to operator blokujący, który odczyta wszystkie dane z danych wejściowych przed wygenerowaniem jakichkolwiek wierszy. GbAggToStrmimplementuje agregację według grup jako agregację strumieniową (która również wymaga sortowania danych wejściowych w tym przypadku). Jest to również operator blokujący. GbAggToHSimplementuje jako dopasowanie skrótu, co widzieliśmy w złym planie z pytania, ale może być implementowane jako dopasowanie skrótu (agregacja) lub dopasowanie skrótu (odrębny przepływ).

Operator dopasowania mieszania ( odrębny przepływ ) jest jednym ze sposobów rozwiązania tego problemu, ponieważ nie blokuje. Program SQL Server powinien być w stanie zatrzymać skanowanie, gdy znajdzie wystarczająco wyraźne wartości.

Operator logiczny Flow Distinct skanuje dane wejściowe, usuwając duplikaty. Podczas gdy operator Distinct zużywa wszystkie dane wejściowe przed wytworzeniem danych wyjściowych, operator Flow Distinct zwraca każdy wiersz otrzymany z danych wejściowych (chyba że ten wiersz jest duplikatem, w którym to przypadku jest odrzucany).

Dlaczego zapytanie w pytaniu używa dopasowania skrótu (agregacja) zamiast dopasowania skrótu (odrębny przepływ)? Ponieważ liczba różnych wartości zmienia się w tabeli, spodziewałbym się, że koszt zapytania dopasowania mieszania (odrębnego przepływu) zmniejszy się, ponieważ szacunkowa liczba wierszy, które musi przeskanować do tabeli powinna się zmniejszyć. Spodziewałbym się, że koszt planu dopasowania (agregacji) wzrośnie, ponieważ tabela skrótów, którą musi zbudować, będzie się powiększać. Jednym ze sposobów sprawdzenia tego jest stworzenie przewodnika po planach . Jeśli utworzę dwie kopie danych, ale zastosuję przewodnik po planie do jednego z nich, powinienem być w stanie porównać dopasowanie hash (agregacja) do dopasowania hash (odrębne) obok siebie z tymi samymi danymi. Pamiętaj, że nie mogę tego zrobić, wyłączając reguły optymalizatora zapytań, ponieważ ta sama reguła dotyczy obu planów ( GbAggToHS).

Oto jeden ze sposobów uzyskania przewodnika po planie, którego szukam:

DROP TABLE IF EXISTS X_PLAN_GUIDE_TARGET;

CREATE TABLE X_PLAN_GUIDE_TARGET (VAL VARCHAR(10) NOT NULL);

INSERT INTO X_PLAN_GUIDE_TARGET WITH (TABLOCK)
SELECT CAST(N % 10000 AS VARCHAR(10))
FROM dbo.GetNums(10000000);

UPDATE STATISTICS X_PLAN_GUIDE_TARGET WITH FULLSCAN;

-- run this query
SELECT DISTINCT TOP 10 VAL  FROM X_PLAN_GUIDE_TARGET  OPTION (MAXDOP 1)

Pobierz uchwyt planu i użyj go, aby utworzyć przewodnik po planie:

-- plan handle is 0x060007009014BC025097E88F6C01000001000000000000000000000000000000000000000000000000000000
SELECT qs.plan_handle, st.text FROM 
sys.dm_exec_query_stats AS qs   
CROSS APPLY sys.dm_exec_sql_text(qs.sql_handle) AS st  
WHERE st.text LIKE '%X[_]PLAN[_]GUIDE[_]TARGET%'
ORDER BY last_execution_time DESC;

EXEC sp_create_plan_guide_from_handle 
'EVIL_PLAN_GUIDE', 
0x060007009014BC025097E88F6C01000001000000000000000000000000000000000000000000000000000000;

Przewodniki po planach działają tylko na dokładnym tekście zapytania, więc skopiujmy go z przewodnika po planach:

SELECT query_text
FROM sys.plan_guides
WHERE name = 'EVIL_PLAN_GUIDE';

Zresetuj dane:

TRUNCATE TABLE X_PLAN_GUIDE_TARGET;

INSERT INTO X_PLAN_GUIDE_TARGET WITH (TABLOCK)
SELECT REPLICATE(CHAR(65 + (N / 100000 ) % 10 ), 10)
FROM dbo.GetNums(10000000);

Uzyskaj plan zapytania dla zapytania z zastosowanym przewodnikiem planu:

SELECT DISTINCT TOP 10 VAL  FROM X_PLAN_GUIDE_TARGET  OPTION (MAXDOP 1)

Ma to operator dopasowania mieszania (odrębny przepływ), który chcieliśmy z naszymi danymi testowymi. Zauważ, że SQL Server spodziewa się odczytać wszystkie wiersze z tabeli i że szacowany koszt jest dokładnie taki sam jak w przypadku planu z dopasowaniem mieszania (agregacja). Testy, które przeprowadziłem, zasugerowały, że koszty dla dwóch planów są identyczne, gdy cel wiersza dla planu jest większy lub równy liczbie różnych wartości, których SQL Server oczekuje od tabeli, co w tym przypadku można po prostu uzyskać z Statystyka. Niestety (dla naszego zapytania) optymalizator wybiera dopasowanie mieszające (agregujące) zamiast dopasowania mieszającego (odrębne dla przepływu), gdy koszty są takie same. Jesteśmy więc 0,0000001 magicznych jednostek optymalizujących z dala od pożądanego planu.

Jednym ze sposobów na zaatakowanie tego problemu jest zmniejszenie celu rzędu. Jeśli cel wiersza z punktu widzenia optymalizatora jest mniejszy niż wyraźna liczba wierszy, prawdopodobnie uzyskamy dopasowanie mieszania (odrębny przepływ). Można to zrobić za pomocą OPTIMIZE FORwskazówki dotyczącej zapytania:

DECLARE @j INT = 10;

SELECT DISTINCT TOP (@j) VAL
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1, OPTIMIZE FOR (@j = 1));

Dla tego zapytania optymalizator tworzy plan tak, jakby zapytanie wymagało tylko pierwszego wiersza, ale po wykonaniu zapytania odzyskuje pierwsze 10 wierszy. Na moim komputerze to zapytanie skanuje 892800 wierszy zi X_10_DISTINCT_HEAPkończy się w 299 ms przy 250 ms czasu procesora i 2537 logicznych odczytach.

Zauważ, że ta technika nie będzie działać, jeśli statystyki zgłaszają tylko jedną wyraźną wartość, co może się zdarzyć w przypadku próbkowanych statystyk w odniesieniu do wypaczonych danych. Jednak w takim przypadku jest mało prawdopodobne, aby dane były wystarczająco gęsto upakowane, aby uzasadnić zastosowanie takich technik. Nie możesz wiele stracić, skanując wszystkie dane w tabeli, zwłaszcza jeśli można to zrobić równolegle.

Innym sposobem na zaatakowanie tego problemu jest zwiększenie liczby oszacowanych odrębnych wartości, które SQL Server spodziewa się uzyskać z tabeli podstawowej. To było trudniejsze niż się spodziewano. Zastosowanie funkcji deterministycznej nie może zwiększyć wyraźnej liczby wyników. Jeśli optymalizator zapytań jest świadomy tego faktu matematycznego (niektóre testy sugerują, że jest to przynajmniej do naszych celów), wówczas zastosowanie funkcji deterministycznych ( obejmujących wszystkie funkcje łańcuchowe ) nie zwiększy szacowanej liczby różnych wierszy.

Wiele niedeterministycznych funkcji też nie działało, w tym oczywiste wybory NEWID()i RAND(). Jednak LAG()sztuczka dla tego zapytania. Optymalizator zapytań oczekuje 10 milionów różnych wartości w stosunku do LAGwyrażenia, które zachęci do planu dopasowania mieszania (odrębnego przepływu) :

SELECT DISTINCT TOP 10 LAG(VAL, 0) OVER (ORDER BY (SELECT NULL)) AS ID
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1);

Na moim komputerze to zapytanie skanuje 892800 wierszy zi X_10_DISTINCT_HEAPkończy się w 1165 ms z 1109 ms czasu procesora i 2537 odczytami logicznymi, więc LAG()dodaje sporo względnego obciążenia. @Paul White zasugerował, aby spróbować przetwarzania w trybie wsadowym dla tego zapytania. Na SQL Server 2016 możemy uzyskać przetwarzanie w trybie wsadowym nawet z MAXDOP 1. Jednym ze sposobów uzyskania przetwarzania w trybie wsadowym dla tabeli magazynu wierszy jest dołączenie do pustego CCI w następujący sposób:

CREATE TABLE #X_DUMMY_CCI (ID INT NOT NULL);

CREATE CLUSTERED COLUMNSTORE INDEX X_DUMMY_CCI ON #X_DUMMY_CCI;

SELECT DISTINCT TOP 10 VAL
FROM
(
    SELECT LAG(VAL, 1) OVER (ORDER BY (SELECT NULL)) AS VAL
    FROM X_10_DISTINCT_HEAP
    LEFT OUTER JOIN #X_DUMMY_CCI ON 1 = 0
) t
WHERE t.VAL IS NOT NULL
OPTION (MAXDOP 1);

Ten kod powoduje powstanie tego planu zapytań .

Paul zwrócił uwagę, że muszę zmienić zapytanie, aby użyć, LAG(..., 1)ponieważ LAG(..., 0)nie wydaje się, że kwalifikuje się do optymalizacji agregacji okien. Ta zmiana skróciła czas, który upłynął do 520 ms, a czas procesora do 454 ms.

Zauważ, że LAG()podejście nie jest najbardziej stabilne. Jeśli Microsoft zmieni założenie o unikatowości funkcji, może ona przestać działać. Ma inny szacunek dla starszej wersji CE. Również ten rodzaj optymalizacji w stosunku do sterty nie jest konieczny, dobry pomysł. Jeśli tabela zostanie przebudowana, możliwe jest zakończenie w najgorszym przypadku, w którym prawie wszystkie wiersze muszą zostać odczytane z tabeli.

Przeciwko tabeli z unikalną kolumną (taką jak przykład indeksu klastrowego w pytaniu) mamy lepsze opcje. Na przykład możemy oszukać optymalizator, używając SUBSTRINGwyrażenia, które zawsze zwraca pusty ciąg. SQL Server nie uważa, że SUBSTRINGzmieni liczbę odrębnych wartości, więc jeśli zastosujemy ją do unikalnej kolumny, takiej jak PK, wówczas szacunkowa liczba różnych wierszy wynosi 10 milionów. Poniższe zapytanie pobiera operator dopasowania skrótu (odrębny przepływ):

SELECT DISTINCT TOP 10 VAL + SUBSTRING(CAST(PK AS VARCHAR(10)), 11, 1)
FROM X_10_DISTINCT_CI
OPTION (MAXDOP 1);

Na moim komputerze to zapytanie skanuje 900000 wierszy zi X_10_DISTINCT_CIkończy się w 333 ms przy 297 ms czasu procesora i 3011 logicznych odczytach.

Podsumowując, optymalizator zapytań wydaje się zakładać, że wszystkie wiersze będą odczytywane z tabeli dla SELECT DISTINCT TOP Nzapytań, gdy N> = liczba szacowanych odrębnych wierszy z tabeli. Operator dopasowania skrótu (agregujący) może mieć taki sam koszt jak operator dopasowania skrótu (odrębny dla przepływu), ale optymalizator zawsze wybiera operator agregacji. Może to prowadzić do niepotrzebnych odczytów logicznych, gdy w pobliżu początku skanowania tabeli znajduje się wystarczająco wyraźna wartość. Dwa sposoby na nakłonienie optymalizatora do użycia operatora dopasowania mieszania (odrębnego przepływu) to obniżenie celu wiersza za pomocą OPTIMIZE FORpodpowiedzi lub zwiększenie szacunkowej liczby różnych wierszy za pomocą LAG()lub SUBSTRINGw unikalnej kolumnie.

Odpowiedziałeś już poprawnie na swoje pytania.

Chcę tylko dodać spostrzeżenie, że najskuteczniejszym sposobem jest przeskanowanie całej tabeli - jeśli można ją zorganizować jako „stertę” magazynu kolumn :

CREATE CLUSTERED COLUMNSTORE INDEX CCSI 
ON dbo.X_10_DISTINCT_HEAP;

Proste zapytanie:

SELECT DISTINCT TOP (10)
    XDH.VAL 
FROM dbo.X_10_DISTINCT_HEAP AS XDH
OPTION (MAXDOP 1);

następnie daje:

Tabela „X_10_DISTINCT_HEAP”. Liczba skanów 1,
 odczyt logiczny 0, odczyt fizyczny 0, odczyt z wyprzedzeniem 0, 
 lob logiczne odczytuje 66 , lob fizycznie odczytuje 0, lob odczytuje z wyprzedzeniem 0.
Tabela „X_10_DISTINCT_HEAP”. Segment ma wartość 13, segment pominięty 0.

 Czasy wykonania programu SQL Server:
   Czas procesora = 0 ms, upływ czasu = 11 ms.

Hash Match (Flow Distinct) nie może obecnie być wykonywany w trybie wsadowym. Metody, które tego używają, są znacznie wolniejsze z powodu (niewidocznego) kosztownego przejścia od przetwarzania wsadowego do wierszowego. Na przykład:

SET ROWCOUNT 10;

SELECT DISTINCT 
    XDH.VAL
FROM dbo.X_10_DISTINCT_HEAP AS XDH
OPTION (FAST 1);

SET ROWCOUNT 0;

Daje:

Tabela „X_10_DISTINCT_HEAP”. Liczba skanów 1,
 odczyt logiczny 0, odczyt fizyczny 0, odczyt z wyprzedzeniem 0, 
 lob logiczne odczytuje 20 , lob fizycznie odczytuje 0, lob odczytuje z wyprzedzeniem 0.
Tabela „X_10_DISTINCT_HEAP”. Segment odczytuje 4 , segment pomija 0.

 Czasy wykonania programu SQL Server:
   Czas procesora = 640 ms, czas, który upłynął = 680 ms.

Jest to wolniejsze niż wtedy, gdy tabela jest zorganizowana jako kupa magazynu wierszy.

Oto próba emulacji powtarzanego skanowania częściowego (podobnego, ale nie takiego samego jak skanowanie pomijane) przy użyciu rekurencyjnego CTE. Celem - ponieważ nie mamy włączonego indeksu (id)- jest uniknięcie sortowania i wielokrotnego skanowania na stole.

Wykonuje kilka sztuczek, aby ominąć niektóre rekurencyjne ograniczenia CTE:

• Nie TOPwolno w rekurencyjnym części. ROW_NUMBER()Zamiast tego używamy podkwerendy .
• Nie możemy mieć wielu odniesień do części stałej ani użycia LEFT JOINlub użycia NOT IN (SELECT id FROM cte)części rekurencyjnej. Aby ominąć, tworzymy VARCHARciąg, który gromadzi wszystkie idwartości, podobne do STRING_AGGlub do hierarchyID, a następnie porównujemy z LIKE.

Dla stosu (zakładając, że kolumna ma nazwę id) test-1 na rextester.com .

To - jak wykazały testy - nie pozwala uniknąć wielokrotnego skanowania, ale wykonuje OK, gdy na kilku pierwszych stronach zostaną znalezione różne wartości. Jeśli jednak wartości nie są równomiernie rozłożone, może wykonać wiele skanów dużych części tabeli - co oczywiście skutkuje słabą wydajnością.

WITH ct (id, found, list) AS
  ( SELECT TOP (1) id, 1, CAST('/' + id + '/' AS VARCHAR(MAX))
    FROM x_large_table_2
  UNION ALL
    SELECT y.ID, ct.found + 1, CAST(ct.list + y.id + '/' AS VARCHAR(MAX))
    FROM ct
      CROSS APPLY 
      ( SELECT x.id, 
               rn = ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
        FROM x_large_table_2 AS x
        WHERE ct.list NOT LIKE '%/' + id + '/%'
      ) AS y
    WHERE ct.found < 3         -- the TOP (n) parameter here
      AND y.rn = 1
  )
SELECT id FROM ct ;

a kiedy tabela jest skupiona (CI włączony unique_key), test-2 na rextester.com .

Wykorzystuje klastrowany indeks ( WHERE x.unique_key > ct.unique_key), aby uniknąć wielokrotnego skanowania:

WITH ct (unique_key, id, found, list) AS
  ( SELECT TOP (1) unique_key, id, 1, CAST(CONCAT('/',id, '/') AS VARCHAR(MAX))
    FROM x_large_table_2
  UNION ALL
    SELECT y.unique_key, y.ID, ct.found + 1, 
        CAST(CONCAT(ct.list, y.id, '/') AS VARCHAR(MAX))
    FROM ct
      CROSS APPLY 
      ( SELECT x.unique_key, x.id, 
               rn = ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
        FROM x_large_table_2 AS x
        WHERE x.unique_key > ct.unique_key
          AND ct.list NOT LIKE '%/' + id + '/%'
      ) AS y
    WHERE ct.found < 5       -- the TOP (n) parameter here
      AND y.rn = 1
  )
-- SELECT * FROM ct ;        -- for debugging
SELECT id FROM ct ;

Dla kompletności innym sposobem podejścia do tego problemu jest użycie ZEWNĘTRZNEGO ZASTOSOWANIA . Możemy dodać OUTER APPLYoperatora dla każdej odrębnej wartości, którą musimy znaleźć. Jest to podobne podejście do rekurencyjnego podejścia ypercube, ale skutecznie rekursję wypisuje ręcznie. Jedną z zalet jest to, że jesteśmy w stanie użyć TOPtabel pochodnych zamiast ROW_NUMBER()obejścia. Dużą wadą jest to, że tekst zapytania wydłuża się wraz ze Nwzrostem.

Oto jedna implementacja zapytania dla sterty:

SELECT VAL
FROM (
    SELECT t1.VAL VAL1, t2.VAL VAL2, t3.VAL VAL3, t4.VAL VAL4, t5.VAL VAL5, t6.VAL VAL6, t7.VAL VAL7, t8.VAL VAL8, t9.VAL VAL9, t10.VAL VAL10
    FROM 
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP 
    ) t1
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t2 WHERE t2.VAL NOT IN (t1.VAL)
    ) t2
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t3 WHERE t3.VAL NOT IN (t1.VAL, t2.VAL)
    ) t3
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t4 WHERE t4.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL)
    ) t4
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t5 WHERE t5.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL)
    ) t5
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t6 WHERE t6.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL)
    ) t6
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t7 WHERE t7.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL, t6.VAL)
    ) t7
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t8 WHERE t8.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL, t6.VAL, t7.VAL)
    ) t8
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t9 WHERE t9.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL, t6.VAL, t7.VAL, t8.VAL)
    ) t9
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t10 WHERE t10.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL, t6.VAL, t7.VAL, t8.VAL, t9.VAL)
    ) t10
) t
UNPIVOT 
(
  VAL FOR VALS IN (VAL1, VAL2, VAL3, VAL4, VAL5, VAL6, VAL7, VAL8, VAL9, VAL10)
) AS upvt;

Oto aktualny plan zapytania dla powyższego zapytania. Na moim komputerze to zapytanie kończy się w 713 ms z 625 ms czasu procesora i odczytami logicznymi 12605. Otrzymujemy nową wyraźną wartość co 100 000 wierszy, więc oczekiwałbym, że to zapytanie przeskanuje około 900000 * 10 * 0,5 = 4500000 wierszy. Teoretycznie to zapytanie powinno wykonać pięciokrotność logicznych odczytów tego zapytania z drugiej odpowiedzi:

DECLARE @j INT = 10;

SELECT DISTINCT TOP (@j) VAL
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1, OPTIMIZE FOR (@j = 1));

To zapytanie wykonało 2537 logicznych odczytów. 2537 * 5 = 12685, co jest bardzo zbliżone do 12605.

W przypadku tabeli z indeksem klastrowym możemy zrobić lepiej. Jest tak, ponieważ możemy przekazać ostatnią wartość klucza klastrowanego do tabeli pochodnej, aby uniknąć skanowania tych samych wierszy dwa razy. Jedna implementacja:

SELECT VAL
FROM (
    SELECT t1.VAL VAL1, t2.VAL VAL2, t3.VAL VAL3, t4.VAL VAL4, t5.VAL VAL5, t6.VAL VAL6, t7.VAL VAL7, t8.VAL VAL8, t9.VAL VAL9, t10.VAL VAL10
    FROM 
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI 
    ) t1
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t2 WHERE PK > t1.PK AND t2.VAL NOT IN (t1.VAL)
    ) t2
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t3 WHERE PK > t2.PK AND t3.VAL NOT IN (t1.VAL, t2.VAL)
    ) t3
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t4 WHERE PK > t3.PK AND t4.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL)
    ) t4
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t5 WHERE PK > t4.PK AND t5.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL)
    ) t5
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t6 WHERE PK > t5.PK AND t6.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL)
    ) t6
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t7 WHERE PK > t6.PK AND t7.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL, t6.VAL)
    ) t7
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t8 WHERE PK > t7.PK AND t8.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL, t6.VAL, t7.VAL)
    ) t8
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t9 WHERE PK > t8.PK AND t9.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL, t6.VAL, t7.VAL, t8.VAL)
    ) t9
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t10 WHERE PK > t9.PK AND t10.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL, t6.VAL, t7.VAL, t8.VAL, t9.VAL)
    ) t10
) t
UNPIVOT 
(
  VAL FOR VALS IN (VAL1, VAL2, VAL3, VAL4, VAL5, VAL6, VAL7, VAL8, VAL9, VAL10)
) AS upvt;

Oto aktualny plan zapytania dla powyższego zapytania. Na mojej maszynie to zapytanie kończy się w 154 ms przy 140 ms czasu procesora i 3203 logicznych odczytach. Wydawało się, że działa to nieco szybciej niż OPTIMIZE FORzapytanie względem tabeli indeksów klastrowych. Nie spodziewałem się tego, więc starałem się dokładniej zmierzyć wydajność. Moja metodologia było uruchomić każdy dziesięć razy zapytań bez zestawów wyników i spojrzeć na liczby łącznie z sys.dm_exec_sessionsa sys.dm_exec_session_wait_stats. Sesja 56 była APPLYzapytaniem, a sesja 63 była OPTIMIZE FORzapytaniem.

Wyjście sys.dm_exec_sessions:

╔════════════╦══════════╦════════════════════╦═══════════════╗
║ session_id ║ cpu_time ║ total_elapsed_time ║ logical_reads ║
╠════════════╬══════════╬════════════════════╬═══════════════╣
║         56 ║     1360 ║               1373 ║         32030 ║
║         63 ║     2094 ║               2091 ║         30400 ║
╚════════════╩══════════╩════════════════════╩═══════════════╝

Wydaje się, że istnieje wyraźna przewaga w cpu_time i elapsed_time dla APPLYzapytania.

Wyjście sys.dm_exec_session_wait_stats:

╔════════════╦════════════════════════════════╦═════════════════════╦══════════════╦══════════════════╦═════════════════════╗
║ session_id ║           wait_type            ║ waiting_tasks_count ║ wait_time_ms ║ max_wait_time_ms ║ signal_wait_time_ms ║
╠════════════╬════════════════════════════════╬═════════════════════╬══════════════╬══════════════════╬═════════════════════╣
║         56 ║ SOS_SCHEDULER_YIELD            ║                 340 ║            0 ║                0 ║                   0 ║
║         56 ║ MEMORY_ALLOCATION_EXT          ║                  38 ║            0 ║                0 ║                   0 ║
║         63 ║ SOS_SCHEDULER_YIELD            ║                 518 ║            0 ║                0 ║                   0 ║
║         63 ║ MEMORY_ALLOCATION_EXT          ║                  98 ║            0 ║                0 ║                   0 ║
║         63 ║ RESERVED_MEMORY_ALLOCATION_EXT ║                 400 ║            0 ║                0 ║                   0 ║
╚════════════╩════════════════════════════════╩═════════════════════╩══════════════╩══════════════════╩═════════════════════╝

OPTIMIZE FORKwerenda ma dodatkowy typ oczekiwania, RESERVED_MEMORY_ALLOCATION_EXT . Nie wiem dokładnie, co to znaczy. Może to być po prostu pomiar narzutu w operatorze dopasowania mieszania (odmienny przepływ). W każdym razie być może nie warto martwić się różnicą czasu procesora wynoszącą 70 ms.

Myślę, że masz odpowiedź na pytanie, dlaczego
może to być sposób na rozwiązanie tego problemu.
Wiem, że wygląda to niechlujnie, ale w planie wykonania stwierdzono, że wyraźna pierwsza 2 to 84% kosztów

SELECT distinct top (2)  [enumID]
FROM [ENRONbbb].[dbo].[docSVenum1]

declare @table table (enumID tinyint);
declare @enumID tinyint;
set @enumID = (select top (1) [enumID] from [docSVenum1]);
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
select enumID from @table;