Database
 sql >> Database >  >> RDS >> Database

Partita più ravvicinata, parte 3

In Closest Match, parte 1, ho trattato una sfida T-SQL che mi è stata fornita da Karen Ly, analista di reddito fisso Jr. presso RBC. La sfida riguardava due tabelle:T1 e T2, ciascuna con una colonna chiave (keycol), un valore (val) e alcune altre colonne (rappresentate con una colonna chiamata othercols). Il compito era abbinare a ciascuna riga di T1 la riga di T2 in cui T2.val è più vicino a T1.val (la differenza assoluta è la più bassa più bassa), utilizzando il valore T2.keycol più basso come spareggio. Ho fornito un paio di soluzioni relazionali e discusso le loro caratteristiche prestazionali. Ti ho anche sfidato a cercare di trovare una soluzione ragionevolmente performante nei casi in cui non sei autorizzato/in grado di creare indici di supporto. Nella parte 2, ho dimostrato come ciò può essere ottenuto utilizzando soluzioni iterative. Ho ricevuto diverse soluzioni per i lettori molto interessanti da Kamil Konsno, Alejandro Mesa e Radek Celuch, e queste soluzioni sono al centro dell'articolo di questo mese.

Dati di esempio

Come promemoria, ho fornito piccoli e grandi set di dati di esempio con cui lavorare. Piccoli set per verificare la validità della vostra soluzione e grandi set per verificarne le prestazioni. Utilizzare il codice seguente per creare il database di esempio testdb e al suo interno le tabelle di esempio T1 e T2:

-- Esempio dbSET NOCOUNT ON; IF DB_ID('testdb') IS NULL CREATE DATABASE testdb;GO USE testdb;GO -- Tabelle di esempio T1 e T2DROP TABLE IF EXISTS dbo.T1, dbo.T2; CREATE TABLE 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)); CREATE TABLE dbo.T2( keycol INT NOT NULL IDENTITY CONSTRAINT PK_T2 PRIMARY KEY, val INT NOT NULL, othercols BINARY(100) NOT NULL CONSTRAINT DFT_T2_col1 DEFAULT(0xBB));

Utilizzare il codice seguente per popolare le tabelle con piccoli set di dati di esempio:

-- Popolare T1 e T2 con piccoli set di dati campione 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);

Userò piccoli set di dati campione per descrivere la logica delle diverse soluzioni e fornire set di risultati intermedi per i passaggi delle soluzioni.

Utilizzare il codice seguente per creare la funzione di supporto GetNums e per popolare le tabelle con grandi insiemi di dati di esempio:

-- Funzione di supporto per generare una sequenza di interiDROP FUNCTION IF EXISTS dbo.GetNums;GO CREATE OR ALTER FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RESTITUISCE TABLEASRETURN CON L0 AS (SELECT c FROM (SELECT 1 UNION ALL SELECT 1) AS D(c)), L1 AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B), L2 AS (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B), L3 AS (SELEZIONA 1 AS c DA L2 COME UN CROSS JOIN L2 COME B), L4 AS (SELEZIONA 1 AS c DA L3 COME UN CROSS JOIN L3 COME B), L5 AS (SELEZIONA 1 AS c DA L4 COME UN 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 ORDINE PER rownum;GO -- Popolare T1 e T2 con grandi set di dati campione DECLARE @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;

Quando vuoi testare la tua soluzione con indici di supporto, usa il codice seguente per creare quegli indici:

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 DESC, keycol) INCLUDE(altre colonne);

Quando vuoi testare la tua soluzione senza supportare gli indici, usa il codice seguente per rimuovere quegli indici:

DROP INDEX SE ESISTE idx_val_key SU dbo.T1;DROP INDEX SE ESISTE idx_val_key SU dbo.T2;DROP INDEX SE ESISTE idx_valD_key SU dbo.T2;

Soluzione 1 di Kamil Kosno – Utilizzo di una tabella temporanea

