# Thread: Calculate max intersects between two fields in resultset?

1. Registered User
Join Date
Jan 2009
Posts
4

## Unanswered: Calculate max intersects between two fields in resultset?

Hi,

I'm trying to figure out the best way to calculate the maximum number of intersections between two columns in a resultset. The problem is taken from a connection table where CreateDate and DeleteDate of each connection is stored and I would like to know what the maximum number of concurrent connections was.

Ex:
Code:
CreateDate              DeleteDate
2009-01-14 22:33:41.857	2009-01-14 22:35:59.543
2009-01-14 22:34:26.513	2009-01-14 22:35:43.233
2009-01-14 22:35:14.920	2009-01-14 22:35:31.530
2009-01-14 22:35:50.373	2009-01-14 22:36:07.340
2009-01-14 22:37:26.793	2009-01-14 22:37:44.857
2009-01-14 22:39:22.077	2009-01-14 22:39:38.543
2009-01-14 22:38:03.873	2009-01-14 22:38:20.827
2009-01-14 22:39:39.247	2009-01-14 22:39:55.840
2009-01-14 22:41:25.857	2009-01-14 22:41:42.467
2009-01-14 22:43:14.607	2009-01-14 22:44:31.483
2009-01-14 22:52:10.233	2009-01-14 22:52:26.827
2009-01-14 22:53:08.187	2009-01-14 22:53:24.983
2009-01-14 22:53:36.483	2009-01-14 22:53:53.060
2009-01-14 22:56:56.403	2009-01-14 22:57:13.263
2009-01-14 22:57:28.247	2009-01-14 22:57:44.780
2009-01-14 22:58:16.090	2009-01-14 22:58:32.623
2009-01-14 22:58:52.137	2009-01-14 22:59:08.670
2009-01-14 22:59:21.170	2009-01-14 22:59:37.733
Should result in 3.

One solution is to timeslice from earliest CreateDate to latest DeleteDate and check how many connections that are active each minute and save the greatest value. This doesn't always give a correct value though, to get that you have to use a resolution of seconds and with a large timespan that could be costly. Is there other solutions that I have missed? Any code help is appreciated.

Kind Regards
Andreas

2. Registered User
Join Date
Apr 2007
Posts
183
Code:
-- Prepare sample data
DECLARE	@Sample TABLE
(
CreateDate DATETIME,
DeleteDate DATETIME
)

INSERT	@Sample
SELECT	'2009-01-14 22:33:41.857', '2009-01-14 22:35:59.543' UNION ALL
SELECT	'2009-01-14 22:34:26.513', '2009-01-14 22:35:43.233' UNION ALL
SELECT	'2009-01-14 22:35:14.920', '2009-01-14 22:35:31.530' UNION ALL
SELECT	'2009-01-14 22:35:50.373', '2009-01-14 22:36:07.340' UNION ALL
SELECT	'2009-01-14 22:37:26.793', '2009-01-14 22:37:44.857' UNION ALL
SELECT	'2009-01-14 22:39:22.077', '2009-01-14 22:39:38.543' UNION ALL
SELECT	'2009-01-14 22:38:03.873', '2009-01-14 22:38:20.827' UNION ALL
SELECT	'2009-01-14 22:39:39.247', '2009-01-14 22:39:55.840' UNION ALL
SELECT	'2009-01-14 22:41:25.857', '2009-01-14 22:41:42.467' UNION ALL
SELECT	'2009-01-14 22:43:14.607', '2009-01-14 22:44:31.483' UNION ALL
SELECT	'2009-01-14 22:52:10.233', '2009-01-14 22:52:26.827' UNION ALL
SELECT	'2009-01-14 22:53:08.187', '2009-01-14 22:53:24.983' UNION ALL
SELECT	'2009-01-14 22:53:36.483', '2009-01-14 22:53:53.060' UNION ALL
SELECT	'2009-01-14 22:56:56.403', '2009-01-14 22:57:13.263' UNION ALL
SELECT	'2009-01-14 22:57:28.247', '2009-01-14 22:57:44.780' UNION ALL
SELECT	'2009-01-14 22:58:16.090', '2009-01-14 22:58:32.623' UNION ALL
SELECT	'2009-01-14 22:58:52.137', '2009-01-14 22:59:08.670' UNION ALL
SELECT	'2009-01-14 22:59:21.170', '2009-01-14 22:59:37.733'

