Najbliższy mecz, część 3

W Closest Match, Part 1, omówiłem wyzwanie T-SQL, które dostarczyła mi Karen Ly, Jr. Fixed Income Analyst w RBC. Wyzwanie obejmowało dwie tabele — T1 i T2, każda z kolumną klucza (keycol), wartością (val) i kilkoma innymi kolumnami (reprezentowanymi przez kolumnę o nazwie othercols). Zadanie polegało na dopasowaniu do każdego wiersza z T1 tego wiersza z T2, gdzie T2.val jest najbliżej T1.val (różnica bezwzględna to najniższa najniższa wartość), używając najniższej wartości T2.keycol jako rozstrzygającej. Przedstawiłem kilka rozwiązań relacyjnych i omówiłem ich charakterystykę działania. Rzuciłem Ci również wyzwanie, abyś spróbował znaleźć rozsądne rozwiązanie w przypadkach, w których nie możesz / nie możesz tworzyć indeksów pomocniczych. W części 2 pokazałem, jak można to osiągnąć, stosując rozwiązania iteracyjne. Od Kamila Konsna, Alejandro Mesy i Radka Celucha dostałem kilka bardzo ciekawych rozwiązań czytelniczych i na tych rozwiązaniach będzie się skupiać artykuł w tym miesiącu.

Przykładowe dane

Przypominam, że udostępniłem do pracy zarówno małe, jak i duże zestawy przykładowych danych. Małe zestawy do sprawdzenia poprawności rozwiązania i duże zestawy do sprawdzenia jego wydajności. Użyj poniższego kodu, aby utworzyć przykładową bazę danych testdb, a w niej przykładowe tabele T1 i T2:

-- Przykładowy dbSET NOCOUNT ON; IF DB_ID('testdb') JEST NULL CREATE DATABASE testdb;GO USE testdb;GO -- Przykładowe tabele T1 i 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, innecols 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, innecols BINARY(100) NOT NULL CONSTRAINT DFT_T2_col1 DEFAULT(0xBB));

Użyj poniższego kodu, aby wypełnić tabele małymi zestawami przykładowych danych:

-- Wypełnij T1 i T2 małymi zestawami danych przykładowych TRUNCATE TABLE dbo.T1;TRUNCATE TABLE dbo.T2; WSTAW W dbo.T1 (val) WARTOŚCI(1),(1),(3),(3),(5),(8),(13),(16),(18),(20),( 21); WSTAW W dbo.T2 (val) WARTOŚCI(2),(2),(7),(3),(3),(11),(11),(13),(17),(19);

Użyję małych zestawów przykładowych danych podczas opisywania logiki różnych rozwiązań i dostarczę pośrednie zestawy wyników dla etapów rozwiązań.

Użyj poniższego kodu, aby utworzyć funkcję pomocniczą GetNums i wypełnić tabele dużymi zestawami przykładowych danych:

-- Funkcja pomocnicza do generowania sekwencji liczb całkowitych FUNKCJA DROP JEŻELI ISTNIEJE dbo.GetNums;GO CREATE OR ALTER FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) ZWRACA TABELĘASRETURN Z L0 AS (SELECT c FROM (SELECT) 1 UNION ALL WYBIERZ 1) JAK D(c)), L1 AS (WYBIERZ 1 JAKO c Z L0 JAKO KRZYŻ DOŁĄCZ L0 JAK B), L2 JAK (WYBIERZ 1 JAKO c Z L1 JAKO KRZYŻ DOŁĄCZ L1 JAK B), L3 AS (WYBIERZ 1 JAKO c Z L2 JAKO KRZYŻ DO L2 JAK B), L4 JAK (WYBIERZ 1 JAKO c Z L3 JAKO KRZYŻ DOŁĄCZ L3 JAK B), L5 AS (WYBIERZ 1 JAKO c Z L4 JAKO POŁĄCZENIE KRZYŻOWE L4 AS B), Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum FROM L5) SELECT TOP(@high - @low + 1) @low + rownum - 1 AS n FROM Nums ORDER BY rownum;GO -- Wypełnij T1 i T2 dużymi zestawami przykładowych danychDECLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =10000000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =10000000; OBCIĄĆ TABELĘ dbo.T1;OBCIĄĆ TABELĘ dbo.T2; INSERT INTO dbo.T1 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT1 + 1 AS val FROM dbo.GetNums(1, @numrowsT1) AS Nums; INSERT INTO dbo.T2 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT2 + 1 AS val FROM dbo.GetNums(1, @numrowsT2) AS Nums;

