Solutions to TSQL Challenge – Reoccurring Visits

Last week I provided a T-SQL challenge involving a table called DailyVisits that holds information about daily visits to a website. Your task was to identify, for each day, certain statistics compared to the previous day, like how many visits there were, how many visitors were added, how many removed, and how many remained. You can find the puzzle details here. I’d like to thank all those who submitted solutions including Peter Larsson (Peso), Alejandro Mesa, simran and Tomaz Kastrun.

To test the performance of the solutions I populated the DailyVisits table with about 180,000 rows using the following code:

-- large set of sample data for perf tests

-- about 180,000 rows

DECLARE

  @from AS DATE = '20110101',

  @to   AS DATE = '20110630';

TRUNCATE TABLE dbo.DailyVisits;

INSERT INTO dbo.DailyVisits WITH (TABLOCK) (dt, visitor)

  SELECT dt, CAST(number AS VARCHAR(10)) AS visitor

  FROM dbo.GetDates(@from, @to) AS D

    CROSS APPLY (SELECT number, ABS(CHECKSUM(NEWID())) % 2 AS rnd

                 FROM master..spt_values

                 WHERE type = 'p'

                   AND number BETWEEN 1 AND 2000) AS A

  WHERE rnd = 1;

I also added the following index:

CREATE UNIQUE INDEX idx_visitor_dt ON dbo.DailyVisits(visitor, dt);

Part of the difficulty in addressing the task was that there was no assurance for visits every day; technically, it is possible to have zero visits in some days, and then there are no entries for such days in the DailyVisits table. But you had to include days without visits in the output if they fell in the input range of dates. In the puzzle’s comments section you can find that simran and Tomaz Kastrun addressed this difficulty by using either a loop or a recursive query to loop through the dates in the input range.

Simran’s Solutions

Simran used in one solution a loop and in the other recursion to iterate through the dates in the input range and then used subueries to calculate the different measures. Both solutions ran over a minute against the larger set of sample data.

Tomaz Kastrun’s Solutions

Tomaz Kastrun used recursion in his first solution to create the dates in the input period. In his second solution he used master..spt_values as alternative to an auxiliary table of numbers, and based on the numbers generated the dates in the input period. Then in the second part of the solutions, Tomaz joined the set of dates produced in the first step with DailyVisits twice, using left outer joins—once for current date, and second time for previous date. Then he use expressions checking counts of each measure by looking at current vs. previous elements. Both solutions ran over a minute.

GetDates Functions

Alejandro, I and Peso used a helper table called GetDates that generates a set of dates within an input range. Here’s the function’s definition:

-- definition of GetDates function

IF OBJECT_ID('dbo.GetDates', 'IF') IS NOT NULL

  DROP FUNCTION dbo.GetDates;

GO

CREATE FUNCTION dbo.GetDates(@low AS DATE, @high AS DATE) RETURNS TABLE

AS

RETURN

  WITH

    L0   AS (SELECT c FROM (VALUES(1),(1)) AS D(c)),

    L1   AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),

    L2   AS (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),

    L3   AS (SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),

    L4   AS (SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B),

    L5   AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B),

    Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum

            FROM L5)

  SELECT TOP (DATEDIFF(day, @low, @high) + 1) DATEADD(day, rownum - 1, @low) AS dt

  FROM Nums

  ORDER BY rownum;

GO

-- test function

SELECT dt

FROM dbo.GetDates('20110601', '20110608') AS D;

dt

----------

2011-06-01

2011-06-02

2011-06-03

2011-06-04

2011-06-05

2011-06-06

2011-06-07

2011-06-08

Alejandro’s Solutions

Here’s Alejandro’s first solution (call it Alejandro 1):

Run time: 55 seconds.

Description (by Alejandro): My approach was to generate the Cartesian product between visitors and dates in the range, which could be very expensive if there are many visitors, or many dates, or both.  Then doing an outer join with the table to flag each row as visit or no visit.  Finally a self join to compare current and previous visit to calculate if current visit was added, removed, or remained, and grouping by date.

Solution code:

DECLARE

  @from AS DATE = '20110101',

  @to   AS DATE = '20110630';

-- self join

WITH V AS (

SELECT DISTINCT visitor

FROM dbo.DailyVisits

)

, D AS (

SELECT dt

FROM dbo.GetDates(@from, @to)

)

