Dichtstbijzijnde, deel 3

In Closest Match, Part 1, heb ik een T-SQL-uitdaging behandeld die mij werd aangeboden door Karen Ly, een Jr. Fixed Income Analyst bij RBC. De uitdaging omvatte twee tabellen:T1 en T2, elk met een sleutelkolom (keycol), een waarde (val) en enkele andere kolommen (weergegeven met een kolom genaamd othercols). De taak was om voor elke rij van T1 de rij van T2 te matchen waar T2.val het dichtst bij T1.val ligt (het absolute verschil is de laagste laagste), met behulp van de laagste T2.keycol-waarde als een tiebreaker. Ik heb een aantal relationele oplossingen aangedragen en hun prestatiekenmerken besproken. Ik heb je ook uitgedaagd om te proberen een redelijk presterende oplossing te vinden in gevallen waarin je geen ondersteunende indexen mag/kunnen maken. In deel 2 heb ik laten zien hoe dit kan worden bereikt door iteratieve oplossingen te gebruiken. Ik heb verschillende zeer interessante lezeroplossingen gekregen van Kamil Konsno, Alejandro Mesa en Radek Celuch, en die oplossingen staan ​​​​centraal in het artikel van deze maand.

Voorbeeldgegevens

Ter herinnering:ik heb zowel kleine als grote sets voorbeeldgegevens voor u verstrekt om mee te werken. Kleine sets om de validiteit van uw oplossing te controleren en grote sets om de prestaties te controleren. Gebruik de volgende code om de voorbeelddatabase testdb te maken en daarin de voorbeeldtabellen T1 en T2:

-- Voorbeeld dbSET NOCOUNT AAN; IF DB_ID('testdb') IS NULL MAAK DATABASE testdb;GO GEBRUIK testdb;GO -- Voorbeeldtabellen T1 en T2DROP TABEL INDIEN BESTAAT dbo.T1, dbo.T2; MAAK TABEL dbo.T1( keycol INT NOT NULL IDENTITY CONSTRAINT PK_T1 PRIMARY KEY, val INT NOT NULL, othercols BINARY(100) NOT NULL CONSTRAINT DFT_T1_col1 DEFAULT (0xAA)); MAAK TABEL dbo.T2( keycol INT NOT NULL IDENTITY CONSTRAINT PK_T2 PRIMAIRE SLEUTEL, val INT NOT NULL, othercols BINARY(100) NOT NULL CONSTRAINT DFT_T2_col1 DEFAULT(0xBB));

Gebruik de volgende code om de tabellen te vullen met kleine sets voorbeeldgegevens:

-- Vul T1 en T2 in met kleine sets voorbeeldgegevens TRUNCATE TABLE dbo.T1;TRUNCATE TABLE dbo.T2; INSERT INTO dbo.T1 (val) WAARDEN(1),(1),(3),(3),(5),(8),(13),(16),(18),(20),( 21); INSERT INTO dbo.T2 (val) WAARDEN(2),(2),(7),(3),(3),(11),(11),(13),(17),(19);

Ik zal de kleine sets voorbeeldgegevens gebruiken bij het beschrijven van de logica van de verschillende oplossingen en tussenliggende resultatensets leveren voor de stappen van de oplossingen.

Gebruik de volgende code om de helperfunctie GetNums . te maken en om de tabellen te vullen met grote sets voorbeeldgegevens:

-- Helperfunctie om een ​​reeks gehele getallen te genereren DROP FUNCTIE INDIEN BESTAAT dbo.GetNums;GO CREATE OR WIJZIG FUNCTIE dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNS TABLEASRETURN WITH L0 AS (SELECT c FROM (SELECT) 1 UNION ALL SELECTEER 1) ALS D(c)), L1 AS (SELECTEER 1 ALS c VAN L0 ALS EEN CROSS JOIN L0 AS B), L2 AS (SELECTEER 1 AS c VAN L1 ALS EEN CROSS JOIN L1 AS B), L3 AS (SELECTEER 1 ALS c VAN L2 ALS EEN CROSS JOIN L2 AS B), L4 AS (SELECTEER 1 AS c VAN L3 ALS EEN CROSS JOIN L3 AS B), L5 AS (SELECTEER 1 AS c VAN L4 ALS EEN CROSS JOIN L4 AS B), Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum VAN L5) SELECT TOP(@high - @low + 1) @low + rownum - 1 AS n FROM Nums ORDER BY rownum;GO -- Vul T1 en T2 in met grote sets voorbeeldgegevensDECLARE @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) SELECTEER ABS(CHECKSUM(NEWID())) % @maxvalT1 + 1 AS val FROM dbo.GetNums(1, @numrowsT1) AS Nums; INSERT INTO dbo.T2 WITH(TABLOCK) (val) SELECTEER ABS(CHECKSUM(NEWID())) % @maxvalT2 + 1 AS val FROM dbo.GetNums(1, @numrowsT2) AS Nums;

