## PerfML Part 2: Self-Tuning with a Tally Table

In PerfML Part 1 we covered a some new algorithms for creating a self-tuning function. In Part 2 we’ll turbo charge our algorithm with parallelism and a tally table.

## Before You Begin

This is the second article about PerfML, where I introduced some new concepts, as well as some less common ones which will be referenced heavily in this article, such as the dynamic algorithm (completely unrelated to dynamic programming). If you haven’t read Part 1, I suggest you do so before continuing as you will get much more out of this article. I use delimitedsplit8k, fnTally and make_parallel so grab a copy of each if you are playing along at home.

## Introduction

In Part 1 of this series you were introduced to the self-tuning function and PerfML, the science of creating fast, deterministic, elegant self-tuning routines such as functions and stored procedures. We reviewed the difference between exact and approximation algorithms and how they can be combined to return a deterministic result. I also introduced a new type of parameter: the gap parameter (G)which can be used to add gaps to a sequence the purpose of creating an approximation algorithm. We then created a string search routine which leveraged an exact, brute force algorithm to find a specific sequence in a string. Then we transformed the function to leverage an approximation algorithm using our gap parameter which allowed us to introduce a margin of error, or range of possible valid values, while reducing the cost of the algorithm by a factor of G while preserving the ability to return an exact result when G=1. Lastly, we reviewed how to reduce the search area of our exact algorithm by first using an approximation to identify a much smaller range of possible valid answers.

Today I’ll define and teach you how to use a tuning parameter, the most important component of PerfML. A tuning parameter can be defined as:

A parameter that allows you to dynamically tune a deterministic function’s algorithm while guaranteeing the same deterministic return value.

The gap parameter (introduced in Part 1), is a form of tuning parameter. The tuning parameter is the core component of PerfML, tuning parameters are where your intelligence lives. For any given input there can be only one tuning parameter value which does the least amount of work, that value will be perform the best – both in speed and resource usage (memory, IO). Determining the best value for your tuning parameter is the most important (and daunting) task you will perform while developing self-tuning functions; master this and your algorithms will figure out how to mater themselves. Choosing the best tuning parameter value can be done as part of a pre-processing task, at runtime or a combination of both. This will all make more sense when you see the code examples.

## Sequential to Set-Based with fnTally

In part 1 we created a self-tuning function leveraging a self-referencing recursive scalar UDF. The goal was not to develop the most performant function but rather to understand the algorithms and other new concepts which are vital to PerfML; iterative programming and basic recursion are easier to understand. Functions are a vital component of any major programming language and avoiding loops, and other iterative, RBAR-style logic is vital to writing fast clean code in most declarative programming languages. For this series I’m using Microsoft SQL server which means we’ll be using fnTally by SQL MVP Jeff Moden to replace our loop logic fromPart 1. There are many advantages to a tally table of a loop, these are the ones I consider most important:

1. Speed
2. Functional Purity
3. Ability to measure performance
4. Parallel execution
##### 1.    Speed

First, a lazy sequence (CTE tally table in this case) will perform faster than a loop, cursor, iterative recursion (using recursion for counting) and any other iterative methods used for solving common programming problems. fnTally counts to one billion in 90 seconds on my laptop. Second, the fastest kind of T-SQL function in SQL Server is the Inline Table Valued Function (iTVF). With iTVFs, however, data structures are immutable so there is no way to perform your typical loop (do, while, etc.) This leaves you two options in SQL: recursion  or a tally table. Recursion is slow, tally tables are fast and virtually I/O free (readless). Because of the immutable data structures, the functional purity of an iTVF and  speed of a quality tally table or tally table function, the SQL optimizer a full range of options including the ability to multi-thread execution, that is, leverage parallelism.

##### 2.    Functional Purity

fnTally is an iTVF, which is SQL Server’s version of a pure function . Pure functions are generally side-effect free, don’t experience memory leaks and allow for very clean, concise and reusable code. Note the Advantages of pure functions section of this Microsoft article: Functional programming vs. imperative programming and the benefits on SQL iTVFs in Paul White’s article about APPLY.

The primary reason to implement functional transformations as pure functions is that pure functions are composable: that is, self-contained and stateless. These characteristics bring a number of benefits, including the following:

1. Increased readability and maintainability. This is because each function is designed to accomplish a specific task given its arguments. The function doesn’t rely on any external state.
2. Easier reiterative development. Because the code is easier to refactor, changes to design are often easier to implement. For example, suppose you write a complicated transformation, and then realize that some code is repeated several times in the transformation. If you refactor through a pure method, you can call your pure method at will without worrying about side effects.
3. Easier testing and debugging. Because pure functions can more easily be tested in isolation, you can write test code that calls the pure function with typical values, valid edge cases, and invalid edge cases.

Starting with fast and clean pure functions for our self-tuning algorithms will keep your functions blazing while being easier to debug.

##### 3.    Measuring Performance

It is very difficult to accurately measure scalar UDF performance (except when leveraging SQL Server 2019 scalar UDF inlining.) Key performance metric collection tasks such as measuring I/O, accurate run times and even extracting a usable execution plan are impossible when writing non-inline (impure) T-SQL scalar UDFs. The opposite is true with an inline table valued function (iTVF); fnTally is an iTVF and will be used later in this article for the logic used to replace our recursive scalar logic from Part 1 (dbo.stringSearchV1) .Below is a portion  of the execution plan from dbo.stringSearch (truncated for brevity) which leverages fnTally.

