Peter Larsson : Algorithm, Math

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

Date and Time concurrency

Peso — Sat, 19 Sep 2009 10:51:00 GMT

In the past I mostly have given the advice to break down all date intervals into the smallest part (often minutes) and then group by the minute.

-- Prepare sample data
DECLARE  @Data TABLE
         (
             RecID INT IDENTITY(1, 1) PRIMARY KEY CLUSTERED,
             CreateDate DATETIME,
             DeleteDate DATETIME
         )

-- Populate sample data
INSERT  @Data
        (
            CreateDate,
            DeleteDate
        )
SELECT  '2009-01-14 22:33', '2009-01-14 22:35' UNION ALL
SELECT  '2009-01-14 22:33', '2009-01-14 22:33' UNION ALL
SELECT  '2009-01-14 22:34', '2009-01-14 22:35' UNION ALL
SELECT  '2009-01-14 22:35', '2009-01-14 22:35' UNION ALL
SELECT  '2009-01-14 22:35', '2009-01-14 22:36' UNION ALL
SELECT  '2009-01-14 22:37', '2009-01-14 22:37' UNION ALL
SELECT  '2009-01-14 22:39', '2009-01-14 22:39' UNION ALL
SELECT  '2009-01-14 22:38', '2009-01-14 22:38' UNION ALL
SELECT  '2009-01-14 22:39', '2009-01-14 22:39' UNION ALL
SELECT  '2009-01-14 22:41', '2009-01-14 22:41' UNION ALL
SELECT  '2009-01-14 22:43', '2009-01-14 22:44' UNION ALL
SELECT  '2009-01-14 22:52', '2009-01-14 22:52' UNION ALL
SELECT  '2009-01-14 22:53', '2009-01-14 22:53' UNION ALL
SELECT  '2009-01-14 22:53', '2009-01-14 22:53' UNION ALL
SELECT  '2009-01-14 22:56', '2009-01-14 22:57' UNION ALL
SELECT  '2009-01-14 22:57', '2009-01-14 22:57' UNION ALL
SELECT  '2009-01-14 22:58', '2009-01-14 22:58' UNION ALL
SELECT  '2009-01-14 22:58', '2009-01-14 22:59' UNION ALL
SELECT  '2009-01-14 22:59', '2009-01-14 22:59'

DECLARE @From INT,
        @To INT

SELECT  @From = MIN(DATEDIFF(MINUTE, 0, CreateDate)),
        @To = MAX(DATEDIFF(MINUTE, 0, DeleteDate))
FROM    @Data

SELECT      w.theTime,
            COUNT(*)
FROM        (
                SELECT  DATEADD(MINUTE, Number + @From, 0) AS theTime
                FROM    master..spt_values
                WHERE   Type = 'P'
                        AND Number <= @To - @From
            ) AS w
INNER JOIN @Data AS d ON d.CreateDate <= w.theTime
                AND d.DeleteDate >= w.TheTime
GROUP BY    w.theTime
ORDER BY    COUNT(*) DESC,
            w.theTime DESC

Well, sometimes the time interval is too large to hold all minute values, and what if you all of a sudden decides to break down the calculation into milliseconds?

The problem resembles about date range searching. Most people tend to use

SELECT  *
FROM    Table1
WHERE   Col1 BETWEEN '20090129 00:00:00.000' AND '20090129 23:59:59.997'

What you should use is open-ended search criteria as

SELECT  *
FROM    Table1
WHERE   Col1 >= '20090129'
        AND Col1 < '20090130'

The solution for this type of problem can then look something like this

-- Prepare sample data

DECLARE @Data TABLE

(

RecID INT IDENTITY(1, 1) PRIMARY KEY CLUSTERED,

CreateDate DATETIME,

DeleteDate DATETIME

)

-- Populate sample data

INSERT @Data

(

CreateDate,

DeleteDate

)

SELECT '2009-01-14 22:33:41.857', '2009-01-14 22:35:59.543' UNION ALL

