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.