Nummerseriegenerator-udfordringsløsninger – Del 4

Her er de præstationstal, jeg fik for denne test:

Tabel 'NullBits102400'. Scanningsantal 2, logisk læser 0, fysisk læser 0, sideserver læser 0, read-ahead læser 0, sideserver read-ahead læser 0, lob logisk læser 8, lob fysisk læser 0, lob sideserver læser 0, lob læs- ahead læser 0, lob sideserver read-ahead læser 0.

Tabel 'NullBits102400'. Segment viser 2, segment sprunget over 0.

Bemærk, at køretiden faldt fra 9,813 sekunder ved brug af variabel tildelingsteknikken til 7,053 ved brug af den samlede teknik. Det er lidt over to sekunders eksekveringstid, som vi kan tilskrive variabeltildelingen her.

Og her er koden til at teste Pauls løsning:

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

Jeg får planen vist i figur 7 for denne test.

Figur 7:Plan for dbo.GetNums_SQLkiwi-funktion med aggregat

Og nu til det store øjeblik. Jeg fik følgende præstationstal for denne test:

Tabel 'CS'. Scanningsantal 2, logisk læser 0, fysisk læser 0, sideserver læser 0, read-ahead læser 0, sideserver read-ahead læser 0, lob logisk læser 44, lob fysisk læser 0, lob sideserver læser 0, lob læs- ahead læser 0, lob sideserver read-ahead læser 0.

Tabel 'CS'. Segment viser 2, segment sprunget over 0.

Køretiden faldt fra 7,822 sekunder til 3,149 sekunder! Lad os undersøge operatørens udførelsestidspunkter i den faktiske plan i SSMS, som vist i figur 8.

Figur 8:Operatørudførelsestider for dbo.GetNums-funktion med aggregat

Hvis du nu akkumulerer de enkelte operatørers eksekveringstider, vil du få et antal svarende til den samlede planudførelsestid.

Figur 9 har en præstationssammenligning med hensyn til forløbet tid mellem de tre løsninger ved brug af både variabel tildeling og aggregerede testteknikker.

Figur 9:Præstationssammenligning

Pauls løsning er en klar vinder, og det er især tydeligt, når man bruger aggregattestteknikken. Hvilken imponerende bedrift!

Dekonstruktion og rekonstruktion af Pauls løsning

At dekonstruere og derefter rekonstruere Pauls løsning er en god øvelse, og du kommer til at lære meget, mens du gør det. Som foreslået tidligere, anbefaler jeg, at du selv gennemgår processen, før du fortsætter med at læse.

Det første valg, du skal foretage, er den teknik, du vil bruge til at generere det ønskede potentielle antal rækker af 4B. Paul valgte at bruge en kolonnelagertabel og udfylde den med lige så mange rækker som kvadratroden af ​​det nødvendige antal, hvilket betyder 65.536 rækker, så du med en enkelt krydssammenføjning ville få det nødvendige antal. Måske tænker du, at med færre end 102.400 rækker ville du ikke få en komprimeret rækkegruppe, men dette gælder, når du udfylder tabellen med en INSERT-sætning, som vi gjorde med tabellen dbo.NullBits102400. Det gælder ikke, når du opretter et kolonnelagerindeks på en forududfyldt tabel. Så Paul brugte en SELECT INTO-sætning til at oprette og udfylde tabellen som en rækkelagerbaseret heap med 65.536 rækker og oprettede derefter et klynget kolonnelagerindeks, hvilket resulterede i en komprimeret rækkegruppe.

Den næste udfordring er at finde ud af, hvordan man får en krydssammenføjning til at blive behandlet med en batch-mode-operatør. Til dette skal join-algoritmen være hash. Husk, at en krydssammenføjning er optimeret ved hjælp af algoritmen for indlejrede sløjfer. Du skal på en eller anden måde narre optimeringsværktøjet til at tro, at du bruger en indre equijoin (hash kræver mindst ét ​​lighedsbaseret prædikat), men få en cross join i praksis.

Et oplagt første forsøg er at bruge en indre joinforbindelse med et kunstigt joinprædikat, der altid er sandt, som sådan:

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

Men denne kode fejler med følgende fejl:

