Nærmest match, del 3

I Closest Match, del 1, dækkede jeg en T-SQL-udfordring, som blev leveret til mig af Karen Ly, en Jr. Fixed Income Analyst hos RBC. Udfordringen involverede to tabeller - T1 og T2, hver med en nøglekolonne (keycol), en værdi (val) og nogle andre kolonner (repræsenteret med en kolonne kaldet othercols). Opgaven var at matche til hver række fra T1 rækken fra T2, hvor T2.val er tættest på T1.val (den absolutte forskel er den laveste laveste), ved at bruge den laveste T2.keycol værdi som tiebreaker. Jeg leverede et par relationelle løsninger og diskuterede deres præstationskarakteristika. Jeg udfordrede dig også til at forsøge at finde en rimeligt effektiv løsning i tilfælde, hvor du ikke har lov til/i stand til at oprette understøttende indekser. I del 2 demonstrerede jeg, hvordan dette kan opnås ved at bruge iterative løsninger. Jeg fik flere meget interessante læserløsninger fra Kamil Konsno, Alejandro Mesa og Radek Celuch, og de løsninger er fokus i denne måneds artikel.

Eksempel på data

Som en påmindelse har jeg givet både små og store sæt eksempeldata, som du kan arbejde med. Små sæt til at kontrollere gyldigheden af ​​din løsning og store sæt til at kontrollere dens ydeevne. Brug følgende kode til at oprette prøvedatabasen testdb og i den eksempeltabellerne T1 og T2:

-- Eksempel på dbSET NOCOUNT ON; HVIS DB_ID('testdb') ER NULL OPRET DATABASE testdb;GO BRUG testdb;GO -- Eksempeltabeller T1 og T2DROP TABEL HVIS FINDER dbo.T1, dbo.T2; CREATE TABLE dbo.T1( keycol INT IKKE NULL IDENTITETSBEGRÆNSNING PK_T1 PRIMÆR NØGLE, val INT IKKE NULL, othercols BINÆR(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 BINÆR(100) IKKE NULL BEGRÆNSNING DFT_T2_col1 DEFAULT(0xBB));

Brug følgende kode til at udfylde tabellerne med små sæt eksempeldata:

-- Udfyld T1 og T2 med små sæt af eksempeldata TRUNCATE TABLE dbo.T1;TRUNCATE TABLE 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);

Jeg vil bruge de små sæt eksempeldata, når jeg skal beskrive logikken i de forskellige løsninger og levere mellemresultatsæt for trinene i løsningerne.

Brug følgende kode til at oprette hjælpefunktionen GetNums og for at udfylde tabellerne med store sæt eksempeldata:

-- Hjælpefunktion til at generere en sekvens af heltalDROP FUNKTION HVIS FINDER dbo.GetNums;GO CREATE ELLER ALTER FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURERER TABLEASRETURN MED L0 AS (VÆLG c FRA (VÆLG c FRA) 1 FORBINDELSE ALLE VÆLG 1) SOM D(c)), L1 AS (VÆLG 1 SOM c FRA L0 SOM EN KRYDSJOIN L0 SOM B), L2 SOM (VÆLG 1 SOM c FRA L1 SOM KRYDSFIND L1 SOM B), L3 AS (VÆLG 1 AS c FRA L2 SOM A CROSS JOIN L2 AS B), L4 AS (SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B), L5 AS (VÆLG 1 AS c FRA L4 SOM A CROSS JOIN L4 AS B), Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum FROM L5) SELECT TOP(@high - @low + 1) @low + rownum - 1 AS n FROM Nums ORDER BY rownum;GO -- Udfyld T1 og T2 med store sæt af eksempeldataDECLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =10000000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =10000000; TRUNCATE TABLE dbo.T1;TRUNCATE TABLE 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;

Når du vil teste din løsning med understøttende indekser, skal du bruge følgende kode til at oprette disse indekser:

CREATE INDEX idx_val_key ON dbo.T1(val, keycol) INCLUDE(othercols);CREATE INDEX idx_val_key ON dbo.T2(val, keycol) INCLUDE(othercols);CREATE INDEX idx_valD_key ON dbo.T2(val) DE INCLUDE(othercols);

Når du vil teste din løsning uden at understøtte indekser, skal du bruge følgende kode til at fjerne disse 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;

Løsning 1 af Kamil Kosno – Brug af en midlertidig tabel

Kamil Kosno indsendte et par stykker - to med hans originale ideer og to variationer af Alejandros og Radeks løsninger. Kamils ​​første løsning bruger en indekseret midlertidig tabel. Ofte er det sådan, at selvom du ikke må oprette understøttende indekser på de originale tabeller, har du lov til at arbejde med midlertidige tabeller, og med midlertidige tabeller kan du altid oprette dine egne indekser.

Her er den komplette løsnings kode:

DROP TABEL HVIS FINDER #T2; SELECT MIN(keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val; CREATE UNIQUE INDEX idx_nc_val_key ON #T2(val, keycol); MED bestvals AS( SELECT keycol AS keycol1, val AS val1, othercols AS othercols1, CASE WHEN (prev + nxt IS NULL) THEN COALESCE(prev, nxt) WHEN ABS(val - prev)  

 I trin 1 af løsningen gemmer du minimum keycol for hver unik val i en midlertidig tabel kaldet #T2, og opretter et understøttende indeks på (val, keycol). Her er koden, der implementerer dette trin:
 