Our iTVF that generated the plan above uses the same “exact approximation” logic we used in our scalar UDF from the previous article. In this plan, because I’m familiar with my logic I can see that approximation algorithm retrieves 32,064 rows from my fnTally, which grows to 42,064 during the merge join. The exact algorithm then requires another 18,144 rows from fnTally which grows to 26,613 during the second merge join. The number of iterations for the scalar UDF is a mystery; all we know for sure as you will see, is that the fnTally version is profoundly faster.

##### 4.    Parallel Execution

T-SQL scalar UDFs (as well as multi-statement table values functions) cannot utilize a parallel execution plan unless they can leverage SQL Server 2019 scalar UDF inlining, and still parallel execution is not possible with inlined scalar UDFs that are self-referencing (in my experience). iTVFs that leverage fnTally, on the other hand, can be processed asynchronously and are often substantially faster as you will see momentarily.

Most of my functions which leverage a tally table or correctly developed tally table function, such as dbo.fnTally, run much faster when leveraging a parallel execution plan. Sometimes a parallel plan yields no performance benefit at all which, then, is a liability – you have multiple CPUs doing the job of one instead doing something more productive. Sometimes parallel plans are slower than serial, that’s an even bigger bummer. Sometimes it’s system/instance level settings (e.g. cost threshold for parallelism) and sometimes even your set-based code is bad (set-based != bullet proof.) Sometimes the optimizer just gets it wrong. Either way, if you need a parallel execution plan you have two options, Trace Flag 8649 and make_parallel by Adam Machanic. Trace Flag 8649 is not documented and therefore not safe for production. make_parallel is a simple T-SQL function which, in short, freaks the optimizer out and causes it to choose parallel execution if it’s available. make_parallel adds a lot of bloat to the execution plan so: in Dev I use the trace flag, in Production I use make_parallel when I have determined that doing so is the best option.

## Function Logic

We are going to build the same function from part 1, dbo.stringsearchV1, using fnTally for our iterative logic. These are the parameters we’ll use:

``````DECLARE
@G BIGINT       = 5,   -- gap param
@C VARCHAR(100) = 'X', -- search character
@L BIGINT       = 1,   -- min length
@H BIGINT       = 22,  -- max length
@S VARCHAR(MAX) = '999999999-XXXXXXXXXXXXXX-999999999'; -- sample search string``````

fnTally takes two parameters: @ZeroOrOne, which determines is the first row will be zero or one; we will set this to 0. @MaxN will be the highest integer returned, for @MaxN I came up with this formula: (@H-@L+1)/@G+SIGN((@H-@L+1)%@G); it will determine the correct number of rows with the @G-sized gaps in the.

##### Avoiding the descending sort

SQL sorts generally have a complexity of N log N, which is worse than linear. This means that the more rows we sort, the cost to sort each row increases. For row counts in the 10’s of thousands, this is not a big deal but it becomes a problem when we get into the 100’s of thousands and beyond.

The recursive solution from Part 1 did not require a sort to determine the “longest” allowable string. For our fnTally version we will be seeking the longest value which does requires us to use an ORDER BY N DESC clause. To circumvent this problem we can return N is descending order using Jeff Moden’s formula: @MaxN-N+1, mentioned in the fnTally documentation. This only works, however, when we are seeking an exact result (@G=1) and, therefore, no gaps in the sequence.

To return the numbers beginning with @H, decrementing by @G until @L we’ll use: IIF(t.N<gap.N, @H-@G*t.N, @L). If the final number is less than @L, @L is returned for the final iteration. So far we have:

``````SELECT
[N ASC]  = t.N,                          -- fnTally "N" (0-base row number)
[N DESC] = IIF(t.N<gap.N, @H-@G*t.N, @L) -- Gap reduced sequence from @H to @L
FROM        (VALUES((@H-@L+1)/@G+SIGN((@H-@L+1)%@G))) AS gap(N) -- number of rows
CROSS APPLY dbo.fnTally(0,gap.N)                      AS t;     -- fnTally call``````

With this logic, setting @G=2 would return (truncated) [22 20 … 6 4 2 1] for “[N DESC]”; @G=5 returns [22 17 12 7 2 1], @G=6 returns [22 16 10 4 1], and so on. For the L column (the lower-bound value) we’re using [N Desc] from earlier. For H, the upper-bound, we’ll leverage LAG: f.N+ISNULL(LAG(f.N,1) OVER (ORDER BY t.N)-f.N,1)-1.

``````SELECT
L = IIF(t.N<gap.N, @H-@G*t.N, @L), -- Gap reduced sequence from @H to @L
H = f.N+ISNULL(LAG(f.N,1) OVER (ORDER BY t.N)-f.N,1)-1
FROM        (VALUES((@H-@L+1)/@G+SIGN((@H-@L+1)%@G))) AS gap(N) -- how many rows
CROSS APPLY dbo.fnTally(0, gap.N)                     AS t
CROSS APPLY (VALUES(IIF(t.N<gap.N, @H-@G*t.N, @L)))   AS f(N);``````
##### Retrieving matched values

Then add a subquery that searches the string (@S) for an L-sized series of @C in the input string (@S), and exclude rows where there is no match:

``````CROSS APPLY (VALUES(CHARINDEX(REPLICATE(@C,f2.L),@S)))  AS p(Idx)
WHERE        p.Idx > 0``````