Kamil Kosno ne ha presentati alcuni:due con le sue idee originali e due variazioni sulle soluzioni di Alejandro e Radek. La prima soluzione di Kamil utilizza una tabella temporanea indicizzata. Spesso capita che anche se non ti è permesso creare indici di supporto sulle tabelle originali, ti è permesso lavorare con tabelle temporanee e con le tabelle temporanee puoi sempre creare i tuoi indici.

Ecco il codice completo della soluzione:

TABELLA A CADUTA SE ESISTE #T2; SELECT MIN(keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val; CREA INDICE UNICO idx_nc_val_key ON #T2(val, keycol); WITH 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)  

 Nel passaggio 1 della soluzione memorizzi il keycol minimo per ogni val univoco in una tabella temporanea denominata #T2 e crei un indice di supporto su (val, keycol). Ecco il codice che implementa questo passaggio:
 
TABELLA A CADUTA SE ESISTE #T2; SELECT MIN(keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val; CREA INDICE UNICO idx_nc_val_key ON #T2(val, keycol); SELEZIONA * DA #T2;
 

 La tabella temporanea viene popolata con i seguenti dati:
 
keycol val----------- ----------1 24 33 76 118 139 1710 19
 

 Nel passaggio 2 della soluzione applichi quanto segue:
 

 Per ogni riga in T1 calcola i valori prev e nxt da #T2. Calcola prev come valore massimo in #T2 inferiore o uguale a val in T1. Calcola nxt come valore minimo in #T2 maggiore o uguale a val in T1.
 

 Utilizzare un'espressione CASE per calcolare val2 in base alla logica seguente:
 
     
  •  Quando prev o nxt è null, restituisce il primo non null dei due o NULL se entrambi sono NULL. 
    • 
 
  •  Quando la differenza assoluta tra val e prev è minore della differenza assoluta tra val e nxt, restituisce prev. 
    • 
 
  •  Quando se la differenza assoluta tra val e nxt è minore della differenza assoluta tra val e prv, restituire nxt. 
    • 
 
  •  Altrimenti, se nxt è minore di prev, restituisce nxt, altrimenti restituisce prev. 
    • 
 

 

 Ecco il codice che implementa questo passaggio:
 
SELECT keycol AS keycol1, val AS val1, othercols AS othercols1, CASE WHEN (prev + nxt IS NULL) THEN COALESCE(prev, nxt) WHEN ABS(val - prev)  

 Questo codice genera il seguente 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
 

 Nel passaggio 3 della soluzione, definisci un CTE chiamato bestvals in base alla query del passaggio 2. Quindi unisci bestvals con #T2 per ottenere le chiavi e unisci il risultato con T2 per ottenere il resto dei dati (othercols).
 

 Ecco il codice che implementa questo passaggio:
 
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;
 

 Il piano per la soluzione 1 di Kamil con gli indici di supporto sono mostrati nella Figura 1.
 

 Figura 1:Piano per la soluzione 1 di Kamil con indici 
 

 Il primo ramo del piano raggruppa e aggrega i dati di T2 e scrive il risultato nella tabella temporanea #T2. Si noti che questo ramo utilizza un algoritmo Stream Aggregate preordinato che si basa su una scansione ordinata dell'indice idx_valD_key su T2.
 

 Ecco le statistiche sul rendimento di questo piano:
 
tempo di esecuzione (sec):5,55, CPU (sec):16,6, letture logiche:6.687.172
 

 Il piano per la soluzione 1 di Kamil senza indici di supporto è mostrato nella Figura 2.
 

 Figura 2:Piano per la soluzione 1 di Kamil senza indici 
 

 La principale differenza tra questo piano e il precedente è che il primo ramo del piano, che gestisce la parte di raggruppamento e aggregazione nel passaggio 1, questa volta non può estrarre i dati preordinati da un indice di supporto, quindi li estrae non ordinati dal cluster index su T2 e quindi utilizza un algoritmo Hash Aggregate.
 

 Ecco le statistiche sul rendimento di questo piano:
 