Als u uw oplossing wilt testen met ondersteunende indexen, gebruikt u de volgende code om die indexen te maken:

CREATE INDEX idx_val_key OP 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 DESC, keycol) INCLUDE(overigecols);

Als u uw oplossing wilt testen zonder indexen te ondersteunen, gebruikt u de volgende code om die indexen te verwijderen:

DROP INDEX INDIEN BESTAAT idx_val_key OP dbo.T1;DROP INDEX INDIEN BESTAAT idx_val_key OP dbo.T2;DROP INDEX INDIEN BESTAAT idx_valD_key OP dbo.T2;

Oplossing 1 door Kamil Kosno – Een tijdelijke tabel gebruiken

Kamil Kosno heeft er een paar ingediend - twee met zijn originele ideeën en twee variaties op de oplossingen van Alejandro en Radek. De eerste oplossing van Kamil maakt gebruik van een geïndexeerde tijdelijke tabel. Vaak is het zo dat zelfs als je geen ondersteunende indexen op de originele tabellen mag maken, je wel met tijdelijke tabellen mag werken, en met tijdelijke tabellen kun je altijd je eigen indexen maken.

Hier is de code van de volledige oplossing:

DROP TABEL INDIEN BESTAAT #T2; SELECTEER MIN(keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val; MAAK UNIEKE INDEX idx_nc_val_key OP #T2(val, keycol); WITH bestvals AS( SELECT keycol AS keycol1, val AS val1 ABS(val - nxt)  

 In stap 1 van de oplossing slaat u de minimale keycol voor elke unieke val op in een tijdelijke tabel met de naam #T2 en maakt u een ondersteunende index op (val, keycol). Hier is de code die deze stap implementeert:
 
DROP TABEL INDIEN BESTAAT #T2; SELECTEER MIN(keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val; MAAK UNIEKE INDEX idx_nc_val_key OP #T2(val, keycol); SELECTEER * VAN #T2;
 

 De tijdelijke tabel is gevuld met de volgende gegevens:
 
keycol val----------- ----------1 24 33 76 118 139 1710 19
 

 In stap 2 van de oplossing past u het volgende toe:
 

 Bereken voor elke rij in T1 de vorige en nxt-waarden van #T2. Bereken prev als de maximale waarde in #T2 die kleiner is dan of gelijk is aan de waarde in T1. Bereken nxt als de minimale val in #T2 die groter is dan of gelijk is aan val in T1.
 

 Gebruik een CASE-expressie om val2 te berekenen op basis van de volgende logica:
 
 
 Als prev of nxt null is, retourneert u de eerste niet-null van de twee, of NULL als beide NULL zijn. 
 
 Als het absolute verschil tussen val en prev kleiner is dan het absolute verschil tussen val en nxt, retourneer prev. 
 
 Als het absolute verschil tussen val en nxt kleiner is dan het absolute verschil tussen val en prv, retourneer nxt. 
 
 Anders, als nxt kleiner is dan vorige, retourneer nxt, anders retour vorige. 
 
 

 Hier is de code die deze stap implementeert:
 
SELECT keycol AS keycol1, val AS val1, othercols AS othercols1, CASE WHEN (prev + nxt IS NULL) THEN COALESCE(prev, nxt) WHEN ABS(val - prev)  

 Deze code genereert de volgende uitvoer:
 
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
 

 In stap 3 van de oplossing definieert u een CTE met de naam bestvals op basis van de query uit stap 2. Vervolgens voegt u bestvals samen met #T2 om de sleutels te krijgen, en voegt u het resultaat samen met T2 om de rest van de gegevens (othercols) te krijgen.
 

 Hier is de code die deze stap implementeert:
 
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 INNERLIJKE JOIN dbo.T2 ON T2.keycol =tempT2.keycol;
 

 Het plan voor oplossing 1 door Kamil met ondersteunende indexen wordt getoond in figuur 1.
 

 Figuur 1:Plan voor oplossing 1 door Kamil met indexen 
 

 De eerste tak van het plan groepeert en aggregeert de gegevens van T2 en schrijft het resultaat naar de tijdelijke tabel #T2. Merk op dat deze tak een vooraf besteld Stream Aggregate-algoritme gebruikt dat vertrouwt op een geordende scan van de index idx_valD_key op T2.
 

 Dit zijn de prestatiestatistieken voor dit abonnement:
 
