Närmaste match, del 3

I Closest Match, del 1, täckte jag en T-SQL-utmaning som jag fick av Karen Ly, en Jr. Fixed Income Analyst på RBC. Utmaningen involverade två tabeller - T1 och T2, var och en med en nyckelkolumn (keycol), ett värde (val) och några andra kolumner (representerade med en kolumn som kallas othercols). Uppgiften var att till varje rad från T1 matcha raden från T2 där T2.val är närmast T1.val (den absoluta skillnaden är lägst lägst), med det lägsta T2.keycol-värdet som tiebreaker. Jag gav ett par relationella lösningar och diskuterade deras prestationsegenskaper. Jag utmanade dig också att försöka hitta en rimligt fungerande lösning i de fall du inte får/kan skapa stödjande index. I del 2 visade jag hur detta kan uppnås genom att använda iterativa lösningar. Jag fick flera mycket intressanta läsarlösningar från Kamil Konsno, Alejandro Mesa och Radek Celuch, och dessa lösningar är i fokus i denna månads artikel.

Exempeldata

Som en påminnelse tillhandahöll jag både små och stora uppsättningar exempeldata för dig att arbeta med. Små uppsättningar för att kontrollera giltigheten av din lösning och stora uppsättningar för att kontrollera dess prestanda. Använd följande kod för att skapa exempeldatabasen testdb och i den exempeltabellerna T1 och T2:

-- Exempel på dbSET NOCOUNT ON; OM DB_ID('testdb') ÄR NULL SKAPA DATABAS testdb;GO ANVÄND testdb;GO -- Exempeltabeller T1 och T2DROP TABELL OM FINNS dbo.T1, dbo.T2; CREATE TABLE dbo.T1( keycol INT INTE NULL IDENTITETSBEGRÄNSNING PK_T1 PRIMÄRNYCKEL, val INT INTE NULL, othercols BINARY(100) NOT NULL CONSTRAINT DFT_T1_col1 DEFAULT(0xAA)); SKAPA TABELL dbo.T2( nyckelkol INT INTE NULL IDENTITETSBEGRÄNSNING PK_T2 PRIMÄRNYCKEL, val INT INTE NULL, andra kolum BINARY(100) INTE NULL BEGRÄNSNING DFT_T2_col1 DEFAULT(0xBB));

Använd följande kod för att fylla i tabellerna med små uppsättningar exempeldata:

-- Fyll T1 och T2 med små uppsättningar exempeldata TRUNCATE TABLE dbo.T1;TRUNCATE TABLE dbo.T2; INSERT INTO dbo.T1 (val) VÄRDEN(1),(1),(3),(3),(5),(8),(13),(16),(18),(20),( 21); INSERT INTO dbo.T2 (val) VÄRDEN(2),(2),(7),(3),(3),(11),(11),(13),(17),(19);

Jag kommer att använda de små uppsättningarna exempeldata när jag beskriver logiken för de olika lösningarna och tillhandahåller mellanliggande resultatuppsättningar för stegen i lösningarna.

Använd följande kod för att skapa hjälpfunktionen GetNums och för att fylla tabellerna med stora uppsättningar exempeldata:

-- Hjälpfunktion för att generera en sekvens av heltalDROP-FUNKTION OM FINNS dbo.GetNums;GO SKAPA ELLER ÄNDRA FUNKTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURER TABLEASRETURN MED L0 AS (VÄLJ c FRÅN (SELECT c FROM) 1 FÖRENADE ALLA VÄLJ 1) SOM D(c)), L1 SOM (VÄLJ 1 SOM c FRÅN L0 SOM EN KORSAJNING L0 SOM B), L2 SOM (VÄLJ 1 SOM c FRÅN L1 SOM EN KORSSFOGA L1 SOM B), L3 AS (VÄLJ 1 AS c FRÅN L2 SOM EN KORSKOPPLING L2 AS B), L4 AS (VÄLJ 1 AS c FRÅN L3 SOM EN KORSKOPPLING L3 SOM B), L5 AS (VÄLJ 1 AS c FRÅN L4 SOM EN KORSJOIN L4 SOM 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 -- Fyll i T1 och T2 med stora uppsättningar exempeldataDECLARE @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 vill testa din lösning med stödjande index, använd följande kod för att skapa dessa index:

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

När du vill testa din lösning utan att stödja index, använd följande kod för att ta bort dessa index:

SLÄPP INDEX OM FINNS idx_val_key PÅ dbo.T1;SLIP INDEX OM FINNS idx_val_key PÅ dbo.T2;SLIPPA INDEX OM FINNS idx_valD_key PÅ dbo.T2;

Lösning 1 av Kamil Kosno – Använda en tillfällig tabell

Kamil Kosno skickade in några - två med sina ursprungliga idéer och två varianter av Alejandros och Radeks lösningar. Kamils ​​första lösning använder en indexerad temporär tabell. Ofta är det så att även om du inte får skapa stödjande index på de ursprungliga tabellerna, så får du arbeta med temporära tabeller, och med temporära tabeller kan du alltid skapa dina egna index.

Här är den fullständiga lösningens kod:

SLIPTA TABELL OM FINNS #T2; SELECT MIN(keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val; SKAPA UNIKT INDEX idx_nc_val_key PÅ #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 steg 1 av lösningen lagrar du minsta nyckelkolumn för varje unik val i en temporär tabell som heter #T2, och skapar ett stödjande index på (val, nyckelkol). Här är koden som implementerar detta steg:
 
SLIPTA TABELL OM FINNS #T2; SELECT MIN(keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val; SKAPA UNIKT INDEX idx_nc_val_key PÅ #T2(val, keycol); VÄLJ * FRÅN #T2;
 

 Den tillfälliga tabellen är fylld med följande data:
 
keycol val----------- ----------1 24 33 76 118 139 1710 19
 

 I steg 2 av lösningen tillämpar du följande:
 

 Beräkna prev och nxt värden från #T2 för varje rad i T1. Beräkna prev som det maximala värdet i #T2 som är mindre än eller lika med värdet i T1. Beräkna nxt som minimivärdet i #T2 som är större än eller lika med valet i T1.
 

 Använd ett CASE-uttryck för att beräkna val2 baserat på följande logik:
 
 
 När prev eller nxt är null, returnera den första nonnull av de två, eller NULL om båda är NULL. 
 
 När den absoluta skillnaden mellan val och prev är mindre än den absoluta skillnaden mellan val och nxt, returnera prev. 
 
 När om den absoluta skillnaden mellan val och nxt är mindre än den absoluta skillnaden mellan val och prv, returnera nxt. 
 
 Annars, om nxt är mindre än prev, returnera nxt, annars returnera föregående. 
 
 

 Här är koden som implementerar detta steg:
 
SELECT keycol AS keycol1, val AS val1, othercols AS othercols1, CASE WHEN (prev + nxt IS NULL) THEN COALESCE(prev, nxt) WHEN ABS(val - prev)  

 Denna kod genererar följande utdata:
 
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 steg 3 av lösningen definierar du en CTE som kallas bestvals baserat på frågan från steg 2. Du går sedan ihop bestvals med #T2 för att få nycklarna, och sammanfogar resultatet med T2 för att få resten av data (othercols).
 

 Här är koden som implementerar detta steg:
 
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 för lösning 1 av Kamil med stödjande index visas i figur 1.
 

 Figur 1:Plan för lösning 1 av Kamil med index 
 

 Den första grenen av planen grupperar och aggregerar data från T2 och skriver resultatet till den temporära tabellen #T2. Observera att den här grenen använder en förbeställd Stream Aggregate-algoritm som förlitar sig på en beställd genomsökning av indexet idx_valD_key på T2.
 

 Här är resultatstatistiken för denna plan:
 
körtid (sek):5,55, CPU (sek):16,6, logiska läsningar:6 687 172
 

 Planen för lösning 1 av Kamil utan stödjande index visas i figur 2.
 

 Figur 2:Plan för lösning 1 av Kamil utan index 
 

 Huvudskillnaden mellan den här planen och den föregående är att den första grenen av planen, som hanterar grupperings- och aggregeringsdelen i steg 1, denna gång inte kan hämta data som förbeställts från ett stödjande index, så den drar den oordnad från den klustrade index på T2 och använder sedan en Hash Aggregate-algoritm.
 

 Här är resultatstatistiken för denna plan:
 
körtid:6,44, CPU:19,3, logiska läsningar:6 688 277
 
Lösning av Alejandro Mesa – Använder senaste icke-null-teknik
 

 Alejandros lösning använder den sista icke-null-tekniken som beskrivs här.
 

 Här är den fullständiga lösningens kod (tillhandahålls här utan att returnera andra kolor):
 
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 RADER MELLAN 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 RADER MELLAN 1 FÖLJANDE OCH OBEGRÄNSAD FÖLJANDE ) AS above_binstr FRÅN ( VÄLJ keycol, val, 1 AS tid FRÅN dbo.T1 UNION ALLA VÄLJ MIN(keycol) AS keycol, val, 0 AS tid FRÅN 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 int) 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_key2_SELECT) ASW_COL. ) <=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;val END AS 

 I steg 1 av lösningen förenar du raderna från T1 (tilldelar en resultatkolumn som kallas tid till 1) med raderna från T2 (tilldelar tid =0), och definierar en härledd tabell som heter T baserat på resultatet. Genom att använda den sista icke-null-tekniken, baserat på ordningen val, tid, keycol, för varje aktuell rad, hämtar du den sista tid =0 radens värden sammanlänkade i en binär kolumn som heter below_binstr. På samma sätt hämtar du nästa tid =0 rads värden sammanlänkade i en binär kolumn som heter ovan_binstr.
 

 Här är koden som implementerar detta steg:
 
