Optimize database schema / indexes for faster query result when using LIKE and EXISTS clauses

While implementing a tree structure over a SQL 2005 server database, the query response is taking too long ( below queries are talking more than 5 sec ) when using LIKE clause combined with the EXISTS clause.

The slow queries involve two tables - [SitePath_T] and [UserSiteRight_T] :

CREATE TABLE [dbo].[UserSiteRight_T](
      [UserID_i] [int] NOT NULL
    , [SiteID_i] [int] NOT NULL
    , CONSTRAINT [PKC_UserSiteRight_UserIDSiteID] PRIMARY KEY CLUSTERED ( [UserID_i] ASC, [SiteID_i] ASC )
    , CONSTRAINT [FK_UserSiteRight_UserID] FOREIGN KEY( [UserID_i] ) REFERENCES [dbo].[User_T] ( [ID_i] )
    , CONSTRAINT [FK_UserSiteRight_SiteID] FOREIGN KEY( [SiteID_i] ) REFERENCES [dbo].[Site_T] ( [ID_i] )
) 开发者_StackOverflow

Number of rows ( rights ) for UserID_i = 2484 in [UserSiteRight_T] table is quite small : 545

( UserID_i = 2484 was randomly chosen )

Also, the database is relatively small - only 23000 rows in the [SitePath_T] table :

CREATE TABLE [dbo].[SitePath_T] (
    [SiteID_i] INT NOT NULL,
    [Path_v] VARCHAR(255) NOT NULL,
    CONSTRAINT [PK_SitePath_PathSiteID] PRIMARY KEY CLUSTERED ( [Path_v] ASC, [SiteID_i] ASC ),
    CONSTRAINT [AK_SitePath_Path] UNIQUE NONCLUSTERED ( [Path_v] ASC ),
    CONSTRAINT [FK_SitePath_SiteID] FOREIGN KEY( [SiteID_i] ) REFERENCES [Site_T] ( [ID_i] )

)

I am trying to get only the SiteIDs which have subsites accessible by a certain UserID ( given by the [UserSiteRight_T] table ) as :

SELECT sp.SiteID_i
  FROM SitePath_t sp
 WHERE EXISTS ( SELECT *
              FROM [dbo].[SitePath_T] usp
                 , [dbo].[UserSiteRight_T] uusr
             WHERE uusr.SiteID_i = usp.SiteID_i
               AND uusr.UserID_i = 2484
               AND usp.Path_v LIKE sp.Path_v+'%' )

Below you can find a part of the result where only column sp.SiteID_i is needed/returned - also I added the related corresponding Path_v, UserSiteRight_T.SiteID_i WHERE UserID = 2484 and the corresponding SitePath_T SiteID_i and Path_v matching the LIKE condition :

sp.SiteID_i  sp.Path_v      [UserSiteRight_T].SiteID_i      usp.SiteID_i        usp.Path_v
1           '1.'                        NULL                10054               '1.10054.'
10054       '1.10054.'                  10054               10054               '1.10054.'
10275       '1.10275.'                  10275               10275               '1.10275.'
1533        '1.1533.'                   NULL                2697                '1.1533.2689.2693.2697.'
2689        '1.1533.2689.'              NULL                2697                '1.1533.2689.2693.2697.'
2693        '1.1533.2689.2693.'         NULL                2697                '1.1533.2689.2693.2697.'
2697        '1.1533.2689.2693.2697.'    2697                2697                '1.1533.2689.2693.2697.'
1580        '1.1580.'                   NULL                1581                '1.1580.1581.'
1581        '1.1580.1581.'              1581                1581                '1.1580.1581.'
1585        '1.1580.1581.1585.'         1585                1585                '1.1580.1581.1585.'
222         '1.222.'                    222                 222                 '1.222.'
223         '1.222.223.'                223                 223                 '1.222.223.'
224         '1.222.223.224.'            224                 224                 '1.222.223.224.'
3103        '1.3103.'                   NULL                3537                '1.3103.3529.3533.3537.'
3529        '1.3103.3529.'              NULL                3537                '1.3103.3529.3533.3537.'
3533        '1.3103.3529.3533.'         NULL                3537                '1.3103.3529.3533.3537.'
3537        '1.3103.3529.3533.3537.'    3537                3537                '1.3103.3529.3533.3537.'

