Förra månaden lade jag ett pussel som gick ut på att matcha varje rad från ett bord med den närmast matchningen från ett annat bord. Jag fick det här pusslet från Karen Ly, en Jr. Fixed Income Analyst på RBC. Jag täckte två huvudsakliga relationslösningar som kombinerade APPLY-operatorn med TOP-baserade underfrågor. Lösning 1 hade alltid kvadratisk skalning. Lösning 2 klarade sig ganska bra när den försågs med bra stödjande index, men utan dessa index hade den också kvadrisk skalning. I den här artikeln tar jag upp iterativa lösningar, som trots att de i allmänhet är ogillade av SQL-proffs, ger mycket bättre skalning i vårt fall även utan optimal indexering.

Utmaningen

Som en snabb påminnelse omfattar vår utmaning tabeller som heter T1 och T2, som du skapar med följande kod:

 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) );

Du använder sedan följande kod för att fylla i tabellerna med små uppsättningar exempeldata för att 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);

Minns utmaningen var att till varje rad från T1 matcha raden från T2 där den absoluta skillnaden mellan T2.val och T1.val är den lägsta. I fall av oavgjort, är det meningen att du ska använda val stigande, keycol stigande ordning som tiebreaker.

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 pre  

 För att kontrollera prestanda för dina lösningar behöver du större uppsättningar exempeldata. Du skapar först hjälpfunktionen GetNums, som genererar en sekvens av heltal i ett begärt intervall, med hjälp av följande kod:
 
 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Å
 

 Du fyller sedan i T1 och T2 med följande kod och justerar parametrarna som anger antalet rader och maximala värden baserat på dina behov:
 
 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;
 

 I det här exemplet fyller du i tabellerna med 1 000 000 rader vardera, med värden i intervallet 1 – 10 000 000 i valkolumnen (låg densitet).
 