, EDV AS (

SELECT

      V.visitor,

      D.dt,

      CASE WHEN DV.visitor IS NULL AND DV.dt IS NULL THEN 0 ELSE 1 END AS visit_cnt

FROM

      (

      V

      CROSS JOIN

      D

      )

      LEFT OUTER JOIN

      dbo.DailyVisits AS DV

      ON V.visitor = DV.visitor

      AND D.dt = DV.dt

)

SELECT

      A.dt,

      SUM(ISNULL(A.visit_cnt, 0)) AS numvisits,

      SUM(CASE WHEN A.visit_cnt > ISNULL(B.visit_cnt, 0) THEN 1 ELSE 0 END) AS added,

      SUM(CASE WHEN A.visit_cnt < ISNULL(B.visit_cnt, 0) THEN 1 ELSE 0 END) AS removed,

      SUM(CASE WHEN A.visit_cnt + ISNULL(B.visit_cnt, 0) = 2 THEN 1 ELSE 0 END) AS remained

FROM

      EDV AS A

      LEFT OUTER JOIN

      EDV AS B

      ON A.visitor = B.visitor

      AND A.dt = DATEADD([day], 1, B.dt)

GROUP BY

      A.dt

ORDER BY

      A.dt

Alejandro also proposed a second solution (call it Alejandro 2) that uses window functions called LAG and LEAD that aren’t yet supported by SQL Server, but are planned to be supported in SQL Server Denali:

DECLARE

  @from AS DATE = '20110101',

  @to   AS DATE = '20110630';

WITH R AS

(

  SELECT dt AS cur_dt, visitor,

    CASE WHEN DATEDIFF(day, LAG(dt) OVER(PARTITION BY visitor ORDER BY dt), dt) = 1 THEN 1 ELSE 0 END AS prvbit,

    CASE WHEN DATEDIFF(day, dt, LEAD(dt) OVER(PARTITION BY visitor ORDER BY dt)) = 1 THEN 1 ELSE 0 END AS nxtbit

  FROM dbo.DailyVisits

)

SELECT dt,

  COUNT(CASE WHEN dt = cur_dt THEN 1 END) AS numvisits,

  COUNT(CASE WHEN dt = cur_dt AND COALESCE(prvbit, 0) = 0 THEN 1 END) AS added,

  COUNT(CASE WHEN dt <> cur_dt AND nxtbit = 0 THEN 1 END) AS removed,

  COUNT(CASE WHEN dt = cur_dt AND prvbit = 1 THEN 1 END) AS remained

FROM dbo.GetDates(@from, @to) AS D

  LEFT OUTER JOIN R

    ON dt IN(cur_dt, DATEADD(day, 1, cur_dt))

GROUP BY dt;

Performance remains to be seen in the future. As for the logic of the solution, the LAG function returns a value from the previous row in the partition based on the given ordering, and LEAD returns a value from the next row. The solution defines a CTE called R where in addition to the existing info from DailyVisits it computes two flags using LAG and LEAD indicating whether the current visitor had a visit the day before and day after, respectively. Then the solution performs a left outer join between the set of dates in the input range obtained from the GetNums table and R. Finally, in the outer query, the solution analyzes the flags to determine the needed statistics.

Itzik’s Solutions

Here’s my first solution (call it Itzik 1):

Run time: 31 seconds.

Description: The solution performs a full outer join between two instances of DailyVisits—one representing the current row and the other the previous row. The join predicate is: CUR.visitor = PRV.visitor AND CUR.dt = DATEADD(day, 1, PRV.dt). The solution then performs a left outer join between the set of dates in the input range obtained from GetDates (call it D) and the result of the aforementioned full join. The join predicate is: D.dt IN (CUR.dt, DATEADD(day, 1, PRV.dt)). The solution then groups the rows by D.dt, and computes the desired statistics by analyzing the details in the current vs. previous rows.

Solution code:

DECLARE

  @from AS DATE = '20110101',

  @to   AS DATE = '20110630';

SELECT D.dt,

  COUNT(CUR.visitor) AS numvisits,

  COUNT(CASE WHEN CUR.visitor IS NOT NULL AND PRV.visitor IS NULL THEN 1 END) AS added,

  COUNT(CASE WHEN CUR.visitor IS NULL AND PRV.visitor IS NOT NULL THEN 1 END) AS removed,

  COUNT(CASE WHEN CUR.visitor = PRV.visitor THEN 1 END) AS remained

