Най-близкото съвпадение, част 3

В най-близкото съвпадение, част 1, разгледах T-SQL предизвикателство, което ми беше предоставено от Карън Ли, младши анализатор по фиксирани доходи в RBC. Предизвикателството включваше две таблици – T1 и T2, всяка с ключова колона (keycol), стойност (val) и някои други колони (представени с колона, наречена othercol). Задачата беше да съпоставим на всеки ред от T1 реда от T2, където T2.val е най-близо до T1.val (абсолютната разлика е най-ниската най-ниска), като се използва най-ниската стойност T2.keycol като тайбрейк. Предоставих няколко релационни решения и обсъдих техните характеристики на работа. Също така ви предизвиках да се опитате да намерите разумно работещо решение в случаите, когато не ви е позволено/възможно да създавате поддържащи индекси. В част 2 демонстрирах как това може да се постигне чрез използване на итеративни решения. Получих няколко много интересни решения за четене от Kamil Konsno, Alejandro Mesa и Radek Celuch и тези решения са в центъра на статията от този месец.

Примерни данни

Като напомняне, предоставих както малки, така и големи набори от примерни данни, с които да работите. Малки комплекти за проверка на валидността на вашето решение и големи набори за проверка на ефективността му. Използвайте следния код, за да създадете примерната база данни testdb и в нея примерните таблици T1 и T2:

-- Примерен dbSET NOCOUNT ON; АКО DB_ID('testdb') Е NULL СЪЗДАВАНЕ НА БАЗА ДАННИ testdb;GO ИЗПОЛЗВАЙТЕ testdb;GO -- Примерни таблици T1 и T2DROP TABLE IF EXISTS dbo.T1, dbo.T2; CREATE TABLE dbo.T1( keycol INT NOT NULL ОГРАНИЧЕНИЕ ЗА ИДЕНТИЧНОСТ PK_T1 ПЪРВИЧЕН КЛЮЧ, val INT НЕ NULL, други cols BINARY(100) NOT NULL ОГРАНИЧЕНИЕ DFT_T1_col1 DEFAULT(0xAA)); CREATE TABLE dbo.T2( keycol INT NOT NULL ОГРАНИЧЕНИЕ НА ИДЕНТИЧНОСТ PK_T2 ПЪРВИЧЕН КЛЮЧ, val INT НЕ NULL, други cols BINARY(100) NOT NULL ОГРАНИЧЕНИЕ DFT_T2_col1 DEFAULT(0xBB));

Използвайте следния код, за да попълните таблиците с малки набори от примерни данни:

-- Попълване на T1 и T2 с малки набори от примерни данни TRUNCATE TABLE dbo.T1; TRUNCATE TABLE dbo.T2; ВМЕСТЕ В dbo.T1 (val) СТОЙНОСТИ(1),(1),(3),(3),(5),(8),(13),(16),(18),(20),( 21); ВМЕСТЕ В dbo.T2 (val) СТОЙНОСТИ(2),(2),(7),(3),(3),(11),(11),(13),(17),(19); 

 Ще използвам малките набори от примерни данни, когато описвам логиката на различните решения и ще предоставя междинни набори от резултати за стъпките на решенията.
 

 Използвайте следния код, за да създадете помощната функция GetNums и да попълните таблиците с големи набори от примерни данни:
 
