2

I am working on a concept for database synchronization recently. The scenario is as follows:

  • there is a master table "Items" with 1M+ rows in it

        CREATE TABLE [dbo].[Item](
            [Id] [uniqueidentifier] NOT NULL,
            [Title] [nvarchar](50) NULL,
            [Modified] [datetime2](7) NOT NULL,
         CONSTRAINT [PK_Item] PRIMARY KEY CLUSTERED ([Id] ASC) ON [PRIMARY]
    
  • we want to sync data to a client in a very flexible way - so we are playing around with a "Items_sync" table, that contains an entry for every user and every item they should download during a sync process.

    CREATE TABLE [dbo].[Item_syncfilter](
        [Id] [bigint] IDENTITY(1,1) NOT NULL,
        [ItemId] [uniqueidentifier] NOT NULL,
        [Modified] [datetime2](7) NOT NULL,
        [IsDeleted] [bit] NOT NULL,
        [UserId] [bigint] NOT NULL,
     CONSTRAINT [PK_Item_syncfilter] PRIMARY KEY CLUSTERED ([Id] ASC) ON [PRIMARY]
    

Now what makes this a bit complicated is the following: there are numerous reasons why a particular user may get the permission to download a particular row. These are

  • he is added to the contributors group
  • he is added to the administrators group
  • an item is directly assigned to him/her

Thus, there may be multiple rows for the same user for a single item stating that she is allowed to download that item.

Also, the sync process needs to work incrementally. Meaning:

  • If user Andrew has access to item A, and it is modified, next time he syncs he should receive the newest version
  • Is user Andrew did not have access to item A, but then he is added to the administrators group (=> gets a corresponding Item_sync entry) he should download the item the next time he syncs.
  • If Andrew had already synced item A and is added to the administrators group, nothing should be synced.

Now what we came up with up until now is the following query:

declare @userid bigint;
declare @date datetime2(7);
set @date = '2018-05-02 13:00:00.0000000';
set @userid = 5;

select i.*, 0 as Toombstoned from item i
where 
-- clause 1: get all modified items where there exists at least one non-deleted sync row
(i.modified >= @date
    -- and there exists at least one non-deleted syncfilter
    and exists (select id from item_syncfilter where itemid = i.id and userid = @userid and isdeleted = 0))
-- clause 2: get all items, which were not modified, but their sync rows are newer (toombstoned or not)
or (i.modified <  @date
    -- and there is at least one younger, non-deleted syncfilter (permission was added to user)
    and exists (select id from item_syncfilter where itemid = i.id and userid = @userid and isdeleted = 0 and modified >  @date)
    -- make sure this item was not already synced by an older valid and non-deleted filter
    and not exists (select id from item_syncfilter where itemid = i.id and userid = @userid and isdeleted = 0 and modified <  @date))

union all
select i.*, 1 as Toombstoned from item i
where 
-- clause 3: get all toombstoned items
--                  - where no non-deleted syncfilter exists
--                  - and there is a deleted sync filter younger than "date"
(not exists (select id from item_syncfilter where itemid = i.id and userid = @userid and isdeleted = 0)
    and exists (select id from item_syncfilter where itemid = i.id and userid = @userid and isdeleted = 1 and modified >  @date))

However this performs quite badly due to the 5 usages of "exists" i.e. for 1 million rows in the main table, the query runs for 5 seconds and the STATISTICS IO output shows a looooot of reads, even if the query only returns a small subset of data.

Can you give me any hint how we could improve this query dramatically?

UPDATE
Thanks for your responses. The following SQL snippet shows

  • the complete table schema
  • including indexes that I use
  • and some test data which showcases how the query works


-- ########################
-- ## Sync Item
-- ########################

CREATE TABLE [dbo].[Item](
    [Id] [uniqueidentifier] NOT NULL,
    [Title] [nvarchar](100) NULL,
    [Modified] [datetime2](7) NOT NULL,
 CONSTRAINT [PK_Item] PRIMARY KEY CLUSTERED ([Id] ASC) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]
GO
ALTER TABLE [dbo].[Item] ADD  CONSTRAINT [DF_Item_Id]  DEFAULT (newid()) FOR [Id]
GO
ALTER TABLE [dbo].[Item] ADD  CONSTRAINT [DF_Item_Modified]  DEFAULT (getutcdate()) FOR [Modified]
GO

CREATE NONCLUSTERED INDEX [IX_ItemModified] ON [dbo].[Item]
(
    [Modified] DESC
) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO


-- ########################
-- ## sync filter
-- ########################

CREATE TABLE [dbo].[Item_syncfilter](
    [Id] [bigint] IDENTITY(1,1) NOT NULL,
    [ItemId] [uniqueidentifier] NOT NULL,
    [Modified] [datetime2](7) NOT NULL,
    [IsDeleted] [bit] NOT NULL,
    [UserId] [bigint] NOT NULL,
 CONSTRAINT [PK_Item_syncfilter] PRIMARY KEY CLUSTERED ([Id] ASC) WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]
GO
ALTER TABLE [dbo].[Item_syncfilter] ADD  CONSTRAINT [DF_Item_syncfilter_Modified]  DEFAULT (getutcdate()) FOR [Modified]
GO
ALTER TABLE [dbo].[Item_syncfilter] ADD  CONSTRAINT [DF_Item_syncfilter_IsDeleted]  DEFAULT ((0)) FOR [IsDeleted]
GO
ALTER TABLE [dbo].[Item_syncfilter] ADD  CONSTRAINT [DF_Item_syncfilter_UserId]  DEFAULT (CONVERT([int],((20)+(1))*rand())) FOR [UserId]
GO

CREATE NONCLUSTERED INDEX [IX_SyncItemModified] ON [dbo].[Item_syncfilter]
(
    [UserId] ASC,
    [ItemId] ASC,
    [IsDeleted] ASC,
    [Modified] DESC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO
CREATE NONCLUSTERED INDEX [IX_SyncItemItemId] ON [dbo].[Item_syncfilter]
(
    [ItemId] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO


-- ########################
-- ## TestData
-- ########################

INSERT [dbo].[Item] ([Id], [Title], [Modified]) VALUES (N'a14ae781-b595-4fa8-942f-3abf8d848bdf', N'1 new deleted, 1 old still valid  NOTINSYNC', CAST(N'2018-05-01T14:10:25.8400000' AS DateTime2))
INSERT [dbo].[Item] ([Id], [Title], [Modified]) VALUES (N'45b71309-49d9-4457-a784-52dcc1331ec2', N'Modified and all filters new', CAST(N'2018-05-03T06:33:04.7200000' AS DateTime2))
INSERT [dbo].[Item] ([Id], [Title], [Modified]) VALUES (N'cf01ebde-7f11-4bad-a32c-54caa6fca14b', N'No new filter NOTINSYNC', CAST(N'2018-05-01T14:10:11.0833333' AS DateTime2))
INSERT [dbo].[Item] ([Id], [Title], [Modified]) VALUES (N'80fc71ff-e984-4dae-bdf1-98e02d27c926', N'All deleted', CAST(N'2018-05-02T14:09:48.6200000' AS DateTime2))
INSERT [dbo].[Item] ([Id], [Title], [Modified]) VALUES (N'a5fa6d29-5c2b-4edb-8390-aeec44232368', N'Modified', CAST(N'2018-05-02T14:09:48.6200000' AS DateTime2))
INSERT [dbo].[Item] ([Id], [Title], [Modified]) VALUES (N'5995209d-c571-40b8-9ff6-b650add6ffbf', N'Some filters new NOTINSYNC', CAST(N'2018-05-01T14:10:04.2900000' AS DateTime2))
INSERT [dbo].[Item] ([Id], [Title], [Modified]) VALUES (N'd79a3967-780c-46e3-b1ec-e6038214e711', N'All filters new', CAST(N'2018-05-01T14:10:04.2900000' AS DateTime2))
SET IDENTITY_INSERT [dbo].[Item_syncfilter] ON 

INSERT [dbo].[Item_syncfilter] ([Id], [ItemId], [Modified], [IsDeleted], [UserId]) VALUES (1, N'a5fa6d29-5c2b-4edb-8390-aeec44232368', CAST(N'2018-05-01T14:13:30.5000000' AS DateTime2), 0, 1)
INSERT [dbo].[Item_syncfilter] ([Id], [ItemId], [Modified], [IsDeleted], [UserId]) VALUES (2, N'a5fa6d29-5c2b-4edb-8390-aeec44232368', CAST(N'2018-05-01T14:13:37.8133333' AS DateTime2), 1, 1)
INSERT [dbo].[Item_syncfilter] ([Id], [ItemId], [Modified], [IsDeleted], [UserId]) VALUES (3, N'd79a3967-780c-46e3-b1ec-e6038214e711', CAST(N'2018-05-02T16:15:04.5933333' AS DateTime2), 0, 1)
INSERT [dbo].[Item_syncfilter] ([Id], [ItemId], [Modified], [IsDeleted], [UserId]) VALUES (4, N'd79a3967-780c-46e3-b1ec-e6038214e711', CAST(N'2018-05-02T16:15:07.1266667' AS DateTime2), 0, 1)
INSERT [dbo].[Item_syncfilter] ([Id], [ItemId], [Modified], [IsDeleted], [UserId]) VALUES (5, N'a14ae781-b595-4fa8-942f-3abf8d848bdf', CAST(N'2018-05-01T14:13:37.8133333' AS DateTime2), 0, 1)
INSERT [dbo].[Item_syncfilter] ([Id], [ItemId], [Modified], [IsDeleted], [UserId]) VALUES (6, N'a14ae781-b595-4fa8-942f-3abf8d848bdf', CAST(N'2018-05-02T14:15:31.7666667' AS DateTime2), 1, 1)
INSERT [dbo].[Item_syncfilter] ([Id], [ItemId], [Modified], [IsDeleted], [UserId]) VALUES (7, N'cf01ebde-7f11-4bad-a32c-54caa6fca14b', CAST(N'2018-05-01T14:13:37.8133333' AS DateTime2), 0, 1)
INSERT [dbo].[Item_syncfilter] ([Id], [ItemId], [Modified], [IsDeleted], [UserId]) VALUES (8, N'cf01ebde-7f11-4bad-a32c-54caa6fca14b', CAST(N'2018-05-01T14:13:37.8133333' AS DateTime2), 1, 1)
INSERT [dbo].[Item_syncfilter] ([Id], [ItemId], [Modified], [IsDeleted], [UserId]) VALUES (9, N'80fc71ff-e984-4dae-bdf1-98e02d27c926', CAST(N'2018-05-01T14:13:37.8133333' AS DateTime2), 1, 1)
INSERT [dbo].[Item_syncfilter] ([Id], [ItemId], [Modified], [IsDeleted], [UserId]) VALUES (10, N'80fc71ff-e984-4dae-bdf1-98e02d27c926', CAST(N'2018-04-30T14:13:37.8133333' AS DateTime2), 1, 1)
INSERT [dbo].[Item_syncfilter] ([Id], [ItemId], [Modified], [IsDeleted], [UserId]) VALUES (11, N'5995209d-c571-40b8-9ff6-b650add6ffbf', CAST(N'2018-04-30T14:13:37.8133333' AS DateTime2), 0, 1)
INSERT [dbo].[Item_syncfilter] ([Id], [ItemId], [Modified], [IsDeleted], [UserId]) VALUES (12, N'5995209d-c571-40b8-9ff6-b650add6ffbf', CAST(N'2018-05-02T16:39:20.5066667' AS DateTime2), 0, 1)
INSERT [dbo].[Item_syncfilter] ([Id], [ItemId], [Modified], [IsDeleted], [UserId]) VALUES (13, N'5995209d-c571-40b8-9ff6-b650add6ffbf', CAST(N'2018-05-02T16:39:21.7066667' AS DateTime2), 1, 1)
INSERT [dbo].[Item_syncfilter] ([Id], [ItemId], [Modified], [IsDeleted], [UserId]) VALUES (14, N'45b71309-49d9-4457-a784-52dcc1331ec2', CAST(N'2018-05-03T06:33:34.7900000' AS DateTime2), 0, 1)
INSERT [dbo].[Item_syncfilter] ([Id], [ItemId], [Modified], [IsDeleted], [UserId]) VALUES (15, N'45b71309-49d9-4457-a784-52dcc1331ec2', CAST(N'2018-05-03T06:33:38.0300000' AS DateTime2), 1, 1)
SET IDENTITY_INSERT [dbo].[Item_syncfilter] OFF

To generate the test data I used:

   -- ## Create many items items
   DECLARE @startnum INT=1;
   DECLARE @endnum INT=5000;

   WITH gen AS (
       SELECT @startnum AS num
       UNION ALL
       SELECT num+1 FROM gen WHERE num+1<=@endnum
   ) 

   insert into [Item] ([Id], [Title], [Modified])
   (SELECT newId() as [Id]
         ,[Title]  + ' -#'+ CONVERT(varchar(1000), n.num) as [Title]
         ,[Modified]
     FROM [Item]
     cross join gen as n)
   option (maxrecursion 10000);

   select count(*) as item_count from item;

   -- ## generate syncfilter rows for 10 users
   set @startNum = 1;
   set @endNum = 10;

   WITH gen AS (
       SELECT @startnum AS num
       UNION ALL
       SELECT num+1 FROM gen WHERE num+1<=@endnum
   )    

    insert into item_syncfilter ([ItemId],[Modified],[IsDeleted],[UserId])
    (select i.[Id], DATEADD(month, -6, i.[Modified]), 0 as IsDeleted, n.num as [Userid] from item i 
       left outer join item_syncfilter s on s.itemid = i.id
         cross join gen as n
       where s.id is null)
    option (maxrecursion 10000);

    select count(*) item_syncfilter_count from Item_syncfilter;

This creates 35K items and 350K syncfilter rows.

The statistics IO output is

(15003 rows affected)
Table 'Item_syncfilter'. Scan count 35013, logical reads 105648, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Item'. Scan count 1, logical reads 610, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

(21 rows affected)

(1 row affected)

You can download the execution plan from here

1

Update:

I went along looked at the execution plan of the separate sub-clauses of the query.

For clause 3 (finding tombstoned items), the execution plan showed that the following index would improve the performance:

    CREATE NONCLUSTERED INDEX [IX_SyncItemDeletedItems] ON [dbo].[Item_syncfilter] 
    (
        [IsDeleted],
        [UserId],
        [Modified])
    INCLUDE ([ItemId])

Running only clause 3 of the query with "statistics IO on":

    set statistics io on

    declare @userid bigint;
    declare @date datetime2(7);
    set @date = '2018-05-02 13:00:00.0000000';
    set @userid = 5;

    select i.*, 1 as Toombstoned from item i
    where 
    -- clause 3: get all toombstoned items
    --                  - where no non-deleted syncfilter exists
    --                  - and there is a deleted sync filter younger than "date"
    (not exists (select id from item_syncfilter where itemid = i.id and userid = @userid and isdeleted = 0)
        and exists (select id from item_syncfilter where itemid = i.id and userid = @userid and isdeleted = 1 and modified >  @date))

shows before:

  (0 rows affected)
  Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
  Table 'Item_syncfilter'. Scan count 1, logical reads 1433, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

  (1 row affected)

after:

  (0 rows affected)
  Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
  Table 'Item_syncfilter'. Scan count 1, logical reads 3, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

  (1 row affected)

... so this greatly reduces the number of logical reads!

For clause 1 and 2, it was more interesting. If run separately, they performed quite well, but combined, they resulted in a terrible execution plan:

    set statistics io on

    declare @userid bigint;
    declare @date datetime2(7);
    set @date = '2018-05-02 13:00:00.0000000';
    set @userid = 5;

    select i.*, 0 as Toombstoned from item i
    where 
    -- clause 1: get all modified items where there exists at least one non-deleted sync row
    (i.modified >= @date
        -- and there exists at least one non-deleted syncfilter
        and exists (select id from item_syncfilter where itemid = i.id and userid = @userid and isdeleted = 0))
    -- clause 2: get all items, which were not modified, but their sync rows are newer (toombstoned or not)
    or (i.modified <  @date
        -- and there is at least one younger, non-deleted syncfilter (permission was added to user)
        and exists (select id from item_syncfilter where itemid = i.id and userid = @userid and isdeleted = 0 and modified >  @date)
        -- make sure this item was not already synced by an older valid and non-deleted filter
        and not exists (select id from item_syncfilter where itemid = i.id and userid = @userid and isdeleted = 0 and modified <  @date))

Returns

    (0 rows affected)
    Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    Table 'Item_syncfilter'. Scan count 229376, logical reads 688128, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    Table 'Item'. Scan count 1, logical reads 3980, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

    (1 row affected)

The reason is the following execution step in the execution plan:

enter image description here

So as you can see, sql server scans the clustered index for items where the modified date is >= @date OR < @date, which more or less returns the whole table -> thus, those many reads

So what I did was to simply split the two clauses, which were combined using "OR" into two separate queries which are just combined using UNION ALL:

    set statistics io on

    declare @userid bigint;
    declare @date datetime2(7);
    set @date = '2018-05-02 13:00:00.0000000';
    set @userid = 5;

    select i.*, 0 as Toombstoned from item i
    where 
    -- clause 1: get all modified items where there exists at least one non-deleted sync row
    (i.modified >= @date
        -- and there exists at least one non-deleted syncfilter
        and exists (select id from item_syncfilter where itemid = i.id and userid = @userid and isdeleted = 0))

    -- clause 2: get all items, which were not modified, but their sync rows are newer (toombstoned or not)
    union all
    select i.*, 0 as Toombstoned from item i
        where i.modified <  @date
        -- and there is at least one younger, non-deleted syncfilter (permission was added to user)
        and exists (select id from item_syncfilter where itemid = i.id and userid = @userid and isdeleted = 0 and modified >  @date)
        -- make sure this item was not already synced by an older valid and non-deleted filter
        and not exists (select id from item_syncfilter where itemid = i.id and userid = @userid and isdeleted = 0 and modified <  @date)

which interestingly yields the following statistics

    (0 rows affected)
    Table 'Workfile'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    Table 'Item_syncfilter'. Scan count 3, logical reads 12, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    Table 'Item'. Scan count 2, logical reads 8, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

    (1 row affected)

=> so from 229376 down to 3, from 688128 down to 12, etc. This is a huge gain!

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.