Lösning 3, med en markör och en diskbaserad tabellvariabel
 

 En effektiv iterativ lösning för vår närmaste matchutmaning är baserad på en algoritm som liknar algoritmen Merge join. Tanken är att bara lägga ett ordnat pass mot varje bord med hjälp av markörer, utvärdera ordnings- och tiebreaking-elementen i varje omgång för att avgöra på vilken sida man ska avancera, och matcha raderna längs vägen. 
 

 Det ordnade passet mot varje tabell kommer säkert att gynnas av stödjande index, men innebörden av att inte ha dessa är att explicit sortering kommer att äga rum. Detta innebär att sorteringsdelen kommer att medföra n log n-skalning, men det är mycket mindre allvarlig än den kvadratiska skalningen som du får från lösning 2 under liknande omständigheter.
 

 Prestandan för lösningar 1 och 2 påverkades också av valkolonnens densitet. Med högre densitet applicerade planen färre återbindningar. Omvänt, eftersom de iterativa lösningarna endast utför ett pass mot var och en av ingångarna, är densiteten för valkolumnen inte en prestationspåverkande faktor.
 

 Använd följande kod för att skapa stödjande index:
 
 CREATE INDEX idx_val_key PÅ dbo.T1(val, keycol) INCLUDE(othercols); SKAPA INDEX idx_val_key PÅ dbo.T2(val, keycol) INCLUDE(othercols);
 

 Se till att du testar lösningarna både med och utan dessa index.
 

 Här är den fullständiga koden för lösning 3:
 
 STÄLL IN NOCOUNT PÅ; BÖRJA TRAN; DEKLARE @keycol1 AS INT, @val1 AS INT, @othercols1 AS BINARY(100), @keycol2 AS INT, @val2 AS INT, @othercols2 AS BINARY(100), @prevkeycol2 AS INT, @prevval2 AS INT, @prevothercols2 AS BINARY(100), @C1 SOM MARKÖR, @C2 SOM MARKÖR, @C1fetch_status SOM INT, @C2fetch_status SOM INT; DECLARE @Result SOM TABELL ( keycol1 INT NOT NULL PRIMÄRKEY, val1 INT NOT NULL, othercols1 BINARY(100) NOT NULL, keycol2 INT NULL, val2 INT NULL, othercols2 BINARY(100) NULL ); SET @C1 =CURSOR FORWARD_ONLY STATIC READ_ONLY FOR SELECT keycol, val, othercols FROM dbo.T1 ORDER BY val, keycol; SET @C2 =CURSOR FORWARD_ONLY STATIC READ_ONLY FÖR SELECT keycol, val, othercols FROM dbo.T2 ORDER BY val, keycol; ÖPPNA @C1; ÖPPNA @C2; HÄMTA NÄSTA FRÅN @C2 INTO @keycol2, @val2, @othercols2; SET @C2fetch_status =@@fetch_status; SELECT @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2; HÄMTA NÄSTA FRÅN @C1 INTO @keycol1, @val1, @othercols1; SET @C1fetch_status =@@fetch_status; WHILE @C1fetch_status =0 BEGIN IF @val1 <=@val2 OR @C2fetch_status <> 0 BEGIN IF ABS(@val1 - @val2)  @prevval2 SELECT @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2; HÄMTA NÄSTA FRÅN @C2 INTO @keycol2, @val2, @othercols2; SET @C2fetch_status =@@fetch_status; SLUTET; SLUTET; SELECT keycol1, val1, SUBSTRING(othercols1, 1, 1) AS othercols1, keycol2, val2, SUBSTRING(othercols2, 1, 1) AS othercols2 FROM @Result; BETA ÖVERFÖRING;
 

 Koden använder en tabellvariabel som heter @Result för att lagra matchningarna och returnerar dem så småningom genom att fråga tabellvariabeln. Observera att koden utför arbetet i en transaktion för att minska loggningen. 
 

 Koden använder markörvariabler som kallas @C1 och @C2 för att iterera genom rader i T1 respektive T2, i båda fallen sorterade efter val, keycol. Lokala variabler används för att lagra de aktuella radvärdena från varje markör (@keycol1, @val1 och @othercols1 för @C1, och @keycol2, @val2 och @othercols2 för @C2). Ytterligare lokala variabler lagrar de föregående radvärdena från @C2 (@prevkeycol2, @prevval2 och @prevothercols2). Variablerna @C1fetch_status och @C2fetch_status håller statusen för den senaste hämtningen från respektive markör.
 

 Efter att ha deklarerat och öppnat båda markörerna hämtar koden en rad från varje markör till respektive lokala variabler och lagrar initialt de aktuella radvärdena från @C2 även i föregående radvariabler. Koden går sedan in i en loop som fortsätter att köras medan den senaste hämtningen från @C1 lyckades (@C1fetch_status =0). Slingans kropp tillämpar följande pseudokod i varje omgång:
 
 Om @val1 <=@val2 eller nått slutet av @C2 Börja Om den absoluta skillnaden mellan @val1 och @val2 är mindre än mellan @val1 och @prevval2 Lägg till rad till @Resultat med aktuella radvärden från @C1 och aktuell rad värden från @C2 Annars Lägg till rad till @Resultat med aktuella radvärden från @C1 och föregående radvärden från @C2 Hämta nästa rad från @C1 Sluta annars om senaste hämtning från @C2 lyckades Börja If @val2> @prevval2 Ställ in variabler som håller @C2s föregående radvärden till värden för aktuella radvariabler Hämta nästa rad från @C2 End
 

 Koden frågar sedan helt enkelt tabellvariabeln @Result för att returnera alla matchningar.
 

 Genom att använda de stora uppsättningarna av exempeldata (1 000 000 rader i varje tabell), med optimal indexering på plats, tog den här lösningen 38 sekunder att slutföra på mitt system och utförde 28 240 logiska läsningar. Naturligtvis är skalningen av denna lösning linjär. Utan optimal indexering tog det 40 sekunder att slutföra (endast 2 sekunder extra!), och utförde 29 519 logiska avläsningar. Sorteringsdelen i denna lösning har n log n-skalning.
 
