Карън Ли, младши анализатор на фиксирани доходи в RBC, ми даде T-SQL предизвикателство, което включва намиране на най-близкото съвпадение, вместо намиране на точно съвпадение. В тази статия разглеждам обобщена, опростена форма на предизвикателството.
Предизвикателството
Предизвикателството включва съпоставяне на редове от две таблици, T1 и T2. Използвайте следния код, за да създадете примерна база данни, наречена testdb, и в нея таблиците T1 и T2:
ЗАДАДЕТЕ NOCOUNT ON; АКО DB_ID('testdb') Е NULL СЪЗДАВАНЕ НА БАЗА ДАННИ testdb; ИЗПОЛЗВАЙТЕ testdb; ИЗПУСКАНЕ ТАБЛИЦА, АКО СЪЩЕСТВУВА 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 ОГРАНИЧЕНИЕ 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 ОГРАНИЧЕНИЕ DFT_T2_col1 DEFAULT(0xBB) ); Както можете да видите, и T1, и T2 имат числова колона (тип INT в този пример), наречена val. Предизвикателството е да съпоставите на всеки ред от T1 реда от T2, където абсолютната разлика между T2.val и T1.val е най-ниската. В случай на равенство (множество съвпадащи редове в T2), съпоставете горния ред въз основа на възходящ ред на val, възходящ ред. Тоест, редът с най-ниската стойност в колоната val и ако все още имате връзки, редът с най-ниската стойност на ключов символ. Тайбрейкът се използва за гарантиране на детерминизъм.
Използвайте следния код, за да попълните T1 и T2 с малки набори от примерни данни, за да можете да проверите правилността на вашите решения:
ОТСЪЩАНЕ НА ТАБЛИЦА dbo.T1; ТАБЛИЦА ОТСЪЖАНЕ 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);Проверете съдържанието на T1:
ИЗБЕРЕТЕ keycol, val, SUBSTRING(othercols, 1, 1) AS othercols ОТ dbo.T1 ORDER BY val, keycol;Този код генерира следния изход:
keycol val othercols ----------- ----------- --------- 1 1 0xAA 2 1 0xAA 3 3 0xAA 4 3 0xAA 5 5 0xAA 6 8 0xAA 7 13 0xAA 8 16 0xAA 9 18 0xAA 10 20 0xAA 11 21 0xAAПроверете съдържанието на T2:
ИЗБЕРЕТЕ keycol, val, SUBSTRING(othercols, 1, 1) AS othercols ОТ dbo.T2 ORDER BY val, keycol;Този код генерира следния изход:
keycol val othercols ----------- ----------- --------- 1 2 0xBB 2 2 0xBB 4 3 0xBB 5 3 0xBB 3 7 0xBB 6 11 0xBB 7 11 0xBB 8 13 0xBB 9 17 0xBB 10 19 0xBBЕто желания резултат за дадените примерни данни:
keycol1 val1 othercols1 keycol2 val2 othercols2 ----------- ----------- ---------- --------- -- ----------- ---------- 1 1 0xAA 1 2 0xBB 2 1 0xAA 1 2 0xBB 3 3 0xAA 4 3 0xBB 4 3 0xAA 4 3 0xBB 5 5 0xAA 4 3 0xBB 6 8 0xAA 3 7 0xBB 7 13 0xAA 8 13 0xBB 8 16 0xAA 9 17 0xBB 9 18 0xAA 9 17 0xBB 10 20 0xAA 10 19 0xBB 8 16 0xAA 9 17 0xBB 9 18 0xAA 9 17 0xBB 10 20 0xAA 10 19 0x10 BB0 10 19 0x1 AAПреди да започнете да работите по предизвикателството, проучете желания резултат и се уверете, че разбирате логиката на съвпадението, включително логиката на тайбрейка. Например, помислете за реда в T1, където keycol е 5 и val е 5. Този ред има множество най-близки съвпадения в T2:
keycol val othercols ----------- ----------- --------- 4 3 0xBB 5 3 0xBB 3 7 0xBBВъв всички тези редове абсолютната разлика между T2.val и T1.val (5) е 2. Използвайки логиката за разбиване на равенство, базирана на нарастващия ред val, клавишната колона, възходяща на най-горния ред тук, е тази, където val е 3, а keycol е 4.
Ще използвате малките набори от примерни данни, за да проверите валидността на вашите решения. За да проверите производителността, имате нужда от по-големи комплекти. Използвайте следния код, за да създадете помощна функция, наречена GetNums, която генерира поредица от цели числа в заявен диапазон:
ИЗПУСКАНЕ ФУНКЦИЯ, АКО СЪЩЕСТВУВА dbo.GetNums; ИЗБИРАЙТЕ СЪЗДАВАТЕ ИЛИ ПРОМЕНЯТЕ ФУНКЦИЯ dbo.GetNums(@low AS BIGINT, @high AS BIGINT) ВРЪЩА ТАБЛИЦА КАТО ВЪЗВРЪЩАНЕ С L0 AS (ИЗБЕРЕТЕ c ОТ (ИЗБЕРЕТЕ 1 СЪЕДИНЕНИЕ ВСИЧКИ SELECT 1) КАТО D(c)), L1 КАТО (ИЗБЕРЕТЕ 1 КАТО c ОТ L0 КАТО КРЪСТО СЪЕДИНЕНИЕ L0 AS B), L2 AS (ИЗБЕРЕТЕ 1 КАТО c ОТ L1 КАТО КРЪСТО СЪЕДИНЕНИЕ L1 AS B), L3 AS (ИЗБЕРЕТЕ 1 КАТО c ОТ L2 КАТО КРЪСТО СЪЕДИНЕНИЕ L2 AS B), L4 AS (ИЗБЕРЕТЕ 1 КАТО c ОТ L3 КАТО КРЪСТО СЪЕДИНЕНИЕ L3 КАТО B), L5 AS (ИЗБЕРЕТЕ 1 КАТО c ОТ L4 КАТО КРЪСТО СЪЕДИНЕНИЕ L4 КАТО B), Nums AS (ИЗБЕРЕТЕ ROW_NUMBER() НАД (ПОРЪЧАЙТЕ ОТ (ИЗБЕРЕТЕ NULL) ) КАТО rownum ОТ L5) SELECT TOP(@high - @low + 1) @low + rownum - 1 КАТО n FROM Nums ORDER BY rownum; ОТПРАВИИзползвайте следния код, за да попълните T1 и T2 с големи набори от примерни данни:
ДЕКЛАРИРАНЕ @numrowsT1 КАТО INT =1000000, @maxvalT1 КАТО INT =10000000, @numrowsT2 КАТО INT =1000000, @maxvalT2 КАТО INT =10000000; ТАБЛИЦА ОТСЪЖАНЕ 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;Променливите @numrowsT1 и @numrowsT2 контролират броя на редовете, с които искате да се попълват таблиците. Променливите @maxvalT1 и @maxvalT2 контролират диапазона от различни стойности в колоната val и следователно влияят върху плътността на колоната. Горният код запълва таблиците с по 1 000 000 реда всяка и използва диапазона от 1 – 10 000 000 за колоната val и в двете таблици. Това води до ниска плътност в колоната (голям брой различни стойности, с малък брой дубликати). Използването на по-ниски максимални стойности ще доведе до по-висока плътност (по-малък брой различни стойности и следователно повече дублирани).
Решение 1, като се използва една ТОП подзаявка
Най-простото и очевидно решение вероятно е това, което отправя заявка към T1 и използвайки оператора CROSS APPLY прилага заявка с TOP (1) филтър, подреждайки редовете по абсолютната разлика между T1.val и T2.val, използвайки T2.val , T2.keycol като тайбрейк. Ето кода на решението:
ИЗБЕРЕТЕ T1.keycol КАТО keycol1, T1.val КАТО val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) КАТО othercols2 ОТ dbo.T1 КРЪСТ ПРИЛОЖИ (ИЗБЕРЕТЕ ВЪРХА (1) T2.* ОТ dbo.T2 ПОРЪЧАЙТЕ ПО ABS(T2.val - T1.val), T2.val, T2.keycol ) КАТО A;Не забравяйте, че има 1 000 000 реда във всяка от таблиците. И плътността на колоната val е ниска и в двете таблици. За съжаление, тъй като в приложената заявка няма предикат за филтриране и подреждането включва израз, който манипулира колони, тук няма потенциал за създаване на поддържащи индекси. Тази заявка генерира плана на фигура 1.
Фигура 1:План за решение 1
Външният вход на цикъла сканира 1 000 000 реда от T1. Вътрешният вход на цикъла извършва пълно сканиране на T2 и сортиране TopN за всяка отделна стойност на T1.val. В нашия план това се случва 998 657 пъти, тъй като имаме много ниска плътност. Той поставя редовете в индексна спула, ключирана от T1.val, така че да може да ги използва повторно за дублиране на T1.val стойности, но имаме много малко дубликати. Този план има квадратична сложност. Между всички очаквани изпълнения на вътрешния клон на цикъла се очаква да обработи близо трилион реда. Когато говорим за голям брой редове за обработка на заявка, след като започнете да споменавате милиарди редове, хората вече знаят, че имате работа със скъпа заявка. Обикновено хората не произнасят термини като трилиони, освен ако не обсъждат националния дълг на САЩ или сривовете на фондовия пазар. Обикновено не се занимавате с такива числа в контекста на обработка на заявки. Но плановете с квадратична сложност могат бързо да се окажат с такива числа. Изпълняването на заявката в SSMS с включена статистика за заявка на живо отне 39,6 секунди, за да обработи само 100 реда от T1 на моя лаптоп. Това означава, че завършването на тази заявка трябва да отнеме около 4,5 дни. Въпросът е дали наистина обичате да наблюдавате планове за заявки на живо? Може да е интересен рекорд на Гинес, който да опитате и поставите.
Решение 2, използващо две ТОП подзаявки
Ако приемем, че търсите решение, което отнема секунди, а не дни, за да завършите, ето една идея. В приложения израз на таблица, обединете две вътрешни заявки TOP (1) – едната филтрира ред, където T2.val
=T1.val (подредено от T2.val, T2.keycol). Лесно е да се създават индекси за поддръжка на такива заявки, като се активира едноредово търсене. Все още в рамките на приложения табличен израз, използвайте външна заявка TOP (1) срещу двуредовия резултат, въз основа на реда ABS(D.val – T1.val), D.val, D.keycol. Ще има включено сортиране по TopN, но то ще се прилага към два реда наведнъж. Ето препоръчителните индекси в подкрепа на това решение:
СЪЗДАЙТЕ ИНДЕКС idx_val_key ON dbo.T1(val, keycol) INCLUDE(othercols); CREATE INDEX idx_val_key ON dbo.T2(val, keycol) INCLUDE(othercols); СЪЗДАЙТЕ ИНДЕКС idx_valD_key НА dbo.T2(val DESC, keycol) INCLUDE(othercols);Ето пълния код на решението:
ИЗБЕРЕТЕ T1.keycol КАТО keycol1, T1.val КАТО val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) КАТО други cols2 ОТ dbo.T1 КРЪСТ ПРИЛОЖИ ( ИЗБЕРЕТЕ ВЪРХА (1) D.* ОТ ( ИЗБЕРЕТЕ ВЪРХА (1) * ОТ dbo.T2 КЪДЕТО T2.val=T1.val ПОРЪЧКА ПО T2.val, T2.keycol ) КАТО D ПОРЪЧКА ПО ABS(D.val - T1.val), D.val, D. keycol ) AS A; Не забравяйте, че имаме 1 000 000 реда във всяка таблица, като колоната val има стойности в диапазона 1 – 10 000 000 (ниска плътност) и оптимални индекси.
Планът за тази заявка е показан на Фигура 2.
Фигура 2:План за решение 2
Спазвайте оптималното използване на индексите на T2, което води до план с линейно мащабиране. Този план използва индексна шпула по същия начин, както предишният план, т.е., за да се избегне повтарянето на работата във вътрешния клон на цикъла за дублирани стойности на T1.val. Ето статистическите данни за производителността, които получих за изпълнението на тази заявка в моята система:
Изминало:27,7 сек, CPU:27,6 сек, логически показания:17 304 674Решение 2, с изключено пулиране
Няма как да не се чудите дали индексната шпула наистина е полезна тук. Въпросът е да се избягва повтарянето на работа за дублирани стойности на T1.val, но в ситуация като нашата, когато имаме много ниска плътност, има много малко дубликати. Това означава, че най-вероятно работата, свързана с буферирането, е по-голяма от простото повтаряне на работата за дубликати. Има прост начин да потвърдите това - като използвате флаг за проследяване 8690, можете да деактивирате буферирането в плана, както следва:
ИЗБЕРЕТЕ T1.keycol КАТО keycol1, T1.val КАТО val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) КАТО други cols2 ОТ dbo.T1 КРЪСТ ПРИЛОЖИ ( ИЗБЕРЕТЕ ВЪРХА (1) D.* ОТ ( ИЗБЕРЕТЕ ВЪРХА (1) * ОТ dbo.T2 КЪДЕТО T2.val=T1.val ПОРЪЧКА ПО T2.val, T2.keycol ) КАТО D ПОРЪЧКА ПО ABS(D.val - T1.val), D.val, D. keycol ) КАТО ОПЦИЯ(QUERYTRACEON 8690); Получих плана, показан на фигура 3 за това изпълнение:
Фигура 3:План за решение 2, с изключено буфериране
Забележете, че индексната макара е изчезнала и този път вътрешният клон на цикъла се изпълнява 1 000 000 пъти. Ето статистическите данни за производителността, които получих за това изпълнение:
Изминало:19,18 сек, CPU:19,17 сек, логически показания:6 042 148Това е намаление от 44 процента във времето за изпълнение.
Решение 2, с модифициран диапазон от стойности и индексиране
Деактивирането на спулинга има много смисъл, когато имате ниска плътност в стойностите на T1.val; въпреки това, навиването може да бъде много полезно, когато имате висока плътност. Например, изпълнете следния код, за да попълните отново T1 и T2 с примерна настройка на данни @maxvalT1 и @maxvalT2 до 1000 (1000 максимални различни стойности):
ДЕКЛАРИРАНЕ @numrowsT1 КАТО INT =1000000, @maxvalT1 КАТО INT =1000, @numrowsT2 КАТО INT =1000000, @maxvalT2 КАТО INT =1000; ТАБЛИЦА ОТСЪЖАНЕ 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;Повторете Решение 2, първо без флага за проследяване:
ИЗБЕРЕТЕ T1.keycol КАТО keycol1, T1.val КАТО val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) КАТО други cols2 ОТ dbo.T1 КРЪСТ ПРИЛОЖИ ( ИЗБЕРЕТЕ ВЪРХА (1) D.* ОТ ( ИЗБЕРЕТЕ ВЪРХА (1) * ОТ dbo.T2 КЪДЕТО T2.val=T1.val ПОРЪЧКА ПО T2.val, T2.keycol ) КАТО D ПОРЪЧКА ПО ABS(D.val - T1.val), D.val, D. keycol ) AS A; Планът за това изпълнение е показан на Фигура 4:
Фигура 4:План за решение 2, с диапазон на стойност 1 – 1000
Оптимизаторът реши да използва различен план поради високата плътност в T1.val. Обърнете внимание, че индексът на T1 се сканира в ключов ред. И така, за всяко първо появяване на отделна стойност T1.val вътрешният клон на цикъла се изпълнява и резултатът се пулсира в обикновена таблица за пулиране (повторно свързване). След това, за всяко непърво появяване на стойността, се прилага пренавиване. С 1000 различни стойности, вътрешният клон се изпълнява само 1000 пъти. Това води до отлична статистика за ефективността:
Изминало:1,16 сек, CPU:1,14 сек, логически показания:23 278Сега опитайте да стартирате решението с изключено спулиране:
ИЗБЕРЕТЕ T1.keycol КАТО keycol1, T1.val КАТО val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) КАТО други cols2 ОТ dbo.T1 КРЪСТ ПРИЛОЖИ ( ИЗБЕРЕТЕ ВЪРХА (1) D.* ОТ ( ИЗБЕРЕТЕ ВЪРХА (1) * ОТ dbo.T2 КЪДЕТО T2.val=T1.val ПОРЪЧКА ПО T2.val, T2.keycol ) КАТО D ПОРЪЧКА ПО ABS(D.val - T1.val), D.val, D. keycol ) КАТО ОПЦИЯ(QUERYTRACEON 8690); Получих плана, показан на фигура 5.
Фигура 5:План за решение 2, с диапазон на стойност 1 – 1000 и изключване на буфериране
По същество това е същият план, показан по-рано на Фигура 3. Вътрешният клон на цикъла се изпълнява 1 000 000 пъти. Ето статистическите данни за производителността, които получих за това изпълнение:
Изминало:24,5 сек, CPU:24,2 сек, логически показания:8 012 548Ясно е, че искате да внимавате да не деактивирате спулинга, когато имате висока плътност в T1.val.
Животът е добър, когато ситуацията ви е достатъчно проста, за да можете да създавате поддържащи индекси. Реалността е, че в някои случаи на практика има достатъчно допълнителна логика в заявката, която изключва възможността за създаване на оптимални поддържащи индекси. В такива случаи Решение 2 няма да се справи добре.
За да демонстрирате производителността на Решение 2 без поддържащи индекси, попълнете отново T1 и T2 с примерна настройка на данни @maxvalT1 и @maxvalT2 до 10000000 (диапазон на стойностите 1 – 10M), а също така премахнете поддържащите индекси:
ИЗПУСКАНЕ НА ИНДЕКС, АКО СЪЩЕСТВУВА idx_val_key НА dbo.T1; ИЗПУСКАНЕ НА ИНДЕКС, АКО СЪЩЕСТВУВА idx_val_key НА dbo.T2; ИЗПУСКАНЕ НА ИНДЕКС, АКО СЪЩЕСТВУВА idx_valD_key НА dbo.T2; ДЕКЛАРИРАНЕ @numrowsT1 КАТО INT =1000000, @maxvalT1 КАТО INT =10000000, @numrowsT2 КАТО INT =1000000, @maxvalT2 КАТО INT =10000000; ТАБЛИЦА ОТСЪЖАНЕ 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;Изпълнете повторно Решение 2, с активирана статистика за заявка на живо в SSMS:
ИЗБЕРЕТЕ T1.keycol КАТО keycol1, T1.val КАТО val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) КАТО други cols2 ОТ dbo.T1 КРЪСТ ПРИЛОЖИ ( ИЗБЕРЕТЕ ВЪРХА (1) D.* ОТ ( ИЗБЕРЕТЕ ВЪРХА (1) * ОТ dbo.T2 КЪДЕТО T2.val=T1.val ПОРЪЧКА ПО T2.val, T2.keycol ) КАТО D ПОРЪЧКА ПО ABS(D.val - T1.val), D.val, D. keycol ) AS A; Получих плана, показан на фигура 6 за тази заявка:
Фигура 6:План за решение 2, без индексиране, с диапазон на стойност 1 – 1 000 000
Можете да видите модел, много подобен на този, показан по-рано на фигура 1, само че този път планът сканира T2 два пъти за отделна стойност на T1.val. Отново сложността на плана става квадратична. Изпълнението на заявката в SSMS с активирана статистика за включване на заявки на живо отне 49,6 секунди за обработка на 100 реда от T1 на моя лаптоп, което означава, че тази заявка трябва да отнеме около 5,7 дни, за да завърши. Това, разбира се, може да означава добра новина, ако се опитвате да счупите световния рекорд на Гинес за прекомерно гледане на план за заявка на живо.
Заключение
Бих искал да благодаря на Karen Ly от RBC, че ми представи това хубаво предизвикателство за най-близък мач. Бях доста впечатлен от нейния код за работа с него, който включваше много допълнителна логика, която беше специфична за нейната система. В тази статия показах разумно работещи решения, когато можете да създадете оптимални поддържащи индекси. Но както можете да видите, в случаите, когато това не е опция, очевидно времето за изпълнение, което получавате, е ужасно. Можете ли да измислите решения, които ще се справят добре дори без оптимални поддържащи индекси? Следва продължение...