DROP TABEL HVIS FINDER #T2; SELECT MIN(keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val; CREATE UNIQUE INDEX idx_nc_val_key ON #T2(val, keycol); VÆLG * FRA #T2;
 

 Den midlertidige tabel er udfyldt med følgende data:
 
keycol val----------- ----------1 24 33 76 118 139 1710 19
 

 I trin 2 af løsningen anvender du følgende:
 

 For hver række i T1 udregn prev og nxt værdier fra #T2. Beregn prev som den maksimale værdi i #T2, der er mindre end eller lig med val i T1. Beregn nxt som minimumsværdien i #T2, der er større end eller lig med værdien i T1.
 

 Brug et CASE-udtryk til at beregne val2 baseret på følgende logik:
 
 
 Når prev eller nxt er null, returneres den første nonnull af de to, eller NULL, hvis begge er NULL. 
 
 Når den absolutte forskel mellem val og prev er mindre end den absolutte forskel mellem val og nxt, returneres prev. 
 
 Når, hvis den absolutte forskel mellem val og nxt er mindre end den absolutte forskel mellem val og prv, returneres nxt. 
 
 Ellers, hvis nxt er mindre end prev, returner nxt, ellers returner prev. 
 
 

 Her er koden, der implementerer dette trin:
 
SELECT keycol AS keycol1, val AS val1, othercols AS othercols1, CASE WHEN (prev + nxt IS NULL) THEN COALESCE(prev, nxt) WHEN ABS(val - prev)  

 Denne kode genererer følgende output:
 
keycol1 val1 othercols1 val2-------- ----- ---------- -----1 1 0xAA 22 1 0xAA 23 3 0xAA 34 3 0xAA 35 5 0xAA 36 8 0xAA 77 13 0xAA 138 16 0xAA 179 18 0xAA 1710 20 0xAA 1911 21 0xAA 19
 

 I trin 3 af løsningen definerer du en CTE kaldet bestvals baseret på forespørgslen fra trin 2. Du forbinder derefter bestvals med #T2 for at få nøglerne, og slutter resultatet med T2 for at få resten af ​​dataene (othercols).
 

 Her er koden, der implementerer dette trin:
 
SELECT keycol1, val1, SUBSTRING(othercols1, 1, 1) AS othercols1, tempT2.keycol AS keycol2, val2, SUBSTRING(T2.othercols, 1, 1) AS othercols2FROM bestvals AS B INNER JOIN #T2 AS tempT2 ON tempT2 .val =B.val2 INNER JOIN dbo.T2 ON T2.keycol =tempT2.keycol;
 

 Planen for løsning 1 af Kamil med understøttende indekser er vist i figur 1.
 

 Figur 1:Plan for løsning 1 af Kamil med indekser 
 

 Den første gren af ​​planen grupperer og aggregerer dataene fra T2 og skriver resultatet til den midlertidige tabel #T2. Bemærk, at denne gren bruger en forudbestilt Stream Aggregate-algoritme, der er afhængig af en bestilt scanning af indekset idx_valD_key på T2.
 

 Her er præstationsstatistikkerne for denne plan:
 
køretid (sek):5,55, CPU (sek):16,6, logisk læsning:6.687.172
 

 Planen for løsning 1 af Kamil uden understøttende indekser er vist i figur 2.
 

 Figur 2:Plan for løsning 1 af Kamil uden indekser 
 

 Hovedforskellen mellem denne plan og den forrige er, at den første gren af ​​planen, som håndterer grupperings- og aggregeringsdelen i trin 1, denne gang ikke kan trække de forudbestilte data fra et understøttende indeks, så den trækker dem uordnet fra den klyngede indeks på T2 og bruger derefter en Hash Aggregate-algoritme.
 

 Her er præstationsstatistikkerne for denne plan:
 
køretid:6.44, CPU:19.3, logisk læsning:6.688.277
 
Løsning af Alejandro Mesa – Bruger sidste ikke-nul-teknik
 

 Alejandros løsning bruger den sidste nonnull-teknik, der er beskrevet her.
 

 Her er den komplette løsnings kode (leveres her uden at returnere andre cols):
 
