Utmaningslösningar för nummerseriegenerator – del 4

Här är prestationssiffrorna som jag fick för det här testet:

Tabell 'NullBits102400'. Skanningsantal 2, logiskt läser 0, fysiskt läser 0, sidserver läser 0, read-ahead läser 0, sidserver läser framåt läser 0, lob logiskt läser 8, lob fysisk läser 0, lob sidserver läser 0, lob läs- ahead läser 0, lob page server read-ahead läser 0.

Tabell 'NullBits102400'. Segment visar 2, segment hoppade över 0.

Observera att körtiden sjönk från 9,813 sekunder med variabeltilldelningstekniken till 7,053 med den aggregerade tekniken. Det är lite över två sekunders exekveringstid som vi kan tillskriva variabeltilldelningen här.

Och här är koden för att testa Pauls lösning:

SELECT MAX(n) AS mx FROM dbo.GetNums_SQLkiwi(1, 100000000) OPTION(MAXDOP 1);

Jag får planen som visas i figur 7 för detta test.

Figur 7:Plan för dbo.GetNums_SQLkiwi-funktion med aggregat

Och nu till det stora ögonblicket. Jag fick följande prestationssiffror för det här testet:

Tabell 'CS'. Scan count 2, logiskt läser 0, fysiskt läser 0, sidserver läser 0, läs framåt läser 0, sidserver läser framåt läser 0, lob logiskt läser 44, lob fysisk läser 0, lob sidserver läser 0, lob läs- ahead läser 0, lob page server read-ahead läser 0.

Tabell 'CS'. Segment visar 2, segment hoppade över 0.

Körtiden sjönk från 7,822 sekunder till 3,149 sekunder! Låt oss undersöka operatörens utförandetider i den faktiska planen i SSMS, som visas i figur 8.

Figur 8:Operatörskörningstider för dbo.GetNums-funktionen med aggregat

Om du nu ackumulerar genomförandetiderna för de enskilda operatörerna kommer du att få ett liknande antal som den totala planens genomförandetid.

Figur 9 har en prestandajämförelse i termer av förfluten tid mellan de tre lösningarna med användning av både variabel tilldelning och aggregerad testteknik.

Figur 9:Prestandajämförelse

Pauls lösning är en klar vinnare, och detta är särskilt uppenbart när man använder aggregattestningstekniken. Vilken imponerande bedrift!

Dekonstruerar och rekonstruerar Pauls lösning

Att dekonstruera och sedan rekonstruera Pauls lösning är en fantastisk övning, och du får lära dig mycket medan du gör det. Som föreslagits tidigare rekommenderar jag att du går igenom processen själv innan du fortsätter läsa.

Det första valet du behöver göra är den teknik som du skulle använda för att generera det önskade potentiella antalet rader av 4B. Paul valde att använda en kolumnlagertabell och fylla den med så många rader som kvadratroten av det erforderliga numret, vilket betyder 65 536 rader, så att du med en enda korskoppling skulle få det antal som krävs. Du kanske tänker att med färre än 102 400 rader skulle du inte få en komprimerad radgrupp, men detta gäller när du fyller i tabellen med en INSERT-sats som vi gjorde med tabellen dbo.NullBits102400. Det gäller inte när du skapar ett kolumnlagerindex på en förifylld tabell. Så Paul använde en SELECT INTO-sats för att skapa och fylla i tabellen som en radlagringsbaserad hög med 65 536 rader och skapade sedan ett klustrat kolumnlagerindex, vilket resulterade i en komprimerad radgrupp.

Nästa utmaning är att ta reda på hur man får en korskoppling att bearbetas med en batchlägesoperatör. För detta behöver du att join-algoritmen är hash. Kom ihåg att en korskoppling är optimerad med algoritmen för kapslade loopar. Du måste på något sätt lura optimeraren att tro att du använder en inre equijoin (hash kräver minst ett likhetsbaserat predikat), men få en cross join i praktiken.

Ett uppenbart första försök är att använda en inre sammanfogning med ett artificiellt sammanfogningspredikat som alltid är sant, som så:

SELECT *
FROM dbo.CS AS N1
  INNER HASH JOIN dbo.CS AS N2
    ON 0 = 0;

Men den här koden misslyckas med följande fel:

SQL Servers optimerare känner igen att detta är ett artificiellt inre kopplingspredikat, förenklar den inre kopplingen till en korskoppling och ger ett felmeddelande som säger att den inte kan hantera tipset att tvinga fram en hashkopplingsalgoritm.

För att lösa detta skapade Paul en INT NOT NULL-kolumn (mer om varför denna specifikation inom kort) kallad n1 i sin dbo.CS-tabell och fyllde den med 0 i alla rader. Han använde sedan join-predikatet N2.n1 =N1.n1, och fick i praktiken propositionen 0 =0 i alla matchningsutvärderingar, samtidigt som han uppfyllde minimikraven för en hash join-algoritm.

Detta fungerar och producerar en plan för all-batch-läge:

SELECT *
FROM dbo.CS AS N1
  INNER HASH JOIN dbo.CS AS N2
    ON N2.n1 = N1.n1;

Angående anledningen till att n1 definieras som INT NOT NULL; varför förbjuda NULLs och varför inte använda BIGINT? Anledningen till dessa val är att undvika en rest av hash-sond (ett extra filter som appliceras av hash-join-operatören utöver det ursprungliga join-predikatet), vilket kan resultera i extra onödiga kostnader. Se Pauls artikel Gå med i prestanda, implicita omvandlingar och rester för detaljer. Här är den del av artikeln som är relevant för oss:

Observera att denna optimering inte gäller för stora kolumner."

För att kontrollera denna aspekt, låt oss skapa en annan tabell som heter dbo.CS2 med en nollbar n1-kolumn:

DROP TABLE IF EXISTS dbo.CS2;
 
SELECT * INTO dbo.CS2 FROM dbo.CS;
 
ALTER TABLE dbo.CS2 ALTER COLUMN n1 INT NULL;
 
CREATE CLUSTERED COLUMNSTORE INDEX CCI 
ON dbo.CS2
WITH (MAXDOP = 1);

Låt oss först testa en fråga mot dbo.CS (där n1 definieras som INT NOT NULL), generera 4B basradnummer i en kolumn som kallas rn och tillämpa MAX-aggregatet på kolumnen:

SELECT
    mx = MAX(N.rn)
FROM
(
    SELECT 
        rn = ROW_NUMBER() OVER (ORDER BY @@TRANCOUNT ASC)
    FROM dbo.CS AS N1
    JOIN dbo.CS AS N2
        ON N2.n1 = N1.n1
) AS N;

Vi kommer att jämföra planen för den här frågan med planen för en liknande fråga mot dbo.CS2 (där n1 är definierad som INT NULL):

SELECT
    mx = MAX(N.rn)
FROM
(
    SELECT 
        rn = ROW_NUMBER() OVER (ORDER BY @@TRANCOUNT ASC)
    FROM dbo.CS2 AS N1
    JOIN dbo.CS2 AS N2
        ON N2.n1 = N1.n1
) AS N;

Planerna för båda frågorna visas i figur 10.

Figur 10:Planjämförelse för NOT NULL vs NULL join-nyckel

Du kan tydligt se den extra sondresten som appliceras i den andra planen men inte den första.

På min maskin slutfördes frågan mot dbo.CS på 91 sekunder, och frågan mot dbo.CS2 klar på 92 sekunder. I Pauls artikel rapporterar han en skillnad på 11 % till förmån för NOT NULL-fallet för exemplet han använde.

BTW, de av er med ett skarpt öga kommer att ha lagt märke till användningen av ORDER BY @@TRANCOUNT som ROW_NUMBER-funktionens beställningsspecifikation. Om du noggrant läser Pauls inline-kommentarer i hans lösning, nämner han att användningen av funktionen @@TRANCOUNT är en parallellismhämmare, medan användningen av @@SPID inte är det. Så du kan använda @@TRANCOUNT som körtidskonstant i beställningsspecifikationen när du vill tvinga fram en serieplan och @@SPID när du inte gör det.

