I sidste måned dækkede jeg et puslespil, der involverede at matche hver række fra et bord med det nærmeste match fra et andet bord. Jeg fik dette puslespil fra Karen Ly, en Jr. Fixed Income Analyst hos RBC. Jeg dækkede to primære relationelle løsninger, der kombinerede APPLY-operatoren med TOP-baserede underforespørgsler. Løsning 1 havde altid kvadratisk skalering. Løsning 2 klarede sig ret godt, når den var forsynet med gode understøttende indekser, men uden disse indekser havde den også quadric skalering. I denne artikel dækker jeg iterative løsninger, som på trods af at de generelt er ildeset af SQL-professionelle, giver meget bedre skalering i vores tilfælde selv uden optimal indeksering.

Udfordringen

Som en hurtig påmindelse involverer vores udfordring tabeller kaldet T1 og T2, som du opretter med følgende kode:

 INDSTIL ANTAL TIL; HVIS DB_ID('testdb') ER NULL OPRET DATABASE testdb; GÅ BRUG testdb; DROP TABEL HVIS FINDER dbo.T1, dbo.T2; OPRET TABEL dbo.T1 ( keycol INT IKKE NULL IDENTITETSBEGRÆNSNING PK_T1 PRIMÆR NØGLE, val INT IKKE NULL, othercols BINARY(100) IKKE NULL BEGRÆNSNING DFT_T1_col1 DEFAULT(0xAA) ); OPRET TABEL dbo.T2 ( keycol INT IKKE NULL IDENTITETSBEGRÆNSNING PK_T2 PRIMÆR NØGLE, val INT IKKE NULL, othercols BINARY(100) IKKE NULL BEGRÆNSNING DFT_T2_col1 DEFAULT(0xBB) );

Du bruger derefter følgende kode til at udfylde tabellerne med små sæt eksempeldata for at kontrollere rigtigheden af ​​dine løsninger:

 TRUNCATE TABLE dbo.T1; TRUNCATE TABEL dbo.T2; INSERT INTO dbo.T1 (val) VALUES(1),(1),(3),(3),(5),(8),(13),(16),(18),(20),( 21); INSERT INTO dbo.T2 (val) VALUES(2),(2),(7),(3),(3),(11),(11),(13),(17),(19);

Husk, at udfordringen var at matche rækken fra T2 til hver række fra T1, hvor den absolutte forskel mellem T2.val og T1.val er den laveste. I tilfælde af uafgjort, er det meningen, at du skal bruge val ascending, keycol stigende rækkefølge som tiebreaker.

Her er det ønskede resultat for de givne eksempeldata:

 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 10 19 01 0BB 

 For at kontrollere ydeevnen af ​​dine løsninger har du brug for større sæt prøvedata. Du opretter først hjælpefunktionen GetNums, som genererer en sekvens af heltal i et anmodet område ved hjælp af følgende kode:
 
 DROP-FUNKTION HVIS FINDER dbo.GetNums; GÅ OPRET ELLER ÆNDRE FUNKTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNERER TABEL SOM RETURNERING MED L0 AS (VÆLG c FRA (VÆLG 1 UNION ALLE VÆLG 1) SOM D(c)), L1 AS (VÆLG 1 SOM c FRA L0 SOM EN KRYDSJOIN L0 AS B), L2 AS (VÆLG 1 SOM c FRA L1 SOM EN KRYDSJOIN L1 SOM B), L3 AS (VÆLG 1 AS c FRA L2 SOM KRYDSFIND L2 SOM B), L4 AS (VÆLG 1 AS c FRA L3 SOM A CROSS JOIN L3 AS B), L5 AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B), Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL) ) SOM rækkenummer FRA L5) VÆLG TOP(@høj - @lav + 1) @lav + rækkenummer - 1 SOM n FRA numre BESTIL EFTER rækkenummer; GÅ
 

 Du udfylder derefter T1 og T2 ved hjælp af følgende kode, og justerer parametrene, der angiver antallet af rækker og maksimale værdier baseret på dine behov:
 
 DEKLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =10000000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =10000000; TRUNCATE TABEL dbo.T1; TRUNCATE 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;
 

 I dette eksempel udfylder du tabellerne med hver 1.000.000 rækker med værdier i intervallet 1 – 10.000.000 i valkolonnen (lav tæthed).
 