-- Помощна функция за генериране на поредица от цели числа DROP FUNCTION IF EXISTS dbo.GetNums;GO CREATE OR ALTER FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) ВРЪЩА TABLEASRETURN С L0 AS (ИЗБЕРЕТЕ c ОТ (ИЗБЕРЕТЕ c ОТ 1 СЪЕДИНЕНИЕ ВСИЧКИ ИЗБЕРЕТЕ 1) КАТО D(c)), L1 AS (ИЗБЕРЕТЕ 1 КАТО c ОТ L0 КАТО КРЪСТО СЪЕДИНЕНИЕ L0 КАТО B), L2 AS (ИЗБЕРЕТЕ 1 КАТО c ОТ L1 КАТО КРЪСТО СЪЕДИНЕНИЕ L1 КАТО B), L3 AS (ИЗБЕРЕТЕ 1 КАТО c ОТ L2 КАТО КРЪСТО СЪЕДИНЕНИЕ L2 AS B), L4 AS (ИЗБЕРЕТЕ 1 КАТО c ОТ L3 КАТО КРЪСТО СЪЕДИНЕНИЕ L3 КАТО B), L5 AS (ИЗБЕРЕТЕ 1 КАТО c ОТ L4 КАТО КРЪСТО СЪЕДИНЕНИЕ L4 AS B), Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum ОТ L5) SELECT TOP(@high - @low + 1) @low + rownum - 1 AS n FROM Nums ORDER BY rownum;GO -- Попълнете T1 и T2 с големи набори от примерни данниDECLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =10000000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =100000; ТАБЛИЦА ОТСЪЖАНЕ dbo.T1; ОТСЪЗЯВАНЕ НА ТАБЛИЦА dbo.T2; INSERT INTO dbo.T1 WITH(TABLOCK) (val) SELECT ABS(CHECKSSUM(NEWID())) % @maxvalT1 + 1 AS val FROM dbo.GetNums(1, @numrowsT1) AS Nums; INSERT INTO dbo.T2 WITH(TABLOCK) (val) SELECT ABS(COCKKSUM(NEWID())) % @maxvalT2 + 1 AS val FROM dbo.GetNums(1, @numrowsT2) AS Nums;
 

 Когато искате да тествате решението си с поддържащи индекси, използвайте следния код, за да създадете тези индекси:
 
СЪЗДАЙТЕ ИНДЕКС idx_val_key НА dbo.T1(val, keycol) INCLUDE(othercols);СЪЗРАВЕТЕ ИНДЕКС idx_val_key НА dbo.T2(val, keycol) INCLUDE(othercols);СЪЗРАВЕТЕ ИНДЕКС idx_valD_key(othercols) ВКЛЮЧВАНЕ(другикол);
 

 Когато искате да тествате решението си без да поддържате индекси, използвайте следния код, за да премахнете тези индекси:
 
ИЗПУСКАНЕ НА ИНДЕКС, АКО СЪЩЕСТВУВА idx_val_key НА dbo.T1; ИЗПУСКАНЕ НА ИНДЕКС, АКО СЪЩЕСТВУВА idx_val_key НА dbo.T2; ИЗПУСКАНЕ НА ИНДЕКС, АКО СЪЩЕСТВУВА idx_valD_key НА dbo.T2;
 
Решение 1 от Камил Косно – Използване на временна таблица
 

 Камил Косно представи няколко – две с оригиналните си идеи и две вариации на решенията на Алехандро и Радек. Първото решение на Kamil използва индексирана временна таблица. Често се случва, че дори и да не ви е позволено да създавате поддържащи индекси върху оригиналните таблици, ви е позволено да работите с временни таблици, а с временни таблици винаги можете да създавате свои собствени индекси.
 

 Ето пълния код на решението:
 
ПРОСТАНЕ ТАБЛИЦА, АКО СЪЩЕСТВУВА #T2; SELECT MIN(keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val; СЪЗДАЙТЕ УНИКАЛЕН ИНДЕКС idx_nc_val_key НА #T2(val, keycol); С 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)  

 В стъпка 1 от решението вие съхранявате минималния ключов стол за всеки уникален val във временна таблица, наречена #T2, и създавате поддържащ индекс на (val, keycol). Ето кода, който изпълнява тази стъпка:
 
ПРОСТАНЕ ТАБЛИЦА, АКО СЪЩЕСТВУВА #T2; SELECT MIN(keycol) AS keycol, valINTO #T2FROM dbo.T2GROUP BY val; СЪЗДАЙТЕ УНИКАЛЕН ИНДЕКС idx_nc_val_key НА #T2(val, keycol); ИЗБЕРЕТЕ * ОТ #T2;
 

 Временната таблица се попълва със следните данни:
 
keycol val----------- ----------1 24 33 76 118 139 1710 19
 

 В стъпка 2 от решението прилагате следното:
 

 За всеки ред в T1 изчислете prev и nxt стойности от #T2. Изчислете prev като максималния val в #T2, който е по-малък или равен на val в T1. Изчислете nxt като минималния val в #T2, който е по-голям или равен на val в T1.
 

 Използвайте CASE израз, за ​​да изчислите val2 въз основа на следната логика:
 
 
 Когато prev или nxt са нулеви, върнете първото ненулево от двете или NULL, ако и двете са NULL. 
 
 Когато абсолютната разлика между val и prev е по-малка от абсолютната разлика между val и nxt, върнете prev. 
 
 Когато абсолютната разлика между val и nxt е по-малка от абсолютната разлика между val и prv, върнете nxt. 
 
 В противен случай, ако nxt е по-малко от prev, върнете nxt, в противен случай върнете prev. 
 
 

 Ето кода, който изпълнява тази стъпка:
 