Execution plan for the above query :

  |--Nested Loops(Left Semi Join, WHERE:([MyTestDB].[dbo].[SitePath_T].[Path_v] as [usp].[Path_v] like [Expr1007]))
       |--Compute Scalar(DEFINE:([Expr1007]=[MyTestDB].[dbo].[SitePath_T].[Path_v] as [sp].[Path_v]+'%', [Expr1008]=LikeRangeStart([MyTestDB].[dbo].[SitePath_T].[Path_v] as [sp].[Path_v]+'%'), [Expr1009]=LikeRangeEnd([MyTestDB].[dbo].[SitePath_T].[Path_v] as [sp].[Path_v]+'%'), [Expr1010]=LikeRangeInfo([MyTestDB].[dbo].[SitePath_T].[Path_v] as [sp].[Path_v]+'%')))
       |    |--Index Scan(OBJECT:([MyTestDB].[dbo].[SitePath_T].[AK_SitePath_Path] AS [sp]))
       |--Table Spool
            |--Hash Match(Inner Join, HASH:([uusr].[SiteID_i])=([usp].[SiteID_i]))
                 |--Clustered Index Seek(OBJECT:([MyTestDB].[dbo].[UserSiteRight_T].[PKC_UserSiteRight_UserIDSiteID] AS [uusr]), SEEK:([uusr].[UserID_i]=(2484)) ORDERED FORWARD)
                 |--Index Scan(OBJECT:([MyTestDB].[dbo].[SitePath_T].[AK_SitePath_Path] AS [usp]))

And the rewritten query :

SELECT DISTINCT 
       sp.SiteID_i
  FROM [dbo].[SitePath_t] sp
     , [dbo].[SitePath_T] usp
     , [dbo].[UserSiteRight_T] uusr
 WHERE ( uusr.SiteID_i = usp.SiteID_i
   AND uusr.UserID_i = 2484
   AND usp.Path_v LIKE sp.Path_v+'%' )
 ORDER BY SiteID_i ASC

Execution plan :

  |--Hash Match(Aggregate, HASH:([sp].[SiteID_i]))
       |--Nested Loops(Inner Join, WHERE:([MyTestDB].[dbo].[SitePath_T].[Path_v] as [usp].[Path_v] like [Expr1006]))
            |--Hash Match(Inner Join, HASH:([uusr].[SiteID_i])=([usp].[SiteID_i]))
            |    |--Clustered Index Seek(OBJECT:([MyTestDB].[dbo].[UserSiteRight_T].[PKC_UserSiteRight_UserIDSiteID] AS [uusr]), SEEK:([uusr].[UserID_i]=(2484)) ORDERED FORWARD)
            |    |--Index Scan(OBJECT:([MyTestDB].[dbo].[SitePath_T].[AK_SitePath_Path] AS [usp]))
            |--Table Spool
                 |--Compute Scalar(DEFINE:([Expr1006]=[MyTestDB].[dbo].[SitePath_T].[Path_v] as [sp].[Path_v]+'%', [Expr1007]=LikeRangeStart([MyTestDB].[dbo].[SitePath_T].[Path_v] as [sp].[Path_v]+'%'), [Expr1008]=LikeRangeEnd([MyTestDB].[dbo].[SitePath_T].[Path_v] as [sp].[Path_v]+'%'), [Expr1009]=LikeRangeInfo([MyTestDB].[dbo].[SitePath_T].[Path_v] as [sp].[Path_v]+'%')))
                      |--Index Scan(OBJECT:([MyTestDB].[dbo].[SitePath_T].[AK_SitePath_Path] AS [sp]))