Løsning 3, ved hjælp af en markør og en diskbaseret tabelvariabel
 

 En effektiv iterativ løsning til vores tætteste match-udfordring er baseret på en algoritme svarende til Merge join-algoritmen. Ideen er kun at anvende én ordnet aflevering mod hvert bord ved hjælp af markører, evaluere rækkefølgen og tiebreaking-elementerne i hver runde for at beslutte, i hvilken side man skal rykke frem, og matche rækkerne undervejs. 
 

 Den bestilte pas mod hver tabel vil helt sikkert drage fordel af at understøtte indekser, men implikationen af ​​ikke at have dem er, at eksplicit sortering vil finde sted. Det betyder, at sorteringsdelen vil pådrage sig n log n skalering, men det er meget mindre alvorlig end den kvadratiske skalering, du får fra løsning 2 under lignende omstændigheder.
 

 Ydeevnen af ​​opløsning 1 og 2 blev også påvirket af tætheden af ​​val-kolonnen. Med højere tæthed anvendte planen færre genbindinger. Omvendt, da de iterative løsninger kun udfører én gennemgang mod hver af inputs, er tætheden af ​​val-kolonnen ikke en præstationspåvirkende faktor.
 

 Brug følgende kode til at oprette understøttende indekser:
 
 CREATE INDEX idx_val_key ON dbo.T1(val, keycol) INCLUDE(othercols); OPRET INDEX idx_val_key PÅ dbo.T2(val, keycol) INCLUDE(othercols);
 

 Sørg for at teste løsningerne både med og uden disse indekser.
 

 Her er den komplette kode til løsning 3:
 
 INDSTIL ANTAL TIL; BEGIN 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 CURSOR, @C2 SOM CURSOR, @C1fetch_status AS INT, @C2fetch_status AS INT; DECLARE @Result AS TABLE ( keycol1 INT IKKE NULL PRIMÆR NØGLE, val1 INT IKKE 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 FRA dbo.T1 BESTIL EFTER val, keycol; SET @C2 =CURSOR FORWARD_ONLY STATIC READ_ONLY FOR SELECT keycol, val, othercols FRA dbo.T2 BESTIL EFTER val, keycol; ÅBN @C1; ÅBN @C2; FETCH NEXT FROM @C2 INTO @keycol2, @val2, @othercols2; SET @C2fetch_status =@@fetch_status; VÆLG @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2; FETCH NEXT FROM @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 VÆLG @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2; FETCH NEXT FROM @C2 INTO @keycol2, @val2, @othercols2; SET @C2fetch_status =@@fetch_status; ENDE; ENDE; SELECT keycol1, val1, SUBSTRING(othercols1, 1, 1) AS othercols1, keycol2, val2, SUBSTRING(othercols2, 1, 1) AS othercols2 FROM @Result; FORBIND OVERFØRSEL;
 

 Koden bruger en tabelvariabel kaldet @Result til at gemme kampene og returnerer dem til sidst ved at forespørge tabelvariablen. Bemærk, at koden udfører arbejdet i én transaktion for at reducere logning. 
 

 Koden bruger markørvariabler kaldet @C1 og @C2 til at iterere gennem rækker i henholdsvis T1 og T2, i begge tilfælde sorteret efter val, keycol. Lokale variabler bruges til at gemme de aktuelle rækkeværdier fra hver markør (@keycol1, @val1 og @othercols1 for @C1, og @keycol2, @val2 og @othercols2 for @C2). Yderligere lokale variabler gemmer de foregående rækkeværdier fra @C2 (@prevkeycol2, @prevval2 og @prevothercols2). Variablerne @C1fetch_status og @C2fetch_status holder status for den sidste hentning fra den respektive markør.
 

 Efter at have erklæret og åbnet begge markører, henter koden en række fra hver markør ind i de respektive lokale variabler og gemmer til at begynde med de aktuelle rækkeværdier fra @C2 også i de foregående rækkevariabler. Koden går derefter ind i en løkke, der bliver ved med at køre, mens den sidste hentning fra @C1 var vellykket (@C1fetch_status =0). Løkkens krop anvender følgende pseudokode i hver runde:
 
 Hvis @val1 <=@val2 eller nåede slutningen af ​​@C2 Start Hvis den absolutte forskel mellem @val1 og @val2 er mindre end mellem @val1 og @prevval2 Tilføj række til @Resultat med aktuelle rækkeværdier fra @C1 og nuværende række værdier fra @C2 Else Tilføj række til @Resultat med aktuelle rækkeværdier fra @C1 og forrige rækkeværdier fra @C2 Hent næste række fra @C1 Slut Else hvis sidste hentning fra @C2 lykkedes Start If @val2> @prevval2 Indstil variabler @C2's forrige rækkeværdier til værdier af aktuelle rækkevariable Hent næste række fra @C2 End
 

 Koden forespørger derefter blot tabelvariablen @Result for at returnere alle matches.
 

 Ved at bruge de store sæt eksempeldata (1.000.000 rækker i hver tabel), med optimal indeksering på plads, tog denne løsning 38 sekunder at fuldføre på mit system og udførte 28.240 logiske aflæsninger. Selvfølgelig er skaleringen af ​​denne løsning lineær. Uden optimal indeksering tog det 40 sekunder at gennemføre (kun 2 sekunder ekstra!), og udførte 29.519 logiske aflæsninger. Sorteringsdelen i denne løsning har n log n skalering.
 
Løsning 4 ved hjælp af en markør og en hukommelsesoptimeret tabelvariabel
 

 I et forsøg på at forbedre ydeevnen af ​​den iterative tilgang, er en ting du kan prøve at erstatte brugen af ​​den diskbaserede tabelvariabel med en hukommelsesoptimeret. Da løsningen involverer at skrive 1.000.000 rækker til tabelvariablen, kan dette resultere i en ikke ubetydelig forbedring. 
 

 Først skal du aktivere In-Memory OLTP i databasen ved at oprette en filgruppe, der er markeret som CONTAINS MEMORY_OPTIMIZED_DATA, og i den en container, der peger på en mappe i filsystemet. Hvis du antager, at du forud har oprettet en overordnet mappe kaldet C:\IMOLTP\, skal du bruge følgende kode til at anvende disse to trin:
 
 ALTER DATABASE testdb TILFØJ FILGROUP testdb_MO INDEHOLDER MEMORY_OPTIMIZED_DATA; ÆNDRE DATABASE testdb TILFØJ FIL (NAVN =testdb_dir, FILENAME ='C:\IMOLTP\testdb_dir') TIL FILGRUPPE testdb_MO;
 

 Det næste trin er at oprette en hukommelsesoptimeret tabeltype som skabelon for vores tabelvariabel ved at køre følgende kode:
 
 DROP TYPE HVIS FINDER dbo.TYPE_closestmatch; GÅ OPRET TYPE dbo.TYPE_closestmatch SOM TABEL ( keycol1 INT IKKE NULL PRIMÆR NØGLE IKKE KLUNGERET, val1 INT IKKE NULL, othercols1 BINARY(100) NOT NULL, keycol2 INT NULL, val2 INT NULL, othercols2 BINARY (10MINE0) );
 

 Så i stedet for den oprindelige erklæring af tabelvariablen @Result, ville du bruge følgende kode:
 
 DECLARE @Result AS dbo.TYPE_closestmatch;
 

 Her er den komplette løsningskode:
 
 INDSTIL ANTAL TIL; BRUG testdb; BEGIN 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 CURSOR, @C2 SOM CURSOR, @C1fetch_status AS INT, @C2fetch_status AS INT; DECLARE @Result AS dbo.TYPE_closestmatch; SET @C1 =CURSOR FORWARD_ONLY STATIC READ_ONLY FOR SELECT keycol, val, othercols FRA dbo.T1 BESTIL EFTER val, keycol; SET @C2 =CURSOR FORWARD_ONLY STATIC READ_ONLY FOR SELECT keycol, val, othercols FRA dbo.T2 BESTIL EFTER val, keycol; ÅBN @C1; ÅBN @C2; FETCH NEXT FROM @C2 INTO @keycol2, @val2, @othercols2; SET @C2fetch_status =@@fetch_status; VÆLG @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2; FETCH NEXT FROM @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 VÆLG @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2; FETCH NEXT FROM @C2 INTO @keycol2, @val2, @othercols2; SET @C2fetch_status =@@fetch_status; ENDE; ENDE; SELECT keycol1, val1, SUBSTRING(othercols1, 1, 1) AS othercols1, keycol2, val2, SUBSTRING(othercols2, 1, 1) AS othercols2 FROM @Result; FORBIND OVERFØRSEL;
 

 Med den optimale indeksering på plads tog denne løsning 27 sekunder at gennemføre på min maskine (sammenlignet med 38 sekunder med den diskbaserede tabelvariabel), og uden optimal indeksering tog det 29 sekunder at gennemføre (sammenlignet med 40 sekunder). Det er tæt på 30 procents reduktion i køretiden.
 
Løsning 5, ved hjælp af SQL CLR
 

 En anden måde at forbedre ydeevnen af ​​den iterative tilgang yderligere på er at implementere løsningen ved hjælp af SQL CLR, eftersom det meste af overheaden i T-SQL-løsningen skyldes ineffektiviteten ved cursorhentning og looping i T-SQL.
 

 Her er den komplette løsningskode, der implementerer den samme algoritme, som jeg brugte i løsninger 3 og 4 med C#, ved at bruge SqlDataReader-objekter i stedet for T-SQL-markører:
 
 ved hjælp af System; ved hjælp af System.Data; ved hjælp af System.Data.SqlClient; ved hjælp af System.Data.SqlTypes; bruger 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)=truml; =ny SqlCommand(); SqlCommand comm2 =ny SqlCommand(); comm1.Forbindelse =tilslutning; comm2.Forbindelse =tilslutning; comm1.CommandText ="VÆLG keycol, val, othercols FRA dbo.T1 BESTIL EFTER val, keycol;"; comm2.CommandText ="VÆLG keycol, val, othercols FRA dbo.T2 BESTIL EFTER val, keycol;"; SqlMetaData[] kolonner =ny SqlMetaData[6]; columns[0] =new SqlMetaData("keycol1", SqlDbType.Int); columns[1] =new SqlMetaData("val1", SqlDbType.Int); columns[2] =new SqlMetaData("othercols1", SqlDbType.Binary, 100); columns[3] =new SqlMetaData("keycol2", SqlDbType.Int); columns[4] =new SqlMetaData("val2", SqlDbType.Int); columns[5] =new SqlMetaData("othercols2", SqlDbType.Binary, 100); SqlDataRecord record =new SqlDataRecord(kolonner); 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æser2.GetSqlInt32(1); othercols2 =reader2.GetSqlBinary(2); prevkeycol2 =keycol2; prævval2 =val2; prevothercols2 =othercols2; } Boolean reader1foundrow =reader1.Read(); if (reader1foundrow) { keycol1 =reader1.GetSqlInt32(0); val1 =læser1.GetSqlInt32(1); othercols1 =reader1.GetSqlBinary(2); } while (reader1foundrow) { if (val1 <=val2 || !reader2foundrow) { if (Math.Abs((int)(val1 - val2))  prevval2) { prevkeycol2 =keycol2; prævval2 =val2; prevothercols2 =othercols2; } reader2foundrow =reader2.Read(); if (reader2foundrow) { keycol2 =reader2.GetSqlInt32(0); val2 =læser2.GetSqlInt32(1); othercols2 =reader2.GetSqlBinary(2); } } } SqlContext.Pipe.SendResultsEnd(); } } }
 

 For at oprette forbindelse til databasen ville du normalt bruge indstillingen "context connection=true" i stedet for en komplet forbindelsesstreng. Desværre er denne mulighed ikke tilgængelig, når du skal arbejde med flere aktive resultatsæt. Vores løsning, der emulerer parallelt arbejde med to markører ved hjælp af to SqlDataReader-objekter, og derfor har du brug for en komplet forbindelsesstreng med muligheden MultipleActiveResultSets=true. Her er den fulde forbindelsesstreng:
 
 "data source=MyServer\\MyInstance;Database=testdb;Trusted_Connection=True;MultipleActiveResultSets=true;"
 

 I dit tilfælde skal du selvfølgelig erstatte MyServer\\MyInstance med dine server- og instansnavne (hvis relevant).
 

 Også det faktum, at du ikke brugte "context connection=true" snarere en eksplicit forbindelsesstreng, betyder, at samlingen har brug for adgang til en ekstern ressource og derfor er tillid til. Normalt ville du opnå dette ved at signere det med et certifikat eller en asymmetrisk nøgle, der har et tilsvarende login med den rigtige tilladelse, eller hvidliste det ved at bruge sp_add_trusted_assembly-proceduren. For nemheds skyld vil jeg sætte databaseindstillingen TRUSTWORTHY til ON, og angive EXTERNAL_ACCESS-tilladelsessættet, når du opretter forsamlingen. Følgende kode implementerer løsningen i databasen:
 
 EXEC sys.sp_configure 'avanceret', 1; REKONFIGURER; EXEC sys.sp_configure 'clr aktiveret', 1; EXEC sys.sp_configure 'clr strict security', 0; REKONFIGURER; EXEC sys.sp_configure 'avanceret', 0; REKONFIGURER; ALTER DATABASE testdb INDSTILLE TROLIGT TIL; BRUG testdb; DROP PROC HVIS FINDER dbo.GetClosestMatches; SLIP SAMLING HVIS FINDER ClosestMatch; OPRET ASSEMBLE ClosestMatch FRA 'C:\ClosestMatch\ClosestMatch\bin\Debug\ClosestMatch.dll' MED PERMISSION_SET =EXTERNAL_ACCESS; GÅ OPRET PROCEDURE dbo.GetClosestMatches SOM EKSTERNT NAVN ClosestMatch.ClosestMatch.GetClosestMatches;
 

 Koden aktiverer CLR i instansen, deaktiverer den strenge sikkerhedsindstilling CLR, sætter databaseindstillingen TRUSTWORTHY til TIL, opretter samlingen og opretter proceduren GetClosestMatches.
 

 Brug følgende kode til at teste den lagrede procedure:
 
 EXEC dbo.GetClosestMatches;
 

 CLR-løsningen tog 8 sekunder at fuldføre på mit system med optimal indeksering og 9 sekunder uden. Det er en ret imponerende forbedring af ydeevnen sammenlignet med alle andre løsninger – både relationelle og iterative.
 
Konklusion
 

 Iterative løsninger er typisk ilde set i SQL-fællesskabet, da de ikke følger den relationelle model. Virkeligheden er dog, at nogle gange er du ikke i stand til at skabe gode relationelle løsninger, og ydeevne er en prioritet. Ved at bruge en iterativ tilgang er du ikke begrænset til de algoritmer, som SQL Server optimizer har adgang til, men kan snarere implementere enhver algoritme, som du kan lide. Som vist i denne artikel var du ved at bruge en flettelignende algoritme i stand til at opnå opgaven med et enkelt ordnet gennemløb mod hver af inputs. Ved at bruge T-SQL-markører og en disk-baseret tabelvariabel fik du rimelig ydeevne og skalering. Du var i stand til at forbedre ydeevnen med omkring 30 procent ved at skifte til en hukommelsesoptimeret tabelvariabel og væsentligt mere ved at bruge SQL CLR.