SELECT keycol AS keycol1, val AS val1, othercols AS othercols1, CASE WHEN (prev + nxt IS NULL) THEN COALESCE(prev, nxt) WHEN ABS(val - prev)  

 Този код генерира следния изход:
 
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
 

 В стъпка 3 от решението вие дефинирате CTE, наречен bestvals, въз основа на заявката от стъпка 2. След това се присъединявате към bestvals с #T2, за да получите ключовете, и присъединявате резултата с T2, за да получите останалите данни (други колове).
 

 Ето кода, който изпълнява тази стъпка:
 
SELECT keycol1, val1, SUBSTRING(othercols1, 1, 1) AS othercols1, tempT2.keycol AS keycol2, val2, SUBSTRING(T2.othercols, 1, 1) КАТО othercols2FROM bestvals AS B INNER temp JOIN #T2 AStemp .val =B.val2 INNER JOIN dbo.T2 ON T2.keycol =tempT2.keycol;
 

 Планът за решение 1 от Камил с поддържащи индекси е показано на фигура 1.
 

 Фигура 1:План за решение 1 от Kamil с индекси 
 

 Първият клон на плана групира и обобщава данните от T2 и записва резултата във временната таблица #T2. Забележете, че този клон използва предварително поръчан алгоритъм на потока, който разчита на подредено сканиране на индекса idx_valD_key на T2.
 

 Ето статистиката за ефективността за този план:
 
време на изпълнение (сек):5,55, CPU (сек):16,6, логически четения:6 687 172
 

 Планът за решение 1 от Kamil без поддържащи индекси е показан на Фигура 2.
 

 Фигура 2:План за решение 1 от Kamil без индекси 
 

 Основната разлика между този план и предишния е, че първият клон на плана, който обработва частта за групиране и агрегиране в Стъпка 1, този път не може да изтегли предварително подредените данни от поддържащ индекс, така че ги изтегля неподредени от клъстерирания индекс на T2 и след това използва алгоритъм за хеш агрегатиране.
 

 Ето статистиката за ефективността за този план:
 
време на изпълнение:6.44, процесор:19.3, логически четения:6,688,277
 
Решение от Алехандро Меса – Използване на последна ненулева техника
 

 Решението на Алехандро използва последната ненулева техника, описана тук.
 

 Ето пълния код на решението (предоставен тук без връщане на другикол):
 