Som nämnt tog det frågan mot dbo.CS 91 sekunder att köra på min maskin. Vid det här laget kan det vara intressant att testa samma kod med en äkta korskoppling, så att optimeraren kan använda en algoritm för kapslade loopar i radläge:

SELECT
    mx = MAX(N.rn)
FROM
(
    SELECT 
        rn = ROW_NUMBER() OVER (ORDER BY @@TRANCOUNT ASC)
    FROM dbo.CS AS N1
    CROSS JOIN dbo.CS AS N2
) AS N;

Det tog den här koden 104 sekunder att slutföra på min maskin. Så vi får en avsevärd prestandaförbättring med batch-mode hash join.

Vårt nästa problem är det faktum att när du använder TOP för att filtrera önskat antal rader, får du en plan med en row-mode Top-operatör. Här är ett försök att implementera funktionen dbo.GetNums_SQLkiwi med ett TOP-filter:

CREATE OR ALTER FUNCTION dbo.GetNums_SQLkiwi
(
    @low bigint = 1,
    @high bigint
)
RETURNS table 
AS
RETURN
    SELECT
        N.rn,
        n = @low - 1 + N.rn,
        op = @high + 1 - N.rn
    FROM
    (
        SELECT TOP (100000000 - 1 + 1)
            rn = ROW_NUMBER() OVER (ORDER BY @@SPID ASC)
        FROM dbo.CS AS N1
        JOIN dbo.CS AS N2
            ON N2.n1 = N1.n1
        ORDER BY rn
    ) AS N;
GO

Låt oss testa funktionen:

SELECT MAX(n) FROM dbo.GetNums_SQLkiwi(1, 100000000);

Jag fick planen som visas i figur 11 för detta test.

Figur 11:Planera med TOP-filter

Observera att Top-operatören är den enda i planen som använder radlägesbearbetning.

Jag fick följande tidsstatistik för denna körning:

Den största delen av körtiden i denna plan spenderas av row-mode Top-operatören och det faktum att planen måste gå igenom batch-to-row-mode-konvertering och tillbaka.

Vår utmaning är att hitta ett batch-mode-filtreringsalternativ till rad-mode TOP. Predikatbaserade filter som de som tillämpas med WHERE-satsen kan potentiellt hanteras med batchbearbetning.

Pauls tillvägagångssätt var att introducera en andra INT-typad kolumn (se inline-kommentaren "allt är ändå normaliserat till 64-bitar i kolumnlagrings-/batchläge" ) anropade n2 till tabellen dbo.CS och fyll i den med heltalssekvensen 1 till 65 536. I lösningens kod använde han två predikatbaserade filter. Det ena är ett grovt filter i den inre frågan med predikat som involverar kolumnen n2 från båda sidor av kopplingen. Detta grovfilter kan resultera i vissa falska positiva resultat. Här är det första förenklade försöket med ett sådant filter:

WHERE
    -- Coarse filter:
    N1.n2 <= CONVERT(integer, CEILING(SQRT(CONVERT(float, @high - @low + 1))))
    AND N2.n2 <= CONVERT(integer, CEILING(SQRT(CONVERT(float, @high - @low + 1))))

Med ingångarna 1 och 100 000 000 som @låg och @hög får du inga falska positiva resultat. Men försök med 1 och 100 000 001, så får du några. Du får en sekvens med 100 020 001 nummer istället för 100 000 001.

För att eliminera de falska positiva, lade Paul till ett andra, exakt, filter som involverade kolumnen rn i den yttre frågan. Här är det första förenklade försöket med ett så exakt filter:

WHERE
    -- Precise filter:
    N.rn < @high - @low + 2

Låt oss revidera definitionen av funktionen för att använda ovanstående predikatbaserade filter istället för TOP, ta 1:

CREATE OR ALTER FUNCTION dbo.GetNums_SQLkiwi
(
    @low bigint = 1,
    @high bigint
)
RETURNS table 
AS
RETURN
    SELECT
        N.rn,
        n = @low - 1 + N.rn,
        op = @high + 1 - N.rn
    FROM
    (
        SELECT
            rn = ROW_NUMBER() OVER (ORDER BY @@TRANCOUNT ASC)
        FROM dbo.CS AS N1
        JOIN dbo.CS AS N2
            ON N2.n1 = N1.n1
        WHERE
            -- Coarse filter:
            N1.n2 <= CONVERT(integer, CEILING(SQRT(CONVERT(float, @high - @low + 1))))
            AND N2.n2 <= CONVERT(integer, CEILING(SQRT(CONVERT(float, @high - @low + 1))))
    ) AS N
    WHERE
        -- Precise filter:
        N.rn < @high - @low + 2;
GO

Låt oss testa funktionen:

SELECT MAX(n) FROM dbo.GetNums_SQLkiwi(1, 100000000);

Jag fick planen som visas i figur 12 för detta test.

Figur 12:Planera med WHERE-filter, ta 1

Tyvärr gick något helt klart fel. SQL Server konverterade vårt predikatbaserade filter som involverade kolumnen rn till ett TOP-baserat filter och optimerade det med en Top-operator – vilket är precis vad vi försökte undvika. För att lägga förolämpning till skada bestämde optimeraren också att använda algoritmen för kapslade loopar för sammanfogningen.

Det tog den här koden 18,8 sekunder att slutföra på min maskin. Ser inte bra ut.

Angående de kapslade loops join, detta är något som vi enkelt skulle kunna ta hand om med hjälp av en join-tips i den inre frågan. Bara för att se prestandapåverkan, här är ett test med en påtvingad hash-anslutningsfrågetips som används i själva testfrågan:

SELECT MAX(n) FROM dbo.GetNums_SQLkiwi(1, 100000000) OPTION(HASH JOIN);

Körtiden minskar till 13,2 sekunder.

Vi har fortfarande problemet med konverteringen av WHERE-filtret mot rn till ett TOP-filter. Låt oss försöka förstå hur detta hände. Vi använde följande filter i den yttre frågan:

WHERE N.rn < @high - @low + 2

Kom ihåg att rn representerar ett omanipulerat ROW_NUMBER-baserat uttryck. Ett filter baserat på att ett sådant omanipulerat uttryck ligger i ett givet intervall optimeras ofta med en Top-operator, vilket för oss är dåliga nyheter på grund av användningen av radlägesbehandling.

Pauls lösning var att använda ett likvärdigt predikat, men ett som tillämpar manipulation på rn, som så:

WHERE @low - 2 + N.rn < @high

Filtrering av ett uttryck som lägger till manipulation till ett ROW_NUMBER-baserat uttryck hämmar konverteringen av det predikatbaserade filtret till ett TOP-baserat. Det är lysande!

Låt oss revidera funktionens definition för att använda ovanstående WHERE-predikat, ta 2:

CREATE OR ALTER FUNCTION dbo.GetNums_SQLkiwi
(
    @low bigint = 1,
    @high bigint
)
RETURNS table 
AS
RETURN
    SELECT
        N.rn,
        n = @low - 1 + N.rn,
        op = @high + 1 - N.rn
    FROM
    (
        SELECT
            rn = ROW_NUMBER() OVER (ORDER BY @@TRANCOUNT ASC)
        FROM dbo.CS AS N1
        JOIN dbo.CS AS N2
            ON N2.n1 = N1.n1
        WHERE
            -- Coarse filter:
            N1.n2 <= CONVERT(integer, CEILING(SQRT(CONVERT(float, @high - @low + 1))))
            AND N2.n2 <= CONVERT(integer, CEILING(SQRT(CONVERT(float, @high - @low + 1))))
    ) AS N
    WHERE
        -- Precise filter:
        @low - 2 + N.rn < @high;
GO

Testa funktionen igen, utan några speciella tips eller något:

SELECT MAX(n) FROM dbo.GetNums_SQLkiwi(1, 100000000);

Den får naturligtvis en hel-batch-mode-plan med en hash join-algoritm och ingen toppoperatör, vilket resulterar i en exekveringstid på 3,177 sekunder. Ser bra ut.

Nästa steg är att kontrollera om lösningen hanterar dåliga ingångar bra. Låt oss prova det med ett negativt delta:

SELECT MAX(n) FROM dbo.GetNums_SQLkiwi(100000000, 1);