MED R1 AS( SELECT keycol, val, tid, MAX( CASE WHEN tid =0 THEN CAST(val AS binær(4)) + CAST(keycol AS binær(4)) END ) OVER( ORDER BY val, tid , keycol RÆKKER MELLEM UNBOUNDED PRECEDING AND 1 PRECEDING ) AS below_binstr, MIN( CASE WHEN tid =0 THEN CAST(val AS binær(4)) + CAST(keycol AS binær(4)) END ) OVER( ORDER BY val, tid, keycol RÆKKER MELLEM 1 FØLGENDE OG UBUNDET FØLGENDE ) AS above_binstr FRA ( SELECT keycol, val, 1 AS tid FRA dbo.T1 UNION ALLE VÆLG MIN(keycol) AS keycol, val, 0 AS tid FRA dbo.T2 GROUP BY val ) AS T ),R2 AS( SELECT keycol, val, CAST(SUBSTRING(below_binstr, 1, 4) AS int) AS below_T2_val, CAST(SUBSTRING(below_binstr, 5, 4) AS int) AS below_T2_keycol, CAST(SUBSTRING(above_binstr, 1, 4) AS int) AS above_T2_val, CAST(SUBSTRING(above_binstr, 5, 4) AS above_T2_keycol FROM R1 WHERE tid =1),R3 AS( SELECT keycol, val, COALESCE(below_T2_val, above_T2 _val) AS below_T2_val, COALESCE(below_T2_keycol, above_T2_keycol) AS below_T2_keycol, COALESCE(above_T2_val, below_T2_val) AS above_T2_val, COALESCE(above_T2_keycol, below_T2_keycol_col)_col_key ASV_key2_SELECT_1 ) <=ABS(above_T2_val - val) THEN below_T2_keycol ELSE above_T2_keycol END AS keycol2, CASE WHEN ABS(val - below_T2_val) <=ABS(above_T2_val - val) THEN below_T2_val ELSE above_T2_val END AS;
 I trin 1 af løsningen forener du rækkerne fra T1 (tildeler en resultatkolonne kaldet tid til 1) med rækkerne fra T2 (tildeler tid =0), og definerer en afledt tabel kaldet T baseret på resultatet. Ved at bruge den sidste nonnull-teknik, baseret på rækkefølgen af ​​val, tid, keycol, for hver aktuelle række, henter du den sidste tid =0 rækkes værdier sammenkædet i en binær kolonne kaldet below_binstr. På samme måde henter du den næste tid =0 rækkes værdier sammenkædet i en binær kolonne kaldet ovenfor_binstr.
 

 Her er koden, der implementerer dette trin:
 
SELECT keycol, val, tid, MAX( CASE WHEN tid =0 THEN CAST(val AS binær(4)) + CAST(keycol AS binær(4)) END ) OVER( ORDER BY val, tid, keycol RÆKKER MELLEM UNBOUNDED PRECEDING AND 1 PRECEDING ) AS below_binstr, MIN( CASE WHEN tid =0 THEN CAST(val AS binær(4)) + CAST(keycol AS binær(4)) END ) OVER( ORDER BY val, tid, keycol RÆKKER MELLEM 1 FØLGENDE OG UBEGRÆNSET FØLGENDE ) AS above_binstrFROM ( SELECT keycol, val, 1 AS tid FRA dbo.T1 UNION ALL SELECT MIN(keycol) AS keycol, val, 0 AS tid FRA dbo.T2 GROUP BY val ) AS T;
 

 Denne kode genererer følgende output:
 
keycol val tid below_binstr above_binstr------------------------------------------------- --------- ---------------------- 1 1 1 NULL 0x00000002000000012 1 1 NULL 0x00000002000000011 2 0 NULL 0X000000030000044 3 0 0x0000000300000004 0x00000007000000035 5 1 0x0000000300000004 0x00000007000000033 7 0x0000000300000004 0x0000000b000000066 8 1 0x0000000007000003 0x0000000000000000000 08 0x00000011000000098 16 1 0x0000000d00000008 0x00000011000000099 17 0 

 I trin 2 af løsningen definerer du en CTE kaldet R1 baseret på forespørgslen fra Trin 1. Du forespørger R1, filtrerer kun rækker, hvor tid =1, og udtrækker de individuelle værdier fra de sammenkædede binære strenge.
 

 Her er koden, der implementerer dette trin:
 
SELECT keycol, val, CAST(SUBSTRING(below_binstr, 1, 4) AS int) AS below_T2_val, CAST(SUBSTRING(below_binstr, 5, 4) AS int) AS below_T2_keycol, CAST(SUBSTRING(above_binstr, 1, 4) AS int) AS above_T2_val, CAST(SUBSTRING(above_binstr, 5, 4) AS int) AS above_T2_keycolFROM R1WHERE tid =1;
 

 Denne kode genererer følgende output:
 
keycol val below_T2_val below_T2_keycol above_T2_val above_T2_keycol---------------- ---------- ------------ ------- ------------ ---------------1 1 NULL NULL 2 12 1 NULL NULL 2 13 3 3 4 7 34 3 3 4 7 35 5 3 4 7 36 8 7 3 11 67 13 13 8 17 98 16 13 8 17 99 18 17 9 19 1010 20 19 10 NULL 2 NULL 1 
 I trin 3 af løsningen definerer du en CTE kaldet R2 baseret på forespørgslen fra trin 2. Du beregner derefter følgende resultatkolonner:
 
 
 below_T2_val:den første nonnull mellem below_T2_val og above_T2_val 
 
 below_T2_keycol:den første nonnull mellem below_T2_keycol og above_T2_keycol 
 
 above_T2_val:den første nonnull mellem above_T2_val og below_T2_val 
 
 above_T2_keycol:den første nonnull mellem above_T2_keycol og below_T2_keycol 
 
 

 Her er koden, der implementerer dette trin:
 
SELECT keycol, val, COALESCE(below_T2_val, above_T2_val) AS below_T2_val, COALESCE(below_T2_keycol, above_T2_keycol) AS below_T2_keycol, COALESCE(above_T2_val, below_T2_val) AS above_ALES_2_val) AS above_ALES_2_2 key below, COALF_2_val; 

 Denne kode genererer følgende output:
 