FROM dbo.GetDates(@from, @to) AS D

  LEFT JOIN

    (           dbo.DailyVisits AS CUR

      FULL JOIN dbo.DailyVisits AS PRV

             ON CUR.visitor = PRV.visitor

            AND CUR.dt = DATEADD(day, 1, PRV.dt))

         ON D.dt IN (CUR.dt, DATEADD(day, 1, PRV.dt))

GROUP BY D.dt;

In my second solution (call it Itzik 2) I also used the LAG function that is planned to be supported in SQL Server Denali. Here’s the solution’s code:

DECLARE

  @from AS DATE = '20110101',

  @to   AS DATE = '20110630';

WITH C1 AS

(

  SELECT dt, visitor,

    CASE WHEN DATEDIFF(day, LAG(dt) OVER(PARTITION BY visitor ORDER BY dt), dt) = 1

      THEN 1 ELSE 0 END AS prvbit

  FROM dbo.DailyVisits

),

C2 AS

(

  SELECT dt,

    COUNT(*) AS numvisits,

    SUM(1-prvbit) AS added,

    SUM(prvbit) AS remained,

    -- removed = prev numvisits - cur remained

    CASE WHEN DATEDIFF(day, LAG(dt) OVER(ORDER BY dt), dt) = 1

      THEN LAG(COUNT(*)) OVER(ORDER BY dt) - SUM(prvbit) ELSE 0 END AS removed,

    0 AS filler

  FROM C1

  GROUP BY dt

  UNION ALL

  SELECT dt, 0, 0, 0, 0, 1

  FROM dbo.GetDates(@from, @to) AS D

  WHERE dt NOT IN (SELECT dt FROM dbo.DailyVisits)

)

SELECT dt,

  numvisits,

  added,

  remained,

  CASE WHEN filler = 0 THEN removed ELSE

    LAG(numvisits) OVER(ORDER BY dt) END AS removed

FROM C2;

The CTE C1 uses the LAG function to compute a flag (call it prvbit) that indicates whether the visitor had a previous visit the day before.

The CTE C2 unifies the results of two queries. One query groups the rows from C1 by dt, and computes based on the prvbit flag how many daily visits there were, how many added and how many remained. To calculate how many were removed you can subtract from the previous day’s number of visits the current day’s remained number. To get the previous day’s number of visits, the solution uses the LAG function again. The solution then queries the GetDates function returning all dates from the input range that do not appear in DailyVisits, and unifies the rows with the result of the grouped query. The code assigns a flag 1 to the rows from GetDates indicating that those are filler rows, and the flag 0 to the rows in the result of the grouped query to indicate those aren’t filler rows. 

Finally, the outer query queries the CTE C2, and computes in filler rows the removed attribute using the LAG function a third time. The number of visits in the previous day is the number of removed visits in the filler row.

Performance is yet to be seen, but I suspect the query will perform quite good.

Peso’s Solution

And the best saved for last! Peso’s solution ran only 2 seconds against the large set of sample data. It is very clever and creative, and I enjoyed very much following its logic. Here’s the solution code followed by Peso’s description of the solution:

DECLARE

  @from AS DATE = '20110101',

  @to   AS DATE = '20110630';

;WITH cteSource(dt, NumVisits, Added, Removed)

AS (

            SELECT              dt,

                                    SUM(NumVisits) AS NumVisits,

                                    SUM(Added) AS Added,

                                    SUM(Removed) AS Removed

            FROM                (

                                                SELECT              DATEADD(DAY, f.DayDelta, w.dt) AS dt,

                                                                        w.Visitor,

                                                                        f.NumVisits,

                                                                        f.Added,

                                                                        f.Removed

                                                FROM                dbo.DailyVisits AS w

                                                CROSS JOIN       (

                                                                                    VALUES  (0, 1,  1, -1),

                                                                                                (1, 0, -1,  1)

                                                                        ) AS f(DayDelta, NumVisits, Added, Removed)

                                                WHERE              w.dt BETWEEN DATEADD(DAY, -1, @From) AND @To

                                    ) AS d

            WHERE              dt BETWEEN @From AND @To

            GROUP BY          dt,

                                    Visitor

)