tempo di esecuzione:6.44, CPU:19.3, letture logiche:6.688.277
 
Soluzione di Alejandro Mesa – Utilizzo dell'ultima tecnica non nulla
 

 La soluzione di Alejandro utilizza l'ultima tecnica non nulla descritta qui.
 

 Ecco il codice completo della soluzione (fornito qui senza restituire othercols):
 
CON R1 AS( SELECT keycol, val, tid, MAX( CASE WHEN tid =0 THEN CAST(val AS binary(4)) + CAST(keycol AS binary(4)) END ) OVER( ORDER BY val, tid , keycol ROWS BETWEEN UNBOUNDED PRECEDING E 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 RIGHE TRA 1 SEGUENTE E UNBOUNDED FOLLOWING ) AS above_binstr FROM ( 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 ),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 sotto_T2_val, COALESCE(sotto_T2_keycol, sopra_T2_keycol) AS sotto_T2_keycol, COALESCE(sopra_T2_val, sotto_T2_val) AS sopra_T2_val, COALESCE(sopra_T2_keycol, sotto_T2_keycol) AS sopra_T2_keycol FROM R2)SELECT keycol AS keycol1, val AS val1 - CASE WHEN ABS(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(above_T2_val - val) THEN below_T2_val ELSE above_T2_val END AS val2DA R3;
 

 Nel passaggio 1 della soluzione, unisci le righe di T1 (assegnando una colonna di risultati denominata tid a 1) con le righe di T2 (assegnando tid =0) e definisci una tabella derivata denominata T in base al risultato. Utilizzando l'ultima tecnica non nulla, basata sull'ordine di val, tid, keycol, per ogni riga corrente, si recuperano i valori dell'ultima riga tid =0 concatenati in una colonna binaria denominata below_binstr. Allo stesso modo, recuperi i valori della riga successiva tid =0 concatenati in una colonna binaria chiamata above_binstr.
 

 Ecco il codice che implementa questo passaggio:
 
SELECT keycol, val, tid, MAX( CASE WHEN tid =0 THEN CAST(val AS binary(4)) + CAST(keycol AS binary(4)) END ) OVER( ORDER BY val, tid, keycol ROWS BETWEEN UNBOUNDED PRECEDING AND 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 ROWS BETWEEN 1 FOLLOWING AND UNBOUNDED FOLLOWING ) 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;
 

 Questo codice genera il seguente output:
 
keycol val tid below_binstr above_binstr----------- ----------- ----------- --------- --------- ------------------ 1 1 1 NULL 0x0000000000000012 1 1 NULL 0x000000000000000011 2 0 NULL 0x00000003000000044 3 0 0x0000000200000001 0x0000000000000033 3 1 0x0000000004 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 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
 

 Nel passaggio 2 della soluzione definisci un CTE chiamato R1 in base alla query del passaggio 1. interroghi R1, filtri solo le righe in cui tid =1 ed estrai i singoli valori dalle stringhe binarie concatenate.
 

 Ecco il codice che implementa questo passaggio:
 
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;
 

 Questo codice genera il seguente output:
 
keycol val sotto_T2_val sotto_T2_keycol sopra_T2_val sopra_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
 

 Nel passaggio 3 della soluzione definisci un CTE chiamato R2 in base alla query del passaggio 2. Quindi calcola le seguenti colonne di risultati:
 
     
  •  sotto_T2_val:il primo valore non nullo tra sotto_T2_val e sopra_T2_val 
    • 
 
  •  sotto_T2_keycol:il primo non null tra sotto_T2_keycol e sopra_T2_keycol 
    • 
 
  •  above_T2_val:il primo non null tra above_T2_val e below_T2_val 
    • 
 
  •  above_T2_keycol:il primo non null tra above_T2_keycol e below_T2_keycol 
    • 
 

 

 Ecco il codice che implementa questo passaggio:
 
SELECT keycol, val, COALESCE(sotto_T2_val, sopra_T2_val) AS sotto_T2_val, COALESCE(sotto_T2_keycol, sopra_T2_keycol) AS sotto_T2_keycol, COALESCE(sopra_T2_val, sotto_T2_val) AS sopra_T2_val, COALESCE(sopra_T2_keycol, sotto_T2_keycol) AS above_T2_keyFROM 

 Questo codice genera il seguente output:
 
keycol val sotto_T2_val sotto_T2_keycol sopra_T2_val sopra_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
 

 Nel passaggio 4 della soluzione si definisce un CTE chiamato R3 in base alla query del passaggio 3. Si restituisce keycol alias come T1_keycol e val alias come T1_val. Calcola la colonna dei risultati T2_keycol come:se la differenza assoluta tra val e sotto_T2_val è minore o uguale alla differenza assoluta tra sopra_T2_val e val, ritorna sotto_T2_keycol, altrimenti sopra_T2_keycol. Calcola la colonna dei risultati T2_val come:se la differenza assoluta tra val e sotto_T2_val è minore o uguale alla differenza assoluta tra sopra_T2_val e val, ritorna sotto_T2_val, altrimenti sopra_T2_val.
 

 Ecco il codice che implementa questo passaggio:
 
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(above_T2_val - val) THEN sotto_T2_val ELSE sopra_T2_val END AS val2DA R3;
 

 Il piano per la soluzione di Alejandro con indici di supporto è mostrato nella Figura 3.
 

 Figura 3:Piano per la soluzione di Alejandro con indici 
 

 Ecco le statistiche sul rendimento di questo piano:
 
tempo di esecuzione:7.8, CPU:12.6, letture logiche:35.886
 

 Il piano per la soluzione di Alejandro senza indici di supporto è mostrato nella Figura 4.
 

 Figura 4:Piano per la soluzione di Alejandro senza indici 
 

 Ecco le statistiche sul rendimento di questo piano:
 
tempo di esecuzione:8.19, CPU:14.8, letture logiche:37.091
 

 Si noti che nei primi due rami del piano nella Figura 4 sono presenti due tipi prima dell'operatore Merge Join (Concatenation) a causa della mancanza di indici di supporto. Tali ordinamenti non sono necessari nel piano in Figura 3 poiché i dati vengono recuperati preordinati dagli indici di supporto.
 
Variante di Kamil sulla soluzione di Alejandro
 

 In questa soluzione, Kamil ha fatto affidamento anche sull'ultima tecnica non nulla. Ecco il codice completo della soluzione:
 
CON all_vals AS( SELECT keycol, val FROM dbo.T1 UNION ALL SELECT DISTINCT NULL, val FROM dbo.T2), intervalli AS( SELECT keycol, val, MAX(CASE WHEN keycol IS NULL THEN val END) OVER (ORDINE PER val, keycol RIGA TRA UNBOUNDED PRECEDENTE E 1 PRECEDENTE) COME precedente, MIN(CASE WHEN keycol IS NULL THEN val END) OVER (ORDINE PER val, keycol RIGA TRA 1 SEGUENTE E UNBOUNDED SEGUENTE) 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 FROM range WHERE keycol NON È 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) AS rn FROM dbo.T2 ) AS T2 ON T2.val =M.val2 AND rn =1 INNER JOIN dbo.T1 ON T1.keycol =keycol1;
 

 Nel passaggio 1 della soluzione si definiscono CTE denominate all_vals e intervalli, in cui si utilizza l'ultima tecnica non nulla per identificare per ogni valore in T1 (dove keycol non è NULL) intervalli di valori inferiori (prec.) e superiori (nxt) da T2 ( dove keycol è null).
 

 Ecco il codice che implementa questo passaggio:
 