keycol val below_T2_val below_T2_keycol above_T2_val above_T2_keycol---------------- ---------- ------------ ------- ------------ --------------------1 1 2 1 2 12 1 2 1 2 13 3 3 4 7 34 3 3 4 7 35 5 3 4 7 36 8 7 3 11 67 13 13 8 17 98 16 13 8 17 99 18 17 9 19 1010 20 19 10 19 10 19 10 19 10 19 

 I trin 4 af løsningen definerer du en CTE kaldet R3 baseret på forespørgslen fra trin 3. Du returnerer keycol aliaseret som T1_keycol og val aliased som T1_val. Beregn resultatkolonnen T2_keycol som:hvis den absolutte forskel mellem val og under_T2_val er mindre end eller lig med den absolutte forskel mellem ovenfor_T2_val og val, returneres under_T2_keycol, ellers ovenfor_T2_keycol. Beregn resultatkolonnen T2_val som:hvis den absolutte forskel mellem val og under_T2_val er mindre end eller lig med den absolutte forskel mellem ovenfor_T2_val og val, returneres under_T2_val, ellers over_T2_val.
 

 Her er koden, der implementerer dette trin:
 
SELECT keycol AS keycol1, val AS val1, CASE WHEN ABS(val - below_T2_val) <=ABS(above_T2_val - val) THEN below_T2_keycol ELSE above_T2_keycol END AS keycol2, CASE WHEN ABS(val - below_T2_val) <=ABS_val) -ve_T2_val val) THEN below_T2_val ELSE above_T2_val END AS val2FROM R3;
 

 Planen for Alejandros løsning med understøttende indekser er vist i figur 3.
 

 Figur 3:Plan for løsning af Alejandro med indekser 
 

 Her er præstationsstatistikkerne for denne plan:
 
køretid:7,8, CPU:12,6, logisk læsning:35.886
 

 Planen for Alejandros løsning uden understøttende indekser er vist i figur 4.
 

 Figur 4:Plan for løsning af Alejandro uden indekser 
 

 Her er præstationsstatistikkerne for denne plan:
 
køretid:8.19, CPU:14.8, logisk læsning:37.091
 

 Bemærk, at der i de første to grene af planen i figur 4 er to typer forud for Merge Join (Concatenation)-operatøren på grund af manglen på understøttende indekser. Disse sorter er ikke nødvendige i planen i figur 3, da dataene hentes forudbestilt fra de understøttende indekser.
 
Kamils ​​variation af Alejandros løsning
 

 I denne løsning stolede Kamil også på den sidste nonnull-teknik. Her er den komplette løsnings kode:
 
WITH all_vals AS( SELECT keycol, val FROM dbo.T1 UNION ALL SELECT DISTINCT NULL, val FROM dbo.T2), ranges AS( SELECT keycol, val, MAX(CASE WHEN keycol IS NULL THEN val END) OVER (ORDER BY val, keycol RÆKKER MELLEM UNBOUNDED PRECEDING AND 1 PRECEDING) SOM prev, MIN(CASE WHEN keycol IS NULL THEN val END) OVER (ORDER BY val, keycol RÆKKER MELLEM 1 FØLGENDE OG UBEGRÆNSET FØLGENDE) AS_nxts Fmatched all_vals(Fmatched) SELECT keycol AS keycol1, val AS val1, CASE NÅR ABS(val - prev) <=ISNULL(ABS(val - nxt), prev) THEN prev ELSE nxt END AS val2 FRA intervaller WHERE keycol IS NOT NULL)SELECT keycol1, val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, val2, T2.keycol AS keycol2, SUBSTRING(T2.othercols, 1, 1) AS othercols2 FROM matched_vals AS M INNER JOIN (SELECT *, ROW_NUMBER() OVER (PARTITION BY val BESTIL EFTER keycol) SOM rn FRA dbo.T2 ) AS T2 ON T2.val =M.val2 OG rn =1 INNER JOIN dbo.T1 ON T1.keycol =keycol1;
 

 I trin 1 af løsningen definerer du CTE'er kaldet all_vals og ranges, hvor du bruger den sidste nonnull-teknik til at identificere for hver værdi i T1 (hvor keycol ikke er NULL) områder med under (prev) og over (nxt) værdier fra T2 ( hvor keycol er null).
 

 Her er koden, der implementerer dette trin:
 