С 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 РЕДОВЕ МЕЖДУ НЕОГРАНИЧЕН ПРЕДШЕСТВАЩ И 1 ПРЕДИШЕН ) КАТО по-долу_binstr, MIN( CASE WHEN tid =0 THEN CAST(val AS binary(4)) + CAST(keycol AS binary(4)) END ) OVER( ORDER BY val, tid keycol РЕДОВЕ МЕЖДУ 1 СЛЕДВАЩ И НЕОГРАНИЧЕН СЛЕД ) КАТО по-горе_binstr ОТ ( ИЗБЕРЕТЕ ключов символ, val, 1 КАТО tid ОТ dbo.T1 UNION ALL SELECT MIN(keycol) КАТО keycol, val, 0 КАТО tid ОТ TBY.Tval GROUP) КАТО ГРУПА ),R2 AS( SELECT keycol, val, CAST(SUBSTRING(below_binstr, 1, 4) AS int) AS под_T2_val, CAST(SUBSTRING(below_binstr, 5, 4) AS int) AS под_T2_keycol, CAST(SUBSTRING(above_binstr, 1, 4) AS int) AS над_T2_val, CAST(SUBSTRING(above_binstr, 5, 4) AS int) AS над_T2_keycol ОТ R1 КЪДЕ 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 above_T2_keycol FROM R2)SELECT keycol AS keycol1, val AS val1, CASE WHEN ABS(val - below_T2_val ) <=ABS(above_T2_val - val) THEN under_T2_keycol ELSE above_T2_keycol END AS keycol2, CASE WHEN ABS(val - under_T2_val) <=ABS(above_T2_val - val) THEN under_T2_val ELSE
 В стъпка 1 от решението вие обединявате редовете от T1 (присвояване на колона за резултат, наречена tid на 1) с редовете от T2 (присвояване на tid =0) и дефинирате производна таблица, наречена T, въз основа на резултата. Използвайки последната ненулева техника, базирана на реда на val, tid, keycol, за всеки текущ ред, вие извличате стойностите на последния tid =0 ред, конкатенирани в двоична колона, наречена below_binstr. По същия начин извличате стойностите на следващия tid =0 ред, обединени в двоична колона, наречена above_binstr.
 

 Ето кода, който изпълнява тази стъпка:
 
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 РЕДОВЕ МЕЖДУ НЕОГРАНИЧЕН ПРЕДШЕСТВАЩ И 1 ПРЕДИШЕН ) КАТО по-долу_binstr, MIN( CASE WHEN tid =0 THEN CAST(val AS binary(4)) + CAST(keycol AS binary(4)) END ) OVER( ORDER BY val, tid, keycol РЕДОВЕ МЕЖДУ1 СЛЕДВАНЕ И НЕЗГРАНИЧНО СЛЕДВАНЕ ) AS above_binstrFROM ( SELECT keycol, val, 1 AS tid ОТ dbo.T1 UNION ALL SELECT MIN(keycol) AS keycol, val, 0 AS tid ОТ dbo.T2 GROUP BY val ) AS T;
 

 Този код генерира следния изход:
 
keycol val tid below_binstr above_binstr----------- ----------- ----------- --------- --------- ------------------ 1 1 1 1 NULL 0x00000002000000012 1 1 NULL 0x00000002000000011 2 0 NULL 0x000000030000044 3 0 0x0000000200000001 0x000000070000033 3 1 0x0000000000000000404000 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
 

 В стъпка 2 от решението вие дефинирате CTE, наречен R1, въз основа на заявката от стъпка 1. Заявявате R1, филтрирате само редове, където tid =1, и извличате отделните стойности от конкатенираните двоични низове.
 

 Ето кода, който изпълнява тази стъпка:
 
SELECT keycol, val, CAST(SUBSTRING(below_binstr, 1, 4) AS int) AS под_T2_val, CAST(SUBSTRING(below_binstr, 5, 4) AS int) AS под_T2_keycol, CAST(SUBSTRING(above_binstr, 1, 4) AS int) AS горе_T2_val, CAST(SUBSTRING(above_binstr, 5, 4) AS int) AS горе_T2_keycolFROM R1WHERE tid =1;
 

 Този код генерира следния изход:
 
keycol val under_T2_val under_T2_keycol above_T2_val above_T2_keycol----------- ----------- ------------ ------- --------- ------------ ----------------1 1 NULL NULL 2 12 1 NULL NULL 2 13 3 3 4 7 34 3 3 4 7 35 5 3 4 7 36 8 7 3 11 67 13 13 8 17 98 16 13 8 17 99 18 17 9 19 1010 20 19 10 NULL NULL 19 0 NULL NULL 19 

 В стъпка 3 от решението вие дефинирате CTE, наречен R2 въз основа на заявката от стъпка 2. След това изчислявате следните колони с резултати:
 
 
 below_T2_val:първата ненулева стойност между bottom_T2_val и above_T2_val 
 
 below_T2_keycol:първият ненулев между bottom_T2_keycol и above_T2_keycol 
 
 above_T2_val:първата ненулева стойност между above_T2_val и bottom_T2_val 
 
 above_T2_keycol:първата ненулева между above_T2_keycol и bottom_T2_keycol 
 
 

 Ето кода, който изпълнява тази стъпка:
 
 Изберете KeyCol, Val, CoalesCe (по -долу_t2_val, над_t2_val) като по -долу_T2_VAL, CAUDESCE (под_T2_KEYCOL, над_t2_keycol) като по -долу_t2_keycol, coadesce (над_t2_val, по -долу_t2_val) като над_t2_val, coalesce 

 Този код генерира следния изход:
 