Jeśli chcesz przetestować swoje rozwiązanie z pomocniczymi indeksami, użyj następującego kodu, aby utworzyć te indeksy:

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) INCLUDE(inne);

Jeśli chcesz przetestować swoje rozwiązanie bez obsługi indeksów, użyj następującego kodu, aby usunąć te indeksy:

DRUP INDEX, JEŚLI ISTNIEJE idx_val_key NA dbo.T1;DROP INDEX, JEŚLI ISTNIEJE idx_val_key NA dbo.T2;DROP INDEX, JEŚLI ISTNIEJE idx_valD_key NA dbo.T2;

Rozwiązanie 1 autorstwa Kamila Kosno – Korzystanie z tabeli tymczasowej

Kamil Kosno przedstawił kilka – dwie ze swoimi oryginalnymi pomysłami i dwie wariacje na temat rozwiązań Alejandro i Radka. Pierwsze rozwiązanie Kamila wykorzystuje indeksowaną tabelę tymczasową. Często jest tak, że nawet jeśli nie możesz tworzyć indeksów pomocniczych w oryginalnych tabelach, możesz pracować z tabelami tymczasowymi, a z tabelami tymczasowymi zawsze możesz tworzyć własne indeksy.

Oto kompletny kod rozwiązania:

UPUŚĆ TABELĘ, JEŚLI ISTNIEJE #T2; SELECT MIN (keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val; UTWÓRZ UNIKALNY INDEKS idx_nc_val_key ON #T2(val, keycol); WITH bestvals AS( SELECT keycol AS keycol1, val AS val1, othercols AS othercols1, CASE WEN (prev + nxt IS NULL) THEN COALESCE(prev, nxt) WHEN ABS(val - prev)  

 W kroku 1 rozwiązania przechowujesz minimalną wartość klucza dla każdej unikatowej wartości w tabeli tymczasowej o nazwie #T2 i tworzysz indeks pomocniczy na (val, keycol). Oto kod implementujący ten krok:
 
UPUŚĆ TABELĘ, JEŚLI ISTNIEJE #T2; SELECT MIN (keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val; UTWÓRZ UNIKALNY INDEKS idx_nc_val_key ON #T2(val, keycol); WYBIERZ * Z #T2;
 

 Tabela tymczasowa jest wypełniona następującymi danymi:
 
wartość klucza----------- ----------1 24 33 76 118 139 1710 19
 

 W kroku 2 rozwiązania zastosuj następujące elementy:
 

 Dla każdego wiersza w T1 oblicz wartości prev i nxt z #T2. Oblicz prev jako maksymalną val w #T2, która jest mniejsza lub równa val w T1. Oblicz nxt jako minimalną wartość w #T2, która jest większa lub równa wartości w T1.
 

 Użyj wyrażenia CASE, aby obliczyć val2 w oparciu o następującą logikę:
 
 
 Gdy prev lub nxt ma wartość NULL, zwróć pierwszą wartość nienull z tych dwóch lub NULL, jeśli oba są NULL. 
 
 Gdy bezwzględna różnica między val i prev jest mniejsza niż bezwzględna różnica między val i nxt, zwróć prev. 
 
 Jeśli bezwzględna różnica między val i nxt jest mniejsza niż bezwzględna różnica między val i prv, zwróć nxt. 
 
 W przeciwnym razie, jeśli nxt jest mniejsze niż prev, zwróć nxt, w przeciwnym razie zwróć prev. 
 
 

 Oto kod implementujący ten krok:
 
SELECT keycol AS keycol1,val AS val1, othercols AS othercols1, CASE WHEN (prev + nxt IS NULL) THEN COALESCE(prev, nxt) WHEN ABS(val - prev)  

 Ten kod generuje następujące dane wyjściowe:
 