WITH all_vals AS( SELECT keycol, val FROM dbo.T1 UNION ALL SELECT DISTINCT NULL, val FROM dbo.T2), ranges AS( SELECT keycol, val, MAX(CASE WHEN keycol IS NULL THEN val END) OVER (ORDER BY val, keycol RÆKKER MELLEM UNBOUNDED PRECEDING AND 1 PRECEDING) SOM prev, MIN(CASE WHEN keycol IS NULL THEN val END) OVER (ORDER BY val, keycol RÆKKER MELLEM 1 FØLGENDE OG UBEGRÆNSET FØLGENDE) * alle_nxts SELECT.;
 

 Denne kode genererer følgende output:
 
keycol val prev nxt----------- ----------- ------------------ ---------- -1 1 NULL 22 1 NULL 2 NULL 2 NULL 3 NULL 3 2 73 3 3 74 3 3 75 5 3 7NULL 7 3 116 8 7 11NULL 11 7 13NULL 13 11 177 13 NULL 13 11 177 17 19 1 7 19 19 19 19 19 19 19 19 19 20 19 NULL11 21 19 NULL
 

 I trin 2 af løsningen forespørger du CTE-intervallerne og filtrerer kun rækker, hvor keycol ikke er null. Du returnerer keycol og val kolonnerne fra T1 som henholdsvis keycol1 og val1. Derefter, mellem prev og nxt, returnerer du nærmest val1 som val2.
 

 Her er koden, der implementerer dette trin:
 
SELECT keycol AS keycol1, val AS val1, CASE WHEN ABS(val - prev) <=ISNULL(ABS(val - nxt), prev) THEN prev ELSE nxt END AS val2FROM rangesWHERE keycol IS NOT NULL;
 

 Denne kode genererer følgende output:
 
keycol1 val1 val2------------ ----------- ----------1 1 22 1 23 3 34 3 35 5 36 8 77 13 138 16 179 18 1710 20 1911 21 19
 

 I trin 3 af løsningen definerer du en CTE kaldet matched_vals baseret på forespørgslen fra trin 2. Du definerer også en afledt tabel kaldet T2, hvor du ved hjælp af partitionerede rækkenumre håndterer tiebreaking-logikken for rækkerne fra dbo.T2. Du forbinder derefter matched_vals, CTE T2 og tabellen T1 for at håndtere den endelige matchningslogik.
 

 Her er koden, der implementerer dette trin:
 
SELECT keycol1, val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, val2, T2.keycol AS keycol2, SUBSTRING(T2.othercols, 1, 1) AS othercols2 FROM matched_vals AS M INNER JOIN ( SELECT * , ROW_NUMBER() OVER (PARTITION BY val ORDER BY keycol) AS rn FROM dbo.T2 ) AS T2 ON T2.val =M.val2 AND rn =1 INNER JOIN dbo.T1 ON T1.keycol =keycol1;
 

 Planen for Kamils ​​variation af Alejandros løsning med understøttende indekser er vist i figur 5.
 

 Figur 5:Plan for Kamils ​​variation af Alejandros løsning med indekser 
 

 Her er præstationsstatistikkerne for denne plan:
 
køretid:11,5, CPU:18,3, logisk læsning:59.218
 

 Planen for Kamils ​​variation af Alejandros løsning uden understøttende indekser er vist i figur 6.
 

 Figur 6:Plan for Kamils ​​variation af Alejandros løsning uden indekser 
 

 Her er præstationsstatistikkerne for denne plan:
 
køretid:12,6, CPU:23,5, logisk læsning:61.432
 

 I lighed med planerne for Alejandros løsning kræver planen i figur 5 heller ikke i dette tilfælde eksplicit sortering før anvendelse af Merge Join (sammenkædning)-operatoren, da dataene hentes forudbestilt fra understøttende indekser, og planen i figur 6 gør det. kræver eksplicitte sorteringer, da der ikke er nogen understøttende indekser.
 
Løsning af Radek Celuch – Brug af intervaller
 

 Radek kom med en enkel og smuk idé. For hver distinkt værdi i T2.val beregner du et interval, der repræsenterer rækken af ​​værdier fra T1.val, der ville matche den aktuelle T2.val. 
 

 Her er den komplette løsnings kode:
 
MED Pre1 AS( SELECT keycol, val, othercols, ROW_NUMBER() OVER(PARTITION BY val ORDER BY keycol) SOM rn FRA dbo.T2),Pre2 AS( SELECT keycol, val, othercols, LAG(val) OVER( ORDER BY val) AS prev, LEAD(val) OVER(ORDER BY val) AS next FROM Pre1 WHERE rn =1),T2 AS( SELECT keycol, val, othercols, ISNULL(val - (val - prev) / 2 + ( 1 - (val - prev) % 2), 0) AS low, ISNULL(val + (next - val) / 2, 2147483647) AS high FROM Pre2)SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING( T1.othercols, 1, 1) AS othercols1, T2.keycol AS keycol2, T2.val AS val2, SUBSTRING(T2.othercols, 1, 1) AS othercols2FROM dbo.T1 INNER JOIN T2 PÅ T1.val MELLEM T2.lav OG T2.high;
 

 I trin 1 af løsningen forespørger du T2 og beregner rækkenumre (kald kolonnen rn), opdelt efter val og sorteret efter keycol. Du definerer en CTE kaldet Pre1 baseret på denne forespørgsel. Du forespørger derefter Pre1 og filtrerer kun rækkerne, hvor rn =1. I den samme forespørgsel, ved hjælp af LAG og LEAD, returnerer du for hver række værdien af ​​val-kolonnen fra den forrige række (kald den prev) og fra den næste række ( kald det næste).
 

 Her er koden, der implementerer dette trin:
 
MED Pre1 AS( SELECT keycol, val, othercols, ROW_NUMBER() OVER(PARTITION BY val ORDER BY keycol) SOM rn FRA dbo.T2)SELECT keycol, val, othercols, LAG(val) OVER(ORDER BY val) AS prev, LEAD(val) OVER(ORDER BY val) AS nextFROM Pre1WHERE rn =1;
 

 Denne kode genererer følgende output:
 
keycol val othercols prev next------- ---- ---------- ------------------ ---------- -1 2 0xBB NULL 34 3 0xBB 2 73 7 0xBB 3 116 11 0xBB 7 138 13 0xBB 11 179 17 0xBB 13 1910 19 0xBB 17 NULL
 

 I trin 2 af løsningen definerer du en CTE kaldet Pre2 baseret på forespørgslen fra trin 1. Du forespørger Pre2 og beregner for hver række et interval [lav, høj], hvor val fra T1 ville falde ind. Her er beregningerne for lav og høj:
 
 
 lav =ISNULL(val – (val – forrige) / 2 + (1 – (val – forrige) % 2), 0) 
 
 høj =ISNULL(val + (næste – val) / 2, 2147483647) 
 
 

 Mod 2-kontrollen til beregning af den lave grænse bruges til at opfylde det nedre T2.val-krav, og rækkenummerfilteret bruges til at opfylde det nedre T2.keycol-krav. Værdierne 0 og 2147483647 bruges som de ekstreme nedre og øvre grænser.
 

 Her er koden, der implementerer dette trin:
 
SELECT keycol, val, othercols, ISNULL(val - (val - prev) / 2 + (1 - (val - prev) % 2), 0) AS low, ISNULL(val + (next - val) / 2 , 2147483647) SÅ højt FRA Pre2;
 

 Denne kode genererer følgende output:
 
keycol val othercols lav høj------- ---- ---------- ---- -------------1 2 0xBB 0 24 3 0xBB 3 53 7 0xBB 6 96 11 0xBB 10 128 13 0xBB 13 159 17 0xBB 16 1810 19 0xBB 19 2147483647
 

 I trin 3 af løsningen definerer du en CTE kaldet T2 baseret på forespørgslen fra trin 2. Du forbinder derefter tabellen T1 med CTE T2 matchende rækker baseret på val fra T1 inden for intervallet [lav, høj] i T2.
 

 Her er koden, der implementerer dette trin:
 
SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, T2.keycol AS keycol2, T2.val AS val2, SUBSTRING(T2.othercols, 1, 1) ) SOM andre cols2FROM dbo.T1 INNER JOIN T2 PÅ T1.val MELLEM T2.low OG T2.high;
 

 Planen for Radeks løsning med understøttende indekser er vist i figur 7. 
 

 Figur 7:Plan for løsning af Radek med indekser 
 

 Her er præstationsstatistikkerne for denne plan:
 