-- All concurrencies
SELECT		s.CreateDate,
s.DeleteDate,
SUM(f.q) AS Concurrency
FROM		@Sample AS s
CROSS APPLY	(
SELECT	1
FROM	@Sample AS w
WHERE	w.CreateDate <= s.DeleteDate
AND w.DeleteDate >= s.CreateDate
AND w.CreateDate <> s.CreateDate
AND w.DeleteDate <> s.DeleteDate
) AS f(q)
GROUP BY	s.CreateDate,
s.DeleteDate
ORDER BY	SUM(f.q) DESC,
s.CreateDate DESC

-- Highest concurrency
SELECT TOP 1	WITH TIES
s.CreateDate,
s.DeleteDate,
SUM(f.q) AS Concurrency
FROM		@Sample AS s
CROSS APPLY	(
SELECT	1
FROM	@Sample AS w
WHERE	w.CreateDate <= s.DeleteDate
AND w.DeleteDate >= s.CreateDate
AND w.CreateDate <> s.CreateDate
AND w.DeleteDate <> s.DeleteDate
) AS f(q)
GROUP BY	s.CreateDate,
s.DeleteDate
ORDER BY	SUM(f.q) DESC

3. Registered User
Join Date
Jan 2009
Posts
4
Thanks Peso for the reply. I thought of that algorithm as well but considered it faulty.

For example:

Code:
INSERT	@Sample
SELECT	'2009-01-14 22:33:41.857', '2009-01-14 22:35:59.543' UNION ALL
SELECT	'2009-01-14 22:33:42.857', '2009-01-14 22:33:59.543' UNION ALL
SELECT	'2009-01-14 22:34:26.513', '2009-01-14 22:35:43.233' UNION ALL
SELECT	'2009-01-14 22:35:14.920', '2009-01-14 22:35:31.530' UNION ALL
SELECT	'2009-01-14 22:35:50.373', '2009-01-14 22:36:07.340' UNION ALL
SELECT	'2009-01-14 22:37:26.793', '2009-01-14 22:37:44.857' UNION ALL
SELECT	'2009-01-14 22:39:22.077', '2009-01-14 22:39:38.543' UNION ALL
SELECT	'2009-01-14 22:38:03.873', '2009-01-14 22:38:20.827' UNION ALL
SELECT	'2009-01-14 22:39:39.247', '2009-01-14 22:39:55.840' UNION ALL
SELECT	'2009-01-14 22:41:25.857', '2009-01-14 22:41:42.467' UNION ALL
SELECT	'2009-01-14 22:43:14.607', '2009-01-14 22:44:31.483' UNION ALL
SELECT	'2009-01-14 22:52:10.233', '2009-01-14 22:52:26.827' UNION ALL
SELECT	'2009-01-14 22:53:08.187', '2009-01-14 22:53:24.983' UNION ALL
SELECT	'2009-01-14 22:53:36.483', '2009-01-14 22:53:53.060' UNION ALL
SELECT	'2009-01-14 22:56:56.403', '2009-01-14 22:57:13.263' UNION ALL
SELECT	'2009-01-14 22:57:28.247', '2009-01-14 22:57:44.780' UNION ALL
SELECT	'2009-01-14 22:58:16.090', '2009-01-14 22:58:32.623' UNION ALL
SELECT	'2009-01-14 22:58:52.137', '2009-01-14 22:59:08.670' UNION ALL
SELECT	'2009-01-14 22:59:21.170', '2009-01-14 22:59:37.733'
Results in 4 but the correct answer is still 3.

4. Registered User
Join Date
Apr 2007
Posts
183
I am thinking of a recursive CTE that will cut the time ranges into smaller slices.

5. Registered User
Join Date
Apr 2007
Posts
183
No need for CTE either.
It seems the problem is quite easy and automatically uses any present time resolution.
If ony day is present, days are counted. If milliseconds are present, milliseconds are used.

Code:
-- Prepare sample data
DECLARE	@Data TABLE
(
RecID INT IDENTITY(1, 1) PRIMARY KEY CLUSTERED,
CreateDate DATETIME,
DeleteDate DATETIME
)

