Peter Larsson : Optimization

T-SQL Tuesday #001: Exploring "Fuzzy" Interval Islands Without Using SQLCLR

Peso — Tue, 08 Dec 2009 22:20:00 GMT

In response to Adam's new series of T-SQL Tuesday, I wanted to write that there are faster ways to get the data in a set-based manner without resorting to SQLCLR.
http://sqlblog.com/blogs/adam_machanic/archive/2009/12/08/t-sql-tuesday-001-exploring-fuzzy-interval-islands-using-sqlclr.aspx

Many companies today still think of SQLCLR's as security risks, so I wanted to rewrite Adam's set-based code to a more efficient algorithm.
On my computer, Adam's code run in about 25 seconds. These two new algorithms below, runs in less than a second each. Which one to choose is how you interpret the definition Adam wrote. Also, this is not a blog post to make someone feel bad, it is a blog post to show there are other ways to write code, with better performance. You just have to think a little different. If someone is interested in how this algorithm works, please ask nice and I'll probably write a more in-depth blog post about the algorithm.
Complaining in the comments doesn't work.

Take 1:

DECLARE @Interval INT = 7

;WITH cteSource
AS (
    SELECT ProductID,
            TransactionDate,
            ROW_NUMBER() OVER (PARTITION BY ProductID ORDER BY TransactionDate) AS recID
    FROM    Production.TransactionHistory
), cteMatch
AS (
    SELECT     s1.ProductID,
                s1.TransactionDate AS FromDate,
                s2.TransactionDate AS ToDate
    FROM        cteSource AS s1
    INNER JOIN cteSource AS s2 ON s2.ProductID = s1.ProductID
    WHERE       s1.recID = s2.recID - 1
), cteYak
AS (
        SELECT     ProductID,
                    FromDate,
                    ToDate,
                    y - ROW_NUMBER() OVER (PARTITION BY ProductID ORDER BY FromDate) AS grp
        FROM        (
                        SELECT ProductID,
                                FromDate,
                                ToDate,
                                CASE
                                    WHEN DATEDIFF(DAY, FromDate, ToDate) <= @Interval
                                        THEN ROW_NUMBER() OVER (PARTITION BY ProductID ORDER BY FromDate)
                                    ELSE NULL
                                END AS y
                        FROM    cteMatch
                    ) AS d
        WHERE       y IS NOT NULL
)
SELECT      ProductID,
            MIN(FromDate) AS FromDate,
            MAX(ToDate) AS ToDate
FROM        cteYak
WHERE       DATEDIFF(DAY, FromDate, ToDate) <= @Interval
GROUP BY    ProductID,
            grp
ORDER BY    ProductID,
            MIN(FromDate)

This runs in less than a second.

Take2:

DECLARE @Interval INT = 7

;WITH cteSource
AS (
    SELECT ProductID,
            TransactionDate,
            ROW_NUMBER() OVER (PARTITION BY ProductID ORDER BY TransactionDate) AS recID
    FROM    Production.TransactionHistory
), cteMatch
AS (
    SELECT      s1.ProductID,
                s1.TransactionDate AS FromDate,
                s2.TransactionDate AS ToDate
    FROM        cteSource AS s1
    INNER JOIN cteSource AS s2 ON s2.ProductID = s1.ProductID
    WHERE       s1.recID = s2.recID - 1
), cteYak
AS (
    SELECT      ProductID,
                FromDate,
                ToDate,
                CASE
                    WHEN DATEDIFF(DAY, FromDate, ToDate) <= @Interval THEN 1
                    ELSE -1
                END * ROW_NUMBER() OVER (PARTITION BY ProductID ORDER BY FromDate) AS recID
    FROM        cteMatch
), cteFinal
AS (
    SELECT      ProductID,
                MIN(FromDate) AS StartDate,
                DATEADD(DAY, @Interval, MAX(ToDate)) AS EndDate,
                1 + MAX(recID) AS recID
    FROM        (
                    SELECT ProductID,
                            FromDate,
                            ToDate,
                            recID - ROW_NUMBER() OVER (PARTITION BY ProductID ORDER BY FromDate) AS grp,
                            recID
                    FROM    cteYak
                    WHERE   recID > 0
                ) AS d
    GROUP BY    ProductID,
                grp

    UNION ALL

    SELECT      ProductID,
                FromDate AS StartDate,
                DATEADD(DAY, @Interval, FromDate) AS EndDate,
                ABS(recID) AS recID
    FROM        cteYak
    WHERE       recID < 0
)