keycol val under_T2_val under_T2_keycol above_T2_val above_T2_keycol----------- ----------- ------------ ------- --------- ----------- ----------------1 1 2 1 2 12 1 2 1 2 13 3 3 4 7 34 3 3 4 7 35 5 3 4 7 36 8 7 3 11 67 13 13 8 17 98 16 13 8 17 99 18 17 9 19 1010 20 19 10 19 101 0 1 1 1 1 1 

 В стъпка 4 от решението вие дефинирате CTE, наречен R3, въз основа на заявката от стъпка 3. Връщате keycol с псевдоним T1_keycol и val с псевдоним T1_val. Изчислете колоната за резултат T2_keycol като:ако абсолютната разлика между val и bottom_T2_val е по-малка или равна на абсолютната разлика между above_T2_val и val, върнете under_T2_keycol, в противен случай над_T2_keycol. Изчислете колоната за резултат T2_val като:ако абсолютната разлика между val и bottom_T2_val е по-малка или равна на абсолютната разлика между above_T2_val и val, върнете под_T2_val, в противен случай над_T2_val.
 

 Ето кода, който изпълнява тази стъпка:
 
SELECT keycol AS keycol1, val AS val1, CASE WHEN ABS(val - under_T2_val) <=ABS(above_T2_val - val) THEN under_T2_keycol ELSE above_T2_keycol END AS keycol2, CASE WHEN ABS(val - val - val) val) THEN under_T2_val ELSE above_T2_val END AS val2FROM R3;
 

 Планът за решението на Алехандро с поддържащи индекси е показан на фигура 3.
 

 Фигура 3:План за решение от Алехандро с индекси 
 

 Ето статистиката за ефективността за този план:
 
време на изпълнение:7.8, CPU:12.6, логически четения:35 886
 

 Планът за решението на Алехандро без поддържащи индекси е показан на фигура 4.
 

 Фигура 4:План за решение от Алехандро без индекси 
 

 Ето статистиката за ефективността за този план:
 
време на изпълнение:8.19, CPU:14.8, логически показания:37 091
 

 Забележете, че в първите два клона на плана на Фигура 4 има два вида преди оператора Merge Join (Concatenation) поради липсата на поддържащи индекси. Тези сортировки не са необходими в плана на фигура 3, тъй като данните се извличат предварително поръчани от поддържащите индекси.
 
Вариантът на Камил върху решението на Алехандро
 

 В това решение Камил също разчита на последната ненулева техника. Ето пълния код на решението:
 
WITH all_vals AS( SELECT keycol, val FROM dbo.T1 UNION ALL SELECT DISTINCT NULL, val FROM dbo.T2), диапазони AS( SELECT keycol, val, MAX(СЛУЧАЙ, КОГАТО keycol Е NULL ТОГАВА val END) НАД (ПОРЪЧКА BY val, keycol РЕДОВЕ МЕЖДУ НЕОГРАНИЧЕН ПРЕДШЕСТВАЩ И 1 ПРЕДИШЕН) КАТО предишна, MIN(СЛУЧАЙ, КОГАТО keycol е NULL, ТОГАВА val END) НАД (ПОРЕД ПО val, keycol РЕДОВЕ МЕЖДУ 1 СЛЕДВАЩ И НЕОГРАНИЧЕН) КАТО всички СЛЕДВАЩИ КАТО_n SELECT keycol AS keycol1, val AS val1, CASE WHEN ABS(val - prev) <=ISNULL(ABS(val - nxt), prev) THEN prev ELSE nxt КРАЙ КАТО val2 ОТ диапазони, КЪДЕТО keycol НЕ Е NULL)SELECT keycol1, val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, val2, T2.keycol AS keycol2, SUBSTRING(T2.othercols, 1, 1) КАТО othercols2 FROM matched_vals AS M INNER JOIN ( SELECT *, ROW_NUMBER() НАД (PARTITION) val ORDER BY keycol) AS rn ОТ dbo.T2 ) AS T2 ON T2.val =M.val2 И rn =1 INNER JOIN dbo.T1 ON T1.keycol =keycol1;
 

 В стъпка 1 от решението вие дефинирате CTE, наречени all_vals и диапазони, където използвате последната ненулева техника, за да идентифицирате за всяка стойност в T1 (където keycol не е NULL) диапазони от по-долу (prev) и по-горе (nxt) стойности от T2 ( където keycol е нула).
 

 Ето кода, който изпълнява тази стъпка:
 
