Minulý měsíc jsem řešil hádanku, která zahrnovala shodu každého řádku z jedné tabulky s nejbližší shodou z jiné tabulky. Tuto hádanku jsem dostal od Karen Ly, Jr. analytičky s pevným příjmem v RBC. Zabýval jsem se dvěma hlavními relačními řešeními, která kombinovala operátor APPLY s poddotazy založenými na TOP. Řešení 1 mělo vždy kvadratické škálování. Řešení 2 si vedlo docela dobře, když bylo opatřeno dobrými podpůrnými indexy, ale bez těchto indexů mělo také kvadrické škálování. V tomto článku se zabývám iterativními řešeními, která navzdory tomu, že jsou profíci SQL obecně odsuzováni, poskytují v našem případě mnohem lepší škálování i bez optimálního indexování.

Výzva

Jako rychlé připomenutí, naše výzva zahrnuje tabulky nazvané T1 a T2, které vytvoříte pomocí následujícího kódu:

 SET NOCOUNT ON; IF DB_ID('testdb') JE NULL CREATE DATABASE testdb; GO USE testdb; DROP TABULKU, POKUD EXISTUJE dbo.T1, dbo.T2; CREATE TABLE dbo.T1 ( klíčový sloupec INT NOT NULL OMEZENÍ IDENTITY PK_T1 PRIMÁRNÍ KLÍČ, hodnota INT NOT NULL, ostatní sloupce BINARY(100) NOT NULL CONSTRAINT DFT_T1_col1 DEFAULT(0xAA) ); CREATE TABLE dbo.T2 ( keycol INT NOT NULL IDENTITY CONSTRAINT PK_T2 PRIMARY KEY, hodnota INT NOT NULL, othercols BINARY(100) NOT NULL CONSTRAINT DFT_T2_col1 DEFAULT(0xBB) );

Poté pomocí následujícího kódu naplníte tabulky malými sadami ukázkových dat, abyste zkontrolovali správnost svých řešení:

 TRUNCATE TABLE dbo.T1; TRUNCATE TABLE 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); 

 Připomeňme, že výzvou bylo přiřadit ke každému řádku z T1 řádek z T2, kde je absolutní rozdíl mezi T2.val a T1.val nejnižší. V případě nerozhodného výsledku byste měli jako nerozhodný výsledek použít val vzestupně, keycol vzestupné pořadí. 
 

 Zde je požadovaný výsledek pro daná ukázková data:
 
 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 BB19 0xAA 10 BB19 0x AA 10 BB19 0x 10 BB19 0x 10 BB 19 00x 

 Ke kontrole výkonu vašich řešení potřebujete větší sady vzorových dat. Nejprve vytvořte pomocnou funkci GetNums, která generuje sekvenci celých čísel v požadovaném rozsahu, pomocí následujícího kódu:
 
 DROP FUNCTION IF EXISTS dbo.GetNums; GO VYTVOŘIT NEBO ZMĚNIT FUNKCI dbo.GetNums(@nízká JAK VELKÁ, @vysoká JAKO BIGINT) VRÁTÍ TABULKU JAKO NÁVRAT S L0 JAKO (VYBRAT c Z (VYBRAT 1 UNION VŠECHNY VYBRAT 1) JAKO D(c)), L1 JAKO (VYBRAT 1 JAKO c OD L0 JAKO KŘÍŽOVÉ PŘIPOJENÍ L0 JAKO B), L2 JAKO (VYBERTE 1 JAKO C Z L1 JAKO KŘÍŽOVÉ SPOJE L1 JAKO B), L3 AS (VYBERTE 1 JAKO C Z L2 JAKO KŘÍŽOVÉ SPOJE L2 JAKO B), L4 AS (VYBERTE 1 JAKO c Z L3 JAKO CŘÍŽOVÉ PŘIPOJENÍ L3 JAKO B), L5 AS (VYBERTE 1 JAKO C Z L4 JAKO CŘÍŽOVÉ SPOJE L4 JAKO B), Nums AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL) ) AS rownum FROM L5) SELECT TOP(@high - @low + 1) @low + rownum - 1 AS n FROM Nums ORDER BY rownum; GO
 

 Poté vyplníte T1 a T2 pomocí následujícího kódu a upravíte parametry udávající počty řádků a maximální hodnoty podle vašich potřeb:
 
 DECLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =10000000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =10000000; TRUNCATE TABLE dbo.T1; TRUNCATE TABLE 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;
 

 V tomto příkladu naplňujete tabulky 1 000 000 řádky, přičemž hodnoty ve sloupci val (nízká hustota) jsou v rozsahu 1 – 10 000 000.
 
