Kdy se řazení SQL Server přetočí?

Úvod

Přetočení jsou specifické pro operátory na vnitřní straně vnořených smyček, které se spojují nebo používají. Cílem je znovu použít dříve vypočítané výsledky z části prováděcího plánu tam, kde je to bezpečné.

Kanonický příklad operátora plánu, který dokáže přetáčet, je líný Table Spool . Jeho raison d’être je uložit řádky výsledků z podstromu plánu do mezipaměti a poté tyto řádky přehrát v následujících iteracích, pokud se nezmění některé parametry korelované smyčky. Přehrání řádků může být levnější než opětovné spuštění podstromu, který je vygeneroval. Další informace o těchto řadách výkonu viz můj předchozí článek.

Dokumentace říká, že pouze následující operátoři mohou přetáčet:

Spool tabulky
Řazení počtu řádků
Neclustered Index Spool
Funkce s tabulkovou hodnotou
Řadit
Vzdálený dotaz
Tvrdit a Filtrovat operátory s spouštěcím výrazem

První tři položky jsou nejčastěji výkonnostní cívky, i když mohou být zavedeny z jiných důvodů (když mohou být nedočkaví a líní).

Funkce s tabulkovou hodnotou použijte proměnnou tabulky, kterou lze za vhodných okolností použít k ukládání a přehrání výsledků. Pokud máte zájem o přetočení funkcí s tabulkovou hodnotou, podívejte se prosím na mé otázky a odpovědi na serveru Database Administrators Stack Exchange.

S těmi, kteří stojí v cestě, je tento článek výhradně o Řazení a kdy mohou přetáčet.

Řadit převinutí zpět

Třídění využívá úložiště (paměť a možná i disk, pokud se vysypou), takže mají zařízení schopné ukládání řádků mezi iteracemi smyčky. Zejména seřazený výstup lze v zásadě přehrát (přetočit).

Přesto krátká odpověď na titulní otázku „Do Sorts Rewind?“ je:

Ano, ale moc často to neuvidíte.

Typy řazení

Řazení jsou interně k dispozici v mnoha různých typech, ale pro naše současné účely existují pouze dva:

Řazení v paměti (CQScanInMemSortNew ).
- Vždy v paměti; nelze rozlít na disk.
- Používá rychlé třídění standardní knihovny.
- Maximálně 500 řádků a dvě stránky o velikosti 8 kB celkem.
- Všechny vstupy musí být běhové konstanty. Obvykle to znamená, že celý podstrom řazení musí obsahovat pouze Neustálé skenování a/nebo Vypočítat skalární operátory.
- Výslovně rozlišitelné pouze v plánech provádění při podrobném předváděcím plánu je povoleno (příznak trasování 8666). To přidá další vlastnosti do Řadit operátor, z nichž jeden je „InMemory=[0|1]“.
Všechny ostatní druhy.

(Oba typy Řazení operátora zahrnout jejich Nejvyšší řazení a Odlišné řazení varianty).

Chování zpětného přetočení

Řazení v paměti lze vždy přetočit zpět když je to bezpečné. Pokud neexistují žádné korelované parametry smyčky nebo se hodnoty parametrů oproti bezprostředně předchozí iteraci nezměnily, může tento typ řazení přehrát uložená data namísto opětovného spouštění operátorů pod nimi v prováděcím plánu.
Řazení mimo paměť může přetočit zpět když je to bezpečné, ale pouze pokud je Třídit operátor obsahuje nejvýše jeden řádek . Všimněte si prosím Řazení vstup může poskytnout jeden řádek v některých iteracích, ale ne v jiných. Chování za běhu tedy může být složitou směsí přetočení a převázání. Zcela záleží na tom, kolik řádků je poskytnuto do Řazení při každé iteraci za běhu. Obecně nelze předvídat, jaké Třídění provede při každé iteraci kontrolou prováděcího plánu.

