先月、あるテーブルの各行を別のテーブルの最も近い行と一致させるパズルについて説明しました。このパズルは、RBCのジュニア債券アナリストであるKarenLyから入手しました。 APPLY演算子とTOPベースのサブクエリを組み合わせた2つの主要なリレーショナルソリューションについて説明しました。ソリューション1には常に2次スケーリングがありました。ソリューション2は、適切なサポートインデックスが提供されている場合は非常にうまく機能しましたが、これらのインデックスがないと、2次スケーリングもありました。この記事では、SQLの専門家に一般的に嫌われているにもかかわらず、最適なインデックス作成がなくても、この場合ははるかに優れたスケーリングを提供する反復ソリューションについて説明します。
課題
簡単に言うと、私たちの課題には、次のコードで作成するT1およびT2というテーブルが含まれます。
SET NOCOUNT ON;
IF DB_ID('testdb') IS NULL
CREATE DATABASE testdb;
GO
USE testdb;
DROP TABLE IF EXISTS 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
CONSTRAINT 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
CONSTRAINT DFT_T2_col1 DEFAULT(0xBB)
); 次に、次のコードを使用して、ソリューションの正確さを確認するために、サンプルデータの小さなセットをテーブルに入力します。
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); 課題は、T1の各行をT2.valとT1.valの絶対差が最も小さいT2の行に一致させることであったことを思い出してください。同点の場合、タイブレーカーとしてval昇順、keycol昇順を使用することになっています。
与えられたサンプルデータの望ましい結果は次のとおりです。
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 11 21 0xAA 10 19 0xBB
ソリューションのパフォーマンスを確認するには、より多くのサンプルデータのセットが必要です。最初に、次のコードを使用して、要求された範囲の整数のシーケンスを生成するヘルパー関数GetNumsを作成します。
DROP FUNCTION IF EXISTS dbo.GetNums;
GO
CREATE OR ALTER FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNS TABLE
AS
RETURN
WITH
L0 AS (SELECT c FROM (SELECT 1 UNION ALL SELECT 1) AS D(c)),
L1 AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),
L2 AS (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),
L3 AS (SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),
L4 AS (SELECT 1 AS c FROM L3 AS 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)) AS rownum
FROM L5)
SELECT TOP(@high - @low + 1) @low + rownum - 1 AS n
FROM Nums
ORDER BY rownum;
GO 次に、次のコードを使用してT1とT2にデータを入力し、必要に応じて行数と最大値を示すパラメーターを調整します。
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; この例では、テーブルにそれぞれ1,000,000行を入力し、val列に1〜10,000,000の範囲の値を設定しています（低密度）。
解決策3、カーソルとディスクベースのテーブル変数を使用
最も近い一致の課題に対する効率的な反復ソリューションは、マージ結合アルゴリズムと同様のアルゴリズムに基づいています。アイデアは、カーソルを使用して各テーブルに対して1つの順序付きパスのみを適用し、各ラウンドの順序要素とタイブレーク要素を評価してどちらの側に進むかを決定し、途中で行を一致させることです。
各テーブルに対する順序付きパスは、インデックスをサポートすることで確かにメリットがありますが、インデックスがないことの意味は、明示的な並べ替えが行われることです。これは、並べ替え部分でn log nスケーリングが発生することを意味しますが、同様の状況でソリューション2から得られる2次スケーリングよりもはるかに深刻ではありません。
また、ソリューション1および2のパフォーマンスは、valカラムの密度の影響を受けました。密度が高くなると、プランで適用される再バインドは少なくなります。逆に、反復ソリューションは各入力に対して1回のパスしか実行しないため、val列の密度はパフォーマンスに影響を与える要因ではありません。
次のコードを使用して、サポートするインデックスを作成します。
CREATE INDEX idx_val_key ON dbo.T1(val, keycol) INCLUDE(othercols); CREATE INDEX idx_val_key ON dbo.T2(val, keycol) INCLUDE(othercols);
これらのインデックスがある場合とない場合の両方でソリューションをテストしてください。
ソリューション3の完全なコードは次のとおりです。
SET NOCOUNT ON;
BEGIN 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 PRIMARY KEY,
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 FOR
SELECT keycol, val, othercols FROM dbo.T2 ORDER BY val, keycol;
OPEN @C1;
OPEN @C2;
FETCH NEXT FROM @C2 INTO @keycol2, @val2, @othercols2;
SET @C2fetch_status = @@fetch_status;
SELECT @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) < ABS(@val1 - @prevval2)
INSERT INTO @Result(keycol1, val1, othercols1, keycol2, val2, othercols2)
VALUES(@keycol1, @val1, @othercols1, @keycol2, @val2, @othercols2);
ELSE
INSERT INTO @Result(keycol1, val1, othercols1, keycol2, val2, othercols2)
VALUES(@keycol1, @val1, @othercols1, @prevkeycol2, @prevval2, @prevothercols2);
FETCH NEXT FROM @C1 INTO @keycol1, @val1, @othercols1;
SET @C1fetch_status = @@fetch_status;
END
ELSE IF @C2fetch_status = 0
BEGIN
IF @val2 > @prevval2
SELECT @prevkeycol2 = @keycol2, @prevval2 = @val2, @prevothercols2 = @othercols2;
FETCH NEXT FROM @C2 INTO @keycol2, @val2, @othercols2;
SET @C2fetch_status = @@fetch_status;
END;
END;
SELECT
keycol1, val1, SUBSTRING(othercols1, 1, 1) AS othercols1,
keycol2, val2, SUBSTRING(othercols2, 1, 1) AS othercols2
FROM @Result;
COMMIT TRAN; このコードは、@ Resultというテーブル変数を使用して一致を格納し、最終的にはテーブル変数をクエリしてそれらを返します。コードが1つのトランザクションで作業を実行して、ロギングを削減していることに注意してください。
このコードは、@C1および@C2と呼ばれるカーソル変数を使用して、それぞれT1およびT2の行を反復処理します。どちらの場合も、val、keycolの順に並べられます。ローカル変数は、各カーソルからの現在の行の値を格納するために使用されます（@C1の場合は@keycol1、@ val1、@ othercols1、@C2の場合は@keycol2、@ val2、@ othercols2）。追加のローカル変数は、@ C2（@ prevkeycol2、@ prevval2、および@ prevothercols2）からの前の行の値を格納します。変数@C1fetch_statusと@C2fetch_statusは、それぞれのカーソルからの最後のフェッチのステータスを保持します。
両方のカーソルを宣言して開いた後、コードは各カーソルからそれぞれのローカル変数に行をフェッチし、最初に@C2からの現在の行の値を前の行変数にも格納します。次に、コードはループに入り、@ C1からの最後のフェッチが成功している間（@ C1fetch_status =0）実行を続けます。ループの本体は、各ラウンドで次の擬似コードを適用します。
If @val1 <= @val2 or reached end of @C2
Begin
If absolute difference between @val1 and @val2 is less than between @val1 and @prevval2
Add row to @Result with current row values from @C1 and current row values from @C2
Else
Add row to @Result with current row values from @C1 and previous row values from @C2
Fetch next row from @C1
End
Else if last fetch from @C2 was successful
Begin
If @val2 > @prevval2
Set variables holding @C2’s previous row values to values of current row variables
Fetch next row from @C2
End 次に、コードはテーブル変数@Resultをクエリして、すべての一致を返します。
最適なインデックスが設定されたサンプルデータの大規模なセット（各テーブルに1,000,000行）を使用すると、このソリューションはシステムで完了するのに38秒かかり、28,240の論理読み取りを実行しました。もちろん、このソリューションのスケーリングは線形です。最適なインデックス作成がないと、完了までに40秒かかり（わずか2秒余分に！）、29,519の論理読み取りを実行しました。このソリューションの並べ替え部分には、nlognスケーリングがあります。
解決策4、カーソルとメモリ最適化テーブル変数を使用
反復アプローチのパフォーマンスを向上させるために試みることができる1つのことは、ディスクベースのテーブル変数の使用をメモリ最適化されたものに置き換えることです。このソリューションでは、テーブル変数に1,000,000行を書き込む必要があるため、これにより、無視できない改善がもたらされる可能性があります。
まず、CONTAINS MEMORY_OPTIMIZED_DATAとしてマークされたファイルグループを作成し、その中にファイルシステム内のフォルダーを指すコンテナーを作成して、データベースでインメモリOLTPを有効にする必要があります。 C：\ IMOLTP \という親フォルダーを先に作成したとすると、次のコードを使用して次の2つの手順を適用します。
ALTER DATABASE testdb
ADD FILEGROUP testdb_MO CONTAINS MEMORY_OPTIMIZED_DATA;
ALTER DATABASE testdb
ADD FILE ( NAME = testdb_dir,
FILENAME = 'C:\IMOLTP\testdb_dir' )
TO FILEGROUP testdb_MO; 次のステップは、次のコードを実行して、テーブル変数のテンプレートとしてメモリ最適化テーブルタイプを作成することです。
DROP TYPE IF EXISTS dbo.TYPE_closestmatch;
GO
CREATE TYPE dbo.TYPE_closestmatch AS TABLE
(
keycol1 INT NOT NULL PRIMARY KEY NONCLUSTERED,
val1 INT NOT NULL,
othercols1 BINARY(100) NOT NULL,
keycol2 INT NULL,
val2 INT NULL,
othercols2 BINARY(100) NULL
)
WITH (MEMORY_OPTIMIZED = ON); 次に、テーブル変数@Resultの元の宣言の代わりに、次のコードを使用します。
DECLARE @Result AS dbo.TYPE_closestmatch;
完全なソリューションコードは次のとおりです。
SET NOCOUNT ON;
USE testdb;
BEGIN 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 FROM @C2 INTO @keycol2, @val2, @othercols2;
SET @C2fetch_status = @@fetch_status;
SELECT @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) < ABS(@val1 - @prevval2)
INSERT INTO @Result(keycol1, val1, othercols1, keycol2, val2, othercols2)
VALUES(@keycol1, @val1, @othercols1, @keycol2, @val2, @othercols2);
ELSE
INSERT INTO @Result(keycol1, val1, othercols1, keycol2, val2, othercols2)
VALUES(@keycol1, @val1, @othercols1, @prevkeycol2, @prevval2, @prevothercols2);
FETCH NEXT FROM @C1 INTO @keycol1, @val1, @othercols1;
SET @C1fetch_status = @@fetch_status;
END
ELSE IF @C2fetch_status = 0
BEGIN
IF @val2 > @prevval2
SELECT @prevkeycol2 = @keycol2, @prevval2 = @val2, @prevothercols2 = @othercols2;
FETCH NEXT FROM @C2 INTO @keycol2, @val2, @othercols2;
SET @C2fetch_status = @@fetch_status;
END;
END;
SELECT
keycol1, val1, SUBSTRING(othercols1, 1, 1) AS othercols1,
keycol2, val2, SUBSTRING(othercols2, 1, 1) AS othercols2
FROM @Result;
COMMIT TRAN; 最適なインデックスが設定されている場合、このソリューションは私のマシンで完了するのに27秒かかり（ディスクベースのテーブル変数の場合は38秒）、最適なインデックスがない場合は完了するのに29秒かかりました（40秒と比較して）。これにより、実行時間が30％近く短縮されます。
SQLCLRを使用したソリューション5
反復アプローチのパフォーマンスをさらに向上させる別の方法は、SQL CLRを使用してソリューションを実装することです。これは、T-SQLソリューションのオーバーヘッドのほとんどが、T-SQLでのカーソルのフェッチとループの非効率性によるものであるためです。
>これは、T-SQLカーソルの代わりにSqlDataReaderオブジェクトを使用して、C＃でソリューション3および4で使用したものとまったく同じアルゴリズムを実装する完全なソリューションコードです。
using System;
using System.Data;
using System.Data.SqlClient;
using System.Data.SqlTypes;
using 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=true;"))
{
SqlCommand comm1 = 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[] columns = 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);
SqlDataRecord record = new SqlDataRecord(columns);
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 = reader2.GetSqlInt32(1);
othercols2 = reader2.GetSqlBinary(2);
prevkeycol2 = keycol2;
prevval2 = val2;
prevothercols2 = othercols2;
}
Boolean reader1foundrow = reader1.Read();
if (reader1foundrow)
{
keycol1 = reader1.GetSqlInt32(0);
val1 = reader1.GetSqlInt32(1);
othercols1 = reader1.GetSqlBinary(2);
}
while (reader1foundrow)
{
if (val1 <= val2 || !reader2foundrow)
{
if (Math.Abs((int)(val1 - val2)) < Math.Abs((int)(val1 - prevval2)))
{
record.SetSqlInt32(0, keycol1);
record.SetSqlInt32(1, val1);
record.SetSqlBinary(2, othercols1);
record.SetSqlInt32(3, keycol2);
record.SetSqlInt32(4, val2);
record.SetSqlBinary(5, othercols2);
SqlContext.Pipe.SendResultsRow(record);
}
else
{
record.SetSqlInt32(0, keycol1);
record.SetSqlInt32(1, val1);
record.SetSqlBinary(2, othercols1);
record.SetSqlInt32(3, prevkeycol2);
record.SetSqlInt32(4, prevval2);
record.SetSqlBinary(5, prevothercols2);
SqlContext.Pipe.SendResultsRow(record);
}
reader1foundrow = reader1.Read();
if (reader1foundrow)
{
keycol1 = reader1.GetSqlInt32(0);
val1 = reader1.GetSqlInt32(1);
othercols1 = reader1.GetSqlBinary(2);
}
}
else if (reader2foundrow)
{
if (val2 > prevval2)
{
prevkeycol2 = keycol2;
prevval2 = val2;
prevothercols2 = othercols2;
}
reader2foundrow = reader2.Read();
if (reader2foundrow)
{
keycol2 = reader2.GetSqlInt32(0);
val2 = reader2.GetSqlInt32(1);
othercols2 = reader2.GetSqlBinary(2);
}
}
}
SqlContext.Pipe.SendResultsEnd();
}
}
} データベースに接続するには、通常、本格的な接続文字列ではなく、オプション「contextconnection=true」を使用します。残念ながら、このオプションは、複数のアクティブな結果セットを操作する必要がある場合は使用できません。 2つのSqlDataReaderオブジェクトを使用して2つのカーソルで並列作業をエミュレートするソリューションでは、したがって、オプションMultipleActiveResultSets=trueを使用した本格的な接続文字列が必要です。完全な接続文字列は次のとおりです：
"data source=MyServer\\MyInstance;Database=testdb;Trusted_Connection=True;MultipleActiveResultSets=true;"
もちろん、あなたの場合、MyServer \\ MyInstanceをサーバーとインスタンス（該当する場合）の名前に置き換える必要があります。
また、明示的な接続文字列ではなく「context connection =true」を使用しなかったという事実は、アセンブリが外部リソースにアクセスする必要があるため、信頼できることを意味します。通常、これを実現するには、適切な権限を持つ対応するログインを持つ証明書または非対称キーを使用して署名するか、sp_add_trusted_assemblyプロシージャを使用してホワイトリストに登録します。簡単にするために、データベースオプションTRUSTWORTHYをONに設定し、アセンブリの作成時にEXTERNAL_ACCESS権限セットを指定します。次のコードは、ソリューションをデータベースにデプロイします。
EXEC sys.sp_configure 'advanced', 1;
RECONFIGURE;
EXEC sys.sp_configure 'clr enabled', 1;
EXEC sys.sp_configure 'clr strict security', 0;
RECONFIGURE;
EXEC sys.sp_configure 'advanced', 0;
RECONFIGURE;
ALTER DATABASE testdb SET TRUSTWORTHY ON;
USE testdb;
DROP PROC IF EXISTS dbo.GetClosestMatches;
DROP ASSEMBLY IF EXISTS ClosestMatch;
CREATE ASSEMBLY ClosestMatch
FROM 'C:\ClosestMatch\ClosestMatch\bin\Debug\ClosestMatch.dll'
WITH PERMISSION_SET = EXTERNAL_ACCESS;
GO
CREATE PROCEDURE dbo.GetClosestMatches
AS EXTERNAL NAME ClosestMatch.ClosestMatch.GetClosestMatches; このコードは、インスタンスでCLRを有効にし、CLRの厳密なセキュリティオプションを無効にし、データベースオプションTRUSTWORTHYをONに設定し、アセンブリを作成し、プロシージャGetClosestMatchesを作成します。
次のコードを使用して、ストアドプロシージャをテストします。
EXEC dbo.GetClosestMatches;
CLRソリューションは、最適なインデックスを作成したシステムで完了するのに8秒かかり、インデックスを作成しない場合は9秒かかりました。これは、リレーショナルおよび反復の両方で、他のすべてのソリューションと比較して非常に印象的なパフォーマンスの向上です。
結論
反復ソリューションは、リレーショナルモデルに準拠していないため、SQLコミュニティでは一般的に嫌われています。ただし、実際には、パフォーマンスの高いリレーショナルソリューションを作成できない場合があり、パフォーマンスが優先されます。反復アプローチを使用すると、SQL Serverオプティマイザーがアクセスできるアルゴリズムに限定されず、任意のアルゴリズムを実装できます。この記事で示されているように、マージのようなアルゴリズムを使用すると、各入力に対して1回の順序付きパスでタスクを実行できました。 T-SQLカーソルとディスクベースのテーブル変数を使用すると、妥当なパフォーマンスとスケーリングが得られます。メモリ最適化テーブル変数に切り替えることでパフォーマンスを約30％向上させ、SQLCLRを使用することでパフォーマンスを大幅に向上させることができました。