Lösning 4, med en markör och en minnesoptimerad tabellvariabel
 

 I ett försök att förbättra prestandan för det iterativa tillvägagångssättet är en sak du kan prova att ersätta användningen av den diskbaserade tabellvariabeln med en minnesoptimerad. Eftersom lösningen innebär att man skriver 1 000 000 rader till tabellvariabeln kan detta resultera i en icke försumbar förbättring. 
 

 Först måste du aktivera In-Memory OLTP i databasen genom att skapa en filgrupp som är markerad som CONTAINS MEMORY_OPTIMIZED_DATA, och inom den en behållare som pekar på en mapp i filsystemet. Om du antar att du har skapat en överordnad mapp som heter C:\IMOLTP\ använder du följande kod för att tillämpa dessa två steg:
 
 ALTER DATABASE testdb ADD FILEGROUP testdb_MO INNEHÅLLER MEMORY_OPTIMIZED_DATA; ALTER DATABASE testdb LÄGG TILL FIL (NAMN =testdb_dir, FILNAMN ='C:\IMOLTP\testdb_dir') TILL FILGRUPPER testdb_MO;
 

 Nästa steg är att skapa en minnesoptimerad tabelltyp som en mall för vår tabellvariabel genom att köra följande kod:
 
 SLUTA TYP OM FINNS dbo.TYPE_closestmatch; GÅ SKAPA TYP dbo.TYPE_closestmatch SOM TABELL (keycol1 INT NOT NULL PRIMÄRKEY ICLUSTERED, val1 INT NOT NULL, othercols1 BINARY(100) NOT NULL, keycol2 INT NULL, val2 INT NULL, othercols2 BINARY (10MEZEN) );
 

 Då skulle du istället för den ursprungliga deklarationen av tabellvariabeln @Result använda följande kod:
 
 DECLARE @Result AS dbo.TYPE_closestmatch;
 

 Här är den fullständiga lösningskoden:
 
 STÄLL IN NOCOUNT PÅ; ANVÄND testdb; BÖRJA TRAN; DEKLARE @keycol1 AS INT, @val1 AS INT, @othercols1 AS BINARY(100), @keycol2 AS INT, @val2 AS INT, @othercols2 AS BINARY(100), @prevkeycol2 AS INT, @prevval2 AS INT, @prevothercols2 AS BINARY(100), @C1 SOM MARKÖR, @C2 SOM MARKÖR, @C1fetch_status SOM INT, @C2fetch_status SOM INT; DECLARE @Result AS dbo.TYPE_closestmatch; SET @C1 =CURSOR FORWARD_ONLY STATIC READ_ONLY FOR SELECT keycol, val, othercols FROM dbo.T1 ORDER BY val, keycol; SET @C2 =CURSOR FORWARD_ONLY STATIC READ_ONLY FÖR SELECT keycol, val, othercols FROM dbo.T2 ORDER BY val, keycol; ÖPPNA @C1; ÖPPNA @C2; HÄMTA NÄSTA FRÅN @C2 INTO @keycol2, @val2, @othercols2; SET @C2fetch_status =@@fetch_status; SELECT @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2; HÄMTA NÄSTA FRÅN @C1 INTO @keycol1, @val1, @othercols1; SET @C1fetch_status =@@fetch_status; WHILE @C1fetch_status =0 BEGIN IF @val1 <=@val2 OR @C2fetch_status <> 0 BEGIN IF ABS(@val1 - @val2)  @prevval2 SELECT @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2; HÄMTA NÄSTA FRÅN @C2 INTO @keycol2, @val2, @othercols2; SET @C2fetch_status =@@fetch_status; SLUTET; SLUTET; SELECT keycol1, val1, SUBSTRING(othercols1, 1, 1) AS othercols1, keycol2, val2, SUBSTRING(othercols2, 1, 1) AS othercols2 FROM @Result; BETA ÖVERFÖRING;
 

 Med den optimala indexeringen på plats tog den här lösningen 27 sekunder att slutföra på min maskin (jämfört med 38 sekunder med den diskbaserade tabellvariabeln), och utan optimal indexering tog det 29 sekunder att slutföra (jämfört med 40 sekunder). Det är nära 30 procents minskning av körtiden.
 