keycol1 val1 innecols1 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
 

 W kroku 3 rozwiązania definiujesz CTE o nazwie bestvals na podstawie zapytania z kroku 2. Następnie dołączasz do bestvals z #T2, aby zdobyć klucze i łączysz wynik z T2, aby uzyskać resztę danych (inne).
 

 Oto kod implementujący ten krok:
 
SELECT keycol1, val1, SUBSTRING(innecols1,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 POŁĄCZENIE WEWNĘTRZNE dbo.T2 ON T2.keycol =tempT2.keycol;
 

 Plan rozwiązania 1 autorstwa Kamila z pomocnicze indeksy pokazano na rysunku 1.
 

 Rysunek 1:Plan rozwiązania 1 autorstwa Kamila z indeksami 
 

 Pierwsza gałąź planu grupuje i agreguje dane z T2 i zapisuje wynik do tabeli tymczasowej #T2. Zauważ, że ta gałąź używa zamówionego wcześniej algorytmu Stream Aggregate, który opiera się na uporządkowanym skanowaniu indeksu idx_valD_key w T2.
 

 Oto statystyki wydajności tego planu:
 
czas działania (s):5,55, procesor (s):16,6, odczyty logiczne:6 687 172
 

 Plan rozwiązania 1 Kamila bez indeksów pomocniczych pokazano na rysunku 2.
 

 Rysunek 2:Plan rozwiązania 1 autorstwa Kamila bez indeksów 
 

 Główna różnica między tym planem a poprzednim polega na tym, że pierwsza gałąź planu, która obsługuje część grupowania i agregacji w kroku 1, tym razem nie może pobrać danych zamówionych z góry z indeksu pomocniczego, więc pobiera je nieuporządkowane z klastrowanych indeksuje na T2, a następnie używa algorytmu Hash Aggregate.
 

 Oto statystyki wydajności tego planu:
 
czas działania:6,44, procesor:19,3, odczyty logiczne:6 688 277
 
Rozwiązanie Alejandro Mesy – Użycie ostatniej niezerowej techniki
 

 Rozwiązanie Alejandro wykorzystuje ostatnią niepustą technikę opisaną tutaj.
 

 Oto kompletny kod rozwiązania (dostarczony tutaj bez zwracania innych kolumn):
 
Z 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 POMIĘDZY NIEOGRANICZONYM POSTĘPOWANIEM A 1 POSTĘPOWANIEM ) 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 WIERSZE MIĘDZY 1 NASTĘPNYMI I NIEOGRANICZONYMI NASTĘPUJĄCYMI ) AS above_binstr FROM ( WYBIERZ 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 powyżej_T2_val, CAST(SUBSTRING(powyżej_binstr, 5, 4) AS int) AS powyżej_T2_keycol FROM R1 WHERE tid =1),R3 AS(SELECT keycol,val, COALESCE(poniżej_T2_val, powyżej_T2 _val) AS poniżej_T2_val, COALESCE(poniżej_T2_keycol, powyżej_T2_keycol) AS poniżej_T2_keycol, COALESCE(powyżej_T2_val, poniżej_T2_val) AS powyżej_T2_val, COALESCE(nad_T2_keycol, poniżej_T2_val_val_val_klaw.col powyżej_T2_ROM2_val_val klucz AS ) <=ABS(powyżej_T2_val - val) THEN below_T2_keycol ELSE powyżej_T2_keycol END AS keycol2, PRZYPADEK, KIEDY ABS(val - below_T2_val) <=ABS(above_T2_val - val) THEN below_T2_val ELSE powyżej_T2_pre END R AS; 

 W kroku 1 rozwiązania ujednolicasz wiersze z T1 (przypisywanie kolumny wyników o nazwie tid do 1) z wierszami z T2 (przypisywanie tid =0) i definiujesz tabelę pochodną o nazwie T na podstawie wyniku. Używając ostatniej techniki niezerowej, opartej na kolejności val, tid, keycol, dla każdego bieżącego wiersza, pobierasz wartości ostatniego wiersza tid =0 połączone w binarną kolumnę o nazwie below_binstr. Podobnie, pobierasz wartości następnego wiersza tid =0 połączone w binarną kolumnę o nazwie above_binstr.
 

 Oto kod implementujący ten krok:
 
 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 PRECED I 1 PRECED ) 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 POMIĘDZY 1 PO I NIEOGRANICZONYCH PO ) 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;
 

 Ten kod generuje następujące dane wyjściowe:
 