runtime (sec):5.55, CPU (sec):16.6, logische waarden:6.687.172
 

 Het plan voor oplossing 1 door Kamil zonder ondersteunende indexen wordt getoond in figuur 2.
 

 Figuur 2:Plan voor oplossing 1 door Kamil zonder indexen 
 

 Het belangrijkste verschil tussen dit plan en het vorige is dat de eerste tak van het plan, die het groeperings- en aggregatiegedeelte in stap 1 afhandelt, deze keer de vooraf bestelde gegevens niet uit een ondersteunende index kan halen, dus het haalt het ongeordend uit de geclusterde index op T2 en gebruikt vervolgens een Hash Aggregate-algoritme.
 

 Dit zijn de prestatiestatistieken voor dit abonnement:
 
runtime:6.44, CPU:19.3, logische waarden:6.688.277
 
Oplossing door Alejandro Mesa – Met behulp van de laatste niet-null-techniek
 

 De oplossing van Alejandro gebruikt de laatste niet-null-techniek die hier wordt beschreven.
 

 Hier is de code van de volledige oplossing (hier geleverd zonder andere kolommen terug te geven):
 
MET R1 AS( SELECT keycol, val, tid, MAX( CASE WHEN tid =0 THEN CAST(val AS binair(4)) + CAST(keycol AS binair(4)) END ) OVER( ORDER BY val, tid , keycol RIJEN TUSSEN ONGEBONDEN PRECEDING EN 1 PRECEDING ) 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 RIJEN TUSSEN 1 VOLGENDE EN ONGEBONDEN VOLGENDE) AS above_binstr FROM (SELECT keycol, val, 1 AS tid FROM dbo.T1 UNION ALL SELECTEER MIN(keycol) AS keycol, val, 0 AS tid FROM 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_keycol) AS key hieronder -(tove_T2_keycol, below_T2_T2SELECT_key) AS key ) <=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 R3 END AS val2F> 

 In stap 1 van de oplossing verenigt u de rijen van T1 (toewijzen van een resultaatkolom genaamd tid aan 1) met de rijen van T2 (toewijzen van tid =0), en definieert u een afgeleide tabel met de naam T op basis van het resultaat. Met behulp van de laatste niet-null-techniek, gebaseerd op de volgorde van val, tid, keycol, haalt u voor elke huidige rij de waarden van de laatste tid =0 rij op, samengevoegd in een binaire kolom genaamd below_binstr. Op dezelfde manier haalt u de waarden van de volgende tid =0 rij op, samengevoegd in een binaire kolom met de naam above_binstr.
 

 Hier is de code die deze stap implementeert:
 
SELECT keycol, val, tid, MAX( CASE WHEN tid =0 THEN CAST(val AS binair(4)) + CAST(keycol AS binair(4)) END ) OVER( ORDER BY val, tid, keycol RIJEN TUSSEN UNBOUNDED PRECEDING EN 1 PRECEDING ) 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 RIJEN TUSSEN 1 VOLGENDE EN ONGEBONDEN VOLGENDE) AS above_binstrFROM (SELECT keycol, val, 1 AS tid FROM dbo.T1 UNION ALL SELECT MIN(keycol) AS keycol, val, 0 AS tid FROM dbo.T2 GROUP BY val) AS T;
 

 Deze code genereert de volgende uitvoer:
 
keycol val tid below_binstr above_binstr----------- ----------- ----------- --------- --------- ------------------1 1 1 NULL 0x00000002000000012 1 1 NULL 0x00000002000000011 2 0 NULL 0x00000003000000044 3 0 0x0000000200000001 0x00000007000000003 3 1 0x0000000300000004 0x00000007000000034 3 1 0x0000000300000004 0x00000007000000035 5 1 0x0000000300000004 0x00000007000000033 7 0 0x0000000300000004 0x0000000B000000066 8 1 0x0000000700000003 0x0000000B000000066 11 0 0x0000000700000003 0x0000000D000000088 13 0 0x0000000B00000006 0x00000011000000097 13000000 1 0x000000000000 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
 

 In stap 2 van de oplossing definieert u een CTE met de naam R1 op basis van de query uit stap 1. U voert een query uit op R1, filtert alleen rijen waar tid =1, en extraheert de individuele waarden uit de aaneengeschakelde binaire strings.
 

 Hier is de code die deze stap implementeert:
 
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;
 

 Deze code genereert de volgende uitvoer:
 
