Results 1 to 10 of 10
  1. #1
    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. #2
    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. #3
    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. #4
    Join Date
    Apr 2007
    Posts
    183
    I am thinking of a recursive CTE that will cut the time ranges into smaller slices.

  5. #5
    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. #6
    Join Date
    Apr 2007
    Posts
    183
    Bumping input from OP...

  7. #7
    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 13:19.

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

  9. #9
    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. #10
    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
  •