keycol val tid below_binstr above_binstr----------- ----------- ----------- --------- --------- ------------------1 1 1 NULL 0x00000002000000012 1 1 NULL 0x00000002000000011 2 0 NULL 0x00000003000000044 3 0 0x0000000200000001 0x00000007000000033 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 0x0000000B0000000000D000 000000x0001 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
 W kroku 2 rozwiązania definiujesz CTE o nazwie R1 na podstawie zapytania z kroku 1. Zapytanie R1, filtrujesz tylko wiersze, w których tid =1 i wyodrębniasz poszczególne wartości ze połączonych ciągów binarnych.
 

 Oto kod implementujący ten krok:
 
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 powyżej_T2_val, CAST(SUBSTRING(powyżej_binstr, 5, 4) AS int) AS powyżej_T2_keycolFROM R1WHERE tid =1;
 

 Ten kod generuje następujące dane wyjściowe:
 
wartość klucza poniżej_T2_val poniżej_T2_wartość klucza powyżej_T2_val powyżej_T2_wartość klucza----------- ----------- ------------ ------- -------- ------------ ---------------1 1 PUSTA PUSTE 2 12 1 PUSTE PUSTE 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
 

 W kroku 3 rozwiązania definiujesz CTE o nazwie R2 na podstawie zapytania z kroku 2. Następnie obliczasz następujące kolumny wyników:
 
 
 below_T2_val:pierwsza wartość niezerowa między below_T2_val i above_T2_val 
 
 below_T2_keycol:pierwsza wartość niezerowa między below_T2_keycol i above_T2_keycol 
 
 above_T2_val:pierwsza wartość niezerowa między above_T2_val i below_T2_val 
 
 above_T2_keycol:pierwsza wartość niezerowa między above_T2_keycol i below_T2_keycol 
 
 

 Oto kod implementujący ten krok:
 
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) ASbove_T2_keycol, above_T2_keycol) AS below_T2_keycol, COALESCE(above_T2_val, below_T2_val) ASbove_T2_keyT2_col>col 

 Ten kod generuje następujące dane wyjściowe:
 
wartość klucza poniżej_T2_val poniżej_T2_wartość klucza powyżej_T2_val powyżej_T2_wartość klucza----------- ----------- ------------ ------- -------- ------------ ---------------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
 

 W kroku 4 rozwiązania definiujesz CTE o nazwie R3 na podstawie zapytania z kroku 3. Zwracasz keycol o aliasie T1_keycol i val o aliasie T1_val. Oblicz kolumnę wyników T2_keycol jako:jeśli bezwzględna różnica między wartością val i poniżej_T2_val jest mniejsza lub równa bezwzględnej różnicy między powyżej_T2_val i val, zwróć poniżej_T2_keycol, w przeciwnym razie powyżej_T2_keycol. Oblicz kolumnę wynikową T2_val jako:jeśli bezwzględna różnica między wart a poniżej_T2_val jest mniejsza lub równa bezwzględnej różnicy między powyższą_T2_val a val, zwróć poniżej_T2_val, w przeciwnym razie powyżej_T2_val.
 

 Oto kod implementujący ten krok:
 
WYBIERZ keycol AS keycol1, val AS val1, CASE, GDY ABS(val - below_T2_val) <=ABS(powyżej_T2_val - val) THEN below_T2_keycol ELSE above_T2_keycol END AS keycol2, CASE WHEN ABS(val - below_T2_val) <=ABS(powyżej -_ val) THEN below_T2_val ELSE above_T2_val END AS val2FROM R3;
 

 Plan rozwiązania Alejandro z pomocniczymi indeksami pokazano na rysunku 3.
 

 Rysunek 3:Plan rozwiązania przez Alejandro z indeksami 
 

 Oto statystyki wydajności tego planu:
 