køretid:10,6, CPU:7,63, logisk læsning:3.193.125
 

 Planen for Radeks løsning uden understøttende indekser er vist i figur 8. 
 

 Figur 8:Plan for løsning af Radek uden indekser 
 

 Her er præstationsstatistikkerne for denne plan:
 
køretid:18.1, CPU:27.4, logisk læsning:5.827.360
 

 Her er præstationsforskellen mellem de to planer ret betydelig. Planen i figur 8 kræver en foreløbig sortering før beregningen af ​​rækkenumrene, hvilket planen i figur 7 ikke gør. Endnu vigtigere, for at matche hvert interval med de respektive rækker fra T1, skaber planen i figur 8 en indeksspole i det væsentlige som et alternativ til det manglende indeks, hvorimod planen i figur 7 blot bruger det eksisterende indeks idx_val_key på T1. Det er hovedårsagen til de store forskelle på tværs af alle præstationsmål. Alligevel er ydeevnen uden understøttende indekser rimelig.
 
Kamils ​​variation af Radeks løsning
 

 Kamil kom med en variation over Radeks løsning. Her er den komplette løsnings kode:
 
WITH T2_collapsed AS( SELECT keycol AS keycol2, val AS val2 , ROW_NUMBER() OVER (PARTITION BY val ORDER BY keycol) AS rn FROM dbo.T2), ranges AS( SELECT keycol2 AS prevkey, val2 AS prevval, LEAD( keycol2) OVER (ORDER BY val2) AS nxtkey, LEAD(val2) OVER (ORDER BY val2) AS nxtval FROM T2_collapsed WHERE rn =1),bestmatches AS( SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1) .othercols, 1, 1) SOM othercols1, CASE WHEN ABS(T1.val - prevval) <=ABS(T1.val - nxtval) THEN prevkey ELSE nxtkey END AS keycol2, CASE WHEN ABS(T1.val - prevval) <=ABS(T1.val - nxtval) THEN prevval ELSE nxtval END AS val2 FRA områder INNER JOIN dbo.T1 ON prevval <=T1.val AND T1.val  

 Here’s Kamil’s own description of this solution:
 

 This solution is close to Radek's idea of checking against low and high range, although the ranges are based purely on actual T2 values. We get each row and the lead values only for each row in collapsed T2 (first step always gets rid of duplicate keys if found, by using row number or min(keycol) grouped by val on t2). The key concepts are how to check low and high range not to get duplicates – lower range inclusive, higher range exclusive, as well as handling the outliers (if present) by creating a separate set looking at the lowest and max values in T2 (UNION ALL bit). The check against the max value is done with inclusive range to complement the case of T1 vals being equal to the top T2 vals.
 

 The plan for Kamil’s variation on Radek’s solution with supporting indexes is shown in Figure 9.
 

 Figure 9:Plan for Kamil’s variation on Radek’s solution with indexes 
 

 Here are the performance stats for this plan:
 
