5
\$\begingroup\$

The goal of this challenge is to implement a storage and retrieval pattern that will most quickly determine if a set of recurrence definitions fall within a date range.

Consider the schema: Event -|--has one or many--<- Schedules

Schedule is a record defining a recurrence, e.g. (these are just samples)

  • Monthly, every month
  • Monthly, first Wednesday of every month
  • Monthly, Monday and Tuesday of every 3rd month from start date
  • Monthly, Monday and Tuesday of every May, June and July
  • Weekly, every Tuesday through Saturday
  • Weekly, Monday every 3rd week from start date

The types of supported schedules should be (definitive list):

Pattern

  1. Daily
  2. Weekly, every [X] weeks on [set of 1-7 days]
  3. Monthly, every [Xth] day of every [Y] months
  4. Monthly, every [1st-4th-last] [weekday] of every [Y] months
  5. Yearly, on [month] [day of month] every [X] years
  6. Yearly, on [1st-4th-last] [weekday] of [month]
  7. Monthly, every [Xth] day of [set of months]
  8. Monthly, every [1st-4th-last] [weekday] of [set of months]

End date (Start is always a single date)

  1. No end date (for simplicity, you could omit this since we can use year 2999)
  2. A single date
  3. A number of [X] occurences

To win, the answer must define:

  1. Table schema
  2. SQL query or function (any RBDMS) to test a date range against the entire table

Determination of winner:

  1. test data: 10,000 events will be created randomly; 20 special test cases will be added as well
  2. test case: 100 random date ranges (min:1 max:32 days), 5 fixed date ranges (min:1 max:32 days)
  3. test execution: Test will be repeated 3 times
  4. proof of correctness: All answers must be correct 6: speed: Quickest execution wins

Example test case:

---------
Schedules
---------
Event A: Weekly, Every Monday starting 1 Jan 2015
Event A: Monthly, Every [31st] day of every [1] month starting 1 Jan 2015
  (e.g. Event A is a backup schedule)
Event B: Monthly, Every [1st] day of every [1] month starting 1 Jan 2015
Event C: Yearly, Every [10th] day of every [3] months starting 1 Jan 2015
  (e.g. quarterly summary report)
Event D: Weekly, Every [Tue,Wed,Fri] starting 1 Jan 2015
Event E: Weekly, Every [Tue,Wed,Fri] starting 1 Jan 2015 ending 3 July 2015
(assume no end dates unless stated)

-----
Query
-----
What events occur between 1 July 2015 and 31 July 2015 (inclusive)