WITH all_vals AS( SELECT keycol, val FROM dbo.T1 UNION ALL SELECT DISTINCT NULL, val FROM dbo.T2), диапазони AS( SELECT keycol, val, MAX(СЛУЧАЙ, КОГАТО keycol Е NULL ТОГАВА val END) НАД (ПОРЪЧКА BY val, keycol РЕДОВЕ МЕЖДУ НЕОГРАНИЧЕН ПРЕДШЕСТВАЩ И 1 ПРЕДИШЕН) КАТО предишна, MIN(СЛУЧАЙ, КОГАТО keycol е NULL, ТОГАВА val END) НАД (ПОРЕД ПО val, keycol РЕДОВЕ МЕЖДУ 1 СЛЕДВАЩ И НЕОГРАНИЧЕН РЕДОВ МЕЖДУ 1 СЛЕДВАЩ И НЕОГРАНИЧЕН FROM ИЗБРАНИ ИЗБРАНИ *n диапазон) FROM_val;
 

 Този код генерира следния изход:
 
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 7 NULL 7 3 116 8 7 11 NULL 11 7 13 NULL 13 11 177 17 19 17 17 19 17 17 17 17 17 17 17 20 19 NULL11 21 19 NULL
 

 В стъпка 2 от решението вие заявявате CTE диапазоните и филтрирате само редове, където keycol не е нула. Връщате колоните keycol и val от T1 като keycol1 и val1, съответно. След това, между prev и nxt, връщате най-близкото до val1 като val2.
 

 Ето кода, който изпълнява тази стъпка:
 
ИЗБЕРЕТЕ keycol КАТО keycol1, val КАТО val1, CASE WHEN ABS(val - prev) <=ISNULL(ABS(val - nxt), prev) THEN prev ELSE nxt END AS val2FROM диапазони WHERE keycol НЕ Е NULL;
 

 Този код генерира следния изход:
 
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
 

 В стъпка 3 от решението вие дефинирате CTE, наречен matched_vals, въз основа на заявката от стъпка 2. Вие също така дефинирате извлечена таблица, наречена T2, където с помощта на разделени номера на редове обработвате логиката за разделяне на редовете за редовете от dbo.T2. След това се присъединявате към matched_vals, CTE T2 и таблицата T1, за да обработвате окончателната логика за съвпадение.
 

 Ето кода, който изпълнява тази стъпка:
 
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 SELECT * INNER JOIN (ИЗБЕРЕТЕ , ROW_NUMBER() НАД (РАЗДЕЛЯНЕ ПО val ПОРЪЧКА ПО keycol) КАТО rn ОТ dbo.T2 ) КАТО T2 ON T2.val =M.val2 И rn =1 INNER JOIN dbo.T1 ON T1.keycol =keycol1;
 

 Планът за вариацията на Камил върху решението на Алехандро с поддържащи индекси е показан на фигура 5.
 

 Фигура 5:План за вариацията на Камил върху решението на Алехандро с индекси 
 

 Ето статистиката за ефективността за този план:
 
време на изпълнение:11.5, CPU:18.3, логически показания:59 218
 

 Планът за вариацията на Камил върху решението на Алехандро без поддържащи индекси е показан на фигура 6.
 

 Фигура 6:План за вариацията на Камил върху решението на Алехандро без индекси 
 

 Ето статистиката за ефективността за този план:
 
време на изпълнение:12.6, CPU:23.5, логически четения:61 432
 

 Подобно на плановете за решението на Алехандро, също и в този случай планът на фигура 5 не изисква изрично сортиране преди прилагането на оператора за свързване на сливане (конкатенация), тъй като данните се извличат предварително подредени от поддържащи индекси, а планът на фигура 6 го прави изискват изрично сортиране, тъй като няма поддържащи индекси.
 
Решение от Radek Celuch – Използване на интервали
 

 Радек му хрумна проста и красива идея. За всяка отделна стойност в T2.val изчислявате интервал, представляващ диапазона от стойности от T1.val, които биха съвпадали с текущия T2.val. 
 

 Ето пълния код на решението:
 
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 предишна, 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 - предишна) % 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 НА T1.val МЕЖДУ T2.low T2.високо;
 

 В стъпка 1 от решението вие заявявате T2 и изчислявате номерата на редовете (извикайте колоната rn), разделени по val и подредени по keycol. Вие дефинирате CTE, наречен Pre1, въз основа на тази заявка. След това правите заявка Pre1 и филтрирате само редовете, където rn =1. В същата заявка, използвайки LAG и LEAD, връщате за всеки ред стойността на колоната val от предишния ред (наречете го prev) и от следващия ред ( обадете се по-нататък).
 

 Ето кода, който изпълнява тази стъпка:
 
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) КАТО предишен, LEAD(val) OVER(ORDER BY val) AS nextFROM Pre1WHERE rn =1;
 

 Този код генерира следния изход:
 