Slovo „bezpečné“ ve výše uvedených popisech znamená:Buď nedošlo ke změně parametru, nebo žádné operátory pod Řadit mají závislost změněné hodnoty.

Důležitá poznámka o plánech provádění

Prováděcí plány ne vždy správně hlásí přetočení (a opětovné svázání) pro Řadit operátory. Operátor nahlásí přetočit zpět, pokud se některé korelované parametry nezmění, a v opačném případě znovu svázat.

U řazení mimo paměť (nejčastěji zdaleka nejběžnější) nahlášené přetočení ve skutečnosti přehraje uložené výsledky řazení pouze v případě, že je ve výstupní vyrovnávací paměti řazení nejvýše jeden řádek. V opačném případě se řazení hlásí převinout zpět, ale podstrom bude stále plně znovu spuštěn (znovu svázání).

Chcete-li zkontrolovat, kolik hlášených přetočení bylo skutečných přetočení, zkontrolujte Počet provedení vlastnost na operátory pod Řadit .

Historie a moje vysvětlení

Řadit Chování operátora přetáčení se může zdát divné, ale bylo tomu tak od (alespoň) SQL Server 2000 až po SQL Server 2019 včetně (stejně jako Azure SQL Database). Nepodařilo se mi k tomu najít žádné oficiální vysvětlení ani dokumentaci.

Můj osobní názor je, že Řadit převinutí je dost drahé kvůli základnímu třídicímu stroji, včetně zařízení na přetáčení, a použití systémových transakcí v tempdb .

Ve většině případů optimalizátor udělá lépe, když zavede explicitní spool výkonu když detekuje možnost duplicitních korelovaných parametrů smyčky. Spooly jsou nejméně nákladným způsobem ukládání dílčích výsledků do mezipaměti.

Je to možné že přehrání Řazení výsledek by byl pouze nákladově efektivnější než spool při Řadit obsahuje nejvýše jeden řádek. Koneckonců, řazení jednoho řádku (nebo žádných řádků!) ve skutečnosti nezahrnuje žádné třídění, takže se lze vyhnout velké režii.

Čistá spekulace, ale někdo se musel zeptat, tak to je.

Ukázka 1:Nepřesná přetočení

Tento první příklad obsahuje dvě proměnné tabulky. První obsahuje tři hodnoty třikrát duplikované ve sloupci c1 . Druhá tabulka obsahuje dva řádky pro každou shodu na c2 = c1 . Dva odpovídající řádky jsou odlišeny hodnotou ve sloupci c3 .

Úkolem je vrátit řádek z druhé tabulky s nejvyšším c3 hodnotu pro každou shodu na c1 = c2 . Kód je pravděpodobně jasnější než moje vysvětlení:

DECLARE @T1 table (c1 integer NOT NULL INDEX i);
DECLARE @T2 table (c2 integer NOT NULL, c3 integer NOT NULL);
 
INSERT @T1
    (c1)
VALUES
    (1), (1), (1),
    (2), (2), (2),
    (3), (3), (3);
 
INSERT @T2 
    (c2, c3)
VALUES
    (1, 1),
    (1, 2),
    (2, 3),
    (2, 4),
    (3, 5),
    (3, 6);
 
SELECT
    T1.c1,
    CA.c2,
    CA.c3
FROM @T1 AS T1
CROSS APPLY
(
    SELECT TOP (1)
        T2.c2,
        T2.c3
    FROM @T2 AS T2
    WHERE 
        T2.c2 = T1.c1
    ORDER BY 
        T2.c3 DESC
) AS CA
ORDER BY T1.c1 ASC
OPTION (NO_PERFORMANCE_SPOOL);

NO_PERFORMANCE_SPOOL rada je zde proto, aby zabránila optimalizátoru zavést zařazování výkonu. To se může stát s proměnnými tabulky, když např. je povolen příznak trasování 2453 nebo je k dispozici odložená kompilace proměnných tabulky, takže optimalizátor může vidět skutečnou mohutnost proměnné tabulky (ale ne distribuci hodnot).

