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

Adam Machanic — Tue, 08 Dec 2009 19:13:00 GMT

When working with time intervals, we often want to ask a couple of basic questions:

Which time periods are not covered by our intervals? These are known as "gaps".
What are the time ranges that we are fully covering? These are known as "islands".

If you're unfamiliar with "gaps" and "islands" I highly recommend reading some of Itzik Ben-Gan's recent work in SQL Server Magazine. He's had a great series going on the topic. But one thing that he hasn't found a good T-SQL solution for is a problem that I call "fuzzy islands."

When is an island fuzzy? When it doesn't necessarily have a fixed end time. For an example of this, consider a store, selling a number of products. Management might want to see a report showing when each product was selling. This is, effectively, an island question. The goal is to find all of the covered ranges during which sales occurred. But running such a report, you might find that way too much data is returned. A given product may have sold units on Monday, Tuesday, and Thursday, but for some reason no one bought one on Wednesday. Creating a new island every time there is a small gap will create a 300-page report where a 1-page dashboard might suffice--not a good user experience, nor a good way of representing the data. The solution? Introduce a bit of fuzziness--a rule that says, for instance, that a gap is only a gap if it's longer than 7 days.

Answering the fuzzy islands question is not a very difficult thing to do in T-SQL. The basic algorithm follows:

Find all of the "start" dates or times. These are simply those dates or times for which a previous date or time in the fuzzy interval does not exist. So if a row is dated 2009-12-08 and our fuzzy granularity is 7 days, we know we have a start date if there is no other covered data from the end of November.
For each start date identified, find the minimum date greater than the start date. This is done by looking ahead rather than behind, so if our date is 2009-12-08 and we have a granularity of 7 days, we'll look forward until December 15th.
Optionally, add the fuzzy factor to the end date. This is something that I think is a good idea, as it introduces the concept of an "active" interval--a period over which, for example, a product is considered to have been selling. The interval shouldn't necessarily terminate the day that the last sale occurred. But of course this depends on the situation in question.

The following query produces a fuzzy islands report for each product in the AdventureWorks (or AdventureWorks2008) Production.TransactionHistory table. You can modify the @active_interval variable to tweak the fuzziness and change the output.

--Find all "active" product time ranges, meaning that the product
--has sold within the previous 7 days
DECLARE @active_interval INT = 7

SELECT DISTINCT
    t_s.ProductID,
    t_s.TransactionDate AS StartDate,
    DATEADD
    (
        dd,
        @active_interval,
        (
            SELECT
                MIN(t_e.TransactionDate)
            FROM Production.TransactionHistory AS t_e
            WHERE
                t_e.ProductID = t_s.ProductID
                AND t_e.TransactionDate >= t_s.TransactionDate
                AND NOT EXISTS
                (
                    SELECT *
                    FROM Production.TransactionHistory AS t_ae
                    WHERE
                        t_ae.ProductID = t_s.ProductID
                        AND t_ae.TransactionDate BETWEEN 
                            DATEADD(dd, 1, t_e.TransactionDate) 
                            AND DATEADD(dd, @active_interval, t_e.TransactionDate)
                )
        )
    ) AS EndDate
FROM 
(
    SELECT DISTINCT
        ProductID,
        TransactionDate
    FROM Production.TransactionHistory
) AS t_s
WHERE
    NOT EXISTS
    (
        SELECT *
        FROM Production.TransactionHistory AS t_ps
        WHERE
            t_ps.ProductID = t_s.ProductID
            AND t_ps.TransactionDate BETWEEN 
                DATEADD(dd, -@active_interval, t_s.TransactionDate) 
                AND DATEADD(dd, -1, t_s.TransactionDate)
    )
ORDER BY
    ProductID,
    StartDate
GO

Running this query you'll find that it works... But the results are returned a bit more slowly than we might desire--15 to 16 seconds on my end. Looking at the query plan, the reason for this becomes quite obvious: Lots and lots of table scans. How can we eliminate all of the overhead?

SQLCLR to the rescue. The best way to solve this problem--at least until the SQL Server team adds proper OVER clause support (LAG and LEAD, specifically)--is to use a cursor algorithm. We could do this in a T-SQL cursor, but why bother? Cursor logic in SQLCLR is much, much faster.

To solve the problem, I implemented an enumerator, called active_products_enumerator. The enumerator is initialized using a SqlDataReader and an "active interval" -- the number of days we're allowing for fuzziness. The DataReader is expected to return rows ordered by ProductID and TransactionDate. The enumeration process uses the following algorithm:

If the current ProductID is not the same as the previous ProductID, return an end date for the previous interval and start a new one
If the current period date is greater than the previous period date plus the active interval, return an end date for the previous interval and start a new one
Otherwise, continue

