Clarifications Regarding TSQL Challenge: Packing Date and Time Intervals

A couple of weeks ago I posted a challenge involving packing date and time intervals. The challenge is still open. I got several questions regarding the challenge and replied to those in my blog; but in case you haven’t followed the comments, perhaps I should clarify things here to avoid any further confusion. I also wanted to provide a status update with the run times of the solutions I got so far.

A couple of requests first…

I got many solutions so far, and it’s very hard to follow people’s logic without any accompanying narrative that explains the solution. So I’d greatly appreciate it if when you send your solution you:

1. Send it to me directly via e-mail (itzik@solidq.com) in a .sql file so that the formatting of the code won’t be messed up like when posting it as a comment in the blog.

2. Please add some narrative with a description of the solution’s logic. This applies also in case you already sent your solution without describing it. Think that your description needs to be sufficient to copy-paste it to explain it to others that see it for the first time.

3. Your solution must run against the sample data provided and must produce the desired results in order to be considered.

Clarifications…

Q: When are the solutions to the puzzle going to be published?

A: First day of spring.

Q: You say that the solution needs to be set-based; what does this mean? Does it need to be a single query solution?

A: No, it doesn't need to be a single query solution. In set-based I mean:

·         Not to use iterative constructs like cursors or loops where you interact with one row at a time, as opposed to interacting with the set as a whole.
·         Not to rely on consuming data in specific physical order for the solution to work correctly.

But of course, if you have an iterative solution that is very fast, please feel free to share.

Q: You say that the solution needs to be standard; what do you mean by that?

A: By standard I mean constructs defined by ISO and ANSI SQL. The idea is for the solution to be cross platform. Such that you can copy-paste it to run it on Oracle/DB2/etc. (or with very minor revisions).

To check for portability, in case you have access to both a SQL Server and Oracle system, try running your solution on both. You can use the following code to create the sample data on an Oracle system:

CREATE TABLE dbo.Sessions
(
  id        INT          NOT NULL,
  username  VARCHAR2(14) NOT NULL,
  starttime TIMESTAMP    NOT NULL,
  endtime   TIMESTAMP    NOT NULL,
  CONSTRAINT PK_Sessions PRIMARY KEY(id),
  CONSTRAINT CHK_endtime_gteq_starttime
    CHECK (endtime >= starttime)
);

INSERT INTO dbo.Sessions VALUES(1, 'User1', TO_DATE('20111201 08:00:00',  'YYYYMMDD HH24:MI:SS'), TO_DATE('20111201 08:30:00',  'YYYYMMDD HH24:MI:SS'));
INSERT INTO dbo.Sessions VALUES(2, 'User1', TO_DATE('20111201 08:30:00',  'YYYYMMDD HH24:MI:SS'), TO_DATE('20111201 09:00:00',  'YYYYMMDD HH24:MI:SS'));
INSERT INTO dbo.Sessions VALUES(3, 'User1', TO_DATE('20111201 09:00:00',  'YYYYMMDD HH24:MI:SS'), TO_DATE('20111201 09:30:00',  'YYYYMMDD HH24:MI:SS'));
INSERT INTO dbo.Sessions VALUES(4, 'User1', TO_DATE('20111201 10:00:00',  'YYYYMMDD HH24:MI:SS'), TO_DATE('20111201 11:00:00',  'YYYYMMDD HH24:MI:SS'));
INSERT INTO dbo.Sessions VALUES(5, 'User1', TO_DATE('20111201 10:30:00',  'YYYYMMDD HH24:MI:SS'), TO_DATE('20111201 12:00:00',  'YYYYMMDD HH24:MI:SS'));
INSERT INTO dbo.Sessions VALUES(6, 'User1', TO_DATE('20111201 11:30:00',  'YYYYMMDD HH24:MI:SS'), TO_DATE('20111201 12:30:00',  'YYYYMMDD HH24:MI:SS'));
INSERT INTO dbo.Sessions VALUES(7, 'User2', TO_DATE('20111201 08:00:00',  'YYYYMMDD HH24:MI:SS'), TO_DATE('20111201 10:30:00',  'YYYYMMDD HH24:MI:SS'));
INSERT INTO dbo.Sessions VALUES(8, 'User2', TO_DATE('20111201 08:30:00',  'YYYYMMDD HH24:MI:SS'), TO_DATE('20111201 10:00:00',  'YYYYMMDD HH24:MI:SS'));
INSERT INTO dbo.Sessions VALUES(9, 'User2', TO_DATE('20111201 09:00:00',  'YYYYMMDD HH24:MI:SS'), TO_DATE('20111201 09:30:00',  'YYYYMMDD HH24:MI:SS'));
INSERT INTO dbo.Sessions VALUES(10, 'User2', TO_DATE('20111201 11:00:00',  'YYYYMMDD HH24:MI:SS'), TO_DATE('20111201 11:30:00',  'YYYYMMDD HH24:MI:SS'));
INSERT INTO dbo.Sessions VALUES(11, 'User2', TO_DATE('20111201 11:32:00',  'YYYYMMDD HH24:MI:SS'), TO_DATE('20111201 12:00:00',  'YYYYMMDD HH24:MI:SS'));
INSERT INTO dbo.Sessions VALUES(12, 'User2', TO_DATE('20111201 12:04:00',  'YYYYMMDD HH24:MI:SS'), TO_DATE('20111201 12:30:00',  'YYYYMMDD HH24:MI:SS'));
INSERT INTO dbo.Sessions VALUES(13, 'User3', TO_DATE('20111201 08:00:00',  'YYYYMMDD HH24:MI:SS'), TO_DATE('20111201 09:00:00',  'YYYYMMDD HH24:MI:SS'));
INSERT INTO dbo.Sessions VALUES(14, 'User3', TO_DATE('20111201 08:00:00',  'YYYYMMDD HH24:MI:SS'), TO_DATE('20111201 08:30:00',  'YYYYMMDD HH24:MI:SS'));
INSERT INTO dbo.Sessions VALUES(15, 'User3', TO_DATE('20111201 08:30:00',  'YYYYMMDD HH24:MI:SS'), TO_DATE('20111201 09:00:00',  'YYYYMMDD HH24:MI:SS'));
INSERT INTO dbo.Sessions VALUES(16, 'User3', TO_DATE('20111201 09:30:00',  'YYYYMMDD HH24:MI:SS'), TO_DATE('20111201 09:30:00',  'YYYYMMDD HH24:MI:SS'));

 