keycol val onder_T2_val onder_T2_keycol boven_T2_val boven_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 NULL11 21 19 10 NULL NULL
 

 In stap 3 van de oplossing definieert u een CTE met de naam R2 op basis van de query uit stap 2. Vervolgens berekent u de volgende resultaatkolommen:
 
 
 below_T2_val:de eerste niet-null tussen below_T2_val en above_T2_val 
 
 below_T2_keycol:de eerste niet-null tussen below_T2_keycol en above_T2_keycol 
 
 above_T2_val:de eerste niet-null tussen above_T2_val en below_T2_val 
 
 above_T2_keycol:de eerste niet-null tussen above_T2_keycol en below_T2_keycol 
 
 

 Hier is de code die deze stap implementeert:
 
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 CO_T2_val) AS above CO_T2_keycol) 

 Deze code genereert de volgende uitvoer:
 
keycol val onder_T2_val onder_T2_keycol boven_T2_val boven_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 1011 21 19 10 19 10
 

 In stap 4 van de oplossing definieert u een CTE met de naam R3 op basis van de query uit stap 3. U retourneert keycol met een alias als T1_keycol en met een alias als T1_val. Bereken de resultaatkolom T2_keycol als:als het absolute verschil tussen val en below_T2_val kleiner is dan of gelijk is aan het absolute verschil tussen above_T2_val en val, retourneer je below_T2_keycol, anders above_T2_keycol. Bereken de resultaatkolom T2_val als:als het absolute verschil tussen val en below_T2_val kleiner is dan of gelijk is aan het absolute verschil tussen above_T2_val en val, retourneer dan below_T2_val, anders above_T2_val.
 

 Hier is de code die deze stap implementeert:
 
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 - below_T2_val) <=ABS_val - below_T2_val) val) THEN below_T2_val ELSE above_T2_val END AS val2FROM R3;
 

 Het plan voor de oplossing van Alejandro met ondersteunende indexen wordt getoond in figuur 3.
 

 Figuur 3:Plan voor oplossing door Alejandro met indexen 
 

 Dit zijn de prestatiestatistieken voor dit abonnement:
 
runtime:7.8, CPU:12.6, logische uitlezingen:35.886
 

 Het plan voor de oplossing van Alejandro zonder ondersteunende indexen wordt getoond in figuur 4.
 

 Figuur 4:Plan voor oplossing door Alejandro zonder indexen 
 

 Dit zijn de prestatiestatistieken voor dit abonnement:
 
runtime:8.19, CPU:14.8, logische uitlezingen:37.091
 

 Merk op dat er in de eerste twee takken van het plan in figuur 4 twee soorten zijn voorafgaand aan de operator Samenvoegen (aaneenschakelen) vanwege het ontbreken van ondersteunende indexen. Die soorten zijn niet nodig in het plan in figuur 3, omdat de gegevens vooraf worden opgehaald uit de ondersteunende indexen.
 
Kamils ​​variatie op de oplossing van Alejandro
 

 In deze oplossing vertrouwde Kamil ook op de laatste niet-null-techniek. Hier is de code van de volledige oplossing:
 
WITH all_vals AS( SELECT keycol, val FROM dbo.T1 UNION ALL SELECT DISTINCT NULL, val FROM dbo.T2),bereiken AS( SELECT keycol, val, MAX(CASE WHEN keycol IS NULL THEN val END) OVER (ORDER BY val, keycol RIJEN TUSSEN ONGEBONDEN VOORAFGAANDE EN 1 PRECEDING) AS prev, MIN(CASE WHEN WHEN keycol IS NULL THEN val END) OVER (ORDER BY val, keycol RIJEN TUSSEN 1 VOLGENDE EN ONGEBONDEN VOLGENDE) AS nxt FROM all_vals),matched_vals AS SELECT keycol AS keycol1, val AS val1, CASE WHEN ABS(val - prev) <=ISNULL(ABS(val - nxt), prev) THEN prev ELSE nxt END AS val2 UIT bereiken WAAR keycol NIET NULL is)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 DOOR keycol) AS rn VAN dbo.T2 ) AS T2 OP T2.val =M.val2 EN rn =1 BINNENVERBINDING dbo.T1 OP T1.keycol =keycol1;
 

 In stap 1 van de oplossing definieert u CTE's genaamd all_vals en ranges, waarbij u de laatste niet-null-techniek gebruikt om voor elke waarde in T1 (waar keycol niet NULL is) bereiken van onder (prev) en boven (nxt) waarden van T2 ( waarbij keycol null is).
 

 Hier is de code die deze stap implementeert:
 