SELECT '2009-01-14 22:33:42.857', '2009-01-14 22:33:59.543' UNION ALL

SELECT '2009-01-14 22:34:26.513', '2009-01-14 22:35:43.233' UNION ALL

SELECT '2009-01-14 22:35:14.920', '2009-01-14 22:35:31.530' UNION ALL

SELECT '2009-01-14 22:35:50.373', '2009-01-14 22:36:07.340' UNION ALL

SELECT '2009-01-14 22:37:26.793', '2009-01-14 22:37:44.857' UNION ALL

SELECT '2009-01-14 22:39:22.077', '2009-01-14 22:39:38.543' UNION ALL

SELECT '2009-01-14 22:38:03.873', '2009-01-14 22:38:20.827' UNION ALL

SELECT '2009-01-14 22:39:39.247', '2009-01-14 22:39:55.840' UNION ALL

SELECT '2009-01-14 22:41:25.857', '2009-01-14 22:41:42.467' UNION ALL

SELECT '2009-01-14 22:43:14.607', '2009-01-14 22:44:31.483' UNION ALL

SELECT '2009-01-14 22:52:10.233', '2009-01-14 22:52:26.827' UNION ALL

SELECT '2009-01-14 22:53:08.187', '2009-01-14 22:53:24.983' UNION ALL

SELECT '2009-01-14 22:53:36.483', '2009-01-14 22:53:53.060' UNION ALL

SELECT '2009-01-14 22:56:56.403', '2009-01-14 22:57:13.263' UNION ALL

SELECT '2009-01-14 22:57:28.247', '2009-01-14 22:57:44.780' UNION ALL

SELECT '2009-01-14 22:58:16.090', '2009-01-14 22:58:32.623' UNION ALL

SELECT '2009-01-14 22:58:52.137', '2009-01-14 22:59:08.670' UNION ALL

SELECT '2009-01-14 22:59:21.170', '2009-01-14 22:59:37.733'

-- Prepare staging table

DECLARE @Stage TABLE

(

RecID INT IDENTITY(1, 1) PRIMARY KEY CLUSTERED,

FromTime DATETIME NOT NULL,

ToTime DATETIME NOT NULL

)

-- Populate staging table

INSERT @Stage

(

FromTime,

ToTime

)

SELECT u.theTime,

u.theTime

FROM @Data AS d

UNPIVOT (

theTime

FOR theCol IN (d.CreateDate, d.DeleteDate)

) AS u

GROUP BY u.theTime

ORDER BY u.theTime

-- Update with closest range

UPDATE s

SET s.ToTime = w.FromTime

FROM @Stage AS s

INNER JOIN @Stage AS w ON w.RecID = s.RecID + 1

-- Delete last time

DELETE

FROM @Stage

WHERE RecID = SCOPE_IDENTITY()

-- Display the result

SELECT s.FromTime,

s.ToTime,

COUNT(*) AS Occurencies

FROM @Data AS d

INNER JOIN @Stage AS s ON s.FromTime < d.DeleteDate

AND s.ToTime > d.CreateDate

GROUP BY s.FromTime,

s.ToTime

HAVING COUNT(*) > 1

ORDER BY COUNT(*) DESC,

s.FromTime DESC

Finally, there is also a twist with this approach. You do not only get for which exact minute there is the most concurrency, you get the whole range!

And you can also see the gaps, where no concurrency occurs at all.

-- Display the gaps

SELECT s.FromTime,

s.ToTime,

COUNT(d.CreateDate) AS Occurencies

FROM @Data AS d

RIGHT JOIN @Stage AS s ON s.FromTime < d.DeleteDate

AND s.ToTime > d.CreateDate

GROUP BY s.FromTime,

s.ToTime

HAVING COUNT(d.CreateDate) = 0

ORDER BY COUNT(d.CreateDate) DESC,

s.FromTime

//Peso

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