SELECT keycol, val, tid, MAX( CASE WHEN tid =0 THEN CAST(val AS binär(4)) + CAST(keycol AS binär(4)) END ) OVER( ORDNING EFTER val, tid, keycol RADER MELLAN OBEGRÄNSAD FÖREGÅENDE OCH 1 FÖREGÅENDE ) AS below_binstr, MIN( CASE WHEN tid =0 THEN CAST(val AS binary(4)) + CAST(keycol AS binary(4)) END ) OVER( ORDER BY val, tid, keycol RADER MELLAN 1 FÖLJANDE OCH OBEGRÄNSAD FÖLJANDE ) SOM ovan_binstrFROM ( VÄLJ keycol, val, 1 AS tid FROM dbo.T1 UNION ALLA VÄLJ MIN(keycol) AS keycol, val, 0 AS tid FROM dbo.T2 GROUP BY val ) AS T;
 

 Denna kod genererar följande utdata:
 
keycol val tid below_binstr above_binstr------------------------------------------------- ---------- ------------------ 1 1 1 NULL 0x00000002000000012 1 1 NULL 0x00000002000000011 2 0 NULL 0x00000003000000044 3 0 0x0000000200000001 0x0000000007000000033 3 1 0x00000000000000000044 0x00000000000000 0001 0x00000000070000000333 3 1 0x00000000000000000044 0x00000000000000 0001 0x00000000070000000333 3 1 0x00000000000000000044 0x0000000000000000 0001 0x00000000070000000333 3 1 0x0000000000000000004400000000000000000000011 0x000000070000000333 3 1 0x0000000000000000004400000000000000000001 0x0000000300000004 0x00000007000000035 5 1 0x0000000300000004 0x00000007000000033 7 0 0x0000000300000004 0x0000000B000000066 8 1 0x0000000700000003 0x0000000B000000066 11 0 0x0000000700000003 0x0000000D000000088 13 0 0x0000000B00000006 0x00000011000000097 13 1 0x0000000D000000 08 0x00000011000000098 16 1 0x0000000D00000008 0x00000011000000099 17 0 0x0000000D00000008 0x000000130000000A9 18 1 0x0000001100000009 0x000000130000000A10 19 0 0x0000001100000009 NULL10 20 1 0x000000130000000A NULL11 21 1 0x000000130000000A NULL
 

 I steg 2 av lösningen definierar du en CTE som kallas R1 baserat på frågan från steg 1. Du frågar R1, filtrerar endast rader där tid =1 och extraherar de individuella värdena från de sammanlänkade binära strängarna.
 

 Här är koden som implementerar detta steg:
 
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;
 

 Denna kod genererar följande utdata:
 
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 steg 3 av lösningen definierar du en CTE som kallas R2 baserat på frågan från steg 2. Du beräknar sedan följande resultatkolumner:
 
 
 under_T2_val:den första icke-nullen mellan under_T2_val och ovan_T2_val 
 
 below_T2_keycol:den första icke-nullen mellan below_T2_keycol och above_T2_keycol 
 
 ovan_T2_val:den första icke-nullen mellan ovan_T2_val och under_T2_val 
 
 above_T2_keycol:den första icke-nullen mellan above_T2_keycol och below_T2_keycol 
 
 

 Här är koden som implementerar detta steg:
 