The solution has to run on SQL Server, though, so constructs that are not available in SQL Server are a problem. Though as usual, if you have an interesting solution that relies on such constructs, feel free to share it.

Status Update…

As mentioned, I’m going to publish the solutions on the first day of spring. In the meanwhile, I’ll provide the run times of the solutions that from first examination appear to be valid. I ran all solutions against an Alienware M15x laptop with a Core i7 processor (quad core with hyper threading, namely, 8 logical CPUs), 4 GB RAM 1333 MHz. The run times I’ll provide are when the solutions were executed with hot cache. Here are the run times in seconds from fastest to slowest:

Itzik 2: 3
Muhammad Al Pasha: 14
Itzik 1: 17
Peter Larsson (Peso): 23
Stefan: 40
Alejandro Mesa: 130
Ami Levin: 225
Geri Reshef: 1,690
Classic: 5,621

Note that I did not report run times for solutions that did not produce correct results or that were not written to work against the tables I provided in the challenge.
 

Keep ‘em coming…

BG

 

 

Discuss this Blog Entry 6

on Feb 1, 2011
Here's the code to fill a Users table in case you need one:

-- assumes there is a table of users (reasonable assumption)
IF OBJECT_ID('dbo.Users') IS NOT NULL DROP TABLE dbo.Users;

CREATE TABLE dbo.Users
(
username VARCHAR(14) NOT NULL,
CONSTRAINT PK_Users PRIMARY KEY(username)
);

DECLARE @num_users AS INT = 1000;

INSERT INTO dbo.Users(username)
SELECT 'User' + RIGHT('000000000' + CAST(U.n AS VARCHAR(10)), 10) AS username
FROM dbo.GetNums(@num_users) AS U;
















on Jan 28, 2011
One more question: Is the time to create indexes included in your published times ?
on Feb 8, 2011
Wow! A 14 second solution.
Maybe it's time to reveal "Itzik 1"? :-)




on Jan 29, 2011
I've got another question for clarification:
Q. Can the APPLY operator be used?
A. In terms of being standard, APPLY itself isn't standar;, however, the standard does support a very similar constract called LATERAL correlation. So using APPLY-like solutions in platforms that support LATERAL would require only minor revisions. So in this respect APPLY can be considered fair game.
Also, It is safe to assume in such problems where there's a partitioning element (the user in our case), that there's a table available with the distinct partitioning values (a table of users in our case). A solution that uses APPLY against a table of users, therefore, is fair game. If you like to use such an approach, feel free to create a table of Users, fill it with the distinct username values, and assume it's available to begin with.


on Feb 21, 2011
Not much activity here...

on Jan 29, 2011
Stefan, no, time to create indexes is not included.

Please or Register to post comments.

What's Puzzled By T-SQL Blog?

T-SQL tips and logical puzzles from Itzik Ben-Gan.

Blog Archive

Sponsored Introduction Continue on to (or wait seconds) ×