CON all_vals AS( SELECT keycol, val FROM dbo.T1 UNION ALL SELECT DISTINCT NULL, val FROM dbo.T2), intervalli AS( SELECT keycol, val, MAX(CASE WHEN keycol IS NULL THEN val END) OVER (ORDINE PER val, keycol RIGHE TRA UNBOUNDED PRECEDENTE E 1 PRECEDENTE) COME prec, MIN(CASE WHEN keycol IS NULL THEN val END) OVER (ORDINA PER val, keycol RIGA TRA 1 SEGUENTE E UNBOUNDED SEGUENTE) AS nxt FROM all_vals)SELECT * FROM ranges;
 

 Questo codice genera il seguente 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 7 NULL 7 3 116 8 7 11 NULL 11 7 13 NULL 13 11 177 13 13 178 16 13 17 NULL 17 13 199 19 NULL 20 19 NULL11 21 19 NULL
 

 Nel passaggio 2 della soluzione si interrogano gli intervalli CTE e si filtrano solo le righe in cui keycol non è null. Restituisci le colonne keycol e val da T1 rispettivamente come keycol1 e val1. Quindi, tra prev e nxt, restituisci il più vicino a val1 come val2.
 

 Ecco il codice che implementa questo passaggio:
 
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 NON È NULL;
 

 Questo codice genera il seguente 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
 

 Nel passaggio 3 della soluzione si definisce un CTE chiamato valori_corrispondenti in base alla query del passaggio 2. Si definisce anche una tabella derivata denominata T2 in cui utilizzando i numeri di riga partizionati si gestisce la logica di tiebreaking per le righe da dbo.T2. Quindi unisci matched_vals, CTE T2 e tabella T1 per gestire la logica di corrispondenza finale.
 

 Ecco il codice che implementa questo passaggio:
 
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;
 

 Il piano per la variazione di Kamil sulla soluzione di Alejandro con indici di supporto è mostrato nella Figura 5.
 

 Figura 5:Piano per la variazione di Kamil sulla soluzione di Alejandro con indici 
 

 Ecco le statistiche sul rendimento di questo piano:
 