SELECT      ProductID,
            MIN(StartDate) AS StartDate,
            MAX(EndDate) AS EndDate
FROM        cteFinal
GROUP BY    ProductID,
            recID

This also runs in less than a second. And produces the exact same result as Adam's code.

//Peter

Simple Fibonacci calculation

Peso — Sun, 18 Oct 2009 12:08:00 GMT

I have listened to the critique in the comments and removed the advanced version where you can calculate virtually any Fibonacci number. Contact me if you have the need for it again. I won't bother non-interested people with the algorithm here.

Instead, I am concentrating on how this easy example of how to use recursive CTE for calculating the Fibonacci series is constructed.

This is done as an easy exercise for students how to implement a recursive CTE, because the results can be confirmed visually.
Understanding recursive queries is not natural for many people.

For those of you not familiar with Fibonacci series and wonder what uses does it have, I can tell that Fibonacci series is used in a number of areas

Run-time analysis of Euclid's algorithm to determine the greatest common divisor of two integers (the worst case input for this algorithm is a pair of consecutive Fibonacci numbers
The Fibonacci numbers and principle is also used in the financial markets. It is used in trading algorithms, applications and strategies.
Fibonacci numbers are used by some pseudorandom number generators.
Fibonacci numbers are used in a polyphase version of the merge sort algorithm in which an unsorted list is divided into two lists whose lengths correspond to sequential Fibonacci numbers.
The Fibonacci cube is an undirected graph with a Fibonacci number of nodes that has been proposed as a network topology for parallel computing.
A one-dimensional optimization method, called the Fibonacci search technique, uses Fibonacci numbers.
The Fibonacci number series is used for optional lossy compression in the IFF 8SVX audio file format used on Amiga computers

So how is the Fibonacci series built?

The matemathical formula is F(n) = F(n-1) + F(n-2), which in plain english is that any Fibonacci number (greater than 2) is the sum of the two previous numbers.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 etc..

So how do we solve this using a recursive CTE (CTE is an acronym for Common Table Expression which was introduced with Microsof SQL Server 2005)?
Can we solve it at all? A recursive query is nested only one level, right? And the Fibonacci series is "nested" two level?

Yes, we can solve it by using a complementary "sideways" translation, a sort of intermediate storage. First thing, all recursive CTE need an anchor part, a fixed part from which the recursion is expanded from. I do this by using the values {0, 1} which per definition are the two first values of the Fibonacci series.

How is then the recursive part done? I use the two values from the previous iteration and sum them together for the next Fibonacci value. I store that value in a column, shift the columns, and use the previous value in the same recursion level. Easy, huh?

;WITH Fibonacci(n, f, f1)
AS (
        -- This is the anchor part
        -- Initialize level to 1 and set the first two values as per definition
        SELECT CAST(1 AS BIGINT),
                CAST(0 AS BIGINT),
                CAST(1 AS BIGINT)

        UNION ALL

        -- This is the recursive part
        -- Calculate the next Fibonacci value using the previous two values
        -- Shift column (place) for the sum in order to accomodate the previous
        -- value too because next iteration need them both
        SELECT n + 1,
                f + f1,
                f
        FROM    Fibonacci
        -- Stop at iteration 93 because we than have reached maximum limit
        -- for BIGINT in Microsoft SQL Server
        WHERE   n < 93
)
-- Now the easy presentation part
SELECT n,
        f AS Number
FROM    Fibonacci

Performance consideration when using a Table Variable

Peso — Thu, 15 Oct 2009 13:26:00 GMT

This is nothing new to me (I come across this autumn 2007) and probably not to you either but I forgot about it and yesterday it came alive again.
I often choose a table variable for performance reasons (if data is less than 1 page anyway) due to the benefits of no logging etc etc.