Finally, we wrap our logic into a subquery, add our TOP (1) clause, ordered by N. Note that I am using the aliased of “RN” for “Row Number”; I use RN as my sort-key, and “N” for my tally table N column. We’ll wrap all this up in an iTVF and create a VARCHAR(8000) and VARCHAR(MAX) version of our new stringsearch function. The only difference between the two functions is the data type for @S. The final tally table (lazy sequence) logic for the our two set-based approximation function are:

### dbo.stringSearch8K

``````CREATE OR ALTER FUNCTION dbo.stringSearch8K
(
@C CHAR(1),
@S VARCHAR(8000),
@L BIGINT,
@H BIGINT,
@G BIGINT
)
/* Created on 20201004 by Alan Burstein. */
RETURNS TABLE WITH SCHEMABINDING AS RETURN
SELECT TOP(1)
L   = f2.L,  -- Lower Boundary
H   = f2.H,  -- Upper Boundary
Idx = p.Idx -- ItemIndex (position of the item match)
FROM
(
SELECT t.N, f.N, f.N+ISNULL(LAG(f.N,1) OVER (ORDER BY t.N)-f.N,1)-1
FROM        (VALUES((@H-@L+1)/@G+SIGN((@H-@L+1)%@G))) AS gap(N) -- how many rows
CROSS APPLY dbo.fnTally(0, gap.N)                     AS t
CROSS APPLY (VALUES(IIF(t.N<gap.N, @H-@G*t.N, @L)))   AS f(N)
) AS f2(RN,L,H)
CROSS APPLY (VALUES(CHARINDEX(REPLICATE(@C,f2.L),@S))) AS p(Idx)
WHERE        p.Idx > 0
ORDER BY     f2.RN;``````

### dbo.stringSearch

``````CREATE OR ALTER FUNCTION dbo.stringSearch
(
@C CHAR(1),
@S VARCHAR(MAX),
@L BIGINT,
@H BIGINT,
@G BIGINT
)
/* Created on 20201004 by Alan Burstein. */
RETURNS TABLE WITH SCHEMABINDING AS RETURN
SELECT TOP(1)
L   = f2.L, -- Lower Boundary
H   = f2.H, -- Upper Boundary
Idx = p.Idx -- ItemIndex (position of the item match)
FROM
(
SELECT t.N, f.N, f.N+ISNULL(LAG(f.N,1) OVER (ORDER BY t.N)-f.N,1)-1
FROM        (VALUES((@H-@L+1)/@G+SIGN((@H-@L+1)%@G))) AS gap(N) -- how many rows
CROSS APPLY dbo.fnTally(0, gap.N)                     AS t
CROSS APPLY (VALUES(IIF(t.N<gap.N, @H-@G*t.N, @L)))   AS f(N)
) AS f2(RN,L,H)
CROSS APPLY (VALUES(CHARINDEX(REPLICATE(@C,f2.L),@S))) AS p(Idx)
WHERE        p.Idx > 0
ORDER BY     f2.RN;``````

The 8K version is slightly faster when dealing with smaller strings with a smaller range of acceptable values. As the strings and range of acceptable values grow, the Max version becomes faster.

## The Tuning Procedure

The tuning procedure (see the attached DDL as a text file below) is a T-SQL stored procedure I spun up quickly to test different design patterns using values for @G. This will help us find the optimal parameter for a specific predictable input. The procedure accepts the following parameters:

The procedure accepts all the parameters required for dbo.stringsearch. @I is for the number of test iterations the stored procedure should perform. @mode is for selecting on of 10 different design patterns to test. The parameter, @gaps is a comma-delimited list of different gap parameters (@G) for our function to accept. @puff and @C build sample strings of NEWIDs with the search pattern stuffed in the middle. Setting @mode=1, @I=5, @gaps = ‘1,2,5,10’ will test a specific design pattern using dbo.stringsearch 5 times for each value in @gaps. There are 4 gap values so for this example that would be a total of 20 tests.

The proc has examples with a performance test for each design pattern; executed with serial and parallel execution plans. Again, in Development environments I use the trace_flag 8649 because it’s easier to read the execution plan. I use make_parallel in Production because it performs the same and is safe to use in Production.

Below is the example output from a test I ran against a large set of rows five times (@I=5) for seven parameters between 5 and 35 (@gaps=’5,10,15,20,25,30,35′). The Gap column is the value of @G, Total is the total run time, min and max represent the slowest and fastest runs respectively. TAvg is a rolling average of the total time.

``````Gap   Total  Min    Max    TAvg
----- ------ ------ ------ ------
25    69294  13140  14437  69294
20    69546  12804  14603  69420
30	  71460  13096  14950  70100
35	  74830  13514  15990  71282
15    75196  13790  16413  72065
10    94631  17383  20097  75826
5     165316 30423  34530  88610``````

In this above example, with the example data used, @G=20 had the fastest run at 12.8 seconds, but it appears that 25 is the optimal value based on the total run time.

In the real world we would replace our sample data table, ##strings, with a sampling of real data you are developing a self-tuning functions for. For example, once I used to write ETL packages that collected social media metrics from search and social media companies. The source data from each company came in as a text file where we would extract key metrics. The content of each file, and the input strings within, was looked very different for each company but, for each the text was predictable. The optimal use case for self-tuning function for string parsing here would be to determine the best gap parameter value for each companies source data. For this we could build a tuning procedure for each company and store the best parameter value for later use.

## Design Patterns Tested