czas działania:7,8, procesor:12,6, odczyty logiczne:35 886
 

 Plan rozwiązania Alejandro bez obsługi indeksów pokazano na rysunku 4.
 

 Rysunek 4:Plan rozwiązania przez Alejandro bez indeksów 
 

 Oto statystyki wydajności tego planu:
 
czas działania:8,19, procesor:14,8, odczyty logiczne:37 091
 

 Zauważ, że w pierwszych dwóch gałęziach planu na rysunku 4 są dwa sortowania przed operatorem Merge Join (Concatenation) ze względu na brak indeksów pomocniczych. Te rodzaje nie są potrzebne w planie na rysunku 3, ponieważ dane są pobierane w przedsprzedaży z indeksów pomocniczych.
 
Wariacja Kamila na temat rozwiązania Alejandro
 

 W tym rozwiązaniu Kamil również oparł się na ostatniej technice nonnull. Oto kompletny kod rozwiązania:
 
WTH all_vals AS( SELECT keycol, val FROM dbo.T1 UNION ALL SELECT DISTINCT NULL, val FROM dbo.T2), zakresy AS( SELECT keycol, val, MAX(CASE WHEN keycol IS NULL THEN val END) OVER (ORDER) WEDŁUG val, keycol WIERSZE POMIĘDZY NIEOGRANICZONYM POSTĘPOWANIEM I 1 POSTĘPOWANIEM) AS prev, MIN (przypadek GDY keycol JEST NULL TO val END) OVER (KOLEJNOŚĆ WEDŁUG val, keycol WIERSZE MIĘDZY 1 NASTĘPNYM I NIEOGRANICZONYM NASTĘPNYM) AS nxt (Asmatched all_vals) SELECT keycol AS keycol1, val AS val1, CASE, GDZIE ABS(val - prev) <=ISNULL(ABS(val - nxt), prev) THEN prev ELSE nxt END AS val2 FROM zakresy GDZIE keycol NIE JEST NULL) SELECT keycol1, val1 SUBSTRING(T1.othercols, 1, 1) AS innecols1, val2, T2.keycol AS keycol2, SUBSTRING(T2.othercols, 1,1) AS innecols2 FROM matched_vals AS M INNER JOIN ( SELECT *, ROW_NUMBER() OVER (PARTITION BY val ZAMÓWIENIE WEDŁUG keycol) AS rn Z dbo.T2 ) AS T2 ON T2.val =M.val2 AND rn =1 POŁĄCZENIE WEWNĘTRZNE dbo.T1 ON T1.keycol =keycol1;
 

 W kroku 1 rozwiązania definiujesz CTE zwane all_vals i zakresami, w których używasz ostatniej techniki niezerowej do identyfikowania dla każdej wartości w T1 (gdzie keycol nie jest NULL) zakresów poniżej (prev) i powyżej (nxt) wartości z T2 ( gdzie keycol ma wartość null).
 

 Oto kod implementujący ten krok:
 
WTH all_vals AS( SELECT keycol, val FROM dbo.T1 UNION ALL SELECT DISTINCT NULL, val FROM dbo.T2), zakresy AS( SELECT keycol, val, MAX(CASE WHEN keycol IS NULL THEN val END) OVER (ORDER) BY val, keycol WIERSZE POMIĘDZY NIEOGRANICZONYM POSTĘPOWANIEM I 1 POSTĘPOWANIEM) AS prev, MIN (przypadek GDY keycol JEST NULL TO val END) OVER (KOLEJNOŚĆ WEDŁUG val, keycol WIERSZE MIĘDZY 1 NASTĘPNYM I NIEOGRANICZONYM NASTĘPNYM) AS nxt) SELECT FROM * all_vals;
 

 Ten kod generuje następujące dane wyjściowe:
 
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 18 17 19 NULL 19 17 NULL10 20 19 NULL11 21 19 NULL
 

 W kroku 2 rozwiązania wysyłasz zapytanie do zakresów CTE i filtrujesz tylko wiersze, w których keycol nie ma wartości NULL. Zwracasz kolumny keycol i val z T1 jako odpowiednio keycol1 i val1. Następnie, pomiędzy prev i nxt, zwracasz najbliższą wartości val1 jako val2.
 

 Oto kod implementujący ten krok:
 