tempo di esecuzione:11.5, CPU:18.3, letture logiche:59.218
 

 Il piano per la variazione di Kamil sulla soluzione di Alejandro senza indici di supporto è mostrato nella Figura 6.
 

 Figura 6:piano per la variazione di Kamil sulla soluzione di Alejandro senza indici 
 

 Ecco le statistiche sul rendimento di questo piano:
 
tempo di esecuzione:12,6, CPU:23,5, letture logiche:61.432
 

 Simile ai piani per la soluzione di Alejandro, anche in questo caso il piano in Figura 5 non richiede ordinamenti espliciti prima di applicare l'operatore Merge Join (concatenazione) poiché i dati vengono recuperati preordinati dagli indici di supporto e il piano in Figura 6 lo fa richiedono ordinamenti espliciti poiché non ci sono indici di supporto.
 
Soluzione di Radek Celuch – Utilizzo degli intervalli
 

 Radek ha avuto un'idea semplice e bella. Per ogni valore distinto in T2.val si calcola un intervallo che rappresenta l'intervallo di valori da T1.val che corrisponderebbe all'attuale T2.val. 
 

 Ecco il codice completo della soluzione:
 
CON 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 basso, ISNULL(val + (successivo - val) / 2, 2147483647) AS alto DA 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 othercols2DA dbo.T1 INNER JOIN T2 ON T1.val TRA T2.low AND T2.alto;
 

 Nel passaggio 1 della soluzione si interroga T2 e si calcolano i numeri di riga (chiamare la colonna rn), partizionati per val e ordinati per keycol. Definisci un CTE chiamato Pre1 in base a questa query. Quindi interroghi Pre1 e filtri solo le righe dove rn =1. Nella stessa query, utilizzando LAG e LEAD, restituisci per ogni riga il valore della colonna val dalla riga precedente (chiamala prev) e dalla riga successiva ( chiamalo dopo).
 

 Ecco il codice che implementa questo passaggio:
 