VÄLJ 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_2key below, COALESCE(above_T2_val) AS above_ALES_2_2 key; 

 Denna kod genererar följande utdata:
 
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 10 19 10 19 10 19 

 I steg 4 av lösningen definierar du en CTE som kallas R3 baserat på frågan från steg 3. Du returnerar keycol alias som T1_keycol och val aliased som T1_val. Beräkna resultatkolumnen T2_keycol som:om den absoluta skillnaden mellan val och under_T2_val är mindre än eller lika med den absoluta skillnaden mellan ovan_T2_val och val, returnera under_T2_keycol, annars ovan_T2_keycol. Beräkna resultatkolumnen T2_val som:om den absoluta skillnaden mellan val och under_T2_val är mindre än eller lika med den absoluta skillnaden mellan ovan_T2_val och val, returnera under_T2_val, annars ovan_T2_val.
 

 Här är koden som implementerar detta steg:
 
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) <=_T2_val) -ve_T2_val val) THEN below_T2_val ELSE above_T2_val END AS val2FROM R3;
 

 Planen för Alejandros lösning med stödjande index visas i figur 3.
 

 Figur 3:Plan för lösning av Alejandro med index 
 

 Här är resultatstatistiken för denna plan:
 
körtid:7,8, CPU:12,6, logiska läsningar:35 886
 

 Planen för Alejandros lösning utan stödjande index visas i figur 4.
 

 Figur 4:Plan för lösning av Alejandro utan index 
 

 Här är resultatstatistiken för denna plan:
 
körtid:8,19, CPU:14,8, logiska läsningar:37 091
 

 Lägg märke till att i de två första grenarna av planen i figur 4 finns det två sorters före operatören Merge Join (Concatenation) på grund av bristen på stödjande index. Dessa sorter behövs inte i planen i figur 3 eftersom data hämtas förbeställt från de stödjande indexen.
 