We have two versions of our function, one for 8K strings and one for VARCHAR(MAX). The performance is nearly identical for both functions except that the 8K version is faster with shorter strings (e.g. less than a 1000 characters). Note these parameters, the queries, my comments and the results.

###### Test Parameters and sample data

Executing this code will create the sample data table (##strings) leaving it intact for further analysis.

``````DECLARE
@rows BIGINT        = 2000,
@puff BIGINT        = 5,
@gaps VARCHAR(8000) = '5,10,15,20,25,30,35', -- Gap parameters to test
@C    VARCHAR(100)  = 'X',
@L    BIGINT        = 1,
@H    BIGINT        = 1000,
@max  BIGINT        = 1100,
@I    BIGINT        = 1,
@out  BIGINT        = 1; -- general performance details of test run

EXEC dbo.usp_stringsearch_test1 @rows, @puff, @G, @C, @L, @H, @max, 15, @out, @I, 0;``````

Please test away and let me know what you find.

###### Design Patterns

With our sample table in place we can test a few different design patterns; there are three: our exact algorithm, a dynamic algorithm (approximation > exact) and a dynamic algorithm with two approximation reductions (approximation > approximation > exact).

``````--==== 1. EXACT algorithm
SELECT
s.stringId, s.string,             -- ##strings attributes
Boundaries = CONCAT(f.L,'-',f.H), -- The Upper and lower bounds (exact because @G=1))
ItemIndex  = f.Idx
FROM        ##strings                             AS s
CROSS APPLY dbo.stringSearch(@C,s.String,@L,@H,1) AS f -- @G=1 means EXACT
WHERE       f.L >= @L;

--==== 2. DYNAMIC algorithm: approximation to exact reduction
SELECT      @X = f.L
FROM        ##strings                                 AS s
CROSS APPLY dbo.stringSearch(@C,s.String,@L,@H,@G)    AS f0
CROSS APPLY dbo.stringSearch(@C,s.String,f0.L,f0.H,1) AS f
WHERE       f.L >= @L
END;

--==== 3. DYNAMIC algorithm with two reductions: Approx to Approx to Exact
DECLARE @G2 BIGINT = @G/3+1; -- Simple reduction: split by 1/3rd then add 1 (min=2)

SELECT      @X = f.L
FROM        ##strings                                       AS s
CROSS APPLY dbo.stringSearch(@C, s.String, @L, @H, @G)      AS f0
CROSS APPLY dbo.stringSearch(@C, s.String, f0.L, f0.H, @G2) AS f1
CROSS APPLY dbo.stringSearch(@C, s.String, f1.L,
IIF(f1.L+2<=@H,f1.L+2,@H), 1) AS f
WHERE       f.L >= @L;``````

The first will be the slowest because it’s running in serial mode. The second is much faster because, again, parallel plans turbo charge the performance when combining fnTally and a pure dynamic alogrithm. The Third example, the two-reduction solution is slower for short strings but the fastest (by far) as strings and search patterns get longer. When I already know a query is going to be slow I’ll often set @I low (1 or 2) just to confirm while saving time.

## Performance Test

Using the parameters posted above let’s execute dbo.usp_stringsearch_test1 to as shown below.

``````--==== 8K - Dynamic with 1 reduction - SERIAL
EXEC dbo.usp_stringsearch_test1 @rows, @puff, @gaps, @C, @L, @H, @max, 5,  @out, @I, 1;

