Karen Ly, en Jr. Fixed Income Analyst hos RBC, gav mig en T-SQL-udfordring, der involverer at finde det tætteste match, i modsætning til at finde et nøjagtigt match. I denne artikel dækker jeg en generaliseret, forenklet form af udfordringen.
Udfordringen
Udfordringen involverer matchende rækker fra to tabeller, T1 og T2. Brug følgende kode til at oprette en eksempeldatabase kaldet testdb, og i den tabellerne T1 og T2:
INDSTIL ANTAL TIL; HVIS DB_ID('testdb') ER NULL OPRET DATABASE testdb; GÅ BRUG testdb; DROP TABEL HVIS FINDER dbo.T1, dbo.T2; OPRET TABEL dbo.T1 ( keycol INT IKKE NULL IDENTITETSBEGRÆNSNING PK_T1 PRIMÆR NØGLE, val INT IKKE NULL, othercols BINARY(100) IKKE NULL BEGRÆNSNING DFT_T1_col1 DEFAULT(0xAA) ); OPRET TABEL dbo.T2 ( keycol INT IKKE NULL IDENTITETSBEGRÆNSNING PK_T2 PRIMÆR NØGLE, val INT IKKE NULL, othercols BINARY(100) IKKE NULL BEGRÆNSNING DFT_T2_col1 DEFAULT(0xBB) ); Som du kan se, har både T1 og T2 en numerisk kolonne (INT-type i dette eksempel) kaldet val. Udfordringen er at matche til hver række fra T1 rækken fra T2, hvor den absolutte forskel mellem T2.val og T1.val er den laveste. I tilfælde af uafgjort (flere matchende rækker i T2), match den øverste række baseret på val opadgående, keycol stigende rækkefølge. Det vil sige rækken med den laveste værdi i valkolonnen, og hvis du stadig har uafgjort, rækken med den laveste keycol-værdi. Tiebreaken bruges til at garantere determinisme.
Brug følgende kode til at udfylde T1 og T2 med små sæt eksempeldata for at kunne kontrollere rigtigheden af dine løsninger:
TRUNCATE TABLE dbo.T1; TRUNCATE TABEL dbo.T2; INSERT INTO dbo.T1 (val) VALUES(1),(1),(3),(3),(5),(8),(13),(16),(18),(20),( 21); INSERT INTO dbo.T2 (val) VALUES(2),(2),(7),(3),(3),(11),(11),(13),(17),(19);
Tjek indholdet af T1:
SELECT keycol, val, SUBSTRING(othercols, 1, 1) AS othercols FRA dbo.T1 BESTIL EFTER val, keycol;
Denne kode genererer følgende output:
keycol val othercols ----------- ----------- ---------- 1 1 0xAA 2 1 0xAA 3 3 0xAA 4 3 0xAA 5 5 0xAA 6 8 0xAA 7 13 0xAA 8 16 0xAA 9 18 0xAA 10 20 0xAA 11 21 0xAA
Tjek indholdet af T2:
SELECT keycol, val, SUBSTRING(othercols, 1, 1) AS othercols FRA dbo.T2 BESTIL EFTER val, keycol;
Denne kode genererer følgende output:
keycol val othercols ----------- ----------- ---------- 1 2 0xBB 2 2 0xBB 4 3 0xBB 5 3 0xBB 3 7 0xBB 6 11 0xBB 7 11 0xBB 8 13 0xBB 9 17 0xBB 10 19 0xBB
Her er det ønskede resultat for de givne eksempeldata:
keycol1 val1 othercols1 keycol2 val2 othercols2 ----------- ---------- ---------- ---------- ------------ ---------- 1 1 0xAA 1 2 0xBB 2 1 0xAA 1 2 0xBB 3 3 0xAA 4 3 0xBB 4 3 0xAA 4 3 0xBB 5 5 0xAA 4 3 0xBB 6 8 0xAA 3 7 0xBB 7 13 0xAA 8 13 0xBB 8 16 0xAA 9 17 0xBB 9 18 0xAA 9 17 0xBB 10 20 0xAA 10 19 01 0x 10 19 01 0BBInden du begynder at arbejde med udfordringen, skal du undersøge det ønskede resultat og sikre dig, at du forstår matchningslogikken, inklusive den uafgjorte logik. Overvej f.eks. rækken i T1, hvor keycol er 5 og val er 5. Denne række har flere tætteste match i T2:
keycol val othercols ------------------ ----------- ---------- 4 3 0xBB 5 3 0xBB 3 7 0xBBI alle disse rækker er den absolutte forskel mellem T2.val og T1.val (5) 2. Ved at bruge tiebreaking-logikken baseret på rækkefølgen val ascending, er keycol, der stiger i den øverste række her, den, hvor val er 3 og keycol er 4.
Du vil bruge de små sæt af eksempeldata til at kontrollere gyldigheden af dine løsninger. For at kontrollere ydeevnen har du brug for større sæt. Brug følgende kode til at oprette en hjælpefunktion kaldet GetNums, som genererer en sekvens af heltal i et anmodet område:
DROP-FUNKTION HVIS FINDER dbo.GetNums; GÅ OPRET ELLER ÆNDRING AF FUNKTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNERER TABEL SOM RETURNERING MED L0 AS (VÆLG c FRA (VÆLG 1 UNION ALLE VÆLG 1) SOM D(c)), L1 AS (VÆLG 1 SOM c FRA L0 SOM EN KRYDSJOIN L0 AS B), L2 AS (VÆLG 1 SOM c FRA L1 SOM EN KRYDSJOIN L1 SOM B), L3 AS (VÆLG 1 AS c FRA L2 SOM KRYDSFIND L2 SOM B), L4 AS (VÆLG 1 AS c FRA L3 SOM A CROSS JOIN L3 AS B), L5 AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B), Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL) ) SOM rækkenummer FRA L5) VÆLG TOP(@høj - @lav + 1) @lav + rækkenummer - 1 SOM n FRA numre BESTIL EFTER rækkenummer; GOBrug følgende kode til at udfylde T1 og T2 med store sæt eksempeldata:
DEKLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =10000000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =10000000; TRUNCATE TABEL dbo.T1; TRUNCATE TABEL dbo.T2; INSERT INTO dbo.T1 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT1 + 1 AS val FROM dbo.GetNums(1, @numrowsT1) AS Nums; INSERT INTO dbo.T2 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT2 + 1 AS val FROM dbo.GetNums(1, @numrowsT2) AS Nums;Variablerne @numrowsT1 og @numrowsT2 styrer antallet af rækker, du ønsker, at tabellerne skal udfyldes med. Variablerne @maxvalT1 og @maxvalT2 styrer rækken af distinkte værdier i valkolonnen og påvirker derfor tætheden af kolonnen. Ovenstående kode fylder tabellerne med 1.000.000 rækker hver og bruger intervallet 1 – 10.000.000 for valkolonnen i begge tabeller. Dette resulterer i lav tæthed i kolonnen (stort antal forskellige værdier, med et lille antal dubletter). Brug af lavere maksimumværdier vil resultere i højere tæthed (mindre antal forskellige værdier og dermed flere dubletter).
Løsning 1 med én TOP-underforespørgsel
Den enkleste og mest oplagte løsning er nok en, der forespørger T1, og ved at bruge CROSS APPLY-operatoren anvender en forespørgsel med et TOP (1)-filter, og rækkerne sorteres efter den absolutte forskel mellem T1.val og T2.val ved hjælp af T2.val , T2.keycol som tiebreaker. Her er løsningens kode:
SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1) ) AS othercols2 FRA dbo.T1 CROSS APPLY (VÆLG TOP (1) T2.* FRA dbo.T2 BESTILLING AF ABS(T2.val - T1.val), T2.val, T2.keycol ) SOM A;Husk, at der er 1.000.000 rækker i hver af tabellerne. Og tætheden af valkolonnen er lav i begge tabeller. Desværre, da der ikke er noget filtreringsprædikat i den anvendte forespørgsel, og rækkefølgen involverer et udtryk, der manipulerer kolonner, er der ikke noget potentiale her for at skabe understøttende indekser. Denne forespørgsel genererer planen i figur 1.
Figur 1:Plan for løsning 1
Sløjfens ydre input scanner 1.000.000 rækker fra T1. Det indre input af sløjfen udfører en fuld scanning af T2 og en TopN-sortering for hver særskilte T1.val-værdi. I vores plan sker dette 998.657 gange, da vi har meget lav tæthed. Den placerer rækkerne i en indeksspool, tastet af T1.val, så den kan genbruge dem til duplikerede forekomster af T1.val-værdier, men vi har meget få dubletter. Denne plan har kvadratisk kompleksitet. Mellem alle forventede henrettelser af den indre gren af løkken forventes den at behandle tæt på en billion rækker. Når du taler om et stort antal rækker, som en forespørgsel skal behandle, når du begynder at nævne milliarder af rækker, ved folk allerede, at du har at gøre med en dyr forespørgsel. Normalt udtaler folk ikke udtryk som billioner, medmindre de diskuterer den amerikanske statsgæld eller børskrak. Du beskæftiger dig normalt ikke med sådanne tal i forbindelse med forespørgselsbehandling. Men planer med kvadratisk kompleksitet kan hurtigt ende med sådanne tal. At køre forespørgslen i SSMS med Inkluder Live Query Statistics aktiveret tog 39,6 sekunder at behandle kun 100 rækker fra T1 på min bærbare computer. Det betyder, at det bør tage denne forespørgsel omkring 4,5 dage at fuldføre. Spørgsmålet er, om du virkelig er til binge-watching live-forespørgselsplaner? Det kunne være en interessant Guinness-rekord at prøve at sætte.
Løsning 2, der bruger to TOP-underforespørgsler
Hvis du antager, at du leder efter en løsning, der tager sekunder, ikke dage, at fuldføre, er her en idé. I det anvendte tabeludtryk skal du forene to indre TOP (1)-forespørgsler – den ene filtrerer en række, hvor T2.val
=T1.val (bestilles efter T2.val, T2.keycol). Det er nemt at oprette indekser til at understøtte sådanne forespørgsler ved at aktivere en enkelt række-søgning. Stadig inden for det anvendte tabeludtryk skal du bruge en ydre TOP (1)-forespørgsel mod resultatet med to rækker, baseret på rækkefølgen ABS(D.val – T1.val), D.val, D.keycol. Der vil være en TopN-sortering involveret, men den vil blive anvendt på to rækker ad gangen. Her er de anbefalede indekser til at understøtte denne løsning:
CREATE INDEX idx_val_key ON dbo.T1(val, keycol) INCLUDE(othercols); CREATE INDEX idx_val_key ON dbo.T2(val, keycol) INCLUDE(othercols); OPRET INDEX idx_valD_key PÅ dbo.T2(val DESC, keycol) INCLUDE(othercols);Her er den komplette løsningskode:
SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1) ) SOM andre cols2 FRA dbo.T1 KRYDS ANVEND ( VÆLG TOP (1) D.* FRA ( VÆLG TOP (1) * FRA dbo.T2 HVOR T2.val=T1.val BESTIL EFTER T2.val, T2.keycol ) SOM DORDER AF ABS(D.val - T1.val), D.val, D. keycol ) AS A; Husk, at vi har 1.000.000 rækker i hver tabel, hvor valkolonnen har værdier i området 1 – 10.000.000 (lav tæthed) og optimale indekser på plads.
Planen for denne forespørgsel er vist i figur 2.
Figur 2:Plan for løsning 2
Observer den optimale brug af indekserne på T2, hvilket resulterer i en plan med lineær skalering. Denne plan bruger en indeksspole på samme måde som den tidligere plan gjorde, dvs. for at undgå at gentage arbejdet i den indre gren af sløjfen for duplikerede T1.val-værdier. Her er præstationsstatistikken, som jeg fik for udførelsen af denne forespørgsel på mit system:
Forløbet:27,7 sek., CPU:27,6 sek., logisk læsning:17.304.674Løsning 2, med spooling deaktiveret
Du kan ikke lade være med at spekulere på, om indeksspolen virkelig er gavnlig her. Pointen er at undgå at gentage arbejde for duplikerede T1.val-værdier, men i en situation som vores, hvor vi har meget lav tæthed, er der meget få dubletter. Det betyder, at det mest sandsynlige arbejde, der er involveret i spooling, er større end blot at gentage arbejdet for dubletter. Der er en enkel måde at bekræfte dette på - ved at bruge sporingsflag 8690 kan du deaktivere spooling i planen, sådan:
SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1) ) SOM andre cols2 FRA dbo.T1 KRYDS ANVEND ( VÆLG TOP (1) D.* FRA ( VÆLG TOP (1) * FRA dbo.T2 HVOR T2.val=T1.val BESTIL EFTER T2.val, T2.keycol ) SOM DORDER AF ABS(D.val - T1.val), D.val, D. keycol ) SOM EN MULIGHED(QUERYTRACEON 8690); Jeg fik planen vist i figur 3 for denne udførelse:
Figur 3:Plan for løsning 2, med spooling deaktiveret
Bemærk, at indeksspolen forsvandt, og denne gang bliver den indre gren af løkken udført 1.000.000 gange. Her er præstationsstatistikken, som jeg fik for denne udførelse:
Forløbet:19,18 sek., CPU:19,17 sek., logisk læsning:6.042.148Det er en reduktion på 44 procent i eksekveringstiden.
Løsning 2, med ændret værdiområde og indeksering
Deaktivering af spooling giver meget mening, når du har lav tæthed i T1.val-værdierne; dog kan spoleringen være meget fordelagtig, når du har høj tæthed. Kør f.eks. følgende kode for at genudfylde T1 og T2 med eksempeldataindstilling @maxvalT1 og @maxvalT2 til 1000 (1.000 maksimale distinkte værdier):
DEKLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =1000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =1000; TRUNCATE TABEL dbo.T1; TRUNCATE TABEL dbo.T2; INSERT INTO dbo.T1 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT1 + 1 AS val FROM dbo.GetNums(1, @numrowsT1) AS Nums; INSERT INTO dbo.T2 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT2 + 1 AS val FROM dbo.GetNums(1, @numrowsT2) AS Nums;Kør løsning 2 igen, først uden sporingsflaget:
SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1) ) SOM andre cols2 FRA dbo.T1 KRYDS ANVEND ( VÆLG TOP (1) D.* FRA ( VÆLG TOP (1) * FRA dbo.T2 HVOR T2.val=T1.val BESTIL EFTER T2.val, T2.keycol ) SOM DORDER AF ABS(D.val - T1.val), D.val, D. keycol ) AS A; Planen for denne udførelse er vist i figur 4:
Figur 4:Plan for løsning 2, med værdiområde 1 – 1000
Optimizeren besluttede at bruge en anden plan på grund af den høje tæthed i T1.val. Bemærk, at indekset på T1 scannes i nøglerækkefølge. Så for hver første forekomst af en distinkt T1.val-værdi udføres den indre gren af løkken, og resultatet spooles i en regulær tabelspool (rebind). Derefter, for hver ikke-første forekomst af værdien, anvendes en tilbagespoling. Med 1.000 forskellige værdier udføres den indre gren kun 1.000 gange. Dette resulterer i fremragende præstationsstatistikker:
Forløbet:1,16 sek., CPU:1,14 sek., logisk læsning:23.278Prøv nu at køre løsningen med spooling deaktiveret:
SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1) ) SOM andre cols2 FRA dbo.T1 KRYDS ANVEND ( VÆLG TOP (1) D.* FRA ( VÆLG TOP (1) * FRA dbo.T2 HVOR T2.val=T1.val BESTIL EFTER T2.val, T2.keycol ) SOM DORDER AF ABS(D.val - T1.val), D.val, D. keycol ) SOM EN MULIGHED(QUERYTRACEON 8690); Jeg fik planen vist i figur 5.
Figur 5:Plan for løsning 2, med værdiområde 1 – 1.000 og spooling deaktiveret
Det er i det væsentlige den samme plan vist tidligere i figur 3. Den indre gren af løkken bliver udført 1.000.000 gange. Her er præstationsstatistikken, som jeg fik for denne udførelse:
Forløbet:24,5 sek., CPU:24,2 sek., logisk læsning:8.012.548Det er klart, at du skal passe på ikke at deaktivere spooling, når du har høj tæthed i T1.val.
Livet er godt, når din situation er enkel nok til, at du er i stand til at oprette understøttende indekser. Virkeligheden er, at der i nogle tilfælde i praksis er nok yderligere logik i forespørgslen, der udelukker muligheden for at skabe optimale understøttende indekser. I sådanne tilfælde vil løsning 2 ikke klare sig godt.
For at demonstrere ydeevnen af løsning 2 uden at understøtte indekser skal du genudfylde T1 og T2 med eksempeldataindstilling @maxvalT1 og @maxvalT2 til 10000000 (værdiområde 1 – 10M), og også fjerne de understøttende indekser:
DROP INDEX HVIS FINDER idx_val_key PÅ dbo.T1; DROP INDEX HVIS FINDER idx_val_key PÅ dbo.T2; DROP INDEX HVIS FINDER idx_valD_key PÅ dbo.T2; DEKLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =10000000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =10000000; TRUNCATE TABEL dbo.T1; TRUNCATE TABEL dbo.T2; INSERT INTO dbo.T1 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT1 + 1 AS val FROM dbo.GetNums(1, @numrowsT1) AS Nums; INSERT INTO dbo.T2 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT2 + 1 AS val FROM dbo.GetNums(1, @numrowsT2) AS Nums;Genkør løsning 2, med Inkluder Live Query Statistics aktiveret i SSMS:
SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1) ) SOM andre cols2 FRA dbo.T1 KRYDS ANVEND ( VÆLG TOP (1) D.* FRA ( VÆLG TOP (1) * FRA dbo.T2 HVOR T2.val=T1.val BESTIL EFTER T2.val, T2.keycol ) SOM DORDER AF ABS(D.val - T1.val), D.val, D. keycol ) AS A; Jeg fik planen vist i figur 6 for denne forespørgsel:
Figur 6:Plan for løsning 2, uden indeksering, med værdiområde 1 – 1.000.000
Du kan se et mønster meget lig det vist tidligere i figur 1, kun denne gang scanner planen T2 to gange pr. særskilt T1.val-værdi. Igen bliver planens kompleksitet kvadratisk. At køre forespørgslen i SSMS med Inkluder Live Query Statistics aktiveret tog 49,6 sekunder at behandle 100 rækker fra T1 på min bærbare computer, hvilket betyder, at det skulle tage denne forespørgsel omkring 5,7 dage at fuldføre. Dette kan selvfølgelig betyde gode nyheder, hvis du forsøger at bryde Guinness verdensrekord for binge-watching en live-forespørgselsplan.
Konklusion
Jeg vil gerne takke Karen Ly fra RBC for at have præsenteret mig for denne fineste match-udfordring. Jeg var ret imponeret over hendes kode til at håndtere den, som inkluderede en masse ekstra logik, der var specifik for hendes system. I denne artikel viste jeg rimeligt effektive løsninger, når du er i stand til at skabe optimale understøttende indekser. Men som du kunne se, i de tilfælde, hvor dette ikke er en mulighed, er de eksekveringstider, du får, naturligvis uhyggelige. Kan du tænke på løsninger, der vil klare sig godt selv uden optimale understøttende indekser? Fortsættes...