But yesterday I wrote a query for Phil Factor's "Subscription List" competition where I had choosen a table variable for the same reasons as before. It took a while to realize why (in this case) the solution with a temporary table was 30% faster than the solution with a table variable.

So I started to investigate the issue. SQL Profiler proofed me right over and over again for the 30% performance gain when using a temporary table over a table variable. It just didn't make any sense to me that the performance should differ that much. The INSERT was derived from a million record table, and the final resultset after grouping was just 120 records of 14 bytes each, well below the "one page rule". How come the solution with table variable was so much slower?
Remember, in this fierce competition we calculated milliseconds for who was in the lead, so 30% was a giant leap.

I won't bore you with details, but finally it come clear to me that it seems table variables doesn't support parallelism. So I went to Google for searching this issue and the results supported my finding. Insert to a table variables makes parallelism impossible. Why? A table variable is just like any other table (except logging).
I found this KB article http://support.microsoft.com/default.aspx/kb/305977/EN-US/ (the INSERT ... EXEC is suppoted with SQL Server 2008).
And this http://msdn.microsoft.com/en-us/library/ms175010(SQL.90).aspx. However it doesn't say why a table doesn't support parallelism, just that doesn't support parallelism.
Here is a page from the SQL Server Engine Storage Team http://blogs.msdn.com/sqlserverstorageengine/archive/2008/03/30/sql-server-table-variable-vs-local-temporary-table.aspx

Here is a testcase in a million record table.

-- First with a temporary table

CREATE TABLE #Sample

(

DateJoined SMALLINT NOT NULL,

DateLeft SMALLINT,

Registrations INT NOT NULL

)

INSERT #Sample

(

DateJoined,

DateLeft,

Registrations

)

SELECT DATEDIFF(MONTH, 0, DateJoined),

DATEDIFF(MONTH, 0, DateLeft),

COUNT(*)

FROM dbo.Registrations

GROUP BY DATEDIFF(MONTH, 0, DateJoined),

DATEDIFF(MONTH, 0, DateLeft)

DROP TABLE #Sample

-- Second with a table variable

DECLARE @Sample TABLE

(

DateJoined SMALLINT NOT NULL,

DateLeft SMALLINT,

Registrations INT NOT NULL

)

INSERT @Sample

(

DateJoined,

DateLeft,

Registrations

)

SELECT DATEDIFF(MONTH, 0, DateJoined),

DATEDIFF(MONTH, 0, DateLeft),

COUNT(*)

FROM dbo.Registrations

GROUP BY DATEDIFF(MONTH, 0, DateJoined),

DATEDIFF(MONTH, 0, DateLeft)

-- And then a conventional SELECT

SELECT DATEDIFF(MONTH, 0, DateJoined),

DATEDIFF(MONTH, 0, DateLeft),

COUNT(*)

FROM dbo.Registrations

GROUP BY DATEDIFF(MONTH, 0, DateJoined),

DATEDIFF(MONTH, 0, DateLeft)

Moving average and Weighted Moving Average

Peso — Fri, 18 Sep 2009 08:03:00 GMT

In my previous blog post, I wrote about how to calculate median value and weighted median value in a secure and fast approach.

In this blog post I am going to describe how you can calculate a fast moving average and also calculate a fast weighted moving average.
This is the sample data we should work with during the whole exercise. I also display both the normal moving average and the weighted moving average at the same time.

DECLARE @Sample TABLE
        (
            dt SMALLDATETIME,
            Rate SMALLMONEY
        )

