Top 2 rows per partition from an absolute value date difference

Question

I have a database of security camera footage in a denormalized database. I have Locations which have multiple Cameras which take multiple images.

Location + Camera + image capture_date is the clustered primary key, and currently the only index on the table. The kicker is searching a single camera takes <1 millisecond from SSMS and ~70ms from my web application. My current working CTE solutions take around 3 minutes for three cameras.

To give an overview of the cameras at a location I need to select 2 images from each camera nearest a given date (such as the current date). Because of this I need an absolute value (dates before or after the search date are equally valid), thus I'm searching by the smallest ABS(@date -capture_date).

Here's the current code. It works but it's not SARGable and it's extremely slow. I also only need the top 2 rows per camera in the CTE, since there may be hundreds of thousands of images per partition.

DECLARE @date datetime,
        @location varchar(4)
SET     @date ='2011-12-13 12:00:00'
SET     @location='CS01';
WITH CTE AS (
    SELECT
        *,
        ROW_NUMBER() OVER (PARTITION  BY Camera ORDER BY  abs(datediff(second,@date, [capture_date]))) AS Ranking
    FROM rs_camera_pictures
    WHERE 
        location=@location)
SELECT * FROM CTE WHERE Ranking <= 2

Answer 1

This is just a starting point and will likely need some tweaking.

Essentially this will get you the 4 closest capture dates to your specified date (2 closest after and 2 closest before).

You will need to add some logic to your outer select to pick which ones to use, but you will be doing a DATEDIFF on 4 fields instead of all of them.

WITH CTE AS
(
SELECT camera, MIN(r1.capture_date) as 'After', MAX(r2.capture_date) as 'Before'
FROM rs_camera_pictures r1
INNER JOIN rs_camera_pictures r2
    ON r1.location = r2.location
    AND r1.camera = r2.camera
WHERE r1.capture_date > @date
AND r2.capture_date < @date
GROUP BY camera
UNION ALL
SELECT camera, MIN(r1.capture_date) as 'After', MAX(r2.capture_date) as 'Before'
FROM rs_camera_pictures r1
INNER JOIN rs_camera_pictures r2
    ON r1.location = r2.location
    AND r1.camera = r2.camera
INNER JOIN CTE c
    ON r1.location = c.location
    AND r1.camera = c.camera
WHERE r1.capture_date > c.[After]
AND r2.capture_date < c.Before
GROUP BY camera
)

Answer 2

This should return four rows per camera in the selected location and then rank them to eturn the best two for each camera.

LocationCamera is the distinct list of the cameras for a location.

DECLARE @date datetime,
        @location varchar(4)
SET     @date ='2011-12-13 12:00:00'
SET     @location='CS01';

SELECT      Location,Camera,Capture_Date,Ranking
FROM        (
                SELECT      Location,Camera,Capture_Date,
                            ROW_NUMBER() OVER (PARTITION  BY Camera ORDER BY  abs(datediff(second,@date, [capture_date]))) AS Ranking
                FROM        (
                                SELECT      L.Location,
                                            L.Camera,
                                            CP.capture_date
                                FROM        LocationCamera  L
                                CROSS APPLY (
                                                SELECT      TOP (2)
                                                            CP.[capture_date]
                                                FROM        rs_camera_pictures  CP
                                                WHERE       L.Location          = CP.Location
                                                AND         L.Camera            = CP.Camera
                                                AND         CP.capture_date     >= @date
                                                ORDER BY    [capture_date]
                                            )   TopN
                                WHERE       L.Location      = @Location
                                UNION ALL
                                SELECT      L.Location,
                                            L.Camera,
                                            CP.[capture_date]
                                FROM        LocationCamera  L
                                CROSS APPLY (
                                                SELECT      TOP (2)
                                                            CP.[capture_date]
                                                FROM        rs_camera_pictures  CP
                                                WHERE       L.Location          = CP.Location
                                                AND         L.Camera            = CP.Camera
                                                AND         CP.capture_date     < @date
                                                ORDER BY    [capture_date]      DESC
                                            )   BottomN
                                WHERE       L.Location      = @location
                            )   D
            )   R
WHERE       Ranking <= 2

Answer 3

To the best of my knowledge (plus some Google searching and hacking to see if there was a way I didn't yet know) there is no solution that will avoid the non-SARGable ABS(DATEDIFF and outperform what you have now.

Thus, if you must implement a non-SARGable search, the most important thing to do is find SARGable ways to restrict the size of the set. At present, your WHERE clause does include a SARGable clause, but if we are talking about potentially hundreds of thousands of rows per camera (i.e. potential millions per location), it makes sense to further shrink the problem domain.

My recommendation is to choose a sane value for maximum search distance and establish an upper and lower bound on the date. e.g. Let's say your system would normally always take a picture at least every 5 minutes unless the camera is failing. We can set an upper and lower bound of 6 minutes (to allow for "jitter" in the timing) and only rank the images within those bounds. That would look like this:

DECLARE @date datetime,
        @location varchar(4) ,
        @dateUB DATETIME,
        @dateLB DATETIME
SET     @date ='2011-12-13 12:00:00'
SET     @DateUB = DATEADD(minute, 6, @matchDate)
SET     @DateLB = DATEADD(minute, -6, @matchDate)
SET     @location='CS01';
WITH CTE AS (
    SELECT
        *,
        ROW_NUMBER() OVER (PARTITION  BY Camera ORDER BY  abs(datediff(second,@date, [capture_date]))) AS Ranking
    FROM rs_camera_pictures
    WHERE 
        location=@location
    AND capture_date BETWEEN @dateUB AND @dateLB )
SELECT * FROM CTE WHERE Ranking <= 2

If capture_date and location are covered by indexes, this should give you a significant improvement.

Answer 4

Maybe take the top 2 in both directions from the selected date, then take the top 2 from that.

DECLARE @date datetime,
        @location varchar(4)
SET     @date ='2011-12-13 12:00:00'
SET     @location='CS01';
WITH candidates AS (
    SELECT * FROM (
        SELECT TOP 2 *
        FROM rs_camera_pictures
        WHERE location=@location
            AND capture_date <= @date
        ORDER BY capture_date DESC
    ) [before]
    UNION
    SELECT * FROM (
        SELECT TOP 2 *
        FROM rs_camera_pictures
        WHERE location=@location
            AND capture_date >= @date
        ORDER BY capture_date ASC
    ) [after]
),
CTE AS (
    SELECT
        *,
        ROW_NUMBER() OVER (PARTITION  BY Camera ORDER BY  abs(datediff(second,@date, [capture_date]))) AS Ranking
    FROM candidates
    WHERE 
        location=@location
)
SELECT * FROM CTE WHERE Ranking <= 2