WITH all_vals AS( SELECT keycol, val FROM dbo.T1 UNION ALL SELECT DISTINCT NULL, val FROM dbo.T2),bereiken AS( SELECT keycol, val, MAX(CASE WHEN keycol IS NULL THEN val END) OVER (ORDER BY val, keycol RIJEN TUSSEN UNBOUNDED VOORAFGAANDE EN 1 PRECEDING) AS prev, MIN(CASE WHEN WHEN keycol IS NULL THEN val END) OVER (ORDER BY val, keycol RIJEN TUSSEN 1 VOLGENDE EN ONGEBONDEN VOLGENDE) AS nxt FROM all_vals)SELECTEER * UIT bereiken;
 

 Deze code genereert de volgende uitvoer:
 
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 13 13 178 16 13 17NULL 17 13 199 18 17 19NULL 19 17 NULL10 20 19 NULL11 21 19 NULL
 

 In stap 2 van de oplossing zoekt u de CTE-bereiken op en filtert u alleen rijen waar keycol niet null is. U retourneert de kolommen keycol en val van T1 als respectievelijk keycol1 en val1. Vervolgens, tussen prev en nxt, retourneert u het dichtst bij val1 als val2.
 

 Hier is de code die deze stap implementeert:
 
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 NIET NULL;
 

 Deze code genereert de volgende uitvoer:
 
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
 

 In stap 3 van de oplossing definieert u een CTE met de naam matched_vals op basis van de query uit stap 2. U definieert ook een afgeleide tabel met de naam T2 waarin u met behulp van gepartitioneerde rijnummers de tiebreaklogica voor de rijen uit dbo.T2 afhandelt. Vervolgens voegt u matched_vals, de CTE T2 en de tabel T1 samen om de uiteindelijke matchlogica af te handelen.
 

 Hier is de code die deze stap implementeert:
 
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 (PARTITIE OP val ORDER OP keycol) ALS rn VAN dbo.T2 ) AS T2 OP T2.val =M.val2 EN rn =1 INNERLIJKE JOIN dbo.T1 OP T1.keycol =keycol1;
 

 Het plan voor Kamil's variatie op de oplossing van Alejandro met ondersteunende indexen wordt getoond in figuur 5.
 

 Figuur 5:Plan voor Kamils ​​variatie op Alejandro's oplossing met indexen 
 

 Dit zijn de prestatiestatistieken voor dit abonnement:
 
runtime:11.5, CPU:18.3, logische uitlezingen:59.218
 

 Het plan voor Kamil's variatie op de oplossing van Alejandro zonder ondersteunende indexen wordt getoond in figuur 6.
 

 Figuur 6:plan voor Kamils ​​variatie op Alejandro's oplossing zonder indexen 
 

 Dit zijn de prestatiestatistieken voor dit abonnement:
 
runtime:12.6, CPU:23.5, logische uitlezingen:61.432
 

 Net als bij de plannen voor de oplossing van Alejandro, vereist het plan in Afbeelding 5 ook in dit geval geen expliciete sorteringen voordat de operator Samenvoegen (aaneenschakeling) wordt toegepast, aangezien de gegevens vooraf worden opgehaald uit ondersteunende indexen, en het plan in Afbeelding 6 doet dat wel. vereisen expliciete sorteringen omdat er geen ondersteunende indexen zijn.
 
Oplossing door Radek Celuch – Intervallen gebruiken
 

 Radek kwam met een simpel en mooi idee. Voor elke afzonderlijke waarde in T2.val berekent u een interval dat het waardenbereik van T1.val vertegenwoordigt dat overeenkomt met de huidige T2.val. 
 

 Hier is de code van de volledige oplossing:
 