INSERT @Sample
VALUES (DATEADD(DAY, DATEDIFF(DAY, 10, GETDATE()), 0), 2),
        (DATEADD(DAY, DATEDIFF(DAY, 9, GETDATE()), 0), 2),
        (DATEADD(DAY, DATEDIFF(DAY, 8, GETDATE()), 0), 4),
        (DATEADD(DAY, DATEDIFF(DAY, 7, GETDATE()), 0), 4),
        (DATEADD(DAY, DATEDIFF(DAY, 6, GETDATE()), 0), 5),
        (DATEADD(DAY, DATEDIFF(DAY, 5, GETDATE()), 0), 6),
        (DATEADD(DAY, DATEDIFF(DAY, 4, GETDATE()), 0), 6),
        (DATEADD(DAY, DATEDIFF(DAY, 3, GETDATE()), 0), 8),
        (DATEADD(DAY, DATEDIFF(DAY, 2, GETDATE()), 0), 9),
        (DATEADD(DAY, DATEDIFF(DAY, 1, GETDATE()), 0), 10),
        (DATEADD(DAY, DATEDIFF(DAY, 0, GETDATE()), 0), 11),
        (DATEADD(DAY, DATEDIFF(DAY, -1, GETDATE()), 0), 9)

DECLARE @Result TABLE
        (
            dt SMALLDATETIME,
            ma SMALLMONEY,
            wma SMALLMONEY
        )

First of all, I am going to show you an approach made by a cursor. This is actually one of the fastest way to accomplish this task!
It is also very resource friendly and uses (n) combinations to get the results.

-- Declare some variables needed by the CURSOR
DECLARE @Date SMALLDATETIME,
        @Rate SMALLMONEY,
        @RateCurrent SMALLMONEY,
        @RateMinusOne SMALLMONEY,
        @RateMinusTwo SMALLMONEY

DECLARE curUgly CURSOR FOR SELECT      dt,
                                        Rate
                            FROM        @Sample
                            ORDER BY    dt

OPEN    curUgly

FETCH   NEXT
FROM    curUgly
INTO    @Date,
        @Rate

WHILE @@FETCH_STATUS = 0
    BEGIN
        SELECT @RateMinusTwo = @RateMinusOne,
                @RateMinusOne = @RateCurrent,
                @RateCurrent = @Rate

        IF @RateMinusTwo IS NOT NULL AND @RateMinusOne IS NOT NULL AND @RateCurrent IS NOT NULL
            INSERT @Result
                    (
                        dt,
                        ma,
                        wma
                    )
            VALUES (
                        @Date,
                        (@RateCurrent + @RateMinusOne + @RateMinusTwo) / 3,
                        0.7 * @RateCurrent + 0.2 * @RateMinusOne + 0.1 * @RateMinusTwo
                    )

        FETCH   NEXT
        FROM    curUgly
        INTO    @Date,
                @Rate
    END

CLOSE       curUgly
DEALLOCATE curUgly

SELECT     dt AS [Date],
            ma AS NormalMovingAverage,
            wma AS WeightedMovingAverage
FROM        @Result
ORDER BY    dt

But, as you can see it is not very configurable. What if you suddenly wants a moving average over 5 days? Well, you simply have to rewrite several parts such as declare, initial select statement, if clause and the insert part. Essentially the whole code.

Now, what if we want to write a SET-based query to do the same thing? The most frequent used query I have seen before, is a self-join query (Cartesian product) like this.
It is very slow since it tries all combinatations (n * n) before filtering out the rows to be used. However it is more configurable friendly.

-- A common SET-based solution
SELECT     t1.dt AS [Date],
            AVG(t2.Rate) AS NormalMovingAverage,
            SUM(CASE DATEDIFF(DAY, t2.dt, t1.dt)
                    WHEN 0 THEN 0.7 * t2.Rate
                    WHEN 1 THEN 0.2 * t2.Rate
                    WHEN 2 THEN 0.1 * t2.Rate
                END
            ) AS WeightedMovingAverage
FROM        @Sample AS t1
INNER JOIN @Sample AS t2 ON DATEDIFF(DAY, t2.dt, t1.dt) BETWEEN 0 AND 2
GROUP BY    t1.dt
HAVING      COUNT(t1.dt) = 3
ORDER BY    t1.dt

Even if the code looks SET-based, it is not in reality. I know Jeff Moden would call this RBAR (Row-By-Agonizing-Row). However, the code is more maintainable and altering from a 3 day to a 5 day moving average will make you have to change the code in 3 places only; the case statement, between value and having clause. Much better, but also absolutely worse performance compared to a cursor.