SQL Servers optimizer genkender, at dette er et kunstigt indre join-prædikat, forenkler den indre join til en cross join og producerer en fejl, der siger, at den ikke kan imødekomme hint om at tvinge en hash join-algoritme.

For at løse dette oprettede Paul en INT NOT NULL-kolonne (mere om hvorfor denne specifikation snart) kaldet n1 i sin dbo.CS-tabel og udfyldte den med 0 i alle rækker. Han brugte derefter join-prædikatet N2.n1 =N1.n1, hvilket effektivt fik propositionen 0 =0 i alle matchevalueringer, mens han overholdt de minimale krav til en hash-join-algoritme.

Dette virker og producerer en plan for alle batchtilstande:

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

Hvad angår årsagen til, at n1 skal defineres som INT IKKE NULL; hvorfor ikke tillade NULLs, og hvorfor ikke bruge BIGINT? Årsagen til disse valg er at undgå en rest af hash-sonde (et ekstra filter, der anvendes af hash join-operatøren ud over det oprindelige join-prædikat), hvilket kan resultere i ekstra unødvendige omkostninger. Se Pauls artikel Join Performance, Implicit Conversions, and Residuals for detaljer. Her er den del af artiklen, der er relevant for os:

Bemærk, at denne optimering ikke gælder for store kolonner."

For at kontrollere dette aspekt, lad os oprette en anden tabel kaldet dbo.CS2 med en nullbar n1-kolonne:

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