---------------
Expected Result
---------------
(shown in date order)    
01 July: Event B
01 July: Event E
03 July: Event E  << last occurrence due to end date
06 July: Event A
10 July: Event C
13 July: Event A
20 July: Event A
27 July: Event A
31 July: Event A
(a lot of event D's every Tue/Wed/Fri in July)
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG stack exchange! This is an interesting challenge - we haven't had many database challenges recently. To be clear, is the challenge to return a boolean saying whether or not any of the events are in the date range, or is it to return all overlapping recurrences? \$\endgroup\$ – isaacg Jul 14 '15 at 21:05
  • \$\begingroup\$ The challenge is only to return a boolean, or in other words, the set of events with schedules that intersect the date range queried. \$\endgroup\$ – RichardTheKiwi Jul 14 '15 at 21:06
  • 3
    \$\begingroup\$ The two things you said in that answer are very different. Do you want a True or False result, or a set of events? Either way, please add the clarification to your answer. \$\endgroup\$ – isaacg Jul 14 '15 at 21:09
  • \$\begingroup\$ "E.g."? Please specify precisely what needs to be supported. \$\endgroup\$ – Peter Taylor Jul 14 '15 at 21:12
  • \$\begingroup\$ @MickyT Thank you for the suggestion, I have edited the question with test data and an example expected result \$\endgroup\$ – RichardTheKiwi Jul 14 '15 at 23:48
1
\$\begingroup\$

T-SQL

Given that the speed of the query is the most important part of the challenge, I have created a table that is an expansion of the events so that each event has all of it's occurrence dates stored. The query is then just a simple WHERE DATE BETWEEN query and will perform extremely quickly.

This of course is built towards the query speed and not for the maintenance of the data. Building and populating the table will take a fair amount of time depending on the amount of dates that the events cover.

The parsing of the records assume the the Days and Months are all abbreviated

View

A simple view to give a list of numbers up to 1e8

CREATE View [dbo].[Tally] as
WITH
    E1(N) AS (select 1 from (values (1),(1),(1),(1),(1),(1),(1),(1),(1),(1))dt(n)),
    E2(N) AS (SELECT 1 FROM E1 a, E1 b), --10E+2 or 100 rows
    E4(N) AS (SELECT 1 FROM E2 a, E2 b), --10E+4 or 10,000 rows max
    E8(N) AS (SELECT 1 FROM E4 a, E4 b), --10E+4 or 100,000,000 rows max
    cteTally(N) AS 
    (
        SELECT  ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM E4
    )
SELECT N FROM cteTally;
GO

Functions

A couple of inline table functions to parse and expand the Event input records.

CREATE FUNCTION ParseEvent (@InputString VARCHAR(1000)) RETURNS TABLE AS RETURN
    -- Parse rest of the components
    SELECT 
        EventName,
        ScheduleType,
        StartDate,
        EndDate,
        CASE WHEN ScheduleType = 'Weekly' THEN 
            SUBSTRING(Remainder,7,CHARINDEX(' weeks ',Remainder)-7)
        END WeeklyX,
        CASE WHEN ScheduleType = 'Weekly' THEN 
            SUBSTRING(Remainder,CHARINDEX(' on ',Remainder)+4,999)
        END WeeklyDays,
        CASE WHEN ScheduleType = 'Monthly' and Remainder like '% day of %' THEN 
            SUBSTRING(Remainder,7,CHARINDEX(' day ',Remainder)-7)
        END MonthlyDayOfMonth,
        CASE WHEN ScheduleType = 'Monthly' and Remainder like '% of every %' THEN 
            REPLACE(SUBSTRING(Remainder,CHARINDEX(' of every',Remainder)+10,999),' months','')
        END MonthlyX, -- Y
        CASE WHEN ScheduleType = 'Monthly' and Remainder not like '% of every %' THEN 
            SUBSTRING(Remainder,CHARINDEX(' of ',Remainder)+4,999)
        END MonthlyMonths,
        CASE WHEN ScheduleType = 'Yearly' THEN 
            CASE WHEN Remainder like '% every %' THEN 
                SUBSTRING(Remainder,4,CHARINDEX(' ',Remainder,4)-4) -- length 3 ?
            ELSE
                SUBSTRING(Remainder,CHARINDEX(' of ',Remainder)+4,999) -- Right(Remainder,3) ?
            END
        END YearlyMonth,
        CASE WHEN ScheduleType = 'Yearly' and Remainder like '% every %' THEN 
            SUBSTRING(Remainder,CHARINDEX(' ',Remainder,4)+1,CHARINDEX(' ',Remainder,CHARINDEX(' ',Remainder,4)+1)-CHARINDEX(' ',Remainder,4)-1) -- Can we assume 3 ??
        END YearlyDayOfMonth,
        CASE WHEN ScheduleType = 'Yearly' and Remainder like '% every %' THEN 
            REPLACE(SUBSTRING(Remainder,CHARINDEX(' every ',Remainder)+7,9999),' years','')
        END YearlyX,
        CASE WHEN (ScheduleType = 'Yearly' and Remainder like '% of %') OR 
            (ScheduleType = 'Monthly' and remainder not like '% day %') THEN 
            SUBSTRING(Remainder,CHARINDEX(' ',Remainder)+1,CHARINDEX(' of ',Remainder)-CHARINDEX(' ',Remainder)-1)
        END WeekDayOccurance
        FROM
        -- Get the start and end dates
        (SELECT 
            EventName,
            ScheduleType,
            CAST(SUBSTRING(Remainder, CHARINDEX('Starting',Remainder)+9, IIF(CHARINDEX('Ending',Remainder)=0,999,CHARINDEX('Ending',Remainder) - (CHARINDEX('Starting',Remainder) + 9))) AS DATE)  StartDate,
            CAST(IIF(CHARINDEX('Ending',Remainder)=0,'31 Dec 2999',SUBSTRING(Remainder, CHARINDEX('Ending',Remainder) + 7, 999)) AS DATE) EndDate,
            RTRIM(STUFF(Remainder,CHARINDEX('Starting',Remainder),999,'')) Remainder
        FROM
            -- Get the schedule type
            (SELECT EventName,
                LTRIM(LEFT(Remainder, CHARINDEX(',',Remainder)-1)) ScheduleType,
                LTRIM(STUFF(Remainder, 1, CHARINDEX(',',Remainder), '')) Remainder
            FROM 
                -- Get the event name
                ( SELECT 
                    LEFT(@InputString, CHARINDEX(':',@InputString)-1) EventName,
                    STUFF(@InputString, 1, CHARINDEX(':',REPLACE(@InputString,'Daily ','Daily, ')), '') Remainder
                ) EventName
            ) ScheduleType
        ) StartEndDate
;
GO

CREATE FUNCTION ExpandEvent (
        @EventName VARCHAR(100),
        @ScheduleType VARCHAR(20),
        @StartDate DATE,
        @EndDate DATE,
        @WeeklyX VARCHAR(10),
        @WeeklyDays VARCHAR(50),
        @MonthlyDayOfMonth VARCHAR(10),
        @MonthlyX VARCHAR(10),
        @MonthlyMonths VARCHAR(50),
        @YearlyMonth VARCHAR(50),
        @YearlyDayOfMonth VARCHAR(10),
        @YearlyX VARCHAR(10),
        @WeekDayOccurance VARCHAR(50)
    ) RETURNS TABLE RETURN
WITH AllDays AS (
    SELECT *
    FROM (
        SELECT 
            DENSE_RANK() OVER (ORDER BY DATEPART(year,D)) - 1 YearCount
            ,DENSE_RANK() OVER (ORDER BY DATEPART(year,D), DATEPART(month,D)) - 1 MonthCount
            ,DENSE_RANK() OVER (ORDER BY DATEPART(year,D), DATEPART(week,D)) - 1 WeekCount
            ,CASE DATEPART(month,D)
                WHEN 1 THEN 'Jan'
                WHEN 2 THEN 'Feb'
                WHEN 3 THEN 'Mar'
                WHEN 4 THEN 'Apr'
                WHEN 5 THEN 'May'
                WHEN 6 THEN 'Jun'
                WHEN 7 THEN 'Jul'
                WHEN 8 THEN 'Aug'
                WHEN 9 THEN 'Sep'
                WHEN 10 THEN 'Oct'
                WHEN 11 THEN 'Nov'
                WHEN 12 THEN 'Dec'
            END MonthAbrev
            ,DATEPART(day,D) MonthDay
            ,CASE DATEPART(weekday,D) 
                WHEN 1 THEN 'Sun'
                WHEN 2 THEN 'Mon'
                WHEN 3 THEN 'Tue'
                WHEN 4 THEN 'Wed'
                WHEN 5 THEN 'Thu'
                WHEN 6 THEN 'Fri'
                ELSE 'Sat'
            END DayOfWeek
            ,DENSE_RANK() OVER (PARTITION BY DATEPART(year,D),DATEPART(month,D),DATEPART(weekday,D) ORDER BY D) DayWeekMonthOccurance
            ,COUNT(*) OVER (PARTITION BY DATEPART(year,D),DATEPART(month,D),DATEPART(weekday,D)) DayWeekMonthMax
            ,D
        FROM (
            SELECT DATEADD(day,t.N,@StartDate) D
            FROM (SELECT TOP(DATEDIFF(day,@StartDate,@EndDate) + 1) N - 1 N FROM Tally) T
            ) Days
        ) AllDays
    )
SELECT @EventName E, D FROM AllDays
WHERE (@ScheduleType = 'Daily') 
    OR (WeekCount % @WeeklyX = 0 and @weeklyDays like '%'+DayofWeek+'%' and @ScheduleType = 'Weekly') 
    OR (MonthDay = SUBSTRING(@MonthlyDayOfMonth,1,LEN(@MonthlyDayOfMonth)-2) and MonthCount % @MonthlyX = 0 and @ScheduleType = 'Monthly' and @MonthlyDayOfMonth IS NOT NULL and @MonthlyX IS NOT NULL) 
    OR (MonthDay = SUBSTRING(@MonthlyDayOfMonth,1,LEN(@MonthlyDayOfMonth)-2) and @MonthlyMonths like '%'+MonthAbrev+'%' and @ScheduleType = 'Monthly' and @MonthlyDayOfMonth IS NOT NULL and @MonthlyMonths IS NOT NULL
    OR (DayWeekMonthOccurance = CASE WHEN @WeekDayOccurance like 'last %' THEN DayWeekMonthMax ELSE LEFT(@WeekDayOccurance,1) END and DayOfWeek = RIGHT(@WeekDayOccurance,3) and MonthCount % @MonthlyX = 0 and @ScheduleType = 'Monthly' and @WeekDayOccurance IS NOT NULL and @MonthlyX IS NOT NULL) 
    OR (DayWeekMonthOccurance = CASE WHEN @WeekDayOccurance like 'last %' THEN DayWeekMonthMax ELSE LEFT(@WeekDayOccurance,1) END and DayOfWeek = RIGHT(@WeekDayOccurance,3) and @MonthlyMonths like '%'+MonthAbrev+'%' and @ScheduleType = 'Monthly' and @WeekDayOccurance IS NOT NULL and @MonthlyMonths IS NOT NULL) 
    OR (@YearlyMonth like '%'+MonthAbrev+'%' and MonthDay = @YearlyDayOfMonth and YearCount % @YearlyX = 0 and @ScheduleType = 'Yearly' and @YearlyMonth IS NOT NULL and @YearlyDayOfMonth IS NOT NULL and @YearlyX IS NOT NULL) 
    OR (DayWeekMonthOccurance = CASE WHEN @WeekDayOccurance like 'last %' THEN DayWeekMonthMax ELSE LEFT(@WeekDayOccurance,1) END and DayOfWeek = RIGHT(@WeekDayOccurance,3) and @YearlyMonth like '%'+MonthAbrev+'%' and @ScheduleType = 'Yearly' and @WeekDayOccurance IS NOT NULL and @YearlyMonth IS NOT NULL)
;
GO

Table

The search table for the event dates

CREATE TABLE SearchEvents (
    ID BIGINT IDENTITY (1,1) NOT NULL PRIMARY KEY,
    EventName VARCHAR(100) NOT NULL,
    EventDate DATE NOT NULL
    );

Table Population

An example of populating the SearchEvents table. This example shows each of the Event patterns that are acceptable and will likely error if that format is deviated from. Note the Months and Days are abbreviated. The ending date is not required and will default to 31 Dec 2999. But I would suggest that it is set.

INSERT INTO SearchEvents
SELECT Ex.E, Ex.D
FROM (VALUES
    ('Event A: Daily, Starting 3 Jun 2010 Ending 5 Dec 2020')
    ,('Event B: Weekly,  every 2 weeks on Mon,Tue Starting 3 Jun 2010 Ending 5 Dec 2020')
    ,('Event C: Monthly, every 2nd day of every 2 months Starting 3 Jun 2010 Ending 5 Dec 2020')
    ,('Event D: Monthly, every 3rd day of Jun,Jul,Dec,Jan Starting 3 Jun 2010 Ending 5 Dec 2020')
    ,('Event E: Monthly, every 2nd Tue of every 3 months Starting 3 Jun 2010 Ending 5 Dec 2020')
    ,('Event F: Monthly, every last Wed of Jun,Nov Starting 3 Jun 2010 Ending 5 Dec 2020')
    ,('Event B: Yearly, on Jun 10 every 1 years Starting 3 Jun 2010 Ending 5 Dec 2020')
    ,('Event H: Yearly, on 3rd Wed of Jun Starting 3 Jun 2010 Ending 5 Dec 2020')
)A(S) CROSS APPLY (SELECT * FROM parseEvent(S)) P
    CROSS APPLY (SELECT * FROM ExpandEvent(
        EventName,
        ScheduleType,
        StartDate,
        EndDate,
        WeeklyX,
        WeeklyDays,
        MonthlyDayOfMonth,
        MonthlyX,
        MonthlyMonths,
        YearlyMonth,
        YearlyDayOfMonth,
        YearlyX,
        WeekDayOccurance    
    )) Ex

Indexing

The important part, indexing of the date field

CREATE INDEX SE_EventDate_IDX ON SearchEvents(EventDate) INCLUDE (EventName);
GO

Query

An example query

SELECT EventName, EventDate
FROM SearchEvents
WHERE EventDate BETWEEN CAST('1 Jan 2015' AS DATE) AND CAST('31 Dec 2015' AS DATE)
ORDER BY EventDate

This executed with the following stats on my machine. 1 years worth of events from ten years of data.

SQL Server parse and compile time: 
   CPU time = 0 ms, elapsed time = 1 ms.

(435 row(s) affected)
Table 'SearchEvents'. Scan count 1, logical reads 5, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

 SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 98 ms.
SQL Server parse and compile time: 
   CPU time = 0 ms, elapsed time = 0 ms.

 SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 0 ms.
\$\endgroup\$
  • \$\begingroup\$ It turns out it is pretty efficient with almost negligible cost to calculate at query time the events that will occur in a date range. Scales linearly against both number of days as well as number of schedules defined. Compared with the cost of calculating and storing 36500 records per "daily" event projected for 100 years, it's a clear winner. I'll give it a few days before sharing it. \$\endgroup\$ – RichardTheKiwi Jul 23 '15 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.