MET 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 ON T1.val TUSSEN T2.low EN T2.hoog;
 

 In stap 1 van de oplossing vraagt ​​u T2 op en berekent u rijnummers (roep de kolom rn aan), gepartitioneerd op val en geordend op keycol. Op basis van deze query definieert u een CTE met de naam Pre1. Vervolgens voert u een query uit op Pre1 en filtert u alleen de rijen waarin rn =1. In dezelfde query, met behulp van LAG en LEAD, retourneert u voor elke rij de waarde van de val-kolom van de vorige rij (noem deze prev) en van de volgende rij ( noem het de volgende).
 

 Hier is de code die deze stap implementeert:
 
MET Pre1 AS( SELECT keycol, val, othercols, ROW_NUMBER() OVER(PARTITION BY val ORDER BY keycol) AS 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;
 

 Deze code genereert de volgende uitvoer:
 
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
 

 In stap 2 van de oplossing definieert u een CTE met de naam Pre2 op basis van de query uit stap 1. U voert een query uit op Pre2 en berekent voor elke rij een interval [laag, hoog] waar val uit T1 zou vallen. Hier zijn de berekeningen voor laag en hoog:
 
 
 laag =ISNULL(val – (val – vorige) / 2 + (1 – (val – vorige) % 2), 0) 
 
 hoog =ISNULL(val + (volgende – val) / 2, 2147483647) 
 
 

 De mod 2-controle bij het berekenen van de ondergrens wordt gebruikt om te voldoen aan de lagere T2.val-vereiste, en het rijnummerfilter wordt gebruikt om te voldoen aan de lagere T2.keycol-vereiste. De waarden 0 en 2147483647 worden gebruikt als uiterste onder- en bovengrenzen.
 

 Hier is de code die deze stap implementeert:
 
SELECT keycol, val, othercols, ISNULL(val - (val - vorige) / 2 + (1 - (val - vorige) % 2), 0) AS low, ISNULL(val + (volgende - val) / 2 , 2147483647) AS highFROM Pre2;
 

 Deze code genereert de volgende uitvoer:
 
keycol val overigecols laag hoog------- ---- ---------- ---- -----------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
 

 In stap 3 van de oplossing definieert u een CTE met de naam T2 op basis van de query uit stap 2. Vervolgens voegt u de tabel T1 samen met de CTE T2 overeenkomende rijen op basis van val van T1 binnen het interval [laag, hoog] in T2.
 

 Hier is de code die deze stap implementeert:
 
SELECTEER 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 TUSSEN T2.low EN T2.high;
 

 Het plan voor Radeks oplossing met ondersteunende indexen wordt getoond in figuur 7. 
 

 Figuur 7:Plan voor oplossing door Radek met indexen 
 

 Dit zijn de prestatiestatistieken voor dit abonnement:
 
runtime:10.6, CPU:7.63, logische uitlezingen:3.193.125
 

 Het plan voor Radeks oplossing zonder ondersteunende indexen wordt getoond in figuur 8. 
 

 Figuur 8:plan voor oplossing door Radek zonder indexen 
 

 Dit zijn de prestatiestatistieken voor dit abonnement:
 
runtime:18.1, CPU:27.4, logische uitlezingen:5.827.360
 

 Hier is het prestatieverschil tussen de twee plannen behoorlijk aanzienlijk. Het plan in figuur 8 vereist een voorlopige sortering vóór de berekening van de rijnummers, wat het plan in figuur 7 niet doet. Wat nog belangrijker is, om elk interval te matchen met de respectieve rijen van T1, creëert het plan in Figuur 8 een Index Spool in wezen als een alternatief voor de ontbrekende index, terwijl het plan in Figuur 7 gewoon de bestaande index idx_val_key op T1 gebruikt. Dat is de belangrijkste reden voor de grote verschillen tussen alle prestatiemetingen. Toch zijn de prestaties zonder ondersteunende indexen redelijk.
 
Kamils ​​variatie op Radeks oplossing
 

 Kamil bedacht een variatie op de oplossing van Radek. Hier is de code van de volledige oplossing:
 
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),bereiken 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) AS 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 
 
 

 Here’s the code implementing this step:
 
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;
 

 This code generates the following 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.
 

 Here’s the code implementing this step:
 
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;
 

 This code generates the following 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.
 

 Here’s the code implementing this step:
 
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;
 

 This code generates the following 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.
 

 Here’s the code implementing this step:
 
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;
 

 This code generates the following 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.
 

 Here’s the code implementing this step:
 
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.
 
Conclusie
 

 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!