Řešení 3 s použitím kurzoru a diskové proměnné tabulky
 

 Efektivní iterativní řešení pro naši výzvu k nejbližší shodě je založeno na algoritmu podobném algoritmu sloučení. Myšlenkou je použít u každého stolu pouze jeden uspořádaný průchod pomocí kurzorů, vyhodnocení prvků pořadí a rozlosování v každém kole, aby se rozhodlo, na kterou stranu postoupíte, a porovnávání řad na cestě. 
 

 Uspořádaný průchod pro každou tabulku bude jistě těžit z podpory indexů, ale důsledek toho, že je nebudete mít, je, že bude probíhat explicitní řazení. To znamená, že třídící část bude mít n log n škálování, ale to je mnohem méně závažné než kvadratické škálování, které získáte z řešení 2 za podobných okolností.
 

 Také výkon řešení 1 a 2 byl ovlivněn hustotou valové kolony. S vyšší hustotou plán aplikoval méně převazů. Naopak, protože iterativní řešení provádějí pouze jeden průchod proti každému ze vstupů, hustota sloupce val není faktorem ovlivňujícím výkon.
 

 K vytvoření podpůrných indexů použijte následující kód:
 
 CREATE INDEX idx_val_key ON dbo.T1(val, keycol) INCLUDE(othercols); CREATE INDEX idx_val_key ON dbo.T2(val, keycol) INCLUDE(othercols);
 

 Ujistěte se, že testujete řešení jak s těmito indexy, tak bez nich.
 

 Zde je úplný kód pro řešení 3:
 
 SET NOCOUNT ON; ZAČÍT TRAN; DECLARE @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 AS CURSOR, @C2 AS CURSOR, @C1fetch_status AS INT, @C2fetch_status AS INT; DECLARE @Result AS TABLE ( keycol1 INT NOT NULL PRIMÁRNÍ KLÍČ, hodnota1 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 FOR SELECT keycol, val, othercols FROM dbo.T2 ORDER BY val, keycol; OPEN @C1; OPEN @C2; FETCH NEXT Z @C2 DO @keycol2, @val2, @othercols2; SET @C2fetch_status =@@fetch_status; SELECT @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2; FETCH NEXT Z @C1 DO @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; FETCH NEXT Z @C2 DO @keycol2, @val2, @othercols2; SET @C2fetch_status =@@fetch_status; KONEC; KONEC; SELECT keycol1, hodnota1, SUBSTRING(othercols1, 1, 1) AS othercols1, keycol2, val2, SUBSTRING(othercols2, 1, 1) AS othercols2 FROM @Result; COMMIT TRAN;
 

 Kód používá proměnnou tabulky s názvem @Result k uložení shod a nakonec je vrátí dotazem na proměnnou tabulky. Všimněte si, že kód provádí práci v jedné transakci, aby se snížilo protokolování. 
 

 Kód používá kurzorové proměnné nazvané @C1 a @C2 k iteraci řádků v T1 a T2, v obou případech seřazených podle val, keycol. Lokální proměnné se používají k uložení aktuálních hodnot řádku z každého kurzoru (@keycol1, @val1 a @othercols1 pro @C1 a @keycol2, @val2 a @othercols2 pro @C2). Další lokální proměnné ukládají hodnoty předchozího řádku z @C2 (@prevkeycol2, @prevval2 a @prevothercols2). Proměnné @C1fetch_status a @C2fetch_status drží stav posledního načtení z příslušného kurzoru.
 

 Po deklaraci a otevření obou kurzorů kód načte řádek z každého kurzoru do příslušných lokálních proměnných a zpočátku uloží aktuální hodnoty řádku z @C2 také do proměnných předchozího řádku. Kód poté vstoupí do smyčky, která běží, dokud bylo poslední načtení z @C1 úspěšné (@C1fetch_status =0). Tělo smyčky aplikuje v každém kole následující pseudokód:
 
 Pokud @val1 <=@val2 nebo dosáhl konce @C2 Begin Pokud je absolutní rozdíl mezi @val1 a @val2 menší než mezi @val1 a @prevval2 Přidejte řádek do @Výsledku s aktuálními hodnotami řádku z @C1 a aktuálním řádkem hodnoty z @C2 Else Přidat řádek do @Výsledek s aktuálními hodnotami řádku z @C1 a předchozími hodnotami řádku z @C2 Načíst další řádek z @C1 Konec Jinak, pokud bylo poslední načtení z @C2 úspěšné Začít, pokud @val2> @předchozí2 Nastavit držení proměnných Hodnoty předchozího řádku @C2 na hodnoty aktuálních proměnných řádku Načíst další řádek z @C2 End
 

 Kód se pak jednoduše dotáže na proměnnou tabulky @Result, aby vrátil všechny shody.
 

 Při použití velkých sad vzorových dat (1 000 000 řádků v každé tabulce) s optimálním indexováním trvalo dokončení tohoto řešení v mém systému 38 sekund a provedlo 28 240 logických čtení. Samozřejmě, že škálování tohoto řešení je pak lineární. Bez optimálního indexování trvalo dokončení 40 sekund (jen 2 sekundy navíc!) a provedlo 29 519 logických čtení. Třídicí část v tomto řešení má n log n měřítko.
 
Řešení 4, používající kurzor a proměnnou tabulky optimalizované pro paměť
 

 Ve snaze zlepšit výkon iterativního přístupu můžete zkusit jednu věc, a to nahradit použití proměnné tabulky založené na disku proměnnou optimalizovanou pro paměť. Vzhledem k tomu, že řešení zahrnuje zápis 1 000 000 řádků do proměnné tabulky, mohlo by to vést k nezanedbatelnému zlepšení. 
 

 Nejprve musíte povolit In-Memory OLTP v databázi vytvořením skupiny souborů, která je označena jako CONTAINS MEMORY_OPTIMIZED_DATA, a v ní kontejner, který ukazuje na složku v systému souborů. Za předpokladu, že jste předem vytvořili nadřazenou složku s názvem C:\IMOLTP\, použijte k provedení těchto dvou kroků následující kód:
 
 ALTER DATABASE testdb ADD FILEGROUP testdb_MO OBSAHUJE MEMORY_OPTIMIZED_DATA; ALTER DATABASE testdb PŘIDAT SOUBOR ( NAME =testdb_dir, FILENAME ='C:\IMOLTP\testdb_dir' ) DO FILEGROUP testdb_MO;
 

 Dalším krokem je vytvoření typu tabulky optimalizované pro paměť jako šablony pro naši proměnnou tabulky spuštěním následujícího kódu:
 
 DROP TYPE IF EXISTS dbo.TYPE_closestmatch; GO CREATE TYPE dbo.TYPE_closestmatch AS TABLE ( keycol1 INT NOT NULL PRIMÁRNÍ KLÍČ NONCLUSTERED, hodnota1 INT NOT NULL, othercols1 BINARY(100) NOT NULL, keycol2 INT NULL, othercols2 BINARY_100 =)WILLTIMIZEMOD );
 

 Potom byste místo původní deklarace proměnné tabulky @Result použili následující kód:
 
 DECLARE @Result AS dbo.TYPE_closestmatch;
 

 Zde je úplný kód řešení:
 
 SET NOCOUNT ON; USE testdb; ZAČÍT TRAN; DECLARE @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 AS CURSOR, @C2 AS 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 FROM dbo.T1 ORDER BY val, keycol; SET @C2 =CURSOR FORWARD_ONLY STATIC READ_ONLY FOR SELECT keycol, val, othercols FROM dbo.T2 ORDER BY val, keycol; OPEN @C1; OPEN @C2; FETCH NEXT Z @C2 DO @keycol2, @val2, @othercols2; SET @C2fetch_status =@@fetch_status; SELECT @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2; FETCH NEXT Z @C1 DO @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; FETCH NEXT Z @C2 DO @keycol2, @val2, @othercols2; SET @C2fetch_status =@@fetch_status; KONEC; KONEC; SELECT keycol1, hodnota1, SUBSTRING(othercols1, 1, 1) AS othercols1, keycol2, val2, SUBSTRING(othercols2, 1, 1) AS othercols2 FROM @Result; COMMIT TRAN;
 

 S optimálním indexováním trvalo dokončení tohoto řešení na mém počítači 27 sekund (ve srovnání s 38 sekundami s proměnnou tabulky založené na disku) a bez optimálního indexování trvalo dokončení 29 sekund (ve srovnání se 40 sekundami). To je téměř 30procentní zkrácení doby běhu.
 