-- Populate sample data
INSERT	@Data
(
CreateDate,
DeleteDate
)
SELECT	'2009-01-14 22:33:41.857', '2009-01-14 22:35:59.543' UNION ALL
SELECT	'2009-01-14 22:33:42.857', '2009-01-14 22:33:59.543' UNION ALL
SELECT	'2009-01-14 22:34:26.513', '2009-01-14 22:35:43.233' UNION ALL
SELECT	'2009-01-14 22:35:14.920', '2009-01-14 22:35:31.530' UNION ALL
SELECT	'2009-01-14 22:35:50.373', '2009-01-14 22:36:07.340' UNION ALL
SELECT	'2009-01-14 22:37:26.793', '2009-01-14 22:37:44.857' UNION ALL
SELECT	'2009-01-14 22:39:22.077', '2009-01-14 22:39:38.543' UNION ALL
SELECT	'2009-01-14 22:38:03.873', '2009-01-14 22:38:20.827' UNION ALL
SELECT	'2009-01-14 22:39:39.247', '2009-01-14 22:39:55.840' UNION ALL
SELECT	'2009-01-14 22:41:25.857', '2009-01-14 22:41:42.467' UNION ALL
SELECT	'2009-01-14 22:43:14.607', '2009-01-14 22:44:31.483' UNION ALL
SELECT	'2009-01-14 22:52:10.233', '2009-01-14 22:52:26.827' UNION ALL
SELECT	'2009-01-14 22:53:08.187', '2009-01-14 22:53:24.983' UNION ALL
SELECT	'2009-01-14 22:53:36.483', '2009-01-14 22:53:53.060' UNION ALL
SELECT	'2009-01-14 22:56:56.403', '2009-01-14 22:57:13.263' UNION ALL
SELECT	'2009-01-14 22:57:28.247', '2009-01-14 22:57:44.780' UNION ALL
SELECT	'2009-01-14 22:58:16.090', '2009-01-14 22:58:32.623' UNION ALL
SELECT	'2009-01-14 22:58:52.137', '2009-01-14 22:59:08.670' UNION ALL
SELECT	'2009-01-14 22:59:21.170', '2009-01-14 22:59:37.733'

-- Prepare staging table
DECLARE	@Stage TABLE
(
RecID INT IDENTITY(1, 1) PRIMARY KEY CLUSTERED,
FromTime DATETIME NOT NULL,
ToTime DATETIME NOT NULL
)

-- Populate staging table
INSERT		@Stage
(
FromTime,
ToTime
)
SELECT		u.theTime,
u.theTime
FROM		@Data AS d
UNPIVOT		(
theTime
FOR theCol IN (d.CreateDate, d.DeleteDate)
) AS u
GROUP BY	u.theTime
ORDER BY	u.theTime

-- Update with closest range
UPDATE		s
SET		s.ToTime = w.FromTime
FROM		@Stage AS s
INNER JOIN	@Stage AS w ON w.RecID = s.RecID + 1

-- Delete last time
DELETE
FROM	@Stage
WHERE	RecID = SCOPE_IDENTITY()

-- Display the result
SELECT		s.FromTime,
s.ToTime,
COUNT(*) AS Occurencies
FROM		@Data AS d
INNER JOIN	@Stage AS s ON s.FromTime < d.DeleteDate
AND s.ToTime > d.CreateDate
GROUP BY	s.FromTime,
s.ToTime
HAVING		COUNT(*) > 1
ORDER BY	COUNT(*) DESC,
s.FromTime DESC

6. Registered User
Join Date
Apr 2007
Posts
183
Bumping input from OP...

7. Registered User
Join Date
Jan 2009
Posts
4
Thanks Peso, you are a real guru on SQL. I almost started my own implementation of another algorithm in Java when I saw that this thread had been updated. It works perfect in Management Studio, but I would like to send it in as a sql query and at the moment I don't get a result back (Subsets of the query works though). Do you know what could cause such a behaviour?

Kind Regards
Andreas
Last edited by Andreas Johansson; 02-03-09 at 12:19.

8. Registered User
Join Date
Apr 2007
Posts
183
I have to see the full code.
Du kan skicka den till min mailadress

9. Registered User
Join Date
Jan 2009
Posts
4
It seems the problem is in Java and the JDBC driver. I can send multiple statements in one query using Visual Studio but not with Java. My options right now are:

1. See if it's possible to configure the JDBC driver to support multiple statements.
2. Create a stored procedure that does what I want (With the SQL above).

The SQL works like a charm - now I just have to determine the best way to implement it.

Thanks Peso
Tack för hjälpen

Kind Regards
Andreas

10. Registered User
Join Date
Apr 2007
Posts
183
You can write the whole code as a stored procedure.
If you need to pass some parameters, include them in procedure header.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•