Výsledky dotazu zobrazují c2 a c3 vrácené hodnoty jsou stejné pro každý odlišný c1 hodnota:

Skutečný plán provádění dotazu je:

c1 hodnoty uvedené v pořadí odpovídají předchozí iteraci 6krát a mění se 3krát. Řadit hlásí to jako 6 přetočení a 3 převázání.

Pokud by to byla pravda, Prohledání tabulky provede se pouze 3krát. Řadit přehraje (přetočí) své výsledky při dalších 6 příležitostech.

Jak to je, vidíme Skenování tabulky byl proveden 9krát, jednou pro každý řádek z tabulky @T1 . Zde nedošlo k žádnému přetočení zpět .

Ukázka 2:Řazení převinutí

Předchozí příklad neumožňoval Řadit přetočit zpět, protože (a) nejde o Řazení v paměti; a (b) v každé iteraci smyčky Sort obsahovala dvě řady. Průzkumník plánu zobrazuje celkem 18 řádků z Prohledání tabulky , dva řádky v každé z 9 iterací.

Upravme nyní příklad, aby byl pouze jeden řádek v tabulce @T2 pro každý odpovídající řádek z @T1 :

DECLARE @T1 table (c1 integer NOT NULL INDEX i);
DECLARE @T2 table (c2 integer NOT NULL, c3 integer NOT NULL);
 
INSERT @T1
    (c1)
VALUES
    (1), (1), (1),
    (2), (2), (2),
    (3), (3), (3);
 
-- Only one matching row per iteration now
INSERT @T2 
    (c2, c3)
VALUES
    --(1, 1),
    (1, 2),
    --(2, 3),
    (2, 4),
    --(3, 5),
    (3, 6);
 
SELECT
    T1.c1,
    CA.c2,
    CA.c3
FROM @T1 AS T1
CROSS APPLY
(
    SELECT TOP (1)
        T2.c2,
        T2.c3
    FROM @T2 AS T2
    WHERE 
        T2.c2 = T1.c1
    ORDER BY 
        T2.c3 DESC
) AS CA
ORDER BY T1.c1 ASC
OPTION (NO_PERFORMANCE_SPOOL);

Výsledky jsou stejné jako dříve, protože jsme ponechali odpovídající řádek seřazený nejvýše ve sloupci c3 . Prováděcí plán je také povrchně podobný, ale s důležitým rozdílem:

S jedním řádkem v Řadit kdykoli je schopen přetočit zpět, když korelovaný parametr c1 se nemění. Skenování tabulky se v důsledku toho provede pouze 3krát.

Všimněte si Řadit vytváří více řádků (9), než obdrží (3). To je dobrá známka toho, že Seřadit se podařilo uložit sadu výsledků jednou nebo vícekrát do mezipaměti – úspěšné přetočení zpět.

Ukázka 3:Nic přetáčení

Již jsem zmínil, že Řadit není v paměti lze přetočit zpět, když obsahuje nejvýše jeden řádek.

Chcete-li to vidět v akci s nulovými řádky , změníme na OUTER APPLY a do tabulky @T2 nevkládejte žádné řádky . Z důvodů, které brzy vyjdou najevo, také přestaneme promítat sloupec c2 :

DECLARE @T1 table (c1 integer NOT NULL INDEX i);
DECLARE @T2 table (c2 integer NOT NULL, c3 integer NOT NULL);
 
INSERT @T1
    (c1)
VALUES
    (1), (1), (1),
    (2), (2), (2),
    (3), (3), (3);
 
-- No rows added to table @T2
 
-- No longer projecting c2
SELECT
    T1.c1,
    --CA.c2,
    CA.c3
