SQLCLR UDA for Longest Common Substring - Testing

/*
    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;
-- <Items Merged="False"><Item>referen</Item></Items>
-- 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)
/*
<Items Merged="False">
  <Item IsLongest="True">referen</Item>
  <Item IsLongest="False">refere</Item>
  <Item IsLongest="False">eferen</Item>
  <Item IsLongest="False">refer</Item>
  <Item IsLongest="False">efere</Item>
  <Item IsLongest="False">feren</Item>
  <Item IsLongest="False">refe</Item>
  <Item IsLongest="False">efer</Item>
  <Item IsLongest="False">fere</Item>
  <Item IsLongest="False">eren</Item>
  <Item IsLongest="False">ref</Item>
  <Item IsLongest="False">efe</Item>
  <Item IsLongest="False">fer</Item>
  <Item IsLongest="False">ere</Item>
  <Item IsLongest="False">ren</Item>
  <Item IsLongest="False">re</Item>
  <Item IsLongest="False">ef</Item>
  <Item IsLongest="False">fe</Item>
  <Item IsLongest="False">er</Item>
  <Item IsLongest="False">en</Item>
  <Item IsLongest="False">r</Item>
  <Item IsLongest="False">e</Item>
  <Item IsLongest="False">f</Item>
  <Item IsLongest="False">n</Item>
  <Item IsLongest="False">c</Item>
  <Item IsLongest="False">_</Item>
</Items>
*/
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;
-- <Items Merged="False"><Item>referen</Item><Item>1234567</Item></Items>
-- 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)
/*
<Items Merged="False">
  <Item IsLongest="True">referen</Item>
  <Item IsLongest="True">1234567</Item>
  <Item IsLongest="False">refere</Item>
  <Item IsLongest="False">eferen</Item>
  <Item IsLongest="False">123456</Item>
  <Item IsLongest="False">234567</Item>
  <Item IsLongest="False">refer</Item>
  <Item IsLongest="False">efere</Item>
  <Item IsLongest="False">feren</Item>
  <Item IsLongest="False">12345</Item>
  <Item IsLongest="False">23456</Item>
  <Item IsLongest="False">34567</Item>
  <Item IsLongest="False">refe</Item>
  <Item IsLongest="False">efer</Item>
  <Item IsLongest="False">fere</Item>
  <Item IsLongest="False">eren</Item>
  <Item IsLongest="False">1234</Item>
  <Item IsLongest="False">2345</Item>
  <Item IsLongest="False">3456</Item>
  <Item IsLongest="False">4567</Item>
  <Item IsLongest="False">_Yo!</Item>
  <Item IsLongest="False">ref</Item>
  <Item IsLongest="False">efe</Item>
  <Item IsLongest="False">fer</Item>
  <Item IsLongest="False">ere</Item>
  <Item IsLongest="False">ren</Item>
  <Item IsLongest="False">123</Item>
  <Item IsLongest="False">234</Item>
  <Item IsLongest="False">345</Item>
  <Item IsLongest="False">456</Item>
  <Item IsLongest="False">567</Item>
  <Item IsLongest="False">_Yo</Item>
  <Item IsLongest="False">Yo!</Item>
  <Item IsLongest="False">re</Item>
  <Item IsLongest="False">ef</Item>
  <Item IsLongest="False">fe</Item>
  <Item IsLongest="False">er</Item>
  <Item IsLongest="False">en</Item>
  <Item IsLongest="False">12</Item>
  <Item IsLongest="False">23</Item>
  <Item IsLongest="False">34</Item>
  <Item IsLongest="False">45</Item>
  <Item IsLongest="False">56</Item>
  <Item IsLongest="False">67</Item>
  <Item IsLongest="False">_Y</Item>
  <Item IsLongest="False">Yo</Item>
  <Item IsLongest="False">o!</Item>
  <Item IsLongest="False">r</Item>
  <Item IsLongest="False">e</Item>
  <Item IsLongest="False">f</Item>
  <Item IsLongest="False">n</Item>
  <Item IsLongest="False">c</Item>
  <Item IsLongest="False">_</Item>
  <Item IsLongest="False">1</Item>
  <Item IsLongest="False">2</Item>
  <Item IsLongest="False">3</Item>
  <Item IsLongest="False">4</Item>
  <Item IsLongest="False">5</Item>
  <Item IsLongest="False">6</Item>
  <Item IsLongest="False">7</Item>
  <Item IsLongest="False">Y</Item>
  <Item IsLongest="False">o</Item>
  <Item IsLongest="False">!</Item>
</Items>
*/
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!'

*/