Kamils ​​variant av Alejandros lösning
 

 I denna lösning förlitade sig Kamil också på den sista icke-null-tekniken. Här är den fullständiga lösningens kod:
 
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 RADER MELLAN OBEGRÄNSAD FÖREGÅENDE OCH 1 FÖREGÅENDE) SOM föregående, MIN(CASE WHEN keycol IS NULL THEN val END) ÖVER (ORDER BY val, keycol RADER MELLAN 1 FÖLJANDE OCH OBEGRÄNSADE FÖLJANDE) AS_nxt 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 FROM intervall 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 ORDER BY keycol) SOM rn FRÅN dbo.T2 ) AS T2 ON T2.val =M.val2 OCH rn =1 INNER JOIN dbo.T1 ON T1.keycol =keycol1;
 

 I steg 1 av lösningen definierar du CTE:er som kallas all_vals och ranges, där du använder den sista icke-null-tekniken för att identifiera för varje värde i T1 (där keycol inte är NULL) intervall med under (prev) och över (nxt) värden från T2 ( där keycol är null).
 

 Här är koden som implementerar detta steg:
 
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 RADER MELLAN OBEGRÄNSAD FÖREGÅENDE OCH 1 FÖREGÅENDE) SOM föregående, MIN(CASE WHEN keycol IS NULL THEN val END) ÖVER (ORDER BY val, keycol RADER MELLAN 1 FÖLJANDE OCH OBEGRÄNSAD FÖLJANDE) * alla_nxts SELECTs FROM;
 

 Denna kod genererar följande utdata:
 
keycol val prev nxt------------ ---------- ------------------ ---------- -1 1 NULL 22 1 NULL 2NULL 2 NULL 3NULL 3 2 73 3 3 74 3 3 75 5 3 7NULL 7 3 116 8 7 11NULL 11 7 13NULL 13 11 177 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 20 19 NULL11 21 19 NULL
 

 I steg 2 av lösningen frågar du CTE-intervallen och filtrerar endast rader där keycol inte är null. Du returnerar kolumnerna keycol och val från T1 som keycol1 respektive val1. Sedan, mellan prev och nxt, returnerar du närmast val1 som val2.
 

 Här är koden som implementerar detta steg:
 
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;
 

 Denna kod genererar följande utdata:
 
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 steg 3 av lösningen definierar du en CTE som heter matched_vals baserat på frågan från steg 2. Du definierar även en härledd tabell som heter T2 där du med hjälp av partitionerade radnummer hanterar tiebreaking-logiken för raderna från dbo.T2. Du kopplar sedan ihop matched_vals, CTE T2 och tabellen T1 för att hantera den slutliga matchningslogiken.
 

 Här är koden som implementerar detta steg:
 
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 ( VÄLJ * , ROW_NUMBER() OVER (PARTITION BY val ORDER BY keycol) SOM rn FRÅN dbo.T2 ) AS T2 ON T2.val =M.val2 OCH rn =1 INNER JOIN dbo.T1 ON T1.keycol =keycol1;
 

 Planen för Kamils ​​variant av Alejandros lösning med stödjande index visas i figur 5.
 

 Figur 5:Plan för Kamils ​​variant av Alejandros lösning med index 
 

 Här är resultatstatistiken för denna plan:
 
körtid:11,5, CPU:18,3, logiska läsningar:59 218
 

 Planen för Kamils ​​variant av Alejandros lösning utan stödjande index visas i figur 6.
 

 Figur 6:Plan för Kamils ​​variant av Alejandros lösning utan index 
 

 Här är resultatstatistiken för denna plan:
 
körtid:12,6, CPU:23,5, logiska läsningar:61 432
 

 I likhet med planerna för Alejandros lösning kräver inte planen i figur 5 explicit sortering innan operatören Merge Join (sammankoppling) används eftersom data hämtas förbeställd från stödjande index, och planen i figur 6 gör det. kräver explicit sortering eftersom det inte finns några stödjande index.
 
Lösning av Radek Celuch – Använda intervaller
 

 Radek kom på en enkel och vacker idé. För varje distinkt värde i T2.val beräknar du ett intervall som representerar intervallet av värden från T1.val som skulle matcha det aktuella T2.val. 
 

 Här är den fullständiga lösningens kod:
 