Lad os først teste en forespørgsel mod dbo.CS (hvor n1 er defineret som INT IKKE NULL), generere 4B basisrækkenumre i en kolonne kaldet rn og anvende MAX-aggregatet til kolonnen:

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 vil sammenligne planen for denne forespørgsel med planen for en lignende forespørgsel mod dbo.CS2 (hvor n1 er defineret 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;

Planerne for begge forespørgsler er vist i figur 10.

Figur 10:Plansammenligning for NOT NULL vs NULL joinnøgle

Du kan tydeligt se den ekstra sonderest, der er påført i den anden plan, men ikke den første.

På min maskine blev forespørgslen mod dbo.CS afsluttet på 91 sekunder, og forespørgslen mod dbo.CS2 gennemført på 92 sekunder. I Pauls artikel rapporterer han om en forskel på 11 % til fordel for NOT NULL-tilfældet for det eksempel, han brugte.

BTW, de af jer med et skarpt øje vil have bemærket brugen af ​​ORDER BY @@TRANCOUNT som ROW_NUMBER-funktionens bestillingsspecifikation. Hvis du nøje læser Pauls inline-kommentarer i hans løsning, nævner han, at brugen af ​​funktionen @@TRANCOUNT er en parallelismehæmmer, hvorimod brugen af ​​@@SPID ikke er det. Så du kan bruge @@TRANCOUNT som køretidskonstanten i bestillingsspecifikationen, når du vil gennemtvinge en seriel plan og @@SPID, når du ikke gør det.

Som nævnt tog det forespørgslen mod dbo.CS 91 sekunder at køre på min maskine. På dette tidspunkt kunne det være interessant at teste den samme kode med en ægte krydssammenføjning og lade optimeringsværktøjet bruge en algoritme for indlejrede sløjfer i rækketilstand:

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 denne kode 104 sekunder at fuldføre på min maskine. Så vi får en betydelig præstationsforbedring med batch-mode hash join.

Vores næste problem er det faktum, at når du bruger TOP til at filtrere det ønskede antal rækker, får du en plan med en række-mode Top-operatør. Her er et forsøg på at implementere dbo.GetNums_SQLkiwi-funktionen med et 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

Lad os teste funktionen:

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

Jeg fik planen vist i figur 11 for denne test.

Figur 11:Planlæg med TOP-filter

Bemærk, at Top-operatøren er den eneste i planen, der bruger rækketilstandsbehandling.

Jeg fik følgende tidsstatistik for denne udførelse:

Den største del af kørselstiden i denne plan bruges af række-tilstand Top-operatøren og det faktum, at planen skal gennemgå batch-til-række-tilstand konvertering og tilbage.

Vores udfordring er at finde ud af et batch-mode-filtreringsalternativ til række-mode TOP. Prædikatbaserede filtre som dem, der anvendes med WHERE-sætningen, kan potentielt håndteres med batchbehandling.

Pauls tilgang var at introducere en anden INT-type kolonne (se inline-kommentaren "alt er alligevel normaliseret til 64-bit i kolonnelager/batch-tilstand" ) kaldet n2 til tabellen dbo.CS, og udfyld den med heltalssekvensen 1 til 65.536. I løsningens kode brugte han to prædikatbaserede filtre. Den ene er et groft filter i den indre forespørgsel med prædikater, der involverer kolonnen n2 fra begge sider af joinforbindelsen. Dette grove filter kan resultere i nogle falske positiver. Her er det første forsimplede forsøg på et 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 input 1 og 100.000.000 som @lav og @høj får du ingen falske positiver. Men prøv med 1 og 100.000.001, og du får nogle. Du får en sekvens på 100.020.001 numre i stedet for 100.000.001.

For at eliminere de falske positiver tilføjede Paul et andet, præcist, filter, der involverede kolonnen rn i den ydre forespørgsel. Her er det første forsimplede forsøg på et så præcist filter:

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

Lad os revidere definitionen af ​​funktionen for at bruge ovenstående prædikatbaserede filtre i stedet for TOP, tag 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

Lad os teste funktionen:

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

Jeg fik planen vist i figur 12 for denne test.

Figur 12:Planlæg med WHERE-filter, tag 1

Ak, noget gik tydeligvis galt. SQL Server konverterede vores prædikatbaserede filter, der involverede kolonnen rn, til et TOP-baseret filter og optimerede det med en Top-operator - hvilket er præcis, hvad vi forsøgte at undgå. For at føje spot til skade besluttede optimeringsværktøjet også at bruge den indlejrede loops-algoritme til sammenføjningen.

Det tog denne kode 18,8 sekunder at afslutte på min maskine. Det ser ikke godt ud.

Med hensyn til de indlejrede loops join, er dette noget, som vi nemt kunne tage os af ved at bruge et jointip i den indre forespørgsel. Bare for at se præstationspåvirkningen er her en test med et hint til tvungen hash joinforespørgsel, der bruges i selve testforespørgslen:

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

Køretiden reduceres til 13,2 sekunder.

Vi har stadig problemet med konverteringen af ​​WHERE-filteret mod rn til et TOP-filter. Lad os prøve at forstå, hvordan dette skete. Vi brugte følgende filter i den ydre forespørgsel:

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

Husk, at rn repræsenterer et umanipuleret ROW_NUMBER-baseret udtryk. Et filter baseret på, at et sådant umanipuleret udtryk er i et givent område, er ofte optimeret med en Top-operator, hvilket for os er dårlige nyheder på grund af brugen af ​​row-mode-behandling.

Pauls løsning var at bruge et tilsvarende prædikat, men et der anvender manipulation på rn, som sådan:

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

Filtrering af et udtryk, der tilføjer manipulation til et ROW_NUMBER-baseret udtryk, hæmmer konverteringen af ​​det prædikatbaserede filter til et TOP-baseret. Det er genialt!

Lad os revidere funktionens definition for at bruge ovenstående WHERE-prædikat, tag 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

Test the function again, without any special hints or anything:

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

It naturally gets an all-batch-mode plan with a hash join algorithm and no Top operator, resulting in an execution time of 3.177 seconds. Looking good.

The next step is to check if the solution handles bad inputs well. Let’s try it with a negative delta:

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

This execution fails with the following error.

Paul’s solution involved two additions. One is to add the following predicate to the inner query’s WHERE clause:

 @high >= @low

This filter does more than what it seems initially. If you’ve read Paul’s inline comments carefully, you could find this part:

The intriguing part here is the potential to use a constant scan with constants as inputs. I’ll get to this shortly.

The other addition is to apply the IIF function to the input expression to the SQRT function. This is done to avoid negative input when using nonconstants as inputs to our numbers function, and in case the optimizer decides to handle the predicate involving SQRT before the predicate @high>=@low.

Before the IIF addition, for example, the predicate involving N1.n2 looked like this:

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. Prøv 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! :)

Konklusion

I’ll have what Paul’s having.

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

No and no.