keycol val othercols предишна следваща------- ---- ---------- ----------- ---------- -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
 

 В стъпка 2 от решението вие дефинирате CTE, наречен Pre2 въз основа на заявката от стъпка 1. Запитвате Pre2 и изчислявате за всеки ред интервал [нисък, висок], където val от T1 ще попадне. Ето изчисленията за ниски и високо:
 
 
 ниско =ISNULL(val – (val – предишна) / 2 + (1 – (val – предишна) % 2), 0) 
 
 високо =ISNULL(val + (следващо – val) / 2, 2147483647) 
 
 

 Проверката на мод 2 при изчисляване на ниската граница се използва за покриване на по-ниското изискване за T2.val, а филтърът за номера на редове се използва за покриване на по-ниското изискване за T2.keycol. Стойностите 0 и 2147483647 се използват като крайна долна и горна граница.
 

 Ето кода, който изпълнява тази стъпка:
 
SELECT keycol, val, othercols, ISNULL(val - (val - prev) / 2 + (1 - (val - prev) % 2), 0) AS low, ISNULL(val + (next - val) / 2 , 2147483647) AS highFROM Pre2;
 

 Този код генерира следния изход:
 
keycol val othercols low high------- ---- ---------- ---- -----------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
 

 В стъпка 3 от решението вие дефинирате CTE, наречен T2, въз основа на заявката от стъпка 2. След това присъединявате таблицата T1 с редовете, съответстващи на CTE T2, базирани на val от T1, които са в интервала [ниско, високо] в T2.
 

 Ето кода, който изпълнява тази стъпка:
 
ИЗБЕРЕТЕ 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 ) КАТО othercols2FROM dbo.T1 INNER JOIN T2 НА T1.val МЕЖДУ T2.low И T2.high;
 

 Планът за решението на Radek с поддържащи индекси е показан на Фигура 7. 
 

 Фигура 7:План за решение от Radek с индекси 
 

 Ето статистиката за ефективността за този план:
 
време на изпълнение:10.6, процесор:7.63, логически четения:3,193,125
 

 Планът за решението на Radek без поддържащи индекси е показан на Фигура 8. 
 

 Фигура 8:План за решение от Radek без индекси 
 

 Ето статистическите данни за ефективността за този план:
 
време на изпълнение:18.1, CPU:27.4, логически четения:5 827 360
 

 Тук разликата в производителността между двата плана е доста значителна. Планът на фигура 8 изисква предварително сортиране преди изчисляването на номерата на редовете, което планът на фигура 7 не прави. По-важното е, че за да съпостави всеки интервал със съответните редове от T1, планът на Фигура 8 създава Index Spool по същество като алтернатива на липсващия индекс, докато планът на Фигура 7 просто използва съществуващия индекс idx_val_key на T1. Това е основната причина за големите разлики във всички показатели за ефективност. Все пак производителността без поддържащи индекси е разумна.
 
Вариант на Камил върху решението на Радек
 

 Камил излезе с вариация на решението на Радек. Ето пълния код на решението:
 
WITH T2_collapsed AS( SELECT keycol AS keycol2, val AS val2 , ROW_NUMBER() НАД (РАЗДЕЛЯНЕ BY val ORDER BY keycol) КАТО rn ОТ dbo.T2), диапазони AS( SELECT keycol2 КАТО prevkey, val2 AS prevval, LEAD( keycol2) НАД (ПОРЕД ПО val2) КАТО nxkey, LEAD(val2) НАД (ПОРЕД ПО val2) КАТО nxtval ОТ T2_collapsed КЪДЕ rn =1), най-добре съвпада КАТО( ИЗБЕРЕТЕ T1.keycol КАТО keycol1, T1.val КАТО valT1, SUBSTRING .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.
 
Заключение
 

 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!