/* This script relates to the following DBA.StackExchange answer: http://dba.stackexchange.com/questions/131759/is-there-a-sql-server-implementation-of-the-longest-common-substring-problem/131766#131766 This script provides several performance / scalability tests for the [LongestCommonSubstring] User-Defined Aggregate (UDA). A T-SQL installation script (no external DLL) containing only the User-Defined Aggregate (UDA) is located at: http://pastebin.com/wnLwT1GM The source code for the [LongestCommonSubstring] User-Defined Aggregate (UDA) is located at: http://pastebin.com/ceDypBp0 Date: 2016-03-17 Version: 1.0.3 For more functions like this, please visit: http://SQLsharp.com Copyright (c) 2016 Sql Quantum Leap. All rights reserved. http://www.SqlQuantumLeap.com */ /* -- CLEAN UP (if needed) USE [ {your_database_name} ]; */ SET ANSI_NULLS, ANSI_PADDING, ANSI_WARNINGS, ARITHABORT, CONCAT_NULL_YIELDS_NULL, QUOTED_IDENTIFIER ON; SET NOCOUNT ON; GO USE [ {your_database_name} ]; GO ------------------------------------------------------------------------------------- -- Original @MisterMagoo Test ------------------------------------------------------------------------------------- /* -- Highlight and execute the following once IF (OBJECT_ID('tempdb..#ShortStrings') IS NOT NULL) BEGIN PRINT N'Dropping #ShortStrings table...'; DROP TABLE #ShortStrings; END; PRINT N'Creating and Populating #ShortStrings table...'; CREATE TABLE #ShortStrings ( [ShortStringsID] INT NOT NULL IDENTITY(1, 1) PRIMARY KEY, [String] sysname COLLATE DATABASE_DEFAULT NULL ); INSERT INTO #ShortStrings ([String]) SELECT sac.[Name] AS [String] FROM master.sys.all_columns sac CROSS JOIN master.sys.indexes si1 CROSS JOIN master.sys.indexes si2 WHERE sac.[Name] LIKE N'%refer%'; -- 1,213,488 rows on SQL Server 2014 SELECT COUNT(*) FROM #ShortStrings; */ /* Any NULLs mean there is not a "longest common string" */ IF (EXISTS(SELECT 1 FROM #ShortStrings WHERE [String] IS NULL)) BEGIN SELECT NULL AS [Longest Common Substrings]; RETURN; END; /* We need to know number of rows in the sample and the length of the shortest string as the longest common substring cannot be longer than the shortest string in the set */ DECLARE @TotalRows INT, @MinLen TINYINT, @MatchesFound INT = 0; SELECT @MinLen = MIN(LEN([String])), @TotalRows = COUNT(DISTINCT [String]) FROM #ShortStrings; RAISERROR(N'Maximum Possible Length: %d; Total Distinct Rows: %d', 0, 0, @MinLen, @TotalRows) WITH NOWAIT; DECLARE @Matches TABLE ( [String] sysname COLLATE DATABASE_DEFAULT NULL ); /* Check backwards from the longest possible string to the shortest and break when we find a match */ /* You might want to check the air conditioner is switched on here */ WHILE (@MinLen > 0 AND @MatchesFound = 0) BEGIN RAISERROR(N'Processing strings of length: %d', 0, 0, @MinLen) WITH NOWAIT; /* this method is "brute force" 1. find all substrings for each input string 2. pick the first substring that appears in every input string we find this by grouping, counting and comparing to the number of input strings */ INSERT INTO @Matches ([String]) SELECT [Match] FROM ( SELECT [String], SUBSTRING([String], T.[N], @MinLen) AS [Match] FROM #ShortStrings CROSS APPLY ( SELECT LEN([String]) - @MinLen + 1 ) a(L) CROSS APPLY ( SELECT TOP(a.[L]) V.[N] FROM ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12),(13),(14),(15),(16),(17), (18),(19),(20),(21),(22),(23),(24),(25),(26),(27),(28),(29),(30),(31),(32),(33),(34), (35),(36),(37),(38),(39),(40),(41),(42),(43),(44),(45),(46),(47),(48),(49),(50) ) V(N) ) T(N) ) Matches(String, Match) GROUP BY [Match] HAVING COUNT(DISTINCT [String]) = @TotalRows; SET @MatchesFound = @@ROWCOUNT; /* Decrement so next time we check for a shorter match */ SET @MinLen = (@MinLen - 1); END; /* Display the results */ SELECT [String] AS [Longest Common Substrings] FROM @Matches; -- Longest Common Substring: referen -- 1:13 (across 3 successive executions AFTER the initial execution) ----------------- SELECT dbo.LongestCommonSubstring([String], 0) FROM #ShortStrings; -- referen -- 0:12 (across 3 successive executions AFTER the initial execution) SELECT dbo.LongestCommonSubstring([String], 1) FROM #ShortStrings; -- 0:12 (across 3 successive executions AFTER the initial execution) /* referen refere eferen refer efere feren refe efer fere eren ref efe fer ere ren re ef fe er en r e f n c _ */ GO ------------------------------------------------------------------------------------- -- Modified @MisterMagoo Test: -- Same code and base data, but add to each row: a tie-for-first-place -- substring, a 4 character common substring, and 3 random characters. ------------------------------------------------------------------------------------- /* -- Highlight and execute the following once IF (OBJECT_ID('tempdb..#MultipleMatches') IS NOT NULL) BEGIN PRINT N'Dropping #MultipleMatches table...'; DROP TABLE #MultipleMatches; END; PRINT N'Creating and Populating #MultipleMatches table...'; CREATE TABLE #MultipleMatches ( [MultipleMatchesID] INT NOT NULL IDENTITY(1, 1) PRIMARY KEY, [String] sysname COLLATE DATABASE_DEFAULT NULL ); INSERT INTO #MultipleMatches ([String]) SELECT ss.[String] + '1234567' + CONVERT(VARCHAR(5), CRYPT_GEN_RANDOM(3)) + '_Yo!' AS [String] FROM #ShortStrings ss -- 1,213,488 rows on SQL Server 2014 SELECT COUNT(*) FROM #MultipleMatches; */ /* Any NULLs mean there is not a "longest common string" */ IF (EXISTS(SELECT 1 FROM #MultipleMatches WHERE [String] IS NULL)) BEGIN SELECT NULL AS [Longest Common Substrings]; RETURN; END; /* We need to know number of rows in the sample and the length of the shortest string as the longest common substring cannot be longer than the shortest string in the set */ DECLARE @TotalRows INT, @MinLen TINYINT, @MatchesFound INT = 0; SELECT @MinLen = MIN(LEN([String])), @TotalRows = COUNT(DISTINCT [String]) FROM #MultipleMatches; RAISERROR(N'Maximum Possible Length: %d; Total Distinct Rows: %d', 0, 0, @MinLen, @TotalRows) WITH NOWAIT; DECLARE @Matches TABLE ( [String] sysname COLLATE DATABASE_DEFAULT NULL ); /* Check backwards from the longest possible string to the shortest and break when we find a match */ /* You might want to check the air conditioner is switched on here */ WHILE (@MinLen > 0 AND @MatchesFound = 0) BEGIN RAISERROR(N'Processing strings of length: %d', 0, 0, @MinLen) WITH NOWAIT; /* this method is "brute force" 1. find all substrings for each input string 2. pick the first substring that appears in every input string we find this by grouping, counting and comparing to the number of input strings */ INSERT INTO @Matches ([String]) SELECT [Match] FROM ( SELECT [String], SUBSTRING([String], T.[N], @MinLen) AS [Match] FROM #MultipleMatches CROSS APPLY ( SELECT LEN([String]) - @MinLen + 1 ) a(L) CROSS APPLY ( SELECT TOP(a.[L]) V.[N] FROM ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12),(13),(14),(15),(16),(17), (18),(19),(20),(21),(22),(23),(24),(25),(26),(27),(28),(29),(30),(31),(32),(33),(34), (35),(36),(37),(38),(39),(40),(41),(42),(43),(44),(45),(46),(47),(48),(49),(50) ) V(N) ) T(N) ) Matches(String, Match) GROUP BY [Match] HAVING COUNT(DISTINCT [String]) = @TotalRows; SET @MatchesFound = @@ROWCOUNT; /* Decrement so next time we check for a shorter match */ SET @MinLen = (@MinLen - 1); END; /* Display the results */ SELECT [String] AS [Longest Common Substrings] FROM @Matches; -- ?? never returned -- ?? killed after 23 minutes. Only process strings of lengths: 27, 26, and 25 ----------------- SELECT dbo.LongestCommonSubstring([String], 0) FROM #MultipleMatches; -- referen1234567 -- 1:09 (across 3 successive executions AFTER the initial execution) SELECT dbo.LongestCommonSubstring([String], 1) FROM #MultipleMatches; -- 1:10 (across 3 successive executions AFTER the initial execution) /* referen 1234567 refere eferen 123456 234567 refer efere feren 12345 23456 34567 refe efer fere eren 1234 2345 3456 4567 _Yo! ref efe fer ere ren 123 234 345 456 567 _Yo Yo! re ef fe er en 12 23 34 45 56 67 _Y Yo o! r e f n c _ 1 2 3 4 5 6 7 Y o ! */ GO ------------------------------------------------------------------------------------- -- Solomonified @MisterMagoo Technique: -- Same data as "Modifed @MisterMagoo Test", but attempt to extract -- substrings from 2 entries into a temp table, then find which ones -- are present across all rows, then return the longest one(s). ------------------------------------------------------------------------------------- DECLARE @ReturnAllSubstrings BIT = 0; IF (OBJECT_ID('tempdb..#Substrings') IS NOT NULL) BEGIN PRINT N'Dropping #Substrings table...'; DROP TABLE #Substrings; END; PRINT N'Creating #Substrings table...'; CREATE TABLE #Substrings ( [SubstringsID] INT NOT NULL IDENTITY(1, 1) PRIMARY KEY, [String] sysname COLLATE DATABASE_DEFAULT NULL ); /* Any NULLs mean there is not a "longest common string" */ IF (EXISTS(SELECT 1 FROM #MultipleMatches WHERE [String] IS NULL)) BEGIN RETURN; END; /* We need to know number of rows in the sample and the length of the shortest string as the longest common substring cannot be longer than the shortest string in the set */ DECLARE @TotalRows INT, @MinLen TINYINT, @MatchesFound INT = 0; SELECT @MinLen = MIN(LEN([String])), @TotalRows = COUNT(*) FROM #MultipleMatches; RAISERROR(N'Maximum Possible Length: %d; Total Distinct Rows: %d', 0, 0, @MinLen, @TotalRows) WITH NOWAIT; /* Check backwards from the longest possible string to the shortest and break when we find a match */ DECLARE @SampleSet TABLE ( [String] sysname COLLATE DATABASE_DEFAULT NULL ); INSERT INTO @SampleSet ([String]) SELECT TOP (2) [String] FROM #MultipleMatches GROUP BY [String] ORDER BY LEN([String]) ASC; WHILE (@MinLen > 0) BEGIN RAISERROR(N'Processing strings of length: %d', 0, 0, @MinLen) WITH NOWAIT; /* this method is "brute force" 1. find all substrings for each input string 2. pick the first substring that appears in every input string we find this by grouping, counting and comparing to the number of input strings */ INSERT INTO #Substrings ([String]) SELECT [Match] FROM ( SELECT [String], SUBSTRING([String], T.[N], @MinLen) AS [Match] FROM @SampleSet CROSS APPLY ( SELECT LEN([String]) - @MinLen + 1 ) a(L) CROSS APPLY ( SELECT TOP(a.[L]) V.[N] FROM ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12),(13),(14),(15),(16),(17), (18),(19),(20),(21),(22),(23),(24),(25),(26),(27),(28),(29),(30),(31),(32),(33),(34), (35),(36),(37),(38),(39),(40),(41),(42),(43),(44),(45),(46),(47),(48),(49),(50) ) V(N) ) T(N) ) Matches(String, Match) GROUP BY [Match] HAVING COUNT(DISTINCT [String]) = 2; SET @MatchesFound = @@ROWCOUNT; /* Decrement so next time we check for a shorter match */ SET @MinLen = (@MinLen - 1); END; --SELECT * FROM #Substrings ORDER BY LEN([String]) DESC, SubstringsID ASC; DECLARE @Matches TABLE ( [String] sysname COLLATE DATABASE_DEFAULT NULL, [IsLongest] BIT NOT NULL ); DECLARE @Test sysname, @MaxLength INT, @CurrentLength INT; DECLARE tests CURSOR STATIC LOCAL READ_ONLY FORWARD_ONLY FOR SELECT [String] FROM #Substrings ORDER BY LEN([String]) DESC;--, [SubstringsID] ASC -- ?? OPEN tests; FETCH NEXT FROM tests INTO @Test; WHILE (@@FETCH_STATUS = 0) BEGIN SET @CurrentLength = LEN(@Test); RAISERROR(N'Testing substring: %s', 0, 0, @Test) WITH NOWAIT; -- @MaxLength will remain NULL until the first common substring is found IF ((@ReturnAllSubstrings = 0) AND (@CurrentLength < @MaxLength)) BEGIN BREAK; END; IF (NOT EXISTS( SELECT * FROM #MultipleMatches mm WHERE CHARINDEX(@Test, mm.[String]) = 0 ) ) BEGIN SET @MaxLength = ISNULL(@MaxLength, @CurrentLength); INSERT INTO @Matches ([String], [IsLongest]) VALUES (@Test, IIF(@CurrentLength = @MaxLength, 1, 0)); RAISERROR(N'Found match: %s; Length: %d', 0, 0, @Test, @CurrentLength) WITH NOWAIT; END; FETCH NEXT FROM tests INTO @Test; END; CLOSE tests; DEALLOCATE tests; /* Display the results */ SELECT [String], [IsLongest] FROM @Matches; -- 0:22 across several executions IF @ReturnAllSubstrings = 0 -- 2:41 across several executions IF @ReturnAllSubstrings = 1 /* String IsLongest 1234567 1 referen 1 123456 0 234567 0 eferen 0 refere 0 12345 0 23456 0 34567 0 efere 0 feren 0 refer 0 _Yo! 0 1234 0 2345 0 3456 0 4567 0 efer 0 eren 0 fere 0 refe 0 _Yo 0 123 0 234 0 345 0 456 0 567 0 efe 0 ere 0 fer 0 ref 0 ren 0 Yo! 0 _Y 0 12 0 23 0 34 0 45 0 56 0 67 0 ef 0 en 0 er 0 fe 0 o! 0 re 0 Yo 0 ! 0 _ 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 c 0 e 0 f 0 n 0 o 0 r 0 Y 0 */ ------------------------------------------------------------------------------------- /* -- related research queries: SELECT MAX(LEN([String])) FROM #ShortStrings; SELECT DISTINCT [String] FROM #ShortStrings; SELECT * FROM sys.assemblies; SELECT * FROM sys.dm_clr_loaded_assemblies; SELECT CONVERT(BIT, 'True'); SELECT '1234567' + CONVERT(VARCHAR(5), CRYPT_GEN_RANDOM(3)) + '_Yo!' */