Řešení 5 s použitím SQL CLR
 

 Dalším způsobem, jak dále zlepšit výkon iterativního přístupu, je implementace řešení pomocí SQL CLR, vzhledem k tomu, že většina režie řešení T-SQL je způsobena neefektivitou načítání kurzoru a smyčkování v T-SQL.
 

 Zde je úplný kód řešení implementující stejný algoritmus, který jsem použil v řešeních 3 a 4 s C#, s použitím objektů SqlDataReader namísto kurzorů T-SQL:
 
 pomocí System; pomocí System.Data; pomocí System.Data.SqlClient; pomocí System.Data.SqlTypes; pomocí Microsoft.SqlServer.Server; public částečná třída ClosestMatch { [SqlProcedure] public static void GetClosestMatches() { using (SqlConnection conn =new SqlConnection("data source=MyServer\\MyInstance;Database=testdb;Trusted_Connection=True;MultipleActiveResultSets);)CommultSets {=truecomm =new SqlCommand(); SqlCommand comm2 =new SqlCommand(); comm1.Connection =conn; comm2.Connection =conn; comm1.CommandText ="SELECT keycol, val, othercols FROM dbo.T1 ORDER BY val, keycol;"; comm2.CommandText ="SELECT keycol, val, othercols FROM dbo.T2 ORDER BY val, keycol;"; SqlMetaData[] sloupce =new 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); Záznam SqlDataRecord =new SqlDataRecord(columns); SqlContext.Pipe.SendResultsStart(záznam); 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 =čtenář2.GetSqlInt32(1); othercols2 =reader2.GetSqlBinary(2); prevkeycol2 =keycol2; prevval2 =val2; prevothercols2 =othercols2; } Boolean reader1foundrow =reader1.Read(); if (reader1foundrow) { keycol1 =reader1.GetSqlInt32(0); val1 =čtenář1.GetSqlInt32(1); othercols1 =reader1.GetSqlBinary(2); } while (reader1foundrow) { if (val1 <=hodnota2 || !reader2foundrow) { if (Math.Abs((int)(val1 - val2))  prevval2) { prevkeycol2 =keycol2; prevval2 =val2; prevothercols2 =othercols2; } reader2foundrow =čtenář2.Read(); if (reader2foundrow) { keycol2 =reader2.GetSqlInt32(0); val2 =čtenář2.GetSqlInt32(1); othercols2 =reader2.GetSqlBinary(2); } } } SqlContext.Pipe.SendResultsEnd(); } } }
 

 Pro připojení k databázi byste normálně použili volbu "context connection=true" namísto úplného připojovacího řetězce. Tato možnost bohužel není dostupná, když potřebujete pracovat s více aktivními sadami výsledků. Naše řešení emulující paralelní práci se dvěma kurzory pomocí dvou objektů SqlDataReader, a proto potřebujete úplný připojovací řetězec s možností MultipleActiveResultSets=true. Zde je úplný připojovací řetězec:
 
 "zdroj dat=MyServer\\MyInstance;Database=testdb;Trusted_Connection=True;MultipleActiveResultSets=true;"
 

 Samozřejmě ve vašem případě budete muset nahradit MyServer\\MyInstance názvy vašeho serveru a instance (pokud jsou relevantní).
 

 Také skutečnost, že jste nepoužili "context connection=true" spíše explicitní připojovací řetězec, znamená, že sestavení potřebuje přístup k externímu zdroji, a proto musí být důvěryhodné. Normálně byste toho dosáhli tak, že jej podepíšete certifikátem nebo asymetrickým klíčem, který má odpovídající přihlášení se správným oprávněním, nebo jej zařadíte na seznam povolených pomocí procedury sp_add_trusted_assembly. Pro jednoduchost nastavím volbu databáze DŮVĚRYHODNÉ na ZAPNUTO a při vytváření sestavy určím sadu oprávnění EXTERNAL_ACCESS. Následující kód nasadí řešení do databáze:
 
 EXEC sys.sp_configure 'pokročilé', 1; PŘENASTAVIT; EXEC sys.sp_configure 'clr povoleno', 1; EXEC sys.sp_configure 'clr strict security', 0; PŘENASTAVIT; EXEC sys.sp_configure 'pokročilé', 0; PŘENASTAVIT; ALTER DATABASE testdb NASTAVIT DŮVĚRYHODNÉ ZAPNUTO; USE testdb; DROP PROC IF EXISTS dbo.GetClosestMatches; DROP MONTÁŽ, POKUD EXISTUJE ClosestMatch; VYTVOŘTE SESTAVENÍ ClosestMatch Z 'C:\ClosestMatch\ClosestMatch\bin\Debug\ClosestMatch.dll' S POVOLENOU_SET =EXTERNAL_ACCESS; GO VYTVOŘENÍ dbo.GetClosestMatches JAKO EXTERNÍ NÁZEV ClosestMatch.ClosestMatch.GetClosestMatches;
 

 Kód povolí CLR v instanci, zakáže přísnou možnost zabezpečení CLR, nastaví volbu databáze TRUSTWORTHY na ON, vytvoří sestavení a vytvoří proceduru GetClosestMatches.
 

 K otestování uložené procedury použijte následující kód:
 
 EXEC dbo.GetClosestMatches;
 

 Dokončení řešení CLR na mém systému s optimální indexací trvalo 8 sekund a bez 9 sekund. To je docela působivé zlepšení výkonu ve srovnání se všemi ostatními řešeními – jak relačními, tak iterativními.
 
Závěr
 

 Iterativní řešení jsou typicky odsuzována v komunitě SQL, protože se neřídí relačním modelem. Skutečností však je, že někdy nejste schopni vytvořit dobře fungující relační řešení a výkon je prioritou. Při použití iterativního přístupu nejste omezeni na algoritmy, ke kterým má optimalizátor SQL Server přístup, ale můžete implementovat libovolný algoritmus, který chcete. Jak je ukázáno v tomto článku, pomocí algoritmu podobného sloučení jste byli schopni dosáhnout úkolu jediným uspořádaným průchodem proti každému ze vstupů. Pomocí kurzorů T-SQL a diskové proměnné tabulky jste získali přiměřený výkon a škálování. Přepnutím na proměnnou tabulky optimalizované pro paměť jste byli schopni zlepšit výkon asi o 30 procent a výrazně více pomocí SQL CLR.