How can I optimize this query over this logging table?

Question

I am trying to optimize a table layout for a table that logs events.

The log table contains three relevant columns: Timestamp, ItemId, LocationId
Each row means that at a given time, a certain item has been seen at a certain location.

2017-01-01 10:00    Item A has been seen at location 1
2017-01-01 10:01    Item A has been seen at location 1
2017-01-01 11:00    Item B has been seen at location 1
2017-01-01 11:01    Item B has been seen at location 2
2017-01-01 11:02    Item A has been seen at location 2
2017-01-01 11:03    Item B has been seen at location 1

There are about 100 different locations, 20.000 new items per day, a million events per day, and 14 days of logs.

Now I need to run queries on this data, such as:

• Which items were at location '1' at time '2017-01-01 11:00'
  (= which items have been seen at location 1 before time '2017-01-01 11:00', and were not seen elsewhere after being seen at 1 but before '2017-01-01 11:00'

To get this data I can execute

SELECT DISTINCT  ItemId     
FROM events e1 
WHERE LocationId = 1
  AND e1.TimeStamp < '2017-01-01 11:00'
  AND NOT EXISTS (SELECT 1 FROM events e2
                  WHERE e2.LocationId <> e1.LocationId
                    AND e2.ItemId = e1.ItemId
                    AND e2.TimeStamp >= e1.TimeStamp
                    AND e2.TimeStamp <'2017-01-01 11:00')

Currently, this query takes about 15 seconds, when there is zero load on the database. The goal is to execute this query in less that 100ms, with heavy load. I don't think this is possible with the current design.

I have an index on item and location, and a clustered index on timestamp

Is there a table layout that would allow me to perform this query more efficiently?

Or is there a query that would work with the existing table?

Answer 1

You could try a different query:

SELECT ItemID
  FROM (SELECT ItemID
              ,ROW_NUMBER() OVER (PARTITION BY ItemID ORDER BY TimeStamp DESC) rn
              ,LocationId
          FROM events
         WHERE TimeStamp < '2017-01-01 11:00'
       ) e1
  WHERE LocationId = 1
    AND rn = 1
;

No promises that this will do any better (it could actually be worse); it's just a different approach.

Also - if it makes sense, you may want to put a lower bound on the possible TimeStamp values; if you can ignore everything more than 12 hours prior to the time you're looking for, that could eliminate a large number of rows.

Answer 2

I can't reproduce the issue. I'm not sure if I did the data prep wrong or the machine I'm testing against is very different than yours. With that said, it may be worth tuning the system instead of the query.

In my table I have 14.5 million rows, 100 distinct locations, and 338k distinct items. Each item moves every 90 minutes for three days and stops moving after that. Here's the code:

CREATE TABLE [events] (
    [TimeStamp] DATETIME NOT NULL,
    ItemId BIGINT NOT NULL,
    LocationId BIGINT NOT NULL,
    FILLER VARCHAR(60) NOT NULL
);

CREATE CLUSTERED INDEX CI_events ON [events] ([TimeStamp]);

INSERT INTO [events] WITH (TABLOCK)
SELECT *
FROM
(
    SELECT 
      DATEADD(MINUTE, 90 * t.cnt, DATEADD(SECOND, ItemId * (14 * 86400.) / (17. * 20000), '20161220')) [TimeStamp]
    , i.ItemId
    , 1 + ((1 + i.ItemId % 100) + 7 * t.cnt) % 100 LocationId
    , REPLICATE('Z', 30) FILLER
    FROM
    (
        SELECT TOP (17 * 20000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) ItemId
        FROM master..spt_values t1
        CROSS JOIN master..spt_values t2
    ) i
    CROSS JOIN (
        SELECT TOP (48) -1 + ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) cnt
        FROM master..spt_values t1
    ) t
) t2
WHERE t2.[TimeStamp] >= '20161223'
OPTION (MAXDOP 1);


CREATE INDEX IX_events_Loc_Item ON [events] (LocationId, ItemId);

CREATE INDEX IX_events_Item_Loc ON [events] (ItemId, LocationId);

Based on your query plan it looks like you have another nonclustered index on the table that you didn't mention. I'm going to assume that it's on location and item.

Your query runs in about 250 ms on my machine:

SELECT DISTINCT ItemId     
FROM events e1 
WHERE LocationId = 1
  AND e1.[TimeStamp] < '2017-01-01 11:00'
  AND NOT EXISTS (SELECT 1 FROM [events] e2
                  WHERE e2.LocationId <> e1.LocationId
                    AND e2.ItemId = e1.ItemId
                    AND e2.[TimeStamp] >= e1.[TimeStamp]
                    AND e2.[TimeStamp] <'2017-01-01 11:00')