Following is the MoveNext method for the enumerator (the complete code is attached to this post so that you can run it on your end without my bombarding you with a gigantic code-filled post):

public bool MoveNext()
{
    try
    {
        current_results = null;

        while (r.Read())
        {
            new_ProductID = r.GetSqlInt32(0);
            new_period_date = r.GetDateTime(1);

            if (new_ProductID != ProductID)
            {
                if (ProductID != 0)
                {
                    current_results = new results(
                        ProductID,
                        StartDate,
                        period_plus_interval);
                }

                ProductID = new_ProductID;
                StartDate = new_period_date;
                period_plus_interval = new_period_date.AddDays(activeInterval);

                if (current_results != null)
                    return (true);
            }
            else
            {
                if (period_plus_interval < new_period_date)
                {
                    current_results = new results(
                        ProductID,
                        StartDate,
                        period_plus_interval);

                    StartDate = new_period_date;
                }

                period_plus_interval = new_period_date.AddDays(activeInterval);

                if (current_results != null)
                    return (true);
            }
        }

        //return the last row of data
        if (ProductID != 0)
        {
            current_results = new results(
                ProductID,
                StartDate,
                period_plus_interval);

            //set this to 0 so we don't return another row
            ProductID = 0;
        }

        if (current_results != null)
            return (true);
        else
        {
            r.Dispose();
            return (false);
        }
    }
    catch
    {
        r.Dispose();
        throw;
    }
}

Put into a table-valued function, as the attached code does, this algorithm will return the same data as the T-SQL query in under a third of a second on my end--around 45 times faster than the T-SQL version.

Note that I've played some games with a loopback connection to get this whole thing to work. That's a topic for a future blog post, so stay tuned. In the meantime, please realize that you'll have to catalog the assembly with EXTERNAL_ACCESS permission to make this happen.

This post was created for T-SQL Tuesday, the revolving SQL Server blog party, hosted this month by... me. Enjoy!

Invitation to Participate in T-SQL Tuesday #001: Date/Time Tricks

Adam Machanic — Mon, 30 Nov 2009 17:47:00 GMT

T-SQL Tuesday is the SQL Server blogosphere's first recurring, revolving blog party. The idea is simple: Each month a blog will host the party, and about a week before the second Tuesday of the month a theme will be posted. Any blogger that wishes to participate is invited to write a post on the chosen topic. The event is called "T-SQL Tuesday", but any post that is related to both SQL Server and the theme is fair game. So feel free to post about SSIS, SSRS, Java integration, or whatever other technologies you're working with in conjunction with SQL Server. Even if your post includes no T-SQL we still want to see it.

The posts must go live on the second Tuesday of the month, by (or before) 23:59 PST. Each post must link back to the host blog's post, and the blogger should make sure that a trackback has been generated and successfully posted to the host blog; if not, a comment should be posted on the host blog with a link, so that the host blogger can find the post. The host blogger will then take all of the posts and within a day or two will compile a "roundup"--a brief summary with links--so that readers can find all of the relevant posts.

Why do this? Several reasons: It's fun, it's going to generate a lot of interesting content, and it's going to bring lots of bloggers into the fold and improve our overall community by creating a lot of links between blogs. Any blogger is invited to participate, whether the blog has been live for six days or six years. If you can write, you should join in the fun.

Rules of engagement for hosts: Although anyone can join in the party, hosting has a slightly higher bar: Your blog must have been active in the last six months ("active" is defined as at least one post per month), and you must have participated in T-SQL Tuesday events on at least two prior occasions. Since that's impossible until we've had two events, I'll host the first two myself. After that it will move around to as many blogs as we can get involved--and I hope that a number of you out there decide to go for it. The host blogger is not required to write a participating post to be included in the roundup, but is free to do so if he or she chooses. Want to host? Contact me through my blog--I'll keep a waiting list and control it centrally so that it doesn't devolve into anarchy too quickly.

So that's that. If you bothered to read the title of this post you're aware that the topic for this month is Date/Time Tricks. Write a blog post that talks about dates and times--this can be based around T-SQL programming, data modeling, ETL, reporting, or whatever else you're using dates and times for (and who isn't?). Make sure that your post goes live on Tuesday, December 8, between 00:00 and 23:59 PST. Make it clear in your post that it's for T-SQL Tuesday, and make sure it links back here. Finally, make absolutely certain that a comment shows up here so that I can find the post.

Questions? Comments? Post here.

Enjoy! I'm looking forward to the start of a great blog tradition in the SQL Server community.

Search results matching tags 'T-SQL Tuesday' and 'time'

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

Invitation to Participate in T-SQL Tuesday #001: Date/Time Tricks