MED Pre1 AS( SELECT keycol, val, othercols, ROW_NUMBER() OVER(PARTITION BY val ORDER BY keycol) AS rn FROM 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 MELLAN T2.låg OCH T2.high;
 

 I steg 1 av lösningen frågar du T2 och beräknar radnummer (anropar kolumnen rn), partitionerat efter val och ordnat efter keycol. Du definierar en CTE som heter Pre1 baserat på denna fråga. Du frågar sedan Pre1 och filtrerar endast raderna där rn =1. I samma fråga, med hjälp av LAG och LEAD, returnerar du för varje rad värdet på valkolumnen från föregående rad (kalla den prev) och från nästa rad ( kalla det nästa).
 

 Här är koden som implementerar detta steg:
 
MED Pre1 AS( SELECT keycol, val, othercols, ROW_NUMBER() OVER(PARTITION BY val ORDER BY keycol) SOM rn FROM 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;
 

 Denna kod genererar följande utdata:
 
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 steg 2 av lösningen definierar du en CTE som kallas Pre2 baserat på frågan från steg 1. Du frågar Pre2 och beräknar för varje rad ett intervall [lågt, högt] där val från T1 skulle falla in. Här är beräkningarna för låg och hög:
 
 
 låg =ISNULL(val – (val – prev) / 2 + (1 – (val – prev) % 2), 0) 
 
 hög =ISNULL(val + (nästa – val) / 2, 2147483647) 
 
 

 Mod 2-kontrollen för att beräkna den nedre gränsen används för att uppfylla det lägre T2.val-kravet, och radnummerfiltret används för att uppfylla det lägre T2.keycol-kravet. Värdena 0 och 2147483647 används som extrema nedre och övre gränser.
 

 Här är koden som implementerar detta steg:
 
SELECT keycol, val, othercols, ISNULL(val - (val - prev) / 2 + (1 - (val - prev) % 2), 0) AS low, ISNULL(val + (next - val) / 2 , 2147483647) SÅ HÖGT FROM Pre2;
 

 Denna kod genererar följande utdata:
 
keycol val othercols låg hög------- ---- ---------- ---- -------------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 steg 3 av lösningen definierar du en CTE som kallas T2 baserat på frågan från steg 2. Du kopplar sedan ihop tabellen T1 med CTE T2 matchande rader baserat på val från T1 som ligger inom intervallet [låg, hög] i T2.
 

 Här är koden som implementerar detta steg:
 
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 ON T1.val MELLAN T2.low AND T2.high;
 

 Planen för Radeks lösning med stödjande index visas i figur 7. 
 

 Figur 7:Plan för lösning av Radek med index 
 

 Här är resultatstatistiken för denna plan:
 
körtid:10,6, CPU:7,63, logiska läsningar:3 193 125
 

 Planen för Radeks lösning utan stödjande index visas i figur 8. 
 

 Figur 8:Plan för lösning av Radek utan index 
 

 Här är resultatstatistiken för denna plan:
 
körtid:18,1, CPU:27,4, logiska läsningar:5 827 360
 

 Här är prestandaskillnaden mellan de två planerna ganska betydande. Planen i figur 8 kräver en preliminär sortering före beräkningen av radnumren, vilket planen i figur 7 inte gör. Ännu viktigare, för att matcha varje intervall med respektive rad från T1, skapar planen i figur 8 en indexspole i huvudsak som ett alternativ till det saknade indexet, medan planen i figur 7 helt enkelt använder det befintliga indexet idx_val_key på T1. Det är huvudorsaken till de stora skillnaderna mellan alla resultatmått. Ändå är prestandan utan stödjande index rimlig.
 
Kamils ​​variant av Radeks lösning
 

 Kamil kom med en variant på Radeks lösning. Här är den fullständiga lösningens kod:
 
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),bästa matchar 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 FROM ranges 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 
 
 

 Här är koden som implementerar detta steg:
 
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;
 

 Denna kod genererar följande utdata:
 
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.
 

 Här är koden som implementerar detta steg:
 
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;
 

 Denna kod genererar följande utdata:
 
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.
 

 Här är koden som implementerar detta steg:
 
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;
 

 Denna kod genererar följande utdata:
 
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.
 

 Här är koden som implementerar detta steg:
 
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;
 

 Denna kod genererar följande utdata:
 
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.
 

 Här är koden som implementerar detta steg:
 
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.
 
Slutsats
 

 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!