SELECT keycol AS keycol1, val AS val1, CASE, GDY ABS(val - prev) <=ISNULL(ABS(val - nxt), prev) THEN prev ELSE nxt END AS val2FROM zakresyWHERE keycol NIE JEST NULL;
 

 Ten kod generuje następujące dane wyjściowe:
 
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
 

 W kroku 3 rozwiązania definiujesz CTE o nazwie matched_vals na podstawie zapytania z kroku 2. Definiujesz również tabelę pochodną o nazwie T2, w której przy użyciu numerów wierszy podzielonych na partycje obsługujesz logikę rozstrzygania rozstrzygnięć dla wierszy z dbo.T2. Następnie dołączasz matched_vals, CTE T2 i tabelę T1, aby obsłużyć ostateczną logikę dopasowania.
 

 Oto kod implementujący ten krok:
 
SELECT keycol1, val1, SUBSTRING(T1.othercols, 1, 1) AS innecols1, val2, T2.keycol AS keycol2, SUBSTRING(T2.othercols, 1,1) AS innecols2 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;
 

 Plan wariacji Kamila na temat rozwiązania Alejandro wraz z indeksami pomocniczymi pokazano na rysunku 5.
 

 Rysunek 5:Plan wariacji Kamila na temat rozwiązania Alejandro z indeksami 
 

 Oto statystyki wydajności tego planu:
 
czas działania:11,5, procesor:18,3, odczyty logiczne:59 218
 

 Plan wariacji Kamila na temat rozwiązania Alejandro bez pomocniczych indeksów pokazano na rysunku 6.
 

 Rysunek 6:Plan dla wariacji Kamila na temat rozwiązania Alejandro bez indeksów 
 

 Oto statystyki wydajności tego planu:
 
czas działania:12,6, procesor:23,5, odczyty logiczne:61 432
 

 Podobnie jak w przypadku planów rozwiązania Alejandro, również w tym przypadku plan na rysunku 5 nie wymaga jawnego sortowania przed zastosowaniem operatora łączenia łączenia (konkatenacji), ponieważ dane są pobierane w przedsprzedaży z indeksów pomocniczych, a plan na rysunku 6 nie wymaga wymagają jawnego sortowania, ponieważ nie ma pomocniczych indeksów.
 
Rozwiązanie Radka Celucha – Wykorzystanie interwałów
 

 Radek wpadł na prosty i piękny pomysł. Dla każdej odrębnej wartości w T2.val oblicza się przedział reprezentujący zakres wartości z T1.val, który odpowiadałby bieżącej wartości T2.val. 
 

 Oto kompletny kod rozwiązania:
 
With 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 ZŁĄCZE WEWNĘTRZNE T2 NA T1.val MIĘDZY T2.low ORAZ T2.wysoki;
 

 W kroku 1 rozwiązania wykonujesz zapytanie T2 i obliczasz numery wierszy (wywołaj kolumnę rn), podzielone według wartości val i uporządkowane według keycol. Na podstawie tego zapytania definiujesz CTE o nazwie Pre1. Następnie wykonujesz zapytanie Pre1 i filtrujesz tylko wiersze, w których rn =1. W tym samym zapytaniu, używając LAG i LEAD, zwracasz dla każdego wiersza wartość kolumny val z poprzedniego wiersza (nazwij to prev) i z następnego wiersza ( zadzwoń dalej).
 

 Oto kod implementujący ten krok:
 