OPTION (MAXDOP 1);

The query can also be written to not use a join:

SELECT ItemId
FROM events e1
WHERE e1.[TimeStamp] < '2017-01-01 11:00'
GROUP BY ItemId
HAVING MAX(CASE WHEN LocationID = 1 THEN ([TimeStamp]) ELSE NULL END) = MAX([TimeStamp])
OPTION (MAXDOP 1);

Query plan:

The rewrite parallelizes well but it's unlikely to get to the 100 ms target time. It's doing an index scan of 10 million rows. The filter on TimeStamp simply isn't selective enough. It's really hard to know if this will help, but you could add a column that increments per ItemId every time an item moves. That would allow you to seek over less rows to find the next relevant event for each item. Here's how I created the table:

CREATE TABLE [events_with_id] (
    LocationId BIGINT NOT NULL,
    ItemId BIGINT NOT NULL,
    [TimeStamp] DATETIME NOT NULL,
    Item_move_id  BIGINT NOT NULL,
    FILLER VARCHAR(60) NOT NULL
);

CREATE CLUSTERED INDEX CI_events_with_id ON [events_with_id] ([TimeStamp] );

INSERT INTO [events_with_id] WITH (TABLOCK)
SELECT 
  LocationId
, ItemId
, [Timestamp]
, ROW_NUMBER() OVER (PARTITION BY ItemId ORDER BY [Timestamp])
, REPLICATE('Z', 30)
FROM [events];

CREATE INDEX IX_events_new_loc_start ON [events_with_id] (LocationId, [TimeStamp])
    INCLUDE (ItemId, Item_move_id);
CREATE UNIQUE INDEX IX_events_item_item_move ON [events_with_id] (ItemId, Item_move_id);

Here's the query:

SELECT DISTINCT ItemId     
FROM [events_with_id] e1 
WHERE LocationId = 1
  AND e1.[TimeStamp] < '2017-01-01 11:00'
  AND NOT EXISTS (SELECT 1 FROM [events_with_id] e2
                  WHERE e2.Item_move_id = e1.Item_move_id + 1
                    AND e2.ItemId = e1.ItemId
                    AND e2.[TimeStamp] <'2017-01-01 11:00')
OPTION (LOOP JOIN, MAXDOP 1);

Without the hint I was getting a merge join which didn't perform very well. This query runs in 175 ms on my machine, so it's a slight improvement over the first query.

Another option is to include both the start and end time for each row in the table. You'd have to keep this updated which will be more difficult than simply inserting a row every time an item moves. Here's code to initially populate it:

CREATE TABLE [events_with_end] (
    LocationId BIGINT NOT NULL,
    ItemId BIGINT NOT NULL,
    [Start_TimeStamp] DATETIME NOT NULL,
    [End_TimeStamp] DATETIME NULL,
    FILLER VARCHAR(60) NOT NULL
);

CREATE CLUSTERED INDEX CI_events_new ON [events_with_end] ([Start_TimeStamp] );

INSERT INTO [events_with_end] WITH (TABLOCK)
SELECT LocationId, ItemId, [Timestamp], LEAD([Timestamp]) OVER (PARTITION BY ItemId ORDER BY [Timestamp]), REPLICATE('Z', 30)
FROM [events];

CREATE INDEX IX_events_new_loc_start ON [events_with_end] (LocationId, [Start_TimeStamp]) INCLUDE (ItemId, [End_TimeStamp]);

CREATE INDEX IX_events_new_loc_end ON [events_with_end] (LocationId, [End_TimeStamp]) INCLUDE (ItemId);

Now I can do a more targeted seek, although SQL Server won't be able to index seek on both the start and the end times:

SELECT DISTINCT ItemId
FROM [events_with_end] e1
WHERE LocationID = 1 
AND e1.[Start_TimeStamp] < '2017-01-01 11:00'
AND (e1.[End_TimeStamp] > '2017-01-01 11:00' OR e1.[End_TimeStamp] IS NULL)
OPTION (MAXDOP 1);

That query uses the IX_events_new_loc_end index and finishes in around 10 ms. If I change the filter time to be closer to the start of the table (2016-12-25 11:00) then I use the other index:

The query still finishes in around 10 ms. It's not clear if it's necessary to create both indexes.