CON 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 nextDA PRE1WHERE rn =1;
 

 Questo codice genera il seguente 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
 

 Nel passaggio 2 della soluzione si definisce un CTE chiamato Pre2 in base alla query del passaggio 1. Si interroga Pre2 e si calcola per ogni riga un intervallo [basso, alto] in cui rientrerebbe val da T1. Ecco i calcoli per basso e alto:
 
     
  •  basso =ISNULL(val – (val – prev) / 2 + (1 – (val – prev) % 2), 0) 
    • 
 
  •  alto =ISNULL(val + (successivo – val) / 2, 2147483647) 
    • 
 

 

 Il controllo mod 2 sul calcolo del limite inferiore viene utilizzato per soddisfare il requisito T2.val inferiore e il filtro del numero di riga viene utilizzato per soddisfare il requisito T2.keycol inferiore. I valori 0 e 2147483647 sono usati come limiti inferiori e superiori estremi.
 

 Ecco il codice che implementa questo passaggio:
 
SELECT keycol, val, othercols, ISNULL(val - (val - prev) / 2 + (1 - (val - prev) % 2), 0) AS low, ISNULL(val + (next - val) / 2 , 2147483647) COME highFROM Pre2;
 

 Questo codice genera il seguente output:
 
keycol val othercols basso alto------- ---- ---------- ---- -----------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
 

 Nel passaggio 3 della soluzione definisci un CTE chiamato T2 in base alla query del passaggio 2. Quindi unisci la tabella T1 con le righe corrispondenti CTE T2 in base al fatto che val da T1 si trova all'interno dell'intervallo [basso, alto] in T2.
 

 Ecco il codice che implementa questo passaggio:
 
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 SU T1.val TRA T2.low E T2.high;
 

 Il piano per la soluzione di Radek con indici di supporto è mostrato nella Figura 7. 
 

 Figura 7:Piano per la soluzione di Radek con indici 
 

 Ecco le statistiche sul rendimento di questo piano:
 
tempo di esecuzione:10.6, CPU:7.63, letture logiche:3.193.125
 

 Il piano per la soluzione di Radek senza indici di supporto è mostrato nella Figura 8. 
 

 Figura 8:piano per la soluzione di Radek senza indici 
 

 Ecco le statistiche sul rendimento di questo piano:
 
tempo di esecuzione:18.1, CPU:27.4, letture logiche:5.827.360
 

 Qui la differenza di prestazioni tra i due piani è piuttosto sostanziale. Il piano in Figura 8 richiede un ordinamento preliminare prima del calcolo dei numeri di riga, cosa che il piano in Figura 7 non prevede. Ancora più importante, per far corrispondere ogni intervallo con le rispettive righe di T1, il piano in Figura 8 crea uno spool di indice essenzialmente come alternativa all'indice mancante, mentre il piano in Figura 7 usa semplicemente l'indice esistente idx_val_key su T1. Questo è il motivo principale delle grandi differenze tra tutte le misure di prestazione. Tuttavia, le prestazioni senza il supporto degli indici sono ragionevoli.
 
Variante di Kamil sulla soluzione di Radek
 

 Kamil ha escogitato una variazione sulla soluzione di Radek. Ecco il codice completo della soluzione:
 
CON T2_collapsed AS( SELECT keycol AS keycol2, val AS val2 , ROW_NUMBER() OVER (PARTITION BY val ORDER BY keycol) AS rn FROM dbo.T2), intervalli AS( SELECT keycol2 AS prevkey, val2 AS prevval, LEAD( keycol2) OVER (ORDINE PER val2) AS nxtkey, LEAD(val2) OVER (ORDINE PER val2) AS nxtval DA 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.
 
Conclusione
 

 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!