With 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;
 

 Ten kod generuje następujące dane wyjściowe:
 
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
 

 W kroku 2 rozwiązania definiujesz CTE o nazwie Pre2 na podstawie zapytania z kroku 1. Zapytasz Pre2 i obliczasz dla każdego wiersza przedział [low, high], w którym przypadałaby val z T1. Oto obliczenia dla low i wysoki:
 
 
 niski =ISNULL(val – (val – prev) / 2 + (1 – (val – prev) % 2), 0) 
 
 wysoka =ISNULL(wartość + (następna – wartość) / 2, 2147483647) 
 
 

 Sprawdzenie mod 2 przy obliczaniu dolnej granicy służy do spełnienia dolnego wymogu T2.val, a filtr numerów wierszy służy do spełnienia dolnego wymogu T2.keycol. Wartości 0 i 2147483647 są używane jako skrajne dolne i górne granice.
 

 Oto kod implementujący ten krok:
 
SELECT keycol, val, othercols, ISNULL(val - (val - prev) / 2 + (1 - (val - prev) % 2), 0) AS low, ISNULL(val + (next - val) / 2 , 2147483647) JAK WYSOKI OD Pre2;
 

 Ten kod generuje następujące dane wyjściowe:
 
wartość klucza inne kol. niska wysoka -------- ---- ---------- ---- -----------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
 

 W kroku 3 rozwiązania definiujesz CTE o nazwie T2 na podstawie zapytania z kroku 2. Następnie łączysz tabelę T1 z wierszami pasującymi CTE T2 na podstawie wartości val z T1 mieszczącej się w przedziale [low, high] w T2.
 

 Oto kod implementujący ten krok:
 
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 ) JAKO othercols2FROM dbo.T1 WEWNĘTRZNE ZŁĄCZE T2 NA T1.val MIĘDZY T2.low I T2.high;
 

 Plan rozwiązania Radka wraz z indeksami pomocniczymi pokazano na rysunku 7. 
 

 Rysunek 7:Plan rozwiązania Radka z indeksami 
 

 Oto statystyki wydajności tego planu:
 
czas działania:10,6, procesor:7,63, odczyty logiczne:3,193,125
 

 Plan rozwiązania Radka bez obsługi indeksów pokazano na rysunku 8. 
 

 Rysunek 8:Plan rozwiązania Radka bez indeksów 
 

 Oto statystyki wydajności tego planu:
 
czas działania:18,1, procesor:27,4, odczyty logiczne:5,827,360
 

 Tutaj różnica w wydajności między dwoma planami jest dość znaczna. Plan na rysunku 8 wymaga wstępnego sortowania przed obliczeniem numerów rzędów, czego nie robi plan na rysunku 7. Co ważniejsze, aby dopasować każdy interwał do odpowiednich wierszy z T1, plan na rysunku 8 tworzy szpulę indeksu zasadniczo jako alternatywę dla brakującego indeksu, podczas gdy plan na rysunku 7 po prostu używa istniejącego indeksu idx_val_key na T1. To główny powód dużych różnic we wszystkich miarach wydajności. Mimo to wydajność bez obsługi indeksów jest rozsądna.
 
Wariacja Kamila na temat rozwiązania Radka
 

 Kamil wymyślił wariację na temat rozwiązania Radka. Oto kompletny kod rozwiązania:
 
Z T2_collapsed AS( SELECT keycol AS keycol2, val AS val2 , ROW_NUMBER() OVER (PARTITION BY val ORDER BY keycol) AS rn FROM dbo.T2), zakresy 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), najlepiej pasuje 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) TO prevval ELSE nxtval END AS val2 Z zakresów INNER JOIN dbo.T1 ON prevval <=T1.val AND T1.val  

 Oto własny opis tego rozwiązania autorstwa Kamila:
 

 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. Oto kompletny kod rozwiązania:
 
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 
 
 

 Oto kod implementujący ten krok:
 
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;
 

 Ten kod generuje następujące dane wyjściowe:
 
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.
 

 Oto kod implementujący ten krok:
 
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;
 

 Ten kod generuje następujące dane wyjściowe:
 
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.
 

 Oto kod implementujący ten krok:
 
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;
 

 Ten kod generuje następujące dane wyjściowe:
 
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.
 

 Oto kod implementujący ten krok:
 
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;
 

 Ten kod generuje następujące dane wyjściowe:
 
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.
 

 Oto kod implementujący ten krok:
 
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.
 
Wniosek
 

 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!