Surely there must be a way to combine these two approaches? Yes, there is, and the combinations needed to get the result is only (3 * n) which is much less than the other set-based code but also somewhat more than the cursor approach.

See this code.

-- A better SET-based approach
SELECT     DATEADD(DAY, d.Number, s.dt) AS [Date],
            AVG(s.Rate) AS NormalMovingAverage,
            SUM(d.Coefficient * s.Rate) AS WeightedMovingAverage
FROM        @Sample AS s
CROSS JOIN (
                VALUES (0, 0.7),
                        (1, 0.2),
                        (2, 0.1)
            ) AS d(Number, Coefficient)
GROUP BY    DATEADD(DAY, d.Number, s.dt)
HAVING      COUNT(*) = 3
ORDER BY    DATEADD(DAY, d.Number, s.dt)

Changing this piece of code to a 5 day moving average only takes editing in 2 places; the derived table and the having clause. If you have the coefficients in an auxiliary table, there will be only one edit to be made! In the auxiliary table, because the having part can equal a subquery calculating the number of records in the auxiliary table.

For comparison, I tested all three methods on 5,000 sample rows and got this result

CURSOR             6,813 ms
Common set-based  20,577 ms
Better set-based     127 ms

//Peso

Median and Weighted Median calculations

Peso — Fri, 18 Sep 2009 07:02:00 GMT

Hi all!

This is my first blog post here at sqlblog.com after some convincing arguments made by Adam Machanic.
Some of you know me as Peso, and I have mostly blogged at SQLTeam.com before.

Yesterday Joe Celko posted a query on microsoft.public.sqlserver.programming newsgroup of how to write an elegant query for Weighted Median calculation.
He managed to get the correct results but also ended up with some pretty ugly code. Joe also wrote he had a feeling of an elegant query should exist but was not seeing it.

Anyway, since some of Celko's books have helped me in the past, I thought I should return the favor.

Consider this sample data

DECLARE @Foo TABLE
        (
            x SMALLMONEY NOT NULL
        )

INSERT @Foo
VALUES (1),
        (2),
        (2),
        (3),
        (3),
        (3)

The most common approach to calculate the median value I have seen is

SELECT AVG(x)
FROM    (
            SELECT x,
                    ROW_NUMBER() OVER (ORDER BY x DESC) AS a,
                    ROW_NUMBER() OVER (ORDER BY x) AS b
            FROM    @Foo
        ) AS d
WHERE   b - a BETWEEN -1 AND 1

It's a great method and it works in almost all cases. Yes, in almost all cases. There are circumstances where SQL Server will not give the correct result.
Adam Machanic has described the problem in this Connect issue. It seems the table need some key to work properly, but as seen with Celko's sample data, there is no key in this scenario.

x       a b a-b
1.0000 6 1    5
2.0000 4 2    2
2.0000 5 3    2
3.0000 1 4   -3
3.0000 2 5   -3
3.0000 3 6   -3

As you can see, the difference calculated by a-b suddenly doesn't match!
How can we overcome this behaviour? How can we write a piece of code that works all times?
It's not that hard. See this query.

-- Median by Peso
SELECT AVG(x)
FROM    (
            SELECT x,
                    2 * ROW_NUMBER() OVER (ORDER BY x) - COUNT(*) OVER () AS y
            FROM    @Foo
        ) AS d
WHERE   y BETWEEN 0 AND 2

Yes it works! And now how to do the weighted median? Well, we follow the same approach and write this piece of code.

-- Weighted Median by Peso
SELECT SUM(y) / SUM(t)
FROM    (
            SELECT SUM(x) OVER (PARTITION BY x) AS y,
                    2 * ROW_NUMBER() OVER (ORDER BY x) - COUNT(*) OVER () AS z,
                    COUNT(*) OVER (PARTITION BY x) AS t
            FROM    @Foo
        ) AS d
WHERE   z BETWEEN 0 AND 2

I think the query qualifies as elegant. Let's see if Celko thinks the same.
As you can see, the query is only slightly more complicated than the normal Median. I leave the math behind it as an exercise to the reader.

//Peso