SELECT              dt,

                        SUM(NumVisits) AS NumVisits,

                        SUM(Added) AS Added,

                        SUM(Removed) AS Removed,

                        SUM(Remained) AS Remained

FROM                (

                                    SELECT              dt,

                                                            SUM(NumVisits) AS NumVisits,

                                                            SUM(CASE WHEN Added = 1 THEN 1 ELSE 0 END) AS Added,

                                                            SUM(CASE WHEN Removed = 1 THEN 1 ELSE 0 END) AS Removed,

                                                            SUM(CASE WHEN 1 IN (Added, Removed) THEN 0 ELSE 1 END) AS Remained

                                    FROM                cteSource

                                    GROUP BY          dt

                                    UNION ALL

                                    SELECT              dt,

                                                            0 AS NumVisits,

                                                            0 AS Added,

                                                            0 AS Removed,

                                                            0 AS Remained

                                    FROM                dbo.GetDates(@From, @To)

                        ) AS d

GROUP BY          dt;

Peso’s description:

This was an interesting challenge because it had a “make it or break it” logic which was not that obvious at first glance. My beta query (in my head) used a JOIN which I think most of you used too. But when you think of the actual problem in this challenge, it’s about “carry-forward” from one day to next.

What does this mean, in terms of logic and performance? Well, if the problem is to carry forward some values from one day to the next day, which is the fastest way to get the final values for the two dates? It’s not by joining, because an efficient self-join need extremely well built indexes and even when they are in place, SQL Server optimizer still need to seek out the very next day. And here is another catch by using an index; what if there is no next day, as in the example code given in this challenge?

A better approach is to calculate the next day! Doing this you avoid self-joining and can enhance performance both in terms of speed and resource utilization. I have dissected my final solution into 5 sections and 1 non-recursive CTE and I will explain the idea and usage for each section below.

Section A:

To have anything to work with, you must get something out from dbo.DailyVisits source table; the dates and the visitors. This is no secret and an absolute must.

Section B

Here is the first optimization trick because here is where you calculate the next day value, rather than seeking it out by self-joining. This also enables the solution to be a “one-pass only” solution which I prefer. The DayDelta is a number to add to the real date value; 0 means same day and 1 means next day according to how DATEADD work. The next optimization trick is to work with the visit count and here I used a value of 1 for the real days and 0 for the calculated virtual next date.
By doing this I can easily just SUM this column to get the correct count for NumVisits result. I use the same technique for the Added and Removed column; use +1 and -1 to sum in a later stage. The third optimization trick is to not calculate Remained at this point. I will get back to Remained in Section D.

Section C:

Here is the major performance gain. Since the clustered index on the dbo.DailyVisits table is on dt column, I can use this to get a nice SEEK operation from the table. And the primary WHERE clause needs to deal with the calculated date values so I want the rows from the day before the earliest day, to the last day. This is because I want the calculated next day to be included in the beginning of the interval.

Common Table Expression cteSource:

Is this section, I simply sum up all NumVisits, Added and Removed values by dt. The trick here is to group by the visitor too, to avoid the costly distinct aggregate operation. For this resultset from cteSource I will later apply another group by and then only over dt column. More about that in Section D. Here I also apply the secondary WHERE clause to remove the real row containing the date before the earliest date and the calculated next date which occurs after the latest date.

Section D:

To avoid the distinct aggregate I apply two group by’s; first over both dt and visitor columns and the second over dt column only. This is the first trick in this section and proved to be very efficient and removes the need for a sort operation in the execution plan. The second trick is to wait to calculate the Remained column until now. If you understand that if there was no difference in Added and Removed value for the visitor at any given day, the visitor must have kept/remained his presence.

Section E:

The first trick is to have this section to deal with missing dates in the source table. Here I use a very efficient function written by Mr. Ben-Gan to get the full interval. The second trick is to use 0 as value for all columns, because if the row for that date is missing, there cannot be any movement either in terms of Added, Removed or Remained.

Final query:

Now the solution is very simple. Just add Section D and Section E and sum the column values.
The query is very fast. I tested on a sample table with about 120,000 random rows and my solution used about 2 ms CPU vs 4400 ms CPU for the JOIN solution; it also used only 10 reads vs. about 800,000 reads for the JOIN solution.

Cheers,

BG