Denna exekvering misslyckas med följande fel.

Pauls lösning innebar två tillägg. En är att lägga till följande predikat till den inre frågans WHERE-sats:

 @high >= @low

Detta filter gör mer än vad det verkar från början. Om du har läst Pauls inline-kommentarer noggrant kan du hitta den här delen:

Den spännande delen här är möjligheten att använda en konstant skanning med konstanter som indata. Jag kommer till det här snart.

Det andra tillägget är att tillämpa IIF-funktionen på inmatningsuttrycket på SQRT-funktionen. Detta görs för att undvika negativ inmatning när man använder icke-konstanter som indata till vår sifferfunktion, och om optimeraren bestämmer sig för att hantera predikatet som involverar SQRT före predikatet @high>=@low.

Innan IIF-tillägget, till exempel, såg predikatet som involverade N1.n2 ut så här:

N1.n2 <= CONVERT(integer, CEILING(SQRT(CONVERT(float, @high - @low + 1))))

After adding IIF, it looks like this:

N1.n2 <= CONVERT(integer, CEILING(SQRT(CONVERT(float, IIF(@high >= @low, @high - @low + 1, 0)))))

With these two additions, we’re now basically ready for the final definition of the dbo.GetNums_SQLkiwi function:

CREATE OR ALTER FUNCTION dbo.GetNums_SQLkiwi
(
    @low bigint = 1,
    @high bigint
)
RETURNS table 
AS
RETURN
    SELECT
        N.rn,
        n = @low - 1 + N.rn,
        op = @high + 1 - N.rn
    FROM
    (
        SELECT 
            -- Use @@TRANCOUNT instead of @@SPID if you like all your queries serial
            rn = ROW_NUMBER() OVER (ORDER BY @@SPID ASC)
        FROM dbo.CS AS N1
        JOIN dbo.CS AS N2
            -- Batch mode hash cross join
            -- Integer not null data type avoid hash probe residual
            -- This is always 0 = 0
            ON N2.n1 = N1.n1
        WHERE
            -- Try to avoid SQRT on negative numbers and enable simplification 
            -- to single constant scan if @low > @high (with literals)
            -- No start-up filters in batch mode
            @high >= @low
            -- Coarse filter:
            -- Limit each side of the cross join to SQRT(target number of rows)
            -- IIF avoids SQRT on negative numbers with parameters
            AND N1.n2 <= CONVERT(integer, CEILING(SQRT(CONVERT(float, IIF(@high >= @low, @high - @low + 1, 0)))))
            AND N2.n2 <= CONVERT(integer, CEILING(SQRT(CONVERT(float, IIF(@high >= @low, @high - @low + 1, 0)))))
    ) AS N
    WHERE
        -- Precise filter:
        -- Batch mode filter the limited cross join to the exact number of rows needed
        -- Avoids the optimizer introducing a row-mode Top with following row mode compute scalar
        @low - 2 + N.rn < @high;
GO

Now back to the comment about the constant scan. When using constants that result in a negative range as inputs to the function, e.g., 100,000,000 and 1 as @low and @high, after parameter embedding the WHERE filter of the inner query looks like this:

WHERE
    1 >= 100000000
    AND ...

The whole plan can then be simplified to a single Constant Scan operator. Prova det:

SELECT MAX(n) FROM dbo.GetNums_SQLkiwi(100000000, 1);

The plan for this execution is shown in Figure 13.

Figure 13:Plan with constant scan

Unsurprisingly, I got the following performance numbers for this execution:

logical reads 0

When passing a negative range with nonconstants as inputs, the use of the IIF function will prevent any attempt to compute a square root of a negative input.

Now let’s test the function with a valid input range:

SELECT MAX(n) FROM dbo.GetNums_SQLkiwi(1, 100000000);

You get the all-batch-mode plan shown in Figure 14.

Figure 14:Plan for dbo.GetNums_SQLkiwi function

This is the same plan you saw earlier in Figure 7.

I got the following time statistics for this execution:

Ladies and gentlemen, I think we have a winner! :)

Slutsats

I’ll have what Paul’s having.

Are we done yet, or is this series going to last forever?

No and no.