Lösning 5, med SQL CLR
 

 Ett annat sätt att ytterligare förbättra prestandan för det iterativa tillvägagångssättet är att implementera lösningen med SQL CLR, med tanke på att det mesta av T-SQL-lösningens omkostnader beror på ineffektiviteten med markörhämtning och looping i T-SQL.
 

 Här är den fullständiga lösningskoden som implementerar samma algoritm som jag använde i lösningar 3 och 4 med C#, med SqlDataReader-objekt istället för T-SQL-markörer:
 
 använder System; använder System.Data; använder System.Data.SqlClient; använder System.Data.SqlTypes; använder Microsoft.SqlServer.Server; public partial class ClosestMatch { [SqlProcedure] public static void GetClosestMatches() { using (SqlConnection conn =new SqlConnection("data source=MyServer\\MyInstance;Database=testdb;Trusted_Connection=True;MultipleActiveResultSets)=trueSql; =new SqlCommand(); SqlCommand comm2 =new SqlCommand(); comm1.Anslutning =anslutning; comm2.Anslutning =anslutning; comm1.CommandText ="VÄLJ keycol, val, othercols FROM dbo.T1 ORDER BY val, keycol;"; comm2.CommandText ="VÄLJ keycol, val, othercols FROM dbo.T2 ORDER BY val, keycol;"; SqlMetaData[] kolumner =new SqlMetaData[6]; kolumner[0] =new SqlMetaData("keycol1", SqlDbType.Int); kolumner[1] =new SqlMetaData("val1", SqlDbType.Int); kolumner[2] =new SqlMetaData("othercols1", SqlDbType.Binary, 100); kolumner[3] =new SqlMetaData("keycol2", SqlDbType.Int); kolumner[4] =new SqlMetaData("val2", SqlDbType.Int); kolumner[5] =new SqlMetaData("othercols2", SqlDbType.Binary, 100); SqlDataRecord record =new SqlDataRecord(kolumner); SqlContext.Pipe.SendResultsStart(record); conn.Open(); SqlDataReader reader1 =comm1.ExecuteReader(); SqlDataReader reader2 =comm2.ExecuteReader(); SqlInt32 keycol1 =SqlInt32.Null; SqlInt32 val1 =SqlInt32.Null; SqlBinary othercols1 =SqlBinary.Null; SqlInt32 keycol2 =SqlInt32.Null; SqlInt32 val2 =SqlInt32.Null; SqlBinary othercols2 =SqlBinary.Null; SqlInt32 prevkeycol2 =SqlInt32.Null; SqlInt32 prevval2 =SqlInt32.Null; SqlBinary prevothercols2 =SqlBinary.Null; Boolean reader2foundrow =reader2.Read(); if (reader2foundrow) { keycol2 =reader2.GetSqlInt32(0); val2 =läsare2.GetSqlInt32(1); othercols2 =reader2.GetSqlBinary(2); prevkeycol2 =keycol2; prevval2 =val2; prevothercols2 =othercols2; } Boolean reader1foundrow =reader1.Read(); if (reader1foundrow) { keycol1 =reader1.GetSqlInt32(0); val1 =läsare1.GetSqlInt32(1); othercols1 =reader1.GetSqlBinary(2); } while (reader1foundrow) { if (val1 <=val2 || !reader2foundrow) { if (Math.Abs((int)(val1 - val2))  prevval2) { prevkeycol2 =keycol2; prevval2 =val2; prevothercols2 =othercols2; } reader2foundrow =reader2.Read(); if (reader2foundrow) { keycol2 =reader2.GetSqlInt32(0); val2 =läsare2.GetSqlInt32(1); othercols2 =reader2.GetSqlBinary(2); } } } SqlContext.Pipe.SendResultsEnd(); } } }
 

 För att ansluta till databasen skulle du normalt använda alternativet "context connection=true" istället för en fullständig anslutningssträng. Tyvärr är det här alternativet inte tillgängligt när du behöver arbeta med flera aktiva resultatuppsättningar. Vår lösning som emulerar parallellt fungerar med två markörer som använder två SqlDataReader-objekt, och därför behöver du en fullständig anslutningssträng, med alternativet MultipleActiveResultSets=true. Här är hela anslutningssträngen:
 
 "data source=MyServer\\MyInstance;Database=testdb;Trusted_Connection=True;MultipleActiveResultSets=true;"
 

 Naturligtvis i ditt fall skulle du behöva ersätta MyServer\\MyInstance med din server och instansnamn (om relevant).
 

 Det faktum att du inte använde "context connection=true" snarare en explicit anslutningssträng betyder att sammansättningen behöver åtkomst till en extern resurs och därför är pålitlig. Normalt skulle du uppnå detta genom att signera det med ett certifikat eller en asymmetrisk nyckel som har en motsvarande inloggning med rätt behörighet, eller vitlista den med sp_add_trusted_assembly-proceduren. För enkelhetens skull kommer jag att ställa in databasalternativet TRUSTWORTHY till ON och ange EXTERNAL_ACCESS-behörighetsuppsättningen när du skapar sammansättningen. Följande kod distribuerar lösningen i databasen:
 
 EXEC sys.sp_configure 'avancerad', 1; KONFIGURERA OM; EXEC sys.sp_configure 'clr enabled', 1; EXEC sys.sp_configure 'clr strikt säkerhet', 0; KONFIGURERA OM; EXEC sys.sp_configure 'avancerad', 0; KONFIGURERA OM; ALTER DATABASE testdb STÄLL PÅ TROLIGT; ANVÄND testdb; SLIP PROC OM FINNS dbo.GetClosestMatches; SLUTA MONTERING OM FINNS ClosestMatch; SKAPA ENHET ClosestMatch FRÅN 'C:\ClosestMatch\ClosestMatch\bin\Debug\ClosestMatch.dll' MED PERMISSION_SET =EXTERNAL_ACCESS; GÅ SKAPA PROCEDUR dbo.GetClosestMatches SOM EXTERNT NAMN ClosestMatch.ClosestMatch.GetClosestMatches;
 

 Koden aktiverar CLR i instansen, inaktiverar CLR strikt säkerhetsalternativ, ställer in databasalternativet TRUSTWORTHY till ON, skapar sammansättningen och skapar proceduren GetClosestMatches.
 

 Använd följande kod för att testa den lagrade proceduren:
 
 EXEC dbo.GetClosestMatches;
 

 CLR-lösningen tog 8 sekunder att slutföra på mitt system med optimal indexering och 9 sekunder utan. Det är en ganska imponerande prestandaförbättring jämfört med alla andra lösningar – både relationella och iterativa.
 
Slutsats
 

 Iterativa lösningar är vanligtvis ogillade i SQL-gemenskapen eftersom de inte följer den relationella modellen. Verkligheten är dock att man ibland inte kan skapa bra presterande relationslösningar och prestation är en prioritet. Genom att använda ett iterativt tillvägagångssätt är du inte begränsad till de algoritmer som SQL Server-optimeraren har tillgång till, utan kan snarare implementera vilken algoritm du vill. Som visas i den här artikeln, med hjälp av en sammanslagningsliknande algoritm, kunde du uppnå uppgiften med ett enda ordnat pass mot var och en av ingångarna. Genom att använda T-SQL-markörer och en diskbaserad tabellvariabel fick du rimlig prestanda och skalning. Du kunde förbättra prestandan med cirka 30 procent genom att byta till en minnesoptimerad tabellvariabel, och betydligt mer genom att använda SQL CLR.