Karen Ly, en Jr. Fixed Income Analyst på RBC, gav mig en T-SQL-utmaning som innebär att hitta den närmaste matchningen, i motsats till att hitta en exakt matchning. I den här artikeln täcker jag en generaliserad, förenklad form av utmaningen.
Utmaningen
Utmaningen innebär att matcha rader från två tabeller, T1 och T2. Använd följande kod för att skapa en exempeldatabas som heter testdb, och i den tabellerna T1 och T2:
STÄLL IN NOCOUNT PÅ; OM DB_ID('testdb') ÄR NULL SKAPA DATABAS testdb; GÅ ANVÄND testdb; SLÄPP TABELL OM FINNS dbo.T1, dbo.T2; CREATE TABLE dbo.T1 (keycol INT INTE NULL IDENTITETSBEGRÄNSNING PK_T1 PRIMÄRNYCKEL, val INT INTE NULL, othercols BINARY(100) NOT NULL CONSTRAINT DFT_T1_col1 DEFAULT(0xAA) ); SKAPA TABELL dbo.T2 (nyckelkol INT INTE NULL IDENTITETSBEGRÄNSNING PK_T2 PRIMÄRNYCKEL, val INT INTE NULL, othercols BINARY(100) NOT NULL CONSTRAINT DFT_T2_col1 DEFAULT(0xBB) ); Som du kan se har både T1 och T2 en numerisk kolumn (INT-typ i detta exempel) som kallas val. Utmaningen är att till varje rad från T1 matcha raden från T2 där den absoluta skillnaden mellan T2.val och T1.val är som lägst. I händelse av oavgjort (flera matchande rader i T2), matcha den översta raden baserat på val stigande, keycol stigande ordning. Det vill säga raden med det lägsta värdet i valkolumnen, och om du fortfarande har oavgjort, raden med det lägsta keycol-värdet. Tiebreaken används för att garantera determinism.
Använd följande kod för att fylla i T1 och T2 med små uppsättningar exempeldata för att kunna kontrollera att dina lösningar är korrekta:
TRUNCATE TABLE dbo.T1; TRUNCATE TABELL dbo.T2; INSERT INTO dbo.T1 (val) VÄRDEN(1),(1),(3),(3),(5),(8),(13),(16),(18),(20),( 21); INSERT INTO dbo.T2 (val) VÄRDEN(2),(2),(7),(3),(3),(11),(11),(13),(17),(19);
Kontrollera innehållet i T1:
SELECT keycol, val, SUBSTRING(othercols, 1, 1) AS othercols FROM dbo.T1 ORDER BY val, keycol;
Denna kod genererar följande utdata:
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
Kontrollera innehållet i T2:
SELECT keycol, val, SUBSTRING(othercols, 1, 1) AS othercols FROM dbo.T2 ORDER BY val, keycol;
Denna kod genererar följande utdata:
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
Här är det önskade resultatet för givna exempeldata:
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 01 0x preInnan du börjar arbeta med utmaningen, undersök det önskade resultatet och se till att du förstår matchningslogiken, inklusive den oavgjorda logiken. Tänk till exempel på raden i T1 där keycol är 5 och val är 5. Den här raden har flera närmast matchningar i T2:
keycol val othercols ------------------ ----------- ---------- 4 3 0xBB 5 3 0xBB 3 7 0xBBI alla dessa rader är den absoluta skillnaden mellan T2.val och T1.val (5) 2. Med hjälp av tiebreaking-logiken baserad på ordningen val stigande, är keycol stigande den översta raden här den där val är 3 och keycol är 4.
Du kommer att använda de små uppsättningarna med exempeldata för att kontrollera giltigheten av dina lösningar. För att kontrollera prestanda behöver du större set. Använd följande kod för att skapa en hjälpfunktion som heter GetNums, som genererar en sekvens av heltal i ett begärt intervall:
DROP-FUNKTION OM FINNS dbo.GetNums; GÅ SKAPA ELLER ÄNDRA FUNKTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNER TABELL SOM RETUR MED L0 AS (VÄLJ c FRÅN (VÄLJ 1 UNION ALLA VÄLJ 1) SOM D(c)), L1 AS (VÄLJ 1 AS c FROM L0 AS A CROSS JOIN L0 AS B), L2 AS (VÄLJ 1 AS c FROM L1 AS A CROSS JOIN L1 AS B), L3 AS (VÄLJ 1 AS c FRÅN L2 SOM A CROSS JOIN L2 AS B), L4 SOM (VÄLJ 1 AS c FRÅN L3 SOM EN KORSKOPPLING L3 SOM B), L5 SOM (VÄLJ 1 SOM c FRÅN L4 SOM EN KORSKOPPLING L4 SOM B), Nums AS (VÄLJ ROW_NUMBER() ÖVER(ORDER BY (VÄLJ NULL) ) SOM radnummer FRÅN L5) VÄLJ TOP(@hög - @låg + 1) @låg + radnummer - 1 SOM n FRÅN NUMMER ORDER BY rownum; GÅAnvänd följande kod för att fylla i T1 och T2 med stora uppsättningar exempeldata:
DEKLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =10000000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =10000000; TRUNCATE TABELL dbo.T1; TRUNCATE TABELL 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;Variablerna @numrowsT1 och @numrowsT2 styr antalet rader du vill att tabellerna ska fyllas med. Variablerna @maxvalT1 och @maxvalT2 styr intervallet av distinkta värden i valkolumnen och påverkar därför kolumndensiteten. Ovanstående kod fyller tabellerna med 1 000 000 rader vardera och använder intervallet 1 – 10 000 000 för valkolumnen i båda tabellerna. Detta resulterar i låg densitet i kolumnen (stort antal distinkta värden, med ett litet antal dubbletter). Användning av lägre maxvärden kommer att resultera i högre densitet (mindre antal distinkta värden, och därmed fler dubbletter).
Lösning 1, med en TOP-underfråga
Den enklaste och mest uppenbara lösningen är förmodligen en som frågar T1, och med hjälp av CROSS APPLY-operatorn appliceras en fråga med ett TOP (1)-filter, som ordnar raderna efter den absoluta skillnaden mellan T1.val och T2.val, med T2.val , T2.keycol som tiebreaker. Här är lösningens kod:
SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1) ) SOM othercols2 FRÅN dbo.T1 CROSS APPLY ( VÄLJ TOP (1) T2.* FROM dbo.T2 ORDER BY ABS(T2.val - T1.val), T2.val, T2.keycol ) SOM A;Kom ihåg att det finns 1 000 000 rader i var och en av tabellerna. Och densiteten för valkolumnen är låg i båda tabellerna. Tyvärr, eftersom det inte finns något filtreringspredikat i den tillämpade frågan, och ordningen involverar ett uttryck som manipulerar kolumner, finns det ingen potential här att skapa stödjande index. Denna fråga genererar planen i figur 1.
Figur 1:Plan för lösning 1
Den yttre ingången på slingan skannar 1 000 000 rader från T1. Slingans inre ingång utför en fullständig avsökning av T2 och en TopN-sortering för varje distinkt T1.val-värde. I vår plan händer detta 998 657 gånger eftersom vi har mycket låg densitet. Den placerar raderna i en indexspool, nycklad av T1.val, så att den kan återanvända dem för dubbla förekomster av T1.val-värden, men vi har väldigt få dubbletter. Denna plan har kvadratisk komplexitet. Mellan alla förväntade avrättningar av den inre grenen av slingan förväntas den bearbeta nära en biljon rader. När du talar om ett stort antal rader för en fråga att bearbeta, när du börjar nämna miljarder rader, vet folk redan att du har att göra med en dyr fråga. Normalt uttalar folk inte termer som biljoner, såvida de inte diskuterar USA:s statsskuld eller börskrascher. Du hanterar vanligtvis inte sådana siffror i frågebehandlingssammanhang. Men planer med kvadratisk komplexitet kan snabbt sluta med sådana siffror. Att köra frågan i SSMS med Inkludera Live Query Statistics aktiverat tog 39,6 sekunder att bearbeta bara 100 rader från T1 på min bärbara dator. Det betyder att det bör ta denna fråga cirka 4,5 dagar att slutföra. Frågan är, är du verkligen intresserad av att titta på direktsända frågeplaner? Kan vara ett intressant Guinness-rekord att försöka sätta.
Lösning 2, med två TOP-underfrågor
Förutsatt att du är ute efter en lösning som tar sekunder, inte dagar, att slutföra, här är en idé. I det tillämpade tabelluttrycket förenar du två inre TOP (1)-frågor – en filtrerar en rad där T2.val
=T1.val (beställt efter T2.val, T2.keycol). Det är lätt att skapa index för att stödja sådana frågor genom att aktivera en enradssökning. Fortfarande inom det tillämpade tabelluttrycket, använd en yttre TOP (1)-fråga mot resultatet med två rader, baserat på ordningen ABS(D.val – T1.val), D.val, D.keycol. Det kommer att vara en TopN-sortering involverad, men den kommer att tillämpas på två rader åt gången. Här är de rekommenderade indexen för att stödja denna lösning:
CREATE INDEX idx_val_key PÅ dbo.T1(val, keycol) INCLUDE(othercols); CREATE INDEX idx_val_key PÅ dbo.T2(val, keycol) INCLUDE(othercols); CREATE INDEX idx_valD_key PÅ dbo.T2(val DESC, keycol) INCLUDE(othercols);Här är den fullständiga lösningskoden:
SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1) ) SOM othercols2 FRÅN dbo.T1 CROSS APPLY ( VÄLJ TOP (1) D.* FRÅN ( VÄLJ TOP (1) * FRÅN dbo.T2 WHERE T2.val=T1.val BESTÄLLS EFTER T2.val, T2.keycol ) SOM BESTÄLLS AV ABS(D.val - T1.val), D.val, D. keycol ) AS A; Kom ihåg att vi har 1 000 000 rader i varje tabell, där valkolumnen har värden i intervallet 1 – 10 000 000 (låg densitet) och optimala index på plats.
Planen för denna fråga visas i figur 2.
Figur 2:Plan för lösning 2
Observera optimal användning av indexen på T2, vilket resulterar i en plan med linjär skalning. Denna plan använder en indexspole på samma sätt som den tidigare planen gjorde, d.v.s. för att undvika att upprepa arbetet i den inre grenen av slingan för dubbla T1.val-värden. Här är prestandastatistiken som jag fick för körningen av den här frågan på mitt system:
Förfluten:27,7 sek, CPU:27,6 sek, logiska läsningar:17 304 674Lösning 2, med spooling inaktiverad
Du kan inte låta bli att undra om indexspolen verkligen är fördelaktig här. Poängen är att undvika att upprepa arbete för dubbletter av T1.val-värden, men i en situation som vår där vi har väldigt låg densitet är det väldigt få dubbletter. Detta innebär att arbetet med spoolning med största sannolikhet är större än att bara upprepa arbetet för dubbletter. Det finns ett enkelt sätt att verifiera detta – med hjälp av spårningsflagga 8690 kan du inaktivera spoolning i planen, så här:
SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1) ) SOM othercols2 FRÅN dbo.T1 CROSS APPLY ( VÄLJ TOP (1) D.* FRÅN ( VÄLJ TOP (1) * FRÅN dbo.T2 WHERE T2.val=T1.val BESTÄLLS EFTER T2.val, T2.keycol ) SOM BESTÄLLS AV ABS(D.val - T1.val), D.val, D. keycol ) SOM ETT ALTERNATIV(QUERYTRACEON 8690); Jag fick planen som visas i figur 3 för det här utförandet:
Figur 3:Plan för lösning 2, med spooling inaktiverad
Observera att indexspolen försvann, och den här gången exekveras den inre grenen av slingan 1 000 000 gånger. Här är prestandastatistiken som jag fick för den här körningen:
Förfluten:19,18 sek, CPU:19,17 sek, logiska läsningar:6 042 148Det är en minskning med 44 procent av genomförandetiden.
Lösning 2, med modifierat värdeintervall och indexering
Att inaktivera spooling är mycket meningsfullt när du har låg densitet i T1.val-värdena; dock kan spolningen vara mycket fördelaktig när du har hög densitet. Kör till exempel följande kod för att fylla på T1 och T2 med exempeldatainställningen @maxvalT1 och @maxvalT2 till 1000 (1 000 maximala distinkta värden):
DEKLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =1000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =1000; TRUNCATE TABELL dbo.T1; TRUNCATE TABELL 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;Kör lösning 2 igen, först utan spårningsflaggan:
SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1) ) SOM othercols2 FRÅN dbo.T1 CROSS APPLY ( VÄLJ TOP (1) D.* FRÅN ( VÄLJ TOP (1) * FRÅN dbo.T2 WHERE T2.val=T1.val BESTÄLLS EFTER T2.val, T2.keycol ) SOM BESTÄLLS AV ABS(D.val - T1.val), D.val, D. keycol ) AS A; Planen för detta utförande visas i figur 4:
Figur 4:Plan för lösning 2, med värdeintervall 1 – 1000
Optimeraren bestämde sig för att använda en annan plan på grund av den höga tätheten i T1.val. Observera att indexet på T1 skannas i nyckelordning. Så för varje första förekomst av ett distinkt T1.val-värde exekveras den inre grenen av slingan, och resultatet spoolas i en vanlig tabellspool (rebind). Sedan, för varje icke-första förekomst av värdet, tillämpas en tillbakaspolning. Med 1 000 distinkta värden exekveras den inre grenen endast 1 000 gånger. Detta resulterar i utmärkt prestandastatistik:
Förfluten:1,16 sek, CPU:1,14 sek, logiska läsningar:23 278Prova nu att köra lösningen med spooling inaktiverad:
SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1) ) SOM othercols2 FRÅN dbo.T1 CROSS APPLY ( VÄLJ TOP (1) D.* FRÅN ( VÄLJ TOP (1) * FRÅN dbo.T2 WHERE T2.val=T1.val BESTÄLLS EFTER T2.val, T2.keycol ) SOM BESTÄLLS AV ABS(D.val - T1.val), D.val, D. keycol ) SOM ETT ALTERNATIV(QUERYTRACEON 8690); Jag fick planen som visas i figur 5.
Figur 5:Plan för lösning 2, med värdeintervall 1 – 1 000 och spooling inaktiverad
Det är i princip samma plan som visades tidigare i figur 3. Den inre grenen av slingan exekveras 1 000 000 gånger. Här är prestandastatistiken som jag fick för den här körningen:
Förfluten:24,5 sek, CPU:24,2 sek, logiska läsningar:8 012 548Det är klart att du vill vara försiktig så att du inte inaktiverar spoolning när du har hög densitet i T1.val.
Livet är bra när din situation är enkel nog att du kan skapa stödjande index. Verkligheten är att det i vissa fall i praktiken finns tillräckligt med ytterligare logik i frågan, som utesluter möjligheten att skapa optimala stödjande index. I sådana fall kommer lösning 2 inte att fungera bra.
För att demonstrera prestandan för lösning 2 utan att stödja index, fyll tillbaka T1 och T2 med exempeldatainställningen @maxvalT1 och @maxvalT2 till 10000000 (värdeområde 1 – 10M), och ta även bort de stödjande indexen:
SLUTA INDEX OM FINNS idx_val_key PÅ dbo.T1; SLAPP INDEX OM FINNS idx_val_key PÅ dbo.T2; SLAPP INDEX OM FINNS idx_valD_key PÅ dbo.T2; DEKLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =10000000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =10000000; TRUNCATE TABELL dbo.T1; TRUNCATE TABELL 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;Kör om lösning 2, med Inkludera Live Query Statistics aktiverat i SSMS:
SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1) ) SOM othercols2 FRÅN dbo.T1 CROSS APPLY ( VÄLJ TOP (1) D.* FRÅN ( VÄLJ TOP (1) * FRÅN dbo.T2 WHERE T2.val=T1.val BESTÄLLS EFTER T2.val, T2.keycol ) SOM BESTÄLLS AV ABS(D.val - T1.val), D.val, D. keycol ) AS A; Jag fick planen som visas i figur 6 för denna fråga:
Figur 6:Plan för lösning 2, utan indexering, med värdeintervall 1 – 1 000 000
Du kan se ett mönster som är mycket likt det som visats tidigare i figur 1, men den här gången skannar planen T2 två gånger per distinkt T1.val-värde. Återigen blir planens komplexitet kvadratisk. Att köra frågan i SSMS med Inkludera Live Query Statistics aktiverat tog 49,6 sekunder att bearbeta 100 rader från T1 på min bärbara dator, vilket innebär att det borde ta den här frågan cirka 5,7 dagar att slutföra. Det här kan naturligtvis betyda goda nyheter om du försöker slå Guinness världsrekord för att titta på en direktsänd frågeplan.
Slutsats
Jag skulle vilja tacka Karen Ly från RBC för att hon presenterade mig för den här finaste matchen. Jag var ganska imponerad av hennes kod för att hantera den, som innehöll mycket extra logik som var specifik för hennes system. I den här artikeln visade jag rimligt presterande lösningar när du kan skapa optimala stödjande index. Men som du kunde se, i de fall där detta inte är ett alternativ, är uppenbarligen avrättningstiderna som du får urusla. Kan du komma på lösningar som kommer att fungera bra även utan optimala stödindex? Fortsättning följer...