run time:8.59, CPU:8.5, logical reads:3,206,849
 

 The plan for Kamil’s variation on Radek’s solution without supporting indexes is shown in Figure 10.
 

 Figure 10:Plan for Kamil’s variation on Radek’s solution without indexes 
 

 Here are the performance stats for this plan:
 
run time:14, CPU:24.5, logical reads:5,870,596
 

 The plan in Figure 9 is serial and most of the calculations are done based on preordered data obtained from the supporting indexes. The plan in Figure 10 is parallel, plus there are a few sorts, and even an index spool activity. The performance measures of the latter plan are substantially higher than the former plan, but the performance in both cases is reasonable.
 
Solution 2 by Kamil Kosno – Using ranking, offset and aggregate window functions
 

 Kamil came up with another original approach that is based on a combination of ranking, offset and aggregate window functions. Here’s the complete solution’s code:
 
WITH A AS( SELECT 1 AS t, keycol,val, DENSE_RANK() OVER(ORDER BY val) AS rnk FROM dbo.T1 UNION ALL SELECT NULL, MIN(keycol), val, 0 FROM dbo.T2 GROUP BY val),B AS( SELECT t, keycol, val, CASE WHEN t =1 THEN DENSE_RANK() OVER (ORDER BY val, t) - rnk ELSE 0 END AS grp, LAG(CASE WHEN t IS NULL THEN val END) OVER(ORDER BY val, t) AS prev, LAG(CASE WHEN t IS NULL THEN keycol END) OVER(ORDER BY val, t) AS prevkey, LEAD(CASE WHEN t IS NULL THEN val END) OVER(ORDER BY val, t) AS nxt, LEAD(CASE WHEN t IS NULL THEN keycol END) OVER(ORDER BY val, t) AS nxtkey FROM A),C AS( SELECT keycol AS keycol1, val AS val1, MAX (prev) OVER(PARTITION BY grp ORDER BY prev DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS mxprev, MAX (prevkey) OVER(PARTITION BY grp ORDER BY prev DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS mxprevkey, MAX (nxt) OVER(PARTITION BY grp ORDER BY nxt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) AS mxnxt, MAX (nxtkey) OVER(PARTITION BY grp ORDER BY nxt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) AS mxnxtkey FROM B WHERE t =1),D AS( SELECT keycol1, val1, CASE WHEN ABS(val1 - mxprev) <=ISNULL(ABS(val1 - mxnxt), mxprev) THEN mxprevkey ELSE mxnxtkey END AS keycol2, CASE WHEN ABS(val1 - mxprev) <=ISNULL(ABS(val1 - mxnxt), mxprev) THEN mxprev ELSE mxnxt END AS val2 FROM C)SELECT D.keycol1, D.val1, D.keycol2, D.val2, SUBSTRING(T1.othercols, 1, 1) AS othercols1, SUBSTRING(T2.othercols, 1, 1) AS othercols2FROM D INNER JOIN dbo.T1 ON T1.keycol =D.keycol1 INNER JOIN dbo.T2 ON T2.keycol =D.keycol2;
 

 In Step 1 of the solution you unify the following result sets:
 
 
 Rows from T1 with a result column called t assigned with the constant 1 and column rnk representing dense rank values ordered by val 
 
 Group rows from T2 by val and return val and min keycol for each group, with the result column t assigned with NULL and rnk with 0 
 
 

 Her er koden, der implementerer dette trin:
 
SELECT 1 AS t, keycol,val, DENSE_RANK() OVER(ORDER BY val) AS rnkFROM dbo.T1UNION ALLSELECT NULL, MIN(keycol), val, 0FROM dbo.T2GROUP BY val;
 

 Denne kode genererer følgende output:
 
t keycol val rnk----------- ----------- ----------- --------------------1 1 1 11 2 1 11 3 3 21 4 3 21 5 5 31 6 8 41 7 13 51 8 16 61 9 18 71 10 20 81 11 21 9NULL 1 2 0NULL 4 3 0NULL 3 7 0NULL 6 11 0NULL 8 13 0NULL 9 17 0NULL 10 19 0
 

 In Step 2 of the solution you define a CTE called A based on the query from Step 1. You query A and compute group identifiers (grp) for T1 values that fall between ranges of distinct T2 values. This is done using an islands technique where you subtract rnk (dense ranks for only T1 values) from rnk2 (dense ranks for unified T1 values and distinct T2 values).
 

 Using the LAG and LEAD functions, you compute for each T1 row the prev/next val and keycol values from T2, if present, and NULL otherwise. These calculations return values for the first and last rows in each group, if present, but NULLs for intermediate rows in groups.
 

 Her er koden, der implementerer dette trin:
 
SELECT t, keycol, val, rnk, DENSE_RANK() OVER (ORDER BY val) AS rnk2, CASE WHEN t =1 THEN DENSE_RANK() OVER (ORDER BY val, t) - rnk ELSE 0 END AS grp, LAG(CASE WHEN t IS NULL THEN val END) OVER(ORDER BY val, t) AS prev, LAG(CASE WHEN t IS NULL THEN keycol END) OVER(ORDER BY val, t) AS prevkey, LEAD(CASE WHEN t IS NULL THEN val END) OVER(ORDER BY val, t) AS nxt, LEAD(CASE WHEN t IS NULL THEN keycol END) OVER(ORDER BY val, t) AS nxtkeyFROM A;
 

 Denne kode genererer følgende output:
 
t keycol val rnk rnk2 grp prev prevkey nxt nxtkey----- ------ --- --- ---- --- ----- ------- ----- -------1 1 1 1 1 0 NULL NULL NULL NULL1 2 1 1 1 0 NULL NULL 2 1NULL 1 2 0 2 0 NULL NULL 3 4NULL 4 3 0 3 0 2 1 NULL NULL1 3 3 2 3 2 3 4 NULL NULL1 4 3 2 3 2 NULL NULL NULL NULL1 5 5 3 4 2 NULL NULL 7 3NULL 3 7 0 5 0 NULL NULL NULL NULL1 6 8 4 6 3 7 3 11 6NULL 6 11 0 7 0 NULL NULL 13 8NULL 8 13 0 8 0 11 6 NULL NULL1 7 13 5 8 5 13 8 NULL NULL1 8 16 6 9 5 NULL NULL 17 9NULL 9 17 0 10 0 NULL NULL NULL NULL1 9 18 7 11 6 17 9 19 10NULL 10 19 0 12 0 NULL NULL NULL NULL1 10 20 8 13 7 19 10 NULL NULL1 11 21 9 14 7 NULL NULL NULL NULL
 

 In Step 3 you define a CTE called B based on the query from Step 2. You Query B and filter only original T1 rows (where t =1). In each group, you return the first row's prev and prevkey values, and last row's nxt and nxtkey values. Instead of just using a window partition clause, a window frame specification is used to define the minimal frame with the desired row to reduce I/O against the spool.
 

 Her er koden, der implementerer dette trin:
 
SELECT keycol AS keycol1, val AS val1, MAX (prev) OVER(PARTITION BY grp ORDER BY prev DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS mxprev, MAX (prevkey) OVER(PARTITION BY grp ORDER BY prev DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS mxprevkey, MAX (nxt) OVER(PARTITION BY grp ORDER BY nxt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) AS mxnxt, MAX (nxtkey) OVER(PARTITION BY grp ORDER BY nxt ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) AS mxnxtkeyFROM BWHERE t =1;
 

 Denne kode genererer følgende output:
 
keycol1 val1 mxprev mxprevkey mxnxt mxnxtkey----------- ----------- ----------- ----------- ----------- -----------2 1 NULL NULL 2 11 1 NULL NULL 2 15 5 3 4 7 33 3 3 4 7 34 3 3 4 7 36 8 7 3 11 68 16 13 8 17 97 13 13 8 17 99 18 17 9 19 1010 20 19 10 NULL NULL11 21 19 10 NULL NULL
 

 In Step 4 you define a CTE called C based on the query from Step 3. You query C to compute keycol2 and val2 based on the closest match.
 

 Her er koden, der implementerer dette trin:
 
SELECT keycol1, val1, CASE WHEN ABS(val1 - mxprev) <=ISNULL(ABS(val1 - mxnxt), mxprev) THEN mxprevkey ELSE mxnxtkey END AS keycol2, CASE WHEN ABS(val1 - mxprev) <=ISNULL(ABS(val1 - mxnxt), mxprev) THEN mxprev ELSE mxnxt END AS val2FROM C;
 

 Denne kode genererer følgende output:
 
keycol1 val1 keycol2 val2----------- ----------- ----------- -----------2 1 1 21 1 1 25 5 4 33 3 4 34 3 4 36 8 3 78 16 9 177 13 8 139 18 9 1710 20 10 1911 21 10 19
 

 In Step 5 you define a CTE called D based on the query from Step 4. You then join D with T1 and T2 to get the other needed columns.
 

 Her er koden, der implementerer dette trin:
 
SELECT D.keycol1, D.val1, D.keycol2, D.val2, SUBSTRING(T1.othercols, 1, 1) AS othercols1, SUBSTRING(T2.othercols, 1, 1) AS othercols2FROM D INNER JOIN dbo.T1 ON T1.keycol =D.keycol1 INNER JOIN dbo.T2 ON T2.keycol =D.keycol2;
 

 The plan for solution 2 by Kamil with supporting indexes is shown in Figure 11.
 

 Figure 11:Plan for solution 2 by Kamil with indexes 
 

 Here are the performance stats for this plan:
 
run time:18.1, CPU:34.4, logical reads:56,736
 

 The plan for solution 2 by Kamil without supporting indexes is shown in Figure 12.
 

 Figure 12:Plan for solution 2 by Kamil without indexes 
 

 Here are the performance stats for this plan:
 
run time:20.3, CPU:38.9, logical reads:59,012
 

 As you can see, the Plan in Figure 12 involves a couple of extra sorts compared to the plan in Figure 1 to order the data for the two queries in the CTE A—one to support the dense rank calculation and the other to support the grouped query. Other than that, the rest of the work is similar in both. In the grand scheme of things, there’s a bit of extra CPU work and consequentially time penalty, but still both queries perform fairly reasonably.
 
Konklusion
 

 This article concludes the series on the closest match challenge. It’s great to see the different creative ideas that Kamil, Alejandro and Radek came up with. Thanks to all of you for sending your solutions!