Depending on platform, this may or may not be possible in a single sql query/without use of a stored procedure.
This problem is effectively equivalent to tree traversal within a table with parent references. You can construct the tree structure through a self join using a query like this:
SELECT
b. *,
a.event as parent_event,
a.start as parent_start,
a.end as parent_end
FROM
interval_test a
join
interval_test b ON b.start >= a.end
order by parent_start, start
Producing a result that looks like this:
Note: the result is truncated to save space, but you get the idea...
Each of the possible successors of an event (those with an end >= start of the predecessor) can be thought of as a child in the tree. You want to find the tree path down the tree that minimizes the start time at each step.
You can do this kind of tree traversal by using recursive queries within SQL Server or using a hierarchical query in Oracle. This kind of recursion is not supported in MySQL and you will need to use a stored procedure if that is your platform.
For example, in SQL Server, the following query would work:
WITH min_path AS
(SELECT RANK() OVER (ORDER BY a.start ASC) AS [rank], cast(NULL as CHAR(10)) as parent_event,
NULL as parent_start, NULL as parent_end, a.event, a.start, a.[end]
FROM dbo.interval_test a
WHERE a.start=
(SELECT MIN(START)
FROM dbo.interval_test)
UNION ALL SELECT RANK() OVER (ORDER BY c.start ASC) AS [rank], b.event as parent_event,
b.start as parent_start, b.[end] as parent_end, c.event, c.start, c.[end]
FROM min_path b
JOIN dbo.interval_test c ON c.start>= b.[end]
WHERE [rank]=1)
SELECT event, start, [end] from min_path where [rank]=1
Producing the following result:
Note, there are probably cleaner ways to write the query above for SQL Server.
From a performance perspective, when you are working in an environment with potentially billions of rows as mentioned in the comments above, I don't have a clear idea of how this might perform. If the query is limited to a small number of events related to a single user it might be fine. Trying to find the whole set of relevant non-overlapping events would probably not work well and you might be better off using a procedural approach.
Best Answer
SQL CLR integration was developed mainly because, implementing logic through T-SQL was really hard. .NET Framework if filled with thousands of useful libraries, to which you have no access at SQL engine level. Thus, any logic should be implemented from scratch. For example, a simple
foreach
loop should be implemented with cursors, which are honestly, far less productive.I have experience of working with SQL CRL integration. I did it for date-time conversion at database engine level. Date-time conversion at the level of database engine is really really hard, while .NET, has
System.Globalization
which facilitates the work.The main point of this method, is to follow the step exactly as described (like extension methods in which, methods should be static functions inside static classes inside first-level namespace). If you fail to do something exactly as you're told, things simply fail.