--==== VARCHAR MAX - Dynamic with 1 reduction(#6) & 1 string reduction(#7) - PARALLEL
SELECT @puff *= 10/*500*/, @I=5, @H=2000, @max=2000;
EXEC dbo.usp_stringsearch_test1 @rows, @puff, @gaps, @C, @L, @H, @max, 6,  @out, @I, 1;
EXEC dbo.usp_stringsearch_test1 @rows, @puff, @gaps, @C, @L, @H, @max, 7,  @out, @I, 1;

--==== 8K & VARCHAR MAX - Dynamic with 2X reductions (@G2=@G/2+1) - PARARLLEL
SELECT @gaps = '100,250,500,800,1000,2000', @I=10;
EXEC dbo.usp_stringsearch_test1 @rows, @puff, @gaps, @C, @L, @H, @max, 8,  @out, @I, 1;
EXEC dbo.usp_stringsearch_test1 @rows, @puff, @gaps, @C, @L, @H, @max, 10, @out, @I, 1;``````

You can see from the results below that:

1. Parallelism makes a huge difference
2. The two reduction solution is the fastest
3. The 8K and VARCHAR(MAX) versions perform almost identically
4. With the one-reduction solutions the tuning parameter can be way too high or way too low, the two-reduction solution seems to perform better with the highest possible value for @G.

Note that, for modes 8 & 10 (the two-reduction test), I chose different (higher) values for the gap:

## Conclusion

In Part 1 we learned how to develop a self-tuning function using a dynamic algorithm. Today we created a much faster version of our function leveraging fnTally. Things get even nasty faster when we add make_parallel. Another victory for set-based SQL and the tally table. In part 3 we’ll use these concepts to do something much cooler. Thanks for reading!

## PerfML Part 1: The Self-Tuning Function

Is it possible for functions to make themselves faster? PerfML, a new performance-centric approach to writing code that leverages machine learning makes this possible. No libraries required, just some old school math.

## Introduction

By the end of this article should understand and will have sample code which can be used to write what I call a self-tuning function – a function which can continuously tune itself better performance over time. This without libraries or third party code, only algorithms and concepts. What you may appreciate most about this approach to writing self-tuning functions is that you can apply it any major programming languages that supports side-effect free functions; especially Functional Programming (FP), Python, .NET and pretty much any flavor of SQL. I came up with this concept while working on a version of the traveling salesperson problem for a logistics company. I quickly discovered that these ideas could be easily applied to common everyday problems Throughout this series we will apply this concept to a simple string and pattern search algorithm then to some more complex but useful functions, all the way through the longest common subsequence between three strings which is NP-Complete (for the general case of an arbitrary number of input sequences).

By the way, welcome to my blog! I created the CodingBlackArts to introduce a whole new approach to writing modular, scalable nasty fast code, language-agnostic. My background has been with Microsoft SQL Server but I’m experienced with most with various flavors of SQL and other declarative programming languages such as MDX and XSLT. Writing high-performing set-based SQL code is my second passion by my first true love was functional programming (FP) and, when possible I like to dabble with XSLT 3.0, Scala and Clojure. Sadly, I’ve never had an opportunity to focus on FP professionally so I’ve come up with ways b ring my favorite FP concepts into my SQL development. Pure functions, higher-order functions, functions as first Class Citizens, lazy sequences, modularity and even code as data. Some of this you will see throughout the series.

PerfML is a collection of ideas, concepts and algorithms intended to enable you to: (1) write super-fast, clean and deterministic functions, (2) teach your functions to make themselves faster (3) teach your functions how to teach themselves how to be faster. The self-tuning function is a core component of PerfML. Perf – as in performance, ML as in Machine Learning. PerfML relies heavily on some new approximation algorithms, reductions and even a new kind of parameter I developed. This is the first of a many articles on this topic. I’ve spent nearly seven years developing this new method of solving old problems and I’m excited to share it with you.

## Disclaimers

First, functions are the center of the PerfML Universe and a the top of that hierarchy is fnTally, a T-SQL function that produces an ordered lazy sequence of numbers similar to python and Clojure’s range function.

This article has the first iteration of code examples which involve loops and T-SQL scalar user defined functions (referred to herein as scalar UDFs). This is for learning purposes only, loops and scalar UDFs perform poorly in MS SQL Server. Loops are generally gross as a math concept in my opinion, especially when developing functions. For now it’s important to understand the concepts, especially if you are new to programming, we’ll address performance later in the series.

Second, as with all CodingBlackArts content, this article is a living document and will be updated frequently. Please forgive any spelling/grammar issues, sample code issues and such. My TOP(1) priority is to deliver my my code, concepts and algorithms as quickly and frequently as possible. than getting my grammar perfect. Please comment below of ping me with ideas, thought, complaints and suggestions.

Third, don’t be discouraged if you are new to programming or SQL specifically. The subject matter is a little advanced but I will do my best to present this subject matter in a way that as many developers and curious onlookers can grasp. When I was new to programming I read a lot of articles that middle little or no sense to me – running and playing with code with was a great learning tool early on and still is.

## The Requirement

Let’s begin with a basic string search algorithm then turn it into a self-tuning function. The requirement is a function that searches a string(S) for the longest consecutive series of a specific character(C), between L and H characters long. Consider these T-SQL parameters and function:

``````DECLARE @C CHAR(1)      = 'x',
@S VARCHAR(MAX) = 'ABC.xxxyz.xxxx!!',
@L BIGINT       = 3,
@H BIGINT      `= 6;

SELECT dbo.stringSearch_exact(@C,@S,@L,@H);``````

Per the above parameters, we need dbo.stringSearch_exact to return the length of the longest series of the letter, “x in the string ABC.xxxyz.xxxx!!, that is between 3 and 6 characters long. The correct result is 4 because the text, “xxxx” appears at position 11.

## Solution 1: An Exact Algorithm

First for the most direct but least performant solution leveraging a loop and a basic brute force search algorithm. The routine will search for a series of the character, @C that that is @L characters long. If no match is found the routine returns zero (0). If a match does exist the routine begins a search for a series with a length of @H, decrementing @H by 1 until a match is found or until @H=@L.

``````-- KEY: Note that, with this algorithm: When @H=@L you know @L is the correct answer.
DECLARE @C CHAR(1)      = 'x',
@S VARCHAR(MAX) = 'zzzabc123xxxxxxxxgggggggfffxxxxxxx',
@L BIGINT       = 5,
@H BIGINT       = 20;

PRINT CHAR(13)+'Function logic as a loop'+CHAR(13)+REPLICATE('-',90);
WHILE @L<=@H
BEGIN
DECLARE @hIdx BIGINT = CHARINDEX(REPLICATE(@C,@H),@S);
PRINT CONCAT('@H:',@H,'; Idx:',@hIdx,';-',IIF(@hIdx>0,' Hit',' No Hit'));

IF CHARINDEX(REPLICATE(@C,@L),@S)=0 BEGIN SELECT  0; BREAK END; -- You done
IF @L=@H                            BEGIN SELECT @H; BREAK END; -- You done
IF CHARINDEX(REPLICATE(@C,@H),@S)>0 BEGIN SELECT @H; BREAK END; -- You done
SET @H=@H-1; -- Lets try again (variable mutation bad - how dare me)
END;``````

There are a couple subtle but slick optimizations worth pointing out. First – if there isn’t a match only one operation is performed. It would be easy to just start counting down from @H, performing O(H) operations to discover that there’s no match. Next, when @H-1 =@L the routine skips the final iteration because it’s done. This means that we a spared one operation in worst case scenarios. The former optimization is a big deal, the latter is a big deal when dealing with really big strings but not smaller ones. I point these optimizations out because they are both math victories. In programming I like to think of each math victory as points in a video game that help you advance to the next level. Even the small ones add up. I digress.

A PRINT statement is included to see what’s happening under the hood.

Output:

``````@H:20; Idx:0;  - No Hit
@H:19; Idx:0;  - No Hit
@H:18; Idx:0;  - No Hit
@H:17; Idx:0;  - No Hit
@H:16; Idx:0;  - No Hit
@H:15; Idx:0;  - No Hit
@H:14; Idx:0;  - No Hit
@H:13; Idx:0;  - No Hit
@H:12; Idx:0;  - No Hit
@H:10; Idx:0;  - No Hit
@H:11; Idx:0;  - No Hit
@H:9;  Idx:0;  - No Hit
@H:8;  Idx:10; - Hit``````

The parameters above will require the routine perform 13 iterations for the correct result. Things quickly get worse when the string gets longer and/or the distance between @L and @H increases. Try the routine above with different parameters. Note the best- and worst-case scenarios. Below is our routine wrapped in a scalar UDF :

##### dbo.stringSearch_exact
``````CREATE FUNCTION dbo.stringSearch_Exact
(
@C CHAR(1),      -- Search character
@S VARCHAR(MAX), -- Input String
@L BIGINT,       -- Lower Boundary
@H BIGINT        -- Upper Boundary
)
/*
Created by Alan Burstein 20200916
WARNING - SLOW CODE, INTENDED FOR LEARNING PURPOSES ONLY

Note the RETURNS NULL ON NULL INPUT. This has performance benefits and will
prevent an infinite loop for when @H is NULL
*/
RETURNS BIGINT WITH SCHEMABINDING, RETURNS NULL ON NULL INPUT AS
BEGIN
WHILE @L<=@H
BEGIN
IF CHARINDEX(REPLICATE(@C,@L),@S)=0 RETURN 0;
IF @L=@H                            RETURN @H;
IF CHARINDEX(REPLICATE(@C,@H),@S)>0 RETURN @H;
SET @H=@H-1;
END
RETURN NULL;
END;``````

We call dbo.stringSearch_Exact like this:

``SELECT dbo.stringSearch_Exact('C', 'ABCCCCDEF', 1, 5); -- RETURNS: 4``

One small thing to note is how the value of @H changes with each iteration. This is referred to as variable mutation a programming anti-pattern which is why this is the last time you will see it here. Variable mutation will be replaced with recursion later in our next solution.

## Solution 2: An Approximation Algorithm

What if we didn’t need an exact match? What if we introduced a margin of error, allowing the answer can be off by a factor of N (N as a user-supplied boundary)? Say we are seeking a match between 5 and 10 characters long, but it doesn’t have to be exact.

Enter the approximation algorithm. Approximations are a vital component of PerfML, consider this definition from Wikipedia:

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable [deterministic] guarantees on the distance of the returned solution to the optimal one.

Approximation Algorithms – Wikipedia

The intended class of problems are NP-hard, a a class of problems most people outside the data science universe rarely deal with. Approximation algorithms were created for this class of problems but work great on the easier stuff, especially when brute force is involved. This needs to change, too many developers are missing out.

Let’s transform our exact algorithm into an approximation algorithm. For this we’ll use a gap parameter. A gap parameter (we’ll call @Gap or @G for short) allows us to decrease the size of a sequence (AKA set) by decrementing by the value of @G instead of 1. So, for example, when: @L=1, @H=10, @G=1, the routine counts down from 10,9,8…2,1. That’s the exact algorithm from above (the a static value instead of @G. If you set @G=2 the routine counts down – 10,8,6…

``````DECLARE @L   BIGINT       = 1,
@H   BIGINT       = 20,
@G   BIGINT       = 2;

PRINT CONCAT('@N:',@H,' (Start)');
WHILE @L<@H
BEGIN
SET @H=IIF(@H-@G < @L, @L, @H-@G);
PRINT CONCAT('@H:',@H);
END``````

To prevent the final iteration from being negative or less than @L:

``SET @H=IIF(@H-@G<@L,@L,@H-@G)``

Again, we still have the option of @G=1 for an exact result by setting the gap parameter to 1: @G=1, or it can be greater. For brevity I’m not adding logic to prevent you from setting @G less than 1, NULL or longer than your string but keep that in mind for now.

``````DECLARE @C CHAR(1)        = 'x',
@S VARCHAR(MAX) = '123xxxyyyzzz123xxxxxxxxgggggggxxxxxxx',
@L BIGINT       = 5,
@H BIGINT       = 20,
@G BIGINT       = 2;

PRINT CHAR(13)+'Function logic as a loop'+CHAR(13)+REPLICATE('-',90);
DECLARE @I BIGINT = 1;

WHILE @L<=@H
BEGIN
DECLARE @hIdx BIGINT = CHARINDEX(REPLICATE(@C,@H),@S);
PRINT CONCAT('@H:',@H,'; Idx:',@hIdx,';-',IIF(@hIdx>0,' Hit',' No Hit'));

IF CHARINDEX(REPLICATE(@C,@L),@S)=0 BEGIN SELECT RESULTS=0;  BREAK END;
IF @L=@H                            BEGIN SELECT RESULTS=@H; BREAK END;
IF CHARINDEX(REPLICATE(@C,@H),@S)>0 BEGIN SELECT RESULTS=@H; BREAK END;
SELECT @H=@H-@G, @I=@I+@G;
END``````

To understand how different values for @G impact the workload consider:

The beauty here is how easy it is to calculate the work/accuracy trade-off for as @G increases reducing the workload while increasing your margin of error. In the analysis above the cost/accuracy trade-off appears to diminish when @G=3. Here, the “sweet spot” is somewhere between 2 and 3. The sweet spot is, however, a constantly moving target; finding it is both Art and Science. The important thing is to understand is the best/worst case scenarios and associated trade-offs.

In the world of Business Intelligence there is a saying, “if you can’t measure it, you can’t manage it.” For example, how could you manage your direct reports if you didn’t know how many you had? Once we go set-based with fnTally we’ll be able to capture real metrics from the execution plan to determine which parameter would have been best for the different kinds of data you are dealing with. Now, when we do a performance test, we aren’t only testing performance, we running a simulation! Black Mirror fans should be excited and nervous.

## The Approximation Function

Our new logic is going to be in the form of a self-referencing recursive scalar UDF. I chose a recursive scalar UDF because:

1. They allow for the cleanest, most lightweight, universal and portable syntax possible in T-SQL. Even programmers unfamiliar with SQL should understand and apply this code to the language of their choosing provided they understand basic recursion (don’t feel bad if you don’t, just remember that recursion should cause you to think about recursion).

Note that logic for dbo.stringSearchV1 is only three lines.
2. There will be good recursion use later on leveraging recursive CTEs which is a little more complicated, the more simple recursive scalar UDF will serve as a good warm-up.
3. A slow scalar recursive UDF is a great way to demonstrate the power of the algorithm; in the test below we’ll look for matching patterns in strings millions and even billions of characters long; we’ll get our answer in seconds.
4. There’s is barely any documentation available on recursive Scalar UDFs in SQL and nothing anywhere about tail recursion in T-SQL server functions – an important topic.
##### Approximation Function Version #1: dbo.stringSearchV1
``````CREATE OR ALTER FUNCTION dbo.stringSearchV1
(
@C VARCHAR(100), -- Search String
@S VARCHAR(MAX), -- Input String
@L BIGINT,       -- Lower Boundary
@H BIGINT,       -- Upper Boundary
@G BIGINT        -- Gap Optimizer
)
/*
Created by Alan Burstein on 20200916
WARNING: SLOW FUNCTION - FOR LEARNING PURPOSES ONLY
*/
RETURNS BIGINT WITH RETURNS NULL ON NULL INPUT AS
BEGIN
IF CHARINDEX(REPLICATE(@C,@L),@S)=0          RETURN 0;         -- Startup Predicate
IF CHARINDEX(REPLICATE(@C,@H),@S)>0 OR @H=@L RETURN @H;        -- Final Recursive call
RETURN dbo.stringSearchV1(@C,@S,@L,IIF(@H-@G<@L,@L,@H-@G),@G); -- Next Recursive call
END;``````

For each iteration where there is still no match without a match, the function calls itself reducing @H by @G using with this formula:

``IIF(@H-@G<@L,@L,@H-@G)``

If, on the final iteration, @H-@G is less than @L (and therefore invalid), @L is used instead of @H-@G. E.g when @H=10, @L=1, @G=4: the pattern size evaluated would be 10,6,2, then 1. If @H=20, @L=10, @G=6: the sizes would be 20,14,10.

As mentioned earlier, and especially in the world of declarative programming (which includes T-SQL), performance is best when parameters and variables are immutable. WRONG:

``````SET @H = IIF(@H-@G < @L, @L, @H-@G)
RETURN dbo.stringSearchV1(@C, @S, @L, @H, @G)``````

Instead of mutating the value of @H the function recursively calls itself with new parameter values. CORRECT:

``RETURN dbo.stringSearchV1(@C, @S, @L, IIF(@H-@G<@L,@L,@H-@G), @G)``

### Approximation Function Performance Test

For our performance test we’re going to:

1. Set up a sample string 21,470,000+ characters long, a good value for stress testing
2. Create and populate a table variable (@gaps) with different values to assign to our gap parameter (@G)
3. Run a performance test with each parameter values for @G
4. Prints the results for review

21,470,000 characters is a good for stress testing, it’s ~1% of the VARCHAR-MAX limit (2,147,483,647). Using the parameters below, dbo.stringSearchV1 takes roughly 2 seconds when @G=10. Since it’s performance is linear, I know (and have confirmed) that 214,700,000 characters will take ~20 seconds, 2.147 billion characters (the limit) takes roughly 200 seconds (~3.5 minutes.) Not bad for a scalar UDF.

``````-- 1. Set up the sample string and parameters
DECLARE @X VARCHAR(MAX) = '?';
DECLARE @C VARCHAR(100) = 'x',
@S VARCHAR(MAX) = '555xx'+@X+'xxxxxxx'+REPLICATE(@X,21470000)+'zzz123xxxggffxxx',
@L BIGINT = 1, @H BIGINT = 20, @G BIGINT, @O BIGINT, @ST DATETIME;

-- 2. Create and populate a temp table with gap parameter(@G) values
DECLARE @gaps TABLE (G BIGINT PRIMARY KEY);
INSERT  @gaps VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(20),(50),(100),(500),(1000);

-- 3. Start the test
PRINT 'APPROXIMAION TEST'+CHAR(13)+REPLICATE('-',90);
WHILE EXISTS (SELECT * FROM @gaps)
BEGIN
SELECT TOP(1) @G = g.G FROM @gaps AS g ORDER BY G;
DELETE FROM @gaps WHERE g=@G;

SELECT @ST=GETDATE();  -- Set the test start time
SELECT L = reduce.L FROM (VALUES(dbo.stringSearch(@C,@S,@L,@H,@G))) AS reduce(L);
-- 4. Print the results
PRINT CONCAT(@G,': ',DATEDIFF(MS,@st,GETDATE()));
END;``````
##### Approximation Function Test Results

I colored the values green for what I consider the best performance/accuracy trade-offs. The slowest, but correct, answer is 7 at 4.3 seconds for an exact result (@G=1). 2 seconds to determine that the value is between 5 and 9 (@G=5), 1 second to determine that it’s between 4 & 11 (@G=8) and 0.5 seconds to determine that it’s between 1 & 20 (@G=20.) This is another example of how to trade accuracy for performance in a very predictable fashion.

## Solution 3: The Dynamic Algorithm

Can we eat our cake and have it too? Can we enjoy the performance benefits of the approximation algorithm without compromising on accuracy? What if we combined our approximation with an exact algorithm?

This is where things get good. Let’s revisit our approximation performance test and make a quick change. Let’s use a simplified string and set @G=5, which will assign the lowest allowable value @Low. Next assign the highest possible value to @High, which is @Low+@G-1.

``````DECLARE @C VARCHAR(100) = 'x',
@S VARCHAR(MAX) = '999xxxxxxxABC123',
@L BIGINT = 1, @H BIGINT = 20, @G BIGINT = 5; -- Gap Parameter set to 5

-- 1. Reduce the search area leveraging the approximation algorithm:
DECLARE @Low  BIGINT = dbo.stringSearchV1(@C,@S,@L,@H,@G); -- Approximation algorithm
DECLARE @High BIGINT = @Low+@G-1;

-- 2. Exact Algorithm
SELECT LowerBound = @Low, UpperBound = @High, Exact = dbo.stringSearchV1(@C,@S,@Low,@High,1);``````

Results:

Using the exact algorithm (@G=1) would require 13 iterations to determine the correct answer is 7. Seeking an approximation, accurate to within 4, we set @G=5. First we perform 4 iterations to determine that the search item is at least 5 but no more than 9. Next we make a second function call with @L=5, @H=9, and set @G=1 for an exact result, which takes 3 iterations. That’s a total of 7 iterations instead of 13! We just reduced the work by almost 1/2 without any loss of accuracy. That’s huge! Data Scientists and Complexity Theory nerds refer to this type of optimization as a combinatorial optimization leveraging a dynamic algorithm. A dynamic algorithm can be defined as:

A general class of algorithms which solve problems by solving smaller versions of the problem, saving the solutions to the small problems and then combining them to solve the larger problem.

The trick is to choose the correct value for @G or, better yet, write a routine that picks the best value for you. Consider the chart below which shows the worst case scenario for when @L=1 and @H=20. “@G” is the gap parameter values from 1-10. “Approx” represents the maximum number of approximation iterations, “Exact” represents the maximum number of exact iterations. “Total” combines the the Approx+Exact for the worst case scenario. The worst case scenario will always be when @G=1, things improve as @G get’s higher.

Notice that 4 and 5 appear to be the sweet spot. This does not mean that when @G=4, or @G=5 the query is guaranteed to be the fastest, only that they are most likely to be best values. Lets run our performance test from earlier but this time we’ll leverage our new dynamic algorithm for an exact result.

### Dynamic Algorithm Performance Test

``````DECLARE @X VARCHAR(MAX) = '?';
DECLARE @C VARCHAR(100) = 'x',
@S VARCHAR(MAX) = '555xx'+@X+'xxxxxxx'+REPLICATE(@X,21470000)+'zzz123xxxggffxxx',
@L BIGINT = 1, @H BIGINT = 20, @G BIGINT, @O BIGINT, @ST DATETIME;

PRINT 'APPROXIMAION TEST'+CHAR(13)+REPLICATE('-',90);
DECLARE @gaps TABLE (G BIGINT PRIMARY KEY);

PRINT 'EXACT APPROXIMAION (DYNAMIC)'+CHAR(13)+REPLICATE('-',90);
INSERT  @gaps VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(15),(20),(30);

WHILE EXISTS (SELECT * FROM @gaps)
BEGIN
SELECT TOP(1) @G = g.G FROM @gaps AS g ORDER BY G;
DELETE FROM @gaps WHERE g=@G;

SELECT @ST=GETDATE();  -- Start the test
DECLARE @Low  BIGINT = dbo.stringSearchV1(@C,@S,@L,@H,@G); -- Approximation
DECLARE @High BIGINT = @Low+@G-1;

SELECT dbo.stringSearchV1(@C,@S,@Low,@High,1); -- @G=1: Exact

PRINT CONCAT(@G,': ',DATEDIFF(MS,@st,GETDATE())); -- Print the results
END;``````

Dynamic Algorithm Performance Test Results:

With the final, dynamic algorithm it appears that 4 and 6 were the best for this specific problem. We were able to determine this by running a test against a single string while trying out different values for our gap parameter (@G). In Part 2 I will show you how to automate the selection of the best value for @G so as to transform our function from one we’ve tuned manually into one that tunes itself. See you there!

## References

https://www.geeksforgeeks.org/np-completeness-set-1/