All the indexes are in place - Database Engine Tuning Advisor is not suggesting new schema modification - but both queries are returning the correct result in more that 5 seconds - and, as it's a response of an Ajax reques - feels ( and is ) very slow when updating the navigation tree

Any suggestions to optimize / modify database schema / indexes / queries in order to get a faster response ?

Thank you

---

Based on:

SELECT sp.SiteID_i 
  FROM SitePath_t sp 
 WHERE EXISTS ( SELECT * 
              FROM [dbo].[SitePath_T] usp 
                 , [dbo].[UserSiteRight_T] uusr 
             WHERE uusr.SiteID_i = usp.SiteID_i 
               AND uusr.UserID_i = 2484 
               AND usp.Path_v LIKE sp.Path_v+'%' ) 

(which is just fine based on the fact that you're doing a Semi Join).

It's focussing (rightly) on the uusr table first, to find the records for that user. It's already doing a CIX Seek on that, which is good. From there, it's finding the corresponding records in usp according to the SiteID_i fields.

So next consider the fact that it wants to find the Sites by SiteID_i, and what kind of join you want this to be.

How about a Merge Join? That would be nice, but requires the data to be sorted on both sides. That's fine if the indexes are in the right order...

...and after that, you want to be finding stuff based on the Path. So how about:

CREATE INDEX ix_UUSR on [dbo].[UserSiteRight_T] (UserID_i, SiteID_i);
CREATE INDEX ix_usp on [dbo].[SitePath_T] (SiteID_i) INCLUDE (Path_v);

And then another index on SitePath_T that finds the SiteIDs you want:

CREATE INDEX ix_sp on [dbo].[SitePath_T] (Path_v) INCLUDE (SiteID_i);

There may be a Nested Loop used on this final one, but that's hopefully not too bad. The thing that's going to impact your system will be the first two indexes, which should let you see a Merge Join between the two tables in your EXISTS clause.

---

I would try to add an index on the foreign keys in your UserSiteRight_T table - they're not yet indexed, and an index on those fields should speed up the lookups:

CREATE NONCLUSTERED INDEX IX01_UserSiteRight
  ON UserSiteRight_T(UserID_i)

CREATE NONCLUSTERED INDEX IX02_UserSiteRight
  ON UserSiteRight_T(SiteID_i)  

and on your SitePath_T table as well:

CREATE NONCLUSTERED INDEX IX01_SitePath
  ON dbo.SitePath_T(SiteID_i)

Try to put these in place, then run your queries again, and compare the run times and the execution plans - do you see any improvement??

It's a common misconception, but SQL Server does not automatically put an index on a foreign key column (like SiteID_i on SitePath_T), even though the general consensus is that a foreign key is useful and potentially speeds up both enforcement of referential integrity, as well as JOINs over those foreign keys.

---

The self join on SitePath_T to find parents is killing you. Perhaps you should add a column for ParentSiteID_i and use a normal recursive CTE?

Then it becomes:

WITH Recurse_CTE AS (
  SELECT 
    us.SiteID_i
  , us.ParentSiteID_i
  , 0 AS RecurseDepth_i
  FROM dbo.SitePath_T us
  JOIN dbo.UserSiteRight_T uusr ON us.SiteID_i = uusr.SiteID_i
  WHERE uusr.UserID_i = 2484
  UNION ALL
  SELECT 
    us.SiteID_i
  , us.ParentSiteID_i
  , rcs.RecurseDepth_i+1 AS RecurseDepth_i
  FROM dbo.SitePath_T us
  JOIN Recurse_CTE rcs ON us.SiteID_i = rcs.ParentSiteID_i
  )
SELECT * FROM Recurse_CTE

Throw an index on SitePath_T (ParentSiteID_i) and performance should be snappy.