FROM @T1 AS T1
OUTER APPLY
(
    SELECT TOP (1)
        --T2.c2,
        T2.c3
    FROM @T2 AS T2
    WHERE 
        T2.c2 = T1.c1
    ORDER BY 
        T2.c3 DESC
) AS CA
ORDER BY T1.c1 ASC
OPTION (NO_PERFORMANCE_SPOOL);

Výsledky nyní mají NULL ve sloupci c3 podle očekávání:

Prováděcí plán je:

Řadit bylo možné přetočit zpět bez řádků ve vyrovnávací paměti, takže Skenování tabulky byl proveden pouze 3krát, pokaždé ve sloupci c1 změněná hodnota.

Ukázka 4:Maximální přetočení!

Stejně jako ostatní operátoři, kteří podporují převíjení vzad, Řadit se pouze znovu sváže jeho podstrom, pokud se korelovaný parametr změnil a podstrom na této hodnotě nějak závisí.

Obnovení sloupce c2 projekce do dema 3 to ukáže v akci:

DECLARE @T1 table (c1 integer NOT NULL INDEX i);
DECLARE @T2 table (c2 integer NOT NULL, c3 integer NOT NULL);
 
INSERT @T1
    (c1)
VALUES
    (1), (1), (1),
    (2), (2), (2),
    (3), (3), (3);
 
-- Still no rows in @T2
-- Column c2 is back!
SELECT
    T1.c1,
    CA.c2,
    CA.c3
FROM @T1 AS T1
OUTER APPLY
(
    SELECT TOP (1)
        T2.c2,
        T2.c3
    FROM @T2 AS T2
    WHERE 
        T2.c2 = T1.c1
    ORDER BY 
        T2.c3 DESC
) AS CA
ORDER BY T1.c1 ASC
OPTION (NO_PERFORMANCE_SPOOL);

Výsledky nyní ukazují dvě NULL samozřejmě sloupce:

Prováděcí plán je zcela odlišný:

Tentokrát Filtr obsahuje kontrolu T2.c2 = T1.c1 a provedete Prohledání tabulky nezávislý aktuální hodnoty korelovaného parametru c1 . Řadit lze bezpečně přetočit 8krát, což znamená, že skenování se provede pouze jednou .

Ukázka 5:Řazení v paměti

Další příklad ukazuje Řazení v paměti operátor:

DECLARE @T table (v integer NOT NULL);
 
INSERT @T 
    (v)
VALUES 
    (1), (2), (3), 
    (4), (5), (6);
 
SELECT 
    T.v,
    OA.i 
FROM @T AS T
OUTER APPLY
(
    SELECT TOP (1) 
        X.i 
    FROM 
    (
        VALUES
            (REPLICATE('Z', 1390)),
            ('0'), ('1'), ('2'), ('3'), ('4'), 
            ('5'), ('6'), ('7'), ('8'), ('9')
    ) AS X (i)
    ORDER BY NEWID()
) AS OA
OPTION (NO_PERFORMANCE_SPOOL);

Výsledky, které získáte, se budou lišit provedení od provedení, ale zde je příklad:

Zajímavostí jsou hodnoty ve sloupci i bude vždy stejný — navzdory ORDER BY NEWID() doložka.

Pravděpodobně jste již uhodli, že důvodem je Řadit výsledky ukládání do mezipaměti (převíjení zpět). Prováděcí plán zobrazuje Konstantní skenování spustí se pouze jednou a vytvoří se celkem 11 řádků:

Toto Seřadit má pouze Vypočítat skalární a Nepřetržité skenování operátory na jeho vstupu, takže jde o Řazení v paměti . Pamatujte, že tyto nejsou omezeny na maximálně jeden řádek – mohou pojmout 500 řádků a 16 kB.

Jak již bylo zmíněno dříve, není možné explicitně zjistit, zda je Třídit je V paměti nebo ne kontrolou pravidelného prováděcího plánu. Potřebujeme podrobný výstup showplanu , povoleno s nedokumentovaným příznakem trasování 8666. Když je povoleno, zobrazí se další vlastnosti operátora:

Když není praktické používat nezdokumentované příznaky trasování, můžete odvodit, že Řadit je „InMemory“ podle frakce vstupní paměti je nula a Využití paměti prvky, které nejsou dostupné v předváděcím plánu po spuštění (ve verzích SQL Server podporujících tyto informace).

Zpět k prováděcímu plánu:Neexistují žádné korelované parametry, takže Seřadit lze zdarma převinout 5krát zpět, což znamená Konstantní skenování se provádí pouze jednou. Neváhejte a změňte TOP (1) do TOP (3) nebo co se vám líbí. Převinutí znamená, že výsledky budou stejné (uložené do mezipaměti/přetočení) pro každý vstupní řádek.

Možná vás obtěžuje ORDER BY NEWID() doložka nebránící přetočení. To je skutečně kontroverzní bod, ale vůbec se neomezuje na druhy. Pro podrobnější diskusi (varování:možná králičí nora) se prosím podívejte na tyto otázky a odpovědi. Zkrácená verze je taková, že se jedná o záměrné rozhodnutí o návrhu produktu, optimalizaci výkonu, ale existují plány, jak toto chování časem učinit intuitivnějším.

Ukázka 6:Žádné řazení v paměti

To je stejné jako demo 5, s výjimkou toho, že replikovaný řetězec je o jeden znak delší:

DECLARE @T table (v integer NOT NULL);
 
INSERT @T 
    (v)
VALUES 
    (1), (2), (3), 
    (4), (5), (6);
 
SELECT 
    T.v,
    OA.i 
FROM @T AS T
OUTER APPLY
(
    SELECT TOP (1) 
        X.i 
    FROM 
    (
        VALUES
            -- 1391 instead of 1390
            (REPLICATE('Z', 1391)),
            ('0'), ('1'), ('2'), ('3'), ('4'), 
            ('5'), ('6'), ('7'), ('8'), ('9')
    ) AS X (i)
    ORDER BY NEWID()
) AS OA
OPTION (NO_PERFORMANCE_SPOOL);

Výsledky se budou opět lišit podle provedení, ale zde je příklad. Všimněte si i hodnoty nyní nejsou všechny stejné:

Znak navíc stačí k posunutí odhadované velikosti setříděných dat přes 16 kB. To znamená Řazení v paměti nelze použít a přetočení zmizí.

Prováděcí plán je:

Řadit stále hlásí 5 přetočí zpět, ale Konstantní skenování se provede 6krát, což znamená, že ve skutečnosti nedošlo k žádnému přetočení. Vytváří všech 11 řádků v každém ze 6 provedení, což dává celkem 66 řádků.

Souhrn a závěrečné myšlenky

Neuvidíte Řazení operátor skutečně přetáčení velmi často, i když to uvidíte říká, že ano docela hodně.

Nezapomeňte, běžné Třídění lze převinout pouze v případě, že je to bezpečné a v daném okamžiku je v řazení maximálně jeden řádek. Být „bezpečný“ znamená buď žádnou změnu v parametrech korelace smyčky, nebo nic pod Řadit je ovlivněna změnami parametrů.

Řazení v paměti může pracovat až s 500 řádky a 16 kB dat pocházejících z Constant Scan a Vypočítat skalární pouze operátory. Přetočí se také, jen když je to bezpečné (chyby produktu stranou!), ale není omezeno na maximálně jeden řádek.

Mohou to vypadat jako esoterické detaily a já předpokládám, že jsou. Pomohli mi tedy porozumět realizačnímu plánu a najít dobrá zlepšení výkonu více než jednou. Možná vám tyto informace jednoho dne budou také užitečné.

Podívejte se na Třídění které produkují více řádků, než mají na svém vstupu!

Pokud byste chtěli vidět realističtější příklad Řadit přetočení na základě dema Itzika Ben-Gana poskytnutého v první části jeho Nejbližšího zápasu série viz Nejbližší shoda s řazením zpět.